//===- 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/MapVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/ValueHandle.h"
namespace llvm {
class AssumptionCache;
class DemandedBits;
class DominatorTree;
class Instruction;
class Loop;
class PredicatedScalarEvolution;
class ScalarEvolution;
class SCEV;
class StoreInst;
/// These are the kinds of recurrences that we support.
enum class RecurKind {
None, ///< Not a recurrence.
Add, ///< Sum of integers.
Mul, ///< Product of integers.
Or, ///< Bitwise or logical OR of integers.
And, ///< Bitwise or logical AND of integers.
Xor, ///< Bitwise or logical XOR of integers.
SMin, ///< Signed integer min implemented in terms of select(cmp()).
SMax, ///< Signed integer max implemented in terms of select(cmp()).
UMin, ///< Unisgned integer min implemented in terms of select(cmp()).
UMax, ///< Unsigned integer max implemented in terms of select(cmp()).
FAdd, ///< Sum of floats.
FMul, ///< Product of floats.
FMin, ///< FP min implemented in terms of select(cmp()).
FMax, ///< FP max implemented in terms of select(cmp()).
FMulAdd, ///< Fused multiply-add of floats (a * b + c).
SelectICmp, ///< Integer select(icmp(),x,y) where one of (x,y) is loop
///< invariant
SelectFCmp ///< Integer select(fcmp(),x,y) where one of (x,y) is loop
///< invariant
};
/// 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:
RecurrenceDescriptor() = default;
RecurrenceDescriptor(Value *Start, Instruction *Exit, StoreInst *Store,
RecurKind K, FastMathFlags FMF, Instruction *ExactFP,
Type *RT, bool Signed, bool Ordered,
SmallPtrSetImpl<Instruction *> &CI,
unsigned MinWidthCastToRecurTy)
: IntermediateStore(Store), StartValue(Start), LoopExitInstr(Exit),
Kind(K), FMF(FMF), ExactFPMathInst(ExactFP), RecurrenceType(RT),
IsSigned(Signed), IsOrdered(Ordered),
MinWidthCastToRecurrenceType(MinWidthCastToRecurTy) {
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 *ExactFP = nullptr)
: IsRecurrence(IsRecur), PatternLastInst(I),
RecKind(RecurKind::None), ExactFPMathInst(ExactFP) {}
InstDesc(Instruction *I, RecurKind K, Instruction *ExactFP = nullptr)
: IsRecurrence(true), PatternLastInst(I), RecKind(K),
ExactFPMathInst(ExactFP) {}
bool isRecurrence() const { return IsRecurrence; }
bool needsExactFPMath() const { return ExactFPMathInst != nullptr; }
Instruction *getExactFPMathInst() const { return ExactFPMathInst; }
RecurKind getRecKind() const { return RecKind; }
Instruction *getPatternInst() const { 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.
RecurKind RecKind;
// Recurrence does not allow floating-point reassociation.
Instruction *ExactFPMathInst;
};
/// Returns a struct describing if the instruction 'I' can be a recurrence
/// variable of type 'Kind' for a Loop \p L and reduction PHI \p Phi.
/// 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(Loop *L, PHINode *Phi, Instruction *I,
RecurKind Kind, InstDesc &Prev,
FastMathFlags FuncFMF);
/// 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 is a llvm.(s/u)(min/max),
/// llvm.minnum/maxnum or a Select(ICmp(X, Y), X, Y) pair of instructions
/// corresponding to a min(X, Y) or max(X, Y), matching the recurrence kind \p
/// Kind. \p Prev specifies the description of an already processed select
/// instruction, so its corresponding cmp can be matched to it.
static InstDesc isMinMaxPattern(Instruction *I, RecurKind Kind,
const InstDesc &Prev);
/// Returns a struct describing whether the instruction is either a
/// Select(ICmp(A, B), X, Y), or
/// Select(FCmp(A, B), X, Y)
/// where one of (X, Y) is a loop invariant integer and the other is a PHI
/// value. \p Prev specifies the description of an already processed select
/// instruction, so its corresponding cmp can be matched to it.
static InstDesc isSelectCmpPattern(Loop *Loop, PHINode *OrigPhi,
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(RecurKind Kind, Instruction *I);
/// Returns identity corresponding to the RecurrenceKind.
Value *getRecurrenceIdentity(RecurKind K, Type *Tp, FastMathFlags FMF) const;
/// Returns the opcode corresponding to the RecurrenceKind.
static unsigned getOpcode(RecurKind 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, RecurKind Kind, Loop *TheLoop,
FastMathFlags FuncFMF, RecurrenceDescriptor &RedDes,
DemandedBits *DB = nullptr, AssumptionCache *AC = nullptr,
DominatorTree *DT = nullptr, ScalarEvolution *SE = 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. If \p SE is non-null, store instructions to loop invariant
/// addresses are processed.
static bool
isReductionPHI(PHINode *Phi, Loop *TheLoop, RecurrenceDescriptor &RedDes,
DemandedBits *DB = nullptr, AssumptionCache *AC = nullptr,
DominatorTree *DT = nullptr, ScalarEvolution *SE = nullptr);
/// Returns true if Phi is a fixed-order recurrence. A fixed-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 a
/// previous iteration (e.g. if the value is defined in the previous
/// iteration, we refer to it as first-order recurrence, if it is defined in
/// the iteration before the previous, we refer to it as second-order
/// recurrence and so on). \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
isFixedOrderRecurrence(PHINode *Phi, Loop *TheLoop,
MapVector<Instruction *, Instruction *> &SinkAfter,
DominatorTree *DT);
RecurKind getRecurrenceKind() const { return Kind; }
unsigned getOpcode() const { return getOpcode(getRecurrenceKind()); }
FastMathFlags getFastMathFlags() const { return FMF; }
TrackingVH<Value> getRecurrenceStartValue() const { return StartValue; }
Instruction *getLoopExitInstr() const { return LoopExitInstr; }
/// Returns true if the recurrence has floating-point math that requires
/// precise (ordered) operations.
bool hasExactFPMath() const { return ExactFPMathInst != nullptr; }
/// Returns 1st non-reassociative FP instruction in the PHI node's use-chain.
Instruction *getExactFPMathInst() const { return ExactFPMathInst; }
/// Returns true if the recurrence kind is an integer kind.
static bool isIntegerRecurrenceKind(RecurKind Kind);
/// Returns true if the recurrence kind is a floating point kind.
static bool isFloatingPointRecurrenceKind(RecurKind Kind);
/// Returns true if the recurrence kind is an integer min/max kind.
static bool isIntMinMaxRecurrenceKind(RecurKind Kind) {
return Kind == RecurKind::UMin || Kind == RecurKind::UMax ||
Kind == RecurKind::SMin || Kind == RecurKind::SMax;
}
/// Returns true if the recurrence kind is a floating-point min/max kind.
static bool isFPMinMaxRecurrenceKind(RecurKind Kind) {
return Kind == RecurKind::FMin || Kind == RecurKind::FMax;
}
/// Returns true if the recurrence kind is any min/max kind.
static bool isMinMaxRecurrenceKind(RecurKind Kind) {
return isIntMinMaxRecurrenceKind(Kind) || isFPMinMaxRecurrenceKind(Kind);
}
/// Returns true if the recurrence kind is of the form
/// select(cmp(),x,y) where one of (x,y) is loop invariant.
static bool isSelectCmpRecurrenceKind(RecurKind Kind) {
return Kind == RecurKind::SelectICmp || Kind == RecurKind::SelectFCmp;
}
/// 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() const { return RecurrenceType; }
/// Returns a reference to the instructions used for type-promoting the
/// recurrence.
const SmallPtrSet<Instruction *, 8> &getCastInsts() const { return CastInsts; }
/// Returns the minimum width used by the recurrence in bits.
unsigned getMinWidthCastToRecurrenceTypeInBits() const {
return MinWidthCastToRecurrenceType;
}
/// Returns true if all source operands of the recurrence are SExtInsts.
bool isSigned() const { return IsSigned; }
/// Expose an ordered FP reduction to the instance users.
bool isOrdered() const { return IsOrdered; }
/// Attempts to find a chain of operations from Phi to LoopExitInst that can
/// be treated as a set of reductions instructions for in-loop reductions.
SmallVector<Instruction *, 4> getReductionOpChain(PHINode *Phi,
Loop *L) const;
/// Returns true if the instruction is a call to the llvm.fmuladd intrinsic.
static bool isFMulAddIntrinsic(Instruction *I) {
return isa<IntrinsicInst>(I) &&
cast<IntrinsicInst>(I)->getIntrinsicID() == Intrinsic::fmuladd;
}
/// Reductions may store temporary or final result to an invariant address.
/// If there is such a store in the loop then, after successfull run of
/// AddReductionVar method, this field will be assigned the last met store.
StoreInst *IntermediateStore = nullptr;
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.
RecurKind Kind = RecurKind::None;
// The fast-math flags on the recurrent instructions. We propagate these
// fast-math flags into the vectorized FP instructions we generate.
FastMathFlags FMF;
// First instance of non-reassociative floating-point in the PHI's use-chain.
Instruction *ExactFPMathInst = nullptr;
// The type of the recurrence.
Type *RecurrenceType = nullptr;
// True if all source operands of the recurrence are SExtInsts.
bool IsSigned = false;
// True if this recurrence can be treated as an in-order reduction.
// Currently only a non-reassociative FAdd can be considered in-order,
// if it is also the only FAdd in the PHI's use chain.
bool IsOrdered = false;
// Instructions used for type-promoting the recurrence.
SmallPtrSet<Instruction *, 8> CastInsts;
// The minimum width used by the recurrence.
unsigned MinWidthCastToRecurrenceType;
};
/// 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;
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 floating-point induction operator that does not allow
/// reassociation (transforming the induction requires an override of normal
/// floating-point rules).
Instruction *getExactFPMathInst() {
if (IK == IK_FpInduction && InductionBinOp &&
!InductionBinOp->hasAllowReassoc())
return InductionBinOp;
return nullptr;
}
/// Returns binary opcode of the induction operator.
Instruction::BinaryOps getInductionOpcode() const {
return InductionBinOp ? InductionBinOp->getOpcode()
: Instruction::BinaryOpsEnd;
}
Type *getElementType() const {
assert(IK == IK_PtrInduction && "Only pointer induction has element type");
return ElementType;
}
/// 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,
Type *ElementType = 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;
// Element type for pointer induction variables.
// TODO: This can be dropped once support for typed pointers is removed.
Type *ElementType = 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