1 //===-- CondPropagate.cpp - Propagate Conditional Expressions -------------===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by the LLVM research group and is distributed under
6 // the University of Illinois Open Source 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/Transforms/Utils/Local.h"
18 #include "llvm/Constants.h"
19 #include "llvm/Function.h"
20 #include "llvm/Instructions.h"
21 #include "llvm/Pass.h"
22 #include "llvm/Type.h"
23 #include "llvm/ADT/STLExtras.h"
24 #include "llvm/ADT/Statistic.h"
30 NumBrThread("condprop", "Number of CFG edges threaded through branches");
32 NumSwThread("condprop", "Number of CFG edges threaded through switches");
34 struct CondProp : public FunctionPass {
35 virtual bool runOnFunction(Function &F);
37 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
38 AU.addRequiredID(BreakCriticalEdgesID);
39 //AU.addRequired<DominanceFrontier>();
44 void SimplifyBlock(BasicBlock *BB);
45 void SimplifyPredecessors(BranchInst *BI);
46 void SimplifyPredecessors(SwitchInst *SI);
47 void RevectorBlockTo(BasicBlock *FromBB, BasicBlock *ToBB);
49 RegisterOpt<CondProp> X("condprop", "Conditional Propagation");
52 FunctionPass *llvm::createCondPropagationPass() {
53 return new CondProp();
56 bool CondProp::runOnFunction(Function &F) {
57 bool EverMadeChange = false;
59 // While we are simplifying blocks, keep iterating.
62 for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
64 EverMadeChange = MadeChange;
66 return EverMadeChange;
69 void CondProp::SimplifyBlock(BasicBlock *BB) {
70 if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator())) {
71 // If this is a conditional branch based on a phi node that is defined in
72 // this block, see if we can simplify predecessors of this block.
73 if (BI->isConditional() && isa<PHINode>(BI->getCondition()) &&
74 cast<PHINode>(BI->getCondition())->getParent() == BB)
75 SimplifyPredecessors(BI);
77 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(BB->getTerminator())) {
78 if (isa<PHINode>(SI->getCondition()) &&
79 cast<PHINode>(SI->getCondition())->getParent() == BB)
80 SimplifyPredecessors(SI);
83 // See if we can fold any PHI nodes in this block now.
84 // FIXME: This would not be required if removePredecessor did this for us!!
86 for (BasicBlock::iterator I = BB->begin(); (PN = dyn_cast<PHINode>(I++)); )
87 if (Value *PNV = hasConstantValue(PN))
88 if (!isa<Instruction>(PNV)) {
89 PN->replaceAllUsesWith(PNV);
90 PN->eraseFromParent();
94 // If possible, simplify the terminator of this block.
95 if (ConstantFoldTerminator(BB))
98 // If this block ends with an unconditional branch and the only successor has
99 // only this block as a predecessor, merge the two blocks together.
100 if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator()))
101 if (BI->isUnconditional() && BI->getSuccessor(0)->getSinglePredecessor()) {
102 BasicBlock *Succ = BI->getSuccessor(0);
104 BI->eraseFromParent();
106 // Move over all of the instructions.
107 BB->getInstList().splice(BB->end(), Succ->getInstList());
109 // Any phi nodes that had entries for Succ now have entries from BB.
110 Succ->replaceAllUsesWith(BB);
112 // Succ is now dead, but we cannot delete it without potentially
113 // invalidating iterators elsewhere. Just insert an unreachable
114 // instruction in it.
115 new UnreachableInst(Succ);
120 // SimplifyPredecessors(branches) - We know that BI is a conditional branch
121 // based on a PHI node defined in this block. If the phi node contains constant
122 // operands, then the blocks corresponding to those operands can be modified to
123 // jump directly to the destination instead of going through this block.
124 void CondProp::SimplifyPredecessors(BranchInst *BI) {
125 // TODO: We currently only handle the most trival case, where the PHI node has
126 // one use (the branch), and is the only instruction besides the branch in the
128 PHINode *PN = cast<PHINode>(BI->getCondition());
129 if (!PN->hasOneUse()) return;
131 BasicBlock *BB = BI->getParent();
132 if (&*BB->begin() != PN || &*next(BB->begin()) != BI)
135 // Ok, we have this really simple case, walk the PHI operands, looking for
136 // constants. Walk from the end to remove operands from the end when
137 // possible, and to avoid invalidating "i".
138 for (unsigned i = PN->getNumIncomingValues(); i != 0; --i)
139 if (ConstantBool *CB = dyn_cast<ConstantBool>(PN->getIncomingValue(i-1))) {
140 // If we have a constant, forward the edge from its current to its
141 // ultimate destination.
142 bool PHIGone = PN->getNumIncomingValues() == 2;
143 RevectorBlockTo(PN->getIncomingBlock(i-1),
144 BI->getSuccessor(CB->getValue() == 0));
147 // If there were two predecessors before this simplification, the PHI node
148 // will be deleted. Don't iterate through it the last time.
153 // SimplifyPredecessors(switch) - We know that SI is switch based on a PHI node
154 // defined in this block. If the phi node contains constant operands, then the
155 // blocks corresponding to those operands can be modified to jump directly to
156 // the destination instead of going through this block.
157 void CondProp::SimplifyPredecessors(SwitchInst *SI) {
158 // TODO: We currently only handle the most trival case, where the PHI node has
159 // one use (the branch), and is the only instruction besides the branch in the
161 PHINode *PN = cast<PHINode>(SI->getCondition());
162 if (!PN->hasOneUse()) return;
164 BasicBlock *BB = SI->getParent();
165 if (&*BB->begin() != PN || &*next(BB->begin()) != SI)
168 bool RemovedPreds = false;
170 // Ok, we have this really simple case, walk the PHI operands, looking for
171 // constants. Walk from the end to remove operands from the end when
172 // possible, and to avoid invalidating "i".
173 for (unsigned i = PN->getNumIncomingValues(); i != 0; --i)
174 if (ConstantInt *CI = dyn_cast<ConstantInt>(PN->getIncomingValue(i-1))) {
175 // If we have a constant, forward the edge from its current to its
176 // ultimate destination.
177 bool PHIGone = PN->getNumIncomingValues() == 2;
178 unsigned DestCase = SI->findCaseValue(CI);
179 RevectorBlockTo(PN->getIncomingBlock(i-1),
180 SI->getSuccessor(DestCase));
184 // If there were two predecessors before this simplification, the PHI node
185 // will be deleted. Don't iterate through it the last time.
191 // RevectorBlockTo - Revector the unconditional branch at the end of FromBB to
192 // the ToBB block, which is one of the successors of its current successor.
193 void CondProp::RevectorBlockTo(BasicBlock *FromBB, BasicBlock *ToBB) {
194 BranchInst *FromBr = cast<BranchInst>(FromBB->getTerminator());
195 assert(FromBr->isUnconditional() && "FromBB should end with uncond br!");
197 // Get the old block we are threading through.
198 BasicBlock *OldSucc = FromBr->getSuccessor(0);
200 // ToBB should not have any PHI nodes in it to update, because OldSucc had
201 // multiple successors. If OldSucc had multiple successor and ToBB had
202 // multiple predecessors, the edge between them would be critical, which we
203 // already took care of.
204 assert(!isa<PHINode>(ToBB->begin()) && "Critical Edge Found!");
206 // Update PHI nodes in OldSucc to know that FromBB no longer branches to it.
207 OldSucc->removePredecessor(FromBB);
209 // Change FromBr to branch to the new destination.
210 FromBr->setSuccessor(0, ToBB);