LLVM  8.0.0svn
GuardWidening.cpp
Go to the documentation of this file.
1 //===- GuardWidening.cpp - ---- Guard widening ----------------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file implements the guard widening pass. The semantics of the
11 // @llvm.experimental.guard intrinsic lets LLVM transform it so that it fails
12 // more often that it did before the transform. This optimization is called
13 // "widening" and can be used hoist and common runtime checks in situations like
14 // these:
15 //
16 // %cmp0 = 7 u< Length
17 // call @llvm.experimental.guard(i1 %cmp0) [ "deopt"(...) ]
18 // call @unknown_side_effects()
19 // %cmp1 = 9 u< Length
20 // call @llvm.experimental.guard(i1 %cmp1) [ "deopt"(...) ]
21 // ...
22 //
23 // =>
24 //
25 // %cmp0 = 9 u< Length
26 // call @llvm.experimental.guard(i1 %cmp0) [ "deopt"(...) ]
27 // call @unknown_side_effects()
28 // ...
29 //
30 // If %cmp0 is false, @llvm.experimental.guard will "deoptimize" back to a
31 // generic implementation of the same function, which will have the correct
32 // semantics from that point onward. It is always _legal_ to deoptimize (so
33 // replacing %cmp0 with false is "correct"), though it may not always be
34 // profitable to do so.
35 //
36 // NB! This pass is a work in progress. It hasn't been tuned to be "production
37 // ready" yet. It is known to have quadriatic running time and will not scale
38 // to large numbers of guards
39 //
40 //===----------------------------------------------------------------------===//
41 
43 #include <functional>
44 #include "llvm/ADT/DenseMap.h"
46 #include "llvm/ADT/Statistic.h"
49 #include "llvm/Analysis/LoopInfo.h"
50 #include "llvm/Analysis/LoopPass.h"
53 #include "llvm/IR/ConstantRange.h"
54 #include "llvm/IR/Dominators.h"
55 #include "llvm/IR/IntrinsicInst.h"
56 #include "llvm/IR/PatternMatch.h"
57 #include "llvm/Pass.h"
58 #include "llvm/Support/Debug.h"
59 #include "llvm/Support/KnownBits.h"
60 #include "llvm/Transforms/Scalar.h"
62 
63 using namespace llvm;
64 
65 #define DEBUG_TYPE "guard-widening"
66 
67 STATISTIC(GuardsEliminated, "Number of eliminated guards");
68 STATISTIC(CondBranchEliminated, "Number of eliminated conditional branches");
69 
71  "guard-widening-widen-frequent-branches", cl::Hidden,
72  cl::desc("Widen conditions of explicit branches into dominating guards in "
73  "case if their taken frequency exceeds threshold set by "
74  "guard-widening-frequent-branch-threshold option"),
75  cl::init(false));
76 
78  "guard-widening-frequent-branch-threshold", cl::Hidden,
79  cl::desc("When WidenFrequentBranches is set to true, this option is used "
80  "to determine which branches are frequently taken. The criteria "
81  "that a branch is taken more often than "
82  "((FrequentBranchThreshold - 1) / FrequentBranchThreshold), then "
83  "it is considered frequently taken"),
84  cl::init(1000));
85 
86 
87 namespace {
88 
89 // Get the condition of \p I. It can either be a guard or a conditional branch.
90 static Value *getCondition(Instruction *I) {
91  if (IntrinsicInst *GI = dyn_cast<IntrinsicInst>(I)) {
92  assert(GI->getIntrinsicID() == Intrinsic::experimental_guard &&
93  "Bad guard intrinsic?");
94  return GI->getArgOperand(0);
95  }
96  return cast<BranchInst>(I)->getCondition();
97 }
98 
99 // Set the condition for \p I to \p NewCond. \p I can either be a guard or a
100 // conditional branch.
101 static void setCondition(Instruction *I, Value *NewCond) {
102  if (IntrinsicInst *GI = dyn_cast<IntrinsicInst>(I)) {
103  assert(GI->getIntrinsicID() == Intrinsic::experimental_guard &&
104  "Bad guard intrinsic?");
105  GI->setArgOperand(0, NewCond);
106  return;
107  }
108  cast<BranchInst>(I)->setCondition(NewCond);
109 }
110 
111 // Eliminates the guard instruction properly.
112 static void eliminateGuard(Instruction *GuardInst) {
113  GuardInst->eraseFromParent();
114  ++GuardsEliminated;
115 }
116 
117 class GuardWideningImpl {
118  DominatorTree &DT;
119  PostDominatorTree *PDT;
120  LoopInfo &LI;
122 
123  /// Together, these describe the region of interest. This might be all of
124  /// the blocks within a function, or only a given loop's blocks and preheader.
125  DomTreeNode *Root;
126  std::function<bool(BasicBlock*)> BlockFilter;
127 
128  /// The set of guards and conditional branches whose conditions have been
129  /// widened into dominating guards.
130  SmallVector<Instruction *, 16> EliminatedGuardsAndBranches;
131 
132  /// The set of guards which have been widened to include conditions to other
133  /// guards.
134  DenseSet<Instruction *> WidenedGuards;
135 
136  /// Try to eliminate guard \p Guard by widening it into an earlier dominating
137  /// guard. \p DFSI is the DFS iterator on the dominator tree that is
138  /// currently visiting the block containing \p Guard, and \p GuardsPerBlock
139  /// maps BasicBlocks to the set of guards seen in that block.
140  bool eliminateGuardViaWidening(
141  Instruction *Guard, const df_iterator<DomTreeNode *> &DFSI,
143  GuardsPerBlock, bool InvertCondition = false);
144 
145  /// Used to keep track of which widening potential is more effective.
146  enum WideningScore {
147  /// Don't widen.
148  WS_IllegalOrNegative,
149 
150  /// Widening is performance neutral as far as the cycles spent in check
151  /// conditions goes (but can still help, e.g., code layout, having less
152  /// deopt state).
153  WS_Neutral,
154 
155  /// Widening is profitable.
156  WS_Positive,
157 
158  /// Widening is very profitable. Not significantly different from \c
159  /// WS_Positive, except by the order.
160  WS_VeryPositive
161  };
162 
163  static StringRef scoreTypeToString(WideningScore WS);
164 
165  /// Compute the score for widening the condition in \p DominatedGuard
166  /// (contained in \p DominatedGuardLoop) into \p DominatingGuard (contained in
167  /// \p DominatingGuardLoop). If \p InvertCond is set, then we widen the
168  /// inverted condition of the dominating guard.
169  WideningScore computeWideningScore(Instruction *DominatedGuard,
170  Loop *DominatedGuardLoop,
171  Instruction *DominatingGuard,
172  Loop *DominatingGuardLoop,
173  bool InvertCond);
174 
175  /// Helper to check if \p V can be hoisted to \p InsertPos.
176  bool isAvailableAt(Value *V, Instruction *InsertPos) {
178  return isAvailableAt(V, InsertPos, Visited);
179  }
180 
181  bool isAvailableAt(Value *V, Instruction *InsertPos,
183 
184  /// Helper to hoist \p V to \p InsertPos. Guaranteed to succeed if \c
185  /// isAvailableAt returned true.
186  void makeAvailableAt(Value *V, Instruction *InsertPos);
187 
188  /// Common helper used by \c widenGuard and \c isWideningCondProfitable. Try
189  /// to generate an expression computing the logical AND of \p Cond0 and (\p
190  /// Cond1 XOR \p InvertCondition).
191  /// Return true if the expression computing the AND is only as
192  /// expensive as computing one of the two. If \p InsertPt is true then
193  /// actually generate the resulting expression, make it available at \p
194  /// InsertPt and return it in \p Result (else no change to the IR is made).
195  bool widenCondCommon(Value *Cond0, Value *Cond1, Instruction *InsertPt,
196  Value *&Result, bool InvertCondition);
197 
198  /// Represents a range check of the form \c Base + \c Offset u< \c Length,
199  /// with the constraint that \c Length is not negative. \c CheckInst is the
200  /// pre-existing instruction in the IR that computes the result of this range
201  /// check.
202  class RangeCheck {
203  Value *Base;
205  Value *Length;
206  ICmpInst *CheckInst;
207 
208  public:
209  explicit RangeCheck(Value *Base, ConstantInt *Offset, Value *Length,
210  ICmpInst *CheckInst)
211  : Base(Base), Offset(Offset), Length(Length), CheckInst(CheckInst) {}
212 
213  void setBase(Value *NewBase) { Base = NewBase; }
214  void setOffset(ConstantInt *NewOffset) { Offset = NewOffset; }
215 
216  Value *getBase() const { return Base; }
217  ConstantInt *getOffset() const { return Offset; }
218  const APInt &getOffsetValue() const { return getOffset()->getValue(); }
219  Value *getLength() const { return Length; };
220  ICmpInst *getCheckInst() const { return CheckInst; }
221 
222  void print(raw_ostream &OS, bool PrintTypes = false) {
223  OS << "Base: ";
224  Base->printAsOperand(OS, PrintTypes);
225  OS << " Offset: ";
226  Offset->printAsOperand(OS, PrintTypes);
227  OS << " Length: ";
228  Length->printAsOperand(OS, PrintTypes);
229  }
230 
231  LLVM_DUMP_METHOD void dump() {
232  print(dbgs());
233  dbgs() << "\n";
234  }
235  };
236 
237  /// Parse \p CheckCond into a conjunction (logical-and) of range checks; and
238  /// append them to \p Checks. Returns true on success, may clobber \c Checks
239  /// on failure.
240  bool parseRangeChecks(Value *CheckCond, SmallVectorImpl<RangeCheck> &Checks) {
241  SmallPtrSet<Value *, 8> Visited;
242  return parseRangeChecks(CheckCond, Checks, Visited);
243  }
244 
245  bool parseRangeChecks(Value *CheckCond, SmallVectorImpl<RangeCheck> &Checks,
246  SmallPtrSetImpl<Value *> &Visited);
247 
248  /// Combine the checks in \p Checks into a smaller set of checks and append
249  /// them into \p CombinedChecks. Return true on success (i.e. all of checks
250  /// in \p Checks were combined into \p CombinedChecks). Clobbers \p Checks
251  /// and \p CombinedChecks on success and on failure.
252  bool combineRangeChecks(SmallVectorImpl<RangeCheck> &Checks,
253  SmallVectorImpl<RangeCheck> &CombinedChecks);
254 
255  /// Can we compute the logical AND of \p Cond0 and \p Cond1 for the price of
256  /// computing only one of the two expressions?
257  bool isWideningCondProfitable(Value *Cond0, Value *Cond1, bool InvertCond) {
258  Value *ResultUnused;
259  return widenCondCommon(Cond0, Cond1, /*InsertPt=*/nullptr, ResultUnused,
260  InvertCond);
261  }
262 
263  /// If \p InvertCondition is false, Widen \p ToWiden to fail if
264  /// \p NewCondition is false, otherwise make it fail if \p NewCondition is
265  /// true (in addition to whatever it is already checking).
266  void widenGuard(Instruction *ToWiden, Value *NewCondition,
267  bool InvertCondition) {
268  Value *Result;
269  widenCondCommon(ToWiden->getOperand(0), NewCondition, ToWiden, Result,
270  InvertCondition);
271  setCondition(ToWiden, Result);
272  }
273 
274 public:
275 
276  explicit GuardWideningImpl(DominatorTree &DT, PostDominatorTree *PDT,
278  DomTreeNode *Root,
279  std::function<bool(BasicBlock*)> BlockFilter)
280  : DT(DT), PDT(PDT), LI(LI), BPI(BPI), Root(Root), BlockFilter(BlockFilter)
281  {}
282 
283  /// The entry point for this pass.
284  bool run();
285 };
286 }
287 
288 bool GuardWideningImpl::run() {
290  bool Changed = false;
291  Optional<BranchProbability> LikelyTaken = None;
292  if (WidenFrequentBranches && BPI) {
294  assert(Threshold > 0 && "Zero threshold makes no sense!");
295  LikelyTaken = BranchProbability(Threshold - 1, Threshold);
296  }
297 
298  for (auto DFI = df_begin(Root), DFE = df_end(Root);
299  DFI != DFE; ++DFI) {
300  auto *BB = (*DFI)->getBlock();
301  if (!BlockFilter(BB))
302  continue;
303 
304  auto &CurrentList = GuardsInBlock[BB];
305 
306  for (auto &I : *BB)
307  if (isGuard(&I))
308  CurrentList.push_back(cast<Instruction>(&I));
309 
310  for (auto *II : CurrentList)
311  Changed |= eliminateGuardViaWidening(II, DFI, GuardsInBlock);
312  if (WidenFrequentBranches && BPI)
313  if (auto *BI = dyn_cast<BranchInst>(BB->getTerminator()))
314  if (BI->isConditional()) {
315  // If one of branches of a conditional is likely taken, try to
316  // eliminate it.
317  if (BPI->getEdgeProbability(BB, 0U) >= *LikelyTaken)
318  Changed |= eliminateGuardViaWidening(BI, DFI, GuardsInBlock);
319  else if (BPI->getEdgeProbability(BB, 1U) >= *LikelyTaken)
320  Changed |= eliminateGuardViaWidening(BI, DFI, GuardsInBlock,
321  /*InvertCondition*/true);
322  }
323  }
324 
325  assert(EliminatedGuardsAndBranches.empty() || Changed);
326  for (auto *I : EliminatedGuardsAndBranches)
327  if (!WidenedGuards.count(I)) {
328  assert(isa<ConstantInt>(getCondition(I)) && "Should be!");
329  if (isGuard(I))
330  eliminateGuard(I);
331  else {
332  assert(isa<BranchInst>(I) &&
333  "Eliminated something other than guard or branch?");
334  ++CondBranchEliminated;
335  }
336  }
337 
338  return Changed;
339 }
340 
341 bool GuardWideningImpl::eliminateGuardViaWidening(
342  Instruction *GuardInst, const df_iterator<DomTreeNode *> &DFSI,
344  GuardsInBlock, bool InvertCondition) {
345  // Ignore trivial true or false conditions. These instructions will be
346  // trivially eliminated by any cleanup pass. Do not erase them because other
347  // guards can possibly be widened into them.
348  if (isa<ConstantInt>(getCondition(GuardInst)))
349  return false;
350 
351  Instruction *BestSoFar = nullptr;
352  auto BestScoreSoFar = WS_IllegalOrNegative;
353  auto *GuardInstLoop = LI.getLoopFor(GuardInst->getParent());
354 
355  // In the set of dominating guards, find the one we can merge GuardInst with
356  // for the most profit.
357  for (unsigned i = 0, e = DFSI.getPathLength(); i != e; ++i) {
358  auto *CurBB = DFSI.getPath(i)->getBlock();
359  if (!BlockFilter(CurBB))
360  break;
361  auto *CurLoop = LI.getLoopFor(CurBB);
362  assert(GuardsInBlock.count(CurBB) && "Must have been populated by now!");
363  const auto &GuardsInCurBB = GuardsInBlock.find(CurBB)->second;
364 
365  auto I = GuardsInCurBB.begin();
366  auto E = GuardsInCurBB.end();
367 
368 #ifndef NDEBUG
369  {
370  unsigned Index = 0;
371  for (auto &I : *CurBB) {
372  if (Index == GuardsInCurBB.size())
373  break;
374  if (GuardsInCurBB[Index] == &I)
375  Index++;
376  }
377  assert(Index == GuardsInCurBB.size() &&
378  "Guards expected to be in order!");
379  }
380 #endif
381 
382  assert((i == (e - 1)) == (GuardInst->getParent() == CurBB) && "Bad DFS?");
383 
384  if (i == (e - 1) && CurBB->getTerminator() != GuardInst) {
385  // Corner case: make sure we're only looking at guards strictly dominating
386  // GuardInst when visiting GuardInst->getParent().
387  auto NewEnd = std::find(I, E, GuardInst);
388  assert(NewEnd != E && "GuardInst not in its own block?");
389  E = NewEnd;
390  }
391 
392  for (auto *Candidate : make_range(I, E)) {
393  auto Score =
394  computeWideningScore(GuardInst, GuardInstLoop, Candidate, CurLoop,
395  InvertCondition);
396  LLVM_DEBUG(dbgs() << "Score between " << *getCondition(GuardInst)
397  << " and " << *getCondition(Candidate) << " is "
398  << scoreTypeToString(Score) << "\n");
399  if (Score > BestScoreSoFar) {
400  BestScoreSoFar = Score;
401  BestSoFar = Candidate;
402  }
403  }
404  }
405 
406  if (BestScoreSoFar == WS_IllegalOrNegative) {
407  LLVM_DEBUG(dbgs() << "Did not eliminate guard " << *GuardInst << "\n");
408  return false;
409  }
410 
411  assert(BestSoFar != GuardInst && "Should have never visited same guard!");
412  assert(DT.dominates(BestSoFar, GuardInst) && "Should be!");
413 
414  LLVM_DEBUG(dbgs() << "Widening " << *GuardInst << " into " << *BestSoFar
415  << " with score " << scoreTypeToString(BestScoreSoFar)
416  << "\n");
417  widenGuard(BestSoFar, getCondition(GuardInst), InvertCondition);
418  auto NewGuardCondition = InvertCondition
419  ? ConstantInt::getFalse(GuardInst->getContext())
420  : ConstantInt::getTrue(GuardInst->getContext());
421  setCondition(GuardInst, NewGuardCondition);
422  EliminatedGuardsAndBranches.push_back(GuardInst);
423  WidenedGuards.insert(BestSoFar);
424  return true;
425 }
426 
427 GuardWideningImpl::WideningScore GuardWideningImpl::computeWideningScore(
428  Instruction *DominatedGuard, Loop *DominatedGuardLoop,
429  Instruction *DominatingGuard, Loop *DominatingGuardLoop, bool InvertCond) {
430  bool HoistingOutOfLoop = false;
431 
432  if (DominatingGuardLoop != DominatedGuardLoop) {
433  // Be conservative and don't widen into a sibling loop. TODO: If the
434  // sibling is colder, we should consider allowing this.
435  if (DominatingGuardLoop &&
436  !DominatingGuardLoop->contains(DominatedGuardLoop))
437  return WS_IllegalOrNegative;
438 
439  HoistingOutOfLoop = true;
440  }
441 
442  if (!isAvailableAt(getCondition(DominatedGuard), DominatingGuard))
443  return WS_IllegalOrNegative;
444 
445  // If the guard was conditional executed, it may never be reached
446  // dynamically. There are two potential downsides to hoisting it out of the
447  // conditionally executed region: 1) we may spuriously deopt without need and
448  // 2) we have the extra cost of computing the guard condition in the common
449  // case. At the moment, we really only consider the second in our heuristic
450  // here. TODO: evaluate cost model for spurious deopt
451  // NOTE: As written, this also lets us hoist right over another guard which
452  // is essentially just another spelling for control flow.
453  if (isWideningCondProfitable(getCondition(DominatedGuard),
454  getCondition(DominatingGuard), InvertCond))
455  return HoistingOutOfLoop ? WS_VeryPositive : WS_Positive;
456 
457  if (HoistingOutOfLoop)
458  return WS_Positive;
459 
460  // Returns true if we might be hoisting above explicit control flow. Note
461  // that this completely ignores implicit control flow (guards, calls which
462  // throw, etc...). That choice appears arbitrary.
463  auto MaybeHoistingOutOfIf = [&]() {
464  auto *DominatingBlock = DominatingGuard->getParent();
465  auto *DominatedBlock = DominatedGuard->getParent();
466 
467  // Same Block?
468  if (DominatedBlock == DominatingBlock)
469  return false;
470  // Obvious successor (common loop header/preheader case)
471  if (DominatedBlock == DominatingBlock->getUniqueSuccessor())
472  return false;
473  // TODO: diamond, triangle cases
474  if (!PDT) return true;
475  return !PDT->dominates(DominatedGuard->getParent(),
476  DominatingGuard->getParent());
477  };
478 
479  return MaybeHoistingOutOfIf() ? WS_IllegalOrNegative : WS_Neutral;
480 }
481 
482 bool GuardWideningImpl::isAvailableAt(Value *V, Instruction *Loc,
484  auto *Inst = dyn_cast<Instruction>(V);
485  if (!Inst || DT.dominates(Inst, Loc) || Visited.count(Inst))
486  return true;
487 
488  if (!isSafeToSpeculativelyExecute(Inst, Loc, &DT) ||
489  Inst->mayReadFromMemory())
490  return false;
491 
492  Visited.insert(Inst);
493 
494  // We only want to go _up_ the dominance chain when recursing.
495  assert(!isa<PHINode>(Loc) &&
496  "PHIs should return false for isSafeToSpeculativelyExecute");
497  assert(DT.isReachableFromEntry(Inst->getParent()) &&
498  "We did a DFS from the block entry!");
499  return all_of(Inst->operands(),
500  [&](Value *Op) { return isAvailableAt(Op, Loc, Visited); });
501 }
502 
503 void GuardWideningImpl::makeAvailableAt(Value *V, Instruction *Loc) {
504  auto *Inst = dyn_cast<Instruction>(V);
505  if (!Inst || DT.dominates(Inst, Loc))
506  return;
507 
508  assert(isSafeToSpeculativelyExecute(Inst, Loc, &DT) &&
509  !Inst->mayReadFromMemory() && "Should've checked with isAvailableAt!");
510 
511  for (Value *Op : Inst->operands())
512  makeAvailableAt(Op, Loc);
513 
514  Inst->moveBefore(Loc);
515 }
516 
517 bool GuardWideningImpl::widenCondCommon(Value *Cond0, Value *Cond1,
518  Instruction *InsertPt, Value *&Result,
519  bool InvertCondition) {
520  using namespace llvm::PatternMatch;
521 
522  {
523  // L >u C0 && L >u C1 -> L >u max(C0, C1)
524  ConstantInt *RHS0, *RHS1;
525  Value *LHS;
526  ICmpInst::Predicate Pred0, Pred1;
527  if (match(Cond0, m_ICmp(Pred0, m_Value(LHS), m_ConstantInt(RHS0))) &&
528  match(Cond1, m_ICmp(Pred1, m_Specific(LHS), m_ConstantInt(RHS1)))) {
529  if (InvertCondition)
530  Pred1 = ICmpInst::getInversePredicate(Pred1);
531 
532  ConstantRange CR0 =
534  ConstantRange CR1 =
536 
537  // SubsetIntersect is a subset of the actual mathematical intersection of
538  // CR0 and CR1, while SupersetIntersect is a superset of the actual
539  // mathematical intersection. If these two ConstantRanges are equal, then
540  // we know we were able to represent the actual mathematical intersection
541  // of CR0 and CR1, and can use the same to generate an icmp instruction.
542  //
543  // Given what we're doing here and the semantics of guards, it would
544  // actually be correct to just use SubsetIntersect, but that may be too
545  // aggressive in cases we care about.
546  auto SubsetIntersect = CR0.inverse().unionWith(CR1.inverse()).inverse();
547  auto SupersetIntersect = CR0.intersectWith(CR1);
548 
549  APInt NewRHSAP;
550  CmpInst::Predicate Pred;
551  if (SubsetIntersect == SupersetIntersect &&
552  SubsetIntersect.getEquivalentICmp(Pred, NewRHSAP)) {
553  if (InsertPt) {
554  ConstantInt *NewRHS = ConstantInt::get(Cond0->getContext(), NewRHSAP);
555  Result = new ICmpInst(InsertPt, Pred, LHS, NewRHS, "wide.chk");
556  }
557  return true;
558  }
559  }
560  }
561 
562  {
563  SmallVector<GuardWideningImpl::RangeCheck, 4> Checks, CombinedChecks;
564  // TODO: Support InvertCondition case?
565  if (!InvertCondition &&
566  parseRangeChecks(Cond0, Checks) && parseRangeChecks(Cond1, Checks) &&
567  combineRangeChecks(Checks, CombinedChecks)) {
568  if (InsertPt) {
569  Result = nullptr;
570  for (auto &RC : CombinedChecks) {
571  makeAvailableAt(RC.getCheckInst(), InsertPt);
572  if (Result)
573  Result = BinaryOperator::CreateAnd(RC.getCheckInst(), Result, "",
574  InsertPt);
575  else
576  Result = RC.getCheckInst();
577  }
578 
579  Result->setName("wide.chk");
580  }
581  return true;
582  }
583  }
584 
585  // Base case -- just logical-and the two conditions together.
586 
587  if (InsertPt) {
588  makeAvailableAt(Cond0, InsertPt);
589  makeAvailableAt(Cond1, InsertPt);
590  if (InvertCondition)
591  Cond1 = BinaryOperator::CreateNot(Cond1, "inverted", InsertPt);
592  Result = BinaryOperator::CreateAnd(Cond0, Cond1, "wide.chk", InsertPt);
593  }
594 
595  // We were not able to compute Cond0 AND Cond1 for the price of one.
596  return false;
597 }
598 
599 bool GuardWideningImpl::parseRangeChecks(
601  SmallPtrSetImpl<Value *> &Visited) {
602  if (!Visited.insert(CheckCond).second)
603  return true;
604 
605  using namespace llvm::PatternMatch;
606 
607  {
608  Value *AndLHS, *AndRHS;
609  if (match(CheckCond, m_And(m_Value(AndLHS), m_Value(AndRHS))))
610  return parseRangeChecks(AndLHS, Checks) &&
611  parseRangeChecks(AndRHS, Checks);
612  }
613 
614  auto *IC = dyn_cast<ICmpInst>(CheckCond);
615  if (!IC || !IC->getOperand(0)->getType()->isIntegerTy() ||
616  (IC->getPredicate() != ICmpInst::ICMP_ULT &&
617  IC->getPredicate() != ICmpInst::ICMP_UGT))
618  return false;
619 
620  Value *CmpLHS = IC->getOperand(0), *CmpRHS = IC->getOperand(1);
621  if (IC->getPredicate() == ICmpInst::ICMP_UGT)
622  std::swap(CmpLHS, CmpRHS);
623 
624  auto &DL = IC->getModule()->getDataLayout();
625 
626  GuardWideningImpl::RangeCheck Check(
627  CmpLHS, cast<ConstantInt>(ConstantInt::getNullValue(CmpRHS->getType())),
628  CmpRHS, IC);
629 
630  if (!isKnownNonNegative(Check.getLength(), DL))
631  return false;
632 
633  // What we have in \c Check now is a correct interpretation of \p CheckCond.
634  // Try to see if we can move some constant offsets into the \c Offset field.
635 
636  bool Changed;
637  auto &Ctx = CheckCond->getContext();
638 
639  do {
640  Value *OpLHS;
641  ConstantInt *OpRHS;
642  Changed = false;
643 
644 #ifndef NDEBUG
645  auto *BaseInst = dyn_cast<Instruction>(Check.getBase());
646  assert((!BaseInst || DT.isReachableFromEntry(BaseInst->getParent())) &&
647  "Unreachable instruction?");
648 #endif
649 
650  if (match(Check.getBase(), m_Add(m_Value(OpLHS), m_ConstantInt(OpRHS)))) {
651  Check.setBase(OpLHS);
652  APInt NewOffset = Check.getOffsetValue() + OpRHS->getValue();
653  Check.setOffset(ConstantInt::get(Ctx, NewOffset));
654  Changed = true;
655  } else if (match(Check.getBase(),
656  m_Or(m_Value(OpLHS), m_ConstantInt(OpRHS)))) {
657  KnownBits Known = computeKnownBits(OpLHS, DL);
658  if ((OpRHS->getValue() & Known.Zero) == OpRHS->getValue()) {
659  Check.setBase(OpLHS);
660  APInt NewOffset = Check.getOffsetValue() + OpRHS->getValue();
661  Check.setOffset(ConstantInt::get(Ctx, NewOffset));
662  Changed = true;
663  }
664  }
665  } while (Changed);
666 
667  Checks.push_back(Check);
668  return true;
669 }
670 
671 bool GuardWideningImpl::combineRangeChecks(
674  unsigned OldCount = Checks.size();
675  while (!Checks.empty()) {
676  // Pick all of the range checks with a specific base and length, and try to
677  // merge them.
678  Value *CurrentBase = Checks.front().getBase();
679  Value *CurrentLength = Checks.front().getLength();
680 
682 
683  auto IsCurrentCheck = [&](GuardWideningImpl::RangeCheck &RC) {
684  return RC.getBase() == CurrentBase && RC.getLength() == CurrentLength;
685  };
686 
687  copy_if(Checks, std::back_inserter(CurrentChecks), IsCurrentCheck);
688  Checks.erase(remove_if(Checks, IsCurrentCheck), Checks.end());
689 
690  assert(CurrentChecks.size() != 0 && "We know we have at least one!");
691 
692  if (CurrentChecks.size() < 3) {
693  RangeChecksOut.insert(RangeChecksOut.end(), CurrentChecks.begin(),
694  CurrentChecks.end());
695  continue;
696  }
697 
698  // CurrentChecks.size() will typically be 3 here, but so far there has been
699  // no need to hard-code that fact.
700 
701  llvm::sort(CurrentChecks, [&](const GuardWideningImpl::RangeCheck &LHS,
702  const GuardWideningImpl::RangeCheck &RHS) {
703  return LHS.getOffsetValue().slt(RHS.getOffsetValue());
704  });
705 
706  // Note: std::sort should not invalidate the ChecksStart iterator.
707 
708  ConstantInt *MinOffset = CurrentChecks.front().getOffset(),
709  *MaxOffset = CurrentChecks.back().getOffset();
710 
711  unsigned BitWidth = MaxOffset->getValue().getBitWidth();
712  if ((MaxOffset->getValue() - MinOffset->getValue())
713  .ugt(APInt::getSignedMinValue(BitWidth)))
714  return false;
715 
716  APInt MaxDiff = MaxOffset->getValue() - MinOffset->getValue();
717  const APInt &HighOffset = MaxOffset->getValue();
718  auto OffsetOK = [&](const GuardWideningImpl::RangeCheck &RC) {
719  return (HighOffset - RC.getOffsetValue()).ult(MaxDiff);
720  };
721 
722  if (MaxDiff.isMinValue() ||
723  !std::all_of(std::next(CurrentChecks.begin()), CurrentChecks.end(),
724  OffsetOK))
725  return false;
726 
727  // We have a series of f+1 checks as:
728  //
729  // I+k_0 u< L ... Chk_0
730  // I+k_1 u< L ... Chk_1
731  // ...
732  // I+k_f u< L ... Chk_f
733  //
734  // with forall i in [0,f]: k_f-k_i u< k_f-k_0 ... Precond_0
735  // k_f-k_0 u< INT_MIN+k_f ... Precond_1
736  // k_f != k_0 ... Precond_2
737  //
738  // Claim:
739  // Chk_0 AND Chk_f implies all the other checks
740  //
741  // Informal proof sketch:
742  //
743  // We will show that the integer range [I+k_0,I+k_f] does not unsigned-wrap
744  // (i.e. going from I+k_0 to I+k_f does not cross the -1,0 boundary) and
745  // thus I+k_f is the greatest unsigned value in that range.
746  //
747  // This combined with Ckh_(f+1) shows that everything in that range is u< L.
748  // Via Precond_0 we know that all of the indices in Chk_0 through Chk_(f+1)
749  // lie in [I+k_0,I+k_f], this proving our claim.
750  //
751  // To see that [I+k_0,I+k_f] is not a wrapping range, note that there are
752  // two possibilities: I+k_0 u< I+k_f or I+k_0 >u I+k_f (they can't be equal
753  // since k_0 != k_f). In the former case, [I+k_0,I+k_f] is not a wrapping
754  // range by definition, and the latter case is impossible:
755  //
756  // 0-----I+k_f---I+k_0----L---INT_MAX,INT_MIN------------------(-1)
757  // xxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
758  //
759  // For Chk_0 to succeed, we'd have to have k_f-k_0 (the range highlighted
760  // with 'x' above) to be at least >u INT_MIN.
761 
762  RangeChecksOut.emplace_back(CurrentChecks.front());
763  RangeChecksOut.emplace_back(CurrentChecks.back());
764  }
765 
766  assert(RangeChecksOut.size() <= OldCount && "We pessimized!");
767  return RangeChecksOut.size() != OldCount;
768 }
769 
770 #ifndef NDEBUG
771 StringRef GuardWideningImpl::scoreTypeToString(WideningScore WS) {
772  switch (WS) {
773  case WS_IllegalOrNegative:
774  return "IllegalOrNegative";
775  case WS_Neutral:
776  return "Neutral";
777  case WS_Positive:
778  return "Positive";
779  case WS_VeryPositive:
780  return "VeryPositive";
781  }
782 
783  llvm_unreachable("Fully covered switch above!");
784 }
785 #endif
786 
789  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
790  auto &LI = AM.getResult<LoopAnalysis>(F);
791  auto &PDT = AM.getResult<PostDominatorTreeAnalysis>(F);
792  BranchProbabilityInfo *BPI = nullptr;
795  if (!GuardWideningImpl(DT, &PDT, LI, BPI, DT.getRootNode(),
796  [](BasicBlock*) { return true; } ).run())
797  return PreservedAnalyses::all();
798 
800  PA.preserveSet<CFGAnalyses>();
801  return PA;
802 }
803 
804 namespace {
805 struct GuardWideningLegacyPass : public FunctionPass {
806  static char ID;
807 
808  GuardWideningLegacyPass() : FunctionPass(ID) {
810  }
811 
812  bool runOnFunction(Function &F) override {
813  if (skipFunction(F))
814  return false;
815  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
816  auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
817  auto &PDT = getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();
818  BranchProbabilityInfo *BPI = nullptr;
820  BPI = &getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI();
821  return GuardWideningImpl(DT, &PDT, LI, BPI, DT.getRootNode(),
822  [](BasicBlock*) { return true; } ).run();
823  }
824 
825  void getAnalysisUsage(AnalysisUsage &AU) const override {
826  AU.setPreservesCFG();
832  }
833 };
834 
835 /// Same as above, but restricted to a single loop at a time. Can be
836 /// scheduled with other loop passes w/o breaking out of LPM
837 struct LoopGuardWideningLegacyPass : public LoopPass {
838  static char ID;
839 
840  LoopGuardWideningLegacyPass() : LoopPass(ID) {
842  }
843 
844  bool runOnLoop(Loop *L, LPPassManager &LPM) override {
845  if (skipLoop(L))
846  return false;
847  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
848  auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
849  auto *PDTWP = getAnalysisIfAvailable<PostDominatorTreeWrapperPass>();
850  auto *PDT = PDTWP ? &PDTWP->getPostDomTree() : nullptr;
851  BasicBlock *RootBB = L->getLoopPredecessor();
852  if (!RootBB)
853  RootBB = L->getHeader();
854  auto BlockFilter = [&](BasicBlock *BB) {
855  return BB == RootBB || L->contains(BB);
856  };
857  BranchProbabilityInfo *BPI = nullptr;
859  BPI = &getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI();
860  return GuardWideningImpl(DT, PDT, LI, BPI,
861  DT.getNode(RootBB), BlockFilter).run();
862  }
863 
864  void getAnalysisUsage(AnalysisUsage &AU) const override {
867  AU.setPreservesCFG();
870  }
871 };
872 }
873 
876 
877 INITIALIZE_PASS_BEGIN(GuardWideningLegacyPass, "guard-widening", "Widen guards",
878  false, false)
884 INITIALIZE_PASS_END(GuardWideningLegacyPass, "guard-widening", "Widen guards",
885  false, false)
886 
887 INITIALIZE_PASS_BEGIN(LoopGuardWideningLegacyPass, "loop-guard-widening",
888  "Widen guards (within a single loop, as a loop pass)",
889  false, false)
895 INITIALIZE_PASS_END(LoopGuardWideningLegacyPass, "loop-guard-widening",
896  "Widen guards (within a single loop, as a loop pass)",
897  false, false)
898 
900  return new GuardWideningLegacyPass();
901 }
902 
904  return new LoopGuardWideningLegacyPass();
905 }
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:81
static bool Check(DecodeStatus &Out, DecodeStatus In)
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
Definition: PatternMatch.h:725
void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, OptimizationRemarkEmitter *ORE=nullptr, bool UseInstrInfo=true)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks &#39;this&#39; from the containing basic block and deletes it.
Definition: Instruction.cpp:68
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:584
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:72
Safe Stack instrumentation pass
Definition: SafeStack.cpp:910
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
ConstantRange unionWith(const ConstantRange &CR) const
Return the range that results from the union of this range with another range.
static BinaryOperator * CreateNot(Value *Op, const Twine &Name="", Instruction *InsertBefore=nullptr)
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:770
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
OutputIt copy_if(R &&Range, OutputIt Out, UnaryPredicate P)
Provide wrappers to std::copy_if which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1089
Implements a dense probed hash-table based set.
Definition: DenseSet.h:250
guard widening
void initializeGuardWideningLegacyPassPass(PassRegistry &)
unsigned less than
Definition: InstrTypes.h:682
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:714
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1042
STATISTIC(NumFunctions, "Total number of functions")
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:231
F(f)
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
Definition: Dominators.cpp:300
static Constant * getNullValue(Type *Ty)
Constructor to create a &#39;0&#39; constant of arbitrary type.
Definition: Constants.cpp:268
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:51
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE, etc.
Definition: InstrTypes.h:755
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:684
NodeRef getPath(unsigned n) const
getPath - Return the n&#39;th node in the path from the entry node to the current node.
unsigned getPathLength() const
getPathLength - Return the length of the path from the entry node to the current node, counting both nodes.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
void setName(const Twine &Name)
Change the name of the value.
Definition: Value.cpp:295
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:939
#define LLVM_DUMP_METHOD
Definition: Compiler.h:74
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
Definition: PatternMatch.h:639
BlockT * getHeader() const
Definition: LoopInfo.h:100
Analysis pass which computes BranchProbabilityInfo.
ConstantRange intersectWith(const ConstantRange &CR) const
Return the range that results from the intersection of this range with another range.
class_match< ConstantInt > m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
Definition: PatternMatch.h:83
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:138
static Error getOffset(const SymbolRef &Sym, SectionRef Sec, uint64_t &Result)
bool isKnownNonNegative(const Value *V, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Returns true if the give value is known to be non-negative.
static cl::opt< bool > WidenFrequentBranches("guard-widening-widen-frequent-branches", cl::Hidden, cl::desc("Widen conditions of explicit branches into dominating guards in " "case if their taken frequency exceeds threshold set by " "guard-widening-frequent-branch-threshold option"), cl::init(false))
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:145
Legacy analysis pass which computes BranchProbabilityInfo.
Value * getOperand(unsigned i) const
Definition: User.h:170
static bool runOnFunction(Function &F, bool PostInlining)
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:410
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:154
* if(!EatIfPresent(lltok::kw_thread_local)) return false
ParseOptionalThreadLocal := /*empty.
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
BinaryOp_match< LHS, RHS, Instruction::Or > m_Or(const LHS &L, const RHS &R)
Definition: PatternMatch.h:731
df_iterator< T > df_end(const T &G)
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator begin()
Definition: SmallVector.h:129
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:371
static void PrintTypes(formatted_raw_ostream &OS, ArrayRef< MVT > Types)
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
Definition: PatternMatch.h:499
Represent the analysis usage information of a pass.
FunctionPass * createGuardWideningPass()
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
This instruction compares its operands according to the predicate given to the constructor.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:657
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:285
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:382
auto remove_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range))
Provide wrappers to std::remove_if which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1082
DomTreeNodeBase< NodeT > * getRootNode()
getRootNode - This returns the entry node for the CFG of the function.
iterator erase(const_iterator CI)
Definition: SmallVector.h:445
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:160
size_t size() const
Definition: SmallVector.h:53
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
auto find(R &&Range, const T &Val) -> decltype(adl_begin(Range))
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1063
void printAsOperand(raw_ostream &O, bool PrintType=true, const Module *M=nullptr) const
Print the name of this Value out to the specified raw_ostream.
Definition: AsmWriter.cpp:4197
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
static SDValue Widen(SelectionDAG *CurDAG, SDValue N)
BranchProbability getEdgeProbability(const BasicBlock *Src, unsigned IndexInSuccessors) const
Get an edge&#39;s probability, relative to other out-edges of the Src.
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:972
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
BlockT * getLoopPredecessor() const
If the given loop&#39;s header has exactly one unique predecessor outside the loop, return it...
Definition: LoopInfoImpl.h:202
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:110
void initializeLoopGuardWideningLegacyPassPass(PassRegistry &)
static ConstantRange makeExactICmpRegion(CmpInst::Predicate Pred, const APInt &Other)
Produce the exact range such that all values in the returned range satisfy the given predicate with a...
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:418
This is the shared class of boolean and integer constants.
Definition: Constants.h:84
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:847
bool dominates(const Instruction *Def, const Use &U) const
Return true if Def dominates a use in User.
Definition: Dominators.cpp:249
Analysis pass which computes a PostDominatorTree.
INITIALIZE_PASS_BEGIN(GuardWideningLegacyPass, "guard-widening", "Widen guards", false, false) if(WidenFrequentBranches) INITIALIZE_PASS_END(GuardWideningLegacyPass
This class represents a range of values.
Definition: ConstantRange.h:47
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:621
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:286
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:577
static cl::opt< unsigned > FrequentBranchThreshold("guard-widening-frequent-branch-threshold", cl::Hidden, cl::desc("When WidenFrequentBranches is set to true, this option is used " "to determine which branches are frequently taken. The criteria " "that a branch is taken more often than " "((FrequentBranchThreshold - 1) / FrequentBranchThreshold), then " "it is considered frequently taken"), cl::init(1000))
bool isGuard(const User *U)
Returns true iff U has semantics of a guard.
Definition: GuardUtils.cpp:18
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:133
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:941
df_iterator< T > df_begin(const T &G)
Class for arbitrary precision integers.
Definition: APInt.h:70
guard Widen guards
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
Represents analyses that only rely on functions&#39; control flow.
Definition: PassManager.h:115
iterator insert(iterator I, T &&Elt)
Definition: SmallVector.h:478
bool dominates(const DomTreeNodeBase< NodeT > *A, const DomTreeNodeBase< NodeT > *B) const
dominates - Returns true iff A dominates B.
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator end()
Definition: SmallVector.h:133
Analysis providing branch probability information.
void emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:652
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:56
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:459
void preserveSet()
Mark an analysis set as preserved.
Definition: PassManager.h:190
#define I(x, y, z)
Definition: MD5.cpp:58
void getLoopAnalysisUsage(AnalysisUsage &AU)
Helper to consistently add the set of standard passes to a loop pass&#39;s AnalysisUsage.
Definition: LoopUtils.cpp:128
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
Definition: PassManager.h:789
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:323
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:92
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
Definition: DenseMap.h:146
bool isMinValue() const
Determine if this is the smallest unsigned value.
Definition: APInt.h:437
static int const Threshold
TODO: Write a new FunctionPass AliasAnalysis so that it can keep a cache.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static APInt getSignedMinValue(unsigned numBits)
Gets minimum signed value of APInt for a specific bit width.
Definition: APInt.h:545
bool isSafeToSpeculativelyExecute(const Value *V, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr)
Return true if the instruction does not have any effects besides calculating the result and does not ...
LLVM Value Representation.
Definition: Value.h:73
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:46
The legacy pass manager&#39;s analysis pass to compute loop information.
Definition: LoopInfo.h:964
print Print MemDeps of function
unsigned greater than
Definition: InstrTypes.h:680
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:49
A container for analyses that lazily runs them and caches their results.
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:260
Pass * createLoopGuardWideningPass()
#define LLVM_DEBUG(X)
Definition: Debug.h:123
ConstantRange inverse() const
Return a new range that is the logical not of the current set.
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:44
const BasicBlock * getParent() const
Definition: Instruction.h:67
CmpClass_match< LHS, RHS, ICmpInst, ICmpInst::Predicate > m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R)
Definition: PatternMatch.h:990