llvm / llvm / 4fee3cff4d923744aa87dd87175a8b6f91deb4a0 / . / include / llvm / Analysis / DependenceAnalysis.h

//===-- llvm/Analysis/DependenceAnalysis.h -------------------- -*- 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 | |

// | |

//===----------------------------------------------------------------------===// | |

// | |

// DependenceAnalysis is an LLVM pass that analyses dependences between memory | |

// accesses. Currently, it is an implementation of the approach described in | |

// | |

// Practical Dependence Testing | |

// Goff, Kennedy, Tseng | |

// PLDI 1991 | |

// | |

// There's a single entry point that analyzes the dependence between a pair | |

// of memory references in a function, returning either NULL, for no dependence, | |

// or a more-or-less detailed description of the dependence between them. | |

// | |

// This pass exists to support the DependenceGraph pass. There are two separate | |

// passes because there's a useful separation of concerns. A dependence exists | |

// if two conditions are met: | |

// | |

// 1) Two instructions reference the same memory location, and | |

// 2) There is a flow of control leading from one instruction to the other. | |

// | |

// DependenceAnalysis attacks the first condition; DependenceGraph will attack | |

// the second (it's not yet ready). | |

// | |

// Please note that this is work in progress and the interface is subject to | |

// change. | |

// | |

// Plausible changes: | |

// Return a set of more precise dependences instead of just one dependence | |

// summarizing all. | |

// | |

//===----------------------------------------------------------------------===// | |

#ifndef LLVM_ANALYSIS_DEPENDENCEANALYSIS_H | |

#define LLVM_ANALYSIS_DEPENDENCEANALYSIS_H | |

#include "llvm/ADT/SmallBitVector.h" | |

#include "llvm/Analysis/AliasAnalysis.h" | |

#include "llvm/IR/Instructions.h" | |

#include "llvm/Pass.h" | |

namespace llvm { | |

template <typename T> class ArrayRef; | |

class Loop; | |

class LoopInfo; | |

class ScalarEvolution; | |

class SCEV; | |

class SCEVConstant; | |

class raw_ostream; | |

/// Dependence - This class represents a dependence between two memory | |

/// memory references in a function. It contains minimal information and | |

/// is used in the very common situation where the compiler is unable to | |

/// determine anything beyond the existence of a dependence; that is, it | |

/// represents a confused dependence (see also FullDependence). In most | |

/// cases (for output, flow, and anti dependences), the dependence implies | |

/// an ordering, where the source must precede the destination; in contrast, | |

/// input dependences are unordered. | |

/// | |

/// When a dependence graph is built, each Dependence will be a member of | |

/// the set of predecessor edges for its destination instruction and a set | |

/// if successor edges for its source instruction. These sets are represented | |

/// as singly-linked lists, with the "next" fields stored in the dependence | |

/// itelf. | |

class Dependence { | |

protected: | |

Dependence(Dependence &&) = default; | |

Dependence &operator=(Dependence &&) = default; | |

public: | |

Dependence(Instruction *Source, | |

Instruction *Destination) : | |

Src(Source), | |

Dst(Destination), | |

NextPredecessor(nullptr), | |

NextSuccessor(nullptr) {} | |

virtual ~Dependence() {} | |

/// Dependence::DVEntry - Each level in the distance/direction vector | |

/// has a direction (or perhaps a union of several directions), and | |

/// perhaps a distance. | |

struct DVEntry { | |

enum { NONE = 0, | |

LT = 1, | |

EQ = 2, | |

LE = 3, | |

GT = 4, | |

NE = 5, | |

GE = 6, | |

ALL = 7 }; | |

unsigned char Direction : 3; // Init to ALL, then refine. | |

bool Scalar : 1; // Init to true. | |

bool PeelFirst : 1; // Peeling the first iteration will break dependence. | |

bool PeelLast : 1; // Peeling the last iteration will break the dependence. | |

bool Splitable : 1; // Splitting the loop will break dependence. | |

const SCEV *Distance; // NULL implies no distance available. | |

DVEntry() : Direction(ALL), Scalar(true), PeelFirst(false), | |

PeelLast(false), Splitable(false), Distance(nullptr) { } | |

}; | |

/// getSrc - Returns the source instruction for this dependence. | |

/// | |

Instruction *getSrc() const { return Src; } | |

/// getDst - Returns the destination instruction for this dependence. | |

/// | |

Instruction *getDst() const { return Dst; } | |

/// isInput - Returns true if this is an input dependence. | |

/// | |

bool isInput() const; | |

/// isOutput - Returns true if this is an output dependence. | |

/// | |

bool isOutput() const; | |

/// isFlow - Returns true if this is a flow (aka true) dependence. | |

/// | |

bool isFlow() const; | |

/// isAnti - Returns true if this is an anti dependence. | |

/// | |

bool isAnti() const; | |

/// isOrdered - Returns true if dependence is Output, Flow, or Anti | |

/// | |

bool isOrdered() const { return isOutput() || isFlow() || isAnti(); } | |

/// isUnordered - Returns true if dependence is Input | |

/// | |

bool isUnordered() const { return isInput(); } | |

/// isLoopIndependent - Returns true if this is a loop-independent | |

/// dependence. | |

virtual bool isLoopIndependent() const { return true; } | |

/// isConfused - Returns true if this dependence is confused | |

/// (the compiler understands nothing and makes worst-case | |

/// assumptions). | |

virtual bool isConfused() const { return true; } | |

/// isConsistent - Returns true if this dependence is consistent | |

/// (occurs every time the source and destination are executed). | |

virtual bool isConsistent() const { return false; } | |

/// getLevels - Returns the number of common loops surrounding the | |

/// source and destination of the dependence. | |

virtual unsigned getLevels() const { return 0; } | |

/// getDirection - Returns the direction associated with a particular | |

/// level. | |

virtual unsigned getDirection(unsigned Level) const { return DVEntry::ALL; } | |

/// getDistance - Returns the distance (or NULL) associated with a | |

/// particular level. | |

virtual const SCEV *getDistance(unsigned Level) const { return nullptr; } | |

/// isPeelFirst - Returns true if peeling the first iteration from | |

/// this loop will break this dependence. | |

virtual bool isPeelFirst(unsigned Level) const { return false; } | |

/// isPeelLast - Returns true if peeling the last iteration from | |

/// this loop will break this dependence. | |

virtual bool isPeelLast(unsigned Level) const { return false; } | |

/// isSplitable - Returns true if splitting this loop will break | |

/// the dependence. | |

virtual bool isSplitable(unsigned Level) const { return false; } | |

/// isScalar - Returns true if a particular level is scalar; that is, | |

/// if no subscript in the source or destination mention the induction | |

/// variable associated with the loop at this level. | |

virtual bool isScalar(unsigned Level) const; | |

/// getNextPredecessor - Returns the value of the NextPredecessor | |

/// field. | |

const Dependence *getNextPredecessor() const { return NextPredecessor; } | |

/// getNextSuccessor - Returns the value of the NextSuccessor | |

/// field. | |

const Dependence *getNextSuccessor() const { return NextSuccessor; } | |

/// setNextPredecessor - Sets the value of the NextPredecessor | |

/// field. | |

void setNextPredecessor(const Dependence *pred) { NextPredecessor = pred; } | |

/// setNextSuccessor - Sets the value of the NextSuccessor | |

/// field. | |

void setNextSuccessor(const Dependence *succ) { NextSuccessor = succ; } | |

/// dump - For debugging purposes, dumps a dependence to OS. | |

/// | |

void dump(raw_ostream &OS) const; | |

private: | |

Instruction *Src, *Dst; | |

const Dependence *NextPredecessor, *NextSuccessor; | |

friend class DependenceInfo; | |

}; | |

/// FullDependence - This class represents a dependence between two memory | |

/// references in a function. It contains detailed information about the | |

/// dependence (direction vectors, etc.) and is used when the compiler is | |

/// able to accurately analyze the interaction of the references; that is, | |

/// it is not a confused dependence (see Dependence). In most cases | |

/// (for output, flow, and anti dependences), the dependence implies an | |

/// ordering, where the source must precede the destination; in contrast, | |

/// input dependences are unordered. | |

class FullDependence final : public Dependence { | |

public: | |

FullDependence(Instruction *Src, Instruction *Dst, bool LoopIndependent, | |

unsigned Levels); | |

/// isLoopIndependent - Returns true if this is a loop-independent | |

/// dependence. | |

bool isLoopIndependent() const override { return LoopIndependent; } | |

/// isConfused - Returns true if this dependence is confused | |

/// (the compiler understands nothing and makes worst-case | |

/// assumptions). | |

bool isConfused() const override { return false; } | |

/// isConsistent - Returns true if this dependence is consistent | |

/// (occurs every time the source and destination are executed). | |

bool isConsistent() const override { return Consistent; } | |

/// getLevels - Returns the number of common loops surrounding the | |

/// source and destination of the dependence. | |

unsigned getLevels() const override { return Levels; } | |

/// getDirection - Returns the direction associated with a particular | |

/// level. | |

unsigned getDirection(unsigned Level) const override; | |

/// getDistance - Returns the distance (or NULL) associated with a | |

/// particular level. | |

const SCEV *getDistance(unsigned Level) const override; | |

/// isPeelFirst - Returns true if peeling the first iteration from | |

/// this loop will break this dependence. | |

bool isPeelFirst(unsigned Level) const override; | |

/// isPeelLast - Returns true if peeling the last iteration from | |

/// this loop will break this dependence. | |

bool isPeelLast(unsigned Level) const override; | |

/// isSplitable - Returns true if splitting the loop will break | |

/// the dependence. | |

bool isSplitable(unsigned Level) const override; | |

/// isScalar - Returns true if a particular level is scalar; that is, | |

/// if no subscript in the source or destination mention the induction | |

/// variable associated with the loop at this level. | |

bool isScalar(unsigned Level) const override; | |

private: | |

unsigned short Levels; | |

bool LoopIndependent; | |

bool Consistent; // Init to true, then refine. | |

std::unique_ptr<DVEntry[]> DV; | |

friend class DependenceInfo; | |

}; | |

/// DependenceInfo - This class is the main dependence-analysis driver. | |

/// | |

class DependenceInfo { | |

public: | |

DependenceInfo(Function *F, AliasAnalysis *AA, ScalarEvolution *SE, | |

LoopInfo *LI) | |

: AA(AA), SE(SE), LI(LI), F(F) {} | |

/// Handle transitive invalidation when the cached analysis results go away. | |

bool invalidate(Function &F, const PreservedAnalyses &PA, | |

FunctionAnalysisManager::Invalidator &Inv); | |

/// depends - Tests for a dependence between the Src and Dst instructions. | |

/// Returns NULL if no dependence; otherwise, returns a Dependence (or a | |

/// FullDependence) with as much information as can be gleaned. | |

/// The flag PossiblyLoopIndependent should be set by the caller | |

/// if it appears that control flow can reach from Src to Dst | |

/// without traversing a loop back edge. | |

std::unique_ptr<Dependence> depends(Instruction *Src, | |

Instruction *Dst, | |

bool PossiblyLoopIndependent); | |

/// getSplitIteration - Give a dependence that's splittable at some | |

/// particular level, return the iteration that should be used to split | |

/// the loop. | |

/// | |

/// Generally, the dependence analyzer will be used to build | |

/// a dependence graph for a function (basically a map from instructions | |

/// to dependences). Looking for cycles in the graph shows us loops | |

/// that cannot be trivially vectorized/parallelized. | |

/// | |

/// We can try to improve the situation by examining all the dependences | |

/// that make up the cycle, looking for ones we can break. | |

/// Sometimes, peeling the first or last iteration of a loop will break | |

/// dependences, and there are flags for those possibilities. | |

/// Sometimes, splitting a loop at some other iteration will do the trick, | |

/// and we've got a flag for that case. Rather than waste the space to | |

/// record the exact iteration (since we rarely know), we provide | |

/// a method that calculates the iteration. It's a drag that it must work | |

/// from scratch, but wonderful in that it's possible. | |

/// | |

/// Here's an example: | |

/// | |

/// for (i = 0; i < 10; i++) | |

/// A[i] = ... | |

/// ... = A[11 - i] | |

/// | |

/// There's a loop-carried flow dependence from the store to the load, | |

/// found by the weak-crossing SIV test. The dependence will have a flag, | |

/// indicating that the dependence can be broken by splitting the loop. | |

/// Calling getSplitIteration will return 5. | |

/// Splitting the loop breaks the dependence, like so: | |

/// | |

/// for (i = 0; i <= 5; i++) | |

/// A[i] = ... | |

/// ... = A[11 - i] | |

/// for (i = 6; i < 10; i++) | |

/// A[i] = ... | |

/// ... = A[11 - i] | |

/// | |

/// breaks the dependence and allows us to vectorize/parallelize | |

/// both loops. | |

const SCEV *getSplitIteration(const Dependence &Dep, unsigned Level); | |

Function *getFunction() const { return F; } | |

private: | |

AliasAnalysis *AA; | |

ScalarEvolution *SE; | |

LoopInfo *LI; | |

Function *F; | |

/// Subscript - This private struct represents a pair of subscripts from | |

/// a pair of potentially multi-dimensional array references. We use a | |

/// vector of them to guide subscript partitioning. | |

struct Subscript { | |

const SCEV *Src; | |

const SCEV *Dst; | |

enum ClassificationKind { ZIV, SIV, RDIV, MIV, NonLinear } Classification; | |

SmallBitVector Loops; | |

SmallBitVector GroupLoops; | |

SmallBitVector Group; | |

}; | |

struct CoefficientInfo { | |

const SCEV *Coeff; | |

const SCEV *PosPart; | |

const SCEV *NegPart; | |

const SCEV *Iterations; | |

}; | |

struct BoundInfo { | |

const SCEV *Iterations; | |

const SCEV *Upper[8]; | |

const SCEV *Lower[8]; | |

unsigned char Direction; | |

unsigned char DirSet; | |

}; | |

/// Constraint - This private class represents a constraint, as defined | |

/// in the paper | |

/// | |

/// Practical Dependence Testing | |

/// Goff, Kennedy, Tseng | |

/// PLDI 1991 | |

/// | |

/// There are 5 kinds of constraint, in a hierarchy. | |

/// 1) Any - indicates no constraint, any dependence is possible. | |

/// 2) Line - A line ax + by = c, where a, b, and c are parameters, | |

/// representing the dependence equation. | |

/// 3) Distance - The value d of the dependence distance; | |

/// 4) Point - A point <x, y> representing the dependence from | |

/// iteration x to iteration y. | |

/// 5) Empty - No dependence is possible. | |

class Constraint { | |

private: | |

enum ConstraintKind { Empty, Point, Distance, Line, Any } Kind; | |

ScalarEvolution *SE; | |

const SCEV *A; | |

const SCEV *B; | |

const SCEV *C; | |

const Loop *AssociatedLoop; | |

public: | |

/// isEmpty - Return true if the constraint is of kind Empty. | |

bool isEmpty() const { return Kind == Empty; } | |

/// isPoint - Return true if the constraint is of kind Point. | |

bool isPoint() const { return Kind == Point; } | |

/// isDistance - Return true if the constraint is of kind Distance. | |

bool isDistance() const { return Kind == Distance; } | |

/// isLine - Return true if the constraint is of kind Line. | |

/// Since Distance's can also be represented as Lines, we also return | |

/// true if the constraint is of kind Distance. | |

bool isLine() const { return Kind == Line || Kind == Distance; } | |

/// isAny - Return true if the constraint is of kind Any; | |

bool isAny() const { return Kind == Any; } | |

/// getX - If constraint is a point <X, Y>, returns X. | |

/// Otherwise assert. | |

const SCEV *getX() const; | |

/// getY - If constraint is a point <X, Y>, returns Y. | |

/// Otherwise assert. | |

const SCEV *getY() const; | |

/// getA - If constraint is a line AX + BY = C, returns A. | |

/// Otherwise assert. | |

const SCEV *getA() const; | |

/// getB - If constraint is a line AX + BY = C, returns B. | |

/// Otherwise assert. | |

const SCEV *getB() const; | |

/// getC - If constraint is a line AX + BY = C, returns C. | |

/// Otherwise assert. | |

const SCEV *getC() const; | |

/// getD - If constraint is a distance, returns D. | |

/// Otherwise assert. | |

const SCEV *getD() const; | |

/// getAssociatedLoop - Returns the loop associated with this constraint. | |

const Loop *getAssociatedLoop() const; | |

/// setPoint - Change a constraint to Point. | |

void setPoint(const SCEV *X, const SCEV *Y, const Loop *CurrentLoop); | |

/// setLine - Change a constraint to Line. | |

void setLine(const SCEV *A, const SCEV *B, | |

const SCEV *C, const Loop *CurrentLoop); | |

/// setDistance - Change a constraint to Distance. | |

void setDistance(const SCEV *D, const Loop *CurrentLoop); | |

/// setEmpty - Change a constraint to Empty. | |

void setEmpty(); | |

/// setAny - Change a constraint to Any. | |

void setAny(ScalarEvolution *SE); | |

/// dump - For debugging purposes. Dumps the constraint | |

/// out to OS. | |

void dump(raw_ostream &OS) const; | |

}; | |

/// establishNestingLevels - Examines the loop nesting of the Src and Dst | |

/// instructions and establishes their shared loops. Sets the variables | |

/// CommonLevels, SrcLevels, and MaxLevels. | |

/// The source and destination instructions needn't be contained in the same | |

/// loop. The routine establishNestingLevels finds the level of most deeply | |

/// nested loop that contains them both, CommonLevels. An instruction that's | |

/// not contained in a loop is at level = 0. MaxLevels is equal to the level | |

/// of the source plus the level of the destination, minus CommonLevels. | |

/// This lets us allocate vectors MaxLevels in length, with room for every | |

/// distinct loop referenced in both the source and destination subscripts. | |

/// The variable SrcLevels is the nesting depth of the source instruction. | |

/// It's used to help calculate distinct loops referenced by the destination. | |

/// Here's the map from loops to levels: | |

/// 0 - unused | |

/// 1 - outermost common loop | |

/// ... - other common loops | |

/// CommonLevels - innermost common loop | |

/// ... - loops containing Src but not Dst | |

/// SrcLevels - innermost loop containing Src but not Dst | |

/// ... - loops containing Dst but not Src | |

/// MaxLevels - innermost loop containing Dst but not Src | |

/// Consider the follow code fragment: | |

/// for (a = ...) { | |

/// for (b = ...) { | |

/// for (c = ...) { | |

/// for (d = ...) { | |

/// A[] = ...; | |

/// } | |

/// } | |

/// for (e = ...) { | |

/// for (f = ...) { | |

/// for (g = ...) { | |

/// ... = A[]; | |

/// } | |

/// } | |

/// } | |

/// } | |

/// } | |

/// If we're looking at the possibility of a dependence between the store | |

/// to A (the Src) and the load from A (the Dst), we'll note that they | |

/// have 2 loops in common, so CommonLevels will equal 2 and the direction | |

/// vector for Result will have 2 entries. SrcLevels = 4 and MaxLevels = 7. | |

/// A map from loop names to level indices would look like | |

/// a - 1 | |

/// b - 2 = CommonLevels | |

/// c - 3 | |

/// d - 4 = SrcLevels | |

/// e - 5 | |

/// f - 6 | |

/// g - 7 = MaxLevels | |

void establishNestingLevels(const Instruction *Src, | |

const Instruction *Dst); | |

unsigned CommonLevels, SrcLevels, MaxLevels; | |

/// mapSrcLoop - Given one of the loops containing the source, return | |

/// its level index in our numbering scheme. | |

unsigned mapSrcLoop(const Loop *SrcLoop) const; | |

/// mapDstLoop - Given one of the loops containing the destination, | |

/// return its level index in our numbering scheme. | |

unsigned mapDstLoop(const Loop *DstLoop) const; | |

/// isLoopInvariant - Returns true if Expression is loop invariant | |

/// in LoopNest. | |

bool isLoopInvariant(const SCEV *Expression, const Loop *LoopNest) const; | |

/// Makes sure all subscript pairs share the same integer type by | |

/// sign-extending as necessary. | |

/// Sign-extending a subscript is safe because getelementptr assumes the | |

/// array subscripts are signed. | |

void unifySubscriptType(ArrayRef<Subscript *> Pairs); | |

/// removeMatchingExtensions - Examines a subscript pair. | |

/// If the source and destination are identically sign (or zero) | |

/// extended, it strips off the extension in an effort to | |

/// simplify the actual analysis. | |

void removeMatchingExtensions(Subscript *Pair); | |

/// collectCommonLoops - Finds the set of loops from the LoopNest that | |

/// have a level <= CommonLevels and are referred to by the SCEV Expression. | |

void collectCommonLoops(const SCEV *Expression, | |

const Loop *LoopNest, | |

SmallBitVector &Loops) const; | |

/// checkSrcSubscript - Examines the SCEV Src, returning true iff it's | |

/// linear. Collect the set of loops mentioned by Src. | |

bool checkSrcSubscript(const SCEV *Src, | |

const Loop *LoopNest, | |

SmallBitVector &Loops); | |

/// checkDstSubscript - Examines the SCEV Dst, returning true iff it's | |

/// linear. Collect the set of loops mentioned by Dst. | |

bool checkDstSubscript(const SCEV *Dst, | |

const Loop *LoopNest, | |

SmallBitVector &Loops); | |

/// isKnownPredicate - Compare X and Y using the predicate Pred. | |

/// Basically a wrapper for SCEV::isKnownPredicate, | |

/// but tries harder, especially in the presence of sign and zero | |

/// extensions and symbolics. | |

bool isKnownPredicate(ICmpInst::Predicate Pred, | |

const SCEV *X, | |

const SCEV *Y) const; | |

/// isKnownLessThan - Compare to see if S is less than Size | |

/// Another wrapper for isKnownNegative(S - max(Size, 1)) with some extra | |

/// checking if S is an AddRec and we can prove lessthan using the loop | |

/// bounds. | |

bool isKnownLessThan(const SCEV *S, const SCEV *Size) const; | |

/// isKnownNonNegative - Compare to see if S is known not to be negative | |

/// Uses the fact that S comes from Ptr, which may be an inbound GEP, | |

/// Proving there is no wrapping going on. | |

bool isKnownNonNegative(const SCEV *S, const Value *Ptr) const; | |

/// collectUpperBound - All subscripts are the same type (on my machine, | |

/// an i64). The loop bound may be a smaller type. collectUpperBound | |

/// find the bound, if available, and zero extends it to the Type T. | |

/// (I zero extend since the bound should always be >= 0.) | |

/// If no upper bound is available, return NULL. | |

const SCEV *collectUpperBound(const Loop *l, Type *T) const; | |

/// collectConstantUpperBound - Calls collectUpperBound(), then | |

/// attempts to cast it to SCEVConstant. If the cast fails, | |

/// returns NULL. | |

const SCEVConstant *collectConstantUpperBound(const Loop *l, Type *T) const; | |

/// classifyPair - Examines the subscript pair (the Src and Dst SCEVs) | |

/// and classifies it as either ZIV, SIV, RDIV, MIV, or Nonlinear. | |

/// Collects the associated loops in a set. | |

Subscript::ClassificationKind classifyPair(const SCEV *Src, | |

const Loop *SrcLoopNest, | |

const SCEV *Dst, | |

const Loop *DstLoopNest, | |

SmallBitVector &Loops); | |

/// testZIV - Tests the ZIV subscript pair (Src and Dst) for dependence. | |

/// Returns true if any possible dependence is disproved. | |

/// If there might be a dependence, returns false. | |

/// If the dependence isn't proven to exist, | |

/// marks the Result as inconsistent. | |

bool testZIV(const SCEV *Src, | |

const SCEV *Dst, | |

FullDependence &Result) const; | |

/// testSIV - Tests the SIV subscript pair (Src and Dst) for dependence. | |

/// Things of the form [c1 + a1*i] and [c2 + a2*j], where | |

/// i and j are induction variables, c1 and c2 are loop invariant, | |

/// and a1 and a2 are constant. | |

/// Returns true if any possible dependence is disproved. | |

/// If there might be a dependence, returns false. | |

/// Sets appropriate direction vector entry and, when possible, | |

/// the distance vector entry. | |

/// If the dependence isn't proven to exist, | |

/// marks the Result as inconsistent. | |

bool testSIV(const SCEV *Src, | |

const SCEV *Dst, | |

unsigned &Level, | |

FullDependence &Result, | |

Constraint &NewConstraint, | |

const SCEV *&SplitIter) const; | |

/// testRDIV - Tests the RDIV subscript pair (Src and Dst) for dependence. | |

/// Things of the form [c1 + a1*i] and [c2 + a2*j] | |

/// where i and j are induction variables, c1 and c2 are loop invariant, | |

/// and a1 and a2 are constant. | |

/// With minor algebra, this test can also be used for things like | |

/// [c1 + a1*i + a2*j][c2]. | |

/// Returns true if any possible dependence is disproved. | |

/// If there might be a dependence, returns false. | |

/// Marks the Result as inconsistent. | |

bool testRDIV(const SCEV *Src, | |

const SCEV *Dst, | |

FullDependence &Result) const; | |

/// testMIV - Tests the MIV subscript pair (Src and Dst) for dependence. | |

/// Returns true if dependence disproved. | |

/// Can sometimes refine direction vectors. | |

bool testMIV(const SCEV *Src, | |

const SCEV *Dst, | |

const SmallBitVector &Loops, | |

FullDependence &Result) const; | |

/// strongSIVtest - Tests the strong SIV subscript pair (Src and Dst) | |

/// for dependence. | |

/// Things of the form [c1 + a*i] and [c2 + a*i], | |

/// where i is an induction variable, c1 and c2 are loop invariant, | |

/// and a is a constant | |

/// Returns true if any possible dependence is disproved. | |

/// If there might be a dependence, returns false. | |

/// Sets appropriate direction and distance. | |

bool strongSIVtest(const SCEV *Coeff, | |

const SCEV *SrcConst, | |

const SCEV *DstConst, | |

const Loop *CurrentLoop, | |

unsigned Level, | |

FullDependence &Result, | |

Constraint &NewConstraint) const; | |

/// weakCrossingSIVtest - Tests the weak-crossing SIV subscript pair | |

/// (Src and Dst) for dependence. | |

/// Things of the form [c1 + a*i] and [c2 - a*i], | |

/// where i is an induction variable, c1 and c2 are loop invariant, | |

/// and a is a constant. | |

/// Returns true if any possible dependence is disproved. | |

/// If there might be a dependence, returns false. | |

/// Sets appropriate direction entry. | |

/// Set consistent to false. | |

/// Marks the dependence as splitable. | |

bool weakCrossingSIVtest(const SCEV *SrcCoeff, | |

const SCEV *SrcConst, | |

const SCEV *DstConst, | |

const Loop *CurrentLoop, | |

unsigned Level, | |

FullDependence &Result, | |

Constraint &NewConstraint, | |

const SCEV *&SplitIter) const; | |

/// ExactSIVtest - Tests the SIV subscript pair | |

/// (Src and Dst) for dependence. | |

/// Things of the form [c1 + a1*i] and [c2 + a2*i], | |

/// where i is an induction variable, c1 and c2 are loop invariant, | |

/// and a1 and a2 are constant. | |

/// Returns true if any possible dependence is disproved. | |

/// If there might be a dependence, returns false. | |

/// Sets appropriate direction entry. | |

/// Set consistent to false. | |

bool exactSIVtest(const SCEV *SrcCoeff, | |

const SCEV *DstCoeff, | |

const SCEV *SrcConst, | |

const SCEV *DstConst, | |

const Loop *CurrentLoop, | |

unsigned Level, | |

FullDependence &Result, | |

Constraint &NewConstraint) const; | |

/// weakZeroSrcSIVtest - Tests the weak-zero SIV subscript pair | |

/// (Src and Dst) for dependence. | |

/// Things of the form [c1] and [c2 + a*i], | |

/// where i is an induction variable, c1 and c2 are loop invariant, | |

/// and a is a constant. See also weakZeroDstSIVtest. | |

/// Returns true if any possible dependence is disproved. | |

/// If there might be a dependence, returns false. | |

/// Sets appropriate direction entry. | |

/// Set consistent to false. | |

/// If loop peeling will break the dependence, mark appropriately. | |

bool weakZeroSrcSIVtest(const SCEV *DstCoeff, | |

const SCEV *SrcConst, | |

const SCEV *DstConst, | |

const Loop *CurrentLoop, | |

unsigned Level, | |

FullDependence &Result, | |

Constraint &NewConstraint) const; | |

/// weakZeroDstSIVtest - Tests the weak-zero SIV subscript pair | |

/// (Src and Dst) for dependence. | |

/// Things of the form [c1 + a*i] and [c2], | |

/// where i is an induction variable, c1 and c2 are loop invariant, | |

/// and a is a constant. See also weakZeroSrcSIVtest. | |

/// Returns true if any possible dependence is disproved. | |

/// If there might be a dependence, returns false. | |

/// Sets appropriate direction entry. | |

/// Set consistent to false. | |

/// If loop peeling will break the dependence, mark appropriately. | |

bool weakZeroDstSIVtest(const SCEV *SrcCoeff, | |

const SCEV *SrcConst, | |

const SCEV *DstConst, | |

const Loop *CurrentLoop, | |

unsigned Level, | |

FullDependence &Result, | |

Constraint &NewConstraint) const; | |

/// exactRDIVtest - Tests the RDIV subscript pair for dependence. | |

/// Things of the form [c1 + a*i] and [c2 + b*j], | |

/// where i and j are induction variable, c1 and c2 are loop invariant, | |

/// and a and b are constants. | |

/// Returns true if any possible dependence is disproved. | |

/// Marks the result as inconsistent. | |

/// Works in some cases that symbolicRDIVtest doesn't, | |

/// and vice versa. | |

bool exactRDIVtest(const SCEV *SrcCoeff, | |

const SCEV *DstCoeff, | |

const SCEV *SrcConst, | |

const SCEV *DstConst, | |

const Loop *SrcLoop, | |

const Loop *DstLoop, | |

FullDependence &Result) const; | |

/// symbolicRDIVtest - Tests the RDIV subscript pair for dependence. | |

/// Things of the form [c1 + a*i] and [c2 + b*j], | |

/// where i and j are induction variable, c1 and c2 are loop invariant, | |

/// and a and b are constants. | |

/// Returns true if any possible dependence is disproved. | |

/// Marks the result as inconsistent. | |

/// Works in some cases that exactRDIVtest doesn't, | |

/// and vice versa. Can also be used as a backup for | |

/// ordinary SIV tests. | |

bool symbolicRDIVtest(const SCEV *SrcCoeff, | |

const SCEV *DstCoeff, | |

const SCEV *SrcConst, | |

const SCEV *DstConst, | |

const Loop *SrcLoop, | |

const Loop *DstLoop) const; | |

/// gcdMIVtest - Tests an MIV subscript pair for dependence. | |

/// Returns true if any possible dependence is disproved. | |

/// Marks the result as inconsistent. | |

/// Can sometimes disprove the equal direction for 1 or more loops. | |

// Can handle some symbolics that even the SIV tests don't get, | |

/// so we use it as a backup for everything. | |

bool gcdMIVtest(const SCEV *Src, | |

const SCEV *Dst, | |

FullDependence &Result) const; | |

/// banerjeeMIVtest - Tests an MIV subscript pair for dependence. | |

/// Returns true if any possible dependence is disproved. | |

/// Marks the result as inconsistent. | |

/// Computes directions. | |

bool banerjeeMIVtest(const SCEV *Src, | |

const SCEV *Dst, | |

const SmallBitVector &Loops, | |

FullDependence &Result) const; | |

/// collectCoefficientInfo - Walks through the subscript, | |

/// collecting each coefficient, the associated loop bounds, | |

/// and recording its positive and negative parts for later use. | |

CoefficientInfo *collectCoeffInfo(const SCEV *Subscript, | |

bool SrcFlag, | |

const SCEV *&Constant) const; | |

/// getPositivePart - X^+ = max(X, 0). | |

/// | |

const SCEV *getPositivePart(const SCEV *X) const; | |

/// getNegativePart - X^- = min(X, 0). | |

/// | |

const SCEV *getNegativePart(const SCEV *X) const; | |

/// getLowerBound - Looks through all the bounds info and | |

/// computes the lower bound given the current direction settings | |

/// at each level. | |

const SCEV *getLowerBound(BoundInfo *Bound) const; | |

/// getUpperBound - Looks through all the bounds info and | |

/// computes the upper bound given the current direction settings | |

/// at each level. | |

const SCEV *getUpperBound(BoundInfo *Bound) const; | |

/// exploreDirections - Hierarchically expands the direction vector | |

/// search space, combining the directions of discovered dependences | |

/// in the DirSet field of Bound. Returns the number of distinct | |

/// dependences discovered. If the dependence is disproved, | |

/// it will return 0. | |

unsigned exploreDirections(unsigned Level, | |

CoefficientInfo *A, | |

CoefficientInfo *B, | |

BoundInfo *Bound, | |

const SmallBitVector &Loops, | |

unsigned &DepthExpanded, | |

const SCEV *Delta) const; | |

/// testBounds - Returns true iff the current bounds are plausible. | |

bool testBounds(unsigned char DirKind, | |

unsigned Level, | |

BoundInfo *Bound, | |

const SCEV *Delta) const; | |

/// findBoundsALL - Computes the upper and lower bounds for level K | |

/// using the * direction. Records them in Bound. | |

void findBoundsALL(CoefficientInfo *A, | |

CoefficientInfo *B, | |

BoundInfo *Bound, | |

unsigned K) const; | |

/// findBoundsLT - Computes the upper and lower bounds for level K | |

/// using the < direction. Records them in Bound. | |

void findBoundsLT(CoefficientInfo *A, | |

CoefficientInfo *B, | |

BoundInfo *Bound, | |

unsigned K) const; | |

/// findBoundsGT - Computes the upper and lower bounds for level K | |

/// using the > direction. Records them in Bound. | |

void findBoundsGT(CoefficientInfo *A, | |

CoefficientInfo *B, | |

BoundInfo *Bound, | |

unsigned K) const; | |

/// findBoundsEQ - Computes the upper and lower bounds for level K | |

/// using the = direction. Records them in Bound. | |

void findBoundsEQ(CoefficientInfo *A, | |

CoefficientInfo *B, | |

BoundInfo *Bound, | |

unsigned K) const; | |

/// intersectConstraints - Updates X with the intersection | |

/// of the Constraints X and Y. Returns true if X has changed. | |

bool intersectConstraints(Constraint *X, | |

const Constraint *Y); | |

/// propagate - Review the constraints, looking for opportunities | |

/// to simplify a subscript pair (Src and Dst). | |

/// Return true if some simplification occurs. | |

/// If the simplification isn't exact (that is, if it is conservative | |

/// in terms of dependence), set consistent to false. | |

bool propagate(const SCEV *&Src, | |

const SCEV *&Dst, | |

SmallBitVector &Loops, | |

SmallVectorImpl<Constraint> &Constraints, | |

bool &Consistent); | |

/// propagateDistance - Attempt to propagate a distance | |

/// constraint into a subscript pair (Src and Dst). | |

/// Return true if some simplification occurs. | |

/// If the simplification isn't exact (that is, if it is conservative | |

/// in terms of dependence), set consistent to false. | |

bool propagateDistance(const SCEV *&Src, | |

const SCEV *&Dst, | |

Constraint &CurConstraint, | |

bool &Consistent); | |

/// propagatePoint - Attempt to propagate a point | |

/// constraint into a subscript pair (Src and Dst). | |

/// Return true if some simplification occurs. | |

bool propagatePoint(const SCEV *&Src, | |

const SCEV *&Dst, | |

Constraint &CurConstraint); | |

/// propagateLine - Attempt to propagate a line | |

/// constraint into a subscript pair (Src and Dst). | |

/// Return true if some simplification occurs. | |

/// If the simplification isn't exact (that is, if it is conservative | |

/// in terms of dependence), set consistent to false. | |

bool propagateLine(const SCEV *&Src, | |

const SCEV *&Dst, | |

Constraint &CurConstraint, | |

bool &Consistent); | |

/// findCoefficient - Given a linear SCEV, | |

/// return the coefficient corresponding to specified loop. | |

/// If there isn't one, return the SCEV constant 0. | |

/// For example, given a*i + b*j + c*k, returning the coefficient | |

/// corresponding to the j loop would yield b. | |

const SCEV *findCoefficient(const SCEV *Expr, | |

const Loop *TargetLoop) const; | |

/// zeroCoefficient - Given a linear SCEV, | |

/// return the SCEV given by zeroing out the coefficient | |

/// corresponding to the specified loop. | |

/// For example, given a*i + b*j + c*k, zeroing the coefficient | |

/// corresponding to the j loop would yield a*i + c*k. | |

const SCEV *zeroCoefficient(const SCEV *Expr, | |

const Loop *TargetLoop) const; | |

/// addToCoefficient - Given a linear SCEV Expr, | |

/// return the SCEV given by adding some Value to the | |

/// coefficient corresponding to the specified TargetLoop. | |

/// For example, given a*i + b*j + c*k, adding 1 to the coefficient | |

/// corresponding to the j loop would yield a*i + (b+1)*j + c*k. | |

const SCEV *addToCoefficient(const SCEV *Expr, | |

const Loop *TargetLoop, | |

const SCEV *Value) const; | |

/// updateDirection - Update direction vector entry | |

/// based on the current constraint. | |

void updateDirection(Dependence::DVEntry &Level, | |

const Constraint &CurConstraint) const; | |

bool tryDelinearize(Instruction *Src, Instruction *Dst, | |

SmallVectorImpl<Subscript> &Pair); | |

}; // class DependenceInfo | |

/// AnalysisPass to compute dependence information in a function | |

class DependenceAnalysis : public AnalysisInfoMixin<DependenceAnalysis> { | |

public: | |

typedef DependenceInfo Result; | |

Result run(Function &F, FunctionAnalysisManager &FAM); | |

private: | |

static AnalysisKey Key; | |

friend struct AnalysisInfoMixin<DependenceAnalysis>; | |

}; // class DependenceAnalysis | |

/// Printer pass to dump DA results. | |

struct DependenceAnalysisPrinterPass | |

: public PassInfoMixin<DependenceAnalysisPrinterPass> { | |

DependenceAnalysisPrinterPass(raw_ostream &OS) : OS(OS) {} | |

PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM); | |

private: | |

raw_ostream &OS; | |

}; // class DependenceAnalysisPrinterPass | |

/// Legacy pass manager pass to access dependence information | |

class DependenceAnalysisWrapperPass : public FunctionPass { | |

public: | |

static char ID; // Class identification, replacement for typeinfo | |

DependenceAnalysisWrapperPass() : FunctionPass(ID) { | |

initializeDependenceAnalysisWrapperPassPass( | |

*PassRegistry::getPassRegistry()); | |

} | |

bool runOnFunction(Function &F) override; | |

void releaseMemory() override; | |

void getAnalysisUsage(AnalysisUsage &) const override; | |

void print(raw_ostream &, const Module * = nullptr) const override; | |

DependenceInfo &getDI() const; | |

private: | |

std::unique_ptr<DependenceInfo> info; | |

}; // class DependenceAnalysisWrapperPass | |

/// createDependenceAnalysisPass - This creates an instance of the | |

/// DependenceAnalysis wrapper pass. | |

FunctionPass *createDependenceAnalysisWrapperPass(); | |

} // namespace llvm | |

#endif |