From 5f255eb48f1a4b4c022ee28e46bc91fb4571e0c3 Mon Sep 17 00:00:00 2001 From: James Molloy Date: Thu, 29 Jan 2015 13:48:05 +0000 Subject: [PATCH] [LoopReroll] Refactor most of reroll() into a helper class reroll() was slightly monolithic and a pain to modify. Refactor a bunch of its state from local variables to member variables of a helper class, and do some trivial simplification while we're there. llvm-svn: 227439 --- llvm/lib/Transforms/Scalar/LoopRerollPass.cpp | 493 ++++++++++++++------------ 1 file changed, 273 insertions(+), 220 deletions(-) diff --git a/llvm/lib/Transforms/Scalar/LoopRerollPass.cpp b/llvm/lib/Transforms/Scalar/LoopRerollPass.cpp index a344de3..d105354 100644 --- a/llvm/lib/Transforms/Scalar/LoopRerollPass.cpp +++ b/llvm/lib/Transforms/Scalar/LoopRerollPass.cpp @@ -311,26 +311,72 @@ protected: DenseSet Reds; }; + // The set of all DAG roots, and state tracking of all roots + // for a particular induction variable. + struct DAGRootTracker { + DAGRootTracker(LoopReroll *Parent, Loop *L, Instruction *IV, + ScalarEvolution *SE, AliasAnalysis *AA, + TargetLibraryInfo *TLI, const DataLayout *DL) + : Parent(Parent), L(L), SE(SE), AA(AA), TLI(TLI), + DL(DL), IV(IV) { + } + + /// Stage 1: Find all the DAG roots for the induction variable. + bool findRoots(); + /// Stage 2: Validate if the found roots are valid. + bool validate(ReductionTracker &Reductions); + /// Stage 3: Assuming validate() returned true, perform the + /// replacement. + /// @param IterCount The maximum iteration count of L. + void replace(const SCEV *IterCount); + + protected: + bool findScaleFromMul(); + bool collectAllRoots(); + + void collectInLoopUserSet(const SmallInstructionVector &Roots, + const SmallInstructionSet &Exclude, + const SmallInstructionSet &Final, + DenseSet &Users); + void collectInLoopUserSet(Instruction *Root, + const SmallInstructionSet &Exclude, + const SmallInstructionSet &Final, + DenseSet &Users); + + LoopReroll *Parent; + + // Members of Parent, replicated here for brevity. + Loop *L; + ScalarEvolution *SE; + AliasAnalysis *AA; + TargetLibraryInfo *TLI; + const DataLayout *DL; + + // The loop induction variable. + Instruction *IV; + // Loop step amount. + uint64_t Inc; + // Loop reroll count; if Inc == 1, this records the scaling applied + // to the indvar: a[i*2+0] = ...; a[i*2+1] = ... ; + // If Inc is not 1, Scale = Inc. + uint64_t Scale; + // If Scale != Inc, then RealIV is IV after its multiplication. + Instruction *RealIV; + // The roots themselves. + SmallInstructionVector Roots; + // All increment instructions for IV. + SmallInstructionVector LoopIncs; + // All instructions transitively used by any root. + DenseSet AllRootUses; + // All instructions transitively used by the base. + DenseSet BaseUseSet; + // All instructions transitively used by the increments. + DenseSet LoopIncUseSet; + }; + void collectPossibleIVs(Loop *L, SmallInstructionVector &PossibleIVs); void collectPossibleReductions(Loop *L, ReductionTracker &Reductions); - void collectInLoopUserSet(Loop *L, - const SmallInstructionVector &Roots, - const SmallInstructionSet &Exclude, - const SmallInstructionSet &Final, - DenseSet &Users); - void collectInLoopUserSet(Loop *L, - Instruction * Root, - const SmallInstructionSet &Exclude, - const SmallInstructionSet &Final, - DenseSet &Users); - bool findScaleFromMul(Instruction *RealIV, uint64_t &Scale, - Instruction *&IV, - SmallInstructionVector &LoopIncs); - bool collectAllRoots(Loop *L, uint64_t Inc, uint64_t Scale, Instruction *IV, - SmallVector &Roots, - SmallInstructionSet &AllRoots, - SmallInstructionVector &LoopIncs); bool reroll(Instruction *IV, Loop *L, BasicBlock *Header, const SCEV *IterCount, ReductionTracker &Reductions); }; @@ -467,7 +513,7 @@ void LoopReroll::collectPossibleReductions(Loop *L, // if they are users, but their users are not added. This is used, for // example, to prevent a reduction update from forcing all later reduction // updates into the use set. -void LoopReroll::collectInLoopUserSet(Loop *L, +void LoopReroll::DAGRootTracker::collectInLoopUserSet( Instruction *Root, const SmallInstructionSet &Exclude, const SmallInstructionSet &Final, DenseSet &Users) { @@ -504,14 +550,14 @@ void LoopReroll::collectInLoopUserSet(Loop *L, // Collect all of the users of all of the provided root instructions (combined // into a single set). -void LoopReroll::collectInLoopUserSet(Loop *L, +void LoopReroll::DAGRootTracker::collectInLoopUserSet( const SmallInstructionVector &Roots, const SmallInstructionSet &Exclude, const SmallInstructionSet &Final, DenseSet &Users) { for (SmallInstructionVector::const_iterator I = Roots.begin(), IE = Roots.end(); I != IE; ++I) - collectInLoopUserSet(L, *I, Exclude, Final, Users); + collectInLoopUserSet(*I, Exclude, Final, Users); } static bool isSimpleLoadStore(Instruction *I) { @@ -524,6 +570,31 @@ static bool isSimpleLoadStore(Instruction *I) { return false; } +bool LoopReroll::DAGRootTracker::findRoots() { + + const SCEVAddRecExpr *RealIVSCEV = cast(SE->getSCEV(IV)); + Inc = cast(RealIVSCEV->getOperand(1))-> + getValue()->getZExtValue(); + + // The effective induction variable, IV, is normally also the real induction + // variable. When we're dealing with a loop like: + // for (int i = 0; i < 500; ++i) + // x[3*i] = ...; + // x[3*i+1] = ...; + // x[3*i+2] = ...; + // then the real IV is still i, but the effective IV is (3*i). + Scale = Inc; + RealIV = IV; + if (Inc == 1 && !findScaleFromMul()) + return false; + + // The set of increment instructions for each increment value. + if (!collectAllRoots()) + return false; + + return true; +} + // Recognize loops that are setup like this: // // %iv = phi [ (preheader, ...), (body, %iv.next) ] @@ -541,9 +612,8 @@ static bool isSimpleLoadStore(Instruction *I) { // br %cmp, header, exit // // and, if found, set IV = %scaled.iv, and add %iv.next to LoopIncs. -bool LoopReroll::findScaleFromMul(Instruction *RealIV, uint64_t &Scale, - Instruction *&IV, - SmallInstructionVector &LoopIncs) { +bool LoopReroll::DAGRootTracker::findScaleFromMul() { + // This is a special case: here we're looking for all uses (except for // the increment) to be multiplied by a common factor. The increment must // be by one. This is to capture loops like: @@ -596,6 +666,10 @@ bool LoopReroll::findScaleFromMul(Instruction *RealIV, uint64_t &Scale, return false; DEBUG(dbgs() << "LRR: Found possible scaling " << *User1 << "\n"); + + assert(Scale <= MaxInc && "Scale is too large"); + assert(Scale > 1 && "Scale must be at least 2"); + return true; } @@ -605,11 +679,9 @@ bool LoopReroll::findScaleFromMul(Instruction *RealIV, uint64_t &Scale, // rerollable loop, each of these increments is the root of an instruction // graph isomorphic to the others. Also, we collect the final induction // increment (the increment equal to the Scale), and its users in LoopIncs. -bool LoopReroll::collectAllRoots(Loop *L, uint64_t Inc, uint64_t Scale, - Instruction *IV, - SmallVector &Roots, - SmallInstructionSet &AllRoots, - SmallInstructionVector &LoopIncs) { +bool LoopReroll::DAGRootTracker::collectAllRoots() { + Roots.resize(Scale-1); + for (User *U : IV->users()) { Instruction *UI = cast(U); if (!SE->isSCEVable(UI->getType())) @@ -625,187 +697,26 @@ bool LoopReroll::collectAllRoots(Loop *L, uint64_t Inc, uint64_t Scale, SE->getSCEV(UI), SE->getSCEV(IV)))) { uint64_t Idx = Diff->getValue()->getValue().getZExtValue(); if (Idx > 0 && Idx < Scale) { - Roots[Idx-1].push_back(UI); - AllRoots.insert(UI); + if (Roots[Idx-1]) + // No duplicates allowed. + return false; + Roots[Idx-1] = UI; } else if (Idx == Scale && Inc > 1) { LoopIncs.push_back(UI); } } } - if (Roots[0].empty()) - return false; - bool AllSame = true; - for (unsigned i = 1; i < Scale-1; ++i) - if (Roots[i].size() != Roots[0].size()) { - AllSame = false; - break; - } - - if (!AllSame) - return false; - - return true; -} - -// Validate the selected reductions. All iterations must have an isomorphic -// part of the reduction chain and, for non-associative reductions, the chain -// entries must appear in order. -bool LoopReroll::ReductionTracker::validateSelected() { - // For a non-associative reduction, the chain entries must appear in order. - for (DenseSet::iterator RI = Reds.begin(), RIE = Reds.end(); - RI != RIE; ++RI) { - int i = *RI; - int PrevIter = 0, BaseCount = 0, Count = 0; - for (Instruction *J : PossibleReds[i]) { - // Note that all instructions in the chain must have been found because - // all instructions in the function must have been assigned to some - // iteration. - int Iter = PossibleRedIter[J]; - if (Iter != PrevIter && Iter != PrevIter + 1 && - !PossibleReds[i].getReducedValue()->isAssociative()) { - DEBUG(dbgs() << "LRR: Out-of-order non-associative reduction: " << - J << "\n"); - return false; - } - - if (Iter != PrevIter) { - if (Count != BaseCount) { - 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; - } + for (unsigned i = 0; i < Scale-1; ++i) { + if (!Roots[i]) + return false; } return true; } -// For all selected reductions, remove all parts except those in the first -// iteration (and the PHI). Replace outside uses of the reduced value with uses -// of the first-iteration reduced value (in other words, reroll the selected -// reductions). -void LoopReroll::ReductionTracker::replaceSelected() { - // Fixup reductions to refer to the last instruction associated with the - // first iteration (not the last). - for (DenseSet::iterator RI = Reds.begin(), RIE = Reds.end(); - RI != RIE; ++RI) { - int i = *RI; - int j = 0; - for (int e = PossibleReds[i].size(); j != e; ++j) - if (PossibleRedIter[PossibleReds[i][j]] != 0) { - --j; - break; - } - - // Replace users with the new end-of-chain value. - SmallInstructionVector Users; - for (User *U : PossibleReds[i].getReducedValue()->users()) - Users.push_back(cast(U)); - - for (SmallInstructionVector::iterator J = Users.begin(), - JE = Users.end(); J != JE; ++J) - (*J)->replaceUsesOfWith(PossibleReds[i].getReducedValue(), - PossibleReds[i][j]); - } -} - -// Reroll the provided loop with respect to the provided induction variable. -// Generally, we're looking for a loop like this: -// -// %iv = phi [ (preheader, ...), (body, %iv.next) ] -// f(%iv) -// %iv.1 = add %iv, 1 <-- a root increment -// f(%iv.1) -// %iv.2 = add %iv, 2 <-- a root increment -// f(%iv.2) -// %iv.scale_m_1 = add %iv, scale-1 <-- a root increment -// f(%iv.scale_m_1) -// ... -// %iv.next = add %iv, scale -// %cmp = icmp(%iv, ...) -// br %cmp, header, exit -// -// Notably, we do not require that f(%iv), f(%iv.1), etc. be isolated groups of -// instructions. In other words, the instructions in f(%iv), f(%iv.1), etc. can -// be intermixed with eachother. The restriction imposed by this algorithm is -// that the relative order of the isomorphic instructions in f(%iv), f(%iv.1), -// etc. be the same. -// -// First, we collect the use set of %iv, excluding the other increment roots. -// This gives us f(%iv). Then we iterate over the loop instructions (scale-1) -// times, having collected the use set of f(%iv.(i+1)), during which we: -// - Ensure that the next unmatched instruction in f(%iv) is isomorphic to -// the next unmatched instruction in f(%iv.(i+1)). -// - Ensure that both matched instructions don't have any external users -// (with the exception of last-in-chain reduction instructions). -// - Track the (aliasing) write set, and other side effects, of all -// instructions that belong to future iterations that come before the matched -// instructions. If the matched instructions read from that write set, then -// f(%iv) or f(%iv.(i+1)) has some dependency on instructions in -// f(%iv.(j+1)) for some j > i, and we cannot reroll the loop. Similarly, -// if any of these future instructions had side effects (could not be -// speculatively executed), and so do the matched instructions, when we -// cannot reorder those side-effect-producing instructions, and rerolling -// fails. -// -// Finally, we make sure that all loop instructions are either loop increment -// roots, belong to simple latch code, parts of validated reductions, part of -// f(%iv) or part of some f(%iv.i). If all of that is true (and all reductions -// have been validated), then we reroll the loop. -bool LoopReroll::reroll(Instruction *IV, Loop *L, BasicBlock *Header, - const SCEV *IterCount, - ReductionTracker &Reductions) { - const SCEVAddRecExpr *RealIVSCEV = cast(SE->getSCEV(IV)); - uint64_t Inc = cast(RealIVSCEV->getOperand(1))-> - getValue()->getZExtValue(); - // The collection of loop increment instructions. - SmallInstructionVector LoopIncs; - uint64_t Scale = Inc; - - // The effective induction variable, IV, is normally also the real induction - // variable. When we're dealing with a loop like: - // for (int i = 0; i < 500; ++i) - // x[3*i] = ...; - // x[3*i+1] = ...; - // x[3*i+2] = ...; - // then the real IV is still i, but the effective IV is (3*i). - Instruction *RealIV = IV; - if (Inc == 1 && !findScaleFromMul(RealIV, Scale, IV, LoopIncs)) - return false; - - assert(Scale <= MaxInc && "Scale is too large"); - assert(Scale > 1 && "Scale must be at least 2"); - - // The set of increment instructions for each increment value. - SmallVector Roots(Scale-1); - SmallInstructionSet AllRoots; - if (!collectAllRoots(L, Inc, Scale, IV, Roots, AllRoots, LoopIncs)) - return false; - - DEBUG(dbgs() << "LRR: Found all root induction increments for: " << - *RealIV << "\n"); - - // An array of just the possible reductions for this scale factor. When we - // collect the set of all users of some root instructions, these reduction - // instructions are treated as 'final' (their uses are not considered). - // This is important because we don't want the root use set to search down - // the reduction chain. - SmallInstructionSet PossibleRedSet; - SmallInstructionSet PossibleRedLastSet, PossibleRedPHISet; - Reductions.restrictToScale(Scale, PossibleRedSet, PossibleRedPHISet, - PossibleRedLastSet); +bool LoopReroll::DAGRootTracker::validate(ReductionTracker &Reductions) { + BasicBlock *Header = L->getHeader(); // We now need to check for equivalence of the use graph of each root with // that of the primary induction variable (excluding the roots). Our goal @@ -815,19 +726,30 @@ bool LoopReroll::reroll(Instruction *IV, Loop *L, BasicBlock *Header, // is the same (although we will not make an assumption about how the // different iterations are intermixed). Note that while the order must be // the same, the instructions may not be in the same basic block. - SmallInstructionSet Exclude(AllRoots); + SmallInstructionSet Exclude; + Exclude.insert(Roots.begin(), Roots.end()); Exclude.insert(LoopIncs.begin(), LoopIncs.end()); - DenseSet BaseUseSet; - collectInLoopUserSet(L, IV, Exclude, PossibleRedSet, BaseUseSet); + // An array of just the possible reductions for this scale factor. When we + // collect the set of all users of some root instructions, these reduction + // instructions are treated as 'final' (their uses are not considered). + // This is important because we don't want the root use set to search down + // the reduction chain. + SmallInstructionSet PossibleRedSet; + SmallInstructionSet PossibleRedLastSet; + SmallInstructionSet PossibleRedPHISet; + Reductions.restrictToScale(Scale, PossibleRedSet, + PossibleRedPHISet, PossibleRedLastSet); + + + collectInLoopUserSet(IV, Exclude, PossibleRedSet, BaseUseSet); - DenseSet AllRootUses; std::vector > RootUseSets(Scale-1); bool MatchFailed = false; for (unsigned i = 0; i < Scale-1 && !MatchFailed; ++i) { DenseSet &RootUseSet = RootUseSets[i]; - collectInLoopUserSet(L, Roots[i], SmallInstructionSet(), + collectInLoopUserSet(Roots[i], SmallInstructionSet(), PossibleRedSet, RootUseSet); DEBUG(dbgs() << "LRR: base use set size: " << BaseUseSet.size() << @@ -861,9 +783,7 @@ bool LoopReroll::reroll(Instruction *IV, Loop *L, BasicBlock *Header, if (PossibleRedPHISet.count(J1)) // Skip reduction PHIs. continue; - while (J2 != JE && (!RootUseSet.count(J2) || - std::find(Roots[i].begin(), Roots[i].end(), J2) != - Roots[i].end())) { + while (J2 != JE && (!RootUseSet.count(J2) || Roots[i] == J2)) { // As we iterate through the instructions, instructions that don't // belong to previous iterations (or the base case), must belong to // future iterations. We want to track the alias set of writes from @@ -960,8 +880,7 @@ bool LoopReroll::reroll(Instruction *IV, Loop *L, BasicBlock *Header, DenseMap::iterator BMI = BaseMap.find(Op2); if (BMI != BaseMap.end()) Op2 = BMI->second; - else if (std::find(Roots[i].begin(), Roots[i].end(), - (Instruction*) Op2) != Roots[i].end()) + else if (Roots[i] == (Instruction*) Op2) Op2 = IV; if (J1->getOperand(Swapped ? unsigned(!j) : j) != Op2) { @@ -1009,8 +928,7 @@ bool LoopReroll::reroll(Instruction *IV, Loop *L, BasicBlock *Header, DEBUG(dbgs() << "LRR: Matched all iteration increments for " << *RealIV << "\n"); - DenseSet LoopIncUseSet; - collectInLoopUserSet(L, LoopIncs, SmallInstructionSet(), + collectInLoopUserSet(LoopIncs, SmallInstructionSet(), SmallInstructionSet(), LoopIncUseSet); DEBUG(dbgs() << "LRR: Loop increment set size: " << LoopIncUseSet.size() << "\n"); @@ -1030,7 +948,7 @@ bool LoopReroll::reroll(Instruction *IV, Loop *L, BasicBlock *Header, isSafeToSpeculativelyExecute(J, DL)))) continue; - if (AllRoots.count(J)) + if (std::find(Roots.begin(), Roots.end(), J) != Roots.end()) continue; if (Reductions.isSelectedPHI(J)) @@ -1047,15 +965,11 @@ bool LoopReroll::reroll(Instruction *IV, Loop *L, BasicBlock *Header, DEBUG(dbgs() << "LRR: all instructions processed from " << *RealIV << "\n"); + return true; +} - if (!Reductions.validateSelected()) - return false; - - // At this point, we've validated the rerolling, and we're committed to - // making changes! - - Reductions.replaceSelected(); - +void LoopReroll::DAGRootTracker::replace(const SCEV *IterCount) { + BasicBlock *Header = L->getHeader(); // Remove instructions associated with non-base iterations. for (BasicBlock::reverse_iterator J = Header->rbegin(); J != Header->rend();) { @@ -1070,6 +984,7 @@ bool LoopReroll::reroll(Instruction *IV, Loop *L, BasicBlock *Header, } // Insert the new induction variable. + const SCEVAddRecExpr *RealIVSCEV = cast(SE->getSCEV(RealIV)); const SCEV *Start = RealIVSCEV->getStart(); if (Inc == 1) Start = SE->getMulExpr(Start, @@ -1102,7 +1017,7 @@ bool LoopReroll::reroll(Instruction *IV, Loop *L, BasicBlock *Header, } else { BasicBlock *Preheader = L->getLoopPreheader(); if (!Preheader) - Preheader = InsertPreheaderForLoop(L, this); + Preheader = InsertPreheaderForLoop(L, Parent); ICMinus1 = Expander.expandCodeFor(ICMinus1SCEV, NewIV->getType(), Preheader->getTerminator()); @@ -1120,6 +1035,144 @@ bool LoopReroll::reroll(Instruction *IV, Loop *L, BasicBlock *Header, SimplifyInstructionsInBlock(Header, DL, TLI); DeleteDeadPHIs(Header, TLI); +} + +// Validate the selected reductions. All iterations must have an isomorphic +// part of the reduction chain and, for non-associative reductions, the chain +// entries must appear in order. +bool LoopReroll::ReductionTracker::validateSelected() { + // For a non-associative reduction, the chain entries must appear in order. + for (DenseSet::iterator RI = Reds.begin(), RIE = Reds.end(); + RI != RIE; ++RI) { + int i = *RI; + int PrevIter = 0, BaseCount = 0, Count = 0; + for (Instruction *J : PossibleReds[i]) { + // Note that all instructions in the chain must have been found because + // all instructions in the function must have been assigned to some + // iteration. + int Iter = PossibleRedIter[J]; + if (Iter != PrevIter && Iter != PrevIter + 1 && + !PossibleReds[i].getReducedValue()->isAssociative()) { + DEBUG(dbgs() << "LRR: Out-of-order non-associative reduction: " << + J << "\n"); + return false; + } + + if (Iter != PrevIter) { + if (Count != BaseCount) { + 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; +} + +// For all selected reductions, remove all parts except those in the first +// iteration (and the PHI). Replace outside uses of the reduced value with uses +// of the first-iteration reduced value (in other words, reroll the selected +// reductions). +void LoopReroll::ReductionTracker::replaceSelected() { + // Fixup reductions to refer to the last instruction associated with the + // first iteration (not the last). + for (DenseSet::iterator RI = Reds.begin(), RIE = Reds.end(); + RI != RIE; ++RI) { + int i = *RI; + int j = 0; + for (int e = PossibleReds[i].size(); j != e; ++j) + if (PossibleRedIter[PossibleReds[i][j]] != 0) { + --j; + break; + } + + // Replace users with the new end-of-chain value. + SmallInstructionVector Users; + for (User *U : PossibleReds[i].getReducedValue()->users()) + Users.push_back(cast(U)); + + for (SmallInstructionVector::iterator J = Users.begin(), + JE = Users.end(); J != JE; ++J) + (*J)->replaceUsesOfWith(PossibleReds[i].getReducedValue(), + PossibleReds[i][j]); + } +} + +// Reroll the provided loop with respect to the provided induction variable. +// Generally, we're looking for a loop like this: +// +// %iv = phi [ (preheader, ...), (body, %iv.next) ] +// f(%iv) +// %iv.1 = add %iv, 1 <-- a root increment +// f(%iv.1) +// %iv.2 = add %iv, 2 <-- a root increment +// f(%iv.2) +// %iv.scale_m_1 = add %iv, scale-1 <-- a root increment +// f(%iv.scale_m_1) +// ... +// %iv.next = add %iv, scale +// %cmp = icmp(%iv, ...) +// br %cmp, header, exit +// +// Notably, we do not require that f(%iv), f(%iv.1), etc. be isolated groups of +// instructions. In other words, the instructions in f(%iv), f(%iv.1), etc. can +// be intermixed with eachother. The restriction imposed by this algorithm is +// that the relative order of the isomorphic instructions in f(%iv), f(%iv.1), +// etc. be the same. +// +// First, we collect the use set of %iv, excluding the other increment roots. +// This gives us f(%iv). Then we iterate over the loop instructions (scale-1) +// times, having collected the use set of f(%iv.(i+1)), during which we: +// - Ensure that the next unmatched instruction in f(%iv) is isomorphic to +// the next unmatched instruction in f(%iv.(i+1)). +// - Ensure that both matched instructions don't have any external users +// (with the exception of last-in-chain reduction instructions). +// - Track the (aliasing) write set, and other side effects, of all +// instructions that belong to future iterations that come before the matched +// instructions. If the matched instructions read from that write set, then +// f(%iv) or f(%iv.(i+1)) has some dependency on instructions in +// f(%iv.(j+1)) for some j > i, and we cannot reroll the loop. Similarly, +// if any of these future instructions had side effects (could not be +// speculatively executed), and so do the matched instructions, when we +// cannot reorder those side-effect-producing instructions, and rerolling +// fails. +// +// Finally, we make sure that all loop instructions are either loop increment +// roots, belong to simple latch code, parts of validated reductions, part of +// f(%iv) or part of some f(%iv.i). If all of that is true (and all reductions +// have been validated), then we reroll the loop. +bool LoopReroll::reroll(Instruction *IV, Loop *L, BasicBlock *Header, + const SCEV *IterCount, + ReductionTracker &Reductions) { + DAGRootTracker DAGRoots(this, L, IV, SE, AA, TLI, DL); + + if (!DAGRoots.findRoots()) + return false; + DEBUG(dbgs() << "LRR: Found all root induction increments for: " << + *IV << "\n"); + + if (!DAGRoots.validate(Reductions)) + return false; + if (!Reductions.validateSelected()) + return false; + // At this point, we've validated the rerolling, and we're committed to + // making changes! + + Reductions.replaceSelected(); + DAGRoots.replace(IterCount); + ++NumRerolledLoops; return true; } -- 2.7.4