| File: | src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Transforms/Scalar/LoopInterchange.cpp |
| Warning: | line 1576, column 7 Called C++ object pointer is null |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
| 1 | //===- LoopInterchange.cpp - Loop interchange pass-------------------------===// | |||
| 2 | // | |||
| 3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. | |||
| 4 | // See https://llvm.org/LICENSE.txt for license information. | |||
| 5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception | |||
| 6 | // | |||
| 7 | //===----------------------------------------------------------------------===// | |||
| 8 | // | |||
| 9 | // This Pass handles loop interchange transform. | |||
| 10 | // This pass interchanges loops to provide a more cache-friendly memory access | |||
| 11 | // patterns. | |||
| 12 | // | |||
| 13 | //===----------------------------------------------------------------------===// | |||
| 14 | ||||
| 15 | #include "llvm/Transforms/Scalar/LoopInterchange.h" | |||
| 16 | #include "llvm/ADT/STLExtras.h" | |||
| 17 | #include "llvm/ADT/SmallVector.h" | |||
| 18 | #include "llvm/ADT/Statistic.h" | |||
| 19 | #include "llvm/ADT/StringRef.h" | |||
| 20 | #include "llvm/Analysis/DependenceAnalysis.h" | |||
| 21 | #include "llvm/Analysis/LoopInfo.h" | |||
| 22 | #include "llvm/Analysis/LoopNestAnalysis.h" | |||
| 23 | #include "llvm/Analysis/LoopPass.h" | |||
| 24 | #include "llvm/Analysis/OptimizationRemarkEmitter.h" | |||
| 25 | #include "llvm/Analysis/ScalarEvolution.h" | |||
| 26 | #include "llvm/Analysis/ScalarEvolutionExpressions.h" | |||
| 27 | #include "llvm/IR/BasicBlock.h" | |||
| 28 | #include "llvm/IR/Constants.h" | |||
| 29 | #include "llvm/IR/DiagnosticInfo.h" | |||
| 30 | #include "llvm/IR/Dominators.h" | |||
| 31 | #include "llvm/IR/Function.h" | |||
| 32 | #include "llvm/IR/IRBuilder.h" | |||
| 33 | #include "llvm/IR/InstrTypes.h" | |||
| 34 | #include "llvm/IR/Instruction.h" | |||
| 35 | #include "llvm/IR/Instructions.h" | |||
| 36 | #include "llvm/IR/Type.h" | |||
| 37 | #include "llvm/IR/User.h" | |||
| 38 | #include "llvm/IR/Value.h" | |||
| 39 | #include "llvm/InitializePasses.h" | |||
| 40 | #include "llvm/Pass.h" | |||
| 41 | #include "llvm/Support/Casting.h" | |||
| 42 | #include "llvm/Support/CommandLine.h" | |||
| 43 | #include "llvm/Support/Debug.h" | |||
| 44 | #include "llvm/Support/ErrorHandling.h" | |||
| 45 | #include "llvm/Support/raw_ostream.h" | |||
| 46 | #include "llvm/Transforms/Scalar.h" | |||
| 47 | #include "llvm/Transforms/Utils.h" | |||
| 48 | #include "llvm/Transforms/Utils/BasicBlockUtils.h" | |||
| 49 | #include "llvm/Transforms/Utils/LoopUtils.h" | |||
| 50 | #include <cassert> | |||
| 51 | #include <utility> | |||
| 52 | #include <vector> | |||
| 53 | ||||
| 54 | using namespace llvm; | |||
| 55 | ||||
| 56 | #define DEBUG_TYPE"loop-interchange" "loop-interchange" | |||
| 57 | ||||
| 58 | STATISTIC(LoopsInterchanged, "Number of loops interchanged")static llvm::Statistic LoopsInterchanged = {"loop-interchange" , "LoopsInterchanged", "Number of loops interchanged"}; | |||
| 59 | ||||
| 60 | static cl::opt<int> LoopInterchangeCostThreshold( | |||
| 61 | "loop-interchange-threshold", cl::init(0), cl::Hidden, | |||
| 62 | cl::desc("Interchange if you gain more than this number")); | |||
| 63 | ||||
| 64 | namespace { | |||
| 65 | ||||
| 66 | using LoopVector = SmallVector<Loop *, 8>; | |||
| 67 | ||||
| 68 | // TODO: Check if we can use a sparse matrix here. | |||
| 69 | using CharMatrix = std::vector<std::vector<char>>; | |||
| 70 | ||||
| 71 | } // end anonymous namespace | |||
| 72 | ||||
| 73 | // Maximum number of dependencies that can be handled in the dependency matrix. | |||
| 74 | static const unsigned MaxMemInstrCount = 100; | |||
| 75 | ||||
| 76 | // Maximum loop depth supported. | |||
| 77 | static const unsigned MaxLoopNestDepth = 10; | |||
| 78 | ||||
| 79 | #ifdef DUMP_DEP_MATRICIES | |||
| 80 | static void printDepMatrix(CharMatrix &DepMatrix) { | |||
| 81 | for (auto &Row : DepMatrix) { | |||
| 82 | for (auto D : Row) | |||
| 83 | LLVM_DEBUG(dbgs() << D << " ")do { } while (false); | |||
| 84 | LLVM_DEBUG(dbgs() << "\n")do { } while (false); | |||
| 85 | } | |||
| 86 | } | |||
| 87 | #endif | |||
| 88 | ||||
| 89 | static bool populateDependencyMatrix(CharMatrix &DepMatrix, unsigned Level, | |||
| 90 | Loop *L, DependenceInfo *DI) { | |||
| 91 | using ValueVector = SmallVector<Value *, 16>; | |||
| 92 | ||||
| 93 | ValueVector MemInstr; | |||
| 94 | ||||
| 95 | // For each block. | |||
| 96 | for (BasicBlock *BB : L->blocks()) { | |||
| 97 | // Scan the BB and collect legal loads and stores. | |||
| 98 | for (Instruction &I : *BB) { | |||
| 99 | if (!isa<Instruction>(I)) | |||
| 100 | return false; | |||
| 101 | if (auto *Ld = dyn_cast<LoadInst>(&I)) { | |||
| 102 | if (!Ld->isSimple()) | |||
| 103 | return false; | |||
| 104 | MemInstr.push_back(&I); | |||
| 105 | } else if (auto *St = dyn_cast<StoreInst>(&I)) { | |||
| 106 | if (!St->isSimple()) | |||
| 107 | return false; | |||
| 108 | MemInstr.push_back(&I); | |||
| 109 | } | |||
| 110 | } | |||
| 111 | } | |||
| 112 | ||||
| 113 | LLVM_DEBUG(dbgs() << "Found " << MemInstr.size()do { } while (false) | |||
| 114 | << " Loads and Stores to analyze\n")do { } while (false); | |||
| 115 | ||||
| 116 | ValueVector::iterator I, IE, J, JE; | |||
| 117 | ||||
| 118 | for (I = MemInstr.begin(), IE = MemInstr.end(); I != IE; ++I) { | |||
| 119 | for (J = I, JE = MemInstr.end(); J != JE; ++J) { | |||
| 120 | std::vector<char> Dep; | |||
| 121 | Instruction *Src = cast<Instruction>(*I); | |||
| 122 | Instruction *Dst = cast<Instruction>(*J); | |||
| 123 | if (Src == Dst) | |||
| 124 | continue; | |||
| 125 | // Ignore Input dependencies. | |||
| 126 | if (isa<LoadInst>(Src) && isa<LoadInst>(Dst)) | |||
| 127 | continue; | |||
| 128 | // Track Output, Flow, and Anti dependencies. | |||
| 129 | if (auto D = DI->depends(Src, Dst, true)) { | |||
| 130 | assert(D->isOrdered() && "Expected an output, flow or anti dep.")((void)0); | |||
| 131 | LLVM_DEBUG(StringRef DepType =do { } while (false) | |||
| 132 | D->isFlow() ? "flow" : D->isAnti() ? "anti" : "output";do { } while (false) | |||
| 133 | dbgs() << "Found " << DepTypedo { } while (false) | |||
| 134 | << " dependency between Src and Dst\n"do { } while (false) | |||
| 135 | << " Src:" << *Src << "\n Dst:" << *Dst << '\n')do { } while (false); | |||
| 136 | unsigned Levels = D->getLevels(); | |||
| 137 | char Direction; | |||
| 138 | for (unsigned II = 1; II <= Levels; ++II) { | |||
| 139 | const SCEV *Distance = D->getDistance(II); | |||
| 140 | const SCEVConstant *SCEVConst = | |||
| 141 | dyn_cast_or_null<SCEVConstant>(Distance); | |||
| 142 | if (SCEVConst) { | |||
| 143 | const ConstantInt *CI = SCEVConst->getValue(); | |||
| 144 | if (CI->isNegative()) | |||
| 145 | Direction = '<'; | |||
| 146 | else if (CI->isZero()) | |||
| 147 | Direction = '='; | |||
| 148 | else | |||
| 149 | Direction = '>'; | |||
| 150 | Dep.push_back(Direction); | |||
| 151 | } else if (D->isScalar(II)) { | |||
| 152 | Direction = 'S'; | |||
| 153 | Dep.push_back(Direction); | |||
| 154 | } else { | |||
| 155 | unsigned Dir = D->getDirection(II); | |||
| 156 | if (Dir == Dependence::DVEntry::LT || | |||
| 157 | Dir == Dependence::DVEntry::LE) | |||
| 158 | Direction = '<'; | |||
| 159 | else if (Dir == Dependence::DVEntry::GT || | |||
| 160 | Dir == Dependence::DVEntry::GE) | |||
| 161 | Direction = '>'; | |||
| 162 | else if (Dir == Dependence::DVEntry::EQ) | |||
| 163 | Direction = '='; | |||
| 164 | else | |||
| 165 | Direction = '*'; | |||
| 166 | Dep.push_back(Direction); | |||
| 167 | } | |||
| 168 | } | |||
| 169 | while (Dep.size() != Level) { | |||
| 170 | Dep.push_back('I'); | |||
| 171 | } | |||
| 172 | ||||
| 173 | DepMatrix.push_back(Dep); | |||
| 174 | if (DepMatrix.size() > MaxMemInstrCount) { | |||
| 175 | LLVM_DEBUG(dbgs() << "Cannot handle more than " << MaxMemInstrCountdo { } while (false) | |||
| 176 | << " dependencies inside loop\n")do { } while (false); | |||
| 177 | return false; | |||
| 178 | } | |||
| 179 | } | |||
| 180 | } | |||
| 181 | } | |||
| 182 | ||||
| 183 | return true; | |||
| 184 | } | |||
| 185 | ||||
| 186 | // A loop is moved from index 'from' to an index 'to'. Update the Dependence | |||
| 187 | // matrix by exchanging the two columns. | |||
| 188 | static void interChangeDependencies(CharMatrix &DepMatrix, unsigned FromIndx, | |||
| 189 | unsigned ToIndx) { | |||
| 190 | for (unsigned I = 0, E = DepMatrix.size(); I < E; ++I) | |||
| 191 | std::swap(DepMatrix[I][ToIndx], DepMatrix[I][FromIndx]); | |||
| 192 | } | |||
| 193 | ||||
| 194 | // Checks if outermost non '=','S'or'I' dependence in the dependence matrix is | |||
| 195 | // '>' | |||
| 196 | static bool isOuterMostDepPositive(CharMatrix &DepMatrix, unsigned Row, | |||
| 197 | unsigned Column) { | |||
| 198 | for (unsigned i = 0; i <= Column; ++i) { | |||
| 199 | if (DepMatrix[Row][i] == '<') | |||
| 200 | return false; | |||
| 201 | if (DepMatrix[Row][i] == '>') | |||
| 202 | return true; | |||
| 203 | } | |||
| 204 | // All dependencies were '=','S' or 'I' | |||
| 205 | return false; | |||
| 206 | } | |||
| 207 | ||||
| 208 | // Checks if no dependence exist in the dependency matrix in Row before Column. | |||
| 209 | static bool containsNoDependence(CharMatrix &DepMatrix, unsigned Row, | |||
| 210 | unsigned Column) { | |||
| 211 | for (unsigned i = 0; i < Column; ++i) { | |||
| 212 | if (DepMatrix[Row][i] != '=' && DepMatrix[Row][i] != 'S' && | |||
| 213 | DepMatrix[Row][i] != 'I') | |||
| 214 | return false; | |||
| 215 | } | |||
| 216 | return true; | |||
| 217 | } | |||
| 218 | ||||
| 219 | static bool validDepInterchange(CharMatrix &DepMatrix, unsigned Row, | |||
| 220 | unsigned OuterLoopId, char InnerDep, | |||
| 221 | char OuterDep) { | |||
| 222 | if (isOuterMostDepPositive(DepMatrix, Row, OuterLoopId)) | |||
| 223 | return false; | |||
| 224 | ||||
| 225 | if (InnerDep == OuterDep) | |||
| 226 | return true; | |||
| 227 | ||||
| 228 | // It is legal to interchange if and only if after interchange no row has a | |||
| 229 | // '>' direction as the leftmost non-'='. | |||
| 230 | ||||
| 231 | if (InnerDep == '=' || InnerDep == 'S' || InnerDep == 'I') | |||
| 232 | return true; | |||
| 233 | ||||
| 234 | if (InnerDep == '<') | |||
| 235 | return true; | |||
| 236 | ||||
| 237 | if (InnerDep == '>') { | |||
| 238 | // If OuterLoopId represents outermost loop then interchanging will make the | |||
| 239 | // 1st dependency as '>' | |||
| 240 | if (OuterLoopId == 0) | |||
| 241 | return false; | |||
| 242 | ||||
| 243 | // If all dependencies before OuterloopId are '=','S'or 'I'. Then | |||
| 244 | // interchanging will result in this row having an outermost non '=' | |||
| 245 | // dependency of '>' | |||
| 246 | if (!containsNoDependence(DepMatrix, Row, OuterLoopId)) | |||
| 247 | return true; | |||
| 248 | } | |||
| 249 | ||||
| 250 | return false; | |||
| 251 | } | |||
| 252 | ||||
| 253 | // Checks if it is legal to interchange 2 loops. | |||
| 254 | // [Theorem] A permutation of the loops in a perfect nest is legal if and only | |||
| 255 | // if the direction matrix, after the same permutation is applied to its | |||
| 256 | // columns, has no ">" direction as the leftmost non-"=" direction in any row. | |||
| 257 | static bool isLegalToInterChangeLoops(CharMatrix &DepMatrix, | |||
| 258 | unsigned InnerLoopId, | |||
| 259 | unsigned OuterLoopId) { | |||
| 260 | unsigned NumRows = DepMatrix.size(); | |||
| 261 | // For each row check if it is valid to interchange. | |||
| 262 | for (unsigned Row = 0; Row < NumRows; ++Row) { | |||
| 263 | char InnerDep = DepMatrix[Row][InnerLoopId]; | |||
| 264 | char OuterDep = DepMatrix[Row][OuterLoopId]; | |||
| 265 | if (InnerDep == '*' || OuterDep == '*') | |||
| 266 | return false; | |||
| 267 | if (!validDepInterchange(DepMatrix, Row, OuterLoopId, InnerDep, OuterDep)) | |||
| 268 | return false; | |||
| 269 | } | |||
| 270 | return true; | |||
| 271 | } | |||
| 272 | ||||
| 273 | static LoopVector populateWorklist(Loop &L) { | |||
| 274 | LLVM_DEBUG(dbgs() << "Calling populateWorklist on Func: "do { } while (false) | |||
| 275 | << L.getHeader()->getParent()->getName() << " Loop: %"do { } while (false) | |||
| 276 | << L.getHeader()->getName() << '\n')do { } while (false); | |||
| 277 | LoopVector LoopList; | |||
| 278 | Loop *CurrentLoop = &L; | |||
| 279 | const std::vector<Loop *> *Vec = &CurrentLoop->getSubLoops(); | |||
| 280 | while (!Vec->empty()) { | |||
| 281 | // The current loop has multiple subloops in it hence it is not tightly | |||
| 282 | // nested. | |||
| 283 | // Discard all loops above it added into Worklist. | |||
| 284 | if (Vec->size() != 1) | |||
| 285 | return {}; | |||
| 286 | ||||
| 287 | LoopList.push_back(CurrentLoop); | |||
| 288 | CurrentLoop = Vec->front(); | |||
| 289 | Vec = &CurrentLoop->getSubLoops(); | |||
| 290 | } | |||
| 291 | LoopList.push_back(CurrentLoop); | |||
| 292 | return LoopList; | |||
| 293 | } | |||
| 294 | ||||
| 295 | static PHINode *getInductionVariable(Loop *L, ScalarEvolution *SE) { | |||
| 296 | PHINode *InnerIndexVar = L->getCanonicalInductionVariable(); | |||
| 297 | if (InnerIndexVar) | |||
| 298 | return InnerIndexVar; | |||
| 299 | if (L->getLoopLatch() == nullptr || L->getLoopPredecessor() == nullptr) | |||
| 300 | return nullptr; | |||
| 301 | for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) { | |||
| 302 | PHINode *PhiVar = cast<PHINode>(I); | |||
| 303 | Type *PhiTy = PhiVar->getType(); | |||
| 304 | if (!PhiTy->isIntegerTy() && !PhiTy->isFloatingPointTy() && | |||
| 305 | !PhiTy->isPointerTy()) | |||
| 306 | return nullptr; | |||
| 307 | const SCEVAddRecExpr *AddRec = | |||
| 308 | dyn_cast<SCEVAddRecExpr>(SE->getSCEV(PhiVar)); | |||
| 309 | if (!AddRec || !AddRec->isAffine()) | |||
| 310 | continue; | |||
| 311 | const SCEV *Step = AddRec->getStepRecurrence(*SE); | |||
| 312 | if (!isa<SCEVConstant>(Step)) | |||
| 313 | continue; | |||
| 314 | // Found the induction variable. | |||
| 315 | // FIXME: Handle loops with more than one induction variable. Note that, | |||
| 316 | // currently, legality makes sure we have only one induction variable. | |||
| 317 | return PhiVar; | |||
| 318 | } | |||
| 319 | return nullptr; | |||
| 320 | } | |||
| 321 | ||||
| 322 | namespace { | |||
| 323 | ||||
| 324 | /// LoopInterchangeLegality checks if it is legal to interchange the loop. | |||
| 325 | class LoopInterchangeLegality { | |||
| 326 | public: | |||
| 327 | LoopInterchangeLegality(Loop *Outer, Loop *Inner, ScalarEvolution *SE, | |||
| 328 | OptimizationRemarkEmitter *ORE) | |||
| 329 | : OuterLoop(Outer), InnerLoop(Inner), SE(SE), ORE(ORE) {} | |||
| 330 | ||||
| 331 | /// Check if the loops can be interchanged. | |||
| 332 | bool canInterchangeLoops(unsigned InnerLoopId, unsigned OuterLoopId, | |||
| 333 | CharMatrix &DepMatrix); | |||
| 334 | ||||
| 335 | /// Check if the loop structure is understood. We do not handle triangular | |||
| 336 | /// loops for now. | |||
| 337 | bool isLoopStructureUnderstood(PHINode *InnerInductionVar); | |||
| 338 | ||||
| 339 | bool currentLimitations(); | |||
| 340 | ||||
| 341 | const SmallPtrSetImpl<PHINode *> &getOuterInnerReductions() const { | |||
| 342 | return OuterInnerReductions; | |||
| 343 | } | |||
| 344 | ||||
| 345 | private: | |||
| 346 | bool tightlyNested(Loop *Outer, Loop *Inner); | |||
| 347 | bool containsUnsafeInstructions(BasicBlock *BB); | |||
| 348 | ||||
| 349 | /// Discover induction and reduction PHIs in the header of \p L. Induction | |||
| 350 | /// PHIs are added to \p Inductions, reductions are added to | |||
| 351 | /// OuterInnerReductions. When the outer loop is passed, the inner loop needs | |||
| 352 | /// to be passed as \p InnerLoop. | |||
| 353 | bool findInductionAndReductions(Loop *L, | |||
| 354 | SmallVector<PHINode *, 8> &Inductions, | |||
| 355 | Loop *InnerLoop); | |||
| 356 | ||||
| 357 | Loop *OuterLoop; | |||
| 358 | Loop *InnerLoop; | |||
| 359 | ||||
| 360 | ScalarEvolution *SE; | |||
| 361 | ||||
| 362 | /// Interface to emit optimization remarks. | |||
| 363 | OptimizationRemarkEmitter *ORE; | |||
| 364 | ||||
| 365 | /// Set of reduction PHIs taking part of a reduction across the inner and | |||
| 366 | /// outer loop. | |||
| 367 | SmallPtrSet<PHINode *, 4> OuterInnerReductions; | |||
| 368 | }; | |||
| 369 | ||||
| 370 | /// LoopInterchangeProfitability checks if it is profitable to interchange the | |||
| 371 | /// loop. | |||
| 372 | class LoopInterchangeProfitability { | |||
| 373 | public: | |||
| 374 | LoopInterchangeProfitability(Loop *Outer, Loop *Inner, ScalarEvolution *SE, | |||
| 375 | OptimizationRemarkEmitter *ORE) | |||
| 376 | : OuterLoop(Outer), InnerLoop(Inner), SE(SE), ORE(ORE) {} | |||
| 377 | ||||
| 378 | /// Check if the loop interchange is profitable. | |||
| 379 | bool isProfitable(unsigned InnerLoopId, unsigned OuterLoopId, | |||
| 380 | CharMatrix &DepMatrix); | |||
| 381 | ||||
| 382 | private: | |||
| 383 | int getInstrOrderCost(); | |||
| 384 | ||||
| 385 | Loop *OuterLoop; | |||
| 386 | Loop *InnerLoop; | |||
| 387 | ||||
| 388 | /// Scev analysis. | |||
| 389 | ScalarEvolution *SE; | |||
| 390 | ||||
| 391 | /// Interface to emit optimization remarks. | |||
| 392 | OptimizationRemarkEmitter *ORE; | |||
| 393 | }; | |||
| 394 | ||||
| 395 | /// LoopInterchangeTransform interchanges the loop. | |||
| 396 | class LoopInterchangeTransform { | |||
| 397 | public: | |||
| 398 | LoopInterchangeTransform(Loop *Outer, Loop *Inner, ScalarEvolution *SE, | |||
| 399 | LoopInfo *LI, DominatorTree *DT, | |||
| 400 | const LoopInterchangeLegality &LIL) | |||
| 401 | : OuterLoop(Outer), InnerLoop(Inner), SE(SE), LI(LI), DT(DT), LIL(LIL) {} | |||
| 402 | ||||
| 403 | /// Interchange OuterLoop and InnerLoop. | |||
| 404 | bool transform(); | |||
| 405 | void restructureLoops(Loop *NewInner, Loop *NewOuter, | |||
| 406 | BasicBlock *OrigInnerPreHeader, | |||
| 407 | BasicBlock *OrigOuterPreHeader); | |||
| 408 | void removeChildLoop(Loop *OuterLoop, Loop *InnerLoop); | |||
| 409 | ||||
| 410 | private: | |||
| 411 | bool adjustLoopLinks(); | |||
| 412 | bool adjustLoopBranches(); | |||
| 413 | ||||
| 414 | Loop *OuterLoop; | |||
| 415 | Loop *InnerLoop; | |||
| 416 | ||||
| 417 | /// Scev analysis. | |||
| 418 | ScalarEvolution *SE; | |||
| 419 | ||||
| 420 | LoopInfo *LI; | |||
| 421 | DominatorTree *DT; | |||
| 422 | ||||
| 423 | const LoopInterchangeLegality &LIL; | |||
| 424 | }; | |||
| 425 | ||||
| 426 | struct LoopInterchange { | |||
| 427 | ScalarEvolution *SE = nullptr; | |||
| 428 | LoopInfo *LI = nullptr; | |||
| 429 | DependenceInfo *DI = nullptr; | |||
| 430 | DominatorTree *DT = nullptr; | |||
| 431 | ||||
| 432 | /// Interface to emit optimization remarks. | |||
| 433 | OptimizationRemarkEmitter *ORE; | |||
| 434 | ||||
| 435 | LoopInterchange(ScalarEvolution *SE, LoopInfo *LI, DependenceInfo *DI, | |||
| 436 | DominatorTree *DT, OptimizationRemarkEmitter *ORE) | |||
| 437 | : SE(SE), LI(LI), DI(DI), DT(DT), ORE(ORE) {} | |||
| 438 | ||||
| 439 | bool run(Loop *L) { | |||
| 440 | if (L->getParentLoop()) | |||
| 441 | return false; | |||
| 442 | ||||
| 443 | return processLoopList(populateWorklist(*L)); | |||
| 444 | } | |||
| 445 | ||||
| 446 | bool run(LoopNest &LN) { | |||
| 447 | const auto &LoopList = LN.getLoops(); | |||
| 448 | for (unsigned I = 1; I < LoopList.size(); ++I) | |||
| 449 | if (LoopList[I]->getParentLoop() != LoopList[I - 1]) | |||
| 450 | return false; | |||
| 451 | return processLoopList(LoopList); | |||
| 452 | } | |||
| 453 | ||||
| 454 | bool isComputableLoopNest(ArrayRef<Loop *> LoopList) { | |||
| 455 | for (Loop *L : LoopList) { | |||
| 456 | const SCEV *ExitCountOuter = SE->getBackedgeTakenCount(L); | |||
| 457 | if (isa<SCEVCouldNotCompute>(ExitCountOuter)) { | |||
| 458 | LLVM_DEBUG(dbgs() << "Couldn't compute backedge count\n")do { } while (false); | |||
| 459 | return false; | |||
| 460 | } | |||
| 461 | if (L->getNumBackEdges() != 1) { | |||
| 462 | LLVM_DEBUG(dbgs() << "NumBackEdges is not equal to 1\n")do { } while (false); | |||
| 463 | return false; | |||
| 464 | } | |||
| 465 | if (!L->getExitingBlock()) { | |||
| 466 | LLVM_DEBUG(dbgs() << "Loop doesn't have unique exit block\n")do { } while (false); | |||
| 467 | return false; | |||
| 468 | } | |||
| 469 | } | |||
| 470 | return true; | |||
| 471 | } | |||
| 472 | ||||
| 473 | unsigned selectLoopForInterchange(ArrayRef<Loop *> LoopList) { | |||
| 474 | // TODO: Add a better heuristic to select the loop to be interchanged based | |||
| 475 | // on the dependence matrix. Currently we select the innermost loop. | |||
| 476 | return LoopList.size() - 1; | |||
| 477 | } | |||
| 478 | ||||
| 479 | bool processLoopList(ArrayRef<Loop *> LoopList) { | |||
| 480 | bool Changed = false; | |||
| 481 | unsigned LoopNestDepth = LoopList.size(); | |||
| 482 | if (LoopNestDepth < 2) { | |||
| 483 | LLVM_DEBUG(dbgs() << "Loop doesn't contain minimum nesting level.\n")do { } while (false); | |||
| 484 | return false; | |||
| 485 | } | |||
| 486 | if (LoopNestDepth > MaxLoopNestDepth) { | |||
| 487 | LLVM_DEBUG(dbgs() << "Cannot handle loops of depth greater than "do { } while (false) | |||
| 488 | << MaxLoopNestDepth << "\n")do { } while (false); | |||
| 489 | return false; | |||
| 490 | } | |||
| 491 | if (!isComputableLoopNest(LoopList)) { | |||
| 492 | LLVM_DEBUG(dbgs() << "Not valid loop candidate for interchange\n")do { } while (false); | |||
| 493 | return false; | |||
| 494 | } | |||
| 495 | ||||
| 496 | LLVM_DEBUG(dbgs() << "Processing LoopList of size = " << LoopNestDepthdo { } while (false) | |||
| 497 | << "\n")do { } while (false); | |||
| 498 | ||||
| 499 | CharMatrix DependencyMatrix; | |||
| 500 | Loop *OuterMostLoop = *(LoopList.begin()); | |||
| 501 | if (!populateDependencyMatrix(DependencyMatrix, LoopNestDepth, | |||
| 502 | OuterMostLoop, DI)) { | |||
| 503 | LLVM_DEBUG(dbgs() << "Populating dependency matrix failed\n")do { } while (false); | |||
| 504 | return false; | |||
| 505 | } | |||
| 506 | #ifdef DUMP_DEP_MATRICIES | |||
| 507 | LLVM_DEBUG(dbgs() << "Dependence before interchange\n")do { } while (false); | |||
| 508 | printDepMatrix(DependencyMatrix); | |||
| 509 | #endif | |||
| 510 | ||||
| 511 | // Get the Outermost loop exit. | |||
| 512 | BasicBlock *LoopNestExit = OuterMostLoop->getExitBlock(); | |||
| 513 | if (!LoopNestExit) { | |||
| 514 | LLVM_DEBUG(dbgs() << "OuterMostLoop needs an unique exit block")do { } while (false); | |||
| 515 | return false; | |||
| 516 | } | |||
| 517 | ||||
| 518 | unsigned SelecLoopId = selectLoopForInterchange(LoopList); | |||
| 519 | // Move the selected loop outwards to the best possible position. | |||
| 520 | Loop *LoopToBeInterchanged = LoopList[SelecLoopId]; | |||
| 521 | for (unsigned i = SelecLoopId; i > 0; i--) { | |||
| 522 | bool Interchanged = processLoop(LoopToBeInterchanged, LoopList[i - 1], i, | |||
| 523 | i - 1, DependencyMatrix); | |||
| 524 | if (!Interchanged) | |||
| 525 | return Changed; | |||
| 526 | // Update the DependencyMatrix | |||
| 527 | interChangeDependencies(DependencyMatrix, i, i - 1); | |||
| 528 | #ifdef DUMP_DEP_MATRICIES | |||
| 529 | LLVM_DEBUG(dbgs() << "Dependence after interchange\n")do { } while (false); | |||
| 530 | printDepMatrix(DependencyMatrix); | |||
| 531 | #endif | |||
| 532 | Changed |= Interchanged; | |||
| 533 | } | |||
| 534 | return Changed; | |||
| 535 | } | |||
| 536 | ||||
| 537 | bool processLoop(Loop *InnerLoop, Loop *OuterLoop, unsigned InnerLoopId, | |||
| 538 | unsigned OuterLoopId, | |||
| 539 | std::vector<std::vector<char>> &DependencyMatrix) { | |||
| 540 | LLVM_DEBUG(dbgs() << "Processing InnerLoopId = " << InnerLoopIddo { } while (false) | |||
| 541 | << " and OuterLoopId = " << OuterLoopId << "\n")do { } while (false); | |||
| 542 | LoopInterchangeLegality LIL(OuterLoop, InnerLoop, SE, ORE); | |||
| 543 | if (!LIL.canInterchangeLoops(InnerLoopId, OuterLoopId, DependencyMatrix)) { | |||
| 544 | LLVM_DEBUG(dbgs() << "Not interchanging loops. Cannot prove legality.\n")do { } while (false); | |||
| 545 | return false; | |||
| 546 | } | |||
| 547 | LLVM_DEBUG(dbgs() << "Loops are legal to interchange\n")do { } while (false); | |||
| 548 | LoopInterchangeProfitability LIP(OuterLoop, InnerLoop, SE, ORE); | |||
| 549 | if (!LIP.isProfitable(InnerLoopId, OuterLoopId, DependencyMatrix)) { | |||
| 550 | LLVM_DEBUG(dbgs() << "Interchanging loops not profitable.\n")do { } while (false); | |||
| 551 | return false; | |||
| 552 | } | |||
| 553 | ||||
| 554 | ORE->emit([&]() { | |||
| 555 | return OptimizationRemark(DEBUG_TYPE"loop-interchange", "Interchanged", | |||
| 556 | InnerLoop->getStartLoc(), | |||
| 557 | InnerLoop->getHeader()) | |||
| 558 | << "Loop interchanged with enclosing loop."; | |||
| 559 | }); | |||
| 560 | ||||
| 561 | LoopInterchangeTransform LIT(OuterLoop, InnerLoop, SE, LI, DT, LIL); | |||
| 562 | LIT.transform(); | |||
| 563 | LLVM_DEBUG(dbgs() << "Loops interchanged.\n")do { } while (false); | |||
| 564 | LoopsInterchanged++; | |||
| 565 | ||||
| 566 | assert(InnerLoop->isLCSSAForm(*DT) &&((void)0) | |||
| 567 | "Inner loop not left in LCSSA form after loop interchange!")((void)0); | |||
| 568 | assert(OuterLoop->isLCSSAForm(*DT) &&((void)0) | |||
| 569 | "Outer loop not left in LCSSA form after loop interchange!")((void)0); | |||
| 570 | ||||
| 571 | return true; | |||
| 572 | } | |||
| 573 | }; | |||
| 574 | ||||
| 575 | } // end anonymous namespace | |||
| 576 | ||||
| 577 | bool LoopInterchangeLegality::containsUnsafeInstructions(BasicBlock *BB) { | |||
| 578 | return any_of(*BB, [](const Instruction &I) { | |||
| 579 | return I.mayHaveSideEffects() || I.mayReadFromMemory(); | |||
| 580 | }); | |||
| 581 | } | |||
| 582 | ||||
| 583 | bool LoopInterchangeLegality::tightlyNested(Loop *OuterLoop, Loop *InnerLoop) { | |||
| 584 | BasicBlock *OuterLoopHeader = OuterLoop->getHeader(); | |||
| 585 | BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader(); | |||
| 586 | BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch(); | |||
| 587 | ||||
| 588 | LLVM_DEBUG(dbgs() << "Checking if loops are tightly nested\n")do { } while (false); | |||
| 589 | ||||
| 590 | // A perfectly nested loop will not have any branch in between the outer and | |||
| 591 | // inner block i.e. outer header will branch to either inner preheader and | |||
| 592 | // outerloop latch. | |||
| 593 | BranchInst *OuterLoopHeaderBI = | |||
| 594 | dyn_cast<BranchInst>(OuterLoopHeader->getTerminator()); | |||
| 595 | if (!OuterLoopHeaderBI) | |||
| 596 | return false; | |||
| 597 | ||||
| 598 | for (BasicBlock *Succ : successors(OuterLoopHeaderBI)) | |||
| 599 | if (Succ != InnerLoopPreHeader && Succ != InnerLoop->getHeader() && | |||
| 600 | Succ != OuterLoopLatch) | |||
| 601 | return false; | |||
| 602 | ||||
| 603 | LLVM_DEBUG(dbgs() << "Checking instructions in Loop header and Loop latch\n")do { } while (false); | |||
| 604 | // We do not have any basic block in between now make sure the outer header | |||
| 605 | // and outer loop latch doesn't contain any unsafe instructions. | |||
| 606 | if (containsUnsafeInstructions(OuterLoopHeader) || | |||
| 607 | containsUnsafeInstructions(OuterLoopLatch)) | |||
| 608 | return false; | |||
| 609 | ||||
| 610 | // Also make sure the inner loop preheader does not contain any unsafe | |||
| 611 | // instructions. Note that all instructions in the preheader will be moved to | |||
| 612 | // the outer loop header when interchanging. | |||
| 613 | if (InnerLoopPreHeader != OuterLoopHeader && | |||
| 614 | containsUnsafeInstructions(InnerLoopPreHeader)) | |||
| 615 | return false; | |||
| 616 | ||||
| 617 | BasicBlock *InnerLoopExit = InnerLoop->getExitBlock(); | |||
| 618 | // Ensure the inner loop exit block flows to the outer loop latch possibly | |||
| 619 | // through empty blocks. | |||
| 620 | const BasicBlock &SuccInner = | |||
| 621 | LoopNest::skipEmptyBlockUntil(InnerLoopExit, OuterLoopLatch); | |||
| 622 | if (&SuccInner != OuterLoopLatch) { | |||
| 623 | LLVM_DEBUG(dbgs() << "Inner loop exit block " << *InnerLoopExitdo { } while (false) | |||
| 624 | << " does not lead to the outer loop latch.\n";)do { } while (false); | |||
| 625 | return false; | |||
| 626 | } | |||
| 627 | // The inner loop exit block does flow to the outer loop latch and not some | |||
| 628 | // other BBs, now make sure it contains safe instructions, since it will be | |||
| 629 | // moved into the (new) inner loop after interchange. | |||
| 630 | if (containsUnsafeInstructions(InnerLoopExit)) | |||
| 631 | return false; | |||
| 632 | ||||
| 633 | LLVM_DEBUG(dbgs() << "Loops are perfectly nested\n")do { } while (false); | |||
| 634 | // We have a perfect loop nest. | |||
| 635 | return true; | |||
| 636 | } | |||
| 637 | ||||
| 638 | bool LoopInterchangeLegality::isLoopStructureUnderstood( | |||
| 639 | PHINode *InnerInduction) { | |||
| 640 | unsigned Num = InnerInduction->getNumOperands(); | |||
| 641 | BasicBlock *InnerLoopPreheader = InnerLoop->getLoopPreheader(); | |||
| 642 | for (unsigned i = 0; i < Num; ++i) { | |||
| 643 | Value *Val = InnerInduction->getOperand(i); | |||
| 644 | if (isa<Constant>(Val)) | |||
| 645 | continue; | |||
| 646 | Instruction *I = dyn_cast<Instruction>(Val); | |||
| 647 | if (!I) | |||
| 648 | return false; | |||
| 649 | // TODO: Handle triangular loops. | |||
| 650 | // e.g. for(int i=0;i<N;i++) | |||
| 651 | // for(int j=i;j<N;j++) | |||
| 652 | unsigned IncomBlockIndx = PHINode::getIncomingValueNumForOperand(i); | |||
| 653 | if (InnerInduction->getIncomingBlock(IncomBlockIndx) == | |||
| 654 | InnerLoopPreheader && | |||
| 655 | !OuterLoop->isLoopInvariant(I)) { | |||
| 656 | return false; | |||
| 657 | } | |||
| 658 | } | |||
| 659 | ||||
| 660 | // TODO: Handle triangular loops of another form. | |||
| 661 | // e.g. for(int i=0;i<N;i++) | |||
| 662 | // for(int j=0;j<i;j++) | |||
| 663 | // or, | |||
| 664 | // for(int i=0;i<N;i++) | |||
| 665 | // for(int j=0;j*i<N;j++) | |||
| 666 | BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch(); | |||
| 667 | BranchInst *InnerLoopLatchBI = | |||
| 668 | dyn_cast<BranchInst>(InnerLoopLatch->getTerminator()); | |||
| 669 | if (!InnerLoopLatchBI->isConditional()) | |||
| 670 | return false; | |||
| 671 | if (CmpInst *InnerLoopCmp = | |||
| 672 | dyn_cast<CmpInst>(InnerLoopLatchBI->getCondition())) { | |||
| 673 | Value *Op0 = InnerLoopCmp->getOperand(0); | |||
| 674 | Value *Op1 = InnerLoopCmp->getOperand(1); | |||
| 675 | ||||
| 676 | // LHS and RHS of the inner loop exit condition, e.g., | |||
| 677 | // in "for(int j=0;j<i;j++)", LHS is j and RHS is i. | |||
| 678 | Value *Left = nullptr; | |||
| 679 | Value *Right = nullptr; | |||
| 680 | ||||
| 681 | // Check if V only involves inner loop induction variable. | |||
| 682 | // Return true if V is InnerInduction, or a cast from | |||
| 683 | // InnerInduction, or a binary operator that involves | |||
| 684 | // InnerInduction and a constant. | |||
| 685 | std::function<bool(Value *)> IsPathToIndVar; | |||
| 686 | IsPathToIndVar = [&InnerInduction, &IsPathToIndVar](Value *V) -> bool { | |||
| 687 | if (V == InnerInduction) | |||
| 688 | return true; | |||
| 689 | if (isa<Constant>(V)) | |||
| 690 | return true; | |||
| 691 | Instruction *I = dyn_cast<Instruction>(V); | |||
| 692 | if (!I) | |||
| 693 | return false; | |||
| 694 | if (isa<CastInst>(I)) | |||
| 695 | return IsPathToIndVar(I->getOperand(0)); | |||
| 696 | if (isa<BinaryOperator>(I)) | |||
| 697 | return IsPathToIndVar(I->getOperand(0)) && | |||
| 698 | IsPathToIndVar(I->getOperand(1)); | |||
| 699 | return false; | |||
| 700 | }; | |||
| 701 | ||||
| 702 | if (IsPathToIndVar(Op0) && !isa<Constant>(Op0)) { | |||
| 703 | Left = Op0; | |||
| 704 | Right = Op1; | |||
| 705 | } else if (IsPathToIndVar(Op1) && !isa<Constant>(Op1)) { | |||
| 706 | Left = Op1; | |||
| 707 | Right = Op0; | |||
| 708 | } | |||
| 709 | ||||
| 710 | if (Left == nullptr) | |||
| 711 | return false; | |||
| 712 | ||||
| 713 | const SCEV *S = SE->getSCEV(Right); | |||
| 714 | if (!SE->isLoopInvariant(S, OuterLoop)) | |||
| 715 | return false; | |||
| 716 | } | |||
| 717 | ||||
| 718 | return true; | |||
| 719 | } | |||
| 720 | ||||
| 721 | // If SV is a LCSSA PHI node with a single incoming value, return the incoming | |||
| 722 | // value. | |||
| 723 | static Value *followLCSSA(Value *SV) { | |||
| 724 | PHINode *PHI = dyn_cast<PHINode>(SV); | |||
| 725 | if (!PHI) | |||
| 726 | return SV; | |||
| 727 | ||||
| 728 | if (PHI->getNumIncomingValues() != 1) | |||
| 729 | return SV; | |||
| 730 | return followLCSSA(PHI->getIncomingValue(0)); | |||
| 731 | } | |||
| 732 | ||||
| 733 | // Check V's users to see if it is involved in a reduction in L. | |||
| 734 | static PHINode *findInnerReductionPhi(Loop *L, Value *V) { | |||
| 735 | // Reduction variables cannot be constants. | |||
| 736 | if (isa<Constant>(V)) | |||
| 737 | return nullptr; | |||
| 738 | ||||
| 739 | for (Value *User : V->users()) { | |||
| 740 | if (PHINode *PHI = dyn_cast<PHINode>(User)) { | |||
| 741 | if (PHI->getNumIncomingValues() == 1) | |||
| 742 | continue; | |||
| 743 | RecurrenceDescriptor RD; | |||
| 744 | if (RecurrenceDescriptor::isReductionPHI(PHI, L, RD)) | |||
| 745 | return PHI; | |||
| 746 | return nullptr; | |||
| 747 | } | |||
| 748 | } | |||
| 749 | ||||
| 750 | return nullptr; | |||
| 751 | } | |||
| 752 | ||||
| 753 | bool LoopInterchangeLegality::findInductionAndReductions( | |||
| 754 | Loop *L, SmallVector<PHINode *, 8> &Inductions, Loop *InnerLoop) { | |||
| 755 | if (!L->getLoopLatch() || !L->getLoopPredecessor()) | |||
| 756 | return false; | |||
| 757 | for (PHINode &PHI : L->getHeader()->phis()) { | |||
| 758 | RecurrenceDescriptor RD; | |||
| 759 | InductionDescriptor ID; | |||
| 760 | if (InductionDescriptor::isInductionPHI(&PHI, L, SE, ID)) | |||
| 761 | Inductions.push_back(&PHI); | |||
| 762 | else { | |||
| 763 | // PHIs in inner loops need to be part of a reduction in the outer loop, | |||
| 764 | // discovered when checking the PHIs of the outer loop earlier. | |||
| 765 | if (!InnerLoop) { | |||
| 766 | if (!OuterInnerReductions.count(&PHI)) { | |||
| 767 | LLVM_DEBUG(dbgs() << "Inner loop PHI is not part of reductions "do { } while (false) | |||
| 768 | "across the outer loop.\n")do { } while (false); | |||
| 769 | return false; | |||
| 770 | } | |||
| 771 | } else { | |||
| 772 | assert(PHI.getNumIncomingValues() == 2 &&((void)0) | |||
| 773 | "Phis in loop header should have exactly 2 incoming values")((void)0); | |||
| 774 | // Check if we have a PHI node in the outer loop that has a reduction | |||
| 775 | // result from the inner loop as an incoming value. | |||
| 776 | Value *V = followLCSSA(PHI.getIncomingValueForBlock(L->getLoopLatch())); | |||
| 777 | PHINode *InnerRedPhi = findInnerReductionPhi(InnerLoop, V); | |||
| 778 | if (!InnerRedPhi || | |||
| 779 | !llvm::is_contained(InnerRedPhi->incoming_values(), &PHI)) { | |||
| 780 | LLVM_DEBUG(do { } while (false) | |||
| 781 | dbgs()do { } while (false) | |||
| 782 | << "Failed to recognize PHI as an induction or reduction.\n")do { } while (false); | |||
| 783 | return false; | |||
| 784 | } | |||
| 785 | OuterInnerReductions.insert(&PHI); | |||
| 786 | OuterInnerReductions.insert(InnerRedPhi); | |||
| 787 | } | |||
| 788 | } | |||
| 789 | } | |||
| 790 | return true; | |||
| 791 | } | |||
| 792 | ||||
| 793 | // This function indicates the current limitations in the transform as a result | |||
| 794 | // of which we do not proceed. | |||
| 795 | bool LoopInterchangeLegality::currentLimitations() { | |||
| 796 | BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader(); | |||
| 797 | BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch(); | |||
| 798 | ||||
| 799 | // transform currently expects the loop latches to also be the exiting | |||
| 800 | // blocks. | |||
| 801 | if (InnerLoop->getExitingBlock() != InnerLoopLatch || | |||
| 802 | OuterLoop->getExitingBlock() != OuterLoop->getLoopLatch() || | |||
| 803 | !isa<BranchInst>(InnerLoopLatch->getTerminator()) || | |||
| 804 | !isa<BranchInst>(OuterLoop->getLoopLatch()->getTerminator())) { | |||
| 805 | LLVM_DEBUG(do { } while (false) | |||
| 806 | dbgs() << "Loops where the latch is not the exiting block are not"do { } while (false) | |||
| 807 | << " supported currently.\n")do { } while (false); | |||
| 808 | ORE->emit([&]() { | |||
| 809 | return OptimizationRemarkMissed(DEBUG_TYPE"loop-interchange", "ExitingNotLatch", | |||
| 810 | OuterLoop->getStartLoc(), | |||
| 811 | OuterLoop->getHeader()) | |||
| 812 | << "Loops where the latch is not the exiting block cannot be" | |||
| 813 | " interchange currently."; | |||
| 814 | }); | |||
| 815 | return true; | |||
| 816 | } | |||
| 817 | ||||
| 818 | PHINode *InnerInductionVar; | |||
| 819 | SmallVector<PHINode *, 8> Inductions; | |||
| 820 | if (!findInductionAndReductions(OuterLoop, Inductions, InnerLoop)) { | |||
| 821 | LLVM_DEBUG(do { } while (false) | |||
| 822 | dbgs() << "Only outer loops with induction or reduction PHI nodes "do { } while (false) | |||
| 823 | << "are supported currently.\n")do { } while (false); | |||
| 824 | ORE->emit([&]() { | |||
| 825 | return OptimizationRemarkMissed(DEBUG_TYPE"loop-interchange", "UnsupportedPHIOuter", | |||
| 826 | OuterLoop->getStartLoc(), | |||
| 827 | OuterLoop->getHeader()) | |||
| 828 | << "Only outer loops with induction or reduction PHI nodes can be" | |||
| 829 | " interchanged currently."; | |||
| 830 | }); | |||
| 831 | return true; | |||
| 832 | } | |||
| 833 | ||||
| 834 | // TODO: Currently we handle only loops with 1 induction variable. | |||
| 835 | if (Inductions.size() != 1) { | |||
| 836 | LLVM_DEBUG(dbgs() << "Loops with more than 1 induction variables are not "do { } while (false) | |||
| 837 | << "supported currently.\n")do { } while (false); | |||
| 838 | ORE->emit([&]() { | |||
| 839 | return OptimizationRemarkMissed(DEBUG_TYPE"loop-interchange", "MultiIndutionOuter", | |||
| 840 | OuterLoop->getStartLoc(), | |||
| 841 | OuterLoop->getHeader()) | |||
| 842 | << "Only outer loops with 1 induction variable can be " | |||
| 843 | "interchanged currently."; | |||
| 844 | }); | |||
| 845 | return true; | |||
| 846 | } | |||
| 847 | ||||
| 848 | Inductions.clear(); | |||
| 849 | if (!findInductionAndReductions(InnerLoop, Inductions, nullptr)) { | |||
| 850 | LLVM_DEBUG(do { } while (false) | |||
| 851 | dbgs() << "Only inner loops with induction or reduction PHI nodes "do { } while (false) | |||
| 852 | << "are supported currently.\n")do { } while (false); | |||
| 853 | ORE->emit([&]() { | |||
| 854 | return OptimizationRemarkMissed(DEBUG_TYPE"loop-interchange", "UnsupportedPHIInner", | |||
| 855 | InnerLoop->getStartLoc(), | |||
| 856 | InnerLoop->getHeader()) | |||
| 857 | << "Only inner loops with induction or reduction PHI nodes can be" | |||
| 858 | " interchange currently."; | |||
| 859 | }); | |||
| 860 | return true; | |||
| 861 | } | |||
| 862 | ||||
| 863 | // TODO: Currently we handle only loops with 1 induction variable. | |||
| 864 | if (Inductions.size() != 1) { | |||
| 865 | LLVM_DEBUG(do { } while (false) | |||
| 866 | dbgs() << "We currently only support loops with 1 induction variable."do { } while (false) | |||
| 867 | << "Failed to interchange due to current limitation\n")do { } while (false); | |||
| 868 | ORE->emit([&]() { | |||
| 869 | return OptimizationRemarkMissed(DEBUG_TYPE"loop-interchange", "MultiInductionInner", | |||
| 870 | InnerLoop->getStartLoc(), | |||
| 871 | InnerLoop->getHeader()) | |||
| 872 | << "Only inner loops with 1 induction variable can be " | |||
| 873 | "interchanged currently."; | |||
| 874 | }); | |||
| 875 | return true; | |||
| 876 | } | |||
| 877 | InnerInductionVar = Inductions.pop_back_val(); | |||
| 878 | ||||
| 879 | // TODO: Triangular loops are not handled for now. | |||
| 880 | if (!isLoopStructureUnderstood(InnerInductionVar)) { | |||
| 881 | LLVM_DEBUG(dbgs() << "Loop structure not understood by pass\n")do { } while (false); | |||
| 882 | ORE->emit([&]() { | |||
| 883 | return OptimizationRemarkMissed(DEBUG_TYPE"loop-interchange", "UnsupportedStructureInner", | |||
| 884 | InnerLoop->getStartLoc(), | |||
| 885 | InnerLoop->getHeader()) | |||
| 886 | << "Inner loop structure not understood currently."; | |||
| 887 | }); | |||
| 888 | return true; | |||
| 889 | } | |||
| 890 | ||||
| 891 | // TODO: Current limitation: Since we split the inner loop latch at the point | |||
| 892 | // were induction variable is incremented (induction.next); We cannot have | |||
| 893 | // more than 1 user of induction.next since it would result in broken code | |||
| 894 | // after split. | |||
| 895 | // e.g. | |||
| 896 | // for(i=0;i<N;i++) { | |||
| 897 | // for(j = 0;j<M;j++) { | |||
| 898 | // A[j+1][i+2] = A[j][i]+k; | |||
| 899 | // } | |||
| 900 | // } | |||
| 901 | Instruction *InnerIndexVarInc = nullptr; | |||
| 902 | if (InnerInductionVar->getIncomingBlock(0) == InnerLoopPreHeader) | |||
| 903 | InnerIndexVarInc = | |||
| 904 | dyn_cast<Instruction>(InnerInductionVar->getIncomingValue(1)); | |||
| 905 | else | |||
| 906 | InnerIndexVarInc = | |||
| 907 | dyn_cast<Instruction>(InnerInductionVar->getIncomingValue(0)); | |||
| 908 | ||||
| 909 | if (!InnerIndexVarInc) { | |||
| 910 | LLVM_DEBUG(do { } while (false) | |||
| 911 | dbgs() << "Did not find an instruction to increment the induction "do { } while (false) | |||
| 912 | << "variable.\n")do { } while (false); | |||
| 913 | ORE->emit([&]() { | |||
| 914 | return OptimizationRemarkMissed(DEBUG_TYPE"loop-interchange", "NoIncrementInInner", | |||
| 915 | InnerLoop->getStartLoc(), | |||
| 916 | InnerLoop->getHeader()) | |||
| 917 | << "The inner loop does not increment the induction variable."; | |||
| 918 | }); | |||
| 919 | return true; | |||
| 920 | } | |||
| 921 | ||||
| 922 | // Since we split the inner loop latch on this induction variable. Make sure | |||
| 923 | // we do not have any instruction between the induction variable and branch | |||
| 924 | // instruction. | |||
| 925 | ||||
| 926 | bool FoundInduction = false; | |||
| 927 | for (const Instruction &I : | |||
| 928 | llvm::reverse(InnerLoopLatch->instructionsWithoutDebug())) { | |||
| 929 | if (isa<BranchInst>(I) || isa<CmpInst>(I) || isa<TruncInst>(I) || | |||
| 930 | isa<ZExtInst>(I)) | |||
| 931 | continue; | |||
| 932 | ||||
| 933 | // We found an instruction. If this is not induction variable then it is not | |||
| 934 | // safe to split this loop latch. | |||
| 935 | if (!I.isIdenticalTo(InnerIndexVarInc)) { | |||
| 936 | LLVM_DEBUG(dbgs() << "Found unsupported instructions between induction "do { } while (false) | |||
| 937 | << "variable increment and branch.\n")do { } while (false); | |||
| 938 | ORE->emit([&]() { | |||
| 939 | return OptimizationRemarkMissed( | |||
| 940 | DEBUG_TYPE"loop-interchange", "UnsupportedInsBetweenInduction", | |||
| 941 | InnerLoop->getStartLoc(), InnerLoop->getHeader()) | |||
| 942 | << "Found unsupported instruction between induction variable " | |||
| 943 | "increment and branch."; | |||
| 944 | }); | |||
| 945 | return true; | |||
| 946 | } | |||
| 947 | ||||
| 948 | FoundInduction = true; | |||
| 949 | break; | |||
| 950 | } | |||
| 951 | // The loop latch ended and we didn't find the induction variable return as | |||
| 952 | // current limitation. | |||
| 953 | if (!FoundInduction) { | |||
| 954 | LLVM_DEBUG(dbgs() << "Did not find the induction variable.\n")do { } while (false); | |||
| 955 | ORE->emit([&]() { | |||
| 956 | return OptimizationRemarkMissed(DEBUG_TYPE"loop-interchange", "NoIndutionVariable", | |||
| 957 | InnerLoop->getStartLoc(), | |||
| 958 | InnerLoop->getHeader()) | |||
| 959 | << "Did not find the induction variable."; | |||
| 960 | }); | |||
| 961 | return true; | |||
| 962 | } | |||
| 963 | return false; | |||
| 964 | } | |||
| 965 | ||||
| 966 | // We currently only support LCSSA PHI nodes in the inner loop exit, if their | |||
| 967 | // users are either reduction PHIs or PHIs outside the outer loop (which means | |||
| 968 | // the we are only interested in the final value after the loop). | |||
| 969 | static bool | |||
| 970 | areInnerLoopExitPHIsSupported(Loop *InnerL, Loop *OuterL, | |||
| 971 | SmallPtrSetImpl<PHINode *> &Reductions) { | |||
| 972 | BasicBlock *InnerExit = OuterL->getUniqueExitBlock(); | |||
| 973 | for (PHINode &PHI : InnerExit->phis()) { | |||
| 974 | // Reduction lcssa phi will have only 1 incoming block that from loop latch. | |||
| 975 | if (PHI.getNumIncomingValues() > 1) | |||
| 976 | return false; | |||
| 977 | if (any_of(PHI.users(), [&Reductions, OuterL](User *U) { | |||
| 978 | PHINode *PN = dyn_cast<PHINode>(U); | |||
| 979 | return !PN || | |||
| 980 | (!Reductions.count(PN) && OuterL->contains(PN->getParent())); | |||
| 981 | })) { | |||
| 982 | return false; | |||
| 983 | } | |||
| 984 | } | |||
| 985 | return true; | |||
| 986 | } | |||
| 987 | ||||
| 988 | // We currently support LCSSA PHI nodes in the outer loop exit, if their | |||
| 989 | // incoming values do not come from the outer loop latch or if the | |||
| 990 | // outer loop latch has a single predecessor. In that case, the value will | |||
| 991 | // be available if both the inner and outer loop conditions are true, which | |||
| 992 | // will still be true after interchanging. If we have multiple predecessor, | |||
| 993 | // that may not be the case, e.g. because the outer loop latch may be executed | |||
| 994 | // if the inner loop is not executed. | |||
| 995 | static bool areOuterLoopExitPHIsSupported(Loop *OuterLoop, Loop *InnerLoop) { | |||
| 996 | BasicBlock *LoopNestExit = OuterLoop->getUniqueExitBlock(); | |||
| 997 | for (PHINode &PHI : LoopNestExit->phis()) { | |||
| 998 | // FIXME: We currently are not able to detect floating point reductions | |||
| 999 | // and have to use floating point PHIs as a proxy to prevent | |||
| 1000 | // interchanging in the presence of floating point reductions. | |||
| 1001 | if (PHI.getType()->isFloatingPointTy()) | |||
| 1002 | return false; | |||
| 1003 | for (unsigned i = 0; i < PHI.getNumIncomingValues(); i++) { | |||
| 1004 | Instruction *IncomingI = dyn_cast<Instruction>(PHI.getIncomingValue(i)); | |||
| 1005 | if (!IncomingI || IncomingI->getParent() != OuterLoop->getLoopLatch()) | |||
| 1006 | continue; | |||
| 1007 | ||||
| 1008 | // The incoming value is defined in the outer loop latch. Currently we | |||
| 1009 | // only support that in case the outer loop latch has a single predecessor. | |||
| 1010 | // This guarantees that the outer loop latch is executed if and only if | |||
| 1011 | // the inner loop is executed (because tightlyNested() guarantees that the | |||
| 1012 | // outer loop header only branches to the inner loop or the outer loop | |||
| 1013 | // latch). | |||
| 1014 | // FIXME: We could weaken this logic and allow multiple predecessors, | |||
| 1015 | // if the values are produced outside the loop latch. We would need | |||
| 1016 | // additional logic to update the PHI nodes in the exit block as | |||
| 1017 | // well. | |||
| 1018 | if (OuterLoop->getLoopLatch()->getUniquePredecessor() == nullptr) | |||
| 1019 | return false; | |||
| 1020 | } | |||
| 1021 | } | |||
| 1022 | return true; | |||
| 1023 | } | |||
| 1024 | ||||
| 1025 | // In case of multi-level nested loops, it may occur that lcssa phis exist in | |||
| 1026 | // the latch of InnerLoop, i.e., when defs of the incoming values are further | |||
| 1027 | // inside the loopnest. Sometimes those incoming values are not available | |||
| 1028 | // after interchange, since the original inner latch will become the new outer | |||
| 1029 | // latch which may have predecessor paths that do not include those incoming | |||
| 1030 | // values. | |||
| 1031 | // TODO: Handle transformation of lcssa phis in the InnerLoop latch in case of | |||
| 1032 | // multi-level loop nests. | |||
| 1033 | static bool areInnerLoopLatchPHIsSupported(Loop *OuterLoop, Loop *InnerLoop) { | |||
| 1034 | if (InnerLoop->getSubLoops().empty()) | |||
| 1035 | return true; | |||
| 1036 | // If the original outer latch has only one predecessor, then values defined | |||
| 1037 | // further inside the looploop, e.g., in the innermost loop, will be available | |||
| 1038 | // at the new outer latch after interchange. | |||
| 1039 | if (OuterLoop->getLoopLatch()->getUniquePredecessor() != nullptr) | |||
| 1040 | return true; | |||
| 1041 | ||||
| 1042 | // The outer latch has more than one predecessors, i.e., the inner | |||
| 1043 | // exit and the inner header. | |||
| 1044 | // PHI nodes in the inner latch are lcssa phis where the incoming values | |||
| 1045 | // are defined further inside the loopnest. Check if those phis are used | |||
| 1046 | // in the original inner latch. If that is the case then bail out since | |||
| 1047 | // those incoming values may not be available at the new outer latch. | |||
| 1048 | BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch(); | |||
| 1049 | for (PHINode &PHI : InnerLoopLatch->phis()) { | |||
| 1050 | for (auto *U : PHI.users()) { | |||
| 1051 | Instruction *UI = cast<Instruction>(U); | |||
| 1052 | if (InnerLoopLatch == UI->getParent()) | |||
| 1053 | return false; | |||
| 1054 | } | |||
| 1055 | } | |||
| 1056 | return true; | |||
| 1057 | } | |||
| 1058 | ||||
| 1059 | bool LoopInterchangeLegality::canInterchangeLoops(unsigned InnerLoopId, | |||
| 1060 | unsigned OuterLoopId, | |||
| 1061 | CharMatrix &DepMatrix) { | |||
| 1062 | if (!isLegalToInterChangeLoops(DepMatrix, InnerLoopId, OuterLoopId)) { | |||
| 1063 | LLVM_DEBUG(dbgs() << "Failed interchange InnerLoopId = " << InnerLoopIddo { } while (false) | |||
| 1064 | << " and OuterLoopId = " << OuterLoopIddo { } while (false) | |||
| 1065 | << " due to dependence\n")do { } while (false); | |||
| 1066 | ORE->emit([&]() { | |||
| 1067 | return OptimizationRemarkMissed(DEBUG_TYPE"loop-interchange", "Dependence", | |||
| 1068 | InnerLoop->getStartLoc(), | |||
| 1069 | InnerLoop->getHeader()) | |||
| 1070 | << "Cannot interchange loops due to dependences."; | |||
| 1071 | }); | |||
| 1072 | return false; | |||
| 1073 | } | |||
| 1074 | // Check if outer and inner loop contain legal instructions only. | |||
| 1075 | for (auto *BB : OuterLoop->blocks()) | |||
| 1076 | for (Instruction &I : BB->instructionsWithoutDebug()) | |||
| 1077 | if (CallInst *CI = dyn_cast<CallInst>(&I)) { | |||
| 1078 | // readnone functions do not prevent interchanging. | |||
| 1079 | if (CI->doesNotReadMemory()) | |||
| 1080 | continue; | |||
| 1081 | LLVM_DEBUG(do { } while (false) | |||
| 1082 | dbgs() << "Loops with call instructions cannot be interchanged "do { } while (false) | |||
| 1083 | << "safely.")do { } while (false); | |||
| 1084 | ORE->emit([&]() { | |||
| 1085 | return OptimizationRemarkMissed(DEBUG_TYPE"loop-interchange", "CallInst", | |||
| 1086 | CI->getDebugLoc(), | |||
| 1087 | CI->getParent()) | |||
| 1088 | << "Cannot interchange loops due to call instruction."; | |||
| 1089 | }); | |||
| 1090 | ||||
| 1091 | return false; | |||
| 1092 | } | |||
| 1093 | ||||
| 1094 | if (!areInnerLoopLatchPHIsSupported(OuterLoop, InnerLoop)) { | |||
| 1095 | LLVM_DEBUG(dbgs() << "Found unsupported PHI nodes in inner loop latch.\n")do { } while (false); | |||
| 1096 | ORE->emit([&]() { | |||
| 1097 | return OptimizationRemarkMissed(DEBUG_TYPE"loop-interchange", "UnsupportedInnerLatchPHI", | |||
| 1098 | InnerLoop->getStartLoc(), | |||
| 1099 | InnerLoop->getHeader()) | |||
| 1100 | << "Cannot interchange loops because unsupported PHI nodes found " | |||
| 1101 | "in inner loop latch."; | |||
| 1102 | }); | |||
| 1103 | return false; | |||
| 1104 | } | |||
| 1105 | ||||
| 1106 | // TODO: The loops could not be interchanged due to current limitations in the | |||
| 1107 | // transform module. | |||
| 1108 | if (currentLimitations()) { | |||
| 1109 | LLVM_DEBUG(dbgs() << "Not legal because of current transform limitation\n")do { } while (false); | |||
| 1110 | return false; | |||
| 1111 | } | |||
| 1112 | ||||
| 1113 | // Check if the loops are tightly nested. | |||
| 1114 | if (!tightlyNested(OuterLoop, InnerLoop)) { | |||
| 1115 | LLVM_DEBUG(dbgs() << "Loops not tightly nested\n")do { } while (false); | |||
| 1116 | ORE->emit([&]() { | |||
| 1117 | return OptimizationRemarkMissed(DEBUG_TYPE"loop-interchange", "NotTightlyNested", | |||
| 1118 | InnerLoop->getStartLoc(), | |||
| 1119 | InnerLoop->getHeader()) | |||
| 1120 | << "Cannot interchange loops because they are not tightly " | |||
| 1121 | "nested."; | |||
| 1122 | }); | |||
| 1123 | return false; | |||
| 1124 | } | |||
| 1125 | ||||
| 1126 | if (!areInnerLoopExitPHIsSupported(OuterLoop, InnerLoop, | |||
| 1127 | OuterInnerReductions)) { | |||
| 1128 | LLVM_DEBUG(dbgs() << "Found unsupported PHI nodes in inner loop exit.\n")do { } while (false); | |||
| 1129 | ORE->emit([&]() { | |||
| 1130 | return OptimizationRemarkMissed(DEBUG_TYPE"loop-interchange", "UnsupportedExitPHI", | |||
| 1131 | InnerLoop->getStartLoc(), | |||
| 1132 | InnerLoop->getHeader()) | |||
| 1133 | << "Found unsupported PHI node in loop exit."; | |||
| 1134 | }); | |||
| 1135 | return false; | |||
| 1136 | } | |||
| 1137 | ||||
| 1138 | if (!areOuterLoopExitPHIsSupported(OuterLoop, InnerLoop)) { | |||
| 1139 | LLVM_DEBUG(dbgs() << "Found unsupported PHI nodes in outer loop exit.\n")do { } while (false); | |||
| 1140 | ORE->emit([&]() { | |||
| 1141 | return OptimizationRemarkMissed(DEBUG_TYPE"loop-interchange", "UnsupportedExitPHI", | |||
| 1142 | OuterLoop->getStartLoc(), | |||
| 1143 | OuterLoop->getHeader()) | |||
| 1144 | << "Found unsupported PHI node in loop exit."; | |||
| 1145 | }); | |||
| 1146 | return false; | |||
| 1147 | } | |||
| 1148 | ||||
| 1149 | return true; | |||
| 1150 | } | |||
| 1151 | ||||
| 1152 | int LoopInterchangeProfitability::getInstrOrderCost() { | |||
| 1153 | unsigned GoodOrder, BadOrder; | |||
| 1154 | BadOrder = GoodOrder = 0; | |||
| 1155 | for (BasicBlock *BB : InnerLoop->blocks()) { | |||
| 1156 | for (Instruction &Ins : *BB) { | |||
| 1157 | if (const GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(&Ins)) { | |||
| 1158 | unsigned NumOp = GEP->getNumOperands(); | |||
| 1159 | bool FoundInnerInduction = false; | |||
| 1160 | bool FoundOuterInduction = false; | |||
| 1161 | for (unsigned i = 0; i < NumOp; ++i) { | |||
| 1162 | // Skip operands that are not SCEV-able. | |||
| 1163 | if (!SE->isSCEVable(GEP->getOperand(i)->getType())) | |||
| 1164 | continue; | |||
| 1165 | ||||
| 1166 | const SCEV *OperandVal = SE->getSCEV(GEP->getOperand(i)); | |||
| 1167 | const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(OperandVal); | |||
| 1168 | if (!AR) | |||
| 1169 | continue; | |||
| 1170 | ||||
| 1171 | // If we find the inner induction after an outer induction e.g. | |||
| 1172 | // for(int i=0;i<N;i++) | |||
| 1173 | // for(int j=0;j<N;j++) | |||
| 1174 | // A[i][j] = A[i-1][j-1]+k; | |||
| 1175 | // then it is a good order. | |||
| 1176 | if (AR->getLoop() == InnerLoop) { | |||
| 1177 | // We found an InnerLoop induction after OuterLoop induction. It is | |||
| 1178 | // a good order. | |||
| 1179 | FoundInnerInduction = true; | |||
| 1180 | if (FoundOuterInduction) { | |||
| 1181 | GoodOrder++; | |||
| 1182 | break; | |||
| 1183 | } | |||
| 1184 | } | |||
| 1185 | // If we find the outer induction after an inner induction e.g. | |||
| 1186 | // for(int i=0;i<N;i++) | |||
| 1187 | // for(int j=0;j<N;j++) | |||
| 1188 | // A[j][i] = A[j-1][i-1]+k; | |||
| 1189 | // then it is a bad order. | |||
| 1190 | if (AR->getLoop() == OuterLoop) { | |||
| 1191 | // We found an OuterLoop induction after InnerLoop induction. It is | |||
| 1192 | // a bad order. | |||
| 1193 | FoundOuterInduction = true; | |||
| 1194 | if (FoundInnerInduction) { | |||
| 1195 | BadOrder++; | |||
| 1196 | break; | |||
| 1197 | } | |||
| 1198 | } | |||
| 1199 | } | |||
| 1200 | } | |||
| 1201 | } | |||
| 1202 | } | |||
| 1203 | return GoodOrder - BadOrder; | |||
| 1204 | } | |||
| 1205 | ||||
| 1206 | static bool isProfitableForVectorization(unsigned InnerLoopId, | |||
| 1207 | unsigned OuterLoopId, | |||
| 1208 | CharMatrix &DepMatrix) { | |||
| 1209 | // TODO: Improve this heuristic to catch more cases. | |||
| 1210 | // If the inner loop is loop independent or doesn't carry any dependency it is | |||
| 1211 | // profitable to move this to outer position. | |||
| 1212 | for (auto &Row : DepMatrix) { | |||
| 1213 | if (Row[InnerLoopId] != 'S' && Row[InnerLoopId] != 'I') | |||
| 1214 | return false; | |||
| 1215 | // TODO: We need to improve this heuristic. | |||
| 1216 | if (Row[OuterLoopId] != '=') | |||
| 1217 | return false; | |||
| 1218 | } | |||
| 1219 | // If outer loop has dependence and inner loop is loop independent then it is | |||
| 1220 | // profitable to interchange to enable parallelism. | |||
| 1221 | // If there are no dependences, interchanging will not improve anything. | |||
| 1222 | return !DepMatrix.empty(); | |||
| 1223 | } | |||
| 1224 | ||||
| 1225 | bool LoopInterchangeProfitability::isProfitable(unsigned InnerLoopId, | |||
| 1226 | unsigned OuterLoopId, | |||
| 1227 | CharMatrix &DepMatrix) { | |||
| 1228 | // TODO: Add better profitability checks. | |||
| 1229 | // e.g | |||
| 1230 | // 1) Construct dependency matrix and move the one with no loop carried dep | |||
| 1231 | // inside to enable vectorization. | |||
| 1232 | ||||
| 1233 | // This is rough cost estimation algorithm. It counts the good and bad order | |||
| 1234 | // of induction variables in the instruction and allows reordering if number | |||
| 1235 | // of bad orders is more than good. | |||
| 1236 | int Cost = getInstrOrderCost(); | |||
| 1237 | LLVM_DEBUG(dbgs() << "Cost = " << Cost << "\n")do { } while (false); | |||
| 1238 | if (Cost < -LoopInterchangeCostThreshold) | |||
| 1239 | return true; | |||
| 1240 | ||||
| 1241 | // It is not profitable as per current cache profitability model. But check if | |||
| 1242 | // we can move this loop outside to improve parallelism. | |||
| 1243 | if (isProfitableForVectorization(InnerLoopId, OuterLoopId, DepMatrix)) | |||
| 1244 | return true; | |||
| 1245 | ||||
| 1246 | ORE->emit([&]() { | |||
| 1247 | return OptimizationRemarkMissed(DEBUG_TYPE"loop-interchange", "InterchangeNotProfitable", | |||
| 1248 | InnerLoop->getStartLoc(), | |||
| 1249 | InnerLoop->getHeader()) | |||
| 1250 | << "Interchanging loops is too costly (cost=" | |||
| 1251 | << ore::NV("Cost", Cost) << ", threshold=" | |||
| 1252 | << ore::NV("Threshold", LoopInterchangeCostThreshold) | |||
| 1253 | << ") and it does not improve parallelism."; | |||
| 1254 | }); | |||
| 1255 | return false; | |||
| 1256 | } | |||
| 1257 | ||||
| 1258 | void LoopInterchangeTransform::removeChildLoop(Loop *OuterLoop, | |||
| 1259 | Loop *InnerLoop) { | |||
| 1260 | for (Loop *L : *OuterLoop) | |||
| 1261 | if (L == InnerLoop) { | |||
| 1262 | OuterLoop->removeChildLoop(L); | |||
| 1263 | return; | |||
| 1264 | } | |||
| 1265 | llvm_unreachable("Couldn't find loop")__builtin_unreachable(); | |||
| 1266 | } | |||
| 1267 | ||||
| 1268 | /// Update LoopInfo, after interchanging. NewInner and NewOuter refer to the | |||
| 1269 | /// new inner and outer loop after interchanging: NewInner is the original | |||
| 1270 | /// outer loop and NewOuter is the original inner loop. | |||
| 1271 | /// | |||
| 1272 | /// Before interchanging, we have the following structure | |||
| 1273 | /// Outer preheader | |||
| 1274 | // Outer header | |||
| 1275 | // Inner preheader | |||
| 1276 | // Inner header | |||
| 1277 | // Inner body | |||
| 1278 | // Inner latch | |||
| 1279 | // outer bbs | |||
| 1280 | // Outer latch | |||
| 1281 | // | |||
| 1282 | // After interchanging: | |||
| 1283 | // Inner preheader | |||
| 1284 | // Inner header | |||
| 1285 | // Outer preheader | |||
| 1286 | // Outer header | |||
| 1287 | // Inner body | |||
| 1288 | // outer bbs | |||
| 1289 | // Outer latch | |||
| 1290 | // Inner latch | |||
| 1291 | void LoopInterchangeTransform::restructureLoops( | |||
| 1292 | Loop *NewInner, Loop *NewOuter, BasicBlock *OrigInnerPreHeader, | |||
| 1293 | BasicBlock *OrigOuterPreHeader) { | |||
| 1294 | Loop *OuterLoopParent = OuterLoop->getParentLoop(); | |||
| 1295 | // The original inner loop preheader moves from the new inner loop to | |||
| 1296 | // the parent loop, if there is one. | |||
| 1297 | NewInner->removeBlockFromLoop(OrigInnerPreHeader); | |||
| 1298 | LI->changeLoopFor(OrigInnerPreHeader, OuterLoopParent); | |||
| 1299 | ||||
| 1300 | // Switch the loop levels. | |||
| 1301 | if (OuterLoopParent) { | |||
| 1302 | // Remove the loop from its parent loop. | |||
| 1303 | removeChildLoop(OuterLoopParent, NewInner); | |||
| 1304 | removeChildLoop(NewInner, NewOuter); | |||
| 1305 | OuterLoopParent->addChildLoop(NewOuter); | |||
| 1306 | } else { | |||
| 1307 | removeChildLoop(NewInner, NewOuter); | |||
| 1308 | LI->changeTopLevelLoop(NewInner, NewOuter); | |||
| 1309 | } | |||
| 1310 | while (!NewOuter->isInnermost()) | |||
| 1311 | NewInner->addChildLoop(NewOuter->removeChildLoop(NewOuter->begin())); | |||
| 1312 | NewOuter->addChildLoop(NewInner); | |||
| 1313 | ||||
| 1314 | // BBs from the original inner loop. | |||
| 1315 | SmallVector<BasicBlock *, 8> OrigInnerBBs(NewOuter->blocks()); | |||
| 1316 | ||||
| 1317 | // Add BBs from the original outer loop to the original inner loop (excluding | |||
| 1318 | // BBs already in inner loop) | |||
| 1319 | for (BasicBlock *BB : NewInner->blocks()) | |||
| 1320 | if (LI->getLoopFor(BB) == NewInner) | |||
| 1321 | NewOuter->addBlockEntry(BB); | |||
| 1322 | ||||
| 1323 | // Now remove inner loop header and latch from the new inner loop and move | |||
| 1324 | // other BBs (the loop body) to the new inner loop. | |||
| 1325 | BasicBlock *OuterHeader = NewOuter->getHeader(); | |||
| 1326 | BasicBlock *OuterLatch = NewOuter->getLoopLatch(); | |||
| 1327 | for (BasicBlock *BB : OrigInnerBBs) { | |||
| 1328 | // Nothing will change for BBs in child loops. | |||
| 1329 | if (LI->getLoopFor(BB) != NewOuter) | |||
| 1330 | continue; | |||
| 1331 | // Remove the new outer loop header and latch from the new inner loop. | |||
| 1332 | if (BB == OuterHeader || BB == OuterLatch) | |||
| 1333 | NewInner->removeBlockFromLoop(BB); | |||
| 1334 | else | |||
| 1335 | LI->changeLoopFor(BB, NewInner); | |||
| 1336 | } | |||
| 1337 | ||||
| 1338 | // The preheader of the original outer loop becomes part of the new | |||
| 1339 | // outer loop. | |||
| 1340 | NewOuter->addBlockEntry(OrigOuterPreHeader); | |||
| 1341 | LI->changeLoopFor(OrigOuterPreHeader, NewOuter); | |||
| 1342 | ||||
| 1343 | // Tell SE that we move the loops around. | |||
| 1344 | SE->forgetLoop(NewOuter); | |||
| 1345 | SE->forgetLoop(NewInner); | |||
| 1346 | } | |||
| 1347 | ||||
| 1348 | bool LoopInterchangeTransform::transform() { | |||
| 1349 | bool Transformed = false; | |||
| 1350 | Instruction *InnerIndexVar; | |||
| 1351 | ||||
| 1352 | if (InnerLoop->getSubLoops().empty()) { | |||
| 1353 | BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader(); | |||
| 1354 | LLVM_DEBUG(dbgs() << "Splitting the inner loop latch\n")do { } while (false); | |||
| 1355 | PHINode *InductionPHI = getInductionVariable(InnerLoop, SE); | |||
| 1356 | if (!InductionPHI) { | |||
| 1357 | LLVM_DEBUG(dbgs() << "Failed to find the point to split loop latch \n")do { } while (false); | |||
| 1358 | return false; | |||
| 1359 | } | |||
| 1360 | ||||
| 1361 | if (InductionPHI->getIncomingBlock(0) == InnerLoopPreHeader) | |||
| 1362 | InnerIndexVar = dyn_cast<Instruction>(InductionPHI->getIncomingValue(1)); | |||
| 1363 | else | |||
| 1364 | InnerIndexVar = dyn_cast<Instruction>(InductionPHI->getIncomingValue(0)); | |||
| 1365 | ||||
| 1366 | // Ensure that InductionPHI is the first Phi node. | |||
| 1367 | if (&InductionPHI->getParent()->front() != InductionPHI) | |||
| 1368 | InductionPHI->moveBefore(&InductionPHI->getParent()->front()); | |||
| 1369 | ||||
| 1370 | // Create a new latch block for the inner loop. We split at the | |||
| 1371 | // current latch's terminator and then move the condition and all | |||
| 1372 | // operands that are not either loop-invariant or the induction PHI into the | |||
| 1373 | // new latch block. | |||
| 1374 | BasicBlock *NewLatch = | |||
| 1375 | SplitBlock(InnerLoop->getLoopLatch(), | |||
| 1376 | InnerLoop->getLoopLatch()->getTerminator(), DT, LI); | |||
| 1377 | ||||
| 1378 | SmallSetVector<Instruction *, 4> WorkList; | |||
| 1379 | unsigned i = 0; | |||
| 1380 | auto MoveInstructions = [&i, &WorkList, this, InductionPHI, NewLatch]() { | |||
| 1381 | for (; i < WorkList.size(); i++) { | |||
| 1382 | // Duplicate instruction and move it the new latch. Update uses that | |||
| 1383 | // have been moved. | |||
| 1384 | Instruction *NewI = WorkList[i]->clone(); | |||
| 1385 | NewI->insertBefore(NewLatch->getFirstNonPHI()); | |||
| 1386 | assert(!NewI->mayHaveSideEffects() &&((void)0) | |||
| 1387 | "Moving instructions with side-effects may change behavior of "((void)0) | |||
| 1388 | "the loop nest!")((void)0); | |||
| 1389 | for (Use &U : llvm::make_early_inc_range(WorkList[i]->uses())) { | |||
| 1390 | Instruction *UserI = cast<Instruction>(U.getUser()); | |||
| 1391 | if (!InnerLoop->contains(UserI->getParent()) || | |||
| 1392 | UserI->getParent() == NewLatch || UserI == InductionPHI) | |||
| 1393 | U.set(NewI); | |||
| 1394 | } | |||
| 1395 | // Add operands of moved instruction to the worklist, except if they are | |||
| 1396 | // outside the inner loop or are the induction PHI. | |||
| 1397 | for (Value *Op : WorkList[i]->operands()) { | |||
| 1398 | Instruction *OpI = dyn_cast<Instruction>(Op); | |||
| 1399 | if (!OpI || | |||
| 1400 | this->LI->getLoopFor(OpI->getParent()) != this->InnerLoop || | |||
| 1401 | OpI == InductionPHI) | |||
| 1402 | continue; | |||
| 1403 | WorkList.insert(OpI); | |||
| 1404 | } | |||
| 1405 | } | |||
| 1406 | }; | |||
| 1407 | ||||
| 1408 | // FIXME: Should we interchange when we have a constant condition? | |||
| 1409 | Instruction *CondI = dyn_cast<Instruction>( | |||
| 1410 | cast<BranchInst>(InnerLoop->getLoopLatch()->getTerminator()) | |||
| 1411 | ->getCondition()); | |||
| 1412 | if (CondI) | |||
| 1413 | WorkList.insert(CondI); | |||
| 1414 | MoveInstructions(); | |||
| 1415 | WorkList.insert(cast<Instruction>(InnerIndexVar)); | |||
| 1416 | MoveInstructions(); | |||
| 1417 | ||||
| 1418 | // Splits the inner loops phi nodes out into a separate basic block. | |||
| 1419 | BasicBlock *InnerLoopHeader = InnerLoop->getHeader(); | |||
| 1420 | SplitBlock(InnerLoopHeader, InnerLoopHeader->getFirstNonPHI(), DT, LI); | |||
| 1421 | LLVM_DEBUG(dbgs() << "splitting InnerLoopHeader done\n")do { } while (false); | |||
| 1422 | } | |||
| 1423 | ||||
| 1424 | // Instructions in the original inner loop preheader may depend on values | |||
| 1425 | // defined in the outer loop header. Move them there, because the original | |||
| 1426 | // inner loop preheader will become the entry into the interchanged loop nest. | |||
| 1427 | // Currently we move all instructions and rely on LICM to move invariant | |||
| 1428 | // instructions outside the loop nest. | |||
| 1429 | BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader(); | |||
| 1430 | BasicBlock *OuterLoopHeader = OuterLoop->getHeader(); | |||
| 1431 | if (InnerLoopPreHeader != OuterLoopHeader) { | |||
| 1432 | SmallPtrSet<Instruction *, 4> NeedsMoving; | |||
| 1433 | for (Instruction &I : | |||
| 1434 | make_early_inc_range(make_range(InnerLoopPreHeader->begin(), | |||
| 1435 | std::prev(InnerLoopPreHeader->end())))) | |||
| 1436 | I.moveBefore(OuterLoopHeader->getTerminator()); | |||
| 1437 | } | |||
| 1438 | ||||
| 1439 | Transformed |= adjustLoopLinks(); | |||
| 1440 | if (!Transformed) { | |||
| 1441 | LLVM_DEBUG(dbgs() << "adjustLoopLinks failed\n")do { } while (false); | |||
| 1442 | return false; | |||
| 1443 | } | |||
| 1444 | ||||
| 1445 | return true; | |||
| 1446 | } | |||
| 1447 | ||||
| 1448 | /// \brief Move all instructions except the terminator from FromBB right before | |||
| 1449 | /// InsertBefore | |||
| 1450 | static void moveBBContents(BasicBlock *FromBB, Instruction *InsertBefore) { | |||
| 1451 | auto &ToList = InsertBefore->getParent()->getInstList(); | |||
| 1452 | auto &FromList = FromBB->getInstList(); | |||
| 1453 | ||||
| 1454 | ToList.splice(InsertBefore->getIterator(), FromList, FromList.begin(), | |||
| 1455 | FromBB->getTerminator()->getIterator()); | |||
| 1456 | } | |||
| 1457 | ||||
| 1458 | /// Swap instructions between \p BB1 and \p BB2 but keep terminators intact. | |||
| 1459 | static void swapBBContents(BasicBlock *BB1, BasicBlock *BB2) { | |||
| 1460 | // Save all non-terminator instructions of BB1 into TempInstrs and unlink them | |||
| 1461 | // from BB1 afterwards. | |||
| 1462 | auto Iter = map_range(*BB1, [](Instruction &I) { return &I; }); | |||
| 1463 | SmallVector<Instruction *, 4> TempInstrs(Iter.begin(), std::prev(Iter.end())); | |||
| 1464 | for (Instruction *I : TempInstrs) | |||
| 1465 | I->removeFromParent(); | |||
| 1466 | ||||
| 1467 | // Move instructions from BB2 to BB1. | |||
| 1468 | moveBBContents(BB2, BB1->getTerminator()); | |||
| 1469 | ||||
| 1470 | // Move instructions from TempInstrs to BB2. | |||
| 1471 | for (Instruction *I : TempInstrs) | |||
| 1472 | I->insertBefore(BB2->getTerminator()); | |||
| 1473 | } | |||
| 1474 | ||||
| 1475 | // Update BI to jump to NewBB instead of OldBB. Records updates to the | |||
| 1476 | // dominator tree in DTUpdates. If \p MustUpdateOnce is true, assert that | |||
| 1477 | // \p OldBB is exactly once in BI's successor list. | |||
| 1478 | static void updateSuccessor(BranchInst *BI, BasicBlock *OldBB, | |||
| 1479 | BasicBlock *NewBB, | |||
| 1480 | std::vector<DominatorTree::UpdateType> &DTUpdates, | |||
| 1481 | bool MustUpdateOnce = true) { | |||
| 1482 | assert((!MustUpdateOnce ||((void)0) | |||
| 1483 | llvm::count_if(successors(BI),((void)0) | |||
| 1484 | [OldBB](BasicBlock *BB) {((void)0) | |||
| 1485 | return BB == OldBB;((void)0) | |||
| 1486 | }) == 1) && "BI must jump to OldBB exactly once.")((void)0); | |||
| 1487 | bool Changed = false; | |||
| 1488 | for (Use &Op : BI->operands()) | |||
| 1489 | if (Op == OldBB) { | |||
| 1490 | Op.set(NewBB); | |||
| 1491 | Changed = true; | |||
| 1492 | } | |||
| 1493 | ||||
| 1494 | if (Changed) { | |||
| 1495 | DTUpdates.push_back( | |||
| 1496 | {DominatorTree::UpdateKind::Insert, BI->getParent(), NewBB}); | |||
| 1497 | DTUpdates.push_back( | |||
| 1498 | {DominatorTree::UpdateKind::Delete, BI->getParent(), OldBB}); | |||
| 1499 | } | |||
| 1500 | assert(Changed && "Expected a successor to be updated")((void)0); | |||
| 1501 | } | |||
| 1502 | ||||
| 1503 | // Move Lcssa PHIs to the right place. | |||
| 1504 | static void moveLCSSAPhis(BasicBlock *InnerExit, BasicBlock *InnerHeader, | |||
| 1505 | BasicBlock *InnerLatch, BasicBlock *OuterHeader, | |||
| 1506 | BasicBlock *OuterLatch, BasicBlock *OuterExit, | |||
| 1507 | Loop *InnerLoop, LoopInfo *LI) { | |||
| 1508 | ||||
| 1509 | // Deal with LCSSA PHI nodes in the exit block of the inner loop, that are | |||
| 1510 | // defined either in the header or latch. Those blocks will become header and | |||
| 1511 | // latch of the new outer loop, and the only possible users can PHI nodes | |||
| 1512 | // in the exit block of the loop nest or the outer loop header (reduction | |||
| 1513 | // PHIs, in that case, the incoming value must be defined in the inner loop | |||
| 1514 | // header). We can just substitute the user with the incoming value and remove | |||
| 1515 | // the PHI. | |||
| 1516 | for (PHINode &P : make_early_inc_range(InnerExit->phis())) { | |||
| 1517 | assert(P.getNumIncomingValues() == 1 &&((void)0) | |||
| 1518 | "Only loops with a single exit are supported!")((void)0); | |||
| 1519 | ||||
| 1520 | // Incoming values are guaranteed be instructions currently. | |||
| 1521 | auto IncI = cast<Instruction>(P.getIncomingValueForBlock(InnerLatch)); | |||
| 1522 | // Skip phis with incoming values from the inner loop body, excluding the | |||
| 1523 | // header and latch. | |||
| 1524 | if (IncI->getParent() != InnerLatch && IncI->getParent() != InnerHeader) | |||
| 1525 | continue; | |||
| 1526 | ||||
| 1527 | assert(all_of(P.users(),((void)0) | |||
| 1528 | [OuterHeader, OuterExit, IncI, InnerHeader](User *U) {((void)0) | |||
| 1529 | return (cast<PHINode>(U)->getParent() == OuterHeader &&((void)0) | |||
| 1530 | IncI->getParent() == InnerHeader) ||((void)0) | |||
| 1531 | cast<PHINode>(U)->getParent() == OuterExit;((void)0) | |||
| 1532 | }) &&((void)0) | |||
| 1533 | "Can only replace phis iff the uses are in the loop nest exit or "((void)0) | |||
| 1534 | "the incoming value is defined in the inner header (it will "((void)0) | |||
| 1535 | "dominate all loop blocks after interchanging)")((void)0); | |||
| 1536 | P.replaceAllUsesWith(IncI); | |||
| 1537 | P.eraseFromParent(); | |||
| 1538 | } | |||
| 1539 | ||||
| 1540 | SmallVector<PHINode *, 8> LcssaInnerExit; | |||
| 1541 | for (PHINode &P : InnerExit->phis()) | |||
| 1542 | LcssaInnerExit.push_back(&P); | |||
| 1543 | ||||
| 1544 | SmallVector<PHINode *, 8> LcssaInnerLatch; | |||
| 1545 | for (PHINode &P : InnerLatch->phis()) | |||
| 1546 | LcssaInnerLatch.push_back(&P); | |||
| 1547 | ||||
| 1548 | // Lcssa PHIs for values used outside the inner loop are in InnerExit. | |||
| 1549 | // If a PHI node has users outside of InnerExit, it has a use outside the | |||
| 1550 | // interchanged loop and we have to preserve it. We move these to | |||
| 1551 | // InnerLatch, which will become the new exit block for the innermost | |||
| 1552 | // loop after interchanging. | |||
| 1553 | for (PHINode *P : LcssaInnerExit) | |||
| ||||
| 1554 | P->moveBefore(InnerLatch->getFirstNonPHI()); | |||
| 1555 | ||||
| 1556 | // If the inner loop latch contains LCSSA PHIs, those come from a child loop | |||
| 1557 | // and we have to move them to the new inner latch. | |||
| 1558 | for (PHINode *P : LcssaInnerLatch) | |||
| 1559 | P->moveBefore(InnerExit->getFirstNonPHI()); | |||
| 1560 | ||||
| 1561 | // Deal with LCSSA PHI nodes in the loop nest exit block. For PHIs that have | |||
| 1562 | // incoming values defined in the outer loop, we have to add a new PHI | |||
| 1563 | // in the inner loop latch, which became the exit block of the outer loop, | |||
| 1564 | // after interchanging. | |||
| 1565 | if (OuterExit) { | |||
| 1566 | for (PHINode &P : OuterExit->phis()) { | |||
| 1567 | if (P.getNumIncomingValues() != 1) | |||
| 1568 | continue; | |||
| 1569 | // Skip Phis with incoming values defined in the inner loop. Those should | |||
| 1570 | // already have been updated. | |||
| 1571 | auto I = dyn_cast<Instruction>(P.getIncomingValue(0)); | |||
| 1572 | if (!I || LI->getLoopFor(I->getParent()) == InnerLoop) | |||
| 1573 | continue; | |||
| 1574 | ||||
| 1575 | PHINode *NewPhi = dyn_cast<PHINode>(P.clone()); | |||
| 1576 | NewPhi->setIncomingValue(0, P.getIncomingValue(0)); | |||
| ||||
| 1577 | NewPhi->setIncomingBlock(0, OuterLatch); | |||
| 1578 | // We might have incoming edges from other BBs, i.e., the original outer | |||
| 1579 | // header. | |||
| 1580 | for (auto *Pred : predecessors(InnerLatch)) { | |||
| 1581 | if (Pred == OuterLatch) | |||
| 1582 | continue; | |||
| 1583 | NewPhi->addIncoming(P.getIncomingValue(0), Pred); | |||
| 1584 | } | |||
| 1585 | NewPhi->insertBefore(InnerLatch->getFirstNonPHI()); | |||
| 1586 | P.setIncomingValue(0, NewPhi); | |||
| 1587 | } | |||
| 1588 | } | |||
| 1589 | ||||
| 1590 | // Now adjust the incoming blocks for the LCSSA PHIs. | |||
| 1591 | // For PHIs moved from Inner's exit block, we need to replace Inner's latch | |||
| 1592 | // with the new latch. | |||
| 1593 | InnerLatch->replacePhiUsesWith(InnerLatch, OuterLatch); | |||
| 1594 | } | |||
| 1595 | ||||
| 1596 | bool LoopInterchangeTransform::adjustLoopBranches() { | |||
| 1597 | LLVM_DEBUG(dbgs() << "adjustLoopBranches called\n")do { } while (false); | |||
| 1598 | std::vector<DominatorTree::UpdateType> DTUpdates; | |||
| 1599 | ||||
| 1600 | BasicBlock *OuterLoopPreHeader = OuterLoop->getLoopPreheader(); | |||
| 1601 | BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader(); | |||
| 1602 | ||||
| 1603 | assert(OuterLoopPreHeader != OuterLoop->getHeader() &&((void)0) | |||
| 1604 | InnerLoopPreHeader != InnerLoop->getHeader() && OuterLoopPreHeader &&((void)0) | |||
| 1605 | InnerLoopPreHeader && "Guaranteed by loop-simplify form")((void)0); | |||
| 1606 | // Ensure that both preheaders do not contain PHI nodes and have single | |||
| 1607 | // predecessors. This allows us to move them easily. We use | |||
| 1608 | // InsertPreHeaderForLoop to create an 'extra' preheader, if the existing | |||
| 1609 | // preheaders do not satisfy those conditions. | |||
| 1610 | if (isa<PHINode>(OuterLoopPreHeader->begin()) || | |||
| 1611 | !OuterLoopPreHeader->getUniquePredecessor()) | |||
| 1612 | OuterLoopPreHeader = | |||
| 1613 | InsertPreheaderForLoop(OuterLoop, DT, LI, nullptr, true); | |||
| 1614 | if (InnerLoopPreHeader == OuterLoop->getHeader()) | |||
| 1615 | InnerLoopPreHeader = | |||
| 1616 | InsertPreheaderForLoop(InnerLoop, DT, LI, nullptr, true); | |||
| 1617 | ||||
| 1618 | // Adjust the loop preheader | |||
| 1619 | BasicBlock *InnerLoopHeader = InnerLoop->getHeader(); | |||
| 1620 | BasicBlock *OuterLoopHeader = OuterLoop->getHeader(); | |||
| 1621 | BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch(); | |||
| 1622 | BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch(); | |||
| 1623 | BasicBlock *OuterLoopPredecessor = OuterLoopPreHeader->getUniquePredecessor(); | |||
| 1624 | BasicBlock *InnerLoopLatchPredecessor = | |||
| 1625 | InnerLoopLatch->getUniquePredecessor(); | |||
| 1626 | BasicBlock *InnerLoopLatchSuccessor; | |||
| 1627 | BasicBlock *OuterLoopLatchSuccessor; | |||
| 1628 | ||||
| 1629 | BranchInst *OuterLoopLatchBI = | |||
| 1630 | dyn_cast<BranchInst>(OuterLoopLatch->getTerminator()); | |||
| 1631 | BranchInst *InnerLoopLatchBI = | |||
| 1632 | dyn_cast<BranchInst>(InnerLoopLatch->getTerminator()); | |||
| 1633 | BranchInst *OuterLoopHeaderBI = | |||
| 1634 | dyn_cast<BranchInst>(OuterLoopHeader->getTerminator()); | |||
| 1635 | BranchInst *InnerLoopHeaderBI = | |||
| 1636 | dyn_cast<BranchInst>(InnerLoopHeader->getTerminator()); | |||
| 1637 | ||||
| 1638 | if (!OuterLoopPredecessor || !InnerLoopLatchPredecessor || | |||
| 1639 | !OuterLoopLatchBI || !InnerLoopLatchBI || !OuterLoopHeaderBI || | |||
| 1640 | !InnerLoopHeaderBI) | |||
| 1641 | return false; | |||
| 1642 | ||||
| 1643 | BranchInst *InnerLoopLatchPredecessorBI = | |||
| 1644 | dyn_cast<BranchInst>(InnerLoopLatchPredecessor->getTerminator()); | |||
| 1645 | BranchInst *OuterLoopPredecessorBI = | |||
| 1646 | dyn_cast<BranchInst>(OuterLoopPredecessor->getTerminator()); | |||
| 1647 | ||||
| 1648 | if (!OuterLoopPredecessorBI || !InnerLoopLatchPredecessorBI) | |||
| 1649 | return false; | |||
| 1650 | BasicBlock *InnerLoopHeaderSuccessor = InnerLoopHeader->getUniqueSuccessor(); | |||
| 1651 | if (!InnerLoopHeaderSuccessor) | |||
| 1652 | return false; | |||
| 1653 | ||||
| 1654 | // Adjust Loop Preheader and headers. | |||
| 1655 | // The branches in the outer loop predecessor and the outer loop header can | |||
| 1656 | // be unconditional branches or conditional branches with duplicates. Consider | |||
| 1657 | // this when updating the successors. | |||
| 1658 | updateSuccessor(OuterLoopPredecessorBI, OuterLoopPreHeader, | |||
| 1659 | InnerLoopPreHeader, DTUpdates, /*MustUpdateOnce=*/false); | |||
| 1660 | // The outer loop header might or might not branch to the outer latch. | |||
| 1661 | // We are guaranteed to branch to the inner loop preheader. | |||
| 1662 | if (llvm::is_contained(OuterLoopHeaderBI->successors(), OuterLoopLatch)) { | |||
| 1663 | // In this case the outerLoopHeader should branch to the InnerLoopLatch. | |||
| 1664 | updateSuccessor(OuterLoopHeaderBI, OuterLoopLatch, InnerLoopLatch, | |||
| 1665 | DTUpdates, | |||
| 1666 | /*MustUpdateOnce=*/false); | |||
| 1667 | } | |||
| 1668 | updateSuccessor(OuterLoopHeaderBI, InnerLoopPreHeader, | |||
| 1669 | InnerLoopHeaderSuccessor, DTUpdates, | |||
| 1670 | /*MustUpdateOnce=*/false); | |||
| 1671 | ||||
| 1672 | // Adjust reduction PHI's now that the incoming block has changed. | |||
| 1673 | InnerLoopHeaderSuccessor->replacePhiUsesWith(InnerLoopHeader, | |||
| 1674 | OuterLoopHeader); | |||
| 1675 | ||||
| 1676 | updateSuccessor(InnerLoopHeaderBI, InnerLoopHeaderSuccessor, | |||
| 1677 | OuterLoopPreHeader, DTUpdates); | |||
| 1678 | ||||
| 1679 | // -------------Adjust loop latches----------- | |||
| 1680 | if (InnerLoopLatchBI->getSuccessor(0) == InnerLoopHeader) | |||
| 1681 | InnerLoopLatchSuccessor = InnerLoopLatchBI->getSuccessor(1); | |||
| 1682 | else | |||
| 1683 | InnerLoopLatchSuccessor = InnerLoopLatchBI->getSuccessor(0); | |||
| 1684 | ||||
| 1685 | updateSuccessor(InnerLoopLatchPredecessorBI, InnerLoopLatch, | |||
| 1686 | InnerLoopLatchSuccessor, DTUpdates); | |||
| 1687 | ||||
| 1688 | ||||
| 1689 | if (OuterLoopLatchBI->getSuccessor(0) == OuterLoopHeader) | |||
| 1690 | OuterLoopLatchSuccessor = OuterLoopLatchBI->getSuccessor(1); | |||
| 1691 | else | |||
| 1692 | OuterLoopLatchSuccessor = OuterLoopLatchBI->getSuccessor(0); | |||
| 1693 | ||||
| 1694 | updateSuccessor(InnerLoopLatchBI, InnerLoopLatchSuccessor, | |||
| 1695 | OuterLoopLatchSuccessor, DTUpdates); | |||
| 1696 | updateSuccessor(OuterLoopLatchBI, OuterLoopLatchSuccessor, InnerLoopLatch, | |||
| 1697 | DTUpdates); | |||
| 1698 | ||||
| 1699 | DT->applyUpdates(DTUpdates); | |||
| 1700 | restructureLoops(OuterLoop, InnerLoop, InnerLoopPreHeader, | |||
| 1701 | OuterLoopPreHeader); | |||
| 1702 | ||||
| 1703 | moveLCSSAPhis(InnerLoopLatchSuccessor, InnerLoopHeader, InnerLoopLatch, | |||
| 1704 | OuterLoopHeader, OuterLoopLatch, InnerLoop->getExitBlock(), | |||
| 1705 | InnerLoop, LI); | |||
| 1706 | // For PHIs in the exit block of the outer loop, outer's latch has been | |||
| 1707 | // replaced by Inners'. | |||
| 1708 | OuterLoopLatchSuccessor->replacePhiUsesWith(OuterLoopLatch, InnerLoopLatch); | |||
| 1709 | ||||
| 1710 | auto &OuterInnerReductions = LIL.getOuterInnerReductions(); | |||
| 1711 | // Now update the reduction PHIs in the inner and outer loop headers. | |||
| 1712 | SmallVector<PHINode *, 4> InnerLoopPHIs, OuterLoopPHIs; | |||
| 1713 | for (PHINode &PHI : InnerLoopHeader->phis()) { | |||
| 1714 | if (OuterInnerReductions.find(&PHI) == OuterInnerReductions.end()) | |||
| 1715 | continue; | |||
| 1716 | InnerLoopPHIs.push_back(cast<PHINode>(&PHI)); | |||
| 1717 | } | |||
| 1718 | for (PHINode &PHI : OuterLoopHeader->phis()) { | |||
| 1719 | if (OuterInnerReductions.find(&PHI) == OuterInnerReductions.end()) | |||
| 1720 | continue; | |||
| 1721 | OuterLoopPHIs.push_back(cast<PHINode>(&PHI)); | |||
| 1722 | } | |||
| 1723 | ||||
| 1724 | // Now move the remaining reduction PHIs from outer to inner loop header and | |||
| 1725 | // vice versa. The PHI nodes must be part of a reduction across the inner and | |||
| 1726 | // outer loop and all the remains to do is and updating the incoming blocks. | |||
| 1727 | for (PHINode *PHI : OuterLoopPHIs) { | |||
| 1728 | PHI->moveBefore(InnerLoopHeader->getFirstNonPHI()); | |||
| 1729 | assert(OuterInnerReductions.count(PHI) && "Expected a reduction PHI node")((void)0); | |||
| 1730 | } | |||
| 1731 | for (PHINode *PHI : InnerLoopPHIs) { | |||
| 1732 | PHI->moveBefore(OuterLoopHeader->getFirstNonPHI()); | |||
| 1733 | assert(OuterInnerReductions.count(PHI) && "Expected a reduction PHI node")((void)0); | |||
| 1734 | } | |||
| 1735 | ||||
| 1736 | // Update the incoming blocks for moved PHI nodes. | |||
| 1737 | OuterLoopHeader->replacePhiUsesWith(InnerLoopPreHeader, OuterLoopPreHeader); | |||
| 1738 | OuterLoopHeader->replacePhiUsesWith(InnerLoopLatch, OuterLoopLatch); | |||
| 1739 | InnerLoopHeader->replacePhiUsesWith(OuterLoopPreHeader, InnerLoopPreHeader); | |||
| 1740 | InnerLoopHeader->replacePhiUsesWith(OuterLoopLatch, InnerLoopLatch); | |||
| 1741 | ||||
| 1742 | // Values defined in the outer loop header could be used in the inner loop | |||
| 1743 | // latch. In that case, we need to create LCSSA phis for them, because after | |||
| 1744 | // interchanging they will be defined in the new inner loop and used in the | |||
| 1745 | // new outer loop. | |||
| 1746 | IRBuilder<> Builder(OuterLoopHeader->getContext()); | |||
| 1747 | SmallVector<Instruction *, 4> MayNeedLCSSAPhis; | |||
| 1748 | for (Instruction &I : | |||
| 1749 | make_range(OuterLoopHeader->begin(), std::prev(OuterLoopHeader->end()))) | |||
| 1750 | MayNeedLCSSAPhis.push_back(&I); | |||
| 1751 | formLCSSAForInstructions(MayNeedLCSSAPhis, *DT, *LI, SE, Builder); | |||
| 1752 | ||||
| 1753 | return true; | |||
| 1754 | } | |||
| 1755 | ||||
| 1756 | bool LoopInterchangeTransform::adjustLoopLinks() { | |||
| 1757 | // Adjust all branches in the inner and outer loop. | |||
| 1758 | bool Changed = adjustLoopBranches(); | |||
| 1759 | if (Changed) { | |||
| 1760 | // We have interchanged the preheaders so we need to interchange the data in | |||
| 1761 | // the preheaders as well. This is because the content of the inner | |||
| 1762 | // preheader was previously executed inside the outer loop. | |||
| 1763 | BasicBlock *OuterLoopPreHeader = OuterLoop->getLoopPreheader(); | |||
| 1764 | BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader(); | |||
| 1765 | swapBBContents(OuterLoopPreHeader, InnerLoopPreHeader); | |||
| 1766 | } | |||
| 1767 | return Changed; | |||
| 1768 | } | |||
| 1769 | ||||
| 1770 | /// Main LoopInterchange Pass. | |||
| 1771 | struct LoopInterchangeLegacyPass : public LoopPass { | |||
| 1772 | static char ID; | |||
| 1773 | ||||
| 1774 | LoopInterchangeLegacyPass() : LoopPass(ID) { | |||
| 1775 | initializeLoopInterchangeLegacyPassPass(*PassRegistry::getPassRegistry()); | |||
| 1776 | } | |||
| 1777 | ||||
| 1778 | void getAnalysisUsage(AnalysisUsage &AU) const override { | |||
| 1779 | AU.addRequired<DependenceAnalysisWrapperPass>(); | |||
| 1780 | AU.addRequired<OptimizationRemarkEmitterWrapperPass>(); | |||
| 1781 | ||||
| 1782 | getLoopAnalysisUsage(AU); | |||
| 1783 | } | |||
| 1784 | ||||
| 1785 | bool runOnLoop(Loop *L, LPPassManager &LPM) override { | |||
| 1786 | if (skipLoop(L)) | |||
| 1787 | return false; | |||
| 1788 | ||||
| 1789 | auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE(); | |||
| 1790 | auto *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); | |||
| 1791 | auto *DI = &getAnalysis<DependenceAnalysisWrapperPass>().getDI(); | |||
| 1792 | auto *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree(); | |||
| 1793 | auto *ORE = &getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE(); | |||
| 1794 | ||||
| 1795 | return LoopInterchange(SE, LI, DI, DT, ORE).run(L); | |||
| 1796 | } | |||
| 1797 | }; | |||
| 1798 | ||||
| 1799 | char LoopInterchangeLegacyPass::ID = 0; | |||
| 1800 | ||||
| 1801 | INITIALIZE_PASS_BEGIN(LoopInterchangeLegacyPass, "loop-interchange",static void *initializeLoopInterchangeLegacyPassPassOnce(PassRegistry &Registry) { | |||
| 1802 | "Interchanges loops for cache reuse", false, false)static void *initializeLoopInterchangeLegacyPassPassOnce(PassRegistry &Registry) { | |||
| 1803 | INITIALIZE_PASS_DEPENDENCY(LoopPass)initializeLoopPassPass(Registry); | |||
| 1804 | INITIALIZE_PASS_DEPENDENCY(DependenceAnalysisWrapperPass)initializeDependenceAnalysisWrapperPassPass(Registry); | |||
| 1805 | INITIALIZE_PASS_DEPENDENCY(OptimizationRemarkEmitterWrapperPass)initializeOptimizationRemarkEmitterWrapperPassPass(Registry); | |||
| 1806 | ||||
| 1807 | INITIALIZE_PASS_END(LoopInterchangeLegacyPass, "loop-interchange",PassInfo *PI = new PassInfo( "Interchanges loops for cache reuse" , "loop-interchange", &LoopInterchangeLegacyPass::ID, PassInfo ::NormalCtor_t(callDefaultCtor<LoopInterchangeLegacyPass> ), false, false); Registry.registerPass(*PI, true); return PI ; } static llvm::once_flag InitializeLoopInterchangeLegacyPassPassFlag ; void llvm::initializeLoopInterchangeLegacyPassPass(PassRegistry &Registry) { llvm::call_once(InitializeLoopInterchangeLegacyPassPassFlag , initializeLoopInterchangeLegacyPassPassOnce, std::ref(Registry )); } | |||
| 1808 | "Interchanges loops for cache reuse", false, false)PassInfo *PI = new PassInfo( "Interchanges loops for cache reuse" , "loop-interchange", &LoopInterchangeLegacyPass::ID, PassInfo ::NormalCtor_t(callDefaultCtor<LoopInterchangeLegacyPass> ), false, false); Registry.registerPass(*PI, true); return PI ; } static llvm::once_flag InitializeLoopInterchangeLegacyPassPassFlag ; void llvm::initializeLoopInterchangeLegacyPassPass(PassRegistry &Registry) { llvm::call_once(InitializeLoopInterchangeLegacyPassPassFlag , initializeLoopInterchangeLegacyPassPassOnce, std::ref(Registry )); } | |||
| 1809 | ||||
| 1810 | Pass *llvm::createLoopInterchangePass() { | |||
| 1811 | return new LoopInterchangeLegacyPass(); | |||
| 1812 | } | |||
| 1813 | ||||
| 1814 | PreservedAnalyses LoopInterchangePass::run(LoopNest &LN, | |||
| 1815 | LoopAnalysisManager &AM, | |||
| 1816 | LoopStandardAnalysisResults &AR, | |||
| 1817 | LPMUpdater &U) { | |||
| 1818 | Function &F = *LN.getParent(); | |||
| 1819 | ||||
| 1820 | DependenceInfo DI(&F, &AR.AA, &AR.SE, &AR.LI); | |||
| 1821 | OptimizationRemarkEmitter ORE(&F); | |||
| 1822 | if (!LoopInterchange(&AR.SE, &AR.LI, &DI, &AR.DT, &ORE).run(LN)) | |||
| 1823 | return PreservedAnalyses::all(); | |||
| 1824 | return getLoopPassPreservedAnalyses(); | |||
| 1825 | } |