JIT LSRA Throughput: Short-circuit register selection

[CarolEidt]

The loop over all the candidate registers in LinearScan::tryAllocateFreeReg() and in LinearScan::allocateBusyReg() could be short-circuited when a register is found that has the best possible score. Additionally, in the case of MinOpts, it could potentially short-circuit as soon as a suitable candidate is found, though one would want to weight the throughput benefit against the code quality impact.

category:throughput
theme:register-allocator
skill-level:expert
cost:medium

[RussKeldorph]

/cc @sivarv

[pgavlin]

The loop over all the candidate registers in LinearScan::tryAllocateFreeReg() and in LinearScan::allocateBusyReg() could be short-circuited when a register is found that has the best possible score

Outside of minopts, is it possible to know the best possible score for a particular attempt a priori?

[CarolEidt]

Outside of minopts, is it possible to know the best possible score for a particular attempt a priori?

So, a bit more description would have been warranted here, and mea culpa for that (this issue has been around for a very long time before migrating from the old work items, and I just copied most of the text from there). There are a couple of ways a register is evaluated as a candidate. The first is the score. And it is possible to know the best possible score based on the characteristics of the RefPosition itself, e.g. whether it has a relatedInterval. However, the second consideration is comparing the location of the next use of the physical register (currently, since we don't do any pre-allocation, that's always a fixed reg reference). Determining the best value for that a priori doesn't seem really practical. However, the way I currently think about this "short-circuiting" is that for both tryAllocateFreeReg and allocateBusyReg, we should ensure that 1) the cheaper and higher value criteria are evaluated first, and as soon as it fails a criteria that would cause it be scored lower than an existing candidate, the loop should short-circuit. I think that, to accomplish this cleanly, those methods could use some cleaning up.

It may be that we could maintain a list of available registers, sorted by nearest next reference. Then it would indeed be possible to short-circuit. That said, one would want to evaluated the throughput impact of the various options.

[kunalspathak]

We did fair amount of refactoring in #45135 that would short circuit the other heuristics once we found a single register candidate out of set of registers.