Index: lib/Transforms/IPO/PassManagerBuilder.cpp =================================================================== --- lib/Transforms/IPO/PassManagerBuilder.cpp +++ lib/Transforms/IPO/PassManagerBuilder.cpp @@ -243,8 +243,6 @@ MPM.add(createIndVarSimplifyPass()); // Canonicalize indvars MPM.add(createLoopIdiomPass()); // Recognize idioms like memset. MPM.add(createLoopDeletionPass()); // Delete dead loops - if (EnableLoopInterchange) - MPM.add(createLoopInterchangePass()); // Interchange loops if (!DisableUnrollLoops) MPM.add(createSimpleLoopUnrollPass()); // Unroll small loops @@ -263,6 +261,12 @@ // opportunities that creates). MPM.add(createBitTrackingDCEPass()); // Delete dead bit computations + if (EnableLoopInterchange) { + MPM.add(createLoopInterchangePass()); // Interchange loops + MPM.add(createLICMPass()); // Hoist loop invariants + MPM.add(createLoopUnswitchPass(SizeLevel || OptLevel < 3)); + } + // Run instcombine after redundancy elimination to exploit opportunities // opened up by them. MPM.add(createInstructionCombiningPass()); Index: lib/Transforms/Scalar/LoopInterchange.cpp =================================================================== --- lib/Transforms/Scalar/LoopInterchange.cpp +++ lib/Transforms/Scalar/LoopInterchange.cpp @@ -32,6 +32,7 @@ #include "llvm/IR/Function.h" #include "llvm/IR/IRBuilder.h" #include "llvm/IR/IntrinsicInst.h" +#include "llvm/IR/Module.h" #include "llvm/IR/InstIterator.h" #include "llvm/IR/Dominators.h" #include "llvm/Pass.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; @@ -101,7 +102,6 @@ MemInstr.push_back(I); } } - DEBUG(dbgs() << "Found " << MemInstr.size() << " Loads and Stores to analyze\n"); @@ -183,8 +183,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 +195,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 +208,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 +218,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; @@ -256,8 +257,9 @@ // [Theorm] 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. @@ -323,6 +325,213 @@ return nullptr; } +static bool isReductionInstr(Instruction *I) { + bool FP = I->getType()->isFloatingPointTy(); + bool FastMath = FP && I->hasUnsafeAlgebra(); + switch (I->getOpcode()) { + default: + return false; + case Instruction::PHI: + return true; + case Instruction::Sub: + case Instruction::Add: + case Instruction::Mul: + case Instruction::And: + case Instruction::Or: + case Instruction::Xor: + return true; + case Instruction::FMul: + case Instruction::FSub: + case Instruction::FAdd: + return FastMath; + } + return false; +} + +static bool hasMultipleUsesOf(Instruction *I, + SmallPtrSetImpl &Insts) { + unsigned NumUses = 0; + for (User::op_iterator Use = I->op_begin(), E = I->op_end(); Use != E; + ++Use) { + if (Insts.count(dyn_cast(*Use))) + ++NumUses; + if (NumUses > 1) + return true; + } + + return false; +} + +static bool areAllUsesIn(Instruction *I, SmallPtrSetImpl &Set) { + for (User::op_iterator Use = I->op_begin(), E = I->op_end(); Use != E; ++Use) + if (!Set.count(dyn_cast(*Use))) + return false; + return true; +} + +static bool isReductionPHI(PHINode *Phi, Loop *TheLoop) { + if (Phi->getNumIncomingValues() != 2) + return false; + + // Reduction variables are only found in the loop header block. + if (Phi->getParent() != TheLoop->getHeader()) + return false; + + Instruction *ExitInstruction = nullptr; + // Indicates that we found a reduction operation in our scan. + bool FoundReduxOp = false; + + // We start with the PHI node and scan for all of the users of this + // instruction. All users must be instructions that can be used as reduction + // variables (such as ADD). We must have a single out-of-block user. The cycle + // must include the original PHI. + bool FoundStartPHI = false; + + SmallPtrSet VisitedInsts; + SmallVector Worklist; + Worklist.push_back(Phi); + VisitedInsts.insert(Phi); + + // A value in the reduction can be used: + // - By the reduction: + // - Reduction operation: + // - One use of reduction value (safe). + // - Multiple use of reduction value (not safe). + // - PHI: + // - All uses of the PHI must be the reduction (safe). + // - Otherwise, not safe. + // - By one instruction outside of the loop (safe). + // - By further instructions outside of the loop (not safe). + // - By an instruction that is not part of the reduction (not safe). + // This is either: + // * An instruction type other than PHI or the reduction operation. + // * A PHI in the header other than the initial PHI. + while (!Worklist.empty()) { + Instruction *Cur = Worklist.back(); + Worklist.pop_back(); + + // No Users. + // If the instruction has no users then this is a broken chain and can't be + // a reduction variable. + if (Cur->use_empty()) + return false; + + bool IsAPhi = isa(Cur); + + // A header PHI use other than the original PHI. + if (Cur != Phi && IsAPhi && Cur->getParent() == Phi->getParent()) + return false; + + // Reductions of instructions such as Div, and Sub is only possible if the + // LHS is the reduction variable. + if (!Cur->isCommutative() && !IsAPhi && !isa(Cur) && + !isa(Cur) && !isa(Cur) && + !VisitedInsts.count(dyn_cast(Cur->getOperand(0)))) + return false; + + bool IsReduction = isReductionInstr(Cur); + if (!IsReduction) { + DEBUG(dbgs() << "IsReduction failed\n"); + return false; + } + + // A reduction operation must only have one use of the reduction value. + if (!IsAPhi && hasMultipleUsesOf(Cur, VisitedInsts)) + return false; + + // All inputs to a PHI node must be a reduction value. + if (IsAPhi && Cur != Phi && !areAllUsesIn(Cur, VisitedInsts)) + return false; + + // Check whether we found a reduction operator. + FoundReduxOp |= !IsAPhi; + + // Process users of current instruction. Push non-PHI nodes after PHI nodes + // onto the stack. This way we are going to have seen all inputs to PHI + // nodes once we get to them. + SmallVector NonPHIs; + SmallVector PHIs; + for (User *U : Cur->users()) { + Instruction *UI = cast(U); + + // Check if we found the exit user. + BasicBlock *Parent = UI->getParent(); + if (!TheLoop->contains(Parent)) { + // Exit if you find multiple outside users or if the header phi node is + // being used. In this case the user uses the value of the previous + // iteration, in which case we would loose "VF-1" iterations of the + // reduction operation if we vectorize. + if (ExitInstruction != nullptr || Cur == Phi) + return false; + + // The instruction used by an outside user must be the last instruction + // before we feed back to the reduction phi. Otherwise, we loose VF-1 + // operations on the value. + if (std::find(Phi->op_begin(), Phi->op_end(), Cur) == Phi->op_end()) + return false; + + ExitInstruction = Cur; + continue; + } + + if (VisitedInsts.insert(UI).second) { + if (isa(UI)) + PHIs.push_back(UI); + else + NonPHIs.push_back(UI); + } + // Remember that we completed the cycle. + if (UI == Phi) + FoundStartPHI = true; + } + Worklist.append(PHIs.begin(), PHIs.end()); + Worklist.append(NonPHIs.begin(), NonPHIs.end()); + } + + if (!FoundStartPHI || !FoundReduxOp || !ExitInstruction) + return false; + + return true; +} + +static bool isInductionPHI(PHINode *Phi, ScalarEvolution *SE) { + Type *PhiTy = Phi->getType(); + if (!PhiTy->isIntegerTy() && !PhiTy->isPointerTy()) + return false; + + // Check that the PHI is consecutive. + const SCEV *PhiScev = SE->getSCEV(Phi); + const SCEVAddRecExpr *AR = dyn_cast(PhiScev); + if (!AR) { + DEBUG(dbgs() << "PHI is not a poly recurrence.\n"); + return false; + } + + const SCEV *Step = AR->getStepRecurrence(*SE); + const SCEVConstant *C = dyn_cast(Step); + if (!C) + return false; + + ConstantInt *CV = C->getValue(); + if (PhiTy->isIntegerTy()) { + return true; + } + + assert(PhiTy->isPointerTy() && "The PHI must be a pointer"); + Type *PointerElementType = PhiTy->getPointerElementType(); + // The pointer stride cannot be determined if the pointer element type is not + // sized. + if (!PointerElementType->isSized()) + return false; + + const DataLayout &DL = Phi->getModule()->getDataLayout(); + int64_t Size = static_cast(DL.getTypeAllocSize(PointerElementType)); + int64_t CVSize = CV->getSExtValue(); + if (CVSize % Size) + return false; + return true; +} + /// LoopInterchangeLegality checks if it is legal to interchange the loop. class LoopInterchangeLegality { public: @@ -341,7 +550,12 @@ private: bool tightlyNested(Loop *Outer, Loop *Inner); - + bool containsUnsafeInstructionsInHeader(BasicBlock *BB); + bool checkAllUsesAreReductions(Instruction *Ins, Loop *L); + bool containsUnsafeInstructionsInLatch(BasicBlock *BB); + bool populateInductionAndReductions(Loop *L); + SmallVector Inductions; + SmallVector Reductions; Loop *OuterLoop; Loop *InnerLoop; @@ -389,6 +603,7 @@ void splitInnerLoopLatch(Instruction *); void splitOuterLoopLatch(); void splitInnerLoopHeader(); + bool hasReductionPHI(Loop *L); bool adjustLoopLinks(); void adjustLoopPreheaders(); void adjustOuterLoopPreheader(); @@ -443,7 +658,7 @@ bool Changed = true; while (!Worklist.empty()) { LoopVector LoopList = Worklist.pop_back_val(); - Changed = processLoopList(LoopList); + Changed = processLoopList(LoopList, F); } return Changed; } @@ -474,9 +689,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 +733,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 +751,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); @@ -559,7 +764,6 @@ bool processLoop(LoopVector LoopList, unsigned InnerLoopId, unsigned OuterLoopId, BasicBlock *LoopNestExit, std::vector> &DependencyMatrix) { - DEBUG(dbgs() << "Processing Innder Loop Id = " << InnerLoopId << " and OuterLoopId = " << OuterLoopId << "\n"); Loop *InnerLoop = LoopList[InnerLoopId]; @@ -586,11 +790,47 @@ }; } // end of namespace +bool LoopInterchangeLegality::checkAllUsesAreReductions(Instruction *Ins, + Loop *L) { + for (auto I = Ins->user_begin(), E = I->user_end(); I != E; ++I) { + PHINode *UserIns = dyn_cast(*I); + if (!UserIns) + return false; + if (!isReductionPHI(UserIns, L)) + return false; + } + return true; +} -static bool containsUnsafeInstructions(BasicBlock *BB) { +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 (!checkAllUsesAreReductions(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 +859,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 +868,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 +894,80 @@ return true; } +bool LoopInterchangeLegality::populateInductionAndReductions(Loop *L) { + if (L->getLoopLatch() == nullptr || L->getLoopPredecessor() == nullptr) + return false; + for (BasicBlock::iterator I = L->getHeader()->begin(); isa(I); ++I) { + PHINode *PHI = cast(I); + if (isInductionPHI(PHI, SE)) + Inductions.push_back(PHI); + else if (isReductionPHI(PHI, L)) + Reductions.push_back(PHI); + else + 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->getNumOperands(); + 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) + if (!populateInductionAndReductions(InnerLoop)) return true; - if (getPHICount(OuterLoopHeader) > 1) + // TODO: Currently we handle only loops with 1 induction variable. + if (Inductions.size() != 1) + return true; + InnerInductionVar = Inductions.pop_back_val(); + Reductions.clear(); + if (!populateInductionAndReductions(OuterLoop)) return true; - InnerInductionVar = getInductionVariable(InnerLoop, SE); - OuterInductionVar = getInductionVariable(OuterLoop, SE); - - 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 +975,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 +1062,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 +1069,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; } @@ -981,11 +1260,47 @@ OuterLoopLatch->getFirstNonPHI(), DT, LI); } +bool LoopInterchangeTransform::hasReductionPHI(Loop *L) { + BasicBlock *LoopHeader = L->getHeader(); + for (auto I = LoopHeader->begin(); isa(I); ++I) { + PHINode *PHI = cast(I); + if (isReductionPHI(PHI, L)) + return true; + } + return false; +} + 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 (hasReductionPHI(InnerLoop)) { + // TODO: 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); + for (auto UI = PHI->user_begin(), UE = PHI->user_end(); UI != UE; ++UI) { + 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"); @@ -1072,6 +1387,17 @@ OuterLoopHeaderBI->setSuccessor(i, InnerLoopHeaderSucessor); } + // Adjust reduction PHI's now that the incoming block has changed. + for (auto I = InnerLoopHeaderSucessor->begin(); isa(I); ++I) { + PHINode *PHI = cast(I); + unsigned Num = PHI->getNumIncomingValues(); + for (unsigned i = 0; i < Num; ++i) { + if (PHI->getIncomingBlock(i) == InnerLoopHeader) { + PHI->setIncomingBlock(i, OuterLoopHeader); + } + } + } + BranchInst::Create(OuterLoopPreHeader, InnerLoopHeaderBI); InnerLoopHeaderBI->eraseFromParent(); @@ -1087,6 +1413,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 +1437,15 @@ else InnerLoopLatchBI->setSuccessor(0, OuterLoopLatchSuccessor); + for (auto I = OuterLoopLatchSuccessor->begin(); isa(I); ++I) { + PHINode *PHI = cast(I); + unsigned Num = PHI->getNumIncomingValues(); + for (unsigned i = 0; i < Num; ++i) { + if (PHI->getIncomingBlock(i) == OuterLoopLatch) + PHI->setIncomingBlock(i, InnerLoopLatch); + } + } + if (OuterLoopLatchBI->getSuccessor(0) == OuterLoopLatchSuccessor) { OuterLoopLatchBI->setSuccessor(0, InnerLoopLatch); } else { @@ -1117,12 +1466,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,290 @@ +; 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