LLVM  6.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 "llvm/ADT/DenseMap.h"
45 #include "llvm/Analysis/LoopInfo.h"
48 #include "llvm/IR/ConstantRange.h"
49 #include "llvm/IR/Dominators.h"
50 #include "llvm/IR/IntrinsicInst.h"
51 #include "llvm/IR/PatternMatch.h"
52 #include "llvm/Pass.h"
53 #include "llvm/Support/Debug.h"
54 #include "llvm/Support/KnownBits.h"
55 #include "llvm/Transforms/Scalar.h"
56 
57 using namespace llvm;
58 
59 #define DEBUG_TYPE "guard-widening"
60 
61 namespace {
62 
63 class GuardWideningImpl {
64  DominatorTree &DT;
65  PostDominatorTree &PDT;
66  LoopInfo &LI;
67 
68  /// The set of guards whose conditions have been widened into dominating
69  /// guards.
70  SmallVector<IntrinsicInst *, 16> EliminatedGuards;
71 
72  /// The set of guards which have been widened to include conditions to other
73  /// guards.
74  DenseSet<IntrinsicInst *> WidenedGuards;
75 
76  /// Try to eliminate guard \p Guard by widening it into an earlier dominating
77  /// guard. \p DFSI is the DFS iterator on the dominator tree that is
78  /// currently visiting the block containing \p Guard, and \p GuardsPerBlock
79  /// maps BasicBlocks to the set of guards seen in that block.
80  bool eliminateGuardViaWidening(
81  IntrinsicInst *Guard, const df_iterator<DomTreeNode *> &DFSI,
83  GuardsPerBlock);
84 
85  /// Used to keep track of which widening potential is more effective.
86  enum WideningScore {
87  /// Don't widen.
88  WS_IllegalOrNegative,
89 
90  /// Widening is performance neutral as far as the cycles spent in check
91  /// conditions goes (but can still help, e.g., code layout, having less
92  /// deopt state).
93  WS_Neutral,
94 
95  /// Widening is profitable.
96  WS_Positive,
97 
98  /// Widening is very profitable. Not significantly different from \c
99  /// WS_Positive, except by the order.
100  WS_VeryPositive
101  };
102 
103  static StringRef scoreTypeToString(WideningScore WS);
104 
105  /// Compute the score for widening the condition in \p DominatedGuard
106  /// (contained in \p DominatedGuardLoop) into \p DominatingGuard (contained in
107  /// \p DominatingGuardLoop).
108  WideningScore computeWideningScore(IntrinsicInst *DominatedGuard,
109  Loop *DominatedGuardLoop,
110  IntrinsicInst *DominatingGuard,
111  Loop *DominatingGuardLoop);
112 
113  /// Helper to check if \p V can be hoisted to \p InsertPos.
114  bool isAvailableAt(Value *V, Instruction *InsertPos) {
116  return isAvailableAt(V, InsertPos, Visited);
117  }
118 
119  bool isAvailableAt(Value *V, Instruction *InsertPos,
121 
122  /// Helper to hoist \p V to \p InsertPos. Guaranteed to succeed if \c
123  /// isAvailableAt returned true.
124  void makeAvailableAt(Value *V, Instruction *InsertPos);
125 
126  /// Common helper used by \c widenGuard and \c isWideningCondProfitable. Try
127  /// to generate an expression computing the logical AND of \p Cond0 and \p
128  /// Cond1. Return true if the expression computing the AND is only as
129  /// expensive as computing one of the two. If \p InsertPt is true then
130  /// actually generate the resulting expression, make it available at \p
131  /// InsertPt and return it in \p Result (else no change to the IR is made).
132  bool widenCondCommon(Value *Cond0, Value *Cond1, Instruction *InsertPt,
133  Value *&Result);
134 
135  /// Represents a range check of the form \c Base + \c Offset u< \c Length,
136  /// with the constraint that \c Length is not negative. \c CheckInst is the
137  /// pre-existing instruction in the IR that computes the result of this range
138  /// check.
139  class RangeCheck {
140  Value *Base;
142  Value *Length;
143  ICmpInst *CheckInst;
144 
145  public:
146  explicit RangeCheck(Value *Base, ConstantInt *Offset, Value *Length,
147  ICmpInst *CheckInst)
148  : Base(Base), Offset(Offset), Length(Length), CheckInst(CheckInst) {}
149 
150  void setBase(Value *NewBase) { Base = NewBase; }
151  void setOffset(ConstantInt *NewOffset) { Offset = NewOffset; }
152 
153  Value *getBase() const { return Base; }
154  ConstantInt *getOffset() const { return Offset; }
155  const APInt &getOffsetValue() const { return getOffset()->getValue(); }
156  Value *getLength() const { return Length; };
157  ICmpInst *getCheckInst() const { return CheckInst; }
158 
159  void print(raw_ostream &OS, bool PrintTypes = false) {
160  OS << "Base: ";
161  Base->printAsOperand(OS, PrintTypes);
162  OS << " Offset: ";
163  Offset->printAsOperand(OS, PrintTypes);
164  OS << " Length: ";
165  Length->printAsOperand(OS, PrintTypes);
166  }
167 
168  LLVM_DUMP_METHOD void dump() {
169  print(dbgs());
170  dbgs() << "\n";
171  }
172  };
173 
174  /// Parse \p CheckCond into a conjunction (logical-and) of range checks; and
175  /// append them to \p Checks. Returns true on success, may clobber \c Checks
176  /// on failure.
177  bool parseRangeChecks(Value *CheckCond, SmallVectorImpl<RangeCheck> &Checks) {
178  SmallPtrSet<Value *, 8> Visited;
179  return parseRangeChecks(CheckCond, Checks, Visited);
180  }
181 
182  bool parseRangeChecks(Value *CheckCond, SmallVectorImpl<RangeCheck> &Checks,
183  SmallPtrSetImpl<Value *> &Visited);
184 
185  /// Combine the checks in \p Checks into a smaller set of checks and append
186  /// them into \p CombinedChecks. Return true on success (i.e. all of checks
187  /// in \p Checks were combined into \p CombinedChecks). Clobbers \p Checks
188  /// and \p CombinedChecks on success and on failure.
189  bool combineRangeChecks(SmallVectorImpl<RangeCheck> &Checks,
190  SmallVectorImpl<RangeCheck> &CombinedChecks);
191 
192  /// Can we compute the logical AND of \p Cond0 and \p Cond1 for the price of
193  /// computing only one of the two expressions?
194  bool isWideningCondProfitable(Value *Cond0, Value *Cond1) {
195  Value *ResultUnused;
196  return widenCondCommon(Cond0, Cond1, /*InsertPt=*/nullptr, ResultUnused);
197  }
198 
199  /// Widen \p ToWiden to fail if \p NewCondition is false (in addition to
200  /// whatever it is already checking).
201  void widenGuard(IntrinsicInst *ToWiden, Value *NewCondition) {
202  Value *Result;
203  widenCondCommon(ToWiden->getArgOperand(0), NewCondition, ToWiden, Result);
204  ToWiden->setArgOperand(0, Result);
205  }
206 
207 public:
208  explicit GuardWideningImpl(DominatorTree &DT, PostDominatorTree &PDT,
209  LoopInfo &LI)
210  : DT(DT), PDT(PDT), LI(LI) {}
211 
212  /// The entry point for this pass.
213  bool run();
214 };
215 
216 struct GuardWideningLegacyPass : public FunctionPass {
217  static char ID;
218  GuardWideningPass Impl;
219 
220  GuardWideningLegacyPass() : FunctionPass(ID) {
222  }
223 
224  bool runOnFunction(Function &F) override {
225  if (skipFunction(F))
226  return false;
227  return GuardWideningImpl(
228  getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
229  getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree(),
230  getAnalysis<LoopInfoWrapperPass>().getLoopInfo()).run();
231  }
232 
233  void getAnalysisUsage(AnalysisUsage &AU) const override {
234  AU.setPreservesCFG();
238  }
239 };
240 
241 }
242 
243 bool GuardWideningImpl::run() {
244  using namespace llvm::PatternMatch;
245 
247  bool Changed = false;
248 
249  for (auto DFI = df_begin(DT.getRootNode()), DFE = df_end(DT.getRootNode());
250  DFI != DFE; ++DFI) {
251  auto *BB = (*DFI)->getBlock();
252  auto &CurrentList = GuardsInBlock[BB];
253 
254  for (auto &I : *BB)
255  if (match(&I, m_Intrinsic<Intrinsic::experimental_guard>()))
256  CurrentList.push_back(cast<IntrinsicInst>(&I));
257 
258  for (auto *II : CurrentList)
259  Changed |= eliminateGuardViaWidening(II, DFI, GuardsInBlock);
260  }
261 
262  for (auto *II : EliminatedGuards)
263  if (!WidenedGuards.count(II))
264  II->eraseFromParent();
265 
266  return Changed;
267 }
268 
269 bool GuardWideningImpl::eliminateGuardViaWidening(
270  IntrinsicInst *GuardInst, const df_iterator<DomTreeNode *> &DFSI,
272  GuardsInBlock) {
273  IntrinsicInst *BestSoFar = nullptr;
274  auto BestScoreSoFar = WS_IllegalOrNegative;
275  auto *GuardInstLoop = LI.getLoopFor(GuardInst->getParent());
276 
277  // In the set of dominating guards, find the one we can merge GuardInst with
278  // for the most profit.
279  for (unsigned i = 0, e = DFSI.getPathLength(); i != e; ++i) {
280  auto *CurBB = DFSI.getPath(i)->getBlock();
281  auto *CurLoop = LI.getLoopFor(CurBB);
282  assert(GuardsInBlock.count(CurBB) && "Must have been populated by now!");
283  const auto &GuardsInCurBB = GuardsInBlock.find(CurBB)->second;
284 
285  auto I = GuardsInCurBB.begin();
286  auto E = GuardsInCurBB.end();
287 
288 #ifndef NDEBUG
289  {
290  unsigned Index = 0;
291  for (auto &I : *CurBB) {
292  if (Index == GuardsInCurBB.size())
293  break;
294  if (GuardsInCurBB[Index] == &I)
295  Index++;
296  }
297  assert(Index == GuardsInCurBB.size() &&
298  "Guards expected to be in order!");
299  }
300 #endif
301 
302  assert((i == (e - 1)) == (GuardInst->getParent() == CurBB) && "Bad DFS?");
303 
304  if (i == (e - 1)) {
305  // Corner case: make sure we're only looking at guards strictly dominating
306  // GuardInst when visiting GuardInst->getParent().
307  auto NewEnd = std::find(I, E, GuardInst);
308  assert(NewEnd != E && "GuardInst not in its own block?");
309  E = NewEnd;
310  }
311 
312  for (auto *Candidate : make_range(I, E)) {
313  auto Score =
314  computeWideningScore(GuardInst, GuardInstLoop, Candidate, CurLoop);
315  DEBUG(dbgs() << "Score between " << *GuardInst->getArgOperand(0)
316  << " and " << *Candidate->getArgOperand(0) << " is "
317  << scoreTypeToString(Score) << "\n");
318  if (Score > BestScoreSoFar) {
319  BestScoreSoFar = Score;
320  BestSoFar = Candidate;
321  }
322  }
323  }
324 
325  if (BestScoreSoFar == WS_IllegalOrNegative) {
326  DEBUG(dbgs() << "Did not eliminate guard " << *GuardInst << "\n");
327  return false;
328  }
329 
330  assert(BestSoFar != GuardInst && "Should have never visited same guard!");
331  assert(DT.dominates(BestSoFar, GuardInst) && "Should be!");
332 
333  DEBUG(dbgs() << "Widening " << *GuardInst << " into " << *BestSoFar
334  << " with score " << scoreTypeToString(BestScoreSoFar) << "\n");
335  widenGuard(BestSoFar, GuardInst->getArgOperand(0));
336  GuardInst->setArgOperand(0, ConstantInt::getTrue(GuardInst->getContext()));
337  EliminatedGuards.push_back(GuardInst);
338  WidenedGuards.insert(BestSoFar);
339  return true;
340 }
341 
342 GuardWideningImpl::WideningScore GuardWideningImpl::computeWideningScore(
343  IntrinsicInst *DominatedGuard, Loop *DominatedGuardLoop,
344  IntrinsicInst *DominatingGuard, Loop *DominatingGuardLoop) {
345  bool HoistingOutOfLoop = false;
346 
347  if (DominatingGuardLoop != DominatedGuardLoop) {
348  if (DominatingGuardLoop &&
349  !DominatingGuardLoop->contains(DominatedGuardLoop))
350  return WS_IllegalOrNegative;
351 
352  HoistingOutOfLoop = true;
353  }
354 
355  if (!isAvailableAt(DominatedGuard->getArgOperand(0), DominatingGuard))
356  return WS_IllegalOrNegative;
357 
358  bool HoistingOutOfIf =
359  !PDT.dominates(DominatedGuard->getParent(), DominatingGuard->getParent());
360 
361  if (isWideningCondProfitable(DominatedGuard->getArgOperand(0),
362  DominatingGuard->getArgOperand(0)))
363  return HoistingOutOfLoop ? WS_VeryPositive : WS_Positive;
364 
365  if (HoistingOutOfLoop)
366  return WS_Positive;
367 
368  return HoistingOutOfIf ? WS_IllegalOrNegative : WS_Neutral;
369 }
370 
371 bool GuardWideningImpl::isAvailableAt(Value *V, Instruction *Loc,
373  auto *Inst = dyn_cast<Instruction>(V);
374  if (!Inst || DT.dominates(Inst, Loc) || Visited.count(Inst))
375  return true;
376 
377  if (!isSafeToSpeculativelyExecute(Inst, Loc, &DT) ||
378  Inst->mayReadFromMemory())
379  return false;
380 
381  Visited.insert(Inst);
382 
383  // We only want to go _up_ the dominance chain when recursing.
384  assert(!isa<PHINode>(Loc) &&
385  "PHIs should return false for isSafeToSpeculativelyExecute");
386  assert(DT.isReachableFromEntry(Inst->getParent()) &&
387  "We did a DFS from the block entry!");
388  return all_of(Inst->operands(),
389  [&](Value *Op) { return isAvailableAt(Op, Loc, Visited); });
390 }
391 
392 void GuardWideningImpl::makeAvailableAt(Value *V, Instruction *Loc) {
393  auto *Inst = dyn_cast<Instruction>(V);
394  if (!Inst || DT.dominates(Inst, Loc))
395  return;
396 
397  assert(isSafeToSpeculativelyExecute(Inst, Loc, &DT) &&
398  !Inst->mayReadFromMemory() && "Should've checked with isAvailableAt!");
399 
400  for (Value *Op : Inst->operands())
401  makeAvailableAt(Op, Loc);
402 
403  Inst->moveBefore(Loc);
404 }
405 
406 bool GuardWideningImpl::widenCondCommon(Value *Cond0, Value *Cond1,
407  Instruction *InsertPt, Value *&Result) {
408  using namespace llvm::PatternMatch;
409 
410  {
411  // L >u C0 && L >u C1 -> L >u max(C0, C1)
412  ConstantInt *RHS0, *RHS1;
413  Value *LHS;
414  ICmpInst::Predicate Pred0, Pred1;
415  if (match(Cond0, m_ICmp(Pred0, m_Value(LHS), m_ConstantInt(RHS0))) &&
416  match(Cond1, m_ICmp(Pred1, m_Specific(LHS), m_ConstantInt(RHS1)))) {
417 
418  ConstantRange CR0 =
420  ConstantRange CR1 =
422 
423  // SubsetIntersect is a subset of the actual mathematical intersection of
424  // CR0 and CR1, while SupersetIntersect is a superset of the actual
425  // mathematical intersection. If these two ConstantRanges are equal, then
426  // we know we were able to represent the actual mathematical intersection
427  // of CR0 and CR1, and can use the same to generate an icmp instruction.
428  //
429  // Given what we're doing here and the semantics of guards, it would
430  // actually be correct to just use SubsetIntersect, but that may be too
431  // aggressive in cases we care about.
432  auto SubsetIntersect = CR0.inverse().unionWith(CR1.inverse()).inverse();
433  auto SupersetIntersect = CR0.intersectWith(CR1);
434 
435  APInt NewRHSAP;
436  CmpInst::Predicate Pred;
437  if (SubsetIntersect == SupersetIntersect &&
438  SubsetIntersect.getEquivalentICmp(Pred, NewRHSAP)) {
439  if (InsertPt) {
440  ConstantInt *NewRHS = ConstantInt::get(Cond0->getContext(), NewRHSAP);
441  Result = new ICmpInst(InsertPt, Pred, LHS, NewRHS, "wide.chk");
442  }
443  return true;
444  }
445  }
446  }
447 
448  {
449  SmallVector<GuardWideningImpl::RangeCheck, 4> Checks, CombinedChecks;
450  if (parseRangeChecks(Cond0, Checks) && parseRangeChecks(Cond1, Checks) &&
451  combineRangeChecks(Checks, CombinedChecks)) {
452  if (InsertPt) {
453  Result = nullptr;
454  for (auto &RC : CombinedChecks) {
455  makeAvailableAt(RC.getCheckInst(), InsertPt);
456  if (Result)
457  Result = BinaryOperator::CreateAnd(RC.getCheckInst(), Result, "",
458  InsertPt);
459  else
460  Result = RC.getCheckInst();
461  }
462 
463  Result->setName("wide.chk");
464  }
465  return true;
466  }
467  }
468 
469  // Base case -- just logical-and the two conditions together.
470 
471  if (InsertPt) {
472  makeAvailableAt(Cond0, InsertPt);
473  makeAvailableAt(Cond1, InsertPt);
474 
475  Result = BinaryOperator::CreateAnd(Cond0, Cond1, "wide.chk", InsertPt);
476  }
477 
478  // We were not able to compute Cond0 AND Cond1 for the price of one.
479  return false;
480 }
481 
482 bool GuardWideningImpl::parseRangeChecks(
484  SmallPtrSetImpl<Value *> &Visited) {
485  if (!Visited.insert(CheckCond).second)
486  return true;
487 
488  using namespace llvm::PatternMatch;
489 
490  {
491  Value *AndLHS, *AndRHS;
492  if (match(CheckCond, m_And(m_Value(AndLHS), m_Value(AndRHS))))
493  return parseRangeChecks(AndLHS, Checks) &&
494  parseRangeChecks(AndRHS, Checks);
495  }
496 
497  auto *IC = dyn_cast<ICmpInst>(CheckCond);
498  if (!IC || !IC->getOperand(0)->getType()->isIntegerTy() ||
499  (IC->getPredicate() != ICmpInst::ICMP_ULT &&
500  IC->getPredicate() != ICmpInst::ICMP_UGT))
501  return false;
502 
503  Value *CmpLHS = IC->getOperand(0), *CmpRHS = IC->getOperand(1);
504  if (IC->getPredicate() == ICmpInst::ICMP_UGT)
505  std::swap(CmpLHS, CmpRHS);
506 
507  auto &DL = IC->getModule()->getDataLayout();
508 
509  GuardWideningImpl::RangeCheck Check(
510  CmpLHS, cast<ConstantInt>(ConstantInt::getNullValue(CmpRHS->getType())),
511  CmpRHS, IC);
512 
513  if (!isKnownNonNegative(Check.getLength(), DL))
514  return false;
515 
516  // What we have in \c Check now is a correct interpretation of \p CheckCond.
517  // Try to see if we can move some constant offsets into the \c Offset field.
518 
519  bool Changed;
520  auto &Ctx = CheckCond->getContext();
521 
522  do {
523  Value *OpLHS;
524  ConstantInt *OpRHS;
525  Changed = false;
526 
527 #ifndef NDEBUG
528  auto *BaseInst = dyn_cast<Instruction>(Check.getBase());
529  assert((!BaseInst || DT.isReachableFromEntry(BaseInst->getParent())) &&
530  "Unreachable instruction?");
531 #endif
532 
533  if (match(Check.getBase(), m_Add(m_Value(OpLHS), m_ConstantInt(OpRHS)))) {
534  Check.setBase(OpLHS);
535  APInt NewOffset = Check.getOffsetValue() + OpRHS->getValue();
536  Check.setOffset(ConstantInt::get(Ctx, NewOffset));
537  Changed = true;
538  } else if (match(Check.getBase(),
539  m_Or(m_Value(OpLHS), m_ConstantInt(OpRHS)))) {
540  KnownBits Known = computeKnownBits(OpLHS, DL);
541  if ((OpRHS->getValue() & Known.Zero) == OpRHS->getValue()) {
542  Check.setBase(OpLHS);
543  APInt NewOffset = Check.getOffsetValue() + OpRHS->getValue();
544  Check.setOffset(ConstantInt::get(Ctx, NewOffset));
545  Changed = true;
546  }
547  }
548  } while (Changed);
549 
550  Checks.push_back(Check);
551  return true;
552 }
553 
554 bool GuardWideningImpl::combineRangeChecks(
557  unsigned OldCount = Checks.size();
558  while (!Checks.empty()) {
559  // Pick all of the range checks with a specific base and length, and try to
560  // merge them.
561  Value *CurrentBase = Checks.front().getBase();
562  Value *CurrentLength = Checks.front().getLength();
563 
565 
566  auto IsCurrentCheck = [&](GuardWideningImpl::RangeCheck &RC) {
567  return RC.getBase() == CurrentBase && RC.getLength() == CurrentLength;
568  };
569 
570  copy_if(Checks, std::back_inserter(CurrentChecks), IsCurrentCheck);
571  Checks.erase(remove_if(Checks, IsCurrentCheck), Checks.end());
572 
573  assert(CurrentChecks.size() != 0 && "We know we have at least one!");
574 
575  if (CurrentChecks.size() < 3) {
576  RangeChecksOut.insert(RangeChecksOut.end(), CurrentChecks.begin(),
577  CurrentChecks.end());
578  continue;
579  }
580 
581  // CurrentChecks.size() will typically be 3 here, but so far there has been
582  // no need to hard-code that fact.
583 
584  std::sort(CurrentChecks.begin(), CurrentChecks.end(),
585  [&](const GuardWideningImpl::RangeCheck &LHS,
586  const GuardWideningImpl::RangeCheck &RHS) {
587  return LHS.getOffsetValue().slt(RHS.getOffsetValue());
588  });
589 
590  // Note: std::sort should not invalidate the ChecksStart iterator.
591 
592  ConstantInt *MinOffset = CurrentChecks.front().getOffset(),
593  *MaxOffset = CurrentChecks.back().getOffset();
594 
595  unsigned BitWidth = MaxOffset->getValue().getBitWidth();
596  if ((MaxOffset->getValue() - MinOffset->getValue())
597  .ugt(APInt::getSignedMinValue(BitWidth)))
598  return false;
599 
600  APInt MaxDiff = MaxOffset->getValue() - MinOffset->getValue();
601  const APInt &HighOffset = MaxOffset->getValue();
602  auto OffsetOK = [&](const GuardWideningImpl::RangeCheck &RC) {
603  return (HighOffset - RC.getOffsetValue()).ult(MaxDiff);
604  };
605 
606  if (MaxDiff.isMinValue() ||
607  !std::all_of(std::next(CurrentChecks.begin()), CurrentChecks.end(),
608  OffsetOK))
609  return false;
610 
611  // We have a series of f+1 checks as:
612  //
613  // I+k_0 u< L ... Chk_0
614  // I+k_1 u< L ... Chk_1
615  // ...
616  // I+k_f u< L ... Chk_f
617  //
618  // with forall i in [0,f]: k_f-k_i u< k_f-k_0 ... Precond_0
619  // k_f-k_0 u< INT_MIN+k_f ... Precond_1
620  // k_f != k_0 ... Precond_2
621  //
622  // Claim:
623  // Chk_0 AND Chk_f implies all the other checks
624  //
625  // Informal proof sketch:
626  //
627  // We will show that the integer range [I+k_0,I+k_f] does not unsigned-wrap
628  // (i.e. going from I+k_0 to I+k_f does not cross the -1,0 boundary) and
629  // thus I+k_f is the greatest unsigned value in that range.
630  //
631  // This combined with Ckh_(f+1) shows that everything in that range is u< L.
632  // Via Precond_0 we know that all of the indices in Chk_0 through Chk_(f+1)
633  // lie in [I+k_0,I+k_f], this proving our claim.
634  //
635  // To see that [I+k_0,I+k_f] is not a wrapping range, note that there are
636  // two possibilities: I+k_0 u< I+k_f or I+k_0 >u I+k_f (they can't be equal
637  // since k_0 != k_f). In the former case, [I+k_0,I+k_f] is not a wrapping
638  // range by definition, and the latter case is impossible:
639  //
640  // 0-----I+k_f---I+k_0----L---INT_MAX,INT_MIN------------------(-1)
641  // xxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
642  //
643  // For Chk_0 to succeed, we'd have to have k_f-k_0 (the range highlighted
644  // with 'x' above) to be at least >u INT_MIN.
645 
646  RangeChecksOut.emplace_back(CurrentChecks.front());
647  RangeChecksOut.emplace_back(CurrentChecks.back());
648  }
649 
650  assert(RangeChecksOut.size() <= OldCount && "We pessimized!");
651  return RangeChecksOut.size() != OldCount;
652 }
653 
656  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
657  auto &LI = AM.getResult<LoopAnalysis>(F);
658  auto &PDT = AM.getResult<PostDominatorTreeAnalysis>(F);
659  if (!GuardWideningImpl(DT, PDT, LI).run())
660  return PreservedAnalyses::all();
661 
663  PA.preserveSet<CFGAnalyses>();
664  return PA;
665 }
666 
667 #ifndef NDEBUG
668 StringRef GuardWideningImpl::scoreTypeToString(WideningScore WS) {
669  switch (WS) {
670  case WS_IllegalOrNegative:
671  return "IllegalOrNegative";
672  case WS_Neutral:
673  return "Neutral";
674  case WS_Positive:
675  return "Positive";
676  case WS_VeryPositive:
677  return "VeryPositive";
678  }
679 
680  llvm_unreachable("Fully covered switch above!");
681 }
682 #endif
683 
685 
686 INITIALIZE_PASS_BEGIN(GuardWideningLegacyPass, "guard-widening", "Widen guards",
687  false, false)
691 INITIALIZE_PASS_END(GuardWideningLegacyPass, "guard-widening", "Widen guards",
692  false, false)
693 
695  return new GuardWideningLegacyPass();
696 }
static bool Check(DecodeStatus &Out, DecodeStatus In)
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
Definition: PatternMatch.h:574
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:72
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
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds...
Definition: Compiler.h:449
LLVM_ATTRIBUTE_ALWAYS_INLINE size_type size() const
Definition: SmallVector.h:136
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:814
auto remove_if(R &&Range, UnaryPredicate P) -> decltype(std::begin(Range))
Provide wrappers to std::remove_if which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:807
Implements a dense probed hash-table based set.
Definition: DenseSet.h:221
void initializeGuardWideningLegacyPassPass(PassRegistry &)
unsigned less than
Definition: InstrTypes.h:878
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:728
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:767
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:238
F(f)
static Constant * getNullValue(Type *Ty)
Constructor to create a &#39;0&#39; constant of arbitrary type.
Definition: Constants.cpp:207
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:286
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:933
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
Definition: PatternMatch.h:502
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:140
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:580
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:116
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:382
Represent the analysis usage information of a pass.
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:853
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
iterator erase(const_iterator CI)
Definition: SmallVector.h:449
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:159
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:3573
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)
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:110
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
auto find(R &&Range, const T &Val) -> decltype(std::begin(Range))
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:788
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:864
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:560
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:285
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:516
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:923
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:482
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator end()
Definition: SmallVector.h:120
guard widening
void emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:656
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:61
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:439
void preserveSet()
Mark an analysis set as preserved.
Definition: PassManager.h:189
Value * getArgOperand(unsigned i) const
getArgOperand/setArgOperand - Return/set the i-th call argument.
#define I(x, y, z)
Definition: MD5.cpp:58
void setArgOperand(unsigned i, Value *v)
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:430
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:538
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
FunctionPass * createGuardWideningPass()
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:44
#define DEBUG(X)
Definition: Debug.h:118
The legacy pass manager&#39;s analysis pass to compute loop information.
Definition: LoopInfo.h:958
unsigned greater than
Definition: InstrTypes.h:876
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:267
void sort(Policy policy, RandomAccessIterator Start, RandomAccessIterator End, const Comparator &Comp=Comparator())
Definition: Parallel.h:199
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:66
CmpClass_match< LHS, RHS, ICmpInst, ICmpInst::Predicate > m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R)
Definition: PatternMatch.h:837