lib/Transforms/Scalar/LoopInterchange.cpp

   1 //===- LoopInterchange.cpp - Loop interchange pass------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This Pass handles loop interchange transform.
  11 // This pass interchanges loops to provide a more cache-friendly memory access
  12 // patterns.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #include "llvm/ADT/SmallVector.h"
  17 #include "llvm/Analysis/AliasAnalysis.h"
  18 #include "llvm/Analysis/AliasSetTracker.h"
  19 #include "llvm/Analysis/AssumptionCache.h"
  20 #include "llvm/Analysis/BlockFrequencyInfo.h"
  21 #include "llvm/Analysis/CodeMetrics.h"
  22 #include "llvm/Analysis/DependenceAnalysis.h"
  23 #include "llvm/Analysis/LoopInfo.h"
  24 #include "llvm/Analysis/LoopIterator.h"
  25 #include "llvm/Analysis/LoopPass.h"
  26 #include "llvm/Analysis/ScalarEvolution.h"
  27 #include "llvm/Analysis/ScalarEvolutionExpander.h"
  28 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
  29 #include "llvm/Analysis/TargetTransformInfo.h"
  30 #include "llvm/Analysis/ValueTracking.h"
  31 #include "llvm/IR/Dominators.h"
  32 #include "llvm/IR/Function.h"
  33 #include "llvm/IR/IRBuilder.h"
  34 #include "llvm/IR/InstIterator.h"
  35 #include "llvm/IR/IntrinsicInst.h"
  36 #include "llvm/Pass.h"
  37 #include "llvm/Support/Debug.h"
  38 #include "llvm/Support/raw_ostream.h"
  39 #include "llvm/Transforms/Scalar.h"
  40 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  41 #include "llvm/Transforms/Utils/LoopUtils.h"
  42 #include "llvm/Transforms/Utils/SSAUpdater.h"
  43 using namespace llvm;
  44
  45 #define DEBUG_TYPE "loop-interchange"
  46
  47 namespace {
  48
  49 typedef SmallVector<Loop *, 8> LoopVector;
  50
  51 // TODO: Check if we can use a sparse matrix here.
  52 typedef std::vector<std::vector<char>> CharMatrix;
  53
  54 // Maximum number of dependencies that can be handled in the dependency matrix.
  55 static const unsigned MaxMemInstrCount = 100;
  56
  57 // Maximum loop depth supported.
  58 static const unsigned MaxLoopNestDepth = 10;
  59
  60 struct LoopInterchange;
  61
  62 #ifdef DUMP_DEP_MATRICIES
  63 void printDepMatrix(CharMatrix &DepMatrix) {
  64   for (auto I = DepMatrix.begin(), E = DepMatrix.end(); I != E; ++I) {
  65     std::vector<char> Vec = *I;
  66     for (auto II = Vec.begin(), EE = Vec.end(); II != EE; ++II)
  67       DEBUG(dbgs() << *II << " ");
  68     DEBUG(dbgs() << "\n");
  69   }
  70 }
  71 #endif
  72
  73 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
 383   /// Interchange OuterLoop and InnerLoop.
 384   bool transform();
 385   void restructureLoops(Loop *InnerLoop, Loop *OuterLoop);
 386   void removeChildLoop(Loop *OuterLoop, Loop *InnerLoop);
 387
 388 private:
 389   void splitInnerLoopLatch(Instruction *);
 390   void splitOuterLoopLatch();
 391   void splitInnerLoopHeader();
 392   bool adjustLoopLinks();
 393   void adjustLoopPreheaders();
 394   void adjustOuterLoopPreheader();
 395   void adjustInnerLoopPreheader();
 396   bool adjustLoopBranches();
 397
 398   Loop *OuterLoop;
 399   Loop *InnerLoop;
 400
 401   /// Scev analysis.
 402   ScalarEvolution *SE;
 403   LoopInfo *LI;
 404   DominatorTree *DT;
 405   BasicBlock *LoopExit;
 406 };
 407
 408 // Main LoopInterchange Pass
 409 struct LoopInterchange : public FunctionPass {
 410   static char ID;
 411   ScalarEvolution *SE;
 412   LoopInfo *LI;
 413   DependenceAnalysis *DA;
 414   DominatorTree *DT;
 415   LoopInterchange()
 416       : FunctionPass(ID), SE(nullptr), LI(nullptr), DA(nullptr), DT(nullptr) {
 417     initializeLoopInterchangePass(*PassRegistry::getPassRegistry());
 418   }
 419
 420   void getAnalysisUsage(AnalysisUsage &AU) const override {
 421     AU.addRequired<ScalarEvolution>();
 422     AU.addRequired<AliasAnalysis>();
 423     AU.addRequired<DominatorTreeWrapperPass>();
 424     AU.addRequired<LoopInfoWrapperPass>();
 425     AU.addRequired<DependenceAnalysis>();
 426     AU.addRequiredID(LoopSimplifyID);
 427     AU.addRequiredID(LCSSAID);
 428   }
 429
 430   bool runOnFunction(Function &F) override {
 431     SE = &getAnalysis<ScalarEvolution>();
 432     LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
 433     DA = &getAnalysis<DependenceAnalysis>();
 434     auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();
 435     DT = DTWP ? &DTWP->getDomTree() : nullptr;
 436     // Build up a worklist of loop pairs to analyze.
 437     SmallVector<LoopVector, 8> Worklist;
 438
 439     for (Loop *L : *LI)
 440       populateWorklist(*L, Worklist);
 441
 442     DEBUG(dbgs() << "Worklist size = " << Worklist.size() << "\n");
 443     bool Changed = true;
 444     while (!Worklist.empty()) {
 445       LoopVector LoopList = Worklist.pop_back_val();
 446       Changed = processLoopList(LoopList);
 447     }
 448     return Changed;
 449   }
 450
 451   bool isComputableLoopNest(LoopVector LoopList) {
 452     for (auto I = LoopList.begin(), E = LoopList.end(); I != E; ++I) {
 453       Loop *L = *I;
 454       const SCEV *ExitCountOuter = SE->getBackedgeTakenCount(L);
 455       if (ExitCountOuter == SE->getCouldNotCompute()) {
 456         DEBUG(dbgs() << "Couldn't compute Backedge count\n");
 457         return false;
 458       }
 459       if (L->getNumBackEdges() != 1) {
 460         DEBUG(dbgs() << "NumBackEdges is not equal to 1\n");
 461         return false;
 462       }
 463       if (!L->getExitingBlock()) {
 464         DEBUG(dbgs() << "Loop Doesn't have unique exit block\n");
 465         return false;
 466       }
 467     }
 468     return true;
 469   }
 470
 471   unsigned selectLoopForInterchange(LoopVector LoopList) {
 472     // TODO: Add a better heuristic to select the loop to be interchanged based
 473     // on the dependece matrix. Currently we select the innermost loop.
 474     return LoopList.size() - 1;
 475   }
 476
 477   bool processLoopList(LoopVector LoopList) {
 478     bool Changed = false;
 479     bool containsLCSSAPHI = false;
 480     CharMatrix DependencyMatrix;
 481     if (LoopList.size() < 2) {
 482       DEBUG(dbgs() << "Loop doesn't contain minimum nesting level.\n");
 483       return false;
 484     }
 485     if (!isComputableLoopNest(LoopList)) {
 486       DEBUG(dbgs() << "Not vaild loop candidate for interchange\n");
 487       return false;
 488     }
 489     Loop *OuterMostLoop = *(LoopList.begin());
 490
 491     DEBUG(dbgs() << "Processing LoopList of size = " << LoopList.size()
 492                  << "\n");
 493
 494     if (!populateDependencyMatrix(DependencyMatrix, LoopList.size(),
 495                                   OuterMostLoop, DA)) {
 496       DEBUG(dbgs() << "Populating Dependency matrix failed\n");
 497       return false;
 498     }
 499 #ifdef DUMP_DEP_MATRICIES
 500     DEBUG(dbgs() << "Dependence before inter change \n");
 501     printDepMatrix(DependencyMatrix);
 502 #endif
 503
 504     BasicBlock *OuterMostLoopLatch = OuterMostLoop->getLoopLatch();
 505     BranchInst *OuterMostLoopLatchBI =
 506         dyn_cast<BranchInst>(OuterMostLoopLatch->getTerminator());
 507     if (!OuterMostLoopLatchBI)
 508       return false;
 509
 510     // Since we currently do not handle LCSSA PHI's any failure in loop
 511     // condition will now branch to LoopNestExit.
 512     // TODO: This should be removed once we handle LCSSA PHI nodes.
 513
 514     // Get the Outermost loop exit.
 515     BasicBlock *LoopNestExit;
 516     if (OuterMostLoopLatchBI->getSuccessor(0) == OuterMostLoop->getHeader())
 517       LoopNestExit = OuterMostLoopLatchBI->getSuccessor(1);
 518     else
 519       LoopNestExit = OuterMostLoopLatchBI->getSuccessor(0);
 520
 521     for (auto I = LoopList.begin(), E = LoopList.end(); I != E; ++I) {
 522       Loop *L = *I;
 523       BasicBlock *Latch = L->getLoopLatch();
 524       BasicBlock *Header = L->getHeader();
 525       if (Latch && Latch != Header && isa<PHINode>(Latch->begin())) {
 526         containsLCSSAPHI = true;
 527         break;
 528       }
 529     }
 530
 531     // TODO: Handle lcssa PHI's. Currently LCSSA PHI's are not handled. Handle
 532     // the same by splitting the loop latch and adjusting loop links
 533     // accordingly.
 534     if (containsLCSSAPHI)
 535       return false;
 536
 537     unsigned SelecLoopId = selectLoopForInterchange(LoopList);
 538     // Move the selected loop outwards to the best posible position.
 539     for (unsigned i = SelecLoopId; i > 0; i--) {
 540       bool Interchanged =
 541           processLoop(LoopList, i, i - 1, LoopNestExit, DependencyMatrix);
 542       if (!Interchanged)
 543         return Changed;
 544       // Loops interchanged reflect the same in LoopList
 545       std::swap(LoopList[i - 1], LoopList[i]);
 546
 547       // Update the DependencyMatrix
 548       interChangeDepedencies(DependencyMatrix, i, i - 1);
 549
 550 #ifdef DUMP_DEP_MATRICIES
 551       DEBUG(dbgs() << "Dependence after inter change \n");
 552       printDepMatrix(DependencyMatrix);
 553 #endif
 554       Changed |= Interchanged;
 555     }
 556     return Changed;
 557   }
 558
 559   bool processLoop(LoopVector LoopList, unsigned InnerLoopId,
 560                    unsigned OuterLoopId, BasicBlock *LoopNestExit,
 561                    std::vector<std::vector<char>> &DependencyMatrix) {
 562
 563     DEBUG(dbgs() << "Processing Innder Loop Id = " << InnerLoopId
 564                  << " and OuterLoopId = " << OuterLoopId << "\n");
 565     Loop *InnerLoop = LoopList[InnerLoopId];
 566     Loop *OuterLoop = LoopList[OuterLoopId];
 567
 568     LoopInterchangeLegality LIL(OuterLoop, InnerLoop, SE, this);
 569     if (!LIL.canInterchangeLoops(InnerLoopId, OuterLoopId, DependencyMatrix)) {
 570       DEBUG(dbgs() << "Not interchanging Loops. Cannot prove legality\n");
 571       return false;
 572     }
 573     DEBUG(dbgs() << "Loops are legal to interchange\n");
 574     LoopInterchangeProfitability LIP(OuterLoop, InnerLoop, SE);
 575     if (!LIP.isProfitable(InnerLoopId, OuterLoopId, DependencyMatrix)) {
 576       DEBUG(dbgs() << "Interchanging Loops not profitable\n");
 577       return false;
 578     }
 579
 580     LoopInterchangeTransform LIT(OuterLoop, InnerLoop, SE, LI, DT, this,
 581                                  LoopNestExit);
 582     LIT.transform();
 583     DEBUG(dbgs() << "Loops interchanged\n");
 584     return true;
 585   }
 586 };
 587
 588 } // end of namespace
 589
 590 static bool containsUnsafeInstructions(BasicBlock *BB) {
 591   for (auto I = BB->begin(), E = BB->end(); I != E; ++I) {
 592     if (I->mayHaveSideEffects() || I->mayReadFromMemory())
 593       return true;
 594   }
 595   return false;
 596 }
 597
 598 bool LoopInterchangeLegality::tightlyNested(Loop *OuterLoop, Loop *InnerLoop) {
 599   BasicBlock *OuterLoopHeader = OuterLoop->getHeader();
 600   BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
 601   BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch();
 602
 603   DEBUG(dbgs() << "Checking if Loops are Tightly Nested\n");
 604
 605   // A perfectly nested loop will not have any branch in between the outer and
 606   // inner block i.e. outer header will branch to either inner preheader and
 607   // outerloop latch.
 608   BranchInst *outerLoopHeaderBI =
 609       dyn_cast<BranchInst>(OuterLoopHeader->getTerminator());
 610   if (!outerLoopHeaderBI)
 611     return false;
 612   unsigned num = outerLoopHeaderBI->getNumSuccessors();
 613   for (unsigned i = 0; i < num; i++) {
 614     if (outerLoopHeaderBI->getSuccessor(i) != InnerLoopPreHeader &&
 615         outerLoopHeaderBI->getSuccessor(i) != OuterLoopLatch)
 616       return false;
 617   }
 618
 619   DEBUG(dbgs() << "Checking instructions in Loop header and Loop latch \n");
 620   // We do not have any basic block in between now make sure the outer header
 621   // and outer loop latch doesnt contain any unsafe instructions.
 622   if (containsUnsafeInstructions(OuterLoopHeader) ||
 623       containsUnsafeInstructions(OuterLoopLatch))
 624     return false;
 625
 626   DEBUG(dbgs() << "Loops are perfectly nested \n");
 627   // We have a perfect loop nest.
 628   return true;
 629 }
 630
 631 static unsigned getPHICount(BasicBlock *BB) {
 632   unsigned PhiCount = 0;
 633   for (auto I = BB->begin(); isa<PHINode>(I); ++I)
 634     PhiCount++;
 635   return PhiCount;
 636 }
 637
 638 bool LoopInterchangeLegality::isLoopStructureUnderstood(
 639     PHINode *InnerInduction) {
 640
 641   unsigned Num = InnerInduction->getNumOperands();
 642   BasicBlock *InnerLoopPreheader = InnerLoop->getLoopPreheader();
 643   for (unsigned i = 0; i < Num; ++i) {
 644     Value *Val = InnerInduction->getOperand(i);
 645     if (isa<Constant>(Val))
 646       continue;
 647     Instruction *I = dyn_cast<Instruction>(Val);
 648     if (!I)
 649       return false;
 650     // TODO: Handle triangular loops.
 651     // e.g. for(int i=0;i<N;i++)
 652     //        for(int j=i;j<N;j++)
 653     unsigned IncomBlockIndx = PHINode::getIncomingValueNumForOperand(i);
 654     if (InnerInduction->getIncomingBlock(IncomBlockIndx) ==
 655             InnerLoopPreheader &&
 656         !OuterLoop->isLoopInvariant(I)) {
 657       return false;
 658     }
 659   }
 660   return true;
 661 }
 662
 663 // This function indicates the current limitations in the transform as a result
 664 // of which we do not proceed.
 665 bool LoopInterchangeLegality::currentLimitations() {
 666
 667   BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
 668   BasicBlock *InnerLoopHeader = InnerLoop->getHeader();
 669   BasicBlock *OuterLoopHeader = OuterLoop->getHeader();
 670   BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch();
 671   BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch();
 672
 673   PHINode *InnerInductionVar;
 674   PHINode *OuterInductionVar;
 675
 676   // We currently handle only 1 induction variable inside the loop. We also do
 677   // not handle reductions as of now.
 678   if (getPHICount(InnerLoopHeader) > 1)
 679     return true;
 680
 681   if (getPHICount(OuterLoopHeader) > 1)
 682     return true;
 683
 684   InnerInductionVar = getInductionVariable(InnerLoop, SE);
 685   OuterInductionVar = getInductionVariable(OuterLoop, SE);
 686
 687   if (!OuterInductionVar || !InnerInductionVar) {
 688     DEBUG(dbgs() << "Induction variable not found\n");
 689     return true;
 690   }
 691
 692   // TODO: Triangular loops are not handled for now.
 693   if (!isLoopStructureUnderstood(InnerInductionVar)) {
 694     DEBUG(dbgs() << "Loop structure not understood by pass\n");
 695     return true;
 696   }
 697
 698   // TODO: Loops with LCSSA PHI's are currently not handled.
 699   if (isa<PHINode>(OuterLoopLatch->begin())) {
 700     DEBUG(dbgs() << "Found and LCSSA PHI in outer loop latch\n");
 701     return true;
 702   }
 703   if (InnerLoopLatch != InnerLoopHeader &&
 704       isa<PHINode>(InnerLoopLatch->begin())) {
 705     DEBUG(dbgs() << "Found and LCSSA PHI in inner loop latch\n");
 706     return true;
 707   }
 708
 709   // TODO: Current limitation: Since we split the inner loop latch at the point
 710   // were induction variable is incremented (induction.next); We cannot have
 711   // more than 1 user of induction.next since it would result in broken code
 712   // after split.
 713   // e.g.
 714   // for(i=0;i<N;i++) {
 715   //    for(j = 0;j<M;j++) {
 716   //      A[j+1][i+2] = A[j][i]+k;
 717   //  }
 718   // }
 719   bool FoundInduction = false;
 720   Instruction *InnerIndexVarInc = nullptr;
 721   if (InnerInductionVar->getIncomingBlock(0) == InnerLoopPreHeader)
 722     InnerIndexVarInc =
 723         dyn_cast<Instruction>(InnerInductionVar->getIncomingValue(1));
 724   else
 725     InnerIndexVarInc =
 726         dyn_cast<Instruction>(InnerInductionVar->getIncomingValue(0));
 727
 728   if (!InnerIndexVarInc)
 729     return true;
 730
 731   // Since we split the inner loop latch on this induction variable. Make sure
 732   // we do not have any instruction between the induction variable and branch
 733   // instruction.
 734
 735   for (auto I = InnerLoopLatch->rbegin(), E = InnerLoopLatch->rend();
 736        I != E && !FoundInduction; ++I) {
 737     if (isa<BranchInst>(*I) || isa<CmpInst>(*I) || isa<TruncInst>(*I))
 738       continue;
 739     const Instruction &Ins = *I;
 740     // We found an instruction. If this is not induction variable then it is not
 741     // safe to split this loop latch.
 742     if (!Ins.isIdenticalTo(InnerIndexVarInc))
 743       return true;
 744     else
 745       FoundInduction = true;
 746   }
 747   // The loop latch ended and we didnt find the induction variable return as
 748   // current limitation.
 749   if (!FoundInduction)
 750     return true;
 751
 752   return false;
 753 }
 754
 755 bool LoopInterchangeLegality::canInterchangeLoops(unsigned InnerLoopId,
 756                                                   unsigned OuterLoopId,
 757                                                   CharMatrix &DepMatrix) {
 758
 759   if (!isLegalToInterChangeLoops(DepMatrix, InnerLoopId, OuterLoopId)) {
 760     DEBUG(dbgs() << "Failed interchange InnerLoopId = " << InnerLoopId
 761                  << "and OuterLoopId = " << OuterLoopId
 762                  << "due to dependence\n");
 763     return false;
 764   }
 765
 766   // Create unique Preheaders if we already do not have one.
 767   BasicBlock *OuterLoopPreHeader = OuterLoop->getLoopPreheader();
 768   BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
 769
 770   // Create  a unique outer preheader -
 771   // 1) If OuterLoop preheader is not present.
 772   // 2) If OuterLoop Preheader is same as OuterLoop Header
 773   // 3) If OuterLoop Preheader is same as Header of the previous loop.
 774   // 4) If OuterLoop Preheader is Entry node.
 775   if (!OuterLoopPreHeader || OuterLoopPreHeader == OuterLoop->getHeader() ||
 776       isa<PHINode>(OuterLoopPreHeader->begin()) ||
 777       !OuterLoopPreHeader->getUniquePredecessor()) {
 778     OuterLoopPreHeader = InsertPreheaderForLoop(OuterLoop, CurrentPass);
 779   }
 780
 781   if (!InnerLoopPreHeader || InnerLoopPreHeader == InnerLoop->getHeader() ||
 782       InnerLoopPreHeader == OuterLoop->getHeader()) {
 783     InnerLoopPreHeader = InsertPreheaderForLoop(InnerLoop, CurrentPass);
 784   }
 785
 786   // Check if the loops are tightly nested.
 787   if (!tightlyNested(OuterLoop, InnerLoop)) {
 788     DEBUG(dbgs() << "Loops not tightly nested\n");
 789     return false;
 790   }
 791
 792   // TODO: The loops could not be interchanged due to current limitations in the
 793   // transform module.
 794   if (currentLimitations()) {
 795     DEBUG(dbgs() << "Not legal because of current transform limitation\n");
 796     return false;
 797   }
 798
 799   return true;
 800 }
 801
 802 int LoopInterchangeProfitability::getInstrOrderCost() {
 803   unsigned GoodOrder, BadOrder;
 804   BadOrder = GoodOrder = 0;
 805   for (auto BI = InnerLoop->block_begin(), BE = InnerLoop->block_end();
 806        BI != BE; ++BI) {
 807     for (auto I = (*BI)->begin(), E = (*BI)->end(); I != E; ++I) {
 808       const Instruction &Ins = *I;
 809       if (const GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(&Ins)) {
 810         unsigned NumOp = GEP->getNumOperands();
 811         bool FoundInnerInduction = false;
 812         bool FoundOuterInduction = false;
 813         for (unsigned i = 0; i < NumOp; ++i) {
 814           const SCEV *OperandVal = SE->getSCEV(GEP->getOperand(i));
 815           const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(OperandVal);
 816           if (!AR)
 817             continue;
 818
 819           // If we find the inner induction after an outer induction e.g.
 820           // for(int i=0;i<N;i++)
 821           //   for(int j=0;j<N;j++)
 822           //     A[i][j] = A[i-1][j-1]+k;
 823           // then it is a good order.
 824           if (AR->getLoop() == InnerLoop) {
 825             // We found an InnerLoop induction after OuterLoop induction. It is
 826             // a good order.
 827             FoundInnerInduction = true;
 828             if (FoundOuterInduction) {
 829               GoodOrder++;
 830               break;
 831             }
 832           }
 833           // If we find the outer induction after an inner induction e.g.
 834           // for(int i=0;i<N;i++)
 835           //   for(int j=0;j<N;j++)
 836           //     A[j][i] = A[j-1][i-1]+k;
 837           // then it is a bad order.
 838           if (AR->getLoop() == OuterLoop) {
 839             // We found an OuterLoop induction after InnerLoop induction. It is
 840             // a bad order.
 841             FoundOuterInduction = true;
 842             if (FoundInnerInduction) {
 843               BadOrder++;
 844               break;
 845             }
 846           }
 847         }
 848       }
 849     }
 850   }
 851   return GoodOrder - BadOrder;
 852 }
 853
 854 static bool isProfitabileForVectorization(unsigned InnerLoopId,
 855                                           unsigned OuterLoopId,
 856                                           CharMatrix &DepMatrix) {
 857   // TODO: Improve this heuristic to catch more cases.
 858   // If the inner loop is loop independent or doesn't carry any dependency it is
 859   // profitable to move this to outer position.
 860   unsigned Row = DepMatrix.size();
 861   for (unsigned i = 0; i < Row; ++i) {
 862     if (DepMatrix[i][InnerLoopId] != 'S' && DepMatrix[i][InnerLoopId] != 'I')
 863       return false;
 864     // TODO: We need to improve this heuristic.
 865     if (DepMatrix[i][OuterLoopId] != '=')
 866       return false;
 867   }
 868   // If outer loop has dependence and inner loop is loop independent then it is
 869   // profitable to interchange to enable parallelism.
 870   return true;
 871 }
 872
 873 bool LoopInterchangeProfitability::isProfitable(unsigned InnerLoopId,
 874                                                 unsigned OuterLoopId,
 875                                                 CharMatrix &DepMatrix) {
 876
 877   // TODO: Add Better Profitibility checks.
 878   // e.g
 879   // 1) Construct dependency matrix and move the one with no loop carried dep
 880   //    inside to enable vectorization.
 881
 882   // This is rough cost estimation algorithm. It counts the good and bad order
 883   // of induction variables in the instruction and allows reordering if number
 884   // of bad orders is more than good.
 885   int Cost = 0;
 886   Cost += getInstrOrderCost();
 887   DEBUG(dbgs() << "Cost = " << Cost << "\n");
 888   if (Cost < 0)
 889     return true;
 890
 891   // It is not profitable as per current cache profitibility model. But check if
 892   // we can move this loop outside to improve parallelism.
 893   bool ImprovesPar =
 894       isProfitabileForVectorization(InnerLoopId, OuterLoopId, DepMatrix);
 895   return ImprovesPar;
 896 }
 897
 898 void LoopInterchangeTransform::removeChildLoop(Loop *OuterLoop,
 899                                                Loop *InnerLoop) {
 900   for (Loop::iterator I = OuterLoop->begin(), E = OuterLoop->end(); I != E;
 901        ++I) {
 902     if (*I == InnerLoop) {
 903       OuterLoop->removeChildLoop(I);
 904       return;
 905     }
 906   }
 907   assert(false && "Couldn't find loop");
 908 }
 909
 910 void LoopInterchangeTransform::restructureLoops(Loop *InnerLoop,
 911                                                 Loop *OuterLoop) {
 912   Loop *OuterLoopParent = OuterLoop->getParentLoop();
 913   if (OuterLoopParent) {
 914     // Remove the loop from its parent loop.
 915     removeChildLoop(OuterLoopParent, OuterLoop);
 916     removeChildLoop(OuterLoop, InnerLoop);
 917     OuterLoopParent->addChildLoop(InnerLoop);
 918   } else {
 919     removeChildLoop(OuterLoop, InnerLoop);
 920     LI->changeTopLevelLoop(OuterLoop, InnerLoop);
 921   }
 922
 923   for (Loop::iterator I = InnerLoop->begin(), E = InnerLoop->end(); I != E; ++I)
 924     OuterLoop->addChildLoop(InnerLoop->removeChildLoop(I));
 925
 926   InnerLoop->addChildLoop(OuterLoop);
 927 }
 928
 929 bool LoopInterchangeTransform::transform() {
 930
 931   DEBUG(dbgs() << "transform\n");
 932   bool Transformed = false;
 933   Instruction *InnerIndexVar;
 934
 935   if (InnerLoop->getSubLoops().size() == 0) {
 936     BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
 937     DEBUG(dbgs() << "Calling Split Inner Loop\n");
 938     PHINode *InductionPHI = getInductionVariable(InnerLoop, SE);
 939     if (!InductionPHI) {
 940       DEBUG(dbgs() << "Failed to find the point to split loop latch \n");
 941       return false;
 942     }
 943
 944     if (InductionPHI->getIncomingBlock(0) == InnerLoopPreHeader)
 945       InnerIndexVar = dyn_cast<Instruction>(InductionPHI->getIncomingValue(1));
 946     else
 947       InnerIndexVar = dyn_cast<Instruction>(InductionPHI->getIncomingValue(0));
 948
 949     //
 950     // Split at the place were the induction variable is
 951     // incremented/decremented.
 952     // TODO: This splitting logic may not work always. Fix this.
 953     splitInnerLoopLatch(InnerIndexVar);
 954     DEBUG(dbgs() << "splitInnerLoopLatch Done\n");
 955
 956     // Splits the inner loops phi nodes out into a seperate basic block.
 957     splitInnerLoopHeader();
 958     DEBUG(dbgs() << "splitInnerLoopHeader Done\n");
 959   }
 960
 961   Transformed |= adjustLoopLinks();
 962   if (!Transformed) {
 963     DEBUG(dbgs() << "adjustLoopLinks Failed\n");
 964     return false;
 965   }
 966
 967   restructureLoops(InnerLoop, OuterLoop);
 968   return true;
 969 }
 970
 971 void LoopInterchangeTransform::splitInnerLoopLatch(Instruction *Inc) {
 972   BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch();
 973   BasicBlock *InnerLoopLatchPred = InnerLoopLatch;
 974   InnerLoopLatch = SplitBlock(InnerLoopLatchPred, Inc, DT, LI);
 975 }
 976
 977 void LoopInterchangeTransform::splitOuterLoopLatch() {
 978   BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch();
 979   BasicBlock *OuterLatchLcssaPhiBlock = OuterLoopLatch;
 980   OuterLoopLatch = SplitBlock(OuterLatchLcssaPhiBlock,
 981                               OuterLoopLatch->getFirstNonPHI(), DT, LI);
 982 }
 983
 984 void LoopInterchangeTransform::splitInnerLoopHeader() {
 985
 986   // Split the inner loop header out.
 987   BasicBlock *InnerLoopHeader = InnerLoop->getHeader();
 988   SplitBlock(InnerLoopHeader, InnerLoopHeader->getFirstNonPHI(), DT, LI);
 989
 990   DEBUG(dbgs() << "Output of splitInnerLoopHeader InnerLoopHeaderSucc & "
 991                   "InnerLoopHeader \n");
 992 }
 993
 994 /// \brief Move all instructions except the terminator from FromBB right before
 995 /// InsertBefore
 996 static void moveBBContents(BasicBlock *FromBB, Instruction *InsertBefore) {
 997   auto &ToList = InsertBefore->getParent()->getInstList();
 998   auto &FromList = FromBB->getInstList();
 999
1000   ToList.splice(InsertBefore, FromList, FromList.begin(),
1001                 FromBB->getTerminator());
1002 }
1003
1004 void LoopInterchangeTransform::adjustOuterLoopPreheader() {
1005   BasicBlock *OuterLoopPreHeader = OuterLoop->getLoopPreheader();
1006   BasicBlock *InnerPreHeader = InnerLoop->getLoopPreheader();
1007
1008   moveBBContents(OuterLoopPreHeader, InnerPreHeader->getTerminator());
1009 }
1010
1011 void LoopInterchangeTransform::adjustInnerLoopPreheader() {
1012   BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
1013   BasicBlock *OuterHeader = OuterLoop->getHeader();
1014
1015   moveBBContents(InnerLoopPreHeader, OuterHeader->getTerminator());
1016 }
1017
1018 bool LoopInterchangeTransform::adjustLoopBranches() {
1019
1020   DEBUG(dbgs() << "adjustLoopBranches called\n");
1021   // Adjust the loop preheader
1022   BasicBlock *InnerLoopHeader = InnerLoop->getHeader();
1023   BasicBlock *OuterLoopHeader = OuterLoop->getHeader();
1024   BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch();
1025   BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch();
1026   BasicBlock *OuterLoopPreHeader = OuterLoop->getLoopPreheader();
1027   BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
1028   BasicBlock *OuterLoopPredecessor = OuterLoopPreHeader->getUniquePredecessor();
1029   BasicBlock *InnerLoopLatchPredecessor =
1030       InnerLoopLatch->getUniquePredecessor();
1031   BasicBlock *InnerLoopLatchSuccessor;
1032   BasicBlock *OuterLoopLatchSuccessor;
1033
1034   BranchInst *OuterLoopLatchBI =
1035       dyn_cast<BranchInst>(OuterLoopLatch->getTerminator());
1036   BranchInst *InnerLoopLatchBI =
1037       dyn_cast<BranchInst>(InnerLoopLatch->getTerminator());
1038   BranchInst *OuterLoopHeaderBI =
1039       dyn_cast<BranchInst>(OuterLoopHeader->getTerminator());
1040   BranchInst *InnerLoopHeaderBI =
1041       dyn_cast<BranchInst>(InnerLoopHeader->getTerminator());
1042
1043   if (!OuterLoopPredecessor || !InnerLoopLatchPredecessor ||
1044       !OuterLoopLatchBI || !InnerLoopLatchBI || !OuterLoopHeaderBI ||
1045       !InnerLoopHeaderBI)
1046     return false;
1047
1048   BranchInst *InnerLoopLatchPredecessorBI =
1049       dyn_cast<BranchInst>(InnerLoopLatchPredecessor->getTerminator());
1050   BranchInst *OuterLoopPredecessorBI =
1051       dyn_cast<BranchInst>(OuterLoopPredecessor->getTerminator());
1052
1053   if (!OuterLoopPredecessorBI || !InnerLoopLatchPredecessorBI)
1054     return false;
1055   BasicBlock *InnerLoopHeaderSucessor = InnerLoopHeader->getUniqueSuccessor();
1056   if (!InnerLoopHeaderSucessor)
1057     return false;
1058
1059   // Adjust Loop Preheader and headers
1060
1061   unsigned NumSucc = OuterLoopPredecessorBI->getNumSuccessors();
1062   for (unsigned i = 0; i < NumSucc; ++i) {
1063     if (OuterLoopPredecessorBI->getSuccessor(i) == OuterLoopPreHeader)
1064       OuterLoopPredecessorBI->setSuccessor(i, InnerLoopPreHeader);
1065   }
1066
1067   NumSucc = OuterLoopHeaderBI->getNumSuccessors();
1068   for (unsigned i = 0; i < NumSucc; ++i) {
1069     if (OuterLoopHeaderBI->getSuccessor(i) == OuterLoopLatch)
1070       OuterLoopHeaderBI->setSuccessor(i, LoopExit);
1071     else if (OuterLoopHeaderBI->getSuccessor(i) == InnerLoopPreHeader)
1072       OuterLoopHeaderBI->setSuccessor(i, InnerLoopHeaderSucessor);
1073   }
1074
1075   BranchInst::Create(OuterLoopPreHeader, InnerLoopHeaderBI);
1076   InnerLoopHeaderBI->eraseFromParent();
1077
1078   // -------------Adjust loop latches-----------
1079   if (InnerLoopLatchBI->getSuccessor(0) == InnerLoopHeader)
1080     InnerLoopLatchSuccessor = InnerLoopLatchBI->getSuccessor(1);
1081   else
1082     InnerLoopLatchSuccessor = InnerLoopLatchBI->getSuccessor(0);
1083
1084   NumSucc = InnerLoopLatchPredecessorBI->getNumSuccessors();
1085   for (unsigned i = 0; i < NumSucc; ++i) {
1086     if (InnerLoopLatchPredecessorBI->getSuccessor(i) == InnerLoopLatch)
1087       InnerLoopLatchPredecessorBI->setSuccessor(i, InnerLoopLatchSuccessor);
1088   }
1089
1090   if (OuterLoopLatchBI->getSuccessor(0) == OuterLoopHeader)
1091     OuterLoopLatchSuccessor = OuterLoopLatchBI->getSuccessor(1);
1092   else
1093     OuterLoopLatchSuccessor = OuterLoopLatchBI->getSuccessor(0);
1094
1095   if (InnerLoopLatchBI->getSuccessor(1) == InnerLoopLatchSuccessor)
1096     InnerLoopLatchBI->setSuccessor(1, OuterLoopLatchSuccessor);
1097   else
1098     InnerLoopLatchBI->setSuccessor(0, OuterLoopLatchSuccessor);
1099
1100   if (OuterLoopLatchBI->getSuccessor(0) == OuterLoopLatchSuccessor) {
1101     OuterLoopLatchBI->setSuccessor(0, InnerLoopLatch);
1102   } else {
1103     OuterLoopLatchBI->setSuccessor(1, InnerLoopLatch);
1104   }
1105
1106   return true;
1107 }
1108 void LoopInterchangeTransform::adjustLoopPreheaders() {
1109
1110   // We have interchanged the preheaders so we need to interchange the data in
1111   // the preheader as well.
1112   // This is because the content of inner preheader was previously executed
1113   // inside the outer loop.
1114   BasicBlock *OuterLoopPreHeader = OuterLoop->getLoopPreheader();
1115   BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
1116   BasicBlock *OuterLoopHeader = OuterLoop->getHeader();
1117   BranchInst *InnerTermBI =
1118       cast<BranchInst>(InnerLoopPreHeader->getTerminator());
1119
1120   BasicBlock *HeaderSplit =
1121       SplitBlock(OuterLoopHeader, OuterLoopHeader->getTerminator(), DT, LI);
1122   Instruction *InsPoint = HeaderSplit->getFirstNonPHI();
1123   // These instructions should now be executed inside the loop.
1124   // Move instruction into a new block after outer header.
1125   moveBBContents(InnerLoopPreHeader, InsPoint);
1126   // These instructions were not executed previously in the loop so move them to
1127   // the older inner loop preheader.
1128   moveBBContents(OuterLoopPreHeader, InnerTermBI);
1129 }
1130
1131 bool LoopInterchangeTransform::adjustLoopLinks() {
1132
1133   // Adjust all branches in the inner and outer loop.
1134   bool Changed = adjustLoopBranches();
1135   if (Changed)
1136     adjustLoopPreheaders();
1137   return Changed;
1138 }
1139
1140 char LoopInterchange::ID = 0;
1141 INITIALIZE_PASS_BEGIN(LoopInterchange, "loop-interchange",
1142                       "Interchanges loops for cache reuse", false, false)
1143 INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
1144 INITIALIZE_PASS_DEPENDENCY(DependenceAnalysis)
1145 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
1146 INITIALIZE_PASS_DEPENDENCY(ScalarEvolution)
1147 INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
1148 INITIALIZE_PASS_DEPENDENCY(LCSSA)
1149 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
1150
1151 INITIALIZE_PASS_END(LoopInterchange, "loop-interchange",
1152                     "Interchanges loops for cache reuse", false, false)
1153
1154 Pass *llvm::createLoopInterchangePass() { return new LoopInterchange(); }