llvm dev - Jul 2021 - Marking a particular virtual register (or live interval) as unspillable

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

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20210708/15b12631/attachment.html>

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> 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
<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/20210708/30c9f761/attachment.html>