return false;
if (St && !St->isSimple())
return false;
- MemInstr.push_back(I);
+ MemInstr.push_back(&*I);
}
}
}
}
- // We don't have a DepMatrix to check legality return false
+ // We don't have a DepMatrix to check legality return false.
if (DepMatrix.size() == 0)
return false;
return true;
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) {
class LoopInterchangeLegality {
public:
LoopInterchangeLegality(Loop *Outer, Loop *Inner, ScalarEvolution *SE,
- LoopInterchange *Pass)
- : OuterLoop(Outer), InnerLoop(Inner), SE(SE), CurrentPass(Pass),
- InnerLoopHasReduction(false) {}
+ LoopInfo *LI, DominatorTree *DT, bool PreserveLCSSA)
+ : OuterLoop(Outer), InnerLoop(Inner), SE(SE), LI(LI), DT(DT),
+ PreserveLCSSA(PreserveLCSSA), InnerLoopHasReduction(false) {}
/// Check if the loops can be interchanged.
bool canInterchangeLoops(unsigned InnerLoopId, unsigned OuterLoopId,
Loop *OuterLoop;
Loop *InnerLoop;
- /// Scev analysis.
ScalarEvolution *SE;
- LoopInterchange *CurrentPass;
+ LoopInfo *LI;
+ DominatorTree *DT;
+ bool PreserveLCSSA;
bool InnerLoopHasReduction;
};
LoopInterchangeProfitability(Loop *Outer, Loop *Inner, ScalarEvolution *SE)
: OuterLoop(Outer), InnerLoop(Inner), SE(SE) {}
- /// Check if the loop interchange is profitable
+ /// Check if the loop interchange is profitable.
bool isProfitable(unsigned InnerLoopId, unsigned OuterLoopId,
CharMatrix &DepMatrix);
ScalarEvolution *SE;
};
-/// LoopInterchangeTransform interchanges the loop
+/// LoopInterchangeTransform interchanges the loop.
class LoopInterchangeTransform {
public:
LoopInterchangeTransform(Loop *Outer, Loop *Inner, ScalarEvolution *SE,
LoopInfo *LI, DominatorTree *DT,
- LoopInterchange *Pass, BasicBlock *LoopNestExit,
+ BasicBlock *LoopNestExit,
bool InnerLoopContainsReductions)
: OuterLoop(Outer), InnerLoop(Inner), SE(SE), LI(LI), DT(DT),
LoopExit(LoopNestExit),
bool InnerLoopHasReduction;
};
-// Main LoopInterchange Pass
+// Main LoopInterchange Pass.
struct LoopInterchange : public FunctionPass {
static char ID;
ScalarEvolution *SE;
LoopInfo *LI;
DependenceAnalysis *DA;
DominatorTree *DT;
+ bool PreserveLCSSA;
LoopInterchange()
: FunctionPass(ID), SE(nullptr), LI(nullptr), DA(nullptr), DT(nullptr) {
initializeLoopInterchangePass(*PassRegistry::getPassRegistry());
}
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>();
DT = DTWP ? &DTWP->getDomTree() : nullptr;
+ PreserveLCSSA = mustPreserveAnalysisID(LCSSAID);
+
// Build up a worklist of loop pairs to analyze.
SmallVector<LoopVector, 8> Worklist;
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;
}
}
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);
Loop *InnerLoop = LoopList[InnerLoopId];
Loop *OuterLoop = LoopList[OuterLoopId];
- LoopInterchangeLegality LIL(OuterLoop, InnerLoop, SE, this);
+ LoopInterchangeLegality LIL(OuterLoop, InnerLoop, SE, LI, DT,
+ PreserveLCSSA);
if (!LIL.canInterchangeLoops(InnerLoopId, OuterLoopId, DependencyMatrix)) {
DEBUG(dbgs() << "Not interchanging Loops. Cannot prove legality\n");
return false;
return false;
}
- LoopInterchangeTransform LIT(OuterLoop, InnerLoop, SE, LI, DT, this,
+ LoopInterchangeTransform LIT(OuterLoop, InnerLoop, SE, LI, DT,
LoopNestExit, LIL.hasInnerLoopReduction());
LIT.transform();
DEBUG(dbgs() << "Loops interchanged\n");
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);
- ReductionDescriptor RD;
- return !UserIns || !ReductionDescriptor::isReductionPHI(UserIns, L, RD);
+ RecurrenceDescriptor RD;
+ return !UserIns || !RecurrenceDescriptor::isReductionPHI(UserIns, L, RD);
});
}
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.
+ // and outer loop latch doesn't contain any unsafe instructions.
if (containsUnsafeInstructionsInHeader(OuterLoopHeader) ||
containsUnsafeInstructionsInLatch(OuterLoopLatch))
return false;
if (!L->getLoopLatch() || !L->getLoopPredecessor())
return false;
for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) {
- ReductionDescriptor RD;
+ RecurrenceDescriptor RD;
+ InductionDescriptor ID;
PHINode *PHI = cast<PHINode>(I);
- ConstantInt *StepValue = nullptr;
- if (isInductionPHI(PHI, SE, StepValue))
+ if (InductionDescriptor::isInductionPHI(PHI, SE, ID))
Inductions.push_back(PHI);
- else if (ReductionDescriptor::isReductionPHI(PHI, L, RD))
+ else if (RecurrenceDescriptor::isReductionPHI(PHI, L, RD))
Reductions.push_back(PHI);
else {
DEBUG(
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;
if (!OuterLoopPreHeader || OuterLoopPreHeader == OuterLoop->getHeader() ||
isa<PHINode>(OuterLoopPreHeader->begin()) ||
!OuterLoopPreHeader->getUniquePredecessor()) {
- OuterLoopPreHeader = InsertPreheaderForLoop(OuterLoop, CurrentPass);
+ OuterLoopPreHeader =
+ InsertPreheaderForLoop(OuterLoop, DT, LI, PreserveLCSSA);
}
if (!InnerLoopPreHeader || InnerLoopPreHeader == InnerLoop->getHeader() ||
InnerLoopPreHeader == OuterLoop->getHeader()) {
- InnerLoopPreHeader = InsertPreheaderForLoop(InnerLoop, CurrentPass);
+ InnerLoopPreHeader =
+ InsertPreheaderForLoop(InnerLoop, DT, LI, PreserveLCSSA);
}
// TODO: The loops could not be interchanged due to current limitations in the
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);
return;
}
}
- assert(false && "Couldn't find loop");
+ llvm_unreachable("Couldn't find loop");
}
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);
}
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");
}
auto &ToList = InsertBefore->getParent()->getInstList();
auto &FromList = FromBB->getInstList();
- ToList.splice(InsertBefore, FromList, FromList.begin(),
- FromBB->getTerminator());
+ ToList.splice(InsertBefore->getIterator(), FromList, FromList.begin(),
+ FromBB->getTerminator()->getIterator());
}
void LoopInterchangeTransform::adjustOuterLoopPreheader() {
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(InnerLoopHeaderSucessor, InnerLoopHeader,
+ updateIncomingBlock(InnerLoopHeaderSuccessor, InnerLoopHeader,
OuterLoopHeader);
BranchInst::Create(OuterLoopPreHeader, InnerLoopHeaderBI);
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