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