llvm dev - May 2011 - [LLVMdev] LiveVariables not updated in MachineBasicBlock::SplitCriticalEdge?

Is LiveVariables updated correctly when TII->RemoveBranch and
TII->InsertBranch are called in the following piece of code?

- MachineBasicBlock::updateTerminator() line 307 of MachineBasicBlock.cpp:
  if (FBB) {
      // The block has a non-fallthrough conditional branch. If one of its
      // successors is its layout successor, rewrite it to a fallthrough
      // conditional branch.
      if (isLayoutSuccessor(TBB)) {
        if (TII->ReverseBranchCondition(Cond))
          return;
        TII->RemoveBranch(*this);
        TII->InsertBranch(*this, FBB, 0, Cond, dl);
      } else if (isLayoutSuccessor(FBB)) {

I am investigating an assertion (shown below) that is fired when I run llc
with -march=mipsel -mcpu=4ke. It seems to me that the root cause of this
assertion is the piece of code shown above that is called during PHI nodes
elimination (llc exits normally if I add -disable-phi-elim-edge-splitting).

llc: llvm/lib/CodeGen/SplitKit.cpp:170: bool
llvm::SplitAnalysis::calcLiveBlockInfo(): Assertion `BI.FirstUse >=
Start'
failed.


The following is the Machine IR and LiveVariables::ValInfo dump before and
after PHI nodes elimination.

1. Before PHI nodes elimination.
-Machine IR:
BB#14: derived from LLVM BB %for.cond151.preheader
    Predecessors according to CFG: BB#12 BB#13
    %vreg29<def> = PHI %vreg25, <BB#12>, %vreg28, <BB#13>;
CPURegs:%vreg29,%vreg25,%vreg28
    %vreg30<def> = PHI %vreg26, <BB#12>, %vreg27, <BB#13>;
CPURegs:%vreg30,%vreg26,%vreg27
    BNE %vreg81<kill>, %ZERO, <BB#17>; CPURegs:%vreg81
    J <BB#15>
    Successors according to CFG: BB#15 BB#17

BB#15: derived from LLVM BB %for.body156.preheader
    Predecessors according to CFG: BB#14

BB#17: derived from LLVM BB %for.end241
    Predecessors according to CFG: BB#14 BB#16

-vreg81's VarInfo:
  Alive in blocks: 5, 6, 7, 8, 10, 12, 13, 19,
  Killed by:
    #0: BNE %vreg81<kill>, %ZERO, <BB#17>; CPURegs:%vreg81

2. During PHI nodes elimination, critical edge BB#14-#17 is split and BB#20
is inserted. The two terminators of BB#14 (BNE and J ) are replaced with a
conditional branch (BEQ) when MachineBasicBlock::updateTerminator() is
called.

3. After PHI nodes elimination.
- Machine IR:
BB#14: derived from LLVM BB %for.cond151.preheader
    Predecessors according to CFG: BB#13 BB#19
    %vreg29<def> = COPY %vreg180<kill>; CPURegs:%vreg29,%vreg180
    %vreg30<def> = COPY %vreg181<kill>; CPURegs:%vreg30,%vreg181
    BEQ %vreg81, %ZERO, <BB#15>; CPURegs:%vreg81
    Successors according to CFG: BB#15 BB#20

BB#20:
    Predecessors according to CFG: BB#14
    %vreg187<def> = COPY %vreg14<kill>; CPURegs:%vreg187,%vreg14
    %vreg188<def> = COPY %vreg29<kill>; CPURegs:%vreg188,%vreg29
    J <BB#17>
    Successors according to CFG: BB#17

BB#15: derived from LLVM BB %for.body156.preheader
    Predecessors according to CFG: BB#14

BB#17: derived from LLVM BB %for.end241
    Predecessors according to CFG: BB#16 BB#20

- vreg81's VarInfo:
  Alive in blocks: 5, 6, 7, 8, 10, 12, 13, 19,
  Killed by:
    #0: J <BB#17>


As you can see, VarInfo vreg81 is killed by the unconditional jump
instruction of BB#20 when it should be killed by the newly created
conditional branch in BB#14 (BEQ). Is this a bug in updateTerminator() or is
the back-end responsible for updating LiveVariables?
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20110502/b7e0853f/attachment.html>

On May 2, 2011, at 3:51 PM, Akira Hatanaka wrote:
> - vreg81's VarInfo:
>   Alive in blocks: 5, 6, 7, 8, 10, 12, 13, 19, 
>   Killed by:
>     #0: J <BB#17>
> 
> 
> As you can see, VarInfo vreg81 is killed by the unconditional jump
instruction of BB#20 when it should be killed by the newly created conditional
branch in BB#14 (BEQ). Is this a bug in updateTerminator() or is the back-end
responsible for updating LiveVariables?
This could be a new issue. Neither ARM nor x86 have conditional branches that
take live register operands, so I don't think anyone has considered if the
back-end should update LiveVariables. It simply hasn't come up before.

I think the target should call LV->replaceKillInstruction() when this
happens.

/jakob

Does updateTerminator() need to be rewritten in order to implement the
changes you suggested (call LV->replaceKillInstruction)? Or can it be taken
care of just by adding code to the files in Target/Mips?

Also, is the generated code still correct if
-disable-phi-elim-edge-splitting is added to the command line options?

On Mon, May 2, 2011 at 5:00 PM, Jakob Stoklund Olesen <stoklund at
2pi.dk>wrote:
>
> On May 2, 2011, at 3:51 PM, Akira Hatanaka wrote:
>
> > - vreg81's VarInfo:
> >   Alive in blocks: 5, 6, 7, 8, 10, 12, 13, 19,
> >   Killed by:
> >     #0: J <BB#17>
> >
> >
> > As you can see, VarInfo vreg81 is killed by the unconditional jump
> instruction of BB#20 when it should be killed by the newly created
> conditional branch in BB#14 (BEQ). Is this a bug in updateTerminator() or
is
> the back-end responsible for updating LiveVariables?
>
> This could be a new issue. Neither ARM nor x86 have conditional branches
> that take live register operands, so I don't think anyone has
considered if
> the back-end should update LiveVariables. It simply hasn't come up
before.
>
> I think the target should call LV->replaceKillInstruction() when this
> happens.
>
> /jakob
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20110502/6a1ae5ab/attachment.html>