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"
25 #include "llvm/Support/Compiler.h"
26 #include "llvm/Support/Streams.h"
29 STATISTIC(NumBrThread, "Number of CFG edges threaded through branches");
30 STATISTIC(NumSwThread, "Number of CFG edges threaded through switches");
33 struct VISIBILITY_HIDDEN CondProp : public FunctionPass {
34 virtual bool runOnFunction(Function &F);
36 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
37 AU.addRequiredID(BreakCriticalEdgesID);
38 //AU.addRequired<DominanceFrontier>();
43 void SimplifyBlock(BasicBlock *BB);
44 void SimplifyPredecessors(BranchInst *BI);
45 void SimplifyPredecessors(SwitchInst *SI);
46 void RevectorBlockTo(BasicBlock *FromBB, BasicBlock *ToBB);
48 RegisterPass<CondProp> X("condprop", "Conditional Propagation");
51 FunctionPass *llvm::createCondPropagationPass() {
52 return new CondProp();
55 bool CondProp::runOnFunction(Function &F) {
56 bool EverMadeChange = false;
58 // While we are simplifying blocks, keep iterating.
61 for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
63 EverMadeChange = MadeChange;
65 return EverMadeChange;
68 void CondProp::SimplifyBlock(BasicBlock *BB) {
69 if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator())) {
70 // If this is a conditional branch based on a phi node that is defined in
71 // this block, see if we can simplify predecessors of this block.
72 if (BI->isConditional() && isa<PHINode>(BI->getCondition()) &&
73 cast<PHINode>(BI->getCondition())->getParent() == BB)
74 SimplifyPredecessors(BI);
76 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(BB->getTerminator())) {
77 if (isa<PHINode>(SI->getCondition()) &&
78 cast<PHINode>(SI->getCondition())->getParent() == BB)
79 SimplifyPredecessors(SI);
82 // If possible, simplify the terminator of this block.
83 if (ConstantFoldTerminator(BB))
86 // If this block ends with an unconditional branch and the only successor has
87 // only this block as a predecessor, merge the two blocks together.
88 if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator()))
89 if (BI->isUnconditional() && BI->getSuccessor(0)->getSinglePredecessor() &&
90 BB != BI->getSuccessor(0)) {
91 BasicBlock *Succ = BI->getSuccessor(0);
93 // If Succ has any PHI nodes, they are all single-entry PHI's.
94 while (PHINode *PN = dyn_cast<PHINode>(Succ->begin())) {
95 assert(PN->getNumIncomingValues() == 1 &&
96 "PHI doesn't match parent block");
97 PN->replaceAllUsesWith(PN->getIncomingValue(0));
98 PN->eraseFromParent();
102 BI->eraseFromParent();
104 // Move over all of the instructions.
105 BB->getInstList().splice(BB->end(), Succ->getInstList());
107 // Any phi nodes that had entries for Succ now have entries from BB.
108 Succ->replaceAllUsesWith(BB);
110 // Succ is now dead, but we cannot delete it without potentially
111 // invalidating iterators elsewhere. Just insert an unreachable
112 // instruction in it.
113 new UnreachableInst(Succ);
118 // SimplifyPredecessors(branches) - We know that BI is a conditional branch
119 // based on a PHI node defined in this block. If the phi node contains constant
120 // operands, then the blocks corresponding to those operands can be modified to
121 // jump directly to the destination instead of going through this block.
122 void CondProp::SimplifyPredecessors(BranchInst *BI) {
123 // TODO: We currently only handle the most trival case, where the PHI node has
124 // one use (the branch), and is the only instruction besides the branch in the
126 PHINode *PN = cast<PHINode>(BI->getCondition());
127 if (!PN->hasOneUse()) return;
129 BasicBlock *BB = BI->getParent();
130 if (&*BB->begin() != PN || &*next(BB->begin()) != BI)
133 // Ok, we have this really simple case, walk the PHI operands, looking for
134 // constants. Walk from the end to remove operands from the end when
135 // possible, and to avoid invalidating "i".
136 for (unsigned i = PN->getNumIncomingValues(); i != 0; --i)
137 if (ConstantInt *CB = dyn_cast<ConstantInt>(PN->getIncomingValue(i-1))) {
138 // If we have a constant, forward the edge from its current to its
139 // ultimate destination.
140 bool PHIGone = PN->getNumIncomingValues() == 2;
141 RevectorBlockTo(PN->getIncomingBlock(i-1),
142 BI->getSuccessor(CB->getZExtValue() == 0));
145 // If there were two predecessors before this simplification, the PHI node
146 // will be deleted. Don't iterate through it the last time.
151 // SimplifyPredecessors(switch) - We know that SI is switch based on a PHI node
152 // defined in this block. If the phi node contains constant operands, then the
153 // blocks corresponding to those operands can be modified to jump directly to
154 // the destination instead of going through this block.
155 void CondProp::SimplifyPredecessors(SwitchInst *SI) {
156 // TODO: We currently only handle the most trival case, where the PHI node has
157 // one use (the branch), and is the only instruction besides the branch in the
159 PHINode *PN = cast<PHINode>(SI->getCondition());
160 if (!PN->hasOneUse()) return;
162 BasicBlock *BB = SI->getParent();
163 if (&*BB->begin() != PN || &*next(BB->begin()) != SI)
166 bool RemovedPreds = false;
168 // Ok, we have this really simple case, walk the PHI operands, looking for
169 // constants. Walk from the end to remove operands from the end when
170 // possible, and to avoid invalidating "i".
171 for (unsigned i = PN->getNumIncomingValues(); i != 0; --i)
172 if (ConstantInt *CI = dyn_cast<ConstantInt>(PN->getIncomingValue(i-1))) {
173 // If we have a constant, forward the edge from its current to its
174 // ultimate destination.
175 bool PHIGone = PN->getNumIncomingValues() == 2;
176 unsigned DestCase = SI->findCaseValue(CI);
177 RevectorBlockTo(PN->getIncomingBlock(i-1),
178 SI->getSuccessor(DestCase));
182 // If there were two predecessors before this simplification, the PHI node
183 // will be deleted. Don't iterate through it the last time.
189 // RevectorBlockTo - Revector the unconditional branch at the end of FromBB to
190 // the ToBB block, which is one of the successors of its current successor.
191 void CondProp::RevectorBlockTo(BasicBlock *FromBB, BasicBlock *ToBB) {
192 BranchInst *FromBr = cast<BranchInst>(FromBB->getTerminator());
193 assert(FromBr->isUnconditional() && "FromBB should end with uncond br!");
195 // Get the old block we are threading through.
196 BasicBlock *OldSucc = FromBr->getSuccessor(0);
198 // OldSucc had multiple successors. If ToBB has multiple predecessors, then
199 // the edge between them would be critical, which we already took care of.
200 // If ToBB has single operand PHI node then take care of it here.
201 while (PHINode *PN = dyn_cast<PHINode>(ToBB->begin())) {
202 assert(PN->getNumIncomingValues() == 1 && "Critical Edge Found!");
203 PN->replaceAllUsesWith(PN->getIncomingValue(0));
204 PN->eraseFromParent();
207 // Update PHI nodes in OldSucc to know that FromBB no longer branches to it.
208 OldSucc->removePredecessor(FromBB);
210 // Change FromBr to branch to the new destination.
211 FromBr->setSuccessor(0, ToBB);