| File: | src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Analysis/LoopInfo.cpp |
| Warning: | line 246, column 36 Called C++ object pointer is null |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
| 1 | //===- LoopInfo.cpp - Natural Loop Calculator -----------------------------===// | |||
| 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 defines the LoopInfo class that is used to identify natural loops | |||
| 10 | // and determine the loop depth of various nodes of the CFG. Note that the | |||
| 11 | // loops identified may actually be several natural loops that share the same | |||
| 12 | // header node... not just a single natural loop. | |||
| 13 | // | |||
| 14 | //===----------------------------------------------------------------------===// | |||
| 15 | ||||
| 16 | #include "llvm/Analysis/LoopInfo.h" | |||
| 17 | #include "llvm/ADT/DepthFirstIterator.h" | |||
| 18 | #include "llvm/ADT/ScopeExit.h" | |||
| 19 | #include "llvm/ADT/SmallPtrSet.h" | |||
| 20 | #include "llvm/Analysis/IVDescriptors.h" | |||
| 21 | #include "llvm/Analysis/LoopInfoImpl.h" | |||
| 22 | #include "llvm/Analysis/LoopIterator.h" | |||
| 23 | #include "llvm/Analysis/LoopNestAnalysis.h" | |||
| 24 | #include "llvm/Analysis/MemorySSA.h" | |||
| 25 | #include "llvm/Analysis/MemorySSAUpdater.h" | |||
| 26 | #include "llvm/Analysis/ScalarEvolutionExpressions.h" | |||
| 27 | #include "llvm/Analysis/ValueTracking.h" | |||
| 28 | #include "llvm/Config/llvm-config.h" | |||
| 29 | #include "llvm/IR/CFG.h" | |||
| 30 | #include "llvm/IR/Constants.h" | |||
| 31 | #include "llvm/IR/DebugLoc.h" | |||
| 32 | #include "llvm/IR/Dominators.h" | |||
| 33 | #include "llvm/IR/IRPrintingPasses.h" | |||
| 34 | #include "llvm/IR/Instructions.h" | |||
| 35 | #include "llvm/IR/LLVMContext.h" | |||
| 36 | #include "llvm/IR/Metadata.h" | |||
| 37 | #include "llvm/IR/PassManager.h" | |||
| 38 | #include "llvm/IR/PrintPasses.h" | |||
| 39 | #include "llvm/InitializePasses.h" | |||
| 40 | #include "llvm/Support/CommandLine.h" | |||
| 41 | #include "llvm/Support/Debug.h" | |||
| 42 | #include "llvm/Support/raw_ostream.h" | |||
| 43 | #include <algorithm> | |||
| 44 | using namespace llvm; | |||
| 45 | ||||
| 46 | // Explicitly instantiate methods in LoopInfoImpl.h for IR-level Loops. | |||
| 47 | template class llvm::LoopBase<BasicBlock, Loop>; | |||
| 48 | template class llvm::LoopInfoBase<BasicBlock, Loop>; | |||
| 49 | ||||
| 50 | // Always verify loopinfo if expensive checking is enabled. | |||
| 51 | #ifdef EXPENSIVE_CHECKS | |||
| 52 | bool llvm::VerifyLoopInfo = true; | |||
| 53 | #else | |||
| 54 | bool llvm::VerifyLoopInfo = false; | |||
| 55 | #endif | |||
| 56 | static cl::opt<bool, true> | |||
| 57 | VerifyLoopInfoX("verify-loop-info", cl::location(VerifyLoopInfo), | |||
| 58 | cl::Hidden, cl::desc("Verify loop info (time consuming)")); | |||
| 59 | ||||
| 60 | //===----------------------------------------------------------------------===// | |||
| 61 | // Loop implementation | |||
| 62 | // | |||
| 63 | ||||
| 64 | bool Loop::isLoopInvariant(const Value *V) const { | |||
| 65 | if (const Instruction *I = dyn_cast<Instruction>(V)) | |||
| 66 | return !contains(I); | |||
| 67 | return true; // All non-instructions are loop invariant | |||
| 68 | } | |||
| 69 | ||||
| 70 | bool Loop::hasLoopInvariantOperands(const Instruction *I) const { | |||
| 71 | return all_of(I->operands(), [this](Value *V) { return isLoopInvariant(V); }); | |||
| 72 | } | |||
| 73 | ||||
| 74 | bool Loop::makeLoopInvariant(Value *V, bool &Changed, Instruction *InsertPt, | |||
| 75 | MemorySSAUpdater *MSSAU) const { | |||
| 76 | if (Instruction *I = dyn_cast<Instruction>(V)) | |||
| 77 | return makeLoopInvariant(I, Changed, InsertPt, MSSAU); | |||
| 78 | return true; // All non-instructions are loop-invariant. | |||
| 79 | } | |||
| 80 | ||||
| 81 | bool Loop::makeLoopInvariant(Instruction *I, bool &Changed, | |||
| 82 | Instruction *InsertPt, | |||
| 83 | MemorySSAUpdater *MSSAU) const { | |||
| 84 | // Test if the value is already loop-invariant. | |||
| 85 | if (isLoopInvariant(I)) | |||
| 86 | return true; | |||
| 87 | if (!isSafeToSpeculativelyExecute(I)) | |||
| 88 | return false; | |||
| 89 | if (I->mayReadFromMemory()) | |||
| 90 | return false; | |||
| 91 | // EH block instructions are immobile. | |||
| 92 | if (I->isEHPad()) | |||
| 93 | return false; | |||
| 94 | // Determine the insertion point, unless one was given. | |||
| 95 | if (!InsertPt) { | |||
| 96 | BasicBlock *Preheader = getLoopPreheader(); | |||
| 97 | // Without a preheader, hoisting is not feasible. | |||
| 98 | if (!Preheader) | |||
| 99 | return false; | |||
| 100 | InsertPt = Preheader->getTerminator(); | |||
| 101 | } | |||
| 102 | // Don't hoist instructions with loop-variant operands. | |||
| 103 | for (Value *Operand : I->operands()) | |||
| 104 | if (!makeLoopInvariant(Operand, Changed, InsertPt, MSSAU)) | |||
| 105 | return false; | |||
| 106 | ||||
| 107 | // Hoist. | |||
| 108 | I->moveBefore(InsertPt); | |||
| 109 | if (MSSAU) | |||
| 110 | if (auto *MUD = MSSAU->getMemorySSA()->getMemoryAccess(I)) | |||
| 111 | MSSAU->moveToPlace(MUD, InsertPt->getParent(), | |||
| 112 | MemorySSA::BeforeTerminator); | |||
| 113 | ||||
| 114 | // There is possibility of hoisting this instruction above some arbitrary | |||
| 115 | // condition. Any metadata defined on it can be control dependent on this | |||
| 116 | // condition. Conservatively strip it here so that we don't give any wrong | |||
| 117 | // information to the optimizer. | |||
| 118 | I->dropUnknownNonDebugMetadata(); | |||
| 119 | ||||
| 120 | Changed = true; | |||
| 121 | return true; | |||
| 122 | } | |||
| 123 | ||||
| 124 | bool Loop::getIncomingAndBackEdge(BasicBlock *&Incoming, | |||
| 125 | BasicBlock *&Backedge) const { | |||
| 126 | BasicBlock *H = getHeader(); | |||
| 127 | ||||
| 128 | Incoming = nullptr; | |||
| 129 | Backedge = nullptr; | |||
| 130 | pred_iterator PI = pred_begin(H); | |||
| 131 | assert(PI != pred_end(H) && "Loop must have at least one backedge!")((void)0); | |||
| 132 | Backedge = *PI++; | |||
| 133 | if (PI == pred_end(H)) | |||
| 134 | return false; // dead loop | |||
| 135 | Incoming = *PI++; | |||
| 136 | if (PI != pred_end(H)) | |||
| 137 | return false; // multiple backedges? | |||
| 138 | ||||
| 139 | if (contains(Incoming)) { | |||
| 140 | if (contains(Backedge)) | |||
| 141 | return false; | |||
| 142 | std::swap(Incoming, Backedge); | |||
| 143 | } else if (!contains(Backedge)) | |||
| 144 | return false; | |||
| 145 | ||||
| 146 | assert(Incoming && Backedge && "expected non-null incoming and backedges")((void)0); | |||
| 147 | return true; | |||
| 148 | } | |||
| 149 | ||||
| 150 | PHINode *Loop::getCanonicalInductionVariable() const { | |||
| 151 | BasicBlock *H = getHeader(); | |||
| 152 | ||||
| 153 | BasicBlock *Incoming = nullptr, *Backedge = nullptr; | |||
| 154 | if (!getIncomingAndBackEdge(Incoming, Backedge)) | |||
| 155 | return nullptr; | |||
| 156 | ||||
| 157 | // Loop over all of the PHI nodes, looking for a canonical indvar. | |||
| 158 | for (BasicBlock::iterator I = H->begin(); isa<PHINode>(I); ++I) { | |||
| 159 | PHINode *PN = cast<PHINode>(I); | |||
| 160 | if (ConstantInt *CI = | |||
| 161 | dyn_cast<ConstantInt>(PN->getIncomingValueForBlock(Incoming))) | |||
| 162 | if (CI->isZero()) | |||
| 163 | if (Instruction *Inc = | |||
| 164 | dyn_cast<Instruction>(PN->getIncomingValueForBlock(Backedge))) | |||
| 165 | if (Inc->getOpcode() == Instruction::Add && Inc->getOperand(0) == PN) | |||
| 166 | if (ConstantInt *CI = dyn_cast<ConstantInt>(Inc->getOperand(1))) | |||
| 167 | if (CI->isOne()) | |||
| 168 | return PN; | |||
| 169 | } | |||
| 170 | return nullptr; | |||
| 171 | } | |||
| 172 | ||||
| 173 | /// Get the latch condition instruction. | |||
| 174 | ICmpInst *Loop::getLatchCmpInst() const { | |||
| 175 | if (BasicBlock *Latch = getLoopLatch()) | |||
| 176 | if (BranchInst *BI = dyn_cast_or_null<BranchInst>(Latch->getTerminator())) | |||
| 177 | if (BI->isConditional()) | |||
| 178 | return dyn_cast<ICmpInst>(BI->getCondition()); | |||
| 179 | ||||
| 180 | return nullptr; | |||
| 181 | } | |||
| 182 | ||||
| 183 | /// Return the final value of the loop induction variable if found. | |||
| 184 | static Value *findFinalIVValue(const Loop &L, const PHINode &IndVar, | |||
| 185 | const Instruction &StepInst) { | |||
| 186 | ICmpInst *LatchCmpInst = L.getLatchCmpInst(); | |||
| 187 | if (!LatchCmpInst) | |||
| 188 | return nullptr; | |||
| 189 | ||||
| 190 | Value *Op0 = LatchCmpInst->getOperand(0); | |||
| 191 | Value *Op1 = LatchCmpInst->getOperand(1); | |||
| 192 | if (Op0 == &IndVar || Op0 == &StepInst) | |||
| 193 | return Op1; | |||
| 194 | ||||
| 195 | if (Op1 == &IndVar || Op1 == &StepInst) | |||
| 196 | return Op0; | |||
| 197 | ||||
| 198 | return nullptr; | |||
| 199 | } | |||
| 200 | ||||
| 201 | Optional<Loop::LoopBounds> Loop::LoopBounds::getBounds(const Loop &L, | |||
| 202 | PHINode &IndVar, | |||
| 203 | ScalarEvolution &SE) { | |||
| 204 | InductionDescriptor IndDesc; | |||
| 205 | if (!InductionDescriptor::isInductionPHI(&IndVar, &L, &SE, IndDesc)) | |||
| 206 | return None; | |||
| 207 | ||||
| 208 | Value *InitialIVValue = IndDesc.getStartValue(); | |||
| 209 | Instruction *StepInst = IndDesc.getInductionBinOp(); | |||
| 210 | if (!InitialIVValue || !StepInst) | |||
| 211 | return None; | |||
| 212 | ||||
| 213 | const SCEV *Step = IndDesc.getStep(); | |||
| 214 | Value *StepInstOp1 = StepInst->getOperand(1); | |||
| 215 | Value *StepInstOp0 = StepInst->getOperand(0); | |||
| 216 | Value *StepValue = nullptr; | |||
| 217 | if (SE.getSCEV(StepInstOp1) == Step) | |||
| 218 | StepValue = StepInstOp1; | |||
| 219 | else if (SE.getSCEV(StepInstOp0) == Step) | |||
| 220 | StepValue = StepInstOp0; | |||
| 221 | ||||
| 222 | Value *FinalIVValue = findFinalIVValue(L, IndVar, *StepInst); | |||
| 223 | if (!FinalIVValue) | |||
| 224 | return None; | |||
| 225 | ||||
| 226 | return LoopBounds(L, *InitialIVValue, *StepInst, StepValue, *FinalIVValue, | |||
| 227 | SE); | |||
| 228 | } | |||
| 229 | ||||
| 230 | using Direction = Loop::LoopBounds::Direction; | |||
| 231 | ||||
| 232 | ICmpInst::Predicate Loop::LoopBounds::getCanonicalPredicate() const { | |||
| 233 | BasicBlock *Latch = L.getLoopLatch(); | |||
| 234 | assert(Latch && "Expecting valid latch")((void)0); | |||
| 235 | ||||
| 236 | BranchInst *BI = dyn_cast_or_null<BranchInst>(Latch->getTerminator()); | |||
| ||||
| 237 | assert(BI && BI->isConditional() && "Expecting conditional latch branch")((void)0); | |||
| 238 | ||||
| 239 | ICmpInst *LatchCmpInst = dyn_cast<ICmpInst>(BI->getCondition()); | |||
| 240 | assert(LatchCmpInst &&((void)0) | |||
| 241 | "Expecting the latch compare instruction to be a CmpInst")((void)0); | |||
| 242 | ||||
| 243 | // Need to inverse the predicate when first successor is not the loop | |||
| 244 | // header | |||
| 245 | ICmpInst::Predicate Pred = (BI->getSuccessor(0) == L.getHeader()) | |||
| 246 | ? LatchCmpInst->getPredicate() | |||
| ||||
| 247 | : LatchCmpInst->getInversePredicate(); | |||
| 248 | ||||
| 249 | if (LatchCmpInst->getOperand(0) == &getFinalIVValue()) | |||
| 250 | Pred = ICmpInst::getSwappedPredicate(Pred); | |||
| 251 | ||||
| 252 | // Need to flip strictness of the predicate when the latch compare instruction | |||
| 253 | // is not using StepInst | |||
| 254 | if (LatchCmpInst->getOperand(0) == &getStepInst() || | |||
| 255 | LatchCmpInst->getOperand(1) == &getStepInst()) | |||
| 256 | return Pred; | |||
| 257 | ||||
| 258 | // Cannot flip strictness of NE and EQ | |||
| 259 | if (Pred != ICmpInst::ICMP_NE && Pred != ICmpInst::ICMP_EQ) | |||
| 260 | return ICmpInst::getFlippedStrictnessPredicate(Pred); | |||
| 261 | ||||
| 262 | Direction D = getDirection(); | |||
| 263 | if (D == Direction::Increasing) | |||
| 264 | return ICmpInst::ICMP_SLT; | |||
| 265 | ||||
| 266 | if (D == Direction::Decreasing) | |||
| 267 | return ICmpInst::ICMP_SGT; | |||
| 268 | ||||
| 269 | // If cannot determine the direction, then unable to find the canonical | |||
| 270 | // predicate | |||
| 271 | return ICmpInst::BAD_ICMP_PREDICATE; | |||
| 272 | } | |||
| 273 | ||||
| 274 | Direction Loop::LoopBounds::getDirection() const { | |||
| 275 | if (const SCEVAddRecExpr *StepAddRecExpr = | |||
| 276 | dyn_cast<SCEVAddRecExpr>(SE.getSCEV(&getStepInst()))) | |||
| 277 | if (const SCEV *StepRecur = StepAddRecExpr->getStepRecurrence(SE)) { | |||
| 278 | if (SE.isKnownPositive(StepRecur)) | |||
| 279 | return Direction::Increasing; | |||
| 280 | if (SE.isKnownNegative(StepRecur)) | |||
| 281 | return Direction::Decreasing; | |||
| 282 | } | |||
| 283 | ||||
| 284 | return Direction::Unknown; | |||
| 285 | } | |||
| 286 | ||||
| 287 | Optional<Loop::LoopBounds> Loop::getBounds(ScalarEvolution &SE) const { | |||
| 288 | if (PHINode *IndVar = getInductionVariable(SE)) | |||
| 289 | return LoopBounds::getBounds(*this, *IndVar, SE); | |||
| 290 | ||||
| 291 | return None; | |||
| 292 | } | |||
| 293 | ||||
| 294 | PHINode *Loop::getInductionVariable(ScalarEvolution &SE) const { | |||
| 295 | if (!isLoopSimplifyForm()) | |||
| 296 | return nullptr; | |||
| 297 | ||||
| 298 | BasicBlock *Header = getHeader(); | |||
| 299 | assert(Header && "Expected a valid loop header")((void)0); | |||
| 300 | ICmpInst *CmpInst = getLatchCmpInst(); | |||
| 301 | if (!CmpInst) | |||
| 302 | return nullptr; | |||
| 303 | ||||
| 304 | Instruction *LatchCmpOp0 = dyn_cast<Instruction>(CmpInst->getOperand(0)); | |||
| 305 | Instruction *LatchCmpOp1 = dyn_cast<Instruction>(CmpInst->getOperand(1)); | |||
| 306 | ||||
| 307 | for (PHINode &IndVar : Header->phis()) { | |||
| 308 | InductionDescriptor IndDesc; | |||
| 309 | if (!InductionDescriptor::isInductionPHI(&IndVar, this, &SE, IndDesc)) | |||
| 310 | continue; | |||
| 311 | ||||
| 312 | Instruction *StepInst = IndDesc.getInductionBinOp(); | |||
| 313 | ||||
| 314 | // case 1: | |||
| 315 | // IndVar = phi[{InitialValue, preheader}, {StepInst, latch}] | |||
| 316 | // StepInst = IndVar + step | |||
| 317 | // cmp = StepInst < FinalValue | |||
| 318 | if (StepInst == LatchCmpOp0 || StepInst == LatchCmpOp1) | |||
| 319 | return &IndVar; | |||
| 320 | ||||
| 321 | // case 2: | |||
| 322 | // IndVar = phi[{InitialValue, preheader}, {StepInst, latch}] | |||
| 323 | // StepInst = IndVar + step | |||
| 324 | // cmp = IndVar < FinalValue | |||
| 325 | if (&IndVar == LatchCmpOp0 || &IndVar == LatchCmpOp1) | |||
| 326 | return &IndVar; | |||
| 327 | } | |||
| 328 | ||||
| 329 | return nullptr; | |||
| 330 | } | |||
| 331 | ||||
| 332 | bool Loop::getInductionDescriptor(ScalarEvolution &SE, | |||
| 333 | InductionDescriptor &IndDesc) const { | |||
| 334 | if (PHINode *IndVar = getInductionVariable(SE)) | |||
| 335 | return InductionDescriptor::isInductionPHI(IndVar, this, &SE, IndDesc); | |||
| 336 | ||||
| 337 | return false; | |||
| 338 | } | |||
| 339 | ||||
| 340 | bool Loop::isAuxiliaryInductionVariable(PHINode &AuxIndVar, | |||
| 341 | ScalarEvolution &SE) const { | |||
| 342 | // Located in the loop header | |||
| 343 | BasicBlock *Header = getHeader(); | |||
| 344 | if (AuxIndVar.getParent() != Header) | |||
| 345 | return false; | |||
| 346 | ||||
| 347 | // No uses outside of the loop | |||
| 348 | for (User *U : AuxIndVar.users()) | |||
| 349 | if (const Instruction *I = dyn_cast<Instruction>(U)) | |||
| 350 | if (!contains(I)) | |||
| 351 | return false; | |||
| 352 | ||||
| 353 | InductionDescriptor IndDesc; | |||
| 354 | if (!InductionDescriptor::isInductionPHI(&AuxIndVar, this, &SE, IndDesc)) | |||
| 355 | return false; | |||
| 356 | ||||
| 357 | // The step instruction opcode should be add or sub. | |||
| 358 | if (IndDesc.getInductionOpcode() != Instruction::Add && | |||
| 359 | IndDesc.getInductionOpcode() != Instruction::Sub) | |||
| 360 | return false; | |||
| 361 | ||||
| 362 | // Incremented by a loop invariant step for each loop iteration | |||
| 363 | return SE.isLoopInvariant(IndDesc.getStep(), this); | |||
| 364 | } | |||
| 365 | ||||
| 366 | BranchInst *Loop::getLoopGuardBranch() const { | |||
| 367 | if (!isLoopSimplifyForm()) | |||
| 368 | return nullptr; | |||
| 369 | ||||
| 370 | BasicBlock *Preheader = getLoopPreheader(); | |||
| 371 | assert(Preheader && getLoopLatch() &&((void)0) | |||
| 372 | "Expecting a loop with valid preheader and latch")((void)0); | |||
| 373 | ||||
| 374 | // Loop should be in rotate form. | |||
| 375 | if (!isRotatedForm()) | |||
| 376 | return nullptr; | |||
| 377 | ||||
| 378 | // Disallow loops with more than one unique exit block, as we do not verify | |||
| 379 | // that GuardOtherSucc post dominates all exit blocks. | |||
| 380 | BasicBlock *ExitFromLatch = getUniqueExitBlock(); | |||
| 381 | if (!ExitFromLatch) | |||
| 382 | return nullptr; | |||
| 383 | ||||
| 384 | BasicBlock *GuardBB = Preheader->getUniquePredecessor(); | |||
| 385 | if (!GuardBB) | |||
| 386 | return nullptr; | |||
| 387 | ||||
| 388 | assert(GuardBB->getTerminator() && "Expecting valid guard terminator")((void)0); | |||
| 389 | ||||
| 390 | BranchInst *GuardBI = dyn_cast<BranchInst>(GuardBB->getTerminator()); | |||
| 391 | if (!GuardBI || GuardBI->isUnconditional()) | |||
| 392 | return nullptr; | |||
| 393 | ||||
| 394 | BasicBlock *GuardOtherSucc = (GuardBI->getSuccessor(0) == Preheader) | |||
| 395 | ? GuardBI->getSuccessor(1) | |||
| 396 | : GuardBI->getSuccessor(0); | |||
| 397 | ||||
| 398 | // Check if ExitFromLatch (or any BasicBlock which is an empty unique | |||
| 399 | // successor of ExitFromLatch) is equal to GuardOtherSucc. If | |||
| 400 | // skipEmptyBlockUntil returns GuardOtherSucc, then the guard branch for the | |||
| 401 | // loop is GuardBI (return GuardBI), otherwise return nullptr. | |||
| 402 | if (&LoopNest::skipEmptyBlockUntil(ExitFromLatch, GuardOtherSucc, | |||
| 403 | /*CheckUniquePred=*/true) == | |||
| 404 | GuardOtherSucc) | |||
| 405 | return GuardBI; | |||
| 406 | else | |||
| 407 | return nullptr; | |||
| 408 | } | |||
| 409 | ||||
| 410 | bool Loop::isCanonical(ScalarEvolution &SE) const { | |||
| 411 | InductionDescriptor IndDesc; | |||
| 412 | if (!getInductionDescriptor(SE, IndDesc)) | |||
| 413 | return false; | |||
| 414 | ||||
| 415 | ConstantInt *Init = dyn_cast_or_null<ConstantInt>(IndDesc.getStartValue()); | |||
| 416 | if (!Init || !Init->isZero()) | |||
| 417 | return false; | |||
| 418 | ||||
| 419 | if (IndDesc.getInductionOpcode() != Instruction::Add) | |||
| 420 | return false; | |||
| 421 | ||||
| 422 | ConstantInt *Step = IndDesc.getConstIntStepValue(); | |||
| 423 | if (!Step || !Step->isOne()) | |||
| 424 | return false; | |||
| 425 | ||||
| 426 | return true; | |||
| 427 | } | |||
| 428 | ||||
| 429 | // Check that 'BB' doesn't have any uses outside of the 'L' | |||
| 430 | static bool isBlockInLCSSAForm(const Loop &L, const BasicBlock &BB, | |||
| 431 | const DominatorTree &DT) { | |||
| 432 | for (const Instruction &I : BB) { | |||
| 433 | // Tokens can't be used in PHI nodes and live-out tokens prevent loop | |||
| 434 | // optimizations, so for the purposes of considered LCSSA form, we | |||
| 435 | // can ignore them. | |||
| 436 | if (I.getType()->isTokenTy()) | |||
| 437 | continue; | |||
| 438 | ||||
| 439 | for (const Use &U : I.uses()) { | |||
| 440 | const Instruction *UI = cast<Instruction>(U.getUser()); | |||
| 441 | const BasicBlock *UserBB = UI->getParent(); | |||
| 442 | ||||
| 443 | // For practical purposes, we consider that the use in a PHI | |||
| 444 | // occurs in the respective predecessor block. For more info, | |||
| 445 | // see the `phi` doc in LangRef and the LCSSA doc. | |||
| 446 | if (const PHINode *P = dyn_cast<PHINode>(UI)) | |||
| 447 | UserBB = P->getIncomingBlock(U); | |||
| 448 | ||||
| 449 | // Check the current block, as a fast-path, before checking whether | |||
| 450 | // the use is anywhere in the loop. Most values are used in the same | |||
| 451 | // block they are defined in. Also, blocks not reachable from the | |||
| 452 | // entry are special; uses in them don't need to go through PHIs. | |||
| 453 | if (UserBB != &BB && !L.contains(UserBB) && | |||
| 454 | DT.isReachableFromEntry(UserBB)) | |||
| 455 | return false; | |||
| 456 | } | |||
| 457 | } | |||
| 458 | return true; | |||
| 459 | } | |||
| 460 | ||||
| 461 | bool Loop::isLCSSAForm(const DominatorTree &DT) const { | |||
| 462 | // For each block we check that it doesn't have any uses outside of this loop. | |||
| 463 | return all_of(this->blocks(), [&](const BasicBlock *BB) { | |||
| 464 | return isBlockInLCSSAForm(*this, *BB, DT); | |||
| 465 | }); | |||
| 466 | } | |||
| 467 | ||||
| 468 | bool Loop::isRecursivelyLCSSAForm(const DominatorTree &DT, | |||
| 469 | const LoopInfo &LI) const { | |||
| 470 | // For each block we check that it doesn't have any uses outside of its | |||
| 471 | // innermost loop. This process will transitively guarantee that the current | |||
| 472 | // loop and all of the nested loops are in LCSSA form. | |||
| 473 | return all_of(this->blocks(), [&](const BasicBlock *BB) { | |||
| 474 | return isBlockInLCSSAForm(*LI.getLoopFor(BB), *BB, DT); | |||
| 475 | }); | |||
| 476 | } | |||
| 477 | ||||
| 478 | bool Loop::isLoopSimplifyForm() const { | |||
| 479 | // Normal-form loops have a preheader, a single backedge, and all of their | |||
| 480 | // exits have all their predecessors inside the loop. | |||
| 481 | return getLoopPreheader() && getLoopLatch() && hasDedicatedExits(); | |||
| 482 | } | |||
| 483 | ||||
| 484 | // Routines that reform the loop CFG and split edges often fail on indirectbr. | |||
| 485 | bool Loop::isSafeToClone() const { | |||
| 486 | // Return false if any loop blocks contain indirectbrs, or there are any calls | |||
| 487 | // to noduplicate functions. | |||
| 488 | // FIXME: it should be ok to clone CallBrInst's if we correctly update the | |||
| 489 | // operand list to reflect the newly cloned labels. | |||
| 490 | for (BasicBlock *BB : this->blocks()) { | |||
| 491 | if (isa<IndirectBrInst>(BB->getTerminator()) || | |||
| 492 | isa<CallBrInst>(BB->getTerminator())) | |||
| 493 | return false; | |||
| 494 | ||||
| 495 | for (Instruction &I : *BB) | |||
| 496 | if (auto *CB = dyn_cast<CallBase>(&I)) | |||
| 497 | if (CB->cannotDuplicate()) | |||
| 498 | return false; | |||
| 499 | } | |||
| 500 | return true; | |||
| 501 | } | |||
| 502 | ||||
| 503 | MDNode *Loop::getLoopID() const { | |||
| 504 | MDNode *LoopID = nullptr; | |||
| 505 | ||||
| 506 | // Go through the latch blocks and check the terminator for the metadata. | |||
| 507 | SmallVector<BasicBlock *, 4> LatchesBlocks; | |||
| 508 | getLoopLatches(LatchesBlocks); | |||
| 509 | for (BasicBlock *BB : LatchesBlocks) { | |||
| 510 | Instruction *TI = BB->getTerminator(); | |||
| 511 | MDNode *MD = TI->getMetadata(LLVMContext::MD_loop); | |||
| 512 | ||||
| 513 | if (!MD) | |||
| 514 | return nullptr; | |||
| 515 | ||||
| 516 | if (!LoopID) | |||
| 517 | LoopID = MD; | |||
| 518 | else if (MD != LoopID) | |||
| 519 | return nullptr; | |||
| 520 | } | |||
| 521 | if (!LoopID || LoopID->getNumOperands() == 0 || | |||
| 522 | LoopID->getOperand(0) != LoopID) | |||
| 523 | return nullptr; | |||
| 524 | return LoopID; | |||
| 525 | } | |||
| 526 | ||||
| 527 | void Loop::setLoopID(MDNode *LoopID) const { | |||
| 528 | assert((!LoopID || LoopID->getNumOperands() > 0) &&((void)0) | |||
| 529 | "Loop ID needs at least one operand")((void)0); | |||
| 530 | assert((!LoopID || LoopID->getOperand(0) == LoopID) &&((void)0) | |||
| 531 | "Loop ID should refer to itself")((void)0); | |||
| 532 | ||||
| 533 | SmallVector<BasicBlock *, 4> LoopLatches; | |||
| 534 | getLoopLatches(LoopLatches); | |||
| 535 | for (BasicBlock *BB : LoopLatches) | |||
| 536 | BB->getTerminator()->setMetadata(LLVMContext::MD_loop, LoopID); | |||
| 537 | } | |||
| 538 | ||||
| 539 | void Loop::setLoopAlreadyUnrolled() { | |||
| 540 | LLVMContext &Context = getHeader()->getContext(); | |||
| 541 | ||||
| 542 | MDNode *DisableUnrollMD = | |||
| 543 | MDNode::get(Context, MDString::get(Context, "llvm.loop.unroll.disable")); | |||
| 544 | MDNode *LoopID = getLoopID(); | |||
| 545 | MDNode *NewLoopID = makePostTransformationMetadata( | |||
| 546 | Context, LoopID, {"llvm.loop.unroll."}, {DisableUnrollMD}); | |||
| 547 | setLoopID(NewLoopID); | |||
| 548 | } | |||
| 549 | ||||
| 550 | void Loop::setLoopMustProgress() { | |||
| 551 | LLVMContext &Context = getHeader()->getContext(); | |||
| 552 | ||||
| 553 | MDNode *MustProgress = findOptionMDForLoop(this, "llvm.loop.mustprogress"); | |||
| 554 | ||||
| 555 | if (MustProgress) | |||
| 556 | return; | |||
| 557 | ||||
| 558 | MDNode *MustProgressMD = | |||
| 559 | MDNode::get(Context, MDString::get(Context, "llvm.loop.mustprogress")); | |||
| 560 | MDNode *LoopID = getLoopID(); | |||
| 561 | MDNode *NewLoopID = | |||
| 562 | makePostTransformationMetadata(Context, LoopID, {}, {MustProgressMD}); | |||
| 563 | setLoopID(NewLoopID); | |||
| 564 | } | |||
| 565 | ||||
| 566 | bool Loop::isAnnotatedParallel() const { | |||
| 567 | MDNode *DesiredLoopIdMetadata = getLoopID(); | |||
| 568 | ||||
| 569 | if (!DesiredLoopIdMetadata) | |||
| 570 | return false; | |||
| 571 | ||||
| 572 | MDNode *ParallelAccesses = | |||
| 573 | findOptionMDForLoop(this, "llvm.loop.parallel_accesses"); | |||
| 574 | SmallPtrSet<MDNode *, 4> | |||
| 575 | ParallelAccessGroups; // For scalable 'contains' check. | |||
| 576 | if (ParallelAccesses) { | |||
| 577 | for (const MDOperand &MD : drop_begin(ParallelAccesses->operands())) { | |||
| 578 | MDNode *AccGroup = cast<MDNode>(MD.get()); | |||
| 579 | assert(isValidAsAccessGroup(AccGroup) &&((void)0) | |||
| 580 | "List item must be an access group")((void)0); | |||
| 581 | ParallelAccessGroups.insert(AccGroup); | |||
| 582 | } | |||
| 583 | } | |||
| 584 | ||||
| 585 | // The loop branch contains the parallel loop metadata. In order to ensure | |||
| 586 | // that any parallel-loop-unaware optimization pass hasn't added loop-carried | |||
| 587 | // dependencies (thus converted the loop back to a sequential loop), check | |||
| 588 | // that all the memory instructions in the loop belong to an access group that | |||
| 589 | // is parallel to this loop. | |||
| 590 | for (BasicBlock *BB : this->blocks()) { | |||
| 591 | for (Instruction &I : *BB) { | |||
| 592 | if (!I.mayReadOrWriteMemory()) | |||
| 593 | continue; | |||
| 594 | ||||
| 595 | if (MDNode *AccessGroup = I.getMetadata(LLVMContext::MD_access_group)) { | |||
| 596 | auto ContainsAccessGroup = [&ParallelAccessGroups](MDNode *AG) -> bool { | |||
| 597 | if (AG->getNumOperands() == 0) { | |||
| 598 | assert(isValidAsAccessGroup(AG) && "Item must be an access group")((void)0); | |||
| 599 | return ParallelAccessGroups.count(AG); | |||
| 600 | } | |||
| 601 | ||||
| 602 | for (const MDOperand &AccessListItem : AG->operands()) { | |||
| 603 | MDNode *AccGroup = cast<MDNode>(AccessListItem.get()); | |||
| 604 | assert(isValidAsAccessGroup(AccGroup) &&((void)0) | |||
| 605 | "List item must be an access group")((void)0); | |||
| 606 | if (ParallelAccessGroups.count(AccGroup)) | |||
| 607 | return true; | |||
| 608 | } | |||
| 609 | return false; | |||
| 610 | }; | |||
| 611 | ||||
| 612 | if (ContainsAccessGroup(AccessGroup)) | |||
| 613 | continue; | |||
| 614 | } | |||
| 615 | ||||
| 616 | // The memory instruction can refer to the loop identifier metadata | |||
| 617 | // directly or indirectly through another list metadata (in case of | |||
| 618 | // nested parallel loops). The loop identifier metadata refers to | |||
| 619 | // itself so we can check both cases with the same routine. | |||
| 620 | MDNode *LoopIdMD = | |||
| 621 | I.getMetadata(LLVMContext::MD_mem_parallel_loop_access); | |||
| 622 | ||||
| 623 | if (!LoopIdMD) | |||
| 624 | return false; | |||
| 625 | ||||
| 626 | if (!llvm::is_contained(LoopIdMD->operands(), DesiredLoopIdMetadata)) | |||
| 627 | return false; | |||
| 628 | } | |||
| 629 | } | |||
| 630 | return true; | |||
| 631 | } | |||
| 632 | ||||
| 633 | DebugLoc Loop::getStartLoc() const { return getLocRange().getStart(); } | |||
| 634 | ||||
| 635 | Loop::LocRange Loop::getLocRange() const { | |||
| 636 | // If we have a debug location in the loop ID, then use it. | |||
| 637 | if (MDNode *LoopID = getLoopID()) { | |||
| 638 | DebugLoc Start; | |||
| 639 | // We use the first DebugLoc in the header as the start location of the loop | |||
| 640 | // and if there is a second DebugLoc in the header we use it as end location | |||
| 641 | // of the loop. | |||
| 642 | for (unsigned i = 1, ie = LoopID->getNumOperands(); i < ie; ++i) { | |||
| 643 | if (DILocation *L = dyn_cast<DILocation>(LoopID->getOperand(i))) { | |||
| 644 | if (!Start) | |||
| 645 | Start = DebugLoc(L); | |||
| 646 | else | |||
| 647 | return LocRange(Start, DebugLoc(L)); | |||
| 648 | } | |||
| 649 | } | |||
| 650 | ||||
| 651 | if (Start) | |||
| 652 | return LocRange(Start); | |||
| 653 | } | |||
| 654 | ||||
| 655 | // Try the pre-header first. | |||
| 656 | if (BasicBlock *PHeadBB = getLoopPreheader()) | |||
| 657 | if (DebugLoc DL = PHeadBB->getTerminator()->getDebugLoc()) | |||
| 658 | return LocRange(DL); | |||
| 659 | ||||
| 660 | // If we have no pre-header or there are no instructions with debug | |||
| 661 | // info in it, try the header. | |||
| 662 | if (BasicBlock *HeadBB = getHeader()) | |||
| 663 | return LocRange(HeadBB->getTerminator()->getDebugLoc()); | |||
| 664 | ||||
| 665 | return LocRange(); | |||
| 666 | } | |||
| 667 | ||||
| 668 | #if !defined(NDEBUG1) || defined(LLVM_ENABLE_DUMP) | |||
| 669 | LLVM_DUMP_METHOD__attribute__((noinline)) void Loop::dump() const { print(dbgs()); } | |||
| 670 | ||||
| 671 | LLVM_DUMP_METHOD__attribute__((noinline)) void Loop::dumpVerbose() const { | |||
| 672 | print(dbgs(), /*Verbose=*/true); | |||
| 673 | } | |||
| 674 | #endif | |||
| 675 | ||||
| 676 | //===----------------------------------------------------------------------===// | |||
| 677 | // UnloopUpdater implementation | |||
| 678 | // | |||
| 679 | ||||
| 680 | namespace { | |||
| 681 | /// Find the new parent loop for all blocks within the "unloop" whose last | |||
| 682 | /// backedges has just been removed. | |||
| 683 | class UnloopUpdater { | |||
| 684 | Loop &Unloop; | |||
| 685 | LoopInfo *LI; | |||
| 686 | ||||
| 687 | LoopBlocksDFS DFS; | |||
| 688 | ||||
| 689 | // Map unloop's immediate subloops to their nearest reachable parents. Nested | |||
| 690 | // loops within these subloops will not change parents. However, an immediate | |||
| 691 | // subloop's new parent will be the nearest loop reachable from either its own | |||
| 692 | // exits *or* any of its nested loop's exits. | |||
| 693 | DenseMap<Loop *, Loop *> SubloopParents; | |||
| 694 | ||||
| 695 | // Flag the presence of an irreducible backedge whose destination is a block | |||
| 696 | // directly contained by the original unloop. | |||
| 697 | bool FoundIB; | |||
| 698 | ||||
| 699 | public: | |||
| 700 | UnloopUpdater(Loop *UL, LoopInfo *LInfo) | |||
| 701 | : Unloop(*UL), LI(LInfo), DFS(UL), FoundIB(false) {} | |||
| 702 | ||||
| 703 | void updateBlockParents(); | |||
| 704 | ||||
| 705 | void removeBlocksFromAncestors(); | |||
| 706 | ||||
| 707 | void updateSubloopParents(); | |||
| 708 | ||||
| 709 | protected: | |||
| 710 | Loop *getNearestLoop(BasicBlock *BB, Loop *BBLoop); | |||
| 711 | }; | |||
| 712 | } // end anonymous namespace | |||
| 713 | ||||
| 714 | /// Update the parent loop for all blocks that are directly contained within the | |||
| 715 | /// original "unloop". | |||
| 716 | void UnloopUpdater::updateBlockParents() { | |||
| 717 | if (Unloop.getNumBlocks()) { | |||
| 718 | // Perform a post order CFG traversal of all blocks within this loop, | |||
| 719 | // propagating the nearest loop from successors to predecessors. | |||
| 720 | LoopBlocksTraversal Traversal(DFS, LI); | |||
| 721 | for (BasicBlock *POI : Traversal) { | |||
| 722 | ||||
| 723 | Loop *L = LI->getLoopFor(POI); | |||
| 724 | Loop *NL = getNearestLoop(POI, L); | |||
| 725 | ||||
| 726 | if (NL != L) { | |||
| 727 | // For reducible loops, NL is now an ancestor of Unloop. | |||
| 728 | assert((NL != &Unloop && (!NL || NL->contains(&Unloop))) &&((void)0) | |||
| 729 | "uninitialized successor")((void)0); | |||
| 730 | LI->changeLoopFor(POI, NL); | |||
| 731 | } else { | |||
| 732 | // Or the current block is part of a subloop, in which case its parent | |||
| 733 | // is unchanged. | |||
| 734 | assert((FoundIB || Unloop.contains(L)) && "uninitialized successor")((void)0); | |||
| 735 | } | |||
| 736 | } | |||
| 737 | } | |||
| 738 | // Each irreducible loop within the unloop induces a round of iteration using | |||
| 739 | // the DFS result cached by Traversal. | |||
| 740 | bool Changed = FoundIB; | |||
| 741 | for (unsigned NIters = 0; Changed; ++NIters) { | |||
| 742 | assert(NIters < Unloop.getNumBlocks() && "runaway iterative algorithm")((void)0); | |||
| 743 | ||||
| 744 | // Iterate over the postorder list of blocks, propagating the nearest loop | |||
| 745 | // from successors to predecessors as before. | |||
| 746 | Changed = false; | |||
| 747 | for (LoopBlocksDFS::POIterator POI = DFS.beginPostorder(), | |||
| 748 | POE = DFS.endPostorder(); | |||
| 749 | POI != POE; ++POI) { | |||
| 750 | ||||
| 751 | Loop *L = LI->getLoopFor(*POI); | |||
| 752 | Loop *NL = getNearestLoop(*POI, L); | |||
| 753 | if (NL != L) { | |||
| 754 | assert(NL != &Unloop && (!NL || NL->contains(&Unloop)) &&((void)0) | |||
| 755 | "uninitialized successor")((void)0); | |||
| 756 | LI->changeLoopFor(*POI, NL); | |||
| 757 | Changed = true; | |||
| 758 | } | |||
| 759 | } | |||
| 760 | } | |||
| 761 | } | |||
| 762 | ||||
| 763 | /// Remove unloop's blocks from all ancestors below their new parents. | |||
| 764 | void UnloopUpdater::removeBlocksFromAncestors() { | |||
| 765 | // Remove all unloop's blocks (including those in nested subloops) from | |||
| 766 | // ancestors below the new parent loop. | |||
| 767 | for (BasicBlock *BB : Unloop.blocks()) { | |||
| 768 | Loop *OuterParent = LI->getLoopFor(BB); | |||
| 769 | if (Unloop.contains(OuterParent)) { | |||
| 770 | while (OuterParent->getParentLoop() != &Unloop) | |||
| 771 | OuterParent = OuterParent->getParentLoop(); | |||
| 772 | OuterParent = SubloopParents[OuterParent]; | |||
| 773 | } | |||
| 774 | // Remove blocks from former Ancestors except Unloop itself which will be | |||
| 775 | // deleted. | |||
| 776 | for (Loop *OldParent = Unloop.getParentLoop(); OldParent != OuterParent; | |||
| 777 | OldParent = OldParent->getParentLoop()) { | |||
| 778 | assert(OldParent && "new loop is not an ancestor of the original")((void)0); | |||
| 779 | OldParent->removeBlockFromLoop(BB); | |||
| 780 | } | |||
| 781 | } | |||
| 782 | } | |||
| 783 | ||||
| 784 | /// Update the parent loop for all subloops directly nested within unloop. | |||
| 785 | void UnloopUpdater::updateSubloopParents() { | |||
| 786 | while (!Unloop.isInnermost()) { | |||
| 787 | Loop *Subloop = *std::prev(Unloop.end()); | |||
| 788 | Unloop.removeChildLoop(std::prev(Unloop.end())); | |||
| 789 | ||||
| 790 | assert(SubloopParents.count(Subloop) && "DFS failed to visit subloop")((void)0); | |||
| 791 | if (Loop *Parent = SubloopParents[Subloop]) | |||
| 792 | Parent->addChildLoop(Subloop); | |||
| 793 | else | |||
| 794 | LI->addTopLevelLoop(Subloop); | |||
| 795 | } | |||
| 796 | } | |||
| 797 | ||||
| 798 | /// Return the nearest parent loop among this block's successors. If a successor | |||
| 799 | /// is a subloop header, consider its parent to be the nearest parent of the | |||
| 800 | /// subloop's exits. | |||
| 801 | /// | |||
| 802 | /// For subloop blocks, simply update SubloopParents and return NULL. | |||
| 803 | Loop *UnloopUpdater::getNearestLoop(BasicBlock *BB, Loop *BBLoop) { | |||
| 804 | ||||
| 805 | // Initially for blocks directly contained by Unloop, NearLoop == Unloop and | |||
| 806 | // is considered uninitialized. | |||
| 807 | Loop *NearLoop = BBLoop; | |||
| 808 | ||||
| 809 | Loop *Subloop = nullptr; | |||
| 810 | if (NearLoop != &Unloop && Unloop.contains(NearLoop)) { | |||
| 811 | Subloop = NearLoop; | |||
| 812 | // Find the subloop ancestor that is directly contained within Unloop. | |||
| 813 | while (Subloop->getParentLoop() != &Unloop) { | |||
| 814 | Subloop = Subloop->getParentLoop(); | |||
| 815 | assert(Subloop && "subloop is not an ancestor of the original loop")((void)0); | |||
| 816 | } | |||
| 817 | // Get the current nearest parent of the Subloop exits, initially Unloop. | |||
| 818 | NearLoop = SubloopParents.insert({Subloop, &Unloop}).first->second; | |||
| 819 | } | |||
| 820 | ||||
| 821 | succ_iterator I = succ_begin(BB), E = succ_end(BB); | |||
| 822 | if (I == E) { | |||
| 823 | assert(!Subloop && "subloop blocks must have a successor")((void)0); | |||
| 824 | NearLoop = nullptr; // unloop blocks may now exit the function. | |||
| 825 | } | |||
| 826 | for (; I != E; ++I) { | |||
| 827 | if (*I == BB) | |||
| 828 | continue; // self loops are uninteresting | |||
| 829 | ||||
| 830 | Loop *L = LI->getLoopFor(*I); | |||
| 831 | if (L == &Unloop) { | |||
| 832 | // This successor has not been processed. This path must lead to an | |||
| 833 | // irreducible backedge. | |||
| 834 | assert((FoundIB || !DFS.hasPostorder(*I)) && "should have seen IB")((void)0); | |||
| 835 | FoundIB = true; | |||
| 836 | } | |||
| 837 | if (L != &Unloop && Unloop.contains(L)) { | |||
| 838 | // Successor is in a subloop. | |||
| 839 | if (Subloop) | |||
| 840 | continue; // Branching within subloops. Ignore it. | |||
| 841 | ||||
| 842 | // BB branches from the original into a subloop header. | |||
| 843 | assert(L->getParentLoop() == &Unloop && "cannot skip into nested loops")((void)0); | |||
| 844 | ||||
| 845 | // Get the current nearest parent of the Subloop's exits. | |||
| 846 | L = SubloopParents[L]; | |||
| 847 | // L could be Unloop if the only exit was an irreducible backedge. | |||
| 848 | } | |||
| 849 | if (L == &Unloop) { | |||
| 850 | continue; | |||
| 851 | } | |||
| 852 | // Handle critical edges from Unloop into a sibling loop. | |||
| 853 | if (L && !L->contains(&Unloop)) { | |||
| 854 | L = L->getParentLoop(); | |||
| 855 | } | |||
| 856 | // Remember the nearest parent loop among successors or subloop exits. | |||
| 857 | if (NearLoop == &Unloop || !NearLoop || NearLoop->contains(L)) | |||
| 858 | NearLoop = L; | |||
| 859 | } | |||
| 860 | if (Subloop) { | |||
| 861 | SubloopParents[Subloop] = NearLoop; | |||
| 862 | return BBLoop; | |||
| 863 | } | |||
| 864 | return NearLoop; | |||
| 865 | } | |||
| 866 | ||||
| 867 | LoopInfo::LoopInfo(const DomTreeBase<BasicBlock> &DomTree) { analyze(DomTree); } | |||
| 868 | ||||
| 869 | bool LoopInfo::invalidate(Function &F, const PreservedAnalyses &PA, | |||
| 870 | FunctionAnalysisManager::Invalidator &) { | |||
| 871 | // Check whether the analysis, all analyses on functions, or the function's | |||
| 872 | // CFG have been preserved. | |||
| 873 | auto PAC = PA.getChecker<LoopAnalysis>(); | |||
| 874 | return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() || | |||
| 875 | PAC.preservedSet<CFGAnalyses>()); | |||
| 876 | } | |||
| 877 | ||||
| 878 | void LoopInfo::erase(Loop *Unloop) { | |||
| 879 | assert(!Unloop->isInvalid() && "Loop has already been erased!")((void)0); | |||
| 880 | ||||
| 881 | auto InvalidateOnExit = make_scope_exit([&]() { destroy(Unloop); }); | |||
| 882 | ||||
| 883 | // First handle the special case of no parent loop to simplify the algorithm. | |||
| 884 | if (Unloop->isOutermost()) { | |||
| 885 | // Since BBLoop had no parent, Unloop blocks are no longer in a loop. | |||
| 886 | for (BasicBlock *BB : Unloop->blocks()) { | |||
| 887 | // Don't reparent blocks in subloops. | |||
| 888 | if (getLoopFor(BB) != Unloop) | |||
| 889 | continue; | |||
| 890 | ||||
| 891 | // Blocks no longer have a parent but are still referenced by Unloop until | |||
| 892 | // the Unloop object is deleted. | |||
| 893 | changeLoopFor(BB, nullptr); | |||
| 894 | } | |||
| 895 | ||||
| 896 | // Remove the loop from the top-level LoopInfo object. | |||
| 897 | for (iterator I = begin();; ++I) { | |||
| 898 | assert(I != end() && "Couldn't find loop")((void)0); | |||
| 899 | if (*I == Unloop) { | |||
| 900 | removeLoop(I); | |||
| 901 | break; | |||
| 902 | } | |||
| 903 | } | |||
| 904 | ||||
| 905 | // Move all of the subloops to the top-level. | |||
| 906 | while (!Unloop->isInnermost()) | |||
| 907 | addTopLevelLoop(Unloop->removeChildLoop(std::prev(Unloop->end()))); | |||
| 908 | ||||
| 909 | return; | |||
| 910 | } | |||
| 911 | ||||
| 912 | // Update the parent loop for all blocks within the loop. Blocks within | |||
| 913 | // subloops will not change parents. | |||
| 914 | UnloopUpdater Updater(Unloop, this); | |||
| 915 | Updater.updateBlockParents(); | |||
| 916 | ||||
| 917 | // Remove blocks from former ancestor loops. | |||
| 918 | Updater.removeBlocksFromAncestors(); | |||
| 919 | ||||
| 920 | // Add direct subloops as children in their new parent loop. | |||
| 921 | Updater.updateSubloopParents(); | |||
| 922 | ||||
| 923 | // Remove unloop from its parent loop. | |||
| 924 | Loop *ParentLoop = Unloop->getParentLoop(); | |||
| 925 | for (Loop::iterator I = ParentLoop->begin();; ++I) { | |||
| 926 | assert(I != ParentLoop->end() && "Couldn't find loop")((void)0); | |||
| 927 | if (*I == Unloop) { | |||
| 928 | ParentLoop->removeChildLoop(I); | |||
| 929 | break; | |||
| 930 | } | |||
| 931 | } | |||
| 932 | } | |||
| 933 | ||||
| 934 | bool | |||
| 935 | LoopInfo::wouldBeOutOfLoopUseRequiringLCSSA(const Value *V, | |||
| 936 | const BasicBlock *ExitBB) const { | |||
| 937 | if (V->getType()->isTokenTy()) | |||
| 938 | // We can't form PHIs of token type, so the definition of LCSSA excludes | |||
| 939 | // values of that type. | |||
| 940 | return false; | |||
| 941 | ||||
| 942 | const Instruction *I = dyn_cast<Instruction>(V); | |||
| 943 | if (!I) | |||
| 944 | return false; | |||
| 945 | const Loop *L = getLoopFor(I->getParent()); | |||
| 946 | if (!L) | |||
| 947 | return false; | |||
| 948 | if (L->contains(ExitBB)) | |||
| 949 | // Could be an exit bb of a subloop and contained in defining loop | |||
| 950 | return false; | |||
| 951 | ||||
| 952 | // We found a (new) out-of-loop use location, for a value defined in-loop. | |||
| 953 | // (Note that because of LCSSA, we don't have to account for values defined | |||
| 954 | // in sibling loops. Such values will have LCSSA phis of their own in the | |||
| 955 | // common parent loop.) | |||
| 956 | return true; | |||
| 957 | } | |||
| 958 | ||||
| 959 | AnalysisKey LoopAnalysis::Key; | |||
| 960 | ||||
| 961 | LoopInfo LoopAnalysis::run(Function &F, FunctionAnalysisManager &AM) { | |||
| 962 | // FIXME: Currently we create a LoopInfo from scratch for every function. | |||
| 963 | // This may prove to be too wasteful due to deallocating and re-allocating | |||
| 964 | // memory each time for the underlying map and vector datastructures. At some | |||
| 965 | // point it may prove worthwhile to use a freelist and recycle LoopInfo | |||
| 966 | // objects. I don't want to add that kind of complexity until the scope of | |||
| 967 | // the problem is better understood. | |||
| 968 | LoopInfo LI; | |||
| 969 | LI.analyze(AM.getResult<DominatorTreeAnalysis>(F)); | |||
| 970 | return LI; | |||
| 971 | } | |||
| 972 | ||||
| 973 | PreservedAnalyses LoopPrinterPass::run(Function &F, | |||
| 974 | FunctionAnalysisManager &AM) { | |||
| 975 | AM.getResult<LoopAnalysis>(F).print(OS); | |||
| 976 | return PreservedAnalyses::all(); | |||
| 977 | } | |||
| 978 | ||||
| 979 | void llvm::printLoop(Loop &L, raw_ostream &OS, const std::string &Banner) { | |||
| 980 | ||||
| 981 | if (forcePrintModuleIR()) { | |||
| 982 | // handling -print-module-scope | |||
| 983 | OS << Banner << " (loop: "; | |||
| 984 | L.getHeader()->printAsOperand(OS, false); | |||
| 985 | OS << ")\n"; | |||
| 986 | ||||
| 987 | // printing whole module | |||
| 988 | OS << *L.getHeader()->getModule(); | |||
| 989 | return; | |||
| 990 | } | |||
| 991 | ||||
| 992 | OS << Banner; | |||
| 993 | ||||
| 994 | auto *PreHeader = L.getLoopPreheader(); | |||
| 995 | if (PreHeader) { | |||
| 996 | OS << "\n; Preheader:"; | |||
| 997 | PreHeader->print(OS); | |||
| 998 | OS << "\n; Loop:"; | |||
| 999 | } | |||
| 1000 | ||||
| 1001 | for (auto *Block : L.blocks()) | |||
| 1002 | if (Block) | |||
| 1003 | Block->print(OS); | |||
| 1004 | else | |||
| 1005 | OS << "Printing <null> block"; | |||
| 1006 | ||||
| 1007 | SmallVector<BasicBlock *, 8> ExitBlocks; | |||
| 1008 | L.getExitBlocks(ExitBlocks); | |||
| 1009 | if (!ExitBlocks.empty()) { | |||
| 1010 | OS << "\n; Exit blocks"; | |||
| 1011 | for (auto *Block : ExitBlocks) | |||
| 1012 | if (Block) | |||
| 1013 | Block->print(OS); | |||
| 1014 | else | |||
| 1015 | OS << "Printing <null> block"; | |||
| 1016 | } | |||
| 1017 | } | |||
| 1018 | ||||
| 1019 | MDNode *llvm::findOptionMDForLoopID(MDNode *LoopID, StringRef Name) { | |||
| 1020 | // No loop metadata node, no loop properties. | |||
| 1021 | if (!LoopID) | |||
| 1022 | return nullptr; | |||
| 1023 | ||||
| 1024 | // First operand should refer to the metadata node itself, for legacy reasons. | |||
| 1025 | assert(LoopID->getNumOperands() > 0 && "requires at least one operand")((void)0); | |||
| 1026 | assert(LoopID->getOperand(0) == LoopID && "invalid loop id")((void)0); | |||
| 1027 | ||||
| 1028 | // Iterate over the metdata node operands and look for MDString metadata. | |||
| 1029 | for (unsigned i = 1, e = LoopID->getNumOperands(); i < e; ++i) { | |||
| 1030 | MDNode *MD = dyn_cast<MDNode>(LoopID->getOperand(i)); | |||
| 1031 | if (!MD || MD->getNumOperands() < 1) | |||
| 1032 | continue; | |||
| 1033 | MDString *S = dyn_cast<MDString>(MD->getOperand(0)); | |||
| 1034 | if (!S) | |||
| 1035 | continue; | |||
| 1036 | // Return the operand node if MDString holds expected metadata. | |||
| 1037 | if (Name.equals(S->getString())) | |||
| 1038 | return MD; | |||
| 1039 | } | |||
| 1040 | ||||
| 1041 | // Loop property not found. | |||
| 1042 | return nullptr; | |||
| 1043 | } | |||
| 1044 | ||||
| 1045 | MDNode *llvm::findOptionMDForLoop(const Loop *TheLoop, StringRef Name) { | |||
| 1046 | return findOptionMDForLoopID(TheLoop->getLoopID(), Name); | |||
| 1047 | } | |||
| 1048 | ||||
| 1049 | /// Find string metadata for loop | |||
| 1050 | /// | |||
| 1051 | /// If it has a value (e.g. {"llvm.distribute", 1} return the value as an | |||
| 1052 | /// operand or null otherwise. If the string metadata is not found return | |||
| 1053 | /// Optional's not-a-value. | |||
| 1054 | Optional<const MDOperand *> llvm::findStringMetadataForLoop(const Loop *TheLoop, | |||
| 1055 | StringRef Name) { | |||
| 1056 | MDNode *MD = findOptionMDForLoop(TheLoop, Name); | |||
| 1057 | if (!MD) | |||
| 1058 | return None; | |||
| 1059 | switch (MD->getNumOperands()) { | |||
| 1060 | case 1: | |||
| 1061 | return nullptr; | |||
| 1062 | case 2: | |||
| 1063 | return &MD->getOperand(1); | |||
| 1064 | default: | |||
| 1065 | llvm_unreachable("loop metadata has 0 or 1 operand")__builtin_unreachable(); | |||
| 1066 | } | |||
| 1067 | } | |||
| 1068 | ||||
| 1069 | Optional<bool> llvm::getOptionalBoolLoopAttribute(const Loop *TheLoop, | |||
| 1070 | StringRef Name) { | |||
| 1071 | MDNode *MD = findOptionMDForLoop(TheLoop, Name); | |||
| 1072 | if (!MD) | |||
| 1073 | return None; | |||
| 1074 | switch (MD->getNumOperands()) { | |||
| 1075 | case 1: | |||
| 1076 | // When the value is absent it is interpreted as 'attribute set'. | |||
| 1077 | return true; | |||
| 1078 | case 2: | |||
| 1079 | if (ConstantInt *IntMD = | |||
| 1080 | mdconst::extract_or_null<ConstantInt>(MD->getOperand(1).get())) | |||
| 1081 | return IntMD->getZExtValue(); | |||
| 1082 | return true; | |||
| 1083 | } | |||
| 1084 | llvm_unreachable("unexpected number of options")__builtin_unreachable(); | |||
| 1085 | } | |||
| 1086 | ||||
| 1087 | bool llvm::getBooleanLoopAttribute(const Loop *TheLoop, StringRef Name) { | |||
| 1088 | return getOptionalBoolLoopAttribute(TheLoop, Name).getValueOr(false); | |||
| 1089 | } | |||
| 1090 | ||||
| 1091 | llvm::Optional<int> llvm::getOptionalIntLoopAttribute(const Loop *TheLoop, | |||
| 1092 | StringRef Name) { | |||
| 1093 | const MDOperand *AttrMD = | |||
| 1094 | findStringMetadataForLoop(TheLoop, Name).getValueOr(nullptr); | |||
| 1095 | if (!AttrMD) | |||
| 1096 | return None; | |||
| 1097 | ||||
| 1098 | ConstantInt *IntMD = mdconst::extract_or_null<ConstantInt>(AttrMD->get()); | |||
| 1099 | if (!IntMD) | |||
| 1100 | return None; | |||
| 1101 | ||||
| 1102 | return IntMD->getSExtValue(); | |||
| 1103 | } | |||
| 1104 | ||||
| 1105 | static const char *LLVMLoopMustProgress = "llvm.loop.mustprogress"; | |||
| 1106 | ||||
| 1107 | bool llvm::hasMustProgress(const Loop *L) { | |||
| 1108 | return getBooleanLoopAttribute(L, LLVMLoopMustProgress); | |||
| 1109 | } | |||
| 1110 | ||||
| 1111 | bool llvm::isMustProgress(const Loop *L) { | |||
| 1112 | return L->getHeader()->getParent()->mustProgress() || hasMustProgress(L); | |||
| 1113 | } | |||
| 1114 | ||||
| 1115 | bool llvm::isValidAsAccessGroup(MDNode *Node) { | |||
| 1116 | return Node->getNumOperands() == 0 && Node->isDistinct(); | |||
| 1117 | } | |||
| 1118 | ||||
| 1119 | MDNode *llvm::makePostTransformationMetadata(LLVMContext &Context, | |||
| 1120 | MDNode *OrigLoopID, | |||
| 1121 | ArrayRef<StringRef> RemovePrefixes, | |||
| 1122 | ArrayRef<MDNode *> AddAttrs) { | |||
| 1123 | // First remove any existing loop metadata related to this transformation. | |||
| 1124 | SmallVector<Metadata *, 4> MDs; | |||
| 1125 | ||||
| 1126 | // Reserve first location for self reference to the LoopID metadata node. | |||
| 1127 | MDs.push_back(nullptr); | |||
| 1128 | ||||
| 1129 | // Remove metadata for the transformation that has been applied or that became | |||
| 1130 | // outdated. | |||
| 1131 | if (OrigLoopID) { | |||
| 1132 | for (unsigned i = 1, ie = OrigLoopID->getNumOperands(); i < ie; ++i) { | |||
| 1133 | bool IsVectorMetadata = false; | |||
| 1134 | Metadata *Op = OrigLoopID->getOperand(i); | |||
| 1135 | if (MDNode *MD = dyn_cast<MDNode>(Op)) { | |||
| 1136 | const MDString *S = dyn_cast<MDString>(MD->getOperand(0)); | |||
| 1137 | if (S) | |||
| 1138 | IsVectorMetadata = | |||
| 1139 | llvm::any_of(RemovePrefixes, [S](StringRef Prefix) -> bool { | |||
| 1140 | return S->getString().startswith(Prefix); | |||
| 1141 | }); | |||
| 1142 | } | |||
| 1143 | if (!IsVectorMetadata) | |||
| 1144 | MDs.push_back(Op); | |||
| 1145 | } | |||
| 1146 | } | |||
| 1147 | ||||
| 1148 | // Add metadata to avoid reapplying a transformation, such as | |||
| 1149 | // llvm.loop.unroll.disable and llvm.loop.isvectorized. | |||
| 1150 | MDs.append(AddAttrs.begin(), AddAttrs.end()); | |||
| 1151 | ||||
| 1152 | MDNode *NewLoopID = MDNode::getDistinct(Context, MDs); | |||
| 1153 | // Replace the temporary node with a self-reference. | |||
| 1154 | NewLoopID->replaceOperandWith(0, NewLoopID); | |||
| 1155 | return NewLoopID; | |||
| 1156 | } | |||
| 1157 | ||||
| 1158 | //===----------------------------------------------------------------------===// | |||
| 1159 | // LoopInfo implementation | |||
| 1160 | // | |||
| 1161 | ||||
| 1162 | LoopInfoWrapperPass::LoopInfoWrapperPass() : FunctionPass(ID) { | |||
| 1163 | initializeLoopInfoWrapperPassPass(*PassRegistry::getPassRegistry()); | |||
| 1164 | } | |||
| 1165 | ||||
| 1166 | char LoopInfoWrapperPass::ID = 0; | |||
| 1167 | INITIALIZE_PASS_BEGIN(LoopInfoWrapperPass, "loops", "Natural Loop Information",static void *initializeLoopInfoWrapperPassPassOnce(PassRegistry &Registry) { | |||
| 1168 | true, true)static void *initializeLoopInfoWrapperPassPassOnce(PassRegistry &Registry) { | |||
| 1169 | INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)initializeDominatorTreeWrapperPassPass(Registry); | |||
| 1170 | INITIALIZE_PASS_END(LoopInfoWrapperPass, "loops", "Natural Loop Information",PassInfo *PI = new PassInfo( "Natural Loop Information", "loops" , &LoopInfoWrapperPass::ID, PassInfo::NormalCtor_t(callDefaultCtor <LoopInfoWrapperPass>), true, true); Registry.registerPass (*PI, true); return PI; } static llvm::once_flag InitializeLoopInfoWrapperPassPassFlag ; void llvm::initializeLoopInfoWrapperPassPass(PassRegistry & Registry) { llvm::call_once(InitializeLoopInfoWrapperPassPassFlag , initializeLoopInfoWrapperPassPassOnce, std::ref(Registry)); } | |||
| 1171 | true, true)PassInfo *PI = new PassInfo( "Natural Loop Information", "loops" , &LoopInfoWrapperPass::ID, PassInfo::NormalCtor_t(callDefaultCtor <LoopInfoWrapperPass>), true, true); Registry.registerPass (*PI, true); return PI; } static llvm::once_flag InitializeLoopInfoWrapperPassPassFlag ; void llvm::initializeLoopInfoWrapperPassPass(PassRegistry & Registry) { llvm::call_once(InitializeLoopInfoWrapperPassPassFlag , initializeLoopInfoWrapperPassPassOnce, std::ref(Registry)); } | |||
| 1172 | ||||
| 1173 | bool LoopInfoWrapperPass::runOnFunction(Function &) { | |||
| 1174 | releaseMemory(); | |||
| 1175 | LI.analyze(getAnalysis<DominatorTreeWrapperPass>().getDomTree()); | |||
| 1176 | return false; | |||
| 1177 | } | |||
| 1178 | ||||
| 1179 | void LoopInfoWrapperPass::verifyAnalysis() const { | |||
| 1180 | // LoopInfoWrapperPass is a FunctionPass, but verifying every loop in the | |||
| 1181 | // function each time verifyAnalysis is called is very expensive. The | |||
| 1182 | // -verify-loop-info option can enable this. In order to perform some | |||
| 1183 | // checking by default, LoopPass has been taught to call verifyLoop manually | |||
| 1184 | // during loop pass sequences. | |||
| 1185 | if (VerifyLoopInfo) { | |||
| 1186 | auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree(); | |||
| 1187 | LI.verify(DT); | |||
| 1188 | } | |||
| 1189 | } | |||
| 1190 | ||||
| 1191 | void LoopInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { | |||
| 1192 | AU.setPreservesAll(); | |||
| 1193 | AU.addRequiredTransitive<DominatorTreeWrapperPass>(); | |||
| 1194 | } | |||
| 1195 | ||||
| 1196 | void LoopInfoWrapperPass::print(raw_ostream &OS, const Module *) const { | |||
| 1197 | LI.print(OS); | |||
| 1198 | } | |||
| 1199 | ||||
| 1200 | PreservedAnalyses LoopVerifierPass::run(Function &F, | |||
| 1201 | FunctionAnalysisManager &AM) { | |||
| 1202 | LoopInfo &LI = AM.getResult<LoopAnalysis>(F); | |||
| 1203 | auto &DT = AM.getResult<DominatorTreeAnalysis>(F); | |||
| 1204 | LI.verify(DT); | |||
| 1205 | return PreservedAnalyses::all(); | |||
| 1206 | } | |||
| 1207 | ||||
| 1208 | //===----------------------------------------------------------------------===// | |||
| 1209 | // LoopBlocksDFS implementation | |||
| 1210 | // | |||
| 1211 | ||||
| 1212 | /// Traverse the loop blocks and store the DFS result. | |||
| 1213 | /// Useful for clients that just want the final DFS result and don't need to | |||
| 1214 | /// visit blocks during the initial traversal. | |||
| 1215 | void LoopBlocksDFS::perform(LoopInfo *LI) { | |||
| 1216 | LoopBlocksTraversal Traversal(*this, LI); | |||
| 1217 | for (LoopBlocksTraversal::POTIterator POI = Traversal.begin(), | |||
| 1218 | POE = Traversal.end(); | |||
| 1219 | POI != POE; ++POI) | |||
| 1220 | ; | |||
| 1221 | } |