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
On 4/10/2013 12:45 PM, Hal Finkel wrote:> > 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 -- Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, hosted by The Linux Foundation
----- Original Message -----> From: "Krzysztof Parzyszek" <kparzysz at codeaurora.org> > To: llvmdev at cs.uiuc.edu > Sent: Wednesday, April 10, 2013 1:10:32 PM > Subject: Re: [LLVMdev] If Conversion and predicated returns > > On 4/10/2013 12:45 PM, Hal Finkel wrote: > > > > 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> > My 2c. > > -Krzysztof > > > -- > Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, > hosted by The Linux Foundation > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >
ARM does predicated returns in ARM and Thumb2 code. Perhaps there’s something there that might help? -Jim On Apr 10, 2013, at 10:45 AM, Hal Finkel <hfinkel at anl.gov> wrote:> 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 > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20130410/0f4d2fd7/attachment.html>