File Manager

003 File Manager

Current Path: /usr/src/contrib/llvm-project/llvm/include/llvm/Analysis

usr / src / contrib / llvm-project / llvm / include / llvm / Analysis /

📁 ..
📄 AliasAnalysis.h(51.98 KB)
📄 AliasAnalysisEvaluator.h(2.7 KB)
📄 AliasSetTracker.h(15.42 KB)
📄 AssumeBundleQueries.h(6.66 KB)
📄 AssumptionCache.h(8.39 KB)
📄 BasicAliasAnalysis.h(10.2 KB)
📄 BlockFrequencyInfo.h(5.59 KB)
📄 BlockFrequencyInfoImpl.h(56.46 KB)
📄 BranchProbabilityInfo.h(10.1 KB)
📄 CFG.h(7.76 KB)
📄 CFGPrinter.h(9.31 KB)
📄 CFLAliasAnalysisUtils.h(1.66 KB)
📄 CFLAndersAliasAnalysis.h(3.97 KB)
📄 CFLSteensAliasAnalysis.h(4.58 KB)
📄 CGSCCPassManager.h(41.2 KB)
📄 CallGraph.h(18.88 KB)
📄 CallGraphSCCPass.h(5.01 KB)
📄 CallPrinter.h(799 B)
📄 CaptureTracking.h(4.78 KB)
📄 CmpInstAnalysis.h(2.57 KB)
📄 CodeMetrics.h(3.15 KB)
📄 ConstantFolding.h(8.01 KB)
📄 DDG.h(19.15 KB)
📄 DOTGraphTraitsPass.h(5.5 KB)
📄 DemandedBits.h(4.07 KB)
📄 DependenceAnalysis.h(41.83 KB)
📄 DependenceGraphBuilder.h(7.74 KB)
📄 DivergenceAnalysis.h(7.38 KB)
📄 DomPrinter.h(1.04 KB)
📄 DomTreeUpdater.h(13.2 KB)
📄 DominanceFrontier.h(6.63 KB)
📄 DominanceFrontierImpl.h(7.12 KB)
📄 EHPersonalities.h(3.22 KB)
📄 GlobalsModRef.h(5.96 KB)
📄 GuardUtils.h(2.11 KB)
📄 HeatUtils.h(1.16 KB)
📄 IVDescriptors.h(14.56 KB)
📄 IVUsers.h(6.07 KB)
📄 IndirectCallPromotionAnalysis.h(2.61 KB)
📄 IndirectCallVisitor.h(1.16 KB)
📄 InlineAdvisor.h(8.71 KB)
📄 InlineCost.h(11.33 KB)
📄 InlineFeaturesAnalysis.h(1.5 KB)
📄 InlineModelFeatureMaps.h(3.41 KB)
📄 InlineSizeEstimatorAnalysis.h(1.07 KB)
📄 InstructionPrecedenceTracking.h(5.9 KB)
📄 InstructionSimplify.h(13.36 KB)
📄 Interval.h(4.84 KB)
📄 IntervalIterator.h(10.64 KB)
📄 IntervalPartition.h(4.05 KB)
📄 IteratedDominanceFrontier.h(2.62 KB)
📄 LazyBlockFrequencyInfo.h(4.34 KB)
📄 LazyBranchProbabilityInfo.h(4.21 KB)
📄 LazyCallGraph.h(50.13 KB)
📄 LazyValueInfo.h(5.4 KB)
📄 LegacyDivergenceAnalysis.h(2.53 KB)
📄 Lint.h(1.35 KB)
📄 Loads.h(7.86 KB)
📄 LoopAccessAnalysis.h(29.75 KB)
📄 LoopAnalysisManager.h(5.83 KB)
📄 LoopCacheAnalysis.h(11.91 KB)
📄 LoopInfo.h(48.27 KB)
📄 LoopInfoImpl.h(27.14 KB)
📄 LoopIterator.h(8.83 KB)
📄 LoopNestAnalysis.h(5.61 KB)
📄 LoopPass.h(4.29 KB)
📄 LoopUnrollAnalyzer.h(3.42 KB)
📄 MLInlineAdvisor.h(3.48 KB)
📄 MLModelRunner.h(1.16 KB)
📄 MemoryBuiltins.h(13.42 KB)
📄 MemoryDependenceAnalysis.h(20.82 KB)
📄 MemoryLocation.h(10.99 KB)
📄 MemorySSA.h(45.92 KB)
📄 MemorySSAUpdater.h(14.55 KB)
📄 ModuleSummaryAnalysis.h(3.44 KB)
📄 MustExecute.h(20.2 KB)
📄 ObjCARCAliasAnalysis.h(3.35 KB)
📄 ObjCARCAnalysisUtils.h(10.22 KB)
📄 ObjCARCInstKind.h(4.87 KB)
📄 OptimizationRemarkEmitter.h(5.93 KB)
📄 PHITransAddr.h(4.77 KB)
📄 Passes.h(3.88 KB)
📄 PhiValues.h(5.25 KB)
📄 PostDominators.h(3.41 KB)
📄 ProfileSummaryInfo.h(9.3 KB)
📄 PtrUseVisitor.h(9.96 KB)
📄 RegionInfo.h(35.23 KB)
📄 RegionInfoImpl.h(25.16 KB)
📄 RegionIterator.h(14.07 KB)
📄 RegionPass.h(4.05 KB)
📄 RegionPrinter.h(2.25 KB)
📄 ScalarEvolution.h(89.21 KB)
📄 ScalarEvolutionAliasAnalysis.h(2.09 KB)
📄 ScalarEvolutionDivision.h(2.48 KB)
📄 ScalarEvolutionExpressions.h(28.61 KB)
📄 ScalarEvolutionNormalization.h(2.47 KB)
📄 ScopedNoAliasAA.h(2.83 KB)
📄 SparsePropagation.h(19.43 KB)
📄 StackLifetime.h(6.16 KB)
📄 StackSafetyAnalysis.h(4.91 KB)
📄 SyncDependenceAnalysis.h(2.85 KB)
📄 SyntheticCountsUtils.h(1.85 KB)
📄 TargetFolder.h(11.04 KB)
📄 TargetLibraryInfo.def(55.35 KB)
📄 TargetLibraryInfo.h(16.86 KB)
📄 TargetTransformInfo.h(96.51 KB)
📄 TargetTransformInfoImpl.h(37.63 KB)
📄 Trace.h(4.1 KB)
📄 TypeBasedAliasAnalysis.h(3.05 KB)
📄 TypeMetadataUtils.h(1.94 KB)
📁 Utils
📄 ValueLattice.h(15.14 KB)
📄 ValueLatticeUtils.h(1.66 KB)
📄 ValueTracking.h(35.82 KB)
📄 VecFuncs.def(10.94 KB)
📄 VectorUtils.h(37.26 KB)

Editing: IVDescriptors.h

//===- llvm/Analysis/IVDescriptors.h - IndVar Descriptors -------*- 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 "describes" induction and recurrence variables.
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_ANALYSIS_IVDESCRIPTORS_H
#define LLVM_ANALYSIS_IVDESCRIPTORS_H

#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Operator.h"
#include "llvm/IR/ValueHandle.h"
#include "llvm/Support/Casting.h"

namespace llvm {

class DemandedBits;
class AssumptionCache;
class Loop;
class PredicatedScalarEvolution;
class ScalarEvolution;
class SCEV;
class DominatorTree;
class ICFLoopSafetyInfo;

/// The RecurrenceDescriptor is used to identify recurrences variables in a
/// loop. Reduction is a special case of recurrence that has uses of the
/// recurrence variable outside the loop. The method isReductionPHI identifies
/// reductions that are basic recurrences.
///
/// Basic recurrences are defined as the summation, product, OR, AND, XOR, min,
/// or max of a set of terms. For example: for(i=0; i<n; i++) { total +=
/// array[i]; } is a summation of array elements. Basic recurrences are a
/// special case of chains of recurrences (CR). See ScalarEvolution for CR
/// references.

/// This struct holds information about recurrence variables.
class RecurrenceDescriptor {
public:
  /// This enum represents the kinds of recurrences that we support.
  enum RecurrenceKind {
    RK_NoRecurrence,  ///< Not a recurrence.
    RK_IntegerAdd,    ///< Sum of integers.
    RK_IntegerMult,   ///< Product of integers.
    RK_IntegerOr,     ///< Bitwise or logical OR of numbers.
    RK_IntegerAnd,    ///< Bitwise or logical AND of numbers.
    RK_IntegerXor,    ///< Bitwise or logical XOR of numbers.
    RK_IntegerMinMax, ///< Min/max implemented in terms of select(cmp()).
    RK_FloatAdd,      ///< Sum of floats.
    RK_FloatMult,     ///< Product of floats.
    RK_FloatMinMax    ///< Min/max implemented in terms of select(cmp()).
  };

// This enum represents the kind of minmax recurrence.
  enum MinMaxRecurrenceKind {
    MRK_Invalid,
    MRK_UIntMin,
    MRK_UIntMax,
    MRK_SIntMin,
    MRK_SIntMax,
    MRK_FloatMin,
    MRK_FloatMax
  };

RecurrenceDescriptor() = default;

RecurrenceDescriptor(Value *Start, Instruction *Exit, RecurrenceKind K,
                       FastMathFlags FMF, MinMaxRecurrenceKind MK,
                       Instruction *UAI, Type *RT, bool Signed,
                       SmallPtrSetImpl<Instruction *> &CI)
      : StartValue(Start), LoopExitInstr(Exit), Kind(K), FMF(FMF),
        MinMaxKind(MK), UnsafeAlgebraInst(UAI), RecurrenceType(RT),
        IsSigned(Signed) {
    CastInsts.insert(CI.begin(), CI.end());
  }

/// This POD struct holds information about a potential recurrence operation.
  class InstDesc {
  public:
    InstDesc(bool IsRecur, Instruction *I, Instruction *UAI = nullptr)
        : IsRecurrence(IsRecur), PatternLastInst(I), MinMaxKind(MRK_Invalid),
          UnsafeAlgebraInst(UAI) {}

InstDesc(Instruction *I, MinMaxRecurrenceKind K, Instruction *UAI = nullptr)
        : IsRecurrence(true), PatternLastInst(I), MinMaxKind(K),
          UnsafeAlgebraInst(UAI) {}

bool isRecurrence() { return IsRecurrence; }

bool hasUnsafeAlgebra() { return UnsafeAlgebraInst != nullptr; }

Instruction *getUnsafeAlgebraInst() { return UnsafeAlgebraInst; }

MinMaxRecurrenceKind getMinMaxKind() { return MinMaxKind; }

Instruction *getPatternInst() { return PatternLastInst; }

private:
    // Is this instruction a recurrence candidate.
    bool IsRecurrence;
    // The last instruction in a min/max pattern (select of the select(icmp())
    // pattern), or the current recurrence instruction otherwise.
    Instruction *PatternLastInst;
    // If this is a min/max pattern the comparison predicate.
    MinMaxRecurrenceKind MinMaxKind;
    // Recurrence has unsafe algebra.
    Instruction *UnsafeAlgebraInst;
  };

/// Returns a struct describing if the instruction 'I' can be a recurrence
  /// variable of type 'Kind'. If the recurrence is a min/max pattern of
  /// select(icmp()) this function advances the instruction pointer 'I' from the
  /// compare instruction to the select instruction and stores this pointer in
  /// 'PatternLastInst' member of the returned struct.
  static InstDesc isRecurrenceInstr(Instruction *I, RecurrenceKind Kind,
                                    InstDesc &Prev, bool HasFunNoNaNAttr);

/// Returns true if instruction I has multiple uses in Insts
  static bool hasMultipleUsesOf(Instruction *I,
                                SmallPtrSetImpl<Instruction *> &Insts,
                                unsigned MaxNumUses);

/// Returns true if all uses of the instruction I is within the Set.
  static bool areAllUsesIn(Instruction *I, SmallPtrSetImpl<Instruction *> &Set);

/// Returns a struct describing if the instruction if the instruction is a
  /// Select(ICmp(X, Y), X, Y) instruction pattern corresponding to a min(X, Y)
  /// or max(X, Y).
  static InstDesc isMinMaxSelectCmpPattern(Instruction *I, InstDesc &Prev);

/// Returns a struct describing if the instruction is a
  /// Select(FCmp(X, Y), (Z = X op PHINode), PHINode) instruction pattern.
  static InstDesc isConditionalRdxPattern(RecurrenceKind Kind, Instruction *I);

/// Returns identity corresponding to the RecurrenceKind.
  static Constant *getRecurrenceIdentity(RecurrenceKind K, Type *Tp);

/// Returns the opcode of binary operation corresponding to the
  /// RecurrenceKind.
  static unsigned getRecurrenceBinOp(RecurrenceKind Kind);

/// Returns true if Phi is a reduction of type Kind and adds it to the
  /// RecurrenceDescriptor. If either \p DB is non-null or \p AC and \p DT are
  /// non-null, the minimal bit width needed to compute the reduction will be
  /// computed.
  static bool AddReductionVar(PHINode *Phi, RecurrenceKind Kind, Loop *TheLoop,
                              bool HasFunNoNaNAttr,
                              RecurrenceDescriptor &RedDes,
                              DemandedBits *DB = nullptr,
                              AssumptionCache *AC = nullptr,
                              DominatorTree *DT = nullptr);

/// Returns true if Phi is a reduction in TheLoop. The RecurrenceDescriptor
  /// is returned in RedDes. If either \p DB is non-null or \p AC and \p DT are
  /// non-null, the minimal bit width needed to compute the reduction will be
  /// computed.
  static bool isReductionPHI(PHINode *Phi, Loop *TheLoop,
                             RecurrenceDescriptor &RedDes,
                             DemandedBits *DB = nullptr,
                             AssumptionCache *AC = nullptr,
                             DominatorTree *DT = nullptr);

/// Returns true if Phi is a first-order recurrence. A first-order recurrence
  /// is a non-reduction recurrence relation in which the value of the
  /// recurrence in the current loop iteration equals a value defined in the
  /// previous iteration. \p SinkAfter includes pairs of instructions where the
  /// first will be rescheduled to appear after the second if/when the loop is
  /// vectorized. It may be augmented with additional pairs if needed in order
  /// to handle Phi as a first-order recurrence.
  static bool
  isFirstOrderRecurrence(PHINode *Phi, Loop *TheLoop,
                         DenseMap<Instruction *, Instruction *> &SinkAfter,
                         DominatorTree *DT);

RecurrenceKind getRecurrenceKind() { return Kind; }

MinMaxRecurrenceKind getMinMaxRecurrenceKind() { return MinMaxKind; }

FastMathFlags getFastMathFlags() { return FMF; }

TrackingVH<Value> getRecurrenceStartValue() { return StartValue; }

Instruction *getLoopExitInstr() { return LoopExitInstr; }

/// Returns true if the recurrence has unsafe algebra which requires a relaxed
  /// floating-point model.
  bool hasUnsafeAlgebra() { return UnsafeAlgebraInst != nullptr; }

/// Returns first unsafe algebra instruction in the PHI node's use-chain.
  Instruction *getUnsafeAlgebraInst() { return UnsafeAlgebraInst; }

/// Returns true if the recurrence kind is an integer kind.
  static bool isIntegerRecurrenceKind(RecurrenceKind Kind);

/// Returns true if the recurrence kind is a floating point kind.
  static bool isFloatingPointRecurrenceKind(RecurrenceKind Kind);

/// Returns true if the recurrence kind is an arithmetic kind.
  static bool isArithmeticRecurrenceKind(RecurrenceKind Kind);

/// Returns the type of the recurrence. This type can be narrower than the
  /// actual type of the Phi if the recurrence has been type-promoted.
  Type *getRecurrenceType() { return RecurrenceType; }

/// Returns a reference to the instructions used for type-promoting the
  /// recurrence.
  SmallPtrSet<Instruction *, 8> &getCastInsts() { return CastInsts; }

/// Returns true if all source operands of the recurrence are SExtInsts.
  bool isSigned() { return IsSigned; }

private:
  // The starting value of the recurrence.
  // It does not have to be zero!
  TrackingVH<Value> StartValue;
  // The instruction who's value is used outside the loop.
  Instruction *LoopExitInstr = nullptr;
  // The kind of the recurrence.
  RecurrenceKind Kind = RK_NoRecurrence;
  // The fast-math flags on the recurrent instructions.  We propagate these
  // fast-math flags into the vectorized FP instructions we generate.
  FastMathFlags FMF;
  // If this a min/max recurrence the kind of recurrence.
  MinMaxRecurrenceKind MinMaxKind = MRK_Invalid;
  // First occurrence of unasfe algebra in the PHI's use-chain.
  Instruction *UnsafeAlgebraInst = nullptr;
  // The type of the recurrence.
  Type *RecurrenceType = nullptr;
  // True if all source operands of the recurrence are SExtInsts.
  bool IsSigned = false;
  // Instructions used for type-promoting the recurrence.
  SmallPtrSet<Instruction *, 8> CastInsts;
};

/// A struct for saving information about induction variables.
class InductionDescriptor {
public:
  /// This enum represents the kinds of inductions that we support.
  enum InductionKind {
    IK_NoInduction,  ///< Not an induction variable.
    IK_IntInduction, ///< Integer induction variable. Step = C.
    IK_PtrInduction, ///< Pointer induction var. Step = C / sizeof(elem).
    IK_FpInduction   ///< Floating point induction variable.
  };

public:
  /// Default constructor - creates an invalid induction.
  InductionDescriptor() = default;

/// Get the consecutive direction. Returns:
  ///   0 - unknown or non-consecutive.
  ///   1 - consecutive and increasing.
  ///  -1 - consecutive and decreasing.
  int getConsecutiveDirection() const;

Value *getStartValue() const { return StartValue; }
  InductionKind getKind() const { return IK; }
  const SCEV *getStep() const { return Step; }
  BinaryOperator *getInductionBinOp() const { return InductionBinOp; }
  ConstantInt *getConstIntStepValue() const;

/// Returns true if \p Phi is an induction in the loop \p L. If \p Phi is an
  /// induction, the induction descriptor \p D will contain the data describing
  /// this induction. If by some other means the caller has a better SCEV
  /// expression for \p Phi than the one returned by the ScalarEvolution
  /// analysis, it can be passed through \p Expr. If the def-use chain
  /// associated with the phi includes casts (that we know we can ignore
  /// under proper runtime checks), they are passed through \p CastsToIgnore.
  static bool
  isInductionPHI(PHINode *Phi, const Loop *L, ScalarEvolution *SE,
                 InductionDescriptor &D, const SCEV *Expr = nullptr,
                 SmallVectorImpl<Instruction *> *CastsToIgnore = nullptr);

/// Returns true if \p Phi is a floating point induction in the loop \p L.
  /// If \p Phi is an induction, the induction descriptor \p D will contain
  /// the data describing this induction.
  static bool isFPInductionPHI(PHINode *Phi, const Loop *L, ScalarEvolution *SE,
                               InductionDescriptor &D);

/// Returns true if \p Phi is a loop \p L induction, in the context associated
  /// with the run-time predicate of PSE. If \p Assume is true, this can add
  /// further SCEV predicates to \p PSE in order to prove that \p Phi is an
  /// induction.
  /// If \p Phi is an induction, \p D will contain the data describing this
  /// induction.
  static bool isInductionPHI(PHINode *Phi, const Loop *L,
                             PredicatedScalarEvolution &PSE,
                             InductionDescriptor &D, bool Assume = false);

/// Returns true if the induction type is FP and the binary operator does
  /// not have the "fast-math" property. Such operation requires a relaxed FP
  /// mode.
  bool hasUnsafeAlgebra() {
    return (IK == IK_FpInduction) && InductionBinOp &&
           !cast<FPMathOperator>(InductionBinOp)->isFast();
  }

/// Returns induction operator that does not have "fast-math" property
  /// and requires FP unsafe mode.
  Instruction *getUnsafeAlgebraInst() {
    if (IK != IK_FpInduction)
      return nullptr;

if (!InductionBinOp || cast<FPMathOperator>(InductionBinOp)->isFast())
      return nullptr;
    return InductionBinOp;
  }

/// Returns binary opcode of the induction operator.
  Instruction::BinaryOps getInductionOpcode() const {
    return InductionBinOp ? InductionBinOp->getOpcode()
                          : Instruction::BinaryOpsEnd;
  }

/// Returns a reference to the type cast instructions in the induction
  /// update chain, that are redundant when guarded with a runtime
  /// SCEV overflow check.
  const SmallVectorImpl<Instruction *> &getCastInsts() const {
    return RedundantCasts;
  }

private:
  /// Private constructor - used by \c isInductionPHI.
  InductionDescriptor(Value *Start, InductionKind K, const SCEV *Step,
                      BinaryOperator *InductionBinOp = nullptr,
                      SmallVectorImpl<Instruction *> *Casts = nullptr);

/// Start value.
  TrackingVH<Value> StartValue;
  /// Induction kind.
  InductionKind IK = IK_NoInduction;
  /// Step value.
  const SCEV *Step = nullptr;
  // Instruction that advances induction variable.
  BinaryOperator *InductionBinOp = nullptr;
  // Instructions used for type-casts of the induction variable,
  // that are redundant when guarded with a runtime SCEV overflow check.
  SmallVector<Instruction *, 2> RedundantCasts;
};

} // end namespace llvm

#endif // LLVM_ANALYSIS_IVDESCRIPTORS_H

003 File Manager

Editing: IVDescriptors.h

Upload File

Create Folder