1 //===- SimplifyCFG.cpp - Code to perform CFG simplification ---------------===//
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 // Peephole optimize the CFG.
12 //===----------------------------------------------------------------------===//
14 #include "llvm/Transforms/Utils/Local.h"
15 #include "llvm/Constants.h"
16 #include "llvm/Instructions.h"
17 #include "llvm/Support/CFG.h"
22 // PropagatePredecessors - This gets "Succ" ready to have the predecessors from
23 // "BB". This is a little tricky because "Succ" has PHI nodes, which need to
24 // have extra slots added to them to hold the merge edges from BB's
25 // predecessors, and BB itself might have had PHI nodes in it. This function
26 // returns true (failure) if the Succ BB already has a predecessor that is a
27 // predecessor of BB and incoming PHI arguments would not be discernible.
29 // Assumption: Succ is the single successor for BB.
31 static bool PropagatePredecessorsForPHIs(BasicBlock *BB, BasicBlock *Succ) {
32 assert(*succ_begin(BB) == Succ && "Succ is not successor of BB!");
34 if (!isa<PHINode>(Succ->front()))
35 return false; // We can make the transformation, no problem.
37 // If there is more than one predecessor, and there are PHI nodes in
38 // the successor, then we need to add incoming edges for the PHI nodes
40 const std::vector<BasicBlock*> BBPreds(pred_begin(BB), pred_end(BB));
42 // Check to see if one of the predecessors of BB is already a predecessor of
43 // Succ. If so, we cannot do the transformation if there are any PHI nodes
44 // with incompatible values coming in from the two edges!
46 for (pred_iterator PI = pred_begin(Succ), PE = pred_end(Succ); PI != PE; ++PI)
47 if (find(BBPreds.begin(), BBPreds.end(), *PI) != BBPreds.end()) {
48 // Loop over all of the PHI nodes checking to see if there are
49 // incompatible values coming in.
50 for (BasicBlock::iterator I = Succ->begin();
51 PHINode *PN = dyn_cast<PHINode>(I); ++I) {
52 // Loop up the entries in the PHI node for BB and for *PI if the values
53 // coming in are non-equal, we cannot merge these two blocks (instead we
54 // should insert a conditional move or something, then merge the
56 int Idx1 = PN->getBasicBlockIndex(BB);
57 int Idx2 = PN->getBasicBlockIndex(*PI);
58 assert(Idx1 != -1 && Idx2 != -1 &&
59 "Didn't have entries for my predecessors??");
60 if (PN->getIncomingValue(Idx1) != PN->getIncomingValue(Idx2))
61 return true; // Values are not equal...
65 // Loop over all of the PHI nodes in the successor BB
66 for (BasicBlock::iterator I = Succ->begin();
67 PHINode *PN = dyn_cast<PHINode>(I); ++I) {
68 Value *OldVal = PN->removeIncomingValue(BB, false);
69 assert(OldVal && "No entry in PHI for Pred BB!");
71 // If this incoming value is one of the PHI nodes in BB...
72 if (isa<PHINode>(OldVal) && cast<PHINode>(OldVal)->getParent() == BB) {
73 PHINode *OldValPN = cast<PHINode>(OldVal);
74 for (std::vector<BasicBlock*>::const_iterator PredI = BBPreds.begin(),
75 End = BBPreds.end(); PredI != End; ++PredI) {
76 PN->addIncoming(OldValPN->getIncomingValueForBlock(*PredI), *PredI);
79 for (std::vector<BasicBlock*>::const_iterator PredI = BBPreds.begin(),
80 End = BBPreds.end(); PredI != End; ++PredI) {
81 // Add an incoming value for each of the new incoming values...
82 PN->addIncoming(OldVal, *PredI);
89 /// GetIfCondition - Given a basic block (BB) with two predecessors (and
90 /// presumably PHI nodes in it), check to see if the merge at this block is due
91 /// to an "if condition". If so, return the boolean condition that determines
92 /// which entry into BB will be taken. Also, return by references the block
93 /// that will be entered from if the condition is true, and the block that will
94 /// be entered if the condition is false.
97 static Value *GetIfCondition(BasicBlock *BB,
98 BasicBlock *&IfTrue, BasicBlock *&IfFalse) {
99 assert(std::distance(pred_begin(BB), pred_end(BB)) == 2 &&
100 "Function can only handle blocks with 2 predecessors!");
101 BasicBlock *Pred1 = *pred_begin(BB);
102 BasicBlock *Pred2 = *++pred_begin(BB);
104 // We can only handle branches. Other control flow will be lowered to
105 // branches if possible anyway.
106 if (!isa<BranchInst>(Pred1->getTerminator()) ||
107 !isa<BranchInst>(Pred2->getTerminator()))
109 BranchInst *Pred1Br = cast<BranchInst>(Pred1->getTerminator());
110 BranchInst *Pred2Br = cast<BranchInst>(Pred2->getTerminator());
112 // Eliminate code duplication by ensuring that Pred1Br is conditional if
114 if (Pred2Br->isConditional()) {
115 // If both branches are conditional, we don't have an "if statement". In
116 // reality, we could transform this case, but since the condition will be
117 // required anyway, we stand no chance of eliminating it, so the xform is
118 // probably not profitable.
119 if (Pred1Br->isConditional())
122 std::swap(Pred1, Pred2);
123 std::swap(Pred1Br, Pred2Br);
126 if (Pred1Br->isConditional()) {
127 // If we found a conditional branch predecessor, make sure that it branches
128 // to BB and Pred2Br. If it doesn't, this isn't an "if statement".
129 if (Pred1Br->getSuccessor(0) == BB &&
130 Pred1Br->getSuccessor(1) == Pred2) {
133 } else if (Pred1Br->getSuccessor(0) == Pred2 &&
134 Pred1Br->getSuccessor(1) == BB) {
138 // We know that one arm of the conditional goes to BB, so the other must
139 // go somewhere unrelated, and this must not be an "if statement".
143 // The only thing we have to watch out for here is to make sure that Pred2
144 // doesn't have incoming edges from other blocks. If it does, the condition
145 // doesn't dominate BB.
146 if (++pred_begin(Pred2) != pred_end(Pred2))
149 return Pred1Br->getCondition();
152 // Ok, if we got here, both predecessors end with an unconditional branch to
153 // BB. Don't panic! If both blocks only have a single (identical)
154 // predecessor, and THAT is a conditional branch, then we're all ok!
155 if (pred_begin(Pred1) == pred_end(Pred1) ||
156 ++pred_begin(Pred1) != pred_end(Pred1) ||
157 pred_begin(Pred2) == pred_end(Pred2) ||
158 ++pred_begin(Pred2) != pred_end(Pred2) ||
159 *pred_begin(Pred1) != *pred_begin(Pred2))
162 // Otherwise, if this is a conditional branch, then we can use it!
163 BasicBlock *CommonPred = *pred_begin(Pred1);
164 if (BranchInst *BI = dyn_cast<BranchInst>(CommonPred->getTerminator())) {
165 assert(BI->isConditional() && "Two successors but not conditional?");
166 if (BI->getSuccessor(0) == Pred1) {
173 return BI->getCondition();
179 // If we have a merge point of an "if condition" as accepted above, return true
180 // if the specified value dominates the block. We don't handle the true
181 // generality of domination here, just a special case which works well enough
183 static bool DominatesMergePoint(Value *V, BasicBlock *BB) {
184 if (Instruction *I = dyn_cast<Instruction>(V)) {
185 BasicBlock *PBB = I->getParent();
186 // If this instruction is defined in a block that contains an unconditional
187 // branch to BB, then it must be in the 'conditional' part of the "if
189 if (isa<BranchInst>(PBB->getTerminator()) &&
190 cast<BranchInst>(PBB->getTerminator())->isUnconditional() &&
191 cast<BranchInst>(PBB->getTerminator())->getSuccessor(0) == BB)
194 // We also don't want to allow wierd loops that might have the "if
195 // condition" in the bottom of this block.
196 if (PBB == BB) return false;
199 // Non-instructions all dominate instructions.
203 // SimplifyCFG - This function is used to do simplification of a CFG. For
204 // example, it adjusts branches to branches to eliminate the extra hop, it
205 // eliminates unreachable basic blocks, and does other "peephole" optimization
206 // of the CFG. It returns true if a modification was made.
208 // WARNING: The entry node of a function may not be simplified.
210 bool llvm::SimplifyCFG(BasicBlock *BB) {
211 bool Changed = false;
212 Function *M = BB->getParent();
214 assert(BB && BB->getParent() && "Block not embedded in function!");
215 assert(BB->getTerminator() && "Degenerate basic block encountered!");
216 assert(&BB->getParent()->front() != BB && "Can't Simplify entry block!");
218 // Check to see if the first instruction in this block is just an unwind. If
219 // so, replace any invoke instructions which use this as an exception
220 // destination with call instructions.
222 if (UnwindInst *UI = dyn_cast<UnwindInst>(BB->getTerminator()))
223 if (BB->begin() == BasicBlock::iterator(UI)) { // Empty block?
224 std::vector<BasicBlock*> Preds(pred_begin(BB), pred_end(BB));
225 while (!Preds.empty()) {
226 BasicBlock *Pred = Preds.back();
227 if (InvokeInst *II = dyn_cast<InvokeInst>(Pred->getTerminator()))
228 if (II->getUnwindDest() == BB) {
229 // Insert a new branch instruction before the invoke, because this
230 // is now a fall through...
231 BranchInst *BI = new BranchInst(II->getNormalDest(), II);
232 Pred->getInstList().remove(II); // Take out of symbol table
234 // Insert the call now...
235 std::vector<Value*> Args(II->op_begin()+3, II->op_end());
236 CallInst *CI = new CallInst(II->getCalledValue(), Args,
238 // If the invoke produced a value, the Call now does instead
239 II->replaceAllUsesWith(CI);
248 // Remove basic blocks that have no predecessors... which are unreachable.
249 if (pred_begin(BB) == pred_end(BB)) {
250 //cerr << "Removing BB: \n" << BB;
252 // Loop through all of our successors and make sure they know that one
253 // of their predecessors is going away.
254 for_each(succ_begin(BB), succ_end(BB),
255 std::bind2nd(std::mem_fun(&BasicBlock::removePredecessor), BB));
257 while (!BB->empty()) {
258 Instruction &I = BB->back();
259 // If this instruction is used, replace uses with an arbitrary
260 // constant value. Because control flow can't get here, we don't care
261 // what we replace the value with. Note that since this block is
262 // unreachable, and all values contained within it must dominate their
263 // uses, that all uses will eventually be removed.
265 // Make all users of this instruction reference the constant instead
266 I.replaceAllUsesWith(Constant::getNullValue(I.getType()));
268 // Remove the instruction from the basic block
269 BB->getInstList().pop_back();
271 M->getBasicBlockList().erase(BB);
275 // Check to see if we can constant propagate this terminator instruction
277 Changed |= ConstantFoldTerminator(BB);
279 // Check to see if this block has no non-phi instructions and only a single
280 // successor. If so, replace references to this basic block with references
282 succ_iterator SI(succ_begin(BB));
283 if (SI != succ_end(BB) && ++SI == succ_end(BB)) { // One succ?
285 BasicBlock::iterator BBI = BB->begin(); // Skip over phi nodes...
286 while (isa<PHINode>(*BBI)) ++BBI;
288 if (BBI->isTerminator()) { // Terminator is the only non-phi instruction!
289 BasicBlock *Succ = *succ_begin(BB); // There is exactly one successor
291 if (Succ != BB) { // Arg, don't hurt infinite loops!
292 // If our successor has PHI nodes, then we need to update them to
293 // include entries for BB's predecessors, not for BB itself.
294 // Be careful though, if this transformation fails (returns true) then
295 // we cannot do this transformation!
297 if (!PropagatePredecessorsForPHIs(BB, Succ)) {
298 //cerr << "Killing Trivial BB: \n" << BB;
299 std::string OldName = BB->getName();
301 std::vector<BasicBlock*>
302 OldSuccPreds(pred_begin(Succ), pred_end(Succ));
304 // Move all PHI nodes in BB to Succ if they are alive, otherwise
306 while (PHINode *PN = dyn_cast<PHINode>(&BB->front()))
308 BB->getInstList().erase(BB->begin()); // Nuke instruction...
310 // The instruction is alive, so this means that Succ must have
311 // *ONLY* had BB as a predecessor, and the PHI node is still valid
312 // now. Simply move it into Succ, because we know that BB
313 // strictly dominated Succ.
314 BB->getInstList().remove(BB->begin());
315 Succ->getInstList().push_front(PN);
317 // We need to add new entries for the PHI node to account for
318 // predecessors of Succ that the PHI node does not take into
319 // account. At this point, since we know that BB dominated succ,
320 // this means that we should any newly added incoming edges should
321 // use the PHI node as the value for these edges, because they are
324 for (unsigned i = 0, e = OldSuccPreds.size(); i != e; ++i)
325 if (OldSuccPreds[i] != BB)
326 PN->addIncoming(PN, OldSuccPreds[i]);
329 // Everything that jumped to BB now goes to Succ...
330 BB->replaceAllUsesWith(Succ);
332 // Delete the old basic block...
333 M->getBasicBlockList().erase(BB);
335 if (!OldName.empty() && !Succ->hasName()) // Transfer name if we can
336 Succ->setName(OldName);
338 //cerr << "Function after removal: \n" << M;
345 // Merge basic blocks into their predecessor if there is only one distinct
346 // pred, and if there is only one distinct successor of the predecessor, and
347 // if there are no PHI nodes.
349 pred_iterator PI(pred_begin(BB)), PE(pred_end(BB));
350 BasicBlock *OnlyPred = *PI++;
351 for (; PI != PE; ++PI) // Search all predecessors, see if they are all same
352 if (*PI != OnlyPred) {
353 OnlyPred = 0; // There are multiple different predecessors...
357 BasicBlock *OnlySucc = 0;
358 if (OnlyPred && OnlyPred != BB && // Don't break self loops
359 OnlyPred->getTerminator()->getOpcode() != Instruction::Invoke) {
360 // Check to see if there is only one distinct successor...
361 succ_iterator SI(succ_begin(OnlyPred)), SE(succ_end(OnlyPred));
363 for (; SI != SE; ++SI)
364 if (*SI != OnlySucc) {
365 OnlySucc = 0; // There are multiple distinct successors!
371 //cerr << "Merging: " << BB << "into: " << OnlyPred;
372 TerminatorInst *Term = OnlyPred->getTerminator();
374 // Resolve any PHI nodes at the start of the block. They are all
375 // guaranteed to have exactly one entry if they exist, unless there are
376 // multiple duplicate (but guaranteed to be equal) entries for the
377 // incoming edges. This occurs when there are multiple edges from
378 // OnlyPred to OnlySucc.
380 while (PHINode *PN = dyn_cast<PHINode>(&BB->front())) {
381 PN->replaceAllUsesWith(PN->getIncomingValue(0));
382 BB->getInstList().pop_front(); // Delete the phi node...
385 // Delete the unconditional branch from the predecessor...
386 OnlyPred->getInstList().pop_back();
388 // Move all definitions in the successor to the predecessor...
389 OnlyPred->getInstList().splice(OnlyPred->end(), BB->getInstList());
391 // Make all PHI nodes that referred to BB now refer to Pred as their
393 BB->replaceAllUsesWith(OnlyPred);
395 std::string OldName = BB->getName();
397 // Erase basic block from the function...
398 M->getBasicBlockList().erase(BB);
400 // Inherit predecessors name if it exists...
401 if (!OldName.empty() && !OnlyPred->hasName())
402 OnlyPred->setName(OldName);
407 // If there is a trivial two-entry PHI node in this basic block, and we can
408 // eliminate it, do so now.
409 if (PHINode *PN = dyn_cast<PHINode>(BB->begin()))
410 if (PN->getNumIncomingValues() == 2) {
411 // Ok, this is a two entry PHI node. Check to see if this is a simple "if
412 // statement", which has a very simple dominance structure. Basically, we
413 // are trying to find the condition that is being branched on, which
414 // subsequently causes this merge to happen. We really want control
415 // dependence information for this check, but simplifycfg can't keep it up
416 // to date, and this catches most of the cases we care about anyway.
418 BasicBlock *IfTrue, *IfFalse;
419 if (Value *IfCond = GetIfCondition(BB, IfTrue, IfFalse)) {
420 //std::cerr << "FOUND IF CONDITION! " << *IfCond << " T: "
421 // << IfTrue->getName() << " F: " << IfFalse->getName() << "\n";
423 // Figure out where to insert instructions as necessary.
424 BasicBlock::iterator AfterPHIIt = BB->begin();
425 while (isa<PHINode>(AfterPHIIt)) ++AfterPHIIt;
427 BasicBlock::iterator I = BB->begin();
428 while (PHINode *PN = dyn_cast<PHINode>(I)) {
431 // If we can eliminate this PHI by directly computing it based on the
432 // condition, do so now. We can't eliminate PHI nodes where the
433 // incoming values are defined in the conditional parts of the branch,
434 // so check for this.
436 if (DominatesMergePoint(PN->getIncomingValue(0), BB) &&
437 DominatesMergePoint(PN->getIncomingValue(1), BB)) {
439 PN->getIncomingValue(PN->getIncomingBlock(0) == IfFalse);
441 PN->getIncomingValue(PN->getIncomingBlock(0) == IfTrue);
443 // FIXME: when we have a 'select' statement, we can be completely
444 // generic and clean here and let the instcombine pass clean up
445 // after us, by folding the select instructions away when possible.
447 if (TrueVal == FalseVal) {
448 // Degenerate case...
449 PN->replaceAllUsesWith(TrueVal);
450 BB->getInstList().erase(PN);
452 } else if (isa<ConstantBool>(TrueVal) &&
453 isa<ConstantBool>(FalseVal)) {
454 if (TrueVal == ConstantBool::True) {
455 // The PHI node produces the same thing as the condition.
456 PN->replaceAllUsesWith(IfCond);
458 // The PHI node produces the inverse of the condition. Insert a
459 // "NOT" instruction, which is really a XOR.
461 BinaryOperator::createNot(IfCond, IfCond->getName()+".inv",
463 PN->replaceAllUsesWith(InverseCond);
465 BB->getInstList().erase(PN);
467 } else if (isa<ConstantInt>(TrueVal) && isa<ConstantInt>(FalseVal)){
468 // If this is a PHI of two constant integers, we insert a cast of
469 // the boolean to the integer type in question, giving us 0 or 1.
470 // Then we multiply this by the difference of the two constants,
471 // giving us 0 if false, and the difference if true. We add this
472 // result to the base constant, giving us our final value. We
473 // rely on the instruction combiner to eliminate many special
474 // cases, like turning multiplies into shifts when possible.
475 std::string Name = PN->getName(); PN->setName("");
476 Value *TheCast = new CastInst(IfCond, TrueVal->getType(),
478 Constant *TheDiff = ConstantExpr::get(Instruction::Sub,
479 cast<Constant>(TrueVal),
480 cast<Constant>(FalseVal));
482 if (TheDiff != ConstantInt::get(TrueVal->getType(), 1))
483 V = BinaryOperator::create(Instruction::Mul, TheCast,
484 TheDiff, TheCast->getName()+".scale",
486 if (!cast<Constant>(FalseVal)->isNullValue())
487 V = BinaryOperator::create(Instruction::Add, V, FalseVal,
488 V->getName()+".offs", AfterPHIIt);
489 PN->replaceAllUsesWith(V);
490 BB->getInstList().erase(PN);
492 } else if (isa<ConstantInt>(FalseVal) &&
493 cast<Constant>(FalseVal)->isNullValue()) {
494 // If the false condition is an integral zero value, we can
495 // compute the PHI by multiplying the condition by the other
497 std::string Name = PN->getName(); PN->setName("");
498 Value *TheCast = new CastInst(IfCond, TrueVal->getType(),
499 Name+".c", AfterPHIIt);
500 Value *V = BinaryOperator::create(Instruction::Mul, TrueVal,
501 TheCast, Name, AfterPHIIt);
502 PN->replaceAllUsesWith(V);
503 BB->getInstList().erase(PN);
505 } else if (isa<ConstantInt>(TrueVal) &&
506 cast<Constant>(TrueVal)->isNullValue()) {
507 // If the true condition is an integral zero value, we can compute
508 // the PHI by multiplying the inverse condition by the other
510 std::string Name = PN->getName(); PN->setName("");
511 Value *NotCond = BinaryOperator::createNot(IfCond, Name+".inv",
513 Value *TheCast = new CastInst(NotCond, TrueVal->getType(),
514 Name+".inv", AfterPHIIt);
515 Value *V = BinaryOperator::create(Instruction::Mul, FalseVal,
516 TheCast, Name, AfterPHIIt);
517 PN->replaceAllUsesWith(V);
518 BB->getInstList().erase(PN);