123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452145314541455145614571458145914601461146214631464146514661467146814691470147114721473147414751476147714781479148014811482148314841485148614871488148914901491149214931494149514961497149814991500150115021503150415051506150715081509151015111512151315141515151615171518151915201521152215231524152515261527152815291530153115321533153415351536153715381539154015411542154315441545154615471548154915501551155215531554155515561557155815591560156115621563156415651566156715681569157015711572157315741575157615771578157915801581158215831584158515861587158815891590159115921593159415951596159715981599160016011602160316041605160616071608160916101611161216131614161516161617161816191620162116221623162416251626162716281629163016311632163316341635163616371638163916401641164216431644164516461647164816491650165116521653165416551656165716581659166016611662166316641665166616671668166916701671167216731674167516761677167816791680168116821683168416851686168716881689169016911692169316941695169616971698169917001701170217031704170517061707170817091710171117121713171417151716171717181719172017211722172317241725172617271728172917301731 |
- #include "llvm/ADT/APInt.h"
- #include "llvm/ADT/BitVector.h"
- #include "llvm/ADT/DenseMap.h"
- #include "llvm/ADT/DenseSet.h"
- #include "llvm/ADT/MapVector.h"
- #include "llvm/ADT/STLExtras.h"
- #include "llvm/ADT/SmallPtrSet.h"
- #include "llvm/ADT/SmallVector.h"
- #include "llvm/ADT/Statistic.h"
- #include "llvm/Analysis/AliasAnalysis.h"
- #include "llvm/Analysis/AliasSetTracker.h"
- #include "llvm/Analysis/LoopInfo.h"
- #include "llvm/Analysis/LoopPass.h"
- #include "llvm/Analysis/ScalarEvolution.h"
- #include "llvm/Analysis/ScalarEvolutionExpressions.h"
- #include "llvm/Analysis/TargetLibraryInfo.h"
- #include "llvm/Analysis/ValueTracking.h"
- #include "llvm/IR/BasicBlock.h"
- #include "llvm/IR/Constants.h"
- #include "llvm/IR/DataLayout.h"
- #include "llvm/IR/DerivedTypes.h"
- #include "llvm/IR/Dominators.h"
- #include "llvm/IR/IRBuilder.h"
- #include "llvm/IR/InstrTypes.h"
- #include "llvm/IR/Instruction.h"
- #include "llvm/IR/Instructions.h"
- #include "llvm/IR/IntrinsicInst.h"
- #include "llvm/IR/Intrinsics.h"
- #include "llvm/IR/Module.h"
- #include "llvm/IR/Type.h"
- #include "llvm/IR/Use.h"
- #include "llvm/IR/User.h"
- #include "llvm/IR/Value.h"
- #include "llvm/InitializePasses.h"
- #include "llvm/Pass.h"
- #include "llvm/Support/Casting.h"
- #include "llvm/Support/CommandLine.h"
- #include "llvm/Support/Debug.h"
- #include "llvm/Support/raw_ostream.h"
- #include "llvm/Transforms/Scalar.h"
- #include "llvm/Transforms/Scalar/LoopReroll.h"
- #include "llvm/Transforms/Utils.h"
- #include "llvm/Transforms/Utils/BasicBlockUtils.h"
- #include "llvm/Transforms/Utils/Local.h"
- #include "llvm/Transforms/Utils/LoopUtils.h"
- #include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"
- #include <cassert>
- #include <cstddef>
- #include <cstdint>
- #include <cstdlib>
- #include <iterator>
- #include <map>
- #include <utility>
- using namespace llvm;
- #define DEBUG_TYPE "loop-reroll"
- STATISTIC(NumRerolledLoops, "Number of rerolled loops");
- static cl::opt<unsigned>
- NumToleratedFailedMatches("reroll-num-tolerated-failed-matches", cl::init(400),
- cl::Hidden,
- cl::desc("The maximum number of failures to tolerate"
- " during fuzzy matching. (default: 400)"));
- namespace {
- enum IterationLimits {
-
- IL_MaxRerollIterations = 32,
-
-
- IL_All,
- IL_End
- };
- class LoopRerollLegacyPass : public LoopPass {
- public:
- static char ID;
- LoopRerollLegacyPass() : LoopPass(ID) {
- initializeLoopRerollLegacyPassPass(*PassRegistry::getPassRegistry());
- }
- bool runOnLoop(Loop *L, LPPassManager &LPM) override;
- void getAnalysisUsage(AnalysisUsage &AU) const override {
- AU.addRequired<TargetLibraryInfoWrapperPass>();
- getLoopAnalysisUsage(AU);
- }
- };
- class LoopReroll {
- public:
- LoopReroll(AliasAnalysis *AA, LoopInfo *LI, ScalarEvolution *SE,
- TargetLibraryInfo *TLI, DominatorTree *DT, bool PreserveLCSSA)
- : AA(AA), LI(LI), SE(SE), TLI(TLI), DT(DT),
- PreserveLCSSA(PreserveLCSSA) {}
- bool runOnLoop(Loop *L);
- protected:
- AliasAnalysis *AA;
- LoopInfo *LI;
- ScalarEvolution *SE;
- TargetLibraryInfo *TLI;
- DominatorTree *DT;
- bool PreserveLCSSA;
- using SmallInstructionVector = SmallVector<Instruction *, 16>;
- using SmallInstructionSet = SmallPtrSet<Instruction *, 16>;
-
- DenseMap<Instruction *, int64_t> IVToIncMap;
-
-
- Instruction *LoopControlIV;
-
-
-
- struct SimpleLoopReduction {
- SimpleLoopReduction(Instruction *P, Loop *L) : Instructions(1, P) {
- assert(isa<PHINode>(P) && "First reduction instruction must be a PHI");
- add(L);
- }
- bool valid() const {
- return Valid;
- }
- Instruction *getPHI() const {
- assert(Valid && "Using invalid reduction");
- return Instructions.front();
- }
- Instruction *getReducedValue() const {
- assert(Valid && "Using invalid reduction");
- return Instructions.back();
- }
- Instruction *get(size_t i) const {
- assert(Valid && "Using invalid reduction");
- return Instructions[i+1];
- }
- Instruction *operator [] (size_t i) const { return get(i); }
-
- size_t size() const {
- assert(Valid && "Using invalid reduction");
- return Instructions.size()-1;
- }
- using iterator = SmallInstructionVector::iterator;
- using const_iterator = SmallInstructionVector::const_iterator;
- iterator begin() {
- assert(Valid && "Using invalid reduction");
- return std::next(Instructions.begin());
- }
- const_iterator begin() const {
- assert(Valid && "Using invalid reduction");
- return std::next(Instructions.begin());
- }
- iterator end() { return Instructions.end(); }
- const_iterator end() const { return Instructions.end(); }
- protected:
- bool Valid = false;
- SmallInstructionVector Instructions;
- void add(Loop *L);
- };
-
-
- struct ReductionTracker {
- using SmallReductionVector = SmallVector<SimpleLoopReduction, 16>;
-
- void addSLR(SimpleLoopReduction &SLR) { PossibleReds.push_back(SLR); }
-
-
-
-
-
-
-
-
- void restrictToScale(uint64_t Scale,
- SmallInstructionSet &PossibleRedSet,
- SmallInstructionSet &PossibleRedPHISet,
- SmallInstructionSet &PossibleRedLastSet) {
- PossibleRedIdx.clear();
- PossibleRedIter.clear();
- Reds.clear();
- for (unsigned i = 0, e = PossibleReds.size(); i != e; ++i)
- if (PossibleReds[i].size() % Scale == 0) {
- PossibleRedLastSet.insert(PossibleReds[i].getReducedValue());
- PossibleRedPHISet.insert(PossibleReds[i].getPHI());
- PossibleRedSet.insert(PossibleReds[i].getPHI());
- PossibleRedIdx[PossibleReds[i].getPHI()] = i;
- for (Instruction *J : PossibleReds[i]) {
- PossibleRedSet.insert(J);
- PossibleRedIdx[J] = i;
- }
- }
- }
-
-
-
- bool isPairInSame(Instruction *J1, Instruction *J2) {
- DenseMap<Instruction *, int>::iterator J1I = PossibleRedIdx.find(J1);
- if (J1I != PossibleRedIdx.end()) {
- DenseMap<Instruction *, int>::iterator J2I = PossibleRedIdx.find(J2);
- if (J2I != PossibleRedIdx.end() && J1I->second == J2I->second)
- return true;
- }
- return false;
- }
-
-
-
- void recordPair(Instruction *J1, Instruction *J2, unsigned i) {
- if (PossibleRedIdx.count(J1)) {
- assert(PossibleRedIdx.count(J2) &&
- "Recording reduction vs. non-reduction instruction?");
- PossibleRedIter[J1] = 0;
- PossibleRedIter[J2] = i;
- int Idx = PossibleRedIdx[J1];
- assert(Idx == PossibleRedIdx[J2] &&
- "Recording pair from different reductions?");
- Reds.insert(Idx);
- }
- }
-
-
- bool validateSelected();
- void replaceSelected();
- protected:
-
- SmallReductionVector PossibleReds;
- DenseMap<Instruction *, int> PossibleRedIdx;
- DenseMap<Instruction *, int> PossibleRedIter;
- DenseSet<int> Reds;
- };
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- struct DAGRootSet {
- Instruction *BaseInst;
- SmallInstructionVector Roots;
-
- SmallInstructionSet SubsumedInsts;
- };
-
-
- struct DAGRootTracker {
- DAGRootTracker(LoopReroll *Parent, Loop *L, Instruction *IV,
- ScalarEvolution *SE, AliasAnalysis *AA,
- TargetLibraryInfo *TLI, DominatorTree *DT, LoopInfo *LI,
- bool PreserveLCSSA,
- DenseMap<Instruction *, int64_t> &IncrMap,
- Instruction *LoopCtrlIV)
- : Parent(Parent), L(L), SE(SE), AA(AA), TLI(TLI), DT(DT), LI(LI),
- PreserveLCSSA(PreserveLCSSA), IV(IV), IVToIncMap(IncrMap),
- LoopControlIV(LoopCtrlIV) {}
-
- bool findRoots();
-
- bool validate(ReductionTracker &Reductions);
-
-
-
- void replace(const SCEV *BackedgeTakenCount);
- protected:
- using UsesTy = MapVector<Instruction *, BitVector>;
- void findRootsRecursive(Instruction *IVU,
- SmallInstructionSet SubsumedInsts);
- bool findRootsBase(Instruction *IVU, SmallInstructionSet SubsumedInsts);
- bool collectPossibleRoots(Instruction *Base,
- std::map<int64_t,Instruction*> &Roots);
- bool validateRootSet(DAGRootSet &DRS);
- bool collectUsedInstructions(SmallInstructionSet &PossibleRedSet);
- void collectInLoopUserSet(const SmallInstructionVector &Roots,
- const SmallInstructionSet &Exclude,
- const SmallInstructionSet &Final,
- DenseSet<Instruction *> &Users);
- void collectInLoopUserSet(Instruction *Root,
- const SmallInstructionSet &Exclude,
- const SmallInstructionSet &Final,
- DenseSet<Instruction *> &Users);
- UsesTy::iterator nextInstr(int Val, UsesTy &In,
- const SmallInstructionSet &Exclude,
- UsesTy::iterator *StartI=nullptr);
- bool isBaseInst(Instruction *I);
- bool isRootInst(Instruction *I);
- bool instrDependsOn(Instruction *I,
- UsesTy::iterator Start,
- UsesTy::iterator End);
- void replaceIV(DAGRootSet &DRS, const SCEV *Start, const SCEV *IncrExpr);
- LoopReroll *Parent;
-
- Loop *L;
- ScalarEvolution *SE;
- AliasAnalysis *AA;
- TargetLibraryInfo *TLI;
- DominatorTree *DT;
- LoopInfo *LI;
- bool PreserveLCSSA;
-
- Instruction *IV;
-
- int64_t Inc;
-
-
-
- uint64_t Scale;
-
- SmallVector<DAGRootSet,16> RootSets;
-
- SmallInstructionVector LoopIncs;
-
-
-
- UsesTy Uses;
-
- DenseMap<Instruction *, int64_t> &IVToIncMap;
- Instruction *LoopControlIV;
- };
-
- bool isCompareUsedByBranch(Instruction *I) {
- auto *TI = I->getParent()->getTerminator();
- if (!isa<BranchInst>(TI) || !isa<CmpInst>(I))
- return false;
- return I->hasOneUse() && TI->getOperand(0) == I;
- };
- bool isLoopControlIV(Loop *L, Instruction *IV);
- void collectPossibleIVs(Loop *L, SmallInstructionVector &PossibleIVs);
- void collectPossibleReductions(Loop *L,
- ReductionTracker &Reductions);
- bool reroll(Instruction *IV, Loop *L, BasicBlock *Header,
- const SCEV *BackedgeTakenCount, ReductionTracker &Reductions);
- };
- }
- char LoopRerollLegacyPass::ID = 0;
- INITIALIZE_PASS_BEGIN(LoopRerollLegacyPass, "loop-reroll", "Reroll loops",
- false, false)
- INITIALIZE_PASS_DEPENDENCY(LoopPass)
- INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
- INITIALIZE_PASS_END(LoopRerollLegacyPass, "loop-reroll", "Reroll loops", false,
- false)
- Pass *llvm::createLoopRerollPass() { return new LoopRerollLegacyPass; }
- static bool hasUsesOutsideLoop(Instruction *I, Loop *L) {
- for (User *U : I->users()) {
- if (!L->contains(cast<Instruction>(U)))
- return true;
- }
- return false;
- }
- bool LoopReroll::isLoopControlIV(Loop *L, Instruction *IV) {
- unsigned IVUses = IV->getNumUses();
- if (IVUses != 2 && IVUses != 1)
- return false;
- for (auto *User : IV->users()) {
- int32_t IncOrCmpUses = User->getNumUses();
- bool IsCompInst = isCompareUsedByBranch(cast<Instruction>(User));
-
- if (IncOrCmpUses != 2 && IncOrCmpUses != 1)
- return false;
-
- if (IVUses == 1) {
-
-
- if (IsCompInst || IncOrCmpUses != 2)
- return false;
- }
-
- if (IVUses == 2 && IncOrCmpUses != 1)
- return false;
-
- if (auto *BO = dyn_cast<BinaryOperator>(User)) {
- if (BO->getOpcode() == Instruction::Add) {
-
-
- for (auto *UU : User->users()) {
- if (PHINode *PN = dyn_cast<PHINode>(UU)) {
- if (PN != IV)
- return false;
- }
-
- else {
- Instruction *UUser = dyn_cast<Instruction>(UU);
-
-
- if (BO->hasNoSignedWrap() && UUser && UUser->hasOneUse() &&
- isa<SExtInst>(UUser))
- UUser = dyn_cast<Instruction>(*(UUser->user_begin()));
- if (!isCompareUsedByBranch(UUser))
- return false;
- }
- }
- } else
- return false;
-
- } else if (!IsCompInst)
- return false;
- }
- return true;
- }
- void LoopReroll::collectPossibleIVs(Loop *L,
- SmallInstructionVector &PossibleIVs) {
- BasicBlock *Header = L->getHeader();
- for (BasicBlock::iterator I = Header->begin(),
- IE = Header->getFirstInsertionPt(); I != IE; ++I) {
- if (!isa<PHINode>(I))
- continue;
- if (!I->getType()->isIntegerTy() && !I->getType()->isPointerTy())
- continue;
- if (const SCEVAddRecExpr *PHISCEV =
- dyn_cast<SCEVAddRecExpr>(SE->getSCEV(&*I))) {
- if (PHISCEV->getLoop() != L)
- continue;
- if (!PHISCEV->isAffine())
- continue;
- auto IncSCEV = dyn_cast<SCEVConstant>(PHISCEV->getStepRecurrence(*SE));
- if (IncSCEV) {
- IVToIncMap[&*I] = IncSCEV->getValue()->getSExtValue();
- LLVM_DEBUG(dbgs() << "LRR: Possible IV: " << *I << " = " << *PHISCEV
- << "\n");
- if (isLoopControlIV(L, &*I)) {
- assert(!LoopControlIV && "Found two loop control only IV");
- LoopControlIV = &(*I);
- LLVM_DEBUG(dbgs() << "LRR: Possible loop control only IV: " << *I
- << " = " << *PHISCEV << "\n");
- } else
- PossibleIVs.push_back(&*I);
- }
- }
- }
- }
- void LoopReroll::SimpleLoopReduction::add(Loop *L) {
- assert(!Valid && "Cannot add to an already-valid chain");
-
-
-
- Instruction *C = Instructions.front();
- if (C->user_empty())
- return;
- do {
- C = cast<Instruction>(*C->user_begin());
- if (C->hasOneUse()) {
- if (!C->isBinaryOp())
- return;
- if (!(isa<PHINode>(Instructions.back()) ||
- C->isSameOperationAs(Instructions.back())))
- return;
- Instructions.push_back(C);
- }
- } while (C->hasOneUse());
- if (Instructions.size() < 2 ||
- !C->isSameOperationAs(Instructions.back()) ||
- C->use_empty())
- return;
-
- for (User *U : C->users()) {
-
- if (L->contains(cast<Instruction>(U)))
- if (cast<Instruction>(U) != Instructions.front())
- return;
- }
- Instructions.push_back(C);
- Valid = true;
- }
- void LoopReroll::collectPossibleReductions(Loop *L,
- ReductionTracker &Reductions) {
- BasicBlock *Header = L->getHeader();
- for (BasicBlock::iterator I = Header->begin(),
- IE = Header->getFirstInsertionPt(); I != IE; ++I) {
- if (!isa<PHINode>(I))
- continue;
- if (!I->getType()->isSingleValueType())
- continue;
- SimpleLoopReduction SLR(&*I, L);
- if (!SLR.valid())
- continue;
- LLVM_DEBUG(dbgs() << "LRR: Possible reduction: " << *I << " (with "
- << SLR.size() << " chained instructions)\n");
- Reductions.addSLR(SLR);
- }
- }
- void LoopReroll::DAGRootTracker::collectInLoopUserSet(
- Instruction *Root, const SmallInstructionSet &Exclude,
- const SmallInstructionSet &Final,
- DenseSet<Instruction *> &Users) {
- SmallInstructionVector Queue(1, Root);
- while (!Queue.empty()) {
- Instruction *I = Queue.pop_back_val();
- if (!Users.insert(I).second)
- continue;
- if (!Final.count(I))
- for (Use &U : I->uses()) {
- Instruction *User = cast<Instruction>(U.getUser());
- if (PHINode *PN = dyn_cast<PHINode>(User)) {
-
- if (PN->getIncomingBlock(U) == L->getHeader())
- continue;
- }
- if (L->contains(User) && !Exclude.count(User)) {
- Queue.push_back(User);
- }
- }
-
- for (Use &U : I->operands()) {
- if (Instruction *Op = dyn_cast<Instruction>(U))
- if (Op->hasOneUse() && L->contains(Op) && !Exclude.count(Op) &&
- !Final.count(Op))
- Queue.push_back(Op);
- }
- }
- }
- void LoopReroll::DAGRootTracker::collectInLoopUserSet(
- const SmallInstructionVector &Roots,
- const SmallInstructionSet &Exclude,
- const SmallInstructionSet &Final,
- DenseSet<Instruction *> &Users) {
- for (Instruction *Root : Roots)
- collectInLoopUserSet(Root, Exclude, Final, Users);
- }
- static bool isUnorderedLoadStore(Instruction *I) {
- if (LoadInst *LI = dyn_cast<LoadInst>(I))
- return LI->isUnordered();
- if (StoreInst *SI = dyn_cast<StoreInst>(I))
- return SI->isUnordered();
- if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I))
- return !MI->isVolatile();
- return false;
- }
- static bool isSimpleArithmeticOp(User *IVU) {
- if (Instruction *I = dyn_cast<Instruction>(IVU)) {
- switch (I->getOpcode()) {
- default: return false;
- case Instruction::Add:
- case Instruction::Sub:
- case Instruction::Mul:
- case Instruction::Shl:
- case Instruction::AShr:
- case Instruction::LShr:
- case Instruction::GetElementPtr:
- case Instruction::Trunc:
- case Instruction::ZExt:
- case Instruction::SExt:
- return true;
- }
- }
- return false;
- }
- static bool isLoopIncrement(User *U, Instruction *IV) {
- BinaryOperator *BO = dyn_cast<BinaryOperator>(U);
- if ((BO && BO->getOpcode() != Instruction::Add) ||
- (!BO && !isa<GetElementPtrInst>(U)))
- return false;
- for (auto *UU : U->users()) {
- PHINode *PN = dyn_cast<PHINode>(UU);
- if (PN && PN == IV)
- return true;
- }
- return false;
- }
- bool LoopReroll::DAGRootTracker::
- collectPossibleRoots(Instruction *Base, std::map<int64_t,Instruction*> &Roots) {
- SmallInstructionVector BaseUsers;
- for (auto *I : Base->users()) {
- ConstantInt *CI = nullptr;
- if (isLoopIncrement(I, IV)) {
- LoopIncs.push_back(cast<Instruction>(I));
- continue;
- }
-
- if (auto *BO = dyn_cast<BinaryOperator>(I)) {
- if (BO->getOpcode() == Instruction::Add ||
- BO->getOpcode() == Instruction::Or)
- CI = dyn_cast<ConstantInt>(BO->getOperand(1));
- } else if (auto *GEP = dyn_cast<GetElementPtrInst>(I)) {
- Value *LastOperand = GEP->getOperand(GEP->getNumOperands()-1);
- CI = dyn_cast<ConstantInt>(LastOperand);
- }
- if (!CI) {
- if (Instruction *II = dyn_cast<Instruction>(I)) {
- BaseUsers.push_back(II);
- continue;
- } else {
- LLVM_DEBUG(dbgs() << "LRR: Aborting due to non-instruction: " << *I
- << "\n");
- return false;
- }
- }
- int64_t V = std::abs(CI->getValue().getSExtValue());
- if (Roots.find(V) != Roots.end())
-
- return false;
- Roots[V] = cast<Instruction>(I);
- }
-
- if (Roots.empty() || (Roots.size() == 1 && BaseUsers.empty()))
- return false;
-
-
-
- if (BaseUsers.size()) {
- if (Roots.find(0) != Roots.end()) {
- LLVM_DEBUG(dbgs() << "LRR: Multiple roots found for base - aborting!\n");
- return false;
- }
- Roots[0] = Base;
- }
-
- unsigned NumBaseUses = BaseUsers.size();
- if (NumBaseUses == 0)
- NumBaseUses = Roots.begin()->second->getNumUses();
-
- for (auto &KV : Roots) {
- if (KV.first == 0)
- continue;
- if (!KV.second->hasNUses(NumBaseUses)) {
- LLVM_DEBUG(dbgs() << "LRR: Aborting - Root and Base #users not the same: "
- << "#Base=" << NumBaseUses
- << ", #Root=" << KV.second->getNumUses() << "\n");
- return false;
- }
- }
- return true;
- }
- void LoopReroll::DAGRootTracker::
- findRootsRecursive(Instruction *I, SmallInstructionSet SubsumedInsts) {
-
-
- if (I->hasNUsesOrMore(IL_MaxRerollIterations + 1))
- return;
- if (I != IV && findRootsBase(I, SubsumedInsts))
- return;
- SubsumedInsts.insert(I);
- for (User *V : I->users()) {
- Instruction *I = cast<Instruction>(V);
- if (is_contained(LoopIncs, I))
- continue;
- if (!isSimpleArithmeticOp(I))
- continue;
-
- findRootsRecursive(I, SubsumedInsts);
- }
- }
- bool LoopReroll::DAGRootTracker::validateRootSet(DAGRootSet &DRS) {
- if (DRS.Roots.empty())
- return false;
-
-
-
- if (hasUsesOutsideLoop(DRS.BaseInst, L))
- return false;
-
-
-
-
-
-
-
-
-
- const auto *ADR = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(DRS.BaseInst));
- if (!ADR)
- return false;
-
- unsigned N = DRS.Roots.size() + 1;
- const SCEV *StepSCEV = SE->getMinusSCEV(SE->getSCEV(DRS.Roots[0]), ADR);
- if (isa<SCEVCouldNotCompute>(StepSCEV) || StepSCEV->getType()->isPointerTy())
- return false;
- const SCEV *ScaleSCEV = SE->getConstant(StepSCEV->getType(), N);
- if (ADR->getStepRecurrence(*SE) != SE->getMulExpr(StepSCEV, ScaleSCEV))
- return false;
-
- for (unsigned i = 1; i < N - 1; ++i) {
- const SCEV *NewStepSCEV = SE->getMinusSCEV(SE->getSCEV(DRS.Roots[i]),
- SE->getSCEV(DRS.Roots[i-1]));
- if (NewStepSCEV != StepSCEV)
- return false;
- }
- return true;
- }
- bool LoopReroll::DAGRootTracker::
- findRootsBase(Instruction *IVU, SmallInstructionSet SubsumedInsts) {
-
- const auto *IVU_ADR = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(IVU));
- if (!IVU_ADR || IVU_ADR->getLoop() != L)
- return false;
- std::map<int64_t, Instruction*> V;
- if (!collectPossibleRoots(IVU, V))
- return false;
-
-
- if (V.find(0) == V.end())
- SubsumedInsts.insert(IVU);
-
- DAGRootSet DRS;
- DRS.BaseInst = nullptr;
- SmallVector<DAGRootSet, 16> PotentialRootSets;
- for (auto &KV : V) {
- if (!DRS.BaseInst) {
- DRS.BaseInst = KV.second;
- DRS.SubsumedInsts = SubsumedInsts;
- } else if (DRS.Roots.empty()) {
- DRS.Roots.push_back(KV.second);
- } else if (V.find(KV.first - 1) != V.end()) {
- DRS.Roots.push_back(KV.second);
- } else {
-
- if (!validateRootSet(DRS))
- return false;
-
- PotentialRootSets.push_back(DRS);
- DRS.BaseInst = KV.second;
- DRS.Roots.clear();
- }
- }
- if (!validateRootSet(DRS))
- return false;
- PotentialRootSets.push_back(DRS);
- RootSets.append(PotentialRootSets.begin(), PotentialRootSets.end());
- return true;
- }
- bool LoopReroll::DAGRootTracker::findRoots() {
- Inc = IVToIncMap[IV];
- assert(RootSets.empty() && "Unclean state!");
- if (std::abs(Inc) == 1) {
- for (auto *IVU : IV->users()) {
- if (isLoopIncrement(IVU, IV))
- LoopIncs.push_back(cast<Instruction>(IVU));
- }
- findRootsRecursive(IV, SmallInstructionSet());
- LoopIncs.push_back(IV);
- } else {
- if (!findRootsBase(IV, SmallInstructionSet()))
- return false;
- }
-
- if (RootSets.empty()) {
- LLVM_DEBUG(dbgs() << "LRR: Aborting because no root sets found!\n");
- return false;
- }
- for (auto &V : RootSets) {
- if (V.Roots.empty() || V.Roots.size() != RootSets[0].Roots.size()) {
- LLVM_DEBUG(
- dbgs()
- << "LRR: Aborting because not all root sets have the same size\n");
- return false;
- }
- }
- Scale = RootSets[0].Roots.size() + 1;
- if (Scale > IL_MaxRerollIterations) {
- LLVM_DEBUG(dbgs() << "LRR: Aborting - too many iterations found. "
- << "#Found=" << Scale
- << ", #Max=" << IL_MaxRerollIterations << "\n");
- return false;
- }
- LLVM_DEBUG(dbgs() << "LRR: Successfully found roots: Scale=" << Scale
- << "\n");
- return true;
- }
- bool LoopReroll::DAGRootTracker::collectUsedInstructions(SmallInstructionSet &PossibleRedSet) {
-
-
- for (auto &I : *L->getHeader()) {
- Uses[&I].resize(IL_End);
- }
- SmallInstructionSet Exclude;
- for (auto &DRS : RootSets) {
- Exclude.insert(DRS.Roots.begin(), DRS.Roots.end());
- Exclude.insert(DRS.SubsumedInsts.begin(), DRS.SubsumedInsts.end());
- Exclude.insert(DRS.BaseInst);
- }
- Exclude.insert(LoopIncs.begin(), LoopIncs.end());
- for (auto &DRS : RootSets) {
- DenseSet<Instruction*> VBase;
- collectInLoopUserSet(DRS.BaseInst, Exclude, PossibleRedSet, VBase);
- for (auto *I : VBase) {
- Uses[I].set(0);
- }
- unsigned Idx = 1;
- for (auto *Root : DRS.Roots) {
- DenseSet<Instruction*> V;
- collectInLoopUserSet(Root, Exclude, PossibleRedSet, V);
-
- if (V.size() != VBase.size()) {
- LLVM_DEBUG(dbgs() << "LRR: Aborting - use sets are different sizes\n");
- return false;
- }
- for (auto *I : V) {
- Uses[I].set(Idx);
- }
- ++Idx;
- }
-
- for (auto *I : DRS.SubsumedInsts) {
- Uses[I].set(IL_All);
- }
- }
-
- Exclude.clear();
- for (auto &DRS : RootSets) {
- Exclude.insert(DRS.Roots.begin(), DRS.Roots.end());
- Exclude.insert(DRS.SubsumedInsts.begin(), DRS.SubsumedInsts.end());
- Exclude.insert(DRS.BaseInst);
- }
- DenseSet<Instruction*> V;
- collectInLoopUserSet(LoopIncs, Exclude, PossibleRedSet, V);
- for (auto *I : V) {
- if (I->mayHaveSideEffects()) {
- LLVM_DEBUG(dbgs() << "LRR: Aborting - "
- << "An instruction which does not belong to any root "
- << "sets must not have side effects: " << *I);
- return false;
- }
- Uses[I].set(IL_All);
- }
- return true;
- }
- LoopReroll::DAGRootTracker::UsesTy::iterator
- LoopReroll::DAGRootTracker::nextInstr(int Val, UsesTy &In,
- const SmallInstructionSet &Exclude,
- UsesTy::iterator *StartI) {
- UsesTy::iterator I = StartI ? *StartI : In.begin();
- while (I != In.end() && (I->second.test(Val) == 0 ||
- Exclude.contains(I->first)))
- ++I;
- return I;
- }
- bool LoopReroll::DAGRootTracker::isBaseInst(Instruction *I) {
- for (auto &DRS : RootSets) {
- if (DRS.BaseInst == I)
- return true;
- }
- return false;
- }
- bool LoopReroll::DAGRootTracker::isRootInst(Instruction *I) {
- for (auto &DRS : RootSets) {
- if (is_contained(DRS.Roots, I))
- return true;
- }
- return false;
- }
- bool LoopReroll::DAGRootTracker::instrDependsOn(Instruction *I,
- UsesTy::iterator Start,
- UsesTy::iterator End) {
- for (auto *U : I->users()) {
- for (auto It = Start; It != End; ++It)
- if (U == It->first)
- return true;
- }
- return false;
- }
- static bool isIgnorableInst(const Instruction *I) {
- if (isa<DbgInfoIntrinsic>(I))
- return true;
- const IntrinsicInst* II = dyn_cast<IntrinsicInst>(I);
- if (!II)
- return false;
- switch (II->getIntrinsicID()) {
- default:
- return false;
- case Intrinsic::annotation:
- case Intrinsic::ptr_annotation:
- case Intrinsic::var_annotation:
-
-
- return true;
- }
- return false;
- }
- bool LoopReroll::DAGRootTracker::validate(ReductionTracker &Reductions) {
-
-
-
-
-
-
-
-
-
-
-
-
-
- SmallInstructionSet PossibleRedSet;
- SmallInstructionSet PossibleRedLastSet;
- SmallInstructionSet PossibleRedPHISet;
- Reductions.restrictToScale(Scale, PossibleRedSet,
- PossibleRedPHISet, PossibleRedLastSet);
-
- if (!collectUsedInstructions(PossibleRedSet))
- return false;
-
- for (auto *I : PossibleRedPHISet) {
- Uses[I].set(IL_All);
- }
-
-
- BasicBlock *Header = L->getHeader();
- if (LoopControlIV && LoopControlIV != IV) {
- for (auto *U : LoopControlIV->users()) {
- Instruction *IVUser = dyn_cast<Instruction>(U);
-
- Uses[IVUser].set(IL_All);
- for (auto *UU : IVUser->users()) {
- Instruction *UUser = dyn_cast<Instruction>(UU);
-
- Uses[UUser].set(IL_All);
-
- if (isa<SExtInst>(UUser)) {
- UUser = dyn_cast<Instruction>(*(UUser->user_begin()));
- Uses[UUser].set(IL_All);
- }
-
- if (UU->hasOneUse()) {
- Instruction *BI = dyn_cast<BranchInst>(*UUser->user_begin());
- if (BI == cast<BranchInst>(Header->getTerminator()))
- Uses[BI].set(IL_All);
- }
- }
- }
- }
-
-
- for (auto &KV : Uses) {
- if (KV.second.count() != 1 && !isIgnorableInst(KV.first)) {
- LLVM_DEBUG(
- dbgs() << "LRR: Aborting - instruction is not used in 1 iteration: "
- << *KV.first << " (#uses=" << KV.second.count() << ")\n");
- return false;
- }
- }
- LLVM_DEBUG(for (auto &KV
- : Uses) {
- dbgs() << "LRR: " << KV.second.find_first() << "\t" << *KV.first << "\n";
- });
- for (unsigned Iter = 1; Iter < Scale; ++Iter) {
-
-
-
-
- bool FutureSideEffects = false;
- AliasSetTracker AST(*AA);
-
- DenseMap<Value *, Value *> BaseMap;
-
- SmallInstructionSet Visited;
- auto BaseIt = nextInstr(0, Uses, Visited);
- auto RootIt = nextInstr(Iter, Uses, Visited);
- auto LastRootIt = Uses.begin();
- while (BaseIt != Uses.end() && RootIt != Uses.end()) {
- Instruction *BaseInst = BaseIt->first;
- Instruction *RootInst = RootIt->first;
-
- bool Continue = false;
- if (isBaseInst(BaseInst)) {
- Visited.insert(BaseInst);
- BaseIt = nextInstr(0, Uses, Visited);
- Continue = true;
- }
- if (isRootInst(RootInst)) {
- LastRootIt = RootIt;
- Visited.insert(RootInst);
- RootIt = nextInstr(Iter, Uses, Visited);
- Continue = true;
- }
- if (Continue) continue;
- if (!BaseInst->isSameOperationAs(RootInst)) {
-
-
-
-
-
-
-
-
-
-
- auto TryIt = RootIt;
- unsigned N = NumToleratedFailedMatches;
- while (TryIt != Uses.end() &&
- !BaseInst->isSameOperationAs(TryIt->first) &&
- N--) {
- ++TryIt;
- TryIt = nextInstr(Iter, Uses, Visited, &TryIt);
- }
- if (TryIt == Uses.end() || TryIt == RootIt ||
- instrDependsOn(TryIt->first, RootIt, TryIt)) {
- LLVM_DEBUG(dbgs() << "LRR: iteration root match failed at "
- << *BaseInst << " vs. " << *RootInst << "\n");
- return false;
- }
- RootIt = TryIt;
- RootInst = TryIt->first;
- }
-
-
-
-
-
-
-
-
- for (; LastRootIt < RootIt; ++LastRootIt) {
- Instruction *I = LastRootIt->first;
- if (LastRootIt->second.find_first() < (int)Iter)
- continue;
- if (I->mayWriteToMemory())
- AST.add(I);
-
-
-
-
- if (!isa<PHINode>(I) && !isUnorderedLoadStore(I) &&
- !isSafeToSpeculativelyExecute(I))
-
- FutureSideEffects = true;
- }
-
-
-
- if (RootIt->second.count() > 1) {
- LLVM_DEBUG(dbgs() << "LRR: iteration root match failed at " << *BaseInst
- << " vs. " << *RootInst << " (prev. case overlap)\n");
- return false;
- }
-
-
-
- if (RootInst->mayReadFromMemory())
- for (auto &K : AST) {
- if (K.aliasesUnknownInst(RootInst, *AA)) {
- LLVM_DEBUG(dbgs() << "LRR: iteration root match failed at "
- << *BaseInst << " vs. " << *RootInst
- << " (depends on future store)\n");
- return false;
- }
- }
-
-
-
-
- if (FutureSideEffects && ((!isUnorderedLoadStore(BaseInst) &&
- !isSafeToSpeculativelyExecute(BaseInst)) ||
- (!isUnorderedLoadStore(RootInst) &&
- !isSafeToSpeculativelyExecute(RootInst)))) {
- LLVM_DEBUG(dbgs() << "LRR: iteration root match failed at " << *BaseInst
- << " vs. " << *RootInst
- << " (side effects prevent reordering)\n");
- return false;
- }
-
-
-
-
-
-
-
-
-
-
- bool InReduction = Reductions.isPairInSame(BaseInst, RootInst);
- if (!(InReduction && BaseInst->isAssociative())) {
- bool Swapped = false, SomeOpMatched = false;
- for (unsigned j = 0; j < BaseInst->getNumOperands(); ++j) {
- Value *Op2 = RootInst->getOperand(j);
-
-
-
- if (InReduction)
- if (Instruction *Op2I = dyn_cast<Instruction>(Op2))
- if (Reductions.isPairInSame(RootInst, Op2I))
- continue;
- DenseMap<Value *, Value *>::iterator BMI = BaseMap.find(Op2);
- if (BMI != BaseMap.end()) {
- Op2 = BMI->second;
- } else {
- for (auto &DRS : RootSets) {
- if (DRS.Roots[Iter-1] == (Instruction*) Op2) {
- Op2 = DRS.BaseInst;
- break;
- }
- }
- }
- if (BaseInst->getOperand(Swapped ? unsigned(!j) : j) != Op2) {
-
-
-
-
-
- if (!Swapped && BaseInst->isCommutative() && !SomeOpMatched &&
- BaseInst->getOperand(!j) == Op2) {
- Swapped = true;
- } else {
- LLVM_DEBUG(dbgs()
- << "LRR: iteration root match failed at " << *BaseInst
- << " vs. " << *RootInst << " (operand " << j << ")\n");
- return false;
- }
- }
- SomeOpMatched = true;
- }
- }
- if ((!PossibleRedLastSet.count(BaseInst) &&
- hasUsesOutsideLoop(BaseInst, L)) ||
- (!PossibleRedLastSet.count(RootInst) &&
- hasUsesOutsideLoop(RootInst, L))) {
- LLVM_DEBUG(dbgs() << "LRR: iteration root match failed at " << *BaseInst
- << " vs. " << *RootInst << " (uses outside loop)\n");
- return false;
- }
- Reductions.recordPair(BaseInst, RootInst, Iter);
- BaseMap.insert(std::make_pair(RootInst, BaseInst));
- LastRootIt = RootIt;
- Visited.insert(BaseInst);
- Visited.insert(RootInst);
- BaseIt = nextInstr(0, Uses, Visited);
- RootIt = nextInstr(Iter, Uses, Visited);
- }
- assert(BaseIt == Uses.end() && RootIt == Uses.end() &&
- "Mismatched set sizes!");
- }
- LLVM_DEBUG(dbgs() << "LRR: Matched all iteration increments for " << *IV
- << "\n");
- return true;
- }
- void LoopReroll::DAGRootTracker::replace(const SCEV *BackedgeTakenCount) {
- BasicBlock *Header = L->getHeader();
-
-
- SmallVector<const SCEV *, 8> StartExprs;
- SmallVector<const SCEV *, 8> IncrExprs;
- for (auto &DRS : RootSets) {
- const SCEVAddRecExpr *IVSCEV =
- cast<SCEVAddRecExpr>(SE->getSCEV(DRS.BaseInst));
- StartExprs.push_back(IVSCEV->getStart());
- IncrExprs.push_back(SE->getMinusSCEV(SE->getSCEV(DRS.Roots[0]), IVSCEV));
- }
-
- for (Instruction &Inst : llvm::make_early_inc_range(llvm::reverse(*Header))) {
- unsigned I = Uses[&Inst].find_first();
- if (I > 0 && I < IL_All) {
- LLVM_DEBUG(dbgs() << "LRR: removing: " << Inst << "\n");
- Inst.eraseFromParent();
- }
- }
-
- for (size_t i = 0, e = RootSets.size(); i != e; ++i)
-
- replaceIV(RootSets[i], StartExprs[i], IncrExprs[i]);
- {
- BranchInst *BI = cast<BranchInst>(Header->getTerminator());
- const DataLayout &DL = Header->getModule()->getDataLayout();
- SCEVExpander Expander(*SE, DL, "reroll");
- auto Zero = SE->getZero(BackedgeTakenCount->getType());
- auto One = SE->getOne(BackedgeTakenCount->getType());
- auto NewIVSCEV = SE->getAddRecExpr(Zero, One, L, SCEV::FlagAnyWrap);
- Value *NewIV =
- Expander.expandCodeFor(NewIVSCEV, BackedgeTakenCount->getType(),
- Header->getFirstNonPHIOrDbg());
-
- auto TripCount = SE->getAddExpr(BackedgeTakenCount, One);
- auto ScaledTripCount = SE->getMulExpr(
- TripCount, SE->getConstant(BackedgeTakenCount->getType(), Scale));
- auto ScaledBECount = SE->getMinusSCEV(ScaledTripCount, One);
- Value *TakenCount =
- Expander.expandCodeFor(ScaledBECount, BackedgeTakenCount->getType(),
- Header->getFirstNonPHIOrDbg());
- Value *Cond =
- new ICmpInst(BI, CmpInst::ICMP_EQ, NewIV, TakenCount, "exitcond");
- BI->setCondition(Cond);
- if (BI->getSuccessor(1) != Header)
- BI->swapSuccessors();
- }
- SimplifyInstructionsInBlock(Header, TLI);
- DeleteDeadPHIs(Header, TLI);
- }
- void LoopReroll::DAGRootTracker::replaceIV(DAGRootSet &DRS,
- const SCEV *Start,
- const SCEV *IncrExpr) {
- BasicBlock *Header = L->getHeader();
- Instruction *Inst = DRS.BaseInst;
- const SCEV *NewIVSCEV =
- SE->getAddRecExpr(Start, IncrExpr, L, SCEV::FlagAnyWrap);
- {
- const DataLayout &DL = Header->getModule()->getDataLayout();
- SCEVExpander Expander(*SE, DL, "reroll");
- Value *NewIV = Expander.expandCodeFor(NewIVSCEV, Inst->getType(),
- Header->getFirstNonPHIOrDbg());
- for (auto &KV : Uses)
- if (KV.second.find_first() == 0)
- KV.first->replaceUsesOfWith(Inst, NewIV);
- }
- }
- bool LoopReroll::ReductionTracker::validateSelected() {
-
- for (int i : Reds) {
- int PrevIter = 0, BaseCount = 0, Count = 0;
- for (Instruction *J : PossibleReds[i]) {
-
-
-
- int Iter = PossibleRedIter[J];
- if (Iter != PrevIter && Iter != PrevIter + 1 &&
- !PossibleReds[i].getReducedValue()->isAssociative()) {
- LLVM_DEBUG(dbgs() << "LRR: Out-of-order non-associative reduction: "
- << J << "\n");
- return false;
- }
- if (Iter != PrevIter) {
- if (Count != BaseCount) {
- LLVM_DEBUG(dbgs()
- << "LRR: Iteration " << PrevIter << " reduction use count "
- << Count << " is not equal to the base use count "
- << BaseCount << "\n");
- return false;
- }
- Count = 0;
- }
- ++Count;
- if (Iter == 0)
- ++BaseCount;
- PrevIter = Iter;
- }
- }
- return true;
- }
- void LoopReroll::ReductionTracker::replaceSelected() {
-
-
- for (int i : Reds) {
- int j = 0;
- for (int e = PossibleReds[i].size(); j != e; ++j)
- if (PossibleRedIter[PossibleReds[i][j]] != 0) {
- --j;
- break;
- }
-
- SmallInstructionVector Users;
- for (User *U : PossibleReds[i].getReducedValue()->users()) {
- Users.push_back(cast<Instruction>(U));
- }
- for (Instruction *User : Users)
- User->replaceUsesOfWith(PossibleReds[i].getReducedValue(),
- PossibleReds[i][j]);
- }
- }
- bool LoopReroll::reroll(Instruction *IV, Loop *L, BasicBlock *Header,
- const SCEV *BackedgeTakenCount,
- ReductionTracker &Reductions) {
- DAGRootTracker DAGRoots(this, L, IV, SE, AA, TLI, DT, LI, PreserveLCSSA,
- IVToIncMap, LoopControlIV);
- if (!DAGRoots.findRoots())
- return false;
- LLVM_DEBUG(dbgs() << "LRR: Found all root induction increments for: " << *IV
- << "\n");
- if (!DAGRoots.validate(Reductions))
- return false;
- if (!Reductions.validateSelected())
- return false;
-
-
- Reductions.replaceSelected();
- DAGRoots.replace(BackedgeTakenCount);
- ++NumRerolledLoops;
- return true;
- }
- bool LoopReroll::runOnLoop(Loop *L) {
- BasicBlock *Header = L->getHeader();
- LLVM_DEBUG(dbgs() << "LRR: F[" << Header->getParent()->getName() << "] Loop %"
- << Header->getName() << " (" << L->getNumBlocks()
- << " block(s))\n");
-
- if (L->getNumBlocks() > 1)
- return false;
- if (!SE->hasLoopInvariantBackedgeTakenCount(L))
- return false;
- const SCEV *BackedgeTakenCount = SE->getBackedgeTakenCount(L);
- LLVM_DEBUG(dbgs() << "\n Before Reroll:\n" << *(L->getHeader()) << "\n");
- LLVM_DEBUG(dbgs() << "LRR: backedge-taken count = " << *BackedgeTakenCount
- << "\n");
-
-
- SmallInstructionVector PossibleIVs;
- IVToIncMap.clear();
- LoopControlIV = nullptr;
- collectPossibleIVs(L, PossibleIVs);
- if (PossibleIVs.empty()) {
- LLVM_DEBUG(dbgs() << "LRR: No possible IVs found\n");
- return false;
- }
- ReductionTracker Reductions;
- collectPossibleReductions(L, Reductions);
- bool Changed = false;
-
-
- for (Instruction *PossibleIV : PossibleIVs)
- if (reroll(PossibleIV, L, Header, BackedgeTakenCount, Reductions)) {
- Changed = true;
- break;
- }
- LLVM_DEBUG(dbgs() << "\n After Reroll:\n" << *(L->getHeader()) << "\n");
-
- if (Changed)
- SE->forgetLoop(L);
- return Changed;
- }
- bool LoopRerollLegacyPass::runOnLoop(Loop *L, LPPassManager &LPM) {
- if (skipLoop(L))
- return false;
- auto *AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
- auto *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
- auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
- auto *TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(
- *L->getHeader()->getParent());
- auto *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
- bool PreserveLCSSA = mustPreserveAnalysisID(LCSSAID);
- return LoopReroll(AA, LI, SE, TLI, DT, PreserveLCSSA).runOnLoop(L);
- }
- PreservedAnalyses LoopRerollPass::run(Loop &L, LoopAnalysisManager &AM,
- LoopStandardAnalysisResults &AR,
- LPMUpdater &U) {
- return LoopReroll(&AR.AA, &AR.LI, &AR.SE, &AR.TLI, &AR.DT, true).runOnLoop(&L)
- ? getLoopPassPreservedAnalyses()
- : PreservedAnalyses::all();
- }
|