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  // Note: This previously looked like this:
544  // ValueState[J] = ValueState[I];
545  // This is incorrect because the DenseMap class may resize the underlying
546  // memory when inserting `J`, which will invalidate the reference to `I`.
547  // Instead, we make sure `J` exists, then set it to `I` afterwards.
548  auto &NewValue = ValueState[J];
549  NewValue = ValueState[I];
550  pushToWorkList(NewValue, J);
551  }
552 }
553 
554 void SCCPInstVisitor::visitInstruction(Instruction &I) {
555  // All the instructions we don't do any special handling for just
556  // go to overdefined.
557  LLVM_DEBUG(dbgs() << "SCCP: Don't know how to handle: " << I << '\n');
558  markOverdefined(&I);
559 }
560 
561 bool SCCPInstVisitor::mergeInValue(ValueLatticeElement &IV, Value *V,
562  ValueLatticeElement MergeWithV,
564  if (IV.mergeIn(MergeWithV, Opts)) {
565  pushToWorkList(IV, V);
566  LLVM_DEBUG(dbgs() << "Merged " << MergeWithV << " into " << *V << " : "
567  << IV << "\n");
568  return true;
569  }
570  return false;
571 }
572 
573 bool SCCPInstVisitor::markEdgeExecutable(BasicBlock *Source, BasicBlock *Dest) {
574  if (!KnownFeasibleEdges.insert(Edge(Source, Dest)).second)
575  return false; // This edge is already known to be executable!
576 
577  if (!markBlockExecutable(Dest)) {
578  // If the destination is already executable, we just made an *edge*
579  // feasible that wasn't before. Revisit the PHI nodes in the block
580  // because they have potentially new operands.
581  LLVM_DEBUG(dbgs() << "Marking Edge Executable: " << Source->getName()
582  << " -> " << Dest->getName() << '\n');
583 
584  for (PHINode &PN : Dest->phis())
585  visitPHINode(PN);
586  }
587  return true;
588 }
589 
590 // getFeasibleSuccessors - Return a vector of booleans to indicate which
591 // successors are reachable from a given terminator instruction.
592 void SCCPInstVisitor::getFeasibleSuccessors(Instruction &TI,
593  SmallVectorImpl<bool> &Succs) {
594  Succs.resize(TI.getNumSuccessors());
595  if (auto *BI = dyn_cast<BranchInst>(&TI)) {
596  if (BI->isUnconditional()) {
597  Succs[0] = true;
598  return;
599  }
600 
601  ValueLatticeElement BCValue = getValueState(BI->getCondition());
602  ConstantInt *CI = getConstantInt(BCValue);
603  if (!CI) {
604  // Overdefined condition variables, and branches on unfoldable constant
605  // conditions, mean the branch could go either way.
606  if (!BCValue.isUnknownOrUndef())
607  Succs[0] = Succs[1] = true;
608  return;
609  }
610 
611  // Constant condition variables mean the branch can only go a single way.
612  Succs[CI->isZero()] = true;
613  return;
614  }
615 
616  // Unwinding instructions successors are always executable.
617  if (TI.isExceptionalTerminator()) {
618  Succs.assign(TI.getNumSuccessors(), true);
619  return;
620  }
621 
622  if (auto *SI = dyn_cast<SwitchInst>(&TI)) {
623  if (!SI->getNumCases()) {
624  Succs[0] = true;
625  return;
626  }
627  const ValueLatticeElement &SCValue = getValueState(SI->getCondition());
628  if (ConstantInt *CI = getConstantInt(SCValue)) {
629  Succs[SI->findCaseValue(CI)->getSuccessorIndex()] = true;
630  return;
631  }
632 
633  // TODO: Switch on undef is UB. Stop passing false once the rest of LLVM
634  // is ready.
635  if (SCValue.isConstantRange(/*UndefAllowed=*/false)) {
636  const ConstantRange &Range = SCValue.getConstantRange();
637  for (const auto &Case : SI->cases()) {
638  const APInt &CaseValue = Case.getCaseValue()->getValue();
639  if (Range.contains(CaseValue))
640  Succs[Case.getSuccessorIndex()] = true;
641  }
642 
643  // TODO: Determine whether default case is reachable.
644  Succs[SI->case_default()->getSuccessorIndex()] = true;
645  return;
646  }
647 
648  // Overdefined or unknown condition? All destinations are executable!
649  if (!SCValue.isUnknownOrUndef())
650  Succs.assign(TI.getNumSuccessors(), true);
651  return;
652  }
653 
654  // In case of indirect branch and its address is a blockaddress, we mark
655  // the target as executable.
656  if (auto *IBR = dyn_cast<IndirectBrInst>(&TI)) {
657  // Casts are folded by visitCastInst.
658  ValueLatticeElement IBRValue = getValueState(IBR->getAddress());
659  BlockAddress *Addr = dyn_cast_or_null<BlockAddress>(getConstant(IBRValue));
660  if (!Addr) { // Overdefined or unknown condition?
661  // All destinations are executable!
662  if (!IBRValue.isUnknownOrUndef())
663  Succs.assign(TI.getNumSuccessors(), true);
664  return;
665  }
666 
667  BasicBlock *T = Addr->getBasicBlock();
668  assert(Addr->getFunction() == T->getParent() &&
669  "Block address of a different function ?");
670  for (unsigned i = 0; i < IBR->getNumSuccessors(); ++i) {
671  // This is the target.
672  if (IBR->getDestination(i) == T) {
673  Succs[i] = true;
674  return;
675  }
676  }
677 
678  // If we didn't find our destination in the IBR successor list, then we
679  // have undefined behavior. Its ok to assume no successor is executable.
680  return;
681  }
682 
683  // In case of callbr, we pessimistically assume that all successors are
684  // feasible.
685  if (isa<CallBrInst>(&TI)) {
686  Succs.assign(TI.getNumSuccessors(), true);
687  return;
688  }
689 
690  LLVM_DEBUG(dbgs() << "Unknown terminator instruction: " << TI << '\n');
691  llvm_unreachable("SCCP: Don't know how to handle this terminator!");
692 }
693 
694 // isEdgeFeasible - Return true if the control flow edge from the 'From' basic
695 // block to the 'To' basic block is currently feasible.
697  // Check if we've called markEdgeExecutable on the edge yet. (We could
698  // be more aggressive and try to consider edges which haven't been marked
699  // yet, but there isn't any need.)
700  return KnownFeasibleEdges.count(Edge(From, To));
701 }
702 
703 // visit Implementations - Something changed in this instruction, either an
704 // operand made a transition, or the instruction is newly executable. Change
705 // the value type of I to reflect these changes if appropriate. This method
706 // makes sure to do the following actions:
707 //
708 // 1. If a phi node merges two constants in, and has conflicting value coming
709 // from different branches, or if the PHI node merges in an overdefined
710 // value, then the PHI node becomes overdefined.
711 // 2. If a phi node merges only constants in, and they all agree on value, the
712 // PHI node becomes a constant value equal to that.
713 // 3. If V <- x (op) y && isConstant(x) && isConstant(y) V = Constant
714 // 4. If V <- x (op) y && (isOverdefined(x) || isOverdefined(y)) V = Overdefined
715 // 5. If V <- MEM or V <- CALL or V <- (unknown) then V = Overdefined
716 // 6. If a conditional branch has a value that is constant, make the selected
717 // destination executable
718 // 7. If a conditional branch has a value that is overdefined, make all
719 // successors executable.
720 void SCCPInstVisitor::visitPHINode(PHINode &PN) {
721  // If this PN returns a struct, just mark the result overdefined.
722  // TODO: We could do a lot better than this if code actually uses this.
723  if (PN.getType()->isStructTy())
724  return (void)markOverdefined(&PN);
725 
726  if (getValueState(&PN).isOverdefined())
727  return; // Quick exit
728 
729  // Super-extra-high-degree PHI nodes are unlikely to ever be marked constant,
730  // and slow us down a lot. Just mark them overdefined.
731  if (PN.getNumIncomingValues() > 64)
732  return (void)markOverdefined(&PN);
733 
734  unsigned NumActiveIncoming = 0;
735 
736  // Look at all of the executable operands of the PHI node. If any of them
737  // are overdefined, the PHI becomes overdefined as well. If they are all
738  // constant, and they agree with each other, the PHI becomes the identical
739  // constant. If they are constant and don't agree, the PHI is a constant
740  // range. If there are no executable operands, the PHI remains unknown.
741  ValueLatticeElement PhiState = getValueState(&PN);
742  for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) {
743  if (!isEdgeFeasible(PN.getIncomingBlock(i), PN.getParent()))
744  continue;
745 
746  ValueLatticeElement IV = getValueState(PN.getIncomingValue(i));
747  PhiState.mergeIn(IV);
748  NumActiveIncoming++;
749  if (PhiState.isOverdefined())
750  break;
751  }
752 
753  // We allow up to 1 range extension per active incoming value and one
754  // additional extension. Note that we manually adjust the number of range
755  // extensions to match the number of active incoming values. This helps to
756  // limit multiple extensions caused by the same incoming value, if other
757  // incoming values are equal.
758  mergeInValue(&PN, PhiState,
759  ValueLatticeElement::MergeOptions().setMaxWidenSteps(
760  NumActiveIncoming + 1));
761  ValueLatticeElement &PhiStateRef = getValueState(&PN);
762  PhiStateRef.setNumRangeExtensions(
763  std::max(NumActiveIncoming, PhiStateRef.getNumRangeExtensions()));
764 }
765 
766 void SCCPInstVisitor::visitReturnInst(ReturnInst &I) {
767  if (I.getNumOperands() == 0)
768  return; // ret void
769 
770  Function *F = I.getParent()->getParent();
771  Value *ResultOp = I.getOperand(0);
772 
773  // If we are tracking the return value of this function, merge it in.
774  if (!TrackedRetVals.empty() && !ResultOp->getType()->isStructTy()) {
775  auto TFRVI = TrackedRetVals.find(F);
776  if (TFRVI != TrackedRetVals.end()) {
777  mergeInValue(TFRVI->second, F, getValueState(ResultOp));
778  return;
779  }
780  }
781 
782  // Handle functions that return multiple values.
783  if (!TrackedMultipleRetVals.empty()) {
784  if (auto *STy = dyn_cast<StructType>(ResultOp->getType()))
785  if (MRVFunctionsTracked.count(F))
786  for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
787  mergeInValue(TrackedMultipleRetVals[std::make_pair(F, i)], F,
788  getStructValueState(ResultOp, i));
789  }
790 }
791 
792 void SCCPInstVisitor::visitTerminator(Instruction &TI) {
793  SmallVector<bool, 16> SuccFeasible;
794  getFeasibleSuccessors(TI, SuccFeasible);
795 
796  BasicBlock *BB = TI.getParent();
797 
798  // Mark all feasible successors executable.
799  for (unsigned i = 0, e = SuccFeasible.size(); i != e; ++i)
800  if (SuccFeasible[i])
801  markEdgeExecutable(BB, TI.getSuccessor(i));
802 }
803 
804 void SCCPInstVisitor::visitCastInst(CastInst &I) {
805  // ResolvedUndefsIn might mark I as overdefined. Bail out, even if we would
806  // discover a concrete value later.
807  if (ValueState[&I].isOverdefined())
808  return;
809 
810  ValueLatticeElement OpSt = getValueState(I.getOperand(0));
811  if (OpSt.isUnknownOrUndef())
812  return;
813 
814  if (Constant *OpC = getConstant(OpSt)) {
815  // Fold the constant as we build.
816  Constant *C = ConstantFoldCastOperand(I.getOpcode(), OpC, I.getType(), DL);
817  if (isa<UndefValue>(C))
818  return;
819  // Propagate constant value
820  markConstant(&I, C);
821  } else if (I.getDestTy()->isIntegerTy()) {
822  auto &LV = getValueState(&I);
823  ConstantRange OpRange =
824  OpSt.isConstantRange()
825  ? OpSt.getConstantRange()
826  : ConstantRange::getFull(
827  I.getOperand(0)->getType()->getScalarSizeInBits());
828 
829  Type *DestTy = I.getDestTy();
830  // Vectors where all elements have the same known constant range are treated
831  // as a single constant range in the lattice. When bitcasting such vectors,
832  // there is a mis-match between the width of the lattice value (single
833  // constant range) and the original operands (vector). Go to overdefined in
834  // that case.
835  if (I.getOpcode() == Instruction::BitCast &&
836  I.getOperand(0)->getType()->isVectorTy() &&
837  OpRange.getBitWidth() < DL.getTypeSizeInBits(DestTy))
838  return (void)markOverdefined(&I);
839 
840  ConstantRange Res =
841  OpRange.castOp(I.getOpcode(), DL.getTypeSizeInBits(DestTy));
842  mergeInValue(LV, &I, ValueLatticeElement::getRange(Res));
843  } else
844  markOverdefined(&I);
845 }
846 
847 void SCCPInstVisitor::visitExtractValueInst(ExtractValueInst &EVI) {
848  // If this returns a struct, mark all elements over defined, we don't track
849  // structs in structs.
850  if (EVI.getType()->isStructTy())
851  return (void)markOverdefined(&EVI);
852 
853  // resolvedUndefsIn might mark I as overdefined. Bail out, even if we would
854  // discover a concrete value later.
855  if (ValueState[&EVI].isOverdefined())
856  return (void)markOverdefined(&EVI);
857 
858  // If this is extracting from more than one level of struct, we don't know.
859  if (EVI.getNumIndices() != 1)
860  return (void)markOverdefined(&EVI);
861 
862  Value *AggVal = EVI.getAggregateOperand();
863  if (AggVal->getType()->isStructTy()) {
864  unsigned i = *EVI.idx_begin();
865  ValueLatticeElement EltVal = getStructValueState(AggVal, i);
866  mergeInValue(getValueState(&EVI), &EVI, EltVal);
867  } else {
868  // Otherwise, must be extracting from an array.
869  return (void)markOverdefined(&EVI);
870  }
871 }
872 
873 void SCCPInstVisitor::visitInsertValueInst(InsertValueInst &IVI) {
874  auto *STy = dyn_cast<StructType>(IVI.getType());
875  if (!STy)
876  return (void)markOverdefined(&IVI);
877 
878  // resolvedUndefsIn might mark I as overdefined. Bail out, even if we would
879  // discover a concrete value later.
880  if (isOverdefined(ValueState[&IVI]))
881  return (void)markOverdefined(&IVI);
882 
883  // If this has more than one index, we can't handle it, drive all results to
884  // undef.
885  if (IVI.getNumIndices() != 1)
886  return (void)markOverdefined(&IVI);
887 
888  Value *Aggr = IVI.getAggregateOperand();
889  unsigned Idx = *IVI.idx_begin();
890 
891  // Compute the result based on what we're inserting.
892  for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
893  // This passes through all values that aren't the inserted element.
894  if (i != Idx) {
895  ValueLatticeElement EltVal = getStructValueState(Aggr, i);
896  mergeInValue(getStructValueState(&IVI, i), &IVI, EltVal);
897  continue;
898  }
899 
900  Value *Val = IVI.getInsertedValueOperand();
901  if (Val->getType()->isStructTy())
902  // We don't track structs in structs.
903  markOverdefined(getStructValueState(&IVI, i), &IVI);
904  else {
905  ValueLatticeElement InVal = getValueState(Val);
906  mergeInValue(getStructValueState(&IVI, i), &IVI, InVal);
907  }
908  }
909 }
910 
911 void SCCPInstVisitor::visitSelectInst(SelectInst &I) {
912  // If this select returns a struct, just mark the result overdefined.
913  // TODO: We could do a lot better than this if code actually uses this.
914  if (I.getType()->isStructTy())
915  return (void)markOverdefined(&I);
916 
917  // resolvedUndefsIn might mark I as overdefined. Bail out, even if we would
918  // discover a concrete value later.
919  if (ValueState[&I].isOverdefined())
920  return (void)markOverdefined(&I);
921 
922  ValueLatticeElement CondValue = getValueState(I.getCondition());
923  if (CondValue.isUnknownOrUndef())
924  return;
925 
926  if (ConstantInt *CondCB = getConstantInt(CondValue)) {
927  Value *OpVal = CondCB->isZero() ? I.getFalseValue() : I.getTrueValue();
928  mergeInValue(&I, getValueState(OpVal));
929  return;
930  }
931 
932  // Otherwise, the condition is overdefined or a constant we can't evaluate.
933  // See if we can produce something better than overdefined based on the T/F
934  // value.
935  ValueLatticeElement TVal = getValueState(I.getTrueValue());
936  ValueLatticeElement FVal = getValueState(I.getFalseValue());
937 
938  bool Changed = ValueState[&I].mergeIn(TVal);
939  Changed |= ValueState[&I].mergeIn(FVal);
940  if (Changed)
941  pushToWorkListMsg(ValueState[&I], &I);
942 }
943 
944 // Handle Unary Operators.
945 void SCCPInstVisitor::visitUnaryOperator(Instruction &I) {
946  ValueLatticeElement V0State = getValueState(I.getOperand(0));
947 
948  ValueLatticeElement &IV = ValueState[&I];
949  // resolvedUndefsIn might mark I as overdefined. Bail out, even if we would
950  // discover a concrete value later.
951  if (isOverdefined(IV))
952  return (void)markOverdefined(&I);
953 
954  if (isConstant(V0State)) {
955  Constant *C = ConstantExpr::get(I.getOpcode(), getConstant(V0State));
956 
957  // op Y -> undef.
958  if (isa<UndefValue>(C))
959  return;
960  return (void)markConstant(IV, &I, C);
961  }
962 
963  // If something is undef, wait for it to resolve.
964  if (!isOverdefined(V0State))
965  return;
966 
967  markOverdefined(&I);
968 }
969 
970 // Handle Binary Operators.
971 void SCCPInstVisitor::visitBinaryOperator(Instruction &I) {
972  ValueLatticeElement V1State = getValueState(I.getOperand(0));
973  ValueLatticeElement V2State = getValueState(I.getOperand(1));
974 
975  ValueLatticeElement &IV = ValueState[&I];
976  if (IV.isOverdefined())
977  return;
978 
979  // If something is undef, wait for it to resolve.
980  if (V1State.isUnknownOrUndef() || V2State.isUnknownOrUndef())
981  return;
982 
983  if (V1State.isOverdefined() && V2State.isOverdefined())
984  return (void)markOverdefined(&I);
985 
986  // If either of the operands is a constant, try to fold it to a constant.
987  // TODO: Use information from notconstant better.
988  if ((V1State.isConstant() || V2State.isConstant())) {
989  Value *V1 = isConstant(V1State) ? getConstant(V1State) : I.getOperand(0);
990  Value *V2 = isConstant(V2State) ? getConstant(V2State) : I.getOperand(1);
991  Value *R = SimplifyBinOp(I.getOpcode(), V1, V2, SimplifyQuery(DL));
992  auto *C = dyn_cast_or_null<Constant>(R);
993  if (C) {
994  // X op Y -> undef.
995  if (isa<UndefValue>(C))
996  return;
997  // Conservatively assume that the result may be based on operands that may
998  // be undef. Note that we use mergeInValue to combine the constant with
999  // the existing lattice value for I, as different constants might be found
1000  // after one of the operands go to overdefined, e.g. due to one operand
1001  // being a special floating value.
1002  ValueLatticeElement NewV;
1003  NewV.markConstant(C, /*MayIncludeUndef=*/true);
1004  return (void)mergeInValue(&I, NewV);
1005  }
1006  }
1007 
1008  // Only use ranges for binary operators on integers.
1009  if (!I.getType()->isIntegerTy())
1010  return markOverdefined(&I);
1011 
1012  // Try to simplify to a constant range.
1013  ConstantRange A = ConstantRange::getFull(I.getType()->getScalarSizeInBits());
1014  ConstantRange B = ConstantRange::getFull(I.getType()->getScalarSizeInBits());
1015  if (V1State.isConstantRange())
1016  A = V1State.getConstantRange();
1017  if (V2State.isConstantRange())
1018  B = V2State.getConstantRange();
1019 
1020  ConstantRange R = A.binaryOp(cast<BinaryOperator>(&I)->getOpcode(), B);
1021  mergeInValue(&I, ValueLatticeElement::getRange(R));
1022 
1023  // TODO: Currently we do not exploit special values that produce something
1024  // better than overdefined with an overdefined operand for vector or floating
1025  // point types, like and <4 x i32> overdefined, zeroinitializer.
1026 }
1027 
1028 // Handle ICmpInst instruction.
1029 void SCCPInstVisitor::visitCmpInst(CmpInst &I) {
1030  // Do not cache this lookup, getValueState calls later in the function might
1031  // invalidate the reference.
1032  if (isOverdefined(ValueState[&I]))
1033  return (void)markOverdefined(&I);
1034 
1035  Value *Op1 = I.getOperand(0);
1036  Value *Op2 = I.getOperand(1);
1037 
1038  // For parameters, use ParamState which includes constant range info if
1039  // available.
1040  auto V1State = getValueState(Op1);
1041  auto V2State = getValueState(Op2);
1042 
1043  Constant *C = V1State.getCompare(I.getPredicate(), I.getType(), V2State);
1044  if (C) {
1045  if (isa<UndefValue>(C))
1046  return;
1048  CV.markConstant(C);
1049  mergeInValue(&I, CV);
1050  return;
1051  }
1052 
1053  // If operands are still unknown, wait for it to resolve.
1054  if ((V1State.isUnknownOrUndef() || V2State.isUnknownOrUndef()) &&
1055  !isConstant(ValueState[&I]))
1056  return;
1057 
1058  markOverdefined(&I);
1059 }
1060 
1061 // Handle getelementptr instructions. If all operands are constants then we
1062 // can turn this into a getelementptr ConstantExpr.
1063 void SCCPInstVisitor::visitGetElementPtrInst(GetElementPtrInst &I) {
1064  if (isOverdefined(ValueState[&I]))
1065  return (void)markOverdefined(&I);
1066 
1068  Operands.reserve(I.getNumOperands());
1069 
1070  for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) {
1071  ValueLatticeElement State = getValueState(I.getOperand(i));
1072  if (State.isUnknownOrUndef())
1073  return; // Operands are not resolved yet.
1074 
1075  if (isOverdefined(State))
1076  return (void)markOverdefined(&I);
1077 
1078  if (Constant *C = getConstant(State)) {
1079  Operands.push_back(C);
1080  continue;
1081  }
1082 
1083  return (void)markOverdefined(&I);
1084  }
1085 
1086  Constant *Ptr = Operands[0];
1087  auto Indices = makeArrayRef(Operands.begin() + 1, Operands.end());
1088  Constant *C =
1089  ConstantExpr::getGetElementPtr(I.getSourceElementType(), Ptr, Indices);
1090  if (isa<UndefValue>(C))
1091  return;
1092  markConstant(&I, C);
1093 }
1094 
1095 void SCCPInstVisitor::visitStoreInst(StoreInst &SI) {
1096  // If this store is of a struct, ignore it.
1097  if (SI.getOperand(0)->getType()->isStructTy())
1098  return;
1099 
1100  if (TrackedGlobals.empty() || !isa<GlobalVariable>(SI.getOperand(1)))
1101  return;
1102 
1103  GlobalVariable *GV = cast<GlobalVariable>(SI.getOperand(1));
1104  auto I = TrackedGlobals.find(GV);
1105  if (I == TrackedGlobals.end())
1106  return;
1107 
1108  // Get the value we are storing into the global, then merge it.
1109  mergeInValue(I->second, GV, getValueState(SI.getOperand(0)),
1111  if (I->second.isOverdefined())
1112  TrackedGlobals.erase(I); // No need to keep tracking this!
1113 }
1114 
1116  if (MDNode *Ranges = I->getMetadata(LLVMContext::MD_range))
1117  if (I->getType()->isIntegerTy())
1119  getConstantRangeFromMetadata(*Ranges));
1120  if (I->hasMetadata(LLVMContext::MD_nonnull))
1122  ConstantPointerNull::get(cast<PointerType>(I->getType())));
1124 }
1125 
1126 // Handle load instructions. If the operand is a constant pointer to a constant
1127 // global, we can replace the load with the loaded constant value!
1128 void SCCPInstVisitor::visitLoadInst(LoadInst &I) {
1129  // If this load is of a struct or the load is volatile, just mark the result
1130  // as overdefined.
1131  if (I.getType()->isStructTy() || I.isVolatile())
1132  return (void)markOverdefined(&I);
1133 
1134  // resolvedUndefsIn might mark I as overdefined. Bail out, even if we would
1135  // discover a concrete value later.
1136  if (ValueState[&I].isOverdefined())
1137  return (void)markOverdefined(&I);
1138 
1139  ValueLatticeElement PtrVal = getValueState(I.getOperand(0));
1140  if (PtrVal.isUnknownOrUndef())
1141  return; // The pointer is not resolved yet!
1142 
1143  ValueLatticeElement &IV = ValueState[&I];
1144 
1145  if (isConstant(PtrVal)) {
1146  Constant *Ptr = getConstant(PtrVal);
1147 
1148  // load null is undefined.
1149  if (isa<ConstantPointerNull>(Ptr)) {
1150  if (NullPointerIsDefined(I.getFunction(), I.getPointerAddressSpace()))
1151  return (void)markOverdefined(IV, &I);
1152  else
1153  return;
1154  }
1155 
1156  // Transform load (constant global) into the value loaded.
1157  if (auto *GV = dyn_cast<GlobalVariable>(Ptr)) {
1158  if (!TrackedGlobals.empty()) {
1159  // If we are tracking this global, merge in the known value for it.
1160  auto It = TrackedGlobals.find(GV);
1161  if (It != TrackedGlobals.end()) {
1162  mergeInValue(IV, &I, It->second, getMaxWidenStepsOpts());
1163  return;
1164  }
1165  }
1166  }
1167 
1168  // Transform load from a constant into a constant if possible.
1169  if (Constant *C = ConstantFoldLoadFromConstPtr(Ptr, I.getType(), DL)) {
1170  if (isa<UndefValue>(C))
1171  return;
1172  return (void)markConstant(IV, &I, C);
1173  }
1174  }
1175 
1176  // Fall back to metadata.
1177  mergeInValue(&I, getValueFromMetadata(&I));
1178 }
1179 
1180 void SCCPInstVisitor::visitCallBase(CallBase &CB) {
1181  handleCallResult(CB);
1182  handleCallArguments(CB);
1183 }
1184 
1185 void SCCPInstVisitor::handleCallOverdefined(CallBase &CB) {
1186  Function *F = CB.getCalledFunction();
1187 
1188  // Void return and not tracking callee, just bail.
1189  if (CB.getType()->isVoidTy())
1190  return;
1191 
1192  // Always mark struct return as overdefined.
1193  if (CB.getType()->isStructTy())
1194  return (void)markOverdefined(&CB);
1195 
1196  // Otherwise, if we have a single return value case, and if the function is
1197  // a declaration, maybe we can constant fold it.
1198  if (F && F->isDeclaration() && canConstantFoldCallTo(&CB, F)) {
1200  for (const Use &A : CB.args()) {
1201  if (A.get()->getType()->isStructTy())
1202  return markOverdefined(&CB); // Can't handle struct args.
1203  ValueLatticeElement State = getValueState(A);
1204 
1205  if (State.isUnknownOrUndef())
1206  return; // Operands are not resolved yet.
1207  if (isOverdefined(State))
1208  return (void)markOverdefined(&CB);
1209  assert(isConstant(State) && "Unknown state!");
1210  Operands.push_back(getConstant(State));
1211  }
1212 
1213  if (isOverdefined(getValueState(&CB)))
1214  return (void)markOverdefined(&CB);
1215 
1216  // If we can constant fold this, mark the result of the call as a
1217  // constant.
1218  if (Constant *C = ConstantFoldCall(&CB, F, Operands, &GetTLI(*F))) {
1219  // call -> undef.
1220  if (isa<UndefValue>(C))
1221  return;
1222  return (void)markConstant(&CB, C);
1223  }
1224  }
1225 
1226  // Fall back to metadata.
1227  mergeInValue(&CB, getValueFromMetadata(&CB));
1228 }
1229 
1230 void SCCPInstVisitor::handleCallArguments(CallBase &CB) {
1231  Function *F = CB.getCalledFunction();
1232  // If this is a local function that doesn't have its address taken, mark its
1233  // entry block executable and merge in the actual arguments to the call into
1234  // the formal arguments of the function.
1235  if (!TrackingIncomingArguments.empty() &&
1236  TrackingIncomingArguments.count(F)) {
1237  markBlockExecutable(&F->front());
1238 
1239  // Propagate information from this call site into the callee.
1240  auto CAI = CB.arg_begin();
1241  for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end(); AI != E;
1242  ++AI, ++CAI) {
1243  // If this argument is byval, and if the function is not readonly, there
1244  // will be an implicit copy formed of the input aggregate.
1245  if (AI->hasByValAttr() && !F->onlyReadsMemory()) {
1246  markOverdefined(&*AI);
1247  continue;
1248  }
1249 
1250  if (auto *STy = dyn_cast<StructType>(AI->getType())) {
1251  for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
1252  ValueLatticeElement CallArg = getStructValueState(*CAI, i);
1253  mergeInValue(getStructValueState(&*AI, i), &*AI, CallArg,
1255  }
1256  } else
1257  mergeInValue(&*AI, getValueState(*CAI), getMaxWidenStepsOpts());
1258  }
1259  }
1260 }
1261 
1262 void SCCPInstVisitor::handleCallResult(CallBase &CB) {
1263  Function *F = CB.getCalledFunction();
1264 
1265  if (auto *II = dyn_cast<IntrinsicInst>(&CB)) {
1266  if (II->getIntrinsicID() == Intrinsic::ssa_copy) {
1267  if (ValueState[&CB].isOverdefined())
1268  return;
1269 
1270  Value *CopyOf = CB.getOperand(0);
1271  ValueLatticeElement CopyOfVal = getValueState(CopyOf);
1272  const auto *PI = getPredicateInfoFor(&CB);
1273  assert(PI && "Missing predicate info for ssa.copy");
1274 
1275  const Optional<PredicateConstraint> &Constraint = PI->getConstraint();
1276  if (!Constraint) {
1277  mergeInValue(ValueState[&CB], &CB, CopyOfVal);
1278  return;
1279  }
1280 
1281  CmpInst::Predicate Pred = Constraint->Predicate;
1282  Value *OtherOp = Constraint->OtherOp;
1283 
1284  // Wait until OtherOp is resolved.
1285  if (getValueState(OtherOp).isUnknown()) {
1286  addAdditionalUser(OtherOp, &CB);
1287  return;
1288  }
1289 
1290  // TODO: Actually filp MayIncludeUndef for the created range to false,
1291  // once most places in the optimizer respect the branches on
1292  // undef/poison are UB rule. The reason why the new range cannot be
1293  // undef is as follows below:
1294  // The new range is based on a branch condition. That guarantees that
1295  // neither of the compare operands can be undef in the branch targets,
1296  // unless we have conditions that are always true/false (e.g. icmp ule
1297  // i32, %a, i32_max). For the latter overdefined/empty range will be
1298  // inferred, but the branch will get folded accordingly anyways.
1299  bool MayIncludeUndef = !isa<PredicateAssume>(PI);
1300 
1301  ValueLatticeElement CondVal = getValueState(OtherOp);
1302  ValueLatticeElement &IV = ValueState[&CB];
1303  if (CondVal.isConstantRange() || CopyOfVal.isConstantRange()) {
1304  auto ImposedCR =
1305  ConstantRange::getFull(DL.getTypeSizeInBits(CopyOf->getType()));
1306 
1307  // Get the range imposed by the condition.
1308  if (CondVal.isConstantRange())
1310  Pred, CondVal.getConstantRange());
1311 
1312  // Combine range info for the original value with the new range from the
1313  // condition.
1314  auto CopyOfCR = CopyOfVal.isConstantRange()
1315  ? CopyOfVal.getConstantRange()
1316  : ConstantRange::getFull(
1317  DL.getTypeSizeInBits(CopyOf->getType()));
1318  auto NewCR = ImposedCR.intersectWith(CopyOfCR);
1319  // If the existing information is != x, do not use the information from
1320  // a chained predicate, as the != x information is more likely to be
1321  // helpful in practice.
1322  if (!CopyOfCR.contains(NewCR) && CopyOfCR.getSingleMissingElement())
1323  NewCR = CopyOfCR;
1324 
1325  addAdditionalUser(OtherOp, &CB);
1326  mergeInValue(IV, &CB,
1327  ValueLatticeElement::getRange(NewCR, MayIncludeUndef));
1328  return;
1329  } else if (Pred == CmpInst::ICMP_EQ && CondVal.isConstant()) {
1330  // For non-integer values or integer constant expressions, only
1331  // propagate equal constants.
1332  addAdditionalUser(OtherOp, &CB);
1333  mergeInValue(IV, &CB, CondVal);
1334  return;
1335  } else if (Pred == CmpInst::ICMP_NE && CondVal.isConstant() &&
1336  !MayIncludeUndef) {
1337  // Propagate inequalities.
1338  addAdditionalUser(OtherOp, &CB);
1339  mergeInValue(IV, &CB,
1341  return;
1342  }
1343 
1344  return (void)mergeInValue(IV, &CB, CopyOfVal);
1345  }
1346 
1347  if (ConstantRange::isIntrinsicSupported(II->getIntrinsicID())) {
1348  // Compute result range for intrinsics supported by ConstantRange.
1349  // Do this even if we don't know a range for all operands, as we may
1350  // still know something about the result range, e.g. of abs(x).
1352  for (Value *Op : II->args()) {
1353  const ValueLatticeElement &State = getValueState(Op);
1354  if (State.isConstantRange())
1355  OpRanges.push_back(State.getConstantRange());
1356  else
1357  OpRanges.push_back(
1358  ConstantRange::getFull(Op->getType()->getScalarSizeInBits()));
1359  }
1360 
1362  ConstantRange::intrinsic(II->getIntrinsicID(), OpRanges);
1363  return (void)mergeInValue(II, ValueLatticeElement::getRange(Result));
1364  }
1365  }
1366 
1367  // The common case is that we aren't tracking the callee, either because we
1368  // are not doing interprocedural analysis or the callee is indirect, or is
1369  // external. Handle these cases first.
1370  if (!F || F->isDeclaration())
1371  return handleCallOverdefined(CB);
1372 
1373  // If this is a single/zero retval case, see if we're tracking the function.
1374  if (auto *STy = dyn_cast<StructType>(F->getReturnType())) {
1375  if (!MRVFunctionsTracked.count(F))
1376  return handleCallOverdefined(CB); // Not tracking this callee.
1377 
1378  // If we are tracking this callee, propagate the result of the function
1379  // into this call site.
1380  for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
1381  mergeInValue(getStructValueState(&CB, i), &CB,
1382  TrackedMultipleRetVals[std::make_pair(F, i)],
1384  } else {
1385  auto TFRVI = TrackedRetVals.find(F);
1386  if (TFRVI == TrackedRetVals.end())
1387  return handleCallOverdefined(CB); // Not tracking this callee.
1388 
1389  // If so, propagate the return value of the callee into this call result.
1390  mergeInValue(&CB, TFRVI->second, getMaxWidenStepsOpts());
1391  }
1392 }
1393 
1395  // Process the work lists until they are empty!
1396  while (!BBWorkList.empty() || !InstWorkList.empty() ||
1397  !OverdefinedInstWorkList.empty()) {
1398  // Process the overdefined instruction's work list first, which drives other
1399  // things to overdefined more quickly.
1400  while (!OverdefinedInstWorkList.empty()) {
1401  Value *I = OverdefinedInstWorkList.pop_back_val();
1402 
1403  LLVM_DEBUG(dbgs() << "\nPopped off OI-WL: " << *I << '\n');
1404 
1405  // "I" got into the work list because it either made the transition from
1406  // bottom to constant, or to overdefined.
1407  //
1408  // Anything on this worklist that is overdefined need not be visited
1409  // since all of its users will have already been marked as overdefined
1410  // Update all of the users of this instruction's value.
1411  //
1412  markUsersAsChanged(I);
1413  }
1414 
1415  // Process the instruction work list.
1416  while (!InstWorkList.empty()) {
1417  Value *I = InstWorkList.pop_back_val();
1418 
1419  LLVM_DEBUG(dbgs() << "\nPopped off I-WL: " << *I << '\n');
1420 
1421  // "I" got into the work list because it made the transition from undef to
1422  // constant.
1423  //
1424  // Anything on this worklist that is overdefined need not be visited
1425  // since all of its users will have already been marked as overdefined.
1426  // Update all of the users of this instruction's value.
1427  //
1428  if (I->getType()->isStructTy() || !getValueState(I).isOverdefined())
1429  markUsersAsChanged(I);
1430  }
1431 
1432  // Process the basic block work list.
1433  while (!BBWorkList.empty()) {
1434  BasicBlock *BB = BBWorkList.pop_back_val();
1435 
1436  LLVM_DEBUG(dbgs() << "\nPopped off BBWL: " << *BB << '\n');
1437 
1438  // Notify all instructions in this basic block that they are newly
1439  // executable.
1440  visit(BB);
1441  }
1442  }
1443 }
1444 
1445 /// resolvedUndefsIn - While solving the dataflow for a function, we assume
1446 /// that branches on undef values cannot reach any of their successors.
1447 /// However, this is not a safe assumption. After we solve dataflow, this
1448 /// method should be use to handle this. If this returns true, the solver
1449 /// should be rerun.
1450 ///
1451 /// This method handles this by finding an unresolved branch and marking it one
1452 /// of the edges from the block as being feasible, even though the condition
1453 /// doesn't say it would otherwise be. This allows SCCP to find the rest of the
1454 /// CFG and only slightly pessimizes the analysis results (by marking one,
1455 /// potentially infeasible, edge feasible). This cannot usefully modify the
1456 /// constraints on the condition of the branch, as that would impact other users
1457 /// of the value.
1458 ///
1459 /// This scan also checks for values that use undefs. It conservatively marks
1460 /// them as overdefined.
1462  bool MadeChange = false;
1463  for (BasicBlock &BB : F) {
1464  if (!BBExecutable.count(&BB))
1465  continue;
1466 
1467  for (Instruction &I : BB) {
1468  // Look for instructions which produce undef values.
1469  if (I.getType()->isVoidTy())
1470  continue;
1471 
1472  if (auto *STy = dyn_cast<StructType>(I.getType())) {
1473  // Only a few things that can be structs matter for undef.
1474 
1475  // Tracked calls must never be marked overdefined in resolvedUndefsIn.
1476  if (auto *CB = dyn_cast<CallBase>(&I))
1477  if (Function *F = CB->getCalledFunction())
1478  if (MRVFunctionsTracked.count(F))
1479  continue;
1480 
1481  // extractvalue and insertvalue don't need to be marked; they are
1482  // tracked as precisely as their operands.
1483  if (isa<ExtractValueInst>(I) || isa<InsertValueInst>(I))
1484  continue;
1485  // Send the results of everything else to overdefined. We could be
1486  // more precise than this but it isn't worth bothering.
1487  for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
1488  ValueLatticeElement &LV = getStructValueState(&I, i);
1489  if (LV.isUnknownOrUndef()) {
1490  markOverdefined(LV, &I);
1491  MadeChange = true;
1492  }
1493  }
1494  continue;
1495  }
1496 
1497  ValueLatticeElement &LV = getValueState(&I);
1498  if (!LV.isUnknownOrUndef())
1499  continue;
1500 
1501  // There are two reasons a call can have an undef result
1502  // 1. It could be tracked.
1503  // 2. It could be constant-foldable.
1504  // Because of the way we solve return values, tracked calls must
1505  // never be marked overdefined in resolvedUndefsIn.
1506  if (auto *CB = dyn_cast<CallBase>(&I))
1507  if (Function *F = CB->getCalledFunction())
1508  if (TrackedRetVals.count(F))
1509  continue;
1510 
1511  if (isa<LoadInst>(I)) {
1512  // A load here means one of two things: a load of undef from a global,
1513  // a load from an unknown pointer. Either way, having it return undef
1514  // is okay.
1515  continue;
1516  }
1517 
1518  markOverdefined(&I);
1519  MadeChange = true;
1520  }
1521 
1522  // Check to see if we have a branch or switch on an undefined value. If so
1523  // we force the branch to go one way or the other to make the successor
1524  // values live. It doesn't really matter which way we force it.
1525  Instruction *TI = BB.getTerminator();
1526  if (auto *BI = dyn_cast<BranchInst>(TI)) {
1527  if (!BI->isConditional())
1528  continue;
1529  if (!getValueState(BI->getCondition()).isUnknownOrUndef())
1530  continue;
1531 
1532  // If the input to SCCP is actually branch on undef, fix the undef to
1533  // false.
1534  if (isa<UndefValue>(BI->getCondition())) {
1535  BI->setCondition(ConstantInt::getFalse(BI->getContext()));
1536  markEdgeExecutable(&BB, TI->getSuccessor(1));
1537  MadeChange = true;
1538  continue;
1539  }
1540 
1541  // Otherwise, it is a branch on a symbolic value which is currently
1542  // considered to be undef. Make sure some edge is executable, so a
1543  // branch on "undef" always flows somewhere.
1544  // FIXME: Distinguish between dead code and an LLVM "undef" value.
1545  BasicBlock *DefaultSuccessor = TI->getSuccessor(1);
1546  if (markEdgeExecutable(&BB, DefaultSuccessor))
1547  MadeChange = true;
1548 
1549  continue;
1550  }
1551 
1552  if (auto *IBR = dyn_cast<IndirectBrInst>(TI)) {
1553  // Indirect branch with no successor ?. Its ok to assume it branches
1554  // to no target.
1555  if (IBR->getNumSuccessors() < 1)
1556  continue;
1557 
1558  if (!getValueState(IBR->getAddress()).isUnknownOrUndef())
1559  continue;
1560 
1561  // If the input to SCCP is actually branch on undef, fix the undef to
1562  // the first successor of the indirect branch.
1563  if (isa<UndefValue>(IBR->getAddress())) {
1564  IBR->setAddress(BlockAddress::get(IBR->getSuccessor(0)));
1565  markEdgeExecutable(&BB, IBR->getSuccessor(0));
1566  MadeChange = true;
1567  continue;
1568  }
1569 
1570  // Otherwise, it is a branch on a symbolic value which is currently
1571  // considered to be undef. Make sure some edge is executable, so a
1572  // branch on "undef" always flows somewhere.
1573  // FIXME: IndirectBr on "undef" doesn't actually need to go anywhere:
1574  // we can assume the branch has undefined behavior instead.
1575  BasicBlock *DefaultSuccessor = IBR->getSuccessor(0);
1576  if (markEdgeExecutable(&BB, DefaultSuccessor))
1577  MadeChange = true;
1578 
1579  continue;
1580  }
1581 
1582  if (auto *SI = dyn_cast<SwitchInst>(TI)) {
1583  if (!SI->getNumCases() ||
1584  !getValueState(SI->getCondition()).isUnknownOrUndef())
1585  continue;
1586 
1587  // If the input to SCCP is actually switch on undef, fix the undef to
1588  // the first constant.
1589  if (isa<UndefValue>(SI->getCondition())) {
1590  SI->setCondition(SI->case_begin()->getCaseValue());
1591  markEdgeExecutable(&BB, SI->case_begin()->getCaseSuccessor());
1592  MadeChange = true;
1593  continue;
1594  }
1595 
1596  // Otherwise, it is a branch on a symbolic value which is currently
1597  // considered to be undef. Make sure some edge is executable, so a
1598  // branch on "undef" always flows somewhere.
1599  // FIXME: Distinguish between dead code and an LLVM "undef" value.
1600  BasicBlock *DefaultSuccessor = SI->case_begin()->getCaseSuccessor();
1601  if (markEdgeExecutable(&BB, DefaultSuccessor))
1602  MadeChange = true;
1603 
1604  continue;
1605  }
1606  }
1607 
1608  return MadeChange;
1609 }
1610 
1611 //===----------------------------------------------------------------------===//
1612 //
1613 // SCCPSolver implementations
1614 //
1616  const DataLayout &DL,
1617  std::function<const TargetLibraryInfo &(Function &)> GetTLI,
1618  LLVMContext &Ctx)
1619  : Visitor(new SCCPInstVisitor(DL, std::move(GetTLI), Ctx)) {}
1620 
1622 
1624  return Visitor->addAnalysis(F, std::move(A));
1625 }
1626 
1628  return Visitor->markBlockExecutable(BB);
1629 }
1630 
1632  return Visitor->getPredicateInfoFor(I);
1633 }
1634 
1635 DomTreeUpdater SCCPSolver::getDTU(Function &F) { return Visitor->getDTU(F); }
1636 
1638  Visitor->trackValueOfGlobalVariable(GV);
1639 }
1640 
1642  Visitor->addTrackedFunction(F);
1643 }
1644 
1646  Visitor->addToMustPreserveReturnsInFunctions(F);
1647 }
1648 
1650  return Visitor->mustPreserveReturn(F);
1651 }
1652 
1654  Visitor->addArgumentTrackedFunction(F);
1655 }
1656 
1658  return Visitor->isArgumentTrackedFunction(F);
1659 }
1660 
1661 void SCCPSolver::solve() { Visitor->solve(); }
1662 
1664  return Visitor->resolvedUndefsIn(F);
1665 }
1666 
1668  return Visitor->isBlockExecutable(BB);
1669 }
1670 
1672  return Visitor->isEdgeFeasible(From, To);
1673 }
1674 
1675 std::vector<ValueLatticeElement>
1677  return Visitor->getStructLatticeValueFor(V);
1678 }
1679 
1681  return Visitor->removeLatticeValueFor(V);
1682 }
1683 
1685  return Visitor->getLatticeValueFor(V);
1686 }
1687 
1690  return Visitor->getTrackedRetVals();
1691 }
1692 
1695  return Visitor->getTrackedGlobals();
1696 }
1697 
1699  return Visitor->getMRVFunctionsTracked();
1700 }
1701 
1702 void SCCPSolver::markOverdefined(Value *V) { Visitor->markOverdefined(V); }
1703 
1705  return Visitor->isStructLatticeConstant(F, STy);
1706 }
1707 
1709  return Visitor->getConstant(LV);
1710 }
1711 
1713  return Visitor->getArgumentTrackedFunctions();
1714 }
1715 
1717  Constant *C) {
1718  Visitor->markArgInFuncSpecialization(F, A, C);
1719 }
1720 
1722  Visitor->markFunctionUnreachable(F);
1723 }
1724 
1725 void SCCPSolver::visit(Instruction *I) { Visitor->visit(I); }
1726 
1727 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
This is an optimization pass for GlobalISel generic memory operations.
Definition: AllocatorList.h:23
llvm::CmpInst::ICMP_EQ
@ ICMP_EQ
equal
Definition: InstrTypes.h:742
llvm::ReturnInst
Return a value (possibly void), from a function.
Definition: Instructions.h:3019
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:113
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:721
llvm::SimplifyQuery
Definition: InstructionSimplify.h:94
T
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:62
Pass.h
llvm::SCCPSolver::getStructLatticeValueFor
std::vector< ValueLatticeElement > getStructLatticeValueFor(Value *V) const
Definition: SCCPSolver.cpp:1676
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:696
llvm::GlobalVariable
Definition: GlobalVariable.h:40
llvm::CmpInst::ICMP_NE
@ ICMP_NE
not equal
Definition: InstrTypes.h:743
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:1708
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
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:1627
llvm::CallBase::arg_begin
User::op_iterator arg_begin()
Return the iterator pointing to the beginning of the argument list.
Definition: InstrTypes.h:1318
llvm::SCCPSolver::visit
void visit(Instruction *I)
Definition: SCCPSolver.cpp:1725
llvm::getConstantRangeFromMetadata
ConstantRange getConstantRangeFromMetadata(const MDNode &RangeMD)
Parse out a conservative ConstantRange from !range metadata.
Definition: ConstantRange.cpp:1777
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:1653
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:914
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:207
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:1721
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:1461
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:1115
llvm::Instruction::getNumSuccessors
unsigned getNumSuccessors() const
Return the number of successors that this instruction has.
Definition: Instruction.cpp:771
llvm::Type::isSingleValueType
bool isSingleValueType() const
Return true if the type is a valid type for a register in codegen.
Definition: Type.h:248
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:2762
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:1702
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:1275
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:1398
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:1657
llvm::ExtractValueInst::getNumIndices
unsigned getNumIndices() const
Definition: Instructions.h:2482
llvm::ConstantRange::isSingleElement
bool isSingleElement() const
Return true if this set contains exactly one member.
Definition: ConstantRange.h:261
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:3049
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:1367
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::SCCPSolver::addAnalysis
void addAnalysis(Function &F, AnalysisResultsForFn A)
Definition: SCCPSolver.cpp:1623
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:925
llvm::SCCPSolver::isStructLatticeConstant
bool isStructLatticeConstant(Function *F, StructType *STy)
Definition: SCCPSolver.cpp:1704
llvm::Instruction::getSuccessor
BasicBlock * getSuccessor(unsigned Idx) const
Return the specified successor. This instruction must be a terminator.
Definition: Instruction.cpp:783
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:2758
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:931
Operands
mir Rename Register Operands
Definition: MIRNamerPass.cpp:78
llvm::InvokeInst
Invoke instruction.
Definition: Instructions.h:3778
llvm::CmpInst
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:711
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:1689
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:702
llvm::DenseSet< Edge >
llvm::PredicateBase
Definition: PredicateInfo.h:82
llvm::SCCPSolver::visitCall
void visitCall(CallInst &I)
Definition: SCCPSolver.cpp:1727
llvm::SCCPInstVisitor::solve
void solve()
Definition: SCCPSolver.cpp:1394
llvm::SCCPSolver::getLatticeValueFor
const ValueLatticeElement & getLatticeValueFor(Value *V) const
Definition: SCCPSolver.cpp:1684
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:204
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:1782
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:5397
llvm::CallBrInst
CallBr instruction, tracking function calls that may not return control but instead transfer it to a ...
Definition: Instructions.h:3987
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:2312
llvm::SCCPSolver::getPredicateInfoFor
const PredicateBase * getPredicateInfoFor(Instruction *I)
Definition: SCCPSolver.cpp:1631
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:2267
llvm::ExtractValueInst::idx_begin
idx_iterator idx_begin() const
Definition: Instructions.h:2462
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:1694
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:1639
SI
StandardInstrumentations SI(Debug, VerifyEach)
llvm::SelectInst
This class represents the LLVM 'select' instruction.
Definition: Instructions.h:1750
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:906
llvm::SCCPSolver::~SCCPSolver
~SCCPSolver()
Definition: SCCPSolver.cpp:1621
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:1635
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:118
llvm::SCCPSolver::SCCPSolver
SCCPSolver(const DataLayout &DL, std::function< const TargetLibraryInfo &(Function &)> GetTLI, LLVMContext &Ctx)
Definition: SCCPSolver.cpp:1615
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:134
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:420
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
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:1680
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:1649
llvm::CastInst
This is the base class for all instructions that perform data casts.
Definition: InstrTypes.h:431
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:309
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:1667
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:880
llvm::ConstantFoldLoadFromConstPtr
Constant * ConstantFoldLoadFromConstPtr(Constant *C, Type *Ty, APInt Offset, const DataLayout &DL)
Return the value that a load from C with offset Offset would produce if it is constant and determinab...
Definition: ConstantFolding.cpp:692
llvm::SCCPSolver::isEdgeFeasible
bool isEdgeFeasible(BasicBlock *From, BasicBlock *To) const
Definition: SCCPSolver.cpp:1671
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:4226
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:324
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:2413
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:221
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:1663
llvm::ExtractValueInst::getAggregateOperand
Value * getAggregateOperand()
Definition: Instructions.h:2468
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:431
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:474
llvm::SCCPSolver::addToMustPreserveReturnsInFunctions
void addToMustPreserveReturnsInFunctions(Function *F)
Add function to the list of functions whose return cannot be modified.
Definition: SCCPSolver.cpp:1645
llvm::Type::isStructTy
bool isStructTy() const
True if this is an instance of StructType.
Definition: Type.h:211
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:1716
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:1834
llvm::PHINode::getIncomingBlock
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Definition: Instructions.h:2782
llvm::max
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:340
llvm::PHINode
Definition: Instructions.h:2666
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:1637
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:1176
llvm::SmallPtrSetImpl
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:343
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:1487
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:4742
llvm::SCCPSolver::solve
void solve()
Solve - Solve for constants and executable blocks.
Definition: SCCPSolver.cpp:1661
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:1970
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:1641
llvm::InsertValueInst
This instruction inserts a struct field of array element value into an aggregate value.
Definition: Instructions.h:2524
llvm::CatchSwitchInst
Definition: Instructions.h:4283
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:74
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:1698
llvm::CallBase::args
iterator_range< User::op_iterator > args()
Iteration adapter for range-for loops.
Definition: InstrTypes.h:1334
llvm::SCCPSolver::getArgumentTrackedFunctions
SmallPtrSetImpl< Function * > & getArgumentTrackedFunctions()
Return a reference to the set of argument tracked functions.
Definition: SCCPSolver.cpp:1712
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::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44
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