Home | History | Annotate | Download | only in Scalar 
      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"
     43 using namespace llvm;
     44 
     45 #define DEBUG_TYPE "loop-interchange"
     46 
     47 namespace {
     48 
     49 typedef SmallVector<Loop *, 8> LoopVector;
     50 
     51 // TODO: Check if we can use a sparse matrix here.
     52 typedef std::vector<std::vector<char>> CharMatrix;
     53 
     54 // Maximum number of dependencies that can be handled in the dependency matrix.
     55 static const unsigned MaxMemInstrCount = 100;
     56 
     57 // Maximum loop depth supported.
     58 static const unsigned MaxLoopNestDepth = 10;
     59 
     60 struct LoopInterchange;
     61 
     62 #ifdef DUMP_DEP_MATRICIES
     63 void 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 
     73 static 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.
    186 static 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 // '>'
    198 static 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.
    211 static 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 
    221 static 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.
    261 static 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 
    279 static 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 
    301 static 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.
    330 class LoopInterchangeLegality {
    331 public:
    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 
    348 private:
    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.
    369 class LoopInterchangeProfitability {
    370 public:
    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 
    378 private:
    379   int getInstrOrderCost();
    380 
    381   Loop *OuterLoop;
    382   Loop *InnerLoop;
    383 
    384   /// Scev analysis.
    385   ScalarEvolution *SE;
    386 };
    387 
    388 /// LoopInterchangeTransform interchanges the loop.
    389 class LoopInterchangeTransform {
    390 public:
    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 
    404 private:
    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.
    425 struct 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
    601 bool 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 
    609 bool 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 
    623 bool 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 
    638 bool 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 
    672 bool 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 
    697 bool 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 
    719 static 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 
    736 static 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.
    752 bool 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 
    849 bool 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 
    898 int 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 
    949 static 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 
    968 bool 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 
    993 void 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 
   1005 void 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 
   1024 bool 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 
   1066 void LoopInterchangeTransform::splitInnerLoopLatch(Instruction *Inc) {
   1067   BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch();
   1068   BasicBlock *InnerLoopLatchPred = InnerLoopLatch;
   1069   InnerLoopLatch = SplitBlock(InnerLoopLatchPred, Inc, DT, LI);
   1070 }
   1071 
   1072 void 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
   1107 static 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 
   1115 void 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 
   1128 bool 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 }
   1237 void 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 
   1257 bool 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 
   1266 char LoopInterchange::ID = 0;
   1267 INITIALIZE_PASS_BEGIN(LoopInterchange, "loop-interchange",
   1268                       "Interchanges loops for cache reuse", false, false)
   1269 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
   1270 INITIALIZE_PASS_DEPENDENCY(DependenceAnalysisWrapperPass)
   1271 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
   1272 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
   1273 INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
   1274 INITIALIZE_PASS_DEPENDENCY(LCSSAWrapperPass)
   1275 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
   1276 
   1277 INITIALIZE_PASS_END(LoopInterchange, "loop-interchange",
   1278                     "Interchanges loops for cache reuse", false, false)
   1279 
   1280 Pass *llvm::createLoopInterchangePass() { return new LoopInterchange(); }
   1281