Differential D114087 Diff 391342 llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

Changeset View

Standalone View

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

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

Show First 20 Lines • Show All 5,916 Lines • ▼ Show 20 Lines

namespace {		namespace {
/// Merges shuffle masks and emits final shuffle instruction, if required.		/// Merges shuffle masks and emits final shuffle instruction, if required.
class ShuffleInstructionBuilder {		class ShuffleInstructionBuilder {
IRBuilderBase &Builder;		IRBuilderBase &Builder;
const unsigned VF = 0;		const unsigned VF = 0;
bool IsFinalized = false;		bool IsFinalized = false;
SmallVector<int, 4> Mask;		SmallVector<int, 4> Mask;
		/// Holds all of the instructions that we gathered.
		SetVector<Instruction *> &GatherShuffleSeq;
		/// A list of blocks that we are going to CSE.
		SetVector<BasicBlock *> &CSEBlocks;

public:		public:
ShuffleInstructionBuilder(IRBuilderBase &Builder, unsigned VF)		ShuffleInstructionBuilder(IRBuilderBase &Builder, unsigned VF,
: Builder(Builder), VF(VF) {}		SetVector<Instruction *> &GatherShuffleSeq,
		SetVector<BasicBlock *> &CSEBlocks)
		: Builder(Builder), VF(VF), GatherShuffleSeq(GatherShuffleSeq),
		CSEBlocks(CSEBlocks) {}

/// Adds a mask, inverting it before applying.		/// Adds a mask, inverting it before applying.
void addInversedMask(ArrayRef<unsigned> SubMask) {		void addInversedMask(ArrayRef<unsigned> SubMask) {
if (SubMask.empty())		if (SubMask.empty())
return;		return;
SmallVector<int, 4> NewMask;		SmallVector<int, 4> NewMask;
inversePermutation(SubMask, NewMask);		inversePermutation(SubMask, NewMask);
addMask(NewMask);		addMask(NewMask);
Show All 13 Lines	Value finalize(Value V) {
if (VF == ValueVF && Mask.empty())		if (VF == ValueVF && Mask.empty())
return V;		return V;
SmallVector<int, 4> NormalizedMask(VF, UndefMaskElem);		SmallVector<int, 4> NormalizedMask(VF, UndefMaskElem);
std::iota(NormalizedMask.begin(), NormalizedMask.end(), 0);		std::iota(NormalizedMask.begin(), NormalizedMask.end(), 0);
addMask(NormalizedMask);		addMask(NormalizedMask);

if (VF == ValueVF && ShuffleVectorInst::isIdentityMask(Mask))		if (VF == ValueVF && ShuffleVectorInst::isIdentityMask(Mask))
return V;		return V;
return Builder.CreateShuffleVector(V, Mask, "shuffle");		Value *Vec = Builder.CreateShuffleVector(V, Mask, "shuffle");
		if (auto *I = dyn_cast<Instruction>(Vec)) {
		GatherShuffleSeq.insert(I);
		CSEBlocks.insert(I->getParent());
		}
		return Vec;
}		}

~ShuffleInstructionBuilder() {		~ShuffleInstructionBuilder() {
assert((IsFinalized \|\| Mask.empty()) &&		assert((IsFinalized \|\| Mask.empty()) &&
"Shuffle construction must be finalized.");		"Shuffle construction must be finalized.");
}		}
};		};
} // namespace		} // namespace
▲ Show 20 Lines • Show All 41 Lines • ▼ Show 20 Lines	if (TreeEntry *E = getTreeEntry(S.OpValue))
} else {		} else {
assert(VF < cast<FixedVectorType>(V->getType())->getNumElements() &&		assert(VF < cast<FixedVectorType>(V->getType())->getNumElements() &&
"Expected vectorization factor less "		"Expected vectorization factor less "
"than original vector size.");		"than original vector size.");
SmallVector<int> UniformMask(VF, 0);		SmallVector<int> UniformMask(VF, 0);
std::iota(UniformMask.begin(), UniformMask.end(), 0);		std::iota(UniformMask.begin(), UniformMask.end(), 0);
V = Builder.CreateShuffleVector(V, UniformMask, "shrink.shuffle");		V = Builder.CreateShuffleVector(V, UniformMask, "shrink.shuffle");
}		}
		if (auto *I = dyn_cast<Instruction>(V)) {
		GatherShuffleSeq.insert(I);
		CSEBlocks.insert(I->getParent());
		}
}		}
return V;		return V;
}		}
}		}

// Check that every instruction appears once in this bundle.		// Check that every instruction appears once in this bundle.
SmallVector<int> ReuseShuffleIndicies;		SmallVector<int> ReuseShuffleIndicies;
SmallVector<Value *> UniqueValues;		SmallVector<Value *> UniqueValues;
Show All 31 Lines	if (UniqueVals == 1 && UniqueValues.size() == 1) {
UniqueValues.clear();		UniqueValues.clear();
UniqueValues.append(VL.begin(), std::next(VL.begin(), NumValues));		UniqueValues.append(VL.begin(), std::next(VL.begin(), NumValues));
}		}
UniqueValues.append(VF - UniqueValues.size(),		UniqueValues.append(VF - UniqueValues.size(),
PoisonValue::get(VL[0]->getType()));		PoisonValue::get(VL[0]->getType()));
VL = UniqueValues;		VL = UniqueValues;
}		}

ShuffleInstructionBuilder ShuffleBuilder(Builder, VF);		ShuffleInstructionBuilder ShuffleBuilder(Builder, VF, GatherShuffleSeq,
		CSEBlocks);
Value *Vec = gather(VL);		Value *Vec = gather(VL);
if (!ReuseShuffleIndicies.empty()) {		if (!ReuseShuffleIndicies.empty()) {
ShuffleBuilder.addMask(ReuseShuffleIndicies);		ShuffleBuilder.addMask(ReuseShuffleIndicies);
Vec = ShuffleBuilder.finalize(Vec);		Vec = ShuffleBuilder.finalize(Vec);
if (auto *I = dyn_cast<Instruction>(Vec)) {
GatherShuffleSeq.insert(I);
CSEBlocks.insert(I->getParent());
}
}		}
return Vec;		return Vec;
}		}

Value BoUpSLP::vectorizeTree(TreeEntry E) {		Value BoUpSLP::vectorizeTree(TreeEntry E) {
IRBuilder<>::InsertPointGuard Guard(Builder);		IRBuilder<>::InsertPointGuard Guard(Builder);

if (E->VectorizedValue) {		if (E->VectorizedValue) {
LLVM_DEBUG(dbgs() << "SLP: Diamond merged for " << *E->Scalars[0] << ".\n");		LLVM_DEBUG(dbgs() << "SLP: Diamond merged for " << *E->Scalars[0] << ".\n");
return E->VectorizedValue;		return E->VectorizedValue;
}		}

bool NeedToShuffleReuses = !E->ReuseShuffleIndices.empty();		bool NeedToShuffleReuses = !E->ReuseShuffleIndices.empty();
unsigned VF = E->getVectorFactor();		unsigned VF = E->getVectorFactor();
ShuffleInstructionBuilder ShuffleBuilder(Builder, VF);		ShuffleInstructionBuilder ShuffleBuilder(Builder, VF, GatherShuffleSeq,
		CSEBlocks);
if (E->State == TreeEntry::NeedToGather) {		if (E->State == TreeEntry::NeedToGather) {
if (E->getMainOp())		if (E->getMainOp())
setInsertPointAfterBundle(E);		setInsertPointAfterBundle(E);
Value *Vec;		Value *Vec;
SmallVector<int> Mask;		SmallVector<int> Mask;
SmallVector<const TreeEntry *> Entries;		SmallVector<const TreeEntry *> Entries;
Optional<TargetTransformInfo::ShuffleKind> Shuffle =		Optional<TargetTransformInfo::ShuffleKind> Shuffle =
isGatherShuffledEntry(E, Mask, Entries);		isGatherShuffledEntry(E, Mask, Entries);
if (Shuffle.hasValue()) {		if (Shuffle.hasValue()) {
assert((Entries.size() == 1 \|\| Entries.size() == 2) &&		assert((Entries.size() == 1 \|\| Entries.size() == 2) &&
"Expected shuffle of 1 or 2 entries.");		"Expected shuffle of 1 or 2 entries.");
Vec = Builder.CreateShuffleVector(Entries.front()->VectorizedValue,		Vec = Builder.CreateShuffleVector(Entries.front()->VectorizedValue,
Entries.back()->VectorizedValue, Mask);		Entries.back()->VectorizedValue, Mask);
		if (auto *I = dyn_cast<Instruction>(Vec)) {
		GatherShuffleSeq.insert(I);
		CSEBlocks.insert(I->getParent());
		}
} else {		} else {
Vec = gather(E->Scalars);		Vec = gather(E->Scalars);
}		}
if (NeedToShuffleReuses) {		if (NeedToShuffleReuses) {
ShuffleBuilder.addMask(E->ReuseShuffleIndices);		ShuffleBuilder.addMask(E->ReuseShuffleIndices);
Vec = ShuffleBuilder.finalize(Vec);		Vec = ShuffleBuilder.finalize(Vec);
if (auto *I = dyn_cast<Instruction>(Vec)) {
GatherShuffleSeq.insert(I);
CSEBlocks.insert(I->getParent());
}
}		}
E->VectorizedValue = Vec;		E->VectorizedValue = Vec;
return Vec;		return Vec;
}		}

assert((E->State == TreeEntry::Vectorize \|\|		assert((E->State == TreeEntry::Vectorize \|\|
E->State == TreeEntry::ScatterVectorize) &&		E->State == TreeEntry::ScatterVectorize) &&
"Unhandled state");		"Unhandled state");
▲ Show 20 Lines • Show All 100 Lines • ▼ Show 20 Lines	case Instruction::InsertElement: {
for (unsigned I = 0; I < NumScalars; ++I) {		for (unsigned I = 0; I < NumScalars; ++I) {
Value *Scalar = E->Scalars[PrevMask[I]];		Value *Scalar = E->Scalars[PrevMask[I]];
Optional<int> InsertIdx = getInsertIndex(Scalar, 0);		Optional<int> InsertIdx = getInsertIndex(Scalar, 0);
if (!InsertIdx \|\| *InsertIdx == UndefMaskElem)		if (!InsertIdx \|\| *InsertIdx == UndefMaskElem)
continue;		continue;
IsIdentity &= *InsertIdx - Offset == I;		IsIdentity &= *InsertIdx - Offset == I;
Mask[*InsertIdx - Offset] = I;		Mask[*InsertIdx - Offset] = I;
}		}
if (!IsIdentity \|\| NumElts != NumScalars)		if (!IsIdentity \|\| NumElts != NumScalars) {
V = Builder.CreateShuffleVector(V, Mask);		V = Builder.CreateShuffleVector(V, Mask);
		if (auto *I = dyn_cast<Instruction>(V)) {
		GatherShuffleSeq.insert(I);
		CSEBlocks.insert(I->getParent());
		}
		}

if ((!IsIdentity \|\| Offset != 0 \|\|		if ((!IsIdentity \|\| Offset != 0 \|\|
!isUndefVector(FirstInsert->getOperand(0))) &&		!isUndefVector(FirstInsert->getOperand(0))) &&
NumElts != NumScalars) {		NumElts != NumScalars) {
SmallVector<int> InsertMask(NumElts);		SmallVector<int> InsertMask(NumElts);
std::iota(InsertMask.begin(), InsertMask.end(), 0);		std::iota(InsertMask.begin(), InsertMask.end(), 0);
for (unsigned I = 0; I < NumElts; I++) {		for (unsigned I = 0; I < NumElts; I++) {
if (Mask[I] != UndefMaskElem)		if (Mask[I] != UndefMaskElem)
InsertMask[Offset + I] = NumElts + I;		InsertMask[Offset + I] = NumElts + I;
}		}

V = Builder.CreateShuffleVector(		V = Builder.CreateShuffleVector(
FirstInsert->getOperand(0), V, InsertMask,		FirstInsert->getOperand(0), V, InsertMask,
cast<Instruction>(E->Scalars.back())->getName());		cast<Instruction>(E->Scalars.back())->getName());
		if (auto *I = dyn_cast<Instruction>(V)) {
		GatherShuffleSeq.insert(I);
		CSEBlocks.insert(I->getParent());
		}
}		}

++NumVectorInstructions;		++NumVectorInstructions;
E->VectorizedValue = V;		E->VectorizedValue = V;
return V;		return V;
}		}
case Instruction::ZExt:		case Instruction::ZExt:
case Instruction::SExt:		case Instruction::SExt:
▲ Show 20 Lines • Show All 366 Lines • ▼ Show 20 Lines	case Instruction::ShuffleVector: {
return I->getOpcode() == E->getAltOpcode();		return I->getOpcode() == E->getAltOpcode();
},		},
Mask, &OpScalars, &AltScalars);		Mask, &OpScalars, &AltScalars);

propagateIRFlags(V0, OpScalars);		propagateIRFlags(V0, OpScalars);
propagateIRFlags(V1, AltScalars);		propagateIRFlags(V1, AltScalars);

Value *V = Builder.CreateShuffleVector(V0, V1, Mask);		Value *V = Builder.CreateShuffleVector(V0, V1, Mask);
if (Instruction *I = dyn_cast<Instruction>(V))		if (auto *I = dyn_cast<Instruction>(V)) {
V = propagateMetadata(I, E->Scalars);		V = propagateMetadata(I, E->Scalars);
		GatherShuffleSeq.insert(I);
		RKSimonUnsubmitted Not Done Reply Inline Actions Do these 2 if() have to be kept separate? RKSimon: Do these 2 if() have to be kept separate?
		ABataevAuthorUnsubmitted Done Reply Inline Actions Will merge them ABataev: Will merge them
		CSEBlocks.insert(I->getParent());
		}
V = ShuffleBuilder.finalize(V);		V = ShuffleBuilder.finalize(V);

E->VectorizedValue = V;		E->VectorizedValue = V;
++NumVectorInstructions;		++NumVectorInstructions;

return V;		return V;
}		}
default:		default:
▲ Show 20 Lines • Show All 224 Lines • ▼ Show 20 Lines	void BoUpSLP::optimizeGatherSequence() {
// Sort blocks by domination. This ensures we visit a block after all blocks		// Sort blocks by domination. This ensures we visit a block after all blocks
// dominating it are visited.		// dominating it are visited.
llvm::sort(CSEWorkList, [](const DomTreeNode A, const DomTreeNode B) {		llvm::sort(CSEWorkList, [](const DomTreeNode A, const DomTreeNode B) {
assert((A == B) == (A->getDFSNumIn() == B->getDFSNumIn()) &&		assert((A == B) == (A->getDFSNumIn() == B->getDFSNumIn()) &&
"Different nodes should have different DFS numbers");		"Different nodes should have different DFS numbers");
return A->getDFSNumIn() < B->getDFSNumIn();		return A->getDFSNumIn() < B->getDFSNumIn();
});		});

// Perform O(N^2) search over the gather sequences and merge identical		// Less defined shuffles can be replaced by the more defined copies.
		// Between two shuffles one is less defined if it has the same vector operands
		vporpoUnsubmitted Not Done Reply Inline Actions nit: Also related to the comment above, perhaps it is worth splitting this lambda in two: IsIdentical() and LessDefined(), wdyt ? vporpo: nit: Also related to the comment above, perhaps it is worth splitting this lambda in two…
		ABataevAuthorUnsubmitted Done Reply Inline Actions Not sure that it will result in better code. ABataev: Not sure that it will result in better code.
		// and its mask indeces are the same as in the first one or undefs. E.g.
		// shuffle %0, poison, <0, 0, 0, undef> is less defined than shuffle %0,
		// poison, <0, 0, 0, 0>.
		auto &&IsIdenticalOrLessDefined = [this](Instruction I1, Instruction I2,
		SmallVectorImpl<int> &NewMask) {
		if (I1->getType() != I2->getType())
		return false;
		auto *SI1 = dyn_cast<ShuffleVectorInst>(I1);
		auto *SI2 = dyn_cast<ShuffleVectorInst>(I2);
		if (!SI1 \|\| !SI2)
		return I1->isIdenticalTo(I2);
		if (SI1->isIdenticalTo(SI2))
		return true;
		RKSimonUnsubmitted Not Done Reply Inline Actions Add a comment about keep track of the terminating (trailing?) undefmaskelems RKSimon: Add a comment about keep track of the terminating (trailing?) undefmaskelems
		ABataevAuthorUnsubmitted Done Reply Inline Actions Will do, thanks! ABataev: Will do, thanks!
		for (int I = 0, E = SI1->getNumOperands(); I < E; ++I)
		if (SI1->getOperand(I) != SI2->getOperand(I))
		return false;
		// Check if the second instruction is more defined than the first one.
		NewMask.assign(SI2->getShuffleMask().begin(), SI2->getShuffleMask().end());
		ArrayRef<int> SM1 = SI1->getShuffleMask();
		// Count trailing undefs in the mask to check the final number of used
		// registers.
		RKSimonUnsubmitted Not Done Reply Inline Actions I don't understand - why do you reset LastUndefsCnt here? RKSimon: I don't understand - why do you reset LastUndefsCnt here?
		ABataevAuthorUnsubmitted Done Reply Inline Actions `LastUndefsCnt` is the number of terminating undefmaskelems, that's why I reset it each time we ran into non-undef mask elem. ABataev: `LastUndefsCnt` is the number of terminating undefmaskelems, that's why I reset it each time we…
		RKSimonUnsubmitted Not Done Reply Inline Actions Got it - thanks. RKSimon: Got it - thanks.
		unsigned LastUndefsCnt = 0;
		for (int I = 0, E = NewMask.size(); I < E; ++I) {
		if (SM1[I] == UndefMaskElem)
		++LastUndefsCnt;
		else
		LastUndefsCnt = 0;
		if (NewMask[I] != UndefMaskElem && SM1[I] != UndefMaskElem &&
		NewMask[I] != SM1[I])
		return false;
		if (NewMask[I] == UndefMaskElem)
		NewMask[I] = SM1[I];
		}
		// Check if the last undefs actually change the final number of used vector
		// registers.
		return SM1.size() - LastUndefsCnt > 1 &&
		TTI->getNumberOfParts(SI1->getType()) ==
		TTI->getNumberOfParts(
		FixedVectorType::get(SI1->getType()->getElementType(),
		SM1.size() - LastUndefsCnt));
		};
		// Perform O(N^2) search over the gather/shuffle sequences and merge identical
		vporpoUnsubmitted Not Done Reply Inline Actions nit: Could you briefly explain in the comment what you mean by "less defined" by showing for example two masks where one is less defined than the other (like the ones from the lit tests below). vporpo: nit: Could you briefly explain in the comment what you mean by "less defined" by showing for…
		ABataevAuthorUnsubmitted Done Reply Inline Actions For example, if we have 2 shuffles: shuffle %0, <0, 0, 0, undef> and shuffle %0, <0, 0, 0, 0> the first shuffle is less defined than the second and can be replaced by the second one. ABataev: For example, if we have 2 shuffles: ``` shuffle %0, <0, 0, 0, undef> ``` and ``` shuffle %0…
		vporpoUnsubmitted Not Done Reply Inline Actions Could you add this explanation to the comment? vporpo: Could you add this explanation to the comment?
		ABataevAuthorUnsubmitted Done Reply Inline Actions Sure, will do. ABataev: Sure, will do.
// instructions. TODO: We can further optimize this scan if we split the		// instructions. TODO: We can further optimize this scan if we split the
// instructions into different buckets based on the insert lane.		// instructions into different buckets based on the insert lane.
SmallVector<Instruction *, 16> Visited;		SmallVector<Instruction *, 16> Visited;
for (auto I = CSEWorkList.begin(), E = CSEWorkList.end(); I != E; ++I) {		for (auto I = CSEWorkList.begin(), E = CSEWorkList.end(); I != E; ++I) {
assert(*I &&		assert(*I &&
(I == CSEWorkList.begin() \|\| !DT->dominates(I, std::prev(I))) &&		(I == CSEWorkList.begin() \|\| !DT->dominates(I, std::prev(I))) &&
"Worklist not sorted properly!");		"Worklist not sorted properly!");
BasicBlock BB = (I)->getBlock();		BasicBlock BB = (I)->getBlock();
// For all instructions in blocks containing gather sequences:		// For all instructions in blocks containing gather sequences:
for (Instruction &In : llvm::make_early_inc_range(*BB)) {		for (Instruction &In : llvm::make_early_inc_range(*BB)) {
if (isDeleted(&In))		if (isDeleted(&In))
continue;		continue;
if (!isa<InsertElementInst>(&In) && !isa<ExtractElementInst>(&In) &&		if (!isa<InsertElementInst>(&In) && !isa<ExtractElementInst>(&In) &&
!isa<ShuffleVectorInst>(&In) && !GatherShuffleSeq.contains(&In))		!isa<ShuffleVectorInst>(&In) && !GatherShuffleSeq.contains(&In))
continue;		continue;

// Check if we can replace this instruction with any of the		// Check if we can replace this instruction with any of the
// visited instructions.		// visited instructions.
bool Replaced = false;		bool Replaced = false;
for (Instruction *v : Visited) {		for (Instruction *&V : Visited) {
if (In.isIdenticalTo(v) &&		SmallVector<int> NewMask;
DT->dominates(v->getParent(), In.getParent())) {		if (IsIdenticalOrLessDefined(&In, V, NewMask) &&
In.replaceAllUsesWith(v);		DT->dominates(V->getParent(), In.getParent())) {
		In.replaceAllUsesWith(V);
eraseInstruction(&In);		eraseInstruction(&In);
		if (auto *SI = dyn_cast<ShuffleVectorInst>(V))
		if (!NewMask.empty())
		SI->setShuffleMask(NewMask);
		Replaced = true;
		break;
		}
		if (isa<ShuffleVectorInst>(In) && isa<ShuffleVectorInst>(V) &&
		GatherShuffleSeq.contains(V) &&
		IsIdenticalOrLessDefined(V, &In, NewMask) &&
		DT->dominates(In.getParent(), V->getParent())) {
		In.moveAfter(V);
		V->replaceAllUsesWith(&In);
		eraseInstruction(V);
		if (auto *SI = dyn_cast<ShuffleVectorInst>(&In))
		RKSimonUnsubmitted Not Done Reply Inline Actions Can't we remove this dyn_cast thanks to the isa<> test above? RKSimon: Can't we remove this dyn_cast thanks to the isa<> test above?
		ABataevAuthorUnsubmitted Done Reply Inline Actions No, we need `SI` here of `ShuffleVectorInst` type to be able to replace its shuffle mask. ABataev: No, we need `SI` here of `ShuffleVectorInst` type to be able to replace its shuffle mask.
		if (!NewMask.empty())
		SI->setShuffleMask(NewMask);
		V = &In;
Replaced = true;		Replaced = true;
break;		break;
}		}
}		}
if (!Replaced) {		if (!Replaced) {
assert(!is_contained(Visited, &In));		assert(!is_contained(Visited, &In));
Visited.push_back(&In);		Visited.push_back(&In);
}		}
▲ Show 20 Lines • Show All 2,995 Lines • Show Last 20 Lines