Fix comment for consistency sake.
[llvm/avr.git] / lib / Transforms / Scalar / CondPropagate.cpp
blob09fc050e13cc5d375c1d3e43b1005e828dae560f
1 //===-- CondPropagate.cpp - Propagate Conditional Expressions -------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
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"
25 using namespace llvm;
27 STATISTIC(NumBrThread, "Number of CFG edges threaded through branches");
28 STATISTIC(NumSwThread, "Number of CFG edges threaded through switches");
30 namespace {
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>();
42 private:
43 bool MadeChange;
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;
62 DeadBlocks.clear();
64 // While we are simplifying blocks, keep iterating.
65 do {
66 MadeChange = false;
67 for (Function::iterator BB = F.begin(), E = F.end(); BB != E;)
68 SimplifyBlock(BB++);
69 EverMadeChange = EverMadeChange || MadeChange;
70 } while (MadeChange);
72 if (EverMadeChange) {
73 while (!DeadBlocks.empty()) {
74 BasicBlock *BB = DeadBlocks.back(); DeadBlocks.pop_back();
75 DeleteDeadBlock(BB);
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))
97 MadeChange = true;
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
107 // them.
108 FoldSingleEntryPHINodes(Succ);
110 // Remove BI.
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);
124 MadeChange = true;
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());
141 return;
145 if (!PN->hasOneUse()) return;
147 BasicBlock *BB = BI->getParent();
148 if (&*BB->begin() != PN)
149 return;
150 BasicBlock::iterator BBI = BB->begin();
151 BasicBlock::iterator BBE = BB->end();
152 while (BBI != BBE && isa<DbgInfoIntrinsic>(++BBI)) /* empty */;
153 if (&*BBI != BI)
154 return;
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))
162 continue;
164 ++NumBrThread;
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
169 // last time.
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)
187 return;
188 BasicBlock::iterator BBI = BB->begin();
189 BasicBlock::iterator BBE = BB->end();
190 while (BBI != BBE && isa<DbgInfoIntrinsic>(++BBI)) /* empty */;
191 if (&*BBI != SI)
192 return;
194 bool RemovedPreds = false;
196 // Ok, we have this really simple case, walk the PHI operands, looking for
197 // constants. Walk from the end to remove operands from the end when
198 // possible, and to avoid invalidating "i".
199 for (unsigned i = PN->getNumIncomingValues(); i != 0; --i)
200 if (ConstantInt *CI = dyn_cast<ConstantInt>(PN->getIncomingValue(i-1))) {
201 // If we have a constant, forward the edge from its current to its
202 // ultimate destination.
203 unsigned DestCase = SI->findCaseValue(CI);
204 RevectorBlockTo(PN->getIncomingBlock(i-1),
205 SI->getSuccessor(DestCase));
206 ++NumSwThread;
207 RemovedPreds = true;
209 // If there were two predecessors before this simplification, or if the
210 // PHI node contained all the same value except for the one we just
211 // substituted, the PHI node may be deleted. Don't iterate through it the
212 // last time.
213 if (SI->getCondition() != PN) return;
218 // RevectorBlockTo - Revector the unconditional branch at the end of FromBB to
219 // the ToBB block, which is one of the successors of its current successor.
220 void CondProp::RevectorBlockTo(BasicBlock *FromBB, BasicBlock *ToBB) {
221 BranchInst *FromBr = cast<BranchInst>(FromBB->getTerminator());
222 assert(FromBr->isUnconditional() && "FromBB should end with uncond br!");
224 // Get the old block we are threading through.
225 BasicBlock *OldSucc = FromBr->getSuccessor(0);
227 // OldSucc had multiple successors. If ToBB has multiple predecessors, then
228 // the edge between them would be critical, which we already took care of.
229 // If ToBB has single operand PHI node then take care of it here.
230 FoldSingleEntryPHINodes(ToBB);
232 // Update PHI nodes in OldSucc to know that FromBB no longer branches to it.
233 OldSucc->removePredecessor(FromBB);
235 // Change FromBr to branch to the new destination.
236 FromBr->setSuccessor(0, ToBB);
238 MadeChange = true;
241 bool CondProp::RevectorBlockTo(BasicBlock *FromBB, Value *Cond, BranchInst *BI){
242 BranchInst *FromBr = cast<BranchInst>(FromBB->getTerminator());
243 if (!FromBr->isUnconditional())
244 return false;
246 // Get the old block we are threading through.
247 BasicBlock *OldSucc = FromBr->getSuccessor(0);
249 // If the condition is a constant, simply revector the unconditional branch at
250 // the end of FromBB to one of the successors of its current successor.
251 if (ConstantInt *CB = dyn_cast<ConstantInt>(Cond)) {
252 BasicBlock *ToBB = BI->getSuccessor(CB->isZero());
254 // OldSucc had multiple successors. If ToBB has multiple predecessors, then
255 // the edge between them would be critical, which we already took care of.
256 // If ToBB has single operand PHI node then take care of it here.
257 FoldSingleEntryPHINodes(ToBB);
259 // Update PHI nodes in OldSucc to know that FromBB no longer branches to it.
260 OldSucc->removePredecessor(FromBB);
262 // Change FromBr to branch to the new destination.
263 FromBr->setSuccessor(0, ToBB);
264 } else {
265 BasicBlock *Succ0 = BI->getSuccessor(0);
266 // Do not perform transform if the new destination has PHI nodes. The
267 // transform will add new preds to the PHI's.
268 if (isa<PHINode>(Succ0->begin()))
269 return false;
271 BasicBlock *Succ1 = BI->getSuccessor(1);
272 if (isa<PHINode>(Succ1->begin()))
273 return false;
275 // Insert the new conditional branch.
276 BranchInst::Create(Succ0, Succ1, Cond, FromBr);
278 FoldSingleEntryPHINodes(Succ0);
279 FoldSingleEntryPHINodes(Succ1);
281 // Update PHI nodes in OldSucc to know that FromBB no longer branches to it.
282 OldSucc->removePredecessor(FromBB);
284 // Delete the old branch.
285 FromBr->eraseFromParent();
288 MadeChange = true;
289 return true;