#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"
}
#endif
-bool populateDependencyMatrix(CharMatrix &DepMatrix, unsigned Level, Loop *L,
- DependenceAnalysis *DA) {
+static bool populateDependencyMatrix(CharMatrix &DepMatrix, unsigned Level,
+ Loop *L, DependenceAnalysis *DA) {
typedef SmallVector<Value *, 16> ValueVector;
ValueVector MemInstr;
// 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];
// 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;
}
// 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')
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;
}
// 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.
DEBUG(dbgs() << "Calling populateWorklist called\n");
LoopVector LoopList;
Loop *CurrentLoop = &L;
- std::vector<Loop *> vec = CurrentLoop->getSubLoopsVector();
- while (vec.size() != 0) {
+ const std::vector<Loop *> *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) {
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,
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<PHINode *, 8> &Inductions,
+ SmallVector<PHINode *, 8> &Reductions);
Loop *OuterLoop;
Loop *InnerLoop;
/// Scev analysis.
ScalarEvolution *SE;
LoopInterchange *CurrentPass;
+
+ bool InnerLoopHasReduction;
};
/// LoopInterchangeProfitability checks if it is profitable to interchange the
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 *);
void adjustOuterLoopPreheader();
void adjustInnerLoopPreheader();
bool adjustLoopBranches();
+ void updateIncomingBlock(BasicBlock *CurrBlock, BasicBlock *OldPred,
+ BasicBlock *NewPred);
Loop *OuterLoop;
Loop *InnerLoop;
LoopInfo *LI;
DominatorTree *DT;
BasicBlock *LoopExit;
+ bool InnerLoopHasReduction;
};
// Main LoopInterchange Pass
}
void getAnalysisUsage(AnalysisUsage &AU) const override {
- AU.addRequired<ScalarEvolution>();
- AU.addRequired<AliasAnalysis>();
+ AU.addRequired<ScalarEvolutionWrapperPass>();
+ AU.addRequired<AAResultsWrapperPass>();
AU.addRequired<DominatorTreeWrapperPass>();
AU.addRequired<LoopInfoWrapperPass>();
AU.addRequired<DependenceAnalysis>();
}
bool runOnFunction(Function &F) override {
- SE = &getAnalysis<ScalarEvolution>();
+ SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
DA = &getAnalysis<DependenceAnalysis>();
auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();
bool Changed = true;
while (!Worklist.empty()) {
LoopVector LoopList = Worklist.pop_back_val();
- Changed = processLoopList(LoopList);
+ Changed = processLoopList(LoopList, F);
}
return Changed;
}
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");
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<PHINode>(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<PHINode>(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);
}
LoopInterchangeTransform LIT(OuterLoop, InnerLoop, SE, LI, DT, this,
- LoopNestExit);
+ LoopNestExit, LIL.hasInnerLoopReduction());
LIT.transform();
DEBUG(dbgs() << "Loops interchanged\n");
return true;
};
} // 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<PHINode>(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<LoadInst>(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<StoreInst>(I)) {
+ PHINode *PHI = dyn_cast<PHINode>(L->getOperand(0));
+ if (!PHI)
+ return true;
+ } else if (I->mayHaveSideEffects() || I->mayReadFromMemory())
return true;
}
return false;
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");
return true;
}
-static unsigned getPHICount(BasicBlock *BB) {
- unsigned PhiCount = 0;
- for (auto I = BB->begin(); isa<PHINode>(I); ++I)
- PhiCount++;
- return PhiCount;
-}
bool LoopInterchangeLegality::isLoopStructureUnderstood(
PHINode *InnerInduction) {
return true;
}
+bool LoopInterchangeLegality::findInductionAndReductions(
+ Loop *L, SmallVector<PHINode *, 8> &Inductions,
+ SmallVector<PHINode *, 8> &Reductions) {
+ if (!L->getLoopLatch() || !L->getLoopPredecessor())
+ return false;
+ for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) {
+ RecurrenceDescriptor RD;
+ InductionDescriptor ID;
+ PHINode *PHI = cast<PHINode>(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<PHINode>(I); ++I) {
+ PHINode *PHI = cast<PHINode>(I);
+ // Reduction lcssa phi will have only 1 incoming block that from loop latch.
+ if (PHI->getNumIncomingValues() > 1)
+ return false;
+ Instruction *Ins = dyn_cast<Instruction>(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<PHINode>(Ins) && isOuterLoopExitBlock)
+ return false;
+ }
+ return true;
+}
+
+static BasicBlock *getLoopLatchExitBlock(BasicBlock *LatchBlock,
+ BasicBlock *LoopHeader) {
+ if (BranchInst *BI = dyn_cast<BranchInst>(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<PHINode *, 8> Inductions;
+ SmallVector<PHINode *, 8> 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)) {
return true;
}
- // TODO: Loops with LCSSA PHI's are currently not handled.
- if (isa<PHINode>(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<PHINode>(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
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;
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()) {
return false;
}
+ // Check if the loops are tightly nested.
+ if (!tightlyNested(OuterLoop, InnerLoop)) {
+ DEBUG(dbgs() << "Loops not tightly nested\n");
+ return false;
+ }
+
return true;
}
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.
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.
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);
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();
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);
}
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");
}
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() {
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<PHINode *, 8> PHIVec;
+ for (auto I = New->begin(); isa<PHINode>(I); ++I) {
+ PHINode *PHI = dyn_cast<PHINode>(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<Instruction *, 8> Inst;
- for (auto I = OuterLoopPreHeader->begin(), E = OuterLoopPreHeader->end();
- I != E; ++I) {
- if (isa<BranchInst>(*I))
- break;
- Inst.push_back(I);
- }
-
BasicBlock *InnerPreHeader = InnerLoop->getLoopPreheader();
- for (auto I = Inst.begin(), E = Inst.end(); I != E; ++I) {
- Instruction *Ins = cast<Instruction>(*I);
- Ins->moveBefore(InnerPreHeader->getTerminator());
- }
+
+ moveBBContents(OuterLoopPreHeader, InnerPreHeader->getTerminator());
}
void LoopInterchangeTransform::adjustInnerLoopPreheader() {
-
BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
- SmallVector<Instruction *, 8> Inst;
- for (auto I = InnerLoopPreHeader->begin(), E = InnerLoopPreHeader->end();
- I != E; ++I) {
- if (isa<BranchInst>(*I))
- break;
- Inst.push_back(I);
- }
BasicBlock *OuterHeader = OuterLoop->getHeader();
- for (auto I = Inst.begin(), E = Inst.end(); I != E; ++I) {
- Instruction *Ins = cast<Instruction>(*I);
- Ins->moveBefore(OuterHeader->getTerminator());
+
+ moveBBContents(InnerLoopPreHeader, OuterHeader->getTerminator());
+}
+
+void LoopInterchangeTransform::updateIncomingBlock(BasicBlock *CurrBlock,
+ BasicBlock *OldPred,
+ BasicBlock *NewPred) {
+ for (auto I = CurrBlock->begin(); isa<PHINode>(I); ++I) {
+ PHINode *PHI = cast<PHINode>(I);
+ unsigned Num = PHI->getNumIncomingValues();
+ for (unsigned i = 0; i < Num; ++i) {
+ if (PHI->getIncomingBlock(i) == OldPred)
+ PHI->setIncomingBlock(i, NewPred);
+ }
}
}
if (!OuterLoopPredecessorBI || !InnerLoopLatchPredecessorBI)
return false;
- BasicBlock *InnerLoopHeaderSucessor = InnerLoopHeader->getUniqueSuccessor();
- if (!InnerLoopHeaderSucessor)
+ BasicBlock *InnerLoopHeaderSuccessor = InnerLoopHeader->getUniqueSuccessor();
+ if (!InnerLoopHeaderSuccessor)
return false;
// Adjust Loop Preheader and headers
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();
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<PHINode *, 8> LcssaVec;
+ for (auto I = InnerLoopLatchSuccessor->begin(); isa<PHINode>(I); ++I) {
+ PHINode *LcssaPhi = cast<PHINode>(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
else
InnerLoopLatchBI->setSuccessor(0, OuterLoopLatchSuccessor);
+ updateIncomingBlock(OuterLoopLatchSuccessor, OuterLoopLatch, InnerLoopLatch);
+
if (OuterLoopLatchBI->getSuccessor(0) == OuterLoopLatchSuccessor) {
OuterLoopLatchBI->setSuccessor(0, InnerLoopLatch);
} else {
BranchInst *InnerTermBI =
cast<BranchInst>(InnerLoopPreHeader->getTerminator());
- SmallVector<Value *, 16> OuterPreheaderInstr;
- SmallVector<Value *, 16> InnerPreheaderInstr;
-
- for (auto I = OuterLoopPreHeader->begin(); !isa<BranchInst>(I); ++I)
- OuterPreheaderInstr.push_back(I);
-
- for (auto I = InnerLoopPreHeader->begin(); !isa<BranchInst>(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<Instruction>(*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<Instruction>(*I);
- Ins->moveBefore(InnerTermBI);
- }
+ moveBBContents(OuterLoopPreHeader, InnerTermBI);
}
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)
projects / oota-llvm.git / blobdiff