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/Transforms/Scalar.h"
  32 #include "llvm/IR/Function.h"
  33 #include "llvm/IR/IRBuilder.h"
  34 #include "llvm/IR/IntrinsicInst.h"
  35 #include "llvm/IR/InstIterator.h"
  36 #include "llvm/IR/Dominators.h"
  37 #include "llvm/Pass.h"
  38 #include "llvm/Support/Debug.h"
  39 #include "llvm/Transforms/Utils/SSAUpdater.h"
  40 #include "llvm/Support/raw_ostream.h"
  41 #include "llvm/Transforms/Utils/LoopUtils.h"
  42 #include "llvm/Transforms/Utils/BasicBlockUtils.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 bool populateDependencyMatrix(CharMatrix &DepMatrix, unsigned Level, Loop *L,
  74                               DependenceAnalysis *DA) {
  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 = DA->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 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 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 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 bool validDepInterchange(CharMatrix &DepMatrix, unsigned Row,
 222                          unsigned OuterLoopId, char InnerDep, char OuterDep) {
 223
 224   if (isOuterMostDepPositive(DepMatrix, Row, OuterLoopId))
 225     return false;
 226
 227   if (InnerDep == OuterDep)
 228     return true;
 229
 230   // It is legal to interchange if and only if after interchange no row has a
 231   // '>' direction as the leftmost non-'='.
 232
 233   if (InnerDep == '=' || InnerDep == 'S' || InnerDep == 'I')
 234     return true;
 235
 236   if (InnerDep == '<')
 237     return true;
 238
 239   if (InnerDep == '>') {
 240     // If OuterLoopId represents outermost loop then interchanging will make the
 241     // 1st dependency as '>'
 242     if (OuterLoopId == 0)
 243       return false;
 244
 245     // If all dependencies before OuterloopId are '=','S'or 'I'. Then
 246     // interchanging will result in this row having an outermost non '='
 247     // dependency of '>'
 248     if (!containsNoDependence(DepMatrix, Row, OuterLoopId))
 249       return true;
 250   }
 251
 252   return false;
 253 }
 254
 255 // Checks if it is legal to interchange 2 loops.
 256 // [Theorm] A permutation of the loops in a perfect nest is legal if and only if
 257 // the direction matrix, after the same permutation is applied to its columns,
 258 // has no ">" direction as the leftmost non-"=" direction in any row.
 259 bool isLegalToInterChangeLoops(CharMatrix &DepMatrix, unsigned InnerLoopId,
 260                                unsigned OuterLoopId) {
 261
 262   unsigned NumRows = DepMatrix.size();
 263   // For each row check if it is valid to interchange.
 264   for (unsigned Row = 0; Row < NumRows; ++Row) {
 265     char InnerDep = DepMatrix[Row][InnerLoopId];
 266     char OuterDep = DepMatrix[Row][OuterLoopId];
 267     if (InnerDep == '*' || OuterDep == '*')
 268       return false;
 269     else if (!validDepInterchange(DepMatrix, Row, OuterLoopId, InnerDep,
 270                                   OuterDep))
 271       return false;
 272   }
 273   return true;
 274 }
 275
 276 static void populateWorklist(Loop &L, SmallVector<LoopVector, 8> &V) {
 277
 278   DEBUG(dbgs() << "Calling populateWorklist called\n");
 279   LoopVector LoopList;
 280   Loop *CurrentLoop = &L;
 281   std::vector<Loop *> vec = CurrentLoop->getSubLoopsVector();
 282   while (vec.size() != 0) {
 283     // The current loop has multiple subloops in it hence it is not tightly
 284     // nested.
 285     // Discard all loops above it added into Worklist.
 286     if (vec.size() != 1) {
 287       LoopList.clear();
 288       return;
 289     }
 290     LoopList.push_back(CurrentLoop);
 291     CurrentLoop = *(vec.begin());
 292     vec = CurrentLoop->getSubLoopsVector();
 293   }
 294   LoopList.push_back(CurrentLoop);
 295   V.push_back(LoopList);
 296 }
 297
 298 static PHINode *getInductionVariable(Loop *L, ScalarEvolution *SE) {
 299   PHINode *InnerIndexVar = L->getCanonicalInductionVariable();
 300   if (InnerIndexVar)
 301     return InnerIndexVar;
 302   if (L->getLoopLatch() == nullptr || L->getLoopPredecessor() == nullptr)
 303     return nullptr;
 304   for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) {
 305     PHINode *PhiVar = cast<PHINode>(I);
 306     Type *PhiTy = PhiVar->getType();
 307     if (!PhiTy->isIntegerTy() && !PhiTy->isFloatingPointTy() &&
 308         !PhiTy->isPointerTy())
 309       return nullptr;
 310     const SCEVAddRecExpr *AddRec =
 311         dyn_cast<SCEVAddRecExpr>(SE->getSCEV(PhiVar));
 312     if (!AddRec || !AddRec->isAffine())
 313       continue;
 314     const SCEV *Step = AddRec->getStepRecurrence(*SE);
 315     const SCEVConstant *C = dyn_cast<SCEVConstant>(Step);
 316     if (!C)
 317       continue;
 318     // Found the induction variable.
 319     // FIXME: Handle loops with more than one induction variable. Note that,
 320     // currently, legality makes sure we have only one induction variable.
 321     return PhiVar;
 322   }
 323   return nullptr;
 324 }
 325
 326 /// LoopInterchangeLegality checks if it is legal to interchange the loop.
 327 class LoopInterchangeLegality {
 328 public:
 329   LoopInterchangeLegality(Loop *Outer, Loop *Inner, ScalarEvolution *SE,
 330                           LoopInterchange *Pass)
 331       : OuterLoop(Outer), InnerLoop(Inner), SE(SE), CurrentPass(Pass) {}
 332
 333   /// Check if the loops can be interchanged.
 334   bool canInterchangeLoops(unsigned InnerLoopId, unsigned OuterLoopId,
 335                            CharMatrix &DepMatrix);
 336   /// Check if the loop structure is understood. We do not handle triangular
 337   /// loops for now.
 338   bool isLoopStructureUnderstood(PHINode *InnerInductionVar);
 339
 340   bool currentLimitations();
 341
 342 private:
 343   bool tightlyNested(Loop *Outer, Loop *Inner);
 344
 345   Loop *OuterLoop;
 346   Loop *InnerLoop;
 347
 348   /// Scev analysis.
 349   ScalarEvolution *SE;
 350   LoopInterchange *CurrentPass;
 351 };
 352
 353 /// LoopInterchangeProfitability checks if it is profitable to interchange the
 354 /// loop.
 355 class LoopInterchangeProfitability {
 356 public:
 357   LoopInterchangeProfitability(Loop *Outer, Loop *Inner, ScalarEvolution *SE)
 358       : OuterLoop(Outer), InnerLoop(Inner), SE(SE) {}
 359
 360   /// Check if the loop interchange is profitable
 361   bool isProfitable(unsigned InnerLoopId, unsigned OuterLoopId,
 362                     CharMatrix &DepMatrix);
 363
 364 private:
 365   int getInstrOrderCost();
 366
 367   Loop *OuterLoop;
 368   Loop *InnerLoop;
 369
 370   /// Scev analysis.
 371   ScalarEvolution *SE;
 372 };
 373
 374 /// LoopInterchangeTransform interchanges the loop
 375 class LoopInterchangeTransform {
 376 public:
 377   LoopInterchangeTransform(Loop *Outer, Loop *Inner, ScalarEvolution *SE,
 378                            LoopInfo *LI, DominatorTree *DT,
 379                            LoopInterchange *Pass, BasicBlock *LoopNestExit)
 380       : OuterLoop(Outer), InnerLoop(Inner), SE(SE), LI(LI), DT(DT),
 381         LoopExit(LoopNestExit) {
 382     initialize();
 383   }
 384
 385   /// Interchange OuterLoop and InnerLoop.
 386   bool transform();
 387   void restructureLoops(Loop *InnerLoop, Loop *OuterLoop);
 388   void removeChildLoop(Loop *OuterLoop, Loop *InnerLoop);
 389   void initialize();
 390
 391 private:
 392   void splitInnerLoopLatch(Instruction *);
 393   void splitOuterLoopLatch();
 394   void splitInnerLoopHeader();
 395   bool adjustLoopLinks();
 396   void adjustLoopPreheaders();
 397   void adjustOuterLoopPreheader();
 398   void adjustInnerLoopPreheader();
 399   bool adjustLoopBranches();
 400
 401   Loop *OuterLoop;
 402   Loop *InnerLoop;
 403
 404   /// Scev analysis.
 405   ScalarEvolution *SE;
 406   LoopInfo *LI;
 407   DominatorTree *DT;
 408   BasicBlock *LoopExit;
 409 };
 410
 411 // Main LoopInterchange Pass
 412 struct LoopInterchange : public FunctionPass {
 413   static char ID;
 414   ScalarEvolution *SE;
 415   LoopInfo *LI;
 416   DependenceAnalysis *DA;
 417   DominatorTree *DT;
 418   LoopInterchange()
 419       : FunctionPass(ID), SE(nullptr), LI(nullptr), DA(nullptr), DT(nullptr) {
 420     initializeLoopInterchangePass(*PassRegistry::getPassRegistry());
 421   }
 422
 423   void getAnalysisUsage(AnalysisUsage &AU) const override {
 424     AU.addRequired<ScalarEvolution>();
 425     AU.addRequired<AliasAnalysis>();
 426     AU.addRequired<DominatorTreeWrapperPass>();
 427     AU.addRequired<LoopInfoWrapperPass>();
 428     AU.addRequired<DependenceAnalysis>();
 429     AU.addRequiredID(LoopSimplifyID);
 430     AU.addRequiredID(LCSSAID);
 431   }
 432
 433   bool runOnFunction(Function &F) override {
 434     SE = &getAnalysis<ScalarEvolution>();
 435     LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
 436     DA = &getAnalysis<DependenceAnalysis>();
 437     auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();
 438     DT = DTWP ? &DTWP->getDomTree() : nullptr;
 439     // Build up a worklist of loop pairs to analyze.
 440     SmallVector<LoopVector, 8> Worklist;
 441
 442     for (Loop *L : *LI)
 443       populateWorklist(*L, Worklist);
 444
 445     DEBUG(dbgs() << "Worklist size = " << Worklist.size() << "\n");
 446     bool Changed = true;
 447     while (!Worklist.empty()) {
 448       LoopVector LoopList = Worklist.pop_back_val();
 449       Changed = processLoopList(LoopList);
 450     }
 451     return Changed;
 452   }
 453
 454   bool isComputableLoopNest(LoopVector LoopList) {
 455     for (auto I = LoopList.begin(), E = LoopList.end(); I != E; ++I) {
 456       Loop *L = *I;
 457       const SCEV *ExitCountOuter = SE->getBackedgeTakenCount(L);
 458       if (ExitCountOuter == SE->getCouldNotCompute()) {
 459         DEBUG(dbgs() << "Couldn't compute Backedge count\n");
 460         return false;
 461       }
 462       if (L->getNumBackEdges() != 1) {
 463         DEBUG(dbgs() << "NumBackEdges is not equal to 1\n");
 464         return false;
 465       }
 466       if (!L->getExitingBlock()) {
 467         DEBUG(dbgs() << "Loop Doesn't have unique exit block\n");
 468         return false;
 469       }
 470     }
 471     return true;
 472   }
 473
 474   unsigned selectLoopForInterchange(LoopVector LoopList) {
 475     // TODO: Add a better heuristic to select the loop to be interchanged based
 476     // on the dependece matrix. Currently we select the innermost loop.
 477     return LoopList.size() - 1;
 478   }
 479
 480   bool processLoopList(LoopVector LoopList) {
 481     bool Changed = false;
 482     bool containsLCSSAPHI = false;
 483     CharMatrix DependencyMatrix;
 484     if (LoopList.size() < 2) {
 485       DEBUG(dbgs() << "Loop doesn't contain minimum nesting level.\n");
 486       return false;
 487     }
 488     if (!isComputableLoopNest(LoopList)) {
 489       DEBUG(dbgs() << "Not vaild loop candidate for interchange\n");
 490       return false;
 491     }
 492     Loop *OuterMostLoop = *(LoopList.begin());
 493
 494     DEBUG(dbgs() << "Processing LoopList of size = " << LoopList.size()
 495                  << "\n");
 496
 497     if (!populateDependencyMatrix(DependencyMatrix, LoopList.size(),
 498                                   OuterMostLoop, DA)) {
 499       DEBUG(dbgs() << "Populating Dependency matrix failed\n");
 500       return false;
 501     }
 502 #ifdef DUMP_DEP_MATRICIES
 503     DEBUG(dbgs() << "Dependence before inter change \n");
 504     printDepMatrix(DependencyMatrix);
 505 #endif
 506
 507     BasicBlock *OuterMostLoopLatch = OuterMostLoop->getLoopLatch();
 508     BranchInst *OuterMostLoopLatchBI =
 509         dyn_cast<BranchInst>(OuterMostLoopLatch->getTerminator());
 510     if (!OuterMostLoopLatchBI)
 511       return false;
 512
 513     // Since we currently do not handle LCSSA PHI's any failure in loop
 514     // condition will now branch to LoopNestExit.
 515     // TODO: This should be removed once we handle LCSSA PHI nodes.
 516
 517     // Get the Outermost loop exit.
 518     BasicBlock *LoopNestExit;
 519     if (OuterMostLoopLatchBI->getSuccessor(0) == OuterMostLoop->getHeader())
 520       LoopNestExit = OuterMostLoopLatchBI->getSuccessor(1);
 521     else
 522       LoopNestExit = OuterMostLoopLatchBI->getSuccessor(0);
 523
 524     for (auto I = LoopList.begin(), E = LoopList.end(); I != E; ++I) {
 525       Loop *L = *I;
 526       BasicBlock *Latch = L->getLoopLatch();
 527       BasicBlock *Header = L->getHeader();
 528       if (Latch && Latch != Header && isa<PHINode>(Latch->begin())) {
 529         containsLCSSAPHI = true;
 530         break;
 531       }
 532     }
 533
 534     // TODO: Handle lcssa PHI's. Currently LCSSA PHI's are not handled. Handle
 535     // the same by splitting the loop latch and adjusting loop links
 536     // accordingly.
 537     if (containsLCSSAPHI)
 538       return false;
 539
 540     unsigned SelecLoopId = selectLoopForInterchange(LoopList);
 541     // Move the selected loop outwards to the best posible position.
 542     for (unsigned i = SelecLoopId; i > 0; i--) {
 543       bool Interchanged =
 544           processLoop(LoopList, i, i - 1, LoopNestExit, DependencyMatrix);
 545       if (!Interchanged)
 546         return Changed;
 547       // Loops interchanged reflect the same in LoopList
 548       Loop *OldOuterLoop = LoopList[i - 1];
 549       LoopList[i - 1] = LoopList[i];
 550       LoopList[i] = OldOuterLoop;
 551
 552       // Update the DependencyMatrix
 553       interChangeDepedencies(DependencyMatrix, i, i - 1);
 554
 555 #ifdef DUMP_DEP_MATRICIES
 556       DEBUG(dbgs() << "Dependence after inter change \n");
 557       printDepMatrix(DependencyMatrix);
 558 #endif
 559       Changed |= Interchanged;
 560     }
 561     return Changed;
 562   }
 563
 564   bool processLoop(LoopVector LoopList, unsigned InnerLoopId,
 565                    unsigned OuterLoopId, BasicBlock *LoopNestExit,
 566                    std::vector<std::vector<char>> &DependencyMatrix) {
 567
 568     DEBUG(dbgs() << "Processing Innder Loop Id = " << InnerLoopId
 569                  << " and OuterLoopId = " << OuterLoopId << "\n");
 570     Loop *InnerLoop = LoopList[InnerLoopId];
 571     Loop *OuterLoop = LoopList[OuterLoopId];
 572
 573     LoopInterchangeLegality LIL(OuterLoop, InnerLoop, SE, this);
 574     if (!LIL.canInterchangeLoops(InnerLoopId, OuterLoopId, DependencyMatrix)) {
 575       DEBUG(dbgs() << "Not interchanging Loops. Cannot prove legality\n");
 576       return false;
 577     }
 578     DEBUG(dbgs() << "Loops are legal to interchange\n");
 579     LoopInterchangeProfitability LIP(OuterLoop, InnerLoop, SE);
 580     if (!LIP.isProfitable(InnerLoopId, OuterLoopId, DependencyMatrix)) {
 581       DEBUG(dbgs() << "Interchanging Loops not profitable\n");
 582       return false;
 583     }
 584
 585     LoopInterchangeTransform LIT(OuterLoop, InnerLoop, SE, LI, DT, this,
 586                                  LoopNestExit);
 587     LIT.transform();
 588     DEBUG(dbgs() << "Loops interchanged\n");
 589     return true;
 590   }
 591 };
 592
 593 } // end of namespace
 594
 595 static bool containsUnsafeInstructions(BasicBlock *BB) {
 596   for (auto I = BB->begin(), E = BB->end(); I != E; ++I) {
 597     if (I->mayHaveSideEffects() || I->mayReadFromMemory())
 598       return true;
 599   }
 600   return false;
 601 }
 602
 603 bool LoopInterchangeLegality::tightlyNested(Loop *OuterLoop, Loop *InnerLoop) {
 604   BasicBlock *OuterLoopHeader = OuterLoop->getHeader();
 605   BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
 606   BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch();
 607
 608   DEBUG(dbgs() << "Checking if Loops are Tightly Nested\n");
 609
 610   // A perfectly nested loop will not have any branch in between the outer and
 611   // inner block i.e. outer header will branch to either inner preheader and
 612   // outerloop latch.
 613   BranchInst *outerLoopHeaderBI =
 614       dyn_cast<BranchInst>(OuterLoopHeader->getTerminator());
 615   if (!outerLoopHeaderBI)
 616     return false;
 617   unsigned num = outerLoopHeaderBI->getNumSuccessors();
 618   for (unsigned i = 0; i < num; i++) {
 619     if (outerLoopHeaderBI->getSuccessor(i) != InnerLoopPreHeader &&
 620         outerLoopHeaderBI->getSuccessor(i) != OuterLoopLatch)
 621       return false;
 622   }
 623
 624   DEBUG(dbgs() << "Checking instructions in Loop header and Loop latch \n");
 625   // We do not have any basic block in between now make sure the outer header
 626   // and outer loop latch doesnt contain any unsafe instructions.
 627   if (containsUnsafeInstructions(OuterLoopHeader) ||
 628       containsUnsafeInstructions(OuterLoopLatch))
 629     return false;
 630
 631   DEBUG(dbgs() << "Loops are perfectly nested \n");
 632   // We have a perfect loop nest.
 633   return true;
 634 }
 635
 636 static unsigned getPHICount(BasicBlock *BB) {
 637   unsigned PhiCount = 0;
 638   for (auto I = BB->begin(); isa<PHINode>(I); ++I)
 639     PhiCount++;
 640   return PhiCount;
 641 }
 642
 643 bool LoopInterchangeLegality::isLoopStructureUnderstood(
 644     PHINode *InnerInduction) {
 645
 646   unsigned Num = InnerInduction->getNumOperands();
 647   BasicBlock *InnerLoopPreheader = InnerLoop->getLoopPreheader();
 648   for (unsigned i = 0; i < Num; ++i) {
 649     Value *Val = InnerInduction->getOperand(i);
 650     if (isa<Constant>(Val))
 651       continue;
 652     Instruction *I = dyn_cast<Instruction>(Val);
 653     if (!I)
 654       return false;
 655     // TODO: Handle triangular loops.
 656     // e.g. for(int i=0;i<N;i++)
 657     //        for(int j=i;j<N;j++)
 658     unsigned IncomBlockIndx = PHINode::getIncomingValueNumForOperand(i);
 659     if (InnerInduction->getIncomingBlock(IncomBlockIndx) ==
 660             InnerLoopPreheader &&
 661         !OuterLoop->isLoopInvariant(I)) {
 662       return false;
 663     }
 664   }
 665   return true;
 666 }
 667
 668 // This function indicates the current limitations in the transform as a result
 669 // of which we do not proceed.
 670 bool LoopInterchangeLegality::currentLimitations() {
 671
 672   BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
 673   BasicBlock *InnerLoopHeader = InnerLoop->getHeader();
 674   BasicBlock *OuterLoopHeader = OuterLoop->getHeader();
 675   BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch();
 676   BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch();
 677
 678   PHINode *InnerInductionVar;
 679   PHINode *OuterInductionVar;
 680
 681   // We currently handle only 1 induction variable inside the loop. We also do
 682   // not handle reductions as of now.
 683   if (getPHICount(InnerLoopHeader) > 1)
 684     return true;
 685
 686   if (getPHICount(OuterLoopHeader) > 1)
 687     return true;
 688
 689   InnerInductionVar = getInductionVariable(InnerLoop, SE);
 690   OuterInductionVar = getInductionVariable(OuterLoop, SE);
 691
 692   if (!OuterInductionVar || !InnerInductionVar) {
 693     DEBUG(dbgs() << "Induction variable not found\n");
 694     return true;
 695   }
 696
 697   // TODO: Triangular loops are not handled for now.
 698   if (!isLoopStructureUnderstood(InnerInductionVar)) {
 699     DEBUG(dbgs() << "Loop structure not understood by pass\n");
 700     return true;
 701   }
 702
 703   // TODO: Loops with LCSSA PHI's are currently not handled.
 704   if (isa<PHINode>(OuterLoopLatch->begin())) {
 705     DEBUG(dbgs() << "Found and LCSSA PHI in outer loop latch\n");
 706     return true;
 707   }
 708   if (InnerLoopLatch != InnerLoopHeader &&
 709       isa<PHINode>(InnerLoopLatch->begin())) {
 710     DEBUG(dbgs() << "Found and LCSSA PHI in inner loop latch\n");
 711     return true;
 712   }
 713
 714   // TODO: Current limitation: Since we split the inner loop latch at the point
 715   // were induction variable is incremented (induction.next); We cannot have
 716   // more than 1 user of induction.next since it would result in broken code
 717   // after split.
 718   // e.g.
 719   // for(i=0;i<N;i++) {
 720   //    for(j = 0;j<M;j++) {
 721   //      A[j+1][i+2] = A[j][i]+k;
 722   //  }
 723   // }
 724   bool FoundInduction = false;
 725   Instruction *InnerIndexVarInc = nullptr;
 726   if (InnerInductionVar->getIncomingBlock(0) == InnerLoopPreHeader)
 727     InnerIndexVarInc =
 728         dyn_cast<Instruction>(InnerInductionVar->getIncomingValue(1));
 729   else
 730     InnerIndexVarInc =
 731         dyn_cast<Instruction>(InnerInductionVar->getIncomingValue(0));
 732
 733   if (!InnerIndexVarInc)
 734     return true;
 735
 736   // Since we split the inner loop latch on this induction variable. Make sure
 737   // we do not have any instruction between the induction variable and branch
 738   // instruction.
 739
 740   for (auto I = InnerLoopLatch->rbegin(), E = InnerLoopLatch->rend();
 741        I != E && !FoundInduction; ++I) {
 742     if (isa<BranchInst>(*I) || isa<CmpInst>(*I) || isa<TruncInst>(*I))
 743       continue;
 744     const Instruction &Ins = *I;
 745     // We found an instruction. If this is not induction variable then it is not
 746     // safe to split this loop latch.
 747     if (!Ins.isIdenticalTo(InnerIndexVarInc))
 748       return true;
 749     else
 750       FoundInduction = true;
 751   }
 752   // The loop latch ended and we didnt find the induction variable return as
 753   // current limitation.
 754   if (!FoundInduction)
 755     return true;
 756
 757   return false;
 758 }
 759
 760 bool LoopInterchangeLegality::canInterchangeLoops(unsigned InnerLoopId,
 761                                                   unsigned OuterLoopId,
 762                                                   CharMatrix &DepMatrix) {
 763
 764   if (!isLegalToInterChangeLoops(DepMatrix, InnerLoopId, OuterLoopId)) {
 765     DEBUG(dbgs() << "Failed interchange InnerLoopId = " << InnerLoopId
 766                  << "and OuterLoopId = " << OuterLoopId
 767                  << "due to dependence\n");
 768     return false;
 769   }
 770
 771   // Create unique Preheaders if we already do not have one.
 772   BasicBlock *OuterLoopPreHeader = OuterLoop->getLoopPreheader();
 773   BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
 774
 775   // Create  a unique outer preheader -
 776   // 1) If OuterLoop preheader is not present.
 777   // 2) If OuterLoop Preheader is same as OuterLoop Header
 778   // 3) If OuterLoop Preheader is same as Header of the previous loop.
 779   // 4) If OuterLoop Preheader is Entry node.
 780   if (!OuterLoopPreHeader || OuterLoopPreHeader == OuterLoop->getHeader() ||
 781       isa<PHINode>(OuterLoopPreHeader->begin()) ||
 782       !OuterLoopPreHeader->getUniquePredecessor()) {
 783     OuterLoopPreHeader = InsertPreheaderForLoop(OuterLoop, CurrentPass);
 784   }
 785
 786   if (!InnerLoopPreHeader || InnerLoopPreHeader == InnerLoop->getHeader() ||
 787       InnerLoopPreHeader == OuterLoop->getHeader()) {
 788     InnerLoopPreHeader = InsertPreheaderForLoop(InnerLoop, CurrentPass);
 789   }
 790
 791   // Check if the loops are tightly nested.
 792   if (!tightlyNested(OuterLoop, InnerLoop)) {
 793     DEBUG(dbgs() << "Loops not tightly nested\n");
 794     return false;
 795   }
 796
 797   // TODO: The loops could not be interchanged due to current limitations in the
 798   // transform module.
 799   if (currentLimitations()) {
 800     DEBUG(dbgs() << "Not legal because of current transform limitation\n");
 801     return false;
 802   }
 803
 804   return true;
 805 }
 806
 807 int LoopInterchangeProfitability::getInstrOrderCost() {
 808   unsigned GoodOrder, BadOrder;
 809   BadOrder = GoodOrder = 0;
 810   for (auto BI = InnerLoop->block_begin(), BE = InnerLoop->block_end();
 811        BI != BE; ++BI) {
 812     for (auto I = (*BI)->begin(), E = (*BI)->end(); I != E; ++I) {
 813       const Instruction &Ins = *I;
 814       if (const GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(&Ins)) {
 815         unsigned NumOp = GEP->getNumOperands();
 816         bool FoundInnerInduction = false;
 817         bool FoundOuterInduction = false;
 818         for (unsigned i = 0; i < NumOp; ++i) {
 819           const SCEV *OperandVal = SE->getSCEV(GEP->getOperand(i));
 820           const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(OperandVal);
 821           if (!AR)
 822             continue;
 823
 824           // If we find the inner induction after an outer induction e.g.
 825           // for(int i=0;i<N;i++)
 826           //   for(int j=0;j<N;j++)
 827           //     A[i][j] = A[i-1][j-1]+k;
 828           // then it is a good order.
 829           if (AR->getLoop() == InnerLoop) {
 830             // We found an InnerLoop induction after OuterLoop induction. It is
 831             // a good order.
 832             FoundInnerInduction = true;
 833             if (FoundOuterInduction) {
 834               GoodOrder++;
 835               break;
 836             }
 837           }
 838           // If we find the outer induction after an inner induction e.g.
 839           // for(int i=0;i<N;i++)
 840           //   for(int j=0;j<N;j++)
 841           //     A[j][i] = A[j-1][i-1]+k;
 842           // then it is a bad order.
 843           if (AR->getLoop() == OuterLoop) {
 844             // We found an OuterLoop induction after InnerLoop induction. It is
 845             // a bad order.
 846             FoundOuterInduction = true;
 847             if (FoundInnerInduction) {
 848               BadOrder++;
 849               break;
 850             }
 851           }
 852         }
 853       }
 854     }
 855   }
 856   return GoodOrder - BadOrder;
 857 }
 858
 859 bool isProfitabileForVectorization(unsigned InnerLoopId, unsigned OuterLoopId,
 860                                    CharMatrix &DepMatrix) {
 861   // TODO: Improve this heuristic to catch more cases.
 862   // If the inner loop is loop independent or doesn't carry any dependency it is
 863   // profitable to move this to outer position.
 864   unsigned Row = DepMatrix.size();
 865   for (unsigned i = 0; i < Row; ++i) {
 866     if (DepMatrix[i][InnerLoopId] != 'S' && DepMatrix[i][InnerLoopId] != 'I')
 867       return false;
 868     // TODO: We need to improve this heuristic.
 869     if (DepMatrix[i][OuterLoopId] != '=')
 870       return false;
 871   }
 872   // If outer loop has dependence and inner loop is loop independent then it is
 873   // profitable to interchange to enable parallelism.
 874   return true;
 875 }
 876
 877 bool LoopInterchangeProfitability::isProfitable(unsigned InnerLoopId,
 878                                                 unsigned OuterLoopId,
 879                                                 CharMatrix &DepMatrix) {
 880
 881   // TODO: Add Better Profitibility checks.
 882   // e.g
 883   // 1) Construct dependency matrix and move the one with no loop carried dep
 884   //    inside to enable vectorization.
 885
 886   // This is rough cost estimation algorithm. It counts the good and bad order
 887   // of induction variables in the instruction and allows reordering if number
 888   // of bad orders is more than good.
 889   int Cost = 0;
 890   Cost += getInstrOrderCost();
 891   DEBUG(dbgs() << "Cost = " << Cost << "\n");
 892   if (Cost < 0)
 893     return true;
 894
 895   // It is not profitable as per current cache profitibility model. But check if
 896   // we can move this loop outside to improve parallelism.
 897   bool ImprovesPar =
 898       isProfitabileForVectorization(InnerLoopId, OuterLoopId, DepMatrix);
 899   return ImprovesPar;
 900 }
 901
 902 void LoopInterchangeTransform::removeChildLoop(Loop *OuterLoop,
 903                                                Loop *InnerLoop) {
 904   for (Loop::iterator I = OuterLoop->begin(), E = OuterLoop->end();; ++I) {
 905     assert(I != E && "Couldn't find loop");
 906     if (*I == InnerLoop) {
 907       OuterLoop->removeChildLoop(I);
 908       return;
 909     }
 910   }
 911 }
 912 void LoopInterchangeTransform::restructureLoops(Loop *InnerLoop,
 913                                                 Loop *OuterLoop) {
 914   Loop *OuterLoopParent = OuterLoop->getParentLoop();
 915   if (OuterLoopParent) {
 916     // Remove the loop from its parent loop.
 917     removeChildLoop(OuterLoopParent, OuterLoop);
 918     removeChildLoop(OuterLoop, InnerLoop);
 919     OuterLoopParent->addChildLoop(InnerLoop);
 920   } else {
 921     removeChildLoop(OuterLoop, InnerLoop);
 922     LI->changeTopLevelLoop(OuterLoop, InnerLoop);
 923   }
 924
 925   for (Loop::iterator I = InnerLoop->begin(), E = InnerLoop->end(); I != E; ++I)
 926     OuterLoop->addChildLoop(InnerLoop->removeChildLoop(I));
 927
 928   InnerLoop->addChildLoop(OuterLoop);
 929 }
 930
 931 bool LoopInterchangeTransform::transform() {
 932
 933   DEBUG(dbgs() << "transform\n");
 934   bool Transformed = false;
 935   Instruction *InnerIndexVar;
 936
 937   if (InnerLoop->getSubLoops().size() == 0) {
 938     BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
 939     DEBUG(dbgs() << "Calling Split Inner Loop\n");
 940     PHINode *InductionPHI = getInductionVariable(InnerLoop, SE);
 941     if (!InductionPHI) {
 942       DEBUG(dbgs() << "Failed to find the point to split loop latch \n");
 943       return false;
 944     }
 945
 946     if (InductionPHI->getIncomingBlock(0) == InnerLoopPreHeader)
 947       InnerIndexVar = dyn_cast<Instruction>(InductionPHI->getIncomingValue(1));
 948     else
 949       InnerIndexVar = dyn_cast<Instruction>(InductionPHI->getIncomingValue(0));
 950
 951     //
 952     // Split at the place were the induction variable is
 953     // incremented/decremented.
 954     // TODO: This splitting logic may not work always. Fix this.
 955     splitInnerLoopLatch(InnerIndexVar);
 956     DEBUG(dbgs() << "splitInnerLoopLatch Done\n");
 957
 958     // Splits the inner loops phi nodes out into a seperate basic block.
 959     splitInnerLoopHeader();
 960     DEBUG(dbgs() << "splitInnerLoopHeader Done\n");
 961   }
 962
 963   Transformed |= adjustLoopLinks();
 964   if (!Transformed) {
 965     DEBUG(dbgs() << "adjustLoopLinks Failed\n");
 966     return false;
 967   }
 968
 969   restructureLoops(InnerLoop, OuterLoop);
 970   return true;
 971 }
 972
 973 void LoopInterchangeTransform::initialize() {}
 974
 975 void LoopInterchangeTransform::splitInnerLoopLatch(Instruction *inc) {
 976
 977   BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch();
 978   BasicBlock::iterator I = InnerLoopLatch->begin();
 979   BasicBlock::iterator E = InnerLoopLatch->end();
 980   for (; I != E; ++I) {
 981     if (inc == I)
 982       break;
 983   }
 984
 985   BasicBlock *InnerLoopLatchPred = InnerLoopLatch;
 986   InnerLoopLatch = SplitBlock(InnerLoopLatchPred, I, DT, LI);
 987 }
 988
 989 void LoopInterchangeTransform::splitOuterLoopLatch() {
 990   BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch();
 991   BasicBlock *OuterLatchLcssaPhiBlock = OuterLoopLatch;
 992   OuterLoopLatch = SplitBlock(OuterLatchLcssaPhiBlock,
 993                               OuterLoopLatch->getFirstNonPHI(), DT, LI);
 994 }
 995
 996 void LoopInterchangeTransform::splitInnerLoopHeader() {
 997
 998   // Split the inner loop header out.
 999   BasicBlock *InnerLoopHeader = InnerLoop->getHeader();
1000   SplitBlock(InnerLoopHeader, InnerLoopHeader->getFirstNonPHI(), DT, LI);
1001
1002   DEBUG(dbgs() << "Output of splitInnerLoopHeader InnerLoopHeaderSucc & "
1003                   "InnerLoopHeader \n");
1004 }
1005
1006 void LoopInterchangeTransform::adjustOuterLoopPreheader() {
1007   BasicBlock *OuterLoopPreHeader = OuterLoop->getLoopPreheader();
1008   SmallVector<Instruction *, 8> Inst;
1009   for (auto I = OuterLoopPreHeader->begin(), E = OuterLoopPreHeader->end();
1010        I != E; ++I) {
1011     if (isa<BranchInst>(*I))
1012       break;
1013     Inst.push_back(I);
1014   }
1015
1016   BasicBlock *InnerPreHeader = InnerLoop->getLoopPreheader();
1017   for (auto I = Inst.begin(), E = Inst.end(); I != E; ++I) {
1018     Instruction *Ins = cast<Instruction>(*I);
1019     Ins->moveBefore(InnerPreHeader->getTerminator());
1020   }
1021 }
1022
1023 void LoopInterchangeTransform::adjustInnerLoopPreheader() {
1024
1025   BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
1026   SmallVector<Instruction *, 8> Inst;
1027   for (auto I = InnerLoopPreHeader->begin(), E = InnerLoopPreHeader->end();
1028        I != E; ++I) {
1029     if (isa<BranchInst>(*I))
1030       break;
1031     Inst.push_back(I);
1032   }
1033   BasicBlock *OuterHeader = OuterLoop->getHeader();
1034   for (auto I = Inst.begin(), E = Inst.end(); I != E; ++I) {
1035     Instruction *Ins = cast<Instruction>(*I);
1036     Ins->moveBefore(OuterHeader->getTerminator());
1037   }
1038 }
1039
1040 bool LoopInterchangeTransform::adjustLoopBranches() {
1041
1042   DEBUG(dbgs() << "adjustLoopBranches called\n");
1043   // Adjust the loop preheader
1044   BasicBlock *InnerLoopHeader = InnerLoop->getHeader();
1045   BasicBlock *OuterLoopHeader = OuterLoop->getHeader();
1046   BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch();
1047   BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch();
1048   BasicBlock *OuterLoopPreHeader = OuterLoop->getLoopPreheader();
1049   BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
1050   BasicBlock *OuterLoopPredecessor = OuterLoopPreHeader->getUniquePredecessor();
1051   BasicBlock *InnerLoopLatchPredecessor =
1052       InnerLoopLatch->getUniquePredecessor();
1053   BasicBlock *InnerLoopLatchSuccessor;
1054   BasicBlock *OuterLoopLatchSuccessor;
1055
1056   BranchInst *OuterLoopLatchBI =
1057       dyn_cast<BranchInst>(OuterLoopLatch->getTerminator());
1058   BranchInst *InnerLoopLatchBI =
1059       dyn_cast<BranchInst>(InnerLoopLatch->getTerminator());
1060   BranchInst *OuterLoopHeaderBI =
1061       dyn_cast<BranchInst>(OuterLoopHeader->getTerminator());
1062   BranchInst *InnerLoopHeaderBI =
1063       dyn_cast<BranchInst>(InnerLoopHeader->getTerminator());
1064
1065   if (!OuterLoopPredecessor || !InnerLoopLatchPredecessor ||
1066       !OuterLoopLatchBI || !InnerLoopLatchBI || !OuterLoopHeaderBI ||
1067       !InnerLoopHeaderBI)
1068     return false;
1069
1070   BranchInst *InnerLoopLatchPredecessorBI =
1071       dyn_cast<BranchInst>(InnerLoopLatchPredecessor->getTerminator());
1072   BranchInst *OuterLoopPredecessorBI =
1073       dyn_cast<BranchInst>(OuterLoopPredecessor->getTerminator());
1074
1075   if (!OuterLoopPredecessorBI || !InnerLoopLatchPredecessorBI)
1076     return false;
1077   BasicBlock *InnerLoopHeaderSucessor = InnerLoopHeader->getUniqueSuccessor();
1078   if (!InnerLoopHeaderSucessor)
1079     return false;
1080
1081   // Adjust Loop Preheader and headers
1082
1083   unsigned NumSucc = OuterLoopPredecessorBI->getNumSuccessors();
1084   for (unsigned i = 0; i < NumSucc; ++i) {
1085     if (OuterLoopPredecessorBI->getSuccessor(i) == OuterLoopPreHeader)
1086       OuterLoopPredecessorBI->setSuccessor(i, InnerLoopPreHeader);
1087   }
1088
1089   NumSucc = OuterLoopHeaderBI->getNumSuccessors();
1090   for (unsigned i = 0; i < NumSucc; ++i) {
1091     if (OuterLoopHeaderBI->getSuccessor(i) == OuterLoopLatch)
1092       OuterLoopHeaderBI->setSuccessor(i, LoopExit);
1093     else if (OuterLoopHeaderBI->getSuccessor(i) == InnerLoopPreHeader)
1094       OuterLoopHeaderBI->setSuccessor(i, InnerLoopHeaderSucessor);
1095   }
1096
1097   BranchInst::Create(OuterLoopPreHeader, InnerLoopHeaderBI);
1098   InnerLoopHeaderBI->eraseFromParent();
1099
1100   // -------------Adjust loop latches-----------
1101   if (InnerLoopLatchBI->getSuccessor(0) == InnerLoopHeader)
1102     InnerLoopLatchSuccessor = InnerLoopLatchBI->getSuccessor(1);
1103   else
1104     InnerLoopLatchSuccessor = InnerLoopLatchBI->getSuccessor(0);
1105
1106   NumSucc = InnerLoopLatchPredecessorBI->getNumSuccessors();
1107   for (unsigned i = 0; i < NumSucc; ++i) {
1108     if (InnerLoopLatchPredecessorBI->getSuccessor(i) == InnerLoopLatch)
1109       InnerLoopLatchPredecessorBI->setSuccessor(i, InnerLoopLatchSuccessor);
1110   }
1111
1112   if (OuterLoopLatchBI->getSuccessor(0) == OuterLoopHeader)
1113     OuterLoopLatchSuccessor = OuterLoopLatchBI->getSuccessor(1);
1114   else
1115     OuterLoopLatchSuccessor = OuterLoopLatchBI->getSuccessor(0);
1116
1117   if (InnerLoopLatchBI->getSuccessor(1) == InnerLoopLatchSuccessor)
1118     InnerLoopLatchBI->setSuccessor(1, OuterLoopLatchSuccessor);
1119   else
1120     InnerLoopLatchBI->setSuccessor(0, OuterLoopLatchSuccessor);
1121
1122   if (OuterLoopLatchBI->getSuccessor(0) == OuterLoopLatchSuccessor) {
1123     OuterLoopLatchBI->setSuccessor(0, InnerLoopLatch);
1124   } else {
1125     OuterLoopLatchBI->setSuccessor(1, InnerLoopLatch);
1126   }
1127
1128   return true;
1129 }
1130 void LoopInterchangeTransform::adjustLoopPreheaders() {
1131
1132   // We have interchanged the preheaders so we need to interchange the data in
1133   // the preheader as well.
1134   // This is because the content of inner preheader was previously executed
1135   // inside the outer loop.
1136   BasicBlock *OuterLoopPreHeader = OuterLoop->getLoopPreheader();
1137   BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
1138   BasicBlock *OuterLoopHeader = OuterLoop->getHeader();
1139   BranchInst *InnerTermBI =
1140       cast<BranchInst>(InnerLoopPreHeader->getTerminator());
1141
1142   SmallVector<Value *, 16> OuterPreheaderInstr;
1143   SmallVector<Value *, 16> InnerPreheaderInstr;
1144
1145   for (auto I = OuterLoopPreHeader->begin(); !isa<BranchInst>(I); ++I)
1146     OuterPreheaderInstr.push_back(I);
1147
1148   for (auto I = InnerLoopPreHeader->begin(); !isa<BranchInst>(I); ++I)
1149     InnerPreheaderInstr.push_back(I);
1150
1151   BasicBlock *HeaderSplit =
1152       SplitBlock(OuterLoopHeader, OuterLoopHeader->getTerminator(), DT, LI);
1153   Instruction *InsPoint = HeaderSplit->getFirstNonPHI();
1154   // These instructions should now be executed inside the loop.
1155   // Move instruction into a new block after outer header.
1156   for (auto I = InnerPreheaderInstr.begin(), E = InnerPreheaderInstr.end();
1157        I != E; ++I) {
1158     Instruction *Ins = cast<Instruction>(*I);
1159     Ins->moveBefore(InsPoint);
1160   }
1161   // These instructions were not executed previously in the loop so move them to
1162   // the older inner loop preheader.
1163   for (auto I = OuterPreheaderInstr.begin(), E = OuterPreheaderInstr.end();
1164        I != E; ++I) {
1165     Instruction *Ins = cast<Instruction>(*I);
1166     Ins->moveBefore(InnerTermBI);
1167   }
1168 }
1169
1170 bool LoopInterchangeTransform::adjustLoopLinks() {
1171
1172   // Adjust all branches in the inner and outer loop.
1173   bool Changed = adjustLoopBranches();
1174   if (Changed)
1175     adjustLoopPreheaders();
1176   return Changed;
1177 }
1178
1179 char LoopInterchange::ID = 0;
1180 INITIALIZE_PASS_BEGIN(LoopInterchange, "loop-interchange",
1181                       "Interchanges loops for cache reuse", false, false)
1182 INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
1183 INITIALIZE_PASS_DEPENDENCY(DependenceAnalysis)
1184 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
1185 INITIALIZE_PASS_DEPENDENCY(ScalarEvolution)
1186 INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
1187 INITIALIZE_PASS_DEPENDENCY(LCSSA)
1188 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
1189
1190 INITIALIZE_PASS_END(LoopInterchange, "loop-interchange",
1191                     "Interchanges loops for cache reuse", false, false)
1192
1193 Pass *llvm::createLoopInterchangePass() { return new LoopInterchange(); }