1 //===----------- VectorUtils.cpp - Vectorizer utility functions -----------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file defines vectorizer utilities.
11 //
12 //===----------------------------------------------------------------------===//
13
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
22 /// \brief Identify if the intrinsic is trivially vectorizable.
23 /// This method returns true if the intrinsic's argument types are all
24 /// scalars for the scalar form of the intrinsic and all vectors for
25 /// the vector form of the intrinsic.
isTriviallyVectorizable(Intrinsic::ID ID)26 bool llvm::isTriviallyVectorizable(Intrinsic::ID ID) {
27 switch (ID) {
28 case Intrinsic::sqrt:
29 case Intrinsic::sin:
30 case Intrinsic::cos:
31 case Intrinsic::exp:
32 case Intrinsic::exp2:
33 case Intrinsic::log:
34 case Intrinsic::log10:
35 case Intrinsic::log2:
36 case Intrinsic::fabs:
37 case Intrinsic::minnum:
38 case Intrinsic::maxnum:
39 case Intrinsic::copysign:
40 case Intrinsic::floor:
41 case Intrinsic::ceil:
42 case Intrinsic::trunc:
43 case Intrinsic::rint:
44 case Intrinsic::nearbyint:
45 case Intrinsic::round:
46 case Intrinsic::bswap:
47 case Intrinsic::ctpop:
48 case Intrinsic::pow:
49 case Intrinsic::fma:
50 case Intrinsic::fmuladd:
51 case Intrinsic::ctlz:
52 case Intrinsic::cttz:
53 case Intrinsic::powi:
54 return true;
55 default:
56 return false;
57 }
58 }
59
60 /// \brief Identifies if the intrinsic has a scalar operand. It check for
61 /// ctlz,cttz and powi special intrinsics whose argument is scalar.
hasVectorInstrinsicScalarOpd(Intrinsic::ID ID,unsigned ScalarOpdIdx)62 bool llvm::hasVectorInstrinsicScalarOpd(Intrinsic::ID ID,
63 unsigned ScalarOpdIdx) {
64 switch (ID) {
65 case Intrinsic::ctlz:
66 case Intrinsic::cttz:
67 case Intrinsic::powi:
68 return (ScalarOpdIdx == 1);
69 default:
70 return false;
71 }
72 }
73
74 /// \brief Check call has a unary float signature
75 /// It checks following:
76 /// a) call should have a single argument
77 /// b) argument type should be floating point type
78 /// c) call instruction type and argument type should be same
79 /// d) call should only reads memory.
80 /// If all these condition is met then return ValidIntrinsicID
81 /// else return not_intrinsic.
82 llvm::Intrinsic::ID
checkUnaryFloatSignature(const CallInst & I,Intrinsic::ID ValidIntrinsicID)83 llvm::checkUnaryFloatSignature(const CallInst &I,
84 Intrinsic::ID ValidIntrinsicID) {
85 if (I.getNumArgOperands() != 1 ||
86 !I.getArgOperand(0)->getType()->isFloatingPointTy() ||
87 I.getType() != I.getArgOperand(0)->getType() || !I.onlyReadsMemory())
88 return Intrinsic::not_intrinsic;
89
90 return ValidIntrinsicID;
91 }
92
93 /// \brief Check call has a binary float signature
94 /// It checks following:
95 /// a) call should have 2 arguments.
96 /// b) arguments type should be floating point type
97 /// c) call instruction type and arguments type should be same
98 /// d) call should only reads memory.
99 /// If all these condition is met then return ValidIntrinsicID
100 /// else return not_intrinsic.
101 llvm::Intrinsic::ID
checkBinaryFloatSignature(const CallInst & I,Intrinsic::ID ValidIntrinsicID)102 llvm::checkBinaryFloatSignature(const CallInst &I,
103 Intrinsic::ID ValidIntrinsicID) {
104 if (I.getNumArgOperands() != 2 ||
105 !I.getArgOperand(0)->getType()->isFloatingPointTy() ||
106 !I.getArgOperand(1)->getType()->isFloatingPointTy() ||
107 I.getType() != I.getArgOperand(0)->getType() ||
108 I.getType() != I.getArgOperand(1)->getType() || !I.onlyReadsMemory())
109 return Intrinsic::not_intrinsic;
110
111 return ValidIntrinsicID;
112 }
113
114 /// \brief Returns intrinsic ID for call.
115 /// For the input call instruction it finds mapping intrinsic and returns
116 /// its ID, in case it does not found it return not_intrinsic.
getIntrinsicIDForCall(CallInst * CI,const TargetLibraryInfo * TLI)117 llvm::Intrinsic::ID llvm::getIntrinsicIDForCall(CallInst *CI,
118 const TargetLibraryInfo *TLI) {
119 // If we have an intrinsic call, check if it is trivially vectorizable.
120 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(CI)) {
121 Intrinsic::ID ID = II->getIntrinsicID();
122 if (isTriviallyVectorizable(ID) || ID == Intrinsic::lifetime_start ||
123 ID == Intrinsic::lifetime_end || ID == Intrinsic::assume)
124 return ID;
125 return Intrinsic::not_intrinsic;
126 }
127
128 if (!TLI)
129 return Intrinsic::not_intrinsic;
130
131 LibFunc::Func Func;
132 Function *F = CI->getCalledFunction();
133 // We're going to make assumptions on the semantics of the functions, check
134 // that the target knows that it's available in this environment and it does
135 // not have local linkage.
136 if (!F || F->hasLocalLinkage() || !TLI->getLibFunc(F->getName(), Func))
137 return Intrinsic::not_intrinsic;
138
139 // Otherwise check if we have a call to a function that can be turned into a
140 // vector intrinsic.
141 switch (Func) {
142 default:
143 break;
144 case LibFunc::sin:
145 case LibFunc::sinf:
146 case LibFunc::sinl:
147 return checkUnaryFloatSignature(*CI, Intrinsic::sin);
148 case LibFunc::cos:
149 case LibFunc::cosf:
150 case LibFunc::cosl:
151 return checkUnaryFloatSignature(*CI, Intrinsic::cos);
152 case LibFunc::exp:
153 case LibFunc::expf:
154 case LibFunc::expl:
155 return checkUnaryFloatSignature(*CI, Intrinsic::exp);
156 case LibFunc::exp2:
157 case LibFunc::exp2f:
158 case LibFunc::exp2l:
159 return checkUnaryFloatSignature(*CI, Intrinsic::exp2);
160 case LibFunc::log:
161 case LibFunc::logf:
162 case LibFunc::logl:
163 return checkUnaryFloatSignature(*CI, Intrinsic::log);
164 case LibFunc::log10:
165 case LibFunc::log10f:
166 case LibFunc::log10l:
167 return checkUnaryFloatSignature(*CI, Intrinsic::log10);
168 case LibFunc::log2:
169 case LibFunc::log2f:
170 case LibFunc::log2l:
171 return checkUnaryFloatSignature(*CI, Intrinsic::log2);
172 case LibFunc::fabs:
173 case LibFunc::fabsf:
174 case LibFunc::fabsl:
175 return checkUnaryFloatSignature(*CI, Intrinsic::fabs);
176 case LibFunc::fmin:
177 case LibFunc::fminf:
178 case LibFunc::fminl:
179 return checkBinaryFloatSignature(*CI, Intrinsic::minnum);
180 case LibFunc::fmax:
181 case LibFunc::fmaxf:
182 case LibFunc::fmaxl:
183 return checkBinaryFloatSignature(*CI, Intrinsic::maxnum);
184 case LibFunc::copysign:
185 case LibFunc::copysignf:
186 case LibFunc::copysignl:
187 return checkBinaryFloatSignature(*CI, Intrinsic::copysign);
188 case LibFunc::floor:
189 case LibFunc::floorf:
190 case LibFunc::floorl:
191 return checkUnaryFloatSignature(*CI, Intrinsic::floor);
192 case LibFunc::ceil:
193 case LibFunc::ceilf:
194 case LibFunc::ceill:
195 return checkUnaryFloatSignature(*CI, Intrinsic::ceil);
196 case LibFunc::trunc:
197 case LibFunc::truncf:
198 case LibFunc::truncl:
199 return checkUnaryFloatSignature(*CI, Intrinsic::trunc);
200 case LibFunc::rint:
201 case LibFunc::rintf:
202 case LibFunc::rintl:
203 return checkUnaryFloatSignature(*CI, Intrinsic::rint);
204 case LibFunc::nearbyint:
205 case LibFunc::nearbyintf:
206 case LibFunc::nearbyintl:
207 return checkUnaryFloatSignature(*CI, Intrinsic::nearbyint);
208 case LibFunc::round:
209 case LibFunc::roundf:
210 case LibFunc::roundl:
211 return checkUnaryFloatSignature(*CI, Intrinsic::round);
212 case LibFunc::pow:
213 case LibFunc::powf:
214 case LibFunc::powl:
215 return checkBinaryFloatSignature(*CI, Intrinsic::pow);
216 }
217
218 return Intrinsic::not_intrinsic;
219 }
220
221 /// \brief Find the operand of the GEP that should be checked for consecutive
222 /// stores. This ignores trailing indices that have no effect on the final
223 /// pointer.
getGEPInductionOperand(const GetElementPtrInst * Gep)224 unsigned llvm::getGEPInductionOperand(const GetElementPtrInst *Gep) {
225 const DataLayout &DL = Gep->getModule()->getDataLayout();
226 unsigned LastOperand = Gep->getNumOperands() - 1;
227 unsigned GEPAllocSize = DL.getTypeAllocSize(
228 cast<PointerType>(Gep->getType()->getScalarType())->getElementType());
229
230 // Walk backwards and try to peel off zeros.
231 while (LastOperand > 1 &&
232 match(Gep->getOperand(LastOperand), llvm::PatternMatch::m_Zero())) {
233 // Find the type we're currently indexing into.
234 gep_type_iterator GEPTI = gep_type_begin(Gep);
235 std::advance(GEPTI, LastOperand - 1);
236
237 // If it's a type with the same allocation size as the result of the GEP we
238 // can peel off the zero index.
239 if (DL.getTypeAllocSize(*GEPTI) != GEPAllocSize)
240 break;
241 --LastOperand;
242 }
243
244 return LastOperand;
245 }
246
247 /// \brief If the argument is a GEP, then returns the operand identified by
248 /// getGEPInductionOperand. However, if there is some other non-loop-invariant
249 /// operand, it returns that instead.
stripGetElementPtr(llvm::Value * Ptr,ScalarEvolution * SE,Loop * Lp)250 llvm::Value *llvm::stripGetElementPtr(llvm::Value *Ptr, ScalarEvolution *SE,
251 Loop *Lp) {
252 GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Ptr);
253 if (!GEP)
254 return Ptr;
255
256 unsigned InductionOperand = getGEPInductionOperand(GEP);
257
258 // Check that all of the gep indices are uniform except for our induction
259 // operand.
260 for (unsigned i = 0, e = GEP->getNumOperands(); i != e; ++i)
261 if (i != InductionOperand &&
262 !SE->isLoopInvariant(SE->getSCEV(GEP->getOperand(i)), Lp))
263 return Ptr;
264 return GEP->getOperand(InductionOperand);
265 }
266
267 /// \brief If a value has only one user that is a CastInst, return it.
getUniqueCastUse(llvm::Value * Ptr,Loop * Lp,Type * Ty)268 llvm::Value *llvm::getUniqueCastUse(llvm::Value *Ptr, Loop *Lp, Type *Ty) {
269 llvm::Value *UniqueCast = nullptr;
270 for (User *U : Ptr->users()) {
271 CastInst *CI = dyn_cast<CastInst>(U);
272 if (CI && CI->getType() == Ty) {
273 if (!UniqueCast)
274 UniqueCast = CI;
275 else
276 return nullptr;
277 }
278 }
279 return UniqueCast;
280 }
281
282 /// \brief Get the stride of a pointer access in a loop. Looks for symbolic
283 /// strides "a[i*stride]". Returns the symbolic stride, or null otherwise.
getStrideFromPointer(llvm::Value * Ptr,ScalarEvolution * SE,Loop * Lp)284 llvm::Value *llvm::getStrideFromPointer(llvm::Value *Ptr, ScalarEvolution *SE,
285 Loop *Lp) {
286 const PointerType *PtrTy = dyn_cast<PointerType>(Ptr->getType());
287 if (!PtrTy || PtrTy->isAggregateType())
288 return nullptr;
289
290 // Try to remove a gep instruction to make the pointer (actually index at this
291 // point) easier analyzable. If OrigPtr is equal to Ptr we are analzying the
292 // pointer, otherwise, we are analyzing the index.
293 llvm::Value *OrigPtr = Ptr;
294
295 // The size of the pointer access.
296 int64_t PtrAccessSize = 1;
297
298 Ptr = stripGetElementPtr(Ptr, SE, Lp);
299 const SCEV *V = SE->getSCEV(Ptr);
300
301 if (Ptr != OrigPtr)
302 // Strip off casts.
303 while (const SCEVCastExpr *C = dyn_cast<SCEVCastExpr>(V))
304 V = C->getOperand();
305
306 const SCEVAddRecExpr *S = dyn_cast<SCEVAddRecExpr>(V);
307 if (!S)
308 return nullptr;
309
310 V = S->getStepRecurrence(*SE);
311 if (!V)
312 return nullptr;
313
314 // Strip off the size of access multiplication if we are still analyzing the
315 // pointer.
316 if (OrigPtr == Ptr) {
317 const DataLayout &DL = Lp->getHeader()->getModule()->getDataLayout();
318 DL.getTypeAllocSize(PtrTy->getElementType());
319 if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(V)) {
320 if (M->getOperand(0)->getSCEVType() != scConstant)
321 return nullptr;
322
323 const APInt &APStepVal =
324 cast<SCEVConstant>(M->getOperand(0))->getValue()->getValue();
325
326 // Huge step value - give up.
327 if (APStepVal.getBitWidth() > 64)
328 return nullptr;
329
330 int64_t StepVal = APStepVal.getSExtValue();
331 if (PtrAccessSize != StepVal)
332 return nullptr;
333 V = M->getOperand(1);
334 }
335 }
336
337 // Strip off casts.
338 Type *StripedOffRecurrenceCast = nullptr;
339 if (const SCEVCastExpr *C = dyn_cast<SCEVCastExpr>(V)) {
340 StripedOffRecurrenceCast = C->getType();
341 V = C->getOperand();
342 }
343
344 // Look for the loop invariant symbolic value.
345 const SCEVUnknown *U = dyn_cast<SCEVUnknown>(V);
346 if (!U)
347 return nullptr;
348
349 llvm::Value *Stride = U->getValue();
350 if (!Lp->isLoopInvariant(Stride))
351 return nullptr;
352
353 // If we have stripped off the recurrence cast we have to make sure that we
354 // return the value that is used in this loop so that we can replace it later.
355 if (StripedOffRecurrenceCast)
356 Stride = getUniqueCastUse(Stride, Lp, StripedOffRecurrenceCast);
357
358 return Stride;
359 }
360
361 /// \brief Given a vector and an element number, see if the scalar value is
362 /// already around as a register, for example if it were inserted then extracted
363 /// from the vector.
findScalarElement(llvm::Value * V,unsigned EltNo)364 llvm::Value *llvm::findScalarElement(llvm::Value *V, unsigned EltNo) {
365 assert(V->getType()->isVectorTy() && "Not looking at a vector?");
366 VectorType *VTy = cast<VectorType>(V->getType());
367 unsigned Width = VTy->getNumElements();
368 if (EltNo >= Width) // Out of range access.
369 return UndefValue::get(VTy->getElementType());
370
371 if (Constant *C = dyn_cast<Constant>(V))
372 return C->getAggregateElement(EltNo);
373
374 if (InsertElementInst *III = dyn_cast<InsertElementInst>(V)) {
375 // If this is an insert to a variable element, we don't know what it is.
376 if (!isa<ConstantInt>(III->getOperand(2)))
377 return nullptr;
378 unsigned IIElt = cast<ConstantInt>(III->getOperand(2))->getZExtValue();
379
380 // If this is an insert to the element we are looking for, return the
381 // inserted value.
382 if (EltNo == IIElt)
383 return III->getOperand(1);
384
385 // Otherwise, the insertelement doesn't modify the value, recurse on its
386 // vector input.
387 return findScalarElement(III->getOperand(0), EltNo);
388 }
389
390 if (ShuffleVectorInst *SVI = dyn_cast<ShuffleVectorInst>(V)) {
391 unsigned LHSWidth = SVI->getOperand(0)->getType()->getVectorNumElements();
392 int InEl = SVI->getMaskValue(EltNo);
393 if (InEl < 0)
394 return UndefValue::get(VTy->getElementType());
395 if (InEl < (int)LHSWidth)
396 return findScalarElement(SVI->getOperand(0), InEl);
397 return findScalarElement(SVI->getOperand(1), InEl - LHSWidth);
398 }
399
400 // Extract a value from a vector add operation with a constant zero.
401 Value *Val = nullptr; Constant *Con = nullptr;
402 if (match(V,
403 llvm::PatternMatch::m_Add(llvm::PatternMatch::m_Value(Val),
404 llvm::PatternMatch::m_Constant(Con)))) {
405 if (Constant *Elt = Con->getAggregateElement(EltNo))
406 if (Elt->isNullValue())
407 return findScalarElement(Val, EltNo);
408 }
409
410 // Otherwise, we don't know.
411 return nullptr;
412 }
413