Live range priority in Greedy RA


In the Greedy RA, I see that the enqueue method adds higher priority to the live intervals based on their sizes.

Isn’t it makes sense to give priority to live intervals that start and end in a loop? Please let me know if the code is already achieving it in some way.

Also consider correcting me, if this approach is wrong.

Hi Dangeti,

As far as I know, 'calculateSpillWeightAndHint' considers loop
induction variable and the spill weight affects evict and spill. If it
is not enough for you, I guess you can add some heuristic code on the

JinGu Kang
2018년 10월 30일 (화) 오전 11:51, Dangeti Tharun kumar via llvm-dev
<>님이 작성:

This may or may not be a good idea. Here’s some hand-wavy reason why it may not be a good idea:

  • It will be tricky to balance the priority based on liverange size with an extra criterium like block frequency as you propose here. In the past I’ve seen two criteria working against each other lead to worse allocations as there is no obvious clear cut at which point the first or at which point the 2nd criterium should be use.
  • Liverange splitting should typically separate the liveranges inside the loop from the liveranges outside, so it’s possible there are few interferences between values inside the loop and outside the loop left.

Ultimately the best way to argue here, is running benchmarks and looking at concrete situations. So the best way to prove this is to implement it, run it on various benchmarks and see how it performs.

  • Matthias


I had a look at this ‘calculateSpillWeightAndHint’ function, spill weights are being calculated considering no of uses, defs, loops etc.
Why not these weights be used as priority, seems they are good enough to serve as priority, instead doing it by their sizes?

As far as I know, there is a good comment about priority on enqueue as below.

  /// Allow the target to reverse allocation order of local live ranges. This
  /// will generally allocate shorter local live ranges first. For targets with
  /// many registers, this could reduce regalloc compile time by a large
  /// factor. It is disabled by default for three reasons:
  /// (1) Top-down allocation is simpler and easier to debug for targets that
  /// don't benefit from reversing the order.
  /// (2) Bottom-up allocation could result in poor evicition decisions on some
  /// targets affecting the performance of compiled code.
  /// (3) Bottom-up allocation is no longer guaranteed to optimally color.
  virtual bool reverseLocalAssignment() const { return false; }

If you are implementing your custom target, you could control the
priority of enqueue with 'reverseLocalAssignment()'. However, the
allocated registers can be evicted with weight comparison and the live
ranges can be split when the all of physical registers are consumed.
The priority on enqueue does not guarantee allocation of physical
register. I am not code owner of register allocation so I might be

JinGu Kang
2018년 11월 8일 (목) 오전 10:02, Dangeti Tharun kumar
<>님이 작성: