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