Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

//===- llvm/Transforms/Utils/LoopUtils.h - Loop utilities -------*- C++ -*-===//

//

// 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 some loop transformation utilities.

//

//===----------------------------------------------------------------------===//

#ifndef LLVM_TRANSFORMS_UTILS_LOOPUTILS_H

#define LLVM_TRANSFORMS_UTILS_LOOPUTILS_H

#include "llvm/Analysis/IVDescriptors.h"

#include "llvm/Analysis/LoopAccessAnalysis.h"

#include "llvm/Transforms/Utils/ValueMapper.h"

namespace llvm {

template <typename T> class DomTreeNodeBase;

using DomTreeNode = DomTreeNodeBase<BasicBlock>;

class AssumptionCache;

class StringRef;

class AnalysisUsage;

class TargetTransformInfo;

class AAResults;

class BasicBlock;

class ICFLoopSafetyInfo;

class IRBuilderBase;

class Loop;

class LoopInfo;

class MemoryAccess;

class MemorySSA;

class MemorySSAUpdater;

class OptimizationRemarkEmitter;

class PredIteratorCache;

class ScalarEvolution;

class SCEV;

class SCEVExpander;

class TargetLibraryInfo;

class LPPassManager;

class Instruction;

struct RuntimeCheckingPtrGroup;

typedef std::pair<const RuntimeCheckingPtrGroup *,

                  const RuntimeCheckingPtrGroup *>

    RuntimePointerCheck;

template <typename T, unsigned N> class SmallSetVector;

template <typename T, unsigned N> class SmallPriorityWorklist;

BasicBlock *InsertPreheaderForLoop(Loop *L, DominatorTree *DT, LoopInfo *LI,

                                   MemorySSAUpdater *MSSAU, bool PreserveLCSSA);

/// Ensure that all exit blocks of the loop are dedicated exits.

///

/// For any loop exit block with non-loop predecessors, we split the loop

/// predecessors to use a dedicated loop exit block. We update the dominator

/// tree and loop info if provided, and will preserve LCSSA if requested.

bool formDedicatedExitBlocks(Loop *L, DominatorTree *DT, LoopInfo *LI,

                             MemorySSAUpdater *MSSAU, bool PreserveLCSSA);

/// Ensures LCSSA form for every instruction from the Worklist in the scope of

/// innermost containing loop.

///

/// For the given instruction which have uses outside of the loop, an LCSSA PHI

/// node is inserted and the uses outside the loop are rewritten to use this

/// node.

///

/// LoopInfo and DominatorTree are required and, since the routine makes no

/// changes to CFG, preserved.

///

/// Returns true if any modifications are made.

///

/// This function may introduce unused PHI nodes. If \p PHIsToRemove is not

/// nullptr, those are added to it (before removing, the caller has to check if

/// they still do not have any uses). Otherwise the PHIs are directly removed.

bool formLCSSAForInstructions(

    SmallVectorImpl<Instruction *> &Worklist, const DominatorTree &DT,

    const LoopInfo &LI, ScalarEvolution *SE, IRBuilderBase &Builder,

    SmallVectorImpl<PHINode *> *PHIsToRemove = nullptr);

/// Put loop into LCSSA form.

///

/// Looks at all instructions in the loop which have uses outside of the

/// current loop. For each, an LCSSA PHI node is inserted and the uses outside

/// the loop are rewritten to use this node. Sub-loops must be in LCSSA form

/// already.

///

/// LoopInfo and DominatorTree are required and preserved.

///

/// If ScalarEvolution is passed in, it will be preserved.

///

/// Returns true if any modifications are made to the loop.

bool formLCSSA(Loop &L, const DominatorTree &DT, const LoopInfo *LI,

               ScalarEvolution *SE);

/// Put a loop nest into LCSSA form.

///

/// This recursively forms LCSSA for a loop nest.

///

/// LoopInfo and DominatorTree are required and preserved.

///

/// If ScalarEvolution is passed in, it will be preserved.

///

/// Returns true if any modifications are made to the loop.

bool formLCSSARecursively(Loop &L, const DominatorTree &DT, const LoopInfo *LI,

                          ScalarEvolution *SE);

/// Flags controlling how much is checked when sinking or hoisting

/// instructions.  The number of memory access in the loop (and whether there

/// are too many) is determined in the constructors when using MemorySSA.

class SinkAndHoistLICMFlags {

public:

  // Explicitly set limits.

  SinkAndHoistLICMFlags(unsigned LicmMssaOptCap,

                        unsigned LicmMssaNoAccForPromotionCap, bool IsSink,

                        Loop *L = nullptr, MemorySSA *MSSA = nullptr);

  // Use default limits.

  SinkAndHoistLICMFlags(bool IsSink, Loop *L = nullptr,

                        MemorySSA *MSSA = nullptr);

  void setIsSink(bool B) { IsSink = B; }

  bool getIsSink() { return IsSink; }

  bool tooManyMemoryAccesses() { return NoOfMemAccTooLarge; }

  bool tooManyClobberingCalls() { return LicmMssaOptCounter >= LicmMssaOptCap; }

  void incrementClobberingCalls() { ++LicmMssaOptCounter; }

protected:

  bool NoOfMemAccTooLarge = false;

  unsigned LicmMssaOptCounter = 0;

  unsigned LicmMssaOptCap;

  unsigned LicmMssaNoAccForPromotionCap;

  bool IsSink;

};

/// Walk the specified region of the CFG (defined by all blocks

/// dominated by the specified block, and that are in the current loop) in

/// reverse depth first order w.r.t the DominatorTree. This allows us to visit

/// uses before definitions, allowing us to sink a loop body in one pass without

/// iteration. Takes DomTreeNode, AAResults, LoopInfo, DominatorTree,

/// TargetLibraryInfo, Loop, AliasSet information for all

/// instructions of the loop and loop safety information as

/// arguments. Diagnostics is emitted via \p ORE. It returns changed status.

/// \p CurLoop is a loop to do sinking on. \p OutermostLoop is used only when

/// this function is called by \p sinkRegionForLoopNest.

bool sinkRegion(DomTreeNode *, AAResults *, LoopInfo *, DominatorTree *,

                TargetLibraryInfo *, TargetTransformInfo *, Loop *CurLoop,

                MemorySSAUpdater &, ICFLoopSafetyInfo *,

                SinkAndHoistLICMFlags &, OptimizationRemarkEmitter *,

                Loop *OutermostLoop = nullptr);

/// Call sinkRegion on loops contained within the specified loop

/// in order from innermost to outermost.

bool sinkRegionForLoopNest(DomTreeNode *, AAResults *, LoopInfo *,

                           DominatorTree *, TargetLibraryInfo *,

                           TargetTransformInfo *, Loop *, MemorySSAUpdater &,

                           ICFLoopSafetyInfo *, SinkAndHoistLICMFlags &,

                           OptimizationRemarkEmitter *);

/// Walk the specified region of the CFG (defined by all blocks

/// dominated by the specified block, and that are in the current loop) in depth

/// first order w.r.t the DominatorTree.  This allows us to visit definitions

/// before uses, allowing us to hoist a loop body in one pass without iteration.

/// Takes DomTreeNode, AAResults, LoopInfo, DominatorTree,

/// TargetLibraryInfo, Loop, AliasSet information for all

/// instructions of the loop and loop safety information as arguments.

/// Diagnostics is emitted via \p ORE. It returns changed status.

/// \p AllowSpeculation is whether values should be hoisted even if they are not

/// guaranteed to execute in the loop, but are safe to speculatively execute.

bool hoistRegion(DomTreeNode *, AAResults *, LoopInfo *, DominatorTree *,

                 AssumptionCache *, TargetLibraryInfo *, Loop *,

                 MemorySSAUpdater &, ScalarEvolution *, ICFLoopSafetyInfo *,

                 SinkAndHoistLICMFlags &, OptimizationRemarkEmitter *, bool,

                 bool AllowSpeculation);

/// This function deletes dead loops. The caller of this function needs to

/// guarantee that the loop is infact dead.

/// The function requires a bunch or prerequisites to be present:

///   - The loop needs to be in LCSSA form

///   - The loop needs to have a Preheader

///   - A unique dedicated exit block must exist

///

/// This also updates the relevant analysis information in \p DT, \p SE, \p LI

/// and \p MSSA if pointers to those are provided.

/// It also updates the loop PM if an updater struct is provided.

void deleteDeadLoop(Loop *L, DominatorTree *DT, ScalarEvolution *SE,

                    LoopInfo *LI, MemorySSA *MSSA = nullptr);

/// Remove the backedge of the specified loop.  Handles loop nests and general

/// loop structures subject to the precondition that the loop has no parent

/// loop and has a single latch block.  Preserves all listed analyses.

void breakLoopBackedge(Loop *L, DominatorTree &DT, ScalarEvolution &SE,

                       LoopInfo &LI, MemorySSA *MSSA);

/// Try to promote memory values to scalars by sinking stores out of

/// the loop and moving loads to before the loop.  We do this by looping over

/// the stores in the loop, looking for stores to Must pointers which are

/// loop invariant. It takes a set of must-alias values, Loop exit blocks

/// vector, loop exit blocks insertion point vector, PredIteratorCache,

/// LoopInfo, DominatorTree, Loop, AliasSet information for all instructions

/// of the loop and loop safety information as arguments.

/// Diagnostics is emitted via \p ORE. It returns changed status.

/// \p AllowSpeculation is whether values should be hoisted even if they are not

/// guaranteed to execute in the loop, but are safe to speculatively execute.

bool promoteLoopAccessesToScalars(

    const SmallSetVector<Value *, 8> &, SmallVectorImpl<BasicBlock *> &,

    SmallVectorImpl<Instruction *> &, SmallVectorImpl<MemoryAccess *> &,

    PredIteratorCache &, LoopInfo *, DominatorTree *, AssumptionCache *AC,

    const TargetLibraryInfo *, TargetTransformInfo *, Loop *,

    MemorySSAUpdater &, ICFLoopSafetyInfo *, OptimizationRemarkEmitter *,

    bool AllowSpeculation, bool HasReadsOutsideSet);

/// 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> collectChildrenInLoop(DomTreeNode *N,

                                                     const Loop *CurLoop);

/// Returns the instructions that use values defined in the loop.

SmallVector<Instruction *, 8> findDefsUsedOutsideOfLoop(Loop *L);

/// Find a combination of metadata ("llvm.loop.vectorize.width" and

/// "llvm.loop.vectorize.scalable.enable") for a loop and use it to construct a

/// ElementCount. If the metadata "llvm.loop.vectorize.width" cannot be found

/// then std::nullopt is returned.

std::optional<ElementCount>

getOptionalElementCountLoopAttribute(const Loop *TheLoop);

/// Create a new loop identifier for a loop created from a loop transformation.

///

/// @param OrigLoopID The loop ID of the loop before the transformation.

/// @param FollowupAttrs List of attribute names that contain attributes to be

///                      added to the new loop ID.

/// @param InheritOptionsAttrsPrefix Selects which attributes should be inherited

///                                  from the original loop. The following values

///                                  are considered:

///        nullptr   : Inherit all attributes from @p OrigLoopID.

///        ""        : Do not inherit any attribute from @p OrigLoopID; only use

///                    those specified by a followup attribute.

///        "<prefix>": Inherit all attributes except those which start with

///                    <prefix>; commonly used to remove metadata for the

///                    applied transformation.

/// @param AlwaysNew If true, do not try to reuse OrigLoopID and never return

///                  std::nullopt.

///

/// @return The loop ID for the after-transformation loop. The following values

///         can be returned:

///         std::nullopt : No followup attribute was found; it is up to the

///                        transformation to choose attributes that make sense.

///         @p OrigLoopID: The original identifier can be reused.

///         nullptr      : The new loop has no attributes.

///         MDNode*      : A new unique loop identifier.

std::optional<MDNode *>

makeFollowupLoopID(MDNode *OrigLoopID, ArrayRef<StringRef> FollowupAttrs,

                   const char *InheritOptionsAttrsPrefix = "",

                   bool AlwaysNew = false);

/// Look for the loop attribute that disables all transformation heuristic.

bool hasDisableAllTransformsHint(const Loop *L);

/// Look for the loop attribute that disables the LICM transformation heuristics.

bool hasDisableLICMTransformsHint(const Loop *L);

/// The mode sets how eager a transformation should be applied.

enum TransformationMode {

  /// The pass can use heuristics to determine whether a transformation should

  /// be applied.

  TM_Unspecified,

  /// The transformation should be applied without considering a cost model.

  TM_Enable,

  /// The transformation should not be applied.

  TM_Disable,

  /// Force is a flag and should not be used alone.

  TM_Force = 0x04,

  /// The transformation was directed by the user, e.g. by a #pragma in

  /// the source code. If the transformation could not be applied, a

  /// warning should be emitted.

  TM_ForcedByUser = TM_Enable | TM_Force,

  /// The transformation must not be applied. For instance, `#pragma clang loop

  /// unroll(disable)` explicitly forbids any unrolling to take place. Unlike

  /// general loop metadata, it must not be dropped. Most passes should not

  /// behave differently under TM_Disable and TM_SuppressedByUser.

  TM_SuppressedByUser = TM_Disable | TM_Force

};

/// @{

/// Get the mode for LLVM's supported loop transformations.

TransformationMode hasUnrollTransformation(const Loop *L);

TransformationMode hasUnrollAndJamTransformation(const Loop *L);

TransformationMode hasVectorizeTransformation(const Loop *L);

TransformationMode hasDistributeTransformation(const Loop *L);

TransformationMode hasLICMVersioningTransformation(const Loop *L);

/// @}

/// 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 addStringMetadataToLoop(Loop *TheLoop, const char *MDString,

                             unsigned V = 0);

/// Returns a loop's estimated trip count based on branch weight metadata.

/// In addition if \p EstimatedLoopInvocationWeight is not null it is

/// initialized with weight of loop's latch leading to the exit.

/// Returns 0 when the count is estimated to be 0, or std::nullopt when a

/// meaningful estimate can not be made.

std::optional<unsigned>

getLoopEstimatedTripCount(Loop *L,

                          unsigned *EstimatedLoopInvocationWeight = nullptr);

/// Set a loop's branch weight metadata to reflect that loop has \p

/// EstimatedTripCount iterations and \p EstimatedLoopInvocationWeight exits

/// through latch. Returns true if metadata is successfully updated, false

/// otherwise. Note that loop must have a latch block which controls loop exit

/// in order to succeed.

bool setLoopEstimatedTripCount(Loop *L, unsigned EstimatedTripCount,

                               unsigned EstimatedLoopInvocationWeight);

/// Check inner loop (L) backedge count is known to be invariant on all

/// iterations of its outer loop. If the loop has no parent, this is trivially

/// true.

bool hasIterationCountInvariantInParent(Loop *L, ScalarEvolution &SE);

/// Helper to consistently add the set of standard passes to a loop pass's \c

/// AnalysisUsage.

///

/// All loop passes should call this as part of implementing their \c

/// getAnalysisUsage.

void getLoopAnalysisUsage(AnalysisUsage &AU);

/// Returns true if is legal to hoist or sink this instruction disregarding the

/// possible introduction of faults.  Reasoning about potential faulting

/// instructions is the responsibility of the caller since it is challenging to

/// do efficiently from within this routine.

/// \p TargetExecutesOncePerLoop is true only when it is guaranteed that the

/// target executes at most once per execution of the loop body.  This is used

/// to assess the legality of duplicating atomic loads.  Generally, this is

/// true when moving out of loop and not true when moving into loops.

/// If \p ORE is set use it to emit optimization remarks.

bool canSinkOrHoistInst(Instruction &I, AAResults *AA, DominatorTree *DT,

                        Loop *CurLoop, MemorySSAUpdater &MSSAU,

                        bool TargetExecutesOncePerLoop,

                        SinkAndHoistLICMFlags &LICMFlags,

                        OptimizationRemarkEmitter *ORE = nullptr);

/// Returns the comparison predicate used when expanding a min/max reduction.

CmpInst::Predicate getMinMaxReductionPredicate(RecurKind RK);

/// See RecurrenceDescriptor::isSelectCmpPattern for a description of the

/// pattern we are trying to match. In this pattern we are only ever selecting

/// between two values: 1) an initial PHI start value, and 2) a loop invariant

/// value. This function uses \p LoopExitInst to determine 2), which we then use

/// to select between \p Left and \p Right. Any lane value in \p Left that

/// matches 2) will be merged into \p Right.

Value *createSelectCmpOp(IRBuilderBase &Builder, Value *StartVal, RecurKind RK,

                         Value *Left, Value *Right);

/// Returns a Min/Max operation corresponding to MinMaxRecurrenceKind.

/// The Builder's fast-math-flags must be set to propagate the expected values.

Value *createMinMaxOp(IRBuilderBase &Builder, RecurKind RK, Value *Left,

                      Value *Right);

/// Generates an ordered vector reduction using extracts to reduce the value.

Value *getOrderedReduction(IRBuilderBase &Builder, Value *Acc, Value *Src,

                           unsigned Op, RecurKind MinMaxKind = RecurKind::None);

/// Generates a vector reduction using shufflevectors to reduce the value.

/// Fast-math-flags are propagated using the IRBuilder's setting.

Value *getShuffleReduction(IRBuilderBase &Builder, Value *Src, unsigned Op,

                           RecurKind MinMaxKind = RecurKind::None);

/// Create a target reduction of the given vector. The reduction operation

/// is described by the \p Opcode parameter. min/max reductions require

/// additional information supplied in \p RdxKind.

/// The target is queried to determine if intrinsics or shuffle sequences are

/// required to implement the reduction.

/// Fast-math-flags are propagated using the IRBuilder's setting.

Value *createSimpleTargetReduction(IRBuilderBase &B,

                                   const TargetTransformInfo *TTI, Value *Src,

                                   RecurKind RdxKind);

/// Create a target reduction of the given vector \p Src for a reduction of the

/// kind RecurKind::SelectICmp or RecurKind::SelectFCmp. The reduction operation

/// is described by \p Desc.

Value *createSelectCmpTargetReduction(IRBuilderBase &B,

                                      const TargetTransformInfo *TTI,

                                      Value *Src,

                                      const RecurrenceDescriptor &Desc,

                                      PHINode *OrigPhi);

/// Create a generic target reduction using a recurrence descriptor \p Desc

/// The target is queried to determine if intrinsics or shuffle sequences are

/// required to implement the reduction.

/// Fast-math-flags are propagated using the RecurrenceDescriptor.

Value *createTargetReduction(IRBuilderBase &B, const TargetTransformInfo *TTI,

                             const RecurrenceDescriptor &Desc, Value *Src,

                             PHINode *OrigPhi = nullptr);

/// Create an ordered reduction intrinsic using the given recurrence

/// descriptor \p Desc.

Value *createOrderedReduction(IRBuilderBase &B,

                              const RecurrenceDescriptor &Desc, Value *Src,

                              Value *Start);

/// Get the intersection (logical and) of all of the potential IR flags

/// of each scalar operation (VL) that will be converted into a vector (I).

/// If OpValue is non-null, we only consider operations similar to OpValue

/// when intersecting.

/// Flag set: NSW, NUW (if IncludeWrapFlags is true), exact, and all of

/// fast-math.

void propagateIRFlags(Value *I, ArrayRef<Value *> VL, Value *OpValue = nullptr,

                      bool IncludeWrapFlags = true);

/// Returns true if we can prove that \p S is defined and always negative in

/// loop \p L.

bool isKnownNegativeInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE);

/// Returns true if we can prove that \p S is defined and always non-negative in

/// loop \p L.

bool isKnownNonNegativeInLoop(const SCEV *S, const Loop *L,

                              ScalarEvolution &SE);

/// Returns true if \p S is defined and never is equal to signed/unsigned max.

bool cannotBeMaxInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE,

                       bool Signed);

/// Returns true if \p S is defined and never is equal to signed/unsigned min.

bool cannotBeMinInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE,

                       bool Signed);

enum ReplaceExitVal {

  NeverRepl,

  OnlyCheapRepl,

  NoHardUse,

  UnusedIndVarInLoop,

  AlwaysRepl

};

/// If the final value of any expressions that are recurrent in the loop can

/// be computed, substitute the exit values from the loop into any instructions

/// outside of the loop that use the final values of the current expressions.

/// Return the number of loop exit values that have been replaced, and the

/// corresponding phi node will be added to DeadInsts.

int 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 and the following distribution of \p OrigLoop iteration among \p

/// UnrolledLoop and \p RemainderLoop. \p UnrolledLoop receives weights that

/// reflect TC/UF iterations, and \p RemainderLoop receives weights that reflect

/// the remaining TC%UF iterations.

///

/// Note that \p OrigLoop may be equal to either \p UnrolledLoop or \p

/// RemainderLoop in which case weights for \p OrigLoop are updated accordingly.

/// Note also behavior is undefined if \p UnrolledLoop and \p RemainderLoop are

/// equal. \p UF must be greater than zero.

/// If \p OrigLoop has no profile info associated nothing happens.

///

/// This utility may be useful for such optimizations as unroller and

/// vectorizer as it's typical transformation for them.

void setProfileInfoAfterUnrolling(Loop *OrigLoop, Loop *UnrolledLoop,

                                  Loop *RemainderLoop, uint64_t UF);

/// Utility that implements appending of loops onto a worklist given a range.

/// We want to process loops in postorder, but the worklist is a LIFO data

/// structure, so we append to it in *reverse* postorder.

/// For trees, a preorder traversal is a viable reverse postorder, so we

/// actually append using a preorder walk algorithm.

template <typename RangeT>

void appendLoopsToWorklist(RangeT &&, SmallPriorityWorklist<Loop *, 4> &);

/// Utility that implements appending of loops onto a worklist given a range.

/// It has the same behavior as appendLoopsToWorklist, but assumes the range of

/// loops has already been reversed, so it processes loops in the given order.

template <typename RangeT>

void appendReversedLoopsToWorklist(RangeT &&,

                                   SmallPriorityWorklist<Loop *, 4> &);

/// Utility that implements appending of loops onto a worklist given LoopInfo.

/// Calls the templated utility taking a Range of loops, handing it the Loops

/// in LoopInfo, iterated in reverse. This is because the loops are stored in

/// RPO w.r.t. the control flow graph in LoopInfo. For the purpose of unrolling,

/// loop deletion, and LICM, we largely want to work forward across the CFG so

/// that we visit defs before uses and can propagate simplifications from one

/// loop nest into the next. Calls appendReversedLoopsToWorklist with the

/// already reversed loops in LI.

/// FIXME: Consider changing the order in LoopInfo.

void appendLoopsToWorklist(LoopInfo &, SmallPriorityWorklist<Loop *, 4> &);

/// Recursively clone the specified loop and all of its children,

/// mapping the blocks with the specified map.

Loop *cloneLoop(Loop *L, Loop *PL, ValueToValueMapTy &VM,

                LoopInfo *LI, LPPassManager *LPM);

/// Add code that checks at runtime if the accessed arrays in \p PointerChecks

/// overlap. Returns the final comparator value or NULL if no check is needed.

Value *

addRuntimeChecks(Instruction *Loc, Loop *TheLoop,

                 const SmallVectorImpl<RuntimePointerCheck> &PointerChecks,

                 SCEVExpander &Expander);

Value *addDiffRuntimeChecks(

    Instruction *Loc, ArrayRef<PointerDiffInfo> Checks, SCEVExpander &Expander,

    function_ref<Value *(IRBuilderBase &, unsigned)> GetVF, unsigned IC);

/// Struct to hold information about a partially invariant condition.

struct IVConditionInfo {

  /// Instructions that need to be duplicated and checked for the unswitching

  /// condition.

  SmallVector<Instruction *> InstToDuplicate;

  /// Constant to indicate for which value the condition is invariant.

  Constant *KnownValue = nullptr;

  /// True if the partially invariant path is no-op (=does not have any

  /// side-effects and no loop value is used outside the loop).

  bool PathIsNoop = true;

  /// If the partially invariant path reaches a single exit block, ExitForPath

  /// is set to that block. Otherwise it is nullptr.

  BasicBlock *ExitForPath = nullptr;

};

/// Check if the loop header has a conditional branch that is not

/// loop-invariant, because it involves load instructions. If all paths from

/// either the true or false successor to the header or loop exists do not

/// modify the memory feeding the condition, perform 'partial unswitching'. That

/// is, duplicate the instructions feeding the condition in the pre-header. Then

/// unswitch on the duplicated condition. The condition is now known in the

/// unswitched version for the 'invariant' path through the original loop.

///

/// If the branch condition of the header is partially invariant, return a pair

/// containing the instructions to duplicate and a boolean Constant to update

/// the condition in the loops created for the true or false successors.

std::optional<IVConditionInfo> hasPartialIVCondition(const Loop &L,

                                                     unsigned MSSAThreshold,

                                                     const MemorySSA &MSSA,

                                                     AAResults &AA);

} // end namespace llvm

#endif // LLVM_TRANSFORMS_UTILS_LOOPUTILS_H