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