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