[LLVMdev] If Conversion and predicated returns

[Hal Finkel]

Evan, et al.,

I've come across a small issue when using the if conversion pass in PPC to generate conditional returns. Here's a small example:

** Before if conversion **

BB#0: derived from LLVM BB %entry
        %R3<def> = LI 0
        %CR0<def> = CMPLWI %R3, 0
        BCC 68, %CR0, <BB#3>
    Successors according to CFG: BB#3(16) BB#1(16)

BB#1: derived from LLVM BB %while.body.lr.ph
    Live Ins: %R3
    Predecessors according to CFG: BB#0
        %CR0<def> = CMPLWI %R3<kill>, 0
        BCC 68, %CR0, <BB#3>
    Successors according to CFG: BB#3(16) BB#2(16)

BB#2: derived from LLVM BB %while.body
    Predecessors according to CFG: BB#2 BB#1
        B <BB#2>
    Successors according to CFG: BB#2

BB#3: derived from LLVM BB %while.end
    Predecessors according to CFG: BB#0 BB#1
        BLR %LR<imp-use>, %RM<imp-use>

** After if conversion **

BB#0: derived from LLVM BB %entry
        %R3<def> = LI 0
        %CR0<def> = CMPLWI %R3, 0
        BCC 68, %CR0, <BB#3>
    Successors according to CFG: BB#3(16) BB#1(16)

BB#1: derived from LLVM BB %while.body.lr.ph
    Live Ins: %R3
    Predecessors according to CFG: BB#0
        %CR0<def> = CMPLWI %R3<kill>, 0
        BCLR 68, %CR0, %LR<imp-use>, %RM<imp-use>
    Successors according to CFG: BB#3(16) BB#2(16)

BB#2: derived from LLVM BB %while.body
    Predecessors according to CFG: BB#2 BB#1
        B <BB#2>
    Successors according to CFG: BB#2

BB#3: derived from LLVM BB %while.end
    Predecessors according to CFG: BB#0 BB#1
        BLR %LR<imp-use>, %RM<imp-use>

While the resulting code is not incorrect, the CFG is not quite right, and this pessimizes later transformations. Specifically, the issue is that BB#1 still lists BB#3 as a successor, but this is not true. Looking at IfConversion.cpp, I see this function:

/// RemoveExtraEdges - Remove true / false edges if either / both are no longer
/// successors.
void IfConverter::RemoveExtraEdges(BBInfo &BBI) {
  MachineBasicBlock *TBB = NULL, *FBB = NULL;
  SmallVector<MachineOperand, 4> Cond;
  if (!TII->AnalyzeBranch(*BBI.BB, TBB, FBB, Cond))
    BBI.BB->CorrectExtraCFGEdges(TBB, FBB, !Cond.empty());
}

and I think that this function is supposed to clean up the successors of BB#1 after merging. The problem is that the PPC implementation of AnalyzeBranch does not understand returns (conditional or otherwise). I'm not sure what the best way of dealing with this is. Should AnalyzeBranch be enhanced to somehow indicate conditional returns?

Alternatively, the diamond conversion routine contains this:

  // RemoveExtraEdges won't work if the block has an unanalyzable branch,
  // which can happen here if TailBB is unanalyzable and is merged, so
  // explicitly remove BBI1 and BBI2 as successors.
  BBI.BB->removeSuccessor(BBI1->BB);
  BBI.BB->removeSuccessor(BBI2->BB);
  RemoveExtraEdges(BBI);

should something similar be added prior to the calls to RemoveExtraEdges in the simple and triangle conversion routines?

Thanks in advance,
Hal

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