| File: | src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Transforms/Scalar/LoopDeletion.cpp |
| Warning: | line 75, column 23 Called C++ object pointer is null |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
| 1 | //===- LoopDeletion.cpp - Dead Loop Deletion 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 file implements the Dead Loop Deletion Pass. This pass is responsible | |||
| 10 | // for eliminating loops with non-infinite computable trip counts that have no | |||
| 11 | // side effects or volatile instructions, and do not contribute to the | |||
| 12 | // computation of the function's return value. | |||
| 13 | // | |||
| 14 | //===----------------------------------------------------------------------===// | |||
| 15 | ||||
| 16 | #include "llvm/Transforms/Scalar/LoopDeletion.h" | |||
| 17 | #include "llvm/ADT/SmallVector.h" | |||
| 18 | #include "llvm/ADT/Statistic.h" | |||
| 19 | #include "llvm/Analysis/CFG.h" | |||
| 20 | #include "llvm/Analysis/GlobalsModRef.h" | |||
| 21 | #include "llvm/Analysis/InstructionSimplify.h" | |||
| 22 | #include "llvm/Analysis/LoopIterator.h" | |||
| 23 | #include "llvm/Analysis/LoopPass.h" | |||
| 24 | #include "llvm/Analysis/MemorySSA.h" | |||
| 25 | #include "llvm/Analysis/OptimizationRemarkEmitter.h" | |||
| 26 | #include "llvm/IR/Dominators.h" | |||
| 27 | ||||
| 28 | #include "llvm/IR/PatternMatch.h" | |||
| 29 | #include "llvm/InitializePasses.h" | |||
| 30 | #include "llvm/Transforms/Scalar.h" | |||
| 31 | #include "llvm/Transforms/Scalar/LoopPassManager.h" | |||
| 32 | #include "llvm/Transforms/Utils/LoopUtils.h" | |||
| 33 | ||||
| 34 | using namespace llvm; | |||
| 35 | ||||
| 36 | #define DEBUG_TYPE"loop-delete" "loop-delete" | |||
| 37 | ||||
| 38 | STATISTIC(NumDeleted, "Number of loops deleted")static llvm::Statistic NumDeleted = {"loop-delete", "NumDeleted" , "Number of loops deleted"}; | |||
| 39 | ||||
| 40 | static cl::opt<bool> EnableSymbolicExecution( | |||
| 41 | "loop-deletion-enable-symbolic-execution", cl::Hidden, cl::init(true), | |||
| 42 | cl::desc("Break backedge through symbolic execution of 1st iteration " | |||
| 43 | "attempting to prove that the backedge is never taken")); | |||
| 44 | ||||
| 45 | enum class LoopDeletionResult { | |||
| 46 | Unmodified, | |||
| 47 | Modified, | |||
| 48 | Deleted, | |||
| 49 | }; | |||
| 50 | ||||
| 51 | static LoopDeletionResult merge(LoopDeletionResult A, LoopDeletionResult B) { | |||
| 52 | if (A == LoopDeletionResult::Deleted || B == LoopDeletionResult::Deleted) | |||
| 53 | return LoopDeletionResult::Deleted; | |||
| 54 | if (A == LoopDeletionResult::Modified || B == LoopDeletionResult::Modified) | |||
| 55 | return LoopDeletionResult::Modified; | |||
| 56 | return LoopDeletionResult::Unmodified; | |||
| 57 | } | |||
| 58 | ||||
| 59 | /// Determines if a loop is dead. | |||
| 60 | /// | |||
| 61 | /// This assumes that we've already checked for unique exit and exiting blocks, | |||
| 62 | /// and that the code is in LCSSA form. | |||
| 63 | static bool isLoopDead(Loop *L, ScalarEvolution &SE, | |||
| 64 | SmallVectorImpl<BasicBlock *> &ExitingBlocks, | |||
| 65 | BasicBlock *ExitBlock, bool &Changed, | |||
| 66 | BasicBlock *Preheader, LoopInfo &LI) { | |||
| 67 | // Make sure that all PHI entries coming from the loop are loop invariant. | |||
| 68 | // Because the code is in LCSSA form, any values used outside of the loop | |||
| 69 | // must pass through a PHI in the exit block, meaning that this check is | |||
| 70 | // sufficient to guarantee that no loop-variant values are used outside | |||
| 71 | // of the loop. | |||
| 72 | bool AllEntriesInvariant = true; | |||
| 73 | bool AllOutgoingValuesSame = true; | |||
| 74 | if (!L->hasNoExitBlocks()) { | |||
| 75 | for (PHINode &P : ExitBlock->phis()) { | |||
| ||||
| 76 | Value *incoming = P.getIncomingValueForBlock(ExitingBlocks[0]); | |||
| 77 | ||||
| 78 | // Make sure all exiting blocks produce the same incoming value for the | |||
| 79 | // block. If there are different incoming values for different exiting | |||
| 80 | // blocks, then it is impossible to statically determine which value | |||
| 81 | // should be used. | |||
| 82 | AllOutgoingValuesSame = | |||
| 83 | all_of(makeArrayRef(ExitingBlocks).slice(1), [&](BasicBlock *BB) { | |||
| 84 | return incoming == P.getIncomingValueForBlock(BB); | |||
| 85 | }); | |||
| 86 | ||||
| 87 | if (!AllOutgoingValuesSame) | |||
| 88 | break; | |||
| 89 | ||||
| 90 | if (Instruction *I = dyn_cast<Instruction>(incoming)) | |||
| 91 | if (!L->makeLoopInvariant(I, Changed, Preheader->getTerminator())) { | |||
| 92 | AllEntriesInvariant = false; | |||
| 93 | break; | |||
| 94 | } | |||
| 95 | } | |||
| 96 | } | |||
| 97 | ||||
| 98 | if (Changed) | |||
| 99 | SE.forgetLoopDispositions(L); | |||
| 100 | ||||
| 101 | if (!AllEntriesInvariant || !AllOutgoingValuesSame) | |||
| 102 | return false; | |||
| 103 | ||||
| 104 | // Make sure that no instructions in the block have potential side-effects. | |||
| 105 | // This includes instructions that could write to memory, and loads that are | |||
| 106 | // marked volatile. | |||
| 107 | for (auto &I : L->blocks()) | |||
| 108 | if (any_of(*I, [](Instruction &I) { | |||
| 109 | return I.mayHaveSideEffects() && !I.isDroppable(); | |||
| 110 | })) | |||
| 111 | return false; | |||
| 112 | ||||
| 113 | // The loop or any of its sub-loops looping infinitely is legal. The loop can | |||
| 114 | // only be considered dead if either | |||
| 115 | // a. the function is mustprogress. | |||
| 116 | // b. all (sub-)loops are mustprogress or have a known trip-count. | |||
| 117 | if (L->getHeader()->getParent()->mustProgress()) | |||
| 118 | return true; | |||
| 119 | ||||
| 120 | LoopBlocksRPO RPOT(L); | |||
| 121 | RPOT.perform(&LI); | |||
| 122 | // If the loop contains an irreducible cycle, it may loop infinitely. | |||
| 123 | if (containsIrreducibleCFG<const BasicBlock *>(RPOT, LI)) | |||
| 124 | return false; | |||
| 125 | ||||
| 126 | SmallVector<Loop *, 8> WorkList; | |||
| 127 | WorkList.push_back(L); | |||
| 128 | while (!WorkList.empty()) { | |||
| 129 | Loop *Current = WorkList.pop_back_val(); | |||
| 130 | if (hasMustProgress(Current)) | |||
| 131 | continue; | |||
| 132 | ||||
| 133 | const SCEV *S = SE.getConstantMaxBackedgeTakenCount(Current); | |||
| 134 | if (isa<SCEVCouldNotCompute>(S)) { | |||
| 135 | LLVM_DEBUG(do { } while (false) | |||
| 136 | dbgs() << "Could not compute SCEV MaxBackedgeTakenCount and was "do { } while (false) | |||
| 137 | "not required to make progress.\n")do { } while (false); | |||
| 138 | return false; | |||
| 139 | } | |||
| 140 | WorkList.append(Current->begin(), Current->end()); | |||
| 141 | } | |||
| 142 | return true; | |||
| 143 | } | |||
| 144 | ||||
| 145 | /// This function returns true if there is no viable path from the | |||
| 146 | /// entry block to the header of \p L. Right now, it only does | |||
| 147 | /// a local search to save compile time. | |||
| 148 | static bool isLoopNeverExecuted(Loop *L) { | |||
| 149 | using namespace PatternMatch; | |||
| 150 | ||||
| 151 | auto *Preheader = L->getLoopPreheader(); | |||
| 152 | // TODO: We can relax this constraint, since we just need a loop | |||
| 153 | // predecessor. | |||
| 154 | assert(Preheader && "Needs preheader!")((void)0); | |||
| 155 | ||||
| 156 | if (Preheader->isEntryBlock()) | |||
| 157 | return false; | |||
| 158 | // All predecessors of the preheader should have a constant conditional | |||
| 159 | // branch, with the loop's preheader as not-taken. | |||
| 160 | for (auto *Pred: predecessors(Preheader)) { | |||
| 161 | BasicBlock *Taken, *NotTaken; | |||
| 162 | ConstantInt *Cond; | |||
| 163 | if (!match(Pred->getTerminator(), | |||
| 164 | m_Br(m_ConstantInt(Cond), Taken, NotTaken))) | |||
| 165 | return false; | |||
| 166 | if (!Cond->getZExtValue()) | |||
| 167 | std::swap(Taken, NotTaken); | |||
| 168 | if (Taken == Preheader) | |||
| 169 | return false; | |||
| 170 | } | |||
| 171 | assert(!pred_empty(Preheader) &&((void)0) | |||
| 172 | "Preheader should have predecessors at this point!")((void)0); | |||
| 173 | // All the predecessors have the loop preheader as not-taken target. | |||
| 174 | return true; | |||
| 175 | } | |||
| 176 | ||||
| 177 | static Value * | |||
| 178 | getValueOnFirstIteration(Value *V, DenseMap<Value *, Value *> &FirstIterValue, | |||
| 179 | const SimplifyQuery &SQ) { | |||
| 180 | // Quick hack: do not flood cache with non-instruction values. | |||
| 181 | if (!isa<Instruction>(V)) | |||
| 182 | return V; | |||
| 183 | // Do we already know cached result? | |||
| 184 | auto Existing = FirstIterValue.find(V); | |||
| 185 | if (Existing != FirstIterValue.end()) | |||
| 186 | return Existing->second; | |||
| 187 | Value *FirstIterV = nullptr; | |||
| 188 | if (auto *BO = dyn_cast<BinaryOperator>(V)) { | |||
| 189 | Value *LHS = | |||
| 190 | getValueOnFirstIteration(BO->getOperand(0), FirstIterValue, SQ); | |||
| 191 | Value *RHS = | |||
| 192 | getValueOnFirstIteration(BO->getOperand(1), FirstIterValue, SQ); | |||
| 193 | FirstIterV = SimplifyBinOp(BO->getOpcode(), LHS, RHS, SQ); | |||
| 194 | } | |||
| 195 | if (!FirstIterV) | |||
| 196 | FirstIterV = V; | |||
| 197 | FirstIterValue[V] = FirstIterV; | |||
| 198 | return FirstIterV; | |||
| 199 | } | |||
| 200 | ||||
| 201 | // Try to prove that one of conditions that dominates the latch must exit on 1st | |||
| 202 | // iteration. | |||
| 203 | static bool canProveExitOnFirstIteration(Loop *L, DominatorTree &DT, | |||
| 204 | LoopInfo &LI) { | |||
| 205 | // Disabled by option. | |||
| 206 | if (!EnableSymbolicExecution) | |||
| 207 | return false; | |||
| 208 | ||||
| 209 | BasicBlock *Predecessor = L->getLoopPredecessor(); | |||
| 210 | BasicBlock *Latch = L->getLoopLatch(); | |||
| 211 | ||||
| 212 | if (!Predecessor || !Latch) | |||
| 213 | return false; | |||
| 214 | ||||
| 215 | LoopBlocksRPO RPOT(L); | |||
| 216 | RPOT.perform(&LI); | |||
| 217 | ||||
| 218 | // For the optimization to be correct, we need RPOT to have a property that | |||
| 219 | // each block is processed after all its predecessors, which may only be | |||
| 220 | // violated for headers of the current loop and all nested loops. Irreducible | |||
| 221 | // CFG provides multiple ways to break this assumption, so we do not want to | |||
| 222 | // deal with it. | |||
| 223 | if (containsIrreducibleCFG<const BasicBlock *>(RPOT, LI)) | |||
| 224 | return false; | |||
| 225 | ||||
| 226 | BasicBlock *Header = L->getHeader(); | |||
| 227 | // Blocks that are reachable on the 1st iteration. | |||
| 228 | SmallPtrSet<BasicBlock *, 4> LiveBlocks; | |||
| 229 | // Edges that are reachable on the 1st iteration. | |||
| 230 | DenseSet<BasicBlockEdge> LiveEdges; | |||
| 231 | LiveBlocks.insert(Header); | |||
| 232 | ||||
| 233 | SmallPtrSet<BasicBlock *, 4> Visited; | |||
| 234 | auto MarkLiveEdge = [&](BasicBlock *From, BasicBlock *To) { | |||
| 235 | assert(LiveBlocks.count(From) && "Must be live!")((void)0); | |||
| 236 | assert((LI.isLoopHeader(To) || !Visited.count(To)) &&((void)0) | |||
| 237 | "Only canonical backedges are allowed. Irreducible CFG?")((void)0); | |||
| 238 | assert((LiveBlocks.count(To) || !Visited.count(To)) &&((void)0) | |||
| 239 | "We already discarded this block as dead!")((void)0); | |||
| 240 | LiveBlocks.insert(To); | |||
| 241 | LiveEdges.insert({ From, To }); | |||
| 242 | }; | |||
| 243 | ||||
| 244 | auto MarkAllSuccessorsLive = [&](BasicBlock *BB) { | |||
| 245 | for (auto *Succ : successors(BB)) | |||
| 246 | MarkLiveEdge(BB, Succ); | |||
| 247 | }; | |||
| 248 | ||||
| 249 | // Check if there is only one value coming from all live predecessor blocks. | |||
| 250 | // Note that because we iterate in RPOT, we have already visited all its | |||
| 251 | // (non-latch) predecessors. | |||
| 252 | auto GetSoleInputOnFirstIteration = [&](PHINode & PN)->Value * { | |||
| 253 | BasicBlock *BB = PN.getParent(); | |||
| 254 | bool HasLivePreds = false; | |||
| 255 | (void)HasLivePreds; | |||
| 256 | if (BB == Header) | |||
| 257 | return PN.getIncomingValueForBlock(Predecessor); | |||
| 258 | Value *OnlyInput = nullptr; | |||
| 259 | for (auto *Pred : predecessors(BB)) | |||
| 260 | if (LiveEdges.count({ Pred, BB })) { | |||
| 261 | HasLivePreds = true; | |||
| 262 | Value *Incoming = PN.getIncomingValueForBlock(Pred); | |||
| 263 | // Skip undefs. If they are present, we can assume they are equal to | |||
| 264 | // the non-undef input. | |||
| 265 | if (isa<UndefValue>(Incoming)) | |||
| 266 | continue; | |||
| 267 | // Two inputs. | |||
| 268 | if (OnlyInput && OnlyInput != Incoming) | |||
| 269 | return nullptr; | |||
| 270 | OnlyInput = Incoming; | |||
| 271 | } | |||
| 272 | ||||
| 273 | assert(HasLivePreds && "No live predecessors?")((void)0); | |||
| 274 | // If all incoming live value were undefs, return undef. | |||
| 275 | return OnlyInput ? OnlyInput : UndefValue::get(PN.getType()); | |||
| 276 | }; | |||
| 277 | DenseMap<Value *, Value *> FirstIterValue; | |||
| 278 | ||||
| 279 | // Use the following algorithm to prove we never take the latch on the 1st | |||
| 280 | // iteration: | |||
| 281 | // 1. Traverse in topological order, so that whenever we visit a block, all | |||
| 282 | // its predecessors are already visited. | |||
| 283 | // 2. If we can prove that the block may have only 1 predecessor on the 1st | |||
| 284 | // iteration, map all its phis onto input from this predecessor. | |||
| 285 | // 3a. If we can prove which successor of out block is taken on the 1st | |||
| 286 | // iteration, mark this successor live. | |||
| 287 | // 3b. If we cannot prove it, conservatively assume that all successors are | |||
| 288 | // live. | |||
| 289 | auto &DL = Header->getModule()->getDataLayout(); | |||
| 290 | const SimplifyQuery SQ(DL); | |||
| 291 | for (auto *BB : RPOT) { | |||
| 292 | Visited.insert(BB); | |||
| 293 | ||||
| 294 | // This block is not reachable on the 1st iterations. | |||
| 295 | if (!LiveBlocks.count(BB)) | |||
| 296 | continue; | |||
| 297 | ||||
| 298 | // Skip inner loops. | |||
| 299 | if (LI.getLoopFor(BB) != L) { | |||
| 300 | MarkAllSuccessorsLive(BB); | |||
| 301 | continue; | |||
| 302 | } | |||
| 303 | ||||
| 304 | // If Phi has only one input from all live input blocks, use it. | |||
| 305 | for (auto &PN : BB->phis()) { | |||
| 306 | if (!PN.getType()->isIntegerTy()) | |||
| 307 | continue; | |||
| 308 | auto *Incoming = GetSoleInputOnFirstIteration(PN); | |||
| 309 | if (Incoming && DT.dominates(Incoming, BB->getTerminator())) { | |||
| 310 | Value *FirstIterV = | |||
| 311 | getValueOnFirstIteration(Incoming, FirstIterValue, SQ); | |||
| 312 | FirstIterValue[&PN] = FirstIterV; | |||
| 313 | } | |||
| 314 | } | |||
| 315 | ||||
| 316 | using namespace PatternMatch; | |||
| 317 | ICmpInst::Predicate Pred; | |||
| 318 | Value *LHS, *RHS; | |||
| 319 | BasicBlock *IfTrue, *IfFalse; | |||
| 320 | auto *Term = BB->getTerminator(); | |||
| 321 | if (match(Term, m_Br(m_ICmp(Pred, m_Value(LHS), m_Value(RHS)), | |||
| 322 | m_BasicBlock(IfTrue), m_BasicBlock(IfFalse)))) { | |||
| 323 | if (!LHS->getType()->isIntegerTy()) { | |||
| 324 | MarkAllSuccessorsLive(BB); | |||
| 325 | continue; | |||
| 326 | } | |||
| 327 | ||||
| 328 | // Can we prove constant true or false for this condition? | |||
| 329 | LHS = getValueOnFirstIteration(LHS, FirstIterValue, SQ); | |||
| 330 | RHS = getValueOnFirstIteration(RHS, FirstIterValue, SQ); | |||
| 331 | auto *KnownCondition = SimplifyICmpInst(Pred, LHS, RHS, SQ); | |||
| 332 | if (!KnownCondition) { | |||
| 333 | // Failed to simplify. | |||
| 334 | MarkAllSuccessorsLive(BB); | |||
| 335 | continue; | |||
| 336 | } | |||
| 337 | if (isa<UndefValue>(KnownCondition)) { | |||
| 338 | // TODO: According to langref, branching by undef is undefined behavior. | |||
| 339 | // It means that, theoretically, we should be able to just continue | |||
| 340 | // without marking any successors as live. However, we are not certain | |||
| 341 | // how correct our compiler is at handling such cases. So we are being | |||
| 342 | // very conservative here. | |||
| 343 | // | |||
| 344 | // If there is a non-loop successor, always assume this branch leaves the | |||
| 345 | // loop. Otherwise, arbitrarily take IfTrue. | |||
| 346 | // | |||
| 347 | // Once we are certain that branching by undef is handled correctly by | |||
| 348 | // other transforms, we should not mark any successors live here. | |||
| 349 | if (L->contains(IfTrue) && L->contains(IfFalse)) | |||
| 350 | MarkLiveEdge(BB, IfTrue); | |||
| 351 | continue; | |||
| 352 | } | |||
| 353 | auto *ConstCondition = dyn_cast<ConstantInt>(KnownCondition); | |||
| 354 | if (!ConstCondition) { | |||
| 355 | // Non-constant condition, cannot analyze any further. | |||
| 356 | MarkAllSuccessorsLive(BB); | |||
| 357 | continue; | |||
| 358 | } | |||
| 359 | if (ConstCondition->isAllOnesValue()) | |||
| 360 | MarkLiveEdge(BB, IfTrue); | |||
| 361 | else | |||
| 362 | MarkLiveEdge(BB, IfFalse); | |||
| 363 | } else if (SwitchInst *SI = dyn_cast<SwitchInst>(Term)) { | |||
| 364 | auto *SwitchValue = SI->getCondition(); | |||
| 365 | auto *SwitchValueOnFirstIter = | |||
| 366 | getValueOnFirstIteration(SwitchValue, FirstIterValue, SQ); | |||
| 367 | auto *ConstSwitchValue = dyn_cast<ConstantInt>(SwitchValueOnFirstIter); | |||
| 368 | if (!ConstSwitchValue) { | |||
| 369 | MarkAllSuccessorsLive(BB); | |||
| 370 | continue; | |||
| 371 | } | |||
| 372 | auto CaseIterator = SI->findCaseValue(ConstSwitchValue); | |||
| 373 | MarkLiveEdge(BB, CaseIterator->getCaseSuccessor()); | |||
| 374 | } else { | |||
| 375 | MarkAllSuccessorsLive(BB); | |||
| 376 | continue; | |||
| 377 | } | |||
| 378 | } | |||
| 379 | ||||
| 380 | // We can break the latch if it wasn't live. | |||
| 381 | return !LiveEdges.count({ Latch, Header }); | |||
| 382 | } | |||
| 383 | ||||
| 384 | /// If we can prove the backedge is untaken, remove it. This destroys the | |||
| 385 | /// loop, but leaves the (now trivially loop invariant) control flow and | |||
| 386 | /// side effects (if any) in place. | |||
| 387 | static LoopDeletionResult | |||
| 388 | breakBackedgeIfNotTaken(Loop *L, DominatorTree &DT, ScalarEvolution &SE, | |||
| 389 | LoopInfo &LI, MemorySSA *MSSA, | |||
| 390 | OptimizationRemarkEmitter &ORE) { | |||
| 391 | assert(L->isLCSSAForm(DT) && "Expected LCSSA!")((void)0); | |||
| 392 | ||||
| 393 | if (!L->getLoopLatch()) | |||
| 394 | return LoopDeletionResult::Unmodified; | |||
| 395 | ||||
| 396 | auto *BTC = SE.getBackedgeTakenCount(L); | |||
| 397 | if (!isa<SCEVCouldNotCompute>(BTC) && SE.isKnownNonZero(BTC)) | |||
| 398 | return LoopDeletionResult::Unmodified; | |||
| 399 | if (!BTC->isZero() && !canProveExitOnFirstIteration(L, DT, LI)) | |||
| 400 | return LoopDeletionResult::Unmodified; | |||
| 401 | ||||
| 402 | breakLoopBackedge(L, DT, SE, LI, MSSA); | |||
| 403 | return LoopDeletionResult::Deleted; | |||
| 404 | } | |||
| 405 | ||||
| 406 | /// Remove a loop if it is dead. | |||
| 407 | /// | |||
| 408 | /// A loop is considered dead either if it does not impact the observable | |||
| 409 | /// behavior of the program other than finite running time, or if it is | |||
| 410 | /// required to make progress by an attribute such as 'mustprogress' or | |||
| 411 | /// 'llvm.loop.mustprogress' and does not make any. This may remove | |||
| 412 | /// infinite loops that have been required to make progress. | |||
| 413 | /// | |||
| 414 | /// This entire process relies pretty heavily on LoopSimplify form and LCSSA in | |||
| 415 | /// order to make various safety checks work. | |||
| 416 | /// | |||
| 417 | /// \returns true if any changes were made. This may mutate the loop even if it | |||
| 418 | /// is unable to delete it due to hoisting trivially loop invariant | |||
| 419 | /// instructions out of the loop. | |||
| 420 | static LoopDeletionResult deleteLoopIfDead(Loop *L, DominatorTree &DT, | |||
| 421 | ScalarEvolution &SE, LoopInfo &LI, | |||
| 422 | MemorySSA *MSSA, | |||
| 423 | OptimizationRemarkEmitter &ORE) { | |||
| 424 | assert(L->isLCSSAForm(DT) && "Expected LCSSA!")((void)0); | |||
| 425 | ||||
| 426 | // We can only remove the loop if there is a preheader that we can branch from | |||
| 427 | // after removing it. Also, if LoopSimplify form is not available, stay out | |||
| 428 | // of trouble. | |||
| 429 | BasicBlock *Preheader = L->getLoopPreheader(); | |||
| 430 | if (!Preheader || !L->hasDedicatedExits()) { | |||
| 431 | LLVM_DEBUG(do { } while (false) | |||
| 432 | dbgs()do { } while (false) | |||
| 433 | << "Deletion requires Loop with preheader and dedicated exits.\n")do { } while (false); | |||
| 434 | return LoopDeletionResult::Unmodified; | |||
| 435 | } | |||
| 436 | ||||
| 437 | BasicBlock *ExitBlock = L->getUniqueExitBlock(); | |||
| 438 | ||||
| 439 | if (ExitBlock && isLoopNeverExecuted(L)) { | |||
| 440 | LLVM_DEBUG(dbgs() << "Loop is proven to never execute, delete it!")do { } while (false); | |||
| 441 | // We need to forget the loop before setting the incoming values of the exit | |||
| 442 | // phis to undef, so we properly invalidate the SCEV expressions for those | |||
| 443 | // phis. | |||
| 444 | SE.forgetLoop(L); | |||
| 445 | // Set incoming value to undef for phi nodes in the exit block. | |||
| 446 | for (PHINode &P : ExitBlock->phis()) { | |||
| 447 | std::fill(P.incoming_values().begin(), P.incoming_values().end(), | |||
| 448 | UndefValue::get(P.getType())); | |||
| 449 | } | |||
| 450 | ORE.emit([&]() { | |||
| 451 | return OptimizationRemark(DEBUG_TYPE"loop-delete", "NeverExecutes", L->getStartLoc(), | |||
| 452 | L->getHeader()) | |||
| 453 | << "Loop deleted because it never executes"; | |||
| 454 | }); | |||
| 455 | deleteDeadLoop(L, &DT, &SE, &LI, MSSA); | |||
| 456 | ++NumDeleted; | |||
| 457 | return LoopDeletionResult::Deleted; | |||
| 458 | } | |||
| 459 | ||||
| 460 | // The remaining checks below are for a loop being dead because all statements | |||
| 461 | // in the loop are invariant. | |||
| 462 | SmallVector<BasicBlock *, 4> ExitingBlocks; | |||
| 463 | L->getExitingBlocks(ExitingBlocks); | |||
| 464 | ||||
| 465 | // We require that the loop has at most one exit block. Otherwise, we'd be in | |||
| 466 | // the situation of needing to be able to solve statically which exit block | |||
| 467 | // will be branched to, or trying to preserve the branching logic in a loop | |||
| 468 | // invariant manner. | |||
| 469 | if (!ExitBlock
| |||
| 470 | LLVM_DEBUG(dbgs() << "Deletion requires at most one exit block.\n")do { } while (false); | |||
| 471 | return LoopDeletionResult::Unmodified; | |||
| 472 | } | |||
| 473 | // Finally, we have to check that the loop really is dead. | |||
| 474 | bool Changed = false; | |||
| 475 | if (!isLoopDead(L, SE, ExitingBlocks, ExitBlock, Changed, Preheader, LI)) { | |||
| 476 | LLVM_DEBUG(dbgs() << "Loop is not invariant, cannot delete.\n")do { } while (false); | |||
| 477 | return Changed ? LoopDeletionResult::Modified | |||
| 478 | : LoopDeletionResult::Unmodified; | |||
| 479 | } | |||
| 480 | ||||
| 481 | LLVM_DEBUG(dbgs() << "Loop is invariant, delete it!")do { } while (false); | |||
| 482 | ORE.emit([&]() { | |||
| 483 | return OptimizationRemark(DEBUG_TYPE"loop-delete", "Invariant", L->getStartLoc(), | |||
| 484 | L->getHeader()) | |||
| 485 | << "Loop deleted because it is invariant"; | |||
| 486 | }); | |||
| 487 | deleteDeadLoop(L, &DT, &SE, &LI, MSSA); | |||
| 488 | ++NumDeleted; | |||
| 489 | ||||
| 490 | return LoopDeletionResult::Deleted; | |||
| 491 | } | |||
| 492 | ||||
| 493 | PreservedAnalyses LoopDeletionPass::run(Loop &L, LoopAnalysisManager &AM, | |||
| 494 | LoopStandardAnalysisResults &AR, | |||
| 495 | LPMUpdater &Updater) { | |||
| 496 | ||||
| 497 | LLVM_DEBUG(dbgs() << "Analyzing Loop for deletion: ")do { } while (false); | |||
| ||||
| 498 | LLVM_DEBUG(L.dump())do { } while (false); | |||
| 499 | std::string LoopName = std::string(L.getName()); | |||
| 500 | // For the new PM, we can't use OptimizationRemarkEmitter as an analysis | |||
| 501 | // pass. Function analyses need to be preserved across loop transformations | |||
| 502 | // but ORE cannot be preserved (see comment before the pass definition). | |||
| 503 | OptimizationRemarkEmitter ORE(L.getHeader()->getParent()); | |||
| 504 | auto Result = deleteLoopIfDead(&L, AR.DT, AR.SE, AR.LI, AR.MSSA, ORE); | |||
| 505 | ||||
| 506 | // If we can prove the backedge isn't taken, just break it and be done. This | |||
| 507 | // leaves the loop structure in place which means it can handle dispatching | |||
| 508 | // to the right exit based on whatever loop invariant structure remains. | |||
| 509 | if (Result != LoopDeletionResult::Deleted) | |||
| 510 | Result = merge(Result, breakBackedgeIfNotTaken(&L, AR.DT, AR.SE, AR.LI, | |||
| 511 | AR.MSSA, ORE)); | |||
| 512 | ||||
| 513 | if (Result == LoopDeletionResult::Unmodified) | |||
| 514 | return PreservedAnalyses::all(); | |||
| 515 | ||||
| 516 | if (Result == LoopDeletionResult::Deleted) | |||
| 517 | Updater.markLoopAsDeleted(L, LoopName); | |||
| 518 | ||||
| 519 | auto PA = getLoopPassPreservedAnalyses(); | |||
| 520 | if (AR.MSSA) | |||
| 521 | PA.preserve<MemorySSAAnalysis>(); | |||
| 522 | return PA; | |||
| 523 | } | |||
| 524 | ||||
| 525 | namespace { | |||
| 526 | class LoopDeletionLegacyPass : public LoopPass { | |||
| 527 | public: | |||
| 528 | static char ID; // Pass ID, replacement for typeid | |||
| 529 | LoopDeletionLegacyPass() : LoopPass(ID) { | |||
| 530 | initializeLoopDeletionLegacyPassPass(*PassRegistry::getPassRegistry()); | |||
| 531 | } | |||
| 532 | ||||
| 533 | // Possibly eliminate loop L if it is dead. | |||
| 534 | bool runOnLoop(Loop *L, LPPassManager &) override; | |||
| 535 | ||||
| 536 | void getAnalysisUsage(AnalysisUsage &AU) const override { | |||
| 537 | AU.addPreserved<MemorySSAWrapperPass>(); | |||
| 538 | getLoopAnalysisUsage(AU); | |||
| 539 | } | |||
| 540 | }; | |||
| 541 | } | |||
| 542 | ||||
| 543 | char LoopDeletionLegacyPass::ID = 0; | |||
| 544 | INITIALIZE_PASS_BEGIN(LoopDeletionLegacyPass, "loop-deletion",static void *initializeLoopDeletionLegacyPassPassOnce(PassRegistry &Registry) { | |||
| 545 | "Delete dead loops", false, false)static void *initializeLoopDeletionLegacyPassPassOnce(PassRegistry &Registry) { | |||
| 546 | INITIALIZE_PASS_DEPENDENCY(LoopPass)initializeLoopPassPass(Registry); | |||
| 547 | INITIALIZE_PASS_END(LoopDeletionLegacyPass, "loop-deletion",PassInfo *PI = new PassInfo( "Delete dead loops", "loop-deletion" , &LoopDeletionLegacyPass::ID, PassInfo::NormalCtor_t(callDefaultCtor <LoopDeletionLegacyPass>), false, false); Registry.registerPass (*PI, true); return PI; } static llvm::once_flag InitializeLoopDeletionLegacyPassPassFlag ; void llvm::initializeLoopDeletionLegacyPassPass(PassRegistry &Registry) { llvm::call_once(InitializeLoopDeletionLegacyPassPassFlag , initializeLoopDeletionLegacyPassPassOnce, std::ref(Registry )); } | |||
| 548 | "Delete dead loops", false, false)PassInfo *PI = new PassInfo( "Delete dead loops", "loop-deletion" , &LoopDeletionLegacyPass::ID, PassInfo::NormalCtor_t(callDefaultCtor <LoopDeletionLegacyPass>), false, false); Registry.registerPass (*PI, true); return PI; } static llvm::once_flag InitializeLoopDeletionLegacyPassPassFlag ; void llvm::initializeLoopDeletionLegacyPassPass(PassRegistry &Registry) { llvm::call_once(InitializeLoopDeletionLegacyPassPassFlag , initializeLoopDeletionLegacyPassPassOnce, std::ref(Registry )); } | |||
| 549 | ||||
| 550 | Pass *llvm::createLoopDeletionPass() { return new LoopDeletionLegacyPass(); } | |||
| 551 | ||||
| 552 | bool LoopDeletionLegacyPass::runOnLoop(Loop *L, LPPassManager &LPM) { | |||
| 553 | if (skipLoop(L)) | |||
| 554 | return false; | |||
| 555 | DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree(); | |||
| 556 | ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE(); | |||
| 557 | LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); | |||
| 558 | auto *MSSAAnalysis = getAnalysisIfAvailable<MemorySSAWrapperPass>(); | |||
| 559 | MemorySSA *MSSA = nullptr; | |||
| 560 | if (MSSAAnalysis) | |||
| 561 | MSSA = &MSSAAnalysis->getMSSA(); | |||
| 562 | // For the old PM, we can't use OptimizationRemarkEmitter as an analysis | |||
| 563 | // pass. Function analyses need to be preserved across loop transformations | |||
| 564 | // but ORE cannot be preserved (see comment before the pass definition). | |||
| 565 | OptimizationRemarkEmitter ORE(L->getHeader()->getParent()); | |||
| 566 | ||||
| 567 | LLVM_DEBUG(dbgs() << "Analyzing Loop for deletion: ")do { } while (false); | |||
| 568 | LLVM_DEBUG(L->dump())do { } while (false); | |||
| 569 | ||||
| 570 | LoopDeletionResult Result = deleteLoopIfDead(L, DT, SE, LI, MSSA, ORE); | |||
| 571 | ||||
| 572 | // If we can prove the backedge isn't taken, just break it and be done. This | |||
| 573 | // leaves the loop structure in place which means it can handle dispatching | |||
| 574 | // to the right exit based on whatever loop invariant structure remains. | |||
| 575 | if (Result != LoopDeletionResult::Deleted) | |||
| 576 | Result = merge(Result, breakBackedgeIfNotTaken(L, DT, SE, LI, MSSA, ORE)); | |||
| 577 | ||||
| 578 | if (Result == LoopDeletionResult::Deleted) | |||
| 579 | LPM.markLoopAsDeleted(*L); | |||
| 580 | ||||
| 581 | return Result != LoopDeletionResult::Unmodified; | |||
| 582 | } |