1 //===- SimplifyCFG.cpp - Code to perform CFG simplification ---------------===//
3 // Peephole optimize the CFG.
5 //===----------------------------------------------------------------------===//
7 #include "llvm/Transforms/Utils/Local.h"
8 #include "llvm/Constant.h"
9 #include "llvm/iPHINode.h"
10 #include "llvm/Support/CFG.h"
14 // PropagatePredecessors - This gets "Succ" ready to have the predecessors from
15 // "BB". This is a little tricky because "Succ" has PHI nodes, which need to
16 // have extra slots added to them to hold the merge edges from BB's
17 // predecessors, and BB itself might have had PHI nodes in it. This function
18 // returns true (failure) if the Succ BB already has a predecessor that is a
19 // predecessor of BB and incoming PHI arguments would not be discernable.
21 // Assumption: Succ is the single successor for BB.
23 static bool PropagatePredecessorsForPHIs(BasicBlock *BB, BasicBlock *Succ) {
24 assert(*succ_begin(BB) == Succ && "Succ is not successor of BB!");
26 if (!isa<PHINode>(Succ->front()))
27 return false; // We can make the transformation, no problem.
29 // If there is more than one predecessor, and there are PHI nodes in
30 // the successor, then we need to add incoming edges for the PHI nodes
32 const std::vector<BasicBlock*> BBPreds(pred_begin(BB), pred_end(BB));
34 // Check to see if one of the predecessors of BB is already a predecessor of
35 // Succ. If so, we cannot do the transformation if there are any PHI nodes
36 // with incompatible values coming in from the two edges!
38 for (pred_iterator PI = pred_begin(Succ), PE = pred_end(Succ); PI != PE; ++PI)
39 if (find(BBPreds.begin(), BBPreds.end(), *PI) != BBPreds.end()) {
40 // Loop over all of the PHI nodes checking to see if there are
41 // incompatible values coming in.
42 for (BasicBlock::iterator I = Succ->begin();
43 PHINode *PN = dyn_cast<PHINode>(I); ++I) {
44 // Loop up the entries in the PHI node for BB and for *PI if the values
45 // coming in are non-equal, we cannot merge these two blocks (instead we
46 // should insert a conditional move or something, then merge the
48 int Idx1 = PN->getBasicBlockIndex(BB);
49 int Idx2 = PN->getBasicBlockIndex(*PI);
50 assert(Idx1 != -1 && Idx2 != -1 &&
51 "Didn't have entries for my predecessors??");
52 if (PN->getIncomingValue(Idx1) != PN->getIncomingValue(Idx2))
53 return true; // Values are not equal...
57 // Loop over all of the PHI nodes in the successor BB
58 for (BasicBlock::iterator I = Succ->begin();
59 PHINode *PN = dyn_cast<PHINode>(I); ++I) {
60 Value *OldVal = PN->removeIncomingValue(BB, false);
61 assert(OldVal && "No entry in PHI for Pred BB!");
63 // If this incoming value is one of the PHI nodes in BB...
64 if (isa<PHINode>(OldVal) && cast<PHINode>(OldVal)->getParent() == BB) {
65 PHINode *OldValPN = cast<PHINode>(OldVal);
66 for (std::vector<BasicBlock*>::const_iterator PredI = BBPreds.begin(),
67 End = BBPreds.end(); PredI != End; ++PredI) {
68 PN->addIncoming(OldValPN->getIncomingValueForBlock(*PredI), *PredI);
71 for (std::vector<BasicBlock*>::const_iterator PredI = BBPreds.begin(),
72 End = BBPreds.end(); PredI != End; ++PredI) {
73 // Add an incoming value for each of the new incoming values...
74 PN->addIncoming(OldVal, *PredI);
82 // SimplifyCFG - This function is used to do simplification of a CFG. For
83 // example, it adjusts branches to branches to eliminate the extra hop, it
84 // eliminates unreachable basic blocks, and does other "peephole" optimization
85 // of the CFG. It returns true if a modification was made.
87 // WARNING: The entry node of a function may not be simplified.
89 bool SimplifyCFG(BasicBlock *BB) {
90 Function *M = BB->getParent();
92 assert(BB && BB->getParent() && "Block not embedded in function!");
93 assert(BB->getTerminator() && "Degenerate basic block encountered!");
94 assert(&BB->getParent()->front() != BB && "Can't Simplify entry block!");
96 // Remove basic blocks that have no predecessors... which are unreachable.
97 if (pred_begin(BB) == pred_end(BB) &&
98 !BB->hasConstantReferences()) {
99 //cerr << "Removing BB: \n" << BB;
101 // Loop through all of our successors and make sure they know that one
102 // of their predecessors is going away.
103 for_each(succ_begin(BB), succ_end(BB),
104 std::bind2nd(std::mem_fun(&BasicBlock::removePredecessor), BB));
106 while (!BB->empty()) {
107 Instruction &I = BB->back();
108 // If this instruction is used, replace uses with an arbitrary
109 // constant value. Because control flow can't get here, we don't care
110 // what we replace the value with. Note that since this block is
111 // unreachable, and all values contained within it must dominate their
112 // uses, that all uses will eventually be removed.
114 // Make all users of this instruction reference the constant instead
115 I.replaceAllUsesWith(Constant::getNullValue(I.getType()));
117 // Remove the instruction from the basic block
118 BB->getInstList().pop_back();
120 M->getBasicBlockList().erase(BB);
124 // Check to see if we can constant propagate this terminator instruction
126 bool Changed = ConstantFoldTerminator(BB);
128 // Check to see if this block has no non-phi instructions and only a single
129 // successor. If so, replace references to this basic block with references
131 succ_iterator SI(succ_begin(BB));
132 if (SI != succ_end(BB) && ++SI == succ_end(BB)) { // One succ?
134 BasicBlock::iterator BBI = BB->begin(); // Skip over phi nodes...
135 while (isa<PHINode>(*BBI)) ++BBI;
137 if (BBI->isTerminator()) { // Terminator is the only non-phi instruction!
138 BasicBlock *Succ = *succ_begin(BB); // There is exactly one successor
140 if (Succ != BB) { // Arg, don't hurt infinite loops!
141 // If our successor has PHI nodes, then we need to update them to
142 // include entries for BB's predecessors, not for BB itself.
143 // Be careful though, if this transformation fails (returns true) then
144 // we cannot do this transformation!
146 if (!PropagatePredecessorsForPHIs(BB, Succ)) {
147 //cerr << "Killing Trivial BB: \n" << BB;
148 std::string OldName = BB->getName();
150 std::vector<BasicBlock*>
151 OldSuccPreds(pred_begin(Succ), pred_end(Succ));
153 // Move all PHI nodes in BB to Succ if they are alive, otherwise
155 while (PHINode *PN = dyn_cast<PHINode>(&BB->front()))
157 BB->getInstList().erase(BB->begin()); // Nuke instruction...
159 // The instruction is alive, so this means that Succ must have
160 // *ONLY* had BB as a predecessor, and the PHI node is still valid
161 // now. Simply move it into Succ, because we know that BB
162 // strictly dominated Succ.
163 BB->getInstList().remove(BB->begin());
164 Succ->getInstList().push_front(PN);
166 // We need to add new entries for the PHI node to account for
167 // predecessors of Succ that the PHI node does not take into
168 // account. At this point, since we know that BB dominated succ,
169 // this means that we should any newly added incoming edges should
170 // use the PHI node as the value for these edges, because they are
173 for (unsigned i = 0, e = OldSuccPreds.size(); i != e; ++i)
174 if (OldSuccPreds[i] != BB)
175 PN->addIncoming(PN, OldSuccPreds[i]);
178 // Everything that jumped to BB now goes to Succ...
179 BB->replaceAllUsesWith(Succ);
181 // Delete the old basic block...
182 M->getBasicBlockList().erase(BB);
184 if (!OldName.empty() && !Succ->hasName()) // Transfer name if we can
185 Succ->setName(OldName);
187 //cerr << "Function after removal: \n" << M;
194 // Merge basic blocks into their predecessor if there is only one distinct
195 // pred, and if there is only one distinct successor of the predecessor, and
196 // if there are no PHI nodes.
198 if (!BB->hasConstantReferences()) {
199 pred_iterator PI(pred_begin(BB)), PE(pred_end(BB));
200 BasicBlock *OnlyPred = *PI++;
201 for (; PI != PE; ++PI) // Search all predecessors, see if they are all same
202 if (*PI != OnlyPred) {
203 OnlyPred = 0; // There are multiple different predecessors...
207 BasicBlock *OnlySucc = 0;
208 if (OnlyPred && OnlyPred != BB && // Don't break self loops
209 OnlyPred->getTerminator()->getOpcode() != Instruction::Invoke) {
210 // Check to see if there is only one distinct successor...
211 succ_iterator SI(succ_begin(OnlyPred)), SE(succ_end(OnlyPred));
213 for (; SI != SE; ++SI)
214 if (*SI != OnlySucc) {
215 OnlySucc = 0; // There are multiple distinct successors!
221 //cerr << "Merging: " << BB << "into: " << OnlyPred;
222 TerminatorInst *Term = OnlyPred->getTerminator();
224 // Resolve any PHI nodes at the start of the block. They are all
225 // guaranteed to have exactly one entry if they exist, unless there are
226 // multiple duplicate (but guaranteed to be equal) entries for the
227 // incoming edges. This occurs when there are multiple edges from
228 // OnlyPred to OnlySucc.
230 while (PHINode *PN = dyn_cast<PHINode>(&BB->front())) {
231 PN->replaceAllUsesWith(PN->getIncomingValue(0));
232 BB->getInstList().pop_front(); // Delete the phi node...
235 // Delete the unconditional branch from the predecessor...
236 OnlyPred->getInstList().pop_back();
238 // Move all definitions in the succecessor to the predecessor...
239 OnlyPred->getInstList().splice(OnlyPred->end(), BB->getInstList());
241 // Make all PHI nodes that refered to BB now refer to Pred as their
243 BB->replaceAllUsesWith(OnlyPred);
245 std::string OldName = BB->getName();
247 // Erase basic block from the function...
248 M->getBasicBlockList().erase(BB);
250 // Inherit predecessors name if it exists...
251 if (!OldName.empty() && !OnlyPred->hasName())
252 OnlyPred->setName(OldName);