If Conversion and predicated returns

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

Should AnalyzeBranch be enhanced to somehow indicate conditional returns?

I don't think that returns can ever be analyzable (since LLVM's CFG does not have a designated exit block).

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?

Both of these cases know what scenario they are dealing with (i.e. whether there is a return instruction in the block or not), so they should be able to handle the edge updates (just like the diamond case). The only special case would be when the CFG edges go to the same block (i.e. there is a conditional branch whose both paths end up in the same place), but I think that if-conversion would give up on that (or that the branch folder would take care of it).

My 2c.

-Krzysztof

From: "Krzysztof Parzyszek" <kparzysz@codeaurora.org>
To: llvmdev@cs.uiuc.edu
Sent: Wednesday, April 10, 2013 1:10:32 PM
Subject: Re: [LLVMdev] If Conversion and predicated returns

>
> Should AnalyzeBranch be enhanced to somehow indicate conditional
> returns?

I don't think that returns can ever be analyzable (since LLVM's CFG
does
not have a designated exit block).

> 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?

Both of these cases know what scenario they are dealing with (i.e.
whether there is a return instruction in the block or not), so they
should be able to handle the edge updates (just like the diamond
case).
  The only special case would be when the CFG edges go to the same
  block
(i.e. there is a conditional branch whose both paths end up in the
same
place), but I think that if-conversion would give up on that (or that
the branch folder would take care of it).

Seemed simply enough. r179227.

Thanks again,
Hal

ARM does predicated returns in ARM and Thumb2 code. Perhaps there’s something there that might help?

-Jim