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                           LoopInfo *LI, DominatorTree *DT, bool PreserveLCSSA)
 335       : OuterLoop(Outer), InnerLoop(Inner), SE(SE), LI(LI), DT(DT),
 336         PreserveLCSSA(PreserveLCSSA), 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   ScalarEvolution *SE;
 361   LoopInfo *LI;
 362   DominatorTree *DT;
 363   bool PreserveLCSSA;
 364
 365   bool InnerLoopHasReduction;
 366 };
 367
 368 /// LoopInterchangeProfitability checks if it is profitable to interchange the
 369 /// loop.
 370 class LoopInterchangeProfitability {
 371 public:
 372   LoopInterchangeProfitability(Loop *Outer, Loop *Inner, ScalarEvolution *SE)
 373       : OuterLoop(Outer), InnerLoop(Inner), SE(SE) {}
 374
 375   /// Check if the loop interchange is profitable.
 376   bool isProfitable(unsigned InnerLoopId, unsigned OuterLoopId,
 377                     CharMatrix &DepMatrix);
 378
 379 private:
 380   int getInstrOrderCost();
 381
 382   Loop *OuterLoop;
 383   Loop *InnerLoop;
 384
 385   /// Scev analysis.
 386   ScalarEvolution *SE;
 387 };
 388
 389 /// LoopInterchangeTransform interchanges the loop.
 390 class LoopInterchangeTransform {
 391 public:
 392   LoopInterchangeTransform(Loop *Outer, Loop *Inner, ScalarEvolution *SE,
 393                            LoopInfo *LI, DominatorTree *DT,
 394                            BasicBlock *LoopNestExit,
 395                            bool InnerLoopContainsReductions)
 396       : OuterLoop(Outer), InnerLoop(Inner), SE(SE), LI(LI), DT(DT),
 397         LoopExit(LoopNestExit),
 398         InnerLoopHasReduction(InnerLoopContainsReductions) {}
 399
 400   /// Interchange OuterLoop and InnerLoop.
 401   bool transform();
 402   void restructureLoops(Loop *InnerLoop, Loop *OuterLoop);
 403   void removeChildLoop(Loop *OuterLoop, Loop *InnerLoop);
 404
 405 private:
 406   void splitInnerLoopLatch(Instruction *);
 407   void splitOuterLoopLatch();
 408   void splitInnerLoopHeader();
 409   bool adjustLoopLinks();
 410   void adjustLoopPreheaders();
 411   void adjustOuterLoopPreheader();
 412   void adjustInnerLoopPreheader();
 413   bool adjustLoopBranches();
 414   void updateIncomingBlock(BasicBlock *CurrBlock, BasicBlock *OldPred,
 415                            BasicBlock *NewPred);
 416
 417   Loop *OuterLoop;
 418   Loop *InnerLoop;
 419
 420   /// Scev analysis.
 421   ScalarEvolution *SE;
 422   LoopInfo *LI;
 423   DominatorTree *DT;
 424   BasicBlock *LoopExit;
 425   bool InnerLoopHasReduction;
 426 };
 427
 428 // Main LoopInterchange Pass.
 429 struct LoopInterchange : public FunctionPass {
 430   static char ID;
 431   ScalarEvolution *SE;
 432   LoopInfo *LI;
 433   DependenceAnalysis *DA;
 434   DominatorTree *DT;
 435   bool PreserveLCSSA;
 436   LoopInterchange()
 437       : FunctionPass(ID), SE(nullptr), LI(nullptr), DA(nullptr), DT(nullptr) {
 438     initializeLoopInterchangePass(*PassRegistry::getPassRegistry());
 439   }
 440
 441   void getAnalysisUsage(AnalysisUsage &AU) const override {
 442     AU.addRequired<ScalarEvolutionWrapperPass>();
 443     AU.addRequired<AAResultsWrapperPass>();
 444     AU.addRequired<DominatorTreeWrapperPass>();
 445     AU.addRequired<LoopInfoWrapperPass>();
 446     AU.addRequired<DependenceAnalysis>();
 447     AU.addRequiredID(LoopSimplifyID);
 448     AU.addRequiredID(LCSSAID);
 449   }
 450
 451   bool runOnFunction(Function &F) override {
 452     SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
 453     LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
 454     DA = &getAnalysis<DependenceAnalysis>();
 455     auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();
 456     DT = DTWP ? &DTWP->getDomTree() : nullptr;
 457     PreserveLCSSA = mustPreserveAnalysisID(LCSSAID);
 458
 459     // Build up a worklist of loop pairs to analyze.
 460     SmallVector<LoopVector, 8> Worklist;
 461
 462     for (Loop *L : *LI)
 463       populateWorklist(*L, Worklist);
 464
 465     DEBUG(dbgs() << "Worklist size = " << Worklist.size() << "\n");
 466     bool Changed = true;
 467     while (!Worklist.empty()) {
 468       LoopVector LoopList = Worklist.pop_back_val();
 469       Changed = processLoopList(LoopList, F);
 470     }
 471     return Changed;
 472   }
 473
 474   bool isComputableLoopNest(LoopVector LoopList) {
 475     for (auto I = LoopList.begin(), E = LoopList.end(); I != E; ++I) {
 476       Loop *L = *I;
 477       const SCEV *ExitCountOuter = SE->getBackedgeTakenCount(L);
 478       if (ExitCountOuter == SE->getCouldNotCompute()) {
 479         DEBUG(dbgs() << "Couldn't compute Backedge count\n");
 480         return false;
 481       }
 482       if (L->getNumBackEdges() != 1) {
 483         DEBUG(dbgs() << "NumBackEdges is not equal to 1\n");
 484         return false;
 485       }
 486       if (!L->getExitingBlock()) {
 487         DEBUG(dbgs() << "Loop Doesn't have unique exit block\n");
 488         return false;
 489       }
 490     }
 491     return true;
 492   }
 493
 494   unsigned selectLoopForInterchange(LoopVector LoopList) {
 495     // TODO: Add a better heuristic to select the loop to be interchanged based
 496     // on the dependence matrix. Currently we select the innermost loop.
 497     return LoopList.size() - 1;
 498   }
 499
 500   bool processLoopList(LoopVector LoopList, Function &F) {
 501
 502     bool Changed = false;
 503     CharMatrix DependencyMatrix;
 504     if (LoopList.size() < 2) {
 505       DEBUG(dbgs() << "Loop doesn't contain minimum nesting level.\n");
 506       return false;
 507     }
 508     if (!isComputableLoopNest(LoopList)) {
 509       DEBUG(dbgs() << "Not vaild loop candidate for interchange\n");
 510       return false;
 511     }
 512     Loop *OuterMostLoop = *(LoopList.begin());
 513
 514     DEBUG(dbgs() << "Processing LoopList of size = " << LoopList.size()
 515                  << "\n");
 516
 517     if (!populateDependencyMatrix(DependencyMatrix, LoopList.size(),
 518                                   OuterMostLoop, DA)) {
 519       DEBUG(dbgs() << "Populating Dependency matrix failed\n");
 520       return false;
 521     }
 522 #ifdef DUMP_DEP_MATRICIES
 523     DEBUG(dbgs() << "Dependence before inter change \n");
 524     printDepMatrix(DependencyMatrix);
 525 #endif
 526
 527     BasicBlock *OuterMostLoopLatch = OuterMostLoop->getLoopLatch();
 528     BranchInst *OuterMostLoopLatchBI =
 529         dyn_cast<BranchInst>(OuterMostLoopLatch->getTerminator());
 530     if (!OuterMostLoopLatchBI)
 531       return false;
 532
 533     // Since we currently do not handle LCSSA PHI's any failure in loop
 534     // condition will now branch to LoopNestExit.
 535     // TODO: This should be removed once we handle LCSSA PHI nodes.
 536
 537     // Get the Outermost loop exit.
 538     BasicBlock *LoopNestExit;
 539     if (OuterMostLoopLatchBI->getSuccessor(0) == OuterMostLoop->getHeader())
 540       LoopNestExit = OuterMostLoopLatchBI->getSuccessor(1);
 541     else
 542       LoopNestExit = OuterMostLoopLatchBI->getSuccessor(0);
 543
 544     if (isa<PHINode>(LoopNestExit->begin())) {
 545       DEBUG(dbgs() << "PHI Nodes in loop nest exit is not handled for now "
 546                       "since on failure all loops branch to loop nest exit.\n");
 547       return false;
 548     }
 549
 550     unsigned SelecLoopId = selectLoopForInterchange(LoopList);
 551     // Move the selected loop outwards to the best possible position.
 552     for (unsigned i = SelecLoopId; i > 0; i--) {
 553       bool Interchanged =
 554           processLoop(LoopList, i, i - 1, LoopNestExit, DependencyMatrix);
 555       if (!Interchanged)
 556         return Changed;
 557       // Loops interchanged reflect the same in LoopList
 558       std::swap(LoopList[i - 1], LoopList[i]);
 559
 560       // Update the DependencyMatrix
 561       interChangeDepedencies(DependencyMatrix, i, i - 1);
 562       DT->recalculate(F);
 563 #ifdef DUMP_DEP_MATRICIES
 564       DEBUG(dbgs() << "Dependence after inter change \n");
 565       printDepMatrix(DependencyMatrix);
 566 #endif
 567       Changed |= Interchanged;
 568     }
 569     return Changed;
 570   }
 571
 572   bool processLoop(LoopVector LoopList, unsigned InnerLoopId,
 573                    unsigned OuterLoopId, BasicBlock *LoopNestExit,
 574                    std::vector<std::vector<char>> &DependencyMatrix) {
 575
 576     DEBUG(dbgs() << "Processing Innder Loop Id = " << InnerLoopId
 577                  << " and OuterLoopId = " << OuterLoopId << "\n");
 578     Loop *InnerLoop = LoopList[InnerLoopId];
 579     Loop *OuterLoop = LoopList[OuterLoopId];
 580
 581     LoopInterchangeLegality LIL(OuterLoop, InnerLoop, SE, LI, DT,
 582                                 PreserveLCSSA);
 583     if (!LIL.canInterchangeLoops(InnerLoopId, OuterLoopId, DependencyMatrix)) {
 584       DEBUG(dbgs() << "Not interchanging Loops. Cannot prove legality\n");
 585       return false;
 586     }
 587     DEBUG(dbgs() << "Loops are legal to interchange\n");
 588     LoopInterchangeProfitability LIP(OuterLoop, InnerLoop, SE);
 589     if (!LIP.isProfitable(InnerLoopId, OuterLoopId, DependencyMatrix)) {
 590       DEBUG(dbgs() << "Interchanging Loops not profitable\n");
 591       return false;
 592     }
 593
 594     LoopInterchangeTransform LIT(OuterLoop, InnerLoop, SE, LI, DT,
 595                                  LoopNestExit, LIL.hasInnerLoopReduction());
 596     LIT.transform();
 597     DEBUG(dbgs() << "Loops interchanged\n");
 598     return true;
 599   }
 600 };
 601
 602 } // end of namespace
 603 bool LoopInterchangeLegality::areAllUsesReductions(Instruction *Ins, Loop *L) {
 604   return !std::any_of(Ins->user_begin(), Ins->user_end(), [=](User *U) -> bool {
 605     PHINode *UserIns = dyn_cast<PHINode>(U);
 606     RecurrenceDescriptor RD;
 607     return !UserIns || !RecurrenceDescriptor::isReductionPHI(UserIns, L, RD);
 608   });
 609 }
 610
 611 bool LoopInterchangeLegality::containsUnsafeInstructionsInHeader(
 612     BasicBlock *BB) {
 613   for (auto I = BB->begin(), E = BB->end(); I != E; ++I) {
 614     // Load corresponding to reduction PHI's are safe while concluding if
 615     // tightly nested.
 616     if (LoadInst *L = dyn_cast<LoadInst>(I)) {
 617       if (!areAllUsesReductions(L, InnerLoop))
 618         return true;
 619     } else if (I->mayHaveSideEffects() || I->mayReadFromMemory())
 620       return true;
 621   }
 622   return false;
 623 }
 624
 625 bool LoopInterchangeLegality::containsUnsafeInstructionsInLatch(
 626     BasicBlock *BB) {
 627   for (auto I = BB->begin(), E = BB->end(); I != E; ++I) {
 628     // Stores corresponding to reductions are safe while concluding if tightly
 629     // nested.
 630     if (StoreInst *L = dyn_cast<StoreInst>(I)) {
 631       PHINode *PHI = dyn_cast<PHINode>(L->getOperand(0));
 632       if (!PHI)
 633         return true;
 634     } else if (I->mayHaveSideEffects() || I->mayReadFromMemory())
 635       return true;
 636   }
 637   return false;
 638 }
 639
 640 bool LoopInterchangeLegality::tightlyNested(Loop *OuterLoop, Loop *InnerLoop) {
 641   BasicBlock *OuterLoopHeader = OuterLoop->getHeader();
 642   BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
 643   BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch();
 644
 645   DEBUG(dbgs() << "Checking if Loops are Tightly Nested\n");
 646
 647   // A perfectly nested loop will not have any branch in between the outer and
 648   // inner block i.e. outer header will branch to either inner preheader and
 649   // outerloop latch.
 650   BranchInst *outerLoopHeaderBI =
 651       dyn_cast<BranchInst>(OuterLoopHeader->getTerminator());
 652   if (!outerLoopHeaderBI)
 653     return false;
 654   unsigned num = outerLoopHeaderBI->getNumSuccessors();
 655   for (unsigned i = 0; i < num; i++) {
 656     if (outerLoopHeaderBI->getSuccessor(i) != InnerLoopPreHeader &&
 657         outerLoopHeaderBI->getSuccessor(i) != OuterLoopLatch)
 658       return false;
 659   }
 660
 661   DEBUG(dbgs() << "Checking instructions in Loop header and Loop latch \n");
 662   // We do not have any basic block in between now make sure the outer header
 663   // and outer loop latch doesn't contain any unsafe instructions.
 664   if (containsUnsafeInstructionsInHeader(OuterLoopHeader) ||
 665       containsUnsafeInstructionsInLatch(OuterLoopLatch))
 666     return false;
 667
 668   DEBUG(dbgs() << "Loops are perfectly nested \n");
 669   // We have a perfect loop nest.
 670   return true;
 671 }
 672
 673
 674 bool LoopInterchangeLegality::isLoopStructureUnderstood(
 675     PHINode *InnerInduction) {
 676
 677   unsigned Num = InnerInduction->getNumOperands();
 678   BasicBlock *InnerLoopPreheader = InnerLoop->getLoopPreheader();
 679   for (unsigned i = 0; i < Num; ++i) {
 680     Value *Val = InnerInduction->getOperand(i);
 681     if (isa<Constant>(Val))
 682       continue;
 683     Instruction *I = dyn_cast<Instruction>(Val);
 684     if (!I)
 685       return false;
 686     // TODO: Handle triangular loops.
 687     // e.g. for(int i=0;i<N;i++)
 688     //        for(int j=i;j<N;j++)
 689     unsigned IncomBlockIndx = PHINode::getIncomingValueNumForOperand(i);
 690     if (InnerInduction->getIncomingBlock(IncomBlockIndx) ==
 691             InnerLoopPreheader &&
 692         !OuterLoop->isLoopInvariant(I)) {
 693       return false;
 694     }
 695   }
 696   return true;
 697 }
 698
 699 bool LoopInterchangeLegality::findInductionAndReductions(
 700     Loop *L, SmallVector<PHINode *, 8> &Inductions,
 701     SmallVector<PHINode *, 8> &Reductions) {
 702   if (!L->getLoopLatch() || !L->getLoopPredecessor())
 703     return false;
 704   for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) {
 705     RecurrenceDescriptor RD;
 706     InductionDescriptor ID;
 707     PHINode *PHI = cast<PHINode>(I);
 708     if (InductionDescriptor::isInductionPHI(PHI, SE, ID))
 709       Inductions.push_back(PHI);
 710     else if (RecurrenceDescriptor::isReductionPHI(PHI, L, RD))
 711       Reductions.push_back(PHI);
 712     else {
 713       DEBUG(
 714           dbgs() << "Failed to recognize PHI as an induction or reduction.\n");
 715       return false;
 716     }
 717   }
 718   return true;
 719 }
 720
 721 static bool containsSafePHI(BasicBlock *Block, bool isOuterLoopExitBlock) {
 722   for (auto I = Block->begin(); isa<PHINode>(I); ++I) {
 723     PHINode *PHI = cast<PHINode>(I);
 724     // Reduction lcssa phi will have only 1 incoming block that from loop latch.
 725     if (PHI->getNumIncomingValues() > 1)
 726       return false;
 727     Instruction *Ins = dyn_cast<Instruction>(PHI->getIncomingValue(0));
 728     if (!Ins)
 729       return false;
 730     // Incoming value for lcssa phi's in outer loop exit can only be inner loop
 731     // exits lcssa phi else it would not be tightly nested.
 732     if (!isa<PHINode>(Ins) && isOuterLoopExitBlock)
 733       return false;
 734   }
 735   return true;
 736 }
 737
 738 static BasicBlock *getLoopLatchExitBlock(BasicBlock *LatchBlock,
 739                                          BasicBlock *LoopHeader) {
 740   if (BranchInst *BI = dyn_cast<BranchInst>(LatchBlock->getTerminator())) {
 741     unsigned Num = BI->getNumSuccessors();
 742     assert(Num == 2);
 743     for (unsigned i = 0; i < Num; ++i) {
 744       if (BI->getSuccessor(i) == LoopHeader)
 745         continue;
 746       return BI->getSuccessor(i);
 747     }
 748   }
 749   return nullptr;
 750 }
 751
 752 // This function indicates the current limitations in the transform as a result
 753 // of which we do not proceed.
 754 bool LoopInterchangeLegality::currentLimitations() {
 755
 756   BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
 757   BasicBlock *InnerLoopHeader = InnerLoop->getHeader();
 758   BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch();
 759   BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch();
 760   BasicBlock *OuterLoopHeader = OuterLoop->getHeader();
 761
 762   PHINode *InnerInductionVar;
 763   SmallVector<PHINode *, 8> Inductions;
 764   SmallVector<PHINode *, 8> Reductions;
 765   if (!findInductionAndReductions(InnerLoop, Inductions, Reductions))
 766     return true;
 767
 768   // TODO: Currently we handle only loops with 1 induction variable.
 769   if (Inductions.size() != 1) {
 770     DEBUG(dbgs() << "We currently only support loops with 1 induction variable."
 771                  << "Failed to interchange due to current limitation\n");
 772     return true;
 773   }
 774   if (Reductions.size() > 0)
 775     InnerLoopHasReduction = true;
 776
 777   InnerInductionVar = Inductions.pop_back_val();
 778   Reductions.clear();
 779   if (!findInductionAndReductions(OuterLoop, Inductions, Reductions))
 780     return true;
 781
 782   // Outer loop cannot have reduction because then loops will not be tightly
 783   // nested.
 784   if (!Reductions.empty())
 785     return true;
 786   // TODO: Currently we handle only loops with 1 induction variable.
 787   if (Inductions.size() != 1)
 788     return true;
 789
 790   // TODO: Triangular loops are not handled for now.
 791   if (!isLoopStructureUnderstood(InnerInductionVar)) {
 792     DEBUG(dbgs() << "Loop structure not understood by pass\n");
 793     return true;
 794   }
 795
 796   // TODO: We only handle LCSSA PHI's corresponding to reduction for now.
 797   BasicBlock *LoopExitBlock =
 798       getLoopLatchExitBlock(OuterLoopLatch, OuterLoopHeader);
 799   if (!LoopExitBlock || !containsSafePHI(LoopExitBlock, true))
 800     return true;
 801
 802   LoopExitBlock = getLoopLatchExitBlock(InnerLoopLatch, InnerLoopHeader);
 803   if (!LoopExitBlock || !containsSafePHI(LoopExitBlock, false))
 804     return true;
 805
 806   // TODO: Current limitation: Since we split the inner loop latch at the point
 807   // were induction variable is incremented (induction.next); We cannot have
 808   // more than 1 user of induction.next since it would result in broken code
 809   // after split.
 810   // e.g.
 811   // for(i=0;i<N;i++) {
 812   //    for(j = 0;j<M;j++) {
 813   //      A[j+1][i+2] = A[j][i]+k;
 814   //  }
 815   // }
 816   bool FoundInduction = false;
 817   Instruction *InnerIndexVarInc = nullptr;
 818   if (InnerInductionVar->getIncomingBlock(0) == InnerLoopPreHeader)
 819     InnerIndexVarInc =
 820         dyn_cast<Instruction>(InnerInductionVar->getIncomingValue(1));
 821   else
 822     InnerIndexVarInc =
 823         dyn_cast<Instruction>(InnerInductionVar->getIncomingValue(0));
 824
 825   if (!InnerIndexVarInc)
 826     return true;
 827
 828   // Since we split the inner loop latch on this induction variable. Make sure
 829   // we do not have any instruction between the induction variable and branch
 830   // instruction.
 831
 832   for (auto I = InnerLoopLatch->rbegin(), E = InnerLoopLatch->rend();
 833        I != E && !FoundInduction; ++I) {
 834     if (isa<BranchInst>(*I) || isa<CmpInst>(*I) || isa<TruncInst>(*I))
 835       continue;
 836     const Instruction &Ins = *I;
 837     // We found an instruction. If this is not induction variable then it is not
 838     // safe to split this loop latch.
 839     if (!Ins.isIdenticalTo(InnerIndexVarInc))
 840       return true;
 841     else
 842       FoundInduction = true;
 843   }
 844   // The loop latch ended and we didn't find the induction variable return as
 845   // current limitation.
 846   if (!FoundInduction)
 847     return true;
 848
 849   return false;
 850 }
 851
 852 bool LoopInterchangeLegality::canInterchangeLoops(unsigned InnerLoopId,
 853                                                   unsigned OuterLoopId,
 854                                                   CharMatrix &DepMatrix) {
 855
 856   if (!isLegalToInterChangeLoops(DepMatrix, InnerLoopId, OuterLoopId)) {
 857     DEBUG(dbgs() << "Failed interchange InnerLoopId = " << InnerLoopId
 858                  << "and OuterLoopId = " << OuterLoopId
 859                  << "due to dependence\n");
 860     return false;
 861   }
 862
 863   // Create unique Preheaders if we already do not have one.
 864   BasicBlock *OuterLoopPreHeader = OuterLoop->getLoopPreheader();
 865   BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
 866
 867   // Create  a unique outer preheader -
 868   // 1) If OuterLoop preheader is not present.
 869   // 2) If OuterLoop Preheader is same as OuterLoop Header
 870   // 3) If OuterLoop Preheader is same as Header of the previous loop.
 871   // 4) If OuterLoop Preheader is Entry node.
 872   if (!OuterLoopPreHeader || OuterLoopPreHeader == OuterLoop->getHeader() ||
 873       isa<PHINode>(OuterLoopPreHeader->begin()) ||
 874       !OuterLoopPreHeader->getUniquePredecessor()) {
 875     OuterLoopPreHeader =
 876         InsertPreheaderForLoop(OuterLoop, DT, LI, PreserveLCSSA);
 877   }
 878
 879   if (!InnerLoopPreHeader || InnerLoopPreHeader == InnerLoop->getHeader() ||
 880       InnerLoopPreHeader == OuterLoop->getHeader()) {
 881     InnerLoopPreHeader =
 882         InsertPreheaderForLoop(InnerLoop, DT, LI, PreserveLCSSA);
 883   }
 884
 885   // TODO: The loops could not be interchanged due to current limitations in the
 886   // transform module.
 887   if (currentLimitations()) {
 888     DEBUG(dbgs() << "Not legal because of current transform limitation\n");
 889     return false;
 890   }
 891
 892   // Check if the loops are tightly nested.
 893   if (!tightlyNested(OuterLoop, InnerLoop)) {
 894     DEBUG(dbgs() << "Loops not tightly nested\n");
 895     return false;
 896   }
 897
 898   return true;
 899 }
 900
 901 int LoopInterchangeProfitability::getInstrOrderCost() {
 902   unsigned GoodOrder, BadOrder;
 903   BadOrder = GoodOrder = 0;
 904   for (auto BI = InnerLoop->block_begin(), BE = InnerLoop->block_end();
 905        BI != BE; ++BI) {
 906     for (auto I = (*BI)->begin(), E = (*BI)->end(); I != E; ++I) {
 907       const Instruction &Ins = *I;
 908       if (const GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(&Ins)) {
 909         unsigned NumOp = GEP->getNumOperands();
 910         bool FoundInnerInduction = false;
 911         bool FoundOuterInduction = false;
 912         for (unsigned i = 0; i < NumOp; ++i) {
 913           const SCEV *OperandVal = SE->getSCEV(GEP->getOperand(i));
 914           const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(OperandVal);
 915           if (!AR)
 916             continue;
 917
 918           // If we find the inner induction after an outer induction e.g.
 919           // for(int i=0;i<N;i++)
 920           //   for(int j=0;j<N;j++)
 921           //     A[i][j] = A[i-1][j-1]+k;
 922           // then it is a good order.
 923           if (AR->getLoop() == InnerLoop) {
 924             // We found an InnerLoop induction after OuterLoop induction. It is
 925             // a good order.
 926             FoundInnerInduction = true;
 927             if (FoundOuterInduction) {
 928               GoodOrder++;
 929               break;
 930             }
 931           }
 932           // If we find the outer induction after an inner induction e.g.
 933           // for(int i=0;i<N;i++)
 934           //   for(int j=0;j<N;j++)
 935           //     A[j][i] = A[j-1][i-1]+k;
 936           // then it is a bad order.
 937           if (AR->getLoop() == OuterLoop) {
 938             // We found an OuterLoop induction after InnerLoop induction. It is
 939             // a bad order.
 940             FoundOuterInduction = true;
 941             if (FoundInnerInduction) {
 942               BadOrder++;
 943               break;
 944             }
 945           }
 946         }
 947       }
 948     }
 949   }
 950   return GoodOrder - BadOrder;
 951 }
 952
 953 static bool isProfitabileForVectorization(unsigned InnerLoopId,
 954                                           unsigned OuterLoopId,
 955                                           CharMatrix &DepMatrix) {
 956   // TODO: Improve this heuristic to catch more cases.
 957   // If the inner loop is loop independent or doesn't carry any dependency it is
 958   // profitable to move this to outer position.
 959   unsigned Row = DepMatrix.size();
 960   for (unsigned i = 0; i < Row; ++i) {
 961     if (DepMatrix[i][InnerLoopId] != 'S' && DepMatrix[i][InnerLoopId] != 'I')
 962       return false;
 963     // TODO: We need to improve this heuristic.
 964     if (DepMatrix[i][OuterLoopId] != '=')
 965       return false;
 966   }
 967   // If outer loop has dependence and inner loop is loop independent then it is
 968   // profitable to interchange to enable parallelism.
 969   return true;
 970 }
 971
 972 bool LoopInterchangeProfitability::isProfitable(unsigned InnerLoopId,
 973                                                 unsigned OuterLoopId,
 974                                                 CharMatrix &DepMatrix) {
 975
 976   // TODO: Add better profitability checks.
 977   // e.g
 978   // 1) Construct dependency matrix and move the one with no loop carried dep
 979   //    inside to enable vectorization.
 980
 981   // This is rough cost estimation algorithm. It counts the good and bad order
 982   // of induction variables in the instruction and allows reordering if number
 983   // of bad orders is more than good.
 984   int Cost = 0;
 985   Cost += getInstrOrderCost();
 986   DEBUG(dbgs() << "Cost = " << Cost << "\n");
 987   if (Cost < 0)
 988     return true;
 989
 990   // It is not profitable as per current cache profitability model. But check if
 991   // we can move this loop outside to improve parallelism.
 992   bool ImprovesPar =
 993       isProfitabileForVectorization(InnerLoopId, OuterLoopId, DepMatrix);
 994   return ImprovesPar;
 995 }
 996
 997 void LoopInterchangeTransform::removeChildLoop(Loop *OuterLoop,
 998                                                Loop *InnerLoop) {
 999   for (Loop::iterator I = OuterLoop->begin(), E = OuterLoop->end(); I != E;
1000        ++I) {
1001     if (*I == InnerLoop) {
1002       OuterLoop->removeChildLoop(I);
1003       return;
1004     }
1005   }
1006   llvm_unreachable("Couldn't find loop");
1007 }
1008
1009 void LoopInterchangeTransform::restructureLoops(Loop *InnerLoop,
1010                                                 Loop *OuterLoop) {
1011   Loop *OuterLoopParent = OuterLoop->getParentLoop();
1012   if (OuterLoopParent) {
1013     // Remove the loop from its parent loop.
1014     removeChildLoop(OuterLoopParent, OuterLoop);
1015     removeChildLoop(OuterLoop, InnerLoop);
1016     OuterLoopParent->addChildLoop(InnerLoop);
1017   } else {
1018     removeChildLoop(OuterLoop, InnerLoop);
1019     LI->changeTopLevelLoop(OuterLoop, InnerLoop);
1020   }
1021
1022   while (!InnerLoop->empty())
1023     OuterLoop->addChildLoop(InnerLoop->removeChildLoop(InnerLoop->begin()));
1024
1025   InnerLoop->addChildLoop(OuterLoop);
1026 }
1027
1028 bool LoopInterchangeTransform::transform() {
1029
1030   DEBUG(dbgs() << "transform\n");
1031   bool Transformed = false;
1032   Instruction *InnerIndexVar;
1033
1034   if (InnerLoop->getSubLoops().size() == 0) {
1035     BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
1036     DEBUG(dbgs() << "Calling Split Inner Loop\n");
1037     PHINode *InductionPHI = getInductionVariable(InnerLoop, SE);
1038     if (!InductionPHI) {
1039       DEBUG(dbgs() << "Failed to find the point to split loop latch \n");
1040       return false;
1041     }
1042
1043     if (InductionPHI->getIncomingBlock(0) == InnerLoopPreHeader)
1044       InnerIndexVar = dyn_cast<Instruction>(InductionPHI->getIncomingValue(1));
1045     else
1046       InnerIndexVar = dyn_cast<Instruction>(InductionPHI->getIncomingValue(0));
1047
1048     //
1049     // Split at the place were the induction variable is
1050     // incremented/decremented.
1051     // TODO: This splitting logic may not work always. Fix this.
1052     splitInnerLoopLatch(InnerIndexVar);
1053     DEBUG(dbgs() << "splitInnerLoopLatch Done\n");
1054
1055     // Splits the inner loops phi nodes out into a separate basic block.
1056     splitInnerLoopHeader();
1057     DEBUG(dbgs() << "splitInnerLoopHeader Done\n");
1058   }
1059
1060   Transformed |= adjustLoopLinks();
1061   if (!Transformed) {
1062     DEBUG(dbgs() << "adjustLoopLinks Failed\n");
1063     return false;
1064   }
1065
1066   restructureLoops(InnerLoop, OuterLoop);
1067   return true;
1068 }
1069
1070 void LoopInterchangeTransform::splitInnerLoopLatch(Instruction *Inc) {
1071   BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch();
1072   BasicBlock *InnerLoopLatchPred = InnerLoopLatch;
1073   InnerLoopLatch = SplitBlock(InnerLoopLatchPred, Inc, DT, LI);
1074 }
1075
1076 void LoopInterchangeTransform::splitOuterLoopLatch() {
1077   BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch();
1078   BasicBlock *OuterLatchLcssaPhiBlock = OuterLoopLatch;
1079   OuterLoopLatch = SplitBlock(OuterLatchLcssaPhiBlock,
1080                               OuterLoopLatch->getFirstNonPHI(), DT, LI);
1081 }
1082
1083 void LoopInterchangeTransform::splitInnerLoopHeader() {
1084
1085   // Split the inner loop header out. Here make sure that the reduction PHI's
1086   // stay in the innerloop body.
1087   BasicBlock *InnerLoopHeader = InnerLoop->getHeader();
1088   BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
1089   if (InnerLoopHasReduction) {
1090     // FIXME: Check if the induction PHI will always be the first PHI.
1091     BasicBlock *New = InnerLoopHeader->splitBasicBlock(
1092         ++(InnerLoopHeader->begin()), InnerLoopHeader->getName() + ".split");
1093     if (LI)
1094       if (Loop *L = LI->getLoopFor(InnerLoopHeader))
1095         L->addBasicBlockToLoop(New, *LI);
1096
1097     // Adjust Reduction PHI's in the block.
1098     SmallVector<PHINode *, 8> PHIVec;
1099     for (auto I = New->begin(); isa<PHINode>(I); ++I) {
1100       PHINode *PHI = dyn_cast<PHINode>(I);
1101       Value *V = PHI->getIncomingValueForBlock(InnerLoopPreHeader);
1102       PHI->replaceAllUsesWith(V);
1103       PHIVec.push_back((PHI));
1104     }
1105     for (auto I = PHIVec.begin(), E = PHIVec.end(); I != E; ++I) {
1106       PHINode *P = *I;
1107       P->eraseFromParent();
1108     }
1109   } else {
1110     SplitBlock(InnerLoopHeader, InnerLoopHeader->getFirstNonPHI(), DT, LI);
1111   }
1112
1113   DEBUG(dbgs() << "Output of splitInnerLoopHeader InnerLoopHeaderSucc & "
1114                   "InnerLoopHeader \n");
1115 }
1116
1117 /// \brief Move all instructions except the terminator from FromBB right before
1118 /// InsertBefore
1119 static void moveBBContents(BasicBlock *FromBB, Instruction *InsertBefore) {
1120   auto &ToList = InsertBefore->getParent()->getInstList();
1121   auto &FromList = FromBB->getInstList();
1122
1123   ToList.splice(InsertBefore->getIterator(), FromList, FromList.begin(),
1124                 FromBB->getTerminator()->getIterator());
1125 }
1126
1127 void LoopInterchangeTransform::adjustOuterLoopPreheader() {
1128   BasicBlock *OuterLoopPreHeader = OuterLoop->getLoopPreheader();
1129   BasicBlock *InnerPreHeader = InnerLoop->getLoopPreheader();
1130
1131   moveBBContents(OuterLoopPreHeader, InnerPreHeader->getTerminator());
1132 }
1133
1134 void LoopInterchangeTransform::adjustInnerLoopPreheader() {
1135   BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
1136   BasicBlock *OuterHeader = OuterLoop->getHeader();
1137
1138   moveBBContents(InnerLoopPreHeader, OuterHeader->getTerminator());
1139 }
1140
1141 void LoopInterchangeTransform::updateIncomingBlock(BasicBlock *CurrBlock,
1142                                                    BasicBlock *OldPred,
1143                                                    BasicBlock *NewPred) {
1144   for (auto I = CurrBlock->begin(); isa<PHINode>(I); ++I) {
1145     PHINode *PHI = cast<PHINode>(I);
1146     unsigned Num = PHI->getNumIncomingValues();
1147     for (unsigned i = 0; i < Num; ++i) {
1148       if (PHI->getIncomingBlock(i) == OldPred)
1149         PHI->setIncomingBlock(i, NewPred);
1150     }
1151   }
1152 }
1153
1154 bool LoopInterchangeTransform::adjustLoopBranches() {
1155
1156   DEBUG(dbgs() << "adjustLoopBranches called\n");
1157   // Adjust the loop preheader
1158   BasicBlock *InnerLoopHeader = InnerLoop->getHeader();
1159   BasicBlock *OuterLoopHeader = OuterLoop->getHeader();
1160   BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch();
1161   BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch();
1162   BasicBlock *OuterLoopPreHeader = OuterLoop->getLoopPreheader();
1163   BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
1164   BasicBlock *OuterLoopPredecessor = OuterLoopPreHeader->getUniquePredecessor();
1165   BasicBlock *InnerLoopLatchPredecessor =
1166       InnerLoopLatch->getUniquePredecessor();
1167   BasicBlock *InnerLoopLatchSuccessor;
1168   BasicBlock *OuterLoopLatchSuccessor;
1169
1170   BranchInst *OuterLoopLatchBI =
1171       dyn_cast<BranchInst>(OuterLoopLatch->getTerminator());
1172   BranchInst *InnerLoopLatchBI =
1173       dyn_cast<BranchInst>(InnerLoopLatch->getTerminator());
1174   BranchInst *OuterLoopHeaderBI =
1175       dyn_cast<BranchInst>(OuterLoopHeader->getTerminator());
1176   BranchInst *InnerLoopHeaderBI =
1177       dyn_cast<BranchInst>(InnerLoopHeader->getTerminator());
1178
1179   if (!OuterLoopPredecessor || !InnerLoopLatchPredecessor ||
1180       !OuterLoopLatchBI || !InnerLoopLatchBI || !OuterLoopHeaderBI ||
1181       !InnerLoopHeaderBI)
1182     return false;
1183
1184   BranchInst *InnerLoopLatchPredecessorBI =
1185       dyn_cast<BranchInst>(InnerLoopLatchPredecessor->getTerminator());
1186   BranchInst *OuterLoopPredecessorBI =
1187       dyn_cast<BranchInst>(OuterLoopPredecessor->getTerminator());
1188
1189   if (!OuterLoopPredecessorBI || !InnerLoopLatchPredecessorBI)
1190     return false;
1191   BasicBlock *InnerLoopHeaderSuccessor = InnerLoopHeader->getUniqueSuccessor();
1192   if (!InnerLoopHeaderSuccessor)
1193     return false;
1194
1195   // Adjust Loop Preheader and headers
1196
1197   unsigned NumSucc = OuterLoopPredecessorBI->getNumSuccessors();
1198   for (unsigned i = 0; i < NumSucc; ++i) {
1199     if (OuterLoopPredecessorBI->getSuccessor(i) == OuterLoopPreHeader)
1200       OuterLoopPredecessorBI->setSuccessor(i, InnerLoopPreHeader);
1201   }
1202
1203   NumSucc = OuterLoopHeaderBI->getNumSuccessors();
1204   for (unsigned i = 0; i < NumSucc; ++i) {
1205     if (OuterLoopHeaderBI->getSuccessor(i) == OuterLoopLatch)
1206       OuterLoopHeaderBI->setSuccessor(i, LoopExit);
1207     else if (OuterLoopHeaderBI->getSuccessor(i) == InnerLoopPreHeader)
1208       OuterLoopHeaderBI->setSuccessor(i, InnerLoopHeaderSuccessor);
1209   }
1210
1211   // Adjust reduction PHI's now that the incoming block has changed.
1212   updateIncomingBlock(InnerLoopHeaderSuccessor, InnerLoopHeader,
1213                       OuterLoopHeader);
1214
1215   BranchInst::Create(OuterLoopPreHeader, InnerLoopHeaderBI);
1216   InnerLoopHeaderBI->eraseFromParent();
1217
1218   // -------------Adjust loop latches-----------
1219   if (InnerLoopLatchBI->getSuccessor(0) == InnerLoopHeader)
1220     InnerLoopLatchSuccessor = InnerLoopLatchBI->getSuccessor(1);
1221   else
1222     InnerLoopLatchSuccessor = InnerLoopLatchBI->getSuccessor(0);
1223
1224   NumSucc = InnerLoopLatchPredecessorBI->getNumSuccessors();
1225   for (unsigned i = 0; i < NumSucc; ++i) {
1226     if (InnerLoopLatchPredecessorBI->getSuccessor(i) == InnerLoopLatch)
1227       InnerLoopLatchPredecessorBI->setSuccessor(i, InnerLoopLatchSuccessor);
1228   }
1229
1230   // Adjust PHI nodes in InnerLoopLatchSuccessor. Update all uses of PHI with
1231   // the value and remove this PHI node from inner loop.
1232   SmallVector<PHINode *, 8> LcssaVec;
1233   for (auto I = InnerLoopLatchSuccessor->begin(); isa<PHINode>(I); ++I) {
1234     PHINode *LcssaPhi = cast<PHINode>(I);
1235     LcssaVec.push_back(LcssaPhi);
1236   }
1237   for (auto I = LcssaVec.begin(), E = LcssaVec.end(); I != E; ++I) {
1238     PHINode *P = *I;
1239     Value *Incoming = P->getIncomingValueForBlock(InnerLoopLatch);
1240     P->replaceAllUsesWith(Incoming);
1241     P->eraseFromParent();
1242   }
1243
1244   if (OuterLoopLatchBI->getSuccessor(0) == OuterLoopHeader)
1245     OuterLoopLatchSuccessor = OuterLoopLatchBI->getSuccessor(1);
1246   else
1247     OuterLoopLatchSuccessor = OuterLoopLatchBI->getSuccessor(0);
1248
1249   if (InnerLoopLatchBI->getSuccessor(1) == InnerLoopLatchSuccessor)
1250     InnerLoopLatchBI->setSuccessor(1, OuterLoopLatchSuccessor);
1251   else
1252     InnerLoopLatchBI->setSuccessor(0, OuterLoopLatchSuccessor);
1253
1254   updateIncomingBlock(OuterLoopLatchSuccessor, OuterLoopLatch, InnerLoopLatch);
1255
1256   if (OuterLoopLatchBI->getSuccessor(0) == OuterLoopLatchSuccessor) {
1257     OuterLoopLatchBI->setSuccessor(0, InnerLoopLatch);
1258   } else {
1259     OuterLoopLatchBI->setSuccessor(1, InnerLoopLatch);
1260   }
1261
1262   return true;
1263 }
1264 void LoopInterchangeTransform::adjustLoopPreheaders() {
1265
1266   // We have interchanged the preheaders so we need to interchange the data in
1267   // the preheader as well.
1268   // This is because the content of inner preheader was previously executed
1269   // inside the outer loop.
1270   BasicBlock *OuterLoopPreHeader = OuterLoop->getLoopPreheader();
1271   BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
1272   BasicBlock *OuterLoopHeader = OuterLoop->getHeader();
1273   BranchInst *InnerTermBI =
1274       cast<BranchInst>(InnerLoopPreHeader->getTerminator());
1275
1276   // These instructions should now be executed inside the loop.
1277   // Move instruction into a new block after outer header.
1278   moveBBContents(InnerLoopPreHeader, OuterLoopHeader->getTerminator());
1279   // These instructions were not executed previously in the loop so move them to
1280   // the older inner loop preheader.
1281   moveBBContents(OuterLoopPreHeader, InnerTermBI);
1282 }
1283
1284 bool LoopInterchangeTransform::adjustLoopLinks() {
1285
1286   // Adjust all branches in the inner and outer loop.
1287   bool Changed = adjustLoopBranches();
1288   if (Changed)
1289     adjustLoopPreheaders();
1290   return Changed;
1291 }
1292
1293 char LoopInterchange::ID = 0;
1294 INITIALIZE_PASS_BEGIN(LoopInterchange, "loop-interchange",
1295                       "Interchanges loops for cache reuse", false, false)
1296 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
1297 INITIALIZE_PASS_DEPENDENCY(DependenceAnalysis)
1298 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
1299 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
1300 INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
1301 INITIALIZE_PASS_DEPENDENCY(LCSSA)
1302 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
1303
1304 INITIALIZE_PASS_END(LoopInterchange, "loop-interchange",
1305                     "Interchanges loops for cache reuse", false, false)
1306
1307 Pass *llvm::createLoopInterchangePass() { return new LoopInterchange(); }