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/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"
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"));
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
) {
79 LLVM_DEBUG(dbgs() << D
<< " ");
80 LLVM_DEBUG(dbgs() << "\n");
85 static bool populateDependencyMatrix(CharMatrix
&DepMatrix
, unsigned Level
,
86 Loop
*L
, DependenceInfo
*DI
) {
87 using ValueVector
= SmallVector
<Value
*, 16>;
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
))
97 if (auto *Ld
= dyn_cast
<LoadInst
>(&I
)) {
100 MemInstr
.push_back(&I
);
101 } else if (auto *St
= dyn_cast
<StoreInst
>(&I
)) {
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
);
121 // Ignore Input dependencies.
122 if (isa
<LoadInst
>(Src
) && isa
<LoadInst
>(Dst
))
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();
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
);
139 const ConstantInt
*CI
= SCEVConst
->getValue();
140 if (CI
->isNegative())
142 else if (CI
->isZero())
146 Dep
.push_back(Direction
);
147 } else if (D
->isScalar(II
)) {
149 Dep
.push_back(Direction
);
151 unsigned Dir
= D
->getDirection(II
);
152 if (Dir
== Dependence::DVEntry::LT
||
153 Dir
== Dependence::DVEntry::LE
)
155 else if (Dir
== Dependence::DVEntry::GT
||
156 Dir
== Dependence::DVEntry::GE
)
158 else if (Dir
== Dependence::DVEntry::EQ
)
162 Dep
.push_back(Direction
);
165 while (Dep
.size() != Level
) {
169 DepMatrix
.push_back(Dep
);
170 if (DepMatrix
.size() > MaxMemInstrCount
) {
171 LLVM_DEBUG(dbgs() << "Cannot handle more than " << MaxMemInstrCount
172 << " dependencies inside loop\n");
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
,
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
196 static bool isOuterMostDepPositive(CharMatrix
&DepMatrix
, unsigned Row
,
198 for (unsigned i
= 0; i
<= Column
; ++i
) {
199 if (DepMatrix
[Row
][i
] == '<')
201 if (DepMatrix
[Row
][i
] == '>')
204 // All dependencies were '=','S' or 'I'
208 // Checks if no dependence exist in the dependency matrix in Row before Column.
209 static bool containsNoDependence(CharMatrix
&DepMatrix
, unsigned Row
,
211 for (unsigned i
= 0; i
< Column
; ++i
) {
212 if (DepMatrix
[Row
][i
] != '=' && DepMatrix
[Row
][i
] != 'S' &&
213 DepMatrix
[Row
][i
] != 'I')
219 static bool validDepInterchange(CharMatrix
&DepMatrix
, unsigned Row
,
220 unsigned OuterLoopId
, char InnerDep
,
222 if (isOuterMostDepPositive(DepMatrix
, Row
, OuterLoopId
))
225 if (InnerDep
== OuterDep
)
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')
237 if (InnerDep
== '>') {
238 // If OuterLoopId represents outermost loop then interchanging will make the
239 // 1st dependency as '>'
240 if (OuterLoopId
== 0)
243 // If all dependencies before OuterloopId are '=','S'or 'I'. Then
244 // interchanging will result in this row having an outermost non '='
246 if (!containsNoDependence(DepMatrix
, Row
, OuterLoopId
))
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
== '*')
267 if (!validDepInterchange(DepMatrix
, Row
, OuterLoopId
, InnerDep
, OuterDep
))
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');
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
283 // Discard all loops above it added into Worklist.
284 if (Vec
->size() != 1)
287 LoopList
.push_back(CurrentLoop
);
288 CurrentLoop
= Vec
->front();
289 Vec
= &CurrentLoop
->getSubLoops();
291 LoopList
.push_back(CurrentLoop
);
295 static PHINode
*getInductionVariable(Loop
*L
, ScalarEvolution
*SE
) {
296 PHINode
*InnerIndexVar
= L
->getCanonicalInductionVariable();
298 return InnerIndexVar
;
299 if (L
->getLoopLatch() == nullptr || L
->getLoopPredecessor() == 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())
307 const SCEVAddRecExpr
*AddRec
=
308 dyn_cast
<SCEVAddRecExpr
>(SE
->getSCEV(PhiVar
));
309 if (!AddRec
|| !AddRec
->isAffine())
311 const SCEV
*Step
= AddRec
->getStepRecurrence(*SE
);
312 if (!isa
<SCEVConstant
>(Step
))
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.
324 /// LoopInterchangeLegality checks if it is legal to interchange the loop.
325 class LoopInterchangeLegality
{
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
337 bool isLoopStructureUnderstood(PHINode
*InnerInductionVar
);
339 bool currentLimitations();
341 const SmallPtrSetImpl
<PHINode
*> &getOuterInnerReductions() const {
342 return OuterInnerReductions
;
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
,
362 /// Interface to emit optimization remarks.
363 OptimizationRemarkEmitter
*ORE
;
365 /// Set of reduction PHIs taking part of a reduction across the inner and
367 SmallPtrSet
<PHINode
*, 4> OuterInnerReductions
;
370 /// LoopInterchangeProfitability checks if it is profitable to interchange the
372 class LoopInterchangeProfitability
{
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
);
383 int getInstrOrderCost();
391 /// Interface to emit optimization remarks.
392 OptimizationRemarkEmitter
*ORE
;
395 /// LoopInterchangeTransform interchanges the loop.
396 class LoopInterchangeTransform
{
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.
407 void restructureLoops(Loop
*NewInner
, Loop
*NewOuter
,
408 BasicBlock
*OrigInnerPreHeader
,
409 BasicBlock
*OrigOuterPreHeader
);
410 void removeChildLoop(Loop
*OuterLoop
, Loop
*InnerLoop
);
413 bool adjustLoopLinks();
414 void adjustLoopPreheaders();
415 bool adjustLoopBranches();
425 BasicBlock
*LoopExit
;
427 const LoopInterchangeLegality
&LIL
;
430 // Main LoopInterchange Pass.
431 struct LoopInterchange
: public LoopPass
{
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())
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");
472 if (L
->getNumBackEdges() != 1) {
473 LLVM_DEBUG(dbgs() << "NumBackEdges is not equal to 1\n");
476 if (!L
->getExitingBlock()) {
477 LLVM_DEBUG(dbgs() << "Loop doesn't have unique exit block\n");
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");
497 if (LoopNestDepth
> MaxLoopNestDepth
) {
498 LLVM_DEBUG(dbgs() << "Cannot handle loops of depth greater than "
499 << MaxLoopNestDepth
<< "\n");
502 if (!isComputableLoopNest(LoopList
)) {
503 LLVM_DEBUG(dbgs() << "Not valid loop candidate for interchange\n");
507 LLVM_DEBUG(dbgs() << "Processing LoopList of size = " << LoopNestDepth
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");
517 #ifdef DUMP_DEP_MATRICIES
518 LLVM_DEBUG(dbgs() << "Dependence before interchange\n");
519 printDepMatrix(DependencyMatrix
);
522 // Get the Outermost loop exit.
523 BasicBlock
*LoopNestExit
= OuterMostLoop
->getExitBlock();
525 LLVM_DEBUG(dbgs() << "OuterMostLoop needs an unique exit block");
529 unsigned SelecLoopId
= selectLoopForInterchange(LoopList
);
530 // Move the selected loop outwards to the best possible position.
531 for (unsigned i
= SelecLoopId
; i
> 0; i
--) {
533 processLoop(LoopList
, i
, i
- 1, LoopNestExit
, DependencyMatrix
);
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
);
545 Changed
|= Interchanged
;
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");
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");
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
,
580 LLVM_DEBUG(dbgs() << "Loops interchanged.\n");
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
604 BranchInst
*OuterLoopHeaderBI
=
605 dyn_cast
<BranchInst
>(OuterLoopHeader
->getTerminator());
606 if (!OuterLoopHeaderBI
)
609 for (BasicBlock
*Succ
: successors(OuterLoopHeaderBI
))
610 if (Succ
!= InnerLoopPreHeader
&& Succ
!= InnerLoop
->getHeader() &&
611 Succ
!= OuterLoopLatch
)
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
))
621 LLVM_DEBUG(dbgs() << "Loops are perfectly nested\n");
622 // We have a perfect loop nest.
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
))
634 Instruction
*I
= dyn_cast
<Instruction
>(Val
);
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
)) {
650 // If SV is a LCSSA PHI node with a single incoming value, return the incoming
652 static Value
*followLCSSA(Value
*SV
) {
653 PHINode
*PHI
= dyn_cast
<PHINode
>(SV
);
657 if (PHI
->getNumIncomingValues() != 1)
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)
668 RecurrenceDescriptor RD
;
669 if (RecurrenceDescriptor::isReductionPHI(PHI
, L
, RD
))
678 bool LoopInterchangeLegality::findInductionAndReductions(
679 Loop
*L
, SmallVector
<PHINode
*, 8> &Inductions
, Loop
*InnerLoop
) {
680 if (!L
->getLoopLatch() || !L
->getLoopPredecessor())
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
);
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.
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");
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
);
704 !llvm::any_of(InnerRedPhi
->incoming_values(),
705 [&PHI
](Value
*V
) { return V
== &PHI
; })) {
708 << "Failed to recognize PHI as an induction or reduction.\n");
711 OuterInnerReductions
.insert(&PHI
);
712 OuterInnerReductions
.insert(InnerRedPhi
);
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)
724 Instruction
*Ins
= dyn_cast
<Instruction
>(PHI
.getIncomingValue(0));
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
)
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
743 if (InnerLoop
->getExitingBlock() != InnerLoopLatch
||
744 OuterLoop
->getExitingBlock() != OuterLoop
->getLoopLatch() ||
745 !isa
<BranchInst
>(InnerLoopLatch
->getTerminator()) ||
746 !isa
<BranchInst
>(OuterLoop
->getLoopLatch()->getTerminator())) {
748 dbgs() << "Loops where the latch is not the exiting block are not"
749 << " supported currently.\n");
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.";
760 PHINode
*InnerInductionVar
;
761 SmallVector
<PHINode
*, 8> Inductions
;
762 if (!findInductionAndReductions(OuterLoop
, Inductions
, InnerLoop
)) {
764 dbgs() << "Only outer loops with induction or reduction PHI nodes "
765 << "are supported currently.\n");
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.";
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");
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.";
791 if (!findInductionAndReductions(InnerLoop
, Inductions
, nullptr)) {
793 dbgs() << "Only inner loops with induction or reduction PHI nodes "
794 << "are supported currently.\n");
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.";
805 // TODO: Currently we handle only loops with 1 induction variable.
806 if (Inductions
.size() != 1) {
808 dbgs() << "We currently only support loops with 1 induction variable."
809 << "Failed to interchange due to current limitation\n");
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.";
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");
825 return OptimizationRemarkMissed(DEBUG_TYPE
, "UnsupportedStructureInner",
826 InnerLoop
->getStartLoc(),
827 InnerLoop
->getHeader())
828 << "Inner loop structure not understood currently.";
833 // TODO: We only handle LCSSA PHI's corresponding to reduction for now.
834 BasicBlock
*InnerExit
= InnerLoop
->getExitBlock();
835 if (!containsSafePHI(InnerExit
, false)) {
837 dbgs() << "Can only handle LCSSA PHIs in inner loops currently.\n");
839 return OptimizationRemarkMissed(DEBUG_TYPE
, "NoLCSSAPHIOuterInner",
840 InnerLoop
->getStartLoc(),
841 InnerLoop
->getHeader())
842 << "Only inner loops with LCSSA PHIs can be interchange "
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
853 // for(i=0;i<N;i++) {
854 // for(j = 0;j<M;j++) {
855 // A[j+1][i+2] = A[j][i]+k;
858 Instruction
*InnerIndexVarInc
= nullptr;
859 if (InnerInductionVar
->getIncomingBlock(0) == InnerLoopPreHeader
)
861 dyn_cast
<Instruction
>(InnerInductionVar
->getIncomingValue(1));
864 dyn_cast
<Instruction
>(InnerInductionVar
->getIncomingValue(0));
866 if (!InnerIndexVarInc
) {
868 dbgs() << "Did not find an instruction to increment the induction "
871 return OptimizationRemarkMissed(DEBUG_TYPE
, "NoIncrementInInner",
872 InnerLoop
->getStartLoc(),
873 InnerLoop
->getHeader())
874 << "The inner loop does not increment the induction variable.";
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
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
) ||
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");
896 return OptimizationRemarkMissed(
897 DEBUG_TYPE
, "UnsupportedInsBetweenInduction",
898 InnerLoop
->getStartLoc(), InnerLoop
->getHeader())
899 << "Found unsupported instruction between induction variable "
900 "increment and branch.";
905 FoundInduction
= true;
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");
913 return OptimizationRemarkMissed(DEBUG_TYPE
, "NoIndutionVariable",
914 InnerLoop
->getStartLoc(),
915 InnerLoop
->getHeader())
916 << "Did not find the induction variable.";
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())
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())
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
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
953 if (OuterLoop
->getLoopLatch()->getUniquePredecessor() == nullptr)
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");
968 return OptimizationRemarkMissed(DEBUG_TYPE
, "Dependence",
969 InnerLoop
->getStartLoc(),
970 InnerLoop
->getHeader())
971 << "Cannot interchange loops due to dependences.";
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())
983 dbgs() << "Loops with call instructions cannot be interchanged "
986 return OptimizationRemarkMissed(DEBUG_TYPE
, "CallInst",
989 << "Cannot interchange loops due to call instruction.";
995 // TODO: The loops could not be interchanged due to current limitations in the
997 if (currentLimitations()) {
998 LLVM_DEBUG(dbgs() << "Not legal because of current transform limitation\n");
1002 // Check if the loops are tightly nested.
1003 if (!tightlyNested(OuterLoop
, InnerLoop
)) {
1004 LLVM_DEBUG(dbgs() << "Loops not tightly nested\n");
1006 return OptimizationRemarkMissed(DEBUG_TYPE
, "NotTightlyNested",
1007 InnerLoop
->getStartLoc(),
1008 InnerLoop
->getHeader())
1009 << "Cannot interchange loops because they are not tightly "
1015 if (!areLoopExitPHIsSupported(OuterLoop
, InnerLoop
)) {
1016 LLVM_DEBUG(dbgs() << "Found unsupported PHI nodes in outer loop exit.\n");
1018 return OptimizationRemarkMissed(DEBUG_TYPE
, "UnsupportedExitPHI",
1019 OuterLoop
->getStartLoc(),
1020 OuterLoop
->getHeader())
1021 << "Found unsupported PHI node in loop exit.";
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
);
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
1052 FoundInnerInduction
= true;
1053 if (FoundOuterInduction
) {
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
1066 FoundOuterInduction
= true;
1067 if (FoundInnerInduction
) {
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')
1088 // TODO: We need to improve this heuristic.
1089 if (Row
[OuterLoopId
] != '=')
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.
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
)
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
))
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.";
1131 void LoopInterchangeTransform::removeChildLoop(Loop
*OuterLoop
,
1133 for (Loop
*L
: *OuterLoop
)
1134 if (L
== InnerLoop
) {
1135 OuterLoop
->removeChildLoop(L
);
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
1155 // After interchanging:
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
);
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
)
1204 // Remove the new outer loop header and latch from the new inner loop.
1205 if (BB
== OuterHeader
|| BB
== OuterLatch
)
1206 NewInner
->removeBlockFromLoop(BB
);
1208 LI
->changeLoopFor(BB
, NewInner
);
1211 // The preheader of the original outer loop becomes part of the new
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");
1234 if (InductionPHI
->getIncomingBlock(0) == InnerLoopPreHeader
)
1235 InnerIndexVar
= dyn_cast
<Instruction
>(InductionPHI
->getIncomingValue(1));
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
1247 BasicBlock
*NewLatch
=
1248 SplitBlock(InnerLoop
->getLoopLatch(),
1249 InnerLoop
->getLoopLatch()->getTerminator(), DT
, LI
);
1251 SmallSetVector
<Instruction
*, 4> WorkList
;
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
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 "
1262 for (auto UI
= WorkList
[i
]->use_begin(), UE
= WorkList
[i
]->use_end();
1265 Instruction
*UserI
= cast
<Instruction
>(U
.getUser());
1266 if (!InnerLoop
->contains(UserI
->getParent()) ||
1267 UserI
->getParent() == NewLatch
|| UserI
== InductionPHI
)
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
);
1275 this->LI
->getLoopFor(OpI
->getParent()) != this->InnerLoop
||
1276 OpI
== InductionPHI
)
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())
1288 WorkList
.insert(CondI
);
1290 WorkList
.insert(cast
<Instruction
>(InnerIndexVar
));
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();
1301 LLVM_DEBUG(dbgs() << "adjustLoopLinks failed\n");
1308 /// \brief Move all instructions except the terminator from FromBB right before
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
,
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
});
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
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
)
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
;
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.
1401 for (PHINode
&P
: OuterExit
->phis()) {
1402 if (P
.getNumIncomingValues() != 1)
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
))
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
||
1473 BranchInst
*InnerLoopLatchPredecessorBI
=
1474 dyn_cast
<BranchInst
>(InnerLoopLatchPredecessor
->getTerminator());
1475 BranchInst
*OuterLoopPredecessorBI
=
1476 dyn_cast
<BranchInst
>(OuterLoopPredecessor
->getTerminator());
1478 if (!OuterLoopPredecessorBI
|| !InnerLoopLatchPredecessorBI
)
1480 BasicBlock
*InnerLoopHeaderSuccessor
= InnerLoopHeader
->getUniqueSuccessor();
1481 if (!InnerLoopHeaderSuccessor
)
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
,
1495 updateSuccessor(InnerLoopHeaderBI
, InnerLoopHeaderSuccessor
,
1496 OuterLoopPreHeader
, DTUpdates
);
1498 // -------------Adjust loop latches-----------
1499 if (InnerLoopLatchBI
->getSuccessor(0) == InnerLoopHeader
)
1500 InnerLoopLatchSuccessor
= InnerLoopLatchBI
->getSuccessor(1);
1502 InnerLoopLatchSuccessor
= InnerLoopLatchBI
->getSuccessor(0);
1504 updateSuccessor(InnerLoopLatchPredecessorBI
, InnerLoopLatch
,
1505 InnerLoopLatchSuccessor
, DTUpdates
);
1508 if (OuterLoopLatchBI
->getSuccessor(0) == OuterLoopHeader
)
1509 OuterLoopLatchSuccessor
= OuterLoopLatchBI
->getSuccessor(1);
1511 OuterLoopLatchSuccessor
= OuterLoopLatchBI
->getSuccessor(0);
1513 updateSuccessor(InnerLoopLatchBI
, InnerLoopLatchSuccessor
,
1514 OuterLoopLatchSuccessor
, DTUpdates
);
1515 updateSuccessor(OuterLoopLatchBI
, OuterLoopLatchSuccessor
, InnerLoopLatch
,
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
);
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();
1584 adjustLoopPreheaders();
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(); }