Diff 58194

include/llvm/Analysis/LoopAccessAnalysis.h

	Show All 9 Lines
	// This file defines the interface for the loop memory dependence framework that			// This file defines the interface for the loop memory dependence framework that
	// was originally developed for the Loop Vectorizer.			// was originally developed for the Loop Vectorizer.
	//			//
	//===----------------------------------------------------------------------===//			//===----------------------------------------------------------------------===//

	#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/DenseMap.h"
	#include "llvm/ADT/Optional.h"
	#include "llvm/ADT/SetVector.h"
	#include "llvm/Analysis/AliasAnalysis.h"			#include "llvm/Analysis/AliasAnalysis.h"
	#include "llvm/Analysis/AliasSetTracker.h"			#include "llvm/IR/PassManager.h"
	#include "llvm/Analysis/ScalarEvolutionExpressions.h"			#include "llvm/InitializePasses.h"
	#include "llvm/IR/ValueHandle.h"
	#include "llvm/Pass.h"			#include "llvm/Pass.h"
	#include "llvm/Support/raw_ostream.h"

	namespace llvm {			namespace llvm {

	class Value;			class DominatorTree;
	class DataLayout;
	class ScalarEvolution;
	class Loop;			class Loop;
	class SCEV;
	class SCEVUnionPredicate;
	class LoopAccessInfo;			class LoopAccessInfo;
				class LoopInfo;
				class ScalarEvolution;
				class TargetLibraryInfo;
				class Value;

	/// Optimization analysis message produced during vectorization. Messages inform			typedef DenseMap<const Value , Value > ValueToValueMap;
	/// the user why vectorization did not occur.
	class LoopAccessReport {
	std::string Message;
	const Instruction *Instr;

	protected:
	LoopAccessReport(const Twine &Message, const Instruction *I)
	: Message(Message.str()), Instr(I) {}

	public:
	LoopAccessReport(const Instruction *I = nullptr) : Instr(I) {}

	template <typename A> LoopAccessReport &operator<<(const A &Value) {
	raw_string_ostream Out(Message);
	Out << Value;
	return *this;
	}

	const Instruction *getInstr() const { return Instr; }

	std::string &str() { return Message; }
	const std::string &str() const { return Message; }
	operator Twine() { return Message; }

	/// \brief Emit an analysis note for \p PassName with the debug location from
	/// the instruction in \p Message if available. Otherwise use the location of
	/// \p TheLoop.
	static void emitAnalysis(const LoopAccessReport &Message,
	const Function *TheFunction,
	const Loop *TheLoop,
	const char *PassName);
	};

	/// \brief Collection of parameters shared beetween the Loop Vectorizer and the
	/// Loop Access Analysis.
	struct VectorizerParams {
	/// \brief Maximum SIMD width.
	static const unsigned MaxVectorWidth;

	/// \brief VF as overridden by the user.
	static unsigned VectorizationFactor;
	/// \brief Interleave factor as overridden by the user.
	static unsigned VectorizationInterleave;
	/// \brief True if force-vector-interleave was specified by the user.
	static bool isInterleaveForced();

	/// \\brief When performing memory disambiguation checks at runtime do not
	/// make more than this number of comparisons.
	static unsigned RuntimeMemoryCheckThreshold;
	};

	/// \brief Checks memory dependences among accesses to the same underlying
	/// object to determine whether there vectorization is legal or not (and at
	/// which vectorization factor).
	///
	/// Note: This class will compute a conservative dependence for access to
	/// different underlying pointers. Clients, such as the loop vectorizer, will
	/// sometimes deal these potential dependencies by emitting runtime checks.
	///
	/// We use the ScalarEvolution framework to symbolically evalutate access
	/// functions pairs. Since we currently don't restructure the loop we can rely
	/// on the program order of memory accesses to determine their safety.
	/// At the moment we will only deem accesses as safe for:
	/// * A negative constant distance assuming program order.
	///
	/// Safe: tmp = a[i + 1]; OR a[i + 1] = x;
	/// a[i] = tmp; y = a[i];
	///
	/// The latter case is safe because later checks guarantuee that there can't
	/// be a cycle through a phi node (that is, we check that "x" and "y" is not
	/// the same variable: a header phi can only be an induction or a reduction, a
	/// reduction can't have a memory sink, an induction can't have a memory
	/// source). This is important and must not be violated (or we have to
	/// resort to checking for cycles through memory).
	///
	/// * A positive constant distance assuming program order that is bigger
	/// than the biggest memory access.
	///
	/// tmp = a[i] OR b[i] = x
	/// a[i+2] = tmp y = b[i+2];
	///
	/// Safe distance: 2 x sizeof(a[0]), and 2 x sizeof(b[0]), respectively.
	///
	/// * Zero distances and all accesses have the same size.
	///
	class MemoryDepChecker {
	public:
	typedef PointerIntPair<Value *, 1, bool> MemAccessInfo;
	typedef SmallPtrSet<MemAccessInfo, 8> MemAccessInfoSet;
	/// \brief Set of potential dependent memory accesses.
	typedef EquivalenceClasses<MemAccessInfo> DepCandidates;

	/// \brief Dependece between memory access instructions.
	struct Dependence {
	/// \brief The type of the dependence.
	enum DepType {
	// No dependence.
	NoDep,
	// We couldn't determine the direction or the distance.
	Unknown,
	// Lexically forward.
	//
	// FIXME: If we only have loop-independent forward dependences (e.g. a
	// read and write of A[i]), LAA will locally deem the dependence "safe"
	// without querying the MemoryDepChecker. Therefore we can miss
	// enumerating loop-independent forward dependences in
	// getDependences. Note that as soon as there are different
	// indices used to access the same array, the MemoryDepChecker is
	// queried and the dependence list is complete.
	Forward,
	// Forward, but if vectorized, is likely to prevent store-to-load
	// forwarding.
	ForwardButPreventsForwarding,
	// Lexically backward.
	Backward,
	// Backward, but the distance allows a vectorization factor of
	// MaxSafeDepDistBytes.
	BackwardVectorizable,
	// Same, but may prevent store-to-load forwarding.
	BackwardVectorizableButPreventsForwarding
	};

	/// \brief String version of the types.
	static const char *DepName[];

	/// \brief Index of the source of the dependence in the InstMap vector.
	unsigned Source;
	/// \brief Index of the destination of the dependence in the InstMap vector.
	unsigned Destination;
	/// \brief The type of the dependence.
	DepType Type;

	Dependence(unsigned Source, unsigned Destination, DepType Type)
	: Source(Source), Destination(Destination), Type(Type) {}

	/// \brief Return the source instruction of the dependence.
	Instruction *getSource(const LoopAccessInfo &LAI) const;
	/// \brief Return the destination instruction of the dependence.
	Instruction *getDestination(const LoopAccessInfo &LAI) const;

	/// \brief Dependence types that don't prevent vectorization.
	static bool isSafeForVectorization(DepType Type);

	/// \brief Lexically forward dependence.
	bool isForward() const;
	/// \brief Lexically backward dependence.
	bool isBackward() const;

	/// \brief May be a lexically backward dependence type (includes Unknown).
	bool isPossiblyBackward() const;

	/// \brief Print the dependence. \p Instr is used to map the instruction
	/// indices to instructions.
	void print(raw_ostream &OS, unsigned Depth,
	const SmallVectorImpl<Instruction *> &Instrs) const;
	};

	MemoryDepChecker(PredicatedScalarEvolution &PSE, const Loop *L)
	: PSE(PSE), InnermostLoop(L), AccessIdx(0),
	ShouldRetryWithRuntimeCheck(false), SafeForVectorization(true),
	RecordDependences(true) {}

	/// \brief Register the location (instructions are given increasing numbers)
	/// of a write access.
	void addAccess(StoreInst *SI) {
	Value *Ptr = SI->getPointerOperand();
	Accesses[MemAccessInfo(Ptr, true)].push_back(AccessIdx);
	InstMap.push_back(SI);
	++AccessIdx;
	}

	/// \brief Register the location (instructions are given increasing numbers)
	/// of a write access.
	void addAccess(LoadInst *LI) {
	Value *Ptr = LI->getPointerOperand();
	Accesses[MemAccessInfo(Ptr, false)].push_back(AccessIdx);
	InstMap.push_back(LI);
	++AccessIdx;
	}

	/// \brief Check whether the dependencies between the accesses are safe.
	///
	/// Only checks sets with elements in \p CheckDeps.
	bool areDepsSafe(DepCandidates &AccessSets, MemAccessInfoSet &CheckDeps,
	const ValueToValueMap &Strides);

	/// \brief No memory dependence was encountered that would inhibit
	/// vectorization.
	bool isSafeForVectorization() const { return SafeForVectorization; }

	/// \brief The maximum number of bytes of a vector register we can vectorize
	/// the accesses safely with.
	unsigned getMaxSafeDepDistBytes() { return MaxSafeDepDistBytes; }

	/// \brief In same cases when the dependency check fails we can still
	/// vectorize the loop with a dynamic array access check.
	bool shouldRetryWithRuntimeCheck() { return ShouldRetryWithRuntimeCheck; }

	/// \brief Returns the memory dependences. If null is returned we exceeded
	/// the MaxDependences threshold and this information is not
	/// available.
	const SmallVectorImpl<Dependence> *getDependences() const {
	return RecordDependences ? &Dependences : nullptr;
	}

	void clearDependences() { Dependences.clear(); }

	/// \brief The vector of memory access instructions. The indices are used as
	/// instruction identifiers in the Dependence class.
	const SmallVectorImpl<Instruction *> &getMemoryInstructions() const {
	return InstMap;
	}

	/// \brief Generate a mapping between the memory instructions and their
	/// indices according to program order.
	DenseMap<Instruction *, unsigned> generateInstructionOrderMap() const {
	DenseMap<Instruction *, unsigned> OrderMap;

	for (unsigned I = 0; I < InstMap.size(); ++I)
	OrderMap[InstMap[I]] = I;

	return OrderMap;
	}

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

	private:
	/// A wrapper around ScalarEvolution, used to add runtime SCEV checks, and
	/// applies dynamic knowledge to simplify SCEV expressions and convert them
	/// 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
	/// example we might assume a unit stride for a pointer in order to prove
	/// that a memory access is strided and doesn't wrap.
	PredicatedScalarEvolution &PSE;
	const Loop *InnermostLoop;

	/// \brief Maps access locations (ptr, read/write) to program order.
	DenseMap<MemAccessInfo, std::vector<unsigned> > Accesses;

	/// \brief Memory access instructions in program order.
	SmallVector<Instruction *, 16> InstMap;

	/// \brief The program order index to be used for the next instruction.
	unsigned AccessIdx;

	// We can access this many bytes in parallel safely.
	unsigned MaxSafeDepDistBytes;

	/// \brief If we see a non-constant dependence distance we can still try to
	/// vectorize this loop with runtime checks.
	bool ShouldRetryWithRuntimeCheck;

	/// \brief No memory dependence was encountered that would inhibit
	/// vectorization.
	bool SafeForVectorization;

	//// \brief True if Dependences reflects the dependences in the
	//// loop. If false we exceeded MaxDependences and
	//// Dependences is invalid.
	bool RecordDependences;

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

	/// \brief Check whether there is a plausible dependence between the two
	/// accesses.
	///
	/// Access \p A must happen before \p B in program order. The two indices
	/// identify the index into the program order map.
	///
	/// 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
	/// plausible dependence but the dependence distance is bigger than one
	/// element access it records this distance in \p MaxSafeDepDistBytes (if this
	/// distance is smaller than any other distance encountered so far).
	/// Otherwise, this function returns true signaling a possible dependence.
	Dependence::DepType isDependent(const MemAccessInfo &A, unsigned AIdx,
	const MemAccessInfo &B, unsigned BIdx,
	const ValueToValueMap &Strides);

	/// \brief Check whether the data dependence could prevent store-load
	/// forwarding.
	///
	/// \return false if we shouldn't vectorize at all or avoid larger
	/// vectorization factors by limiting MaxSafeDepDistBytes.
	bool couldPreventStoreLoadForward(unsigned Distance, unsigned TypeByteSize);
	};

	/// \brief Holds information about the memory runtime legality checks to verify			// Analysis manager base
	/// that a group of pointers do not overlap.			class LoopAccessAMBase {
	class RuntimePointerChecking {
	public:			public:
	struct PointerInfo {			virtual TargetLibraryInfo *getTLI() = 0;
	/// Holds the pointer value that we need to check.			virtual AliasAnalysis *getAAResults() = 0;
	TrackingVH<Value> PointerValue;			virtual DominatorTree *getDominatorTree() = 0;
	/// Holds the pointer value at the beginning of the loop.			virtual LoopInfo *getLoopInfo() = 0;
	const SCEV *Start;			virtual ScalarEvolution *getSCEV() = 0;
	/// Holds the pointer value at the end of the loop.			virtual ~LoopAccessAMBase() {}
	const SCEV *End;
	/// Holds the information if this pointer is used for writing to memory.
	bool IsWritePtr;
	/// Holds the id of the set of pointers that could be dependent because of a
	/// shared underlying object.
	unsigned DependencySetId;
	/// Holds the id of the disjoint alias set to which this pointer belongs.
	unsigned AliasSetId;
	/// SCEV for the access.
	const SCEV *Expr;

	PointerInfo(Value PointerValue, const SCEV Start, const SCEV *End,
	bool IsWritePtr, unsigned DependencySetId, unsigned AliasSetId,
	const SCEV *Expr)
	: PointerValue(PointerValue), Start(Start), End(End),
	IsWritePtr(IsWritePtr), DependencySetId(DependencySetId),
	AliasSetId(AliasSetId), Expr(Expr) {}
	};

	RuntimePointerChecking(ScalarEvolution *SE) : Need(false), SE(SE) {}

	/// Reset the state of the pointer runtime information.
	void reset() {
	Need = false;
	Pointers.clear();
	Checks.clear();
	}

	/// Insert a pointer and calculate the start and end SCEVs.
	/// We need \p PSE in order to compute the SCEV expression of the pointer
	/// according to the assumptions that we've made during the analysis.
	/// The method might also version the pointer stride according to \p Strides,
	/// and add new predicates to \p PSE.
	void insert(Loop Lp, Value Ptr, bool WritePtr, unsigned DepSetId,
	unsigned ASId, const ValueToValueMap &Strides,
	PredicatedScalarEvolution &PSE);

	/// \brief No run-time memory checking is necessary.
	bool empty() const { return Pointers.empty(); }

	/// A grouping of pointers. A single memcheck is required between
	/// two groups.
	struct CheckingPtrGroup {
	/// \brief Create a new pointer checking group containing a single
	/// pointer, with index \p Index in RtCheck.
	CheckingPtrGroup(unsigned Index, RuntimePointerChecking &RtCheck)
	: RtCheck(RtCheck), High(RtCheck.Pointers[Index].End),
	Low(RtCheck.Pointers[Index].Start) {
	Members.push_back(Index);
	}

	/// \brief Tries to add the pointer recorded in RtCheck at index
	/// \p Index to this pointer checking group. We can only add a pointer
	/// to a checking group if we will still be able to get
	/// the upper and lower bounds of the check. Returns true in case
	/// of success, false otherwise.
	bool addPointer(unsigned Index);

	/// Constitutes the context of this pointer checking group. For each
	/// pointer that is a member of this group we will retain the index
	/// at which it appears in RtCheck.
	RuntimePointerChecking &RtCheck;
	/// The SCEV expression which represents the upper bound of all the
	/// pointers in this group.
	const SCEV *High;
	/// The SCEV expression which represents the lower bound of all the
	/// pointers in this group.
	const SCEV *Low;
	/// Indices of all the pointers that constitute this grouping.
	SmallVector<unsigned, 2> Members;
	};

	/// \brief A memcheck which made up of a pair of grouped pointers.
	///
	/// These have to be const for now, since checks are generated from
	/// CheckingPtrGroups in LAI::addRuntimeChecks which is a const member
	/// function. FIXME: once check-generation is moved inside this class (after
	/// the PtrPartition hack is removed), we could drop const.
	typedef std::pair<const CheckingPtrGroup , const CheckingPtrGroup >
	PointerCheck;

	/// \brief Generate the checks and store it. This also performs the grouping
	/// of pointers to reduce the number of memchecks necessary.
	void generateChecks(MemoryDepChecker::DepCandidates &DepCands,
	bool UseDependencies);

	/// \brief Returns the checks that generateChecks created.
	const SmallVector<PointerCheck, 4> &getChecks() const { return Checks; }

	/// \brief Decide if we need to add a check between two groups of pointers,
	/// according to needsChecking.
	bool needsChecking(const CheckingPtrGroup &M,
	const CheckingPtrGroup &N) const;

	/// \brief Returns the number of run-time checks required according to
	/// needsChecking.
	unsigned getNumberOfChecks() const { return Checks.size(); }

	/// \brief Print the list run-time memory checks necessary.
	void print(raw_ostream &OS, unsigned Depth = 0) const;

	/// Print \p Checks.
	void printChecks(raw_ostream &OS, const SmallVectorImpl<PointerCheck> &Checks,
	unsigned Depth = 0) const;

	/// This flag indicates if we need to add the runtime check.
	bool Need;

	/// Information about the pointers that may require checking.
	SmallVector<PointerInfo, 2> Pointers;

	/// Holds a partitioning of pointers into "check groups".
	SmallVector<CheckingPtrGroup, 2> CheckingGroups;

	/// \brief Check if pointers are in the same partition
	///
	/// \p PtrToPartition contains the partition number for pointers (-1 if the
	/// pointer belongs to multiple partitions).
	static bool
	arePointersInSamePartition(const SmallVectorImpl<int> &PtrToPartition,
	unsigned PtrIdx1, unsigned PtrIdx2);

	/// \brief Decide whether we need to issue a run-time check for pointer at
	/// index \p I and \p J to prove their independence.
	bool needsChecking(unsigned I, unsigned J) const;

	/// \brief Return PointerInfo for pointer at index \p PtrIdx.
	const PointerInfo &getPointerInfo(unsigned PtrIdx) const {
	return Pointers[PtrIdx];
	}

	private:
	/// \brief Groups pointers such that a single memcheck is required
	/// between two different groups. This will clear the CheckingGroups vector
	/// and re-compute it. We will only group dependecies if \p UseDependencies
	/// is true, otherwise we will create a separate group for each pointer.
	void groupChecks(MemoryDepChecker::DepCandidates &DepCands,
	bool UseDependencies);

	/// Generate the checks and return them.
	SmallVector<PointerCheck, 4>
	generateChecks() const;

	/// Holds a pointer to the ScalarEvolution analysis.
	ScalarEvolution *SE;

	/// \brief Set of run-time checks required to establish independence of
	/// otherwise may-aliasing pointers in the loop.
	SmallVector<PointerCheck, 4> Checks;
	};			};

	/// \brief Drive the analysis of memory accesses in the loop			class LoopAccessFuncInfo {
	///
	/// This class is responsible for analyzing the memory accesses of a loop. It
	/// collects the accesses and then its main helper the AccessAnalysis class
	/// finds and categorizes the dependences in buildDependenceSets.
	///
	/// For memory dependences that can be analyzed at compile time, it determines
	/// whether the dependence is part of cycle inhibiting vectorization. This work
	/// is delegated to the MemoryDepChecker class.
	///
	/// For memory dependences that cannot be determined at compile time, it
	/// generates run-time checks to prove independence. This is done by
	/// AccessAnalysis::canCheckPtrAtRT and the checks are maintained by the
	/// RuntimePointerCheck class.
	///
	/// If pointers can wrap or can't be expressed as affine AddRec expressions by
	/// ScalarEvolution, we will generate run-time checks by emitting a
	/// SCEVUnionPredicate.
	///
	/// 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.
	class LoopAccessInfo {
	public:			public:
	LoopAccessInfo(Loop L, ScalarEvolution SE, const DataLayout &DL,			LoopAccessFuncInfo() : LoopAccessInfoMap(), AM(nullptr) {}
	const TargetLibraryInfo TLI, AliasAnalysis AA,			/// \brief Query the result of the loop access information for the loop \p L.
	DominatorTree DT, LoopInfo LI,
	const ValueToValueMap &Strides);

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

	const RuntimePointerChecking *getRuntimePointerChecking() const {
	return &PtrRtChecking;
	}

	/// \brief Number of memchecks required to prove independence of otherwise
	/// may-alias pointers.
	unsigned getNumRuntimePointerChecks() const {
	return PtrRtChecking.getNumberOfChecks();
	}

	/// Return true if the block BB needs to be predicated in order for the loop
	/// to be vectorized.
	static bool blockNeedsPredication(BasicBlock BB, Loop TheLoop,
	DominatorTree *DT);

	/// Returns true if the value V is uniform within the loop.
	bool isUniform(Value *V) const;

	unsigned getMaxSafeDepDistBytes() const { return MaxSafeDepDistBytes; }
	unsigned getNumStores() const { return NumStores; }
	unsigned getNumLoads() const { return NumLoads;}

	/// \brief Add code that checks at runtime if the accessed arrays overlap.
	///
	/// Returns a pair of instructions where the first element is the first
	/// instruction generated in possibly a sequence of instructions and the
	/// second value is the final comparator value or NULL if no check is needed.
	std::pair<Instruction , Instruction >
	addRuntimeChecks(Instruction *Loc) const;

	/// \brief Generete the instructions for the checks in \p PointerChecks.
	///			///
	/// Returns a pair of instructions where the first element is the first			/// If the client speculates (and then issues run-time checks) for the values
	/// instruction generated in possibly a sequence of instructions and the			/// of symbolic strides, \p Strides provides the mapping (see
	/// second value is the final comparator value or NULL if no check is needed.			/// replaceSymbolicStrideSCEV). If there is no cached result available run
	std::pair<Instruction , Instruction >			/// the analysis.
	addRuntimeChecks(Instruction *Loc,			const LoopAccessInfo &getInfo(Loop *L, const ValueToValueMap &Strides);
	const SmallVectorImpl<RuntimePointerChecking::PointerCheck>
	&PointerChecks) const;

	/// \brief The diagnostics report generated for the analysis. E.g. why we
	/// couldn't analyze the loop.
	const Optional<LoopAccessReport> &getReport() const { return Report; }

	/// \brief the Memory Dependence Checker which can determine the
	/// loop-independent and loop-carried dependences between memory accesses.
	const MemoryDepChecker &getDepChecker() const { return DepChecker; }

	/// \brief Return the list of instructions that use \p Ptr to read or write
	/// memory.
	SmallVector<Instruction , 4> getInstructionsForAccess(Value Ptr,
	bool isWrite) const {
	return DepChecker.getInstructionsForAccess(Ptr, isWrite);
	}

	/// \brief Print the information about the memory accesses in the loop.			void print(raw_ostream &OS, const Module *M = nullptr) const;
	void print(raw_ostream &OS, unsigned Depth = 0) const;

	/// \brief Used to ensure that if the analysis was run with speculating the			void releaseMemory() {
	/// value of symbolic strides, the client queries it with the same assumption.			// Invalidate the cache when the pass is freed.
	/// Only used in DEBUG build but we don't want NDEBUG-dependent ABI.			LoopAccessInfoMap.clear();
	unsigned NumSymbolicStrides;

	/// \brief Checks existence of store to invariant address inside loop.
	/// If the loop has any store to invariant address, then it returns true,
	/// else returns false.
	bool hasStoreToLoopInvariantAddress() const {
	return StoreToLoopInvariantAddress;
	}			}

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

	private:			private:
	/// \brief Analyze the loop. Substitute symbolic strides using Strides.			/// \brief The cache.
	void analyzeLoop(const ValueToValueMap &Strides);			DenseMap<Loop *, std::unique_ptr<LoopAccessInfo>> LoopAccessInfoMap;
				std::unique_ptr<LoopAccessAMBase> AM;
	/// \brief Check if the structure of the loop allows it to be analyzed by this
	/// pass.
	bool canAnalyzeLoop();

	void emitAnalysis(LoopAccessReport &Message);

	/// We need to check that all of the pointers in this list are disjoint
	/// at runtime.
	RuntimePointerChecking PtrRtChecking;

	/// \brief the Memory Dependence Checker which can determine the
	/// loop-independent and loop-carried dependences between memory accesses.
	MemoryDepChecker DepChecker;

	Loop *TheLoop;
	const DataLayout &DL;
	const TargetLibraryInfo *TLI;
	AliasAnalysis *AA;
	DominatorTree *DT;
	LoopInfo *LI;

	unsigned NumLoads;
	unsigned NumStores;

	unsigned MaxSafeDepDistBytes;

	/// \brief Cache the result of analyzeLoop.
	bool CanVecMem;

	/// \brief Indicator for storing to uniform addresses.
	/// If a loop has write to a loop invariant address then it should be true.
	bool StoreToLoopInvariantAddress;

	/// \brief The diagnostics report generated for the analysis. E.g. why we
	/// couldn't analyze the loop.
	Optional<LoopAccessReport> Report;
	};			};

	Value stripIntegerCast(Value V);

	/// \brief Return the SCEV corresponding to a pointer with the symbolic stride
	/// replaced with constant one, assuming the SCEV predicate associated with
	/// \p PSE is true.
	///
	/// If necessary this method will version the stride of the pointer according
	/// to \p PtrToStride and therefore add further predicates to \p PSE.
	///
	/// If \p OrigPtr is not null, use it to look up the stride value instead of \p
	/// Ptr. \p PtrToStride provides the mapping between the pointer value and its
	/// stride as collected by LoopVectorizationLegality::collectStridedAccess.
	const SCEV *replaceSymbolicStrideSCEV(PredicatedScalarEvolution &PSE,
	const ValueToValueMap &PtrToStride,
	Value Ptr, Value OrigPtr = nullptr);

	/// \brief If the pointer has a constant stride return it in units of its
	/// element size. Otherwise return zero.
	///
	/// Ensure that it does not wrap in the address space, assuming the predicate
	/// associated with \p PSE is true.
	///
	/// If necessary this method will version the stride of the pointer according
	/// to \p PtrToStride and therefore add further predicates to \p PSE.
	/// The \p Assume parameter indicates if we are allowed to make additional
	/// run-time assumptions.
	int getPtrStride(PredicatedScalarEvolution &PSE, Value Ptr, const Loop Lp,
	const ValueToValueMap &StridesMap = ValueToValueMap(),
	bool Assume = false);

	/// \brief Returns true if the memory operations \p A and \p B are consecutive.
	/// This is a simple API that does not depend on the analysis pass.
	bool isConsecutiveAccess(Value A, Value B, const DataLayout &DL,
	ScalarEvolution &SE, bool CheckType = true);

	/// \brief This analysis provides dependence information for the memory accesses			/// \brief This analysis provides dependence information for the memory accesses
	/// of a loop.			/// of a loop.
	///			///
	/// It runs the analysis for a loop on demand. This can be initiated by			/// It runs the analysis for a loop on demand. This can be initiated by
	/// querying the loop access info via LAA::getInfo. getInfo return a			/// querying the loop access info via LAA::getInfo. getInfo return a
	/// LoopAccessInfo object. See this class for the specifics of what information			/// LoopAccessInfo object. See this class for the specifics of what information
	/// is provided.			/// is provided.
	class LoopAccessAnalysis : public FunctionPass {			class LoopAccessAnalysis : public FunctionPass {
				davideUnsubmitted Not Done Reply Inline Actions I'm not entirely sure what's the preferred LLVM style here, but I seldom (if ever) have seen variables ending with `_` used like this. I might miss something (and certainly I didn't compile), but, won't `this.AAR = AAR` et similia work? davide: I'm not entirely sure what's the preferred LLVM style here, but I seldom (if ever) have seen…
	public:			public:
	static char ID;			static char ID;

	LoopAccessAnalysis() : FunctionPass(ID) {			LoopAccessAnalysis() : FunctionPass(ID), LAFI() {
	initializeLoopAccessAnalysisPass(*PassRegistry::getPassRegistry());			initializeLoopAccessAnalysisPass(*PassRegistry::getPassRegistry());
	}			}

	bool runOnFunction(Function &F) override;			bool runOnFunction(Function &F) override;

	void getAnalysisUsage(AnalysisUsage &AU) const override;			void getAnalysisUsage(AnalysisUsage &AU) const override;

	/// \brief Query the result of the loop access information for the loop \p L.			LoopAccessFuncInfo &getInfo() { return LAFI; }
	///
	/// If the client speculates (and then issues run-time checks) for the values
	/// of symbolic strides, \p Strides provides the mapping (see
	/// replaceSymbolicStrideSCEV). If there is no cached result available run
	/// the analysis.
	const LoopAccessInfo &getInfo(Loop *L, const ValueToValueMap &Strides);

	void releaseMemory() override {			void releaseMemory() override {
	// Invalidate the cache when the pass is freed.			// Invalidate the cache when the pass is freed.
	LoopAccessInfoMap.clear();			LAFI.releaseMemory();
	}			}
				davideUnsubmitted Not Done Reply Inline Actions Move this outside of the function, and make it doxygen, i.e. `\brief Invalidate the cache when this pass is freed` davide: Move this outside of the function, and make it doxygen, i.e. `\brief Invalidate the cache when…

	/// \brief Print the result of the analysis when invoked with -analyze.			/// \brief Print the result of the analysis when invoked with -analyze.
	void print(raw_ostream &OS, const Module *M = nullptr) const override;			void print(raw_ostream &OS, const Module *M = nullptr) const override {
				LAFI.print(OS, M);
				}
				davideUnsubmitted Not Done Reply Inline Actions This comment is too generic to be somehow useful. I think it should be expanded a bit, while you're here. davide: This comment is too generic to be somehow useful. I think it should be expanded a bit, while…

	private:			private:
	/// \brief The cache.			LoopAccessFuncInfo LAFI;
				davideUnsubmitted Not Done Reply Inline Actions Why `AAR` and not `AA` as it was before? Also more consistent with how other variables are named. davide: Why `AAR` and not `AA` as it was before? Also more consistent with how other variables are…
				anemetUnsubmitted Not Done Reply Inline Actions s/LAFI/LAAR anemet: s/LAFI/LAAR
	DenseMap<Loop *, std::unique_ptr<LoopAccessInfo>> LoopAccessInfoMap;

	// The used analysis passes.
	ScalarEvolution *SE;
	const TargetLibraryInfo *TLI;
	AliasAnalysis *AA;
	DominatorTree *DT;
	LoopInfo *LI;
	};			};

	inline Instruction *MemoryDepChecker::Dependence::getSource(
	const LoopAccessInfo &LAI) const {
	return LAI.getDepChecker().getMemoryInstructions()[Source];
	}

	inline Instruction *MemoryDepChecker::Dependence::getDestination(
	const LoopAccessInfo &LAI) const {
	return LAI.getDepChecker().getMemoryInstructions()[Destination];
	}

	} // End llvm namespace			} // End llvm namespace

	#endif			#endif
				anemetUnsubmitted Not Done Reply Inline Actions You don't need to call the default ctor for LAIM like this. Also you may want to use in-class data member initializers for the nullptrs and then remove the ctor altogether. anemet: You don't need to call the default ctor for LAIM like this. Also you may want to use in-class…
				anemetUnsubmitted Not Done Reply Inline Actions This needs a class comment. Also what do you think about naming this Result as well, i.e. LoopAccessAnalysisResult? anemet: This needs a class comment. Also what do you think about naming this Result as well, i.e.

include/llvm/Analysis/LoopAccessInfo.h

	//===- llvm/Analysis/LoopAccessAnalysis.h ------------------------ C++ --===//			//===- llvm/Analysis/LoopAccessAnalysis.h ------------------------ C++ --===//
	//			//
	// The LLVM Compiler Infrastructure			// The LLVM Compiler Infrastructure
	//			//
	// This file is distributed under the University of Illinois Open Source			// This file is distributed under the University of Illinois Open Source
	// License. See LICENSE.TXT for details.			// License. See LICENSE.TXT for details.
	//			//
	//===----------------------------------------------------------------------===//			//===----------------------------------------------------------------------===//
	//			//
	// This file defines the interface for the loop memory dependence framework that			// This file defines the interface for the loop memory dependence framework that
	// was originally developed for the Loop Vectorizer.			// was originally developed for the Loop Vectorizer.
	//			//
	//===----------------------------------------------------------------------===//			//===----------------------------------------------------------------------===//

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

	#include "llvm/ADT/EquivalenceClasses.h"			#include "llvm/ADT/EquivalenceClasses.h"
	#include "llvm/ADT/Optional.h"			#include "llvm/ADT/Optional.h"
	#include "llvm/ADT/SetVector.h"			#include "llvm/ADT/SetVector.h"
	#include "llvm/Analysis/AliasAnalysis.h"			#include "llvm/Analysis/AliasAnalysis.h"
	#include "llvm/Analysis/AliasSetTracker.h"			#include "llvm/Analysis/AliasSetTracker.h"
	#include "llvm/Analysis/ScalarEvolutionExpressions.h"			#include "llvm/Analysis/ScalarEvolutionExpressions.h"
	#include "llvm/IR/ValueHandle.h"			#include "llvm/IR/ValueHandle.h"
	#include "llvm/Pass.h"
	#include "llvm/Support/raw_ostream.h"			#include "llvm/Support/raw_ostream.h"

	namespace llvm {			namespace llvm {

	class Value;			class Value;
	class DataLayout;			class DataLayout;
	class ScalarEvolution;			class ScalarEvolution;
	class Loop;			class Loop;
	▲ Show 20 Lines • Show All 631 Lines • ▼ Show 20 Lines
	/// to \p PtrToStride and therefore add further predicates to \p PSE.			/// to \p PtrToStride and therefore add further predicates to \p PSE.
	/// The \p Assume parameter indicates if we are allowed to make additional			/// The \p Assume parameter indicates if we are allowed to make additional
	/// run-time assumptions.			/// run-time assumptions.
	int getPtrStride(PredicatedScalarEvolution &PSE, Value Ptr, const Loop Lp,			int getPtrStride(PredicatedScalarEvolution &PSE, Value Ptr, const Loop Lp,
	const ValueToValueMap &StridesMap = ValueToValueMap(),			const ValueToValueMap &StridesMap = ValueToValueMap(),
	bool Assume = false);			bool Assume = false);

	/// \brief Returns true if the memory operations \p A and \p B are consecutive.			/// \brief Returns true if the memory operations \p A and \p B are consecutive.
	/// This is a simple API that does not depend on the analysis pass.			/// This is a simple API that does not depend on the analysis pass.
	bool isConsecutiveAccess(Value A, Value B, const DataLayout &DL,			bool isConsecutiveAccess(Value A, Value B, const DataLayout &DL,
	ScalarEvolution &SE, bool CheckType = true);			ScalarEvolution &SE, bool CheckType = true);

	/// \brief This analysis provides dependence information for the memory accesses			inline Instruction *
	/// of a loop.			MemoryDepChecker::Dependence::getSource(const LoopAccessInfo &LAI) const {
	///
	/// It runs the analysis for a loop on demand. This can be initiated by
	/// querying the loop access info via LAA::getInfo. getInfo return a
	/// LoopAccessInfo object. See this class for the specifics of what information
	/// is provided.
	class LoopAccessAnalysis : public FunctionPass {
	public:
	static char ID;

	LoopAccessAnalysis() : FunctionPass(ID) {
	initializeLoopAccessAnalysisPass(*PassRegistry::getPassRegistry());
	}

	bool runOnFunction(Function &F) override;

	void getAnalysisUsage(AnalysisUsage &AU) const override;

	/// \brief Query the result of the loop access information for the loop \p L.
	///
	/// If the client speculates (and then issues run-time checks) for the values
	/// of symbolic strides, \p Strides provides the mapping (see
	/// replaceSymbolicStrideSCEV). If there is no cached result available run
	/// the analysis.
	const LoopAccessInfo &getInfo(Loop *L, const ValueToValueMap &Strides);

	void releaseMemory() override {
	// Invalidate the cache when the pass is freed.
	LoopAccessInfoMap.clear();
	}

	/// \brief Print the result of the analysis when invoked with -analyze.
	void print(raw_ostream &OS, const Module *M = nullptr) const override;

	private:
	/// \brief The cache.
	DenseMap<Loop *, std::unique_ptr<LoopAccessInfo>> LoopAccessInfoMap;

	// The used analysis passes.
	ScalarEvolution *SE;
	const TargetLibraryInfo *TLI;
	AliasAnalysis *AA;
	DominatorTree *DT;
	LoopInfo *LI;
	};

	inline Instruction *MemoryDepChecker::Dependence::getSource(
	const LoopAccessInfo &LAI) const {
	return LAI.getDepChecker().getMemoryInstructions()[Source];			return LAI.getDepChecker().getMemoryInstructions()[Source];
	}			}

	inline Instruction *MemoryDepChecker::Dependence::getDestination(			inline Instruction *MemoryDepChecker::Dependence::getDestination(
	const LoopAccessInfo &LAI) const {			const LoopAccessInfo &LAI) const {
	return LAI.getDepChecker().getMemoryInstructions()[Destination];			return LAI.getDepChecker().getMemoryInstructions()[Destination];
	}			}

	} // End llvm namespace			} // End llvm namespace

	#endif			#endif

include/llvm/Transforms/Utils/LoopVersioning.h

	Show All 11 Lines
	// emits checks to prove this.			// emits checks to prove this.
	//			//
	//===----------------------------------------------------------------------===//			//===----------------------------------------------------------------------===//

	#ifndef LLVM_TRANSFORMS_UTILS_LOOPVERSIONING_H			#ifndef LLVM_TRANSFORMS_UTILS_LOOPVERSIONING_H
	#define LLVM_TRANSFORMS_UTILS_LOOPVERSIONING_H			#define LLVM_TRANSFORMS_UTILS_LOOPVERSIONING_H

	#include "llvm/Analysis/LoopAccessAnalysis.h"			#include "llvm/Analysis/LoopAccessAnalysis.h"
				#include "llvm/Analysis/LoopAccessInfo.h"
	#include "llvm/Analysis/ScalarEvolution.h"			#include "llvm/Analysis/ScalarEvolution.h"
	#include "llvm/Transforms/Utils/ValueMapper.h"
	#include "llvm/Transforms/Utils/LoopUtils.h"			#include "llvm/Transforms/Utils/LoopUtils.h"
				#include "llvm/Transforms/Utils/ValueMapper.h"

	namespace llvm {			namespace llvm {

	class Loop;			class Loop;
	class LoopAccessInfo;			class LoopAccessInfo;
	class LoopInfo;			class LoopInfo;
	class ScalarEvolution;			class ScalarEvolution;

	▲ Show 20 Lines • Show All 122 Lines • Show Last 20 Lines

lib/Analysis/LoopAccessAnalysis.cpp

//===- LoopAccessAnalysis.cpp - Loop Access Analysis Implementation --------==//		//===- LoopAccessAnalysis.cpp - Loop Access Analysis Implementation --------==//
//		//
// The LLVM Compiler Infrastructure		// The LLVM Compiler Infrastructure
//		//
// This file is distributed under the University of Illinois Open Source		// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.		// License. See LICENSE.TXT for details.
//		//
//===----------------------------------------------------------------------===//		//===----------------------------------------------------------------------===//
//		//
// The implementation for the loop memory dependence that was originally		// The implementation for the loop memory dependence that was originally
// developed for the loop vectorizer.		// developed for the loop vectorizer.
//		//
//===----------------------------------------------------------------------===//		//===----------------------------------------------------------------------===//

#include "llvm/Analysis/LoopAccessAnalysis.h"		#include "llvm/Analysis/LoopAccessAnalysis.h"
		#include "llvm/Analysis/LoopAccessInfo.h"
#include "llvm/Analysis/LoopInfo.h"		#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/ScalarEvolutionExpander.h"		#include "llvm/Analysis/ScalarEvolutionExpander.h"
#include "llvm/Analysis/TargetLibraryInfo.h"		#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/ValueTracking.h"		#include "llvm/Analysis/ValueTracking.h"
		#include "llvm/Analysis/VectorUtils.h"
#include "llvm/IR/DiagnosticInfo.h"		#include "llvm/IR/DiagnosticInfo.h"
#include "llvm/IR/Dominators.h"		#include "llvm/IR/Dominators.h"
#include "llvm/IR/IRBuilder.h"		#include "llvm/IR/IRBuilder.h"
#include "llvm/Support/Debug.h"		#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"		#include "llvm/Support/raw_ostream.h"
#include "llvm/Analysis/VectorUtils.h"
using namespace llvm;		using namespace llvm;

#define DEBUG_TYPE "loop-accesses"		#define DEBUG_TYPE "loop-accesses"

static cl::opt<unsigned, true>		static cl::opt<unsigned, true>
VectorizationFactor("force-vector-width", cl::Hidden,		VectorizationFactor("force-vector-width", cl::Hidden,
cl::desc("Sets the SIMD width. Zero is autoselect."),		cl::desc("Sets the SIMD width. Zero is autoselect."),
cl::location(VectorizerParams::VectorizationFactor));		cl::location(VectorizerParams::VectorizationFactor));
▲ Show 20 Lines • Show All 1,887 Lines • ▼ Show 20 Lines	void LoopAccessInfo::print(raw_ostream &OS, unsigned Depth) const {

OS << "\n";		OS << "\n";

OS.indent(Depth) << "Expressions re-written:\n";		OS.indent(Depth) << "Expressions re-written:\n";
PSE.print(OS, Depth);		PSE.print(OS, Depth);
}		}

const LoopAccessInfo &		const LoopAccessInfo &
LoopAccessAnalysis::getInfo(Loop *L, const ValueToValueMap &Strides) {		LoopAccessFuncInfo::getInfo(Loop *L, const ValueToValueMap &Strides) {
auto &LAI = LoopAccessInfoMap[L];		auto &LAI = LoopAccessInfoMap[L];

#ifndef NDEBUG		#ifndef NDEBUG
assert((!LAI \|\| LAI->NumSymbolicStrides == Strides.size()) &&		assert((!LAI \|\| LAI->NumSymbolicStrides == Strides.size()) &&
"Symbolic strides changed for loop");		"Symbolic strides changed for loop");
#endif		#endif

if (!LAI) {		if (!LAI) {
const DataLayout &DL = L->getHeader()->getModule()->getDataLayout();		const DataLayout &DL = L->getHeader()->getModule()->getDataLayout();
LAI =		LAI = llvm::make_unique<LoopAccessInfo>(
llvm::make_unique<LoopAccessInfo>(L, SE, DL, TLI, AA, DT, LI, Strides);		L, AM->getSCEV(), DL, AM->getTLI(), AM->getAAResults(),
		AM->getDominatorTree(), AM->getLoopInfo(), Strides);
#ifndef NDEBUG		#ifndef NDEBUG
LAI->NumSymbolicStrides = Strides.size();		LAI->NumSymbolicStrides = Strides.size();
#endif		#endif
}		}
return *LAI.get();		return *LAI.get();
}		}

void LoopAccessAnalysis::print(raw_ostream &OS, const Module *M) const {		void LoopAccessFuncInfo::print(raw_ostream &OS, const Module *M) const {
LoopAccessAnalysis &LAA = const_cast<LoopAccessAnalysis >(this);		LoopInfo *LI = AM->getLoopInfo();

ValueToValueMap NoSymbolicStrides;		ValueToValueMap NoSymbolicStrides;

for (Loop TopLevelLoop : LI)		for (Loop TopLevelLoop : LI)
for (Loop *L : depth_first(TopLevelLoop)) {		for (Loop *L : depth_first(TopLevelLoop)) {
OS.indent(2) << L->getHeader()->getName() << ":\n";		OS.indent(2) << L->getHeader()->getName() << ":\n";
auto &LAI = LAA.getInfo(L, NoSymbolicStrides);		auto &LAI =
		const_cast<LoopAccessFuncInfo *>(this)->getInfo(L, NoSymbolicStrides);
LAI.print(OS, 4);		LAI.print(OS, 4);
}		}
}		}

bool LoopAccessAnalysis::runOnFunction(Function &F) {		class LoopAccessAMLegacy : public LoopAccessAMBase {
SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();		public:
auto *TLIP = getAnalysisIfAvailable<TargetLibraryInfoWrapperPass>();		LoopAccessAMLegacy(LoopAccessAnalysis &LAA) {
		davideUnsubmitted Not Done Reply Inline Actions As you're passing `getAnalysis` everywhere, can't you also inline `TLIP ? &TLIP->getTLI() : nullptr` instead of assigning `TLI` and passing the variable? davide: As you're passing `getAnalysis` everywhere, can't you also inline `TLIP ? &TLIP->getTLI()…
		SE = &LAA.getAnalysis<ScalarEvolutionWrapperPass>().getSE();
		auto *TLIP = LAA.getAnalysisIfAvailable<TargetLibraryInfoWrapperPass>();
TLI = TLIP ? &TLIP->getTLI() : nullptr;		TLI = TLIP ? &TLIP->getTLI() : nullptr;
AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();		AA = &LAA.getAnalysis<AAResultsWrapperPass>().getAAResults();
DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();		DT = &LAA.getAnalysis<DominatorTreeWrapperPass>().getDomTree();
LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();		LI = &LAA.getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
		}
		TargetLibraryInfo *getTLI() override { return TLI; }
		AliasAnalysis *getAAResults() override { return AA; }
		DominatorTree *getDominatorTree() override { return DT; }
		LoopInfo *getLoopInfo() override { return LI; }
		ScalarEvolution *getSCEV() override { return SE; }

		private:
		ScalarEvolution *SE;
		TargetLibraryInfo *TLI;
		AliasAnalysis *AA;
		DominatorTree *DT;
		LoopInfo *LI;
		};

		bool LoopAccessAnalysis::runOnFunction(Function &F) {
		LAFI.setAM(new LoopAccessAMLegacy(*this));
return false;		return false;
}		}

void LoopAccessAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {		void LoopAccessAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
AU.addRequired<ScalarEvolutionWrapperPass>();		AU.addRequired<ScalarEvolutionWrapperPass>();
AU.addRequired<AAResultsWrapperPass>();		AU.addRequired<AAResultsWrapperPass>();
AU.addRequired<DominatorTreeWrapperPass>();		AU.addRequired<DominatorTreeWrapperPass>();
AU.addRequired<LoopInfoWrapperPass>();		AU.addRequired<LoopInfoWrapperPass>();
Show All 20 Lines

lib/Transforms/Scalar/LoopDistribute.cpp

Show First 20 Lines • Show All 602 Lines • ▼ Show 20 Lines	bool processLoop(LoopAccessAnalysis *LAA) {

BasicBlock *PH = L->getLoopPreheader();		BasicBlock *PH = L->getLoopPreheader();
if (!PH)		if (!PH)
return fail("no preheader");		return fail("no preheader");
if (!L->getExitBlock())		if (!L->getExitBlock())
return fail("multiple exit blocks");		return fail("multiple exit blocks");

// LAA will check that we only have a single exiting block.		// LAA will check that we only have a single exiting block.
LAI = &LAA->getInfo(L, ValueToValueMap());		LAI = &LAA->getInfo().getInfo(L, ValueToValueMap());
		anemetUnsubmitted Not Done Reply Inline Actions getInfo().getInfo(...), really? What is the difference between LAFI and LAA conceptually? Without knowing much about the new PM, I see that you split out the cache from LAA (which was pretty much all it contained). Should this perhaps be: LAA->getCache().getInfo(..) or getLoopInfo(..) ? anemet: getInfo().getInfo(...), really? What is the difference between LAFI and LAA conceptually?

// Currently, we only distribute to isolate the part of the loop with		// Currently, we only distribute to isolate the part of the loop with
// dependence cycles to enable partial vectorization.		// dependence cycles to enable partial vectorization.
if (LAI->canVectorizeMemory())		if (LAI->canVectorizeMemory())
return fail("memory operations are safe for vectorization");		return fail("memory operations are safe for vectorization");

auto *Dependences = LAI->getDepChecker().getDependences();		auto *Dependences = LAI->getDepChecker().getDependences();
if (!Dependences \|\| Dependences->empty())		if (!Dependences \|\| Dependences->empty())
▲ Show 20 Lines • Show All 322 Lines • Show Last 20 Lines

lib/Transforms/Scalar/LoopIdiomRecognize.cpp

	Show All 25 Lines
	// i64 and larger types when i64 is legal and the value has few bits set. It			// i64 and larger types when i64 is legal and the value has few bits set. It
	// would be good to enhance isel to emit a loop for ctpop in this case.			// would be good to enhance isel to emit a loop for ctpop in this case.
	//			//
	// This could recognize common matrix multiplies and dot product idioms and			// This could recognize common matrix multiplies and dot product idioms and
	// replace them with calls to BLAS (if linked in??).			// replace them with calls to BLAS (if linked in??).
	//			//
	//===----------------------------------------------------------------------===//			//===----------------------------------------------------------------------===//

	#include "llvm/Transforms/Scalar.h"
	#include "llvm/ADT/MapVector.h"			#include "llvm/ADT/MapVector.h"
	#include "llvm/ADT/SetVector.h"			#include "llvm/ADT/SetVector.h"
	#include "llvm/ADT/Statistic.h"			#include "llvm/ADT/Statistic.h"
	#include "llvm/Analysis/AliasAnalysis.h"			#include "llvm/Analysis/AliasAnalysis.h"
	#include "llvm/Analysis/BasicAliasAnalysis.h"			#include "llvm/Analysis/BasicAliasAnalysis.h"
	#include "llvm/Analysis/GlobalsModRef.h"			#include "llvm/Analysis/GlobalsModRef.h"
	#include "llvm/Analysis/LoopPass.h"
	#include "llvm/Analysis/LoopAccessAnalysis.h"			#include "llvm/Analysis/LoopAccessAnalysis.h"
				#include "llvm/Analysis/LoopAccessInfo.h"
				#include "llvm/Analysis/LoopPass.h"
	#include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"			#include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
	#include "llvm/Analysis/ScalarEvolutionExpander.h"			#include "llvm/Analysis/ScalarEvolutionExpander.h"
	#include "llvm/Analysis/ScalarEvolutionExpressions.h"			#include "llvm/Analysis/ScalarEvolutionExpressions.h"
	#include "llvm/Analysis/TargetLibraryInfo.h"			#include "llvm/Analysis/TargetLibraryInfo.h"
	#include "llvm/Analysis/TargetTransformInfo.h"			#include "llvm/Analysis/TargetTransformInfo.h"
	#include "llvm/Analysis/ValueTracking.h"			#include "llvm/Analysis/ValueTracking.h"
	#include "llvm/IR/DataLayout.h"			#include "llvm/IR/DataLayout.h"
	#include "llvm/IR/Dominators.h"			#include "llvm/IR/Dominators.h"
	#include "llvm/IR/IRBuilder.h"			#include "llvm/IR/IRBuilder.h"
	#include "llvm/IR/IntrinsicInst.h"			#include "llvm/IR/IntrinsicInst.h"
	#include "llvm/IR/Module.h"			#include "llvm/IR/Module.h"
	#include "llvm/Support/Debug.h"			#include "llvm/Support/Debug.h"
	#include "llvm/Support/raw_ostream.h"			#include "llvm/Support/raw_ostream.h"
				#include "llvm/Transforms/Scalar.h"
	#include "llvm/Transforms/Utils/BuildLibCalls.h"			#include "llvm/Transforms/Utils/BuildLibCalls.h"
	#include "llvm/Transforms/Utils/Local.h"			#include "llvm/Transforms/Utils/Local.h"
	#include "llvm/Transforms/Utils/LoopUtils.h"			#include "llvm/Transforms/Utils/LoopUtils.h"
	using namespace llvm;			using namespace llvm;

	#define DEBUG_TYPE "loop-idiom"			#define DEBUG_TYPE "loop-idiom"

	STATISTIC(NumMemSet, "Number of memset's formed from loop stores");			STATISTIC(NumMemSet, "Number of memset's formed from loop stores");
	▲ Show 20 Lines • Show All 991 Lines • Show Last 20 Lines

lib/Transforms/Scalar/LoopLoadElimination.cpp

Show First 20 Lines • Show All 546 Lines • ▼ Show 20 Lines	for (Loop TopLevelLoop : LI)
for (Loop *L : depth_first(TopLevelLoop))		for (Loop *L : depth_first(TopLevelLoop))
// We only handle inner-most loops.		// We only handle inner-most loops.
if (L->empty())		if (L->empty())
Worklist.push_back(L);		Worklist.push_back(L);

// Now walk the identified inner loops.		// Now walk the identified inner loops.
bool Changed = false;		bool Changed = false;
for (Loop *L : Worklist) {		for (Loop *L : Worklist) {
const LoopAccessInfo &LAI = LAA->getInfo(L, ValueToValueMap());		const LoopAccessInfo &LAI = LAA->getInfo().getInfo(L, ValueToValueMap());
		davideUnsubmitted Not Done Reply Inline Actions I agree with Adam here, the getInfo().getInfo() is just very weird davide: I agree with Adam here, the getInfo().getInfo() is just very weird
// The actual work is performed by LoadEliminationForLoop.		// The actual work is performed by LoadEliminationForLoop.
LoadEliminationForLoop LEL(L, LI, LAI, DT);		LoadEliminationForLoop LEL(L, LI, LAI, DT);
Changed \|= LEL.processLoop();		Changed \|= LEL.processLoop();
}		}

// Process each loop nest in the function.		// Process each loop nest in the function.
return Changed;		return Changed;
}		}
Show All 31 Lines

lib/Transforms/Scalar/LoopVersioningLICM.cpp

Show First 20 Lines • Show All 405 Lines • ▼ Show 20 Lines	bool LoopVersioningLICM::legalLoopInstructions() {
// instruction safety.		// instruction safety.
for (auto *Block : CurLoop->getBlocks())		for (auto *Block : CurLoop->getBlocks())
for (auto &Inst : *Block) {		for (auto &Inst : *Block) {
// If instruction is unsafe just return false.		// If instruction is unsafe just return false.
if (!instructionSafeForVersioning(&Inst))		if (!instructionSafeForVersioning(&Inst))
return false;		return false;
}		}
// Get LoopAccessInfo from current loop.		// Get LoopAccessInfo from current loop.
LAI = &LAA->getInfo(CurLoop, Strides);		LAI = &LAA->getInfo().getInfo(CurLoop, Strides);
// Check LoopAccessInfo for need of runtime check.		// Check LoopAccessInfo for need of runtime check.
if (LAI->getRuntimePointerChecking()->getChecks().empty()) {		if (LAI->getRuntimePointerChecking()->getChecks().empty()) {
DEBUG(dbgs() << " LAA: Runtime check not found !!\n");		DEBUG(dbgs() << " LAA: Runtime check not found !!\n");
return false;		return false;
}		}
// Number of runtime-checks should be less then RuntimeMemoryCheckThreshold		// Number of runtime-checks should be less then RuntimeMemoryCheckThreshold
if (LAI->getNumRuntimePointerChecks() >		if (LAI->getNumRuntimePointerChecks() >
VectorizerParams::RuntimeMemoryCheckThreshold) {		VectorizerParams::RuntimeMemoryCheckThreshold) {
▲ Show 20 Lines • Show All 175 Lines • Show Last 20 Lines

lib/Transforms/Utils/LoopVersioning.cpp

Show First 20 Lines • Show All 262 Lines • ▼ Show 20 Lines	for (Loop TopLevelLoop : LI)
for (Loop *L : depth_first(TopLevelLoop))		for (Loop *L : depth_first(TopLevelLoop))
// We only handle inner-most loops.		// We only handle inner-most loops.
if (L->empty())		if (L->empty())
Worklist.push_back(L);		Worklist.push_back(L);

// Now walk the identified inner loops.		// Now walk the identified inner loops.
bool Changed = false;		bool Changed = false;
for (Loop *L : Worklist) {		for (Loop *L : Worklist) {
const LoopAccessInfo &LAI = LAA->getInfo(L, ValueToValueMap());		const LoopAccessInfo &LAI = LAA->getInfo().getInfo(L, ValueToValueMap());
if (LAI.getNumRuntimePointerChecks() \|\|		if (LAI.getNumRuntimePointerChecks() \|\|
!LAI.PSE.getUnionPredicate().isAlwaysTrue()) {		!LAI.PSE.getUnionPredicate().isAlwaysTrue()) {
LoopVersioning LVer(LAI, L, LI, DT, SE);		LoopVersioning LVer(LAI, L, LI, DT, SE);
LVer.versionLoop();		LVer.versionLoop();
LVer.annotateLoopWithNoAlias();		LVer.annotateLoopWithNoAlias();
Changed = true;		Changed = true;
}		}
}		}
Show All 35 Lines

lib/Transforms/Vectorize/LoopVectorize.cpp

	Show First 20 Lines • Show All 991 Lines • ▼ Show 20 Lines
	Uniforms.insert(I);			Uniforms.insert(I);

	// Insert all operands.			// Insert all operands.
	Worklist.insert(Worklist.end(), I->op_begin(), I->op_end());			Worklist.insert(Worklist.end(), I->op_begin(), I->op_end());
	}			}
	}			}

	bool LoopVectorizationLegality::canVectorizeMemory() {			bool LoopVectorizationLegality::canVectorizeMemory() {
	LAI = &LAA->getInfo(TheLoop, Strides);			LAI = &LAA->getInfo().getInfo(TheLoop, Strides);
	auto &OptionalReport = LAI->getReport();			auto &OptionalReport = LAI->getReport();
	if (OptionalReport)			if (OptionalReport)
	emitAnalysis(VectorizationReport(*OptionalReport));			emitAnalysis(VectorizationReport(*OptionalReport));
	if (!LAI->canVectorizeMemory())			if (!LAI->canVectorizeMemory())
	return false;			return false;

	if (LAI->hasStoreToLoopInvariantAddress()) {			if (LAI->hasStoreToLoopInvariantAddress()) {
	emitAnalysis(			emitAnalysis(
	▲ Show 20 Lines • Show All 991 Lines • Show Last 20 Lines

lib/Transforms/Vectorize/SLPVectorizer.cpp

	Show All 20 Lines
	#include "llvm/ADT/SetVector.h"			#include "llvm/ADT/SetVector.h"
	#include "llvm/ADT/Statistic.h"			#include "llvm/ADT/Statistic.h"
	#include "llvm/Analysis/AliasAnalysis.h"			#include "llvm/Analysis/AliasAnalysis.h"
	#include "llvm/Analysis/AssumptionCache.h"			#include "llvm/Analysis/AssumptionCache.h"
	#include "llvm/Analysis/CodeMetrics.h"			#include "llvm/Analysis/CodeMetrics.h"
	#include "llvm/Analysis/DemandedBits.h"			#include "llvm/Analysis/DemandedBits.h"
	#include "llvm/Analysis/GlobalsModRef.h"			#include "llvm/Analysis/GlobalsModRef.h"
	#include "llvm/Analysis/LoopAccessAnalysis.h"			#include "llvm/Analysis/LoopAccessAnalysis.h"
	#include "llvm/Analysis/LoopAccessAnalysis.h"			#include "llvm/Analysis/LoopAccessInfo.h"
	#include "llvm/Analysis/LoopInfo.h"			#include "llvm/Analysis/LoopInfo.h"
	#include "llvm/Analysis/ScalarEvolution.h"			#include "llvm/Analysis/ScalarEvolution.h"
	#include "llvm/Analysis/ScalarEvolutionExpressions.h"			#include "llvm/Analysis/ScalarEvolutionExpressions.h"
	#include "llvm/Analysis/TargetTransformInfo.h"			#include "llvm/Analysis/TargetTransformInfo.h"
	#include "llvm/Analysis/ValueTracking.h"			#include "llvm/Analysis/ValueTracking.h"
	#include "llvm/Analysis/VectorUtils.h"			#include "llvm/Analysis/VectorUtils.h"
	#include "llvm/IR/DataLayout.h"			#include "llvm/IR/DataLayout.h"
	#include "llvm/IR/Dominators.h"			#include "llvm/IR/Dominators.h"
	▲ Show 20 Lines • Show All 991 Lines • Show Last 20 Lines

This is an archive of the discontinued LLVM Phabricator instance.

[new PM] port LoopAccessAnalysis to new pass manager (part-1)
ClosedPublic

Details

Diff Detail

Event Timeline

Revision Contents

Diff 58194

include/llvm/Analysis/LoopAccessAnalysis.h

include/llvm/Analysis/LoopAccessInfo.h

include/llvm/Transforms/Utils/LoopVersioning.h

lib/Analysis/LoopAccessAnalysis.cpp

lib/Transforms/Scalar/LoopDistribute.cpp

lib/Transforms/Scalar/LoopIdiomRecognize.cpp

lib/Transforms/Scalar/LoopLoadElimination.cpp

lib/Transforms/Scalar/LoopVersioningLICM.cpp

lib/Transforms/Utils/LoopVersioning.cpp

lib/Transforms/Vectorize/LoopVectorize.cpp

lib/Transforms/Vectorize/SLPVectorizer.cpp

This is an archive of the discontinued LLVM Phabricator instance.

[new PM] port LoopAccessAnalysis to new pass manager (part-1)ClosedPublic

Details

Diff Detail

Event Timeline

Revision Contents

Diff 58194

include/llvm/Analysis/LoopAccessAnalysis.h

include/llvm/Analysis/LoopAccessInfo.h

include/llvm/Transforms/Utils/LoopVersioning.h

lib/Analysis/LoopAccessAnalysis.cpp

lib/Transforms/Scalar/LoopDistribute.cpp

lib/Transforms/Scalar/LoopIdiomRecognize.cpp

lib/Transforms/Scalar/LoopLoadElimination.cpp

lib/Transforms/Scalar/LoopVersioningLICM.cpp

lib/Transforms/Utils/LoopVersioning.cpp

lib/Transforms/Vectorize/LoopVectorize.cpp

lib/Transforms/Vectorize/SLPVectorizer.cpp

[new PM] port LoopAccessAnalysis to new pass manager (part-1)
ClosedPublic