Chris Lattner | 01d1ee3 | 2002-05-21 20:50:24 +0000 | [diff] [blame] | 1 | //===- SimplifyCFG.cpp - Code to perform CFG simplification ---------------===// |
| 2 | // |
Chris Lattner | bb190ac | 2002-10-08 21:36:33 +0000 | [diff] [blame] | 3 | // Peephole optimize the CFG. |
Chris Lattner | 01d1ee3 | 2002-05-21 20:50:24 +0000 | [diff] [blame] | 4 | // |
| 5 | //===----------------------------------------------------------------------===// |
| 6 | |
| 7 | #include "llvm/Transforms/Utils/Local.h" |
| 8 | #include "llvm/Constant.h" |
| 9 | #include "llvm/iPHINode.h" |
| 10 | #include "llvm/Support/CFG.h" |
| 11 | #include <algorithm> |
| 12 | #include <functional> |
| 13 | |
Misha Brukman | a3bbcb5 | 2002-10-29 23:06:16 +0000 | [diff] [blame] | 14 | // PropagatePredecessors - This gets "Succ" ready to have the predecessors from |
Chris Lattner | 01d1ee3 | 2002-05-21 20:50:24 +0000 | [diff] [blame] | 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 |
Chris Lattner | e2ca540 | 2003-03-05 21:01:52 +0000 | [diff] [blame] | 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. |
Chris Lattner | 01d1ee3 | 2002-05-21 20:50:24 +0000 | [diff] [blame] | 20 | // |
| 21 | // Assumption: Succ is the single successor for BB. |
| 22 | // |
Misha Brukman | a3bbcb5 | 2002-10-29 23:06:16 +0000 | [diff] [blame] | 23 | static bool PropagatePredecessorsForPHIs(BasicBlock *BB, BasicBlock *Succ) { |
Chris Lattner | 01d1ee3 | 2002-05-21 20:50:24 +0000 | [diff] [blame] | 24 | assert(*succ_begin(BB) == Succ && "Succ is not successor of BB!"); |
Chris Lattner | 3abb95d | 2002-09-24 00:09:26 +0000 | [diff] [blame] | 25 | |
| 26 | if (!isa<PHINode>(Succ->front())) |
| 27 | return false; // We can make the transformation, no problem. |
Chris Lattner | 01d1ee3 | 2002-05-21 20:50:24 +0000 | [diff] [blame] | 28 | |
| 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 |
| 31 | // |
| 32 | const std::vector<BasicBlock*> BBPreds(pred_begin(BB), pred_end(BB)); |
| 33 | |
| 34 | // Check to see if one of the predecessors of BB is already a predecessor of |
Chris Lattner | e2ca540 | 2003-03-05 21:01:52 +0000 | [diff] [blame] | 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! |
Chris Lattner | 01d1ee3 | 2002-05-21 20:50:24 +0000 | [diff] [blame] | 37 | // |
Chris Lattner | e2ca540 | 2003-03-05 21:01:52 +0000 | [diff] [blame] | 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. |
Chris Lattner | 46a5f1f | 2003-03-05 21:36:33 +0000 | [diff] [blame^] | 42 | for (BasicBlock::iterator I = Succ->begin(); |
| 43 | PHINode *PN = dyn_cast<PHINode>(&*I); ++I) { |
Chris Lattner | e2ca540 | 2003-03-05 21:01:52 +0000 | [diff] [blame] | 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 |
| 47 | // blocks). |
| 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... |
| 54 | } |
| 55 | } |
Chris Lattner | 01d1ee3 | 2002-05-21 20:50:24 +0000 | [diff] [blame] | 56 | |
| 57 | // Loop over all of the PHI nodes in the successor BB |
| 58 | for (BasicBlock::iterator I = Succ->begin(); |
Chris Lattner | 1896150 | 2002-06-25 16:12:52 +0000 | [diff] [blame] | 59 | PHINode *PN = dyn_cast<PHINode>(&*I); ++I) { |
Chris Lattner | bb190ac | 2002-10-08 21:36:33 +0000 | [diff] [blame] | 60 | Value *OldVal = PN->removeIncomingValue(BB, false); |
Chris Lattner | 01d1ee3 | 2002-05-21 20:50:24 +0000 | [diff] [blame] | 61 | assert(OldVal && "No entry in PHI for Pred BB!"); |
| 62 | |
Chris Lattner | 46a5f1f | 2003-03-05 21:36:33 +0000 | [diff] [blame^] | 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); |
| 69 | } |
| 70 | } else { |
| 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); |
| 75 | } |
Chris Lattner | 01d1ee3 | 2002-05-21 20:50:24 +0000 | [diff] [blame] | 76 | } |
| 77 | } |
| 78 | return false; |
| 79 | } |
| 80 | |
| 81 | |
| 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 |
Chris Lattner | e2ca540 | 2003-03-05 21:01:52 +0000 | [diff] [blame] | 85 | // of the CFG. It returns true if a modification was made. |
Chris Lattner | 01d1ee3 | 2002-05-21 20:50:24 +0000 | [diff] [blame] | 86 | // |
| 87 | // WARNING: The entry node of a function may not be simplified. |
| 88 | // |
Chris Lattner | 1896150 | 2002-06-25 16:12:52 +0000 | [diff] [blame] | 89 | bool SimplifyCFG(BasicBlock *BB) { |
Chris Lattner | 01d1ee3 | 2002-05-21 20:50:24 +0000 | [diff] [blame] | 90 | Function *M = BB->getParent(); |
| 91 | |
| 92 | assert(BB && BB->getParent() && "Block not embedded in function!"); |
| 93 | assert(BB->getTerminator() && "Degenerate basic block encountered!"); |
Chris Lattner | 1896150 | 2002-06-25 16:12:52 +0000 | [diff] [blame] | 94 | assert(&BB->getParent()->front() != BB && "Can't Simplify entry block!"); |
Chris Lattner | 01d1ee3 | 2002-05-21 20:50:24 +0000 | [diff] [blame] | 95 | |
Chris Lattner | 01d1ee3 | 2002-05-21 20:50:24 +0000 | [diff] [blame] | 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; |
| 100 | |
| 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)); |
| 105 | |
| 106 | while (!BB->empty()) { |
Chris Lattner | 1896150 | 2002-06-25 16:12:52 +0000 | [diff] [blame] | 107 | Instruction &I = BB->back(); |
Chris Lattner | 01d1ee3 | 2002-05-21 20:50:24 +0000 | [diff] [blame] | 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. |
Chris Lattner | 1896150 | 2002-06-25 16:12:52 +0000 | [diff] [blame] | 113 | if (!I.use_empty()) |
Chris Lattner | 01d1ee3 | 2002-05-21 20:50:24 +0000 | [diff] [blame] | 114 | // Make all users of this instruction reference the constant instead |
Chris Lattner | 1896150 | 2002-06-25 16:12:52 +0000 | [diff] [blame] | 115 | I.replaceAllUsesWith(Constant::getNullValue(I.getType())); |
Chris Lattner | 01d1ee3 | 2002-05-21 20:50:24 +0000 | [diff] [blame] | 116 | |
| 117 | // Remove the instruction from the basic block |
Chris Lattner | 1896150 | 2002-06-25 16:12:52 +0000 | [diff] [blame] | 118 | BB->getInstList().pop_back(); |
Chris Lattner | 01d1ee3 | 2002-05-21 20:50:24 +0000 | [diff] [blame] | 119 | } |
Chris Lattner | 1896150 | 2002-06-25 16:12:52 +0000 | [diff] [blame] | 120 | M->getBasicBlockList().erase(BB); |
Chris Lattner | 01d1ee3 | 2002-05-21 20:50:24 +0000 | [diff] [blame] | 121 | return true; |
| 122 | } |
| 123 | |
Chris Lattner | 46a5f1f | 2003-03-05 21:36:33 +0000 | [diff] [blame^] | 124 | // Check to see if this block has no non-phi instructions and only a single |
| 125 | // successor. If so, replace references to this basic block with references |
| 126 | // to the successor. |
Chris Lattner | 01d1ee3 | 2002-05-21 20:50:24 +0000 | [diff] [blame] | 127 | succ_iterator SI(succ_begin(BB)); |
| 128 | if (SI != succ_end(BB) && ++SI == succ_end(BB)) { // One succ? |
Chris Lattner | 46a5f1f | 2003-03-05 21:36:33 +0000 | [diff] [blame^] | 129 | |
| 130 | BasicBlock::iterator BBI = BB->begin(); // Skip over phi nodes... |
| 131 | while (isa<PHINode>(*BBI)) ++BBI; |
| 132 | |
| 133 | if (BBI->isTerminator()) { // Terminator is the only non-phi instruction! |
Chris Lattner | 01d1ee3 | 2002-05-21 20:50:24 +0000 | [diff] [blame] | 134 | BasicBlock *Succ = *succ_begin(BB); // There is exactly one successor |
| 135 | |
| 136 | if (Succ != BB) { // Arg, don't hurt infinite loops! |
| 137 | // If our successor has PHI nodes, then we need to update them to |
| 138 | // include entries for BB's predecessors, not for BB itself. |
| 139 | // Be careful though, if this transformation fails (returns true) then |
| 140 | // we cannot do this transformation! |
| 141 | // |
Misha Brukman | a3bbcb5 | 2002-10-29 23:06:16 +0000 | [diff] [blame] | 142 | if (!PropagatePredecessorsForPHIs(BB, Succ)) { |
Chris Lattner | 01d1ee3 | 2002-05-21 20:50:24 +0000 | [diff] [blame] | 143 | //cerr << "Killing Trivial BB: \n" << BB; |
Chris Lattner | 01d1ee3 | 2002-05-21 20:50:24 +0000 | [diff] [blame] | 144 | BB->replaceAllUsesWith(Succ); |
Chris Lattner | 1896150 | 2002-06-25 16:12:52 +0000 | [diff] [blame] | 145 | std::string OldName = BB->getName(); |
| 146 | |
Chris Lattner | 46a5f1f | 2003-03-05 21:36:33 +0000 | [diff] [blame^] | 147 | // Move all PHI nodes in BB to Succ if they are alive, otherwise |
| 148 | // delete them. |
| 149 | while (PHINode *PN = dyn_cast<PHINode>(&BB->front())) |
| 150 | if (PN->use_empty()) |
| 151 | BB->getInstList().erase(BB->begin()); // Nuke instruction... |
| 152 | else { |
| 153 | // The instruction is alive, so this means that Succ must have |
| 154 | // *ONLY* had BB as a predecessor, and the PHI node is still valid |
| 155 | // now. Simply move it into Succ. |
| 156 | BB->getInstList().remove(BB->begin()); |
| 157 | Succ->getInstList().push_front(PN); |
| 158 | } |
| 159 | |
Chris Lattner | 1896150 | 2002-06-25 16:12:52 +0000 | [diff] [blame] | 160 | // Delete the old basic block... |
| 161 | M->getBasicBlockList().erase(BB); |
Chris Lattner | 01d1ee3 | 2002-05-21 20:50:24 +0000 | [diff] [blame] | 162 | |
Chris Lattner | 1896150 | 2002-06-25 16:12:52 +0000 | [diff] [blame] | 163 | if (!OldName.empty() && !Succ->hasName()) // Transfer name if we can |
| 164 | Succ->setName(OldName); |
Chris Lattner | 01d1ee3 | 2002-05-21 20:50:24 +0000 | [diff] [blame] | 165 | |
| 166 | //cerr << "Function after removal: \n" << M; |
| 167 | return true; |
| 168 | } |
| 169 | } |
| 170 | } |
| 171 | } |
| 172 | |
| 173 | // Merge basic blocks into their predecessor if there is only one distinct |
| 174 | // pred, and if there is only one distinct successor of the predecessor, and |
| 175 | // if there are no PHI nodes. |
| 176 | // |
Chris Lattner | 91b65c0 | 2002-07-29 21:26:30 +0000 | [diff] [blame] | 177 | if (!BB->hasConstantReferences()) { |
Chris Lattner | 01d1ee3 | 2002-05-21 20:50:24 +0000 | [diff] [blame] | 178 | pred_iterator PI(pred_begin(BB)), PE(pred_end(BB)); |
| 179 | BasicBlock *OnlyPred = *PI++; |
| 180 | for (; PI != PE; ++PI) // Search all predecessors, see if they are all same |
| 181 | if (*PI != OnlyPred) { |
| 182 | OnlyPred = 0; // There are multiple different predecessors... |
| 183 | break; |
| 184 | } |
| 185 | |
| 186 | BasicBlock *OnlySucc = 0; |
| 187 | if (OnlyPred && OnlyPred != BB) { // Don't break self loops |
| 188 | // Check to see if there is only one distinct successor... |
| 189 | succ_iterator SI(succ_begin(OnlyPred)), SE(succ_end(OnlyPred)); |
| 190 | OnlySucc = BB; |
| 191 | for (; SI != SE; ++SI) |
| 192 | if (*SI != OnlySucc) { |
| 193 | OnlySucc = 0; // There are multiple distinct successors! |
| 194 | break; |
| 195 | } |
| 196 | } |
| 197 | |
| 198 | if (OnlySucc) { |
| 199 | //cerr << "Merging: " << BB << "into: " << OnlyPred; |
| 200 | TerminatorInst *Term = OnlyPred->getTerminator(); |
| 201 | |
Chris Lattner | 91b65c0 | 2002-07-29 21:26:30 +0000 | [diff] [blame] | 202 | // Resolve any PHI nodes at the start of the block. They are all |
Chris Lattner | 929b2c6 | 2002-09-24 16:09:17 +0000 | [diff] [blame] | 203 | // guaranteed to have exactly one entry if they exist, unless there are |
| 204 | // multiple duplicate (but guaranteed to be equal) entries for the |
| 205 | // incoming edges. This occurs when there are multiple edges from |
| 206 | // OnlyPred to OnlySucc. |
Chris Lattner | 91b65c0 | 2002-07-29 21:26:30 +0000 | [diff] [blame] | 207 | // |
| 208 | while (PHINode *PN = dyn_cast<PHINode>(&BB->front())) { |
Chris Lattner | 91b65c0 | 2002-07-29 21:26:30 +0000 | [diff] [blame] | 209 | PN->replaceAllUsesWith(PN->getIncomingValue(0)); |
| 210 | BB->getInstList().pop_front(); // Delete the phi node... |
| 211 | } |
| 212 | |
Chris Lattner | 01d1ee3 | 2002-05-21 20:50:24 +0000 | [diff] [blame] | 213 | // Delete the unconditional branch from the predecessor... |
Chris Lattner | 1896150 | 2002-06-25 16:12:52 +0000 | [diff] [blame] | 214 | OnlyPred->getInstList().pop_back(); |
Chris Lattner | 01d1ee3 | 2002-05-21 20:50:24 +0000 | [diff] [blame] | 215 | |
| 216 | // Move all definitions in the succecessor to the predecessor... |
Chris Lattner | 1896150 | 2002-06-25 16:12:52 +0000 | [diff] [blame] | 217 | OnlyPred->getInstList().splice(OnlyPred->end(), BB->getInstList()); |
| 218 | |
Chris Lattner | 01d1ee3 | 2002-05-21 20:50:24 +0000 | [diff] [blame] | 219 | // Make all PHI nodes that refered to BB now refer to Pred as their |
| 220 | // source... |
| 221 | BB->replaceAllUsesWith(OnlyPred); |
Chris Lattner | 1896150 | 2002-06-25 16:12:52 +0000 | [diff] [blame] | 222 | |
| 223 | std::string OldName = BB->getName(); |
| 224 | |
| 225 | // Erase basic block from the function... |
| 226 | M->getBasicBlockList().erase(BB); |
| 227 | |
Chris Lattner | 01d1ee3 | 2002-05-21 20:50:24 +0000 | [diff] [blame] | 228 | // Inherit predecessors name if it exists... |
Chris Lattner | 1896150 | 2002-06-25 16:12:52 +0000 | [diff] [blame] | 229 | if (!OldName.empty() && !OnlyPred->hasName()) |
| 230 | OnlyPred->setName(OldName); |
Chris Lattner | 01d1ee3 | 2002-05-21 20:50:24 +0000 | [diff] [blame] | 231 | |
Chris Lattner | 01d1ee3 | 2002-05-21 20:50:24 +0000 | [diff] [blame] | 232 | return true; |
| 233 | } |
| 234 | } |
| 235 | |
| 236 | return false; |
| 237 | } |