1 //===- LoopInterchange.cpp - Loop interchange pass-------------------------===//
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
9 // This Pass handles loop interchange transform.
10 // This pass interchanges loops to provide a more cache-friendly memory access
13 //===----------------------------------------------------------------------===//
15 #include "llvm/ADT/STLExtras.h"
16 #include "llvm/ADT/SmallVector.h"
17 #include "llvm/ADT/Statistic.h"
18 #include "llvm/ADT/StringRef.h"
19 #include "llvm/Analysis/DependenceAnalysis.h"
20 #include "llvm/Analysis/LoopInfo.h"
21 #include "llvm/Analysis/LoopPass.h"
22 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
23 #include "llvm/Analysis/ScalarEvolution.h"
24 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
25 #include "llvm/IR/BasicBlock.h"
26 #include "llvm/IR/Constants.h"
27 #include "llvm/IR/DiagnosticInfo.h"
28 #include "llvm/IR/Dominators.h"
29 #include "llvm/IR/Function.h"
30 #include "llvm/IR/InstrTypes.h"
31 #include "llvm/IR/Instruction.h"
32 #include "llvm/IR/Instructions.h"
33 #include "llvm/IR/Type.h"
34 #include "llvm/IR/User.h"
35 #include "llvm/IR/Value.h"
36 #include "llvm/InitializePasses.h"
37 #include "llvm/Pass.h"
38 #include "llvm/Support/Casting.h"
39 #include "llvm/Support/CommandLine.h"
40 #include "llvm/Support/Debug.h"
41 #include "llvm/Support/ErrorHandling.h"
42 #include "llvm/Support/raw_ostream.h"
43 #include "llvm/Transforms/Scalar.h"
44 #include "llvm/Transforms/Utils.h"
45 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
46 #include "llvm/Transforms/Utils/LoopUtils.h"
53 #define DEBUG_TYPE "loop-interchange"
55 STATISTIC(LoopsInterchanged, "Number of loops interchanged");
57 static cl::opt<int> LoopInterchangeCostThreshold(
58 "loop-interchange-threshold", cl::init(0), cl::Hidden,
59 cl::desc("Interchange if you gain more than this number"));
63 using LoopVector = SmallVector<Loop *, 8>;
65 // TODO: Check if we can use a sparse matrix here.
66 using CharMatrix = std::vector<std::vector<char>>;
68 } // end anonymous namespace
70 // Maximum number of dependencies that can be handled in the dependency matrix.
71 static const unsigned MaxMemInstrCount = 100;
73 // Maximum loop depth supported.
74 static const unsigned MaxLoopNestDepth = 10;
76 #ifdef DUMP_DEP_MATRICIES
77 static void printDepMatrix(CharMatrix &DepMatrix) {
78 for (auto &Row : DepMatrix) {
80 LLVM_DEBUG(dbgs() << D << " ");
81 LLVM_DEBUG(dbgs() << "\n");
86 static bool populateDependencyMatrix(CharMatrix &DepMatrix, unsigned Level,
87 Loop *L, DependenceInfo *DI) {
88 using ValueVector = SmallVector<Value *, 16>;
93 for (BasicBlock *BB : L->blocks()) {
94 // Scan the BB and collect legal loads and stores.
95 for (Instruction &I : *BB) {
96 if (!isa<Instruction>(I))
98 if (auto *Ld = dyn_cast<LoadInst>(&I)) {
101 MemInstr.push_back(&I);
102 } else if (auto *St = dyn_cast<StoreInst>(&I)) {
105 MemInstr.push_back(&I);
110 LLVM_DEBUG(dbgs() << "Found " << MemInstr.size()
111 << " Loads and Stores to analyze\n");
113 ValueVector::iterator I, IE, J, JE;
115 for (I = MemInstr.begin(), IE = MemInstr.end(); I != IE; ++I) {
116 for (J = I, JE = MemInstr.end(); J != JE; ++J) {
117 std::vector<char> Dep;
118 Instruction *Src = cast<Instruction>(*I);
119 Instruction *Dst = cast<Instruction>(*J);
122 // Ignore Input dependencies.
123 if (isa<LoadInst>(Src) && isa<LoadInst>(Dst))
125 // Track Output, Flow, and Anti dependencies.
126 if (auto D = DI->depends(Src, Dst, true)) {
127 assert(D->isOrdered() && "Expected an output, flow or anti dep.");
128 LLVM_DEBUG(StringRef DepType =
129 D->isFlow() ? "flow" : D->isAnti() ? "anti" : "output";
130 dbgs() << "Found " << DepType
131 << " dependency between Src and Dst\n"
132 << " Src:" << *Src << "\n Dst:" << *Dst << '\n');
133 unsigned Levels = D->getLevels();
135 for (unsigned II = 1; II <= Levels; ++II) {
136 const SCEV *Distance = D->getDistance(II);
137 const SCEVConstant *SCEVConst =
138 dyn_cast_or_null<SCEVConstant>(Distance);
140 const ConstantInt *CI = SCEVConst->getValue();
141 if (CI->isNegative())
143 else if (CI->isZero())
147 Dep.push_back(Direction);
148 } else if (D->isScalar(II)) {
150 Dep.push_back(Direction);
152 unsigned Dir = D->getDirection(II);
153 if (Dir == Dependence::DVEntry::LT ||
154 Dir == Dependence::DVEntry::LE)
156 else if (Dir == Dependence::DVEntry::GT ||
157 Dir == Dependence::DVEntry::GE)
159 else if (Dir == Dependence::DVEntry::EQ)
163 Dep.push_back(Direction);
166 while (Dep.size() != Level) {
170 DepMatrix.push_back(Dep);
171 if (DepMatrix.size() > MaxMemInstrCount) {
172 LLVM_DEBUG(dbgs() << "Cannot handle more than " << MaxMemInstrCount
173 << " dependencies inside loop\n");
183 // A loop is moved from index 'from' to an index 'to'. Update the Dependence
184 // matrix by exchanging the two columns.
185 static void interChangeDependencies(CharMatrix &DepMatrix, unsigned FromIndx,
187 unsigned numRows = DepMatrix.size();
188 for (unsigned i = 0; i < numRows; ++i) {
189 char TmpVal = DepMatrix[i][ToIndx];
190 DepMatrix[i][ToIndx] = DepMatrix[i][FromIndx];
191 DepMatrix[i][FromIndx] = TmpVal;
195 // Checks if outermost non '=','S'or'I' dependence in the dependence matrix is
197 static bool isOuterMostDepPositive(CharMatrix &DepMatrix, unsigned Row,
199 for (unsigned i = 0; i <= Column; ++i) {
200 if (DepMatrix[Row][i] == '<')
202 if (DepMatrix[Row][i] == '>')
205 // All dependencies were '=','S' or 'I'
209 // Checks if no dependence exist in the dependency matrix in Row before Column.
210 static bool containsNoDependence(CharMatrix &DepMatrix, unsigned Row,
212 for (unsigned i = 0; i < Column; ++i) {
213 if (DepMatrix[Row][i] != '=' && DepMatrix[Row][i] != 'S' &&
214 DepMatrix[Row][i] != 'I')
220 static bool validDepInterchange(CharMatrix &DepMatrix, unsigned Row,
221 unsigned OuterLoopId, char InnerDep,
223 if (isOuterMostDepPositive(DepMatrix, Row, OuterLoopId))
226 if (InnerDep == OuterDep)
229 // It is legal to interchange if and only if after interchange no row has a
230 // '>' direction as the leftmost non-'='.
232 if (InnerDep == '=' || InnerDep == 'S' || InnerDep == 'I')
238 if (InnerDep == '>') {
239 // If OuterLoopId represents outermost loop then interchanging will make the
240 // 1st dependency as '>'
241 if (OuterLoopId == 0)
244 // If all dependencies before OuterloopId are '=','S'or 'I'. Then
245 // interchanging will result in this row having an outermost non '='
247 if (!containsNoDependence(DepMatrix, Row, OuterLoopId))
254 // Checks if it is legal to interchange 2 loops.
255 // [Theorem] A permutation of the loops in a perfect nest is legal if and only
256 // if the direction matrix, after the same permutation is applied to its
257 // columns, has no ">" direction as the leftmost non-"=" direction in any row.
258 static bool isLegalToInterChangeLoops(CharMatrix &DepMatrix,
259 unsigned InnerLoopId,
260 unsigned OuterLoopId) {
261 unsigned NumRows = DepMatrix.size();
262 // For each row check if it is valid to interchange.
263 for (unsigned Row = 0; Row < NumRows; ++Row) {
264 char InnerDep = DepMatrix[Row][InnerLoopId];
265 char OuterDep = DepMatrix[Row][OuterLoopId];
266 if (InnerDep == '*' || OuterDep == '*')
268 if (!validDepInterchange(DepMatrix, Row, OuterLoopId, InnerDep, OuterDep))
274 static LoopVector populateWorklist(Loop &L) {
275 LLVM_DEBUG(dbgs() << "Calling populateWorklist on Func: "
276 << L.getHeader()->getParent()->getName() << " Loop: %"
277 << L.getHeader()->getName() << '\n');
279 Loop *CurrentLoop = &L;
280 const std::vector<Loop *> *Vec = &CurrentLoop->getSubLoops();
281 while (!Vec->empty()) {
282 // The current loop has multiple subloops in it hence it is not tightly
284 // Discard all loops above it added into Worklist.
285 if (Vec->size() != 1)
288 LoopList.push_back(CurrentLoop);
289 CurrentLoop = Vec->front();
290 Vec = &CurrentLoop->getSubLoops();
292 LoopList.push_back(CurrentLoop);
296 static PHINode *getInductionVariable(Loop *L, ScalarEvolution *SE) {
297 PHINode *InnerIndexVar = L->getCanonicalInductionVariable();
299 return InnerIndexVar;
300 if (L->getLoopLatch() == nullptr || L->getLoopPredecessor() == nullptr)
302 for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) {
303 PHINode *PhiVar = cast<PHINode>(I);
304 Type *PhiTy = PhiVar->getType();
305 if (!PhiTy->isIntegerTy() && !PhiTy->isFloatingPointTy() &&
306 !PhiTy->isPointerTy())
308 const SCEVAddRecExpr *AddRec =
309 dyn_cast<SCEVAddRecExpr>(SE->getSCEV(PhiVar));
310 if (!AddRec || !AddRec->isAffine())
312 const SCEV *Step = AddRec->getStepRecurrence(*SE);
313 if (!isa<SCEVConstant>(Step))
315 // Found the induction variable.
316 // FIXME: Handle loops with more than one induction variable. Note that,
317 // currently, legality makes sure we have only one induction variable.
325 /// LoopInterchangeLegality checks if it is legal to interchange the loop.
326 class LoopInterchangeLegality {
328 LoopInterchangeLegality(Loop *Outer, Loop *Inner, ScalarEvolution *SE,
329 OptimizationRemarkEmitter *ORE)
330 : OuterLoop(Outer), InnerLoop(Inner), SE(SE), ORE(ORE) {}
332 /// Check if the loops can be interchanged.
333 bool canInterchangeLoops(unsigned InnerLoopId, unsigned OuterLoopId,
334 CharMatrix &DepMatrix);
336 /// Check if the loop structure is understood. We do not handle triangular
338 bool isLoopStructureUnderstood(PHINode *InnerInductionVar);
340 bool currentLimitations();
342 const SmallPtrSetImpl<PHINode *> &getOuterInnerReductions() const {
343 return OuterInnerReductions;
347 bool tightlyNested(Loop *Outer, Loop *Inner);
348 bool containsUnsafeInstructions(BasicBlock *BB);
350 /// Discover induction and reduction PHIs in the header of \p L. Induction
351 /// PHIs are added to \p Inductions, reductions are added to
352 /// OuterInnerReductions. When the outer loop is passed, the inner loop needs
353 /// to be passed as \p InnerLoop.
354 bool findInductionAndReductions(Loop *L,
355 SmallVector<PHINode *, 8> &Inductions,
363 /// Interface to emit optimization remarks.
364 OptimizationRemarkEmitter *ORE;
366 /// Set of reduction PHIs taking part of a reduction across the inner and
368 SmallPtrSet<PHINode *, 4> OuterInnerReductions;
371 /// LoopInterchangeProfitability checks if it is profitable to interchange the
373 class LoopInterchangeProfitability {
375 LoopInterchangeProfitability(Loop *Outer, Loop *Inner, ScalarEvolution *SE,
376 OptimizationRemarkEmitter *ORE)
377 : OuterLoop(Outer), InnerLoop(Inner), SE(SE), ORE(ORE) {}
379 /// Check if the loop interchange is profitable.
380 bool isProfitable(unsigned InnerLoopId, unsigned OuterLoopId,
381 CharMatrix &DepMatrix);
384 int getInstrOrderCost();
392 /// Interface to emit optimization remarks.
393 OptimizationRemarkEmitter *ORE;
396 /// LoopInterchangeTransform interchanges the loop.
397 class LoopInterchangeTransform {
399 LoopInterchangeTransform(Loop *Outer, Loop *Inner, ScalarEvolution *SE,
400 LoopInfo *LI, DominatorTree *DT,
401 BasicBlock *LoopNestExit,
402 const LoopInterchangeLegality &LIL)
403 : OuterLoop(Outer), InnerLoop(Inner), SE(SE), LI(LI), DT(DT),
404 LoopExit(LoopNestExit), LIL(LIL) {}
406 /// Interchange OuterLoop and InnerLoop.
408 void restructureLoops(Loop *NewInner, Loop *NewOuter,
409 BasicBlock *OrigInnerPreHeader,
410 BasicBlock *OrigOuterPreHeader);
411 void removeChildLoop(Loop *OuterLoop, Loop *InnerLoop);
414 bool adjustLoopLinks();
415 void adjustLoopPreheaders();
416 bool adjustLoopBranches();
426 BasicBlock *LoopExit;
428 const LoopInterchangeLegality &LIL;
431 // Main LoopInterchange Pass.
432 struct LoopInterchange : public LoopPass {
434 ScalarEvolution *SE = nullptr;
435 LoopInfo *LI = nullptr;
436 DependenceInfo *DI = nullptr;
437 DominatorTree *DT = nullptr;
439 /// Interface to emit optimization remarks.
440 OptimizationRemarkEmitter *ORE;
442 LoopInterchange() : LoopPass(ID) {
443 initializeLoopInterchangePass(*PassRegistry::getPassRegistry());
446 void getAnalysisUsage(AnalysisUsage &AU) const override {
447 AU.addRequired<DependenceAnalysisWrapperPass>();
448 AU.addRequired<OptimizationRemarkEmitterWrapperPass>();
450 getLoopAnalysisUsage(AU);
453 bool runOnLoop(Loop *L, LPPassManager &LPM) override {
454 if (skipLoop(L) || L->getParentLoop())
457 SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
458 LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
459 DI = &getAnalysis<DependenceAnalysisWrapperPass>().getDI();
460 DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
461 ORE = &getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE();
463 return processLoopList(populateWorklist(*L));
466 bool isComputableLoopNest(LoopVector LoopList) {
467 for (Loop *L : LoopList) {
468 const SCEV *ExitCountOuter = SE->getBackedgeTakenCount(L);
469 if (ExitCountOuter == SE->getCouldNotCompute()) {
470 LLVM_DEBUG(dbgs() << "Couldn't compute backedge count\n");
473 if (L->getNumBackEdges() != 1) {
474 LLVM_DEBUG(dbgs() << "NumBackEdges is not equal to 1\n");
477 if (!L->getExitingBlock()) {
478 LLVM_DEBUG(dbgs() << "Loop doesn't have unique exit block\n");
485 unsigned selectLoopForInterchange(const LoopVector &LoopList) {
486 // TODO: Add a better heuristic to select the loop to be interchanged based
487 // on the dependence matrix. Currently we select the innermost loop.
488 return LoopList.size() - 1;
491 bool processLoopList(LoopVector LoopList) {
492 bool Changed = false;
493 unsigned LoopNestDepth = LoopList.size();
494 if (LoopNestDepth < 2) {
495 LLVM_DEBUG(dbgs() << "Loop doesn't contain minimum nesting level.\n");
498 if (LoopNestDepth > MaxLoopNestDepth) {
499 LLVM_DEBUG(dbgs() << "Cannot handle loops of depth greater than "
500 << MaxLoopNestDepth << "\n");
503 if (!isComputableLoopNest(LoopList)) {
504 LLVM_DEBUG(dbgs() << "Not valid loop candidate for interchange\n");
508 LLVM_DEBUG(dbgs() << "Processing LoopList of size = " << LoopNestDepth
511 CharMatrix DependencyMatrix;
512 Loop *OuterMostLoop = *(LoopList.begin());
513 if (!populateDependencyMatrix(DependencyMatrix, LoopNestDepth,
514 OuterMostLoop, DI)) {
515 LLVM_DEBUG(dbgs() << "Populating dependency matrix failed\n");
518 #ifdef DUMP_DEP_MATRICIES
519 LLVM_DEBUG(dbgs() << "Dependence before interchange\n");
520 printDepMatrix(DependencyMatrix);
523 // Get the Outermost loop exit.
524 BasicBlock *LoopNestExit = OuterMostLoop->getExitBlock();
526 LLVM_DEBUG(dbgs() << "OuterMostLoop needs an unique exit block");
530 unsigned SelecLoopId = selectLoopForInterchange(LoopList);
531 // Move the selected loop outwards to the best possible position.
532 for (unsigned i = SelecLoopId; i > 0; i--) {
534 processLoop(LoopList, i, i - 1, LoopNestExit, DependencyMatrix);
537 // Loops interchanged reflect the same in LoopList
538 std::swap(LoopList[i - 1], LoopList[i]);
540 // Update the DependencyMatrix
541 interChangeDependencies(DependencyMatrix, i, i - 1);
542 #ifdef DUMP_DEP_MATRICIES
543 LLVM_DEBUG(dbgs() << "Dependence after interchange\n");
544 printDepMatrix(DependencyMatrix);
546 Changed |= Interchanged;
551 bool processLoop(LoopVector LoopList, unsigned InnerLoopId,
552 unsigned OuterLoopId, BasicBlock *LoopNestExit,
553 std::vector<std::vector<char>> &DependencyMatrix) {
554 LLVM_DEBUG(dbgs() << "Processing Inner Loop Id = " << InnerLoopId
555 << " and OuterLoopId = " << OuterLoopId << "\n");
556 Loop *InnerLoop = LoopList[InnerLoopId];
557 Loop *OuterLoop = LoopList[OuterLoopId];
559 LoopInterchangeLegality LIL(OuterLoop, InnerLoop, SE, ORE);
560 if (!LIL.canInterchangeLoops(InnerLoopId, OuterLoopId, DependencyMatrix)) {
561 LLVM_DEBUG(dbgs() << "Not interchanging loops. Cannot prove legality.\n");
564 LLVM_DEBUG(dbgs() << "Loops are legal to interchange\n");
565 LoopInterchangeProfitability LIP(OuterLoop, InnerLoop, SE, ORE);
566 if (!LIP.isProfitable(InnerLoopId, OuterLoopId, DependencyMatrix)) {
567 LLVM_DEBUG(dbgs() << "Interchanging loops not profitable.\n");
572 return OptimizationRemark(DEBUG_TYPE, "Interchanged",
573 InnerLoop->getStartLoc(),
574 InnerLoop->getHeader())
575 << "Loop interchanged with enclosing loop.";
578 LoopInterchangeTransform LIT(OuterLoop, InnerLoop, SE, LI, DT, LoopNestExit,
581 LLVM_DEBUG(dbgs() << "Loops interchanged.\n");
587 } // end anonymous namespace
589 bool LoopInterchangeLegality::containsUnsafeInstructions(BasicBlock *BB) {
590 return any_of(*BB, [](const Instruction &I) {
591 return I.mayHaveSideEffects() || I.mayReadFromMemory();
595 bool LoopInterchangeLegality::tightlyNested(Loop *OuterLoop, Loop *InnerLoop) {
596 BasicBlock *OuterLoopHeader = OuterLoop->getHeader();
597 BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
598 BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch();
600 LLVM_DEBUG(dbgs() << "Checking if loops are tightly nested\n");
602 // A perfectly nested loop will not have any branch in between the outer and
603 // inner block i.e. outer header will branch to either inner preheader and
605 BranchInst *OuterLoopHeaderBI =
606 dyn_cast<BranchInst>(OuterLoopHeader->getTerminator());
607 if (!OuterLoopHeaderBI)
610 for (BasicBlock *Succ : successors(OuterLoopHeaderBI))
611 if (Succ != InnerLoopPreHeader && Succ != InnerLoop->getHeader() &&
612 Succ != OuterLoopLatch)
615 LLVM_DEBUG(dbgs() << "Checking instructions in Loop header and Loop latch\n");
616 // We do not have any basic block in between now make sure the outer header
617 // and outer loop latch doesn't contain any unsafe instructions.
618 if (containsUnsafeInstructions(OuterLoopHeader) ||
619 containsUnsafeInstructions(OuterLoopLatch))
622 LLVM_DEBUG(dbgs() << "Loops are perfectly nested\n");
623 // We have a perfect loop nest.
627 bool LoopInterchangeLegality::isLoopStructureUnderstood(
628 PHINode *InnerInduction) {
629 unsigned Num = InnerInduction->getNumOperands();
630 BasicBlock *InnerLoopPreheader = InnerLoop->getLoopPreheader();
631 for (unsigned i = 0; i < Num; ++i) {
632 Value *Val = InnerInduction->getOperand(i);
633 if (isa<Constant>(Val))
635 Instruction *I = dyn_cast<Instruction>(Val);
638 // TODO: Handle triangular loops.
639 // e.g. for(int i=0;i<N;i++)
640 // for(int j=i;j<N;j++)
641 unsigned IncomBlockIndx = PHINode::getIncomingValueNumForOperand(i);
642 if (InnerInduction->getIncomingBlock(IncomBlockIndx) ==
643 InnerLoopPreheader &&
644 !OuterLoop->isLoopInvariant(I)) {
651 // If SV is a LCSSA PHI node with a single incoming value, return the incoming
653 static Value *followLCSSA(Value *SV) {
654 PHINode *PHI = dyn_cast<PHINode>(SV);
658 if (PHI->getNumIncomingValues() != 1)
660 return followLCSSA(PHI->getIncomingValue(0));
663 // Check V's users to see if it is involved in a reduction in L.
664 static PHINode *findInnerReductionPhi(Loop *L, Value *V) {
665 for (Value *User : V->users()) {
666 if (PHINode *PHI = dyn_cast<PHINode>(User)) {
667 if (PHI->getNumIncomingValues() == 1)
669 RecurrenceDescriptor RD;
670 if (RecurrenceDescriptor::isReductionPHI(PHI, L, RD))
679 bool LoopInterchangeLegality::findInductionAndReductions(
680 Loop *L, SmallVector<PHINode *, 8> &Inductions, Loop *InnerLoop) {
681 if (!L->getLoopLatch() || !L->getLoopPredecessor())
683 for (PHINode &PHI : L->getHeader()->phis()) {
684 RecurrenceDescriptor RD;
685 InductionDescriptor ID;
686 if (InductionDescriptor::isInductionPHI(&PHI, L, SE, ID))
687 Inductions.push_back(&PHI);
689 // PHIs in inner loops need to be part of a reduction in the outer loop,
690 // discovered when checking the PHIs of the outer loop earlier.
692 if (OuterInnerReductions.find(&PHI) == OuterInnerReductions.end()) {
693 LLVM_DEBUG(dbgs() << "Inner loop PHI is not part of reductions "
694 "across the outer loop.\n");
698 assert(PHI.getNumIncomingValues() == 2 &&
699 "Phis in loop header should have exactly 2 incoming values");
700 // Check if we have a PHI node in the outer loop that has a reduction
701 // result from the inner loop as an incoming value.
702 Value *V = followLCSSA(PHI.getIncomingValueForBlock(L->getLoopLatch()));
703 PHINode *InnerRedPhi = findInnerReductionPhi(InnerLoop, V);
705 !llvm::any_of(InnerRedPhi->incoming_values(),
706 [&PHI](Value *V) { return V == &PHI; })) {
709 << "Failed to recognize PHI as an induction or reduction.\n");
712 OuterInnerReductions.insert(&PHI);
713 OuterInnerReductions.insert(InnerRedPhi);
720 // This function indicates the current limitations in the transform as a result
721 // of which we do not proceed.
722 bool LoopInterchangeLegality::currentLimitations() {
723 BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
724 BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch();
726 // transform currently expects the loop latches to also be the exiting
728 if (InnerLoop->getExitingBlock() != InnerLoopLatch ||
729 OuterLoop->getExitingBlock() != OuterLoop->getLoopLatch() ||
730 !isa<BranchInst>(InnerLoopLatch->getTerminator()) ||
731 !isa<BranchInst>(OuterLoop->getLoopLatch()->getTerminator())) {
733 dbgs() << "Loops where the latch is not the exiting block are not"
734 << " supported currently.\n");
736 return OptimizationRemarkMissed(DEBUG_TYPE, "ExitingNotLatch",
737 OuterLoop->getStartLoc(),
738 OuterLoop->getHeader())
739 << "Loops where the latch is not the exiting block cannot be"
740 " interchange currently.";
745 PHINode *InnerInductionVar;
746 SmallVector<PHINode *, 8> Inductions;
747 if (!findInductionAndReductions(OuterLoop, Inductions, InnerLoop)) {
749 dbgs() << "Only outer loops with induction or reduction PHI nodes "
750 << "are supported currently.\n");
752 return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedPHIOuter",
753 OuterLoop->getStartLoc(),
754 OuterLoop->getHeader())
755 << "Only outer loops with induction or reduction PHI nodes can be"
756 " interchanged currently.";
761 // TODO: Currently we handle only loops with 1 induction variable.
762 if (Inductions.size() != 1) {
763 LLVM_DEBUG(dbgs() << "Loops with more than 1 induction variables are not "
764 << "supported currently.\n");
766 return OptimizationRemarkMissed(DEBUG_TYPE, "MultiIndutionOuter",
767 OuterLoop->getStartLoc(),
768 OuterLoop->getHeader())
769 << "Only outer loops with 1 induction variable can be "
770 "interchanged currently.";
776 if (!findInductionAndReductions(InnerLoop, Inductions, nullptr)) {
778 dbgs() << "Only inner loops with induction or reduction PHI nodes "
779 << "are supported currently.\n");
781 return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedPHIInner",
782 InnerLoop->getStartLoc(),
783 InnerLoop->getHeader())
784 << "Only inner loops with induction or reduction PHI nodes can be"
785 " interchange currently.";
790 // TODO: Currently we handle only loops with 1 induction variable.
791 if (Inductions.size() != 1) {
793 dbgs() << "We currently only support loops with 1 induction variable."
794 << "Failed to interchange due to current limitation\n");
796 return OptimizationRemarkMissed(DEBUG_TYPE, "MultiInductionInner",
797 InnerLoop->getStartLoc(),
798 InnerLoop->getHeader())
799 << "Only inner loops with 1 induction variable can be "
800 "interchanged currently.";
804 InnerInductionVar = Inductions.pop_back_val();
806 // TODO: Triangular loops are not handled for now.
807 if (!isLoopStructureUnderstood(InnerInductionVar)) {
808 LLVM_DEBUG(dbgs() << "Loop structure not understood by pass\n");
810 return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedStructureInner",
811 InnerLoop->getStartLoc(),
812 InnerLoop->getHeader())
813 << "Inner loop structure not understood currently.";
818 // TODO: Current limitation: Since we split the inner loop latch at the point
819 // were induction variable is incremented (induction.next); We cannot have
820 // more than 1 user of induction.next since it would result in broken code
823 // for(i=0;i<N;i++) {
824 // for(j = 0;j<M;j++) {
825 // A[j+1][i+2] = A[j][i]+k;
828 Instruction *InnerIndexVarInc = nullptr;
829 if (InnerInductionVar->getIncomingBlock(0) == InnerLoopPreHeader)
831 dyn_cast<Instruction>(InnerInductionVar->getIncomingValue(1));
834 dyn_cast<Instruction>(InnerInductionVar->getIncomingValue(0));
836 if (!InnerIndexVarInc) {
838 dbgs() << "Did not find an instruction to increment the induction "
841 return OptimizationRemarkMissed(DEBUG_TYPE, "NoIncrementInInner",
842 InnerLoop->getStartLoc(),
843 InnerLoop->getHeader())
844 << "The inner loop does not increment the induction variable.";
849 // Since we split the inner loop latch on this induction variable. Make sure
850 // we do not have any instruction between the induction variable and branch
853 bool FoundInduction = false;
854 for (const Instruction &I :
855 llvm::reverse(InnerLoopLatch->instructionsWithoutDebug())) {
856 if (isa<BranchInst>(I) || isa<CmpInst>(I) || isa<TruncInst>(I) ||
860 // We found an instruction. If this is not induction variable then it is not
861 // safe to split this loop latch.
862 if (!I.isIdenticalTo(InnerIndexVarInc)) {
863 LLVM_DEBUG(dbgs() << "Found unsupported instructions between induction "
864 << "variable increment and branch.\n");
866 return OptimizationRemarkMissed(
867 DEBUG_TYPE, "UnsupportedInsBetweenInduction",
868 InnerLoop->getStartLoc(), InnerLoop->getHeader())
869 << "Found unsupported instruction between induction variable "
870 "increment and branch.";
875 FoundInduction = true;
878 // The loop latch ended and we didn't find the induction variable return as
879 // current limitation.
880 if (!FoundInduction) {
881 LLVM_DEBUG(dbgs() << "Did not find the induction variable.\n");
883 return OptimizationRemarkMissed(DEBUG_TYPE, "NoIndutionVariable",
884 InnerLoop->getStartLoc(),
885 InnerLoop->getHeader())
886 << "Did not find the induction variable.";
893 // We currently only support LCSSA PHI nodes in the inner loop exit, if their
894 // users are either reduction PHIs or PHIs outside the outer loop (which means
895 // the we are only interested in the final value after the loop).
897 areInnerLoopExitPHIsSupported(Loop *InnerL, Loop *OuterL,
898 SmallPtrSetImpl<PHINode *> &Reductions) {
899 BasicBlock *InnerExit = OuterL->getUniqueExitBlock();
900 for (PHINode &PHI : InnerExit->phis()) {
901 // Reduction lcssa phi will have only 1 incoming block that from loop latch.
902 if (PHI.getNumIncomingValues() > 1)
904 if (any_of(PHI.users(), [&Reductions, OuterL](User *U) {
905 PHINode *PN = dyn_cast<PHINode>(U);
906 return !PN || (Reductions.find(PN) == Reductions.end() &&
907 OuterL->contains(PN->getParent()));
915 // We currently support LCSSA PHI nodes in the outer loop exit, if their
916 // incoming values do not come from the outer loop latch or if the
917 // outer loop latch has a single predecessor. In that case, the value will
918 // be available if both the inner and outer loop conditions are true, which
919 // will still be true after interchanging. If we have multiple predecessor,
920 // that may not be the case, e.g. because the outer loop latch may be executed
921 // if the inner loop is not executed.
922 static bool areOuterLoopExitPHIsSupported(Loop *OuterLoop, Loop *InnerLoop) {
923 BasicBlock *LoopNestExit = OuterLoop->getUniqueExitBlock();
924 for (PHINode &PHI : LoopNestExit->phis()) {
925 // FIXME: We currently are not able to detect floating point reductions
926 // and have to use floating point PHIs as a proxy to prevent
927 // interchanging in the presence of floating point reductions.
928 if (PHI.getType()->isFloatingPointTy())
930 for (unsigned i = 0; i < PHI.getNumIncomingValues(); i++) {
931 Instruction *IncomingI = dyn_cast<Instruction>(PHI.getIncomingValue(i));
932 if (!IncomingI || IncomingI->getParent() != OuterLoop->getLoopLatch())
935 // The incoming value is defined in the outer loop latch. Currently we
936 // only support that in case the outer loop latch has a single predecessor.
937 // This guarantees that the outer loop latch is executed if and only if
938 // the inner loop is executed (because tightlyNested() guarantees that the
939 // outer loop header only branches to the inner loop or the outer loop
941 // FIXME: We could weaken this logic and allow multiple predecessors,
942 // if the values are produced outside the loop latch. We would need
943 // additional logic to update the PHI nodes in the exit block as
945 if (OuterLoop->getLoopLatch()->getUniquePredecessor() == nullptr)
952 bool LoopInterchangeLegality::canInterchangeLoops(unsigned InnerLoopId,
953 unsigned OuterLoopId,
954 CharMatrix &DepMatrix) {
955 if (!isLegalToInterChangeLoops(DepMatrix, InnerLoopId, OuterLoopId)) {
956 LLVM_DEBUG(dbgs() << "Failed interchange InnerLoopId = " << InnerLoopId
957 << " and OuterLoopId = " << OuterLoopId
958 << " due to dependence\n");
960 return OptimizationRemarkMissed(DEBUG_TYPE, "Dependence",
961 InnerLoop->getStartLoc(),
962 InnerLoop->getHeader())
963 << "Cannot interchange loops due to dependences.";
967 // Check if outer and inner loop contain legal instructions only.
968 for (auto *BB : OuterLoop->blocks())
969 for (Instruction &I : BB->instructionsWithoutDebug())
970 if (CallInst *CI = dyn_cast<CallInst>(&I)) {
971 // readnone functions do not prevent interchanging.
972 if (CI->doesNotReadMemory())
975 dbgs() << "Loops with call instructions cannot be interchanged "
978 return OptimizationRemarkMissed(DEBUG_TYPE, "CallInst",
981 << "Cannot interchange loops due to call instruction.";
987 // TODO: The loops could not be interchanged due to current limitations in the
989 if (currentLimitations()) {
990 LLVM_DEBUG(dbgs() << "Not legal because of current transform limitation\n");
994 // Check if the loops are tightly nested.
995 if (!tightlyNested(OuterLoop, InnerLoop)) {
996 LLVM_DEBUG(dbgs() << "Loops not tightly nested\n");
998 return OptimizationRemarkMissed(DEBUG_TYPE, "NotTightlyNested",
999 InnerLoop->getStartLoc(),
1000 InnerLoop->getHeader())
1001 << "Cannot interchange loops because they are not tightly "
1007 if (!areInnerLoopExitPHIsSupported(OuterLoop, InnerLoop,
1008 OuterInnerReductions)) {
1009 LLVM_DEBUG(dbgs() << "Found unsupported PHI nodes in inner loop exit.\n");
1011 return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedExitPHI",
1012 InnerLoop->getStartLoc(),
1013 InnerLoop->getHeader())
1014 << "Found unsupported PHI node in loop exit.";
1019 if (!areOuterLoopExitPHIsSupported(OuterLoop, InnerLoop)) {
1020 LLVM_DEBUG(dbgs() << "Found unsupported PHI nodes in outer loop exit.\n");
1022 return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedExitPHI",
1023 OuterLoop->getStartLoc(),
1024 OuterLoop->getHeader())
1025 << "Found unsupported PHI node in loop exit.";
1033 int LoopInterchangeProfitability::getInstrOrderCost() {
1034 unsigned GoodOrder, BadOrder;
1035 BadOrder = GoodOrder = 0;
1036 for (BasicBlock *BB : InnerLoop->blocks()) {
1037 for (Instruction &Ins : *BB) {
1038 if (const GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(&Ins)) {
1039 unsigned NumOp = GEP->getNumOperands();
1040 bool FoundInnerInduction = false;
1041 bool FoundOuterInduction = false;
1042 for (unsigned i = 0; i < NumOp; ++i) {
1043 const SCEV *OperandVal = SE->getSCEV(GEP->getOperand(i));
1044 const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(OperandVal);
1048 // If we find the inner induction after an outer induction e.g.
1049 // for(int i=0;i<N;i++)
1050 // for(int j=0;j<N;j++)
1051 // A[i][j] = A[i-1][j-1]+k;
1052 // then it is a good order.
1053 if (AR->getLoop() == InnerLoop) {
1054 // We found an InnerLoop induction after OuterLoop induction. It is
1056 FoundInnerInduction = true;
1057 if (FoundOuterInduction) {
1062 // If we find the outer induction after an inner induction e.g.
1063 // for(int i=0;i<N;i++)
1064 // for(int j=0;j<N;j++)
1065 // A[j][i] = A[j-1][i-1]+k;
1066 // then it is a bad order.
1067 if (AR->getLoop() == OuterLoop) {
1068 // We found an OuterLoop induction after InnerLoop induction. It is
1070 FoundOuterInduction = true;
1071 if (FoundInnerInduction) {
1080 return GoodOrder - BadOrder;
1083 static bool isProfitableForVectorization(unsigned InnerLoopId,
1084 unsigned OuterLoopId,
1085 CharMatrix &DepMatrix) {
1086 // TODO: Improve this heuristic to catch more cases.
1087 // If the inner loop is loop independent or doesn't carry any dependency it is
1088 // profitable to move this to outer position.
1089 for (auto &Row : DepMatrix) {
1090 if (Row[InnerLoopId] != 'S' && Row[InnerLoopId] != 'I')
1092 // TODO: We need to improve this heuristic.
1093 if (Row[OuterLoopId] != '=')
1096 // If outer loop has dependence and inner loop is loop independent then it is
1097 // profitable to interchange to enable parallelism.
1098 // If there are no dependences, interchanging will not improve anything.
1099 return !DepMatrix.empty();
1102 bool LoopInterchangeProfitability::isProfitable(unsigned InnerLoopId,
1103 unsigned OuterLoopId,
1104 CharMatrix &DepMatrix) {
1105 // TODO: Add better profitability checks.
1107 // 1) Construct dependency matrix and move the one with no loop carried dep
1108 // inside to enable vectorization.
1110 // This is rough cost estimation algorithm. It counts the good and bad order
1111 // of induction variables in the instruction and allows reordering if number
1112 // of bad orders is more than good.
1113 int Cost = getInstrOrderCost();
1114 LLVM_DEBUG(dbgs() << "Cost = " << Cost << "\n");
1115 if (Cost < -LoopInterchangeCostThreshold)
1118 // It is not profitable as per current cache profitability model. But check if
1119 // we can move this loop outside to improve parallelism.
1120 if (isProfitableForVectorization(InnerLoopId, OuterLoopId, DepMatrix))
1124 return OptimizationRemarkMissed(DEBUG_TYPE, "InterchangeNotProfitable",
1125 InnerLoop->getStartLoc(),
1126 InnerLoop->getHeader())
1127 << "Interchanging loops is too costly (cost="
1128 << ore::NV("Cost", Cost) << ", threshold="
1129 << ore::NV("Threshold", LoopInterchangeCostThreshold)
1130 << ") and it does not improve parallelism.";
1135 void LoopInterchangeTransform::removeChildLoop(Loop *OuterLoop,
1137 for (Loop *L : *OuterLoop)
1138 if (L == InnerLoop) {
1139 OuterLoop->removeChildLoop(L);
1142 llvm_unreachable("Couldn't find loop");
1145 /// Update LoopInfo, after interchanging. NewInner and NewOuter refer to the
1146 /// new inner and outer loop after interchanging: NewInner is the original
1147 /// outer loop and NewOuter is the original inner loop.
1149 /// Before interchanging, we have the following structure
1159 // After interchanging:
1168 void LoopInterchangeTransform::restructureLoops(
1169 Loop *NewInner, Loop *NewOuter, BasicBlock *OrigInnerPreHeader,
1170 BasicBlock *OrigOuterPreHeader) {
1171 Loop *OuterLoopParent = OuterLoop->getParentLoop();
1172 // The original inner loop preheader moves from the new inner loop to
1173 // the parent loop, if there is one.
1174 NewInner->removeBlockFromLoop(OrigInnerPreHeader);
1175 LI->changeLoopFor(OrigInnerPreHeader, OuterLoopParent);
1177 // Switch the loop levels.
1178 if (OuterLoopParent) {
1179 // Remove the loop from its parent loop.
1180 removeChildLoop(OuterLoopParent, NewInner);
1181 removeChildLoop(NewInner, NewOuter);
1182 OuterLoopParent->addChildLoop(NewOuter);
1184 removeChildLoop(NewInner, NewOuter);
1185 LI->changeTopLevelLoop(NewInner, NewOuter);
1187 while (!NewOuter->empty())
1188 NewInner->addChildLoop(NewOuter->removeChildLoop(NewOuter->begin()));
1189 NewOuter->addChildLoop(NewInner);
1191 // BBs from the original inner loop.
1192 SmallVector<BasicBlock *, 8> OrigInnerBBs(NewOuter->blocks());
1194 // Add BBs from the original outer loop to the original inner loop (excluding
1195 // BBs already in inner loop)
1196 for (BasicBlock *BB : NewInner->blocks())
1197 if (LI->getLoopFor(BB) == NewInner)
1198 NewOuter->addBlockEntry(BB);
1200 // Now remove inner loop header and latch from the new inner loop and move
1201 // other BBs (the loop body) to the new inner loop.
1202 BasicBlock *OuterHeader = NewOuter->getHeader();
1203 BasicBlock *OuterLatch = NewOuter->getLoopLatch();
1204 for (BasicBlock *BB : OrigInnerBBs) {
1205 // Nothing will change for BBs in child loops.
1206 if (LI->getLoopFor(BB) != NewOuter)
1208 // Remove the new outer loop header and latch from the new inner loop.
1209 if (BB == OuterHeader || BB == OuterLatch)
1210 NewInner->removeBlockFromLoop(BB);
1212 LI->changeLoopFor(BB, NewInner);
1215 // The preheader of the original outer loop becomes part of the new
1217 NewOuter->addBlockEntry(OrigOuterPreHeader);
1218 LI->changeLoopFor(OrigOuterPreHeader, NewOuter);
1220 // Tell SE that we move the loops around.
1221 SE->forgetLoop(NewOuter);
1222 SE->forgetLoop(NewInner);
1225 bool LoopInterchangeTransform::transform() {
1226 bool Transformed = false;
1227 Instruction *InnerIndexVar;
1229 if (InnerLoop->getSubLoops().empty()) {
1230 BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
1231 LLVM_DEBUG(dbgs() << "Splitting the inner loop latch\n");
1232 PHINode *InductionPHI = getInductionVariable(InnerLoop, SE);
1233 if (!InductionPHI) {
1234 LLVM_DEBUG(dbgs() << "Failed to find the point to split loop latch \n");
1238 if (InductionPHI->getIncomingBlock(0) == InnerLoopPreHeader)
1239 InnerIndexVar = dyn_cast<Instruction>(InductionPHI->getIncomingValue(1));
1241 InnerIndexVar = dyn_cast<Instruction>(InductionPHI->getIncomingValue(0));
1243 // Ensure that InductionPHI is the first Phi node.
1244 if (&InductionPHI->getParent()->front() != InductionPHI)
1245 InductionPHI->moveBefore(&InductionPHI->getParent()->front());
1247 // Create a new latch block for the inner loop. We split at the
1248 // current latch's terminator and then move the condition and all
1249 // operands that are not either loop-invariant or the induction PHI into the
1251 BasicBlock *NewLatch =
1252 SplitBlock(InnerLoop->getLoopLatch(),
1253 InnerLoop->getLoopLatch()->getTerminator(), DT, LI);
1255 SmallSetVector<Instruction *, 4> WorkList;
1257 auto MoveInstructions = [&i, &WorkList, this, InductionPHI, NewLatch]() {
1258 for (; i < WorkList.size(); i++) {
1259 // Duplicate instruction and move it the new latch. Update uses that
1261 Instruction *NewI = WorkList[i]->clone();
1262 NewI->insertBefore(NewLatch->getFirstNonPHI());
1263 assert(!NewI->mayHaveSideEffects() &&
1264 "Moving instructions with side-effects may change behavior of "
1266 for (auto UI = WorkList[i]->use_begin(), UE = WorkList[i]->use_end();
1269 Instruction *UserI = cast<Instruction>(U.getUser());
1270 if (!InnerLoop->contains(UserI->getParent()) ||
1271 UserI->getParent() == NewLatch || UserI == InductionPHI)
1274 // Add operands of moved instruction to the worklist, except if they are
1275 // outside the inner loop or are the induction PHI.
1276 for (Value *Op : WorkList[i]->operands()) {
1277 Instruction *OpI = dyn_cast<Instruction>(Op);
1279 this->LI->getLoopFor(OpI->getParent()) != this->InnerLoop ||
1280 OpI == InductionPHI)
1282 WorkList.insert(OpI);
1287 // FIXME: Should we interchange when we have a constant condition?
1288 Instruction *CondI = dyn_cast<Instruction>(
1289 cast<BranchInst>(InnerLoop->getLoopLatch()->getTerminator())
1292 WorkList.insert(CondI);
1294 WorkList.insert(cast<Instruction>(InnerIndexVar));
1297 // Splits the inner loops phi nodes out into a separate basic block.
1298 BasicBlock *InnerLoopHeader = InnerLoop->getHeader();
1299 SplitBlock(InnerLoopHeader, InnerLoopHeader->getFirstNonPHI(), DT, LI);
1300 LLVM_DEBUG(dbgs() << "splitting InnerLoopHeader done\n");
1303 Transformed |= adjustLoopLinks();
1305 LLVM_DEBUG(dbgs() << "adjustLoopLinks failed\n");
1312 /// \brief Move all instructions except the terminator from FromBB right before
1314 static void moveBBContents(BasicBlock *FromBB, Instruction *InsertBefore) {
1315 auto &ToList = InsertBefore->getParent()->getInstList();
1316 auto &FromList = FromBB->getInstList();
1318 ToList.splice(InsertBefore->getIterator(), FromList, FromList.begin(),
1319 FromBB->getTerminator()->getIterator());
1322 // Update BI to jump to NewBB instead of OldBB. Records updates to the
1323 // dominator tree in DTUpdates. If \p MustUpdateOnce is true, assert that
1324 // \p OldBB is exactly once in BI's successor list.
1325 static void updateSuccessor(BranchInst *BI, BasicBlock *OldBB,
1327 std::vector<DominatorTree::UpdateType> &DTUpdates,
1328 bool MustUpdateOnce = true) {
1329 assert((!MustUpdateOnce ||
1330 llvm::count_if(successors(BI),
1331 [OldBB](BasicBlock *BB) {
1333 }) == 1) && "BI must jump to OldBB exactly once.");
1334 bool Changed = false;
1335 for (Use &Op : BI->operands())
1342 DTUpdates.push_back(
1343 {DominatorTree::UpdateKind::Insert, BI->getParent(), NewBB});
1344 DTUpdates.push_back(
1345 {DominatorTree::UpdateKind::Delete, BI->getParent(), OldBB});
1347 assert(Changed && "Expected a successor to be updated");
1350 // Move Lcssa PHIs to the right place.
1351 static void moveLCSSAPhis(BasicBlock *InnerExit, BasicBlock *InnerHeader,
1352 BasicBlock *InnerLatch, BasicBlock *OuterHeader,
1353 BasicBlock *OuterLatch, BasicBlock *OuterExit,
1354 Loop *InnerLoop, LoopInfo *LI) {
1356 // Deal with LCSSA PHI nodes in the exit block of the inner loop, that are
1357 // defined either in the header or latch. Those blocks will become header and
1358 // latch of the new outer loop, and the only possible users can PHI nodes
1359 // in the exit block of the loop nest or the outer loop header (reduction
1360 // PHIs, in that case, the incoming value must be defined in the inner loop
1361 // header). We can just substitute the user with the incoming value and remove
1363 for (PHINode &P : make_early_inc_range(InnerExit->phis())) {
1364 assert(P.getNumIncomingValues() == 1 &&
1365 "Only loops with a single exit are supported!");
1367 // Incoming values are guaranteed be instructions currently.
1368 auto IncI = cast<Instruction>(P.getIncomingValueForBlock(InnerLatch));
1369 // Skip phis with incoming values from the inner loop body, excluding the
1370 // header and latch.
1371 if (IncI->getParent() != InnerLatch && IncI->getParent() != InnerHeader)
1374 assert(all_of(P.users(),
1375 [OuterHeader, OuterExit, IncI, InnerHeader](User *U) {
1376 return (cast<PHINode>(U)->getParent() == OuterHeader &&
1377 IncI->getParent() == InnerHeader) ||
1378 cast<PHINode>(U)->getParent() == OuterExit;
1380 "Can only replace phis iff the uses are in the loop nest exit or "
1381 "the incoming value is defined in the inner header (it will "
1382 "dominate all loop blocks after interchanging)");
1383 P.replaceAllUsesWith(IncI);
1384 P.eraseFromParent();
1387 SmallVector<PHINode *, 8> LcssaInnerExit;
1388 for (PHINode &P : InnerExit->phis())
1389 LcssaInnerExit.push_back(&P);
1391 SmallVector<PHINode *, 8> LcssaInnerLatch;
1392 for (PHINode &P : InnerLatch->phis())
1393 LcssaInnerLatch.push_back(&P);
1395 // Lcssa PHIs for values used outside the inner loop are in InnerExit.
1396 // If a PHI node has users outside of InnerExit, it has a use outside the
1397 // interchanged loop and we have to preserve it. We move these to
1398 // InnerLatch, which will become the new exit block for the innermost
1399 // loop after interchanging.
1400 for (PHINode *P : LcssaInnerExit)
1401 P->moveBefore(InnerLatch->getFirstNonPHI());
1403 // If the inner loop latch contains LCSSA PHIs, those come from a child loop
1404 // and we have to move them to the new inner latch.
1405 for (PHINode *P : LcssaInnerLatch)
1406 P->moveBefore(InnerExit->getFirstNonPHI());
1408 // Deal with LCSSA PHI nodes in the loop nest exit block. For PHIs that have
1409 // incoming values defined in the outer loop, we have to add a new PHI
1410 // in the inner loop latch, which became the exit block of the outer loop,
1411 // after interchanging.
1413 for (PHINode &P : OuterExit->phis()) {
1414 if (P.getNumIncomingValues() != 1)
1416 // Skip Phis with incoming values defined in the inner loop. Those should
1417 // already have been updated.
1418 auto I = dyn_cast<Instruction>(P.getIncomingValue(0));
1419 if (!I || LI->getLoopFor(I->getParent()) == InnerLoop)
1422 PHINode *NewPhi = dyn_cast<PHINode>(P.clone());
1423 NewPhi->setIncomingValue(0, P.getIncomingValue(0));
1424 NewPhi->setIncomingBlock(0, OuterLatch);
1425 NewPhi->insertBefore(InnerLatch->getFirstNonPHI());
1426 P.setIncomingValue(0, NewPhi);
1430 // Now adjust the incoming blocks for the LCSSA PHIs.
1431 // For PHIs moved from Inner's exit block, we need to replace Inner's latch
1432 // with the new latch.
1433 InnerLatch->replacePhiUsesWith(InnerLatch, OuterLatch);
1436 bool LoopInterchangeTransform::adjustLoopBranches() {
1437 LLVM_DEBUG(dbgs() << "adjustLoopBranches called\n");
1438 std::vector<DominatorTree::UpdateType> DTUpdates;
1440 BasicBlock *OuterLoopPreHeader = OuterLoop->getLoopPreheader();
1441 BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
1443 assert(OuterLoopPreHeader != OuterLoop->getHeader() &&
1444 InnerLoopPreHeader != InnerLoop->getHeader() && OuterLoopPreHeader &&
1445 InnerLoopPreHeader && "Guaranteed by loop-simplify form");
1446 // Ensure that both preheaders do not contain PHI nodes and have single
1447 // predecessors. This allows us to move them easily. We use
1448 // InsertPreHeaderForLoop to create an 'extra' preheader, if the existing
1449 // preheaders do not satisfy those conditions.
1450 if (isa<PHINode>(OuterLoopPreHeader->begin()) ||
1451 !OuterLoopPreHeader->getUniquePredecessor())
1452 OuterLoopPreHeader =
1453 InsertPreheaderForLoop(OuterLoop, DT, LI, nullptr, true);
1454 if (InnerLoopPreHeader == OuterLoop->getHeader())
1455 InnerLoopPreHeader =
1456 InsertPreheaderForLoop(InnerLoop, DT, LI, nullptr, true);
1458 // Adjust the loop preheader
1459 BasicBlock *InnerLoopHeader = InnerLoop->getHeader();
1460 BasicBlock *OuterLoopHeader = OuterLoop->getHeader();
1461 BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch();
1462 BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch();
1463 BasicBlock *OuterLoopPredecessor = OuterLoopPreHeader->getUniquePredecessor();
1464 BasicBlock *InnerLoopLatchPredecessor =
1465 InnerLoopLatch->getUniquePredecessor();
1466 BasicBlock *InnerLoopLatchSuccessor;
1467 BasicBlock *OuterLoopLatchSuccessor;
1469 BranchInst *OuterLoopLatchBI =
1470 dyn_cast<BranchInst>(OuterLoopLatch->getTerminator());
1471 BranchInst *InnerLoopLatchBI =
1472 dyn_cast<BranchInst>(InnerLoopLatch->getTerminator());
1473 BranchInst *OuterLoopHeaderBI =
1474 dyn_cast<BranchInst>(OuterLoopHeader->getTerminator());
1475 BranchInst *InnerLoopHeaderBI =
1476 dyn_cast<BranchInst>(InnerLoopHeader->getTerminator());
1478 if (!OuterLoopPredecessor || !InnerLoopLatchPredecessor ||
1479 !OuterLoopLatchBI || !InnerLoopLatchBI || !OuterLoopHeaderBI ||
1483 BranchInst *InnerLoopLatchPredecessorBI =
1484 dyn_cast<BranchInst>(InnerLoopLatchPredecessor->getTerminator());
1485 BranchInst *OuterLoopPredecessorBI =
1486 dyn_cast<BranchInst>(OuterLoopPredecessor->getTerminator());
1488 if (!OuterLoopPredecessorBI || !InnerLoopLatchPredecessorBI)
1490 BasicBlock *InnerLoopHeaderSuccessor = InnerLoopHeader->getUniqueSuccessor();
1491 if (!InnerLoopHeaderSuccessor)
1494 // Adjust Loop Preheader and headers.
1495 // The branches in the outer loop predecessor and the outer loop header can
1496 // be unconditional branches or conditional branches with duplicates. Consider
1497 // this when updating the successors.
1498 updateSuccessor(OuterLoopPredecessorBI, OuterLoopPreHeader,
1499 InnerLoopPreHeader, DTUpdates, /*MustUpdateOnce=*/false);
1500 // The outer loop header might or might not branch to the outer latch.
1501 // We are guaranteed to branch to the inner loop preheader.
1502 if (std::find(succ_begin(OuterLoopHeaderBI), succ_end(OuterLoopHeaderBI),
1503 OuterLoopLatch) != succ_end(OuterLoopHeaderBI))
1504 updateSuccessor(OuterLoopHeaderBI, OuterLoopLatch, LoopExit, DTUpdates,
1505 /*MustUpdateOnce=*/false);
1506 updateSuccessor(OuterLoopHeaderBI, InnerLoopPreHeader,
1507 InnerLoopHeaderSuccessor, DTUpdates,
1508 /*MustUpdateOnce=*/false);
1510 // Adjust reduction PHI's now that the incoming block has changed.
1511 InnerLoopHeaderSuccessor->replacePhiUsesWith(InnerLoopHeader,
1514 updateSuccessor(InnerLoopHeaderBI, InnerLoopHeaderSuccessor,
1515 OuterLoopPreHeader, DTUpdates);
1517 // -------------Adjust loop latches-----------
1518 if (InnerLoopLatchBI->getSuccessor(0) == InnerLoopHeader)
1519 InnerLoopLatchSuccessor = InnerLoopLatchBI->getSuccessor(1);
1521 InnerLoopLatchSuccessor = InnerLoopLatchBI->getSuccessor(0);
1523 updateSuccessor(InnerLoopLatchPredecessorBI, InnerLoopLatch,
1524 InnerLoopLatchSuccessor, DTUpdates);
1527 if (OuterLoopLatchBI->getSuccessor(0) == OuterLoopHeader)
1528 OuterLoopLatchSuccessor = OuterLoopLatchBI->getSuccessor(1);
1530 OuterLoopLatchSuccessor = OuterLoopLatchBI->getSuccessor(0);
1532 updateSuccessor(InnerLoopLatchBI, InnerLoopLatchSuccessor,
1533 OuterLoopLatchSuccessor, DTUpdates);
1534 updateSuccessor(OuterLoopLatchBI, OuterLoopLatchSuccessor, InnerLoopLatch,
1537 DT->applyUpdates(DTUpdates);
1538 restructureLoops(OuterLoop, InnerLoop, InnerLoopPreHeader,
1539 OuterLoopPreHeader);
1541 moveLCSSAPhis(InnerLoopLatchSuccessor, InnerLoopHeader, InnerLoopLatch,
1542 OuterLoopHeader, OuterLoopLatch, InnerLoop->getExitBlock(),
1544 // For PHIs in the exit block of the outer loop, outer's latch has been
1545 // replaced by Inners'.
1546 OuterLoopLatchSuccessor->replacePhiUsesWith(OuterLoopLatch, InnerLoopLatch);
1548 // Now update the reduction PHIs in the inner and outer loop headers.
1549 SmallVector<PHINode *, 4> InnerLoopPHIs, OuterLoopPHIs;
1550 for (PHINode &PHI : drop_begin(InnerLoopHeader->phis(), 1))
1551 InnerLoopPHIs.push_back(cast<PHINode>(&PHI));
1552 for (PHINode &PHI : drop_begin(OuterLoopHeader->phis(), 1))
1553 OuterLoopPHIs.push_back(cast<PHINode>(&PHI));
1555 auto &OuterInnerReductions = LIL.getOuterInnerReductions();
1556 (void)OuterInnerReductions;
1558 // Now move the remaining reduction PHIs from outer to inner loop header and
1559 // vice versa. The PHI nodes must be part of a reduction across the inner and
1560 // outer loop and all the remains to do is and updating the incoming blocks.
1561 for (PHINode *PHI : OuterLoopPHIs) {
1562 PHI->moveBefore(InnerLoopHeader->getFirstNonPHI());
1563 assert(OuterInnerReductions.find(PHI) != OuterInnerReductions.end() &&
1564 "Expected a reduction PHI node");
1566 for (PHINode *PHI : InnerLoopPHIs) {
1567 PHI->moveBefore(OuterLoopHeader->getFirstNonPHI());
1568 assert(OuterInnerReductions.find(PHI) != OuterInnerReductions.end() &&
1569 "Expected a reduction PHI node");
1572 // Update the incoming blocks for moved PHI nodes.
1573 OuterLoopHeader->replacePhiUsesWith(InnerLoopPreHeader, OuterLoopPreHeader);
1574 OuterLoopHeader->replacePhiUsesWith(InnerLoopLatch, OuterLoopLatch);
1575 InnerLoopHeader->replacePhiUsesWith(OuterLoopPreHeader, InnerLoopPreHeader);
1576 InnerLoopHeader->replacePhiUsesWith(OuterLoopLatch, InnerLoopLatch);
1581 void LoopInterchangeTransform::adjustLoopPreheaders() {
1582 // We have interchanged the preheaders so we need to interchange the data in
1583 // the preheader as well.
1584 // This is because the content of inner preheader was previously executed
1585 // inside the outer loop.
1586 BasicBlock *OuterLoopPreHeader = OuterLoop->getLoopPreheader();
1587 BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
1588 BasicBlock *OuterLoopHeader = OuterLoop->getHeader();
1589 BranchInst *InnerTermBI =
1590 cast<BranchInst>(InnerLoopPreHeader->getTerminator());
1592 // These instructions should now be executed inside the loop.
1593 // Move instruction into a new block after outer header.
1594 moveBBContents(InnerLoopPreHeader, OuterLoopHeader->getTerminator());
1595 // These instructions were not executed previously in the loop so move them to
1596 // the older inner loop preheader.
1597 moveBBContents(OuterLoopPreHeader, InnerTermBI);
1600 bool LoopInterchangeTransform::adjustLoopLinks() {
1601 // Adjust all branches in the inner and outer loop.
1602 bool Changed = adjustLoopBranches();
1604 adjustLoopPreheaders();
1608 char LoopInterchange::ID = 0;
1610 INITIALIZE_PASS_BEGIN(LoopInterchange, "loop-interchange",
1611 "Interchanges loops for cache reuse", false, false)
1612 INITIALIZE_PASS_DEPENDENCY(LoopPass)
1613 INITIALIZE_PASS_DEPENDENCY(DependenceAnalysisWrapperPass)
1614 INITIALIZE_PASS_DEPENDENCY(OptimizationRemarkEmitterWrapperPass)
1616 INITIALIZE_PASS_END(LoopInterchange, "loop-interchange",
1617 "Interchanges loops for cache reuse", false, false)
1619 Pass *llvm::createLoopInterchangePass() { return new LoopInterchange(); }