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