106f32e7eSjoerg //===----------- VectorUtils.cpp - Vectorizer utility functions -----------===//
206f32e7eSjoerg //
306f32e7eSjoerg // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
406f32e7eSjoerg // See https://llvm.org/LICENSE.txt for license information.
506f32e7eSjoerg // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
606f32e7eSjoerg //
706f32e7eSjoerg //===----------------------------------------------------------------------===//
806f32e7eSjoerg //
906f32e7eSjoerg // This file defines vectorizer utilities.
1006f32e7eSjoerg //
1106f32e7eSjoerg //===----------------------------------------------------------------------===//
1206f32e7eSjoerg
1306f32e7eSjoerg #include "llvm/Analysis/VectorUtils.h"
1406f32e7eSjoerg #include "llvm/ADT/EquivalenceClasses.h"
1506f32e7eSjoerg #include "llvm/Analysis/DemandedBits.h"
1606f32e7eSjoerg #include "llvm/Analysis/LoopInfo.h"
1706f32e7eSjoerg #include "llvm/Analysis/LoopIterator.h"
1806f32e7eSjoerg #include "llvm/Analysis/ScalarEvolution.h"
1906f32e7eSjoerg #include "llvm/Analysis/ScalarEvolutionExpressions.h"
2006f32e7eSjoerg #include "llvm/Analysis/TargetTransformInfo.h"
2106f32e7eSjoerg #include "llvm/Analysis/ValueTracking.h"
2206f32e7eSjoerg #include "llvm/IR/Constants.h"
2306f32e7eSjoerg #include "llvm/IR/GetElementPtrTypeIterator.h"
2406f32e7eSjoerg #include "llvm/IR/IRBuilder.h"
2506f32e7eSjoerg #include "llvm/IR/PatternMatch.h"
2606f32e7eSjoerg #include "llvm/IR/Value.h"
27*da58b97aSjoerg #include "llvm/Support/CommandLine.h"
2806f32e7eSjoerg
2906f32e7eSjoerg #define DEBUG_TYPE "vectorutils"
3006f32e7eSjoerg
3106f32e7eSjoerg using namespace llvm;
3206f32e7eSjoerg using namespace llvm::PatternMatch;
3306f32e7eSjoerg
3406f32e7eSjoerg /// Maximum factor for an interleaved memory access.
3506f32e7eSjoerg static cl::opt<unsigned> MaxInterleaveGroupFactor(
3606f32e7eSjoerg "max-interleave-group-factor", cl::Hidden,
3706f32e7eSjoerg cl::desc("Maximum factor for an interleaved access group (default = 8)"),
3806f32e7eSjoerg cl::init(8));
3906f32e7eSjoerg
4006f32e7eSjoerg /// Return true if all of the intrinsic's arguments and return type are scalars
4106f32e7eSjoerg /// for the scalar form of the intrinsic, and vectors for the vector form of the
4206f32e7eSjoerg /// intrinsic (except operands that are marked as always being scalar by
4306f32e7eSjoerg /// hasVectorInstrinsicScalarOpd).
isTriviallyVectorizable(Intrinsic::ID ID)4406f32e7eSjoerg bool llvm::isTriviallyVectorizable(Intrinsic::ID ID) {
4506f32e7eSjoerg switch (ID) {
46*da58b97aSjoerg case Intrinsic::abs: // Begin integer bit-manipulation.
47*da58b97aSjoerg case Intrinsic::bswap:
4806f32e7eSjoerg case Intrinsic::bitreverse:
4906f32e7eSjoerg case Intrinsic::ctpop:
5006f32e7eSjoerg case Intrinsic::ctlz:
5106f32e7eSjoerg case Intrinsic::cttz:
5206f32e7eSjoerg case Intrinsic::fshl:
5306f32e7eSjoerg case Intrinsic::fshr:
54*da58b97aSjoerg case Intrinsic::smax:
55*da58b97aSjoerg case Intrinsic::smin:
56*da58b97aSjoerg case Intrinsic::umax:
57*da58b97aSjoerg case Intrinsic::umin:
5806f32e7eSjoerg case Intrinsic::sadd_sat:
5906f32e7eSjoerg case Intrinsic::ssub_sat:
6006f32e7eSjoerg case Intrinsic::uadd_sat:
6106f32e7eSjoerg case Intrinsic::usub_sat:
6206f32e7eSjoerg case Intrinsic::smul_fix:
6306f32e7eSjoerg case Intrinsic::smul_fix_sat:
6406f32e7eSjoerg case Intrinsic::umul_fix:
6506f32e7eSjoerg case Intrinsic::umul_fix_sat:
6606f32e7eSjoerg case Intrinsic::sqrt: // Begin floating-point.
6706f32e7eSjoerg case Intrinsic::sin:
6806f32e7eSjoerg case Intrinsic::cos:
6906f32e7eSjoerg case Intrinsic::exp:
7006f32e7eSjoerg case Intrinsic::exp2:
7106f32e7eSjoerg case Intrinsic::log:
7206f32e7eSjoerg case Intrinsic::log10:
7306f32e7eSjoerg case Intrinsic::log2:
7406f32e7eSjoerg case Intrinsic::fabs:
7506f32e7eSjoerg case Intrinsic::minnum:
7606f32e7eSjoerg case Intrinsic::maxnum:
7706f32e7eSjoerg case Intrinsic::minimum:
7806f32e7eSjoerg case Intrinsic::maximum:
7906f32e7eSjoerg case Intrinsic::copysign:
8006f32e7eSjoerg case Intrinsic::floor:
8106f32e7eSjoerg case Intrinsic::ceil:
8206f32e7eSjoerg case Intrinsic::trunc:
8306f32e7eSjoerg case Intrinsic::rint:
8406f32e7eSjoerg case Intrinsic::nearbyint:
8506f32e7eSjoerg case Intrinsic::round:
86*da58b97aSjoerg case Intrinsic::roundeven:
8706f32e7eSjoerg case Intrinsic::pow:
8806f32e7eSjoerg case Intrinsic::fma:
8906f32e7eSjoerg case Intrinsic::fmuladd:
9006f32e7eSjoerg case Intrinsic::powi:
9106f32e7eSjoerg case Intrinsic::canonicalize:
9206f32e7eSjoerg return true;
9306f32e7eSjoerg default:
9406f32e7eSjoerg return false;
9506f32e7eSjoerg }
9606f32e7eSjoerg }
9706f32e7eSjoerg
9806f32e7eSjoerg /// Identifies if the vector form of the intrinsic has a scalar operand.
hasVectorInstrinsicScalarOpd(Intrinsic::ID ID,unsigned ScalarOpdIdx)9906f32e7eSjoerg bool llvm::hasVectorInstrinsicScalarOpd(Intrinsic::ID ID,
10006f32e7eSjoerg unsigned ScalarOpdIdx) {
10106f32e7eSjoerg switch (ID) {
102*da58b97aSjoerg case Intrinsic::abs:
10306f32e7eSjoerg case Intrinsic::ctlz:
10406f32e7eSjoerg case Intrinsic::cttz:
10506f32e7eSjoerg case Intrinsic::powi:
10606f32e7eSjoerg return (ScalarOpdIdx == 1);
10706f32e7eSjoerg case Intrinsic::smul_fix:
10806f32e7eSjoerg case Intrinsic::smul_fix_sat:
10906f32e7eSjoerg case Intrinsic::umul_fix:
11006f32e7eSjoerg case Intrinsic::umul_fix_sat:
11106f32e7eSjoerg return (ScalarOpdIdx == 2);
11206f32e7eSjoerg default:
11306f32e7eSjoerg return false;
11406f32e7eSjoerg }
11506f32e7eSjoerg }
11606f32e7eSjoerg
11706f32e7eSjoerg /// Returns intrinsic ID for call.
11806f32e7eSjoerg /// For the input call instruction it finds mapping intrinsic and returns
11906f32e7eSjoerg /// its ID, in case it does not found it return not_intrinsic.
getVectorIntrinsicIDForCall(const CallInst * CI,const TargetLibraryInfo * TLI)12006f32e7eSjoerg Intrinsic::ID llvm::getVectorIntrinsicIDForCall(const CallInst *CI,
12106f32e7eSjoerg const TargetLibraryInfo *TLI) {
122*da58b97aSjoerg Intrinsic::ID ID = getIntrinsicForCallSite(*CI, TLI);
12306f32e7eSjoerg if (ID == Intrinsic::not_intrinsic)
12406f32e7eSjoerg return Intrinsic::not_intrinsic;
12506f32e7eSjoerg
12606f32e7eSjoerg if (isTriviallyVectorizable(ID) || ID == Intrinsic::lifetime_start ||
12706f32e7eSjoerg ID == Intrinsic::lifetime_end || ID == Intrinsic::assume ||
128*da58b97aSjoerg ID == Intrinsic::experimental_noalias_scope_decl ||
129*da58b97aSjoerg ID == Intrinsic::sideeffect || ID == Intrinsic::pseudoprobe)
13006f32e7eSjoerg return ID;
13106f32e7eSjoerg return Intrinsic::not_intrinsic;
13206f32e7eSjoerg }
13306f32e7eSjoerg
13406f32e7eSjoerg /// Find the operand of the GEP that should be checked for consecutive
13506f32e7eSjoerg /// stores. This ignores trailing indices that have no effect on the final
13606f32e7eSjoerg /// pointer.
getGEPInductionOperand(const GetElementPtrInst * Gep)13706f32e7eSjoerg unsigned llvm::getGEPInductionOperand(const GetElementPtrInst *Gep) {
13806f32e7eSjoerg const DataLayout &DL = Gep->getModule()->getDataLayout();
13906f32e7eSjoerg unsigned LastOperand = Gep->getNumOperands() - 1;
140*da58b97aSjoerg TypeSize GEPAllocSize = DL.getTypeAllocSize(Gep->getResultElementType());
14106f32e7eSjoerg
14206f32e7eSjoerg // Walk backwards and try to peel off zeros.
14306f32e7eSjoerg while (LastOperand > 1 && match(Gep->getOperand(LastOperand), m_Zero())) {
14406f32e7eSjoerg // Find the type we're currently indexing into.
14506f32e7eSjoerg gep_type_iterator GEPTI = gep_type_begin(Gep);
14606f32e7eSjoerg std::advance(GEPTI, LastOperand - 2);
14706f32e7eSjoerg
14806f32e7eSjoerg // If it's a type with the same allocation size as the result of the GEP we
14906f32e7eSjoerg // can peel off the zero index.
15006f32e7eSjoerg if (DL.getTypeAllocSize(GEPTI.getIndexedType()) != GEPAllocSize)
15106f32e7eSjoerg break;
15206f32e7eSjoerg --LastOperand;
15306f32e7eSjoerg }
15406f32e7eSjoerg
15506f32e7eSjoerg return LastOperand;
15606f32e7eSjoerg }
15706f32e7eSjoerg
15806f32e7eSjoerg /// If the argument is a GEP, then returns the operand identified by
15906f32e7eSjoerg /// getGEPInductionOperand. However, if there is some other non-loop-invariant
16006f32e7eSjoerg /// operand, it returns that instead.
stripGetElementPtr(Value * Ptr,ScalarEvolution * SE,Loop * Lp)16106f32e7eSjoerg Value *llvm::stripGetElementPtr(Value *Ptr, ScalarEvolution *SE, Loop *Lp) {
16206f32e7eSjoerg GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Ptr);
16306f32e7eSjoerg if (!GEP)
16406f32e7eSjoerg return Ptr;
16506f32e7eSjoerg
16606f32e7eSjoerg unsigned InductionOperand = getGEPInductionOperand(GEP);
16706f32e7eSjoerg
16806f32e7eSjoerg // Check that all of the gep indices are uniform except for our induction
16906f32e7eSjoerg // operand.
17006f32e7eSjoerg for (unsigned i = 0, e = GEP->getNumOperands(); i != e; ++i)
17106f32e7eSjoerg if (i != InductionOperand &&
17206f32e7eSjoerg !SE->isLoopInvariant(SE->getSCEV(GEP->getOperand(i)), Lp))
17306f32e7eSjoerg return Ptr;
17406f32e7eSjoerg return GEP->getOperand(InductionOperand);
17506f32e7eSjoerg }
17606f32e7eSjoerg
17706f32e7eSjoerg /// If a value has only one user that is a CastInst, return it.
getUniqueCastUse(Value * Ptr,Loop * Lp,Type * Ty)17806f32e7eSjoerg Value *llvm::getUniqueCastUse(Value *Ptr, Loop *Lp, Type *Ty) {
17906f32e7eSjoerg Value *UniqueCast = nullptr;
18006f32e7eSjoerg for (User *U : Ptr->users()) {
18106f32e7eSjoerg CastInst *CI = dyn_cast<CastInst>(U);
18206f32e7eSjoerg if (CI && CI->getType() == Ty) {
18306f32e7eSjoerg if (!UniqueCast)
18406f32e7eSjoerg UniqueCast = CI;
18506f32e7eSjoerg else
18606f32e7eSjoerg return nullptr;
18706f32e7eSjoerg }
18806f32e7eSjoerg }
18906f32e7eSjoerg return UniqueCast;
19006f32e7eSjoerg }
19106f32e7eSjoerg
19206f32e7eSjoerg /// Get the stride of a pointer access in a loop. Looks for symbolic
19306f32e7eSjoerg /// strides "a[i*stride]". Returns the symbolic stride, or null otherwise.
getStrideFromPointer(Value * Ptr,ScalarEvolution * SE,Loop * Lp)19406f32e7eSjoerg Value *llvm::getStrideFromPointer(Value *Ptr, ScalarEvolution *SE, Loop *Lp) {
19506f32e7eSjoerg auto *PtrTy = dyn_cast<PointerType>(Ptr->getType());
19606f32e7eSjoerg if (!PtrTy || PtrTy->isAggregateType())
19706f32e7eSjoerg return nullptr;
19806f32e7eSjoerg
19906f32e7eSjoerg // Try to remove a gep instruction to make the pointer (actually index at this
20006f32e7eSjoerg // point) easier analyzable. If OrigPtr is equal to Ptr we are analyzing the
20106f32e7eSjoerg // pointer, otherwise, we are analyzing the index.
20206f32e7eSjoerg Value *OrigPtr = Ptr;
20306f32e7eSjoerg
20406f32e7eSjoerg // The size of the pointer access.
20506f32e7eSjoerg int64_t PtrAccessSize = 1;
20606f32e7eSjoerg
20706f32e7eSjoerg Ptr = stripGetElementPtr(Ptr, SE, Lp);
20806f32e7eSjoerg const SCEV *V = SE->getSCEV(Ptr);
20906f32e7eSjoerg
21006f32e7eSjoerg if (Ptr != OrigPtr)
21106f32e7eSjoerg // Strip off casts.
212*da58b97aSjoerg while (const SCEVIntegralCastExpr *C = dyn_cast<SCEVIntegralCastExpr>(V))
21306f32e7eSjoerg V = C->getOperand();
21406f32e7eSjoerg
21506f32e7eSjoerg const SCEVAddRecExpr *S = dyn_cast<SCEVAddRecExpr>(V);
21606f32e7eSjoerg if (!S)
21706f32e7eSjoerg return nullptr;
21806f32e7eSjoerg
21906f32e7eSjoerg V = S->getStepRecurrence(*SE);
22006f32e7eSjoerg if (!V)
22106f32e7eSjoerg return nullptr;
22206f32e7eSjoerg
22306f32e7eSjoerg // Strip off the size of access multiplication if we are still analyzing the
22406f32e7eSjoerg // pointer.
22506f32e7eSjoerg if (OrigPtr == Ptr) {
22606f32e7eSjoerg if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(V)) {
22706f32e7eSjoerg if (M->getOperand(0)->getSCEVType() != scConstant)
22806f32e7eSjoerg return nullptr;
22906f32e7eSjoerg
23006f32e7eSjoerg const APInt &APStepVal = cast<SCEVConstant>(M->getOperand(0))->getAPInt();
23106f32e7eSjoerg
23206f32e7eSjoerg // Huge step value - give up.
23306f32e7eSjoerg if (APStepVal.getBitWidth() > 64)
23406f32e7eSjoerg return nullptr;
23506f32e7eSjoerg
23606f32e7eSjoerg int64_t StepVal = APStepVal.getSExtValue();
23706f32e7eSjoerg if (PtrAccessSize != StepVal)
23806f32e7eSjoerg return nullptr;
23906f32e7eSjoerg V = M->getOperand(1);
24006f32e7eSjoerg }
24106f32e7eSjoerg }
24206f32e7eSjoerg
24306f32e7eSjoerg // Strip off casts.
24406f32e7eSjoerg Type *StripedOffRecurrenceCast = nullptr;
245*da58b97aSjoerg if (const SCEVIntegralCastExpr *C = dyn_cast<SCEVIntegralCastExpr>(V)) {
24606f32e7eSjoerg StripedOffRecurrenceCast = C->getType();
24706f32e7eSjoerg V = C->getOperand();
24806f32e7eSjoerg }
24906f32e7eSjoerg
25006f32e7eSjoerg // Look for the loop invariant symbolic value.
25106f32e7eSjoerg const SCEVUnknown *U = dyn_cast<SCEVUnknown>(V);
25206f32e7eSjoerg if (!U)
25306f32e7eSjoerg return nullptr;
25406f32e7eSjoerg
25506f32e7eSjoerg Value *Stride = U->getValue();
25606f32e7eSjoerg if (!Lp->isLoopInvariant(Stride))
25706f32e7eSjoerg return nullptr;
25806f32e7eSjoerg
25906f32e7eSjoerg // If we have stripped off the recurrence cast we have to make sure that we
26006f32e7eSjoerg // return the value that is used in this loop so that we can replace it later.
26106f32e7eSjoerg if (StripedOffRecurrenceCast)
26206f32e7eSjoerg Stride = getUniqueCastUse(Stride, Lp, StripedOffRecurrenceCast);
26306f32e7eSjoerg
26406f32e7eSjoerg return Stride;
26506f32e7eSjoerg }
26606f32e7eSjoerg
26706f32e7eSjoerg /// Given a vector and an element number, see if the scalar value is
26806f32e7eSjoerg /// already around as a register, for example if it were inserted then extracted
26906f32e7eSjoerg /// from the vector.
findScalarElement(Value * V,unsigned EltNo)27006f32e7eSjoerg Value *llvm::findScalarElement(Value *V, unsigned EltNo) {
27106f32e7eSjoerg assert(V->getType()->isVectorTy() && "Not looking at a vector?");
27206f32e7eSjoerg VectorType *VTy = cast<VectorType>(V->getType());
273*da58b97aSjoerg // For fixed-length vector, return undef for out of range access.
274*da58b97aSjoerg if (auto *FVTy = dyn_cast<FixedVectorType>(VTy)) {
275*da58b97aSjoerg unsigned Width = FVTy->getNumElements();
276*da58b97aSjoerg if (EltNo >= Width)
277*da58b97aSjoerg return UndefValue::get(FVTy->getElementType());
278*da58b97aSjoerg }
27906f32e7eSjoerg
28006f32e7eSjoerg if (Constant *C = dyn_cast<Constant>(V))
28106f32e7eSjoerg return C->getAggregateElement(EltNo);
28206f32e7eSjoerg
28306f32e7eSjoerg if (InsertElementInst *III = dyn_cast<InsertElementInst>(V)) {
28406f32e7eSjoerg // If this is an insert to a variable element, we don't know what it is.
28506f32e7eSjoerg if (!isa<ConstantInt>(III->getOperand(2)))
28606f32e7eSjoerg return nullptr;
28706f32e7eSjoerg unsigned IIElt = cast<ConstantInt>(III->getOperand(2))->getZExtValue();
28806f32e7eSjoerg
28906f32e7eSjoerg // If this is an insert to the element we are looking for, return the
29006f32e7eSjoerg // inserted value.
29106f32e7eSjoerg if (EltNo == IIElt)
29206f32e7eSjoerg return III->getOperand(1);
29306f32e7eSjoerg
294*da58b97aSjoerg // Guard against infinite loop on malformed, unreachable IR.
295*da58b97aSjoerg if (III == III->getOperand(0))
296*da58b97aSjoerg return nullptr;
297*da58b97aSjoerg
29806f32e7eSjoerg // Otherwise, the insertelement doesn't modify the value, recurse on its
29906f32e7eSjoerg // vector input.
30006f32e7eSjoerg return findScalarElement(III->getOperand(0), EltNo);
30106f32e7eSjoerg }
30206f32e7eSjoerg
303*da58b97aSjoerg ShuffleVectorInst *SVI = dyn_cast<ShuffleVectorInst>(V);
304*da58b97aSjoerg // Restrict the following transformation to fixed-length vector.
305*da58b97aSjoerg if (SVI && isa<FixedVectorType>(SVI->getType())) {
306*da58b97aSjoerg unsigned LHSWidth =
307*da58b97aSjoerg cast<FixedVectorType>(SVI->getOperand(0)->getType())->getNumElements();
30806f32e7eSjoerg int InEl = SVI->getMaskValue(EltNo);
30906f32e7eSjoerg if (InEl < 0)
31006f32e7eSjoerg return UndefValue::get(VTy->getElementType());
31106f32e7eSjoerg if (InEl < (int)LHSWidth)
31206f32e7eSjoerg return findScalarElement(SVI->getOperand(0), InEl);
31306f32e7eSjoerg return findScalarElement(SVI->getOperand(1), InEl - LHSWidth);
31406f32e7eSjoerg }
31506f32e7eSjoerg
31606f32e7eSjoerg // Extract a value from a vector add operation with a constant zero.
31706f32e7eSjoerg // TODO: Use getBinOpIdentity() to generalize this.
31806f32e7eSjoerg Value *Val; Constant *C;
31906f32e7eSjoerg if (match(V, m_Add(m_Value(Val), m_Constant(C))))
32006f32e7eSjoerg if (Constant *Elt = C->getAggregateElement(EltNo))
32106f32e7eSjoerg if (Elt->isNullValue())
32206f32e7eSjoerg return findScalarElement(Val, EltNo);
32306f32e7eSjoerg
32406f32e7eSjoerg // Otherwise, we don't know.
32506f32e7eSjoerg return nullptr;
32606f32e7eSjoerg }
32706f32e7eSjoerg
getSplatIndex(ArrayRef<int> Mask)328*da58b97aSjoerg int llvm::getSplatIndex(ArrayRef<int> Mask) {
329*da58b97aSjoerg int SplatIndex = -1;
330*da58b97aSjoerg for (int M : Mask) {
331*da58b97aSjoerg // Ignore invalid (undefined) mask elements.
332*da58b97aSjoerg if (M < 0)
333*da58b97aSjoerg continue;
334*da58b97aSjoerg
335*da58b97aSjoerg // There can be only 1 non-negative mask element value if this is a splat.
336*da58b97aSjoerg if (SplatIndex != -1 && SplatIndex != M)
337*da58b97aSjoerg return -1;
338*da58b97aSjoerg
339*da58b97aSjoerg // Initialize the splat index to the 1st non-negative mask element.
340*da58b97aSjoerg SplatIndex = M;
341*da58b97aSjoerg }
342*da58b97aSjoerg assert((SplatIndex == -1 || SplatIndex >= 0) && "Negative index?");
343*da58b97aSjoerg return SplatIndex;
344*da58b97aSjoerg }
345*da58b97aSjoerg
34606f32e7eSjoerg /// Get splat value if the input is a splat vector or return nullptr.
34706f32e7eSjoerg /// This function is not fully general. It checks only 2 cases:
34806f32e7eSjoerg /// the input value is (1) a splat constant vector or (2) a sequence
34906f32e7eSjoerg /// of instructions that broadcasts a scalar at element 0.
getSplatValue(const Value * V)350*da58b97aSjoerg Value *llvm::getSplatValue(const Value *V) {
35106f32e7eSjoerg if (isa<VectorType>(V->getType()))
35206f32e7eSjoerg if (auto *C = dyn_cast<Constant>(V))
35306f32e7eSjoerg return C->getSplatValue();
35406f32e7eSjoerg
35506f32e7eSjoerg // shuf (inselt ?, Splat, 0), ?, <0, undef, 0, ...>
35606f32e7eSjoerg Value *Splat;
357*da58b97aSjoerg if (match(V,
358*da58b97aSjoerg m_Shuffle(m_InsertElt(m_Value(), m_Value(Splat), m_ZeroInt()),
359*da58b97aSjoerg m_Value(), m_ZeroMask())))
36006f32e7eSjoerg return Splat;
36106f32e7eSjoerg
36206f32e7eSjoerg return nullptr;
36306f32e7eSjoerg }
36406f32e7eSjoerg
isSplatValue(const Value * V,int Index,unsigned Depth)365*da58b97aSjoerg bool llvm::isSplatValue(const Value *V, int Index, unsigned Depth) {
366*da58b97aSjoerg assert(Depth <= MaxAnalysisRecursionDepth && "Limit Search Depth");
36706f32e7eSjoerg
36806f32e7eSjoerg if (isa<VectorType>(V->getType())) {
36906f32e7eSjoerg if (isa<UndefValue>(V))
37006f32e7eSjoerg return true;
371*da58b97aSjoerg // FIXME: We can allow undefs, but if Index was specified, we may want to
372*da58b97aSjoerg // check that the constant is defined at that index.
37306f32e7eSjoerg if (auto *C = dyn_cast<Constant>(V))
37406f32e7eSjoerg return C->getSplatValue() != nullptr;
37506f32e7eSjoerg }
37606f32e7eSjoerg
377*da58b97aSjoerg if (auto *Shuf = dyn_cast<ShuffleVectorInst>(V)) {
378*da58b97aSjoerg // FIXME: We can safely allow undefs here. If Index was specified, we will
379*da58b97aSjoerg // check that the mask elt is defined at the required index.
380*da58b97aSjoerg if (!is_splat(Shuf->getShuffleMask()))
381*da58b97aSjoerg return false;
382*da58b97aSjoerg
383*da58b97aSjoerg // Match any index.
384*da58b97aSjoerg if (Index == -1)
385*da58b97aSjoerg return true;
386*da58b97aSjoerg
387*da58b97aSjoerg // Match a specific element. The mask should be defined at and match the
388*da58b97aSjoerg // specified index.
389*da58b97aSjoerg return Shuf->getMaskValue(Index) == Index;
390*da58b97aSjoerg }
39106f32e7eSjoerg
39206f32e7eSjoerg // The remaining tests are all recursive, so bail out if we hit the limit.
393*da58b97aSjoerg if (Depth++ == MaxAnalysisRecursionDepth)
39406f32e7eSjoerg return false;
39506f32e7eSjoerg
39606f32e7eSjoerg // If both operands of a binop are splats, the result is a splat.
39706f32e7eSjoerg Value *X, *Y, *Z;
39806f32e7eSjoerg if (match(V, m_BinOp(m_Value(X), m_Value(Y))))
399*da58b97aSjoerg return isSplatValue(X, Index, Depth) && isSplatValue(Y, Index, Depth);
40006f32e7eSjoerg
40106f32e7eSjoerg // If all operands of a select are splats, the result is a splat.
40206f32e7eSjoerg if (match(V, m_Select(m_Value(X), m_Value(Y), m_Value(Z))))
403*da58b97aSjoerg return isSplatValue(X, Index, Depth) && isSplatValue(Y, Index, Depth) &&
404*da58b97aSjoerg isSplatValue(Z, Index, Depth);
40506f32e7eSjoerg
40606f32e7eSjoerg // TODO: Add support for unary ops (fneg), casts, intrinsics (overflow ops).
40706f32e7eSjoerg
40806f32e7eSjoerg return false;
40906f32e7eSjoerg }
41006f32e7eSjoerg
narrowShuffleMaskElts(int Scale,ArrayRef<int> Mask,SmallVectorImpl<int> & ScaledMask)411*da58b97aSjoerg void llvm::narrowShuffleMaskElts(int Scale, ArrayRef<int> Mask,
412*da58b97aSjoerg SmallVectorImpl<int> &ScaledMask) {
413*da58b97aSjoerg assert(Scale > 0 && "Unexpected scaling factor");
414*da58b97aSjoerg
415*da58b97aSjoerg // Fast-path: if no scaling, then it is just a copy.
416*da58b97aSjoerg if (Scale == 1) {
417*da58b97aSjoerg ScaledMask.assign(Mask.begin(), Mask.end());
418*da58b97aSjoerg return;
419*da58b97aSjoerg }
420*da58b97aSjoerg
421*da58b97aSjoerg ScaledMask.clear();
422*da58b97aSjoerg for (int MaskElt : Mask) {
423*da58b97aSjoerg if (MaskElt >= 0) {
424*da58b97aSjoerg assert(((uint64_t)Scale * MaskElt + (Scale - 1)) <= INT32_MAX &&
425*da58b97aSjoerg "Overflowed 32-bits");
426*da58b97aSjoerg }
427*da58b97aSjoerg for (int SliceElt = 0; SliceElt != Scale; ++SliceElt)
428*da58b97aSjoerg ScaledMask.push_back(MaskElt < 0 ? MaskElt : Scale * MaskElt + SliceElt);
429*da58b97aSjoerg }
430*da58b97aSjoerg }
431*da58b97aSjoerg
widenShuffleMaskElts(int Scale,ArrayRef<int> Mask,SmallVectorImpl<int> & ScaledMask)432*da58b97aSjoerg bool llvm::widenShuffleMaskElts(int Scale, ArrayRef<int> Mask,
433*da58b97aSjoerg SmallVectorImpl<int> &ScaledMask) {
434*da58b97aSjoerg assert(Scale > 0 && "Unexpected scaling factor");
435*da58b97aSjoerg
436*da58b97aSjoerg // Fast-path: if no scaling, then it is just a copy.
437*da58b97aSjoerg if (Scale == 1) {
438*da58b97aSjoerg ScaledMask.assign(Mask.begin(), Mask.end());
439*da58b97aSjoerg return true;
440*da58b97aSjoerg }
441*da58b97aSjoerg
442*da58b97aSjoerg // We must map the original elements down evenly to a type with less elements.
443*da58b97aSjoerg int NumElts = Mask.size();
444*da58b97aSjoerg if (NumElts % Scale != 0)
445*da58b97aSjoerg return false;
446*da58b97aSjoerg
447*da58b97aSjoerg ScaledMask.clear();
448*da58b97aSjoerg ScaledMask.reserve(NumElts / Scale);
449*da58b97aSjoerg
450*da58b97aSjoerg // Step through the input mask by splitting into Scale-sized slices.
451*da58b97aSjoerg do {
452*da58b97aSjoerg ArrayRef<int> MaskSlice = Mask.take_front(Scale);
453*da58b97aSjoerg assert((int)MaskSlice.size() == Scale && "Expected Scale-sized slice.");
454*da58b97aSjoerg
455*da58b97aSjoerg // The first element of the slice determines how we evaluate this slice.
456*da58b97aSjoerg int SliceFront = MaskSlice.front();
457*da58b97aSjoerg if (SliceFront < 0) {
458*da58b97aSjoerg // Negative values (undef or other "sentinel" values) must be equal across
459*da58b97aSjoerg // the entire slice.
460*da58b97aSjoerg if (!is_splat(MaskSlice))
461*da58b97aSjoerg return false;
462*da58b97aSjoerg ScaledMask.push_back(SliceFront);
463*da58b97aSjoerg } else {
464*da58b97aSjoerg // A positive mask element must be cleanly divisible.
465*da58b97aSjoerg if (SliceFront % Scale != 0)
466*da58b97aSjoerg return false;
467*da58b97aSjoerg // Elements of the slice must be consecutive.
468*da58b97aSjoerg for (int i = 1; i < Scale; ++i)
469*da58b97aSjoerg if (MaskSlice[i] != SliceFront + i)
470*da58b97aSjoerg return false;
471*da58b97aSjoerg ScaledMask.push_back(SliceFront / Scale);
472*da58b97aSjoerg }
473*da58b97aSjoerg Mask = Mask.drop_front(Scale);
474*da58b97aSjoerg } while (!Mask.empty());
475*da58b97aSjoerg
476*da58b97aSjoerg assert((int)ScaledMask.size() * Scale == NumElts && "Unexpected scaled mask");
477*da58b97aSjoerg
478*da58b97aSjoerg // All elements of the original mask can be scaled down to map to the elements
479*da58b97aSjoerg // of a mask with wider elements.
480*da58b97aSjoerg return true;
481*da58b97aSjoerg }
482*da58b97aSjoerg
48306f32e7eSjoerg MapVector<Instruction *, uint64_t>
computeMinimumValueSizes(ArrayRef<BasicBlock * > Blocks,DemandedBits & DB,const TargetTransformInfo * TTI)48406f32e7eSjoerg llvm::computeMinimumValueSizes(ArrayRef<BasicBlock *> Blocks, DemandedBits &DB,
48506f32e7eSjoerg const TargetTransformInfo *TTI) {
48606f32e7eSjoerg
48706f32e7eSjoerg // DemandedBits will give us every value's live-out bits. But we want
48806f32e7eSjoerg // to ensure no extra casts would need to be inserted, so every DAG
48906f32e7eSjoerg // of connected values must have the same minimum bitwidth.
49006f32e7eSjoerg EquivalenceClasses<Value *> ECs;
49106f32e7eSjoerg SmallVector<Value *, 16> Worklist;
49206f32e7eSjoerg SmallPtrSet<Value *, 4> Roots;
49306f32e7eSjoerg SmallPtrSet<Value *, 16> Visited;
49406f32e7eSjoerg DenseMap<Value *, uint64_t> DBits;
49506f32e7eSjoerg SmallPtrSet<Instruction *, 4> InstructionSet;
49606f32e7eSjoerg MapVector<Instruction *, uint64_t> MinBWs;
49706f32e7eSjoerg
49806f32e7eSjoerg // Determine the roots. We work bottom-up, from truncs or icmps.
49906f32e7eSjoerg bool SeenExtFromIllegalType = false;
50006f32e7eSjoerg for (auto *BB : Blocks)
50106f32e7eSjoerg for (auto &I : *BB) {
50206f32e7eSjoerg InstructionSet.insert(&I);
50306f32e7eSjoerg
50406f32e7eSjoerg if (TTI && (isa<ZExtInst>(&I) || isa<SExtInst>(&I)) &&
50506f32e7eSjoerg !TTI->isTypeLegal(I.getOperand(0)->getType()))
50606f32e7eSjoerg SeenExtFromIllegalType = true;
50706f32e7eSjoerg
50806f32e7eSjoerg // Only deal with non-vector integers up to 64-bits wide.
50906f32e7eSjoerg if ((isa<TruncInst>(&I) || isa<ICmpInst>(&I)) &&
51006f32e7eSjoerg !I.getType()->isVectorTy() &&
51106f32e7eSjoerg I.getOperand(0)->getType()->getScalarSizeInBits() <= 64) {
51206f32e7eSjoerg // Don't make work for ourselves. If we know the loaded type is legal,
51306f32e7eSjoerg // don't add it to the worklist.
51406f32e7eSjoerg if (TTI && isa<TruncInst>(&I) && TTI->isTypeLegal(I.getType()))
51506f32e7eSjoerg continue;
51606f32e7eSjoerg
51706f32e7eSjoerg Worklist.push_back(&I);
51806f32e7eSjoerg Roots.insert(&I);
51906f32e7eSjoerg }
52006f32e7eSjoerg }
52106f32e7eSjoerg // Early exit.
52206f32e7eSjoerg if (Worklist.empty() || (TTI && !SeenExtFromIllegalType))
52306f32e7eSjoerg return MinBWs;
52406f32e7eSjoerg
52506f32e7eSjoerg // Now proceed breadth-first, unioning values together.
52606f32e7eSjoerg while (!Worklist.empty()) {
52706f32e7eSjoerg Value *Val = Worklist.pop_back_val();
52806f32e7eSjoerg Value *Leader = ECs.getOrInsertLeaderValue(Val);
52906f32e7eSjoerg
53006f32e7eSjoerg if (Visited.count(Val))
53106f32e7eSjoerg continue;
53206f32e7eSjoerg Visited.insert(Val);
53306f32e7eSjoerg
53406f32e7eSjoerg // Non-instructions terminate a chain successfully.
53506f32e7eSjoerg if (!isa<Instruction>(Val))
53606f32e7eSjoerg continue;
53706f32e7eSjoerg Instruction *I = cast<Instruction>(Val);
53806f32e7eSjoerg
53906f32e7eSjoerg // If we encounter a type that is larger than 64 bits, we can't represent
54006f32e7eSjoerg // it so bail out.
54106f32e7eSjoerg if (DB.getDemandedBits(I).getBitWidth() > 64)
54206f32e7eSjoerg return MapVector<Instruction *, uint64_t>();
54306f32e7eSjoerg
54406f32e7eSjoerg uint64_t V = DB.getDemandedBits(I).getZExtValue();
54506f32e7eSjoerg DBits[Leader] |= V;
54606f32e7eSjoerg DBits[I] = V;
54706f32e7eSjoerg
54806f32e7eSjoerg // Casts, loads and instructions outside of our range terminate a chain
54906f32e7eSjoerg // successfully.
55006f32e7eSjoerg if (isa<SExtInst>(I) || isa<ZExtInst>(I) || isa<LoadInst>(I) ||
55106f32e7eSjoerg !InstructionSet.count(I))
55206f32e7eSjoerg continue;
55306f32e7eSjoerg
55406f32e7eSjoerg // Unsafe casts terminate a chain unsuccessfully. We can't do anything
55506f32e7eSjoerg // useful with bitcasts, ptrtoints or inttoptrs and it'd be unsafe to
55606f32e7eSjoerg // transform anything that relies on them.
55706f32e7eSjoerg if (isa<BitCastInst>(I) || isa<PtrToIntInst>(I) || isa<IntToPtrInst>(I) ||
55806f32e7eSjoerg !I->getType()->isIntegerTy()) {
55906f32e7eSjoerg DBits[Leader] |= ~0ULL;
56006f32e7eSjoerg continue;
56106f32e7eSjoerg }
56206f32e7eSjoerg
56306f32e7eSjoerg // We don't modify the types of PHIs. Reductions will already have been
56406f32e7eSjoerg // truncated if possible, and inductions' sizes will have been chosen by
56506f32e7eSjoerg // indvars.
56606f32e7eSjoerg if (isa<PHINode>(I))
56706f32e7eSjoerg continue;
56806f32e7eSjoerg
56906f32e7eSjoerg if (DBits[Leader] == ~0ULL)
57006f32e7eSjoerg // All bits demanded, no point continuing.
57106f32e7eSjoerg continue;
57206f32e7eSjoerg
57306f32e7eSjoerg for (Value *O : cast<User>(I)->operands()) {
57406f32e7eSjoerg ECs.unionSets(Leader, O);
57506f32e7eSjoerg Worklist.push_back(O);
57606f32e7eSjoerg }
57706f32e7eSjoerg }
57806f32e7eSjoerg
57906f32e7eSjoerg // Now we've discovered all values, walk them to see if there are
58006f32e7eSjoerg // any users we didn't see. If there are, we can't optimize that
58106f32e7eSjoerg // chain.
58206f32e7eSjoerg for (auto &I : DBits)
58306f32e7eSjoerg for (auto *U : I.first->users())
58406f32e7eSjoerg if (U->getType()->isIntegerTy() && DBits.count(U) == 0)
58506f32e7eSjoerg DBits[ECs.getOrInsertLeaderValue(I.first)] |= ~0ULL;
58606f32e7eSjoerg
58706f32e7eSjoerg for (auto I = ECs.begin(), E = ECs.end(); I != E; ++I) {
58806f32e7eSjoerg uint64_t LeaderDemandedBits = 0;
589*da58b97aSjoerg for (Value *M : llvm::make_range(ECs.member_begin(I), ECs.member_end()))
590*da58b97aSjoerg LeaderDemandedBits |= DBits[M];
59106f32e7eSjoerg
59206f32e7eSjoerg uint64_t MinBW = (sizeof(LeaderDemandedBits) * 8) -
59306f32e7eSjoerg llvm::countLeadingZeros(LeaderDemandedBits);
59406f32e7eSjoerg // Round up to a power of 2
59506f32e7eSjoerg if (!isPowerOf2_64((uint64_t)MinBW))
59606f32e7eSjoerg MinBW = NextPowerOf2(MinBW);
59706f32e7eSjoerg
59806f32e7eSjoerg // We don't modify the types of PHIs. Reductions will already have been
59906f32e7eSjoerg // truncated if possible, and inductions' sizes will have been chosen by
60006f32e7eSjoerg // indvars.
60106f32e7eSjoerg // If we are required to shrink a PHI, abandon this entire equivalence class.
60206f32e7eSjoerg bool Abort = false;
603*da58b97aSjoerg for (Value *M : llvm::make_range(ECs.member_begin(I), ECs.member_end()))
604*da58b97aSjoerg if (isa<PHINode>(M) && MinBW < M->getType()->getScalarSizeInBits()) {
60506f32e7eSjoerg Abort = true;
60606f32e7eSjoerg break;
60706f32e7eSjoerg }
60806f32e7eSjoerg if (Abort)
60906f32e7eSjoerg continue;
61006f32e7eSjoerg
611*da58b97aSjoerg for (Value *M : llvm::make_range(ECs.member_begin(I), ECs.member_end())) {
612*da58b97aSjoerg if (!isa<Instruction>(M))
61306f32e7eSjoerg continue;
614*da58b97aSjoerg Type *Ty = M->getType();
615*da58b97aSjoerg if (Roots.count(M))
616*da58b97aSjoerg Ty = cast<Instruction>(M)->getOperand(0)->getType();
61706f32e7eSjoerg if (MinBW < Ty->getScalarSizeInBits())
618*da58b97aSjoerg MinBWs[cast<Instruction>(M)] = MinBW;
61906f32e7eSjoerg }
62006f32e7eSjoerg }
62106f32e7eSjoerg
62206f32e7eSjoerg return MinBWs;
62306f32e7eSjoerg }
62406f32e7eSjoerg
62506f32e7eSjoerg /// Add all access groups in @p AccGroups to @p List.
62606f32e7eSjoerg template <typename ListT>
addToAccessGroupList(ListT & List,MDNode * AccGroups)62706f32e7eSjoerg static void addToAccessGroupList(ListT &List, MDNode *AccGroups) {
62806f32e7eSjoerg // Interpret an access group as a list containing itself.
62906f32e7eSjoerg if (AccGroups->getNumOperands() == 0) {
63006f32e7eSjoerg assert(isValidAsAccessGroup(AccGroups) && "Node must be an access group");
63106f32e7eSjoerg List.insert(AccGroups);
63206f32e7eSjoerg return;
63306f32e7eSjoerg }
63406f32e7eSjoerg
63506f32e7eSjoerg for (auto &AccGroupListOp : AccGroups->operands()) {
63606f32e7eSjoerg auto *Item = cast<MDNode>(AccGroupListOp.get());
63706f32e7eSjoerg assert(isValidAsAccessGroup(Item) && "List item must be an access group");
63806f32e7eSjoerg List.insert(Item);
63906f32e7eSjoerg }
64006f32e7eSjoerg }
64106f32e7eSjoerg
uniteAccessGroups(MDNode * AccGroups1,MDNode * AccGroups2)64206f32e7eSjoerg MDNode *llvm::uniteAccessGroups(MDNode *AccGroups1, MDNode *AccGroups2) {
64306f32e7eSjoerg if (!AccGroups1)
64406f32e7eSjoerg return AccGroups2;
64506f32e7eSjoerg if (!AccGroups2)
64606f32e7eSjoerg return AccGroups1;
64706f32e7eSjoerg if (AccGroups1 == AccGroups2)
64806f32e7eSjoerg return AccGroups1;
64906f32e7eSjoerg
65006f32e7eSjoerg SmallSetVector<Metadata *, 4> Union;
65106f32e7eSjoerg addToAccessGroupList(Union, AccGroups1);
65206f32e7eSjoerg addToAccessGroupList(Union, AccGroups2);
65306f32e7eSjoerg
65406f32e7eSjoerg if (Union.size() == 0)
65506f32e7eSjoerg return nullptr;
65606f32e7eSjoerg if (Union.size() == 1)
65706f32e7eSjoerg return cast<MDNode>(Union.front());
65806f32e7eSjoerg
65906f32e7eSjoerg LLVMContext &Ctx = AccGroups1->getContext();
66006f32e7eSjoerg return MDNode::get(Ctx, Union.getArrayRef());
66106f32e7eSjoerg }
66206f32e7eSjoerg
intersectAccessGroups(const Instruction * Inst1,const Instruction * Inst2)66306f32e7eSjoerg MDNode *llvm::intersectAccessGroups(const Instruction *Inst1,
66406f32e7eSjoerg const Instruction *Inst2) {
66506f32e7eSjoerg bool MayAccessMem1 = Inst1->mayReadOrWriteMemory();
66606f32e7eSjoerg bool MayAccessMem2 = Inst2->mayReadOrWriteMemory();
66706f32e7eSjoerg
66806f32e7eSjoerg if (!MayAccessMem1 && !MayAccessMem2)
66906f32e7eSjoerg return nullptr;
67006f32e7eSjoerg if (!MayAccessMem1)
67106f32e7eSjoerg return Inst2->getMetadata(LLVMContext::MD_access_group);
67206f32e7eSjoerg if (!MayAccessMem2)
67306f32e7eSjoerg return Inst1->getMetadata(LLVMContext::MD_access_group);
67406f32e7eSjoerg
67506f32e7eSjoerg MDNode *MD1 = Inst1->getMetadata(LLVMContext::MD_access_group);
67606f32e7eSjoerg MDNode *MD2 = Inst2->getMetadata(LLVMContext::MD_access_group);
67706f32e7eSjoerg if (!MD1 || !MD2)
67806f32e7eSjoerg return nullptr;
67906f32e7eSjoerg if (MD1 == MD2)
68006f32e7eSjoerg return MD1;
68106f32e7eSjoerg
68206f32e7eSjoerg // Use set for scalable 'contains' check.
68306f32e7eSjoerg SmallPtrSet<Metadata *, 4> AccGroupSet2;
68406f32e7eSjoerg addToAccessGroupList(AccGroupSet2, MD2);
68506f32e7eSjoerg
68606f32e7eSjoerg SmallVector<Metadata *, 4> Intersection;
68706f32e7eSjoerg if (MD1->getNumOperands() == 0) {
68806f32e7eSjoerg assert(isValidAsAccessGroup(MD1) && "Node must be an access group");
68906f32e7eSjoerg if (AccGroupSet2.count(MD1))
69006f32e7eSjoerg Intersection.push_back(MD1);
69106f32e7eSjoerg } else {
69206f32e7eSjoerg for (const MDOperand &Node : MD1->operands()) {
69306f32e7eSjoerg auto *Item = cast<MDNode>(Node.get());
69406f32e7eSjoerg assert(isValidAsAccessGroup(Item) && "List item must be an access group");
69506f32e7eSjoerg if (AccGroupSet2.count(Item))
69606f32e7eSjoerg Intersection.push_back(Item);
69706f32e7eSjoerg }
69806f32e7eSjoerg }
69906f32e7eSjoerg
70006f32e7eSjoerg if (Intersection.size() == 0)
70106f32e7eSjoerg return nullptr;
70206f32e7eSjoerg if (Intersection.size() == 1)
70306f32e7eSjoerg return cast<MDNode>(Intersection.front());
70406f32e7eSjoerg
70506f32e7eSjoerg LLVMContext &Ctx = Inst1->getContext();
70606f32e7eSjoerg return MDNode::get(Ctx, Intersection);
70706f32e7eSjoerg }
70806f32e7eSjoerg
70906f32e7eSjoerg /// \returns \p I after propagating metadata from \p VL.
propagateMetadata(Instruction * Inst,ArrayRef<Value * > VL)71006f32e7eSjoerg Instruction *llvm::propagateMetadata(Instruction *Inst, ArrayRef<Value *> VL) {
711*da58b97aSjoerg if (VL.empty())
712*da58b97aSjoerg return Inst;
71306f32e7eSjoerg Instruction *I0 = cast<Instruction>(VL[0]);
71406f32e7eSjoerg SmallVector<std::pair<unsigned, MDNode *>, 4> Metadata;
71506f32e7eSjoerg I0->getAllMetadataOtherThanDebugLoc(Metadata);
71606f32e7eSjoerg
71706f32e7eSjoerg for (auto Kind : {LLVMContext::MD_tbaa, LLVMContext::MD_alias_scope,
71806f32e7eSjoerg LLVMContext::MD_noalias, LLVMContext::MD_fpmath,
71906f32e7eSjoerg LLVMContext::MD_nontemporal, LLVMContext::MD_invariant_load,
72006f32e7eSjoerg LLVMContext::MD_access_group}) {
72106f32e7eSjoerg MDNode *MD = I0->getMetadata(Kind);
72206f32e7eSjoerg
72306f32e7eSjoerg for (int J = 1, E = VL.size(); MD && J != E; ++J) {
72406f32e7eSjoerg const Instruction *IJ = cast<Instruction>(VL[J]);
72506f32e7eSjoerg MDNode *IMD = IJ->getMetadata(Kind);
72606f32e7eSjoerg switch (Kind) {
72706f32e7eSjoerg case LLVMContext::MD_tbaa:
72806f32e7eSjoerg MD = MDNode::getMostGenericTBAA(MD, IMD);
72906f32e7eSjoerg break;
73006f32e7eSjoerg case LLVMContext::MD_alias_scope:
73106f32e7eSjoerg MD = MDNode::getMostGenericAliasScope(MD, IMD);
73206f32e7eSjoerg break;
73306f32e7eSjoerg case LLVMContext::MD_fpmath:
73406f32e7eSjoerg MD = MDNode::getMostGenericFPMath(MD, IMD);
73506f32e7eSjoerg break;
73606f32e7eSjoerg case LLVMContext::MD_noalias:
73706f32e7eSjoerg case LLVMContext::MD_nontemporal:
73806f32e7eSjoerg case LLVMContext::MD_invariant_load:
73906f32e7eSjoerg MD = MDNode::intersect(MD, IMD);
74006f32e7eSjoerg break;
74106f32e7eSjoerg case LLVMContext::MD_access_group:
74206f32e7eSjoerg MD = intersectAccessGroups(Inst, IJ);
74306f32e7eSjoerg break;
74406f32e7eSjoerg default:
74506f32e7eSjoerg llvm_unreachable("unhandled metadata");
74606f32e7eSjoerg }
74706f32e7eSjoerg }
74806f32e7eSjoerg
74906f32e7eSjoerg Inst->setMetadata(Kind, MD);
75006f32e7eSjoerg }
75106f32e7eSjoerg
75206f32e7eSjoerg return Inst;
75306f32e7eSjoerg }
75406f32e7eSjoerg
75506f32e7eSjoerg Constant *
createBitMaskForGaps(IRBuilderBase & Builder,unsigned VF,const InterleaveGroup<Instruction> & Group)756*da58b97aSjoerg llvm::createBitMaskForGaps(IRBuilderBase &Builder, unsigned VF,
75706f32e7eSjoerg const InterleaveGroup<Instruction> &Group) {
75806f32e7eSjoerg // All 1's means mask is not needed.
75906f32e7eSjoerg if (Group.getNumMembers() == Group.getFactor())
76006f32e7eSjoerg return nullptr;
76106f32e7eSjoerg
76206f32e7eSjoerg // TODO: support reversed access.
76306f32e7eSjoerg assert(!Group.isReverse() && "Reversed group not supported.");
76406f32e7eSjoerg
76506f32e7eSjoerg SmallVector<Constant *, 16> Mask;
76606f32e7eSjoerg for (unsigned i = 0; i < VF; i++)
76706f32e7eSjoerg for (unsigned j = 0; j < Group.getFactor(); ++j) {
76806f32e7eSjoerg unsigned HasMember = Group.getMember(j) ? 1 : 0;
76906f32e7eSjoerg Mask.push_back(Builder.getInt1(HasMember));
77006f32e7eSjoerg }
77106f32e7eSjoerg
77206f32e7eSjoerg return ConstantVector::get(Mask);
77306f32e7eSjoerg }
77406f32e7eSjoerg
775*da58b97aSjoerg llvm::SmallVector<int, 16>
createReplicatedMask(unsigned ReplicationFactor,unsigned VF)776*da58b97aSjoerg llvm::createReplicatedMask(unsigned ReplicationFactor, unsigned VF) {
777*da58b97aSjoerg SmallVector<int, 16> MaskVec;
77806f32e7eSjoerg for (unsigned i = 0; i < VF; i++)
77906f32e7eSjoerg for (unsigned j = 0; j < ReplicationFactor; j++)
780*da58b97aSjoerg MaskVec.push_back(i);
78106f32e7eSjoerg
782*da58b97aSjoerg return MaskVec;
78306f32e7eSjoerg }
78406f32e7eSjoerg
createInterleaveMask(unsigned VF,unsigned NumVecs)785*da58b97aSjoerg llvm::SmallVector<int, 16> llvm::createInterleaveMask(unsigned VF,
78606f32e7eSjoerg unsigned NumVecs) {
787*da58b97aSjoerg SmallVector<int, 16> Mask;
78806f32e7eSjoerg for (unsigned i = 0; i < VF; i++)
78906f32e7eSjoerg for (unsigned j = 0; j < NumVecs; j++)
790*da58b97aSjoerg Mask.push_back(j * VF + i);
79106f32e7eSjoerg
792*da58b97aSjoerg return Mask;
79306f32e7eSjoerg }
79406f32e7eSjoerg
795*da58b97aSjoerg llvm::SmallVector<int, 16>
createStrideMask(unsigned Start,unsigned Stride,unsigned VF)796*da58b97aSjoerg llvm::createStrideMask(unsigned Start, unsigned Stride, unsigned VF) {
797*da58b97aSjoerg SmallVector<int, 16> Mask;
79806f32e7eSjoerg for (unsigned i = 0; i < VF; i++)
799*da58b97aSjoerg Mask.push_back(Start + i * Stride);
80006f32e7eSjoerg
801*da58b97aSjoerg return Mask;
80206f32e7eSjoerg }
80306f32e7eSjoerg
createSequentialMask(unsigned Start,unsigned NumInts,unsigned NumUndefs)804*da58b97aSjoerg llvm::SmallVector<int, 16> llvm::createSequentialMask(unsigned Start,
805*da58b97aSjoerg unsigned NumInts,
806*da58b97aSjoerg unsigned NumUndefs) {
807*da58b97aSjoerg SmallVector<int, 16> Mask;
80806f32e7eSjoerg for (unsigned i = 0; i < NumInts; i++)
809*da58b97aSjoerg Mask.push_back(Start + i);
81006f32e7eSjoerg
81106f32e7eSjoerg for (unsigned i = 0; i < NumUndefs; i++)
812*da58b97aSjoerg Mask.push_back(-1);
81306f32e7eSjoerg
814*da58b97aSjoerg return Mask;
81506f32e7eSjoerg }
81606f32e7eSjoerg
81706f32e7eSjoerg /// A helper function for concatenating vectors. This function concatenates two
81806f32e7eSjoerg /// vectors having the same element type. If the second vector has fewer
81906f32e7eSjoerg /// elements than the first, it is padded with undefs.
concatenateTwoVectors(IRBuilderBase & Builder,Value * V1,Value * V2)820*da58b97aSjoerg static Value *concatenateTwoVectors(IRBuilderBase &Builder, Value *V1,
82106f32e7eSjoerg Value *V2) {
82206f32e7eSjoerg VectorType *VecTy1 = dyn_cast<VectorType>(V1->getType());
82306f32e7eSjoerg VectorType *VecTy2 = dyn_cast<VectorType>(V2->getType());
82406f32e7eSjoerg assert(VecTy1 && VecTy2 &&
82506f32e7eSjoerg VecTy1->getScalarType() == VecTy2->getScalarType() &&
82606f32e7eSjoerg "Expect two vectors with the same element type");
82706f32e7eSjoerg
828*da58b97aSjoerg unsigned NumElts1 = cast<FixedVectorType>(VecTy1)->getNumElements();
829*da58b97aSjoerg unsigned NumElts2 = cast<FixedVectorType>(VecTy2)->getNumElements();
83006f32e7eSjoerg assert(NumElts1 >= NumElts2 && "Unexpect the first vector has less elements");
83106f32e7eSjoerg
83206f32e7eSjoerg if (NumElts1 > NumElts2) {
83306f32e7eSjoerg // Extend with UNDEFs.
834*da58b97aSjoerg V2 = Builder.CreateShuffleVector(
835*da58b97aSjoerg V2, createSequentialMask(0, NumElts2, NumElts1 - NumElts2));
83606f32e7eSjoerg }
83706f32e7eSjoerg
838*da58b97aSjoerg return Builder.CreateShuffleVector(
839*da58b97aSjoerg V1, V2, createSequentialMask(0, NumElts1 + NumElts2, 0));
84006f32e7eSjoerg }
84106f32e7eSjoerg
concatenateVectors(IRBuilderBase & Builder,ArrayRef<Value * > Vecs)842*da58b97aSjoerg Value *llvm::concatenateVectors(IRBuilderBase &Builder,
843*da58b97aSjoerg ArrayRef<Value *> Vecs) {
84406f32e7eSjoerg unsigned NumVecs = Vecs.size();
84506f32e7eSjoerg assert(NumVecs > 1 && "Should be at least two vectors");
84606f32e7eSjoerg
84706f32e7eSjoerg SmallVector<Value *, 8> ResList;
84806f32e7eSjoerg ResList.append(Vecs.begin(), Vecs.end());
84906f32e7eSjoerg do {
85006f32e7eSjoerg SmallVector<Value *, 8> TmpList;
85106f32e7eSjoerg for (unsigned i = 0; i < NumVecs - 1; i += 2) {
85206f32e7eSjoerg Value *V0 = ResList[i], *V1 = ResList[i + 1];
85306f32e7eSjoerg assert((V0->getType() == V1->getType() || i == NumVecs - 2) &&
85406f32e7eSjoerg "Only the last vector may have a different type");
85506f32e7eSjoerg
85606f32e7eSjoerg TmpList.push_back(concatenateTwoVectors(Builder, V0, V1));
85706f32e7eSjoerg }
85806f32e7eSjoerg
85906f32e7eSjoerg // Push the last vector if the total number of vectors is odd.
86006f32e7eSjoerg if (NumVecs % 2 != 0)
86106f32e7eSjoerg TmpList.push_back(ResList[NumVecs - 1]);
86206f32e7eSjoerg
86306f32e7eSjoerg ResList = TmpList;
86406f32e7eSjoerg NumVecs = ResList.size();
86506f32e7eSjoerg } while (NumVecs > 1);
86606f32e7eSjoerg
86706f32e7eSjoerg return ResList[0];
86806f32e7eSjoerg }
86906f32e7eSjoerg
maskIsAllZeroOrUndef(Value * Mask)87006f32e7eSjoerg bool llvm::maskIsAllZeroOrUndef(Value *Mask) {
871*da58b97aSjoerg assert(isa<VectorType>(Mask->getType()) &&
872*da58b97aSjoerg isa<IntegerType>(Mask->getType()->getScalarType()) &&
873*da58b97aSjoerg cast<IntegerType>(Mask->getType()->getScalarType())->getBitWidth() ==
874*da58b97aSjoerg 1 &&
875*da58b97aSjoerg "Mask must be a vector of i1");
876*da58b97aSjoerg
87706f32e7eSjoerg auto *ConstMask = dyn_cast<Constant>(Mask);
87806f32e7eSjoerg if (!ConstMask)
87906f32e7eSjoerg return false;
88006f32e7eSjoerg if (ConstMask->isNullValue() || isa<UndefValue>(ConstMask))
88106f32e7eSjoerg return true;
882*da58b97aSjoerg if (isa<ScalableVectorType>(ConstMask->getType()))
883*da58b97aSjoerg return false;
884*da58b97aSjoerg for (unsigned
885*da58b97aSjoerg I = 0,
886*da58b97aSjoerg E = cast<FixedVectorType>(ConstMask->getType())->getNumElements();
887*da58b97aSjoerg I != E; ++I) {
88806f32e7eSjoerg if (auto *MaskElt = ConstMask->getAggregateElement(I))
88906f32e7eSjoerg if (MaskElt->isNullValue() || isa<UndefValue>(MaskElt))
89006f32e7eSjoerg continue;
89106f32e7eSjoerg return false;
89206f32e7eSjoerg }
89306f32e7eSjoerg return true;
89406f32e7eSjoerg }
89506f32e7eSjoerg
89606f32e7eSjoerg
maskIsAllOneOrUndef(Value * Mask)89706f32e7eSjoerg bool llvm::maskIsAllOneOrUndef(Value *Mask) {
898*da58b97aSjoerg assert(isa<VectorType>(Mask->getType()) &&
899*da58b97aSjoerg isa<IntegerType>(Mask->getType()->getScalarType()) &&
900*da58b97aSjoerg cast<IntegerType>(Mask->getType()->getScalarType())->getBitWidth() ==
901*da58b97aSjoerg 1 &&
902*da58b97aSjoerg "Mask must be a vector of i1");
903*da58b97aSjoerg
90406f32e7eSjoerg auto *ConstMask = dyn_cast<Constant>(Mask);
90506f32e7eSjoerg if (!ConstMask)
90606f32e7eSjoerg return false;
90706f32e7eSjoerg if (ConstMask->isAllOnesValue() || isa<UndefValue>(ConstMask))
90806f32e7eSjoerg return true;
909*da58b97aSjoerg if (isa<ScalableVectorType>(ConstMask->getType()))
910*da58b97aSjoerg return false;
911*da58b97aSjoerg for (unsigned
912*da58b97aSjoerg I = 0,
913*da58b97aSjoerg E = cast<FixedVectorType>(ConstMask->getType())->getNumElements();
914*da58b97aSjoerg I != E; ++I) {
91506f32e7eSjoerg if (auto *MaskElt = ConstMask->getAggregateElement(I))
91606f32e7eSjoerg if (MaskElt->isAllOnesValue() || isa<UndefValue>(MaskElt))
91706f32e7eSjoerg continue;
91806f32e7eSjoerg return false;
91906f32e7eSjoerg }
92006f32e7eSjoerg return true;
92106f32e7eSjoerg }
92206f32e7eSjoerg
92306f32e7eSjoerg /// TODO: This is a lot like known bits, but for
92406f32e7eSjoerg /// vectors. Is there something we can common this with?
possiblyDemandedEltsInMask(Value * Mask)92506f32e7eSjoerg APInt llvm::possiblyDemandedEltsInMask(Value *Mask) {
926*da58b97aSjoerg assert(isa<FixedVectorType>(Mask->getType()) &&
927*da58b97aSjoerg isa<IntegerType>(Mask->getType()->getScalarType()) &&
928*da58b97aSjoerg cast<IntegerType>(Mask->getType()->getScalarType())->getBitWidth() ==
929*da58b97aSjoerg 1 &&
930*da58b97aSjoerg "Mask must be a fixed width vector of i1");
93106f32e7eSjoerg
932*da58b97aSjoerg const unsigned VWidth =
933*da58b97aSjoerg cast<FixedVectorType>(Mask->getType())->getNumElements();
93406f32e7eSjoerg APInt DemandedElts = APInt::getAllOnesValue(VWidth);
93506f32e7eSjoerg if (auto *CV = dyn_cast<ConstantVector>(Mask))
93606f32e7eSjoerg for (unsigned i = 0; i < VWidth; i++)
93706f32e7eSjoerg if (CV->getAggregateElement(i)->isNullValue())
93806f32e7eSjoerg DemandedElts.clearBit(i);
93906f32e7eSjoerg return DemandedElts;
94006f32e7eSjoerg }
94106f32e7eSjoerg
isStrided(int Stride)94206f32e7eSjoerg bool InterleavedAccessInfo::isStrided(int Stride) {
94306f32e7eSjoerg unsigned Factor = std::abs(Stride);
94406f32e7eSjoerg return Factor >= 2 && Factor <= MaxInterleaveGroupFactor;
94506f32e7eSjoerg }
94606f32e7eSjoerg
collectConstStrideAccesses(MapVector<Instruction *,StrideDescriptor> & AccessStrideInfo,const ValueToValueMap & Strides)94706f32e7eSjoerg void InterleavedAccessInfo::collectConstStrideAccesses(
94806f32e7eSjoerg MapVector<Instruction *, StrideDescriptor> &AccessStrideInfo,
94906f32e7eSjoerg const ValueToValueMap &Strides) {
95006f32e7eSjoerg auto &DL = TheLoop->getHeader()->getModule()->getDataLayout();
95106f32e7eSjoerg
95206f32e7eSjoerg // Since it's desired that the load/store instructions be maintained in
95306f32e7eSjoerg // "program order" for the interleaved access analysis, we have to visit the
95406f32e7eSjoerg // blocks in the loop in reverse postorder (i.e., in a topological order).
95506f32e7eSjoerg // Such an ordering will ensure that any load/store that may be executed
95606f32e7eSjoerg // before a second load/store will precede the second load/store in
95706f32e7eSjoerg // AccessStrideInfo.
95806f32e7eSjoerg LoopBlocksDFS DFS(TheLoop);
95906f32e7eSjoerg DFS.perform(LI);
96006f32e7eSjoerg for (BasicBlock *BB : make_range(DFS.beginRPO(), DFS.endRPO()))
96106f32e7eSjoerg for (auto &I : *BB) {
96206f32e7eSjoerg Value *Ptr = getLoadStorePointerOperand(&I);
963*da58b97aSjoerg if (!Ptr)
964*da58b97aSjoerg continue;
965*da58b97aSjoerg Type *ElementTy = getLoadStoreType(&I);
966*da58b97aSjoerg
96706f32e7eSjoerg // We don't check wrapping here because we don't know yet if Ptr will be
96806f32e7eSjoerg // part of a full group or a group with gaps. Checking wrapping for all
96906f32e7eSjoerg // pointers (even those that end up in groups with no gaps) will be overly
97006f32e7eSjoerg // conservative. For full groups, wrapping should be ok since if we would
97106f32e7eSjoerg // wrap around the address space we would do a memory access at nullptr
97206f32e7eSjoerg // even without the transformation. The wrapping checks are therefore
97306f32e7eSjoerg // deferred until after we've formed the interleaved groups.
97406f32e7eSjoerg int64_t Stride = getPtrStride(PSE, Ptr, TheLoop, Strides,
97506f32e7eSjoerg /*Assume=*/true, /*ShouldCheckWrap=*/false);
97606f32e7eSjoerg
97706f32e7eSjoerg const SCEV *Scev = replaceSymbolicStrideSCEV(PSE, Strides, Ptr);
978*da58b97aSjoerg uint64_t Size = DL.getTypeAllocSize(ElementTy);
979*da58b97aSjoerg AccessStrideInfo[&I] = StrideDescriptor(Stride, Scev, Size,
980*da58b97aSjoerg getLoadStoreAlignment(&I));
98106f32e7eSjoerg }
98206f32e7eSjoerg }
98306f32e7eSjoerg
98406f32e7eSjoerg // Analyze interleaved accesses and collect them into interleaved load and
98506f32e7eSjoerg // store groups.
98606f32e7eSjoerg //
98706f32e7eSjoerg // When generating code for an interleaved load group, we effectively hoist all
98806f32e7eSjoerg // loads in the group to the location of the first load in program order. When
98906f32e7eSjoerg // generating code for an interleaved store group, we sink all stores to the
99006f32e7eSjoerg // location of the last store. This code motion can change the order of load
99106f32e7eSjoerg // and store instructions and may break dependences.
99206f32e7eSjoerg //
99306f32e7eSjoerg // The code generation strategy mentioned above ensures that we won't violate
99406f32e7eSjoerg // any write-after-read (WAR) dependences.
99506f32e7eSjoerg //
99606f32e7eSjoerg // E.g., for the WAR dependence: a = A[i]; // (1)
99706f32e7eSjoerg // A[i] = b; // (2)
99806f32e7eSjoerg //
99906f32e7eSjoerg // The store group of (2) is always inserted at or below (2), and the load
100006f32e7eSjoerg // group of (1) is always inserted at or above (1). Thus, the instructions will
100106f32e7eSjoerg // never be reordered. All other dependences are checked to ensure the
100206f32e7eSjoerg // correctness of the instruction reordering.
100306f32e7eSjoerg //
100406f32e7eSjoerg // The algorithm visits all memory accesses in the loop in bottom-up program
100506f32e7eSjoerg // order. Program order is established by traversing the blocks in the loop in
100606f32e7eSjoerg // reverse postorder when collecting the accesses.
100706f32e7eSjoerg //
100806f32e7eSjoerg // We visit the memory accesses in bottom-up order because it can simplify the
100906f32e7eSjoerg // construction of store groups in the presence of write-after-write (WAW)
101006f32e7eSjoerg // dependences.
101106f32e7eSjoerg //
101206f32e7eSjoerg // E.g., for the WAW dependence: A[i] = a; // (1)
101306f32e7eSjoerg // A[i] = b; // (2)
101406f32e7eSjoerg // A[i + 1] = c; // (3)
101506f32e7eSjoerg //
101606f32e7eSjoerg // We will first create a store group with (3) and (2). (1) can't be added to
101706f32e7eSjoerg // this group because it and (2) are dependent. However, (1) can be grouped
101806f32e7eSjoerg // with other accesses that may precede it in program order. Note that a
101906f32e7eSjoerg // bottom-up order does not imply that WAW dependences should not be checked.
analyzeInterleaving(bool EnablePredicatedInterleavedMemAccesses)102006f32e7eSjoerg void InterleavedAccessInfo::analyzeInterleaving(
102106f32e7eSjoerg bool EnablePredicatedInterleavedMemAccesses) {
102206f32e7eSjoerg LLVM_DEBUG(dbgs() << "LV: Analyzing interleaved accesses...\n");
102306f32e7eSjoerg const ValueToValueMap &Strides = LAI->getSymbolicStrides();
102406f32e7eSjoerg
102506f32e7eSjoerg // Holds all accesses with a constant stride.
102606f32e7eSjoerg MapVector<Instruction *, StrideDescriptor> AccessStrideInfo;
102706f32e7eSjoerg collectConstStrideAccesses(AccessStrideInfo, Strides);
102806f32e7eSjoerg
102906f32e7eSjoerg if (AccessStrideInfo.empty())
103006f32e7eSjoerg return;
103106f32e7eSjoerg
103206f32e7eSjoerg // Collect the dependences in the loop.
103306f32e7eSjoerg collectDependences();
103406f32e7eSjoerg
103506f32e7eSjoerg // Holds all interleaved store groups temporarily.
103606f32e7eSjoerg SmallSetVector<InterleaveGroup<Instruction> *, 4> StoreGroups;
103706f32e7eSjoerg // Holds all interleaved load groups temporarily.
103806f32e7eSjoerg SmallSetVector<InterleaveGroup<Instruction> *, 4> LoadGroups;
103906f32e7eSjoerg
104006f32e7eSjoerg // Search in bottom-up program order for pairs of accesses (A and B) that can
104106f32e7eSjoerg // form interleaved load or store groups. In the algorithm below, access A
104206f32e7eSjoerg // precedes access B in program order. We initialize a group for B in the
104306f32e7eSjoerg // outer loop of the algorithm, and then in the inner loop, we attempt to
104406f32e7eSjoerg // insert each A into B's group if:
104506f32e7eSjoerg //
104606f32e7eSjoerg // 1. A and B have the same stride,
104706f32e7eSjoerg // 2. A and B have the same memory object size, and
104806f32e7eSjoerg // 3. A belongs in B's group according to its distance from B.
104906f32e7eSjoerg //
105006f32e7eSjoerg // Special care is taken to ensure group formation will not break any
105106f32e7eSjoerg // dependences.
105206f32e7eSjoerg for (auto BI = AccessStrideInfo.rbegin(), E = AccessStrideInfo.rend();
105306f32e7eSjoerg BI != E; ++BI) {
105406f32e7eSjoerg Instruction *B = BI->first;
105506f32e7eSjoerg StrideDescriptor DesB = BI->second;
105606f32e7eSjoerg
105706f32e7eSjoerg // Initialize a group for B if it has an allowable stride. Even if we don't
105806f32e7eSjoerg // create a group for B, we continue with the bottom-up algorithm to ensure
105906f32e7eSjoerg // we don't break any of B's dependences.
106006f32e7eSjoerg InterleaveGroup<Instruction> *Group = nullptr;
106106f32e7eSjoerg if (isStrided(DesB.Stride) &&
106206f32e7eSjoerg (!isPredicated(B->getParent()) || EnablePredicatedInterleavedMemAccesses)) {
106306f32e7eSjoerg Group = getInterleaveGroup(B);
106406f32e7eSjoerg if (!Group) {
106506f32e7eSjoerg LLVM_DEBUG(dbgs() << "LV: Creating an interleave group with:" << *B
106606f32e7eSjoerg << '\n');
106706f32e7eSjoerg Group = createInterleaveGroup(B, DesB.Stride, DesB.Alignment);
106806f32e7eSjoerg }
106906f32e7eSjoerg if (B->mayWriteToMemory())
107006f32e7eSjoerg StoreGroups.insert(Group);
107106f32e7eSjoerg else
107206f32e7eSjoerg LoadGroups.insert(Group);
107306f32e7eSjoerg }
107406f32e7eSjoerg
107506f32e7eSjoerg for (auto AI = std::next(BI); AI != E; ++AI) {
107606f32e7eSjoerg Instruction *A = AI->first;
107706f32e7eSjoerg StrideDescriptor DesA = AI->second;
107806f32e7eSjoerg
107906f32e7eSjoerg // Our code motion strategy implies that we can't have dependences
108006f32e7eSjoerg // between accesses in an interleaved group and other accesses located
108106f32e7eSjoerg // between the first and last member of the group. Note that this also
108206f32e7eSjoerg // means that a group can't have more than one member at a given offset.
108306f32e7eSjoerg // The accesses in a group can have dependences with other accesses, but
108406f32e7eSjoerg // we must ensure we don't extend the boundaries of the group such that
108506f32e7eSjoerg // we encompass those dependent accesses.
108606f32e7eSjoerg //
108706f32e7eSjoerg // For example, assume we have the sequence of accesses shown below in a
108806f32e7eSjoerg // stride-2 loop:
108906f32e7eSjoerg //
109006f32e7eSjoerg // (1, 2) is a group | A[i] = a; // (1)
109106f32e7eSjoerg // | A[i-1] = b; // (2) |
109206f32e7eSjoerg // A[i-3] = c; // (3)
109306f32e7eSjoerg // A[i] = d; // (4) | (2, 4) is not a group
109406f32e7eSjoerg //
109506f32e7eSjoerg // Because accesses (2) and (3) are dependent, we can group (2) with (1)
109606f32e7eSjoerg // but not with (4). If we did, the dependent access (3) would be within
109706f32e7eSjoerg // the boundaries of the (2, 4) group.
109806f32e7eSjoerg if (!canReorderMemAccessesForInterleavedGroups(&*AI, &*BI)) {
109906f32e7eSjoerg // If a dependence exists and A is already in a group, we know that A
110006f32e7eSjoerg // must be a store since A precedes B and WAR dependences are allowed.
110106f32e7eSjoerg // Thus, A would be sunk below B. We release A's group to prevent this
110206f32e7eSjoerg // illegal code motion. A will then be free to form another group with
110306f32e7eSjoerg // instructions that precede it.
110406f32e7eSjoerg if (isInterleaved(A)) {
110506f32e7eSjoerg InterleaveGroup<Instruction> *StoreGroup = getInterleaveGroup(A);
110606f32e7eSjoerg
110706f32e7eSjoerg LLVM_DEBUG(dbgs() << "LV: Invalidated store group due to "
110806f32e7eSjoerg "dependence between " << *A << " and "<< *B << '\n');
110906f32e7eSjoerg
111006f32e7eSjoerg StoreGroups.remove(StoreGroup);
111106f32e7eSjoerg releaseGroup(StoreGroup);
111206f32e7eSjoerg }
111306f32e7eSjoerg
111406f32e7eSjoerg // If a dependence exists and A is not already in a group (or it was
111506f32e7eSjoerg // and we just released it), B might be hoisted above A (if B is a
111606f32e7eSjoerg // load) or another store might be sunk below A (if B is a store). In
111706f32e7eSjoerg // either case, we can't add additional instructions to B's group. B
111806f32e7eSjoerg // will only form a group with instructions that it precedes.
111906f32e7eSjoerg break;
112006f32e7eSjoerg }
112106f32e7eSjoerg
112206f32e7eSjoerg // At this point, we've checked for illegal code motion. If either A or B
112306f32e7eSjoerg // isn't strided, there's nothing left to do.
112406f32e7eSjoerg if (!isStrided(DesA.Stride) || !isStrided(DesB.Stride))
112506f32e7eSjoerg continue;
112606f32e7eSjoerg
112706f32e7eSjoerg // Ignore A if it's already in a group or isn't the same kind of memory
112806f32e7eSjoerg // operation as B.
112906f32e7eSjoerg // Note that mayReadFromMemory() isn't mutually exclusive to
113006f32e7eSjoerg // mayWriteToMemory in the case of atomic loads. We shouldn't see those
113106f32e7eSjoerg // here, canVectorizeMemory() should have returned false - except for the
113206f32e7eSjoerg // case we asked for optimization remarks.
113306f32e7eSjoerg if (isInterleaved(A) ||
113406f32e7eSjoerg (A->mayReadFromMemory() != B->mayReadFromMemory()) ||
113506f32e7eSjoerg (A->mayWriteToMemory() != B->mayWriteToMemory()))
113606f32e7eSjoerg continue;
113706f32e7eSjoerg
113806f32e7eSjoerg // Check rules 1 and 2. Ignore A if its stride or size is different from
113906f32e7eSjoerg // that of B.
114006f32e7eSjoerg if (DesA.Stride != DesB.Stride || DesA.Size != DesB.Size)
114106f32e7eSjoerg continue;
114206f32e7eSjoerg
114306f32e7eSjoerg // Ignore A if the memory object of A and B don't belong to the same
114406f32e7eSjoerg // address space
114506f32e7eSjoerg if (getLoadStoreAddressSpace(A) != getLoadStoreAddressSpace(B))
114606f32e7eSjoerg continue;
114706f32e7eSjoerg
114806f32e7eSjoerg // Calculate the distance from A to B.
114906f32e7eSjoerg const SCEVConstant *DistToB = dyn_cast<SCEVConstant>(
115006f32e7eSjoerg PSE.getSE()->getMinusSCEV(DesA.Scev, DesB.Scev));
115106f32e7eSjoerg if (!DistToB)
115206f32e7eSjoerg continue;
115306f32e7eSjoerg int64_t DistanceToB = DistToB->getAPInt().getSExtValue();
115406f32e7eSjoerg
115506f32e7eSjoerg // Check rule 3. Ignore A if its distance to B is not a multiple of the
115606f32e7eSjoerg // size.
115706f32e7eSjoerg if (DistanceToB % static_cast<int64_t>(DesB.Size))
115806f32e7eSjoerg continue;
115906f32e7eSjoerg
116006f32e7eSjoerg // All members of a predicated interleave-group must have the same predicate,
116106f32e7eSjoerg // and currently must reside in the same BB.
116206f32e7eSjoerg BasicBlock *BlockA = A->getParent();
116306f32e7eSjoerg BasicBlock *BlockB = B->getParent();
116406f32e7eSjoerg if ((isPredicated(BlockA) || isPredicated(BlockB)) &&
116506f32e7eSjoerg (!EnablePredicatedInterleavedMemAccesses || BlockA != BlockB))
116606f32e7eSjoerg continue;
116706f32e7eSjoerg
116806f32e7eSjoerg // The index of A is the index of B plus A's distance to B in multiples
116906f32e7eSjoerg // of the size.
117006f32e7eSjoerg int IndexA =
117106f32e7eSjoerg Group->getIndex(B) + DistanceToB / static_cast<int64_t>(DesB.Size);
117206f32e7eSjoerg
117306f32e7eSjoerg // Try to insert A into B's group.
117406f32e7eSjoerg if (Group->insertMember(A, IndexA, DesA.Alignment)) {
117506f32e7eSjoerg LLVM_DEBUG(dbgs() << "LV: Inserted:" << *A << '\n'
117606f32e7eSjoerg << " into the interleave group with" << *B
117706f32e7eSjoerg << '\n');
117806f32e7eSjoerg InterleaveGroupMap[A] = Group;
117906f32e7eSjoerg
118006f32e7eSjoerg // Set the first load in program order as the insert position.
118106f32e7eSjoerg if (A->mayReadFromMemory())
118206f32e7eSjoerg Group->setInsertPos(A);
118306f32e7eSjoerg }
118406f32e7eSjoerg } // Iteration over A accesses.
118506f32e7eSjoerg } // Iteration over B accesses.
118606f32e7eSjoerg
118706f32e7eSjoerg // Remove interleaved store groups with gaps.
118806f32e7eSjoerg for (auto *Group : StoreGroups)
118906f32e7eSjoerg if (Group->getNumMembers() != Group->getFactor()) {
119006f32e7eSjoerg LLVM_DEBUG(
119106f32e7eSjoerg dbgs() << "LV: Invalidate candidate interleaved store group due "
119206f32e7eSjoerg "to gaps.\n");
119306f32e7eSjoerg releaseGroup(Group);
119406f32e7eSjoerg }
119506f32e7eSjoerg // Remove interleaved groups with gaps (currently only loads) whose memory
119606f32e7eSjoerg // accesses may wrap around. We have to revisit the getPtrStride analysis,
119706f32e7eSjoerg // this time with ShouldCheckWrap=true, since collectConstStrideAccesses does
119806f32e7eSjoerg // not check wrapping (see documentation there).
119906f32e7eSjoerg // FORNOW we use Assume=false;
120006f32e7eSjoerg // TODO: Change to Assume=true but making sure we don't exceed the threshold
120106f32e7eSjoerg // of runtime SCEV assumptions checks (thereby potentially failing to
120206f32e7eSjoerg // vectorize altogether).
120306f32e7eSjoerg // Additional optional optimizations:
120406f32e7eSjoerg // TODO: If we are peeling the loop and we know that the first pointer doesn't
120506f32e7eSjoerg // wrap then we can deduce that all pointers in the group don't wrap.
120606f32e7eSjoerg // This means that we can forcefully peel the loop in order to only have to
120706f32e7eSjoerg // check the first pointer for no-wrap. When we'll change to use Assume=true
120806f32e7eSjoerg // we'll only need at most one runtime check per interleaved group.
120906f32e7eSjoerg for (auto *Group : LoadGroups) {
121006f32e7eSjoerg // Case 1: A full group. Can Skip the checks; For full groups, if the wide
121106f32e7eSjoerg // load would wrap around the address space we would do a memory access at
121206f32e7eSjoerg // nullptr even without the transformation.
121306f32e7eSjoerg if (Group->getNumMembers() == Group->getFactor())
121406f32e7eSjoerg continue;
121506f32e7eSjoerg
121606f32e7eSjoerg // Case 2: If first and last members of the group don't wrap this implies
121706f32e7eSjoerg // that all the pointers in the group don't wrap.
121806f32e7eSjoerg // So we check only group member 0 (which is always guaranteed to exist),
121906f32e7eSjoerg // and group member Factor - 1; If the latter doesn't exist we rely on
122006f32e7eSjoerg // peeling (if it is a non-reversed accsess -- see Case 3).
122106f32e7eSjoerg Value *FirstMemberPtr = getLoadStorePointerOperand(Group->getMember(0));
122206f32e7eSjoerg if (!getPtrStride(PSE, FirstMemberPtr, TheLoop, Strides, /*Assume=*/false,
122306f32e7eSjoerg /*ShouldCheckWrap=*/true)) {
122406f32e7eSjoerg LLVM_DEBUG(
122506f32e7eSjoerg dbgs() << "LV: Invalidate candidate interleaved group due to "
122606f32e7eSjoerg "first group member potentially pointer-wrapping.\n");
122706f32e7eSjoerg releaseGroup(Group);
122806f32e7eSjoerg continue;
122906f32e7eSjoerg }
123006f32e7eSjoerg Instruction *LastMember = Group->getMember(Group->getFactor() - 1);
123106f32e7eSjoerg if (LastMember) {
123206f32e7eSjoerg Value *LastMemberPtr = getLoadStorePointerOperand(LastMember);
123306f32e7eSjoerg if (!getPtrStride(PSE, LastMemberPtr, TheLoop, Strides, /*Assume=*/false,
123406f32e7eSjoerg /*ShouldCheckWrap=*/true)) {
123506f32e7eSjoerg LLVM_DEBUG(
123606f32e7eSjoerg dbgs() << "LV: Invalidate candidate interleaved group due to "
123706f32e7eSjoerg "last group member potentially pointer-wrapping.\n");
123806f32e7eSjoerg releaseGroup(Group);
123906f32e7eSjoerg }
124006f32e7eSjoerg } else {
124106f32e7eSjoerg // Case 3: A non-reversed interleaved load group with gaps: We need
124206f32e7eSjoerg // to execute at least one scalar epilogue iteration. This will ensure
124306f32e7eSjoerg // we don't speculatively access memory out-of-bounds. We only need
124406f32e7eSjoerg // to look for a member at index factor - 1, since every group must have
124506f32e7eSjoerg // a member at index zero.
124606f32e7eSjoerg if (Group->isReverse()) {
124706f32e7eSjoerg LLVM_DEBUG(
124806f32e7eSjoerg dbgs() << "LV: Invalidate candidate interleaved group due to "
124906f32e7eSjoerg "a reverse access with gaps.\n");
125006f32e7eSjoerg releaseGroup(Group);
125106f32e7eSjoerg continue;
125206f32e7eSjoerg }
125306f32e7eSjoerg LLVM_DEBUG(
125406f32e7eSjoerg dbgs() << "LV: Interleaved group requires epilogue iteration.\n");
125506f32e7eSjoerg RequiresScalarEpilogue = true;
125606f32e7eSjoerg }
125706f32e7eSjoerg }
125806f32e7eSjoerg }
125906f32e7eSjoerg
invalidateGroupsRequiringScalarEpilogue()126006f32e7eSjoerg void InterleavedAccessInfo::invalidateGroupsRequiringScalarEpilogue() {
126106f32e7eSjoerg // If no group had triggered the requirement to create an epilogue loop,
126206f32e7eSjoerg // there is nothing to do.
126306f32e7eSjoerg if (!requiresScalarEpilogue())
126406f32e7eSjoerg return;
126506f32e7eSjoerg
1266*da58b97aSjoerg bool ReleasedGroup = false;
1267*da58b97aSjoerg // Release groups requiring scalar epilogues. Note that this also removes them
1268*da58b97aSjoerg // from InterleaveGroups.
1269*da58b97aSjoerg for (auto *Group : make_early_inc_range(InterleaveGroups)) {
1270*da58b97aSjoerg if (!Group->requiresScalarEpilogue())
1271*da58b97aSjoerg continue;
127206f32e7eSjoerg LLVM_DEBUG(
127306f32e7eSjoerg dbgs()
127406f32e7eSjoerg << "LV: Invalidate candidate interleaved group due to gaps that "
127506f32e7eSjoerg "require a scalar epilogue (not allowed under optsize) and cannot "
127606f32e7eSjoerg "be masked (not enabled). \n");
1277*da58b97aSjoerg releaseGroup(Group);
1278*da58b97aSjoerg ReleasedGroup = true;
127906f32e7eSjoerg }
1280*da58b97aSjoerg assert(ReleasedGroup && "At least one group must be invalidated, as a "
1281*da58b97aSjoerg "scalar epilogue was required");
1282*da58b97aSjoerg (void)ReleasedGroup;
128306f32e7eSjoerg RequiresScalarEpilogue = false;
128406f32e7eSjoerg }
128506f32e7eSjoerg
128606f32e7eSjoerg template <typename InstT>
addMetadata(InstT * NewInst) const128706f32e7eSjoerg void InterleaveGroup<InstT>::addMetadata(InstT *NewInst) const {
128806f32e7eSjoerg llvm_unreachable("addMetadata can only be used for Instruction");
128906f32e7eSjoerg }
129006f32e7eSjoerg
129106f32e7eSjoerg namespace llvm {
129206f32e7eSjoerg template <>
addMetadata(Instruction * NewInst) const129306f32e7eSjoerg void InterleaveGroup<Instruction>::addMetadata(Instruction *NewInst) const {
129406f32e7eSjoerg SmallVector<Value *, 4> VL;
129506f32e7eSjoerg std::transform(Members.begin(), Members.end(), std::back_inserter(VL),
129606f32e7eSjoerg [](std::pair<int, Instruction *> p) { return p.second; });
129706f32e7eSjoerg propagateMetadata(NewInst, VL);
129806f32e7eSjoerg }
129906f32e7eSjoerg }
1300*da58b97aSjoerg
mangleTLIVectorName(StringRef VectorName,StringRef ScalarName,unsigned numArgs,ElementCount VF)1301*da58b97aSjoerg std::string VFABI::mangleTLIVectorName(StringRef VectorName,
1302*da58b97aSjoerg StringRef ScalarName, unsigned numArgs,
1303*da58b97aSjoerg ElementCount VF) {
1304*da58b97aSjoerg SmallString<256> Buffer;
1305*da58b97aSjoerg llvm::raw_svector_ostream Out(Buffer);
1306*da58b97aSjoerg Out << "_ZGV" << VFABI::_LLVM_ << "N";
1307*da58b97aSjoerg if (VF.isScalable())
1308*da58b97aSjoerg Out << 'x';
1309*da58b97aSjoerg else
1310*da58b97aSjoerg Out << VF.getFixedValue();
1311*da58b97aSjoerg for (unsigned I = 0; I < numArgs; ++I)
1312*da58b97aSjoerg Out << "v";
1313*da58b97aSjoerg Out << "_" << ScalarName << "(" << VectorName << ")";
1314*da58b97aSjoerg return std::string(Out.str());
1315*da58b97aSjoerg }
1316*da58b97aSjoerg
getVectorVariantNames(const CallInst & CI,SmallVectorImpl<std::string> & VariantMappings)1317*da58b97aSjoerg void VFABI::getVectorVariantNames(
1318*da58b97aSjoerg const CallInst &CI, SmallVectorImpl<std::string> &VariantMappings) {
1319*da58b97aSjoerg const StringRef S =
1320*da58b97aSjoerg CI.getAttribute(AttributeList::FunctionIndex, VFABI::MappingsAttrName)
1321*da58b97aSjoerg .getValueAsString();
1322*da58b97aSjoerg if (S.empty())
1323*da58b97aSjoerg return;
1324*da58b97aSjoerg
1325*da58b97aSjoerg SmallVector<StringRef, 8> ListAttr;
1326*da58b97aSjoerg S.split(ListAttr, ",");
1327*da58b97aSjoerg
1328*da58b97aSjoerg for (auto &S : SetVector<StringRef>(ListAttr.begin(), ListAttr.end())) {
1329*da58b97aSjoerg #ifndef NDEBUG
1330*da58b97aSjoerg LLVM_DEBUG(dbgs() << "VFABI: adding mapping '" << S << "'\n");
1331*da58b97aSjoerg Optional<VFInfo> Info = VFABI::tryDemangleForVFABI(S, *(CI.getModule()));
1332*da58b97aSjoerg assert(Info.hasValue() && "Invalid name for a VFABI variant.");
1333*da58b97aSjoerg assert(CI.getModule()->getFunction(Info.getValue().VectorName) &&
1334*da58b97aSjoerg "Vector function is missing.");
1335*da58b97aSjoerg #endif
1336*da58b97aSjoerg VariantMappings.push_back(std::string(S));
1337*da58b97aSjoerg }
1338*da58b97aSjoerg }
1339*da58b97aSjoerg
hasValidParameterList() const1340*da58b97aSjoerg bool VFShape::hasValidParameterList() const {
1341*da58b97aSjoerg for (unsigned Pos = 0, NumParams = Parameters.size(); Pos < NumParams;
1342*da58b97aSjoerg ++Pos) {
1343*da58b97aSjoerg assert(Parameters[Pos].ParamPos == Pos && "Broken parameter list.");
1344*da58b97aSjoerg
1345*da58b97aSjoerg switch (Parameters[Pos].ParamKind) {
1346*da58b97aSjoerg default: // Nothing to check.
1347*da58b97aSjoerg break;
1348*da58b97aSjoerg case VFParamKind::OMP_Linear:
1349*da58b97aSjoerg case VFParamKind::OMP_LinearRef:
1350*da58b97aSjoerg case VFParamKind::OMP_LinearVal:
1351*da58b97aSjoerg case VFParamKind::OMP_LinearUVal:
1352*da58b97aSjoerg // Compile time linear steps must be non-zero.
1353*da58b97aSjoerg if (Parameters[Pos].LinearStepOrPos == 0)
1354*da58b97aSjoerg return false;
1355*da58b97aSjoerg break;
1356*da58b97aSjoerg case VFParamKind::OMP_LinearPos:
1357*da58b97aSjoerg case VFParamKind::OMP_LinearRefPos:
1358*da58b97aSjoerg case VFParamKind::OMP_LinearValPos:
1359*da58b97aSjoerg case VFParamKind::OMP_LinearUValPos:
1360*da58b97aSjoerg // The runtime linear step must be referring to some other
1361*da58b97aSjoerg // parameters in the signature.
1362*da58b97aSjoerg if (Parameters[Pos].LinearStepOrPos >= int(NumParams))
1363*da58b97aSjoerg return false;
1364*da58b97aSjoerg // The linear step parameter must be marked as uniform.
1365*da58b97aSjoerg if (Parameters[Parameters[Pos].LinearStepOrPos].ParamKind !=
1366*da58b97aSjoerg VFParamKind::OMP_Uniform)
1367*da58b97aSjoerg return false;
1368*da58b97aSjoerg // The linear step parameter can't point at itself.
1369*da58b97aSjoerg if (Parameters[Pos].LinearStepOrPos == int(Pos))
1370*da58b97aSjoerg return false;
1371*da58b97aSjoerg break;
1372*da58b97aSjoerg case VFParamKind::GlobalPredicate:
1373*da58b97aSjoerg // The global predicate must be the unique. Can be placed anywhere in the
1374*da58b97aSjoerg // signature.
1375*da58b97aSjoerg for (unsigned NextPos = Pos + 1; NextPos < NumParams; ++NextPos)
1376*da58b97aSjoerg if (Parameters[NextPos].ParamKind == VFParamKind::GlobalPredicate)
1377*da58b97aSjoerg return false;
1378*da58b97aSjoerg break;
1379*da58b97aSjoerg }
1380*da58b97aSjoerg }
1381*da58b97aSjoerg return true;
1382*da58b97aSjoerg }
1383