LLVM  8.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,
331  : OuterLoop(Outer), InnerLoop(Inner), SE(SE), ORE(ORE) {}
332 
333  /// Check if the loops can be interchanged.
334  bool canInterchangeLoops(unsigned InnerLoopId, unsigned OuterLoopId,
335  CharMatrix &DepMatrix);
336 
337  /// Check if the loop structure is understood. We do not handle triangular
338  /// loops for now.
339  bool isLoopStructureUnderstood(PHINode *InnerInductionVar);
340 
341  bool currentLimitations();
342 
343  bool hasInnerLoopReduction() { return InnerLoopHasReduction; }
344 
345 private:
346  bool tightlyNested(Loop *Outer, Loop *Inner);
347  bool containsUnsafeInstructionsInHeader(BasicBlock *BB);
348  bool areAllUsesReductions(Instruction *Ins, Loop *L);
349  bool containsUnsafeInstructionsInLatch(BasicBlock *BB);
350  bool findInductionAndReductions(Loop *L,
351  SmallVector<PHINode *, 8> &Inductions,
352  SmallVector<PHINode *, 8> &Reductions);
353 
354  Loop *OuterLoop;
355  Loop *InnerLoop;
356 
357  ScalarEvolution *SE;
358 
359  /// Interface to emit optimization remarks.
361 
362  bool InnerLoopHasReduction = false;
363 };
364 
365 /// LoopInterchangeProfitability checks if it is profitable to interchange the
366 /// loop.
367 class LoopInterchangeProfitability {
368 public:
369  LoopInterchangeProfitability(Loop *Outer, Loop *Inner, ScalarEvolution *SE,
371  : OuterLoop(Outer), InnerLoop(Inner), SE(SE), ORE(ORE) {}
372 
373  /// Check if the loop interchange is profitable.
374  bool isProfitable(unsigned InnerLoopId, unsigned OuterLoopId,
375  CharMatrix &DepMatrix);
376 
377 private:
378  int getInstrOrderCost();
379 
380  Loop *OuterLoop;
381  Loop *InnerLoop;
382 
383  /// Scev analysis.
384  ScalarEvolution *SE;
385 
386  /// Interface to emit optimization remarks.
388 };
389 
390 /// LoopInterchangeTransform interchanges the loop.
391 class LoopInterchangeTransform {
392 public:
393  LoopInterchangeTransform(Loop *Outer, Loop *Inner, ScalarEvolution *SE,
394  LoopInfo *LI, DominatorTree *DT,
395  BasicBlock *LoopNestExit,
396  bool InnerLoopContainsReductions)
397  : OuterLoop(Outer), InnerLoop(Inner), SE(SE), LI(LI), DT(DT),
398  LoopExit(LoopNestExit),
399  InnerLoopHasReduction(InnerLoopContainsReductions) {}
400 
401  /// Interchange OuterLoop and InnerLoop.
402  bool transform();
403  void restructureLoops(Loop *NewInner, Loop *NewOuter,
404  BasicBlock *OrigInnerPreHeader,
405  BasicBlock *OrigOuterPreHeader);
406  void removeChildLoop(Loop *OuterLoop, Loop *InnerLoop);
407 
408 private:
409  void splitInnerLoopLatch(Instruction *);
410  void splitInnerLoopHeader();
411  bool adjustLoopLinks();
412  void adjustLoopPreheaders();
413  bool adjustLoopBranches();
414  void updateIncomingBlock(BasicBlock *CurrBlock, BasicBlock *OldPred,
415  BasicBlock *NewPred);
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  bool InnerLoopHasReduction;
427 };
428 
429 // Main LoopInterchange Pass.
430 struct LoopInterchange : public FunctionPass {
431  static char ID;
432  ScalarEvolution *SE = nullptr;
433  LoopInfo *LI = nullptr;
434  DependenceInfo *DI = nullptr;
435  DominatorTree *DT = nullptr;
436  bool PreserveLCSSA;
437 
438  /// Interface to emit optimization remarks.
440 
441  LoopInterchange() : FunctionPass(ID) {
443  }
444 
445  void getAnalysisUsage(AnalysisUsage &AU) const override {
454 
458  }
459 
460  bool runOnFunction(Function &F) override {
461  if (skipFunction(F))
462  return false;
463 
464  SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
465  LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
466  DI = &getAnalysis<DependenceAnalysisWrapperPass>().getDI();
467  DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
468  ORE = &getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE();
469  PreserveLCSSA = mustPreserveAnalysisID(LCSSAID);
470 
471  // Build up a worklist of loop pairs to analyze.
473 
474  for (Loop *L : *LI)
475  populateWorklist(*L, Worklist);
476 
477  LLVM_DEBUG(dbgs() << "Worklist size = " << Worklist.size() << "\n");
478  bool Changed = true;
479  while (!Worklist.empty()) {
480  LoopVector LoopList = Worklist.pop_back_val();
481  Changed = processLoopList(LoopList, F);
482  }
483  return Changed;
484  }
485 
486  bool isComputableLoopNest(LoopVector LoopList) {
487  for (Loop *L : LoopList) {
488  const SCEV *ExitCountOuter = SE->getBackedgeTakenCount(L);
489  if (ExitCountOuter == SE->getCouldNotCompute()) {
490  LLVM_DEBUG(dbgs() << "Couldn't compute backedge count\n");
491  return false;
492  }
493  if (L->getNumBackEdges() != 1) {
494  LLVM_DEBUG(dbgs() << "NumBackEdges is not equal to 1\n");
495  return false;
496  }
497  if (!L->getExitingBlock()) {
498  LLVM_DEBUG(dbgs() << "Loop doesn't have unique exit block\n");
499  return false;
500  }
501  }
502  return true;
503  }
504 
505  unsigned selectLoopForInterchange(const LoopVector &LoopList) {
506  // TODO: Add a better heuristic to select the loop to be interchanged based
507  // on the dependence matrix. Currently we select the innermost loop.
508  return LoopList.size() - 1;
509  }
510 
511  bool processLoopList(LoopVector LoopList, Function &F) {
512  bool Changed = false;
513  unsigned LoopNestDepth = LoopList.size();
514  if (LoopNestDepth < 2) {
515  LLVM_DEBUG(dbgs() << "Loop doesn't contain minimum nesting level.\n");
516  return false;
517  }
518  if (LoopNestDepth > MaxLoopNestDepth) {
519  LLVM_DEBUG(dbgs() << "Cannot handle loops of depth greater than "
520  << MaxLoopNestDepth << "\n");
521  return false;
522  }
523  if (!isComputableLoopNest(LoopList)) {
524  LLVM_DEBUG(dbgs() << "Not valid loop candidate for interchange\n");
525  return false;
526  }
527 
528  LLVM_DEBUG(dbgs() << "Processing LoopList of size = " << LoopNestDepth
529  << "\n");
530 
531  CharMatrix DependencyMatrix;
532  Loop *OuterMostLoop = *(LoopList.begin());
533  if (!populateDependencyMatrix(DependencyMatrix, LoopNestDepth,
534  OuterMostLoop, DI)) {
535  LLVM_DEBUG(dbgs() << "Populating dependency matrix failed\n");
536  return false;
537  }
538 #ifdef DUMP_DEP_MATRICIES
539  LLVM_DEBUG(dbgs() << "Dependence before interchange\n");
540  printDepMatrix(DependencyMatrix);
541 #endif
542 
543  // Get the Outermost loop exit.
544  BasicBlock *LoopNestExit = OuterMostLoop->getExitBlock();
545  if (!LoopNestExit) {
546  LLVM_DEBUG(dbgs() << "OuterMostLoop needs an unique exit block");
547  return false;
548  }
549 
550  unsigned SelecLoopId = selectLoopForInterchange(LoopList);
551  // Move the selected loop outwards to the best possible position.
552  for (unsigned i = SelecLoopId; i > 0; i--) {
553  bool Interchanged =
554  processLoop(LoopList, i, i - 1, LoopNestExit, DependencyMatrix);
555  if (!Interchanged)
556  return Changed;
557  // Loops interchanged reflect the same in LoopList
558  std::swap(LoopList[i - 1], LoopList[i]);
559 
560  // Update the DependencyMatrix
561  interChangeDependencies(DependencyMatrix, i, i - 1);
562 #ifdef DUMP_DEP_MATRICIES
563  LLVM_DEBUG(dbgs() << "Dependence after interchange\n");
564  printDepMatrix(DependencyMatrix);
565 #endif
566  Changed |= Interchanged;
567  }
568  return Changed;
569  }
570 
571  bool processLoop(LoopVector LoopList, unsigned InnerLoopId,
572  unsigned OuterLoopId, BasicBlock *LoopNestExit,
573  std::vector<std::vector<char>> &DependencyMatrix) {
574  LLVM_DEBUG(dbgs() << "Processing Inner Loop Id = " << InnerLoopId
575  << " and OuterLoopId = " << OuterLoopId << "\n");
576  Loop *InnerLoop = LoopList[InnerLoopId];
577  Loop *OuterLoop = LoopList[OuterLoopId];
578 
579  LoopInterchangeLegality LIL(OuterLoop, InnerLoop, SE, ORE);
580  if (!LIL.canInterchangeLoops(InnerLoopId, OuterLoopId, DependencyMatrix)) {
581  LLVM_DEBUG(dbgs() << "Not interchanging loops. Cannot prove legality.\n");
582  return false;
583  }
584  LLVM_DEBUG(dbgs() << "Loops are legal to interchange\n");
585  LoopInterchangeProfitability LIP(OuterLoop, InnerLoop, SE, ORE);
586  if (!LIP.isProfitable(InnerLoopId, OuterLoopId, DependencyMatrix)) {
587  LLVM_DEBUG(dbgs() << "Interchanging loops not profitable.\n");
588  return false;
589  }
590 
591  ORE->emit([&]() {
592  return OptimizationRemark(DEBUG_TYPE, "Interchanged",
593  InnerLoop->getStartLoc(),
594  InnerLoop->getHeader())
595  << "Loop interchanged with enclosing loop.";
596  });
597 
598  LoopInterchangeTransform LIT(OuterLoop, InnerLoop, SE, LI, DT,
599  LoopNestExit, LIL.hasInnerLoopReduction());
600  LIT.transform();
601  LLVM_DEBUG(dbgs() << "Loops interchanged.\n");
602  LoopsInterchanged++;
603  return true;
604  }
605 };
606 
607 } // end anonymous namespace
608 
609 bool LoopInterchangeLegality::areAllUsesReductions(Instruction *Ins, Loop *L) {
610  return llvm::none_of(Ins->users(), [=](User *U) -> bool {
611  auto *UserIns = dyn_cast<PHINode>(U);
613  return !UserIns || !RecurrenceDescriptor::isReductionPHI(UserIns, L, RD);
614  });
615 }
616 
617 bool LoopInterchangeLegality::containsUnsafeInstructionsInHeader(
618  BasicBlock *BB) {
619  for (Instruction &I : *BB) {
620  // Load corresponding to reduction PHI's are safe while concluding if
621  // tightly nested.
622  if (LoadInst *L = dyn_cast<LoadInst>(&I)) {
623  if (!areAllUsesReductions(L, InnerLoop))
624  return true;
625  } else if (I.mayHaveSideEffects() || I.mayReadFromMemory())
626  return true;
627  }
628  return false;
629 }
630 
631 bool LoopInterchangeLegality::containsUnsafeInstructionsInLatch(
632  BasicBlock *BB) {
633  for (Instruction &I : *BB) {
634  // Stores corresponding to reductions are safe while concluding if tightly
635  // nested.
636  if (StoreInst *L = dyn_cast<StoreInst>(&I)) {
637  if (!isa<PHINode>(L->getOperand(0)))
638  return true;
639  } else if (I.mayHaveSideEffects() || I.mayReadFromMemory())
640  return true;
641  }
642  return false;
643 }
644 
645 bool LoopInterchangeLegality::tightlyNested(Loop *OuterLoop, Loop *InnerLoop) {
646  BasicBlock *OuterLoopHeader = OuterLoop->getHeader();
647  BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
648  BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch();
649 
650  LLVM_DEBUG(dbgs() << "Checking if loops are tightly nested\n");
651 
652  // A perfectly nested loop will not have any branch in between the outer and
653  // inner block i.e. outer header will branch to either inner preheader and
654  // outerloop latch.
655  BranchInst *OuterLoopHeaderBI =
656  dyn_cast<BranchInst>(OuterLoopHeader->getTerminator());
657  if (!OuterLoopHeaderBI)
658  return false;
659 
660  for (BasicBlock *Succ : successors(OuterLoopHeaderBI))
661  if (Succ != InnerLoopPreHeader && Succ != InnerLoop->getHeader() &&
662  Succ != OuterLoopLatch)
663  return false;
664 
665  LLVM_DEBUG(dbgs() << "Checking instructions in Loop header and Loop latch\n");
666  // We do not have any basic block in between now make sure the outer header
667  // and outer loop latch doesn't contain any unsafe instructions.
668  if (containsUnsafeInstructionsInHeader(OuterLoopHeader) ||
669  containsUnsafeInstructionsInLatch(OuterLoopLatch))
670  return false;
671 
672  LLVM_DEBUG(dbgs() << "Loops are perfectly nested\n");
673  // We have a perfect loop nest.
674  return true;
675 }
676 
677 bool LoopInterchangeLegality::isLoopStructureUnderstood(
678  PHINode *InnerInduction) {
679  unsigned Num = InnerInduction->getNumOperands();
680  BasicBlock *InnerLoopPreheader = InnerLoop->getLoopPreheader();
681  for (unsigned i = 0; i < Num; ++i) {
682  Value *Val = InnerInduction->getOperand(i);
683  if (isa<Constant>(Val))
684  continue;
686  if (!I)
687  return false;
688  // TODO: Handle triangular loops.
689  // e.g. for(int i=0;i<N;i++)
690  // for(int j=i;j<N;j++)
691  unsigned IncomBlockIndx = PHINode::getIncomingValueNumForOperand(i);
692  if (InnerInduction->getIncomingBlock(IncomBlockIndx) ==
693  InnerLoopPreheader &&
694  !OuterLoop->isLoopInvariant(I)) {
695  return false;
696  }
697  }
698  return true;
699 }
700 
701 bool LoopInterchangeLegality::findInductionAndReductions(
702  Loop *L, SmallVector<PHINode *, 8> &Inductions,
703  SmallVector<PHINode *, 8> &Reductions) {
704  if (!L->getLoopLatch() || !L->getLoopPredecessor())
705  return false;
706  for (PHINode &PHI : L->getHeader()->phis()) {
709  if (InductionDescriptor::isInductionPHI(&PHI, L, SE, ID))
710  Inductions.push_back(&PHI);
711  else if (RecurrenceDescriptor::isReductionPHI(&PHI, L, RD))
712  Reductions.push_back(&PHI);
713  else {
714  LLVM_DEBUG(
715  dbgs() << "Failed to recognize PHI as an induction or reduction.\n");
716  return false;
717  }
718  }
719  return true;
720 }
721 
722 static bool containsSafePHI(BasicBlock *Block, bool isOuterLoopExitBlock) {
723  for (PHINode &PHI : Block->phis()) {
724  // Reduction lcssa phi will have only 1 incoming block that from loop latch.
725  if (PHI.getNumIncomingValues() > 1)
726  return false;
727  Instruction *Ins = dyn_cast<Instruction>(PHI.getIncomingValue(0));
728  if (!Ins)
729  return false;
730  // Incoming value for lcssa phi's in outer loop exit can only be inner loop
731  // exits lcssa phi else it would not be tightly nested.
732  if (!isa<PHINode>(Ins) && isOuterLoopExitBlock)
733  return false;
734  }
735  return true;
736 }
737 
738 // This function indicates the current limitations in the transform as a result
739 // of which we do not proceed.
740 bool LoopInterchangeLegality::currentLimitations() {
741  BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
742  BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch();
743 
744  // transform currently expects the loop latches to also be the exiting
745  // blocks.
746  if (InnerLoop->getExitingBlock() != InnerLoopLatch ||
747  OuterLoop->getExitingBlock() != OuterLoop->getLoopLatch() ||
748  !isa<BranchInst>(InnerLoopLatch->getTerminator()) ||
749  !isa<BranchInst>(OuterLoop->getLoopLatch()->getTerminator())) {
750  LLVM_DEBUG(
751  dbgs() << "Loops where the latch is not the exiting block are not"
752  << " supported currently.\n");
753  ORE->emit([&]() {
754  return OptimizationRemarkMissed(DEBUG_TYPE, "ExitingNotLatch",
755  OuterLoop->getStartLoc(),
756  OuterLoop->getHeader())
757  << "Loops where the latch is not the exiting block cannot be"
758  " interchange currently.";
759  });
760  return true;
761  }
762 
763  PHINode *InnerInductionVar;
764  SmallVector<PHINode *, 8> Inductions;
765  SmallVector<PHINode *, 8> Reductions;
766  if (!findInductionAndReductions(InnerLoop, Inductions, Reductions)) {
767  LLVM_DEBUG(
768  dbgs() << "Only inner loops with induction or reduction PHI nodes "
769  << "are supported currently.\n");
770  ORE->emit([&]() {
771  return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedPHIInner",
772  InnerLoop->getStartLoc(),
773  InnerLoop->getHeader())
774  << "Only inner loops with induction or reduction PHI nodes can be"
775  " interchange currently.";
776  });
777  return true;
778  }
779 
780  // TODO: Currently we handle only loops with 1 induction variable.
781  if (Inductions.size() != 1) {
782  LLVM_DEBUG(
783  dbgs() << "We currently only support loops with 1 induction variable."
784  << "Failed to interchange due to current limitation\n");
785  ORE->emit([&]() {
786  return OptimizationRemarkMissed(DEBUG_TYPE, "MultiInductionInner",
787  InnerLoop->getStartLoc(),
788  InnerLoop->getHeader())
789  << "Only inner loops with 1 induction variable can be "
790  "interchanged currently.";
791  });
792  return true;
793  }
794  if (Reductions.size() > 0)
795  InnerLoopHasReduction = true;
796 
797  InnerInductionVar = Inductions.pop_back_val();
798  Reductions.clear();
799  if (!findInductionAndReductions(OuterLoop, Inductions, Reductions)) {
800  LLVM_DEBUG(
801  dbgs() << "Only outer loops with induction or reduction PHI nodes "
802  << "are supported currently.\n");
803  ORE->emit([&]() {
804  return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedPHIOuter",
805  OuterLoop->getStartLoc(),
806  OuterLoop->getHeader())
807  << "Only outer loops with induction or reduction PHI nodes can be"
808  " interchanged currently.";
809  });
810  return true;
811  }
812 
813  // Outer loop cannot have reduction because then loops will not be tightly
814  // nested.
815  if (!Reductions.empty()) {
816  LLVM_DEBUG(dbgs() << "Outer loops with reductions are not supported "
817  << "currently.\n");
818  ORE->emit([&]() {
819  return OptimizationRemarkMissed(DEBUG_TYPE, "ReductionsOuter",
820  OuterLoop->getStartLoc(),
821  OuterLoop->getHeader())
822  << "Outer loops with reductions cannot be interchangeed "
823  "currently.";
824  });
825  return true;
826  }
827  // TODO: Currently we handle only loops with 1 induction variable.
828  if (Inductions.size() != 1) {
829  LLVM_DEBUG(dbgs() << "Loops with more than 1 induction variables are not "
830  << "supported currently.\n");
831  ORE->emit([&]() {
832  return OptimizationRemarkMissed(DEBUG_TYPE, "MultiIndutionOuter",
833  OuterLoop->getStartLoc(),
834  OuterLoop->getHeader())
835  << "Only outer loops with 1 induction variable can be "
836  "interchanged currently.";
837  });
838  return true;
839  }
840 
841  // TODO: Triangular loops are not handled for now.
842  if (!isLoopStructureUnderstood(InnerInductionVar)) {
843  LLVM_DEBUG(dbgs() << "Loop structure not understood by pass\n");
844  ORE->emit([&]() {
845  return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedStructureInner",
846  InnerLoop->getStartLoc(),
847  InnerLoop->getHeader())
848  << "Inner loop structure not understood currently.";
849  });
850  return true;
851  }
852 
853  // TODO: We only handle LCSSA PHI's corresponding to reduction for now.
854  BasicBlock *InnerExit = InnerLoop->getExitBlock();
855  if (!containsSafePHI(InnerExit, false)) {
856  LLVM_DEBUG(
857  dbgs() << "Can only handle LCSSA PHIs in inner loops currently.\n");
858  ORE->emit([&]() {
859  return OptimizationRemarkMissed(DEBUG_TYPE, "NoLCSSAPHIOuterInner",
860  InnerLoop->getStartLoc(),
861  InnerLoop->getHeader())
862  << "Only inner loops with LCSSA PHIs can be interchange "
863  "currently.";
864  });
865  return true;
866  }
867 
868  // TODO: Current limitation: Since we split the inner loop latch at the point
869  // were induction variable is incremented (induction.next); We cannot have
870  // more than 1 user of induction.next since it would result in broken code
871  // after split.
872  // e.g.
873  // for(i=0;i<N;i++) {
874  // for(j = 0;j<M;j++) {
875  // A[j+1][i+2] = A[j][i]+k;
876  // }
877  // }
878  Instruction *InnerIndexVarInc = nullptr;
879  if (InnerInductionVar->getIncomingBlock(0) == InnerLoopPreHeader)
880  InnerIndexVarInc =
881  dyn_cast<Instruction>(InnerInductionVar->getIncomingValue(1));
882  else
883  InnerIndexVarInc =
884  dyn_cast<Instruction>(InnerInductionVar->getIncomingValue(0));
885 
886  if (!InnerIndexVarInc) {
887  LLVM_DEBUG(
888  dbgs() << "Did not find an instruction to increment the induction "
889  << "variable.\n");
890  ORE->emit([&]() {
891  return OptimizationRemarkMissed(DEBUG_TYPE, "NoIncrementInInner",
892  InnerLoop->getStartLoc(),
893  InnerLoop->getHeader())
894  << "The inner loop does not increment the induction variable.";
895  });
896  return true;
897  }
898 
899  // Since we split the inner loop latch on this induction variable. Make sure
900  // we do not have any instruction between the induction variable and branch
901  // instruction.
902 
903  bool FoundInduction = false;
904  for (const Instruction &I :
905  llvm::reverse(InnerLoopLatch->instructionsWithoutDebug())) {
906  if (isa<BranchInst>(I) || isa<CmpInst>(I) || isa<TruncInst>(I) ||
907  isa<ZExtInst>(I))
908  continue;
909 
910  // We found an instruction. If this is not induction variable then it is not
911  // safe to split this loop latch.
912  if (!I.isIdenticalTo(InnerIndexVarInc)) {
913  LLVM_DEBUG(dbgs() << "Found unsupported instructions between induction "
914  << "variable increment and branch.\n");
915  ORE->emit([&]() {
917  DEBUG_TYPE, "UnsupportedInsBetweenInduction",
918  InnerLoop->getStartLoc(), InnerLoop->getHeader())
919  << "Found unsupported instruction between induction variable "
920  "increment and branch.";
921  });
922  return true;
923  }
924 
925  FoundInduction = true;
926  break;
927  }
928  // The loop latch ended and we didn't find the induction variable return as
929  // current limitation.
930  if (!FoundInduction) {
931  LLVM_DEBUG(dbgs() << "Did not find the induction variable.\n");
932  ORE->emit([&]() {
933  return OptimizationRemarkMissed(DEBUG_TYPE, "NoIndutionVariable",
934  InnerLoop->getStartLoc(),
935  InnerLoop->getHeader())
936  << "Did not find the induction variable.";
937  });
938  return true;
939  }
940  return false;
941 }
942 
943 // We currently support LCSSA PHI nodes in the outer loop exit, if their
944 // incoming values do not come from the outer loop latch or if the
945 // outer loop latch has a single predecessor. In that case, the value will
946 // be available if both the inner and outer loop conditions are true, which
947 // will still be true after interchanging. If we have multiple predecessor,
948 // that may not be the case, e.g. because the outer loop latch may be executed
949 // if the inner loop is not executed.
950 static bool areLoopExitPHIsSupported(Loop *OuterLoop, Loop *InnerLoop) {
951  BasicBlock *LoopNestExit = OuterLoop->getUniqueExitBlock();
952  for (PHINode &PHI : LoopNestExit->phis()) {
953  // FIXME: We currently are not able to detect floating point reductions
954  // and have to use floating point PHIs as a proxy to prevent
955  // interchanging in the presence of floating point reductions.
956  if (PHI.getType()->isFloatingPointTy())
957  return false;
958  for (unsigned i = 0; i < PHI.getNumIncomingValues(); i++) {
959  Instruction *IncomingI = dyn_cast<Instruction>(PHI.getIncomingValue(i));
960  if (!IncomingI || IncomingI->getParent() != OuterLoop->getLoopLatch())
961  continue;
962 
963  // The incoming value is defined in the outer loop latch. Currently we
964  // only support that in case the outer loop latch has a single predecessor.
965  // This guarantees that the outer loop latch is executed if and only if
966  // the inner loop is executed (because tightlyNested() guarantees that the
967  // outer loop header only branches to the inner loop or the outer loop
968  // latch).
969  // FIXME: We could weaken this logic and allow multiple predecessors,
970  // if the values are produced outside the loop latch. We would need
971  // additional logic to update the PHI nodes in the exit block as
972  // well.
973  if (OuterLoop->getLoopLatch()->getUniquePredecessor() == nullptr)
974  return false;
975  }
976  }
977  return true;
978 }
979 
980 bool LoopInterchangeLegality::canInterchangeLoops(unsigned InnerLoopId,
981  unsigned OuterLoopId,
982  CharMatrix &DepMatrix) {
983  if (!isLegalToInterChangeLoops(DepMatrix, InnerLoopId, OuterLoopId)) {
984  LLVM_DEBUG(dbgs() << "Failed interchange InnerLoopId = " << InnerLoopId
985  << " and OuterLoopId = " << OuterLoopId
986  << " due to dependence\n");
987  ORE->emit([&]() {
988  return OptimizationRemarkMissed(DEBUG_TYPE, "Dependence",
989  InnerLoop->getStartLoc(),
990  InnerLoop->getHeader())
991  << "Cannot interchange loops due to dependences.";
992  });
993  return false;
994  }
995  // Check if outer and inner loop contain legal instructions only.
996  for (auto *BB : OuterLoop->blocks())
997  for (Instruction &I : BB->instructionsWithoutDebug())
998  if (CallInst *CI = dyn_cast<CallInst>(&I)) {
999  // readnone functions do not prevent interchanging.
1000  if (CI->doesNotReadMemory())
1001  continue;
1002  LLVM_DEBUG(
1003  dbgs() << "Loops with call instructions cannot be interchanged "
1004  << "safely.");
1005  ORE->emit([&]() {
1006  return OptimizationRemarkMissed(DEBUG_TYPE, "CallInst",
1007  CI->getDebugLoc(),
1008  CI->getParent())
1009  << "Cannot interchange loops due to call instruction.";
1010  });
1011 
1012  return false;
1013  }
1014 
1015  // TODO: The loops could not be interchanged due to current limitations in the
1016  // transform module.
1017  if (currentLimitations()) {
1018  LLVM_DEBUG(dbgs() << "Not legal because of current transform limitation\n");
1019  return false;
1020  }
1021 
1022  // Check if the loops are tightly nested.
1023  if (!tightlyNested(OuterLoop, InnerLoop)) {
1024  LLVM_DEBUG(dbgs() << "Loops not tightly nested\n");
1025  ORE->emit([&]() {
1026  return OptimizationRemarkMissed(DEBUG_TYPE, "NotTightlyNested",
1027  InnerLoop->getStartLoc(),
1028  InnerLoop->getHeader())
1029  << "Cannot interchange loops because they are not tightly "
1030  "nested.";
1031  });
1032  return false;
1033  }
1034 
1035  if (!areLoopExitPHIsSupported(OuterLoop, InnerLoop)) {
1036  LLVM_DEBUG(dbgs() << "Found unsupported PHI nodes in outer loop exit.\n");
1037  ORE->emit([&]() {
1038  return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedExitPHI",
1039  OuterLoop->getStartLoc(),
1040  OuterLoop->getHeader())
1041  << "Found unsupported PHI node in loop exit.";
1042  });
1043  return false;
1044  }
1045 
1046  return true;
1047 }
1048 
1049 int LoopInterchangeProfitability::getInstrOrderCost() {
1050  unsigned GoodOrder, BadOrder;
1051  BadOrder = GoodOrder = 0;
1052  for (BasicBlock *BB : InnerLoop->blocks()) {
1053  for (Instruction &Ins : *BB) {
1054  if (const GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(&Ins)) {
1055  unsigned NumOp = GEP->getNumOperands();
1056  bool FoundInnerInduction = false;
1057  bool FoundOuterInduction = false;
1058  for (unsigned i = 0; i < NumOp; ++i) {
1059  const SCEV *OperandVal = SE->getSCEV(GEP->getOperand(i));
1060  const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(OperandVal);
1061  if (!AR)
1062  continue;
1063 
1064  // If we find the inner induction after an outer induction e.g.
1065  // for(int i=0;i<N;i++)
1066  // for(int j=0;j<N;j++)
1067  // A[i][j] = A[i-1][j-1]+k;
1068  // then it is a good order.
1069  if (AR->getLoop() == InnerLoop) {
1070  // We found an InnerLoop induction after OuterLoop induction. It is
1071  // a good order.
1072  FoundInnerInduction = true;
1073  if (FoundOuterInduction) {
1074  GoodOrder++;
1075  break;
1076  }
1077  }
1078  // If we find the outer induction after an inner induction e.g.
1079  // for(int i=0;i<N;i++)
1080  // for(int j=0;j<N;j++)
1081  // A[j][i] = A[j-1][i-1]+k;
1082  // then it is a bad order.
1083  if (AR->getLoop() == OuterLoop) {
1084  // We found an OuterLoop induction after InnerLoop induction. It is
1085  // a bad order.
1086  FoundOuterInduction = true;
1087  if (FoundInnerInduction) {
1088  BadOrder++;
1089  break;
1090  }
1091  }
1092  }
1093  }
1094  }
1095  }
1096  return GoodOrder - BadOrder;
1097 }
1098 
1099 static bool isProfitableForVectorization(unsigned InnerLoopId,
1100  unsigned OuterLoopId,
1101  CharMatrix &DepMatrix) {
1102  // TODO: Improve this heuristic to catch more cases.
1103  // If the inner loop is loop independent or doesn't carry any dependency it is
1104  // profitable to move this to outer position.
1105  for (auto &Row : DepMatrix) {
1106  if (Row[InnerLoopId] != 'S' && Row[InnerLoopId] != 'I')
1107  return false;
1108  // TODO: We need to improve this heuristic.
1109  if (Row[OuterLoopId] != '=')
1110  return false;
1111  }
1112  // If outer loop has dependence and inner loop is loop independent then it is
1113  // profitable to interchange to enable parallelism.
1114  // If there are no dependences, interchanging will not improve anything.
1115  return !DepMatrix.empty();
1116 }
1117 
1118 bool LoopInterchangeProfitability::isProfitable(unsigned InnerLoopId,
1119  unsigned OuterLoopId,
1120  CharMatrix &DepMatrix) {
1121  // TODO: Add better profitability checks.
1122  // e.g
1123  // 1) Construct dependency matrix and move the one with no loop carried dep
1124  // inside to enable vectorization.
1125 
1126  // This is rough cost estimation algorithm. It counts the good and bad order
1127  // of induction variables in the instruction and allows reordering if number
1128  // of bad orders is more than good.
1129  int Cost = getInstrOrderCost();
1130  LLVM_DEBUG(dbgs() << "Cost = " << Cost << "\n");
1131  if (Cost < -LoopInterchangeCostThreshold)
1132  return true;
1133 
1134  // It is not profitable as per current cache profitability model. But check if
1135  // we can move this loop outside to improve parallelism.
1136  if (isProfitableForVectorization(InnerLoopId, OuterLoopId, DepMatrix))
1137  return true;
1138 
1139  ORE->emit([&]() {
1140  return OptimizationRemarkMissed(DEBUG_TYPE, "InterchangeNotProfitable",
1141  InnerLoop->getStartLoc(),
1142  InnerLoop->getHeader())
1143  << "Interchanging loops is too costly (cost="
1144  << ore::NV("Cost", Cost) << ", threshold="
1145  << ore::NV("Threshold", LoopInterchangeCostThreshold)
1146  << ") and it does not improve parallelism.";
1147  });
1148  return false;
1149 }
1150 
1151 void LoopInterchangeTransform::removeChildLoop(Loop *OuterLoop,
1152  Loop *InnerLoop) {
1153  for (Loop *L : *OuterLoop)
1154  if (L == InnerLoop) {
1155  OuterLoop->removeChildLoop(L);
1156  return;
1157  }
1158  llvm_unreachable("Couldn't find loop");
1159 }
1160 
1161 /// Update LoopInfo, after interchanging. NewInner and NewOuter refer to the
1162 /// new inner and outer loop after interchanging: NewInner is the original
1163 /// outer loop and NewOuter is the original inner loop.
1164 ///
1165 /// Before interchanging, we have the following structure
1166 /// Outer preheader
1167 // Outer header
1168 // Inner preheader
1169 // Inner header
1170 // Inner body
1171 // Inner latch
1172 // outer bbs
1173 // Outer latch
1174 //
1175 // After interchanging:
1176 // Inner preheader
1177 // Inner header
1178 // Outer preheader
1179 // Outer header
1180 // Inner body
1181 // outer bbs
1182 // Outer latch
1183 // Inner latch
1184 void LoopInterchangeTransform::restructureLoops(
1185  Loop *NewInner, Loop *NewOuter, BasicBlock *OrigInnerPreHeader,
1186  BasicBlock *OrigOuterPreHeader) {
1187  Loop *OuterLoopParent = OuterLoop->getParentLoop();
1188  // The original inner loop preheader moves from the new inner loop to
1189  // the parent loop, if there is one.
1190  NewInner->removeBlockFromLoop(OrigInnerPreHeader);
1191  LI->changeLoopFor(OrigInnerPreHeader, OuterLoopParent);
1192 
1193  // Switch the loop levels.
1194  if (OuterLoopParent) {
1195  // Remove the loop from its parent loop.
1196  removeChildLoop(OuterLoopParent, NewInner);
1197  removeChildLoop(NewInner, NewOuter);
1198  OuterLoopParent->addChildLoop(NewOuter);
1199  } else {
1200  removeChildLoop(NewInner, NewOuter);
1201  LI->changeTopLevelLoop(NewInner, NewOuter);
1202  }
1203  while (!NewOuter->empty())
1204  NewInner->addChildLoop(NewOuter->removeChildLoop(NewOuter->begin()));
1205  NewOuter->addChildLoop(NewInner);
1206 
1207  // BBs from the original inner loop.
1208  SmallVector<BasicBlock *, 8> OrigInnerBBs(NewOuter->blocks());
1209 
1210  // Add BBs from the original outer loop to the original inner loop (excluding
1211  // BBs already in inner loop)
1212  for (BasicBlock *BB : NewInner->blocks())
1213  if (LI->getLoopFor(BB) == NewInner)
1214  NewOuter->addBlockEntry(BB);
1215 
1216  // Now remove inner loop header and latch from the new inner loop and move
1217  // other BBs (the loop body) to the new inner loop.
1218  BasicBlock *OuterHeader = NewOuter->getHeader();
1219  BasicBlock *OuterLatch = NewOuter->getLoopLatch();
1220  for (BasicBlock *BB : OrigInnerBBs) {
1221  // Nothing will change for BBs in child loops.
1222  if (LI->getLoopFor(BB) != NewOuter)
1223  continue;
1224  // Remove the new outer loop header and latch from the new inner loop.
1225  if (BB == OuterHeader || BB == OuterLatch)
1226  NewInner->removeBlockFromLoop(BB);
1227  else
1228  LI->changeLoopFor(BB, NewInner);
1229  }
1230 
1231  // The preheader of the original outer loop becomes part of the new
1232  // outer loop.
1233  NewOuter->addBlockEntry(OrigOuterPreHeader);
1234  LI->changeLoopFor(OrigOuterPreHeader, NewOuter);
1235 
1236  // Tell SE that we move the loops around.
1237  SE->forgetLoop(NewOuter);
1238  SE->forgetLoop(NewInner);
1239 }
1240 
1242  bool Transformed = false;
1243  Instruction *InnerIndexVar;
1244 
1245  if (InnerLoop->getSubLoops().empty()) {
1246  BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
1247  LLVM_DEBUG(dbgs() << "Calling Split Inner Loop\n");
1248  PHINode *InductionPHI = getInductionVariable(InnerLoop, SE);
1249  if (!InductionPHI) {
1250  LLVM_DEBUG(dbgs() << "Failed to find the point to split loop latch \n");
1251  return false;
1252  }
1253 
1254  if (InductionPHI->getIncomingBlock(0) == InnerLoopPreHeader)
1255  InnerIndexVar = dyn_cast<Instruction>(InductionPHI->getIncomingValue(1));
1256  else
1257  InnerIndexVar = dyn_cast<Instruction>(InductionPHI->getIncomingValue(0));
1258 
1259  // Ensure that InductionPHI is the first Phi node.
1260  if (&InductionPHI->getParent()->front() != InductionPHI)
1261  InductionPHI->moveBefore(&InductionPHI->getParent()->front());
1262 
1263  // Split at the place were the induction variable is
1264  // incremented/decremented.
1265  // TODO: This splitting logic may not work always. Fix this.
1266  splitInnerLoopLatch(InnerIndexVar);
1267  LLVM_DEBUG(dbgs() << "splitInnerLoopLatch done\n");
1268 
1269  // Splits the inner loops phi nodes out into a separate basic block.
1270  BasicBlock *InnerLoopHeader = InnerLoop->getHeader();
1271  SplitBlock(InnerLoopHeader, InnerLoopHeader->getFirstNonPHI(), DT, LI);
1272  LLVM_DEBUG(dbgs() << "splitting InnerLoopHeader done\n");
1273  }
1274 
1275  Transformed |= adjustLoopLinks();
1276  if (!Transformed) {
1277  LLVM_DEBUG(dbgs() << "adjustLoopLinks failed\n");
1278  return false;
1279  }
1280 
1281  return true;
1282 }
1283 
1284 void LoopInterchangeTransform::splitInnerLoopLatch(Instruction *Inc) {
1285  BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch();
1286  BasicBlock *InnerLoopLatchPred = InnerLoopLatch;
1287  InnerLoopLatch = SplitBlock(InnerLoopLatchPred, Inc, DT, LI);
1288 }
1289 
1290 /// \brief Move all instructions except the terminator from FromBB right before
1291 /// InsertBefore
1292 static void moveBBContents(BasicBlock *FromBB, Instruction *InsertBefore) {
1293  auto &ToList = InsertBefore->getParent()->getInstList();
1294  auto &FromList = FromBB->getInstList();
1295 
1296  ToList.splice(InsertBefore->getIterator(), FromList, FromList.begin(),
1297  FromBB->getTerminator()->getIterator());
1298 }
1299 
1300 void LoopInterchangeTransform::updateIncomingBlock(BasicBlock *CurrBlock,
1301  BasicBlock *OldPred,
1302  BasicBlock *NewPred) {
1303  for (PHINode &PHI : CurrBlock->phis()) {
1304  unsigned Num = PHI.getNumIncomingValues();
1305  for (unsigned i = 0; i < Num; ++i) {
1306  if (PHI.getIncomingBlock(i) == OldPred)
1307  PHI.setIncomingBlock(i, NewPred);
1308  }
1309  }
1310 }
1311 
1312 /// Update BI to jump to NewBB instead of OldBB. Records updates to
1313 /// the dominator tree in DTUpdates, if DT should be preserved.
1314 static void updateSuccessor(BranchInst *BI, BasicBlock *OldBB,
1315  BasicBlock *NewBB,
1316  std::vector<DominatorTree::UpdateType> &DTUpdates) {
1318  [OldBB](BasicBlock *BB) { return BB == OldBB; }) < 2 &&
1319  "BI must jump to OldBB at most once.");
1320  for (unsigned i = 0, e = BI->getNumSuccessors(); i < e; ++i) {
1321  if (BI->getSuccessor(i) == OldBB) {
1322  BI->setSuccessor(i, NewBB);
1323 
1324  DTUpdates.push_back(
1326  DTUpdates.push_back(
1328  break;
1329  }
1330  }
1331 }
1332 
1333 bool LoopInterchangeTransform::adjustLoopBranches() {
1334  LLVM_DEBUG(dbgs() << "adjustLoopBranches called\n");
1335  std::vector<DominatorTree::UpdateType> DTUpdates;
1336 
1337  BasicBlock *OuterLoopPreHeader = OuterLoop->getLoopPreheader();
1338  BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
1339 
1340  assert(OuterLoopPreHeader != OuterLoop->getHeader() &&
1341  InnerLoopPreHeader != InnerLoop->getHeader() && OuterLoopPreHeader &&
1342  InnerLoopPreHeader && "Guaranteed by loop-simplify form");
1343  // Ensure that both preheaders do not contain PHI nodes and have single
1344  // predecessors. This allows us to move them easily. We use
1345  // InsertPreHeaderForLoop to create an 'extra' preheader, if the existing
1346  // preheaders do not satisfy those conditions.
1347  if (isa<PHINode>(OuterLoopPreHeader->begin()) ||
1348  !OuterLoopPreHeader->getUniquePredecessor())
1349  OuterLoopPreHeader = InsertPreheaderForLoop(OuterLoop, DT, LI, true);
1350  if (InnerLoopPreHeader == OuterLoop->getHeader())
1351  InnerLoopPreHeader = InsertPreheaderForLoop(InnerLoop, DT, LI, true);
1352 
1353  // Adjust the loop preheader
1354  BasicBlock *InnerLoopHeader = InnerLoop->getHeader();
1355  BasicBlock *OuterLoopHeader = OuterLoop->getHeader();
1356  BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch();
1357  BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch();
1358  BasicBlock *OuterLoopPredecessor = OuterLoopPreHeader->getUniquePredecessor();
1359  BasicBlock *InnerLoopLatchPredecessor =
1360  InnerLoopLatch->getUniquePredecessor();
1361  BasicBlock *InnerLoopLatchSuccessor;
1362  BasicBlock *OuterLoopLatchSuccessor;
1363 
1364  BranchInst *OuterLoopLatchBI =
1365  dyn_cast<BranchInst>(OuterLoopLatch->getTerminator());
1366  BranchInst *InnerLoopLatchBI =
1367  dyn_cast<BranchInst>(InnerLoopLatch->getTerminator());
1368  BranchInst *OuterLoopHeaderBI =
1369  dyn_cast<BranchInst>(OuterLoopHeader->getTerminator());
1370  BranchInst *InnerLoopHeaderBI =
1371  dyn_cast<BranchInst>(InnerLoopHeader->getTerminator());
1372 
1373  if (!OuterLoopPredecessor || !InnerLoopLatchPredecessor ||
1374  !OuterLoopLatchBI || !InnerLoopLatchBI || !OuterLoopHeaderBI ||
1375  !InnerLoopHeaderBI)
1376  return false;
1377 
1378  BranchInst *InnerLoopLatchPredecessorBI =
1379  dyn_cast<BranchInst>(InnerLoopLatchPredecessor->getTerminator());
1380  BranchInst *OuterLoopPredecessorBI =
1381  dyn_cast<BranchInst>(OuterLoopPredecessor->getTerminator());
1382 
1383  if (!OuterLoopPredecessorBI || !InnerLoopLatchPredecessorBI)
1384  return false;
1385  BasicBlock *InnerLoopHeaderSuccessor = InnerLoopHeader->getUniqueSuccessor();
1386  if (!InnerLoopHeaderSuccessor)
1387  return false;
1388 
1389  // Adjust Loop Preheader and headers
1390  updateSuccessor(OuterLoopPredecessorBI, OuterLoopPreHeader,
1391  InnerLoopPreHeader, DTUpdates);
1392  updateSuccessor(OuterLoopHeaderBI, OuterLoopLatch, LoopExit, DTUpdates);
1393  updateSuccessor(OuterLoopHeaderBI, InnerLoopPreHeader,
1394  InnerLoopHeaderSuccessor, DTUpdates);
1395 
1396  // Adjust reduction PHI's now that the incoming block has changed.
1397  updateIncomingBlock(InnerLoopHeaderSuccessor, InnerLoopHeader,
1398  OuterLoopHeader);
1399 
1400  updateSuccessor(InnerLoopHeaderBI, InnerLoopHeaderSuccessor,
1401  OuterLoopPreHeader, DTUpdates);
1402 
1403  // -------------Adjust loop latches-----------
1404  if (InnerLoopLatchBI->getSuccessor(0) == InnerLoopHeader)
1405  InnerLoopLatchSuccessor = InnerLoopLatchBI->getSuccessor(1);
1406  else
1407  InnerLoopLatchSuccessor = InnerLoopLatchBI->getSuccessor(0);
1408 
1409  updateSuccessor(InnerLoopLatchPredecessorBI, InnerLoopLatch,
1410  InnerLoopLatchSuccessor, DTUpdates);
1411 
1412  // Adjust PHI nodes in InnerLoopLatchSuccessor. Update all uses of PHI with
1413  // the value and remove this PHI node from inner loop.
1414  SmallVector<PHINode *, 8> LcssaVec;
1415  for (PHINode &P : InnerLoopLatchSuccessor->phis())
1416  LcssaVec.push_back(&P);
1417 
1418  for (PHINode *P : LcssaVec) {
1419  Value *Incoming = P->getIncomingValueForBlock(InnerLoopLatch);
1420  P->replaceAllUsesWith(Incoming);
1421  P->eraseFromParent();
1422  }
1423 
1424  if (OuterLoopLatchBI->getSuccessor(0) == OuterLoopHeader)
1425  OuterLoopLatchSuccessor = OuterLoopLatchBI->getSuccessor(1);
1426  else
1427  OuterLoopLatchSuccessor = OuterLoopLatchBI->getSuccessor(0);
1428 
1429  updateSuccessor(InnerLoopLatchBI, InnerLoopLatchSuccessor,
1430  OuterLoopLatchSuccessor, DTUpdates);
1431  updateSuccessor(OuterLoopLatchBI, OuterLoopLatchSuccessor, InnerLoopLatch,
1432  DTUpdates);
1433 
1434  updateIncomingBlock(OuterLoopLatchSuccessor, OuterLoopLatch, InnerLoopLatch);
1435 
1436  DT->applyUpdates(DTUpdates);
1437  restructureLoops(OuterLoop, InnerLoop, InnerLoopPreHeader,
1438  OuterLoopPreHeader);
1439 
1440  // Now update the reduction PHIs in the inner and outer loop headers.
1441  SmallVector<PHINode *, 4> InnerLoopPHIs, OuterLoopPHIs;
1442  for (PHINode &PHI : drop_begin(InnerLoopHeader->phis(), 1))
1443  InnerLoopPHIs.push_back(cast<PHINode>(&PHI));
1444  for (PHINode &PHI : drop_begin(OuterLoopHeader->phis(), 1))
1445  OuterLoopPHIs.push_back(cast<PHINode>(&PHI));
1446 
1447  for (PHINode *PHI : OuterLoopPHIs)
1448  PHI->moveBefore(InnerLoopHeader->getFirstNonPHI());
1449 
1450  // Move the PHI nodes from the inner loop header to the outer loop header.
1451  // We have to deal with one kind of PHI nodes:
1452  // 1) PHI nodes that are part of inner loop-only reductions.
1453  // We only have to move the PHI node and update the incoming blocks.
1454  for (PHINode *PHI : InnerLoopPHIs) {
1455  PHI->moveBefore(OuterLoopHeader->getFirstNonPHI());
1456  for (BasicBlock *InBB : PHI->blocks()) {
1457  if (InnerLoop->contains(InBB))
1458  continue;
1459 
1460  assert(!isa<PHINode>(PHI->getIncomingValueForBlock(InBB)) &&
1461  "Unexpected incoming PHI node, reductions in outer loop are not "
1462  "supported yet");
1463  PHI->replaceAllUsesWith(PHI->getIncomingValueForBlock(InBB));
1464  PHI->eraseFromParent();
1465  break;
1466  }
1467  }
1468 
1469  // Update the incoming blocks for moved PHI nodes.
1470  updateIncomingBlock(OuterLoopHeader, InnerLoopPreHeader, OuterLoopPreHeader);
1471  updateIncomingBlock(OuterLoopHeader, InnerLoopLatch, OuterLoopLatch);
1472  updateIncomingBlock(InnerLoopHeader, OuterLoopPreHeader, InnerLoopPreHeader);
1473  updateIncomingBlock(InnerLoopHeader, OuterLoopLatch, InnerLoopLatch);
1474 
1475  return true;
1476 }
1477 
1478 void LoopInterchangeTransform::adjustLoopPreheaders() {
1479  // We have interchanged the preheaders so we need to interchange the data in
1480  // the preheader as well.
1481  // This is because the content of inner preheader was previously executed
1482  // inside the outer loop.
1483  BasicBlock *OuterLoopPreHeader = OuterLoop->getLoopPreheader();
1484  BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
1485  BasicBlock *OuterLoopHeader = OuterLoop->getHeader();
1486  BranchInst *InnerTermBI =
1487  cast<BranchInst>(InnerLoopPreHeader->getTerminator());
1488 
1489  // These instructions should now be executed inside the loop.
1490  // Move instruction into a new block after outer header.
1491  moveBBContents(InnerLoopPreHeader, OuterLoopHeader->getTerminator());
1492  // These instructions were not executed previously in the loop so move them to
1493  // the older inner loop preheader.
1494  moveBBContents(OuterLoopPreHeader, InnerTermBI);
1495 }
1496 
1497 bool LoopInterchangeTransform::adjustLoopLinks() {
1498  // Adjust all branches in the inner and outer loop.
1499  bool Changed = adjustLoopBranches();
1500  if (Changed)
1501  adjustLoopPreheaders();
1502  return Changed;
1503 }
1504 
1505 char LoopInterchange::ID = 0;
1506 
1507 INITIALIZE_PASS_BEGIN(LoopInterchange, "loop-interchange",
1508  "Interchanges loops for cache reuse", false, false)
1513 INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
1514 INITIALIZE_PASS_DEPENDENCY(LCSSAWrapperPass)
1517 
1518 INITIALIZE_PASS_END(LoopInterchange, "loop-interchange",
1519  "Interchanges loops for cache reuse", false, false)
1520 
1521 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:218
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
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.
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:1116
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:1056
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:251
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:145
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()
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:424
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.
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:335
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:53
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:58
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: IVDescriptors.h:63
#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.
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:847
iterator begin() const
Definition: LoopInfo.h:142
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:381
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:941
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:113
iterator_range< user_iterator > users()
Definition: Value.h:400
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:56
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:1124
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.
succ_range successors(Instruction *I)
Definition: CFG.h:262
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
BasicBlock * SplitBlock(BasicBlock *Old, Instruction *SplitPt, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr)
Split the specified block at the specified instruction - everything before SplitPt stays in Old and e...
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:260
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:123
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:708
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