LLVM  16.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
212  LV.markConstant(Elt); // Constants are constant.
213  }
214 
215  // All others are underdefined by default.
216  return LV;
217  }
218 
219  /// markEdgeExecutable - Mark a basic block as executable, adding it to the BB
220  /// work list if it is not already executable.
221  bool markEdgeExecutable(BasicBlock *Source, BasicBlock *Dest);
222 
223  // getFeasibleSuccessors - Return a vector of booleans to indicate which
224  // successors are reachable from a given terminator instruction.
225  void getFeasibleSuccessors(Instruction &TI, SmallVectorImpl<bool> &Succs);
226 
227  // OperandChangedState - This method is invoked on all of the users of an
228  // instruction that was just changed state somehow. Based on this
229  // information, we need to update the specified user of this instruction.
230  void operandChangedState(Instruction *I) {
231  if (BBExecutable.count(I->getParent())) // Inst is executable?
232  visit(*I);
233  }
234 
235  // Add U as additional user of V.
236  void addAdditionalUser(Value *V, User *U) {
237  auto Iter = AdditionalUsers.insert({V, {}});
238  Iter.first->second.insert(U);
239  }
240 
241  // Mark I's users as changed, including AdditionalUsers.
242  void markUsersAsChanged(Value *I) {
243  // Functions include their arguments in the use-list. Changed function
244  // values mean that the result of the function changed. We only need to
245  // update the call sites with the new function result and do not have to
246  // propagate the call arguments.
247  if (isa<Function>(I)) {
248  for (User *U : I->users()) {
249  if (auto *CB = dyn_cast<CallBase>(U))
250  handleCallResult(*CB);
251  }
252  } else {
253  for (User *U : I->users())
254  if (auto *UI = dyn_cast<Instruction>(U))
255  operandChangedState(UI);
256  }
257 
258  auto Iter = AdditionalUsers.find(I);
259  if (Iter != AdditionalUsers.end()) {
260  // Copy additional users before notifying them of changes, because new
261  // users may be added, potentially invalidating the iterator.
263  for (User *U : Iter->second)
264  if (auto *UI = dyn_cast<Instruction>(U))
265  ToNotify.push_back(UI);
266  for (Instruction *UI : ToNotify)
267  operandChangedState(UI);
268  }
269  }
270  void handleCallOverdefined(CallBase &CB);
271  void handleCallResult(CallBase &CB);
272  void handleCallArguments(CallBase &CB);
273 
274 private:
276 
277  // visit implementations - Something changed in this instruction. Either an
278  // operand made a transition, or the instruction is newly executable. Change
279  // the value type of I to reflect these changes if appropriate.
280  void visitPHINode(PHINode &I);
281 
282  // Terminators
283 
284  void visitReturnInst(ReturnInst &I);
285  void visitTerminator(Instruction &TI);
286 
287  void visitCastInst(CastInst &I);
288  void visitSelectInst(SelectInst &I);
289  void visitUnaryOperator(Instruction &I);
290  void visitBinaryOperator(Instruction &I);
291  void visitCmpInst(CmpInst &I);
292  void visitExtractValueInst(ExtractValueInst &EVI);
293  void visitInsertValueInst(InsertValueInst &IVI);
294 
295  void visitCatchSwitchInst(CatchSwitchInst &CPI) {
296  markOverdefined(&CPI);
297  visitTerminator(CPI);
298  }
299 
300  // Instructions that cannot be folded away.
301 
302  void visitStoreInst(StoreInst &I);
303  void visitLoadInst(LoadInst &I);
304  void visitGetElementPtrInst(GetElementPtrInst &I);
305 
306  void visitInvokeInst(InvokeInst &II) {
307  visitCallBase(II);
308  visitTerminator(II);
309  }
310 
311  void visitCallBrInst(CallBrInst &CBI) {
312  visitCallBase(CBI);
313  visitTerminator(CBI);
314  }
315 
316  void visitCallBase(CallBase &CB);
317  void visitResumeInst(ResumeInst &I) { /*returns void*/
318  }
319  void visitUnreachableInst(UnreachableInst &I) { /*returns void*/
320  }
321  void visitFenceInst(FenceInst &I) { /*returns void*/
322  }
323 
324  void visitInstruction(Instruction &I);
325 
326 public:
328  AnalysisResults.insert({&F, std::move(A)});
329  }
330 
331  void visitCallInst(CallInst &I) { visitCallBase(I); }
332 
334 
336  auto A = AnalysisResults.find(I->getParent()->getParent());
337  if (A == AnalysisResults.end())
338  return nullptr;
339  return A->second.PredInfo->getPredicateInfoFor(I);
340  }
341 
343  auto A = AnalysisResults.find(&F);
344  assert(A != AnalysisResults.end() && A->second.LI &&
345  "Need LoopInfo analysis results for function.");
346  return *A->second.LI;
347  }
348 
350  auto A = AnalysisResults.find(&F);
351  assert(A != AnalysisResults.end() && "Need analysis results for function.");
352  return {A->second.DT, A->second.PDT, DomTreeUpdater::UpdateStrategy::Lazy};
353  }
354 
356  std::function<const TargetLibraryInfo &(Function &)> GetTLI,
357  LLVMContext &Ctx)
358  : DL(DL), GetTLI(GetTLI), Ctx(Ctx) {}
359 
361  // We only track the contents of scalar globals.
362  if (GV->getValueType()->isSingleValueType()) {
363  ValueLatticeElement &IV = TrackedGlobals[GV];
364  IV.markConstant(GV->getInitializer());
365  }
366  }
367 
369  // Add an entry, F -> undef.
370  if (auto *STy = dyn_cast<StructType>(F->getReturnType())) {
371  MRVFunctionsTracked.insert(F);
372  for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
373  TrackedMultipleRetVals.insert(
374  std::make_pair(std::make_pair(F, i), ValueLatticeElement()));
375  } else if (!F->getReturnType()->isVoidTy())
376  TrackedRetVals.insert(std::make_pair(F, ValueLatticeElement()));
377  }
378 
380  MustPreserveReturnsInFunctions.insert(F);
381  }
382 
384  return MustPreserveReturnsInFunctions.count(F);
385  }
386 
388  TrackingIncomingArguments.insert(F);
389  }
390 
392  return TrackingIncomingArguments.count(F);
393  }
394 
395  void solve();
396 
397  bool resolvedUndefsIn(Function &F);
398 
400  return BBExecutable.count(BB);
401  }
402 
403  bool isEdgeFeasible(BasicBlock *From, BasicBlock *To) const;
404 
405  std::vector<ValueLatticeElement> getStructLatticeValueFor(Value *V) const {
406  std::vector<ValueLatticeElement> StructValues;
407  auto *STy = dyn_cast<StructType>(V->getType());
408  assert(STy && "getStructLatticeValueFor() can be called only on structs");
409  for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
410  auto I = StructValueState.find(std::make_pair(V, i));
411  assert(I != StructValueState.end() && "Value not in valuemap!");
412  StructValues.push_back(I->second);
413  }
414  return StructValues;
415  }
416 
417  void removeLatticeValueFor(Value *V) { ValueState.erase(V); }
418 
420  assert(!V->getType()->isStructTy() &&
421  "Should use getStructLatticeValueFor");
423  ValueState.find(V);
424  assert(I != ValueState.end() &&
425  "V not found in ValueState nor Paramstate map!");
426  return I->second;
427  }
428 
430  return TrackedRetVals;
431  }
432 
434  return TrackedGlobals;
435  }
436 
438  return MRVFunctionsTracked;
439  }
440 
442  if (auto *STy = dyn_cast<StructType>(V->getType()))
443  for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
444  markOverdefined(getStructValueState(V, i), V);
445  else
446  markOverdefined(ValueState[V], V);
447  }
448 
450 
451  Constant *getConstant(const ValueLatticeElement &LV) const;
453 
455  return TrackingIncomingArguments;
456  }
457 
460 
462  for (auto &BB : *F)
463  BBExecutable.erase(&BB);
464  }
465 };
466 
467 } // namespace llvm
468 
470  if (!BBExecutable.insert(BB).second)
471  return false;
472  LLVM_DEBUG(dbgs() << "Marking Block Executable: " << BB->getName() << '\n');
473  BBWorkList.push_back(BB); // Add the block to the work list!
474  return true;
475 }
476 
477 void SCCPInstVisitor::pushToWorkList(ValueLatticeElement &IV, Value *V) {
478  if (IV.isOverdefined())
479  return OverdefinedInstWorkList.push_back(V);
480  InstWorkList.push_back(V);
481 }
482 
483 void SCCPInstVisitor::pushToWorkListMsg(ValueLatticeElement &IV, Value *V) {
484  LLVM_DEBUG(dbgs() << "updated " << IV << ": " << *V << '\n');
485  pushToWorkList(IV, V);
486 }
487 
488 bool SCCPInstVisitor::markConstant(ValueLatticeElement &IV, Value *V,
489  Constant *C, bool MayIncludeUndef) {
490  if (!IV.markConstant(C, MayIncludeUndef))
491  return false;
492  LLVM_DEBUG(dbgs() << "markConstant: " << *C << ": " << *V << '\n');
493  pushToWorkList(IV, V);
494  return true;
495 }
496 
497 bool SCCPInstVisitor::markOverdefined(ValueLatticeElement &IV, Value *V) {
498  if (!IV.markOverdefined())
499  return false;
500 
501  LLVM_DEBUG(dbgs() << "markOverdefined: ";
502  if (auto *F = dyn_cast<Function>(V)) dbgs()
503  << "Function '" << F->getName() << "'\n";
504  else dbgs() << *V << '\n');
505  // Only instructions go on the work list
506  pushToWorkList(IV, V);
507  return true;
508 }
509 
511  for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
512  const auto &It = TrackedMultipleRetVals.find(std::make_pair(F, i));
513  assert(It != TrackedMultipleRetVals.end());
514  ValueLatticeElement LV = It->second;
515  if (!isConstant(LV))
516  return false;
517  }
518  return true;
519 }
520 
522  if (LV.isConstant())
523  return LV.getConstant();
524 
525  if (LV.isConstantRange()) {
526  const auto &CR = LV.getConstantRange();
527  if (CR.getSingleElement())
528  return ConstantInt::get(Ctx, *CR.getSingleElement());
529  }
530  return nullptr;
531 }
532 
535  Type *Ty) const {
536  assert(Ty->isIntOrIntVectorTy() && "Should be int or int vector");
537  if (LV.isConstantRange())
538  return LV.getConstantRange();
539  return ConstantRange::getFull(Ty->getScalarSizeInBits());
540 }
541 
544  assert(!Args.empty() && "Specialization without arguments");
545  assert(F->arg_size() == Args[0].Formal->getParent()->arg_size() &&
546  "Functions should have the same number of arguments");
547 
548  auto Iter = Args.begin();
549  Argument *NewArg = F->arg_begin();
550  Argument *OldArg = Args[0].Formal->getParent()->arg_begin();
551  for (auto End = F->arg_end(); NewArg != End; ++NewArg, ++OldArg) {
552 
553  LLVM_DEBUG(dbgs() << "SCCP: Marking argument "
554  << NewArg->getNameOrAsOperand() << "\n");
555 
556  if (Iter != Args.end() && OldArg == Iter->Formal) {
557  // Mark the argument constants in the new function.
558  markConstant(NewArg, Iter->Actual);
559  ++Iter;
560  } else if (ValueState.count(OldArg)) {
561  // For the remaining arguments in the new function, copy the lattice state
562  // over from the old function.
563  //
564  // Note: This previously looked like this:
565  // ValueState[NewArg] = ValueState[OldArg];
566  // This is incorrect because the DenseMap class may resize the underlying
567  // memory when inserting `NewArg`, which will invalidate the reference to
568  // `OldArg`. Instead, we make sure `NewArg` exists before setting it.
569  auto &NewValue = ValueState[NewArg];
570  NewValue = ValueState[OldArg];
571  pushToWorkList(NewValue, NewArg);
572  }
573  }
574 }
575 
576 void SCCPInstVisitor::visitInstruction(Instruction &I) {
577  // All the instructions we don't do any special handling for just
578  // go to overdefined.
579  LLVM_DEBUG(dbgs() << "SCCP: Don't know how to handle: " << I << '\n');
580  markOverdefined(&I);
581 }
582 
583 bool SCCPInstVisitor::mergeInValue(ValueLatticeElement &IV, Value *V,
584  ValueLatticeElement MergeWithV,
586  if (IV.mergeIn(MergeWithV, Opts)) {
587  pushToWorkList(IV, V);
588  LLVM_DEBUG(dbgs() << "Merged " << MergeWithV << " into " << *V << " : "
589  << IV << "\n");
590  return true;
591  }
592  return false;
593 }
594 
595 bool SCCPInstVisitor::markEdgeExecutable(BasicBlock *Source, BasicBlock *Dest) {
596  if (!KnownFeasibleEdges.insert(Edge(Source, Dest)).second)
597  return false; // This edge is already known to be executable!
598 
599  if (!markBlockExecutable(Dest)) {
600  // If the destination is already executable, we just made an *edge*
601  // feasible that wasn't before. Revisit the PHI nodes in the block
602  // because they have potentially new operands.
603  LLVM_DEBUG(dbgs() << "Marking Edge Executable: " << Source->getName()
604  << " -> " << Dest->getName() << '\n');
605 
606  for (PHINode &PN : Dest->phis())
607  visitPHINode(PN);
608  }
609  return true;
610 }
611 
612 // getFeasibleSuccessors - Return a vector of booleans to indicate which
613 // successors are reachable from a given terminator instruction.
614 void SCCPInstVisitor::getFeasibleSuccessors(Instruction &TI,
615  SmallVectorImpl<bool> &Succs) {
616  Succs.resize(TI.getNumSuccessors());
617  if (auto *BI = dyn_cast<BranchInst>(&TI)) {
618  if (BI->isUnconditional()) {
619  Succs[0] = true;
620  return;
621  }
622 
623  ValueLatticeElement BCValue = getValueState(BI->getCondition());
624  ConstantInt *CI = getConstantInt(BCValue);
625  if (!CI) {
626  // Overdefined condition variables, and branches on unfoldable constant
627  // conditions, mean the branch could go either way.
628  if (!BCValue.isUnknownOrUndef())
629  Succs[0] = Succs[1] = true;
630  return;
631  }
632 
633  // Constant condition variables mean the branch can only go a single way.
634  Succs[CI->isZero()] = true;
635  return;
636  }
637 
638  // Unwinding instructions successors are always executable.
639  if (TI.isExceptionalTerminator()) {
640  Succs.assign(TI.getNumSuccessors(), true);
641  return;
642  }
643 
644  if (auto *SI = dyn_cast<SwitchInst>(&TI)) {
645  if (!SI->getNumCases()) {
646  Succs[0] = true;
647  return;
648  }
649  const ValueLatticeElement &SCValue = getValueState(SI->getCondition());
650  if (ConstantInt *CI = getConstantInt(SCValue)) {
651  Succs[SI->findCaseValue(CI)->getSuccessorIndex()] = true;
652  return;
653  }
654 
655  // TODO: Switch on undef is UB. Stop passing false once the rest of LLVM
656  // is ready.
657  if (SCValue.isConstantRange(/*UndefAllowed=*/false)) {
658  const ConstantRange &Range = SCValue.getConstantRange();
659  for (const auto &Case : SI->cases()) {
660  const APInt &CaseValue = Case.getCaseValue()->getValue();
661  if (Range.contains(CaseValue))
662  Succs[Case.getSuccessorIndex()] = true;
663  }
664 
665  // TODO: Determine whether default case is reachable.
666  Succs[SI->case_default()->getSuccessorIndex()] = true;
667  return;
668  }
669 
670  // Overdefined or unknown condition? All destinations are executable!
671  if (!SCValue.isUnknownOrUndef())
672  Succs.assign(TI.getNumSuccessors(), true);
673  return;
674  }
675 
676  // In case of indirect branch and its address is a blockaddress, we mark
677  // the target as executable.
678  if (auto *IBR = dyn_cast<IndirectBrInst>(&TI)) {
679  // Casts are folded by visitCastInst.
680  ValueLatticeElement IBRValue = getValueState(IBR->getAddress());
681  BlockAddress *Addr = dyn_cast_or_null<BlockAddress>(getConstant(IBRValue));
682  if (!Addr) { // Overdefined or unknown condition?
683  // All destinations are executable!
684  if (!IBRValue.isUnknownOrUndef())
685  Succs.assign(TI.getNumSuccessors(), true);
686  return;
687  }
688 
689  BasicBlock *T = Addr->getBasicBlock();
690  assert(Addr->getFunction() == T->getParent() &&
691  "Block address of a different function ?");
692  for (unsigned i = 0; i < IBR->getNumSuccessors(); ++i) {
693  // This is the target.
694  if (IBR->getDestination(i) == T) {
695  Succs[i] = true;
696  return;
697  }
698  }
699 
700  // If we didn't find our destination in the IBR successor list, then we
701  // have undefined behavior. Its ok to assume no successor is executable.
702  return;
703  }
704 
705  // In case of callbr, we pessimistically assume that all successors are
706  // feasible.
707  if (isa<CallBrInst>(&TI)) {
708  Succs.assign(TI.getNumSuccessors(), true);
709  return;
710  }
711 
712  LLVM_DEBUG(dbgs() << "Unknown terminator instruction: " << TI << '\n');
713  llvm_unreachable("SCCP: Don't know how to handle this terminator!");
714 }
715 
716 // isEdgeFeasible - Return true if the control flow edge from the 'From' basic
717 // block to the 'To' basic block is currently feasible.
719  // Check if we've called markEdgeExecutable on the edge yet. (We could
720  // be more aggressive and try to consider edges which haven't been marked
721  // yet, but there isn't any need.)
722  return KnownFeasibleEdges.count(Edge(From, To));
723 }
724 
725 // visit Implementations - Something changed in this instruction, either an
726 // operand made a transition, or the instruction is newly executable. Change
727 // the value type of I to reflect these changes if appropriate. This method
728 // makes sure to do the following actions:
729 //
730 // 1. If a phi node merges two constants in, and has conflicting value coming
731 // from different branches, or if the PHI node merges in an overdefined
732 // value, then the PHI node becomes overdefined.
733 // 2. If a phi node merges only constants in, and they all agree on value, the
734 // PHI node becomes a constant value equal to that.
735 // 3. If V <- x (op) y && isConstant(x) && isConstant(y) V = Constant
736 // 4. If V <- x (op) y && (isOverdefined(x) || isOverdefined(y)) V = Overdefined
737 // 5. If V <- MEM or V <- CALL or V <- (unknown) then V = Overdefined
738 // 6. If a conditional branch has a value that is constant, make the selected
739 // destination executable
740 // 7. If a conditional branch has a value that is overdefined, make all
741 // successors executable.
742 void SCCPInstVisitor::visitPHINode(PHINode &PN) {
743  // If this PN returns a struct, just mark the result overdefined.
744  // TODO: We could do a lot better than this if code actually uses this.
745  if (PN.getType()->isStructTy())
746  return (void)markOverdefined(&PN);
747 
748  if (getValueState(&PN).isOverdefined())
749  return; // Quick exit
750 
751  // Super-extra-high-degree PHI nodes are unlikely to ever be marked constant,
752  // and slow us down a lot. Just mark them overdefined.
753  if (PN.getNumIncomingValues() > 64)
754  return (void)markOverdefined(&PN);
755 
756  unsigned NumActiveIncoming = 0;
757 
758  // Look at all of the executable operands of the PHI node. If any of them
759  // are overdefined, the PHI becomes overdefined as well. If they are all
760  // constant, and they agree with each other, the PHI becomes the identical
761  // constant. If they are constant and don't agree, the PHI is a constant
762  // range. If there are no executable operands, the PHI remains unknown.
763  ValueLatticeElement PhiState = getValueState(&PN);
764  for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) {
765  if (!isEdgeFeasible(PN.getIncomingBlock(i), PN.getParent()))
766  continue;
767 
768  ValueLatticeElement IV = getValueState(PN.getIncomingValue(i));
769  PhiState.mergeIn(IV);
770  NumActiveIncoming++;
771  if (PhiState.isOverdefined())
772  break;
773  }
774 
775  // We allow up to 1 range extension per active incoming value and one
776  // additional extension. Note that we manually adjust the number of range
777  // extensions to match the number of active incoming values. This helps to
778  // limit multiple extensions caused by the same incoming value, if other
779  // incoming values are equal.
780  mergeInValue(&PN, PhiState,
781  ValueLatticeElement::MergeOptions().setMaxWidenSteps(
782  NumActiveIncoming + 1));
783  ValueLatticeElement &PhiStateRef = getValueState(&PN);
784  PhiStateRef.setNumRangeExtensions(
785  std::max(NumActiveIncoming, PhiStateRef.getNumRangeExtensions()));
786 }
787 
788 void SCCPInstVisitor::visitReturnInst(ReturnInst &I) {
789  if (I.getNumOperands() == 0)
790  return; // ret void
791 
792  Function *F = I.getParent()->getParent();
793  Value *ResultOp = I.getOperand(0);
794 
795  // If we are tracking the return value of this function, merge it in.
796  if (!TrackedRetVals.empty() && !ResultOp->getType()->isStructTy()) {
797  auto TFRVI = TrackedRetVals.find(F);
798  if (TFRVI != TrackedRetVals.end()) {
799  mergeInValue(TFRVI->second, F, getValueState(ResultOp));
800  return;
801  }
802  }
803 
804  // Handle functions that return multiple values.
805  if (!TrackedMultipleRetVals.empty()) {
806  if (auto *STy = dyn_cast<StructType>(ResultOp->getType()))
807  if (MRVFunctionsTracked.count(F))
808  for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
809  mergeInValue(TrackedMultipleRetVals[std::make_pair(F, i)], F,
810  getStructValueState(ResultOp, i));
811  }
812 }
813 
814 void SCCPInstVisitor::visitTerminator(Instruction &TI) {
815  SmallVector<bool, 16> SuccFeasible;
816  getFeasibleSuccessors(TI, SuccFeasible);
817 
818  BasicBlock *BB = TI.getParent();
819 
820  // Mark all feasible successors executable.
821  for (unsigned i = 0, e = SuccFeasible.size(); i != e; ++i)
822  if (SuccFeasible[i])
823  markEdgeExecutable(BB, TI.getSuccessor(i));
824 }
825 
826 void SCCPInstVisitor::visitCastInst(CastInst &I) {
827  // ResolvedUndefsIn might mark I as overdefined. Bail out, even if we would
828  // discover a concrete value later.
829  if (ValueState[&I].isOverdefined())
830  return;
831 
832  ValueLatticeElement OpSt = getValueState(I.getOperand(0));
833  if (OpSt.isUnknownOrUndef())
834  return;
835 
836  if (Constant *OpC = getConstant(OpSt)) {
837  // Fold the constant as we build.
838  Constant *C = ConstantFoldCastOperand(I.getOpcode(), OpC, I.getType(), DL);
839  markConstant(&I, C);
840  } else if (I.getDestTy()->isIntegerTy() &&
841  I.getSrcTy()->isIntOrIntVectorTy()) {
842  auto &LV = getValueState(&I);
843  ConstantRange OpRange = getConstantRange(OpSt, I.getSrcTy());
844 
845  Type *DestTy = I.getDestTy();
846  // Vectors where all elements have the same known constant range are treated
847  // as a single constant range in the lattice. When bitcasting such vectors,
848  // there is a mis-match between the width of the lattice value (single
849  // constant range) and the original operands (vector). Go to overdefined in
850  // that case.
851  if (I.getOpcode() == Instruction::BitCast &&
852  I.getOperand(0)->getType()->isVectorTy() &&
853  OpRange.getBitWidth() < DL.getTypeSizeInBits(DestTy))
854  return (void)markOverdefined(&I);
855 
856  ConstantRange Res =
857  OpRange.castOp(I.getOpcode(), DL.getTypeSizeInBits(DestTy));
858  mergeInValue(LV, &I, ValueLatticeElement::getRange(Res));
859  } else
860  markOverdefined(&I);
861 }
862 
863 void SCCPInstVisitor::visitExtractValueInst(ExtractValueInst &EVI) {
864  // If this returns a struct, mark all elements over defined, we don't track
865  // structs in structs.
866  if (EVI.getType()->isStructTy())
867  return (void)markOverdefined(&EVI);
868 
869  // resolvedUndefsIn might mark I as overdefined. Bail out, even if we would
870  // discover a concrete value later.
871  if (ValueState[&EVI].isOverdefined())
872  return (void)markOverdefined(&EVI);
873 
874  // If this is extracting from more than one level of struct, we don't know.
875  if (EVI.getNumIndices() != 1)
876  return (void)markOverdefined(&EVI);
877 
878  Value *AggVal = EVI.getAggregateOperand();
879  if (AggVal->getType()->isStructTy()) {
880  unsigned i = *EVI.idx_begin();
881  ValueLatticeElement EltVal = getStructValueState(AggVal, i);
882  mergeInValue(getValueState(&EVI), &EVI, EltVal);
883  } else {
884  // Otherwise, must be extracting from an array.
885  return (void)markOverdefined(&EVI);
886  }
887 }
888 
889 void SCCPInstVisitor::visitInsertValueInst(InsertValueInst &IVI) {
890  auto *STy = dyn_cast<StructType>(IVI.getType());
891  if (!STy)
892  return (void)markOverdefined(&IVI);
893 
894  // resolvedUndefsIn might mark I as overdefined. Bail out, even if we would
895  // discover a concrete value later.
896  if (isOverdefined(ValueState[&IVI]))
897  return (void)markOverdefined(&IVI);
898 
899  // If this has more than one index, we can't handle it, drive all results to
900  // undef.
901  if (IVI.getNumIndices() != 1)
902  return (void)markOverdefined(&IVI);
903 
904  Value *Aggr = IVI.getAggregateOperand();
905  unsigned Idx = *IVI.idx_begin();
906 
907  // Compute the result based on what we're inserting.
908  for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
909  // This passes through all values that aren't the inserted element.
910  if (i != Idx) {
911  ValueLatticeElement EltVal = getStructValueState(Aggr, i);
912  mergeInValue(getStructValueState(&IVI, i), &IVI, EltVal);
913  continue;
914  }
915 
916  Value *Val = IVI.getInsertedValueOperand();
917  if (Val->getType()->isStructTy())
918  // We don't track structs in structs.
919  markOverdefined(getStructValueState(&IVI, i), &IVI);
920  else {
921  ValueLatticeElement InVal = getValueState(Val);
922  mergeInValue(getStructValueState(&IVI, i), &IVI, InVal);
923  }
924  }
925 }
926 
927 void SCCPInstVisitor::visitSelectInst(SelectInst &I) {
928  // If this select returns a struct, just mark the result overdefined.
929  // TODO: We could do a lot better than this if code actually uses this.
930  if (I.getType()->isStructTy())
931  return (void)markOverdefined(&I);
932 
933  // resolvedUndefsIn might mark I as overdefined. Bail out, even if we would
934  // discover a concrete value later.
935  if (ValueState[&I].isOverdefined())
936  return (void)markOverdefined(&I);
937 
938  ValueLatticeElement CondValue = getValueState(I.getCondition());
939  if (CondValue.isUnknownOrUndef())
940  return;
941 
942  if (ConstantInt *CondCB = getConstantInt(CondValue)) {
943  Value *OpVal = CondCB->isZero() ? I.getFalseValue() : I.getTrueValue();
944  mergeInValue(&I, getValueState(OpVal));
945  return;
946  }
947 
948  // Otherwise, the condition is overdefined or a constant we can't evaluate.
949  // See if we can produce something better than overdefined based on the T/F
950  // value.
951  ValueLatticeElement TVal = getValueState(I.getTrueValue());
952  ValueLatticeElement FVal = getValueState(I.getFalseValue());
953 
954  bool Changed = ValueState[&I].mergeIn(TVal);
955  Changed |= ValueState[&I].mergeIn(FVal);
956  if (Changed)
957  pushToWorkListMsg(ValueState[&I], &I);
958 }
959 
960 // Handle Unary Operators.
961 void SCCPInstVisitor::visitUnaryOperator(Instruction &I) {
962  ValueLatticeElement V0State = getValueState(I.getOperand(0));
963 
964  ValueLatticeElement &IV = ValueState[&I];
965  // resolvedUndefsIn might mark I as overdefined. Bail out, even if we would
966  // discover a concrete value later.
967  if (isOverdefined(IV))
968  return (void)markOverdefined(&I);
969 
970  // If something is unknown/undef, wait for it to resolve.
971  if (V0State.isUnknownOrUndef())
972  return;
973 
974  if (isConstant(V0State))
975  if (Constant *C = ConstantFoldUnaryOpOperand(I.getOpcode(),
976  getConstant(V0State), DL))
977  return (void)markConstant(IV, &I, C);
978 
979  markOverdefined(&I);
980 }
981 
982 // Handle Binary Operators.
983 void SCCPInstVisitor::visitBinaryOperator(Instruction &I) {
984  ValueLatticeElement V1State = getValueState(I.getOperand(0));
985  ValueLatticeElement V2State = getValueState(I.getOperand(1));
986 
987  ValueLatticeElement &IV = ValueState[&I];
988  if (IV.isOverdefined())
989  return;
990 
991  // If something is undef, wait for it to resolve.
992  if (V1State.isUnknownOrUndef() || V2State.isUnknownOrUndef())
993  return;
994 
995  if (V1State.isOverdefined() && V2State.isOverdefined())
996  return (void)markOverdefined(&I);
997 
998  // If either of the operands is a constant, try to fold it to a constant.
999  // TODO: Use information from notconstant better.
1000  if ((V1State.isConstant() || V2State.isConstant())) {
1001  Value *V1 = isConstant(V1State) ? getConstant(V1State) : I.getOperand(0);
1002  Value *V2 = isConstant(V2State) ? getConstant(V2State) : I.getOperand(1);
1003  Value *R = simplifyBinOp(I.getOpcode(), V1, V2, SimplifyQuery(DL));
1004  auto *C = dyn_cast_or_null<Constant>(R);
1005  if (C) {
1006  // Conservatively assume that the result may be based on operands that may
1007  // be undef. Note that we use mergeInValue to combine the constant with
1008  // the existing lattice value for I, as different constants might be found
1009  // after one of the operands go to overdefined, e.g. due to one operand
1010  // being a special floating value.
1011  ValueLatticeElement NewV;
1012  NewV.markConstant(C, /*MayIncludeUndef=*/true);
1013  return (void)mergeInValue(&I, NewV);
1014  }
1015  }
1016 
1017  // Only use ranges for binary operators on integers.
1018  if (!I.getType()->isIntegerTy())
1019  return markOverdefined(&I);
1020 
1021  // Try to simplify to a constant range.
1022  ConstantRange A = getConstantRange(V1State, I.getType());
1023  ConstantRange B = getConstantRange(V2State, I.getType());
1024  ConstantRange R = A.binaryOp(cast<BinaryOperator>(&I)->getOpcode(), B);
1025  mergeInValue(&I, ValueLatticeElement::getRange(R));
1026 
1027  // TODO: Currently we do not exploit special values that produce something
1028  // better than overdefined with an overdefined operand for vector or floating
1029  // point types, like and <4 x i32> overdefined, zeroinitializer.
1030 }
1031 
1032 // Handle ICmpInst instruction.
1033 void SCCPInstVisitor::visitCmpInst(CmpInst &I) {
1034  // Do not cache this lookup, getValueState calls later in the function might
1035  // invalidate the reference.
1036  if (isOverdefined(ValueState[&I]))
1037  return (void)markOverdefined(&I);
1038 
1039  Value *Op1 = I.getOperand(0);
1040  Value *Op2 = I.getOperand(1);
1041 
1042  // For parameters, use ParamState which includes constant range info if
1043  // available.
1044  auto V1State = getValueState(Op1);
1045  auto V2State = getValueState(Op2);
1046 
1047  Constant *C = V1State.getCompare(I.getPredicate(), I.getType(), V2State, DL);
1048  if (C) {
1050  CV.markConstant(C);
1051  mergeInValue(&I, CV);
1052  return;
1053  }
1054 
1055  // If operands are still unknown, wait for it to resolve.
1056  if ((V1State.isUnknownOrUndef() || V2State.isUnknownOrUndef()) &&
1057  !isConstant(ValueState[&I]))
1058  return;
1059 
1060  markOverdefined(&I);
1061 }
1062 
1063 // Handle getelementptr instructions. If all operands are constants then we
1064 // can turn this into a getelementptr ConstantExpr.
1065 void SCCPInstVisitor::visitGetElementPtrInst(GetElementPtrInst &I) {
1066  if (isOverdefined(ValueState[&I]))
1067  return (void)markOverdefined(&I);
1068 
1070  Operands.reserve(I.getNumOperands());
1071 
1072  for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) {
1073  ValueLatticeElement State = getValueState(I.getOperand(i));
1074  if (State.isUnknownOrUndef())
1075  return; // Operands are not resolved yet.
1076 
1077  if (isOverdefined(State))
1078  return (void)markOverdefined(&I);
1079 
1080  if (Constant *C = getConstant(State)) {
1081  Operands.push_back(C);
1082  continue;
1083  }
1084 
1085  return (void)markOverdefined(&I);
1086  }
1087 
1088  Constant *Ptr = Operands[0];
1089  auto Indices = makeArrayRef(Operands.begin() + 1, Operands.end());
1090  Constant *C =
1091  ConstantExpr::getGetElementPtr(I.getSourceElementType(), Ptr, Indices);
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  return (void)markConstant(IV, &I, C);
1171  }
1172 
1173  // Fall back to metadata.
1174  mergeInValue(&I, getValueFromMetadata(&I));
1175 }
1176 
1177 void SCCPInstVisitor::visitCallBase(CallBase &CB) {
1178  handleCallResult(CB);
1179  handleCallArguments(CB);
1180 }
1181 
1182 void SCCPInstVisitor::handleCallOverdefined(CallBase &CB) {
1183  Function *F = CB.getCalledFunction();
1184 
1185  // Void return and not tracking callee, just bail.
1186  if (CB.getType()->isVoidTy())
1187  return;
1188 
1189  // Always mark struct return as overdefined.
1190  if (CB.getType()->isStructTy())
1191  return (void)markOverdefined(&CB);
1192 
1193  // Otherwise, if we have a single return value case, and if the function is
1194  // a declaration, maybe we can constant fold it.
1195  if (F && F->isDeclaration() && canConstantFoldCallTo(&CB, F)) {
1197  for (const Use &A : CB.args()) {
1198  if (A.get()->getType()->isStructTy())
1199  return markOverdefined(&CB); // Can't handle struct args.
1200  if (A.get()->getType()->isMetadataTy())
1201  continue; // Carried in CB, not allowed in Operands.
1202  ValueLatticeElement State = getValueState(A);
1203 
1204  if (State.isUnknownOrUndef())
1205  return; // Operands are not resolved yet.
1206  if (isOverdefined(State))
1207  return (void)markOverdefined(&CB);
1208  assert(isConstant(State) && "Unknown state!");
1209  Operands.push_back(getConstant(State));
1210  }
1211 
1212  if (isOverdefined(getValueState(&CB)))
1213  return (void)markOverdefined(&CB);
1214 
1215  // If we can constant fold this, mark the result of the call as a
1216  // constant.
1217  if (Constant *C = ConstantFoldCall(&CB, F, Operands, &GetTLI(*F)))
1218  return (void)markConstant(&CB, C);
1219  }
1220 
1221  // Fall back to metadata.
1222  mergeInValue(&CB, getValueFromMetadata(&CB));
1223 }
1224 
1225 void SCCPInstVisitor::handleCallArguments(CallBase &CB) {
1226  Function *F = CB.getCalledFunction();
1227  // If this is a local function that doesn't have its address taken, mark its
1228  // entry block executable and merge in the actual arguments to the call into
1229  // the formal arguments of the function.
1230  if (!TrackingIncomingArguments.empty() &&
1231  TrackingIncomingArguments.count(F)) {
1232  markBlockExecutable(&F->front());
1233 
1234  // Propagate information from this call site into the callee.
1235  auto CAI = CB.arg_begin();
1236  for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end(); AI != E;
1237  ++AI, ++CAI) {
1238  // If this argument is byval, and if the function is not readonly, there
1239  // will be an implicit copy formed of the input aggregate.
1240  if (AI->hasByValAttr() && !F->onlyReadsMemory()) {
1241  markOverdefined(&*AI);
1242  continue;
1243  }
1244 
1245  if (auto *STy = dyn_cast<StructType>(AI->getType())) {
1246  for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
1247  ValueLatticeElement CallArg = getStructValueState(*CAI, i);
1248  mergeInValue(getStructValueState(&*AI, i), &*AI, CallArg,
1250  }
1251  } else
1252  mergeInValue(&*AI, getValueState(*CAI), getMaxWidenStepsOpts());
1253  }
1254  }
1255 }
1256 
1257 void SCCPInstVisitor::handleCallResult(CallBase &CB) {
1258  Function *F = CB.getCalledFunction();
1259 
1260  if (auto *II = dyn_cast<IntrinsicInst>(&CB)) {
1261  if (II->getIntrinsicID() == Intrinsic::ssa_copy) {
1262  if (ValueState[&CB].isOverdefined())
1263  return;
1264 
1265  Value *CopyOf = CB.getOperand(0);
1266  ValueLatticeElement CopyOfVal = getValueState(CopyOf);
1267  const auto *PI = getPredicateInfoFor(&CB);
1268  assert(PI && "Missing predicate info for ssa.copy");
1269 
1270  const Optional<PredicateConstraint> &Constraint = PI->getConstraint();
1271  if (!Constraint) {
1272  mergeInValue(ValueState[&CB], &CB, CopyOfVal);
1273  return;
1274  }
1275 
1276  CmpInst::Predicate Pred = Constraint->Predicate;
1277  Value *OtherOp = Constraint->OtherOp;
1278 
1279  // Wait until OtherOp is resolved.
1280  if (getValueState(OtherOp).isUnknown()) {
1281  addAdditionalUser(OtherOp, &CB);
1282  return;
1283  }
1284 
1285  ValueLatticeElement CondVal = getValueState(OtherOp);
1286  ValueLatticeElement &IV = ValueState[&CB];
1287  if (CondVal.isConstantRange() || CopyOfVal.isConstantRange()) {
1288  auto ImposedCR =
1289  ConstantRange::getFull(DL.getTypeSizeInBits(CopyOf->getType()));
1290 
1291  // Get the range imposed by the condition.
1292  if (CondVal.isConstantRange())
1294  Pred, CondVal.getConstantRange());
1295 
1296  // Combine range info for the original value with the new range from the
1297  // condition.
1298  auto CopyOfCR = getConstantRange(CopyOfVal, CopyOf->getType());
1299  auto NewCR = ImposedCR.intersectWith(CopyOfCR);
1300  // If the existing information is != x, do not use the information from
1301  // a chained predicate, as the != x information is more likely to be
1302  // helpful in practice.
1303  if (!CopyOfCR.contains(NewCR) && CopyOfCR.getSingleMissingElement())
1304  NewCR = CopyOfCR;
1305 
1306  // The new range is based on a branch condition. That guarantees that
1307  // neither of the compare operands can be undef in the branch targets,
1308  // unless we have conditions that are always true/false (e.g. icmp ule
1309  // i32, %a, i32_max). For the latter overdefined/empty range will be
1310  // inferred, but the branch will get folded accordingly anyways.
1311  addAdditionalUser(OtherOp, &CB);
1312  mergeInValue(
1313  IV, &CB,
1314  ValueLatticeElement::getRange(NewCR, /*MayIncludeUndef*/ false));
1315  return;
1316  } else if (Pred == CmpInst::ICMP_EQ && CondVal.isConstant()) {
1317  // For non-integer values or integer constant expressions, only
1318  // propagate equal constants.
1319  addAdditionalUser(OtherOp, &CB);
1320  mergeInValue(IV, &CB, CondVal);
1321  return;
1322  } else if (Pred == CmpInst::ICMP_NE && CondVal.isConstant()) {
1323  // Propagate inequalities.
1324  addAdditionalUser(OtherOp, &CB);
1325  mergeInValue(IV, &CB,
1327  return;
1328  }
1329 
1330  return (void)mergeInValue(IV, &CB, CopyOfVal);
1331  }
1332 
1333  if (ConstantRange::isIntrinsicSupported(II->getIntrinsicID())) {
1334  // Compute result range for intrinsics supported by ConstantRange.
1335  // Do this even if we don't know a range for all operands, as we may
1336  // still know something about the result range, e.g. of abs(x).
1338  for (Value *Op : II->args()) {
1339  const ValueLatticeElement &State = getValueState(Op);
1340  OpRanges.push_back(getConstantRange(State, Op->getType()));
1341  }
1342 
1344  ConstantRange::intrinsic(II->getIntrinsicID(), OpRanges);
1345  return (void)mergeInValue(II, ValueLatticeElement::getRange(Result));
1346  }
1347  }
1348 
1349  // The common case is that we aren't tracking the callee, either because we
1350  // are not doing interprocedural analysis or the callee is indirect, or is
1351  // external. Handle these cases first.
1352  if (!F || F->isDeclaration())
1353  return handleCallOverdefined(CB);
1354 
1355  // If this is a single/zero retval case, see if we're tracking the function.
1356  if (auto *STy = dyn_cast<StructType>(F->getReturnType())) {
1357  if (!MRVFunctionsTracked.count(F))
1358  return handleCallOverdefined(CB); // Not tracking this callee.
1359 
1360  // If we are tracking this callee, propagate the result of the function
1361  // into this call site.
1362  for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
1363  mergeInValue(getStructValueState(&CB, i), &CB,
1364  TrackedMultipleRetVals[std::make_pair(F, i)],
1366  } else {
1367  auto TFRVI = TrackedRetVals.find(F);
1368  if (TFRVI == TrackedRetVals.end())
1369  return handleCallOverdefined(CB); // Not tracking this callee.
1370 
1371  // If so, propagate the return value of the callee into this call result.
1372  mergeInValue(&CB, TFRVI->second, getMaxWidenStepsOpts());
1373  }
1374 }
1375 
1377  // Process the work lists until they are empty!
1378  while (!BBWorkList.empty() || !InstWorkList.empty() ||
1379  !OverdefinedInstWorkList.empty()) {
1380  // Process the overdefined instruction's work list first, which drives other
1381  // things to overdefined more quickly.
1382  while (!OverdefinedInstWorkList.empty()) {
1383  Value *I = OverdefinedInstWorkList.pop_back_val();
1384 
1385  LLVM_DEBUG(dbgs() << "\nPopped off OI-WL: " << *I << '\n');
1386 
1387  // "I" got into the work list because it either made the transition from
1388  // bottom to constant, or to overdefined.
1389  //
1390  // Anything on this worklist that is overdefined need not be visited
1391  // since all of its users will have already been marked as overdefined
1392  // Update all of the users of this instruction's value.
1393  //
1394  markUsersAsChanged(I);
1395  }
1396 
1397  // Process the instruction work list.
1398  while (!InstWorkList.empty()) {
1399  Value *I = InstWorkList.pop_back_val();
1400 
1401  LLVM_DEBUG(dbgs() << "\nPopped off I-WL: " << *I << '\n');
1402 
1403  // "I" got into the work list because it made the transition from undef to
1404  // constant.
1405  //
1406  // Anything on this worklist that is overdefined need not be visited
1407  // since all of its users will have already been marked as overdefined.
1408  // Update all of the users of this instruction's value.
1409  //
1410  if (I->getType()->isStructTy() || !getValueState(I).isOverdefined())
1411  markUsersAsChanged(I);
1412  }
1413 
1414  // Process the basic block work list.
1415  while (!BBWorkList.empty()) {
1416  BasicBlock *BB = BBWorkList.pop_back_val();
1417 
1418  LLVM_DEBUG(dbgs() << "\nPopped off BBWL: " << *BB << '\n');
1419 
1420  // Notify all instructions in this basic block that they are newly
1421  // executable.
1422  visit(BB);
1423  }
1424  }
1425 }
1426 
1427 /// While solving the dataflow for a function, we don't compute a result for
1428 /// operations with an undef operand, to allow undef to be lowered to a
1429 /// constant later. For example, constant folding of "zext i8 undef to i16"
1430 /// would result in "i16 0", and if undef is later lowered to "i8 1", then the
1431 /// zext result would become "i16 1" and would result into an overdefined
1432 /// lattice value once merged with the previous result. Not computing the
1433 /// result of the zext (treating undef the same as unknown) allows us to handle
1434 /// a later undef->constant lowering more optimally.
1435 ///
1436 /// However, if the operand remains undef when the solver returns, we do need
1437 /// to assign some result to the instruction (otherwise we would treat it as
1438 /// unreachable). For simplicity, we mark any instructions that are still
1439 /// unknown as overdefined.
1441  bool MadeChange = false;
1442  for (BasicBlock &BB : F) {
1443  if (!BBExecutable.count(&BB))
1444  continue;
1445 
1446  for (Instruction &I : BB) {
1447  // Look for instructions which produce undef values.
1448  if (I.getType()->isVoidTy())
1449  continue;
1450 
1451  if (auto *STy = dyn_cast<StructType>(I.getType())) {
1452  // Only a few things that can be structs matter for undef.
1453 
1454  // Tracked calls must never be marked overdefined in resolvedUndefsIn.
1455  if (auto *CB = dyn_cast<CallBase>(&I))
1456  if (Function *F = CB->getCalledFunction())
1457  if (MRVFunctionsTracked.count(F))
1458  continue;
1459 
1460  // extractvalue and insertvalue don't need to be marked; they are
1461  // tracked as precisely as their operands.
1462  if (isa<ExtractValueInst>(I) || isa<InsertValueInst>(I))
1463  continue;
1464  // Send the results of everything else to overdefined. We could be
1465  // more precise than this but it isn't worth bothering.
1466  for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
1467  ValueLatticeElement &LV = getStructValueState(&I, i);
1468  if (LV.isUnknown()) {
1469  markOverdefined(LV, &I);
1470  MadeChange = true;
1471  }
1472  }
1473  continue;
1474  }
1475 
1476  ValueLatticeElement &LV = getValueState(&I);
1477  if (!LV.isUnknown())
1478  continue;
1479 
1480  // There are two reasons a call can have an undef result
1481  // 1. It could be tracked.
1482  // 2. It could be constant-foldable.
1483  // Because of the way we solve return values, tracked calls must
1484  // never be marked overdefined in resolvedUndefsIn.
1485  if (auto *CB = dyn_cast<CallBase>(&I))
1486  if (Function *F = CB->getCalledFunction())
1487  if (TrackedRetVals.count(F))
1488  continue;
1489 
1490  if (isa<LoadInst>(I)) {
1491  // A load here means one of two things: a load of undef from a global,
1492  // a load from an unknown pointer. Either way, having it return undef
1493  // is okay.
1494  continue;
1495  }
1496 
1497  markOverdefined(&I);
1498  MadeChange = true;
1499  }
1500  }
1501 
1502  return MadeChange;
1503 }
1504 
1505 //===----------------------------------------------------------------------===//
1506 //
1507 // SCCPSolver implementations
1508 //
1510  const DataLayout &DL,
1511  std::function<const TargetLibraryInfo &(Function &)> GetTLI,
1512  LLVMContext &Ctx)
1513  : Visitor(new SCCPInstVisitor(DL, std::move(GetTLI), Ctx)) {}
1514 
1515 SCCPSolver::~SCCPSolver() = default;
1516 
1518  return Visitor->addAnalysis(F, std::move(A));
1519 }
1520 
1522  return Visitor->markBlockExecutable(BB);
1523 }
1524 
1526  return Visitor->getPredicateInfoFor(I);
1527 }
1528 
1530  return Visitor->getLoopInfo(F);
1531 }
1532 
1533 DomTreeUpdater SCCPSolver::getDTU(Function &F) { return Visitor->getDTU(F); }
1534 
1536  Visitor->trackValueOfGlobalVariable(GV);
1537 }
1538 
1540  Visitor->addTrackedFunction(F);
1541 }
1542 
1544  Visitor->addToMustPreserveReturnsInFunctions(F);
1545 }
1546 
1548  return Visitor->mustPreserveReturn(F);
1549 }
1550 
1552  Visitor->addArgumentTrackedFunction(F);
1553 }
1554 
1556  return Visitor->isArgumentTrackedFunction(F);
1557 }
1558 
1559 void SCCPSolver::solve() { Visitor->solve(); }
1560 
1562  return Visitor->resolvedUndefsIn(F);
1563 }
1564 
1566  return Visitor->isBlockExecutable(BB);
1567 }
1568 
1570  return Visitor->isEdgeFeasible(From, To);
1571 }
1572 
1573 std::vector<ValueLatticeElement>
1575  return Visitor->getStructLatticeValueFor(V);
1576 }
1577 
1579  return Visitor->removeLatticeValueFor(V);
1580 }
1581 
1583  return Visitor->getLatticeValueFor(V);
1584 }
1585 
1588  return Visitor->getTrackedRetVals();
1589 }
1590 
1593  return Visitor->getTrackedGlobals();
1594 }
1595 
1597  return Visitor->getMRVFunctionsTracked();
1598 }
1599 
1600 void SCCPSolver::markOverdefined(Value *V) { Visitor->markOverdefined(V); }
1601 
1603  return Visitor->isStructLatticeConstant(F, STy);
1604 }
1605 
1607  return Visitor->getConstant(LV);
1608 }
1609 
1611  return Visitor->getArgumentTrackedFunctions();
1612 }
1613 
1616  Visitor->markArgInFuncSpecialization(F, Args);
1617 }
1618 
1620  Visitor->markFunctionUnreachable(F);
1621 }
1622 
1623 void SCCPSolver::visit(Instruction *I) { Visitor->visit(I); }
1624 
1625 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:417
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::Instruction::getNumSuccessors
unsigned getNumSuccessors() const LLVM_READONLY
Return the number of successors that this instruction has.
Definition: Instruction.cpp:814
llvm::ValueLatticeElement::isConstant
bool isConstant() const
Definition: ValueLattice.h:243
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::CmpInst::ICMP_EQ
@ ICMP_EQ
equal
Definition: InstrTypes.h:741
llvm::ConstantFoldUnaryOpOperand
Constant * ConstantFoldUnaryOpOperand(unsigned Opcode, Constant *Op, const DataLayout &DL)
Attempt to constant fold a unary operation with the specified operand.
Definition: ConstantFolding.cpp:1332
llvm::ReturnInst
Return a value (possibly void), from a function.
Definition: Instructions.h:3050
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:419
llvm::SCCPInstVisitor::getDTU
DomTreeUpdater getDTU(Function &F)
Definition: SCCPSolver.cpp:349
llvm::CmpInst::Predicate
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:720
llvm::SimplifyQuery
Definition: InstructionSimplify.h:93
T
llvm::AnalysisResultsForFn
Helper struct for bundling up the analysis results per function for IPSCCP.
Definition: SCCPSolver.h:41
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:1574
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1199
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:718
llvm::SCCPInstVisitor::markArgInFuncSpecialization
void markArgInFuncSpecialization(Function *F, const SmallVectorImpl< ArgInfo > &Args)
Definition: SCCPSolver.cpp:542
llvm::GlobalVariable
Definition: GlobalVariable.h:39
llvm::CmpInst::ICMP_NE
@ ICMP_NE
not equal
Definition: InstrTypes.h:742
llvm::SCCPInstVisitor::getConstantRange
ConstantRange getConstantRange(const ValueLatticeElement &LV, Type *Ty) const
Definition: SCCPSolver.cpp:534
llvm::SCCPSolver::getLoopInfo
const LoopInfo & getLoopInfo(Function &F)
Definition: SCCPSolver.cpp:1529
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:1606
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:510
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:433
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::max
Expected< ExpressionValue > max(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:337
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:1521
llvm::CallBase::arg_begin
User::op_iterator arg_begin()
Return the iterator pointing to the beginning of the argument list.
Definition: InstrTypes.h:1317
llvm::SCCPSolver::visit
void visit(Instruction *I)
Definition: SCCPSolver.cpp:1623
llvm::getConstantRangeFromMetadata
ConstantRange getConstantRangeFromMetadata(const MDNode &RangeMD)
Parse out a conservative ConstantRange from !range metadata.
Definition: ConstantRange.cpp:1800
llvm::SCCPInstVisitor::SCCPInstVisitor
SCCPInstVisitor(const DataLayout &DL, std::function< const TargetLibraryInfo &(Function &)> GetTLI, LLVMContext &Ctx)
Definition: SCCPSolver.cpp:355
llvm::ValueLatticeElement::getCompare
Constant * getCompare(CmpInst::Predicate Pred, Type *Ty, const ValueLatticeElement &Other, const DataLayout &DL) const
true, false or undef constants, or nullptr if the comparison cannot be evaluated.
Definition: ValueLattice.cpp:14
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:179
llvm::SCCPSolver::addArgumentTrackedFunction
void addArgumentTrackedFunction(Function *F)
Definition: SCCPSolver.cpp:1551
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:265
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:1619
llvm::SCCPInstVisitor::resolvedUndefsIn
bool resolvedUndefsIn(Function &F)
While solving the dataflow for a function, we don't compute a result for operations with an undef ope...
Definition: SCCPSolver.cpp:1440
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:391
getValueFromMetadata
static ValueLatticeElement getValueFromMetadata(const Instruction *I)
Definition: SCCPSolver.cpp:1115
llvm::Type::isSingleValueType
bool isSingleValueType() const
Return true if the type is a valid type for a register in codegen.
Definition: Type.h:268
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:441
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:2793
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:1600
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:1411
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:1397
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:1555
llvm::ExtractValueInst::getNumIndices
unsigned getNumIndices() const
Definition: Instructions.h:2513
llvm::ConstantRange::isSingleElement
bool isSingleElement() const
Return true if this set contains exactly one member.
Definition: ConstantRange.h:261
SI
@ SI
Definition: SIInstrInfo.cpp:7966
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:3245
llvm::ms_demangle::QualifierMangleMode::Result
@ Result
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:5706
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:1499
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::SCCPSolver::addAnalysis
void addAnalysis(Function &F, AnalysisResultsForFn A)
Definition: SCCPSolver.cpp:1517
llvm::Instruction
Definition: Instruction.h:42
llvm::Type::getScalarSizeInBits
unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type.
Definition: Type.cpp:189
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:364
llvm::SmallVectorImpl::resize
void resize(size_type N)
Definition: SmallVector.h:642
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:879
llvm::SCCPSolver::isStructLatticeConstant
bool isStructLatticeConstant(Function *F, StructType *STy)
Definition: SCCPSolver.cpp:1602
llvm::SCCPInstVisitor::getMRVFunctionsTracked
const SmallPtrSet< Function *, 16 > getMRVFunctionsTracked()
Definition: SCCPSolver.cpp:437
llvm::PHINode::getNumIncomingValues
unsigned getNumIncomingValues() const
Return the number of incoming edges.
Definition: Instructions.h:2789
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:3809
llvm::CmpInst
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:710
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:1587
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:1625
llvm::SCCPInstVisitor::solve
void solve()
Definition: SCCPSolver.cpp:1376
llvm::SCCPSolver::getLatticeValueFor
const ValueLatticeElement & getLatticeValueFor(Value *V) const
Definition: SCCPSolver.cpp:1582
llvm::StoreInst
An instruction for storing to memory.
Definition: Instructions.h:298
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::Instruction::getSuccessor
BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY
Return the specified successor. This instruction must be a terminator.
Definition: Instruction.cpp:826
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:443
llvm::SCCPInstVisitor
Helper class for SCCPSolver.
Definition: SCCPSolver.cpp:67
llvm::SCCPInstVisitor::getLoopInfo
const LoopInfo & getLoopInfo(Function &F)
Definition: SCCPSolver.cpp:342
Addr
uint64_t Addr
Definition: ELFObjHandler.cpp:79
llvm::ConstantPointerNull::get
static ConstantPointerNull * get(PointerType *T)
Static factory methods - Return objects of the specified value.
Definition: Constants.cpp:1699
llvm::CallBrInst
CallBr instruction, tracking function calls that may not return control but instead transfer it to a ...
Definition: Instructions.h:4018
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:67
isConstant
static bool isConstant(const MachineInstr &MI)
Definition: AMDGPUInstructionSelector.cpp:2605
llvm::SCCPSolver::getPredicateInfoFor
const PredicateBase * getPredicateInfoFor(Instruction *I)
Definition: SCCPSolver.cpp:1525
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:53
llvm::DenseMap
Definition: DenseMap.h:714
llvm::SCCPInstVisitor::addArgumentTrackedFunction
void addArgumentTrackedFunction(Function *F)
Definition: SCCPSolver.cpp:387
MaxNumRangeExtensions
static const unsigned MaxNumRangeExtensions
Definition: SCCPSolver.cpp:34
llvm::ExtractValueInst::idx_begin
idx_iterator idx_begin() const
Definition: Instructions.h:2493
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::SCCPInstVisitor::getArgumentTrackedFunctions
SmallPtrSetImpl< Function * > & getArgumentTrackedFunctions()
Definition: SCCPSolver.cpp:454
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:429
llvm::SCCPSolver::getTrackedGlobals
const DenseMap< GlobalVariable *, ValueLatticeElement > & getTrackedGlobals()
getTrackedGlobals - Get and return the set of inferred initializers for global variables.
Definition: SCCPSolver.cpp:1592
llvm::ValueLatticeElement::getNumRangeExtensions
unsigned getNumRangeExtensions() const
Definition: ValueLattice.h:458
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:1861
Ptr
@ Ptr
Definition: TargetLibraryInfo.cpp:60
llvm::SelectInst
This class represents the LLVM 'select' instruction.
Definition: Instructions.h:1735
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:944
getOpcode
static std::optional< unsigned > getOpcode(ArrayRef< VPValue * > Values)
Returns the opcode of Values or ~0 if they do not all agree.
Definition: VPlanSLP.cpp:191
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:383
llvm::BlockAddress
The address of a basic block.
Definition: Constants.h:849
llvm::SCCPSolver::getDTU
DomTreeUpdater getDTU(Function &F)
Definition: SCCPSolver.cpp:1533
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:1614
llvm::LoopInfo
Definition: LoopInfo.h:1108
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:1509
llvm::StructType
Class to represent struct types.
Definition: DerivedTypes.h:213
llvm::logicalview::LVAttributeKind::Range
@ Range
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:1578
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:1547
llvm::CastInst
This is the base class for all instructions that perform data casts.
Definition: InstrTypes.h:430
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:308
llvm::SCCPInstVisitor::trackValueOfGlobalVariable
void trackValueOfGlobalVariable(GlobalVariable *GV)
Definition: SCCPSolver.cpp:360
llvm::LoadInst
An instruction for reading from memory.
Definition: Instructions.h:174
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:256
llvm::SCCPInstVisitor::getTrackedGlobals
const DenseMap< GlobalVariable *, ValueLatticeElement > & getTrackedGlobals()
Definition: SCCPSolver.cpp:433
llvm::SCCPInstVisitor::getConstant
Constant * getConstant(const ValueLatticeElement &LV) const
Definition: SCCPSolver.cpp:521
llvm::SCCPSolver::isBlockExecutable
bool isBlockExecutable(BasicBlock *BB) const
Definition: SCCPSolver.cpp:1565
llvm::StructType::getNumElements
unsigned getNumElements() const
Random access to the elements.
Definition: DerivedTypes.h:327
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:729
llvm::SCCPSolver::isEdgeFeasible
bool isEdgeFeasible(BasicBlock *From, BasicBlock *To) const
Definition: SCCPSolver.cpp:1569
llvm::SCCPInstVisitor::markFunctionUnreachable
void markFunctionUnreachable(Function *F)
Definition: SCCPSolver.cpp:461
llvm::NVPTX::PTXLdStInstCode::V2
@ V2
Definition: NVPTX.h:123
llvm::ResumeInst
Resume the propagation of an exception.
Definition: Instructions.h:4251
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:708
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:348
llvm::Type::isIntOrIntVectorTy
bool isIntOrIntVectorTy() const
Return true if this is an integer type or a vector of integer types.
Definition: Type.h:216
llvm::SCCPInstVisitor::getPredicateInfoFor
const PredicateBase * getPredicateInfoFor(Instruction *I)
Definition: SCCPSolver.cpp:335
llvm::ExtractValueInst
This instruction extracts a struct member or array element value from an aggregate value.
Definition: Instructions.h:2444
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:226
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:1561
llvm::ExtractValueInst::getAggregateOperand
Value * getAggregateOperand()
Definition: Instructions.h:2499
llvm::SCCPInstVisitor::addTrackedFunction
void addTrackedFunction(Function *F)
Definition: SCCPSolver.cpp:368
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:1543
llvm::Type::isStructTy
bool isStructTy() const
True if this is an instance of StructType.
Definition: Type.h:231
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::PHINode::getIncomingBlock
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Definition: Instructions.h:2813
llvm::PHINode
Definition: Instructions.h:2697
IV
static const uint32_t IV[8]
Definition: blake3_impl.h:85
llvm::SmallVectorImpl< bool >
llvm::ValueLatticeElement::isUnknown
bool isUnknown() const
Definition: ValueLattice.h:241
llvm::SCCPSolver::trackValueOfGlobalVariable
void trackValueOfGlobalVariable(GlobalVariable *GV)
trackValueOfGlobalVariable - Clients can use this method to inform the SCCPSolver that it should trac...
Definition: SCCPSolver.cpp:1535
llvm::SCCPInstVisitor::addToMustPreserveReturnsInFunctions
void addToMustPreserveReturnsInFunctions(Function *F)
Definition: SCCPSolver.cpp:379
llvm::CallBase
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1175
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:292
llvm::SCCPInstVisitor::getStructLatticeValueFor
std::vector< ValueLatticeElement > getStructLatticeValueFor(Value *V) const
Definition: SCCPSolver.cpp:405
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:4768
llvm::SCCPSolver::solve
void solve()
Solve - Solve for constants and executable blocks.
Definition: SCCPSolver.cpp:1559
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:327
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:2109
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:1539
llvm::InsertValueInst
This instruction inserts a struct field of array element value into an aggregate value.
Definition: Instructions.h:2555
llvm::ConstantExpr::getGetElementPtr
static Constant * getGetElementPtr(Type *Ty, Constant *C, ArrayRef< Constant * > IdxList, bool InBounds=false, Optional< unsigned > InRangeIndex=std::nullopt, Type *OnlyIfReducedTy=nullptr)
Getelementptr form.
Definition: Constants.h:1219
llvm::CatchSwitchInst
Definition: Instructions.h:4308
llvm::SCCPInstVisitor::visitCallInst
void visitCallInst(CallInst &I)
Definition: SCCPSolver.cpp:331
llvm::SCCPInstVisitor::markBlockExecutable
bool markBlockExecutable(BasicBlock *BB)
Definition: SCCPSolver.cpp:469
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:1596
llvm::CallBase::args
iterator_range< User::op_iterator > args()
Iteration adapter for range-for loops.
Definition: InstrTypes.h:1333
llvm::SCCPSolver::getArgumentTrackedFunctions
SmallPtrSetImpl< Function * > & getArgumentTrackedFunctions()
Return a reference to the set of argument tracked functions.
Definition: SCCPSolver.cpp:1610
llvm::ValueLatticeElement::setNumRangeExtensions
void setNumRangeExtensions(unsigned N)
Definition: ValueLattice.h:459
llvm::SCCPInstVisitor::isBlockExecutable
bool isBlockExecutable(BasicBlock *BB) const
Definition: SCCPSolver.cpp:399
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