1//===-- LoopPredication.cpp - Guard based loop predication pass -----------===//
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// The LoopPredication pass tries to convert loop variant range checks to loop
10// invariant by widening checks across loop iterations. For example, it will
11// convert
12//
13// for (i = 0; i < n; i++) {
14// guard(i < len);
15// ...
16// }
17//
18// to
19//
20// for (i = 0; i < n; i++) {
21// guard(n - 1 < len);
22// ...
23// }
24//
25// After this transformation the condition of the guard is loop invariant, so
26// loop-unswitch can later unswitch the loop by this condition which basically
27// predicates the loop by the widened condition:
28//
29// if (n - 1 < len)
30// for (i = 0; i < n; i++) {
31// ...
32// }
33// else
34// deoptimize
35//
36// It's tempting to rely on SCEV here, but it has proven to be problematic.
37// Generally the facts SCEV provides about the increment step of add
38// recurrences are true if the backedge of the loop is taken, which implicitly
39// assumes that the guard doesn't fail. Using these facts to optimize the
40// guard results in a circular logic where the guard is optimized under the
41// assumption that it never fails.
42//
43// For example, in the loop below the induction variable will be marked as nuw
44// basing on the guard. Basing on nuw the guard predicate will be considered
45// monotonic. Given a monotonic condition it's tempting to replace the induction
46// variable in the condition with its value on the last iteration. But this
47// transformation is not correct, e.g. e = 4, b = 5 breaks the loop.
48//
49// for (int i = b; i != e; i++)
50// guard(i u< len)
51//
52// One of the ways to reason about this problem is to use an inductive proof
53// approach. Given the loop:
54//
55// if (B(0)) {
56// do {
57// I = PHI(0, I.INC)
58// I.INC = I + Step
59// guard(G(I));
60// } while (B(I));
61// }
62//
63// where B(x) and G(x) are predicates that map integers to booleans, we want a
64// loop invariant expression M such the following program has the same semantics
65// as the above:
66//
67// if (B(0)) {
68// do {
69// I = PHI(0, I.INC)
70// I.INC = I + Step
71// guard(G(0) && M);
72// } while (B(I));
73// }
74//
75// One solution for M is M = forall X . (G(X) && B(X)) => G(X + Step)
76//
77// Informal proof that the transformation above is correct:
78//
79// By the definition of guards we can rewrite the guard condition to:
80// G(I) && G(0) && M
81//
82// Let's prove that for each iteration of the loop:
83// G(0) && M => G(I)
84// And the condition above can be simplified to G(Start) && M.
85//
86// Induction base.
87// G(0) && M => G(0)
88//
89// Induction step. Assuming G(0) && M => G(I) on the subsequent
90// iteration:
91//
92// B(I) is true because it's the backedge condition.
93// G(I) is true because the backedge is guarded by this condition.
94//
95// So M = forall X . (G(X) && B(X)) => G(X + Step) implies G(I + Step).
96//
97// Note that we can use anything stronger than M, i.e. any condition which
98// implies M.
99//
100// When S = 1 (i.e. forward iterating loop), the transformation is supported
101// when:
102// * The loop has a single latch with the condition of the form:
103// B(X) = latchStart + X <pred> latchLimit,
104// where <pred> is u<, u<=, s<, or s<=.
105// * The guard condition is of the form
106// G(X) = guardStart + X u< guardLimit
107//
108// For the ult latch comparison case M is:
109// forall X . guardStart + X u< guardLimit && latchStart + X <u latchLimit =>
110// guardStart + X + 1 u< guardLimit
111//
112// The only way the antecedent can be true and the consequent can be false is
113// if
114// X == guardLimit - 1 - guardStart
115// (and guardLimit is non-zero, but we won't use this latter fact).
116// If X == guardLimit - 1 - guardStart then the second half of the antecedent is
117// latchStart + guardLimit - 1 - guardStart u< latchLimit
118// and its negation is
119// latchStart + guardLimit - 1 - guardStart u>= latchLimit
120//
121// In other words, if
122// latchLimit u<= latchStart + guardLimit - 1 - guardStart
123// then:
124// (the ranges below are written in ConstantRange notation, where [A, B) is the
125// set for (I = A; I != B; I++ /*maywrap*/) yield(I);)
126//
127// forall X . guardStart + X u< guardLimit &&
128// latchStart + X u< latchLimit =>
129// guardStart + X + 1 u< guardLimit
130// == forall X . guardStart + X u< guardLimit &&
131// latchStart + X u< latchStart + guardLimit - 1 - guardStart =>
132// guardStart + X + 1 u< guardLimit
133// == forall X . (guardStart + X) in [0, guardLimit) &&
134// (latchStart + X) in [0, latchStart + guardLimit - 1 - guardStart) =>
135// (guardStart + X + 1) in [0, guardLimit)
136// == forall X . X in [-guardStart, guardLimit - guardStart) &&
137// X in [-latchStart, guardLimit - 1 - guardStart) =>
138// X in [-guardStart - 1, guardLimit - guardStart - 1)
139// == true
140//
141// So the widened condition is:
142// guardStart u< guardLimit &&
143// latchStart + guardLimit - 1 - guardStart u>= latchLimit
144// Similarly for ule condition the widened condition is:
145// guardStart u< guardLimit &&
146// latchStart + guardLimit - 1 - guardStart u> latchLimit
147// For slt condition the widened condition is:
148// guardStart u< guardLimit &&
149// latchStart + guardLimit - 1 - guardStart s>= latchLimit
150// For sle condition the widened condition is:
151// guardStart u< guardLimit &&
152// latchStart + guardLimit - 1 - guardStart s> latchLimit
153//
154// When S = -1 (i.e. reverse iterating loop), the transformation is supported
155// when:
156// * The loop has a single latch with the condition of the form:
157// B(X) = X <pred> latchLimit, where <pred> is u>, u>=, s>, or s>=.
158// * The guard condition is of the form
159// G(X) = X - 1 u< guardLimit
160//
161// For the ugt latch comparison case M is:
162// forall X. X-1 u< guardLimit and X u> latchLimit => X-2 u< guardLimit
163//
164// The only way the antecedent can be true and the consequent can be false is if
165// X == 1.
166// If X == 1 then the second half of the antecedent is
167// 1 u> latchLimit, and its negation is latchLimit u>= 1.
168//
169// So the widened condition is:
170// guardStart u< guardLimit && latchLimit u>= 1.
171// Similarly for sgt condition the widened condition is:
172// guardStart u< guardLimit && latchLimit s>= 1.
173// For uge condition the widened condition is:
174// guardStart u< guardLimit && latchLimit u> 1.
175// For sge condition the widened condition is:
176// guardStart u< guardLimit && latchLimit s> 1.
177//===----------------------------------------------------------------------===//
178
179#include "llvm/Transforms/Scalar/LoopPredication.h"
180#include "ScalarOptions.h"
181#include "llvm/ADT/Statistic.h"
182#include "llvm/Analysis/AliasAnalysis.h"
183#include "llvm/Analysis/BranchProbabilityInfo.h"
184#include "llvm/Analysis/GuardUtils.h"
185#include "llvm/Analysis/LoopInfo.h"
186#include "llvm/Analysis/LoopPass.h"
187#include "llvm/Analysis/MemorySSA.h"
188#include "llvm/Analysis/MemorySSAUpdater.h"
189#include "llvm/Analysis/ScalarEvolution.h"
190#include "llvm/Analysis/ScalarEvolutionExpressions.h"
191#include "llvm/IR/Function.h"
192#include "llvm/IR/IntrinsicInst.h"
193#include "llvm/IR/Module.h"
194#include "llvm/IR/PatternMatch.h"
195#include "llvm/IR/ProfDataUtils.h"
196#include "llvm/Pass.h"
197#include "llvm/Support/Debug.h"
198#include "llvm/Transforms/Scalar.h"
199#include "llvm/Transforms/Utils/GuardUtils.h"
200#include "llvm/Transforms/Utils/Local.h"
201#include "llvm/Transforms/Utils/LoopUtils.h"
202#include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"
203#include <optional>
204
205#define DEBUG_TYPE "loop-predication"
206
207STATISTIC(TotalConsidered, "Number of guards considered");
208STATISTIC(TotalWidened, "Number of checks widened");
209
210using namespace llvm;
211
212namespace {
213/// Represents an induction variable check:
214/// icmp Pred, <induction variable>, <loop invariant limit>
215struct LoopICmp {
216 ICmpInst::Predicate Pred;
217 const SCEVAddRecExpr *IV;
218 const SCEV *Limit;
219 LoopICmp(ICmpInst::Predicate Pred, const SCEVAddRecExpr *IV,
220 const SCEV *Limit)
221 : Pred(Pred), IV(IV), Limit(Limit) {}
222 LoopICmp() = default;
223 void dump() {
224 dbgs() << "LoopICmp Pred = " << Pred << ", IV = " << *IV
225 << ", Limit = " << *Limit << "\n";
226 }
227};
228
229class LoopPredication {
230 const ScalarOptions &Opts;
231 AliasAnalysis *AA;
232 DominatorTree *DT;
233 ScalarEvolution *SE;
234 LoopInfo *LI;
235 MemorySSAUpdater *MSSAU;
236
237 Loop *L;
238 const DataLayout *DL;
239 BasicBlock *Preheader;
240 LoopICmp LatchCheck;
241
242 bool isSupportedStep(const SCEV* Step);
243 std::optional<LoopICmp> parseLoopICmp(ICmpInst *ICI);
244 std::optional<LoopICmp> parseLoopLatchICmp();
245
246 /// Return an insertion point suitable for inserting a safe to speculate
247 /// instruction whose only user will be 'User' which has operands 'Ops'. A
248 /// trivial result would be the at the User itself, but we try to return a
249 /// loop invariant location if possible.
250 Instruction *findInsertPt(Instruction *User, ArrayRef<Value*> Ops);
251 /// Same as above, *except* that this uses the SCEV definition of invariant
252 /// which is that an expression *can be made* invariant via SCEVExpander.
253 /// Thus, this version is only suitable for finding an insert point to be
254 /// passed to SCEVExpander!
255 Instruction *findInsertPt(const SCEVExpander &Expander, Instruction *User,
256 ArrayRef<const SCEV *> Ops);
257
258 /// Return true if the value is known to produce a single fixed value across
259 /// all iterations on which it executes. Note that this does not imply
260 /// speculation safety. That must be established separately.
261 bool isLoopInvariantValue(const SCEV* S);
262
263 Value *expandCheck(SCEVExpander &Expander, Instruction *Guard,
264 ICmpInst::Predicate Pred, const SCEV *LHS,
265 const SCEV *RHS);
266
267 std::optional<Value *> widenICmpRangeCheck(ICmpInst *ICI,
268 SCEVExpander &Expander,
269 Instruction *Guard);
270 std::optional<Value *>
271 widenICmpRangeCheckIncrementingLoop(LoopICmp LatchCheck, LoopICmp RangeCheck,
272 SCEVExpander &Expander,
273 Instruction *Guard);
274 std::optional<Value *>
275 widenICmpRangeCheckDecrementingLoop(LoopICmp LatchCheck, LoopICmp RangeCheck,
276 SCEVExpander &Expander,
277 Instruction *Guard);
278 void widenChecks(SmallVectorImpl<Value *> &Checks,
279 SmallVectorImpl<Value *> &WidenedChecks,
280 SCEVExpander &Expander, Instruction *Guard);
281 bool widenGuardConditions(IntrinsicInst *II, SCEVExpander &Expander);
282 bool widenWidenableBranchGuardConditions(CondBrInst *Guard,
283 SCEVExpander &Expander);
284 // If the loop always exits through another block in the loop, we should not
285 // predicate based on the latch check. For example, the latch check can be a
286 // very coarse grained check and there can be more fine grained exit checks
287 // within the loop.
288 bool isLoopProfitableToPredicate();
289
290 bool predicateLoopExits(Loop *L, SCEVExpander &Rewriter);
291
292public:
293 LoopPredication(const ScalarOptions &Opts, AliasAnalysis *AA,
294 DominatorTree *DT, ScalarEvolution *SE, LoopInfo *LI,
295 MemorySSAUpdater *MSSAU)
296 : Opts(Opts), AA(AA), DT(DT), SE(SE), LI(LI), MSSAU(MSSAU) {};
297 bool runOnLoop(Loop *L);
298};
299
300} // end namespace
301
302PreservedAnalyses LoopPredicationPass::run(Loop &L, LoopAnalysisManager &AM,
303 LoopStandardAnalysisResults &AR,
304 LPMUpdater &U) {
305 std::unique_ptr<MemorySSAUpdater> MSSAU;
306 if (AR.MSSA)
307 MSSAU = std::make_unique<MemorySSAUpdater>(args&: AR.MSSA);
308 const ScalarOptions &Opts = getScalarOptions(L);
309 LoopPredication LP(Opts, &AR.AA, &AR.DT, &AR.SE, &AR.LI,
310 MSSAU ? MSSAU.get() : nullptr);
311 if (!LP.runOnLoop(L: &L))
312 return PreservedAnalyses::all();
313
314 auto PA = getLoopPassPreservedAnalyses();
315 if (AR.MSSA)
316 PA.preserve<MemorySSAAnalysis>();
317 return PA;
318}
319
320std::optional<LoopICmp> LoopPredication::parseLoopICmp(ICmpInst *ICI) {
321 auto Pred = ICI->getPredicate();
322 auto *LHS = ICI->getOperand(i_nocapture: 0);
323 auto *RHS = ICI->getOperand(i_nocapture: 1);
324
325 const SCEV *LHSS = SE->getSCEV(V: LHS);
326 if (isa<SCEVCouldNotCompute>(Val: LHSS))
327 return std::nullopt;
328 const SCEV *RHSS = SE->getSCEV(V: RHS);
329 if (isa<SCEVCouldNotCompute>(Val: RHSS))
330 return std::nullopt;
331
332 // Canonicalize RHS to be loop invariant bound, LHS - a loop computable IV
333 if (SE->isLoopInvariant(S: LHSS, L)) {
334 std::swap(a&: LHS, b&: RHS);
335 std::swap(a&: LHSS, b&: RHSS);
336 Pred = ICmpInst::getSwappedPredicate(pred: Pred);
337 }
338
339 const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Val: LHSS);
340 if (!AR || AR->getLoop() != L)
341 return std::nullopt;
342
343 return LoopICmp(Pred, AR, RHSS);
344}
345
346Value *LoopPredication::expandCheck(SCEVExpander &Expander,
347 Instruction *Guard,
348 ICmpInst::Predicate Pred, const SCEV *LHS,
349 const SCEV *RHS) {
350 Type *Ty = LHS->getType();
351 assert(Ty == RHS->getType() && "expandCheck operands have different types?");
352
353 if (SE->isLoopInvariant(S: LHS, L) && SE->isLoopInvariant(S: RHS, L)) {
354 IRBuilder<> Builder(Guard);
355 if (SE->isLoopEntryGuardedByCond(L, Pred, LHS, RHS))
356 return Builder.getTrue();
357 if (SE->isLoopEntryGuardedByCond(L, Pred: ICmpInst::getInversePredicate(pred: Pred),
358 LHS, RHS))
359 return Builder.getFalse();
360 }
361
362 Value *LHSV =
363 Expander.expandCodeFor(SH: LHS, Ty, I: findInsertPt(Expander, User: Guard, Ops: {LHS}));
364 Value *RHSV =
365 Expander.expandCodeFor(SH: RHS, Ty, I: findInsertPt(Expander, User: Guard, Ops: {RHS}));
366 IRBuilder<> Builder(findInsertPt(User: Guard, Ops: {LHSV, RHSV}));
367 return Builder.CreateICmp(P: Pred, LHS: LHSV, RHS: RHSV);
368}
369
370// Returns true if its safe to truncate the IV to RangeCheckType.
371// When the IV type is wider than the range operand type, we can still do loop
372// predication, by generating SCEVs for the range and latch that are of the
373// same type. We achieve this by generating a SCEV truncate expression for the
374// latch IV. This is done iff truncation of the IV is a safe operation,
375// without loss of information.
376// Another way to achieve this is by generating a wider type SCEV for the
377// range check operand, however, this needs a more involved check that
378// operands do not overflow. This can lead to loss of information when the
379// range operand is of the form: add i32 %offset, %iv. We need to prove that
380// sext(x + y) is same as sext(x) + sext(y).
381// This function returns true if we can safely represent the IV type in
382// the RangeCheckType without loss of information.
383static bool isSafeToTruncateWideIVType(const ScalarOptions &Opts,
384 const DataLayout &DL,
385 ScalarEvolution &SE,
386 const LoopICmp LatchCheck,
387 Type *RangeCheckType) {
388 if (!Opts.loop_predication_enable_iv_truncation)
389 return false;
390 assert(DL.getTypeSizeInBits(LatchCheck.IV->getType()).getFixedValue() >
391 DL.getTypeSizeInBits(RangeCheckType).getFixedValue() &&
392 "Expected latch check IV type to be larger than range check operand "
393 "type!");
394 // The start and end values of the IV should be known. This is to guarantee
395 // that truncating the wide type will not lose information.
396 auto *Limit = dyn_cast<SCEVConstant>(Val: LatchCheck.Limit);
397 auto *Start = dyn_cast<SCEVConstant>(Val: LatchCheck.IV->getStart());
398 if (!Limit || !Start)
399 return false;
400 // This check makes sure that the IV does not change sign during loop
401 // iterations. Consider latchType = i64, LatchStart = 5, Pred = ICMP_SGE,
402 // LatchEnd = 2, rangeCheckType = i32. If it's not a monotonic predicate, the
403 // IV wraps around, and the truncation of the IV would lose the range of
404 // iterations between 2^32 and 2^64.
405 if (!SE.getMonotonicPredicateType(LHS: LatchCheck.IV, Pred: LatchCheck.Pred))
406 return false;
407 // The active bits should be less than the bits in the RangeCheckType. This
408 // guarantees that truncating the latch check to RangeCheckType is a safe
409 // operation.
410 auto RangeCheckTypeBitSize =
411 DL.getTypeSizeInBits(Ty: RangeCheckType).getFixedValue();
412 return Start->getAPInt().getActiveBits() < RangeCheckTypeBitSize &&
413 Limit->getAPInt().getActiveBits() < RangeCheckTypeBitSize;
414}
415
416// Return an LoopICmp describing a latch check equivlent to LatchCheck but with
417// the requested type if safe to do so. May involve the use of a new IV.
418static std::optional<LoopICmp> generateLoopLatchCheck(const ScalarOptions &Opts,
419 const DataLayout &DL,
420 ScalarEvolution &SE,
421 const LoopICmp LatchCheck,
422 Type *RangeCheckType) {
423
424 auto *LatchType = LatchCheck.IV->getType();
425 if (RangeCheckType == LatchType)
426 return LatchCheck;
427 // For now, bail out if latch type is narrower than range type.
428 if (DL.getTypeSizeInBits(Ty: LatchType).getFixedValue() <
429 DL.getTypeSizeInBits(Ty: RangeCheckType).getFixedValue())
430 return std::nullopt;
431 if (!isSafeToTruncateWideIVType(Opts, DL, SE, LatchCheck, RangeCheckType))
432 return std::nullopt;
433 // We can now safely identify the truncated version of the IV and limit for
434 // RangeCheckType.
435 LoopICmp NewLatchCheck;
436 NewLatchCheck.Pred = LatchCheck.Pred;
437 NewLatchCheck.IV = dyn_cast<SCEVAddRecExpr>(
438 Val: SE.getTruncateExpr(Op: LatchCheck.IV, Ty: RangeCheckType));
439 if (!NewLatchCheck.IV)
440 return std::nullopt;
441 NewLatchCheck.Limit = SE.getTruncateExpr(Op: LatchCheck.Limit, Ty: RangeCheckType);
442 LLVM_DEBUG(dbgs() << "IV of type: " << *LatchType
443 << "can be represented as range check type:"
444 << *RangeCheckType << "\n");
445 LLVM_DEBUG(dbgs() << "LatchCheck.IV: " << *NewLatchCheck.IV << "\n");
446 LLVM_DEBUG(dbgs() << "LatchCheck.Limit: " << *NewLatchCheck.Limit << "\n");
447 return NewLatchCheck;
448}
449
450bool LoopPredication::isSupportedStep(const SCEV* Step) {
451 return Step->isOne() || (Step->isAllOnesValue() &&
452 Opts.loop_predication_enable_count_down_loop);
453}
454
455Instruction *LoopPredication::findInsertPt(Instruction *Use,
456 ArrayRef<Value*> Ops) {
457 for (Value *Op : Ops)
458 if (!L->isLoopInvariant(V: Op))
459 return Use;
460 return Preheader->getTerminator();
461}
462
463Instruction *LoopPredication::findInsertPt(const SCEVExpander &Expander,
464 Instruction *Use,
465 ArrayRef<const SCEV *> Ops) {
466 // Subtlety: SCEV considers things to be invariant if the value produced is
467 // the same across iterations. This is not the same as being able to
468 // evaluate outside the loop, which is what we actually need here.
469 for (const SCEV *Op : Ops)
470 if (!SE->isLoopInvariant(S: Op, L) ||
471 !Expander.isSafeToExpandAt(S: Op, InsertionPoint: Preheader->getTerminator()))
472 return Use;
473 return Preheader->getTerminator();
474}
475
476bool LoopPredication::isLoopInvariantValue(const SCEV* S) {
477 // Handling expressions which produce invariant results, but *haven't* yet
478 // been removed from the loop serves two important purposes.
479 // 1) Most importantly, it resolves a pass ordering cycle which would
480 // otherwise need us to iteration licm, loop-predication, and either
481 // loop-unswitch or loop-peeling to make progress on examples with lots of
482 // predicable range checks in a row. (Since, in the general case, we can't
483 // hoist the length checks until the dominating checks have been discharged
484 // as we can't prove doing so is safe.)
485 // 2) As a nice side effect, this exposes the value of peeling or unswitching
486 // much more obviously in the IR. Otherwise, the cost modeling for other
487 // transforms would end up needing to duplicate all of this logic to model a
488 // check which becomes predictable based on a modeled peel or unswitch.
489 //
490 // The cost of doing so in the worst case is an extra fill from the stack in
491 // the loop to materialize the loop invariant test value instead of checking
492 // against the original IV which is presumable in a register inside the loop.
493 // Such cases are presumably rare, and hint at missing oppurtunities for
494 // other passes.
495
496 if (SE->isLoopInvariant(S, L))
497 // Note: This the SCEV variant, so the original Value* may be within the
498 // loop even though SCEV has proven it is loop invariant.
499 return true;
500
501 // Handle a particular important case which SCEV doesn't yet know about which
502 // shows up in range checks on arrays with immutable lengths.
503 // TODO: This should be sunk inside SCEV.
504 if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(Val: S))
505 if (const auto *LI = dyn_cast<LoadInst>(Val: U->getValue()))
506 if (LI->isUnordered() && L->hasLoopInvariantOperands(I: LI))
507 if (!isModSet(MRI: AA->getModRefInfoMask(P: LI->getOperand(i_nocapture: 0))) ||
508 LI->hasMetadata(KindID: LLVMContext::MD_invariant_load))
509 return true;
510 return false;
511}
512
513std::optional<Value *> LoopPredication::widenICmpRangeCheckIncrementingLoop(
514 LoopICmp LatchCheck, LoopICmp RangeCheck, SCEVExpander &Expander,
515 Instruction *Guard) {
516 auto *Ty = RangeCheck.IV->getType();
517 // Generate the widened condition for the forward loop:
518 // guardStart u< guardLimit &&
519 // latchLimit <pred> guardLimit - 1 - guardStart + latchStart
520 // where <pred> depends on the latch condition predicate. See the file
521 // header comment for the reasoning.
522 // guardLimit - guardStart + latchStart - 1
523 const SCEV *GuardStart = RangeCheck.IV->getStart();
524 const SCEV *GuardLimit = RangeCheck.Limit;
525 const SCEV *LatchStart = LatchCheck.IV->getStart();
526 const SCEV *LatchLimit = LatchCheck.Limit;
527 // Subtlety: We need all the values to be *invariant* across all iterations,
528 // but we only need to check expansion safety for those which *aren't*
529 // already guaranteed to dominate the guard.
530 if (!isLoopInvariantValue(S: GuardStart) ||
531 !isLoopInvariantValue(S: GuardLimit) ||
532 !isLoopInvariantValue(S: LatchStart) ||
533 !isLoopInvariantValue(S: LatchLimit)) {
534 LLVM_DEBUG(dbgs() << "Can't expand limit check!\n");
535 return std::nullopt;
536 }
537 if (!Expander.isSafeToExpandAt(S: LatchStart, InsertionPoint: Guard) ||
538 !Expander.isSafeToExpandAt(S: LatchLimit, InsertionPoint: Guard)) {
539 LLVM_DEBUG(dbgs() << "Can't expand limit check!\n");
540 return std::nullopt;
541 }
542
543 // guardLimit - guardStart + latchStart - 1
544 const SCEV *RHS =
545 SE->getAddExpr(LHS: SE->getMinusSCEV(LHS: GuardLimit, RHS: GuardStart),
546 RHS: SE->getMinusSCEV(LHS: LatchStart, RHS: SE->getOne(Ty)));
547 auto LimitCheckPred =
548 ICmpInst::getFlippedStrictnessPredicate(pred: LatchCheck.Pred);
549
550 LLVM_DEBUG(dbgs() << "LHS: " << *LatchLimit << "\n");
551 LLVM_DEBUG(dbgs() << "RHS: " << *RHS << "\n");
552 LLVM_DEBUG(dbgs() << "Pred: " << LimitCheckPred << "\n");
553
554 auto *LimitCheck =
555 expandCheck(Expander, Guard, Pred: LimitCheckPred, LHS: LatchLimit, RHS);
556 auto *FirstIterationCheck = expandCheck(Expander, Guard, Pred: RangeCheck.Pred,
557 LHS: GuardStart, RHS: GuardLimit);
558 IRBuilder<> Builder(findInsertPt(Use: Guard, Ops: {FirstIterationCheck, LimitCheck}));
559 return Builder.CreateFreeze(
560 V: Builder.CreateAnd(LHS: FirstIterationCheck, RHS: LimitCheck));
561}
562
563std::optional<Value *> LoopPredication::widenICmpRangeCheckDecrementingLoop(
564 LoopICmp LatchCheck, LoopICmp RangeCheck, SCEVExpander &Expander,
565 Instruction *Guard) {
566 auto *Ty = RangeCheck.IV->getType();
567 const SCEV *GuardStart = RangeCheck.IV->getStart();
568 const SCEV *GuardLimit = RangeCheck.Limit;
569 const SCEV *LatchStart = LatchCheck.IV->getStart();
570 const SCEV *LatchLimit = LatchCheck.Limit;
571 // Subtlety: We need all the values to be *invariant* across all iterations,
572 // but we only need to check expansion safety for those which *aren't*
573 // already guaranteed to dominate the guard.
574 if (!isLoopInvariantValue(S: GuardStart) ||
575 !isLoopInvariantValue(S: GuardLimit) ||
576 !isLoopInvariantValue(S: LatchStart) ||
577 !isLoopInvariantValue(S: LatchLimit)) {
578 LLVM_DEBUG(dbgs() << "Can't expand limit check!\n");
579 return std::nullopt;
580 }
581 if (!Expander.isSafeToExpandAt(S: LatchStart, InsertionPoint: Guard) ||
582 !Expander.isSafeToExpandAt(S: LatchLimit, InsertionPoint: Guard)) {
583 LLVM_DEBUG(dbgs() << "Can't expand limit check!\n");
584 return std::nullopt;
585 }
586 // The decrement of the latch check IV should be the same as the
587 // rangeCheckIV.
588 auto *PostDecLatchCheckIV = LatchCheck.IV->getPostIncExpr(SE&: *SE);
589 if (RangeCheck.IV != PostDecLatchCheckIV) {
590 LLVM_DEBUG(dbgs() << "Not the same. PostDecLatchCheckIV: "
591 << *PostDecLatchCheckIV
592 << " and RangeCheckIV: " << *RangeCheck.IV << "\n");
593 return std::nullopt;
594 }
595
596 // Generate the widened condition for CountDownLoop:
597 // guardStart u< guardLimit &&
598 // latchLimit <pred> 1.
599 // See the header comment for reasoning of the checks.
600 auto LimitCheckPred =
601 ICmpInst::getFlippedStrictnessPredicate(pred: LatchCheck.Pred);
602 auto *FirstIterationCheck = expandCheck(Expander, Guard,
603 Pred: ICmpInst::ICMP_ULT,
604 LHS: GuardStart, RHS: GuardLimit);
605 auto *LimitCheck = expandCheck(Expander, Guard, Pred: LimitCheckPred, LHS: LatchLimit,
606 RHS: SE->getOne(Ty));
607 IRBuilder<> Builder(findInsertPt(Use: Guard, Ops: {FirstIterationCheck, LimitCheck}));
608 return Builder.CreateFreeze(
609 V: Builder.CreateAnd(LHS: FirstIterationCheck, RHS: LimitCheck));
610}
611
612static void normalizePredicate(ScalarEvolution *SE, Loop *L,
613 LoopICmp& RC) {
614 // LFTR canonicalizes checks to the ICMP_NE/EQ form; normalize back to the
615 // ULT/UGE form for ease of handling by our caller.
616 if (ICmpInst::isEquality(P: RC.Pred) &&
617 RC.IV->getStepRecurrence(SE&: *SE)->isOne() &&
618 SE->isKnownPredicate(Pred: ICmpInst::ICMP_ULE, LHS: RC.IV->getStart(), RHS: RC.Limit))
619 RC.Pred = RC.Pred == ICmpInst::ICMP_NE ?
620 ICmpInst::ICMP_ULT : ICmpInst::ICMP_UGE;
621}
622
623/// If ICI can be widened to a loop invariant condition emits the loop
624/// invariant condition in the loop preheader and return it, otherwise
625/// returns std::nullopt.
626std::optional<Value *>
627LoopPredication::widenICmpRangeCheck(ICmpInst *ICI, SCEVExpander &Expander,
628 Instruction *Guard) {
629 LLVM_DEBUG(dbgs() << "Analyzing ICmpInst condition:\n");
630 LLVM_DEBUG(ICI->dump());
631
632 // parseLoopStructure guarantees that the latch condition is:
633 // ++i <pred> latchLimit, where <pred> is u<, u<=, s<, or s<=.
634 // We are looking for the range checks of the form:
635 // i u< guardLimit
636 auto RangeCheck = parseLoopICmp(ICI);
637 if (!RangeCheck) {
638 LLVM_DEBUG(dbgs() << "Failed to parse the loop latch condition!\n");
639 return std::nullopt;
640 }
641 LLVM_DEBUG(dbgs() << "Guard check:\n");
642 LLVM_DEBUG(RangeCheck->dump());
643 if (RangeCheck->Pred != ICmpInst::ICMP_ULT) {
644 LLVM_DEBUG(dbgs() << "Unsupported range check predicate("
645 << RangeCheck->Pred << ")!\n");
646 return std::nullopt;
647 }
648 auto *RangeCheckIV = RangeCheck->IV;
649 if (!RangeCheckIV->isAffine()) {
650 LLVM_DEBUG(dbgs() << "Range check IV is not affine!\n");
651 return std::nullopt;
652 }
653 const SCEV *Step = RangeCheckIV->getStepRecurrence(SE&: *SE);
654 // We cannot just compare with latch IV step because the latch and range IVs
655 // may have different types.
656 if (!isSupportedStep(Step)) {
657 LLVM_DEBUG(dbgs() << "Range check and latch have IVs different steps!\n");
658 return std::nullopt;
659 }
660 auto *Ty = RangeCheckIV->getType();
661 auto CurrLatchCheckOpt =
662 generateLoopLatchCheck(Opts, DL: *DL, SE&: *SE, LatchCheck, RangeCheckType: Ty);
663 if (!CurrLatchCheckOpt) {
664 LLVM_DEBUG(dbgs() << "Failed to generate a loop latch check "
665 "corresponding to range type: "
666 << *Ty << "\n");
667 return std::nullopt;
668 }
669
670 LoopICmp CurrLatchCheck = *CurrLatchCheckOpt;
671 // At this point, the range and latch step should have the same type, but need
672 // not have the same value (we support both 1 and -1 steps).
673 assert(Step->getType() ==
674 CurrLatchCheck.IV->getStepRecurrence(*SE)->getType() &&
675 "Range and latch steps should be of same type!");
676 if (Step != CurrLatchCheck.IV->getStepRecurrence(SE&: *SE)) {
677 LLVM_DEBUG(dbgs() << "Range and latch have different step values!\n");
678 return std::nullopt;
679 }
680
681 if (Step->isOne())
682 return widenICmpRangeCheckIncrementingLoop(LatchCheck: CurrLatchCheck, RangeCheck: *RangeCheck,
683 Expander, Guard);
684 else {
685 assert(Step->isAllOnesValue() && "Step should be -1!");
686 return widenICmpRangeCheckDecrementingLoop(LatchCheck: CurrLatchCheck, RangeCheck: *RangeCheck,
687 Expander, Guard);
688 }
689}
690
691void LoopPredication::widenChecks(SmallVectorImpl<Value *> &Checks,
692 SmallVectorImpl<Value *> &WidenedChecks,
693 SCEVExpander &Expander, Instruction *Guard) {
694 for (auto &Check : Checks)
695 if (ICmpInst *ICI = dyn_cast<ICmpInst>(Val: Check))
696 if (auto NewRangeCheck = widenICmpRangeCheck(ICI, Expander, Guard)) {
697 WidenedChecks.push_back(Elt: Check);
698 Check = *NewRangeCheck;
699 }
700}
701
702bool LoopPredication::widenGuardConditions(IntrinsicInst *Guard,
703 SCEVExpander &Expander) {
704 LLVM_DEBUG(dbgs() << "Processing guard:\n");
705 LLVM_DEBUG(Guard->dump());
706
707 TotalConsidered++;
708 SmallVector<Value *, 4> Checks;
709 SmallVector<Value *> WidenedChecks;
710 parseWidenableGuard(U: Guard, Checks);
711 widenChecks(Checks, WidenedChecks, Expander, Guard);
712 if (WidenedChecks.empty())
713 return false;
714
715 TotalWidened += WidenedChecks.size();
716
717 // Emit the new guard condition
718 IRBuilder<> Builder(findInsertPt(Use: Guard, Ops: Checks));
719 Value *AllChecks = Builder.CreateAnd(Ops: Checks);
720 auto *OldCond = Guard->getOperand(i_nocapture: 0);
721 Guard->setOperand(i_nocapture: 0, Val_nocapture: AllChecks);
722 if (Opts.loop_predication_insert_assumes_of_predicated_guards_conditions) {
723 Builder.SetInsertPoint(&*++BasicBlock::iterator(Guard));
724 Builder.CreateAssumption(Cond: OldCond);
725 }
726 RecursivelyDeleteTriviallyDeadInstructions(V: OldCond, TLI: nullptr /* TLI */, MSSAU);
727
728 LLVM_DEBUG(dbgs() << "Widened checks = " << WidenedChecks.size() << "\n");
729 return true;
730}
731
732bool LoopPredication::widenWidenableBranchGuardConditions(
733 CondBrInst *BI, SCEVExpander &Expander) {
734 assert(isGuardAsWidenableBranch(BI) && "Must be!");
735 LLVM_DEBUG(dbgs() << "Processing guard:\n");
736 LLVM_DEBUG(BI->dump());
737
738 TotalConsidered++;
739 SmallVector<Value *, 4> Checks;
740 SmallVector<Value *> WidenedChecks;
741 parseWidenableGuard(U: BI, Checks);
742 // At the moment, our matching logic for wideable conditions implicitly
743 // assumes we preserve the form: (br (and Cond, WC())). FIXME
744 auto WC = extractWidenableCondition(U: BI);
745 Checks.push_back(Elt: WC);
746 widenChecks(Checks, WidenedChecks, Expander, Guard: BI);
747 if (WidenedChecks.empty())
748 return false;
749
750 TotalWidened += WidenedChecks.size();
751
752 // Emit the new guard condition
753 IRBuilder<> Builder(findInsertPt(Use: BI, Ops: Checks));
754 Value *AllChecks = Builder.CreateAnd(Ops: Checks);
755 auto *OldCond = BI->getCondition();
756 BI->setCondition(AllChecks);
757 if (Opts.loop_predication_insert_assumes_of_predicated_guards_conditions) {
758 BasicBlock *IfTrueBB = BI->getSuccessor(i: 0);
759 Builder.SetInsertPoint(IfTrueBB->getFirstInsertionPt());
760 // If this block has other predecessors, we might not be able to use Cond.
761 // In this case, create a Phi where every other input is `true` and input
762 // from guard block is Cond.
763 Value *AssumeCond = Builder.CreateAnd(Ops: WidenedChecks);
764 if (!IfTrueBB->getUniquePredecessor()) {
765 auto *GuardBB = BI->getParent();
766 auto *PN = Builder.CreatePHI(Ty: AssumeCond->getType(), NumReservedValues: pred_size(BB: IfTrueBB),
767 Name: "assume.cond");
768 for (auto *Pred : predecessors(BB: IfTrueBB))
769 PN->addIncoming(V: Pred == GuardBB ? AssumeCond : Builder.getTrue(), BB: Pred);
770 AssumeCond = PN;
771 }
772 Builder.CreateAssumption(Cond: AssumeCond);
773 }
774 RecursivelyDeleteTriviallyDeadInstructions(V: OldCond, TLI: nullptr /* TLI */, MSSAU);
775 assert(isGuardAsWidenableBranch(BI) &&
776 "Stopped being a guard after transform?");
777
778 LLVM_DEBUG(dbgs() << "Widened checks = " << WidenedChecks.size() << "\n");
779 return true;
780}
781
782std::optional<LoopICmp> LoopPredication::parseLoopLatchICmp() {
783 using namespace PatternMatch;
784
785 BasicBlock *LoopLatch = L->getLoopLatch();
786 if (!LoopLatch) {
787 LLVM_DEBUG(dbgs() << "The loop doesn't have a single latch!\n");
788 return std::nullopt;
789 }
790
791 auto *BI = dyn_cast<CondBrInst>(Val: LoopLatch->getTerminator());
792 if (!BI) {
793 LLVM_DEBUG(dbgs() << "Failed to match the latch terminator!\n");
794 return std::nullopt;
795 }
796 BasicBlock *TrueDest = BI->getSuccessor(i: 0);
797 assert(
798 (TrueDest == L->getHeader() || BI->getSuccessor(1) == L->getHeader()) &&
799 "One of the latch's destinations must be the header");
800
801 auto *ICI = dyn_cast<ICmpInst>(Val: BI->getCondition());
802 if (!ICI) {
803 LLVM_DEBUG(dbgs() << "Failed to match the latch condition!\n");
804 return std::nullopt;
805 }
806 auto Result = parseLoopICmp(ICI);
807 if (!Result) {
808 LLVM_DEBUG(dbgs() << "Failed to parse the loop latch condition!\n");
809 return std::nullopt;
810 }
811
812 if (TrueDest != L->getHeader())
813 Result->Pred = ICmpInst::getInversePredicate(pred: Result->Pred);
814
815 // Check affine first, so if it's not we don't try to compute the step
816 // recurrence.
817 if (!Result->IV->isAffine()) {
818 LLVM_DEBUG(dbgs() << "The induction variable is not affine!\n");
819 return std::nullopt;
820 }
821
822 const SCEV *Step = Result->IV->getStepRecurrence(SE&: *SE);
823 if (!isSupportedStep(Step)) {
824 LLVM_DEBUG(dbgs() << "Unsupported loop stride(" << *Step << ")!\n");
825 return std::nullopt;
826 }
827
828 auto IsUnsupportedPredicate = [](const SCEV *Step, ICmpInst::Predicate Pred) {
829 if (Step->isOne()) {
830 return Pred != ICmpInst::ICMP_ULT && Pred != ICmpInst::ICMP_SLT &&
831 Pred != ICmpInst::ICMP_ULE && Pred != ICmpInst::ICMP_SLE;
832 } else {
833 assert(Step->isAllOnesValue() && "Step should be -1!");
834 return Pred != ICmpInst::ICMP_UGT && Pred != ICmpInst::ICMP_SGT &&
835 Pred != ICmpInst::ICMP_UGE && Pred != ICmpInst::ICMP_SGE;
836 }
837 };
838
839 normalizePredicate(SE, L, RC&: *Result);
840 if (IsUnsupportedPredicate(Step, Result->Pred)) {
841 LLVM_DEBUG(dbgs() << "Unsupported loop latch predicate(" << Result->Pred
842 << ")!\n");
843 return std::nullopt;
844 }
845
846 return Result;
847}
848
849bool LoopPredication::isLoopProfitableToPredicate() {
850 if (Opts.loop_predication_skip_profitability_checks)
851 return true;
852
853 SmallVector<std::pair<BasicBlock *, BasicBlock *>, 8> ExitEdges;
854 LI->getExitEdges(L: *L, ExitEdges);
855 // If there is only one exiting edge in the loop, it is always profitable to
856 // predicate the loop.
857 if (ExitEdges.size() == 1)
858 return true;
859
860 // Calculate the exiting probabilities of all exiting edges from the loop,
861 // starting with the LatchExitProbability.
862 // Heuristic for profitability: If any of the exiting blocks' probability of
863 // exiting the loop is larger than exiting through the latch block, it's not
864 // profitable to predicate the loop.
865 auto *LatchBlock = L->getLoopLatch();
866 assert(LatchBlock && "Should have a single latch at this point!");
867 auto *LatchTerm = LatchBlock->getTerminator();
868 assert(LatchTerm->getNumSuccessors() == 2 &&
869 "expected to be an exiting block with 2 succs!");
870 unsigned LatchBrExitIdx =
871 LatchTerm->getSuccessor(Idx: 0) == L->getHeader() ? 1 : 0;
872 // We compute branch probabilities without BPI. We do not rely on BPI since
873 // Loop predication is usually run in an LPM and BPI is only preserved
874 // lossily within loop pass managers, while BPI has an inherent notion of
875 // being complete for an entire function.
876
877 // If the latch exits into a deoptimize or an unreachable block, do not
878 // predicate on that latch check.
879 auto *LatchExitBlock = LatchTerm->getSuccessor(Idx: LatchBrExitIdx);
880 if (isa<UnreachableInst>(Val: LatchTerm) ||
881 LatchExitBlock->getTerminatingDeoptimizeCall())
882 return false;
883
884 // Latch terminator has no valid profile data, so nothing to check
885 // profitability on.
886 if (!hasValidBranchWeightMD(I: *LatchTerm))
887 return true;
888
889 auto ComputeBranchProbability =
890 [&](const BasicBlock *ExitingBlock,
891 const BasicBlock *ExitBlock) -> BranchProbability {
892 auto *Term = ExitingBlock->getTerminator();
893 unsigned NumSucc = Term->getNumSuccessors();
894 if (MDNode *ProfileData = getValidBranchWeightMDNode(I: *Term)) {
895 SmallVector<uint32_t> Weights;
896 extractBranchWeights(ProfileData, Weights);
897 uint64_t Numerator = 0, Denominator = 0;
898 for (auto [i, Weight] : llvm::enumerate(First&: Weights)) {
899 if (Term->getSuccessor(Idx: i) == ExitBlock)
900 Numerator += Weight;
901 Denominator += Weight;
902 }
903 // If all weights are zero act as if there was no profile data
904 if (Denominator == 0)
905 return BranchProbability::getBranchProbability(Numerator: 1, Denominator: NumSucc);
906 return BranchProbability::getBranchProbability(Numerator, Denominator);
907 } else {
908 assert(LatchBlock != ExitingBlock &&
909 "Latch term should always have profile data!");
910 // No profile data, so we choose the weight as 1/num_of_succ(Src)
911 return BranchProbability::getBranchProbability(Numerator: 1, Denominator: NumSucc);
912 }
913 };
914
915 BranchProbability LatchExitProbability =
916 ComputeBranchProbability(LatchBlock, LatchExitBlock);
917
918 // Protect against degenerate inputs provided by the user. Providing a value
919 // less than one, can invert the definition of profitable loop predication.
920 float ScaleFactor = Opts.loop_predication_latch_probability_scale;
921 if (ScaleFactor < 1) {
922 LLVM_DEBUG(
923 dbgs()
924 << "Ignored user setting for loop-predication-latch-probability-scale: "
925 << Opts.loop_predication_latch_probability_scale << "\n");
926 LLVM_DEBUG(dbgs() << "The value is set to 1.0\n");
927 ScaleFactor = 1.0;
928 }
929 const auto LatchProbabilityThreshold = LatchExitProbability * ScaleFactor;
930
931 for (const auto &ExitEdge : ExitEdges) {
932 BranchProbability ExitingBlockProbability =
933 ComputeBranchProbability(ExitEdge.first, ExitEdge.second);
934 // Some exiting edge has higher probability than the latch exiting edge.
935 // No longer profitable to predicate.
936 if (ExitingBlockProbability > LatchProbabilityThreshold)
937 return false;
938 }
939
940 // We have concluded that the most probable way to exit from the
941 // loop is through the latch (or there's no profile information and all
942 // exits are equally likely).
943 return true;
944}
945
946/// If we can (cheaply) find a widenable branch which controls entry into the
947/// loop, return it.
948static CondBrInst *FindWidenableTerminatorAboveLoop(Loop *L, LoopInfo &LI) {
949 // Walk back through any unconditional executed blocks and see if we can find
950 // a widenable condition which seems to control execution of this loop. Note
951 // that we predict that maythrow calls are likely untaken and thus that it's
952 // profitable to widen a branch before a maythrow call with a condition
953 // afterwards even though that may cause the slow path to run in a case where
954 // it wouldn't have otherwise.
955 BasicBlock *BB = L->getLoopPreheader();
956 if (!BB)
957 return nullptr;
958 do {
959 if (BasicBlock *Pred = BB->getSinglePredecessor())
960 if (BB == Pred->getSingleSuccessor()) {
961 BB = Pred;
962 continue;
963 }
964 break;
965 } while (true);
966
967 if (BasicBlock *Pred = BB->getSinglePredecessor()) {
968 if (auto *BI = dyn_cast<CondBrInst>(Val: Pred->getTerminator()))
969 if (BI->getSuccessor(i: 0) == BB && isWidenableBranch(U: BI))
970 return BI;
971 }
972 return nullptr;
973}
974
975/// Return the minimum of all analyzeable exit counts. This is an upper bound
976/// on the actual exit count. If there are not at least two analyzeable exits,
977/// returns SCEVCouldNotCompute.
978static const SCEV *getMinAnalyzeableBackedgeTakenCount(ScalarEvolution &SE,
979 DominatorTree &DT,
980 Loop *L) {
981 SmallVector<BasicBlock *, 16> ExitingBlocks;
982 L->getExitingBlocks(ExitingBlocks);
983
984 SmallVector<SCEVUse, 4> ExitCounts;
985 for (BasicBlock *ExitingBB : ExitingBlocks) {
986 SCEVUse ExitCount = SE.getExitCount(L, ExitingBlock: ExitingBB);
987 if (isa<SCEVCouldNotCompute>(Val: ExitCount))
988 continue;
989 assert(DT.dominates(ExitingBB, L->getLoopLatch()) &&
990 "We should only have known counts for exiting blocks that "
991 "dominate latch!");
992 ExitCounts.push_back(Elt: ExitCount);
993 }
994 if (ExitCounts.size() < 2)
995 return SE.getCouldNotCompute();
996 return SE.getUMinFromMismatchedTypes(Ops&: ExitCounts);
997}
998
999/// This implements an analogous, but entirely distinct transform from the main
1000/// loop predication transform. This one is phrased in terms of using a
1001/// widenable branch *outside* the loop to allow us to simplify loop exits in a
1002/// following loop. This is close in spirit to the IndVarSimplify transform
1003/// of the same name, but is materially different widening loosens legality
1004/// sharply.
1005bool LoopPredication::predicateLoopExits(Loop *L, SCEVExpander &Rewriter) {
1006 // The transformation performed here aims to widen a widenable condition
1007 // above the loop such that all analyzeable exit leading to deopt are dead.
1008 // It assumes that the latch is the dominant exit for profitability and that
1009 // exits branching to deoptimizing blocks are rarely taken. It relies on the
1010 // semantics of widenable expressions for legality. (i.e. being able to fall
1011 // down the widenable path spuriously allows us to ignore exit order,
1012 // unanalyzeable exits, side effects, exceptional exits, and other challenges
1013 // which restrict the applicability of the non-WC based version of this
1014 // transform in IndVarSimplify.)
1015 //
1016 // NOTE ON POISON/UNDEF - We're hoisting an expression above guards which may
1017 // imply flags on the expression being hoisted and inserting new uses (flags
1018 // are only correct for current uses). The result is that we may be
1019 // inserting a branch on the value which can be either poison or undef. In
1020 // this case, the branch can legally go either way; we just need to avoid
1021 // introducing UB. This is achieved through the use of the freeze
1022 // instruction.
1023
1024 SmallVector<BasicBlock *, 16> ExitingBlocks;
1025 L->getExitingBlocks(ExitingBlocks);
1026
1027 if (ExitingBlocks.empty())
1028 return false; // Nothing to do.
1029
1030 auto *Latch = L->getLoopLatch();
1031 if (!Latch)
1032 return false;
1033
1034 auto *WidenableBR = FindWidenableTerminatorAboveLoop(L, LI&: *LI);
1035 if (!WidenableBR)
1036 return false;
1037
1038 const SCEV *LatchEC = SE->getExitCount(L, ExitingBlock: Latch);
1039 if (isa<SCEVCouldNotCompute>(Val: LatchEC))
1040 return false; // profitability - want hot exit in analyzeable set
1041
1042 // At this point, we have found an analyzeable latch, and a widenable
1043 // condition above the loop. If we have a widenable exit within the loop
1044 // (for which we can't compute exit counts), drop the ability to further
1045 // widen so that we gain ability to analyze it's exit count and perform this
1046 // transform. TODO: It'd be nice to know for sure the exit became
1047 // analyzeable after dropping widenability.
1048 bool ChangedLoop = false;
1049
1050 for (auto *ExitingBB : ExitingBlocks) {
1051 if (LI->getLoopFor(BB: ExitingBB) != L)
1052 continue;
1053
1054 auto *BI = dyn_cast<CondBrInst>(Val: ExitingBB->getTerminator());
1055 if (!BI)
1056 continue;
1057
1058 if (auto WC = extractWidenableCondition(U: BI))
1059 if (L->contains(BB: BI->getSuccessor(i: 0))) {
1060 assert(WC->hasOneUse() && "Not appropriate widenable branch!");
1061 WC->user_back()->replaceUsesOfWith(
1062 From: WC, To: ConstantInt::getTrue(Context&: BI->getContext()));
1063 ChangedLoop = true;
1064 }
1065 }
1066 if (ChangedLoop)
1067 SE->forgetLoop(L);
1068
1069 // The insertion point for the widening should be at the widenably call, not
1070 // at the WidenableBR. If we do this at the widenableBR, we can incorrectly
1071 // change a loop-invariant condition to a loop-varying one.
1072 auto *IP = cast<Instruction>(Val: WidenableBR->getCondition());
1073
1074 // The use of umin(all analyzeable exits) instead of latch is subtle, but
1075 // important for profitability. We may have a loop which hasn't been fully
1076 // canonicalized just yet. If the exit we chose to widen is provably never
1077 // taken, we want the widened form to *also* be provably never taken. We
1078 // can't guarantee this as a current unanalyzeable exit may later become
1079 // analyzeable, but we can at least avoid the obvious cases.
1080 const SCEV *MinEC = getMinAnalyzeableBackedgeTakenCount(SE&: *SE, DT&: *DT, L);
1081 if (isa<SCEVCouldNotCompute>(Val: MinEC) || MinEC->getType()->isPointerTy() ||
1082 !SE->isLoopInvariant(S: MinEC, L) ||
1083 !Rewriter.isSafeToExpandAt(S: MinEC, InsertionPoint: IP))
1084 return ChangedLoop;
1085
1086 Rewriter.setInsertPoint(IP);
1087 IRBuilder<> B(IP);
1088
1089 bool InvalidateLoop = false;
1090 Value *MinECV = nullptr; // lazily generated if needed
1091 for (BasicBlock *ExitingBB : ExitingBlocks) {
1092 // If our exiting block exits multiple loops, we can only rewrite the
1093 // innermost one. Otherwise, we're changing how many times the innermost
1094 // loop runs before it exits.
1095 if (LI->getLoopFor(BB: ExitingBB) != L)
1096 continue;
1097
1098 // Can't rewrite non-branch yet.
1099 auto *BI = dyn_cast<CondBrInst>(Val: ExitingBB->getTerminator());
1100 if (!BI)
1101 continue;
1102
1103 // If already constant, nothing to do.
1104 if (isa<Constant>(Val: BI->getCondition()))
1105 continue;
1106
1107 const SCEV *ExitCount = SE->getExitCount(L, ExitingBlock: ExitingBB);
1108 if (isa<SCEVCouldNotCompute>(Val: ExitCount) ||
1109 ExitCount->getType()->isPointerTy() ||
1110 !Rewriter.isSafeToExpandAt(S: ExitCount, InsertionPoint: WidenableBR))
1111 continue;
1112
1113 const bool ExitIfTrue = !L->contains(BB: *succ_begin(BB: ExitingBB));
1114 BasicBlock *ExitBB = BI->getSuccessor(i: ExitIfTrue ? 0 : 1);
1115 if (!ExitBB->getPostdominatingDeoptimizeCall())
1116 continue;
1117
1118 /// Here we can be fairly sure that executing this exit will most likely
1119 /// lead to executing llvm.experimental.deoptimize.
1120 /// This is a profitability heuristic, not a legality constraint.
1121
1122 // If we found a widenable exit condition, do two things:
1123 // 1) fold the widened exit test into the widenable condition
1124 // 2) fold the branch to untaken - avoids infinite looping
1125
1126 Value *ECV = Rewriter.expandCodeFor(SH: ExitCount);
1127 if (!MinECV)
1128 MinECV = Rewriter.expandCodeFor(SH: MinEC);
1129 Value *RHS = MinECV;
1130 if (ECV->getType() != RHS->getType()) {
1131 Type *WiderTy = SE->getWiderType(Ty1: ECV->getType(), Ty2: RHS->getType());
1132 ECV = B.CreateZExt(V: ECV, DestTy: WiderTy);
1133 RHS = B.CreateZExt(V: RHS, DestTy: WiderTy);
1134 }
1135 assert(!Latch || DT->dominates(ExitingBB, Latch));
1136 Value *NewCond = B.CreateICmp(P: ICmpInst::ICMP_UGT, LHS: ECV, RHS);
1137 // Freeze poison or undef to an arbitrary bit pattern to ensure we can
1138 // branch without introducing UB. See NOTE ON POISON/UNDEF above for
1139 // context.
1140 NewCond = B.CreateFreeze(V: NewCond);
1141
1142 widenWidenableBranch(WidenableBR, NewCond);
1143
1144 Value *OldCond = BI->getCondition();
1145 BI->setCondition(ConstantInt::get(Ty: OldCond->getType(), V: !ExitIfTrue));
1146 InvalidateLoop = true;
1147 }
1148
1149 if (InvalidateLoop)
1150 // We just mutated a bunch of loop exits changing there exit counts
1151 // widely. We need to force recomputation of the exit counts given these
1152 // changes. Note that all of the inserted exits are never taken, and
1153 // should be removed next time the CFG is modified.
1154 SE->forgetLoop(L);
1155
1156 // Always return `true` since we have moved the WidenableBR's condition.
1157 return true;
1158}
1159
1160bool LoopPredication::runOnLoop(Loop *Loop) {
1161 L = Loop;
1162
1163 LLVM_DEBUG(dbgs() << "Analyzing ");
1164 LLVM_DEBUG(L->dump());
1165
1166 Module *M = L->getHeader()->getModule();
1167
1168 // There is nothing to do if the module doesn't use guards
1169 auto *GuardDecl =
1170 Intrinsic::getDeclarationIfExists(M, id: Intrinsic::experimental_guard);
1171 bool HasIntrinsicGuards = GuardDecl && !GuardDecl->use_empty();
1172 auto *WCDecl = Intrinsic::getDeclarationIfExists(
1173 M, id: Intrinsic::experimental_widenable_condition);
1174 bool HasWidenableConditions =
1175 Opts.loop_predication_predicate_widenable_branches_to_deopt && WCDecl &&
1176 !WCDecl->use_empty();
1177 if (!HasIntrinsicGuards && !HasWidenableConditions)
1178 return false;
1179
1180 DL = &M->getDataLayout();
1181
1182 Preheader = L->getLoopPreheader();
1183 if (!Preheader)
1184 return false;
1185
1186 auto LatchCheckOpt = parseLoopLatchICmp();
1187 if (!LatchCheckOpt)
1188 return false;
1189 LatchCheck = *LatchCheckOpt;
1190
1191 LLVM_DEBUG(dbgs() << "Latch check:\n");
1192 LLVM_DEBUG(LatchCheck.dump());
1193
1194 if (!isLoopProfitableToPredicate()) {
1195 LLVM_DEBUG(dbgs() << "Loop not profitable to predicate!\n");
1196 return false;
1197 }
1198 // Collect all the guards into a vector and process later, so as not
1199 // to invalidate the instruction iterator.
1200 SmallVector<IntrinsicInst *, 4> Guards;
1201 SmallVector<CondBrInst *, 4> GuardsAsWidenableBranches;
1202 for (const auto BB : L->blocks()) {
1203 for (auto &I : *BB)
1204 if (isGuard(U: &I))
1205 Guards.push_back(Elt: cast<IntrinsicInst>(Val: &I));
1206 if (Opts.loop_predication_predicate_widenable_branches_to_deopt &&
1207 isGuardAsWidenableBranch(U: BB->getTerminator()))
1208 GuardsAsWidenableBranches.push_back(
1209 Elt: cast<CondBrInst>(Val: BB->getTerminator()));
1210 }
1211
1212 SCEVExpander Expander(*SE, "loop-predication");
1213 bool Changed = false;
1214 for (auto *Guard : Guards)
1215 Changed |= widenGuardConditions(Guard, Expander);
1216 for (auto *Guard : GuardsAsWidenableBranches)
1217 Changed |= widenWidenableBranchGuardConditions(BI: Guard, Expander);
1218 Changed |= predicateLoopExits(L, Rewriter&: Expander);
1219
1220 if (MSSAU && VerifyMemorySSA)
1221 MSSAU->getMemorySSA()->verifyMemorySSA();
1222 return Changed;
1223}
1224