[LLVMdev] Strong vs. default phi elimination and single-reg classes

[Hal Finkel]

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