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