Index: lib/Transforms/IPO/PassManagerBuilder.cpp =================================================================== --- lib/Transforms/IPO/PassManagerBuilder.cpp +++ lib/Transforms/IPO/PassManagerBuilder.cpp @@ -246,9 +246,10 @@ MPM.add(createIndVarSimplifyPass()); // Canonicalize indvars MPM.add(createLoopIdiomPass()); // Recognize idioms like memset. MPM.add(createLoopDeletionPass()); // Delete dead loops - if (EnableLoopInterchange) + if (EnableLoopInterchange) { MPM.add(createLoopInterchangePass()); // Interchange loops - + MPM.add(createCFGSimplificationPass()); + } if (!DisableUnrollLoops) MPM.add(createSimpleLoopUnrollPass()); // Unroll small loops addExtensionsToPM(EP_LoopOptimizerEnd, MPM); Index: lib/Transforms/Scalar/LoopInterchange.cpp =================================================================== --- lib/Transforms/Scalar/LoopInterchange.cpp +++ lib/Transforms/Scalar/LoopInterchange.cpp @@ -33,6 +33,7 @@ #include "llvm/IR/IRBuilder.h" #include "llvm/IR/InstIterator.h" #include "llvm/IR/IntrinsicInst.h" +#include "llvm/IR/Module.h" #include "llvm/Pass.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" @@ -70,8 +71,8 @@ } #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 @@ // 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 @@ // 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 @@ } // 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 @@ 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 @@ } // 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. @@ -328,7 +332,8 @@ 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 @@ 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,9 +390,11 @@ 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) {} + LoopExit(LoopNestExit), + InnerLoopHasReduction(InnerLoopContainsReductions) {} /// Interchange OuterLoop and InnerLoop. bool transform(); @@ -394,6 +410,8 @@ void adjustOuterLoopPreheader(); void adjustInnerLoopPreheader(); bool adjustLoopBranches(); + void updateIncomingBlock(BasicBlock *CurrBlock, BasicBlock *OldPred, + BasicBlock *NewPred); Loop *OuterLoop; Loop *InnerLoop; @@ -403,6 +421,7 @@ LoopInfo *LI; DominatorTree *DT; BasicBlock *LoopExit; + bool InnerLoopHasReduction; }; // Main LoopInterchange Pass @@ -443,7 +462,7 @@ bool Changed = true; while (!Worklist.empty()) { LoopVector LoopList = Worklist.pop_back_val(); - Changed = processLoopList(LoopList); + Changed = processLoopList(LoopList, F); } return Changed; } @@ -474,9 +493,9 @@ 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"); @@ -518,21 +537,11 @@ 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. @@ -546,7 +555,7 @@ // Update the DependencyMatrix interChangeDepedencies(DependencyMatrix, i, i - 1); - + DT->recalculate(F); #ifdef DUMP_DEP_MATRICIES DEBUG(dbgs() << "Dependence after inter change \n"); printDepMatrix(DependencyMatrix); @@ -578,7 +587,7 @@ } LoopInterchangeTransform LIT(OuterLoop, InnerLoop, SE, LI, DT, this, - LoopNestExit); + LoopNestExit, LIL.hasInnerLoopReduction()); LIT.transform(); DEBUG(dbgs() << "Loops interchanged\n"); return true; @@ -586,10 +595,38 @@ }; } // 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); + ReductionDescriptor RD; + return !UserIns || !ReductionDescriptor::isReductionPHI(UserIns, L, RD); + }); +} -static bool containsUnsafeInstructions(BasicBlock *BB) { +bool LoopInterchangeLegality::containsUnsafeInstructionsInHeader( + BasicBlock *BB) { for (auto I = BB->begin(), E = BB->end(); I != E; ++I) { - if (I->mayHaveSideEffects() || I->mayReadFromMemory()) + // 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; +} + +bool LoopInterchangeLegality::containsUnsafeInstructionsInLatch( + BasicBlock *BB) { + for (auto I = BB->begin(), E = BB->end(); I != E; ++I) { + // 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; @@ -619,8 +656,8 @@ 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)) + if (containsUnsafeInstructionsInHeader(OuterLoopHeader) || + containsUnsafeInstructionsInLatch(OuterLoopLatch)) return false; DEBUG(dbgs() << "Loops are perfectly nested \n"); @@ -628,12 +665,6 @@ 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) { @@ -660,34 +691,96 @@ 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) { + ReductionDescriptor RD; + PHINode *PHI = cast(I); + ConstantInt *StepValue = nullptr; + if (isInductionPHI(PHI, SE, StepValue)) + Inductions.push_back(PHI); + else if (ReductionDescriptor::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)) { @@ -695,16 +788,15 @@ 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 @@ -783,12 +875,6 @@ 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()) { @@ -796,6 +882,12 @@ return false; } + // Check if the loops are tightly nested. + if (!tightlyNested(OuterLoop, InnerLoop)) { + DEBUG(dbgs() << "Loops not tightly nested\n"); + return false; + } + return true; } @@ -983,9 +1075,33 @@ 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"); @@ -1015,6 +1131,19 @@ 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); + } + } +} + bool LoopInterchangeTransform::adjustLoopBranches() { DEBUG(dbgs() << "adjustLoopBranches called\n"); @@ -1072,6 +1201,10 @@ OuterLoopHeaderBI->setSuccessor(i, InnerLoopHeaderSucessor); } + // Adjust reduction PHI's now that the incoming block has changed. + updateIncomingBlock(InnerLoopHeaderSucessor, InnerLoopHeader, + OuterLoopHeader); + BranchInst::Create(OuterLoopPreHeader, InnerLoopHeaderBI); InnerLoopHeaderBI->eraseFromParent(); @@ -1087,6 +1220,20 @@ 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 @@ -1097,6 +1244,8 @@ else InnerLoopLatchBI->setSuccessor(0, OuterLoopLatchSuccessor); + updateIncomingBlock(OuterLoopLatchSuccessor, OuterLoopLatch, InnerLoopLatch); + if (OuterLoopLatchBI->getSuccessor(0) == OuterLoopLatchSuccessor) { OuterLoopLatchBI->setSuccessor(0, InnerLoopLatch); } else { @@ -1117,12 +1266,9 @@ BranchInst *InnerTermBI = cast(InnerLoopPreHeader->getTerminator()); - 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. - moveBBContents(InnerLoopPreHeader, InsPoint); + moveBBContents(InnerLoopPreHeader, OuterLoopHeader->getTerminator()); // These instructions were not executed previously in the loop so move them to // the older inner loop preheader. moveBBContents(OuterLoopPreHeader, InnerTermBI); Index: test/Transforms/LoopInterchange/reductions.ll =================================================================== --- test/Transforms/LoopInterchange/reductions.ll +++ test/Transforms/LoopInterchange/reductions.ll @@ -0,0 +1,289 @@ +; RUN: opt < %s -basicaa -loop-interchange -S | FileCheck %s +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" +target triple = "x86_64-unknown-linux-gnu" + +@A = common global [500 x [500 x i32]] zeroinitializer +@X = common global i32 0 +@B = common global [500 x [500 x i32]] zeroinitializer +@Y = common global i32 0 + +;; for( int i=1;i