1 | //===- InductiveRangeCheckElimination.cpp - -------------------------------===// |
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 InductiveRangeCheckElimination pass splits a loop's iteration space into |
10 | // three disjoint ranges. It does that in a way such that the loop running in |
11 | // the middle loop provably does not need range checks. As an example, it will |
12 | // convert |
13 | // |
14 | // len = < known positive > |
15 | // for (i = 0; i < n; i++) { |
16 | // if (0 <= i && i < len) { |
17 | // do_something(); |
18 | // } else { |
19 | // throw_out_of_bounds(); |
20 | // } |
21 | // } |
22 | // |
23 | // to |
24 | // |
25 | // len = < known positive > |
26 | // limit = smin(n, len) |
27 | // // no first segment |
28 | // for (i = 0; i < limit; i++) { |
29 | // if (0 <= i && i < len) { // this check is fully redundant |
30 | // do_something(); |
31 | // } else { |
32 | // throw_out_of_bounds(); |
33 | // } |
34 | // } |
35 | // for (i = limit; i < n; i++) { |
36 | // if (0 <= i && i < len) { |
37 | // do_something(); |
38 | // } else { |
39 | // throw_out_of_bounds(); |
40 | // } |
41 | // } |
42 | // |
43 | //===----------------------------------------------------------------------===// |
44 | |
45 | #include "llvm/Transforms/Scalar/InductiveRangeCheckElimination.h" |
46 | #include "llvm/ADT/APInt.h" |
47 | #include "llvm/ADT/ArrayRef.h" |
48 | #include "llvm/ADT/PriorityWorklist.h" |
49 | #include "llvm/ADT/SmallPtrSet.h" |
50 | #include "llvm/ADT/SmallVector.h" |
51 | #include "llvm/ADT/StringRef.h" |
52 | #include "llvm/ADT/Twine.h" |
53 | #include "llvm/Analysis/BlockFrequencyInfo.h" |
54 | #include "llvm/Analysis/BranchProbabilityInfo.h" |
55 | #include "llvm/Analysis/LoopAnalysisManager.h" |
56 | #include "llvm/Analysis/LoopInfo.h" |
57 | #include "llvm/Analysis/ScalarEvolution.h" |
58 | #include "llvm/Analysis/ScalarEvolutionExpressions.h" |
59 | #include "llvm/IR/BasicBlock.h" |
60 | #include "llvm/IR/CFG.h" |
61 | #include "llvm/IR/Constants.h" |
62 | #include "llvm/IR/DerivedTypes.h" |
63 | #include "llvm/IR/Dominators.h" |
64 | #include "llvm/IR/Function.h" |
65 | #include "llvm/IR/IRBuilder.h" |
66 | #include "llvm/IR/InstrTypes.h" |
67 | #include "llvm/IR/Instructions.h" |
68 | #include "llvm/IR/Metadata.h" |
69 | #include "llvm/IR/Module.h" |
70 | #include "llvm/IR/PatternMatch.h" |
71 | #include "llvm/IR/Type.h" |
72 | #include "llvm/IR/Use.h" |
73 | #include "llvm/IR/User.h" |
74 | #include "llvm/IR/Value.h" |
75 | #include "llvm/Support/BranchProbability.h" |
76 | #include "llvm/Support/Casting.h" |
77 | #include "llvm/Support/CommandLine.h" |
78 | #include "llvm/Support/Compiler.h" |
79 | #include "llvm/Support/Debug.h" |
80 | #include "llvm/Support/ErrorHandling.h" |
81 | #include "llvm/Support/raw_ostream.h" |
82 | #include "llvm/Transforms/Utils/BasicBlockUtils.h" |
83 | #include "llvm/Transforms/Utils/Cloning.h" |
84 | #include "llvm/Transforms/Utils/LoopConstrainer.h" |
85 | #include "llvm/Transforms/Utils/LoopSimplify.h" |
86 | #include "llvm/Transforms/Utils/LoopUtils.h" |
87 | #include "llvm/Transforms/Utils/ScalarEvolutionExpander.h" |
88 | #include "llvm/Transforms/Utils/ValueMapper.h" |
89 | #include <algorithm> |
90 | #include <cassert> |
91 | #include <iterator> |
92 | #include <optional> |
93 | #include <utility> |
94 | |
95 | using namespace llvm; |
96 | using namespace llvm::PatternMatch; |
97 | |
98 | static cl::opt<unsigned> LoopSizeCutoff("irce-loop-size-cutoff" , cl::Hidden, |
99 | cl::init(Val: 64)); |
100 | |
101 | static cl::opt<bool> PrintChangedLoops("irce-print-changed-loops" , cl::Hidden, |
102 | cl::init(Val: false)); |
103 | |
104 | static cl::opt<bool> PrintRangeChecks("irce-print-range-checks" , cl::Hidden, |
105 | cl::init(Val: false)); |
106 | |
107 | static cl::opt<bool> SkipProfitabilityChecks("irce-skip-profitability-checks" , |
108 | cl::Hidden, cl::init(Val: false)); |
109 | |
110 | static cl::opt<unsigned> MinRuntimeIterations("irce-min-runtime-iterations" , |
111 | cl::Hidden, cl::init(Val: 10)); |
112 | |
113 | static cl::opt<bool> AllowUnsignedLatchCondition("irce-allow-unsigned-latch" , |
114 | cl::Hidden, cl::init(Val: true)); |
115 | |
116 | static cl::opt<bool> AllowNarrowLatchCondition( |
117 | "irce-allow-narrow-latch" , cl::Hidden, cl::init(Val: true), |
118 | cl::desc("If set to true, IRCE may eliminate wide range checks in loops " |
119 | "with narrow latch condition." )); |
120 | |
121 | static cl::opt<unsigned> MaxTypeSizeForOverflowCheck( |
122 | "irce-max-type-size-for-overflow-check" , cl::Hidden, cl::init(Val: 32), |
123 | cl::desc( |
124 | "Maximum size of range check type for which can be produced runtime " |
125 | "overflow check of its limit's computation" )); |
126 | |
127 | static cl::opt<bool> |
128 | PrintScaledBoundaryRangeChecks("irce-print-scaled-boundary-range-checks" , |
129 | cl::Hidden, cl::init(Val: false)); |
130 | |
131 | #define DEBUG_TYPE "irce" |
132 | |
133 | namespace { |
134 | |
135 | /// An inductive range check is conditional branch in a loop with |
136 | /// |
137 | /// 1. a very cold successor (i.e. the branch jumps to that successor very |
138 | /// rarely) |
139 | /// |
140 | /// and |
141 | /// |
142 | /// 2. a condition that is provably true for some contiguous range of values |
143 | /// taken by the containing loop's induction variable. |
144 | /// |
145 | class InductiveRangeCheck { |
146 | |
147 | const SCEV *Begin = nullptr; |
148 | const SCEV *Step = nullptr; |
149 | const SCEV *End = nullptr; |
150 | Use *CheckUse = nullptr; |
151 | |
152 | static bool parseRangeCheckICmp(Loop *L, ICmpInst *ICI, ScalarEvolution &SE, |
153 | const SCEVAddRecExpr *&Index, |
154 | const SCEV *&End); |
155 | |
156 | static void |
157 | extractRangeChecksFromCond(Loop *L, ScalarEvolution &SE, Use &ConditionUse, |
158 | SmallVectorImpl<InductiveRangeCheck> &Checks, |
159 | SmallPtrSetImpl<Value *> &Visited); |
160 | |
161 | static bool parseIvAgaisntLimit(Loop *L, Value *LHS, Value *RHS, |
162 | ICmpInst::Predicate Pred, ScalarEvolution &SE, |
163 | const SCEVAddRecExpr *&Index, |
164 | const SCEV *&End); |
165 | |
166 | static bool reassociateSubLHS(Loop *L, Value *VariantLHS, Value *InvariantRHS, |
167 | ICmpInst::Predicate Pred, ScalarEvolution &SE, |
168 | const SCEVAddRecExpr *&Index, const SCEV *&End); |
169 | |
170 | public: |
171 | const SCEV *getBegin() const { return Begin; } |
172 | const SCEV *getStep() const { return Step; } |
173 | const SCEV *getEnd() const { return End; } |
174 | |
175 | void print(raw_ostream &OS) const { |
176 | OS << "InductiveRangeCheck:\n" ; |
177 | OS << " Begin: " ; |
178 | Begin->print(OS); |
179 | OS << " Step: " ; |
180 | Step->print(OS); |
181 | OS << " End: " ; |
182 | End->print(OS); |
183 | OS << "\n CheckUse: " ; |
184 | getCheckUse()->getUser()->print(O&: OS); |
185 | OS << " Operand: " << getCheckUse()->getOperandNo() << "\n" ; |
186 | } |
187 | |
188 | LLVM_DUMP_METHOD |
189 | void dump() { |
190 | print(OS&: dbgs()); |
191 | } |
192 | |
193 | Use *getCheckUse() const { return CheckUse; } |
194 | |
195 | /// Represents an signed integer range [Range.getBegin(), Range.getEnd()). If |
196 | /// R.getEnd() le R.getBegin(), then R denotes the empty range. |
197 | |
198 | class Range { |
199 | const SCEV *Begin; |
200 | const SCEV *End; |
201 | |
202 | public: |
203 | Range(const SCEV *Begin, const SCEV *End) : Begin(Begin), End(End) { |
204 | assert(Begin->getType() == End->getType() && "ill-typed range!" ); |
205 | } |
206 | |
207 | Type *getType() const { return Begin->getType(); } |
208 | const SCEV *getBegin() const { return Begin; } |
209 | const SCEV *getEnd() const { return End; } |
210 | bool isEmpty(ScalarEvolution &SE, bool IsSigned) const { |
211 | if (Begin == End) |
212 | return true; |
213 | if (IsSigned) |
214 | return SE.isKnownPredicate(Pred: ICmpInst::ICMP_SGE, LHS: Begin, RHS: End); |
215 | else |
216 | return SE.isKnownPredicate(Pred: ICmpInst::ICMP_UGE, LHS: Begin, RHS: End); |
217 | } |
218 | }; |
219 | |
220 | /// This is the value the condition of the branch needs to evaluate to for the |
221 | /// branch to take the hot successor (see (1) above). |
222 | bool getPassingDirection() { return true; } |
223 | |
224 | /// Computes a range for the induction variable (IndVar) in which the range |
225 | /// check is redundant and can be constant-folded away. The induction |
226 | /// variable is not required to be the canonical {0,+,1} induction variable. |
227 | std::optional<Range> computeSafeIterationSpace(ScalarEvolution &SE, |
228 | const SCEVAddRecExpr *IndVar, |
229 | bool IsLatchSigned) const; |
230 | |
231 | /// Parse out a set of inductive range checks from \p BI and append them to \p |
232 | /// Checks. |
233 | /// |
234 | /// NB! There may be conditions feeding into \p BI that aren't inductive range |
235 | /// checks, and hence don't end up in \p Checks. |
236 | static void extractRangeChecksFromBranch( |
237 | BranchInst *BI, Loop *L, ScalarEvolution &SE, BranchProbabilityInfo *BPI, |
238 | SmallVectorImpl<InductiveRangeCheck> &Checks, bool &Changed); |
239 | }; |
240 | |
241 | class InductiveRangeCheckElimination { |
242 | ScalarEvolution &SE; |
243 | BranchProbabilityInfo *BPI; |
244 | DominatorTree &DT; |
245 | LoopInfo &LI; |
246 | |
247 | using GetBFIFunc = |
248 | std::optional<llvm::function_ref<llvm::BlockFrequencyInfo &()>>; |
249 | GetBFIFunc GetBFI; |
250 | |
251 | // Returns true if it is profitable to do a transform basing on estimation of |
252 | // number of iterations. |
253 | bool isProfitableToTransform(const Loop &L, LoopStructure &LS); |
254 | |
255 | public: |
256 | InductiveRangeCheckElimination(ScalarEvolution &SE, |
257 | BranchProbabilityInfo *BPI, DominatorTree &DT, |
258 | LoopInfo &LI, GetBFIFunc GetBFI = std::nullopt) |
259 | : SE(SE), BPI(BPI), DT(DT), LI(LI), GetBFI(GetBFI) {} |
260 | |
261 | bool run(Loop *L, function_ref<void(Loop *, bool)> LPMAddNewLoop); |
262 | }; |
263 | |
264 | } // end anonymous namespace |
265 | |
266 | /// Parse a single ICmp instruction, `ICI`, into a range check. If `ICI` cannot |
267 | /// be interpreted as a range check, return false. Otherwise set `Index` to the |
268 | /// SCEV being range checked, and set `End` to the upper or lower limit `Index` |
269 | /// is being range checked. |
270 | bool InductiveRangeCheck::parseRangeCheckICmp(Loop *L, ICmpInst *ICI, |
271 | ScalarEvolution &SE, |
272 | const SCEVAddRecExpr *&Index, |
273 | const SCEV *&End) { |
274 | auto IsLoopInvariant = [&SE, L](Value *V) { |
275 | return SE.isLoopInvariant(S: SE.getSCEV(V), L); |
276 | }; |
277 | |
278 | ICmpInst::Predicate Pred = ICI->getPredicate(); |
279 | Value *LHS = ICI->getOperand(i_nocapture: 0); |
280 | Value *RHS = ICI->getOperand(i_nocapture: 1); |
281 | |
282 | // Canonicalize to the `Index Pred Invariant` comparison |
283 | if (IsLoopInvariant(LHS)) { |
284 | std::swap(a&: LHS, b&: RHS); |
285 | Pred = CmpInst::getSwappedPredicate(pred: Pred); |
286 | } else if (!IsLoopInvariant(RHS)) |
287 | // Both LHS and RHS are loop variant |
288 | return false; |
289 | |
290 | if (parseIvAgaisntLimit(L, LHS, RHS, Pred, SE, Index, End)) |
291 | return true; |
292 | |
293 | if (reassociateSubLHS(L, VariantLHS: LHS, InvariantRHS: RHS, Pred, SE, Index, End)) |
294 | return true; |
295 | |
296 | // TODO: support ReassociateAddLHS |
297 | return false; |
298 | } |
299 | |
300 | // Try to parse range check in the form of "IV vs Limit" |
301 | bool InductiveRangeCheck::parseIvAgaisntLimit(Loop *L, Value *LHS, Value *RHS, |
302 | ICmpInst::Predicate Pred, |
303 | ScalarEvolution &SE, |
304 | const SCEVAddRecExpr *&Index, |
305 | const SCEV *&End) { |
306 | |
307 | auto SIntMaxSCEV = [&](Type *T) { |
308 | unsigned BitWidth = cast<IntegerType>(Val: T)->getBitWidth(); |
309 | return SE.getConstant(Val: APInt::getSignedMaxValue(numBits: BitWidth)); |
310 | }; |
311 | |
312 | const auto *AddRec = dyn_cast<SCEVAddRecExpr>(Val: SE.getSCEV(V: LHS)); |
313 | if (!AddRec) |
314 | return false; |
315 | |
316 | // We strengthen "0 <= I" to "0 <= I < INT_SMAX" and "I < L" to "0 <= I < L". |
317 | // We can potentially do much better here. |
318 | // If we want to adjust upper bound for the unsigned range check as we do it |
319 | // for signed one, we will need to pick Unsigned max |
320 | switch (Pred) { |
321 | default: |
322 | return false; |
323 | |
324 | case ICmpInst::ICMP_SGE: |
325 | if (match(V: RHS, P: m_ConstantInt<0>())) { |
326 | Index = AddRec; |
327 | End = SIntMaxSCEV(Index->getType()); |
328 | return true; |
329 | } |
330 | return false; |
331 | |
332 | case ICmpInst::ICMP_SGT: |
333 | if (match(V: RHS, P: m_ConstantInt<-1>())) { |
334 | Index = AddRec; |
335 | End = SIntMaxSCEV(Index->getType()); |
336 | return true; |
337 | } |
338 | return false; |
339 | |
340 | case ICmpInst::ICMP_SLT: |
341 | case ICmpInst::ICMP_ULT: |
342 | Index = AddRec; |
343 | End = SE.getSCEV(V: RHS); |
344 | return true; |
345 | |
346 | case ICmpInst::ICMP_SLE: |
347 | case ICmpInst::ICMP_ULE: |
348 | const SCEV *One = SE.getOne(Ty: RHS->getType()); |
349 | const SCEV *RHSS = SE.getSCEV(V: RHS); |
350 | bool Signed = Pred == ICmpInst::ICMP_SLE; |
351 | if (SE.willNotOverflow(BinOp: Instruction::BinaryOps::Add, Signed, LHS: RHSS, RHS: One)) { |
352 | Index = AddRec; |
353 | End = SE.getAddExpr(LHS: RHSS, RHS: One); |
354 | return true; |
355 | } |
356 | return false; |
357 | } |
358 | |
359 | llvm_unreachable("default clause returns!" ); |
360 | } |
361 | |
362 | // Try to parse range check in the form of "IV - Offset vs Limit" or "Offset - |
363 | // IV vs Limit" |
364 | bool InductiveRangeCheck::reassociateSubLHS( |
365 | Loop *L, Value *VariantLHS, Value *InvariantRHS, ICmpInst::Predicate Pred, |
366 | ScalarEvolution &SE, const SCEVAddRecExpr *&Index, const SCEV *&End) { |
367 | Value *LHS, *RHS; |
368 | if (!match(V: VariantLHS, P: m_Sub(L: m_Value(V&: LHS), R: m_Value(V&: RHS)))) |
369 | return false; |
370 | |
371 | const SCEV *IV = SE.getSCEV(V: LHS); |
372 | const SCEV *Offset = SE.getSCEV(V: RHS); |
373 | const SCEV *Limit = SE.getSCEV(V: InvariantRHS); |
374 | |
375 | bool OffsetSubtracted = false; |
376 | if (SE.isLoopInvariant(S: IV, L)) |
377 | // "Offset - IV vs Limit" |
378 | std::swap(a&: IV, b&: Offset); |
379 | else if (SE.isLoopInvariant(S: Offset, L)) |
380 | // "IV - Offset vs Limit" |
381 | OffsetSubtracted = true; |
382 | else |
383 | return false; |
384 | |
385 | const auto *AddRec = dyn_cast<SCEVAddRecExpr>(Val: IV); |
386 | if (!AddRec) |
387 | return false; |
388 | |
389 | // In order to turn "IV - Offset < Limit" into "IV < Limit + Offset", we need |
390 | // to be able to freely move values from left side of inequality to right side |
391 | // (just as in normal linear arithmetics). Overflows make things much more |
392 | // complicated, so we want to avoid this. |
393 | // |
394 | // Let's prove that the initial subtraction doesn't overflow with all IV's |
395 | // values from the safe range constructed for that check. |
396 | // |
397 | // [Case 1] IV - Offset < Limit |
398 | // It doesn't overflow if: |
399 | // SINT_MIN <= IV - Offset <= SINT_MAX |
400 | // In terms of scaled SINT we need to prove: |
401 | // SINT_MIN + Offset <= IV <= SINT_MAX + Offset |
402 | // Safe range will be constructed: |
403 | // 0 <= IV < Limit + Offset |
404 | // It means that 'IV - Offset' doesn't underflow, because: |
405 | // SINT_MIN + Offset < 0 <= IV |
406 | // and doesn't overflow: |
407 | // IV < Limit + Offset <= SINT_MAX + Offset |
408 | // |
409 | // [Case 2] Offset - IV > Limit |
410 | // It doesn't overflow if: |
411 | // SINT_MIN <= Offset - IV <= SINT_MAX |
412 | // In terms of scaled SINT we need to prove: |
413 | // -SINT_MIN >= IV - Offset >= -SINT_MAX |
414 | // Offset - SINT_MIN >= IV >= Offset - SINT_MAX |
415 | // Safe range will be constructed: |
416 | // 0 <= IV < Offset - Limit |
417 | // It means that 'Offset - IV' doesn't underflow, because |
418 | // Offset - SINT_MAX < 0 <= IV |
419 | // and doesn't overflow: |
420 | // IV < Offset - Limit <= Offset - SINT_MIN |
421 | // |
422 | // For the computed upper boundary of the IV's range (Offset +/- Limit) we |
423 | // don't know exactly whether it overflows or not. So if we can't prove this |
424 | // fact at compile time, we scale boundary computations to a wider type with |
425 | // the intention to add runtime overflow check. |
426 | |
427 | auto getExprScaledIfOverflow = [&](Instruction::BinaryOps BinOp, |
428 | const SCEV *LHS, |
429 | const SCEV *RHS) -> const SCEV * { |
430 | const SCEV *(ScalarEvolution::*Operation)(const SCEV *, const SCEV *, |
431 | SCEV::NoWrapFlags, unsigned); |
432 | switch (BinOp) { |
433 | default: |
434 | llvm_unreachable("Unsupported binary op" ); |
435 | case Instruction::Add: |
436 | Operation = &ScalarEvolution::getAddExpr; |
437 | break; |
438 | case Instruction::Sub: |
439 | Operation = &ScalarEvolution::getMinusSCEV; |
440 | break; |
441 | } |
442 | |
443 | if (SE.willNotOverflow(BinOp, Signed: ICmpInst::isSigned(predicate: Pred), LHS, RHS, |
444 | CtxI: cast<Instruction>(Val: VariantLHS))) |
445 | return (SE.*Operation)(LHS, RHS, SCEV::FlagAnyWrap, 0); |
446 | |
447 | // We couldn't prove that the expression does not overflow. |
448 | // Than scale it to a wider type to check overflow at runtime. |
449 | auto *Ty = cast<IntegerType>(Val: LHS->getType()); |
450 | if (Ty->getBitWidth() > MaxTypeSizeForOverflowCheck) |
451 | return nullptr; |
452 | |
453 | auto WideTy = IntegerType::get(C&: Ty->getContext(), NumBits: Ty->getBitWidth() * 2); |
454 | return (SE.*Operation)(SE.getSignExtendExpr(Op: LHS, Ty: WideTy), |
455 | SE.getSignExtendExpr(Op: RHS, Ty: WideTy), SCEV::FlagAnyWrap, |
456 | 0); |
457 | }; |
458 | |
459 | if (OffsetSubtracted) |
460 | // "IV - Offset < Limit" -> "IV" < Offset + Limit |
461 | Limit = getExprScaledIfOverflow(Instruction::BinaryOps::Add, Offset, Limit); |
462 | else { |
463 | // "Offset - IV > Limit" -> "IV" < Offset - Limit |
464 | Limit = getExprScaledIfOverflow(Instruction::BinaryOps::Sub, Offset, Limit); |
465 | Pred = ICmpInst::getSwappedPredicate(pred: Pred); |
466 | } |
467 | |
468 | if (Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_SLE) { |
469 | // "Expr <= Limit" -> "Expr < Limit + 1" |
470 | if (Pred == ICmpInst::ICMP_SLE && Limit) |
471 | Limit = getExprScaledIfOverflow(Instruction::BinaryOps::Add, Limit, |
472 | SE.getOne(Ty: Limit->getType())); |
473 | if (Limit) { |
474 | Index = AddRec; |
475 | End = Limit; |
476 | return true; |
477 | } |
478 | } |
479 | return false; |
480 | } |
481 | |
482 | void InductiveRangeCheck::( |
483 | Loop *L, ScalarEvolution &SE, Use &ConditionUse, |
484 | SmallVectorImpl<InductiveRangeCheck> &Checks, |
485 | SmallPtrSetImpl<Value *> &Visited) { |
486 | Value *Condition = ConditionUse.get(); |
487 | if (!Visited.insert(Ptr: Condition).second) |
488 | return; |
489 | |
490 | // TODO: Do the same for OR, XOR, NOT etc? |
491 | if (match(V: Condition, P: m_LogicalAnd(L: m_Value(), R: m_Value()))) { |
492 | extractRangeChecksFromCond(L, SE, ConditionUse&: cast<User>(Val: Condition)->getOperandUse(i: 0), |
493 | Checks, Visited); |
494 | extractRangeChecksFromCond(L, SE, ConditionUse&: cast<User>(Val: Condition)->getOperandUse(i: 1), |
495 | Checks, Visited); |
496 | return; |
497 | } |
498 | |
499 | ICmpInst *ICI = dyn_cast<ICmpInst>(Val: Condition); |
500 | if (!ICI) |
501 | return; |
502 | |
503 | const SCEV *End = nullptr; |
504 | const SCEVAddRecExpr *IndexAddRec = nullptr; |
505 | if (!parseRangeCheckICmp(L, ICI, SE, Index&: IndexAddRec, End)) |
506 | return; |
507 | |
508 | assert(IndexAddRec && "IndexAddRec was not computed" ); |
509 | assert(End && "End was not computed" ); |
510 | |
511 | if ((IndexAddRec->getLoop() != L) || !IndexAddRec->isAffine()) |
512 | return; |
513 | |
514 | InductiveRangeCheck IRC; |
515 | IRC.End = End; |
516 | IRC.Begin = IndexAddRec->getStart(); |
517 | IRC.Step = IndexAddRec->getStepRecurrence(SE); |
518 | IRC.CheckUse = &ConditionUse; |
519 | Checks.push_back(Elt: IRC); |
520 | } |
521 | |
522 | void InductiveRangeCheck::( |
523 | BranchInst *BI, Loop *L, ScalarEvolution &SE, BranchProbabilityInfo *BPI, |
524 | SmallVectorImpl<InductiveRangeCheck> &Checks, bool &Changed) { |
525 | if (BI->isUnconditional() || BI->getParent() == L->getLoopLatch()) |
526 | return; |
527 | |
528 | unsigned IndexLoopSucc = L->contains(BB: BI->getSuccessor(i: 0)) ? 0 : 1; |
529 | assert(L->contains(BI->getSuccessor(IndexLoopSucc)) && |
530 | "No edges coming to loop?" ); |
531 | BranchProbability LikelyTaken(15, 16); |
532 | |
533 | if (!SkipProfitabilityChecks && BPI && |
534 | BPI->getEdgeProbability(Src: BI->getParent(), IndexInSuccessors: IndexLoopSucc) < LikelyTaken) |
535 | return; |
536 | |
537 | // IRCE expects branch's true edge comes to loop. Invert branch for opposite |
538 | // case. |
539 | if (IndexLoopSucc != 0) { |
540 | IRBuilder<> Builder(BI); |
541 | InvertBranch(PBI: BI, Builder); |
542 | if (BPI) |
543 | BPI->swapSuccEdgesProbabilities(Src: BI->getParent()); |
544 | Changed = true; |
545 | } |
546 | |
547 | SmallPtrSet<Value *, 8> Visited; |
548 | InductiveRangeCheck::extractRangeChecksFromCond(L, SE, ConditionUse&: BI->getOperandUse(i: 0), |
549 | Checks, Visited); |
550 | } |
551 | |
552 | /// If the type of \p S matches with \p Ty, return \p S. Otherwise, return |
553 | /// signed or unsigned extension of \p S to type \p Ty. |
554 | static const SCEV *NoopOrExtend(const SCEV *S, Type *Ty, ScalarEvolution &SE, |
555 | bool Signed) { |
556 | return Signed ? SE.getNoopOrSignExtend(V: S, Ty) : SE.getNoopOrZeroExtend(V: S, Ty); |
557 | } |
558 | |
559 | // Compute a safe set of limits for the main loop to run in -- effectively the |
560 | // intersection of `Range' and the iteration space of the original loop. |
561 | // Return std::nullopt if unable to compute the set of subranges. |
562 | static std::optional<LoopConstrainer::SubRanges> |
563 | calculateSubRanges(ScalarEvolution &SE, const Loop &L, |
564 | InductiveRangeCheck::Range &Range, |
565 | const LoopStructure &MainLoopStructure) { |
566 | auto *RTy = cast<IntegerType>(Val: Range.getType()); |
567 | // We only support wide range checks and narrow latches. |
568 | if (!AllowNarrowLatchCondition && RTy != MainLoopStructure.ExitCountTy) |
569 | return std::nullopt; |
570 | if (RTy->getBitWidth() < MainLoopStructure.ExitCountTy->getBitWidth()) |
571 | return std::nullopt; |
572 | |
573 | LoopConstrainer::SubRanges Result; |
574 | |
575 | bool IsSignedPredicate = MainLoopStructure.IsSignedPredicate; |
576 | // I think we can be more aggressive here and make this nuw / nsw if the |
577 | // addition that feeds into the icmp for the latch's terminating branch is nuw |
578 | // / nsw. In any case, a wrapping 2's complement addition is safe. |
579 | const SCEV *Start = NoopOrExtend(S: SE.getSCEV(V: MainLoopStructure.IndVarStart), |
580 | Ty: RTy, SE, Signed: IsSignedPredicate); |
581 | const SCEV *End = NoopOrExtend(S: SE.getSCEV(V: MainLoopStructure.LoopExitAt), Ty: RTy, |
582 | SE, Signed: IsSignedPredicate); |
583 | |
584 | bool Increasing = MainLoopStructure.IndVarIncreasing; |
585 | |
586 | // We compute `Smallest` and `Greatest` such that [Smallest, Greatest), or |
587 | // [Smallest, GreatestSeen] is the range of values the induction variable |
588 | // takes. |
589 | |
590 | const SCEV *Smallest = nullptr, *Greatest = nullptr, *GreatestSeen = nullptr; |
591 | |
592 | const SCEV *One = SE.getOne(Ty: RTy); |
593 | if (Increasing) { |
594 | Smallest = Start; |
595 | Greatest = End; |
596 | // No overflow, because the range [Smallest, GreatestSeen] is not empty. |
597 | GreatestSeen = SE.getMinusSCEV(LHS: End, RHS: One); |
598 | } else { |
599 | // These two computations may sign-overflow. Here is why that is okay: |
600 | // |
601 | // We know that the induction variable does not sign-overflow on any |
602 | // iteration except the last one, and it starts at `Start` and ends at |
603 | // `End`, decrementing by one every time. |
604 | // |
605 | // * if `Smallest` sign-overflows we know `End` is `INT_SMAX`. Since the |
606 | // induction variable is decreasing we know that the smallest value |
607 | // the loop body is actually executed with is `INT_SMIN` == `Smallest`. |
608 | // |
609 | // * if `Greatest` sign-overflows, we know it can only be `INT_SMIN`. In |
610 | // that case, `Clamp` will always return `Smallest` and |
611 | // [`Result.LowLimit`, `Result.HighLimit`) = [`Smallest`, `Smallest`) |
612 | // will be an empty range. Returning an empty range is always safe. |
613 | |
614 | Smallest = SE.getAddExpr(LHS: End, RHS: One); |
615 | Greatest = SE.getAddExpr(LHS: Start, RHS: One); |
616 | GreatestSeen = Start; |
617 | } |
618 | |
619 | auto Clamp = [&SE, Smallest, Greatest, IsSignedPredicate](const SCEV *S) { |
620 | return IsSignedPredicate |
621 | ? SE.getSMaxExpr(LHS: Smallest, RHS: SE.getSMinExpr(LHS: Greatest, RHS: S)) |
622 | : SE.getUMaxExpr(LHS: Smallest, RHS: SE.getUMinExpr(LHS: Greatest, RHS: S)); |
623 | }; |
624 | |
625 | // In some cases we can prove that we don't need a pre or post loop. |
626 | ICmpInst::Predicate PredLE = |
627 | IsSignedPredicate ? ICmpInst::ICMP_SLE : ICmpInst::ICMP_ULE; |
628 | ICmpInst::Predicate PredLT = |
629 | IsSignedPredicate ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT; |
630 | |
631 | bool ProvablyNoPreloop = |
632 | SE.isKnownPredicate(Pred: PredLE, LHS: Range.getBegin(), RHS: Smallest); |
633 | if (!ProvablyNoPreloop) |
634 | Result.LowLimit = Clamp(Range.getBegin()); |
635 | |
636 | bool ProvablyNoPostLoop = |
637 | SE.isKnownPredicate(Pred: PredLT, LHS: GreatestSeen, RHS: Range.getEnd()); |
638 | if (!ProvablyNoPostLoop) |
639 | Result.HighLimit = Clamp(Range.getEnd()); |
640 | |
641 | return Result; |
642 | } |
643 | |
644 | /// Computes and returns a range of values for the induction variable (IndVar) |
645 | /// in which the range check can be safely elided. If it cannot compute such a |
646 | /// range, returns std::nullopt. |
647 | std::optional<InductiveRangeCheck::Range> |
648 | InductiveRangeCheck::computeSafeIterationSpace(ScalarEvolution &SE, |
649 | const SCEVAddRecExpr *IndVar, |
650 | bool IsLatchSigned) const { |
651 | // We can deal when types of latch check and range checks don't match in case |
652 | // if latch check is more narrow. |
653 | auto *IVType = dyn_cast<IntegerType>(Val: IndVar->getType()); |
654 | auto *RCType = dyn_cast<IntegerType>(Val: getBegin()->getType()); |
655 | auto *EndType = dyn_cast<IntegerType>(Val: getEnd()->getType()); |
656 | // Do not work with pointer types. |
657 | if (!IVType || !RCType) |
658 | return std::nullopt; |
659 | if (IVType->getBitWidth() > RCType->getBitWidth()) |
660 | return std::nullopt; |
661 | |
662 | // IndVar is of the form "A + B * I" (where "I" is the canonical induction |
663 | // variable, that may or may not exist as a real llvm::Value in the loop) and |
664 | // this inductive range check is a range check on the "C + D * I" ("C" is |
665 | // getBegin() and "D" is getStep()). We rewrite the value being range |
666 | // checked to "M + N * IndVar" where "N" = "D * B^(-1)" and "M" = "C - NA". |
667 | // |
668 | // The actual inequalities we solve are of the form |
669 | // |
670 | // 0 <= M + 1 * IndVar < L given L >= 0 (i.e. N == 1) |
671 | // |
672 | // Here L stands for upper limit of the safe iteration space. |
673 | // The inequality is satisfied by (0 - M) <= IndVar < (L - M). To avoid |
674 | // overflows when calculating (0 - M) and (L - M) we, depending on type of |
675 | // IV's iteration space, limit the calculations by borders of the iteration |
676 | // space. For example, if IndVar is unsigned, (0 - M) overflows for any M > 0. |
677 | // If we figured out that "anything greater than (-M) is safe", we strengthen |
678 | // this to "everything greater than 0 is safe", assuming that values between |
679 | // -M and 0 just do not exist in unsigned iteration space, and we don't want |
680 | // to deal with overflown values. |
681 | |
682 | if (!IndVar->isAffine()) |
683 | return std::nullopt; |
684 | |
685 | const SCEV *A = NoopOrExtend(S: IndVar->getStart(), Ty: RCType, SE, Signed: IsLatchSigned); |
686 | const SCEVConstant *B = dyn_cast<SCEVConstant>( |
687 | Val: NoopOrExtend(S: IndVar->getStepRecurrence(SE), Ty: RCType, SE, Signed: IsLatchSigned)); |
688 | if (!B) |
689 | return std::nullopt; |
690 | assert(!B->isZero() && "Recurrence with zero step?" ); |
691 | |
692 | const SCEV *C = getBegin(); |
693 | const SCEVConstant *D = dyn_cast<SCEVConstant>(Val: getStep()); |
694 | if (D != B) |
695 | return std::nullopt; |
696 | |
697 | assert(!D->getValue()->isZero() && "Recurrence with zero step?" ); |
698 | unsigned BitWidth = RCType->getBitWidth(); |
699 | const SCEV *SIntMax = SE.getConstant(Val: APInt::getSignedMaxValue(numBits: BitWidth)); |
700 | const SCEV *SIntMin = SE.getConstant(Val: APInt::getSignedMinValue(numBits: BitWidth)); |
701 | |
702 | // Subtract Y from X so that it does not go through border of the IV |
703 | // iteration space. Mathematically, it is equivalent to: |
704 | // |
705 | // ClampedSubtract(X, Y) = min(max(X - Y, INT_MIN), INT_MAX). [1] |
706 | // |
707 | // In [1], 'X - Y' is a mathematical subtraction (result is not bounded to |
708 | // any width of bit grid). But after we take min/max, the result is |
709 | // guaranteed to be within [INT_MIN, INT_MAX]. |
710 | // |
711 | // In [1], INT_MAX and INT_MIN are respectively signed and unsigned max/min |
712 | // values, depending on type of latch condition that defines IV iteration |
713 | // space. |
714 | auto ClampedSubtract = [&](const SCEV *X, const SCEV *Y) { |
715 | // FIXME: The current implementation assumes that X is in [0, SINT_MAX]. |
716 | // This is required to ensure that SINT_MAX - X does not overflow signed and |
717 | // that X - Y does not overflow unsigned if Y is negative. Can we lift this |
718 | // restriction and make it work for negative X either? |
719 | if (IsLatchSigned) { |
720 | // X is a number from signed range, Y is interpreted as signed. |
721 | // Even if Y is SINT_MAX, (X - Y) does not reach SINT_MIN. So the only |
722 | // thing we should care about is that we didn't cross SINT_MAX. |
723 | // So, if Y is positive, we subtract Y safely. |
724 | // Rule 1: Y > 0 ---> Y. |
725 | // If 0 <= -Y <= (SINT_MAX - X), we subtract Y safely. |
726 | // Rule 2: Y >=s (X - SINT_MAX) ---> Y. |
727 | // If 0 <= (SINT_MAX - X) < -Y, we can only subtract (X - SINT_MAX). |
728 | // Rule 3: Y <s (X - SINT_MAX) ---> (X - SINT_MAX). |
729 | // It gives us smax(Y, X - SINT_MAX) to subtract in all cases. |
730 | const SCEV *XMinusSIntMax = SE.getMinusSCEV(LHS: X, RHS: SIntMax); |
731 | return SE.getMinusSCEV(LHS: X, RHS: SE.getSMaxExpr(LHS: Y, RHS: XMinusSIntMax), |
732 | Flags: SCEV::FlagNSW); |
733 | } else |
734 | // X is a number from unsigned range, Y is interpreted as signed. |
735 | // Even if Y is SINT_MIN, (X - Y) does not reach UINT_MAX. So the only |
736 | // thing we should care about is that we didn't cross zero. |
737 | // So, if Y is negative, we subtract Y safely. |
738 | // Rule 1: Y <s 0 ---> Y. |
739 | // If 0 <= Y <= X, we subtract Y safely. |
740 | // Rule 2: Y <=s X ---> Y. |
741 | // If 0 <= X < Y, we should stop at 0 and can only subtract X. |
742 | // Rule 3: Y >s X ---> X. |
743 | // It gives us smin(X, Y) to subtract in all cases. |
744 | return SE.getMinusSCEV(LHS: X, RHS: SE.getSMinExpr(LHS: X, RHS: Y), Flags: SCEV::FlagNUW); |
745 | }; |
746 | const SCEV *M = SE.getMinusSCEV(LHS: C, RHS: A); |
747 | const SCEV *Zero = SE.getZero(Ty: M->getType()); |
748 | |
749 | // This function returns SCEV equal to 1 if X is non-negative 0 otherwise. |
750 | auto SCEVCheckNonNegative = [&](const SCEV *X) { |
751 | const Loop *L = IndVar->getLoop(); |
752 | const SCEV *Zero = SE.getZero(Ty: X->getType()); |
753 | const SCEV *One = SE.getOne(Ty: X->getType()); |
754 | // Can we trivially prove that X is a non-negative or negative value? |
755 | if (isKnownNonNegativeInLoop(S: X, L, SE)) |
756 | return One; |
757 | else if (isKnownNegativeInLoop(S: X, L, SE)) |
758 | return Zero; |
759 | // If not, we will have to figure it out during the execution. |
760 | // Function smax(smin(X, 0), -1) + 1 equals to 1 if X >= 0 and 0 if X < 0. |
761 | const SCEV *NegOne = SE.getNegativeSCEV(V: One); |
762 | return SE.getAddExpr(LHS: SE.getSMaxExpr(LHS: SE.getSMinExpr(LHS: X, RHS: Zero), RHS: NegOne), RHS: One); |
763 | }; |
764 | |
765 | // This function returns SCEV equal to 1 if X will not overflow in terms of |
766 | // range check type, 0 otherwise. |
767 | auto SCEVCheckWillNotOverflow = [&](const SCEV *X) { |
768 | // X doesn't overflow if SINT_MAX >= X. |
769 | // Then if (SINT_MAX - X) >= 0, X doesn't overflow |
770 | const SCEV *SIntMaxExt = SE.getSignExtendExpr(Op: SIntMax, Ty: X->getType()); |
771 | const SCEV *OverflowCheck = |
772 | SCEVCheckNonNegative(SE.getMinusSCEV(LHS: SIntMaxExt, RHS: X)); |
773 | |
774 | // X doesn't underflow if X >= SINT_MIN. |
775 | // Then if (X - SINT_MIN) >= 0, X doesn't underflow |
776 | const SCEV *SIntMinExt = SE.getSignExtendExpr(Op: SIntMin, Ty: X->getType()); |
777 | const SCEV *UnderflowCheck = |
778 | SCEVCheckNonNegative(SE.getMinusSCEV(LHS: X, RHS: SIntMinExt)); |
779 | |
780 | return SE.getMulExpr(LHS: OverflowCheck, RHS: UnderflowCheck); |
781 | }; |
782 | |
783 | // FIXME: Current implementation of ClampedSubtract implicitly assumes that |
784 | // X is non-negative (in sense of a signed value). We need to re-implement |
785 | // this function in a way that it will correctly handle negative X as well. |
786 | // We use it twice: for X = 0 everything is fine, but for X = getEnd() we can |
787 | // end up with a negative X and produce wrong results. So currently we ensure |
788 | // that if getEnd() is negative then both ends of the safe range are zero. |
789 | // Note that this may pessimize elimination of unsigned range checks against |
790 | // negative values. |
791 | const SCEV *REnd = getEnd(); |
792 | const SCEV *EndWillNotOverflow = SE.getOne(Ty: RCType); |
793 | |
794 | auto PrintRangeCheck = [&](raw_ostream &OS) { |
795 | auto L = IndVar->getLoop(); |
796 | OS << "irce: in function " ; |
797 | OS << L->getHeader()->getParent()->getName(); |
798 | OS << ", in " ; |
799 | L->print(OS); |
800 | OS << "there is range check with scaled boundary:\n" ; |
801 | print(OS); |
802 | }; |
803 | |
804 | if (EndType->getBitWidth() > RCType->getBitWidth()) { |
805 | assert(EndType->getBitWidth() == RCType->getBitWidth() * 2); |
806 | if (PrintScaledBoundaryRangeChecks) |
807 | PrintRangeCheck(errs()); |
808 | // End is computed with extended type but will be truncated to a narrow one |
809 | // type of range check. Therefore we need a check that the result will not |
810 | // overflow in terms of narrow type. |
811 | EndWillNotOverflow = |
812 | SE.getTruncateExpr(Op: SCEVCheckWillNotOverflow(REnd), Ty: RCType); |
813 | REnd = SE.getTruncateExpr(Op: REnd, Ty: RCType); |
814 | } |
815 | |
816 | const SCEV *RuntimeChecks = |
817 | SE.getMulExpr(LHS: SCEVCheckNonNegative(REnd), RHS: EndWillNotOverflow); |
818 | const SCEV *Begin = SE.getMulExpr(LHS: ClampedSubtract(Zero, M), RHS: RuntimeChecks); |
819 | const SCEV *End = SE.getMulExpr(LHS: ClampedSubtract(REnd, M), RHS: RuntimeChecks); |
820 | |
821 | return InductiveRangeCheck::Range(Begin, End); |
822 | } |
823 | |
824 | static std::optional<InductiveRangeCheck::Range> |
825 | IntersectSignedRange(ScalarEvolution &SE, |
826 | const std::optional<InductiveRangeCheck::Range> &R1, |
827 | const InductiveRangeCheck::Range &R2) { |
828 | if (R2.isEmpty(SE, /* IsSigned */ true)) |
829 | return std::nullopt; |
830 | if (!R1) |
831 | return R2; |
832 | auto &R1Value = *R1; |
833 | // We never return empty ranges from this function, and R1 is supposed to be |
834 | // a result of intersection. Thus, R1 is never empty. |
835 | assert(!R1Value.isEmpty(SE, /* IsSigned */ true) && |
836 | "We should never have empty R1!" ); |
837 | |
838 | // TODO: we could widen the smaller range and have this work; but for now we |
839 | // bail out to keep things simple. |
840 | if (R1Value.getType() != R2.getType()) |
841 | return std::nullopt; |
842 | |
843 | const SCEV *NewBegin = SE.getSMaxExpr(LHS: R1Value.getBegin(), RHS: R2.getBegin()); |
844 | const SCEV *NewEnd = SE.getSMinExpr(LHS: R1Value.getEnd(), RHS: R2.getEnd()); |
845 | |
846 | // If the resulting range is empty, just return std::nullopt. |
847 | auto Ret = InductiveRangeCheck::Range(NewBegin, NewEnd); |
848 | if (Ret.isEmpty(SE, /* IsSigned */ true)) |
849 | return std::nullopt; |
850 | return Ret; |
851 | } |
852 | |
853 | static std::optional<InductiveRangeCheck::Range> |
854 | IntersectUnsignedRange(ScalarEvolution &SE, |
855 | const std::optional<InductiveRangeCheck::Range> &R1, |
856 | const InductiveRangeCheck::Range &R2) { |
857 | if (R2.isEmpty(SE, /* IsSigned */ false)) |
858 | return std::nullopt; |
859 | if (!R1) |
860 | return R2; |
861 | auto &R1Value = *R1; |
862 | // We never return empty ranges from this function, and R1 is supposed to be |
863 | // a result of intersection. Thus, R1 is never empty. |
864 | assert(!R1Value.isEmpty(SE, /* IsSigned */ false) && |
865 | "We should never have empty R1!" ); |
866 | |
867 | // TODO: we could widen the smaller range and have this work; but for now we |
868 | // bail out to keep things simple. |
869 | if (R1Value.getType() != R2.getType()) |
870 | return std::nullopt; |
871 | |
872 | const SCEV *NewBegin = SE.getUMaxExpr(LHS: R1Value.getBegin(), RHS: R2.getBegin()); |
873 | const SCEV *NewEnd = SE.getUMinExpr(LHS: R1Value.getEnd(), RHS: R2.getEnd()); |
874 | |
875 | // If the resulting range is empty, just return std::nullopt. |
876 | auto Ret = InductiveRangeCheck::Range(NewBegin, NewEnd); |
877 | if (Ret.isEmpty(SE, /* IsSigned */ false)) |
878 | return std::nullopt; |
879 | return Ret; |
880 | } |
881 | |
882 | PreservedAnalyses IRCEPass::run(Function &F, FunctionAnalysisManager &AM) { |
883 | auto &DT = AM.getResult<DominatorTreeAnalysis>(IR&: F); |
884 | LoopInfo &LI = AM.getResult<LoopAnalysis>(IR&: F); |
885 | // There are no loops in the function. Return before computing other expensive |
886 | // analyses. |
887 | if (LI.empty()) |
888 | return PreservedAnalyses::all(); |
889 | auto &SE = AM.getResult<ScalarEvolutionAnalysis>(IR&: F); |
890 | auto &BPI = AM.getResult<BranchProbabilityAnalysis>(IR&: F); |
891 | |
892 | // Get BFI analysis result on demand. Please note that modification of |
893 | // CFG invalidates this analysis and we should handle it. |
894 | auto getBFI = [&F, &AM ]()->BlockFrequencyInfo & { |
895 | return AM.getResult<BlockFrequencyAnalysis>(IR&: F); |
896 | }; |
897 | InductiveRangeCheckElimination IRCE(SE, &BPI, DT, LI, { getBFI }); |
898 | |
899 | bool Changed = false; |
900 | { |
901 | bool CFGChanged = false; |
902 | for (const auto &L : LI) { |
903 | CFGChanged |= simplifyLoop(L, DT: &DT, LI: &LI, SE: &SE, AC: nullptr, MSSAU: nullptr, |
904 | /*PreserveLCSSA=*/false); |
905 | Changed |= formLCSSARecursively(L&: *L, DT, LI: &LI, SE: &SE); |
906 | } |
907 | Changed |= CFGChanged; |
908 | |
909 | if (CFGChanged && !SkipProfitabilityChecks) { |
910 | PreservedAnalyses PA = PreservedAnalyses::all(); |
911 | PA.abandon<BlockFrequencyAnalysis>(); |
912 | AM.invalidate(IR&: F, PA); |
913 | } |
914 | } |
915 | |
916 | SmallPriorityWorklist<Loop *, 4> Worklist; |
917 | appendLoopsToWorklist(LI, Worklist); |
918 | auto LPMAddNewLoop = [&Worklist](Loop *NL, bool IsSubloop) { |
919 | if (!IsSubloop) |
920 | appendLoopsToWorklist(*NL, Worklist); |
921 | }; |
922 | |
923 | while (!Worklist.empty()) { |
924 | Loop *L = Worklist.pop_back_val(); |
925 | if (IRCE.run(L, LPMAddNewLoop)) { |
926 | Changed = true; |
927 | if (!SkipProfitabilityChecks) { |
928 | PreservedAnalyses PA = PreservedAnalyses::all(); |
929 | PA.abandon<BlockFrequencyAnalysis>(); |
930 | AM.invalidate(IR&: F, PA); |
931 | } |
932 | } |
933 | } |
934 | |
935 | if (!Changed) |
936 | return PreservedAnalyses::all(); |
937 | return getLoopPassPreservedAnalyses(); |
938 | } |
939 | |
940 | bool |
941 | InductiveRangeCheckElimination::isProfitableToTransform(const Loop &L, |
942 | LoopStructure &LS) { |
943 | if (SkipProfitabilityChecks) |
944 | return true; |
945 | if (GetBFI) { |
946 | BlockFrequencyInfo &BFI = (*GetBFI)(); |
947 | uint64_t hFreq = BFI.getBlockFreq(BB: LS.Header).getFrequency(); |
948 | uint64_t phFreq = BFI.getBlockFreq(BB: L.getLoopPreheader()).getFrequency(); |
949 | if (phFreq != 0 && hFreq != 0 && (hFreq / phFreq < MinRuntimeIterations)) { |
950 | LLVM_DEBUG(dbgs() << "irce: could not prove profitability: " |
951 | << "the estimated number of iterations basing on " |
952 | "frequency info is " << (hFreq / phFreq) << "\n" ;); |
953 | return false; |
954 | } |
955 | return true; |
956 | } |
957 | |
958 | if (!BPI) |
959 | return true; |
960 | BranchProbability ExitProbability = |
961 | BPI->getEdgeProbability(Src: LS.Latch, IndexInSuccessors: LS.LatchBrExitIdx); |
962 | if (ExitProbability > BranchProbability(1, MinRuntimeIterations)) { |
963 | LLVM_DEBUG(dbgs() << "irce: could not prove profitability: " |
964 | << "the exit probability is too big " << ExitProbability |
965 | << "\n" ;); |
966 | return false; |
967 | } |
968 | return true; |
969 | } |
970 | |
971 | bool InductiveRangeCheckElimination::run( |
972 | Loop *L, function_ref<void(Loop *, bool)> LPMAddNewLoop) { |
973 | if (L->getBlocks().size() >= LoopSizeCutoff) { |
974 | LLVM_DEBUG(dbgs() << "irce: giving up constraining loop, too large\n" ); |
975 | return false; |
976 | } |
977 | |
978 | BasicBlock * = L->getLoopPreheader(); |
979 | if (!Preheader) { |
980 | LLVM_DEBUG(dbgs() << "irce: loop has no preheader, leaving\n" ); |
981 | return false; |
982 | } |
983 | |
984 | LLVMContext &Context = Preheader->getContext(); |
985 | SmallVector<InductiveRangeCheck, 16> RangeChecks; |
986 | bool Changed = false; |
987 | |
988 | for (auto *BBI : L->getBlocks()) |
989 | if (BranchInst *TBI = dyn_cast<BranchInst>(Val: BBI->getTerminator())) |
990 | InductiveRangeCheck::extractRangeChecksFromBranch(BI: TBI, L, SE, BPI, |
991 | Checks&: RangeChecks, Changed); |
992 | |
993 | if (RangeChecks.empty()) |
994 | return Changed; |
995 | |
996 | auto PrintRecognizedRangeChecks = [&](raw_ostream &OS) { |
997 | OS << "irce: looking at loop " ; L->print(OS); |
998 | OS << "irce: loop has " << RangeChecks.size() |
999 | << " inductive range checks: \n" ; |
1000 | for (InductiveRangeCheck &IRC : RangeChecks) |
1001 | IRC.print(OS); |
1002 | }; |
1003 | |
1004 | LLVM_DEBUG(PrintRecognizedRangeChecks(dbgs())); |
1005 | |
1006 | if (PrintRangeChecks) |
1007 | PrintRecognizedRangeChecks(errs()); |
1008 | |
1009 | const char *FailureReason = nullptr; |
1010 | std::optional<LoopStructure> MaybeLoopStructure = |
1011 | LoopStructure::parseLoopStructure(SE, *L, AllowUnsignedLatchCondition, |
1012 | FailureReason); |
1013 | if (!MaybeLoopStructure) { |
1014 | LLVM_DEBUG(dbgs() << "irce: could not parse loop structure: " |
1015 | << FailureReason << "\n" ;); |
1016 | return Changed; |
1017 | } |
1018 | LoopStructure LS = *MaybeLoopStructure; |
1019 | if (!isProfitableToTransform(L: *L, LS)) |
1020 | return Changed; |
1021 | const SCEVAddRecExpr *IndVar = |
1022 | cast<SCEVAddRecExpr>(Val: SE.getMinusSCEV(LHS: SE.getSCEV(V: LS.IndVarBase), RHS: SE.getSCEV(V: LS.IndVarStep))); |
1023 | |
1024 | std::optional<InductiveRangeCheck::Range> SafeIterRange; |
1025 | |
1026 | SmallVector<InductiveRangeCheck, 4> RangeChecksToEliminate; |
1027 | // Basing on the type of latch predicate, we interpret the IV iteration range |
1028 | // as signed or unsigned range. We use different min/max functions (signed or |
1029 | // unsigned) when intersecting this range with safe iteration ranges implied |
1030 | // by range checks. |
1031 | auto IntersectRange = |
1032 | LS.IsSignedPredicate ? IntersectSignedRange : IntersectUnsignedRange; |
1033 | |
1034 | for (InductiveRangeCheck &IRC : RangeChecks) { |
1035 | auto Result = IRC.computeSafeIterationSpace(SE, IndVar, |
1036 | IsLatchSigned: LS.IsSignedPredicate); |
1037 | if (Result) { |
1038 | auto MaybeSafeIterRange = IntersectRange(SE, SafeIterRange, *Result); |
1039 | if (MaybeSafeIterRange) { |
1040 | assert(!MaybeSafeIterRange->isEmpty(SE, LS.IsSignedPredicate) && |
1041 | "We should never return empty ranges!" ); |
1042 | RangeChecksToEliminate.push_back(Elt: IRC); |
1043 | SafeIterRange = *MaybeSafeIterRange; |
1044 | } |
1045 | } |
1046 | } |
1047 | |
1048 | if (!SafeIterRange) |
1049 | return Changed; |
1050 | |
1051 | std::optional<LoopConstrainer::SubRanges> MaybeSR = |
1052 | calculateSubRanges(SE, L: *L, Range&: *SafeIterRange, MainLoopStructure: LS); |
1053 | if (!MaybeSR) { |
1054 | LLVM_DEBUG(dbgs() << "irce: could not compute subranges\n" ); |
1055 | return false; |
1056 | } |
1057 | |
1058 | LoopConstrainer LC(*L, LI, LPMAddNewLoop, LS, SE, DT, |
1059 | SafeIterRange->getBegin()->getType(), *MaybeSR); |
1060 | |
1061 | if (LC.run()) { |
1062 | Changed = true; |
1063 | |
1064 | auto PrintConstrainedLoopInfo = [L]() { |
1065 | dbgs() << "irce: in function " ; |
1066 | dbgs() << L->getHeader()->getParent()->getName() << ": " ; |
1067 | dbgs() << "constrained " ; |
1068 | L->print(OS&: dbgs()); |
1069 | }; |
1070 | |
1071 | LLVM_DEBUG(PrintConstrainedLoopInfo()); |
1072 | |
1073 | if (PrintChangedLoops) |
1074 | PrintConstrainedLoopInfo(); |
1075 | |
1076 | // Optimize away the now-redundant range checks. |
1077 | |
1078 | for (InductiveRangeCheck &IRC : RangeChecksToEliminate) { |
1079 | ConstantInt *FoldedRangeCheck = IRC.getPassingDirection() |
1080 | ? ConstantInt::getTrue(Context) |
1081 | : ConstantInt::getFalse(Context); |
1082 | IRC.getCheckUse()->set(FoldedRangeCheck); |
1083 | } |
1084 | } |
1085 | |
1086 | return Changed; |
1087 | } |
1088 | |