LLVM API Documentation
00001 //===- SCCP.cpp - Sparse Conditional Constant Propagation -----------------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file implements sparse conditional constant propagation and merging: 00011 // 00012 // Specifically, this: 00013 // * Assumes values are constant unless proven otherwise 00014 // * Assumes BasicBlocks are dead unless proven otherwise 00015 // * Proves values to be constant, and replaces them with constants 00016 // * Proves conditional branches to be unconditional 00017 // 00018 // Notice that: 00019 // * This pass has a habit of making definitions be dead. It is a good idea 00020 // to to run a DCE pass sometime after running this pass. 00021 // 00022 //===----------------------------------------------------------------------===// 00023 00024 #define DEBUG_TYPE "sccp" 00025 #include "llvm/Transforms/Scalar.h" 00026 #include "llvm/Transforms/IPO.h" 00027 #include "llvm/Constants.h" 00028 #include "llvm/DerivedTypes.h" 00029 #include "llvm/Instructions.h" 00030 #include "llvm/Pass.h" 00031 #include "llvm/Support/InstVisitor.h" 00032 #include "llvm/Transforms/Utils/Local.h" 00033 #include "llvm/Support/CallSite.h" 00034 #include "llvm/Support/Debug.h" 00035 #include "llvm/ADT/hash_map" 00036 #include "llvm/ADT/Statistic.h" 00037 #include "llvm/ADT/STLExtras.h" 00038 #include <algorithm> 00039 #include <iostream> 00040 #include <set> 00041 using namespace llvm; 00042 00043 // LatticeVal class - This class represents the different lattice values that an 00044 // instruction may occupy. It is a simple class with value semantics. 00045 // 00046 namespace { 00047 00048 class LatticeVal { 00049 enum { 00050 undefined, // This instruction has no known value 00051 constant, // This instruction has a constant value 00052 overdefined // This instruction has an unknown value 00053 } LatticeValue; // The current lattice position 00054 Constant *ConstantVal; // If Constant value, the current value 00055 public: 00056 inline LatticeVal() : LatticeValue(undefined), ConstantVal(0) {} 00057 00058 // markOverdefined - Return true if this is a new status to be in... 00059 inline bool markOverdefined() { 00060 if (LatticeValue != overdefined) { 00061 LatticeValue = overdefined; 00062 return true; 00063 } 00064 return false; 00065 } 00066 00067 // markConstant - Return true if this is a new status for us... 00068 inline bool markConstant(Constant *V) { 00069 if (LatticeValue != constant) { 00070 LatticeValue = constant; 00071 ConstantVal = V; 00072 return true; 00073 } else { 00074 assert(ConstantVal == V && "Marking constant with different value"); 00075 } 00076 return false; 00077 } 00078 00079 inline bool isUndefined() const { return LatticeValue == undefined; } 00080 inline bool isConstant() const { return LatticeValue == constant; } 00081 inline bool isOverdefined() const { return LatticeValue == overdefined; } 00082 00083 inline Constant *getConstant() const { 00084 assert(isConstant() && "Cannot get the constant of a non-constant!"); 00085 return ConstantVal; 00086 } 00087 }; 00088 00089 } // end anonymous namespace 00090 00091 00092 //===----------------------------------------------------------------------===// 00093 // 00094 /// SCCPSolver - This class is a general purpose solver for Sparse Conditional 00095 /// Constant Propagation. 00096 /// 00097 class SCCPSolver : public InstVisitor<SCCPSolver> { 00098 std::set<BasicBlock*> BBExecutable;// The basic blocks that are executable 00099 hash_map<Value*, LatticeVal> ValueState; // The state each value is in... 00100 00101 /// GlobalValue - If we are tracking any values for the contents of a global 00102 /// variable, we keep a mapping from the constant accessor to the element of 00103 /// the global, to the currently known value. If the value becomes 00104 /// overdefined, it's entry is simply removed from this map. 00105 hash_map<GlobalVariable*, LatticeVal> TrackedGlobals; 00106 00107 /// TrackedFunctionRetVals - If we are tracking arguments into and the return 00108 /// value out of a function, it will have an entry in this map, indicating 00109 /// what the known return value for the function is. 00110 hash_map<Function*, LatticeVal> TrackedFunctionRetVals; 00111 00112 // The reason for two worklists is that overdefined is the lowest state 00113 // on the lattice, and moving things to overdefined as fast as possible 00114 // makes SCCP converge much faster. 00115 // By having a separate worklist, we accomplish this because everything 00116 // possibly overdefined will become overdefined at the soonest possible 00117 // point. 00118 std::vector<Value*> OverdefinedInstWorkList; 00119 std::vector<Value*> InstWorkList; 00120 00121 00122 std::vector<BasicBlock*> BBWorkList; // The BasicBlock work list 00123 00124 /// UsersOfOverdefinedPHIs - Keep track of any users of PHI nodes that are not 00125 /// overdefined, despite the fact that the PHI node is overdefined. 00126 std::multimap<PHINode*, Instruction*> UsersOfOverdefinedPHIs; 00127 00128 /// KnownFeasibleEdges - Entries in this set are edges which have already had 00129 /// PHI nodes retriggered. 00130 typedef std::pair<BasicBlock*,BasicBlock*> Edge; 00131 std::set<Edge> KnownFeasibleEdges; 00132 public: 00133 00134 /// MarkBlockExecutable - This method can be used by clients to mark all of 00135 /// the blocks that are known to be intrinsically live in the processed unit. 00136 void MarkBlockExecutable(BasicBlock *BB) { 00137 DEBUG(std::cerr << "Marking Block Executable: " << BB->getName() << "\n"); 00138 BBExecutable.insert(BB); // Basic block is executable! 00139 BBWorkList.push_back(BB); // Add the block to the work list! 00140 } 00141 00142 /// TrackValueOfGlobalVariable - Clients can use this method to 00143 /// inform the SCCPSolver that it should track loads and stores to the 00144 /// specified global variable if it can. This is only legal to call if 00145 /// performing Interprocedural SCCP. 00146 void TrackValueOfGlobalVariable(GlobalVariable *GV) { 00147 const Type *ElTy = GV->getType()->getElementType(); 00148 if (ElTy->isFirstClassType()) { 00149 LatticeVal &IV = TrackedGlobals[GV]; 00150 if (!isa<UndefValue>(GV->getInitializer())) 00151 IV.markConstant(GV->getInitializer()); 00152 } 00153 } 00154 00155 /// AddTrackedFunction - If the SCCP solver is supposed to track calls into 00156 /// and out of the specified function (which cannot have its address taken), 00157 /// this method must be called. 00158 void AddTrackedFunction(Function *F) { 00159 assert(F->hasInternalLinkage() && "Can only track internal functions!"); 00160 // Add an entry, F -> undef. 00161 TrackedFunctionRetVals[F]; 00162 } 00163 00164 /// Solve - Solve for constants and executable blocks. 00165 /// 00166 void Solve(); 00167 00168 /// ResolveBranchesIn - While solving the dataflow for a function, we assume 00169 /// that branches on undef values cannot reach any of their successors. 00170 /// However, this is not a safe assumption. After we solve dataflow, this 00171 /// method should be use to handle this. If this returns true, the solver 00172 /// should be rerun. 00173 bool ResolveBranchesIn(Function &F); 00174 00175 /// getExecutableBlocks - Once we have solved for constants, return the set of 00176 /// blocks that is known to be executable. 00177 std::set<BasicBlock*> &getExecutableBlocks() { 00178 return BBExecutable; 00179 } 00180 00181 /// getValueMapping - Once we have solved for constants, return the mapping of 00182 /// LLVM values to LatticeVals. 00183 hash_map<Value*, LatticeVal> &getValueMapping() { 00184 return ValueState; 00185 } 00186 00187 /// getTrackedFunctionRetVals - Get the inferred return value map. 00188 /// 00189 const hash_map<Function*, LatticeVal> &getTrackedFunctionRetVals() { 00190 return TrackedFunctionRetVals; 00191 } 00192 00193 /// getTrackedGlobals - Get and return the set of inferred initializers for 00194 /// global variables. 00195 const hash_map<GlobalVariable*, LatticeVal> &getTrackedGlobals() { 00196 return TrackedGlobals; 00197 } 00198 00199 00200 private: 00201 // markConstant - Make a value be marked as "constant". If the value 00202 // is not already a constant, add it to the instruction work list so that 00203 // the users of the instruction are updated later. 00204 // 00205 inline void markConstant(LatticeVal &IV, Value *V, Constant *C) { 00206 if (IV.markConstant(C)) { 00207 DEBUG(std::cerr << "markConstant: " << *C << ": " << *V); 00208 InstWorkList.push_back(V); 00209 } 00210 } 00211 inline void markConstant(Value *V, Constant *C) { 00212 markConstant(ValueState[V], V, C); 00213 } 00214 00215 // markOverdefined - Make a value be marked as "overdefined". If the 00216 // value is not already overdefined, add it to the overdefined instruction 00217 // work list so that the users of the instruction are updated later. 00218 00219 inline void markOverdefined(LatticeVal &IV, Value *V) { 00220 if (IV.markOverdefined()) { 00221 DEBUG(std::cerr << "markOverdefined: "; 00222 if (Function *F = dyn_cast<Function>(V)) 00223 std::cerr << "Function '" << F->getName() << "'\n"; 00224 else 00225 std::cerr << *V); 00226 // Only instructions go on the work list 00227 OverdefinedInstWorkList.push_back(V); 00228 } 00229 } 00230 inline void markOverdefined(Value *V) { 00231 markOverdefined(ValueState[V], V); 00232 } 00233 00234 inline void mergeInValue(LatticeVal &IV, Value *V, LatticeVal &MergeWithV) { 00235 if (IV.isOverdefined() || MergeWithV.isUndefined()) 00236 return; // Noop. 00237 if (MergeWithV.isOverdefined()) 00238 markOverdefined(IV, V); 00239 else if (IV.isUndefined()) 00240 markConstant(IV, V, MergeWithV.getConstant()); 00241 else if (IV.getConstant() != MergeWithV.getConstant()) 00242 markOverdefined(IV, V); 00243 } 00244 00245 inline void mergeInValue(Value *V, LatticeVal &MergeWithV) { 00246 return mergeInValue(ValueState[V], V, MergeWithV); 00247 } 00248 00249 00250 // getValueState - Return the LatticeVal object that corresponds to the value. 00251 // This function is necessary because not all values should start out in the 00252 // underdefined state... Argument's should be overdefined, and 00253 // constants should be marked as constants. If a value is not known to be an 00254 // Instruction object, then use this accessor to get its value from the map. 00255 // 00256 inline LatticeVal &getValueState(Value *V) { 00257 hash_map<Value*, LatticeVal>::iterator I = ValueState.find(V); 00258 if (I != ValueState.end()) return I->second; // Common case, in the map 00259 00260 if (Constant *CPV = dyn_cast<Constant>(V)) { 00261 if (isa<UndefValue>(V)) { 00262 // Nothing to do, remain undefined. 00263 } else { 00264 ValueState[CPV].markConstant(CPV); // Constants are constant 00265 } 00266 } 00267 // All others are underdefined by default... 00268 return ValueState[V]; 00269 } 00270 00271 // markEdgeExecutable - Mark a basic block as executable, adding it to the BB 00272 // work list if it is not already executable... 00273 // 00274 void markEdgeExecutable(BasicBlock *Source, BasicBlock *Dest) { 00275 if (!KnownFeasibleEdges.insert(Edge(Source, Dest)).second) 00276 return; // This edge is already known to be executable! 00277 00278 if (BBExecutable.count(Dest)) { 00279 DEBUG(std::cerr << "Marking Edge Executable: " << Source->getName() 00280 << " -> " << Dest->getName() << "\n"); 00281 00282 // The destination is already executable, but we just made an edge 00283 // feasible that wasn't before. Revisit the PHI nodes in the block 00284 // because they have potentially new operands. 00285 for (BasicBlock::iterator I = Dest->begin(); isa<PHINode>(I); ++I) 00286 visitPHINode(*cast<PHINode>(I)); 00287 00288 } else { 00289 MarkBlockExecutable(Dest); 00290 } 00291 } 00292 00293 // getFeasibleSuccessors - Return a vector of booleans to indicate which 00294 // successors are reachable from a given terminator instruction. 00295 // 00296 void getFeasibleSuccessors(TerminatorInst &TI, std::vector<bool> &Succs); 00297 00298 // isEdgeFeasible - Return true if the control flow edge from the 'From' basic 00299 // block to the 'To' basic block is currently feasible... 00300 // 00301 bool isEdgeFeasible(BasicBlock *From, BasicBlock *To); 00302 00303 // OperandChangedState - This method is invoked on all of the users of an 00304 // instruction that was just changed state somehow.... Based on this 00305 // information, we need to update the specified user of this instruction. 00306 // 00307 void OperandChangedState(User *U) { 00308 // Only instructions use other variable values! 00309 Instruction &I = cast<Instruction>(*U); 00310 if (BBExecutable.count(I.getParent())) // Inst is executable? 00311 visit(I); 00312 } 00313 00314 private: 00315 friend class InstVisitor<SCCPSolver>; 00316 00317 // visit implementations - Something changed in this instruction... Either an 00318 // operand made a transition, or the instruction is newly executable. Change 00319 // the value type of I to reflect these changes if appropriate. 00320 // 00321 void visitPHINode(PHINode &I); 00322 00323 // Terminators 00324 void visitReturnInst(ReturnInst &I); 00325 void visitTerminatorInst(TerminatorInst &TI); 00326 00327 void visitCastInst(CastInst &I); 00328 void visitSelectInst(SelectInst &I); 00329 void visitBinaryOperator(Instruction &I); 00330 void visitShiftInst(ShiftInst &I) { visitBinaryOperator(I); } 00331 void visitExtractElementInst(ExtractElementInst &I); 00332 void visitInsertElementInst(InsertElementInst &I); 00333 void visitShuffleVectorInst(ShuffleVectorInst &I); 00334 00335 // Instructions that cannot be folded away... 00336 void visitStoreInst (Instruction &I); 00337 void visitLoadInst (LoadInst &I); 00338 void visitGetElementPtrInst(GetElementPtrInst &I); 00339 void visitCallInst (CallInst &I) { visitCallSite(CallSite::get(&I)); } 00340 void visitInvokeInst (InvokeInst &II) { 00341 visitCallSite(CallSite::get(&II)); 00342 visitTerminatorInst(II); 00343 } 00344 void visitCallSite (CallSite CS); 00345 void visitUnwindInst (TerminatorInst &I) { /*returns void*/ } 00346 void visitUnreachableInst(TerminatorInst &I) { /*returns void*/ } 00347 void visitAllocationInst(Instruction &I) { markOverdefined(&I); } 00348 void visitVANextInst (Instruction &I) { markOverdefined(&I); } 00349 void visitVAArgInst (Instruction &I) { markOverdefined(&I); } 00350 void visitFreeInst (Instruction &I) { /*returns void*/ } 00351 00352 void visitInstruction(Instruction &I) { 00353 // If a new instruction is added to LLVM that we don't handle... 00354 std::cerr << "SCCP: Don't know how to handle: " << I; 00355 markOverdefined(&I); // Just in case 00356 } 00357 }; 00358 00359 // getFeasibleSuccessors - Return a vector of booleans to indicate which 00360 // successors are reachable from a given terminator instruction. 00361 // 00362 void SCCPSolver::getFeasibleSuccessors(TerminatorInst &TI, 00363 std::vector<bool> &Succs) { 00364 Succs.resize(TI.getNumSuccessors()); 00365 if (BranchInst *BI = dyn_cast<BranchInst>(&TI)) { 00366 if (BI->isUnconditional()) { 00367 Succs[0] = true; 00368 } else { 00369 LatticeVal &BCValue = getValueState(BI->getCondition()); 00370 if (BCValue.isOverdefined() || 00371 (BCValue.isConstant() && !isa<ConstantBool>(BCValue.getConstant()))) { 00372 // Overdefined condition variables, and branches on unfoldable constant 00373 // conditions, mean the branch could go either way. 00374 Succs[0] = Succs[1] = true; 00375 } else if (BCValue.isConstant()) { 00376 // Constant condition variables mean the branch can only go a single way 00377 Succs[BCValue.getConstant() == ConstantBool::False] = true; 00378 } 00379 } 00380 } else if (InvokeInst *II = dyn_cast<InvokeInst>(&TI)) { 00381 // Invoke instructions successors are always executable. 00382 Succs[0] = Succs[1] = true; 00383 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(&TI)) { 00384 LatticeVal &SCValue = getValueState(SI->getCondition()); 00385 if (SCValue.isOverdefined() || // Overdefined condition? 00386 (SCValue.isConstant() && !isa<ConstantInt>(SCValue.getConstant()))) { 00387 // All destinations are executable! 00388 Succs.assign(TI.getNumSuccessors(), true); 00389 } else if (SCValue.isConstant()) { 00390 Constant *CPV = SCValue.getConstant(); 00391 // Make sure to skip the "default value" which isn't a value 00392 for (unsigned i = 1, E = SI->getNumSuccessors(); i != E; ++i) { 00393 if (SI->getSuccessorValue(i) == CPV) {// Found the right branch... 00394 Succs[i] = true; 00395 return; 00396 } 00397 } 00398 00399 // Constant value not equal to any of the branches... must execute 00400 // default branch then... 00401 Succs[0] = true; 00402 } 00403 } else { 00404 std::cerr << "SCCP: Don't know how to handle: " << TI; 00405 Succs.assign(TI.getNumSuccessors(), true); 00406 } 00407 } 00408 00409 00410 // isEdgeFeasible - Return true if the control flow edge from the 'From' basic 00411 // block to the 'To' basic block is currently feasible... 00412 // 00413 bool SCCPSolver::isEdgeFeasible(BasicBlock *From, BasicBlock *To) { 00414 assert(BBExecutable.count(To) && "Dest should always be alive!"); 00415 00416 // Make sure the source basic block is executable!! 00417 if (!BBExecutable.count(From)) return false; 00418 00419 // Check to make sure this edge itself is actually feasible now... 00420 TerminatorInst *TI = From->getTerminator(); 00421 if (BranchInst *BI = dyn_cast<BranchInst>(TI)) { 00422 if (BI->isUnconditional()) 00423 return true; 00424 else { 00425 LatticeVal &BCValue = getValueState(BI->getCondition()); 00426 if (BCValue.isOverdefined()) { 00427 // Overdefined condition variables mean the branch could go either way. 00428 return true; 00429 } else if (BCValue.isConstant()) { 00430 // Not branching on an evaluatable constant? 00431 if (!isa<ConstantBool>(BCValue.getConstant())) return true; 00432 00433 // Constant condition variables mean the branch can only go a single way 00434 return BI->getSuccessor(BCValue.getConstant() == 00435 ConstantBool::False) == To; 00436 } 00437 return false; 00438 } 00439 } else if (InvokeInst *II = dyn_cast<InvokeInst>(TI)) { 00440 // Invoke instructions successors are always executable. 00441 return true; 00442 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 00443 LatticeVal &SCValue = getValueState(SI->getCondition()); 00444 if (SCValue.isOverdefined()) { // Overdefined condition? 00445 // All destinations are executable! 00446 return true; 00447 } else if (SCValue.isConstant()) { 00448 Constant *CPV = SCValue.getConstant(); 00449 if (!isa<ConstantInt>(CPV)) 00450 return true; // not a foldable constant? 00451 00452 // Make sure to skip the "default value" which isn't a value 00453 for (unsigned i = 1, E = SI->getNumSuccessors(); i != E; ++i) 00454 if (SI->getSuccessorValue(i) == CPV) // Found the taken branch... 00455 return SI->getSuccessor(i) == To; 00456 00457 // Constant value not equal to any of the branches... must execute 00458 // default branch then... 00459 return SI->getDefaultDest() == To; 00460 } 00461 return false; 00462 } else { 00463 std::cerr << "Unknown terminator instruction: " << *TI; 00464 abort(); 00465 } 00466 } 00467 00468 // visit Implementations - Something changed in this instruction... Either an 00469 // operand made a transition, or the instruction is newly executable. Change 00470 // the value type of I to reflect these changes if appropriate. This method 00471 // makes sure to do the following actions: 00472 // 00473 // 1. If a phi node merges two constants in, and has conflicting value coming 00474 // from different branches, or if the PHI node merges in an overdefined 00475 // value, then the PHI node becomes overdefined. 00476 // 2. If a phi node merges only constants in, and they all agree on value, the 00477 // PHI node becomes a constant value equal to that. 00478 // 3. If V <- x (op) y && isConstant(x) && isConstant(y) V = Constant 00479 // 4. If V <- x (op) y && (isOverdefined(x) || isOverdefined(y)) V = Overdefined 00480 // 5. If V <- MEM or V <- CALL or V <- (unknown) then V = Overdefined 00481 // 6. If a conditional branch has a value that is constant, make the selected 00482 // destination executable 00483 // 7. If a conditional branch has a value that is overdefined, make all 00484 // successors executable. 00485 // 00486 void SCCPSolver::visitPHINode(PHINode &PN) { 00487 LatticeVal &PNIV = getValueState(&PN); 00488 if (PNIV.isOverdefined()) { 00489 // There may be instructions using this PHI node that are not overdefined 00490 // themselves. If so, make sure that they know that the PHI node operand 00491 // changed. 00492 std::multimap<PHINode*, Instruction*>::iterator I, E; 00493 tie(I, E) = UsersOfOverdefinedPHIs.equal_range(&PN); 00494 if (I != E) { 00495 std::vector<Instruction*> Users; 00496 Users.reserve(std::distance(I, E)); 00497 for (; I != E; ++I) Users.push_back(I->second); 00498 while (!Users.empty()) { 00499 visit(Users.back()); 00500 Users.pop_back(); 00501 } 00502 } 00503 return; // Quick exit 00504 } 00505 00506 // Super-extra-high-degree PHI nodes are unlikely to ever be marked constant, 00507 // and slow us down a lot. Just mark them overdefined. 00508 if (PN.getNumIncomingValues() > 64) { 00509 markOverdefined(PNIV, &PN); 00510 return; 00511 } 00512 00513 // Look at all of the executable operands of the PHI node. If any of them 00514 // are overdefined, the PHI becomes overdefined as well. If they are all 00515 // constant, and they agree with each other, the PHI becomes the identical 00516 // constant. If they are constant and don't agree, the PHI is overdefined. 00517 // If there are no executable operands, the PHI remains undefined. 00518 // 00519 Constant *OperandVal = 0; 00520 for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) { 00521 LatticeVal &IV = getValueState(PN.getIncomingValue(i)); 00522 if (IV.isUndefined()) continue; // Doesn't influence PHI node. 00523 00524 if (isEdgeFeasible(PN.getIncomingBlock(i), PN.getParent())) { 00525 if (IV.isOverdefined()) { // PHI node becomes overdefined! 00526 markOverdefined(PNIV, &PN); 00527 return; 00528 } 00529 00530 if (OperandVal == 0) { // Grab the first value... 00531 OperandVal = IV.getConstant(); 00532 } else { // Another value is being merged in! 00533 // There is already a reachable operand. If we conflict with it, 00534 // then the PHI node becomes overdefined. If we agree with it, we 00535 // can continue on. 00536 00537 // Check to see if there are two different constants merging... 00538 if (IV.getConstant() != OperandVal) { 00539 // Yes there is. This means the PHI node is not constant. 00540 // You must be overdefined poor PHI. 00541 // 00542 markOverdefined(PNIV, &PN); // The PHI node now becomes overdefined 00543 return; // I'm done analyzing you 00544 } 00545 } 00546 } 00547 } 00548 00549 // If we exited the loop, this means that the PHI node only has constant 00550 // arguments that agree with each other(and OperandVal is the constant) or 00551 // OperandVal is null because there are no defined incoming arguments. If 00552 // this is the case, the PHI remains undefined. 00553 // 00554 if (OperandVal) 00555 markConstant(PNIV, &PN, OperandVal); // Acquire operand value 00556 } 00557 00558 void SCCPSolver::visitReturnInst(ReturnInst &I) { 00559 if (I.getNumOperands() == 0) return; // Ret void 00560 00561 // If we are tracking the return value of this function, merge it in. 00562 Function *F = I.getParent()->getParent(); 00563 if (F->hasInternalLinkage() && !TrackedFunctionRetVals.empty()) { 00564 hash_map<Function*, LatticeVal>::iterator TFRVI = 00565 TrackedFunctionRetVals.find(F); 00566 if (TFRVI != TrackedFunctionRetVals.end() && 00567 !TFRVI->second.isOverdefined()) { 00568 LatticeVal &IV = getValueState(I.getOperand(0)); 00569 mergeInValue(TFRVI->second, F, IV); 00570 } 00571 } 00572 } 00573 00574 00575 void SCCPSolver::visitTerminatorInst(TerminatorInst &TI) { 00576 std::vector<bool> SuccFeasible; 00577 getFeasibleSuccessors(TI, SuccFeasible); 00578 00579 BasicBlock *BB = TI.getParent(); 00580 00581 // Mark all feasible successors executable... 00582 for (unsigned i = 0, e = SuccFeasible.size(); i != e; ++i) 00583 if (SuccFeasible[i]) 00584 markEdgeExecutable(BB, TI.getSuccessor(i)); 00585 } 00586 00587 void SCCPSolver::visitCastInst(CastInst &I) { 00588 Value *V = I.getOperand(0); 00589 LatticeVal &VState = getValueState(V); 00590 if (VState.isOverdefined()) // Inherit overdefinedness of operand 00591 markOverdefined(&I); 00592 else if (VState.isConstant()) // Propagate constant value 00593 markConstant(&I, ConstantExpr::getCast(VState.getConstant(), I.getType())); 00594 } 00595 00596 void SCCPSolver::visitSelectInst(SelectInst &I) { 00597 LatticeVal &CondValue = getValueState(I.getCondition()); 00598 if (CondValue.isUndefined()) 00599 return; 00600 if (CondValue.isConstant()) { 00601 Value *InVal = 0; 00602 if (CondValue.getConstant() == ConstantBool::True) { 00603 mergeInValue(&I, getValueState(I.getTrueValue())); 00604 return; 00605 } else if (CondValue.getConstant() == ConstantBool::False) { 00606 mergeInValue(&I, getValueState(I.getFalseValue())); 00607 return; 00608 } 00609 } 00610 00611 // Otherwise, the condition is overdefined or a constant we can't evaluate. 00612 // See if we can produce something better than overdefined based on the T/F 00613 // value. 00614 LatticeVal &TVal = getValueState(I.getTrueValue()); 00615 LatticeVal &FVal = getValueState(I.getFalseValue()); 00616 00617 // select ?, C, C -> C. 00618 if (TVal.isConstant() && FVal.isConstant() && 00619 TVal.getConstant() == FVal.getConstant()) { 00620 markConstant(&I, FVal.getConstant()); 00621 return; 00622 } 00623 00624 if (TVal.isUndefined()) { // select ?, undef, X -> X. 00625 mergeInValue(&I, FVal); 00626 } else if (FVal.isUndefined()) { // select ?, X, undef -> X. 00627 mergeInValue(&I, TVal); 00628 } else { 00629 markOverdefined(&I); 00630 } 00631 } 00632 00633 // Handle BinaryOperators and Shift Instructions... 00634 void SCCPSolver::visitBinaryOperator(Instruction &I) { 00635 LatticeVal &IV = ValueState[&I]; 00636 if (IV.isOverdefined()) return; 00637 00638 LatticeVal &V1State = getValueState(I.getOperand(0)); 00639 LatticeVal &V2State = getValueState(I.getOperand(1)); 00640 00641 if (V1State.isOverdefined() || V2State.isOverdefined()) { 00642 // If this is an AND or OR with 0 or -1, it doesn't matter that the other 00643 // operand is overdefined. 00644 if (I.getOpcode() == Instruction::And || I.getOpcode() == Instruction::Or) { 00645 LatticeVal *NonOverdefVal = 0; 00646 if (!V1State.isOverdefined()) { 00647 NonOverdefVal = &V1State; 00648 } else if (!V2State.isOverdefined()) { 00649 NonOverdefVal = &V2State; 00650 } 00651 00652 if (NonOverdefVal) { 00653 if (NonOverdefVal->isUndefined()) { 00654 // Could annihilate value. 00655 if (I.getOpcode() == Instruction::And) 00656 markConstant(IV, &I, Constant::getNullValue(I.getType())); 00657 else 00658 markConstant(IV, &I, ConstantInt::getAllOnesValue(I.getType())); 00659 return; 00660 } else { 00661 if (I.getOpcode() == Instruction::And) { 00662 if (NonOverdefVal->getConstant()->isNullValue()) { 00663 markConstant(IV, &I, NonOverdefVal->getConstant()); 00664 return; // X or 0 = -1 00665 } 00666 } else { 00667 if (ConstantIntegral *CI = 00668 dyn_cast<ConstantIntegral>(NonOverdefVal->getConstant())) 00669 if (CI->isAllOnesValue()) { 00670 markConstant(IV, &I, NonOverdefVal->getConstant()); 00671 return; // X or -1 = -1 00672 } 00673 } 00674 } 00675 } 00676 } 00677 00678 00679 // If both operands are PHI nodes, it is possible that this instruction has 00680 // a constant value, despite the fact that the PHI node doesn't. Check for 00681 // this condition now. 00682 if (PHINode *PN1 = dyn_cast<PHINode>(I.getOperand(0))) 00683 if (PHINode *PN2 = dyn_cast<PHINode>(I.getOperand(1))) 00684 if (PN1->getParent() == PN2->getParent()) { 00685 // Since the two PHI nodes are in the same basic block, they must have 00686 // entries for the same predecessors. Walk the predecessor list, and 00687 // if all of the incoming values are constants, and the result of 00688 // evaluating this expression with all incoming value pairs is the 00689 // same, then this expression is a constant even though the PHI node 00690 // is not a constant! 00691 LatticeVal Result; 00692 for (unsigned i = 0, e = PN1->getNumIncomingValues(); i != e; ++i) { 00693 LatticeVal &In1 = getValueState(PN1->getIncomingValue(i)); 00694 BasicBlock *InBlock = PN1->getIncomingBlock(i); 00695 LatticeVal &In2 = 00696 getValueState(PN2->getIncomingValueForBlock(InBlock)); 00697 00698 if (In1.isOverdefined() || In2.isOverdefined()) { 00699 Result.markOverdefined(); 00700 break; // Cannot fold this operation over the PHI nodes! 00701 } else if (In1.isConstant() && In2.isConstant()) { 00702 Constant *V = ConstantExpr::get(I.getOpcode(), In1.getConstant(), 00703 In2.getConstant()); 00704 if (Result.isUndefined()) 00705 Result.markConstant(V); 00706 else if (Result.isConstant() && Result.getConstant() != V) { 00707 Result.markOverdefined(); 00708 break; 00709 } 00710 } 00711 } 00712 00713 // If we found a constant value here, then we know the instruction is 00714 // constant despite the fact that the PHI nodes are overdefined. 00715 if (Result.isConstant()) { 00716 markConstant(IV, &I, Result.getConstant()); 00717 // Remember that this instruction is virtually using the PHI node 00718 // operands. 00719 UsersOfOverdefinedPHIs.insert(std::make_pair(PN1, &I)); 00720 UsersOfOverdefinedPHIs.insert(std::make_pair(PN2, &I)); 00721 return; 00722 } else if (Result.isUndefined()) { 00723 return; 00724 } 00725 00726 // Okay, this really is overdefined now. Since we might have 00727 // speculatively thought that this was not overdefined before, and 00728 // added ourselves to the UsersOfOverdefinedPHIs list for the PHIs, 00729 // make sure to clean out any entries that we put there, for 00730 // efficiency. 00731 std::multimap<PHINode*, Instruction*>::iterator It, E; 00732 tie(It, E) = UsersOfOverdefinedPHIs.equal_range(PN1); 00733 while (It != E) { 00734 if (It->second == &I) { 00735 UsersOfOverdefinedPHIs.erase(It++); 00736 } else 00737 ++It; 00738 } 00739 tie(It, E) = UsersOfOverdefinedPHIs.equal_range(PN2); 00740 while (It != E) { 00741 if (It->second == &I) { 00742 UsersOfOverdefinedPHIs.erase(It++); 00743 } else 00744 ++It; 00745 } 00746 } 00747 00748 markOverdefined(IV, &I); 00749 } else if (V1State.isConstant() && V2State.isConstant()) { 00750 markConstant(IV, &I, ConstantExpr::get(I.getOpcode(), V1State.getConstant(), 00751 V2State.getConstant())); 00752 } 00753 } 00754 00755 void SCCPSolver::visitExtractElementInst(ExtractElementInst &I) { 00756 LatticeVal &ValState = getValueState(I.getOperand(0)); 00757 LatticeVal &IdxState = getValueState(I.getOperand(1)); 00758 00759 if (ValState.isOverdefined() || IdxState.isOverdefined()) 00760 markOverdefined(&I); 00761 else if(ValState.isConstant() && IdxState.isConstant()) 00762 markConstant(&I, ConstantExpr::getExtractElement(ValState.getConstant(), 00763 IdxState.getConstant())); 00764 } 00765 00766 void SCCPSolver::visitInsertElementInst(InsertElementInst &I) { 00767 LatticeVal &ValState = getValueState(I.getOperand(0)); 00768 LatticeVal &EltState = getValueState(I.getOperand(1)); 00769 LatticeVal &IdxState = getValueState(I.getOperand(2)); 00770 00771 if (ValState.isOverdefined() || EltState.isOverdefined() || 00772 IdxState.isOverdefined()) 00773 markOverdefined(&I); 00774 else if(ValState.isConstant() && EltState.isConstant() && 00775 IdxState.isConstant()) 00776 markConstant(&I, ConstantExpr::getInsertElement(ValState.getConstant(), 00777 EltState.getConstant(), 00778 IdxState.getConstant())); 00779 else if (ValState.isUndefined() && EltState.isConstant() && 00780 IdxState.isConstant()) 00781 markConstant(&I, ConstantExpr::getInsertElement(UndefValue::get(I.getType()), 00782 EltState.getConstant(), 00783 IdxState.getConstant())); 00784 } 00785 00786 void SCCPSolver::visitShuffleVectorInst(ShuffleVectorInst &I) { 00787 LatticeVal &V1State = getValueState(I.getOperand(0)); 00788 LatticeVal &V2State = getValueState(I.getOperand(1)); 00789 LatticeVal &MaskState = getValueState(I.getOperand(2)); 00790 00791 if (MaskState.isUndefined() || 00792 (V1State.isUndefined() && V2State.isUndefined())) 00793 return; // Undefined output if mask or both inputs undefined. 00794 00795 if (V1State.isOverdefined() || V2State.isOverdefined() || 00796 MaskState.isOverdefined()) { 00797 markOverdefined(&I); 00798 } else { 00799 // A mix of constant/undef inputs. 00800 Constant *V1 = V1State.isConstant() ? 00801 V1State.getConstant() : UndefValue::get(I.getType()); 00802 Constant *V2 = V2State.isConstant() ? 00803 V2State.getConstant() : UndefValue::get(I.getType()); 00804 Constant *Mask = MaskState.isConstant() ? 00805 MaskState.getConstant() : UndefValue::get(I.getOperand(2)->getType()); 00806 markConstant(&I, ConstantExpr::getShuffleVector(V1, V2, Mask)); 00807 } 00808 } 00809 00810 // Handle getelementptr instructions... if all operands are constants then we 00811 // can turn this into a getelementptr ConstantExpr. 00812 // 00813 void SCCPSolver::visitGetElementPtrInst(GetElementPtrInst &I) { 00814 LatticeVal &IV = ValueState[&I]; 00815 if (IV.isOverdefined()) return; 00816 00817 std::vector<Constant*> Operands; 00818 Operands.reserve(I.getNumOperands()); 00819 00820 for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) { 00821 LatticeVal &State = getValueState(I.getOperand(i)); 00822 if (State.isUndefined()) 00823 return; // Operands are not resolved yet... 00824 else if (State.isOverdefined()) { 00825 markOverdefined(IV, &I); 00826 return; 00827 } 00828 assert(State.isConstant() && "Unknown state!"); 00829 Operands.push_back(State.getConstant()); 00830 } 00831 00832 Constant *Ptr = Operands[0]; 00833 Operands.erase(Operands.begin()); // Erase the pointer from idx list... 00834 00835 markConstant(IV, &I, ConstantExpr::getGetElementPtr(Ptr, Operands)); 00836 } 00837 00838 void SCCPSolver::visitStoreInst(Instruction &SI) { 00839 if (TrackedGlobals.empty() || !isa<GlobalVariable>(SI.getOperand(1))) 00840 return; 00841 GlobalVariable *GV = cast<GlobalVariable>(SI.getOperand(1)); 00842 hash_map<GlobalVariable*, LatticeVal>::iterator I = TrackedGlobals.find(GV); 00843 if (I == TrackedGlobals.end() || I->second.isOverdefined()) return; 00844 00845 // Get the value we are storing into the global. 00846 LatticeVal &PtrVal = getValueState(SI.getOperand(0)); 00847 00848 mergeInValue(I->second, GV, PtrVal); 00849 if (I->second.isOverdefined()) 00850 TrackedGlobals.erase(I); // No need to keep tracking this! 00851 } 00852 00853 00854 // Handle load instructions. If the operand is a constant pointer to a constant 00855 // global, we can replace the load with the loaded constant value! 00856 void SCCPSolver::visitLoadInst(LoadInst &I) { 00857 LatticeVal &IV = ValueState[&I]; 00858 if (IV.isOverdefined()) return; 00859 00860 LatticeVal &PtrVal = getValueState(I.getOperand(0)); 00861 if (PtrVal.isUndefined()) return; // The pointer is not resolved yet! 00862 if (PtrVal.isConstant() && !I.isVolatile()) { 00863 Value *Ptr = PtrVal.getConstant(); 00864 if (isa<ConstantPointerNull>(Ptr)) { 00865 // load null -> null 00866 markConstant(IV, &I, Constant::getNullValue(I.getType())); 00867 return; 00868 } 00869 00870 // Transform load (constant global) into the value loaded. 00871 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Ptr)) { 00872 if (GV->isConstant()) { 00873 if (!GV->isExternal()) { 00874 markConstant(IV, &I, GV->getInitializer()); 00875 return; 00876 } 00877 } else if (!TrackedGlobals.empty()) { 00878 // If we are tracking this global, merge in the known value for it. 00879 hash_map<GlobalVariable*, LatticeVal>::iterator It = 00880 TrackedGlobals.find(GV); 00881 if (It != TrackedGlobals.end()) { 00882 mergeInValue(IV, &I, It->second); 00883 return; 00884 } 00885 } 00886 } 00887 00888 // Transform load (constantexpr_GEP global, 0, ...) into the value loaded. 00889 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Ptr)) 00890 if (CE->getOpcode() == Instruction::GetElementPtr) 00891 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(CE->getOperand(0))) 00892 if (GV->isConstant() && !GV->isExternal()) 00893 if (Constant *V = 00894 ConstantFoldLoadThroughGEPConstantExpr(GV->getInitializer(), CE)) { 00895 markConstant(IV, &I, V); 00896 return; 00897 } 00898 } 00899 00900 // Otherwise we cannot say for certain what value this load will produce. 00901 // Bail out. 00902 markOverdefined(IV, &I); 00903 } 00904 00905 void SCCPSolver::visitCallSite(CallSite CS) { 00906 Function *F = CS.getCalledFunction(); 00907 00908 // If we are tracking this function, we must make sure to bind arguments as 00909 // appropriate. 00910 hash_map<Function*, LatticeVal>::iterator TFRVI =TrackedFunctionRetVals.end(); 00911 if (F && F->hasInternalLinkage()) 00912 TFRVI = TrackedFunctionRetVals.find(F); 00913 00914 if (TFRVI != TrackedFunctionRetVals.end()) { 00915 // If this is the first call to the function hit, mark its entry block 00916 // executable. 00917 if (!BBExecutable.count(F->begin())) 00918 MarkBlockExecutable(F->begin()); 00919 00920 CallSite::arg_iterator CAI = CS.arg_begin(); 00921 for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end(); 00922 AI != E; ++AI, ++CAI) { 00923 LatticeVal &IV = ValueState[AI]; 00924 if (!IV.isOverdefined()) 00925 mergeInValue(IV, AI, getValueState(*CAI)); 00926 } 00927 } 00928 Instruction *I = CS.getInstruction(); 00929 if (I->getType() == Type::VoidTy) return; 00930 00931 LatticeVal &IV = ValueState[I]; 00932 if (IV.isOverdefined()) return; 00933 00934 // Propagate the return value of the function to the value of the instruction. 00935 if (TFRVI != TrackedFunctionRetVals.end()) { 00936 mergeInValue(IV, I, TFRVI->second); 00937 return; 00938 } 00939 00940 if (F == 0 || !F->isExternal() || !canConstantFoldCallTo(F)) { 00941 markOverdefined(IV, I); 00942 return; 00943 } 00944 00945 std::vector<Constant*> Operands; 00946 Operands.reserve(I->getNumOperands()-1); 00947 00948 for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end(); 00949 AI != E; ++AI) { 00950 LatticeVal &State = getValueState(*AI); 00951 if (State.isUndefined()) 00952 return; // Operands are not resolved yet... 00953 else if (State.isOverdefined()) { 00954 markOverdefined(IV, I); 00955 return; 00956 } 00957 assert(State.isConstant() && "Unknown state!"); 00958 Operands.push_back(State.getConstant()); 00959 } 00960 00961 if (Constant *C = ConstantFoldCall(F, Operands)) 00962 markConstant(IV, I, C); 00963 else 00964 markOverdefined(IV, I); 00965 } 00966 00967 00968 void SCCPSolver::Solve() { 00969 // Process the work lists until they are empty! 00970 while (!BBWorkList.empty() || !InstWorkList.empty() || 00971 !OverdefinedInstWorkList.empty()) { 00972 // Process the instruction work list... 00973 while (!OverdefinedInstWorkList.empty()) { 00974 Value *I = OverdefinedInstWorkList.back(); 00975 OverdefinedInstWorkList.pop_back(); 00976 00977 DEBUG(std::cerr << "\nPopped off OI-WL: " << *I); 00978 00979 // "I" got into the work list because it either made the transition from 00980 // bottom to constant 00981 // 00982 // Anything on this worklist that is overdefined need not be visited 00983 // since all of its users will have already been marked as overdefined 00984 // Update all of the users of this instruction's value... 00985 // 00986 for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); 00987 UI != E; ++UI) 00988 OperandChangedState(*UI); 00989 } 00990 // Process the instruction work list... 00991 while (!InstWorkList.empty()) { 00992 Value *I = InstWorkList.back(); 00993 InstWorkList.pop_back(); 00994 00995 DEBUG(std::cerr << "\nPopped off I-WL: " << *I); 00996 00997 // "I" got into the work list because it either made the transition from 00998 // bottom to constant 00999 // 01000 // Anything on this worklist that is overdefined need not be visited 01001 // since all of its users will have already been marked as overdefined. 01002 // Update all of the users of this instruction's value... 01003 // 01004 if (!getValueState(I).isOverdefined()) 01005 for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); 01006 UI != E; ++UI) 01007 OperandChangedState(*UI); 01008 } 01009 01010 // Process the basic block work list... 01011 while (!BBWorkList.empty()) { 01012 BasicBlock *BB = BBWorkList.back(); 01013 BBWorkList.pop_back(); 01014 01015 DEBUG(std::cerr << "\nPopped off BBWL: " << *BB); 01016 01017 // Notify all instructions in this basic block that they are newly 01018 // executable. 01019 visit(BB); 01020 } 01021 } 01022 } 01023 01024 /// ResolveBranchesIn - While solving the dataflow for a function, we assume 01025 /// that branches on undef values cannot reach any of their successors. 01026 /// However, this is not a safe assumption. After we solve dataflow, this 01027 /// method should be use to handle this. If this returns true, the solver 01028 /// should be rerun. 01029 bool SCCPSolver::ResolveBranchesIn(Function &F) { 01030 bool BranchesResolved = false; 01031 for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) 01032 if (BBExecutable.count(BB)) { 01033 TerminatorInst *TI = BB->getTerminator(); 01034 if (BranchInst *BI = dyn_cast<BranchInst>(TI)) { 01035 if (BI->isConditional()) { 01036 LatticeVal &BCValue = getValueState(BI->getCondition()); 01037 if (BCValue.isUndefined()) { 01038 BI->setCondition(ConstantBool::True); 01039 BranchesResolved = true; 01040 visit(BI); 01041 } 01042 } 01043 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 01044 LatticeVal &SCValue = getValueState(SI->getCondition()); 01045 if (SCValue.isUndefined()) { 01046 const Type *CondTy = SI->getCondition()->getType(); 01047 SI->setCondition(Constant::getNullValue(CondTy)); 01048 BranchesResolved = true; 01049 visit(SI); 01050 } 01051 } 01052 } 01053 01054 return BranchesResolved; 01055 } 01056 01057 01058 namespace { 01059 Statistic<> NumInstRemoved("sccp", "Number of instructions removed"); 01060 Statistic<> NumDeadBlocks ("sccp", "Number of basic blocks unreachable"); 01061 01062 //===--------------------------------------------------------------------===// 01063 // 01064 /// SCCP Class - This class uses the SCCPSolver to implement a per-function 01065 /// Sparse Conditional COnstant Propagator. 01066 /// 01067 struct SCCP : public FunctionPass { 01068 // runOnFunction - Run the Sparse Conditional Constant Propagation 01069 // algorithm, and return true if the function was modified. 01070 // 01071 bool runOnFunction(Function &F); 01072 01073 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 01074 AU.setPreservesCFG(); 01075 } 01076 }; 01077 01078 RegisterOpt<SCCP> X("sccp", "Sparse Conditional Constant Propagation"); 01079 } // end anonymous namespace 01080 01081 01082 // createSCCPPass - This is the public interface to this file... 01083 FunctionPass *llvm::createSCCPPass() { 01084 return new SCCP(); 01085 } 01086 01087 01088 // runOnFunction() - Run the Sparse Conditional Constant Propagation algorithm, 01089 // and return true if the function was modified. 01090 // 01091 bool SCCP::runOnFunction(Function &F) { 01092 DEBUG(std::cerr << "SCCP on function '" << F.getName() << "'\n"); 01093 SCCPSolver Solver; 01094 01095 // Mark the first block of the function as being executable. 01096 Solver.MarkBlockExecutable(F.begin()); 01097 01098 // Mark all arguments to the function as being overdefined. 01099 hash_map<Value*, LatticeVal> &Values = Solver.getValueMapping(); 01100 for (Function::arg_iterator AI = F.arg_begin(), E = F.arg_end(); AI != E; ++AI) 01101 Values[AI].markOverdefined(); 01102 01103 // Solve for constants. 01104 bool ResolvedBranches = true; 01105 while (ResolvedBranches) { 01106 Solver.Solve(); 01107 DEBUG(std::cerr << "RESOLVING UNDEF BRANCHES\n"); 01108 ResolvedBranches = Solver.ResolveBranchesIn(F); 01109 } 01110 01111 bool MadeChanges = false; 01112 01113 // If we decided that there are basic blocks that are dead in this function, 01114 // delete their contents now. Note that we cannot actually delete the blocks, 01115 // as we cannot modify the CFG of the function. 01116 // 01117 std::set<BasicBlock*> &ExecutableBBs = Solver.getExecutableBlocks(); 01118 for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) 01119 if (!ExecutableBBs.count(BB)) { 01120 DEBUG(std::cerr << " BasicBlock Dead:" << *BB); 01121 ++NumDeadBlocks; 01122 01123 // Delete the instructions backwards, as it has a reduced likelihood of 01124 // having to update as many def-use and use-def chains. 01125 std::vector<Instruction*> Insts; 01126 for (BasicBlock::iterator I = BB->begin(), E = BB->getTerminator(); 01127 I != E; ++I) 01128 Insts.push_back(I); 01129 while (!Insts.empty()) { 01130 Instruction *I = Insts.back(); 01131 Insts.pop_back(); 01132 if (!I->use_empty()) 01133 I->replaceAllUsesWith(UndefValue::get(I->getType())); 01134 BB->getInstList().erase(I); 01135 MadeChanges = true; 01136 ++NumInstRemoved; 01137 } 01138 } else { 01139 // Iterate over all of the instructions in a function, replacing them with 01140 // constants if we have found them to be of constant values. 01141 // 01142 for (BasicBlock::iterator BI = BB->begin(), E = BB->end(); BI != E; ) { 01143 Instruction *Inst = BI++; 01144 if (Inst->getType() != Type::VoidTy) { 01145 LatticeVal &IV = Values[Inst]; 01146 if (IV.isConstant() || IV.isUndefined() && 01147 !isa<TerminatorInst>(Inst)) { 01148 Constant *Const = IV.isConstant() 01149 ? IV.getConstant() : UndefValue::get(Inst->getType()); 01150 DEBUG(std::cerr << " Constant: " << *Const << " = " << *Inst); 01151 01152 // Replaces all of the uses of a variable with uses of the constant. 01153 Inst->replaceAllUsesWith(Const); 01154 01155 // Delete the instruction. 01156 BB->getInstList().erase(Inst); 01157 01158 // Hey, we just changed something! 01159 MadeChanges = true; 01160 ++NumInstRemoved; 01161 } 01162 } 01163 } 01164 } 01165 01166 return MadeChanges; 01167 } 01168 01169 namespace { 01170 Statistic<> IPNumInstRemoved("ipsccp", "Number of instructions removed"); 01171 Statistic<> IPNumDeadBlocks ("ipsccp", "Number of basic blocks unreachable"); 01172 Statistic<> IPNumArgsElimed ("ipsccp", 01173 "Number of arguments constant propagated"); 01174 Statistic<> IPNumGlobalConst("ipsccp", 01175 "Number of globals found to be constant"); 01176 01177 //===--------------------------------------------------------------------===// 01178 // 01179 /// IPSCCP Class - This class implements interprocedural Sparse Conditional 01180 /// Constant Propagation. 01181 /// 01182 struct IPSCCP : public ModulePass { 01183 bool runOnModule(Module &M); 01184 }; 01185 01186 RegisterOpt<IPSCCP> 01187 Y("ipsccp", "Interprocedural Sparse Conditional Constant Propagation"); 01188 } // end anonymous namespace 01189 01190 // createIPSCCPPass - This is the public interface to this file... 01191 ModulePass *llvm::createIPSCCPPass() { 01192 return new IPSCCP(); 01193 } 01194 01195 01196 static bool AddressIsTaken(GlobalValue *GV) { 01197 // Delete any dead constantexpr klingons. 01198 GV->removeDeadConstantUsers(); 01199 01200 for (Value::use_iterator UI = GV->use_begin(), E = GV->use_end(); 01201 UI != E; ++UI) 01202 if (StoreInst *SI = dyn_cast<StoreInst>(*UI)) { 01203 if (SI->getOperand(0) == GV || SI->isVolatile()) 01204 return true; // Storing addr of GV. 01205 } else if (isa<InvokeInst>(*UI) || isa<CallInst>(*UI)) { 01206 // Make sure we are calling the function, not passing the address. 01207 CallSite CS = CallSite::get(cast<Instruction>(*UI)); 01208 for (CallSite::arg_iterator AI = CS.arg_begin(), 01209 E = CS.arg_end(); AI != E; ++AI) 01210 if (*AI == GV) 01211 return true; 01212 } else if (LoadInst *LI = dyn_cast<LoadInst>(*UI)) { 01213 if (LI->isVolatile()) 01214 return true; 01215 } else { 01216 return true; 01217 } 01218 return false; 01219 } 01220 01221 bool IPSCCP::runOnModule(Module &M) { 01222 SCCPSolver Solver; 01223 01224 // Loop over all functions, marking arguments to those with their addresses 01225 // taken or that are external as overdefined. 01226 // 01227 hash_map<Value*, LatticeVal> &Values = Solver.getValueMapping(); 01228 for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) 01229 if (!F->hasInternalLinkage() || AddressIsTaken(F)) { 01230 if (!F->isExternal()) 01231 Solver.MarkBlockExecutable(F->begin()); 01232 for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end(); 01233 AI != E; ++AI) 01234 Values[AI].markOverdefined(); 01235 } else { 01236 Solver.AddTrackedFunction(F); 01237 } 01238 01239 // Loop over global variables. We inform the solver about any internal global 01240 // variables that do not have their 'addresses taken'. If they don't have 01241 // their addresses taken, we can propagate constants through them. 01242 for (Module::global_iterator G = M.global_begin(), E = M.global_end(); 01243 G != E; ++G) 01244 if (!G->isConstant() && G->hasInternalLinkage() && !AddressIsTaken(G)) 01245 Solver.TrackValueOfGlobalVariable(G); 01246 01247 // Solve for constants. 01248 bool ResolvedBranches = true; 01249 while (ResolvedBranches) { 01250 Solver.Solve(); 01251 01252 DEBUG(std::cerr << "RESOLVING UNDEF BRANCHES\n"); 01253 ResolvedBranches = false; 01254 for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) 01255 ResolvedBranches |= Solver.ResolveBranchesIn(*F); 01256 } 01257 01258 bool MadeChanges = false; 01259 01260 // Iterate over all of the instructions in the module, replacing them with 01261 // constants if we have found them to be of constant values. 01262 // 01263 std::set<BasicBlock*> &ExecutableBBs = Solver.getExecutableBlocks(); 01264 for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) { 01265 for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end(); 01266 AI != E; ++AI) 01267 if (!AI->use_empty()) { 01268 LatticeVal &IV = Values[AI]; 01269 if (IV.isConstant() || IV.isUndefined()) { 01270 Constant *CST = IV.isConstant() ? 01271 IV.getConstant() : UndefValue::get(AI->getType()); 01272 DEBUG(std::cerr << "*** Arg " << *AI << " = " << *CST <<"\n"); 01273 01274 // Replaces all of the uses of a variable with uses of the 01275 // constant. 01276 AI->replaceAllUsesWith(CST); 01277 ++IPNumArgsElimed; 01278 } 01279 } 01280 01281 std::vector<BasicBlock*> BlocksToErase; 01282 for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) 01283 if (!ExecutableBBs.count(BB)) { 01284 DEBUG(std::cerr << " BasicBlock Dead:" << *BB); 01285 ++IPNumDeadBlocks; 01286 01287 // Delete the instructions backwards, as it has a reduced likelihood of 01288 // having to update as many def-use and use-def chains. 01289 std::vector<Instruction*> Insts; 01290 TerminatorInst *TI = BB->getTerminator(); 01291 for (BasicBlock::iterator I = BB->begin(), E = TI; I != E; ++I) 01292 Insts.push_back(I); 01293 01294 while (!Insts.empty()) { 01295 Instruction *I = Insts.back(); 01296 Insts.pop_back(); 01297 if (!I->use_empty()) 01298 I->replaceAllUsesWith(UndefValue::get(I->getType())); 01299 BB->getInstList().erase(I); 01300 MadeChanges = true; 01301 ++IPNumInstRemoved; 01302 } 01303 01304 for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) { 01305 BasicBlock *Succ = TI->getSuccessor(i); 01306 if (Succ->begin() != Succ->end() && isa<PHINode>(Succ->begin())) 01307 TI->getSuccessor(i)->removePredecessor(BB); 01308 } 01309 if (!TI->use_empty()) 01310 TI->replaceAllUsesWith(UndefValue::get(TI->getType())); 01311 BB->getInstList().erase(TI); 01312 01313 if (&*BB != &F->front()) 01314 BlocksToErase.push_back(BB); 01315 else 01316 new UnreachableInst(BB); 01317 01318 } else { 01319 for (BasicBlock::iterator BI = BB->begin(), E = BB->end(); BI != E; ) { 01320 Instruction *Inst = BI++; 01321 if (Inst->getType() != Type::VoidTy) { 01322 LatticeVal &IV = Values[Inst]; 01323 if (IV.isConstant() || IV.isUndefined() && 01324 !isa<TerminatorInst>(Inst)) { 01325 Constant *Const = IV.isConstant() 01326 ? IV.getConstant() : UndefValue::get(Inst->getType()); 01327 DEBUG(std::cerr << " Constant: " << *Const << " = " << *Inst); 01328 01329 // Replaces all of the uses of a variable with uses of the 01330 // constant. 01331 Inst->replaceAllUsesWith(Const); 01332 01333 // Delete the instruction. 01334 if (!isa<TerminatorInst>(Inst) && !isa<CallInst>(Inst)) 01335 BB->getInstList().erase(Inst); 01336 01337 // Hey, we just changed something! 01338 MadeChanges = true; 01339 ++IPNumInstRemoved; 01340 } 01341 } 01342 } 01343 } 01344 01345 // Now that all instructions in the function are constant folded, erase dead 01346 // blocks, because we can now use ConstantFoldTerminator to get rid of 01347 // in-edges. 01348 for (unsigned i = 0, e = BlocksToErase.size(); i != e; ++i) { 01349 // If there are any PHI nodes in this successor, drop entries for BB now. 01350 BasicBlock *DeadBB = BlocksToErase[i]; 01351 while (!DeadBB->use_empty()) { 01352 Instruction *I = cast<Instruction>(DeadBB->use_back()); 01353 bool Folded = ConstantFoldTerminator(I->getParent()); 01354 assert(Folded && "Didn't fold away reference to block!"); 01355 } 01356 01357 // Finally, delete the basic block. 01358 F->getBasicBlockList().erase(DeadBB); 01359 } 01360 } 01361 01362 // If we inferred constant or undef return values for a function, we replaced 01363 // all call uses with the inferred value. This means we don't need to bother 01364 // actually returning anything from the function. Replace all return 01365 // instructions with return undef. 01366 const hash_map<Function*, LatticeVal> &RV =Solver.getTrackedFunctionRetVals(); 01367 for (hash_map<Function*, LatticeVal>::const_iterator I = RV.begin(), 01368 E = RV.end(); I != E; ++I) 01369 if (!I->second.isOverdefined() && 01370 I->first->getReturnType() != Type::VoidTy) { 01371 Function *F = I->first; 01372 for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) 01373 if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) 01374 if (!isa<UndefValue>(RI->getOperand(0))) 01375 RI->setOperand(0, UndefValue::get(F->getReturnType())); 01376 } 01377 01378 // If we infered constant or undef values for globals variables, we can delete 01379 // the global and any stores that remain to it. 01380 const hash_map<GlobalVariable*, LatticeVal> &TG = Solver.getTrackedGlobals(); 01381 for (hash_map<GlobalVariable*, LatticeVal>::const_iterator I = TG.begin(), 01382 E = TG.end(); I != E; ++I) { 01383 GlobalVariable *GV = I->first; 01384 assert(!I->second.isOverdefined() && 01385 "Overdefined values should have been taken out of the map!"); 01386 DEBUG(std::cerr << "Found that GV '" << GV->getName()<< "' is constant!\n"); 01387 while (!GV->use_empty()) { 01388 StoreInst *SI = cast<StoreInst>(GV->use_back()); 01389 SI->eraseFromParent(); 01390 } 01391 M.getGlobalList().erase(GV); 01392 ++IPNumGlobalConst; 01393 } 01394 01395 return MadeChanges; 01396 }