| File: | src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Transforms/Utils/LoopUnrollAndJam.cpp |
| Warning: | line 308, column 37 Called C++ object pointer is null |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
| 1 | //===-- LoopUnrollAndJam.cpp - Loop unrolling utilities -------------------===// | |||
| 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 file implements loop unroll and jam as a routine, much like | |||
| 10 | // LoopUnroll.cpp implements loop unroll. | |||
| 11 | // | |||
| 12 | //===----------------------------------------------------------------------===// | |||
| 13 | ||||
| 14 | #include "llvm/ADT/ArrayRef.h" | |||
| 15 | #include "llvm/ADT/DenseMap.h" | |||
| 16 | #include "llvm/ADT/Optional.h" | |||
| 17 | #include "llvm/ADT/STLExtras.h" | |||
| 18 | #include "llvm/ADT/Sequence.h" | |||
| 19 | #include "llvm/ADT/SmallPtrSet.h" | |||
| 20 | #include "llvm/ADT/SmallVector.h" | |||
| 21 | #include "llvm/ADT/Statistic.h" | |||
| 22 | #include "llvm/ADT/StringRef.h" | |||
| 23 | #include "llvm/ADT/Twine.h" | |||
| 24 | #include "llvm/ADT/iterator_range.h" | |||
| 25 | #include "llvm/Analysis/AssumptionCache.h" | |||
| 26 | #include "llvm/Analysis/DependenceAnalysis.h" | |||
| 27 | #include "llvm/Analysis/DomTreeUpdater.h" | |||
| 28 | #include "llvm/Analysis/LoopInfo.h" | |||
| 29 | #include "llvm/Analysis/LoopIterator.h" | |||
| 30 | #include "llvm/Analysis/MustExecute.h" | |||
| 31 | #include "llvm/Analysis/OptimizationRemarkEmitter.h" | |||
| 32 | #include "llvm/Analysis/ScalarEvolution.h" | |||
| 33 | #include "llvm/IR/BasicBlock.h" | |||
| 34 | #include "llvm/IR/DebugInfoMetadata.h" | |||
| 35 | #include "llvm/IR/DebugLoc.h" | |||
| 36 | #include "llvm/IR/DiagnosticInfo.h" | |||
| 37 | #include "llvm/IR/Dominators.h" | |||
| 38 | #include "llvm/IR/Function.h" | |||
| 39 | #include "llvm/IR/Instruction.h" | |||
| 40 | #include "llvm/IR/Instructions.h" | |||
| 41 | #include "llvm/IR/IntrinsicInst.h" | |||
| 42 | #include "llvm/IR/Use.h" | |||
| 43 | #include "llvm/IR/User.h" | |||
| 44 | #include "llvm/IR/Value.h" | |||
| 45 | #include "llvm/IR/ValueHandle.h" | |||
| 46 | #include "llvm/IR/ValueMap.h" | |||
| 47 | #include "llvm/Support/Casting.h" | |||
| 48 | #include "llvm/Support/Debug.h" | |||
| 49 | #include "llvm/Support/ErrorHandling.h" | |||
| 50 | #include "llvm/Support/GenericDomTree.h" | |||
| 51 | #include "llvm/Support/raw_ostream.h" | |||
| 52 | #include "llvm/Transforms/Utils/BasicBlockUtils.h" | |||
| 53 | #include "llvm/Transforms/Utils/Cloning.h" | |||
| 54 | #include "llvm/Transforms/Utils/LoopUtils.h" | |||
| 55 | #include "llvm/Transforms/Utils/UnrollLoop.h" | |||
| 56 | #include "llvm/Transforms/Utils/ValueMapper.h" | |||
| 57 | #include <assert.h> | |||
| 58 | #include <memory> | |||
| 59 | #include <type_traits> | |||
| 60 | #include <vector> | |||
| 61 | ||||
| 62 | using namespace llvm; | |||
| 63 | ||||
| 64 | #define DEBUG_TYPE"loop-unroll-and-jam" "loop-unroll-and-jam" | |||
| 65 | ||||
| 66 | STATISTIC(NumUnrolledAndJammed, "Number of loops unroll and jammed")static llvm::Statistic NumUnrolledAndJammed = {"loop-unroll-and-jam" , "NumUnrolledAndJammed", "Number of loops unroll and jammed" }; | |||
| 67 | STATISTIC(NumCompletelyUnrolledAndJammed, "Number of loops unroll and jammed")static llvm::Statistic NumCompletelyUnrolledAndJammed = {"loop-unroll-and-jam" , "NumCompletelyUnrolledAndJammed", "Number of loops unroll and jammed" }; | |||
| 68 | ||||
| 69 | typedef SmallPtrSet<BasicBlock *, 4> BasicBlockSet; | |||
| 70 | ||||
| 71 | // Partition blocks in an outer/inner loop pair into blocks before and after | |||
| 72 | // the loop | |||
| 73 | static bool partitionLoopBlocks(Loop &L, BasicBlockSet &ForeBlocks, | |||
| 74 | BasicBlockSet &AftBlocks, DominatorTree &DT) { | |||
| 75 | Loop *SubLoop = L.getSubLoops()[0]; | |||
| 76 | BasicBlock *SubLoopLatch = SubLoop->getLoopLatch(); | |||
| 77 | ||||
| 78 | for (BasicBlock *BB : L.blocks()) { | |||
| 79 | if (!SubLoop->contains(BB)) { | |||
| 80 | if (DT.dominates(SubLoopLatch, BB)) | |||
| 81 | AftBlocks.insert(BB); | |||
| 82 | else | |||
| 83 | ForeBlocks.insert(BB); | |||
| 84 | } | |||
| 85 | } | |||
| 86 | ||||
| 87 | // Check that all blocks in ForeBlocks together dominate the subloop | |||
| 88 | // TODO: This might ideally be done better with a dominator/postdominators. | |||
| 89 | BasicBlock *SubLoopPreHeader = SubLoop->getLoopPreheader(); | |||
| 90 | for (BasicBlock *BB : ForeBlocks) { | |||
| 91 | if (BB == SubLoopPreHeader) | |||
| 92 | continue; | |||
| 93 | Instruction *TI = BB->getTerminator(); | |||
| 94 | for (BasicBlock *Succ : successors(TI)) | |||
| 95 | if (!ForeBlocks.count(Succ)) | |||
| 96 | return false; | |||
| 97 | } | |||
| 98 | ||||
| 99 | return true; | |||
| 100 | } | |||
| 101 | ||||
| 102 | /// Partition blocks in a loop nest into blocks before and after each inner | |||
| 103 | /// loop. | |||
| 104 | static bool partitionOuterLoopBlocks( | |||
| 105 | Loop &Root, Loop &JamLoop, BasicBlockSet &JamLoopBlocks, | |||
| 106 | DenseMap<Loop *, BasicBlockSet> &ForeBlocksMap, | |||
| 107 | DenseMap<Loop *, BasicBlockSet> &AftBlocksMap, DominatorTree &DT) { | |||
| 108 | JamLoopBlocks.insert(JamLoop.block_begin(), JamLoop.block_end()); | |||
| 109 | ||||
| 110 | for (Loop *L : Root.getLoopsInPreorder()) { | |||
| 111 | if (L == &JamLoop) | |||
| 112 | break; | |||
| 113 | ||||
| 114 | if (!partitionLoopBlocks(*L, ForeBlocksMap[L], AftBlocksMap[L], DT)) | |||
| 115 | return false; | |||
| 116 | } | |||
| 117 | ||||
| 118 | return true; | |||
| 119 | } | |||
| 120 | ||||
| 121 | // TODO Remove when UnrollAndJamLoop changed to support unroll and jamming more | |||
| 122 | // than 2 levels loop. | |||
| 123 | static bool partitionOuterLoopBlocks(Loop *L, Loop *SubLoop, | |||
| 124 | BasicBlockSet &ForeBlocks, | |||
| 125 | BasicBlockSet &SubLoopBlocks, | |||
| 126 | BasicBlockSet &AftBlocks, | |||
| 127 | DominatorTree *DT) { | |||
| 128 | SubLoopBlocks.insert(SubLoop->block_begin(), SubLoop->block_end()); | |||
| 129 | return partitionLoopBlocks(*L, ForeBlocks, AftBlocks, *DT); | |||
| 130 | } | |||
| 131 | ||||
| 132 | // Looks at the phi nodes in Header for values coming from Latch. For these | |||
| 133 | // instructions and all their operands calls Visit on them, keeping going for | |||
| 134 | // all the operands in AftBlocks. Returns false if Visit returns false, | |||
| 135 | // otherwise returns true. This is used to process the instructions in the | |||
| 136 | // Aft blocks that need to be moved before the subloop. It is used in two | |||
| 137 | // places. One to check that the required set of instructions can be moved | |||
| 138 | // before the loop. Then to collect the instructions to actually move in | |||
| 139 | // moveHeaderPhiOperandsToForeBlocks. | |||
| 140 | template <typename T> | |||
| 141 | static bool processHeaderPhiOperands(BasicBlock *Header, BasicBlock *Latch, | |||
| 142 | BasicBlockSet &AftBlocks, T Visit) { | |||
| 143 | SmallVector<Instruction *, 8> Worklist; | |||
| 144 | SmallPtrSet<Instruction *, 8> VisitedInstr; | |||
| 145 | for (auto &Phi : Header->phis()) { | |||
| 146 | Value *V = Phi.getIncomingValueForBlock(Latch); | |||
| 147 | if (Instruction *I = dyn_cast<Instruction>(V)) | |||
| 148 | Worklist.push_back(I); | |||
| 149 | } | |||
| 150 | ||||
| 151 | while (!Worklist.empty()) { | |||
| 152 | Instruction *I = Worklist.pop_back_val(); | |||
| 153 | if (!Visit(I)) | |||
| 154 | return false; | |||
| 155 | VisitedInstr.insert(I); | |||
| 156 | ||||
| 157 | if (AftBlocks.count(I->getParent())) | |||
| 158 | for (auto &U : I->operands()) | |||
| 159 | if (Instruction *II = dyn_cast<Instruction>(U)) | |||
| 160 | if (!VisitedInstr.count(II)) | |||
| 161 | Worklist.push_back(II); | |||
| 162 | } | |||
| 163 | ||||
| 164 | return true; | |||
| 165 | } | |||
| 166 | ||||
| 167 | // Move the phi operands of Header from Latch out of AftBlocks to InsertLoc. | |||
| 168 | static void moveHeaderPhiOperandsToForeBlocks(BasicBlock *Header, | |||
| 169 | BasicBlock *Latch, | |||
| 170 | Instruction *InsertLoc, | |||
| 171 | BasicBlockSet &AftBlocks) { | |||
| 172 | // We need to ensure we move the instructions in the correct order, | |||
| 173 | // starting with the earliest required instruction and moving forward. | |||
| 174 | std::vector<Instruction *> Visited; | |||
| 175 | processHeaderPhiOperands(Header, Latch, AftBlocks, | |||
| 176 | [&Visited, &AftBlocks](Instruction *I) { | |||
| 177 | if (AftBlocks.count(I->getParent())) | |||
| 178 | Visited.push_back(I); | |||
| 179 | return true; | |||
| 180 | }); | |||
| 181 | ||||
| 182 | // Move all instructions in program order to before the InsertLoc | |||
| 183 | BasicBlock *InsertLocBB = InsertLoc->getParent(); | |||
| 184 | for (Instruction *I : reverse(Visited)) { | |||
| 185 | if (I->getParent() != InsertLocBB) | |||
| 186 | I->moveBefore(InsertLoc); | |||
| 187 | } | |||
| 188 | } | |||
| 189 | ||||
| 190 | /* | |||
| 191 | This method performs Unroll and Jam. For a simple loop like: | |||
| 192 | for (i = ..) | |||
| 193 | Fore(i) | |||
| 194 | for (j = ..) | |||
| 195 | SubLoop(i, j) | |||
| 196 | Aft(i) | |||
| 197 | ||||
| 198 | Instead of doing normal inner or outer unrolling, we do: | |||
| 199 | for (i = .., i+=2) | |||
| 200 | Fore(i) | |||
| 201 | Fore(i+1) | |||
| 202 | for (j = ..) | |||
| 203 | SubLoop(i, j) | |||
| 204 | SubLoop(i+1, j) | |||
| 205 | Aft(i) | |||
| 206 | Aft(i+1) | |||
| 207 | ||||
| 208 | So the outer loop is essetially unrolled and then the inner loops are fused | |||
| 209 | ("jammed") together into a single loop. This can increase speed when there | |||
| 210 | are loads in SubLoop that are invariant to i, as they become shared between | |||
| 211 | the now jammed inner loops. | |||
| 212 | ||||
| 213 | We do this by spliting the blocks in the loop into Fore, Subloop and Aft. | |||
| 214 | Fore blocks are those before the inner loop, Aft are those after. Normal | |||
| 215 | Unroll code is used to copy each of these sets of blocks and the results are | |||
| 216 | combined together into the final form above. | |||
| 217 | ||||
| 218 | isSafeToUnrollAndJam should be used prior to calling this to make sure the | |||
| 219 | unrolling will be valid. Checking profitablility is also advisable. | |||
| 220 | ||||
| 221 | If EpilogueLoop is non-null, it receives the epilogue loop (if it was | |||
| 222 | necessary to create one and not fully unrolled). | |||
| 223 | */ | |||
| 224 | LoopUnrollResult | |||
| 225 | llvm::UnrollAndJamLoop(Loop *L, unsigned Count, unsigned TripCount, | |||
| 226 | unsigned TripMultiple, bool UnrollRemainder, | |||
| 227 | LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, | |||
| 228 | AssumptionCache *AC, const TargetTransformInfo *TTI, | |||
| 229 | OptimizationRemarkEmitter *ORE, Loop **EpilogueLoop) { | |||
| 230 | ||||
| 231 | // When we enter here we should have already checked that it is safe | |||
| 232 | BasicBlock *Header = L->getHeader(); | |||
| 233 | assert(Header && "No header.")((void)0); | |||
| 234 | assert(L->getSubLoops().size() == 1)((void)0); | |||
| 235 | Loop *SubLoop = *L->begin(); | |||
| 236 | ||||
| 237 | // Don't enter the unroll code if there is nothing to do. | |||
| 238 | if (TripCount == 0 && Count < 2) { | |||
| ||||
| 239 | LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; almost nothing to do\n")do { } while (false); | |||
| 240 | return LoopUnrollResult::Unmodified; | |||
| 241 | } | |||
| 242 | ||||
| 243 | assert(Count > 0)((void)0); | |||
| 244 | assert(TripMultiple > 0)((void)0); | |||
| 245 | assert(TripCount == 0 || TripCount % TripMultiple == 0)((void)0); | |||
| 246 | ||||
| 247 | // Are we eliminating the loop control altogether? | |||
| 248 | bool CompletelyUnroll = (Count == TripCount); | |||
| 249 | ||||
| 250 | // We use the runtime remainder in cases where we don't know trip multiple | |||
| 251 | if (TripMultiple % Count != 0) { | |||
| 252 | if (!UnrollRuntimeLoopRemainder(L, Count, /*AllowExpensiveTripCount*/ false, | |||
| 253 | /*UseEpilogRemainder*/ true, | |||
| 254 | UnrollRemainder, /*ForgetAllSCEV*/ false, | |||
| 255 | LI, SE, DT, AC, TTI, true, EpilogueLoop)) { | |||
| 256 | LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; remainder loop could not be "do { } while (false) | |||
| 257 | "generated when assuming runtime trip count\n")do { } while (false); | |||
| 258 | return LoopUnrollResult::Unmodified; | |||
| 259 | } | |||
| 260 | } | |||
| 261 | ||||
| 262 | // Notify ScalarEvolution that the loop will be substantially changed, | |||
| 263 | // if not outright eliminated. | |||
| 264 | if (SE) { | |||
| 265 | SE->forgetLoop(L); | |||
| 266 | SE->forgetLoop(SubLoop); | |||
| 267 | } | |||
| 268 | ||||
| 269 | using namespace ore; | |||
| 270 | // Report the unrolling decision. | |||
| 271 | if (CompletelyUnroll
| |||
| 272 | LLVM_DEBUG(dbgs() << "COMPLETELY UNROLL AND JAMMING loop %"do { } while (false) | |||
| 273 | << Header->getName() << " with trip count " << TripCountdo { } while (false) | |||
| 274 | << "!\n")do { } while (false); | |||
| 275 | ORE->emit(OptimizationRemark(DEBUG_TYPE"loop-unroll-and-jam", "FullyUnrolled", L->getStartLoc(), | |||
| 276 | L->getHeader()) | |||
| 277 | << "completely unroll and jammed loop with " | |||
| 278 | << NV("UnrollCount", TripCount) << " iterations"); | |||
| 279 | } else { | |||
| 280 | auto DiagBuilder = [&]() { | |||
| 281 | OptimizationRemark Diag(DEBUG_TYPE"loop-unroll-and-jam", "PartialUnrolled", L->getStartLoc(), | |||
| 282 | L->getHeader()); | |||
| 283 | return Diag << "unroll and jammed loop by a factor of " | |||
| 284 | << NV("UnrollCount", Count); | |||
| 285 | }; | |||
| 286 | ||||
| 287 | LLVM_DEBUG(dbgs() << "UNROLL AND JAMMING loop %" << Header->getName()do { } while (false) | |||
| 288 | << " by " << Count)do { } while (false); | |||
| 289 | if (TripMultiple != 1) { | |||
| 290 | LLVM_DEBUG(dbgs() << " with " << TripMultiple << " trips per branch")do { } while (false); | |||
| 291 | ORE->emit([&]() { | |||
| 292 | return DiagBuilder() << " with " << NV("TripMultiple", TripMultiple) | |||
| 293 | << " trips per branch"; | |||
| 294 | }); | |||
| 295 | } else { | |||
| 296 | LLVM_DEBUG(dbgs() << " with run-time trip count")do { } while (false); | |||
| 297 | ORE->emit([&]() { return DiagBuilder() << " with run-time trip count"; }); | |||
| 298 | } | |||
| 299 | LLVM_DEBUG(dbgs() << "!\n")do { } while (false); | |||
| 300 | } | |||
| 301 | ||||
| 302 | BasicBlock *Preheader = L->getLoopPreheader(); | |||
| 303 | BasicBlock *LatchBlock = L->getLoopLatch(); | |||
| 304 | assert(Preheader && "No preheader")((void)0); | |||
| 305 | assert(LatchBlock && "No latch block")((void)0); | |||
| 306 | BranchInst *BI = dyn_cast<BranchInst>(LatchBlock->getTerminator()); | |||
| 307 | assert(BI && !BI->isUnconditional())((void)0); | |||
| 308 | bool ContinueOnTrue = L->contains(BI->getSuccessor(0)); | |||
| ||||
| 309 | BasicBlock *LoopExit = BI->getSuccessor(ContinueOnTrue); | |||
| 310 | bool SubLoopContinueOnTrue = SubLoop->contains( | |||
| 311 | SubLoop->getLoopLatch()->getTerminator()->getSuccessor(0)); | |||
| 312 | ||||
| 313 | // Partition blocks in an outer/inner loop pair into blocks before and after | |||
| 314 | // the loop | |||
| 315 | BasicBlockSet SubLoopBlocks; | |||
| 316 | BasicBlockSet ForeBlocks; | |||
| 317 | BasicBlockSet AftBlocks; | |||
| 318 | partitionOuterLoopBlocks(L, SubLoop, ForeBlocks, SubLoopBlocks, AftBlocks, | |||
| 319 | DT); | |||
| 320 | ||||
| 321 | // We keep track of the entering/first and exiting/last block of each of | |||
| 322 | // Fore/SubLoop/Aft in each iteration. This helps make the stapling up of | |||
| 323 | // blocks easier. | |||
| 324 | std::vector<BasicBlock *> ForeBlocksFirst; | |||
| 325 | std::vector<BasicBlock *> ForeBlocksLast; | |||
| 326 | std::vector<BasicBlock *> SubLoopBlocksFirst; | |||
| 327 | std::vector<BasicBlock *> SubLoopBlocksLast; | |||
| 328 | std::vector<BasicBlock *> AftBlocksFirst; | |||
| 329 | std::vector<BasicBlock *> AftBlocksLast; | |||
| 330 | ForeBlocksFirst.push_back(Header); | |||
| 331 | ForeBlocksLast.push_back(SubLoop->getLoopPreheader()); | |||
| 332 | SubLoopBlocksFirst.push_back(SubLoop->getHeader()); | |||
| 333 | SubLoopBlocksLast.push_back(SubLoop->getExitingBlock()); | |||
| 334 | AftBlocksFirst.push_back(SubLoop->getExitBlock()); | |||
| 335 | AftBlocksLast.push_back(L->getExitingBlock()); | |||
| 336 | // Maps Blocks[0] -> Blocks[It] | |||
| 337 | ValueToValueMapTy LastValueMap; | |||
| 338 | ||||
| 339 | // Move any instructions from fore phi operands from AftBlocks into Fore. | |||
| 340 | moveHeaderPhiOperandsToForeBlocks( | |||
| 341 | Header, LatchBlock, ForeBlocksLast[0]->getTerminator(), AftBlocks); | |||
| 342 | ||||
| 343 | // The current on-the-fly SSA update requires blocks to be processed in | |||
| 344 | // reverse postorder so that LastValueMap contains the correct value at each | |||
| 345 | // exit. | |||
| 346 | LoopBlocksDFS DFS(L); | |||
| 347 | DFS.perform(LI); | |||
| 348 | // Stash the DFS iterators before adding blocks to the loop. | |||
| 349 | LoopBlocksDFS::RPOIterator BlockBegin = DFS.beginRPO(); | |||
| 350 | LoopBlocksDFS::RPOIterator BlockEnd = DFS.endRPO(); | |||
| 351 | ||||
| 352 | // When a FSDiscriminator is enabled, we don't need to add the multiply | |||
| 353 | // factors to the discriminators. | |||
| 354 | if (Header->getParent()->isDebugInfoForProfiling() && !EnableFSDiscriminator) | |||
| 355 | for (BasicBlock *BB : L->getBlocks()) | |||
| 356 | for (Instruction &I : *BB) | |||
| 357 | if (!isa<DbgInfoIntrinsic>(&I)) | |||
| 358 | if (const DILocation *DIL = I.getDebugLoc()) { | |||
| 359 | auto NewDIL = DIL->cloneByMultiplyingDuplicationFactor(Count); | |||
| 360 | if (NewDIL) | |||
| 361 | I.setDebugLoc(NewDIL.getValue()); | |||
| 362 | else | |||
| 363 | LLVM_DEBUG(dbgs()do { } while (false) | |||
| 364 | << "Failed to create new discriminator: "do { } while (false) | |||
| 365 | << DIL->getFilename() << " Line: " << DIL->getLine())do { } while (false); | |||
| 366 | } | |||
| 367 | ||||
| 368 | // Copy all blocks | |||
| 369 | for (unsigned It = 1; It != Count; ++It) { | |||
| 370 | SmallVector<BasicBlock *, 8> NewBlocks; | |||
| 371 | // Maps Blocks[It] -> Blocks[It-1] | |||
| 372 | DenseMap<Value *, Value *> PrevItValueMap; | |||
| 373 | SmallDenseMap<const Loop *, Loop *, 4> NewLoops; | |||
| 374 | NewLoops[L] = L; | |||
| 375 | NewLoops[SubLoop] = SubLoop; | |||
| 376 | ||||
| 377 | for (LoopBlocksDFS::RPOIterator BB = BlockBegin; BB != BlockEnd; ++BB) { | |||
| 378 | ValueToValueMapTy VMap; | |||
| 379 | BasicBlock *New = CloneBasicBlock(*BB, VMap, "." + Twine(It)); | |||
| 380 | Header->getParent()->getBasicBlockList().push_back(New); | |||
| 381 | ||||
| 382 | // Tell LI about New. | |||
| 383 | addClonedBlockToLoopInfo(*BB, New, LI, NewLoops); | |||
| 384 | ||||
| 385 | if (ForeBlocks.count(*BB)) { | |||
| 386 | if (*BB == ForeBlocksFirst[0]) | |||
| 387 | ForeBlocksFirst.push_back(New); | |||
| 388 | if (*BB == ForeBlocksLast[0]) | |||
| 389 | ForeBlocksLast.push_back(New); | |||
| 390 | } else if (SubLoopBlocks.count(*BB)) { | |||
| 391 | if (*BB == SubLoopBlocksFirst[0]) | |||
| 392 | SubLoopBlocksFirst.push_back(New); | |||
| 393 | if (*BB == SubLoopBlocksLast[0]) | |||
| 394 | SubLoopBlocksLast.push_back(New); | |||
| 395 | } else if (AftBlocks.count(*BB)) { | |||
| 396 | if (*BB == AftBlocksFirst[0]) | |||
| 397 | AftBlocksFirst.push_back(New); | |||
| 398 | if (*BB == AftBlocksLast[0]) | |||
| 399 | AftBlocksLast.push_back(New); | |||
| 400 | } else { | |||
| 401 | llvm_unreachable("BB being cloned should be in Fore/Sub/Aft")__builtin_unreachable(); | |||
| 402 | } | |||
| 403 | ||||
| 404 | // Update our running maps of newest clones | |||
| 405 | PrevItValueMap[New] = (It == 1 ? *BB : LastValueMap[*BB]); | |||
| 406 | LastValueMap[*BB] = New; | |||
| 407 | for (ValueToValueMapTy::iterator VI = VMap.begin(), VE = VMap.end(); | |||
| 408 | VI != VE; ++VI) { | |||
| 409 | PrevItValueMap[VI->second] = | |||
| 410 | const_cast<Value *>(It == 1 ? VI->first : LastValueMap[VI->first]); | |||
| 411 | LastValueMap[VI->first] = VI->second; | |||
| 412 | } | |||
| 413 | ||||
| 414 | NewBlocks.push_back(New); | |||
| 415 | ||||
| 416 | // Update DomTree: | |||
| 417 | if (*BB == ForeBlocksFirst[0]) | |||
| 418 | DT->addNewBlock(New, ForeBlocksLast[It - 1]); | |||
| 419 | else if (*BB == SubLoopBlocksFirst[0]) | |||
| 420 | DT->addNewBlock(New, SubLoopBlocksLast[It - 1]); | |||
| 421 | else if (*BB == AftBlocksFirst[0]) | |||
| 422 | DT->addNewBlock(New, AftBlocksLast[It - 1]); | |||
| 423 | else { | |||
| 424 | // Each set of blocks (Fore/Sub/Aft) will have the same internal domtree | |||
| 425 | // structure. | |||
| 426 | auto BBDomNode = DT->getNode(*BB); | |||
| 427 | auto BBIDom = BBDomNode->getIDom(); | |||
| 428 | BasicBlock *OriginalBBIDom = BBIDom->getBlock(); | |||
| 429 | assert(OriginalBBIDom)((void)0); | |||
| 430 | assert(LastValueMap[cast<Value>(OriginalBBIDom)])((void)0); | |||
| 431 | DT->addNewBlock( | |||
| 432 | New, cast<BasicBlock>(LastValueMap[cast<Value>(OriginalBBIDom)])); | |||
| 433 | } | |||
| 434 | } | |||
| 435 | ||||
| 436 | // Remap all instructions in the most recent iteration | |||
| 437 | remapInstructionsInBlocks(NewBlocks, LastValueMap); | |||
| 438 | for (BasicBlock *NewBlock : NewBlocks) { | |||
| 439 | for (Instruction &I : *NewBlock) { | |||
| 440 | if (auto *II = dyn_cast<AssumeInst>(&I)) | |||
| 441 | AC->registerAssumption(II); | |||
| 442 | } | |||
| 443 | } | |||
| 444 | ||||
| 445 | // Alter the ForeBlocks phi's, pointing them at the latest version of the | |||
| 446 | // value from the previous iteration's phis | |||
| 447 | for (PHINode &Phi : ForeBlocksFirst[It]->phis()) { | |||
| 448 | Value *OldValue = Phi.getIncomingValueForBlock(AftBlocksLast[It]); | |||
| 449 | assert(OldValue && "should have incoming edge from Aft[It]")((void)0); | |||
| 450 | Value *NewValue = OldValue; | |||
| 451 | if (Value *PrevValue = PrevItValueMap[OldValue]) | |||
| 452 | NewValue = PrevValue; | |||
| 453 | ||||
| 454 | assert(Phi.getNumOperands() == 2)((void)0); | |||
| 455 | Phi.setIncomingBlock(0, ForeBlocksLast[It - 1]); | |||
| 456 | Phi.setIncomingValue(0, NewValue); | |||
| 457 | Phi.removeIncomingValue(1); | |||
| 458 | } | |||
| 459 | } | |||
| 460 | ||||
| 461 | // Now that all the basic blocks for the unrolled iterations are in place, | |||
| 462 | // finish up connecting the blocks and phi nodes. At this point LastValueMap | |||
| 463 | // is the last unrolled iterations values. | |||
| 464 | ||||
| 465 | // Update Phis in BB from OldBB to point to NewBB and use the latest value | |||
| 466 | // from LastValueMap | |||
| 467 | auto updatePHIBlocksAndValues = [](BasicBlock *BB, BasicBlock *OldBB, | |||
| 468 | BasicBlock *NewBB, | |||
| 469 | ValueToValueMapTy &LastValueMap) { | |||
| 470 | for (PHINode &Phi : BB->phis()) { | |||
| 471 | for (unsigned b = 0; b < Phi.getNumIncomingValues(); ++b) { | |||
| 472 | if (Phi.getIncomingBlock(b) == OldBB) { | |||
| 473 | Value *OldValue = Phi.getIncomingValue(b); | |||
| 474 | if (Value *LastValue = LastValueMap[OldValue]) | |||
| 475 | Phi.setIncomingValue(b, LastValue); | |||
| 476 | Phi.setIncomingBlock(b, NewBB); | |||
| 477 | break; | |||
| 478 | } | |||
| 479 | } | |||
| 480 | } | |||
| 481 | }; | |||
| 482 | // Move all the phis from Src into Dest | |||
| 483 | auto movePHIs = [](BasicBlock *Src, BasicBlock *Dest) { | |||
| 484 | Instruction *insertPoint = Dest->getFirstNonPHI(); | |||
| 485 | while (PHINode *Phi = dyn_cast<PHINode>(Src->begin())) | |||
| 486 | Phi->moveBefore(insertPoint); | |||
| 487 | }; | |||
| 488 | ||||
| 489 | // Update the PHI values outside the loop to point to the last block | |||
| 490 | updatePHIBlocksAndValues(LoopExit, AftBlocksLast[0], AftBlocksLast.back(), | |||
| 491 | LastValueMap); | |||
| 492 | ||||
| 493 | // Update ForeBlocks successors and phi nodes | |||
| 494 | BranchInst *ForeTerm = | |||
| 495 | cast<BranchInst>(ForeBlocksLast.back()->getTerminator()); | |||
| 496 | assert(ForeTerm->getNumSuccessors() == 1 && "Expecting one successor")((void)0); | |||
| 497 | ForeTerm->setSuccessor(0, SubLoopBlocksFirst[0]); | |||
| 498 | ||||
| 499 | if (CompletelyUnroll) { | |||
| 500 | while (PHINode *Phi = dyn_cast<PHINode>(ForeBlocksFirst[0]->begin())) { | |||
| 501 | Phi->replaceAllUsesWith(Phi->getIncomingValueForBlock(Preheader)); | |||
| 502 | Phi->getParent()->getInstList().erase(Phi); | |||
| 503 | } | |||
| 504 | } else { | |||
| 505 | // Update the PHI values to point to the last aft block | |||
| 506 | updatePHIBlocksAndValues(ForeBlocksFirst[0], AftBlocksLast[0], | |||
| 507 | AftBlocksLast.back(), LastValueMap); | |||
| 508 | } | |||
| 509 | ||||
| 510 | for (unsigned It = 1; It != Count; It++) { | |||
| 511 | // Remap ForeBlock successors from previous iteration to this | |||
| 512 | BranchInst *ForeTerm = | |||
| 513 | cast<BranchInst>(ForeBlocksLast[It - 1]->getTerminator()); | |||
| 514 | assert(ForeTerm->getNumSuccessors() == 1 && "Expecting one successor")((void)0); | |||
| 515 | ForeTerm->setSuccessor(0, ForeBlocksFirst[It]); | |||
| 516 | } | |||
| 517 | ||||
| 518 | // Subloop successors and phis | |||
| 519 | BranchInst *SubTerm = | |||
| 520 | cast<BranchInst>(SubLoopBlocksLast.back()->getTerminator()); | |||
| 521 | SubTerm->setSuccessor(!SubLoopContinueOnTrue, SubLoopBlocksFirst[0]); | |||
| 522 | SubTerm->setSuccessor(SubLoopContinueOnTrue, AftBlocksFirst[0]); | |||
| 523 | SubLoopBlocksFirst[0]->replacePhiUsesWith(ForeBlocksLast[0], | |||
| 524 | ForeBlocksLast.back()); | |||
| 525 | SubLoopBlocksFirst[0]->replacePhiUsesWith(SubLoopBlocksLast[0], | |||
| 526 | SubLoopBlocksLast.back()); | |||
| 527 | ||||
| 528 | for (unsigned It = 1; It != Count; It++) { | |||
| 529 | // Replace the conditional branch of the previous iteration subloop with an | |||
| 530 | // unconditional one to this one | |||
| 531 | BranchInst *SubTerm = | |||
| 532 | cast<BranchInst>(SubLoopBlocksLast[It - 1]->getTerminator()); | |||
| 533 | BranchInst::Create(SubLoopBlocksFirst[It], SubTerm); | |||
| 534 | SubTerm->eraseFromParent(); | |||
| 535 | ||||
| 536 | SubLoopBlocksFirst[It]->replacePhiUsesWith(ForeBlocksLast[It], | |||
| 537 | ForeBlocksLast.back()); | |||
| 538 | SubLoopBlocksFirst[It]->replacePhiUsesWith(SubLoopBlocksLast[It], | |||
| 539 | SubLoopBlocksLast.back()); | |||
| 540 | movePHIs(SubLoopBlocksFirst[It], SubLoopBlocksFirst[0]); | |||
| 541 | } | |||
| 542 | ||||
| 543 | // Aft blocks successors and phis | |||
| 544 | BranchInst *AftTerm = cast<BranchInst>(AftBlocksLast.back()->getTerminator()); | |||
| 545 | if (CompletelyUnroll) { | |||
| 546 | BranchInst::Create(LoopExit, AftTerm); | |||
| 547 | AftTerm->eraseFromParent(); | |||
| 548 | } else { | |||
| 549 | AftTerm->setSuccessor(!ContinueOnTrue, ForeBlocksFirst[0]); | |||
| 550 | assert(AftTerm->getSuccessor(ContinueOnTrue) == LoopExit &&((void)0) | |||
| 551 | "Expecting the ContinueOnTrue successor of AftTerm to be LoopExit")((void)0); | |||
| 552 | } | |||
| 553 | AftBlocksFirst[0]->replacePhiUsesWith(SubLoopBlocksLast[0], | |||
| 554 | SubLoopBlocksLast.back()); | |||
| 555 | ||||
| 556 | for (unsigned It = 1; It != Count; It++) { | |||
| 557 | // Replace the conditional branch of the previous iteration subloop with an | |||
| 558 | // unconditional one to this one | |||
| 559 | BranchInst *AftTerm = | |||
| 560 | cast<BranchInst>(AftBlocksLast[It - 1]->getTerminator()); | |||
| 561 | BranchInst::Create(AftBlocksFirst[It], AftTerm); | |||
| 562 | AftTerm->eraseFromParent(); | |||
| 563 | ||||
| 564 | AftBlocksFirst[It]->replacePhiUsesWith(SubLoopBlocksLast[It], | |||
| 565 | SubLoopBlocksLast.back()); | |||
| 566 | movePHIs(AftBlocksFirst[It], AftBlocksFirst[0]); | |||
| 567 | } | |||
| 568 | ||||
| 569 | DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy); | |||
| 570 | // Dominator Tree. Remove the old links between Fore, Sub and Aft, adding the | |||
| 571 | // new ones required. | |||
| 572 | if (Count != 1) { | |||
| 573 | SmallVector<DominatorTree::UpdateType, 4> DTUpdates; | |||
| 574 | DTUpdates.emplace_back(DominatorTree::UpdateKind::Delete, ForeBlocksLast[0], | |||
| 575 | SubLoopBlocksFirst[0]); | |||
| 576 | DTUpdates.emplace_back(DominatorTree::UpdateKind::Delete, | |||
| 577 | SubLoopBlocksLast[0], AftBlocksFirst[0]); | |||
| 578 | ||||
| 579 | DTUpdates.emplace_back(DominatorTree::UpdateKind::Insert, | |||
| 580 | ForeBlocksLast.back(), SubLoopBlocksFirst[0]); | |||
| 581 | DTUpdates.emplace_back(DominatorTree::UpdateKind::Insert, | |||
| 582 | SubLoopBlocksLast.back(), AftBlocksFirst[0]); | |||
| 583 | DTU.applyUpdatesPermissive(DTUpdates); | |||
| 584 | } | |||
| 585 | ||||
| 586 | // Merge adjacent basic blocks, if possible. | |||
| 587 | SmallPtrSet<BasicBlock *, 16> MergeBlocks; | |||
| 588 | MergeBlocks.insert(ForeBlocksLast.begin(), ForeBlocksLast.end()); | |||
| 589 | MergeBlocks.insert(SubLoopBlocksLast.begin(), SubLoopBlocksLast.end()); | |||
| 590 | MergeBlocks.insert(AftBlocksLast.begin(), AftBlocksLast.end()); | |||
| 591 | ||||
| 592 | MergeBlockSuccessorsIntoGivenBlocks(MergeBlocks, L, &DTU, LI); | |||
| 593 | ||||
| 594 | // Apply updates to the DomTree. | |||
| 595 | DT = &DTU.getDomTree(); | |||
| 596 | ||||
| 597 | // At this point, the code is well formed. We now do a quick sweep over the | |||
| 598 | // inserted code, doing constant propagation and dead code elimination as we | |||
| 599 | // go. | |||
| 600 | simplifyLoopAfterUnroll(SubLoop, true, LI, SE, DT, AC, TTI); | |||
| 601 | simplifyLoopAfterUnroll(L, !CompletelyUnroll && Count > 1, LI, SE, DT, AC, | |||
| 602 | TTI); | |||
| 603 | ||||
| 604 | NumCompletelyUnrolledAndJammed += CompletelyUnroll; | |||
| 605 | ++NumUnrolledAndJammed; | |||
| 606 | ||||
| 607 | // Update LoopInfo if the loop is completely removed. | |||
| 608 | if (CompletelyUnroll) | |||
| 609 | LI->erase(L); | |||
| 610 | ||||
| 611 | #ifndef NDEBUG1 | |||
| 612 | // We shouldn't have done anything to break loop simplify form or LCSSA. | |||
| 613 | Loop *OutestLoop = SubLoop->getParentLoop() | |||
| 614 | ? SubLoop->getParentLoop()->getParentLoop() | |||
| 615 | ? SubLoop->getParentLoop()->getParentLoop() | |||
| 616 | : SubLoop->getParentLoop() | |||
| 617 | : SubLoop; | |||
| 618 | assert(DT->verify())((void)0); | |||
| 619 | LI->verify(*DT); | |||
| 620 | assert(OutestLoop->isRecursivelyLCSSAForm(*DT, *LI))((void)0); | |||
| 621 | if (!CompletelyUnroll) | |||
| 622 | assert(L->isLoopSimplifyForm())((void)0); | |||
| 623 | assert(SubLoop->isLoopSimplifyForm())((void)0); | |||
| 624 | SE->verify(); | |||
| 625 | #endif | |||
| 626 | ||||
| 627 | return CompletelyUnroll ? LoopUnrollResult::FullyUnrolled | |||
| 628 | : LoopUnrollResult::PartiallyUnrolled; | |||
| 629 | } | |||
| 630 | ||||
| 631 | static bool getLoadsAndStores(BasicBlockSet &Blocks, | |||
| 632 | SmallVector<Instruction *, 4> &MemInstr) { | |||
| 633 | // Scan the BBs and collect legal loads and stores. | |||
| 634 | // Returns false if non-simple loads/stores are found. | |||
| 635 | for (BasicBlock *BB : Blocks) { | |||
| 636 | for (Instruction &I : *BB) { | |||
| 637 | if (auto *Ld = dyn_cast<LoadInst>(&I)) { | |||
| 638 | if (!Ld->isSimple()) | |||
| 639 | return false; | |||
| 640 | MemInstr.push_back(&I); | |||
| 641 | } else if (auto *St = dyn_cast<StoreInst>(&I)) { | |||
| 642 | if (!St->isSimple()) | |||
| 643 | return false; | |||
| 644 | MemInstr.push_back(&I); | |||
| 645 | } else if (I.mayReadOrWriteMemory()) { | |||
| 646 | return false; | |||
| 647 | } | |||
| 648 | } | |||
| 649 | } | |||
| 650 | return true; | |||
| 651 | } | |||
| 652 | ||||
| 653 | static bool preservesForwardDependence(Instruction *Src, Instruction *Dst, | |||
| 654 | unsigned UnrollLevel, unsigned JamLevel, | |||
| 655 | bool Sequentialized, Dependence *D) { | |||
| 656 | // UnrollLevel might carry the dependency Src --> Dst | |||
| 657 | // Does a different loop after unrolling? | |||
| 658 | for (unsigned CurLoopDepth = UnrollLevel + 1; CurLoopDepth <= JamLevel; | |||
| 659 | ++CurLoopDepth) { | |||
| 660 | auto JammedDir = D->getDirection(CurLoopDepth); | |||
| 661 | if (JammedDir == Dependence::DVEntry::LT) | |||
| 662 | return true; | |||
| 663 | ||||
| 664 | if (JammedDir & Dependence::DVEntry::GT) | |||
| 665 | return false; | |||
| 666 | } | |||
| 667 | ||||
| 668 | return true; | |||
| 669 | } | |||
| 670 | ||||
| 671 | static bool preservesBackwardDependence(Instruction *Src, Instruction *Dst, | |||
| 672 | unsigned UnrollLevel, unsigned JamLevel, | |||
| 673 | bool Sequentialized, Dependence *D) { | |||
| 674 | // UnrollLevel might carry the dependency Dst --> Src | |||
| 675 | for (unsigned CurLoopDepth = UnrollLevel + 1; CurLoopDepth <= JamLevel; | |||
| 676 | ++CurLoopDepth) { | |||
| 677 | auto JammedDir = D->getDirection(CurLoopDepth); | |||
| 678 | if (JammedDir == Dependence::DVEntry::GT) | |||
| 679 | return true; | |||
| 680 | ||||
| 681 | if (JammedDir & Dependence::DVEntry::LT) | |||
| 682 | return false; | |||
| 683 | } | |||
| 684 | ||||
| 685 | // Backward dependencies are only preserved if not interleaved. | |||
| 686 | return Sequentialized; | |||
| 687 | } | |||
| 688 | ||||
| 689 | // Check whether it is semantically safe Src and Dst considering any potential | |||
| 690 | // dependency between them. | |||
| 691 | // | |||
| 692 | // @param UnrollLevel The level of the loop being unrolled | |||
| 693 | // @param JamLevel The level of the loop being jammed; if Src and Dst are on | |||
| 694 | // different levels, the outermost common loop counts as jammed level | |||
| 695 | // | |||
| 696 | // @return true if is safe and false if there is a dependency violation. | |||
| 697 | static bool checkDependency(Instruction *Src, Instruction *Dst, | |||
| 698 | unsigned UnrollLevel, unsigned JamLevel, | |||
| 699 | bool Sequentialized, DependenceInfo &DI) { | |||
| 700 | assert(UnrollLevel <= JamLevel &&((void)0) | |||
| 701 | "Expecting JamLevel to be at least UnrollLevel")((void)0); | |||
| 702 | ||||
| 703 | if (Src == Dst) | |||
| 704 | return true; | |||
| 705 | // Ignore Input dependencies. | |||
| 706 | if (isa<LoadInst>(Src) && isa<LoadInst>(Dst)) | |||
| 707 | return true; | |||
| 708 | ||||
| 709 | // Check whether unroll-and-jam may violate a dependency. | |||
| 710 | // By construction, every dependency will be lexicographically non-negative | |||
| 711 | // (if it was, it would violate the current execution order), such as | |||
| 712 | // (0,0,>,*,*) | |||
| 713 | // Unroll-and-jam changes the GT execution of two executions to the same | |||
| 714 | // iteration of the chosen unroll level. That is, a GT dependence becomes a GE | |||
| 715 | // dependence (or EQ, if we fully unrolled the loop) at the loop's position: | |||
| 716 | // (0,0,>=,*,*) | |||
| 717 | // Now, the dependency is not necessarily non-negative anymore, i.e. | |||
| 718 | // unroll-and-jam may violate correctness. | |||
| 719 | std::unique_ptr<Dependence> D = DI.depends(Src, Dst, true); | |||
| 720 | if (!D) | |||
| 721 | return true; | |||
| 722 | assert(D->isOrdered() && "Expected an output, flow or anti dep.")((void)0); | |||
| 723 | ||||
| 724 | if (D->isConfused()) { | |||
| 725 | LLVM_DEBUG(dbgs() << " Confused dependency between:\n"do { } while (false) | |||
| 726 | << " " << *Src << "\n"do { } while (false) | |||
| 727 | << " " << *Dst << "\n")do { } while (false); | |||
| 728 | return false; | |||
| 729 | } | |||
| 730 | ||||
| 731 | // If outer levels (levels enclosing the loop being unroll-and-jammed) have a | |||
| 732 | // non-equal direction, then the locations accessed in the inner levels cannot | |||
| 733 | // overlap in memory. We assumes the indexes never overlap into neighboring | |||
| 734 | // dimensions. | |||
| 735 | for (unsigned CurLoopDepth = 1; CurLoopDepth < UnrollLevel; ++CurLoopDepth) | |||
| 736 | if (!(D->getDirection(CurLoopDepth) & Dependence::DVEntry::EQ)) | |||
| 737 | return true; | |||
| 738 | ||||
| 739 | auto UnrollDirection = D->getDirection(UnrollLevel); | |||
| 740 | ||||
| 741 | // If the distance carried by the unrolled loop is 0, then after unrolling | |||
| 742 | // that distance will become non-zero resulting in non-overlapping accesses in | |||
| 743 | // the inner loops. | |||
| 744 | if (UnrollDirection == Dependence::DVEntry::EQ) | |||
| 745 | return true; | |||
| 746 | ||||
| 747 | if (UnrollDirection & Dependence::DVEntry::LT && | |||
| 748 | !preservesForwardDependence(Src, Dst, UnrollLevel, JamLevel, | |||
| 749 | Sequentialized, D.get())) | |||
| 750 | return false; | |||
| 751 | ||||
| 752 | if (UnrollDirection & Dependence::DVEntry::GT && | |||
| 753 | !preservesBackwardDependence(Src, Dst, UnrollLevel, JamLevel, | |||
| 754 | Sequentialized, D.get())) | |||
| 755 | return false; | |||
| 756 | ||||
| 757 | return true; | |||
| 758 | } | |||
| 759 | ||||
| 760 | static bool | |||
| 761 | checkDependencies(Loop &Root, const BasicBlockSet &SubLoopBlocks, | |||
| 762 | const DenseMap<Loop *, BasicBlockSet> &ForeBlocksMap, | |||
| 763 | const DenseMap<Loop *, BasicBlockSet> &AftBlocksMap, | |||
| 764 | DependenceInfo &DI, LoopInfo &LI) { | |||
| 765 | SmallVector<BasicBlockSet, 8> AllBlocks; | |||
| 766 | for (Loop *L : Root.getLoopsInPreorder()) | |||
| 767 | if (ForeBlocksMap.find(L) != ForeBlocksMap.end()) | |||
| 768 | AllBlocks.push_back(ForeBlocksMap.lookup(L)); | |||
| 769 | AllBlocks.push_back(SubLoopBlocks); | |||
| 770 | for (Loop *L : Root.getLoopsInPreorder()) | |||
| 771 | if (AftBlocksMap.find(L) != AftBlocksMap.end()) | |||
| 772 | AllBlocks.push_back(AftBlocksMap.lookup(L)); | |||
| 773 | ||||
| 774 | unsigned LoopDepth = Root.getLoopDepth(); | |||
| 775 | SmallVector<Instruction *, 4> EarlierLoadsAndStores; | |||
| 776 | SmallVector<Instruction *, 4> CurrentLoadsAndStores; | |||
| 777 | for (BasicBlockSet &Blocks : AllBlocks) { | |||
| 778 | CurrentLoadsAndStores.clear(); | |||
| 779 | if (!getLoadsAndStores(Blocks, CurrentLoadsAndStores)) | |||
| 780 | return false; | |||
| 781 | ||||
| 782 | Loop *CurLoop = LI.getLoopFor((*Blocks.begin())->front().getParent()); | |||
| 783 | unsigned CurLoopDepth = CurLoop->getLoopDepth(); | |||
| 784 | ||||
| 785 | for (auto *Earlier : EarlierLoadsAndStores) { | |||
| 786 | Loop *EarlierLoop = LI.getLoopFor(Earlier->getParent()); | |||
| 787 | unsigned EarlierDepth = EarlierLoop->getLoopDepth(); | |||
| 788 | unsigned CommonLoopDepth = std::min(EarlierDepth, CurLoopDepth); | |||
| 789 | for (auto *Later : CurrentLoadsAndStores) { | |||
| 790 | if (!checkDependency(Earlier, Later, LoopDepth, CommonLoopDepth, false, | |||
| 791 | DI)) | |||
| 792 | return false; | |||
| 793 | } | |||
| 794 | } | |||
| 795 | ||||
| 796 | size_t NumInsts = CurrentLoadsAndStores.size(); | |||
| 797 | for (size_t I = 0; I < NumInsts; ++I) { | |||
| 798 | for (size_t J = I; J < NumInsts; ++J) { | |||
| 799 | if (!checkDependency(CurrentLoadsAndStores[I], CurrentLoadsAndStores[J], | |||
| 800 | LoopDepth, CurLoopDepth, true, DI)) | |||
| 801 | return false; | |||
| 802 | } | |||
| 803 | } | |||
| 804 | ||||
| 805 | EarlierLoadsAndStores.append(CurrentLoadsAndStores.begin(), | |||
| 806 | CurrentLoadsAndStores.end()); | |||
| 807 | } | |||
| 808 | return true; | |||
| 809 | } | |||
| 810 | ||||
| 811 | static bool isEligibleLoopForm(const Loop &Root) { | |||
| 812 | // Root must have a child. | |||
| 813 | if (Root.getSubLoops().size() != 1) | |||
| 814 | return false; | |||
| 815 | ||||
| 816 | const Loop *L = &Root; | |||
| 817 | do { | |||
| 818 | // All loops in Root need to be in simplify and rotated form. | |||
| 819 | if (!L->isLoopSimplifyForm()) | |||
| 820 | return false; | |||
| 821 | ||||
| 822 | if (!L->isRotatedForm()) | |||
| 823 | return false; | |||
| 824 | ||||
| 825 | if (L->getHeader()->hasAddressTaken()) { | |||
| 826 | LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; Address taken\n")do { } while (false); | |||
| 827 | return false; | |||
| 828 | } | |||
| 829 | ||||
| 830 | unsigned SubLoopsSize = L->getSubLoops().size(); | |||
| 831 | if (SubLoopsSize == 0) | |||
| 832 | return true; | |||
| 833 | ||||
| 834 | // Only one child is allowed. | |||
| 835 | if (SubLoopsSize != 1) | |||
| 836 | return false; | |||
| 837 | ||||
| 838 | // Only loops with a single exit block can be unrolled and jammed. | |||
| 839 | // The function getExitBlock() is used for this check, rather than | |||
| 840 | // getUniqueExitBlock() to ensure loops with mulitple exit edges are | |||
| 841 | // disallowed. | |||
| 842 | if (!L->getExitBlock()) { | |||
| 843 | LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; only loops with single exit "do { } while (false) | |||
| 844 | "blocks can be unrolled and jammed.\n")do { } while (false); | |||
| 845 | return false; | |||
| 846 | } | |||
| 847 | ||||
| 848 | // Only loops with a single exiting block can be unrolled and jammed. | |||
| 849 | if (!L->getExitingBlock()) { | |||
| 850 | LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; only loops with single "do { } while (false) | |||
| 851 | "exiting blocks can be unrolled and jammed.\n")do { } while (false); | |||
| 852 | return false; | |||
| 853 | } | |||
| 854 | ||||
| 855 | L = L->getSubLoops()[0]; | |||
| 856 | } while (L); | |||
| 857 | ||||
| 858 | return true; | |||
| 859 | } | |||
| 860 | ||||
| 861 | static Loop *getInnerMostLoop(Loop *L) { | |||
| 862 | while (!L->getSubLoops().empty()) | |||
| 863 | L = L->getSubLoops()[0]; | |||
| 864 | return L; | |||
| 865 | } | |||
| 866 | ||||
| 867 | bool llvm::isSafeToUnrollAndJam(Loop *L, ScalarEvolution &SE, DominatorTree &DT, | |||
| 868 | DependenceInfo &DI, LoopInfo &LI) { | |||
| 869 | if (!isEligibleLoopForm(*L)) { | |||
| 870 | LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; Ineligible loop form\n")do { } while (false); | |||
| 871 | return false; | |||
| 872 | } | |||
| 873 | ||||
| 874 | /* We currently handle outer loops like this: | |||
| 875 | | | |||
| 876 | ForeFirst <------\ } | |||
| 877 | Blocks | } ForeBlocks of L | |||
| 878 | ForeLast | } | |||
| 879 | | | | |||
| 880 | ... | | |||
| 881 | | | | |||
| 882 | ForeFirst <----\ | } | |||
| 883 | Blocks | | } ForeBlocks of a inner loop of L | |||
| 884 | ForeLast | | } | |||
| 885 | | | | | |||
| 886 | JamLoopFirst <\ | | } | |||
| 887 | Blocks | | | } JamLoopBlocks of the innermost loop | |||
| 888 | JamLoopLast -/ | | } | |||
| 889 | | | | | |||
| 890 | AftFirst | | } | |||
| 891 | Blocks | | } AftBlocks of a inner loop of L | |||
| 892 | AftLast ------/ | } | |||
| 893 | | | | |||
| 894 | ... | | |||
| 895 | | | | |||
| 896 | AftFirst | } | |||
| 897 | Blocks | } AftBlocks of L | |||
| 898 | AftLast --------/ } | |||
| 899 | | | |||
| 900 | ||||
| 901 | There are (theoretically) any number of blocks in ForeBlocks, SubLoopBlocks | |||
| 902 | and AftBlocks, providing that there is one edge from Fores to SubLoops, | |||
| 903 | one edge from SubLoops to Afts and a single outer loop exit (from Afts). | |||
| 904 | In practice we currently limit Aft blocks to a single block, and limit | |||
| 905 | things further in the profitablility checks of the unroll and jam pass. | |||
| 906 | ||||
| 907 | Because of the way we rearrange basic blocks, we also require that | |||
| 908 | the Fore blocks of L on all unrolled iterations are safe to move before the | |||
| 909 | blocks of the direct child of L of all iterations. So we require that the | |||
| 910 | phi node looping operands of ForeHeader can be moved to at least the end of | |||
| 911 | ForeEnd, so that we can arrange cloned Fore Blocks before the subloop and | |||
| 912 | match up Phi's correctly. | |||
| 913 | ||||
| 914 | i.e. The old order of blocks used to be | |||
| 915 | (F1)1 (F2)1 J1_1 J1_2 (A2)1 (A1)1 (F1)2 (F2)2 J2_1 J2_2 (A2)2 (A1)2. | |||
| 916 | It needs to be safe to transform this to | |||
| 917 | (F1)1 (F1)2 (F2)1 (F2)2 J1_1 J1_2 J2_1 J2_2 (A2)1 (A2)2 (A1)1 (A1)2. | |||
| 918 | ||||
| 919 | There are then a number of checks along the lines of no calls, no | |||
| 920 | exceptions, inner loop IV is consistent, etc. Note that for loops requiring | |||
| 921 | runtime unrolling, UnrollRuntimeLoopRemainder can also fail in | |||
| 922 | UnrollAndJamLoop if the trip count cannot be easily calculated. | |||
| 923 | */ | |||
| 924 | ||||
| 925 | // Split blocks into Fore/SubLoop/Aft based on dominators | |||
| 926 | Loop *JamLoop = getInnerMostLoop(L); | |||
| 927 | BasicBlockSet SubLoopBlocks; | |||
| 928 | DenseMap<Loop *, BasicBlockSet> ForeBlocksMap; | |||
| 929 | DenseMap<Loop *, BasicBlockSet> AftBlocksMap; | |||
| 930 | if (!partitionOuterLoopBlocks(*L, *JamLoop, SubLoopBlocks, ForeBlocksMap, | |||
| 931 | AftBlocksMap, DT)) { | |||
| 932 | LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; Incompatible loop layout\n")do { } while (false); | |||
| 933 | return false; | |||
| 934 | } | |||
| 935 | ||||
| 936 | // Aft blocks may need to move instructions to fore blocks, which becomes more | |||
| 937 | // difficult if there are multiple (potentially conditionally executed) | |||
| 938 | // blocks. For now we just exclude loops with multiple aft blocks. | |||
| 939 | if (AftBlocksMap[L].size() != 1) { | |||
| 940 | LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; Can't currently handle "do { } while (false) | |||
| 941 | "multiple blocks after the loop\n")do { } while (false); | |||
| 942 | return false; | |||
| 943 | } | |||
| 944 | ||||
| 945 | // Check inner loop backedge count is consistent on all iterations of the | |||
| 946 | // outer loop | |||
| 947 | if (any_of(L->getLoopsInPreorder(), [&SE](Loop *SubLoop) { | |||
| 948 | return !hasIterationCountInvariantInParent(SubLoop, SE); | |||
| 949 | })) { | |||
| 950 | LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; Inner loop iteration count is "do { } while (false) | |||
| 951 | "not consistent on each iteration\n")do { } while (false); | |||
| 952 | return false; | |||
| 953 | } | |||
| 954 | ||||
| 955 | // Check the loop safety info for exceptions. | |||
| 956 | SimpleLoopSafetyInfo LSI; | |||
| 957 | LSI.computeLoopSafetyInfo(L); | |||
| 958 | if (LSI.anyBlockMayThrow()) { | |||
| 959 | LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; Something may throw\n")do { } while (false); | |||
| 960 | return false; | |||
| 961 | } | |||
| 962 | ||||
| 963 | // We've ruled out the easy stuff and now need to check that there are no | |||
| 964 | // interdependencies which may prevent us from moving the: | |||
| 965 | // ForeBlocks before Subloop and AftBlocks. | |||
| 966 | // Subloop before AftBlocks. | |||
| 967 | // ForeBlock phi operands before the subloop | |||
| 968 | ||||
| 969 | // Make sure we can move all instructions we need to before the subloop | |||
| 970 | BasicBlock *Header = L->getHeader(); | |||
| 971 | BasicBlock *Latch = L->getLoopLatch(); | |||
| 972 | BasicBlockSet AftBlocks = AftBlocksMap[L]; | |||
| 973 | Loop *SubLoop = L->getSubLoops()[0]; | |||
| 974 | if (!processHeaderPhiOperands( | |||
| 975 | Header, Latch, AftBlocks, [&AftBlocks, &SubLoop](Instruction *I) { | |||
| 976 | if (SubLoop->contains(I->getParent())) | |||
| 977 | return false; | |||
| 978 | if (AftBlocks.count(I->getParent())) { | |||
| 979 | // If we hit a phi node in afts we know we are done (probably | |||
| 980 | // LCSSA) | |||
| 981 | if (isa<PHINode>(I)) | |||
| 982 | return false; | |||
| 983 | // Can't move instructions with side effects or memory | |||
| 984 | // reads/writes | |||
| 985 | if (I->mayHaveSideEffects() || I->mayReadOrWriteMemory()) | |||
| 986 | return false; | |||
| 987 | } | |||
| 988 | // Keep going | |||
| 989 | return true; | |||
| 990 | })) { | |||
| 991 | LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; can't move required "do { } while (false) | |||
| 992 | "instructions after subloop to before it\n")do { } while (false); | |||
| 993 | return false; | |||
| 994 | } | |||
| 995 | ||||
| 996 | // Check for memory dependencies which prohibit the unrolling we are doing. | |||
| 997 | // Because of the way we are unrolling Fore/Sub/Aft blocks, we need to check | |||
| 998 | // there are no dependencies between Fore-Sub, Fore-Aft, Sub-Aft and Sub-Sub. | |||
| 999 | if (!checkDependencies(*L, SubLoopBlocks, ForeBlocksMap, AftBlocksMap, DI, | |||
| 1000 | LI)) { | |||
| 1001 | LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; failed dependency check\n")do { } while (false); | |||
| 1002 | return false; | |||
| 1003 | } | |||
| 1004 | ||||
| 1005 | return true; | |||
| 1006 | } |