1 //===- LoopInterchange.cpp - Loop interchange pass------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This Pass handles loop interchange transform.
11 // This pass interchanges loops to provide a more cache-friendly memory access
14 //===----------------------------------------------------------------------===//
16 #include "llvm/ADT/SmallVector.h"
17 #include "llvm/Analysis/AliasAnalysis.h"
18 #include "llvm/Analysis/AliasSetTracker.h"
19 #include "llvm/Analysis/AssumptionCache.h"
20 #include "llvm/Analysis/BlockFrequencyInfo.h"
21 #include "llvm/Analysis/CodeMetrics.h"
22 #include "llvm/Analysis/DependenceAnalysis.h"
23 #include "llvm/Analysis/LoopInfo.h"
24 #include "llvm/Analysis/LoopIterator.h"
25 #include "llvm/Analysis/LoopPass.h"
26 #include "llvm/Analysis/ScalarEvolution.h"
27 #include "llvm/Analysis/ScalarEvolutionExpander.h"
28 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
29 #include "llvm/Analysis/TargetTransformInfo.h"
30 #include "llvm/Analysis/ValueTracking.h"
31 #include "llvm/IR/Dominators.h"
32 #include "llvm/IR/Function.h"
33 #include "llvm/IR/IRBuilder.h"
34 #include "llvm/IR/InstIterator.h"
35 #include "llvm/IR/IntrinsicInst.h"
36 #include "llvm/IR/Module.h"
37 #include "llvm/Pass.h"
38 #include "llvm/Support/Debug.h"
39 #include "llvm/Support/raw_ostream.h"
40 #include "llvm/Transforms/Scalar.h"
41 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
42 #include "llvm/Transforms/Utils/LoopUtils.h"
43 #include "llvm/Transforms/Utils/SSAUpdater.h"
46 #define DEBUG_TYPE "loop-interchange"
50 typedef SmallVector<Loop *, 8> LoopVector;
52 // TODO: Check if we can use a sparse matrix here.
53 typedef std::vector<std::vector<char>> CharMatrix;
55 // Maximum number of dependencies that can be handled in the dependency matrix.
56 static const unsigned MaxMemInstrCount = 100;
58 // Maximum loop depth supported.
59 static const unsigned MaxLoopNestDepth = 10;
61 struct LoopInterchange;
63 #ifdef DUMP_DEP_MATRICIES
64 void printDepMatrix(CharMatrix &DepMatrix) {
65 for (auto I = DepMatrix.begin(), E = DepMatrix.end(); I != E; ++I) {
66 std::vector<char> Vec = *I;
67 for (auto II = Vec.begin(), EE = Vec.end(); II != EE; ++II)
68 DEBUG(dbgs() << *II << " ");
69 DEBUG(dbgs() << "\n");
74 static bool populateDependencyMatrix(CharMatrix &DepMatrix, unsigned Level,
75 Loop *L, DependenceAnalysis *DA) {
76 typedef SmallVector<Value *, 16> ValueVector;
79 if (Level > MaxLoopNestDepth) {
80 DEBUG(dbgs() << "Cannot handle loops of depth greater than "
81 << MaxLoopNestDepth << "\n");
86 for (Loop::block_iterator BB = L->block_begin(), BE = L->block_end();
88 // Scan the BB and collect legal loads and stores.
89 for (BasicBlock::iterator I = (*BB)->begin(), E = (*BB)->end(); I != E;
91 Instruction *Ins = dyn_cast<Instruction>(I);
94 LoadInst *Ld = dyn_cast<LoadInst>(I);
95 StoreInst *St = dyn_cast<StoreInst>(I);
98 if (Ld && !Ld->isSimple())
100 if (St && !St->isSimple())
102 MemInstr.push_back(&*I);
106 DEBUG(dbgs() << "Found " << MemInstr.size()
107 << " Loads and Stores to analyze\n");
109 ValueVector::iterator I, IE, J, JE;
111 for (I = MemInstr.begin(), IE = MemInstr.end(); I != IE; ++I) {
112 for (J = I, JE = MemInstr.end(); J != JE; ++J) {
113 std::vector<char> Dep;
114 Instruction *Src = dyn_cast<Instruction>(*I);
115 Instruction *Des = dyn_cast<Instruction>(*J);
118 if (isa<LoadInst>(Src) && isa<LoadInst>(Des))
120 if (auto D = DA->depends(Src, Des, true)) {
121 DEBUG(dbgs() << "Found Dependency between Src=" << Src << " Des=" << Des
124 // TODO: Handle Flow dependence.Check if it is sufficient to populate
125 // the Dependence Matrix with the direction reversed.
126 DEBUG(dbgs() << "Flow dependence not handled");
130 DEBUG(dbgs() << "Found Anti dependence \n");
131 unsigned Levels = D->getLevels();
133 for (unsigned II = 1; II <= Levels; ++II) {
134 const SCEV *Distance = D->getDistance(II);
135 const SCEVConstant *SCEVConst =
136 dyn_cast_or_null<SCEVConstant>(Distance);
138 const ConstantInt *CI = SCEVConst->getValue();
139 if (CI->isNegative())
141 else if (CI->isZero())
145 Dep.push_back(Direction);
146 } else if (D->isScalar(II)) {
148 Dep.push_back(Direction);
150 unsigned Dir = D->getDirection(II);
151 if (Dir == Dependence::DVEntry::LT ||
152 Dir == Dependence::DVEntry::LE)
154 else if (Dir == Dependence::DVEntry::GT ||
155 Dir == Dependence::DVEntry::GE)
157 else if (Dir == Dependence::DVEntry::EQ)
161 Dep.push_back(Direction);
164 while (Dep.size() != Level) {
168 DepMatrix.push_back(Dep);
169 if (DepMatrix.size() > MaxMemInstrCount) {
170 DEBUG(dbgs() << "Cannot handle more than " << MaxMemInstrCount
171 << " dependencies inside loop\n");
179 // We don't have a DepMatrix to check legality return false.
180 if (DepMatrix.size() == 0)
185 // A loop is moved from index 'from' to an index 'to'. Update the Dependence
186 // matrix by exchanging the two columns.
187 static void interChangeDepedencies(CharMatrix &DepMatrix, unsigned FromIndx,
189 unsigned numRows = DepMatrix.size();
190 for (unsigned i = 0; i < numRows; ++i) {
191 char TmpVal = DepMatrix[i][ToIndx];
192 DepMatrix[i][ToIndx] = DepMatrix[i][FromIndx];
193 DepMatrix[i][FromIndx] = TmpVal;
197 // Checks if outermost non '=','S'or'I' dependence in the dependence matrix is
199 static bool isOuterMostDepPositive(CharMatrix &DepMatrix, unsigned Row,
201 for (unsigned i = 0; i <= Column; ++i) {
202 if (DepMatrix[Row][i] == '<')
204 if (DepMatrix[Row][i] == '>')
207 // All dependencies were '=','S' or 'I'
211 // Checks if no dependence exist in the dependency matrix in Row before Column.
212 static bool containsNoDependence(CharMatrix &DepMatrix, unsigned Row,
214 for (unsigned i = 0; i < Column; ++i) {
215 if (DepMatrix[Row][i] != '=' || DepMatrix[Row][i] != 'S' ||
216 DepMatrix[Row][i] != 'I')
222 static bool validDepInterchange(CharMatrix &DepMatrix, unsigned Row,
223 unsigned OuterLoopId, char InnerDep,
226 if (isOuterMostDepPositive(DepMatrix, Row, OuterLoopId))
229 if (InnerDep == OuterDep)
232 // It is legal to interchange if and only if after interchange no row has a
233 // '>' direction as the leftmost non-'='.
235 if (InnerDep == '=' || InnerDep == 'S' || InnerDep == 'I')
241 if (InnerDep == '>') {
242 // If OuterLoopId represents outermost loop then interchanging will make the
243 // 1st dependency as '>'
244 if (OuterLoopId == 0)
247 // If all dependencies before OuterloopId are '=','S'or 'I'. Then
248 // interchanging will result in this row having an outermost non '='
250 if (!containsNoDependence(DepMatrix, Row, OuterLoopId))
257 // Checks if it is legal to interchange 2 loops.
258 // [Theorem] A permutation of the loops in a perfect nest is legal if and only
260 // the direction matrix, after the same permutation is applied to its columns,
261 // has no ">" direction as the leftmost non-"=" direction in any row.
262 static bool isLegalToInterChangeLoops(CharMatrix &DepMatrix,
263 unsigned InnerLoopId,
264 unsigned OuterLoopId) {
266 unsigned NumRows = DepMatrix.size();
267 // For each row check if it is valid to interchange.
268 for (unsigned Row = 0; Row < NumRows; ++Row) {
269 char InnerDep = DepMatrix[Row][InnerLoopId];
270 char OuterDep = DepMatrix[Row][OuterLoopId];
271 if (InnerDep == '*' || OuterDep == '*')
273 else if (!validDepInterchange(DepMatrix, Row, OuterLoopId, InnerDep,
280 static void populateWorklist(Loop &L, SmallVector<LoopVector, 8> &V) {
282 DEBUG(dbgs() << "Calling populateWorklist called\n");
284 Loop *CurrentLoop = &L;
285 const std::vector<Loop *> *Vec = &CurrentLoop->getSubLoops();
286 while (!Vec->empty()) {
287 // The current loop has multiple subloops in it hence it is not tightly
289 // Discard all loops above it added into Worklist.
290 if (Vec->size() != 1) {
294 LoopList.push_back(CurrentLoop);
295 CurrentLoop = Vec->front();
296 Vec = &CurrentLoop->getSubLoops();
298 LoopList.push_back(CurrentLoop);
299 V.push_back(std::move(LoopList));
302 static PHINode *getInductionVariable(Loop *L, ScalarEvolution *SE) {
303 PHINode *InnerIndexVar = L->getCanonicalInductionVariable();
305 return InnerIndexVar;
306 if (L->getLoopLatch() == nullptr || L->getLoopPredecessor() == nullptr)
308 for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) {
309 PHINode *PhiVar = cast<PHINode>(I);
310 Type *PhiTy = PhiVar->getType();
311 if (!PhiTy->isIntegerTy() && !PhiTy->isFloatingPointTy() &&
312 !PhiTy->isPointerTy())
314 const SCEVAddRecExpr *AddRec =
315 dyn_cast<SCEVAddRecExpr>(SE->getSCEV(PhiVar));
316 if (!AddRec || !AddRec->isAffine())
318 const SCEV *Step = AddRec->getStepRecurrence(*SE);
319 const SCEVConstant *C = dyn_cast<SCEVConstant>(Step);
322 // Found the induction variable.
323 // FIXME: Handle loops with more than one induction variable. Note that,
324 // currently, legality makes sure we have only one induction variable.
330 /// LoopInterchangeLegality checks if it is legal to interchange the loop.
331 class LoopInterchangeLegality {
333 LoopInterchangeLegality(Loop *Outer, Loop *Inner, ScalarEvolution *SE,
334 LoopInfo *LI, DominatorTree *DT, bool PreserveLCSSA)
335 : OuterLoop(Outer), InnerLoop(Inner), SE(SE), LI(LI), DT(DT),
336 PreserveLCSSA(PreserveLCSSA), InnerLoopHasReduction(false) {}
338 /// Check if the loops can be interchanged.
339 bool canInterchangeLoops(unsigned InnerLoopId, unsigned OuterLoopId,
340 CharMatrix &DepMatrix);
341 /// Check if the loop structure is understood. We do not handle triangular
343 bool isLoopStructureUnderstood(PHINode *InnerInductionVar);
345 bool currentLimitations();
347 bool hasInnerLoopReduction() { return InnerLoopHasReduction; }
350 bool tightlyNested(Loop *Outer, Loop *Inner);
351 bool containsUnsafeInstructionsInHeader(BasicBlock *BB);
352 bool areAllUsesReductions(Instruction *Ins, Loop *L);
353 bool containsUnsafeInstructionsInLatch(BasicBlock *BB);
354 bool findInductionAndReductions(Loop *L,
355 SmallVector<PHINode *, 8> &Inductions,
356 SmallVector<PHINode *, 8> &Reductions);
365 bool InnerLoopHasReduction;
368 /// LoopInterchangeProfitability checks if it is profitable to interchange the
370 class LoopInterchangeProfitability {
372 LoopInterchangeProfitability(Loop *Outer, Loop *Inner, ScalarEvolution *SE)
373 : OuterLoop(Outer), InnerLoop(Inner), SE(SE) {}
375 /// Check if the loop interchange is profitable.
376 bool isProfitable(unsigned InnerLoopId, unsigned OuterLoopId,
377 CharMatrix &DepMatrix);
380 int getInstrOrderCost();
389 /// LoopInterchangeTransform interchanges the loop.
390 class LoopInterchangeTransform {
392 LoopInterchangeTransform(Loop *Outer, Loop *Inner, ScalarEvolution *SE,
393 LoopInfo *LI, DominatorTree *DT,
394 BasicBlock *LoopNestExit,
395 bool InnerLoopContainsReductions)
396 : OuterLoop(Outer), InnerLoop(Inner), SE(SE), LI(LI), DT(DT),
397 LoopExit(LoopNestExit),
398 InnerLoopHasReduction(InnerLoopContainsReductions) {}
400 /// Interchange OuterLoop and InnerLoop.
402 void restructureLoops(Loop *InnerLoop, Loop *OuterLoop);
403 void removeChildLoop(Loop *OuterLoop, Loop *InnerLoop);
406 void splitInnerLoopLatch(Instruction *);
407 void splitOuterLoopLatch();
408 void splitInnerLoopHeader();
409 bool adjustLoopLinks();
410 void adjustLoopPreheaders();
411 void adjustOuterLoopPreheader();
412 void adjustInnerLoopPreheader();
413 bool adjustLoopBranches();
414 void updateIncomingBlock(BasicBlock *CurrBlock, BasicBlock *OldPred,
415 BasicBlock *NewPred);
424 BasicBlock *LoopExit;
425 bool InnerLoopHasReduction;
428 // Main LoopInterchange Pass.
429 struct LoopInterchange : public FunctionPass {
433 DependenceAnalysis *DA;
437 : FunctionPass(ID), SE(nullptr), LI(nullptr), DA(nullptr), DT(nullptr) {
438 initializeLoopInterchangePass(*PassRegistry::getPassRegistry());
441 void getAnalysisUsage(AnalysisUsage &AU) const override {
442 AU.addRequired<ScalarEvolutionWrapperPass>();
443 AU.addRequired<AAResultsWrapperPass>();
444 AU.addRequired<DominatorTreeWrapperPass>();
445 AU.addRequired<LoopInfoWrapperPass>();
446 AU.addRequired<DependenceAnalysis>();
447 AU.addRequiredID(LoopSimplifyID);
448 AU.addRequiredID(LCSSAID);
451 bool runOnFunction(Function &F) override {
452 SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
453 LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
454 DA = &getAnalysis<DependenceAnalysis>();
455 auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();
456 DT = DTWP ? &DTWP->getDomTree() : nullptr;
457 PreserveLCSSA = mustPreserveAnalysisID(LCSSAID);
459 // Build up a worklist of loop pairs to analyze.
460 SmallVector<LoopVector, 8> Worklist;
463 populateWorklist(*L, Worklist);
465 DEBUG(dbgs() << "Worklist size = " << Worklist.size() << "\n");
467 while (!Worklist.empty()) {
468 LoopVector LoopList = Worklist.pop_back_val();
469 Changed = processLoopList(LoopList, F);
474 bool isComputableLoopNest(LoopVector LoopList) {
475 for (auto I = LoopList.begin(), E = LoopList.end(); I != E; ++I) {
477 const SCEV *ExitCountOuter = SE->getBackedgeTakenCount(L);
478 if (ExitCountOuter == SE->getCouldNotCompute()) {
479 DEBUG(dbgs() << "Couldn't compute Backedge count\n");
482 if (L->getNumBackEdges() != 1) {
483 DEBUG(dbgs() << "NumBackEdges is not equal to 1\n");
486 if (!L->getExitingBlock()) {
487 DEBUG(dbgs() << "Loop Doesn't have unique exit block\n");
494 unsigned selectLoopForInterchange(LoopVector LoopList) {
495 // TODO: Add a better heuristic to select the loop to be interchanged based
496 // on the dependence matrix. Currently we select the innermost loop.
497 return LoopList.size() - 1;
500 bool processLoopList(LoopVector LoopList, Function &F) {
502 bool Changed = false;
503 CharMatrix DependencyMatrix;
504 if (LoopList.size() < 2) {
505 DEBUG(dbgs() << "Loop doesn't contain minimum nesting level.\n");
508 if (!isComputableLoopNest(LoopList)) {
509 DEBUG(dbgs() << "Not vaild loop candidate for interchange\n");
512 Loop *OuterMostLoop = *(LoopList.begin());
514 DEBUG(dbgs() << "Processing LoopList of size = " << LoopList.size()
517 if (!populateDependencyMatrix(DependencyMatrix, LoopList.size(),
518 OuterMostLoop, DA)) {
519 DEBUG(dbgs() << "Populating Dependency matrix failed\n");
522 #ifdef DUMP_DEP_MATRICIES
523 DEBUG(dbgs() << "Dependence before inter change \n");
524 printDepMatrix(DependencyMatrix);
527 BasicBlock *OuterMostLoopLatch = OuterMostLoop->getLoopLatch();
528 BranchInst *OuterMostLoopLatchBI =
529 dyn_cast<BranchInst>(OuterMostLoopLatch->getTerminator());
530 if (!OuterMostLoopLatchBI)
533 // Since we currently do not handle LCSSA PHI's any failure in loop
534 // condition will now branch to LoopNestExit.
535 // TODO: This should be removed once we handle LCSSA PHI nodes.
537 // Get the Outermost loop exit.
538 BasicBlock *LoopNestExit;
539 if (OuterMostLoopLatchBI->getSuccessor(0) == OuterMostLoop->getHeader())
540 LoopNestExit = OuterMostLoopLatchBI->getSuccessor(1);
542 LoopNestExit = OuterMostLoopLatchBI->getSuccessor(0);
544 if (isa<PHINode>(LoopNestExit->begin())) {
545 DEBUG(dbgs() << "PHI Nodes in loop nest exit is not handled for now "
546 "since on failure all loops branch to loop nest exit.\n");
550 unsigned SelecLoopId = selectLoopForInterchange(LoopList);
551 // Move the selected loop outwards to the best possible position.
552 for (unsigned i = SelecLoopId; i > 0; i--) {
554 processLoop(LoopList, i, i - 1, LoopNestExit, DependencyMatrix);
557 // Loops interchanged reflect the same in LoopList
558 std::swap(LoopList[i - 1], LoopList[i]);
560 // Update the DependencyMatrix
561 interChangeDepedencies(DependencyMatrix, i, i - 1);
563 #ifdef DUMP_DEP_MATRICIES
564 DEBUG(dbgs() << "Dependence after inter change \n");
565 printDepMatrix(DependencyMatrix);
567 Changed |= Interchanged;
572 bool processLoop(LoopVector LoopList, unsigned InnerLoopId,
573 unsigned OuterLoopId, BasicBlock *LoopNestExit,
574 std::vector<std::vector<char>> &DependencyMatrix) {
576 DEBUG(dbgs() << "Processing Innder Loop Id = " << InnerLoopId
577 << " and OuterLoopId = " << OuterLoopId << "\n");
578 Loop *InnerLoop = LoopList[InnerLoopId];
579 Loop *OuterLoop = LoopList[OuterLoopId];
581 LoopInterchangeLegality LIL(OuterLoop, InnerLoop, SE, LI, DT,
583 if (!LIL.canInterchangeLoops(InnerLoopId, OuterLoopId, DependencyMatrix)) {
584 DEBUG(dbgs() << "Not interchanging Loops. Cannot prove legality\n");
587 DEBUG(dbgs() << "Loops are legal to interchange\n");
588 LoopInterchangeProfitability LIP(OuterLoop, InnerLoop, SE);
589 if (!LIP.isProfitable(InnerLoopId, OuterLoopId, DependencyMatrix)) {
590 DEBUG(dbgs() << "Interchanging Loops not profitable\n");
594 LoopInterchangeTransform LIT(OuterLoop, InnerLoop, SE, LI, DT,
595 LoopNestExit, LIL.hasInnerLoopReduction());
597 DEBUG(dbgs() << "Loops interchanged\n");
602 } // end of namespace
603 bool LoopInterchangeLegality::areAllUsesReductions(Instruction *Ins, Loop *L) {
604 return !std::any_of(Ins->user_begin(), Ins->user_end(), [=](User *U) -> bool {
605 PHINode *UserIns = dyn_cast<PHINode>(U);
606 RecurrenceDescriptor RD;
607 return !UserIns || !RecurrenceDescriptor::isReductionPHI(UserIns, L, RD);
611 bool LoopInterchangeLegality::containsUnsafeInstructionsInHeader(
613 for (auto I = BB->begin(), E = BB->end(); I != E; ++I) {
614 // Load corresponding to reduction PHI's are safe while concluding if
616 if (LoadInst *L = dyn_cast<LoadInst>(I)) {
617 if (!areAllUsesReductions(L, InnerLoop))
619 } else if (I->mayHaveSideEffects() || I->mayReadFromMemory())
625 bool LoopInterchangeLegality::containsUnsafeInstructionsInLatch(
627 for (auto I = BB->begin(), E = BB->end(); I != E; ++I) {
628 // Stores corresponding to reductions are safe while concluding if tightly
630 if (StoreInst *L = dyn_cast<StoreInst>(I)) {
631 PHINode *PHI = dyn_cast<PHINode>(L->getOperand(0));
634 } else if (I->mayHaveSideEffects() || I->mayReadFromMemory())
640 bool LoopInterchangeLegality::tightlyNested(Loop *OuterLoop, Loop *InnerLoop) {
641 BasicBlock *OuterLoopHeader = OuterLoop->getHeader();
642 BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
643 BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch();
645 DEBUG(dbgs() << "Checking if Loops are Tightly Nested\n");
647 // A perfectly nested loop will not have any branch in between the outer and
648 // inner block i.e. outer header will branch to either inner preheader and
650 BranchInst *outerLoopHeaderBI =
651 dyn_cast<BranchInst>(OuterLoopHeader->getTerminator());
652 if (!outerLoopHeaderBI)
654 unsigned num = outerLoopHeaderBI->getNumSuccessors();
655 for (unsigned i = 0; i < num; i++) {
656 if (outerLoopHeaderBI->getSuccessor(i) != InnerLoopPreHeader &&
657 outerLoopHeaderBI->getSuccessor(i) != OuterLoopLatch)
661 DEBUG(dbgs() << "Checking instructions in Loop header and Loop latch \n");
662 // We do not have any basic block in between now make sure the outer header
663 // and outer loop latch doesn't contain any unsafe instructions.
664 if (containsUnsafeInstructionsInHeader(OuterLoopHeader) ||
665 containsUnsafeInstructionsInLatch(OuterLoopLatch))
668 DEBUG(dbgs() << "Loops are perfectly nested \n");
669 // We have a perfect loop nest.
674 bool LoopInterchangeLegality::isLoopStructureUnderstood(
675 PHINode *InnerInduction) {
677 unsigned Num = InnerInduction->getNumOperands();
678 BasicBlock *InnerLoopPreheader = InnerLoop->getLoopPreheader();
679 for (unsigned i = 0; i < Num; ++i) {
680 Value *Val = InnerInduction->getOperand(i);
681 if (isa<Constant>(Val))
683 Instruction *I = dyn_cast<Instruction>(Val);
686 // TODO: Handle triangular loops.
687 // e.g. for(int i=0;i<N;i++)
688 // for(int j=i;j<N;j++)
689 unsigned IncomBlockIndx = PHINode::getIncomingValueNumForOperand(i);
690 if (InnerInduction->getIncomingBlock(IncomBlockIndx) ==
691 InnerLoopPreheader &&
692 !OuterLoop->isLoopInvariant(I)) {
699 bool LoopInterchangeLegality::findInductionAndReductions(
700 Loop *L, SmallVector<PHINode *, 8> &Inductions,
701 SmallVector<PHINode *, 8> &Reductions) {
702 if (!L->getLoopLatch() || !L->getLoopPredecessor())
704 for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) {
705 RecurrenceDescriptor RD;
706 InductionDescriptor ID;
707 PHINode *PHI = cast<PHINode>(I);
708 if (InductionDescriptor::isInductionPHI(PHI, SE, ID))
709 Inductions.push_back(PHI);
710 else if (RecurrenceDescriptor::isReductionPHI(PHI, L, RD))
711 Reductions.push_back(PHI);
714 dbgs() << "Failed to recognize PHI as an induction or reduction.\n");
721 static bool containsSafePHI(BasicBlock *Block, bool isOuterLoopExitBlock) {
722 for (auto I = Block->begin(); isa<PHINode>(I); ++I) {
723 PHINode *PHI = cast<PHINode>(I);
724 // Reduction lcssa phi will have only 1 incoming block that from loop latch.
725 if (PHI->getNumIncomingValues() > 1)
727 Instruction *Ins = dyn_cast<Instruction>(PHI->getIncomingValue(0));
730 // Incoming value for lcssa phi's in outer loop exit can only be inner loop
731 // exits lcssa phi else it would not be tightly nested.
732 if (!isa<PHINode>(Ins) && isOuterLoopExitBlock)
738 static BasicBlock *getLoopLatchExitBlock(BasicBlock *LatchBlock,
739 BasicBlock *LoopHeader) {
740 if (BranchInst *BI = dyn_cast<BranchInst>(LatchBlock->getTerminator())) {
741 unsigned Num = BI->getNumSuccessors();
743 for (unsigned i = 0; i < Num; ++i) {
744 if (BI->getSuccessor(i) == LoopHeader)
746 return BI->getSuccessor(i);
752 // This function indicates the current limitations in the transform as a result
753 // of which we do not proceed.
754 bool LoopInterchangeLegality::currentLimitations() {
756 BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
757 BasicBlock *InnerLoopHeader = InnerLoop->getHeader();
758 BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch();
759 BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch();
760 BasicBlock *OuterLoopHeader = OuterLoop->getHeader();
762 PHINode *InnerInductionVar;
763 SmallVector<PHINode *, 8> Inductions;
764 SmallVector<PHINode *, 8> Reductions;
765 if (!findInductionAndReductions(InnerLoop, Inductions, Reductions))
768 // TODO: Currently we handle only loops with 1 induction variable.
769 if (Inductions.size() != 1) {
770 DEBUG(dbgs() << "We currently only support loops with 1 induction variable."
771 << "Failed to interchange due to current limitation\n");
774 if (Reductions.size() > 0)
775 InnerLoopHasReduction = true;
777 InnerInductionVar = Inductions.pop_back_val();
779 if (!findInductionAndReductions(OuterLoop, Inductions, Reductions))
782 // Outer loop cannot have reduction because then loops will not be tightly
784 if (!Reductions.empty())
786 // TODO: Currently we handle only loops with 1 induction variable.
787 if (Inductions.size() != 1)
790 // TODO: Triangular loops are not handled for now.
791 if (!isLoopStructureUnderstood(InnerInductionVar)) {
792 DEBUG(dbgs() << "Loop structure not understood by pass\n");
796 // TODO: We only handle LCSSA PHI's corresponding to reduction for now.
797 BasicBlock *LoopExitBlock =
798 getLoopLatchExitBlock(OuterLoopLatch, OuterLoopHeader);
799 if (!LoopExitBlock || !containsSafePHI(LoopExitBlock, true))
802 LoopExitBlock = getLoopLatchExitBlock(InnerLoopLatch, InnerLoopHeader);
803 if (!LoopExitBlock || !containsSafePHI(LoopExitBlock, false))
806 // TODO: Current limitation: Since we split the inner loop latch at the point
807 // were induction variable is incremented (induction.next); We cannot have
808 // more than 1 user of induction.next since it would result in broken code
811 // for(i=0;i<N;i++) {
812 // for(j = 0;j<M;j++) {
813 // A[j+1][i+2] = A[j][i]+k;
816 bool FoundInduction = false;
817 Instruction *InnerIndexVarInc = nullptr;
818 if (InnerInductionVar->getIncomingBlock(0) == InnerLoopPreHeader)
820 dyn_cast<Instruction>(InnerInductionVar->getIncomingValue(1));
823 dyn_cast<Instruction>(InnerInductionVar->getIncomingValue(0));
825 if (!InnerIndexVarInc)
828 // Since we split the inner loop latch on this induction variable. Make sure
829 // we do not have any instruction between the induction variable and branch
832 for (auto I = InnerLoopLatch->rbegin(), E = InnerLoopLatch->rend();
833 I != E && !FoundInduction; ++I) {
834 if (isa<BranchInst>(*I) || isa<CmpInst>(*I) || isa<TruncInst>(*I))
836 const Instruction &Ins = *I;
837 // We found an instruction. If this is not induction variable then it is not
838 // safe to split this loop latch.
839 if (!Ins.isIdenticalTo(InnerIndexVarInc))
842 FoundInduction = true;
844 // The loop latch ended and we didn't find the induction variable return as
845 // current limitation.
852 bool LoopInterchangeLegality::canInterchangeLoops(unsigned InnerLoopId,
853 unsigned OuterLoopId,
854 CharMatrix &DepMatrix) {
856 if (!isLegalToInterChangeLoops(DepMatrix, InnerLoopId, OuterLoopId)) {
857 DEBUG(dbgs() << "Failed interchange InnerLoopId = " << InnerLoopId
858 << "and OuterLoopId = " << OuterLoopId
859 << "due to dependence\n");
863 // Create unique Preheaders if we already do not have one.
864 BasicBlock *OuterLoopPreHeader = OuterLoop->getLoopPreheader();
865 BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
867 // Create a unique outer preheader -
868 // 1) If OuterLoop preheader is not present.
869 // 2) If OuterLoop Preheader is same as OuterLoop Header
870 // 3) If OuterLoop Preheader is same as Header of the previous loop.
871 // 4) If OuterLoop Preheader is Entry node.
872 if (!OuterLoopPreHeader || OuterLoopPreHeader == OuterLoop->getHeader() ||
873 isa<PHINode>(OuterLoopPreHeader->begin()) ||
874 !OuterLoopPreHeader->getUniquePredecessor()) {
876 InsertPreheaderForLoop(OuterLoop, DT, LI, PreserveLCSSA);
879 if (!InnerLoopPreHeader || InnerLoopPreHeader == InnerLoop->getHeader() ||
880 InnerLoopPreHeader == OuterLoop->getHeader()) {
882 InsertPreheaderForLoop(InnerLoop, DT, LI, PreserveLCSSA);
885 // TODO: The loops could not be interchanged due to current limitations in the
887 if (currentLimitations()) {
888 DEBUG(dbgs() << "Not legal because of current transform limitation\n");
892 // Check if the loops are tightly nested.
893 if (!tightlyNested(OuterLoop, InnerLoop)) {
894 DEBUG(dbgs() << "Loops not tightly nested\n");
901 int LoopInterchangeProfitability::getInstrOrderCost() {
902 unsigned GoodOrder, BadOrder;
903 BadOrder = GoodOrder = 0;
904 for (auto BI = InnerLoop->block_begin(), BE = InnerLoop->block_end();
906 for (auto I = (*BI)->begin(), E = (*BI)->end(); I != E; ++I) {
907 const Instruction &Ins = *I;
908 if (const GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(&Ins)) {
909 unsigned NumOp = GEP->getNumOperands();
910 bool FoundInnerInduction = false;
911 bool FoundOuterInduction = false;
912 for (unsigned i = 0; i < NumOp; ++i) {
913 const SCEV *OperandVal = SE->getSCEV(GEP->getOperand(i));
914 const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(OperandVal);
918 // If we find the inner induction after an outer induction e.g.
919 // for(int i=0;i<N;i++)
920 // for(int j=0;j<N;j++)
921 // A[i][j] = A[i-1][j-1]+k;
922 // then it is a good order.
923 if (AR->getLoop() == InnerLoop) {
924 // We found an InnerLoop induction after OuterLoop induction. It is
926 FoundInnerInduction = true;
927 if (FoundOuterInduction) {
932 // If we find the outer induction after an inner induction e.g.
933 // for(int i=0;i<N;i++)
934 // for(int j=0;j<N;j++)
935 // A[j][i] = A[j-1][i-1]+k;
936 // then it is a bad order.
937 if (AR->getLoop() == OuterLoop) {
938 // We found an OuterLoop induction after InnerLoop induction. It is
940 FoundOuterInduction = true;
941 if (FoundInnerInduction) {
950 return GoodOrder - BadOrder;
953 static bool isProfitabileForVectorization(unsigned InnerLoopId,
954 unsigned OuterLoopId,
955 CharMatrix &DepMatrix) {
956 // TODO: Improve this heuristic to catch more cases.
957 // If the inner loop is loop independent or doesn't carry any dependency it is
958 // profitable to move this to outer position.
959 unsigned Row = DepMatrix.size();
960 for (unsigned i = 0; i < Row; ++i) {
961 if (DepMatrix[i][InnerLoopId] != 'S' && DepMatrix[i][InnerLoopId] != 'I')
963 // TODO: We need to improve this heuristic.
964 if (DepMatrix[i][OuterLoopId] != '=')
967 // If outer loop has dependence and inner loop is loop independent then it is
968 // profitable to interchange to enable parallelism.
972 bool LoopInterchangeProfitability::isProfitable(unsigned InnerLoopId,
973 unsigned OuterLoopId,
974 CharMatrix &DepMatrix) {
976 // TODO: Add better profitability checks.
978 // 1) Construct dependency matrix and move the one with no loop carried dep
979 // inside to enable vectorization.
981 // This is rough cost estimation algorithm. It counts the good and bad order
982 // of induction variables in the instruction and allows reordering if number
983 // of bad orders is more than good.
985 Cost += getInstrOrderCost();
986 DEBUG(dbgs() << "Cost = " << Cost << "\n");
990 // It is not profitable as per current cache profitability model. But check if
991 // we can move this loop outside to improve parallelism.
993 isProfitabileForVectorization(InnerLoopId, OuterLoopId, DepMatrix);
997 void LoopInterchangeTransform::removeChildLoop(Loop *OuterLoop,
999 for (Loop::iterator I = OuterLoop->begin(), E = OuterLoop->end(); I != E;
1001 if (*I == InnerLoop) {
1002 OuterLoop->removeChildLoop(I);
1006 llvm_unreachable("Couldn't find loop");
1009 void LoopInterchangeTransform::restructureLoops(Loop *InnerLoop,
1011 Loop *OuterLoopParent = OuterLoop->getParentLoop();
1012 if (OuterLoopParent) {
1013 // Remove the loop from its parent loop.
1014 removeChildLoop(OuterLoopParent, OuterLoop);
1015 removeChildLoop(OuterLoop, InnerLoop);
1016 OuterLoopParent->addChildLoop(InnerLoop);
1018 removeChildLoop(OuterLoop, InnerLoop);
1019 LI->changeTopLevelLoop(OuterLoop, InnerLoop);
1022 while (!InnerLoop->empty())
1023 OuterLoop->addChildLoop(InnerLoop->removeChildLoop(InnerLoop->begin()));
1025 InnerLoop->addChildLoop(OuterLoop);
1028 bool LoopInterchangeTransform::transform() {
1030 DEBUG(dbgs() << "transform\n");
1031 bool Transformed = false;
1032 Instruction *InnerIndexVar;
1034 if (InnerLoop->getSubLoops().size() == 0) {
1035 BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
1036 DEBUG(dbgs() << "Calling Split Inner Loop\n");
1037 PHINode *InductionPHI = getInductionVariable(InnerLoop, SE);
1038 if (!InductionPHI) {
1039 DEBUG(dbgs() << "Failed to find the point to split loop latch \n");
1043 if (InductionPHI->getIncomingBlock(0) == InnerLoopPreHeader)
1044 InnerIndexVar = dyn_cast<Instruction>(InductionPHI->getIncomingValue(1));
1046 InnerIndexVar = dyn_cast<Instruction>(InductionPHI->getIncomingValue(0));
1049 // Split at the place were the induction variable is
1050 // incremented/decremented.
1051 // TODO: This splitting logic may not work always. Fix this.
1052 splitInnerLoopLatch(InnerIndexVar);
1053 DEBUG(dbgs() << "splitInnerLoopLatch Done\n");
1055 // Splits the inner loops phi nodes out into a separate basic block.
1056 splitInnerLoopHeader();
1057 DEBUG(dbgs() << "splitInnerLoopHeader Done\n");
1060 Transformed |= adjustLoopLinks();
1062 DEBUG(dbgs() << "adjustLoopLinks Failed\n");
1066 restructureLoops(InnerLoop, OuterLoop);
1070 void LoopInterchangeTransform::splitInnerLoopLatch(Instruction *Inc) {
1071 BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch();
1072 BasicBlock *InnerLoopLatchPred = InnerLoopLatch;
1073 InnerLoopLatch = SplitBlock(InnerLoopLatchPred, Inc, DT, LI);
1076 void LoopInterchangeTransform::splitOuterLoopLatch() {
1077 BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch();
1078 BasicBlock *OuterLatchLcssaPhiBlock = OuterLoopLatch;
1079 OuterLoopLatch = SplitBlock(OuterLatchLcssaPhiBlock,
1080 OuterLoopLatch->getFirstNonPHI(), DT, LI);
1083 void LoopInterchangeTransform::splitInnerLoopHeader() {
1085 // Split the inner loop header out. Here make sure that the reduction PHI's
1086 // stay in the innerloop body.
1087 BasicBlock *InnerLoopHeader = InnerLoop->getHeader();
1088 BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
1089 if (InnerLoopHasReduction) {
1090 // FIXME: Check if the induction PHI will always be the first PHI.
1091 BasicBlock *New = InnerLoopHeader->splitBasicBlock(
1092 ++(InnerLoopHeader->begin()), InnerLoopHeader->getName() + ".split");
1094 if (Loop *L = LI->getLoopFor(InnerLoopHeader))
1095 L->addBasicBlockToLoop(New, *LI);
1097 // Adjust Reduction PHI's in the block.
1098 SmallVector<PHINode *, 8> PHIVec;
1099 for (auto I = New->begin(); isa<PHINode>(I); ++I) {
1100 PHINode *PHI = dyn_cast<PHINode>(I);
1101 Value *V = PHI->getIncomingValueForBlock(InnerLoopPreHeader);
1102 PHI->replaceAllUsesWith(V);
1103 PHIVec.push_back((PHI));
1105 for (auto I = PHIVec.begin(), E = PHIVec.end(); I != E; ++I) {
1107 P->eraseFromParent();
1110 SplitBlock(InnerLoopHeader, InnerLoopHeader->getFirstNonPHI(), DT, LI);
1113 DEBUG(dbgs() << "Output of splitInnerLoopHeader InnerLoopHeaderSucc & "
1114 "InnerLoopHeader \n");
1117 /// \brief Move all instructions except the terminator from FromBB right before
1119 static void moveBBContents(BasicBlock *FromBB, Instruction *InsertBefore) {
1120 auto &ToList = InsertBefore->getParent()->getInstList();
1121 auto &FromList = FromBB->getInstList();
1123 ToList.splice(InsertBefore->getIterator(), FromList, FromList.begin(),
1124 FromBB->getTerminator()->getIterator());
1127 void LoopInterchangeTransform::adjustOuterLoopPreheader() {
1128 BasicBlock *OuterLoopPreHeader = OuterLoop->getLoopPreheader();
1129 BasicBlock *InnerPreHeader = InnerLoop->getLoopPreheader();
1131 moveBBContents(OuterLoopPreHeader, InnerPreHeader->getTerminator());
1134 void LoopInterchangeTransform::adjustInnerLoopPreheader() {
1135 BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
1136 BasicBlock *OuterHeader = OuterLoop->getHeader();
1138 moveBBContents(InnerLoopPreHeader, OuterHeader->getTerminator());
1141 void LoopInterchangeTransform::updateIncomingBlock(BasicBlock *CurrBlock,
1142 BasicBlock *OldPred,
1143 BasicBlock *NewPred) {
1144 for (auto I = CurrBlock->begin(); isa<PHINode>(I); ++I) {
1145 PHINode *PHI = cast<PHINode>(I);
1146 unsigned Num = PHI->getNumIncomingValues();
1147 for (unsigned i = 0; i < Num; ++i) {
1148 if (PHI->getIncomingBlock(i) == OldPred)
1149 PHI->setIncomingBlock(i, NewPred);
1154 bool LoopInterchangeTransform::adjustLoopBranches() {
1156 DEBUG(dbgs() << "adjustLoopBranches called\n");
1157 // Adjust the loop preheader
1158 BasicBlock *InnerLoopHeader = InnerLoop->getHeader();
1159 BasicBlock *OuterLoopHeader = OuterLoop->getHeader();
1160 BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch();
1161 BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch();
1162 BasicBlock *OuterLoopPreHeader = OuterLoop->getLoopPreheader();
1163 BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
1164 BasicBlock *OuterLoopPredecessor = OuterLoopPreHeader->getUniquePredecessor();
1165 BasicBlock *InnerLoopLatchPredecessor =
1166 InnerLoopLatch->getUniquePredecessor();
1167 BasicBlock *InnerLoopLatchSuccessor;
1168 BasicBlock *OuterLoopLatchSuccessor;
1170 BranchInst *OuterLoopLatchBI =
1171 dyn_cast<BranchInst>(OuterLoopLatch->getTerminator());
1172 BranchInst *InnerLoopLatchBI =
1173 dyn_cast<BranchInst>(InnerLoopLatch->getTerminator());
1174 BranchInst *OuterLoopHeaderBI =
1175 dyn_cast<BranchInst>(OuterLoopHeader->getTerminator());
1176 BranchInst *InnerLoopHeaderBI =
1177 dyn_cast<BranchInst>(InnerLoopHeader->getTerminator());
1179 if (!OuterLoopPredecessor || !InnerLoopLatchPredecessor ||
1180 !OuterLoopLatchBI || !InnerLoopLatchBI || !OuterLoopHeaderBI ||
1184 BranchInst *InnerLoopLatchPredecessorBI =
1185 dyn_cast<BranchInst>(InnerLoopLatchPredecessor->getTerminator());
1186 BranchInst *OuterLoopPredecessorBI =
1187 dyn_cast<BranchInst>(OuterLoopPredecessor->getTerminator());
1189 if (!OuterLoopPredecessorBI || !InnerLoopLatchPredecessorBI)
1191 BasicBlock *InnerLoopHeaderSuccessor = InnerLoopHeader->getUniqueSuccessor();
1192 if (!InnerLoopHeaderSuccessor)
1195 // Adjust Loop Preheader and headers
1197 unsigned NumSucc = OuterLoopPredecessorBI->getNumSuccessors();
1198 for (unsigned i = 0; i < NumSucc; ++i) {
1199 if (OuterLoopPredecessorBI->getSuccessor(i) == OuterLoopPreHeader)
1200 OuterLoopPredecessorBI->setSuccessor(i, InnerLoopPreHeader);
1203 NumSucc = OuterLoopHeaderBI->getNumSuccessors();
1204 for (unsigned i = 0; i < NumSucc; ++i) {
1205 if (OuterLoopHeaderBI->getSuccessor(i) == OuterLoopLatch)
1206 OuterLoopHeaderBI->setSuccessor(i, LoopExit);
1207 else if (OuterLoopHeaderBI->getSuccessor(i) == InnerLoopPreHeader)
1208 OuterLoopHeaderBI->setSuccessor(i, InnerLoopHeaderSuccessor);
1211 // Adjust reduction PHI's now that the incoming block has changed.
1212 updateIncomingBlock(InnerLoopHeaderSuccessor, InnerLoopHeader,
1215 BranchInst::Create(OuterLoopPreHeader, InnerLoopHeaderBI);
1216 InnerLoopHeaderBI->eraseFromParent();
1218 // -------------Adjust loop latches-----------
1219 if (InnerLoopLatchBI->getSuccessor(0) == InnerLoopHeader)
1220 InnerLoopLatchSuccessor = InnerLoopLatchBI->getSuccessor(1);
1222 InnerLoopLatchSuccessor = InnerLoopLatchBI->getSuccessor(0);
1224 NumSucc = InnerLoopLatchPredecessorBI->getNumSuccessors();
1225 for (unsigned i = 0; i < NumSucc; ++i) {
1226 if (InnerLoopLatchPredecessorBI->getSuccessor(i) == InnerLoopLatch)
1227 InnerLoopLatchPredecessorBI->setSuccessor(i, InnerLoopLatchSuccessor);
1230 // Adjust PHI nodes in InnerLoopLatchSuccessor. Update all uses of PHI with
1231 // the value and remove this PHI node from inner loop.
1232 SmallVector<PHINode *, 8> LcssaVec;
1233 for (auto I = InnerLoopLatchSuccessor->begin(); isa<PHINode>(I); ++I) {
1234 PHINode *LcssaPhi = cast<PHINode>(I);
1235 LcssaVec.push_back(LcssaPhi);
1237 for (auto I = LcssaVec.begin(), E = LcssaVec.end(); I != E; ++I) {
1239 Value *Incoming = P->getIncomingValueForBlock(InnerLoopLatch);
1240 P->replaceAllUsesWith(Incoming);
1241 P->eraseFromParent();
1244 if (OuterLoopLatchBI->getSuccessor(0) == OuterLoopHeader)
1245 OuterLoopLatchSuccessor = OuterLoopLatchBI->getSuccessor(1);
1247 OuterLoopLatchSuccessor = OuterLoopLatchBI->getSuccessor(0);
1249 if (InnerLoopLatchBI->getSuccessor(1) == InnerLoopLatchSuccessor)
1250 InnerLoopLatchBI->setSuccessor(1, OuterLoopLatchSuccessor);
1252 InnerLoopLatchBI->setSuccessor(0, OuterLoopLatchSuccessor);
1254 updateIncomingBlock(OuterLoopLatchSuccessor, OuterLoopLatch, InnerLoopLatch);
1256 if (OuterLoopLatchBI->getSuccessor(0) == OuterLoopLatchSuccessor) {
1257 OuterLoopLatchBI->setSuccessor(0, InnerLoopLatch);
1259 OuterLoopLatchBI->setSuccessor(1, InnerLoopLatch);
1264 void LoopInterchangeTransform::adjustLoopPreheaders() {
1266 // We have interchanged the preheaders so we need to interchange the data in
1267 // the preheader as well.
1268 // This is because the content of inner preheader was previously executed
1269 // inside the outer loop.
1270 BasicBlock *OuterLoopPreHeader = OuterLoop->getLoopPreheader();
1271 BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
1272 BasicBlock *OuterLoopHeader = OuterLoop->getHeader();
1273 BranchInst *InnerTermBI =
1274 cast<BranchInst>(InnerLoopPreHeader->getTerminator());
1276 // These instructions should now be executed inside the loop.
1277 // Move instruction into a new block after outer header.
1278 moveBBContents(InnerLoopPreHeader, OuterLoopHeader->getTerminator());
1279 // These instructions were not executed previously in the loop so move them to
1280 // the older inner loop preheader.
1281 moveBBContents(OuterLoopPreHeader, InnerTermBI);
1284 bool LoopInterchangeTransform::adjustLoopLinks() {
1286 // Adjust all branches in the inner and outer loop.
1287 bool Changed = adjustLoopBranches();
1289 adjustLoopPreheaders();
1293 char LoopInterchange::ID = 0;
1294 INITIALIZE_PASS_BEGIN(LoopInterchange, "loop-interchange",
1295 "Interchanges loops for cache reuse", false, false)
1296 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
1297 INITIALIZE_PASS_DEPENDENCY(DependenceAnalysis)
1298 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
1299 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
1300 INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
1301 INITIALIZE_PASS_DEPENDENCY(LCSSA)
1302 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
1304 INITIALIZE_PASS_END(LoopInterchange, "loop-interchange",
1305 "Interchanges loops for cache reuse", false, false)
1307 Pass *llvm::createLoopInterchangePass() { return new LoopInterchange(); }