[yaml2obj/obj2yaml] - Add support for .stack_sizes sections.
[llvm-complete.git] / lib / Transforms / Scalar / LoopInterchange.cpp
blob1af4b21b432e2a89688733691b8c2336f53df305
1 //===- LoopInterchange.cpp - Loop interchange pass-------------------------===//
2 //
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
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This Pass handles loop interchange transform.
10 // This pass interchanges loops to provide a more cache-friendly memory access
11 // patterns.
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/Pass.h"
37 #include "llvm/Support/Casting.h"
38 #include "llvm/Support/CommandLine.h"
39 #include "llvm/Support/Debug.h"
40 #include "llvm/Support/ErrorHandling.h"
41 #include "llvm/Support/raw_ostream.h"
42 #include "llvm/Transforms/Scalar.h"
43 #include "llvm/Transforms/Utils.h"
44 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
45 #include "llvm/Transforms/Utils/LoopUtils.h"
46 #include <cassert>
47 #include <utility>
48 #include <vector>
50 using namespace llvm;
52 #define DEBUG_TYPE "loop-interchange"
54 STATISTIC(LoopsInterchanged, "Number of loops interchanged");
56 static cl::opt<int> LoopInterchangeCostThreshold(
57 "loop-interchange-threshold", cl::init(0), cl::Hidden,
58 cl::desc("Interchange if you gain more than this number"));
60 namespace {
62 using LoopVector = SmallVector<Loop *, 8>;
64 // TODO: Check if we can use a sparse matrix here.
65 using CharMatrix = std::vector<std::vector<char>>;
67 } // end anonymous namespace
69 // Maximum number of dependencies that can be handled in the dependency matrix.
70 static const unsigned MaxMemInstrCount = 100;
72 // Maximum loop depth supported.
73 static const unsigned MaxLoopNestDepth = 10;
75 #ifdef DUMP_DEP_MATRICIES
76 static void printDepMatrix(CharMatrix &DepMatrix) {
77 for (auto &Row : DepMatrix) {
78 for (auto D : Row)
79 LLVM_DEBUG(dbgs() << D << " ");
80 LLVM_DEBUG(dbgs() << "\n");
83 #endif
85 static bool populateDependencyMatrix(CharMatrix &DepMatrix, unsigned Level,
86 Loop *L, DependenceInfo *DI) {
87 using ValueVector = SmallVector<Value *, 16>;
89 ValueVector MemInstr;
91 // For each block.
92 for (BasicBlock *BB : L->blocks()) {
93 // Scan the BB and collect legal loads and stores.
94 for (Instruction &I : *BB) {
95 if (!isa<Instruction>(I))
96 return false;
97 if (auto *Ld = dyn_cast<LoadInst>(&I)) {
98 if (!Ld->isSimple())
99 return false;
100 MemInstr.push_back(&I);
101 } else if (auto *St = dyn_cast<StoreInst>(&I)) {
102 if (!St->isSimple())
103 return false;
104 MemInstr.push_back(&I);
109 LLVM_DEBUG(dbgs() << "Found " << MemInstr.size()
110 << " Loads and Stores to analyze\n");
112 ValueVector::iterator I, IE, J, JE;
114 for (I = MemInstr.begin(), IE = MemInstr.end(); I != IE; ++I) {
115 for (J = I, JE = MemInstr.end(); J != JE; ++J) {
116 std::vector<char> Dep;
117 Instruction *Src = cast<Instruction>(*I);
118 Instruction *Dst = cast<Instruction>(*J);
119 if (Src == Dst)
120 continue;
121 // Ignore Input dependencies.
122 if (isa<LoadInst>(Src) && isa<LoadInst>(Dst))
123 continue;
124 // Track Output, Flow, and Anti dependencies.
125 if (auto D = DI->depends(Src, Dst, true)) {
126 assert(D->isOrdered() && "Expected an output, flow or anti dep.");
127 LLVM_DEBUG(StringRef DepType =
128 D->isFlow() ? "flow" : D->isAnti() ? "anti" : "output";
129 dbgs() << "Found " << DepType
130 << " dependency between Src and Dst\n"
131 << " Src:" << *Src << "\n Dst:" << *Dst << '\n');
132 unsigned Levels = D->getLevels();
133 char Direction;
134 for (unsigned II = 1; II <= Levels; ++II) {
135 const SCEV *Distance = D->getDistance(II);
136 const SCEVConstant *SCEVConst =
137 dyn_cast_or_null<SCEVConstant>(Distance);
138 if (SCEVConst) {
139 const ConstantInt *CI = SCEVConst->getValue();
140 if (CI->isNegative())
141 Direction = '<';
142 else if (CI->isZero())
143 Direction = '=';
144 else
145 Direction = '>';
146 Dep.push_back(Direction);
147 } else if (D->isScalar(II)) {
148 Direction = 'S';
149 Dep.push_back(Direction);
150 } else {
151 unsigned Dir = D->getDirection(II);
152 if (Dir == Dependence::DVEntry::LT ||
153 Dir == Dependence::DVEntry::LE)
154 Direction = '<';
155 else if (Dir == Dependence::DVEntry::GT ||
156 Dir == Dependence::DVEntry::GE)
157 Direction = '>';
158 else if (Dir == Dependence::DVEntry::EQ)
159 Direction = '=';
160 else
161 Direction = '*';
162 Dep.push_back(Direction);
165 while (Dep.size() != Level) {
166 Dep.push_back('I');
169 DepMatrix.push_back(Dep);
170 if (DepMatrix.size() > MaxMemInstrCount) {
171 LLVM_DEBUG(dbgs() << "Cannot handle more than " << MaxMemInstrCount
172 << " dependencies inside loop\n");
173 return false;
179 return true;
182 // A loop is moved from index 'from' to an index 'to'. Update the Dependence
183 // matrix by exchanging the two columns.
184 static void interChangeDependencies(CharMatrix &DepMatrix, unsigned FromIndx,
185 unsigned ToIndx) {
186 unsigned numRows = DepMatrix.size();
187 for (unsigned i = 0; i < numRows; ++i) {
188 char TmpVal = DepMatrix[i][ToIndx];
189 DepMatrix[i][ToIndx] = DepMatrix[i][FromIndx];
190 DepMatrix[i][FromIndx] = TmpVal;
194 // Checks if outermost non '=','S'or'I' dependence in the dependence matrix is
195 // '>'
196 static bool isOuterMostDepPositive(CharMatrix &DepMatrix, unsigned Row,
197 unsigned Column) {
198 for (unsigned i = 0; i <= Column; ++i) {
199 if (DepMatrix[Row][i] == '<')
200 return false;
201 if (DepMatrix[Row][i] == '>')
202 return true;
204 // All dependencies were '=','S' or 'I'
205 return false;
208 // Checks if no dependence exist in the dependency matrix in Row before Column.
209 static bool containsNoDependence(CharMatrix &DepMatrix, unsigned Row,
210 unsigned Column) {
211 for (unsigned i = 0; i < Column; ++i) {
212 if (DepMatrix[Row][i] != '=' && DepMatrix[Row][i] != 'S' &&
213 DepMatrix[Row][i] != 'I')
214 return false;
216 return true;
219 static bool validDepInterchange(CharMatrix &DepMatrix, unsigned Row,
220 unsigned OuterLoopId, char InnerDep,
221 char OuterDep) {
222 if (isOuterMostDepPositive(DepMatrix, Row, OuterLoopId))
223 return false;
225 if (InnerDep == OuterDep)
226 return true;
228 // It is legal to interchange if and only if after interchange no row has a
229 // '>' direction as the leftmost non-'='.
231 if (InnerDep == '=' || InnerDep == 'S' || InnerDep == 'I')
232 return true;
234 if (InnerDep == '<')
235 return true;
237 if (InnerDep == '>') {
238 // If OuterLoopId represents outermost loop then interchanging will make the
239 // 1st dependency as '>'
240 if (OuterLoopId == 0)
241 return false;
243 // If all dependencies before OuterloopId are '=','S'or 'I'. Then
244 // interchanging will result in this row having an outermost non '='
245 // dependency of '>'
246 if (!containsNoDependence(DepMatrix, Row, OuterLoopId))
247 return true;
250 return false;
253 // Checks if it is legal to interchange 2 loops.
254 // [Theorem] A permutation of the loops in a perfect nest is legal if and only
255 // if the direction matrix, after the same permutation is applied to its
256 // columns, has no ">" direction as the leftmost non-"=" direction in any row.
257 static bool isLegalToInterChangeLoops(CharMatrix &DepMatrix,
258 unsigned InnerLoopId,
259 unsigned OuterLoopId) {
260 unsigned NumRows = DepMatrix.size();
261 // For each row check if it is valid to interchange.
262 for (unsigned Row = 0; Row < NumRows; ++Row) {
263 char InnerDep = DepMatrix[Row][InnerLoopId];
264 char OuterDep = DepMatrix[Row][OuterLoopId];
265 if (InnerDep == '*' || OuterDep == '*')
266 return false;
267 if (!validDepInterchange(DepMatrix, Row, OuterLoopId, InnerDep, OuterDep))
268 return false;
270 return true;
273 static LoopVector populateWorklist(Loop &L) {
274 LLVM_DEBUG(dbgs() << "Calling populateWorklist on Func: "
275 << L.getHeader()->getParent()->getName() << " Loop: %"
276 << L.getHeader()->getName() << '\n');
277 LoopVector LoopList;
278 Loop *CurrentLoop = &L;
279 const std::vector<Loop *> *Vec = &CurrentLoop->getSubLoops();
280 while (!Vec->empty()) {
281 // The current loop has multiple subloops in it hence it is not tightly
282 // nested.
283 // Discard all loops above it added into Worklist.
284 if (Vec->size() != 1)
285 return {};
287 LoopList.push_back(CurrentLoop);
288 CurrentLoop = Vec->front();
289 Vec = &CurrentLoop->getSubLoops();
291 LoopList.push_back(CurrentLoop);
292 return LoopList;
295 static PHINode *getInductionVariable(Loop *L, ScalarEvolution *SE) {
296 PHINode *InnerIndexVar = L->getCanonicalInductionVariable();
297 if (InnerIndexVar)
298 return InnerIndexVar;
299 if (L->getLoopLatch() == nullptr || L->getLoopPredecessor() == nullptr)
300 return nullptr;
301 for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) {
302 PHINode *PhiVar = cast<PHINode>(I);
303 Type *PhiTy = PhiVar->getType();
304 if (!PhiTy->isIntegerTy() && !PhiTy->isFloatingPointTy() &&
305 !PhiTy->isPointerTy())
306 return nullptr;
307 const SCEVAddRecExpr *AddRec =
308 dyn_cast<SCEVAddRecExpr>(SE->getSCEV(PhiVar));
309 if (!AddRec || !AddRec->isAffine())
310 continue;
311 const SCEV *Step = AddRec->getStepRecurrence(*SE);
312 if (!isa<SCEVConstant>(Step))
313 continue;
314 // Found the induction variable.
315 // FIXME: Handle loops with more than one induction variable. Note that,
316 // currently, legality makes sure we have only one induction variable.
317 return PhiVar;
319 return nullptr;
322 namespace {
324 /// LoopInterchangeLegality checks if it is legal to interchange the loop.
325 class LoopInterchangeLegality {
326 public:
327 LoopInterchangeLegality(Loop *Outer, Loop *Inner, ScalarEvolution *SE,
328 OptimizationRemarkEmitter *ORE)
329 : OuterLoop(Outer), InnerLoop(Inner), SE(SE), ORE(ORE) {}
331 /// Check if the loops can be interchanged.
332 bool canInterchangeLoops(unsigned InnerLoopId, unsigned OuterLoopId,
333 CharMatrix &DepMatrix);
335 /// Check if the loop structure is understood. We do not handle triangular
336 /// loops for now.
337 bool isLoopStructureUnderstood(PHINode *InnerInductionVar);
339 bool currentLimitations();
341 const SmallPtrSetImpl<PHINode *> &getOuterInnerReductions() const {
342 return OuterInnerReductions;
345 private:
346 bool tightlyNested(Loop *Outer, Loop *Inner);
347 bool containsUnsafeInstructions(BasicBlock *BB);
349 /// Discover induction and reduction PHIs in the header of \p L. Induction
350 /// PHIs are added to \p Inductions, reductions are added to
351 /// OuterInnerReductions. When the outer loop is passed, the inner loop needs
352 /// to be passed as \p InnerLoop.
353 bool findInductionAndReductions(Loop *L,
354 SmallVector<PHINode *, 8> &Inductions,
355 Loop *InnerLoop);
357 Loop *OuterLoop;
358 Loop *InnerLoop;
360 ScalarEvolution *SE;
362 /// Interface to emit optimization remarks.
363 OptimizationRemarkEmitter *ORE;
365 /// Set of reduction PHIs taking part of a reduction across the inner and
366 /// outer loop.
367 SmallPtrSet<PHINode *, 4> OuterInnerReductions;
370 /// LoopInterchangeProfitability checks if it is profitable to interchange the
371 /// loop.
372 class LoopInterchangeProfitability {
373 public:
374 LoopInterchangeProfitability(Loop *Outer, Loop *Inner, ScalarEvolution *SE,
375 OptimizationRemarkEmitter *ORE)
376 : OuterLoop(Outer), InnerLoop(Inner), SE(SE), ORE(ORE) {}
378 /// Check if the loop interchange is profitable.
379 bool isProfitable(unsigned InnerLoopId, unsigned OuterLoopId,
380 CharMatrix &DepMatrix);
382 private:
383 int getInstrOrderCost();
385 Loop *OuterLoop;
386 Loop *InnerLoop;
388 /// Scev analysis.
389 ScalarEvolution *SE;
391 /// Interface to emit optimization remarks.
392 OptimizationRemarkEmitter *ORE;
395 /// LoopInterchangeTransform interchanges the loop.
396 class LoopInterchangeTransform {
397 public:
398 LoopInterchangeTransform(Loop *Outer, Loop *Inner, ScalarEvolution *SE,
399 LoopInfo *LI, DominatorTree *DT,
400 BasicBlock *LoopNestExit,
401 const LoopInterchangeLegality &LIL)
402 : OuterLoop(Outer), InnerLoop(Inner), SE(SE), LI(LI), DT(DT),
403 LoopExit(LoopNestExit), LIL(LIL) {}
405 /// Interchange OuterLoop and InnerLoop.
406 bool transform();
407 void restructureLoops(Loop *NewInner, Loop *NewOuter,
408 BasicBlock *OrigInnerPreHeader,
409 BasicBlock *OrigOuterPreHeader);
410 void removeChildLoop(Loop *OuterLoop, Loop *InnerLoop);
412 private:
413 bool adjustLoopLinks();
414 void adjustLoopPreheaders();
415 bool adjustLoopBranches();
417 Loop *OuterLoop;
418 Loop *InnerLoop;
420 /// Scev analysis.
421 ScalarEvolution *SE;
423 LoopInfo *LI;
424 DominatorTree *DT;
425 BasicBlock *LoopExit;
427 const LoopInterchangeLegality &LIL;
430 // Main LoopInterchange Pass.
431 struct LoopInterchange : public LoopPass {
432 static char ID;
433 ScalarEvolution *SE = nullptr;
434 LoopInfo *LI = nullptr;
435 DependenceInfo *DI = nullptr;
436 DominatorTree *DT = nullptr;
438 /// Interface to emit optimization remarks.
439 OptimizationRemarkEmitter *ORE;
441 LoopInterchange() : LoopPass(ID) {
442 initializeLoopInterchangePass(*PassRegistry::getPassRegistry());
445 void getAnalysisUsage(AnalysisUsage &AU) const override {
446 AU.addRequired<DependenceAnalysisWrapperPass>();
447 AU.addRequired<OptimizationRemarkEmitterWrapperPass>();
449 getLoopAnalysisUsage(AU);
452 bool runOnLoop(Loop *L, LPPassManager &LPM) override {
453 if (skipLoop(L) || L->getParentLoop())
454 return false;
456 SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
457 LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
458 DI = &getAnalysis<DependenceAnalysisWrapperPass>().getDI();
459 DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
460 ORE = &getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE();
462 return processLoopList(populateWorklist(*L));
465 bool isComputableLoopNest(LoopVector LoopList) {
466 for (Loop *L : LoopList) {
467 const SCEV *ExitCountOuter = SE->getBackedgeTakenCount(L);
468 if (ExitCountOuter == SE->getCouldNotCompute()) {
469 LLVM_DEBUG(dbgs() << "Couldn't compute backedge count\n");
470 return false;
472 if (L->getNumBackEdges() != 1) {
473 LLVM_DEBUG(dbgs() << "NumBackEdges is not equal to 1\n");
474 return false;
476 if (!L->getExitingBlock()) {
477 LLVM_DEBUG(dbgs() << "Loop doesn't have unique exit block\n");
478 return false;
481 return true;
484 unsigned selectLoopForInterchange(const LoopVector &LoopList) {
485 // TODO: Add a better heuristic to select the loop to be interchanged based
486 // on the dependence matrix. Currently we select the innermost loop.
487 return LoopList.size() - 1;
490 bool processLoopList(LoopVector LoopList) {
491 bool Changed = false;
492 unsigned LoopNestDepth = LoopList.size();
493 if (LoopNestDepth < 2) {
494 LLVM_DEBUG(dbgs() << "Loop doesn't contain minimum nesting level.\n");
495 return false;
497 if (LoopNestDepth > MaxLoopNestDepth) {
498 LLVM_DEBUG(dbgs() << "Cannot handle loops of depth greater than "
499 << MaxLoopNestDepth << "\n");
500 return false;
502 if (!isComputableLoopNest(LoopList)) {
503 LLVM_DEBUG(dbgs() << "Not valid loop candidate for interchange\n");
504 return false;
507 LLVM_DEBUG(dbgs() << "Processing LoopList of size = " << LoopNestDepth
508 << "\n");
510 CharMatrix DependencyMatrix;
511 Loop *OuterMostLoop = *(LoopList.begin());
512 if (!populateDependencyMatrix(DependencyMatrix, LoopNestDepth,
513 OuterMostLoop, DI)) {
514 LLVM_DEBUG(dbgs() << "Populating dependency matrix failed\n");
515 return false;
517 #ifdef DUMP_DEP_MATRICIES
518 LLVM_DEBUG(dbgs() << "Dependence before interchange\n");
519 printDepMatrix(DependencyMatrix);
520 #endif
522 // Get the Outermost loop exit.
523 BasicBlock *LoopNestExit = OuterMostLoop->getExitBlock();
524 if (!LoopNestExit) {
525 LLVM_DEBUG(dbgs() << "OuterMostLoop needs an unique exit block");
526 return false;
529 unsigned SelecLoopId = selectLoopForInterchange(LoopList);
530 // Move the selected loop outwards to the best possible position.
531 for (unsigned i = SelecLoopId; i > 0; i--) {
532 bool Interchanged =
533 processLoop(LoopList, i, i - 1, LoopNestExit, DependencyMatrix);
534 if (!Interchanged)
535 return Changed;
536 // Loops interchanged reflect the same in LoopList
537 std::swap(LoopList[i - 1], LoopList[i]);
539 // Update the DependencyMatrix
540 interChangeDependencies(DependencyMatrix, i, i - 1);
541 #ifdef DUMP_DEP_MATRICIES
542 LLVM_DEBUG(dbgs() << "Dependence after interchange\n");
543 printDepMatrix(DependencyMatrix);
544 #endif
545 Changed |= Interchanged;
547 return Changed;
550 bool processLoop(LoopVector LoopList, unsigned InnerLoopId,
551 unsigned OuterLoopId, BasicBlock *LoopNestExit,
552 std::vector<std::vector<char>> &DependencyMatrix) {
553 LLVM_DEBUG(dbgs() << "Processing Inner Loop Id = " << InnerLoopId
554 << " and OuterLoopId = " << OuterLoopId << "\n");
555 Loop *InnerLoop = LoopList[InnerLoopId];
556 Loop *OuterLoop = LoopList[OuterLoopId];
558 LoopInterchangeLegality LIL(OuterLoop, InnerLoop, SE, ORE);
559 if (!LIL.canInterchangeLoops(InnerLoopId, OuterLoopId, DependencyMatrix)) {
560 LLVM_DEBUG(dbgs() << "Not interchanging loops. Cannot prove legality.\n");
561 return false;
563 LLVM_DEBUG(dbgs() << "Loops are legal to interchange\n");
564 LoopInterchangeProfitability LIP(OuterLoop, InnerLoop, SE, ORE);
565 if (!LIP.isProfitable(InnerLoopId, OuterLoopId, DependencyMatrix)) {
566 LLVM_DEBUG(dbgs() << "Interchanging loops not profitable.\n");
567 return false;
570 ORE->emit([&]() {
571 return OptimizationRemark(DEBUG_TYPE, "Interchanged",
572 InnerLoop->getStartLoc(),
573 InnerLoop->getHeader())
574 << "Loop interchanged with enclosing loop.";
577 LoopInterchangeTransform LIT(OuterLoop, InnerLoop, SE, LI, DT, LoopNestExit,
578 LIL);
579 LIT.transform();
580 LLVM_DEBUG(dbgs() << "Loops interchanged.\n");
581 LoopsInterchanged++;
582 return true;
586 } // end anonymous namespace
588 bool LoopInterchangeLegality::containsUnsafeInstructions(BasicBlock *BB) {
589 return any_of(*BB, [](const Instruction &I) {
590 return I.mayHaveSideEffects() || I.mayReadFromMemory();
594 bool LoopInterchangeLegality::tightlyNested(Loop *OuterLoop, Loop *InnerLoop) {
595 BasicBlock *OuterLoopHeader = OuterLoop->getHeader();
596 BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
597 BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch();
599 LLVM_DEBUG(dbgs() << "Checking if loops are tightly nested\n");
601 // A perfectly nested loop will not have any branch in between the outer and
602 // inner block i.e. outer header will branch to either inner preheader and
603 // outerloop latch.
604 BranchInst *OuterLoopHeaderBI =
605 dyn_cast<BranchInst>(OuterLoopHeader->getTerminator());
606 if (!OuterLoopHeaderBI)
607 return false;
609 for (BasicBlock *Succ : successors(OuterLoopHeaderBI))
610 if (Succ != InnerLoopPreHeader && Succ != InnerLoop->getHeader() &&
611 Succ != OuterLoopLatch)
612 return false;
614 LLVM_DEBUG(dbgs() << "Checking instructions in Loop header and Loop latch\n");
615 // We do not have any basic block in between now make sure the outer header
616 // and outer loop latch doesn't contain any unsafe instructions.
617 if (containsUnsafeInstructions(OuterLoopHeader) ||
618 containsUnsafeInstructions(OuterLoopLatch))
619 return false;
621 LLVM_DEBUG(dbgs() << "Loops are perfectly nested\n");
622 // We have a perfect loop nest.
623 return true;
626 bool LoopInterchangeLegality::isLoopStructureUnderstood(
627 PHINode *InnerInduction) {
628 unsigned Num = InnerInduction->getNumOperands();
629 BasicBlock *InnerLoopPreheader = InnerLoop->getLoopPreheader();
630 for (unsigned i = 0; i < Num; ++i) {
631 Value *Val = InnerInduction->getOperand(i);
632 if (isa<Constant>(Val))
633 continue;
634 Instruction *I = dyn_cast<Instruction>(Val);
635 if (!I)
636 return false;
637 // TODO: Handle triangular loops.
638 // e.g. for(int i=0;i<N;i++)
639 // for(int j=i;j<N;j++)
640 unsigned IncomBlockIndx = PHINode::getIncomingValueNumForOperand(i);
641 if (InnerInduction->getIncomingBlock(IncomBlockIndx) ==
642 InnerLoopPreheader &&
643 !OuterLoop->isLoopInvariant(I)) {
644 return false;
647 return true;
650 // If SV is a LCSSA PHI node with a single incoming value, return the incoming
651 // value.
652 static Value *followLCSSA(Value *SV) {
653 PHINode *PHI = dyn_cast<PHINode>(SV);
654 if (!PHI)
655 return SV;
657 if (PHI->getNumIncomingValues() != 1)
658 return SV;
659 return followLCSSA(PHI->getIncomingValue(0));
662 // Check V's users to see if it is involved in a reduction in L.
663 static PHINode *findInnerReductionPhi(Loop *L, Value *V) {
664 for (Value *User : V->users()) {
665 if (PHINode *PHI = dyn_cast<PHINode>(User)) {
666 if (PHI->getNumIncomingValues() == 1)
667 continue;
668 RecurrenceDescriptor RD;
669 if (RecurrenceDescriptor::isReductionPHI(PHI, L, RD))
670 return PHI;
671 return nullptr;
675 return nullptr;
678 bool LoopInterchangeLegality::findInductionAndReductions(
679 Loop *L, SmallVector<PHINode *, 8> &Inductions, Loop *InnerLoop) {
680 if (!L->getLoopLatch() || !L->getLoopPredecessor())
681 return false;
682 for (PHINode &PHI : L->getHeader()->phis()) {
683 RecurrenceDescriptor RD;
684 InductionDescriptor ID;
685 if (InductionDescriptor::isInductionPHI(&PHI, L, SE, ID))
686 Inductions.push_back(&PHI);
687 else {
688 // PHIs in inner loops need to be part of a reduction in the outer loop,
689 // discovered when checking the PHIs of the outer loop earlier.
690 if (!InnerLoop) {
691 if (OuterInnerReductions.find(&PHI) == OuterInnerReductions.end()) {
692 LLVM_DEBUG(dbgs() << "Inner loop PHI is not part of reductions "
693 "across the outer loop.\n");
694 return false;
696 } else {
697 assert(PHI.getNumIncomingValues() == 2 &&
698 "Phis in loop header should have exactly 2 incoming values");
699 // Check if we have a PHI node in the outer loop that has a reduction
700 // result from the inner loop as an incoming value.
701 Value *V = followLCSSA(PHI.getIncomingValueForBlock(L->getLoopLatch()));
702 PHINode *InnerRedPhi = findInnerReductionPhi(InnerLoop, V);
703 if (!InnerRedPhi ||
704 !llvm::any_of(InnerRedPhi->incoming_values(),
705 [&PHI](Value *V) { return V == &PHI; })) {
706 LLVM_DEBUG(
707 dbgs()
708 << "Failed to recognize PHI as an induction or reduction.\n");
709 return false;
711 OuterInnerReductions.insert(&PHI);
712 OuterInnerReductions.insert(InnerRedPhi);
716 return true;
719 static bool containsSafePHI(BasicBlock *Block, bool isOuterLoopExitBlock) {
720 for (PHINode &PHI : Block->phis()) {
721 // Reduction lcssa phi will have only 1 incoming block that from loop latch.
722 if (PHI.getNumIncomingValues() > 1)
723 return false;
724 Instruction *Ins = dyn_cast<Instruction>(PHI.getIncomingValue(0));
725 if (!Ins)
726 return false;
727 // Incoming value for lcssa phi's in outer loop exit can only be inner loop
728 // exits lcssa phi else it would not be tightly nested.
729 if (!isa<PHINode>(Ins) && isOuterLoopExitBlock)
730 return false;
732 return true;
735 // This function indicates the current limitations in the transform as a result
736 // of which we do not proceed.
737 bool LoopInterchangeLegality::currentLimitations() {
738 BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
739 BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch();
741 // transform currently expects the loop latches to also be the exiting
742 // blocks.
743 if (InnerLoop->getExitingBlock() != InnerLoopLatch ||
744 OuterLoop->getExitingBlock() != OuterLoop->getLoopLatch() ||
745 !isa<BranchInst>(InnerLoopLatch->getTerminator()) ||
746 !isa<BranchInst>(OuterLoop->getLoopLatch()->getTerminator())) {
747 LLVM_DEBUG(
748 dbgs() << "Loops where the latch is not the exiting block are not"
749 << " supported currently.\n");
750 ORE->emit([&]() {
751 return OptimizationRemarkMissed(DEBUG_TYPE, "ExitingNotLatch",
752 OuterLoop->getStartLoc(),
753 OuterLoop->getHeader())
754 << "Loops where the latch is not the exiting block cannot be"
755 " interchange currently.";
757 return true;
760 PHINode *InnerInductionVar;
761 SmallVector<PHINode *, 8> Inductions;
762 if (!findInductionAndReductions(OuterLoop, Inductions, InnerLoop)) {
763 LLVM_DEBUG(
764 dbgs() << "Only outer loops with induction or reduction PHI nodes "
765 << "are supported currently.\n");
766 ORE->emit([&]() {
767 return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedPHIOuter",
768 OuterLoop->getStartLoc(),
769 OuterLoop->getHeader())
770 << "Only outer loops with induction or reduction PHI nodes can be"
771 " interchanged currently.";
773 return true;
776 // TODO: Currently we handle only loops with 1 induction variable.
777 if (Inductions.size() != 1) {
778 LLVM_DEBUG(dbgs() << "Loops with more than 1 induction variables are not "
779 << "supported currently.\n");
780 ORE->emit([&]() {
781 return OptimizationRemarkMissed(DEBUG_TYPE, "MultiIndutionOuter",
782 OuterLoop->getStartLoc(),
783 OuterLoop->getHeader())
784 << "Only outer loops with 1 induction variable can be "
785 "interchanged currently.";
787 return true;
790 Inductions.clear();
791 if (!findInductionAndReductions(InnerLoop, Inductions, nullptr)) {
792 LLVM_DEBUG(
793 dbgs() << "Only inner loops with induction or reduction PHI nodes "
794 << "are supported currently.\n");
795 ORE->emit([&]() {
796 return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedPHIInner",
797 InnerLoop->getStartLoc(),
798 InnerLoop->getHeader())
799 << "Only inner loops with induction or reduction PHI nodes can be"
800 " interchange currently.";
802 return true;
805 // TODO: Currently we handle only loops with 1 induction variable.
806 if (Inductions.size() != 1) {
807 LLVM_DEBUG(
808 dbgs() << "We currently only support loops with 1 induction variable."
809 << "Failed to interchange due to current limitation\n");
810 ORE->emit([&]() {
811 return OptimizationRemarkMissed(DEBUG_TYPE, "MultiInductionInner",
812 InnerLoop->getStartLoc(),
813 InnerLoop->getHeader())
814 << "Only inner loops with 1 induction variable can be "
815 "interchanged currently.";
817 return true;
819 InnerInductionVar = Inductions.pop_back_val();
821 // TODO: Triangular loops are not handled for now.
822 if (!isLoopStructureUnderstood(InnerInductionVar)) {
823 LLVM_DEBUG(dbgs() << "Loop structure not understood by pass\n");
824 ORE->emit([&]() {
825 return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedStructureInner",
826 InnerLoop->getStartLoc(),
827 InnerLoop->getHeader())
828 << "Inner loop structure not understood currently.";
830 return true;
833 // TODO: We only handle LCSSA PHI's corresponding to reduction for now.
834 BasicBlock *InnerExit = InnerLoop->getExitBlock();
835 if (!containsSafePHI(InnerExit, false)) {
836 LLVM_DEBUG(
837 dbgs() << "Can only handle LCSSA PHIs in inner loops currently.\n");
838 ORE->emit([&]() {
839 return OptimizationRemarkMissed(DEBUG_TYPE, "NoLCSSAPHIOuterInner",
840 InnerLoop->getStartLoc(),
841 InnerLoop->getHeader())
842 << "Only inner loops with LCSSA PHIs can be interchange "
843 "currently.";
845 return true;
848 // TODO: Current limitation: Since we split the inner loop latch at the point
849 // were induction variable is incremented (induction.next); We cannot have
850 // more than 1 user of induction.next since it would result in broken code
851 // after split.
852 // e.g.
853 // for(i=0;i<N;i++) {
854 // for(j = 0;j<M;j++) {
855 // A[j+1][i+2] = A[j][i]+k;
856 // }
857 // }
858 Instruction *InnerIndexVarInc = nullptr;
859 if (InnerInductionVar->getIncomingBlock(0) == InnerLoopPreHeader)
860 InnerIndexVarInc =
861 dyn_cast<Instruction>(InnerInductionVar->getIncomingValue(1));
862 else
863 InnerIndexVarInc =
864 dyn_cast<Instruction>(InnerInductionVar->getIncomingValue(0));
866 if (!InnerIndexVarInc) {
867 LLVM_DEBUG(
868 dbgs() << "Did not find an instruction to increment the induction "
869 << "variable.\n");
870 ORE->emit([&]() {
871 return OptimizationRemarkMissed(DEBUG_TYPE, "NoIncrementInInner",
872 InnerLoop->getStartLoc(),
873 InnerLoop->getHeader())
874 << "The inner loop does not increment the induction variable.";
876 return true;
879 // Since we split the inner loop latch on this induction variable. Make sure
880 // we do not have any instruction between the induction variable and branch
881 // instruction.
883 bool FoundInduction = false;
884 for (const Instruction &I :
885 llvm::reverse(InnerLoopLatch->instructionsWithoutDebug())) {
886 if (isa<BranchInst>(I) || isa<CmpInst>(I) || isa<TruncInst>(I) ||
887 isa<ZExtInst>(I))
888 continue;
890 // We found an instruction. If this is not induction variable then it is not
891 // safe to split this loop latch.
892 if (!I.isIdenticalTo(InnerIndexVarInc)) {
893 LLVM_DEBUG(dbgs() << "Found unsupported instructions between induction "
894 << "variable increment and branch.\n");
895 ORE->emit([&]() {
896 return OptimizationRemarkMissed(
897 DEBUG_TYPE, "UnsupportedInsBetweenInduction",
898 InnerLoop->getStartLoc(), InnerLoop->getHeader())
899 << "Found unsupported instruction between induction variable "
900 "increment and branch.";
902 return true;
905 FoundInduction = true;
906 break;
908 // The loop latch ended and we didn't find the induction variable return as
909 // current limitation.
910 if (!FoundInduction) {
911 LLVM_DEBUG(dbgs() << "Did not find the induction variable.\n");
912 ORE->emit([&]() {
913 return OptimizationRemarkMissed(DEBUG_TYPE, "NoIndutionVariable",
914 InnerLoop->getStartLoc(),
915 InnerLoop->getHeader())
916 << "Did not find the induction variable.";
918 return true;
920 return false;
923 // We currently support LCSSA PHI nodes in the outer loop exit, if their
924 // incoming values do not come from the outer loop latch or if the
925 // outer loop latch has a single predecessor. In that case, the value will
926 // be available if both the inner and outer loop conditions are true, which
927 // will still be true after interchanging. If we have multiple predecessor,
928 // that may not be the case, e.g. because the outer loop latch may be executed
929 // if the inner loop is not executed.
930 static bool areLoopExitPHIsSupported(Loop *OuterLoop, Loop *InnerLoop) {
931 BasicBlock *LoopNestExit = OuterLoop->getUniqueExitBlock();
932 for (PHINode &PHI : LoopNestExit->phis()) {
933 // FIXME: We currently are not able to detect floating point reductions
934 // and have to use floating point PHIs as a proxy to prevent
935 // interchanging in the presence of floating point reductions.
936 if (PHI.getType()->isFloatingPointTy())
937 return false;
938 for (unsigned i = 0; i < PHI.getNumIncomingValues(); i++) {
939 Instruction *IncomingI = dyn_cast<Instruction>(PHI.getIncomingValue(i));
940 if (!IncomingI || IncomingI->getParent() != OuterLoop->getLoopLatch())
941 continue;
943 // The incoming value is defined in the outer loop latch. Currently we
944 // only support that in case the outer loop latch has a single predecessor.
945 // This guarantees that the outer loop latch is executed if and only if
946 // the inner loop is executed (because tightlyNested() guarantees that the
947 // outer loop header only branches to the inner loop or the outer loop
948 // latch).
949 // FIXME: We could weaken this logic and allow multiple predecessors,
950 // if the values are produced outside the loop latch. We would need
951 // additional logic to update the PHI nodes in the exit block as
952 // well.
953 if (OuterLoop->getLoopLatch()->getUniquePredecessor() == nullptr)
954 return false;
957 return true;
960 bool LoopInterchangeLegality::canInterchangeLoops(unsigned InnerLoopId,
961 unsigned OuterLoopId,
962 CharMatrix &DepMatrix) {
963 if (!isLegalToInterChangeLoops(DepMatrix, InnerLoopId, OuterLoopId)) {
964 LLVM_DEBUG(dbgs() << "Failed interchange InnerLoopId = " << InnerLoopId
965 << " and OuterLoopId = " << OuterLoopId
966 << " due to dependence\n");
967 ORE->emit([&]() {
968 return OptimizationRemarkMissed(DEBUG_TYPE, "Dependence",
969 InnerLoop->getStartLoc(),
970 InnerLoop->getHeader())
971 << "Cannot interchange loops due to dependences.";
973 return false;
975 // Check if outer and inner loop contain legal instructions only.
976 for (auto *BB : OuterLoop->blocks())
977 for (Instruction &I : BB->instructionsWithoutDebug())
978 if (CallInst *CI = dyn_cast<CallInst>(&I)) {
979 // readnone functions do not prevent interchanging.
980 if (CI->doesNotReadMemory())
981 continue;
982 LLVM_DEBUG(
983 dbgs() << "Loops with call instructions cannot be interchanged "
984 << "safely.");
985 ORE->emit([&]() {
986 return OptimizationRemarkMissed(DEBUG_TYPE, "CallInst",
987 CI->getDebugLoc(),
988 CI->getParent())
989 << "Cannot interchange loops due to call instruction.";
992 return false;
995 // TODO: The loops could not be interchanged due to current limitations in the
996 // transform module.
997 if (currentLimitations()) {
998 LLVM_DEBUG(dbgs() << "Not legal because of current transform limitation\n");
999 return false;
1002 // Check if the loops are tightly nested.
1003 if (!tightlyNested(OuterLoop, InnerLoop)) {
1004 LLVM_DEBUG(dbgs() << "Loops not tightly nested\n");
1005 ORE->emit([&]() {
1006 return OptimizationRemarkMissed(DEBUG_TYPE, "NotTightlyNested",
1007 InnerLoop->getStartLoc(),
1008 InnerLoop->getHeader())
1009 << "Cannot interchange loops because they are not tightly "
1010 "nested.";
1012 return false;
1015 if (!areLoopExitPHIsSupported(OuterLoop, InnerLoop)) {
1016 LLVM_DEBUG(dbgs() << "Found unsupported PHI nodes in outer loop exit.\n");
1017 ORE->emit([&]() {
1018 return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedExitPHI",
1019 OuterLoop->getStartLoc(),
1020 OuterLoop->getHeader())
1021 << "Found unsupported PHI node in loop exit.";
1023 return false;
1026 return true;
1029 int LoopInterchangeProfitability::getInstrOrderCost() {
1030 unsigned GoodOrder, BadOrder;
1031 BadOrder = GoodOrder = 0;
1032 for (BasicBlock *BB : InnerLoop->blocks()) {
1033 for (Instruction &Ins : *BB) {
1034 if (const GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(&Ins)) {
1035 unsigned NumOp = GEP->getNumOperands();
1036 bool FoundInnerInduction = false;
1037 bool FoundOuterInduction = false;
1038 for (unsigned i = 0; i < NumOp; ++i) {
1039 const SCEV *OperandVal = SE->getSCEV(GEP->getOperand(i));
1040 const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(OperandVal);
1041 if (!AR)
1042 continue;
1044 // If we find the inner induction after an outer induction e.g.
1045 // for(int i=0;i<N;i++)
1046 // for(int j=0;j<N;j++)
1047 // A[i][j] = A[i-1][j-1]+k;
1048 // then it is a good order.
1049 if (AR->getLoop() == InnerLoop) {
1050 // We found an InnerLoop induction after OuterLoop induction. It is
1051 // a good order.
1052 FoundInnerInduction = true;
1053 if (FoundOuterInduction) {
1054 GoodOrder++;
1055 break;
1058 // If we find the outer induction after an inner induction e.g.
1059 // for(int i=0;i<N;i++)
1060 // for(int j=0;j<N;j++)
1061 // A[j][i] = A[j-1][i-1]+k;
1062 // then it is a bad order.
1063 if (AR->getLoop() == OuterLoop) {
1064 // We found an OuterLoop induction after InnerLoop induction. It is
1065 // a bad order.
1066 FoundOuterInduction = true;
1067 if (FoundInnerInduction) {
1068 BadOrder++;
1069 break;
1076 return GoodOrder - BadOrder;
1079 static bool isProfitableForVectorization(unsigned InnerLoopId,
1080 unsigned OuterLoopId,
1081 CharMatrix &DepMatrix) {
1082 // TODO: Improve this heuristic to catch more cases.
1083 // If the inner loop is loop independent or doesn't carry any dependency it is
1084 // profitable to move this to outer position.
1085 for (auto &Row : DepMatrix) {
1086 if (Row[InnerLoopId] != 'S' && Row[InnerLoopId] != 'I')
1087 return false;
1088 // TODO: We need to improve this heuristic.
1089 if (Row[OuterLoopId] != '=')
1090 return false;
1092 // If outer loop has dependence and inner loop is loop independent then it is
1093 // profitable to interchange to enable parallelism.
1094 // If there are no dependences, interchanging will not improve anything.
1095 return !DepMatrix.empty();
1098 bool LoopInterchangeProfitability::isProfitable(unsigned InnerLoopId,
1099 unsigned OuterLoopId,
1100 CharMatrix &DepMatrix) {
1101 // TODO: Add better profitability checks.
1102 // e.g
1103 // 1) Construct dependency matrix and move the one with no loop carried dep
1104 // inside to enable vectorization.
1106 // This is rough cost estimation algorithm. It counts the good and bad order
1107 // of induction variables in the instruction and allows reordering if number
1108 // of bad orders is more than good.
1109 int Cost = getInstrOrderCost();
1110 LLVM_DEBUG(dbgs() << "Cost = " << Cost << "\n");
1111 if (Cost < -LoopInterchangeCostThreshold)
1112 return true;
1114 // It is not profitable as per current cache profitability model. But check if
1115 // we can move this loop outside to improve parallelism.
1116 if (isProfitableForVectorization(InnerLoopId, OuterLoopId, DepMatrix))
1117 return true;
1119 ORE->emit([&]() {
1120 return OptimizationRemarkMissed(DEBUG_TYPE, "InterchangeNotProfitable",
1121 InnerLoop->getStartLoc(),
1122 InnerLoop->getHeader())
1123 << "Interchanging loops is too costly (cost="
1124 << ore::NV("Cost", Cost) << ", threshold="
1125 << ore::NV("Threshold", LoopInterchangeCostThreshold)
1126 << ") and it does not improve parallelism.";
1128 return false;
1131 void LoopInterchangeTransform::removeChildLoop(Loop *OuterLoop,
1132 Loop *InnerLoop) {
1133 for (Loop *L : *OuterLoop)
1134 if (L == InnerLoop) {
1135 OuterLoop->removeChildLoop(L);
1136 return;
1138 llvm_unreachable("Couldn't find loop");
1141 /// Update LoopInfo, after interchanging. NewInner and NewOuter refer to the
1142 /// new inner and outer loop after interchanging: NewInner is the original
1143 /// outer loop and NewOuter is the original inner loop.
1145 /// Before interchanging, we have the following structure
1146 /// Outer preheader
1147 // Outer header
1148 // Inner preheader
1149 // Inner header
1150 // Inner body
1151 // Inner latch
1152 // outer bbs
1153 // Outer latch
1155 // After interchanging:
1156 // Inner preheader
1157 // Inner header
1158 // Outer preheader
1159 // Outer header
1160 // Inner body
1161 // outer bbs
1162 // Outer latch
1163 // Inner latch
1164 void LoopInterchangeTransform::restructureLoops(
1165 Loop *NewInner, Loop *NewOuter, BasicBlock *OrigInnerPreHeader,
1166 BasicBlock *OrigOuterPreHeader) {
1167 Loop *OuterLoopParent = OuterLoop->getParentLoop();
1168 // The original inner loop preheader moves from the new inner loop to
1169 // the parent loop, if there is one.
1170 NewInner->removeBlockFromLoop(OrigInnerPreHeader);
1171 LI->changeLoopFor(OrigInnerPreHeader, OuterLoopParent);
1173 // Switch the loop levels.
1174 if (OuterLoopParent) {
1175 // Remove the loop from its parent loop.
1176 removeChildLoop(OuterLoopParent, NewInner);
1177 removeChildLoop(NewInner, NewOuter);
1178 OuterLoopParent->addChildLoop(NewOuter);
1179 } else {
1180 removeChildLoop(NewInner, NewOuter);
1181 LI->changeTopLevelLoop(NewInner, NewOuter);
1183 while (!NewOuter->empty())
1184 NewInner->addChildLoop(NewOuter->removeChildLoop(NewOuter->begin()));
1185 NewOuter->addChildLoop(NewInner);
1187 // BBs from the original inner loop.
1188 SmallVector<BasicBlock *, 8> OrigInnerBBs(NewOuter->blocks());
1190 // Add BBs from the original outer loop to the original inner loop (excluding
1191 // BBs already in inner loop)
1192 for (BasicBlock *BB : NewInner->blocks())
1193 if (LI->getLoopFor(BB) == NewInner)
1194 NewOuter->addBlockEntry(BB);
1196 // Now remove inner loop header and latch from the new inner loop and move
1197 // other BBs (the loop body) to the new inner loop.
1198 BasicBlock *OuterHeader = NewOuter->getHeader();
1199 BasicBlock *OuterLatch = NewOuter->getLoopLatch();
1200 for (BasicBlock *BB : OrigInnerBBs) {
1201 // Nothing will change for BBs in child loops.
1202 if (LI->getLoopFor(BB) != NewOuter)
1203 continue;
1204 // Remove the new outer loop header and latch from the new inner loop.
1205 if (BB == OuterHeader || BB == OuterLatch)
1206 NewInner->removeBlockFromLoop(BB);
1207 else
1208 LI->changeLoopFor(BB, NewInner);
1211 // The preheader of the original outer loop becomes part of the new
1212 // outer loop.
1213 NewOuter->addBlockEntry(OrigOuterPreHeader);
1214 LI->changeLoopFor(OrigOuterPreHeader, NewOuter);
1216 // Tell SE that we move the loops around.
1217 SE->forgetLoop(NewOuter);
1218 SE->forgetLoop(NewInner);
1221 bool LoopInterchangeTransform::transform() {
1222 bool Transformed = false;
1223 Instruction *InnerIndexVar;
1225 if (InnerLoop->getSubLoops().empty()) {
1226 BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
1227 LLVM_DEBUG(dbgs() << "Splitting the inner loop latch\n");
1228 PHINode *InductionPHI = getInductionVariable(InnerLoop, SE);
1229 if (!InductionPHI) {
1230 LLVM_DEBUG(dbgs() << "Failed to find the point to split loop latch \n");
1231 return false;
1234 if (InductionPHI->getIncomingBlock(0) == InnerLoopPreHeader)
1235 InnerIndexVar = dyn_cast<Instruction>(InductionPHI->getIncomingValue(1));
1236 else
1237 InnerIndexVar = dyn_cast<Instruction>(InductionPHI->getIncomingValue(0));
1239 // Ensure that InductionPHI is the first Phi node.
1240 if (&InductionPHI->getParent()->front() != InductionPHI)
1241 InductionPHI->moveBefore(&InductionPHI->getParent()->front());
1243 // Create a new latch block for the inner loop. We split at the
1244 // current latch's terminator and then move the condition and all
1245 // operands that are not either loop-invariant or the induction PHI into the
1246 // new latch block.
1247 BasicBlock *NewLatch =
1248 SplitBlock(InnerLoop->getLoopLatch(),
1249 InnerLoop->getLoopLatch()->getTerminator(), DT, LI);
1251 SmallSetVector<Instruction *, 4> WorkList;
1252 unsigned i = 0;
1253 auto MoveInstructions = [&i, &WorkList, this, InductionPHI, NewLatch]() {
1254 for (; i < WorkList.size(); i++) {
1255 // Duplicate instruction and move it the new latch. Update uses that
1256 // have been moved.
1257 Instruction *NewI = WorkList[i]->clone();
1258 NewI->insertBefore(NewLatch->getFirstNonPHI());
1259 assert(!NewI->mayHaveSideEffects() &&
1260 "Moving instructions with side-effects may change behavior of "
1261 "the loop nest!");
1262 for (auto UI = WorkList[i]->use_begin(), UE = WorkList[i]->use_end();
1263 UI != UE;) {
1264 Use &U = *UI++;
1265 Instruction *UserI = cast<Instruction>(U.getUser());
1266 if (!InnerLoop->contains(UserI->getParent()) ||
1267 UserI->getParent() == NewLatch || UserI == InductionPHI)
1268 U.set(NewI);
1270 // Add operands of moved instruction to the worklist, except if they are
1271 // outside the inner loop or are the induction PHI.
1272 for (Value *Op : WorkList[i]->operands()) {
1273 Instruction *OpI = dyn_cast<Instruction>(Op);
1274 if (!OpI ||
1275 this->LI->getLoopFor(OpI->getParent()) != this->InnerLoop ||
1276 OpI == InductionPHI)
1277 continue;
1278 WorkList.insert(OpI);
1283 // FIXME: Should we interchange when we have a constant condition?
1284 Instruction *CondI = dyn_cast<Instruction>(
1285 cast<BranchInst>(InnerLoop->getLoopLatch()->getTerminator())
1286 ->getCondition());
1287 if (CondI)
1288 WorkList.insert(CondI);
1289 MoveInstructions();
1290 WorkList.insert(cast<Instruction>(InnerIndexVar));
1291 MoveInstructions();
1293 // Splits the inner loops phi nodes out into a separate basic block.
1294 BasicBlock *InnerLoopHeader = InnerLoop->getHeader();
1295 SplitBlock(InnerLoopHeader, InnerLoopHeader->getFirstNonPHI(), DT, LI);
1296 LLVM_DEBUG(dbgs() << "splitting InnerLoopHeader done\n");
1299 Transformed |= adjustLoopLinks();
1300 if (!Transformed) {
1301 LLVM_DEBUG(dbgs() << "adjustLoopLinks failed\n");
1302 return false;
1305 return true;
1308 /// \brief Move all instructions except the terminator from FromBB right before
1309 /// InsertBefore
1310 static void moveBBContents(BasicBlock *FromBB, Instruction *InsertBefore) {
1311 auto &ToList = InsertBefore->getParent()->getInstList();
1312 auto &FromList = FromBB->getInstList();
1314 ToList.splice(InsertBefore->getIterator(), FromList, FromList.begin(),
1315 FromBB->getTerminator()->getIterator());
1318 /// Update BI to jump to NewBB instead of OldBB. Records updates to
1319 /// the dominator tree in DTUpdates, if DT should be preserved.
1320 static void updateSuccessor(BranchInst *BI, BasicBlock *OldBB,
1321 BasicBlock *NewBB,
1322 std::vector<DominatorTree::UpdateType> &DTUpdates) {
1323 assert(llvm::count_if(successors(BI),
1324 [OldBB](BasicBlock *BB) { return BB == OldBB; }) < 2 &&
1325 "BI must jump to OldBB at most once.");
1326 for (unsigned i = 0, e = BI->getNumSuccessors(); i < e; ++i) {
1327 if (BI->getSuccessor(i) == OldBB) {
1328 BI->setSuccessor(i, NewBB);
1330 DTUpdates.push_back(
1331 {DominatorTree::UpdateKind::Insert, BI->getParent(), NewBB});
1332 DTUpdates.push_back(
1333 {DominatorTree::UpdateKind::Delete, BI->getParent(), OldBB});
1334 break;
1339 // Move Lcssa PHIs to the right place.
1340 static void moveLCSSAPhis(BasicBlock *InnerExit, BasicBlock *InnerHeader,
1341 BasicBlock *InnerLatch, BasicBlock *OuterHeader,
1342 BasicBlock *OuterLatch, BasicBlock *OuterExit) {
1344 // Deal with LCSSA PHI nodes in the exit block of the inner loop, that are
1345 // defined either in the header or latch. Those blocks will become header and
1346 // latch of the new outer loop, and the only possible users can PHI nodes
1347 // in the exit block of the loop nest or the outer loop header (reduction
1348 // PHIs, in that case, the incoming value must be defined in the inner loop
1349 // header). We can just substitute the user with the incoming value and remove
1350 // the PHI.
1351 for (PHINode &P : make_early_inc_range(InnerExit->phis())) {
1352 assert(P.getNumIncomingValues() == 1 &&
1353 "Only loops with a single exit are supported!");
1355 // Incoming values are guaranteed be instructions currently.
1356 auto IncI = cast<Instruction>(P.getIncomingValueForBlock(InnerLatch));
1357 // Skip phis with incoming values from the inner loop body, excluding the
1358 // header and latch.
1359 if (IncI->getParent() != InnerLatch && IncI->getParent() != InnerHeader)
1360 continue;
1362 assert(all_of(P.users(),
1363 [OuterHeader, OuterExit, IncI, InnerHeader](User *U) {
1364 return (cast<PHINode>(U)->getParent() == OuterHeader &&
1365 IncI->getParent() == InnerHeader) ||
1366 cast<PHINode>(U)->getParent() == OuterExit;
1367 }) &&
1368 "Can only replace phis iff the uses are in the loop nest exit or "
1369 "the incoming value is defined in the inner header (it will "
1370 "dominate all loop blocks after interchanging)");
1371 P.replaceAllUsesWith(IncI);
1372 P.eraseFromParent();
1375 SmallVector<PHINode *, 8> LcssaInnerExit;
1376 for (PHINode &P : InnerExit->phis())
1377 LcssaInnerExit.push_back(&P);
1379 SmallVector<PHINode *, 8> LcssaInnerLatch;
1380 for (PHINode &P : InnerLatch->phis())
1381 LcssaInnerLatch.push_back(&P);
1383 // Lcssa PHIs for values used outside the inner loop are in InnerExit.
1384 // If a PHI node has users outside of InnerExit, it has a use outside the
1385 // interchanged loop and we have to preserve it. We move these to
1386 // InnerLatch, which will become the new exit block for the innermost
1387 // loop after interchanging.
1388 for (PHINode *P : LcssaInnerExit)
1389 P->moveBefore(InnerLatch->getFirstNonPHI());
1391 // If the inner loop latch contains LCSSA PHIs, those come from a child loop
1392 // and we have to move them to the new inner latch.
1393 for (PHINode *P : LcssaInnerLatch)
1394 P->moveBefore(InnerExit->getFirstNonPHI());
1396 // Deal with LCSSA PHI nodes in the loop nest exit block. For PHIs that have
1397 // incoming values from the outer latch or header, we have to add a new PHI
1398 // in the inner loop latch, which became the exit block of the outer loop,
1399 // after interchanging.
1400 if (OuterExit) {
1401 for (PHINode &P : OuterExit->phis()) {
1402 if (P.getNumIncomingValues() != 1)
1403 continue;
1404 // Skip Phis with incoming values not defined in the outer loop's header
1405 // and latch. Also skip incoming phis defined in the latch. Those should
1406 // already have been updated.
1407 auto I = dyn_cast<Instruction>(P.getIncomingValue(0));
1408 if (!I || ((I->getParent() != OuterLatch || isa<PHINode>(I)) &&
1409 I->getParent() != OuterHeader))
1410 continue;
1412 PHINode *NewPhi = dyn_cast<PHINode>(P.clone());
1413 NewPhi->setIncomingValue(0, P.getIncomingValue(0));
1414 NewPhi->setIncomingBlock(0, OuterLatch);
1415 NewPhi->insertBefore(InnerLatch->getFirstNonPHI());
1416 P.setIncomingValue(0, NewPhi);
1420 // Now adjust the incoming blocks for the LCSSA PHIs.
1421 // For PHIs moved from Inner's exit block, we need to replace Inner's latch
1422 // with the new latch.
1423 InnerLatch->replacePhiUsesWith(InnerLatch, OuterLatch);
1426 bool LoopInterchangeTransform::adjustLoopBranches() {
1427 LLVM_DEBUG(dbgs() << "adjustLoopBranches called\n");
1428 std::vector<DominatorTree::UpdateType> DTUpdates;
1430 BasicBlock *OuterLoopPreHeader = OuterLoop->getLoopPreheader();
1431 BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
1433 assert(OuterLoopPreHeader != OuterLoop->getHeader() &&
1434 InnerLoopPreHeader != InnerLoop->getHeader() && OuterLoopPreHeader &&
1435 InnerLoopPreHeader && "Guaranteed by loop-simplify form");
1436 // Ensure that both preheaders do not contain PHI nodes and have single
1437 // predecessors. This allows us to move them easily. We use
1438 // InsertPreHeaderForLoop to create an 'extra' preheader, if the existing
1439 // preheaders do not satisfy those conditions.
1440 if (isa<PHINode>(OuterLoopPreHeader->begin()) ||
1441 !OuterLoopPreHeader->getUniquePredecessor())
1442 OuterLoopPreHeader =
1443 InsertPreheaderForLoop(OuterLoop, DT, LI, nullptr, true);
1444 if (InnerLoopPreHeader == OuterLoop->getHeader())
1445 InnerLoopPreHeader =
1446 InsertPreheaderForLoop(InnerLoop, DT, LI, nullptr, true);
1448 // Adjust the loop preheader
1449 BasicBlock *InnerLoopHeader = InnerLoop->getHeader();
1450 BasicBlock *OuterLoopHeader = OuterLoop->getHeader();
1451 BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch();
1452 BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch();
1453 BasicBlock *OuterLoopPredecessor = OuterLoopPreHeader->getUniquePredecessor();
1454 BasicBlock *InnerLoopLatchPredecessor =
1455 InnerLoopLatch->getUniquePredecessor();
1456 BasicBlock *InnerLoopLatchSuccessor;
1457 BasicBlock *OuterLoopLatchSuccessor;
1459 BranchInst *OuterLoopLatchBI =
1460 dyn_cast<BranchInst>(OuterLoopLatch->getTerminator());
1461 BranchInst *InnerLoopLatchBI =
1462 dyn_cast<BranchInst>(InnerLoopLatch->getTerminator());
1463 BranchInst *OuterLoopHeaderBI =
1464 dyn_cast<BranchInst>(OuterLoopHeader->getTerminator());
1465 BranchInst *InnerLoopHeaderBI =
1466 dyn_cast<BranchInst>(InnerLoopHeader->getTerminator());
1468 if (!OuterLoopPredecessor || !InnerLoopLatchPredecessor ||
1469 !OuterLoopLatchBI || !InnerLoopLatchBI || !OuterLoopHeaderBI ||
1470 !InnerLoopHeaderBI)
1471 return false;
1473 BranchInst *InnerLoopLatchPredecessorBI =
1474 dyn_cast<BranchInst>(InnerLoopLatchPredecessor->getTerminator());
1475 BranchInst *OuterLoopPredecessorBI =
1476 dyn_cast<BranchInst>(OuterLoopPredecessor->getTerminator());
1478 if (!OuterLoopPredecessorBI || !InnerLoopLatchPredecessorBI)
1479 return false;
1480 BasicBlock *InnerLoopHeaderSuccessor = InnerLoopHeader->getUniqueSuccessor();
1481 if (!InnerLoopHeaderSuccessor)
1482 return false;
1484 // Adjust Loop Preheader and headers
1485 updateSuccessor(OuterLoopPredecessorBI, OuterLoopPreHeader,
1486 InnerLoopPreHeader, DTUpdates);
1487 updateSuccessor(OuterLoopHeaderBI, OuterLoopLatch, LoopExit, DTUpdates);
1488 updateSuccessor(OuterLoopHeaderBI, InnerLoopPreHeader,
1489 InnerLoopHeaderSuccessor, DTUpdates);
1491 // Adjust reduction PHI's now that the incoming block has changed.
1492 InnerLoopHeaderSuccessor->replacePhiUsesWith(InnerLoopHeader,
1493 OuterLoopHeader);
1495 updateSuccessor(InnerLoopHeaderBI, InnerLoopHeaderSuccessor,
1496 OuterLoopPreHeader, DTUpdates);
1498 // -------------Adjust loop latches-----------
1499 if (InnerLoopLatchBI->getSuccessor(0) == InnerLoopHeader)
1500 InnerLoopLatchSuccessor = InnerLoopLatchBI->getSuccessor(1);
1501 else
1502 InnerLoopLatchSuccessor = InnerLoopLatchBI->getSuccessor(0);
1504 updateSuccessor(InnerLoopLatchPredecessorBI, InnerLoopLatch,
1505 InnerLoopLatchSuccessor, DTUpdates);
1508 if (OuterLoopLatchBI->getSuccessor(0) == OuterLoopHeader)
1509 OuterLoopLatchSuccessor = OuterLoopLatchBI->getSuccessor(1);
1510 else
1511 OuterLoopLatchSuccessor = OuterLoopLatchBI->getSuccessor(0);
1513 updateSuccessor(InnerLoopLatchBI, InnerLoopLatchSuccessor,
1514 OuterLoopLatchSuccessor, DTUpdates);
1515 updateSuccessor(OuterLoopLatchBI, OuterLoopLatchSuccessor, InnerLoopLatch,
1516 DTUpdates);
1518 DT->applyUpdates(DTUpdates);
1519 restructureLoops(OuterLoop, InnerLoop, InnerLoopPreHeader,
1520 OuterLoopPreHeader);
1522 moveLCSSAPhis(InnerLoopLatchSuccessor, InnerLoopHeader, InnerLoopLatch,
1523 OuterLoopHeader, OuterLoopLatch, InnerLoop->getExitBlock());
1524 // For PHIs in the exit block of the outer loop, outer's latch has been
1525 // replaced by Inners'.
1526 OuterLoopLatchSuccessor->replacePhiUsesWith(OuterLoopLatch, InnerLoopLatch);
1528 // Now update the reduction PHIs in the inner and outer loop headers.
1529 SmallVector<PHINode *, 4> InnerLoopPHIs, OuterLoopPHIs;
1530 for (PHINode &PHI : drop_begin(InnerLoopHeader->phis(), 1))
1531 InnerLoopPHIs.push_back(cast<PHINode>(&PHI));
1532 for (PHINode &PHI : drop_begin(OuterLoopHeader->phis(), 1))
1533 OuterLoopPHIs.push_back(cast<PHINode>(&PHI));
1535 auto &OuterInnerReductions = LIL.getOuterInnerReductions();
1536 (void)OuterInnerReductions;
1538 // Now move the remaining reduction PHIs from outer to inner loop header and
1539 // vice versa. The PHI nodes must be part of a reduction across the inner and
1540 // outer loop and all the remains to do is and updating the incoming blocks.
1541 for (PHINode *PHI : OuterLoopPHIs) {
1542 PHI->moveBefore(InnerLoopHeader->getFirstNonPHI());
1543 assert(OuterInnerReductions.find(PHI) != OuterInnerReductions.end() &&
1544 "Expected a reduction PHI node");
1546 for (PHINode *PHI : InnerLoopPHIs) {
1547 PHI->moveBefore(OuterLoopHeader->getFirstNonPHI());
1548 assert(OuterInnerReductions.find(PHI) != OuterInnerReductions.end() &&
1549 "Expected a reduction PHI node");
1552 // Update the incoming blocks for moved PHI nodes.
1553 OuterLoopHeader->replacePhiUsesWith(InnerLoopPreHeader, OuterLoopPreHeader);
1554 OuterLoopHeader->replacePhiUsesWith(InnerLoopLatch, OuterLoopLatch);
1555 InnerLoopHeader->replacePhiUsesWith(OuterLoopPreHeader, InnerLoopPreHeader);
1556 InnerLoopHeader->replacePhiUsesWith(OuterLoopLatch, InnerLoopLatch);
1558 return true;
1561 void LoopInterchangeTransform::adjustLoopPreheaders() {
1562 // We have interchanged the preheaders so we need to interchange the data in
1563 // the preheader as well.
1564 // This is because the content of inner preheader was previously executed
1565 // inside the outer loop.
1566 BasicBlock *OuterLoopPreHeader = OuterLoop->getLoopPreheader();
1567 BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
1568 BasicBlock *OuterLoopHeader = OuterLoop->getHeader();
1569 BranchInst *InnerTermBI =
1570 cast<BranchInst>(InnerLoopPreHeader->getTerminator());
1572 // These instructions should now be executed inside the loop.
1573 // Move instruction into a new block after outer header.
1574 moveBBContents(InnerLoopPreHeader, OuterLoopHeader->getTerminator());
1575 // These instructions were not executed previously in the loop so move them to
1576 // the older inner loop preheader.
1577 moveBBContents(OuterLoopPreHeader, InnerTermBI);
1580 bool LoopInterchangeTransform::adjustLoopLinks() {
1581 // Adjust all branches in the inner and outer loop.
1582 bool Changed = adjustLoopBranches();
1583 if (Changed)
1584 adjustLoopPreheaders();
1585 return Changed;
1588 char LoopInterchange::ID = 0;
1590 INITIALIZE_PASS_BEGIN(LoopInterchange, "loop-interchange",
1591 "Interchanges loops for cache reuse", false, false)
1592 INITIALIZE_PASS_DEPENDENCY(LoopPass)
1593 INITIALIZE_PASS_DEPENDENCY(DependenceAnalysisWrapperPass)
1594 INITIALIZE_PASS_DEPENDENCY(OptimizationRemarkEmitterWrapperPass)
1596 INITIALIZE_PASS_END(LoopInterchange, "loop-interchange",
1597 "Interchanges loops for cache reuse", false, false)
1599 Pass *llvm::createLoopInterchangePass() { return new LoopInterchange(); }