LLVM  10.0.0svn
LoopInterchange.cpp
Go to the documentation of this file.
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/ADT/STLExtras.h"
16 #include "llvm/ADT/SmallVector.h"
17 #include "llvm/ADT/Statistic.h"
18 #include "llvm/ADT/StringRef.h"
20 #include "llvm/Analysis/LoopInfo.h"
21 #include "llvm/Analysis/LoopPass.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"
39 #include "llvm/Support/Debug.h"
42 #include "llvm/Transforms/Scalar.h"
43 #include "llvm/Transforms/Utils.h"
46 #include <cassert>
47 #include <utility>
48 #include <vector>
49 
50 using namespace llvm;
51 
52 #define DEBUG_TYPE "loop-interchange"
53 
54 STATISTIC(LoopsInterchanged, "Number of loops interchanged");
55 
57  "loop-interchange-threshold", cl::init(0), cl::Hidden,
58  cl::desc("Interchange if you gain more than this number"));
59 
60 namespace {
61 
62 using LoopVector = SmallVector<Loop *, 8>;
63 
64 // TODO: Check if we can use a sparse matrix here.
65 using CharMatrix = std::vector<std::vector<char>>;
66 
67 } // end anonymous namespace
68 
69 // Maximum number of dependencies that can be handled in the dependency matrix.
70 static const unsigned MaxMemInstrCount = 100;
71 
72 // Maximum loop depth supported.
73 static const unsigned MaxLoopNestDepth = 10;
74 
75 #ifdef DUMP_DEP_MATRICIES
76 static void printDepMatrix(CharMatrix &DepMatrix) {
77  for (auto &Row : DepMatrix) {
78  for (auto D : Row)
79  LLVM_DEBUG(dbgs() << D << " ");
80  LLVM_DEBUG(dbgs() << "\n");
81  }
82 }
83 #endif
84 
85 static bool populateDependencyMatrix(CharMatrix &DepMatrix, unsigned Level,
86  Loop *L, DependenceInfo *DI) {
87  using ValueVector = SmallVector<Value *, 16>;
88 
89  ValueVector MemInstr;
90 
91  // For each block.
92  for (BasicBlock *BB : L->blocks()) {
93  // Scan the BB and collect legal loads and stores.
94  for (Instruction &I : *BB) {
95  if (!isa<Instruction>(I))
96  return false;
97  if (auto *Ld = dyn_cast<LoadInst>(&I)) {
98  if (!Ld->isSimple())
99  return false;
100  MemInstr.push_back(&I);
101  } else if (auto *St = dyn_cast<StoreInst>(&I)) {
102  if (!St->isSimple())
103  return false;
104  MemInstr.push_back(&I);
105  }
106  }
107  }
108 
109  LLVM_DEBUG(dbgs() << "Found " << MemInstr.size()
110  << " Loads and Stores to analyze\n");
111 
112  ValueVector::iterator I, IE, J, JE;
113 
114  for (I = MemInstr.begin(), IE = MemInstr.end(); I != IE; ++I) {
115  for (J = I, JE = MemInstr.end(); J != JE; ++J) {
116  std::vector<char> Dep;
117  Instruction *Src = cast<Instruction>(*I);
118  Instruction *Dst = cast<Instruction>(*J);
119  if (Src == Dst)
120  continue;
121  // Ignore Input dependencies.
122  if (isa<LoadInst>(Src) && isa<LoadInst>(Dst))
123  continue;
124  // Track Output, Flow, and Anti dependencies.
125  if (auto D = DI->depends(Src, Dst, true)) {
126  assert(D->isOrdered() && "Expected an output, flow or anti dep.");
127  LLVM_DEBUG(StringRef DepType =
128  D->isFlow() ? "flow" : D->isAnti() ? "anti" : "output";
129  dbgs() << "Found " << DepType
130  << " dependency between Src and Dst\n"
131  << " Src:" << *Src << "\n Dst:" << *Dst << '\n');
132  unsigned Levels = D->getLevels();
133  char Direction;
134  for (unsigned II = 1; II <= Levels; ++II) {
135  const SCEV *Distance = D->getDistance(II);
136  const SCEVConstant *SCEVConst =
137  dyn_cast_or_null<SCEVConstant>(Distance);
138  if (SCEVConst) {
139  const ConstantInt *CI = SCEVConst->getValue();
140  if (CI->isNegative())
141  Direction = '<';
142  else if (CI->isZero())
143  Direction = '=';
144  else
145  Direction = '>';
146  Dep.push_back(Direction);
147  } else if (D->isScalar(II)) {
148  Direction = 'S';
149  Dep.push_back(Direction);
150  } else {
151  unsigned Dir = D->getDirection(II);
152  if (Dir == Dependence::DVEntry::LT ||
154  Direction = '<';
155  else if (Dir == Dependence::DVEntry::GT ||
157  Direction = '>';
158  else if (Dir == Dependence::DVEntry::EQ)
159  Direction = '=';
160  else
161  Direction = '*';
162  Dep.push_back(Direction);
163  }
164  }
165  while (Dep.size() != Level) {
166  Dep.push_back('I');
167  }
168 
169  DepMatrix.push_back(Dep);
170  if (DepMatrix.size() > MaxMemInstrCount) {
171  LLVM_DEBUG(dbgs() << "Cannot handle more than " << MaxMemInstrCount
172  << " dependencies inside loop\n");
173  return false;
174  }
175  }
176  }
177  }
178 
179  return true;
180 }
181 
182 // A loop is moved from index 'from' to an index 'to'. Update the Dependence
183 // matrix by exchanging the two columns.
184 static void interChangeDependencies(CharMatrix &DepMatrix, unsigned FromIndx,
185  unsigned ToIndx) {
186  unsigned numRows = DepMatrix.size();
187  for (unsigned i = 0; i < numRows; ++i) {
188  char TmpVal = DepMatrix[i][ToIndx];
189  DepMatrix[i][ToIndx] = DepMatrix[i][FromIndx];
190  DepMatrix[i][FromIndx] = TmpVal;
191  }
192 }
193 
194 // Checks if outermost non '=','S'or'I' dependence in the dependence matrix is
195 // '>'
196 static bool isOuterMostDepPositive(CharMatrix &DepMatrix, unsigned Row,
197  unsigned Column) {
198  for (unsigned i = 0; i <= Column; ++i) {
199  if (DepMatrix[Row][i] == '<')
200  return false;
201  if (DepMatrix[Row][i] == '>')
202  return true;
203  }
204  // All dependencies were '=','S' or 'I'
205  return false;
206 }
207 
208 // Checks if no dependence exist in the dependency matrix in Row before Column.
209 static bool containsNoDependence(CharMatrix &DepMatrix, unsigned Row,
210  unsigned Column) {
211  for (unsigned i = 0; i < Column; ++i) {
212  if (DepMatrix[Row][i] != '=' && DepMatrix[Row][i] != 'S' &&
213  DepMatrix[Row][i] != 'I')
214  return false;
215  }
216  return true;
217 }
218 
219 static bool validDepInterchange(CharMatrix &DepMatrix, unsigned Row,
220  unsigned OuterLoopId, char InnerDep,
221  char OuterDep) {
222  if (isOuterMostDepPositive(DepMatrix, Row, OuterLoopId))
223  return false;
224 
225  if (InnerDep == OuterDep)
226  return true;
227 
228  // It is legal to interchange if and only if after interchange no row has a
229  // '>' direction as the leftmost non-'='.
230 
231  if (InnerDep == '=' || InnerDep == 'S' || InnerDep == 'I')
232  return true;
233 
234  if (InnerDep == '<')
235  return true;
236 
237  if (InnerDep == '>') {
238  // If OuterLoopId represents outermost loop then interchanging will make the
239  // 1st dependency as '>'
240  if (OuterLoopId == 0)
241  return false;
242 
243  // If all dependencies before OuterloopId are '=','S'or 'I'. Then
244  // interchanging will result in this row having an outermost non '='
245  // dependency of '>'
246  if (!containsNoDependence(DepMatrix, Row, OuterLoopId))
247  return true;
248  }
249 
250  return false;
251 }
252 
253 // Checks if it is legal to interchange 2 loops.
254 // [Theorem] A permutation of the loops in a perfect nest is legal if and only
255 // if the direction matrix, after the same permutation is applied to its
256 // columns, has no ">" direction as the leftmost non-"=" direction in any row.
257 static bool isLegalToInterChangeLoops(CharMatrix &DepMatrix,
258  unsigned InnerLoopId,
259  unsigned OuterLoopId) {
260  unsigned NumRows = DepMatrix.size();
261  // For each row check if it is valid to interchange.
262  for (unsigned Row = 0; Row < NumRows; ++Row) {
263  char InnerDep = DepMatrix[Row][InnerLoopId];
264  char OuterDep = DepMatrix[Row][OuterLoopId];
265  if (InnerDep == '*' || OuterDep == '*')
266  return false;
267  if (!validDepInterchange(DepMatrix, Row, OuterLoopId, InnerDep, OuterDep))
268  return false;
269  }
270  return true;
271 }
272 
273 static LoopVector populateWorklist(Loop &L) {
274  LLVM_DEBUG(dbgs() << "Calling populateWorklist on Func: "
275  << L.getHeader()->getParent()->getName() << " Loop: %"
276  << L.getHeader()->getName() << '\n');
277  LoopVector LoopList;
278  Loop *CurrentLoop = &L;
279  const std::vector<Loop *> *Vec = &CurrentLoop->getSubLoops();
280  while (!Vec->empty()) {
281  // The current loop has multiple subloops in it hence it is not tightly
282  // nested.
283  // Discard all loops above it added into Worklist.
284  if (Vec->size() != 1)
285  return {};
286 
287  LoopList.push_back(CurrentLoop);
288  CurrentLoop = Vec->front();
289  Vec = &CurrentLoop->getSubLoops();
290  }
291  LoopList.push_back(CurrentLoop);
292  return LoopList;
293 }
294 
296  PHINode *InnerIndexVar = L->getCanonicalInductionVariable();
297  if (InnerIndexVar)
298  return InnerIndexVar;
299  if (L->getLoopLatch() == nullptr || L->getLoopPredecessor() == nullptr)
300  return nullptr;
301  for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) {
302  PHINode *PhiVar = cast<PHINode>(I);
303  Type *PhiTy = PhiVar->getType();
304  if (!PhiTy->isIntegerTy() && !PhiTy->isFloatingPointTy() &&
305  !PhiTy->isPointerTy())
306  return nullptr;
307  const SCEVAddRecExpr *AddRec =
308  dyn_cast<SCEVAddRecExpr>(SE->getSCEV(PhiVar));
309  if (!AddRec || !AddRec->isAffine())
310  continue;
311  const SCEV *Step = AddRec->getStepRecurrence(*SE);
312  if (!isa<SCEVConstant>(Step))
313  continue;
314  // Found the induction variable.
315  // FIXME: Handle loops with more than one induction variable. Note that,
316  // currently, legality makes sure we have only one induction variable.
317  return PhiVar;
318  }
319  return nullptr;
320 }
321 
322 namespace {
323 
324 /// LoopInterchangeLegality checks if it is legal to interchange the loop.
325 class LoopInterchangeLegality {
326 public:
327  LoopInterchangeLegality(Loop *Outer, Loop *Inner, ScalarEvolution *SE,
329  : OuterLoop(Outer), InnerLoop(Inner), SE(SE), ORE(ORE) {}
330 
331  /// Check if the loops can be interchanged.
332  bool canInterchangeLoops(unsigned InnerLoopId, unsigned OuterLoopId,
333  CharMatrix &DepMatrix);
334 
335  /// Check if the loop structure is understood. We do not handle triangular
336  /// loops for now.
337  bool isLoopStructureUnderstood(PHINode *InnerInductionVar);
338 
339  bool currentLimitations();
340 
341  const SmallPtrSetImpl<PHINode *> &getOuterInnerReductions() const {
342  return OuterInnerReductions;
343  }
344 
345 private:
346  bool tightlyNested(Loop *Outer, Loop *Inner);
347  bool containsUnsafeInstructions(BasicBlock *BB);
348 
349  /// Discover induction and reduction PHIs in the header of \p L. Induction
350  /// PHIs are added to \p Inductions, reductions are added to
351  /// OuterInnerReductions. When the outer loop is passed, the inner loop needs
352  /// to be passed as \p InnerLoop.
353  bool findInductionAndReductions(Loop *L,
354  SmallVector<PHINode *, 8> &Inductions,
355  Loop *InnerLoop);
356 
357  Loop *OuterLoop;
358  Loop *InnerLoop;
359 
360  ScalarEvolution *SE;
361 
362  /// Interface to emit optimization remarks.
364 
365  /// Set of reduction PHIs taking part of a reduction across the inner and
366  /// outer loop.
367  SmallPtrSet<PHINode *, 4> OuterInnerReductions;
368 };
369 
370 /// LoopInterchangeProfitability checks if it is profitable to interchange the
371 /// loop.
372 class LoopInterchangeProfitability {
373 public:
374  LoopInterchangeProfitability(Loop *Outer, Loop *Inner, ScalarEvolution *SE,
376  : OuterLoop(Outer), InnerLoop(Inner), SE(SE), ORE(ORE) {}
377 
378  /// Check if the loop interchange is profitable.
379  bool isProfitable(unsigned InnerLoopId, unsigned OuterLoopId,
380  CharMatrix &DepMatrix);
381 
382 private:
383  int getInstrOrderCost();
384 
385  Loop *OuterLoop;
386  Loop *InnerLoop;
387 
388  /// Scev analysis.
389  ScalarEvolution *SE;
390 
391  /// Interface to emit optimization remarks.
393 };
394 
395 /// LoopInterchangeTransform interchanges the loop.
396 class LoopInterchangeTransform {
397 public:
398  LoopInterchangeTransform(Loop *Outer, Loop *Inner, ScalarEvolution *SE,
399  LoopInfo *LI, DominatorTree *DT,
400  BasicBlock *LoopNestExit,
401  const LoopInterchangeLegality &LIL)
402  : OuterLoop(Outer), InnerLoop(Inner), SE(SE), LI(LI), DT(DT),
403  LoopExit(LoopNestExit), LIL(LIL) {}
404 
405  /// Interchange OuterLoop and InnerLoop.
406  bool transform();
407  void restructureLoops(Loop *NewInner, Loop *NewOuter,
408  BasicBlock *OrigInnerPreHeader,
409  BasicBlock *OrigOuterPreHeader);
410  void removeChildLoop(Loop *OuterLoop, Loop *InnerLoop);
411 
412 private:
413  bool adjustLoopLinks();
414  void adjustLoopPreheaders();
415  bool adjustLoopBranches();
416 
417  Loop *OuterLoop;
418  Loop *InnerLoop;
419 
420  /// Scev analysis.
421  ScalarEvolution *SE;
422 
423  LoopInfo *LI;
424  DominatorTree *DT;
425  BasicBlock *LoopExit;
426 
427  const LoopInterchangeLegality &LIL;
428 };
429 
430 // Main LoopInterchange Pass.
431 struct LoopInterchange : public LoopPass {
432  static char ID;
433  ScalarEvolution *SE = nullptr;
434  LoopInfo *LI = nullptr;
435  DependenceInfo *DI = nullptr;
436  DominatorTree *DT = nullptr;
437 
438  /// Interface to emit optimization remarks.
440 
441  LoopInterchange() : LoopPass(ID) {
443  }
444 
445  void getAnalysisUsage(AnalysisUsage &AU) const override {
448 
450  }
451 
452  bool runOnLoop(Loop *L, LPPassManager &LPM) override {
453  if (skipLoop(L) || L->getParentLoop())
454  return false;
455 
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();
461 
462  return processLoopList(populateWorklist(*L));
463  }
464 
465  bool isComputableLoopNest(LoopVector LoopList) {
466  for (Loop *L : LoopList) {
467  const SCEV *ExitCountOuter = SE->getBackedgeTakenCount(L);
468  if (ExitCountOuter == SE->getCouldNotCompute()) {
469  LLVM_DEBUG(dbgs() << "Couldn't compute backedge count\n");
470  return false;
471  }
472  if (L->getNumBackEdges() != 1) {
473  LLVM_DEBUG(dbgs() << "NumBackEdges is not equal to 1\n");
474  return false;
475  }
476  if (!L->getExitingBlock()) {
477  LLVM_DEBUG(dbgs() << "Loop doesn't have unique exit block\n");
478  return false;
479  }
480  }
481  return true;
482  }
483 
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;
488  }
489 
490  bool processLoopList(LoopVector LoopList) {
491  bool Changed = false;
492  unsigned LoopNestDepth = LoopList.size();
493  if (LoopNestDepth < 2) {
494  LLVM_DEBUG(dbgs() << "Loop doesn't contain minimum nesting level.\n");
495  return false;
496  }
497  if (LoopNestDepth > MaxLoopNestDepth) {
498  LLVM_DEBUG(dbgs() << "Cannot handle loops of depth greater than "
499  << MaxLoopNestDepth << "\n");
500  return false;
501  }
502  if (!isComputableLoopNest(LoopList)) {
503  LLVM_DEBUG(dbgs() << "Not valid loop candidate for interchange\n");
504  return false;
505  }
506 
507  LLVM_DEBUG(dbgs() << "Processing LoopList of size = " << LoopNestDepth
508  << "\n");
509 
510  CharMatrix DependencyMatrix;
511  Loop *OuterMostLoop = *(LoopList.begin());
512  if (!populateDependencyMatrix(DependencyMatrix, LoopNestDepth,
513  OuterMostLoop, DI)) {
514  LLVM_DEBUG(dbgs() << "Populating dependency matrix failed\n");
515  return false;
516  }
517 #ifdef DUMP_DEP_MATRICIES
518  LLVM_DEBUG(dbgs() << "Dependence before interchange\n");
519  printDepMatrix(DependencyMatrix);
520 #endif
521 
522  // Get the Outermost loop exit.
523  BasicBlock *LoopNestExit = OuterMostLoop->getExitBlock();
524  if (!LoopNestExit) {
525  LLVM_DEBUG(dbgs() << "OuterMostLoop needs an unique exit block");
526  return false;
527  }
528 
529  unsigned SelecLoopId = selectLoopForInterchange(LoopList);
530  // Move the selected loop outwards to the best possible position.
531  for (unsigned i = SelecLoopId; i > 0; i--) {
532  bool Interchanged =
533  processLoop(LoopList, i, i - 1, LoopNestExit, DependencyMatrix);
534  if (!Interchanged)
535  return Changed;
536  // Loops interchanged reflect the same in LoopList
537  std::swap(LoopList[i - 1], LoopList[i]);
538 
539  // Update the DependencyMatrix
540  interChangeDependencies(DependencyMatrix, i, i - 1);
541 #ifdef DUMP_DEP_MATRICIES
542  LLVM_DEBUG(dbgs() << "Dependence after interchange\n");
543  printDepMatrix(DependencyMatrix);
544 #endif
545  Changed |= Interchanged;
546  }
547  return Changed;
548  }
549 
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];
557 
558  LoopInterchangeLegality LIL(OuterLoop, InnerLoop, SE, ORE);
559  if (!LIL.canInterchangeLoops(InnerLoopId, OuterLoopId, DependencyMatrix)) {
560  LLVM_DEBUG(dbgs() << "Not interchanging loops. Cannot prove legality.\n");
561  return false;
562  }
563  LLVM_DEBUG(dbgs() << "Loops are legal to interchange\n");
564  LoopInterchangeProfitability LIP(OuterLoop, InnerLoop, SE, ORE);
565  if (!LIP.isProfitable(InnerLoopId, OuterLoopId, DependencyMatrix)) {
566  LLVM_DEBUG(dbgs() << "Interchanging loops not profitable.\n");
567  return false;
568  }
569 
570  ORE->emit([&]() {
571  return OptimizationRemark(DEBUG_TYPE, "Interchanged",
572  InnerLoop->getStartLoc(),
573  InnerLoop->getHeader())
574  << "Loop interchanged with enclosing loop.";
575  });
576 
577  LoopInterchangeTransform LIT(OuterLoop, InnerLoop, SE, LI, DT, LoopNestExit,
578  LIL);
579  LIT.transform();
580  LLVM_DEBUG(dbgs() << "Loops interchanged.\n");
581  LoopsInterchanged++;
582  return true;
583  }
584 };
585 
586 } // end anonymous namespace
587 
588 bool LoopInterchangeLegality::containsUnsafeInstructions(BasicBlock *BB) {
589  return any_of(*BB, [](const Instruction &I) {
590  return I.mayHaveSideEffects() || I.mayReadFromMemory();
591  });
592 }
593 
594 bool LoopInterchangeLegality::tightlyNested(Loop *OuterLoop, Loop *InnerLoop) {
595  BasicBlock *OuterLoopHeader = OuterLoop->getHeader();
596  BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
597  BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch();
598 
599  LLVM_DEBUG(dbgs() << "Checking if loops are tightly nested\n");
600 
601  // A perfectly nested loop will not have any branch in between the outer and
602  // inner block i.e. outer header will branch to either inner preheader and
603  // outerloop latch.
604  BranchInst *OuterLoopHeaderBI =
605  dyn_cast<BranchInst>(OuterLoopHeader->getTerminator());
606  if (!OuterLoopHeaderBI)
607  return false;
608 
609  for (BasicBlock *Succ : successors(OuterLoopHeaderBI))
610  if (Succ != InnerLoopPreHeader && Succ != InnerLoop->getHeader() &&
611  Succ != OuterLoopLatch)
612  return false;
613 
614  LLVM_DEBUG(dbgs() << "Checking instructions in Loop header and Loop latch\n");
615  // We do not have any basic block in between now make sure the outer header
616  // and outer loop latch doesn't contain any unsafe instructions.
617  if (containsUnsafeInstructions(OuterLoopHeader) ||
618  containsUnsafeInstructions(OuterLoopLatch))
619  return false;
620 
621  LLVM_DEBUG(dbgs() << "Loops are perfectly nested\n");
622  // We have a perfect loop nest.
623  return true;
624 }
625 
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;
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.
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.
664  for (Value *User : V->users()) {
665  if (PHINode *PHI = dyn_cast<PHINode>(User)) {
666  if (PHI->getNumIncomingValues() == 1)
667  continue;
669  if (RecurrenceDescriptor::isReductionPHI(PHI, L, RD))
670  return PHI;
671  return nullptr;
672  }
673  }
674 
675  return nullptr;
676 }
677 
678 bool LoopInterchangeLegality::findInductionAndReductions(
679  Loop *L, SmallVector<PHINode *, 8> &Inductions, Loop *InnerLoop) {
680  if (!L->getLoopLatch() || !L->getLoopPredecessor())
681  return false;
682  for (PHINode &PHI : L->getHeader()->phis()) {
685  if (InductionDescriptor::isInductionPHI(&PHI, L, SE, ID))
686  Inductions.push_back(&PHI);
687  else {
688  // PHIs in inner loops need to be part of a reduction in the outer loop,
689  // discovered when checking the PHIs of the outer loop earlier.
690  if (!InnerLoop) {
691  if (OuterInnerReductions.find(&PHI) == OuterInnerReductions.end()) {
692  LLVM_DEBUG(dbgs() << "Inner loop PHI is not part of reductions "
693  "across the outer loop.\n");
694  return false;
695  }
696  } else {
697  assert(PHI.getNumIncomingValues() == 2 &&
698  "Phis in loop header should have exactly 2 incoming values");
699  // Check if we have a PHI node in the outer loop that has a reduction
700  // result from the inner loop as an incoming value.
701  Value *V = followLCSSA(PHI.getIncomingValueForBlock(L->getLoopLatch()));
702  PHINode *InnerRedPhi = findInnerReductionPhi(InnerLoop, V);
703  if (!InnerRedPhi ||
704  !llvm::any_of(InnerRedPhi->incoming_values(),
705  [&PHI](Value *V) { return V == &PHI; })) {
706  LLVM_DEBUG(
707  dbgs()
708  << "Failed to recognize PHI as an induction or reduction.\n");
709  return false;
710  }
711  OuterInnerReductions.insert(&PHI);
712  OuterInnerReductions.insert(InnerRedPhi);
713  }
714  }
715  }
716  return true;
717 }
718 
719 static bool containsSafePHI(BasicBlock *Block, bool isOuterLoopExitBlock) {
720  for (PHINode &PHI : Block->phis()) {
721  // Reduction lcssa phi will have only 1 incoming block that from loop latch.
722  if (PHI.getNumIncomingValues() > 1)
723  return false;
724  Instruction *Ins = dyn_cast<Instruction>(PHI.getIncomingValue(0));
725  if (!Ins)
726  return false;
727  // Incoming value for lcssa phi's in outer loop exit can only be inner loop
728  // exits lcssa phi else it would not be tightly nested.
729  if (!isa<PHINode>(Ins) && isOuterLoopExitBlock)
730  return false;
731  }
732  return true;
733 }
734 
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();
740 
741  // transform currently expects the loop latches to also be the exiting
742  // blocks.
743  if (InnerLoop->getExitingBlock() != InnerLoopLatch ||
744  OuterLoop->getExitingBlock() != OuterLoop->getLoopLatch() ||
745  !isa<BranchInst>(InnerLoopLatch->getTerminator()) ||
746  !isa<BranchInst>(OuterLoop->getLoopLatch()->getTerminator())) {
747  LLVM_DEBUG(
748  dbgs() << "Loops where the latch is not the exiting block are not"
749  << " supported currently.\n");
750  ORE->emit([&]() {
751  return OptimizationRemarkMissed(DEBUG_TYPE, "ExitingNotLatch",
752  OuterLoop->getStartLoc(),
753  OuterLoop->getHeader())
754  << "Loops where the latch is not the exiting block cannot be"
755  " interchange currently.";
756  });
757  return true;
758  }
759 
760  PHINode *InnerInductionVar;
761  SmallVector<PHINode *, 8> Inductions;
762  if (!findInductionAndReductions(OuterLoop, Inductions, InnerLoop)) {
763  LLVM_DEBUG(
764  dbgs() << "Only outer loops with induction or reduction PHI nodes "
765  << "are supported currently.\n");
766  ORE->emit([&]() {
767  return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedPHIOuter",
768  OuterLoop->getStartLoc(),
769  OuterLoop->getHeader())
770  << "Only outer loops with induction or reduction PHI nodes can be"
771  " interchanged currently.";
772  });
773  return true;
774  }
775 
776  // TODO: Currently we handle only loops with 1 induction variable.
777  if (Inductions.size() != 1) {
778  LLVM_DEBUG(dbgs() << "Loops with more than 1 induction variables are not "
779  << "supported currently.\n");
780  ORE->emit([&]() {
781  return OptimizationRemarkMissed(DEBUG_TYPE, "MultiIndutionOuter",
782  OuterLoop->getStartLoc(),
783  OuterLoop->getHeader())
784  << "Only outer loops with 1 induction variable can be "
785  "interchanged currently.";
786  });
787  return true;
788  }
789 
790  Inductions.clear();
791  if (!findInductionAndReductions(InnerLoop, Inductions, nullptr)) {
792  LLVM_DEBUG(
793  dbgs() << "Only inner loops with induction or reduction PHI nodes "
794  << "are supported currently.\n");
795  ORE->emit([&]() {
796  return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedPHIInner",
797  InnerLoop->getStartLoc(),
798  InnerLoop->getHeader())
799  << "Only inner loops with induction or reduction PHI nodes can be"
800  " interchange currently.";
801  });
802  return true;
803  }
804 
805  // TODO: Currently we handle only loops with 1 induction variable.
806  if (Inductions.size() != 1) {
807  LLVM_DEBUG(
808  dbgs() << "We currently only support loops with 1 induction variable."
809  << "Failed to interchange due to current limitation\n");
810  ORE->emit([&]() {
811  return OptimizationRemarkMissed(DEBUG_TYPE, "MultiInductionInner",
812  InnerLoop->getStartLoc(),
813  InnerLoop->getHeader())
814  << "Only inner loops with 1 induction variable can be "
815  "interchanged currently.";
816  });
817  return true;
818  }
819  InnerInductionVar = Inductions.pop_back_val();
820 
821  // TODO: Triangular loops are not handled for now.
822  if (!isLoopStructureUnderstood(InnerInductionVar)) {
823  LLVM_DEBUG(dbgs() << "Loop structure not understood by pass\n");
824  ORE->emit([&]() {
825  return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedStructureInner",
826  InnerLoop->getStartLoc(),
827  InnerLoop->getHeader())
828  << "Inner loop structure not understood currently.";
829  });
830  return true;
831  }
832 
833  // TODO: We only handle LCSSA PHI's corresponding to reduction for now.
834  BasicBlock *InnerExit = InnerLoop->getExitBlock();
835  if (!containsSafePHI(InnerExit, false)) {
836  LLVM_DEBUG(
837  dbgs() << "Can only handle LCSSA PHIs in inner loops currently.\n");
838  ORE->emit([&]() {
839  return OptimizationRemarkMissed(DEBUG_TYPE, "NoLCSSAPHIOuterInner",
840  InnerLoop->getStartLoc(),
841  InnerLoop->getHeader())
842  << "Only inner loops with LCSSA PHIs can be interchange "
843  "currently.";
844  });
845  return true;
846  }
847 
848  // TODO: Current limitation: Since we split the inner loop latch at the point
849  // were induction variable is incremented (induction.next); We cannot have
850  // more than 1 user of induction.next since it would result in broken code
851  // after split.
852  // e.g.
853  // for(i=0;i<N;i++) {
854  // for(j = 0;j<M;j++) {
855  // A[j+1][i+2] = A[j][i]+k;
856  // }
857  // }
858  Instruction *InnerIndexVarInc = nullptr;
859  if (InnerInductionVar->getIncomingBlock(0) == InnerLoopPreHeader)
860  InnerIndexVarInc =
861  dyn_cast<Instruction>(InnerInductionVar->getIncomingValue(1));
862  else
863  InnerIndexVarInc =
864  dyn_cast<Instruction>(InnerInductionVar->getIncomingValue(0));
865 
866  if (!InnerIndexVarInc) {
867  LLVM_DEBUG(
868  dbgs() << "Did not find an instruction to increment the induction "
869  << "variable.\n");
870  ORE->emit([&]() {
871  return OptimizationRemarkMissed(DEBUG_TYPE, "NoIncrementInInner",
872  InnerLoop->getStartLoc(),
873  InnerLoop->getHeader())
874  << "The inner loop does not increment the induction variable.";
875  });
876  return true;
877  }
878 
879  // Since we split the inner loop latch on this induction variable. Make sure
880  // we do not have any instruction between the induction variable and branch
881  // instruction.
882 
883  bool FoundInduction = false;
884  for (const Instruction &I :
885  llvm::reverse(InnerLoopLatch->instructionsWithoutDebug())) {
886  if (isa<BranchInst>(I) || isa<CmpInst>(I) || isa<TruncInst>(I) ||
887  isa<ZExtInst>(I))
888  continue;
889 
890  // We found an instruction. If this is not induction variable then it is not
891  // safe to split this loop latch.
892  if (!I.isIdenticalTo(InnerIndexVarInc)) {
893  LLVM_DEBUG(dbgs() << "Found unsupported instructions between induction "
894  << "variable increment and branch.\n");
895  ORE->emit([&]() {
897  DEBUG_TYPE, "UnsupportedInsBetweenInduction",
898  InnerLoop->getStartLoc(), InnerLoop->getHeader())
899  << "Found unsupported instruction between induction variable "
900  "increment and branch.";
901  });
902  return true;
903  }
904 
905  FoundInduction = true;
906  break;
907  }
908  // The loop latch ended and we didn't find the induction variable return as
909  // current limitation.
910  if (!FoundInduction) {
911  LLVM_DEBUG(dbgs() << "Did not find the induction variable.\n");
912  ORE->emit([&]() {
913  return OptimizationRemarkMissed(DEBUG_TYPE, "NoIndutionVariable",
914  InnerLoop->getStartLoc(),
915  InnerLoop->getHeader())
916  << "Did not find the induction variable.";
917  });
918  return true;
919  }
920  return false;
921 }
922 
923 // We currently support LCSSA PHI nodes in the outer loop exit, if their
924 // incoming values do not come from the outer loop latch or if the
925 // outer loop latch has a single predecessor. In that case, the value will
926 // be available if both the inner and outer loop conditions are true, which
927 // will still be true after interchanging. If we have multiple predecessor,
928 // that may not be the case, e.g. because the outer loop latch may be executed
929 // if the inner loop is not executed.
930 static bool areLoopExitPHIsSupported(Loop *OuterLoop, Loop *InnerLoop) {
931  BasicBlock *LoopNestExit = OuterLoop->getUniqueExitBlock();
932  for (PHINode &PHI : LoopNestExit->phis()) {
933  // FIXME: We currently are not able to detect floating point reductions
934  // and have to use floating point PHIs as a proxy to prevent
935  // interchanging in the presence of floating point reductions.
936  if (PHI.getType()->isFloatingPointTy())
937  return false;
938  for (unsigned i = 0; i < PHI.getNumIncomingValues(); i++) {
939  Instruction *IncomingI = dyn_cast<Instruction>(PHI.getIncomingValue(i));
940  if (!IncomingI || IncomingI->getParent() != OuterLoop->getLoopLatch())
941  continue;
942 
943  // The incoming value is defined in the outer loop latch. Currently we
944  // only support that in case the outer loop latch has a single predecessor.
945  // This guarantees that the outer loop latch is executed if and only if
946  // the inner loop is executed (because tightlyNested() guarantees that the
947  // outer loop header only branches to the inner loop or the outer loop
948  // latch).
949  // FIXME: We could weaken this logic and allow multiple predecessors,
950  // if the values are produced outside the loop latch. We would need
951  // additional logic to update the PHI nodes in the exit block as
952  // well.
953  if (OuterLoop->getLoopLatch()->getUniquePredecessor() == nullptr)
954  return false;
955  }
956  }
957  return true;
958 }
959 
960 bool LoopInterchangeLegality::canInterchangeLoops(unsigned InnerLoopId,
961  unsigned OuterLoopId,
962  CharMatrix &DepMatrix) {
963  if (!isLegalToInterChangeLoops(DepMatrix, InnerLoopId, OuterLoopId)) {
964  LLVM_DEBUG(dbgs() << "Failed interchange InnerLoopId = " << InnerLoopId
965  << " and OuterLoopId = " << OuterLoopId
966  << " due to dependence\n");
967  ORE->emit([&]() {
968  return OptimizationRemarkMissed(DEBUG_TYPE, "Dependence",
969  InnerLoop->getStartLoc(),
970  InnerLoop->getHeader())
971  << "Cannot interchange loops due to dependences.";
972  });
973  return false;
974  }
975  // Check if outer and inner loop contain legal instructions only.
976  for (auto *BB : OuterLoop->blocks())
977  for (Instruction &I : BB->instructionsWithoutDebug())
978  if (CallInst *CI = dyn_cast<CallInst>(&I)) {
979  // readnone functions do not prevent interchanging.
980  if (CI->doesNotReadMemory())
981  continue;
982  LLVM_DEBUG(
983  dbgs() << "Loops with call instructions cannot be interchanged "
984  << "safely.");
985  ORE->emit([&]() {
986  return OptimizationRemarkMissed(DEBUG_TYPE, "CallInst",
987  CI->getDebugLoc(),
988  CI->getParent())
989  << "Cannot interchange loops due to call instruction.";
990  });
991 
992  return false;
993  }
994 
995  // TODO: The loops could not be interchanged due to current limitations in the
996  // transform module.
997  if (currentLimitations()) {
998  LLVM_DEBUG(dbgs() << "Not legal because of current transform limitation\n");
999  return false;
1000  }
1001 
1002  // Check if the loops are tightly nested.
1003  if (!tightlyNested(OuterLoop, InnerLoop)) {
1004  LLVM_DEBUG(dbgs() << "Loops not tightly nested\n");
1005  ORE->emit([&]() {
1006  return OptimizationRemarkMissed(DEBUG_TYPE, "NotTightlyNested",
1007  InnerLoop->getStartLoc(),
1008  InnerLoop->getHeader())
1009  << "Cannot interchange loops because they are not tightly "
1010  "nested.";
1011  });
1012  return false;
1013  }
1014 
1015  if (!areLoopExitPHIsSupported(OuterLoop, InnerLoop)) {
1016  LLVM_DEBUG(dbgs() << "Found unsupported PHI nodes in outer loop exit.\n");
1017  ORE->emit([&]() {
1018  return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedExitPHI",
1019  OuterLoop->getStartLoc(),
1020  OuterLoop->getHeader())
1021  << "Found unsupported PHI node in loop exit.";
1022  });
1023  return false;
1024  }
1025 
1026  return true;
1027 }
1028 
1029 int LoopInterchangeProfitability::getInstrOrderCost() {
1030  unsigned GoodOrder, BadOrder;
1031  BadOrder = GoodOrder = 0;
1032  for (BasicBlock *BB : InnerLoop->blocks()) {
1033  for (Instruction &Ins : *BB) {
1034  if (const GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(&Ins)) {
1035  unsigned NumOp = GEP->getNumOperands();
1036  bool FoundInnerInduction = false;
1037  bool FoundOuterInduction = false;
1038  for (unsigned i = 0; i < NumOp; ++i) {
1039  const SCEV *OperandVal = SE->getSCEV(GEP->getOperand(i));
1040  const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(OperandVal);
1041  if (!AR)
1042  continue;
1043 
1044  // If we find the inner induction after an outer induction e.g.
1045  // for(int i=0;i<N;i++)
1046  // for(int j=0;j<N;j++)
1047  // A[i][j] = A[i-1][j-1]+k;
1048  // then it is a good order.
1049  if (AR->getLoop() == InnerLoop) {
1050  // We found an InnerLoop induction after OuterLoop induction. It is
1051  // a good order.
1052  FoundInnerInduction = true;
1053  if (FoundOuterInduction) {
1054  GoodOrder++;
1055  break;
1056  }
1057  }
1058  // If we find the outer induction after an inner induction e.g.
1059  // for(int i=0;i<N;i++)
1060  // for(int j=0;j<N;j++)
1061  // A[j][i] = A[j-1][i-1]+k;
1062  // then it is a bad order.
1063  if (AR->getLoop() == OuterLoop) {
1064  // We found an OuterLoop induction after InnerLoop induction. It is
1065  // a bad order.
1066  FoundOuterInduction = true;
1067  if (FoundInnerInduction) {
1068  BadOrder++;
1069  break;
1070  }
1071  }
1072  }
1073  }
1074  }
1075  }
1076  return GoodOrder - BadOrder;
1077 }
1078 
1079 static bool isProfitableForVectorization(unsigned InnerLoopId,
1080  unsigned OuterLoopId,
1081  CharMatrix &DepMatrix) {
1082  // TODO: Improve this heuristic to catch more cases.
1083  // If the inner loop is loop independent or doesn't carry any dependency it is
1084  // profitable to move this to outer position.
1085  for (auto &Row : DepMatrix) {
1086  if (Row[InnerLoopId] != 'S' && Row[InnerLoopId] != 'I')
1087  return false;
1088  // TODO: We need to improve this heuristic.
1089  if (Row[OuterLoopId] != '=')
1090  return false;
1091  }
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();
1096 }
1097 
1098 bool LoopInterchangeProfitability::isProfitable(unsigned InnerLoopId,
1099  unsigned OuterLoopId,
1100  CharMatrix &DepMatrix) {
1101  // TODO: Add better profitability checks.
1102  // e.g
1103  // 1) Construct dependency matrix and move the one with no loop carried dep
1104  // inside to enable vectorization.
1105 
1106  // This is rough cost estimation algorithm. It counts the good and bad order
1107  // of induction variables in the instruction and allows reordering if number
1108  // of bad orders is more than good.
1109  int Cost = getInstrOrderCost();
1110  LLVM_DEBUG(dbgs() << "Cost = " << Cost << "\n");
1111  if (Cost < -LoopInterchangeCostThreshold)
1112  return true;
1113 
1114  // It is not profitable as per current cache profitability model. But check if
1115  // we can move this loop outside to improve parallelism.
1116  if (isProfitableForVectorization(InnerLoopId, OuterLoopId, DepMatrix))
1117  return true;
1118 
1119  ORE->emit([&]() {
1120  return OptimizationRemarkMissed(DEBUG_TYPE, "InterchangeNotProfitable",
1121  InnerLoop->getStartLoc(),
1122  InnerLoop->getHeader())
1123  << "Interchanging loops is too costly (cost="
1124  << ore::NV("Cost", Cost) << ", threshold="
1125  << ore::NV("Threshold", LoopInterchangeCostThreshold)
1126  << ") and it does not improve parallelism.";
1127  });
1128  return false;
1129 }
1130 
1131 void LoopInterchangeTransform::removeChildLoop(Loop *OuterLoop,
1132  Loop *InnerLoop) {
1133  for (Loop *L : *OuterLoop)
1134  if (L == InnerLoop) {
1135  OuterLoop->removeChildLoop(L);
1136  return;
1137  }
1138  llvm_unreachable("Couldn't find loop");
1139 }
1140 
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.
1144 ///
1145 /// Before interchanging, we have the following structure
1146 /// Outer preheader
1147 // Outer header
1148 // Inner preheader
1149 // Inner header
1150 // Inner body
1151 // Inner latch
1152 // outer bbs
1153 // Outer latch
1154 //
1155 // After interchanging:
1156 // Inner preheader
1157 // Inner header
1158 // Outer preheader
1159 // Outer header
1160 // Inner body
1161 // outer bbs
1162 // Outer latch
1163 // Inner latch
1164 void LoopInterchangeTransform::restructureLoops(
1165  Loop *NewInner, Loop *NewOuter, BasicBlock *OrigInnerPreHeader,
1166  BasicBlock *OrigOuterPreHeader) {
1167  Loop *OuterLoopParent = OuterLoop->getParentLoop();
1168  // The original inner loop preheader moves from the new inner loop to
1169  // the parent loop, if there is one.
1170  NewInner->removeBlockFromLoop(OrigInnerPreHeader);
1171  LI->changeLoopFor(OrigInnerPreHeader, OuterLoopParent);
1172 
1173  // Switch the loop levels.
1174  if (OuterLoopParent) {
1175  // Remove the loop from its parent loop.
1176  removeChildLoop(OuterLoopParent, NewInner);
1177  removeChildLoop(NewInner, NewOuter);
1178  OuterLoopParent->addChildLoop(NewOuter);
1179  } else {
1180  removeChildLoop(NewInner, NewOuter);
1181  LI->changeTopLevelLoop(NewInner, NewOuter);
1182  }
1183  while (!NewOuter->empty())
1184  NewInner->addChildLoop(NewOuter->removeChildLoop(NewOuter->begin()));
1185  NewOuter->addChildLoop(NewInner);
1186 
1187  // BBs from the original inner loop.
1188  SmallVector<BasicBlock *, 8> OrigInnerBBs(NewOuter->blocks());
1189 
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);
1195 
1196  // Now remove inner loop header and latch from the new inner loop and move
1197  // other BBs (the loop body) to the new inner loop.
1198  BasicBlock *OuterHeader = NewOuter->getHeader();
1199  BasicBlock *OuterLatch = NewOuter->getLoopLatch();
1200  for (BasicBlock *BB : OrigInnerBBs) {
1201  // Nothing will change for BBs in child loops.
1202  if (LI->getLoopFor(BB) != NewOuter)
1203  continue;
1204  // Remove the new outer loop header and latch from the new inner loop.
1205  if (BB == OuterHeader || BB == OuterLatch)
1206  NewInner->removeBlockFromLoop(BB);
1207  else
1208  LI->changeLoopFor(BB, NewInner);
1209  }
1210 
1211  // The preheader of the original outer loop becomes part of the new
1212  // outer loop.
1213  NewOuter->addBlockEntry(OrigOuterPreHeader);
1214  LI->changeLoopFor(OrigOuterPreHeader, NewOuter);
1215 
1216  // Tell SE that we move the loops around.
1217  SE->forgetLoop(NewOuter);
1218  SE->forgetLoop(NewInner);
1219 }
1220 
1222  bool Transformed = false;
1223  Instruction *InnerIndexVar;
1224 
1225  if (InnerLoop->getSubLoops().empty()) {
1226  BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
1227  LLVM_DEBUG(dbgs() << "Splitting the inner loop latch\n");
1228  PHINode *InductionPHI = getInductionVariable(InnerLoop, SE);
1229  if (!InductionPHI) {
1230  LLVM_DEBUG(dbgs() << "Failed to find the point to split loop latch \n");
1231  return false;
1232  }
1233 
1234  if (InductionPHI->getIncomingBlock(0) == InnerLoopPreHeader)
1235  InnerIndexVar = dyn_cast<Instruction>(InductionPHI->getIncomingValue(1));
1236  else
1237  InnerIndexVar = dyn_cast<Instruction>(InductionPHI->getIncomingValue(0));
1238 
1239  // Ensure that InductionPHI is the first Phi node.
1240  if (&InductionPHI->getParent()->front() != InductionPHI)
1241  InductionPHI->moveBefore(&InductionPHI->getParent()->front());
1242 
1243  // Create a new latch block for the inner loop. We split at the
1244  // current latch's terminator and then move the condition and all
1245  // operands that are not either loop-invariant or the induction PHI into the
1246  // new latch block.
1247  BasicBlock *NewLatch =
1248  SplitBlock(InnerLoop->getLoopLatch(),
1249  InnerLoop->getLoopLatch()->getTerminator(), DT, LI);
1250 
1252  unsigned i = 0;
1253  auto MoveInstructions = [&i, &WorkList, this, InductionPHI, NewLatch]() {
1254  for (; i < WorkList.size(); i++) {
1255  // Duplicate instruction and move it the new latch. Update uses that
1256  // have been moved.
1257  Instruction *NewI = WorkList[i]->clone();
1258  NewI->insertBefore(NewLatch->getFirstNonPHI());
1259  assert(!NewI->mayHaveSideEffects() &&
1260  "Moving instructions with side-effects may change behavior of "
1261  "the loop nest!");
1262  for (auto UI = WorkList[i]->use_begin(), UE = WorkList[i]->use_end();
1263  UI != UE;) {
1264  Use &U = *UI++;
1265  Instruction *UserI = cast<Instruction>(U.getUser());
1266  if (!InnerLoop->contains(UserI->getParent()) ||
1267  UserI->getParent() == NewLatch || UserI == InductionPHI)
1268  U.set(NewI);
1269  }
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()) {
1274  if (!OpI ||
1275  this->LI->getLoopFor(OpI->getParent()) != this->InnerLoop ||
1276  OpI == InductionPHI)
1277  continue;
1278  WorkList.insert(OpI);
1279  }
1280  }
1281  };
1282 
1283  // FIXME: Should we interchange when we have a constant condition?
1284  Instruction *CondI = dyn_cast<Instruction>(
1285  cast<BranchInst>(InnerLoop->getLoopLatch()->getTerminator())
1286  ->getCondition());
1287  if (CondI)
1288  WorkList.insert(CondI);
1289  MoveInstructions();
1290  WorkList.insert(cast<Instruction>(InnerIndexVar));
1291  MoveInstructions();
1292 
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");
1297  }
1298 
1299  Transformed |= adjustLoopLinks();
1300  if (!Transformed) {
1301  LLVM_DEBUG(dbgs() << "adjustLoopLinks failed\n");
1302  return false;
1303  }
1304 
1305  return true;
1306 }
1307 
1308 /// \brief Move all instructions except the terminator from FromBB right before
1309 /// InsertBefore
1310 static void moveBBContents(BasicBlock *FromBB, Instruction *InsertBefore) {
1311  auto &ToList = InsertBefore->getParent()->getInstList();
1312  auto &FromList = FromBB->getInstList();
1313 
1314  ToList.splice(InsertBefore->getIterator(), FromList, FromList.begin(),
1315  FromBB->getTerminator()->getIterator());
1316 }
1317 
1318 /// Update BI to jump to NewBB instead of OldBB. Records updates to
1319 /// the dominator tree in DTUpdates, if DT should be preserved.
1320 static void updateSuccessor(BranchInst *BI, BasicBlock *OldBB,
1321  BasicBlock *NewBB,
1322  std::vector<DominatorTree::UpdateType> &DTUpdates) {
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);
1329 
1330  DTUpdates.push_back(
1332  DTUpdates.push_back(
1334  break;
1335  }
1336  }
1337 }
1338 
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) {
1343 
1344  // Deal with LCSSA PHI nodes in the exit block of the inner loop, that are
1345  // defined either in the header or latch. Those blocks will become header and
1346  // latch of the new outer loop, and the only possible users can PHI nodes
1347  // in the exit block of the loop nest or the outer loop header (reduction
1348  // PHIs, in that case, the incoming value must be defined in the inner loop
1349  // header). We can just substitute the user with the incoming value and remove
1350  // the PHI.
1351  for (PHINode &P : make_early_inc_range(InnerExit->phis())) {
1352  assert(P.getNumIncomingValues() == 1 &&
1353  "Only loops with a single exit are supported!");
1354 
1355  // Incoming values are guaranteed be instructions currently.
1356  auto IncI = cast<Instruction>(P.getIncomingValueForBlock(InnerLatch));
1357  // Skip phis with incoming values from the inner loop body, excluding the
1358  // header and latch.
1359  if (IncI->getParent() != InnerLatch && IncI->getParent() != InnerHeader)
1360  continue;
1361 
1362  assert(all_of(P.users(),
1363  [OuterHeader, OuterExit, IncI, InnerHeader](User *U) {
1364  return (cast<PHINode>(U)->getParent() == OuterHeader &&
1365  IncI->getParent() == InnerHeader) ||
1366  cast<PHINode>(U)->getParent() == OuterExit;
1367  }) &&
1368  "Can only replace phis iff the uses are in the loop nest exit or "
1369  "the incoming value is defined in the inner header (it will "
1370  "dominate all loop blocks after interchanging)");
1371  P.replaceAllUsesWith(IncI);
1372  P.eraseFromParent();
1373  }
1374 
1375  SmallVector<PHINode *, 8> LcssaInnerExit;
1376  for (PHINode &P : InnerExit->phis())
1377  LcssaInnerExit.push_back(&P);
1378 
1379  SmallVector<PHINode *, 8> LcssaInnerLatch;
1380  for (PHINode &P : InnerLatch->phis())
1381  LcssaInnerLatch.push_back(&P);
1382 
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());
1390 
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());
1395 
1396  // Deal with LCSSA PHI nodes in the loop nest exit block. For PHIs that have
1397  // incoming values from the outer latch or header, we have to add a new PHI
1398  // in the inner loop latch, which became the exit block of the outer loop,
1399  // after interchanging.
1400  if (OuterExit) {
1401  for (PHINode &P : OuterExit->phis()) {
1402  if (P.getNumIncomingValues() != 1)
1403  continue;
1404  // Skip Phis with incoming values not defined in the outer loop's header
1405  // and latch. Also skip incoming phis defined in the latch. Those should
1406  // already have been updated.
1407  auto I = dyn_cast<Instruction>(P.getIncomingValue(0));
1408  if (!I || ((I->getParent() != OuterLatch || isa<PHINode>(I)) &&
1409  I->getParent() != OuterHeader))
1410  continue;
1411 
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);
1417  }
1418  }
1419 
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);
1424 }
1425 
1426 bool LoopInterchangeTransform::adjustLoopBranches() {
1427  LLVM_DEBUG(dbgs() << "adjustLoopBranches called\n");
1428  std::vector<DominatorTree::UpdateType> DTUpdates;
1429 
1430  BasicBlock *OuterLoopPreHeader = OuterLoop->getLoopPreheader();
1431  BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
1432 
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);
1447 
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;
1458 
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());
1467 
1468  if (!OuterLoopPredecessor || !InnerLoopLatchPredecessor ||
1469  !OuterLoopLatchBI || !InnerLoopLatchBI || !OuterLoopHeaderBI ||
1470  !InnerLoopHeaderBI)
1471  return false;
1472 
1473  BranchInst *InnerLoopLatchPredecessorBI =
1474  dyn_cast<BranchInst>(InnerLoopLatchPredecessor->getTerminator());
1475  BranchInst *OuterLoopPredecessorBI =
1476  dyn_cast<BranchInst>(OuterLoopPredecessor->getTerminator());
1477 
1478  if (!OuterLoopPredecessorBI || !InnerLoopLatchPredecessorBI)
1479  return false;
1480  BasicBlock *InnerLoopHeaderSuccessor = InnerLoopHeader->getUniqueSuccessor();
1481  if (!InnerLoopHeaderSuccessor)
1482  return false;
1483 
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);
1490 
1491  // Adjust reduction PHI's now that the incoming block has changed.
1492  InnerLoopHeaderSuccessor->replacePhiUsesWith(InnerLoopHeader,
1493  OuterLoopHeader);
1494 
1495  updateSuccessor(InnerLoopHeaderBI, InnerLoopHeaderSuccessor,
1496  OuterLoopPreHeader, DTUpdates);
1497 
1498  // -------------Adjust loop latches-----------
1499  if (InnerLoopLatchBI->getSuccessor(0) == InnerLoopHeader)
1500  InnerLoopLatchSuccessor = InnerLoopLatchBI->getSuccessor(1);
1501  else
1502  InnerLoopLatchSuccessor = InnerLoopLatchBI->getSuccessor(0);
1503 
1504  updateSuccessor(InnerLoopLatchPredecessorBI, InnerLoopLatch,
1505  InnerLoopLatchSuccessor, DTUpdates);
1506 
1507 
1508  if (OuterLoopLatchBI->getSuccessor(0) == OuterLoopHeader)
1509  OuterLoopLatchSuccessor = OuterLoopLatchBI->getSuccessor(1);
1510  else
1511  OuterLoopLatchSuccessor = OuterLoopLatchBI->getSuccessor(0);
1512 
1513  updateSuccessor(InnerLoopLatchBI, InnerLoopLatchSuccessor,
1514  OuterLoopLatchSuccessor, DTUpdates);
1515  updateSuccessor(OuterLoopLatchBI, OuterLoopLatchSuccessor, InnerLoopLatch,
1516  DTUpdates);
1517 
1518  DT->applyUpdates(DTUpdates);
1519  restructureLoops(OuterLoop, InnerLoop, InnerLoopPreHeader,
1520  OuterLoopPreHeader);
1521 
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);
1527 
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));
1534 
1535  auto &OuterInnerReductions = LIL.getOuterInnerReductions();
1536  (void)OuterInnerReductions;
1537 
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");
1545  }
1546  for (PHINode *PHI : InnerLoopPHIs) {
1547  PHI->moveBefore(OuterLoopHeader->getFirstNonPHI());
1548  assert(OuterInnerReductions.find(PHI) != OuterInnerReductions.end() &&
1549  "Expected a reduction PHI node");
1550  }
1551 
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);
1557 
1558  return true;
1559 }
1560 
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());
1571 
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);
1578 }
1579 
1580 bool LoopInterchangeTransform::adjustLoopLinks() {
1581  // Adjust all branches in the inner and outer loop.
1582  bool Changed = adjustLoopBranches();
1583  if (Changed)
1584  adjustLoopPreheaders();
1585  return Changed;
1586 }
1587 
1588 char LoopInterchange::ID = 0;
1589 
1590 INITIALIZE_PASS_BEGIN(LoopInterchange, "loop-interchange",
1591  "Interchanges loops for cache reuse", false, false)
1595 
1596 INITIALIZE_PASS_END(LoopInterchange, "loop-interchange",
1597  "Interchanges loops for cache reuse", false, false)
1598 
1599 Pass *llvm::createLoopInterchangePass() { return new LoopInterchange(); }
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:80
Diagnostic information for missed-optimization remarks.
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h:209
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
DiagnosticInfoOptimizationBase::Argument NV
This class represents lattice values for constants.
Definition: AllocatorList.h:23
static bool isInductionPHI(PHINode *Phi, const Loop *L, ScalarEvolution *SE, InductionDescriptor &D, const SCEV *Expr=nullptr, SmallVectorImpl< Instruction *> *CastsToIgnore=nullptr)
Returns true if Phi is an induction in the loop L.
static LoopVector populateWorklist(Loop &L)
Legacy pass manager pass to access dependence information.
static bool isProfitableForVectorization(unsigned InnerLoopId, unsigned OuterLoopId, CharMatrix &DepMatrix)
void push_back(const T &Elt)
Definition: SmallVector.h:211
LoopT * removeChildLoop(iterator I)
This removes the specified child from being a subloop of this loop.
Definition: LoopInfo.h:384
The main scalar evolution driver.
This class represents a function call, abstracting a target machine&#39;s calling convention.
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:160
static bool containsNoDependence(CharMatrix &DepMatrix, unsigned Row, unsigned Column)
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition: STLExtras.h:508
auto count_if(R &&Range, UnaryPredicate P) -> typename std::iterator_traits< decltype(adl_begin(Range))>::difference_type
Wrapper function around std::count_if to count the number of times an element satisfying a given pred...
Definition: STLExtras.h:1239
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1165
BasicBlock * getSuccessor(unsigned i) const
STATISTIC(NumFunctions, "Total number of functions")
Hexagon Common GEP
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.cpp:144
DependenceInfo - This class is the main dependence-analysis driver.
BasicBlock * SplitBlock(BasicBlock *Old, Instruction *SplitPt, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="")
Split the specified block at the specified instruction - everything before SplitPt stays in Old and e...
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:343
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:273
static bool populateDependencyMatrix(CharMatrix &DepMatrix, unsigned Level, Loop *L, DependenceInfo *DI)
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:50
unsigned getNumBackEdges() const
Calculate the number of back edges to the loop header.
Definition: LoopInfo.h:233
void replacePhiUsesWith(BasicBlock *Old, BasicBlock *New)
Update all phi nodes in this basic block to refer to basic block New instead of basic block Old...
Definition: BasicBlock.cpp:441
unsigned getNumSuccessors() const
A Use represents the edge between a Value definition and its users.
Definition: Use.h:55
void addBlockEntry(BlockT *BB)
This adds a basic block directly to the basic block list.
Definition: LoopInfo.h:403
BlockT * getHeader() const
Definition: LoopInfo.h:105
ConstantInt * getValue() const
auto reverse(ContainerTy &&C, typename std::enable_if< has_rbegin< ContainerTy >::value >::type *=nullptr) -> decltype(make_range(C.rbegin(), C.rend()))
Definition: STLExtras.h:261
static cl::opt< int > LoopInterchangeCostThreshold("loop-interchange-threshold", cl::init(0), cl::Hidden, cl::desc("Interchange if you gain more than this number"))
Instruction * clone() const
Create a copy of &#39;this&#39; instruction that is identical in all ways except the following: ...
User * getUser() const LLVM_READONLY
Returns the User that contains this Use.
Definition: Use.cpp:40
static bool isLegalToInterChangeLoops(CharMatrix &DepMatrix, unsigned InnerLoopId, unsigned OuterLoopId)
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:246
This node represents a polynomial recurrence on the trip count of the specified loop.
const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
Definition: BasicBlock.cpp:253
static bool validDepInterchange(CharMatrix &DepMatrix, unsigned Row, unsigned OuterLoopId, char InnerDep, char OuterDep)
static const unsigned MaxLoopNestDepth
static void updateSuccessor(BranchInst *BI, BasicBlock *OldBB, BasicBlock *NewBB, std::vector< DominatorTree::UpdateType > &DTUpdates)
Update BI to jump to NewBB instead of OldBB.
const SCEV * getStepRecurrence(ScalarEvolution &SE) const
Constructs and returns the recurrence indicating how much this expression steps by.
loop interchange
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
Value * getOperand(unsigned i) const
Definition: User.h:169
an instruction for type-safe pointer arithmetic to access elements of arrays and structs ...
Definition: Instructions.h:881
const SCEV * getCouldNotCompute()
#define P(N)
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
std::unique_ptr< Dependence > depends(Instruction *Src, Instruction *Dst, bool PossiblyLoopIndependent)
depends - Tests for a dependence between the Src and Dst instructions.
const Instruction * getFirstNonPHI() const
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
Definition: BasicBlock.cpp:196
void set(Value *Val)
Definition: Value.h:730
void insertBefore(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified instruction...
Definition: Instruction.cpp:73
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:46
Conditional or Unconditional Branch instruction.
iterator_range< filter_iterator< BasicBlock::const_iterator, std::function< bool(const Instruction &)> > > instructionsWithoutDebug() const
Return a const iterator range over the instructions in the block, skipping any debug instructions...
Definition: BasicBlock.cpp:94
This file contains the declarations for the subclasses of Constant, which represent the different fla...
const Instruction & front() const
Definition: BasicBlock.h:285
bool mayHaveSideEffects() const
Return true if the instruction may have side effects.
Definition: Instruction.h:582
loop Interchanges loops for cache reuse
Diagnostic information for applied optimization remarks.
Represent the analysis usage information of a pass.
void splice(iterator where, iplist_impl &L2)
Definition: ilist.h:327
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1172
constexpr double e
Definition: MathExtras.h:57
bool isAffine() const
Return true if this represents an expression A + B*x where A and B are loop invariant values...
self_iterator getIterator()
Definition: ilist_node.h:81
static bool isReductionPHI(PHINode *Phi, Loop *TheLoop, RecurrenceDescriptor &RedDes, DemandedBits *DB=nullptr, AssumptionCache *AC=nullptr, DominatorTree *DT=nullptr)
Returns true if Phi is a reduction in TheLoop.
BlockT * getExitBlock() const
If getExitBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:75
Used in the streaming interface as the general argument type.
BlockT * getUniqueExitBlock() const
If getUniqueExitBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:131
DebugLoc getStartLoc() const
Return the debug location of the start of this loop.
Definition: LoopInfo.cpp:611
iterator_range< decltype(adl_begin(std::declval< T >)))> drop_begin(T &&t, int n)
static unsigned getIncomingValueNumForOperand(unsigned i)
size_t size() const
Definition: SmallVector.h:52
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
void initializeLoopInterchangePass(PassRegistry &)
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
bool isLoopInvariant(const Value *V) const
Return true if the specified value is loop invariant.
Definition: LoopInfo.cpp:61
void setSuccessor(unsigned idx, BasicBlock *NewSucc)
bool isNegative() const
Definition: Constants.h:187
The RecurrenceDescriptor is used to identify recurrences variables in a loop.
Definition: IVDescriptors.h:62
#define DEBUG_TYPE
BlockT * getLoopPredecessor() const
If the given loop&#39;s header has exactly one unique predecessor outside the loop, return it...
Definition: LoopInfoImpl.h:188
const InstListType & getInstList() const
Return the underlying instruction list container.
Definition: BasicBlock.h:338
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:115
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:297
Iterator for intrusive lists based on ilist_node.
unsigned getNumOperands() const
Definition: User.h:191
static bool containsSafePHI(BasicBlock *Block, bool isOuterLoopExitBlock)
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:417
This is the shared class of boolean and integer constants.
Definition: Constants.h:83
void emit(DiagnosticInfoOptimizationBase &OptDiag)
Output the remark via the diagnostic handler and to the optimization record file. ...
A struct for saving information about induction variables.
void setIncomingBlock(unsigned i, BasicBlock *BB)
Pass * createLoopInterchangePass()
static void moveBBContents(BasicBlock *FromBB, Instruction *InsertBefore)
Move all instructions except the terminator from FromBB right before InsertBefore.
iterator begin() const
Definition: LoopInfo.h:147
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:374
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
unsigned getNumIncomingValues() const
Return the number of incoming edges.
static const unsigned MaxMemInstrCount
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:940
PHINode * getCanonicalInductionVariable() const
Check to see if the loop has a canonical induction variable: an integer recurrence that starts at 0 a...
Definition: LoopInfo.cpp:146
iterator_range< user_iterator > users()
Definition: Value.h:420
INITIALIZE_PASS_BEGIN(LoopInterchange, "loop-interchange", "Interchanges loops for cache reuse", false, false) INITIALIZE_PASS_END(LoopInterchange
LoopT * getParentLoop() const
Definition: LoopInfo.h:106
static PHINode * findInnerReductionPhi(Loop *L, Value *V)
const std::vector< LoopT * > & getSubLoops() const
Return the loops contained entirely within this loop.
Definition: LoopInfo.h:136
This class represents an analyzed expression in the program.
void addChildLoop(LoopT *NewChild)
Add the specified loop to be a child of this loop.
Definition: LoopInfo.h:375
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:509
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:214
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:106
#define I(x, y, z)
Definition: MD5.cpp:58
bool mayReadFromMemory() const
Return true if this instruction may read memory.
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
Definition: Constants.h:192
void getLoopAnalysisUsage(AnalysisUsage &AU)
Helper to consistently add the set of standard passes to a loop pass&#39;s AnalysisUsage.
Definition: LoopUtils.cpp:138
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:332
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
Definition: BasicBlock.h:329
static bool isOuterMostDepPositive(CharMatrix &DepMatrix, unsigned Row, unsigned Column)
void removeBlockFromLoop(BlockT *BB)
This removes the specified basic block from the current loop, updating the Blocks as appropriate...
Definition: LoopInfo.h:440
OutputIt transform(R &&Range, OutputIt d_first, UnaryPredicate P)
Wrapper function around std::transform to apply a function to a range and store the result elsewhere...
Definition: STLExtras.h:1247
Loop::LoopBounds::Direction Direction
Definition: LoopInfo.cpp:226
bool empty() const
Definition: LoopInfo.h:151
const SCEV * getBackedgeTakenCount(const Loop *L)
If the specified loop has a predictable backedge-taken count, return it, otherwise return a SCEVCould...
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static void interChangeDependencies(CharMatrix &DepMatrix, unsigned FromIndx, unsigned ToIndx)
LLVM Value Representation.
Definition: Value.h:74
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
static Value * followLCSSA(Value *SV)
succ_range successors(Instruction *I)
Definition: CFG.h:259
OptimizationRemarkEmitter legacy analysis pass.
void moveBefore(Instruction *MovePos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
Definition: Instruction.cpp:86
BasicBlock * InsertPreheaderForLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, MemorySSAUpdater *MSSAU, bool PreserveLCSSA)
InsertPreheaderForLoop - Once we discover that a loop doesn&#39;t have a preheader, this method is called...
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:48
void setIncomingValue(unsigned i, Value *V)
static void moveLCSSAPhis(BasicBlock *InnerExit, BasicBlock *InnerHeader, BasicBlock *InnerLatch, BasicBlock *OuterHeader, BasicBlock *OuterLatch, BasicBlock *OuterExit)
#define LLVM_DEBUG(X)
Definition: Debug.h:122
op_range incoming_values()
for(unsigned i=Desc.getNumOperands(), e=OldMI.getNumOperands();i !=e;++i)
iterator_range< block_iterator > blocks() const
Definition: LoopInfo.h:161
BlockT * getExitingBlock() const
If getExitingBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:49
The optimization diagnostic interface.
static bool areLoopExitPHIsSupported(Loop *OuterLoop, Loop *InnerLoop)
loops
Definition: LoopInfo.cpp:1058
const BasicBlock * getParent() const
Definition: Instruction.h:66
This class represents a constant integer value.
static PHINode * getInductionVariable(Loop *L, ScalarEvolution *SE)
const BasicBlock * getUniqueSuccessor() const
Return the successor of this block if it has a unique successor.
Definition: BasicBlock.cpp:283