LLVM  7.0.0svn
LoopInterchange.cpp
Go to the documentation of this file.
1 //===- LoopInterchange.cpp - Loop interchange pass-------------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This Pass handles loop interchange transform.
11 // This pass interchanges loops to provide a more cache-friendly memory access
12 // patterns.
13 //
14 //===----------------------------------------------------------------------===//
15 
16 #include "llvm/ADT/STLExtras.h"
17 #include "llvm/ADT/SmallVector.h"
18 #include "llvm/ADT/Statistic.h"
19 #include "llvm/ADT/StringRef.h"
22 #include "llvm/Analysis/LoopInfo.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/InstrTypes.h"
32 #include "llvm/IR/Instruction.h"
33 #include "llvm/IR/Instructions.h"
34 #include "llvm/IR/Type.h"
35 #include "llvm/IR/User.h"
36 #include "llvm/IR/Value.h"
37 #include "llvm/Pass.h"
38 #include "llvm/Support/Casting.h"
40 #include "llvm/Support/Debug.h"
43 #include "llvm/Transforms/Scalar.h"
44 #include "llvm/Transforms/Utils.h"
47 #include <cassert>
48 #include <utility>
49 #include <vector>
50 
51 using namespace llvm;
52 
53 #define DEBUG_TYPE "loop-interchange"
54 
55 STATISTIC(LoopsInterchanged, "Number of loops interchanged");
56 
58  "loop-interchange-threshold", cl::init(0), cl::Hidden,
59  cl::desc("Interchange if you gain more than this number"));
60 
61 namespace {
62 
63 using LoopVector = SmallVector<Loop *, 8>;
64 
65 // TODO: Check if we can use a sparse matrix here.
66 using CharMatrix = std::vector<std::vector<char>>;
67 
68 } // end anonymous namespace
69 
70 // Maximum number of dependencies that can be handled in the dependency matrix.
71 static const unsigned MaxMemInstrCount = 100;
72 
73 // Maximum loop depth supported.
74 static const unsigned MaxLoopNestDepth = 10;
75 
76 #ifdef DUMP_DEP_MATRICIES
77 static void printDepMatrix(CharMatrix &DepMatrix) {
78  for (auto &Row : DepMatrix) {
79  for (auto D : Row)
80  LLVM_DEBUG(dbgs() << D << " ");
81  LLVM_DEBUG(dbgs() << "\n");
82  }
83 }
84 #endif
85 
86 static bool populateDependencyMatrix(CharMatrix &DepMatrix, unsigned Level,
87  Loop *L, DependenceInfo *DI) {
88  using ValueVector = SmallVector<Value *, 16>;
89 
90  ValueVector MemInstr;
91 
92  // For each block.
93  for (BasicBlock *BB : L->blocks()) {
94  // Scan the BB and collect legal loads and stores.
95  for (Instruction &I : *BB) {
96  if (!isa<Instruction>(I))
97  return false;
98  if (auto *Ld = dyn_cast<LoadInst>(&I)) {
99  if (!Ld->isSimple())
100  return false;
101  MemInstr.push_back(&I);
102  } else if (auto *St = dyn_cast<StoreInst>(&I)) {
103  if (!St->isSimple())
104  return false;
105  MemInstr.push_back(&I);
106  }
107  }
108  }
109 
110  LLVM_DEBUG(dbgs() << "Found " << MemInstr.size()
111  << " Loads and Stores to analyze\n");
112 
113  ValueVector::iterator I, IE, J, JE;
114 
115  for (I = MemInstr.begin(), IE = MemInstr.end(); I != IE; ++I) {
116  for (J = I, JE = MemInstr.end(); J != JE; ++J) {
117  std::vector<char> Dep;
118  Instruction *Src = cast<Instruction>(*I);
119  Instruction *Dst = cast<Instruction>(*J);
120  if (Src == Dst)
121  continue;
122  // Ignore Input dependencies.
123  if (isa<LoadInst>(Src) && isa<LoadInst>(Dst))
124  continue;
125  // Track Output, Flow, and Anti dependencies.
126  if (auto D = DI->depends(Src, Dst, true)) {
127  assert(D->isOrdered() && "Expected an output, flow or anti dep.");
128  LLVM_DEBUG(StringRef DepType =
129  D->isFlow() ? "flow" : D->isAnti() ? "anti" : "output";
130  dbgs() << "Found " << DepType
131  << " dependency between Src and Dst\n"
132  << " Src:" << *Src << "\n Dst:" << *Dst << '\n');
133  unsigned Levels = D->getLevels();
134  char Direction;
135  for (unsigned II = 1; II <= Levels; ++II) {
136  const SCEV *Distance = D->getDistance(II);
137  const SCEVConstant *SCEVConst =
138  dyn_cast_or_null<SCEVConstant>(Distance);
139  if (SCEVConst) {
140  const ConstantInt *CI = SCEVConst->getValue();
141  if (CI->isNegative())
142  Direction = '<';
143  else if (CI->isZero())
144  Direction = '=';
145  else
146  Direction = '>';
147  Dep.push_back(Direction);
148  } else if (D->isScalar(II)) {
149  Direction = 'S';
150  Dep.push_back(Direction);
151  } else {
152  unsigned Dir = D->getDirection(II);
153  if (Dir == Dependence::DVEntry::LT ||
155  Direction = '<';
156  else if (Dir == Dependence::DVEntry::GT ||
158  Direction = '>';
159  else if (Dir == Dependence::DVEntry::EQ)
160  Direction = '=';
161  else
162  Direction = '*';
163  Dep.push_back(Direction);
164  }
165  }
166  while (Dep.size() != Level) {
167  Dep.push_back('I');
168  }
169 
170  DepMatrix.push_back(Dep);
171  if (DepMatrix.size() > MaxMemInstrCount) {
172  LLVM_DEBUG(dbgs() << "Cannot handle more than " << MaxMemInstrCount
173  << " dependencies inside loop\n");
174  return false;
175  }
176  }
177  }
178  }
179 
180  return true;
181 }
182 
183 // A loop is moved from index 'from' to an index 'to'. Update the Dependence
184 // matrix by exchanging the two columns.
185 static void interChangeDependencies(CharMatrix &DepMatrix, unsigned FromIndx,
186  unsigned ToIndx) {
187  unsigned numRows = DepMatrix.size();
188  for (unsigned i = 0; i < numRows; ++i) {
189  char TmpVal = DepMatrix[i][ToIndx];
190  DepMatrix[i][ToIndx] = DepMatrix[i][FromIndx];
191  DepMatrix[i][FromIndx] = TmpVal;
192  }
193 }
194 
195 // Checks if outermost non '=','S'or'I' dependence in the dependence matrix is
196 // '>'
197 static bool isOuterMostDepPositive(CharMatrix &DepMatrix, unsigned Row,
198  unsigned Column) {
199  for (unsigned i = 0; i <= Column; ++i) {
200  if (DepMatrix[Row][i] == '<')
201  return false;
202  if (DepMatrix[Row][i] == '>')
203  return true;
204  }
205  // All dependencies were '=','S' or 'I'
206  return false;
207 }
208 
209 // Checks if no dependence exist in the dependency matrix in Row before Column.
210 static bool containsNoDependence(CharMatrix &DepMatrix, unsigned Row,
211  unsigned Column) {
212  for (unsigned i = 0; i < Column; ++i) {
213  if (DepMatrix[Row][i] != '=' && DepMatrix[Row][i] != 'S' &&
214  DepMatrix[Row][i] != 'I')
215  return false;
216  }
217  return true;
218 }
219 
220 static bool validDepInterchange(CharMatrix &DepMatrix, unsigned Row,
221  unsigned OuterLoopId, char InnerDep,
222  char OuterDep) {
223  if (isOuterMostDepPositive(DepMatrix, Row, OuterLoopId))
224  return false;
225 
226  if (InnerDep == OuterDep)
227  return true;
228 
229  // It is legal to interchange if and only if after interchange no row has a
230  // '>' direction as the leftmost non-'='.
231 
232  if (InnerDep == '=' || InnerDep == 'S' || InnerDep == 'I')
233  return true;
234 
235  if (InnerDep == '<')
236  return true;
237 
238  if (InnerDep == '>') {
239  // If OuterLoopId represents outermost loop then interchanging will make the
240  // 1st dependency as '>'
241  if (OuterLoopId == 0)
242  return false;
243 
244  // If all dependencies before OuterloopId are '=','S'or 'I'. Then
245  // interchanging will result in this row having an outermost non '='
246  // dependency of '>'
247  if (!containsNoDependence(DepMatrix, Row, OuterLoopId))
248  return true;
249  }
250 
251  return false;
252 }
253 
254 // Checks if it is legal to interchange 2 loops.
255 // [Theorem] A permutation of the loops in a perfect nest is legal if and only
256 // if the direction matrix, after the same permutation is applied to its
257 // columns, has no ">" direction as the leftmost non-"=" direction in any row.
258 static bool isLegalToInterChangeLoops(CharMatrix &DepMatrix,
259  unsigned InnerLoopId,
260  unsigned OuterLoopId) {
261  unsigned NumRows = DepMatrix.size();
262  // For each row check if it is valid to interchange.
263  for (unsigned Row = 0; Row < NumRows; ++Row) {
264  char InnerDep = DepMatrix[Row][InnerLoopId];
265  char OuterDep = DepMatrix[Row][OuterLoopId];
266  if (InnerDep == '*' || OuterDep == '*')
267  return false;
268  if (!validDepInterchange(DepMatrix, Row, OuterLoopId, InnerDep, OuterDep))
269  return false;
270  }
271  return true;
272 }
273 
275  LLVM_DEBUG(dbgs() << "Calling populateWorklist on Func: "
276  << L.getHeader()->getParent()->getName() << " Loop: %"
277  << L.getHeader()->getName() << '\n');
278  LoopVector LoopList;
279  Loop *CurrentLoop = &L;
280  const std::vector<Loop *> *Vec = &CurrentLoop->getSubLoops();
281  while (!Vec->empty()) {
282  // The current loop has multiple subloops in it hence it is not tightly
283  // nested.
284  // Discard all loops above it added into Worklist.
285  if (Vec->size() != 1) {
286  LoopList.clear();
287  return;
288  }
289  LoopList.push_back(CurrentLoop);
290  CurrentLoop = Vec->front();
291  Vec = &CurrentLoop->getSubLoops();
292  }
293  LoopList.push_back(CurrentLoop);
294  V.push_back(std::move(LoopList));
295 }
296 
298  PHINode *InnerIndexVar = L->getCanonicalInductionVariable();
299  if (InnerIndexVar)
300  return InnerIndexVar;
301  if (L->getLoopLatch() == nullptr || L->getLoopPredecessor() == nullptr)
302  return nullptr;
303  for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) {
304  PHINode *PhiVar = cast<PHINode>(I);
305  Type *PhiTy = PhiVar->getType();
306  if (!PhiTy->isIntegerTy() && !PhiTy->isFloatingPointTy() &&
307  !PhiTy->isPointerTy())
308  return nullptr;
309  const SCEVAddRecExpr *AddRec =
310  dyn_cast<SCEVAddRecExpr>(SE->getSCEV(PhiVar));
311  if (!AddRec || !AddRec->isAffine())
312  continue;
313  const SCEV *Step = AddRec->getStepRecurrence(*SE);
314  if (!isa<SCEVConstant>(Step))
315  continue;
316  // Found the induction variable.
317  // FIXME: Handle loops with more than one induction variable. Note that,
318  // currently, legality makes sure we have only one induction variable.
319  return PhiVar;
320  }
321  return nullptr;
322 }
323 
324 namespace {
325 
326 /// LoopInterchangeLegality checks if it is legal to interchange the loop.
327 class LoopInterchangeLegality {
328 public:
329  LoopInterchangeLegality(Loop *Outer, Loop *Inner, ScalarEvolution *SE,
330  LoopInfo *LI, DominatorTree *DT, bool PreserveLCSSA,
332  : OuterLoop(Outer), InnerLoop(Inner), SE(SE), LI(LI), DT(DT),
333  PreserveLCSSA(PreserveLCSSA), ORE(ORE) {}
334 
335  /// Check if the loops can be interchanged.
336  bool canInterchangeLoops(unsigned InnerLoopId, unsigned OuterLoopId,
337  CharMatrix &DepMatrix);
338 
339  /// Check if the loop structure is understood. We do not handle triangular
340  /// loops for now.
341  bool isLoopStructureUnderstood(PHINode *InnerInductionVar);
342 
343  bool currentLimitations();
344 
345  bool hasInnerLoopReduction() { return InnerLoopHasReduction; }
346 
347 private:
348  bool tightlyNested(Loop *Outer, Loop *Inner);
349  bool containsUnsafeInstructionsInHeader(BasicBlock *BB);
350  bool areAllUsesReductions(Instruction *Ins, Loop *L);
351  bool containsUnsafeInstructionsInLatch(BasicBlock *BB);
352  bool findInductionAndReductions(Loop *L,
353  SmallVector<PHINode *, 8> &Inductions,
354  SmallVector<PHINode *, 8> &Reductions);
355 
356  Loop *OuterLoop;
357  Loop *InnerLoop;
358 
359  ScalarEvolution *SE;
360  LoopInfo *LI;
361  DominatorTree *DT;
362  bool PreserveLCSSA;
363 
364  /// Interface to emit optimization remarks.
366 
367  bool InnerLoopHasReduction = false;
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  bool InnerLoopContainsReductions)
402  : OuterLoop(Outer), InnerLoop(Inner), SE(SE), LI(LI), DT(DT),
403  LoopExit(LoopNestExit),
404  InnerLoopHasReduction(InnerLoopContainsReductions) {}
405 
406  /// Interchange OuterLoop and InnerLoop.
407  bool transform();
408  void restructureLoops(Loop *NewInner, Loop *NewOuter,
409  BasicBlock *OrigInnerPreHeader,
410  BasicBlock *OrigOuterPreHeader);
411  void removeChildLoop(Loop *OuterLoop, Loop *InnerLoop);
412 
413 private:
414  void splitInnerLoopLatch(Instruction *);
415  void splitInnerLoopHeader();
416  bool adjustLoopLinks();
417  void adjustLoopPreheaders();
418  bool adjustLoopBranches();
419  void updateIncomingBlock(BasicBlock *CurrBlock, BasicBlock *OldPred,
420  BasicBlock *NewPred);
421 
422  Loop *OuterLoop;
423  Loop *InnerLoop;
424 
425  /// Scev analysis.
426  ScalarEvolution *SE;
427 
428  LoopInfo *LI;
429  DominatorTree *DT;
430  BasicBlock *LoopExit;
431  bool InnerLoopHasReduction;
432 };
433 
434 // Main LoopInterchange Pass.
435 struct LoopInterchange : public FunctionPass {
436  static char ID;
437  ScalarEvolution *SE = nullptr;
438  LoopInfo *LI = nullptr;
439  DependenceInfo *DI = nullptr;
440  DominatorTree *DT = nullptr;
441  bool PreserveLCSSA;
442 
443  /// Interface to emit optimization remarks.
445 
446  LoopInterchange() : FunctionPass(ID) {
448  }
449 
450  void getAnalysisUsage(AnalysisUsage &AU) const override {
459 
462  }
463 
464  bool runOnFunction(Function &F) override {
465  if (skipFunction(F))
466  return false;
467 
468  SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
469  LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
470  DI = &getAnalysis<DependenceAnalysisWrapperPass>().getDI();
471  DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
472  ORE = &getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE();
473  PreserveLCSSA = mustPreserveAnalysisID(LCSSAID);
474 
475  // Build up a worklist of loop pairs to analyze.
477 
478  for (Loop *L : *LI)
479  populateWorklist(*L, Worklist);
480 
481  LLVM_DEBUG(dbgs() << "Worklist size = " << Worklist.size() << "\n");
482  bool Changed = true;
483  while (!Worklist.empty()) {
484  LoopVector LoopList = Worklist.pop_back_val();
485  Changed = processLoopList(LoopList, F);
486  }
487  return Changed;
488  }
489 
490  bool isComputableLoopNest(LoopVector LoopList) {
491  for (Loop *L : LoopList) {
492  const SCEV *ExitCountOuter = SE->getBackedgeTakenCount(L);
493  if (ExitCountOuter == SE->getCouldNotCompute()) {
494  LLVM_DEBUG(dbgs() << "Couldn't compute backedge count\n");
495  return false;
496  }
497  if (L->getNumBackEdges() != 1) {
498  LLVM_DEBUG(dbgs() << "NumBackEdges is not equal to 1\n");
499  return false;
500  }
501  if (!L->getExitingBlock()) {
502  LLVM_DEBUG(dbgs() << "Loop doesn't have unique exit block\n");
503  return false;
504  }
505  }
506  return true;
507  }
508 
509  unsigned selectLoopForInterchange(const LoopVector &LoopList) {
510  // TODO: Add a better heuristic to select the loop to be interchanged based
511  // on the dependence matrix. Currently we select the innermost loop.
512  return LoopList.size() - 1;
513  }
514 
515  bool processLoopList(LoopVector LoopList, Function &F) {
516  bool Changed = false;
517  unsigned LoopNestDepth = LoopList.size();
518  if (LoopNestDepth < 2) {
519  LLVM_DEBUG(dbgs() << "Loop doesn't contain minimum nesting level.\n");
520  return false;
521  }
522  if (LoopNestDepth > MaxLoopNestDepth) {
523  LLVM_DEBUG(dbgs() << "Cannot handle loops of depth greater than "
524  << MaxLoopNestDepth << "\n");
525  return false;
526  }
527  if (!isComputableLoopNest(LoopList)) {
528  LLVM_DEBUG(dbgs() << "Not valid loop candidate for interchange\n");
529  return false;
530  }
531 
532  LLVM_DEBUG(dbgs() << "Processing LoopList of size = " << LoopNestDepth
533  << "\n");
534 
535  CharMatrix DependencyMatrix;
536  Loop *OuterMostLoop = *(LoopList.begin());
537  if (!populateDependencyMatrix(DependencyMatrix, LoopNestDepth,
538  OuterMostLoop, DI)) {
539  LLVM_DEBUG(dbgs() << "Populating dependency matrix failed\n");
540  return false;
541  }
542 #ifdef DUMP_DEP_MATRICIES
543  LLVM_DEBUG(dbgs() << "Dependence before interchange\n");
544  printDepMatrix(DependencyMatrix);
545 #endif
546 
547  // Get the Outermost loop exit.
548  BasicBlock *LoopNestExit = OuterMostLoop->getExitBlock();
549  if (!LoopNestExit) {
550  LLVM_DEBUG(dbgs() << "OuterMostLoop needs an unique exit block");
551  return false;
552  }
553 
554  unsigned SelecLoopId = selectLoopForInterchange(LoopList);
555  // Move the selected loop outwards to the best possible position.
556  for (unsigned i = SelecLoopId; i > 0; i--) {
557  bool Interchanged =
558  processLoop(LoopList, i, i - 1, LoopNestExit, DependencyMatrix);
559  if (!Interchanged)
560  return Changed;
561  // Loops interchanged reflect the same in LoopList
562  std::swap(LoopList[i - 1], LoopList[i]);
563 
564  // Update the DependencyMatrix
565  interChangeDependencies(DependencyMatrix, i, i - 1);
566 #ifdef DUMP_DEP_MATRICIES
567  LLVM_DEBUG(dbgs() << "Dependence after interchange\n");
568  printDepMatrix(DependencyMatrix);
569 #endif
570  Changed |= Interchanged;
571  }
572  return Changed;
573  }
574 
575  bool processLoop(LoopVector LoopList, unsigned InnerLoopId,
576  unsigned OuterLoopId, BasicBlock *LoopNestExit,
577  std::vector<std::vector<char>> &DependencyMatrix) {
578  LLVM_DEBUG(dbgs() << "Processing Inner Loop Id = " << InnerLoopId
579  << " and OuterLoopId = " << OuterLoopId << "\n");
580  Loop *InnerLoop = LoopList[InnerLoopId];
581  Loop *OuterLoop = LoopList[OuterLoopId];
582 
583  LoopInterchangeLegality LIL(OuterLoop, InnerLoop, SE, LI, DT,
584  PreserveLCSSA, ORE);
585  if (!LIL.canInterchangeLoops(InnerLoopId, OuterLoopId, DependencyMatrix)) {
586  LLVM_DEBUG(dbgs() << "Not interchanging loops. Cannot prove legality.\n");
587  return false;
588  }
589  LLVM_DEBUG(dbgs() << "Loops are legal to interchange\n");
590  LoopInterchangeProfitability LIP(OuterLoop, InnerLoop, SE, ORE);
591  if (!LIP.isProfitable(InnerLoopId, OuterLoopId, DependencyMatrix)) {
592  LLVM_DEBUG(dbgs() << "Interchanging loops not profitable.\n");
593  return false;
594  }
595 
596  ORE->emit([&]() {
597  return OptimizationRemark(DEBUG_TYPE, "Interchanged",
598  InnerLoop->getStartLoc(),
599  InnerLoop->getHeader())
600  << "Loop interchanged with enclosing loop.";
601  });
602 
603  LoopInterchangeTransform LIT(OuterLoop, InnerLoop, SE, LI, DT,
604  LoopNestExit, LIL.hasInnerLoopReduction());
605  LIT.transform();
606  LLVM_DEBUG(dbgs() << "Loops interchanged.\n");
607  LoopsInterchanged++;
608  return true;
609  }
610 };
611 
612 } // end anonymous namespace
613 
614 bool LoopInterchangeLegality::areAllUsesReductions(Instruction *Ins, Loop *L) {
615  return llvm::none_of(Ins->users(), [=](User *U) -> bool {
616  auto *UserIns = dyn_cast<PHINode>(U);
618  return !UserIns || !RecurrenceDescriptor::isReductionPHI(UserIns, L, RD);
619  });
620 }
621 
622 bool LoopInterchangeLegality::containsUnsafeInstructionsInHeader(
623  BasicBlock *BB) {
624  for (Instruction &I : *BB) {
625  // Load corresponding to reduction PHI's are safe while concluding if
626  // tightly nested.
627  if (LoadInst *L = dyn_cast<LoadInst>(&I)) {
628  if (!areAllUsesReductions(L, InnerLoop))
629  return true;
630  } else if (I.mayHaveSideEffects() || I.mayReadFromMemory())
631  return true;
632  }
633  return false;
634 }
635 
636 bool LoopInterchangeLegality::containsUnsafeInstructionsInLatch(
637  BasicBlock *BB) {
638  for (Instruction &I : *BB) {
639  // Stores corresponding to reductions are safe while concluding if tightly
640  // nested.
641  if (StoreInst *L = dyn_cast<StoreInst>(&I)) {
642  if (!isa<PHINode>(L->getOperand(0)))
643  return true;
644  } else if (I.mayHaveSideEffects() || I.mayReadFromMemory())
645  return true;
646  }
647  return false;
648 }
649 
650 bool LoopInterchangeLegality::tightlyNested(Loop *OuterLoop, Loop *InnerLoop) {
651  BasicBlock *OuterLoopHeader = OuterLoop->getHeader();
652  BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
653  BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch();
654 
655  LLVM_DEBUG(dbgs() << "Checking if loops are tightly nested\n");
656 
657  // A perfectly nested loop will not have any branch in between the outer and
658  // inner block i.e. outer header will branch to either inner preheader and
659  // outerloop latch.
660  BranchInst *OuterLoopHeaderBI =
661  dyn_cast<BranchInst>(OuterLoopHeader->getTerminator());
662  if (!OuterLoopHeaderBI)
663  return false;
664 
665  for (BasicBlock *Succ : OuterLoopHeaderBI->successors())
666  if (Succ != InnerLoopPreHeader && Succ != OuterLoopLatch)
667  return false;
668 
669  LLVM_DEBUG(dbgs() << "Checking instructions in Loop header and Loop latch\n");
670  // We do not have any basic block in between now make sure the outer header
671  // and outer loop latch doesn't contain any unsafe instructions.
672  if (containsUnsafeInstructionsInHeader(OuterLoopHeader) ||
673  containsUnsafeInstructionsInLatch(OuterLoopLatch))
674  return false;
675 
676  LLVM_DEBUG(dbgs() << "Loops are perfectly nested\n");
677  // We have a perfect loop nest.
678  return true;
679 }
680 
681 bool LoopInterchangeLegality::isLoopStructureUnderstood(
682  PHINode *InnerInduction) {
683  unsigned Num = InnerInduction->getNumOperands();
684  BasicBlock *InnerLoopPreheader = InnerLoop->getLoopPreheader();
685  for (unsigned i = 0; i < Num; ++i) {
686  Value *Val = InnerInduction->getOperand(i);
687  if (isa<Constant>(Val))
688  continue;
690  if (!I)
691  return false;
692  // TODO: Handle triangular loops.
693  // e.g. for(int i=0;i<N;i++)
694  // for(int j=i;j<N;j++)
695  unsigned IncomBlockIndx = PHINode::getIncomingValueNumForOperand(i);
696  if (InnerInduction->getIncomingBlock(IncomBlockIndx) ==
697  InnerLoopPreheader &&
698  !OuterLoop->isLoopInvariant(I)) {
699  return false;
700  }
701  }
702  return true;
703 }
704 
705 bool LoopInterchangeLegality::findInductionAndReductions(
706  Loop *L, SmallVector<PHINode *, 8> &Inductions,
707  SmallVector<PHINode *, 8> &Reductions) {
708  if (!L->getLoopLatch() || !L->getLoopPredecessor())
709  return false;
710  for (PHINode &PHI : L->getHeader()->phis()) {
713  if (InductionDescriptor::isInductionPHI(&PHI, L, SE, ID))
714  Inductions.push_back(&PHI);
715  else if (RecurrenceDescriptor::isReductionPHI(&PHI, L, RD))
716  Reductions.push_back(&PHI);
717  else {
718  LLVM_DEBUG(
719  dbgs() << "Failed to recognize PHI as an induction or reduction.\n");
720  return false;
721  }
722  }
723  return true;
724 }
725 
726 static bool containsSafePHI(BasicBlock *Block, bool isOuterLoopExitBlock) {
727  for (PHINode &PHI : Block->phis()) {
728  // Reduction lcssa phi will have only 1 incoming block that from loop latch.
729  if (PHI.getNumIncomingValues() > 1)
730  return false;
731  Instruction *Ins = dyn_cast<Instruction>(PHI.getIncomingValue(0));
732  if (!Ins)
733  return false;
734  // Incoming value for lcssa phi's in outer loop exit can only be inner loop
735  // exits lcssa phi else it would not be tightly nested.
736  if (!isa<PHINode>(Ins) && isOuterLoopExitBlock)
737  return false;
738  }
739  return true;
740 }
741 
742 // This function indicates the current limitations in the transform as a result
743 // of which we do not proceed.
744 bool LoopInterchangeLegality::currentLimitations() {
745  BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
746  BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch();
747 
748  // transform currently expects the loop latches to also be the exiting
749  // blocks.
750  if (InnerLoop->getExitingBlock() != InnerLoopLatch ||
751  OuterLoop->getExitingBlock() != OuterLoop->getLoopLatch() ||
752  !isa<BranchInst>(InnerLoopLatch->getTerminator()) ||
753  !isa<BranchInst>(OuterLoop->getLoopLatch()->getTerminator())) {
754  LLVM_DEBUG(
755  dbgs() << "Loops where the latch is not the exiting block are not"
756  << " supported currently.\n");
757  ORE->emit([&]() {
758  return OptimizationRemarkMissed(DEBUG_TYPE, "ExitingNotLatch",
759  OuterLoop->getStartLoc(),
760  OuterLoop->getHeader())
761  << "Loops where the latch is not the exiting block cannot be"
762  " interchange currently.";
763  });
764  return true;
765  }
766 
767  PHINode *InnerInductionVar;
768  SmallVector<PHINode *, 8> Inductions;
769  SmallVector<PHINode *, 8> Reductions;
770  if (!findInductionAndReductions(InnerLoop, Inductions, Reductions)) {
771  LLVM_DEBUG(
772  dbgs() << "Only inner loops with induction or reduction PHI nodes "
773  << "are supported currently.\n");
774  ORE->emit([&]() {
775  return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedPHIInner",
776  InnerLoop->getStartLoc(),
777  InnerLoop->getHeader())
778  << "Only inner loops with induction or reduction PHI nodes can be"
779  " interchange currently.";
780  });
781  return true;
782  }
783 
784  // TODO: Currently we handle only loops with 1 induction variable.
785  if (Inductions.size() != 1) {
786  LLVM_DEBUG(
787  dbgs() << "We currently only support loops with 1 induction variable."
788  << "Failed to interchange due to current limitation\n");
789  ORE->emit([&]() {
790  return OptimizationRemarkMissed(DEBUG_TYPE, "MultiInductionInner",
791  InnerLoop->getStartLoc(),
792  InnerLoop->getHeader())
793  << "Only inner loops with 1 induction variable can be "
794  "interchanged currently.";
795  });
796  return true;
797  }
798  if (Reductions.size() > 0)
799  InnerLoopHasReduction = true;
800 
801  InnerInductionVar = Inductions.pop_back_val();
802  Reductions.clear();
803  if (!findInductionAndReductions(OuterLoop, Inductions, Reductions)) {
804  LLVM_DEBUG(
805  dbgs() << "Only outer loops with induction or reduction PHI nodes "
806  << "are supported currently.\n");
807  ORE->emit([&]() {
808  return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedPHIOuter",
809  OuterLoop->getStartLoc(),
810  OuterLoop->getHeader())
811  << "Only outer loops with induction or reduction PHI nodes can be"
812  " interchanged currently.";
813  });
814  return true;
815  }
816 
817  // Outer loop cannot have reduction because then loops will not be tightly
818  // nested.
819  if (!Reductions.empty()) {
820  LLVM_DEBUG(dbgs() << "Outer loops with reductions are not supported "
821  << "currently.\n");
822  ORE->emit([&]() {
823  return OptimizationRemarkMissed(DEBUG_TYPE, "ReductionsOuter",
824  OuterLoop->getStartLoc(),
825  OuterLoop->getHeader())
826  << "Outer loops with reductions cannot be interchangeed "
827  "currently.";
828  });
829  return true;
830  }
831  // TODO: Currently we handle only loops with 1 induction variable.
832  if (Inductions.size() != 1) {
833  LLVM_DEBUG(dbgs() << "Loops with more than 1 induction variables are not "
834  << "supported currently.\n");
835  ORE->emit([&]() {
836  return OptimizationRemarkMissed(DEBUG_TYPE, "MultiIndutionOuter",
837  OuterLoop->getStartLoc(),
838  OuterLoop->getHeader())
839  << "Only outer loops with 1 induction variable can be "
840  "interchanged currently.";
841  });
842  return true;
843  }
844 
845  // TODO: Triangular loops are not handled for now.
846  if (!isLoopStructureUnderstood(InnerInductionVar)) {
847  LLVM_DEBUG(dbgs() << "Loop structure not understood by pass\n");
848  ORE->emit([&]() {
849  return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedStructureInner",
850  InnerLoop->getStartLoc(),
851  InnerLoop->getHeader())
852  << "Inner loop structure not understood currently.";
853  });
854  return true;
855  }
856 
857  // TODO: We only handle LCSSA PHI's corresponding to reduction for now.
858  BasicBlock *InnerExit = InnerLoop->getExitBlock();
859  if (!containsSafePHI(InnerExit, false)) {
860  LLVM_DEBUG(
861  dbgs() << "Can only handle LCSSA PHIs in inner loops currently.\n");
862  ORE->emit([&]() {
863  return OptimizationRemarkMissed(DEBUG_TYPE, "NoLCSSAPHIOuterInner",
864  InnerLoop->getStartLoc(),
865  InnerLoop->getHeader())
866  << "Only inner loops with LCSSA PHIs can be interchange "
867  "currently.";
868  });
869  return true;
870  }
871 
872  // TODO: Current limitation: Since we split the inner loop latch at the point
873  // were induction variable is incremented (induction.next); We cannot have
874  // more than 1 user of induction.next since it would result in broken code
875  // after split.
876  // e.g.
877  // for(i=0;i<N;i++) {
878  // for(j = 0;j<M;j++) {
879  // A[j+1][i+2] = A[j][i]+k;
880  // }
881  // }
882  Instruction *InnerIndexVarInc = nullptr;
883  if (InnerInductionVar->getIncomingBlock(0) == InnerLoopPreHeader)
884  InnerIndexVarInc =
885  dyn_cast<Instruction>(InnerInductionVar->getIncomingValue(1));
886  else
887  InnerIndexVarInc =
888  dyn_cast<Instruction>(InnerInductionVar->getIncomingValue(0));
889 
890  if (!InnerIndexVarInc) {
891  LLVM_DEBUG(
892  dbgs() << "Did not find an instruction to increment the induction "
893  << "variable.\n");
894  ORE->emit([&]() {
895  return OptimizationRemarkMissed(DEBUG_TYPE, "NoIncrementInInner",
896  InnerLoop->getStartLoc(),
897  InnerLoop->getHeader())
898  << "The inner loop does not increment the induction variable.";
899  });
900  return true;
901  }
902 
903  // Since we split the inner loop latch on this induction variable. Make sure
904  // we do not have any instruction between the induction variable and branch
905  // instruction.
906 
907  bool FoundInduction = false;
908  for (const Instruction &I :
909  llvm::reverse(InnerLoopLatch->instructionsWithoutDebug())) {
910  if (isa<BranchInst>(I) || isa<CmpInst>(I) || isa<TruncInst>(I) ||
911  isa<ZExtInst>(I))
912  continue;
913 
914  // We found an instruction. If this is not induction variable then it is not
915  // safe to split this loop latch.
916  if (!I.isIdenticalTo(InnerIndexVarInc)) {
917  LLVM_DEBUG(dbgs() << "Found unsupported instructions between induction "
918  << "variable increment and branch.\n");
919  ORE->emit([&]() {
921  DEBUG_TYPE, "UnsupportedInsBetweenInduction",
922  InnerLoop->getStartLoc(), InnerLoop->getHeader())
923  << "Found unsupported instruction between induction variable "
924  "increment and branch.";
925  });
926  return true;
927  }
928 
929  FoundInduction = true;
930  break;
931  }
932  // The loop latch ended and we didn't find the induction variable return as
933  // current limitation.
934  if (!FoundInduction) {
935  LLVM_DEBUG(dbgs() << "Did not find the induction variable.\n");
936  ORE->emit([&]() {
937  return OptimizationRemarkMissed(DEBUG_TYPE, "NoIndutionVariable",
938  InnerLoop->getStartLoc(),
939  InnerLoop->getHeader())
940  << "Did not find the induction variable.";
941  });
942  return true;
943  }
944  return false;
945 }
946 
947 // We currently support LCSSA PHI nodes in the outer loop exit, if their
948 // incoming values do not come from the outer loop latch or if the
949 // outer loop latch has a single predecessor. In that case, the value will
950 // be available if both the inner and outer loop conditions are true, which
951 // will still be true after interchanging. If we have multiple predecessor,
952 // that may not be the case, e.g. because the outer loop latch may be executed
953 // if the inner loop is not executed.
954 static bool areLoopExitPHIsSupported(Loop *OuterLoop, Loop *InnerLoop) {
955  BasicBlock *LoopNestExit = OuterLoop->getUniqueExitBlock();
956  for (PHINode &PHI : LoopNestExit->phis()) {
957  // FIXME: We currently are not able to detect floating point reductions
958  // and have to use floating point PHIs as a proxy to prevent
959  // interchanging in the presence of floating point reductions.
960  if (PHI.getType()->isFloatingPointTy())
961  return false;
962  for (unsigned i = 0; i < PHI.getNumIncomingValues(); i++) {
963  Instruction *IncomingI = dyn_cast<Instruction>(PHI.getIncomingValue(i));
964  if (!IncomingI || IncomingI->getParent() != OuterLoop->getLoopLatch())
965  continue;
966 
967  // The incoming value is defined in the outer loop latch. Currently we
968  // only support that in case the outer loop latch has a single predecessor.
969  // This guarantees that the outer loop latch is executed if and only if
970  // the inner loop is executed (because tightlyNested() guarantees that the
971  // outer loop header only branches to the inner loop or the outer loop
972  // latch).
973  // FIXME: We could weaken this logic and allow multiple predecessors,
974  // if the values are produced outside the loop latch. We would need
975  // additional logic to update the PHI nodes in the exit block as
976  // well.
977  if (OuterLoop->getLoopLatch()->getUniquePredecessor() == nullptr)
978  return false;
979  }
980  }
981  return true;
982 }
983 
984 bool LoopInterchangeLegality::canInterchangeLoops(unsigned InnerLoopId,
985  unsigned OuterLoopId,
986  CharMatrix &DepMatrix) {
987  if (!isLegalToInterChangeLoops(DepMatrix, InnerLoopId, OuterLoopId)) {
988  LLVM_DEBUG(dbgs() << "Failed interchange InnerLoopId = " << InnerLoopId
989  << " and OuterLoopId = " << OuterLoopId
990  << " due to dependence\n");
991  ORE->emit([&]() {
992  return OptimizationRemarkMissed(DEBUG_TYPE, "Dependence",
993  InnerLoop->getStartLoc(),
994  InnerLoop->getHeader())
995  << "Cannot interchange loops due to dependences.";
996  });
997  return false;
998  }
999  // Check if outer and inner loop contain legal instructions only.
1000  for (auto *BB : OuterLoop->blocks())
1001  for (Instruction &I : BB->instructionsWithoutDebug())
1002  if (CallInst *CI = dyn_cast<CallInst>(&I)) {
1003  // readnone functions do not prevent interchanging.
1004  if (CI->doesNotReadMemory())
1005  continue;
1006  LLVM_DEBUG(
1007  dbgs() << "Loops with call instructions cannot be interchanged "
1008  << "safely.");
1009  ORE->emit([&]() {
1010  return OptimizationRemarkMissed(DEBUG_TYPE, "CallInst",
1011  CI->getDebugLoc(),
1012  CI->getParent())
1013  << "Cannot interchange loops due to call instruction.";
1014  });
1015 
1016  return false;
1017  }
1018 
1019  // Create unique Preheaders if we already do not have one.
1020  BasicBlock *OuterLoopPreHeader = OuterLoop->getLoopPreheader();
1021  BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
1022 
1023  // Create a unique outer preheader -
1024  // 1) If OuterLoop preheader is not present.
1025  // 2) If OuterLoop Preheader is same as OuterLoop Header
1026  // 3) If OuterLoop Preheader is same as Header of the previous loop.
1027  // 4) If OuterLoop Preheader is Entry node.
1028  if (!OuterLoopPreHeader || OuterLoopPreHeader == OuterLoop->getHeader() ||
1029  isa<PHINode>(OuterLoopPreHeader->begin()) ||
1030  !OuterLoopPreHeader->getUniquePredecessor()) {
1031  OuterLoopPreHeader =
1032  InsertPreheaderForLoop(OuterLoop, DT, LI, PreserveLCSSA);
1033  }
1034 
1035  if (!InnerLoopPreHeader || InnerLoopPreHeader == InnerLoop->getHeader() ||
1036  InnerLoopPreHeader == OuterLoop->getHeader()) {
1037  InnerLoopPreHeader =
1038  InsertPreheaderForLoop(InnerLoop, DT, LI, PreserveLCSSA);
1039  }
1040 
1041  // TODO: The loops could not be interchanged due to current limitations in the
1042  // transform module.
1043  if (currentLimitations()) {
1044  LLVM_DEBUG(dbgs() << "Not legal because of current transform limitation\n");
1045  return false;
1046  }
1047 
1048  // Check if the loops are tightly nested.
1049  if (!tightlyNested(OuterLoop, InnerLoop)) {
1050  LLVM_DEBUG(dbgs() << "Loops not tightly nested\n");
1051  ORE->emit([&]() {
1052  return OptimizationRemarkMissed(DEBUG_TYPE, "NotTightlyNested",
1053  InnerLoop->getStartLoc(),
1054  InnerLoop->getHeader())
1055  << "Cannot interchange loops because they are not tightly "
1056  "nested.";
1057  });
1058  return false;
1059  }
1060 
1061  if (!areLoopExitPHIsSupported(OuterLoop, InnerLoop)) {
1062  LLVM_DEBUG(dbgs() << "Found unsupported PHI nodes in outer loop exit.\n");
1063  ORE->emit([&]() {
1064  return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedExitPHI",
1065  OuterLoop->getStartLoc(),
1066  OuterLoop->getHeader())
1067  << "Found unsupported PHI node in loop exit.";
1068  });
1069  return false;
1070  }
1071 
1072  return true;
1073 }
1074 
1075 int LoopInterchangeProfitability::getInstrOrderCost() {
1076  unsigned GoodOrder, BadOrder;
1077  BadOrder = GoodOrder = 0;
1078  for (BasicBlock *BB : InnerLoop->blocks()) {
1079  for (Instruction &Ins : *BB) {
1080  if (const GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(&Ins)) {
1081  unsigned NumOp = GEP->getNumOperands();
1082  bool FoundInnerInduction = false;
1083  bool FoundOuterInduction = false;
1084  for (unsigned i = 0; i < NumOp; ++i) {
1085  const SCEV *OperandVal = SE->getSCEV(GEP->getOperand(i));
1086  const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(OperandVal);
1087  if (!AR)
1088  continue;
1089 
1090  // If we find the inner induction after an outer induction e.g.
1091  // for(int i=0;i<N;i++)
1092  // for(int j=0;j<N;j++)
1093  // A[i][j] = A[i-1][j-1]+k;
1094  // then it is a good order.
1095  if (AR->getLoop() == InnerLoop) {
1096  // We found an InnerLoop induction after OuterLoop induction. It is
1097  // a good order.
1098  FoundInnerInduction = true;
1099  if (FoundOuterInduction) {
1100  GoodOrder++;
1101  break;
1102  }
1103  }
1104  // If we find the outer induction after an inner induction e.g.
1105  // for(int i=0;i<N;i++)
1106  // for(int j=0;j<N;j++)
1107  // A[j][i] = A[j-1][i-1]+k;
1108  // then it is a bad order.
1109  if (AR->getLoop() == OuterLoop) {
1110  // We found an OuterLoop induction after InnerLoop induction. It is
1111  // a bad order.
1112  FoundOuterInduction = true;
1113  if (FoundInnerInduction) {
1114  BadOrder++;
1115  break;
1116  }
1117  }
1118  }
1119  }
1120  }
1121  }
1122  return GoodOrder - BadOrder;
1123 }
1124 
1125 static bool isProfitableForVectorization(unsigned InnerLoopId,
1126  unsigned OuterLoopId,
1127  CharMatrix &DepMatrix) {
1128  // TODO: Improve this heuristic to catch more cases.
1129  // If the inner loop is loop independent or doesn't carry any dependency it is
1130  // profitable to move this to outer position.
1131  for (auto &Row : DepMatrix) {
1132  if (Row[InnerLoopId] != 'S' && Row[InnerLoopId] != 'I')
1133  return false;
1134  // TODO: We need to improve this heuristic.
1135  if (Row[OuterLoopId] != '=')
1136  return false;
1137  }
1138  // If outer loop has dependence and inner loop is loop independent then it is
1139  // profitable to interchange to enable parallelism.
1140  // If there are no dependences, interchanging will not improve anything.
1141  return !DepMatrix.empty();
1142 }
1143 
1144 bool LoopInterchangeProfitability::isProfitable(unsigned InnerLoopId,
1145  unsigned OuterLoopId,
1146  CharMatrix &DepMatrix) {
1147  // TODO: Add better profitability checks.
1148  // e.g
1149  // 1) Construct dependency matrix and move the one with no loop carried dep
1150  // inside to enable vectorization.
1151 
1152  // This is rough cost estimation algorithm. It counts the good and bad order
1153  // of induction variables in the instruction and allows reordering if number
1154  // of bad orders is more than good.
1155  int Cost = getInstrOrderCost();
1156  LLVM_DEBUG(dbgs() << "Cost = " << Cost << "\n");
1157  if (Cost < -LoopInterchangeCostThreshold)
1158  return true;
1159 
1160  // It is not profitable as per current cache profitability model. But check if
1161  // we can move this loop outside to improve parallelism.
1162  if (isProfitableForVectorization(InnerLoopId, OuterLoopId, DepMatrix))
1163  return true;
1164 
1165  ORE->emit([&]() {
1166  return OptimizationRemarkMissed(DEBUG_TYPE, "InterchangeNotProfitable",
1167  InnerLoop->getStartLoc(),
1168  InnerLoop->getHeader())
1169  << "Interchanging loops is too costly (cost="
1170  << ore::NV("Cost", Cost) << ", threshold="
1171  << ore::NV("Threshold", LoopInterchangeCostThreshold)
1172  << ") and it does not improve parallelism.";
1173  });
1174  return false;
1175 }
1176 
1177 void LoopInterchangeTransform::removeChildLoop(Loop *OuterLoop,
1178  Loop *InnerLoop) {
1179  for (Loop *L : *OuterLoop)
1180  if (L == InnerLoop) {
1181  OuterLoop->removeChildLoop(L);
1182  return;
1183  }
1184  llvm_unreachable("Couldn't find loop");
1185 }
1186 
1187 /// Update LoopInfo, after interchanging. NewInner and NewOuter refer to the
1188 /// new inner and outer loop after interchanging: NewInner is the original
1189 /// outer loop and NewOuter is the original inner loop.
1190 ///
1191 /// Before interchanging, we have the following structure
1192 /// Outer preheader
1193 // Outer header
1194 // Inner preheader
1195 // Inner header
1196 // Inner body
1197 // Inner latch
1198 // outer bbs
1199 // Outer latch
1200 //
1201 // After interchanging:
1202 // Inner preheader
1203 // Inner header
1204 // Outer preheader
1205 // Outer header
1206 // Inner body
1207 // outer bbs
1208 // Outer latch
1209 // Inner latch
1210 void LoopInterchangeTransform::restructureLoops(
1211  Loop *NewInner, Loop *NewOuter, BasicBlock *OrigInnerPreHeader,
1212  BasicBlock *OrigOuterPreHeader) {
1213  Loop *OuterLoopParent = OuterLoop->getParentLoop();
1214  // The original inner loop preheader moves from the new inner loop to
1215  // the parent loop, if there is one.
1216  NewInner->removeBlockFromLoop(OrigInnerPreHeader);
1217  LI->changeLoopFor(OrigInnerPreHeader, OuterLoopParent);
1218 
1219  // Switch the loop levels.
1220  if (OuterLoopParent) {
1221  // Remove the loop from its parent loop.
1222  removeChildLoop(OuterLoopParent, NewInner);
1223  removeChildLoop(NewInner, NewOuter);
1224  OuterLoopParent->addChildLoop(NewOuter);
1225  } else {
1226  removeChildLoop(NewInner, NewOuter);
1227  LI->changeTopLevelLoop(NewInner, NewOuter);
1228  }
1229  while (!NewOuter->empty())
1230  NewInner->addChildLoop(NewOuter->removeChildLoop(NewOuter->begin()));
1231  NewOuter->addChildLoop(NewInner);
1232 
1233  // BBs from the original inner loop.
1234  SmallVector<BasicBlock *, 8> OrigInnerBBs(NewOuter->blocks());
1235 
1236  // Add BBs from the original outer loop to the original inner loop (excluding
1237  // BBs already in inner loop)
1238  for (BasicBlock *BB : NewInner->blocks())
1239  if (LI->getLoopFor(BB) == NewInner)
1240  NewOuter->addBlockEntry(BB);
1241 
1242  // Now remove inner loop header and latch from the new inner loop and move
1243  // other BBs (the loop body) to the new inner loop.
1244  BasicBlock *OuterHeader = NewOuter->getHeader();
1245  BasicBlock *OuterLatch = NewOuter->getLoopLatch();
1246  for (BasicBlock *BB : OrigInnerBBs) {
1247  // Nothing will change for BBs in child loops.
1248  if (LI->getLoopFor(BB) != NewOuter)
1249  continue;
1250  // Remove the new outer loop header and latch from the new inner loop.
1251  if (BB == OuterHeader || BB == OuterLatch)
1252  NewInner->removeBlockFromLoop(BB);
1253  else
1254  LI->changeLoopFor(BB, NewInner);
1255  }
1256 
1257  // The preheader of the original outer loop becomes part of the new
1258  // outer loop.
1259  NewOuter->addBlockEntry(OrigOuterPreHeader);
1260  LI->changeLoopFor(OrigOuterPreHeader, NewOuter);
1261 }
1262 
1264  bool Transformed = false;
1265  Instruction *InnerIndexVar;
1266 
1267  if (InnerLoop->getSubLoops().empty()) {
1268  BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
1269  LLVM_DEBUG(dbgs() << "Calling Split Inner Loop\n");
1270  PHINode *InductionPHI = getInductionVariable(InnerLoop, SE);
1271  if (!InductionPHI) {
1272  LLVM_DEBUG(dbgs() << "Failed to find the point to split loop latch \n");
1273  return false;
1274  }
1275 
1276  if (InductionPHI->getIncomingBlock(0) == InnerLoopPreHeader)
1277  InnerIndexVar = dyn_cast<Instruction>(InductionPHI->getIncomingValue(1));
1278  else
1279  InnerIndexVar = dyn_cast<Instruction>(InductionPHI->getIncomingValue(0));
1280 
1281  // Ensure that InductionPHI is the first Phi node.
1282  if (&InductionPHI->getParent()->front() != InductionPHI)
1283  InductionPHI->moveBefore(&InductionPHI->getParent()->front());
1284 
1285  // Split at the place were the induction variable is
1286  // incremented/decremented.
1287  // TODO: This splitting logic may not work always. Fix this.
1288  splitInnerLoopLatch(InnerIndexVar);
1289  LLVM_DEBUG(dbgs() << "splitInnerLoopLatch done\n");
1290 
1291  // Splits the inner loops phi nodes out into a separate basic block.
1292  BasicBlock *InnerLoopHeader = InnerLoop->getHeader();
1293  SplitBlock(InnerLoopHeader, InnerLoopHeader->getFirstNonPHI(), DT, LI);
1294  LLVM_DEBUG(dbgs() << "splitting InnerLoopHeader done\n");
1295  }
1296 
1297  Transformed |= adjustLoopLinks();
1298  if (!Transformed) {
1299  LLVM_DEBUG(dbgs() << "adjustLoopLinks failed\n");
1300  return false;
1301  }
1302 
1303  return true;
1304 }
1305 
1306 void LoopInterchangeTransform::splitInnerLoopLatch(Instruction *Inc) {
1307  BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch();
1308  BasicBlock *InnerLoopLatchPred = InnerLoopLatch;
1309  InnerLoopLatch = SplitBlock(InnerLoopLatchPred, Inc, DT, LI);
1310 }
1311 
1312 /// \brief Move all instructions except the terminator from FromBB right before
1313 /// InsertBefore
1314 static void moveBBContents(BasicBlock *FromBB, Instruction *InsertBefore) {
1315  auto &ToList = InsertBefore->getParent()->getInstList();
1316  auto &FromList = FromBB->getInstList();
1317 
1318  ToList.splice(InsertBefore->getIterator(), FromList, FromList.begin(),
1319  FromBB->getTerminator()->getIterator());
1320 }
1321 
1322 void LoopInterchangeTransform::updateIncomingBlock(BasicBlock *CurrBlock,
1323  BasicBlock *OldPred,
1324  BasicBlock *NewPred) {
1325  for (PHINode &PHI : CurrBlock->phis()) {
1326  unsigned Num = PHI.getNumIncomingValues();
1327  for (unsigned i = 0; i < Num; ++i) {
1328  if (PHI.getIncomingBlock(i) == OldPred)
1329  PHI.setIncomingBlock(i, NewPred);
1330  }
1331  }
1332 }
1333 
1334 /// Update BI to jump to NewBB instead of OldBB. Records updates to
1335 /// the dominator tree in DTUpdates, if DT should be preserved.
1336 static void updateSuccessor(BranchInst *BI, BasicBlock *OldBB,
1337  BasicBlock *NewBB,
1338  std::vector<DominatorTree::UpdateType> &DTUpdates) {
1340  [OldBB](BasicBlock *BB) { return BB == OldBB; }) < 2 &&
1341  "BI must jump to OldBB at most once.");
1342  for (unsigned i = 0, e = BI->getNumSuccessors(); i < e; ++i) {
1343  if (BI->getSuccessor(i) == OldBB) {
1344  BI->setSuccessor(i, NewBB);
1345 
1346  DTUpdates.push_back(
1348  DTUpdates.push_back(
1350  break;
1351  }
1352  }
1353 }
1354 
1355 bool LoopInterchangeTransform::adjustLoopBranches() {
1356  LLVM_DEBUG(dbgs() << "adjustLoopBranches called\n");
1357  std::vector<DominatorTree::UpdateType> DTUpdates;
1358 
1359  // Adjust the loop preheader
1360  BasicBlock *InnerLoopHeader = InnerLoop->getHeader();
1361  BasicBlock *OuterLoopHeader = OuterLoop->getHeader();
1362  BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch();
1363  BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch();
1364  BasicBlock *OuterLoopPreHeader = OuterLoop->getLoopPreheader();
1365  BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
1366  BasicBlock *OuterLoopPredecessor = OuterLoopPreHeader->getUniquePredecessor();
1367  BasicBlock *InnerLoopLatchPredecessor =
1368  InnerLoopLatch->getUniquePredecessor();
1369  BasicBlock *InnerLoopLatchSuccessor;
1370  BasicBlock *OuterLoopLatchSuccessor;
1371 
1372  BranchInst *OuterLoopLatchBI =
1373  dyn_cast<BranchInst>(OuterLoopLatch->getTerminator());
1374  BranchInst *InnerLoopLatchBI =
1375  dyn_cast<BranchInst>(InnerLoopLatch->getTerminator());
1376  BranchInst *OuterLoopHeaderBI =
1377  dyn_cast<BranchInst>(OuterLoopHeader->getTerminator());
1378  BranchInst *InnerLoopHeaderBI =
1379  dyn_cast<BranchInst>(InnerLoopHeader->getTerminator());
1380 
1381  if (!OuterLoopPredecessor || !InnerLoopLatchPredecessor ||
1382  !OuterLoopLatchBI || !InnerLoopLatchBI || !OuterLoopHeaderBI ||
1383  !InnerLoopHeaderBI)
1384  return false;
1385 
1386  BranchInst *InnerLoopLatchPredecessorBI =
1387  dyn_cast<BranchInst>(InnerLoopLatchPredecessor->getTerminator());
1388  BranchInst *OuterLoopPredecessorBI =
1389  dyn_cast<BranchInst>(OuterLoopPredecessor->getTerminator());
1390 
1391  if (!OuterLoopPredecessorBI || !InnerLoopLatchPredecessorBI)
1392  return false;
1393  BasicBlock *InnerLoopHeaderSuccessor = InnerLoopHeader->getUniqueSuccessor();
1394  if (!InnerLoopHeaderSuccessor)
1395  return false;
1396 
1397  // Adjust Loop Preheader and headers
1398  updateSuccessor(OuterLoopPredecessorBI, OuterLoopPreHeader,
1399  InnerLoopPreHeader, DTUpdates);
1400  updateSuccessor(OuterLoopHeaderBI, OuterLoopLatch, LoopExit, DTUpdates);
1401  updateSuccessor(OuterLoopHeaderBI, InnerLoopPreHeader,
1402  InnerLoopHeaderSuccessor, DTUpdates);
1403 
1404  // Adjust reduction PHI's now that the incoming block has changed.
1405  updateIncomingBlock(InnerLoopHeaderSuccessor, InnerLoopHeader,
1406  OuterLoopHeader);
1407 
1408  updateSuccessor(InnerLoopHeaderBI, InnerLoopHeaderSuccessor,
1409  OuterLoopPreHeader, DTUpdates);
1410 
1411  // -------------Adjust loop latches-----------
1412  if (InnerLoopLatchBI->getSuccessor(0) == InnerLoopHeader)
1413  InnerLoopLatchSuccessor = InnerLoopLatchBI->getSuccessor(1);
1414  else
1415  InnerLoopLatchSuccessor = InnerLoopLatchBI->getSuccessor(0);
1416 
1417  updateSuccessor(InnerLoopLatchPredecessorBI, InnerLoopLatch,
1418  InnerLoopLatchSuccessor, DTUpdates);
1419 
1420  // Adjust PHI nodes in InnerLoopLatchSuccessor. Update all uses of PHI with
1421  // the value and remove this PHI node from inner loop.
1422  SmallVector<PHINode *, 8> LcssaVec;
1423  for (PHINode &P : InnerLoopLatchSuccessor->phis())
1424  LcssaVec.push_back(&P);
1425 
1426  for (PHINode *P : LcssaVec) {
1427  Value *Incoming = P->getIncomingValueForBlock(InnerLoopLatch);
1428  P->replaceAllUsesWith(Incoming);
1429  P->eraseFromParent();
1430  }
1431 
1432  if (OuterLoopLatchBI->getSuccessor(0) == OuterLoopHeader)
1433  OuterLoopLatchSuccessor = OuterLoopLatchBI->getSuccessor(1);
1434  else
1435  OuterLoopLatchSuccessor = OuterLoopLatchBI->getSuccessor(0);
1436 
1437  updateSuccessor(InnerLoopLatchBI, InnerLoopLatchSuccessor,
1438  OuterLoopLatchSuccessor, DTUpdates);
1439  updateSuccessor(OuterLoopLatchBI, OuterLoopLatchSuccessor, InnerLoopLatch,
1440  DTUpdates);
1441 
1442  updateIncomingBlock(OuterLoopLatchSuccessor, OuterLoopLatch, InnerLoopLatch);
1443 
1444  DT->applyUpdates(DTUpdates);
1445  restructureLoops(OuterLoop, InnerLoop, InnerLoopPreHeader,
1446  OuterLoopPreHeader);
1447 
1448  // Now update the reduction PHIs in the inner and outer loop headers.
1449  SmallVector<PHINode *, 4> InnerLoopPHIs, OuterLoopPHIs;
1450  for (PHINode &PHI : drop_begin(InnerLoopHeader->phis(), 1))
1451  InnerLoopPHIs.push_back(cast<PHINode>(&PHI));
1452  for (PHINode &PHI : drop_begin(OuterLoopHeader->phis(), 1))
1453  OuterLoopPHIs.push_back(cast<PHINode>(&PHI));
1454 
1455  for (PHINode *PHI : OuterLoopPHIs)
1456  PHI->moveBefore(InnerLoopHeader->getFirstNonPHI());
1457 
1458  // Move the PHI nodes from the inner loop header to the outer loop header.
1459  // We have to deal with one kind of PHI nodes:
1460  // 1) PHI nodes that are part of inner loop-only reductions.
1461  // We only have to move the PHI node and update the incoming blocks.
1462  for (PHINode *PHI : InnerLoopPHIs) {
1463  PHI->moveBefore(OuterLoopHeader->getFirstNonPHI());
1464  for (BasicBlock *InBB : PHI->blocks()) {
1465  if (InnerLoop->contains(InBB))
1466  continue;
1467 
1468  assert(!isa<PHINode>(PHI->getIncomingValueForBlock(InBB)) &&
1469  "Unexpected incoming PHI node, reductions in outer loop are not "
1470  "supported yet");
1471  PHI->replaceAllUsesWith(PHI->getIncomingValueForBlock(InBB));
1472  PHI->eraseFromParent();
1473  break;
1474  }
1475  }
1476 
1477  // Update the incoming blocks for moved PHI nodes.
1478  updateIncomingBlock(OuterLoopHeader, InnerLoopPreHeader, OuterLoopPreHeader);
1479  updateIncomingBlock(OuterLoopHeader, InnerLoopLatch, OuterLoopLatch);
1480  updateIncomingBlock(InnerLoopHeader, OuterLoopPreHeader, InnerLoopPreHeader);
1481  updateIncomingBlock(InnerLoopHeader, OuterLoopLatch, InnerLoopLatch);
1482 
1483  return true;
1484 }
1485 
1486 void LoopInterchangeTransform::adjustLoopPreheaders() {
1487  // We have interchanged the preheaders so we need to interchange the data in
1488  // the preheader as well.
1489  // This is because the content of inner preheader was previously executed
1490  // inside the outer loop.
1491  BasicBlock *OuterLoopPreHeader = OuterLoop->getLoopPreheader();
1492  BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
1493  BasicBlock *OuterLoopHeader = OuterLoop->getHeader();
1494  BranchInst *InnerTermBI =
1495  cast<BranchInst>(InnerLoopPreHeader->getTerminator());
1496 
1497  // These instructions should now be executed inside the loop.
1498  // Move instruction into a new block after outer header.
1499  moveBBContents(InnerLoopPreHeader, OuterLoopHeader->getTerminator());
1500  // These instructions were not executed previously in the loop so move them to
1501  // the older inner loop preheader.
1502  moveBBContents(OuterLoopPreHeader, InnerTermBI);
1503 }
1504 
1505 bool LoopInterchangeTransform::adjustLoopLinks() {
1506  // Adjust all branches in the inner and outer loop.
1507  bool Changed = adjustLoopBranches();
1508  if (Changed)
1509  adjustLoopPreheaders();
1510  return Changed;
1511 }
1512 
1513 char LoopInterchange::ID = 0;
1514 
1515 INITIALIZE_PASS_BEGIN(LoopInterchange, "loop-interchange",
1516  "Interchanges loops for cache reuse", false, false)
1521 INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
1522 INITIALIZE_PASS_DEPENDENCY(LCSSAWrapperPass)
1525 
1526 INITIALIZE_PASS_END(LoopInterchange, "loop-interchange",
1527  "Interchanges loops for cache reuse", false, false)
1528 
1529 Pass *llvm::createLoopInterchangePass() { return new LoopInterchange(); }
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:81
void push_back(const T &Elt)
Definition: SmallVector.h:213
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
Diagnostic information for missed-optimization remarks.
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h:225
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
DiagnosticInfoOptimizationBase::Argument NV
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
BasicBlock * SplitBlock(BasicBlock *Old, Instruction *SplitPt, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr)
Split the specified block at the specified instruction - everything before SplitPt stays in Old and e...
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.
Definition: LoopUtils.cpp:1076
LLVM_ATTRIBUTE_ALWAYS_INLINE size_type size() const
Definition: SmallVector.h:137
Legacy pass manager pass to access dependence information.
static bool isProfitableForVectorization(unsigned InnerLoopId, unsigned OuterLoopId, CharMatrix &DepMatrix)
LoopT * removeChildLoop(iterator I)
This removes the specified child from being a subloop of this loop.
Definition: LoopInfo.h:340
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:174
static bool containsNoDependence(CharMatrix &DepMatrix, unsigned Row, unsigned Column)
BasicBlock * InsertPreheaderForLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, bool PreserveLCSSA)
InsertPreheaderForLoop - Once we discover that a loop doesn&#39;t have a preheader, this method is called...
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:982
BasicBlock * getSuccessor(unsigned i) const
STATISTIC(NumFunctions, "Total number of functions")
F(f)
An instruction for reading from memory.
Definition: Instructions.h:168
Hexagon Common GEP
DependenceInfo - This class is the main dependence-analysis driver.
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:264
static bool populateDependencyMatrix(CharMatrix &DepMatrix, unsigned Level, Loop *L, DependenceInfo *DI)
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:51
unsigned getNumSuccessors() const
void addBlockEntry(BlockT *BB)
This adds a basic block directly to the basic block list.
Definition: LoopInfo.h:359
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:922
BlockT * getHeader() const
Definition: LoopInfo.h:100
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:237
static cl::opt< int > LoopInterchangeCostThreshold("loop-interchange-threshold", cl::init(0), cl::Hidden, cl::desc("Interchange if you gain more than this number"))
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:245
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:248
static bool validDepInterchange(CharMatrix &DepMatrix, unsigned Row, unsigned OuterLoopId, char InnerDep, char OuterDep)
static const unsigned MaxLoopNestDepth
An instruction for storing to memory.
Definition: Instructions.h:310
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:142
Value * getOperand(unsigned i) const
Definition: User.h:170
an instruction for type-safe pointer arithmetic to access elements of arrays and structs ...
Definition: Instructions.h:841
const SCEV * getCouldNotCompute()
succ_range successors()
Definition: InstrTypes.h:268
static bool runOnFunction(Function &F, bool PostInlining)
#define P(N)
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:410
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:189
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
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:95
This file contains the declarations for the subclasses of Constant, which represent the different fla...
const Instruction & front() const
Definition: BasicBlock.h:276
char & LCSSAID
Definition: LCSSA.cpp:423
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:329
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:285
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:82
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.
Definition: LoopUtils.cpp:546
BlockT * getExitBlock() const
If getExitBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:76
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:145
DebugLoc getStartLoc() const
Return the debug location of the start of this loop.
Definition: LoopInfo.cpp:346
iterator_range< decltype(adl_begin(std::declval< T >)))> drop_begin(T &&t, int n)
static unsigned getIncomingValueNumForOperand(unsigned i)
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:57
void setSuccessor(unsigned idx, BasicBlock *NewSucc)
bool isNegative() const
Definition: Constants.h:188
char & LoopSimplifyID
The RecurrenceDescriptor is used to identify recurrences variables in a loop.
Definition: LoopUtils.h:64
#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:202
const InstListType & getInstList() const
Return the underlying instruction list container.
Definition: BasicBlock.h:329
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:110
Iterator for intrusive lists based on ilist_node.
unsigned getNumOperands() const
Definition: User.h:192
static bool containsSafePHI(BasicBlock *Block, bool isOuterLoopExitBlock)
This is the shared class of boolean and integer constants.
Definition: Constants.h:84
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.
Definition: LoopUtils.h:254
Pass * createLoopInterchangePass()
AnalysisUsage & addRequiredID(const void *ID)
Definition: Pass.cpp:299
static void moveBBContents(BasicBlock *FromBB, Instruction *InsertBefore)
Move all instructions except the terminator from FromBB right before InsertBefore.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:861
iterator begin() const
Definition: LoopInfo.h:142
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:382
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static const unsigned MaxMemInstrCount
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:133
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:924
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:112
iterator_range< user_iterator > users()
Definition: Value.h:399
INITIALIZE_PASS_BEGIN(LoopInterchange, "loop-interchange", "Interchanges loops for cache reuse", false, false) INITIALIZE_PASS_END(LoopInterchange
LoopT * getParentLoop() const
Definition: LoopInfo.h:101
const std::vector< LoopT * > & getSubLoops() const
Return the loops contained entirely within this loop.
Definition: LoopInfo.h:131
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:331
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:62
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:459
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:224
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:108
#define I(x, y, z)
Definition: MD5.cpp:58
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
Definition: Constants.h:193
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:323
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
Definition: BasicBlock.h:320
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:396
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:990
static void populateWorklist(Loop &L, SmallVector< LoopVector, 8 > &V)
bool empty() const
Definition: LoopInfo.h:146
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:73
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
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:87
The legacy pass manager&#39;s analysis pass to compute loop information.
Definition: LoopInfo.h:964
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:49
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:254
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object...
const TerminatorInst * 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:138
#define LLVM_DEBUG(X)
Definition: Debug.h:119
for(unsigned i=Desc.getNumOperands(), e=OldMI.getNumOperands();i !=e;++i)
iterator_range< block_iterator > blocks() const
Definition: LoopInfo.h:156
BlockT * getExitingBlock() const
If getExitingBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:50
The optimization diagnostic interface.
static bool areLoopExitPHIsSupported(Loop *OuterLoop, Loop *InnerLoop)
loops
Definition: LoopInfo.cpp:719
const BasicBlock * getParent() const
Definition: Instruction.h:67
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:270