LLVM  12.0.0git
SCCP.cpp
Go to the documentation of this file.
1 //===- SCCP.cpp - Sparse Conditional Constant Propagation -----------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file implements sparse conditional constant propagation and merging:
10 //
11 // Specifically, this:
12 // * Assumes values are constant unless proven otherwise
13 // * Assumes BasicBlocks are dead unless proven otherwise
14 // * Proves values to be constant, and replaces them with constants
15 // * Proves conditional branches to be unconditional
16 //
17 //===----------------------------------------------------------------------===//
18 
20 #include "llvm/ADT/ArrayRef.h"
21 #include "llvm/ADT/DenseMap.h"
22 #include "llvm/ADT/DenseSet.h"
23 #include "llvm/ADT/MapVector.h"
25 #include "llvm/ADT/STLExtras.h"
26 #include "llvm/ADT/SetVector.h"
27 #include "llvm/ADT/SmallPtrSet.h"
28 #include "llvm/ADT/SmallVector.h"
29 #include "llvm/ADT/Statistic.h"
38 #include "llvm/IR/BasicBlock.h"
39 #include "llvm/IR/Constant.h"
40 #include "llvm/IR/Constants.h"
41 #include "llvm/IR/DataLayout.h"
42 #include "llvm/IR/DerivedTypes.h"
43 #include "llvm/IR/Function.h"
44 #include "llvm/IR/GlobalVariable.h"
45 #include "llvm/IR/InstVisitor.h"
46 #include "llvm/IR/InstrTypes.h"
47 #include "llvm/IR/Instruction.h"
48 #include "llvm/IR/Instructions.h"
49 #include "llvm/IR/Module.h"
50 #include "llvm/IR/PassManager.h"
51 #include "llvm/IR/Type.h"
52 #include "llvm/IR/User.h"
53 #include "llvm/IR/Value.h"
54 #include "llvm/InitializePasses.h"
55 #include "llvm/Pass.h"
56 #include "llvm/Support/Casting.h"
57 #include "llvm/Support/Debug.h"
60 #include "llvm/Transforms/Scalar.h"
63 #include <cassert>
64 #include <utility>
65 #include <vector>
66 
67 using namespace llvm;
68 
69 #define DEBUG_TYPE "sccp"
70 
71 STATISTIC(NumInstRemoved, "Number of instructions removed");
72 STATISTIC(NumDeadBlocks , "Number of basic blocks unreachable");
73 STATISTIC(NumInstReplaced,
74  "Number of instructions replaced with (simpler) instruction");
75 
76 STATISTIC(IPNumInstRemoved, "Number of instructions removed by IPSCCP");
77 STATISTIC(IPNumArgsElimed ,"Number of arguments constant propagated by IPSCCP");
78 STATISTIC(IPNumGlobalConst, "Number of globals found to be constant by IPSCCP");
79 STATISTIC(
80  IPNumInstReplaced,
81  "Number of instructions replaced with (simpler) instruction by IPSCCP");
82 
83 // The maximum number of range extensions allowed for operations requiring
84 // widening.
85 static const unsigned MaxNumRangeExtensions = 10;
86 
87 /// Returns MergeOptions with MaxWidenSteps set to MaxNumRangeExtensions.
90  MaxNumRangeExtensions);
91 }
92 namespace {
93 
94 // Helper to check if \p LV is either a constant or a constant
95 // range with a single element. This should cover exactly the same cases as the
96 // old ValueLatticeElement::isConstant() and is intended to be used in the
97 // transition to ValueLatticeElement.
98 bool isConstant(const ValueLatticeElement &LV) {
99  return LV.isConstant() ||
101 }
102 
103 // Helper to check if \p LV is either overdefined or a constant range with more
104 // than a single element. This should cover exactly the same cases as the old
105 // ValueLatticeElement::isOverdefined() and is intended to be used in the
106 // transition to ValueLatticeElement.
107 bool isOverdefined(const ValueLatticeElement &LV) {
108  return !LV.isUnknownOrUndef() && !isConstant(LV);
109 }
110 
111 //===----------------------------------------------------------------------===//
112 //
113 /// SCCPSolver - This class is a general purpose solver for Sparse Conditional
114 /// Constant Propagation.
115 ///
116 class SCCPSolver : public InstVisitor<SCCPSolver> {
117  const DataLayout &DL;
118  std::function<const TargetLibraryInfo &(Function &)> GetTLI;
119  SmallPtrSet<BasicBlock *, 8> BBExecutable; // The BBs that are executable.
121  ValueState; // The state each value is in.
122 
123  /// StructValueState - This maintains ValueState for values that have
124  /// StructType, for example for formal arguments, calls, insertelement, etc.
126 
127  /// GlobalValue - If we are tracking any values for the contents of a global
128  /// variable, we keep a mapping from the constant accessor to the element of
129  /// the global, to the currently known value. If the value becomes
130  /// overdefined, it's entry is simply removed from this map.
132 
133  /// TrackedRetVals - If we are tracking arguments into and the return
134  /// value out of a function, it will have an entry in this map, indicating
135  /// what the known return value for the function is.
137 
138  /// TrackedMultipleRetVals - Same as TrackedRetVals, but used for functions
139  /// that return multiple values.
141  TrackedMultipleRetVals;
142 
143  /// MRVFunctionsTracked - Each function in TrackedMultipleRetVals is
144  /// represented here for efficient lookup.
145  SmallPtrSet<Function *, 16> MRVFunctionsTracked;
146 
147  /// MustTailFunctions - Each function here is a callee of non-removable
148  /// musttail call site.
149  SmallPtrSet<Function *, 16> MustTailCallees;
150 
151  /// TrackingIncomingArguments - This is the set of functions for whose
152  /// arguments we make optimistic assumptions about and try to prove as
153  /// constants.
154  SmallPtrSet<Function *, 16> TrackingIncomingArguments;
155 
156  /// The reason for two worklists is that overdefined is the lowest state
157  /// on the lattice, and moving things to overdefined as fast as possible
158  /// makes SCCP converge much faster.
159  ///
160  /// By having a separate worklist, we accomplish this because everything
161  /// possibly overdefined will become overdefined at the soonest possible
162  /// point.
163  SmallVector<Value *, 64> OverdefinedInstWorkList;
164  SmallVector<Value *, 64> InstWorkList;
165 
166  // The BasicBlock work list
168 
169  /// KnownFeasibleEdges - Entries in this set are edges which have already had
170  /// PHI nodes retriggered.
171  using Edge = std::pair<BasicBlock *, BasicBlock *>;
172  DenseSet<Edge> KnownFeasibleEdges;
173 
176 
177  LLVMContext &Ctx;
178 
179 public:
180  void addAnalysis(Function &F, AnalysisResultsForFn A) {
181  AnalysisResults.insert({&F, std::move(A)});
182  }
183 
184  const PredicateBase *getPredicateInfoFor(Instruction *I) {
185  auto A = AnalysisResults.find(I->getParent()->getParent());
186  if (A == AnalysisResults.end())
187  return nullptr;
188  return A->second.PredInfo->getPredicateInfoFor(I);
189  }
190 
191  DomTreeUpdater getDTU(Function &F) {
192  auto A = AnalysisResults.find(&F);
193  assert(A != AnalysisResults.end() && "Need analysis results for function.");
194  return {A->second.DT, A->second.PDT, DomTreeUpdater::UpdateStrategy::Lazy};
195  }
196 
197  SCCPSolver(const DataLayout &DL,
198  std::function<const TargetLibraryInfo &(Function &)> GetTLI,
199  LLVMContext &Ctx)
200  : DL(DL), GetTLI(std::move(GetTLI)), Ctx(Ctx) {}
201 
202  /// MarkBlockExecutable - This method can be used by clients to mark all of
203  /// the blocks that are known to be intrinsically live in the processed unit.
204  ///
205  /// This returns true if the block was not considered live before.
206  bool MarkBlockExecutable(BasicBlock *BB) {
207  if (!BBExecutable.insert(BB).second)
208  return false;
209  LLVM_DEBUG(dbgs() << "Marking Block Executable: " << BB->getName() << '\n');
210  BBWorkList.push_back(BB); // Add the block to the work list!
211  return true;
212  }
213 
214  /// TrackValueOfGlobalVariable - Clients can use this method to
215  /// inform the SCCPSolver that it should track loads and stores to the
216  /// specified global variable if it can. This is only legal to call if
217  /// performing Interprocedural SCCP.
218  void TrackValueOfGlobalVariable(GlobalVariable *GV) {
219  // We only track the contents of scalar globals.
220  if (GV->getValueType()->isSingleValueType()) {
221  ValueLatticeElement &IV = TrackedGlobals[GV];
222  if (!isa<UndefValue>(GV->getInitializer()))
223  IV.markConstant(GV->getInitializer());
224  }
225  }
226 
227  /// AddTrackedFunction - If the SCCP solver is supposed to track calls into
228  /// and out of the specified function (which cannot have its address taken),
229  /// this method must be called.
230  void AddTrackedFunction(Function *F) {
231  // Add an entry, F -> undef.
232  if (auto *STy = dyn_cast<StructType>(F->getReturnType())) {
233  MRVFunctionsTracked.insert(F);
234  for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
235  TrackedMultipleRetVals.insert(
236  std::make_pair(std::make_pair(F, i), ValueLatticeElement()));
237  } else if (!F->getReturnType()->isVoidTy())
238  TrackedRetVals.insert(std::make_pair(F, ValueLatticeElement()));
239  }
240 
241  /// AddMustTailCallee - If the SCCP solver finds that this function is called
242  /// from non-removable musttail call site.
243  void AddMustTailCallee(Function *F) {
244  MustTailCallees.insert(F);
245  }
246 
247  /// Returns true if the given function is called from non-removable musttail
248  /// call site.
249  bool isMustTailCallee(Function *F) {
250  return MustTailCallees.count(F);
251  }
252 
253  void AddArgumentTrackedFunction(Function *F) {
254  TrackingIncomingArguments.insert(F);
255  }
256 
257  /// Returns true if the given function is in the solver's set of
258  /// argument-tracked functions.
259  bool isArgumentTrackedFunction(Function *F) {
260  return TrackingIncomingArguments.count(F);
261  }
262 
263  /// Solve - Solve for constants and executable blocks.
264  void Solve();
265 
266  /// ResolvedUndefsIn - While solving the dataflow for a function, we assume
267  /// that branches on undef values cannot reach any of their successors.
268  /// However, this is not a safe assumption. After we solve dataflow, this
269  /// method should be use to handle this. If this returns true, the solver
270  /// should be rerun.
271  bool ResolvedUndefsIn(Function &F);
272 
273  bool isBlockExecutable(BasicBlock *BB) const {
274  return BBExecutable.count(BB);
275  }
276 
277  // isEdgeFeasible - Return true if the control flow edge from the 'From' basic
278  // block to the 'To' basic block is currently feasible.
279  bool isEdgeFeasible(BasicBlock *From, BasicBlock *To) const;
280 
281  std::vector<ValueLatticeElement> getStructLatticeValueFor(Value *V) const {
282  std::vector<ValueLatticeElement> StructValues;
283  auto *STy = dyn_cast<StructType>(V->getType());
284  assert(STy && "getStructLatticeValueFor() can be called only on structs");
285  for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
286  auto I = StructValueState.find(std::make_pair(V, i));
287  assert(I != StructValueState.end() && "Value not in valuemap!");
288  StructValues.push_back(I->second);
289  }
290  return StructValues;
291  }
292 
293  void removeLatticeValueFor(Value *V) { ValueState.erase(V); }
294 
295  const ValueLatticeElement &getLatticeValueFor(Value *V) const {
296  assert(!V->getType()->isStructTy() &&
297  "Should use getStructLatticeValueFor");
299  ValueState.find(V);
300  assert(I != ValueState.end() &&
301  "V not found in ValueState nor Paramstate map!");
302  return I->second;
303  }
304 
305  /// getTrackedRetVals - Get the inferred return value map.
306  const MapVector<Function *, ValueLatticeElement> &getTrackedRetVals() {
307  return TrackedRetVals;
308  }
309 
310  /// getTrackedGlobals - Get and return the set of inferred initializers for
311  /// global variables.
312  const DenseMap<GlobalVariable *, ValueLatticeElement> &getTrackedGlobals() {
313  return TrackedGlobals;
314  }
315 
316  /// getMRVFunctionsTracked - Get the set of functions which return multiple
317  /// values tracked by the pass.
318  const SmallPtrSet<Function *, 16> getMRVFunctionsTracked() {
319  return MRVFunctionsTracked;
320  }
321 
322  /// getMustTailCallees - Get the set of functions which are called
323  /// from non-removable musttail call sites.
324  const SmallPtrSet<Function *, 16> getMustTailCallees() {
325  return MustTailCallees;
326  }
327 
328  /// markOverdefined - Mark the specified value overdefined. This
329  /// works with both scalars and structs.
330  void markOverdefined(Value *V) {
331  if (auto *STy = dyn_cast<StructType>(V->getType()))
332  for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
333  markOverdefined(getStructValueState(V, i), V);
334  else
335  markOverdefined(ValueState[V], V);
336  }
337 
338  // isStructLatticeConstant - Return true if all the lattice values
339  // corresponding to elements of the structure are constants,
340  // false otherwise.
341  bool isStructLatticeConstant(Function *F, StructType *STy) {
342  for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
343  const auto &It = TrackedMultipleRetVals.find(std::make_pair(F, i));
344  assert(It != TrackedMultipleRetVals.end());
345  ValueLatticeElement LV = It->second;
346  if (!isConstant(LV))
347  return false;
348  }
349  return true;
350  }
351 
352  /// Helper to return a Constant if \p LV is either a constant or a constant
353  /// range with a single element.
354  Constant *getConstant(const ValueLatticeElement &LV) const {
355  if (LV.isConstant())
356  return LV.getConstant();
357 
358  if (LV.isConstantRange()) {
359  auto &CR = LV.getConstantRange();
360  if (CR.getSingleElement())
361  return ConstantInt::get(Ctx, *CR.getSingleElement());
362  }
363  return nullptr;
364  }
365 
366 private:
367  ConstantInt *getConstantInt(const ValueLatticeElement &IV) const {
368  return dyn_cast_or_null<ConstantInt>(getConstant(IV));
369  }
370 
371  // pushToWorkList - Helper for markConstant/markOverdefined
372  void pushToWorkList(ValueLatticeElement &IV, Value *V) {
373  if (IV.isOverdefined())
374  return OverdefinedInstWorkList.push_back(V);
375  InstWorkList.push_back(V);
376  }
377 
378  // Helper to push \p V to the worklist, after updating it to \p IV. Also
379  // prints a debug message with the updated value.
380  void pushToWorkListMsg(ValueLatticeElement &IV, Value *V) {
381  LLVM_DEBUG(dbgs() << "updated " << IV << ": " << *V << '\n');
382  pushToWorkList(IV, V);
383  }
384 
385  // markConstant - Make a value be marked as "constant". If the value
386  // is not already a constant, add it to the instruction work list so that
387  // the users of the instruction are updated later.
388  bool markConstant(ValueLatticeElement &IV, Value *V, Constant *C,
389  bool MayIncludeUndef = false) {
390  if (!IV.markConstant(C, MayIncludeUndef))
391  return false;
392  LLVM_DEBUG(dbgs() << "markConstant: " << *C << ": " << *V << '\n');
393  pushToWorkList(IV, V);
394  return true;
395  }
396 
397  bool markConstant(Value *V, Constant *C) {
398  assert(!V->getType()->isStructTy() && "structs should use mergeInValue");
399  return markConstant(ValueState[V], V, C);
400  }
401 
402  // markOverdefined - Make a value be marked as "overdefined". If the
403  // value is not already overdefined, add it to the overdefined instruction
404  // work list so that the users of the instruction are updated later.
405  bool markOverdefined(ValueLatticeElement &IV, Value *V) {
406  if (!IV.markOverdefined()) return false;
407 
408  LLVM_DEBUG(dbgs() << "markOverdefined: ";
409  if (auto *F = dyn_cast<Function>(V)) dbgs()
410  << "Function '" << F->getName() << "'\n";
411  else dbgs() << *V << '\n');
412  // Only instructions go on the work list
413  pushToWorkList(IV, V);
414  return true;
415  }
416 
417  /// Merge \p MergeWithV into \p IV and push \p V to the worklist, if \p IV
418  /// changes.
419  bool mergeInValue(ValueLatticeElement &IV, Value *V,
420  ValueLatticeElement MergeWithV,
422  /*MayIncludeUndef=*/false, /*CheckWiden=*/false}) {
423  if (IV.mergeIn(MergeWithV, Opts)) {
424  pushToWorkList(IV, V);
425  LLVM_DEBUG(dbgs() << "Merged " << MergeWithV << " into " << *V << " : "
426  << IV << "\n");
427  return true;
428  }
429  return false;
430  }
431 
432  bool mergeInValue(Value *V, ValueLatticeElement MergeWithV,
434  /*MayIncludeUndef=*/false, /*CheckWiden=*/false}) {
435  assert(!V->getType()->isStructTy() &&
436  "non-structs should use markConstant");
437  return mergeInValue(ValueState[V], V, MergeWithV, Opts);
438  }
439 
440  /// getValueState - Return the ValueLatticeElement object that corresponds to
441  /// the value. This function handles the case when the value hasn't been seen
442  /// yet by properly seeding constants etc.
443  ValueLatticeElement &getValueState(Value *V) {
444  assert(!V->getType()->isStructTy() && "Should use getStructValueState");
445 
446  auto I = ValueState.insert(std::make_pair(V, ValueLatticeElement()));
447  ValueLatticeElement &LV = I.first->second;
448 
449  if (!I.second)
450  return LV; // Common case, already in the map.
451 
452  if (auto *C = dyn_cast<Constant>(V))
453  LV.markConstant(C); // Constants are constant
454 
455  // All others are unknown by default.
456  return LV;
457  }
458 
459  /// getStructValueState - Return the ValueLatticeElement object that
460  /// corresponds to the value/field pair. This function handles the case when
461  /// the value hasn't been seen yet by properly seeding constants etc.
462  ValueLatticeElement &getStructValueState(Value *V, unsigned i) {
463  assert(V->getType()->isStructTy() && "Should use getValueState");
464  assert(i < cast<StructType>(V->getType())->getNumElements() &&
465  "Invalid element #");
466 
467  auto I = StructValueState.insert(
468  std::make_pair(std::make_pair(V, i), ValueLatticeElement()));
469  ValueLatticeElement &LV = I.first->second;
470 
471  if (!I.second)
472  return LV; // Common case, already in the map.
473 
474  if (auto *C = dyn_cast<Constant>(V)) {
475  Constant *Elt = C->getAggregateElement(i);
476 
477  if (!Elt)
478  LV.markOverdefined(); // Unknown sort of constant.
479  else if (isa<UndefValue>(Elt))
480  ; // Undef values remain unknown.
481  else
482  LV.markConstant(Elt); // Constants are constant.
483  }
484 
485  // All others are underdefined by default.
486  return LV;
487  }
488 
489  /// markEdgeExecutable - Mark a basic block as executable, adding it to the BB
490  /// work list if it is not already executable.
491  bool markEdgeExecutable(BasicBlock *Source, BasicBlock *Dest) {
492  if (!KnownFeasibleEdges.insert(Edge(Source, Dest)).second)
493  return false; // This edge is already known to be executable!
494 
495  if (!MarkBlockExecutable(Dest)) {
496  // If the destination is already executable, we just made an *edge*
497  // feasible that wasn't before. Revisit the PHI nodes in the block
498  // because they have potentially new operands.
499  LLVM_DEBUG(dbgs() << "Marking Edge Executable: " << Source->getName()
500  << " -> " << Dest->getName() << '\n');
501 
502  for (PHINode &PN : Dest->phis())
503  visitPHINode(PN);
504  }
505  return true;
506  }
507 
508  // getFeasibleSuccessors - Return a vector of booleans to indicate which
509  // successors are reachable from a given terminator instruction.
510  void getFeasibleSuccessors(Instruction &TI, SmallVectorImpl<bool> &Succs);
511 
512  // OperandChangedState - This method is invoked on all of the users of an
513  // instruction that was just changed state somehow. Based on this
514  // information, we need to update the specified user of this instruction.
515  void OperandChangedState(Instruction *I) {
516  if (BBExecutable.count(I->getParent())) // Inst is executable?
517  visit(*I);
518  }
519 
520  // Add U as additional user of V.
521  void addAdditionalUser(Value *V, User *U) {
522  auto Iter = AdditionalUsers.insert({V, {}});
523  Iter.first->second.insert(U);
524  }
525 
526  // Mark I's users as changed, including AdditionalUsers.
527  void markUsersAsChanged(Value *I) {
528  // Functions include their arguments in the use-list. Changed function
529  // values mean that the result of the function changed. We only need to
530  // update the call sites with the new function result and do not have to
531  // propagate the call arguments.
532  if (isa<Function>(I)) {
533  for (User *U : I->users()) {
534  if (auto *CB = dyn_cast<CallBase>(U))
535  handleCallResult(*CB);
536  }
537  } else {
538  for (User *U : I->users())
539  if (auto *UI = dyn_cast<Instruction>(U))
540  OperandChangedState(UI);
541  }
542 
543  auto Iter = AdditionalUsers.find(I);
544  if (Iter != AdditionalUsers.end()) {
545  for (User *U : Iter->second)
546  if (auto *UI = dyn_cast<Instruction>(U))
547  OperandChangedState(UI);
548  }
549  }
550  void handleCallOverdefined(CallBase &CB);
551  void handleCallResult(CallBase &CB);
552  void handleCallArguments(CallBase &CB);
553 
554 private:
555  friend class InstVisitor<SCCPSolver>;
556 
557  // visit implementations - Something changed in this instruction. Either an
558  // operand made a transition, or the instruction is newly executable. Change
559  // the value type of I to reflect these changes if appropriate.
560  void visitPHINode(PHINode &I);
561 
562  // Terminators
563 
564  void visitReturnInst(ReturnInst &I);
565  void visitTerminator(Instruction &TI);
566 
567  void visitCastInst(CastInst &I);
568  void visitSelectInst(SelectInst &I);
569  void visitUnaryOperator(Instruction &I);
570  void visitBinaryOperator(Instruction &I);
571  void visitCmpInst(CmpInst &I);
572  void visitExtractValueInst(ExtractValueInst &EVI);
573  void visitInsertValueInst(InsertValueInst &IVI);
574 
575  void visitCatchSwitchInst(CatchSwitchInst &CPI) {
576  markOverdefined(&CPI);
577  visitTerminator(CPI);
578  }
579 
580  // Instructions that cannot be folded away.
581 
582  void visitStoreInst (StoreInst &I);
583  void visitLoadInst (LoadInst &I);
584  void visitGetElementPtrInst(GetElementPtrInst &I);
585 
586  void visitCallInst (CallInst &I) {
587  visitCallBase(I);
588  }
589 
590  void visitInvokeInst (InvokeInst &II) {
591  visitCallBase(II);
592  visitTerminator(II);
593  }
594 
595  void visitCallBrInst (CallBrInst &CBI) {
596  visitCallBase(CBI);
597  visitTerminator(CBI);
598  }
599 
600  void visitCallBase (CallBase &CB);
601  void visitResumeInst (ResumeInst &I) { /*returns void*/ }
602  void visitUnreachableInst(UnreachableInst &I) { /*returns void*/ }
603  void visitFenceInst (FenceInst &I) { /*returns void*/ }
604 
605  void visitInstruction(Instruction &I) {
606  // All the instructions we don't do any special handling for just
607  // go to overdefined.
608  LLVM_DEBUG(dbgs() << "SCCP: Don't know how to handle: " << I << '\n');
609  markOverdefined(&I);
610  }
611 };
612 
613 } // end anonymous namespace
614 
615 // getFeasibleSuccessors - Return a vector of booleans to indicate which
616 // successors are reachable from a given terminator instruction.
617 void SCCPSolver::getFeasibleSuccessors(Instruction &TI,
618  SmallVectorImpl<bool> &Succs) {
619  Succs.resize(TI.getNumSuccessors());
620  if (auto *BI = dyn_cast<BranchInst>(&TI)) {
621  if (BI->isUnconditional()) {
622  Succs[0] = true;
623  return;
624  }
625 
626  ValueLatticeElement BCValue = getValueState(BI->getCondition());
627  ConstantInt *CI = getConstantInt(BCValue);
628  if (!CI) {
629  // Overdefined condition variables, and branches on unfoldable constant
630  // conditions, mean the branch could go either way.
631  if (!BCValue.isUnknownOrUndef())
632  Succs[0] = Succs[1] = true;
633  return;
634  }
635 
636  // Constant condition variables mean the branch can only go a single way.
637  Succs[CI->isZero()] = true;
638  return;
639  }
640 
641  // Unwinding instructions successors are always executable.
642  if (TI.isExceptionalTerminator()) {
643  Succs.assign(TI.getNumSuccessors(), true);
644  return;
645  }
646 
647  if (auto *SI = dyn_cast<SwitchInst>(&TI)) {
648  if (!SI->getNumCases()) {
649  Succs[0] = true;
650  return;
651  }
652  const ValueLatticeElement &SCValue = getValueState(SI->getCondition());
653  if (ConstantInt *CI = getConstantInt(SCValue)) {
654  Succs[SI->findCaseValue(CI)->getSuccessorIndex()] = true;
655  return;
656  }
657 
658  // TODO: Switch on undef is UB. Stop passing false once the rest of LLVM
659  // is ready.
660  if (SCValue.isConstantRange(/*UndefAllowed=*/false)) {
661  const ConstantRange &Range = SCValue.getConstantRange();
662  for (const auto &Case : SI->cases()) {
663  const APInt &CaseValue = Case.getCaseValue()->getValue();
664  if (Range.contains(CaseValue))
665  Succs[Case.getSuccessorIndex()] = true;
666  }
667 
668  // TODO: Determine whether default case is reachable.
669  Succs[SI->case_default()->getSuccessorIndex()] = true;
670  return;
671  }
672 
673  // Overdefined or unknown condition? All destinations are executable!
674  if (!SCValue.isUnknownOrUndef())
675  Succs.assign(TI.getNumSuccessors(), true);
676  return;
677  }
678 
679  // In case of indirect branch and its address is a blockaddress, we mark
680  // the target as executable.
681  if (auto *IBR = dyn_cast<IndirectBrInst>(&TI)) {
682  // Casts are folded by visitCastInst.
683  ValueLatticeElement IBRValue = getValueState(IBR->getAddress());
684  BlockAddress *Addr = dyn_cast_or_null<BlockAddress>(getConstant(IBRValue));
685  if (!Addr) { // Overdefined or unknown condition?
686  // All destinations are executable!
687  if (!IBRValue.isUnknownOrUndef())
688  Succs.assign(TI.getNumSuccessors(), true);
689  return;
690  }
691 
692  BasicBlock* T = Addr->getBasicBlock();
693  assert(Addr->getFunction() == T->getParent() &&
694  "Block address of a different function ?");
695  for (unsigned i = 0; i < IBR->getNumSuccessors(); ++i) {
696  // This is the target.
697  if (IBR->getDestination(i) == T) {
698  Succs[i] = true;
699  return;
700  }
701  }
702 
703  // If we didn't find our destination in the IBR successor list, then we
704  // have undefined behavior. Its ok to assume no successor is executable.
705  return;
706  }
707 
708  // In case of callbr, we pessimistically assume that all successors are
709  // feasible.
710  if (isa<CallBrInst>(&TI)) {
711  Succs.assign(TI.getNumSuccessors(), true);
712  return;
713  }
714 
715  LLVM_DEBUG(dbgs() << "Unknown terminator instruction: " << TI << '\n');
716  llvm_unreachable("SCCP: Don't know how to handle this terminator!");
717 }
718 
719 // isEdgeFeasible - Return true if the control flow edge from the 'From' basic
720 // block to the 'To' basic block is currently feasible.
721 bool SCCPSolver::isEdgeFeasible(BasicBlock *From, BasicBlock *To) const {
722  // Check if we've called markEdgeExecutable on the edge yet. (We could
723  // be more aggressive and try to consider edges which haven't been marked
724  // yet, but there isn't any need.)
725  return KnownFeasibleEdges.count(Edge(From, To));
726 }
727 
728 // visit Implementations - Something changed in this instruction, either an
729 // operand made a transition, or the instruction is newly executable. Change
730 // the value type of I to reflect these changes if appropriate. This method
731 // makes sure to do the following actions:
732 //
733 // 1. If a phi node merges two constants in, and has conflicting value coming
734 // from different branches, or if the PHI node merges in an overdefined
735 // value, then the PHI node becomes overdefined.
736 // 2. If a phi node merges only constants in, and they all agree on value, the
737 // PHI node becomes a constant value equal to that.
738 // 3. If V <- x (op) y && isConstant(x) && isConstant(y) V = Constant
739 // 4. If V <- x (op) y && (isOverdefined(x) || isOverdefined(y)) V = Overdefined
740 // 5. If V <- MEM or V <- CALL or V <- (unknown) then V = Overdefined
741 // 6. If a conditional branch has a value that is constant, make the selected
742 // destination executable
743 // 7. If a conditional branch has a value that is overdefined, make all
744 // successors executable.
745 void SCCPSolver::visitPHINode(PHINode &PN) {
746  // If this PN returns a struct, just mark the result overdefined.
747  // TODO: We could do a lot better than this if code actually uses this.
748  if (PN.getType()->isStructTy())
749  return (void)markOverdefined(&PN);
750 
751  if (getValueState(&PN).isOverdefined())
752  return; // Quick exit
753 
754  // Super-extra-high-degree PHI nodes are unlikely to ever be marked constant,
755  // and slow us down a lot. Just mark them overdefined.
756  if (PN.getNumIncomingValues() > 64)
757  return (void)markOverdefined(&PN);
758 
759  unsigned NumActiveIncoming = 0;
760 
761  // Look at all of the executable operands of the PHI node. If any of them
762  // are overdefined, the PHI becomes overdefined as well. If they are all
763  // constant, and they agree with each other, the PHI becomes the identical
764  // constant. If they are constant and don't agree, the PHI is a constant
765  // range. If there are no executable operands, the PHI remains unknown.
766  ValueLatticeElement PhiState = getValueState(&PN);
767  for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) {
768  if (!isEdgeFeasible(PN.getIncomingBlock(i), PN.getParent()))
769  continue;
770 
771  ValueLatticeElement IV = getValueState(PN.getIncomingValue(i));
772  PhiState.mergeIn(IV);
773  NumActiveIncoming++;
774  if (PhiState.isOverdefined())
775  break;
776  }
777 
778  // We allow up to 1 range extension per active incoming value and one
779  // additional extension. Note that we manually adjust the number of range
780  // extensions to match the number of active incoming values. This helps to
781  // limit multiple extensions caused by the same incoming value, if other
782  // incoming values are equal.
783  mergeInValue(&PN, PhiState,
784  ValueLatticeElement::MergeOptions().setMaxWidenSteps(
785  NumActiveIncoming + 1));
786  ValueLatticeElement &PhiStateRef = getValueState(&PN);
787  PhiStateRef.setNumRangeExtensions(
788  std::max(NumActiveIncoming, PhiStateRef.getNumRangeExtensions()));
789 }
790 
791 void SCCPSolver::visitReturnInst(ReturnInst &I) {
792  if (I.getNumOperands() == 0) return; // ret void
793 
794  Function *F = I.getParent()->getParent();
795  Value *ResultOp = I.getOperand(0);
796 
797  // If we are tracking the return value of this function, merge it in.
798  if (!TrackedRetVals.empty() && !ResultOp->getType()->isStructTy()) {
799  auto TFRVI = TrackedRetVals.find(F);
800  if (TFRVI != TrackedRetVals.end()) {
801  mergeInValue(TFRVI->second, F, getValueState(ResultOp));
802  return;
803  }
804  }
805 
806  // Handle functions that return multiple values.
807  if (!TrackedMultipleRetVals.empty()) {
808  if (auto *STy = dyn_cast<StructType>(ResultOp->getType()))
809  if (MRVFunctionsTracked.count(F))
810  for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
811  mergeInValue(TrackedMultipleRetVals[std::make_pair(F, i)], F,
812  getStructValueState(ResultOp, i));
813  }
814 }
815 
816 void SCCPSolver::visitTerminator(Instruction &TI) {
817  SmallVector<bool, 16> SuccFeasible;
818  getFeasibleSuccessors(TI, SuccFeasible);
819 
820  BasicBlock *BB = TI.getParent();
821 
822  // Mark all feasible successors executable.
823  for (unsigned i = 0, e = SuccFeasible.size(); i != e; ++i)
824  if (SuccFeasible[i])
825  markEdgeExecutable(BB, TI.getSuccessor(i));
826 }
827 
828 void SCCPSolver::visitCastInst(CastInst &I) {
829  // ResolvedUndefsIn might mark I as overdefined. Bail out, even if we would
830  // discover a concrete value later.
831  if (ValueState[&I].isOverdefined())
832  return;
833 
834  ValueLatticeElement OpSt = getValueState(I.getOperand(0));
835  if (Constant *OpC = getConstant(OpSt)) {
836  // Fold the constant as we build.
838  if (isa<UndefValue>(C))
839  return;
840  // Propagate constant value
841  markConstant(&I, C);
842  } else if (OpSt.isConstantRange() && I.getDestTy()->isIntegerTy()) {
843  auto &LV = getValueState(&I);
844  ConstantRange OpRange = OpSt.getConstantRange();
845  Type *DestTy = I.getDestTy();
846  // Vectors where all elements have the same known constant range are treated
847  // as a single constant range in the lattice. When bitcasting such vectors,
848  // there is a mis-match between the width of the lattice value (single
849  // constant range) and the original operands (vector). Go to overdefined in
850  // that case.
851  if (I.getOpcode() == Instruction::BitCast &&
852  I.getOperand(0)->getType()->isVectorTy() &&
853  OpRange.getBitWidth() < DL.getTypeSizeInBits(DestTy))
854  return (void)markOverdefined(&I);
855 
856  ConstantRange Res =
857  OpRange.castOp(I.getOpcode(), DL.getTypeSizeInBits(DestTy));
858  mergeInValue(LV, &I, ValueLatticeElement::getRange(Res));
859  } else if (!OpSt.isUnknownOrUndef())
860  markOverdefined(&I);
861 }
862 
863 void SCCPSolver::visitExtractValueInst(ExtractValueInst &EVI) {
864  // If this returns a struct, mark all elements over defined, we don't track
865  // structs in structs.
866  if (EVI.getType()->isStructTy())
867  return (void)markOverdefined(&EVI);
868 
869  // ResolvedUndefsIn might mark I as overdefined. Bail out, even if we would
870  // discover a concrete value later.
871  if (ValueState[&EVI].isOverdefined())
872  return (void)markOverdefined(&EVI);
873 
874  // If this is extracting from more than one level of struct, we don't know.
875  if (EVI.getNumIndices() != 1)
876  return (void)markOverdefined(&EVI);
877 
878  Value *AggVal = EVI.getAggregateOperand();
879  if (AggVal->getType()->isStructTy()) {
880  unsigned i = *EVI.idx_begin();
881  ValueLatticeElement EltVal = getStructValueState(AggVal, i);
882  mergeInValue(getValueState(&EVI), &EVI, EltVal);
883  } else {
884  // Otherwise, must be extracting from an array.
885  return (void)markOverdefined(&EVI);
886  }
887 }
888 
889 void SCCPSolver::visitInsertValueInst(InsertValueInst &IVI) {
890  auto *STy = dyn_cast<StructType>(IVI.getType());
891  if (!STy)
892  return (void)markOverdefined(&IVI);
893 
894  // ResolvedUndefsIn might mark I as overdefined. Bail out, even if we would
895  // discover a concrete value later.
896  if (isOverdefined(ValueState[&IVI]))
897  return (void)markOverdefined(&IVI);
898 
899  // If this has more than one index, we can't handle it, drive all results to
900  // undef.
901  if (IVI.getNumIndices() != 1)
902  return (void)markOverdefined(&IVI);
903 
904  Value *Aggr = IVI.getAggregateOperand();
905  unsigned Idx = *IVI.idx_begin();
906 
907  // Compute the result based on what we're inserting.
908  for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
909  // This passes through all values that aren't the inserted element.
910  if (i != Idx) {
911  ValueLatticeElement EltVal = getStructValueState(Aggr, i);
912  mergeInValue(getStructValueState(&IVI, i), &IVI, EltVal);
913  continue;
914  }
915 
916  Value *Val = IVI.getInsertedValueOperand();
917  if (Val->getType()->isStructTy())
918  // We don't track structs in structs.
919  markOverdefined(getStructValueState(&IVI, i), &IVI);
920  else {
921  ValueLatticeElement InVal = getValueState(Val);
922  mergeInValue(getStructValueState(&IVI, i), &IVI, InVal);
923  }
924  }
925 }
926 
927 void SCCPSolver::visitSelectInst(SelectInst &I) {
928  // If this select returns a struct, just mark the result overdefined.
929  // TODO: We could do a lot better than this if code actually uses this.
930  if (I.getType()->isStructTy())
931  return (void)markOverdefined(&I);
932 
933  // ResolvedUndefsIn might mark I as overdefined. Bail out, even if we would
934  // discover a concrete value later.
935  if (ValueState[&I].isOverdefined())
936  return (void)markOverdefined(&I);
937 
938  ValueLatticeElement CondValue = getValueState(I.getCondition());
939  if (CondValue.isUnknownOrUndef())
940  return;
941 
942  if (ConstantInt *CondCB = getConstantInt(CondValue)) {
943  Value *OpVal = CondCB->isZero() ? I.getFalseValue() : I.getTrueValue();
944  mergeInValue(&I, getValueState(OpVal));
945  return;
946  }
947 
948  // Otherwise, the condition is overdefined or a constant we can't evaluate.
949  // See if we can produce something better than overdefined based on the T/F
950  // value.
951  ValueLatticeElement TVal = getValueState(I.getTrueValue());
952  ValueLatticeElement FVal = getValueState(I.getFalseValue());
953 
954  bool Changed = ValueState[&I].mergeIn(TVal);
955  Changed |= ValueState[&I].mergeIn(FVal);
956  if (Changed)
957  pushToWorkListMsg(ValueState[&I], &I);
958 }
959 
960 // Handle Unary Operators.
961 void SCCPSolver::visitUnaryOperator(Instruction &I) {
962  ValueLatticeElement V0State = getValueState(I.getOperand(0));
963 
964  ValueLatticeElement &IV = ValueState[&I];
965  // ResolvedUndefsIn might mark I as overdefined. Bail out, even if we would
966  // discover a concrete value later.
967  if (isOverdefined(IV))
968  return (void)markOverdefined(&I);
969 
970  if (isConstant(V0State)) {
971  Constant *C = ConstantExpr::get(I.getOpcode(), getConstant(V0State));
972 
973  // op Y -> undef.
974  if (isa<UndefValue>(C))
975  return;
976  return (void)markConstant(IV, &I, C);
977  }
978 
979  // If something is undef, wait for it to resolve.
980  if (!isOverdefined(V0State))
981  return;
982 
983  markOverdefined(&I);
984 }
985 
986 // Handle Binary Operators.
987 void SCCPSolver::visitBinaryOperator(Instruction &I) {
988  ValueLatticeElement V1State = getValueState(I.getOperand(0));
989  ValueLatticeElement V2State = getValueState(I.getOperand(1));
990 
991  ValueLatticeElement &IV = ValueState[&I];
992  if (IV.isOverdefined())
993  return;
994 
995  // If something is undef, wait for it to resolve.
996  if (V1State.isUnknownOrUndef() || V2State.isUnknownOrUndef())
997  return;
998 
999  if (V1State.isOverdefined() && V2State.isOverdefined())
1000  return (void)markOverdefined(&I);
1001 
1002  // If either of the operands is a constant, try to fold it to a constant.
1003  // TODO: Use information from notconstant better.
1004  if ((V1State.isConstant() || V2State.isConstant())) {
1005  Value *V1 = isConstant(V1State) ? getConstant(V1State) : I.getOperand(0);
1006  Value *V2 = isConstant(V2State) ? getConstant(V2State) : I.getOperand(1);
1007  Value *R = SimplifyBinOp(I.getOpcode(), V1, V2, SimplifyQuery(DL));
1008  auto *C = dyn_cast_or_null<Constant>(R);
1009  if (C) {
1010  // X op Y -> undef.
1011  if (isa<UndefValue>(C))
1012  return;
1013  // Conservatively assume that the result may be based on operands that may
1014  // be undef. Note that we use mergeInValue to combine the constant with
1015  // the existing lattice value for I, as different constants might be found
1016  // after one of the operands go to overdefined, e.g. due to one operand
1017  // being a special floating value.
1018  ValueLatticeElement NewV;
1019  NewV.markConstant(C, /*MayIncludeUndef=*/true);
1020  return (void)mergeInValue(&I, NewV);
1021  }
1022  }
1023 
1024  // Only use ranges for binary operators on integers.
1025  if (!I.getType()->isIntegerTy())
1026  return markOverdefined(&I);
1027 
1028  // Try to simplify to a constant range.
1029  ConstantRange A = ConstantRange::getFull(I.getType()->getScalarSizeInBits());
1030  ConstantRange B = ConstantRange::getFull(I.getType()->getScalarSizeInBits());
1031  if (V1State.isConstantRange())
1032  A = V1State.getConstantRange();
1033  if (V2State.isConstantRange())
1034  B = V2State.getConstantRange();
1035 
1036  ConstantRange R = A.binaryOp(cast<BinaryOperator>(&I)->getOpcode(), B);
1037  mergeInValue(&I, ValueLatticeElement::getRange(R));
1038 
1039  // TODO: Currently we do not exploit special values that produce something
1040  // better than overdefined with an overdefined operand for vector or floating
1041  // point types, like and <4 x i32> overdefined, zeroinitializer.
1042 }
1043 
1044 // Handle ICmpInst instruction.
1045 void SCCPSolver::visitCmpInst(CmpInst &I) {
1046  // Do not cache this lookup, getValueState calls later in the function might
1047  // invalidate the reference.
1048  if (isOverdefined(ValueState[&I]))
1049  return (void)markOverdefined(&I);
1050 
1051  Value *Op1 = I.getOperand(0);
1052  Value *Op2 = I.getOperand(1);
1053 
1054  // For parameters, use ParamState which includes constant range info if
1055  // available.
1056  auto V1State = getValueState(Op1);
1057  auto V2State = getValueState(Op2);
1058 
1059  Constant *C = V1State.getCompare(I.getPredicate(), I.getType(), V2State);
1060  if (C) {
1061  if (isa<UndefValue>(C))
1062  return;
1064  CV.markConstant(C);
1065  mergeInValue(&I, CV);
1066  return;
1067  }
1068 
1069  // If operands are still unknown, wait for it to resolve.
1070  if ((V1State.isUnknownOrUndef() || V2State.isUnknownOrUndef()) &&
1071  !isConstant(ValueState[&I]))
1072  return;
1073 
1074  markOverdefined(&I);
1075 }
1076 
1077 // Handle getelementptr instructions. If all operands are constants then we
1078 // can turn this into a getelementptr ConstantExpr.
1079 void SCCPSolver::visitGetElementPtrInst(GetElementPtrInst &I) {
1080  if (isOverdefined(ValueState[&I]))
1081  return (void)markOverdefined(&I);
1082 
1084  Operands.reserve(I.getNumOperands());
1085 
1086  for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) {
1087  ValueLatticeElement State = getValueState(I.getOperand(i));
1088  if (State.isUnknownOrUndef())
1089  return; // Operands are not resolved yet.
1090 
1091  if (isOverdefined(State))
1092  return (void)markOverdefined(&I);
1093 
1094  if (Constant *C = getConstant(State)) {
1095  Operands.push_back(C);
1096  continue;
1097  }
1098 
1099  return (void)markOverdefined(&I);
1100  }
1101 
1102  Constant *Ptr = Operands[0];
1103  auto Indices = makeArrayRef(Operands.begin() + 1, Operands.end());
1104  Constant *C =
1105  ConstantExpr::getGetElementPtr(I.getSourceElementType(), Ptr, Indices);
1106  if (isa<UndefValue>(C))
1107  return;
1108  markConstant(&I, C);
1109 }
1110 
1111 void SCCPSolver::visitStoreInst(StoreInst &SI) {
1112  // If this store is of a struct, ignore it.
1113  if (SI.getOperand(0)->getType()->isStructTy())
1114  return;
1115 
1116  if (TrackedGlobals.empty() || !isa<GlobalVariable>(SI.getOperand(1)))
1117  return;
1118 
1119  GlobalVariable *GV = cast<GlobalVariable>(SI.getOperand(1));
1120  auto I = TrackedGlobals.find(GV);
1121  if (I == TrackedGlobals.end())
1122  return;
1123 
1124  // Get the value we are storing into the global, then merge it.
1125  mergeInValue(I->second, GV, getValueState(SI.getOperand(0)),
1127  if (I->second.isOverdefined())
1128  TrackedGlobals.erase(I); // No need to keep tracking this!
1129 }
1130 
1132  if (MDNode *Ranges = I->getMetadata(LLVMContext::MD_range))
1133  if (I->getType()->isIntegerTy())
1135  getConstantRangeFromMetadata(*Ranges));
1136  if (I->hasMetadata(LLVMContext::MD_nonnull))
1138  ConstantPointerNull::get(cast<PointerType>(I->getType())));
1140 }
1141 
1142 // Handle load instructions. If the operand is a constant pointer to a constant
1143 // global, we can replace the load with the loaded constant value!
1144 void SCCPSolver::visitLoadInst(LoadInst &I) {
1145  // If this load is of a struct or the load is volatile, just mark the result
1146  // as overdefined.
1147  if (I.getType()->isStructTy() || I.isVolatile())
1148  return (void)markOverdefined(&I);
1149 
1150  // ResolvedUndefsIn might mark I as overdefined. Bail out, even if we would
1151  // discover a concrete value later.
1152  if (ValueState[&I].isOverdefined())
1153  return (void)markOverdefined(&I);
1154 
1155  ValueLatticeElement PtrVal = getValueState(I.getOperand(0));
1156  if (PtrVal.isUnknownOrUndef())
1157  return; // The pointer is not resolved yet!
1158 
1159  ValueLatticeElement &IV = ValueState[&I];
1160 
1161  if (isConstant(PtrVal)) {
1162  Constant *Ptr = getConstant(PtrVal);
1163 
1164  // load null is undefined.
1165  if (isa<ConstantPointerNull>(Ptr)) {
1167  return (void)markOverdefined(IV, &I);
1168  else
1169  return;
1170  }
1171 
1172  // Transform load (constant global) into the value loaded.
1173  if (auto *GV = dyn_cast<GlobalVariable>(Ptr)) {
1174  if (!TrackedGlobals.empty()) {
1175  // If we are tracking this global, merge in the known value for it.
1176  auto It = TrackedGlobals.find(GV);
1177  if (It != TrackedGlobals.end()) {
1178  mergeInValue(IV, &I, It->second, getMaxWidenStepsOpts());
1179  return;
1180  }
1181  }
1182  }
1183 
1184  // Transform load from a constant into a constant if possible.
1185  if (Constant *C = ConstantFoldLoadFromConstPtr(Ptr, I.getType(), DL)) {
1186  if (isa<UndefValue>(C))
1187  return;
1188  return (void)markConstant(IV, &I, C);
1189  }
1190  }
1191 
1192  // Fall back to metadata.
1193  mergeInValue(&I, getValueFromMetadata(&I));
1194 }
1195 
1196 void SCCPSolver::visitCallBase(CallBase &CB) {
1197  handleCallResult(CB);
1198  handleCallArguments(CB);
1199 }
1200 
1201 void SCCPSolver::handleCallOverdefined(CallBase &CB) {
1202  Function *F = CB.getCalledFunction();
1203 
1204  // Void return and not tracking callee, just bail.
1205  if (CB.getType()->isVoidTy())
1206  return;
1207 
1208  // Always mark struct return as overdefined.
1209  if (CB.getType()->isStructTy())
1210  return (void)markOverdefined(&CB);
1211 
1212  // Otherwise, if we have a single return value case, and if the function is
1213  // a declaration, maybe we can constant fold it.
1214  if (F && F->isDeclaration() && canConstantFoldCallTo(&CB, F)) {
1216  for (auto AI = CB.arg_begin(), E = CB.arg_end(); AI != E; ++AI) {
1217  if (AI->get()->getType()->isStructTy())
1218  return markOverdefined(&CB); // Can't handle struct args.
1219  ValueLatticeElement State = getValueState(*AI);
1220 
1221  if (State.isUnknownOrUndef())
1222  return; // Operands are not resolved yet.
1223  if (isOverdefined(State))
1224  return (void)markOverdefined(&CB);
1225  assert(isConstant(State) && "Unknown state!");
1226  Operands.push_back(getConstant(State));
1227  }
1228 
1229  if (isOverdefined(getValueState(&CB)))
1230  return (void)markOverdefined(&CB);
1231 
1232  // If we can constant fold this, mark the result of the call as a
1233  // constant.
1234  if (Constant *C = ConstantFoldCall(&CB, F, Operands, &GetTLI(*F))) {
1235  // call -> undef.
1236  if (isa<UndefValue>(C))
1237  return;
1238  return (void)markConstant(&CB, C);
1239  }
1240  }
1241 
1242  // Fall back to metadata.
1243  mergeInValue(&CB, getValueFromMetadata(&CB));
1244 }
1245 
1246 void SCCPSolver::handleCallArguments(CallBase &CB) {
1247  Function *F = CB.getCalledFunction();
1248  // If this is a local function that doesn't have its address taken, mark its
1249  // entry block executable and merge in the actual arguments to the call into
1250  // the formal arguments of the function.
1251  if (!TrackingIncomingArguments.empty() &&
1252  TrackingIncomingArguments.count(F)) {
1253  MarkBlockExecutable(&F->front());
1254 
1255  // Propagate information from this call site into the callee.
1256  auto CAI = CB.arg_begin();
1257  for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end(); AI != E;
1258  ++AI, ++CAI) {
1259  // If this argument is byval, and if the function is not readonly, there
1260  // will be an implicit copy formed of the input aggregate.
1261  if (AI->hasByValAttr() && !F->onlyReadsMemory()) {
1262  markOverdefined(&*AI);
1263  continue;
1264  }
1265 
1266  if (auto *STy = dyn_cast<StructType>(AI->getType())) {
1267  for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
1268  ValueLatticeElement CallArg = getStructValueState(*CAI, i);
1269  mergeInValue(getStructValueState(&*AI, i), &*AI, CallArg,
1271  }
1272  } else
1273  mergeInValue(&*AI, getValueState(*CAI), getMaxWidenStepsOpts());
1274  }
1275  }
1276 }
1277 
1278 void SCCPSolver::handleCallResult(CallBase &CB) {
1279  Function *F = CB.getCalledFunction();
1280 
1281  if (auto *II = dyn_cast<IntrinsicInst>(&CB)) {
1282  if (II->getIntrinsicID() == Intrinsic::ssa_copy) {
1283  if (ValueState[&CB].isOverdefined())
1284  return;
1285 
1286  Value *CopyOf = CB.getOperand(0);
1287  ValueLatticeElement CopyOfVal = getValueState(CopyOf);
1288  auto *PI = getPredicateInfoFor(&CB);
1289  assert(PI && "Missing predicate info for ssa.copy");
1290 
1291  const Optional<PredicateConstraint> &Constraint = PI->getConstraint();
1292  if (!Constraint) {
1293  mergeInValue(ValueState[&CB], &CB, CopyOfVal);
1294  return;
1295  }
1296 
1297  CmpInst::Predicate Pred = Constraint->Predicate;
1298  Value *OtherOp = Constraint->OtherOp;
1299 
1300  // Wait until OtherOp is resolved.
1301  if (getValueState(OtherOp).isUnknown()) {
1302  addAdditionalUser(OtherOp, &CB);
1303  return;
1304  }
1305 
1306  // TODO: Actually filp MayIncludeUndef for the created range to false,
1307  // once most places in the optimizer respect the branches on
1308  // undef/poison are UB rule. The reason why the new range cannot be
1309  // undef is as follows below:
1310  // The new range is based on a branch condition. That guarantees that
1311  // neither of the compare operands can be undef in the branch targets,
1312  // unless we have conditions that are always true/false (e.g. icmp ule
1313  // i32, %a, i32_max). For the latter overdefined/empty range will be
1314  // inferred, but the branch will get folded accordingly anyways.
1315  bool MayIncludeUndef = !isa<PredicateAssume>(PI);
1316 
1317  ValueLatticeElement CondVal = getValueState(OtherOp);
1318  ValueLatticeElement &IV = ValueState[&CB];
1319  if (CondVal.isConstantRange() || CopyOfVal.isConstantRange()) {
1320  auto ImposedCR =
1321  ConstantRange::getFull(DL.getTypeSizeInBits(CopyOf->getType()));
1322 
1323  // Get the range imposed by the condition.
1324  if (CondVal.isConstantRange())
1326  Pred, CondVal.getConstantRange());
1327 
1328  // Combine range info for the original value with the new range from the
1329  // condition.
1330  auto CopyOfCR = CopyOfVal.isConstantRange()
1331  ? CopyOfVal.getConstantRange()
1332  : ConstantRange::getFull(
1333  DL.getTypeSizeInBits(CopyOf->getType()));
1334  auto NewCR = ImposedCR.intersectWith(CopyOfCR);
1335  // If the existing information is != x, do not use the information from
1336  // a chained predicate, as the != x information is more likely to be
1337  // helpful in practice.
1338  if (!CopyOfCR.contains(NewCR) && CopyOfCR.getSingleMissingElement())
1339  NewCR = CopyOfCR;
1340 
1341  addAdditionalUser(OtherOp, &CB);
1342  mergeInValue(
1343  IV, &CB,
1344  ValueLatticeElement::getRange(NewCR, MayIncludeUndef));
1345  return;
1346  } else if (Pred == CmpInst::ICMP_EQ && CondVal.isConstant()) {
1347  // For non-integer values or integer constant expressions, only
1348  // propagate equal constants.
1349  addAdditionalUser(OtherOp, &CB);
1350  mergeInValue(IV, &CB, CondVal);
1351  return;
1352  } else if (Pred == CmpInst::ICMP_NE && CondVal.isConstant() &&
1353  !MayIncludeUndef) {
1354  // Propagate inequalities.
1355  addAdditionalUser(OtherOp, &CB);
1356  mergeInValue(IV, &CB,
1357  ValueLatticeElement::getNot(CondVal.getConstant()));
1358  return;
1359  }
1360 
1361  return (void)mergeInValue(IV, &CB, CopyOfVal);
1362  }
1363 
1364  if (ConstantRange::isIntrinsicSupported(II->getIntrinsicID())) {
1365  // Compute result range for intrinsics supported by ConstantRange.
1366  // Do this even if we don't know a range for all operands, as we may
1367  // still know something about the result range, e.g. of abs(x).
1369  for (Value *Op : II->args()) {
1370  const ValueLatticeElement &State = getValueState(Op);
1371  if (State.isConstantRange())
1372  OpRanges.push_back(State.getConstantRange());
1373  else
1374  OpRanges.push_back(
1375  ConstantRange::getFull(Op->getType()->getScalarSizeInBits()));
1376  }
1377 
1378  ConstantRange Result =
1379  ConstantRange::intrinsic(II->getIntrinsicID(), OpRanges);
1380  return (void)mergeInValue(II, ValueLatticeElement::getRange(Result));
1381  }
1382  }
1383 
1384  // The common case is that we aren't tracking the callee, either because we
1385  // are not doing interprocedural analysis or the callee is indirect, or is
1386  // external. Handle these cases first.
1387  if (!F || F->isDeclaration())
1388  return handleCallOverdefined(CB);
1389 
1390  // If this is a single/zero retval case, see if we're tracking the function.
1391  if (auto *STy = dyn_cast<StructType>(F->getReturnType())) {
1392  if (!MRVFunctionsTracked.count(F))
1393  return handleCallOverdefined(CB); // Not tracking this callee.
1394 
1395  // If we are tracking this callee, propagate the result of the function
1396  // into this call site.
1397  for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
1398  mergeInValue(getStructValueState(&CB, i), &CB,
1399  TrackedMultipleRetVals[std::make_pair(F, i)],
1401  } else {
1402  auto TFRVI = TrackedRetVals.find(F);
1403  if (TFRVI == TrackedRetVals.end())
1404  return handleCallOverdefined(CB); // Not tracking this callee.
1405 
1406  // If so, propagate the return value of the callee into this call result.
1407  mergeInValue(&CB, TFRVI->second, getMaxWidenStepsOpts());
1408  }
1409 }
1410 
1411 void SCCPSolver::Solve() {
1412  // Process the work lists until they are empty!
1413  while (!BBWorkList.empty() || !InstWorkList.empty() ||
1414  !OverdefinedInstWorkList.empty()) {
1415  // Process the overdefined instruction's work list first, which drives other
1416  // things to overdefined more quickly.
1417  while (!OverdefinedInstWorkList.empty()) {
1418  Value *I = OverdefinedInstWorkList.pop_back_val();
1419 
1420  LLVM_DEBUG(dbgs() << "\nPopped off OI-WL: " << *I << '\n');
1421 
1422  // "I" got into the work list because it either made the transition from
1423  // bottom to constant, or to overdefined.
1424  //
1425  // Anything on this worklist that is overdefined need not be visited
1426  // since all of its users will have already been marked as overdefined
1427  // Update all of the users of this instruction's value.
1428  //
1429  markUsersAsChanged(I);
1430  }
1431 
1432  // Process the instruction work list.
1433  while (!InstWorkList.empty()) {
1434  Value *I = InstWorkList.pop_back_val();
1435 
1436  LLVM_DEBUG(dbgs() << "\nPopped off I-WL: " << *I << '\n');
1437 
1438  // "I" got into the work list because it made the transition from undef to
1439  // constant.
1440  //
1441  // Anything on this worklist that is overdefined need not be visited
1442  // since all of its users will have already been marked as overdefined.
1443  // Update all of the users of this instruction's value.
1444  //
1445  if (I->getType()->isStructTy() || !getValueState(I).isOverdefined())
1446  markUsersAsChanged(I);
1447  }
1448 
1449  // Process the basic block work list.
1450  while (!BBWorkList.empty()) {
1451  BasicBlock *BB = BBWorkList.back();
1452  BBWorkList.pop_back();
1453 
1454  LLVM_DEBUG(dbgs() << "\nPopped off BBWL: " << *BB << '\n');
1455 
1456  // Notify all instructions in this basic block that they are newly
1457  // executable.
1458  visit(BB);
1459  }
1460  }
1461 }
1462 
1463 /// ResolvedUndefsIn - While solving the dataflow for a function, we assume
1464 /// that branches on undef values cannot reach any of their successors.
1465 /// However, this is not a safe assumption. After we solve dataflow, this
1466 /// method should be use to handle this. If this returns true, the solver
1467 /// should be rerun.
1468 ///
1469 /// This method handles this by finding an unresolved branch and marking it one
1470 /// of the edges from the block as being feasible, even though the condition
1471 /// doesn't say it would otherwise be. This allows SCCP to find the rest of the
1472 /// CFG and only slightly pessimizes the analysis results (by marking one,
1473 /// potentially infeasible, edge feasible). This cannot usefully modify the
1474 /// constraints on the condition of the branch, as that would impact other users
1475 /// of the value.
1476 ///
1477 /// This scan also checks for values that use undefs. It conservatively marks
1478 /// them as overdefined.
1479 bool SCCPSolver::ResolvedUndefsIn(Function &F) {
1480  bool MadeChange = false;
1481  for (BasicBlock &BB : F) {
1482  if (!BBExecutable.count(&BB))
1483  continue;
1484 
1485  for (Instruction &I : BB) {
1486  // Look for instructions which produce undef values.
1487  if (I.getType()->isVoidTy()) continue;
1488 
1489  if (auto *STy = dyn_cast<StructType>(I.getType())) {
1490  // Only a few things that can be structs matter for undef.
1491 
1492  // Tracked calls must never be marked overdefined in ResolvedUndefsIn.
1493  if (auto *CB = dyn_cast<CallBase>(&I))
1494  if (Function *F = CB->getCalledFunction())
1495  if (MRVFunctionsTracked.count(F))
1496  continue;
1497 
1498  // extractvalue and insertvalue don't need to be marked; they are
1499  // tracked as precisely as their operands.
1500  if (isa<ExtractValueInst>(I) || isa<InsertValueInst>(I))
1501  continue;
1502  // Send the results of everything else to overdefined. We could be
1503  // more precise than this but it isn't worth bothering.
1504  for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
1505  ValueLatticeElement &LV = getStructValueState(&I, i);
1506  if (LV.isUnknownOrUndef()) {
1507  markOverdefined(LV, &I);
1508  MadeChange = true;
1509  }
1510  }
1511  continue;
1512  }
1513 
1514  ValueLatticeElement &LV = getValueState(&I);
1515  if (!LV.isUnknownOrUndef())
1516  continue;
1517 
1518  // There are two reasons a call can have an undef result
1519  // 1. It could be tracked.
1520  // 2. It could be constant-foldable.
1521  // Because of the way we solve return values, tracked calls must
1522  // never be marked overdefined in ResolvedUndefsIn.
1523  if (auto *CB = dyn_cast<CallBase>(&I))
1524  if (Function *F = CB->getCalledFunction())
1525  if (TrackedRetVals.count(F))
1526  continue;
1527 
1528  if (isa<LoadInst>(I)) {
1529  // A load here means one of two things: a load of undef from a global,
1530  // a load from an unknown pointer. Either way, having it return undef
1531  // is okay.
1532  continue;
1533  }
1534 
1535  markOverdefined(&I);
1536  MadeChange = true;
1537  }
1538 
1539  // Check to see if we have a branch or switch on an undefined value. If so
1540  // we force the branch to go one way or the other to make the successor
1541  // values live. It doesn't really matter which way we force it.
1542  Instruction *TI = BB.getTerminator();
1543  if (auto *BI = dyn_cast<BranchInst>(TI)) {
1544  if (!BI->isConditional()) continue;
1545  if (!getValueState(BI->getCondition()).isUnknownOrUndef())
1546  continue;
1547 
1548  // If the input to SCCP is actually branch on undef, fix the undef to
1549  // false.
1550  if (isa<UndefValue>(BI->getCondition())) {
1551  BI->setCondition(ConstantInt::getFalse(BI->getContext()));
1552  markEdgeExecutable(&BB, TI->getSuccessor(1));
1553  MadeChange = true;
1554  continue;
1555  }
1556 
1557  // Otherwise, it is a branch on a symbolic value which is currently
1558  // considered to be undef. Make sure some edge is executable, so a
1559  // branch on "undef" always flows somewhere.
1560  // FIXME: Distinguish between dead code and an LLVM "undef" value.
1561  BasicBlock *DefaultSuccessor = TI->getSuccessor(1);
1562  if (markEdgeExecutable(&BB, DefaultSuccessor))
1563  MadeChange = true;
1564 
1565  continue;
1566  }
1567 
1568  if (auto *IBR = dyn_cast<IndirectBrInst>(TI)) {
1569  // Indirect branch with no successor ?. Its ok to assume it branches
1570  // to no target.
1571  if (IBR->getNumSuccessors() < 1)
1572  continue;
1573 
1574  if (!getValueState(IBR->getAddress()).isUnknownOrUndef())
1575  continue;
1576 
1577  // If the input to SCCP is actually branch on undef, fix the undef to
1578  // the first successor of the indirect branch.
1579  if (isa<UndefValue>(IBR->getAddress())) {
1580  IBR->setAddress(BlockAddress::get(IBR->getSuccessor(0)));
1581  markEdgeExecutable(&BB, IBR->getSuccessor(0));
1582  MadeChange = true;
1583  continue;
1584  }
1585 
1586  // Otherwise, it is a branch on a symbolic value which is currently
1587  // considered to be undef. Make sure some edge is executable, so a
1588  // branch on "undef" always flows somewhere.
1589  // FIXME: IndirectBr on "undef" doesn't actually need to go anywhere:
1590  // we can assume the branch has undefined behavior instead.
1591  BasicBlock *DefaultSuccessor = IBR->getSuccessor(0);
1592  if (markEdgeExecutable(&BB, DefaultSuccessor))
1593  MadeChange = true;
1594 
1595  continue;
1596  }
1597 
1598  if (auto *SI = dyn_cast<SwitchInst>(TI)) {
1599  if (!SI->getNumCases() ||
1600  !getValueState(SI->getCondition()).isUnknownOrUndef())
1601  continue;
1602 
1603  // If the input to SCCP is actually switch on undef, fix the undef to
1604  // the first constant.
1605  if (isa<UndefValue>(SI->getCondition())) {
1606  SI->setCondition(SI->case_begin()->getCaseValue());
1607  markEdgeExecutable(&BB, SI->case_begin()->getCaseSuccessor());
1608  MadeChange = true;
1609  continue;
1610  }
1611 
1612  // Otherwise, it is a branch on a symbolic value which is currently
1613  // considered to be undef. Make sure some edge is executable, so a
1614  // branch on "undef" always flows somewhere.
1615  // FIXME: Distinguish between dead code and an LLVM "undef" value.
1616  BasicBlock *DefaultSuccessor = SI->case_begin()->getCaseSuccessor();
1617  if (markEdgeExecutable(&BB, DefaultSuccessor))
1618  MadeChange = true;
1619 
1620  continue;
1621  }
1622  }
1623 
1624  return MadeChange;
1625 }
1626 
1627 static bool tryToReplaceWithConstant(SCCPSolver &Solver, Value *V) {
1628  Constant *Const = nullptr;
1629  if (V->getType()->isStructTy()) {
1630  std::vector<ValueLatticeElement> IVs = Solver.getStructLatticeValueFor(V);
1631  if (any_of(IVs,
1632  [](const ValueLatticeElement &LV) { return isOverdefined(LV); }))
1633  return false;
1634  std::vector<Constant *> ConstVals;
1635  auto *ST = cast<StructType>(V->getType());
1636  for (unsigned i = 0, e = ST->getNumElements(); i != e; ++i) {
1637  ValueLatticeElement V = IVs[i];
1638  ConstVals.push_back(isConstant(V)
1639  ? Solver.getConstant(V)
1640  : UndefValue::get(ST->getElementType(i)));
1641  }
1642  Const = ConstantStruct::get(ST, ConstVals);
1643  } else {
1644  const ValueLatticeElement &IV = Solver.getLatticeValueFor(V);
1645  if (isOverdefined(IV))
1646  return false;
1647 
1648  Const =
1649  isConstant(IV) ? Solver.getConstant(IV) : UndefValue::get(V->getType());
1650  }
1651  assert(Const && "Constant is nullptr here!");
1652 
1653  // Replacing `musttail` instructions with constant breaks `musttail` invariant
1654  // unless the call itself can be removed
1655  CallInst *CI = dyn_cast<CallInst>(V);
1656  if (CI && CI->isMustTailCall() && !CI->isSafeToRemove()) {
1657  Function *F = CI->getCalledFunction();
1658 
1659  // Don't zap returns of the callee
1660  if (F)
1661  Solver.AddMustTailCallee(F);
1662 
1663  LLVM_DEBUG(dbgs() << " Can\'t treat the result of musttail call : " << *CI
1664  << " as a constant\n");
1665  return false;
1666  }
1667 
1668  LLVM_DEBUG(dbgs() << " Constant: " << *Const << " = " << *V << '\n');
1669 
1670  // Replaces all of the uses of a variable with uses of the constant.
1671  V->replaceAllUsesWith(Const);
1672  return true;
1673 }
1674 
1675 static bool simplifyInstsInBlock(SCCPSolver &Solver, BasicBlock &BB,
1676  SmallPtrSetImpl<Value *> &InsertedValues,
1677  Statistic &InstRemovedStat,
1678  Statistic &InstReplacedStat) {
1679  bool MadeChanges = false;
1680  for (Instruction &Inst : make_early_inc_range(BB)) {
1681  if (Inst.getType()->isVoidTy())
1682  continue;
1683  if (tryToReplaceWithConstant(Solver, &Inst)) {
1684  if (Inst.isSafeToRemove())
1685  Inst.eraseFromParent();
1686  // Hey, we just changed something!
1687  MadeChanges = true;
1688  ++InstRemovedStat;
1689  } else if (isa<SExtInst>(&Inst)) {
1690  Value *ExtOp = Inst.getOperand(0);
1691  if (isa<Constant>(ExtOp) || InsertedValues.count(ExtOp))
1692  continue;
1693  const ValueLatticeElement &IV = Solver.getLatticeValueFor(ExtOp);
1694  if (!IV.isConstantRange(/*UndefAllowed=*/false))
1695  continue;
1696  if (IV.getConstantRange().isAllNonNegative()) {
1697  auto *ZExt = new ZExtInst(ExtOp, Inst.getType(), "", &Inst);
1698  InsertedValues.insert(ZExt);
1699  Inst.replaceAllUsesWith(ZExt);
1700  Solver.removeLatticeValueFor(&Inst);
1701  Inst.eraseFromParent();
1702  InstReplacedStat++;
1703  MadeChanges = true;
1704  }
1705  }
1706  }
1707  return MadeChanges;
1708 }
1709 
1710 // runSCCP() - Run the Sparse Conditional Constant Propagation algorithm,
1711 // and return true if the function was modified.
1712 static bool runSCCP(Function &F, const DataLayout &DL,
1713  const TargetLibraryInfo *TLI) {
1714  LLVM_DEBUG(dbgs() << "SCCP on function '" << F.getName() << "'\n");
1715  SCCPSolver Solver(
1716  DL, [TLI](Function &F) -> const TargetLibraryInfo & { return *TLI; },
1717  F.getContext());
1718 
1719  // Mark the first block of the function as being executable.
1720  Solver.MarkBlockExecutable(&F.front());
1721 
1722  // Mark all arguments to the function as being overdefined.
1723  for (Argument &AI : F.args())
1724  Solver.markOverdefined(&AI);
1725 
1726  // Solve for constants.
1727  bool ResolvedUndefs = true;
1728  while (ResolvedUndefs) {
1729  Solver.Solve();
1730  LLVM_DEBUG(dbgs() << "RESOLVING UNDEFs\n");
1731  ResolvedUndefs = Solver.ResolvedUndefsIn(F);
1732  }
1733 
1734  bool MadeChanges = false;
1735 
1736  // If we decided that there are basic blocks that are dead in this function,
1737  // delete their contents now. Note that we cannot actually delete the blocks,
1738  // as we cannot modify the CFG of the function.
1739 
1740  SmallPtrSet<Value *, 32> InsertedValues;
1741  for (BasicBlock &BB : F) {
1742  if (!Solver.isBlockExecutable(&BB)) {
1743  LLVM_DEBUG(dbgs() << " BasicBlock Dead:" << BB);
1744 
1745  ++NumDeadBlocks;
1746  NumInstRemoved += removeAllNonTerminatorAndEHPadInstructions(&BB).first;
1747 
1748  MadeChanges = true;
1749  continue;
1750  }
1751 
1752  MadeChanges |= simplifyInstsInBlock(Solver, BB, InsertedValues,
1753  NumInstRemoved, NumInstReplaced);
1754  }
1755 
1756  return MadeChanges;
1757 }
1758 
1760  const DataLayout &DL = F.getParent()->getDataLayout();
1761  auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
1762  if (!runSCCP(F, DL, &TLI))
1763  return PreservedAnalyses::all();
1764 
1765  auto PA = PreservedAnalyses();
1766  PA.preserve<GlobalsAA>();
1767  PA.preserveSet<CFGAnalyses>();
1768  return PA;
1769 }
1770 
1771 namespace {
1772 
1773 //===--------------------------------------------------------------------===//
1774 //
1775 /// SCCP Class - This class uses the SCCPSolver to implement a per-function
1776 /// Sparse Conditional Constant Propagator.
1777 ///
1778 class SCCPLegacyPass : public FunctionPass {
1779 public:
1780  // Pass identification, replacement for typeid
1781  static char ID;
1782 
1783  SCCPLegacyPass() : FunctionPass(ID) {
1785  }
1786 
1787  void getAnalysisUsage(AnalysisUsage &AU) const override {
1790  AU.setPreservesCFG();
1791  }
1792 
1793  // runOnFunction - Run the Sparse Conditional Constant Propagation
1794  // algorithm, and return true if the function was modified.
1795  bool runOnFunction(Function &F) override {
1796  if (skipFunction(F))
1797  return false;
1798  const DataLayout &DL = F.getParent()->getDataLayout();
1799  const TargetLibraryInfo *TLI =
1800  &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
1801  return runSCCP(F, DL, TLI);
1802  }
1803 };
1804 
1805 } // end anonymous namespace
1806 
1807 char SCCPLegacyPass::ID = 0;
1808 
1809 INITIALIZE_PASS_BEGIN(SCCPLegacyPass, "sccp",
1810  "Sparse Conditional Constant Propagation", false, false)
1812 INITIALIZE_PASS_END(SCCPLegacyPass, "sccp",
1813  "Sparse Conditional Constant Propagation", false, false)
1814 
1815 // createSCCPPass - This is the public interface to this file.
1816 FunctionPass *llvm::createSCCPPass() { return new SCCPLegacyPass(); }
1817 
1819  SmallVector<ReturnInst *, 8> &ReturnsToZap,
1820  SCCPSolver &Solver) {
1821  // We can only do this if we know that nothing else can call the function.
1822  if (!Solver.isArgumentTrackedFunction(&F))
1823  return;
1824 
1825  // There is a non-removable musttail call site of this function. Zapping
1826  // returns is not allowed.
1827  if (Solver.isMustTailCallee(&F)) {
1828  LLVM_DEBUG(dbgs() << "Can't zap returns of the function : " << F.getName()
1829  << " due to present musttail call of it\n");
1830  return;
1831  }
1832 
1833  assert(
1834  all_of(F.users(),
1835  [&Solver](User *U) {
1836  if (isa<Instruction>(U) &&
1837  !Solver.isBlockExecutable(cast<Instruction>(U)->getParent()))
1838  return true;
1839  // Non-callsite uses are not impacted by zapping. Also, constant
1840  // uses (like blockaddresses) could stuck around, without being
1841  // used in the underlying IR, meaning we do not have lattice
1842  // values for them.
1843  if (!isa<CallBase>(U))
1844  return true;
1845  if (U->getType()->isStructTy()) {
1846  return all_of(Solver.getStructLatticeValueFor(U),
1847  [](const ValueLatticeElement &LV) {
1848  return !isOverdefined(LV);
1849  });
1850  }
1851  return !isOverdefined(Solver.getLatticeValueFor(U));
1852  }) &&
1853  "We can only zap functions where all live users have a concrete value");
1854 
1855  for (BasicBlock &BB : F) {
1856  if (CallInst *CI = BB.getTerminatingMustTailCall()) {
1857  LLVM_DEBUG(dbgs() << "Can't zap return of the block due to present "
1858  << "musttail call : " << *CI << "\n");
1859  (void)CI;
1860  return;
1861  }
1862 
1863  if (auto *RI = dyn_cast<ReturnInst>(BB.getTerminator()))
1864  if (!isa<UndefValue>(RI->getOperand(0)))
1865  ReturnsToZap.push_back(RI);
1866  }
1867 }
1868 
1869 static bool removeNonFeasibleEdges(const SCCPSolver &Solver, BasicBlock *BB,
1870  DomTreeUpdater &DTU) {
1871  SmallPtrSet<BasicBlock *, 8> FeasibleSuccessors;
1872  bool HasNonFeasibleEdges = false;
1873  for (BasicBlock *Succ : successors(BB)) {
1874  if (Solver.isEdgeFeasible(BB, Succ))
1875  FeasibleSuccessors.insert(Succ);
1876  else
1877  HasNonFeasibleEdges = true;
1878  }
1879 
1880  // All edges feasible, nothing to do.
1881  if (!HasNonFeasibleEdges)
1882  return false;
1883 
1884  // SCCP can only determine non-feasible edges for br, switch and indirectbr.
1885  Instruction *TI = BB->getTerminator();
1886  assert((isa<BranchInst>(TI) || isa<SwitchInst>(TI) ||
1887  isa<IndirectBrInst>(TI)) &&
1888  "Terminator must be a br, switch or indirectbr");
1889 
1890  if (FeasibleSuccessors.size() == 1) {
1891  // Replace with an unconditional branch to the only feasible successor.
1892  BasicBlock *OnlyFeasibleSuccessor = *FeasibleSuccessors.begin();
1894  bool HaveSeenOnlyFeasibleSuccessor = false;
1895  for (BasicBlock *Succ : successors(BB)) {
1896  if (Succ == OnlyFeasibleSuccessor && !HaveSeenOnlyFeasibleSuccessor) {
1897  // Don't remove the edge to the only feasible successor the first time
1898  // we see it. We still do need to remove any multi-edges to it though.
1899  HaveSeenOnlyFeasibleSuccessor = true;
1900  continue;
1901  }
1902 
1903  Succ->removePredecessor(BB);
1904  Updates.push_back({DominatorTree::Delete, BB, Succ});
1905  }
1906 
1907  BranchInst::Create(OnlyFeasibleSuccessor, BB);
1908  TI->eraseFromParent();
1909  DTU.applyUpdatesPermissive(Updates);
1910  } else if (FeasibleSuccessors.size() > 1) {
1911  SwitchInstProfUpdateWrapper SI(*cast<SwitchInst>(TI));
1913  for (auto CI = SI->case_begin(); CI != SI->case_end();) {
1914  if (FeasibleSuccessors.contains(CI->getCaseSuccessor())) {
1915  ++CI;
1916  continue;
1917  }
1918 
1919  BasicBlock *Succ = CI->getCaseSuccessor();
1920  Succ->removePredecessor(BB);
1921  Updates.push_back({DominatorTree::Delete, BB, Succ});
1922  SI.removeCase(CI);
1923  // Don't increment CI, as we removed a case.
1924  }
1925 
1926  DTU.applyUpdatesPermissive(Updates);
1927  } else {
1928  llvm_unreachable("Must have at least one feasible successor");
1929  }
1930  return true;
1931 }
1932 
1934  Module &M, const DataLayout &DL,
1935  std::function<const TargetLibraryInfo &(Function &)> GetTLI,
1936  function_ref<AnalysisResultsForFn(Function &)> getAnalysis) {
1937  SCCPSolver Solver(DL, GetTLI, M.getContext());
1938 
1939  // Loop over all functions, marking arguments to those with their addresses
1940  // taken or that are external as overdefined.
1941  for (Function &F : M) {
1942  if (F.isDeclaration())
1943  continue;
1944 
1945  Solver.addAnalysis(F, getAnalysis(F));
1946 
1947  // Determine if we can track the function's return values. If so, add the
1948  // function to the solver's set of return-tracked functions.
1950  Solver.AddTrackedFunction(&F);
1951 
1952  // Determine if we can track the function's arguments. If so, add the
1953  // function to the solver's set of argument-tracked functions.
1955  Solver.AddArgumentTrackedFunction(&F);
1956  continue;
1957  }
1958 
1959  // Assume the function is called.
1960  Solver.MarkBlockExecutable(&F.front());
1961 
1962  // Assume nothing about the incoming arguments.
1963  for (Argument &AI : F.args())
1964  Solver.markOverdefined(&AI);
1965  }
1966 
1967  // Determine if we can track any of the module's global variables. If so, add
1968  // the global variables we can track to the solver's set of tracked global
1969  // variables.
1970  for (GlobalVariable &G : M.globals()) {
1971  G.removeDeadConstantUsers();
1973  Solver.TrackValueOfGlobalVariable(&G);
1974  }
1975 
1976  // Solve for constants.
1977  bool ResolvedUndefs = true;
1978  Solver.Solve();
1979  while (ResolvedUndefs) {
1980  LLVM_DEBUG(dbgs() << "RESOLVING UNDEFS\n");
1981  ResolvedUndefs = false;
1982  for (Function &F : M) {
1983  if (Solver.ResolvedUndefsIn(F))
1984  ResolvedUndefs = true;
1985  }
1986  if (ResolvedUndefs)
1987  Solver.Solve();
1988  }
1989 
1990  bool MadeChanges = false;
1991 
1992  // Iterate over all of the instructions in the module, replacing them with
1993  // constants if we have found them to be of constant values.
1994 
1995  for (Function &F : M) {
1996  if (F.isDeclaration())
1997  continue;
1998 
1999  SmallVector<BasicBlock *, 512> BlocksToErase;
2000 
2001  if (Solver.isBlockExecutable(&F.front())) {
2002  bool ReplacedPointerArg = false;
2003  for (Argument &Arg : F.args()) {
2004  if (!Arg.use_empty() && tryToReplaceWithConstant(Solver, &Arg)) {
2005  ReplacedPointerArg |= Arg.getType()->isPointerTy();
2006  ++IPNumArgsElimed;
2007  }
2008  }
2009 
2010  // If we replaced an argument, the argmemonly and
2011  // inaccessiblemem_or_argmemonly attributes do not hold any longer. Remove
2012  // them from both the function and callsites.
2013  if (ReplacedPointerArg) {
2014  AttrBuilder AttributesToRemove;
2015  AttributesToRemove.addAttribute(Attribute::ArgMemOnly);
2016  AttributesToRemove.addAttribute(Attribute::InaccessibleMemOrArgMemOnly);
2017  F.removeAttributes(AttributeList::FunctionIndex, AttributesToRemove);
2018 
2019  for (User *U : F.users()) {
2020  auto *CB = dyn_cast<CallBase>(U);
2021  if (!CB || CB->getCalledFunction() != &F)
2022  continue;
2023 
2025  AttributesToRemove);
2026  }
2027  }
2028  }
2029 
2030  SmallPtrSet<Value *, 32> InsertedValues;
2031  for (BasicBlock &BB : F) {
2032  if (!Solver.isBlockExecutable(&BB)) {
2033  LLVM_DEBUG(dbgs() << " BasicBlock Dead:" << BB);
2034  ++NumDeadBlocks;
2035 
2036  MadeChanges = true;
2037 
2038  if (&BB != &F.front())
2039  BlocksToErase.push_back(&BB);
2040  continue;
2041  }
2042 
2043  MadeChanges |= simplifyInstsInBlock(Solver, BB, InsertedValues,
2044  IPNumInstRemoved, IPNumInstReplaced);
2045  }
2046 
2047  DomTreeUpdater DTU = Solver.getDTU(F);
2048  // Change dead blocks to unreachable. We do it after replacing constants
2049  // in all executable blocks, because changeToUnreachable may remove PHI
2050  // nodes in executable blocks we found values for. The function's entry
2051  // block is not part of BlocksToErase, so we have to handle it separately.
2052  for (BasicBlock *BB : BlocksToErase) {
2053  NumInstRemoved +=
2054  changeToUnreachable(BB->getFirstNonPHI(), /*UseLLVMTrap=*/false,
2055  /*PreserveLCSSA=*/false, &DTU);
2056  }
2057  if (!Solver.isBlockExecutable(&F.front()))
2058  NumInstRemoved += changeToUnreachable(F.front().getFirstNonPHI(),
2059  /*UseLLVMTrap=*/false,
2060  /*PreserveLCSSA=*/false, &DTU);
2061 
2062  for (BasicBlock &BB : F)
2063  MadeChanges |= removeNonFeasibleEdges(Solver, &BB, DTU);
2064 
2065  for (BasicBlock *DeadBB : BlocksToErase)
2066  DTU.deleteBB(DeadBB);
2067 
2068  for (BasicBlock &BB : F) {
2069  for (BasicBlock::iterator BI = BB.begin(), E = BB.end(); BI != E;) {
2070  Instruction *Inst = &*BI++;
2071  if (Solver.getPredicateInfoFor(Inst)) {
2072  if (auto *II = dyn_cast<IntrinsicInst>(Inst)) {
2073  if (II->getIntrinsicID() == Intrinsic::ssa_copy) {
2074  Value *Op = II->getOperand(0);
2075  Inst->replaceAllUsesWith(Op);
2076  Inst->eraseFromParent();
2077  }
2078  }
2079  }
2080  }
2081  }
2082  }
2083 
2084  // If we inferred constant or undef return values for a function, we replaced
2085  // all call uses with the inferred value. This means we don't need to bother
2086  // actually returning anything from the function. Replace all return
2087  // instructions with return undef.
2088  //
2089  // Do this in two stages: first identify the functions we should process, then
2090  // actually zap their returns. This is important because we can only do this
2091  // if the address of the function isn't taken. In cases where a return is the
2092  // last use of a function, the order of processing functions would affect
2093  // whether other functions are optimizable.
2094  SmallVector<ReturnInst*, 8> ReturnsToZap;
2095 
2096  for (const auto &I : Solver.getTrackedRetVals()) {
2097  Function *F = I.first;
2098  const ValueLatticeElement &ReturnValue = I.second;
2099 
2100  // If there is a known constant range for the return value, add !range
2101  // metadata to the function's call sites.
2102  if (ReturnValue.isConstantRange() &&
2103  !ReturnValue.getConstantRange().isSingleElement()) {
2104  // Do not add range metadata if the return value may include undef.
2105  if (ReturnValue.isConstantRangeIncludingUndef())
2106  continue;
2107 
2108  auto &CR = ReturnValue.getConstantRange();
2109  for (User *User : F->users()) {
2110  auto *CB = dyn_cast<CallBase>(User);
2111  if (!CB || CB->getCalledFunction() != F)
2112  continue;
2113 
2114  // Limit to cases where the return value is guaranteed to be neither
2115  // poison nor undef. Poison will be outside any range and currently
2116  // values outside of the specified range cause immediate undefined
2117  // behavior.
2118  if (!isGuaranteedNotToBeUndefOrPoison(CB, nullptr, CB))
2119  continue;
2120 
2121  // Do not touch existing metadata for now.
2122  // TODO: We should be able to take the intersection of the existing
2123  // metadata and the inferred range.
2124  if (CB->getMetadata(LLVMContext::MD_range))
2125  continue;
2126 
2128  Metadata *RangeMD[] = {
2129  ConstantAsMetadata::get(ConstantInt::get(Context, CR.getLower())),
2130  ConstantAsMetadata::get(ConstantInt::get(Context, CR.getUpper()))};
2131  CB->setMetadata(LLVMContext::MD_range, MDNode::get(Context, RangeMD));
2132  }
2133  continue;
2134  }
2135  if (F->getReturnType()->isVoidTy())
2136  continue;
2137  if (isConstant(ReturnValue) || ReturnValue.isUnknownOrUndef())
2138  findReturnsToZap(*F, ReturnsToZap, Solver);
2139  }
2140 
2141  for (auto F : Solver.getMRVFunctionsTracked()) {
2142  assert(F->getReturnType()->isStructTy() &&
2143  "The return type should be a struct");
2144  StructType *STy = cast<StructType>(F->getReturnType());
2145  if (Solver.isStructLatticeConstant(F, STy))
2146  findReturnsToZap(*F, ReturnsToZap, Solver);
2147  }
2148 
2149  // Zap all returns which we've identified as zap to change.
2150  SmallSetVector<Function *, 8> FuncZappedReturn;
2151  for (unsigned i = 0, e = ReturnsToZap.size(); i != e; ++i) {
2152  Function *F = ReturnsToZap[i]->getParent()->getParent();
2153  ReturnsToZap[i]->setOperand(0, UndefValue::get(F->getReturnType()));
2154  // Record all functions that are zapped.
2155  FuncZappedReturn.insert(F);
2156  }
2157 
2158  // Remove the returned attribute for zapped functions and the
2159  // corresponding call sites.
2160  for (Function *F : FuncZappedReturn) {
2161  for (Argument &A : F->args())
2162  F->removeParamAttr(A.getArgNo(), Attribute::Returned);
2163  for (Use &U : F->uses()) {
2164  // Skip over blockaddr users.
2165  if (isa<BlockAddress>(U.getUser()))
2166  continue;
2167  CallBase *CB = cast<CallBase>(U.getUser());
2168  for (Use &Arg : CB->args())
2169  CB->removeParamAttr(CB->getArgOperandNo(&Arg), Attribute::Returned);
2170  }
2171  }
2172 
2173  // If we inferred constant or undef values for globals variables, we can
2174  // delete the global and any stores that remain to it.
2175  for (auto &I : make_early_inc_range(Solver.getTrackedGlobals())) {
2176  GlobalVariable *GV = I.first;
2177  if (isOverdefined(I.second))
2178  continue;
2179  LLVM_DEBUG(dbgs() << "Found that GV '" << GV->getName()
2180  << "' is constant!\n");
2181  while (!GV->use_empty()) {
2182  StoreInst *SI = cast<StoreInst>(GV->user_back());
2183  SI->eraseFromParent();
2184  MadeChanges = true;
2185  }
2186  M.getGlobalList().erase(GV);
2187  ++IPNumGlobalConst;
2188  }
2189 
2190  return MadeChanges;
2191 }
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:524
uint64_t CallInst * C
Return a value (possibly void), from a function.
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks &#39;this&#39; from the containing basic block and deletes it.
Definition: Instruction.cpp:77
static bool simplifyInstsInBlock(SCCPSolver &Solver, BasicBlock &BB, SmallPtrSetImpl< Value *> &InsertedValues, Statistic &InstRemovedStat, Statistic &InstReplacedStat)
Definition: SCCP.cpp:1675
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:111
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:801
bool contains(ConstPtrType Ptr) const
Definition: SmallPtrSet.h:381
CaseIt case_end()
Returns a read/write iterator that points one past the last in the SwitchInst.
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:718
iterator_range< use_iterator > uses()
Definition: Value.h:375
void removeParamAttr(unsigned ArgNo, Attribute::AttrKind Kind)
removes the attribute from the list of attributes.
Definition: Function.cpp:538
static bool isConstant(const MachineInstr &MI)
LLVM_NODISCARD std::enable_if_t< !is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type > dyn_cast(const Y &Val)
Definition: Casting.h:334
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
MergeOptions & setMaxWidenSteps(unsigned Steps=1)
Definition: ValueLattice.h:138
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:29
LLVMContext & Context
Base class for instruction visitors.
Definition: InstVisitor.h:79
Interprocedural Sparse Conditional Constant Propagation
Definition: SCCP.cpp:88
sccp
Definition: SCCP.cpp:1812
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:785
static ValueLatticeElement getRange(ConstantRange CR, bool MayIncludeUndef=false)
Definition: ValueLattice.h:215
const Constant * getInitializer() const
getInitializer - Return the initializer for this global variable.
This class represents lattice values for constants.
Definition: AllocatorList.h:23
This is the interface for a simple mod/ref and alias analysis over globals.
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:67
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:1208
BasicBlock * getSuccessor(unsigned Idx) const
Return the specified successor. This instruction must be a terminator.
An instruction for ordering other memory operations.
Definition: Instructions.h:444
const ConstantRange & getConstantRange(bool UndefAllowed=true) const
Returns the constant range for this value.
Definition: ValueLattice.h:270
bool canTrackArgumentsInterprocedurally(Function *F)
Determine if the values of the given function&#39;s arguments can be tracked interprocedurally.
Constant * ConstantFoldCall(const CallBase *Call, Function *F, ArrayRef< Constant *> Operands, const TargetLibraryInfo *TLI=nullptr)
ConstantFoldCall - Attempt to constant fold a call to the specified function with the specified argum...
Implements a dense probed hash-table based set.
Definition: DenseSet.h:260
This class represents zero extension of integer types.
void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
Definition: BasicBlock.cpp:338
unsigned getNumElements() const
Random access to the elements.
Definition: DerivedTypes.h:328
bool isSafeToRemove() const
Return true if the instruction can be removed if the result is unused.
This class represents a function call, abstracting a target machine&#39;s calling convention.
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition: STLExtras.h:581
const Value * getTrueValue() const
CaseIt case_begin()
Returns a read/write iterator that points to the first case in the SwitchInst.
A wrapper class to simplify modification of SwitchInst cases along with their prof branch_weights met...
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLExtras.h:176
This class implements a map that also provides access to all stored values in a deterministic order...
Definition: MapVector.h:37
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1498
arg_iterator arg_end()
Definition: Function.h:758
STATISTIC(NumFunctions, "Total number of functions")
Metadata node.
Definition: Metadata.h:870
bool markConstant(Constant *V, bool MayIncludeUndef=false)
Definition: ValueLattice.h:302
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1137
F(f)
bool isConstantRange(bool UndefAllowed=true) const
Returns true if this value is a constant range.
Definition: ValueLattice.h:250
User::op_iterator arg_end()
Return the iterator pointing to the end of the argument list.
Definition: InstrTypes.h:1267
An instruction for reading from memory.
Definition: Instructions.h:174
const Instruction * 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:152
bool isVectorTy() const
True if this is an instance of VectorType.
Definition: Type.h:231
static ConstantRange makeAllowedICmpRegion(CmpInst::Predicate Pred, const ConstantRange &Other)
Produce the smallest range such that all values that may satisfy the given predicate with any value c...
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:728
void reserve(size_type N)
Definition: SmallVector.h:493
bool isMustTailCall() const
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:32
static void findReturnsToZap(Function &F, SmallVector< ReturnInst *, 8 > &ReturnsToZap, SCCPSolver &Solver)
Definition: SCCP.cpp:1818
MergeOptions & setCheckWiden(bool V=true)
Definition: ValueLattice.h:133
std::unique_ptr< PredicateInfo > PredInfo
Definition: SCCP.h:43
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:207
bool isUnknownOrUndef() const
Definition: ValueLattice.h:240
The address of a basic block.
Definition: Constants.h:849
uint32_t getBitWidth() const
Get the bit width of this ConstantRange.
AnalysisUsage & addRequired()
void setNumRangeExtensions(unsigned N)
Definition: ValueLattice.h:488
bool isVolatile() const
Return true if this is a load from a volatile memory location.
Definition: Instructions.h:211
static bool removeNonFeasibleEdges(const SCCPSolver &Solver, BasicBlock *BB, DomTreeUpdater &DTU)
Definition: SCCP.cpp:1869
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:397
This is the base class for all instructions that perform data casts.
Definition: InstrTypes.h:432
ArrayRef< T > makeArrayRef(const T &OneElt)
Construct an ArrayRef from a single element.
Definition: ArrayRef.h:458
Class to represent struct types.
Definition: DerivedTypes.h:218
Struct to control some aspects related to merging constant ranges.
Definition: ValueLattice.h:109
LLVMContext & getContext() const
Get the global data context.
Definition: Module.h:253
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44
void initializeSCCPLegacyPassPass(PassRegistry &)
static Optional< unsigned > getOpcode(ArrayRef< VPValue *> Values)
Returns the opcode of Values or ~0 if they do not all agree.
Definition: VPlanSLP.cpp:197
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:43
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition: Type.h:198
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: SCCP.cpp:1759
bool isConstantRangeIncludingUndef() const
Definition: ValueLattice.h:243
CmpInst::Predicate Predicate
Definition: PredicateInfo.h:76
bool hasMetadata() const
Return true if this instruction has any metadata attached to it.
Definition: Instruction.h:259
static ValueLatticeElement getNot(Constant *C)
Definition: ValueLattice.h:209
FunctionPass * createSCCPPass()
Definition: SCCP.cpp:1816
mir Rename Register Operands
bool contains(const APInt &Val) const
Return true if the specified value is in the set.
Helper struct for bundling up the analysis results per function for IPSCCP.
Definition: SCCP.h:42
unsigned getNumRangeExtensions() const
Definition: ValueLattice.h:487
void assign(size_type NumElts, const T &Elt)
Definition: SmallVector.h:544
Instruction::CastOps getOpcode() const
Return the opcode of this CastInst.
Definition: InstrTypes.h:685
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:246
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:141
#define T
static const unsigned MaxNumRangeExtensions
Definition: SCCP.cpp:85
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
Definition: Instruction.h:277
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:160
PostDominatorTree * PDT
Definition: SCCP.h:45
An instruction for storing to memory.
Definition: Instructions.h:303
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:511
iterator find(const KeyT &Key)
Definition: MapVector.h:147
static ConstantAsMetadata * get(Constant *C)
Definition: Metadata.h:410
ConstantRange castOp(Instruction::CastOps CastOp, uint32_t BitWidth) const
Return a new range representing the possible values resulting from an application of the specified ca...
unsigned getNumSuccessors() const
Return the number of successors that this instruction has.
Value * getOperand(unsigned i) const
Definition: User.h:169
SwitchInst::CaseIt removeCase(SwitchInst::CaseIt I)
Delegate the call to the underlying SwitchInst::removeCase() and remove correspondent branch weight...
Constant * getAggregateElement(unsigned Elt) const
For aggregates (struct/array/vector) return the constant that corresponds to the specified element if...
Definition: Constants.cpp:410
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:138
an instruction for type-safe pointer arithmetic to access elements of arrays and structs ...
Definition: Instructions.h:905
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata *> MDs)
Definition: Metadata.h:1172
static bool runOnFunction(Function &F, bool PostInlining)
bool isAllNonNegative() const
Return true if all values in this range are non-negative.
Type * getReturnType() const
Returns the type of the ret val.
Definition: Function.h:170
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
static ConstantPointerNull * get(PointerType *T)
Static factory methods - Return objects of the specified value.
Definition: Constants.cpp:1670
ConstantRange getConstantRangeFromMetadata(const MDNode &RangeMD)
Parse out a conservative ConstantRange from !range metadata.
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:46
void deleteBB(BasicBlock *DelBB)
Delete DelBB.
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:68
static BlockAddress * get(Function *F, BasicBlock *BB)
Return a BlockAddress for the specified function and basic block.
Definition: Constants.cpp:1703
This function has undefined behavior.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This is an important base class in LLVM.
Definition: Constant.h:41
Resume the propagation of an exception.
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:364
unsigned getNumIndices() const
unsigned getArgOperandNo(const Use *U) const
Given a use for a arg operand, get the arg operand number that corresponds to it. ...
Definition: InstrTypes.h:1327
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:1505
const Instruction & back() const
Definition: BasicBlock.h:310
Analysis pass providing a never-invalidated alias analysis result.
constexpr double e
Definition: MathExtras.h:58
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:284
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
static Constant * get(StructType *T, ArrayRef< Constant *> V)
Definition: Constants.cpp:1236
arg_iterator arg_begin()
Definition: Function.h:749
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:375
void applyUpdatesPermissive(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
const Function * getFunction() const
Return the function this instruction belongs to.
Definition: Instruction.cpp:69
static bool tryToReplaceWithConstant(SCCPSolver &Solver, Value *V)
Definition: SCCP.cpp:1627
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...
static bool isIntrinsicSupported(Intrinsic::ID IntrinsicID)
Returns true if ConstantRange calculations are supported for intrinsic with IntrinsicID.
const Value * getCondition() const
LLVMContext & getContext() const
getContext - Return a reference to the LLVMContext associated with this function. ...
Definition: Function.cpp:296
static UndefValue * get(Type *T)
Static factory methods - Return an &#39;undef&#39; object of the specified type.
Definition: Constants.cpp:1684
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:161
bool isExceptionalTerminator() const
Definition: Instruction.h:170
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
iterator_range< User::op_iterator > args()
Iteration adapter for range-for loops.
Definition: InstrTypes.h:1277
This file implements the PredicateInfo analysis, which creates an Extended SSA form for operations us...
Constant * getConstant() const
Definition: ValueLattice.h:256
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.
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
Definition: Metadata.cpp:1296
bool runIPSCCP(Module &M, const DataLayout &DL, std::function< const TargetLibraryInfo &(Function &)> GetTLI, function_ref< AnalysisResultsForFn(Function &)> getAnalysis)
Definition: SCCP.cpp:1933
CallBr instruction, tracking function calls that may not return control but instead transfer it to a ...
bool canConstantFoldCallTo(const CallBase *Call, const Function *F)
canConstantFoldCallTo - Return true if its even possible to fold a call to the specified function...
size_type size() const
Definition: SmallPtrSet.h:92
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: MapVector.h:117
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:307
Iterator for intrusive lists based on ilist_node.
unsigned getNumOperands() const
Definition: User.h:191
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:442
This is the shared class of boolean and integer constants.
Definition: Constants.h:77
BlockVerifier::State From
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:350
INITIALIZE_PASS_BEGIN(IPSCCPLegacyPass, "ipsccp", "Interprocedural Sparse Conditional Constant Propagation", false, false) INITIALIZE_PASS_END(IPSCCPLegacyPass
unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type...
Definition: Type.cpp:137
void removeAttributes(unsigned i, const AttrBuilder &Attrs)
Definition: InstrTypes.h:1491
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:960
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.
This class represents a range of values.
Definition: ConstantRange.h:47
const DataFlowGraph & G
Definition: RDFGraph.cpp:202
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:838
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:253
Type * getDestTy() const
Return the destination type, as a convenience.
Definition: InstrTypes.h:692
unsigned getNumIncomingValues() const
Return the number of incoming edges.
bool NullPointerIsDefined(const Function *F, unsigned AS=0)
Check whether null pointer dereferencing is considered undefined behavior for a given function or an ...
Definition: Function.cpp:1760
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
std::pair< unsigned, unsigned > removeAllNonTerminatorAndEHPadInstructions(BasicBlock *BB)
Remove all instructions from a basic block other than its terminator and any present EH pad instructi...
Definition: Local.cpp:2013
Class for arbitrary precision integers.
Definition: APInt.h:70
iterator_range< user_iterator > users()
Definition: Value.h:420
Represents analyses that only rely on functions&#39; control flow.
Definition: PassManager.h:116
const Value * getFalseValue() const
bool mergeIn(const ValueLatticeElement &RHS, MergeOptions Opts=MergeOptions())
Updates this object to approximate both this object and RHS.
Definition: ValueLattice.h:386
User::op_iterator arg_begin()
Return the iterator pointing to the beginning of the argument list.
Definition: InstrTypes.h:1261
void removeAttributes(unsigned i, const AttrBuilder &Attrs)
removes the attributes from the list of attributes.
Definition: Function.cpp:532
iterator begin() const
Definition: SmallPtrSet.h:395
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:295
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation.
Definition: InstrTypes.h:1351
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:107
#define I(x, y, z)
Definition: MD5.cpp:59
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
DominatorTree * DT
Definition: SCCP.h:44
void removeParamAttr(unsigned ArgNo, Attribute::AttrKind Kind)
Removes the attribute from the given argument.
Definition: InstrTypes.h:1498
idx_iterator idx_begin() const
Type * getValueType() const
Definition: GlobalValue.h:273
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
Definition: BasicBlock.h:352
static ValueLatticeElement getValueFromMetadata(const Instruction *I)
Definition: SCCP.cpp:1131
bool isDeclaration() const
Return true if the primary definition of this global value is outside of the current translation unit...
Definition: Globals.cpp:228
bool isSingleElement() const
Return true if this set contains exactly one member.
Analysis pass providing the TargetLibraryInfo.
unsigned getPointerAddressSpace() const
Returns the address space of the pointer operand.
Definition: Instructions.h:272
Value * SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for a BinaryOperator, fold the result or return null.
iterator end()
Definition: MapVector.h:71
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
const BasicBlock & front() const
Definition: Function.h:741
AttrBuilder & addAttribute(Attribute::AttrKind Val)
Add an attribute to the builder.
Definition: Attributes.h:780
bool isSingleValueType() const
Return true if the type is a valid type for a register in codegen.
Definition: Type.h:253
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:572
LLVM Value Representation.
Definition: Value.h:75
succ_range successors(Instruction *I)
Definition: CFG.h:260
static const Function * getParent(const Value *V)
static ValueLatticeElement::MergeOptions getMaxWidenStepsOpts()
Returns MergeOptions with MaxWidenSteps set to MaxNumRangeExtensions.
Definition: SCCP.cpp:88
Invoke instruction.
print Print MemDeps of function
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1556
static ValueLatticeElement getOverdefined()
Definition: ValueLattice.h:232
A container for analyses that lazily runs them and caches their results.
This header defines various interfaces for pass management in LLVM.
#define LLVM_DEBUG(X)
Definition: Debug.h:122
static ConstantRange intrinsic(Intrinsic::ID IntrinsicID, ArrayRef< ConstantRange > Ops)
Compute range of intrinsic result for the given operand ranges.
ConstantRange binaryOp(Instruction::BinaryOps BinOp, const ConstantRange &Other) const
Return a new range representing the possible values resulting from an application of the specified bi...
Root of the metadata hierarchy.
Definition: Metadata.h:58
unsigned changeToUnreachable(Instruction *I, bool UseLLVMTrap, bool PreserveLCSSA=false, DomTreeUpdater *DTU=nullptr, MemorySSAUpdater *MSSAU=nullptr)
Insert an unreachable instruction before the specified instruction, making it and the rest of the cod...
Definition: Local.cpp:2037
bool use_empty() const
Definition: Value.h:343
bool isGuaranteedNotToBeUndefOrPoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Return true if this function can prove that V does not have undef bits and is never poison...
static bool runSCCP(Function &F, const DataLayout &DL, const TargetLibraryInfo *TLI)
Definition: SCCP.cpp:1712
iterator_range< arg_iterator > args()
Definition: Function.h:773
bool isStructTy() const
True if this is an instance of StructType.
Definition: Type.h:219
User * user_back()
Definition: Value.h:406
const BasicBlock * getParent() const
Definition: Instruction.h:94
This instruction inserts a struct field of array element value into an aggregate value.
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
void resize(size_type N)
Definition: SmallVector.h:463
static Constant * get(unsigned Opcode, Constant *C1, unsigned Flags=0, Type *OnlyIfReducedTy=nullptr)
get - Return a unary operator constant expression, folding if possible.
Definition: Constants.cpp:2126