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