Bug Summary

File:lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp
Warning:line 862, column 8
Value stored to 'IsSignedPredicate' during its initialization is never read

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name InductiveRangeCheckElimination.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mthread-model posix -fmath-errno -masm-verbose -mconstructor-aliases -munwind-tables -fuse-init-array -target-cpu x86-64 -dwarf-column-info -debugger-tuning=gdb -momit-leaf-frame-pointer -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-9/lib/clang/9.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-9~svn362543/build-llvm/lib/Transforms/Scalar -I /build/llvm-toolchain-snapshot-9~svn362543/lib/Transforms/Scalar -I /build/llvm-toolchain-snapshot-9~svn362543/build-llvm/include -I /build/llvm-toolchain-snapshot-9~svn362543/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0/backward -internal-isystem /usr/include/clang/9.0.0/include/ -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-9/lib/clang/9.0.0/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-comment -std=c++11 -fdeprecated-macro -fdebug-compilation-dir /build/llvm-toolchain-snapshot-9~svn362543/build-llvm/lib/Transforms/Scalar -fdebug-prefix-map=/build/llvm-toolchain-snapshot-9~svn362543=. -ferror-limit 19 -fmessage-length 0 -fvisibility-inlines-hidden -stack-protector 2 -fobjc-runtime=gcc -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -o /tmp/scan-build-2019-06-05-060531-1271-1 -x c++ /build/llvm-toolchain-snapshot-9~svn362543/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp -faddrsig
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/None.h"
49#include "llvm/ADT/Optional.h"
50#include "llvm/ADT/SmallPtrSet.h"
51#include "llvm/ADT/SmallVector.h"
52#include "llvm/ADT/StringRef.h"
53#include "llvm/ADT/Twine.h"
54#include "llvm/Analysis/BranchProbabilityInfo.h"
55#include "llvm/Analysis/LoopAnalysisManager.h"
56#include "llvm/Analysis/LoopInfo.h"
57#include "llvm/Analysis/LoopPass.h"
58#include "llvm/Analysis/ScalarEvolution.h"
59#include "llvm/Analysis/ScalarEvolutionExpander.h"
60#include "llvm/Analysis/ScalarEvolutionExpressions.h"
61#include "llvm/IR/BasicBlock.h"
62#include "llvm/IR/CFG.h"
63#include "llvm/IR/Constants.h"
64#include "llvm/IR/DerivedTypes.h"
65#include "llvm/IR/Dominators.h"
66#include "llvm/IR/Function.h"
67#include "llvm/IR/IRBuilder.h"
68#include "llvm/IR/InstrTypes.h"
69#include "llvm/IR/Instructions.h"
70#include "llvm/IR/Metadata.h"
71#include "llvm/IR/Module.h"
72#include "llvm/IR/PatternMatch.h"
73#include "llvm/IR/Type.h"
74#include "llvm/IR/Use.h"
75#include "llvm/IR/User.h"
76#include "llvm/IR/Value.h"
77#include "llvm/Pass.h"
78#include "llvm/Support/BranchProbability.h"
79#include "llvm/Support/Casting.h"
80#include "llvm/Support/CommandLine.h"
81#include "llvm/Support/Compiler.h"
82#include "llvm/Support/Debug.h"
83#include "llvm/Support/ErrorHandling.h"
84#include "llvm/Support/raw_ostream.h"
85#include "llvm/Transforms/Scalar.h"
86#include "llvm/Transforms/Utils/Cloning.h"
87#include "llvm/Transforms/Utils/LoopSimplify.h"
88#include "llvm/Transforms/Utils/LoopUtils.h"
89#include "llvm/Transforms/Utils/ValueMapper.h"
90#include <algorithm>
91#include <cassert>
92#include <iterator>
93#include <limits>
94#include <utility>
95#include <vector>
96
97using namespace llvm;
98using namespace llvm::PatternMatch;
99
100static cl::opt<unsigned> LoopSizeCutoff("irce-loop-size-cutoff", cl::Hidden,
101 cl::init(64));
102
103static cl::opt<bool> PrintChangedLoops("irce-print-changed-loops", cl::Hidden,
104 cl::init(false));
105
106static cl::opt<bool> PrintRangeChecks("irce-print-range-checks", cl::Hidden,
107 cl::init(false));
108
109static cl::opt<int> MaxExitProbReciprocal("irce-max-exit-prob-reciprocal",
110 cl::Hidden, cl::init(10));
111
112static cl::opt<bool> SkipProfitabilityChecks("irce-skip-profitability-checks",
113 cl::Hidden, cl::init(false));
114
115static cl::opt<bool> AllowUnsignedLatchCondition("irce-allow-unsigned-latch",
116 cl::Hidden, cl::init(true));
117
118static cl::opt<bool> AllowNarrowLatchCondition(
119 "irce-allow-narrow-latch", cl::Hidden, cl::init(true),
120 cl::desc("If set to true, IRCE may eliminate wide range checks in loops "
121 "with narrow latch condition."));
122
123static const char *ClonedLoopTag = "irce.loop.clone";
124
125#define DEBUG_TYPE"irce" "irce"
126
127namespace {
128
129/// An inductive range check is conditional branch in a loop with
130///
131/// 1. a very cold successor (i.e. the branch jumps to that successor very
132/// rarely)
133///
134/// and
135///
136/// 2. a condition that is provably true for some contiguous range of values
137/// taken by the containing loop's induction variable.
138///
139class InductiveRangeCheck {
140
141 const SCEV *Begin = nullptr;
142 const SCEV *Step = nullptr;
143 const SCEV *End = nullptr;
144 Use *CheckUse = nullptr;
145 bool IsSigned = true;
146
147 static bool parseRangeCheckICmp(Loop *L, ICmpInst *ICI, ScalarEvolution &SE,
148 Value *&Index, Value *&Length,
149 bool &IsSigned);
150
151 static void
152 extractRangeChecksFromCond(Loop *L, ScalarEvolution &SE, Use &ConditionUse,
153 SmallVectorImpl<InductiveRangeCheck> &Checks,
154 SmallPtrSetImpl<Value *> &Visited);
155
156public:
157 const SCEV *getBegin() const { return Begin; }
158 const SCEV *getStep() const { return Step; }
159 const SCEV *getEnd() const { return End; }
160 bool isSigned() const { return IsSigned; }
161
162 void print(raw_ostream &OS) const {
163 OS << "InductiveRangeCheck:\n";
164 OS << " Begin: ";
165 Begin->print(OS);
166 OS << " Step: ";
167 Step->print(OS);
168 OS << " End: ";
169 End->print(OS);
170 OS << "\n CheckUse: ";
171 getCheckUse()->getUser()->print(OS);
172 OS << " Operand: " << getCheckUse()->getOperandNo() << "\n";
173 }
174
175 LLVM_DUMP_METHOD__attribute__((noinline)) __attribute__((__used__))
176 void dump() {
177 print(dbgs());
178 }
179
180 Use *getCheckUse() const { return CheckUse; }
181
182 /// Represents an signed integer range [Range.getBegin(), Range.getEnd()). If
183 /// R.getEnd() le R.getBegin(), then R denotes the empty range.
184
185 class Range {
186 const SCEV *Begin;
187 const SCEV *End;
188
189 public:
190 Range(const SCEV *Begin, const SCEV *End) : Begin(Begin), End(End) {
191 assert(Begin->getType() == End->getType() && "ill-typed range!")((Begin->getType() == End->getType() && "ill-typed range!"
) ? static_cast<void> (0) : __assert_fail ("Begin->getType() == End->getType() && \"ill-typed range!\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp"
, 191, __PRETTY_FUNCTION__))
;
192 }
193
194 Type *getType() const { return Begin->getType(); }
195 const SCEV *getBegin() const { return Begin; }
196 const SCEV *getEnd() const { return End; }
197 bool isEmpty(ScalarEvolution &SE, bool IsSigned) const {
198 if (Begin == End)
199 return true;
200 if (IsSigned)
201 return SE.isKnownPredicate(ICmpInst::ICMP_SGE, Begin, End);
202 else
203 return SE.isKnownPredicate(ICmpInst::ICMP_UGE, Begin, End);
204 }
205 };
206
207 /// This is the value the condition of the branch needs to evaluate to for the
208 /// branch to take the hot successor (see (1) above).
209 bool getPassingDirection() { return true; }
210
211 /// Computes a range for the induction variable (IndVar) in which the range
212 /// check is redundant and can be constant-folded away. The induction
213 /// variable is not required to be the canonical {0,+,1} induction variable.
214 Optional<Range> computeSafeIterationSpace(ScalarEvolution &SE,
215 const SCEVAddRecExpr *IndVar,
216 bool IsLatchSigned) const;
217
218 /// Parse out a set of inductive range checks from \p BI and append them to \p
219 /// Checks.
220 ///
221 /// NB! There may be conditions feeding into \p BI that aren't inductive range
222 /// checks, and hence don't end up in \p Checks.
223 static void
224 extractRangeChecksFromBranch(BranchInst *BI, Loop *L, ScalarEvolution &SE,
225 BranchProbabilityInfo *BPI,
226 SmallVectorImpl<InductiveRangeCheck> &Checks);
227};
228
229class InductiveRangeCheckElimination {
230 ScalarEvolution &SE;
231 BranchProbabilityInfo *BPI;
232 DominatorTree &DT;
233 LoopInfo &LI;
234
235public:
236 InductiveRangeCheckElimination(ScalarEvolution &SE,
237 BranchProbabilityInfo *BPI, DominatorTree &DT,
238 LoopInfo &LI)
239 : SE(SE), BPI(BPI), DT(DT), LI(LI) {}
240
241 bool run(Loop *L, function_ref<void(Loop *, bool)> LPMAddNewLoop);
242};
243
244class IRCELegacyPass : public LoopPass {
245public:
246 static char ID;
247
248 IRCELegacyPass() : LoopPass(ID) {
249 initializeIRCELegacyPassPass(*PassRegistry::getPassRegistry());
250 }
251
252 void getAnalysisUsage(AnalysisUsage &AU) const override {
253 AU.addRequired<BranchProbabilityInfoWrapperPass>();
254 getLoopAnalysisUsage(AU);
255 }
256
257 bool runOnLoop(Loop *L, LPPassManager &LPM) override;
258};
259
260} // end anonymous namespace
261
262char IRCELegacyPass::ID = 0;
263
264INITIALIZE_PASS_BEGIN(IRCELegacyPass, "irce",static void *initializeIRCELegacyPassPassOnce(PassRegistry &
Registry) {
265 "Inductive range check elimination", false, false)static void *initializeIRCELegacyPassPassOnce(PassRegistry &
Registry) {
266INITIALIZE_PASS_DEPENDENCY(BranchProbabilityInfoWrapperPass)initializeBranchProbabilityInfoWrapperPassPass(Registry);
267INITIALIZE_PASS_DEPENDENCY(LoopPass)initializeLoopPassPass(Registry);
268INITIALIZE_PASS_END(IRCELegacyPass, "irce", "Inductive range check elimination",PassInfo *PI = new PassInfo( "Inductive range check elimination"
, "irce", &IRCELegacyPass::ID, PassInfo::NormalCtor_t(callDefaultCtor
<IRCELegacyPass>), false, false); Registry.registerPass
(*PI, true); return PI; } static llvm::once_flag InitializeIRCELegacyPassPassFlag
; void llvm::initializeIRCELegacyPassPass(PassRegistry &Registry
) { llvm::call_once(InitializeIRCELegacyPassPassFlag, initializeIRCELegacyPassPassOnce
, std::ref(Registry)); }
269 false, false)PassInfo *PI = new PassInfo( "Inductive range check elimination"
, "irce", &IRCELegacyPass::ID, PassInfo::NormalCtor_t(callDefaultCtor
<IRCELegacyPass>), false, false); Registry.registerPass
(*PI, true); return PI; } static llvm::once_flag InitializeIRCELegacyPassPassFlag
; void llvm::initializeIRCELegacyPassPass(PassRegistry &Registry
) { llvm::call_once(InitializeIRCELegacyPassPassFlag, initializeIRCELegacyPassPassOnce
, std::ref(Registry)); }
270
271/// Parse a single ICmp instruction, `ICI`, into a range check. If `ICI` cannot
272/// be interpreted as a range check, return false and set `Index` and `Length`
273/// to `nullptr`. Otherwise set `Index` to the value being range checked, and
274/// set `Length` to the upper limit `Index` is being range checked.
275bool
276InductiveRangeCheck::parseRangeCheckICmp(Loop *L, ICmpInst *ICI,
277 ScalarEvolution &SE, Value *&Index,
278 Value *&Length, bool &IsSigned) {
279 auto IsLoopInvariant = [&SE, L](Value *V) {
280 return SE.isLoopInvariant(SE.getSCEV(V), L);
281 };
282
283 ICmpInst::Predicate Pred = ICI->getPredicate();
284 Value *LHS = ICI->getOperand(0);
285 Value *RHS = ICI->getOperand(1);
286
287 switch (Pred) {
288 default:
289 return false;
290
291 case ICmpInst::ICMP_SLE:
292 std::swap(LHS, RHS);
293 LLVM_FALLTHROUGH[[clang::fallthrough]];
294 case ICmpInst::ICMP_SGE:
295 IsSigned = true;
296 if (match(RHS, m_ConstantInt<0>())) {
297 Index = LHS;
298 return true; // Lower.
299 }
300 return false;
301
302 case ICmpInst::ICMP_SLT:
303 std::swap(LHS, RHS);
304 LLVM_FALLTHROUGH[[clang::fallthrough]];
305 case ICmpInst::ICMP_SGT:
306 IsSigned = true;
307 if (match(RHS, m_ConstantInt<-1>())) {
308 Index = LHS;
309 return true; // Lower.
310 }
311
312 if (IsLoopInvariant(LHS)) {
313 Index = RHS;
314 Length = LHS;
315 return true; // Upper.
316 }
317 return false;
318
319 case ICmpInst::ICMP_ULT:
320 std::swap(LHS, RHS);
321 LLVM_FALLTHROUGH[[clang::fallthrough]];
322 case ICmpInst::ICMP_UGT:
323 IsSigned = false;
324 if (IsLoopInvariant(LHS)) {
325 Index = RHS;
326 Length = LHS;
327 return true; // Both lower and upper.
328 }
329 return false;
330 }
331
332 llvm_unreachable("default clause returns!")::llvm::llvm_unreachable_internal("default clause returns!", "/build/llvm-toolchain-snapshot-9~svn362543/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp"
, 332)
;
333}
334
335void InductiveRangeCheck::extractRangeChecksFromCond(
336 Loop *L, ScalarEvolution &SE, Use &ConditionUse,
337 SmallVectorImpl<InductiveRangeCheck> &Checks,
338 SmallPtrSetImpl<Value *> &Visited) {
339 Value *Condition = ConditionUse.get();
340 if (!Visited.insert(Condition).second)
341 return;
342
343 // TODO: Do the same for OR, XOR, NOT etc?
344 if (match(Condition, m_And(m_Value(), m_Value()))) {
345 extractRangeChecksFromCond(L, SE, cast<User>(Condition)->getOperandUse(0),
346 Checks, Visited);
347 extractRangeChecksFromCond(L, SE, cast<User>(Condition)->getOperandUse(1),
348 Checks, Visited);
349 return;
350 }
351
352 ICmpInst *ICI = dyn_cast<ICmpInst>(Condition);
353 if (!ICI)
354 return;
355
356 Value *Length = nullptr, *Index;
357 bool IsSigned;
358 if (!parseRangeCheckICmp(L, ICI, SE, Index, Length, IsSigned))
359 return;
360
361 const auto *IndexAddRec = dyn_cast<SCEVAddRecExpr>(SE.getSCEV(Index));
362 bool IsAffineIndex =
363 IndexAddRec && (IndexAddRec->getLoop() == L) && IndexAddRec->isAffine();
364
365 if (!IsAffineIndex)
366 return;
367
368 const SCEV *End = nullptr;
369 // We strengthen "0 <= I" to "0 <= I < INT_SMAX" and "I < L" to "0 <= I < L".
370 // We can potentially do much better here.
371 if (Length)
372 End = SE.getSCEV(Length);
373 else {
374 // So far we can only reach this point for Signed range check. This may
375 // change in future. In this case we will need to pick Unsigned max for the
376 // unsigned range check.
377 unsigned BitWidth = cast<IntegerType>(IndexAddRec->getType())->getBitWidth();
378 const SCEV *SIntMax = SE.getConstant(APInt::getSignedMaxValue(BitWidth));
379 End = SIntMax;
380 }
381
382 InductiveRangeCheck IRC;
383 IRC.End = End;
384 IRC.Begin = IndexAddRec->getStart();
385 IRC.Step = IndexAddRec->getStepRecurrence(SE);
386 IRC.CheckUse = &ConditionUse;
387 IRC.IsSigned = IsSigned;
388 Checks.push_back(IRC);
389}
390
391void InductiveRangeCheck::extractRangeChecksFromBranch(
392 BranchInst *BI, Loop *L, ScalarEvolution &SE, BranchProbabilityInfo *BPI,
393 SmallVectorImpl<InductiveRangeCheck> &Checks) {
394 if (BI->isUnconditional() || BI->getParent() == L->getLoopLatch())
395 return;
396
397 BranchProbability LikelyTaken(15, 16);
398
399 if (!SkipProfitabilityChecks && BPI &&
400 BPI->getEdgeProbability(BI->getParent(), (unsigned)0) < LikelyTaken)
401 return;
402
403 SmallPtrSet<Value *, 8> Visited;
404 InductiveRangeCheck::extractRangeChecksFromCond(L, SE, BI->getOperandUse(0),
405 Checks, Visited);
406}
407
408// Add metadata to the loop L to disable loop optimizations. Callers need to
409// confirm that optimizing loop L is not beneficial.
410static void DisableAllLoopOptsOnLoop(Loop &L) {
411 // We do not care about any existing loopID related metadata for L, since we
412 // are setting all loop metadata to false.
413 LLVMContext &Context = L.getHeader()->getContext();
414 // Reserve first location for self reference to the LoopID metadata node.
415 MDNode *Dummy = MDNode::get(Context, {});
416 MDNode *DisableUnroll = MDNode::get(
417 Context, {MDString::get(Context, "llvm.loop.unroll.disable")});
418 Metadata *FalseVal =
419 ConstantAsMetadata::get(ConstantInt::get(Type::getInt1Ty(Context), 0));
420 MDNode *DisableVectorize = MDNode::get(
421 Context,
422 {MDString::get(Context, "llvm.loop.vectorize.enable"), FalseVal});
423 MDNode *DisableLICMVersioning = MDNode::get(
424 Context, {MDString::get(Context, "llvm.loop.licm_versioning.disable")});
425 MDNode *DisableDistribution= MDNode::get(
426 Context,
427 {MDString::get(Context, "llvm.loop.distribute.enable"), FalseVal});
428 MDNode *NewLoopID =
429 MDNode::get(Context, {Dummy, DisableUnroll, DisableVectorize,
430 DisableLICMVersioning, DisableDistribution});
431 // Set operand 0 to refer to the loop id itself.
432 NewLoopID->replaceOperandWith(0, NewLoopID);
433 L.setLoopID(NewLoopID);
434}
435
436namespace {
437
438// Keeps track of the structure of a loop. This is similar to llvm::Loop,
439// except that it is more lightweight and can track the state of a loop through
440// changing and potentially invalid IR. This structure also formalizes the
441// kinds of loops we can deal with -- ones that have a single latch that is also
442// an exiting block *and* have a canonical induction variable.
443struct LoopStructure {
444 const char *Tag = "";
445
446 BasicBlock *Header = nullptr;
447 BasicBlock *Latch = nullptr;
448
449 // `Latch's terminator instruction is `LatchBr', and it's `LatchBrExitIdx'th
450 // successor is `LatchExit', the exit block of the loop.
451 BranchInst *LatchBr = nullptr;
452 BasicBlock *LatchExit = nullptr;
453 unsigned LatchBrExitIdx = std::numeric_limits<unsigned>::max();
454
455 // The loop represented by this instance of LoopStructure is semantically
456 // equivalent to:
457 //
458 // intN_ty inc = IndVarIncreasing ? 1 : -1;
459 // pred_ty predicate = IndVarIncreasing ? ICMP_SLT : ICMP_SGT;
460 //
461 // for (intN_ty iv = IndVarStart; predicate(iv, LoopExitAt); iv = IndVarBase)
462 // ... body ...
463
464 Value *IndVarBase = nullptr;
465 Value *IndVarStart = nullptr;
466 Value *IndVarStep = nullptr;
467 Value *LoopExitAt = nullptr;
468 bool IndVarIncreasing = false;
469 bool IsSignedPredicate = true;
470
471 LoopStructure() = default;
472
473 template <typename M> LoopStructure map(M Map) const {
474 LoopStructure Result;
475 Result.Tag = Tag;
476 Result.Header = cast<BasicBlock>(Map(Header));
477 Result.Latch = cast<BasicBlock>(Map(Latch));
478 Result.LatchBr = cast<BranchInst>(Map(LatchBr));
479 Result.LatchExit = cast<BasicBlock>(Map(LatchExit));
480 Result.LatchBrExitIdx = LatchBrExitIdx;
481 Result.IndVarBase = Map(IndVarBase);
482 Result.IndVarStart = Map(IndVarStart);
483 Result.IndVarStep = Map(IndVarStep);
484 Result.LoopExitAt = Map(LoopExitAt);
485 Result.IndVarIncreasing = IndVarIncreasing;
486 Result.IsSignedPredicate = IsSignedPredicate;
487 return Result;
488 }
489
490 static Optional<LoopStructure> parseLoopStructure(ScalarEvolution &,
491 BranchProbabilityInfo *BPI,
492 Loop &, const char *&);
493};
494
495/// This class is used to constrain loops to run within a given iteration space.
496/// The algorithm this class implements is given a Loop and a range [Begin,
497/// End). The algorithm then tries to break out a "main loop" out of the loop
498/// it is given in a way that the "main loop" runs with the induction variable
499/// in a subset of [Begin, End). The algorithm emits appropriate pre and post
500/// loops to run any remaining iterations. The pre loop runs any iterations in
501/// which the induction variable is < Begin, and the post loop runs any
502/// iterations in which the induction variable is >= End.
503class LoopConstrainer {
504 // The representation of a clone of the original loop we started out with.
505 struct ClonedLoop {
506 // The cloned blocks
507 std::vector<BasicBlock *> Blocks;
508
509 // `Map` maps values in the clonee into values in the cloned version
510 ValueToValueMapTy Map;
511
512 // An instance of `LoopStructure` for the cloned loop
513 LoopStructure Structure;
514 };
515
516 // Result of rewriting the range of a loop. See changeIterationSpaceEnd for
517 // more details on what these fields mean.
518 struct RewrittenRangeInfo {
519 BasicBlock *PseudoExit = nullptr;
520 BasicBlock *ExitSelector = nullptr;
521 std::vector<PHINode *> PHIValuesAtPseudoExit;
522 PHINode *IndVarEnd = nullptr;
523
524 RewrittenRangeInfo() = default;
525 };
526
527 // Calculated subranges we restrict the iteration space of the main loop to.
528 // See the implementation of `calculateSubRanges' for more details on how
529 // these fields are computed. `LowLimit` is None if there is no restriction
530 // on low end of the restricted iteration space of the main loop. `HighLimit`
531 // is None if there is no restriction on high end of the restricted iteration
532 // space of the main loop.
533
534 struct SubRanges {
535 Optional<const SCEV *> LowLimit;
536 Optional<const SCEV *> HighLimit;
537 };
538
539 // Compute a safe set of limits for the main loop to run in -- effectively the
540 // intersection of `Range' and the iteration space of the original loop.
541 // Return None if unable to compute the set of subranges.
542 Optional<SubRanges> calculateSubRanges(bool IsSignedPredicate) const;
543
544 // Clone `OriginalLoop' and return the result in CLResult. The IR after
545 // running `cloneLoop' is well formed except for the PHI nodes in CLResult --
546 // the PHI nodes say that there is an incoming edge from `OriginalPreheader`
547 // but there is no such edge.
548 void cloneLoop(ClonedLoop &CLResult, const char *Tag) const;
549
550 // Create the appropriate loop structure needed to describe a cloned copy of
551 // `Original`. The clone is described by `VM`.
552 Loop *createClonedLoopStructure(Loop *Original, Loop *Parent,
553 ValueToValueMapTy &VM, bool IsSubloop);
554
555 // Rewrite the iteration space of the loop denoted by (LS, Preheader). The
556 // iteration space of the rewritten loop ends at ExitLoopAt. The start of the
557 // iteration space is not changed. `ExitLoopAt' is assumed to be slt
558 // `OriginalHeaderCount'.
559 //
560 // If there are iterations left to execute, control is made to jump to
561 // `ContinuationBlock', otherwise they take the normal loop exit. The
562 // returned `RewrittenRangeInfo' object is populated as follows:
563 //
564 // .PseudoExit is a basic block that unconditionally branches to
565 // `ContinuationBlock'.
566 //
567 // .ExitSelector is a basic block that decides, on exit from the loop,
568 // whether to branch to the "true" exit or to `PseudoExit'.
569 //
570 // .PHIValuesAtPseudoExit are PHINodes in `PseudoExit' that compute the value
571 // for each PHINode in the loop header on taking the pseudo exit.
572 //
573 // After changeIterationSpaceEnd, `Preheader' is no longer a legitimate
574 // preheader because it is made to branch to the loop header only
575 // conditionally.
576 RewrittenRangeInfo
577 changeIterationSpaceEnd(const LoopStructure &LS, BasicBlock *Preheader,
578 Value *ExitLoopAt,
579 BasicBlock *ContinuationBlock) const;
580
581 // The loop denoted by `LS' has `OldPreheader' as its preheader. This
582 // function creates a new preheader for `LS' and returns it.
583 BasicBlock *createPreheader(const LoopStructure &LS, BasicBlock *OldPreheader,
584 const char *Tag) const;
585
586 // `ContinuationBlockAndPreheader' was the continuation block for some call to
587 // `changeIterationSpaceEnd' and is the preheader to the loop denoted by `LS'.
588 // This function rewrites the PHI nodes in `LS.Header' to start with the
589 // correct value.
590 void rewriteIncomingValuesForPHIs(
591 LoopStructure &LS, BasicBlock *ContinuationBlockAndPreheader,
592 const LoopConstrainer::RewrittenRangeInfo &RRI) const;
593
594 // Even though we do not preserve any passes at this time, we at least need to
595 // keep the parent loop structure consistent. The `LPPassManager' seems to
596 // verify this after running a loop pass. This function adds the list of
597 // blocks denoted by BBs to this loops parent loop if required.
598 void addToParentLoopIfNeeded(ArrayRef<BasicBlock *> BBs);
599
600 // Some global state.
601 Function &F;
602 LLVMContext &Ctx;
603 ScalarEvolution &SE;
604 DominatorTree &DT;
605 LoopInfo &LI;
606 function_ref<void(Loop *, bool)> LPMAddNewLoop;
607
608 // Information about the original loop we started out with.
609 Loop &OriginalLoop;
610
611 const SCEV *LatchTakenCount = nullptr;
612 BasicBlock *OriginalPreheader = nullptr;
613
614 // The preheader of the main loop. This may or may not be different from
615 // `OriginalPreheader'.
616 BasicBlock *MainLoopPreheader = nullptr;
617
618 // The range we need to run the main loop in.
619 InductiveRangeCheck::Range Range;
620
621 // The structure of the main loop (see comment at the beginning of this class
622 // for a definition)
623 LoopStructure MainLoopStructure;
624
625public:
626 LoopConstrainer(Loop &L, LoopInfo &LI,
627 function_ref<void(Loop *, bool)> LPMAddNewLoop,
628 const LoopStructure &LS, ScalarEvolution &SE,
629 DominatorTree &DT, InductiveRangeCheck::Range R)
630 : F(*L.getHeader()->getParent()), Ctx(L.getHeader()->getContext()),
631 SE(SE), DT(DT), LI(LI), LPMAddNewLoop(LPMAddNewLoop), OriginalLoop(L),
632 Range(R), MainLoopStructure(LS) {}
633
634 // Entry point for the algorithm. Returns true on success.
635 bool run();
636};
637
638} // end anonymous namespace
639
640/// Given a loop with an deccreasing induction variable, is it possible to
641/// safely calculate the bounds of a new loop using the given Predicate.
642static bool isSafeDecreasingBound(const SCEV *Start,
643 const SCEV *BoundSCEV, const SCEV *Step,
644 ICmpInst::Predicate Pred,
645 unsigned LatchBrExitIdx,
646 Loop *L, ScalarEvolution &SE) {
647 if (Pred != ICmpInst::ICMP_SLT && Pred != ICmpInst::ICMP_SGT &&
648 Pred != ICmpInst::ICMP_ULT && Pred != ICmpInst::ICMP_UGT)
649 return false;
650
651 if (!SE.isAvailableAtLoopEntry(BoundSCEV, L))
652 return false;
653
654 assert(SE.isKnownNegative(Step) && "expecting negative step")((SE.isKnownNegative(Step) && "expecting negative step"
) ? static_cast<void> (0) : __assert_fail ("SE.isKnownNegative(Step) && \"expecting negative step\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp"
, 654, __PRETTY_FUNCTION__))
;
655
656 LLVM_DEBUG(dbgs() << "irce: isSafeDecreasingBound with:\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("irce")) { dbgs() << "irce: isSafeDecreasingBound with:\n"
; } } while (false)
;
657 LLVM_DEBUG(dbgs() << "irce: Start: " << *Start << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("irce")) { dbgs() << "irce: Start: " << *Start <<
"\n"; } } while (false)
;
658 LLVM_DEBUG(dbgs() << "irce: Step: " << *Step << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("irce")) { dbgs() << "irce: Step: " << *Step <<
"\n"; } } while (false)
;
659 LLVM_DEBUG(dbgs() << "irce: BoundSCEV: " << *BoundSCEV << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("irce")) { dbgs() << "irce: BoundSCEV: " << *BoundSCEV
<< "\n"; } } while (false)
;
660 LLVM_DEBUG(dbgs() << "irce: Pred: " << ICmpInst::getPredicateName(Pred)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("irce")) { dbgs() << "irce: Pred: " << ICmpInst::
getPredicateName(Pred) << "\n"; } } while (false)
661 << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("irce")) { dbgs() << "irce: Pred: " << ICmpInst::
getPredicateName(Pred) << "\n"; } } while (false)
;
662 LLVM_DEBUG(dbgs() << "irce: LatchExitBrIdx: " << LatchBrExitIdx << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("irce")) { dbgs() << "irce: LatchExitBrIdx: " <<
LatchBrExitIdx << "\n"; } } while (false)
;
663
664 bool IsSigned = ICmpInst::isSigned(Pred);
665 // The predicate that we need to check that the induction variable lies
666 // within bounds.
667 ICmpInst::Predicate BoundPred =
668 IsSigned ? CmpInst::ICMP_SGT : CmpInst::ICMP_UGT;
669
670 if (LatchBrExitIdx == 1)
671 return SE.isLoopEntryGuardedByCond(L, BoundPred, Start, BoundSCEV);
672
673 assert(LatchBrExitIdx == 0 &&((LatchBrExitIdx == 0 && "LatchBrExitIdx should be either 0 or 1"
) ? static_cast<void> (0) : __assert_fail ("LatchBrExitIdx == 0 && \"LatchBrExitIdx should be either 0 or 1\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp"
, 674, __PRETTY_FUNCTION__))
674 "LatchBrExitIdx should be either 0 or 1")((LatchBrExitIdx == 0 && "LatchBrExitIdx should be either 0 or 1"
) ? static_cast<void> (0) : __assert_fail ("LatchBrExitIdx == 0 && \"LatchBrExitIdx should be either 0 or 1\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp"
, 674, __PRETTY_FUNCTION__))
;
675
676 const SCEV *StepPlusOne = SE.getAddExpr(Step, SE.getOne(Step->getType()));
677 unsigned BitWidth = cast<IntegerType>(BoundSCEV->getType())->getBitWidth();
678 APInt Min = IsSigned ? APInt::getSignedMinValue(BitWidth) :
679 APInt::getMinValue(BitWidth);
680 const SCEV *Limit = SE.getMinusSCEV(SE.getConstant(Min), StepPlusOne);
681
682 const SCEV *MinusOne =
683 SE.getMinusSCEV(BoundSCEV, SE.getOne(BoundSCEV->getType()));
684
685 return SE.isLoopEntryGuardedByCond(L, BoundPred, Start, MinusOne) &&
686 SE.isLoopEntryGuardedByCond(L, BoundPred, BoundSCEV, Limit);
687
688}
689
690/// Given a loop with an increasing induction variable, is it possible to
691/// safely calculate the bounds of a new loop using the given Predicate.
692static bool isSafeIncreasingBound(const SCEV *Start,
693 const SCEV *BoundSCEV, const SCEV *Step,
694 ICmpInst::Predicate Pred,
695 unsigned LatchBrExitIdx,
696 Loop *L, ScalarEvolution &SE) {
697 if (Pred != ICmpInst::ICMP_SLT && Pred != ICmpInst::ICMP_SGT &&
698 Pred != ICmpInst::ICMP_ULT && Pred != ICmpInst::ICMP_UGT)
699 return false;
700
701 if (!SE.isAvailableAtLoopEntry(BoundSCEV, L))
702 return false;
703
704 LLVM_DEBUG(dbgs() << "irce: isSafeIncreasingBound with:\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("irce")) { dbgs() << "irce: isSafeIncreasingBound with:\n"
; } } while (false)
;
705 LLVM_DEBUG(dbgs() << "irce: Start: " << *Start << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("irce")) { dbgs() << "irce: Start: " << *Start <<
"\n"; } } while (false)
;
706 LLVM_DEBUG(dbgs() << "irce: Step: " << *Step << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("irce")) { dbgs() << "irce: Step: " << *Step <<
"\n"; } } while (false)
;
707 LLVM_DEBUG(dbgs() << "irce: BoundSCEV: " << *BoundSCEV << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("irce")) { dbgs() << "irce: BoundSCEV: " << *BoundSCEV
<< "\n"; } } while (false)
;
708 LLVM_DEBUG(dbgs() << "irce: Pred: " << ICmpInst::getPredicateName(Pred)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("irce")) { dbgs() << "irce: Pred: " << ICmpInst::
getPredicateName(Pred) << "\n"; } } while (false)
709 << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("irce")) { dbgs() << "irce: Pred: " << ICmpInst::
getPredicateName(Pred) << "\n"; } } while (false)
;
710 LLVM_DEBUG(dbgs() << "irce: LatchExitBrIdx: " << LatchBrExitIdx << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("irce")) { dbgs() << "irce: LatchExitBrIdx: " <<
LatchBrExitIdx << "\n"; } } while (false)
;
711
712 bool IsSigned = ICmpInst::isSigned(Pred);
713 // The predicate that we need to check that the induction variable lies
714 // within bounds.
715 ICmpInst::Predicate BoundPred =
716 IsSigned ? CmpInst::ICMP_SLT : CmpInst::ICMP_ULT;
717
718 if (LatchBrExitIdx == 1)
719 return SE.isLoopEntryGuardedByCond(L, BoundPred, Start, BoundSCEV);
720
721 assert(LatchBrExitIdx == 0 && "LatchBrExitIdx should be 0 or 1")((LatchBrExitIdx == 0 && "LatchBrExitIdx should be 0 or 1"
) ? static_cast<void> (0) : __assert_fail ("LatchBrExitIdx == 0 && \"LatchBrExitIdx should be 0 or 1\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp"
, 721, __PRETTY_FUNCTION__))
;
722
723 const SCEV *StepMinusOne =
724 SE.getMinusSCEV(Step, SE.getOne(Step->getType()));
725 unsigned BitWidth = cast<IntegerType>(BoundSCEV->getType())->getBitWidth();
726 APInt Max = IsSigned ? APInt::getSignedMaxValue(BitWidth) :
727 APInt::getMaxValue(BitWidth);
728 const SCEV *Limit = SE.getMinusSCEV(SE.getConstant(Max), StepMinusOne);
729
730 return (SE.isLoopEntryGuardedByCond(L, BoundPred, Start,
731 SE.getAddExpr(BoundSCEV, Step)) &&
732 SE.isLoopEntryGuardedByCond(L, BoundPred, BoundSCEV, Limit));
733}
734
735Optional<LoopStructure>
736LoopStructure::parseLoopStructure(ScalarEvolution &SE,
737 BranchProbabilityInfo *BPI, Loop &L,
738 const char *&FailureReason) {
739 if (!L.isLoopSimplifyForm()) {
740 FailureReason = "loop not in LoopSimplify form";
741 return None;
742 }
743
744 BasicBlock *Latch = L.getLoopLatch();
745 assert(Latch && "Simplified loops only have one latch!")((Latch && "Simplified loops only have one latch!") ?
static_cast<void> (0) : __assert_fail ("Latch && \"Simplified loops only have one latch!\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp"
, 745, __PRETTY_FUNCTION__))
;
746
747 if (Latch->getTerminator()->getMetadata(ClonedLoopTag)) {
748 FailureReason = "loop has already been cloned";
749 return None;
750 }
751
752 if (!L.isLoopExiting(Latch)) {
753 FailureReason = "no loop latch";
754 return None;
755 }
756
757 BasicBlock *Header = L.getHeader();
758 BasicBlock *Preheader = L.getLoopPreheader();
759 if (!Preheader) {
760 FailureReason = "no preheader";
761 return None;
762 }
763
764 BranchInst *LatchBr = dyn_cast<BranchInst>(Latch->getTerminator());
765 if (!LatchBr || LatchBr->isUnconditional()) {
766 FailureReason = "latch terminator not conditional branch";
767 return None;
768 }
769
770 unsigned LatchBrExitIdx = LatchBr->getSuccessor(0) == Header ? 1 : 0;
771
772 BranchProbability ExitProbability =
773 BPI ? BPI->getEdgeProbability(LatchBr->getParent(), LatchBrExitIdx)
774 : BranchProbability::getZero();
775
776 if (!SkipProfitabilityChecks &&
777 ExitProbability > BranchProbability(1, MaxExitProbReciprocal)) {
778 FailureReason = "short running loop, not profitable";
779 return None;
780 }
781
782 ICmpInst *ICI = dyn_cast<ICmpInst>(LatchBr->getCondition());
783 if (!ICI || !isa<IntegerType>(ICI->getOperand(0)->getType())) {
784 FailureReason = "latch terminator branch not conditional on integral icmp";
785 return None;
786 }
787
788 const SCEV *LatchCount = SE.getExitCount(&L, Latch);
789 if (isa<SCEVCouldNotCompute>(LatchCount)) {
790 FailureReason = "could not compute latch count";
791 return None;
792 }
793
794 ICmpInst::Predicate Pred = ICI->getPredicate();
795 Value *LeftValue = ICI->getOperand(0);
796 const SCEV *LeftSCEV = SE.getSCEV(LeftValue);
797 IntegerType *IndVarTy = cast<IntegerType>(LeftValue->getType());
798
799 Value *RightValue = ICI->getOperand(1);
800 const SCEV *RightSCEV = SE.getSCEV(RightValue);
801
802 // We canonicalize `ICI` such that `LeftSCEV` is an add recurrence.
803 if (!isa<SCEVAddRecExpr>(LeftSCEV)) {
804 if (isa<SCEVAddRecExpr>(RightSCEV)) {
805 std::swap(LeftSCEV, RightSCEV);
806 std::swap(LeftValue, RightValue);
807 Pred = ICmpInst::getSwappedPredicate(Pred);
808 } else {
809 FailureReason = "no add recurrences in the icmp";
810 return None;
811 }
812 }
813
814 auto HasNoSignedWrap = [&](const SCEVAddRecExpr *AR) {
815 if (AR->getNoWrapFlags(SCEV::FlagNSW))
816 return true;
817
818 IntegerType *Ty = cast<IntegerType>(AR->getType());
819 IntegerType *WideTy =
820 IntegerType::get(Ty->getContext(), Ty->getBitWidth() * 2);
821
822 const SCEVAddRecExpr *ExtendAfterOp =
823 dyn_cast<SCEVAddRecExpr>(SE.getSignExtendExpr(AR, WideTy));
824 if (ExtendAfterOp) {
825 const SCEV *ExtendedStart = SE.getSignExtendExpr(AR->getStart(), WideTy);
826 const SCEV *ExtendedStep =
827 SE.getSignExtendExpr(AR->getStepRecurrence(SE), WideTy);
828
829 bool NoSignedWrap = ExtendAfterOp->getStart() == ExtendedStart &&
830 ExtendAfterOp->getStepRecurrence(SE) == ExtendedStep;
831
832 if (NoSignedWrap)
833 return true;
834 }
835
836 // We may have proved this when computing the sign extension above.
837 return AR->getNoWrapFlags(SCEV::FlagNSW) != SCEV::FlagAnyWrap;
838 };
839
840 // `ICI` is interpreted as taking the backedge if the *next* value of the
841 // induction variable satisfies some constraint.
842
843 const SCEVAddRecExpr *IndVarBase = cast<SCEVAddRecExpr>(LeftSCEV);
844 if (!IndVarBase->isAffine()) {
845 FailureReason = "LHS in icmp not induction variable";
846 return None;
847 }
848 const SCEV* StepRec = IndVarBase->getStepRecurrence(SE);
849 if (!isa<SCEVConstant>(StepRec)) {
850 FailureReason = "LHS in icmp not induction variable";
851 return None;
852 }
853 ConstantInt *StepCI = cast<SCEVConstant>(StepRec)->getValue();
854
855 if (ICI->isEquality() && !HasNoSignedWrap(IndVarBase)) {
856 FailureReason = "LHS in icmp needs nsw for equality predicates";
857 return None;
858 }
859
860 assert(!StepCI->isZero() && "Zero step?")((!StepCI->isZero() && "Zero step?") ? static_cast
<void> (0) : __assert_fail ("!StepCI->isZero() && \"Zero step?\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp"
, 860, __PRETTY_FUNCTION__))
;
861 bool IsIncreasing = !StepCI->isNegative();
862 bool IsSignedPredicate = ICmpInst::isSigned(Pred);
Value stored to 'IsSignedPredicate' during its initialization is never read
863 const SCEV *StartNext = IndVarBase->getStart();
864 const SCEV *Addend = SE.getNegativeSCEV(IndVarBase->getStepRecurrence(SE));
865 const SCEV *IndVarStart = SE.getAddExpr(StartNext, Addend);
866 const SCEV *Step = SE.getSCEV(StepCI);
867
868 ConstantInt *One = ConstantInt::get(IndVarTy, 1);
869 if (IsIncreasing) {
870 bool DecreasedRightValueByOne = false;
871 if (StepCI->isOne()) {
872 // Try to turn eq/ne predicates to those we can work with.
873 if (Pred == ICmpInst::ICMP_NE && LatchBrExitIdx == 1)
874 // while (++i != len) { while (++i < len) {
875 // ... ---> ...
876 // } }
877 // If both parts are known non-negative, it is profitable to use
878 // unsigned comparison in increasing loop. This allows us to make the
879 // comparison check against "RightSCEV + 1" more optimistic.
880 if (isKnownNonNegativeInLoop(IndVarStart, &L, SE) &&
881 isKnownNonNegativeInLoop(RightSCEV, &L, SE))
882 Pred = ICmpInst::ICMP_ULT;
883 else
884 Pred = ICmpInst::ICMP_SLT;
885 else if (Pred == ICmpInst::ICMP_EQ && LatchBrExitIdx == 0) {
886 // while (true) { while (true) {
887 // if (++i == len) ---> if (++i > len - 1)
888 // break; break;
889 // ... ...
890 // } }
891 if (IndVarBase->getNoWrapFlags(SCEV::FlagNUW) &&
892 cannotBeMinInLoop(RightSCEV, &L, SE, /*Signed*/false)) {
893 Pred = ICmpInst::ICMP_UGT;
894 RightSCEV = SE.getMinusSCEV(RightSCEV,
895 SE.getOne(RightSCEV->getType()));
896 DecreasedRightValueByOne = true;
897 } else if (cannotBeMinInLoop(RightSCEV, &L, SE, /*Signed*/true)) {
898 Pred = ICmpInst::ICMP_SGT;
899 RightSCEV = SE.getMinusSCEV(RightSCEV,
900 SE.getOne(RightSCEV->getType()));
901 DecreasedRightValueByOne = true;
902 }
903 }
904 }
905
906 bool LTPred = (Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_ULT);
907 bool GTPred = (Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_UGT);
908 bool FoundExpectedPred =
909 (LTPred && LatchBrExitIdx == 1) || (GTPred && LatchBrExitIdx == 0);
910
911 if (!FoundExpectedPred) {
912 FailureReason = "expected icmp slt semantically, found something else";
913 return None;
914 }
915
916 IsSignedPredicate = ICmpInst::isSigned(Pred);
917 if (!IsSignedPredicate && !AllowUnsignedLatchCondition) {
918 FailureReason = "unsigned latch conditions are explicitly prohibited";
919 return None;
920 }
921
922 if (!isSafeIncreasingBound(IndVarStart, RightSCEV, Step, Pred,
923 LatchBrExitIdx, &L, SE)) {
924 FailureReason = "Unsafe loop bounds";
925 return None;
926 }
927 if (LatchBrExitIdx == 0) {
928 // We need to increase the right value unless we have already decreased
929 // it virtually when we replaced EQ with SGT.
930 if (!DecreasedRightValueByOne) {
931 IRBuilder<> B(Preheader->getTerminator());
932 RightValue = B.CreateAdd(RightValue, One);
933 }
934 } else {
935 assert(!DecreasedRightValueByOne &&((!DecreasedRightValueByOne && "Right value can be decreased only for LatchBrExitIdx == 0!"
) ? static_cast<void> (0) : __assert_fail ("!DecreasedRightValueByOne && \"Right value can be decreased only for LatchBrExitIdx == 0!\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp"
, 936, __PRETTY_FUNCTION__))
936 "Right value can be decreased only for LatchBrExitIdx == 0!")((!DecreasedRightValueByOne && "Right value can be decreased only for LatchBrExitIdx == 0!"
) ? static_cast<void> (0) : __assert_fail ("!DecreasedRightValueByOne && \"Right value can be decreased only for LatchBrExitIdx == 0!\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp"
, 936, __PRETTY_FUNCTION__))
;
937 }
938 } else {
939 bool IncreasedRightValueByOne = false;
940 if (StepCI->isMinusOne()) {
941 // Try to turn eq/ne predicates to those we can work with.
942 if (Pred == ICmpInst::ICMP_NE && LatchBrExitIdx == 1)
943 // while (--i != len) { while (--i > len) {
944 // ... ---> ...
945 // } }
946 // We intentionally don't turn the predicate into UGT even if we know
947 // that both operands are non-negative, because it will only pessimize
948 // our check against "RightSCEV - 1".
949 Pred = ICmpInst::ICMP_SGT;
950 else if (Pred == ICmpInst::ICMP_EQ && LatchBrExitIdx == 0) {
951 // while (true) { while (true) {
952 // if (--i == len) ---> if (--i < len + 1)
953 // break; break;
954 // ... ...
955 // } }
956 if (IndVarBase->getNoWrapFlags(SCEV::FlagNUW) &&
957 cannotBeMaxInLoop(RightSCEV, &L, SE, /* Signed */ false)) {
958 Pred = ICmpInst::ICMP_ULT;
959 RightSCEV = SE.getAddExpr(RightSCEV, SE.getOne(RightSCEV->getType()));
960 IncreasedRightValueByOne = true;
961 } else if (cannotBeMaxInLoop(RightSCEV, &L, SE, /* Signed */ true)) {
962 Pred = ICmpInst::ICMP_SLT;
963 RightSCEV = SE.getAddExpr(RightSCEV, SE.getOne(RightSCEV->getType()));
964 IncreasedRightValueByOne = true;
965 }
966 }
967 }
968
969 bool LTPred = (Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_ULT);
970 bool GTPred = (Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_UGT);
971
972 bool FoundExpectedPred =
973 (GTPred && LatchBrExitIdx == 1) || (LTPred && LatchBrExitIdx == 0);
974
975 if (!FoundExpectedPred) {
976 FailureReason = "expected icmp sgt semantically, found something else";
977 return None;
978 }
979
980 IsSignedPredicate =
981 Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_SGT;
982
983 if (!IsSignedPredicate && !AllowUnsignedLatchCondition) {
984 FailureReason = "unsigned latch conditions are explicitly prohibited";
985 return None;
986 }
987
988 if (!isSafeDecreasingBound(IndVarStart, RightSCEV, Step, Pred,
989 LatchBrExitIdx, &L, SE)) {
990 FailureReason = "Unsafe bounds";
991 return None;
992 }
993
994 if (LatchBrExitIdx == 0) {
995 // We need to decrease the right value unless we have already increased
996 // it virtually when we replaced EQ with SLT.
997 if (!IncreasedRightValueByOne) {
998 IRBuilder<> B(Preheader->getTerminator());
999 RightValue = B.CreateSub(RightValue, One);
1000 }
1001 } else {
1002 assert(!IncreasedRightValueByOne &&((!IncreasedRightValueByOne && "Right value can be increased only for LatchBrExitIdx == 0!"
) ? static_cast<void> (0) : __assert_fail ("!IncreasedRightValueByOne && \"Right value can be increased only for LatchBrExitIdx == 0!\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp"
, 1003, __PRETTY_FUNCTION__))
1003 "Right value can be increased only for LatchBrExitIdx == 0!")((!IncreasedRightValueByOne && "Right value can be increased only for LatchBrExitIdx == 0!"
) ? static_cast<void> (0) : __assert_fail ("!IncreasedRightValueByOne && \"Right value can be increased only for LatchBrExitIdx == 0!\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp"
, 1003, __PRETTY_FUNCTION__))
;
1004 }
1005 }
1006 BasicBlock *LatchExit = LatchBr->getSuccessor(LatchBrExitIdx);
1007
1008 assert(SE.getLoopDisposition(LatchCount, &L) ==((SE.getLoopDisposition(LatchCount, &L) == ScalarEvolution
::LoopInvariant && "loop variant exit count doesn't make sense!"
) ? static_cast<void> (0) : __assert_fail ("SE.getLoopDisposition(LatchCount, &L) == ScalarEvolution::LoopInvariant && \"loop variant exit count doesn't make sense!\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp"
, 1010, __PRETTY_FUNCTION__))
1009 ScalarEvolution::LoopInvariant &&((SE.getLoopDisposition(LatchCount, &L) == ScalarEvolution
::LoopInvariant && "loop variant exit count doesn't make sense!"
) ? static_cast<void> (0) : __assert_fail ("SE.getLoopDisposition(LatchCount, &L) == ScalarEvolution::LoopInvariant && \"loop variant exit count doesn't make sense!\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp"
, 1010, __PRETTY_FUNCTION__))
1010 "loop variant exit count doesn't make sense!")((SE.getLoopDisposition(LatchCount, &L) == ScalarEvolution
::LoopInvariant && "loop variant exit count doesn't make sense!"
) ? static_cast<void> (0) : __assert_fail ("SE.getLoopDisposition(LatchCount, &L) == ScalarEvolution::LoopInvariant && \"loop variant exit count doesn't make sense!\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp"
, 1010, __PRETTY_FUNCTION__))
;
1011
1012 assert(!L.contains(LatchExit) && "expected an exit block!")((!L.contains(LatchExit) && "expected an exit block!"
) ? static_cast<void> (0) : __assert_fail ("!L.contains(LatchExit) && \"expected an exit block!\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp"
, 1012, __PRETTY_FUNCTION__))
;
1013 const DataLayout &DL = Preheader->getModule()->getDataLayout();
1014 Value *IndVarStartV =
1015 SCEVExpander(SE, DL, "irce")
1016 .expandCodeFor(IndVarStart, IndVarTy, Preheader->getTerminator());
1017 IndVarStartV->setName("indvar.start");
1018
1019 LoopStructure Result;
1020
1021 Result.Tag = "main";
1022 Result.Header = Header;
1023 Result.Latch = Latch;
1024 Result.LatchBr = LatchBr;
1025 Result.LatchExit = LatchExit;
1026 Result.LatchBrExitIdx = LatchBrExitIdx;
1027 Result.IndVarStart = IndVarStartV;
1028 Result.IndVarStep = StepCI;
1029 Result.IndVarBase = LeftValue;
1030 Result.IndVarIncreasing = IsIncreasing;
1031 Result.LoopExitAt = RightValue;
1032 Result.IsSignedPredicate = IsSignedPredicate;
1033
1034 FailureReason = nullptr;
1035
1036 return Result;
1037}
1038
1039/// If the type of \p S matches with \p Ty, return \p S. Otherwise, return
1040/// signed or unsigned extension of \p S to type \p Ty.
1041static const SCEV *NoopOrExtend(const SCEV *S, Type *Ty, ScalarEvolution &SE,
1042 bool Signed) {
1043 return Signed ? SE.getNoopOrSignExtend(S, Ty) : SE.getNoopOrZeroExtend(S, Ty);
1044}
1045
1046Optional<LoopConstrainer::SubRanges>
1047LoopConstrainer::calculateSubRanges(bool IsSignedPredicate) const {
1048 IntegerType *Ty = cast<IntegerType>(LatchTakenCount->getType());
1049
1050 auto *RTy = cast<IntegerType>(Range.getType());
1051
1052 // We only support wide range checks and narrow latches.
1053 if (!AllowNarrowLatchCondition && RTy != Ty)
1054 return None;
1055 if (RTy->getBitWidth() < Ty->getBitWidth())
1056 return None;
1057
1058 LoopConstrainer::SubRanges Result;
1059
1060 // I think we can be more aggressive here and make this nuw / nsw if the
1061 // addition that feeds into the icmp for the latch's terminating branch is nuw
1062 // / nsw. In any case, a wrapping 2's complement addition is safe.
1063 const SCEV *Start = NoopOrExtend(SE.getSCEV(MainLoopStructure.IndVarStart),
1064 RTy, SE, IsSignedPredicate);
1065 const SCEV *End = NoopOrExtend(SE.getSCEV(MainLoopStructure.LoopExitAt), RTy,
1066 SE, IsSignedPredicate);
1067
1068 bool Increasing = MainLoopStructure.IndVarIncreasing;
1069
1070 // We compute `Smallest` and `Greatest` such that [Smallest, Greatest), or
1071 // [Smallest, GreatestSeen] is the range of values the induction variable
1072 // takes.
1073
1074 const SCEV *Smallest = nullptr, *Greatest = nullptr, *GreatestSeen = nullptr;
1075
1076 const SCEV *One = SE.getOne(RTy);
1077 if (Increasing) {
1078 Smallest = Start;
1079 Greatest = End;
1080 // No overflow, because the range [Smallest, GreatestSeen] is not empty.
1081 GreatestSeen = SE.getMinusSCEV(End, One);
1082 } else {
1083 // These two computations may sign-overflow. Here is why that is okay:
1084 //
1085 // We know that the induction variable does not sign-overflow on any
1086 // iteration except the last one, and it starts at `Start` and ends at
1087 // `End`, decrementing by one every time.
1088 //
1089 // * if `Smallest` sign-overflows we know `End` is `INT_SMAX`. Since the
1090 // induction variable is decreasing we know that that the smallest value
1091 // the loop body is actually executed with is `INT_SMIN` == `Smallest`.
1092 //
1093 // * if `Greatest` sign-overflows, we know it can only be `INT_SMIN`. In
1094 // that case, `Clamp` will always return `Smallest` and
1095 // [`Result.LowLimit`, `Result.HighLimit`) = [`Smallest`, `Smallest`)
1096 // will be an empty range. Returning an empty range is always safe.
1097
1098 Smallest = SE.getAddExpr(End, One);
1099 Greatest = SE.getAddExpr(Start, One);
1100 GreatestSeen = Start;
1101 }
1102
1103 auto Clamp = [this, Smallest, Greatest, IsSignedPredicate](const SCEV *S) {
1104 return IsSignedPredicate
1105 ? SE.getSMaxExpr(Smallest, SE.getSMinExpr(Greatest, S))
1106 : SE.getUMaxExpr(Smallest, SE.getUMinExpr(Greatest, S));
1107 };
1108
1109 // In some cases we can prove that we don't need a pre or post loop.
1110 ICmpInst::Predicate PredLE =
1111 IsSignedPredicate ? ICmpInst::ICMP_SLE : ICmpInst::ICMP_ULE;
1112 ICmpInst::Predicate PredLT =
1113 IsSignedPredicate ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT;
1114
1115 bool ProvablyNoPreloop =
1116 SE.isKnownPredicate(PredLE, Range.getBegin(), Smallest);
1117 if (!ProvablyNoPreloop)
1118 Result.LowLimit = Clamp(Range.getBegin());
1119
1120 bool ProvablyNoPostLoop =
1121 SE.isKnownPredicate(PredLT, GreatestSeen, Range.getEnd());
1122 if (!ProvablyNoPostLoop)
1123 Result.HighLimit = Clamp(Range.getEnd());
1124
1125 return Result;
1126}
1127
1128void LoopConstrainer::cloneLoop(LoopConstrainer::ClonedLoop &Result,
1129 const char *Tag) const {
1130 for (BasicBlock *BB : OriginalLoop.getBlocks()) {
1131 BasicBlock *Clone = CloneBasicBlock(BB, Result.Map, Twine(".") + Tag, &F);
1132 Result.Blocks.push_back(Clone);
1133 Result.Map[BB] = Clone;
1134 }
1135
1136 auto GetClonedValue = [&Result](Value *V) {
1137 assert(V && "null values not in domain!")((V && "null values not in domain!") ? static_cast<
void> (0) : __assert_fail ("V && \"null values not in domain!\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp"
, 1137, __PRETTY_FUNCTION__))
;
1138 auto It = Result.Map.find(V);
1139 if (It == Result.Map.end())
1140 return V;
1141 return static_cast<Value *>(It->second);
1142 };
1143
1144 auto *ClonedLatch =
1145 cast<BasicBlock>(GetClonedValue(OriginalLoop.getLoopLatch()));
1146 ClonedLatch->getTerminator()->setMetadata(ClonedLoopTag,
1147 MDNode::get(Ctx, {}));
1148
1149 Result.Structure = MainLoopStructure.map(GetClonedValue);
1150 Result.Structure.Tag = Tag;
1151
1152 for (unsigned i = 0, e = Result.Blocks.size(); i != e; ++i) {
1153 BasicBlock *ClonedBB = Result.Blocks[i];
1154 BasicBlock *OriginalBB = OriginalLoop.getBlocks()[i];
1155
1156 assert(Result.Map[OriginalBB] == ClonedBB && "invariant!")((Result.Map[OriginalBB] == ClonedBB && "invariant!")
? static_cast<void> (0) : __assert_fail ("Result.Map[OriginalBB] == ClonedBB && \"invariant!\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp"
, 1156, __PRETTY_FUNCTION__))
;
1157
1158 for (Instruction &I : *ClonedBB)
1159 RemapInstruction(&I, Result.Map,
1160 RF_NoModuleLevelChanges | RF_IgnoreMissingLocals);
1161
1162 // Exit blocks will now have one more predecessor and their PHI nodes need
1163 // to be edited to reflect that. No phi nodes need to be introduced because
1164 // the loop is in LCSSA.
1165
1166 for (auto *SBB : successors(OriginalBB)) {
1167 if (OriginalLoop.contains(SBB))
1168 continue; // not an exit block
1169
1170 for (PHINode &PN : SBB->phis()) {
1171 Value *OldIncoming = PN.getIncomingValueForBlock(OriginalBB);
1172 PN.addIncoming(GetClonedValue(OldIncoming), ClonedBB);
1173 }
1174 }
1175 }
1176}
1177
1178LoopConstrainer::RewrittenRangeInfo LoopConstrainer::changeIterationSpaceEnd(
1179 const LoopStructure &LS, BasicBlock *Preheader, Value *ExitSubloopAt,
1180 BasicBlock *ContinuationBlock) const {
1181 // We start with a loop with a single latch:
1182 //
1183 // +--------------------+
1184 // | |
1185 // | preheader |
1186 // | |
1187 // +--------+-----------+
1188 // | ----------------\
1189 // | / |
1190 // +--------v----v------+ |
1191 // | | |
1192 // | header | |
1193 // | | |
1194 // +--------------------+ |
1195 // |
1196 // ..... |
1197 // |
1198 // +--------------------+ |
1199 // | | |
1200 // | latch >----------/
1201 // | |
1202 // +-------v------------+
1203 // |
1204 // |
1205 // | +--------------------+
1206 // | | |
1207 // +---> original exit |
1208 // | |
1209 // +--------------------+
1210 //
1211 // We change the control flow to look like
1212 //
1213 //
1214 // +--------------------+
1215 // | |
1216 // | preheader >-------------------------+
1217 // | | |
1218 // +--------v-----------+ |
1219 // | /-------------+ |
1220 // | / | |
1221 // +--------v--v--------+ | |
1222 // | | | |
1223 // | header | | +--------+ |
1224 // | | | | | |
1225 // +--------------------+ | | +-----v-----v-----------+
1226 // | | | |
1227 // | | | .pseudo.exit |
1228 // | | | |
1229 // | | +-----------v-----------+
1230 // | | |
1231 // ..... | | |
1232 // | | +--------v-------------+
1233 // +--------------------+ | | | |
1234 // | | | | | ContinuationBlock |
1235 // | latch >------+ | | |
1236 // | | | +----------------------+
1237 // +---------v----------+ |
1238 // | |
1239 // | |
1240 // | +---------------^-----+
1241 // | | |
1242 // +-----> .exit.selector |
1243 // | |
1244 // +----------v----------+
1245 // |
1246 // +--------------------+ |
1247 // | | |
1248 // | original exit <----+
1249 // | |
1250 // +--------------------+
1251
1252 RewrittenRangeInfo RRI;
1253
1254 BasicBlock *BBInsertLocation = LS.Latch->getNextNode();
1255 RRI.ExitSelector = BasicBlock::Create(Ctx, Twine(LS.Tag) + ".exit.selector",
1256 &F, BBInsertLocation);
1257 RRI.PseudoExit = BasicBlock::Create(Ctx, Twine(LS.Tag) + ".pseudo.exit", &F,
1258 BBInsertLocation);
1259
1260 BranchInst *PreheaderJump = cast<BranchInst>(Preheader->getTerminator());
1261 bool Increasing = LS.IndVarIncreasing;
1262 bool IsSignedPredicate = LS.IsSignedPredicate;
1263
1264 IRBuilder<> B(PreheaderJump);
1265 auto *RangeTy = Range.getBegin()->getType();
1266 auto NoopOrExt = [&](Value *V) {
1267 if (V->getType() == RangeTy)
1268 return V;
1269 return IsSignedPredicate ? B.CreateSExt(V, RangeTy, "wide." + V->getName())
1270 : B.CreateZExt(V, RangeTy, "wide." + V->getName());
1271 };
1272
1273 // EnterLoopCond - is it okay to start executing this `LS'?
1274 Value *EnterLoopCond = nullptr;
1275 auto Pred =
1276 Increasing
1277 ? (IsSignedPredicate ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT)
1278 : (IsSignedPredicate ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT);
1279 Value *IndVarStart = NoopOrExt(LS.IndVarStart);
1280 EnterLoopCond = B.CreateICmp(Pred, IndVarStart, ExitSubloopAt);
1281
1282 B.CreateCondBr(EnterLoopCond, LS.Header, RRI.PseudoExit);
1283 PreheaderJump->eraseFromParent();
1284
1285 LS.LatchBr->setSuccessor(LS.LatchBrExitIdx, RRI.ExitSelector);
1286 B.SetInsertPoint(LS.LatchBr);
1287 Value *IndVarBase = NoopOrExt(LS.IndVarBase);
1288 Value *TakeBackedgeLoopCond = B.CreateICmp(Pred, IndVarBase, ExitSubloopAt);
1289
1290 Value *CondForBranch = LS.LatchBrExitIdx == 1
1291 ? TakeBackedgeLoopCond
1292 : B.CreateNot(TakeBackedgeLoopCond);
1293
1294 LS.LatchBr->setCondition(CondForBranch);
1295
1296 B.SetInsertPoint(RRI.ExitSelector);
1297
1298 // IterationsLeft - are there any more iterations left, given the original
1299 // upper bound on the induction variable? If not, we branch to the "real"
1300 // exit.
1301 Value *LoopExitAt = NoopOrExt(LS.LoopExitAt);
1302 Value *IterationsLeft = B.CreateICmp(Pred, IndVarBase, LoopExitAt);
1303 B.CreateCondBr(IterationsLeft, RRI.PseudoExit, LS.LatchExit);
1304
1305 BranchInst *BranchToContinuation =
1306 BranchInst::Create(ContinuationBlock, RRI.PseudoExit);
1307
1308 // We emit PHI nodes into `RRI.PseudoExit' that compute the "latest" value of
1309 // each of the PHI nodes in the loop header. This feeds into the initial
1310 // value of the same PHI nodes if/when we continue execution.
1311 for (PHINode &PN : LS.Header->phis()) {
1312 PHINode *NewPHI = PHINode::Create(PN.getType(), 2, PN.getName() + ".copy",
1313 BranchToContinuation);
1314
1315 NewPHI->addIncoming(PN.getIncomingValueForBlock(Preheader), Preheader);
1316 NewPHI->addIncoming(PN.getIncomingValueForBlock(LS.Latch),
1317 RRI.ExitSelector);
1318 RRI.PHIValuesAtPseudoExit.push_back(NewPHI);
1319 }
1320
1321 RRI.IndVarEnd = PHINode::Create(IndVarBase->getType(), 2, "indvar.end",
1322 BranchToContinuation);
1323 RRI.IndVarEnd->addIncoming(IndVarStart, Preheader);
1324 RRI.IndVarEnd->addIncoming(IndVarBase, RRI.ExitSelector);
1325
1326 // The latch exit now has a branch from `RRI.ExitSelector' instead of
1327 // `LS.Latch'. The PHI nodes need to be updated to reflect that.
1328 LS.LatchExit->replacePhiUsesWith(LS.Latch, RRI.ExitSelector);
1329
1330 return RRI;
1331}
1332
1333void LoopConstrainer::rewriteIncomingValuesForPHIs(
1334 LoopStructure &LS, BasicBlock *ContinuationBlock,
1335 const LoopConstrainer::RewrittenRangeInfo &RRI) const {
1336 unsigned PHIIndex = 0;
1337 for (PHINode &PN : LS.Header->phis())
1338 for (unsigned i = 0, e = PN.getNumIncomingValues(); i < e; ++i)
1339 if (PN.getIncomingBlock(i) == ContinuationBlock)
1340 PN.setIncomingValue(i, RRI.PHIValuesAtPseudoExit[PHIIndex++]);
1341
1342 LS.IndVarStart = RRI.IndVarEnd;
1343}
1344
1345BasicBlock *LoopConstrainer::createPreheader(const LoopStructure &LS,
1346 BasicBlock *OldPreheader,
1347 const char *Tag) const {
1348 BasicBlock *Preheader = BasicBlock::Create(Ctx, Tag, &F, LS.Header);
1349 BranchInst::Create(LS.Header, Preheader);
1350
1351 LS.Header->replacePhiUsesWith(OldPreheader, Preheader);
1352
1353 return Preheader;
1354}
1355
1356void LoopConstrainer::addToParentLoopIfNeeded(ArrayRef<BasicBlock *> BBs) {
1357 Loop *ParentLoop = OriginalLoop.getParentLoop();
1358 if (!ParentLoop)
1359 return;
1360
1361 for (BasicBlock *BB : BBs)
1362 ParentLoop->addBasicBlockToLoop(BB, LI);
1363}
1364
1365Loop *LoopConstrainer::createClonedLoopStructure(Loop *Original, Loop *Parent,
1366 ValueToValueMapTy &VM,
1367 bool IsSubloop) {
1368 Loop &New = *LI.AllocateLoop();
1369 if (Parent)
1370 Parent->addChildLoop(&New);
1371 else
1372 LI.addTopLevelLoop(&New);
1373 LPMAddNewLoop(&New, IsSubloop);
1374
1375 // Add all of the blocks in Original to the new loop.
1376 for (auto *BB : Original->blocks())
1377 if (LI.getLoopFor(BB) == Original)
1378 New.addBasicBlockToLoop(cast<BasicBlock>(VM[BB]), LI);
1379
1380 // Add all of the subloops to the new loop.
1381 for (Loop *SubLoop : *Original)
1382 createClonedLoopStructure(SubLoop, &New, VM, /* IsSubloop */ true);
1383
1384 return &New;
1385}
1386
1387bool LoopConstrainer::run() {
1388 BasicBlock *Preheader = nullptr;
1389 LatchTakenCount = SE.getExitCount(&OriginalLoop, MainLoopStructure.Latch);
1390 Preheader = OriginalLoop.getLoopPreheader();
1391 assert(!isa<SCEVCouldNotCompute>(LatchTakenCount) && Preheader != nullptr &&((!isa<SCEVCouldNotCompute>(LatchTakenCount) &&
Preheader != nullptr && "preconditions!") ? static_cast
<void> (0) : __assert_fail ("!isa<SCEVCouldNotCompute>(LatchTakenCount) && Preheader != nullptr && \"preconditions!\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp"
, 1392, __PRETTY_FUNCTION__))
1392 "preconditions!")((!isa<SCEVCouldNotCompute>(LatchTakenCount) &&
Preheader != nullptr && "preconditions!") ? static_cast
<void> (0) : __assert_fail ("!isa<SCEVCouldNotCompute>(LatchTakenCount) && Preheader != nullptr && \"preconditions!\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp"
, 1392, __PRETTY_FUNCTION__))
;
1393
1394 OriginalPreheader = Preheader;
1395 MainLoopPreheader = Preheader;
1396
1397 bool IsSignedPredicate = MainLoopStructure.IsSignedPredicate;
1398 Optional<SubRanges> MaybeSR = calculateSubRanges(IsSignedPredicate);
1399 if (!MaybeSR.hasValue()) {
1400 LLVM_DEBUG(dbgs() << "irce: could not compute subranges\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("irce")) { dbgs() << "irce: could not compute subranges\n"
; } } while (false)
;
1401 return false;
1402 }
1403
1404 SubRanges SR = MaybeSR.getValue();
1405 bool Increasing = MainLoopStructure.IndVarIncreasing;
1406 IntegerType *IVTy =
1407 cast<IntegerType>(Range.getBegin()->getType());
1408
1409 SCEVExpander Expander(SE, F.getParent()->getDataLayout(), "irce");
1410 Instruction *InsertPt = OriginalPreheader->getTerminator();
1411
1412 // It would have been better to make `PreLoop' and `PostLoop'
1413 // `Optional<ClonedLoop>'s, but `ValueToValueMapTy' does not have a copy
1414 // constructor.
1415 ClonedLoop PreLoop, PostLoop;
1416 bool NeedsPreLoop =
1417 Increasing ? SR.LowLimit.hasValue() : SR.HighLimit.hasValue();
1418 bool NeedsPostLoop =
1419 Increasing ? SR.HighLimit.hasValue() : SR.LowLimit.hasValue();
1420
1421 Value *ExitPreLoopAt = nullptr;
1422 Value *ExitMainLoopAt = nullptr;
1423 const SCEVConstant *MinusOneS =
1424 cast<SCEVConstant>(SE.getConstant(IVTy, -1, true /* isSigned */));
1425
1426 if (NeedsPreLoop) {
1427 const SCEV *ExitPreLoopAtSCEV = nullptr;
1428
1429 if (Increasing)
1430 ExitPreLoopAtSCEV = *SR.LowLimit;
1431 else if (cannotBeMinInLoop(*SR.HighLimit, &OriginalLoop, SE,
1432 IsSignedPredicate))
1433 ExitPreLoopAtSCEV = SE.getAddExpr(*SR.HighLimit, MinusOneS);
1434 else {
1435 LLVM_DEBUG(dbgs() << "irce: could not prove no-overflow when computing "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("irce")) { dbgs() << "irce: could not prove no-overflow when computing "
<< "preloop exit limit. HighLimit = " << *(*SR.
HighLimit) << "\n"; } } while (false)
1436 << "preloop exit limit. HighLimit = "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("irce")) { dbgs() << "irce: could not prove no-overflow when computing "
<< "preloop exit limit. HighLimit = " << *(*SR.
HighLimit) << "\n"; } } while (false)
1437 << *(*SR.HighLimit) << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("irce")) { dbgs() << "irce: could not prove no-overflow when computing "
<< "preloop exit limit. HighLimit = " << *(*SR.
HighLimit) << "\n"; } } while (false)
;
1438 return false;
1439 }
1440
1441 if (!isSafeToExpandAt(ExitPreLoopAtSCEV, InsertPt, SE)) {
1442 LLVM_DEBUG(dbgs() << "irce: could not prove that it is safe to expand the"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("irce")) { dbgs() << "irce: could not prove that it is safe to expand the"
<< " preloop exit limit " << *ExitPreLoopAtSCEV <<
" at block " << InsertPt->getParent()->getName()
<< "\n"; } } while (false)
1443 << " preloop exit limit " << *ExitPreLoopAtSCEVdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("irce")) { dbgs() << "irce: could not prove that it is safe to expand the"
<< " preloop exit limit " << *ExitPreLoopAtSCEV <<
" at block " << InsertPt->getParent()->getName()
<< "\n"; } } while (false)
1444 << " at block " << InsertPt->getParent()->getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("irce")) { dbgs() << "irce: could not prove that it is safe to expand the"
<< " preloop exit limit " << *ExitPreLoopAtSCEV <<
" at block " << InsertPt->getParent()->getName()
<< "\n"; } } while (false)
1445 << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("irce")) { dbgs() << "irce: could not prove that it is safe to expand the"
<< " preloop exit limit " << *ExitPreLoopAtSCEV <<
" at block " << InsertPt->getParent()->getName()
<< "\n"; } } while (false)
;
1446 return false;
1447 }
1448
1449 ExitPreLoopAt = Expander.expandCodeFor(ExitPreLoopAtSCEV, IVTy, InsertPt);
1450 ExitPreLoopAt->setName("exit.preloop.at");
1451 }
1452
1453 if (NeedsPostLoop) {
1454 const SCEV *ExitMainLoopAtSCEV = nullptr;
1455
1456 if (Increasing)
1457 ExitMainLoopAtSCEV = *SR.HighLimit;
1458 else if (cannotBeMinInLoop(*SR.LowLimit, &OriginalLoop, SE,
1459 IsSignedPredicate))
1460 ExitMainLoopAtSCEV = SE.getAddExpr(*SR.LowLimit, MinusOneS);
1461 else {
1462 LLVM_DEBUG(dbgs() << "irce: could not prove no-overflow when computing "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("irce")) { dbgs() << "irce: could not prove no-overflow when computing "
<< "mainloop exit limit. LowLimit = " << *(*SR.
LowLimit) << "\n"; } } while (false)
1463 << "mainloop exit limit. LowLimit = "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("irce")) { dbgs() << "irce: could not prove no-overflow when computing "
<< "mainloop exit limit. LowLimit = " << *(*SR.
LowLimit) << "\n"; } } while (false)
1464 << *(*SR.LowLimit) << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("irce")) { dbgs() << "irce: could not prove no-overflow when computing "
<< "mainloop exit limit. LowLimit = " << *(*SR.
LowLimit) << "\n"; } } while (false)
;
1465 return false;
1466 }
1467
1468 if (!isSafeToExpandAt(ExitMainLoopAtSCEV, InsertPt, SE)) {
1469 LLVM_DEBUG(dbgs() << "irce: could not prove that it is safe to expand the"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("irce")) { dbgs() << "irce: could not prove that it is safe to expand the"
<< " main loop exit limit " << *ExitMainLoopAtSCEV
<< " at block " << InsertPt->getParent()->
getName() << "\n"; } } while (false)
1470 << " main loop exit limit " << *ExitMainLoopAtSCEVdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("irce")) { dbgs() << "irce: could not prove that it is safe to expand the"
<< " main loop exit limit " << *ExitMainLoopAtSCEV
<< " at block " << InsertPt->getParent()->
getName() << "\n"; } } while (false)
1471 << " at block " << InsertPt->getParent()->getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("irce")) { dbgs() << "irce: could not prove that it is safe to expand the"
<< " main loop exit limit " << *ExitMainLoopAtSCEV
<< " at block " << InsertPt->getParent()->
getName() << "\n"; } } while (false)
1472 << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("irce")) { dbgs() << "irce: could not prove that it is safe to expand the"
<< " main loop exit limit " << *ExitMainLoopAtSCEV
<< " at block " << InsertPt->getParent()->
getName() << "\n"; } } while (false)
;
1473 return false;
1474 }
1475
1476 ExitMainLoopAt = Expander.expandCodeFor(ExitMainLoopAtSCEV, IVTy, InsertPt);
1477 ExitMainLoopAt->setName("exit.mainloop.at");
1478 }
1479
1480 // We clone these ahead of time so that we don't have to deal with changing
1481 // and temporarily invalid IR as we transform the loops.
1482 if (NeedsPreLoop)
1483 cloneLoop(PreLoop, "preloop");
1484 if (NeedsPostLoop)
1485 cloneLoop(PostLoop, "postloop");
1486
1487 RewrittenRangeInfo PreLoopRRI;
1488
1489 if (NeedsPreLoop) {
1490 Preheader->getTerminator()->replaceUsesOfWith(MainLoopStructure.Header,
1491 PreLoop.Structure.Header);
1492
1493 MainLoopPreheader =
1494 createPreheader(MainLoopStructure, Preheader, "mainloop");
1495 PreLoopRRI = changeIterationSpaceEnd(PreLoop.Structure, Preheader,
1496 ExitPreLoopAt, MainLoopPreheader);
1497 rewriteIncomingValuesForPHIs(MainLoopStructure, MainLoopPreheader,
1498 PreLoopRRI);
1499 }
1500
1501 BasicBlock *PostLoopPreheader = nullptr;
1502 RewrittenRangeInfo PostLoopRRI;
1503
1504 if (NeedsPostLoop) {
1505 PostLoopPreheader =
1506 createPreheader(PostLoop.Structure, Preheader, "postloop");
1507 PostLoopRRI = changeIterationSpaceEnd(MainLoopStructure, MainLoopPreheader,
1508 ExitMainLoopAt, PostLoopPreheader);
1509 rewriteIncomingValuesForPHIs(PostLoop.Structure, PostLoopPreheader,
1510 PostLoopRRI);
1511 }
1512
1513 BasicBlock *NewMainLoopPreheader =
1514 MainLoopPreheader != Preheader ? MainLoopPreheader : nullptr;
1515 BasicBlock *NewBlocks[] = {PostLoopPreheader, PreLoopRRI.PseudoExit,
1516 PreLoopRRI.ExitSelector, PostLoopRRI.PseudoExit,
1517 PostLoopRRI.ExitSelector, NewMainLoopPreheader};
1518
1519 // Some of the above may be nullptr, filter them out before passing to
1520 // addToParentLoopIfNeeded.
1521 auto NewBlocksEnd =
1522 std::remove(std::begin(NewBlocks), std::end(NewBlocks), nullptr);
1523
1524 addToParentLoopIfNeeded(makeArrayRef(std::begin(NewBlocks), NewBlocksEnd));
1525
1526 DT.recalculate(F);
1527
1528 // We need to first add all the pre and post loop blocks into the loop
1529 // structures (as part of createClonedLoopStructure), and then update the
1530 // LCSSA form and LoopSimplifyForm. This is necessary for correctly updating
1531 // LI when LoopSimplifyForm is generated.
1532 Loop *PreL = nullptr, *PostL = nullptr;
1533 if (!PreLoop.Blocks.empty()) {
1534 PreL = createClonedLoopStructure(&OriginalLoop,
1535 OriginalLoop.getParentLoop(), PreLoop.Map,
1536 /* IsSubLoop */ false);
1537 }
1538
1539 if (!PostLoop.Blocks.empty()) {
1540 PostL =
1541 createClonedLoopStructure(&OriginalLoop, OriginalLoop.getParentLoop(),
1542 PostLoop.Map, /* IsSubLoop */ false);
1543 }
1544
1545 // This function canonicalizes the loop into Loop-Simplify and LCSSA forms.
1546 auto CanonicalizeLoop = [&] (Loop *L, bool IsOriginalLoop) {
1547 formLCSSARecursively(*L, DT, &LI, &SE);
1548 simplifyLoop(L, &DT, &LI, &SE, nullptr, nullptr, true);
1549 // Pre/post loops are slow paths, we do not need to perform any loop
1550 // optimizations on them.
1551 if (!IsOriginalLoop)
1552 DisableAllLoopOptsOnLoop(*L);
1553 };
1554 if (PreL)
1555 CanonicalizeLoop(PreL, false);
1556 if (PostL)
1557 CanonicalizeLoop(PostL, false);
1558 CanonicalizeLoop(&OriginalLoop, true);
1559
1560 return true;
1561}
1562
1563/// Computes and returns a range of values for the induction variable (IndVar)
1564/// in which the range check can be safely elided. If it cannot compute such a
1565/// range, returns None.
1566Optional<InductiveRangeCheck::Range>
1567InductiveRangeCheck::computeSafeIterationSpace(
1568 ScalarEvolution &SE, const SCEVAddRecExpr *IndVar,
1569 bool IsLatchSigned) const {
1570 // We can deal when types of latch check and range checks don't match in case
1571 // if latch check is more narrow.
1572 auto *IVType = cast<IntegerType>(IndVar->getType());
1573 auto *RCType = cast<IntegerType>(getBegin()->getType());
1574 if (IVType->getBitWidth() > RCType->getBitWidth())
1575 return None;
1576 // IndVar is of the form "A + B * I" (where "I" is the canonical induction
1577 // variable, that may or may not exist as a real llvm::Value in the loop) and
1578 // this inductive range check is a range check on the "C + D * I" ("C" is
1579 // getBegin() and "D" is getStep()). We rewrite the value being range
1580 // checked to "M + N * IndVar" where "N" = "D * B^(-1)" and "M" = "C - NA".
1581 //
1582 // The actual inequalities we solve are of the form
1583 //
1584 // 0 <= M + 1 * IndVar < L given L >= 0 (i.e. N == 1)
1585 //
1586 // Here L stands for upper limit of the safe iteration space.
1587 // The inequality is satisfied by (0 - M) <= IndVar < (L - M). To avoid
1588 // overflows when calculating (0 - M) and (L - M) we, depending on type of
1589 // IV's iteration space, limit the calculations by borders of the iteration
1590 // space. For example, if IndVar is unsigned, (0 - M) overflows for any M > 0.
1591 // If we figured out that "anything greater than (-M) is safe", we strengthen
1592 // this to "everything greater than 0 is safe", assuming that values between
1593 // -M and 0 just do not exist in unsigned iteration space, and we don't want
1594 // to deal with overflown values.
1595
1596 if (!IndVar->isAffine())
1597 return None;
1598
1599 const SCEV *A = NoopOrExtend(IndVar->getStart(), RCType, SE, IsLatchSigned);
1600 const SCEVConstant *B = dyn_cast<SCEVConstant>(
1601 NoopOrExtend(IndVar->getStepRecurrence(SE), RCType, SE, IsLatchSigned));
1602 if (!B)
1603 return None;
1604 assert(!B->isZero() && "Recurrence with zero step?")((!B->isZero() && "Recurrence with zero step?") ? static_cast
<void> (0) : __assert_fail ("!B->isZero() && \"Recurrence with zero step?\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp"
, 1604, __PRETTY_FUNCTION__))
;
1605
1606 const SCEV *C = getBegin();
1607 const SCEVConstant *D = dyn_cast<SCEVConstant>(getStep());
1608 if (D != B)
1609 return None;
1610
1611 assert(!D->getValue()->isZero() && "Recurrence with zero step?")((!D->getValue()->isZero() && "Recurrence with zero step?"
) ? static_cast<void> (0) : __assert_fail ("!D->getValue()->isZero() && \"Recurrence with zero step?\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp"
, 1611, __PRETTY_FUNCTION__))
;
1612 unsigned BitWidth = RCType->getBitWidth();
1613 const SCEV *SIntMax = SE.getConstant(APInt::getSignedMaxValue(BitWidth));
1614
1615 // Subtract Y from X so that it does not go through border of the IV
1616 // iteration space. Mathematically, it is equivalent to:
1617 //
1618 // ClampedSubtract(X, Y) = min(max(X - Y, INT_MIN), INT_MAX). [1]
1619 //
1620 // In [1], 'X - Y' is a mathematical subtraction (result is not bounded to
1621 // any width of bit grid). But after we take min/max, the result is
1622 // guaranteed to be within [INT_MIN, INT_MAX].
1623 //
1624 // In [1], INT_MAX and INT_MIN are respectively signed and unsigned max/min
1625 // values, depending on type of latch condition that defines IV iteration
1626 // space.
1627 auto ClampedSubtract = [&](const SCEV *X, const SCEV *Y) {
1628 // FIXME: The current implementation assumes that X is in [0, SINT_MAX].
1629 // This is required to ensure that SINT_MAX - X does not overflow signed and
1630 // that X - Y does not overflow unsigned if Y is negative. Can we lift this
1631 // restriction and make it work for negative X either?
1632 if (IsLatchSigned) {
1633 // X is a number from signed range, Y is interpreted as signed.
1634 // Even if Y is SINT_MAX, (X - Y) does not reach SINT_MIN. So the only
1635 // thing we should care about is that we didn't cross SINT_MAX.
1636 // So, if Y is positive, we subtract Y safely.
1637 // Rule 1: Y > 0 ---> Y.
1638 // If 0 <= -Y <= (SINT_MAX - X), we subtract Y safely.
1639 // Rule 2: Y >=s (X - SINT_MAX) ---> Y.
1640 // If 0 <= (SINT_MAX - X) < -Y, we can only subtract (X - SINT_MAX).
1641 // Rule 3: Y <s (X - SINT_MAX) ---> (X - SINT_MAX).
1642 // It gives us smax(Y, X - SINT_MAX) to subtract in all cases.
1643 const SCEV *XMinusSIntMax = SE.getMinusSCEV(X, SIntMax);
1644 return SE.getMinusSCEV(X, SE.getSMaxExpr(Y, XMinusSIntMax),
1645 SCEV::FlagNSW);
1646 } else
1647 // X is a number from unsigned range, Y is interpreted as signed.
1648 // Even if Y is SINT_MIN, (X - Y) does not reach UINT_MAX. So the only
1649 // thing we should care about is that we didn't cross zero.
1650 // So, if Y is negative, we subtract Y safely.
1651 // Rule 1: Y <s 0 ---> Y.
1652 // If 0 <= Y <= X, we subtract Y safely.
1653 // Rule 2: Y <=s X ---> Y.
1654 // If 0 <= X < Y, we should stop at 0 and can only subtract X.
1655 // Rule 3: Y >s X ---> X.
1656 // It gives us smin(X, Y) to subtract in all cases.
1657 return SE.getMinusSCEV(X, SE.getSMinExpr(X, Y), SCEV::FlagNUW);
1658 };
1659 const SCEV *M = SE.getMinusSCEV(C, A);
1660 const SCEV *Zero = SE.getZero(M->getType());
1661
1662 // This function returns SCEV equal to 1 if X is non-negative 0 otherwise.
1663 auto SCEVCheckNonNegative = [&](const SCEV *X) {
1664 const Loop *L = IndVar->getLoop();
1665 const SCEV *One = SE.getOne(X->getType());
1666 // Can we trivially prove that X is a non-negative or negative value?
1667 if (isKnownNonNegativeInLoop(X, L, SE))
1668 return One;
1669 else if (isKnownNegativeInLoop(X, L, SE))
1670 return Zero;
1671 // If not, we will have to figure it out during the execution.
1672 // Function smax(smin(X, 0), -1) + 1 equals to 1 if X >= 0 and 0 if X < 0.
1673 const SCEV *NegOne = SE.getNegativeSCEV(One);
1674 return SE.getAddExpr(SE.getSMaxExpr(SE.getSMinExpr(X, Zero), NegOne), One);
1675 };
1676 // FIXME: Current implementation of ClampedSubtract implicitly assumes that
1677 // X is non-negative (in sense of a signed value). We need to re-implement
1678 // this function in a way that it will correctly handle negative X as well.
1679 // We use it twice: for X = 0 everything is fine, but for X = getEnd() we can
1680 // end up with a negative X and produce wrong results. So currently we ensure
1681 // that if getEnd() is negative then both ends of the safe range are zero.
1682 // Note that this may pessimize elimination of unsigned range checks against
1683 // negative values.
1684 const SCEV *REnd = getEnd();
1685 const SCEV *EndIsNonNegative = SCEVCheckNonNegative(REnd);
1686
1687 const SCEV *Begin = SE.getMulExpr(ClampedSubtract(Zero, M), EndIsNonNegative);
1688 const SCEV *End = SE.getMulExpr(ClampedSubtract(REnd, M), EndIsNonNegative);
1689 return InductiveRangeCheck::Range(Begin, End);
1690}
1691
1692static Optional<InductiveRangeCheck::Range>
1693IntersectSignedRange(ScalarEvolution &SE,
1694 const Optional<InductiveRangeCheck::Range> &R1,
1695 const InductiveRangeCheck::Range &R2) {
1696 if (R2.isEmpty(SE, /* IsSigned */ true))
1697 return None;
1698 if (!R1.hasValue())
1699 return R2;
1700 auto &R1Value = R1.getValue();
1701 // We never return empty ranges from this function, and R1 is supposed to be
1702 // a result of intersection. Thus, R1 is never empty.
1703 assert(!R1Value.isEmpty(SE, /* IsSigned */ true) &&((!R1Value.isEmpty(SE, true) && "We should never have empty R1!"
) ? static_cast<void> (0) : __assert_fail ("!R1Value.isEmpty(SE, true) && \"We should never have empty R1!\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp"
, 1704, __PRETTY_FUNCTION__))
1704 "We should never have empty R1!")((!R1Value.isEmpty(SE, true) && "We should never have empty R1!"
) ? static_cast<void> (0) : __assert_fail ("!R1Value.isEmpty(SE, true) && \"We should never have empty R1!\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp"
, 1704, __PRETTY_FUNCTION__))
;
1705
1706 // TODO: we could widen the smaller range and have this work; but for now we
1707 // bail out to keep things simple.
1708 if (R1Value.getType() != R2.getType())
1709 return None;
1710
1711 const SCEV *NewBegin = SE.getSMaxExpr(R1Value.getBegin(), R2.getBegin());
1712 const SCEV *NewEnd = SE.getSMinExpr(R1Value.getEnd(), R2.getEnd());
1713
1714 // If the resulting range is empty, just return None.
1715 auto Ret = InductiveRangeCheck::Range(NewBegin, NewEnd);
1716 if (Ret.isEmpty(SE, /* IsSigned */ true))
1717 return None;
1718 return Ret;
1719}
1720
1721static Optional<InductiveRangeCheck::Range>
1722IntersectUnsignedRange(ScalarEvolution &SE,
1723 const Optional<InductiveRangeCheck::Range> &R1,
1724 const InductiveRangeCheck::Range &R2) {
1725 if (R2.isEmpty(SE, /* IsSigned */ false))
1726 return None;
1727 if (!R1.hasValue())
1728 return R2;
1729 auto &R1Value = R1.getValue();
1730 // We never return empty ranges from this function, and R1 is supposed to be
1731 // a result of intersection. Thus, R1 is never empty.
1732 assert(!R1Value.isEmpty(SE, /* IsSigned */ false) &&((!R1Value.isEmpty(SE, false) && "We should never have empty R1!"
) ? static_cast<void> (0) : __assert_fail ("!R1Value.isEmpty(SE, false) && \"We should never have empty R1!\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp"
, 1733, __PRETTY_FUNCTION__))
1733 "We should never have empty R1!")((!R1Value.isEmpty(SE, false) && "We should never have empty R1!"
) ? static_cast<void> (0) : __assert_fail ("!R1Value.isEmpty(SE, false) && \"We should never have empty R1!\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp"
, 1733, __PRETTY_FUNCTION__))
;
1734
1735 // TODO: we could widen the smaller range and have this work; but for now we
1736 // bail out to keep things simple.
1737 if (R1Value.getType() != R2.getType())
1738 return None;
1739
1740 const SCEV *NewBegin = SE.getUMaxExpr(R1Value.getBegin(), R2.getBegin());
1741 const SCEV *NewEnd = SE.getUMinExpr(R1Value.getEnd(), R2.getEnd());
1742
1743 // If the resulting range is empty, just return None.
1744 auto Ret = InductiveRangeCheck::Range(NewBegin, NewEnd);
1745 if (Ret.isEmpty(SE, /* IsSigned */ false))
1746 return None;
1747 return Ret;
1748}
1749
1750PreservedAnalyses IRCEPass::run(Loop &L, LoopAnalysisManager &AM,
1751 LoopStandardAnalysisResults &AR,
1752 LPMUpdater &U) {
1753 Function *F = L.getHeader()->getParent();
1754 const auto &FAM =
1755 AM.getResult<FunctionAnalysisManagerLoopProxy>(L, AR).getManager();
1756 auto *BPI = FAM.getCachedResult<BranchProbabilityAnalysis>(*F);
1757 InductiveRangeCheckElimination IRCE(AR.SE, BPI, AR.DT, AR.LI);
1758 auto LPMAddNewLoop = [&U](Loop *NL, bool IsSubloop) {
1759 if (!IsSubloop)
1760 U.addSiblingLoops(NL);
1761 };
1762 bool Changed = IRCE.run(&L, LPMAddNewLoop);
1763 if (!Changed)
1764 return PreservedAnalyses::all();
1765
1766 return getLoopPassPreservedAnalyses();
1767}
1768
1769bool IRCELegacyPass::runOnLoop(Loop *L, LPPassManager &LPM) {
1770 if (skipLoop(L))
1771 return false;
1772
1773 ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
1774 BranchProbabilityInfo &BPI =
1775 getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI();
1776 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1777 auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
1778 InductiveRangeCheckElimination IRCE(SE, &BPI, DT, LI);
1779 auto LPMAddNewLoop = [&LPM](Loop *NL, bool /* IsSubLoop */) {
1780 LPM.addLoop(*NL);
1781 };
1782 return IRCE.run(L, LPMAddNewLoop);
1783}
1784
1785bool InductiveRangeCheckElimination::run(
1786 Loop *L, function_ref<void(Loop *, bool)> LPMAddNewLoop) {
1787 if (L->getBlocks().size() >= LoopSizeCutoff) {
1788 LLVM_DEBUG(dbgs() << "irce: giving up constraining loop, too large\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("irce")) { dbgs() << "irce: giving up constraining loop, too large\n"
; } } while (false)
;
1789 return false;
1790 }
1791
1792 BasicBlock *Preheader = L->getLoopPreheader();
1793 if (!Preheader) {
1794 LLVM_DEBUG(dbgs() << "irce: loop has no preheader, leaving\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("irce")) { dbgs() << "irce: loop has no preheader, leaving\n"
; } } while (false)
;
1795 return false;
1796 }
1797
1798 LLVMContext &Context = Preheader->getContext();
1799 SmallVector<InductiveRangeCheck, 16> RangeChecks;
1800
1801 for (auto BBI : L->getBlocks())
1802 if (BranchInst *TBI = dyn_cast<BranchInst>(BBI->getTerminator()))
1803 InductiveRangeCheck::extractRangeChecksFromBranch(TBI, L, SE, BPI,
1804 RangeChecks);
1805
1806 if (RangeChecks.empty())
1807 return false;
1808
1809 auto PrintRecognizedRangeChecks = [&](raw_ostream &OS) {
1810 OS << "irce: looking at loop "; L->print(OS);
1811 OS << "irce: loop has " << RangeChecks.size()
1812 << " inductive range checks: \n";
1813 for (InductiveRangeCheck &IRC : RangeChecks)
1814 IRC.print(OS);
1815 };
1816
1817 LLVM_DEBUG(PrintRecognizedRangeChecks(dbgs()))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("irce")) { PrintRecognizedRangeChecks(dbgs()); } } while (false
)
;
1818
1819 if (PrintRangeChecks)
1820 PrintRecognizedRangeChecks(errs());
1821
1822 const char *FailureReason = nullptr;
1823 Optional<LoopStructure> MaybeLoopStructure =
1824 LoopStructure::parseLoopStructure(SE, BPI, *L, FailureReason);
1825 if (!MaybeLoopStructure.hasValue()) {
1826 LLVM_DEBUG(dbgs() << "irce: could not parse loop structure: "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("irce")) { dbgs() << "irce: could not parse loop structure: "
<< FailureReason << "\n";; } } while (false)
1827 << FailureReason << "\n";)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("irce")) { dbgs() << "irce: could not parse loop structure: "
<< FailureReason << "\n";; } } while (false)
;
1828 return false;
1829 }
1830 LoopStructure LS = MaybeLoopStructure.getValue();
1831 const SCEVAddRecExpr *IndVar =
1832 cast<SCEVAddRecExpr>(SE.getMinusSCEV(SE.getSCEV(LS.IndVarBase), SE.getSCEV(LS.IndVarStep)));
1833
1834 Optional<InductiveRangeCheck::Range> SafeIterRange;
1835 Instruction *ExprInsertPt = Preheader->getTerminator();
1836
1837 SmallVector<InductiveRangeCheck, 4> RangeChecksToEliminate;
1838 // Basing on the type of latch predicate, we interpret the IV iteration range
1839 // as signed or unsigned range. We use different min/max functions (signed or
1840 // unsigned) when intersecting this range with safe iteration ranges implied
1841 // by range checks.
1842 auto IntersectRange =
1843 LS.IsSignedPredicate ? IntersectSignedRange : IntersectUnsignedRange;
1844
1845 IRBuilder<> B(ExprInsertPt);
1846 for (InductiveRangeCheck &IRC : RangeChecks) {
1847 auto Result = IRC.computeSafeIterationSpace(SE, IndVar,
1848 LS.IsSignedPredicate);
1849 if (Result.hasValue()) {
1850 auto MaybeSafeIterRange =
1851 IntersectRange(SE, SafeIterRange, Result.getValue());
1852 if (MaybeSafeIterRange.hasValue()) {
1853 assert(((!MaybeSafeIterRange.getValue().isEmpty(SE, LS.IsSignedPredicate
) && "We should never return empty ranges!") ? static_cast
<void> (0) : __assert_fail ("!MaybeSafeIterRange.getValue().isEmpty(SE, LS.IsSignedPredicate) && \"We should never return empty ranges!\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp"
, 1855, __PRETTY_FUNCTION__))
1854 !MaybeSafeIterRange.getValue().isEmpty(SE, LS.IsSignedPredicate) &&((!MaybeSafeIterRange.getValue().isEmpty(SE, LS.IsSignedPredicate
) && "We should never return empty ranges!") ? static_cast
<void> (0) : __assert_fail ("!MaybeSafeIterRange.getValue().isEmpty(SE, LS.IsSignedPredicate) && \"We should never return empty ranges!\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp"
, 1855, __PRETTY_FUNCTION__))
1855 "We should never return empty ranges!")((!MaybeSafeIterRange.getValue().isEmpty(SE, LS.IsSignedPredicate
) && "We should never return empty ranges!") ? static_cast
<void> (0) : __assert_fail ("!MaybeSafeIterRange.getValue().isEmpty(SE, LS.IsSignedPredicate) && \"We should never return empty ranges!\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp"
, 1855, __PRETTY_FUNCTION__))
;
1856 RangeChecksToEliminate.push_back(IRC);
1857 SafeIterRange = MaybeSafeIterRange.getValue();
1858 }
1859 }
1860 }
1861
1862 if (!SafeIterRange.hasValue())
1863 return false;
1864
1865 LoopConstrainer LC(*L, LI, LPMAddNewLoop, LS, SE, DT,
1866 SafeIterRange.getValue());
1867 bool Changed = LC.run();
1868
1869 if (Changed) {
1870 auto PrintConstrainedLoopInfo = [L]() {
1871 dbgs() << "irce: in function ";
1872 dbgs() << L->getHeader()->getParent()->getName() << ": ";
1873 dbgs() << "constrained ";
1874 L->print(dbgs());
1875 };
1876
1877 LLVM_DEBUG(PrintConstrainedLoopInfo())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("irce")) { PrintConstrainedLoopInfo(); } } while (false)
;
1878
1879 if (PrintChangedLoops)
1880 PrintConstrainedLoopInfo();
1881
1882 // Optimize away the now-redundant range checks.
1883
1884 for (InductiveRangeCheck &IRC : RangeChecksToEliminate) {
1885 ConstantInt *FoldedRangeCheck = IRC.getPassingDirection()
1886 ? ConstantInt::getTrue(Context)
1887 : ConstantInt::getFalse(Context);
1888 IRC.getCheckUse()->set(FoldedRangeCheck);
1889 }
1890 }
1891
1892 return Changed;
1893}
1894
1895Pass *llvm::createInductiveRangeCheckEliminationPass() {
1896 return new IRCELegacyPass();
1897}