Bug Summary

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