[llvm-dev] [EXTERNAL] Marking a particular virtual register (or live interval) as unspillable

Fri Jul 9 12:53:34 PDT 2021

Thanks again for helping enlighten me for a portion of the backend I’ve yet to completely grok. I’ll see about running a pass to modify the LiveIntervals before allocation. I see other targets doing this by inserting a pass just after the TwoAddress pass in either its own addFast/OptimizedRegalloc or as part of addPreRegAlloc.

As for how we’re modeling the delay slots, I feel the decision was made due to a number of complicating factors. To that end, I believe that bundling the two instructions together would be insufficient, since the spill will still occur, and will just move from in between the branch to after the occurs. In addition, our target already utilizes bundles to represent VLIW ILP, so there would be some inconsistencies in representation. However, this is all certainly problems on our end, and not something with which to continue pestering the list, so I’ll leave it there (until we’re looking to upstream of course 😊 ).

Regards,
JB

From: Quentin Colombet <qcolombet at apple.com>
Sent: Friday, July 9, 2021 2:26 PM
To: Nagurne, James <j-nagurne at ti.com>
Cc: llvm-dev at lists.llvm.org
Subject: Re: [EXTERNAL] [llvm-dev] Marking a particular virtual register (or live interval) as unspillable

Hi James,

On Jul 9, 2021, at 11:51 AM, Nagurne, James <j-nagurne at ti.com<mailto:j-nagurne at ti.com>> wrote:

Thanks for the response, Quentin.

I'm aware of markNotSpillable, but it looks like the only use of that function is for the aforementioned unspillable terminators and for very particular live ranges in ‘generic’ code. Are you suggesting that there’s a way to modify the LiveIntervals analysis before the allocator/spiller uses them?
Yes, you can run your own machine pass and set this “flag” yourself. Just make sure you do it in the middle of where LiveIntervals are set and preserved (e.g., right before the register coalescer.)

I was under the assumption that the LiveInterval information was calculated immediately preceding the allocator, and that the target couldn’t easily influence that.

No, you can actually modify the LiveIntervals essentially between right before register coalescer and right after register allocation (i.e., that includes before and after the scheduler).

“From what you’re describing, it feels to me that the bug is in the block placement since it’s moving the store above the intended definition and that marking the LI not spillable is just a workaround.”

It’s not so much moving the store as it is removing the terminators and then replacing them at the end of the block, which is where terminators are required to exist. It just so happens that the initiate has a gap which contains a dependent instruction that gets re-ordered on the call to insertBranch.

For background: the pair of instructions models branch delay slots, a branch and its associated discontinuity which occurs on a different cycle. By separating the branch instruction and the actual discontinuity into separate instructions, it becomes possible to use an instruction scheduler to fill the delay slots, rather than using a separate pre-emit pass that Lanai, Mips, and Sparc uses.

With that said, I believe block placement is certainly doing something that should be 'ok' with regards to the IR semantics. Specifically, the pass uses the target’s removeBranch and insertBranch implementations, which should be guaranteed not to affect the execution behavior of a block. Our target has a further requirement that no instruction can exist between the initiate and the actual discontinuity for insertBranch to ensure that the program has not changed. The spill being created breaks that rule, and so removeBranch/insertBranch do not work as desired.

So it looks like the way forward might be:
- Find a way to mark the live interval from the branch register def as unspillable
- Attempt to mimic how Sparc/Lanai/Mips fills delay slots

Mimicking what the other targets are doing is probably your safest bet since it has been extensively tested and thus is supported.
One thing you could try as well is create a bundle with the initiate branch and actual branch so that it is impossible to insert anything between the two instructions. Using bundles may be tricky though.

Cheers,
-Quentin

Regards,
JB

________________________________
From: Quentin Colombet <qcolombet at apple.com<mailto:qcolombet at apple.com>>
Sent: Thursday, July 8, 2021 7:48 PM
To: Nagurne, James
Cc: llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>
Subject: [EXTERNAL] Re: [llvm-dev] Marking a particular virtual register (or live interval) as unspillable

Hi James,

If you want to make a particular live-interval unspillable, you can use LiveInterval::markNotSpillable.
Please be aware that this may not cover all your use cases:
- An unspillable live-interval can still be split (i.e., moved around), but all the newly created intervals would spill be unspillable.
- The unspillable information is lost if you have a pass that doesn’t preserve the LiveIntervals analysis and thus this analysis has to rerun.

Now, I am not entirely sure I understand the problem.

From what you’re describing, it feels to me that the bug is in the block placement since it’s moving the store above the intended definition and that marking the LI not spillable is just a workaround.

The thing I am not sure though is are you allowed to have instructions between the initiate and the branch?

If you do not, then it sounds to me that you could mark the initiate as a terminator as well. I don’t guarantee that doing that would solve the problem out of the box, but if it doesn’t we should just fix whatever introduce the issue because in theory, we are not allowed to insert code after the first terminator.

Cheers,
-Quentin

On Jul 8, 2021, at 3:48 PM, Nagurne, James via llvm-dev <llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>> wrote:

Hi all, I have a question regarding spills that I’ve been unable to find a satisfactory answer for in my perusal of the source.

I have a downstream target which contains an instruction that defines a register and is very closely associated with a terminator, but is not itself a terminator. Specifically, the first instruction is effectively ‘initiate the branch’, and the actual terminator is ‘branch occurs’.

The expectation is that the ‘initiate the branch’ instruction occurs as the last non-terminator instruction if it’s present at all due to the aforementioned association with terminators.

MBB:
                $r0 = Branch $r0 (tied def 0)
                Occurs
               ; $r0 is live-out of MBB

However, spilling is occurring, causing a store to appear between the initiation and the branch occurs.

MBB:
                $r0 = Branch $r0 (tied def 0)
                Store $r0 to memory
                Occurs

When block placement occurs, the branches are removed from the block and then re-inserted. This affects the branch and the occurs, but not the store, leading to a change in execution behavior:

MBB:
                Store $r0 to memory
                $r0 = Branch $r0 (tied def 0)
                Occurs

One potential solution I believed would have worked is to combine the branch and its occurs into a single terminator, but this causes the three-address instruction pass to insert a COPY just after the combined instruction for the tied def, leading to a similar problem where a non-terminator occurs after a terminator.

I found the concept of an ‘unspillable terminator’ added in commit 0447f350 for ARM, but the problematic instruction isn’t a terminator. I had thought to generalize the concept to consider a virtual register unspillable regardless of being a terminator or not, but ran into issues in the verifier that made me reconsider (The value is live across the backedge of the loop as well out live-out of the loop, which runs across an expectation that unspillable terminators have 1 use). I thought that controlling spilling seemed like an important concept for a target to have some level of control over, but could not find anything in the spill or LiveInterval code that seemed to allow a target to mark a register/interval as unspillable.

I’m hoping I’ve just missed something and someone knows enough to point me in the right direction.

Thanks,
J.B. Nagurne
Code Generation
Texas Instruments

_______________________________________________
LLVM Developers mailing list
llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20210709/86e462f9/attachment.html>