#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 (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 (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 std::optional< bool > | findGCD (unsigned Bits, const APInt &AM, const APInt &BM, const APInt &Delta, APInt &G, APInt &X, APInt &Y) |
| static OverflowSafeSignedAPInt | floorOfQuotient (const OverflowSafeSignedAPInt &OA, const OverflowSafeSignedAPInt &OB) |
| static OverflowSafeSignedAPInt | ceilingOfQuotient (const OverflowSafeSignedAPInt &OA, const OverflowSafeSignedAPInt &OB) |
| static std::pair< OverflowSafeSignedAPInt, OverflowSafeSignedAPInt > | inferDomainOfAffine (OverflowSafeSignedAPInt A, OverflowSafeSignedAPInt B, OverflowSafeSignedAPInt 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 > | getConstantCoefficient (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 BanerjeeInterval | addIntervals (const BanerjeeInterval &A, const BanerjeeInterval &B, ScalarEvolution &SE) |
| Add two intervals. | |
| static BanerjeeInterval | intersectIntervals (const BanerjeeInterval &A, const BanerjeeInterval &B, ScalarEvolution &SE) |
| Intersect two intervals. | |
| static BanerjeeInterval | constantInterval (const SCEV *C) |
Return the singleton interval containing C. | |
| static BanerjeeInterval | emptyInterval (Type *Ty, ScalarEvolution &SE) |
| Return the canonical empty interval [1, 0]. | |
| static BanerjeeInterval | signedRangeInterval (const SCEV *Coeff, const SCEV *Lower, const SCEV *Upper, ScalarEvolution &SE) |
Compute the range of Coeff * X for Lower <=s X <=s Upper. | |
| static BanerjeeInterval | variableInterval (const SCEV *Coeff, const SCEV *Upper, ScalarEvolution &SE) |
| Compute the range of Coeff * X for 0 <= X <= Upper. | |
| static BanerjeeInterval | strictDirectionIntervalWithUnknownUpperBound (const SCEV *ACoeff, const SCEV *BCoeff, unsigned char Direction, ScalarEvolution &SE) |
| Compute any finite one-sided bound on. | |
| static BanerjeeInterval | intervalFromValues (ArrayRef< const SCEV * > Values, ScalarEvolution &SE) |
| Return the smallest closed interval containing Values. | |
| static const SCEV * | evaluateSubscriptDifference (const SCEV *A, const SCEV *SrcIndex, const SCEV *B, const SCEV *DstIndex, ScalarEvolution &SE) |
| Evaluate one loop level's contribution A * SrcIndex - B * DstIndex to the complete source-minus-destination subscript difference. | |
| static Type * | getBanerjeeBaseType (const SCEV *Src, const SCEV *Dst, ScalarEvolution &SE) |
| Return the widest type used by a subscript or by an exact backedge-taken count of one of its recurrences. | |
| 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::Default), 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::Default, "default", "Enable all dependence test routines except " "Banerjee MIV (default)."), 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::GCDMIV, "gcd-miv", "Enable only GCD MIV test."), clEnumValN(DependenceTestType::BanerjeeMIV, "banerjee-miv", "Enable only Banerjee MIV test."))) |
| da | |
| Dependence | Analysis |
| Dependence | true |
Macro Definition Documentation
◆ DEBUG_TYPE
| #define DEBUG_TYPE "da" |
Definition at line 65 of file DependenceAnalysis.cpp.
Function Documentation
◆ addIntervals()
|
static |
Add two intervals.
A missing endpoint propagates the corresponding infinity.
Definition at line 1948 of file DependenceAnalysis.cpp.
References A(), B(), llvm::ScalarEvolution::getAddExpr(), llvm::Lower, and llvm::Upper.
◆ ceilingOfQuotient()
|
static |
Definition at line 1251 of file DependenceAnalysis.cpp.
References A(), B(), and llvm::APInt::sdivrem().
Referenced by inferDomainOfAffine().
◆ constantInterval()
Return the singleton interval containing C.
Definition at line 1976 of file DependenceAnalysis.cpp.
References C().
Referenced by variableInterval().
◆ dumpExampleDependence()
|
static |
Definition at line 303 of file DependenceAnalysis.cpp.
References assert(), D(), llvm::Dependence::DVEntry::EQ, F, llvm::inst_begin(), llvm::inst_end(), and llvm::SCEV::isZero().
Referenced by llvm::DependenceAnalysisWrapperPass::print(), and llvm::DependenceAnalysisPrinterPass::run().
◆ dumpSmallBitVector()
|
static |
Definition at line 2629 of file DependenceAnalysis.cpp.
References llvm::dbgs(), llvm::SmallBitVector::find_next(), and llvm::SmallBitVector::set_bits().
Referenced by llvm::DependenceInfo::depends().
◆ emptyInterval()
|
static |
Return the canonical empty interval [1, 0].
Definition at line 1981 of file DependenceAnalysis.cpp.
References llvm::ScalarEvolution::getOne(), and llvm::ScalarEvolution::getZero().
◆ evaluateSubscriptDifference()
|
static |
Evaluate one loop level's contribution A * SrcIndex - B * DstIndex to the complete source-minus-destination subscript difference.
Definition at line 2085 of file DependenceAnalysis.cpp.
References A(), B(), llvm::ScalarEvolution::getMinusSCEV(), and llvm::ScalarEvolution::getMulExpr().
◆ findGCD()
|
static |
Definition at line 1193 of file DependenceAnalysis.cpp.
References llvm::APInt::abs(), llvm::dbgs(), G, llvm::APInt::isMinSignedValue(), LLVM_DEBUG, llvm::APInt::sdiv(), llvm::APInt::sdivrem(), llvm::APInt::slt(), llvm::APInt::srem(), X, and Y.
◆ floorOfQuotient()
|
static |
Definition at line 1233 of file DependenceAnalysis.cpp.
References A(), B(), and llvm::APInt::sdivrem().
Referenced by inferDomainOfAffine().
◆ getBanerjeeBaseType()
Return the widest type used by a subscript or by an exact backedge-taken count of one of its recurrences.
Definition at line 2093 of file DependenceAnalysis.cpp.
References llvm::dyn_cast(), llvm::ScalarEvolution::getBackedgeTakenCount(), llvm::SCEVAddRecExpr::getLoop(), llvm::SCEVAddRecExpr::getStart(), llvm::SCEV::getType(), llvm::ScalarEvolution::getWiderType(), and llvm::isa().
◆ getConstantCoefficient()
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 1776 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 >=s 0
we can derive the following inequalities for k when A is positive:
k >=s -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 <=s UB
which leads to:
k <=s (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 and UB are non-negative.
Definition at line 1299 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.
◆ intersectIntervals()
|
static |
Intersect two intervals.
Both inputs conservatively contain the feasible values, so their intersection does too and may provide tighter one-sided bounds.
Definition at line 1963 of file DependenceAnalysis.cpp.
References A(), B(), llvm::ScalarEvolution::getSMaxExpr(), llvm::ScalarEvolution::getSMinExpr(), llvm::Lower, and llvm::Upper.
◆ intervalFromValues()
|
static |
Return the smallest closed interval containing Values.
Definition at line 2070 of file DependenceAnalysis.cpp.
References assert(), llvm::ScalarEvolution::getSMaxExpr(), llvm::ScalarEvolution::getSMinExpr(), llvm::Lower, llvm::Upper, and llvm::Values.
◆ isDependenceTestEnabled()
|
static |
Returns true iff Test is enabled.
Definition at line 900 of file DependenceAnalysis.cpp.
References EnableDependenceTest, and llvm::Test.
◆ isLoadOrStore()
|
static |
Definition at line 603 of file DependenceAnalysis.cpp.
References llvm::dyn_cast(), and I.
Referenced by llvm::DependenceInfo::depends().
◆ isRemainderZero()
|
static |
Definition at line 1361 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 892 of file DependenceAnalysis.cpp.
References A(), B(), llvm::ScalarEvolution::getMinusSCEV(), and llvm::ScalarEvolution::willNotOverflow().
◆ signedRangeInterval()
|
static |
Compute the range of Coeff * X for Lower <=s X <=s Upper.
Definition at line 1986 of file DependenceAnalysis.cpp.
References llvm::ScalarEvolution::getMulExpr(), llvm::ScalarEvolution::getSMaxExpr(), llvm::ScalarEvolution::getSMinExpr(), llvm::Lower, and llvm::Upper.
Referenced by variableInterval().
◆ STATISTIC() [1/25]
| STATISTIC | ( | BanerjeeApplications | , |
| "Banerjee applications" | ) |
◆ STATISTIC() [2/25]
| STATISTIC | ( | BanerjeeIndependence | , |
| "Banerjee independence" | ) |
◆ STATISTIC() [3/25]
| STATISTIC | ( | BanerjeeSuccesses | , |
| "Banerjee successes" | ) |
◆ STATISTIC() [4/25]
| STATISTIC | ( | ExactRDIVapplications | , |
| "Exact RDIV applications" | ) |
◆ STATISTIC() [5/25]
| STATISTIC | ( | ExactRDIVindependence | , |
| "Exact RDIV independence" | ) |
◆ STATISTIC() [6/25]
| STATISTIC | ( | ExactSIVapplications | , |
| "Exact SIV applications" | ) |
◆ STATISTIC() [7/25]
| STATISTIC | ( | ExactSIVindependence | , |
| "Exact SIV independence" | ) |
◆ STATISTIC() [8/25]
| STATISTIC | ( | ExactSIVsuccesses | , |
| "Exact SIV successes" | ) |
◆ STATISTIC() [9/25]
| STATISTIC | ( | GCDapplications | , |
| "GCD applications" | ) |
◆ STATISTIC() [10/25]
| STATISTIC | ( | GCDindependence | , |
| "GCD independence" | ) |
◆ STATISTIC() [11/25]
| STATISTIC | ( | GCDsuccesses | , |
| "GCD successes" | ) |
◆ STATISTIC() [12/25]
| STATISTIC | ( | NonlinearSubscriptPairs | , |
| "Nonlinear subscript pairs" | ) |
◆ STATISTIC() [13/25]
| STATISTIC | ( | SameSDLoopsCount | , |
| "Loops with Same iteration Space and Depth" | ) |
◆ STATISTIC() [14/25]
| STATISTIC | ( | StrongSIVapplications | , |
| "Strong SIV applications" | ) |
◆ STATISTIC() [15/25]
| STATISTIC | ( | StrongSIVindependence | , |
| "Strong SIV independence" | ) |
◆ STATISTIC() [16/25]
| STATISTIC | ( | StrongSIVsuccesses | , |
| "Strong SIV successes" | ) |
◆ STATISTIC() [17/25]
| STATISTIC | ( | TotalArrayPairs | , |
| "Array pairs tested" | ) |
◆ STATISTIC() [18/25]
| STATISTIC | ( | WeakCrossingSIVapplications | , |
| "Weak-Crossing SIV applications" | ) |
◆ STATISTIC() [19/25]
| STATISTIC | ( | WeakCrossingSIVindependence | , |
| "Weak-Crossing SIV independence" | ) |
◆ STATISTIC() [20/25]
| STATISTIC | ( | WeakCrossingSIVsuccesses | , |
| "Weak-Crossing SIV successes" | ) |
◆ STATISTIC() [21/25]
| STATISTIC | ( | WeakZeroSIVapplications | , |
| "Weak-Zero SIV applications" | ) |
◆ STATISTIC() [22/25]
| STATISTIC | ( | WeakZeroSIVindependence | , |
| "Weak-Zero SIV independence" | ) |
◆ STATISTIC() [23/25]
| STATISTIC | ( | WeakZeroSIVsuccesses | , |
| "Weak-Zero SIV successes" | ) |
◆ STATISTIC() [24/25]
| STATISTIC | ( | ZIVapplications | , |
| "ZIV applications" | ) |
◆ STATISTIC() [25/25]
| STATISTIC | ( | ZIVindependence | , |
| "ZIV independence" | ) |
◆ strictDirectionIntervalWithUnknownUpperBound()
|
static |
Compute any finite one-sided bound on.
A * SrcIndex - B * DstIndex
for a strict direction when no upper bound is known for the nonnegative normalized indices.
For SrcIndex < DstIndex, write DstIndex = SrcIndex + D, where D >= 1:
A * SrcIndex - B * DstIndex = (A - B) * SrcIndex + (-B) * D.
If A - B >= 0 and B <= 0, both terms increase with their nonnegative variables (SrcIndex and D), so the expression is bounded below by -B. If A - B <= 0 and B >= 0, it is bounded above by -B.
For SrcIndex > DstIndex, write SrcIndex = DstIndex + D:
A * SrcIndex - B * DstIndex = (A - B) * DstIndex + A * D.
If A - B >= 0 and A >= 0, the expression is bounded below by A. If A - B <= 0 and A <= 0, it is bounded above by A.
Definition at line 2039 of file DependenceAnalysis.cpp.
References llvm::ScalarEvolution::getMinusSCEV(), llvm::ScalarEvolution::getNegativeSCEV(), llvm::Dependence::DVEntry::GT, llvm::ScalarEvolution::isKnownNonNegative(), llvm::ScalarEvolution::isKnownNonPositive(), llvm_unreachable, llvm::Lower, llvm::Dependence::DVEntry::LT, and llvm::Upper.
◆ underlyingObjectsAlias()
|
static |
Definition at line 568 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().
◆ variableInterval()
|
static |
Compute the range of Coeff * X for 0 <= X <= Upper.
A null Upper denotes an unbounded nonnegative X.
Definition at line 2001 of file DependenceAnalysis.cpp.
References constantInterval(), llvm::SCEV::getType(), llvm::ScalarEvolution::getZero(), llvm::ScalarEvolution::isKnownNegative(), llvm::ScalarEvolution::isKnownNonNegative(), llvm::SCEV::isZero(), signedRangeInterval(), and llvm::Upper.
Variable Documentation
◆ Analysis
| Dependence Analysis |
Definition at line 175 of file DependenceAnalysis.cpp.
◆ da
| da |
Definition at line 175 of file DependenceAnalysis.cpp.
◆ Delinearize
|
static |
Referenced by llvm::DependenceInfo::depends().
◆ DisableDelinearizationChecks
|
static |
◆ EnableDependenceTest
|
static |
Referenced by isDependenceTestEnabled().
◆ MIVMaxLevelThreshold
|
static |
◆ true
| Dependence true |
Definition at line 176 of file DependenceAnalysis.cpp.
Generated on for LLVM by
1.14.0