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