LLVM 23.0.0git
Public Member Functions | Static Public Attributes | List of all members
slpvectorizer::BoUpSLP::LookAheadHeuristics Class Reference

A helper class used for scoring candidates for two consecutive lanes. More...

Public Member Functions

 LookAheadHeuristics (const TargetLibraryInfo &TLI, const DataLayout &DL, ScalarEvolution &SE, const BoUpSLP &R, int NumLanes, int MaxLevel)
int getShallowScore (Value *V1, Value *V2, Instruction *U1, Instruction *U2, ArrayRef< Value * > MainAltOps) const
int getScoreAtLevelRec (Value *LHS, Value *RHS, Instruction *U1, Instruction *U2, int CurrLevel, ArrayRef< Value * > MainAltOps) const
 Go through the operands of LHS and RHS recursively until MaxLevel, and return the cummulative score.

Static Public Attributes

static constexpr int ScoreConsecutiveLoads = 40
 Loads from consecutive memory addresses, e.g. load(A[i]), load(A[i+1]).
static constexpr int ScoreSplatLoads = 30
 The same load multiple times.
static constexpr int ScoreReversedLoads = 30
 Loads from reversed memory addresses, e.g. load(A[i+1]), load(A[i]).
static constexpr int ScoreMaskedGatherCandidate = 10
 A load candidate for masked gather.
static constexpr int ScoreConsecutiveExtracts = 40
 ExtractElementInst from same vector and consecutive indexes.
static constexpr int ScoreReversedExtracts = 30
 ExtractElementInst from same vector and reversed indices.
static constexpr int ScoreConstants = 15
 Constants.
static constexpr int ScoreSameConstants = 17
 Same constants.
static constexpr int ScoreSameOpcode = 20
 Instructions with the same opcode.
static constexpr int ScoreAltOpcodes = 10
 Instructions with alt opcodes (e.g, add + sub).
static constexpr int ScoreSplat = 10
 Identical instructions (a.k.a. splat or broadcast).
static constexpr int ScoreUndef = 10
 Matching with an undef is preferable to failing.
static constexpr int ScoreFail = 0
 Score for failing to find a decent match.
static constexpr int ScoreAllUserVectorized = 10
 Score if all users are vectorized.

Detailed Description

A helper class used for scoring candidates for two consecutive lanes.

Definition at line 2495 of file SLPVectorizer.cpp.

Constructor & Destructor Documentation

◆ LookAheadHeuristics()

slpvectorizer::BoUpSLP::LookAheadHeuristics::LookAheadHeuristics ( const TargetLibraryInfo & TLI,
const DataLayout & DL,
ScalarEvolution & SE,
const BoUpSLP & R,
int NumLanes,
int MaxLevel )
inline

Definition at line 2504 of file SLPVectorizer.cpp.

References slpvectorizer::BoUpSLP::BoUpSLP().

Member Function Documentation

◆ getScoreAtLevelRec()

int slpvectorizer::BoUpSLP::LookAheadHeuristics::getScoreAtLevelRec ( Value * LHS,
Value * RHS,
Instruction * U1,
Instruction * U2,
int CurrLevel,
ArrayRef< Value * > MainAltOps ) const
inline

Go through the operands of LHS and RHS recursively until MaxLevel, and return the cummulative score.

U1 and U2 are the users of LHS and RHS (that is LHS and RHS are operands of U1 and U2), except at the beginning of the recursion where these are set to nullptr.

For example: 

///  A[0]  B[0]  A[1]  B[1]  C[0] D[0]  B[1] A[1]
///     \ /         \ /         \ /        \ /
///      +           +           +          +
///     G1          G2          G3         G4
///

The getScoreAtLevelRec(G1, G2) function will try to match the nodes at each level recursively, accumulating the score. It starts from matching the additions at level 0, then moves on to the loads (level 1). The score of G1 and G2 is higher than G1 and G3, because {A[0],A[1]} and {B[0],B[1]} match with LookAheadHeuristics::ScoreConsecutiveLoads, while {A[0],C[0]} has a score of LookAheadHeuristics::ScoreFail. Please note that the order of the operands does not matter, as we evaluate the score of all profitable combinations of operands. In other words the score of G1 and G4 is the same as G1 and G2. This heuristic is based on ideas described in: Look-ahead SLP: Auto-vectorization in the presence of commutative operations, CGO 2018 by Vasileios Porpodas, Rodrigo C. O. Rocha, Luís F. W. Góes

Definition at line 2755 of file SLPVectorizer.cpp.

References assert(), llvm::SmallSet< T, N, C >::count(), llvm::dyn_cast(), getScoreAtLevelRec(), getShallowScore(), llvm::SmallSet< T, N, C >::insert(), llvm::isa(), isCommutative(), ScoreFail, and ScoreSameOpcode.

Referenced by slpvectorizer::BoUpSLP::findBestRootPair(), and getScoreAtLevelRec().

◆ getShallowScore()

int slpvectorizer::BoUpSLP::LookAheadHeuristics::getShallowScore ( Value * V1,
Value * V2,
Instruction * U1,
Instruction * U2,
ArrayRef< Value * > MainAltOps ) const
inline
Returns
the score of placing V1 and V2 in consecutive lanes. U1 and U2 are the users of V1 and V2. Also, checks if V1 and V2 are compatible with instructions in MainAltOps.

Definition at line 2557 of file SLPVectorizer.cpp.

References AbstractManglingParser< Derived, Alloc >::Ops, llvm::all_of(), llvm::any_of(), llvm::cast(), Cond, llvm::dyn_cast(), llvm::ArrayRef< T >::empty(), llvm::from_range, llvm::ElementCount::getFixed(), llvm::getPointersDiff(), getSameOpcode(), llvm::Value::getType(), llvm::getUnderlyingObject(), getWidenedType(), llvm::ConstantInt::getZExtValue(), llvm::Value::hasNUsesOrMore(), llvm::isa(), isConstant(), isUndefVector(), isValidElementType(), llvm::PatternMatchHelpers::m_CombineOr(), llvm::PatternMatch::m_ConstantInt(), llvm::PatternMatch::m_ExtractElt(), llvm::PatternMatch::m_Select(), llvm::PatternMatch::m_Undef(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::m_ZExt(), llvm::PatternMatch::match(), ScoreAltOpcodes, ScoreConsecutiveExtracts, ScoreConsecutiveLoads, ScoreConstants, ScoreFail, ScoreMaskedGatherCandidate, ScoreReversedExtracts, ScoreReversedLoads, ScoreSameConstants, ScoreSameOpcode, ScoreSplat, ScoreSplatLoads, ScoreUndef, UsesLimit, and llvm::V1.

Referenced by getScoreAtLevelRec().

Member Data Documentation

◆ ScoreAllUserVectorized

int slpvectorizer::BoUpSLP::LookAheadHeuristics::ScoreAllUserVectorized = 10
staticconstexpr

Score if all users are vectorized.

Definition at line 2551 of file SLPVectorizer.cpp.

◆ ScoreAltOpcodes

int slpvectorizer::BoUpSLP::LookAheadHeuristics::ScoreAltOpcodes = 10
staticconstexpr

Instructions with alt opcodes (e.g, add + sub).

Definition at line 2543 of file SLPVectorizer.cpp.

Referenced by getShallowScore().

◆ ScoreConsecutiveExtracts

int slpvectorizer::BoUpSLP::LookAheadHeuristics::ScoreConsecutiveExtracts = 40
staticconstexpr

ExtractElementInst from same vector and consecutive indexes.

Definition at line 2533 of file SLPVectorizer.cpp.

Referenced by getShallowScore().

◆ ScoreConsecutiveLoads

int slpvectorizer::BoUpSLP::LookAheadHeuristics::ScoreConsecutiveLoads = 40
staticconstexpr

Loads from consecutive memory addresses, e.g. load(A[i]), load(A[i+1]).

Definition at line 2522 of file SLPVectorizer.cpp.

Referenced by getShallowScore().

◆ ScoreConstants

int slpvectorizer::BoUpSLP::LookAheadHeuristics::ScoreConstants = 15
staticconstexpr

Constants.

Definition at line 2537 of file SLPVectorizer.cpp.

Referenced by getShallowScore().

◆ ScoreFail

int slpvectorizer::BoUpSLP::LookAheadHeuristics::ScoreFail = 0
staticconstexpr

Score for failing to find a decent match.

Definition at line 2549 of file SLPVectorizer.cpp.

Referenced by slpvectorizer::BoUpSLP::findBestRootPair(), getScoreAtLevelRec(), and getShallowScore().

◆ ScoreMaskedGatherCandidate

int slpvectorizer::BoUpSLP::LookAheadHeuristics::ScoreMaskedGatherCandidate = 10
staticconstexpr

A load candidate for masked gather.

Definition at line 2531 of file SLPVectorizer.cpp.

Referenced by getShallowScore().

◆ ScoreReversedExtracts

int slpvectorizer::BoUpSLP::LookAheadHeuristics::ScoreReversedExtracts = 30
staticconstexpr

ExtractElementInst from same vector and reversed indices.

Definition at line 2535 of file SLPVectorizer.cpp.

Referenced by getShallowScore().

◆ ScoreReversedLoads

int slpvectorizer::BoUpSLP::LookAheadHeuristics::ScoreReversedLoads = 30
staticconstexpr

Loads from reversed memory addresses, e.g. load(A[i+1]), load(A[i]).

Definition at line 2529 of file SLPVectorizer.cpp.

Referenced by getShallowScore().

◆ ScoreSameConstants

int slpvectorizer::BoUpSLP::LookAheadHeuristics::ScoreSameConstants = 17
staticconstexpr

Same constants.

Definition at line 2539 of file SLPVectorizer.cpp.

Referenced by getShallowScore().

◆ ScoreSameOpcode

int slpvectorizer::BoUpSLP::LookAheadHeuristics::ScoreSameOpcode = 20
staticconstexpr

Instructions with the same opcode.

Definition at line 2541 of file SLPVectorizer.cpp.

Referenced by getScoreAtLevelRec(), and getShallowScore().

◆ ScoreSplat

int slpvectorizer::BoUpSLP::LookAheadHeuristics::ScoreSplat = 10
staticconstexpr

Identical instructions (a.k.a. splat or broadcast).

Definition at line 2545 of file SLPVectorizer.cpp.

Referenced by getShallowScore().

◆ ScoreSplatLoads

int slpvectorizer::BoUpSLP::LookAheadHeuristics::ScoreSplatLoads = 30
staticconstexpr

The same load multiple times.

This should have a better score than ScoreSplat because it in x86 for a 2-lane vector we can represent it with movddup (reg), xmm0 which has a throughput of 0.5 versus 0.5 for a vector load and 1.0 for a broadcast.

Definition at line 2527 of file SLPVectorizer.cpp.

Referenced by getShallowScore(), and slpvectorizer::BoUpSLP::transformNodes().

◆ ScoreUndef

int slpvectorizer::BoUpSLP::LookAheadHeuristics::ScoreUndef = 10
staticconstexpr

Matching with an undef is preferable to failing.

Definition at line 2547 of file SLPVectorizer.cpp.

Referenced by getShallowScore().

The documentation for this class was generated from the following file:
Generated on for LLVM by doxygen 1.14.0