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.
12 //
13 //===----------------------------------------------------------------------===//
14
15 #include "llvm/Transforms/Scalar/LoopInterchange.h"
16 #include "llvm/ADT/STLExtras.h"
17 #include "llvm/ADT/SmallVector.h"
18 #include "llvm/ADT/Statistic.h"
19 #include "llvm/ADT/StringRef.h"
20 #include "llvm/Analysis/DependenceAnalysis.h"
21 #include "llvm/Analysis/LoopInfo.h"
22 #include "llvm/Analysis/LoopPass.h"
23 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
24 #include "llvm/Analysis/ScalarEvolution.h"
25 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
26 #include "llvm/IR/BasicBlock.h"
27 #include "llvm/IR/Constants.h"
28 #include "llvm/IR/DiagnosticInfo.h"
29 #include "llvm/IR/Dominators.h"
30 #include "llvm/IR/Function.h"
31 #include "llvm/IR/IRBuilder.h"
32 #include "llvm/IR/InstrTypes.h"
33 #include "llvm/IR/Instruction.h"
34 #include "llvm/IR/Instructions.h"
35 #include "llvm/IR/Type.h"
36 #include "llvm/IR/User.h"
37 #include "llvm/IR/Value.h"
38 #include "llvm/InitializePasses.h"
39 #include "llvm/Pass.h"
40 #include "llvm/Support/Casting.h"
41 #include "llvm/Support/CommandLine.h"
42 #include "llvm/Support/Debug.h"
43 #include "llvm/Support/ErrorHandling.h"
44 #include "llvm/Support/raw_ostream.h"
45 #include "llvm/Transforms/Scalar.h"
46 #include "llvm/Transforms/Utils.h"
47 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
48 #include "llvm/Transforms/Utils/LoopUtils.h"
49 #include <cassert>
50 #include <utility>
51 #include <vector>
52
53 using namespace llvm;
54
55 #define DEBUG_TYPE "loop-interchange"
56
57 STATISTIC(LoopsInterchanged, "Number of loops interchanged");
58
59 static cl::opt<int> LoopInterchangeCostThreshold(
60 "loop-interchange-threshold", cl::init(0), cl::Hidden,
61 cl::desc("Interchange if you gain more than this number"));
62
63 namespace {
64
65 using LoopVector = SmallVector<Loop *, 8>;
66
67 // TODO: Check if we can use a sparse matrix here.
68 using CharMatrix = std::vector<std::vector<char>>;
69
70 } // end anonymous namespace
71
72 // Maximum number of dependencies that can be handled in the dependency matrix.
73 static const unsigned MaxMemInstrCount = 100;
74
75 // Maximum loop depth supported.
76 static const unsigned MaxLoopNestDepth = 10;
77
78 #ifdef DUMP_DEP_MATRICIES
printDepMatrix(CharMatrix & DepMatrix)79 static void printDepMatrix(CharMatrix &DepMatrix) {
80 for (auto &Row : DepMatrix) {
81 for (auto D : Row)
82 LLVM_DEBUG(dbgs() << D << " ");
83 LLVM_DEBUG(dbgs() << "\n");
84 }
85 }
86 #endif
87
populateDependencyMatrix(CharMatrix & DepMatrix,unsigned Level,Loop * L,DependenceInfo * DI)88 static bool populateDependencyMatrix(CharMatrix &DepMatrix, unsigned Level,
89 Loop *L, DependenceInfo *DI) {
90 using ValueVector = SmallVector<Value *, 16>;
91
92 ValueVector MemInstr;
93
94 // For each block.
95 for (BasicBlock *BB : L->blocks()) {
96 // Scan the BB and collect legal loads and stores.
97 for (Instruction &I : *BB) {
98 if (!isa<Instruction>(I))
99 return false;
100 if (auto *Ld = dyn_cast<LoadInst>(&I)) {
101 if (!Ld->isSimple())
102 return false;
103 MemInstr.push_back(&I);
104 } else if (auto *St = dyn_cast<StoreInst>(&I)) {
105 if (!St->isSimple())
106 return false;
107 MemInstr.push_back(&I);
108 }
109 }
110 }
111
112 LLVM_DEBUG(dbgs() << "Found " << MemInstr.size()
113 << " Loads and Stores to analyze\n");
114
115 ValueVector::iterator I, IE, J, JE;
116
117 for (I = MemInstr.begin(), IE = MemInstr.end(); I != IE; ++I) {
118 for (J = I, JE = MemInstr.end(); J != JE; ++J) {
119 std::vector<char> Dep;
120 Instruction *Src = cast<Instruction>(*I);
121 Instruction *Dst = cast<Instruction>(*J);
122 if (Src == Dst)
123 continue;
124 // Ignore Input dependencies.
125 if (isa<LoadInst>(Src) && isa<LoadInst>(Dst))
126 continue;
127 // Track Output, Flow, and Anti dependencies.
128 if (auto D = DI->depends(Src, Dst, true)) {
129 assert(D->isOrdered() && "Expected an output, flow or anti dep.");
130 LLVM_DEBUG(StringRef DepType =
131 D->isFlow() ? "flow" : D->isAnti() ? "anti" : "output";
132 dbgs() << "Found " << DepType
133 << " dependency between Src and Dst\n"
134 << " Src:" << *Src << "\n Dst:" << *Dst << '\n');
135 unsigned Levels = D->getLevels();
136 char Direction;
137 for (unsigned II = 1; II <= Levels; ++II) {
138 const SCEV *Distance = D->getDistance(II);
139 const SCEVConstant *SCEVConst =
140 dyn_cast_or_null<SCEVConstant>(Distance);
141 if (SCEVConst) {
142 const ConstantInt *CI = SCEVConst->getValue();
143 if (CI->isNegative())
144 Direction = '<';
145 else if (CI->isZero())
146 Direction = '=';
147 else
148 Direction = '>';
149 Dep.push_back(Direction);
150 } else if (D->isScalar(II)) {
151 Direction = 'S';
152 Dep.push_back(Direction);
153 } else {
154 unsigned Dir = D->getDirection(II);
155 if (Dir == Dependence::DVEntry::LT ||
156 Dir == Dependence::DVEntry::LE)
157 Direction = '<';
158 else if (Dir == Dependence::DVEntry::GT ||
159 Dir == Dependence::DVEntry::GE)
160 Direction = '>';
161 else if (Dir == Dependence::DVEntry::EQ)
162 Direction = '=';
163 else
164 Direction = '*';
165 Dep.push_back(Direction);
166 }
167 }
168 while (Dep.size() != Level) {
169 Dep.push_back('I');
170 }
171
172 DepMatrix.push_back(Dep);
173 if (DepMatrix.size() > MaxMemInstrCount) {
174 LLVM_DEBUG(dbgs() << "Cannot handle more than " << MaxMemInstrCount
175 << " dependencies inside loop\n");
176 return false;
177 }
178 }
179 }
180 }
181
182 return true;
183 }
184
185 // A loop is moved from index 'from' to an index 'to'. Update the Dependence
186 // matrix by exchanging the two columns.
interChangeDependencies(CharMatrix & DepMatrix,unsigned FromIndx,unsigned ToIndx)187 static void interChangeDependencies(CharMatrix &DepMatrix, unsigned FromIndx,
188 unsigned ToIndx) {
189 unsigned numRows = DepMatrix.size();
190 for (unsigned i = 0; i < numRows; ++i) {
191 char TmpVal = DepMatrix[i][ToIndx];
192 DepMatrix[i][ToIndx] = DepMatrix[i][FromIndx];
193 DepMatrix[i][FromIndx] = TmpVal;
194 }
195 }
196
197 // Checks if outermost non '=','S'or'I' dependence in the dependence matrix is
198 // '>'
isOuterMostDepPositive(CharMatrix & DepMatrix,unsigned Row,unsigned Column)199 static bool isOuterMostDepPositive(CharMatrix &DepMatrix, unsigned Row,
200 unsigned Column) {
201 for (unsigned i = 0; i <= Column; ++i) {
202 if (DepMatrix[Row][i] == '<')
203 return false;
204 if (DepMatrix[Row][i] == '>')
205 return true;
206 }
207 // All dependencies were '=','S' or 'I'
208 return false;
209 }
210
211 // Checks if no dependence exist in the dependency matrix in Row before Column.
containsNoDependence(CharMatrix & DepMatrix,unsigned Row,unsigned Column)212 static bool containsNoDependence(CharMatrix &DepMatrix, unsigned Row,
213 unsigned Column) {
214 for (unsigned i = 0; i < Column; ++i) {
215 if (DepMatrix[Row][i] != '=' && DepMatrix[Row][i] != 'S' &&
216 DepMatrix[Row][i] != 'I')
217 return false;
218 }
219 return true;
220 }
221
validDepInterchange(CharMatrix & DepMatrix,unsigned Row,unsigned OuterLoopId,char InnerDep,char OuterDep)222 static bool validDepInterchange(CharMatrix &DepMatrix, unsigned Row,
223 unsigned OuterLoopId, char InnerDep,
224 char OuterDep) {
225 if (isOuterMostDepPositive(DepMatrix, Row, OuterLoopId))
226 return false;
227
228 if (InnerDep == OuterDep)
229 return true;
230
231 // It is legal to interchange if and only if after interchange no row has a
232 // '>' direction as the leftmost non-'='.
233
234 if (InnerDep == '=' || InnerDep == 'S' || InnerDep == 'I')
235 return true;
236
237 if (InnerDep == '<')
238 return true;
239
240 if (InnerDep == '>') {
241 // If OuterLoopId represents outermost loop then interchanging will make the
242 // 1st dependency as '>'
243 if (OuterLoopId == 0)
244 return false;
245
246 // If all dependencies before OuterloopId are '=','S'or 'I'. Then
247 // interchanging will result in this row having an outermost non '='
248 // dependency of '>'
249 if (!containsNoDependence(DepMatrix, Row, OuterLoopId))
250 return true;
251 }
252
253 return false;
254 }
255
256 // Checks if it is legal to interchange 2 loops.
257 // [Theorem] A permutation of the loops in a perfect nest is legal if and only
258 // if the direction matrix, after the same permutation is applied to its
259 // columns, has no ">" direction as the leftmost non-"=" direction in any row.
isLegalToInterChangeLoops(CharMatrix & DepMatrix,unsigned InnerLoopId,unsigned OuterLoopId)260 static bool isLegalToInterChangeLoops(CharMatrix &DepMatrix,
261 unsigned InnerLoopId,
262 unsigned OuterLoopId) {
263 unsigned NumRows = DepMatrix.size();
264 // For each row check if it is valid to interchange.
265 for (unsigned Row = 0; Row < NumRows; ++Row) {
266 char InnerDep = DepMatrix[Row][InnerLoopId];
267 char OuterDep = DepMatrix[Row][OuterLoopId];
268 if (InnerDep == '*' || OuterDep == '*')
269 return false;
270 if (!validDepInterchange(DepMatrix, Row, OuterLoopId, InnerDep, OuterDep))
271 return false;
272 }
273 return true;
274 }
275
populateWorklist(Loop & L)276 static LoopVector populateWorklist(Loop &L) {
277 LLVM_DEBUG(dbgs() << "Calling populateWorklist on Func: "
278 << L.getHeader()->getParent()->getName() << " Loop: %"
279 << L.getHeader()->getName() << '\n');
280 LoopVector LoopList;
281 Loop *CurrentLoop = &L;
282 const std::vector<Loop *> *Vec = &CurrentLoop->getSubLoops();
283 while (!Vec->empty()) {
284 // The current loop has multiple subloops in it hence it is not tightly
285 // nested.
286 // Discard all loops above it added into Worklist.
287 if (Vec->size() != 1)
288 return {};
289
290 LoopList.push_back(CurrentLoop);
291 CurrentLoop = Vec->front();
292 Vec = &CurrentLoop->getSubLoops();
293 }
294 LoopList.push_back(CurrentLoop);
295 return LoopList;
296 }
297
getInductionVariable(Loop * L,ScalarEvolution * SE)298 static PHINode *getInductionVariable(Loop *L, ScalarEvolution *SE) {
299 PHINode *InnerIndexVar = L->getCanonicalInductionVariable();
300 if (InnerIndexVar)
301 return InnerIndexVar;
302 if (L->getLoopLatch() == nullptr || L->getLoopPredecessor() == nullptr)
303 return nullptr;
304 for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) {
305 PHINode *PhiVar = cast<PHINode>(I);
306 Type *PhiTy = PhiVar->getType();
307 if (!PhiTy->isIntegerTy() && !PhiTy->isFloatingPointTy() &&
308 !PhiTy->isPointerTy())
309 return nullptr;
310 const SCEVAddRecExpr *AddRec =
311 dyn_cast<SCEVAddRecExpr>(SE->getSCEV(PhiVar));
312 if (!AddRec || !AddRec->isAffine())
313 continue;
314 const SCEV *Step = AddRec->getStepRecurrence(*SE);
315 if (!isa<SCEVConstant>(Step))
316 continue;
317 // Found the induction variable.
318 // FIXME: Handle loops with more than one induction variable. Note that,
319 // currently, legality makes sure we have only one induction variable.
320 return PhiVar;
321 }
322 return nullptr;
323 }
324
325 namespace {
326
327 /// LoopInterchangeLegality checks if it is legal to interchange the loop.
328 class LoopInterchangeLegality {
329 public:
LoopInterchangeLegality(Loop * Outer,Loop * Inner,ScalarEvolution * SE,OptimizationRemarkEmitter * ORE)330 LoopInterchangeLegality(Loop *Outer, Loop *Inner, ScalarEvolution *SE,
331 OptimizationRemarkEmitter *ORE)
332 : OuterLoop(Outer), InnerLoop(Inner), SE(SE), ORE(ORE) {}
333
334 /// Check if the loops can be interchanged.
335 bool canInterchangeLoops(unsigned InnerLoopId, unsigned OuterLoopId,
336 CharMatrix &DepMatrix);
337
338 /// Check if the loop structure is understood. We do not handle triangular
339 /// loops for now.
340 bool isLoopStructureUnderstood(PHINode *InnerInductionVar);
341
342 bool currentLimitations();
343
getOuterInnerReductions() const344 const SmallPtrSetImpl<PHINode *> &getOuterInnerReductions() const {
345 return OuterInnerReductions;
346 }
347
348 private:
349 bool tightlyNested(Loop *Outer, Loop *Inner);
350 bool containsUnsafeInstructions(BasicBlock *BB);
351
352 /// Discover induction and reduction PHIs in the header of \p L. Induction
353 /// PHIs are added to \p Inductions, reductions are added to
354 /// OuterInnerReductions. When the outer loop is passed, the inner loop needs
355 /// to be passed as \p InnerLoop.
356 bool findInductionAndReductions(Loop *L,
357 SmallVector<PHINode *, 8> &Inductions,
358 Loop *InnerLoop);
359
360 Loop *OuterLoop;
361 Loop *InnerLoop;
362
363 ScalarEvolution *SE;
364
365 /// Interface to emit optimization remarks.
366 OptimizationRemarkEmitter *ORE;
367
368 /// Set of reduction PHIs taking part of a reduction across the inner and
369 /// outer loop.
370 SmallPtrSet<PHINode *, 4> OuterInnerReductions;
371 };
372
373 /// LoopInterchangeProfitability checks if it is profitable to interchange the
374 /// loop.
375 class LoopInterchangeProfitability {
376 public:
LoopInterchangeProfitability(Loop * Outer,Loop * Inner,ScalarEvolution * SE,OptimizationRemarkEmitter * ORE)377 LoopInterchangeProfitability(Loop *Outer, Loop *Inner, ScalarEvolution *SE,
378 OptimizationRemarkEmitter *ORE)
379 : OuterLoop(Outer), InnerLoop(Inner), SE(SE), ORE(ORE) {}
380
381 /// Check if the loop interchange is profitable.
382 bool isProfitable(unsigned InnerLoopId, unsigned OuterLoopId,
383 CharMatrix &DepMatrix);
384
385 private:
386 int getInstrOrderCost();
387
388 Loop *OuterLoop;
389 Loop *InnerLoop;
390
391 /// Scev analysis.
392 ScalarEvolution *SE;
393
394 /// Interface to emit optimization remarks.
395 OptimizationRemarkEmitter *ORE;
396 };
397
398 /// LoopInterchangeTransform interchanges the loop.
399 class LoopInterchangeTransform {
400 public:
LoopInterchangeTransform(Loop * Outer,Loop * Inner,ScalarEvolution * SE,LoopInfo * LI,DominatorTree * DT,BasicBlock * LoopNestExit,const LoopInterchangeLegality & LIL)401 LoopInterchangeTransform(Loop *Outer, Loop *Inner, ScalarEvolution *SE,
402 LoopInfo *LI, DominatorTree *DT,
403 BasicBlock *LoopNestExit,
404 const LoopInterchangeLegality &LIL)
405 : OuterLoop(Outer), InnerLoop(Inner), SE(SE), LI(LI), DT(DT),
406 LoopExit(LoopNestExit), LIL(LIL) {}
407
408 /// Interchange OuterLoop and InnerLoop.
409 bool transform();
410 void restructureLoops(Loop *NewInner, Loop *NewOuter,
411 BasicBlock *OrigInnerPreHeader,
412 BasicBlock *OrigOuterPreHeader);
413 void removeChildLoop(Loop *OuterLoop, Loop *InnerLoop);
414
415 private:
416 bool adjustLoopLinks();
417 bool adjustLoopBranches();
418
419 Loop *OuterLoop;
420 Loop *InnerLoop;
421
422 /// Scev analysis.
423 ScalarEvolution *SE;
424
425 LoopInfo *LI;
426 DominatorTree *DT;
427 BasicBlock *LoopExit;
428
429 const LoopInterchangeLegality &LIL;
430 };
431
432 struct LoopInterchange {
433 ScalarEvolution *SE = nullptr;
434 LoopInfo *LI = nullptr;
435 DependenceInfo *DI = nullptr;
436 DominatorTree *DT = nullptr;
437
438 /// Interface to emit optimization remarks.
439 OptimizationRemarkEmitter *ORE;
440
LoopInterchange__anon21544b6d0211::LoopInterchange441 LoopInterchange(ScalarEvolution *SE, LoopInfo *LI, DependenceInfo *DI,
442 DominatorTree *DT, OptimizationRemarkEmitter *ORE)
443 : SE(SE), LI(LI), DI(DI), DT(DT), ORE(ORE) {}
444
run__anon21544b6d0211::LoopInterchange445 bool run(Loop *L) {
446 if (L->getParentLoop())
447 return false;
448
449 return processLoopList(populateWorklist(*L));
450 }
451
isComputableLoopNest__anon21544b6d0211::LoopInterchange452 bool isComputableLoopNest(LoopVector LoopList) {
453 for (Loop *L : LoopList) {
454 const SCEV *ExitCountOuter = SE->getBackedgeTakenCount(L);
455 if (isa<SCEVCouldNotCompute>(ExitCountOuter)) {
456 LLVM_DEBUG(dbgs() << "Couldn't compute backedge count\n");
457 return false;
458 }
459 if (L->getNumBackEdges() != 1) {
460 LLVM_DEBUG(dbgs() << "NumBackEdges is not equal to 1\n");
461 return false;
462 }
463 if (!L->getExitingBlock()) {
464 LLVM_DEBUG(dbgs() << "Loop doesn't have unique exit block\n");
465 return false;
466 }
467 }
468 return true;
469 }
470
selectLoopForInterchange__anon21544b6d0211::LoopInterchange471 unsigned selectLoopForInterchange(const LoopVector &LoopList) {
472 // TODO: Add a better heuristic to select the loop to be interchanged based
473 // on the dependence matrix. Currently we select the innermost loop.
474 return LoopList.size() - 1;
475 }
476
processLoopList__anon21544b6d0211::LoopInterchange477 bool processLoopList(LoopVector LoopList) {
478 bool Changed = false;
479 unsigned LoopNestDepth = LoopList.size();
480 if (LoopNestDepth < 2) {
481 LLVM_DEBUG(dbgs() << "Loop doesn't contain minimum nesting level.\n");
482 return false;
483 }
484 if (LoopNestDepth > MaxLoopNestDepth) {
485 LLVM_DEBUG(dbgs() << "Cannot handle loops of depth greater than "
486 << MaxLoopNestDepth << "\n");
487 return false;
488 }
489 if (!isComputableLoopNest(LoopList)) {
490 LLVM_DEBUG(dbgs() << "Not valid loop candidate for interchange\n");
491 return false;
492 }
493
494 LLVM_DEBUG(dbgs() << "Processing LoopList of size = " << LoopNestDepth
495 << "\n");
496
497 CharMatrix DependencyMatrix;
498 Loop *OuterMostLoop = *(LoopList.begin());
499 if (!populateDependencyMatrix(DependencyMatrix, LoopNestDepth,
500 OuterMostLoop, DI)) {
501 LLVM_DEBUG(dbgs() << "Populating dependency matrix failed\n");
502 return false;
503 }
504 #ifdef DUMP_DEP_MATRICIES
505 LLVM_DEBUG(dbgs() << "Dependence before interchange\n");
506 printDepMatrix(DependencyMatrix);
507 #endif
508
509 // Get the Outermost loop exit.
510 BasicBlock *LoopNestExit = OuterMostLoop->getExitBlock();
511 if (!LoopNestExit) {
512 LLVM_DEBUG(dbgs() << "OuterMostLoop needs an unique exit block");
513 return false;
514 }
515
516 unsigned SelecLoopId = selectLoopForInterchange(LoopList);
517 // Move the selected loop outwards to the best possible position.
518 for (unsigned i = SelecLoopId; i > 0; i--) {
519 bool Interchanged =
520 processLoop(LoopList, i, i - 1, LoopNestExit, DependencyMatrix);
521 if (!Interchanged)
522 return Changed;
523 // Loops interchanged reflect the same in LoopList
524 std::swap(LoopList[i - 1], LoopList[i]);
525
526 // Update the DependencyMatrix
527 interChangeDependencies(DependencyMatrix, i, i - 1);
528 #ifdef DUMP_DEP_MATRICIES
529 LLVM_DEBUG(dbgs() << "Dependence after interchange\n");
530 printDepMatrix(DependencyMatrix);
531 #endif
532 Changed |= Interchanged;
533 }
534 return Changed;
535 }
536
processLoop__anon21544b6d0211::LoopInterchange537 bool processLoop(LoopVector LoopList, unsigned InnerLoopId,
538 unsigned OuterLoopId, BasicBlock *LoopNestExit,
539 std::vector<std::vector<char>> &DependencyMatrix) {
540 LLVM_DEBUG(dbgs() << "Processing Inner Loop Id = " << InnerLoopId
541 << " and OuterLoopId = " << OuterLoopId << "\n");
542 Loop *InnerLoop = LoopList[InnerLoopId];
543 Loop *OuterLoop = LoopList[OuterLoopId];
544
545 LoopInterchangeLegality LIL(OuterLoop, InnerLoop, SE, ORE);
546 if (!LIL.canInterchangeLoops(InnerLoopId, OuterLoopId, DependencyMatrix)) {
547 LLVM_DEBUG(dbgs() << "Not interchanging loops. Cannot prove legality.\n");
548 return false;
549 }
550 LLVM_DEBUG(dbgs() << "Loops are legal to interchange\n");
551 LoopInterchangeProfitability LIP(OuterLoop, InnerLoop, SE, ORE);
552 if (!LIP.isProfitable(InnerLoopId, OuterLoopId, DependencyMatrix)) {
553 LLVM_DEBUG(dbgs() << "Interchanging loops not profitable.\n");
554 return false;
555 }
556
557 ORE->emit([&]() {
558 return OptimizationRemark(DEBUG_TYPE, "Interchanged",
559 InnerLoop->getStartLoc(),
560 InnerLoop->getHeader())
561 << "Loop interchanged with enclosing loop.";
562 });
563
564 LoopInterchangeTransform LIT(OuterLoop, InnerLoop, SE, LI, DT, LoopNestExit,
565 LIL);
566 LIT.transform();
567 LLVM_DEBUG(dbgs() << "Loops interchanged.\n");
568 LoopsInterchanged++;
569
570 assert(InnerLoop->isLCSSAForm(*DT) &&
571 "Inner loop not left in LCSSA form after loop interchange!");
572 assert(OuterLoop->isLCSSAForm(*DT) &&
573 "Outer loop not left in LCSSA form after loop interchange!");
574
575 return true;
576 }
577 };
578
579 } // end anonymous namespace
580
containsUnsafeInstructions(BasicBlock * BB)581 bool LoopInterchangeLegality::containsUnsafeInstructions(BasicBlock *BB) {
582 return any_of(*BB, [](const Instruction &I) {
583 return I.mayHaveSideEffects() || I.mayReadFromMemory();
584 });
585 }
586
tightlyNested(Loop * OuterLoop,Loop * InnerLoop)587 bool LoopInterchangeLegality::tightlyNested(Loop *OuterLoop, Loop *InnerLoop) {
588 BasicBlock *OuterLoopHeader = OuterLoop->getHeader();
589 BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
590 BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch();
591
592 LLVM_DEBUG(dbgs() << "Checking if loops are tightly nested\n");
593
594 // A perfectly nested loop will not have any branch in between the outer and
595 // inner block i.e. outer header will branch to either inner preheader and
596 // outerloop latch.
597 BranchInst *OuterLoopHeaderBI =
598 dyn_cast<BranchInst>(OuterLoopHeader->getTerminator());
599 if (!OuterLoopHeaderBI)
600 return false;
601
602 for (BasicBlock *Succ : successors(OuterLoopHeaderBI))
603 if (Succ != InnerLoopPreHeader && Succ != InnerLoop->getHeader() &&
604 Succ != OuterLoopLatch)
605 return false;
606
607 LLVM_DEBUG(dbgs() << "Checking instructions in Loop header and Loop latch\n");
608 // We do not have any basic block in between now make sure the outer header
609 // and outer loop latch doesn't contain any unsafe instructions.
610 if (containsUnsafeInstructions(OuterLoopHeader) ||
611 containsUnsafeInstructions(OuterLoopLatch))
612 return false;
613
614 // Also make sure the inner loop preheader does not contain any unsafe
615 // instructions. Note that all instructions in the preheader will be moved to
616 // the outer loop header when interchanging.
617 if (InnerLoopPreHeader != OuterLoopHeader &&
618 containsUnsafeInstructions(InnerLoopPreHeader))
619 return false;
620
621 LLVM_DEBUG(dbgs() << "Loops are perfectly nested\n");
622 // We have a perfect loop nest.
623 return true;
624 }
625
isLoopStructureUnderstood(PHINode * InnerInduction)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;
645 }
646 }
647 return true;
648 }
649
650 // If SV is a LCSSA PHI node with a single incoming value, return the incoming
651 // value.
followLCSSA(Value * SV)652 static Value *followLCSSA(Value *SV) {
653 PHINode *PHI = dyn_cast<PHINode>(SV);
654 if (!PHI)
655 return SV;
656
657 if (PHI->getNumIncomingValues() != 1)
658 return SV;
659 return followLCSSA(PHI->getIncomingValue(0));
660 }
661
662 // Check V's users to see if it is involved in a reduction in L.
findInnerReductionPhi(Loop * L,Value * V)663 static PHINode *findInnerReductionPhi(Loop *L, Value *V) {
664 // Reduction variables cannot be constants.
665 if (isa<Constant>(V))
666 return nullptr;
667
668 for (Value *User : V->users()) {
669 if (PHINode *PHI = dyn_cast<PHINode>(User)) {
670 if (PHI->getNumIncomingValues() == 1)
671 continue;
672 RecurrenceDescriptor RD;
673 if (RecurrenceDescriptor::isReductionPHI(PHI, L, RD))
674 return PHI;
675 return nullptr;
676 }
677 }
678
679 return nullptr;
680 }
681
findInductionAndReductions(Loop * L,SmallVector<PHINode *,8> & Inductions,Loop * InnerLoop)682 bool LoopInterchangeLegality::findInductionAndReductions(
683 Loop *L, SmallVector<PHINode *, 8> &Inductions, Loop *InnerLoop) {
684 if (!L->getLoopLatch() || !L->getLoopPredecessor())
685 return false;
686 for (PHINode &PHI : L->getHeader()->phis()) {
687 RecurrenceDescriptor RD;
688 InductionDescriptor ID;
689 if (InductionDescriptor::isInductionPHI(&PHI, L, SE, ID))
690 Inductions.push_back(&PHI);
691 else {
692 // PHIs in inner loops need to be part of a reduction in the outer loop,
693 // discovered when checking the PHIs of the outer loop earlier.
694 if (!InnerLoop) {
695 if (!OuterInnerReductions.count(&PHI)) {
696 LLVM_DEBUG(dbgs() << "Inner loop PHI is not part of reductions "
697 "across the outer loop.\n");
698 return false;
699 }
700 } else {
701 assert(PHI.getNumIncomingValues() == 2 &&
702 "Phis in loop header should have exactly 2 incoming values");
703 // Check if we have a PHI node in the outer loop that has a reduction
704 // result from the inner loop as an incoming value.
705 Value *V = followLCSSA(PHI.getIncomingValueForBlock(L->getLoopLatch()));
706 PHINode *InnerRedPhi = findInnerReductionPhi(InnerLoop, V);
707 if (!InnerRedPhi ||
708 !llvm::is_contained(InnerRedPhi->incoming_values(), &PHI)) {
709 LLVM_DEBUG(
710 dbgs()
711 << "Failed to recognize PHI as an induction or reduction.\n");
712 return false;
713 }
714 OuterInnerReductions.insert(&PHI);
715 OuterInnerReductions.insert(InnerRedPhi);
716 }
717 }
718 }
719 return true;
720 }
721
722 // This function indicates the current limitations in the transform as a result
723 // of which we do not proceed.
currentLimitations()724 bool LoopInterchangeLegality::currentLimitations() {
725 BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
726 BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch();
727
728 // transform currently expects the loop latches to also be the exiting
729 // blocks.
730 if (InnerLoop->getExitingBlock() != InnerLoopLatch ||
731 OuterLoop->getExitingBlock() != OuterLoop->getLoopLatch() ||
732 !isa<BranchInst>(InnerLoopLatch->getTerminator()) ||
733 !isa<BranchInst>(OuterLoop->getLoopLatch()->getTerminator())) {
734 LLVM_DEBUG(
735 dbgs() << "Loops where the latch is not the exiting block are not"
736 << " supported currently.\n");
737 ORE->emit([&]() {
738 return OptimizationRemarkMissed(DEBUG_TYPE, "ExitingNotLatch",
739 OuterLoop->getStartLoc(),
740 OuterLoop->getHeader())
741 << "Loops where the latch is not the exiting block cannot be"
742 " interchange currently.";
743 });
744 return true;
745 }
746
747 PHINode *InnerInductionVar;
748 SmallVector<PHINode *, 8> Inductions;
749 if (!findInductionAndReductions(OuterLoop, Inductions, InnerLoop)) {
750 LLVM_DEBUG(
751 dbgs() << "Only outer loops with induction or reduction PHI nodes "
752 << "are supported currently.\n");
753 ORE->emit([&]() {
754 return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedPHIOuter",
755 OuterLoop->getStartLoc(),
756 OuterLoop->getHeader())
757 << "Only outer loops with induction or reduction PHI nodes can be"
758 " interchanged currently.";
759 });
760 return true;
761 }
762
763 // TODO: Currently we handle only loops with 1 induction variable.
764 if (Inductions.size() != 1) {
765 LLVM_DEBUG(dbgs() << "Loops with more than 1 induction variables are not "
766 << "supported currently.\n");
767 ORE->emit([&]() {
768 return OptimizationRemarkMissed(DEBUG_TYPE, "MultiIndutionOuter",
769 OuterLoop->getStartLoc(),
770 OuterLoop->getHeader())
771 << "Only outer loops with 1 induction variable can be "
772 "interchanged currently.";
773 });
774 return true;
775 }
776
777 Inductions.clear();
778 if (!findInductionAndReductions(InnerLoop, Inductions, nullptr)) {
779 LLVM_DEBUG(
780 dbgs() << "Only inner loops with induction or reduction PHI nodes "
781 << "are supported currently.\n");
782 ORE->emit([&]() {
783 return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedPHIInner",
784 InnerLoop->getStartLoc(),
785 InnerLoop->getHeader())
786 << "Only inner loops with induction or reduction PHI nodes can be"
787 " interchange currently.";
788 });
789 return true;
790 }
791
792 // TODO: Currently we handle only loops with 1 induction variable.
793 if (Inductions.size() != 1) {
794 LLVM_DEBUG(
795 dbgs() << "We currently only support loops with 1 induction variable."
796 << "Failed to interchange due to current limitation\n");
797 ORE->emit([&]() {
798 return OptimizationRemarkMissed(DEBUG_TYPE, "MultiInductionInner",
799 InnerLoop->getStartLoc(),
800 InnerLoop->getHeader())
801 << "Only inner loops with 1 induction variable can be "
802 "interchanged currently.";
803 });
804 return true;
805 }
806 InnerInductionVar = Inductions.pop_back_val();
807
808 // TODO: Triangular loops are not handled for now.
809 if (!isLoopStructureUnderstood(InnerInductionVar)) {
810 LLVM_DEBUG(dbgs() << "Loop structure not understood by pass\n");
811 ORE->emit([&]() {
812 return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedStructureInner",
813 InnerLoop->getStartLoc(),
814 InnerLoop->getHeader())
815 << "Inner loop structure not understood currently.";
816 });
817 return true;
818 }
819
820 // TODO: Current limitation: Since we split the inner loop latch at the point
821 // were induction variable is incremented (induction.next); We cannot have
822 // more than 1 user of induction.next since it would result in broken code
823 // after split.
824 // e.g.
825 // for(i=0;i<N;i++) {
826 // for(j = 0;j<M;j++) {
827 // A[j+1][i+2] = A[j][i]+k;
828 // }
829 // }
830 Instruction *InnerIndexVarInc = nullptr;
831 if (InnerInductionVar->getIncomingBlock(0) == InnerLoopPreHeader)
832 InnerIndexVarInc =
833 dyn_cast<Instruction>(InnerInductionVar->getIncomingValue(1));
834 else
835 InnerIndexVarInc =
836 dyn_cast<Instruction>(InnerInductionVar->getIncomingValue(0));
837
838 if (!InnerIndexVarInc) {
839 LLVM_DEBUG(
840 dbgs() << "Did not find an instruction to increment the induction "
841 << "variable.\n");
842 ORE->emit([&]() {
843 return OptimizationRemarkMissed(DEBUG_TYPE, "NoIncrementInInner",
844 InnerLoop->getStartLoc(),
845 InnerLoop->getHeader())
846 << "The inner loop does not increment the induction variable.";
847 });
848 return true;
849 }
850
851 // Since we split the inner loop latch on this induction variable. Make sure
852 // we do not have any instruction between the induction variable and branch
853 // instruction.
854
855 bool FoundInduction = false;
856 for (const Instruction &I :
857 llvm::reverse(InnerLoopLatch->instructionsWithoutDebug())) {
858 if (isa<BranchInst>(I) || isa<CmpInst>(I) || isa<TruncInst>(I) ||
859 isa<ZExtInst>(I))
860 continue;
861
862 // We found an instruction. If this is not induction variable then it is not
863 // safe to split this loop latch.
864 if (!I.isIdenticalTo(InnerIndexVarInc)) {
865 LLVM_DEBUG(dbgs() << "Found unsupported instructions between induction "
866 << "variable increment and branch.\n");
867 ORE->emit([&]() {
868 return OptimizationRemarkMissed(
869 DEBUG_TYPE, "UnsupportedInsBetweenInduction",
870 InnerLoop->getStartLoc(), InnerLoop->getHeader())
871 << "Found unsupported instruction between induction variable "
872 "increment and branch.";
873 });
874 return true;
875 }
876
877 FoundInduction = true;
878 break;
879 }
880 // The loop latch ended and we didn't find the induction variable return as
881 // current limitation.
882 if (!FoundInduction) {
883 LLVM_DEBUG(dbgs() << "Did not find the induction variable.\n");
884 ORE->emit([&]() {
885 return OptimizationRemarkMissed(DEBUG_TYPE, "NoIndutionVariable",
886 InnerLoop->getStartLoc(),
887 InnerLoop->getHeader())
888 << "Did not find the induction variable.";
889 });
890 return true;
891 }
892 return false;
893 }
894
895 // We currently only support LCSSA PHI nodes in the inner loop exit, if their
896 // users are either reduction PHIs or PHIs outside the outer loop (which means
897 // the we are only interested in the final value after the loop).
898 static bool
areInnerLoopExitPHIsSupported(Loop * InnerL,Loop * OuterL,SmallPtrSetImpl<PHINode * > & Reductions)899 areInnerLoopExitPHIsSupported(Loop *InnerL, Loop *OuterL,
900 SmallPtrSetImpl<PHINode *> &Reductions) {
901 BasicBlock *InnerExit = OuterL->getUniqueExitBlock();
902 for (PHINode &PHI : InnerExit->phis()) {
903 // Reduction lcssa phi will have only 1 incoming block that from loop latch.
904 if (PHI.getNumIncomingValues() > 1)
905 return false;
906 if (any_of(PHI.users(), [&Reductions, OuterL](User *U) {
907 PHINode *PN = dyn_cast<PHINode>(U);
908 return !PN ||
909 (!Reductions.count(PN) && OuterL->contains(PN->getParent()));
910 })) {
911 return false;
912 }
913 }
914 return true;
915 }
916
917 // We currently support LCSSA PHI nodes in the outer loop exit, if their
918 // incoming values do not come from the outer loop latch or if the
919 // outer loop latch has a single predecessor. In that case, the value will
920 // be available if both the inner and outer loop conditions are true, which
921 // will still be true after interchanging. If we have multiple predecessor,
922 // that may not be the case, e.g. because the outer loop latch may be executed
923 // if the inner loop is not executed.
areOuterLoopExitPHIsSupported(Loop * OuterLoop,Loop * InnerLoop)924 static bool areOuterLoopExitPHIsSupported(Loop *OuterLoop, Loop *InnerLoop) {
925 BasicBlock *LoopNestExit = OuterLoop->getUniqueExitBlock();
926 for (PHINode &PHI : LoopNestExit->phis()) {
927 // FIXME: We currently are not able to detect floating point reductions
928 // and have to use floating point PHIs as a proxy to prevent
929 // interchanging in the presence of floating point reductions.
930 if (PHI.getType()->isFloatingPointTy())
931 return false;
932 for (unsigned i = 0; i < PHI.getNumIncomingValues(); i++) {
933 Instruction *IncomingI = dyn_cast<Instruction>(PHI.getIncomingValue(i));
934 if (!IncomingI || IncomingI->getParent() != OuterLoop->getLoopLatch())
935 continue;
936
937 // The incoming value is defined in the outer loop latch. Currently we
938 // only support that in case the outer loop latch has a single predecessor.
939 // This guarantees that the outer loop latch is executed if and only if
940 // the inner loop is executed (because tightlyNested() guarantees that the
941 // outer loop header only branches to the inner loop or the outer loop
942 // latch).
943 // FIXME: We could weaken this logic and allow multiple predecessors,
944 // if the values are produced outside the loop latch. We would need
945 // additional logic to update the PHI nodes in the exit block as
946 // well.
947 if (OuterLoop->getLoopLatch()->getUniquePredecessor() == nullptr)
948 return false;
949 }
950 }
951 return true;
952 }
953
canInterchangeLoops(unsigned InnerLoopId,unsigned OuterLoopId,CharMatrix & DepMatrix)954 bool LoopInterchangeLegality::canInterchangeLoops(unsigned InnerLoopId,
955 unsigned OuterLoopId,
956 CharMatrix &DepMatrix) {
957 if (!isLegalToInterChangeLoops(DepMatrix, InnerLoopId, OuterLoopId)) {
958 LLVM_DEBUG(dbgs() << "Failed interchange InnerLoopId = " << InnerLoopId
959 << " and OuterLoopId = " << OuterLoopId
960 << " due to dependence\n");
961 ORE->emit([&]() {
962 return OptimizationRemarkMissed(DEBUG_TYPE, "Dependence",
963 InnerLoop->getStartLoc(),
964 InnerLoop->getHeader())
965 << "Cannot interchange loops due to dependences.";
966 });
967 return false;
968 }
969 // Check if outer and inner loop contain legal instructions only.
970 for (auto *BB : OuterLoop->blocks())
971 for (Instruction &I : BB->instructionsWithoutDebug())
972 if (CallInst *CI = dyn_cast<CallInst>(&I)) {
973 // readnone functions do not prevent interchanging.
974 if (CI->doesNotReadMemory())
975 continue;
976 LLVM_DEBUG(
977 dbgs() << "Loops with call instructions cannot be interchanged "
978 << "safely.");
979 ORE->emit([&]() {
980 return OptimizationRemarkMissed(DEBUG_TYPE, "CallInst",
981 CI->getDebugLoc(),
982 CI->getParent())
983 << "Cannot interchange loops due to call instruction.";
984 });
985
986 return false;
987 }
988
989 // TODO: The loops could not be interchanged due to current limitations in the
990 // transform module.
991 if (currentLimitations()) {
992 LLVM_DEBUG(dbgs() << "Not legal because of current transform limitation\n");
993 return false;
994 }
995
996 // Check if the loops are tightly nested.
997 if (!tightlyNested(OuterLoop, InnerLoop)) {
998 LLVM_DEBUG(dbgs() << "Loops not tightly nested\n");
999 ORE->emit([&]() {
1000 return OptimizationRemarkMissed(DEBUG_TYPE, "NotTightlyNested",
1001 InnerLoop->getStartLoc(),
1002 InnerLoop->getHeader())
1003 << "Cannot interchange loops because they are not tightly "
1004 "nested.";
1005 });
1006 return false;
1007 }
1008
1009 if (!areInnerLoopExitPHIsSupported(OuterLoop, InnerLoop,
1010 OuterInnerReductions)) {
1011 LLVM_DEBUG(dbgs() << "Found unsupported PHI nodes in inner loop exit.\n");
1012 ORE->emit([&]() {
1013 return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedExitPHI",
1014 InnerLoop->getStartLoc(),
1015 InnerLoop->getHeader())
1016 << "Found unsupported PHI node in loop exit.";
1017 });
1018 return false;
1019 }
1020
1021 if (!areOuterLoopExitPHIsSupported(OuterLoop, InnerLoop)) {
1022 LLVM_DEBUG(dbgs() << "Found unsupported PHI nodes in outer loop exit.\n");
1023 ORE->emit([&]() {
1024 return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedExitPHI",
1025 OuterLoop->getStartLoc(),
1026 OuterLoop->getHeader())
1027 << "Found unsupported PHI node in loop exit.";
1028 });
1029 return false;
1030 }
1031
1032 return true;
1033 }
1034
getInstrOrderCost()1035 int LoopInterchangeProfitability::getInstrOrderCost() {
1036 unsigned GoodOrder, BadOrder;
1037 BadOrder = GoodOrder = 0;
1038 for (BasicBlock *BB : InnerLoop->blocks()) {
1039 for (Instruction &Ins : *BB) {
1040 if (const GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(&Ins)) {
1041 unsigned NumOp = GEP->getNumOperands();
1042 bool FoundInnerInduction = false;
1043 bool FoundOuterInduction = false;
1044 for (unsigned i = 0; i < NumOp; ++i) {
1045 // Skip operands that are not SCEV-able.
1046 if (!SE->isSCEVable(GEP->getOperand(i)->getType()))
1047 continue;
1048
1049 const SCEV *OperandVal = SE->getSCEV(GEP->getOperand(i));
1050 const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(OperandVal);
1051 if (!AR)
1052 continue;
1053
1054 // If we find the inner induction after an outer induction e.g.
1055 // for(int i=0;i<N;i++)
1056 // for(int j=0;j<N;j++)
1057 // A[i][j] = A[i-1][j-1]+k;
1058 // then it is a good order.
1059 if (AR->getLoop() == InnerLoop) {
1060 // We found an InnerLoop induction after OuterLoop induction. It is
1061 // a good order.
1062 FoundInnerInduction = true;
1063 if (FoundOuterInduction) {
1064 GoodOrder++;
1065 break;
1066 }
1067 }
1068 // If we find the outer induction after an inner induction e.g.
1069 // for(int i=0;i<N;i++)
1070 // for(int j=0;j<N;j++)
1071 // A[j][i] = A[j-1][i-1]+k;
1072 // then it is a bad order.
1073 if (AR->getLoop() == OuterLoop) {
1074 // We found an OuterLoop induction after InnerLoop induction. It is
1075 // a bad order.
1076 FoundOuterInduction = true;
1077 if (FoundInnerInduction) {
1078 BadOrder++;
1079 break;
1080 }
1081 }
1082 }
1083 }
1084 }
1085 }
1086 return GoodOrder - BadOrder;
1087 }
1088
isProfitableForVectorization(unsigned InnerLoopId,unsigned OuterLoopId,CharMatrix & DepMatrix)1089 static bool isProfitableForVectorization(unsigned InnerLoopId,
1090 unsigned OuterLoopId,
1091 CharMatrix &DepMatrix) {
1092 // TODO: Improve this heuristic to catch more cases.
1093 // If the inner loop is loop independent or doesn't carry any dependency it is
1094 // profitable to move this to outer position.
1095 for (auto &Row : DepMatrix) {
1096 if (Row[InnerLoopId] != 'S' && Row[InnerLoopId] != 'I')
1097 return false;
1098 // TODO: We need to improve this heuristic.
1099 if (Row[OuterLoopId] != '=')
1100 return false;
1101 }
1102 // If outer loop has dependence and inner loop is loop independent then it is
1103 // profitable to interchange to enable parallelism.
1104 // If there are no dependences, interchanging will not improve anything.
1105 return !DepMatrix.empty();
1106 }
1107
isProfitable(unsigned InnerLoopId,unsigned OuterLoopId,CharMatrix & DepMatrix)1108 bool LoopInterchangeProfitability::isProfitable(unsigned InnerLoopId,
1109 unsigned OuterLoopId,
1110 CharMatrix &DepMatrix) {
1111 // TODO: Add better profitability checks.
1112 // e.g
1113 // 1) Construct dependency matrix and move the one with no loop carried dep
1114 // inside to enable vectorization.
1115
1116 // This is rough cost estimation algorithm. It counts the good and bad order
1117 // of induction variables in the instruction and allows reordering if number
1118 // of bad orders is more than good.
1119 int Cost = getInstrOrderCost();
1120 LLVM_DEBUG(dbgs() << "Cost = " << Cost << "\n");
1121 if (Cost < -LoopInterchangeCostThreshold)
1122 return true;
1123
1124 // It is not profitable as per current cache profitability model. But check if
1125 // we can move this loop outside to improve parallelism.
1126 if (isProfitableForVectorization(InnerLoopId, OuterLoopId, DepMatrix))
1127 return true;
1128
1129 ORE->emit([&]() {
1130 return OptimizationRemarkMissed(DEBUG_TYPE, "InterchangeNotProfitable",
1131 InnerLoop->getStartLoc(),
1132 InnerLoop->getHeader())
1133 << "Interchanging loops is too costly (cost="
1134 << ore::NV("Cost", Cost) << ", threshold="
1135 << ore::NV("Threshold", LoopInterchangeCostThreshold)
1136 << ") and it does not improve parallelism.";
1137 });
1138 return false;
1139 }
1140
removeChildLoop(Loop * OuterLoop,Loop * InnerLoop)1141 void LoopInterchangeTransform::removeChildLoop(Loop *OuterLoop,
1142 Loop *InnerLoop) {
1143 for (Loop *L : *OuterLoop)
1144 if (L == InnerLoop) {
1145 OuterLoop->removeChildLoop(L);
1146 return;
1147 }
1148 llvm_unreachable("Couldn't find loop");
1149 }
1150
1151 /// Update LoopInfo, after interchanging. NewInner and NewOuter refer to the
1152 /// new inner and outer loop after interchanging: NewInner is the original
1153 /// outer loop and NewOuter is the original inner loop.
1154 ///
1155 /// Before interchanging, we have the following structure
1156 /// Outer preheader
1157 // Outer header
1158 // Inner preheader
1159 // Inner header
1160 // Inner body
1161 // Inner latch
1162 // outer bbs
1163 // Outer latch
1164 //
1165 // After interchanging:
1166 // Inner preheader
1167 // Inner header
1168 // Outer preheader
1169 // Outer header
1170 // Inner body
1171 // outer bbs
1172 // Outer latch
1173 // Inner latch
restructureLoops(Loop * NewInner,Loop * NewOuter,BasicBlock * OrigInnerPreHeader,BasicBlock * OrigOuterPreHeader)1174 void LoopInterchangeTransform::restructureLoops(
1175 Loop *NewInner, Loop *NewOuter, BasicBlock *OrigInnerPreHeader,
1176 BasicBlock *OrigOuterPreHeader) {
1177 Loop *OuterLoopParent = OuterLoop->getParentLoop();
1178 // The original inner loop preheader moves from the new inner loop to
1179 // the parent loop, if there is one.
1180 NewInner->removeBlockFromLoop(OrigInnerPreHeader);
1181 LI->changeLoopFor(OrigInnerPreHeader, OuterLoopParent);
1182
1183 // Switch the loop levels.
1184 if (OuterLoopParent) {
1185 // Remove the loop from its parent loop.
1186 removeChildLoop(OuterLoopParent, NewInner);
1187 removeChildLoop(NewInner, NewOuter);
1188 OuterLoopParent->addChildLoop(NewOuter);
1189 } else {
1190 removeChildLoop(NewInner, NewOuter);
1191 LI->changeTopLevelLoop(NewInner, NewOuter);
1192 }
1193 while (!NewOuter->isInnermost())
1194 NewInner->addChildLoop(NewOuter->removeChildLoop(NewOuter->begin()));
1195 NewOuter->addChildLoop(NewInner);
1196
1197 // BBs from the original inner loop.
1198 SmallVector<BasicBlock *, 8> OrigInnerBBs(NewOuter->blocks());
1199
1200 // Add BBs from the original outer loop to the original inner loop (excluding
1201 // BBs already in inner loop)
1202 for (BasicBlock *BB : NewInner->blocks())
1203 if (LI->getLoopFor(BB) == NewInner)
1204 NewOuter->addBlockEntry(BB);
1205
1206 // Now remove inner loop header and latch from the new inner loop and move
1207 // other BBs (the loop body) to the new inner loop.
1208 BasicBlock *OuterHeader = NewOuter->getHeader();
1209 BasicBlock *OuterLatch = NewOuter->getLoopLatch();
1210 for (BasicBlock *BB : OrigInnerBBs) {
1211 // Nothing will change for BBs in child loops.
1212 if (LI->getLoopFor(BB) != NewOuter)
1213 continue;
1214 // Remove the new outer loop header and latch from the new inner loop.
1215 if (BB == OuterHeader || BB == OuterLatch)
1216 NewInner->removeBlockFromLoop(BB);
1217 else
1218 LI->changeLoopFor(BB, NewInner);
1219 }
1220
1221 // The preheader of the original outer loop becomes part of the new
1222 // outer loop.
1223 NewOuter->addBlockEntry(OrigOuterPreHeader);
1224 LI->changeLoopFor(OrigOuterPreHeader, NewOuter);
1225
1226 // Tell SE that we move the loops around.
1227 SE->forgetLoop(NewOuter);
1228 SE->forgetLoop(NewInner);
1229 }
1230
transform()1231 bool LoopInterchangeTransform::transform() {
1232 bool Transformed = false;
1233 Instruction *InnerIndexVar;
1234
1235 if (InnerLoop->getSubLoops().empty()) {
1236 BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
1237 LLVM_DEBUG(dbgs() << "Splitting the inner loop latch\n");
1238 PHINode *InductionPHI = getInductionVariable(InnerLoop, SE);
1239 if (!InductionPHI) {
1240 LLVM_DEBUG(dbgs() << "Failed to find the point to split loop latch \n");
1241 return false;
1242 }
1243
1244 if (InductionPHI->getIncomingBlock(0) == InnerLoopPreHeader)
1245 InnerIndexVar = dyn_cast<Instruction>(InductionPHI->getIncomingValue(1));
1246 else
1247 InnerIndexVar = dyn_cast<Instruction>(InductionPHI->getIncomingValue(0));
1248
1249 // Ensure that InductionPHI is the first Phi node.
1250 if (&InductionPHI->getParent()->front() != InductionPHI)
1251 InductionPHI->moveBefore(&InductionPHI->getParent()->front());
1252
1253 // Create a new latch block for the inner loop. We split at the
1254 // current latch's terminator and then move the condition and all
1255 // operands that are not either loop-invariant or the induction PHI into the
1256 // new latch block.
1257 BasicBlock *NewLatch =
1258 SplitBlock(InnerLoop->getLoopLatch(),
1259 InnerLoop->getLoopLatch()->getTerminator(), DT, LI);
1260
1261 SmallSetVector<Instruction *, 4> WorkList;
1262 unsigned i = 0;
1263 auto MoveInstructions = [&i, &WorkList, this, InductionPHI, NewLatch]() {
1264 for (; i < WorkList.size(); i++) {
1265 // Duplicate instruction and move it the new latch. Update uses that
1266 // have been moved.
1267 Instruction *NewI = WorkList[i]->clone();
1268 NewI->insertBefore(NewLatch->getFirstNonPHI());
1269 assert(!NewI->mayHaveSideEffects() &&
1270 "Moving instructions with side-effects may change behavior of "
1271 "the loop nest!");
1272 for (auto UI = WorkList[i]->use_begin(), UE = WorkList[i]->use_end();
1273 UI != UE;) {
1274 Use &U = *UI++;
1275 Instruction *UserI = cast<Instruction>(U.getUser());
1276 if (!InnerLoop->contains(UserI->getParent()) ||
1277 UserI->getParent() == NewLatch || UserI == InductionPHI)
1278 U.set(NewI);
1279 }
1280 // Add operands of moved instruction to the worklist, except if they are
1281 // outside the inner loop or are the induction PHI.
1282 for (Value *Op : WorkList[i]->operands()) {
1283 Instruction *OpI = dyn_cast<Instruction>(Op);
1284 if (!OpI ||
1285 this->LI->getLoopFor(OpI->getParent()) != this->InnerLoop ||
1286 OpI == InductionPHI)
1287 continue;
1288 WorkList.insert(OpI);
1289 }
1290 }
1291 };
1292
1293 // FIXME: Should we interchange when we have a constant condition?
1294 Instruction *CondI = dyn_cast<Instruction>(
1295 cast<BranchInst>(InnerLoop->getLoopLatch()->getTerminator())
1296 ->getCondition());
1297 if (CondI)
1298 WorkList.insert(CondI);
1299 MoveInstructions();
1300 WorkList.insert(cast<Instruction>(InnerIndexVar));
1301 MoveInstructions();
1302
1303 // Splits the inner loops phi nodes out into a separate basic block.
1304 BasicBlock *InnerLoopHeader = InnerLoop->getHeader();
1305 SplitBlock(InnerLoopHeader, InnerLoopHeader->getFirstNonPHI(), DT, LI);
1306 LLVM_DEBUG(dbgs() << "splitting InnerLoopHeader done\n");
1307 }
1308
1309 // Instructions in the original inner loop preheader may depend on values
1310 // defined in the outer loop header. Move them there, because the original
1311 // inner loop preheader will become the entry into the interchanged loop nest.
1312 // Currently we move all instructions and rely on LICM to move invariant
1313 // instructions outside the loop nest.
1314 BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
1315 BasicBlock *OuterLoopHeader = OuterLoop->getHeader();
1316 if (InnerLoopPreHeader != OuterLoopHeader) {
1317 SmallPtrSet<Instruction *, 4> NeedsMoving;
1318 for (Instruction &I :
1319 make_early_inc_range(make_range(InnerLoopPreHeader->begin(),
1320 std::prev(InnerLoopPreHeader->end()))))
1321 I.moveBefore(OuterLoopHeader->getTerminator());
1322 }
1323
1324 Transformed |= adjustLoopLinks();
1325 if (!Transformed) {
1326 LLVM_DEBUG(dbgs() << "adjustLoopLinks failed\n");
1327 return false;
1328 }
1329
1330 return true;
1331 }
1332
1333 /// \brief Move all instructions except the terminator from FromBB right before
1334 /// InsertBefore
moveBBContents(BasicBlock * FromBB,Instruction * InsertBefore)1335 static void moveBBContents(BasicBlock *FromBB, Instruction *InsertBefore) {
1336 auto &ToList = InsertBefore->getParent()->getInstList();
1337 auto &FromList = FromBB->getInstList();
1338
1339 ToList.splice(InsertBefore->getIterator(), FromList, FromList.begin(),
1340 FromBB->getTerminator()->getIterator());
1341 }
1342
1343 /// Swap instructions between \p BB1 and \p BB2 but keep terminators intact.
swapBBContents(BasicBlock * BB1,BasicBlock * BB2)1344 static void swapBBContents(BasicBlock *BB1, BasicBlock *BB2) {
1345 // Save all non-terminator instructions of BB1 into TempInstrs and unlink them
1346 // from BB1 afterwards.
1347 auto Iter = map_range(*BB1, [](Instruction &I) { return &I; });
1348 SmallVector<Instruction *, 4> TempInstrs(Iter.begin(), std::prev(Iter.end()));
1349 for (Instruction *I : TempInstrs)
1350 I->removeFromParent();
1351
1352 // Move instructions from BB2 to BB1.
1353 moveBBContents(BB2, BB1->getTerminator());
1354
1355 // Move instructions from TempInstrs to BB2.
1356 for (Instruction *I : TempInstrs)
1357 I->insertBefore(BB2->getTerminator());
1358 }
1359
1360 // Update BI to jump to NewBB instead of OldBB. Records updates to the
1361 // dominator tree in DTUpdates. If \p MustUpdateOnce is true, assert that
1362 // \p OldBB is exactly once in BI's successor list.
updateSuccessor(BranchInst * BI,BasicBlock * OldBB,BasicBlock * NewBB,std::vector<DominatorTree::UpdateType> & DTUpdates,bool MustUpdateOnce=true)1363 static void updateSuccessor(BranchInst *BI, BasicBlock *OldBB,
1364 BasicBlock *NewBB,
1365 std::vector<DominatorTree::UpdateType> &DTUpdates,
1366 bool MustUpdateOnce = true) {
1367 assert((!MustUpdateOnce ||
1368 llvm::count_if(successors(BI),
1369 [OldBB](BasicBlock *BB) {
1370 return BB == OldBB;
1371 }) == 1) && "BI must jump to OldBB exactly once.");
1372 bool Changed = false;
1373 for (Use &Op : BI->operands())
1374 if (Op == OldBB) {
1375 Op.set(NewBB);
1376 Changed = true;
1377 }
1378
1379 if (Changed) {
1380 DTUpdates.push_back(
1381 {DominatorTree::UpdateKind::Insert, BI->getParent(), NewBB});
1382 DTUpdates.push_back(
1383 {DominatorTree::UpdateKind::Delete, BI->getParent(), OldBB});
1384 }
1385 assert(Changed && "Expected a successor to be updated");
1386 }
1387
1388 // Move Lcssa PHIs to the right place.
moveLCSSAPhis(BasicBlock * InnerExit,BasicBlock * InnerHeader,BasicBlock * InnerLatch,BasicBlock * OuterHeader,BasicBlock * OuterLatch,BasicBlock * OuterExit,Loop * InnerLoop,LoopInfo * LI)1389 static void moveLCSSAPhis(BasicBlock *InnerExit, BasicBlock *InnerHeader,
1390 BasicBlock *InnerLatch, BasicBlock *OuterHeader,
1391 BasicBlock *OuterLatch, BasicBlock *OuterExit,
1392 Loop *InnerLoop, LoopInfo *LI) {
1393
1394 // Deal with LCSSA PHI nodes in the exit block of the inner loop, that are
1395 // defined either in the header or latch. Those blocks will become header and
1396 // latch of the new outer loop, and the only possible users can PHI nodes
1397 // in the exit block of the loop nest or the outer loop header (reduction
1398 // PHIs, in that case, the incoming value must be defined in the inner loop
1399 // header). We can just substitute the user with the incoming value and remove
1400 // the PHI.
1401 for (PHINode &P : make_early_inc_range(InnerExit->phis())) {
1402 assert(P.getNumIncomingValues() == 1 &&
1403 "Only loops with a single exit are supported!");
1404
1405 // Incoming values are guaranteed be instructions currently.
1406 auto IncI = cast<Instruction>(P.getIncomingValueForBlock(InnerLatch));
1407 // Skip phis with incoming values from the inner loop body, excluding the
1408 // header and latch.
1409 if (IncI->getParent() != InnerLatch && IncI->getParent() != InnerHeader)
1410 continue;
1411
1412 assert(all_of(P.users(),
1413 [OuterHeader, OuterExit, IncI, InnerHeader](User *U) {
1414 return (cast<PHINode>(U)->getParent() == OuterHeader &&
1415 IncI->getParent() == InnerHeader) ||
1416 cast<PHINode>(U)->getParent() == OuterExit;
1417 }) &&
1418 "Can only replace phis iff the uses are in the loop nest exit or "
1419 "the incoming value is defined in the inner header (it will "
1420 "dominate all loop blocks after interchanging)");
1421 P.replaceAllUsesWith(IncI);
1422 P.eraseFromParent();
1423 }
1424
1425 SmallVector<PHINode *, 8> LcssaInnerExit;
1426 for (PHINode &P : InnerExit->phis())
1427 LcssaInnerExit.push_back(&P);
1428
1429 SmallVector<PHINode *, 8> LcssaInnerLatch;
1430 for (PHINode &P : InnerLatch->phis())
1431 LcssaInnerLatch.push_back(&P);
1432
1433 // Lcssa PHIs for values used outside the inner loop are in InnerExit.
1434 // If a PHI node has users outside of InnerExit, it has a use outside the
1435 // interchanged loop and we have to preserve it. We move these to
1436 // InnerLatch, which will become the new exit block for the innermost
1437 // loop after interchanging.
1438 for (PHINode *P : LcssaInnerExit)
1439 P->moveBefore(InnerLatch->getFirstNonPHI());
1440
1441 // If the inner loop latch contains LCSSA PHIs, those come from a child loop
1442 // and we have to move them to the new inner latch.
1443 for (PHINode *P : LcssaInnerLatch)
1444 P->moveBefore(InnerExit->getFirstNonPHI());
1445
1446 // Deal with LCSSA PHI nodes in the loop nest exit block. For PHIs that have
1447 // incoming values defined in the outer loop, we have to add a new PHI
1448 // in the inner loop latch, which became the exit block of the outer loop,
1449 // after interchanging.
1450 if (OuterExit) {
1451 for (PHINode &P : OuterExit->phis()) {
1452 if (P.getNumIncomingValues() != 1)
1453 continue;
1454 // Skip Phis with incoming values defined in the inner loop. Those should
1455 // already have been updated.
1456 auto I = dyn_cast<Instruction>(P.getIncomingValue(0));
1457 if (!I || LI->getLoopFor(I->getParent()) == InnerLoop)
1458 continue;
1459
1460 PHINode *NewPhi = dyn_cast<PHINode>(P.clone());
1461 NewPhi->setIncomingValue(0, P.getIncomingValue(0));
1462 NewPhi->setIncomingBlock(0, OuterLatch);
1463 NewPhi->insertBefore(InnerLatch->getFirstNonPHI());
1464 P.setIncomingValue(0, NewPhi);
1465 }
1466 }
1467
1468 // Now adjust the incoming blocks for the LCSSA PHIs.
1469 // For PHIs moved from Inner's exit block, we need to replace Inner's latch
1470 // with the new latch.
1471 InnerLatch->replacePhiUsesWith(InnerLatch, OuterLatch);
1472 }
1473
adjustLoopBranches()1474 bool LoopInterchangeTransform::adjustLoopBranches() {
1475 LLVM_DEBUG(dbgs() << "adjustLoopBranches called\n");
1476 std::vector<DominatorTree::UpdateType> DTUpdates;
1477
1478 BasicBlock *OuterLoopPreHeader = OuterLoop->getLoopPreheader();
1479 BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
1480
1481 assert(OuterLoopPreHeader != OuterLoop->getHeader() &&
1482 InnerLoopPreHeader != InnerLoop->getHeader() && OuterLoopPreHeader &&
1483 InnerLoopPreHeader && "Guaranteed by loop-simplify form");
1484 // Ensure that both preheaders do not contain PHI nodes and have single
1485 // predecessors. This allows us to move them easily. We use
1486 // InsertPreHeaderForLoop to create an 'extra' preheader, if the existing
1487 // preheaders do not satisfy those conditions.
1488 if (isa<PHINode>(OuterLoopPreHeader->begin()) ||
1489 !OuterLoopPreHeader->getUniquePredecessor())
1490 OuterLoopPreHeader =
1491 InsertPreheaderForLoop(OuterLoop, DT, LI, nullptr, true);
1492 if (InnerLoopPreHeader == OuterLoop->getHeader())
1493 InnerLoopPreHeader =
1494 InsertPreheaderForLoop(InnerLoop, DT, LI, nullptr, true);
1495
1496 // Adjust the loop preheader
1497 BasicBlock *InnerLoopHeader = InnerLoop->getHeader();
1498 BasicBlock *OuterLoopHeader = OuterLoop->getHeader();
1499 BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch();
1500 BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch();
1501 BasicBlock *OuterLoopPredecessor = OuterLoopPreHeader->getUniquePredecessor();
1502 BasicBlock *InnerLoopLatchPredecessor =
1503 InnerLoopLatch->getUniquePredecessor();
1504 BasicBlock *InnerLoopLatchSuccessor;
1505 BasicBlock *OuterLoopLatchSuccessor;
1506
1507 BranchInst *OuterLoopLatchBI =
1508 dyn_cast<BranchInst>(OuterLoopLatch->getTerminator());
1509 BranchInst *InnerLoopLatchBI =
1510 dyn_cast<BranchInst>(InnerLoopLatch->getTerminator());
1511 BranchInst *OuterLoopHeaderBI =
1512 dyn_cast<BranchInst>(OuterLoopHeader->getTerminator());
1513 BranchInst *InnerLoopHeaderBI =
1514 dyn_cast<BranchInst>(InnerLoopHeader->getTerminator());
1515
1516 if (!OuterLoopPredecessor || !InnerLoopLatchPredecessor ||
1517 !OuterLoopLatchBI || !InnerLoopLatchBI || !OuterLoopHeaderBI ||
1518 !InnerLoopHeaderBI)
1519 return false;
1520
1521 BranchInst *InnerLoopLatchPredecessorBI =
1522 dyn_cast<BranchInst>(InnerLoopLatchPredecessor->getTerminator());
1523 BranchInst *OuterLoopPredecessorBI =
1524 dyn_cast<BranchInst>(OuterLoopPredecessor->getTerminator());
1525
1526 if (!OuterLoopPredecessorBI || !InnerLoopLatchPredecessorBI)
1527 return false;
1528 BasicBlock *InnerLoopHeaderSuccessor = InnerLoopHeader->getUniqueSuccessor();
1529 if (!InnerLoopHeaderSuccessor)
1530 return false;
1531
1532 // Adjust Loop Preheader and headers.
1533 // The branches in the outer loop predecessor and the outer loop header can
1534 // be unconditional branches or conditional branches with duplicates. Consider
1535 // this when updating the successors.
1536 updateSuccessor(OuterLoopPredecessorBI, OuterLoopPreHeader,
1537 InnerLoopPreHeader, DTUpdates, /*MustUpdateOnce=*/false);
1538 // The outer loop header might or might not branch to the outer latch.
1539 // We are guaranteed to branch to the inner loop preheader.
1540 if (llvm::is_contained(OuterLoopHeaderBI->successors(), OuterLoopLatch))
1541 updateSuccessor(OuterLoopHeaderBI, OuterLoopLatch, LoopExit, DTUpdates,
1542 /*MustUpdateOnce=*/false);
1543 updateSuccessor(OuterLoopHeaderBI, InnerLoopPreHeader,
1544 InnerLoopHeaderSuccessor, DTUpdates,
1545 /*MustUpdateOnce=*/false);
1546
1547 // Adjust reduction PHI's now that the incoming block has changed.
1548 InnerLoopHeaderSuccessor->replacePhiUsesWith(InnerLoopHeader,
1549 OuterLoopHeader);
1550
1551 updateSuccessor(InnerLoopHeaderBI, InnerLoopHeaderSuccessor,
1552 OuterLoopPreHeader, DTUpdates);
1553
1554 // -------------Adjust loop latches-----------
1555 if (InnerLoopLatchBI->getSuccessor(0) == InnerLoopHeader)
1556 InnerLoopLatchSuccessor = InnerLoopLatchBI->getSuccessor(1);
1557 else
1558 InnerLoopLatchSuccessor = InnerLoopLatchBI->getSuccessor(0);
1559
1560 updateSuccessor(InnerLoopLatchPredecessorBI, InnerLoopLatch,
1561 InnerLoopLatchSuccessor, DTUpdates);
1562
1563
1564 if (OuterLoopLatchBI->getSuccessor(0) == OuterLoopHeader)
1565 OuterLoopLatchSuccessor = OuterLoopLatchBI->getSuccessor(1);
1566 else
1567 OuterLoopLatchSuccessor = OuterLoopLatchBI->getSuccessor(0);
1568
1569 updateSuccessor(InnerLoopLatchBI, InnerLoopLatchSuccessor,
1570 OuterLoopLatchSuccessor, DTUpdates);
1571 updateSuccessor(OuterLoopLatchBI, OuterLoopLatchSuccessor, InnerLoopLatch,
1572 DTUpdates);
1573
1574 DT->applyUpdates(DTUpdates);
1575 restructureLoops(OuterLoop, InnerLoop, InnerLoopPreHeader,
1576 OuterLoopPreHeader);
1577
1578 moveLCSSAPhis(InnerLoopLatchSuccessor, InnerLoopHeader, InnerLoopLatch,
1579 OuterLoopHeader, OuterLoopLatch, InnerLoop->getExitBlock(),
1580 InnerLoop, LI);
1581 // For PHIs in the exit block of the outer loop, outer's latch has been
1582 // replaced by Inners'.
1583 OuterLoopLatchSuccessor->replacePhiUsesWith(OuterLoopLatch, InnerLoopLatch);
1584
1585 // Now update the reduction PHIs in the inner and outer loop headers.
1586 SmallVector<PHINode *, 4> InnerLoopPHIs, OuterLoopPHIs;
1587 for (PHINode &PHI : drop_begin(InnerLoopHeader->phis()))
1588 InnerLoopPHIs.push_back(cast<PHINode>(&PHI));
1589 for (PHINode &PHI : drop_begin(OuterLoopHeader->phis()))
1590 OuterLoopPHIs.push_back(cast<PHINode>(&PHI));
1591
1592 auto &OuterInnerReductions = LIL.getOuterInnerReductions();
1593 (void)OuterInnerReductions;
1594
1595 // Now move the remaining reduction PHIs from outer to inner loop header and
1596 // vice versa. The PHI nodes must be part of a reduction across the inner and
1597 // outer loop and all the remains to do is and updating the incoming blocks.
1598 for (PHINode *PHI : OuterLoopPHIs) {
1599 PHI->moveBefore(InnerLoopHeader->getFirstNonPHI());
1600 assert(OuterInnerReductions.count(PHI) && "Expected a reduction PHI node");
1601 }
1602 for (PHINode *PHI : InnerLoopPHIs) {
1603 PHI->moveBefore(OuterLoopHeader->getFirstNonPHI());
1604 assert(OuterInnerReductions.count(PHI) && "Expected a reduction PHI node");
1605 }
1606
1607 // Update the incoming blocks for moved PHI nodes.
1608 OuterLoopHeader->replacePhiUsesWith(InnerLoopPreHeader, OuterLoopPreHeader);
1609 OuterLoopHeader->replacePhiUsesWith(InnerLoopLatch, OuterLoopLatch);
1610 InnerLoopHeader->replacePhiUsesWith(OuterLoopPreHeader, InnerLoopPreHeader);
1611 InnerLoopHeader->replacePhiUsesWith(OuterLoopLatch, InnerLoopLatch);
1612
1613 // Values defined in the outer loop header could be used in the inner loop
1614 // latch. In that case, we need to create LCSSA phis for them, because after
1615 // interchanging they will be defined in the new inner loop and used in the
1616 // new outer loop.
1617 IRBuilder<> Builder(OuterLoopHeader->getContext());
1618 SmallVector<Instruction *, 4> MayNeedLCSSAPhis;
1619 for (Instruction &I :
1620 make_range(OuterLoopHeader->begin(), std::prev(OuterLoopHeader->end())))
1621 MayNeedLCSSAPhis.push_back(&I);
1622 formLCSSAForInstructions(MayNeedLCSSAPhis, *DT, *LI, SE, Builder);
1623
1624 return true;
1625 }
1626
adjustLoopLinks()1627 bool LoopInterchangeTransform::adjustLoopLinks() {
1628 // Adjust all branches in the inner and outer loop.
1629 bool Changed = adjustLoopBranches();
1630 if (Changed) {
1631 // We have interchanged the preheaders so we need to interchange the data in
1632 // the preheaders as well. This is because the content of the inner
1633 // preheader was previously executed inside the outer loop.
1634 BasicBlock *OuterLoopPreHeader = OuterLoop->getLoopPreheader();
1635 BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
1636 swapBBContents(OuterLoopPreHeader, InnerLoopPreHeader);
1637 }
1638 return Changed;
1639 }
1640
1641 /// Main LoopInterchange Pass.
1642 struct LoopInterchangeLegacyPass : public LoopPass {
1643 static char ID;
1644
LoopInterchangeLegacyPassLoopInterchangeLegacyPass1645 LoopInterchangeLegacyPass() : LoopPass(ID) {
1646 initializeLoopInterchangeLegacyPassPass(*PassRegistry::getPassRegistry());
1647 }
1648
getAnalysisUsageLoopInterchangeLegacyPass1649 void getAnalysisUsage(AnalysisUsage &AU) const override {
1650 AU.addRequired<DependenceAnalysisWrapperPass>();
1651 AU.addRequired<OptimizationRemarkEmitterWrapperPass>();
1652
1653 getLoopAnalysisUsage(AU);
1654 }
1655
runOnLoopLoopInterchangeLegacyPass1656 bool runOnLoop(Loop *L, LPPassManager &LPM) override {
1657 if (skipLoop(L))
1658 return false;
1659
1660 auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
1661 auto *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
1662 auto *DI = &getAnalysis<DependenceAnalysisWrapperPass>().getDI();
1663 auto *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1664 auto *ORE = &getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE();
1665
1666 return LoopInterchange(SE, LI, DI, DT, ORE).run(L);
1667 }
1668 };
1669
1670 char LoopInterchangeLegacyPass::ID = 0;
1671
1672 INITIALIZE_PASS_BEGIN(LoopInterchangeLegacyPass, "loop-interchange",
1673 "Interchanges loops for cache reuse", false, false)
INITIALIZE_PASS_DEPENDENCY(LoopPass)1674 INITIALIZE_PASS_DEPENDENCY(LoopPass)
1675 INITIALIZE_PASS_DEPENDENCY(DependenceAnalysisWrapperPass)
1676 INITIALIZE_PASS_DEPENDENCY(OptimizationRemarkEmitterWrapperPass)
1677
1678 INITIALIZE_PASS_END(LoopInterchangeLegacyPass, "loop-interchange",
1679 "Interchanges loops for cache reuse", false, false)
1680
1681 Pass *llvm::createLoopInterchangePass() {
1682 return new LoopInterchangeLegacyPass();
1683 }
1684
run(Loop & L,LoopAnalysisManager & AM,LoopStandardAnalysisResults & AR,LPMUpdater & U)1685 PreservedAnalyses LoopInterchangePass::run(Loop &L, LoopAnalysisManager &AM,
1686 LoopStandardAnalysisResults &AR,
1687 LPMUpdater &U) {
1688 Function &F = *L.getHeader()->getParent();
1689
1690 DependenceInfo DI(&F, &AR.AA, &AR.SE, &AR.LI);
1691 OptimizationRemarkEmitter ORE(&F);
1692 if (!LoopInterchange(&AR.SE, &AR.LI, &DI, &AR.DT, &ORE).run(&L))
1693 return PreservedAnalyses::all();
1694 return getLoopPassPreservedAnalyses();
1695 }
1696