LLVM  16.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"
47 #include "llvm/Analysis/LoopInfo.h"
48 #include "llvm/Analysis/LoopPass.h"
52 #include "llvm/IR/ConstantRange.h"
53 #include "llvm/IR/Dominators.h"
54 #include "llvm/IR/IntrinsicInst.h"
55 #include "llvm/IR/PatternMatch.h"
56 #include "llvm/InitializePasses.h"
57 #include "llvm/Pass.h"
59 #include "llvm/Support/Debug.h"
60 #include "llvm/Support/KnownBits.h"
61 #include "llvm/Transforms/Scalar.h"
64 #include <functional>
65 
66 using namespace llvm;
67 
68 #define DEBUG_TYPE "guard-widening"
69 
70 STATISTIC(GuardsEliminated, "Number of eliminated guards");
71 STATISTIC(CondBranchEliminated, "Number of eliminated conditional branches");
72 
73 static cl::opt<bool>
74  WidenBranchGuards("guard-widening-widen-branch-guards", cl::Hidden,
75  cl::desc("Whether or not we should widen guards "
76  "expressed as branches by widenable conditions"),
77  cl::init(true));
78 
79 namespace {
80 
81 // Get the condition of \p I. It can either be a guard or a conditional branch.
82 static Value *getCondition(Instruction *I) {
83  if (IntrinsicInst *GI = dyn_cast<IntrinsicInst>(I)) {
84  assert(GI->getIntrinsicID() == Intrinsic::experimental_guard &&
85  "Bad guard intrinsic?");
86  return GI->getArgOperand(0);
87  }
88  Value *Cond, *WC;
89  BasicBlock *IfTrueBB, *IfFalseBB;
90  if (parseWidenableBranch(I, Cond, WC, IfTrueBB, IfFalseBB))
91  return Cond;
92 
93  return cast<BranchInst>(I)->getCondition();
94 }
95 
96 // Set the condition for \p I to \p NewCond. \p I can either be a guard or a
97 // conditional branch.
98 static void setCondition(Instruction *I, Value *NewCond) {
99  if (IntrinsicInst *GI = dyn_cast<IntrinsicInst>(I)) {
100  assert(GI->getIntrinsicID() == Intrinsic::experimental_guard &&
101  "Bad guard intrinsic?");
102  GI->setArgOperand(0, NewCond);
103  return;
104  }
105  cast<BranchInst>(I)->setCondition(NewCond);
106 }
107 
108 // Eliminates the guard instruction properly.
109 static void eliminateGuard(Instruction *GuardInst, MemorySSAUpdater *MSSAU) {
110  GuardInst->eraseFromParent();
111  if (MSSAU)
112  MSSAU->removeMemoryAccess(GuardInst);
113  ++GuardsEliminated;
114 }
115 
116 class GuardWideningImpl {
117  DominatorTree &DT;
118  PostDominatorTree *PDT;
119  LoopInfo &LI;
120  AssumptionCache &AC;
121  MemorySSAUpdater *MSSAU;
122 
123  /// Together, these describe the region of interest. This might be all of
124  /// the blocks within a function, or only a given loop's blocks and preheader.
125  DomTreeNode *Root;
126  std::function<bool(BasicBlock*)> BlockFilter;
127 
128  /// The set of guards and conditional branches whose conditions have been
129  /// widened into dominating guards.
130  SmallVector<Instruction *, 16> EliminatedGuardsAndBranches;
131 
132  /// The set of guards which have been widened to include conditions to other
133  /// guards.
134  DenseSet<Instruction *> WidenedGuards;
135 
136  /// Try to eliminate instruction \p Instr by widening it into an earlier
137  /// dominating guard. \p DFSI is the DFS iterator on the dominator tree that
138  /// is currently visiting the block containing \p Guard, and \p GuardsPerBlock
139  /// maps BasicBlocks to the set of guards seen in that block.
140  bool eliminateInstrViaWidening(
141  Instruction *Instr, const df_iterator<DomTreeNode *> &DFSI,
143  GuardsPerBlock, bool InvertCondition = false);
144 
145  /// Used to keep track of which widening potential is more effective.
146  enum WideningScore {
147  /// Don't widen.
148  WS_IllegalOrNegative,
149 
150  /// Widening is performance neutral as far as the cycles spent in check
151  /// conditions goes (but can still help, e.g., code layout, having less
152  /// deopt state).
153  WS_Neutral,
154 
155  /// Widening is profitable.
156  WS_Positive,
157 
158  /// Widening is very profitable. Not significantly different from \c
159  /// WS_Positive, except by the order.
160  WS_VeryPositive
161  };
162 
163  static StringRef scoreTypeToString(WideningScore WS);
164 
165  /// Compute the score for widening the condition in \p DominatedInstr
166  /// into \p DominatingGuard. If \p InvertCond is set, then we widen the
167  /// inverted condition of the dominating guard.
168  WideningScore computeWideningScore(Instruction *DominatedInstr,
169  Instruction *DominatingGuard,
170  bool InvertCond);
171 
172  /// Helper to check if \p V can be hoisted to \p InsertPos.
173  bool isAvailableAt(const Value *V, const Instruction *InsertPos) const {
175  return isAvailableAt(V, InsertPos, Visited);
176  }
177 
178  bool isAvailableAt(const Value *V, const Instruction *InsertPos,
179  SmallPtrSetImpl<const Instruction *> &Visited) const;
180 
181  /// Helper to hoist \p V to \p InsertPos. Guaranteed to succeed if \c
182  /// isAvailableAt returned true.
183  void makeAvailableAt(Value *V, Instruction *InsertPos) const;
184 
185  /// Common helper used by \c widenGuard and \c isWideningCondProfitable. Try
186  /// to generate an expression computing the logical AND of \p Cond0 and (\p
187  /// Cond1 XOR \p InvertCondition).
188  /// Return true if the expression computing the AND is only as
189  /// expensive as computing one of the two. If \p InsertPt is true then
190  /// actually generate the resulting expression, make it available at \p
191  /// InsertPt and return it in \p Result (else no change to the IR is made).
192  bool widenCondCommon(Value *Cond0, Value *Cond1, Instruction *InsertPt,
193  Value *&Result, bool InvertCondition);
194 
195  /// Represents a range check of the form \c Base + \c Offset u< \c Length,
196  /// with the constraint that \c Length is not negative. \c CheckInst is the
197  /// pre-existing instruction in the IR that computes the result of this range
198  /// check.
199  class RangeCheck {
200  const Value *Base;
201  const ConstantInt *Offset;
202  const Value *Length;
203  ICmpInst *CheckInst;
204 
205  public:
206  explicit RangeCheck(const Value *Base, const ConstantInt *Offset,
207  const Value *Length, ICmpInst *CheckInst)
208  : Base(Base), Offset(Offset), Length(Length), CheckInst(CheckInst) {}
209 
210  void setBase(const Value *NewBase) { Base = NewBase; }
211  void setOffset(const ConstantInt *NewOffset) { Offset = NewOffset; }
212 
213  const Value *getBase() const { return Base; }
214  const ConstantInt *getOffset() const { return Offset; }
215  const APInt &getOffsetValue() const { return getOffset()->getValue(); }
216  const Value *getLength() const { return Length; };
217  ICmpInst *getCheckInst() const { return CheckInst; }
218 
219  void print(raw_ostream &OS, bool PrintTypes = false) {
220  OS << "Base: ";
221  Base->printAsOperand(OS, PrintTypes);
222  OS << " Offset: ";
223  Offset->printAsOperand(OS, PrintTypes);
224  OS << " Length: ";
225  Length->printAsOperand(OS, PrintTypes);
226  }
227 
228  LLVM_DUMP_METHOD void dump() {
229  print(dbgs());
230  dbgs() << "\n";
231  }
232  };
233 
234  /// Parse \p CheckCond into a conjunction (logical-and) of range checks; and
235  /// append them to \p Checks. Returns true on success, may clobber \c Checks
236  /// on failure.
237  bool parseRangeChecks(Value *CheckCond, SmallVectorImpl<RangeCheck> &Checks) {
239  return parseRangeChecks(CheckCond, Checks, Visited);
240  }
241 
242  bool parseRangeChecks(Value *CheckCond, SmallVectorImpl<RangeCheck> &Checks,
244 
245  /// Combine the checks in \p Checks into a smaller set of checks and append
246  /// them into \p CombinedChecks. Return true on success (i.e. all of checks
247  /// in \p Checks were combined into \p CombinedChecks). Clobbers \p Checks
248  /// and \p CombinedChecks on success and on failure.
249  bool combineRangeChecks(SmallVectorImpl<RangeCheck> &Checks,
250  SmallVectorImpl<RangeCheck> &CombinedChecks) const;
251 
252  /// Can we compute the logical AND of \p Cond0 and \p Cond1 for the price of
253  /// computing only one of the two expressions?
254  bool isWideningCondProfitable(Value *Cond0, Value *Cond1, bool InvertCond) {
255  Value *ResultUnused;
256  return widenCondCommon(Cond0, Cond1, /*InsertPt=*/nullptr, ResultUnused,
257  InvertCond);
258  }
259 
260  /// If \p InvertCondition is false, Widen \p ToWiden to fail if
261  /// \p NewCondition is false, otherwise make it fail if \p NewCondition is
262  /// true (in addition to whatever it is already checking).
263  void widenGuard(Instruction *ToWiden, Value *NewCondition,
264  bool InvertCondition) {
265  Value *Result;
266 
267  widenCondCommon(getCondition(ToWiden), NewCondition, ToWiden, Result,
268  InvertCondition);
269  if (isGuardAsWidenableBranch(ToWiden)) {
270  setWidenableBranchCond(cast<BranchInst>(ToWiden), Result);
271  return;
272  }
273  setCondition(ToWiden, Result);
274  }
275 
276 public:
277  explicit GuardWideningImpl(DominatorTree &DT, PostDominatorTree *PDT,
278  LoopInfo &LI, AssumptionCache &AC,
279  MemorySSAUpdater *MSSAU, DomTreeNode *Root,
280  std::function<bool(BasicBlock *)> BlockFilter)
281  : DT(DT), PDT(PDT), LI(LI), AC(AC), MSSAU(MSSAU), Root(Root),
282  BlockFilter(BlockFilter) {}
283 
284  /// The entry point for this pass.
285  bool run();
286 };
287 }
288 
290  if (isGuard(Insn))
291  return true;
293  return true;
294  return false;
295 }
296 
297 bool GuardWideningImpl::run() {
299  bool Changed = false;
300  for (auto DFI = df_begin(Root), DFE = df_end(Root);
301  DFI != DFE; ++DFI) {
302  auto *BB = (*DFI)->getBlock();
303  if (!BlockFilter(BB))
304  continue;
305 
306  auto &CurrentList = GuardsInBlock[BB];
307 
308  for (auto &I : *BB)
310  CurrentList.push_back(cast<Instruction>(&I));
311 
312  for (auto *II : CurrentList)
313  Changed |= eliminateInstrViaWidening(II, DFI, GuardsInBlock);
314  }
315 
316  assert(EliminatedGuardsAndBranches.empty() || Changed);
317  for (auto *I : EliminatedGuardsAndBranches)
318  if (!WidenedGuards.count(I)) {
319  assert(isa<ConstantInt>(getCondition(I)) && "Should be!");
321  eliminateGuard(I, MSSAU);
322  else {
323  assert(isa<BranchInst>(I) &&
324  "Eliminated something other than guard or branch?");
325  ++CondBranchEliminated;
326  }
327  }
328 
329  return Changed;
330 }
331 
332 bool GuardWideningImpl::eliminateInstrViaWidening(
333  Instruction *Instr, const df_iterator<DomTreeNode *> &DFSI,
335  GuardsInBlock, bool InvertCondition) {
336  // Ignore trivial true or false conditions. These instructions will be
337  // trivially eliminated by any cleanup pass. Do not erase them because other
338  // guards can possibly be widened into them.
339  if (isa<ConstantInt>(getCondition(Instr)))
340  return false;
341 
342  Instruction *BestSoFar = nullptr;
343  auto BestScoreSoFar = WS_IllegalOrNegative;
344 
345  // In the set of dominating guards, find the one we can merge GuardInst with
346  // for the most profit.
347  for (unsigned i = 0, e = DFSI.getPathLength(); i != e; ++i) {
348  auto *CurBB = DFSI.getPath(i)->getBlock();
349  if (!BlockFilter(CurBB))
350  break;
351  assert(GuardsInBlock.count(CurBB) && "Must have been populated by now!");
352  const auto &GuardsInCurBB = GuardsInBlock.find(CurBB)->second;
353 
354  auto I = GuardsInCurBB.begin();
355  auto E = Instr->getParent() == CurBB ? find(GuardsInCurBB, Instr)
356  : GuardsInCurBB.end();
357 
358 #ifndef NDEBUG
359  {
360  unsigned Index = 0;
361  for (auto &I : *CurBB) {
362  if (Index == GuardsInCurBB.size())
363  break;
364  if (GuardsInCurBB[Index] == &I)
365  Index++;
366  }
367  assert(Index == GuardsInCurBB.size() &&
368  "Guards expected to be in order!");
369  }
370 #endif
371 
372  assert((i == (e - 1)) == (Instr->getParent() == CurBB) && "Bad DFS?");
373 
374  for (auto *Candidate : make_range(I, E)) {
375  auto Score = computeWideningScore(Instr, Candidate, InvertCondition);
376  LLVM_DEBUG(dbgs() << "Score between " << *getCondition(Instr)
377  << " and " << *getCondition(Candidate) << " is "
378  << scoreTypeToString(Score) << "\n");
379  if (Score > BestScoreSoFar) {
380  BestScoreSoFar = Score;
381  BestSoFar = Candidate;
382  }
383  }
384  }
385 
386  if (BestScoreSoFar == WS_IllegalOrNegative) {
387  LLVM_DEBUG(dbgs() << "Did not eliminate guard " << *Instr << "\n");
388  return false;
389  }
390 
391  assert(BestSoFar != Instr && "Should have never visited same guard!");
392  assert(DT.dominates(BestSoFar, Instr) && "Should be!");
393 
394  LLVM_DEBUG(dbgs() << "Widening " << *Instr << " into " << *BestSoFar
395  << " with score " << scoreTypeToString(BestScoreSoFar)
396  << "\n");
397  widenGuard(BestSoFar, getCondition(Instr), InvertCondition);
398  auto NewGuardCondition = InvertCondition
400  : ConstantInt::getTrue(Instr->getContext());
401  setCondition(Instr, NewGuardCondition);
402  EliminatedGuardsAndBranches.push_back(Instr);
403  WidenedGuards.insert(BestSoFar);
404  return true;
405 }
406 
407 GuardWideningImpl::WideningScore
408 GuardWideningImpl::computeWideningScore(Instruction *DominatedInstr,
409  Instruction *DominatingGuard,
410  bool InvertCond) {
411  Loop *DominatedInstrLoop = LI.getLoopFor(DominatedInstr->getParent());
412  Loop *DominatingGuardLoop = LI.getLoopFor(DominatingGuard->getParent());
413  bool HoistingOutOfLoop = false;
414 
415  if (DominatingGuardLoop != DominatedInstrLoop) {
416  // Be conservative and don't widen into a sibling loop. TODO: If the
417  // sibling is colder, we should consider allowing this.
418  if (DominatingGuardLoop &&
419  !DominatingGuardLoop->contains(DominatedInstrLoop))
420  return WS_IllegalOrNegative;
421 
422  HoistingOutOfLoop = true;
423  }
424 
425  if (!isAvailableAt(getCondition(DominatedInstr), DominatingGuard))
426  return WS_IllegalOrNegative;
427 
428  // If the guard was conditional executed, it may never be reached
429  // dynamically. There are two potential downsides to hoisting it out of the
430  // conditionally executed region: 1) we may spuriously deopt without need and
431  // 2) we have the extra cost of computing the guard condition in the common
432  // case. At the moment, we really only consider the second in our heuristic
433  // here. TODO: evaluate cost model for spurious deopt
434  // NOTE: As written, this also lets us hoist right over another guard which
435  // is essentially just another spelling for control flow.
436  if (isWideningCondProfitable(getCondition(DominatedInstr),
437  getCondition(DominatingGuard), InvertCond))
438  return HoistingOutOfLoop ? WS_VeryPositive : WS_Positive;
439 
440  if (HoistingOutOfLoop)
441  return WS_Positive;
442 
443  // Returns true if we might be hoisting above explicit control flow. Note
444  // that this completely ignores implicit control flow (guards, calls which
445  // throw, etc...). That choice appears arbitrary.
446  auto MaybeHoistingOutOfIf = [&]() {
447  auto *DominatingBlock = DominatingGuard->getParent();
448  auto *DominatedBlock = DominatedInstr->getParent();
449  if (isGuardAsWidenableBranch(DominatingGuard))
450  DominatingBlock = cast<BranchInst>(DominatingGuard)->getSuccessor(0);
451 
452  // Same Block?
453  if (DominatedBlock == DominatingBlock)
454  return false;
455  // Obvious successor (common loop header/preheader case)
456  if (DominatedBlock == DominatingBlock->getUniqueSuccessor())
457  return false;
458  // TODO: diamond, triangle cases
459  if (!PDT) return true;
460  return !PDT->dominates(DominatedBlock, DominatingBlock);
461  };
462 
463  return MaybeHoistingOutOfIf() ? WS_IllegalOrNegative : WS_Neutral;
464 }
465 
466 bool GuardWideningImpl::isAvailableAt(
467  const Value *V, const Instruction *Loc,
468  SmallPtrSetImpl<const Instruction *> &Visited) const {
469  auto *Inst = dyn_cast<Instruction>(V);
470  if (!Inst || DT.dominates(Inst, Loc) || Visited.count(Inst))
471  return true;
472 
473  if (!isSafeToSpeculativelyExecute(Inst, Loc, &AC, &DT) ||
474  Inst->mayReadFromMemory())
475  return false;
476 
477  Visited.insert(Inst);
478 
479  // We only want to go _up_ the dominance chain when recursing.
480  assert(!isa<PHINode>(Loc) &&
481  "PHIs should return false for isSafeToSpeculativelyExecute");
482  assert(DT.isReachableFromEntry(Inst->getParent()) &&
483  "We did a DFS from the block entry!");
484  return all_of(Inst->operands(),
485  [&](Value *Op) { return isAvailableAt(Op, Loc, Visited); });
486 }
487 
488 void GuardWideningImpl::makeAvailableAt(Value *V, Instruction *Loc) const {
489  auto *Inst = dyn_cast<Instruction>(V);
490  if (!Inst || DT.dominates(Inst, Loc))
491  return;
492 
493  assert(isSafeToSpeculativelyExecute(Inst, Loc, &AC, &DT) &&
494  !Inst->mayReadFromMemory() && "Should've checked with isAvailableAt!");
495 
496  for (Value *Op : Inst->operands())
497  makeAvailableAt(Op, Loc);
498 
499  Inst->moveBefore(Loc);
500  // If we moved instruction before guard we must clean poison generating flags.
501  Inst->dropPoisonGeneratingFlags();
502 }
503 
504 bool GuardWideningImpl::widenCondCommon(Value *Cond0, Value *Cond1,
505  Instruction *InsertPt, Value *&Result,
506  bool InvertCondition) {
507  using namespace llvm::PatternMatch;
508 
509  {
510  // L >u C0 && L >u C1 -> L >u max(C0, C1)
511  ConstantInt *RHS0, *RHS1;
512  Value *LHS;
513  ICmpInst::Predicate Pred0, Pred1;
514  if (match(Cond0, m_ICmp(Pred0, m_Value(LHS), m_ConstantInt(RHS0))) &&
515  match(Cond1, m_ICmp(Pred1, m_Specific(LHS), m_ConstantInt(RHS1)))) {
516  if (InvertCondition)
517  Pred1 = ICmpInst::getInversePredicate(Pred1);
518 
519  ConstantRange CR0 =
521  ConstantRange CR1 =
523 
524  // Given what we're doing here and the semantics of guards, it would
525  // be correct to use a subset intersection, but that may be too
526  // aggressive in cases we care about.
527  if (Optional<ConstantRange> Intersect = CR0.exactIntersectWith(CR1)) {
528  APInt NewRHSAP;
529  CmpInst::Predicate Pred;
530  if (Intersect->getEquivalentICmp(Pred, NewRHSAP)) {
531  if (InsertPt) {
532  ConstantInt *NewRHS =
533  ConstantInt::get(Cond0->getContext(), NewRHSAP);
534  Result = new ICmpInst(InsertPt, Pred, LHS, NewRHS, "wide.chk");
535  }
536  return true;
537  }
538  }
539  }
540  }
541 
542  {
543  SmallVector<GuardWideningImpl::RangeCheck, 4> Checks, CombinedChecks;
544  // TODO: Support InvertCondition case?
545  if (!InvertCondition &&
546  parseRangeChecks(Cond0, Checks) && parseRangeChecks(Cond1, Checks) &&
547  combineRangeChecks(Checks, CombinedChecks)) {
548  if (InsertPt) {
549  Result = nullptr;
550  for (auto &RC : CombinedChecks) {
551  makeAvailableAt(RC.getCheckInst(), InsertPt);
552  if (Result)
553  Result = BinaryOperator::CreateAnd(RC.getCheckInst(), Result, "",
554  InsertPt);
555  else
556  Result = RC.getCheckInst();
557  }
558  assert(Result && "Failed to find result value");
559  Result->setName("wide.chk");
560  }
561  return true;
562  }
563  }
564 
565  // Base case -- just logical-and the two conditions together.
566 
567  if (InsertPt) {
568  makeAvailableAt(Cond0, InsertPt);
569  makeAvailableAt(Cond1, InsertPt);
570  if (InvertCondition)
571  Cond1 = BinaryOperator::CreateNot(Cond1, "inverted", InsertPt);
572  Result = BinaryOperator::CreateAnd(Cond0, Cond1, "wide.chk", InsertPt);
573  }
574 
575  // We were not able to compute Cond0 AND Cond1 for the price of one.
576  return false;
577 }
578 
579 bool GuardWideningImpl::parseRangeChecks(
582  if (!Visited.insert(CheckCond).second)
583  return true;
584 
585  using namespace llvm::PatternMatch;
586 
587  {
588  Value *AndLHS, *AndRHS;
589  if (match(CheckCond, m_And(m_Value(AndLHS), m_Value(AndRHS))))
590  return parseRangeChecks(AndLHS, Checks) &&
591  parseRangeChecks(AndRHS, Checks);
592  }
593 
594  auto *IC = dyn_cast<ICmpInst>(CheckCond);
595  if (!IC || !IC->getOperand(0)->getType()->isIntegerTy() ||
596  (IC->getPredicate() != ICmpInst::ICMP_ULT &&
597  IC->getPredicate() != ICmpInst::ICMP_UGT))
598  return false;
599 
600  const Value *CmpLHS = IC->getOperand(0), *CmpRHS = IC->getOperand(1);
601  if (IC->getPredicate() == ICmpInst::ICMP_UGT)
602  std::swap(CmpLHS, CmpRHS);
603 
604  auto &DL = IC->getModule()->getDataLayout();
605 
606  GuardWideningImpl::RangeCheck Check(
607  CmpLHS, cast<ConstantInt>(ConstantInt::getNullValue(CmpRHS->getType())),
608  CmpRHS, IC);
609 
610  if (!isKnownNonNegative(Check.getLength(), DL))
611  return false;
612 
613  // What we have in \c Check now is a correct interpretation of \p CheckCond.
614  // Try to see if we can move some constant offsets into the \c Offset field.
615 
616  bool Changed;
617  auto &Ctx = CheckCond->getContext();
618 
619  do {
620  Value *OpLHS;
621  ConstantInt *OpRHS;
622  Changed = false;
623 
624 #ifndef NDEBUG
625  auto *BaseInst = dyn_cast<Instruction>(Check.getBase());
626  assert((!BaseInst || DT.isReachableFromEntry(BaseInst->getParent())) &&
627  "Unreachable instruction?");
628 #endif
629 
630  if (match(Check.getBase(), m_Add(m_Value(OpLHS), m_ConstantInt(OpRHS)))) {
631  Check.setBase(OpLHS);
632  APInt NewOffset = Check.getOffsetValue() + OpRHS->getValue();
633  Check.setOffset(ConstantInt::get(Ctx, NewOffset));
634  Changed = true;
635  } else if (match(Check.getBase(),
636  m_Or(m_Value(OpLHS), m_ConstantInt(OpRHS)))) {
637  KnownBits Known = computeKnownBits(OpLHS, DL);
638  if ((OpRHS->getValue() & Known.Zero) == OpRHS->getValue()) {
639  Check.setBase(OpLHS);
640  APInt NewOffset = Check.getOffsetValue() + OpRHS->getValue();
641  Check.setOffset(ConstantInt::get(Ctx, NewOffset));
642  Changed = true;
643  }
644  }
645  } while (Changed);
646 
647  Checks.push_back(Check);
648  return true;
649 }
650 
651 bool GuardWideningImpl::combineRangeChecks(
653  SmallVectorImpl<GuardWideningImpl::RangeCheck> &RangeChecksOut) const {
654  unsigned OldCount = Checks.size();
655  while (!Checks.empty()) {
656  // Pick all of the range checks with a specific base and length, and try to
657  // merge them.
658  const Value *CurrentBase = Checks.front().getBase();
659  const Value *CurrentLength = Checks.front().getLength();
660 
662 
663  auto IsCurrentCheck = [&](GuardWideningImpl::RangeCheck &RC) {
664  return RC.getBase() == CurrentBase && RC.getLength() == CurrentLength;
665  };
666 
667  copy_if(Checks, std::back_inserter(CurrentChecks), IsCurrentCheck);
668  erase_if(Checks, IsCurrentCheck);
669 
670  assert(CurrentChecks.size() != 0 && "We know we have at least one!");
671 
672  if (CurrentChecks.size() < 3) {
673  llvm::append_range(RangeChecksOut, CurrentChecks);
674  continue;
675  }
676 
677  // CurrentChecks.size() will typically be 3 here, but so far there has been
678  // no need to hard-code that fact.
679 
680  llvm::sort(CurrentChecks, [&](const GuardWideningImpl::RangeCheck &LHS,
681  const GuardWideningImpl::RangeCheck &RHS) {
682  return LHS.getOffsetValue().slt(RHS.getOffsetValue());
683  });
684 
685  // Note: std::sort should not invalidate the ChecksStart iterator.
686 
687  const ConstantInt *MinOffset = CurrentChecks.front().getOffset();
688  const ConstantInt *MaxOffset = CurrentChecks.back().getOffset();
689 
690  unsigned BitWidth = MaxOffset->getValue().getBitWidth();
691  if ((MaxOffset->getValue() - MinOffset->getValue())
693  return false;
694 
695  APInt MaxDiff = MaxOffset->getValue() - MinOffset->getValue();
696  const APInt &HighOffset = MaxOffset->getValue();
697  auto OffsetOK = [&](const GuardWideningImpl::RangeCheck &RC) {
698  return (HighOffset - RC.getOffsetValue()).ult(MaxDiff);
699  };
700 
701  if (MaxDiff.isMinValue() || !all_of(drop_begin(CurrentChecks), OffsetOK))
702  return false;
703 
704  // We have a series of f+1 checks as:
705  //
706  // I+k_0 u< L ... Chk_0
707  // I+k_1 u< L ... Chk_1
708  // ...
709  // I+k_f u< L ... Chk_f
710  //
711  // with forall i in [0,f]: k_f-k_i u< k_f-k_0 ... Precond_0
712  // k_f-k_0 u< INT_MIN+k_f ... Precond_1
713  // k_f != k_0 ... Precond_2
714  //
715  // Claim:
716  // Chk_0 AND Chk_f implies all the other checks
717  //
718  // Informal proof sketch:
719  //
720  // We will show that the integer range [I+k_0,I+k_f] does not unsigned-wrap
721  // (i.e. going from I+k_0 to I+k_f does not cross the -1,0 boundary) and
722  // thus I+k_f is the greatest unsigned value in that range.
723  //
724  // This combined with Ckh_(f+1) shows that everything in that range is u< L.
725  // Via Precond_0 we know that all of the indices in Chk_0 through Chk_(f+1)
726  // lie in [I+k_0,I+k_f], this proving our claim.
727  //
728  // To see that [I+k_0,I+k_f] is not a wrapping range, note that there are
729  // two possibilities: I+k_0 u< I+k_f or I+k_0 >u I+k_f (they can't be equal
730  // since k_0 != k_f). In the former case, [I+k_0,I+k_f] is not a wrapping
731  // range by definition, and the latter case is impossible:
732  //
733  // 0-----I+k_f---I+k_0----L---INT_MAX,INT_MIN------------------(-1)
734  // xxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
735  //
736  // For Chk_0 to succeed, we'd have to have k_f-k_0 (the range highlighted
737  // with 'x' above) to be at least >u INT_MIN.
738 
739  RangeChecksOut.emplace_back(CurrentChecks.front());
740  RangeChecksOut.emplace_back(CurrentChecks.back());
741  }
742 
743  assert(RangeChecksOut.size() <= OldCount && "We pessimized!");
744  return RangeChecksOut.size() != OldCount;
745 }
746 
747 #ifndef NDEBUG
748 StringRef GuardWideningImpl::scoreTypeToString(WideningScore WS) {
749  switch (WS) {
750  case WS_IllegalOrNegative:
751  return "IllegalOrNegative";
752  case WS_Neutral:
753  return "Neutral";
754  case WS_Positive:
755  return "Positive";
756  case WS_VeryPositive:
757  return "VeryPositive";
758  }
759 
760  llvm_unreachable("Fully covered switch above!");
761 }
762 #endif
763 
766  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
767  auto &LI = AM.getResult<LoopAnalysis>(F);
768  auto &PDT = AM.getResult<PostDominatorTreeAnalysis>(F);
769  auto &AC = AM.getResult<AssumptionAnalysis>(F);
770  auto *MSSAA = AM.getCachedResult<MemorySSAAnalysis>(F);
771  std::unique_ptr<MemorySSAUpdater> MSSAU;
772  if (MSSAA)
773  MSSAU = std::make_unique<MemorySSAUpdater>(&MSSAA->getMSSA());
774  if (!GuardWideningImpl(DT, &PDT, LI, AC, MSSAU ? MSSAU.get() : nullptr,
775  DT.getRootNode(), [](BasicBlock *) { return true; })
776  .run())
777  return PreservedAnalyses::all();
778 
780  PA.preserveSet<CFGAnalyses>();
782  return PA;
783 }
784 
787  LPMUpdater &U) {
788  BasicBlock *RootBB = L.getLoopPredecessor();
789  if (!RootBB)
790  RootBB = L.getHeader();
791  auto BlockFilter = [&](BasicBlock *BB) {
792  return BB == RootBB || L.contains(BB);
793  };
794  std::unique_ptr<MemorySSAUpdater> MSSAU;
795  if (AR.MSSA)
796  MSSAU = std::make_unique<MemorySSAUpdater>(AR.MSSA);
797  if (!GuardWideningImpl(AR.DT, nullptr, AR.LI, AR.AC,
798  MSSAU ? MSSAU.get() : nullptr, AR.DT.getNode(RootBB),
799  BlockFilter)
800  .run())
801  return PreservedAnalyses::all();
802 
803  auto PA = getLoopPassPreservedAnalyses();
804  if (AR.MSSA)
805  PA.preserve<MemorySSAAnalysis>();
806  return PA;
807 }
808 
809 namespace {
810 struct GuardWideningLegacyPass : public FunctionPass {
811  static char ID;
812 
813  GuardWideningLegacyPass() : FunctionPass(ID) {
815  }
816 
817  bool runOnFunction(Function &F) override {
818  if (skipFunction(F))
819  return false;
820  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
821  auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
822  auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
823  auto &PDT = getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();
824  auto *MSSAWP = getAnalysisIfAvailable<MemorySSAWrapperPass>();
825  std::unique_ptr<MemorySSAUpdater> MSSAU;
826  if (MSSAWP)
827  MSSAU = std::make_unique<MemorySSAUpdater>(&MSSAWP->getMSSA());
828  return GuardWideningImpl(DT, &PDT, LI, AC, MSSAU ? MSSAU.get() : nullptr,
829  DT.getRootNode(),
830  [](BasicBlock *) { return true; })
831  .run();
832  }
833 
834  void getAnalysisUsage(AnalysisUsage &AU) const override {
835  AU.setPreservesCFG();
840  }
841 };
842 
843 /// Same as above, but restricted to a single loop at a time. Can be
844 /// scheduled with other loop passes w/o breaking out of LPM
845 struct LoopGuardWideningLegacyPass : public LoopPass {
846  static char ID;
847 
848  LoopGuardWideningLegacyPass() : LoopPass(ID) {
850  }
851 
852  bool runOnLoop(Loop *L, LPPassManager &LPM) override {
853  if (skipLoop(L))
854  return false;
855  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
856  auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
857  auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
858  *L->getHeader()->getParent());
859  auto *PDTWP = getAnalysisIfAvailable<PostDominatorTreeWrapperPass>();
860  auto *PDT = PDTWP ? &PDTWP->getPostDomTree() : nullptr;
861  auto *MSSAWP = getAnalysisIfAvailable<MemorySSAWrapperPass>();
862  std::unique_ptr<MemorySSAUpdater> MSSAU;
863  if (MSSAWP)
864  MSSAU = std::make_unique<MemorySSAUpdater>(&MSSAWP->getMSSA());
865 
866  BasicBlock *RootBB = L->getLoopPredecessor();
867  if (!RootBB)
868  RootBB = L->getHeader();
869  auto BlockFilter = [&](BasicBlock *BB) {
870  return BB == RootBB || L->contains(BB);
871  };
872  return GuardWideningImpl(DT, PDT, LI, AC, MSSAU ? MSSAU.get() : nullptr,
873  DT.getNode(RootBB), BlockFilter)
874  .run();
875  }
876 
877  void getAnalysisUsage(AnalysisUsage &AU) const override {
878  AU.setPreservesCFG();
882  }
883 };
884 }
885 
888 
889 INITIALIZE_PASS_BEGIN(GuardWideningLegacyPass, "guard-widening", "Widen guards",
890  false, false)
894 INITIALIZE_PASS_END(GuardWideningLegacyPass, "guard-widening", "Widen guards",
896 
897 INITIALIZE_PASS_BEGIN(LoopGuardWideningLegacyPass, "loop-guard-widening",
898  "Widen guards (within a single loop, as a loop pass)",
899  false, false)
903 INITIALIZE_PASS_END(LoopGuardWideningLegacyPass, "loop-guard-widening",
904  "Widen guards (within a single loop, as a loop pass)",
905  false, false)
906 
908  return new GuardWideningLegacyPass();
909 }
910 
912  return new LoopGuardWideningLegacyPass();
913 }
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
AssumptionCache.h
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:492
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::LoopStandardAnalysisResults::AC
AssumptionCache & AC
Definition: LoopAnalysisManager.h:53
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:321
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:387
llvm::AArch64PACKey::ID
ID
Definition: AArch64BaseInfo.h:818
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:764
llvm::BasicBlock::getParent
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:104
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:774
Scalar.h
MemorySSAUpdater.h
llvm::Function
Definition: Function.h:60
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:547
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:139
llvm::BinaryOperator::CreateNot
static BinaryOperator * CreateNot(Value *Op, const Twine &Name="", Instruction *InsertBefore=nullptr)
Definition: Instructions.cpp:2992
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:1199
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:211
llvm::PatternMatch::m_Add
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
Definition: PatternMatch.h:979
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:1972
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:142
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:140
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:1431
llvm::sys::path::end
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:235
widening
guard widening
Definition: GuardWidening.cpp:894
llvm::LoopInfoWrapperPass
The legacy pass manager's analysis pass to compute loop information.
Definition: LoopInfo.h:1293
llvm::createGuardWideningPass
FunctionPass * createGuardWideningPass()
Definition: GuardWidening.cpp:907
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:145
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:172
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:1101
llvm::createLoopGuardWideningPass
Pass * createLoopGuardWideningPass()
Definition: GuardWidening.cpp:911
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:1709
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:984
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:24
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:2145
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:289
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:52
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:189
LoopInfo.h
llvm::sort
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1657
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:81
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:1185
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:1729
llvm::AssumptionAnalysis
A function analysis which provides an AssumptionCache.
Definition: AssumptionCache.h:173
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:1099
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:53
llvm::DenseMap
Definition: DenseMap.h:714
llvm::LoopInfoBase::getLoopFor
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:992
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:447
llvm::PatternMatch::m_And
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1093
llvm::df_begin
df_iterator< T > df_begin(const T &G)
Definition: DepthFirstIterator.h:219
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:150
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:196
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:934
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:4758
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::print
Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr)
Definition: GCNRegPressure.cpp:138
llvm::LoopInfo
Definition: LoopInfo.h:1108
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:265
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
llvm::AssumptionCache
A cache of @llvm.assume calls within a function.
Definition: AssumptionCache.h:42
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:1988
llvm::Value::getContext
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:994
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:85
Insn
SmallVector< AArch64_IMM::ImmInsnModel, 4 > Insn
Definition: AArch64MIPeepholeOpt.cpp:130
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:1755
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:793
llvm::BitWidth
constexpr unsigned BitWidth
Definition: BitmaskEnum.h:147
llvm::LoopBase::getHeader
BlockT * getHeader() const
Definition: LoopInfo.h:105
guards
guard Widen guards
Definition: GuardWidening.cpp:894
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:772
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:1394
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:413
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::isSafeToSpeculativelyExecute
bool isSafeToSpeculativelyExecute(const Instruction *I, const Instruction *CtxI=nullptr, AssumptionCache *AC=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:4730
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:1268
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:941
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