LoopUtils.cpp | Explore in Territory

//===-- LoopUtils.cpp - Loop Utility functions -------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This file defines common loop utility functions.
//
//===----------------------------------------------------------------------===//

#include "llvm/Transforms/Utils/LoopUtils.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/PriorityWorklist.h"
#include "llvm/ADT/ScopeExit.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/BasicAliasAnalysis.h"
#include "llvm/Analysis/DomTreeUpdater.h"
#include "llvm/Analysis/GlobalsModRef.h"
#include "llvm/Analysis/InstSimplifyFolder.h"
#include "llvm/Analysis/LoopAccessAnalysis.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/Analysis/MemorySSA.h"
#include "llvm/Analysis/MemorySSAUpdater.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/IR/DIBuilder.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/MDBuilder.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/IR/ProfDataUtils.h"
#include "llvm/IR/ValueHandle.h"
#include "llvm/InitializePasses.h"
#include "llvm/Pass.h"
#include "llvm/Support/Debug.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"

usingnamespacellvm;
usingnamespacellvm::PatternMatch;

#define DEBUG_TYPE …

static const char *LLVMLoopDisableNonforced = …;
static const char *LLVMLoopDisableLICM = …;

bool llvm::formDedicatedExitBlocks(Loop *L, DominatorTree *DT, LoopInfo *LI,
                                   MemorySSAUpdater *MSSAU,
                                   bool PreserveLCSSA) { … }

/// Returns the instructions that use values defined in the loop.
SmallVector<Instruction *, 8> llvm::findDefsUsedOutsideOfLoop(Loop *L) { … }

void llvm::getLoopAnalysisUsage(AnalysisUsage &AU) { … }

/// Manually defined generic "LoopPass" dependency initialization. This is used
/// to initialize the exact set of passes from above in \c
/// getLoopAnalysisUsage. It can be used within a loop pass's initialization
/// with:
///
///   INITIALIZE_PASS_DEPENDENCY(LoopPass)
///
/// As-if "LoopPass" were a pass.
void llvm::initializeLoopPassPass(PassRegistry &Registry) { … }

/// Create MDNode for input string.
static MDNode *createStringMetadata(Loop *TheLoop, StringRef Name, unsigned V) { … }

/// Set input string into loop metadata by keeping other values intact.
/// If the string is already in loop metadata update value if it is
/// different.
void llvm::addStringMetadataToLoop(Loop *TheLoop, const char *StringMD,
                                   unsigned V) { … }

std::optional<ElementCount>
llvm::getOptionalElementCountLoopAttribute(const Loop *TheLoop) { … }

std::optional<MDNode *> llvm::makeFollowupLoopID(
    MDNode *OrigLoopID, ArrayRef<StringRef> FollowupOptions,
    const char *InheritOptionsExceptPrefix, bool AlwaysNew) { … }

bool llvm::hasDisableAllTransformsHint(const Loop *L) { … }

bool llvm::hasDisableLICMTransformsHint(const Loop *L) { … }

TransformationMode llvm::hasUnrollTransformation(const Loop *L) { … }

TransformationMode llvm::hasUnrollAndJamTransformation(const Loop *L) { … }

TransformationMode llvm::hasVectorizeTransformation(const Loop *L) { … }

TransformationMode llvm::hasDistributeTransformation(const Loop *L) { … }

TransformationMode llvm::hasLICMVersioningTransformation(const Loop *L) { … }

/// Does a BFS from a given node to all of its children inside a given loop.
/// The returned vector of nodes includes the starting point.
SmallVector<DomTreeNode *, 16>
llvm::collectChildrenInLoop(DomTreeNode *N, const Loop *CurLoop) { … }

bool llvm::isAlmostDeadIV(PHINode *PN, BasicBlock *LatchBlock, Value *Cond) { … }


void llvm::deleteDeadLoop(Loop *L, DominatorTree *DT, ScalarEvolution *SE,
                          LoopInfo *LI, MemorySSA *MSSA) { … }

void llvm::breakLoopBackedge(Loop *L, DominatorTree &DT, ScalarEvolution &SE,
                             LoopInfo &LI, MemorySSA *MSSA) { … }


/// Checks if \p L has an exiting latch branch.  There may also be other
/// exiting blocks.  Returns branch instruction terminating the loop
/// latch if above check is successful, nullptr otherwise.
static BranchInst *getExpectedExitLoopLatchBranch(Loop *L) { … }

/// Return the estimated trip count for any exiting branch which dominates
/// the loop latch.
static std::optional<uint64_t> getEstimatedTripCount(BranchInst *ExitingBranch,
                                                     Loop *L,
                                                     uint64_t &OrigExitWeight) { … }

std::optional<unsigned>
llvm::getLoopEstimatedTripCount(Loop *L,
                                unsigned *EstimatedLoopInvocationWeight) { … }

bool llvm::setLoopEstimatedTripCount(Loop *L, unsigned EstimatedTripCount,
                                     unsigned EstimatedloopInvocationWeight) { … }

bool llvm::hasIterationCountInvariantInParent(Loop *InnerLoop,
                                              ScalarEvolution &SE) { … }

constexpr Intrinsic::ID llvm::getReductionIntrinsicID(RecurKind RK) { … }

unsigned llvm::getArithmeticReductionInstruction(Intrinsic::ID RdxID) { … }

Intrinsic::ID llvm::getMinMaxReductionIntrinsicOp(Intrinsic::ID RdxID) { … }

Intrinsic::ID llvm::getMinMaxReductionIntrinsicOp(RecurKind RK) { … }

RecurKind llvm::getMinMaxReductionRecurKind(Intrinsic::ID RdxID) { … }

CmpInst::Predicate llvm::getMinMaxReductionPredicate(RecurKind RK) { … }

Value *llvm::createMinMaxOp(IRBuilderBase &Builder, RecurKind RK, Value *Left,
                            Value *Right) { … }

// Helper to generate an ordered reduction.
Value *llvm::getOrderedReduction(IRBuilderBase &Builder, Value *Acc, Value *Src,
                                 unsigned Op, RecurKind RdxKind) { … }

// Helper to generate a log2 shuffle reduction.
Value *llvm::getShuffleReduction(IRBuilderBase &Builder, Value *Src,
                                 unsigned Op,
                                 TargetTransformInfo::ReductionShuffle RS,
                                 RecurKind RdxKind) { … }

Value *llvm::createAnyOfReduction(IRBuilderBase &Builder, Value *Src,
                                  const RecurrenceDescriptor &Desc,
                                  PHINode *OrigPhi) { … }

Value *llvm::getReductionIdentity(Intrinsic::ID RdxID, Type *Ty,
                                  FastMathFlags Flags) { … }

Value *llvm::getRecurrenceIdentity(RecurKind K, Type *Tp, FastMathFlags FMF) { … }

Value *llvm::createSimpleReduction(IRBuilderBase &Builder, Value *Src,
                                   RecurKind RdxKind) { … }

Value *llvm::createSimpleReduction(VectorBuilder &VBuilder, Value *Src,
                                   const RecurrenceDescriptor &Desc) { … }

Value *llvm::createReduction(IRBuilderBase &B,
                             const RecurrenceDescriptor &Desc, Value *Src,
                             PHINode *OrigPhi) { … }

Value *llvm::createOrderedReduction(IRBuilderBase &B,
                                    const RecurrenceDescriptor &Desc,
                                    Value *Src, Value *Start) { … }

Value *llvm::createOrderedReduction(VectorBuilder &VBuilder,
                                    const RecurrenceDescriptor &Desc,
                                    Value *Src, Value *Start) { … }

void llvm::propagateIRFlags(Value *I, ArrayRef<Value *> VL, Value *OpValue,
                            bool IncludeWrapFlags) { … }

bool llvm::isKnownNegativeInLoop(const SCEV *S, const Loop *L,
                                 ScalarEvolution &SE) { … }

bool llvm::isKnownNonNegativeInLoop(const SCEV *S, const Loop *L,
                                    ScalarEvolution &SE) { … }

bool llvm::isKnownPositiveInLoop(const SCEV *S, const Loop *L,
                                 ScalarEvolution &SE) { … }

bool llvm::isKnownNonPositiveInLoop(const SCEV *S, const Loop *L,
                                    ScalarEvolution &SE) { … }

bool llvm::cannotBeMinInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE,
                             bool Signed) { … }

bool llvm::cannotBeMaxInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE,
                             bool Signed) { … }

//===----------------------------------------------------------------------===//
// rewriteLoopExitValues - Optimize IV users outside the loop.
// As a side effect, reduces the amount of IV processing within the loop.
//===----------------------------------------------------------------------===//

static bool hasHardUserWithinLoop(const Loop *L, const Instruction *I) { … }

// Collect information about PHI nodes which can be transformed in
// rewriteLoopExitValues.
struct RewritePhi { … };

// Check whether it is possible to delete the loop after rewriting exit
// value. If it is possible, ignore ReplaceExitValue and do rewriting
// aggressively.
static bool canLoopBeDeleted(Loop *L, SmallVector<RewritePhi, 8> &RewritePhiSet) { … }

/// Checks if it is safe to call InductionDescriptor::isInductionPHI for \p Phi,
/// and returns true if this Phi is an induction phi in the loop. When
/// isInductionPHI returns true, \p ID will be also be set by isInductionPHI.
static bool checkIsIndPhi(PHINode *Phi, Loop *L, ScalarEvolution *SE,
                          InductionDescriptor &ID) { … }

int llvm::rewriteLoopExitValues(Loop *L, LoopInfo *LI, TargetLibraryInfo *TLI,
                                ScalarEvolution *SE,
                                const TargetTransformInfo *TTI,
                                SCEVExpander &Rewriter, DominatorTree *DT,
                                ReplaceExitVal ReplaceExitValue,
                                SmallVector<WeakTrackingVH, 16> &DeadInsts) { … }

/// Set weights for \p UnrolledLoop and \p RemainderLoop based on weights for
/// \p OrigLoop.
void llvm::setProfileInfoAfterUnrolling(Loop *OrigLoop, Loop *UnrolledLoop,
                                        Loop *RemainderLoop, uint64_t UF) { … }

/// Utility that implements appending of loops onto a worklist.
/// Loops are added in preorder (analogous for reverse postorder for trees),
/// and the worklist is processed LIFO.
template <typename RangeT>
void llvm::appendReversedLoopsToWorklist(
    RangeT &&Loops, SmallPriorityWorklist<Loop *, 4> &Worklist) { … }

template <typename RangeT>
void llvm::appendLoopsToWorklist(RangeT &&Loops,
                                 SmallPriorityWorklist<Loop *, 4> &Worklist) { … }

template void llvm::appendLoopsToWorklist<ArrayRef<Loop *> &>(
    ArrayRef<Loop *> &Loops, SmallPriorityWorklist<Loop *, 4> &Worklist);

template void
llvm::appendLoopsToWorklist<Loop &>(Loop &L,
                                    SmallPriorityWorklist<Loop *, 4> &Worklist);

void llvm::appendLoopsToWorklist(LoopInfo &LI,
                                 SmallPriorityWorklist<Loop *, 4> &Worklist) { … }

Loop *llvm::cloneLoop(Loop *L, Loop *PL, ValueToValueMapTy &VM,
                      LoopInfo *LI, LPPassManager *LPM) { … }

/// IR Values for the lower and upper bounds of a pointer evolution.  We
/// need to use value-handles because SCEV expansion can invalidate previously
/// expanded values.  Thus expansion of a pointer can invalidate the bounds for
/// a previous one.
struct PointerBounds { … };

/// Expand code for the lower and upper bound of the pointer group \p CG
/// in \p TheLoop.  \return the values for the bounds.
static PointerBounds expandBounds(const RuntimeCheckingPtrGroup *CG,
                                  Loop *TheLoop, Instruction *Loc,
                                  SCEVExpander &Exp, bool HoistRuntimeChecks) { … }

/// Turns a collection of checks into a collection of expanded upper and
/// lower bounds for both pointers in the check.
static SmallVector<std::pair<PointerBounds, PointerBounds>, 4>
expandBounds(const SmallVectorImpl<RuntimePointerCheck> &PointerChecks, Loop *L,
             Instruction *Loc, SCEVExpander &Exp, bool HoistRuntimeChecks) { … }

Value *llvm::addRuntimeChecks(
    Instruction *Loc, Loop *TheLoop,
    const SmallVectorImpl<RuntimePointerCheck> &PointerChecks,
    SCEVExpander &Exp, bool HoistRuntimeChecks) { … }

Value *llvm::addDiffRuntimeChecks(
    Instruction *Loc, ArrayRef<PointerDiffInfo> Checks, SCEVExpander &Expander,
    function_ref<Value *(IRBuilderBase &, unsigned)> GetVF, unsigned IC) { … }

std::optional<IVConditionInfo>
llvm::hasPartialIVCondition(const Loop &L, unsigned MSSAThreshold,
                            const MemorySSA &MSSA, AAResults &AA) { … }
llvm/llvm/lib/Transforms/Utils/LoopUtils.cpp
