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