lib/Transforms/Scalar/SCCP.cpp

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