1 //===-- CondPropagate.cpp - Propagate Conditional Expressions -------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This pass propagates information about conditional expressions through the
11 // program, allowing it to eliminate conditional branches in some cases.
13 //===----------------------------------------------------------------------===//
15 #define DEBUG_TYPE "condprop"
16 #include "llvm/Transforms/Scalar.h"
17 #include "llvm/Instructions.h"
18 #include "llvm/IntrinsicInst.h"
19 #include "llvm/Pass.h"
20 #include "llvm/Type.h"
21 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
22 #include "llvm/Transforms/Utils/Local.h"
23 #include "llvm/ADT/Statistic.h"
24 #include "llvm/ADT/SmallVector.h"
27 STATISTIC(NumBrThread
, "Number of CFG edges threaded through branches");
28 STATISTIC(NumSwThread
, "Number of CFG edges threaded through switches");
31 struct CondProp
: public FunctionPass
{
32 static char ID
; // Pass identification, replacement for typeid
33 CondProp() : FunctionPass(&ID
) {}
35 virtual bool runOnFunction(Function
&F
);
37 virtual void getAnalysisUsage(AnalysisUsage
&AU
) const {
38 AU
.addRequiredID(BreakCriticalEdgesID
);
39 //AU.addRequired<DominanceFrontier>();
44 SmallVector
<BasicBlock
*, 4> DeadBlocks
;
45 void SimplifyBlock(BasicBlock
*BB
);
46 void SimplifyPredecessors(BranchInst
*BI
);
47 void SimplifyPredecessors(SwitchInst
*SI
);
48 void RevectorBlockTo(BasicBlock
*FromBB
, BasicBlock
*ToBB
);
49 bool RevectorBlockTo(BasicBlock
*FromBB
, Value
*Cond
, BranchInst
*BI
);
53 char CondProp::ID
= 0;
54 static RegisterPass
<CondProp
> X("condprop", "Conditional Propagation");
56 FunctionPass
*llvm::createCondPropagationPass() {
57 return new CondProp();
60 bool CondProp::runOnFunction(Function
&F
) {
61 bool EverMadeChange
= false;
64 // While we are simplifying blocks, keep iterating.
67 for (Function::iterator BB
= F
.begin(), E
= F
.end(); BB
!= E
;)
69 EverMadeChange
= EverMadeChange
|| MadeChange
;
73 while (!DeadBlocks
.empty()) {
74 BasicBlock
*BB
= DeadBlocks
.back(); DeadBlocks
.pop_back();
78 return EverMadeChange
;
81 void CondProp::SimplifyBlock(BasicBlock
*BB
) {
82 if (BranchInst
*BI
= dyn_cast
<BranchInst
>(BB
->getTerminator())) {
83 // If this is a conditional branch based on a phi node that is defined in
84 // this block, see if we can simplify predecessors of this block.
85 if (BI
->isConditional() && isa
<PHINode
>(BI
->getCondition()) &&
86 cast
<PHINode
>(BI
->getCondition())->getParent() == BB
)
87 SimplifyPredecessors(BI
);
89 } else if (SwitchInst
*SI
= dyn_cast
<SwitchInst
>(BB
->getTerminator())) {
90 if (isa
<PHINode
>(SI
->getCondition()) &&
91 cast
<PHINode
>(SI
->getCondition())->getParent() == BB
)
92 SimplifyPredecessors(SI
);
95 // If possible, simplify the terminator of this block.
96 if (ConstantFoldTerminator(BB
))
99 // If this block ends with an unconditional branch and the only successor has
100 // only this block as a predecessor, merge the two blocks together.
101 if (BranchInst
*BI
= dyn_cast
<BranchInst
>(BB
->getTerminator()))
102 if (BI
->isUnconditional() && BI
->getSuccessor(0)->getSinglePredecessor() &&
103 BB
!= BI
->getSuccessor(0)) {
104 BasicBlock
*Succ
= BI
->getSuccessor(0);
106 // If Succ has any PHI nodes, they are all single-entry PHI's. Eliminate
108 FoldSingleEntryPHINodes(Succ
);
111 BI
->eraseFromParent();
113 // Move over all of the instructions.
114 BB
->getInstList().splice(BB
->end(), Succ
->getInstList());
116 // Any phi nodes that had entries for Succ now have entries from BB.
117 Succ
->replaceAllUsesWith(BB
);
119 // Succ is now dead, but we cannot delete it without potentially
120 // invalidating iterators elsewhere. Just insert an unreachable
121 // instruction in it and delete this block later on.
122 new UnreachableInst(BB
->getContext(), Succ
);
123 DeadBlocks
.push_back(Succ
);
128 // SimplifyPredecessors(branches) - We know that BI is a conditional branch
129 // based on a PHI node defined in this block. If the phi node contains constant
130 // operands, then the blocks corresponding to those operands can be modified to
131 // jump directly to the destination instead of going through this block.
132 void CondProp::SimplifyPredecessors(BranchInst
*BI
) {
133 // TODO: We currently only handle the most trival case, where the PHI node has
134 // one use (the branch), and is the only instruction besides the branch and dbg
135 // intrinsics in the block.
136 PHINode
*PN
= cast
<PHINode
>(BI
->getCondition());
138 if (PN
->getNumIncomingValues() == 1) {
139 // Eliminate single-entry PHI nodes.
140 FoldSingleEntryPHINodes(PN
->getParent());
145 if (!PN
->hasOneUse()) return;
147 BasicBlock
*BB
= BI
->getParent();
148 if (&*BB
->begin() != PN
)
150 BasicBlock::iterator BBI
= BB
->begin();
151 BasicBlock::iterator BBE
= BB
->end();
152 while (BBI
!= BBE
&& isa
<DbgInfoIntrinsic
>(++BBI
)) /* empty */;
156 // Ok, we have this really simple case, walk the PHI operands, looking for
157 // constants. Walk from the end to remove operands from the end when
158 // possible, and to avoid invalidating "i".
159 for (unsigned i
= PN
->getNumIncomingValues(); i
!= 0; --i
) {
160 Value
*InVal
= PN
->getIncomingValue(i
-1);
161 if (!RevectorBlockTo(PN
->getIncomingBlock(i
-1), InVal
, BI
))
166 // If there were two predecessors before this simplification, or if the
167 // PHI node contained all the same value except for the one we just
168 // substituted, the PHI node may be deleted. Don't iterate through it the
170 if (BI
->getCondition() != PN
) return;
174 // SimplifyPredecessors(switch) - We know that SI is switch based on a PHI node
175 // defined in this block. If the phi node contains constant operands, then the
176 // blocks corresponding to those operands can be modified to jump directly to
177 // the destination instead of going through this block.
178 void CondProp::SimplifyPredecessors(SwitchInst
*SI
) {
179 // TODO: We currently only handle the most trival case, where the PHI node has
180 // one use (the branch), and is the only instruction besides the branch and
181 // dbg intrinsics in the block.
182 PHINode
*PN
= cast
<PHINode
>(SI
->getCondition());
183 if (!PN
->hasOneUse()) return;
185 BasicBlock
*BB
= SI
->getParent();
186 if (&*BB
->begin() != PN
)
188 BasicBlock::iterator BBI
= BB
->begin();
189 BasicBlock::iterator BBE
= BB
->end();
190 while (BBI
!= BBE
&& isa
<DbgInfoIntrinsic
>(++BBI
)) /* empty */;
194 // Ok, we have this really simple case, walk the PHI operands, looking for
195 // constants. Walk from the end to remove operands from the end when
196 // possible, and to avoid invalidating "i".
197 for (unsigned i
= PN
->getNumIncomingValues(); i
!= 0; --i
)
198 if (ConstantInt
*CI
= dyn_cast
<ConstantInt
>(PN
->getIncomingValue(i
-1))) {
199 // If we have a constant, forward the edge from its current to its
200 // ultimate destination.
201 unsigned DestCase
= SI
->findCaseValue(CI
);
202 RevectorBlockTo(PN
->getIncomingBlock(i
-1),
203 SI
->getSuccessor(DestCase
));
206 // If there were two predecessors before this simplification, or if the
207 // PHI node contained all the same value except for the one we just
208 // substituted, the PHI node may be deleted. Don't iterate through it the
210 if (SI
->getCondition() != PN
) return;
215 // RevectorBlockTo - Revector the unconditional branch at the end of FromBB to
216 // the ToBB block, which is one of the successors of its current successor.
217 void CondProp::RevectorBlockTo(BasicBlock
*FromBB
, BasicBlock
*ToBB
) {
218 BranchInst
*FromBr
= cast
<BranchInst
>(FromBB
->getTerminator());
219 assert(FromBr
->isUnconditional() && "FromBB should end with uncond br!");
221 // Get the old block we are threading through.
222 BasicBlock
*OldSucc
= FromBr
->getSuccessor(0);
224 // OldSucc had multiple successors. If ToBB has multiple predecessors, then
225 // the edge between them would be critical, which we already took care of.
226 // If ToBB has single operand PHI node then take care of it here.
227 FoldSingleEntryPHINodes(ToBB
);
229 // Update PHI nodes in OldSucc to know that FromBB no longer branches to it.
230 OldSucc
->removePredecessor(FromBB
);
232 // Change FromBr to branch to the new destination.
233 FromBr
->setSuccessor(0, ToBB
);
238 bool CondProp::RevectorBlockTo(BasicBlock
*FromBB
, Value
*Cond
, BranchInst
*BI
){
239 BranchInst
*FromBr
= cast
<BranchInst
>(FromBB
->getTerminator());
240 if (!FromBr
->isUnconditional())
243 // Get the old block we are threading through.
244 BasicBlock
*OldSucc
= FromBr
->getSuccessor(0);
246 // If the condition is a constant, simply revector the unconditional branch at
247 // the end of FromBB to one of the successors of its current successor.
248 if (ConstantInt
*CB
= dyn_cast
<ConstantInt
>(Cond
)) {
249 BasicBlock
*ToBB
= BI
->getSuccessor(CB
->isZero());
251 // OldSucc had multiple successors. If ToBB has multiple predecessors, then
252 // the edge between them would be critical, which we already took care of.
253 // If ToBB has single operand PHI node then take care of it here.
254 FoldSingleEntryPHINodes(ToBB
);
256 // Update PHI nodes in OldSucc to know that FromBB no longer branches to it.
257 OldSucc
->removePredecessor(FromBB
);
259 // Change FromBr to branch to the new destination.
260 FromBr
->setSuccessor(0, ToBB
);
262 BasicBlock
*Succ0
= BI
->getSuccessor(0);
263 // Do not perform transform if the new destination has PHI nodes. The
264 // transform will add new preds to the PHI's.
265 if (isa
<PHINode
>(Succ0
->begin()))
268 BasicBlock
*Succ1
= BI
->getSuccessor(1);
269 if (isa
<PHINode
>(Succ1
->begin()))
272 // Insert the new conditional branch.
273 BranchInst::Create(Succ0
, Succ1
, Cond
, FromBr
);
275 FoldSingleEntryPHINodes(Succ0
);
276 FoldSingleEntryPHINodes(Succ1
);
278 // Update PHI nodes in OldSucc to know that FromBB no longer branches to it.
279 OldSucc
->removePredecessor(FromBB
);
281 // Delete the old branch.
282 FromBr
->eraseFromParent();