LLVM  15.0.0git
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 "llvm/ADT/DenseMap.h"
44 #include "llvm/ADT/Statistic.h"
46 #include "llvm/Analysis/LoopInfo.h"
47 #include "llvm/Analysis/LoopPass.h"
51 #include "llvm/IR/ConstantRange.h"
52 #include "llvm/IR/Dominators.h"
53 #include "llvm/IR/IntrinsicInst.h"
54 #include "llvm/IR/PatternMatch.h"
55 #include "llvm/InitializePasses.h"
56 #include "llvm/Pass.h"
58 #include "llvm/Support/Debug.h"
59 #include "llvm/Support/KnownBits.h"
60 #include "llvm/Transforms/Scalar.h"
63 #include <functional>
64 
65 using namespace llvm;
66 
67 #define DEBUG_TYPE "guard-widening"
68 
69 STATISTIC(GuardsEliminated, "Number of eliminated guards");
70 STATISTIC(CondBranchEliminated, "Number of eliminated conditional branches");
71 
72 static cl::opt<bool>
73  WidenBranchGuards("guard-widening-widen-branch-guards", cl::Hidden,
74  cl::desc("Whether or not we should widen guards "
75  "expressed as branches by widenable conditions"),
76  cl::init(true));
77 
78 namespace {
79 
80 // Get the condition of \p I. It can either be a guard or a conditional branch.
81 static Value *getCondition(Instruction *I) {
82  if (IntrinsicInst *GI = dyn_cast<IntrinsicInst>(I)) {
83  assert(GI->getIntrinsicID() == Intrinsic::experimental_guard &&
84  "Bad guard intrinsic?");
85  return GI->getArgOperand(0);
86  }
87  Value *Cond, *WC;
88  BasicBlock *IfTrueBB, *IfFalseBB;
89  if (parseWidenableBranch(I, Cond, WC, IfTrueBB, IfFalseBB))
90  return Cond;
91 
92  return cast<BranchInst>(I)->getCondition();
93 }
94 
95 // Set the condition for \p I to \p NewCond. \p I can either be a guard or a
96 // conditional branch.
97 static void setCondition(Instruction *I, Value *NewCond) {
98  if (IntrinsicInst *GI = dyn_cast<IntrinsicInst>(I)) {
99  assert(GI->getIntrinsicID() == Intrinsic::experimental_guard &&
100  "Bad guard intrinsic?");
101  GI->setArgOperand(0, NewCond);
102  return;
103  }
104  cast<BranchInst>(I)->setCondition(NewCond);
105 }
106 
107 // Eliminates the guard instruction properly.
108 static void eliminateGuard(Instruction *GuardInst, MemorySSAUpdater *MSSAU) {
109  GuardInst->eraseFromParent();
110  if (MSSAU)
111  MSSAU->removeMemoryAccess(GuardInst);
112  ++GuardsEliminated;
113 }
114 
115 class GuardWideningImpl {
116  DominatorTree &DT;
117  PostDominatorTree *PDT;
118  LoopInfo &LI;
119  MemorySSAUpdater *MSSAU;
120 
121  /// Together, these describe the region of interest. This might be all of
122  /// the blocks within a function, or only a given loop's blocks and preheader.
123  DomTreeNode *Root;
124  std::function<bool(BasicBlock*)> BlockFilter;
125 
126  /// The set of guards and conditional branches whose conditions have been
127  /// widened into dominating guards.
128  SmallVector<Instruction *, 16> EliminatedGuardsAndBranches;
129 
130  /// The set of guards which have been widened to include conditions to other
131  /// guards.
132  DenseSet<Instruction *> WidenedGuards;
133 
134  /// Try to eliminate instruction \p Instr by widening it into an earlier
135  /// dominating guard. \p DFSI is the DFS iterator on the dominator tree that
136  /// is currently visiting the block containing \p Guard, and \p GuardsPerBlock
137  /// maps BasicBlocks to the set of guards seen in that block.
138  bool eliminateInstrViaWidening(
139  Instruction *Instr, const df_iterator<DomTreeNode *> &DFSI,
141  GuardsPerBlock, bool InvertCondition = false);
142 
143  /// Used to keep track of which widening potential is more effective.
144  enum WideningScore {
145  /// Don't widen.
146  WS_IllegalOrNegative,
147 
148  /// Widening is performance neutral as far as the cycles spent in check
149  /// conditions goes (but can still help, e.g., code layout, having less
150  /// deopt state).
151  WS_Neutral,
152 
153  /// Widening is profitable.
154  WS_Positive,
155 
156  /// Widening is very profitable. Not significantly different from \c
157  /// WS_Positive, except by the order.
158  WS_VeryPositive
159  };
160 
161  static StringRef scoreTypeToString(WideningScore WS);
162 
163  /// Compute the score for widening the condition in \p DominatedInstr
164  /// into \p DominatingGuard. If \p InvertCond is set, then we widen the
165  /// inverted condition of the dominating guard.
166  WideningScore computeWideningScore(Instruction *DominatedInstr,
167  Instruction *DominatingGuard,
168  bool InvertCond);
169 
170  /// Helper to check if \p V can be hoisted to \p InsertPos.
171  bool isAvailableAt(const Value *V, const Instruction *InsertPos) const {
173  return isAvailableAt(V, InsertPos, Visited);
174  }
175 
176  bool isAvailableAt(const Value *V, const Instruction *InsertPos,
177  SmallPtrSetImpl<const Instruction *> &Visited) const;
178 
179  /// Helper to hoist \p V to \p InsertPos. Guaranteed to succeed if \c
180  /// isAvailableAt returned true.
181  void makeAvailableAt(Value *V, Instruction *InsertPos) const;
182 
183  /// Common helper used by \c widenGuard and \c isWideningCondProfitable. Try
184  /// to generate an expression computing the logical AND of \p Cond0 and (\p
185  /// Cond1 XOR \p InvertCondition).
186  /// Return true if the expression computing the AND is only as
187  /// expensive as computing one of the two. If \p InsertPt is true then
188  /// actually generate the resulting expression, make it available at \p
189  /// InsertPt and return it in \p Result (else no change to the IR is made).
190  bool widenCondCommon(Value *Cond0, Value *Cond1, Instruction *InsertPt,
191  Value *&Result, bool InvertCondition);
192 
193  /// Represents a range check of the form \c Base + \c Offset u< \c Length,
194  /// with the constraint that \c Length is not negative. \c CheckInst is the
195  /// pre-existing instruction in the IR that computes the result of this range
196  /// check.
197  class RangeCheck {
198  const Value *Base;
199  const ConstantInt *Offset;
200  const Value *Length;
201  ICmpInst *CheckInst;
202 
203  public:
204  explicit RangeCheck(const Value *Base, const ConstantInt *Offset,
205  const Value *Length, ICmpInst *CheckInst)
206  : Base(Base), Offset(Offset), Length(Length), CheckInst(CheckInst) {}
207 
208  void setBase(const Value *NewBase) { Base = NewBase; }
209  void setOffset(const ConstantInt *NewOffset) { Offset = NewOffset; }
210 
211  const Value *getBase() const { return Base; }
212  const ConstantInt *getOffset() const { return Offset; }
213  const APInt &getOffsetValue() const { return getOffset()->getValue(); }
214  const Value *getLength() const { return Length; };
215  ICmpInst *getCheckInst() const { return CheckInst; }
216 
217  void print(raw_ostream &OS, bool PrintTypes = false) {
218  OS << "Base: ";
219  Base->printAsOperand(OS, PrintTypes);
220  OS << " Offset: ";
221  Offset->printAsOperand(OS, PrintTypes);
222  OS << " Length: ";
223  Length->printAsOperand(OS, PrintTypes);
224  }
225 
226  LLVM_DUMP_METHOD void dump() {
227  print(dbgs());
228  dbgs() << "\n";
229  }
230  };
231 
232  /// Parse \p CheckCond into a conjunction (logical-and) of range checks; and
233  /// append them to \p Checks. Returns true on success, may clobber \c Checks
234  /// on failure.
235  bool parseRangeChecks(Value *CheckCond, SmallVectorImpl<RangeCheck> &Checks) {
237  return parseRangeChecks(CheckCond, Checks, Visited);
238  }
239 
240  bool parseRangeChecks(Value *CheckCond, SmallVectorImpl<RangeCheck> &Checks,
242 
243  /// Combine the checks in \p Checks into a smaller set of checks and append
244  /// them into \p CombinedChecks. Return true on success (i.e. all of checks
245  /// in \p Checks were combined into \p CombinedChecks). Clobbers \p Checks
246  /// and \p CombinedChecks on success and on failure.
247  bool combineRangeChecks(SmallVectorImpl<RangeCheck> &Checks,
248  SmallVectorImpl<RangeCheck> &CombinedChecks) const;
249 
250  /// Can we compute the logical AND of \p Cond0 and \p Cond1 for the price of
251  /// computing only one of the two expressions?
252  bool isWideningCondProfitable(Value *Cond0, Value *Cond1, bool InvertCond) {
253  Value *ResultUnused;
254  return widenCondCommon(Cond0, Cond1, /*InsertPt=*/nullptr, ResultUnused,
255  InvertCond);
256  }
257 
258  /// If \p InvertCondition is false, Widen \p ToWiden to fail if
259  /// \p NewCondition is false, otherwise make it fail if \p NewCondition is
260  /// true (in addition to whatever it is already checking).
261  void widenGuard(Instruction *ToWiden, Value *NewCondition,
262  bool InvertCondition) {
263  Value *Result;
264 
265  widenCondCommon(getCondition(ToWiden), NewCondition, ToWiden, Result,
266  InvertCondition);
267  if (isGuardAsWidenableBranch(ToWiden)) {
268  setWidenableBranchCond(cast<BranchInst>(ToWiden), Result);
269  return;
270  }
271  setCondition(ToWiden, Result);
272  }
273 
274 public:
275  explicit GuardWideningImpl(DominatorTree &DT, PostDominatorTree *PDT,
276  LoopInfo &LI, MemorySSAUpdater *MSSAU,
277  DomTreeNode *Root,
278  std::function<bool(BasicBlock*)> BlockFilter)
279  : DT(DT), PDT(PDT), LI(LI), MSSAU(MSSAU), Root(Root),
280  BlockFilter(BlockFilter) {}
281 
282  /// The entry point for this pass.
283  bool run();
284 };
285 }
286 
288  if (isGuard(Insn))
289  return true;
291  return true;
292  return false;
293 }
294 
295 bool GuardWideningImpl::run() {
297  bool Changed = false;
298  for (auto DFI = df_begin(Root), DFE = df_end(Root);
299  DFI != DFE; ++DFI) {
300  auto *BB = (*DFI)->getBlock();
301  if (!BlockFilter(BB))
302  continue;
303 
304  auto &CurrentList = GuardsInBlock[BB];
305 
306  for (auto &I : *BB)
308  CurrentList.push_back(cast<Instruction>(&I));
309 
310  for (auto *II : CurrentList)
311  Changed |= eliminateInstrViaWidening(II, DFI, GuardsInBlock);
312  }
313 
314  assert(EliminatedGuardsAndBranches.empty() || Changed);
315  for (auto *I : EliminatedGuardsAndBranches)
316  if (!WidenedGuards.count(I)) {
317  assert(isa<ConstantInt>(getCondition(I)) && "Should be!");
319  eliminateGuard(I, MSSAU);
320  else {
321  assert(isa<BranchInst>(I) &&
322  "Eliminated something other than guard or branch?");
323  ++CondBranchEliminated;
324  }
325  }
326 
327  return Changed;
328 }
329 
330 bool GuardWideningImpl::eliminateInstrViaWidening(
331  Instruction *Instr, const df_iterator<DomTreeNode *> &DFSI,
333  GuardsInBlock, bool InvertCondition) {
334  // Ignore trivial true or false conditions. These instructions will be
335  // trivially eliminated by any cleanup pass. Do not erase them because other
336  // guards can possibly be widened into them.
337  if (isa<ConstantInt>(getCondition(Instr)))
338  return false;
339 
340  Instruction *BestSoFar = nullptr;
341  auto BestScoreSoFar = WS_IllegalOrNegative;
342 
343  // In the set of dominating guards, find the one we can merge GuardInst with
344  // for the most profit.
345  for (unsigned i = 0, e = DFSI.getPathLength(); i != e; ++i) {
346  auto *CurBB = DFSI.getPath(i)->getBlock();
347  if (!BlockFilter(CurBB))
348  break;
349  assert(GuardsInBlock.count(CurBB) && "Must have been populated by now!");
350  const auto &GuardsInCurBB = GuardsInBlock.find(CurBB)->second;
351 
352  auto I = GuardsInCurBB.begin();
353  auto E = Instr->getParent() == CurBB ? find(GuardsInCurBB, Instr)
354  : GuardsInCurBB.end();
355 
356 #ifndef NDEBUG
357  {
358  unsigned Index = 0;
359  for (auto &I : *CurBB) {
360  if (Index == GuardsInCurBB.size())
361  break;
362  if (GuardsInCurBB[Index] == &I)
363  Index++;
364  }
365  assert(Index == GuardsInCurBB.size() &&
366  "Guards expected to be in order!");
367  }
368 #endif
369 
370  assert((i == (e - 1)) == (Instr->getParent() == CurBB) && "Bad DFS?");
371 
372  for (auto *Candidate : make_range(I, E)) {
373  auto Score = computeWideningScore(Instr, Candidate, InvertCondition);
374  LLVM_DEBUG(dbgs() << "Score between " << *getCondition(Instr)
375  << " and " << *getCondition(Candidate) << " is "
376  << scoreTypeToString(Score) << "\n");
377  if (Score > BestScoreSoFar) {
378  BestScoreSoFar = Score;
379  BestSoFar = Candidate;
380  }
381  }
382  }
383 
384  if (BestScoreSoFar == WS_IllegalOrNegative) {
385  LLVM_DEBUG(dbgs() << "Did not eliminate guard " << *Instr << "\n");
386  return false;
387  }
388 
389  assert(BestSoFar != Instr && "Should have never visited same guard!");
390  assert(DT.dominates(BestSoFar, Instr) && "Should be!");
391 
392  LLVM_DEBUG(dbgs() << "Widening " << *Instr << " into " << *BestSoFar
393  << " with score " << scoreTypeToString(BestScoreSoFar)
394  << "\n");
395  widenGuard(BestSoFar, getCondition(Instr), InvertCondition);
396  auto NewGuardCondition = InvertCondition
398  : ConstantInt::getTrue(Instr->getContext());
399  setCondition(Instr, NewGuardCondition);
400  EliminatedGuardsAndBranches.push_back(Instr);
401  WidenedGuards.insert(BestSoFar);
402  return true;
403 }
404 
405 GuardWideningImpl::WideningScore
406 GuardWideningImpl::computeWideningScore(Instruction *DominatedInstr,
407  Instruction *DominatingGuard,
408  bool InvertCond) {
409  Loop *DominatedInstrLoop = LI.getLoopFor(DominatedInstr->getParent());
410  Loop *DominatingGuardLoop = LI.getLoopFor(DominatingGuard->getParent());
411  bool HoistingOutOfLoop = false;
412 
413  if (DominatingGuardLoop != DominatedInstrLoop) {
414  // Be conservative and don't widen into a sibling loop. TODO: If the
415  // sibling is colder, we should consider allowing this.
416  if (DominatingGuardLoop &&
417  !DominatingGuardLoop->contains(DominatedInstrLoop))
418  return WS_IllegalOrNegative;
419 
420  HoistingOutOfLoop = true;
421  }
422 
423  if (!isAvailableAt(getCondition(DominatedInstr), DominatingGuard))
424  return WS_IllegalOrNegative;
425 
426  // If the guard was conditional executed, it may never be reached
427  // dynamically. There are two potential downsides to hoisting it out of the
428  // conditionally executed region: 1) we may spuriously deopt without need and
429  // 2) we have the extra cost of computing the guard condition in the common
430  // case. At the moment, we really only consider the second in our heuristic
431  // here. TODO: evaluate cost model for spurious deopt
432  // NOTE: As written, this also lets us hoist right over another guard which
433  // is essentially just another spelling for control flow.
434  if (isWideningCondProfitable(getCondition(DominatedInstr),
435  getCondition(DominatingGuard), InvertCond))
436  return HoistingOutOfLoop ? WS_VeryPositive : WS_Positive;
437 
438  if (HoistingOutOfLoop)
439  return WS_Positive;
440 
441  // Returns true if we might be hoisting above explicit control flow. Note
442  // that this completely ignores implicit control flow (guards, calls which
443  // throw, etc...). That choice appears arbitrary.
444  auto MaybeHoistingOutOfIf = [&]() {
445  auto *DominatingBlock = DominatingGuard->getParent();
446  auto *DominatedBlock = DominatedInstr->getParent();
447  if (isGuardAsWidenableBranch(DominatingGuard))
448  DominatingBlock = cast<BranchInst>(DominatingGuard)->getSuccessor(0);
449 
450  // Same Block?
451  if (DominatedBlock == DominatingBlock)
452  return false;
453  // Obvious successor (common loop header/preheader case)
454  if (DominatedBlock == DominatingBlock->getUniqueSuccessor())
455  return false;
456  // TODO: diamond, triangle cases
457  if (!PDT) return true;
458  return !PDT->dominates(DominatedBlock, DominatingBlock);
459  };
460 
461  return MaybeHoistingOutOfIf() ? WS_IllegalOrNegative : WS_Neutral;
462 }
463 
464 bool GuardWideningImpl::isAvailableAt(
465  const Value *V, const Instruction *Loc,
466  SmallPtrSetImpl<const Instruction *> &Visited) const {
467  auto *Inst = dyn_cast<Instruction>(V);
468  if (!Inst || DT.dominates(Inst, Loc) || Visited.count(Inst))
469  return true;
470 
471  if (!isSafeToSpeculativelyExecute(Inst, Loc, &DT) ||
472  Inst->mayReadFromMemory())
473  return false;
474 
475  Visited.insert(Inst);
476 
477  // We only want to go _up_ the dominance chain when recursing.
478  assert(!isa<PHINode>(Loc) &&
479  "PHIs should return false for isSafeToSpeculativelyExecute");
480  assert(DT.isReachableFromEntry(Inst->getParent()) &&
481  "We did a DFS from the block entry!");
482  return all_of(Inst->operands(),
483  [&](Value *Op) { return isAvailableAt(Op, Loc, Visited); });
484 }
485 
486 void GuardWideningImpl::makeAvailableAt(Value *V, Instruction *Loc) const {
487  auto *Inst = dyn_cast<Instruction>(V);
488  if (!Inst || DT.dominates(Inst, Loc))
489  return;
490 
491  assert(isSafeToSpeculativelyExecute(Inst, Loc, &DT) &&
492  !Inst->mayReadFromMemory() && "Should've checked with isAvailableAt!");
493 
494  for (Value *Op : Inst->operands())
495  makeAvailableAt(Op, Loc);
496 
497  Inst->moveBefore(Loc);
498  // If we moved instruction before guard we must clean poison generating flags.
499  Inst->dropPoisonGeneratingFlags();
500 }
501 
502 bool GuardWideningImpl::widenCondCommon(Value *Cond0, Value *Cond1,
503  Instruction *InsertPt, Value *&Result,
504  bool InvertCondition) {
505  using namespace llvm::PatternMatch;
506 
507  {
508  // L >u C0 && L >u C1 -> L >u max(C0, C1)
509  ConstantInt *RHS0, *RHS1;
510  Value *LHS;
511  ICmpInst::Predicate Pred0, Pred1;
512  if (match(Cond0, m_ICmp(Pred0, m_Value(LHS), m_ConstantInt(RHS0))) &&
513  match(Cond1, m_ICmp(Pred1, m_Specific(LHS), m_ConstantInt(RHS1)))) {
514  if (InvertCondition)
515  Pred1 = ICmpInst::getInversePredicate(Pred1);
516 
517  ConstantRange CR0 =
519  ConstantRange CR1 =
521 
522  // Given what we're doing here and the semantics of guards, it would
523  // be correct to use a subset intersection, but that may be too
524  // aggressive in cases we care about.
525  if (Optional<ConstantRange> Intersect = CR0.exactIntersectWith(CR1)) {
526  APInt NewRHSAP;
527  CmpInst::Predicate Pred;
528  if (Intersect->getEquivalentICmp(Pred, NewRHSAP)) {
529  if (InsertPt) {
530  ConstantInt *NewRHS =
531  ConstantInt::get(Cond0->getContext(), NewRHSAP);
532  Result = new ICmpInst(InsertPt, Pred, LHS, NewRHS, "wide.chk");
533  }
534  return true;
535  }
536  }
537  }
538  }
539 
540  {
541  SmallVector<GuardWideningImpl::RangeCheck, 4> Checks, CombinedChecks;
542  // TODO: Support InvertCondition case?
543  if (!InvertCondition &&
544  parseRangeChecks(Cond0, Checks) && parseRangeChecks(Cond1, Checks) &&
545  combineRangeChecks(Checks, CombinedChecks)) {
546  if (InsertPt) {
547  Result = nullptr;
548  for (auto &RC : CombinedChecks) {
549  makeAvailableAt(RC.getCheckInst(), InsertPt);
550  if (Result)
551  Result = BinaryOperator::CreateAnd(RC.getCheckInst(), Result, "",
552  InsertPt);
553  else
554  Result = RC.getCheckInst();
555  }
556  assert(Result && "Failed to find result value");
557  Result->setName("wide.chk");
558  }
559  return true;
560  }
561  }
562 
563  // Base case -- just logical-and the two conditions together.
564 
565  if (InsertPt) {
566  makeAvailableAt(Cond0, InsertPt);
567  makeAvailableAt(Cond1, InsertPt);
568  if (InvertCondition)
569  Cond1 = BinaryOperator::CreateNot(Cond1, "inverted", InsertPt);
570  Result = BinaryOperator::CreateAnd(Cond0, Cond1, "wide.chk", InsertPt);
571  }
572 
573  // We were not able to compute Cond0 AND Cond1 for the price of one.
574  return false;
575 }
576 
577 bool GuardWideningImpl::parseRangeChecks(
580  if (!Visited.insert(CheckCond).second)
581  return true;
582 
583  using namespace llvm::PatternMatch;
584 
585  {
586  Value *AndLHS, *AndRHS;
587  if (match(CheckCond, m_And(m_Value(AndLHS), m_Value(AndRHS))))
588  return parseRangeChecks(AndLHS, Checks) &&
589  parseRangeChecks(AndRHS, Checks);
590  }
591 
592  auto *IC = dyn_cast<ICmpInst>(CheckCond);
593  if (!IC || !IC->getOperand(0)->getType()->isIntegerTy() ||
594  (IC->getPredicate() != ICmpInst::ICMP_ULT &&
595  IC->getPredicate() != ICmpInst::ICMP_UGT))
596  return false;
597 
598  const Value *CmpLHS = IC->getOperand(0), *CmpRHS = IC->getOperand(1);
599  if (IC->getPredicate() == ICmpInst::ICMP_UGT)
600  std::swap(CmpLHS, CmpRHS);
601 
602  auto &DL = IC->getModule()->getDataLayout();
603 
604  GuardWideningImpl::RangeCheck Check(
605  CmpLHS, cast<ConstantInt>(ConstantInt::getNullValue(CmpRHS->getType())),
606  CmpRHS, IC);
607 
608  if (!isKnownNonNegative(Check.getLength(), DL))
609  return false;
610 
611  // What we have in \c Check now is a correct interpretation of \p CheckCond.
612  // Try to see if we can move some constant offsets into the \c Offset field.
613 
614  bool Changed;
615  auto &Ctx = CheckCond->getContext();
616 
617  do {
618  Value *OpLHS;
619  ConstantInt *OpRHS;
620  Changed = false;
621 
622 #ifndef NDEBUG
623  auto *BaseInst = dyn_cast<Instruction>(Check.getBase());
624  assert((!BaseInst || DT.isReachableFromEntry(BaseInst->getParent())) &&
625  "Unreachable instruction?");
626 #endif
627 
628  if (match(Check.getBase(), m_Add(m_Value(OpLHS), m_ConstantInt(OpRHS)))) {
629  Check.setBase(OpLHS);
630  APInt NewOffset = Check.getOffsetValue() + OpRHS->getValue();
631  Check.setOffset(ConstantInt::get(Ctx, NewOffset));
632  Changed = true;
633  } else if (match(Check.getBase(),
634  m_Or(m_Value(OpLHS), m_ConstantInt(OpRHS)))) {
635  KnownBits Known = computeKnownBits(OpLHS, DL);
636  if ((OpRHS->getValue() & Known.Zero) == OpRHS->getValue()) {
637  Check.setBase(OpLHS);
638  APInt NewOffset = Check.getOffsetValue() + OpRHS->getValue();
639  Check.setOffset(ConstantInt::get(Ctx, NewOffset));
640  Changed = true;
641  }
642  }
643  } while (Changed);
644 
645  Checks.push_back(Check);
646  return true;
647 }
648 
649 bool GuardWideningImpl::combineRangeChecks(
651  SmallVectorImpl<GuardWideningImpl::RangeCheck> &RangeChecksOut) const {
652  unsigned OldCount = Checks.size();
653  while (!Checks.empty()) {
654  // Pick all of the range checks with a specific base and length, and try to
655  // merge them.
656  const Value *CurrentBase = Checks.front().getBase();
657  const Value *CurrentLength = Checks.front().getLength();
658 
660 
661  auto IsCurrentCheck = [&](GuardWideningImpl::RangeCheck &RC) {
662  return RC.getBase() == CurrentBase && RC.getLength() == CurrentLength;
663  };
664 
665  copy_if(Checks, std::back_inserter(CurrentChecks), IsCurrentCheck);
666  erase_if(Checks, IsCurrentCheck);
667 
668  assert(CurrentChecks.size() != 0 && "We know we have at least one!");
669 
670  if (CurrentChecks.size() < 3) {
671  llvm::append_range(RangeChecksOut, CurrentChecks);
672  continue;
673  }
674 
675  // CurrentChecks.size() will typically be 3 here, but so far there has been
676  // no need to hard-code that fact.
677 
678  llvm::sort(CurrentChecks, [&](const GuardWideningImpl::RangeCheck &LHS,
679  const GuardWideningImpl::RangeCheck &RHS) {
680  return LHS.getOffsetValue().slt(RHS.getOffsetValue());
681  });
682 
683  // Note: std::sort should not invalidate the ChecksStart iterator.
684 
685  const ConstantInt *MinOffset = CurrentChecks.front().getOffset();
686  const ConstantInt *MaxOffset = CurrentChecks.back().getOffset();
687 
688  unsigned BitWidth = MaxOffset->getValue().getBitWidth();
689  if ((MaxOffset->getValue() - MinOffset->getValue())
691  return false;
692 
693  APInt MaxDiff = MaxOffset->getValue() - MinOffset->getValue();
694  const APInt &HighOffset = MaxOffset->getValue();
695  auto OffsetOK = [&](const GuardWideningImpl::RangeCheck &RC) {
696  return (HighOffset - RC.getOffsetValue()).ult(MaxDiff);
697  };
698 
699  if (MaxDiff.isMinValue() || !all_of(drop_begin(CurrentChecks), OffsetOK))
700  return false;
701 
702  // We have a series of f+1 checks as:
703  //
704  // I+k_0 u< L ... Chk_0
705  // I+k_1 u< L ... Chk_1
706  // ...
707  // I+k_f u< L ... Chk_f
708  //
709  // with forall i in [0,f]: k_f-k_i u< k_f-k_0 ... Precond_0
710  // k_f-k_0 u< INT_MIN+k_f ... Precond_1
711  // k_f != k_0 ... Precond_2
712  //
713  // Claim:
714  // Chk_0 AND Chk_f implies all the other checks
715  //
716  // Informal proof sketch:
717  //
718  // We will show that the integer range [I+k_0,I+k_f] does not unsigned-wrap
719  // (i.e. going from I+k_0 to I+k_f does not cross the -1,0 boundary) and
720  // thus I+k_f is the greatest unsigned value in that range.
721  //
722  // This combined with Ckh_(f+1) shows that everything in that range is u< L.
723  // Via Precond_0 we know that all of the indices in Chk_0 through Chk_(f+1)
724  // lie in [I+k_0,I+k_f], this proving our claim.
725  //
726  // To see that [I+k_0,I+k_f] is not a wrapping range, note that there are
727  // two possibilities: I+k_0 u< I+k_f or I+k_0 >u I+k_f (they can't be equal
728  // since k_0 != k_f). In the former case, [I+k_0,I+k_f] is not a wrapping
729  // range by definition, and the latter case is impossible:
730  //
731  // 0-----I+k_f---I+k_0----L---INT_MAX,INT_MIN------------------(-1)
732  // xxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
733  //
734  // For Chk_0 to succeed, we'd have to have k_f-k_0 (the range highlighted
735  // with 'x' above) to be at least >u INT_MIN.
736 
737  RangeChecksOut.emplace_back(CurrentChecks.front());
738  RangeChecksOut.emplace_back(CurrentChecks.back());
739  }
740 
741  assert(RangeChecksOut.size() <= OldCount && "We pessimized!");
742  return RangeChecksOut.size() != OldCount;
743 }
744 
745 #ifndef NDEBUG
746 StringRef GuardWideningImpl::scoreTypeToString(WideningScore WS) {
747  switch (WS) {
748  case WS_IllegalOrNegative:
749  return "IllegalOrNegative";
750  case WS_Neutral:
751  return "Neutral";
752  case WS_Positive:
753  return "Positive";
754  case WS_VeryPositive:
755  return "VeryPositive";
756  }
757 
758  llvm_unreachable("Fully covered switch above!");
759 }
760 #endif
761 
764  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
765  auto &LI = AM.getResult<LoopAnalysis>(F);
766  auto &PDT = AM.getResult<PostDominatorTreeAnalysis>(F);
767  auto *MSSAA = AM.getCachedResult<MemorySSAAnalysis>(F);
768  std::unique_ptr<MemorySSAUpdater> MSSAU;
769  if (MSSAA)
770  MSSAU = std::make_unique<MemorySSAUpdater>(&MSSAA->getMSSA());
771  if (!GuardWideningImpl(DT, &PDT, LI, MSSAU ? MSSAU.get() : nullptr,
772  DT.getRootNode(), [](BasicBlock *) { return true; })
773  .run())
774  return PreservedAnalyses::all();
775 
777  PA.preserveSet<CFGAnalyses>();
779  return PA;
780 }
781 
784  LPMUpdater &U) {
785  BasicBlock *RootBB = L.getLoopPredecessor();
786  if (!RootBB)
787  RootBB = L.getHeader();
788  auto BlockFilter = [&](BasicBlock *BB) {
789  return BB == RootBB || L.contains(BB);
790  };
791  std::unique_ptr<MemorySSAUpdater> MSSAU;
792  if (AR.MSSA)
793  MSSAU = std::make_unique<MemorySSAUpdater>(AR.MSSA);
794  if (!GuardWideningImpl(AR.DT, nullptr, AR.LI, MSSAU ? MSSAU.get() : nullptr,
795  AR.DT.getNode(RootBB), BlockFilter).run())
796  return PreservedAnalyses::all();
797 
798  auto PA = getLoopPassPreservedAnalyses();
799  if (AR.MSSA)
800  PA.preserve<MemorySSAAnalysis>();
801  return PA;
802 }
803 
804 namespace {
805 struct GuardWideningLegacyPass : public FunctionPass {
806  static char ID;
807 
808  GuardWideningLegacyPass() : FunctionPass(ID) {
810  }
811 
812  bool runOnFunction(Function &F) override {
813  if (skipFunction(F))
814  return false;
815  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
816  auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
817  auto &PDT = getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();
818  auto *MSSAWP = getAnalysisIfAvailable<MemorySSAWrapperPass>();
819  std::unique_ptr<MemorySSAUpdater> MSSAU;
820  if (MSSAWP)
821  MSSAU = std::make_unique<MemorySSAUpdater>(&MSSAWP->getMSSA());
822  return GuardWideningImpl(DT, &PDT, LI, MSSAU ? MSSAU.get() : nullptr,
823  DT.getRootNode(),
824  [](BasicBlock *) { return true; })
825  .run();
826  }
827 
828  void getAnalysisUsage(AnalysisUsage &AU) const override {
829  AU.setPreservesCFG();
834  }
835 };
836 
837 /// Same as above, but restricted to a single loop at a time. Can be
838 /// scheduled with other loop passes w/o breaking out of LPM
839 struct LoopGuardWideningLegacyPass : public LoopPass {
840  static char ID;
841 
842  LoopGuardWideningLegacyPass() : LoopPass(ID) {
844  }
845 
846  bool runOnLoop(Loop *L, LPPassManager &LPM) override {
847  if (skipLoop(L))
848  return false;
849  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
850  auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
851  auto *PDTWP = getAnalysisIfAvailable<PostDominatorTreeWrapperPass>();
852  auto *PDT = PDTWP ? &PDTWP->getPostDomTree() : nullptr;
853  auto *MSSAWP = getAnalysisIfAvailable<MemorySSAWrapperPass>();
854  std::unique_ptr<MemorySSAUpdater> MSSAU;
855  if (MSSAWP)
856  MSSAU = std::make_unique<MemorySSAUpdater>(&MSSAWP->getMSSA());
857 
858  BasicBlock *RootBB = L->getLoopPredecessor();
859  if (!RootBB)
860  RootBB = L->getHeader();
861  auto BlockFilter = [&](BasicBlock *BB) {
862  return BB == RootBB || L->contains(BB);
863  };
864  return GuardWideningImpl(DT, PDT, LI, MSSAU ? MSSAU.get() : nullptr,
865  DT.getNode(RootBB), BlockFilter).run();
866  }
867 
868  void getAnalysisUsage(AnalysisUsage &AU) const override {
869  AU.setPreservesCFG();
873  }
874 };
875 }
876 
879 
880 INITIALIZE_PASS_BEGIN(GuardWideningLegacyPass, "guard-widening", "Widen guards",
881  false, false)
885 INITIALIZE_PASS_END(GuardWideningLegacyPass, "guard-widening", "Widen guards",
887 
888 INITIALIZE_PASS_BEGIN(LoopGuardWideningLegacyPass, "loop-guard-widening",
889  "Widen guards (within a single loop, as a loop pass)",
890  false, false)
894 INITIALIZE_PASS_END(LoopGuardWideningLegacyPass, "loop-guard-widening",
895  "Widen guards (within a single loop, as a loop pass)",
896  false, false)
897 
899  return new GuardWideningLegacyPass();
900 }
901 
903  return new LoopGuardWideningLegacyPass();
904 }
i
i
Definition: README.txt:29
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
as
compiles conv shl5 shl ret i32 or10 it would be better as
Definition: README.txt:615
llvm::df_iterator::getPathLength
unsigned getPathLength() const
getPathLength - Return the length of the path from the entry node to the current node,...
Definition: DepthFirstIterator.h:209
LLVM_DUMP_METHOD
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition: Compiler.h:494
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::make_range
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Definition: iterator_range.h:53
llvm::isKnownNonNegative
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.
Definition: ValueTracking.cpp:347
llvm::drop_begin
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
Definition: STLExtras.h:280
print
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
Definition: ArchiveWriter.cpp:189
llvm::CmpInst::Predicate
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:719
llvm::GuardWideningPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: GuardWidening.cpp:762
IntrinsicInst.h
llvm::AnalysisManager::getResult
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:780
Scalar.h
MemorySSAUpdater.h
llvm::Function
Definition: Function.h:60
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:546
Pass.h
llvm::LoopBase::contains
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:138
llvm::BinaryOperator::CreateNot
static BinaryOperator * CreateNot(Value *Op, const Twine &Name="", Instruction *InsertBefore=nullptr)
Definition: Instructions.cpp:2838
llvm::KnownBits::Zero
APInt Zero
Definition: KnownBits.h:24
llvm::ConstantInt::getValue
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:133
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1185
Statistic.h
llvm::LoopBase::getLoopPredecessor
BlockT * getLoopPredecessor() const
If the given loop's header has exactly one unique predecessor outside the loop, return it.
Definition: LoopInfoImpl.h:194
llvm::PatternMatch::m_Add
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
Definition: PatternMatch.h:973
llvm::erase_if
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
Definition: STLExtras.h:1807
llvm::CmpInst::getInversePredicate
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...
Definition: InstrTypes.h:833
llvm::df_end
df_iterator< T > df_end(const T &G)
Definition: DepthFirstIterator.h:224
ValueTracking.h
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
llvm::getLoopAnalysisUsage
void getLoopAnalysisUsage(AnalysisUsage &AU)
Helper to consistently add the set of standard passes to a loop pass's AnalysisUsage.
Definition: LoopUtils.cpp:144
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:139
llvm::ConstantRange::exactIntersectWith
Optional< ConstantRange > exactIntersectWith(const ConstantRange &CR) const
Intersect the two ranges and return the result if it can be represented exactly, otherwise return Non...
Definition: ConstantRange.cpp:703
DenseMap.h
llvm::APInt::getBitWidth
unsigned getBitWidth() const
Return the number of bits in the APInt.
Definition: APInt.h:1411
llvm::sys::path::end
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:235
widening
guard widening
Definition: GuardWidening.cpp:885
llvm::LoopInfoWrapperPass
The legacy pass manager's analysis pass to compute loop information.
Definition: LoopInfo.h:1287
llvm::createGuardWideningPass
FunctionPass * createGuardWideningPass()
Definition: GuardWidening.cpp:898
llvm::LoopStandardAnalysisResults
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
Definition: LoopAnalysisManager.h:51
llvm::DominatorTreeBase::getNode
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
Definition: GenericDomTree.h:351
llvm::Optional
Definition: APInt.h:33
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::count
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
Definition: DenseMap.h:147
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
llvm::dump
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
Definition: SparseBitVector.h:877
RHS
Value * RHS
Definition: X86PartialReduction.cpp:76
llvm::LoopStandardAnalysisResults::DT
DominatorTree & DT
Definition: LoopAnalysisManager.h:54
llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::insert
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:206
llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::count
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
Definition: DenseSet.h:97
llvm::getOffset
static Error getOffset(const SymbolRef &Sym, SectionRef Sec, uint64_t &Result)
Definition: RuntimeDyld.cpp:174
llvm::APInt::isMinValue
bool isMinValue() const
Determine if this is the smallest unsigned value.
Definition: APInt.h:402
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
DepthFirstIterator.h
F
#define F(x, y, z)
Definition: MD5.cpp:55
KnownBits.h
loop
Analysis the ScalarEvolution expression for r is< loop > Outside the loop
Definition: README.txt:8
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
a
=0.0 ? 0.0 :(a > 0.0 ? 1.0 :-1.0) a
Definition: README.txt:489
Widen
static SDValue Widen(SelectionDAG *CurDAG, SDValue N)
Definition: AArch64ISelDAGToDAG.cpp:1069
llvm::createLoopGuardWideningPass
Pass * createLoopGuardWideningPass()
Definition: GuardWidening.cpp:902
llvm::isGuard
bool isGuard(const User *U)
Returns true iff U has semantics of a guard expressed in a form of call of llvm.experimental....
Definition: GuardUtils.cpp:18
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::DominatorTree::dominates
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
Definition: Dominators.cpp:122
CommandLine.h
LHS
Value * LHS
Definition: X86PartialReduction.cpp:75
llvm::ConstantInt
This is the shared class of boolean and integer constants.
Definition: Constants.h:79
llvm::all_of
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:1617
llvm::setWidenableBranchCond
void setWidenableBranchCond(BranchInst *WidenableBR, Value *Cond)
Given a branch we know is widenable (defined per Analysis/GuardUtils.h), set it's condition such that...
Definition: GuardUtils.cpp:108
llvm::MemorySSAWrapperPass
Legacy analysis pass which computes MemorySSA.
Definition: MemorySSA.h:998
llvm::DominatorTreeBase::getRootNode
DomTreeNodeBase< NodeT > * getRootNode()
getRootNode - This returns the entry node for the CFG of the function.
Definition: GenericDomTree.h:370
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
llvm::PatternMatch::match
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
PostDominators.h
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
GuardUtils.h
llvm::PostDominatorTreeWrapperPass
Definition: PostDominators.h:73
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::ms_demangle::QualifierMangleMode::Result
@ Result
Check
#define Check(C,...)
Definition: Lint.cpp:170
false
Definition: StackSlotColoring.cpp:141
llvm::dwarf::Index
Index
Definition: Dwarf.h:472
pass
modulo schedule Modulo Schedule test pass
Definition: ModuloSchedule.cpp:2123
llvm::PatternMatch::m_ConstantInt
class_match< ConstantInt > m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
Definition: PatternMatch.h:147
llvm::Instruction
Definition: Instruction.h:42
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:302
isSupportedGuardInstruction
static bool isSupportedGuardInstruction(const Instruction *Insn)
Definition: GuardWidening.cpp:287
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
llvm::initializeLoopGuardWideningLegacyPassPass
void initializeLoopGuardWideningLegacyPassPass(PassRegistry &)
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:54
llvm::ConstantInt::get
static Constant * get(Type *Ty, uint64_t V, bool IsSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:879
LoopUtils.h
llvm::LPPassManager
Definition: LoopPass.h:76
WidenBranchGuards
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))
PatternMatch.h
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
llvm::initializeGuardWideningLegacyPassPass
void initializeGuardWideningLegacyPassPass(PassRegistry &)
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
llvm::dxil::PointerTypeAnalysis::run
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
Definition: PointerTypeAnalysis.cpp:101
LoopInfo.h
llvm::DenseSet
Implements a dense probed hash-table based set.
Definition: DenseSet.h:268
llvm::getLoopPassPreservedAnalyses
PreservedAnalyses getLoopPassPreservedAnalyses()
Returns the minimum set of Analyses that all loop passes must preserve.
Definition: LoopAnalysisManager.cpp:137
llvm::cl::opt< bool >
llvm::Instruction::eraseFromParent
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:77
llvm::AMDGPU::Hwreg::Offset
Offset
Definition: SIDefines.h:416
llvm::ICmpInst
This instruction compares its operands according to the predicate given to the constructor.
Definition: Instructions.h:1183
llvm::LoopPass
Definition: LoopPass.h:28
llvm::MemorySSAUpdater
Definition: MemorySSAUpdater.h:54
llvm::LPMUpdater
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
Definition: LoopPassManager.h:262
llvm::find
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1637
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::PreservedAnalyses::preserve
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:173
llvm::PatternMatch::m_Or
BinaryOp_match< LHS, RHS, Instruction::Or > m_Or(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1093
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
llvm::DenseMap
Definition: DenseMap.h:716
llvm::LoopInfoBase::getLoopFor
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:986
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
llvm::PatternMatch::m_And
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1087
llvm::df_begin
df_iterator< T > df_begin(const T &G)
Definition: DepthFirstIterator.h:219
llvm::isSafeToSpeculativelyExecute
bool isSafeToSpeculativelyExecute(const Instruction *I, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr)
Return true if the instruction does not have any effects besides calculating the result and does not ...
Definition: ValueTracking.cpp:4682
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::find
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:152
llvm::computeKnownBits
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...
Definition: ValueTracking.cpp:222
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
std::swap
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:853
GuardWidening.h
llvm::DominatorTree::isReachableFromEntry
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
Definition: Dominators.cpp:335
function
print Print MemDeps of function
Definition: MemDepPrinter.cpp:82
llvm::MemorySSAAnalysis
An analysis that produces MemorySSA for a function.
Definition: MemorySSA.h:948
llvm::df_iterator
Definition: DepthFirstIterator.h:86
llvm::SmallPtrSetImpl::count
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:383
llvm::Value::printAsOperand
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:4669
llvm::PatternMatch::m_Value
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:76
llvm::APInt
Class for arbitrary precision integers.
Definition: APInt.h:75
llvm::LoopInfo
Definition: LoopInfo.h:1102
llvm::parseWidenableBranch
bool parseWidenableBranch(const User *U, Value *&Condition, Value *&WidenableCondition, BasicBlock *&IfTrueBB, BasicBlock *&IfFalseBB)
If U is widenable branch looking like: cond = ...
Definition: GuardUtils.cpp:44
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:137
llvm::AnalysisUsage::setPreservesCFG
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:263
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:58
llvm::CmpInst::ICMP_ULT
@ ICMP_ULT
unsigned less than
Definition: InstrTypes.h:744
LoopPass.h
llvm::PostDominatorTree
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
Definition: PostDominators.h:28
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:143
llvm::CFGAnalyses
Represents analyses that only rely on functions' control flow.
Definition: PassManager.h:113
llvm::AnalysisUsage::addPreserved
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
Definition: PassAnalysisSupport.h:98
llvm::append_range
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
Definition: STLExtras.h:1823
llvm::Value::getContext
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:991
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
ConstantRange.h
llvm::LoopStandardAnalysisResults::LI
LoopInfo & LI
Definition: LoopAnalysisManager.h:55
llvm::DomTreeNodeBase< BasicBlock >
llvm::ConstantInt::getFalse
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:834
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:69
Insn
SmallVector< AArch64_IMM::ImmInsnModel, 4 > Insn
Definition: AArch64MIPeepholeOpt.cpp:127
llvm::Constant::getNullValue
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
Definition: Constants.cpp:350
llvm::KnownBits
Definition: KnownBits.h:23
llvm::copy_if
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:1663
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:348
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
llvm::isGuardAsWidenableBranch
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:29
llvm::AnalysisManager::getCachedResult
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
Definition: PassManager.h:799
llvm::BitWidth
constexpr unsigned BitWidth
Definition: BitmaskEnum.h:147
llvm::LoopBase::getHeader
BlockT * getHeader() const
Definition: LoopInfo.h:104
llvm::sort
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1562
guards
guard Widen guards
Definition: GuardWidening.cpp:885
llvm::APInt::getSignedMinValue
static APInt getSignedMinValue(unsigned numBits)
Gets minimum signed value of APInt for a specific bit width.
Definition: APInt.h:199
llvm::ConstantRange
This class represents a range of values.
Definition: ConstantRange.h:47
llvm::df_iterator::getPath
NodeRef getPath(unsigned n) const
getPath - Return the n'th node in the path from the entry node to the current node.
Definition: DepthFirstIterator.h:213
llvm::IntrinsicInst
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:46
GuardUtils.h
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:267
llvm::Pass
Pass interface - Implemented by all 'passes'.
Definition: Pass.h:91
llvm::PreservedAnalyses::preserveSet
void preserveSet()
Mark an analysis set as preserved.
Definition: PassManager.h:188
llvm::PatternMatch::m_Specific
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
Definition: PatternMatch.h:766
llvm::PatternMatch::m_ICmp
CmpClass_match< LHS, RHS, ICmpInst, ICmpInst::Predicate > m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R)
Definition: PatternMatch.h:1388
llvm::CmpInst::ICMP_UGT
@ ICMP_UGT
unsigned greater than
Definition: InstrTypes.h:742
Dominators.h
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:91
getTrue
static Constant * getTrue(Type *Ty)
For a boolean type or a vector of boolean type, return true or a vector with every element true.
Definition: InstructionSimplify.cpp:125
llvm::LoopStandardAnalysisResults::MSSA
MemorySSA * MSSA
Definition: LoopAnalysisManager.h:61
llvm::PatternMatch
Definition: PatternMatch.h:47
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
llvm::ConstantRange::makeExactICmpRegion
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...
Definition: ConstantRange.cpp:156
llvm::SmallPtrSetImpl
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:344
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:308
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::PostDominatorTreeAnalysis
Analysis pass which computes a PostDominatorTree.
Definition: PostDominators.h:47
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(GuardWideningLegacyPass, "guard-widening", "Widen guards", false, false) INITIALIZE_PASS_END(GuardWideningLegacyPass
llvm::cl::desc
Definition: CommandLine.h:405
llvm::PostDominatorTree::dominates
bool dominates(const Instruction *I1, const Instruction *I2) const
Return true if I1 dominates I2.
Definition: PostDominators.cpp:54
InitializePasses.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
Debug.h
llvm::LoopAnalysis
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:1262
llvm::MemorySSAUpdater::removeMemoryAccess
void removeMemoryAccess(MemoryAccess *, bool OptimizePhis=false)
Remove a MemoryAccess from MemorySSA, including updating all definitions and uses.
Definition: MemorySSAUpdater.cpp:1305
llvm::sampleprof::Base
@ Base
Definition: Discriminator.h:58
llvm::SmallVectorImpl::emplace_back
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:927
llvm::SmallPtrSetImpl::insert
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:365
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38