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