LLVM  7.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/Analysis/LoopInfo.h"
47 #include "llvm/Analysis/LoopPass.h"
50 #include "llvm/IR/ConstantRange.h"
51 #include "llvm/IR/Dominators.h"
52 #include "llvm/IR/IntrinsicInst.h"
53 #include "llvm/IR/PatternMatch.h"
54 #include "llvm/Pass.h"
55 #include "llvm/Support/Debug.h"
56 #include "llvm/Support/KnownBits.h"
57 #include "llvm/Transforms/Scalar.h"
59 
60 using namespace llvm;
61 
62 #define DEBUG_TYPE "guard-widening"
63 
64 namespace {
65 
66 class GuardWideningImpl {
67  DominatorTree &DT;
68  PostDominatorTree *PDT;
69  LoopInfo &LI;
70 
71  /// Together, these describe the region of interest. This might be all of
72  /// the blocks within a function, or only a given loop's blocks and preheader.
73  DomTreeNode *Root;
74  std::function<bool(BasicBlock*)> BlockFilter;
75 
76  /// The set of guards whose conditions have been widened into dominating
77  /// guards.
78  SmallVector<IntrinsicInst *, 16> EliminatedGuards;
79 
80  /// The set of guards which have been widened to include conditions to other
81  /// guards.
82  DenseSet<IntrinsicInst *> WidenedGuards;
83 
84  /// Try to eliminate guard \p Guard by widening it into an earlier dominating
85  /// guard. \p DFSI is the DFS iterator on the dominator tree that is
86  /// currently visiting the block containing \p Guard, and \p GuardsPerBlock
87  /// maps BasicBlocks to the set of guards seen in that block.
88  bool eliminateGuardViaWidening(
89  IntrinsicInst *Guard, const df_iterator<DomTreeNode *> &DFSI,
91  GuardsPerBlock);
92 
93  /// Used to keep track of which widening potential is more effective.
94  enum WideningScore {
95  /// Don't widen.
96  WS_IllegalOrNegative,
97 
98  /// Widening is performance neutral as far as the cycles spent in check
99  /// conditions goes (but can still help, e.g., code layout, having less
100  /// deopt state).
101  WS_Neutral,
102 
103  /// Widening is profitable.
104  WS_Positive,
105 
106  /// Widening is very profitable. Not significantly different from \c
107  /// WS_Positive, except by the order.
108  WS_VeryPositive
109  };
110 
111  static StringRef scoreTypeToString(WideningScore WS);
112 
113  /// Compute the score for widening the condition in \p DominatedGuard
114  /// (contained in \p DominatedGuardLoop) into \p DominatingGuard (contained in
115  /// \p DominatingGuardLoop).
116  WideningScore computeWideningScore(IntrinsicInst *DominatedGuard,
117  Loop *DominatedGuardLoop,
118  IntrinsicInst *DominatingGuard,
119  Loop *DominatingGuardLoop);
120 
121  /// Helper to check if \p V can be hoisted to \p InsertPos.
122  bool isAvailableAt(Value *V, Instruction *InsertPos) {
124  return isAvailableAt(V, InsertPos, Visited);
125  }
126 
127  bool isAvailableAt(Value *V, Instruction *InsertPos,
129 
130  /// Helper to hoist \p V to \p InsertPos. Guaranteed to succeed if \c
131  /// isAvailableAt returned true.
132  void makeAvailableAt(Value *V, Instruction *InsertPos);
133 
134  /// Common helper used by \c widenGuard and \c isWideningCondProfitable. Try
135  /// to generate an expression computing the logical AND of \p Cond0 and \p
136  /// Cond1. Return true if the expression computing the AND is only as
137  /// expensive as computing one of the two. If \p InsertPt is true then
138  /// actually generate the resulting expression, make it available at \p
139  /// InsertPt and return it in \p Result (else no change to the IR is made).
140  bool widenCondCommon(Value *Cond0, Value *Cond1, Instruction *InsertPt,
141  Value *&Result);
142 
143  /// Represents a range check of the form \c Base + \c Offset u< \c Length,
144  /// with the constraint that \c Length is not negative. \c CheckInst is the
145  /// pre-existing instruction in the IR that computes the result of this range
146  /// check.
147  class RangeCheck {
148  Value *Base;
150  Value *Length;
151  ICmpInst *CheckInst;
152 
153  public:
154  explicit RangeCheck(Value *Base, ConstantInt *Offset, Value *Length,
155  ICmpInst *CheckInst)
156  : Base(Base), Offset(Offset), Length(Length), CheckInst(CheckInst) {}
157 
158  void setBase(Value *NewBase) { Base = NewBase; }
159  void setOffset(ConstantInt *NewOffset) { Offset = NewOffset; }
160 
161  Value *getBase() const { return Base; }
162  ConstantInt *getOffset() const { return Offset; }
163  const APInt &getOffsetValue() const { return getOffset()->getValue(); }
164  Value *getLength() const { return Length; };
165  ICmpInst *getCheckInst() const { return CheckInst; }
166 
167  void print(raw_ostream &OS, bool PrintTypes = false) {
168  OS << "Base: ";
169  Base->printAsOperand(OS, PrintTypes);
170  OS << " Offset: ";
171  Offset->printAsOperand(OS, PrintTypes);
172  OS << " Length: ";
173  Length->printAsOperand(OS, PrintTypes);
174  }
175 
176  LLVM_DUMP_METHOD void dump() {
177  print(dbgs());
178  dbgs() << "\n";
179  }
180  };
181 
182  /// Parse \p CheckCond into a conjunction (logical-and) of range checks; and
183  /// append them to \p Checks. Returns true on success, may clobber \c Checks
184  /// on failure.
185  bool parseRangeChecks(Value *CheckCond, SmallVectorImpl<RangeCheck> &Checks) {
186  SmallPtrSet<Value *, 8> Visited;
187  return parseRangeChecks(CheckCond, Checks, Visited);
188  }
189 
190  bool parseRangeChecks(Value *CheckCond, SmallVectorImpl<RangeCheck> &Checks,
191  SmallPtrSetImpl<Value *> &Visited);
192 
193  /// Combine the checks in \p Checks into a smaller set of checks and append
194  /// them into \p CombinedChecks. Return true on success (i.e. all of checks
195  /// in \p Checks were combined into \p CombinedChecks). Clobbers \p Checks
196  /// and \p CombinedChecks on success and on failure.
197  bool combineRangeChecks(SmallVectorImpl<RangeCheck> &Checks,
198  SmallVectorImpl<RangeCheck> &CombinedChecks);
199 
200  /// Can we compute the logical AND of \p Cond0 and \p Cond1 for the price of
201  /// computing only one of the two expressions?
202  bool isWideningCondProfitable(Value *Cond0, Value *Cond1) {
203  Value *ResultUnused;
204  return widenCondCommon(Cond0, Cond1, /*InsertPt=*/nullptr, ResultUnused);
205  }
206 
207  /// Widen \p ToWiden to fail if \p NewCondition is false (in addition to
208  /// whatever it is already checking).
209  void widenGuard(IntrinsicInst *ToWiden, Value *NewCondition) {
210  Value *Result;
211  widenCondCommon(ToWiden->getArgOperand(0), NewCondition, ToWiden, Result);
212  ToWiden->setArgOperand(0, Result);
213  }
214 
215 public:
216 
217  explicit GuardWideningImpl(DominatorTree &DT, PostDominatorTree *PDT,
218  LoopInfo &LI, DomTreeNode *Root,
219  std::function<bool(BasicBlock*)> BlockFilter)
220  : DT(DT), PDT(PDT), LI(LI), Root(Root), BlockFilter(BlockFilter) {}
221 
222  /// The entry point for this pass.
223  bool run();
224 };
225 }
226 
227 bool GuardWideningImpl::run() {
228  using namespace llvm::PatternMatch;
229 
231  bool Changed = false;
232 
233  for (auto DFI = df_begin(Root), DFE = df_end(Root);
234  DFI != DFE; ++DFI) {
235  auto *BB = (*DFI)->getBlock();
236  if (!BlockFilter(BB))
237  continue;
238 
239  auto &CurrentList = GuardsInBlock[BB];
240 
241  for (auto &I : *BB)
242  if (match(&I, m_Intrinsic<Intrinsic::experimental_guard>()))
243  CurrentList.push_back(cast<IntrinsicInst>(&I));
244 
245  for (auto *II : CurrentList)
246  Changed |= eliminateGuardViaWidening(II, DFI, GuardsInBlock);
247  }
248 
249  assert(EliminatedGuards.empty() || Changed);
250  for (auto *II : EliminatedGuards)
251  if (!WidenedGuards.count(II))
252  II->eraseFromParent();
253 
254  return Changed;
255 }
256 
257 bool GuardWideningImpl::eliminateGuardViaWidening(
258  IntrinsicInst *GuardInst, const df_iterator<DomTreeNode *> &DFSI,
260  GuardsInBlock) {
261  IntrinsicInst *BestSoFar = nullptr;
262  auto BestScoreSoFar = WS_IllegalOrNegative;
263  auto *GuardInstLoop = LI.getLoopFor(GuardInst->getParent());
264 
265  // In the set of dominating guards, find the one we can merge GuardInst with
266  // for the most profit.
267  for (unsigned i = 0, e = DFSI.getPathLength(); i != e; ++i) {
268  auto *CurBB = DFSI.getPath(i)->getBlock();
269  if (!BlockFilter(CurBB))
270  break;
271  auto *CurLoop = LI.getLoopFor(CurBB);
272  assert(GuardsInBlock.count(CurBB) && "Must have been populated by now!");
273  const auto &GuardsInCurBB = GuardsInBlock.find(CurBB)->second;
274 
275  auto I = GuardsInCurBB.begin();
276  auto E = GuardsInCurBB.end();
277 
278 #ifndef NDEBUG
279  {
280  unsigned Index = 0;
281  for (auto &I : *CurBB) {
282  if (Index == GuardsInCurBB.size())
283  break;
284  if (GuardsInCurBB[Index] == &I)
285  Index++;
286  }
287  assert(Index == GuardsInCurBB.size() &&
288  "Guards expected to be in order!");
289  }
290 #endif
291 
292  assert((i == (e - 1)) == (GuardInst->getParent() == CurBB) && "Bad DFS?");
293 
294  if (i == (e - 1)) {
295  // Corner case: make sure we're only looking at guards strictly dominating
296  // GuardInst when visiting GuardInst->getParent().
297  auto NewEnd = std::find(I, E, GuardInst);
298  assert(NewEnd != E && "GuardInst not in its own block?");
299  E = NewEnd;
300  }
301 
302  for (auto *Candidate : make_range(I, E)) {
303  auto Score =
304  computeWideningScore(GuardInst, GuardInstLoop, Candidate, CurLoop);
305  LLVM_DEBUG(dbgs() << "Score between " << *GuardInst->getArgOperand(0)
306  << " and " << *Candidate->getArgOperand(0) << " is "
307  << scoreTypeToString(Score) << "\n");
308  if (Score > BestScoreSoFar) {
309  BestScoreSoFar = Score;
310  BestSoFar = Candidate;
311  }
312  }
313  }
314 
315  if (BestScoreSoFar == WS_IllegalOrNegative) {
316  LLVM_DEBUG(dbgs() << "Did not eliminate guard " << *GuardInst << "\n");
317  return false;
318  }
319 
320  assert(BestSoFar != GuardInst && "Should have never visited same guard!");
321  assert(DT.dominates(BestSoFar, GuardInst) && "Should be!");
322 
323  LLVM_DEBUG(dbgs() << "Widening " << *GuardInst << " into " << *BestSoFar
324  << " with score " << scoreTypeToString(BestScoreSoFar)
325  << "\n");
326  widenGuard(BestSoFar, GuardInst->getArgOperand(0));
327  GuardInst->setArgOperand(0, ConstantInt::getTrue(GuardInst->getContext()));
328  EliminatedGuards.push_back(GuardInst);
329  WidenedGuards.insert(BestSoFar);
330  return true;
331 }
332 
333 GuardWideningImpl::WideningScore GuardWideningImpl::computeWideningScore(
334  IntrinsicInst *DominatedGuard, Loop *DominatedGuardLoop,
335  IntrinsicInst *DominatingGuard, Loop *DominatingGuardLoop) {
336  bool HoistingOutOfLoop = false;
337 
338  if (DominatingGuardLoop != DominatedGuardLoop) {
339  // Be conservative and don't widen into a sibling loop. TODO: If the
340  // sibling is colder, we should consider allowing this.
341  if (DominatingGuardLoop &&
342  !DominatingGuardLoop->contains(DominatedGuardLoop))
343  return WS_IllegalOrNegative;
344 
345  HoistingOutOfLoop = true;
346  }
347 
348  if (!isAvailableAt(DominatedGuard->getArgOperand(0), DominatingGuard))
349  return WS_IllegalOrNegative;
350 
351  // If the guard was conditional executed, it may never be reached
352  // dynamically. There are two potential downsides to hoisting it out of the
353  // conditionally executed region: 1) we may spuriously deopt without need and
354  // 2) we have the extra cost of computing the guard condition in the common
355  // case. At the moment, we really only consider the second in our heuristic
356  // here. TODO: evaluate cost model for spurious deopt
357  // NOTE: As written, this also lets us hoist right over another guard which
358  // is essentially just another spelling for control flow.
359  if (isWideningCondProfitable(DominatedGuard->getArgOperand(0),
360  DominatingGuard->getArgOperand(0)))
361  return HoistingOutOfLoop ? WS_VeryPositive : WS_Positive;
362 
363  if (HoistingOutOfLoop)
364  return WS_Positive;
365 
366  // Returns true if we might be hoisting above explicit control flow. Note
367  // that this completely ignores implicit control flow (guards, calls which
368  // throw, etc...). That choice appears arbitrary.
369  auto MaybeHoistingOutOfIf = [&]() {
370  auto *DominatingBlock = DominatingGuard->getParent();
371  auto *DominatedBlock = DominatedGuard->getParent();
372 
373  // Same Block?
374  if (DominatedBlock == DominatingBlock)
375  return false;
376  // Obvious successor (common loop header/preheader case)
377  if (DominatedBlock == DominatingBlock->getUniqueSuccessor())
378  return false;
379  // TODO: diamond, triangle cases
380  if (!PDT) return true;
381  return !PDT->dominates(DominatedGuard->getParent(),
382  DominatingGuard->getParent());
383  };
384 
385  return MaybeHoistingOutOfIf() ? WS_IllegalOrNegative : WS_Neutral;
386 }
387 
388 bool GuardWideningImpl::isAvailableAt(Value *V, Instruction *Loc,
390  auto *Inst = dyn_cast<Instruction>(V);
391  if (!Inst || DT.dominates(Inst, Loc) || Visited.count(Inst))
392  return true;
393 
394  if (!isSafeToSpeculativelyExecute(Inst, Loc, &DT) ||
395  Inst->mayReadFromMemory())
396  return false;
397 
398  Visited.insert(Inst);
399 
400  // We only want to go _up_ the dominance chain when recursing.
401  assert(!isa<PHINode>(Loc) &&
402  "PHIs should return false for isSafeToSpeculativelyExecute");
403  assert(DT.isReachableFromEntry(Inst->getParent()) &&
404  "We did a DFS from the block entry!");
405  return all_of(Inst->operands(),
406  [&](Value *Op) { return isAvailableAt(Op, Loc, Visited); });
407 }
408 
409 void GuardWideningImpl::makeAvailableAt(Value *V, Instruction *Loc) {
410  auto *Inst = dyn_cast<Instruction>(V);
411  if (!Inst || DT.dominates(Inst, Loc))
412  return;
413 
414  assert(isSafeToSpeculativelyExecute(Inst, Loc, &DT) &&
415  !Inst->mayReadFromMemory() && "Should've checked with isAvailableAt!");
416 
417  for (Value *Op : Inst->operands())
418  makeAvailableAt(Op, Loc);
419 
420  Inst->moveBefore(Loc);
421 }
422 
423 bool GuardWideningImpl::widenCondCommon(Value *Cond0, Value *Cond1,
424  Instruction *InsertPt, Value *&Result) {
425  using namespace llvm::PatternMatch;
426 
427  {
428  // L >u C0 && L >u C1 -> L >u max(C0, C1)
429  ConstantInt *RHS0, *RHS1;
430  Value *LHS;
431  ICmpInst::Predicate Pred0, Pred1;
432  if (match(Cond0, m_ICmp(Pred0, m_Value(LHS), m_ConstantInt(RHS0))) &&
433  match(Cond1, m_ICmp(Pred1, m_Specific(LHS), m_ConstantInt(RHS1)))) {
434 
435  ConstantRange CR0 =
437  ConstantRange CR1 =
439 
440  // SubsetIntersect is a subset of the actual mathematical intersection of
441  // CR0 and CR1, while SupersetIntersect is a superset of the actual
442  // mathematical intersection. If these two ConstantRanges are equal, then
443  // we know we were able to represent the actual mathematical intersection
444  // of CR0 and CR1, and can use the same to generate an icmp instruction.
445  //
446  // Given what we're doing here and the semantics of guards, it would
447  // actually be correct to just use SubsetIntersect, but that may be too
448  // aggressive in cases we care about.
449  auto SubsetIntersect = CR0.inverse().unionWith(CR1.inverse()).inverse();
450  auto SupersetIntersect = CR0.intersectWith(CR1);
451 
452  APInt NewRHSAP;
453  CmpInst::Predicate Pred;
454  if (SubsetIntersect == SupersetIntersect &&
455  SubsetIntersect.getEquivalentICmp(Pred, NewRHSAP)) {
456  if (InsertPt) {
457  ConstantInt *NewRHS = ConstantInt::get(Cond0->getContext(), NewRHSAP);
458  Result = new ICmpInst(InsertPt, Pred, LHS, NewRHS, "wide.chk");
459  }
460  return true;
461  }
462  }
463  }
464 
465  {
466  SmallVector<GuardWideningImpl::RangeCheck, 4> Checks, CombinedChecks;
467  if (parseRangeChecks(Cond0, Checks) && parseRangeChecks(Cond1, Checks) &&
468  combineRangeChecks(Checks, CombinedChecks)) {
469  if (InsertPt) {
470  Result = nullptr;
471  for (auto &RC : CombinedChecks) {
472  makeAvailableAt(RC.getCheckInst(), InsertPt);
473  if (Result)
474  Result = BinaryOperator::CreateAnd(RC.getCheckInst(), Result, "",
475  InsertPt);
476  else
477  Result = RC.getCheckInst();
478  }
479 
480  Result->setName("wide.chk");
481  }
482  return true;
483  }
484  }
485 
486  // Base case -- just logical-and the two conditions together.
487 
488  if (InsertPt) {
489  makeAvailableAt(Cond0, InsertPt);
490  makeAvailableAt(Cond1, InsertPt);
491 
492  Result = BinaryOperator::CreateAnd(Cond0, Cond1, "wide.chk", InsertPt);
493  }
494 
495  // We were not able to compute Cond0 AND Cond1 for the price of one.
496  return false;
497 }
498 
499 bool GuardWideningImpl::parseRangeChecks(
501  SmallPtrSetImpl<Value *> &Visited) {
502  if (!Visited.insert(CheckCond).second)
503  return true;
504 
505  using namespace llvm::PatternMatch;
506 
507  {
508  Value *AndLHS, *AndRHS;
509  if (match(CheckCond, m_And(m_Value(AndLHS), m_Value(AndRHS))))
510  return parseRangeChecks(AndLHS, Checks) &&
511  parseRangeChecks(AndRHS, Checks);
512  }
513 
514  auto *IC = dyn_cast<ICmpInst>(CheckCond);
515  if (!IC || !IC->getOperand(0)->getType()->isIntegerTy() ||
516  (IC->getPredicate() != ICmpInst::ICMP_ULT &&
517  IC->getPredicate() != ICmpInst::ICMP_UGT))
518  return false;
519 
520  Value *CmpLHS = IC->getOperand(0), *CmpRHS = IC->getOperand(1);
521  if (IC->getPredicate() == ICmpInst::ICMP_UGT)
522  std::swap(CmpLHS, CmpRHS);
523 
524  auto &DL = IC->getModule()->getDataLayout();
525 
526  GuardWideningImpl::RangeCheck Check(
527  CmpLHS, cast<ConstantInt>(ConstantInt::getNullValue(CmpRHS->getType())),
528  CmpRHS, IC);
529 
530  if (!isKnownNonNegative(Check.getLength(), DL))
531  return false;
532 
533  // What we have in \c Check now is a correct interpretation of \p CheckCond.
534  // Try to see if we can move some constant offsets into the \c Offset field.
535 
536  bool Changed;
537  auto &Ctx = CheckCond->getContext();
538 
539  do {
540  Value *OpLHS;
541  ConstantInt *OpRHS;
542  Changed = false;
543 
544 #ifndef NDEBUG
545  auto *BaseInst = dyn_cast<Instruction>(Check.getBase());
546  assert((!BaseInst || DT.isReachableFromEntry(BaseInst->getParent())) &&
547  "Unreachable instruction?");
548 #endif
549 
550  if (match(Check.getBase(), m_Add(m_Value(OpLHS), m_ConstantInt(OpRHS)))) {
551  Check.setBase(OpLHS);
552  APInt NewOffset = Check.getOffsetValue() + OpRHS->getValue();
553  Check.setOffset(ConstantInt::get(Ctx, NewOffset));
554  Changed = true;
555  } else if (match(Check.getBase(),
556  m_Or(m_Value(OpLHS), m_ConstantInt(OpRHS)))) {
557  KnownBits Known = computeKnownBits(OpLHS, DL);
558  if ((OpRHS->getValue() & Known.Zero) == OpRHS->getValue()) {
559  Check.setBase(OpLHS);
560  APInt NewOffset = Check.getOffsetValue() + OpRHS->getValue();
561  Check.setOffset(ConstantInt::get(Ctx, NewOffset));
562  Changed = true;
563  }
564  }
565  } while (Changed);
566 
567  Checks.push_back(Check);
568  return true;
569 }
570 
571 bool GuardWideningImpl::combineRangeChecks(
574  unsigned OldCount = Checks.size();
575  while (!Checks.empty()) {
576  // Pick all of the range checks with a specific base and length, and try to
577  // merge them.
578  Value *CurrentBase = Checks.front().getBase();
579  Value *CurrentLength = Checks.front().getLength();
580 
582 
583  auto IsCurrentCheck = [&](GuardWideningImpl::RangeCheck &RC) {
584  return RC.getBase() == CurrentBase && RC.getLength() == CurrentLength;
585  };
586 
587  copy_if(Checks, std::back_inserter(CurrentChecks), IsCurrentCheck);
588  Checks.erase(remove_if(Checks, IsCurrentCheck), Checks.end());
589 
590  assert(CurrentChecks.size() != 0 && "We know we have at least one!");
591 
592  if (CurrentChecks.size() < 3) {
593  RangeChecksOut.insert(RangeChecksOut.end(), CurrentChecks.begin(),
594  CurrentChecks.end());
595  continue;
596  }
597 
598  // CurrentChecks.size() will typically be 3 here, but so far there has been
599  // no need to hard-code that fact.
600 
601  llvm::sort(CurrentChecks.begin(), CurrentChecks.end(),
602  [&](const GuardWideningImpl::RangeCheck &LHS,
603  const GuardWideningImpl::RangeCheck &RHS) {
604  return LHS.getOffsetValue().slt(RHS.getOffsetValue());
605  });
606 
607  // Note: std::sort should not invalidate the ChecksStart iterator.
608 
609  ConstantInt *MinOffset = CurrentChecks.front().getOffset(),
610  *MaxOffset = CurrentChecks.back().getOffset();
611 
612  unsigned BitWidth = MaxOffset->getValue().getBitWidth();
613  if ((MaxOffset->getValue() - MinOffset->getValue())
614  .ugt(APInt::getSignedMinValue(BitWidth)))
615  return false;
616 
617  APInt MaxDiff = MaxOffset->getValue() - MinOffset->getValue();
618  const APInt &HighOffset = MaxOffset->getValue();
619  auto OffsetOK = [&](const GuardWideningImpl::RangeCheck &RC) {
620  return (HighOffset - RC.getOffsetValue()).ult(MaxDiff);
621  };
622 
623  if (MaxDiff.isMinValue() ||
624  !std::all_of(std::next(CurrentChecks.begin()), CurrentChecks.end(),
625  OffsetOK))
626  return false;
627 
628  // We have a series of f+1 checks as:
629  //
630  // I+k_0 u< L ... Chk_0
631  // I+k_1 u< L ... Chk_1
632  // ...
633  // I+k_f u< L ... Chk_f
634  //
635  // with forall i in [0,f]: k_f-k_i u< k_f-k_0 ... Precond_0
636  // k_f-k_0 u< INT_MIN+k_f ... Precond_1
637  // k_f != k_0 ... Precond_2
638  //
639  // Claim:
640  // Chk_0 AND Chk_f implies all the other checks
641  //
642  // Informal proof sketch:
643  //
644  // We will show that the integer range [I+k_0,I+k_f] does not unsigned-wrap
645  // (i.e. going from I+k_0 to I+k_f does not cross the -1,0 boundary) and
646  // thus I+k_f is the greatest unsigned value in that range.
647  //
648  // This combined with Ckh_(f+1) shows that everything in that range is u< L.
649  // Via Precond_0 we know that all of the indices in Chk_0 through Chk_(f+1)
650  // lie in [I+k_0,I+k_f], this proving our claim.
651  //
652  // To see that [I+k_0,I+k_f] is not a wrapping range, note that there are
653  // two possibilities: I+k_0 u< I+k_f or I+k_0 >u I+k_f (they can't be equal
654  // since k_0 != k_f). In the former case, [I+k_0,I+k_f] is not a wrapping
655  // range by definition, and the latter case is impossible:
656  //
657  // 0-----I+k_f---I+k_0----L---INT_MAX,INT_MIN------------------(-1)
658  // xxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
659  //
660  // For Chk_0 to succeed, we'd have to have k_f-k_0 (the range highlighted
661  // with 'x' above) to be at least >u INT_MIN.
662 
663  RangeChecksOut.emplace_back(CurrentChecks.front());
664  RangeChecksOut.emplace_back(CurrentChecks.back());
665  }
666 
667  assert(RangeChecksOut.size() <= OldCount && "We pessimized!");
668  return RangeChecksOut.size() != OldCount;
669 }
670 
671 #ifndef NDEBUG
672 StringRef GuardWideningImpl::scoreTypeToString(WideningScore WS) {
673  switch (WS) {
674  case WS_IllegalOrNegative:
675  return "IllegalOrNegative";
676  case WS_Neutral:
677  return "Neutral";
678  case WS_Positive:
679  return "Positive";
680  case WS_VeryPositive:
681  return "VeryPositive";
682  }
683 
684  llvm_unreachable("Fully covered switch above!");
685 }
686 #endif
687 
690  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
691  auto &LI = AM.getResult<LoopAnalysis>(F);
692  auto &PDT = AM.getResult<PostDominatorTreeAnalysis>(F);
693  if (!GuardWideningImpl(DT, &PDT, LI, DT.getRootNode(),
694  [](BasicBlock*) { return true; } ).run())
695  return PreservedAnalyses::all();
696 
698  PA.preserveSet<CFGAnalyses>();
699  return PA;
700 }
701 
702 namespace {
703 struct GuardWideningLegacyPass : public FunctionPass {
704  static char ID;
705 
706  GuardWideningLegacyPass() : FunctionPass(ID) {
708  }
709 
710  bool runOnFunction(Function &F) override {
711  if (skipFunction(F))
712  return false;
713  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
714  auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
715  auto &PDT = getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();
716  return GuardWideningImpl(DT, &PDT, LI, DT.getRootNode(),
717  [](BasicBlock*) { return true; } ).run();
718  }
719 
720  void getAnalysisUsage(AnalysisUsage &AU) const override {
721  AU.setPreservesCFG();
725  }
726 };
727 
728 /// Same as above, but restricted to a single loop at a time. Can be
729 /// scheduled with other loop passes w/o breaking out of LPM
730 struct LoopGuardWideningLegacyPass : public LoopPass {
731  static char ID;
732 
733  LoopGuardWideningLegacyPass() : LoopPass(ID) {
735  }
736 
737  bool runOnLoop(Loop *L, LPPassManager &LPM) override {
738  if (skipLoop(L))
739  return false;
740  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
741  auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
742  auto *PDTWP = getAnalysisIfAvailable<PostDominatorTreeWrapperPass>();
743  auto *PDT = PDTWP ? &PDTWP->getPostDomTree() : nullptr;
744  BasicBlock *RootBB = L->getLoopPredecessor();
745  if (!RootBB)
746  RootBB = L->getHeader();
747  auto BlockFilter = [&](BasicBlock *BB) {
748  return BB == RootBB || L->contains(BB);
749  };
750  return GuardWideningImpl(DT, PDT, LI,
751  DT.getNode(RootBB), BlockFilter).run();
752  }
753 
754  void getAnalysisUsage(AnalysisUsage &AU) const override {
755  AU.setPreservesCFG();
758  }
759 };
760 }
761 
764 
765 INITIALIZE_PASS_BEGIN(GuardWideningLegacyPass, "guard-widening", "Widen guards",
766  false, false)
770 INITIALIZE_PASS_END(GuardWideningLegacyPass, "guard-widening", "Widen guards",
771  false, false)
772 
773 INITIALIZE_PASS_BEGIN(LoopGuardWideningLegacyPass, "loop-guard-widening",
774  "Widen guards (within a single loop, as a loop pass)",
775  false, false)
779 INITIALIZE_PASS_END(LoopGuardWideningLegacyPass, "loop-guard-widening",
780  "Widen guards (within a single loop, as a loop pass)",
781  false, false)
782 
784  return new GuardWideningLegacyPass();
785 }
786 
788  return new LoopGuardWideningLegacyPass();
789 }
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:718
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:72
Safe Stack instrumentation pass
Definition: SafeStack.cpp:900
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.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:687
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
LLVM_ATTRIBUTE_ALWAYS_INLINE size_type size() const
Definition: SmallVector.h:137
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:955
Implements a dense probed hash-table based set.
Definition: DenseSet.h:221
guard widening
void initializeGuardWideningLegacyPassPass(PassRegistry &)
unsigned less than
Definition: InstrTypes.h:910
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:908
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:225
F(f)
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds...
Definition: Compiler.h:452
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
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
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
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)
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:142
INITIALIZE_PASS_BEGIN(GuardWideningLegacyPass, "guard-widening", "Widen guards", false, false) INITIALIZE_PASS_END(GuardWideningLegacyPass
static bool runOnFunction(Function &F, bool PostInlining)
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
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
BinaryOp_match< LHS, RHS, Instruction::Or > m_Or(const LHS &L, const RHS &R)
Definition: PatternMatch.h:724
bool isKnownNonNegative(const Value *V, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr)
Returns true if the give value is known to be non-negative.
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:117
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:885
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:285
void setArgOperand(unsigned i, Value *v)
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:948
iterator erase(const_iterator CI)
Definition: SmallVector.h:446
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:159
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:929
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:4143
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)
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:859
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:861
Analysis pass which computes a PostDominatorTree.
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
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:924
df_iterator< T > df_begin(const T &G)
Class for arbitrary precision integers.
Definition: APInt.h:69
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:479
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator end()
Definition: SmallVector.h:121
void emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:653
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:62
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:459
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:1226
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
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
Value * getArgOperand(unsigned i) const
getArgOperand/setArgOperand - Return/set the i-th call argument.
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:908
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:254
Pass * createLoopGuardWideningPass()
#define LLVM_DEBUG(X)
Definition: Debug.h:119
ConstantRange inverse() const
Return a new range that is the logical not of the current set.
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)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
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:983