LLVM 19.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"
52#include "llvm/IR/Dominators.h"
53#include "llvm/IR/IRBuilder.h"
55#include "llvm/IR/Module.h"
58#include "llvm/Support/Debug.h"
63#include <functional>
64
65using namespace llvm;
66
67#define DEBUG_TYPE "guard-widening"
68
69STATISTIC(GuardsEliminated, "Number of eliminated guards");
70STATISTIC(CondBranchEliminated, "Number of eliminated conditional branches");
71STATISTIC(FreezeAdded, "Number of freeze instruction introduced");
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 std::optional<BasicBlock::iterator>
126findInsertionPointForWideCondition(Instruction *WCOrGuard) {
127 if (isGuard(WCOrGuard))
128 return WCOrGuard->getIterator();
129 if (auto WC = extractWidenableCondition(WCOrGuard))
130 return cast<Instruction>(WC)->getIterator();
131 return std::nullopt;
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);
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 WideningPoint.
185 WideningScore computeWideningScore(Instruction *DominatedInstr,
186 Instruction *ToWiden,
187 BasicBlock::iterator WideningPoint,
188 SmallVectorImpl<Value *> &ChecksToHoist,
189 SmallVectorImpl<Value *> &ChecksToWiden);
190
191 /// Helper to check if \p V can be hoisted to \p InsertPos.
192 bool canBeHoistedTo(const Value *V, BasicBlock::iterator InsertPos) const {
194 return canBeHoistedTo(V, InsertPos, Visited);
195 }
196
197 bool canBeHoistedTo(const Value *V, BasicBlock::iterator InsertPos,
199
200 bool canBeHoistedTo(const SmallVectorImpl<Value *> &Checks,
201 BasicBlock::iterator InsertPos) const {
202 return all_of(Checks,
203 [&](const Value *V) { return canBeHoistedTo(V, InsertPos); });
204 }
205 /// Helper to hoist \p V to \p InsertPos. Guaranteed to succeed if \c
206 /// canBeHoistedTo returned true.
207 void makeAvailableAt(Value *V, BasicBlock::iterator InsertPos) const;
208
209 void makeAvailableAt(const SmallVectorImpl<Value *> &Checks,
210 BasicBlock::iterator InsertPos) const {
211 for (Value *V : Checks)
212 makeAvailableAt(V, InsertPos);
213 }
214
215 /// Common helper used by \c widenGuard and \c isWideningCondProfitable. Try
216 /// to generate an expression computing the logical AND of \p ChecksToHoist
217 /// and \p ChecksToWiden. Return true if the expression computing the AND is
218 /// only as expensive as computing one of the set of expressions. If \p
219 /// InsertPt is true then actually generate the resulting expression, make it
220 /// available at \p InsertPt and return it in \p Result (else no change to the
221 /// IR is made).
222 std::optional<Value *>
223 mergeChecks(SmallVectorImpl<Value *> &ChecksToHoist,
224 SmallVectorImpl<Value *> &ChecksToWiden,
225 std::optional<BasicBlock::iterator> InsertPt);
226
227 /// Generate the logical AND of \p ChecksToHoist and \p OldCondition and make
228 /// it available at InsertPt
229 Value *hoistChecks(SmallVectorImpl<Value *> &ChecksToHoist,
230 Value *OldCondition, BasicBlock::iterator InsertPt);
231
232 /// Adds freeze to Orig and push it as far as possible very aggressively.
233 /// Also replaces all uses of frozen instruction with frozen version.
234 Value *freezeAndPush(Value *Orig, BasicBlock::iterator InsertPt);
235
236 /// Represents a range check of the form \c Base + \c Offset u< \c Length,
237 /// with the constraint that \c Length is not negative. \c CheckInst is the
238 /// pre-existing instruction in the IR that computes the result of this range
239 /// check.
240 class RangeCheck {
241 const Value *Base;
242 const ConstantInt *Offset;
243 const Value *Length;
244 ICmpInst *CheckInst;
245
246 public:
247 explicit RangeCheck(const Value *Base, const ConstantInt *Offset,
248 const Value *Length, ICmpInst *CheckInst)
249 : Base(Base), Offset(Offset), Length(Length), CheckInst(CheckInst) {}
250
251 void setBase(const Value *NewBase) { Base = NewBase; }
252 void setOffset(const ConstantInt *NewOffset) { Offset = NewOffset; }
253
254 const Value *getBase() const { return Base; }
255 const ConstantInt *getOffset() const { return Offset; }
256 const APInt &getOffsetValue() const { return getOffset()->getValue(); }
257 const Value *getLength() const { return Length; };
258 ICmpInst *getCheckInst() const { return CheckInst; }
259
260 void print(raw_ostream &OS, bool PrintTypes = false) {
261 OS << "Base: ";
262 Base->printAsOperand(OS, PrintTypes);
263 OS << " Offset: ";
264 Offset->printAsOperand(OS, PrintTypes);
265 OS << " Length: ";
266 Length->printAsOperand(OS, PrintTypes);
267 }
268
269 LLVM_DUMP_METHOD void dump() {
270 print(dbgs());
271 dbgs() << "\n";
272 }
273 };
274
275 /// Parse \p ToParse into a conjunction (logical-and) of range checks; and
276 /// append them to \p Checks. Returns true on success, may clobber \c Checks
277 /// on failure.
278 bool parseRangeChecks(SmallVectorImpl<Value *> &ToParse,
280 for (auto CheckCond : ToParse) {
281 if (!parseRangeChecks(CheckCond, Checks))
282 return false;
283 }
284 return true;
285 }
286
287 bool parseRangeChecks(Value *CheckCond, SmallVectorImpl<RangeCheck> &Checks);
288
289 /// Combine the checks in \p Checks into a smaller set of checks and append
290 /// them into \p CombinedChecks. Return true on success (i.e. all of checks
291 /// in \p Checks were combined into \p CombinedChecks). Clobbers \p Checks
292 /// and \p CombinedChecks on success and on failure.
293 bool combineRangeChecks(SmallVectorImpl<RangeCheck> &Checks,
294 SmallVectorImpl<RangeCheck> &CombinedChecks) const;
295
296 /// Can we compute the logical AND of \p ChecksToHoist and \p ChecksToWiden
297 /// for the price of computing only one of the set of expressions?
298 bool isWideningCondProfitable(SmallVectorImpl<Value *> &ChecksToHoist,
299 SmallVectorImpl<Value *> &ChecksToWiden) {
300 return mergeChecks(ChecksToHoist, ChecksToWiden, /*InsertPt=*/std::nullopt)
301 .has_value();
302 }
303
304 /// Widen \p ChecksToWiden to fail if any of \p ChecksToHoist is false
305 void widenGuard(SmallVectorImpl<Value *> &ChecksToHoist,
306 SmallVectorImpl<Value *> &ChecksToWiden,
307 Instruction *ToWiden) {
308 auto InsertPt = findInsertionPointForWideCondition(ToWiden);
309 auto MergedCheck = mergeChecks(ChecksToHoist, ChecksToWiden, InsertPt);
310 Value *Result = MergedCheck ? *MergedCheck
311 : hoistChecks(ChecksToHoist,
312 getCondition(ToWiden), *InsertPt);
313
314 if (isGuardAsWidenableBranch(ToWiden)) {
315 setWidenableBranchCond(cast<BranchInst>(ToWiden), Result);
316 return;
317 }
318 setCondition(ToWiden, Result);
319 }
320
321public:
322 explicit GuardWideningImpl(DominatorTree &DT, PostDominatorTree *PDT,
323 LoopInfo &LI, AssumptionCache &AC,
324 MemorySSAUpdater *MSSAU, DomTreeNode *Root,
325 std::function<bool(BasicBlock *)> BlockFilter)
326 : DT(DT), PDT(PDT), LI(LI), AC(AC), MSSAU(MSSAU), Root(Root),
327 BlockFilter(BlockFilter) {}
328
329 /// The entry point for this pass.
330 bool run();
331};
332}
333
335 if (isGuard(Insn))
336 return true;
338 return true;
339 return false;
340}
341
342bool GuardWideningImpl::run() {
344 bool Changed = false;
345 for (auto DFI = df_begin(Root), DFE = df_end(Root);
346 DFI != DFE; ++DFI) {
347 auto *BB = (*DFI)->getBlock();
348 if (!BlockFilter(BB))
349 continue;
350
351 auto &CurrentList = GuardsInBlock[BB];
352
353 for (auto &I : *BB)
355 CurrentList.push_back(cast<Instruction>(&I));
356
357 for (auto *II : CurrentList)
358 Changed |= eliminateInstrViaWidening(II, DFI, GuardsInBlock);
359 }
360
361 assert(EliminatedGuardsAndBranches.empty() || Changed);
362 for (auto *I : EliminatedGuardsAndBranches)
363 if (!WidenedGuards.count(I)) {
364 assert(isa<ConstantInt>(getCondition(I)) && "Should be!");
366 eliminateGuard(I, MSSAU);
367 else {
368 assert(isa<BranchInst>(I) &&
369 "Eliminated something other than guard or branch?");
370 ++CondBranchEliminated;
371 }
372 }
373
374 return Changed;
375}
376
377bool GuardWideningImpl::eliminateInstrViaWidening(
378 Instruction *Instr, const df_iterator<DomTreeNode *> &DFSI,
380 &GuardsInBlock) {
381 SmallVector<Value *> ChecksToHoist;
382 parseWidenableGuard(Instr, ChecksToHoist);
383 // Ignore trivial true or false conditions. These instructions will be
384 // trivially eliminated by any cleanup pass. Do not erase them because other
385 // guards can possibly be widened into them.
386 if (ChecksToHoist.empty() ||
387 (ChecksToHoist.size() == 1 && isa<ConstantInt>(ChecksToHoist.front())))
388 return false;
389
390 Instruction *BestSoFar = nullptr;
391 auto BestScoreSoFar = WS_IllegalOrNegative;
392
393 // In the set of dominating guards, find the one we can merge GuardInst with
394 // for the most profit.
395 for (unsigned i = 0, e = DFSI.getPathLength(); i != e; ++i) {
396 auto *CurBB = DFSI.getPath(i)->getBlock();
397 if (!BlockFilter(CurBB))
398 break;
399 assert(GuardsInBlock.count(CurBB) && "Must have been populated by now!");
400 const auto &GuardsInCurBB = GuardsInBlock.find(CurBB)->second;
401
402 auto I = GuardsInCurBB.begin();
403 auto E = Instr->getParent() == CurBB ? find(GuardsInCurBB, Instr)
404 : GuardsInCurBB.end();
405
406#ifndef NDEBUG
407 {
408 unsigned Index = 0;
409 for (auto &I : *CurBB) {
410 if (Index == GuardsInCurBB.size())
411 break;
412 if (GuardsInCurBB[Index] == &I)
413 Index++;
414 }
415 assert(Index == GuardsInCurBB.size() &&
416 "Guards expected to be in order!");
417 }
418#endif
419
420 assert((i == (e - 1)) == (Instr->getParent() == CurBB) && "Bad DFS?");
421
422 for (auto *Candidate : make_range(I, E)) {
423 auto WideningPoint = findInsertionPointForWideCondition(Candidate);
424 if (!WideningPoint)
425 continue;
426 SmallVector<Value *> CandidateChecks;
427 parseWidenableGuard(Candidate, CandidateChecks);
428 auto Score = computeWideningScore(Instr, Candidate, *WideningPoint,
429 ChecksToHoist, CandidateChecks);
430 LLVM_DEBUG(dbgs() << "Score between " << *Instr << " and " << *Candidate
431 << " is " << scoreTypeToString(Score) << "\n");
432 if (Score > BestScoreSoFar) {
433 BestScoreSoFar = Score;
434 BestSoFar = Candidate;
435 }
436 }
437 }
438
439 if (BestScoreSoFar == WS_IllegalOrNegative) {
440 LLVM_DEBUG(dbgs() << "Did not eliminate guard " << *Instr << "\n");
441 return false;
442 }
443
444 assert(BestSoFar != Instr && "Should have never visited same guard!");
445 assert(DT.dominates(BestSoFar, Instr) && "Should be!");
446
447 LLVM_DEBUG(dbgs() << "Widening " << *Instr << " into " << *BestSoFar
448 << " with score " << scoreTypeToString(BestScoreSoFar)
449 << "\n");
450 SmallVector<Value *> ChecksToWiden;
451 parseWidenableGuard(BestSoFar, ChecksToWiden);
452 widenGuard(ChecksToHoist, ChecksToWiden, BestSoFar);
453 auto NewGuardCondition = ConstantInt::getTrue(Instr->getContext());
454 setCondition(Instr, NewGuardCondition);
455 EliminatedGuardsAndBranches.push_back(Instr);
456 WidenedGuards.insert(BestSoFar);
457 return true;
458}
459
460GuardWideningImpl::WideningScore GuardWideningImpl::computeWideningScore(
461 Instruction *DominatedInstr, Instruction *ToWiden,
462 BasicBlock::iterator WideningPoint, SmallVectorImpl<Value *> &ChecksToHoist,
463 SmallVectorImpl<Value *> &ChecksToWiden) {
464 Loop *DominatedInstrLoop = LI.getLoopFor(DominatedInstr->getParent());
465 Loop *DominatingGuardLoop = LI.getLoopFor(WideningPoint->getParent());
466 bool HoistingOutOfLoop = false;
467
468 if (DominatingGuardLoop != DominatedInstrLoop) {
469 // Be conservative and don't widen into a sibling loop. TODO: If the
470 // sibling is colder, we should consider allowing this.
471 if (DominatingGuardLoop &&
472 !DominatingGuardLoop->contains(DominatedInstrLoop))
473 return WS_IllegalOrNegative;
474
475 HoistingOutOfLoop = true;
476 }
477
478 if (!canBeHoistedTo(ChecksToHoist, WideningPoint))
479 return WS_IllegalOrNegative;
480 // Further in the GuardWideningImpl::hoistChecks the entire condition might be
481 // widened, not the parsed list of checks. So we need to check the possibility
482 // of that condition hoisting.
483 if (!canBeHoistedTo(getCondition(ToWiden), WideningPoint))
484 return WS_IllegalOrNegative;
485
486 // If the guard was conditional executed, it may never be reached
487 // dynamically. There are two potential downsides to hoisting it out of the
488 // conditionally executed region: 1) we may spuriously deopt without need and
489 // 2) we have the extra cost of computing the guard condition in the common
490 // case. At the moment, we really only consider the second in our heuristic
491 // here. TODO: evaluate cost model for spurious deopt
492 // NOTE: As written, this also lets us hoist right over another guard which
493 // is essentially just another spelling for control flow.
494 if (isWideningCondProfitable(ChecksToHoist, ChecksToWiden))
495 return HoistingOutOfLoop ? WS_VeryPositive : WS_Positive;
496
497 if (HoistingOutOfLoop)
498 return WS_Positive;
499
500 // For a given basic block \p BB, return its successor which is guaranteed or
501 // highly likely will be taken as its successor.
502 auto GetLikelySuccessor = [](const BasicBlock * BB)->const BasicBlock * {
503 if (auto *UniqueSucc = BB->getUniqueSuccessor())
504 return UniqueSucc;
505 auto *Term = BB->getTerminator();
506 Value *Cond = nullptr;
507 const BasicBlock *IfTrue = nullptr, *IfFalse = nullptr;
508 using namespace PatternMatch;
509 if (!match(Term, m_Br(m_Value(Cond), m_BasicBlock(IfTrue),
510 m_BasicBlock(IfFalse))))
511 return nullptr;
512 // For constant conditions, only one dynamical successor is possible
513 if (auto *ConstCond = dyn_cast<ConstantInt>(Cond))
514 return ConstCond->isAllOnesValue() ? IfTrue : IfFalse;
515 // If one of successors ends with deopt, another one is likely.
516 if (IfFalse->getPostdominatingDeoptimizeCall())
517 return IfTrue;
519 return IfFalse;
520 // TODO: Use branch frequency metatada to allow hoisting through non-deopt
521 // branches?
522 return nullptr;
523 };
524
525 // Returns true if we might be hoisting above explicit control flow into a
526 // considerably hotter block. Note that this completely ignores implicit
527 // control flow (guards, calls which throw, etc...). That choice appears
528 // arbitrary (we assume that implicit control flow exits are all rare).
529 auto MaybeHoistingToHotterBlock = [&]() {
530 const auto *DominatingBlock = WideningPoint->getParent();
531 const auto *DominatedBlock = DominatedInstr->getParent();
532
533 // Descend as low as we can, always taking the likely successor.
534 assert(DT.isReachableFromEntry(DominatingBlock) && "Unreached code");
535 assert(DT.isReachableFromEntry(DominatedBlock) && "Unreached code");
536 assert(DT.dominates(DominatingBlock, DominatedBlock) && "No dominance");
537 while (DominatedBlock != DominatingBlock) {
538 auto *LikelySucc = GetLikelySuccessor(DominatingBlock);
539 // No likely successor?
540 if (!LikelySucc)
541 break;
542 // Only go down the dominator tree.
543 if (!DT.properlyDominates(DominatingBlock, LikelySucc))
544 break;
545 DominatingBlock = LikelySucc;
546 }
547
548 // Found?
549 if (DominatedBlock == DominatingBlock)
550 return false;
551 // We followed the likely successor chain and went past the dominated
552 // block. It means that the dominated guard is in dead/very cold code.
553 if (!DT.dominates(DominatingBlock, DominatedBlock))
554 return true;
555 // TODO: diamond, triangle cases
556 if (!PDT)
557 return true;
558 return !PDT->dominates(DominatedBlock, DominatingBlock);
559 };
560
561 return MaybeHoistingToHotterBlock() ? WS_IllegalOrNegative : WS_Neutral;
562}
563
564bool GuardWideningImpl::canBeHoistedTo(
565 const Value *V, BasicBlock::iterator Loc,
567 auto *Inst = dyn_cast<Instruction>(V);
568 if (!Inst || DT.dominates(Inst, Loc) || Visited.count(Inst))
569 return true;
570
571 if (!isSafeToSpeculativelyExecute(Inst, Loc, &AC, &DT) ||
572 Inst->mayReadFromMemory())
573 return false;
574
575 Visited.insert(Inst);
576
577 // We only want to go _up_ the dominance chain when recursing.
578 assert(!isa<PHINode>(Loc) &&
579 "PHIs should return false for isSafeToSpeculativelyExecute");
580 assert(DT.isReachableFromEntry(Inst->getParent()) &&
581 "We did a DFS from the block entry!");
582 return all_of(Inst->operands(),
583 [&](Value *Op) { return canBeHoistedTo(Op, Loc, Visited); });
584}
585
586void GuardWideningImpl::makeAvailableAt(Value *V,
587 BasicBlock::iterator Loc) const {
588 auto *Inst = dyn_cast<Instruction>(V);
589 if (!Inst || DT.dominates(Inst, Loc))
590 return;
591
592 assert(isSafeToSpeculativelyExecute(Inst, Loc, &AC, &DT) &&
593 !Inst->mayReadFromMemory() &&
594 "Should've checked with canBeHoistedTo!");
595
596 for (Value *Op : Inst->operands())
597 makeAvailableAt(Op, Loc);
598
599 Inst->moveBefore(*Loc->getParent(), Loc);
600}
601
602// Return Instruction before which we can insert freeze for the value V as close
603// to def as possible. If there is no place to add freeze, return empty.
604static std::optional<BasicBlock::iterator>
606 auto *I = dyn_cast<Instruction>(V);
607 if (!I)
608 return DT.getRoot()->getFirstNonPHIOrDbgOrAlloca()->getIterator();
609
610 std::optional<BasicBlock::iterator> Res = I->getInsertionPointAfterDef();
611 // If there is no place to add freeze - return nullptr.
612 if (!Res || !DT.dominates(I, &**Res))
613 return std::nullopt;
614
615 Instruction *ResInst = &**Res;
616
617 // If there is a User dominated by original I, then it should be dominated
618 // by Freeze instruction as well.
619 if (any_of(I->users(), [&](User *U) {
620 Instruction *User = cast<Instruction>(U);
621 return ResInst != User && DT.dominates(I, User) &&
622 !DT.dominates(ResInst, User);
623 }))
624 return std::nullopt;
625 return Res;
626}
627
628Value *GuardWideningImpl::freezeAndPush(Value *Orig,
629 BasicBlock::iterator InsertPt) {
630 if (isGuaranteedNotToBePoison(Orig, nullptr, InsertPt, &DT))
631 return Orig;
632 std::optional<BasicBlock::iterator> InsertPtAtDef =
633 getFreezeInsertPt(Orig, DT);
634 if (!InsertPtAtDef) {
635 FreezeInst *FI = new FreezeInst(Orig, "gw.freeze");
636 FI->insertBefore(*InsertPt->getParent(), InsertPt);
637 return FI;
638 }
639 if (isa<Constant>(Orig) || isa<GlobalValue>(Orig)) {
640 BasicBlock::iterator InsertPt = *InsertPtAtDef;
641 FreezeInst *FI = new FreezeInst(Orig, "gw.freeze");
642 FI->insertBefore(*InsertPt->getParent(), InsertPt);
643 return FI;
644 }
645
646 SmallSet<Value *, 16> Visited;
648 SmallSet<Instruction *, 16> DropPoisonFlags;
649 SmallVector<Value *, 16> NeedFreeze;
650 DenseMap<Value *, FreezeInst *> CacheOfFreezes;
651
652 // A bit overloaded data structures. Visited contains constant/GV
653 // if we already met it. In this case CacheOfFreezes has a freeze if it is
654 // required.
655 auto handleConstantOrGlobal = [&](Use &U) {
656 Value *Def = U.get();
657 if (!isa<Constant>(Def) && !isa<GlobalValue>(Def))
658 return false;
659
660 if (Visited.insert(Def).second) {
661 if (isGuaranteedNotToBePoison(Def, nullptr, InsertPt, &DT))
662 return true;
663 BasicBlock::iterator InsertPt = *getFreezeInsertPt(Def, DT);
664 FreezeInst *FI = new FreezeInst(Def, Def->getName() + ".gw.fr");
665 FI->insertBefore(*InsertPt->getParent(), InsertPt);
666 CacheOfFreezes[Def] = FI;
667 }
668
669 if (CacheOfFreezes.count(Def))
670 U.set(CacheOfFreezes[Def]);
671 return true;
672 };
673
674 Worklist.push_back(Orig);
675 while (!Worklist.empty()) {
676 Value *V = Worklist.pop_back_val();
677 if (!Visited.insert(V).second)
678 continue;
679
680 if (isGuaranteedNotToBePoison(V, nullptr, InsertPt, &DT))
681 continue;
682
683 Instruction *I = dyn_cast<Instruction>(V);
684 if (!I || canCreateUndefOrPoison(cast<Operator>(I),
685 /*ConsiderFlagsAndMetadata*/ false)) {
686 NeedFreeze.push_back(V);
687 continue;
688 }
689 // Check all operands. If for any of them we cannot insert Freeze,
690 // stop here. Otherwise, iterate.
691 if (any_of(I->operands(), [&](Value *Op) {
692 return isa<Instruction>(Op) && !getFreezeInsertPt(Op, DT);
693 })) {
694 NeedFreeze.push_back(I);
695 continue;
696 }
697 DropPoisonFlags.insert(I);
698 for (Use &U : I->operands())
699 if (!handleConstantOrGlobal(U))
700 Worklist.push_back(U.get());
701 }
702 for (Instruction *I : DropPoisonFlags)
703 I->dropPoisonGeneratingAnnotations();
704
705 Value *Result = Orig;
706 for (Value *V : NeedFreeze) {
707 BasicBlock::iterator FreezeInsertPt = *getFreezeInsertPt(V, DT);
708 FreezeInst *FI = new FreezeInst(V, V->getName() + ".gw.fr");
709 FI->insertBefore(*FreezeInsertPt->getParent(), FreezeInsertPt);
710 ++FreezeAdded;
711 if (V == Orig)
712 Result = FI;
713 V->replaceUsesWithIf(
714 FI, [&](const Use & U)->bool { return U.getUser() != FI; });
715 }
716
717 return Result;
718}
719
720std::optional<Value *>
721GuardWideningImpl::mergeChecks(SmallVectorImpl<Value *> &ChecksToHoist,
722 SmallVectorImpl<Value *> &ChecksToWiden,
723 std::optional<BasicBlock::iterator> InsertPt) {
724 using namespace llvm::PatternMatch;
725
726 Value *Result = nullptr;
727 {
728 // L >u C0 && L >u C1 -> L >u max(C0, C1)
729 ConstantInt *RHS0, *RHS1;
730 Value *LHS;
731 ICmpInst::Predicate Pred0, Pred1;
732 // TODO: Support searching for pairs to merge from both whole lists of
733 // ChecksToHoist and ChecksToWiden.
734 if (ChecksToWiden.size() == 1 && ChecksToHoist.size() == 1 &&
735 match(ChecksToWiden.front(),
736 m_ICmp(Pred0, m_Value(LHS), m_ConstantInt(RHS0))) &&
737 match(ChecksToHoist.front(),
738 m_ICmp(Pred1, m_Specific(LHS), m_ConstantInt(RHS1)))) {
739
740 ConstantRange CR0 =
742 ConstantRange CR1 =
744
745 // Given what we're doing here and the semantics of guards, it would
746 // be correct to use a subset intersection, but that may be too
747 // aggressive in cases we care about.
748 if (std::optional<ConstantRange> Intersect =
749 CR0.exactIntersectWith(CR1)) {
750 APInt NewRHSAP;
752 if (Intersect->getEquivalentICmp(Pred, NewRHSAP)) {
753 if (InsertPt) {
754 ConstantInt *NewRHS =
755 ConstantInt::get((*InsertPt)->getContext(), NewRHSAP);
756 assert(canBeHoistedTo(LHS, *InsertPt) && "must be");
757 makeAvailableAt(LHS, *InsertPt);
758 Result = new ICmpInst(*InsertPt, Pred, LHS, NewRHS, "wide.chk");
759 }
760 return Result;
761 }
762 }
763 }
764 }
765
766 {
768 if (parseRangeChecks(ChecksToWiden, Checks) &&
769 parseRangeChecks(ChecksToHoist, Checks) &&
770 combineRangeChecks(Checks, CombinedChecks)) {
771 if (InsertPt) {
772 for (auto &RC : CombinedChecks) {
773 makeAvailableAt(RC.getCheckInst(), *InsertPt);
774 if (Result)
775 Result = BinaryOperator::CreateAnd(RC.getCheckInst(), Result, "",
776 *InsertPt);
777 else
778 Result = RC.getCheckInst();
779 }
780 assert(Result && "Failed to find result value");
781 Result->setName("wide.chk");
782 Result = freezeAndPush(Result, *InsertPt);
783 }
784 return Result;
785 }
786 }
787 // We were not able to compute ChecksToHoist AND ChecksToWiden for the price
788 // of one.
789 return std::nullopt;
790}
791
792Value *GuardWideningImpl::hoistChecks(SmallVectorImpl<Value *> &ChecksToHoist,
793 Value *OldCondition,
794 BasicBlock::iterator InsertPt) {
795 assert(!ChecksToHoist.empty());
796 IRBuilder<> Builder(InsertPt->getParent(), InsertPt);
797 makeAvailableAt(ChecksToHoist, InsertPt);
798 makeAvailableAt(OldCondition, InsertPt);
799 Value *Result = Builder.CreateAnd(ChecksToHoist);
800 Result = freezeAndPush(Result, InsertPt);
801 Result = Builder.CreateAnd(OldCondition, Result);
802 Result->setName("wide.chk");
803 return Result;
804}
805
806bool GuardWideningImpl::parseRangeChecks(
808 using namespace llvm::PatternMatch;
809
810 auto *IC = dyn_cast<ICmpInst>(CheckCond);
811 if (!IC || !IC->getOperand(0)->getType()->isIntegerTy() ||
812 (IC->getPredicate() != ICmpInst::ICMP_ULT &&
813 IC->getPredicate() != ICmpInst::ICMP_UGT))
814 return false;
815
816 const Value *CmpLHS = IC->getOperand(0), *CmpRHS = IC->getOperand(1);
817 if (IC->getPredicate() == ICmpInst::ICMP_UGT)
818 std::swap(CmpLHS, CmpRHS);
819
820 auto &DL = IC->getDataLayout();
821
822 GuardWideningImpl::RangeCheck Check(
823 CmpLHS, cast<ConstantInt>(ConstantInt::getNullValue(CmpRHS->getType())),
824 CmpRHS, IC);
825
826 if (!isKnownNonNegative(Check.getLength(), DL))
827 return false;
828
829 // What we have in \c Check now is a correct interpretation of \p CheckCond.
830 // Try to see if we can move some constant offsets into the \c Offset field.
831
832 bool Changed;
833 auto &Ctx = CheckCond->getContext();
834
835 do {
836 Value *OpLHS;
837 ConstantInt *OpRHS;
838 Changed = false;
839
840#ifndef NDEBUG
841 auto *BaseInst = dyn_cast<Instruction>(Check.getBase());
842 assert((!BaseInst || DT.isReachableFromEntry(BaseInst->getParent())) &&
843 "Unreachable instruction?");
844#endif
845
846 if (match(Check.getBase(), m_Add(m_Value(OpLHS), m_ConstantInt(OpRHS)))) {
847 Check.setBase(OpLHS);
848 APInt NewOffset = Check.getOffsetValue() + OpRHS->getValue();
849 Check.setOffset(ConstantInt::get(Ctx, NewOffset));
850 Changed = true;
851 } else if (match(Check.getBase(),
852 m_Or(m_Value(OpLHS), m_ConstantInt(OpRHS)))) {
853 KnownBits Known = computeKnownBits(OpLHS, DL);
854 if ((OpRHS->getValue() & Known.Zero) == OpRHS->getValue()) {
855 Check.setBase(OpLHS);
856 APInt NewOffset = Check.getOffsetValue() + OpRHS->getValue();
857 Check.setOffset(ConstantInt::get(Ctx, NewOffset));
858 Changed = true;
859 }
860 }
861 } while (Changed);
862
863 Checks.push_back(Check);
864 return true;
865}
866
867bool GuardWideningImpl::combineRangeChecks(
870 unsigned OldCount = Checks.size();
871 while (!Checks.empty()) {
872 // Pick all of the range checks with a specific base and length, and try to
873 // merge them.
874 const Value *CurrentBase = Checks.front().getBase();
875 const Value *CurrentLength = Checks.front().getLength();
876
878
879 auto IsCurrentCheck = [&](GuardWideningImpl::RangeCheck &RC) {
880 return RC.getBase() == CurrentBase && RC.getLength() == CurrentLength;
881 };
882
883 copy_if(Checks, std::back_inserter(CurrentChecks), IsCurrentCheck);
884 erase_if(Checks, IsCurrentCheck);
885
886 assert(CurrentChecks.size() != 0 && "We know we have at least one!");
887
888 if (CurrentChecks.size() < 3) {
889 llvm::append_range(RangeChecksOut, CurrentChecks);
890 continue;
891 }
892
893 // CurrentChecks.size() will typically be 3 here, but so far there has been
894 // no need to hard-code that fact.
895
896 llvm::sort(CurrentChecks, [&](const GuardWideningImpl::RangeCheck &LHS,
897 const GuardWideningImpl::RangeCheck &RHS) {
898 return LHS.getOffsetValue().slt(RHS.getOffsetValue());
899 });
900
901 // Note: std::sort should not invalidate the ChecksStart iterator.
902
903 const ConstantInt *MinOffset = CurrentChecks.front().getOffset();
904 const ConstantInt *MaxOffset = CurrentChecks.back().getOffset();
905
906 unsigned BitWidth = MaxOffset->getValue().getBitWidth();
907 if ((MaxOffset->getValue() - MinOffset->getValue())
909 return false;
910
911 APInt MaxDiff = MaxOffset->getValue() - MinOffset->getValue();
912 const APInt &HighOffset = MaxOffset->getValue();
913 auto OffsetOK = [&](const GuardWideningImpl::RangeCheck &RC) {
914 return (HighOffset - RC.getOffsetValue()).ult(MaxDiff);
915 };
916
917 if (MaxDiff.isMinValue() || !all_of(drop_begin(CurrentChecks), OffsetOK))
918 return false;
919
920 // We have a series of f+1 checks as:
921 //
922 // I+k_0 u< L ... Chk_0
923 // I+k_1 u< L ... Chk_1
924 // ...
925 // I+k_f u< L ... Chk_f
926 //
927 // with forall i in [0,f]: k_f-k_i u< k_f-k_0 ... Precond_0
928 // k_f-k_0 u< INT_MIN+k_f ... Precond_1
929 // k_f != k_0 ... Precond_2
930 //
931 // Claim:
932 // Chk_0 AND Chk_f implies all the other checks
933 //
934 // Informal proof sketch:
935 //
936 // We will show that the integer range [I+k_0,I+k_f] does not unsigned-wrap
937 // (i.e. going from I+k_0 to I+k_f does not cross the -1,0 boundary) and
938 // thus I+k_f is the greatest unsigned value in that range.
939 //
940 // This combined with Ckh_(f+1) shows that everything in that range is u< L.
941 // Via Precond_0 we know that all of the indices in Chk_0 through Chk_(f+1)
942 // lie in [I+k_0,I+k_f], this proving our claim.
943 //
944 // To see that [I+k_0,I+k_f] is not a wrapping range, note that there are
945 // two possibilities: I+k_0 u< I+k_f or I+k_0 >u I+k_f (they can't be equal
946 // since k_0 != k_f). In the former case, [I+k_0,I+k_f] is not a wrapping
947 // range by definition, and the latter case is impossible:
948 //
949 // 0-----I+k_f---I+k_0----L---INT_MAX,INT_MIN------------------(-1)
950 // xxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
951 //
952 // For Chk_0 to succeed, we'd have to have k_f-k_0 (the range highlighted
953 // with 'x' above) to be at least >u INT_MIN.
954
955 RangeChecksOut.emplace_back(CurrentChecks.front());
956 RangeChecksOut.emplace_back(CurrentChecks.back());
957 }
958
959 assert(RangeChecksOut.size() <= OldCount && "We pessimized!");
960 return RangeChecksOut.size() != OldCount;
961}
962
963#ifndef NDEBUG
964StringRef GuardWideningImpl::scoreTypeToString(WideningScore WS) {
965 switch (WS) {
966 case WS_IllegalOrNegative:
967 return "IllegalOrNegative";
968 case WS_Neutral:
969 return "Neutral";
970 case WS_Positive:
971 return "Positive";
972 case WS_VeryPositive:
973 return "VeryPositive";
974 }
975
976 llvm_unreachable("Fully covered switch above!");
977}
978#endif
979
982 // Avoid requesting analyses if there are no guards or widenable conditions.
983 auto *GuardDecl = F.getParent()->getFunction(
984 Intrinsic::getName(Intrinsic::experimental_guard));
985 bool HasIntrinsicGuards = GuardDecl && !GuardDecl->use_empty();
986 auto *WCDecl = F.getParent()->getFunction(
987 Intrinsic::getName(Intrinsic::experimental_widenable_condition));
988 bool HasWidenableConditions = WCDecl && !WCDecl->use_empty();
989 if (!HasIntrinsicGuards && !HasWidenableConditions)
990 return PreservedAnalyses::all();
991 auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
992 auto &LI = AM.getResult<LoopAnalysis>(F);
993 auto &PDT = AM.getResult<PostDominatorTreeAnalysis>(F);
994 auto &AC = AM.getResult<AssumptionAnalysis>(F);
995 auto *MSSAA = AM.getCachedResult<MemorySSAAnalysis>(F);
996 std::unique_ptr<MemorySSAUpdater> MSSAU;
997 if (MSSAA)
998 MSSAU = std::make_unique<MemorySSAUpdater>(&MSSAA->getMSSA());
999 if (!GuardWideningImpl(DT, &PDT, LI, AC, MSSAU ? MSSAU.get() : nullptr,
1000 DT.getRootNode(), [](BasicBlock *) { return true; })
1001 .run())
1002 return PreservedAnalyses::all();
1003
1007 return PA;
1008}
1009
1012 LPMUpdater &U) {
1013 BasicBlock *RootBB = L.getLoopPredecessor();
1014 if (!RootBB)
1015 RootBB = L.getHeader();
1016 auto BlockFilter = [&](BasicBlock *BB) {
1017 return BB == RootBB || L.contains(BB);
1018 };
1019 std::unique_ptr<MemorySSAUpdater> MSSAU;
1020 if (AR.MSSA)
1021 MSSAU = std::make_unique<MemorySSAUpdater>(AR.MSSA);
1022 if (!GuardWideningImpl(AR.DT, nullptr, AR.LI, AR.AC,
1023 MSSAU ? MSSAU.get() : nullptr, AR.DT.getNode(RootBB),
1024 BlockFilter)
1025 .run())
1026 return PreservedAnalyses::all();
1027
1028 auto PA = getLoopPassPreservedAnalyses();
1029 if (AR.MSSA)
1030 PA.preserve<MemorySSAAnalysis>();
1031 return PA;
1032}
SmallVector< AArch64_IMM::ImmInsnModel, 4 > Insn
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition: Compiler.h:537
#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.
#define Check(C,...)
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)
static std::optional< BasicBlock::iterator > getFreezeInsertPt(Value *V, const DominatorTree &DT)
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
Module.h This file contains the declarations for the Module class.
uint64_t IntrinsicInst * II
const SmallVectorImpl< MachineOperand > & Cond
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:78
unsigned getBitWidth() const
Return the number of bits in the APInt.
Definition: APInt.h:1448
bool isMinValue() const
Determine if this is the smallest unsigned value.
Definition: APInt.h:397
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:253
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
Definition: PassManager.h:424
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:405
A function analysis which provides an AssumptionCache.
A cache of @llvm.assume calls within a function.
LLVM Basic Block Representation.
Definition: BasicBlock.h:61
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:209
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:167
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:428
const CallInst * getPostdominatingDeoptimizeCall() const
Returns the call instruction calling @llvm.experimental.deoptimize that is present either in current ...
Definition: BasicBlock.cpp:344
Represents analyses that only rely on functions' control flow.
Definition: Analysis.h:72
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:757
This is the shared class of boolean and integer constants.
Definition: Constants.h:81
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:850
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:146
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...
This class represents an Operation in the Expression.
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.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:162
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 ...
This instruction compares its operands according to the predicate given to the constructor.
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:2671
void insertBefore(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified instruction.
Definition: Instruction.cpp:97
InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:92
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:48
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:571
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:44
An analysis that produces MemorySSA for a function.
Definition: MemorySSA.h:928
void removeMemoryAccess(MemoryAccess *, bool OptimizePhis=false)
Remove a MemoryAccess from MemorySSA, including updating all definitions and uses.
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: Analysis.h:111
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: Analysis.h:117
void preserveSet()
Mark an analysis set as preserved.
Definition: Analysis.h:146
void preserve()
Mark an analysis as preserved.
Definition: Analysis.h:131
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:323
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:412
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:344
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:479
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:586
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:950
void push_back(const T &Elt)
Definition: SmallVector.h:426
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
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:1075
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.
const ParentTy * getParent() const
Definition: ilist_node.h:32
self_iterator getIterator()
Definition: ilist_node.h:132
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.
StringRef getName(ID id)
Return the LLVM name for an intrinsic, such as "llvm.ppc.altivec.lvx".
Definition: Function.cpp:1071
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
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:875
class_match< ConstantInt > m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
Definition: PatternMatch.h:168
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:92
class_match< BasicBlock > m_BasicBlock()
Match an arbitrary basic block value and ignore it.
Definition: PatternMatch.h:189
BinaryOp_match< LHS, RHS, Instruction::Or > m_Or(const LHS &L, const RHS &R)
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:443
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
NodeAddr< InstrNode * > Instr
Definition: RDFGraph.h:389
NodeAddr< DefNode * > Def
Definition: RDFGraph.h:384
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:236
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
Definition: STLExtras.h:329
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
@ Length
Definition: DWP.cpp:480
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:1742
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:1722
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 range R to container C.
Definition: STLExtras.h:2067
df_iterator< T > df_begin(const T &G)
Value * extractWidenableCondition(const User *U)
Definition: GuardUtils.cpp:151
void parseWidenableGuard(const User *U, llvm::SmallVectorImpl< Value * > &Checks)
Definition: GuardUtils.cpp:138
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:1768
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:1729
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:53
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1647
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...
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:33
void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=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 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:191
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:2051
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)
Returns true if V cannot be poison, but may be undef.
bool isKnownNonNegative(const Value *V, const SimplifyQuery &SQ, unsigned Depth=0)
Returns true if the give value is known to be non-negative.
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...