Yi Kong | 8328301 | 2023-12-13 12:57:00 +0900 | [diff] [blame^] | 1 | //===- llvm/Analysis/LoopInfo.h - Natural Loop Calculator -------*- C++ -*-===// |
| 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 declares a GenericLoopInfo instantiation for LLVM IR. |
| 10 | // |
| 11 | //===----------------------------------------------------------------------===// |
| 12 | |
| 13 | #ifndef LLVM_ANALYSIS_LOOPINFO_H |
| 14 | #define LLVM_ANALYSIS_LOOPINFO_H |
| 15 | |
| 16 | #include "llvm/ADT/DenseMap.h" |
| 17 | #include "llvm/ADT/DenseSet.h" |
| 18 | #include "llvm/ADT/GraphTraits.h" |
| 19 | #include "llvm/ADT/SmallPtrSet.h" |
| 20 | #include "llvm/ADT/SmallVector.h" |
| 21 | #include "llvm/IR/CFG.h" |
| 22 | #include "llvm/IR/Instructions.h" |
| 23 | #include "llvm/IR/PassManager.h" |
| 24 | #include "llvm/Pass.h" |
| 25 | #include "llvm/Support/GenericLoopInfo.h" |
| 26 | #include <algorithm> |
| 27 | #include <optional> |
| 28 | #include <utility> |
| 29 | |
| 30 | namespace llvm { |
| 31 | |
| 32 | class DominatorTree; |
| 33 | class InductionDescriptor; |
| 34 | class Instruction; |
| 35 | class LoopInfo; |
| 36 | class Loop; |
| 37 | class MDNode; |
| 38 | class MemorySSAUpdater; |
| 39 | class ScalarEvolution; |
| 40 | class raw_ostream; |
| 41 | |
| 42 | // Implementation in Support/GenericLoopInfoImpl.h |
| 43 | extern template class LoopBase<BasicBlock, Loop>; |
| 44 | |
| 45 | /// Represents a single loop in the control flow graph. Note that not all SCCs |
| 46 | /// in the CFG are necessarily loops. |
| 47 | class LLVM_EXTERNAL_VISIBILITY Loop : public LoopBase<BasicBlock, Loop> { |
| 48 | public: |
| 49 | /// A range representing the start and end location of a loop. |
| 50 | class LocRange { |
| 51 | DebugLoc Start; |
| 52 | DebugLoc End; |
| 53 | |
| 54 | public: |
| 55 | LocRange() = default; |
| 56 | LocRange(DebugLoc Start) : Start(Start), End(Start) {} |
| 57 | LocRange(DebugLoc Start, DebugLoc End) |
| 58 | : Start(std::move(Start)), End(std::move(End)) {} |
| 59 | |
| 60 | const DebugLoc &getStart() const { return Start; } |
| 61 | const DebugLoc &getEnd() const { return End; } |
| 62 | |
| 63 | /// Check for null. |
| 64 | /// |
| 65 | explicit operator bool() const { return Start && End; } |
| 66 | }; |
| 67 | |
| 68 | /// Return true if the specified value is loop invariant. |
| 69 | bool isLoopInvariant(const Value *V) const; |
| 70 | |
| 71 | /// Return true if all the operands of the specified instruction are loop |
| 72 | /// invariant. |
| 73 | bool hasLoopInvariantOperands(const Instruction *I) const; |
| 74 | |
| 75 | /// If the given value is an instruction inside of the loop and it can be |
| 76 | /// hoisted, do so to make it trivially loop-invariant. |
| 77 | /// Return true if \c V is already loop-invariant, and false if \c V can't |
| 78 | /// be made loop-invariant. If \c V is made loop-invariant, \c Changed is |
| 79 | /// set to true. This function can be used as a slightly more aggressive |
| 80 | /// replacement for isLoopInvariant. |
| 81 | /// |
| 82 | /// If InsertPt is specified, it is the point to hoist instructions to. |
| 83 | /// If null, the terminator of the loop preheader is used. |
| 84 | /// |
| 85 | bool makeLoopInvariant(Value *V, bool &Changed, |
| 86 | Instruction *InsertPt = nullptr, |
| 87 | MemorySSAUpdater *MSSAU = nullptr, |
| 88 | ScalarEvolution *SE = nullptr) const; |
| 89 | |
| 90 | /// If the given instruction is inside of the loop and it can be hoisted, do |
| 91 | /// so to make it trivially loop-invariant. |
| 92 | /// Return true if \c I is already loop-invariant, and false if \c I can't |
| 93 | /// be made loop-invariant. If \c I is made loop-invariant, \c Changed is |
| 94 | /// set to true. This function can be used as a slightly more aggressive |
| 95 | /// replacement for isLoopInvariant. |
| 96 | /// |
| 97 | /// If InsertPt is specified, it is the point to hoist instructions to. |
| 98 | /// If null, the terminator of the loop preheader is used. |
| 99 | /// |
| 100 | bool makeLoopInvariant(Instruction *I, bool &Changed, |
| 101 | Instruction *InsertPt = nullptr, |
| 102 | MemorySSAUpdater *MSSAU = nullptr, |
| 103 | ScalarEvolution *SE = nullptr) const; |
| 104 | |
| 105 | /// Check to see if the loop has a canonical induction variable: an integer |
| 106 | /// recurrence that starts at 0 and increments by one each time through the |
| 107 | /// loop. If so, return the phi node that corresponds to it. |
| 108 | /// |
| 109 | /// The IndVarSimplify pass transforms loops to have a canonical induction |
| 110 | /// variable. |
| 111 | /// |
| 112 | PHINode *getCanonicalInductionVariable() const; |
| 113 | |
| 114 | /// Get the latch condition instruction. |
| 115 | ICmpInst *getLatchCmpInst() const; |
| 116 | |
| 117 | /// Obtain the unique incoming and back edge. Return false if they are |
| 118 | /// non-unique or the loop is dead; otherwise, return true. |
| 119 | bool getIncomingAndBackEdge(BasicBlock *&Incoming, |
| 120 | BasicBlock *&Backedge) const; |
| 121 | |
| 122 | /// Below are some utilities to get the loop guard, loop bounds and induction |
| 123 | /// variable, and to check if a given phinode is an auxiliary induction |
| 124 | /// variable, if the loop is guarded, and if the loop is canonical. |
| 125 | /// |
| 126 | /// Here is an example: |
| 127 | /// \code |
| 128 | /// for (int i = lb; i < ub; i+=step) |
| 129 | /// <loop body> |
| 130 | /// --- pseudo LLVMIR --- |
| 131 | /// beforeloop: |
| 132 | /// guardcmp = (lb < ub) |
| 133 | /// if (guardcmp) goto preheader; else goto afterloop |
| 134 | /// preheader: |
| 135 | /// loop: |
| 136 | /// i_1 = phi[{lb, preheader}, {i_2, latch}] |
| 137 | /// <loop body> |
| 138 | /// i_2 = i_1 + step |
| 139 | /// latch: |
| 140 | /// cmp = (i_2 < ub) |
| 141 | /// if (cmp) goto loop |
| 142 | /// exit: |
| 143 | /// afterloop: |
| 144 | /// \endcode |
| 145 | /// |
| 146 | /// - getBounds |
| 147 | /// - getInitialIVValue --> lb |
| 148 | /// - getStepInst --> i_2 = i_1 + step |
| 149 | /// - getStepValue --> step |
| 150 | /// - getFinalIVValue --> ub |
| 151 | /// - getCanonicalPredicate --> '<' |
| 152 | /// - getDirection --> Increasing |
| 153 | /// |
| 154 | /// - getInductionVariable --> i_1 |
| 155 | /// - isAuxiliaryInductionVariable(x) --> true if x == i_1 |
| 156 | /// - getLoopGuardBranch() |
| 157 | /// --> `if (guardcmp) goto preheader; else goto afterloop` |
| 158 | /// - isGuarded() --> true |
| 159 | /// - isCanonical --> false |
| 160 | struct LoopBounds { |
| 161 | /// Return the LoopBounds object if |
| 162 | /// - the given \p IndVar is an induction variable |
| 163 | /// - the initial value of the induction variable can be found |
| 164 | /// - the step instruction of the induction variable can be found |
| 165 | /// - the final value of the induction variable can be found |
| 166 | /// |
| 167 | /// Else std::nullopt. |
| 168 | static std::optional<Loop::LoopBounds> |
| 169 | getBounds(const Loop &L, PHINode &IndVar, ScalarEvolution &SE); |
| 170 | |
| 171 | /// Get the initial value of the loop induction variable. |
| 172 | Value &getInitialIVValue() const { return InitialIVValue; } |
| 173 | |
| 174 | /// Get the instruction that updates the loop induction variable. |
| 175 | Instruction &getStepInst() const { return StepInst; } |
| 176 | |
| 177 | /// Get the step that the loop induction variable gets updated by in each |
| 178 | /// loop iteration. Return nullptr if not found. |
| 179 | Value *getStepValue() const { return StepValue; } |
| 180 | |
| 181 | /// Get the final value of the loop induction variable. |
| 182 | Value &getFinalIVValue() const { return FinalIVValue; } |
| 183 | |
| 184 | /// Return the canonical predicate for the latch compare instruction, if |
| 185 | /// able to be calcuated. Else BAD_ICMP_PREDICATE. |
| 186 | /// |
| 187 | /// A predicate is considered as canonical if requirements below are all |
| 188 | /// satisfied: |
| 189 | /// 1. The first successor of the latch branch is the loop header |
| 190 | /// If not, inverse the predicate. |
| 191 | /// 2. One of the operands of the latch comparison is StepInst |
| 192 | /// If not, and |
| 193 | /// - if the current calcuated predicate is not ne or eq, flip the |
| 194 | /// predicate. |
| 195 | /// - else if the loop is increasing, return slt |
| 196 | /// (notice that it is safe to change from ne or eq to sign compare) |
| 197 | /// - else if the loop is decreasing, return sgt |
| 198 | /// (notice that it is safe to change from ne or eq to sign compare) |
| 199 | /// |
| 200 | /// Here is an example when both (1) and (2) are not satisfied: |
| 201 | /// \code |
| 202 | /// loop.header: |
| 203 | /// %iv = phi [%initialiv, %loop.preheader], [%inc, %loop.header] |
| 204 | /// %inc = add %iv, %step |
| 205 | /// %cmp = slt %iv, %finaliv |
| 206 | /// br %cmp, %loop.exit, %loop.header |
| 207 | /// loop.exit: |
| 208 | /// \endcode |
| 209 | /// - The second successor of the latch branch is the loop header instead |
| 210 | /// of the first successor (slt -> sge) |
| 211 | /// - The first operand of the latch comparison (%cmp) is the IndVar (%iv) |
| 212 | /// instead of the StepInst (%inc) (sge -> sgt) |
| 213 | /// |
| 214 | /// The predicate would be sgt if both (1) and (2) are satisfied. |
| 215 | /// getCanonicalPredicate() returns sgt for this example. |
| 216 | /// Note: The IR is not changed. |
| 217 | ICmpInst::Predicate getCanonicalPredicate() const; |
| 218 | |
| 219 | /// An enum for the direction of the loop |
| 220 | /// - for (int i = 0; i < ub; ++i) --> Increasing |
| 221 | /// - for (int i = ub; i > 0; --i) --> Descresing |
| 222 | /// - for (int i = x; i != y; i+=z) --> Unknown |
| 223 | enum class Direction { Increasing, Decreasing, Unknown }; |
| 224 | |
| 225 | /// Get the direction of the loop. |
| 226 | Direction getDirection() const; |
| 227 | |
| 228 | private: |
| 229 | LoopBounds(const Loop &Loop, Value &I, Instruction &SI, Value *SV, Value &F, |
| 230 | ScalarEvolution &SE) |
| 231 | : L(Loop), InitialIVValue(I), StepInst(SI), StepValue(SV), |
| 232 | FinalIVValue(F), SE(SE) {} |
| 233 | |
| 234 | const Loop &L; |
| 235 | |
| 236 | // The initial value of the loop induction variable |
| 237 | Value &InitialIVValue; |
| 238 | |
| 239 | // The instruction that updates the loop induction variable |
| 240 | Instruction &StepInst; |
| 241 | |
| 242 | // The value that the loop induction variable gets updated by in each loop |
| 243 | // iteration |
| 244 | Value *StepValue; |
| 245 | |
| 246 | // The final value of the loop induction variable |
| 247 | Value &FinalIVValue; |
| 248 | |
| 249 | ScalarEvolution &SE; |
| 250 | }; |
| 251 | |
| 252 | /// Return the struct LoopBounds collected if all struct members are found, |
| 253 | /// else std::nullopt. |
| 254 | std::optional<LoopBounds> getBounds(ScalarEvolution &SE) const; |
| 255 | |
| 256 | /// Return the loop induction variable if found, else return nullptr. |
| 257 | /// An instruction is considered as the loop induction variable if |
| 258 | /// - it is an induction variable of the loop; and |
| 259 | /// - it is used to determine the condition of the branch in the loop latch |
| 260 | /// |
| 261 | /// Note: the induction variable doesn't need to be canonical, i.e. starts at |
| 262 | /// zero and increments by one each time through the loop (but it can be). |
| 263 | PHINode *getInductionVariable(ScalarEvolution &SE) const; |
| 264 | |
| 265 | /// Get the loop induction descriptor for the loop induction variable. Return |
| 266 | /// true if the loop induction variable is found. |
| 267 | bool getInductionDescriptor(ScalarEvolution &SE, |
| 268 | InductionDescriptor &IndDesc) const; |
| 269 | |
| 270 | /// Return true if the given PHINode \p AuxIndVar is |
| 271 | /// - in the loop header |
| 272 | /// - not used outside of the loop |
| 273 | /// - incremented by a loop invariant step for each loop iteration |
| 274 | /// - step instruction opcode should be add or sub |
| 275 | /// Note: auxiliary induction variable is not required to be used in the |
| 276 | /// conditional branch in the loop latch. (but it can be) |
| 277 | bool isAuxiliaryInductionVariable(PHINode &AuxIndVar, |
| 278 | ScalarEvolution &SE) const; |
| 279 | |
| 280 | /// Return the loop guard branch, if it exists. |
| 281 | /// |
| 282 | /// This currently only works on simplified loop, as it requires a preheader |
| 283 | /// and a latch to identify the guard. It will work on loops of the form: |
| 284 | /// \code |
| 285 | /// GuardBB: |
| 286 | /// br cond1, Preheader, ExitSucc <== GuardBranch |
| 287 | /// Preheader: |
| 288 | /// br Header |
| 289 | /// Header: |
| 290 | /// ... |
| 291 | /// br Latch |
| 292 | /// Latch: |
| 293 | /// br cond2, Header, ExitBlock |
| 294 | /// ExitBlock: |
| 295 | /// br ExitSucc |
| 296 | /// ExitSucc: |
| 297 | /// \endcode |
| 298 | BranchInst *getLoopGuardBranch() const; |
| 299 | |
| 300 | /// Return true iff the loop is |
| 301 | /// - in simplify rotated form, and |
| 302 | /// - guarded by a loop guard branch. |
| 303 | bool isGuarded() const { return (getLoopGuardBranch() != nullptr); } |
| 304 | |
| 305 | /// Return true if the loop is in rotated form. |
| 306 | /// |
| 307 | /// This does not check if the loop was rotated by loop rotation, instead it |
| 308 | /// only checks if the loop is in rotated form (has a valid latch that exists |
| 309 | /// the loop). |
| 310 | bool isRotatedForm() const { |
| 311 | assert(!isInvalid() && "Loop not in a valid state!"); |
| 312 | BasicBlock *Latch = getLoopLatch(); |
| 313 | return Latch && isLoopExiting(Latch); |
| 314 | } |
| 315 | |
| 316 | /// Return true if the loop induction variable starts at zero and increments |
| 317 | /// by one each time through the loop. |
| 318 | bool isCanonical(ScalarEvolution &SE) const; |
| 319 | |
| 320 | /// Return true if the Loop is in LCSSA form. If \p IgnoreTokens is set to |
| 321 | /// true, token values defined inside loop are allowed to violate LCSSA form. |
| 322 | bool isLCSSAForm(const DominatorTree &DT, bool IgnoreTokens = true) const; |
| 323 | |
| 324 | /// Return true if this Loop and all inner subloops are in LCSSA form. If \p |
| 325 | /// IgnoreTokens is set to true, token values defined inside loop are allowed |
| 326 | /// to violate LCSSA form. |
| 327 | bool isRecursivelyLCSSAForm(const DominatorTree &DT, const LoopInfo &LI, |
| 328 | bool IgnoreTokens = true) const; |
| 329 | |
| 330 | /// Return true if the Loop is in the form that the LoopSimplify form |
| 331 | /// transforms loops to, which is sometimes called normal form. |
| 332 | bool isLoopSimplifyForm() const; |
| 333 | |
| 334 | /// Return true if the loop body is safe to clone in practice. |
| 335 | bool isSafeToClone() const; |
| 336 | |
| 337 | /// Returns true if the loop is annotated parallel. |
| 338 | /// |
| 339 | /// A parallel loop can be assumed to not contain any dependencies between |
| 340 | /// iterations by the compiler. That is, any loop-carried dependency checking |
| 341 | /// can be skipped completely when parallelizing the loop on the target |
| 342 | /// machine. Thus, if the parallel loop information originates from the |
| 343 | /// programmer, e.g. via the OpenMP parallel for pragma, it is the |
| 344 | /// programmer's responsibility to ensure there are no loop-carried |
| 345 | /// dependencies. The final execution order of the instructions across |
| 346 | /// iterations is not guaranteed, thus, the end result might or might not |
| 347 | /// implement actual concurrent execution of instructions across multiple |
| 348 | /// iterations. |
| 349 | bool isAnnotatedParallel() const; |
| 350 | |
| 351 | /// Return the llvm.loop loop id metadata node for this loop if it is present. |
| 352 | /// |
| 353 | /// If this loop contains the same llvm.loop metadata on each branch to the |
| 354 | /// header then the node is returned. If any latch instruction does not |
| 355 | /// contain llvm.loop or if multiple latches contain different nodes then |
| 356 | /// 0 is returned. |
| 357 | MDNode *getLoopID() const; |
| 358 | /// Set the llvm.loop loop id metadata for this loop. |
| 359 | /// |
| 360 | /// The LoopID metadata node will be added to each terminator instruction in |
| 361 | /// the loop that branches to the loop header. |
| 362 | /// |
| 363 | /// The LoopID metadata node should have one or more operands and the first |
| 364 | /// operand should be the node itself. |
| 365 | void setLoopID(MDNode *LoopID) const; |
| 366 | |
| 367 | /// Add llvm.loop.unroll.disable to this loop's loop id metadata. |
| 368 | /// |
| 369 | /// Remove existing unroll metadata and add unroll disable metadata to |
| 370 | /// indicate the loop has already been unrolled. This prevents a loop |
| 371 | /// from being unrolled more than is directed by a pragma if the loop |
| 372 | /// unrolling pass is run more than once (which it generally is). |
| 373 | void setLoopAlreadyUnrolled(); |
| 374 | |
| 375 | /// Add llvm.loop.mustprogress to this loop's loop id metadata. |
| 376 | void setLoopMustProgress(); |
| 377 | |
| 378 | void dump() const; |
| 379 | void dumpVerbose() const; |
| 380 | |
| 381 | /// Return the debug location of the start of this loop. |
| 382 | /// This looks for a BB terminating instruction with a known debug |
| 383 | /// location by looking at the preheader and header blocks. If it |
| 384 | /// cannot find a terminating instruction with location information, |
| 385 | /// it returns an unknown location. |
| 386 | DebugLoc getStartLoc() const; |
| 387 | |
| 388 | /// Return the source code span of the loop. |
| 389 | LocRange getLocRange() const; |
| 390 | |
| 391 | StringRef getName() const { |
| 392 | if (BasicBlock *Header = getHeader()) |
| 393 | if (Header->hasName()) |
| 394 | return Header->getName(); |
| 395 | return "<unnamed loop>"; |
| 396 | } |
| 397 | |
| 398 | private: |
| 399 | Loop() = default; |
| 400 | |
| 401 | friend class LoopInfoBase<BasicBlock, Loop>; |
| 402 | friend class LoopBase<BasicBlock, Loop>; |
| 403 | explicit Loop(BasicBlock *BB) : LoopBase<BasicBlock, Loop>(BB) {} |
| 404 | ~Loop() = default; |
| 405 | }; |
| 406 | |
| 407 | // Implementation in Support/GenericLoopInfoImpl.h |
| 408 | extern template class LoopInfoBase<BasicBlock, Loop>; |
| 409 | |
| 410 | class LoopInfo : public LoopInfoBase<BasicBlock, Loop> { |
| 411 | typedef LoopInfoBase<BasicBlock, Loop> BaseT; |
| 412 | |
| 413 | friend class LoopBase<BasicBlock, Loop>; |
| 414 | |
| 415 | void operator=(const LoopInfo &) = delete; |
| 416 | LoopInfo(const LoopInfo &) = delete; |
| 417 | |
| 418 | public: |
| 419 | LoopInfo() = default; |
| 420 | explicit LoopInfo(const DominatorTreeBase<BasicBlock, false> &DomTree); |
| 421 | |
| 422 | LoopInfo(LoopInfo &&Arg) : BaseT(std::move(static_cast<BaseT &>(Arg))) {} |
| 423 | LoopInfo &operator=(LoopInfo &&RHS) { |
| 424 | BaseT::operator=(std::move(static_cast<BaseT &>(RHS))); |
| 425 | return *this; |
| 426 | } |
| 427 | |
| 428 | /// Handle invalidation explicitly. |
| 429 | bool invalidate(Function &F, const PreservedAnalyses &PA, |
| 430 | FunctionAnalysisManager::Invalidator &); |
| 431 | |
| 432 | // Most of the public interface is provided via LoopInfoBase. |
| 433 | |
| 434 | /// Update LoopInfo after removing the last backedge from a loop. This updates |
| 435 | /// the loop forest and parent loops for each block so that \c L is no longer |
| 436 | /// referenced, but does not actually delete \c L immediately. The pointer |
| 437 | /// will remain valid until this LoopInfo's memory is released. |
| 438 | void erase(Loop *L); |
| 439 | |
| 440 | /// Returns true if replacing From with To everywhere is guaranteed to |
| 441 | /// preserve LCSSA form. |
| 442 | bool replacementPreservesLCSSAForm(Instruction *From, Value *To) { |
| 443 | // Preserving LCSSA form is only problematic if the replacing value is an |
| 444 | // instruction. |
| 445 | Instruction *I = dyn_cast<Instruction>(To); |
| 446 | if (!I) |
| 447 | return true; |
| 448 | // If both instructions are defined in the same basic block then replacement |
| 449 | // cannot break LCSSA form. |
| 450 | if (I->getParent() == From->getParent()) |
| 451 | return true; |
| 452 | // If the instruction is not defined in a loop then it can safely replace |
| 453 | // anything. |
| 454 | Loop *ToLoop = getLoopFor(I->getParent()); |
| 455 | if (!ToLoop) |
| 456 | return true; |
| 457 | // If the replacing instruction is defined in the same loop as the original |
| 458 | // instruction, or in a loop that contains it as an inner loop, then using |
| 459 | // it as a replacement will not break LCSSA form. |
| 460 | return ToLoop->contains(getLoopFor(From->getParent())); |
| 461 | } |
| 462 | |
| 463 | /// Checks if moving a specific instruction can break LCSSA in any loop. |
| 464 | /// |
| 465 | /// Return true if moving \p Inst to before \p NewLoc will break LCSSA, |
| 466 | /// assuming that the function containing \p Inst and \p NewLoc is currently |
| 467 | /// in LCSSA form. |
| 468 | bool movementPreservesLCSSAForm(Instruction *Inst, Instruction *NewLoc) { |
| 469 | assert(Inst->getFunction() == NewLoc->getFunction() && |
| 470 | "Can't reason about IPO!"); |
| 471 | |
| 472 | auto *OldBB = Inst->getParent(); |
| 473 | auto *NewBB = NewLoc->getParent(); |
| 474 | |
| 475 | // Movement within the same loop does not break LCSSA (the equality check is |
| 476 | // to avoid doing a hashtable lookup in case of intra-block movement). |
| 477 | if (OldBB == NewBB) |
| 478 | return true; |
| 479 | |
| 480 | auto *OldLoop = getLoopFor(OldBB); |
| 481 | auto *NewLoop = getLoopFor(NewBB); |
| 482 | |
| 483 | if (OldLoop == NewLoop) |
| 484 | return true; |
| 485 | |
| 486 | // Check if Outer contains Inner; with the null loop counting as the |
| 487 | // "outermost" loop. |
| 488 | auto Contains = [](const Loop *Outer, const Loop *Inner) { |
| 489 | return !Outer || Outer->contains(Inner); |
| 490 | }; |
| 491 | |
| 492 | // To check that the movement of Inst to before NewLoc does not break LCSSA, |
| 493 | // we need to check two sets of uses for possible LCSSA violations at |
| 494 | // NewLoc: the users of NewInst, and the operands of NewInst. |
| 495 | |
| 496 | // If we know we're hoisting Inst out of an inner loop to an outer loop, |
| 497 | // then the uses *of* Inst don't need to be checked. |
| 498 | |
| 499 | if (!Contains(NewLoop, OldLoop)) { |
| 500 | for (Use &U : Inst->uses()) { |
| 501 | auto *UI = cast<Instruction>(U.getUser()); |
| 502 | auto *UBB = isa<PHINode>(UI) ? cast<PHINode>(UI)->getIncomingBlock(U) |
| 503 | : UI->getParent(); |
| 504 | if (UBB != NewBB && getLoopFor(UBB) != NewLoop) |
| 505 | return false; |
| 506 | } |
| 507 | } |
| 508 | |
| 509 | // If we know we're sinking Inst from an outer loop into an inner loop, then |
| 510 | // the *operands* of Inst don't need to be checked. |
| 511 | |
| 512 | if (!Contains(OldLoop, NewLoop)) { |
| 513 | // See below on why we can't handle phi nodes here. |
| 514 | if (isa<PHINode>(Inst)) |
| 515 | return false; |
| 516 | |
| 517 | for (Use &U : Inst->operands()) { |
| 518 | auto *DefI = dyn_cast<Instruction>(U.get()); |
| 519 | if (!DefI) |
| 520 | return false; |
| 521 | |
| 522 | // This would need adjustment if we allow Inst to be a phi node -- the |
| 523 | // new use block won't simply be NewBB. |
| 524 | |
| 525 | auto *DefBlock = DefI->getParent(); |
| 526 | if (DefBlock != NewBB && getLoopFor(DefBlock) != NewLoop) |
| 527 | return false; |
| 528 | } |
| 529 | } |
| 530 | |
| 531 | return true; |
| 532 | } |
| 533 | |
| 534 | // Return true if a new use of V added in ExitBB would require an LCSSA PHI |
| 535 | // to be inserted at the begining of the block. Note that V is assumed to |
| 536 | // dominate ExitBB, and ExitBB must be the exit block of some loop. The |
| 537 | // IR is assumed to be in LCSSA form before the planned insertion. |
| 538 | bool wouldBeOutOfLoopUseRequiringLCSSA(const Value *V, |
| 539 | const BasicBlock *ExitBB) const; |
| 540 | }; |
| 541 | |
| 542 | /// Enable verification of loop info. |
| 543 | /// |
| 544 | /// The flag enables checks which are expensive and are disabled by default |
| 545 | /// unless the `EXPENSIVE_CHECKS` macro is defined. The `-verify-loop-info` |
| 546 | /// flag allows the checks to be enabled selectively without re-compilation. |
| 547 | extern bool VerifyLoopInfo; |
| 548 | |
| 549 | // Allow clients to walk the list of nested loops... |
| 550 | template <> struct GraphTraits<const Loop *> { |
| 551 | typedef const Loop *NodeRef; |
| 552 | typedef LoopInfo::iterator ChildIteratorType; |
| 553 | |
| 554 | static NodeRef getEntryNode(const Loop *L) { return L; } |
| 555 | static ChildIteratorType child_begin(NodeRef N) { return N->begin(); } |
| 556 | static ChildIteratorType child_end(NodeRef N) { return N->end(); } |
| 557 | }; |
| 558 | |
| 559 | template <> struct GraphTraits<Loop *> { |
| 560 | typedef Loop *NodeRef; |
| 561 | typedef LoopInfo::iterator ChildIteratorType; |
| 562 | |
| 563 | static NodeRef getEntryNode(Loop *L) { return L; } |
| 564 | static ChildIteratorType child_begin(NodeRef N) { return N->begin(); } |
| 565 | static ChildIteratorType child_end(NodeRef N) { return N->end(); } |
| 566 | }; |
| 567 | |
| 568 | /// Analysis pass that exposes the \c LoopInfo for a function. |
| 569 | class LoopAnalysis : public AnalysisInfoMixin<LoopAnalysis> { |
| 570 | friend AnalysisInfoMixin<LoopAnalysis>; |
| 571 | static AnalysisKey Key; |
| 572 | |
| 573 | public: |
| 574 | typedef LoopInfo Result; |
| 575 | |
| 576 | LoopInfo run(Function &F, FunctionAnalysisManager &AM); |
| 577 | }; |
| 578 | |
| 579 | /// Printer pass for the \c LoopAnalysis results. |
| 580 | class LoopPrinterPass : public PassInfoMixin<LoopPrinterPass> { |
| 581 | raw_ostream &OS; |
| 582 | |
| 583 | public: |
| 584 | explicit LoopPrinterPass(raw_ostream &OS) : OS(OS) {} |
| 585 | PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); |
| 586 | }; |
| 587 | |
| 588 | /// Verifier pass for the \c LoopAnalysis results. |
| 589 | struct LoopVerifierPass : public PassInfoMixin<LoopVerifierPass> { |
| 590 | PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); |
| 591 | }; |
| 592 | |
| 593 | /// The legacy pass manager's analysis pass to compute loop information. |
| 594 | class LoopInfoWrapperPass : public FunctionPass { |
| 595 | LoopInfo LI; |
| 596 | |
| 597 | public: |
| 598 | static char ID; // Pass identification, replacement for typeid |
| 599 | |
| 600 | LoopInfoWrapperPass(); |
| 601 | |
| 602 | LoopInfo &getLoopInfo() { return LI; } |
| 603 | const LoopInfo &getLoopInfo() const { return LI; } |
| 604 | |
| 605 | /// Calculate the natural loop information for a given function. |
| 606 | bool runOnFunction(Function &F) override; |
| 607 | |
| 608 | void verifyAnalysis() const override; |
| 609 | |
| 610 | void releaseMemory() override { LI.releaseMemory(); } |
| 611 | |
| 612 | void print(raw_ostream &O, const Module *M = nullptr) const override; |
| 613 | |
| 614 | void getAnalysisUsage(AnalysisUsage &AU) const override; |
| 615 | }; |
| 616 | |
| 617 | /// Function to print a loop's contents as LLVM's text IR assembly. |
| 618 | void printLoop(Loop &L, raw_ostream &OS, const std::string &Banner = ""); |
| 619 | |
| 620 | /// Find and return the loop attribute node for the attribute @p Name in |
| 621 | /// @p LoopID. Return nullptr if there is no such attribute. |
| 622 | MDNode *findOptionMDForLoopID(MDNode *LoopID, StringRef Name); |
| 623 | |
| 624 | /// Find string metadata for a loop. |
| 625 | /// |
| 626 | /// Returns the MDNode where the first operand is the metadata's name. The |
| 627 | /// following operands are the metadata's values. If no metadata with @p Name is |
| 628 | /// found, return nullptr. |
| 629 | MDNode *findOptionMDForLoop(const Loop *TheLoop, StringRef Name); |
| 630 | |
| 631 | std::optional<bool> getOptionalBoolLoopAttribute(const Loop *TheLoop, |
| 632 | StringRef Name); |
| 633 | |
| 634 | /// Returns true if Name is applied to TheLoop and enabled. |
| 635 | bool getBooleanLoopAttribute(const Loop *TheLoop, StringRef Name); |
| 636 | |
| 637 | /// Find named metadata for a loop with an integer value. |
| 638 | std::optional<int> getOptionalIntLoopAttribute(const Loop *TheLoop, |
| 639 | StringRef Name); |
| 640 | |
| 641 | /// Find named metadata for a loop with an integer value. Return \p Default if |
| 642 | /// not set. |
| 643 | int getIntLoopAttribute(const Loop *TheLoop, StringRef Name, int Default = 0); |
| 644 | |
| 645 | /// Find string metadata for loop |
| 646 | /// |
| 647 | /// If it has a value (e.g. {"llvm.distribute", 1} return the value as an |
| 648 | /// operand or null otherwise. If the string metadata is not found return |
| 649 | /// Optional's not-a-value. |
| 650 | std::optional<const MDOperand *> findStringMetadataForLoop(const Loop *TheLoop, |
| 651 | StringRef Name); |
| 652 | |
| 653 | /// Look for the loop attribute that requires progress within the loop. |
| 654 | /// Note: Most consumers probably want "isMustProgress" which checks |
| 655 | /// the containing function attribute too. |
| 656 | bool hasMustProgress(const Loop *L); |
| 657 | |
| 658 | /// Return true if this loop can be assumed to make progress. (i.e. can't |
| 659 | /// be infinite without side effects without also being undefined) |
| 660 | bool isMustProgress(const Loop *L); |
| 661 | |
| 662 | /// Return true if this loop can be assumed to run for a finite number of |
| 663 | /// iterations. |
| 664 | bool isFinite(const Loop *L); |
| 665 | |
| 666 | /// Return whether an MDNode might represent an access group. |
| 667 | /// |
| 668 | /// Access group metadata nodes have to be distinct and empty. Being |
| 669 | /// always-empty ensures that it never needs to be changed (which -- because |
| 670 | /// MDNodes are designed immutable -- would require creating a new MDNode). Note |
| 671 | /// that this is not a sufficient condition: not every distinct and empty NDNode |
| 672 | /// is representing an access group. |
| 673 | bool isValidAsAccessGroup(MDNode *AccGroup); |
| 674 | |
| 675 | /// Create a new LoopID after the loop has been transformed. |
| 676 | /// |
| 677 | /// This can be used when no follow-up loop attributes are defined |
| 678 | /// (llvm::makeFollowupLoopID returning None) to stop transformations to be |
| 679 | /// applied again. |
| 680 | /// |
| 681 | /// @param Context The LLVMContext in which to create the new LoopID. |
| 682 | /// @param OrigLoopID The original LoopID; can be nullptr if the original |
| 683 | /// loop has no LoopID. |
| 684 | /// @param RemovePrefixes Remove all loop attributes that have these prefixes. |
| 685 | /// Use to remove metadata of the transformation that has |
| 686 | /// been applied. |
| 687 | /// @param AddAttrs Add these loop attributes to the new LoopID. |
| 688 | /// |
| 689 | /// @return A new LoopID that can be applied using Loop::setLoopID(). |
| 690 | llvm::MDNode * |
| 691 | makePostTransformationMetadata(llvm::LLVMContext &Context, MDNode *OrigLoopID, |
| 692 | llvm::ArrayRef<llvm::StringRef> RemovePrefixes, |
| 693 | llvm::ArrayRef<llvm::MDNode *> AddAttrs); |
| 694 | |
| 695 | } // namespace llvm |
| 696 | |
| 697 | #endif |