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