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