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