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/Constants.h" 00027 #include "llvm/Function.h" 00028 #include "llvm/GlobalVariable.h" 00029 #include "llvm/Instructions.h" 00030 #include "llvm/Pass.h" 00031 #include "llvm/Type.h" 00032 #include "llvm/Support/InstVisitor.h" 00033 #include "llvm/Transforms/Utils/Local.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 <set> 00040 using namespace llvm; 00041 00042 // LatticeVal class - This class represents the different lattice values that an 00043 // instruction may occupy. It is a simple class with value semantics. 00044 // 00045 namespace { 00046 Statistic<> NumInstRemoved("sccp", "Number of instructions removed"); 00047 Statistic<> NumDeadBlocks ("sccp", "Number of basic blocks unreachable"); 00048 00049 class LatticeVal { 00050 enum { 00051 undefined, // This instruction has no known value 00052 constant, // This instruction has a constant value 00053 overdefined // This instruction has an unknown value 00054 } LatticeValue; // The current lattice position 00055 Constant *ConstantVal; // If Constant value, the current value 00056 public: 00057 inline LatticeVal() : LatticeValue(undefined), ConstantVal(0) {} 00058 00059 // markOverdefined - Return true if this is a new status to be in... 00060 inline bool markOverdefined() { 00061 if (LatticeValue != overdefined) { 00062 LatticeValue = overdefined; 00063 return true; 00064 } 00065 return false; 00066 } 00067 00068 // markConstant - Return true if this is a new status for us... 00069 inline bool markConstant(Constant *V) { 00070 if (LatticeValue != constant) { 00071 LatticeValue = constant; 00072 ConstantVal = V; 00073 return true; 00074 } else { 00075 assert(ConstantVal == V && "Marking constant with different value"); 00076 } 00077 return false; 00078 } 00079 00080 inline bool isUndefined() const { return LatticeValue == undefined; } 00081 inline bool isConstant() const { return LatticeValue == constant; } 00082 inline bool isOverdefined() const { return LatticeValue == overdefined; } 00083 00084 inline Constant *getConstant() const { 00085 assert(isConstant() && "Cannot get the constant of a non-constant!"); 00086 return ConstantVal; 00087 } 00088 }; 00089 00090 } // end anonymous namespace 00091 00092 00093 //===----------------------------------------------------------------------===// 00094 // 00095 /// SCCPSolver - This class is a general purpose solver for Sparse Conditional 00096 /// Constant Propagation. 00097 /// 00098 class SCCPSolver : public InstVisitor<SCCPSolver> { 00099 std::set<BasicBlock*> BBExecutable;// The basic blocks that are executable 00100 hash_map<Value*, LatticeVal> ValueState; // The state each value is in... 00101 00102 // The reason for two worklists is that overdefined is the lowest state 00103 // on the lattice, and moving things to overdefined as fast as possible 00104 // makes SCCP converge much faster. 00105 // By having a separate worklist, we accomplish this because everything 00106 // possibly overdefined will become overdefined at the soonest possible 00107 // point. 00108 std::vector<Instruction*> OverdefinedInstWorkList;// The overdefined 00109 // instruction work list 00110 std::vector<Instruction*> InstWorkList;// The instruction work list 00111 00112 00113 std::vector<BasicBlock*> BBWorkList; // The BasicBlock work list 00114 00115 /// UsersOfOverdefinedPHIs - Keep track of any users of PHI nodes that are not 00116 /// overdefined, despite the fact that the PHI node is overdefined. 00117 std::multimap<PHINode*, Instruction*> UsersOfOverdefinedPHIs; 00118 00119 /// KnownFeasibleEdges - Entries in this set are edges which have already had 00120 /// PHI nodes retriggered. 00121 typedef std::pair<BasicBlock*,BasicBlock*> Edge; 00122 std::set<Edge> KnownFeasibleEdges; 00123 public: 00124 00125 /// MarkBlockExecutable - This method can be used by clients to mark all of 00126 /// the blocks that are known to be intrinsically live in the processed unit. 00127 void MarkBlockExecutable(BasicBlock *BB) { 00128 DEBUG(std::cerr << "Marking Block Executable: " << BB->getName() << "\n"); 00129 BBExecutable.insert(BB); // Basic block is executable! 00130 BBWorkList.push_back(BB); // Add the block to the work list! 00131 } 00132 00133 /// Solve - Solve for constants and executable blocks. 00134 /// 00135 void Solve(); 00136 00137 /// getExecutableBlocks - Once we have solved for constants, return the set of 00138 /// blocks that is known to be executable. 00139 std::set<BasicBlock*> &getExecutableBlocks() { 00140 return BBExecutable; 00141 } 00142 00143 /// getValueMapping - Once we have solved for constants, return the mapping of 00144 /// LLVM values to LatticeVals. 00145 hash_map<Value*, LatticeVal> &getValueMapping() { 00146 return ValueState; 00147 } 00148 00149 private: 00150 // markConstant - Make a value be marked as "constant". If the value 00151 // is not already a constant, add it to the instruction work list so that 00152 // the users of the instruction are updated later. 00153 // 00154 inline void markConstant(LatticeVal &IV, Instruction *I, Constant *C) { 00155 if (IV.markConstant(C)) { 00156 DEBUG(std::cerr << "markConstant: " << *C << ": " << *I); 00157 InstWorkList.push_back(I); 00158 } 00159 } 00160 inline void markConstant(Instruction *I, Constant *C) { 00161 markConstant(ValueState[I], I, C); 00162 } 00163 00164 // markOverdefined - Make a value be marked as "overdefined". If the 00165 // value is not already overdefined, add it to the overdefined instruction 00166 // work list so that the users of the instruction are updated later. 00167 00168 inline void markOverdefined(LatticeVal &IV, Instruction *I) { 00169 if (IV.markOverdefined()) { 00170 DEBUG(std::cerr << "markOverdefined: " << *I); 00171 // Only instructions go on the work list 00172 OverdefinedInstWorkList.push_back(I); 00173 } 00174 } 00175 inline void markOverdefined(Instruction *I) { 00176 markOverdefined(ValueState[I], I); 00177 } 00178 00179 // getValueState - Return the LatticeVal object that corresponds to the value. 00180 // This function is necessary because not all values should start out in the 00181 // underdefined state... Argument's should be overdefined, and 00182 // constants should be marked as constants. If a value is not known to be an 00183 // Instruction object, then use this accessor to get its value from the map. 00184 // 00185 inline LatticeVal &getValueState(Value *V) { 00186 hash_map<Value*, LatticeVal>::iterator I = ValueState.find(V); 00187 if (I != ValueState.end()) return I->second; // Common case, in the map 00188 00189 if (Constant *CPV = dyn_cast<Constant>(V)) { 00190 if (isa<UndefValue>(V)) { 00191 // Nothing to do, remain undefined. 00192 } else { 00193 ValueState[CPV].markConstant(CPV); // Constants are constant 00194 } 00195 } 00196 // All others are underdefined by default... 00197 return ValueState[V]; 00198 } 00199 00200 // markEdgeExecutable - Mark a basic block as executable, adding it to the BB 00201 // work list if it is not already executable... 00202 // 00203 void markEdgeExecutable(BasicBlock *Source, BasicBlock *Dest) { 00204 if (!KnownFeasibleEdges.insert(Edge(Source, Dest)).second) 00205 return; // This edge is already known to be executable! 00206 00207 if (BBExecutable.count(Dest)) { 00208 DEBUG(std::cerr << "Marking Edge Executable: " << Source->getName() 00209 << " -> " << Dest->getName() << "\n"); 00210 00211 // The destination is already executable, but we just made an edge 00212 // feasible that wasn't before. Revisit the PHI nodes in the block 00213 // because they have potentially new operands. 00214 for (BasicBlock::iterator I = Dest->begin(); isa<PHINode>(I); ++I) { 00215 PHINode *PN = cast<PHINode>(I); 00216 visitPHINode(*PN); 00217 } 00218 00219 } else { 00220 MarkBlockExecutable(Dest); 00221 } 00222 } 00223 00224 // getFeasibleSuccessors - Return a vector of booleans to indicate which 00225 // successors are reachable from a given terminator instruction. 00226 // 00227 void getFeasibleSuccessors(TerminatorInst &TI, std::vector<bool> &Succs); 00228 00229 // isEdgeFeasible - Return true if the control flow edge from the 'From' basic 00230 // block to the 'To' basic block is currently feasible... 00231 // 00232 bool isEdgeFeasible(BasicBlock *From, BasicBlock *To); 00233 00234 // OperandChangedState - This method is invoked on all of the users of an 00235 // instruction that was just changed state somehow.... Based on this 00236 // information, we need to update the specified user of this instruction. 00237 // 00238 void OperandChangedState(User *U) { 00239 // Only instructions use other variable values! 00240 Instruction &I = cast<Instruction>(*U); 00241 if (BBExecutable.count(I.getParent())) // Inst is executable? 00242 visit(I); 00243 } 00244 00245 private: 00246 friend class InstVisitor<SCCPSolver>; 00247 00248 // visit implementations - Something changed in this instruction... Either an 00249 // operand made a transition, or the instruction is newly executable. Change 00250 // the value type of I to reflect these changes if appropriate. 00251 // 00252 void visitPHINode(PHINode &I); 00253 00254 // Terminators 00255 void visitReturnInst(ReturnInst &I) { /*does not have an effect*/ } 00256 void visitTerminatorInst(TerminatorInst &TI); 00257 00258 void visitCastInst(CastInst &I); 00259 void visitSelectInst(SelectInst &I); 00260 void visitBinaryOperator(Instruction &I); 00261 void visitShiftInst(ShiftInst &I) { visitBinaryOperator(I); } 00262 00263 // Instructions that cannot be folded away... 00264 void visitStoreInst (Instruction &I) { /*returns void*/ } 00265 void visitLoadInst (LoadInst &I); 00266 void visitGetElementPtrInst(GetElementPtrInst &I); 00267 void visitCallInst (CallInst &I); 00268 void visitInvokeInst (TerminatorInst &I) { 00269 if (I.getType() != Type::VoidTy) markOverdefined(&I); 00270 visitTerminatorInst(I); 00271 } 00272 void visitUnwindInst (TerminatorInst &I) { /*returns void*/ } 00273 void visitUnreachableInst(TerminatorInst &I) { /*returns void*/ } 00274 void visitAllocationInst(Instruction &I) { markOverdefined(&I); } 00275 void visitVANextInst (Instruction &I) { markOverdefined(&I); } 00276 void visitVAArgInst (Instruction &I) { markOverdefined(&I); } 00277 void visitFreeInst (Instruction &I) { /*returns void*/ } 00278 00279 void visitInstruction(Instruction &I) { 00280 // If a new instruction is added to LLVM that we don't handle... 00281 std::cerr << "SCCP: Don't know how to handle: " << I; 00282 markOverdefined(&I); // Just in case 00283 } 00284 }; 00285 00286 // getFeasibleSuccessors - Return a vector of booleans to indicate which 00287 // successors are reachable from a given terminator instruction. 00288 // 00289 void SCCPSolver::getFeasibleSuccessors(TerminatorInst &TI, 00290 std::vector<bool> &Succs) { 00291 Succs.resize(TI.getNumSuccessors()); 00292 if (BranchInst *BI = dyn_cast<BranchInst>(&TI)) { 00293 if (BI->isUnconditional()) { 00294 Succs[0] = true; 00295 } else { 00296 LatticeVal &BCValue = getValueState(BI->getCondition()); 00297 if (BCValue.isOverdefined() || 00298 (BCValue.isConstant() && !isa<ConstantBool>(BCValue.getConstant()))) { 00299 // Overdefined condition variables, and branches on unfoldable constant 00300 // conditions, mean the branch could go either way. 00301 Succs[0] = Succs[1] = true; 00302 } else if (BCValue.isConstant()) { 00303 // Constant condition variables mean the branch can only go a single way 00304 Succs[BCValue.getConstant() == ConstantBool::False] = true; 00305 } 00306 } 00307 } else if (InvokeInst *II = dyn_cast<InvokeInst>(&TI)) { 00308 // Invoke instructions successors are always executable. 00309 Succs[0] = Succs[1] = true; 00310 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(&TI)) { 00311 LatticeVal &SCValue = getValueState(SI->getCondition()); 00312 if (SCValue.isOverdefined() || // Overdefined condition? 00313 (SCValue.isConstant() && !isa<ConstantInt>(SCValue.getConstant()))) { 00314 // All destinations are executable! 00315 Succs.assign(TI.getNumSuccessors(), true); 00316 } else if (SCValue.isConstant()) { 00317 Constant *CPV = SCValue.getConstant(); 00318 // Make sure to skip the "default value" which isn't a value 00319 for (unsigned i = 1, E = SI->getNumSuccessors(); i != E; ++i) { 00320 if (SI->getSuccessorValue(i) == CPV) {// Found the right branch... 00321 Succs[i] = true; 00322 return; 00323 } 00324 } 00325 00326 // Constant value not equal to any of the branches... must execute 00327 // default branch then... 00328 Succs[0] = true; 00329 } 00330 } else { 00331 std::cerr << "SCCP: Don't know how to handle: " << TI; 00332 Succs.assign(TI.getNumSuccessors(), true); 00333 } 00334 } 00335 00336 00337 // isEdgeFeasible - Return true if the control flow edge from the 'From' basic 00338 // block to the 'To' basic block is currently feasible... 00339 // 00340 bool SCCPSolver::isEdgeFeasible(BasicBlock *From, BasicBlock *To) { 00341 assert(BBExecutable.count(To) && "Dest should always be alive!"); 00342 00343 // Make sure the source basic block is executable!! 00344 if (!BBExecutable.count(From)) return false; 00345 00346 // Check to make sure this edge itself is actually feasible now... 00347 TerminatorInst *TI = From->getTerminator(); 00348 if (BranchInst *BI = dyn_cast<BranchInst>(TI)) { 00349 if (BI->isUnconditional()) 00350 return true; 00351 else { 00352 LatticeVal &BCValue = getValueState(BI->getCondition()); 00353 if (BCValue.isOverdefined()) { 00354 // Overdefined condition variables mean the branch could go either way. 00355 return true; 00356 } else if (BCValue.isConstant()) { 00357 // Not branching on an evaluatable constant? 00358 if (!isa<ConstantBool>(BCValue.getConstant())) return true; 00359 00360 // Constant condition variables mean the branch can only go a single way 00361 return BI->getSuccessor(BCValue.getConstant() == 00362 ConstantBool::False) == To; 00363 } 00364 return false; 00365 } 00366 } else if (InvokeInst *II = dyn_cast<InvokeInst>(TI)) { 00367 // Invoke instructions successors are always executable. 00368 return true; 00369 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 00370 LatticeVal &SCValue = getValueState(SI->getCondition()); 00371 if (SCValue.isOverdefined()) { // Overdefined condition? 00372 // All destinations are executable! 00373 return true; 00374 } else if (SCValue.isConstant()) { 00375 Constant *CPV = SCValue.getConstant(); 00376 if (!isa<ConstantInt>(CPV)) 00377 return true; // not a foldable constant? 00378 00379 // Make sure to skip the "default value" which isn't a value 00380 for (unsigned i = 1, E = SI->getNumSuccessors(); i != E; ++i) 00381 if (SI->getSuccessorValue(i) == CPV) // Found the taken branch... 00382 return SI->getSuccessor(i) == To; 00383 00384 // Constant value not equal to any of the branches... must execute 00385 // default branch then... 00386 return SI->getDefaultDest() == To; 00387 } 00388 return false; 00389 } else { 00390 std::cerr << "Unknown terminator instruction: " << *TI; 00391 abort(); 00392 } 00393 } 00394 00395 // visit Implementations - Something changed in this instruction... Either an 00396 // operand made a transition, or the instruction is newly executable. Change 00397 // the value type of I to reflect these changes if appropriate. This method 00398 // makes sure to do the following actions: 00399 // 00400 // 1. If a phi node merges two constants in, and has conflicting value coming 00401 // from different branches, or if the PHI node merges in an overdefined 00402 // value, then the PHI node becomes overdefined. 00403 // 2. If a phi node merges only constants in, and they all agree on value, the 00404 // PHI node becomes a constant value equal to that. 00405 // 3. If V <- x (op) y && isConstant(x) && isConstant(y) V = Constant 00406 // 4. If V <- x (op) y && (isOverdefined(x) || isOverdefined(y)) V = Overdefined 00407 // 5. If V <- MEM or V <- CALL or V <- (unknown) then V = Overdefined 00408 // 6. If a conditional branch has a value that is constant, make the selected 00409 // destination executable 00410 // 7. If a conditional branch has a value that is overdefined, make all 00411 // successors executable. 00412 // 00413 void SCCPSolver::visitPHINode(PHINode &PN) { 00414 LatticeVal &PNIV = getValueState(&PN); 00415 if (PNIV.isOverdefined()) { 00416 // There may be instructions using this PHI node that are not overdefined 00417 // themselves. If so, make sure that they know that the PHI node operand 00418 // changed. 00419 std::multimap<PHINode*, Instruction*>::iterator I, E; 00420 tie(I, E) = UsersOfOverdefinedPHIs.equal_range(&PN); 00421 if (I != E) { 00422 std::vector<Instruction*> Users; 00423 Users.reserve(std::distance(I, E)); 00424 for (; I != E; ++I) Users.push_back(I->second); 00425 while (!Users.empty()) { 00426 visit(Users.back()); 00427 Users.pop_back(); 00428 } 00429 } 00430 return; // Quick exit 00431 } 00432 00433 // Super-extra-high-degree PHI nodes are unlikely to ever be marked constant, 00434 // and slow us down a lot. Just mark them overdefined. 00435 if (PN.getNumIncomingValues() > 64) { 00436 markOverdefined(PNIV, &PN); 00437 return; 00438 } 00439 00440 // Look at all of the executable operands of the PHI node. If any of them 00441 // are overdefined, the PHI becomes overdefined as well. If they are all 00442 // constant, and they agree with each other, the PHI becomes the identical 00443 // constant. If they are constant and don't agree, the PHI is overdefined. 00444 // If there are no executable operands, the PHI remains undefined. 00445 // 00446 Constant *OperandVal = 0; 00447 for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) { 00448 LatticeVal &IV = getValueState(PN.getIncomingValue(i)); 00449 if (IV.isUndefined()) continue; // Doesn't influence PHI node. 00450 00451 if (isEdgeFeasible(PN.getIncomingBlock(i), PN.getParent())) { 00452 if (IV.isOverdefined()) { // PHI node becomes overdefined! 00453 markOverdefined(PNIV, &PN); 00454 return; 00455 } 00456 00457 if (OperandVal == 0) { // Grab the first value... 00458 OperandVal = IV.getConstant(); 00459 } else { // Another value is being merged in! 00460 // There is already a reachable operand. If we conflict with it, 00461 // then the PHI node becomes overdefined. If we agree with it, we 00462 // can continue on. 00463 00464 // Check to see if there are two different constants merging... 00465 if (IV.getConstant() != OperandVal) { 00466 // Yes there is. This means the PHI node is not constant. 00467 // You must be overdefined poor PHI. 00468 // 00469 markOverdefined(PNIV, &PN); // The PHI node now becomes overdefined 00470 return; // I'm done analyzing you 00471 } 00472 } 00473 } 00474 } 00475 00476 // If we exited the loop, this means that the PHI node only has constant 00477 // arguments that agree with each other(and OperandVal is the constant) or 00478 // OperandVal is null because there are no defined incoming arguments. If 00479 // this is the case, the PHI remains undefined. 00480 // 00481 if (OperandVal) 00482 markConstant(PNIV, &PN, OperandVal); // Acquire operand value 00483 } 00484 00485 void SCCPSolver::visitTerminatorInst(TerminatorInst &TI) { 00486 std::vector<bool> SuccFeasible; 00487 getFeasibleSuccessors(TI, SuccFeasible); 00488 00489 BasicBlock *BB = TI.getParent(); 00490 00491 // Mark all feasible successors executable... 00492 for (unsigned i = 0, e = SuccFeasible.size(); i != e; ++i) 00493 if (SuccFeasible[i]) 00494 markEdgeExecutable(BB, TI.getSuccessor(i)); 00495 } 00496 00497 void SCCPSolver::visitCastInst(CastInst &I) { 00498 Value *V = I.getOperand(0); 00499 LatticeVal &VState = getValueState(V); 00500 if (VState.isOverdefined()) // Inherit overdefinedness of operand 00501 markOverdefined(&I); 00502 else if (VState.isConstant()) // Propagate constant value 00503 markConstant(&I, ConstantExpr::getCast(VState.getConstant(), I.getType())); 00504 } 00505 00506 void SCCPSolver::visitSelectInst(SelectInst &I) { 00507 LatticeVal &CondValue = getValueState(I.getCondition()); 00508 if (CondValue.isOverdefined()) 00509 markOverdefined(&I); 00510 else if (CondValue.isConstant()) { 00511 if (CondValue.getConstant() == ConstantBool::True) { 00512 LatticeVal &Val = getValueState(I.getTrueValue()); 00513 if (Val.isOverdefined()) 00514 markOverdefined(&I); 00515 else if (Val.isConstant()) 00516 markConstant(&I, Val.getConstant()); 00517 } else if (CondValue.getConstant() == ConstantBool::False) { 00518 LatticeVal &Val = getValueState(I.getFalseValue()); 00519 if (Val.isOverdefined()) 00520 markOverdefined(&I); 00521 else if (Val.isConstant()) 00522 markConstant(&I, Val.getConstant()); 00523 } else 00524 markOverdefined(&I); 00525 } 00526 } 00527 00528 // Handle BinaryOperators and Shift Instructions... 00529 void SCCPSolver::visitBinaryOperator(Instruction &I) { 00530 LatticeVal &IV = ValueState[&I]; 00531 if (IV.isOverdefined()) return; 00532 00533 LatticeVal &V1State = getValueState(I.getOperand(0)); 00534 LatticeVal &V2State = getValueState(I.getOperand(1)); 00535 00536 if (V1State.isOverdefined() || V2State.isOverdefined()) { 00537 // If both operands are PHI nodes, it is possible that this instruction has 00538 // a constant value, despite the fact that the PHI node doesn't. Check for 00539 // this condition now. 00540 if (PHINode *PN1 = dyn_cast<PHINode>(I.getOperand(0))) 00541 if (PHINode *PN2 = dyn_cast<PHINode>(I.getOperand(1))) 00542 if (PN1->getParent() == PN2->getParent()) { 00543 // Since the two PHI nodes are in the same basic block, they must have 00544 // entries for the same predecessors. Walk the predecessor list, and 00545 // if all of the incoming values are constants, and the result of 00546 // evaluating this expression with all incoming value pairs is the 00547 // same, then this expression is a constant even though the PHI node 00548 // is not a constant! 00549 LatticeVal Result; 00550 for (unsigned i = 0, e = PN1->getNumIncomingValues(); i != e; ++i) { 00551 LatticeVal &In1 = getValueState(PN1->getIncomingValue(i)); 00552 BasicBlock *InBlock = PN1->getIncomingBlock(i); 00553 LatticeVal &In2 = 00554 getValueState(PN2->getIncomingValueForBlock(InBlock)); 00555 00556 if (In1.isOverdefined() || In2.isOverdefined()) { 00557 Result.markOverdefined(); 00558 break; // Cannot fold this operation over the PHI nodes! 00559 } else if (In1.isConstant() && In2.isConstant()) { 00560 Constant *V = ConstantExpr::get(I.getOpcode(), In1.getConstant(), 00561 In2.getConstant()); 00562 if (Result.isUndefined()) 00563 Result.markConstant(V); 00564 else if (Result.isConstant() && Result.getConstant() != V) { 00565 Result.markOverdefined(); 00566 break; 00567 } 00568 } 00569 } 00570 00571 // If we found a constant value here, then we know the instruction is 00572 // constant despite the fact that the PHI nodes are overdefined. 00573 if (Result.isConstant()) { 00574 markConstant(IV, &I, Result.getConstant()); 00575 // Remember that this instruction is virtually using the PHI node 00576 // operands. 00577 UsersOfOverdefinedPHIs.insert(std::make_pair(PN1, &I)); 00578 UsersOfOverdefinedPHIs.insert(std::make_pair(PN2, &I)); 00579 return; 00580 } else if (Result.isUndefined()) { 00581 return; 00582 } 00583 00584 // Okay, this really is overdefined now. Since we might have 00585 // speculatively thought that this was not overdefined before, and 00586 // added ourselves to the UsersOfOverdefinedPHIs list for the PHIs, 00587 // make sure to clean out any entries that we put there, for 00588 // efficiency. 00589 std::multimap<PHINode*, Instruction*>::iterator It, E; 00590 tie(It, E) = UsersOfOverdefinedPHIs.equal_range(PN1); 00591 while (It != E) { 00592 if (It->second == &I) { 00593 UsersOfOverdefinedPHIs.erase(It++); 00594 } else 00595 ++It; 00596 } 00597 tie(It, E) = UsersOfOverdefinedPHIs.equal_range(PN2); 00598 while (It != E) { 00599 if (It->second == &I) { 00600 UsersOfOverdefinedPHIs.erase(It++); 00601 } else 00602 ++It; 00603 } 00604 } 00605 00606 markOverdefined(IV, &I); 00607 } else if (V1State.isConstant() && V2State.isConstant()) { 00608 markConstant(IV, &I, ConstantExpr::get(I.getOpcode(), V1State.getConstant(), 00609 V2State.getConstant())); 00610 } 00611 } 00612 00613 // Handle getelementptr instructions... if all operands are constants then we 00614 // can turn this into a getelementptr ConstantExpr. 00615 // 00616 void SCCPSolver::visitGetElementPtrInst(GetElementPtrInst &I) { 00617 LatticeVal &IV = ValueState[&I]; 00618 if (IV.isOverdefined()) return; 00619 00620 std::vector<Constant*> Operands; 00621 Operands.reserve(I.getNumOperands()); 00622 00623 for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) { 00624 LatticeVal &State = getValueState(I.getOperand(i)); 00625 if (State.isUndefined()) 00626 return; // Operands are not resolved yet... 00627 else if (State.isOverdefined()) { 00628 markOverdefined(IV, &I); 00629 return; 00630 } 00631 assert(State.isConstant() && "Unknown state!"); 00632 Operands.push_back(State.getConstant()); 00633 } 00634 00635 Constant *Ptr = Operands[0]; 00636 Operands.erase(Operands.begin()); // Erase the pointer from idx list... 00637 00638 markConstant(IV, &I, ConstantExpr::getGetElementPtr(Ptr, Operands)); 00639 } 00640 00641 /// GetGEPGlobalInitializer - Given a constant and a getelementptr constantexpr, 00642 /// return the constant value being addressed by the constant expression, or 00643 /// null if something is funny. 00644 /// 00645 static Constant *GetGEPGlobalInitializer(Constant *C, ConstantExpr *CE) { 00646 if (CE->getOperand(1) != Constant::getNullValue(CE->getOperand(1)->getType())) 00647 return 0; // Do not allow stepping over the value! 00648 00649 // Loop over all of the operands, tracking down which value we are 00650 // addressing... 00651 for (unsigned i = 2, e = CE->getNumOperands(); i != e; ++i) 00652 if (ConstantUInt *CU = dyn_cast<ConstantUInt>(CE->getOperand(i))) { 00653 ConstantStruct *CS = dyn_cast<ConstantStruct>(C); 00654 if (CS == 0) return 0; 00655 if (CU->getValue() >= CS->getNumOperands()) return 0; 00656 C = CS->getOperand(CU->getValue()); 00657 } else if (ConstantSInt *CS = dyn_cast<ConstantSInt>(CE->getOperand(i))) { 00658 ConstantArray *CA = dyn_cast<ConstantArray>(C); 00659 if (CA == 0) return 0; 00660 if ((uint64_t)CS->getValue() >= CA->getNumOperands()) return 0; 00661 C = CA->getOperand(CS->getValue()); 00662 } else 00663 return 0; 00664 return C; 00665 } 00666 00667 // Handle load instructions. If the operand is a constant pointer to a constant 00668 // global, we can replace the load with the loaded constant value! 00669 void SCCPSolver::visitLoadInst(LoadInst &I) { 00670 LatticeVal &IV = ValueState[&I]; 00671 if (IV.isOverdefined()) return; 00672 00673 LatticeVal &PtrVal = getValueState(I.getOperand(0)); 00674 if (PtrVal.isUndefined()) return; // The pointer is not resolved yet! 00675 if (PtrVal.isConstant() && !I.isVolatile()) { 00676 Value *Ptr = PtrVal.getConstant(); 00677 if (isa<ConstantPointerNull>(Ptr)) { 00678 // load null -> null 00679 markConstant(IV, &I, Constant::getNullValue(I.getType())); 00680 return; 00681 } 00682 00683 // Transform load (constant global) into the value loaded. 00684 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Ptr)) 00685 if (GV->isConstant() && !GV->isExternal()) { 00686 markConstant(IV, &I, GV->getInitializer()); 00687 return; 00688 } 00689 00690 // Transform load (constantexpr_GEP global, 0, ...) into the value loaded. 00691 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Ptr)) 00692 if (CE->getOpcode() == Instruction::GetElementPtr) 00693 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(CE->getOperand(0))) 00694 if (GV->isConstant() && !GV->isExternal()) 00695 if (Constant *V = 00696 GetGEPGlobalInitializer(GV->getInitializer(), CE)) { 00697 markConstant(IV, &I, V); 00698 return; 00699 } 00700 } 00701 00702 // Otherwise we cannot say for certain what value this load will produce. 00703 // Bail out. 00704 markOverdefined(IV, &I); 00705 } 00706 00707 void SCCPSolver::visitCallInst(CallInst &I) { 00708 LatticeVal &IV = ValueState[&I]; 00709 if (IV.isOverdefined()) return; 00710 00711 Function *F = I.getCalledFunction(); 00712 if (F == 0 || !canConstantFoldCallTo(F)) { 00713 markOverdefined(IV, &I); 00714 return; 00715 } 00716 00717 std::vector<Constant*> Operands; 00718 Operands.reserve(I.getNumOperands()-1); 00719 00720 for (unsigned i = 1, e = I.getNumOperands(); i != e; ++i) { 00721 LatticeVal &State = getValueState(I.getOperand(i)); 00722 if (State.isUndefined()) 00723 return; // Operands are not resolved yet... 00724 else if (State.isOverdefined()) { 00725 markOverdefined(IV, &I); 00726 return; 00727 } 00728 assert(State.isConstant() && "Unknown state!"); 00729 Operands.push_back(State.getConstant()); 00730 } 00731 00732 if (Constant *C = ConstantFoldCall(F, Operands)) 00733 markConstant(IV, &I, C); 00734 else 00735 markOverdefined(IV, &I); 00736 } 00737 00738 00739 void SCCPSolver::Solve() { 00740 // Process the work lists until they are empty! 00741 while (!BBWorkList.empty() || !InstWorkList.empty() || 00742 !OverdefinedInstWorkList.empty()) { 00743 // Process the instruction work list... 00744 while (!OverdefinedInstWorkList.empty()) { 00745 Instruction *I = OverdefinedInstWorkList.back(); 00746 OverdefinedInstWorkList.pop_back(); 00747 00748 DEBUG(std::cerr << "\nPopped off OI-WL: " << I); 00749 00750 // "I" got into the work list because it either made the transition from 00751 // bottom to constant 00752 // 00753 // Anything on this worklist that is overdefined need not be visited 00754 // since all of its users will have already been marked as overdefined 00755 // Update all of the users of this instruction's value... 00756 // 00757 for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); 00758 UI != E; ++UI) 00759 OperandChangedState(*UI); 00760 } 00761 // Process the instruction work list... 00762 while (!InstWorkList.empty()) { 00763 Instruction *I = InstWorkList.back(); 00764 InstWorkList.pop_back(); 00765 00766 DEBUG(std::cerr << "\nPopped off I-WL: " << *I); 00767 00768 // "I" got into the work list because it either made the transition from 00769 // bottom to constant 00770 // 00771 // Anything on this worklist that is overdefined need not be visited 00772 // since all of its users will have already been marked as overdefined. 00773 // Update all of the users of this instruction's value... 00774 // 00775 if (!getValueState(I).isOverdefined()) 00776 for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); 00777 UI != E; ++UI) 00778 OperandChangedState(*UI); 00779 } 00780 00781 // Process the basic block work list... 00782 while (!BBWorkList.empty()) { 00783 BasicBlock *BB = BBWorkList.back(); 00784 BBWorkList.pop_back(); 00785 00786 DEBUG(std::cerr << "\nPopped off BBWL: " << *BB); 00787 00788 // Notify all instructions in this basic block that they are newly 00789 // executable. 00790 visit(BB); 00791 } 00792 } 00793 } 00794 00795 00796 namespace { 00797 //===--------------------------------------------------------------------===// 00798 // 00799 /// SCCP Class - This class uses the SCCPSolver to implement a per-function 00800 /// Sparse Conditional COnstant Propagator. 00801 /// 00802 struct SCCP : public FunctionPass { 00803 // runOnFunction - Run the Sparse Conditional Constant Propagation 00804 // algorithm, and return true if the function was modified. 00805 // 00806 bool runOnFunction(Function &F); 00807 00808 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00809 AU.setPreservesCFG(); 00810 } 00811 }; 00812 00813 RegisterOpt<SCCP> X("sccp", "Sparse Conditional Constant Propagation"); 00814 } // end anonymous namespace 00815 00816 00817 // createSCCPPass - This is the public interface to this file... 00818 FunctionPass *llvm::createSCCPPass() { 00819 return new SCCP(); 00820 } 00821 00822 00823 // runOnFunction() - Run the Sparse Conditional Constant Propagation algorithm, 00824 // and return true if the function was modified. 00825 // 00826 bool SCCP::runOnFunction(Function &F) { 00827 DEBUG(std::cerr << "SCCP on function '" << F.getName() << "'\n"); 00828 SCCPSolver Solver; 00829 00830 // Mark the first block of the function as being executable. 00831 Solver.MarkBlockExecutable(F.begin()); 00832 00833 // Mark all arguments to the function as being overdefined. 00834 hash_map<Value*, LatticeVal> &Values = Solver.getValueMapping(); 00835 for (Function::aiterator AI = F.abegin(), E = F.aend(); AI != E; ++AI) 00836 Values[AI].markOverdefined(); 00837 00838 // Solve for constants. 00839 Solver.Solve(); 00840 00841 bool MadeChanges = false; 00842 00843 // If we decided that there are basic blocks that are dead in this function, 00844 // delete their contents now. Note that we cannot actually delete the blocks, 00845 // as we cannot modify the CFG of the function. 00846 // 00847 std::set<BasicBlock*> &ExecutableBBs = Solver.getExecutableBlocks(); 00848 for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) 00849 if (!ExecutableBBs.count(BB)) { 00850 DEBUG(std::cerr << " BasicBlock Dead:" << *BB); 00851 ++NumDeadBlocks; 00852 00853 // Delete the instructions backwards, as it has a reduced likelihood of 00854 // having to update as many def-use and use-def chains. 00855 std::vector<Instruction*> Insts; 00856 for (BasicBlock::iterator I = BB->begin(), E = BB->getTerminator(); 00857 I != E; ++I) 00858 Insts.push_back(I); 00859 while (!Insts.empty()) { 00860 Instruction *I = Insts.back(); 00861 Insts.pop_back(); 00862 if (!I->use_empty()) 00863 I->replaceAllUsesWith(UndefValue::get(I->getType())); 00864 BB->getInstList().erase(I); 00865 MadeChanges = true; 00866 ++NumInstRemoved; 00867 } 00868 } 00869 00870 // Iterate over all of the instructions in a function, replacing them with 00871 // constants if we have found them to be of constant values. 00872 // 00873 for (Function::iterator BB = F.begin(), BBE = F.end(); BB != BBE; ++BB) 00874 for (BasicBlock::iterator BI = BB->begin(), E = BB->end(); BI != E; ) { 00875 Instruction *Inst = BI++; 00876 if (Inst->getType() != Type::VoidTy) { 00877 LatticeVal &IV = Values[Inst]; 00878 if (IV.isConstant() || IV.isUndefined() && !isa<TerminatorInst>(Inst)) { 00879 Constant *Const; 00880 if (IV.isConstant()) { 00881 Const = IV.getConstant(); 00882 DEBUG(std::cerr << " Constant: " << *Const << " = " << *Inst); 00883 } else { 00884 Const = UndefValue::get(Inst->getType()); 00885 DEBUG(std::cerr << " Undefined: " << *Inst); 00886 } 00887 00888 // Replaces all of the uses of a variable with uses of the constant. 00889 Inst->replaceAllUsesWith(Const); 00890 00891 // Delete the instruction. 00892 BB->getInstList().erase(Inst); 00893 00894 // Hey, we just changed something! 00895 MadeChanges = true; 00896 ++NumInstRemoved; 00897 } 00898 } 00899 } 00900 00901 return MadeChanges; 00902 }