lib/Transforms/Scalar/LoopInterchange.cpp

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