Diff 156301

include/llvm/Analysis/VectorUtils.h

	Show All 9 Lines
	// This file defines some vectorizer utilities.			// This file defines some vectorizer utilities.
	//			//
	//===----------------------------------------------------------------------===//			//===----------------------------------------------------------------------===//

	#ifndef LLVM_ANALYSIS_VECTORUTILS_H			#ifndef LLVM_ANALYSIS_VECTORUTILS_H
	#define LLVM_ANALYSIS_VECTORUTILS_H			#define LLVM_ANALYSIS_VECTORUTILS_H

	#include "llvm/ADT/MapVector.h"			#include "llvm/ADT/MapVector.h"
				#include "llvm/Analysis/LoopAccessAnalysis.h"
	#include "llvm/Analysis/TargetLibraryInfo.h"			#include "llvm/Analysis/TargetLibraryInfo.h"
	#include "llvm/IR/IRBuilder.h"			#include "llvm/IR/IRBuilder.h"

	namespace llvm {			namespace llvm {

	template <typename T> class ArrayRef;			template <typename T> class ArrayRef;
	class DemandedBits;			class DemandedBits;
	class GetElementPtrInst;			class GetElementPtrInst;
	▲ Show 20 Lines • Show All 145 Lines • ▼ Show 20 Lines
	///			///
	/// This function generates code that concatenate the vectors in \p Vecs into a			/// This function generates code that concatenate the vectors in \p Vecs into a
	/// single large vector. The number of vectors should be greater than one, and			/// single large vector. The number of vectors should be greater than one, and
	/// their element types should be the same. The number of elements in the			/// their element types should be the same. The number of elements in the
	/// vectors should also be the same; however, if the last vector has fewer			/// vectors should also be the same; however, if the last vector has fewer
	/// elements, it will be padded with undefs.			/// elements, it will be padded with undefs.
	Value concatenateVectors(IRBuilder<> &Builder, ArrayRef<Value > Vecs);			Value concatenateVectors(IRBuilder<> &Builder, ArrayRef<Value > Vecs);

				/// The group of interleaved loads/stores sharing the same stride and
				/// close to each other.
				///
				/// Each member in this group has an index starting from 0, and the largest
				/// index should be less than interleaved factor, which is equal to the absolute
				/// value of the access's stride.
				///
				/// E.g. An interleaved load group of factor 4:
				/// for (unsigned i = 0; i < 1024; i+=4) {
				/// a = A[i]; // Member of index 0
				/// b = A[i+1]; // Member of index 1
				/// d = A[i+3]; // Member of index 3
				/// ...
				/// }
				///
				/// An interleaved store group of factor 4:
				/// for (unsigned i = 0; i < 1024; i+=4) {
				/// ...
				/// A[i] = a; // Member of index 0
				/// A[i+1] = b; // Member of index 1
				/// A[i+2] = c; // Member of index 2
				/// A[i+3] = d; // Member of index 3
				/// }
				///
				/// Note: the interleaved load group could have gaps (missing members), but
				/// the interleaved store group doesn't allow gaps.
				class InterleaveGroup {
				public:
				InterleaveGroup(Instruction *Instr, int Stride, unsigned Align)
				: Align(Align), InsertPos(Instr) {
				assert(Align && "The alignment should be non-zero");

				Factor = std::abs(Stride);
				assert(Factor > 1 && "Invalid interleave factor");

				Reverse = Stride < 0;
				Members[0] = Instr;
				}

				bool isReverse() const { return Reverse; }
				unsigned getFactor() const { return Factor; }
				unsigned getAlignment() const { return Align; }
				unsigned getNumMembers() const { return Members.size(); }

				/// Try to insert a new member \p Instr with index \p Index and
				/// alignment \p NewAlign. The index is related to the leader and it could be
				/// negative if it is the new leader.
				///
				/// \returns false if the instruction doesn't belong to the group.
				bool insertMember(Instruction *Instr, int Index, unsigned NewAlign) {
				assert(NewAlign && "The new member's alignment should be non-zero");

				int Key = Index + SmallestKey;

				// Skip if there is already a member with the same index.
				if (Members.count(Key))
				return false;

				if (Key > LargestKey) {
				// The largest index is always less than the interleave factor.
				if (Index >= static_cast<int>(Factor))
				return false;

				LargestKey = Key;
				} else if (Key < SmallestKey) {
				// The largest index is always less than the interleave factor.
				if (LargestKey - Key >= static_cast<int>(Factor))
				return false;

				SmallestKey = Key;
				}

				// It's always safe to select the minimum alignment.
				Align = std::min(Align, NewAlign);
				Members[Key] = Instr;
				return true;
				}

				/// Get the member with the given index \p Index
				///
				/// \returns nullptr if contains no such member.
				Instruction *getMember(unsigned Index) const {
				int Key = SmallestKey + Index;
				if (!Members.count(Key))
				xbolva00Unsubmitted Not Done Reply Inline Actions Do we need count? if (Members.find(Key) == Members.end()) return nullptr; ? xbolva00: Do we need count? if (Members.find(Key) == Members.end()) return nullptr; ?
				fhahnAuthorUnsubmitted Not Done Reply Inline Actions No need to count here I think, but I would prefer to keep this change NFC. Feel free to fix this in the the current version in LoopVectorize.cpp. Otherwise I can make the count() change separately too. Before submitting the patch, I will make sure it contains any changes made the LoopVectorize.cpp's version of the code. fhahn: No need to count here I think, but I would prefer to keep this change NFC. Feel free to fix…
				xbolva00Unsubmitted Not Done Reply Inline Actions https://reviews.llvm.org/D51054 xbolva00: https://reviews.llvm.org/D51054
				return nullptr;

				return Members.find(Key)->second;
				}

				/// Get the index for the given member. Unlike the key in the member
				/// map, the index starts from 0.
				unsigned getIndex(Instruction *Instr) const {
				for (auto I : Members)
				if (I.second == Instr)
				return I.first - SmallestKey;

				llvm_unreachable("InterleaveGroup contains no such member");
				}

				Instruction *getInsertPos() const { return InsertPos; }
				void setInsertPos(Instruction *Inst) { InsertPos = Inst; }

				/// Add metadata (e.g. alias info) from the instructions in this group to \p
				/// NewInst.
				///
				/// FIXME: this function currently does not add noalias metadata a'la
				/// addNewMedata. To do that we need to compute the intersection of the
				/// noalias info from all members.
				void addMetadata(Instruction *NewInst) const {
				SmallVector<Value *, 4> VL;
				std::transform(Members.begin(), Members.end(), std::back_inserter(VL),
				[](std::pair<int, Instruction *> p) { return p.second; });
				propagateMetadata(NewInst, VL);
				}

				private:
				unsigned Factor; // Interleave Factor.
				bool Reverse;
				unsigned Align;
				DenseMap<int, Instruction *> Members;
				int SmallestKey = 0;
				int LargestKey = 0;

				// To avoid breaking dependences, vectorized instructions of an interleave
				// group should be inserted at either the first load or the last store in
				// program order.
				//
				// E.g. %even = load i32 // Insert Position
				// %add = add i32 %even // Use of %even
				// %odd = load i32
				//
				// store i32 %even
				// %odd = add i32 // Def of %odd
				// store i32 %odd // Insert Position
				Instruction *InsertPos;
				};

				/// Drive the analysis of interleaved memory accesses in the loop.
				///
				/// Use this class to analyze interleaved accesses only when we can vectorize
				/// a loop. Otherwise it's meaningless to do analysis as the vectorization
				/// on interleaved accesses is unsafe.
				///
				/// The analysis collects interleave groups and records the relationships
				/// between the member and the group in a map.
				class InterleavedAccessInfo {
				public:
				InterleavedAccessInfo(PredicatedScalarEvolution &PSE, Loop *L,
				DominatorTree DT, LoopInfo LI,
				const LoopAccessInfo *LAI)
				: PSE(PSE), TheLoop(L), DT(DT), LI(LI), LAI(LAI) {}

				~InterleavedAccessInfo() {
				SmallPtrSet<InterleaveGroup *, 4> DelSet;
				// Avoid releasing a pointer twice.
				for (auto &I : InterleaveGroupMap)
				DelSet.insert(I.second);
				for (auto *Ptr : DelSet)
				delete Ptr;
				}

				/// Analyze the interleaved accesses and collect them in interleave
				/// groups. Substitute symbolic strides using \p Strides.
				void analyzeInterleaving();

				/// Check if \p Instr belongs to any interleave group.
				bool isInterleaved(Instruction *Instr) const {
				return InterleaveGroupMap.count(Instr);
				}

				/// Get the interleave group that \p Instr belongs to.
				///
				/// \returns nullptr if doesn't have such group.
				InterleaveGroup getInterleaveGroup(Instruction Instr) const {
				if (InterleaveGroupMap.count(Instr))
				return InterleaveGroupMap.find(Instr)->second;
				return nullptr;
				}

				/// Returns true if an interleaved group that may access memory
				/// out-of-bounds requires a scalar epilogue iteration for correctness.
				bool requiresScalarEpilogue() const { return RequiresScalarEpilogue; }

				private:
				/// A wrapper around ScalarEvolution, used to add runtime SCEV checks.
				/// Simplifies SCEV expressions in the context of existing SCEV assumptions.
				/// The interleaved access analysis can also add new predicates (for example
				/// by versioning strides of pointers).
				PredicatedScalarEvolution &PSE;

				Loop *TheLoop;
				DominatorTree *DT;
				LoopInfo *LI;
				const LoopAccessInfo *LAI;

				/// True if the loop may contain non-reversed interleaved groups with
				/// out-of-bounds accesses. We ensure we don't speculatively access memory
				/// out-of-bounds by executing at least one scalar epilogue iteration.
				bool RequiresScalarEpilogue = false;

				/// Holds the relationships between the members and the interleave group.
				DenseMap<Instruction , InterleaveGroup > InterleaveGroupMap;

				/// Holds dependences among the memory accesses in the loop. It maps a source
				/// access to a set of dependent sink accesses.
				DenseMap<Instruction , SmallPtrSet<Instruction , 2>> Dependences;

				/// The descriptor for a strided memory access.
				struct StrideDescriptor {
				StrideDescriptor() = default;
				StrideDescriptor(int64_t Stride, const SCEV *Scev, uint64_t Size,
				unsigned Align)
				: Stride(Stride), Scev(Scev), Size(Size), Align(Align) {}

				// The access's stride. It is negative for a reverse access.
				int64_t Stride = 0;

				// The scalar expression of this access.
				const SCEV *Scev = nullptr;

				// The size of the memory object.
				uint64_t Size = 0;

				// The alignment of this access.
				unsigned Align = 0;
				};

				/// A type for holding instructions and their stride descriptors.
				using StrideEntry = std::pair<Instruction *, StrideDescriptor>;

				/// Create a new interleave group with the given instruction \p Instr,
				/// stride \p Stride and alignment \p Align.
				///
				/// \returns the newly created interleave group.
				InterleaveGroup createInterleaveGroup(Instruction Instr, int Stride,
				unsigned Align) {
				assert(!InterleaveGroupMap.count(Instr) &&
				"Already in an interleaved access group");
				InterleaveGroupMap[Instr] = new InterleaveGroup(Instr, Stride, Align);
				return InterleaveGroupMap[Instr];
				}

				/// Release the group and remove all the relationships.
				void releaseGroup(InterleaveGroup *Group) {
				for (unsigned i = 0; i < Group->getFactor(); i++)
				if (Instruction *Member = Group->getMember(i))
				InterleaveGroupMap.erase(Member);

				delete Group;
				}

				/// Collect all the accesses with a constant stride in program order.
				void collectConstStrideAccesses(
				MapVector<Instruction *, StrideDescriptor> &AccessStrideInfo,
				const ValueToValueMap &Strides);

				/// Returns true if \p Stride is allowed in an interleaved group.
				static bool isStrided(int Stride);

				/// Returns true if \p BB is a predicated block.
				bool isPredicated(BasicBlock *BB) const {
				return LoopAccessInfo::blockNeedsPredication(BB, TheLoop, DT);
				}

				/// Returns true if LoopAccessInfo can be used for dependence queries.
				bool areDependencesValid() const {
				return LAI && LAI->getDepChecker().getDependences();
				}

				/// Returns true if memory accesses \p A and \p B can be reordered, if
				/// necessary, when constructing interleaved groups.
				///
				/// \p A must precede \p B in program order. We return false if reordering is
				/// not necessary or is prevented because \p A and \p B may be dependent.
				bool canReorderMemAccessesForInterleavedGroups(StrideEntry *A,
				StrideEntry *B) const {
				// Code motion for interleaved accesses can potentially hoist strided loads
				// and sink strided stores. The code below checks the legality of the
				// following two conditions:
				//
				// 1. Potentially moving a strided load (B) before any store (A) that
				// precedes B, or
				//
				// 2. Potentially moving a strided store (A) after any load or store (B)
				// that A precedes.
				//
				// It's legal to reorder A and B if we know there isn't a dependence from A
				// to B. Note that this determination is conservative since some
				// dependences could potentially be reordered safely.

				// A is potentially the source of a dependence.
				auto *Src = A->first;
				auto SrcDes = A->second;

				// B is potentially the sink of a dependence.
				auto *Sink = B->first;
				auto SinkDes = B->second;

				// Code motion for interleaved accesses can't violate WAR dependences.
				// Thus, reordering is legal if the source isn't a write.
				if (!Src->mayWriteToMemory())
				return true;

				// At least one of the accesses must be strided.
				if (!isStrided(SrcDes.Stride) && !isStrided(SinkDes.Stride))
				return true;

				// If dependence information is not available from LoopAccessInfo,
				// conservatively assume the instructions can't be reordered.
				if (!areDependencesValid())
				return false;

				// If we know there is a dependence from source to sink, assume the
				// instructions can't be reordered. Otherwise, reordering is legal.
				return !Dependences.count(Src) \|\| !Dependences.lookup(Src).count(Sink);
				}

				/// Collect the dependences from LoopAccessInfo.
				///
				/// We process the dependences once during the interleaved access analysis to
				/// enable constant-time dependence queries.
				void collectDependences() {
				if (!areDependencesValid())
				return;
				auto *Deps = LAI->getDepChecker().getDependences();
				for (auto Dep : *Deps)
				Dependences[Dep.getSource(LAI)].insert(Dep.getDestination(LAI));
				}
				};

	} // llvm namespace			} // llvm namespace
				rengolinUnsubmitted Not Done Reply Inline Actions This sounds bad. If they have common signature we could have linking issues. Regardless, we should keep inline functions to cpp files, not headers. rengolin: This sounds bad. If they have common signature we could have linking issues. Regardless, we…
				fhahnAuthorUnsubmitted Not Done Reply Inline Actions Yep I did some digging but could not really pin down other users where they would be helpful. As indicated in the comment, neither LoopVectorize.cpp nor VectorUtils.h seems like appropriate places. However I am unsure what the ideal place would be? fhahn: Yep I did some digging but could not really pin down other users where they would be helpful.
				rengolinUnsubmitted Not Done Reply Inline Actions `getMemInstValueType` is only ever used in `LoopVectorize.cpp`, so could stay there until we find a better place. The other two, with your patch, seem to be used on both `LoopVectorize.cpp` and `VectorUtils.cpp` and they're not even in the same directory. But looking at what they are, there's absolutely nothing LV about them, they're just Value helpers, which could easily be transferred to LoadInst/StoreInst directly, as a member function. rengolin: `getMemInstValueType` is only ever used in `LoopVectorize.cpp`, so could stay there until we…

	#endif			#endif

include/llvm/IR/Instructions.h

	Show First 20 Lines • Show All 5,242 Lines • ▼ Show 20 Lines
	inline Value getPointerOperand(Value V) {			inline Value getPointerOperand(Value V) {
	if (auto *Ptr = getLoadStorePointerOperand(V))			if (auto *Ptr = getLoadStorePointerOperand(V))
	return Ptr;			return Ptr;
	if (auto *Gep = dyn_cast<GetElementPtrInst>(V))			if (auto *Gep = dyn_cast<GetElementPtrInst>(V))
	return Gep->getPointerOperand();			return Gep->getPointerOperand();
	return nullptr;			return nullptr;
	}			}

				/// A helper function that returns the alignment of load or store instruction.
				inline unsigned getMemInstAlignment(Value *I) {
				assert((isa<LoadInst>(I) \|\| isa<StoreInst>(I)) &&
				"Expected Load or Store instruction");
				if (auto *LI = dyn_cast<LoadInst>(I))
				return LI->getAlignment();
				return cast<StoreInst>(I)->getAlignment();
				}

				/// A helper function that returns the address space of the pointer operand of
				/// load or store instruction.
				inline unsigned getMemInstAddressSpace(Value *I) {
				assert((isa<LoadInst>(I) \|\| isa<StoreInst>(I)) &&
				"Expected Load or Store instruction");
				if (auto *LI = dyn_cast<LoadInst>(I))
				return LI->getPointerAddressSpace();
				return cast<StoreInst>(I)->getPointerAddressSpace();
				}

	} // end namespace llvm			} // end namespace llvm

	#endif // LLVM_IR_INSTRUCTIONS_H			#endif // LLVM_IR_INSTRUCTIONS_H

lib/Analysis/VectorUtils.cpp

Show All 9 Lines
// This file defines vectorizer utilities.		// This file defines vectorizer utilities.
//		//
//===----------------------------------------------------------------------===//		//===----------------------------------------------------------------------===//

#include "llvm/Analysis/VectorUtils.h"		#include "llvm/Analysis/VectorUtils.h"
#include "llvm/ADT/EquivalenceClasses.h"		#include "llvm/ADT/EquivalenceClasses.h"
#include "llvm/Analysis/DemandedBits.h"		#include "llvm/Analysis/DemandedBits.h"
#include "llvm/Analysis/LoopInfo.h"		#include "llvm/Analysis/LoopInfo.h"
		#include "llvm/Analysis/LoopIterator.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/IR/Constants.h"		#include "llvm/IR/Constants.h"
#include "llvm/IR/GetElementPtrTypeIterator.h"		#include "llvm/IR/GetElementPtrTypeIterator.h"
#include "llvm/IR/IRBuilder.h"		#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/PatternMatch.h"		#include "llvm/IR/PatternMatch.h"
#include "llvm/IR/Value.h"		#include "llvm/IR/Value.h"

		#define DEBUG_TYPE "vectorutils"

using namespace llvm;		using namespace llvm;
using namespace llvm::PatternMatch;		using namespace llvm::PatternMatch;

		/// Maximum factor for an interleaved memory access.
		static cl::opt<unsigned> MaxInterleaveGroupFactor(
		"max-interleave-group-factor", cl::Hidden,
		cl::desc("Maximum factor for an interleaved access group (default = 8)"),
		cl::init(8));

/// Identify if the intrinsic is trivially vectorizable.		/// Identify if the intrinsic is trivially vectorizable.
/// This method returns true if the intrinsic's argument types are all		/// This method returns true if the intrinsic's argument types are all
/// scalars for the scalar form of the intrinsic and all vectors for		/// scalars for the scalar form of the intrinsic and all vectors for
/// the vector form of the intrinsic.		/// the vector form of the intrinsic.
bool llvm::isTriviallyVectorizable(Intrinsic::ID ID) {		bool llvm::isTriviallyVectorizable(Intrinsic::ID ID) {
switch (ID) {		switch (ID) {
case Intrinsic::sqrt:		case Intrinsic::sqrt:
case Intrinsic::sin:		case Intrinsic::sin:
▲ Show 20 Lines • Show All 531 Lines • ▼ Show 20 Lines	if (NumVecs % 2 != 0)
TmpList.push_back(ResList[NumVecs - 1]);		TmpList.push_back(ResList[NumVecs - 1]);

ResList = TmpList;		ResList = TmpList;
NumVecs = ResList.size();		NumVecs = ResList.size();
} while (NumVecs > 1);		} while (NumVecs > 1);

return ResList[0];		return ResList[0];
}		}

		bool InterleavedAccessInfo::isStrided(int Stride) {
		unsigned Factor = std::abs(Stride);
		rengolinUnsubmitted Not Done Reply Inline Actions This is not strictly true for all users, which are many. $ grep -riI VectorUtils.h lib/Transforms/InstCombine/InstCombineVectorOps.cpp:#include "llvm/Analysis/VectorUtils.h" lib/Transforms/Scalar/Scalarizer.cpp:#include "llvm/Analysis/VectorUtils.h" lib/Transforms/Vectorize/LoopVectorizationLegality.cpp:#include "llvm/Analysis/VectorUtils.h" lib/Transforms/Vectorize/SLPVectorizer.cpp:#include "llvm/Analysis/VectorUtils.h" lib/Transforms/Vectorize/LoopVectorize.cpp:#include "llvm/Analysis/VectorUtils.h" lib/Transforms/Vectorize/LoadStoreVectorizer.cpp:#include "llvm/Analysis/VectorUtils.h" lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp:#include "llvm/Analysis/VectorUtils.h" lib/Analysis/InstructionSimplify.cpp:#include "llvm/Analysis/VectorUtils.h" lib/Analysis/VectorUtils.cpp:#include "llvm/Analysis/VectorUtils.h" lib/Analysis/LoopAccessAnalysis.cpp:#include "llvm/Analysis/VectorUtils.h" lib/Target/X86/X86InterleavedAccess.cpp:#include "llvm/Analysis/VectorUtils.h" lib/Target/ARM/ARMISelLowering.cpp:#include "llvm/Analysis/VectorUtils.h" lib/Target/AArch64/AArch64ISelLowering.cpp:#include "llvm/Analysis/VectorUtils.h" include/llvm/Analysis/TargetTransformInfoImpl.h:#include "llvm/Analysis/VectorUtils.h" rengolin: This is not strictly true for all users, which are many. $ grep -riI VectorUtils.h…
		return Factor >= 2 && Factor <= MaxInterleaveGroupFactor;
		}

		void InterleavedAccessInfo::collectConstStrideAccesses(
		MapVector<Instruction *, StrideDescriptor> &AccessStrideInfo,
		const ValueToValueMap &Strides) {
		auto &DL = TheLoop->getHeader()->getModule()->getDataLayout();

		// Since it's desired that the load/store instructions be maintained in
		// "program order" for the interleaved access analysis, we have to visit the
		// blocks in the loop in reverse postorder (i.e., in a topological order).
		// Such an ordering will ensure that any load/store that may be executed
		// before a second load/store will precede the second load/store in
		// AccessStrideInfo.
		LoopBlocksDFS DFS(TheLoop);
		DFS.perform(LI);
		for (BasicBlock *BB : make_range(DFS.beginRPO(), DFS.endRPO()))
		for (auto &I : *BB) {
		auto *LI = dyn_cast<LoadInst>(&I);
		auto *SI = dyn_cast<StoreInst>(&I);
		if (!LI && !SI)
		continue;

		Value *Ptr = getLoadStorePointerOperand(&I);
		// We don't check wrapping here because we don't know yet if Ptr will be
		// part of a full group or a group with gaps. Checking wrapping for all
		// pointers (even those that end up in groups with no gaps) will be overly
		// conservative. For full groups, wrapping should be ok since if we would
		// wrap around the address space we would do a memory access at nullptr
		// even without the transformation. The wrapping checks are therefore
		// deferred until after we've formed the interleaved groups.
		int64_t Stride = getPtrStride(PSE, Ptr, TheLoop, Strides,
		/Assume=/true, /ShouldCheckWrap=/false);

		const SCEV *Scev = replaceSymbolicStrideSCEV(PSE, Strides, Ptr);
		PointerType *PtrTy = dyn_cast<PointerType>(Ptr->getType());
		uint64_t Size = DL.getTypeAllocSize(PtrTy->getElementType());

		// An alignment of 0 means target ABI alignment.
		unsigned Align = getMemInstAlignment(&I);
		if (!Align)
		Align = DL.getABITypeAlignment(PtrTy->getElementType());

		AccessStrideInfo[&I] = StrideDescriptor(Stride, Scev, Size, Align);
		}
		}

		// Analyze interleaved accesses and collect them into interleaved load and
		// store groups.
		//
		// When generating code for an interleaved load group, we effectively hoist all
		// loads in the group to the location of the first load in program order. When
		// generating code for an interleaved store group, we sink all stores to the
		// location of the last store. This code motion can change the order of load
		// and store instructions and may break dependences.
		//
		// The code generation strategy mentioned above ensures that we won't violate
		// any write-after-read (WAR) dependences.
		//
		// E.g., for the WAR dependence: a = A[i]; // (1)
		// A[i] = b; // (2)
		//
		// The store group of (2) is always inserted at or below (2), and the load
		// group of (1) is always inserted at or above (1). Thus, the instructions will
		// never be reordered. All other dependences are checked to ensure the
		// correctness of the instruction reordering.
		//
		// The algorithm visits all memory accesses in the loop in bottom-up program
		// order. Program order is established by traversing the blocks in the loop in
		// reverse postorder when collecting the accesses.
		//
		// We visit the memory accesses in bottom-up order because it can simplify the
		// construction of store groups in the presence of write-after-write (WAW)
		// dependences.
		//
		// E.g., for the WAW dependence: A[i] = a; // (1)
		// A[i] = b; // (2)
		// A[i + 1] = c; // (3)
		//
		// We will first create a store group with (3) and (2). (1) can't be added to
		// this group because it and (2) are dependent. However, (1) can be grouped
		// with other accesses that may precede it in program order. Note that a
		// bottom-up order does not imply that WAW dependences should not be checked.
		void InterleavedAccessInfo::analyzeInterleaving() {
		LLVM_DEBUG(dbgs() << "LV: Analyzing interleaved accesses...\n");
		const ValueToValueMap &Strides = LAI->getSymbolicStrides();

		// Holds all accesses with a constant stride.
		MapVector<Instruction *, StrideDescriptor> AccessStrideInfo;
		collectConstStrideAccesses(AccessStrideInfo, Strides);

		if (AccessStrideInfo.empty())
		return;

		// Collect the dependences in the loop.
		collectDependences();

		// Holds all interleaved store groups temporarily.
		SmallSetVector<InterleaveGroup *, 4> StoreGroups;
		// Holds all interleaved load groups temporarily.
		SmallSetVector<InterleaveGroup *, 4> LoadGroups;

		// Search in bottom-up program order for pairs of accesses (A and B) that can
		// form interleaved load or store groups. In the algorithm below, access A
		// precedes access B in program order. We initialize a group for B in the
		// outer loop of the algorithm, and then in the inner loop, we attempt to
		// insert each A into B's group if:
		//
		// 1. A and B have the same stride,
		// 2. A and B have the same memory object size, and
		// 3. A belongs in B's group according to its distance from B.
		//
		// Special care is taken to ensure group formation will not break any
		// dependences.
		for (auto BI = AccessStrideInfo.rbegin(), E = AccessStrideInfo.rend();
		BI != E; ++BI) {
		Instruction *B = BI->first;
		StrideDescriptor DesB = BI->second;

		// Initialize a group for B if it has an allowable stride. Even if we don't
		// create a group for B, we continue with the bottom-up algorithm to ensure
		// we don't break any of B's dependences.
		InterleaveGroup *Group = nullptr;
		if (isStrided(DesB.Stride)) {
		Group = getInterleaveGroup(B);
		if (!Group) {
		LLVM_DEBUG(dbgs() << "LV: Creating an interleave group with:" << *B
		<< '\n');
		Group = createInterleaveGroup(B, DesB.Stride, DesB.Align);
		}
		if (B->mayWriteToMemory())
		StoreGroups.insert(Group);
		else
		LoadGroups.insert(Group);
		}

		for (auto AI = std::next(BI); AI != E; ++AI) {
		Instruction *A = AI->first;
		StrideDescriptor DesA = AI->second;

		// Our code motion strategy implies that we can't have dependences
		// between accesses in an interleaved group and other accesses located
		// between the first and last member of the group. Note that this also
		// means that a group can't have more than one member at a given offset.
		// The accesses in a group can have dependences with other accesses, but
		// we must ensure we don't extend the boundaries of the group such that
		// we encompass those dependent accesses.
		//
		// For example, assume we have the sequence of accesses shown below in a
		// stride-2 loop:
		//
		// (1, 2) is a group \| A[i] = a; // (1)
		// \| A[i-1] = b; // (2) \|
		// A[i-3] = c; // (3)
		// A[i] = d; // (4) \| (2, 4) is not a group
		//
		// Because accesses (2) and (3) are dependent, we can group (2) with (1)
		// but not with (4). If we did, the dependent access (3) would be within
		// the boundaries of the (2, 4) group.
		if (!canReorderMemAccessesForInterleavedGroups(&AI, &BI)) {
		// If a dependence exists and A is already in a group, we know that A
		// must be a store since A precedes B and WAR dependences are allowed.
		// Thus, A would be sunk below B. We release A's group to prevent this
		// illegal code motion. A will then be free to form another group with
		// instructions that precede it.
		if (isInterleaved(A)) {
		InterleaveGroup *StoreGroup = getInterleaveGroup(A);
		StoreGroups.remove(StoreGroup);
		releaseGroup(StoreGroup);
		}

		// If a dependence exists and A is not already in a group (or it was
		// and we just released it), B might be hoisted above A (if B is a
		// load) or another store might be sunk below A (if B is a store). In
		// either case, we can't add additional instructions to B's group. B
		// will only form a group with instructions that it precedes.
		break;
		}

		// At this point, we've checked for illegal code motion. If either A or B
		// isn't strided, there's nothing left to do.
		if (!isStrided(DesA.Stride) \|\| !isStrided(DesB.Stride))
		continue;

		// Ignore A if it's already in a group or isn't the same kind of memory
		// operation as B.
		// Note that mayReadFromMemory() isn't mutually exclusive to
		// mayWriteToMemory in the case of atomic loads. We shouldn't see those
		// here, canVectorizeMemory() should have returned false - except for the
		// case we asked for optimization remarks.
		if (isInterleaved(A) \|\|
		(A->mayReadFromMemory() != B->mayReadFromMemory()) \|\|
		(A->mayWriteToMemory() != B->mayWriteToMemory()))
		continue;

		// Check rules 1 and 2. Ignore A if its stride or size is different from
		// that of B.
		if (DesA.Stride != DesB.Stride \|\| DesA.Size != DesB.Size)
		continue;

		// Ignore A if the memory object of A and B don't belong to the same
		// address space
		if (getMemInstAddressSpace(A) != getMemInstAddressSpace(B))
		continue;

		// Calculate the distance from A to B.
		const SCEVConstant *DistToB = dyn_cast<SCEVConstant>(
		PSE.getSE()->getMinusSCEV(DesA.Scev, DesB.Scev));
		if (!DistToB)
		continue;
		int64_t DistanceToB = DistToB->getAPInt().getSExtValue();

		// Check rule 3. Ignore A if its distance to B is not a multiple of the
		// size.
		if (DistanceToB % static_cast<int64_t>(DesB.Size))
		continue;

		// Ignore A if either A or B is in a predicated block. Although we
		// currently prevent group formation for predicated accesses, we may be
		// able to relax this limitation in the future once we handle more
		// complicated blocks.
		if (isPredicated(A->getParent()) \|\| isPredicated(B->getParent()))
		continue;

		// The index of A is the index of B plus A's distance to B in multiples
		// of the size.
		int IndexA =
		Group->getIndex(B) + DistanceToB / static_cast<int64_t>(DesB.Size);

		// Try to insert A into B's group.
		if (Group->insertMember(A, IndexA, DesA.Align)) {
		LLVM_DEBUG(dbgs() << "LV: Inserted:" << *A << '\n'
		<< " into the interleave group with" << *B
		<< '\n');
		InterleaveGroupMap[A] = Group;

		// Set the first load in program order as the insert position.
		if (A->mayReadFromMemory())
		Group->setInsertPos(A);
		}
		} // Iteration over A accesses.
		} // Iteration over B accesses.

		// Remove interleaved store groups with gaps.
		for (InterleaveGroup *Group : StoreGroups)
		if (Group->getNumMembers() != Group->getFactor()) {
		LLVM_DEBUG(
		dbgs() << "LV: Invalidate candidate interleaved store group due "
		"to gaps.\n");
		releaseGroup(Group);
		}
		// Remove interleaved groups with gaps (currently only loads) whose memory
		// accesses may wrap around. We have to revisit the getPtrStride analysis,
		// this time with ShouldCheckWrap=true, since collectConstStrideAccesses does
		// not check wrapping (see documentation there).
		// FORNOW we use Assume=false;
		// TODO: Change to Assume=true but making sure we don't exceed the threshold
		// of runtime SCEV assumptions checks (thereby potentially failing to
		// vectorize altogether).
		// Additional optional optimizations:
		// TODO: If we are peeling the loop and we know that the first pointer doesn't
		// wrap then we can deduce that all pointers in the group don't wrap.
		// This means that we can forcefully peel the loop in order to only have to
		// check the first pointer for no-wrap. When we'll change to use Assume=true
		// we'll only need at most one runtime check per interleaved group.
		for (InterleaveGroup *Group : LoadGroups) {
		// Case 1: A full group. Can Skip the checks; For full groups, if the wide
		// load would wrap around the address space we would do a memory access at
		// nullptr even without the transformation.
		if (Group->getNumMembers() == Group->getFactor())
		continue;

		// Case 2: If first and last members of the group don't wrap this implies
		// that all the pointers in the group don't wrap.
		// So we check only group member 0 (which is always guaranteed to exist),
		// and group member Factor - 1; If the latter doesn't exist we rely on
		// peeling (if it is a non-reveresed accsess -- see Case 3).
		Value *FirstMemberPtr = getLoadStorePointerOperand(Group->getMember(0));
		if (!getPtrStride(PSE, FirstMemberPtr, TheLoop, Strides, /Assume=/false,
		/ShouldCheckWrap=/true)) {
		LLVM_DEBUG(
		dbgs() << "LV: Invalidate candidate interleaved group due to "
		"first group member potentially pointer-wrapping.\n");
		releaseGroup(Group);
		continue;
		}
		Instruction *LastMember = Group->getMember(Group->getFactor() - 1);
		if (LastMember) {
		Value *LastMemberPtr = getLoadStorePointerOperand(LastMember);
		if (!getPtrStride(PSE, LastMemberPtr, TheLoop, Strides, /Assume=/false,
		/ShouldCheckWrap=/true)) {
		LLVM_DEBUG(
		dbgs() << "LV: Invalidate candidate interleaved group due to "
		"last group member potentially pointer-wrapping.\n");
		releaseGroup(Group);
		}
		} else {
		// Case 3: A non-reversed interleaved load group with gaps: We need
		// to execute at least one scalar epilogue iteration. This will ensure
		// we don't speculatively access memory out-of-bounds. We only need
		// to look for a member at index factor - 1, since every group must have
		// a member at index zero.
		if (Group->isReverse()) {
		LLVM_DEBUG(
		dbgs() << "LV: Invalidate candidate interleaved group due to "
		"a reverse access with gaps.\n");
		releaseGroup(Group);
		continue;
		}
		LLVM_DEBUG(
		dbgs() << "LV: Interleaved group requires epilogue iteration.\n");
		RequiresScalarEpilogue = true;
		}
		}
		}

lib/Transforms/Vectorize/LoopVectorize.cpp

This file is larger than 256 KB, so syntax highlighting is disabled by default.

Show First 20 Lines • Show All 165 Lines • ▼ Show 20 Lines	static cl::opt<bool> MaximizeBandwidth(
"vectorizer-maximize-bandwidth", cl::init(false), cl::Hidden,		"vectorizer-maximize-bandwidth", cl::init(false), cl::Hidden,
cl::desc("Maximize bandwidth when selecting vectorization factor which "		cl::desc("Maximize bandwidth when selecting vectorization factor which "
"will be determined by the smallest type in loop."));		"will be determined by the smallest type in loop."));

static cl::opt<bool> EnableInterleavedMemAccesses(		static cl::opt<bool> EnableInterleavedMemAccesses(
"enable-interleaved-mem-accesses", cl::init(false), cl::Hidden,		"enable-interleaved-mem-accesses", cl::init(false), cl::Hidden,
cl::desc("Enable vectorization on interleaved memory accesses in a loop"));		cl::desc("Enable vectorization on interleaved memory accesses in a loop"));

/// Maximum factor for an interleaved memory access.
static cl::opt<unsigned> MaxInterleaveGroupFactor(
"max-interleave-group-factor", cl::Hidden,
cl::desc("Maximum factor for an interleaved access group (default = 8)"),
cl::init(8));

/// We don't interleave loops with a known constant trip count below this		/// We don't interleave loops with a known constant trip count below this
/// number.		/// number.
static const unsigned TinyTripCountInterleaveThreshold = 128;		static const unsigned TinyTripCountInterleaveThreshold = 128;

static cl::opt<unsigned> ForceTargetNumScalarRegs(		static cl::opt<unsigned> ForceTargetNumScalarRegs(
"force-target-num-scalar-regs", cl::init(0), cl::Hidden,		"force-target-num-scalar-regs", cl::init(0), cl::Hidden,
cl::desc("A flag that overrides the target's number of scalar registers."));		cl::desc("A flag that overrides the target's number of scalar registers."));

▲ Show 20 Lines • Show All 72 Lines • ▼ Show 20 Lines
/// If the incoming type is void, we return void. If the VF is 1, we return		/// If the incoming type is void, we return void. If the VF is 1, we return
/// the scalar type.		/// the scalar type.
static Type ToVectorTy(Type Scalar, unsigned VF) {		static Type ToVectorTy(Type Scalar, unsigned VF) {
if (Scalar->isVoidTy() \|\| VF == 1)		if (Scalar->isVoidTy() \|\| VF == 1)
return Scalar;		return Scalar;
return VectorType::get(Scalar, VF);		return VectorType::get(Scalar, VF);
}		}

// FIXME: The following helper functions have multiple implementations
// in the project. They can be effectively organized in a common Load/Store
// utilities unit.

/// A helper function that returns the type of loaded or stored value.		/// A helper function that returns the type of loaded or stored value.
static Type getMemInstValueType(Value I) {		static Type getMemInstValueType(Value I) {
assert((isa<LoadInst>(I) \|\| isa<StoreInst>(I)) &&		assert((isa<LoadInst>(I) \|\| isa<StoreInst>(I)) &&
"Expected Load or Store instruction");		"Expected Load or Store instruction");
if (auto *LI = dyn_cast<LoadInst>(I))		if (auto *LI = dyn_cast<LoadInst>(I))
return LI->getType();		return LI->getType();
return cast<StoreInst>(I)->getValueOperand()->getType();		return cast<StoreInst>(I)->getValueOperand()->getType();
}		}

/// A helper function that returns the alignment of load or store instruction.
static unsigned getMemInstAlignment(Value *I) {
assert((isa<LoadInst>(I) \|\| isa<StoreInst>(I)) &&
"Expected Load or Store instruction");
if (auto *LI = dyn_cast<LoadInst>(I))
return LI->getAlignment();
return cast<StoreInst>(I)->getAlignment();
}

/// A helper function that returns the address space of the pointer operand of
/// load or store instruction.
static unsigned getMemInstAddressSpace(Value *I) {
assert((isa<LoadInst>(I) \|\| isa<StoreInst>(I)) &&
"Expected Load or Store instruction");
if (auto *LI = dyn_cast<LoadInst>(I))
return LI->getPointerAddressSpace();
return cast<StoreInst>(I)->getPointerAddressSpace();
}

/// A helper function that returns true if the given type is irregular. The		/// A helper function that returns true if the given type is irregular. The
/// type is irregular if its allocated size doesn't equal the store size of an		/// type is irregular if its allocated size doesn't equal the store size of an
/// element of the corresponding vector type at the given vectorization factor.		/// element of the corresponding vector type at the given vectorization factor.
static bool hasIrregularType(Type *Ty, const DataLayout &DL, unsigned VF) {		static bool hasIrregularType(Type *Ty, const DataLayout &DL, unsigned VF) {
// Determine if an array of VF elements of type Ty is "bitcast compatible"		// Determine if an array of VF elements of type Ty is "bitcast compatible"
// with a <VF x Ty> vector.		// with a <VF x Ty> vector.
if (VF > 1) {		if (VF > 1) {
auto *VectorTy = VectorType::get(Ty, VF);		auto *VectorTy = VectorType::get(Ty, VF);
▲ Show 20 Lines • Show All 486 Lines • ▼ Show 20 Lines
void InnerLoopVectorizer::addMetadata(ArrayRef<Value *> To,		void InnerLoopVectorizer::addMetadata(ArrayRef<Value *> To,
Instruction *From) {		Instruction *From) {
for (Value *V : To) {		for (Value *V : To) {
if (Instruction *I = dyn_cast<Instruction>(V))		if (Instruction *I = dyn_cast<Instruction>(V))
addMetadata(I, From);		addMetadata(I, From);
}		}
}		}

namespace llvm {

/// The group of interleaved loads/stores sharing the same stride and
/// close to each other.
///
/// Each member in this group has an index starting from 0, and the largest
/// index should be less than interleaved factor, which is equal to the absolute
/// value of the access's stride.
///
/// E.g. An interleaved load group of factor 4:
/// for (unsigned i = 0; i < 1024; i+=4) {
/// a = A[i]; // Member of index 0
/// b = A[i+1]; // Member of index 1
/// d = A[i+3]; // Member of index 3
/// ...
/// }
///
/// An interleaved store group of factor 4:
/// for (unsigned i = 0; i < 1024; i+=4) {
/// ...
/// A[i] = a; // Member of index 0
/// A[i+1] = b; // Member of index 1
/// A[i+2] = c; // Member of index 2
/// A[i+3] = d; // Member of index 3
/// }
///
/// Note: the interleaved load group could have gaps (missing members), but
/// the interleaved store group doesn't allow gaps.
class InterleaveGroup {
public:
InterleaveGroup(Instruction *Instr, int Stride, unsigned Align)
: Align(Align), InsertPos(Instr) {
assert(Align && "The alignment should be non-zero");

Factor = std::abs(Stride);
assert(Factor > 1 && "Invalid interleave factor");

Reverse = Stride < 0;
Members[0] = Instr;
}

bool isReverse() const { return Reverse; }
unsigned getFactor() const { return Factor; }
unsigned getAlignment() const { return Align; }
unsigned getNumMembers() const { return Members.size(); }

/// Try to insert a new member \p Instr with index \p Index and
/// alignment \p NewAlign. The index is related to the leader and it could be
/// negative if it is the new leader.
///
/// \returns false if the instruction doesn't belong to the group.
bool insertMember(Instruction *Instr, int Index, unsigned NewAlign) {
assert(NewAlign && "The new member's alignment should be non-zero");

int Key = Index + SmallestKey;

// Skip if there is already a member with the same index.
if (Members.count(Key))
return false;

if (Key > LargestKey) {
// The largest index is always less than the interleave factor.
if (Index >= static_cast<int>(Factor))
return false;

LargestKey = Key;
} else if (Key < SmallestKey) {
// The largest index is always less than the interleave factor.
if (LargestKey - Key >= static_cast<int>(Factor))
return false;

SmallestKey = Key;
}

// It's always safe to select the minimum alignment.
Align = std::min(Align, NewAlign);
Members[Key] = Instr;
return true;
}

/// Get the member with the given index \p Index
///
/// \returns nullptr if contains no such member.
Instruction *getMember(unsigned Index) const {
int Key = SmallestKey + Index;
if (!Members.count(Key))
return nullptr;

return Members.find(Key)->second;
}

/// Get the index for the given member. Unlike the key in the member
/// map, the index starts from 0.
unsigned getIndex(Instruction *Instr) const {
for (auto I : Members)
if (I.second == Instr)
return I.first - SmallestKey;

llvm_unreachable("InterleaveGroup contains no such member");
}

Instruction *getInsertPos() const { return InsertPos; }
void setInsertPos(Instruction *Inst) { InsertPos = Inst; }

/// Add metadata (e.g. alias info) from the instructions in this group to \p
/// NewInst.
///
/// FIXME: this function currently does not add noalias metadata a'la
/// addNewMedata. To do that we need to compute the intersection of the
/// noalias info from all members.
void addMetadata(Instruction *NewInst) const {
SmallVector<Value *, 4> VL;
std::transform(Members.begin(), Members.end(), std::back_inserter(VL),
[](std::pair<int, Instruction *> p) { return p.second; });
propagateMetadata(NewInst, VL);
}

private:
unsigned Factor; // Interleave Factor.
bool Reverse;
unsigned Align;
DenseMap<int, Instruction *> Members;
int SmallestKey = 0;
int LargestKey = 0;

// To avoid breaking dependences, vectorized instructions of an interleave
// group should be inserted at either the first load or the last store in
// program order.
//
// E.g. %even = load i32 // Insert Position
// %add = add i32 %even // Use of %even
// %odd = load i32
//
// store i32 %even
// %odd = add i32 // Def of %odd
// store i32 %odd // Insert Position
Instruction *InsertPos;
};
} // end namespace llvm

namespace {

/// Drive the analysis of interleaved memory accesses in the loop.
///
/// Use this class to analyze interleaved accesses only when we can vectorize
/// a loop. Otherwise it's meaningless to do analysis as the vectorization
/// on interleaved accesses is unsafe.
///
/// The analysis collects interleave groups and records the relationships
/// between the member and the group in a map.
class InterleavedAccessInfo {
public:
InterleavedAccessInfo(PredicatedScalarEvolution &PSE, Loop *L,
DominatorTree DT, LoopInfo LI,
const LoopAccessInfo *LAI)
: PSE(PSE), TheLoop(L), DT(DT), LI(LI), LAI(LAI) {}

~InterleavedAccessInfo() {
SmallPtrSet<InterleaveGroup *, 4> DelSet;
// Avoid releasing a pointer twice.
for (auto &I : InterleaveGroupMap)
DelSet.insert(I.second);
for (auto *Ptr : DelSet)
delete Ptr;
}

/// Analyze the interleaved accesses and collect them in interleave
/// groups. Substitute symbolic strides using \p Strides.
void analyzeInterleaving();

/// Check if \p Instr belongs to any interleave group.
bool isInterleaved(Instruction *Instr) const {
return InterleaveGroupMap.count(Instr);
}

/// Get the interleave group that \p Instr belongs to.
///
/// \returns nullptr if doesn't have such group.
InterleaveGroup getInterleaveGroup(Instruction Instr) const {
if (InterleaveGroupMap.count(Instr))
return InterleaveGroupMap.find(Instr)->second;
return nullptr;
}

/// Returns true if an interleaved group that may access memory
/// out-of-bounds requires a scalar epilogue iteration for correctness.
bool requiresScalarEpilogue() const { return RequiresScalarEpilogue; }

private:
/// A wrapper around ScalarEvolution, used to add runtime SCEV checks.
/// Simplifies SCEV expressions in the context of existing SCEV assumptions.
/// The interleaved access analysis can also add new predicates (for example
/// by versioning strides of pointers).
PredicatedScalarEvolution &PSE;

Loop *TheLoop;
DominatorTree *DT;
LoopInfo *LI;
const LoopAccessInfo *LAI;

/// True if the loop may contain non-reversed interleaved groups with
/// out-of-bounds accesses. We ensure we don't speculatively access memory
/// out-of-bounds by executing at least one scalar epilogue iteration.
bool RequiresScalarEpilogue = false;

/// Holds the relationships between the members and the interleave group.
DenseMap<Instruction , InterleaveGroup > InterleaveGroupMap;

/// Holds dependences among the memory accesses in the loop. It maps a source
/// access to a set of dependent sink accesses.
DenseMap<Instruction , SmallPtrSet<Instruction , 2>> Dependences;

/// The descriptor for a strided memory access.
struct StrideDescriptor {
StrideDescriptor() = default;
StrideDescriptor(int64_t Stride, const SCEV *Scev, uint64_t Size,
unsigned Align)
: Stride(Stride), Scev(Scev), Size(Size), Align(Align) {}

// The access's stride. It is negative for a reverse access.
int64_t Stride = 0;

// The scalar expression of this access.
const SCEV *Scev = nullptr;

// The size of the memory object.
uint64_t Size = 0;

// The alignment of this access.
unsigned Align = 0;
};

/// A type for holding instructions and their stride descriptors.
using StrideEntry = std::pair<Instruction *, StrideDescriptor>;

/// Create a new interleave group with the given instruction \p Instr,
/// stride \p Stride and alignment \p Align.
///
/// \returns the newly created interleave group.
InterleaveGroup createInterleaveGroup(Instruction Instr, int Stride,
unsigned Align) {
assert(!InterleaveGroupMap.count(Instr) &&
"Already in an interleaved access group");
InterleaveGroupMap[Instr] = new InterleaveGroup(Instr, Stride, Align);
return InterleaveGroupMap[Instr];
}

/// Release the group and remove all the relationships.
void releaseGroup(InterleaveGroup *Group) {
for (unsigned i = 0; i < Group->getFactor(); i++)
if (Instruction *Member = Group->getMember(i))
InterleaveGroupMap.erase(Member);

delete Group;
}

/// Collect all the accesses with a constant stride in program order.
void collectConstStrideAccesses(
MapVector<Instruction *, StrideDescriptor> &AccessStrideInfo,
const ValueToValueMap &Strides);

/// Returns true if \p Stride is allowed in an interleaved group.
static bool isStrided(int Stride) {
unsigned Factor = std::abs(Stride);
return Factor >= 2 && Factor <= MaxInterleaveGroupFactor;
}

/// Returns true if \p BB is a predicated block.
bool isPredicated(BasicBlock *BB) const {
return LoopAccessInfo::blockNeedsPredication(BB, TheLoop, DT);
}

/// Returns true if LoopAccessInfo can be used for dependence queries.
bool areDependencesValid() const {
return LAI && LAI->getDepChecker().getDependences();
}

/// Returns true if memory accesses \p A and \p B can be reordered, if
/// necessary, when constructing interleaved groups.
///
/// \p A must precede \p B in program order. We return false if reordering is
/// not necessary or is prevented because \p A and \p B may be dependent.
bool canReorderMemAccessesForInterleavedGroups(StrideEntry *A,
StrideEntry *B) const {
// Code motion for interleaved accesses can potentially hoist strided loads
// and sink strided stores. The code below checks the legality of the
// following two conditions:
//
// 1. Potentially moving a strided load (B) before any store (A) that
// precedes B, or
//
// 2. Potentially moving a strided store (A) after any load or store (B)
// that A precedes.
//
// It's legal to reorder A and B if we know there isn't a dependence from A
// to B. Note that this determination is conservative since some
// dependences could potentially be reordered safely.

// A is potentially the source of a dependence.
auto *Src = A->first;
auto SrcDes = A->second;

// B is potentially the sink of a dependence.
auto *Sink = B->first;
auto SinkDes = B->second;

// Code motion for interleaved accesses can't violate WAR dependences.
// Thus, reordering is legal if the source isn't a write.
if (!Src->mayWriteToMemory())
return true;

// At least one of the accesses must be strided.
if (!isStrided(SrcDes.Stride) && !isStrided(SinkDes.Stride))
return true;

// If dependence information is not available from LoopAccessInfo,
// conservatively assume the instructions can't be reordered.
if (!areDependencesValid())
return false;

// If we know there is a dependence from source to sink, assume the
// instructions can't be reordered. Otherwise, reordering is legal.
return !Dependences.count(Src) \|\| !Dependences.lookup(Src).count(Sink);
}

/// Collect the dependences from LoopAccessInfo.
///
/// We process the dependences once during the interleaved access analysis to
/// enable constant-time dependence queries.
void collectDependences() {
if (!areDependencesValid())
return;
auto *Deps = LAI->getDepChecker().getDependences();
for (auto Dep : *Deps)
Dependences[Dep.getSource(LAI)].insert(Dep.getDestination(LAI));
}
};

} // end anonymous namespace

static void emitMissedWarning(Function F, Loop L,		static void emitMissedWarning(Function F, Loop L,
const LoopVectorizeHints &LH,		const LoopVectorizeHints &LH,
OptimizationRemarkEmitter *ORE) {		OptimizationRemarkEmitter *ORE) {
LH.emitRemarkWithHints();		LH.emitRemarkWithHints();

if (LH.getForce() == LoopVectorizeHints::FK_Enabled) {		if (LH.getForce() == LoopVectorizeHints::FK_Enabled) {
if (LH.getWidth() != 1)		if (LH.getWidth() != 1)
ORE->emit(DiagnosticInfoOptimizationFailure(		ORE->emit(DiagnosticInfoOptimizationFailure(
▲ Show 20 Lines • Show All 3,415 Lines • ▼ Show 20 Lines	for (auto &Induction : *Legal->getInductionVars()) {
LLVM_DEBUG(dbgs() << "LV: Found uniform instruction: " << *Ind << "\n");		LLVM_DEBUG(dbgs() << "LV: Found uniform instruction: " << *Ind << "\n");
LLVM_DEBUG(dbgs() << "LV: Found uniform instruction: " << *IndUpdate		LLVM_DEBUG(dbgs() << "LV: Found uniform instruction: " << *IndUpdate
<< "\n");		<< "\n");
}		}

Uniforms[VF].insert(Worklist.begin(), Worklist.end());		Uniforms[VF].insert(Worklist.begin(), Worklist.end());
}		}

void InterleavedAccessInfo::collectConstStrideAccesses(
MapVector<Instruction *, StrideDescriptor> &AccessStrideInfo,
const ValueToValueMap &Strides) {
auto &DL = TheLoop->getHeader()->getModule()->getDataLayout();

// Since it's desired that the load/store instructions be maintained in
// "program order" for the interleaved access analysis, we have to visit the
// blocks in the loop in reverse postorder (i.e., in a topological order).
// Such an ordering will ensure that any load/store that may be executed
// before a second load/store will precede the second load/store in
// AccessStrideInfo.
LoopBlocksDFS DFS(TheLoop);
DFS.perform(LI);
for (BasicBlock *BB : make_range(DFS.beginRPO(), DFS.endRPO()))
for (auto &I : *BB) {
auto *LI = dyn_cast<LoadInst>(&I);
auto *SI = dyn_cast<StoreInst>(&I);
if (!LI && !SI)
continue;

Value *Ptr = getLoadStorePointerOperand(&I);
// We don't check wrapping here because we don't know yet if Ptr will be
// part of a full group or a group with gaps. Checking wrapping for all
// pointers (even those that end up in groups with no gaps) will be overly
// conservative. For full groups, wrapping should be ok since if we would
// wrap around the address space we would do a memory access at nullptr
// even without the transformation. The wrapping checks are therefore
// deferred until after we've formed the interleaved groups.
int64_t Stride = getPtrStride(PSE, Ptr, TheLoop, Strides,
/Assume=/true, /ShouldCheckWrap=/false);

const SCEV *Scev = replaceSymbolicStrideSCEV(PSE, Strides, Ptr);
PointerType *PtrTy = dyn_cast<PointerType>(Ptr->getType());
uint64_t Size = DL.getTypeAllocSize(PtrTy->getElementType());

// An alignment of 0 means target ABI alignment.
unsigned Align = getMemInstAlignment(&I);
if (!Align)
Align = DL.getABITypeAlignment(PtrTy->getElementType());

AccessStrideInfo[&I] = StrideDescriptor(Stride, Scev, Size, Align);
}
}

// Analyze interleaved accesses and collect them into interleaved load and
// store groups.
//
// When generating code for an interleaved load group, we effectively hoist all
// loads in the group to the location of the first load in program order. When
// generating code for an interleaved store group, we sink all stores to the
// location of the last store. This code motion can change the order of load
// and store instructions and may break dependences.
//
// The code generation strategy mentioned above ensures that we won't violate
// any write-after-read (WAR) dependences.
//
// E.g., for the WAR dependence: a = A[i]; // (1)
// A[i] = b; // (2)
//
// The store group of (2) is always inserted at or below (2), and the load
// group of (1) is always inserted at or above (1). Thus, the instructions will
// never be reordered. All other dependences are checked to ensure the
// correctness of the instruction reordering.
//
// The algorithm visits all memory accesses in the loop in bottom-up program
// order. Program order is established by traversing the blocks in the loop in
// reverse postorder when collecting the accesses.
//
// We visit the memory accesses in bottom-up order because it can simplify the
// construction of store groups in the presence of write-after-write (WAW)
// dependences.
//
// E.g., for the WAW dependence: A[i] = a; // (1)
// A[i] = b; // (2)
// A[i + 1] = c; // (3)
//
// We will first create a store group with (3) and (2). (1) can't be added to
// this group because it and (2) are dependent. However, (1) can be grouped
// with other accesses that may precede it in program order. Note that a
// bottom-up order does not imply that WAW dependences should not be checked.
void InterleavedAccessInfo::analyzeInterleaving() {
LLVM_DEBUG(dbgs() << "LV: Analyzing interleaved accesses...\n");
const ValueToValueMap &Strides = LAI->getSymbolicStrides();

// Holds all accesses with a constant stride.
MapVector<Instruction *, StrideDescriptor> AccessStrideInfo;
collectConstStrideAccesses(AccessStrideInfo, Strides);

if (AccessStrideInfo.empty())
return;

// Collect the dependences in the loop.
collectDependences();

// Holds all interleaved store groups temporarily.
SmallSetVector<InterleaveGroup *, 4> StoreGroups;
// Holds all interleaved load groups temporarily.
SmallSetVector<InterleaveGroup *, 4> LoadGroups;

// Search in bottom-up program order for pairs of accesses (A and B) that can
// form interleaved load or store groups. In the algorithm below, access A
// precedes access B in program order. We initialize a group for B in the
// outer loop of the algorithm, and then in the inner loop, we attempt to
// insert each A into B's group if:
//
// 1. A and B have the same stride,
// 2. A and B have the same memory object size, and
// 3. A belongs in B's group according to its distance from B.
//
// Special care is taken to ensure group formation will not break any
// dependences.
for (auto BI = AccessStrideInfo.rbegin(), E = AccessStrideInfo.rend();
BI != E; ++BI) {
Instruction *B = BI->first;
StrideDescriptor DesB = BI->second;

// Initialize a group for B if it has an allowable stride. Even if we don't
// create a group for B, we continue with the bottom-up algorithm to ensure
// we don't break any of B's dependences.
InterleaveGroup *Group = nullptr;
if (isStrided(DesB.Stride)) {
Group = getInterleaveGroup(B);
if (!Group) {
LLVM_DEBUG(dbgs() << "LV: Creating an interleave group with:" << *B
<< '\n');
Group = createInterleaveGroup(B, DesB.Stride, DesB.Align);
}
if (B->mayWriteToMemory())
StoreGroups.insert(Group);
else
LoadGroups.insert(Group);
}

for (auto AI = std::next(BI); AI != E; ++AI) {
Instruction *A = AI->first;
StrideDescriptor DesA = AI->second;

// Our code motion strategy implies that we can't have dependences
// between accesses in an interleaved group and other accesses located
// between the first and last member of the group. Note that this also
// means that a group can't have more than one member at a given offset.
// The accesses in a group can have dependences with other accesses, but
// we must ensure we don't extend the boundaries of the group such that
// we encompass those dependent accesses.
//
// For example, assume we have the sequence of accesses shown below in a
// stride-2 loop:
//
// (1, 2) is a group \| A[i] = a; // (1)
// \| A[i-1] = b; // (2) \|
// A[i-3] = c; // (3)
// A[i] = d; // (4) \| (2, 4) is not a group
//
// Because accesses (2) and (3) are dependent, we can group (2) with (1)
// but not with (4). If we did, the dependent access (3) would be within
// the boundaries of the (2, 4) group.
if (!canReorderMemAccessesForInterleavedGroups(&AI, &BI)) {
// If a dependence exists and A is already in a group, we know that A
// must be a store since A precedes B and WAR dependences are allowed.
// Thus, A would be sunk below B. We release A's group to prevent this
// illegal code motion. A will then be free to form another group with
// instructions that precede it.
if (isInterleaved(A)) {
InterleaveGroup *StoreGroup = getInterleaveGroup(A);
StoreGroups.remove(StoreGroup);
releaseGroup(StoreGroup);
}

// If a dependence exists and A is not already in a group (or it was
// and we just released it), B might be hoisted above A (if B is a
// load) or another store might be sunk below A (if B is a store). In
// either case, we can't add additional instructions to B's group. B
// will only form a group with instructions that it precedes.
break;
}

// At this point, we've checked for illegal code motion. If either A or B
// isn't strided, there's nothing left to do.
if (!isStrided(DesA.Stride) \|\| !isStrided(DesB.Stride))
continue;

// Ignore A if it's already in a group or isn't the same kind of memory
// operation as B.
// Note that mayReadFromMemory() isn't mutually exclusive to mayWriteToMemory
// in the case of atomic loads. We shouldn't see those here, canVectorizeMemory()
// should have returned false - except for the case we asked for optimization
// remarks.
if (isInterleaved(A) \|\| (A->mayReadFromMemory() != B->mayReadFromMemory())
\|\| (A->mayWriteToMemory() != B->mayWriteToMemory()))
continue;

// Check rules 1 and 2. Ignore A if its stride or size is different from
// that of B.
if (DesA.Stride != DesB.Stride \|\| DesA.Size != DesB.Size)
continue;

// Ignore A if the memory object of A and B don't belong to the same
// address space
if (getMemInstAddressSpace(A) != getMemInstAddressSpace(B))
continue;

// Calculate the distance from A to B.
const SCEVConstant *DistToB = dyn_cast<SCEVConstant>(
PSE.getSE()->getMinusSCEV(DesA.Scev, DesB.Scev));
if (!DistToB)
continue;
int64_t DistanceToB = DistToB->getAPInt().getSExtValue();

// Check rule 3. Ignore A if its distance to B is not a multiple of the
// size.
if (DistanceToB % static_cast<int64_t>(DesB.Size))
continue;

// Ignore A if either A or B is in a predicated block. Although we
// currently prevent group formation for predicated accesses, we may be
// able to relax this limitation in the future once we handle more
// complicated blocks.
if (isPredicated(A->getParent()) \|\| isPredicated(B->getParent()))
continue;

// The index of A is the index of B plus A's distance to B in multiples
// of the size.
int IndexA =
Group->getIndex(B) + DistanceToB / static_cast<int64_t>(DesB.Size);

// Try to insert A into B's group.
if (Group->insertMember(A, IndexA, DesA.Align)) {
LLVM_DEBUG(dbgs() << "LV: Inserted:" << *A << '\n'
<< " into the interleave group with" << *B
<< '\n');
InterleaveGroupMap[A] = Group;

// Set the first load in program order as the insert position.
if (A->mayReadFromMemory())
Group->setInsertPos(A);
}
} // Iteration over A accesses.
} // Iteration over B accesses.

// Remove interleaved store groups with gaps.
for (InterleaveGroup *Group : StoreGroups)
if (Group->getNumMembers() != Group->getFactor()) {
LLVM_DEBUG(
dbgs() << "LV: Invalidate candidate interleaved store group due "
"to gaps.\n");
releaseGroup(Group);
}
// Remove interleaved groups with gaps (currently only loads) whose memory
// accesses may wrap around. We have to revisit the getPtrStride analysis,
// this time with ShouldCheckWrap=true, since collectConstStrideAccesses does
// not check wrapping (see documentation there).
// FORNOW we use Assume=false;
// TODO: Change to Assume=true but making sure we don't exceed the threshold
// of runtime SCEV assumptions checks (thereby potentially failing to
// vectorize altogether).
// Additional optional optimizations:
// TODO: If we are peeling the loop and we know that the first pointer doesn't
// wrap then we can deduce that all pointers in the group don't wrap.
// This means that we can forcefully peel the loop in order to only have to
// check the first pointer for no-wrap. When we'll change to use Assume=true
// we'll only need at most one runtime check per interleaved group.
for (InterleaveGroup *Group : LoadGroups) {
// Case 1: A full group. Can Skip the checks; For full groups, if the wide
// load would wrap around the address space we would do a memory access at
// nullptr even without the transformation.
if (Group->getNumMembers() == Group->getFactor())
continue;

// Case 2: If first and last members of the group don't wrap this implies
// that all the pointers in the group don't wrap.
// So we check only group member 0 (which is always guaranteed to exist),
// and group member Factor - 1; If the latter doesn't exist we rely on
// peeling (if it is a non-reveresed accsess -- see Case 3).
Value *FirstMemberPtr = getLoadStorePointerOperand(Group->getMember(0));
if (!getPtrStride(PSE, FirstMemberPtr, TheLoop, Strides, /Assume=/false,
/ShouldCheckWrap=/true)) {
LLVM_DEBUG(
dbgs() << "LV: Invalidate candidate interleaved group due to "
"first group member potentially pointer-wrapping.\n");
releaseGroup(Group);
continue;
}
Instruction *LastMember = Group->getMember(Group->getFactor() - 1);
if (LastMember) {
Value *LastMemberPtr = getLoadStorePointerOperand(LastMember);
if (!getPtrStride(PSE, LastMemberPtr, TheLoop, Strides, /Assume=/false,
/ShouldCheckWrap=/true)) {
LLVM_DEBUG(
dbgs() << "LV: Invalidate candidate interleaved group due to "
"last group member potentially pointer-wrapping.\n");
releaseGroup(Group);
}
} else {
// Case 3: A non-reversed interleaved load group with gaps: We need
// to execute at least one scalar epilogue iteration. This will ensure
// we don't speculatively access memory out-of-bounds. We only need
// to look for a member at index factor - 1, since every group must have
// a member at index zero.
if (Group->isReverse()) {
LLVM_DEBUG(
dbgs() << "LV: Invalidate candidate interleaved group due to "
"a reverse access with gaps.\n");
releaseGroup(Group);
continue;
}
LLVM_DEBUG(
dbgs() << "LV: Interleaved group requires epilogue iteration.\n");
RequiresScalarEpilogue = true;
}
}
}

Optional<unsigned> LoopVectorizationCostModel::computeMaxVF(bool OptForSize) {		Optional<unsigned> LoopVectorizationCostModel::computeMaxVF(bool OptForSize) {
if (Legal->getRuntimePointerChecking()->Need && TTI.hasBranchDivergence()) {		if (Legal->getRuntimePointerChecking()->Need && TTI.hasBranchDivergence()) {
// TODO: It may by useful to do since it's still likely to be dynamically		// TODO: It may by useful to do since it's still likely to be dynamically
// uniform if the target can skip.		// uniform if the target can skip.
LLVM_DEBUG(		LLVM_DEBUG(
dbgs() << "LV: Not inserting runtime ptr check for divergent target");		dbgs() << "LV: Not inserting runtime ptr check for divergent target");

ORE->emit(		ORE->emit(
▲ Show 20 Lines • Show All 2,774 Lines • Show Last 20 Lines

This is an archive of the discontinued LLVM Phabricator instance.

[LV] Move InterleaveGroup and InterleavedAccessInfo to VectorUtils.h (NFC)
ClosedPublic

Details

Diff Detail

Event Timeline

Revision Contents

Diff 156301

include/llvm/Analysis/VectorUtils.h

include/llvm/IR/Instructions.h

lib/Analysis/VectorUtils.cpp

lib/Transforms/Vectorize/LoopVectorize.cpp

This is an archive of the discontinued LLVM Phabricator instance.

[LV] Move InterleaveGroup and InterleavedAccessInfo to VectorUtils.h (NFC)ClosedPublic

Details

Diff Detail

Event Timeline

Revision Contents

Diff 156301

include/llvm/Analysis/VectorUtils.h

include/llvm/IR/Instructions.h

lib/Analysis/VectorUtils.cpp

lib/Transforms/Vectorize/LoopVectorize.cpp

[LV] Move InterleaveGroup and InterleavedAccessInfo to VectorUtils.h (NFC)
ClosedPublic