X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FScalar%2FLoopInterchange.cpp;h=e296b710a6f3f167ecf1517f03df241c635b7c0b;hb=dabf510ba1b95298551a310c96e1ae1f681f816a;hp=6ded56e4eb94b0858f7f363b1d75cfad3f0267be;hpb=52610d84adc800a66eac48eb5fae487557f04751;p=oota-llvm.git diff --git a/lib/Transforms/Scalar/LoopInterchange.cpp b/lib/Transforms/Scalar/LoopInterchange.cpp index 6ded56e4eb9..e296b710a6f 100644 --- a/lib/Transforms/Scalar/LoopInterchange.cpp +++ b/lib/Transforms/Scalar/LoopInterchange.cpp @@ -28,18 +28,19 @@ #include "llvm/Analysis/ScalarEvolutionExpressions.h" #include "llvm/Analysis/TargetTransformInfo.h" #include "llvm/Analysis/ValueTracking.h" -#include "llvm/Transforms/Scalar.h" +#include "llvm/IR/Dominators.h" #include "llvm/IR/Function.h" #include "llvm/IR/IRBuilder.h" -#include "llvm/IR/IntrinsicInst.h" #include "llvm/IR/InstIterator.h" -#include "llvm/IR/Dominators.h" +#include "llvm/IR/IntrinsicInst.h" +#include "llvm/IR/Module.h" #include "llvm/Pass.h" #include "llvm/Support/Debug.h" -#include "llvm/Transforms/Utils/SSAUpdater.h" #include "llvm/Support/raw_ostream.h" -#include "llvm/Transforms/Utils/LoopUtils.h" +#include "llvm/Transforms/Scalar.h" #include "llvm/Transforms/Utils/BasicBlockUtils.h" +#include "llvm/Transforms/Utils/LoopUtils.h" +#include "llvm/Transforms/Utils/SSAUpdater.h" using namespace llvm; #define DEBUG_TYPE "loop-interchange" @@ -70,8 +71,8 @@ void printDepMatrix(CharMatrix &DepMatrix) { } #endif -bool populateDependencyMatrix(CharMatrix &DepMatrix, unsigned Level, Loop *L, - DependenceAnalysis *DA) { +static bool populateDependencyMatrix(CharMatrix &DepMatrix, unsigned Level, + Loop *L, DependenceAnalysis *DA) { typedef SmallVector ValueVector; ValueVector MemInstr; @@ -183,8 +184,8 @@ bool populateDependencyMatrix(CharMatrix &DepMatrix, unsigned Level, Loop *L, // A loop is moved from index 'from' to an index 'to'. Update the Dependence // matrix by exchanging the two columns. -void interChangeDepedencies(CharMatrix &DepMatrix, unsigned FromIndx, - unsigned ToIndx) { +static void interChangeDepedencies(CharMatrix &DepMatrix, unsigned FromIndx, + unsigned ToIndx) { unsigned numRows = DepMatrix.size(); for (unsigned i = 0; i < numRows; ++i) { char TmpVal = DepMatrix[i][ToIndx]; @@ -195,8 +196,8 @@ void interChangeDepedencies(CharMatrix &DepMatrix, unsigned FromIndx, // Checks if outermost non '=','S'or'I' dependence in the dependence matrix is // '>' -bool isOuterMostDepPositive(CharMatrix &DepMatrix, unsigned Row, - unsigned Column) { +static bool isOuterMostDepPositive(CharMatrix &DepMatrix, unsigned Row, + unsigned Column) { for (unsigned i = 0; i <= Column; ++i) { if (DepMatrix[Row][i] == '<') return false; @@ -208,8 +209,8 @@ bool isOuterMostDepPositive(CharMatrix &DepMatrix, unsigned Row, } // Checks if no dependence exist in the dependency matrix in Row before Column. -bool containsNoDependence(CharMatrix &DepMatrix, unsigned Row, - unsigned Column) { +static bool containsNoDependence(CharMatrix &DepMatrix, unsigned Row, + unsigned Column) { for (unsigned i = 0; i < Column; ++i) { if (DepMatrix[Row][i] != '=' || DepMatrix[Row][i] != 'S' || DepMatrix[Row][i] != 'I') @@ -218,8 +219,9 @@ bool containsNoDependence(CharMatrix &DepMatrix, unsigned Row, return true; } -bool validDepInterchange(CharMatrix &DepMatrix, unsigned Row, - unsigned OuterLoopId, char InnerDep, char OuterDep) { +static bool validDepInterchange(CharMatrix &DepMatrix, unsigned Row, + unsigned OuterLoopId, char InnerDep, + char OuterDep) { if (isOuterMostDepPositive(DepMatrix, Row, OuterLoopId)) return false; @@ -253,11 +255,13 @@ bool validDepInterchange(CharMatrix &DepMatrix, unsigned Row, } // Checks if it is legal to interchange 2 loops. -// [Theorm] A permutation of the loops in a perfect nest is legal if and only if +// [Theorem] A permutation of the loops in a perfect nest is legal if and only +// if // the direction matrix, after the same permutation is applied to its columns, // has no ">" direction as the leftmost non-"=" direction in any row. -bool isLegalToInterChangeLoops(CharMatrix &DepMatrix, unsigned InnerLoopId, - unsigned OuterLoopId) { +static bool isLegalToInterChangeLoops(CharMatrix &DepMatrix, + unsigned InnerLoopId, + unsigned OuterLoopId) { unsigned NumRows = DepMatrix.size(); // For each row check if it is valid to interchange. @@ -278,21 +282,21 @@ static void populateWorklist(Loop &L, SmallVector &V) { DEBUG(dbgs() << "Calling populateWorklist called\n"); LoopVector LoopList; Loop *CurrentLoop = &L; - std::vector vec = CurrentLoop->getSubLoopsVector(); - while (vec.size() != 0) { + const std::vector *Vec = &CurrentLoop->getSubLoops(); + while (!Vec->empty()) { // The current loop has multiple subloops in it hence it is not tightly // nested. // Discard all loops above it added into Worklist. - if (vec.size() != 1) { + if (Vec->size() != 1) { LoopList.clear(); return; } LoopList.push_back(CurrentLoop); - CurrentLoop = *(vec.begin()); - vec = CurrentLoop->getSubLoopsVector(); + CurrentLoop = Vec->front(); + Vec = &CurrentLoop->getSubLoops(); } LoopList.push_back(CurrentLoop); - V.push_back(LoopList); + V.push_back(std::move(LoopList)); } static PHINode *getInductionVariable(Loop *L, ScalarEvolution *SE) { @@ -328,7 +332,8 @@ class LoopInterchangeLegality { public: LoopInterchangeLegality(Loop *Outer, Loop *Inner, ScalarEvolution *SE, LoopInterchange *Pass) - : OuterLoop(Outer), InnerLoop(Inner), SE(SE), CurrentPass(Pass) {} + : OuterLoop(Outer), InnerLoop(Inner), SE(SE), CurrentPass(Pass), + InnerLoopHasReduction(false) {} /// Check if the loops can be interchanged. bool canInterchangeLoops(unsigned InnerLoopId, unsigned OuterLoopId, @@ -339,15 +344,24 @@ public: bool currentLimitations(); + bool hasInnerLoopReduction() { return InnerLoopHasReduction; } + private: bool tightlyNested(Loop *Outer, Loop *Inner); - + bool containsUnsafeInstructionsInHeader(BasicBlock *BB); + bool areAllUsesReductions(Instruction *Ins, Loop *L); + bool containsUnsafeInstructionsInLatch(BasicBlock *BB); + bool findInductionAndReductions(Loop *L, + SmallVector &Inductions, + SmallVector &Reductions); Loop *OuterLoop; Loop *InnerLoop; /// Scev analysis. ScalarEvolution *SE; LoopInterchange *CurrentPass; + + bool InnerLoopHasReduction; }; /// LoopInterchangeProfitability checks if it is profitable to interchange the @@ -376,17 +390,16 @@ class LoopInterchangeTransform { public: LoopInterchangeTransform(Loop *Outer, Loop *Inner, ScalarEvolution *SE, LoopInfo *LI, DominatorTree *DT, - LoopInterchange *Pass, BasicBlock *LoopNestExit) + LoopInterchange *Pass, BasicBlock *LoopNestExit, + bool InnerLoopContainsReductions) : OuterLoop(Outer), InnerLoop(Inner), SE(SE), LI(LI), DT(DT), - LoopExit(LoopNestExit) { - initialize(); - } + LoopExit(LoopNestExit), + InnerLoopHasReduction(InnerLoopContainsReductions) {} /// Interchange OuterLoop and InnerLoop. bool transform(); void restructureLoops(Loop *InnerLoop, Loop *OuterLoop); void removeChildLoop(Loop *OuterLoop, Loop *InnerLoop); - void initialize(); private: void splitInnerLoopLatch(Instruction *); @@ -397,6 +410,8 @@ private: void adjustOuterLoopPreheader(); void adjustInnerLoopPreheader(); bool adjustLoopBranches(); + void updateIncomingBlock(BasicBlock *CurrBlock, BasicBlock *OldPred, + BasicBlock *NewPred); Loop *OuterLoop; Loop *InnerLoop; @@ -406,6 +421,7 @@ private: LoopInfo *LI; DominatorTree *DT; BasicBlock *LoopExit; + bool InnerLoopHasReduction; }; // Main LoopInterchange Pass @@ -421,8 +437,8 @@ struct LoopInterchange : public FunctionPass { } void getAnalysisUsage(AnalysisUsage &AU) const override { - AU.addRequired(); - AU.addRequired(); + AU.addRequired(); + AU.addRequired(); AU.addRequired(); AU.addRequired(); AU.addRequired(); @@ -431,7 +447,7 @@ struct LoopInterchange : public FunctionPass { } bool runOnFunction(Function &F) override { - SE = &getAnalysis(); + SE = &getAnalysis().getSE(); LI = &getAnalysis().getLoopInfo(); DA = &getAnalysis(); auto *DTWP = getAnalysisIfAvailable(); @@ -446,7 +462,7 @@ struct LoopInterchange : public FunctionPass { bool Changed = true; while (!Worklist.empty()) { LoopVector LoopList = Worklist.pop_back_val(); - Changed = processLoopList(LoopList); + Changed = processLoopList(LoopList, F); } return Changed; } @@ -473,13 +489,13 @@ struct LoopInterchange : public FunctionPass { unsigned selectLoopForInterchange(LoopVector LoopList) { // TODO: Add a better heuristic to select the loop to be interchanged based - // on the dependece matrix. Currently we select the innermost loop. + // on the dependence matrix. Currently we select the innermost loop. return LoopList.size() - 1; } - bool processLoopList(LoopVector LoopList) { + bool processLoopList(LoopVector LoopList, Function &F) { + bool Changed = false; - bool containsLCSSAPHI = false; CharMatrix DependencyMatrix; if (LoopList.size() < 2) { DEBUG(dbgs() << "Loop doesn't contain minimum nesting level.\n"); @@ -521,37 +537,25 @@ struct LoopInterchange : public FunctionPass { else LoopNestExit = OuterMostLoopLatchBI->getSuccessor(0); - for (auto I = LoopList.begin(), E = LoopList.end(); I != E; ++I) { - Loop *L = *I; - BasicBlock *Latch = L->getLoopLatch(); - BasicBlock *Header = L->getHeader(); - if (Latch && Latch != Header && isa(Latch->begin())) { - containsLCSSAPHI = true; - break; - } - } - - // TODO: Handle lcssa PHI's. Currently LCSSA PHI's are not handled. Handle - // the same by splitting the loop latch and adjusting loop links - // accordingly. - if (containsLCSSAPHI) + if (isa(LoopNestExit->begin())) { + DEBUG(dbgs() << "PHI Nodes in loop nest exit is not handled for now " + "since on failure all loops branch to loop nest exit.\n"); return false; + } unsigned SelecLoopId = selectLoopForInterchange(LoopList); - // Move the selected loop outwards to the best posible position. + // Move the selected loop outwards to the best possible position. for (unsigned i = SelecLoopId; i > 0; i--) { bool Interchanged = processLoop(LoopList, i, i - 1, LoopNestExit, DependencyMatrix); if (!Interchanged) return Changed; // Loops interchanged reflect the same in LoopList - Loop *OldOuterLoop = LoopList[i - 1]; - LoopList[i - 1] = LoopList[i]; - LoopList[i] = OldOuterLoop; + std::swap(LoopList[i - 1], LoopList[i]); // Update the DependencyMatrix interChangeDepedencies(DependencyMatrix, i, i - 1); - + DT->recalculate(F); #ifdef DUMP_DEP_MATRICIES DEBUG(dbgs() << "Dependence after inter change \n"); printDepMatrix(DependencyMatrix); @@ -583,7 +587,7 @@ struct LoopInterchange : public FunctionPass { } LoopInterchangeTransform LIT(OuterLoop, InnerLoop, SE, LI, DT, this, - LoopNestExit); + LoopNestExit, LIL.hasInnerLoopReduction()); LIT.transform(); DEBUG(dbgs() << "Loops interchanged\n"); return true; @@ -591,10 +595,38 @@ struct LoopInterchange : public FunctionPass { }; } // end of namespace +bool LoopInterchangeLegality::areAllUsesReductions(Instruction *Ins, Loop *L) { + return !std::any_of(Ins->user_begin(), Ins->user_end(), [=](User *U) -> bool { + PHINode *UserIns = dyn_cast(U); + RecurrenceDescriptor RD; + return !UserIns || !RecurrenceDescriptor::isReductionPHI(UserIns, L, RD); + }); +} + +bool LoopInterchangeLegality::containsUnsafeInstructionsInHeader( + BasicBlock *BB) { + for (auto I = BB->begin(), E = BB->end(); I != E; ++I) { + // Load corresponding to reduction PHI's are safe while concluding if + // tightly nested. + if (LoadInst *L = dyn_cast(I)) { + if (!areAllUsesReductions(L, InnerLoop)) + return true; + } else if (I->mayHaveSideEffects() || I->mayReadFromMemory()) + return true; + } + return false; +} -static bool containsUnsafeInstructions(BasicBlock *BB) { +bool LoopInterchangeLegality::containsUnsafeInstructionsInLatch( + BasicBlock *BB) { for (auto I = BB->begin(), E = BB->end(); I != E; ++I) { - if (I->mayHaveSideEffects() || I->mayReadFromMemory()) + // Stores corresponding to reductions are safe while concluding if tightly + // nested. + if (StoreInst *L = dyn_cast(I)) { + PHINode *PHI = dyn_cast(L->getOperand(0)); + if (!PHI) + return true; + } else if (I->mayHaveSideEffects() || I->mayReadFromMemory()) return true; } return false; @@ -623,9 +655,9 @@ bool LoopInterchangeLegality::tightlyNested(Loop *OuterLoop, Loop *InnerLoop) { DEBUG(dbgs() << "Checking instructions in Loop header and Loop latch \n"); // We do not have any basic block in between now make sure the outer header - // and outer loop latch doesnt contain any unsafe instructions. - if (containsUnsafeInstructions(OuterLoopHeader) || - containsUnsafeInstructions(OuterLoopLatch)) + // and outer loop latch doesn't contain any unsafe instructions. + if (containsUnsafeInstructionsInHeader(OuterLoopHeader) || + containsUnsafeInstructionsInLatch(OuterLoopLatch)) return false; DEBUG(dbgs() << "Loops are perfectly nested \n"); @@ -633,12 +665,6 @@ bool LoopInterchangeLegality::tightlyNested(Loop *OuterLoop, Loop *InnerLoop) { return true; } -static unsigned getPHICount(BasicBlock *BB) { - unsigned PhiCount = 0; - for (auto I = BB->begin(); isa(I); ++I) - PhiCount++; - return PhiCount; -} bool LoopInterchangeLegality::isLoopStructureUnderstood( PHINode *InnerInduction) { @@ -665,34 +691,96 @@ bool LoopInterchangeLegality::isLoopStructureUnderstood( return true; } +bool LoopInterchangeLegality::findInductionAndReductions( + Loop *L, SmallVector &Inductions, + SmallVector &Reductions) { + if (!L->getLoopLatch() || !L->getLoopPredecessor()) + return false; + for (BasicBlock::iterator I = L->getHeader()->begin(); isa(I); ++I) { + RecurrenceDescriptor RD; + InductionDescriptor ID; + PHINode *PHI = cast(I); + if (InductionDescriptor::isInductionPHI(PHI, SE, ID)) + Inductions.push_back(PHI); + else if (RecurrenceDescriptor::isReductionPHI(PHI, L, RD)) + Reductions.push_back(PHI); + else { + DEBUG( + dbgs() << "Failed to recognize PHI as an induction or reduction.\n"); + return false; + } + } + return true; +} + +static bool containsSafePHI(BasicBlock *Block, bool isOuterLoopExitBlock) { + for (auto I = Block->begin(); isa(I); ++I) { + PHINode *PHI = cast(I); + // Reduction lcssa phi will have only 1 incoming block that from loop latch. + if (PHI->getNumIncomingValues() > 1) + return false; + Instruction *Ins = dyn_cast(PHI->getIncomingValue(0)); + if (!Ins) + return false; + // Incoming value for lcssa phi's in outer loop exit can only be inner loop + // exits lcssa phi else it would not be tightly nested. + if (!isa(Ins) && isOuterLoopExitBlock) + return false; + } + return true; +} + +static BasicBlock *getLoopLatchExitBlock(BasicBlock *LatchBlock, + BasicBlock *LoopHeader) { + if (BranchInst *BI = dyn_cast(LatchBlock->getTerminator())) { + unsigned Num = BI->getNumSuccessors(); + assert(Num == 2); + for (unsigned i = 0; i < Num; ++i) { + if (BI->getSuccessor(i) == LoopHeader) + continue; + return BI->getSuccessor(i); + } + } + return nullptr; +} + // This function indicates the current limitations in the transform as a result // of which we do not proceed. bool LoopInterchangeLegality::currentLimitations() { BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader(); BasicBlock *InnerLoopHeader = InnerLoop->getHeader(); - BasicBlock *OuterLoopHeader = OuterLoop->getHeader(); BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch(); BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch(); + BasicBlock *OuterLoopHeader = OuterLoop->getHeader(); PHINode *InnerInductionVar; - PHINode *OuterInductionVar; - - // We currently handle only 1 induction variable inside the loop. We also do - // not handle reductions as of now. - if (getPHICount(InnerLoopHeader) > 1) + SmallVector Inductions; + SmallVector Reductions; + if (!findInductionAndReductions(InnerLoop, Inductions, Reductions)) return true; - if (getPHICount(OuterLoopHeader) > 1) + // TODO: Currently we handle only loops with 1 induction variable. + if (Inductions.size() != 1) { + DEBUG(dbgs() << "We currently only support loops with 1 induction variable." + << "Failed to interchange due to current limitation\n"); return true; + } + if (Reductions.size() > 0) + InnerLoopHasReduction = true; - InnerInductionVar = getInductionVariable(InnerLoop, SE); - OuterInductionVar = getInductionVariable(OuterLoop, SE); + InnerInductionVar = Inductions.pop_back_val(); + Reductions.clear(); + if (!findInductionAndReductions(OuterLoop, Inductions, Reductions)) + return true; - if (!OuterInductionVar || !InnerInductionVar) { - DEBUG(dbgs() << "Induction variable not found\n"); + // Outer loop cannot have reduction because then loops will not be tightly + // nested. + if (!Reductions.empty()) + return true; + // TODO: Currently we handle only loops with 1 induction variable. + if (Inductions.size() != 1) return true; - } // TODO: Triangular loops are not handled for now. if (!isLoopStructureUnderstood(InnerInductionVar)) { @@ -700,16 +788,15 @@ bool LoopInterchangeLegality::currentLimitations() { return true; } - // TODO: Loops with LCSSA PHI's are currently not handled. - if (isa(OuterLoopLatch->begin())) { - DEBUG(dbgs() << "Found and LCSSA PHI in outer loop latch\n"); + // TODO: We only handle LCSSA PHI's corresponding to reduction for now. + BasicBlock *LoopExitBlock = + getLoopLatchExitBlock(OuterLoopLatch, OuterLoopHeader); + if (!LoopExitBlock || !containsSafePHI(LoopExitBlock, true)) return true; - } - if (InnerLoopLatch != InnerLoopHeader && - isa(InnerLoopLatch->begin())) { - DEBUG(dbgs() << "Found and LCSSA PHI in inner loop latch\n"); + + LoopExitBlock = getLoopLatchExitBlock(InnerLoopLatch, InnerLoopHeader); + if (!LoopExitBlock || !containsSafePHI(LoopExitBlock, false)) return true; - } // TODO: Current limitation: Since we split the inner loop latch at the point // were induction variable is incremented (induction.next); We cannot have @@ -749,7 +836,7 @@ bool LoopInterchangeLegality::currentLimitations() { else FoundInduction = true; } - // The loop latch ended and we didnt find the induction variable return as + // The loop latch ended and we didn't find the induction variable return as // current limitation. if (!FoundInduction) return true; @@ -788,12 +875,6 @@ bool LoopInterchangeLegality::canInterchangeLoops(unsigned InnerLoopId, InnerLoopPreHeader = InsertPreheaderForLoop(InnerLoop, CurrentPass); } - // Check if the loops are tightly nested. - if (!tightlyNested(OuterLoop, InnerLoop)) { - DEBUG(dbgs() << "Loops not tightly nested\n"); - return false; - } - // TODO: The loops could not be interchanged due to current limitations in the // transform module. if (currentLimitations()) { @@ -801,6 +882,12 @@ bool LoopInterchangeLegality::canInterchangeLoops(unsigned InnerLoopId, return false; } + // Check if the loops are tightly nested. + if (!tightlyNested(OuterLoop, InnerLoop)) { + DEBUG(dbgs() << "Loops not tightly nested\n"); + return false; + } + return true; } @@ -856,8 +943,9 @@ int LoopInterchangeProfitability::getInstrOrderCost() { return GoodOrder - BadOrder; } -bool isProfitabileForVectorization(unsigned InnerLoopId, unsigned OuterLoopId, - CharMatrix &DepMatrix) { +static bool isProfitabileForVectorization(unsigned InnerLoopId, + unsigned OuterLoopId, + CharMatrix &DepMatrix) { // TODO: Improve this heuristic to catch more cases. // If the inner loop is loop independent or doesn't carry any dependency it is // profitable to move this to outer position. @@ -878,7 +966,7 @@ bool LoopInterchangeProfitability::isProfitable(unsigned InnerLoopId, unsigned OuterLoopId, CharMatrix &DepMatrix) { - // TODO: Add Better Profitibility checks. + // TODO: Add better profitability checks. // e.g // 1) Construct dependency matrix and move the one with no loop carried dep // inside to enable vectorization. @@ -892,7 +980,7 @@ bool LoopInterchangeProfitability::isProfitable(unsigned InnerLoopId, if (Cost < 0) return true; - // It is not profitable as per current cache profitibility model. But check if + // It is not profitable as per current cache profitability model. But check if // we can move this loop outside to improve parallelism. bool ImprovesPar = isProfitabileForVectorization(InnerLoopId, OuterLoopId, DepMatrix); @@ -901,14 +989,16 @@ bool LoopInterchangeProfitability::isProfitable(unsigned InnerLoopId, void LoopInterchangeTransform::removeChildLoop(Loop *OuterLoop, Loop *InnerLoop) { - for (Loop::iterator I = OuterLoop->begin(), E = OuterLoop->end();; ++I) { - assert(I != E && "Couldn't find loop"); + for (Loop::iterator I = OuterLoop->begin(), E = OuterLoop->end(); I != E; + ++I) { if (*I == InnerLoop) { OuterLoop->removeChildLoop(I); return; } } + assert(false && "Couldn't find loop"); } + void LoopInterchangeTransform::restructureLoops(Loop *InnerLoop, Loop *OuterLoop) { Loop *OuterLoopParent = OuterLoop->getParentLoop(); @@ -922,8 +1012,8 @@ void LoopInterchangeTransform::restructureLoops(Loop *InnerLoop, LI->changeTopLevelLoop(OuterLoop, InnerLoop); } - for (Loop::iterator I = InnerLoop->begin(), E = InnerLoop->end(); I != E; ++I) - OuterLoop->addChildLoop(InnerLoop->removeChildLoop(I)); + while (!InnerLoop->empty()) + OuterLoop->addChildLoop(InnerLoop->removeChildLoop(InnerLoop->begin())); InnerLoop->addChildLoop(OuterLoop); } @@ -955,7 +1045,7 @@ bool LoopInterchangeTransform::transform() { splitInnerLoopLatch(InnerIndexVar); DEBUG(dbgs() << "splitInnerLoopLatch Done\n"); - // Splits the inner loops phi nodes out into a seperate basic block. + // Splits the inner loops phi nodes out into a separate basic block. splitInnerLoopHeader(); DEBUG(dbgs() << "splitInnerLoopHeader Done\n"); } @@ -970,20 +1060,10 @@ bool LoopInterchangeTransform::transform() { return true; } -void LoopInterchangeTransform::initialize() {} - -void LoopInterchangeTransform::splitInnerLoopLatch(Instruction *inc) { - +void LoopInterchangeTransform::splitInnerLoopLatch(Instruction *Inc) { BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch(); - BasicBlock::iterator I = InnerLoopLatch->begin(); - BasicBlock::iterator E = InnerLoopLatch->end(); - for (; I != E; ++I) { - if (inc == I) - break; - } - BasicBlock *InnerLoopLatchPred = InnerLoopLatch; - InnerLoopLatch = SplitBlock(InnerLoopLatchPred, I, DT, LI); + InnerLoopLatch = SplitBlock(InnerLoopLatchPred, Inc, DT, LI); } void LoopInterchangeTransform::splitOuterLoopLatch() { @@ -995,45 +1075,72 @@ void LoopInterchangeTransform::splitOuterLoopLatch() { void LoopInterchangeTransform::splitInnerLoopHeader() { - // Split the inner loop header out. + // Split the inner loop header out. Here make sure that the reduction PHI's + // stay in the innerloop body. BasicBlock *InnerLoopHeader = InnerLoop->getHeader(); - SplitBlock(InnerLoopHeader, InnerLoopHeader->getFirstNonPHI(), DT, LI); + BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader(); + if (InnerLoopHasReduction) { + // FIXME: Check if the induction PHI will always be the first PHI. + BasicBlock *New = InnerLoopHeader->splitBasicBlock( + ++(InnerLoopHeader->begin()), InnerLoopHeader->getName() + ".split"); + if (LI) + if (Loop *L = LI->getLoopFor(InnerLoopHeader)) + L->addBasicBlockToLoop(New, *LI); + + // Adjust Reduction PHI's in the block. + SmallVector PHIVec; + for (auto I = New->begin(); isa(I); ++I) { + PHINode *PHI = dyn_cast(I); + Value *V = PHI->getIncomingValueForBlock(InnerLoopPreHeader); + PHI->replaceAllUsesWith(V); + PHIVec.push_back((PHI)); + } + for (auto I = PHIVec.begin(), E = PHIVec.end(); I != E; ++I) { + PHINode *P = *I; + P->eraseFromParent(); + } + } else { + SplitBlock(InnerLoopHeader, InnerLoopHeader->getFirstNonPHI(), DT, LI); + } DEBUG(dbgs() << "Output of splitInnerLoopHeader InnerLoopHeaderSucc & " "InnerLoopHeader \n"); } +/// \brief Move all instructions except the terminator from FromBB right before +/// InsertBefore +static void moveBBContents(BasicBlock *FromBB, Instruction *InsertBefore) { + auto &ToList = InsertBefore->getParent()->getInstList(); + auto &FromList = FromBB->getInstList(); + + ToList.splice(InsertBefore, FromList, FromList.begin(), + FromBB->getTerminator()); +} + void LoopInterchangeTransform::adjustOuterLoopPreheader() { BasicBlock *OuterLoopPreHeader = OuterLoop->getLoopPreheader(); - SmallVector Inst; - for (auto I = OuterLoopPreHeader->begin(), E = OuterLoopPreHeader->end(); - I != E; ++I) { - if (isa(*I)) - break; - Inst.push_back(I); - } - BasicBlock *InnerPreHeader = InnerLoop->getLoopPreheader(); - for (auto I = Inst.begin(), E = Inst.end(); I != E; ++I) { - Instruction *Ins = cast(*I); - Ins->moveBefore(InnerPreHeader->getTerminator()); - } + + moveBBContents(OuterLoopPreHeader, InnerPreHeader->getTerminator()); } void LoopInterchangeTransform::adjustInnerLoopPreheader() { - BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader(); - SmallVector Inst; - for (auto I = InnerLoopPreHeader->begin(), E = InnerLoopPreHeader->end(); - I != E; ++I) { - if (isa(*I)) - break; - Inst.push_back(I); - } BasicBlock *OuterHeader = OuterLoop->getHeader(); - for (auto I = Inst.begin(), E = Inst.end(); I != E; ++I) { - Instruction *Ins = cast(*I); - Ins->moveBefore(OuterHeader->getTerminator()); + + moveBBContents(InnerLoopPreHeader, OuterHeader->getTerminator()); +} + +void LoopInterchangeTransform::updateIncomingBlock(BasicBlock *CurrBlock, + BasicBlock *OldPred, + BasicBlock *NewPred) { + for (auto I = CurrBlock->begin(); isa(I); ++I) { + PHINode *PHI = cast(I); + unsigned Num = PHI->getNumIncomingValues(); + for (unsigned i = 0; i < Num; ++i) { + if (PHI->getIncomingBlock(i) == OldPred) + PHI->setIncomingBlock(i, NewPred); + } } } @@ -1074,8 +1181,8 @@ bool LoopInterchangeTransform::adjustLoopBranches() { if (!OuterLoopPredecessorBI || !InnerLoopLatchPredecessorBI) return false; - BasicBlock *InnerLoopHeaderSucessor = InnerLoopHeader->getUniqueSuccessor(); - if (!InnerLoopHeaderSucessor) + BasicBlock *InnerLoopHeaderSuccessor = InnerLoopHeader->getUniqueSuccessor(); + if (!InnerLoopHeaderSuccessor) return false; // Adjust Loop Preheader and headers @@ -1091,9 +1198,13 @@ bool LoopInterchangeTransform::adjustLoopBranches() { if (OuterLoopHeaderBI->getSuccessor(i) == OuterLoopLatch) OuterLoopHeaderBI->setSuccessor(i, LoopExit); else if (OuterLoopHeaderBI->getSuccessor(i) == InnerLoopPreHeader) - OuterLoopHeaderBI->setSuccessor(i, InnerLoopHeaderSucessor); + OuterLoopHeaderBI->setSuccessor(i, InnerLoopHeaderSuccessor); } + // Adjust reduction PHI's now that the incoming block has changed. + updateIncomingBlock(InnerLoopHeaderSuccessor, InnerLoopHeader, + OuterLoopHeader); + BranchInst::Create(OuterLoopPreHeader, InnerLoopHeaderBI); InnerLoopHeaderBI->eraseFromParent(); @@ -1109,6 +1220,20 @@ bool LoopInterchangeTransform::adjustLoopBranches() { InnerLoopLatchPredecessorBI->setSuccessor(i, InnerLoopLatchSuccessor); } + // Adjust PHI nodes in InnerLoopLatchSuccessor. Update all uses of PHI with + // the value and remove this PHI node from inner loop. + SmallVector LcssaVec; + for (auto I = InnerLoopLatchSuccessor->begin(); isa(I); ++I) { + PHINode *LcssaPhi = cast(I); + LcssaVec.push_back(LcssaPhi); + } + for (auto I = LcssaVec.begin(), E = LcssaVec.end(); I != E; ++I) { + PHINode *P = *I; + Value *Incoming = P->getIncomingValueForBlock(InnerLoopLatch); + P->replaceAllUsesWith(Incoming); + P->eraseFromParent(); + } + if (OuterLoopLatchBI->getSuccessor(0) == OuterLoopHeader) OuterLoopLatchSuccessor = OuterLoopLatchBI->getSuccessor(1); else @@ -1119,6 +1244,8 @@ bool LoopInterchangeTransform::adjustLoopBranches() { else InnerLoopLatchBI->setSuccessor(0, OuterLoopLatchSuccessor); + updateIncomingBlock(OuterLoopLatchSuccessor, OuterLoopLatch, InnerLoopLatch); + if (OuterLoopLatchBI->getSuccessor(0) == OuterLoopLatchSuccessor) { OuterLoopLatchBI->setSuccessor(0, InnerLoopLatch); } else { @@ -1139,32 +1266,12 @@ void LoopInterchangeTransform::adjustLoopPreheaders() { BranchInst *InnerTermBI = cast(InnerLoopPreHeader->getTerminator()); - SmallVector OuterPreheaderInstr; - SmallVector InnerPreheaderInstr; - - for (auto I = OuterLoopPreHeader->begin(); !isa(I); ++I) - OuterPreheaderInstr.push_back(I); - - for (auto I = InnerLoopPreHeader->begin(); !isa(I); ++I) - InnerPreheaderInstr.push_back(I); - - BasicBlock *HeaderSplit = - SplitBlock(OuterLoopHeader, OuterLoopHeader->getTerminator(), DT, LI); - Instruction *InsPoint = HeaderSplit->getFirstNonPHI(); // These instructions should now be executed inside the loop. // Move instruction into a new block after outer header. - for (auto I = InnerPreheaderInstr.begin(), E = InnerPreheaderInstr.end(); - I != E; ++I) { - Instruction *Ins = cast(*I); - Ins->moveBefore(InsPoint); - } + moveBBContents(InnerLoopPreHeader, OuterLoopHeader->getTerminator()); // These instructions were not executed previously in the loop so move them to // the older inner loop preheader. - for (auto I = OuterPreheaderInstr.begin(), E = OuterPreheaderInstr.end(); - I != E; ++I) { - Instruction *Ins = cast(*I); - Ins->moveBefore(InnerTermBI); - } + moveBBContents(OuterLoopPreHeader, InnerTermBI); } bool LoopInterchangeTransform::adjustLoopLinks() { @@ -1179,10 +1286,10 @@ bool LoopInterchangeTransform::adjustLoopLinks() { char LoopInterchange::ID = 0; INITIALIZE_PASS_BEGIN(LoopInterchange, "loop-interchange", "Interchanges loops for cache reuse", false, false) -INITIALIZE_AG_DEPENDENCY(AliasAnalysis) +INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) INITIALIZE_PASS_DEPENDENCY(DependenceAnalysis) INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) -INITIALIZE_PASS_DEPENDENCY(ScalarEvolution) +INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass) INITIALIZE_PASS_DEPENDENCY(LoopSimplify) INITIALIZE_PASS_DEPENDENCY(LCSSA) INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)