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/SmallVector.h"
17#include "llvm/Analysis/AliasAnalysis.h"
18#include "llvm/Analysis/AssumptionCache.h"
19#include "llvm/Analysis/BlockFrequencyInfo.h"
20#include "llvm/Analysis/CodeMetrics.h"
21#include "llvm/Analysis/DependenceAnalysis.h"
22#include "llvm/Analysis/LoopInfo.h"
23#include "llvm/Analysis/LoopIterator.h"
24#include "llvm/Analysis/LoopPass.h"
25#include "llvm/Analysis/ScalarEvolution.h"
26#include "llvm/Analysis/ScalarEvolutionExpander.h"
27#include "llvm/Analysis/ScalarEvolutionExpressions.h"
28#include "llvm/Analysis/TargetTransformInfo.h"
29#include "llvm/Analysis/ValueTracking.h"
30#include "llvm/IR/Dominators.h"
31#include "llvm/IR/Function.h"
32#include "llvm/IR/IRBuilder.h"
33#include "llvm/IR/InstIterator.h"
34#include "llvm/IR/IntrinsicInst.h"
35#include "llvm/IR/Module.h"
36#include "llvm/Pass.h"
37#include "llvm/Support/Debug.h"
38#include "llvm/Support/raw_ostream.h"
39#include "llvm/Transforms/Scalar.h"
40#include "llvm/Transforms/Utils/BasicBlockUtils.h"
41#include "llvm/Transforms/Utils/LoopUtils.h"
42#include "llvm/Transforms/Utils/SSAUpdater.h"
43using namespace llvm;
44
45#define DEBUG_TYPE "loop-interchange"
46
47namespace {
48
49typedef SmallVector<Loop *, 8> LoopVector;
50
51// TODO: Check if we can use a sparse matrix here.
52typedef std::vector<std::vector<char>> CharMatrix;
53
54// Maximum number of dependencies that can be handled in the dependency matrix.
55static const unsigned MaxMemInstrCount = 100;
56
57// Maximum loop depth supported.
58static const unsigned MaxLoopNestDepth = 10;
59
60struct LoopInterchange;
61
62#ifdef DUMP_DEP_MATRICIES
63void printDepMatrix(CharMatrix &DepMatrix) {
64  for (auto I = DepMatrix.begin(), E = DepMatrix.end(); I != E; ++I) {
65    std::vector<char> Vec = *I;
66    for (auto II = Vec.begin(), EE = Vec.end(); II != EE; ++II)
67      DEBUG(dbgs() << *II << " ");
68    DEBUG(dbgs() << "\n");
69  }
70}
71#endif
72
73static bool populateDependencyMatrix(CharMatrix &DepMatrix, unsigned Level,
74                                     Loop *L, DependenceInfo *DI) {
75  typedef SmallVector<Value *, 16> ValueVector;
76  ValueVector MemInstr;
77
78  if (Level > MaxLoopNestDepth) {
79    DEBUG(dbgs() << "Cannot handle loops of depth greater than "
80                 << MaxLoopNestDepth << "\n");
81    return false;
82  }
83
84  // For each block.
85  for (Loop::block_iterator BB = L->block_begin(), BE = L->block_end();
86       BB != BE; ++BB) {
87    // Scan the BB and collect legal loads and stores.
88    for (BasicBlock::iterator I = (*BB)->begin(), E = (*BB)->end(); I != E;
89         ++I) {
90      Instruction *Ins = dyn_cast<Instruction>(I);
91      if (!Ins)
92        return false;
93      LoadInst *Ld = dyn_cast<LoadInst>(I);
94      StoreInst *St = dyn_cast<StoreInst>(I);
95      if (!St && !Ld)
96        continue;
97      if (Ld && !Ld->isSimple())
98        return false;
99      if (St && !St->isSimple())
100        return false;
101      MemInstr.push_back(&*I);
102    }
103  }
104
105  DEBUG(dbgs() << "Found " << MemInstr.size()
106               << " Loads and Stores to analyze\n");
107
108  ValueVector::iterator I, IE, J, JE;
109
110  for (I = MemInstr.begin(), IE = MemInstr.end(); I != IE; ++I) {
111    for (J = I, JE = MemInstr.end(); J != JE; ++J) {
112      std::vector<char> Dep;
113      Instruction *Src = dyn_cast<Instruction>(*I);
114      Instruction *Des = dyn_cast<Instruction>(*J);
115      if (Src == Des)
116        continue;
117      if (isa<LoadInst>(Src) && isa<LoadInst>(Des))
118        continue;
119      if (auto D = DI->depends(Src, Des, true)) {
120        DEBUG(dbgs() << "Found Dependency between Src=" << Src << " Des=" << Des
121                     << "\n");
122        if (D->isFlow()) {
123          // TODO: Handle Flow dependence.Check if it is sufficient to populate
124          // the Dependence Matrix with the direction reversed.
125          DEBUG(dbgs() << "Flow dependence not handled");
126          return false;
127        }
128        if (D->isAnti()) {
129          DEBUG(dbgs() << "Found Anti dependence \n");
130          unsigned Levels = D->getLevels();
131          char Direction;
132          for (unsigned II = 1; II <= Levels; ++II) {
133            const SCEV *Distance = D->getDistance(II);
134            const SCEVConstant *SCEVConst =
135                dyn_cast_or_null<SCEVConstant>(Distance);
136            if (SCEVConst) {
137              const ConstantInt *CI = SCEVConst->getValue();
138              if (CI->isNegative())
139                Direction = '<';
140              else if (CI->isZero())
141                Direction = '=';
142              else
143                Direction = '>';
144              Dep.push_back(Direction);
145            } else if (D->isScalar(II)) {
146              Direction = 'S';
147              Dep.push_back(Direction);
148            } else {
149              unsigned Dir = D->getDirection(II);
150              if (Dir == Dependence::DVEntry::LT ||
151                  Dir == Dependence::DVEntry::LE)
152                Direction = '<';
153              else if (Dir == Dependence::DVEntry::GT ||
154                       Dir == Dependence::DVEntry::GE)
155                Direction = '>';
156              else if (Dir == Dependence::DVEntry::EQ)
157                Direction = '=';
158              else
159                Direction = '*';
160              Dep.push_back(Direction);
161            }
162          }
163          while (Dep.size() != Level) {
164            Dep.push_back('I');
165          }
166
167          DepMatrix.push_back(Dep);
168          if (DepMatrix.size() > MaxMemInstrCount) {
169            DEBUG(dbgs() << "Cannot handle more than " << MaxMemInstrCount
170                         << " dependencies inside loop\n");
171            return false;
172          }
173        }
174      }
175    }
176  }
177
178  // We don't have a DepMatrix to check legality return false.
179  if (DepMatrix.size() == 0)
180    return false;
181  return true;
182}
183
184// A loop is moved from index 'from' to an index 'to'. Update the Dependence
185// matrix by exchanging the two columns.
186static void interChangeDepedencies(CharMatrix &DepMatrix, unsigned FromIndx,
187                                   unsigned ToIndx) {
188  unsigned numRows = DepMatrix.size();
189  for (unsigned i = 0; i < numRows; ++i) {
190    char TmpVal = DepMatrix[i][ToIndx];
191    DepMatrix[i][ToIndx] = DepMatrix[i][FromIndx];
192    DepMatrix[i][FromIndx] = TmpVal;
193  }
194}
195
196// Checks if outermost non '=','S'or'I' dependence in the dependence matrix is
197// '>'
198static bool isOuterMostDepPositive(CharMatrix &DepMatrix, unsigned Row,
199                                   unsigned Column) {
200  for (unsigned i = 0; i <= Column; ++i) {
201    if (DepMatrix[Row][i] == '<')
202      return false;
203    if (DepMatrix[Row][i] == '>')
204      return true;
205  }
206  // All dependencies were '=','S' or 'I'
207  return false;
208}
209
210// Checks if no dependence exist in the dependency matrix in Row before Column.
211static bool containsNoDependence(CharMatrix &DepMatrix, unsigned Row,
212                                 unsigned Column) {
213  for (unsigned i = 0; i < Column; ++i) {
214    if (DepMatrix[Row][i] != '=' || DepMatrix[Row][i] != 'S' ||
215        DepMatrix[Row][i] != 'I')
216      return false;
217  }
218  return true;
219}
220
221static bool validDepInterchange(CharMatrix &DepMatrix, unsigned Row,
222                                unsigned OuterLoopId, char InnerDep,
223                                char OuterDep) {
224
225  if (isOuterMostDepPositive(DepMatrix, Row, OuterLoopId))
226    return false;
227
228  if (InnerDep == OuterDep)
229    return true;
230
231  // It is legal to interchange if and only if after interchange no row has a
232  // '>' direction as the leftmost non-'='.
233
234  if (InnerDep == '=' || InnerDep == 'S' || InnerDep == 'I')
235    return true;
236
237  if (InnerDep == '<')
238    return true;
239
240  if (InnerDep == '>') {
241    // If OuterLoopId represents outermost loop then interchanging will make the
242    // 1st dependency as '>'
243    if (OuterLoopId == 0)
244      return false;
245
246    // If all dependencies before OuterloopId are '=','S'or 'I'. Then
247    // interchanging will result in this row having an outermost non '='
248    // dependency of '>'
249    if (!containsNoDependence(DepMatrix, Row, OuterLoopId))
250      return true;
251  }
252
253  return false;
254}
255
256// Checks if it is legal to interchange 2 loops.
257// [Theorem] A permutation of the loops in a perfect nest is legal if and only
258// if
259// the direction matrix, after the same permutation is applied to its columns,
260// has no ">" direction as the leftmost non-"=" direction in any row.
261static bool isLegalToInterChangeLoops(CharMatrix &DepMatrix,
262                                      unsigned InnerLoopId,
263                                      unsigned OuterLoopId) {
264
265  unsigned NumRows = DepMatrix.size();
266  // For each row check if it is valid to interchange.
267  for (unsigned Row = 0; Row < NumRows; ++Row) {
268    char InnerDep = DepMatrix[Row][InnerLoopId];
269    char OuterDep = DepMatrix[Row][OuterLoopId];
270    if (InnerDep == '*' || OuterDep == '*')
271      return false;
272    else if (!validDepInterchange(DepMatrix, Row, OuterLoopId, InnerDep,
273                                  OuterDep))
274      return false;
275  }
276  return true;
277}
278
279static void populateWorklist(Loop &L, SmallVector<LoopVector, 8> &V) {
280
281  DEBUG(dbgs() << "Calling populateWorklist called\n");
282  LoopVector LoopList;
283  Loop *CurrentLoop = &L;
284  const std::vector<Loop *> *Vec = &CurrentLoop->getSubLoops();
285  while (!Vec->empty()) {
286    // The current loop has multiple subloops in it hence it is not tightly
287    // nested.
288    // Discard all loops above it added into Worklist.
289    if (Vec->size() != 1) {
290      LoopList.clear();
291      return;
292    }
293    LoopList.push_back(CurrentLoop);
294    CurrentLoop = Vec->front();
295    Vec = &CurrentLoop->getSubLoops();
296  }
297  LoopList.push_back(CurrentLoop);
298  V.push_back(std::move(LoopList));
299}
300
301static PHINode *getInductionVariable(Loop *L, ScalarEvolution *SE) {
302  PHINode *InnerIndexVar = L->getCanonicalInductionVariable();
303  if (InnerIndexVar)
304    return InnerIndexVar;
305  if (L->getLoopLatch() == nullptr || L->getLoopPredecessor() == nullptr)
306    return nullptr;
307  for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) {
308    PHINode *PhiVar = cast<PHINode>(I);
309    Type *PhiTy = PhiVar->getType();
310    if (!PhiTy->isIntegerTy() && !PhiTy->isFloatingPointTy() &&
311        !PhiTy->isPointerTy())
312      return nullptr;
313    const SCEVAddRecExpr *AddRec =
314        dyn_cast<SCEVAddRecExpr>(SE->getSCEV(PhiVar));
315    if (!AddRec || !AddRec->isAffine())
316      continue;
317    const SCEV *Step = AddRec->getStepRecurrence(*SE);
318    const SCEVConstant *C = dyn_cast<SCEVConstant>(Step);
319    if (!C)
320      continue;
321    // Found the induction variable.
322    // FIXME: Handle loops with more than one induction variable. Note that,
323    // currently, legality makes sure we have only one induction variable.
324    return PhiVar;
325  }
326  return nullptr;
327}
328
329/// LoopInterchangeLegality checks if it is legal to interchange the loop.
330class LoopInterchangeLegality {
331public:
332  LoopInterchangeLegality(Loop *Outer, Loop *Inner, ScalarEvolution *SE,
333                          LoopInfo *LI, DominatorTree *DT, bool PreserveLCSSA)
334      : OuterLoop(Outer), InnerLoop(Inner), SE(SE), LI(LI), DT(DT),
335        PreserveLCSSA(PreserveLCSSA), InnerLoopHasReduction(false) {}
336
337  /// Check if the loops can be interchanged.
338  bool canInterchangeLoops(unsigned InnerLoopId, unsigned OuterLoopId,
339                           CharMatrix &DepMatrix);
340  /// Check if the loop structure is understood. We do not handle triangular
341  /// loops for now.
342  bool isLoopStructureUnderstood(PHINode *InnerInductionVar);
343
344  bool currentLimitations();
345
346  bool hasInnerLoopReduction() { return InnerLoopHasReduction; }
347
348private:
349  bool tightlyNested(Loop *Outer, Loop *Inner);
350  bool containsUnsafeInstructionsInHeader(BasicBlock *BB);
351  bool areAllUsesReductions(Instruction *Ins, Loop *L);
352  bool containsUnsafeInstructionsInLatch(BasicBlock *BB);
353  bool findInductionAndReductions(Loop *L,
354                                  SmallVector<PHINode *, 8> &Inductions,
355                                  SmallVector<PHINode *, 8> &Reductions);
356  Loop *OuterLoop;
357  Loop *InnerLoop;
358
359  ScalarEvolution *SE;
360  LoopInfo *LI;
361  DominatorTree *DT;
362  bool PreserveLCSSA;
363
364  bool InnerLoopHasReduction;
365};
366
367/// LoopInterchangeProfitability checks if it is profitable to interchange the
368/// loop.
369class LoopInterchangeProfitability {
370public:
371  LoopInterchangeProfitability(Loop *Outer, Loop *Inner, ScalarEvolution *SE)
372      : OuterLoop(Outer), InnerLoop(Inner), SE(SE) {}
373
374  /// Check if the loop interchange is profitable.
375  bool isProfitable(unsigned InnerLoopId, unsigned OuterLoopId,
376                    CharMatrix &DepMatrix);
377
378private:
379  int getInstrOrderCost();
380
381  Loop *OuterLoop;
382  Loop *InnerLoop;
383
384  /// Scev analysis.
385  ScalarEvolution *SE;
386};
387
388/// LoopInterchangeTransform interchanges the loop.
389class LoopInterchangeTransform {
390public:
391  LoopInterchangeTransform(Loop *Outer, Loop *Inner, ScalarEvolution *SE,
392                           LoopInfo *LI, DominatorTree *DT,
393                           BasicBlock *LoopNestExit,
394                           bool InnerLoopContainsReductions)
395      : OuterLoop(Outer), InnerLoop(Inner), SE(SE), LI(LI), DT(DT),
396        LoopExit(LoopNestExit),
397        InnerLoopHasReduction(InnerLoopContainsReductions) {}
398
399  /// Interchange OuterLoop and InnerLoop.
400  bool transform();
401  void restructureLoops(Loop *InnerLoop, Loop *OuterLoop);
402  void removeChildLoop(Loop *OuterLoop, Loop *InnerLoop);
403
404private:
405  void splitInnerLoopLatch(Instruction *);
406  void splitInnerLoopHeader();
407  bool adjustLoopLinks();
408  void adjustLoopPreheaders();
409  bool adjustLoopBranches();
410  void updateIncomingBlock(BasicBlock *CurrBlock, BasicBlock *OldPred,
411                           BasicBlock *NewPred);
412
413  Loop *OuterLoop;
414  Loop *InnerLoop;
415
416  /// Scev analysis.
417  ScalarEvolution *SE;
418  LoopInfo *LI;
419  DominatorTree *DT;
420  BasicBlock *LoopExit;
421  bool InnerLoopHasReduction;
422};
423
424// Main LoopInterchange Pass.
425struct LoopInterchange : public FunctionPass {
426  static char ID;
427  ScalarEvolution *SE;
428  LoopInfo *LI;
429  DependenceInfo *DI;
430  DominatorTree *DT;
431  bool PreserveLCSSA;
432  LoopInterchange()
433      : FunctionPass(ID), SE(nullptr), LI(nullptr), DI(nullptr), DT(nullptr) {
434    initializeLoopInterchangePass(*PassRegistry::getPassRegistry());
435  }
436
437  void getAnalysisUsage(AnalysisUsage &AU) const override {
438    AU.addRequired<ScalarEvolutionWrapperPass>();
439    AU.addRequired<AAResultsWrapperPass>();
440    AU.addRequired<DominatorTreeWrapperPass>();
441    AU.addRequired<LoopInfoWrapperPass>();
442    AU.addRequired<DependenceAnalysisWrapperPass>();
443    AU.addRequiredID(LoopSimplifyID);
444    AU.addRequiredID(LCSSAID);
445  }
446
447  bool runOnFunction(Function &F) override {
448    if (skipFunction(F))
449      return false;
450
451    SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
452    LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
453    DI = &getAnalysis<DependenceAnalysisWrapperPass>().getDI();
454    auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();
455    DT = DTWP ? &DTWP->getDomTree() : nullptr;
456    PreserveLCSSA = mustPreserveAnalysisID(LCSSAID);
457
458    // Build up a worklist of loop pairs to analyze.
459    SmallVector<LoopVector, 8> Worklist;
460
461    for (Loop *L : *LI)
462      populateWorklist(*L, Worklist);
463
464    DEBUG(dbgs() << "Worklist size = " << Worklist.size() << "\n");
465    bool Changed = true;
466    while (!Worklist.empty()) {
467      LoopVector LoopList = Worklist.pop_back_val();
468      Changed = processLoopList(LoopList, F);
469    }
470    return Changed;
471  }
472
473  bool isComputableLoopNest(LoopVector LoopList) {
474    for (Loop *L : LoopList) {
475      const SCEV *ExitCountOuter = SE->getBackedgeTakenCount(L);
476      if (ExitCountOuter == SE->getCouldNotCompute()) {
477        DEBUG(dbgs() << "Couldn't compute Backedge count\n");
478        return false;
479      }
480      if (L->getNumBackEdges() != 1) {
481        DEBUG(dbgs() << "NumBackEdges is not equal to 1\n");
482        return false;
483      }
484      if (!L->getExitingBlock()) {
485        DEBUG(dbgs() << "Loop Doesn't have unique exit block\n");
486        return false;
487      }
488    }
489    return true;
490  }
491
492  unsigned selectLoopForInterchange(const LoopVector &LoopList) {
493    // TODO: Add a better heuristic to select the loop to be interchanged based
494    // on the dependence matrix. Currently we select the innermost loop.
495    return LoopList.size() - 1;
496  }
497
498  bool processLoopList(LoopVector LoopList, Function &F) {
499
500    bool Changed = false;
501    CharMatrix DependencyMatrix;
502    if (LoopList.size() < 2) {
503      DEBUG(dbgs() << "Loop doesn't contain minimum nesting level.\n");
504      return false;
505    }
506    if (!isComputableLoopNest(LoopList)) {
507      DEBUG(dbgs() << "Not vaild loop candidate for interchange\n");
508      return false;
509    }
510    Loop *OuterMostLoop = *(LoopList.begin());
511
512    DEBUG(dbgs() << "Processing LoopList of size = " << LoopList.size()
513                 << "\n");
514
515    if (!populateDependencyMatrix(DependencyMatrix, LoopList.size(),
516                                  OuterMostLoop, DI)) {
517      DEBUG(dbgs() << "Populating Dependency matrix failed\n");
518      return false;
519    }
520#ifdef DUMP_DEP_MATRICIES
521    DEBUG(dbgs() << "Dependence before inter change \n");
522    printDepMatrix(DependencyMatrix);
523#endif
524
525    BasicBlock *OuterMostLoopLatch = OuterMostLoop->getLoopLatch();
526    BranchInst *OuterMostLoopLatchBI =
527        dyn_cast<BranchInst>(OuterMostLoopLatch->getTerminator());
528    if (!OuterMostLoopLatchBI)
529      return false;
530
531    // Since we currently do not handle LCSSA PHI's any failure in loop
532    // condition will now branch to LoopNestExit.
533    // TODO: This should be removed once we handle LCSSA PHI nodes.
534
535    // Get the Outermost loop exit.
536    BasicBlock *LoopNestExit;
537    if (OuterMostLoopLatchBI->getSuccessor(0) == OuterMostLoop->getHeader())
538      LoopNestExit = OuterMostLoopLatchBI->getSuccessor(1);
539    else
540      LoopNestExit = OuterMostLoopLatchBI->getSuccessor(0);
541
542    if (isa<PHINode>(LoopNestExit->begin())) {
543      DEBUG(dbgs() << "PHI Nodes in loop nest exit is not handled for now "
544                      "since on failure all loops branch to loop nest exit.\n");
545      return false;
546    }
547
548    unsigned SelecLoopId = selectLoopForInterchange(LoopList);
549    // Move the selected loop outwards to the best possible position.
550    for (unsigned i = SelecLoopId; i > 0; i--) {
551      bool Interchanged =
552          processLoop(LoopList, i, i - 1, LoopNestExit, DependencyMatrix);
553      if (!Interchanged)
554        return Changed;
555      // Loops interchanged reflect the same in LoopList
556      std::swap(LoopList[i - 1], LoopList[i]);
557
558      // Update the DependencyMatrix
559      interChangeDepedencies(DependencyMatrix, i, i - 1);
560      DT->recalculate(F);
561#ifdef DUMP_DEP_MATRICIES
562      DEBUG(dbgs() << "Dependence after inter change \n");
563      printDepMatrix(DependencyMatrix);
564#endif
565      Changed |= Interchanged;
566    }
567    return Changed;
568  }
569
570  bool processLoop(LoopVector LoopList, unsigned InnerLoopId,
571                   unsigned OuterLoopId, BasicBlock *LoopNestExit,
572                   std::vector<std::vector<char>> &DependencyMatrix) {
573
574    DEBUG(dbgs() << "Processing Innder 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, LI, DT,
580                                PreserveLCSSA);
581    if (!LIL.canInterchangeLoops(InnerLoopId, OuterLoopId, DependencyMatrix)) {
582      DEBUG(dbgs() << "Not interchanging Loops. Cannot prove legality\n");
583      return false;
584    }
585    DEBUG(dbgs() << "Loops are legal to interchange\n");
586    LoopInterchangeProfitability LIP(OuterLoop, InnerLoop, SE);
587    if (!LIP.isProfitable(InnerLoopId, OuterLoopId, DependencyMatrix)) {
588      DEBUG(dbgs() << "Interchanging Loops not profitable\n");
589      return false;
590    }
591
592    LoopInterchangeTransform LIT(OuterLoop, InnerLoop, SE, LI, DT,
593                                 LoopNestExit, LIL.hasInnerLoopReduction());
594    LIT.transform();
595    DEBUG(dbgs() << "Loops interchanged\n");
596    return true;
597  }
598};
599
600} // end of namespace
601bool LoopInterchangeLegality::areAllUsesReductions(Instruction *Ins, Loop *L) {
602  return !std::any_of(Ins->user_begin(), Ins->user_end(), [=](User *U) -> bool {
603    PHINode *UserIns = dyn_cast<PHINode>(U);
604    RecurrenceDescriptor RD;
605    return !UserIns || !RecurrenceDescriptor::isReductionPHI(UserIns, L, RD);
606  });
607}
608
609bool LoopInterchangeLegality::containsUnsafeInstructionsInHeader(
610    BasicBlock *BB) {
611  for (auto I = BB->begin(), E = BB->end(); I != E; ++I) {
612    // Load corresponding to reduction PHI's are safe while concluding if
613    // tightly nested.
614    if (LoadInst *L = dyn_cast<LoadInst>(I)) {
615      if (!areAllUsesReductions(L, InnerLoop))
616        return true;
617    } else if (I->mayHaveSideEffects() || I->mayReadFromMemory())
618      return true;
619  }
620  return false;
621}
622
623bool LoopInterchangeLegality::containsUnsafeInstructionsInLatch(
624    BasicBlock *BB) {
625  for (auto I = BB->begin(), E = BB->end(); I != E; ++I) {
626    // Stores corresponding to reductions are safe while concluding if tightly
627    // nested.
628    if (StoreInst *L = dyn_cast<StoreInst>(I)) {
629      PHINode *PHI = dyn_cast<PHINode>(L->getOperand(0));
630      if (!PHI)
631        return true;
632    } else if (I->mayHaveSideEffects() || I->mayReadFromMemory())
633      return true;
634  }
635  return false;
636}
637
638bool LoopInterchangeLegality::tightlyNested(Loop *OuterLoop, Loop *InnerLoop) {
639  BasicBlock *OuterLoopHeader = OuterLoop->getHeader();
640  BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
641  BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch();
642
643  DEBUG(dbgs() << "Checking if Loops are Tightly Nested\n");
644
645  // A perfectly nested loop will not have any branch in between the outer and
646  // inner block i.e. outer header will branch to either inner preheader and
647  // outerloop latch.
648  BranchInst *outerLoopHeaderBI =
649      dyn_cast<BranchInst>(OuterLoopHeader->getTerminator());
650  if (!outerLoopHeaderBI)
651    return false;
652  unsigned num = outerLoopHeaderBI->getNumSuccessors();
653  for (unsigned i = 0; i < num; i++) {
654    if (outerLoopHeaderBI->getSuccessor(i) != InnerLoopPreHeader &&
655        outerLoopHeaderBI->getSuccessor(i) != OuterLoopLatch)
656      return false;
657  }
658
659  DEBUG(dbgs() << "Checking instructions in Loop header and Loop latch \n");
660  // We do not have any basic block in between now make sure the outer header
661  // and outer loop latch doesn't contain any unsafe instructions.
662  if (containsUnsafeInstructionsInHeader(OuterLoopHeader) ||
663      containsUnsafeInstructionsInLatch(OuterLoopLatch))
664    return false;
665
666  DEBUG(dbgs() << "Loops are perfectly nested \n");
667  // We have a perfect loop nest.
668  return true;
669}
670
671
672bool LoopInterchangeLegality::isLoopStructureUnderstood(
673    PHINode *InnerInduction) {
674
675  unsigned Num = InnerInduction->getNumOperands();
676  BasicBlock *InnerLoopPreheader = InnerLoop->getLoopPreheader();
677  for (unsigned i = 0; i < Num; ++i) {
678    Value *Val = InnerInduction->getOperand(i);
679    if (isa<Constant>(Val))
680      continue;
681    Instruction *I = dyn_cast<Instruction>(Val);
682    if (!I)
683      return false;
684    // TODO: Handle triangular loops.
685    // e.g. for(int i=0;i<N;i++)
686    //        for(int j=i;j<N;j++)
687    unsigned IncomBlockIndx = PHINode::getIncomingValueNumForOperand(i);
688    if (InnerInduction->getIncomingBlock(IncomBlockIndx) ==
689            InnerLoopPreheader &&
690        !OuterLoop->isLoopInvariant(I)) {
691      return false;
692    }
693  }
694  return true;
695}
696
697bool LoopInterchangeLegality::findInductionAndReductions(
698    Loop *L, SmallVector<PHINode *, 8> &Inductions,
699    SmallVector<PHINode *, 8> &Reductions) {
700  if (!L->getLoopLatch() || !L->getLoopPredecessor())
701    return false;
702  for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) {
703    RecurrenceDescriptor RD;
704    InductionDescriptor ID;
705    PHINode *PHI = cast<PHINode>(I);
706    if (InductionDescriptor::isInductionPHI(PHI, SE, ID))
707      Inductions.push_back(PHI);
708    else if (RecurrenceDescriptor::isReductionPHI(PHI, L, RD))
709      Reductions.push_back(PHI);
710    else {
711      DEBUG(
712          dbgs() << "Failed to recognize PHI as an induction or reduction.\n");
713      return false;
714    }
715  }
716  return true;
717}
718
719static bool containsSafePHI(BasicBlock *Block, bool isOuterLoopExitBlock) {
720  for (auto I = Block->begin(); isa<PHINode>(I); ++I) {
721    PHINode *PHI = cast<PHINode>(I);
722    // Reduction lcssa phi will have only 1 incoming block that from loop latch.
723    if (PHI->getNumIncomingValues() > 1)
724      return false;
725    Instruction *Ins = dyn_cast<Instruction>(PHI->getIncomingValue(0));
726    if (!Ins)
727      return false;
728    // Incoming value for lcssa phi's in outer loop exit can only be inner loop
729    // exits lcssa phi else it would not be tightly nested.
730    if (!isa<PHINode>(Ins) && isOuterLoopExitBlock)
731      return false;
732  }
733  return true;
734}
735
736static BasicBlock *getLoopLatchExitBlock(BasicBlock *LatchBlock,
737                                         BasicBlock *LoopHeader) {
738  if (BranchInst *BI = dyn_cast<BranchInst>(LatchBlock->getTerminator())) {
739    unsigned Num = BI->getNumSuccessors();
740    assert(Num == 2);
741    for (unsigned i = 0; i < Num; ++i) {
742      if (BI->getSuccessor(i) == LoopHeader)
743        continue;
744      return BI->getSuccessor(i);
745    }
746  }
747  return nullptr;
748}
749
750// This function indicates the current limitations in the transform as a result
751// of which we do not proceed.
752bool LoopInterchangeLegality::currentLimitations() {
753
754  BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
755  BasicBlock *InnerLoopHeader = InnerLoop->getHeader();
756  BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch();
757  BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch();
758  BasicBlock *OuterLoopHeader = OuterLoop->getHeader();
759
760  PHINode *InnerInductionVar;
761  SmallVector<PHINode *, 8> Inductions;
762  SmallVector<PHINode *, 8> Reductions;
763  if (!findInductionAndReductions(InnerLoop, Inductions, Reductions))
764    return true;
765
766  // TODO: Currently we handle only loops with 1 induction variable.
767  if (Inductions.size() != 1) {
768    DEBUG(dbgs() << "We currently only support loops with 1 induction variable."
769                 << "Failed to interchange due to current limitation\n");
770    return true;
771  }
772  if (Reductions.size() > 0)
773    InnerLoopHasReduction = true;
774
775  InnerInductionVar = Inductions.pop_back_val();
776  Reductions.clear();
777  if (!findInductionAndReductions(OuterLoop, Inductions, Reductions))
778    return true;
779
780  // Outer loop cannot have reduction because then loops will not be tightly
781  // nested.
782  if (!Reductions.empty())
783    return true;
784  // TODO: Currently we handle only loops with 1 induction variable.
785  if (Inductions.size() != 1)
786    return true;
787
788  // TODO: Triangular loops are not handled for now.
789  if (!isLoopStructureUnderstood(InnerInductionVar)) {
790    DEBUG(dbgs() << "Loop structure not understood by pass\n");
791    return true;
792  }
793
794  // TODO: We only handle LCSSA PHI's corresponding to reduction for now.
795  BasicBlock *LoopExitBlock =
796      getLoopLatchExitBlock(OuterLoopLatch, OuterLoopHeader);
797  if (!LoopExitBlock || !containsSafePHI(LoopExitBlock, true))
798    return true;
799
800  LoopExitBlock = getLoopLatchExitBlock(InnerLoopLatch, InnerLoopHeader);
801  if (!LoopExitBlock || !containsSafePHI(LoopExitBlock, false))
802    return true;
803
804  // TODO: Current limitation: Since we split the inner loop latch at the point
805  // were induction variable is incremented (induction.next); We cannot have
806  // more than 1 user of induction.next since it would result in broken code
807  // after split.
808  // e.g.
809  // for(i=0;i<N;i++) {
810  //    for(j = 0;j<M;j++) {
811  //      A[j+1][i+2] = A[j][i]+k;
812  //  }
813  // }
814  Instruction *InnerIndexVarInc = nullptr;
815  if (InnerInductionVar->getIncomingBlock(0) == InnerLoopPreHeader)
816    InnerIndexVarInc =
817        dyn_cast<Instruction>(InnerInductionVar->getIncomingValue(1));
818  else
819    InnerIndexVarInc =
820        dyn_cast<Instruction>(InnerInductionVar->getIncomingValue(0));
821
822  if (!InnerIndexVarInc)
823    return true;
824
825  // Since we split the inner loop latch on this induction variable. Make sure
826  // we do not have any instruction between the induction variable and branch
827  // instruction.
828
829  bool FoundInduction = false;
830  for (const Instruction &I : reverse(*InnerLoopLatch)) {
831    if (isa<BranchInst>(I) || isa<CmpInst>(I) || isa<TruncInst>(I))
832      continue;
833    // We found an instruction. If this is not induction variable then it is not
834    // safe to split this loop latch.
835    if (!I.isIdenticalTo(InnerIndexVarInc))
836      return true;
837
838    FoundInduction = true;
839    break;
840  }
841  // The loop latch ended and we didn't find the induction variable return as
842  // current limitation.
843  if (!FoundInduction)
844    return true;
845
846  return false;
847}
848
849bool LoopInterchangeLegality::canInterchangeLoops(unsigned InnerLoopId,
850                                                  unsigned OuterLoopId,
851                                                  CharMatrix &DepMatrix) {
852
853  if (!isLegalToInterChangeLoops(DepMatrix, InnerLoopId, OuterLoopId)) {
854    DEBUG(dbgs() << "Failed interchange InnerLoopId = " << InnerLoopId
855                 << "and OuterLoopId = " << OuterLoopId
856                 << "due to dependence\n");
857    return false;
858  }
859
860  // Create unique Preheaders if we already do not have one.
861  BasicBlock *OuterLoopPreHeader = OuterLoop->getLoopPreheader();
862  BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
863
864  // Create  a unique outer preheader -
865  // 1) If OuterLoop preheader is not present.
866  // 2) If OuterLoop Preheader is same as OuterLoop Header
867  // 3) If OuterLoop Preheader is same as Header of the previous loop.
868  // 4) If OuterLoop Preheader is Entry node.
869  if (!OuterLoopPreHeader || OuterLoopPreHeader == OuterLoop->getHeader() ||
870      isa<PHINode>(OuterLoopPreHeader->begin()) ||
871      !OuterLoopPreHeader->getUniquePredecessor()) {
872    OuterLoopPreHeader =
873        InsertPreheaderForLoop(OuterLoop, DT, LI, PreserveLCSSA);
874  }
875
876  if (!InnerLoopPreHeader || InnerLoopPreHeader == InnerLoop->getHeader() ||
877      InnerLoopPreHeader == OuterLoop->getHeader()) {
878    InnerLoopPreHeader =
879        InsertPreheaderForLoop(InnerLoop, DT, LI, PreserveLCSSA);
880  }
881
882  // TODO: The loops could not be interchanged due to current limitations in the
883  // transform module.
884  if (currentLimitations()) {
885    DEBUG(dbgs() << "Not legal because of current transform limitation\n");
886    return false;
887  }
888
889  // Check if the loops are tightly nested.
890  if (!tightlyNested(OuterLoop, InnerLoop)) {
891    DEBUG(dbgs() << "Loops not tightly nested\n");
892    return false;
893  }
894
895  return true;
896}
897
898int LoopInterchangeProfitability::getInstrOrderCost() {
899  unsigned GoodOrder, BadOrder;
900  BadOrder = GoodOrder = 0;
901  for (auto BI = InnerLoop->block_begin(), BE = InnerLoop->block_end();
902       BI != BE; ++BI) {
903    for (Instruction &Ins : **BI) {
904      if (const GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(&Ins)) {
905        unsigned NumOp = GEP->getNumOperands();
906        bool FoundInnerInduction = false;
907        bool FoundOuterInduction = false;
908        for (unsigned i = 0; i < NumOp; ++i) {
909          const SCEV *OperandVal = SE->getSCEV(GEP->getOperand(i));
910          const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(OperandVal);
911          if (!AR)
912            continue;
913
914          // If we find the inner induction after an outer induction e.g.
915          // for(int i=0;i<N;i++)
916          //   for(int j=0;j<N;j++)
917          //     A[i][j] = A[i-1][j-1]+k;
918          // then it is a good order.
919          if (AR->getLoop() == InnerLoop) {
920            // We found an InnerLoop induction after OuterLoop induction. It is
921            // a good order.
922            FoundInnerInduction = true;
923            if (FoundOuterInduction) {
924              GoodOrder++;
925              break;
926            }
927          }
928          // If we find the outer induction after an inner induction e.g.
929          // for(int i=0;i<N;i++)
930          //   for(int j=0;j<N;j++)
931          //     A[j][i] = A[j-1][i-1]+k;
932          // then it is a bad order.
933          if (AR->getLoop() == OuterLoop) {
934            // We found an OuterLoop induction after InnerLoop induction. It is
935            // a bad order.
936            FoundOuterInduction = true;
937            if (FoundInnerInduction) {
938              BadOrder++;
939              break;
940            }
941          }
942        }
943      }
944    }
945  }
946  return GoodOrder - BadOrder;
947}
948
949static bool isProfitabileForVectorization(unsigned InnerLoopId,
950                                          unsigned OuterLoopId,
951                                          CharMatrix &DepMatrix) {
952  // TODO: Improve this heuristic to catch more cases.
953  // If the inner loop is loop independent or doesn't carry any dependency it is
954  // profitable to move this to outer position.
955  unsigned Row = DepMatrix.size();
956  for (unsigned i = 0; i < Row; ++i) {
957    if (DepMatrix[i][InnerLoopId] != 'S' && DepMatrix[i][InnerLoopId] != 'I')
958      return false;
959    // TODO: We need to improve this heuristic.
960    if (DepMatrix[i][OuterLoopId] != '=')
961      return false;
962  }
963  // If outer loop has dependence and inner loop is loop independent then it is
964  // profitable to interchange to enable parallelism.
965  return true;
966}
967
968bool LoopInterchangeProfitability::isProfitable(unsigned InnerLoopId,
969                                                unsigned OuterLoopId,
970                                                CharMatrix &DepMatrix) {
971
972  // TODO: Add better profitability checks.
973  // e.g
974  // 1) Construct dependency matrix and move the one with no loop carried dep
975  //    inside to enable vectorization.
976
977  // This is rough cost estimation algorithm. It counts the good and bad order
978  // of induction variables in the instruction and allows reordering if number
979  // of bad orders is more than good.
980  int Cost = 0;
981  Cost += getInstrOrderCost();
982  DEBUG(dbgs() << "Cost = " << Cost << "\n");
983  if (Cost < 0)
984    return true;
985
986  // It is not profitable as per current cache profitability model. But check if
987  // we can move this loop outside to improve parallelism.
988  bool ImprovesPar =
989      isProfitabileForVectorization(InnerLoopId, OuterLoopId, DepMatrix);
990  return ImprovesPar;
991}
992
993void LoopInterchangeTransform::removeChildLoop(Loop *OuterLoop,
994                                               Loop *InnerLoop) {
995  for (Loop::iterator I = OuterLoop->begin(), E = OuterLoop->end(); I != E;
996       ++I) {
997    if (*I == InnerLoop) {
998      OuterLoop->removeChildLoop(I);
999      return;
1000    }
1001  }
1002  llvm_unreachable("Couldn't find loop");
1003}
1004
1005void LoopInterchangeTransform::restructureLoops(Loop *InnerLoop,
1006                                                Loop *OuterLoop) {
1007  Loop *OuterLoopParent = OuterLoop->getParentLoop();
1008  if (OuterLoopParent) {
1009    // Remove the loop from its parent loop.
1010    removeChildLoop(OuterLoopParent, OuterLoop);
1011    removeChildLoop(OuterLoop, InnerLoop);
1012    OuterLoopParent->addChildLoop(InnerLoop);
1013  } else {
1014    removeChildLoop(OuterLoop, InnerLoop);
1015    LI->changeTopLevelLoop(OuterLoop, InnerLoop);
1016  }
1017
1018  while (!InnerLoop->empty())
1019    OuterLoop->addChildLoop(InnerLoop->removeChildLoop(InnerLoop->begin()));
1020
1021  InnerLoop->addChildLoop(OuterLoop);
1022}
1023
1024bool LoopInterchangeTransform::transform() {
1025
1026  DEBUG(dbgs() << "transform\n");
1027  bool Transformed = false;
1028  Instruction *InnerIndexVar;
1029
1030  if (InnerLoop->getSubLoops().size() == 0) {
1031    BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
1032    DEBUG(dbgs() << "Calling Split Inner Loop\n");
1033    PHINode *InductionPHI = getInductionVariable(InnerLoop, SE);
1034    if (!InductionPHI) {
1035      DEBUG(dbgs() << "Failed to find the point to split loop latch \n");
1036      return false;
1037    }
1038
1039    if (InductionPHI->getIncomingBlock(0) == InnerLoopPreHeader)
1040      InnerIndexVar = dyn_cast<Instruction>(InductionPHI->getIncomingValue(1));
1041    else
1042      InnerIndexVar = dyn_cast<Instruction>(InductionPHI->getIncomingValue(0));
1043
1044    //
1045    // Split at the place were the induction variable is
1046    // incremented/decremented.
1047    // TODO: This splitting logic may not work always. Fix this.
1048    splitInnerLoopLatch(InnerIndexVar);
1049    DEBUG(dbgs() << "splitInnerLoopLatch Done\n");
1050
1051    // Splits the inner loops phi nodes out into a separate basic block.
1052    splitInnerLoopHeader();
1053    DEBUG(dbgs() << "splitInnerLoopHeader Done\n");
1054  }
1055
1056  Transformed |= adjustLoopLinks();
1057  if (!Transformed) {
1058    DEBUG(dbgs() << "adjustLoopLinks Failed\n");
1059    return false;
1060  }
1061
1062  restructureLoops(InnerLoop, OuterLoop);
1063  return true;
1064}
1065
1066void LoopInterchangeTransform::splitInnerLoopLatch(Instruction *Inc) {
1067  BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch();
1068  BasicBlock *InnerLoopLatchPred = InnerLoopLatch;
1069  InnerLoopLatch = SplitBlock(InnerLoopLatchPred, Inc, DT, LI);
1070}
1071
1072void LoopInterchangeTransform::splitInnerLoopHeader() {
1073
1074  // Split the inner loop header out. Here make sure that the reduction PHI's
1075  // stay in the innerloop body.
1076  BasicBlock *InnerLoopHeader = InnerLoop->getHeader();
1077  BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
1078  if (InnerLoopHasReduction) {
1079    // FIXME: Check if the induction PHI will always be the first PHI.
1080    BasicBlock *New = InnerLoopHeader->splitBasicBlock(
1081        ++(InnerLoopHeader->begin()), InnerLoopHeader->getName() + ".split");
1082    if (LI)
1083      if (Loop *L = LI->getLoopFor(InnerLoopHeader))
1084        L->addBasicBlockToLoop(New, *LI);
1085
1086    // Adjust Reduction PHI's in the block.
1087    SmallVector<PHINode *, 8> PHIVec;
1088    for (auto I = New->begin(); isa<PHINode>(I); ++I) {
1089      PHINode *PHI = dyn_cast<PHINode>(I);
1090      Value *V = PHI->getIncomingValueForBlock(InnerLoopPreHeader);
1091      PHI->replaceAllUsesWith(V);
1092      PHIVec.push_back((PHI));
1093    }
1094    for (PHINode *P : PHIVec) {
1095      P->eraseFromParent();
1096    }
1097  } else {
1098    SplitBlock(InnerLoopHeader, InnerLoopHeader->getFirstNonPHI(), DT, LI);
1099  }
1100
1101  DEBUG(dbgs() << "Output of splitInnerLoopHeader InnerLoopHeaderSucc & "
1102                  "InnerLoopHeader \n");
1103}
1104
1105/// \brief Move all instructions except the terminator from FromBB right before
1106/// InsertBefore
1107static void moveBBContents(BasicBlock *FromBB, Instruction *InsertBefore) {
1108  auto &ToList = InsertBefore->getParent()->getInstList();
1109  auto &FromList = FromBB->getInstList();
1110
1111  ToList.splice(InsertBefore->getIterator(), FromList, FromList.begin(),
1112                FromBB->getTerminator()->getIterator());
1113}
1114
1115void LoopInterchangeTransform::updateIncomingBlock(BasicBlock *CurrBlock,
1116                                                   BasicBlock *OldPred,
1117                                                   BasicBlock *NewPred) {
1118  for (auto I = CurrBlock->begin(); isa<PHINode>(I); ++I) {
1119    PHINode *PHI = cast<PHINode>(I);
1120    unsigned Num = PHI->getNumIncomingValues();
1121    for (unsigned i = 0; i < Num; ++i) {
1122      if (PHI->getIncomingBlock(i) == OldPred)
1123        PHI->setIncomingBlock(i, NewPred);
1124    }
1125  }
1126}
1127
1128bool LoopInterchangeTransform::adjustLoopBranches() {
1129
1130  DEBUG(dbgs() << "adjustLoopBranches called\n");
1131  // Adjust the loop preheader
1132  BasicBlock *InnerLoopHeader = InnerLoop->getHeader();
1133  BasicBlock *OuterLoopHeader = OuterLoop->getHeader();
1134  BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch();
1135  BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch();
1136  BasicBlock *OuterLoopPreHeader = OuterLoop->getLoopPreheader();
1137  BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
1138  BasicBlock *OuterLoopPredecessor = OuterLoopPreHeader->getUniquePredecessor();
1139  BasicBlock *InnerLoopLatchPredecessor =
1140      InnerLoopLatch->getUniquePredecessor();
1141  BasicBlock *InnerLoopLatchSuccessor;
1142  BasicBlock *OuterLoopLatchSuccessor;
1143
1144  BranchInst *OuterLoopLatchBI =
1145      dyn_cast<BranchInst>(OuterLoopLatch->getTerminator());
1146  BranchInst *InnerLoopLatchBI =
1147      dyn_cast<BranchInst>(InnerLoopLatch->getTerminator());
1148  BranchInst *OuterLoopHeaderBI =
1149      dyn_cast<BranchInst>(OuterLoopHeader->getTerminator());
1150  BranchInst *InnerLoopHeaderBI =
1151      dyn_cast<BranchInst>(InnerLoopHeader->getTerminator());
1152
1153  if (!OuterLoopPredecessor || !InnerLoopLatchPredecessor ||
1154      !OuterLoopLatchBI || !InnerLoopLatchBI || !OuterLoopHeaderBI ||
1155      !InnerLoopHeaderBI)
1156    return false;
1157
1158  BranchInst *InnerLoopLatchPredecessorBI =
1159      dyn_cast<BranchInst>(InnerLoopLatchPredecessor->getTerminator());
1160  BranchInst *OuterLoopPredecessorBI =
1161      dyn_cast<BranchInst>(OuterLoopPredecessor->getTerminator());
1162
1163  if (!OuterLoopPredecessorBI || !InnerLoopLatchPredecessorBI)
1164    return false;
1165  BasicBlock *InnerLoopHeaderSuccessor = InnerLoopHeader->getUniqueSuccessor();
1166  if (!InnerLoopHeaderSuccessor)
1167    return false;
1168
1169  // Adjust Loop Preheader and headers
1170
1171  unsigned NumSucc = OuterLoopPredecessorBI->getNumSuccessors();
1172  for (unsigned i = 0; i < NumSucc; ++i) {
1173    if (OuterLoopPredecessorBI->getSuccessor(i) == OuterLoopPreHeader)
1174      OuterLoopPredecessorBI->setSuccessor(i, InnerLoopPreHeader);
1175  }
1176
1177  NumSucc = OuterLoopHeaderBI->getNumSuccessors();
1178  for (unsigned i = 0; i < NumSucc; ++i) {
1179    if (OuterLoopHeaderBI->getSuccessor(i) == OuterLoopLatch)
1180      OuterLoopHeaderBI->setSuccessor(i, LoopExit);
1181    else if (OuterLoopHeaderBI->getSuccessor(i) == InnerLoopPreHeader)
1182      OuterLoopHeaderBI->setSuccessor(i, InnerLoopHeaderSuccessor);
1183  }
1184
1185  // Adjust reduction PHI's now that the incoming block has changed.
1186  updateIncomingBlock(InnerLoopHeaderSuccessor, InnerLoopHeader,
1187                      OuterLoopHeader);
1188
1189  BranchInst::Create(OuterLoopPreHeader, InnerLoopHeaderBI);
1190  InnerLoopHeaderBI->eraseFromParent();
1191
1192  // -------------Adjust loop latches-----------
1193  if (InnerLoopLatchBI->getSuccessor(0) == InnerLoopHeader)
1194    InnerLoopLatchSuccessor = InnerLoopLatchBI->getSuccessor(1);
1195  else
1196    InnerLoopLatchSuccessor = InnerLoopLatchBI->getSuccessor(0);
1197
1198  NumSucc = InnerLoopLatchPredecessorBI->getNumSuccessors();
1199  for (unsigned i = 0; i < NumSucc; ++i) {
1200    if (InnerLoopLatchPredecessorBI->getSuccessor(i) == InnerLoopLatch)
1201      InnerLoopLatchPredecessorBI->setSuccessor(i, InnerLoopLatchSuccessor);
1202  }
1203
1204  // Adjust PHI nodes in InnerLoopLatchSuccessor. Update all uses of PHI with
1205  // the value and remove this PHI node from inner loop.
1206  SmallVector<PHINode *, 8> LcssaVec;
1207  for (auto I = InnerLoopLatchSuccessor->begin(); isa<PHINode>(I); ++I) {
1208    PHINode *LcssaPhi = cast<PHINode>(I);
1209    LcssaVec.push_back(LcssaPhi);
1210  }
1211  for (PHINode *P : LcssaVec) {
1212    Value *Incoming = P->getIncomingValueForBlock(InnerLoopLatch);
1213    P->replaceAllUsesWith(Incoming);
1214    P->eraseFromParent();
1215  }
1216
1217  if (OuterLoopLatchBI->getSuccessor(0) == OuterLoopHeader)
1218    OuterLoopLatchSuccessor = OuterLoopLatchBI->getSuccessor(1);
1219  else
1220    OuterLoopLatchSuccessor = OuterLoopLatchBI->getSuccessor(0);
1221
1222  if (InnerLoopLatchBI->getSuccessor(1) == InnerLoopLatchSuccessor)
1223    InnerLoopLatchBI->setSuccessor(1, OuterLoopLatchSuccessor);
1224  else
1225    InnerLoopLatchBI->setSuccessor(0, OuterLoopLatchSuccessor);
1226
1227  updateIncomingBlock(OuterLoopLatchSuccessor, OuterLoopLatch, InnerLoopLatch);
1228
1229  if (OuterLoopLatchBI->getSuccessor(0) == OuterLoopLatchSuccessor) {
1230    OuterLoopLatchBI->setSuccessor(0, InnerLoopLatch);
1231  } else {
1232    OuterLoopLatchBI->setSuccessor(1, InnerLoopLatch);
1233  }
1234
1235  return true;
1236}
1237void LoopInterchangeTransform::adjustLoopPreheaders() {
1238
1239  // We have interchanged the preheaders so we need to interchange the data in
1240  // the preheader as well.
1241  // This is because the content of inner preheader was previously executed
1242  // inside the outer loop.
1243  BasicBlock *OuterLoopPreHeader = OuterLoop->getLoopPreheader();
1244  BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
1245  BasicBlock *OuterLoopHeader = OuterLoop->getHeader();
1246  BranchInst *InnerTermBI =
1247      cast<BranchInst>(InnerLoopPreHeader->getTerminator());
1248
1249  // These instructions should now be executed inside the loop.
1250  // Move instruction into a new block after outer header.
1251  moveBBContents(InnerLoopPreHeader, OuterLoopHeader->getTerminator());
1252  // These instructions were not executed previously in the loop so move them to
1253  // the older inner loop preheader.
1254  moveBBContents(OuterLoopPreHeader, InnerTermBI);
1255}
1256
1257bool LoopInterchangeTransform::adjustLoopLinks() {
1258
1259  // Adjust all branches in the inner and outer loop.
1260  bool Changed = adjustLoopBranches();
1261  if (Changed)
1262    adjustLoopPreheaders();
1263  return Changed;
1264}
1265
1266char LoopInterchange::ID = 0;
1267INITIALIZE_PASS_BEGIN(LoopInterchange, "loop-interchange",
1268                      "Interchanges loops for cache reuse", false, false)
1269INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
1270INITIALIZE_PASS_DEPENDENCY(DependenceAnalysisWrapperPass)
1271INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
1272INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
1273INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
1274INITIALIZE_PASS_DEPENDENCY(LCSSAWrapperPass)
1275INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
1276
1277INITIALIZE_PASS_END(LoopInterchange, "loop-interchange",
1278                    "Interchanges loops for cache reuse", false, false)
1279
1280Pass *llvm::createLoopInterchangePass() { return new LoopInterchange(); }
1281