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");
72STATISTIC(FreezeAdded, "Number of freeze instruction introduced");
73
74static cl::opt<bool>
75 WidenBranchGuards("guard-widening-widen-branch-guards", cl::Hidden,
76 cl::desc("Whether or not we should widen guards "
77 "expressed as branches by widenable conditions"),
78 cl::init(true));
79
80namespace {
81
82// Get the condition of \p I. It can either be a guard or a conditional branch.
83static Value *getCondition(Instruction *I) {
84 if (IntrinsicInst *GI = dyn_cast<IntrinsicInst>(I)) {
85 assert(GI->getIntrinsicID() == Intrinsic::experimental_guard &&
86 "Bad guard intrinsic?");
87 return GI->getArgOperand(0);
88 }
89 Value *Cond, *WC;
90 BasicBlock *IfTrueBB, *IfFalseBB;
91 if (parseWidenableBranch(I, Cond, WC, IfTrueBB, IfFalseBB))
92 return Cond;
93
94 return cast<BranchInst>(I)->getCondition();
95}
96
97// Set the condition for \p I to \p NewCond. \p I can either be a guard or a
98// conditional branch.
99static void setCondition(Instruction *I, Value *NewCond) {
100 if (IntrinsicInst *GI = dyn_cast<IntrinsicInst>(I)) {
101 assert(GI->getIntrinsicID() == Intrinsic::experimental_guard &&
102 "Bad guard intrinsic?");
103 GI->setArgOperand(0, NewCond);
104 return;
105 }
106 cast<BranchInst>(I)->setCondition(NewCond);
107}
108
109// Eliminates the guard instruction properly.
110static void eliminateGuard(Instruction *GuardInst, MemorySSAUpdater *MSSAU) {
111 GuardInst->eraseFromParent();
112 if (MSSAU)
113 MSSAU->removeMemoryAccess(GuardInst);
114 ++GuardsEliminated;
115}
116
117/// Find a point at which the widened condition of \p Guard should be inserted.
118/// When it is represented as intrinsic call, we can do it right before the call
119/// instruction. However, when we are dealing with widenable branch, we must
120/// account for the following situation: widening should not turn a
121/// loop-invariant condition into a loop-variant. It means that if
122/// widenable.condition() call is invariant (w.r.t. any loop), the new wide
123/// condition should stay invariant. Otherwise there can be a miscompile, like
124/// the one described at https://github.com/llvm/llvm-project/issues/60234. The
125/// safest way to do it is to expand the new condition at WC's block.
126static Instruction *findInsertionPointForWideCondition(Instruction *Guard) {
127 Value *Condition, *WC;
128 BasicBlock *IfTrue, *IfFalse;
129 if (parseWidenableBranch(Guard, Condition, WC, IfTrue, IfFalse))
130 return cast<Instruction>(WC);
131 return Guard;
132}
133
134class GuardWideningImpl {
135 DominatorTree &DT;
137 LoopInfo &LI;
138 AssumptionCache &AC;
139 MemorySSAUpdater *MSSAU;
140
141 /// Together, these describe the region of interest. This might be all of
142 /// the blocks within a function, or only a given loop's blocks and preheader.
143 DomTreeNode *Root;
144 std::function<bool(BasicBlock*)> BlockFilter;
145
146 /// The set of guards and conditional branches whose conditions have been
147 /// widened into dominating guards.
148 SmallVector<Instruction *, 16> EliminatedGuardsAndBranches;
149
150 /// The set of guards which have been widened to include conditions to other
151 /// guards.
152 DenseSet<Instruction *> WidenedGuards;
153
154 /// Try to eliminate instruction \p Instr by widening it into an earlier
155 /// dominating guard. \p DFSI is the DFS iterator on the dominator tree that
156 /// is currently visiting the block containing \p Guard, and \p GuardsPerBlock
157 /// maps BasicBlocks to the set of guards seen in that block.
158 bool eliminateInstrViaWidening(
159 Instruction *Instr, const df_iterator<DomTreeNode *> &DFSI,
161 GuardsPerBlock, bool InvertCondition = false);
162
163 /// Used to keep track of which widening potential is more effective.
164 enum WideningScore {
165 /// Don't widen.
166 WS_IllegalOrNegative,
167
168 /// Widening is performance neutral as far as the cycles spent in check
169 /// conditions goes (but can still help, e.g., code layout, having less
170 /// deopt state).
171 WS_Neutral,
172
173 /// Widening is profitable.
174 WS_Positive,
175
176 /// Widening is very profitable. Not significantly different from \c
177 /// WS_Positive, except by the order.
178 WS_VeryPositive
179 };
180
181 static StringRef scoreTypeToString(WideningScore WS);
182
183 /// Compute the score for widening the condition in \p DominatedInstr
184 /// into \p DominatingGuard. If \p InvertCond is set, then we widen the
185 /// inverted condition of the dominating guard.
186 WideningScore computeWideningScore(Instruction *DominatedInstr,
187 Instruction *DominatingGuard,
188 bool InvertCond);
189
190 /// Helper to check if \p V can be hoisted to \p InsertPos.
191 bool canBeHoistedTo(const Value *V, const Instruction *InsertPos) const {
193 return canBeHoistedTo(V, InsertPos, Visited);
194 }
195
196 bool canBeHoistedTo(const Value *V, const Instruction *InsertPos,
198
199 /// Helper to hoist \p V to \p InsertPos. Guaranteed to succeed if \c
200 /// canBeHoistedTo returned true.
201 void makeAvailableAt(Value *V, Instruction *InsertPos) const;
202
203 /// Common helper used by \c widenGuard and \c isWideningCondProfitable. Try
204 /// to generate an expression computing the logical AND of \p Cond0 and (\p
205 /// Cond1 XOR \p InvertCondition).
206 /// Return true if the expression computing the AND is only as
207 /// expensive as computing one of the two. If \p InsertPt is true then
208 /// actually generate the resulting expression, make it available at \p
209 /// InsertPt and return it in \p Result (else no change to the IR is made).
210 bool widenCondCommon(Value *Cond0, Value *Cond1, Instruction *InsertPt,
211 Value *&Result, bool InvertCondition);
212
213 /// Adds freeze to Orig and push it as far as possible very aggressively.
214 /// Also replaces all uses of frozen instruction with frozen version.
215 Value *freezeAndPush(Value *Orig, Instruction *InsertPt);
216
217 /// Represents a range check of the form \c Base + \c Offset u< \c Length,
218 /// with the constraint that \c Length is not negative. \c CheckInst is the
219 /// pre-existing instruction in the IR that computes the result of this range
220 /// check.
221 class RangeCheck {
222 const Value *Base;
223 const ConstantInt *Offset;
224 const Value *Length;
225 ICmpInst *CheckInst;
226
227 public:
228 explicit RangeCheck(const Value *Base, const ConstantInt *Offset,
229 const Value *Length, ICmpInst *CheckInst)
230 : Base(Base), Offset(Offset), Length(Length), CheckInst(CheckInst) {}
231
232 void setBase(const Value *NewBase) { Base = NewBase; }
233 void setOffset(const ConstantInt *NewOffset) { Offset = NewOffset; }
234
235 const Value *getBase() const { return Base; }
236 const ConstantInt *getOffset() const { return Offset; }
237 const APInt &getOffsetValue() const { return getOffset()->getValue(); }
238 const Value *getLength() const { return Length; };
239 ICmpInst *getCheckInst() const { return CheckInst; }
240
241 void print(raw_ostream &OS, bool PrintTypes = false) {
242 OS << "Base: ";
243 Base->printAsOperand(OS, PrintTypes);
244 OS << " Offset: ";
245 Offset->printAsOperand(OS, PrintTypes);
246 OS << " Length: ";
247 Length->printAsOperand(OS, PrintTypes);
248 }
249
250 LLVM_DUMP_METHOD void dump() {
251 print(dbgs());
252 dbgs() << "\n";
253 }
254 };
255
256 /// Parse \p CheckCond into a conjunction (logical-and) of range checks; and
257 /// append them to \p Checks. Returns true on success, may clobber \c Checks
258 /// on failure.
259 bool parseRangeChecks(Value *CheckCond, SmallVectorImpl<RangeCheck> &Checks) {
261 return parseRangeChecks(CheckCond, Checks, Visited);
262 }
263
264 bool parseRangeChecks(Value *CheckCond, SmallVectorImpl<RangeCheck> &Checks,
266
267 /// Combine the checks in \p Checks into a smaller set of checks and append
268 /// them into \p CombinedChecks. Return true on success (i.e. all of checks
269 /// in \p Checks were combined into \p CombinedChecks). Clobbers \p Checks
270 /// and \p CombinedChecks on success and on failure.
271 bool combineRangeChecks(SmallVectorImpl<RangeCheck> &Checks,
272 SmallVectorImpl<RangeCheck> &CombinedChecks) const;
273
274 /// Can we compute the logical AND of \p Cond0 and \p Cond1 for the price of
275 /// computing only one of the two expressions?
276 bool isWideningCondProfitable(Value *Cond0, Value *Cond1, bool InvertCond) {
277 Value *ResultUnused;
278 return widenCondCommon(Cond0, Cond1, /*InsertPt=*/nullptr, ResultUnused,
279 InvertCond);
280 }
281
282 /// If \p InvertCondition is false, Widen \p ToWiden to fail if
283 /// \p NewCondition is false, otherwise make it fail if \p NewCondition is
284 /// true (in addition to whatever it is already checking).
285 void widenGuard(Instruction *ToWiden, Value *NewCondition,
286 bool InvertCondition) {
287 Value *Result;
288 Instruction *InsertPt = findInsertionPointForWideCondition(ToWiden);
289 widenCondCommon(getCondition(ToWiden), NewCondition, InsertPt, Result,
290 InvertCondition);
291 if (isGuardAsWidenableBranch(ToWiden)) {
292 setWidenableBranchCond(cast<BranchInst>(ToWiden), Result);
293 return;
294 }
295 setCondition(ToWiden, Result);
296 }
297
298public:
299 explicit GuardWideningImpl(DominatorTree &DT, PostDominatorTree *PDT,
300 LoopInfo &LI, AssumptionCache &AC,
301 MemorySSAUpdater *MSSAU, DomTreeNode *Root,
302 std::function<bool(BasicBlock *)> BlockFilter)
303 : DT(DT), PDT(PDT), LI(LI), AC(AC), MSSAU(MSSAU), Root(Root),
304 BlockFilter(BlockFilter) {}
305
306 /// The entry point for this pass.
307 bool run();
308};
309}
310
312 if (isGuard(Insn))
313 return true;
315 return true;
316 return false;
317}
318
319bool GuardWideningImpl::run() {
321 bool Changed = false;
322 for (auto DFI = df_begin(Root), DFE = df_end(Root);
323 DFI != DFE; ++DFI) {
324 auto *BB = (*DFI)->getBlock();
325 if (!BlockFilter(BB))
326 continue;
327
328 auto &CurrentList = GuardsInBlock[BB];
329
330 for (auto &I : *BB)
332 CurrentList.push_back(cast<Instruction>(&I));
333
334 for (auto *II : CurrentList)
335 Changed |= eliminateInstrViaWidening(II, DFI, GuardsInBlock);
336 }
337
338 assert(EliminatedGuardsAndBranches.empty() || Changed);
339 for (auto *I : EliminatedGuardsAndBranches)
340 if (!WidenedGuards.count(I)) {
341 assert(isa<ConstantInt>(getCondition(I)) && "Should be!");
343 eliminateGuard(I, MSSAU);
344 else {
345 assert(isa<BranchInst>(I) &&
346 "Eliminated something other than guard or branch?");
347 ++CondBranchEliminated;
348 }
349 }
350
351 return Changed;
352}
353
354bool GuardWideningImpl::eliminateInstrViaWidening(
355 Instruction *Instr, const df_iterator<DomTreeNode *> &DFSI,
357 GuardsInBlock, bool InvertCondition) {
358 // Ignore trivial true or false conditions. These instructions will be
359 // trivially eliminated by any cleanup pass. Do not erase them because other
360 // guards can possibly be widened into them.
361 if (isa<ConstantInt>(getCondition(Instr)))
362 return false;
363
364 Instruction *BestSoFar = nullptr;
365 auto BestScoreSoFar = WS_IllegalOrNegative;
366
367 // In the set of dominating guards, find the one we can merge GuardInst with
368 // for the most profit.
369 for (unsigned i = 0, e = DFSI.getPathLength(); i != e; ++i) {
370 auto *CurBB = DFSI.getPath(i)->getBlock();
371 if (!BlockFilter(CurBB))
372 break;
373 assert(GuardsInBlock.count(CurBB) && "Must have been populated by now!");
374 const auto &GuardsInCurBB = GuardsInBlock.find(CurBB)->second;
375
376 auto I = GuardsInCurBB.begin();
377 auto E = Instr->getParent() == CurBB ? find(GuardsInCurBB, Instr)
378 : GuardsInCurBB.end();
379
380#ifndef NDEBUG
381 {
382 unsigned Index = 0;
383 for (auto &I : *CurBB) {
384 if (Index == GuardsInCurBB.size())
385 break;
386 if (GuardsInCurBB[Index] == &I)
387 Index++;
388 }
389 assert(Index == GuardsInCurBB.size() &&
390 "Guards expected to be in order!");
391 }
392#endif
393
394 assert((i == (e - 1)) == (Instr->getParent() == CurBB) && "Bad DFS?");
395
396 for (auto *Candidate : make_range(I, E)) {
397 auto Score = computeWideningScore(Instr, Candidate, InvertCondition);
398 LLVM_DEBUG(dbgs() << "Score between " << *getCondition(Instr)
399 << " and " << *getCondition(Candidate) << " is "
400 << scoreTypeToString(Score) << "\n");
401 if (Score > BestScoreSoFar) {
402 BestScoreSoFar = Score;
403 BestSoFar = Candidate;
404 }
405 }
406 }
407
408 if (BestScoreSoFar == WS_IllegalOrNegative) {
409 LLVM_DEBUG(dbgs() << "Did not eliminate guard " << *Instr << "\n");
410 return false;
411 }
412
413 assert(BestSoFar != Instr && "Should have never visited same guard!");
414 assert(DT.dominates(BestSoFar, Instr) && "Should be!");
415
416 LLVM_DEBUG(dbgs() << "Widening " << *Instr << " into " << *BestSoFar
417 << " with score " << scoreTypeToString(BestScoreSoFar)
418 << "\n");
419 widenGuard(BestSoFar, getCondition(Instr), InvertCondition);
420 auto NewGuardCondition = InvertCondition
422 : ConstantInt::getTrue(Instr->getContext());
423 setCondition(Instr, NewGuardCondition);
424 EliminatedGuardsAndBranches.push_back(Instr);
425 WidenedGuards.insert(BestSoFar);
426 return true;
427}
428
429GuardWideningImpl::WideningScore
430GuardWideningImpl::computeWideningScore(Instruction *DominatedInstr,
431 Instruction *DominatingGuard,
432 bool InvertCond) {
433 Loop *DominatedInstrLoop = LI.getLoopFor(DominatedInstr->getParent());
434 Loop *DominatingGuardLoop = LI.getLoopFor(DominatingGuard->getParent());
435 bool HoistingOutOfLoop = false;
436
437 if (DominatingGuardLoop != DominatedInstrLoop) {
438 // Be conservative and don't widen into a sibling loop. TODO: If the
439 // sibling is colder, we should consider allowing this.
440 if (DominatingGuardLoop &&
441 !DominatingGuardLoop->contains(DominatedInstrLoop))
442 return WS_IllegalOrNegative;
443
444 HoistingOutOfLoop = true;
445 }
446
447 auto *WideningPoint = findInsertionPointForWideCondition(DominatingGuard);
448 if (!canBeHoistedTo(getCondition(DominatedInstr), WideningPoint))
449 return WS_IllegalOrNegative;
450 if (!canBeHoistedTo(getCondition(DominatingGuard), WideningPoint))
451 return WS_IllegalOrNegative;
452
453 // If the guard was conditional executed, it may never be reached
454 // dynamically. There are two potential downsides to hoisting it out of the
455 // conditionally executed region: 1) we may spuriously deopt without need and
456 // 2) we have the extra cost of computing the guard condition in the common
457 // case. At the moment, we really only consider the second in our heuristic
458 // here. TODO: evaluate cost model for spurious deopt
459 // NOTE: As written, this also lets us hoist right over another guard which
460 // is essentially just another spelling for control flow.
461 if (isWideningCondProfitable(getCondition(DominatedInstr),
462 getCondition(DominatingGuard), InvertCond))
463 return HoistingOutOfLoop ? WS_VeryPositive : WS_Positive;
464
465 if (HoistingOutOfLoop)
466 return WS_Positive;
467
468 // For a given basic block \p BB, return its successor which is guaranteed or
469 // highly likely will be taken as its successor.
470 auto GetLikelySuccessor = [](const BasicBlock * BB)->const BasicBlock * {
471 if (auto *UniqueSucc = BB->getUniqueSuccessor())
472 return UniqueSucc;
473 auto *Term = BB->getTerminator();
474 Value *Cond = nullptr;
475 const BasicBlock *IfTrue = nullptr, *IfFalse = nullptr;
476 using namespace PatternMatch;
477 if (!match(Term, m_Br(m_Value(Cond), m_BasicBlock(IfTrue),
478 m_BasicBlock(IfFalse))))
479 return nullptr;
480 // For constant conditions, only one dynamical successor is possible
481 if (auto *ConstCond = dyn_cast<ConstantInt>(Cond))
482 return ConstCond->isAllOnesValue() ? IfTrue : IfFalse;
483 // If one of successors ends with deopt, another one is likely.
484 if (IfFalse->getPostdominatingDeoptimizeCall())
485 return IfTrue;
487 return IfFalse;
488 // TODO: Use branch frequency metatada to allow hoisting through non-deopt
489 // branches?
490 return nullptr;
491 };
492
493 // Returns true if we might be hoisting above explicit control flow into a
494 // considerably hotter block. Note that this completely ignores implicit
495 // control flow (guards, calls which throw, etc...). That choice appears
496 // arbitrary (we assume that implicit control flow exits are all rare).
497 auto MaybeHoistingToHotterBlock = [&]() {
498 const auto *DominatingBlock = DominatingGuard->getParent();
499 const auto *DominatedBlock = DominatedInstr->getParent();
500
501 // Descend as low as we can, always taking the likely successor.
502 assert(DT.isReachableFromEntry(DominatingBlock) && "Unreached code");
503 assert(DT.isReachableFromEntry(DominatedBlock) && "Unreached code");
504 assert(DT.dominates(DominatingBlock, DominatedBlock) && "No dominance");
505 while (DominatedBlock != DominatingBlock) {
506 auto *LikelySucc = GetLikelySuccessor(DominatingBlock);
507 // No likely successor?
508 if (!LikelySucc)
509 break;
510 // Only go down the dominator tree.
511 if (!DT.properlyDominates(DominatingBlock, LikelySucc))
512 break;
513 DominatingBlock = LikelySucc;
514 }
515
516 // Found?
517 if (DominatedBlock == DominatingBlock)
518 return false;
519 // We followed the likely successor chain and went past the dominated
520 // block. It means that the dominated guard is in dead/very cold code.
521 if (!DT.dominates(DominatingBlock, DominatedBlock))
522 return true;
523 // TODO: diamond, triangle cases
524 if (!PDT) return true;
525 return !PDT->dominates(DominatedBlock, DominatingBlock);
526 };
527
528 return MaybeHoistingToHotterBlock() ? WS_IllegalOrNegative : WS_Neutral;
529}
530
531bool GuardWideningImpl::canBeHoistedTo(
532 const Value *V, const Instruction *Loc,
534 auto *Inst = dyn_cast<Instruction>(V);
535 if (!Inst || DT.dominates(Inst, Loc) || Visited.count(Inst))
536 return true;
537
538 if (!isSafeToSpeculativelyExecute(Inst, Loc, &AC, &DT) ||
539 Inst->mayReadFromMemory())
540 return false;
541
542 Visited.insert(Inst);
543
544 // We only want to go _up_ the dominance chain when recursing.
545 assert(!isa<PHINode>(Loc) &&
546 "PHIs should return false for isSafeToSpeculativelyExecute");
547 assert(DT.isReachableFromEntry(Inst->getParent()) &&
548 "We did a DFS from the block entry!");
549 return all_of(Inst->operands(),
550 [&](Value *Op) { return canBeHoistedTo(Op, Loc, Visited); });
551}
552
553void GuardWideningImpl::makeAvailableAt(Value *V, Instruction *Loc) const {
554 auto *Inst = dyn_cast<Instruction>(V);
555 if (!Inst || DT.dominates(Inst, Loc))
556 return;
557
558 assert(isSafeToSpeculativelyExecute(Inst, Loc, &AC, &DT) &&
559 !Inst->mayReadFromMemory() &&
560 "Should've checked with canBeHoistedTo!");
561
562 for (Value *Op : Inst->operands())
563 makeAvailableAt(Op, Loc);
564
565 Inst->moveBefore(Loc);
566}
567
568// Return Instruction before which we can insert freeze for the value V as close
569// to def as possible. If there is no place to add freeze, return nullptr.
571 auto *I = dyn_cast<Instruction>(V);
572 if (!I)
573 return &*DT.getRoot()->getFirstNonPHIOrDbgOrAlloca();
574
575 auto *Res = I->getInsertionPointAfterDef();
576 // If there is no place to add freeze - return nullptr.
577 if (!Res || !DT.dominates(I, Res))
578 return nullptr;
579
580 // If there is a User dominated by original I, then it should be dominated
581 // by Freeze instruction as well.
582 if (any_of(I->users(), [&](User *U) {
583 Instruction *User = cast<Instruction>(U);
584 return Res != User && DT.dominates(I, User) && !DT.dominates(Res, User);
585 }))
586 return nullptr;
587 return Res;
588}
589
590Value *GuardWideningImpl::freezeAndPush(Value *Orig, Instruction *InsertPt) {
591 if (isGuaranteedNotToBePoison(Orig, nullptr, InsertPt, &DT))
592 return Orig;
593 Instruction *InsertPtAtDef = getFreezeInsertPt(Orig, DT);
594 if (!InsertPtAtDef)
595 return new FreezeInst(Orig, "gw.freeze", InsertPt);
596 SmallSet<Value *, 16> Visited;
598 SmallSet<Instruction *, 16> DropPoisonFlags;
599 SmallVector<Value *, 16> NeedFreeze;
600 Worklist.push_back(Orig);
601 while (!Worklist.empty()) {
602 Value *V = Worklist.pop_back_val();
603 if (!Visited.insert(V).second)
604 continue;
605
606 if (isGuaranteedNotToBePoison(V, nullptr, InsertPt, &DT))
607 continue;
608
609 Instruction *I = dyn_cast<Instruction>(V);
610 if (!I || canCreateUndefOrPoison(cast<Operator>(I),
611 /*ConsiderFlagsAndMetadata*/ false)) {
612 NeedFreeze.push_back(V);
613 continue;
614 }
615 // Check all operands. If for any of them we cannot insert Freeze,
616 // stop here. Otherwise, iterate.
617 if (any_of(I->operands(), [&](Value *Op) {
618 return isa<Instruction>(Op) && !getFreezeInsertPt(Op, DT);
619 })) {
620 NeedFreeze.push_back(I);
621 continue;
622 }
623 DropPoisonFlags.insert(I);
624 append_range(Worklist, I->operands());
625 }
626 for (Instruction *I : DropPoisonFlags)
627 I->dropPoisonGeneratingFlagsAndMetadata();
628
629 Value *Result = Orig;
630 for (Value *V : NeedFreeze) {
631 auto *FreezeInsertPt = getFreezeInsertPt(V, DT);
632 FreezeInst *FI = new FreezeInst(V, V->getName() + ".gw.fr", FreezeInsertPt);
633 ++FreezeAdded;
634 if (V == Orig)
635 Result = FI;
636 V->replaceUsesWithIf(FI, [&](Use & U)->bool { return U.getUser() != FI; });
637 }
638
639 return Result;
640}
641
642bool GuardWideningImpl::widenCondCommon(Value *Cond0, Value *Cond1,
643 Instruction *InsertPt, Value *&Result,
644 bool InvertCondition) {
645 using namespace llvm::PatternMatch;
646
647 {
648 // L >u C0 && L >u C1 -> L >u max(C0, C1)
649 ConstantInt *RHS0, *RHS1;
650 Value *LHS;
651 ICmpInst::Predicate Pred0, Pred1;
652 if (match(Cond0, m_ICmp(Pred0, m_Value(LHS), m_ConstantInt(RHS0))) &&
653 match(Cond1, m_ICmp(Pred1, m_Specific(LHS), m_ConstantInt(RHS1)))) {
654 if (InvertCondition)
655 Pred1 = ICmpInst::getInversePredicate(Pred1);
656
657 ConstantRange CR0 =
659 ConstantRange CR1 =
661
662 // Given what we're doing here and the semantics of guards, it would
663 // be correct to use a subset intersection, but that may be too
664 // aggressive in cases we care about.
665 if (std::optional<ConstantRange> Intersect =
666 CR0.exactIntersectWith(CR1)) {
667 APInt NewRHSAP;
669 if (Intersect->getEquivalentICmp(Pred, NewRHSAP)) {
670 if (InsertPt) {
671 ConstantInt *NewRHS =
672 ConstantInt::get(Cond0->getContext(), NewRHSAP);
673 assert(canBeHoistedTo(LHS, InsertPt) && "must be");
674 makeAvailableAt(LHS, InsertPt);
675 Result = new ICmpInst(InsertPt, Pred, LHS, NewRHS, "wide.chk");
676 }
677 return true;
678 }
679 }
680 }
681 }
682
683 {
685 // TODO: Support InvertCondition case?
686 if (!InvertCondition &&
687 parseRangeChecks(Cond0, Checks) && parseRangeChecks(Cond1, Checks) &&
688 combineRangeChecks(Checks, CombinedChecks)) {
689 if (InsertPt) {
690 Result = nullptr;
691 for (auto &RC : CombinedChecks) {
692 makeAvailableAt(RC.getCheckInst(), InsertPt);
693 if (Result)
694 Result = BinaryOperator::CreateAnd(RC.getCheckInst(), Result, "",
695 InsertPt);
696 else
697 Result = RC.getCheckInst();
698 }
699 assert(Result && "Failed to find result value");
700 Result->setName("wide.chk");
701 Result = freezeAndPush(Result, InsertPt);
702 }
703 return true;
704 }
705 }
706
707 // Base case -- just logical-and the two conditions together.
708
709 if (InsertPt) {
710 makeAvailableAt(Cond0, InsertPt);
711 makeAvailableAt(Cond1, InsertPt);
712 if (InvertCondition)
713 Cond1 = BinaryOperator::CreateNot(Cond1, "inverted", InsertPt);
714 Cond1 = freezeAndPush(Cond1, InsertPt);
715 Result = BinaryOperator::CreateAnd(Cond0, Cond1, "wide.chk", InsertPt);
716 }
717
718 // We were not able to compute Cond0 AND Cond1 for the price of one.
719 return false;
720}
721
722bool GuardWideningImpl::parseRangeChecks(
725 if (!Visited.insert(CheckCond).second)
726 return true;
727
728 using namespace llvm::PatternMatch;
729
730 {
731 Value *AndLHS, *AndRHS;
732 if (match(CheckCond, m_And(m_Value(AndLHS), m_Value(AndRHS))))
733 return parseRangeChecks(AndLHS, Checks) &&
734 parseRangeChecks(AndRHS, Checks);
735 }
736
737 auto *IC = dyn_cast<ICmpInst>(CheckCond);
738 if (!IC || !IC->getOperand(0)->getType()->isIntegerTy() ||
739 (IC->getPredicate() != ICmpInst::ICMP_ULT &&
740 IC->getPredicate() != ICmpInst::ICMP_UGT))
741 return false;
742
743 const Value *CmpLHS = IC->getOperand(0), *CmpRHS = IC->getOperand(1);
744 if (IC->getPredicate() == ICmpInst::ICMP_UGT)
745 std::swap(CmpLHS, CmpRHS);
746
747 auto &DL = IC->getModule()->getDataLayout();
748
749 GuardWideningImpl::RangeCheck Check(
750 CmpLHS, cast<ConstantInt>(ConstantInt::getNullValue(CmpRHS->getType())),
751 CmpRHS, IC);
752
753 if (!isKnownNonNegative(Check.getLength(), DL))
754 return false;
755
756 // What we have in \c Check now is a correct interpretation of \p CheckCond.
757 // Try to see if we can move some constant offsets into the \c Offset field.
758
759 bool Changed;
760 auto &Ctx = CheckCond->getContext();
761
762 do {
763 Value *OpLHS;
764 ConstantInt *OpRHS;
765 Changed = false;
766
767#ifndef NDEBUG
768 auto *BaseInst = dyn_cast<Instruction>(Check.getBase());
769 assert((!BaseInst || DT.isReachableFromEntry(BaseInst->getParent())) &&
770 "Unreachable instruction?");
771#endif
772
773 if (match(Check.getBase(), m_Add(m_Value(OpLHS), m_ConstantInt(OpRHS)))) {
774 Check.setBase(OpLHS);
775 APInt NewOffset = Check.getOffsetValue() + OpRHS->getValue();
776 Check.setOffset(ConstantInt::get(Ctx, NewOffset));
777 Changed = true;
778 } else if (match(Check.getBase(),
779 m_Or(m_Value(OpLHS), m_ConstantInt(OpRHS)))) {
780 KnownBits Known = computeKnownBits(OpLHS, DL);
781 if ((OpRHS->getValue() & Known.Zero) == OpRHS->getValue()) {
782 Check.setBase(OpLHS);
783 APInt NewOffset = Check.getOffsetValue() + OpRHS->getValue();
784 Check.setOffset(ConstantInt::get(Ctx, NewOffset));
785 Changed = true;
786 }
787 }
788 } while (Changed);
789
790 Checks.push_back(Check);
791 return true;
792}
793
794bool GuardWideningImpl::combineRangeChecks(
797 unsigned OldCount = Checks.size();
798 while (!Checks.empty()) {
799 // Pick all of the range checks with a specific base and length, and try to
800 // merge them.
801 const Value *CurrentBase = Checks.front().getBase();
802 const Value *CurrentLength = Checks.front().getLength();
803
805
806 auto IsCurrentCheck = [&](GuardWideningImpl::RangeCheck &RC) {
807 return RC.getBase() == CurrentBase && RC.getLength() == CurrentLength;
808 };
809
810 copy_if(Checks, std::back_inserter(CurrentChecks), IsCurrentCheck);
811 erase_if(Checks, IsCurrentCheck);
812
813 assert(CurrentChecks.size() != 0 && "We know we have at least one!");
814
815 if (CurrentChecks.size() < 3) {
816 llvm::append_range(RangeChecksOut, CurrentChecks);
817 continue;
818 }
819
820 // CurrentChecks.size() will typically be 3 here, but so far there has been
821 // no need to hard-code that fact.
822
823 llvm::sort(CurrentChecks, [&](const GuardWideningImpl::RangeCheck &LHS,
824 const GuardWideningImpl::RangeCheck &RHS) {
825 return LHS.getOffsetValue().slt(RHS.getOffsetValue());
826 });
827
828 // Note: std::sort should not invalidate the ChecksStart iterator.
829
830 const ConstantInt *MinOffset = CurrentChecks.front().getOffset();
831 const ConstantInt *MaxOffset = CurrentChecks.back().getOffset();
832
833 unsigned BitWidth = MaxOffset->getValue().getBitWidth();
834 if ((MaxOffset->getValue() - MinOffset->getValue())
836 return false;
837
838 APInt MaxDiff = MaxOffset->getValue() - MinOffset->getValue();
839 const APInt &HighOffset = MaxOffset->getValue();
840 auto OffsetOK = [&](const GuardWideningImpl::RangeCheck &RC) {
841 return (HighOffset - RC.getOffsetValue()).ult(MaxDiff);
842 };
843
844 if (MaxDiff.isMinValue() || !all_of(drop_begin(CurrentChecks), OffsetOK))
845 return false;
846
847 // We have a series of f+1 checks as:
848 //
849 // I+k_0 u< L ... Chk_0
850 // I+k_1 u< L ... Chk_1
851 // ...
852 // I+k_f u< L ... Chk_f
853 //
854 // with forall i in [0,f]: k_f-k_i u< k_f-k_0 ... Precond_0
855 // k_f-k_0 u< INT_MIN+k_f ... Precond_1
856 // k_f != k_0 ... Precond_2
857 //
858 // Claim:
859 // Chk_0 AND Chk_f implies all the other checks
860 //
861 // Informal proof sketch:
862 //
863 // We will show that the integer range [I+k_0,I+k_f] does not unsigned-wrap
864 // (i.e. going from I+k_0 to I+k_f does not cross the -1,0 boundary) and
865 // thus I+k_f is the greatest unsigned value in that range.
866 //
867 // This combined with Ckh_(f+1) shows that everything in that range is u< L.
868 // Via Precond_0 we know that all of the indices in Chk_0 through Chk_(f+1)
869 // lie in [I+k_0,I+k_f], this proving our claim.
870 //
871 // To see that [I+k_0,I+k_f] is not a wrapping range, note that there are
872 // two possibilities: I+k_0 u< I+k_f or I+k_0 >u I+k_f (they can't be equal
873 // since k_0 != k_f). In the former case, [I+k_0,I+k_f] is not a wrapping
874 // range by definition, and the latter case is impossible:
875 //
876 // 0-----I+k_f---I+k_0----L---INT_MAX,INT_MIN------------------(-1)
877 // xxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
878 //
879 // For Chk_0 to succeed, we'd have to have k_f-k_0 (the range highlighted
880 // with 'x' above) to be at least >u INT_MIN.
881
882 RangeChecksOut.emplace_back(CurrentChecks.front());
883 RangeChecksOut.emplace_back(CurrentChecks.back());
884 }
885
886 assert(RangeChecksOut.size() <= OldCount && "We pessimized!");
887 return RangeChecksOut.size() != OldCount;
888}
889
890#ifndef NDEBUG
891StringRef GuardWideningImpl::scoreTypeToString(WideningScore WS) {
892 switch (WS) {
893 case WS_IllegalOrNegative:
894 return "IllegalOrNegative";
895 case WS_Neutral:
896 return "Neutral";
897 case WS_Positive:
898 return "Positive";
899 case WS_VeryPositive:
900 return "VeryPositive";
901 }
902
903 llvm_unreachable("Fully covered switch above!");
904}
905#endif
906
909 auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
910 auto &LI = AM.getResult<LoopAnalysis>(F);
911 auto &PDT = AM.getResult<PostDominatorTreeAnalysis>(F);
912 auto &AC = AM.getResult<AssumptionAnalysis>(F);
913 auto *MSSAA = AM.getCachedResult<MemorySSAAnalysis>(F);
914 std::unique_ptr<MemorySSAUpdater> MSSAU;
915 if (MSSAA)
916 MSSAU = std::make_unique<MemorySSAUpdater>(&MSSAA->getMSSA());
917 if (!GuardWideningImpl(DT, &PDT, LI, AC, MSSAU ? MSSAU.get() : nullptr,
918 DT.getRootNode(), [](BasicBlock *) { return true; })
919 .run())
920 return PreservedAnalyses::all();
921
925 return PA;
926}
927
930 LPMUpdater &U) {
931 BasicBlock *RootBB = L.getLoopPredecessor();
932 if (!RootBB)
933 RootBB = L.getHeader();
934 auto BlockFilter = [&](BasicBlock *BB) {
935 return BB == RootBB || L.contains(BB);
936 };
937 std::unique_ptr<MemorySSAUpdater> MSSAU;
938 if (AR.MSSA)
939 MSSAU = std::make_unique<MemorySSAUpdater>(AR.MSSA);
940 if (!GuardWideningImpl(AR.DT, nullptr, AR.LI, AR.AC,
941 MSSAU ? MSSAU.get() : nullptr, AR.DT.getNode(RootBB),
942 BlockFilter)
943 .run())
944 return PreservedAnalyses::all();
945
947 if (AR.MSSA)
948 PA.preserve<MemorySSAAnalysis>();
949 return PA;
950}
951
952namespace {
953struct GuardWideningLegacyPass : public FunctionPass {
954 static char ID;
955
956 GuardWideningLegacyPass() : FunctionPass(ID) {
958 }
959
960 bool runOnFunction(Function &F) override {
961 if (skipFunction(F))
962 return false;
963 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
964 auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
965 auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
966 auto &PDT = getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();
967 auto *MSSAWP = getAnalysisIfAvailable<MemorySSAWrapperPass>();
968 std::unique_ptr<MemorySSAUpdater> MSSAU;
969 if (MSSAWP)
970 MSSAU = std::make_unique<MemorySSAUpdater>(&MSSAWP->getMSSA());
971 return GuardWideningImpl(DT, &PDT, LI, AC, MSSAU ? MSSAU.get() : nullptr,
972 DT.getRootNode(),
973 [](BasicBlock *) { return true; })
974 .run();
975 }
976
977 void getAnalysisUsage(AnalysisUsage &AU) const override {
978 AU.setPreservesCFG();
983 }
984};
985
986/// Same as above, but restricted to a single loop at a time. Can be
987/// scheduled with other loop passes w/o breaking out of LPM
988struct LoopGuardWideningLegacyPass : public LoopPass {
989 static char ID;
990
991 LoopGuardWideningLegacyPass() : LoopPass(ID) {
993 }
994
995 bool runOnLoop(Loop *L, LPPassManager &LPM) override {
996 if (skipLoop(L))
997 return false;
998 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
999 auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
1000 auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
1001 *L->getHeader()->getParent());
1002 auto *PDTWP = getAnalysisIfAvailable<PostDominatorTreeWrapperPass>();
1003 auto *PDT = PDTWP ? &PDTWP->getPostDomTree() : nullptr;
1004 auto *MSSAWP = getAnalysisIfAvailable<MemorySSAWrapperPass>();
1005 std::unique_ptr<MemorySSAUpdater> MSSAU;
1006 if (MSSAWP)
1007 MSSAU = std::make_unique<MemorySSAUpdater>(&MSSAWP->getMSSA());
1008
1009 BasicBlock *RootBB = L->getLoopPredecessor();
1010 if (!RootBB)
1011 RootBB = L->getHeader();
1012 auto BlockFilter = [&](BasicBlock *BB) {
1013 return BB == RootBB || L->contains(BB);
1014 };
1015 return GuardWideningImpl(DT, PDT, LI, AC, MSSAU ? MSSAU.get() : nullptr,
1016 DT.getNode(RootBB), BlockFilter)
1017 .run();
1018 }
1019
1020 void getAnalysisUsage(AnalysisUsage &AU) const override {
1021 AU.setPreservesCFG();
1025 }
1026};
1027}
1028
1029char GuardWideningLegacyPass::ID = 0;
1030char LoopGuardWideningLegacyPass::ID = 0;
1031
1032INITIALIZE_PASS_BEGIN(GuardWideningLegacyPass, "guard-widening", "Widen guards",
1033 false, false)
1037INITIALIZE_PASS_END(GuardWideningLegacyPass, "guard-widening", "Widen guards",
1039
1040INITIALIZE_PASS_BEGIN(LoopGuardWideningLegacyPass, "loop-guard-widening",
1041 "Widen guards (within a single loop, as a loop pass)",
1042 false, false)
1046INITIALIZE_PASS_END(LoopGuardWideningLegacyPass, "loop-guard-widening",
1047 "Widen guards (within a single loop, as a loop pass)",
1048 false, false)
1049
1051 return new GuardWideningLegacyPass();
1052}
1053
1055 return new LoopGuardWideningLegacyPass();
1056}
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 Instruction * getFreezeInsertPt(Value *V, const DominatorTree &DT)
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_iterator getFirstNonPHIOrDbgOrAlloca() const
Returns an iterator to the first instruction in this block that is not a PHINode, a debug intrinsic,...
Definition: BasicBlock.cpp:264
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.
NodeT * getRoot() const
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
This class represents a freeze function that returns random concrete value if an operand is either a ...
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
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:135
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
Definition: SmallSet.h:179
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
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
LLVM Value Representation.
Definition: Value.h:74
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:996
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)
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1826
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
bool canCreateUndefOrPoison(const Operator *Op, bool ConsiderFlagsAndMetadata=true)
canCreateUndefOrPoison returns true if Op can create undef or poison from non-undef & non-poison oper...
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)
bool isGuaranteedNotToBePoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
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...