LLVM API Documentation
00001 //===- SCCP.cpp - Sparse Conditional Constant Propagation -----------------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // 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/LLVMContext.h" 00031 #include "llvm/Pass.h" 00032 #include "llvm/Analysis/ConstantFolding.h" 00033 #include "llvm/Analysis/ValueTracking.h" 00034 #include "llvm/Transforms/Utils/Local.h" 00035 #include "llvm/Support/CallSite.h" 00036 #include "llvm/Support/Compiler.h" 00037 #include "llvm/Support/Debug.h" 00038 #include "llvm/Support/ErrorHandling.h" 00039 #include "llvm/Support/InstVisitor.h" 00040 #include "llvm/Support/raw_ostream.h" 00041 #include "llvm/ADT/DenseMap.h" 00042 #include "llvm/ADT/DenseSet.h" 00043 #include "llvm/ADT/SmallSet.h" 00044 #include "llvm/ADT/SmallVector.h" 00045 #include "llvm/ADT/Statistic.h" 00046 #include "llvm/ADT/STLExtras.h" 00047 #include <algorithm> 00048 #include <map> 00049 using namespace llvm; 00050 00051 STATISTIC(NumInstRemoved, "Number of instructions removed"); 00052 STATISTIC(NumDeadBlocks , "Number of basic blocks unreachable"); 00053 00054 STATISTIC(IPNumInstRemoved, "Number of instructions removed by IPSCCP"); 00055 STATISTIC(IPNumDeadBlocks , "Number of basic blocks unreachable by IPSCCP"); 00056 STATISTIC(IPNumArgsElimed ,"Number of arguments constant propagated by IPSCCP"); 00057 STATISTIC(IPNumGlobalConst, "Number of globals found to be constant by IPSCCP"); 00058 00059 namespace { 00060 /// LatticeVal class - This class represents the different lattice values that 00061 /// an LLVM value may occupy. It is a simple class with value semantics. 00062 /// 00063 class VISIBILITY_HIDDEN LatticeVal { 00064 enum { 00065 /// undefined - This LLVM Value has no known value yet. 00066 undefined, 00067 00068 /// constant - This LLVM Value has a specific constant value. 00069 constant, 00070 00071 /// forcedconstant - This LLVM Value was thought to be undef until 00072 /// ResolvedUndefsIn. This is treated just like 'constant', but if merged 00073 /// with another (different) constant, it goes to overdefined, instead of 00074 /// asserting. 00075 forcedconstant, 00076 00077 /// overdefined - This instruction is not known to be constant, and we know 00078 /// it has a value. 00079 overdefined 00080 } LatticeValue; // The current lattice position 00081 00082 Constant *ConstantVal; // If Constant value, the current value 00083 public: 00084 inline LatticeVal() : LatticeValue(undefined), ConstantVal(0) {} 00085 00086 // markOverdefined - Return true if this is a new status to be in... 00087 inline bool markOverdefined() { 00088 if (LatticeValue != overdefined) { 00089 LatticeValue = overdefined; 00090 return true; 00091 } 00092 return false; 00093 } 00094 00095 // markConstant - Return true if this is a new status for us. 00096 inline bool markConstant(Constant *V) { 00097 if (LatticeValue != constant) { 00098 if (LatticeValue == undefined) { 00099 LatticeValue = constant; 00100 assert(V && "Marking constant with NULL"); 00101 ConstantVal = V; 00102 } else { 00103 assert(LatticeValue == forcedconstant && 00104 "Cannot move from overdefined to constant!"); 00105 // Stay at forcedconstant if the constant is the same. 00106 if (V == ConstantVal) return false; 00107 00108 // Otherwise, we go to overdefined. Assumptions made based on the 00109 // forced value are possibly wrong. Assuming this is another constant 00110 // could expose a contradiction. 00111 LatticeValue = overdefined; 00112 } 00113 return true; 00114 } else { 00115 assert(ConstantVal == V && "Marking constant with different value"); 00116 } 00117 return false; 00118 } 00119 00120 inline void markForcedConstant(Constant *V) { 00121 assert(LatticeValue == undefined && "Can't force a defined value!"); 00122 LatticeValue = forcedconstant; 00123 ConstantVal = V; 00124 } 00125 00126 inline bool isUndefined() const { return LatticeValue == undefined; } 00127 inline bool isConstant() const { 00128 return LatticeValue == constant || LatticeValue == forcedconstant; 00129 } 00130 inline bool isOverdefined() const { return LatticeValue == overdefined; } 00131 00132 inline Constant *getConstant() const { 00133 assert(isConstant() && "Cannot get the constant of a non-constant!"); 00134 return ConstantVal; 00135 } 00136 }; 00137 00138 //===----------------------------------------------------------------------===// 00139 // 00140 /// SCCPSolver - This class is a general purpose solver for Sparse Conditional 00141 /// Constant Propagation. 00142 /// 00143 class SCCPSolver : public InstVisitor<SCCPSolver> { 00144 LLVMContext *Context; 00145 DenseSet<BasicBlock*> BBExecutable;// The basic blocks that are executable 00146 std::map<Value*, LatticeVal> ValueState; // The state each value is in. 00147 00148 /// GlobalValue - If we are tracking any values for the contents of a global 00149 /// variable, we keep a mapping from the constant accessor to the element of 00150 /// the global, to the currently known value. If the value becomes 00151 /// overdefined, it's entry is simply removed from this map. 00152 DenseMap<GlobalVariable*, LatticeVal> TrackedGlobals; 00153 00154 /// TrackedRetVals - If we are tracking arguments into and the return 00155 /// value out of a function, it will have an entry in this map, indicating 00156 /// what the known return value for the function is. 00157 DenseMap<Function*, LatticeVal> TrackedRetVals; 00158 00159 /// TrackedMultipleRetVals - Same as TrackedRetVals, but used for functions 00160 /// that return multiple values. 00161 DenseMap<std::pair<Function*, unsigned>, LatticeVal> TrackedMultipleRetVals; 00162 00163 // The reason for two worklists is that overdefined is the lowest state 00164 // on the lattice, and moving things to overdefined as fast as possible 00165 // makes SCCP converge much faster. 00166 // By having a separate worklist, we accomplish this because everything 00167 // possibly overdefined will become overdefined at the soonest possible 00168 // point. 00169 SmallVector<Value*, 64> OverdefinedInstWorkList; 00170 SmallVector<Value*, 64> InstWorkList; 00171 00172 00173 SmallVector<BasicBlock*, 64> BBWorkList; // The BasicBlock work list 00174 00175 /// UsersOfOverdefinedPHIs - Keep track of any users of PHI nodes that are not 00176 /// overdefined, despite the fact that the PHI node is overdefined. 00177 std::multimap<PHINode*, Instruction*> UsersOfOverdefinedPHIs; 00178 00179 /// KnownFeasibleEdges - Entries in this set are edges which have already had 00180 /// PHI nodes retriggered. 00181 typedef std::pair<BasicBlock*, BasicBlock*> Edge; 00182 DenseSet<Edge> KnownFeasibleEdges; 00183 public: 00184 void setContext(LLVMContext *C) { Context = C; } 00185 00186 /// MarkBlockExecutable - This method can be used by clients to mark all of 00187 /// the blocks that are known to be intrinsically live in the processed unit. 00188 void MarkBlockExecutable(BasicBlock *BB) { 00189 DEBUG(errs() << "Marking Block Executable: " << BB->getName() << "\n"); 00190 BBExecutable.insert(BB); // Basic block is executable! 00191 BBWorkList.push_back(BB); // Add the block to the work list! 00192 } 00193 00194 /// TrackValueOfGlobalVariable - Clients can use this method to 00195 /// inform the SCCPSolver that it should track loads and stores to the 00196 /// specified global variable if it can. This is only legal to call if 00197 /// performing Interprocedural SCCP. 00198 void TrackValueOfGlobalVariable(GlobalVariable *GV) { 00199 const Type *ElTy = GV->getType()->getElementType(); 00200 if (ElTy->isFirstClassType()) { 00201 LatticeVal &IV = TrackedGlobals[GV]; 00202 if (!isa<UndefValue>(GV->getInitializer())) 00203 IV.markConstant(GV->getInitializer()); 00204 } 00205 } 00206 00207 /// AddTrackedFunction - If the SCCP solver is supposed to track calls into 00208 /// and out of the specified function (which cannot have its address taken), 00209 /// this method must be called. 00210 void AddTrackedFunction(Function *F) { 00211 assert(F->hasLocalLinkage() && "Can only track internal functions!"); 00212 // Add an entry, F -> undef. 00213 if (const StructType *STy = dyn_cast<StructType>(F->getReturnType())) { 00214 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) 00215 TrackedMultipleRetVals.insert(std::make_pair(std::make_pair(F, i), 00216 LatticeVal())); 00217 } else 00218 TrackedRetVals.insert(std::make_pair(F, LatticeVal())); 00219 } 00220 00221 /// Solve - Solve for constants and executable blocks. 00222 /// 00223 void Solve(); 00224 00225 /// ResolvedUndefsIn - While solving the dataflow for a function, we assume 00226 /// that branches on undef values cannot reach any of their successors. 00227 /// However, this is not a safe assumption. After we solve dataflow, this 00228 /// method should be use to handle this. If this returns true, the solver 00229 /// should be rerun. 00230 bool ResolvedUndefsIn(Function &F); 00231 00232 bool isBlockExecutable(BasicBlock *BB) const { 00233 return BBExecutable.count(BB); 00234 } 00235 00236 /// getValueMapping - Once we have solved for constants, return the mapping of 00237 /// LLVM values to LatticeVals. 00238 std::map<Value*, LatticeVal> &getValueMapping() { 00239 return ValueState; 00240 } 00241 00242 /// getTrackedRetVals - Get the inferred return value map. 00243 /// 00244 const DenseMap<Function*, LatticeVal> &getTrackedRetVals() { 00245 return TrackedRetVals; 00246 } 00247 00248 /// getTrackedGlobals - Get and return the set of inferred initializers for 00249 /// global variables. 00250 const DenseMap<GlobalVariable*, LatticeVal> &getTrackedGlobals() { 00251 return TrackedGlobals; 00252 } 00253 00254 inline void markOverdefined(Value *V) { 00255 markOverdefined(ValueState[V], V); 00256 } 00257 00258 private: 00259 // markConstant - Make a value be marked as "constant". If the value 00260 // is not already a constant, add it to the instruction work list so that 00261 // the users of the instruction are updated later. 00262 // 00263 inline void markConstant(LatticeVal &IV, Value *V, Constant *C) { 00264 if (IV.markConstant(C)) { 00265 DEBUG(errs() << "markConstant: " << *C << ": " << *V << '\n'); 00266 InstWorkList.push_back(V); 00267 } 00268 } 00269 00270 inline void markForcedConstant(LatticeVal &IV, Value *V, Constant *C) { 00271 IV.markForcedConstant(C); 00272 DEBUG(errs() << "markForcedConstant: " << *C << ": " << *V << '\n'); 00273 InstWorkList.push_back(V); 00274 } 00275 00276 inline void markConstant(Value *V, Constant *C) { 00277 markConstant(ValueState[V], V, C); 00278 } 00279 00280 // markOverdefined - Make a value be marked as "overdefined". If the 00281 // value is not already overdefined, add it to the overdefined instruction 00282 // work list so that the users of the instruction are updated later. 00283 inline void markOverdefined(LatticeVal &IV, Value *V) { 00284 if (IV.markOverdefined()) { 00285 DEBUG(errs() << "markOverdefined: "; 00286 if (Function *F = dyn_cast<Function>(V)) 00287 errs() << "Function '" << F->getName() << "'\n"; 00288 else 00289 errs() << *V << '\n'); 00290 // Only instructions go on the work list 00291 OverdefinedInstWorkList.push_back(V); 00292 } 00293 } 00294 00295 inline void mergeInValue(LatticeVal &IV, Value *V, LatticeVal &MergeWithV) { 00296 if (IV.isOverdefined() || MergeWithV.isUndefined()) 00297 return; // Noop. 00298 if (MergeWithV.isOverdefined()) 00299 markOverdefined(IV, V); 00300 else if (IV.isUndefined()) 00301 markConstant(IV, V, MergeWithV.getConstant()); 00302 else if (IV.getConstant() != MergeWithV.getConstant()) 00303 markOverdefined(IV, V); 00304 } 00305 00306 inline void mergeInValue(Value *V, LatticeVal &MergeWithV) { 00307 return mergeInValue(ValueState[V], V, MergeWithV); 00308 } 00309 00310 00311 // getValueState - Return the LatticeVal object that corresponds to the value. 00312 // This function is necessary because not all values should start out in the 00313 // underdefined state... Argument's should be overdefined, and 00314 // constants should be marked as constants. If a value is not known to be an 00315 // Instruction object, then use this accessor to get its value from the map. 00316 // 00317 inline LatticeVal &getValueState(Value *V) { 00318 std::map<Value*, LatticeVal>::iterator I = ValueState.find(V); 00319 if (I != ValueState.end()) return I->second; // Common case, in the map 00320 00321 if (Constant *C = dyn_cast<Constant>(V)) { 00322 if (isa<UndefValue>(V)) { 00323 // Nothing to do, remain undefined. 00324 } else { 00325 LatticeVal &LV = ValueState[C]; 00326 LV.markConstant(C); // Constants are constant 00327 return LV; 00328 } 00329 } 00330 // All others are underdefined by default... 00331 return ValueState[V]; 00332 } 00333 00334 // markEdgeExecutable - Mark a basic block as executable, adding it to the BB 00335 // work list if it is not already executable... 00336 // 00337 void markEdgeExecutable(BasicBlock *Source, BasicBlock *Dest) { 00338 if (!KnownFeasibleEdges.insert(Edge(Source, Dest)).second) 00339 return; // This edge is already known to be executable! 00340 00341 if (BBExecutable.count(Dest)) { 00342 DEBUG(errs() << "Marking Edge Executable: " << Source->getName() 00343 << " -> " << Dest->getName() << "\n"); 00344 00345 // The destination is already executable, but we just made an edge 00346 // feasible that wasn't before. Revisit the PHI nodes in the block 00347 // because they have potentially new operands. 00348 for (BasicBlock::iterator I = Dest->begin(); isa<PHINode>(I); ++I) 00349 visitPHINode(*cast<PHINode>(I)); 00350 00351 } else { 00352 MarkBlockExecutable(Dest); 00353 } 00354 } 00355 00356 // getFeasibleSuccessors - Return a vector of booleans to indicate which 00357 // successors are reachable from a given terminator instruction. 00358 // 00359 void getFeasibleSuccessors(TerminatorInst &TI, SmallVector<bool, 16> &Succs); 00360 00361 // isEdgeFeasible - Return true if the control flow edge from the 'From' basic 00362 // block to the 'To' basic block is currently feasible... 00363 // 00364 bool isEdgeFeasible(BasicBlock *From, BasicBlock *To); 00365 00366 // OperandChangedState - This method is invoked on all of the users of an 00367 // instruction that was just changed state somehow.... Based on this 00368 // information, we need to update the specified user of this instruction. 00369 // 00370 void OperandChangedState(User *U) { 00371 // Only instructions use other variable values! 00372 Instruction &I = cast<Instruction>(*U); 00373 if (BBExecutable.count(I.getParent())) // Inst is executable? 00374 visit(I); 00375 } 00376 00377 private: 00378 friend class InstVisitor<SCCPSolver>; 00379 00380 // visit implementations - Something changed in this instruction... Either an 00381 // operand made a transition, or the instruction is newly executable. Change 00382 // the value type of I to reflect these changes if appropriate. 00383 // 00384 void visitPHINode(PHINode &I); 00385 00386 // Terminators 00387 void visitReturnInst(ReturnInst &I); 00388 void visitTerminatorInst(TerminatorInst &TI); 00389 00390 void visitCastInst(CastInst &I); 00391 void visitSelectInst(SelectInst &I); 00392 void visitBinaryOperator(Instruction &I); 00393 void visitCmpInst(CmpInst &I); 00394 void visitExtractElementInst(ExtractElementInst &I); 00395 void visitInsertElementInst(InsertElementInst &I); 00396 void visitShuffleVectorInst(ShuffleVectorInst &I); 00397 void visitExtractValueInst(ExtractValueInst &EVI); 00398 void visitInsertValueInst(InsertValueInst &IVI); 00399 00400 // Instructions that cannot be folded away... 00401 void visitStoreInst (Instruction &I); 00402 void visitLoadInst (LoadInst &I); 00403 void visitGetElementPtrInst(GetElementPtrInst &I); 00404 void visitCallInst (CallInst &I) { visitCallSite(CallSite::get(&I)); } 00405 void visitInvokeInst (InvokeInst &II) { 00406 visitCallSite(CallSite::get(&II)); 00407 visitTerminatorInst(II); 00408 } 00409 void visitCallSite (CallSite CS); 00410 void visitUnwindInst (TerminatorInst &I) { /*returns void*/ } 00411 void visitUnreachableInst(TerminatorInst &I) { /*returns void*/ } 00412 void visitAllocationInst(Instruction &I) { markOverdefined(&I); } 00413 void visitVANextInst (Instruction &I) { markOverdefined(&I); } 00414 void visitVAArgInst (Instruction &I) { markOverdefined(&I); } 00415 void visitFreeInst (Instruction &I) { /*returns void*/ } 00416 00417 void visitInstruction(Instruction &I) { 00418 // If a new instruction is added to LLVM that we don't handle... 00419 cerr << "SCCP: Don't know how to handle: " << I; 00420 markOverdefined(&I); // Just in case 00421 } 00422 }; 00423 00424 } // end anonymous namespace 00425 00426 00427 // getFeasibleSuccessors - Return a vector of booleans to indicate which 00428 // successors are reachable from a given terminator instruction. 00429 // 00430 void SCCPSolver::getFeasibleSuccessors(TerminatorInst &TI, 00431 SmallVector<bool, 16> &Succs) { 00432 Succs.resize(TI.getNumSuccessors()); 00433 if (BranchInst *BI = dyn_cast<BranchInst>(&TI)) { 00434 if (BI->isUnconditional()) { 00435 Succs[0] = true; 00436 } else { 00437 LatticeVal &BCValue = getValueState(BI->getCondition()); 00438 if (BCValue.isOverdefined() || 00439 (BCValue.isConstant() && !isa<ConstantInt>(BCValue.getConstant()))) { 00440 // Overdefined condition variables, and branches on unfoldable constant 00441 // conditions, mean the branch could go either way. 00442 Succs[0] = Succs[1] = true; 00443 } else if (BCValue.isConstant()) { 00444 // Constant condition variables mean the branch can only go a single way 00445 Succs[BCValue.getConstant() == ConstantInt::getFalse(*Context)] = true; 00446 } 00447 } 00448 } else if (isa<InvokeInst>(&TI)) { 00449 // Invoke instructions successors are always executable. 00450 Succs[0] = Succs[1] = true; 00451 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(&TI)) { 00452 LatticeVal &SCValue = getValueState(SI->getCondition()); 00453 if (SCValue.isOverdefined() || // Overdefined condition? 00454 (SCValue.isConstant() && !isa<ConstantInt>(SCValue.getConstant()))) { 00455 // All destinations are executable! 00456 Succs.assign(TI.getNumSuccessors(), true); 00457 } else if (SCValue.isConstant()) 00458 Succs[SI->findCaseValue(cast<ConstantInt>(SCValue.getConstant()))] = true; 00459 } else { 00460 llvm_unreachable("SCCP: Don't know how to handle this terminator!"); 00461 } 00462 } 00463 00464 00465 // isEdgeFeasible - Return true if the control flow edge from the 'From' basic 00466 // block to the 'To' basic block is currently feasible... 00467 // 00468 bool SCCPSolver::isEdgeFeasible(BasicBlock *From, BasicBlock *To) { 00469 assert(BBExecutable.count(To) && "Dest should always be alive!"); 00470 00471 // Make sure the source basic block is executable!! 00472 if (!BBExecutable.count(From)) return false; 00473 00474 // Check to make sure this edge itself is actually feasible now... 00475 TerminatorInst *TI = From->getTerminator(); 00476 if (BranchInst *BI = dyn_cast<BranchInst>(TI)) { 00477 if (BI->isUnconditional()) 00478 return true; 00479 else { 00480 LatticeVal &BCValue = getValueState(BI->getCondition()); 00481 if (BCValue.isOverdefined()) { 00482 // Overdefined condition variables mean the branch could go either way. 00483 return true; 00484 } else if (BCValue.isConstant()) { 00485 // Not branching on an evaluatable constant? 00486 if (!isa<ConstantInt>(BCValue.getConstant())) return true; 00487 00488 // Constant condition variables mean the branch can only go a single way 00489 return BI->getSuccessor(BCValue.getConstant() == 00490 ConstantInt::getFalse(*Context)) == To; 00491 } 00492 return false; 00493 } 00494 } else if (isa<InvokeInst>(TI)) { 00495 // Invoke instructions successors are always executable. 00496 return true; 00497 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 00498 LatticeVal &SCValue = getValueState(SI->getCondition()); 00499 if (SCValue.isOverdefined()) { // Overdefined condition? 00500 // All destinations are executable! 00501 return true; 00502 } else if (SCValue.isConstant()) { 00503 Constant *CPV = SCValue.getConstant(); 00504 if (!isa<ConstantInt>(CPV)) 00505 return true; // not a foldable constant? 00506 00507 // Make sure to skip the "default value" which isn't a value 00508 for (unsigned i = 1, E = SI->getNumSuccessors(); i != E; ++i) 00509 if (SI->getSuccessorValue(i) == CPV) // Found the taken branch... 00510 return SI->getSuccessor(i) == To; 00511 00512 // Constant value not equal to any of the branches... must execute 00513 // default branch then... 00514 return SI->getDefaultDest() == To; 00515 } 00516 return false; 00517 } else { 00518 #ifndef NDEBUG 00519 cerr << "Unknown terminator instruction: " << *TI << '\n'; 00520 #endif 00521 llvm_unreachable(0); 00522 } 00523 } 00524 00525 // visit Implementations - Something changed in this instruction... Either an 00526 // operand made a transition, or the instruction is newly executable. Change 00527 // the value type of I to reflect these changes if appropriate. This method 00528 // makes sure to do the following actions: 00529 // 00530 // 1. If a phi node merges two constants in, and has conflicting value coming 00531 // from different branches, or if the PHI node merges in an overdefined 00532 // value, then the PHI node becomes overdefined. 00533 // 2. If a phi node merges only constants in, and they all agree on value, the 00534 // PHI node becomes a constant value equal to that. 00535 // 3. If V <- x (op) y && isConstant(x) && isConstant(y) V = Constant 00536 // 4. If V <- x (op) y && (isOverdefined(x) || isOverdefined(y)) V = Overdefined 00537 // 5. If V <- MEM or V <- CALL or V <- (unknown) then V = Overdefined 00538 // 6. If a conditional branch has a value that is constant, make the selected 00539 // destination executable 00540 // 7. If a conditional branch has a value that is overdefined, make all 00541 // successors executable. 00542 // 00543 void SCCPSolver::visitPHINode(PHINode &PN) { 00544 LatticeVal &PNIV = getValueState(&PN); 00545 if (PNIV.isOverdefined()) { 00546 // There may be instructions using this PHI node that are not overdefined 00547 // themselves. If so, make sure that they know that the PHI node operand 00548 // changed. 00549 std::multimap<PHINode*, Instruction*>::iterator I, E; 00550 tie(I, E) = UsersOfOverdefinedPHIs.equal_range(&PN); 00551 if (I != E) { 00552 SmallVector<Instruction*, 16> Users; 00553 for (; I != E; ++I) Users.push_back(I->second); 00554 while (!Users.empty()) { 00555 visit(Users.back()); 00556 Users.pop_back(); 00557 } 00558 } 00559 return; // Quick exit 00560 } 00561 00562 // Super-extra-high-degree PHI nodes are unlikely to ever be marked constant, 00563 // and slow us down a lot. Just mark them overdefined. 00564 if (PN.getNumIncomingValues() > 64) { 00565 markOverdefined(PNIV, &PN); 00566 return; 00567 } 00568 00569 // Look at all of the executable operands of the PHI node. If any of them 00570 // are overdefined, the PHI becomes overdefined as well. If they are all 00571 // constant, and they agree with each other, the PHI becomes the identical 00572 // constant. If they are constant and don't agree, the PHI is overdefined. 00573 // If there are no executable operands, the PHI remains undefined. 00574 // 00575 Constant *OperandVal = 0; 00576 for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) { 00577 LatticeVal &IV = getValueState(PN.getIncomingValue(i)); 00578 if (IV.isUndefined()) continue; // Doesn't influence PHI node. 00579 00580 if (isEdgeFeasible(PN.getIncomingBlock(i), PN.getParent())) { 00581 if (IV.isOverdefined()) { // PHI node becomes overdefined! 00582 markOverdefined(&PN); 00583 return; 00584 } 00585 00586 if (OperandVal == 0) { // Grab the first value... 00587 OperandVal = IV.getConstant(); 00588 } else { // Another value is being merged in! 00589 // There is already a reachable operand. If we conflict with it, 00590 // then the PHI node becomes overdefined. If we agree with it, we 00591 // can continue on. 00592 00593 // Check to see if there are two different constants merging... 00594 if (IV.getConstant() != OperandVal) { 00595 // Yes there is. This means the PHI node is not constant. 00596 // You must be overdefined poor PHI. 00597 // 00598 markOverdefined(&PN); // The PHI node now becomes overdefined 00599 return; // I'm done analyzing you 00600 } 00601 } 00602 } 00603 } 00604 00605 // If we exited the loop, this means that the PHI node only has constant 00606 // arguments that agree with each other(and OperandVal is the constant) or 00607 // OperandVal is null because there are no defined incoming arguments. If 00608 // this is the case, the PHI remains undefined. 00609 // 00610 if (OperandVal) 00611 markConstant(&PN, OperandVal); // Acquire operand value 00612 } 00613 00614 void SCCPSolver::visitReturnInst(ReturnInst &I) { 00615 if (I.getNumOperands() == 0) return; // Ret void 00616 00617 Function *F = I.getParent()->getParent(); 00618 // If we are tracking the return value of this function, merge it in. 00619 if (!F->hasLocalLinkage()) 00620 return; 00621 00622 if (!TrackedRetVals.empty() && I.getNumOperands() == 1) { 00623 DenseMap<Function*, LatticeVal>::iterator TFRVI = 00624 TrackedRetVals.find(F); 00625 if (TFRVI != TrackedRetVals.end() && 00626 !TFRVI->second.isOverdefined()) { 00627 LatticeVal &IV = getValueState(I.getOperand(0)); 00628 mergeInValue(TFRVI->second, F, IV); 00629 return; 00630 } 00631 } 00632 00633 // Handle functions that return multiple values. 00634 if (!TrackedMultipleRetVals.empty() && I.getNumOperands() > 1) { 00635 for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) { 00636 DenseMap<std::pair<Function*, unsigned>, LatticeVal>::iterator 00637 It = TrackedMultipleRetVals.find(std::make_pair(F, i)); 00638 if (It == TrackedMultipleRetVals.end()) break; 00639 mergeInValue(It->second, F, getValueState(I.getOperand(i))); 00640 } 00641 } else if (!TrackedMultipleRetVals.empty() && 00642 I.getNumOperands() == 1 && 00643 isa<StructType>(I.getOperand(0)->getType())) { 00644 for (unsigned i = 0, e = I.getOperand(0)->getType()->getNumContainedTypes(); 00645 i != e; ++i) { 00646 DenseMap<std::pair<Function*, unsigned>, LatticeVal>::iterator 00647 It = TrackedMultipleRetVals.find(std::make_pair(F, i)); 00648 if (It == TrackedMultipleRetVals.end()) break; 00649 if (Value *Val = FindInsertedValue(I.getOperand(0), i, I.getContext())) 00650 mergeInValue(It->second, F, getValueState(Val)); 00651 } 00652 } 00653 } 00654 00655 void SCCPSolver::visitTerminatorInst(TerminatorInst &TI) { 00656 SmallVector<bool, 16> SuccFeasible; 00657 getFeasibleSuccessors(TI, SuccFeasible); 00658 00659 BasicBlock *BB = TI.getParent(); 00660 00661 // Mark all feasible successors executable... 00662 for (unsigned i = 0, e = SuccFeasible.size(); i != e; ++i) 00663 if (SuccFeasible[i]) 00664 markEdgeExecutable(BB, TI.getSuccessor(i)); 00665 } 00666 00667 void SCCPSolver::visitCastInst(CastInst &I) { 00668 Value *V = I.getOperand(0); 00669 LatticeVal &VState = getValueState(V); 00670 if (VState.isOverdefined()) // Inherit overdefinedness of operand 00671 markOverdefined(&I); 00672 else if (VState.isConstant()) // Propagate constant value 00673 markConstant(&I, ConstantExpr::getCast(I.getOpcode(), 00674 VState.getConstant(), I.getType())); 00675 } 00676 00677 void SCCPSolver::visitExtractValueInst(ExtractValueInst &EVI) { 00678 Value *Aggr = EVI.getAggregateOperand(); 00679 00680 // If the operand to the extractvalue is an undef, the result is undef. 00681 if (isa<UndefValue>(Aggr)) 00682 return; 00683 00684 // Currently only handle single-index extractvalues. 00685 if (EVI.getNumIndices() != 1) { 00686 markOverdefined(&EVI); 00687 return; 00688 } 00689 00690 Function *F = 0; 00691 if (CallInst *CI = dyn_cast<CallInst>(Aggr)) 00692 F = CI->getCalledFunction(); 00693 else if (InvokeInst *II = dyn_cast<InvokeInst>(Aggr)) 00694 F = II->getCalledFunction(); 00695 00696 // TODO: If IPSCCP resolves the callee of this function, we could propagate a 00697 // result back! 00698 if (F == 0 || TrackedMultipleRetVals.empty()) { 00699 markOverdefined(&EVI); 00700 return; 00701 } 00702 00703 // See if we are tracking the result of the callee. If not tracking this 00704 // function (for example, it is a declaration) just move to overdefined. 00705 if (!TrackedMultipleRetVals.count(std::make_pair(F, *EVI.idx_begin()))) { 00706 markOverdefined(&EVI); 00707 return; 00708 } 00709 00710 // Otherwise, the value will be merged in here as a result of CallSite 00711 // handling. 00712 } 00713 00714 void SCCPSolver::visitInsertValueInst(InsertValueInst &IVI) { 00715 Value *Aggr = IVI.getAggregateOperand(); 00716 Value *Val = IVI.getInsertedValueOperand(); 00717 00718 // If the operands to the insertvalue are undef, the result is undef. 00719 if (isa<UndefValue>(Aggr) && isa<UndefValue>(Val)) 00720 return; 00721 00722 // Currently only handle single-index insertvalues. 00723 if (IVI.getNumIndices() != 1) { 00724 markOverdefined(&IVI); 00725 return; 00726 } 00727 00728 // Currently only handle insertvalue instructions that are in a single-use 00729 // chain that builds up a return value. 00730 for (const InsertValueInst *TmpIVI = &IVI; ; ) { 00731 if (!TmpIVI->hasOneUse()) { 00732 markOverdefined(&IVI); 00733 return; 00734 } 00735 const Value *V = *TmpIVI->use_begin(); 00736 if (isa<ReturnInst>(V)) 00737 break; 00738 TmpIVI = dyn_cast<InsertValueInst>(V); 00739 if (!TmpIVI) { 00740 markOverdefined(&IVI); 00741 return; 00742 } 00743 } 00744 00745 // See if we are tracking the result of the callee. 00746 Function *F = IVI.getParent()->getParent(); 00747 DenseMap<std::pair<Function*, unsigned>, LatticeVal>::iterator 00748 It = TrackedMultipleRetVals.find(std::make_pair(F, *IVI.idx_begin())); 00749 00750 // Merge in the inserted member value. 00751 if (It != TrackedMultipleRetVals.end()) 00752 mergeInValue(It->second, F, getValueState(Val)); 00753 00754 // Mark the aggregate result of the IVI overdefined; any tracking that we do 00755 // will be done on the individual member values. 00756 markOverdefined(&IVI); 00757 } 00758 00759 void SCCPSolver::visitSelectInst(SelectInst &I) { 00760 LatticeVal &CondValue = getValueState(I.getCondition()); 00761 if (CondValue.isUndefined()) 00762 return; 00763 if (CondValue.isConstant()) { 00764 if (ConstantInt *CondCB = dyn_cast<ConstantInt>(CondValue.getConstant())){ 00765 mergeInValue(&I, getValueState(CondCB->getZExtValue() ? I.getTrueValue() 00766 : I.getFalseValue())); 00767 return; 00768 } 00769 } 00770 00771 // Otherwise, the condition is overdefined or a constant we can't evaluate. 00772 // See if we can produce something better than overdefined based on the T/F 00773 // value. 00774 LatticeVal &TVal = getValueState(I.getTrueValue()); 00775 LatticeVal &FVal = getValueState(I.getFalseValue()); 00776 00777 // select ?, C, C -> C. 00778 if (TVal.isConstant() && FVal.isConstant() && 00779 TVal.getConstant() == FVal.getConstant()) { 00780 markConstant(&I, FVal.getConstant()); 00781 return; 00782 } 00783 00784 if (TVal.isUndefined()) { // select ?, undef, X -> X. 00785 mergeInValue(&I, FVal); 00786 } else if (FVal.isUndefined()) { // select ?, X, undef -> X. 00787 mergeInValue(&I, TVal); 00788 } else { 00789 markOverdefined(&I); 00790 } 00791 } 00792 00793 // Handle BinaryOperators and Shift Instructions... 00794 void SCCPSolver::visitBinaryOperator(Instruction &I) { 00795 LatticeVal &IV = ValueState[&I]; 00796 if (IV.isOverdefined()) return; 00797 00798 LatticeVal &V1State = getValueState(I.getOperand(0)); 00799 LatticeVal &V2State = getValueState(I.getOperand(1)); 00800 00801 if (V1State.isOverdefined() || V2State.isOverdefined()) { 00802 // If this is an AND or OR with 0 or -1, it doesn't matter that the other 00803 // operand is overdefined. 00804 if (I.getOpcode() == Instruction::And || I.getOpcode() == Instruction::Or) { 00805 LatticeVal *NonOverdefVal = 0; 00806 if (!V1State.isOverdefined()) { 00807 NonOverdefVal = &V1State; 00808 } else if (!V2State.isOverdefined()) { 00809 NonOverdefVal = &V2State; 00810 } 00811 00812 if (NonOverdefVal) { 00813 if (NonOverdefVal->isUndefined()) { 00814 // Could annihilate value. 00815 if (I.getOpcode() == Instruction::And) 00816 markConstant(IV, &I, Constant::getNullValue(I.getType())); 00817 else if (const VectorType *PT = dyn_cast<VectorType>(I.getType())) 00818 markConstant(IV, &I, Constant::getAllOnesValue(PT)); 00819 else 00820 markConstant(IV, &I, 00821 Constant::getAllOnesValue(I.getType())); 00822 return; 00823 } else { 00824 if (I.getOpcode() == Instruction::And) { 00825 if (NonOverdefVal->getConstant()->isNullValue()) { 00826 markConstant(IV, &I, NonOverdefVal->getConstant()); 00827 return; // X and 0 = 0 00828 } 00829 } else { 00830 if (ConstantInt *CI = 00831 dyn_cast<ConstantInt>(NonOverdefVal->getConstant())) 00832 if (CI->isAllOnesValue()) { 00833 markConstant(IV, &I, NonOverdefVal->getConstant()); 00834 return; // X or -1 = -1 00835 } 00836 } 00837 } 00838 } 00839 } 00840 00841 00842 // If both operands are PHI nodes, it is possible that this instruction has 00843 // a constant value, despite the fact that the PHI node doesn't. Check for 00844 // this condition now. 00845 if (PHINode *PN1 = dyn_cast<PHINode>(I.getOperand(0))) 00846 if (PHINode *PN2 = dyn_cast<PHINode>(I.getOperand(1))) 00847 if (PN1->getParent() == PN2->getParent()) { 00848 // Since the two PHI nodes are in the same basic block, they must have 00849 // entries for the same predecessors. Walk the predecessor list, and 00850 // if all of the incoming values are constants, and the result of 00851 // evaluating this expression with all incoming value pairs is the 00852 // same, then this expression is a constant even though the PHI node 00853 // is not a constant! 00854 LatticeVal Result; 00855 for (unsigned i = 0, e = PN1->getNumIncomingValues(); i != e; ++i) { 00856 LatticeVal &In1 = getValueState(PN1->getIncomingValue(i)); 00857 BasicBlock *InBlock = PN1->getIncomingBlock(i); 00858 LatticeVal &In2 = 00859 getValueState(PN2->getIncomingValueForBlock(InBlock)); 00860 00861 if (In1.isOverdefined() || In2.isOverdefined()) { 00862 Result.markOverdefined(); 00863 break; // Cannot fold this operation over the PHI nodes! 00864 } else if (In1.isConstant() && In2.isConstant()) { 00865 Constant *V = 00866 ConstantExpr::get(I.getOpcode(), In1.getConstant(), 00867 In2.getConstant()); 00868 if (Result.isUndefined()) 00869 Result.markConstant(V); 00870 else if (Result.isConstant() && Result.getConstant() != V) { 00871 Result.markOverdefined(); 00872 break; 00873 } 00874 } 00875 } 00876 00877 // If we found a constant value here, then we know the instruction is 00878 // constant despite the fact that the PHI nodes are overdefined. 00879 if (Result.isConstant()) { 00880 markConstant(IV, &I, Result.getConstant()); 00881 // Remember that this instruction is virtually using the PHI node 00882 // operands. 00883 UsersOfOverdefinedPHIs.insert(std::make_pair(PN1, &I)); 00884 UsersOfOverdefinedPHIs.insert(std::make_pair(PN2, &I)); 00885 return; 00886 } else if (Result.isUndefined()) { 00887 return; 00888 } 00889 00890 // Okay, this really is overdefined now. Since we might have 00891 // speculatively thought that this was not overdefined before, and 00892 // added ourselves to the UsersOfOverdefinedPHIs list for the PHIs, 00893 // make sure to clean out any entries that we put there, for 00894 // efficiency. 00895 std::multimap<PHINode*, Instruction*>::iterator It, E; 00896 tie(It, E) = UsersOfOverdefinedPHIs.equal_range(PN1); 00897 while (It != E) { 00898 if (It->second == &I) { 00899 UsersOfOverdefinedPHIs.erase(It++); 00900 } else 00901 ++It; 00902 } 00903 tie(It, E) = UsersOfOverdefinedPHIs.equal_range(PN2); 00904 while (It != E) { 00905 if (It->second == &I) { 00906 UsersOfOverdefinedPHIs.erase(It++); 00907 } else 00908 ++It; 00909 } 00910 } 00911 00912 markOverdefined(IV, &I); 00913 } else if (V1State.isConstant() && V2State.isConstant()) { 00914 markConstant(IV, &I, 00915 ConstantExpr::get(I.getOpcode(), V1State.getConstant(), 00916 V2State.getConstant())); 00917 } 00918 } 00919 00920 // Handle ICmpInst instruction... 00921 void SCCPSolver::visitCmpInst(CmpInst &I) { 00922 LatticeVal &IV = ValueState[&I]; 00923 if (IV.isOverdefined()) return; 00924 00925 LatticeVal &V1State = getValueState(I.getOperand(0)); 00926 LatticeVal &V2State = getValueState(I.getOperand(1)); 00927 00928 if (V1State.isOverdefined() || V2State.isOverdefined()) { 00929 // If both operands are PHI nodes, it is possible that this instruction has 00930 // a constant value, despite the fact that the PHI node doesn't. Check for 00931 // this condition now. 00932 if (PHINode *PN1 = dyn_cast<PHINode>(I.getOperand(0))) 00933 if (PHINode *PN2 = dyn_cast<PHINode>(I.getOperand(1))) 00934 if (PN1->getParent() == PN2->getParent()) { 00935 // Since the two PHI nodes are in the same basic block, they must have 00936 // entries for the same predecessors. Walk the predecessor list, and 00937 // if all of the incoming values are constants, and the result of 00938 // evaluating this expression with all incoming value pairs is the 00939 // same, then this expression is a constant even though the PHI node 00940 // is not a constant! 00941 LatticeVal Result; 00942 for (unsigned i = 0, e = PN1->getNumIncomingValues(); i != e; ++i) { 00943 LatticeVal &In1 = getValueState(PN1->getIncomingValue(i)); 00944 BasicBlock *InBlock = PN1->getIncomingBlock(i); 00945 LatticeVal &In2 = 00946 getValueState(PN2->getIncomingValueForBlock(InBlock)); 00947 00948 if (In1.isOverdefined() || In2.isOverdefined()) { 00949 Result.markOverdefined(); 00950 break; // Cannot fold this operation over the PHI nodes! 00951 } else if (In1.isConstant() && In2.isConstant()) { 00952 Constant *V = ConstantExpr::getCompare(I.getPredicate(), 00953 In1.getConstant(), 00954 In2.getConstant()); 00955 if (Result.isUndefined()) 00956 Result.markConstant(V); 00957 else if (Result.isConstant() && Result.getConstant() != V) { 00958 Result.markOverdefined(); 00959 break; 00960 } 00961 } 00962 } 00963 00964 // If we found a constant value here, then we know the instruction is 00965 // constant despite the fact that the PHI nodes are overdefined. 00966 if (Result.isConstant()) { 00967 markConstant(IV, &I, Result.getConstant()); 00968 // Remember that this instruction is virtually using the PHI node 00969 // operands. 00970 UsersOfOverdefinedPHIs.insert(std::make_pair(PN1, &I)); 00971 UsersOfOverdefinedPHIs.insert(std::make_pair(PN2, &I)); 00972 return; 00973 } else if (Result.isUndefined()) { 00974 return; 00975 } 00976 00977 // Okay, this really is overdefined now. Since we might have 00978 // speculatively thought that this was not overdefined before, and 00979 // added ourselves to the UsersOfOverdefinedPHIs list for the PHIs, 00980 // make sure to clean out any entries that we put there, for 00981 // efficiency. 00982 std::multimap<PHINode*, Instruction*>::iterator It, E; 00983 tie(It, E) = UsersOfOverdefinedPHIs.equal_range(PN1); 00984 while (It != E) { 00985 if (It->second == &I) { 00986 UsersOfOverdefinedPHIs.erase(It++); 00987 } else 00988 ++It; 00989 } 00990 tie(It, E) = UsersOfOverdefinedPHIs.equal_range(PN2); 00991 while (It != E) { 00992 if (It->second == &I) { 00993 UsersOfOverdefinedPHIs.erase(It++); 00994 } else 00995 ++It; 00996 } 00997 } 00998 00999 markOverdefined(IV, &I); 01000 } else if (V1State.isConstant() && V2State.isConstant()) { 01001 markConstant(IV, &I, ConstantExpr::getCompare(I.getPredicate(), 01002 V1State.getConstant(), 01003 V2State.getConstant())); 01004 } 01005 } 01006 01007 void SCCPSolver::visitExtractElementInst(ExtractElementInst &I) { 01008 // FIXME : SCCP does not handle vectors properly. 01009 markOverdefined(&I); 01010 return; 01011 01012 #if 0 01013 LatticeVal &ValState = getValueState(I.getOperand(0)); 01014 LatticeVal &IdxState = getValueState(I.getOperand(1)); 01015 01016 if (ValState.isOverdefined() || IdxState.isOverdefined()) 01017 markOverdefined(&I); 01018 else if(ValState.isConstant() && IdxState.isConstant()) 01019 markConstant(&I, ConstantExpr::getExtractElement(ValState.getConstant(), 01020 IdxState.getConstant())); 01021 #endif 01022 } 01023 01024 void SCCPSolver::visitInsertElementInst(InsertElementInst &I) { 01025 // FIXME : SCCP does not handle vectors properly. 01026 markOverdefined(&I); 01027 return; 01028 #if 0 01029 LatticeVal &ValState = getValueState(I.getOperand(0)); 01030 LatticeVal &EltState = getValueState(I.getOperand(1)); 01031 LatticeVal &IdxState = getValueState(I.getOperand(2)); 01032 01033 if (ValState.isOverdefined() || EltState.isOverdefined() || 01034 IdxState.isOverdefined()) 01035 markOverdefined(&I); 01036 else if(ValState.isConstant() && EltState.isConstant() && 01037 IdxState.isConstant()) 01038 markConstant(&I, ConstantExpr::getInsertElement(ValState.getConstant(), 01039 EltState.getConstant(), 01040 IdxState.getConstant())); 01041 else if (ValState.isUndefined() && EltState.isConstant() && 01042 IdxState.isConstant()) 01043 markConstant(&I,ConstantExpr::getInsertElement(UndefValue::get(I.getType()), 01044 EltState.getConstant(), 01045 IdxState.getConstant())); 01046 #endif 01047 } 01048 01049 void SCCPSolver::visitShuffleVectorInst(ShuffleVectorInst &I) { 01050 // FIXME : SCCP does not handle vectors properly. 01051 markOverdefined(&I); 01052 return; 01053 #if 0 01054 LatticeVal &V1State = getValueState(I.getOperand(0)); 01055 LatticeVal &V2State = getValueState(I.getOperand(1)); 01056 LatticeVal &MaskState = getValueState(I.getOperand(2)); 01057 01058 if (MaskState.isUndefined() || 01059 (V1State.isUndefined() && V2State.isUndefined())) 01060 return; // Undefined output if mask or both inputs undefined. 01061 01062 if (V1State.isOverdefined() || V2State.isOverdefined() || 01063 MaskState.isOverdefined()) { 01064 markOverdefined(&I); 01065 } else { 01066 // A mix of constant/undef inputs. 01067 Constant *V1 = V1State.isConstant() ? 01068 V1State.getConstant() : UndefValue::get(I.getType()); 01069 Constant *V2 = V2State.isConstant() ? 01070 V2State.getConstant() : UndefValue::get(I.getType()); 01071 Constant *Mask = MaskState.isConstant() ? 01072 MaskState.getConstant() : UndefValue::get(I.getOperand(2)->getType()); 01073 markConstant(&I, ConstantExpr::getShuffleVector(V1, V2, Mask)); 01074 } 01075 #endif 01076 } 01077 01078 // Handle getelementptr instructions... if all operands are constants then we 01079 // can turn this into a getelementptr ConstantExpr. 01080 // 01081 void SCCPSolver::visitGetElementPtrInst(GetElementPtrInst &I) { 01082 LatticeVal &IV = ValueState[&I]; 01083 if (IV.isOverdefined()) return; 01084 01085 SmallVector<Constant*, 8> Operands; 01086 Operands.reserve(I.getNumOperands()); 01087 01088 for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) { 01089 LatticeVal &State = getValueState(I.getOperand(i)); 01090 if (State.isUndefined()) 01091 return; // Operands are not resolved yet... 01092 else if (State.isOverdefined()) { 01093 markOverdefined(IV, &I); 01094 return; 01095 } 01096 assert(State.isConstant() && "Unknown state!"); 01097 Operands.push_back(State.getConstant()); 01098 } 01099 01100 Constant *Ptr = Operands[0]; 01101 Operands.erase(Operands.begin()); // Erase the pointer from idx list... 01102 01103 markConstant(IV, &I, ConstantExpr::getGetElementPtr(Ptr, &Operands[0], 01104 Operands.size())); 01105 } 01106 01107 void SCCPSolver::visitStoreInst(Instruction &SI) { 01108 if (TrackedGlobals.empty() || !isa<GlobalVariable>(SI.getOperand(1))) 01109 return; 01110 GlobalVariable *GV = cast<GlobalVariable>(SI.getOperand(1)); 01111 DenseMap<GlobalVariable*, LatticeVal>::iterator I = TrackedGlobals.find(GV); 01112 if (I == TrackedGlobals.end() || I->second.isOverdefined()) return; 01113 01114 // Get the value we are storing into the global. 01115 LatticeVal &PtrVal = getValueState(SI.getOperand(0)); 01116 01117 mergeInValue(I->second, GV, PtrVal); 01118 if (I->second.isOverdefined()) 01119 TrackedGlobals.erase(I); // No need to keep tracking this! 01120 } 01121 01122 01123 // Handle load instructions. If the operand is a constant pointer to a constant 01124 // global, we can replace the load with the loaded constant value! 01125 void SCCPSolver::visitLoadInst(LoadInst &I) { 01126 LatticeVal &IV = ValueState[&I]; 01127 if (IV.isOverdefined()) return; 01128 01129 LatticeVal &PtrVal = getValueState(I.getOperand(0)); 01130 if (PtrVal.isUndefined()) return; // The pointer is not resolved yet! 01131 if (PtrVal.isConstant() && !I.isVolatile()) { 01132 Value *Ptr = PtrVal.getConstant(); 01133 // TODO: Consider a target hook for valid address spaces for this xform. 01134 if (isa<ConstantPointerNull>(Ptr) && 01135 cast<PointerType>(Ptr->getType())->getAddressSpace() == 0) { 01136 // load null -> null 01137 markConstant(IV, &I, Constant::getNullValue(I.getType())); 01138 return; 01139 } 01140 01141 // Transform load (constant global) into the value loaded. 01142 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Ptr)) { 01143 if (GV->isConstant()) { 01144 if (GV->hasDefinitiveInitializer()) { 01145 markConstant(IV, &I, GV->getInitializer()); 01146 return; 01147 } 01148 } else if (!TrackedGlobals.empty()) { 01149 // If we are tracking this global, merge in the known value for it. 01150 DenseMap<GlobalVariable*, LatticeVal>::iterator It = 01151 TrackedGlobals.find(GV); 01152 if (It != TrackedGlobals.end()) { 01153 mergeInValue(IV, &I, It->second); 01154 return; 01155 } 01156 } 01157 } 01158 01159 // Transform load (constantexpr_GEP global, 0, ...) into the value loaded. 01160 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Ptr)) 01161 if (CE->getOpcode() == Instruction::GetElementPtr) 01162 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(CE->getOperand(0))) 01163 if (GV->isConstant() && GV->hasDefinitiveInitializer()) 01164 if (Constant *V = 01165 ConstantFoldLoadThroughGEPConstantExpr(GV->getInitializer(), CE, 01166 *Context)) { 01167 markConstant(IV, &I, V); 01168 return; 01169 } 01170 } 01171 01172 // Otherwise we cannot say for certain what value this load will produce. 01173 // Bail out. 01174 markOverdefined(IV, &I); 01175 } 01176 01177 void SCCPSolver::visitCallSite(CallSite CS) { 01178 Function *F = CS.getCalledFunction(); 01179 Instruction *I = CS.getInstruction(); 01180 01181 // The common case is that we aren't tracking the callee, either because we 01182 // are not doing interprocedural analysis or the callee is indirect, or is 01183 // external. Handle these cases first. 01184 if (F == 0 || !F->hasLocalLinkage()) { 01185 CallOverdefined: 01186 // Void return and not tracking callee, just bail. 01187 if (I->getType() == Type::getVoidTy(I->getContext())) return; 01188 01189 // Otherwise, if we have a single return value case, and if the function is 01190 // a declaration, maybe we can constant fold it. 01191 if (!isa<StructType>(I->getType()) && F && F->isDeclaration() && 01192 canConstantFoldCallTo(F)) { 01193 01194 SmallVector<Constant*, 8> Operands; 01195 for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end(); 01196 AI != E; ++AI) { 01197 LatticeVal &State = getValueState(*AI); 01198 if (State.isUndefined()) 01199 return; // Operands are not resolved yet. 01200 else if (State.isOverdefined()) { 01201 markOverdefined(I); 01202 return; 01203 } 01204 assert(State.isConstant() && "Unknown state!"); 01205 Operands.push_back(State.getConstant()); 01206 } 01207 01208 // If we can constant fold this, mark the result of the call as a 01209 // constant. 01210 if (Constant *C = ConstantFoldCall(F, Operands.data(), Operands.size())) { 01211 markConstant(I, C); 01212 return; 01213 } 01214 } 01215 01216 // Otherwise, we don't know anything about this call, mark it overdefined. 01217 markOverdefined(I); 01218 return; 01219 } 01220 01221 // If this is a single/zero retval case, see if we're tracking the function. 01222 DenseMap<Function*, LatticeVal>::iterator TFRVI = TrackedRetVals.find(F); 01223 if (TFRVI != TrackedRetVals.end()) { 01224 // If so, propagate the return value of the callee into this call result. 01225 mergeInValue(I, TFRVI->second); 01226 } else if (isa<StructType>(I->getType())) { 01227 // Check to see if we're tracking this callee, if not, handle it in the 01228 // common path above. 01229 DenseMap<std::pair<Function*, unsigned>, LatticeVal>::iterator 01230 TMRVI = TrackedMultipleRetVals.find(std::make_pair(F, 0)); 01231 if (TMRVI == TrackedMultipleRetVals.end()) 01232 goto CallOverdefined; 01233 01234 // If we are tracking this callee, propagate the return values of the call 01235 // into this call site. We do this by walking all the uses. Single-index 01236 // ExtractValueInst uses can be tracked; anything more complicated is 01237 // currently handled conservatively. 01238 for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); 01239 UI != E; ++UI) { 01240 if (ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(*UI)) { 01241 if (EVI->getNumIndices() == 1) { 01242 mergeInValue(EVI, 01243 TrackedMultipleRetVals[std::make_pair(F, *EVI->idx_begin())]); 01244 continue; 01245 } 01246 } 01247 // The aggregate value is used in a way not handled here. Assume nothing. 01248 markOverdefined(*UI); 01249 } 01250 } else { 01251 // Otherwise we're not tracking this callee, so handle it in the 01252 // common path above. 01253 goto CallOverdefined; 01254 } 01255 01256 // Finally, if this is the first call to the function hit, mark its entry 01257 // block executable. 01258 if (!BBExecutable.count(F->begin())) 01259 MarkBlockExecutable(F->begin()); 01260 01261 // Propagate information from this call site into the callee. 01262 CallSite::arg_iterator CAI = CS.arg_begin(); 01263 for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end(); 01264 AI != E; ++AI, ++CAI) { 01265 LatticeVal &IV = ValueState[AI]; 01266 if (AI->hasByValAttr() && isa<PointerType>(AI->getType())) { 01267 IV.markOverdefined(); 01268 continue; 01269 } 01270 if (!IV.isOverdefined()) 01271 mergeInValue(IV, AI, getValueState(*CAI)); 01272 } 01273 } 01274 01275 01276 void SCCPSolver::Solve() { 01277 // Process the work lists until they are empty! 01278 while (!BBWorkList.empty() || !InstWorkList.empty() || 01279 !OverdefinedInstWorkList.empty()) { 01280 // Process the instruction work list... 01281 while (!OverdefinedInstWorkList.empty()) { 01282 Value *I = OverdefinedInstWorkList.back(); 01283 OverdefinedInstWorkList.pop_back(); 01284 01285 DEBUG(errs() << "\nPopped off OI-WL: " << *I << '\n'); 01286 01287 // "I" got into the work list because it either made the transition from 01288 // bottom to constant 01289 // 01290 // Anything on this worklist that is overdefined need not be visited 01291 // since all of its users will have already been marked as overdefined 01292 // Update all of the users of this instruction's value... 01293 // 01294 for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); 01295 UI != E; ++UI) 01296 OperandChangedState(*UI); 01297 } 01298 // Process the instruction work list... 01299 while (!InstWorkList.empty()) { 01300 Value *I = InstWorkList.back(); 01301 InstWorkList.pop_back(); 01302 01303 DEBUG(errs() << "\nPopped off I-WL: " << *I << '\n'); 01304 01305 // "I" got into the work list because it either made the transition from 01306 // bottom to constant 01307 // 01308 // Anything on this worklist that is overdefined need not be visited 01309 // since all of its users will have already been marked as overdefined. 01310 // Update all of the users of this instruction's value... 01311 // 01312 if (!getValueState(I).isOverdefined()) 01313 for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); 01314 UI != E; ++UI) 01315 OperandChangedState(*UI); 01316 } 01317 01318 // Process the basic block work list... 01319 while (!BBWorkList.empty()) { 01320 BasicBlock *BB = BBWorkList.back(); 01321 BBWorkList.pop_back(); 01322 01323 DEBUG(errs() << "\nPopped off BBWL: " << *BB << '\n'); 01324 01325 // Notify all instructions in this basic block that they are newly 01326 // executable. 01327 visit(BB); 01328 } 01329 } 01330 } 01331 01332 /// ResolvedUndefsIn - While solving the dataflow for a function, we assume 01333 /// that branches on undef values cannot reach any of their successors. 01334 /// However, this is not a safe assumption. After we solve dataflow, this 01335 /// method should be use to handle this. If this returns true, the solver 01336 /// should be rerun. 01337 /// 01338 /// This method handles this by finding an unresolved branch and marking it one 01339 /// of the edges from the block as being feasible, even though the condition 01340 /// doesn't say it would otherwise be. This allows SCCP to find the rest of the 01341 /// CFG and only slightly pessimizes the analysis results (by marking one, 01342 /// potentially infeasible, edge feasible). This cannot usefully modify the 01343 /// constraints on the condition of the branch, as that would impact other users 01344 /// of the value. 01345 /// 01346 /// This scan also checks for values that use undefs, whose results are actually 01347 /// defined. For example, 'zext i8 undef to i32' should produce all zeros 01348 /// conservatively, as "(zext i8 X -> i32) & 0xFF00" must always return zero, 01349 /// even if X isn't defined. 01350 bool SCCPSolver::ResolvedUndefsIn(Function &F) { 01351 for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) { 01352 if (!BBExecutable.count(BB)) 01353 continue; 01354 01355 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) { 01356 // Look for instructions which produce undef values. 01357 if (I->getType() == Type::getVoidTy(F.getContext())) continue; 01358 01359 LatticeVal &LV = getValueState(I); 01360 if (!LV.isUndefined()) continue; 01361 01362 // Get the lattice values of the first two operands for use below. 01363 LatticeVal &Op0LV = getValueState(I->getOperand(0)); 01364 LatticeVal Op1LV; 01365 if (I->getNumOperands() == 2) { 01366 // If this is a two-operand instruction, and if both operands are 01367 // undefs, the result stays undef. 01368 Op1LV = getValueState(I->getOperand(1)); 01369 if (Op0LV.isUndefined() && Op1LV.isUndefined()) 01370 continue; 01371 } 01372 01373 // If this is an instructions whose result is defined even if the input is 01374 // not fully defined, propagate the information. 01375 const Type *ITy = I->getType(); 01376 switch (I->getOpcode()) { 01377 default: break; // Leave the instruction as an undef. 01378 case Instruction::ZExt: 01379 // After a zero extend, we know the top part is zero. SExt doesn't have 01380 // to be handled here, because we don't know whether the top part is 1's 01381 // or 0's. 01382 assert(Op0LV.isUndefined()); 01383 markForcedConstant(LV, I, Constant::getNullValue(ITy)); 01384 return true; 01385 case Instruction::Mul: 01386 case Instruction::And: 01387 // undef * X -> 0. X could be zero. 01388 // undef & X -> 0. X could be zero. 01389 markForcedConstant(LV, I, Constant::getNullValue(ITy)); 01390 return true; 01391 01392 case Instruction::Or: 01393 // undef | X -> -1. X could be -1. 01394 if (const VectorType *PTy = dyn_cast<VectorType>(ITy)) 01395 markForcedConstant(LV, I, 01396 Constant::getAllOnesValue(PTy)); 01397 else 01398 markForcedConstant(LV, I, Constant::getAllOnesValue(ITy)); 01399 return true; 01400 01401 case Instruction::SDiv: 01402 case Instruction::UDiv: 01403 case Instruction::SRem: 01404 case Instruction::URem: 01405 // X / undef -> undef. No change. 01406 // X % undef -> undef. No change. 01407 if (Op1LV.isUndefined()) break; 01408 01409 // undef / X -> 0. X could be maxint. 01410 // undef % X -> 0. X could be 1. 01411 markForcedConstant(LV, I, Constant::getNullValue(ITy)); 01412 return true; 01413 01414 case Instruction::AShr: 01415 // undef >>s X -> undef. No change. 01416 if (Op0LV.isUndefined()) break; 01417 01418 // X >>s undef -> X. X could be 0, X could have the high-bit known set. 01419 if (Op0LV.isConstant()) 01420 markForcedConstant(LV, I, Op0LV.getConstant()); 01421 else 01422 markOverdefined(LV, I); 01423 return true; 01424 case Instruction::LShr: 01425 case Instruction::Shl: 01426 // undef >> X -> undef. No change. 01427 // undef << X -> undef. No change. 01428 if (Op0LV.isUndefined()) break; 01429 01430 // X >> undef -> 0. X could be 0. 01431 // X << undef -> 0. X could be 0. 01432 markForcedConstant(LV, I, Constant::getNullValue(ITy)); 01433 return true; 01434 case Instruction::Select: 01435 // undef ? X : Y -> X or Y. There could be commonality between X/Y. 01436 if (Op0LV.isUndefined()) { 01437 if (!Op1LV.isConstant()) // Pick the constant one if there is any. 01438 Op1LV = getValueState(I->getOperand(2)); 01439 } else if (Op1LV.isUndefined()) { 01440 // c ? undef : undef -> undef. No change. 01441 Op1LV = getValueState(I->getOperand(2)); 01442 if (Op1LV.isUndefined()) 01443 break; 01444 // Otherwise, c ? undef : x -> x. 01445 } else { 01446 // Leave Op1LV as Operand(1)'s LatticeValue. 01447 } 01448 01449 if (Op1LV.isConstant()) 01450 markForcedConstant(LV, I, Op1LV.getConstant()); 01451 else 01452 markOverdefined(LV, I); 01453 return true; 01454 case Instruction::Call: 01455 // If a call has an undef result, it is because it is constant foldable 01456 // but one of the inputs was undef. Just force the result to 01457 // overdefined. 01458 markOverdefined(LV, I); 01459 return true; 01460 } 01461 } 01462 01463 TerminatorInst *TI = BB->getTerminator(); 01464 if (BranchInst *BI = dyn_cast<BranchInst>(TI)) { 01465 if (!BI->isConditional()) continue; 01466 if (!getValueState(BI->getCondition()).isUndefined()) 01467 continue; 01468 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 01469 if (SI->getNumSuccessors()<2) // no cases 01470 continue; 01471 if (!getValueState(SI->getCondition()).isUndefined()) 01472 continue; 01473 } else { 01474 continue; 01475 } 01476 01477 // If the edge to the second successor isn't thought to be feasible yet, 01478 // mark it so now. We pick the second one so that this goes to some 01479 // enumerated value in a switch instead of going to the default destination. 01480 if (KnownFeasibleEdges.count(Edge(BB, TI->getSuccessor(1)))) 01481 continue; 01482 01483 // Otherwise, it isn't already thought to be feasible. Mark it as such now 01484 // and return. This will make other blocks reachable, which will allow new 01485 // values to be discovered and existing ones to be moved in the lattice. 01486 markEdgeExecutable(BB, TI->getSuccessor(1)); 01487 01488 // This must be a conditional branch of switch on undef. At this point, 01489 // force the old terminator to branch to the first successor. This is 01490 // required because we are now influencing the dataflow of the function with 01491 // the assumption that this edge is taken. If we leave the branch condition 01492 // as undef, then further analysis could think the undef went another way 01493 // leading to an inconsistent set of conclusions. 01494 if (BranchInst *BI = dyn_cast<BranchInst>(TI)) { 01495 BI->setCondition(ConstantInt::getFalse(*Context)); 01496 } else { 01497 SwitchInst *SI = cast<SwitchInst>(TI); 01498 SI->setCondition(SI->getCaseValue(1)); 01499 } 01500 01501 return true; 01502 } 01503 01504 return false; 01505 } 01506 01507 01508 namespace { 01509 //===--------------------------------------------------------------------===// 01510 // 01511 /// SCCP Class - This class uses the SCCPSolver to implement a per-function 01512 /// Sparse Conditional Constant Propagator. 01513 /// 01514 struct VISIBILITY_HIDDEN SCCP : public FunctionPass { 01515 static char ID; // Pass identification, replacement for typeid 01516 SCCP() : FunctionPass(&ID) {} 01517 01518 // runOnFunction - Run the Sparse Conditional Constant Propagation 01519 // algorithm, and return true if the function was modified. 01520 // 01521 bool runOnFunction(Function &F); 01522 01523 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 01524 AU.setPreservesCFG(); 01525 } 01526 }; 01527 } // end anonymous namespace 01528 01529 char SCCP::ID = 0; 01530 static RegisterPass<SCCP> 01531 X("sccp", "Sparse Conditional Constant Propagation"); 01532 01533 // createSCCPPass - This is the public interface to this file... 01534 FunctionPass *llvm::createSCCPPass() { 01535 return new SCCP(); 01536 } 01537 01538 01539 // runOnFunction() - Run the Sparse Conditional Constant Propagation algorithm, 01540 // and return true if the function was modified. 01541 // 01542 bool SCCP::runOnFunction(Function &F) { 01543 DEBUG(errs() << "SCCP on function '" << F.getName() << "'\n"); 01544 SCCPSolver Solver; 01545 Solver.setContext(&F.getContext()); 01546 01547 // Mark the first block of the function as being executable. 01548 Solver.MarkBlockExecutable(F.begin()); 01549 01550 // Mark all arguments to the function as being overdefined. 01551 for (Function::arg_iterator AI = F.arg_begin(), E = F.arg_end(); AI != E;++AI) 01552 Solver.markOverdefined(AI); 01553 01554 // Solve for constants. 01555 bool ResolvedUndefs = true; 01556 while (ResolvedUndefs) { 01557 Solver.Solve(); 01558 DEBUG(errs() << "RESOLVING UNDEFs\n"); 01559 ResolvedUndefs = Solver.ResolvedUndefsIn(F); 01560 } 01561 01562 bool MadeChanges = false; 01563 01564 // If we decided that there are basic blocks that are dead in this function, 01565 // delete their contents now. Note that we cannot actually delete the blocks, 01566 // as we cannot modify the CFG of the function. 01567 // 01568 SmallVector<Instruction*, 512> Insts; 01569 std::map<Value*, LatticeVal> &Values = Solver.getValueMapping(); 01570 01571 for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) 01572 if (!Solver.isBlockExecutable(BB)) { 01573 DEBUG(errs() << " BasicBlock Dead:" << *BB); 01574 ++NumDeadBlocks; 01575 01576 // Delete the instructions backwards, as it has a reduced likelihood of 01577 // having to update as many def-use and use-def chains. 01578 for (BasicBlock::iterator I = BB->begin(), E = BB->getTerminator(); 01579 I != E; ++I) 01580 Insts.push_back(I); 01581 while (!Insts.empty()) { 01582 Instruction *I = Insts.back(); 01583 Insts.pop_back(); 01584 if (!I->use_empty()) 01585 I->replaceAllUsesWith(UndefValue::get(I->getType())); 01586 BB->getInstList().erase(I); 01587 MadeChanges = true; 01588 ++NumInstRemoved; 01589 } 01590 } else { 01591 // Iterate over all of the instructions in a function, replacing them with 01592 // constants if we have found them to be of constant values. 01593 // 01594 for (BasicBlock::iterator BI = BB->begin(), E = BB->end(); BI != E; ) { 01595 Instruction *Inst = BI++; 01596 if (Inst->getType() == Type::getVoidTy(F.getContext()) || 01597 isa<TerminatorInst>(Inst)) 01598 continue; 01599 01600 LatticeVal &IV = Values[Inst]; 01601 if (!IV.isConstant() && !IV.isUndefined()) 01602 continue; 01603 01604 Constant *Const = IV.isConstant() 01605 ? IV.getConstant() : UndefValue::get(Inst->getType()); 01606 DEBUG(errs() << " Constant: " << *Const << " = " << *Inst); 01607 01608 // Replaces all of the uses of a variable with uses of the constant. 01609 Inst->replaceAllUsesWith(Const); 01610 01611 // Delete the instruction. 01612 Inst->eraseFromParent(); 01613 01614 // Hey, we just changed something! 01615 MadeChanges = true; 01616 ++NumInstRemoved; 01617 } 01618 } 01619 01620 return MadeChanges; 01621 } 01622 01623 namespace { 01624 //===--------------------------------------------------------------------===// 01625 // 01626 /// IPSCCP Class - This class implements interprocedural Sparse Conditional 01627 /// Constant Propagation. 01628 /// 01629 struct VISIBILITY_HIDDEN IPSCCP : public ModulePass { 01630 static char ID; 01631 IPSCCP() : ModulePass(&ID) {} 01632 bool runOnModule(Module &M); 01633 }; 01634 } // end anonymous namespace 01635 01636 char IPSCCP::ID = 0; 01637 static RegisterPass<IPSCCP> 01638 Y("ipsccp", "Interprocedural Sparse Conditional Constant Propagation"); 01639 01640 // createIPSCCPPass - This is the public interface to this file... 01641 ModulePass *llvm::createIPSCCPPass() { 01642 return new IPSCCP(); 01643 } 01644 01645 01646 static bool AddressIsTaken(GlobalValue *GV) { 01647 // Delete any dead constantexpr klingons. 01648 GV->removeDeadConstantUsers(); 01649 01650 for (Value::use_iterator UI = GV->use_begin(), E = GV->use_end(); 01651 UI != E; ++UI) 01652 if (StoreInst *SI = dyn_cast<StoreInst>(*UI)) { 01653 if (SI->getOperand(0) == GV || SI->isVolatile()) 01654 return true; // Storing addr of GV. 01655 } else if (isa<InvokeInst>(*UI) || isa<CallInst>(*UI)) { 01656 // Make sure we are calling the function, not passing the address. 01657 CallSite CS = CallSite::get(cast<Instruction>(*UI)); 01658 if (CS.hasArgument(GV)) 01659 return true; 01660 } else if (LoadInst *LI = dyn_cast<LoadInst>(*UI)) { 01661 if (LI->isVolatile()) 01662 return true; 01663 } else { 01664 return true; 01665 } 01666 return false; 01667 } 01668 01669 bool IPSCCP::runOnModule(Module &M) { 01670 LLVMContext *Context = &M.getContext(); 01671 01672 SCCPSolver Solver; 01673 Solver.setContext(Context); 01674 01675 // Loop over all functions, marking arguments to those with their addresses 01676 // taken or that are external as overdefined. 01677 // 01678 for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) 01679 if (!F->hasLocalLinkage() || AddressIsTaken(F)) { 01680 if (!F->isDeclaration()) 01681 Solver.MarkBlockExecutable(F->begin()); 01682 for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end(); 01683 AI != E; ++AI) 01684 Solver.markOverdefined(AI); 01685 } else { 01686 Solver.AddTrackedFunction(F); 01687 } 01688 01689 // Loop over global variables. We inform the solver about any internal global 01690 // variables that do not have their 'addresses taken'. If they don't have 01691 // their addresses taken, we can propagate constants through them. 01692 for (Module::global_iterator G = M.global_begin(), E = M.global_end(); 01693 G != E; ++G) 01694 if (!G->isConstant() && G->hasLocalLinkage() && !AddressIsTaken(G)) 01695 Solver.TrackValueOfGlobalVariable(G); 01696 01697 // Solve for constants. 01698 bool ResolvedUndefs = true; 01699 while (ResolvedUndefs) { 01700 Solver.Solve(); 01701 01702 DEBUG(errs() << "RESOLVING UNDEFS\n"); 01703 ResolvedUndefs = false; 01704 for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) 01705 ResolvedUndefs |= Solver.ResolvedUndefsIn(*F); 01706 } 01707 01708 bool MadeChanges = false; 01709 01710 // Iterate over all of the instructions in the module, replacing them with 01711 // constants if we have found them to be of constant values. 01712 // 01713 SmallVector<Instruction*, 512> Insts; 01714 SmallVector<BasicBlock*, 512> BlocksToErase; 01715 std::map<Value*, LatticeVal> &Values = Solver.getValueMapping(); 01716 01717 for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) { 01718 for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end(); 01719 AI != E; ++AI) 01720 if (!AI->use_empty()) { 01721 LatticeVal &IV = Values[AI]; 01722 if (IV.isConstant() || IV.isUndefined()) { 01723 Constant *CST = IV.isConstant() ? 01724 IV.getConstant() : UndefValue::get(AI->getType()); 01725 DEBUG(errs() << "*** Arg " << *AI << " = " << *CST <<"\n"); 01726 01727 // Replaces all of the uses of a variable with uses of the 01728 // constant. 01729 AI->replaceAllUsesWith(CST); 01730 ++IPNumArgsElimed; 01731 } 01732 } 01733 01734 for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) 01735 if (!Solver.isBlockExecutable(BB)) { 01736 DEBUG(errs() << " BasicBlock Dead:" << *BB); 01737 ++IPNumDeadBlocks; 01738 01739 // Delete the instructions backwards, as it has a reduced likelihood of 01740 // having to update as many def-use and use-def chains. 01741 TerminatorInst *TI = BB->getTerminator(); 01742 for (BasicBlock::iterator I = BB->begin(), E = TI; I != E; ++I) 01743 Insts.push_back(I); 01744 01745 while (!Insts.empty()) { 01746 Instruction *I = Insts.back(); 01747 Insts.pop_back(); 01748 if (!I->use_empty()) 01749 I->replaceAllUsesWith(UndefValue::get(I->getType())); 01750 BB->getInstList().erase(I); 01751 MadeChanges = true; 01752 ++IPNumInstRemoved; 01753 } 01754 01755 for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) { 01756 BasicBlock *Succ = TI->getSuccessor(i); 01757 if (!Succ->empty() && isa<PHINode>(Succ->begin())) 01758 TI->getSuccessor(i)->removePredecessor(BB); 01759 } 01760 if (!TI->use_empty()) 01761 TI->replaceAllUsesWith(UndefValue::get(TI->getType())); 01762 BB->getInstList().erase(TI); 01763 01764 if (&*BB != &F->front()) 01765 BlocksToErase.push_back(BB); 01766 else 01767 new UnreachableInst(M.getContext(), BB); 01768 01769 } else { 01770 for (BasicBlock::iterator BI = BB->begin(), E = BB->end(); BI != E; ) { 01771 Instruction *Inst = BI++; 01772 if (Inst->getType() == Type::getVoidTy(M.getContext())) 01773 continue; 01774 01775 LatticeVal &IV = Values[Inst]; 01776 if (!IV.isConstant() && !IV.isUndefined()) 01777 continue; 01778 01779 Constant *Const = IV.isConstant() 01780 ? IV.getConstant() : UndefValue::get(Inst->getType()); 01781 DEBUG(errs() << " Constant: " << *Const << " = " << *Inst); 01782 01783 // Replaces all of the uses of a variable with uses of the 01784 // constant. 01785 Inst->replaceAllUsesWith(Const); 01786 01787 // Delete the instruction. 01788 if (!isa<CallInst>(Inst) && !isa<TerminatorInst>(Inst)) 01789 Inst->eraseFromParent(); 01790 01791 // Hey, we just changed something! 01792 MadeChanges = true; 01793 ++IPNumInstRemoved; 01794 } 01795 } 01796 01797 // Now that all instructions in the function are constant folded, erase dead 01798 // blocks, because we can now use ConstantFoldTerminator to get rid of 01799 // in-edges. 01800 for (unsigned i = 0, e = BlocksToErase.size(); i != e; ++i) { 01801 // If there are any PHI nodes in this successor, drop entries for BB now. 01802 BasicBlock *DeadBB = BlocksToErase[i]; 01803 while (!DeadBB->use_empty()) { 01804 Instruction *I = cast<Instruction>(DeadBB->use_back()); 01805 bool Folded = ConstantFoldTerminator(I->getParent()); 01806 if (!Folded) { 01807 // The constant folder may not have been able to fold the terminator 01808 // if this is a branch or switch on undef. Fold it manually as a 01809 // branch to the first successor. 01810 #ifndef NDEBUG 01811 if (BranchInst *BI = dyn_cast<BranchInst>(I)) { 01812 assert(BI->isConditional() && isa<UndefValue>(BI->getCondition()) && 01813 "Branch should be foldable!"); 01814 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(I)) { 01815 assert(isa<UndefValue>(SI->getCondition()) && "Switch should fold"); 01816 } else { 01817 llvm_unreachable("Didn't fold away reference to block!"); 01818 } 01819 #endif 01820 01821 // Make this an uncond branch to the first successor. 01822 TerminatorInst *TI = I->getParent()->getTerminator(); 01823 BranchInst::Create(TI->getSuccessor(0), TI); 01824 01825 // Remove entries in successor phi nodes to remove edges. 01826 for (unsigned i = 1, e = TI->getNumSuccessors(); i != e; ++i) 01827 TI->getSuccessor(i)->removePredecessor(TI->getParent()); 01828 01829 // Remove the old terminator. 01830 TI->eraseFromParent(); 01831 } 01832 } 01833 01834 // Finally, delete the basic block. 01835 F->getBasicBlockList().erase(DeadBB); 01836 } 01837 BlocksToErase.clear(); 01838 } 01839 01840 // If we inferred constant or undef return values for a function, we replaced 01841 // all call uses with the inferred value. This means we don't need to bother 01842 // actually returning anything from the function. Replace all return 01843 // instructions with return undef. 01844 // TODO: Process multiple value ret instructions also. 01845 const DenseMap<Function*, LatticeVal> &RV = Solver.getTrackedRetVals(); 01846 for (DenseMap<Function*, LatticeVal>::const_iterator I = RV.begin(), 01847 E = RV.end(); I != E; ++I) 01848 if (!I->second.isOverdefined() && 01849 I->first->getReturnType() != Type::getVoidTy(M.getContext())) { 01850 Function *F = I->first; 01851 for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) 01852 if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) 01853 if (!isa<UndefValue>(RI->getOperand(0))) 01854 RI->setOperand(0, UndefValue::get(F->getReturnType())); 01855 } 01856 01857 // If we infered constant or undef values for globals variables, we can delete 01858 // the global and any stores that remain to it. 01859 const DenseMap<GlobalVariable*, LatticeVal> &TG = Solver.getTrackedGlobals(); 01860 for (DenseMap<GlobalVariable*, LatticeVal>::const_iterator I = TG.begin(), 01861 E = TG.end(); I != E; ++I) { 01862 GlobalVariable *GV = I->first; 01863 assert(!I->second.isOverdefined() && 01864 "Overdefined values should have been taken out of the map!"); 01865 DEBUG(errs() << "Found that GV '" << GV->getName() << "' is constant!\n"); 01866 while (!GV->use_empty()) { 01867 StoreInst *SI = cast<StoreInst>(GV->use_back()); 01868 SI->eraseFromParent(); 01869 } 01870 M.getGlobalList().erase(GV); 01871 ++IPNumGlobalConst; 01872 } 01873 01874 return MadeChanges; 01875 }