llvm dev - Jun 2012 - [LLVMdev] Strong vs. default phi elimination and single-reg classes

On Thu, 7 Jun 2012 22:14:00 -0700
Jakob Stoklund Olesen <stoklund at 2pi.dk> wrote:
> 
> On Jun 7, 2012, at 7:31 PM, Hal Finkel wrote:
> 
> > 112B    BB#1: derived from LLVM BB %for.body, ADDRESS TAKEN
> >            Predecessors according to CFG: BB#0 BB#1
> > %vreg12<def> = PHI %vreg13, <BB#1>, %vreg11,
> > <BB#0>;CTRRC8:%vreg12,%vreg13,%vreg11 %vreg13<def> = COPY
> > %vreg12<kill>; CTRRC8:%vreg13,%vreg12 %vreg13<def> = BDNZ8
%vreg13,
> > <BB#1>; CTRRC8:%vreg13 B <BB#2>
> >            Successors according to CFG: BB#2 BB#1
> 
> 
> Phi-elim works by inserting copies in the PHI predecessors before the
> first terminator. That isn't possible here since the first terminator
> defines the value of %vreg13 we want to copy. I think that phi-elim
> is not only causing spilling. It is miscompiling the code.
> 
> We simply don't support terminator instructions that define virtual
> registers ATM, it seems.
> 
> I can see how strong phi-elim would work in this case, but I don't
> think it can properly handle this in general. For example:
> 
> 112B    BB#1: derived from LLVM BB %for.body, ADDRESS TAKEN
>            Predecessors according to CFG: BB#0 BB#1
> %vreg12<def> = PHI %vreg13, <BB#1>, %vreg11,
> <BB#0>;CTRRC8:%vreg12,%vreg13,%vreg11 %vreg99<def> = PHI
%vreg13,
> <BB#1>, %vreg2, <BB#0> %vreg13<def> = COPY
%vreg12<kill>;
> CTRRC8:%vreg13,%vreg12 %vreg13<def> = BDNZ8 %vreg13, <BB#1>;
> CTRRC8:%vreg13 B <BB#2>
>            Successors according to CFG: BB#2 BB#1
> 
> Since it is impossible to copy %vreg13 at the end of BB#1, it must be
> merged with %vreg12. The second PHI use means that it must also be
> merged with %vreg99, but that is not possible if %vreg11 and %vreg2
> have different values leaving BB#0.
> 
> Instead of trying to solve this hairy problem, I think you would be
> better off without the CTRRC8 register class.
Thanks for explaining! I can roll-back.
> Your problems with
> {Analyze,Insert,Remove}Branch should be fixable.
I don't think that the problem was with those functions. Adding support
for BDNZ and friends in those functions just enabled other passes to
start moving the blocks around, and that seems to have exposed problems
of its own. For example, sometimes LiveIntervals asserts with:
                register:
%CTR8
clang: /llvm-trunk/lib/CodeGen/LiveIntervalAnalysis.cpp:446:
void llvm::LiveInterval
s::handlePhysicalRegisterDef(llvm::MachineBasicBlock*,
llvm::MachineBasicBlock::iterator, llvm::SlotIndex,
llvm::MachineOperand&, llvm::LiveInt erval&): Assertion
`!isAllocatable(interval.reg) && "Physregs shouldn't be live
out!"'
failed.

in this case the loop is quite simple:
944B    BB#8: derived from LLVM BB %for.inc6, ADDRESS TAKEN
            Live Ins: %CTR8
            Predecessors according to CFG: BB#8 BB#3
960B            BDNZ8 <BB#8>, %CTR8<imp-def>,
%CTR8<imp-use,kill>
            Successors according to CFG: BB#8 BB#10

the preheader is:

240B    BB#3: 
            Predecessors according to CFG: BB#2
256B            %vreg28<def> = LI 0; GPRC:%vreg28
272B            %vreg30<def> = COPY %vreg17<kill>;
GPRC:%vreg30,%vreg17
288B            %vreg31<def> = RLDICL %vreg30<kill>, 0,
32;GPRC:%vreg31,%vreg30
304B            MTCTR8 %vreg31<kill>,%CTR8<imp-def,dead>;
GPRC:%vreg31
320B            B <BB#8>
            Successors according to CFG: BB#8

So maybe LiveInterval would need to be updated to support terminators
that define registers? There are also mis-compiles, but I'm hoping that
they all stem from the same underlying problem.

Thanks again,
Hal
> 
> /jakob

-- 
Hal Finkel
Postdoctoral Appointee
Leadership Computing Facility
Argonne National Laboratory

On Jun 7, 2012, at 10:54 PM, Hal Finkel wrote:
> For example, sometimes LiveIntervals asserts with:
>                register:
> %CTR8
> clang: /llvm-trunk/lib/CodeGen/LiveIntervalAnalysis.cpp:446:
> void llvm::LiveInterval
> s::handlePhysicalRegisterDef(llvm::MachineBasicBlock*,
> llvm::MachineBasicBlock::iterator, llvm::SlotIndex,
> llvm::MachineOperand&, llvm::LiveInt erval&): Assertion
> `!isAllocatable(interval.reg) && "Physregs shouldn't be
live out!"'
> failed.

When machine code is still in SSA form, there are restrictions on what can be
done with physical registers, which by their nature can't be in SSA form.
Lang and I have been trying to come up with some rules, but we haven't found
the right set yet.

So far, we are enforcing:

- Allocatable registers cannot be live across basic blocks, except on entry to
ABI blocks (the entry block and landing pads).

- Unallocatable registers may be live across basic blocks, but you can't use
aliases. (For example, you can't define CTR8 in one block and read CTR in
another).

- Reserved registers can do whatever you want, but defs are treated as having
side effects, blocking certain optimizations like dead code elimination. (You
don't want to DCE a stack pointer update).

In this case, the problem is that CTR and CTR8 are allocatable because CTRRC and
CTRRC8 are allocatable. You can set 'isAllocatable = 0' in those
register classes.

Unfortunately, that breaks your TCRETURNri instructions. Sorry!

Singleton register classes are dangerous because it is so easy to extend the
live range of virtual registers without checking for interference. If you
accidentally cross two live ranges, you get horrible spilling as you've
seen. We try to use explicit unallocatable physreg liveness for singletons like
X86::EFLAGS and ARM::CPSR, but isel and TableGen aren't making it easy.

/jakob

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20120608/2a681331/attachment.html>

On Fri, 8 Jun 2012 08:49:32 -0700
Jakob Stoklund Olesen <stoklund at 2pi.dk> wrote:
> 
> On Jun 7, 2012, at 10:54 PM, Hal Finkel wrote:
> 
> > For example, sometimes LiveIntervals asserts with:
> >                register:
> > %CTR8
> > clang: /llvm-trunk/lib/CodeGen/LiveIntervalAnalysis.cpp:446:
> > void llvm::LiveInterval
> > s::handlePhysicalRegisterDef(llvm::MachineBasicBlock*,
> > llvm::MachineBasicBlock::iterator, llvm::SlotIndex,
> > llvm::MachineOperand&, llvm::LiveInt erval&): Assertion
> > `!isAllocatable(interval.reg) && "Physregs shouldn't
be live out!"'
> > failed.
FYI: I just committed the relevant code (disabled by default); and I
submitted a bug to track this issue:
http://llvm.org/bugs/show_bug.cgi?id=13057
(It seems that I was doing this as you were responding to my e-mail, so
it may be out of date already).
> 
> 
> When machine code is still in SSA form, there are restrictions on
> what can be done with physical registers, which by their nature can't
> be in SSA form. Lang and I have been trying to come up with some
> rules, but we haven't found the right set yet.
> 
> So far, we are enforcing:
> 
> - Allocatable registers cannot be live across basic blocks, except on
> entry to ABI blocks (the entry block and landing pads).
> 
> - Unallocatable registers may be live across basic blocks, but you
> can't use aliases. (For example, you can't define CTR8 in one block
> and read CTR in another).
> 
> - Reserved registers can do whatever you want, but defs are treated
> as having side effects, blocking certain optimizations like dead code
> elimination. (You don't want to DCE a stack pointer update).
> 
> In this case, the problem is that CTR and CTR8 are allocatable
> because CTRRC and CTRRC8 are allocatable. You can set 'isAllocatable
> = 0' in those register classes.
Thanks for explaining! [We should add this to the docs somewhere].
> 
> Unfortunately, that breaks your TCRETURNri instructions. Sorry!
I'm guessing that I can rewrite TCRETURN to reference CTR/CTR8
directly. I'll have to try that.
> 
> Singleton register classes are dangerous because it is so easy to
> extend the live range of virtual registers without checking for
> interference. If you accidentally cross two live ranges, you get
> horrible spilling as you've seen.
Indeed, so it seems ;)
> We try to use explicit
> unallocatable physreg liveness for singletons like X86::EFLAGS and
> ARM::CPSR, but isel and TableGen aren't making it easy.
> 
> /jakob
> 
Thanks again,
Hal

-- 
Hal Finkel
Postdoctoral Appointee
Leadership Computing Facility
Argonne National Laboratory