// 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.
//
#ifndef LLVM_ANALYSIS_DEPENDENCEANALYSIS_H
#define LLVM_ANALYSIS_DEPENDENCEANALYSIS_H
-#include "llvm/Instructions.h"
-#include "llvm/Pass.h"
#include "llvm/ADT/SmallBitVector.h"
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/Pass.h"
namespace llvm {
class AliasAnalysis;
/// 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 preceed the destination; in contrast,
+ /// 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(const Dependence &) = default;
+
public:
- Dependence(const Instruction *Source,
- const Instruction *Destination) :
- Src(Source), Dst(Destination) {}
+ Dependence(Instruction *Source,
+ Instruction *Destination) :
+ Src(Source),
+ Dst(Destination),
+ NextPredecessor(nullptr),
+ NextSuccessor(nullptr) {}
virtual ~Dependence() {}
/// Dependence::DVEntry - Each level in the distance/direction vector
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(NULL) { }
+ PeelLast(false), Splitable(false), Distance(nullptr) { }
};
/// getSrc - Returns the source instruction for this dependence.
///
- const Instruction *getSrc() const { return Src; }
+ Instruction *getSrc() const { return Src; }
/// getDst - Returns the destination instruction for this dependence.
///
- const Instruction *getDst() const { return Dst; }
+ Instruction *getDst() const { return Dst; }
/// isInput - Returns true if this is an input dependence.
///
virtual bool isConsistent() const { return false; }
/// getLevels - Returns the number of common loops surrounding the
- /// souce and destination of the dependence.
+ /// source and destination of the dependence.
virtual unsigned getLevels() const { return 0; }
/// getDirection - Returns the direction associated with a particular
/// getDistance - Returns the distance (or NULL) associated with a
/// particular level.
- virtual const SCEV *getDistance(unsigned Level) const { return NULL; }
+ virtual const SCEV *getDistance(unsigned Level) const { return nullptr; }
/// isPeelFirst - Returns true if peeling the first iteration from
/// this loop will break this dependence.
/// 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:
- const Instruction *Src, *Dst;
+ Instruction *Src, *Dst;
+ const Dependence *NextPredecessor, *NextSuccessor;
friend class DependenceAnalysis;
};
/// 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
+ /// 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 preceed the destination; in contrast,
+ /// ordering, where the source must precede the destination; in contrast,
/// input dependences are unordered.
- class FullDependence : public Dependence {
+ class FullDependence final : public Dependence {
public:
- FullDependence(const Instruction *Src,
- const Instruction *Dst,
- bool LoopIndependent,
+ FullDependence(Instruction *Src, Instruction *Dst, bool LoopIndependent,
unsigned Levels);
- ~FullDependence() {
- delete DV;
- }
+
+ FullDependence(FullDependence &&RHS)
+ : Dependence(RHS), Levels(RHS.Levels),
+ LoopIndependent(RHS.LoopIndependent), Consistent(RHS.Consistent),
+ DV(std::move(RHS.DV)) {}
/// isLoopIndependent - Returns true if this is a loop-independent
/// dependence.
- bool isLoopIndependent() const { return LoopIndependent; }
+ 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 { return false; }
+ 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 { return Consistent; }
+ bool isConsistent() const override { return Consistent; }
/// getLevels - Returns the number of common loops surrounding the
- /// souce and destination of the dependence.
- unsigned getLevels() const { return Levels; }
+ /// 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;
+ unsigned getDirection(unsigned Level) const override;
/// getDistance - Returns the distance (or NULL) associated with a
/// particular level.
- const SCEV *getDistance(unsigned Level) const;
+ 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;
+ 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;
+ bool isPeelLast(unsigned Level) const override;
/// isSplitable - Returns true if splitting the loop will break
/// the dependence.
- bool isSplitable(unsigned Level) const;
+ 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;
+ bool isScalar(unsigned Level) const override;
+
private:
unsigned short Levels;
bool LoopIndependent;
bool Consistent; // Init to true, then refine.
- DVEntry *DV;
+ std::unique_ptr<DVEntry[]> DV;
friend class DependenceAnalysis;
};
/// DependenceAnalysis - This class is the main dependence-analysis driver.
///
class DependenceAnalysis : public FunctionPass {
- void operator=(const DependenceAnalysis &); // do not implement
- DependenceAnalysis(const DependenceAnalysis &); // do not implement
+ void operator=(const DependenceAnalysis &) = delete;
+ DependenceAnalysis(const DependenceAnalysis &) = delete;
public:
/// depends - Tests for a dependence between the Src and Dst instructions.
/// Returns NULL if no dependence; otherwise, returns a Dependence (or a
/// 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.
- Dependence *depends(const Instruction *Src,
- const Instruction *Dst,
- bool PossiblyLoopIndependent);
+ std::unique_ptr<Dependence> depends(Instruction *Src,
+ Instruction *Dst,
+ bool PossiblyLoopIndependent);
- /// getSplitIteration - Give a dependence that's splitable at some
+ /// getSplitIteration - Give a dependence that's splittable at some
/// particular level, return the iteration that should be used to split
/// the loop.
///
///
/// breaks the dependence and allows us to vectorize/parallelize
/// both loops.
- const SCEV *getSplitIteration(const Dependence *Dep, unsigned Level);
+ const SCEV *getSplitIteration(const Dependence &Dep, unsigned Level);
private:
AliasAnalysis *AA;
/// 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
/// isKnownPredicate - Compare X and Y using the predicate Pred.
/// Basically a wrapper for SCEV::isKnownPredicate,
- /// but tries harder, especially in the presense of sign and zero
+ /// but tries harder, especially in the presence of sign and zero
/// extensions and symbolics.
bool isKnownPredicate(ICmpInst::Predicate Pred,
const SCEV *X,
/// 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 inconsistant.
+ /// Marks the result as inconsistent.
/// Works in some cases that symbolicRDIVtest doesn't,
/// and vice versa.
bool exactRDIVtest(const SCEV *SrcCoeff,
/// 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 inconsistant.
+ /// 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.
/// gcdMIVtest - Tests an MIV subscript pair for dependence.
/// Returns true if any possible dependence is disproved.
- /// Marks the result as inconsistant.
+ /// 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.
/// banerjeeMIVtest - Tests an MIV subscript pair for dependence.
/// Returns true if any possible dependence is disproved.
- /// Marks the result as inconsistant.
+ /// Marks the result as inconsistent.
/// Computes directions.
bool banerjeeMIVtest(const SCEV *Src,
const SCEV *Dst,
bool propagate(const SCEV *&Src,
const SCEV *&Dst,
SmallBitVector &Loops,
- SmallVector<Constraint, 4> &Constraints,
+ SmallVectorImpl<Constraint> &Constraints,
bool &Consistent);
/// propagateDistance - Attempt to propagate a distance
/// based on the current constraint.
void updateDirection(Dependence::DVEntry &Level,
const Constraint &CurConstraint) const;
+
+ bool tryDelinearize(const SCEV *SrcSCEV, const SCEV *DstSCEV,
+ SmallVectorImpl<Subscript> &Pair,
+ const SCEV *ElementSize);
+
public:
static char ID; // Class identification, replacement for typeinfo
DependenceAnalysis() : FunctionPass(ID) {
initializeDependenceAnalysisPass(*PassRegistry::getPassRegistry());
}
- bool runOnFunction(Function &F);
- void releaseMemory();
- void getAnalysisUsage(AnalysisUsage &) const;
- void print(raw_ostream &, const Module * = 0) const;
+ bool runOnFunction(Function &F) override;
+ void releaseMemory() override;
+ void getAnalysisUsage(AnalysisUsage &) const override;
+ void print(raw_ostream &, const Module * = nullptr) const override;
}; // class DependenceAnalysis
/// createDependenceAnalysisPass - This creates an instance of the
projects / oota-llvm.git / blobdiff