SimplifyCFG.cpp revision 6306d07aa8cf71e3c7fed7f295665f53595473eb
13ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch//===- SimplifyCFG.cpp - Code to perform CFG simplification ---------------===// 23ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch// 33ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch// The LLVM Compiler Infrastructure 43ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch// 53ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch// This file was developed by the LLVM research group and is distributed under 63ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch// the University of Illinois Open Source License. See LICENSE.TXT for details. 73ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch// 83ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch//===----------------------------------------------------------------------===// 93ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch// 103ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch// Peephole optimize the CFG. 113ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch// 123ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch//===----------------------------------------------------------------------===// 133ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 143ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch#define DEBUG_TYPE "simplifycfg" 153ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch#include "llvm/Transforms/Utils/Local.h" 163ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch#include "llvm/Constants.h" 173ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch#include "llvm/Instructions.h" 183ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch#include "llvm/Type.h" 193ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch#include "llvm/Support/CFG.h" 203ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch#include "llvm/Support/Debug.h" 213ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch#include <algorithm> 223ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch#include <functional> 233ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch#include <set> 243ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch#include <map> 253ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochusing namespace llvm; 263ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 273ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch/// SafeToMergeTerminators - Return true if it is safe to merge these two 283ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch/// terminator instructions together. 293ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch/// 303ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochstatic bool SafeToMergeTerminators(TerminatorInst *SI1, TerminatorInst *SI2) { 313ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (SI1 == SI2) return false; // Can't merge with self! 323ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 333ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // It is not safe to merge these two switch instructions if they have a common 343ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // successor, and if that successor has a PHI node, and if *that* PHI node has 353ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // conflicting incoming values from the two switch blocks. 363ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch BasicBlock *SI1BB = SI1->getParent(); 373ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch BasicBlock *SI2BB = SI2->getParent(); 383ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch std::set<BasicBlock*> SI1Succs(succ_begin(SI1BB), succ_end(SI1BB)); 393ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 403ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch for (succ_iterator I = succ_begin(SI2BB), E = succ_end(SI2BB); I != E; ++I) 413ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (SI1Succs.count(*I)) 423ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch for (BasicBlock::iterator BBI = (*I)->begin(); 433ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch isa<PHINode>(BBI); ++BBI) { 443ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch PHINode *PN = cast<PHINode>(BBI); 453ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (PN->getIncomingValueForBlock(SI1BB) != 463ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch PN->getIncomingValueForBlock(SI2BB)) 473ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch return false; 483ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch } 493ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 503ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch return true; 513ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch} 523ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 533ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch/// AddPredecessorToBlock - Update PHI nodes in Succ to indicate that there will 543ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch/// now be entries in it from the 'NewPred' block. The values that will be 553ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch/// flowing into the PHI nodes will be the same as those coming in from 563ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch/// ExistPred, an existing predecessor of Succ. 573ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochstatic void AddPredecessorToBlock(BasicBlock *Succ, BasicBlock *NewPred, 583ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch BasicBlock *ExistPred) { 593ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch assert(std::find(succ_begin(ExistPred), succ_end(ExistPred), Succ) != 603ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch succ_end(ExistPred) && "ExistPred is not a predecessor of Succ!"); 613ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (!isa<PHINode>(Succ->begin())) return; // Quick exit if nothing to do 623ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 633ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) { 643ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch PHINode *PN = cast<PHINode>(I); 653ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch Value *V = PN->getIncomingValueForBlock(ExistPred); 663ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch PN->addIncoming(V, NewPred); 673ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch } 683ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch} 693ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 703ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch// CanPropagatePredecessorsForPHIs - Return true if we can fold BB, an 713ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch// almost-empty BB ending in an unconditional branch to Succ, into succ. 723ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch// 733ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch// Assumption: Succ is the single successor for BB. 743ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch// 753ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochstatic bool CanPropagatePredecessorsForPHIs(BasicBlock *BB, BasicBlock *Succ) { 763ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch assert(*succ_begin(BB) == Succ && "Succ is not successor of BB!"); 773ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 783ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // Check to see if one of the predecessors of BB is already a predecessor of 793ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // Succ. If so, we cannot do the transformation if there are any PHI nodes 803ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // with incompatible values coming in from the two edges! 813ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // 823ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (isa<PHINode>(Succ->front())) { 833ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch std::set<BasicBlock*> BBPreds(pred_begin(BB), pred_end(BB)); 843ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch for (pred_iterator PI = pred_begin(Succ), PE = pred_end(Succ);\ 853ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch PI != PE; ++PI) 863ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (std::find(BBPreds.begin(), BBPreds.end(), *PI) != BBPreds.end()) { 873ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // Loop over all of the PHI nodes checking to see if there are 883ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // incompatible values coming in. 893ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) { 903ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch PHINode *PN = cast<PHINode>(I); 913ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // Loop up the entries in the PHI node for BB and for *PI if the 923ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // values coming in are non-equal, we cannot merge these two blocks 933ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // (instead we should insert a conditional move or something, then 943ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // merge the blocks). 953ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (PN->getIncomingValueForBlock(BB) != 963ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch PN->getIncomingValueForBlock(*PI)) 973ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch return false; // Values are not equal... 983ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch } 993ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch } 1003ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch } 1013ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 1023ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // Finally, if BB has PHI nodes that are used by things other than the PHIs in 1033ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // Succ and Succ has predecessors that are not Succ and not Pred, we cannot 1043ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // fold these blocks, as we don't know whether BB dominates Succ or not to 1053ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // update the PHI nodes correctly. 1063ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (!isa<PHINode>(BB->begin()) || Succ->getSinglePredecessor()) return true; 1073ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 1083ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // If the predecessors of Succ are only BB and Succ itself, we can handle this. 1093ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch bool IsSafe = true; 1103ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch for (pred_iterator PI = pred_begin(Succ), E = pred_end(Succ); PI != E; ++PI) 1113ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (*PI != Succ && *PI != BB) { 1123ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch IsSafe = false; 1133ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch break; 1143ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch } 1153ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (IsSafe) return true; 1163ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 1173ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // If the PHI nodes in BB are only used by instructions in Succ, we are ok. 1183ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch IsSafe = true; 1193ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I) && IsSafe; ++I) { 1203ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch PHINode *PN = cast<PHINode>(I); 1213ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch for (Value::use_iterator UI = PN->use_begin(), E = PN->use_end(); UI != E; 1223ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch ++UI) 1233ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (cast<Instruction>(*UI)->getParent() != Succ) { 1243ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch IsSafe = false; 1253ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch break; 1263ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch } 1273ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch } 1283ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 1293ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch return IsSafe; 1303ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch} 1313ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 1323ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch/// TryToSimplifyUncondBranchFromEmptyBlock - BB contains an unconditional 1333ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch/// branch to Succ, and contains no instructions other than PHI nodes and the 1343ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch/// branch. If possible, eliminate BB. 1353ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochstatic bool TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB, 1363ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch BasicBlock *Succ) { 1373ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // If our successor has PHI nodes, then we need to update them to include 1383ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // entries for BB's predecessors, not for BB itself. Be careful though, 1393ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // if this transformation fails (returns true) then we cannot do this 1403ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // transformation! 1413ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // 1423ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (!CanPropagatePredecessorsForPHIs(BB, Succ)) return false; 1433ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 1443ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch DEBUG(std::cerr << "Killing Trivial BB: \n" << *BB); 1453ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 1463ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (isa<PHINode>(Succ->begin())) { 1473ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // If there is more than one pred of succ, and there are PHI nodes in 1483ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // the successor, then we need to add incoming edges for the PHI nodes 1493ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // 1503ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch const std::vector<BasicBlock*> BBPreds(pred_begin(BB), pred_end(BB)); 1513ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 1523ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // Loop over all of the PHI nodes in the successor of BB. 1533ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) { 1543ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch PHINode *PN = cast<PHINode>(I); 1553ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch Value *OldVal = PN->removeIncomingValue(BB, false); 156 assert(OldVal && "No entry in PHI for Pred BB!"); 157 158 // If this incoming value is one of the PHI nodes in BB, the new entries 159 // in the PHI node are the entries from the old PHI. 160 if (isa<PHINode>(OldVal) && cast<PHINode>(OldVal)->getParent() == BB) { 161 PHINode *OldValPN = cast<PHINode>(OldVal); 162 for (unsigned i = 0, e = OldValPN->getNumIncomingValues(); i != e; ++i) 163 PN->addIncoming(OldValPN->getIncomingValue(i), 164 OldValPN->getIncomingBlock(i)); 165 } else { 166 for (std::vector<BasicBlock*>::const_iterator PredI = BBPreds.begin(), 167 End = BBPreds.end(); PredI != End; ++PredI) { 168 // Add an incoming value for each of the new incoming values... 169 PN->addIncoming(OldVal, *PredI); 170 } 171 } 172 } 173 } 174 175 if (isa<PHINode>(&BB->front())) { 176 std::vector<BasicBlock*> 177 OldSuccPreds(pred_begin(Succ), pred_end(Succ)); 178 179 // Move all PHI nodes in BB to Succ if they are alive, otherwise 180 // delete them. 181 while (PHINode *PN = dyn_cast<PHINode>(&BB->front())) 182 if (PN->use_empty()) { 183 // Just remove the dead phi. This happens if Succ's PHIs were the only 184 // users of the PHI nodes. 185 PN->eraseFromParent(); 186 } else { 187 // The instruction is alive, so this means that Succ must have 188 // *ONLY* had BB as a predecessor, and the PHI node is still valid 189 // now. Simply move it into Succ, because we know that BB 190 // strictly dominated Succ. 191 Succ->getInstList().splice(Succ->begin(), 192 BB->getInstList(), BB->begin()); 193 194 // We need to add new entries for the PHI node to account for 195 // predecessors of Succ that the PHI node does not take into 196 // account. At this point, since we know that BB dominated succ, 197 // this means that we should any newly added incoming edges should 198 // use the PHI node as the value for these edges, because they are 199 // loop back edges. 200 for (unsigned i = 0, e = OldSuccPreds.size(); i != e; ++i) 201 if (OldSuccPreds[i] != BB) 202 PN->addIncoming(PN, OldSuccPreds[i]); 203 } 204 } 205 206 // Everything that jumped to BB now goes to Succ. 207 std::string OldName = BB->getName(); 208 BB->replaceAllUsesWith(Succ); 209 BB->eraseFromParent(); // Delete the old basic block. 210 211 if (!OldName.empty() && !Succ->hasName()) // Transfer name if we can 212 Succ->setName(OldName); 213 return true; 214} 215 216/// GetIfCondition - Given a basic block (BB) with two predecessors (and 217/// presumably PHI nodes in it), check to see if the merge at this block is due 218/// to an "if condition". If so, return the boolean condition that determines 219/// which entry into BB will be taken. Also, return by references the block 220/// that will be entered from if the condition is true, and the block that will 221/// be entered if the condition is false. 222/// 223/// 224static Value *GetIfCondition(BasicBlock *BB, 225 BasicBlock *&IfTrue, BasicBlock *&IfFalse) { 226 assert(std::distance(pred_begin(BB), pred_end(BB)) == 2 && 227 "Function can only handle blocks with 2 predecessors!"); 228 BasicBlock *Pred1 = *pred_begin(BB); 229 BasicBlock *Pred2 = *++pred_begin(BB); 230 231 // We can only handle branches. Other control flow will be lowered to 232 // branches if possible anyway. 233 if (!isa<BranchInst>(Pred1->getTerminator()) || 234 !isa<BranchInst>(Pred2->getTerminator())) 235 return 0; 236 BranchInst *Pred1Br = cast<BranchInst>(Pred1->getTerminator()); 237 BranchInst *Pred2Br = cast<BranchInst>(Pred2->getTerminator()); 238 239 // Eliminate code duplication by ensuring that Pred1Br is conditional if 240 // either are. 241 if (Pred2Br->isConditional()) { 242 // If both branches are conditional, we don't have an "if statement". In 243 // reality, we could transform this case, but since the condition will be 244 // required anyway, we stand no chance of eliminating it, so the xform is 245 // probably not profitable. 246 if (Pred1Br->isConditional()) 247 return 0; 248 249 std::swap(Pred1, Pred2); 250 std::swap(Pred1Br, Pred2Br); 251 } 252 253 if (Pred1Br->isConditional()) { 254 // If we found a conditional branch predecessor, make sure that it branches 255 // to BB and Pred2Br. If it doesn't, this isn't an "if statement". 256 if (Pred1Br->getSuccessor(0) == BB && 257 Pred1Br->getSuccessor(1) == Pred2) { 258 IfTrue = Pred1; 259 IfFalse = Pred2; 260 } else if (Pred1Br->getSuccessor(0) == Pred2 && 261 Pred1Br->getSuccessor(1) == BB) { 262 IfTrue = Pred2; 263 IfFalse = Pred1; 264 } else { 265 // We know that one arm of the conditional goes to BB, so the other must 266 // go somewhere unrelated, and this must not be an "if statement". 267 return 0; 268 } 269 270 // The only thing we have to watch out for here is to make sure that Pred2 271 // doesn't have incoming edges from other blocks. If it does, the condition 272 // doesn't dominate BB. 273 if (++pred_begin(Pred2) != pred_end(Pred2)) 274 return 0; 275 276 return Pred1Br->getCondition(); 277 } 278 279 // Ok, if we got here, both predecessors end with an unconditional branch to 280 // BB. Don't panic! If both blocks only have a single (identical) 281 // predecessor, and THAT is a conditional branch, then we're all ok! 282 if (pred_begin(Pred1) == pred_end(Pred1) || 283 ++pred_begin(Pred1) != pred_end(Pred1) || 284 pred_begin(Pred2) == pred_end(Pred2) || 285 ++pred_begin(Pred2) != pred_end(Pred2) || 286 *pred_begin(Pred1) != *pred_begin(Pred2)) 287 return 0; 288 289 // Otherwise, if this is a conditional branch, then we can use it! 290 BasicBlock *CommonPred = *pred_begin(Pred1); 291 if (BranchInst *BI = dyn_cast<BranchInst>(CommonPred->getTerminator())) { 292 assert(BI->isConditional() && "Two successors but not conditional?"); 293 if (BI->getSuccessor(0) == Pred1) { 294 IfTrue = Pred1; 295 IfFalse = Pred2; 296 } else { 297 IfTrue = Pred2; 298 IfFalse = Pred1; 299 } 300 return BI->getCondition(); 301 } 302 return 0; 303} 304 305 306// If we have a merge point of an "if condition" as accepted above, return true 307// if the specified value dominates the block. We don't handle the true 308// generality of domination here, just a special case which works well enough 309// for us. 310// 311// If AggressiveInsts is non-null, and if V does not dominate BB, we check to 312// see if V (which must be an instruction) is cheap to compute and is 313// non-trapping. If both are true, the instruction is inserted into the set and 314// true is returned. 315static bool DominatesMergePoint(Value *V, BasicBlock *BB, 316 std::set<Instruction*> *AggressiveInsts) { 317 Instruction *I = dyn_cast<Instruction>(V); 318 if (!I) return true; // Non-instructions all dominate instructions. 319 BasicBlock *PBB = I->getParent(); 320 321 // We don't want to allow weird loops that might have the "if condition" in 322 // the bottom of this block. 323 if (PBB == BB) return false; 324 325 // If this instruction is defined in a block that contains an unconditional 326 // branch to BB, then it must be in the 'conditional' part of the "if 327 // statement". 328 if (BranchInst *BI = dyn_cast<BranchInst>(PBB->getTerminator())) 329 if (BI->isUnconditional() && BI->getSuccessor(0) == BB) { 330 if (!AggressiveInsts) return false; 331 // Okay, it looks like the instruction IS in the "condition". Check to 332 // see if its a cheap instruction to unconditionally compute, and if it 333 // only uses stuff defined outside of the condition. If so, hoist it out. 334 switch (I->getOpcode()) { 335 default: return false; // Cannot hoist this out safely. 336 case Instruction::Load: 337 // We can hoist loads that are non-volatile and obviously cannot trap. 338 if (cast<LoadInst>(I)->isVolatile()) 339 return false; 340 if (!isa<AllocaInst>(I->getOperand(0)) && 341 !isa<Constant>(I->getOperand(0))) 342 return false; 343 344 // Finally, we have to check to make sure there are no instructions 345 // before the load in its basic block, as we are going to hoist the loop 346 // out to its predecessor. 347 if (PBB->begin() != BasicBlock::iterator(I)) 348 return false; 349 break; 350 case Instruction::Add: 351 case Instruction::Sub: 352 case Instruction::And: 353 case Instruction::Or: 354 case Instruction::Xor: 355 case Instruction::Shl: 356 case Instruction::Shr: 357 case Instruction::SetEQ: 358 case Instruction::SetNE: 359 case Instruction::SetLT: 360 case Instruction::SetGT: 361 case Instruction::SetLE: 362 case Instruction::SetGE: 363 break; // These are all cheap and non-trapping instructions. 364 } 365 366 // Okay, we can only really hoist these out if their operands are not 367 // defined in the conditional region. 368 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) 369 if (!DominatesMergePoint(I->getOperand(i), BB, 0)) 370 return false; 371 // Okay, it's safe to do this! Remember this instruction. 372 AggressiveInsts->insert(I); 373 } 374 375 return true; 376} 377 378// GatherConstantSetEQs - Given a potentially 'or'd together collection of seteq 379// instructions that compare a value against a constant, return the value being 380// compared, and stick the constant into the Values vector. 381static Value *GatherConstantSetEQs(Value *V, std::vector<ConstantInt*> &Values){ 382 if (Instruction *Inst = dyn_cast<Instruction>(V)) 383 if (Inst->getOpcode() == Instruction::SetEQ) { 384 if (ConstantInt *C = dyn_cast<ConstantInt>(Inst->getOperand(1))) { 385 Values.push_back(C); 386 return Inst->getOperand(0); 387 } else if (ConstantInt *C = dyn_cast<ConstantInt>(Inst->getOperand(0))) { 388 Values.push_back(C); 389 return Inst->getOperand(1); 390 } 391 } else if (Inst->getOpcode() == Instruction::Or) { 392 if (Value *LHS = GatherConstantSetEQs(Inst->getOperand(0), Values)) 393 if (Value *RHS = GatherConstantSetEQs(Inst->getOperand(1), Values)) 394 if (LHS == RHS) 395 return LHS; 396 } 397 return 0; 398} 399 400// GatherConstantSetNEs - Given a potentially 'and'd together collection of 401// setne instructions that compare a value against a constant, return the value 402// being compared, and stick the constant into the Values vector. 403static Value *GatherConstantSetNEs(Value *V, std::vector<ConstantInt*> &Values){ 404 if (Instruction *Inst = dyn_cast<Instruction>(V)) 405 if (Inst->getOpcode() == Instruction::SetNE) { 406 if (ConstantInt *C = dyn_cast<ConstantInt>(Inst->getOperand(1))) { 407 Values.push_back(C); 408 return Inst->getOperand(0); 409 } else if (ConstantInt *C = dyn_cast<ConstantInt>(Inst->getOperand(0))) { 410 Values.push_back(C); 411 return Inst->getOperand(1); 412 } 413 } else if (Inst->getOpcode() == Instruction::Cast) { 414 // Cast of X to bool is really a comparison against zero. 415 assert(Inst->getType() == Type::BoolTy && "Can only handle bool values!"); 416 Values.push_back(ConstantInt::get(Inst->getOperand(0)->getType(), 0)); 417 return Inst->getOperand(0); 418 } else if (Inst->getOpcode() == Instruction::And) { 419 if (Value *LHS = GatherConstantSetNEs(Inst->getOperand(0), Values)) 420 if (Value *RHS = GatherConstantSetNEs(Inst->getOperand(1), Values)) 421 if (LHS == RHS) 422 return LHS; 423 } 424 return 0; 425} 426 427 428 429/// GatherValueComparisons - If the specified Cond is an 'and' or 'or' of a 430/// bunch of comparisons of one value against constants, return the value and 431/// the constants being compared. 432static bool GatherValueComparisons(Instruction *Cond, Value *&CompVal, 433 std::vector<ConstantInt*> &Values) { 434 if (Cond->getOpcode() == Instruction::Or) { 435 CompVal = GatherConstantSetEQs(Cond, Values); 436 437 // Return true to indicate that the condition is true if the CompVal is 438 // equal to one of the constants. 439 return true; 440 } else if (Cond->getOpcode() == Instruction::And) { 441 CompVal = GatherConstantSetNEs(Cond, Values); 442 443 // Return false to indicate that the condition is false if the CompVal is 444 // equal to one of the constants. 445 return false; 446 } 447 return false; 448} 449 450/// ErasePossiblyDeadInstructionTree - If the specified instruction is dead and 451/// has no side effects, nuke it. If it uses any instructions that become dead 452/// because the instruction is now gone, nuke them too. 453static void ErasePossiblyDeadInstructionTree(Instruction *I) { 454 if (isInstructionTriviallyDead(I)) { 455 std::vector<Value*> Operands(I->op_begin(), I->op_end()); 456 I->getParent()->getInstList().erase(I); 457 for (unsigned i = 0, e = Operands.size(); i != e; ++i) 458 if (Instruction *OpI = dyn_cast<Instruction>(Operands[i])) 459 ErasePossiblyDeadInstructionTree(OpI); 460 } 461} 462 463// isValueEqualityComparison - Return true if the specified terminator checks to 464// see if a value is equal to constant integer value. 465static Value *isValueEqualityComparison(TerminatorInst *TI) { 466 if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 467 // Do not permit merging of large switch instructions into their 468 // predecessors unless there is only one predecessor. 469 if (SI->getNumSuccessors() * std::distance(pred_begin(SI->getParent()), 470 pred_end(SI->getParent())) > 128) 471 return 0; 472 473 return SI->getCondition(); 474 } 475 if (BranchInst *BI = dyn_cast<BranchInst>(TI)) 476 if (BI->isConditional() && BI->getCondition()->hasOneUse()) 477 if (SetCondInst *SCI = dyn_cast<SetCondInst>(BI->getCondition())) 478 if ((SCI->getOpcode() == Instruction::SetEQ || 479 SCI->getOpcode() == Instruction::SetNE) && 480 isa<ConstantInt>(SCI->getOperand(1))) 481 return SCI->getOperand(0); 482 return 0; 483} 484 485// Given a value comparison instruction, decode all of the 'cases' that it 486// represents and return the 'default' block. 487static BasicBlock * 488GetValueEqualityComparisonCases(TerminatorInst *TI, 489 std::vector<std::pair<ConstantInt*, 490 BasicBlock*> > &Cases) { 491 if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 492 Cases.reserve(SI->getNumCases()); 493 for (unsigned i = 1, e = SI->getNumCases(); i != e; ++i) 494 Cases.push_back(std::make_pair(SI->getCaseValue(i), SI->getSuccessor(i))); 495 return SI->getDefaultDest(); 496 } 497 498 BranchInst *BI = cast<BranchInst>(TI); 499 SetCondInst *SCI = cast<SetCondInst>(BI->getCondition()); 500 Cases.push_back(std::make_pair(cast<ConstantInt>(SCI->getOperand(1)), 501 BI->getSuccessor(SCI->getOpcode() == 502 Instruction::SetNE))); 503 return BI->getSuccessor(SCI->getOpcode() == Instruction::SetEQ); 504} 505 506 507// EliminateBlockCases - Given an vector of bb/value pairs, remove any entries 508// in the list that match the specified block. 509static void EliminateBlockCases(BasicBlock *BB, 510 std::vector<std::pair<ConstantInt*, BasicBlock*> > &Cases) { 511 for (unsigned i = 0, e = Cases.size(); i != e; ++i) 512 if (Cases[i].second == BB) { 513 Cases.erase(Cases.begin()+i); 514 --i; --e; 515 } 516} 517 518// ValuesOverlap - Return true if there are any keys in C1 that exist in C2 as 519// well. 520static bool 521ValuesOverlap(std::vector<std::pair<ConstantInt*, BasicBlock*> > &C1, 522 std::vector<std::pair<ConstantInt*, BasicBlock*> > &C2) { 523 std::vector<std::pair<ConstantInt*, BasicBlock*> > *V1 = &C1, *V2 = &C2; 524 525 // Make V1 be smaller than V2. 526 if (V1->size() > V2->size()) 527 std::swap(V1, V2); 528 529 if (V1->size() == 0) return false; 530 if (V1->size() == 1) { 531 // Just scan V2. 532 ConstantInt *TheVal = (*V1)[0].first; 533 for (unsigned i = 0, e = V2->size(); i != e; ++i) 534 if (TheVal == (*V2)[i].first) 535 return true; 536 } 537 538 // Otherwise, just sort both lists and compare element by element. 539 std::sort(V1->begin(), V1->end()); 540 std::sort(V2->begin(), V2->end()); 541 unsigned i1 = 0, i2 = 0, e1 = V1->size(), e2 = V2->size(); 542 while (i1 != e1 && i2 != e2) { 543 if ((*V1)[i1].first == (*V2)[i2].first) 544 return true; 545 if ((*V1)[i1].first < (*V2)[i2].first) 546 ++i1; 547 else 548 ++i2; 549 } 550 return false; 551} 552 553// SimplifyEqualityComparisonWithOnlyPredecessor - If TI is known to be a 554// terminator instruction and its block is known to only have a single 555// predecessor block, check to see if that predecessor is also a value 556// comparison with the same value, and if that comparison determines the outcome 557// of this comparison. If so, simplify TI. This does a very limited form of 558// jump threading. 559static bool SimplifyEqualityComparisonWithOnlyPredecessor(TerminatorInst *TI, 560 BasicBlock *Pred) { 561 Value *PredVal = isValueEqualityComparison(Pred->getTerminator()); 562 if (!PredVal) return false; // Not a value comparison in predecessor. 563 564 Value *ThisVal = isValueEqualityComparison(TI); 565 assert(ThisVal && "This isn't a value comparison!!"); 566 if (ThisVal != PredVal) return false; // Different predicates. 567 568 // Find out information about when control will move from Pred to TI's block. 569 std::vector<std::pair<ConstantInt*, BasicBlock*> > PredCases; 570 BasicBlock *PredDef = GetValueEqualityComparisonCases(Pred->getTerminator(), 571 PredCases); 572 EliminateBlockCases(PredDef, PredCases); // Remove default from cases. 573 574 // Find information about how control leaves this block. 575 std::vector<std::pair<ConstantInt*, BasicBlock*> > ThisCases; 576 BasicBlock *ThisDef = GetValueEqualityComparisonCases(TI, ThisCases); 577 EliminateBlockCases(ThisDef, ThisCases); // Remove default from cases. 578 579 // If TI's block is the default block from Pred's comparison, potentially 580 // simplify TI based on this knowledge. 581 if (PredDef == TI->getParent()) { 582 // If we are here, we know that the value is none of those cases listed in 583 // PredCases. If there are any cases in ThisCases that are in PredCases, we 584 // can simplify TI. 585 if (ValuesOverlap(PredCases, ThisCases)) { 586 if (BranchInst *BTI = dyn_cast<BranchInst>(TI)) { 587 // Okay, one of the successors of this condbr is dead. Convert it to a 588 // uncond br. 589 assert(ThisCases.size() == 1 && "Branch can only have one case!"); 590 Value *Cond = BTI->getCondition(); 591 // Insert the new branch. 592 Instruction *NI = new BranchInst(ThisDef, TI); 593 594 // Remove PHI node entries for the dead edge. 595 ThisCases[0].second->removePredecessor(TI->getParent()); 596 597 DEBUG(std::cerr << "Threading pred instr: " << *Pred->getTerminator() 598 << "Through successor TI: " << *TI << "Leaving: " << *NI << "\n"); 599 600 TI->eraseFromParent(); // Nuke the old one. 601 // If condition is now dead, nuke it. 602 if (Instruction *CondI = dyn_cast<Instruction>(Cond)) 603 ErasePossiblyDeadInstructionTree(CondI); 604 return true; 605 606 } else { 607 SwitchInst *SI = cast<SwitchInst>(TI); 608 // Okay, TI has cases that are statically dead, prune them away. 609 std::set<Constant*> DeadCases; 610 for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 611 DeadCases.insert(PredCases[i].first); 612 613 DEBUG(std::cerr << "Threading pred instr: " << *Pred->getTerminator() 614 << "Through successor TI: " << *TI); 615 616 for (unsigned i = SI->getNumCases()-1; i != 0; --i) 617 if (DeadCases.count(SI->getCaseValue(i))) { 618 SI->getSuccessor(i)->removePredecessor(TI->getParent()); 619 SI->removeCase(i); 620 } 621 622 DEBUG(std::cerr << "Leaving: " << *TI << "\n"); 623 return true; 624 } 625 } 626 627 } else { 628 // Otherwise, TI's block must correspond to some matched value. Find out 629 // which value (or set of values) this is. 630 ConstantInt *TIV = 0; 631 BasicBlock *TIBB = TI->getParent(); 632 for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 633 if (PredCases[i].second == TIBB) 634 if (TIV == 0) 635 TIV = PredCases[i].first; 636 else 637 return false; // Cannot handle multiple values coming to this block. 638 assert(TIV && "No edge from pred to succ?"); 639 640 // Okay, we found the one constant that our value can be if we get into TI's 641 // BB. Find out which successor will unconditionally be branched to. 642 BasicBlock *TheRealDest = 0; 643 for (unsigned i = 0, e = ThisCases.size(); i != e; ++i) 644 if (ThisCases[i].first == TIV) { 645 TheRealDest = ThisCases[i].second; 646 break; 647 } 648 649 // If not handled by any explicit cases, it is handled by the default case. 650 if (TheRealDest == 0) TheRealDest = ThisDef; 651 652 // Remove PHI node entries for dead edges. 653 BasicBlock *CheckEdge = TheRealDest; 654 for (succ_iterator SI = succ_begin(TIBB), e = succ_end(TIBB); SI != e; ++SI) 655 if (*SI != CheckEdge) 656 (*SI)->removePredecessor(TIBB); 657 else 658 CheckEdge = 0; 659 660 // Insert the new branch. 661 Instruction *NI = new BranchInst(TheRealDest, TI); 662 663 DEBUG(std::cerr << "Threading pred instr: " << *Pred->getTerminator() 664 << "Through successor TI: " << *TI << "Leaving: " << *NI << "\n"); 665 Instruction *Cond = 0; 666 if (BranchInst *BI = dyn_cast<BranchInst>(TI)) 667 Cond = dyn_cast<Instruction>(BI->getCondition()); 668 TI->eraseFromParent(); // Nuke the old one. 669 670 if (Cond) ErasePossiblyDeadInstructionTree(Cond); 671 return true; 672 } 673 return false; 674} 675 676// FoldValueComparisonIntoPredecessors - The specified terminator is a value 677// equality comparison instruction (either a switch or a branch on "X == c"). 678// See if any of the predecessors of the terminator block are value comparisons 679// on the same value. If so, and if safe to do so, fold them together. 680static bool FoldValueComparisonIntoPredecessors(TerminatorInst *TI) { 681 BasicBlock *BB = TI->getParent(); 682 Value *CV = isValueEqualityComparison(TI); // CondVal 683 assert(CV && "Not a comparison?"); 684 bool Changed = false; 685 686 std::vector<BasicBlock*> Preds(pred_begin(BB), pred_end(BB)); 687 while (!Preds.empty()) { 688 BasicBlock *Pred = Preds.back(); 689 Preds.pop_back(); 690 691 // See if the predecessor is a comparison with the same value. 692 TerminatorInst *PTI = Pred->getTerminator(); 693 Value *PCV = isValueEqualityComparison(PTI); // PredCondVal 694 695 if (PCV == CV && SafeToMergeTerminators(TI, PTI)) { 696 // Figure out which 'cases' to copy from SI to PSI. 697 std::vector<std::pair<ConstantInt*, BasicBlock*> > BBCases; 698 BasicBlock *BBDefault = GetValueEqualityComparisonCases(TI, BBCases); 699 700 std::vector<std::pair<ConstantInt*, BasicBlock*> > PredCases; 701 BasicBlock *PredDefault = GetValueEqualityComparisonCases(PTI, PredCases); 702 703 // Based on whether the default edge from PTI goes to BB or not, fill in 704 // PredCases and PredDefault with the new switch cases we would like to 705 // build. 706 std::vector<BasicBlock*> NewSuccessors; 707 708 if (PredDefault == BB) { 709 // If this is the default destination from PTI, only the edges in TI 710 // that don't occur in PTI, or that branch to BB will be activated. 711 std::set<ConstantInt*> PTIHandled; 712 for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 713 if (PredCases[i].second != BB) 714 PTIHandled.insert(PredCases[i].first); 715 else { 716 // The default destination is BB, we don't need explicit targets. 717 std::swap(PredCases[i], PredCases.back()); 718 PredCases.pop_back(); 719 --i; --e; 720 } 721 722 // Reconstruct the new switch statement we will be building. 723 if (PredDefault != BBDefault) { 724 PredDefault->removePredecessor(Pred); 725 PredDefault = BBDefault; 726 NewSuccessors.push_back(BBDefault); 727 } 728 for (unsigned i = 0, e = BBCases.size(); i != e; ++i) 729 if (!PTIHandled.count(BBCases[i].first) && 730 BBCases[i].second != BBDefault) { 731 PredCases.push_back(BBCases[i]); 732 NewSuccessors.push_back(BBCases[i].second); 733 } 734 735 } else { 736 // If this is not the default destination from PSI, only the edges 737 // in SI that occur in PSI with a destination of BB will be 738 // activated. 739 std::set<ConstantInt*> PTIHandled; 740 for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 741 if (PredCases[i].second == BB) { 742 PTIHandled.insert(PredCases[i].first); 743 std::swap(PredCases[i], PredCases.back()); 744 PredCases.pop_back(); 745 --i; --e; 746 } 747 748 // Okay, now we know which constants were sent to BB from the 749 // predecessor. Figure out where they will all go now. 750 for (unsigned i = 0, e = BBCases.size(); i != e; ++i) 751 if (PTIHandled.count(BBCases[i].first)) { 752 // If this is one we are capable of getting... 753 PredCases.push_back(BBCases[i]); 754 NewSuccessors.push_back(BBCases[i].second); 755 PTIHandled.erase(BBCases[i].first);// This constant is taken care of 756 } 757 758 // If there are any constants vectored to BB that TI doesn't handle, 759 // they must go to the default destination of TI. 760 for (std::set<ConstantInt*>::iterator I = PTIHandled.begin(), 761 E = PTIHandled.end(); I != E; ++I) { 762 PredCases.push_back(std::make_pair(*I, BBDefault)); 763 NewSuccessors.push_back(BBDefault); 764 } 765 } 766 767 // Okay, at this point, we know which new successor Pred will get. Make 768 // sure we update the number of entries in the PHI nodes for these 769 // successors. 770 for (unsigned i = 0, e = NewSuccessors.size(); i != e; ++i) 771 AddPredecessorToBlock(NewSuccessors[i], Pred, BB); 772 773 // Now that the successors are updated, create the new Switch instruction. 774 SwitchInst *NewSI = new SwitchInst(CV, PredDefault, PredCases.size(),PTI); 775 for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 776 NewSI->addCase(PredCases[i].first, PredCases[i].second); 777 778 Instruction *DeadCond = 0; 779 if (BranchInst *BI = dyn_cast<BranchInst>(PTI)) 780 // If PTI is a branch, remember the condition. 781 DeadCond = dyn_cast<Instruction>(BI->getCondition()); 782 Pred->getInstList().erase(PTI); 783 784 // If the condition is dead now, remove the instruction tree. 785 if (DeadCond) ErasePossiblyDeadInstructionTree(DeadCond); 786 787 // Okay, last check. If BB is still a successor of PSI, then we must 788 // have an infinite loop case. If so, add an infinitely looping block 789 // to handle the case to preserve the behavior of the code. 790 BasicBlock *InfLoopBlock = 0; 791 for (unsigned i = 0, e = NewSI->getNumSuccessors(); i != e; ++i) 792 if (NewSI->getSuccessor(i) == BB) { 793 if (InfLoopBlock == 0) { 794 // Insert it at the end of the loop, because it's either code, 795 // or it won't matter if it's hot. :) 796 InfLoopBlock = new BasicBlock("infloop", BB->getParent()); 797 new BranchInst(InfLoopBlock, InfLoopBlock); 798 } 799 NewSI->setSuccessor(i, InfLoopBlock); 800 } 801 802 Changed = true; 803 } 804 } 805 return Changed; 806} 807 808/// HoistThenElseCodeToIf - Given a conditional branch that goes to BB1 and 809/// BB2, hoist any common code in the two blocks up into the branch block. The 810/// caller of this function guarantees that BI's block dominates BB1 and BB2. 811static bool HoistThenElseCodeToIf(BranchInst *BI) { 812 // This does very trivial matching, with limited scanning, to find identical 813 // instructions in the two blocks. In particular, we don't want to get into 814 // O(M*N) situations here where M and N are the sizes of BB1 and BB2. As 815 // such, we currently just scan for obviously identical instructions in an 816 // identical order. 817 BasicBlock *BB1 = BI->getSuccessor(0); // The true destination. 818 BasicBlock *BB2 = BI->getSuccessor(1); // The false destination 819 820 Instruction *I1 = BB1->begin(), *I2 = BB2->begin(); 821 if (I1->getOpcode() != I2->getOpcode() || !I1->isIdenticalTo(I2) || 822 isa<PHINode>(I1)) 823 return false; 824 825 // If we get here, we can hoist at least one instruction. 826 BasicBlock *BIParent = BI->getParent(); 827 828 do { 829 // If we are hoisting the terminator instruction, don't move one (making a 830 // broken BB), instead clone it, and remove BI. 831 if (isa<TerminatorInst>(I1)) 832 goto HoistTerminator; 833 834 // For a normal instruction, we just move one to right before the branch, 835 // then replace all uses of the other with the first. Finally, we remove 836 // the now redundant second instruction. 837 BIParent->getInstList().splice(BI, BB1->getInstList(), I1); 838 if (!I2->use_empty()) 839 I2->replaceAllUsesWith(I1); 840 BB2->getInstList().erase(I2); 841 842 I1 = BB1->begin(); 843 I2 = BB2->begin(); 844 } while (I1->getOpcode() == I2->getOpcode() && I1->isIdenticalTo(I2)); 845 846 return true; 847 848HoistTerminator: 849 // Okay, it is safe to hoist the terminator. 850 Instruction *NT = I1->clone(); 851 BIParent->getInstList().insert(BI, NT); 852 if (NT->getType() != Type::VoidTy) { 853 I1->replaceAllUsesWith(NT); 854 I2->replaceAllUsesWith(NT); 855 NT->setName(I1->getName()); 856 } 857 858 // Hoisting one of the terminators from our successor is a great thing. 859 // Unfortunately, the successors of the if/else blocks may have PHI nodes in 860 // them. If they do, all PHI entries for BB1/BB2 must agree for all PHI 861 // nodes, so we insert select instruction to compute the final result. 862 std::map<std::pair<Value*,Value*>, SelectInst*> InsertedSelects; 863 for (succ_iterator SI = succ_begin(BB1), E = succ_end(BB1); SI != E; ++SI) { 864 PHINode *PN; 865 for (BasicBlock::iterator BBI = SI->begin(); 866 (PN = dyn_cast<PHINode>(BBI)); ++BBI) { 867 Value *BB1V = PN->getIncomingValueForBlock(BB1); 868 Value *BB2V = PN->getIncomingValueForBlock(BB2); 869 if (BB1V != BB2V) { 870 // These values do not agree. Insert a select instruction before NT 871 // that determines the right value. 872 SelectInst *&SI = InsertedSelects[std::make_pair(BB1V, BB2V)]; 873 if (SI == 0) 874 SI = new SelectInst(BI->getCondition(), BB1V, BB2V, 875 BB1V->getName()+"."+BB2V->getName(), NT); 876 // Make the PHI node use the select for all incoming values for BB1/BB2 877 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 878 if (PN->getIncomingBlock(i) == BB1 || PN->getIncomingBlock(i) == BB2) 879 PN->setIncomingValue(i, SI); 880 } 881 } 882 } 883 884 // Update any PHI nodes in our new successors. 885 for (succ_iterator SI = succ_begin(BB1), E = succ_end(BB1); SI != E; ++SI) 886 AddPredecessorToBlock(*SI, BIParent, BB1); 887 888 BI->eraseFromParent(); 889 return true; 890} 891 892namespace { 893 /// ConstantIntOrdering - This class implements a stable ordering of constant 894 /// integers that does not depend on their address. This is important for 895 /// applications that sort ConstantInt's to ensure uniqueness. 896 struct ConstantIntOrdering { 897 bool operator()(const ConstantInt *LHS, const ConstantInt *RHS) const { 898 return LHS->getRawValue() < RHS->getRawValue(); 899 } 900 }; 901} 902 903// SimplifyCFG - This function is used to do simplification of a CFG. For 904// example, it adjusts branches to branches to eliminate the extra hop, it 905// eliminates unreachable basic blocks, and does other "peephole" optimization 906// of the CFG. It returns true if a modification was made. 907// 908// WARNING: The entry node of a function may not be simplified. 909// 910bool llvm::SimplifyCFG(BasicBlock *BB) { 911 bool Changed = false; 912 Function *M = BB->getParent(); 913 914 assert(BB && BB->getParent() && "Block not embedded in function!"); 915 assert(BB->getTerminator() && "Degenerate basic block encountered!"); 916 assert(&BB->getParent()->front() != BB && "Can't Simplify entry block!"); 917 918 // Remove basic blocks that have no predecessors... which are unreachable. 919 if (pred_begin(BB) == pred_end(BB) || 920 *pred_begin(BB) == BB && ++pred_begin(BB) == pred_end(BB)) { 921 DEBUG(std::cerr << "Removing BB: \n" << *BB); 922 923 // Loop through all of our successors and make sure they know that one 924 // of their predecessors is going away. 925 for (succ_iterator SI = succ_begin(BB), E = succ_end(BB); SI != E; ++SI) 926 SI->removePredecessor(BB); 927 928 while (!BB->empty()) { 929 Instruction &I = BB->back(); 930 // If this instruction is used, replace uses with an arbitrary 931 // value. Because control flow can't get here, we don't care 932 // what we replace the value with. Note that since this block is 933 // unreachable, and all values contained within it must dominate their 934 // uses, that all uses will eventually be removed. 935 if (!I.use_empty()) 936 // Make all users of this instruction use undef instead 937 I.replaceAllUsesWith(UndefValue::get(I.getType())); 938 939 // Remove the instruction from the basic block 940 BB->getInstList().pop_back(); 941 } 942 M->getBasicBlockList().erase(BB); 943 return true; 944 } 945 946 // Check to see if we can constant propagate this terminator instruction 947 // away... 948 Changed |= ConstantFoldTerminator(BB); 949 950 // If this is a returning block with only PHI nodes in it, fold the return 951 // instruction into any unconditional branch predecessors. 952 // 953 // If any predecessor is a conditional branch that just selects among 954 // different return values, fold the replace the branch/return with a select 955 // and return. 956 if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) { 957 BasicBlock::iterator BBI = BB->getTerminator(); 958 if (BBI == BB->begin() || isa<PHINode>(--BBI)) { 959 // Find predecessors that end with branches. 960 std::vector<BasicBlock*> UncondBranchPreds; 961 std::vector<BranchInst*> CondBranchPreds; 962 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { 963 TerminatorInst *PTI = (*PI)->getTerminator(); 964 if (BranchInst *BI = dyn_cast<BranchInst>(PTI)) 965 if (BI->isUnconditional()) 966 UncondBranchPreds.push_back(*PI); 967 else 968 CondBranchPreds.push_back(BI); 969 } 970 971 // If we found some, do the transformation! 972 if (!UncondBranchPreds.empty()) { 973 while (!UncondBranchPreds.empty()) { 974 BasicBlock *Pred = UncondBranchPreds.back(); 975 UncondBranchPreds.pop_back(); 976 Instruction *UncondBranch = Pred->getTerminator(); 977 // Clone the return and add it to the end of the predecessor. 978 Instruction *NewRet = RI->clone(); 979 Pred->getInstList().push_back(NewRet); 980 981 // If the return instruction returns a value, and if the value was a 982 // PHI node in "BB", propagate the right value into the return. 983 if (NewRet->getNumOperands() == 1) 984 if (PHINode *PN = dyn_cast<PHINode>(NewRet->getOperand(0))) 985 if (PN->getParent() == BB) 986 NewRet->setOperand(0, PN->getIncomingValueForBlock(Pred)); 987 // Update any PHI nodes in the returning block to realize that we no 988 // longer branch to them. 989 BB->removePredecessor(Pred); 990 Pred->getInstList().erase(UncondBranch); 991 } 992 993 // If we eliminated all predecessors of the block, delete the block now. 994 if (pred_begin(BB) == pred_end(BB)) 995 // We know there are no successors, so just nuke the block. 996 M->getBasicBlockList().erase(BB); 997 998 return true; 999 } 1000 1001 // Check out all of the conditional branches going to this return 1002 // instruction. If any of them just select between returns, change the 1003 // branch itself into a select/return pair. 1004 while (!CondBranchPreds.empty()) { 1005 BranchInst *BI = CondBranchPreds.back(); 1006 CondBranchPreds.pop_back(); 1007 BasicBlock *TrueSucc = BI->getSuccessor(0); 1008 BasicBlock *FalseSucc = BI->getSuccessor(1); 1009 BasicBlock *OtherSucc = TrueSucc == BB ? FalseSucc : TrueSucc; 1010 1011 // Check to see if the non-BB successor is also a return block. 1012 if (isa<ReturnInst>(OtherSucc->getTerminator())) { 1013 // Check to see if there are only PHI instructions in this block. 1014 BasicBlock::iterator OSI = OtherSucc->getTerminator(); 1015 if (OSI == OtherSucc->begin() || isa<PHINode>(--OSI)) { 1016 // Okay, we found a branch that is going to two return nodes. If 1017 // there is no return value for this function, just change the 1018 // branch into a return. 1019 if (RI->getNumOperands() == 0) { 1020 TrueSucc->removePredecessor(BI->getParent()); 1021 FalseSucc->removePredecessor(BI->getParent()); 1022 new ReturnInst(0, BI); 1023 BI->getParent()->getInstList().erase(BI); 1024 return true; 1025 } 1026 1027 // Otherwise, figure out what the true and false return values are 1028 // so we can insert a new select instruction. 1029 Value *TrueValue = TrueSucc->getTerminator()->getOperand(0); 1030 Value *FalseValue = FalseSucc->getTerminator()->getOperand(0); 1031 1032 // Unwrap any PHI nodes in the return blocks. 1033 if (PHINode *TVPN = dyn_cast<PHINode>(TrueValue)) 1034 if (TVPN->getParent() == TrueSucc) 1035 TrueValue = TVPN->getIncomingValueForBlock(BI->getParent()); 1036 if (PHINode *FVPN = dyn_cast<PHINode>(FalseValue)) 1037 if (FVPN->getParent() == FalseSucc) 1038 FalseValue = FVPN->getIncomingValueForBlock(BI->getParent()); 1039 1040 TrueSucc->removePredecessor(BI->getParent()); 1041 FalseSucc->removePredecessor(BI->getParent()); 1042 1043 // Insert a new select instruction. 1044 Value *NewRetVal; 1045 Value *BrCond = BI->getCondition(); 1046 if (TrueValue != FalseValue) 1047 NewRetVal = new SelectInst(BrCond, TrueValue, 1048 FalseValue, "retval", BI); 1049 else 1050 NewRetVal = TrueValue; 1051 1052 new ReturnInst(NewRetVal, BI); 1053 BI->getParent()->getInstList().erase(BI); 1054 if (BrCond->use_empty()) 1055 if (Instruction *BrCondI = dyn_cast<Instruction>(BrCond)) 1056 BrCondI->getParent()->getInstList().erase(BrCondI); 1057 return true; 1058 } 1059 } 1060 } 1061 } 1062 } else if (UnwindInst *UI = dyn_cast<UnwindInst>(BB->begin())) { 1063 // Check to see if the first instruction in this block is just an unwind. 1064 // If so, replace any invoke instructions which use this as an exception 1065 // destination with call instructions, and any unconditional branch 1066 // predecessor with an unwind. 1067 // 1068 std::vector<BasicBlock*> Preds(pred_begin(BB), pred_end(BB)); 1069 while (!Preds.empty()) { 1070 BasicBlock *Pred = Preds.back(); 1071 if (BranchInst *BI = dyn_cast<BranchInst>(Pred->getTerminator())) { 1072 if (BI->isUnconditional()) { 1073 Pred->getInstList().pop_back(); // nuke uncond branch 1074 new UnwindInst(Pred); // Use unwind. 1075 Changed = true; 1076 } 1077 } else if (InvokeInst *II = dyn_cast<InvokeInst>(Pred->getTerminator())) 1078 if (II->getUnwindDest() == BB) { 1079 // Insert a new branch instruction before the invoke, because this 1080 // is now a fall through... 1081 BranchInst *BI = new BranchInst(II->getNormalDest(), II); 1082 Pred->getInstList().remove(II); // Take out of symbol table 1083 1084 // Insert the call now... 1085 std::vector<Value*> Args(II->op_begin()+3, II->op_end()); 1086 CallInst *CI = new CallInst(II->getCalledValue(), Args, 1087 II->getName(), BI); 1088 CI->setCallingConv(II->getCallingConv()); 1089 // If the invoke produced a value, the Call now does instead 1090 II->replaceAllUsesWith(CI); 1091 delete II; 1092 Changed = true; 1093 } 1094 1095 Preds.pop_back(); 1096 } 1097 1098 // If this block is now dead, remove it. 1099 if (pred_begin(BB) == pred_end(BB)) { 1100 // We know there are no successors, so just nuke the block. 1101 M->getBasicBlockList().erase(BB); 1102 return true; 1103 } 1104 1105 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(BB->getTerminator())) { 1106 if (isValueEqualityComparison(SI)) { 1107 // If we only have one predecessor, and if it is a branch on this value, 1108 // see if that predecessor totally determines the outcome of this switch. 1109 if (BasicBlock *OnlyPred = BB->getSinglePredecessor()) 1110 if (SimplifyEqualityComparisonWithOnlyPredecessor(SI, OnlyPred)) 1111 return SimplifyCFG(BB) || 1; 1112 1113 // If the block only contains the switch, see if we can fold the block 1114 // away into any preds. 1115 if (SI == &BB->front()) 1116 if (FoldValueComparisonIntoPredecessors(SI)) 1117 return SimplifyCFG(BB) || 1; 1118 } 1119 } else if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator())) { 1120 if (BI->isUnconditional()) { 1121 BasicBlock::iterator BBI = BB->begin(); // Skip over phi nodes... 1122 while (isa<PHINode>(*BBI)) ++BBI; 1123 1124 BasicBlock *Succ = BI->getSuccessor(0); 1125 if (BBI->isTerminator() && // Terminator is the only non-phi instruction! 1126 Succ != BB) // Don't hurt infinite loops! 1127 if (TryToSimplifyUncondBranchFromEmptyBlock(BB, Succ)) 1128 return 1; 1129 1130 } else { // Conditional branch 1131 if (Value *CompVal = isValueEqualityComparison(BI)) { 1132 // If we only have one predecessor, and if it is a branch on this value, 1133 // see if that predecessor totally determines the outcome of this 1134 // switch. 1135 if (BasicBlock *OnlyPred = BB->getSinglePredecessor()) 1136 if (SimplifyEqualityComparisonWithOnlyPredecessor(BI, OnlyPred)) 1137 return SimplifyCFG(BB) || 1; 1138 1139 // This block must be empty, except for the setcond inst, if it exists. 1140 BasicBlock::iterator I = BB->begin(); 1141 if (&*I == BI || 1142 (&*I == cast<Instruction>(BI->getCondition()) && 1143 &*++I == BI)) 1144 if (FoldValueComparisonIntoPredecessors(BI)) 1145 return SimplifyCFG(BB) | true; 1146 } 1147 1148 // If this basic block is ONLY a setcc and a branch, and if a predecessor 1149 // branches to us and one of our successors, fold the setcc into the 1150 // predecessor and use logical operations to pick the right destination. 1151 BasicBlock *TrueDest = BI->getSuccessor(0); 1152 BasicBlock *FalseDest = BI->getSuccessor(1); 1153 if (BinaryOperator *Cond = dyn_cast<BinaryOperator>(BI->getCondition())) 1154 if (Cond->getParent() == BB && &BB->front() == Cond && 1155 Cond->getNext() == BI && Cond->hasOneUse() && 1156 TrueDest != BB && FalseDest != BB) 1157 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI!=E; ++PI) 1158 if (BranchInst *PBI = dyn_cast<BranchInst>((*PI)->getTerminator())) 1159 if (PBI->isConditional() && SafeToMergeTerminators(BI, PBI)) { 1160 BasicBlock *PredBlock = *PI; 1161 if (PBI->getSuccessor(0) == FalseDest || 1162 PBI->getSuccessor(1) == TrueDest) { 1163 // Invert the predecessors condition test (xor it with true), 1164 // which allows us to write this code once. 1165 Value *NewCond = 1166 BinaryOperator::createNot(PBI->getCondition(), 1167 PBI->getCondition()->getName()+".not", PBI); 1168 PBI->setCondition(NewCond); 1169 BasicBlock *OldTrue = PBI->getSuccessor(0); 1170 BasicBlock *OldFalse = PBI->getSuccessor(1); 1171 PBI->setSuccessor(0, OldFalse); 1172 PBI->setSuccessor(1, OldTrue); 1173 } 1174 1175 if (PBI->getSuccessor(0) == TrueDest || 1176 PBI->getSuccessor(1) == FalseDest) { 1177 // Clone Cond into the predecessor basic block, and or/and the 1178 // two conditions together. 1179 Instruction *New = Cond->clone(); 1180 New->setName(Cond->getName()); 1181 Cond->setName(Cond->getName()+".old"); 1182 PredBlock->getInstList().insert(PBI, New); 1183 Instruction::BinaryOps Opcode = 1184 PBI->getSuccessor(0) == TrueDest ? 1185 Instruction::Or : Instruction::And; 1186 Value *NewCond = 1187 BinaryOperator::create(Opcode, PBI->getCondition(), 1188 New, "bothcond", PBI); 1189 PBI->setCondition(NewCond); 1190 if (PBI->getSuccessor(0) == BB) { 1191 AddPredecessorToBlock(TrueDest, PredBlock, BB); 1192 PBI->setSuccessor(0, TrueDest); 1193 } 1194 if (PBI->getSuccessor(1) == BB) { 1195 AddPredecessorToBlock(FalseDest, PredBlock, BB); 1196 PBI->setSuccessor(1, FalseDest); 1197 } 1198 return SimplifyCFG(BB) | 1; 1199 } 1200 } 1201 1202 // If this block ends with a branch instruction, and if there is one 1203 // predecessor, see if the previous block ended with a branch on the same 1204 // condition, which makes this conditional branch redundant. 1205 if (BasicBlock *OnlyPred = BB->getSinglePredecessor()) 1206 if (BranchInst *PBI = dyn_cast<BranchInst>(OnlyPred->getTerminator())) 1207 if (PBI->isConditional() && 1208 PBI->getCondition() == BI->getCondition() && 1209 (PBI->getSuccessor(0) != BB || PBI->getSuccessor(1) != BB)) { 1210 // Okay, the outcome of this conditional branch is statically 1211 // knowable. Delete the outgoing CFG edge that is impossible to 1212 // execute. 1213 bool CondIsTrue = PBI->getSuccessor(0) == BB; 1214 BI->getSuccessor(CondIsTrue)->removePredecessor(BB); 1215 new BranchInst(BI->getSuccessor(!CondIsTrue), BB); 1216 BB->getInstList().erase(BI); 1217 return SimplifyCFG(BB) | true; 1218 } 1219 } 1220 } else if (isa<UnreachableInst>(BB->getTerminator())) { 1221 // If there are any instructions immediately before the unreachable that can 1222 // be removed, do so. 1223 Instruction *Unreachable = BB->getTerminator(); 1224 while (Unreachable != BB->begin()) { 1225 BasicBlock::iterator BBI = Unreachable; 1226 --BBI; 1227 if (isa<CallInst>(BBI)) break; 1228 // Delete this instruction 1229 BB->getInstList().erase(BBI); 1230 Changed = true; 1231 } 1232 1233 // If the unreachable instruction is the first in the block, take a gander 1234 // at all of the predecessors of this instruction, and simplify them. 1235 if (&BB->front() == Unreachable) { 1236 std::vector<BasicBlock*> Preds(pred_begin(BB), pred_end(BB)); 1237 for (unsigned i = 0, e = Preds.size(); i != e; ++i) { 1238 TerminatorInst *TI = Preds[i]->getTerminator(); 1239 1240 if (BranchInst *BI = dyn_cast<BranchInst>(TI)) { 1241 if (BI->isUnconditional()) { 1242 if (BI->getSuccessor(0) == BB) { 1243 new UnreachableInst(TI); 1244 TI->eraseFromParent(); 1245 Changed = true; 1246 } 1247 } else { 1248 if (BI->getSuccessor(0) == BB) { 1249 new BranchInst(BI->getSuccessor(1), BI); 1250 BI->eraseFromParent(); 1251 } else if (BI->getSuccessor(1) == BB) { 1252 new BranchInst(BI->getSuccessor(0), BI); 1253 BI->eraseFromParent(); 1254 Changed = true; 1255 } 1256 } 1257 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 1258 for (unsigned i = 1, e = SI->getNumCases(); i != e; ++i) 1259 if (SI->getSuccessor(i) == BB) { 1260 BB->removePredecessor(SI->getParent()); 1261 SI->removeCase(i); 1262 --i; --e; 1263 Changed = true; 1264 } 1265 // If the default value is unreachable, figure out the most popular 1266 // destination and make it the default. 1267 if (SI->getSuccessor(0) == BB) { 1268 std::map<BasicBlock*, unsigned> Popularity; 1269 for (unsigned i = 1, e = SI->getNumCases(); i != e; ++i) 1270 Popularity[SI->getSuccessor(i)]++; 1271 1272 // Find the most popular block. 1273 unsigned MaxPop = 0; 1274 BasicBlock *MaxBlock = 0; 1275 for (std::map<BasicBlock*, unsigned>::iterator 1276 I = Popularity.begin(), E = Popularity.end(); I != E; ++I) { 1277 if (I->second > MaxPop) { 1278 MaxPop = I->second; 1279 MaxBlock = I->first; 1280 } 1281 } 1282 if (MaxBlock) { 1283 // Make this the new default, allowing us to delete any explicit 1284 // edges to it. 1285 SI->setSuccessor(0, MaxBlock); 1286 Changed = true; 1287 1288 // If MaxBlock has phinodes in it, remove MaxPop-1 entries from 1289 // it. 1290 if (isa<PHINode>(MaxBlock->begin())) 1291 for (unsigned i = 0; i != MaxPop-1; ++i) 1292 MaxBlock->removePredecessor(SI->getParent()); 1293 1294 for (unsigned i = 1, e = SI->getNumCases(); i != e; ++i) 1295 if (SI->getSuccessor(i) == MaxBlock) { 1296 SI->removeCase(i); 1297 --i; --e; 1298 } 1299 } 1300 } 1301 } else if (InvokeInst *II = dyn_cast<InvokeInst>(TI)) { 1302 if (II->getUnwindDest() == BB) { 1303 // Convert the invoke to a call instruction. This would be a good 1304 // place to note that the call does not throw though. 1305 BranchInst *BI = new BranchInst(II->getNormalDest(), II); 1306 II->removeFromParent(); // Take out of symbol table 1307 1308 // Insert the call now... 1309 std::vector<Value*> Args(II->op_begin()+3, II->op_end()); 1310 CallInst *CI = new CallInst(II->getCalledValue(), Args, 1311 II->getName(), BI); 1312 CI->setCallingConv(II->getCallingConv()); 1313 // If the invoke produced a value, the Call does now instead. 1314 II->replaceAllUsesWith(CI); 1315 delete II; 1316 Changed = true; 1317 } 1318 } 1319 } 1320 1321 // If this block is now dead, remove it. 1322 if (pred_begin(BB) == pred_end(BB)) { 1323 // We know there are no successors, so just nuke the block. 1324 M->getBasicBlockList().erase(BB); 1325 return true; 1326 } 1327 } 1328 } 1329 1330 // Merge basic blocks into their predecessor if there is only one distinct 1331 // pred, and if there is only one distinct successor of the predecessor, and 1332 // if there are no PHI nodes. 1333 // 1334 pred_iterator PI(pred_begin(BB)), PE(pred_end(BB)); 1335 BasicBlock *OnlyPred = *PI++; 1336 for (; PI != PE; ++PI) // Search all predecessors, see if they are all same 1337 if (*PI != OnlyPred) { 1338 OnlyPred = 0; // There are multiple different predecessors... 1339 break; 1340 } 1341 1342 BasicBlock *OnlySucc = 0; 1343 if (OnlyPred && OnlyPred != BB && // Don't break self loops 1344 OnlyPred->getTerminator()->getOpcode() != Instruction::Invoke) { 1345 // Check to see if there is only one distinct successor... 1346 succ_iterator SI(succ_begin(OnlyPred)), SE(succ_end(OnlyPred)); 1347 OnlySucc = BB; 1348 for (; SI != SE; ++SI) 1349 if (*SI != OnlySucc) { 1350 OnlySucc = 0; // There are multiple distinct successors! 1351 break; 1352 } 1353 } 1354 1355 if (OnlySucc) { 1356 DEBUG(std::cerr << "Merging: " << *BB << "into: " << *OnlyPred); 1357 TerminatorInst *Term = OnlyPred->getTerminator(); 1358 1359 // Resolve any PHI nodes at the start of the block. They are all 1360 // guaranteed to have exactly one entry if they exist, unless there are 1361 // multiple duplicate (but guaranteed to be equal) entries for the 1362 // incoming edges. This occurs when there are multiple edges from 1363 // OnlyPred to OnlySucc. 1364 // 1365 while (PHINode *PN = dyn_cast<PHINode>(&BB->front())) { 1366 PN->replaceAllUsesWith(PN->getIncomingValue(0)); 1367 BB->getInstList().pop_front(); // Delete the phi node... 1368 } 1369 1370 // Delete the unconditional branch from the predecessor... 1371 OnlyPred->getInstList().pop_back(); 1372 1373 // Move all definitions in the successor to the predecessor... 1374 OnlyPred->getInstList().splice(OnlyPred->end(), BB->getInstList()); 1375 1376 // Make all PHI nodes that referred to BB now refer to Pred as their 1377 // source... 1378 BB->replaceAllUsesWith(OnlyPred); 1379 1380 std::string OldName = BB->getName(); 1381 1382 // Erase basic block from the function... 1383 M->getBasicBlockList().erase(BB); 1384 1385 // Inherit predecessors name if it exists... 1386 if (!OldName.empty() && !OnlyPred->hasName()) 1387 OnlyPred->setName(OldName); 1388 1389 return true; 1390 } 1391 1392 // Otherwise, if this block only has a single predecessor, and if that block 1393 // is a conditional branch, see if we can hoist any code from this block up 1394 // into our predecessor. 1395 if (OnlyPred) 1396 if (BranchInst *BI = dyn_cast<BranchInst>(OnlyPred->getTerminator())) 1397 if (BI->isConditional()) { 1398 // Get the other block. 1399 BasicBlock *OtherBB = BI->getSuccessor(BI->getSuccessor(0) == BB); 1400 PI = pred_begin(OtherBB); 1401 ++PI; 1402 if (PI == pred_end(OtherBB)) { 1403 // We have a conditional branch to two blocks that are only reachable 1404 // from the condbr. We know that the condbr dominates the two blocks, 1405 // so see if there is any identical code in the "then" and "else" 1406 // blocks. If so, we can hoist it up to the branching block. 1407 Changed |= HoistThenElseCodeToIf(BI); 1408 } 1409 } 1410 1411 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) 1412 if (BranchInst *BI = dyn_cast<BranchInst>((*PI)->getTerminator())) 1413 // Change br (X == 0 | X == 1), T, F into a switch instruction. 1414 if (BI->isConditional() && isa<Instruction>(BI->getCondition())) { 1415 Instruction *Cond = cast<Instruction>(BI->getCondition()); 1416 // If this is a bunch of seteq's or'd together, or if it's a bunch of 1417 // 'setne's and'ed together, collect them. 1418 Value *CompVal = 0; 1419 std::vector<ConstantInt*> Values; 1420 bool TrueWhenEqual = GatherValueComparisons(Cond, CompVal, Values); 1421 if (CompVal && CompVal->getType()->isInteger()) { 1422 // There might be duplicate constants in the list, which the switch 1423 // instruction can't handle, remove them now. 1424 std::sort(Values.begin(), Values.end(), ConstantIntOrdering()); 1425 Values.erase(std::unique(Values.begin(), Values.end()), Values.end()); 1426 1427 // Figure out which block is which destination. 1428 BasicBlock *DefaultBB = BI->getSuccessor(1); 1429 BasicBlock *EdgeBB = BI->getSuccessor(0); 1430 if (!TrueWhenEqual) std::swap(DefaultBB, EdgeBB); 1431 1432 // Create the new switch instruction now. 1433 SwitchInst *New = new SwitchInst(CompVal, DefaultBB,Values.size(),BI); 1434 1435 // Add all of the 'cases' to the switch instruction. 1436 for (unsigned i = 0, e = Values.size(); i != e; ++i) 1437 New->addCase(Values[i], EdgeBB); 1438 1439 // We added edges from PI to the EdgeBB. As such, if there were any 1440 // PHI nodes in EdgeBB, they need entries to be added corresponding to 1441 // the number of edges added. 1442 for (BasicBlock::iterator BBI = EdgeBB->begin(); 1443 isa<PHINode>(BBI); ++BBI) { 1444 PHINode *PN = cast<PHINode>(BBI); 1445 Value *InVal = PN->getIncomingValueForBlock(*PI); 1446 for (unsigned i = 0, e = Values.size()-1; i != e; ++i) 1447 PN->addIncoming(InVal, *PI); 1448 } 1449 1450 // Erase the old branch instruction. 1451 (*PI)->getInstList().erase(BI); 1452 1453 // Erase the potentially condition tree that was used to computed the 1454 // branch condition. 1455 ErasePossiblyDeadInstructionTree(Cond); 1456 return true; 1457 } 1458 } 1459 1460 // If there is a trivial two-entry PHI node in this basic block, and we can 1461 // eliminate it, do so now. 1462 if (PHINode *PN = dyn_cast<PHINode>(BB->begin())) 1463 if (PN->getNumIncomingValues() == 2) { 1464 // Ok, this is a two entry PHI node. Check to see if this is a simple "if 1465 // statement", which has a very simple dominance structure. Basically, we 1466 // are trying to find the condition that is being branched on, which 1467 // subsequently causes this merge to happen. We really want control 1468 // dependence information for this check, but simplifycfg can't keep it up 1469 // to date, and this catches most of the cases we care about anyway. 1470 // 1471 BasicBlock *IfTrue, *IfFalse; 1472 if (Value *IfCond = GetIfCondition(BB, IfTrue, IfFalse)) { 1473 DEBUG(std::cerr << "FOUND IF CONDITION! " << *IfCond << " T: " 1474 << IfTrue->getName() << " F: " << IfFalse->getName() << "\n"); 1475 1476 // Loop over the PHI's seeing if we can promote them all to select 1477 // instructions. While we are at it, keep track of the instructions 1478 // that need to be moved to the dominating block. 1479 std::set<Instruction*> AggressiveInsts; 1480 bool CanPromote = true; 1481 1482 BasicBlock::iterator AfterPHIIt = BB->begin(); 1483 while (isa<PHINode>(AfterPHIIt)) { 1484 PHINode *PN = cast<PHINode>(AfterPHIIt++); 1485 if (PN->getIncomingValue(0) == PN->getIncomingValue(1)) { 1486 if (PN->getIncomingValue(0) != PN) 1487 PN->replaceAllUsesWith(PN->getIncomingValue(0)); 1488 else 1489 PN->replaceAllUsesWith(UndefValue::get(PN->getType())); 1490 } else if (!DominatesMergePoint(PN->getIncomingValue(0), BB, 1491 &AggressiveInsts) || 1492 !DominatesMergePoint(PN->getIncomingValue(1), BB, 1493 &AggressiveInsts)) { 1494 CanPromote = false; 1495 break; 1496 } 1497 } 1498 1499 // Did we eliminate all PHI's? 1500 CanPromote |= AfterPHIIt == BB->begin(); 1501 1502 // If we all PHI nodes are promotable, check to make sure that all 1503 // instructions in the predecessor blocks can be promoted as well. If 1504 // not, we won't be able to get rid of the control flow, so it's not 1505 // worth promoting to select instructions. 1506 BasicBlock *DomBlock = 0, *IfBlock1 = 0, *IfBlock2 = 0; 1507 if (CanPromote) { 1508 PN = cast<PHINode>(BB->begin()); 1509 BasicBlock *Pred = PN->getIncomingBlock(0); 1510 if (cast<BranchInst>(Pred->getTerminator())->isUnconditional()) { 1511 IfBlock1 = Pred; 1512 DomBlock = *pred_begin(Pred); 1513 for (BasicBlock::iterator I = Pred->begin(); 1514 !isa<TerminatorInst>(I); ++I) 1515 if (!AggressiveInsts.count(I)) { 1516 // This is not an aggressive instruction that we can promote. 1517 // Because of this, we won't be able to get rid of the control 1518 // flow, so the xform is not worth it. 1519 CanPromote = false; 1520 break; 1521 } 1522 } 1523 1524 Pred = PN->getIncomingBlock(1); 1525 if (CanPromote && 1526 cast<BranchInst>(Pred->getTerminator())->isUnconditional()) { 1527 IfBlock2 = Pred; 1528 DomBlock = *pred_begin(Pred); 1529 for (BasicBlock::iterator I = Pred->begin(); 1530 !isa<TerminatorInst>(I); ++I) 1531 if (!AggressiveInsts.count(I)) { 1532 // This is not an aggressive instruction that we can promote. 1533 // Because of this, we won't be able to get rid of the control 1534 // flow, so the xform is not worth it. 1535 CanPromote = false; 1536 break; 1537 } 1538 } 1539 } 1540 1541 // If we can still promote the PHI nodes after this gauntlet of tests, 1542 // do all of the PHI's now. 1543 if (CanPromote) { 1544 // Move all 'aggressive' instructions, which are defined in the 1545 // conditional parts of the if's up to the dominating block. 1546 if (IfBlock1) { 1547 DomBlock->getInstList().splice(DomBlock->getTerminator(), 1548 IfBlock1->getInstList(), 1549 IfBlock1->begin(), 1550 IfBlock1->getTerminator()); 1551 } 1552 if (IfBlock2) { 1553 DomBlock->getInstList().splice(DomBlock->getTerminator(), 1554 IfBlock2->getInstList(), 1555 IfBlock2->begin(), 1556 IfBlock2->getTerminator()); 1557 } 1558 1559 while (PHINode *PN = dyn_cast<PHINode>(BB->begin())) { 1560 // Change the PHI node into a select instruction. 1561 Value *TrueVal = 1562 PN->getIncomingValue(PN->getIncomingBlock(0) == IfFalse); 1563 Value *FalseVal = 1564 PN->getIncomingValue(PN->getIncomingBlock(0) == IfTrue); 1565 1566 std::string Name = PN->getName(); PN->setName(""); 1567 PN->replaceAllUsesWith(new SelectInst(IfCond, TrueVal, FalseVal, 1568 Name, AfterPHIIt)); 1569 BB->getInstList().erase(PN); 1570 } 1571 Changed = true; 1572 } 1573 } 1574 } 1575 1576 return Changed; 1577} 1578