Differential D108371 Diff 368011 llvm/include/llvm/Analysis/LoopAccessAnalysis.h

Changeset View

Standalone View

llvm/include/llvm/Analysis/LoopAccessAnalysis.h

Show All 10 Lines
//		//
//===----------------------------------------------------------------------===//		//===----------------------------------------------------------------------===//

#ifndef LLVM_ANALYSIS_LOOPACCESSANALYSIS_H		#ifndef LLVM_ANALYSIS_LOOPACCESSANALYSIS_H
#define LLVM_ANALYSIS_LOOPACCESSANALYSIS_H		#define LLVM_ANALYSIS_LOOPACCESSANALYSIS_H

#include "llvm/ADT/EquivalenceClasses.h"		#include "llvm/ADT/EquivalenceClasses.h"
#include "llvm/Analysis/LoopAnalysisManager.h"		#include "llvm/Analysis/LoopAnalysisManager.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"		#include "llvm/Analysis/ScalarEvolutionExpressions.h"
		fhahnUnsubmitted Done Reply Inline Actions This change is unnecessary, keep the include in the .cpp fhahn: This change is unnecessary, keep the include in the .cpp
#include "llvm/IR/DiagnosticInfo.h"		#include "llvm/IR/DiagnosticInfo.h"
#include "llvm/Pass.h"		#include "llvm/Pass.h"

namespace llvm {		namespace llvm {

class AAResults;		class AAResults;
class DataLayout;		class DataLayout;
class Loop;		class Loop;
▲ Show 20 Lines • Show All 225 Lines • ▼ Show 20 Lines	DenseMap<Instruction *, unsigned> generateInstructionOrderMap() const {

return OrderMap;		return OrderMap;
}		}

/// Find the set of instructions that read or write via \p Ptr.		/// Find the set of instructions that read or write via \p Ptr.
SmallVector<Instruction , 4> getInstructionsForAccess(Value Ptr,		SmallVector<Instruction , 4> getInstructionsForAccess(Value Ptr,
bool isWrite) const;		bool isWrite) const;

		const SmallVector<Dependence, 2> &getUnsafeDependences() const {
		fhahnUnsubmitted Not Done Reply Inline Actions There's no need to return a SmallVector with the length encoded, the callers should not care about that. You can use ArrayRef if the callers do not add to the vector or SmalLVectorImpl if they need to add elements. fhahn: There's no need to return a SmallVector with the length encoded, the callers should not care…
		malharJAuthorUnsubmitted Done Reply Inline Actions Currently the code uses "auto" when accessing the. value returned by this getter so there isn't a need for the user to know the size used in the template ... regardless, I've changed it to use SmallVector<T> instead if that's ok. malharJ: Currently the code uses "auto" when accessing the. value returned by this getter so there isn't…
		sdesmalenUnsubmitted Done Reply Inline Actions If there is no need to modify the array returned by getUnsafeDependences (which there isn't, because the returned value is `const`), ArrayRef seems the better class to use, because it has all sorts of convenient utilities and is similarly just a (immutable) reference to the array. sdesmalen: If there is no need to modify the array returned by getUnsafeDependences (which there isn't…
		return UnsafeDependences;
		}

private:		private:
/// A wrapper around ScalarEvolution, used to add runtime SCEV checks, and		/// A wrapper around ScalarEvolution, used to add runtime SCEV checks, and
/// applies dynamic knowledge to simplify SCEV expressions and convert them		/// applies dynamic knowledge to simplify SCEV expressions and convert them
/// to a more usable form. We need this in case assumptions about SCEV		/// to a more usable form. We need this in case assumptions about SCEV
/// expressions need to be made in order to avoid unknown dependences. For		/// expressions need to be made in order to avoid unknown dependences. For
/// example we might assume a unit stride for a pointer in order to prove		/// example we might assume a unit stride for a pointer in order to prove
/// that a memory access is strided and doesn't wrap.		/// that a memory access is strided and doesn't wrap.
PredicatedScalarEvolution &PSE;		PredicatedScalarEvolution &PSE;
Show All 30 Lines	private:
//// loop. If false we exceeded MaxDependences and		//// loop. If false we exceeded MaxDependences and
//// Dependences is invalid.		//// Dependences is invalid.
bool RecordDependences;		bool RecordDependences;

/// Memory dependences collected during the analysis. Only valid if		/// Memory dependences collected during the analysis. Only valid if
/// RecordDependences is true.		/// RecordDependences is true.
SmallVector<Dependence, 8> Dependences;		SmallVector<Dependence, 8> Dependences;

		/// Unsafe memory dependences collected during the analysis.
		/// Used for generating optimization remarks.
		alban.bridonneauUnsubmitted Done Reply Inline Actions Seems you only wanted one of these 2 words? alban.bridonneau: Seems you only wanted one of these 2 words?
		SmallVector<Dependence, 2> UnsafeDependences;
		fhahnUnsubmitted Done Reply Inline Actions Does this need to be a `shared_ptr`? If you want to encode the fact that it may not be set, using `Optional` may be a better choice. Or you could initialize it to `NoDep` in case there is no unsafe dependence. fhahn: Does this need to be a `shared_ptr`? If you want to encode the fact that it may not be set…
		malharJAuthorUnsubmitted Done Reply Inline Actions I've removed it now based on review comment by sdesmalen, so this is no longer an issue. malharJ: I've removed it now based on review comment by sdesmalen, so this is no longer an issue.

/// Check whether there is a plausible dependence between the two		/// Check whether there is a plausible dependence between the two
/// accesses.		/// accesses.
///		///
/// Access \p A must happen before \p B in program order. The two indices		/// Access \p A must happen before \p B in program order. The two indices
/// identify the index into the program order map.		/// identify the index into the program order map.
///		///
/// This function checks whether there is a plausible dependence (or the		/// This function checks whether there is a plausible dependence (or the
/// absence of such can't be proved) between the two accesses. If there is a		/// absence of such can't be proved) between the two accesses. If there is a
▲ Show 20 Lines • Show All 204 Lines • ▼ Show 20 Lines
/// If pointers can wrap or can't be expressed as affine AddRec expressions by		/// If pointers can wrap or can't be expressed as affine AddRec expressions by
/// ScalarEvolution, we will generate run-time checks by emitting a		/// ScalarEvolution, we will generate run-time checks by emitting a
/// SCEVUnionPredicate.		/// SCEVUnionPredicate.
///		///
/// Checks for both memory dependences and the SCEV predicates contained in the		/// Checks for both memory dependences and the SCEV predicates contained in the
/// PSE must be emitted in order for the results of this analysis to be valid.		/// PSE must be emitted in order for the results of this analysis to be valid.
class LoopAccessInfo {		class LoopAccessInfo {
public:		public:
		/// Reasons why memory accesses cannot be vectorized (used for OptRemarks)
		enum class FailureReason {
		UnsafeDataDependence,
		UnsafeDataDependenceTriedRT,
		UnknownArrayBounds,
		Unknown
		};

LoopAccessInfo(Loop L, ScalarEvolution SE, const TargetLibraryInfo *TLI,		LoopAccessInfo(Loop L, ScalarEvolution SE, const TargetLibraryInfo *TLI,
AAResults AA, DominatorTree DT, LoopInfo *LI);		AAResults AA, DominatorTree DT, LoopInfo *LI);

/// Return true we can analyze the memory accesses in the loop and there are		/// Return true we can analyze the memory accesses in the loop and there are
/// no memory dependence cycles.		/// no memory dependence cycles.
bool canVectorizeMemory() const { return CanVecMem; }		bool canVectorizeMemory() const { return CanVecMem; }

		/// Return reason describing why memory access cannot be vectorized.
		// Used for the OptRemark generation.
		alban.bridonneauUnsubmitted Done Reply Inline Actions Nit: Missing a slash alban.bridonneau: Nit: Missing a slash
		FailureReason getFailureReason() const { return FailReason; }

/// Return true if there is a convergent operation in the loop. There may		/// Return true if there is a convergent operation in the loop. There may
/// still be reported runtime pointer checks that would be required, but it is		/// still be reported runtime pointer checks that would be required, but it is
/// not legal to insert them.		/// not legal to insert them.
bool hasConvergentOp() const { return HasConvergentOp; }		bool hasConvergentOp() const { return HasConvergentOp; }

const RuntimePointerChecking *getRuntimePointerChecking() const {		const RuntimePointerChecking *getRuntimePointerChecking() const {
return PtrRtChecking.get();		return PtrRtChecking.get();
}		}
▲ Show 20 Lines • Show All 42 Lines • ▼ Show 20 Lines	public:
void print(raw_ostream &OS, unsigned Depth = 0) const;		void print(raw_ostream &OS, unsigned Depth = 0) const;

/// If the loop has memory dependence involving an invariant address, i.e. two		/// If the loop has memory dependence involving an invariant address, i.e. two
/// stores or a store and a load, then return true, else return false.		/// stores or a store and a load, then return true, else return false.
bool hasDependenceInvolvingLoopInvariantAddress() const {		bool hasDependenceInvolvingLoopInvariantAddress() const {
return HasDependenceInvolvingLoopInvariantAddress;		return HasDependenceInvolvingLoopInvariantAddress;
}		}

		const SmallPtrSet<Value *, 4> &getUncomputablePtrs() const {
		return UncomputablePtrs;
		}

/// Used to add runtime SCEV checks. Simplifies SCEV expressions and converts		/// Used to add runtime SCEV checks. Simplifies SCEV expressions and converts
/// them to a more usable form. All SCEV expressions during the analysis		/// them to a more usable form. All SCEV expressions during the analysis
/// should be re-written (and therefore simplified) according to PSE.		/// should be re-written (and therefore simplified) according to PSE.
/// A user of LoopAccessAnalysis will need to emit the runtime checks		/// A user of LoopAccessAnalysis will need to emit the runtime checks
/// associated with this predicate.		/// associated with this predicate.
const PredicatedScalarEvolution &getPSE() const { return *PSE; }		const PredicatedScalarEvolution &getPSE() const { return *PSE; }

private:		private:
Show All 16 Lines	private:
/// Collect memory access with loop invariant strides.		/// Collect memory access with loop invariant strides.
///		///
/// Looks for accesses like "a[i * StrideA]" where "StrideA" is loop		/// Looks for accesses like "a[i * StrideA]" where "StrideA" is loop
/// invariant.		/// invariant.
void collectStridedAccess(Value *LoadOrStoreInst);		void collectStridedAccess(Value *LoadOrStoreInst);

std::unique_ptr<PredicatedScalarEvolution> PSE;		std::unique_ptr<PredicatedScalarEvolution> PSE;

/// We need to check that all of the pointers in this list are disjoint		/// We need to check that all of the pointers in this list are disjoint
		sdesmalenUnsubmitted Done Reply Inline Actions This seems unused? sdesmalen: This seems unused?
		malharJAuthorUnsubmitted Done Reply Inline Actions thanks for pointing it out. Removed it. malharJ: thanks for pointing it out. Removed it.
/// at runtime. Using std::unique_ptr to make using move ctor simpler.		/// at runtime. Using std::unique_ptr to make using move ctor simpler.
std::unique_ptr<RuntimePointerChecking> PtrRtChecking;		std::unique_ptr<RuntimePointerChecking> PtrRtChecking;

/// the Memory Dependence Checker which can determine the		/// the Memory Dependence Checker which can determine the
/// loop-independent and loop-carried dependences between memory accesses.		/// loop-independent and loop-carried dependences between memory accesses.
std::unique_ptr<MemoryDepChecker> DepChecker;		std::unique_ptr<MemoryDepChecker> DepChecker;

Loop *TheLoop;		Loop *TheLoop;
Show All 15 Lines	private:
std::unique_ptr<OptimizationRemarkAnalysis> Report;		std::unique_ptr<OptimizationRemarkAnalysis> Report;

/// If an access has a symbolic strides, this maps the pointer value to		/// If an access has a symbolic strides, this maps the pointer value to
/// the stride symbol.		/// the stride symbol.
ValueToValueMap SymbolicStrides;		ValueToValueMap SymbolicStrides;

/// Set of symbolic strides values.		/// Set of symbolic strides values.
SmallPtrSet<Value *, 8> StrideSet;		SmallPtrSet<Value *, 8> StrideSet;

		/// Reason why memory accesses cannot be vectorized (used for OptRemarks)
		FailureReason FailReason;

		/// Set of uncomputable pointers.
		/// Used when emitting OptRemarks
		SmallPtrSet<Value *, 4> UncomputablePtrs;
};		};

Value stripIntegerCast(Value V);		Value stripIntegerCast(Value V);

/// Return the SCEV corresponding to a pointer with the symbolic stride		/// Return the SCEV corresponding to a pointer with the symbolic stride
/// replaced with constant one, assuming the SCEV predicate associated with		/// replaced with constant one, assuming the SCEV predicate associated with
/// \p PSE is true.		/// \p PSE is true.
///		///
▲ Show 20 Lines • Show All 126 Lines • Show Last 20 Lines