Looks good.

Sorry, I don't have an LLVM sandbox these days. Maybe ask on llvm-commits?

Looks good. I'm all for eliminating recursion.

In D17304#354859, @qcolombet wrote:

Hi Jakob,

Thanks for the root causing this issue.

Will you provide a patch or should Fiona or I work on it?

In D17304#353952, @escha wrote:

To elaborate on this precise example: we have 4000 basic blocks. They're a linear chain of small loops (artificial test). The hopfield network grows at a rate of 2 blocks per call, which results in O(N^2) overall behavior. 256 registers * 4000^2 basic blocks == enormous, big, scary number.

In D13417#261721, @spatel wrote:

I think that shows the intended usage: slack is limited both by a dynamic calculation and a heuristic. Without those limits, we're almost certain to increase the critical path and lose performance (as shown in the examples here).

Looks good!

Instead of maintaining a bitvector in RAGreedy, how about asking LiveRegMatrix? It can tell you if the corresponding LiveIntervalUnion is empty.

Very nice! Should those reg_empty calls be reg_nodbg_empty?