#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 const SCEV * | absSCEVNoSignedOverflow (const SCEV *A, ScalarEvolution &SE) |
Returns the absolute value of A. | |
| 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 > | getConstanCoefficient (const SCEV *Expr) |
| Given a SCEVMulExpr, returns its first operand if its first operand is a constant and the product doesn't overflow in a signed sense. | |
| 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
◆ absSCEVNoSignedOverflow()
|
static |
Returns the absolute value of A.
In the context of dependence analysis, we need an absolute value in a mathematical sense. If A is the signed minimum value, we cannot represent it unless extending the original type. Thus if we cannot prove that A is not the signed minimum value, returns nullptr.
Definition at line 1595 of file DependenceAnalysis.cpp.
References A(), llvm::cast(), llvm::ScalarEvolution::getAbsExpr(), llvm::ScalarEvolution::getConstant(), llvm::APInt::getSignedMinValue(), llvm::CmpInst::ICMP_NE, llvm::ScalarEvolution::isKnownPredicate(), and llvm::SMin.
◆ ceilingOfQuotient()
Definition at line 1984 of file DependenceAnalysis.cpp.
References A(), B(), and llvm::APInt::sdivrem().
Referenced by inferDomainOfAffine().
◆ dumpExampleDependence()
|
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()
|
static |
Definition at line 4056 of file DependenceAnalysis.cpp.
References llvm::dbgs(), llvm::SmallBitVector::find_next(), and llvm::SmallBitVector::set_bits().
Referenced by llvm::DependenceInfo::depends().
◆ findGCD()
|
static |
Definition at line 1942 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()
Definition at line 1972 of file DependenceAnalysis.cpp.
References A(), B(), and llvm::APInt::sdivrem().
Referenced by inferDomainOfAffine().
◆ getConstanCoefficient()
Given a SCEVMulExpr, returns its first operand if its first operand is a constant and the product doesn't overflow in a signed sense.
Otherwise, returns std::nullopt. For example, given (10 * X * Y)<nsw>, it returns 10. Notably, if it doesn't have nsw, the multiplication may overflow, and if so, it may not a multiple of 10.
Definition at line 2862 of file DependenceAnalysis.cpp.
References llvm::dyn_cast().
◆ inferDomainOfAffine()
|
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 2026 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()
|
static |
Returns true iff Test is enabled.
Definition at line 1608 of file DependenceAnalysis.cpp.
References EnableDependenceTest, and llvm::Test.
◆ isLoadOrStore()
|
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()
|
static |
Definition at line 2217 of file DependenceAnalysis.cpp.
References llvm::SCEVConstant::getAPInt(), and llvm::APInt::srem().
◆ minusSCEVNoSignedOverflow()
|
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 1583 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()
|
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
|
static |
Referenced by llvm::DependenceInfo::depends(), and llvm::DependenceInfo::getSplitIteration().
◆ DisableDelinearizationChecks
|
static |
◆ DumpMonotonicityReport
|
static |
Referenced by dumpExampleDependence().
◆ EnableDependenceTest
|
static |
Referenced by isDependenceTestEnabled().
◆ EnableMonotonicityCheck
|
static |
Referenced by llvm::DependenceInfo::depends().
◆ MIVMaxLevelThreshold
|
static |
◆ true
| Dependence true |
Definition at line 200 of file DependenceAnalysis.cpp.
Generated on for LLVM by
1.14.0