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