LLVM  14.0.0git
SCCPSolver.cpp
Go to the documentation of this file.
1 //===- SCCPSolver.cpp - SCCP Utility --------------------------- *- C++ -*-===//
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 // \file
10 // This file implements the Sparse Conditional Constant Propagation (SCCP)
11 // utility.
12 //
13 //===----------------------------------------------------------------------===//
14 
19 #include "llvm/InitializePasses.h"
20 #include "llvm/Pass.h"
21 #include "llvm/Support/Casting.h"
22 #include "llvm/Support/Debug.h"
26 #include <cassert>
27 #include <utility>
28 #include <vector>
29 
30 using namespace llvm;
31 
32 #define DEBUG_TYPE "sccp"
33 
34 // The maximum number of range extensions allowed for operations requiring
35 // widening.
36 static const unsigned MaxNumRangeExtensions = 10;
37 
38 /// Returns MergeOptions with MaxWidenSteps set to MaxNumRangeExtensions.
42 }
43 
44 namespace {
45 
46 // Helper to check if \p LV is either a constant or a constant
47 // range with a single element. This should cover exactly the same cases as the
48 // old ValueLatticeElement::isConstant() and is intended to be used in the
49 // transition to ValueLatticeElement.
50 bool isConstant(const ValueLatticeElement &LV) {
51  return LV.isConstant() ||
53 }
54 
55 // Helper to check if \p LV is either overdefined or a constant range with more
56 // than a single element. This should cover exactly the same cases as the old
57 // ValueLatticeElement::isOverdefined() and is intended to be used in the
58 // transition to ValueLatticeElement.
59 bool isOverdefined(const ValueLatticeElement &LV) {
60  return !LV.isUnknownOrUndef() && !isConstant(LV);
61 }
62 
63 } // namespace
64 
65 namespace llvm {
66 
67 /// Helper class for SCCPSolver. This implements the instruction visitor and
68 /// holds all the state.
69 class SCCPInstVisitor : public InstVisitor<SCCPInstVisitor> {
70  const DataLayout &DL;
71  std::function<const TargetLibraryInfo &(Function &)> GetTLI;
72  SmallPtrSet<BasicBlock *, 8> BBExecutable; // The BBs that are executable.
74  ValueState; // The state each value is in.
75 
76  /// StructValueState - This maintains ValueState for values that have
77  /// StructType, for example for formal arguments, calls, insertelement, etc.
79 
80  /// GlobalValue - If we are tracking any values for the contents of a global
81  /// variable, we keep a mapping from the constant accessor to the element of
82  /// the global, to the currently known value. If the value becomes
83  /// overdefined, it's entry is simply removed from this map.
85 
86  /// TrackedRetVals - If we are tracking arguments into and the return
87  /// value out of a function, it will have an entry in this map, indicating
88  /// what the known return value for the function is.
90 
91  /// TrackedMultipleRetVals - Same as TrackedRetVals, but used for functions
92  /// that return multiple values.
94  TrackedMultipleRetVals;
95 
96  /// MRVFunctionsTracked - Each function in TrackedMultipleRetVals is
97  /// represented here for efficient lookup.
98  SmallPtrSet<Function *, 16> MRVFunctionsTracked;
99 
100  /// A list of functions whose return cannot be modified.
101  SmallPtrSet<Function *, 16> MustPreserveReturnsInFunctions;
102 
103  /// TrackingIncomingArguments - This is the set of functions for whose
104  /// arguments we make optimistic assumptions about and try to prove as
105  /// constants.
106  SmallPtrSet<Function *, 16> TrackingIncomingArguments;
107 
108  /// The reason for two worklists is that overdefined is the lowest state
109  /// on the lattice, and moving things to overdefined as fast as possible
110  /// makes SCCP converge much faster.
111  ///
112  /// By having a separate worklist, we accomplish this because everything
113  /// possibly overdefined will become overdefined at the soonest possible
114  /// point.
115  SmallVector<Value *, 64> OverdefinedInstWorkList;
116  SmallVector<Value *, 64> InstWorkList;
117 
118  // The BasicBlock work list
120 
121  /// KnownFeasibleEdges - Entries in this set are edges which have already had
122  /// PHI nodes retriggered.
123  using Edge = std::pair<BasicBlock *, BasicBlock *>;
124  DenseSet<Edge> KnownFeasibleEdges;
125 
128 
129  LLVMContext &Ctx;
130 
131 private:
132  ConstantInt *getConstantInt(const ValueLatticeElement &IV) const {
133  return dyn_cast_or_null<ConstantInt>(getConstant(IV));
134  }
135 
136  // pushToWorkList - Helper for markConstant/markOverdefined
137  void pushToWorkList(ValueLatticeElement &IV, Value *V);
138 
139  // Helper to push \p V to the worklist, after updating it to \p IV. Also
140  // prints a debug message with the updated value.
141  void pushToWorkListMsg(ValueLatticeElement &IV, Value *V);
142 
143  // markConstant - Make a value be marked as "constant". If the value
144  // is not already a constant, add it to the instruction work list so that
145  // the users of the instruction are updated later.
146  bool markConstant(ValueLatticeElement &IV, Value *V, Constant *C,
147  bool MayIncludeUndef = false);
148 
149  bool markConstant(Value *V, Constant *C) {
150  assert(!V->getType()->isStructTy() && "structs should use mergeInValue");
151  return markConstant(ValueState[V], V, C);
152  }
153 
154  // markOverdefined - Make a value be marked as "overdefined". If the
155  // value is not already overdefined, add it to the overdefined instruction
156  // work list so that the users of the instruction are updated later.
157  bool markOverdefined(ValueLatticeElement &IV, Value *V);
158 
159  /// Merge \p MergeWithV into \p IV and push \p V to the worklist, if \p IV
160  /// changes.
161  bool mergeInValue(ValueLatticeElement &IV, Value *V,
162  ValueLatticeElement MergeWithV,
164  /*MayIncludeUndef=*/false, /*CheckWiden=*/false});
165 
166  bool mergeInValue(Value *V, ValueLatticeElement MergeWithV,
168  /*MayIncludeUndef=*/false, /*CheckWiden=*/false}) {
169  assert(!V->getType()->isStructTy() &&
170  "non-structs should use markConstant");
171  return mergeInValue(ValueState[V], V, MergeWithV, Opts);
172  }
173 
174  /// getValueState - Return the ValueLatticeElement object that corresponds to
175  /// the value. This function handles the case when the value hasn't been seen
176  /// yet by properly seeding constants etc.
177  ValueLatticeElement &getValueState(Value *V) {
178  assert(!V->getType()->isStructTy() && "Should use getStructValueState");
179 
180  auto I = ValueState.insert(std::make_pair(V, ValueLatticeElement()));
181  ValueLatticeElement &LV = I.first->second;
182 
183  if (!I.second)
184  return LV; // Common case, already in the map.
185 
186  if (auto *C = dyn_cast<Constant>(V))
187  LV.markConstant(C); // Constants are constant
188 
189  // All others are unknown by default.
190  return LV;
191  }
192 
193  /// getStructValueState - Return the ValueLatticeElement object that
194  /// corresponds to the value/field pair. This function handles the case when
195  /// the value hasn't been seen yet by properly seeding constants etc.
196  ValueLatticeElement &getStructValueState(Value *V, unsigned i) {
197  assert(V->getType()->isStructTy() && "Should use getValueState");
198  assert(i < cast<StructType>(V->getType())->getNumElements() &&
199  "Invalid element #");
200 
201  auto I = StructValueState.insert(
202  std::make_pair(std::make_pair(V, i), ValueLatticeElement()));
203  ValueLatticeElement &LV = I.first->second;
204 
205  if (!I.second)
206  return LV; // Common case, already in the map.
207 
208  if (auto *C = dyn_cast<Constant>(V)) {
209  Constant *Elt = C->getAggregateElement(i);
210 
211  if (!Elt)
212  LV.markOverdefined(); // Unknown sort of constant.
213  else if (isa<UndefValue>(Elt))
214  ; // Undef values remain unknown.
215  else
216  LV.markConstant(Elt); // Constants are constant.
217  }
218 
219  // All others are underdefined by default.
220  return LV;
221  }
222 
223  /// markEdgeExecutable - Mark a basic block as executable, adding it to the BB
224  /// work list if it is not already executable.
225  bool markEdgeExecutable(BasicBlock *Source, BasicBlock *Dest);
226 
227  // getFeasibleSuccessors - Return a vector of booleans to indicate which
228  // successors are reachable from a given terminator instruction.
229  void getFeasibleSuccessors(Instruction &TI, SmallVectorImpl<bool> &Succs);
230 
231  // OperandChangedState - This method is invoked on all of the users of an
232  // instruction that was just changed state somehow. Based on this
233  // information, we need to update the specified user of this instruction.
234  void operandChangedState(Instruction *I) {
235  if (BBExecutable.count(I->getParent())) // Inst is executable?
236  visit(*I);
237  }
238 
239  // Add U as additional user of V.
240  void addAdditionalUser(Value *V, User *U) {
241  auto Iter = AdditionalUsers.insert({V, {}});
242  Iter.first->second.insert(U);
243  }
244 
245  // Mark I's users as changed, including AdditionalUsers.
246  void markUsersAsChanged(Value *I) {
247  // Functions include their arguments in the use-list. Changed function
248  // values mean that the result of the function changed. We only need to
249  // update the call sites with the new function result and do not have to
250  // propagate the call arguments.
251  if (isa<Function>(I)) {
252  for (User *U : I->users()) {
253  if (auto *CB = dyn_cast<CallBase>(U))
254  handleCallResult(*CB);
255  }
256  } else {
257  for (User *U : I->users())
258  if (auto *UI = dyn_cast<Instruction>(U))
259  operandChangedState(UI);
260  }
261 
262  auto Iter = AdditionalUsers.find(I);
263  if (Iter != AdditionalUsers.end()) {
264  // Copy additional users before notifying them of changes, because new
265  // users may be added, potentially invalidating the iterator.
267  for (User *U : Iter->second)
268  if (auto *UI = dyn_cast<Instruction>(U))
269  ToNotify.push_back(UI);
270  for (Instruction *UI : ToNotify)
271  operandChangedState(UI);
272  }
273  }
274  void handleCallOverdefined(CallBase &CB);
275  void handleCallResult(CallBase &CB);
276  void handleCallArguments(CallBase &CB);
277 
278 private:
280 
281  // visit implementations - Something changed in this instruction. Either an
282  // operand made a transition, or the instruction is newly executable. Change
283  // the value type of I to reflect these changes if appropriate.
284  void visitPHINode(PHINode &I);
285 
286  // Terminators
287 
288  void visitReturnInst(ReturnInst &I);
289  void visitTerminator(Instruction &TI);
290 
291  void visitCastInst(CastInst &I);
292  void visitSelectInst(SelectInst &I);
293  void visitUnaryOperator(Instruction &I);
294  void visitBinaryOperator(Instruction &I);
295  void visitCmpInst(CmpInst &I);
296  void visitExtractValueInst(ExtractValueInst &EVI);
297  void visitInsertValueInst(InsertValueInst &IVI);
298 
299  void visitCatchSwitchInst(CatchSwitchInst &CPI) {
300  markOverdefined(&CPI);
301  visitTerminator(CPI);
302  }
303 
304  // Instructions that cannot be folded away.
305 
306  void visitStoreInst(StoreInst &I);
307  void visitLoadInst(LoadInst &I);
308  void visitGetElementPtrInst(GetElementPtrInst &I);
309 
310  void visitInvokeInst(InvokeInst &II) {
311  visitCallBase(II);
312  visitTerminator(II);
313  }
314 
315  void visitCallBrInst(CallBrInst &CBI) {
316  visitCallBase(CBI);
317  visitTerminator(CBI);
318  }
319 
320  void visitCallBase(CallBase &CB);
321  void visitResumeInst(ResumeInst &I) { /*returns void*/
322  }
323  void visitUnreachableInst(UnreachableInst &I) { /*returns void*/
324  }
325  void visitFenceInst(FenceInst &I) { /*returns void*/
326  }
327 
328  void visitInstruction(Instruction &I);
329 
330 public:
332  AnalysisResults.insert({&F, std::move(A)});
333  }
334 
335  void visitCallInst(CallInst &I) { visitCallBase(I); }
336 
338 
340  auto A = AnalysisResults.find(I->getParent()->getParent());
341  if (A == AnalysisResults.end())
342  return nullptr;
343  return A->second.PredInfo->getPredicateInfoFor(I);
344  }
345 
347  auto A = AnalysisResults.find(&F);
348  assert(A != AnalysisResults.end() && "Need analysis results for function.");
349  return {A->second.DT, A->second.PDT, DomTreeUpdater::UpdateStrategy::Lazy};
350  }
351 
353  std::function<const TargetLibraryInfo &(Function &)> GetTLI,
354  LLVMContext &Ctx)
355  : DL(DL), GetTLI(GetTLI), Ctx(Ctx) {}
356 
358  // We only track the contents of scalar globals.
359  if (GV->getValueType()->isSingleValueType()) {
360  ValueLatticeElement &IV = TrackedGlobals[GV];
361  if (!isa<UndefValue>(GV->getInitializer()))
362  IV.markConstant(GV->getInitializer());
363  }
364  }
365 
367  // Add an entry, F -> undef.
368  if (auto *STy = dyn_cast<StructType>(F->getReturnType())) {
369  MRVFunctionsTracked.insert(F);
370  for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
371  TrackedMultipleRetVals.insert(
372  std::make_pair(std::make_pair(F, i), ValueLatticeElement()));
373  } else if (!F->getReturnType()->isVoidTy())
374  TrackedRetVals.insert(std::make_pair(F, ValueLatticeElement()));
375  }
376 
378  MustPreserveReturnsInFunctions.insert(F);
379  }
380 
382  return MustPreserveReturnsInFunctions.count(F);
383  }
384 
386  TrackingIncomingArguments.insert(F);
387  }
388 
390  return TrackingIncomingArguments.count(F);
391  }
392 
393  void solve();
394 
395  bool resolvedUndefsIn(Function &F);
396 
398  return BBExecutable.count(BB);
399  }
400 
401  bool isEdgeFeasible(BasicBlock *From, BasicBlock *To) const;
402 
403  std::vector<ValueLatticeElement> getStructLatticeValueFor(Value *V) const {
404  std::vector<ValueLatticeElement> StructValues;
405  auto *STy = dyn_cast<StructType>(V->getType());
406  assert(STy && "getStructLatticeValueFor() can be called only on structs");
407  for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
408  auto I = StructValueState.find(std::make_pair(V, i));
409  assert(I != StructValueState.end() && "Value not in valuemap!");
410  StructValues.push_back(I->second);
411  }
412  return StructValues;
413  }
414 
415  void removeLatticeValueFor(Value *V) { ValueState.erase(V); }
416 
418  assert(!V->getType()->isStructTy() &&
419  "Should use getStructLatticeValueFor");
421  ValueState.find(V);
422  assert(I != ValueState.end() &&
423  "V not found in ValueState nor Paramstate map!");
424  return I->second;
425  }
426 
428  return TrackedRetVals;
429  }
430 
432  return TrackedGlobals;
433  }
434 
436  return MRVFunctionsTracked;
437  }
438 
440  if (auto *STy = dyn_cast<StructType>(V->getType()))
441  for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
442  markOverdefined(getStructValueState(V, i), V);
443  else
444  markOverdefined(ValueState[V], V);
445  }
446 
448 
449  Constant *getConstant(const ValueLatticeElement &LV) const;
450 
452  return TrackingIncomingArguments;
453  }
454 
456 
458  for (auto &BB : *F)
459  BBExecutable.erase(&BB);
460  }
461 };
462 
463 } // namespace llvm
464 
466  if (!BBExecutable.insert(BB).second)
467  return false;
468  LLVM_DEBUG(dbgs() << "Marking Block Executable: " << BB->getName() << '\n');
469  BBWorkList.push_back(BB); // Add the block to the work list!
470  return true;
471 }
472 
473 void SCCPInstVisitor::pushToWorkList(ValueLatticeElement &IV, Value *V) {
474  if (IV.isOverdefined())
475  return OverdefinedInstWorkList.push_back(V);
476  InstWorkList.push_back(V);
477 }
478 
479 void SCCPInstVisitor::pushToWorkListMsg(ValueLatticeElement &IV, Value *V) {
480  LLVM_DEBUG(dbgs() << "updated " << IV << ": " << *V << '\n');
481  pushToWorkList(IV, V);
482 }
483 
484 bool SCCPInstVisitor::markConstant(ValueLatticeElement &IV, Value *V,
485  Constant *C, bool MayIncludeUndef) {
486  if (!IV.markConstant(C, MayIncludeUndef))
487  return false;
488  LLVM_DEBUG(dbgs() << "markConstant: " << *C << ": " << *V << '\n');
489  pushToWorkList(IV, V);
490  return true;
491 }
492 
493 bool SCCPInstVisitor::markOverdefined(ValueLatticeElement &IV, Value *V) {
494  if (!IV.markOverdefined())
495  return false;
496 
497  LLVM_DEBUG(dbgs() << "markOverdefined: ";
498  if (auto *F = dyn_cast<Function>(V)) dbgs()
499  << "Function '" << F->getName() << "'\n";
500  else dbgs() << *V << '\n');
501  // Only instructions go on the work list
502  pushToWorkList(IV, V);
503  return true;
504 }
505 
507  for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
508  const auto &It = TrackedMultipleRetVals.find(std::make_pair(F, i));
509  assert(It != TrackedMultipleRetVals.end());
510  ValueLatticeElement LV = It->second;
511  if (!isConstant(LV))
512  return false;
513  }
514  return true;
515 }
516 
518  if (LV.isConstant())
519  return LV.getConstant();
520 
521  if (LV.isConstantRange()) {
522  const auto &CR = LV.getConstantRange();
523  if (CR.getSingleElement())
524  return ConstantInt::get(Ctx, *CR.getSingleElement());
525  }
526  return nullptr;
527 }
528 
530  Constant *C) {
531  assert(F->arg_size() == A->getParent()->arg_size() &&
532  "Functions should have the same number of arguments");
533 
534  // Mark the argument constant in the new function.
535  markConstant(A, C);
536 
537  // For the remaining arguments in the new function, copy the lattice state
538  // over from the old function.
539  for (auto I = F->arg_begin(), J = A->getParent()->arg_begin(),
540  E = F->arg_end();
541  I != E; ++I, ++J)
542  if (J != A && ValueState.count(I)) {
543  ValueState[J] = ValueState[I];
544  pushToWorkList(ValueState[J], J);
545  }
546 }
547 
548 void SCCPInstVisitor::visitInstruction(Instruction &I) {
549  // All the instructions we don't do any special handling for just
550  // go to overdefined.
551  LLVM_DEBUG(dbgs() << "SCCP: Don't know how to handle: " << I << '\n');
552  markOverdefined(&I);
553 }
554 
555 bool SCCPInstVisitor::mergeInValue(ValueLatticeElement &IV, Value *V,
556  ValueLatticeElement MergeWithV,
558  if (IV.mergeIn(MergeWithV, Opts)) {
559  pushToWorkList(IV, V);
560  LLVM_DEBUG(dbgs() << "Merged " << MergeWithV << " into " << *V << " : "
561  << IV << "\n");
562  return true;
563  }
564  return false;
565 }
566 
567 bool SCCPInstVisitor::markEdgeExecutable(BasicBlock *Source, BasicBlock *Dest) {
568  if (!KnownFeasibleEdges.insert(Edge(Source, Dest)).second)
569  return false; // This edge is already known to be executable!
570 
571  if (!markBlockExecutable(Dest)) {
572  // If the destination is already executable, we just made an *edge*
573  // feasible that wasn't before. Revisit the PHI nodes in the block
574  // because they have potentially new operands.
575  LLVM_DEBUG(dbgs() << "Marking Edge Executable: " << Source->getName()
576  << " -> " << Dest->getName() << '\n');
577 
578  for (PHINode &PN : Dest->phis())
579  visitPHINode(PN);
580  }
581  return true;
582 }
583 
584 // getFeasibleSuccessors - Return a vector of booleans to indicate which
585 // successors are reachable from a given terminator instruction.
586 void SCCPInstVisitor::getFeasibleSuccessors(Instruction &TI,
587  SmallVectorImpl<bool> &Succs) {
588  Succs.resize(TI.getNumSuccessors());
589  if (auto *BI = dyn_cast<BranchInst>(&TI)) {
590  if (BI->isUnconditional()) {
591  Succs[0] = true;
592  return;
593  }
594 
595  ValueLatticeElement BCValue = getValueState(BI->getCondition());
596  ConstantInt *CI = getConstantInt(BCValue);
597  if (!CI) {
598  // Overdefined condition variables, and branches on unfoldable constant
599  // conditions, mean the branch could go either way.
600  if (!BCValue.isUnknownOrUndef())
601  Succs[0] = Succs[1] = true;
602  return;
603  }
604 
605  // Constant condition variables mean the branch can only go a single way.
606  Succs[CI->isZero()] = true;
607  return;
608  }
609 
610  // Unwinding instructions successors are always executable.
611  if (TI.isExceptionalTerminator()) {
612  Succs.assign(TI.getNumSuccessors(), true);
613  return;
614  }
615 
616  if (auto *SI = dyn_cast<SwitchInst>(&TI)) {
617  if (!SI->getNumCases()) {
618  Succs[0] = true;
619  return;
620  }
621  const ValueLatticeElement &SCValue = getValueState(SI->getCondition());
622  if (ConstantInt *CI = getConstantInt(SCValue)) {
623  Succs[SI->findCaseValue(CI)->getSuccessorIndex()] = true;
624  return;
625  }
626 
627  // TODO: Switch on undef is UB. Stop passing false once the rest of LLVM
628  // is ready.
629  if (SCValue.isConstantRange(/*UndefAllowed=*/false)) {
630  const ConstantRange &Range = SCValue.getConstantRange();
631  for (const auto &Case : SI->cases()) {
632  const APInt &CaseValue = Case.getCaseValue()->getValue();
633  if (Range.contains(CaseValue))
634  Succs[Case.getSuccessorIndex()] = true;
635  }
636 
637  // TODO: Determine whether default case is reachable.
638  Succs[SI->case_default()->getSuccessorIndex()] = true;
639  return;
640  }
641 
642  // Overdefined or unknown condition? All destinations are executable!
643  if (!SCValue.isUnknownOrUndef())
644  Succs.assign(TI.getNumSuccessors(), true);
645  return;
646  }
647 
648  // In case of indirect branch and its address is a blockaddress, we mark
649  // the target as executable.
650  if (auto *IBR = dyn_cast<IndirectBrInst>(&TI)) {
651  // Casts are folded by visitCastInst.
652  ValueLatticeElement IBRValue = getValueState(IBR->getAddress());
653  BlockAddress *Addr = dyn_cast_or_null<BlockAddress>(getConstant(IBRValue));
654  if (!Addr) { // Overdefined or unknown condition?
655  // All destinations are executable!
656  if (!IBRValue.isUnknownOrUndef())
657  Succs.assign(TI.getNumSuccessors(), true);
658  return;
659  }
660 
661  BasicBlock *T = Addr->getBasicBlock();
662  assert(Addr->getFunction() == T->getParent() &&
663  "Block address of a different function ?");
664  for (unsigned i = 0; i < IBR->getNumSuccessors(); ++i) {
665  // This is the target.
666  if (IBR->getDestination(i) == T) {
667  Succs[i] = true;
668  return;
669  }
670  }
671 
672  // If we didn't find our destination in the IBR successor list, then we
673  // have undefined behavior. Its ok to assume no successor is executable.
674  return;
675  }
676 
677  // In case of callbr, we pessimistically assume that all successors are
678  // feasible.
679  if (isa<CallBrInst>(&TI)) {
680  Succs.assign(TI.getNumSuccessors(), true);
681  return;
682  }
683 
684  LLVM_DEBUG(dbgs() << "Unknown terminator instruction: " << TI << '\n');
685  llvm_unreachable("SCCP: Don't know how to handle this terminator!");
686 }
687 
688 // isEdgeFeasible - Return true if the control flow edge from the 'From' basic
689 // block to the 'To' basic block is currently feasible.
691  // Check if we've called markEdgeExecutable on the edge yet. (We could
692  // be more aggressive and try to consider edges which haven't been marked
693  // yet, but there isn't any need.)
694  return KnownFeasibleEdges.count(Edge(From, To));
695 }
696 
697 // visit Implementations - Something changed in this instruction, either an
698 // operand made a transition, or the instruction is newly executable. Change
699 // the value type of I to reflect these changes if appropriate. This method
700 // makes sure to do the following actions:
701 //
702 // 1. If a phi node merges two constants in, and has conflicting value coming
703 // from different branches, or if the PHI node merges in an overdefined
704 // value, then the PHI node becomes overdefined.
705 // 2. If a phi node merges only constants in, and they all agree on value, the
706 // PHI node becomes a constant value equal to that.
707 // 3. If V <- x (op) y && isConstant(x) && isConstant(y) V = Constant
708 // 4. If V <- x (op) y && (isOverdefined(x) || isOverdefined(y)) V = Overdefined
709 // 5. If V <- MEM or V <- CALL or V <- (unknown) then V = Overdefined
710 // 6. If a conditional branch has a value that is constant, make the selected
711 // destination executable
712 // 7. If a conditional branch has a value that is overdefined, make all
713 // successors executable.
714 void SCCPInstVisitor::visitPHINode(PHINode &PN) {
715  // If this PN returns a struct, just mark the result overdefined.
716  // TODO: We could do a lot better than this if code actually uses this.
717  if (PN.getType()->isStructTy())
718  return (void)markOverdefined(&PN);
719 
720  if (getValueState(&PN).isOverdefined())
721  return; // Quick exit
722 
723  // Super-extra-high-degree PHI nodes are unlikely to ever be marked constant,
724  // and slow us down a lot. Just mark them overdefined.
725  if (PN.getNumIncomingValues() > 64)
726  return (void)markOverdefined(&PN);
727 
728  unsigned NumActiveIncoming = 0;
729 
730  // Look at all of the executable operands of the PHI node. If any of them
731  // are overdefined, the PHI becomes overdefined as well. If they are all
732  // constant, and they agree with each other, the PHI becomes the identical
733  // constant. If they are constant and don't agree, the PHI is a constant
734  // range. If there are no executable operands, the PHI remains unknown.
735  ValueLatticeElement PhiState = getValueState(&PN);
736  for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) {
737  if (!isEdgeFeasible(PN.getIncomingBlock(i), PN.getParent()))
738  continue;
739 
740  ValueLatticeElement IV = getValueState(PN.getIncomingValue(i));
741  PhiState.mergeIn(IV);
742  NumActiveIncoming++;
743  if (PhiState.isOverdefined())
744  break;
745  }
746 
747  // We allow up to 1 range extension per active incoming value and one
748  // additional extension. Note that we manually adjust the number of range
749  // extensions to match the number of active incoming values. This helps to
750  // limit multiple extensions caused by the same incoming value, if other
751  // incoming values are equal.
752  mergeInValue(&PN, PhiState,
753  ValueLatticeElement::MergeOptions().setMaxWidenSteps(
754  NumActiveIncoming + 1));
755  ValueLatticeElement &PhiStateRef = getValueState(&PN);
756  PhiStateRef.setNumRangeExtensions(
757  std::max(NumActiveIncoming, PhiStateRef.getNumRangeExtensions()));
758 }
759 
760 void SCCPInstVisitor::visitReturnInst(ReturnInst &I) {
761  if (I.getNumOperands() == 0)
762  return; // ret void
763 
764  Function *F = I.getParent()->getParent();
765  Value *ResultOp = I.getOperand(0);
766 
767  // If we are tracking the return value of this function, merge it in.
768  if (!TrackedRetVals.empty() && !ResultOp->getType()->isStructTy()) {
769  auto TFRVI = TrackedRetVals.find(F);
770  if (TFRVI != TrackedRetVals.end()) {
771  mergeInValue(TFRVI->second, F, getValueState(ResultOp));
772  return;
773  }
774  }
775 
776  // Handle functions that return multiple values.
777  if (!TrackedMultipleRetVals.empty()) {
778  if (auto *STy = dyn_cast<StructType>(ResultOp->getType()))
779  if (MRVFunctionsTracked.count(F))
780  for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
781  mergeInValue(TrackedMultipleRetVals[std::make_pair(F, i)], F,
782  getStructValueState(ResultOp, i));
783  }
784 }
785 
786 void SCCPInstVisitor::visitTerminator(Instruction &TI) {
787  SmallVector<bool, 16> SuccFeasible;
788  getFeasibleSuccessors(TI, SuccFeasible);
789 
790  BasicBlock *BB = TI.getParent();
791 
792  // Mark all feasible successors executable.
793  for (unsigned i = 0, e = SuccFeasible.size(); i != e; ++i)
794  if (SuccFeasible[i])
795  markEdgeExecutable(BB, TI.getSuccessor(i));
796 }
797 
798 void SCCPInstVisitor::visitCastInst(CastInst &I) {
799  // ResolvedUndefsIn might mark I as overdefined. Bail out, even if we would
800  // discover a concrete value later.
801  if (ValueState[&I].isOverdefined())
802  return;
803 
804  ValueLatticeElement OpSt = getValueState(I.getOperand(0));
805  if (Constant *OpC = getConstant(OpSt)) {
806  // Fold the constant as we build.
807  Constant *C = ConstantFoldCastOperand(I.getOpcode(), OpC, I.getType(), DL);
808  if (isa<UndefValue>(C))
809  return;
810  // Propagate constant value
811  markConstant(&I, C);
812  } else if (OpSt.isConstantRange() && I.getDestTy()->isIntegerTy()) {
813  auto &LV = getValueState(&I);
814  ConstantRange OpRange = OpSt.getConstantRange();
815  Type *DestTy = I.getDestTy();
816  // Vectors where all elements have the same known constant range are treated
817  // as a single constant range in the lattice. When bitcasting such vectors,
818  // there is a mis-match between the width of the lattice value (single
819  // constant range) and the original operands (vector). Go to overdefined in
820  // that case.
821  if (I.getOpcode() == Instruction::BitCast &&
822  I.getOperand(0)->getType()->isVectorTy() &&
823  OpRange.getBitWidth() < DL.getTypeSizeInBits(DestTy))
824  return (void)markOverdefined(&I);
825 
826  ConstantRange Res =
827  OpRange.castOp(I.getOpcode(), DL.getTypeSizeInBits(DestTy));
828  mergeInValue(LV, &I, ValueLatticeElement::getRange(Res));
829  } else if (!OpSt.isUnknownOrUndef())
830  markOverdefined(&I);
831 }
832 
833 void SCCPInstVisitor::visitExtractValueInst(ExtractValueInst &EVI) {
834  // If this returns a struct, mark all elements over defined, we don't track
835  // structs in structs.
836  if (EVI.getType()->isStructTy())
837  return (void)markOverdefined(&EVI);
838 
839  // resolvedUndefsIn might mark I as overdefined. Bail out, even if we would
840  // discover a concrete value later.
841  if (ValueState[&EVI].isOverdefined())
842  return (void)markOverdefined(&EVI);
843 
844  // If this is extracting from more than one level of struct, we don't know.
845  if (EVI.getNumIndices() != 1)
846  return (void)markOverdefined(&EVI);
847 
848  Value *AggVal = EVI.getAggregateOperand();
849  if (AggVal->getType()->isStructTy()) {
850  unsigned i = *EVI.idx_begin();
851  ValueLatticeElement EltVal = getStructValueState(AggVal, i);
852  mergeInValue(getValueState(&EVI), &EVI, EltVal);
853  } else {
854  // Otherwise, must be extracting from an array.
855  return (void)markOverdefined(&EVI);
856  }
857 }
858 
859 void SCCPInstVisitor::visitInsertValueInst(InsertValueInst &IVI) {
860  auto *STy = dyn_cast<StructType>(IVI.getType());
861  if (!STy)
862  return (void)markOverdefined(&IVI);
863 
864  // resolvedUndefsIn might mark I as overdefined. Bail out, even if we would
865  // discover a concrete value later.
866  if (isOverdefined(ValueState[&IVI]))
867  return (void)markOverdefined(&IVI);
868 
869  // If this has more than one index, we can't handle it, drive all results to
870  // undef.
871  if (IVI.getNumIndices() != 1)
872  return (void)markOverdefined(&IVI);
873 
874  Value *Aggr = IVI.getAggregateOperand();
875  unsigned Idx = *IVI.idx_begin();
876 
877  // Compute the result based on what we're inserting.
878  for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
879  // This passes through all values that aren't the inserted element.
880  if (i != Idx) {
881  ValueLatticeElement EltVal = getStructValueState(Aggr, i);
882  mergeInValue(getStructValueState(&IVI, i), &IVI, EltVal);
883  continue;
884  }
885 
886  Value *Val = IVI.getInsertedValueOperand();
887  if (Val->getType()->isStructTy())
888  // We don't track structs in structs.
889  markOverdefined(getStructValueState(&IVI, i), &IVI);
890  else {
891  ValueLatticeElement InVal = getValueState(Val);
892  mergeInValue(getStructValueState(&IVI, i), &IVI, InVal);
893  }
894  }
895 }
896 
897 void SCCPInstVisitor::visitSelectInst(SelectInst &I) {
898  // If this select returns a struct, just mark the result overdefined.
899  // TODO: We could do a lot better than this if code actually uses this.
900  if (I.getType()->isStructTy())
901  return (void)markOverdefined(&I);
902 
903  // resolvedUndefsIn might mark I as overdefined. Bail out, even if we would
904  // discover a concrete value later.
905  if (ValueState[&I].isOverdefined())
906  return (void)markOverdefined(&I);
907 
908  ValueLatticeElement CondValue = getValueState(I.getCondition());
909  if (CondValue.isUnknownOrUndef())
910  return;
911 
912  if (ConstantInt *CondCB = getConstantInt(CondValue)) {
913  Value *OpVal = CondCB->isZero() ? I.getFalseValue() : I.getTrueValue();
914  mergeInValue(&I, getValueState(OpVal));
915  return;
916  }
917 
918  // Otherwise, the condition is overdefined or a constant we can't evaluate.
919  // See if we can produce something better than overdefined based on the T/F
920  // value.
921  ValueLatticeElement TVal = getValueState(I.getTrueValue());
922  ValueLatticeElement FVal = getValueState(I.getFalseValue());
923 
924  bool Changed = ValueState[&I].mergeIn(TVal);
925  Changed |= ValueState[&I].mergeIn(FVal);
926  if (Changed)
927  pushToWorkListMsg(ValueState[&I], &I);
928 }
929 
930 // Handle Unary Operators.
931 void SCCPInstVisitor::visitUnaryOperator(Instruction &I) {
932  ValueLatticeElement V0State = getValueState(I.getOperand(0));
933 
934  ValueLatticeElement &IV = ValueState[&I];
935  // resolvedUndefsIn might mark I as overdefined. Bail out, even if we would
936  // discover a concrete value later.
937  if (isOverdefined(IV))
938  return (void)markOverdefined(&I);
939 
940  if (isConstant(V0State)) {
941  Constant *C = ConstantExpr::get(I.getOpcode(), getConstant(V0State));
942 
943  // op Y -> undef.
944  if (isa<UndefValue>(C))
945  return;
946  return (void)markConstant(IV, &I, C);
947  }
948 
949  // If something is undef, wait for it to resolve.
950  if (!isOverdefined(V0State))
951  return;
952 
953  markOverdefined(&I);
954 }
955 
956 // Handle Binary Operators.
957 void SCCPInstVisitor::visitBinaryOperator(Instruction &I) {
958  ValueLatticeElement V1State = getValueState(I.getOperand(0));
959  ValueLatticeElement V2State = getValueState(I.getOperand(1));
960 
961  ValueLatticeElement &IV = ValueState[&I];
962  if (IV.isOverdefined())
963  return;
964 
965  // If something is undef, wait for it to resolve.
966  if (V1State.isUnknownOrUndef() || V2State.isUnknownOrUndef())
967  return;
968 
969  if (V1State.isOverdefined() && V2State.isOverdefined())
970  return (void)markOverdefined(&I);
971 
972  // If either of the operands is a constant, try to fold it to a constant.
973  // TODO: Use information from notconstant better.
974  if ((V1State.isConstant() || V2State.isConstant())) {
975  Value *V1 = isConstant(V1State) ? getConstant(V1State) : I.getOperand(0);
976  Value *V2 = isConstant(V2State) ? getConstant(V2State) : I.getOperand(1);
977  Value *R = SimplifyBinOp(I.getOpcode(), V1, V2, SimplifyQuery(DL));
978  auto *C = dyn_cast_or_null<Constant>(R);
979  if (C) {
980  // X op Y -> undef.
981  if (isa<UndefValue>(C))
982  return;
983  // Conservatively assume that the result may be based on operands that may
984  // be undef. Note that we use mergeInValue to combine the constant with
985  // the existing lattice value for I, as different constants might be found
986  // after one of the operands go to overdefined, e.g. due to one operand
987  // being a special floating value.
988  ValueLatticeElement NewV;
989  NewV.markConstant(C, /*MayIncludeUndef=*/true);
990  return (void)mergeInValue(&I, NewV);
991  }
992  }
993 
994  // Only use ranges for binary operators on integers.
995  if (!I.getType()->isIntegerTy())
996  return markOverdefined(&I);
997 
998  // Try to simplify to a constant range.
999  ConstantRange A = ConstantRange::getFull(I.getType()->getScalarSizeInBits());
1000  ConstantRange B = ConstantRange::getFull(I.getType()->getScalarSizeInBits());
1001  if (V1State.isConstantRange())
1002  A = V1State.getConstantRange();
1003  if (V2State.isConstantRange())
1004  B = V2State.getConstantRange();
1005 
1006  ConstantRange R = A.binaryOp(cast<BinaryOperator>(&I)->getOpcode(), B);
1007  mergeInValue(&I, ValueLatticeElement::getRange(R));
1008 
1009  // TODO: Currently we do not exploit special values that produce something
1010  // better than overdefined with an overdefined operand for vector or floating
1011  // point types, like and <4 x i32> overdefined, zeroinitializer.
1012 }
1013 
1014 // Handle ICmpInst instruction.
1015 void SCCPInstVisitor::visitCmpInst(CmpInst &I) {
1016  // Do not cache this lookup, getValueState calls later in the function might
1017  // invalidate the reference.
1018  if (isOverdefined(ValueState[&I]))
1019  return (void)markOverdefined(&I);
1020 
1021  Value *Op1 = I.getOperand(0);
1022  Value *Op2 = I.getOperand(1);
1023 
1024  // For parameters, use ParamState which includes constant range info if
1025  // available.
1026  auto V1State = getValueState(Op1);
1027  auto V2State = getValueState(Op2);
1028 
1029  Constant *C = V1State.getCompare(I.getPredicate(), I.getType(), V2State);
1030  if (C) {
1031  if (isa<UndefValue>(C))
1032  return;
1034  CV.markConstant(C);
1035  mergeInValue(&I, CV);
1036  return;
1037  }
1038 
1039  // If operands are still unknown, wait for it to resolve.
1040  if ((V1State.isUnknownOrUndef() || V2State.isUnknownOrUndef()) &&
1041  !isConstant(ValueState[&I]))
1042  return;
1043 
1044  markOverdefined(&I);
1045 }
1046 
1047 // Handle getelementptr instructions. If all operands are constants then we
1048 // can turn this into a getelementptr ConstantExpr.
1049 void SCCPInstVisitor::visitGetElementPtrInst(GetElementPtrInst &I) {
1050  if (isOverdefined(ValueState[&I]))
1051  return (void)markOverdefined(&I);
1052 
1054  Operands.reserve(I.getNumOperands());
1055 
1056  for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) {
1057  ValueLatticeElement State = getValueState(I.getOperand(i));
1058  if (State.isUnknownOrUndef())
1059  return; // Operands are not resolved yet.
1060 
1061  if (isOverdefined(State))
1062  return (void)markOverdefined(&I);
1063 
1064  if (Constant *C = getConstant(State)) {
1065  Operands.push_back(C);
1066  continue;
1067  }
1068 
1069  return (void)markOverdefined(&I);
1070  }
1071 
1072  Constant *Ptr = Operands[0];
1073  auto Indices = makeArrayRef(Operands.begin() + 1, Operands.end());
1074  Constant *C =
1075  ConstantExpr::getGetElementPtr(I.getSourceElementType(), Ptr, Indices);
1076  if (isa<UndefValue>(C))
1077  return;
1078  markConstant(&I, C);
1079 }
1080 
1081 void SCCPInstVisitor::visitStoreInst(StoreInst &SI) {
1082  // If this store is of a struct, ignore it.
1083  if (SI.getOperand(0)->getType()->isStructTy())
1084  return;
1085 
1086  if (TrackedGlobals.empty() || !isa<GlobalVariable>(SI.getOperand(1)))
1087  return;
1088 
1089  GlobalVariable *GV = cast<GlobalVariable>(SI.getOperand(1));
1090  auto I = TrackedGlobals.find(GV);
1091  if (I == TrackedGlobals.end())
1092  return;
1093 
1094  // Get the value we are storing into the global, then merge it.
1095  mergeInValue(I->second, GV, getValueState(SI.getOperand(0)),
1097  if (I->second.isOverdefined())
1098  TrackedGlobals.erase(I); // No need to keep tracking this!
1099 }
1100 
1102  if (MDNode *Ranges = I->getMetadata(LLVMContext::MD_range))
1103  if (I->getType()->isIntegerTy())
1105  getConstantRangeFromMetadata(*Ranges));
1106  if (I->hasMetadata(LLVMContext::MD_nonnull))
1108  ConstantPointerNull::get(cast<PointerType>(I->getType())));
1110 }
1111 
1112 // Handle load instructions. If the operand is a constant pointer to a constant
1113 // global, we can replace the load with the loaded constant value!
1114 void SCCPInstVisitor::visitLoadInst(LoadInst &I) {
1115  // If this load is of a struct or the load is volatile, just mark the result
1116  // as overdefined.
1117  if (I.getType()->isStructTy() || I.isVolatile())
1118  return (void)markOverdefined(&I);
1119 
1120  // resolvedUndefsIn might mark I as overdefined. Bail out, even if we would
1121  // discover a concrete value later.
1122  if (ValueState[&I].isOverdefined())
1123  return (void)markOverdefined(&I);
1124 
1125  ValueLatticeElement PtrVal = getValueState(I.getOperand(0));
1126  if (PtrVal.isUnknownOrUndef())
1127  return; // The pointer is not resolved yet!
1128 
1129  ValueLatticeElement &IV = ValueState[&I];
1130 
1131  if (isConstant(PtrVal)) {
1132  Constant *Ptr = getConstant(PtrVal);
1133 
1134  // load null is undefined.
1135  if (isa<ConstantPointerNull>(Ptr)) {
1136  if (NullPointerIsDefined(I.getFunction(), I.getPointerAddressSpace()))
1137  return (void)markOverdefined(IV, &I);
1138  else
1139  return;
1140  }
1141 
1142  // Transform load (constant global) into the value loaded.
1143  if (auto *GV = dyn_cast<GlobalVariable>(Ptr)) {
1144  if (!TrackedGlobals.empty()) {
1145  // If we are tracking this global, merge in the known value for it.
1146  auto It = TrackedGlobals.find(GV);
1147  if (It != TrackedGlobals.end()) {
1148  mergeInValue(IV, &I, It->second, getMaxWidenStepsOpts());
1149  return;
1150  }
1151  }
1152  }
1153 
1154  // Transform load from a constant into a constant if possible.
1155  if (Constant *C = ConstantFoldLoadFromConstPtr(Ptr, I.getType(), DL)) {
1156  if (isa<UndefValue>(C))
1157  return;
1158  return (void)markConstant(IV, &I, C);
1159  }
1160  }
1161 
1162  // Fall back to metadata.
1163  mergeInValue(&I, getValueFromMetadata(&I));
1164 }
1165 
1166 void SCCPInstVisitor::visitCallBase(CallBase &CB) {
1167  handleCallResult(CB);
1168  handleCallArguments(CB);
1169 }
1170 
1171 void SCCPInstVisitor::handleCallOverdefined(CallBase &CB) {
1172  Function *F = CB.getCalledFunction();
1173 
1174  // Void return and not tracking callee, just bail.
1175  if (CB.getType()->isVoidTy())
1176  return;
1177 
1178  // Always mark struct return as overdefined.
1179  if (CB.getType()->isStructTy())
1180  return (void)markOverdefined(&CB);
1181 
1182  // Otherwise, if we have a single return value case, and if the function is
1183  // a declaration, maybe we can constant fold it.
1184  if (F && F->isDeclaration() && canConstantFoldCallTo(&CB, F)) {
1186  for (auto AI = CB.arg_begin(), E = CB.arg_end(); AI != E; ++AI) {
1187  if (AI->get()->getType()->isStructTy())
1188  return markOverdefined(&CB); // Can't handle struct args.
1189  ValueLatticeElement State = getValueState(*AI);
1190 
1191  if (State.isUnknownOrUndef())
1192  return; // Operands are not resolved yet.
1193  if (isOverdefined(State))
1194  return (void)markOverdefined(&CB);
1195  assert(isConstant(State) && "Unknown state!");
1196  Operands.push_back(getConstant(State));
1197  }
1198 
1199  if (isOverdefined(getValueState(&CB)))
1200  return (void)markOverdefined(&CB);
1201 
1202  // If we can constant fold this, mark the result of the call as a
1203  // constant.
1204  if (Constant *C = ConstantFoldCall(&CB, F, Operands, &GetTLI(*F))) {
1205  // call -> undef.
1206  if (isa<UndefValue>(C))
1207  return;
1208  return (void)markConstant(&CB, C);
1209  }
1210  }
1211 
1212  // Fall back to metadata.
1213  mergeInValue(&CB, getValueFromMetadata(&CB));
1214 }
1215 
1216 void SCCPInstVisitor::handleCallArguments(CallBase &CB) {
1217  Function *F = CB.getCalledFunction();
1218  // If this is a local function that doesn't have its address taken, mark its
1219  // entry block executable and merge in the actual arguments to the call into
1220  // the formal arguments of the function.
1221  if (!TrackingIncomingArguments.empty() &&
1222  TrackingIncomingArguments.count(F)) {
1223  markBlockExecutable(&F->front());
1224 
1225  // Propagate information from this call site into the callee.
1226  auto CAI = CB.arg_begin();
1227  for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end(); AI != E;
1228  ++AI, ++CAI) {
1229  // If this argument is byval, and if the function is not readonly, there
1230  // will be an implicit copy formed of the input aggregate.
1231  if (AI->hasByValAttr() && !F->onlyReadsMemory()) {
1232  markOverdefined(&*AI);
1233  continue;
1234  }
1235 
1236  if (auto *STy = dyn_cast<StructType>(AI->getType())) {
1237  for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
1238  ValueLatticeElement CallArg = getStructValueState(*CAI, i);
1239  mergeInValue(getStructValueState(&*AI, i), &*AI, CallArg,
1241  }
1242  } else
1243  mergeInValue(&*AI, getValueState(*CAI), getMaxWidenStepsOpts());
1244  }
1245  }
1246 }
1247 
1248 void SCCPInstVisitor::handleCallResult(CallBase &CB) {
1249  Function *F = CB.getCalledFunction();
1250 
1251  if (auto *II = dyn_cast<IntrinsicInst>(&CB)) {
1252  if (II->getIntrinsicID() == Intrinsic::ssa_copy) {
1253  if (ValueState[&CB].isOverdefined())
1254  return;
1255 
1256  Value *CopyOf = CB.getOperand(0);
1257  ValueLatticeElement CopyOfVal = getValueState(CopyOf);
1258  const auto *PI = getPredicateInfoFor(&CB);
1259  assert(PI && "Missing predicate info for ssa.copy");
1260 
1261  const Optional<PredicateConstraint> &Constraint = PI->getConstraint();
1262  if (!Constraint) {
1263  mergeInValue(ValueState[&CB], &CB, CopyOfVal);
1264  return;
1265  }
1266 
1267  CmpInst::Predicate Pred = Constraint->Predicate;
1268  Value *OtherOp = Constraint->OtherOp;
1269 
1270  // Wait until OtherOp is resolved.
1271  if (getValueState(OtherOp).isUnknown()) {
1272  addAdditionalUser(OtherOp, &CB);
1273  return;
1274  }
1275 
1276  // TODO: Actually filp MayIncludeUndef for the created range to false,
1277  // once most places in the optimizer respect the branches on
1278  // undef/poison are UB rule. The reason why the new range cannot be
1279  // undef is as follows below:
1280  // The new range is based on a branch condition. That guarantees that
1281  // neither of the compare operands can be undef in the branch targets,
1282  // unless we have conditions that are always true/false (e.g. icmp ule
1283  // i32, %a, i32_max). For the latter overdefined/empty range will be
1284  // inferred, but the branch will get folded accordingly anyways.
1285  bool MayIncludeUndef = !isa<PredicateAssume>(PI);
1286 
1287  ValueLatticeElement CondVal = getValueState(OtherOp);
1288  ValueLatticeElement &IV = ValueState[&CB];
1289  if (CondVal.isConstantRange() || CopyOfVal.isConstantRange()) {
1290  auto ImposedCR =
1291  ConstantRange::getFull(DL.getTypeSizeInBits(CopyOf->getType()));
1292 
1293  // Get the range imposed by the condition.
1294  if (CondVal.isConstantRange())
1296  Pred, CondVal.getConstantRange());
1297 
1298  // Combine range info for the original value with the new range from the
1299  // condition.
1300  auto CopyOfCR = CopyOfVal.isConstantRange()
1301  ? CopyOfVal.getConstantRange()
1302  : ConstantRange::getFull(
1303  DL.getTypeSizeInBits(CopyOf->getType()));
1304  auto NewCR = ImposedCR.intersectWith(CopyOfCR);
1305  // If the existing information is != x, do not use the information from
1306  // a chained predicate, as the != x information is more likely to be
1307  // helpful in practice.
1308  if (!CopyOfCR.contains(NewCR) && CopyOfCR.getSingleMissingElement())
1309  NewCR = CopyOfCR;
1310 
1311  addAdditionalUser(OtherOp, &CB);
1312  mergeInValue(IV, &CB,
1313  ValueLatticeElement::getRange(NewCR, MayIncludeUndef));
1314  return;
1315  } else if (Pred == CmpInst::ICMP_EQ && CondVal.isConstant()) {
1316  // For non-integer values or integer constant expressions, only
1317  // propagate equal constants.
1318  addAdditionalUser(OtherOp, &CB);
1319  mergeInValue(IV, &CB, CondVal);
1320  return;
1321  } else if (Pred == CmpInst::ICMP_NE && CondVal.isConstant() &&
1322  !MayIncludeUndef) {
1323  // Propagate inequalities.
1324  addAdditionalUser(OtherOp, &CB);
1325  mergeInValue(IV, &CB,
1327  return;
1328  }
1329 
1330  return (void)mergeInValue(IV, &CB, CopyOfVal);
1331  }
1332 
1333  if (ConstantRange::isIntrinsicSupported(II->getIntrinsicID())) {
1334  // Compute result range for intrinsics supported by ConstantRange.
1335  // Do this even if we don't know a range for all operands, as we may
1336  // still know something about the result range, e.g. of abs(x).
1338  for (Value *Op : II->args()) {
1339  const ValueLatticeElement &State = getValueState(Op);
1340  if (State.isConstantRange())
1341  OpRanges.push_back(State.getConstantRange());
1342  else
1343  OpRanges.push_back(
1344  ConstantRange::getFull(Op->getType()->getScalarSizeInBits()));
1345  }
1346 
1348  ConstantRange::intrinsic(II->getIntrinsicID(), OpRanges);
1349  return (void)mergeInValue(II, ValueLatticeElement::getRange(Result));
1350  }
1351  }
1352 
1353  // The common case is that we aren't tracking the callee, either because we
1354  // are not doing interprocedural analysis or the callee is indirect, or is
1355  // external. Handle these cases first.
1356  if (!F || F->isDeclaration())
1357  return handleCallOverdefined(CB);
1358 
1359  // If this is a single/zero retval case, see if we're tracking the function.
1360  if (auto *STy = dyn_cast<StructType>(F->getReturnType())) {
1361  if (!MRVFunctionsTracked.count(F))
1362  return handleCallOverdefined(CB); // Not tracking this callee.
1363 
1364  // If we are tracking this callee, propagate the result of the function
1365  // into this call site.
1366  for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
1367  mergeInValue(getStructValueState(&CB, i), &CB,
1368  TrackedMultipleRetVals[std::make_pair(F, i)],
1370  } else {
1371  auto TFRVI = TrackedRetVals.find(F);
1372  if (TFRVI == TrackedRetVals.end())
1373  return handleCallOverdefined(CB); // Not tracking this callee.
1374 
1375  // If so, propagate the return value of the callee into this call result.
1376  mergeInValue(&CB, TFRVI->second, getMaxWidenStepsOpts());
1377  }
1378 }
1379 
1381  // Process the work lists until they are empty!
1382  while (!BBWorkList.empty() || !InstWorkList.empty() ||
1383  !OverdefinedInstWorkList.empty()) {
1384  // Process the overdefined instruction's work list first, which drives other
1385  // things to overdefined more quickly.
1386  while (!OverdefinedInstWorkList.empty()) {
1387  Value *I = OverdefinedInstWorkList.pop_back_val();
1388 
1389  LLVM_DEBUG(dbgs() << "\nPopped off OI-WL: " << *I << '\n');
1390 
1391  // "I" got into the work list because it either made the transition from
1392  // bottom to constant, or to overdefined.
1393  //
1394  // Anything on this worklist that is overdefined need not be visited
1395  // since all of its users will have already been marked as overdefined
1396  // Update all of the users of this instruction's value.
1397  //
1398  markUsersAsChanged(I);
1399  }
1400 
1401  // Process the instruction work list.
1402  while (!InstWorkList.empty()) {
1403  Value *I = InstWorkList.pop_back_val();
1404 
1405  LLVM_DEBUG(dbgs() << "\nPopped off I-WL: " << *I << '\n');
1406 
1407  // "I" got into the work list because it made the transition from undef to
1408  // constant.
1409  //
1410  // Anything on this worklist that is overdefined need not be visited
1411  // since all of its users will have already been marked as overdefined.
1412  // Update all of the users of this instruction's value.
1413  //
1414  if (I->getType()->isStructTy() || !getValueState(I).isOverdefined())
1415  markUsersAsChanged(I);
1416  }
1417 
1418  // Process the basic block work list.
1419  while (!BBWorkList.empty()) {
1420  BasicBlock *BB = BBWorkList.pop_back_val();
1421 
1422  LLVM_DEBUG(dbgs() << "\nPopped off BBWL: " << *BB << '\n');
1423 
1424  // Notify all instructions in this basic block that they are newly
1425  // executable.
1426  visit(BB);
1427  }
1428  }
1429 }
1430 
1431 /// resolvedUndefsIn - While solving the dataflow for a function, we assume
1432 /// that branches on undef values cannot reach any of their successors.
1433 /// However, this is not a safe assumption. After we solve dataflow, this
1434 /// method should be use to handle this. If this returns true, the solver
1435 /// should be rerun.
1436 ///
1437 /// This method handles this by finding an unresolved branch and marking it one
1438 /// of the edges from the block as being feasible, even though the condition
1439 /// doesn't say it would otherwise be. This allows SCCP to find the rest of the
1440 /// CFG and only slightly pessimizes the analysis results (by marking one,
1441 /// potentially infeasible, edge feasible). This cannot usefully modify the
1442 /// constraints on the condition of the branch, as that would impact other users
1443 /// of the value.
1444 ///
1445 /// This scan also checks for values that use undefs. It conservatively marks
1446 /// them as overdefined.
1448  bool MadeChange = false;
1449  for (BasicBlock &BB : F) {
1450  if (!BBExecutable.count(&BB))
1451  continue;
1452 
1453  for (Instruction &I : BB) {
1454  // Look for instructions which produce undef values.
1455  if (I.getType()->isVoidTy())
1456  continue;
1457 
1458  if (auto *STy = dyn_cast<StructType>(I.getType())) {
1459  // Only a few things that can be structs matter for undef.
1460 
1461  // Tracked calls must never be marked overdefined in resolvedUndefsIn.
1462  if (auto *CB = dyn_cast<CallBase>(&I))
1463  if (Function *F = CB->getCalledFunction())
1464  if (MRVFunctionsTracked.count(F))
1465  continue;
1466 
1467  // extractvalue and insertvalue don't need to be marked; they are
1468  // tracked as precisely as their operands.
1469  if (isa<ExtractValueInst>(I) || isa<InsertValueInst>(I))
1470  continue;
1471  // Send the results of everything else to overdefined. We could be
1472  // more precise than this but it isn't worth bothering.
1473  for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
1474  ValueLatticeElement &LV = getStructValueState(&I, i);
1475  if (LV.isUnknownOrUndef()) {
1476  markOverdefined(LV, &I);
1477  MadeChange = true;
1478  }
1479  }
1480  continue;
1481  }
1482 
1483  ValueLatticeElement &LV = getValueState(&I);
1484  if (!LV.isUnknownOrUndef())
1485  continue;
1486 
1487  // There are two reasons a call can have an undef result
1488  // 1. It could be tracked.
1489  // 2. It could be constant-foldable.
1490  // Because of the way we solve return values, tracked calls must
1491  // never be marked overdefined in resolvedUndefsIn.
1492  if (auto *CB = dyn_cast<CallBase>(&I))
1493  if (Function *F = CB->getCalledFunction())
1494  if (TrackedRetVals.count(F))
1495  continue;
1496 
1497  if (isa<LoadInst>(I)) {
1498  // A load here means one of two things: a load of undef from a global,
1499  // a load from an unknown pointer. Either way, having it return undef
1500  // is okay.
1501  continue;
1502  }
1503 
1504  markOverdefined(&I);
1505  MadeChange = true;
1506  }
1507 
1508  // Check to see if we have a branch or switch on an undefined value. If so
1509  // we force the branch to go one way or the other to make the successor
1510  // values live. It doesn't really matter which way we force it.
1511  Instruction *TI = BB.getTerminator();
1512  if (auto *BI = dyn_cast<BranchInst>(TI)) {
1513  if (!BI->isConditional())
1514  continue;
1515  if (!getValueState(BI->getCondition()).isUnknownOrUndef())
1516  continue;
1517 
1518  // If the input to SCCP is actually branch on undef, fix the undef to
1519  // false.
1520  if (isa<UndefValue>(BI->getCondition())) {
1521  BI->setCondition(ConstantInt::getFalse(BI->getContext()));
1522  markEdgeExecutable(&BB, TI->getSuccessor(1));
1523  MadeChange = true;
1524  continue;
1525  }
1526 
1527  // Otherwise, it is a branch on a symbolic value which is currently
1528  // considered to be undef. Make sure some edge is executable, so a
1529  // branch on "undef" always flows somewhere.
1530  // FIXME: Distinguish between dead code and an LLVM "undef" value.
1531  BasicBlock *DefaultSuccessor = TI->getSuccessor(1);
1532  if (markEdgeExecutable(&BB, DefaultSuccessor))
1533  MadeChange = true;
1534 
1535  continue;
1536  }
1537 
1538  if (auto *IBR = dyn_cast<IndirectBrInst>(TI)) {
1539  // Indirect branch with no successor ?. Its ok to assume it branches
1540  // to no target.
1541  if (IBR->getNumSuccessors() < 1)
1542  continue;
1543 
1544  if (!getValueState(IBR->getAddress()).isUnknownOrUndef())
1545  continue;
1546 
1547  // If the input to SCCP is actually branch on undef, fix the undef to
1548  // the first successor of the indirect branch.
1549  if (isa<UndefValue>(IBR->getAddress())) {
1550  IBR->setAddress(BlockAddress::get(IBR->getSuccessor(0)));
1551  markEdgeExecutable(&BB, IBR->getSuccessor(0));
1552  MadeChange = true;
1553  continue;
1554  }
1555 
1556  // Otherwise, it is a branch on a symbolic value which is currently
1557  // considered to be undef. Make sure some edge is executable, so a
1558  // branch on "undef" always flows somewhere.
1559  // FIXME: IndirectBr on "undef" doesn't actually need to go anywhere:
1560  // we can assume the branch has undefined behavior instead.
1561  BasicBlock *DefaultSuccessor = IBR->getSuccessor(0);
1562  if (markEdgeExecutable(&BB, DefaultSuccessor))
1563  MadeChange = true;
1564 
1565  continue;
1566  }
1567 
1568  if (auto *SI = dyn_cast<SwitchInst>(TI)) {
1569  if (!SI->getNumCases() ||
1570  !getValueState(SI->getCondition()).isUnknownOrUndef())
1571  continue;
1572 
1573  // If the input to SCCP is actually switch on undef, fix the undef to
1574  // the first constant.
1575  if (isa<UndefValue>(SI->getCondition())) {
1576  SI->setCondition(SI->case_begin()->getCaseValue());
1577  markEdgeExecutable(&BB, SI->case_begin()->getCaseSuccessor());
1578  MadeChange = true;
1579  continue;
1580  }
1581 
1582  // Otherwise, it is a branch on a symbolic value which is currently
1583  // considered to be undef. Make sure some edge is executable, so a
1584  // branch on "undef" always flows somewhere.
1585  // FIXME: Distinguish between dead code and an LLVM "undef" value.
1586  BasicBlock *DefaultSuccessor = SI->case_begin()->getCaseSuccessor();
1587  if (markEdgeExecutable(&BB, DefaultSuccessor))
1588  MadeChange = true;
1589 
1590  continue;
1591  }
1592  }
1593 
1594  return MadeChange;
1595 }
1596 
1597 //===----------------------------------------------------------------------===//
1598 //
1599 // SCCPSolver implementations
1600 //
1602  const DataLayout &DL,
1603  std::function<const TargetLibraryInfo &(Function &)> GetTLI,
1604  LLVMContext &Ctx)
1605  : Visitor(new SCCPInstVisitor(DL, std::move(GetTLI), Ctx)) {}
1606 
1608 
1610  return Visitor->addAnalysis(F, std::move(A));
1611 }
1612 
1614  return Visitor->markBlockExecutable(BB);
1615 }
1616 
1618  return Visitor->getPredicateInfoFor(I);
1619 }
1620 
1621 DomTreeUpdater SCCPSolver::getDTU(Function &F) { return Visitor->getDTU(F); }
1622 
1624  Visitor->trackValueOfGlobalVariable(GV);
1625 }
1626 
1628  Visitor->addTrackedFunction(F);
1629 }
1630 
1632  Visitor->addToMustPreserveReturnsInFunctions(F);
1633 }
1634 
1636  return Visitor->mustPreserveReturn(F);
1637 }
1638 
1640  Visitor->addArgumentTrackedFunction(F);
1641 }
1642 
1644  return Visitor->isArgumentTrackedFunction(F);
1645 }
1646 
1647 void SCCPSolver::solve() { Visitor->solve(); }
1648 
1650  return Visitor->resolvedUndefsIn(F);
1651 }
1652 
1654  return Visitor->isBlockExecutable(BB);
1655 }
1656 
1658  return Visitor->isEdgeFeasible(From, To);
1659 }
1660 
1661 std::vector<ValueLatticeElement>
1663  return Visitor->getStructLatticeValueFor(V);
1664 }
1665 
1667  return Visitor->removeLatticeValueFor(V);
1668 }
1669 
1671  return Visitor->getLatticeValueFor(V);
1672 }
1673 
1676  return Visitor->getTrackedRetVals();
1677 }
1678 
1681  return Visitor->getTrackedGlobals();
1682 }
1683 
1685  return Visitor->getMRVFunctionsTracked();
1686 }
1687 
1688 void SCCPSolver::markOverdefined(Value *V) { Visitor->markOverdefined(V); }
1689 
1691  return Visitor->isStructLatticeConstant(F, STy);
1692 }
1693 
1695  return Visitor->getConstant(LV);
1696 }
1697 
1699  return Visitor->getArgumentTrackedFunctions();
1700 }
1701 
1703  Constant *C) {
1704  Visitor->markArgInFuncSpecialization(F, A, C);
1705 }
1706 
1708  Visitor->markFunctionUnreachable(F);
1709 }
1710 
1711 void SCCPSolver::visit(Instruction *I) { Visitor->visit(I); }
1712 
1713 void SCCPSolver::visitCall(CallInst &I) { Visitor->visitCall(I); }
llvm::ValueLatticeElement::getNot
static ValueLatticeElement getNot(Constant *C)
Definition: ValueLattice.h:209
i
i
Definition: README.txt:29
llvm::SCCPInstVisitor::removeLatticeValueFor
void removeLatticeValueFor(Value *V)
Definition: SCCPSolver.cpp:415
llvm::ValueLatticeElement::MergeOptions::setMaxWidenSteps
MergeOptions & setMaxWidenSteps(unsigned Steps=1)
Definition: ValueLattice.h:138
llvm::Argument
This class represents an incoming formal argument to a Function.
Definition: Argument.h:29
llvm::ValueLatticeElement::getConstantRange
const ConstantRange & getConstantRange(bool UndefAllowed=true) const
Returns the constant range for this value.
Definition: ValueLattice.h:270
llvm::ValueLatticeElement::isConstant
bool isConstant() const
Definition: ValueLattice.h:241
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::CmpInst::ICMP_EQ
@ ICMP_EQ
equal
Definition: InstrTypes.h:741
llvm::ReturnInst
Return a value (possibly void), from a function.
Definition: Instructions.h:2978
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:112
llvm::SCCPInstVisitor::getLatticeValueFor
const ValueLatticeElement & getLatticeValueFor(Value *V) const
Definition: SCCPSolver.cpp:417
llvm::SCCPInstVisitor::getDTU
DomTreeUpdater getDTU(Function &F)
Definition: SCCPSolver.cpp:346
llvm::CmpInst::Predicate
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:720
llvm::SimplifyQuery
Definition: InstructionSimplify.h:94
llvm::AnalysisResultsForFn
Helper struct for bundling up the analysis results per function for IPSCCP.
Definition: SCCPSolver.h:31
llvm::ValueLatticeElement::getConstant
Constant * getConstant() const
Definition: ValueLattice.h:256
llvm::Function
Definition: Function.h:61
Pass.h
llvm::SCCPSolver::getStructLatticeValueFor
std::vector< ValueLatticeElement > getStructLatticeValueFor(Value *V) const
Definition: SCCPSolver.cpp:1662
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
getMaxWidenStepsOpts
static ValueLatticeElement::MergeOptions getMaxWidenStepsOpts()
Returns MergeOptions with MaxWidenSteps set to MaxNumRangeExtensions.
Definition: SCCPSolver.cpp:39
ErrorHandling.h
llvm::SCCPInstVisitor::isEdgeFeasible
bool isEdgeFeasible(BasicBlock *From, BasicBlock *To) const
Definition: SCCPSolver.cpp:690
llvm::GlobalVariable
Definition: GlobalVariable.h:40
llvm::CmpInst::ICMP_NE
@ ICMP_NE
not equal
Definition: InstrTypes.h:742
ValueTracking.h
Local.h
llvm::SCCPSolver::getConstant
Constant * getConstant(const ValueLatticeElement &LV) const
Helper to return a Constant if LV is either a constant or a constant range with a single element.
Definition: SCCPSolver.cpp:1694
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::erase
bool erase(const KeyT &Val)
Definition: DenseMap.h:302
llvm::SCCPInstVisitor::isStructLatticeConstant
bool isStructLatticeConstant(Function *F, StructType *STy)
Definition: SCCPSolver.cpp:506
llvm::DenseMapIterator
Definition: DenseMap.h:56
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
llvm::ValueLatticeElement::getOverdefined
static ValueLatticeElement getOverdefined()
Definition: ValueLattice.h:232
llvm::Optional
Definition: APInt.h:33
T
#define T
Definition: Mips16ISelLowering.cpp:341
llvm::FenceInst
An instruction for ordering other memory operations.
Definition: Instructions.h:444
llvm::MapVector
This class implements a map that also provides access to all stored values in a deterministic order.
Definition: MapVector.h:37
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:449
llvm::SCCPSolver::markBlockExecutable
bool markBlockExecutable(BasicBlock *BB)
markBlockExecutable - This method can be used by clients to mark all of the blocks that are known to ...
Definition: SCCPSolver.cpp:1613
llvm::CallBase::arg_begin
User::op_iterator arg_begin()
Return the iterator pointing to the beginning of the argument list.
Definition: InstrTypes.h:1303
llvm::SCCPSolver::visit
void visit(Instruction *I)
Definition: SCCPSolver.cpp:1711
llvm::getConstantRangeFromMetadata
ConstantRange getConstantRangeFromMetadata(const MDNode &RangeMD)
Parse out a conservative ConstantRange from !range metadata.
Definition: ConstantRange.cpp:1698
llvm::SCCPInstVisitor::SCCPInstVisitor
SCCPInstVisitor(const DataLayout &DL, std::function< const TargetLibraryInfo &(Function &)> GetTLI, LLVMContext &Ctx)
Definition: SCCPSolver.cpp:352
llvm::detail::DenseSetImpl::insert
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:206
llvm::detail::DenseSetImpl::count
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
Definition: DenseSet.h:97
ConstantFolding.h
llvm::Instruction::isExceptionalTerminator
bool isExceptionalTerminator() const
Definition: Instruction.h:170
llvm::SCCPSolver::addArgumentTrackedFunction
void addArgumentTrackedFunction(Function *F)
Definition: SCCPSolver.cpp:1639
llvm::ConstantRange::makeAllowedICmpRegion
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...
Definition: ConstantRange.cpp:78
llvm::ConstantRange::isIntrinsicSupported
static bool isIntrinsicSupported(Intrinsic::ID IntrinsicID)
Returns true if ConstantRange calculations are supported for intrinsic with IntrinsicID.
Definition: ConstantRange.cpp:858
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
new
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM ID Predecessors according to mbb< bb27, 0x8b0a7c0 > Note ADDri is not a two address instruction its result reg1037 is an operand of the PHI node in bb76 and its operand reg1039 is the result of the PHI node We should treat it as a two address code and make sure the ADDri is scheduled after any node that reads reg1039 Use info(i.e. register scavenger) to assign it a free register to allow reuse the collector could move the objects and invalidate the derived pointer This is bad enough in the first but safe points can crop up unpredictably **array_addr i32 n y store obj * new
Definition: README.txt:125
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::RISCVFenceField::R
@ R
Definition: RISCVBaseInfo.h:193
llvm::DomTreeUpdater::UpdateStrategy::Lazy
@ Lazy
llvm::SCCPSolver::markFunctionUnreachable
void markFunctionUnreachable(Function *F)
Mark all of the blocks in function F non-executable.
Definition: SCCPSolver.cpp:1707
llvm::SCCPInstVisitor::resolvedUndefsIn
bool resolvedUndefsIn(Function &F)
resolvedUndefsIn - While solving the dataflow for a function, we assume that branches on undef values...
Definition: SCCPSolver.cpp:1447
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::SCCPInstVisitor::markArgInFuncSpecialization
void markArgInFuncSpecialization(Function *F, Argument *A, Constant *C)
Definition: SCCPSolver.cpp:529
llvm::ConstantInt
This is the shared class of boolean and integer constants.
Definition: Constants.h:79
llvm::SCCPInstVisitor::isArgumentTrackedFunction
bool isArgumentTrackedFunction(Function *F)
Definition: SCCPSolver.cpp:389
getValueFromMetadata
static ValueLatticeElement getValueFromMetadata(const Instruction *I)
Definition: SCCPSolver.cpp:1101
llvm::Instruction::getNumSuccessors
unsigned getNumSuccessors() const
Return the number of successors that this instruction has.
Definition: Instruction.cpp:765
llvm::Type::isSingleValueType
bool isSingleValueType() const
Return true if the type is a valid type for a register in codegen.
Definition: Type.h:259
llvm::ValueLatticeElement::MergeOptions
Struct to control some aspects related to merging constant ranges.
Definition: ValueLattice.h:109
llvm::SCCPInstVisitor::markOverdefined
void markOverdefined(Value *V)
Definition: SCCPSolver.cpp:439
llvm::PredicateConstraint::OtherOp
Value * OtherOp
Definition: PredicateInfo.h:77
llvm::ValueLatticeElement::isUnknownOrUndef
bool isUnknownOrUndef() const
Definition: ValueLattice.h:240
llvm::PHINode::getIncomingValue
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
Definition: Instructions.h:2721
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::SCCPSolver::markOverdefined
void markOverdefined(Value *V)
markOverdefined - Mark the specified value overdefined.
Definition: SCCPSolver.cpp:1688
llvm::User
Definition: User.h:44
llvm::ConstantFoldCastOperand
Constant * ConstantFoldCastOperand(unsigned Opcode, Constant *C, Type *DestTy, const DataLayout &DL)
Attempt to constant fold a cast with the specified operand.
Definition: ConstantFolding.cpp:1379
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::CallBase::getCalledFunction
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation.
Definition: InstrTypes.h:1393
llvm::SCCPSolver::isArgumentTrackedFunction
bool isArgumentTrackedFunction(Function *F)
Returns true if the given function is in the solver's set of argument-tracked functions.
Definition: SCCPSolver.cpp:1643
llvm::ExtractValueInst::getNumIndices
unsigned getNumIndices() const
Definition: Instructions.h:2441
llvm::ConstantRange::isSingleElement
bool isSingleElement() const
Return true if this set contains exactly one member.
Definition: ConstantRange.h:234
getOpcode
static Optional< unsigned > getOpcode(ArrayRef< VPValue * > Values)
Returns the opcode of Values or ~0 if they do not all agree.
Definition: VPlanSLP.cpp:199
llvm::ConstantFoldCall
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...
Definition: ConstantFolding.cpp:3152
llvm::ms_demangle::QualifierMangleMode::Result
@ Result
llvm::canConstantFoldCallTo
bool canConstantFoldCallTo(const CallBase *Call, const Function *F)
canConstantFoldCallTo - Return true if its even possible to fold a call to the specified function.
Definition: ConstantFolding.cpp:1474
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::SCCPSolver::addAnalysis
void addAnalysis(Function &F, AnalysisResultsForFn A)
Definition: SCCPSolver.cpp:1609
llvm::Instruction
Definition: Instruction.h:45
llvm::BasicBlock::phis
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
Definition: BasicBlock.h:354
llvm::SmallVectorImpl::resize
void resize(size_type N)
Definition: SmallVector.h:606
llvm::DomTreeUpdater
Definition: DomTreeUpdater.h:28
llvm::ConstantInt::get
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:900
llvm::SCCPSolver::isStructLatticeConstant
bool isStructLatticeConstant(Function *F, StructType *STy)
Definition: SCCPSolver.cpp:1690
llvm::Instruction::getSuccessor
BasicBlock * getSuccessor(unsigned Idx) const
Return the specified successor. This instruction must be a terminator.
Definition: Instruction.cpp:777
llvm::SCCPInstVisitor::getMRVFunctionsTracked
const SmallPtrSet< Function *, 16 > getMRVFunctionsTracked()
Definition: SCCPSolver.cpp:435
llvm::PHINode::getNumIncomingValues
unsigned getNumIncomingValues() const
Return the number of incoming edges.
Definition: Instructions.h:2717
llvm::PredicateConstraint::Predicate
CmpInst::Predicate Predicate
Definition: PredicateInfo.h:76
llvm::ConstantRange::intrinsic
static ConstantRange intrinsic(Intrinsic::ID IntrinsicID, ArrayRef< ConstantRange > Ops)
Compute range of intrinsic result for the given operand ranges.
Definition: ConstantRange.cpp:875
Operands
mir Rename Register Operands
Definition: MIRNamerPass.cpp:78
llvm::InvokeInst
Invoke instruction.
Definition: Instructions.h:3741
llvm::CmpInst
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:710
llvm::ValueLatticeElement::markOverdefined
bool markOverdefined()
Definition: ValueLattice.h:285
llvm::ValueLatticeElement::markConstant
bool markConstant(Constant *V, bool MayIncludeUndef=false)
Definition: ValueLattice.h:302
llvm::SCCPSolver::getTrackedRetVals
const MapVector< Function *, ValueLatticeElement > & getTrackedRetVals()
getTrackedRetVals - Get the inferred return value map.
Definition: SCCPSolver.cpp:1675
llvm::ConstantRange::castOp
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...
Definition: ConstantRange.cpp:646
llvm::DenseSet< Edge >
llvm::PredicateBase
Definition: PredicateInfo.h:82
llvm::SCCPSolver::visitCall
void visitCall(CallInst &I)
Definition: SCCPSolver.cpp:1713
llvm::SCCPInstVisitor::solve
void solve()
Definition: SCCPSolver.cpp:1380
llvm::SCCPSolver::getLatticeValueFor
const ValueLatticeElement & getLatticeValueFor(Value *V) const
Definition: SCCPSolver.cpp:1670
llvm::StoreInst
An instruction for storing to memory.
Definition: Instructions.h:304
llvm::GlobalVariable::getInitializer
const Constant * getInitializer() const
getInitializer - Return the initializer for this global variable.
Definition: GlobalVariable.h:136
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
llvm::ConstantRange::getBitWidth
uint32_t getBitWidth() const
Get the bit width of this ConstantRange.
Definition: ConstantRange.h:177
llvm::SCCPInstVisitor
Helper class for SCCPSolver.
Definition: SCCPSolver.cpp:69
Addr
uint64_t Addr
Definition: ELFObjHandler.cpp:80
llvm::ConstantPointerNull::get
static ConstantPointerNull * get(PointerType *T)
Static factory methods - Return objects of the specified value.
Definition: Constants.cpp:1757
llvm::SimplifyBinOp
Value * SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for a BinaryOperator, fold the result or return null.
Definition: InstructionSimplify.cpp:5315
llvm::CallBrInst
CallBr instruction, tracking function calls that may not return control but instead transfer it to a ...
Definition: Instructions.h:3950
move
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
Definition: README.txt:546
llvm::LLVMContext
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:68
isConstant
static bool isConstant(const MachineInstr &MI)
Definition: AMDGPUInstructionSelector.cpp:2311
llvm::SCCPSolver::getPredicateInfoFor
const PredicateBase * getPredicateInfoFor(Instruction *I)
Definition: SCCPSolver.cpp:1617
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
llvm::DenseMap
Definition: DenseMap.h:714
llvm::SCCPInstVisitor::addArgumentTrackedFunction
void addArgumentTrackedFunction(Function *F)
Definition: SCCPSolver.cpp:385
MaxNumRangeExtensions
static const unsigned MaxNumRangeExtensions
Definition: SCCPSolver.cpp:36
llvm::ConstantExpr::get
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:2242
llvm::ExtractValueInst::idx_begin
idx_iterator idx_begin() const
Definition: Instructions.h:2421
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::SCCPInstVisitor::getArgumentTrackedFunctions
SmallPtrSetImpl< Function * > & getArgumentTrackedFunctions()
Definition: SCCPSolver.cpp:451
llvm::GetElementPtrInst
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Definition: Instructions.h:928
llvm::InstVisitor< SCCPInstVisitor >::visit
void visit(Iterator Start, Iterator End)
Definition: InstVisitor.h:88
llvm::SCCPInstVisitor::getTrackedRetVals
const MapVector< Function *, ValueLatticeElement > & getTrackedRetVals()
Definition: SCCPSolver.cpp:427
llvm::ValueLatticeElement::getCompare
Constant * getCompare(CmpInst::Predicate Pred, Type *Ty, const ValueLatticeElement &Other) const
true, false or undef constants, or nullptr if the comparison cannot be evaluated.
Definition: ValueLattice.h:452
llvm::SCCPSolver::getTrackedGlobals
const DenseMap< GlobalVariable *, ValueLatticeElement > & getTrackedGlobals()
getTrackedGlobals - Get and return the set of inferred initializers for global variables.
Definition: SCCPSolver.cpp:1680
llvm::ValueLatticeElement::getNumRangeExtensions
unsigned getNumRangeExtensions() const
Definition: ValueLattice.h:485
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::find
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:150
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::NVPTXISD::CallArg
@ CallArg
Definition: NVPTXISelLowering.h:40
llvm::move
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:1605
SI
StandardInstrumentations SI(Debug, VerifyEach)
llvm::SelectInst
This class represents the LLVM 'select' instruction.
Definition: Instructions.h:1738
function
print Print MemDeps of function
Definition: MemDepPrinter.cpp:83
llvm::Type::isVoidTy
bool isVoidTy() const
Return true if this is 'void'.
Definition: Type.h:138
llvm::MDNode
Metadata node.
Definition: Metadata.h:901
llvm::SCCPSolver::~SCCPSolver
~SCCPSolver()
Definition: SCCPSolver.cpp:1607
llvm::CallBase::arg_end
User::op_iterator arg_end()
Return the iterator pointing to the end of the argument list.
Definition: InstrTypes.h:1309
llvm::SmallPtrSetImpl::count
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:382
llvm::APInt
Class for arbitrary precision integers.
Definition: APInt.h:75
llvm::SCCPInstVisitor::mustPreserveReturn
bool mustPreserveReturn(Function *F)
Definition: SCCPSolver.cpp:381
llvm::BlockAddress
The address of a basic block.
Definition: Constants.h:848
llvm::SCCPSolver::getDTU
DomTreeUpdater getDTU(Function &F)
Definition: SCCPSolver.cpp:1621
llvm::Sched::Source
@ Source
Definition: TargetLowering.h:100
llvm::MapVector::insert
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: MapVector.h:117
llvm::SCCPSolver::SCCPSolver
SCCPSolver(const DataLayout &DL, std::function< const TargetLibraryInfo &(Function &)> GetTLI, LLVMContext &Ctx)
Definition: SCCPSolver.cpp:1601
llvm::StructType
Class to represent struct types.
Definition: DerivedTypes.h:213
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:136
llvm::Constant::getAggregateElement
Constant * getAggregateElement(unsigned Elt) const
For aggregates (struct/array/vector) return the constant that corresponds to the specified element if...
Definition: Constants.cpp:421
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:256
llvm::ConstantInt::isZero
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
Definition: Constants.h:194
A
* A
Definition: README_ALTIVEC.txt:89
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
llvm::SCCPSolver::removeLatticeValueFor
void removeLatticeValueFor(Value *V)
Definition: SCCPSolver.cpp:1666
llvm::ValueLatticeElement
This class represents lattice values for constants.
Definition: ValueLattice.h:27
llvm::InstVisitor
Base class for instruction visitors.
Definition: InstVisitor.h:79
llvm::SCCPSolver::mustPreserveReturn
bool mustPreserveReturn(Function *F)
Returns true if the return of the given function cannot be modified.
Definition: SCCPSolver.cpp:1635
llvm::CastInst
This is the base class for all instructions that perform data casts.
Definition: InstrTypes.h:430
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:297
llvm::SCCPInstVisitor::trackValueOfGlobalVariable
void trackValueOfGlobalVariable(GlobalVariable *GV)
Definition: SCCPSolver.cpp:357
llvm::LoadInst
An instruction for reading from memory.
Definition: Instructions.h:175
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::insert
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:207
llvm::ValueLatticeElement::isOverdefined
bool isOverdefined() const
Definition: ValueLattice.h:254
llvm::SCCPInstVisitor::getTrackedGlobals
const DenseMap< GlobalVariable *, ValueLatticeElement > & getTrackedGlobals()
Definition: SCCPSolver.cpp:431
llvm::SCCPInstVisitor::getConstant
Constant * getConstant(const ValueLatticeElement &LV) const
Definition: SCCPSolver.cpp:517
llvm::SCCPSolver::isBlockExecutable
bool isBlockExecutable(BasicBlock *BB) const
Definition: SCCPSolver.cpp:1653
llvm::StructType::getNumElements
unsigned getNumElements() const
Random access to the elements.
Definition: DerivedTypes.h:327
llvm::ConstantInt::getFalse
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:855
llvm::SCCPSolver::isEdgeFeasible
bool isEdgeFeasible(BasicBlock *From, BasicBlock *To) const
Definition: SCCPSolver.cpp:1657
llvm::SCCPInstVisitor::markFunctionUnreachable
void markFunctionUnreachable(Function *F)
Definition: SCCPSolver.cpp:457
llvm::NVPTX::PTXLdStInstCode::V2
@ V2
Definition: NVPTX.h:123
llvm::ResumeInst
Resume the propagation of an exception.
Definition: Instructions.h:4191
SCCPSolver.h
std
Definition: BitVector.h:838
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::end
iterator end()
Definition: DenseMap.h:83
llvm::SmallVectorImpl::assign
void assign(size_type NumElts, ValueParamT Elt)
Definition: SmallVector.h:669
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:321
llvm::SCCPInstVisitor::getPredicateInfoFor
const PredicateBase * getPredicateInfoFor(Instruction *I)
Definition: SCCPSolver.cpp:339
llvm::ExtractValueInst
This instruction extracts a struct member or array element value from an aggregate value.
Definition: Instructions.h:2372
Casting.h
llvm::ValueLatticeElement::getRange
static ValueLatticeElement getRange(ConstantRange CR, bool MayIncludeUndef=false)
Definition: ValueLattice.h:215
llvm::TargetLibraryInfo
Provides information about what library functions are available for the current target.
Definition: TargetLibraryInfo.h:219
llvm::SCCPSolver::resolvedUndefsIn
bool resolvedUndefsIn(Function &F)
resolvedUndefsIn - While solving the dataflow for a function, we assume that branches on undef values...
Definition: SCCPSolver.cpp:1649
llvm::ExtractValueInst::getAggregateOperand
Value * getAggregateOperand()
Definition: Instructions.h:2427
llvm::SCCPInstVisitor::addTrackedFunction
void addTrackedFunction(Function *F)
Definition: SCCPSolver.cpp:366
llvm::ConstantExpr::getGetElementPtr
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:1210
llvm::ConstantRange::contains
bool contains(const APInt &Val) const
Return true if the specified value is in the set.
Definition: ConstantRange.cpp:393
llvm::ConstantRange
This class represents a range of values.
Definition: ConstantRange.h:47
llvm::ValueLatticeElement::mergeIn
bool mergeIn(const ValueLatticeElement &RHS, MergeOptions Opts=MergeOptions())
Updates this object to approximate both this object and RHS.
Definition: ValueLattice.h:386
llvm::makeArrayRef
ArrayRef< T > makeArrayRef(const T &OneElt)
Construct an ArrayRef from a single element.
Definition: ArrayRef.h:476
llvm::SCCPSolver::addToMustPreserveReturnsInFunctions
void addToMustPreserveReturnsInFunctions(Function *F)
Add function to the list of functions whose return cannot be modified.
Definition: SCCPSolver.cpp:1631
llvm::Type::isStructTy
bool isStructTy() const
True if this is an instance of StructType.
Definition: Type.h:222
llvm::SCCPSolver::markArgInFuncSpecialization
void markArgInFuncSpecialization(Function *F, Argument *A, Constant *C)
Mark argument A constant with value C in a new function specialization.
Definition: SCCPSolver.cpp:1702
llvm::ValueLatticeElement::isConstantRange
bool isConstantRange(bool UndefAllowed=true) const
Returns true if this value is a constant range.
Definition: ValueLattice.h:250
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:94
InstructionSimplify.h
llvm::BlockAddress::get
static BlockAddress * get(Function *F, BasicBlock *BB)
Return a BlockAddress for the specified function and basic block.
Definition: Constants.cpp:1809
llvm::PHINode::getIncomingBlock
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Definition: Instructions.h:2741
llvm::max
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:340
llvm::PHINode
Definition: Instructions.h:2625
llvm::SmallVectorImpl< bool >
llvm::SCCPSolver::trackValueOfGlobalVariable
void trackValueOfGlobalVariable(GlobalVariable *GV)
trackValueOfGlobalVariable - Clients can use this method to inform the SCCPSolver that it should trac...
Definition: SCCPSolver.cpp:1623
llvm::SCCPInstVisitor::addToMustPreserveReturnsInFunctions
void addToMustPreserveReturnsInFunctions(Function *F)
Definition: SCCPSolver.cpp:377
llvm::CallBase
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1161
llvm::SmallPtrSetImpl< Function * >
llvm::GlobalValue::getValueType
Type * getValueType() const
Definition: GlobalValue.h:273
llvm::SCCPInstVisitor::getStructLatticeValueFor
std::vector< ValueLatticeElement > getStructLatticeValueFor(Value *V) const
Definition: SCCPSolver.cpp:403
llvm::CallInst
This class represents a function call, abstracting a target machine's calling convention.
Definition: Instructions.h:1475
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::UnreachableInst
This function has undefined behavior.
Definition: Instructions.h:4707
llvm::SCCPSolver::solve
void solve()
Solve - Solve for constants and executable blocks.
Definition: SCCPSolver.cpp:1647
From
BlockVerifier::State From
Definition: BlockVerifier.cpp:55
llvm::User::getOperand
Value * getOperand(unsigned i) const
Definition: User.h:169
llvm::SCCPInstVisitor::addAnalysis
void addAnalysis(Function &F, AnalysisResultsForFn A)
Definition: SCCPSolver.cpp:331
raw_ostream.h
llvm::NullPointerIsDefined
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:1965
llvm::SCCPSolver::addTrackedFunction
void addTrackedFunction(Function *F)
addTrackedFunction - If the SCCP solver is supposed to track calls into and out of the specified func...
Definition: SCCPSolver.cpp:1627
llvm::InsertValueInst
This instruction inserts a struct field of array element value into an aggregate value.
Definition: Instructions.h:2483
llvm::CatchSwitchInst
Definition: Instructions.h:4248
llvm::SCCPInstVisitor::visitCallInst
void visitCallInst(CallInst &I)
Definition: SCCPSolver.cpp:335
llvm::SCCPInstVisitor::markBlockExecutable
bool markBlockExecutable(BasicBlock *BB)
Definition: SCCPSolver.cpp:465
InitializePasses.h
llvm::ValueLatticeElement::MergeOptions::setCheckWiden
MergeOptions & setCheckWiden(bool V=true)
Definition: ValueLattice.h:133
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
Debug.h
llvm::SCCPSolver::getMRVFunctionsTracked
const SmallPtrSet< Function *, 16 > getMRVFunctionsTracked()
getMRVFunctionsTracked - Get the set of functions which return multiple values tracked by the pass.
Definition: SCCPSolver.cpp:1684
llvm::SCCPSolver::getArgumentTrackedFunctions
SmallPtrSetImpl< Function * > & getArgumentTrackedFunctions()
Return a reference to the set of argument tracked functions.
Definition: SCCPSolver.cpp:1698
llvm::ValueLatticeElement::setNumRangeExtensions
void setNumRangeExtensions(unsigned N)
Definition: ValueLattice.h:486
llvm::SCCPInstVisitor::isBlockExecutable
bool isBlockExecutable(BasicBlock *BB) const
Definition: SCCPSolver.cpp:397
isOverdefined
static bool isOverdefined(const ValueLatticeElement &LV)
Definition: FunctionSpecialization.cpp:105
llvm::SmallPtrSetImpl::insert
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
llvm::ConstantFoldLoadFromConstPtr
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...
Definition: ConstantFolding.cpp:675