Unrolling, PRE/LICM, and register pressure

[DragonDisciple]

I maintain an embedded target backend that has 16 integer registers.

One of our benchmarks is a 10x10 integer matrix multiplication using the traditional 3 nested loop approach.

A change made a few weeks ago (https://github.com/llvm/llvm-project/pull/155415) is causing some havoc in this loop that I’m becoming a bit overwhelmed in tackling.

• The innermost loop is fully unrolled 10x. This leads to one set of loads becoming invariant
• PRE hoists those 10 loads into the middle loop
• The middle loop is then unrolled in one of two ways, with various preference variants:
  • Unrolls and jams by 2
  • Fully unrolls by 10
• LICM hoists some more
• The result is a loop preheader that has 20/100 loads, each of which are live-in to the loop header, and results in a massive number of spills/restores during register allocation.

The root cause here is that we are receiving IR into the machine backend which has excessive register pressure. It looks like the front/middle end doesn’t frequently care about this. LICM even says “Rematerialization of hoisted instructions to reduce register pressure is the responsibility of the back-end”. However, the passes I’m seeing that care about pressure seem to only be doing even more hoisting. MachineSink has a “sink for register pressure”, but it seems to be mostly unused and has a potential bug even (The check to avoid GOT/Constant pool loads is inverted from what I’d expect).

So with that, I suspect the best option here is to enhance the unroller preferences to avoid so much expansion. Any breadcrumbs would be appreciated!

[nikic]

You may want to try this patch:

[MachineLICM] Rematerialize instructions that may be hoisted before LICM

Not sure about that precise approach, but I’d expect the general fix here to be “actually do the register pressure based sinking we promise to do, but actually don’t”.

[nvjle]

This RFC might also be interesting:

[RFC] Improving MachineSink sinking into Cycles

Hi, I have a patch that extends the capabilities of sinking into cycles. The aim for this patch is to make smarter decisions when sinking. This is a fairly big change in logic, so would appreciate people’s input/suggestions. At a glance, this patch: adds register pressure estimation for the whole loop and preheader, only calculating it once. considers sinking multiple instructions at once if it would reduce register pressure of a critical pressure set adds prioritisation for sink candidates C…

[DragonDisciple]

Thanks much for the assist. I hadn’t considered searching for active PRs since I imagined that the problem seemed to not exist for upstream backends (otherwise I’d imagine #155415 would have had more push-back).

I’ll try out this patch and leave a comment or two if it makes sense!

The MachineSink changes, at least those already available upstream, don’t seem work in my case because the input matrices are global, non-constant variables. This makes most isSafeToMove calls return false because the loads aren’t “DereferenceableInvariantLoads”. This, however, didn’t stop the front-end optimizations from hoisting them! Fun.