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