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