RegAllocGreedy: Improve live interval order in ReverseLocal mode

[MatzeB]

Summary

When allocating live intervals in linear order and all of them are local
to a single basic block you get an optimal coloring. This is also true
if you reverse the order, but it is not true if you sort live ranges
beginnings in reverse order, change to sort live range endings in
reverse order. Take the following live ranges for example:

|---| |--------|

They get colored suboptimally with 3 registers if you sort the live range
starting points in reverse order (but optimally with live range begins in order,
or live range ends in reverse order).

No testcase as none of the (in tree) targets use reverse order mode.

[MatzeB]

• RegAllocGreedy: Allow target to specify register class ordering.

[MatzeB]

Please ignore the last update, it should go into an own revision, but arc diff attached it to the last one in my local branch...

[qcolombet]

Hi Matthias,

Nice catch!

When you commit, please detail the example by naming the interval and giving the different orders (non optimal, what we have now, and optimal).
The current explanations are fine, but it took a bit of thought to reconstruct why it is happening and I prefer no-brainer comment :).

Did you see any differences for in-tree targets on the LLVM test-suite?

Thanks,
-Quentin

llvm/trunk/lib/CodeGen/RegAllocGreedy.cpp

if (ExtraRegInfo[Reg].Stage == RS_Assign && !ForceGlobal && !LI->empty() &&
       // are singly defined, this produces optimal coloring in the absence of
       // global interference and other constraints.
       if (!ReverseLocal)
         Prio = LI->beginIndex().getInstrDistance(Indexes->getLastIndex());
       else {
         // Allocating bottom up may allow many short LRGs to be assigned first
         // to one of the cheap registers. This could be much faster for very
         // large blocks on targets with many physical registers.
-        Prio = Indexes->getZeroIndex().getInstrDistance(LI->beginIndex());
+        Prio = Indexes->getZeroIndex().getInstrDistance(LI->endIndex());
       }
     }
     else {
       // Allocate global and split ranges in long->short order. Long ranges that
       // don't fit should be spilled (or split) ASAP so they don't create
       // interference.  Mark a bit to prioritize global above local ranges.
       Prio = (1u << 29) + Size;
     }