1ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines//===-- InductiveRangeCheckElimination.cpp - ------------------------------===// 2ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines// 3ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines// The LLVM Compiler Infrastructure 4ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines// 5ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines// This file is distributed under the University of Illinois Open Source 6ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines// License. See LICENSE.TXT for details. 7ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines// 8ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines//===----------------------------------------------------------------------===// 9ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines// The InductiveRangeCheckElimination pass splits a loop's iteration space into 10ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines// three disjoint ranges. It does that in a way such that the loop running in 11ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines// the middle loop provably does not need range checks. As an example, it will 12ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines// convert 13ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines// 14ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines// len = < known positive > 15ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines// for (i = 0; i < n; i++) { 16ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines// if (0 <= i && i < len) { 17ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines// do_something(); 18ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines// } else { 19ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines// throw_out_of_bounds(); 20ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines// } 21ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines// } 22ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines// 23ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines// to 24ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines// 25ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines// len = < known positive > 26ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines// limit = smin(n, len) 27ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines// // no first segment 28ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines// for (i = 0; i < limit; i++) { 29ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines// if (0 <= i && i < len) { // this check is fully redundant 30ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines// do_something(); 31ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines// } else { 32ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines// throw_out_of_bounds(); 33ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines// } 34ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines// } 35ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines// for (i = limit; i < n; i++) { 36ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines// if (0 <= i && i < len) { 37ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines// do_something(); 38ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines// } else { 39ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines// throw_out_of_bounds(); 40ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines// } 41ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines// } 42ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines//===----------------------------------------------------------------------===// 43ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 44ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines#include "llvm/ADT/Optional.h" 45ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines#include "llvm/Analysis/BranchProbabilityInfo.h" 46ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines#include "llvm/Analysis/InstructionSimplify.h" 47ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines#include "llvm/Analysis/LoopInfo.h" 48ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines#include "llvm/Analysis/LoopPass.h" 49ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines#include "llvm/Analysis/ScalarEvolution.h" 50ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines#include "llvm/Analysis/ScalarEvolutionExpander.h" 51ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines#include "llvm/Analysis/ScalarEvolutionExpressions.h" 52ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines#include "llvm/Analysis/ValueTracking.h" 53ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines#include "llvm/IR/Dominators.h" 54ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines#include "llvm/IR/Function.h" 55ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines#include "llvm/IR/IRBuilder.h" 564c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar#include "llvm/IR/Instructions.h" 57ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines#include "llvm/IR/Module.h" 58ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines#include "llvm/IR/PatternMatch.h" 59ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines#include "llvm/IR/ValueHandle.h" 60ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines#include "llvm/IR/Verifier.h" 614c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar#include "llvm/Pass.h" 62ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines#include "llvm/Support/Debug.h" 634c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar#include "llvm/Support/raw_ostream.h" 64ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines#include "llvm/Transforms/Scalar.h" 65ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines#include "llvm/Transforms/Utils/BasicBlockUtils.h" 66ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines#include "llvm/Transforms/Utils/Cloning.h" 67ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines#include "llvm/Transforms/Utils/LoopUtils.h" 68ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines#include "llvm/Transforms/Utils/SimplifyIndVar.h" 69ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines#include "llvm/Transforms/Utils/UnrollLoop.h" 70ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines#include <array> 71ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 72ebe69fe11e48d322045d5949c83283927a0d790bStephen Hinesusing namespace llvm; 73ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 74ebe69fe11e48d322045d5949c83283927a0d790bStephen Hinesstatic cl::opt<unsigned> LoopSizeCutoff("irce-loop-size-cutoff", cl::Hidden, 75ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines cl::init(64)); 76ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 77ebe69fe11e48d322045d5949c83283927a0d790bStephen Hinesstatic cl::opt<bool> PrintChangedLoops("irce-print-changed-loops", cl::Hidden, 78ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines cl::init(false)); 79ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 804c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainarstatic cl::opt<bool> PrintRangeChecks("irce-print-range-checks", cl::Hidden, 814c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar cl::init(false)); 824c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 83ebe69fe11e48d322045d5949c83283927a0d790bStephen Hinesstatic cl::opt<int> MaxExitProbReciprocal("irce-max-exit-prob-reciprocal", 84ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines cl::Hidden, cl::init(10)); 85ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 86ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines#define DEBUG_TYPE "irce" 87ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 88ebe69fe11e48d322045d5949c83283927a0d790bStephen Hinesnamespace { 89ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 90ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// An inductive range check is conditional branch in a loop with 91ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// 92ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// 1. a very cold successor (i.e. the branch jumps to that successor very 93ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// rarely) 94ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// 95ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// and 96ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// 974c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar/// 2. a condition that is provably true for some contiguous range of values 984c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar/// taken by the containing loop's induction variable. 99ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// 100ebe69fe11e48d322045d5949c83283927a0d790bStephen Hinesclass InductiveRangeCheck { 1014c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // Classifies a range check 1024c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar enum RangeCheckKind : unsigned { 1034c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // Range check of the form "0 <= I". 1044c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar RANGE_CHECK_LOWER = 1, 1054c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 1064c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // Range check of the form "I < L" where L is known positive. 1074c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar RANGE_CHECK_UPPER = 2, 1084c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 1094c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // The logical and of the RANGE_CHECK_LOWER and RANGE_CHECK_UPPER 1104c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // conditions. 1114c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar RANGE_CHECK_BOTH = RANGE_CHECK_LOWER | RANGE_CHECK_UPPER, 1124c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 1134c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // Unrecognized range check condition. 1144c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar RANGE_CHECK_UNKNOWN = (unsigned)-1 1154c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar }; 1164c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 1174c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar static const char *rangeCheckKindToStr(RangeCheckKind); 1184c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 119ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines const SCEV *Offset; 120ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines const SCEV *Scale; 121ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Value *Length; 122ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BranchInst *Branch; 1234c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar RangeCheckKind Kind; 1244c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 1254c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar static RangeCheckKind parseRangeCheckICmp(Loop *L, ICmpInst *ICI, 1264c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar ScalarEvolution &SE, Value *&Index, 1274c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar Value *&Length); 1284c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 1294c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar static InductiveRangeCheck::RangeCheckKind 1304c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar parseRangeCheck(Loop *L, ScalarEvolution &SE, Value *Condition, 1314c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar const SCEV *&Index, Value *&UpperLimit); 132ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 133ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines InductiveRangeCheck() : 134ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Offset(nullptr), Scale(nullptr), Length(nullptr), Branch(nullptr) { } 135ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 136ebe69fe11e48d322045d5949c83283927a0d790bStephen Hinespublic: 137ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines const SCEV *getOffset() const { return Offset; } 138ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines const SCEV *getScale() const { return Scale; } 139ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Value *getLength() const { return Length; } 140ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 141ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines void print(raw_ostream &OS) const { 142ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines OS << "InductiveRangeCheck:\n"; 1434c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar OS << " Kind: " << rangeCheckKindToStr(Kind) << "\n"; 144ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines OS << " Offset: "; 145ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Offset->print(OS); 146ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines OS << " Scale: "; 147ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Scale->print(OS); 148ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines OS << " Length: "; 1494c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (Length) 1504c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar Length->print(OS); 1514c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar else 1524c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar OS << "(null)"; 1534c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar OS << "\n Branch: "; 154ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines getBranch()->print(OS); 155ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines OS << "\n"; 156ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 157ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 158ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 159ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines void dump() { 160ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines print(dbgs()); 161ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 162ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines#endif 163ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 164ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BranchInst *getBranch() const { return Branch; } 165ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 166ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines /// Represents an signed integer range [Range.getBegin(), Range.getEnd()). If 167ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines /// R.getEnd() sle R.getBegin(), then R denotes the empty range. 168ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 169ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines class Range { 170ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines const SCEV *Begin; 171ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines const SCEV *End; 172ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 173ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines public: 174ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Range(const SCEV *Begin, const SCEV *End) : Begin(Begin), End(End) { 175ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines assert(Begin->getType() == End->getType() && "ill-typed range!"); 176ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 177ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 178ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Type *getType() const { return Begin->getType(); } 179ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines const SCEV *getBegin() const { return Begin; } 180ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines const SCEV *getEnd() const { return End; } 181ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines }; 182ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 183ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines typedef SpecificBumpPtrAllocator<InductiveRangeCheck> AllocatorTy; 184ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 185ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines /// This is the value the condition of the branch needs to evaluate to for the 186ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines /// branch to take the hot successor (see (1) above). 187ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines bool getPassingDirection() { return true; } 188ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 189ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines /// Computes a range for the induction variable (IndVar) in which the range 190ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines /// check is redundant and can be constant-folded away. The induction 191ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines /// variable is not required to be the canonical {0,+,1} induction variable. 192ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Optional<Range> computeSafeIterationSpace(ScalarEvolution &SE, 193ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines const SCEVAddRecExpr *IndVar, 194ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines IRBuilder<> &B) const; 195ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 196ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines /// Create an inductive range check out of BI if possible, else return 197ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines /// nullptr. 198ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines static InductiveRangeCheck *create(AllocatorTy &Alloc, BranchInst *BI, 199ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Loop *L, ScalarEvolution &SE, 200ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BranchProbabilityInfo &BPI); 201ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines}; 202ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 203ebe69fe11e48d322045d5949c83283927a0d790bStephen Hinesclass InductiveRangeCheckElimination : public LoopPass { 204ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines InductiveRangeCheck::AllocatorTy Allocator; 205ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 206ebe69fe11e48d322045d5949c83283927a0d790bStephen Hinespublic: 207ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines static char ID; 208ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines InductiveRangeCheckElimination() : LoopPass(ID) { 209ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines initializeInductiveRangeCheckEliminationPass( 210ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines *PassRegistry::getPassRegistry()); 211ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 212ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 213ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines void getAnalysisUsage(AnalysisUsage &AU) const override { 214ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines AU.addRequired<LoopInfoWrapperPass>(); 215ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines AU.addRequiredID(LoopSimplifyID); 216ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines AU.addRequiredID(LCSSAID); 217ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines AU.addRequired<ScalarEvolution>(); 218ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines AU.addRequired<BranchProbabilityInfo>(); 219ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 220ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 221ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines bool runOnLoop(Loop *L, LPPassManager &LPM) override; 222ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines}; 223ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 224ebe69fe11e48d322045d5949c83283927a0d790bStephen Hineschar InductiveRangeCheckElimination::ID = 0; 225ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines} 226ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 227ebe69fe11e48d322045d5949c83283927a0d790bStephen HinesINITIALIZE_PASS(InductiveRangeCheckElimination, "irce", 228ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines "Inductive range check elimination", false, false) 229ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 2304c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainarconst char *InductiveRangeCheck::rangeCheckKindToStr( 2314c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar InductiveRangeCheck::RangeCheckKind RCK) { 2324c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar switch (RCK) { 2334c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar case InductiveRangeCheck::RANGE_CHECK_UNKNOWN: 2344c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return "RANGE_CHECK_UNKNOWN"; 235ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 2364c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar case InductiveRangeCheck::RANGE_CHECK_UPPER: 2374c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return "RANGE_CHECK_UPPER"; 238ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 2394c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar case InductiveRangeCheck::RANGE_CHECK_LOWER: 2404c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return "RANGE_CHECK_LOWER"; 2414c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 2424c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar case InductiveRangeCheck::RANGE_CHECK_BOTH: 2434c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return "RANGE_CHECK_BOTH"; 2444c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 2454c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 2464c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar llvm_unreachable("unknown range check type!"); 2474c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar} 2484c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 2494c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar/// Parse a single ICmp instruction, `ICI`, into a range check. If `ICI` 2504c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar/// cannot 2514c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar/// be interpreted as a range check, return `RANGE_CHECK_UNKNOWN` and set 2524c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar/// `Index` and `Length` to `nullptr`. Otherwise set `Index` to the value 2534c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar/// being 2544c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar/// range checked, and set `Length` to the upper limit `Index` is being range 2554c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar/// checked with if (and only if) the range check type is stronger or equal to 2564c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar/// RANGE_CHECK_UPPER. 2574c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar/// 2584c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga NainarInductiveRangeCheck::RangeCheckKind 2594c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga NainarInductiveRangeCheck::parseRangeCheckICmp(Loop *L, ICmpInst *ICI, 2604c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar ScalarEvolution &SE, Value *&Index, 2614c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar Value *&Length) { 2624c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 2634c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar auto IsNonNegativeAndNotLoopVarying = [&SE, L](Value *V) { 2644c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar const SCEV *S = SE.getSCEV(V); 2654c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (isa<SCEVCouldNotCompute>(S)) 2664c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return false; 2674c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 2684c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return SE.getLoopDisposition(S, L) == ScalarEvolution::LoopInvariant && 2694c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar SE.isKnownNonNegative(S); 2704c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar }; 2714c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 2724c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar using namespace llvm::PatternMatch; 2734c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 2744c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar ICmpInst::Predicate Pred = ICI->getPredicate(); 2754c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar Value *LHS = ICI->getOperand(0); 2764c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar Value *RHS = ICI->getOperand(1); 277ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 278ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines switch (Pred) { 279ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines default: 2804c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return RANGE_CHECK_UNKNOWN; 281ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 282ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines case ICmpInst::ICMP_SLE: 283ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines std::swap(LHS, RHS); 284ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // fallthrough 285ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines case ICmpInst::ICMP_SGE: 2864c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (match(RHS, m_ConstantInt<0>())) { 2874c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar Index = LHS; 2884c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return RANGE_CHECK_LOWER; 2894c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 2904c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return RANGE_CHECK_UNKNOWN; 291ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 292ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines case ICmpInst::ICMP_SLT: 293ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines std::swap(LHS, RHS); 294ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // fallthrough 295ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines case ICmpInst::ICMP_SGT: 2964c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (match(RHS, m_ConstantInt<-1>())) { 2974c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar Index = LHS; 2984c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return RANGE_CHECK_LOWER; 2994c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 300ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 3014c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (IsNonNegativeAndNotLoopVarying(LHS)) { 3024c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar Index = RHS; 3034c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar Length = LHS; 3044c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return RANGE_CHECK_UPPER; 3054c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 3064c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return RANGE_CHECK_UNKNOWN; 307ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 3084c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar case ICmpInst::ICMP_ULT: 309ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines std::swap(LHS, RHS); 310ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // fallthrough 311ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines case ICmpInst::ICMP_UGT: 3124c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (IsNonNegativeAndNotLoopVarying(LHS)) { 3134c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar Index = RHS; 3144c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar Length = LHS; 3154c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return RANGE_CHECK_BOTH; 3164c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 3174c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return RANGE_CHECK_UNKNOWN; 318ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 3194c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 3204c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar llvm_unreachable("default clause returns!"); 321ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines} 322ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 3234c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar/// Parses an arbitrary condition into a range check. `Length` is set only if 3244c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar/// the range check is recognized to be `RANGE_CHECK_UPPER` or stronger. 3254c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga NainarInductiveRangeCheck::RangeCheckKind 3264c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga NainarInductiveRangeCheck::parseRangeCheck(Loop *L, ScalarEvolution &SE, 327ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Value *Condition, const SCEV *&Index, 3284c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar Value *&Length) { 329ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines using namespace llvm::PatternMatch; 330ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 331ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Value *A = nullptr; 332ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Value *B = nullptr; 333ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 334ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (match(Condition, m_And(m_Value(A), m_Value(B)))) { 3354c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar Value *IndexA = nullptr, *IndexB = nullptr; 3364c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar Value *LengthA = nullptr, *LengthB = nullptr; 3374c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar ICmpInst *ICmpA = dyn_cast<ICmpInst>(A), *ICmpB = dyn_cast<ICmpInst>(B); 338ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 3394c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (!ICmpA || !ICmpB) 3404c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return InductiveRangeCheck::RANGE_CHECK_UNKNOWN; 341ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 3424c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar auto RCKindA = parseRangeCheckICmp(L, ICmpA, SE, IndexA, LengthA); 3434c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar auto RCKindB = parseRangeCheckICmp(L, ICmpB, SE, IndexB, LengthB); 344ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 3454c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (RCKindA == InductiveRangeCheck::RANGE_CHECK_UNKNOWN || 3464c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar RCKindB == InductiveRangeCheck::RANGE_CHECK_UNKNOWN) 3474c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return InductiveRangeCheck::RANGE_CHECK_UNKNOWN; 348ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 3494c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (IndexA != IndexB) 3504c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return InductiveRangeCheck::RANGE_CHECK_UNKNOWN; 351ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 3524c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (LengthA != nullptr && LengthB != nullptr && LengthA != LengthB) 3534c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return InductiveRangeCheck::RANGE_CHECK_UNKNOWN; 354ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 3554c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar Index = SE.getSCEV(IndexA); 3564c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (isa<SCEVCouldNotCompute>(Index)) 3574c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return InductiveRangeCheck::RANGE_CHECK_UNKNOWN; 358ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 3594c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar Length = LengthA == nullptr ? LengthB : LengthA; 3604c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 3614c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return (InductiveRangeCheck::RangeCheckKind)(RCKindA | RCKindB); 362ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 363ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 3644c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (ICmpInst *ICI = dyn_cast<ICmpInst>(Condition)) { 3654c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar Value *IndexVal = nullptr; 366ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 3674c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar auto RCKind = parseRangeCheckICmp(L, ICI, SE, IndexVal, Length); 3684c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 3694c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (RCKind == InductiveRangeCheck::RANGE_CHECK_UNKNOWN) 3704c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return InductiveRangeCheck::RANGE_CHECK_UNKNOWN; 3714c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 3724c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar Index = SE.getSCEV(IndexVal); 3734c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (isa<SCEVCouldNotCompute>(Index)) 3744c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return InductiveRangeCheck::RANGE_CHECK_UNKNOWN; 3754c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 3764c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return RCKind; 377ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 378ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 3794c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return InductiveRangeCheck::RANGE_CHECK_UNKNOWN; 380ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines} 381ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 382ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 383ebe69fe11e48d322045d5949c83283927a0d790bStephen HinesInductiveRangeCheck * 384ebe69fe11e48d322045d5949c83283927a0d790bStephen HinesInductiveRangeCheck::create(InductiveRangeCheck::AllocatorTy &A, BranchInst *BI, 385ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Loop *L, ScalarEvolution &SE, 386ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BranchProbabilityInfo &BPI) { 387ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 388ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (BI->isUnconditional() || BI->getParent() == L->getLoopLatch()) 389ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return nullptr; 390ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 391ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BranchProbability LikelyTaken(15, 16); 392ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 393ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (BPI.getEdgeProbability(BI->getParent(), (unsigned) 0) < LikelyTaken) 394ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return nullptr; 395ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 396ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Value *Length = nullptr; 397ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines const SCEV *IndexSCEV = nullptr; 398ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 3994c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar auto RCKind = InductiveRangeCheck::parseRangeCheck(L, SE, BI->getCondition(), 4004c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar IndexSCEV, Length); 4014c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 4024c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (RCKind == InductiveRangeCheck::RANGE_CHECK_UNKNOWN) 403ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return nullptr; 404ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 4054c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar assert(IndexSCEV && "contract with SplitRangeCheckCondition!"); 4064c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar assert((!(RCKind & InductiveRangeCheck::RANGE_CHECK_UPPER) || Length) && 4074c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar "contract with SplitRangeCheckCondition!"); 408ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 409ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines const SCEVAddRecExpr *IndexAddRec = dyn_cast<SCEVAddRecExpr>(IndexSCEV); 410ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines bool IsAffineIndex = 411ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines IndexAddRec && (IndexAddRec->getLoop() == L) && IndexAddRec->isAffine(); 412ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 413ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (!IsAffineIndex) 414ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return nullptr; 415ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 416ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines InductiveRangeCheck *IRC = new (A.Allocate()) InductiveRangeCheck; 417ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines IRC->Length = Length; 418ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines IRC->Offset = IndexAddRec->getStart(); 419ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines IRC->Scale = IndexAddRec->getStepRecurrence(SE); 420ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines IRC->Branch = BI; 4214c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar IRC->Kind = RCKind; 422ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return IRC; 423ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines} 424ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 425ebe69fe11e48d322045d5949c83283927a0d790bStephen Hinesnamespace { 426ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 427ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines// Keeps track of the structure of a loop. This is similar to llvm::Loop, 428ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines// except that it is more lightweight and can track the state of a loop through 429ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines// changing and potentially invalid IR. This structure also formalizes the 430ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines// kinds of loops we can deal with -- ones that have a single latch that is also 431ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines// an exiting block *and* have a canonical induction variable. 432ebe69fe11e48d322045d5949c83283927a0d790bStephen Hinesstruct LoopStructure { 433ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines const char *Tag; 434ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 435ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BasicBlock *Header; 436ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BasicBlock *Latch; 437ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 438ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // `Latch's terminator instruction is `LatchBr', and it's `LatchBrExitIdx'th 439ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // successor is `LatchExit', the exit block of the loop. 440ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BranchInst *LatchBr; 441ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BasicBlock *LatchExit; 442ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines unsigned LatchBrExitIdx; 443ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 444ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Value *IndVarNext; 445ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Value *IndVarStart; 446ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Value *LoopExitAt; 447ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines bool IndVarIncreasing; 448ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 449ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines LoopStructure() 450ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines : Tag(""), Header(nullptr), Latch(nullptr), LatchBr(nullptr), 451ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines LatchExit(nullptr), LatchBrExitIdx(-1), IndVarNext(nullptr), 452ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines IndVarStart(nullptr), LoopExitAt(nullptr), IndVarIncreasing(false) {} 453ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 454ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines template <typename M> LoopStructure map(M Map) const { 455ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines LoopStructure Result; 456ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Result.Tag = Tag; 457ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Result.Header = cast<BasicBlock>(Map(Header)); 458ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Result.Latch = cast<BasicBlock>(Map(Latch)); 459ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Result.LatchBr = cast<BranchInst>(Map(LatchBr)); 460ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Result.LatchExit = cast<BasicBlock>(Map(LatchExit)); 461ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Result.LatchBrExitIdx = LatchBrExitIdx; 462ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Result.IndVarNext = Map(IndVarNext); 463ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Result.IndVarStart = Map(IndVarStart); 464ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Result.LoopExitAt = Map(LoopExitAt); 465ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Result.IndVarIncreasing = IndVarIncreasing; 466ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return Result; 467ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 468ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 469ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines static Optional<LoopStructure> parseLoopStructure(ScalarEvolution &, 470ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BranchProbabilityInfo &BPI, 471ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Loop &, 472ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines const char *&); 473ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines}; 474ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 475ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// This class is used to constrain loops to run within a given iteration space. 476ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// The algorithm this class implements is given a Loop and a range [Begin, 477ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// End). The algorithm then tries to break out a "main loop" out of the loop 478ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// it is given in a way that the "main loop" runs with the induction variable 479ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// in a subset of [Begin, End). The algorithm emits appropriate pre and post 480ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// loops to run any remaining iterations. The pre loop runs any iterations in 481ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// which the induction variable is < Begin, and the post loop runs any 482ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// iterations in which the induction variable is >= End. 483ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// 484ebe69fe11e48d322045d5949c83283927a0d790bStephen Hinesclass LoopConstrainer { 485ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // The representation of a clone of the original loop we started out with. 486ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines struct ClonedLoop { 487ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // The cloned blocks 488ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines std::vector<BasicBlock *> Blocks; 489ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 490ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // `Map` maps values in the clonee into values in the cloned version 491ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines ValueToValueMapTy Map; 492ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 493ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // An instance of `LoopStructure` for the cloned loop 494ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines LoopStructure Structure; 495ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines }; 496ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 497ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // Result of rewriting the range of a loop. See changeIterationSpaceEnd for 498ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // more details on what these fields mean. 499ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines struct RewrittenRangeInfo { 500ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BasicBlock *PseudoExit; 501ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BasicBlock *ExitSelector; 502ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines std::vector<PHINode *> PHIValuesAtPseudoExit; 503ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines PHINode *IndVarEnd; 504ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 505ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines RewrittenRangeInfo() 506ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines : PseudoExit(nullptr), ExitSelector(nullptr), IndVarEnd(nullptr) {} 507ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines }; 508ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 509ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // Calculated subranges we restrict the iteration space of the main loop to. 510ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // See the implementation of `calculateSubRanges' for more details on how 511ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // these fields are computed. `LowLimit` is None if there is no restriction 512ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // on low end of the restricted iteration space of the main loop. `HighLimit` 513ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // is None if there is no restriction on high end of the restricted iteration 514ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // space of the main loop. 515ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 516ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines struct SubRanges { 517ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Optional<const SCEV *> LowLimit; 518ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Optional<const SCEV *> HighLimit; 519ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines }; 520ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 521ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // A utility function that does a `replaceUsesOfWith' on the incoming block 522ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // set of a `PHINode' -- replaces instances of `Block' in the `PHINode's 523ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // incoming block list with `ReplaceBy'. 524ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines static void replacePHIBlock(PHINode *PN, BasicBlock *Block, 525ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BasicBlock *ReplaceBy); 526ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 527ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // Compute a safe set of limits for the main loop to run in -- effectively the 528ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // intersection of `Range' and the iteration space of the original loop. 529ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // Return None if unable to compute the set of subranges. 530ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // 531ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Optional<SubRanges> calculateSubRanges() const; 532ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 533ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // Clone `OriginalLoop' and return the result in CLResult. The IR after 534ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // running `cloneLoop' is well formed except for the PHI nodes in CLResult -- 535ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // the PHI nodes say that there is an incoming edge from `OriginalPreheader` 536ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // but there is no such edge. 537ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // 538ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines void cloneLoop(ClonedLoop &CLResult, const char *Tag) const; 539ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 540ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // Rewrite the iteration space of the loop denoted by (LS, Preheader). The 541ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // iteration space of the rewritten loop ends at ExitLoopAt. The start of the 542ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // iteration space is not changed. `ExitLoopAt' is assumed to be slt 543ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // `OriginalHeaderCount'. 544ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // 545ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // If there are iterations left to execute, control is made to jump to 546ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // `ContinuationBlock', otherwise they take the normal loop exit. The 547ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // returned `RewrittenRangeInfo' object is populated as follows: 548ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // 549ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // .PseudoExit is a basic block that unconditionally branches to 550ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // `ContinuationBlock'. 551ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // 552ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // .ExitSelector is a basic block that decides, on exit from the loop, 553ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // whether to branch to the "true" exit or to `PseudoExit'. 554ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // 555ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // .PHIValuesAtPseudoExit are PHINodes in `PseudoExit' that compute the value 556ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // for each PHINode in the loop header on taking the pseudo exit. 557ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // 558ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // After changeIterationSpaceEnd, `Preheader' is no longer a legitimate 559ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // preheader because it is made to branch to the loop header only 560ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // conditionally. 561ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // 562ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines RewrittenRangeInfo 563ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines changeIterationSpaceEnd(const LoopStructure &LS, BasicBlock *Preheader, 564ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Value *ExitLoopAt, 565ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BasicBlock *ContinuationBlock) const; 566ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 567ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // The loop denoted by `LS' has `OldPreheader' as its preheader. This 568ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // function creates a new preheader for `LS' and returns it. 569ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // 570ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BasicBlock *createPreheader(const LoopStructure &LS, BasicBlock *OldPreheader, 571ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines const char *Tag) const; 572ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 573ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // `ContinuationBlockAndPreheader' was the continuation block for some call to 574ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // `changeIterationSpaceEnd' and is the preheader to the loop denoted by `LS'. 575ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // This function rewrites the PHI nodes in `LS.Header' to start with the 576ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // correct value. 577ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines void rewriteIncomingValuesForPHIs( 578ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines LoopStructure &LS, BasicBlock *ContinuationBlockAndPreheader, 579ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines const LoopConstrainer::RewrittenRangeInfo &RRI) const; 580ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 581ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // Even though we do not preserve any passes at this time, we at least need to 582ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // keep the parent loop structure consistent. The `LPPassManager' seems to 583ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // verify this after running a loop pass. This function adds the list of 584ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // blocks denoted by BBs to this loops parent loop if required. 585ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines void addToParentLoopIfNeeded(ArrayRef<BasicBlock *> BBs); 586ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 587ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // Some global state. 588ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Function &F; 589ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines LLVMContext &Ctx; 590ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines ScalarEvolution &SE; 591ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 592ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // Information about the original loop we started out with. 593ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Loop &OriginalLoop; 594ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines LoopInfo &OriginalLoopInfo; 595ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines const SCEV *LatchTakenCount; 596ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BasicBlock *OriginalPreheader; 597ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 598ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // The preheader of the main loop. This may or may not be different from 599ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // `OriginalPreheader'. 600ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BasicBlock *MainLoopPreheader; 601ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 602ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // The range we need to run the main loop in. 603ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines InductiveRangeCheck::Range Range; 604ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 605ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // The structure of the main loop (see comment at the beginning of this class 606ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // for a definition) 607ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines LoopStructure MainLoopStructure; 608ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 609ebe69fe11e48d322045d5949c83283927a0d790bStephen Hinespublic: 610ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines LoopConstrainer(Loop &L, LoopInfo &LI, const LoopStructure &LS, 611ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines ScalarEvolution &SE, InductiveRangeCheck::Range R) 612ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines : F(*L.getHeader()->getParent()), Ctx(L.getHeader()->getContext()), 613ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines SE(SE), OriginalLoop(L), OriginalLoopInfo(LI), LatchTakenCount(nullptr), 614ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines OriginalPreheader(nullptr), MainLoopPreheader(nullptr), Range(R), 615ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines MainLoopStructure(LS) {} 616ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 617ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // Entry point for the algorithm. Returns true on success. 618ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines bool run(); 619ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines}; 620ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 621ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines} 622ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 623ebe69fe11e48d322045d5949c83283927a0d790bStephen Hinesvoid LoopConstrainer::replacePHIBlock(PHINode *PN, BasicBlock *Block, 624ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BasicBlock *ReplaceBy) { 625ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 626ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (PN->getIncomingBlock(i) == Block) 627ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines PN->setIncomingBlock(i, ReplaceBy); 628ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines} 629ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 630ebe69fe11e48d322045d5949c83283927a0d790bStephen Hinesstatic bool CanBeSMax(ScalarEvolution &SE, const SCEV *S) { 631ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines APInt SMax = 632ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines APInt::getSignedMaxValue(cast<IntegerType>(S->getType())->getBitWidth()); 633ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return SE.getSignedRange(S).contains(SMax) && 634ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines SE.getUnsignedRange(S).contains(SMax); 635ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines} 636ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 637ebe69fe11e48d322045d5949c83283927a0d790bStephen Hinesstatic bool CanBeSMin(ScalarEvolution &SE, const SCEV *S) { 638ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines APInt SMin = 639ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines APInt::getSignedMinValue(cast<IntegerType>(S->getType())->getBitWidth()); 640ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return SE.getSignedRange(S).contains(SMin) && 641ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines SE.getUnsignedRange(S).contains(SMin); 642ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines} 643ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 644ebe69fe11e48d322045d5949c83283927a0d790bStephen HinesOptional<LoopStructure> 645ebe69fe11e48d322045d5949c83283927a0d790bStephen HinesLoopStructure::parseLoopStructure(ScalarEvolution &SE, BranchProbabilityInfo &BPI, 646ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Loop &L, const char *&FailureReason) { 647ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines assert(L.isLoopSimplifyForm() && "should follow from addRequired<>"); 648ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 649ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BasicBlock *Latch = L.getLoopLatch(); 650ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (!L.isLoopExiting(Latch)) { 651ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines FailureReason = "no loop latch"; 652ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return None; 653ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 654ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 655ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BasicBlock *Header = L.getHeader(); 656ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BasicBlock *Preheader = L.getLoopPreheader(); 657ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (!Preheader) { 658ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines FailureReason = "no preheader"; 659ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return None; 660ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 661ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 662ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BranchInst *LatchBr = dyn_cast<BranchInst>(&*Latch->rbegin()); 663ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (!LatchBr || LatchBr->isUnconditional()) { 664ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines FailureReason = "latch terminator not conditional branch"; 665ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return None; 666ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 667ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 668ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines unsigned LatchBrExitIdx = LatchBr->getSuccessor(0) == Header ? 1 : 0; 669ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 670ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BranchProbability ExitProbability = 671ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BPI.getEdgeProbability(LatchBr->getParent(), LatchBrExitIdx); 672ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 673ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (ExitProbability > BranchProbability(1, MaxExitProbReciprocal)) { 674ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines FailureReason = "short running loop, not profitable"; 675ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return None; 676ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 677ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 678ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines ICmpInst *ICI = dyn_cast<ICmpInst>(LatchBr->getCondition()); 679ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (!ICI || !isa<IntegerType>(ICI->getOperand(0)->getType())) { 680ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines FailureReason = "latch terminator branch not conditional on integral icmp"; 681ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return None; 682ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 683ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 684ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines const SCEV *LatchCount = SE.getExitCount(&L, Latch); 685ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (isa<SCEVCouldNotCompute>(LatchCount)) { 686ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines FailureReason = "could not compute latch count"; 687ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return None; 688ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 689ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 690ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines ICmpInst::Predicate Pred = ICI->getPredicate(); 691ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Value *LeftValue = ICI->getOperand(0); 692ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines const SCEV *LeftSCEV = SE.getSCEV(LeftValue); 693ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines IntegerType *IndVarTy = cast<IntegerType>(LeftValue->getType()); 694ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 695ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Value *RightValue = ICI->getOperand(1); 696ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines const SCEV *RightSCEV = SE.getSCEV(RightValue); 697ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 698ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // We canonicalize `ICI` such that `LeftSCEV` is an add recurrence. 699ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (!isa<SCEVAddRecExpr>(LeftSCEV)) { 700ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (isa<SCEVAddRecExpr>(RightSCEV)) { 701ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines std::swap(LeftSCEV, RightSCEV); 702ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines std::swap(LeftValue, RightValue); 703ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Pred = ICmpInst::getSwappedPredicate(Pred); 704ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } else { 705ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines FailureReason = "no add recurrences in the icmp"; 706ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return None; 707ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 708ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 709ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 7104c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar auto HasNoSignedWrap = [&](const SCEVAddRecExpr *AR) { 7114c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (AR->getNoWrapFlags(SCEV::FlagNSW)) 7124c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return true; 713ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 714ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines IntegerType *Ty = cast<IntegerType>(AR->getType()); 715ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines IntegerType *WideTy = 716ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines IntegerType::get(Ty->getContext(), Ty->getBitWidth() * 2); 717ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 718ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines const SCEVAddRecExpr *ExtendAfterOp = 719ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines dyn_cast<SCEVAddRecExpr>(SE.getSignExtendExpr(AR, WideTy)); 7204c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (ExtendAfterOp) { 7214c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar const SCEV *ExtendedStart = SE.getSignExtendExpr(AR->getStart(), WideTy); 7224c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar const SCEV *ExtendedStep = 7234c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar SE.getSignExtendExpr(AR->getStepRecurrence(SE), WideTy); 724ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 7254c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar bool NoSignedWrap = ExtendAfterOp->getStart() == ExtendedStart && 7264c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar ExtendAfterOp->getStepRecurrence(SE) == ExtendedStep; 7274c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 7284c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (NoSignedWrap) 7294c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return true; 7304c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 7314c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 7324c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // We may have proved this when computing the sign extension above. 7334c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return AR->getNoWrapFlags(SCEV::FlagNSW) != SCEV::FlagAnyWrap; 7344c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar }; 7354c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 7364c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar auto IsInductionVar = [&](const SCEVAddRecExpr *AR, bool &IsIncreasing) { 7374c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (!AR->isAffine()) 7384c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return false; 739ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 7404c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // Currently we only work with induction variables that have been proved to 7414c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // not wrap. This restriction can potentially be lifted in the future. 742ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 7434c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (!HasNoSignedWrap(AR)) 744ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return false; 745ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 746ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (const SCEVConstant *StepExpr = 747ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines dyn_cast<SCEVConstant>(AR->getStepRecurrence(SE))) { 748ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines ConstantInt *StepCI = StepExpr->getValue(); 749ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (StepCI->isOne() || StepCI->isMinusOne()) { 750ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines IsIncreasing = StepCI->isOne(); 751ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return true; 752ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 753ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 754ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 755ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return false; 756ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines }; 757ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 758ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // `ICI` is interpreted as taking the backedge if the *next* value of the 759ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // induction variable satisfies some constraint. 760ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 761ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines const SCEVAddRecExpr *IndVarNext = cast<SCEVAddRecExpr>(LeftSCEV); 762ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines bool IsIncreasing = false; 763ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (!IsInductionVar(IndVarNext, IsIncreasing)) { 764ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines FailureReason = "LHS in icmp not induction variable"; 765ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return None; 766ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 767ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 768ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines ConstantInt *One = ConstantInt::get(IndVarTy, 1); 769ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // TODO: generalize the predicates here to also match their unsigned variants. 770ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (IsIncreasing) { 771ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines bool FoundExpectedPred = 772ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines (Pred == ICmpInst::ICMP_SLT && LatchBrExitIdx == 1) || 773ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines (Pred == ICmpInst::ICMP_SGT && LatchBrExitIdx == 0); 774ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 775ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (!FoundExpectedPred) { 776ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines FailureReason = "expected icmp slt semantically, found something else"; 777ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return None; 778ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 779ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 780ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (LatchBrExitIdx == 0) { 781ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (CanBeSMax(SE, RightSCEV)) { 782ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // TODO: this restriction is easily removable -- we just have to 783ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // remember that the icmp was an slt and not an sle. 784ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines FailureReason = "limit may overflow when coercing sle to slt"; 785ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return None; 786ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 787ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 788ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines IRBuilder<> B(&*Preheader->rbegin()); 789ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines RightValue = B.CreateAdd(RightValue, One); 790ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 791ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 792ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } else { 793ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines bool FoundExpectedPred = 794ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines (Pred == ICmpInst::ICMP_SGT && LatchBrExitIdx == 1) || 795ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines (Pred == ICmpInst::ICMP_SLT && LatchBrExitIdx == 0); 796ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 797ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (!FoundExpectedPred) { 798ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines FailureReason = "expected icmp sgt semantically, found something else"; 799ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return None; 800ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 801ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 802ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (LatchBrExitIdx == 0) { 803ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (CanBeSMin(SE, RightSCEV)) { 804ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // TODO: this restriction is easily removable -- we just have to 805ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // remember that the icmp was an sgt and not an sge. 806ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines FailureReason = "limit may overflow when coercing sge to sgt"; 807ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return None; 808ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 809ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 810ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines IRBuilder<> B(&*Preheader->rbegin()); 811ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines RightValue = B.CreateSub(RightValue, One); 812ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 813ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 814ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 815ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines const SCEV *StartNext = IndVarNext->getStart(); 816ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines const SCEV *Addend = SE.getNegativeSCEV(IndVarNext->getStepRecurrence(SE)); 817ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines const SCEV *IndVarStart = SE.getAddExpr(StartNext, Addend); 818ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 819ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BasicBlock *LatchExit = LatchBr->getSuccessor(LatchBrExitIdx); 820ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 821ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines assert(SE.getLoopDisposition(LatchCount, &L) == 822ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines ScalarEvolution::LoopInvariant && 823ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines "loop variant exit count doesn't make sense!"); 824ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 825ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines assert(!L.contains(LatchExit) && "expected an exit block!"); 8264c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar const DataLayout &DL = Preheader->getModule()->getDataLayout(); 8274c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar Value *IndVarStartV = 8284c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar SCEVExpander(SE, DL, "irce") 8294c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar .expandCodeFor(IndVarStart, IndVarTy, &*Preheader->rbegin()); 830ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines IndVarStartV->setName("indvar.start"); 831ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 832ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines LoopStructure Result; 833ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 834ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Result.Tag = "main"; 835ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Result.Header = Header; 836ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Result.Latch = Latch; 837ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Result.LatchBr = LatchBr; 838ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Result.LatchExit = LatchExit; 839ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Result.LatchBrExitIdx = LatchBrExitIdx; 840ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Result.IndVarStart = IndVarStartV; 841ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Result.IndVarNext = LeftValue; 842ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Result.IndVarIncreasing = IsIncreasing; 843ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Result.LoopExitAt = RightValue; 844ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 845ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines FailureReason = nullptr; 846ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 847ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return Result; 848ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines} 849ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 850ebe69fe11e48d322045d5949c83283927a0d790bStephen HinesOptional<LoopConstrainer::SubRanges> 851ebe69fe11e48d322045d5949c83283927a0d790bStephen HinesLoopConstrainer::calculateSubRanges() const { 852ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines IntegerType *Ty = cast<IntegerType>(LatchTakenCount->getType()); 853ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 854ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (Range.getType() != Ty) 855ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return None; 856ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 857ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines LoopConstrainer::SubRanges Result; 858ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 859ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // I think we can be more aggressive here and make this nuw / nsw if the 860ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // addition that feeds into the icmp for the latch's terminating branch is nuw 861ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // / nsw. In any case, a wrapping 2's complement addition is safe. 862ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines ConstantInt *One = ConstantInt::get(Ty, 1); 863ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines const SCEV *Start = SE.getSCEV(MainLoopStructure.IndVarStart); 864ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines const SCEV *End = SE.getSCEV(MainLoopStructure.LoopExitAt); 865ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 866ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines bool Increasing = MainLoopStructure.IndVarIncreasing; 8674c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 868ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // We compute `Smallest` and `Greatest` such that [Smallest, Greatest) is the 869ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // range of values the induction variable takes. 8704c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 8714c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar const SCEV *Smallest = nullptr, *Greatest = nullptr; 8724c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 8734c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (Increasing) { 8744c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar Smallest = Start; 8754c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar Greatest = End; 8764c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } else { 8774c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // These two computations may sign-overflow. Here is why that is okay: 8784c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // 8794c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // We know that the induction variable does not sign-overflow on any 8804c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // iteration except the last one, and it starts at `Start` and ends at 8814c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // `End`, decrementing by one every time. 8824c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // 8834c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // * if `Smallest` sign-overflows we know `End` is `INT_SMAX`. Since the 8844c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // induction variable is decreasing we know that that the smallest value 8854c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // the loop body is actually executed with is `INT_SMIN` == `Smallest`. 8864c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // 8874c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // * if `Greatest` sign-overflows, we know it can only be `INT_SMIN`. In 8884c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // that case, `Clamp` will always return `Smallest` and 8894c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // [`Result.LowLimit`, `Result.HighLimit`) = [`Smallest`, `Smallest`) 8904c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // will be an empty range. Returning an empty range is always safe. 8914c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // 8924c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 8934c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar Smallest = SE.getAddExpr(End, SE.getSCEV(One)); 8944c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar Greatest = SE.getAddExpr(Start, SE.getSCEV(One)); 8954c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 896ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 897ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines auto Clamp = [this, Smallest, Greatest](const SCEV *S) { 898ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return SE.getSMaxExpr(Smallest, SE.getSMinExpr(Greatest, S)); 899ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines }; 900ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 901ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // In some cases we can prove that we don't need a pre or post loop 902ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 903ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines bool ProvablyNoPreloop = 904ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines SE.isKnownPredicate(ICmpInst::ICMP_SLE, Range.getBegin(), Smallest); 905ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (!ProvablyNoPreloop) 906ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Result.LowLimit = Clamp(Range.getBegin()); 907ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 908ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines bool ProvablyNoPostLoop = 909ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines SE.isKnownPredicate(ICmpInst::ICMP_SLE, Greatest, Range.getEnd()); 910ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (!ProvablyNoPostLoop) 911ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Result.HighLimit = Clamp(Range.getEnd()); 912ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 913ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return Result; 914ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines} 915ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 916ebe69fe11e48d322045d5949c83283927a0d790bStephen Hinesvoid LoopConstrainer::cloneLoop(LoopConstrainer::ClonedLoop &Result, 917ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines const char *Tag) const { 918ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines for (BasicBlock *BB : OriginalLoop.getBlocks()) { 919ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BasicBlock *Clone = CloneBasicBlock(BB, Result.Map, Twine(".") + Tag, &F); 920ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Result.Blocks.push_back(Clone); 921ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Result.Map[BB] = Clone; 922ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 923ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 924ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines auto GetClonedValue = [&Result](Value *V) { 925ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines assert(V && "null values not in domain!"); 926ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines auto It = Result.Map.find(V); 927ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (It == Result.Map.end()) 928ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return V; 929ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return static_cast<Value *>(It->second); 930ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines }; 931ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 932ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Result.Structure = MainLoopStructure.map(GetClonedValue); 933ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Result.Structure.Tag = Tag; 934ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 935ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines for (unsigned i = 0, e = Result.Blocks.size(); i != e; ++i) { 936ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BasicBlock *ClonedBB = Result.Blocks[i]; 937ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BasicBlock *OriginalBB = OriginalLoop.getBlocks()[i]; 938ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 939ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines assert(Result.Map[OriginalBB] == ClonedBB && "invariant!"); 940ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 941ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines for (Instruction &I : *ClonedBB) 942ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines RemapInstruction(&I, Result.Map, 943ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines RF_NoModuleLevelChanges | RF_IgnoreMissingEntries); 944ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 945ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // Exit blocks will now have one more predecessor and their PHI nodes need 946ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // to be edited to reflect that. No phi nodes need to be introduced because 947ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // the loop is in LCSSA. 948ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 949ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines for (auto SBBI = succ_begin(OriginalBB), SBBE = succ_end(OriginalBB); 950ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines SBBI != SBBE; ++SBBI) { 951ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 952ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (OriginalLoop.contains(*SBBI)) 953ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines continue; // not an exit block 954ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 955ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines for (Instruction &I : **SBBI) { 956ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (!isa<PHINode>(&I)) 957ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines break; 958ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 959ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines PHINode *PN = cast<PHINode>(&I); 960ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Value *OldIncoming = PN->getIncomingValueForBlock(OriginalBB); 961ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines PN->addIncoming(GetClonedValue(OldIncoming), ClonedBB); 962ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 963ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 964ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 965ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines} 966ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 967ebe69fe11e48d322045d5949c83283927a0d790bStephen HinesLoopConstrainer::RewrittenRangeInfo LoopConstrainer::changeIterationSpaceEnd( 968ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines const LoopStructure &LS, BasicBlock *Preheader, Value *ExitSubloopAt, 969ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BasicBlock *ContinuationBlock) const { 970ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 971ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // We start with a loop with a single latch: 972ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // 973ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // +--------------------+ 974ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // | | 975ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // | preheader | 976ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // | | 977ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // +--------+-----------+ 978ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // | ----------------\ 979ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // | / | 980ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // +--------v----v------+ | 981ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // | | | 982ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // | header | | 983ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // | | | 984ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // +--------------------+ | 985ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // | 986ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // ..... | 987ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // | 988ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // +--------------------+ | 989ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // | | | 990ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // | latch >----------/ 991ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // | | 992ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // +-------v------------+ 993ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // | 994ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // | 995ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // | +--------------------+ 996ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // | | | 997ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // +---> original exit | 998ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // | | 999ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // +--------------------+ 1000ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // 1001ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // We change the control flow to look like 1002ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // 1003ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // 1004ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // +--------------------+ 1005ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // | | 1006ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // | preheader >-------------------------+ 1007ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // | | | 1008ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // +--------v-----------+ | 1009ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // | /-------------+ | 1010ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // | / | | 1011ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // +--------v--v--------+ | | 1012ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // | | | | 1013ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // | header | | +--------+ | 1014ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // | | | | | | 1015ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // +--------------------+ | | +-----v-----v-----------+ 1016ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // | | | | 1017ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // | | | .pseudo.exit | 1018ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // | | | | 1019ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // | | +-----------v-----------+ 1020ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // | | | 1021ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // ..... | | | 1022ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // | | +--------v-------------+ 1023ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // +--------------------+ | | | | 1024ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // | | | | | ContinuationBlock | 1025ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // | latch >------+ | | | 1026ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // | | | +----------------------+ 1027ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // +---------v----------+ | 1028ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // | | 1029ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // | | 1030ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // | +---------------^-----+ 1031ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // | | | 1032ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // +-----> .exit.selector | 1033ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // | | 1034ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // +----------v----------+ 1035ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // | 1036ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // +--------------------+ | 1037ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // | | | 1038ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // | original exit <----+ 1039ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // | | 1040ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // +--------------------+ 1041ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // 1042ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1043ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines RewrittenRangeInfo RRI; 1044ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1045ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines auto BBInsertLocation = std::next(Function::iterator(LS.Latch)); 1046ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines RRI.ExitSelector = BasicBlock::Create(Ctx, Twine(LS.Tag) + ".exit.selector", 1047ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines &F, BBInsertLocation); 1048ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines RRI.PseudoExit = BasicBlock::Create(Ctx, Twine(LS.Tag) + ".pseudo.exit", &F, 1049ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BBInsertLocation); 1050ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1051ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BranchInst *PreheaderJump = cast<BranchInst>(&*Preheader->rbegin()); 1052ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines bool Increasing = LS.IndVarIncreasing; 1053ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1054ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines IRBuilder<> B(PreheaderJump); 1055ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1056ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // EnterLoopCond - is it okay to start executing this `LS'? 1057ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Value *EnterLoopCond = Increasing 1058ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines ? B.CreateICmpSLT(LS.IndVarStart, ExitSubloopAt) 1059ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines : B.CreateICmpSGT(LS.IndVarStart, ExitSubloopAt); 1060ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1061ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines B.CreateCondBr(EnterLoopCond, LS.Header, RRI.PseudoExit); 1062ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines PreheaderJump->eraseFromParent(); 1063ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1064ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines LS.LatchBr->setSuccessor(LS.LatchBrExitIdx, RRI.ExitSelector); 1065ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines B.SetInsertPoint(LS.LatchBr); 1066ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Value *TakeBackedgeLoopCond = 1067ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Increasing ? B.CreateICmpSLT(LS.IndVarNext, ExitSubloopAt) 1068ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines : B.CreateICmpSGT(LS.IndVarNext, ExitSubloopAt); 1069ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Value *CondForBranch = LS.LatchBrExitIdx == 1 1070ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines ? TakeBackedgeLoopCond 1071ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines : B.CreateNot(TakeBackedgeLoopCond); 1072ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1073ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines LS.LatchBr->setCondition(CondForBranch); 1074ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1075ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines B.SetInsertPoint(RRI.ExitSelector); 1076ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1077ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // IterationsLeft - are there any more iterations left, given the original 1078ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // upper bound on the induction variable? If not, we branch to the "real" 1079ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // exit. 1080ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Value *IterationsLeft = Increasing 1081ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines ? B.CreateICmpSLT(LS.IndVarNext, LS.LoopExitAt) 1082ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines : B.CreateICmpSGT(LS.IndVarNext, LS.LoopExitAt); 1083ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines B.CreateCondBr(IterationsLeft, RRI.PseudoExit, LS.LatchExit); 1084ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1085ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BranchInst *BranchToContinuation = 1086ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BranchInst::Create(ContinuationBlock, RRI.PseudoExit); 1087ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1088ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // We emit PHI nodes into `RRI.PseudoExit' that compute the "latest" value of 1089ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // each of the PHI nodes in the loop header. This feeds into the initial 1090ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // value of the same PHI nodes if/when we continue execution. 1091ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines for (Instruction &I : *LS.Header) { 1092ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (!isa<PHINode>(&I)) 1093ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines break; 1094ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1095ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines PHINode *PN = cast<PHINode>(&I); 1096ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1097ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines PHINode *NewPHI = PHINode::Create(PN->getType(), 2, PN->getName() + ".copy", 1098ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BranchToContinuation); 1099ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1100ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines NewPHI->addIncoming(PN->getIncomingValueForBlock(Preheader), Preheader); 1101ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines NewPHI->addIncoming(PN->getIncomingValueForBlock(LS.Latch), 1102ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines RRI.ExitSelector); 1103ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines RRI.PHIValuesAtPseudoExit.push_back(NewPHI); 1104ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 1105ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1106ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines RRI.IndVarEnd = PHINode::Create(LS.IndVarNext->getType(), 2, "indvar.end", 1107ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BranchToContinuation); 1108ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines RRI.IndVarEnd->addIncoming(LS.IndVarStart, Preheader); 1109ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines RRI.IndVarEnd->addIncoming(LS.IndVarNext, RRI.ExitSelector); 1110ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1111ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // The latch exit now has a branch from `RRI.ExitSelector' instead of 1112ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // `LS.Latch'. The PHI nodes need to be updated to reflect that. 1113ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines for (Instruction &I : *LS.LatchExit) { 1114ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (PHINode *PN = dyn_cast<PHINode>(&I)) 1115ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines replacePHIBlock(PN, LS.Latch, RRI.ExitSelector); 1116ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines else 1117ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines break; 1118ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 1119ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1120ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return RRI; 1121ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines} 1122ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1123ebe69fe11e48d322045d5949c83283927a0d790bStephen Hinesvoid LoopConstrainer::rewriteIncomingValuesForPHIs( 1124ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines LoopStructure &LS, BasicBlock *ContinuationBlock, 1125ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines const LoopConstrainer::RewrittenRangeInfo &RRI) const { 1126ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1127ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines unsigned PHIIndex = 0; 1128ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines for (Instruction &I : *LS.Header) { 1129ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (!isa<PHINode>(&I)) 1130ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines break; 1131ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1132ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines PHINode *PN = cast<PHINode>(&I); 1133ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1134ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines for (unsigned i = 0, e = PN->getNumIncomingValues(); i < e; ++i) 1135ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (PN->getIncomingBlock(i) == ContinuationBlock) 1136ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines PN->setIncomingValue(i, RRI.PHIValuesAtPseudoExit[PHIIndex++]); 1137ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 1138ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1139ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines LS.IndVarStart = RRI.IndVarEnd; 1140ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines} 1141ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1142ebe69fe11e48d322045d5949c83283927a0d790bStephen HinesBasicBlock *LoopConstrainer::createPreheader(const LoopStructure &LS, 1143ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BasicBlock *OldPreheader, 1144ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines const char *Tag) const { 1145ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1146ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BasicBlock *Preheader = BasicBlock::Create(Ctx, Tag, &F, LS.Header); 1147ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BranchInst::Create(LS.Header, Preheader); 1148ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1149ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines for (Instruction &I : *LS.Header) { 1150ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (!isa<PHINode>(&I)) 1151ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines break; 1152ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1153ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines PHINode *PN = cast<PHINode>(&I); 1154ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines for (unsigned i = 0, e = PN->getNumIncomingValues(); i < e; ++i) 1155ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines replacePHIBlock(PN, OldPreheader, Preheader); 1156ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 1157ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1158ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return Preheader; 1159ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines} 1160ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1161ebe69fe11e48d322045d5949c83283927a0d790bStephen Hinesvoid LoopConstrainer::addToParentLoopIfNeeded(ArrayRef<BasicBlock *> BBs) { 1162ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Loop *ParentLoop = OriginalLoop.getParentLoop(); 1163ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (!ParentLoop) 1164ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return; 1165ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1166ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines for (BasicBlock *BB : BBs) 1167ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines ParentLoop->addBasicBlockToLoop(BB, OriginalLoopInfo); 1168ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines} 1169ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1170ebe69fe11e48d322045d5949c83283927a0d790bStephen Hinesbool LoopConstrainer::run() { 1171ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BasicBlock *Preheader = nullptr; 1172ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines LatchTakenCount = SE.getExitCount(&OriginalLoop, MainLoopStructure.Latch); 1173ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Preheader = OriginalLoop.getLoopPreheader(); 1174ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines assert(!isa<SCEVCouldNotCompute>(LatchTakenCount) && Preheader != nullptr && 1175ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines "preconditions!"); 1176ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1177ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines OriginalPreheader = Preheader; 1178ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines MainLoopPreheader = Preheader; 1179ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1180ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Optional<SubRanges> MaybeSR = calculateSubRanges(); 1181ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (!MaybeSR.hasValue()) { 1182ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines DEBUG(dbgs() << "irce: could not compute subranges\n"); 1183ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return false; 1184ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 1185ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1186ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines SubRanges SR = MaybeSR.getValue(); 1187ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines bool Increasing = MainLoopStructure.IndVarIncreasing; 1188ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines IntegerType *IVTy = 1189ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines cast<IntegerType>(MainLoopStructure.IndVarNext->getType()); 1190ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 11914c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar SCEVExpander Expander(SE, F.getParent()->getDataLayout(), "irce"); 1192ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Instruction *InsertPt = OriginalPreheader->getTerminator(); 1193ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1194ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // It would have been better to make `PreLoop' and `PostLoop' 1195ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // `Optional<ClonedLoop>'s, but `ValueToValueMapTy' does not have a copy 1196ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // constructor. 1197ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines ClonedLoop PreLoop, PostLoop; 1198ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines bool NeedsPreLoop = 1199ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Increasing ? SR.LowLimit.hasValue() : SR.HighLimit.hasValue(); 1200ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines bool NeedsPostLoop = 1201ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Increasing ? SR.HighLimit.hasValue() : SR.LowLimit.hasValue(); 1202ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1203ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Value *ExitPreLoopAt = nullptr; 1204ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Value *ExitMainLoopAt = nullptr; 1205ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines const SCEVConstant *MinusOneS = 1206ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines cast<SCEVConstant>(SE.getConstant(IVTy, -1, true /* isSigned */)); 1207ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1208ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (NeedsPreLoop) { 1209ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines const SCEV *ExitPreLoopAtSCEV = nullptr; 1210ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1211ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (Increasing) 1212ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines ExitPreLoopAtSCEV = *SR.LowLimit; 1213ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines else { 1214ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (CanBeSMin(SE, *SR.HighLimit)) { 1215ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines DEBUG(dbgs() << "irce: could not prove no-overflow when computing " 1216ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines << "preloop exit limit. HighLimit = " << *(*SR.HighLimit) 1217ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines << "\n"); 1218ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return false; 1219ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 1220ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines ExitPreLoopAtSCEV = SE.getAddExpr(*SR.HighLimit, MinusOneS); 1221ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 1222ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1223ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines ExitPreLoopAt = Expander.expandCodeFor(ExitPreLoopAtSCEV, IVTy, InsertPt); 1224ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines ExitPreLoopAt->setName("exit.preloop.at"); 1225ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 1226ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1227ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (NeedsPostLoop) { 1228ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines const SCEV *ExitMainLoopAtSCEV = nullptr; 1229ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1230ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (Increasing) 1231ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines ExitMainLoopAtSCEV = *SR.HighLimit; 1232ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines else { 1233ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (CanBeSMin(SE, *SR.LowLimit)) { 1234ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines DEBUG(dbgs() << "irce: could not prove no-overflow when computing " 1235ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines << "mainloop exit limit. LowLimit = " << *(*SR.LowLimit) 1236ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines << "\n"); 1237ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return false; 1238ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 1239ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines ExitMainLoopAtSCEV = SE.getAddExpr(*SR.LowLimit, MinusOneS); 1240ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 1241ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1242ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines ExitMainLoopAt = Expander.expandCodeFor(ExitMainLoopAtSCEV, IVTy, InsertPt); 1243ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines ExitMainLoopAt->setName("exit.mainloop.at"); 1244ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 1245ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1246ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // We clone these ahead of time so that we don't have to deal with changing 1247ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // and temporarily invalid IR as we transform the loops. 1248ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (NeedsPreLoop) 1249ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines cloneLoop(PreLoop, "preloop"); 1250ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (NeedsPostLoop) 1251ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines cloneLoop(PostLoop, "postloop"); 1252ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1253ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines RewrittenRangeInfo PreLoopRRI; 1254ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1255ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (NeedsPreLoop) { 1256ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Preheader->getTerminator()->replaceUsesOfWith(MainLoopStructure.Header, 1257ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines PreLoop.Structure.Header); 1258ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1259ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines MainLoopPreheader = 1260ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines createPreheader(MainLoopStructure, Preheader, "mainloop"); 1261ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines PreLoopRRI = changeIterationSpaceEnd(PreLoop.Structure, Preheader, 1262ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines ExitPreLoopAt, MainLoopPreheader); 1263ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines rewriteIncomingValuesForPHIs(MainLoopStructure, MainLoopPreheader, 1264ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines PreLoopRRI); 1265ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 1266ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1267ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BasicBlock *PostLoopPreheader = nullptr; 1268ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines RewrittenRangeInfo PostLoopRRI; 1269ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1270ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (NeedsPostLoop) { 1271ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines PostLoopPreheader = 1272ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines createPreheader(PostLoop.Structure, Preheader, "postloop"); 1273ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines PostLoopRRI = changeIterationSpaceEnd(MainLoopStructure, MainLoopPreheader, 1274ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines ExitMainLoopAt, PostLoopPreheader); 1275ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines rewriteIncomingValuesForPHIs(PostLoop.Structure, PostLoopPreheader, 1276ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines PostLoopRRI); 1277ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 1278ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1279ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BasicBlock *NewMainLoopPreheader = 1280ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines MainLoopPreheader != Preheader ? MainLoopPreheader : nullptr; 1281ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BasicBlock *NewBlocks[] = {PostLoopPreheader, PreLoopRRI.PseudoExit, 1282ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines PreLoopRRI.ExitSelector, PostLoopRRI.PseudoExit, 1283ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines PostLoopRRI.ExitSelector, NewMainLoopPreheader}; 1284ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1285ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // Some of the above may be nullptr, filter them out before passing to 1286ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // addToParentLoopIfNeeded. 1287ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines auto NewBlocksEnd = 1288ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines std::remove(std::begin(NewBlocks), std::end(NewBlocks), nullptr); 1289ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1290ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines addToParentLoopIfNeeded(makeArrayRef(std::begin(NewBlocks), NewBlocksEnd)); 1291ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines addToParentLoopIfNeeded(PreLoop.Blocks); 1292ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines addToParentLoopIfNeeded(PostLoop.Blocks); 1293ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1294ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return true; 1295ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines} 1296ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1297ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// Computes and returns a range of values for the induction variable (IndVar) 1298ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// in which the range check can be safely elided. If it cannot compute such a 1299ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// range, returns None. 1300ebe69fe11e48d322045d5949c83283927a0d790bStephen HinesOptional<InductiveRangeCheck::Range> 1301ebe69fe11e48d322045d5949c83283927a0d790bStephen HinesInductiveRangeCheck::computeSafeIterationSpace(ScalarEvolution &SE, 1302ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines const SCEVAddRecExpr *IndVar, 1303ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines IRBuilder<> &) const { 1304ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // IndVar is of the form "A + B * I" (where "I" is the canonical induction 1305ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // variable, that may or may not exist as a real llvm::Value in the loop) and 1306ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // this inductive range check is a range check on the "C + D * I" ("C" is 1307ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // getOffset() and "D" is getScale()). We rewrite the value being range 1308ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // checked to "M + N * IndVar" where "N" = "D * B^(-1)" and "M" = "C - NA". 1309ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // Currently we support this only for "B" = "D" = { 1 or -1 }, but the code 1310ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // can be generalized as needed. 1311ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // 1312ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // The actual inequalities we solve are of the form 1313ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // 1314ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // 0 <= M + 1 * IndVar < L given L >= 0 (i.e. N == 1) 1315ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // 1316ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // The inequality is satisfied by -M <= IndVar < (L - M) [^1]. All additions 1317ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // and subtractions are twos-complement wrapping and comparisons are signed. 1318ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // 1319ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // Proof: 1320ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // 1321ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // If there exists IndVar such that -M <= IndVar < (L - M) then it follows 1322ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // that -M <= (-M + L) [== Eq. 1]. Since L >= 0, if (-M + L) sign-overflows 1323ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // then (-M + L) < (-M). Hence by [Eq. 1], (-M + L) could not have 1324ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // overflown. 1325ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // 1326ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // This means IndVar = t + (-M) for t in [0, L). Hence (IndVar + M) = t. 1327ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // Hence 0 <= (IndVar + M) < L 1328ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1329ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // [^1]: Note that the solution does _not_ apply if L < 0; consider values M = 1330ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // 127, IndVar = 126 and L = -2 in an i8 world. 1331ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1332ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (!IndVar->isAffine()) 1333ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return None; 1334ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1335ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines const SCEV *A = IndVar->getStart(); 1336ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines const SCEVConstant *B = dyn_cast<SCEVConstant>(IndVar->getStepRecurrence(SE)); 1337ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (!B) 1338ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return None; 1339ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1340ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines const SCEV *C = getOffset(); 1341ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines const SCEVConstant *D = dyn_cast<SCEVConstant>(getScale()); 1342ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (D != B) 1343ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return None; 1344ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1345ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines ConstantInt *ConstD = D->getValue(); 1346ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (!(ConstD->isMinusOne() || ConstD->isOne())) 1347ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return None; 1348ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1349ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines const SCEV *M = SE.getMinusSCEV(C, A); 1350ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1351ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines const SCEV *Begin = SE.getNegativeSCEV(M); 13524c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar const SCEV *UpperLimit = nullptr; 13534c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 13544c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // We strengthen "0 <= I" to "0 <= I < INT_SMAX" and "I < L" to "0 <= I < L". 13554c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // We can potentially do much better here. 13564c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (Value *V = getLength()) { 13574c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar UpperLimit = SE.getSCEV(V); 13584c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } else { 13594c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar assert(Kind == InductiveRangeCheck::RANGE_CHECK_LOWER && "invariant!"); 13604c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar unsigned BitWidth = cast<IntegerType>(IndVar->getType())->getBitWidth(); 13614c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar UpperLimit = SE.getConstant(APInt::getSignedMaxValue(BitWidth)); 13624c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 1363ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 13644c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar const SCEV *End = SE.getMinusSCEV(UpperLimit, M); 1365ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return InductiveRangeCheck::Range(Begin, End); 1366ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines} 1367ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1368ebe69fe11e48d322045d5949c83283927a0d790bStephen Hinesstatic Optional<InductiveRangeCheck::Range> 1369ebe69fe11e48d322045d5949c83283927a0d790bStephen HinesIntersectRange(ScalarEvolution &SE, 1370ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines const Optional<InductiveRangeCheck::Range> &R1, 1371ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines const InductiveRangeCheck::Range &R2, IRBuilder<> &B) { 1372ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (!R1.hasValue()) 1373ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return R2; 1374ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines auto &R1Value = R1.getValue(); 1375ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1376ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // TODO: we could widen the smaller range and have this work; but for now we 1377ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // bail out to keep things simple. 1378ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (R1Value.getType() != R2.getType()) 1379ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return None; 1380ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1381ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines const SCEV *NewBegin = SE.getSMaxExpr(R1Value.getBegin(), R2.getBegin()); 1382ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines const SCEV *NewEnd = SE.getSMinExpr(R1Value.getEnd(), R2.getEnd()); 1383ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1384ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return InductiveRangeCheck::Range(NewBegin, NewEnd); 1385ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines} 1386ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1387ebe69fe11e48d322045d5949c83283927a0d790bStephen Hinesbool InductiveRangeCheckElimination::runOnLoop(Loop *L, LPPassManager &LPM) { 1388ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (L->getBlocks().size() >= LoopSizeCutoff) { 1389ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines DEBUG(dbgs() << "irce: giving up constraining loop, too large\n";); 1390ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return false; 1391ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 1392ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1393ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BasicBlock *Preheader = L->getLoopPreheader(); 1394ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (!Preheader) { 1395ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines DEBUG(dbgs() << "irce: loop has no preheader, leaving\n"); 1396ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return false; 1397ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 1398ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1399ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines LLVMContext &Context = Preheader->getContext(); 1400ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines InductiveRangeCheck::AllocatorTy IRCAlloc; 1401ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines SmallVector<InductiveRangeCheck *, 16> RangeChecks; 1402ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines ScalarEvolution &SE = getAnalysis<ScalarEvolution>(); 1403ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BranchProbabilityInfo &BPI = getAnalysis<BranchProbabilityInfo>(); 1404ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1405ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines for (auto BBI : L->getBlocks()) 1406ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (BranchInst *TBI = dyn_cast<BranchInst>(BBI->getTerminator())) 1407ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (InductiveRangeCheck *IRC = 1408ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines InductiveRangeCheck::create(IRCAlloc, TBI, L, SE, BPI)) 1409ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines RangeChecks.push_back(IRC); 1410ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1411ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (RangeChecks.empty()) 1412ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return false; 1413ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 14144c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar auto PrintRecognizedRangeChecks = [&](raw_ostream &OS) { 14154c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar OS << "irce: looking at loop "; L->print(OS); 14164c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar OS << "irce: loop has " << RangeChecks.size() 14174c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar << " inductive range checks: \n"; 14184c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar for (InductiveRangeCheck *IRC : RangeChecks) 14194c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar IRC->print(OS); 14204c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar }; 14214c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 14224c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar DEBUG(PrintRecognizedRangeChecks(dbgs())); 14234c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 14244c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (PrintRangeChecks) 14254c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar PrintRecognizedRangeChecks(errs()); 1426ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1427ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines const char *FailureReason = nullptr; 1428ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Optional<LoopStructure> MaybeLoopStructure = 1429ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines LoopStructure::parseLoopStructure(SE, BPI, *L, FailureReason); 1430ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (!MaybeLoopStructure.hasValue()) { 1431ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines DEBUG(dbgs() << "irce: could not parse loop structure: " << FailureReason 1432ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines << "\n";); 1433ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return false; 1434ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 1435ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines LoopStructure LS = MaybeLoopStructure.getValue(); 1436ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines bool Increasing = LS.IndVarIncreasing; 1437ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines const SCEV *MinusOne = 1438ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines SE.getConstant(LS.IndVarNext->getType(), Increasing ? -1 : 1, true); 1439ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines const SCEVAddRecExpr *IndVar = 1440ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines cast<SCEVAddRecExpr>(SE.getAddExpr(SE.getSCEV(LS.IndVarNext), MinusOne)); 1441ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1442ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Optional<InductiveRangeCheck::Range> SafeIterRange; 1443ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Instruction *ExprInsertPt = Preheader->getTerminator(); 1444ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1445ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines SmallVector<InductiveRangeCheck *, 4> RangeChecksToEliminate; 1446ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1447ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines IRBuilder<> B(ExprInsertPt); 1448ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines for (InductiveRangeCheck *IRC : RangeChecks) { 1449ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines auto Result = IRC->computeSafeIterationSpace(SE, IndVar, B); 1450ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (Result.hasValue()) { 1451ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines auto MaybeSafeIterRange = 1452ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines IntersectRange(SE, SafeIterRange, Result.getValue(), B); 1453ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (MaybeSafeIterRange.hasValue()) { 1454ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines RangeChecksToEliminate.push_back(IRC); 1455ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines SafeIterRange = MaybeSafeIterRange.getValue(); 1456ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 1457ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 1458ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 1459ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1460ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (!SafeIterRange.hasValue()) 1461ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return false; 1462ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1463ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines LoopConstrainer LC(*L, getAnalysis<LoopInfoWrapperPass>().getLoopInfo(), LS, 1464ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines SE, SafeIterRange.getValue()); 1465ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines bool Changed = LC.run(); 1466ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1467ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (Changed) { 1468ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines auto PrintConstrainedLoopInfo = [L]() { 1469ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines dbgs() << "irce: in function "; 1470ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines dbgs() << L->getHeader()->getParent()->getName() << ": "; 1471ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines dbgs() << "constrained "; 1472ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines L->print(dbgs()); 1473ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines }; 1474ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1475ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines DEBUG(PrintConstrainedLoopInfo()); 1476ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1477ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (PrintChangedLoops) 1478ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines PrintConstrainedLoopInfo(); 1479ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1480ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // Optimize away the now-redundant range checks. 1481ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1482ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines for (InductiveRangeCheck *IRC : RangeChecksToEliminate) { 1483ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines ConstantInt *FoldedRangeCheck = IRC->getPassingDirection() 1484ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines ? ConstantInt::getTrue(Context) 1485ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines : ConstantInt::getFalse(Context); 1486ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines IRC->getBranch()->setCondition(FoldedRangeCheck); 1487ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 1488ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 1489ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1490ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return Changed; 1491ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines} 1492ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1493ebe69fe11e48d322045d5949c83283927a0d790bStephen HinesPass *llvm::createInductiveRangeCheckEliminationPass() { 1494ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return new InductiveRangeCheckElimination; 1495ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines} 1496