lib/Transforms/Scalar/LoopInterchange.cpp

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