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 != E;
 905        ++I) {
 906     if (*I == InnerLoop) {
 907       OuterLoop->removeChildLoop(I);
 908       return;
 909     }
 910   }
 911   assert(false && "Couldn't find loop");
 912 }
 913
 914 void LoopInterchangeTransform::restructureLoops(Loop *InnerLoop,
 915                                                 Loop *OuterLoop) {
 916   Loop *OuterLoopParent = OuterLoop->getParentLoop();
 917   if (OuterLoopParent) {
 918     // Remove the loop from its parent loop.
 919     removeChildLoop(OuterLoopParent, OuterLoop);
 920     removeChildLoop(OuterLoop, InnerLoop);
 921     OuterLoopParent->addChildLoop(InnerLoop);
 922   } else {
 923     removeChildLoop(OuterLoop, InnerLoop);
 924     LI->changeTopLevelLoop(OuterLoop, InnerLoop);
 925   }
 926
 927   for (Loop::iterator I = InnerLoop->begin(), E = InnerLoop->end(); I != E; ++I)
 928     OuterLoop->addChildLoop(InnerLoop->removeChildLoop(I));
 929
 930   InnerLoop->addChildLoop(OuterLoop);
 931 }
 932
 933 bool LoopInterchangeTransform::transform() {
 934
 935   DEBUG(dbgs() << "transform\n");
 936   bool Transformed = false;
 937   Instruction *InnerIndexVar;
 938
 939   if (InnerLoop->getSubLoops().size() == 0) {
 940     BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
 941     DEBUG(dbgs() << "Calling Split Inner Loop\n");
 942     PHINode *InductionPHI = getInductionVariable(InnerLoop, SE);
 943     if (!InductionPHI) {
 944       DEBUG(dbgs() << "Failed to find the point to split loop latch \n");
 945       return false;
 946     }
 947
 948     if (InductionPHI->getIncomingBlock(0) == InnerLoopPreHeader)
 949       InnerIndexVar = dyn_cast<Instruction>(InductionPHI->getIncomingValue(1));
 950     else
 951       InnerIndexVar = dyn_cast<Instruction>(InductionPHI->getIncomingValue(0));
 952
 953     //
 954     // Split at the place were the induction variable is
 955     // incremented/decremented.
 956     // TODO: This splitting logic may not work always. Fix this.
 957     splitInnerLoopLatch(InnerIndexVar);
 958     DEBUG(dbgs() << "splitInnerLoopLatch Done\n");
 959
 960     // Splits the inner loops phi nodes out into a seperate basic block.
 961     splitInnerLoopHeader();
 962     DEBUG(dbgs() << "splitInnerLoopHeader Done\n");
 963   }
 964
 965   Transformed |= adjustLoopLinks();
 966   if (!Transformed) {
 967     DEBUG(dbgs() << "adjustLoopLinks Failed\n");
 968     return false;
 969   }
 970
 971   restructureLoops(InnerLoop, OuterLoop);
 972   return true;
 973 }
 974
 975 void LoopInterchangeTransform::initialize() {}
 976
 977 void LoopInterchangeTransform::splitInnerLoopLatch(Instruction *inc) {
 978
 979   BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch();
 980   BasicBlock::iterator I = InnerLoopLatch->begin();
 981   BasicBlock::iterator E = InnerLoopLatch->end();
 982   for (; I != E; ++I) {
 983     if (inc == I)
 984       break;
 985   }
 986
 987   BasicBlock *InnerLoopLatchPred = InnerLoopLatch;
 988   InnerLoopLatch = SplitBlock(InnerLoopLatchPred, I, DT, LI);
 989 }
 990
 991 void LoopInterchangeTransform::splitOuterLoopLatch() {
 992   BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch();
 993   BasicBlock *OuterLatchLcssaPhiBlock = OuterLoopLatch;
 994   OuterLoopLatch = SplitBlock(OuterLatchLcssaPhiBlock,
 995                               OuterLoopLatch->getFirstNonPHI(), DT, LI);
 996 }
 997
 998 void LoopInterchangeTransform::splitInnerLoopHeader() {
 999
1000   // Split the inner loop header out.
1001   BasicBlock *InnerLoopHeader = InnerLoop->getHeader();
1002   SplitBlock(InnerLoopHeader, InnerLoopHeader->getFirstNonPHI(), DT, LI);
1003
1004   DEBUG(dbgs() << "Output of splitInnerLoopHeader InnerLoopHeaderSucc & "
1005                   "InnerLoopHeader \n");
1006 }
1007
1008 void LoopInterchangeTransform::adjustOuterLoopPreheader() {
1009   BasicBlock *OuterLoopPreHeader = OuterLoop->getLoopPreheader();
1010   SmallVector<Instruction *, 8> Inst;
1011   for (auto I = OuterLoopPreHeader->begin(), E = OuterLoopPreHeader->end();
1012        I != E; ++I) {
1013     if (isa<BranchInst>(*I))
1014       break;
1015     Inst.push_back(I);
1016   }
1017
1018   BasicBlock *InnerPreHeader = InnerLoop->getLoopPreheader();
1019   for (auto I = Inst.begin(), E = Inst.end(); I != E; ++I) {
1020     Instruction *Ins = cast<Instruction>(*I);
1021     Ins->moveBefore(InnerPreHeader->getTerminator());
1022   }
1023 }
1024
1025 void LoopInterchangeTransform::adjustInnerLoopPreheader() {
1026
1027   BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
1028   SmallVector<Instruction *, 8> Inst;
1029   for (auto I = InnerLoopPreHeader->begin(), E = InnerLoopPreHeader->end();
1030        I != E; ++I) {
1031     if (isa<BranchInst>(*I))
1032       break;
1033     Inst.push_back(I);
1034   }
1035   BasicBlock *OuterHeader = OuterLoop->getHeader();
1036   for (auto I = Inst.begin(), E = Inst.end(); I != E; ++I) {
1037     Instruction *Ins = cast<Instruction>(*I);
1038     Ins->moveBefore(OuterHeader->getTerminator());
1039   }
1040 }
1041
1042 bool LoopInterchangeTransform::adjustLoopBranches() {
1043
1044   DEBUG(dbgs() << "adjustLoopBranches called\n");
1045   // Adjust the loop preheader
1046   BasicBlock *InnerLoopHeader = InnerLoop->getHeader();
1047   BasicBlock *OuterLoopHeader = OuterLoop->getHeader();
1048   BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch();
1049   BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch();
1050   BasicBlock *OuterLoopPreHeader = OuterLoop->getLoopPreheader();
1051   BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
1052   BasicBlock *OuterLoopPredecessor = OuterLoopPreHeader->getUniquePredecessor();
1053   BasicBlock *InnerLoopLatchPredecessor =
1054       InnerLoopLatch->getUniquePredecessor();
1055   BasicBlock *InnerLoopLatchSuccessor;
1056   BasicBlock *OuterLoopLatchSuccessor;
1057
1058   BranchInst *OuterLoopLatchBI =
1059       dyn_cast<BranchInst>(OuterLoopLatch->getTerminator());
1060   BranchInst *InnerLoopLatchBI =
1061       dyn_cast<BranchInst>(InnerLoopLatch->getTerminator());
1062   BranchInst *OuterLoopHeaderBI =
1063       dyn_cast<BranchInst>(OuterLoopHeader->getTerminator());
1064   BranchInst *InnerLoopHeaderBI =
1065       dyn_cast<BranchInst>(InnerLoopHeader->getTerminator());
1066
1067   if (!OuterLoopPredecessor || !InnerLoopLatchPredecessor ||
1068       !OuterLoopLatchBI || !InnerLoopLatchBI || !OuterLoopHeaderBI ||
1069       !InnerLoopHeaderBI)
1070     return false;
1071
1072   BranchInst *InnerLoopLatchPredecessorBI =
1073       dyn_cast<BranchInst>(InnerLoopLatchPredecessor->getTerminator());
1074   BranchInst *OuterLoopPredecessorBI =
1075       dyn_cast<BranchInst>(OuterLoopPredecessor->getTerminator());
1076
1077   if (!OuterLoopPredecessorBI || !InnerLoopLatchPredecessorBI)
1078     return false;
1079   BasicBlock *InnerLoopHeaderSucessor = InnerLoopHeader->getUniqueSuccessor();
1080   if (!InnerLoopHeaderSucessor)
1081     return false;
1082
1083   // Adjust Loop Preheader and headers
1084
1085   unsigned NumSucc = OuterLoopPredecessorBI->getNumSuccessors();
1086   for (unsigned i = 0; i < NumSucc; ++i) {
1087     if (OuterLoopPredecessorBI->getSuccessor(i) == OuterLoopPreHeader)
1088       OuterLoopPredecessorBI->setSuccessor(i, InnerLoopPreHeader);
1089   }
1090
1091   NumSucc = OuterLoopHeaderBI->getNumSuccessors();
1092   for (unsigned i = 0; i < NumSucc; ++i) {
1093     if (OuterLoopHeaderBI->getSuccessor(i) == OuterLoopLatch)
1094       OuterLoopHeaderBI->setSuccessor(i, LoopExit);
1095     else if (OuterLoopHeaderBI->getSuccessor(i) == InnerLoopPreHeader)
1096       OuterLoopHeaderBI->setSuccessor(i, InnerLoopHeaderSucessor);
1097   }
1098
1099   BranchInst::Create(OuterLoopPreHeader, InnerLoopHeaderBI);
1100   InnerLoopHeaderBI->eraseFromParent();
1101
1102   // -------------Adjust loop latches-----------
1103   if (InnerLoopLatchBI->getSuccessor(0) == InnerLoopHeader)
1104     InnerLoopLatchSuccessor = InnerLoopLatchBI->getSuccessor(1);
1105   else
1106     InnerLoopLatchSuccessor = InnerLoopLatchBI->getSuccessor(0);
1107
1108   NumSucc = InnerLoopLatchPredecessorBI->getNumSuccessors();
1109   for (unsigned i = 0; i < NumSucc; ++i) {
1110     if (InnerLoopLatchPredecessorBI->getSuccessor(i) == InnerLoopLatch)
1111       InnerLoopLatchPredecessorBI->setSuccessor(i, InnerLoopLatchSuccessor);
1112   }
1113
1114   if (OuterLoopLatchBI->getSuccessor(0) == OuterLoopHeader)
1115     OuterLoopLatchSuccessor = OuterLoopLatchBI->getSuccessor(1);
1116   else
1117     OuterLoopLatchSuccessor = OuterLoopLatchBI->getSuccessor(0);
1118
1119   if (InnerLoopLatchBI->getSuccessor(1) == InnerLoopLatchSuccessor)
1120     InnerLoopLatchBI->setSuccessor(1, OuterLoopLatchSuccessor);
1121   else
1122     InnerLoopLatchBI->setSuccessor(0, OuterLoopLatchSuccessor);
1123
1124   if (OuterLoopLatchBI->getSuccessor(0) == OuterLoopLatchSuccessor) {
1125     OuterLoopLatchBI->setSuccessor(0, InnerLoopLatch);
1126   } else {
1127     OuterLoopLatchBI->setSuccessor(1, InnerLoopLatch);
1128   }
1129
1130   return true;
1131 }
1132 void LoopInterchangeTransform::adjustLoopPreheaders() {
1133
1134   // We have interchanged the preheaders so we need to interchange the data in
1135   // the preheader as well.
1136   // This is because the content of inner preheader was previously executed
1137   // inside the outer loop.
1138   BasicBlock *OuterLoopPreHeader = OuterLoop->getLoopPreheader();
1139   BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
1140   BasicBlock *OuterLoopHeader = OuterLoop->getHeader();
1141   BranchInst *InnerTermBI =
1142       cast<BranchInst>(InnerLoopPreHeader->getTerminator());
1143
1144   SmallVector<Value *, 16> OuterPreheaderInstr;
1145   SmallVector<Value *, 16> InnerPreheaderInstr;
1146
1147   for (auto I = OuterLoopPreHeader->begin(); !isa<BranchInst>(I); ++I)
1148     OuterPreheaderInstr.push_back(I);
1149
1150   for (auto I = InnerLoopPreHeader->begin(); !isa<BranchInst>(I); ++I)
1151     InnerPreheaderInstr.push_back(I);
1152
1153   BasicBlock *HeaderSplit =
1154       SplitBlock(OuterLoopHeader, OuterLoopHeader->getTerminator(), DT, LI);
1155   Instruction *InsPoint = HeaderSplit->getFirstNonPHI();
1156   // These instructions should now be executed inside the loop.
1157   // Move instruction into a new block after outer header.
1158   for (auto I = InnerPreheaderInstr.begin(), E = InnerPreheaderInstr.end();
1159        I != E; ++I) {
1160     Instruction *Ins = cast<Instruction>(*I);
1161     Ins->moveBefore(InsPoint);
1162   }
1163   // These instructions were not executed previously in the loop so move them to
1164   // the older inner loop preheader.
1165   for (auto I = OuterPreheaderInstr.begin(), E = OuterPreheaderInstr.end();
1166        I != E; ++I) {
1167     Instruction *Ins = cast<Instruction>(*I);
1168     Ins->moveBefore(InnerTermBI);
1169   }
1170 }
1171
1172 bool LoopInterchangeTransform::adjustLoopLinks() {
1173
1174   // Adjust all branches in the inner and outer loop.
1175   bool Changed = adjustLoopBranches();
1176   if (Changed)
1177     adjustLoopPreheaders();
1178   return Changed;
1179 }
1180
1181 char LoopInterchange::ID = 0;
1182 INITIALIZE_PASS_BEGIN(LoopInterchange, "loop-interchange",
1183                       "Interchanges loops for cache reuse", false, false)
1184 INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
1185 INITIALIZE_PASS_DEPENDENCY(DependenceAnalysis)
1186 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
1187 INITIALIZE_PASS_DEPENDENCY(ScalarEvolution)
1188 INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
1189 INITIALIZE_PASS_DEPENDENCY(LCSSA)
1190 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
1191
1192 INITIALIZE_PASS_END(LoopInterchange, "loop-interchange",
1193                     "Interchanges loops for cache reuse", false, false)
1194
1195 Pass *llvm::createLoopInterchangePass() { return new LoopInterchange(); }