1 //===----------- VectorUtils.cpp - Vectorizer utility functions -----------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines vectorizer utilities.
12 //===----------------------------------------------------------------------===//
14 #include "llvm/Analysis/LoopInfo.h"
15 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
16 #include "llvm/Analysis/ScalarEvolution.h"
17 #include "llvm/Analysis/VectorUtils.h"
18 #include "llvm/IR/GetElementPtrTypeIterator.h"
19 #include "llvm/IR/PatternMatch.h"
20 #include "llvm/IR/Value.h"
21 #include "llvm/IR/Constants.h"
24 using namespace llvm::PatternMatch;
26 /// \brief Identify if the intrinsic is trivially vectorizable.
27 /// This method returns true if the intrinsic's argument types are all
28 /// scalars for the scalar form of the intrinsic and all vectors for
29 /// the vector form of the intrinsic.
30 bool llvm::isTriviallyVectorizable(Intrinsic::ID ID) {
38 case Intrinsic::log10:
41 case Intrinsic::minnum:
42 case Intrinsic::maxnum:
43 case Intrinsic::copysign:
44 case Intrinsic::floor:
46 case Intrinsic::trunc:
48 case Intrinsic::nearbyint:
49 case Intrinsic::round:
50 case Intrinsic::bswap:
51 case Intrinsic::ctpop:
54 case Intrinsic::fmuladd:
64 /// \brief Identifies if the intrinsic has a scalar operand. It check for
65 /// ctlz,cttz and powi special intrinsics whose argument is scalar.
66 bool llvm::hasVectorInstrinsicScalarOpd(Intrinsic::ID ID,
67 unsigned ScalarOpdIdx) {
72 return (ScalarOpdIdx == 1);
78 /// \brief Check call has a unary float signature
79 /// It checks following:
80 /// a) call should have a single argument
81 /// b) argument type should be floating point type
82 /// c) call instruction type and argument type should be same
83 /// d) call should only reads memory.
84 /// If all these condition is met then return ValidIntrinsicID
85 /// else return not_intrinsic.
87 llvm::checkUnaryFloatSignature(const CallInst &I,
88 Intrinsic::ID ValidIntrinsicID) {
89 if (I.getNumArgOperands() != 1 ||
90 !I.getArgOperand(0)->getType()->isFloatingPointTy() ||
91 I.getType() != I.getArgOperand(0)->getType() || !I.onlyReadsMemory())
92 return Intrinsic::not_intrinsic;
94 return ValidIntrinsicID;
97 /// \brief Check call has a binary float signature
98 /// It checks following:
99 /// a) call should have 2 arguments.
100 /// b) arguments type should be floating point type
101 /// c) call instruction type and arguments type should be same
102 /// d) call should only reads memory.
103 /// If all these condition is met then return ValidIntrinsicID
104 /// else return not_intrinsic.
106 llvm::checkBinaryFloatSignature(const CallInst &I,
107 Intrinsic::ID ValidIntrinsicID) {
108 if (I.getNumArgOperands() != 2 ||
109 !I.getArgOperand(0)->getType()->isFloatingPointTy() ||
110 !I.getArgOperand(1)->getType()->isFloatingPointTy() ||
111 I.getType() != I.getArgOperand(0)->getType() ||
112 I.getType() != I.getArgOperand(1)->getType() || !I.onlyReadsMemory())
113 return Intrinsic::not_intrinsic;
115 return ValidIntrinsicID;
118 /// \brief Returns intrinsic ID for call.
119 /// For the input call instruction it finds mapping intrinsic and returns
120 /// its ID, in case it does not found it return not_intrinsic.
121 Intrinsic::ID llvm::getIntrinsicIDForCall(CallInst *CI,
122 const TargetLibraryInfo *TLI) {
123 // If we have an intrinsic call, check if it is trivially vectorizable.
124 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(CI)) {
125 Intrinsic::ID ID = II->getIntrinsicID();
126 if (isTriviallyVectorizable(ID) || ID == Intrinsic::lifetime_start ||
127 ID == Intrinsic::lifetime_end || ID == Intrinsic::assume)
129 return Intrinsic::not_intrinsic;
133 return Intrinsic::not_intrinsic;
136 Function *F = CI->getCalledFunction();
137 // We're going to make assumptions on the semantics of the functions, check
138 // that the target knows that it's available in this environment and it does
139 // not have local linkage.
140 if (!F || F->hasLocalLinkage() || !TLI->getLibFunc(F->getName(), Func))
141 return Intrinsic::not_intrinsic;
143 // Otherwise check if we have a call to a function that can be turned into a
151 return checkUnaryFloatSignature(*CI, Intrinsic::sin);
155 return checkUnaryFloatSignature(*CI, Intrinsic::cos);
159 return checkUnaryFloatSignature(*CI, Intrinsic::exp);
163 return checkUnaryFloatSignature(*CI, Intrinsic::exp2);
167 return checkUnaryFloatSignature(*CI, Intrinsic::log);
169 case LibFunc::log10f:
170 case LibFunc::log10l:
171 return checkUnaryFloatSignature(*CI, Intrinsic::log10);
175 return checkUnaryFloatSignature(*CI, Intrinsic::log2);
179 return checkUnaryFloatSignature(*CI, Intrinsic::fabs);
183 return checkBinaryFloatSignature(*CI, Intrinsic::minnum);
187 return checkBinaryFloatSignature(*CI, Intrinsic::maxnum);
188 case LibFunc::copysign:
189 case LibFunc::copysignf:
190 case LibFunc::copysignl:
191 return checkBinaryFloatSignature(*CI, Intrinsic::copysign);
193 case LibFunc::floorf:
194 case LibFunc::floorl:
195 return checkUnaryFloatSignature(*CI, Intrinsic::floor);
199 return checkUnaryFloatSignature(*CI, Intrinsic::ceil);
201 case LibFunc::truncf:
202 case LibFunc::truncl:
203 return checkUnaryFloatSignature(*CI, Intrinsic::trunc);
207 return checkUnaryFloatSignature(*CI, Intrinsic::rint);
208 case LibFunc::nearbyint:
209 case LibFunc::nearbyintf:
210 case LibFunc::nearbyintl:
211 return checkUnaryFloatSignature(*CI, Intrinsic::nearbyint);
213 case LibFunc::roundf:
214 case LibFunc::roundl:
215 return checkUnaryFloatSignature(*CI, Intrinsic::round);
219 return checkBinaryFloatSignature(*CI, Intrinsic::pow);
222 return Intrinsic::not_intrinsic;
225 /// \brief Find the operand of the GEP that should be checked for consecutive
226 /// stores. This ignores trailing indices that have no effect on the final
228 unsigned llvm::getGEPInductionOperand(const GetElementPtrInst *Gep) {
229 const DataLayout &DL = Gep->getModule()->getDataLayout();
230 unsigned LastOperand = Gep->getNumOperands() - 1;
231 unsigned GEPAllocSize = DL.getTypeAllocSize(
232 cast<PointerType>(Gep->getType()->getScalarType())->getElementType());
234 // Walk backwards and try to peel off zeros.
235 while (LastOperand > 1 && match(Gep->getOperand(LastOperand), m_Zero())) {
236 // Find the type we're currently indexing into.
237 gep_type_iterator GEPTI = gep_type_begin(Gep);
238 std::advance(GEPTI, LastOperand - 1);
240 // If it's a type with the same allocation size as the result of the GEP we
241 // can peel off the zero index.
242 if (DL.getTypeAllocSize(*GEPTI) != GEPAllocSize)
250 /// \brief If the argument is a GEP, then returns the operand identified by
251 /// getGEPInductionOperand. However, if there is some other non-loop-invariant
252 /// operand, it returns that instead.
253 Value *llvm::stripGetElementPtr(Value *Ptr, ScalarEvolution *SE, Loop *Lp) {
254 GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Ptr);
258 unsigned InductionOperand = getGEPInductionOperand(GEP);
260 // Check that all of the gep indices are uniform except for our induction
262 for (unsigned i = 0, e = GEP->getNumOperands(); i != e; ++i)
263 if (i != InductionOperand &&
264 !SE->isLoopInvariant(SE->getSCEV(GEP->getOperand(i)), Lp))
266 return GEP->getOperand(InductionOperand);
269 /// \brief If a value has only one user that is a CastInst, return it.
270 Value *llvm::getUniqueCastUse(Value *Ptr, Loop *Lp, Type *Ty) {
271 Value *UniqueCast = nullptr;
272 for (User *U : Ptr->users()) {
273 CastInst *CI = dyn_cast<CastInst>(U);
274 if (CI && CI->getType() == Ty) {
284 /// \brief Get the stride of a pointer access in a loop. Looks for symbolic
285 /// strides "a[i*stride]". Returns the symbolic stride, or null otherwise.
286 Value *llvm::getStrideFromPointer(Value *Ptr, ScalarEvolution *SE, Loop *Lp) {
287 auto *PtrTy = dyn_cast<PointerType>(Ptr->getType());
288 if (!PtrTy || PtrTy->isAggregateType())
291 // Try to remove a gep instruction to make the pointer (actually index at this
292 // point) easier analyzable. If OrigPtr is equal to Ptr we are analzying the
293 // pointer, otherwise, we are analyzing the index.
294 Value *OrigPtr = Ptr;
296 // The size of the pointer access.
297 int64_t PtrAccessSize = 1;
299 Ptr = stripGetElementPtr(Ptr, SE, Lp);
300 const SCEV *V = SE->getSCEV(Ptr);
304 while (const SCEVCastExpr *C = dyn_cast<SCEVCastExpr>(V))
307 const SCEVAddRecExpr *S = dyn_cast<SCEVAddRecExpr>(V);
311 V = S->getStepRecurrence(*SE);
315 // Strip off the size of access multiplication if we are still analyzing the
317 if (OrigPtr == Ptr) {
318 const DataLayout &DL = Lp->getHeader()->getModule()->getDataLayout();
319 DL.getTypeAllocSize(PtrTy->getElementType());
320 if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(V)) {
321 if (M->getOperand(0)->getSCEVType() != scConstant)
324 const APInt &APStepVal =
325 cast<SCEVConstant>(M->getOperand(0))->getValue()->getValue();
327 // Huge step value - give up.
328 if (APStepVal.getBitWidth() > 64)
331 int64_t StepVal = APStepVal.getSExtValue();
332 if (PtrAccessSize != StepVal)
334 V = M->getOperand(1);
339 Type *StripedOffRecurrenceCast = nullptr;
340 if (const SCEVCastExpr *C = dyn_cast<SCEVCastExpr>(V)) {
341 StripedOffRecurrenceCast = C->getType();
345 // Look for the loop invariant symbolic value.
346 const SCEVUnknown *U = dyn_cast<SCEVUnknown>(V);
350 Value *Stride = U->getValue();
351 if (!Lp->isLoopInvariant(Stride))
354 // If we have stripped off the recurrence cast we have to make sure that we
355 // return the value that is used in this loop so that we can replace it later.
356 if (StripedOffRecurrenceCast)
357 Stride = getUniqueCastUse(Stride, Lp, StripedOffRecurrenceCast);
362 /// \brief Given a vector and an element number, see if the scalar value is
363 /// already around as a register, for example if it were inserted then extracted
365 Value *llvm::findScalarElement(Value *V, unsigned EltNo) {
366 assert(V->getType()->isVectorTy() && "Not looking at a vector?");
367 VectorType *VTy = cast<VectorType>(V->getType());
368 unsigned Width = VTy->getNumElements();
369 if (EltNo >= Width) // Out of range access.
370 return UndefValue::get(VTy->getElementType());
372 if (Constant *C = dyn_cast<Constant>(V))
373 return C->getAggregateElement(EltNo);
375 if (InsertElementInst *III = dyn_cast<InsertElementInst>(V)) {
376 // If this is an insert to a variable element, we don't know what it is.
377 if (!isa<ConstantInt>(III->getOperand(2)))
379 unsigned IIElt = cast<ConstantInt>(III->getOperand(2))->getZExtValue();
381 // If this is an insert to the element we are looking for, return the
384 return III->getOperand(1);
386 // Otherwise, the insertelement doesn't modify the value, recurse on its
388 return findScalarElement(III->getOperand(0), EltNo);
391 if (ShuffleVectorInst *SVI = dyn_cast<ShuffleVectorInst>(V)) {
392 unsigned LHSWidth = SVI->getOperand(0)->getType()->getVectorNumElements();
393 int InEl = SVI->getMaskValue(EltNo);
395 return UndefValue::get(VTy->getElementType());
396 if (InEl < (int)LHSWidth)
397 return findScalarElement(SVI->getOperand(0), InEl);
398 return findScalarElement(SVI->getOperand(1), InEl - LHSWidth);
401 // Extract a value from a vector add operation with a constant zero.
402 Value *Val = nullptr; Constant *Con = nullptr;
403 if (match(V, m_Add(m_Value(Val), m_Constant(Con))))
404 if (Constant *Elt = Con->getAggregateElement(EltNo))
405 if (Elt->isNullValue())
406 return findScalarElement(Val, EltNo);
408 // Otherwise, we don't know.
412 /// \brief Get splat value if the input is a splat vector or return nullptr.
413 /// The value may be extracted from a splat constants vector or from
414 /// a sequence of instructions that broadcast a single value into a vector.
415 llvm::Value *llvm::getSplatValue(Value *V) {
416 llvm::ConstantDataVector *CV = dyn_cast<llvm::ConstantDataVector>(V);
418 return CV->getSplatValue();
419 llvm::ShuffleVectorInst *ShuffleInst = dyn_cast<llvm::ShuffleVectorInst>(V);
422 // All-zero (our undef) shuffle mask elements.
423 for (int i : ShuffleInst->getShuffleMask())
424 if (i != 0 && i != -1)
426 // The first shuffle source is 'insertelement' with index 0.
427 llvm::InsertElementInst *InsertEltInst =
428 dyn_cast<llvm::InsertElementInst>(ShuffleInst->getOperand(0));
429 if (!InsertEltInst || !isa<ConstantInt>(InsertEltInst->getOperand(2)) ||
430 !cast<ConstantInt>(InsertEltInst->getOperand(2))->isNullValue())
433 return InsertEltInst->getOperand(1);