LLVM 22.0.0git
Macros | Functions | Variables
DependenceAnalysis.cpp File Reference
#include "llvm/Analysis/DependenceAnalysis.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/Delinearization.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/InstIterator.h"
#include "llvm/IR/Module.h"
#include "llvm/InitializePasses.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/raw_ostream.h"

Go to the source code of this file.

Macros

#define DEBUG_TYPE   "da"

Functions

 STATISTIC (TotalArrayPairs, "Array pairs tested")
 STATISTIC (SeparableSubscriptPairs, "Separable subscript pairs")
 STATISTIC (CoupledSubscriptPairs, "Coupled subscript pairs")
 STATISTIC (NonlinearSubscriptPairs, "Nonlinear subscript pairs")
 STATISTIC (ZIVapplications, "ZIV applications")
 STATISTIC (ZIVindependence, "ZIV independence")
 STATISTIC (StrongSIVapplications, "Strong SIV applications")
 STATISTIC (StrongSIVsuccesses, "Strong SIV successes")
 STATISTIC (StrongSIVindependence, "Strong SIV independence")
 STATISTIC (WeakCrossingSIVapplications, "Weak-Crossing SIV applications")
 STATISTIC (WeakCrossingSIVsuccesses, "Weak-Crossing SIV successes")
 STATISTIC (WeakCrossingSIVindependence, "Weak-Crossing SIV independence")
 STATISTIC (ExactSIVapplications, "Exact SIV applications")
 STATISTIC (ExactSIVsuccesses, "Exact SIV successes")
 STATISTIC (ExactSIVindependence, "Exact SIV independence")
 STATISTIC (WeakZeroSIVapplications, "Weak-Zero SIV applications")
 STATISTIC (WeakZeroSIVsuccesses, "Weak-Zero SIV successes")
 STATISTIC (WeakZeroSIVindependence, "Weak-Zero SIV independence")
 STATISTIC (ExactRDIVapplications, "Exact RDIV applications")
 STATISTIC (ExactRDIVindependence, "Exact RDIV independence")
 STATISTIC (SymbolicRDIVapplications, "Symbolic RDIV applications")
 STATISTIC (SymbolicRDIVindependence, "Symbolic RDIV independence")
 STATISTIC (DeltaApplications, "Delta applications")
 STATISTIC (DeltaSuccesses, "Delta successes")
 STATISTIC (DeltaIndependence, "Delta independence")
 STATISTIC (DeltaPropagations, "Delta propagations")
 STATISTIC (GCDapplications, "GCD applications")
 STATISTIC (GCDsuccesses, "GCD successes")
 STATISTIC (GCDindependence, "GCD independence")
 STATISTIC (BanerjeeApplications, "Banerjee applications")
 STATISTIC (BanerjeeIndependence, "Banerjee independence")
 STATISTIC (BanerjeeSuccesses, "Banerjee successes")
 STATISTIC (SameSDLoopsCount, "Loops with Same iteration Space and Depth")
 INITIALIZE_PASS_BEGIN (DependenceAnalysisWrapperPass, "da", "Dependence Analysis", true, true) INITIALIZE_PASS_END(DependenceAnalysisWrapperPass
static void dumpExampleDependence (raw_ostream &OS, DependenceInfo *DA, ScalarEvolution &SE, LoopInfo &LI, bool NormalizeResults)
static AliasResult underlyingObjectsAlias (AAResults *AA, const DataLayout &DL, const MemoryLocation &LocA, const MemoryLocation &LocB)
static bool isLoadOrStore (const Instruction *I)
static const SCEV * minusSCEVNoSignedOverflow (const SCEV *A, const SCEV *B, ScalarEvolution &SE)
 Returns A - B if it guaranteed not to signed wrap.
static bool isDependenceTestEnabled (DependenceTestType Test)
 Returns true iff Test is enabled.
static bool findGCD (unsigned Bits, const APInt &AM, const APInt &BM, const APInt &Delta, APInt &G, APInt &X, APInt &Y)
static APInt floorOfQuotient (const APInt &A, const APInt &B)
static APInt ceilingOfQuotient (const APInt &A, const APInt &B)
static std::pair< std::optional< APInt >, std::optional< APInt > > inferDomainOfAffine (const APInt &A, const APInt &B, const std::optional< APInt > &UB)
 Given an affine expression of the form A*k + B, where k is an arbitrary integer, infer the possible range of k based on the known range of the affine expression.
static bool isRemainderZero (const SCEVConstant *Dividend, const SCEVConstant *Divisor)
static std::optional< APInt > getConstantPart (const SCEV *Expr)
static void dumpSmallBitVector (SmallBitVector &BV)

Variables

static cl::opt< bool > Delinearize ("da-delinearize", cl::init(true), cl::Hidden, cl::desc("Try to delinearize array references."))
static cl::opt< bool > DisableDelinearizationChecks ("da-disable-delinearization-checks", cl::Hidden, cl::desc("Disable checks that try to statically verify validity of " "delinearized subscripts. Enabling this option may result in incorrect " "dependence vectors for languages that allow the subscript of one " "dimension to underflow or overflow into another dimension."))
static cl::opt< unsigned > MIVMaxLevelThreshold ("da-miv-max-level-threshold", cl::init(7), cl::Hidden, cl::desc("Maximum depth allowed for the recursive algorithm used to " "explore MIV direction vectors."))
static cl::opt< DependenceTestType > EnableDependenceTest ("da-enable-dependence-test", cl::init(DependenceTestType::All), cl::ReallyHidden, cl::desc("Run only specified dependence test routine and disable others. " "The purpose is mainly to exclude the influence of other " "dependence test routines in regression tests. If set to All, all " "dependence test routines are enabled."), cl::values(clEnumValN(DependenceTestType::All, "all", "Enable all dependence test routines."), clEnumValN(DependenceTestType::StrongSIV, "strong-siv", "Enable only Strong SIV test."), clEnumValN(DependenceTestType::WeakCrossingSIV, "weak-crossing-siv", "Enable only Weak-Crossing SIV test."), clEnumValN(DependenceTestType::ExactSIV, "exact-siv", "Enable only Exact SIV test."), clEnumValN(DependenceTestType::WeakZeroSIV, "weak-zero-siv", "Enable only Weak-Zero SIV test."), clEnumValN(DependenceTestType::ExactRDIV, "exact-rdiv", "Enable only Exact RDIV test."), clEnumValN(DependenceTestType::SymbolicRDIV, "symbolic-rdiv", "Enable only Symbolic RDIV test."), clEnumValN(DependenceTestType::GCDMIV, "gcd-miv", "Enable only GCD MIV test."), clEnumValN(DependenceTestType::BanerjeeMIV, "banerjee-miv", "Enable only Banerjee MIV test.")))
static cl::opt< bool > EnableMonotonicityCheck ("da-enable-monotonicity-check", cl::init(false), cl::Hidden, cl::desc("Check if the subscripts are monotonic. If it's not, dependence " "is reported as unknown."))
static cl::opt< bool > DumpMonotonicityReport ("da-dump-monotonicity-report", cl::init(false), cl::Hidden, cl::desc("When printing analysis, dump the results of monotonicity checks."))
 da
Dependence Analysis
Dependence true

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE   "da"

Definition at line 70 of file DependenceAnalysis.cpp.

Function Documentation

◆ ceilingOfQuotient()

APInt ceilingOfQuotient ( const APInt & A,
const APInt & B )
static

Definition at line 1958 of file DependenceAnalysis.cpp.

References A(), B(), and llvm::APInt::sdivrem().

Referenced by inferDomainOfAffine().

◆ dumpExampleDependence()

void dumpExampleDependence ( raw_ostream & OS,
DependenceInfo * DA,
ScalarEvolution & SE,
LoopInfo & LI,
bool NormalizeResults )
static

Definition at line 397 of file DependenceAnalysis.cpp.

References assert(), D(), DumpMonotonicityReport, llvm::Dependence::DVEntry::EQ, F, llvm::getLoadStorePointerOperand(), llvm::LoopInfoBase< BlockT, LoopT >::getLoopFor(), llvm::ScalarEvolution::getSCEVAtScope(), llvm::raw_ostream::indent(), llvm::inst_begin(), llvm::inst_end(), instructions, llvm::isa(), llvm::SCEVUnionPredicate::isAlwaysTrue(), llvm::SCEV::isZero(), llvm::SCEVUnionPredicate::print(), Ptr, and llvm::ScalarEvolution::removePointerBase().

Referenced by llvm::DependenceAnalysisWrapperPass::print(), and llvm::DependenceAnalysisPrinterPass::run().

◆ dumpSmallBitVector()

void dumpSmallBitVector ( SmallBitVector & BV)
static

Definition at line 4020 of file DependenceAnalysis.cpp.

References llvm::dbgs(), llvm::SmallBitVector::find_next(), and llvm::SmallBitVector::set_bits().

Referenced by llvm::DependenceInfo::depends().

◆ findGCD()

bool findGCD ( unsigned Bits,
const APInt & AM,
const APInt & BM,
const APInt & Delta,
APInt & G,
APInt & X,
APInt & Y )
static

Definition at line 1916 of file DependenceAnalysis.cpp.

References llvm::APInt::abs(), llvm::dbgs(), G, LLVM_DEBUG, llvm::APInt::sdiv(), llvm::APInt::sdivrem(), llvm::APInt::slt(), llvm::APInt::srem(), X, and Y.

◆ floorOfQuotient()

APInt floorOfQuotient ( const APInt & A,
const APInt & B )
static

Definition at line 1946 of file DependenceAnalysis.cpp.

References A(), B(), and llvm::APInt::sdivrem().

Referenced by inferDomainOfAffine().

◆ getConstantPart()

std::optional< APInt > getConstantPart ( const SCEV * Expr)
static

Definition at line 2827 of file DependenceAnalysis.cpp.

References llvm::dyn_cast().

◆ inferDomainOfAffine()

std::pair< std::optional< APInt >, std::optional< APInt > > inferDomainOfAffine ( const APInt & A,
const APInt & B,
const std::optional< APInt > & UB )
static

Given an affine expression of the form A*k + B, where k is an arbitrary integer, infer the possible range of k based on the known range of the affine expression.

If we know A*k + B is non-negative, i.e.,

A*k + B >= 0

we can derive the following inequalities for k when A is positive:

k >= -B / A

Since k is an integer, it means k is greater than or equal to the ceil(-B / A).

If the upper bound of the affine expression UB is passed, the following inequality can be derived as well:

A*k + B <= UB

which leads to:

k <= (UB - B) / A

Again, as k is an integer, it means k is less than or equal to the floor((UB - B) / A).

The similar logic applies when A is negative, but the inequalities sign flip while working with them.

Preconditions: A is non-zero, and we know A*k + B is non-negative.

Definition at line 2000 of file DependenceAnalysis.cpp.

References A(), assert(), B(), ceilingOfQuotient(), llvm::dbgs(), floorOfQuotient(), and LLVM_DEBUG.

◆ INITIALIZE_PASS_BEGIN()

INITIALIZE_PASS_BEGIN ( DependenceAnalysisWrapperPass ,
"da" ,
"Dependence Analysis" ,
true ,
true  )

References INITIALIZE_PASS_DEPENDENCY.

◆ isDependenceTestEnabled()

bool isDependenceTestEnabled ( DependenceTestType Test)
static

Returns true iff Test is enabled.

Definition at line 1586 of file DependenceAnalysis.cpp.

References EnableDependenceTest, and llvm::Test.

◆ isLoadOrStore()

bool isLoadOrStore ( const Instruction * I)
static

Definition at line 1104 of file DependenceAnalysis.cpp.

References llvm::dyn_cast(), and I.

Referenced by llvm::DependenceInfo::depends(), and llvm::DependenceInfo::getSplitIteration().

◆ isRemainderZero()

bool isRemainderZero ( const SCEVConstant * Dividend,
const SCEVConstant * Divisor )
static

Definition at line 2191 of file DependenceAnalysis.cpp.

References llvm::SCEVConstant::getAPInt(), and llvm::APInt::srem().

◆ minusSCEVNoSignedOverflow()

const SCEV * minusSCEVNoSignedOverflow ( const SCEV * A,
const SCEV * B,
ScalarEvolution & SE )
static

Returns A - B if it guaranteed not to signed wrap.

Otherwise returns nullptr. A and B must have the same integer type.

Definition at line 1578 of file DependenceAnalysis.cpp.

References A(), B(), llvm::ScalarEvolution::getMinusSCEV(), and llvm::ScalarEvolution::willNotOverflow().

◆ STATISTIC() [1/33]

STATISTIC ( BanerjeeApplications ,
"Banerjee applications"  )

◆ STATISTIC() [2/33]

STATISTIC ( BanerjeeIndependence ,
"Banerjee independence"  )

◆ STATISTIC() [3/33]

STATISTIC ( BanerjeeSuccesses ,
"Banerjee successes"  )

◆ STATISTIC() [4/33]

STATISTIC ( CoupledSubscriptPairs ,
"Coupled subscript pairs"  )

◆ STATISTIC() [5/33]

STATISTIC ( DeltaApplications ,
"Delta applications"  )

◆ STATISTIC() [6/33]

STATISTIC ( DeltaIndependence ,
"Delta independence"  )

◆ STATISTIC() [7/33]

STATISTIC ( DeltaPropagations ,
"Delta propagations"  )

◆ STATISTIC() [8/33]

STATISTIC ( DeltaSuccesses ,
"Delta successes"  )

◆ STATISTIC() [9/33]

STATISTIC ( ExactRDIVapplications ,
"Exact RDIV applications"  )

◆ STATISTIC() [10/33]

STATISTIC ( ExactRDIVindependence ,
"Exact RDIV independence"  )

◆ STATISTIC() [11/33]

STATISTIC ( ExactSIVapplications ,
"Exact SIV applications"  )

◆ STATISTIC() [12/33]

STATISTIC ( ExactSIVindependence ,
"Exact SIV independence"  )

◆ STATISTIC() [13/33]

STATISTIC ( ExactSIVsuccesses ,
"Exact SIV successes"  )

◆ STATISTIC() [14/33]

STATISTIC ( GCDapplications ,
"GCD applications"  )

◆ STATISTIC() [15/33]

STATISTIC ( GCDindependence ,
"GCD independence"  )

◆ STATISTIC() [16/33]

STATISTIC ( GCDsuccesses ,
"GCD successes"  )

◆ STATISTIC() [17/33]

STATISTIC ( NonlinearSubscriptPairs ,
"Nonlinear subscript pairs"  )

◆ STATISTIC() [18/33]

STATISTIC ( SameSDLoopsCount ,
"Loops with Same iteration Space and Depth"  )

◆ STATISTIC() [19/33]

STATISTIC ( SeparableSubscriptPairs ,
"Separable subscript pairs"  )

◆ STATISTIC() [20/33]

STATISTIC ( StrongSIVapplications ,
"Strong SIV applications"  )

◆ STATISTIC() [21/33]

STATISTIC ( StrongSIVindependence ,
"Strong SIV independence"  )

◆ STATISTIC() [22/33]

STATISTIC ( StrongSIVsuccesses ,
"Strong SIV successes"  )

◆ STATISTIC() [23/33]

STATISTIC ( SymbolicRDIVapplications ,
"Symbolic RDIV applications"  )

◆ STATISTIC() [24/33]

STATISTIC ( SymbolicRDIVindependence ,
"Symbolic RDIV independence"  )

◆ STATISTIC() [25/33]

STATISTIC ( TotalArrayPairs ,
"Array pairs tested"  )

◆ STATISTIC() [26/33]

STATISTIC ( WeakCrossingSIVapplications ,
"Weak-Crossing SIV applications"  )

◆ STATISTIC() [27/33]

STATISTIC ( WeakCrossingSIVindependence ,
"Weak-Crossing SIV independence"  )

◆ STATISTIC() [28/33]

STATISTIC ( WeakCrossingSIVsuccesses ,
"Weak-Crossing SIV successes"  )

◆ STATISTIC() [29/33]

STATISTIC ( WeakZeroSIVapplications ,
"Weak-Zero SIV applications"  )

◆ STATISTIC() [30/33]

STATISTIC ( WeakZeroSIVindependence ,
"Weak-Zero SIV independence"  )

◆ STATISTIC() [31/33]

STATISTIC ( WeakZeroSIVsuccesses ,
"Weak-Zero SIV successes"  )

◆ STATISTIC() [32/33]

STATISTIC ( ZIVapplications ,
"ZIV applications"  )

◆ STATISTIC() [33/33]

STATISTIC ( ZIVindependence ,
"ZIV independence"  )

◆ underlyingObjectsAlias()

AliasResult underlyingObjectsAlias ( AAResults * AA,
const DataLayout & DL,
const MemoryLocation & LocA,
const MemoryLocation & LocB )
static

Definition at line 1069 of file DependenceAnalysis.cpp.

References llvm::MemoryLocation::AATags, DL, llvm::BatchAAResults::enableCrossIterationMode(), llvm::MemoryLocation::getBeforeOrAfter(), llvm::getUnderlyingObject(), llvm::isIdentifiedObject(), llvm::BatchAAResults::isNoAlias(), llvm::AliasResult::MayAlias, llvm::AliasResult::MustAlias, llvm::AliasResult::NoAlias, and llvm::MemoryLocation::Ptr.

Referenced by llvm::DependenceInfo::depends(), and llvm::DependenceInfo::getSplitIteration().

Variable Documentation

◆ Analysis

Dependence Analysis

Definition at line 199 of file DependenceAnalysis.cpp.

◆ da

da

Definition at line 199 of file DependenceAnalysis.cpp.

◆ Delinearize

cl::opt< bool > Delinearize("da-delinearize", cl::init(true), cl::Hidden, cl::desc("Try to delinearize array references.")) ( "da-delinearize" ,
cl::init(true) ,
cl::Hidden ,
cl::desc("Try to delinearize array references.")  )
static

Referenced by llvm::DependenceInfo::depends(), and llvm::DependenceInfo::getSplitIteration().

◆ DisableDelinearizationChecks

cl::opt< bool > DisableDelinearizationChecks("da-disable-delinearization-checks", cl::Hidden, cl::desc( "Disable checks that try to statically verify validity of " "delinearized subscripts. Enabling this option may result in incorrect " "dependence vectors for languages that allow the subscript of one " "dimension to underflow or overflow into another dimension.")) ( "da-disable-delinearization-checks" ,
cl::Hidden ,
cl::desc( "Disable checks that try to statically verify validity of " "delinearized subscripts. Enabling this option may result in incorrect " "dependence vectors for languages that allow the subscript of one " "dimension to underflow or overflow into another dimension.")  )
static

◆ DumpMonotonicityReport

cl::opt< bool > DumpMonotonicityReport("da-dump-monotonicity-report", cl::init(false), cl::Hidden, cl::desc( "When printing analysis, dump the results of monotonicity checks.")) ( "da-dump-monotonicity-report" ,
cl::init(false) ,
cl::Hidden ,
cl::desc( "When printing analysis, dump the results of monotonicity checks.")  )
static

Referenced by dumpExampleDependence().

◆ EnableDependenceTest

cl::opt< DependenceTestType > EnableDependenceTest("da-enable-dependence-test", cl::init(DependenceTestType::All), cl::ReallyHidden, cl::desc("Run only specified dependence test routine and disable others. " "The purpose is mainly to exclude the influence of other " "dependence test routines in regression tests. If set to All, all " "dependence test routines are enabled."), cl::values(clEnumValN(DependenceTestType::All, "all", "Enable all dependence test routines."), clEnumValN(DependenceTestType::StrongSIV, "strong-siv", "Enable only Strong SIV test."), clEnumValN(DependenceTestType::WeakCrossingSIV, "weak-crossing-siv", "Enable only Weak-Crossing SIV test."), clEnumValN(DependenceTestType::ExactSIV, "exact-siv", "Enable only Exact SIV test."), clEnumValN(DependenceTestType::WeakZeroSIV, "weak-zero-siv", "Enable only Weak-Zero SIV test."), clEnumValN(DependenceTestType::ExactRDIV, "exact-rdiv", "Enable only Exact RDIV test."), clEnumValN(DependenceTestType::SymbolicRDIV, "symbolic-rdiv", "Enable only Symbolic RDIV test."), clEnumValN(DependenceTestType::GCDMIV, "gcd-miv", "Enable only GCD MIV test."), clEnumValN(DependenceTestType::BanerjeeMIV, "banerjee-miv", "Enable only Banerjee MIV test."))) ( "da-enable-dependence-test" ,
cl::init(DependenceTestType::All) ,
cl::ReallyHidden ,
cl::desc("Run only specified dependence test routine and disable others. " "The purpose is mainly to exclude the influence of other " "dependence test routines in regression tests. If set to All, all " "dependence test routines are enabled.") ,
cl::values(clEnumValN(DependenceTestType::All, "all", "Enable all dependence test routines."), clEnumValN(DependenceTestType::StrongSIV, "strong-siv", "Enable only Strong SIV test."), clEnumValN(DependenceTestType::WeakCrossingSIV, "weak-crossing-siv", "Enable only Weak-Crossing SIV test."), clEnumValN(DependenceTestType::ExactSIV, "exact-siv", "Enable only Exact SIV test."), clEnumValN(DependenceTestType::WeakZeroSIV, "weak-zero-siv", "Enable only Weak-Zero SIV test."), clEnumValN(DependenceTestType::ExactRDIV, "exact-rdiv", "Enable only Exact RDIV test."), clEnumValN(DependenceTestType::SymbolicRDIV, "symbolic-rdiv", "Enable only Symbolic RDIV test."), clEnumValN(DependenceTestType::GCDMIV, "gcd-miv", "Enable only GCD MIV test."), clEnumValN(DependenceTestType::BanerjeeMIV, "banerjee-miv", "Enable only Banerjee MIV test."))  )
static

Referenced by isDependenceTestEnabled().

◆ EnableMonotonicityCheck

cl::opt< bool > EnableMonotonicityCheck("da-enable-monotonicity-check", cl::init(false), cl::Hidden, cl::desc("Check if the subscripts are monotonic. If it's not, dependence " "is reported as unknown.")) ( "da-enable-monotonicity-check" ,
cl::init(false) ,
cl::Hidden ,
cl::desc("Check if the subscripts are monotonic. If it's not, dependence " "is reported as unknown.")  )
static

Referenced by llvm::DependenceInfo::depends().

◆ MIVMaxLevelThreshold

cl::opt< unsigned > MIVMaxLevelThreshold("da-miv-max-level-threshold", cl::init(7), cl::Hidden, cl::desc("Maximum depth allowed for the recursive algorithm used to " "explore MIV direction vectors.")) ( "da-miv-max-level-threshold" ,
cl::init(7) ,
cl::Hidden ,
cl::desc("Maximum depth allowed for the recursive algorithm used to " "explore MIV direction vectors.")  )
static

◆ true

Dependence true

Definition at line 200 of file DependenceAnalysis.cpp.

Generated on for LLVM by doxygen 1.14.0