SCCP.cpp revision cf0fe8d813727383d630055bb9d1cde21b00b7e7
1//===- SCCP.cpp - Sparse Conditional Constant Propagation -----------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file implements sparse conditional constant propagation and merging: 11// 12// Specifically, this: 13// * Assumes values are constant unless proven otherwise 14// * Assumes BasicBlocks are dead unless proven otherwise 15// * Proves values to be constant, and replaces them with constants 16// * Proves conditional branches to be unconditional 17// 18// Notice that: 19// * This pass has a habit of making definitions be dead. It is a good idea 20// to to run a DCE pass sometime after running this pass. 21// 22//===----------------------------------------------------------------------===// 23 24#define DEBUG_TYPE "sccp" 25#include "llvm/Transforms/Scalar.h" 26#include "llvm/Transforms/IPO.h" 27#include "llvm/Constants.h" 28#include "llvm/DerivedTypes.h" 29#include "llvm/Instructions.h" 30#include "llvm/LLVMContext.h" 31#include "llvm/Pass.h" 32#include "llvm/Analysis/ConstantFolding.h" 33#include "llvm/Analysis/ValueTracking.h" 34#include "llvm/Transforms/Utils/Local.h" 35#include "llvm/Support/CallSite.h" 36#include "llvm/Support/Debug.h" 37#include "llvm/Support/ErrorHandling.h" 38#include "llvm/Support/InstVisitor.h" 39#include "llvm/Support/raw_ostream.h" 40#include "llvm/ADT/DenseMap.h" 41#include "llvm/ADT/DenseSet.h" 42#include "llvm/ADT/SmallSet.h" 43#include "llvm/ADT/SmallVector.h" 44#include "llvm/ADT/Statistic.h" 45#include "llvm/ADT/STLExtras.h" 46#include <algorithm> 47#include <map> 48using namespace llvm; 49 50STATISTIC(NumInstRemoved, "Number of instructions removed"); 51STATISTIC(NumDeadBlocks , "Number of basic blocks unreachable"); 52 53STATISTIC(IPNumInstRemoved, "Number of instructions removed by IPSCCP"); 54STATISTIC(IPNumDeadBlocks , "Number of basic blocks unreachable by IPSCCP"); 55STATISTIC(IPNumArgsElimed ,"Number of arguments constant propagated by IPSCCP"); 56STATISTIC(IPNumGlobalConst, "Number of globals found to be constant by IPSCCP"); 57 58namespace { 59/// LatticeVal class - This class represents the different lattice values that 60/// an LLVM value may occupy. It is a simple class with value semantics. 61/// 62class LatticeVal { 63 enum { 64 /// undefined - This LLVM Value has no known value yet. 65 undefined, 66 67 /// constant - This LLVM Value has a specific constant value. 68 constant, 69 70 /// forcedconstant - This LLVM Value was thought to be undef until 71 /// ResolvedUndefsIn. This is treated just like 'constant', but if merged 72 /// with another (different) constant, it goes to overdefined, instead of 73 /// asserting. 74 forcedconstant, 75 76 /// overdefined - This instruction is not known to be constant, and we know 77 /// it has a value. 78 overdefined 79 } LatticeValue; // The current lattice position 80 81 Constant *ConstantVal; // If Constant value, the current value 82public: 83 inline LatticeVal() : LatticeValue(undefined), ConstantVal(0) {} 84 85 // markOverdefined - Return true if this is a new status to be in... 86 inline bool markOverdefined() { 87 if (LatticeValue != overdefined) { 88 LatticeValue = overdefined; 89 return true; 90 } 91 return false; 92 } 93 94 // markConstant - Return true if this is a new status for us. 95 inline bool markConstant(Constant *V) { 96 if (LatticeValue != constant) { 97 if (LatticeValue == undefined) { 98 LatticeValue = constant; 99 assert(V && "Marking constant with NULL"); 100 ConstantVal = V; 101 } else { 102 assert(LatticeValue == forcedconstant && 103 "Cannot move from overdefined to constant!"); 104 // Stay at forcedconstant if the constant is the same. 105 if (V == ConstantVal) return false; 106 107 // Otherwise, we go to overdefined. Assumptions made based on the 108 // forced value are possibly wrong. Assuming this is another constant 109 // could expose a contradiction. 110 LatticeValue = overdefined; 111 } 112 return true; 113 } else { 114 assert(ConstantVal == V && "Marking constant with different value"); 115 } 116 return false; 117 } 118 119 inline void markForcedConstant(Constant *V) { 120 assert(LatticeValue == undefined && "Can't force a defined value!"); 121 LatticeValue = forcedconstant; 122 ConstantVal = V; 123 } 124 125 inline bool isUndefined() const { return LatticeValue == undefined; } 126 inline bool isConstant() const { 127 return LatticeValue == constant || LatticeValue == forcedconstant; 128 } 129 inline bool isOverdefined() const { return LatticeValue == overdefined; } 130 131 inline Constant *getConstant() const { 132 assert(isConstant() && "Cannot get the constant of a non-constant!"); 133 return ConstantVal; 134 } 135}; 136 137//===----------------------------------------------------------------------===// 138// 139/// SCCPSolver - This class is a general purpose solver for Sparse Conditional 140/// Constant Propagation. 141/// 142class SCCPSolver : public InstVisitor<SCCPSolver> { 143 LLVMContext *Context; 144 DenseSet<BasicBlock*> BBExecutable;// The basic blocks that are executable 145 std::map<Value*, LatticeVal> ValueState; // The state each value is in. 146 147 /// GlobalValue - If we are tracking any values for the contents of a global 148 /// variable, we keep a mapping from the constant accessor to the element of 149 /// the global, to the currently known value. If the value becomes 150 /// overdefined, it's entry is simply removed from this map. 151 DenseMap<GlobalVariable*, LatticeVal> TrackedGlobals; 152 153 /// TrackedRetVals - If we are tracking arguments into and the return 154 /// value out of a function, it will have an entry in this map, indicating 155 /// what the known return value for the function is. 156 DenseMap<Function*, LatticeVal> TrackedRetVals; 157 158 /// TrackedMultipleRetVals - Same as TrackedRetVals, but used for functions 159 /// that return multiple values. 160 DenseMap<std::pair<Function*, unsigned>, LatticeVal> TrackedMultipleRetVals; 161 162 // The reason for two worklists is that overdefined is the lowest state 163 // on the lattice, and moving things to overdefined as fast as possible 164 // makes SCCP converge much faster. 165 // By having a separate worklist, we accomplish this because everything 166 // possibly overdefined will become overdefined at the soonest possible 167 // point. 168 SmallVector<Value*, 64> OverdefinedInstWorkList; 169 SmallVector<Value*, 64> InstWorkList; 170 171 172 SmallVector<BasicBlock*, 64> BBWorkList; // The BasicBlock work list 173 174 /// UsersOfOverdefinedPHIs - Keep track of any users of PHI nodes that are not 175 /// overdefined, despite the fact that the PHI node is overdefined. 176 std::multimap<PHINode*, Instruction*> UsersOfOverdefinedPHIs; 177 178 /// KnownFeasibleEdges - Entries in this set are edges which have already had 179 /// PHI nodes retriggered. 180 typedef std::pair<BasicBlock*, BasicBlock*> Edge; 181 DenseSet<Edge> KnownFeasibleEdges; 182public: 183 void setContext(LLVMContext *C) { Context = C; } 184 185 /// MarkBlockExecutable - This method can be used by clients to mark all of 186 /// the blocks that are known to be intrinsically live in the processed unit. 187 void MarkBlockExecutable(BasicBlock *BB) { 188 DEBUG(errs() << "Marking Block Executable: " << BB->getName() << "\n"); 189 BBExecutable.insert(BB); // Basic block is executable! 190 BBWorkList.push_back(BB); // Add the block to the work list! 191 } 192 193 /// TrackValueOfGlobalVariable - Clients can use this method to 194 /// inform the SCCPSolver that it should track loads and stores to the 195 /// specified global variable if it can. This is only legal to call if 196 /// performing Interprocedural SCCP. 197 void TrackValueOfGlobalVariable(GlobalVariable *GV) { 198 const Type *ElTy = GV->getType()->getElementType(); 199 if (ElTy->isFirstClassType()) { 200 LatticeVal &IV = TrackedGlobals[GV]; 201 if (!isa<UndefValue>(GV->getInitializer())) 202 IV.markConstant(GV->getInitializer()); 203 } 204 } 205 206 /// AddTrackedFunction - If the SCCP solver is supposed to track calls into 207 /// and out of the specified function (which cannot have its address taken), 208 /// this method must be called. 209 void AddTrackedFunction(Function *F) { 210 assert(F->hasLocalLinkage() && "Can only track internal functions!"); 211 // Add an entry, F -> undef. 212 if (const StructType *STy = dyn_cast<StructType>(F->getReturnType())) { 213 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) 214 TrackedMultipleRetVals.insert(std::make_pair(std::make_pair(F, i), 215 LatticeVal())); 216 } else 217 TrackedRetVals.insert(std::make_pair(F, LatticeVal())); 218 } 219 220 /// Solve - Solve for constants and executable blocks. 221 /// 222 void Solve(); 223 224 /// ResolvedUndefsIn - While solving the dataflow for a function, we assume 225 /// that branches on undef values cannot reach any of their successors. 226 /// However, this is not a safe assumption. After we solve dataflow, this 227 /// method should be use to handle this. If this returns true, the solver 228 /// should be rerun. 229 bool ResolvedUndefsIn(Function &F); 230 231 bool isBlockExecutable(BasicBlock *BB) const { 232 return BBExecutable.count(BB); 233 } 234 235 /// getValueMapping - Once we have solved for constants, return the mapping of 236 /// LLVM values to LatticeVals. 237 std::map<Value*, LatticeVal> &getValueMapping() { 238 return ValueState; 239 } 240 241 /// getTrackedRetVals - Get the inferred return value map. 242 /// 243 const DenseMap<Function*, LatticeVal> &getTrackedRetVals() { 244 return TrackedRetVals; 245 } 246 247 /// getTrackedGlobals - Get and return the set of inferred initializers for 248 /// global variables. 249 const DenseMap<GlobalVariable*, LatticeVal> &getTrackedGlobals() { 250 return TrackedGlobals; 251 } 252 253 inline void markOverdefined(Value *V) { 254 markOverdefined(ValueState[V], V); 255 } 256 257private: 258 // markConstant - Make a value be marked as "constant". If the value 259 // is not already a constant, add it to the instruction work list so that 260 // the users of the instruction are updated later. 261 // 262 inline void markConstant(LatticeVal &IV, Value *V, Constant *C) { 263 if (IV.markConstant(C)) { 264 DEBUG(errs() << "markConstant: " << *C << ": " << *V << '\n'); 265 InstWorkList.push_back(V); 266 } 267 } 268 269 inline void markForcedConstant(LatticeVal &IV, Value *V, Constant *C) { 270 IV.markForcedConstant(C); 271 DEBUG(errs() << "markForcedConstant: " << *C << ": " << *V << '\n'); 272 InstWorkList.push_back(V); 273 } 274 275 inline void markConstant(Value *V, Constant *C) { 276 markConstant(ValueState[V], V, C); 277 } 278 279 // markOverdefined - Make a value be marked as "overdefined". If the 280 // value is not already overdefined, add it to the overdefined instruction 281 // work list so that the users of the instruction are updated later. 282 inline void markOverdefined(LatticeVal &IV, Value *V) { 283 if (IV.markOverdefined()) { 284 DEBUG(errs() << "markOverdefined: "; 285 if (Function *F = dyn_cast<Function>(V)) 286 errs() << "Function '" << F->getName() << "'\n"; 287 else 288 errs() << *V << '\n'); 289 // Only instructions go on the work list 290 OverdefinedInstWorkList.push_back(V); 291 } 292 } 293 294 inline void mergeInValue(LatticeVal &IV, Value *V, LatticeVal &MergeWithV) { 295 if (IV.isOverdefined() || MergeWithV.isUndefined()) 296 return; // Noop. 297 if (MergeWithV.isOverdefined()) 298 markOverdefined(IV, V); 299 else if (IV.isUndefined()) 300 markConstant(IV, V, MergeWithV.getConstant()); 301 else if (IV.getConstant() != MergeWithV.getConstant()) 302 markOverdefined(IV, V); 303 } 304 305 inline void mergeInValue(Value *V, LatticeVal &MergeWithV) { 306 return mergeInValue(ValueState[V], V, MergeWithV); 307 } 308 309 310 // getValueState - Return the LatticeVal object that corresponds to the value. 311 // This function is necessary because not all values should start out in the 312 // underdefined state... Argument's should be overdefined, and 313 // constants should be marked as constants. If a value is not known to be an 314 // Instruction object, then use this accessor to get its value from the map. 315 // 316 inline LatticeVal &getValueState(Value *V) { 317 std::map<Value*, LatticeVal>::iterator I = ValueState.find(V); 318 if (I != ValueState.end()) return I->second; // Common case, in the map 319 320 if (Constant *C = dyn_cast<Constant>(V)) { 321 if (isa<UndefValue>(V)) { 322 // Nothing to do, remain undefined. 323 } else { 324 LatticeVal &LV = ValueState[C]; 325 LV.markConstant(C); // Constants are constant 326 return LV; 327 } 328 } 329 // All others are underdefined by default... 330 return ValueState[V]; 331 } 332 333 // markEdgeExecutable - Mark a basic block as executable, adding it to the BB 334 // work list if it is not already executable... 335 // 336 void markEdgeExecutable(BasicBlock *Source, BasicBlock *Dest) { 337 if (!KnownFeasibleEdges.insert(Edge(Source, Dest)).second) 338 return; // This edge is already known to be executable! 339 340 if (BBExecutable.count(Dest)) { 341 DEBUG(errs() << "Marking Edge Executable: " << Source->getName() 342 << " -> " << Dest->getName() << "\n"); 343 344 // The destination is already executable, but we just made an edge 345 // feasible that wasn't before. Revisit the PHI nodes in the block 346 // because they have potentially new operands. 347 for (BasicBlock::iterator I = Dest->begin(); isa<PHINode>(I); ++I) 348 visitPHINode(*cast<PHINode>(I)); 349 350 } else { 351 MarkBlockExecutable(Dest); 352 } 353 } 354 355 // getFeasibleSuccessors - Return a vector of booleans to indicate which 356 // successors are reachable from a given terminator instruction. 357 // 358 void getFeasibleSuccessors(TerminatorInst &TI, SmallVector<bool, 16> &Succs); 359 360 // isEdgeFeasible - Return true if the control flow edge from the 'From' basic 361 // block to the 'To' basic block is currently feasible... 362 // 363 bool isEdgeFeasible(BasicBlock *From, BasicBlock *To); 364 365 // OperandChangedState - This method is invoked on all of the users of an 366 // instruction that was just changed state somehow.... Based on this 367 // information, we need to update the specified user of this instruction. 368 // 369 void OperandChangedState(User *U) { 370 // Only instructions use other variable values! 371 Instruction &I = cast<Instruction>(*U); 372 if (BBExecutable.count(I.getParent())) // Inst is executable? 373 visit(I); 374 } 375 376private: 377 friend class InstVisitor<SCCPSolver>; 378 379 // visit implementations - Something changed in this instruction... Either an 380 // operand made a transition, or the instruction is newly executable. Change 381 // the value type of I to reflect these changes if appropriate. 382 // 383 void visitPHINode(PHINode &I); 384 385 // Terminators 386 void visitReturnInst(ReturnInst &I); 387 void visitTerminatorInst(TerminatorInst &TI); 388 389 void visitCastInst(CastInst &I); 390 void visitSelectInst(SelectInst &I); 391 void visitBinaryOperator(Instruction &I); 392 void visitCmpInst(CmpInst &I); 393 void visitExtractElementInst(ExtractElementInst &I); 394 void visitInsertElementInst(InsertElementInst &I); 395 void visitShuffleVectorInst(ShuffleVectorInst &I); 396 void visitExtractValueInst(ExtractValueInst &EVI); 397 void visitInsertValueInst(InsertValueInst &IVI); 398 399 // Instructions that cannot be folded away... 400 void visitStoreInst (Instruction &I); 401 void visitLoadInst (LoadInst &I); 402 void visitGetElementPtrInst(GetElementPtrInst &I); 403 void visitCallInst (CallInst &I) { 404 visitCallSite(CallSite::get(&I)); 405 } 406 void visitInvokeInst (InvokeInst &II) { 407 visitCallSite(CallSite::get(&II)); 408 visitTerminatorInst(II); 409 } 410 void visitCallSite (CallSite CS); 411 void visitUnwindInst (TerminatorInst &I) { /*returns void*/ } 412 void visitUnreachableInst(TerminatorInst &I) { /*returns void*/ } 413 void visitAllocationInst(Instruction &I) { markOverdefined(&I); } 414 void visitVANextInst (Instruction &I) { markOverdefined(&I); } 415 void visitVAArgInst (Instruction &I) { markOverdefined(&I); } 416 void visitFreeInst (Instruction &I) { /*returns void*/ } 417 418 void visitInstruction(Instruction &I) { 419 // If a new instruction is added to LLVM that we don't handle... 420 errs() << "SCCP: Don't know how to handle: " << I; 421 markOverdefined(&I); // Just in case 422 } 423}; 424 425} // end anonymous namespace 426 427 428// getFeasibleSuccessors - Return a vector of booleans to indicate which 429// successors are reachable from a given terminator instruction. 430// 431void SCCPSolver::getFeasibleSuccessors(TerminatorInst &TI, 432 SmallVector<bool, 16> &Succs) { 433 Succs.resize(TI.getNumSuccessors()); 434 if (BranchInst *BI = dyn_cast<BranchInst>(&TI)) { 435 if (BI->isUnconditional()) { 436 Succs[0] = true; 437 } else { 438 LatticeVal &BCValue = getValueState(BI->getCondition()); 439 if (BCValue.isOverdefined() || 440 (BCValue.isConstant() && !isa<ConstantInt>(BCValue.getConstant()))) { 441 // Overdefined condition variables, and branches on unfoldable constant 442 // conditions, mean the branch could go either way. 443 Succs[0] = Succs[1] = true; 444 } else if (BCValue.isConstant()) { 445 // Constant condition variables mean the branch can only go a single way 446 Succs[BCValue.getConstant() == ConstantInt::getFalse(*Context)] = true; 447 } 448 } 449 } else if (isa<InvokeInst>(&TI)) { 450 // Invoke instructions successors are always executable. 451 Succs[0] = Succs[1] = true; 452 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(&TI)) { 453 LatticeVal &SCValue = getValueState(SI->getCondition()); 454 if (SCValue.isOverdefined() || // Overdefined condition? 455 (SCValue.isConstant() && !isa<ConstantInt>(SCValue.getConstant()))) { 456 // All destinations are executable! 457 Succs.assign(TI.getNumSuccessors(), true); 458 } else if (SCValue.isConstant()) 459 Succs[SI->findCaseValue(cast<ConstantInt>(SCValue.getConstant()))] = true; 460 } else { 461 llvm_unreachable("SCCP: Don't know how to handle this terminator!"); 462 } 463} 464 465 466// isEdgeFeasible - Return true if the control flow edge from the 'From' basic 467// block to the 'To' basic block is currently feasible... 468// 469bool SCCPSolver::isEdgeFeasible(BasicBlock *From, BasicBlock *To) { 470 assert(BBExecutable.count(To) && "Dest should always be alive!"); 471 472 // Make sure the source basic block is executable!! 473 if (!BBExecutable.count(From)) return false; 474 475 // Check to make sure this edge itself is actually feasible now... 476 TerminatorInst *TI = From->getTerminator(); 477 if (BranchInst *BI = dyn_cast<BranchInst>(TI)) { 478 if (BI->isUnconditional()) 479 return true; 480 else { 481 LatticeVal &BCValue = getValueState(BI->getCondition()); 482 if (BCValue.isOverdefined()) { 483 // Overdefined condition variables mean the branch could go either way. 484 return true; 485 } else if (BCValue.isConstant()) { 486 // Not branching on an evaluatable constant? 487 if (!isa<ConstantInt>(BCValue.getConstant())) return true; 488 489 // Constant condition variables mean the branch can only go a single way 490 return BI->getSuccessor(BCValue.getConstant() == 491 ConstantInt::getFalse(*Context)) == To; 492 } 493 return false; 494 } 495 } else if (isa<InvokeInst>(TI)) { 496 // Invoke instructions successors are always executable. 497 return true; 498 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 499 LatticeVal &SCValue = getValueState(SI->getCondition()); 500 if (SCValue.isOverdefined()) { // Overdefined condition? 501 // All destinations are executable! 502 return true; 503 } else if (SCValue.isConstant()) { 504 Constant *CPV = SCValue.getConstant(); 505 if (!isa<ConstantInt>(CPV)) 506 return true; // not a foldable constant? 507 508 // Make sure to skip the "default value" which isn't a value 509 for (unsigned i = 1, E = SI->getNumSuccessors(); i != E; ++i) 510 if (SI->getSuccessorValue(i) == CPV) // Found the taken branch... 511 return SI->getSuccessor(i) == To; 512 513 // Constant value not equal to any of the branches... must execute 514 // default branch then... 515 return SI->getDefaultDest() == To; 516 } 517 return false; 518 } else { 519#ifndef NDEBUG 520 errs() << "Unknown terminator instruction: " << *TI << '\n'; 521#endif 522 llvm_unreachable(0); 523 } 524} 525 526// visit Implementations - Something changed in this instruction... Either an 527// operand made a transition, or the instruction is newly executable. Change 528// the value type of I to reflect these changes if appropriate. This method 529// makes sure to do the following actions: 530// 531// 1. If a phi node merges two constants in, and has conflicting value coming 532// from different branches, or if the PHI node merges in an overdefined 533// value, then the PHI node becomes overdefined. 534// 2. If a phi node merges only constants in, and they all agree on value, the 535// PHI node becomes a constant value equal to that. 536// 3. If V <- x (op) y && isConstant(x) && isConstant(y) V = Constant 537// 4. If V <- x (op) y && (isOverdefined(x) || isOverdefined(y)) V = Overdefined 538// 5. If V <- MEM or V <- CALL or V <- (unknown) then V = Overdefined 539// 6. If a conditional branch has a value that is constant, make the selected 540// destination executable 541// 7. If a conditional branch has a value that is overdefined, make all 542// successors executable. 543// 544void SCCPSolver::visitPHINode(PHINode &PN) { 545 LatticeVal &PNIV = getValueState(&PN); 546 if (PNIV.isOverdefined()) { 547 // There may be instructions using this PHI node that are not overdefined 548 // themselves. If so, make sure that they know that the PHI node operand 549 // changed. 550 std::multimap<PHINode*, Instruction*>::iterator I, E; 551 tie(I, E) = UsersOfOverdefinedPHIs.equal_range(&PN); 552 if (I != E) { 553 SmallVector<Instruction*, 16> Users; 554 for (; I != E; ++I) Users.push_back(I->second); 555 while (!Users.empty()) { 556 visit(Users.back()); 557 Users.pop_back(); 558 } 559 } 560 return; // Quick exit 561 } 562 563 // Super-extra-high-degree PHI nodes are unlikely to ever be marked constant, 564 // and slow us down a lot. Just mark them overdefined. 565 if (PN.getNumIncomingValues() > 64) { 566 markOverdefined(PNIV, &PN); 567 return; 568 } 569 570 // Look at all of the executable operands of the PHI node. If any of them 571 // are overdefined, the PHI becomes overdefined as well. If they are all 572 // constant, and they agree with each other, the PHI becomes the identical 573 // constant. If they are constant and don't agree, the PHI is overdefined. 574 // If there are no executable operands, the PHI remains undefined. 575 // 576 Constant *OperandVal = 0; 577 for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) { 578 LatticeVal &IV = getValueState(PN.getIncomingValue(i)); 579 if (IV.isUndefined()) continue; // Doesn't influence PHI node. 580 581 if (isEdgeFeasible(PN.getIncomingBlock(i), PN.getParent())) { 582 if (IV.isOverdefined()) { // PHI node becomes overdefined! 583 markOverdefined(&PN); 584 return; 585 } 586 587 if (OperandVal == 0) { // Grab the first value... 588 OperandVal = IV.getConstant(); 589 } else { // Another value is being merged in! 590 // There is already a reachable operand. If we conflict with it, 591 // then the PHI node becomes overdefined. If we agree with it, we 592 // can continue on. 593 594 // Check to see if there are two different constants merging... 595 if (IV.getConstant() != OperandVal) { 596 // Yes there is. This means the PHI node is not constant. 597 // You must be overdefined poor PHI. 598 // 599 markOverdefined(&PN); // The PHI node now becomes overdefined 600 return; // I'm done analyzing you 601 } 602 } 603 } 604 } 605 606 // If we exited the loop, this means that the PHI node only has constant 607 // arguments that agree with each other(and OperandVal is the constant) or 608 // OperandVal is null because there are no defined incoming arguments. If 609 // this is the case, the PHI remains undefined. 610 // 611 if (OperandVal) 612 markConstant(&PN, OperandVal); // Acquire operand value 613} 614 615void SCCPSolver::visitReturnInst(ReturnInst &I) { 616 if (I.getNumOperands() == 0) return; // Ret void 617 618 Function *F = I.getParent()->getParent(); 619 // If we are tracking the return value of this function, merge it in. 620 if (!F->hasLocalLinkage()) 621 return; 622 623 if (!TrackedRetVals.empty() && I.getNumOperands() == 1) { 624 DenseMap<Function*, LatticeVal>::iterator TFRVI = 625 TrackedRetVals.find(F); 626 if (TFRVI != TrackedRetVals.end() && 627 !TFRVI->second.isOverdefined()) { 628 LatticeVal &IV = getValueState(I.getOperand(0)); 629 mergeInValue(TFRVI->second, F, IV); 630 return; 631 } 632 } 633 634 // Handle functions that return multiple values. 635 if (!TrackedMultipleRetVals.empty() && I.getNumOperands() > 1) { 636 for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) { 637 DenseMap<std::pair<Function*, unsigned>, LatticeVal>::iterator 638 It = TrackedMultipleRetVals.find(std::make_pair(F, i)); 639 if (It == TrackedMultipleRetVals.end()) break; 640 mergeInValue(It->second, F, getValueState(I.getOperand(i))); 641 } 642 } else if (!TrackedMultipleRetVals.empty() && 643 I.getNumOperands() == 1 && 644 isa<StructType>(I.getOperand(0)->getType())) { 645 for (unsigned i = 0, e = I.getOperand(0)->getType()->getNumContainedTypes(); 646 i != e; ++i) { 647 DenseMap<std::pair<Function*, unsigned>, LatticeVal>::iterator 648 It = TrackedMultipleRetVals.find(std::make_pair(F, i)); 649 if (It == TrackedMultipleRetVals.end()) break; 650 if (Value *Val = FindInsertedValue(I.getOperand(0), i, I.getContext())) 651 mergeInValue(It->second, F, getValueState(Val)); 652 } 653 } 654} 655 656void SCCPSolver::visitTerminatorInst(TerminatorInst &TI) { 657 SmallVector<bool, 16> SuccFeasible; 658 getFeasibleSuccessors(TI, SuccFeasible); 659 660 BasicBlock *BB = TI.getParent(); 661 662 // Mark all feasible successors executable... 663 for (unsigned i = 0, e = SuccFeasible.size(); i != e; ++i) 664 if (SuccFeasible[i]) 665 markEdgeExecutable(BB, TI.getSuccessor(i)); 666} 667 668void SCCPSolver::visitCastInst(CastInst &I) { 669 Value *V = I.getOperand(0); 670 LatticeVal &VState = getValueState(V); 671 if (VState.isOverdefined()) // Inherit overdefinedness of operand 672 markOverdefined(&I); 673 else if (VState.isConstant()) // Propagate constant value 674 markConstant(&I, ConstantExpr::getCast(I.getOpcode(), 675 VState.getConstant(), I.getType())); 676} 677 678void SCCPSolver::visitExtractValueInst(ExtractValueInst &EVI) { 679 Value *Aggr = EVI.getAggregateOperand(); 680 681 // If the operand to the extractvalue is an undef, the result is undef. 682 if (isa<UndefValue>(Aggr)) 683 return; 684 685 // Currently only handle single-index extractvalues. 686 if (EVI.getNumIndices() != 1) { 687 markOverdefined(&EVI); 688 return; 689 } 690 691 Function *F = 0; 692 if (CallInst *CI = dyn_cast<CallInst>(Aggr)) 693 F = CI->getCalledFunction(); 694 else if (InvokeInst *II = dyn_cast<InvokeInst>(Aggr)) 695 F = II->getCalledFunction(); 696 697 // TODO: If IPSCCP resolves the callee of this function, we could propagate a 698 // result back! 699 if (F == 0 || TrackedMultipleRetVals.empty()) { 700 markOverdefined(&EVI); 701 return; 702 } 703 704 // See if we are tracking the result of the callee. If not tracking this 705 // function (for example, it is a declaration) just move to overdefined. 706 if (!TrackedMultipleRetVals.count(std::make_pair(F, *EVI.idx_begin()))) { 707 markOverdefined(&EVI); 708 return; 709 } 710 711 // Otherwise, the value will be merged in here as a result of CallSite 712 // handling. 713} 714 715void SCCPSolver::visitInsertValueInst(InsertValueInst &IVI) { 716 Value *Aggr = IVI.getAggregateOperand(); 717 Value *Val = IVI.getInsertedValueOperand(); 718 719 // If the operands to the insertvalue are undef, the result is undef. 720 if (isa<UndefValue>(Aggr) && isa<UndefValue>(Val)) 721 return; 722 723 // Currently only handle single-index insertvalues. 724 if (IVI.getNumIndices() != 1) { 725 markOverdefined(&IVI); 726 return; 727 } 728 729 // Currently only handle insertvalue instructions that are in a single-use 730 // chain that builds up a return value. 731 for (const InsertValueInst *TmpIVI = &IVI; ; ) { 732 if (!TmpIVI->hasOneUse()) { 733 markOverdefined(&IVI); 734 return; 735 } 736 const Value *V = *TmpIVI->use_begin(); 737 if (isa<ReturnInst>(V)) 738 break; 739 TmpIVI = dyn_cast<InsertValueInst>(V); 740 if (!TmpIVI) { 741 markOverdefined(&IVI); 742 return; 743 } 744 } 745 746 // See if we are tracking the result of the callee. 747 Function *F = IVI.getParent()->getParent(); 748 DenseMap<std::pair<Function*, unsigned>, LatticeVal>::iterator 749 It = TrackedMultipleRetVals.find(std::make_pair(F, *IVI.idx_begin())); 750 751 // Merge in the inserted member value. 752 if (It != TrackedMultipleRetVals.end()) 753 mergeInValue(It->second, F, getValueState(Val)); 754 755 // Mark the aggregate result of the IVI overdefined; any tracking that we do 756 // will be done on the individual member values. 757 markOverdefined(&IVI); 758} 759 760void SCCPSolver::visitSelectInst(SelectInst &I) { 761 LatticeVal &CondValue = getValueState(I.getCondition()); 762 if (CondValue.isUndefined()) 763 return; 764 if (CondValue.isConstant()) { 765 if (ConstantInt *CondCB = dyn_cast<ConstantInt>(CondValue.getConstant())){ 766 mergeInValue(&I, getValueState(CondCB->getZExtValue() ? I.getTrueValue() 767 : I.getFalseValue())); 768 return; 769 } 770 } 771 772 // Otherwise, the condition is overdefined or a constant we can't evaluate. 773 // See if we can produce something better than overdefined based on the T/F 774 // value. 775 LatticeVal &TVal = getValueState(I.getTrueValue()); 776 LatticeVal &FVal = getValueState(I.getFalseValue()); 777 778 // select ?, C, C -> C. 779 if (TVal.isConstant() && FVal.isConstant() && 780 TVal.getConstant() == FVal.getConstant()) { 781 markConstant(&I, FVal.getConstant()); 782 return; 783 } 784 785 if (TVal.isUndefined()) { // select ?, undef, X -> X. 786 mergeInValue(&I, FVal); 787 } else if (FVal.isUndefined()) { // select ?, X, undef -> X. 788 mergeInValue(&I, TVal); 789 } else { 790 markOverdefined(&I); 791 } 792} 793 794// Handle BinaryOperators and Shift Instructions... 795void SCCPSolver::visitBinaryOperator(Instruction &I) { 796 LatticeVal &IV = ValueState[&I]; 797 if (IV.isOverdefined()) return; 798 799 LatticeVal &V1State = getValueState(I.getOperand(0)); 800 LatticeVal &V2State = getValueState(I.getOperand(1)); 801 802 if (V1State.isOverdefined() || V2State.isOverdefined()) { 803 // If this is an AND or OR with 0 or -1, it doesn't matter that the other 804 // operand is overdefined. 805 if (I.getOpcode() == Instruction::And || I.getOpcode() == Instruction::Or) { 806 LatticeVal *NonOverdefVal = 0; 807 if (!V1State.isOverdefined()) { 808 NonOverdefVal = &V1State; 809 } else if (!V2State.isOverdefined()) { 810 NonOverdefVal = &V2State; 811 } 812 813 if (NonOverdefVal) { 814 if (NonOverdefVal->isUndefined()) { 815 // Could annihilate value. 816 if (I.getOpcode() == Instruction::And) 817 markConstant(IV, &I, Constant::getNullValue(I.getType())); 818 else if (const VectorType *PT = dyn_cast<VectorType>(I.getType())) 819 markConstant(IV, &I, Constant::getAllOnesValue(PT)); 820 else 821 markConstant(IV, &I, 822 Constant::getAllOnesValue(I.getType())); 823 return; 824 } else { 825 if (I.getOpcode() == Instruction::And) { 826 if (NonOverdefVal->getConstant()->isNullValue()) { 827 markConstant(IV, &I, NonOverdefVal->getConstant()); 828 return; // X and 0 = 0 829 } 830 } else { 831 if (ConstantInt *CI = 832 dyn_cast<ConstantInt>(NonOverdefVal->getConstant())) 833 if (CI->isAllOnesValue()) { 834 markConstant(IV, &I, NonOverdefVal->getConstant()); 835 return; // X or -1 = -1 836 } 837 } 838 } 839 } 840 } 841 842 843 // If both operands are PHI nodes, it is possible that this instruction has 844 // a constant value, despite the fact that the PHI node doesn't. Check for 845 // this condition now. 846 if (PHINode *PN1 = dyn_cast<PHINode>(I.getOperand(0))) 847 if (PHINode *PN2 = dyn_cast<PHINode>(I.getOperand(1))) 848 if (PN1->getParent() == PN2->getParent()) { 849 // Since the two PHI nodes are in the same basic block, they must have 850 // entries for the same predecessors. Walk the predecessor list, and 851 // if all of the incoming values are constants, and the result of 852 // evaluating this expression with all incoming value pairs is the 853 // same, then this expression is a constant even though the PHI node 854 // is not a constant! 855 LatticeVal Result; 856 for (unsigned i = 0, e = PN1->getNumIncomingValues(); i != e; ++i) { 857 LatticeVal &In1 = getValueState(PN1->getIncomingValue(i)); 858 BasicBlock *InBlock = PN1->getIncomingBlock(i); 859 LatticeVal &In2 = 860 getValueState(PN2->getIncomingValueForBlock(InBlock)); 861 862 if (In1.isOverdefined() || In2.isOverdefined()) { 863 Result.markOverdefined(); 864 break; // Cannot fold this operation over the PHI nodes! 865 } else if (In1.isConstant() && In2.isConstant()) { 866 Constant *V = 867 ConstantExpr::get(I.getOpcode(), In1.getConstant(), 868 In2.getConstant()); 869 if (Result.isUndefined()) 870 Result.markConstant(V); 871 else if (Result.isConstant() && Result.getConstant() != V) { 872 Result.markOverdefined(); 873 break; 874 } 875 } 876 } 877 878 // If we found a constant value here, then we know the instruction is 879 // constant despite the fact that the PHI nodes are overdefined. 880 if (Result.isConstant()) { 881 markConstant(IV, &I, Result.getConstant()); 882 // Remember that this instruction is virtually using the PHI node 883 // operands. 884 UsersOfOverdefinedPHIs.insert(std::make_pair(PN1, &I)); 885 UsersOfOverdefinedPHIs.insert(std::make_pair(PN2, &I)); 886 return; 887 } else if (Result.isUndefined()) { 888 return; 889 } 890 891 // Okay, this really is overdefined now. Since we might have 892 // speculatively thought that this was not overdefined before, and 893 // added ourselves to the UsersOfOverdefinedPHIs list for the PHIs, 894 // make sure to clean out any entries that we put there, for 895 // efficiency. 896 std::multimap<PHINode*, Instruction*>::iterator It, E; 897 tie(It, E) = UsersOfOverdefinedPHIs.equal_range(PN1); 898 while (It != E) { 899 if (It->second == &I) { 900 UsersOfOverdefinedPHIs.erase(It++); 901 } else 902 ++It; 903 } 904 tie(It, E) = UsersOfOverdefinedPHIs.equal_range(PN2); 905 while (It != E) { 906 if (It->second == &I) { 907 UsersOfOverdefinedPHIs.erase(It++); 908 } else 909 ++It; 910 } 911 } 912 913 markOverdefined(IV, &I); 914 } else if (V1State.isConstant() && V2State.isConstant()) { 915 markConstant(IV, &I, 916 ConstantExpr::get(I.getOpcode(), V1State.getConstant(), 917 V2State.getConstant())); 918 } 919} 920 921// Handle ICmpInst instruction... 922void SCCPSolver::visitCmpInst(CmpInst &I) { 923 LatticeVal &IV = ValueState[&I]; 924 if (IV.isOverdefined()) return; 925 926 LatticeVal &V1State = getValueState(I.getOperand(0)); 927 LatticeVal &V2State = getValueState(I.getOperand(1)); 928 929 if (V1State.isOverdefined() || V2State.isOverdefined()) { 930 // If both operands are PHI nodes, it is possible that this instruction has 931 // a constant value, despite the fact that the PHI node doesn't. Check for 932 // this condition now. 933 if (PHINode *PN1 = dyn_cast<PHINode>(I.getOperand(0))) 934 if (PHINode *PN2 = dyn_cast<PHINode>(I.getOperand(1))) 935 if (PN1->getParent() == PN2->getParent()) { 936 // Since the two PHI nodes are in the same basic block, they must have 937 // entries for the same predecessors. Walk the predecessor list, and 938 // if all of the incoming values are constants, and the result of 939 // evaluating this expression with all incoming value pairs is the 940 // same, then this expression is a constant even though the PHI node 941 // is not a constant! 942 LatticeVal Result; 943 for (unsigned i = 0, e = PN1->getNumIncomingValues(); i != e; ++i) { 944 LatticeVal &In1 = getValueState(PN1->getIncomingValue(i)); 945 BasicBlock *InBlock = PN1->getIncomingBlock(i); 946 LatticeVal &In2 = 947 getValueState(PN2->getIncomingValueForBlock(InBlock)); 948 949 if (In1.isOverdefined() || In2.isOverdefined()) { 950 Result.markOverdefined(); 951 break; // Cannot fold this operation over the PHI nodes! 952 } else if (In1.isConstant() && In2.isConstant()) { 953 Constant *V = ConstantExpr::getCompare(I.getPredicate(), 954 In1.getConstant(), 955 In2.getConstant()); 956 if (Result.isUndefined()) 957 Result.markConstant(V); 958 else if (Result.isConstant() && Result.getConstant() != V) { 959 Result.markOverdefined(); 960 break; 961 } 962 } 963 } 964 965 // If we found a constant value here, then we know the instruction is 966 // constant despite the fact that the PHI nodes are overdefined. 967 if (Result.isConstant()) { 968 markConstant(IV, &I, Result.getConstant()); 969 // Remember that this instruction is virtually using the PHI node 970 // operands. 971 UsersOfOverdefinedPHIs.insert(std::make_pair(PN1, &I)); 972 UsersOfOverdefinedPHIs.insert(std::make_pair(PN2, &I)); 973 return; 974 } else if (Result.isUndefined()) { 975 return; 976 } 977 978 // Okay, this really is overdefined now. Since we might have 979 // speculatively thought that this was not overdefined before, and 980 // added ourselves to the UsersOfOverdefinedPHIs list for the PHIs, 981 // make sure to clean out any entries that we put there, for 982 // efficiency. 983 std::multimap<PHINode*, Instruction*>::iterator It, E; 984 tie(It, E) = UsersOfOverdefinedPHIs.equal_range(PN1); 985 while (It != E) { 986 if (It->second == &I) { 987 UsersOfOverdefinedPHIs.erase(It++); 988 } else 989 ++It; 990 } 991 tie(It, E) = UsersOfOverdefinedPHIs.equal_range(PN2); 992 while (It != E) { 993 if (It->second == &I) { 994 UsersOfOverdefinedPHIs.erase(It++); 995 } else 996 ++It; 997 } 998 } 999 1000 markOverdefined(IV, &I); 1001 } else if (V1State.isConstant() && V2State.isConstant()) { 1002 markConstant(IV, &I, ConstantExpr::getCompare(I.getPredicate(), 1003 V1State.getConstant(), 1004 V2State.getConstant())); 1005 } 1006} 1007 1008void SCCPSolver::visitExtractElementInst(ExtractElementInst &I) { 1009 // FIXME : SCCP does not handle vectors properly. 1010 markOverdefined(&I); 1011 return; 1012 1013#if 0 1014 LatticeVal &ValState = getValueState(I.getOperand(0)); 1015 LatticeVal &IdxState = getValueState(I.getOperand(1)); 1016 1017 if (ValState.isOverdefined() || IdxState.isOverdefined()) 1018 markOverdefined(&I); 1019 else if(ValState.isConstant() && IdxState.isConstant()) 1020 markConstant(&I, ConstantExpr::getExtractElement(ValState.getConstant(), 1021 IdxState.getConstant())); 1022#endif 1023} 1024 1025void SCCPSolver::visitInsertElementInst(InsertElementInst &I) { 1026 // FIXME : SCCP does not handle vectors properly. 1027 markOverdefined(&I); 1028 return; 1029#if 0 1030 LatticeVal &ValState = getValueState(I.getOperand(0)); 1031 LatticeVal &EltState = getValueState(I.getOperand(1)); 1032 LatticeVal &IdxState = getValueState(I.getOperand(2)); 1033 1034 if (ValState.isOverdefined() || EltState.isOverdefined() || 1035 IdxState.isOverdefined()) 1036 markOverdefined(&I); 1037 else if(ValState.isConstant() && EltState.isConstant() && 1038 IdxState.isConstant()) 1039 markConstant(&I, ConstantExpr::getInsertElement(ValState.getConstant(), 1040 EltState.getConstant(), 1041 IdxState.getConstant())); 1042 else if (ValState.isUndefined() && EltState.isConstant() && 1043 IdxState.isConstant()) 1044 markConstant(&I,ConstantExpr::getInsertElement(UndefValue::get(I.getType()), 1045 EltState.getConstant(), 1046 IdxState.getConstant())); 1047#endif 1048} 1049 1050void SCCPSolver::visitShuffleVectorInst(ShuffleVectorInst &I) { 1051 // FIXME : SCCP does not handle vectors properly. 1052 markOverdefined(&I); 1053 return; 1054#if 0 1055 LatticeVal &V1State = getValueState(I.getOperand(0)); 1056 LatticeVal &V2State = getValueState(I.getOperand(1)); 1057 LatticeVal &MaskState = getValueState(I.getOperand(2)); 1058 1059 if (MaskState.isUndefined() || 1060 (V1State.isUndefined() && V2State.isUndefined())) 1061 return; // Undefined output if mask or both inputs undefined. 1062 1063 if (V1State.isOverdefined() || V2State.isOverdefined() || 1064 MaskState.isOverdefined()) { 1065 markOverdefined(&I); 1066 } else { 1067 // A mix of constant/undef inputs. 1068 Constant *V1 = V1State.isConstant() ? 1069 V1State.getConstant() : UndefValue::get(I.getType()); 1070 Constant *V2 = V2State.isConstant() ? 1071 V2State.getConstant() : UndefValue::get(I.getType()); 1072 Constant *Mask = MaskState.isConstant() ? 1073 MaskState.getConstant() : UndefValue::get(I.getOperand(2)->getType()); 1074 markConstant(&I, ConstantExpr::getShuffleVector(V1, V2, Mask)); 1075 } 1076#endif 1077} 1078 1079// Handle getelementptr instructions... if all operands are constants then we 1080// can turn this into a getelementptr ConstantExpr. 1081// 1082void SCCPSolver::visitGetElementPtrInst(GetElementPtrInst &I) { 1083 LatticeVal &IV = ValueState[&I]; 1084 if (IV.isOverdefined()) return; 1085 1086 SmallVector<Constant*, 8> Operands; 1087 Operands.reserve(I.getNumOperands()); 1088 1089 for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) { 1090 LatticeVal &State = getValueState(I.getOperand(i)); 1091 if (State.isUndefined()) 1092 return; // Operands are not resolved yet... 1093 else if (State.isOverdefined()) { 1094 markOverdefined(IV, &I); 1095 return; 1096 } 1097 assert(State.isConstant() && "Unknown state!"); 1098 Operands.push_back(State.getConstant()); 1099 } 1100 1101 Constant *Ptr = Operands[0]; 1102 Operands.erase(Operands.begin()); // Erase the pointer from idx list... 1103 1104 markConstant(IV, &I, ConstantExpr::getGetElementPtr(Ptr, &Operands[0], 1105 Operands.size())); 1106} 1107 1108void SCCPSolver::visitStoreInst(Instruction &SI) { 1109 if (TrackedGlobals.empty() || !isa<GlobalVariable>(SI.getOperand(1))) 1110 return; 1111 GlobalVariable *GV = cast<GlobalVariable>(SI.getOperand(1)); 1112 DenseMap<GlobalVariable*, LatticeVal>::iterator I = TrackedGlobals.find(GV); 1113 if (I == TrackedGlobals.end() || I->second.isOverdefined()) return; 1114 1115 // Get the value we are storing into the global. 1116 LatticeVal &PtrVal = getValueState(SI.getOperand(0)); 1117 1118 mergeInValue(I->second, GV, PtrVal); 1119 if (I->second.isOverdefined()) 1120 TrackedGlobals.erase(I); // No need to keep tracking this! 1121} 1122 1123 1124// Handle load instructions. If the operand is a constant pointer to a constant 1125// global, we can replace the load with the loaded constant value! 1126void SCCPSolver::visitLoadInst(LoadInst &I) { 1127 LatticeVal &IV = ValueState[&I]; 1128 if (IV.isOverdefined()) return; 1129 1130 LatticeVal &PtrVal = getValueState(I.getOperand(0)); 1131 if (PtrVal.isUndefined()) return; // The pointer is not resolved yet! 1132 if (PtrVal.isConstant() && !I.isVolatile()) { 1133 Value *Ptr = PtrVal.getConstant(); 1134 // TODO: Consider a target hook for valid address spaces for this xform. 1135 if (isa<ConstantPointerNull>(Ptr) && I.getPointerAddressSpace() == 0) { 1136 // load null -> null 1137 markConstant(IV, &I, Constant::getNullValue(I.getType())); 1138 return; 1139 } 1140 1141 // Transform load (constant global) into the value loaded. 1142 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Ptr)) { 1143 if (GV->isConstant()) { 1144 if (GV->hasDefinitiveInitializer()) { 1145 markConstant(IV, &I, GV->getInitializer()); 1146 return; 1147 } 1148 } else if (!TrackedGlobals.empty()) { 1149 // If we are tracking this global, merge in the known value for it. 1150 DenseMap<GlobalVariable*, LatticeVal>::iterator It = 1151 TrackedGlobals.find(GV); 1152 if (It != TrackedGlobals.end()) { 1153 mergeInValue(IV, &I, It->second); 1154 return; 1155 } 1156 } 1157 } 1158 1159 // Transform load (constantexpr_GEP global, 0, ...) into the value loaded. 1160 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Ptr)) 1161 if (CE->getOpcode() == Instruction::GetElementPtr) 1162 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(CE->getOperand(0))) 1163 if (GV->isConstant() && GV->hasDefinitiveInitializer()) 1164 if (Constant *V = 1165 ConstantFoldLoadThroughGEPConstantExpr(GV->getInitializer(), CE, 1166 *Context)) { 1167 markConstant(IV, &I, V); 1168 return; 1169 } 1170 } 1171 1172 // Otherwise we cannot say for certain what value this load will produce. 1173 // Bail out. 1174 markOverdefined(IV, &I); 1175} 1176 1177void SCCPSolver::visitCallSite(CallSite CS) { 1178 Function *F = CS.getCalledFunction(); 1179 Instruction *I = CS.getInstruction(); 1180 1181 // The common case is that we aren't tracking the callee, either because we 1182 // are not doing interprocedural analysis or the callee is indirect, or is 1183 // external. Handle these cases first. 1184 if (F == 0 || !F->hasLocalLinkage()) { 1185CallOverdefined: 1186 // Void return and not tracking callee, just bail. 1187 if (I->getType()->isVoidTy()) return; 1188 1189 // Otherwise, if we have a single return value case, and if the function is 1190 // a declaration, maybe we can constant fold it. 1191 if (!isa<StructType>(I->getType()) && F && F->isDeclaration() && 1192 canConstantFoldCallTo(F)) { 1193 1194 SmallVector<Constant*, 8> Operands; 1195 for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end(); 1196 AI != E; ++AI) { 1197 LatticeVal &State = getValueState(*AI); 1198 if (State.isUndefined()) 1199 return; // Operands are not resolved yet. 1200 else if (State.isOverdefined()) { 1201 markOverdefined(I); 1202 return; 1203 } 1204 assert(State.isConstant() && "Unknown state!"); 1205 Operands.push_back(State.getConstant()); 1206 } 1207 1208 // If we can constant fold this, mark the result of the call as a 1209 // constant. 1210 if (Constant *C = ConstantFoldCall(F, Operands.data(), Operands.size())) { 1211 markConstant(I, C); 1212 return; 1213 } 1214 } 1215 1216 // Otherwise, we don't know anything about this call, mark it overdefined. 1217 markOverdefined(I); 1218 return; 1219 } 1220 1221 // If this is a single/zero retval case, see if we're tracking the function. 1222 DenseMap<Function*, LatticeVal>::iterator TFRVI = TrackedRetVals.find(F); 1223 if (TFRVI != TrackedRetVals.end()) { 1224 // If so, propagate the return value of the callee into this call result. 1225 mergeInValue(I, TFRVI->second); 1226 } else if (isa<StructType>(I->getType())) { 1227 // Check to see if we're tracking this callee, if not, handle it in the 1228 // common path above. 1229 DenseMap<std::pair<Function*, unsigned>, LatticeVal>::iterator 1230 TMRVI = TrackedMultipleRetVals.find(std::make_pair(F, 0)); 1231 if (TMRVI == TrackedMultipleRetVals.end()) 1232 goto CallOverdefined; 1233 1234 // If we are tracking this callee, propagate the return values of the call 1235 // into this call site. We do this by walking all the uses. Single-index 1236 // ExtractValueInst uses can be tracked; anything more complicated is 1237 // currently handled conservatively. 1238 for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); 1239 UI != E; ++UI) { 1240 if (ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(*UI)) { 1241 if (EVI->getNumIndices() == 1) { 1242 mergeInValue(EVI, 1243 TrackedMultipleRetVals[std::make_pair(F, *EVI->idx_begin())]); 1244 continue; 1245 } 1246 } 1247 // The aggregate value is used in a way not handled here. Assume nothing. 1248 markOverdefined(*UI); 1249 } 1250 } else { 1251 // Otherwise we're not tracking this callee, so handle it in the 1252 // common path above. 1253 goto CallOverdefined; 1254 } 1255 1256 // Finally, if this is the first call to the function hit, mark its entry 1257 // block executable. 1258 if (!BBExecutable.count(F->begin())) 1259 MarkBlockExecutable(F->begin()); 1260 1261 // Propagate information from this call site into the callee. 1262 CallSite::arg_iterator CAI = CS.arg_begin(); 1263 for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end(); 1264 AI != E; ++AI, ++CAI) { 1265 LatticeVal &IV = ValueState[AI]; 1266 if (AI->hasByValAttr() && !F->onlyReadsMemory()) { 1267 IV.markOverdefined(); 1268 continue; 1269 } 1270 if (!IV.isOverdefined()) 1271 mergeInValue(IV, AI, getValueState(*CAI)); 1272 } 1273} 1274 1275 1276void SCCPSolver::Solve() { 1277 // Process the work lists until they are empty! 1278 while (!BBWorkList.empty() || !InstWorkList.empty() || 1279 !OverdefinedInstWorkList.empty()) { 1280 // Process the instruction work list... 1281 while (!OverdefinedInstWorkList.empty()) { 1282 Value *I = OverdefinedInstWorkList.back(); 1283 OverdefinedInstWorkList.pop_back(); 1284 1285 DEBUG(errs() << "\nPopped off OI-WL: " << *I << '\n'); 1286 1287 // "I" got into the work list because it either made the transition from 1288 // bottom to constant 1289 // 1290 // Anything on this worklist that is overdefined need not be visited 1291 // since all of its users will have already been marked as overdefined 1292 // Update all of the users of this instruction's value... 1293 // 1294 for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); 1295 UI != E; ++UI) 1296 OperandChangedState(*UI); 1297 } 1298 // Process the instruction work list... 1299 while (!InstWorkList.empty()) { 1300 Value *I = InstWorkList.back(); 1301 InstWorkList.pop_back(); 1302 1303 DEBUG(errs() << "\nPopped off I-WL: " << *I << '\n'); 1304 1305 // "I" got into the work list because it either made the transition from 1306 // bottom to constant 1307 // 1308 // Anything on this worklist that is overdefined need not be visited 1309 // since all of its users will have already been marked as overdefined. 1310 // Update all of the users of this instruction's value... 1311 // 1312 if (!getValueState(I).isOverdefined()) 1313 for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); 1314 UI != E; ++UI) 1315 OperandChangedState(*UI); 1316 } 1317 1318 // Process the basic block work list... 1319 while (!BBWorkList.empty()) { 1320 BasicBlock *BB = BBWorkList.back(); 1321 BBWorkList.pop_back(); 1322 1323 DEBUG(errs() << "\nPopped off BBWL: " << *BB << '\n'); 1324 1325 // Notify all instructions in this basic block that they are newly 1326 // executable. 1327 visit(BB); 1328 } 1329 } 1330} 1331 1332/// ResolvedUndefsIn - While solving the dataflow for a function, we assume 1333/// that branches on undef values cannot reach any of their successors. 1334/// However, this is not a safe assumption. After we solve dataflow, this 1335/// method should be use to handle this. If this returns true, the solver 1336/// should be rerun. 1337/// 1338/// This method handles this by finding an unresolved branch and marking it one 1339/// of the edges from the block as being feasible, even though the condition 1340/// doesn't say it would otherwise be. This allows SCCP to find the rest of the 1341/// CFG and only slightly pessimizes the analysis results (by marking one, 1342/// potentially infeasible, edge feasible). This cannot usefully modify the 1343/// constraints on the condition of the branch, as that would impact other users 1344/// of the value. 1345/// 1346/// This scan also checks for values that use undefs, whose results are actually 1347/// defined. For example, 'zext i8 undef to i32' should produce all zeros 1348/// conservatively, as "(zext i8 X -> i32) & 0xFF00" must always return zero, 1349/// even if X isn't defined. 1350bool SCCPSolver::ResolvedUndefsIn(Function &F) { 1351 for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) { 1352 if (!BBExecutable.count(BB)) 1353 continue; 1354 1355 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) { 1356 // Look for instructions which produce undef values. 1357 if (I->getType()->isVoidTy()) continue; 1358 1359 LatticeVal &LV = getValueState(I); 1360 if (!LV.isUndefined()) continue; 1361 1362 // Get the lattice values of the first two operands for use below. 1363 LatticeVal &Op0LV = getValueState(I->getOperand(0)); 1364 LatticeVal Op1LV; 1365 if (I->getNumOperands() == 2) { 1366 // If this is a two-operand instruction, and if both operands are 1367 // undefs, the result stays undef. 1368 Op1LV = getValueState(I->getOperand(1)); 1369 if (Op0LV.isUndefined() && Op1LV.isUndefined()) 1370 continue; 1371 } 1372 1373 // If this is an instructions whose result is defined even if the input is 1374 // not fully defined, propagate the information. 1375 const Type *ITy = I->getType(); 1376 switch (I->getOpcode()) { 1377 default: break; // Leave the instruction as an undef. 1378 case Instruction::ZExt: 1379 // After a zero extend, we know the top part is zero. SExt doesn't have 1380 // to be handled here, because we don't know whether the top part is 1's 1381 // or 0's. 1382 assert(Op0LV.isUndefined()); 1383 markForcedConstant(LV, I, Constant::getNullValue(ITy)); 1384 return true; 1385 case Instruction::Mul: 1386 case Instruction::And: 1387 // undef * X -> 0. X could be zero. 1388 // undef & X -> 0. X could be zero. 1389 markForcedConstant(LV, I, Constant::getNullValue(ITy)); 1390 return true; 1391 1392 case Instruction::Or: 1393 // undef | X -> -1. X could be -1. 1394 if (const VectorType *PTy = dyn_cast<VectorType>(ITy)) 1395 markForcedConstant(LV, I, 1396 Constant::getAllOnesValue(PTy)); 1397 else 1398 markForcedConstant(LV, I, Constant::getAllOnesValue(ITy)); 1399 return true; 1400 1401 case Instruction::SDiv: 1402 case Instruction::UDiv: 1403 case Instruction::SRem: 1404 case Instruction::URem: 1405 // X / undef -> undef. No change. 1406 // X % undef -> undef. No change. 1407 if (Op1LV.isUndefined()) break; 1408 1409 // undef / X -> 0. X could be maxint. 1410 // undef % X -> 0. X could be 1. 1411 markForcedConstant(LV, I, Constant::getNullValue(ITy)); 1412 return true; 1413 1414 case Instruction::AShr: 1415 // undef >>s X -> undef. No change. 1416 if (Op0LV.isUndefined()) break; 1417 1418 // X >>s undef -> X. X could be 0, X could have the high-bit known set. 1419 if (Op0LV.isConstant()) 1420 markForcedConstant(LV, I, Op0LV.getConstant()); 1421 else 1422 markOverdefined(LV, I); 1423 return true; 1424 case Instruction::LShr: 1425 case Instruction::Shl: 1426 // undef >> X -> undef. No change. 1427 // undef << X -> undef. No change. 1428 if (Op0LV.isUndefined()) break; 1429 1430 // X >> undef -> 0. X could be 0. 1431 // X << undef -> 0. X could be 0. 1432 markForcedConstant(LV, I, Constant::getNullValue(ITy)); 1433 return true; 1434 case Instruction::Select: 1435 // undef ? X : Y -> X or Y. There could be commonality between X/Y. 1436 if (Op0LV.isUndefined()) { 1437 if (!Op1LV.isConstant()) // Pick the constant one if there is any. 1438 Op1LV = getValueState(I->getOperand(2)); 1439 } else if (Op1LV.isUndefined()) { 1440 // c ? undef : undef -> undef. No change. 1441 Op1LV = getValueState(I->getOperand(2)); 1442 if (Op1LV.isUndefined()) 1443 break; 1444 // Otherwise, c ? undef : x -> x. 1445 } else { 1446 // Leave Op1LV as Operand(1)'s LatticeValue. 1447 } 1448 1449 if (Op1LV.isConstant()) 1450 markForcedConstant(LV, I, Op1LV.getConstant()); 1451 else 1452 markOverdefined(LV, I); 1453 return true; 1454 case Instruction::Call: 1455 // If a call has an undef result, it is because it is constant foldable 1456 // but one of the inputs was undef. Just force the result to 1457 // overdefined. 1458 markOverdefined(LV, I); 1459 return true; 1460 } 1461 } 1462 1463 TerminatorInst *TI = BB->getTerminator(); 1464 if (BranchInst *BI = dyn_cast<BranchInst>(TI)) { 1465 if (!BI->isConditional()) continue; 1466 if (!getValueState(BI->getCondition()).isUndefined()) 1467 continue; 1468 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 1469 if (SI->getNumSuccessors()<2) // no cases 1470 continue; 1471 if (!getValueState(SI->getCondition()).isUndefined()) 1472 continue; 1473 } else { 1474 continue; 1475 } 1476 1477 // If the edge to the second successor isn't thought to be feasible yet, 1478 // mark it so now. We pick the second one so that this goes to some 1479 // enumerated value in a switch instead of going to the default destination. 1480 if (KnownFeasibleEdges.count(Edge(BB, TI->getSuccessor(1)))) 1481 continue; 1482 1483 // Otherwise, it isn't already thought to be feasible. Mark it as such now 1484 // and return. This will make other blocks reachable, which will allow new 1485 // values to be discovered and existing ones to be moved in the lattice. 1486 markEdgeExecutable(BB, TI->getSuccessor(1)); 1487 1488 // This must be a conditional branch of switch on undef. At this point, 1489 // force the old terminator to branch to the first successor. This is 1490 // required because we are now influencing the dataflow of the function with 1491 // the assumption that this edge is taken. If we leave the branch condition 1492 // as undef, then further analysis could think the undef went another way 1493 // leading to an inconsistent set of conclusions. 1494 if (BranchInst *BI = dyn_cast<BranchInst>(TI)) { 1495 BI->setCondition(ConstantInt::getFalse(*Context)); 1496 } else { 1497 SwitchInst *SI = cast<SwitchInst>(TI); 1498 SI->setCondition(SI->getCaseValue(1)); 1499 } 1500 1501 return true; 1502 } 1503 1504 return false; 1505} 1506 1507 1508namespace { 1509 //===--------------------------------------------------------------------===// 1510 // 1511 /// SCCP Class - This class uses the SCCPSolver to implement a per-function 1512 /// Sparse Conditional Constant Propagator. 1513 /// 1514 struct SCCP : public FunctionPass { 1515 static char ID; // Pass identification, replacement for typeid 1516 SCCP() : FunctionPass(&ID) {} 1517 1518 // runOnFunction - Run the Sparse Conditional Constant Propagation 1519 // algorithm, and return true if the function was modified. 1520 // 1521 bool runOnFunction(Function &F); 1522 1523 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 1524 AU.setPreservesCFG(); 1525 } 1526 }; 1527} // end anonymous namespace 1528 1529char SCCP::ID = 0; 1530static RegisterPass<SCCP> 1531X("sccp", "Sparse Conditional Constant Propagation"); 1532 1533// createSCCPPass - This is the public interface to this file... 1534FunctionPass *llvm::createSCCPPass() { 1535 return new SCCP(); 1536} 1537 1538 1539// runOnFunction() - Run the Sparse Conditional Constant Propagation algorithm, 1540// and return true if the function was modified. 1541// 1542bool SCCP::runOnFunction(Function &F) { 1543 DEBUG(errs() << "SCCP on function '" << F.getName() << "'\n"); 1544 SCCPSolver Solver; 1545 Solver.setContext(&F.getContext()); 1546 1547 // Mark the first block of the function as being executable. 1548 Solver.MarkBlockExecutable(F.begin()); 1549 1550 // Mark all arguments to the function as being overdefined. 1551 for (Function::arg_iterator AI = F.arg_begin(), E = F.arg_end(); AI != E;++AI) 1552 Solver.markOverdefined(AI); 1553 1554 // Solve for constants. 1555 bool ResolvedUndefs = true; 1556 while (ResolvedUndefs) { 1557 Solver.Solve(); 1558 DEBUG(errs() << "RESOLVING UNDEFs\n"); 1559 ResolvedUndefs = Solver.ResolvedUndefsIn(F); 1560 } 1561 1562 bool MadeChanges = false; 1563 1564 // If we decided that there are basic blocks that are dead in this function, 1565 // delete their contents now. Note that we cannot actually delete the blocks, 1566 // as we cannot modify the CFG of the function. 1567 // 1568 SmallVector<Instruction*, 512> Insts; 1569 std::map<Value*, LatticeVal> &Values = Solver.getValueMapping(); 1570 1571 for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) 1572 if (!Solver.isBlockExecutable(BB)) { 1573 DEBUG(errs() << " BasicBlock Dead:" << *BB); 1574 ++NumDeadBlocks; 1575 1576 // Delete the instructions backwards, as it has a reduced likelihood of 1577 // having to update as many def-use and use-def chains. 1578 for (BasicBlock::iterator I = BB->begin(), E = BB->getTerminator(); 1579 I != E; ++I) 1580 Insts.push_back(I); 1581 while (!Insts.empty()) { 1582 Instruction *I = Insts.back(); 1583 Insts.pop_back(); 1584 if (!I->use_empty()) 1585 I->replaceAllUsesWith(UndefValue::get(I->getType())); 1586 BB->getInstList().erase(I); 1587 MadeChanges = true; 1588 ++NumInstRemoved; 1589 } 1590 } else { 1591 // Iterate over all of the instructions in a function, replacing them with 1592 // constants if we have found them to be of constant values. 1593 // 1594 for (BasicBlock::iterator BI = BB->begin(), E = BB->end(); BI != E; ) { 1595 Instruction *Inst = BI++; 1596 if (Inst->getType()->isVoidTy() || isa<TerminatorInst>(Inst)) 1597 continue; 1598 1599 LatticeVal &IV = Values[Inst]; 1600 if (!IV.isConstant() && !IV.isUndefined()) 1601 continue; 1602 1603 Constant *Const = IV.isConstant() 1604 ? IV.getConstant() : UndefValue::get(Inst->getType()); 1605 DEBUG(errs() << " Constant: " << *Const << " = " << *Inst); 1606 1607 // Replaces all of the uses of a variable with uses of the constant. 1608 Inst->replaceAllUsesWith(Const); 1609 1610 // Delete the instruction. 1611 Inst->eraseFromParent(); 1612 1613 // Hey, we just changed something! 1614 MadeChanges = true; 1615 ++NumInstRemoved; 1616 } 1617 } 1618 1619 return MadeChanges; 1620} 1621 1622namespace { 1623 //===--------------------------------------------------------------------===// 1624 // 1625 /// IPSCCP Class - This class implements interprocedural Sparse Conditional 1626 /// Constant Propagation. 1627 /// 1628 struct IPSCCP : public ModulePass { 1629 static char ID; 1630 IPSCCP() : ModulePass(&ID) {} 1631 bool runOnModule(Module &M); 1632 }; 1633} // end anonymous namespace 1634 1635char IPSCCP::ID = 0; 1636static RegisterPass<IPSCCP> 1637Y("ipsccp", "Interprocedural Sparse Conditional Constant Propagation"); 1638 1639// createIPSCCPPass - This is the public interface to this file... 1640ModulePass *llvm::createIPSCCPPass() { 1641 return new IPSCCP(); 1642} 1643 1644 1645static bool AddressIsTaken(GlobalValue *GV) { 1646 // Delete any dead constantexpr klingons. 1647 GV->removeDeadConstantUsers(); 1648 1649 for (Value::use_iterator UI = GV->use_begin(), E = GV->use_end(); 1650 UI != E; ++UI) 1651 if (StoreInst *SI = dyn_cast<StoreInst>(*UI)) { 1652 if (SI->getOperand(0) == GV || SI->isVolatile()) 1653 return true; // Storing addr of GV. 1654 } else if (isa<InvokeInst>(*UI) || isa<CallInst>(*UI)) { 1655 // Make sure we are calling the function, not passing the address. 1656 CallSite CS = CallSite::get(cast<Instruction>(*UI)); 1657 if (CS.hasArgument(GV)) 1658 return true; 1659 } else if (LoadInst *LI = dyn_cast<LoadInst>(*UI)) { 1660 if (LI->isVolatile()) 1661 return true; 1662 } else { 1663 return true; 1664 } 1665 return false; 1666} 1667 1668bool IPSCCP::runOnModule(Module &M) { 1669 LLVMContext *Context = &M.getContext(); 1670 1671 SCCPSolver Solver; 1672 Solver.setContext(Context); 1673 1674 // Loop over all functions, marking arguments to those with their addresses 1675 // taken or that are external as overdefined. 1676 // 1677 for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) 1678 if (!F->hasLocalLinkage() || AddressIsTaken(F)) { 1679 if (!F->isDeclaration()) 1680 Solver.MarkBlockExecutable(F->begin()); 1681 for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end(); 1682 AI != E; ++AI) 1683 Solver.markOverdefined(AI); 1684 } else { 1685 Solver.AddTrackedFunction(F); 1686 } 1687 1688 // Loop over global variables. We inform the solver about any internal global 1689 // variables that do not have their 'addresses taken'. If they don't have 1690 // their addresses taken, we can propagate constants through them. 1691 for (Module::global_iterator G = M.global_begin(), E = M.global_end(); 1692 G != E; ++G) 1693 if (!G->isConstant() && G->hasLocalLinkage() && !AddressIsTaken(G)) 1694 Solver.TrackValueOfGlobalVariable(G); 1695 1696 // Solve for constants. 1697 bool ResolvedUndefs = true; 1698 while (ResolvedUndefs) { 1699 Solver.Solve(); 1700 1701 DEBUG(errs() << "RESOLVING UNDEFS\n"); 1702 ResolvedUndefs = false; 1703 for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) 1704 ResolvedUndefs |= Solver.ResolvedUndefsIn(*F); 1705 } 1706 1707 bool MadeChanges = false; 1708 1709 // Iterate over all of the instructions in the module, replacing them with 1710 // constants if we have found them to be of constant values. 1711 // 1712 SmallVector<Instruction*, 512> Insts; 1713 SmallVector<BasicBlock*, 512> BlocksToErase; 1714 std::map<Value*, LatticeVal> &Values = Solver.getValueMapping(); 1715 1716 for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) { 1717 for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end(); 1718 AI != E; ++AI) 1719 if (!AI->use_empty()) { 1720 LatticeVal &IV = Values[AI]; 1721 if (IV.isConstant() || IV.isUndefined()) { 1722 Constant *CST = IV.isConstant() ? 1723 IV.getConstant() : UndefValue::get(AI->getType()); 1724 DEBUG(errs() << "*** Arg " << *AI << " = " << *CST <<"\n"); 1725 1726 // Replaces all of the uses of a variable with uses of the 1727 // constant. 1728 AI->replaceAllUsesWith(CST); 1729 ++IPNumArgsElimed; 1730 } 1731 } 1732 1733 for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) 1734 if (!Solver.isBlockExecutable(BB)) { 1735 DEBUG(errs() << " BasicBlock Dead:" << *BB); 1736 ++IPNumDeadBlocks; 1737 1738 // Delete the instructions backwards, as it has a reduced likelihood of 1739 // having to update as many def-use and use-def chains. 1740 TerminatorInst *TI = BB->getTerminator(); 1741 for (BasicBlock::iterator I = BB->begin(), E = TI; I != E; ++I) 1742 Insts.push_back(I); 1743 1744 while (!Insts.empty()) { 1745 Instruction *I = Insts.back(); 1746 Insts.pop_back(); 1747 if (!I->use_empty()) 1748 I->replaceAllUsesWith(UndefValue::get(I->getType())); 1749 BB->getInstList().erase(I); 1750 MadeChanges = true; 1751 ++IPNumInstRemoved; 1752 } 1753 1754 for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) { 1755 BasicBlock *Succ = TI->getSuccessor(i); 1756 if (!Succ->empty() && isa<PHINode>(Succ->begin())) 1757 TI->getSuccessor(i)->removePredecessor(BB); 1758 } 1759 if (!TI->use_empty()) 1760 TI->replaceAllUsesWith(UndefValue::get(TI->getType())); 1761 BB->getInstList().erase(TI); 1762 1763 if (&*BB != &F->front()) 1764 BlocksToErase.push_back(BB); 1765 else 1766 new UnreachableInst(M.getContext(), BB); 1767 1768 } else { 1769 for (BasicBlock::iterator BI = BB->begin(), E = BB->end(); BI != E; ) { 1770 Instruction *Inst = BI++; 1771 if (Inst->getType()->isVoidTy()) 1772 continue; 1773 1774 LatticeVal &IV = Values[Inst]; 1775 if (!IV.isConstant() && !IV.isUndefined()) 1776 continue; 1777 1778 Constant *Const = IV.isConstant() 1779 ? IV.getConstant() : UndefValue::get(Inst->getType()); 1780 DEBUG(errs() << " Constant: " << *Const << " = " << *Inst); 1781 1782 // Replaces all of the uses of a variable with uses of the 1783 // constant. 1784 Inst->replaceAllUsesWith(Const); 1785 1786 // Delete the instruction. 1787 if (!isa<CallInst>(Inst) && !isa<TerminatorInst>(Inst)) 1788 Inst->eraseFromParent(); 1789 1790 // Hey, we just changed something! 1791 MadeChanges = true; 1792 ++IPNumInstRemoved; 1793 } 1794 } 1795 1796 // Now that all instructions in the function are constant folded, erase dead 1797 // blocks, because we can now use ConstantFoldTerminator to get rid of 1798 // in-edges. 1799 for (unsigned i = 0, e = BlocksToErase.size(); i != e; ++i) { 1800 // If there are any PHI nodes in this successor, drop entries for BB now. 1801 BasicBlock *DeadBB = BlocksToErase[i]; 1802 while (!DeadBB->use_empty()) { 1803 Instruction *I = cast<Instruction>(DeadBB->use_back()); 1804 bool Folded = ConstantFoldTerminator(I->getParent()); 1805 if (!Folded) { 1806 // The constant folder may not have been able to fold the terminator 1807 // if this is a branch or switch on undef. Fold it manually as a 1808 // branch to the first successor. 1809#ifndef NDEBUG 1810 if (BranchInst *BI = dyn_cast<BranchInst>(I)) { 1811 assert(BI->isConditional() && isa<UndefValue>(BI->getCondition()) && 1812 "Branch should be foldable!"); 1813 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(I)) { 1814 assert(isa<UndefValue>(SI->getCondition()) && "Switch should fold"); 1815 } else { 1816 llvm_unreachable("Didn't fold away reference to block!"); 1817 } 1818#endif 1819 1820 // Make this an uncond branch to the first successor. 1821 TerminatorInst *TI = I->getParent()->getTerminator(); 1822 BranchInst::Create(TI->getSuccessor(0), TI); 1823 1824 // Remove entries in successor phi nodes to remove edges. 1825 for (unsigned i = 1, e = TI->getNumSuccessors(); i != e; ++i) 1826 TI->getSuccessor(i)->removePredecessor(TI->getParent()); 1827 1828 // Remove the old terminator. 1829 TI->eraseFromParent(); 1830 } 1831 } 1832 1833 // Finally, delete the basic block. 1834 F->getBasicBlockList().erase(DeadBB); 1835 } 1836 BlocksToErase.clear(); 1837 } 1838 1839 // If we inferred constant or undef return values for a function, we replaced 1840 // all call uses with the inferred value. This means we don't need to bother 1841 // actually returning anything from the function. Replace all return 1842 // instructions with return undef. 1843 // TODO: Process multiple value ret instructions also. 1844 const DenseMap<Function*, LatticeVal> &RV = Solver.getTrackedRetVals(); 1845 for (DenseMap<Function*, LatticeVal>::const_iterator I = RV.begin(), 1846 E = RV.end(); I != E; ++I) 1847 if (!I->second.isOverdefined() && 1848 !I->first->getReturnType()->isVoidTy()) { 1849 Function *F = I->first; 1850 for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) 1851 if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) 1852 if (!isa<UndefValue>(RI->getOperand(0))) 1853 RI->setOperand(0, UndefValue::get(F->getReturnType())); 1854 } 1855 1856 // If we infered constant or undef values for globals variables, we can delete 1857 // the global and any stores that remain to it. 1858 const DenseMap<GlobalVariable*, LatticeVal> &TG = Solver.getTrackedGlobals(); 1859 for (DenseMap<GlobalVariable*, LatticeVal>::const_iterator I = TG.begin(), 1860 E = TG.end(); I != E; ++I) { 1861 GlobalVariable *GV = I->first; 1862 assert(!I->second.isOverdefined() && 1863 "Overdefined values should have been taken out of the map!"); 1864 DEBUG(errs() << "Found that GV '" << GV->getName() << "' is constant!\n"); 1865 while (!GV->use_empty()) { 1866 StoreInst *SI = cast<StoreInst>(GV->use_back()); 1867 SI->eraseFromParent(); 1868 } 1869 M.getGlobalList().erase(GV); 1870 ++IPNumGlobalConst; 1871 } 1872 1873 return MadeChanges; 1874} 1875