lib/Analysis/VectorUtils.cpp

   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 #include "llvm/IR/Constants.h"
  22
  23 using namespace llvm;
  24 using namespace llvm::PatternMatch;
  25
  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) {
  31   switch (ID) {
  32   case Intrinsic::sqrt:
  33   case Intrinsic::sin:
  34   case Intrinsic::cos:
  35   case Intrinsic::exp:
  36   case Intrinsic::exp2:
  37   case Intrinsic::log:
  38   case Intrinsic::log10:
  39   case Intrinsic::log2:
  40   case Intrinsic::fabs:
  41   case Intrinsic::minnum:
  42   case Intrinsic::maxnum:
  43   case Intrinsic::copysign:
  44   case Intrinsic::floor:
  45   case Intrinsic::ceil:
  46   case Intrinsic::trunc:
  47   case Intrinsic::rint:
  48   case Intrinsic::nearbyint:
  49   case Intrinsic::round:
  50   case Intrinsic::bswap:
  51   case Intrinsic::ctpop:
  52   case Intrinsic::pow:
  53   case Intrinsic::fma:
  54   case Intrinsic::fmuladd:
  55   case Intrinsic::ctlz:
  56   case Intrinsic::cttz:
  57   case Intrinsic::powi:
  58     return true;
  59   default:
  60     return false;
  61   }
  62 }
  63
  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) {
  68   switch (ID) {
  69   case Intrinsic::ctlz:
  70   case Intrinsic::cttz:
  71   case Intrinsic::powi:
  72     return (ScalarOpdIdx == 1);
  73   default:
  74     return false;
  75   }
  76 }
  77
  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.
  86 Intrinsic::ID
  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;
  93
  94   return ValidIntrinsicID;
  95 }
  96
  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.
 105 Intrinsic::ID
 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;
 114
 115   return ValidIntrinsicID;
 116 }
 117
 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)
 128       return ID;
 129     return Intrinsic::not_intrinsic;
 130   }
 131
 132   if (!TLI)
 133     return Intrinsic::not_intrinsic;
 134
 135   LibFunc::Func Func;
 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;
 142
 143   // Otherwise check if we have a call to a function that can be turned into a
 144   // vector intrinsic.
 145   switch (Func) {
 146   default:
 147     break;
 148   case LibFunc::sin:
 149   case LibFunc::sinf:
 150   case LibFunc::sinl:
 151     return checkUnaryFloatSignature(*CI, Intrinsic::sin);
 152   case LibFunc::cos:
 153   case LibFunc::cosf:
 154   case LibFunc::cosl:
 155     return checkUnaryFloatSignature(*CI, Intrinsic::cos);
 156   case LibFunc::exp:
 157   case LibFunc::expf:
 158   case LibFunc::expl:
 159     return checkUnaryFloatSignature(*CI, Intrinsic::exp);
 160   case LibFunc::exp2:
 161   case LibFunc::exp2f:
 162   case LibFunc::exp2l:
 163     return checkUnaryFloatSignature(*CI, Intrinsic::exp2);
 164   case LibFunc::log:
 165   case LibFunc::logf:
 166   case LibFunc::logl:
 167     return checkUnaryFloatSignature(*CI, Intrinsic::log);
 168   case LibFunc::log10:
 169   case LibFunc::log10f:
 170   case LibFunc::log10l:
 171     return checkUnaryFloatSignature(*CI, Intrinsic::log10);
 172   case LibFunc::log2:
 173   case LibFunc::log2f:
 174   case LibFunc::log2l:
 175     return checkUnaryFloatSignature(*CI, Intrinsic::log2);
 176   case LibFunc::fabs:
 177   case LibFunc::fabsf:
 178   case LibFunc::fabsl:
 179     return checkUnaryFloatSignature(*CI, Intrinsic::fabs);
 180   case LibFunc::fmin:
 181   case LibFunc::fminf:
 182   case LibFunc::fminl:
 183     return checkBinaryFloatSignature(*CI, Intrinsic::minnum);
 184   case LibFunc::fmax:
 185   case LibFunc::fmaxf:
 186   case LibFunc::fmaxl:
 187     return checkBinaryFloatSignature(*CI, Intrinsic::maxnum);
 188   case LibFunc::copysign:
 189   case LibFunc::copysignf:
 190   case LibFunc::copysignl:
 191     return checkBinaryFloatSignature(*CI, Intrinsic::copysign);
 192   case LibFunc::floor:
 193   case LibFunc::floorf:
 194   case LibFunc::floorl:
 195     return checkUnaryFloatSignature(*CI, Intrinsic::floor);
 196   case LibFunc::ceil:
 197   case LibFunc::ceilf:
 198   case LibFunc::ceill:
 199     return checkUnaryFloatSignature(*CI, Intrinsic::ceil);
 200   case LibFunc::trunc:
 201   case LibFunc::truncf:
 202   case LibFunc::truncl:
 203     return checkUnaryFloatSignature(*CI, Intrinsic::trunc);
 204   case LibFunc::rint:
 205   case LibFunc::rintf:
 206   case LibFunc::rintl:
 207     return checkUnaryFloatSignature(*CI, Intrinsic::rint);
 208   case LibFunc::nearbyint:
 209   case LibFunc::nearbyintf:
 210   case LibFunc::nearbyintl:
 211     return checkUnaryFloatSignature(*CI, Intrinsic::nearbyint);
 212   case LibFunc::round:
 213   case LibFunc::roundf:
 214   case LibFunc::roundl:
 215     return checkUnaryFloatSignature(*CI, Intrinsic::round);
 216   case LibFunc::pow:
 217   case LibFunc::powf:
 218   case LibFunc::powl:
 219     return checkBinaryFloatSignature(*CI, Intrinsic::pow);
 220   }
 221
 222   return Intrinsic::not_intrinsic;
 223 }
 224
 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
 227 /// pointer.
 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());
 233
 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);
 239
 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)
 243       break;
 244     --LastOperand;
 245   }
 246
 247   return LastOperand;
 248 }
 249
 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);
 255   if (!GEP)
 256     return Ptr;
 257
 258   unsigned InductionOperand = getGEPInductionOperand(GEP);
 259
 260   // Check that all of the gep indices are uniform except for our induction
 261   // operand.
 262   for (unsigned i = 0, e = GEP->getNumOperands(); i != e; ++i)
 263     if (i != InductionOperand &&
 264         !SE->isLoopInvariant(SE->getSCEV(GEP->getOperand(i)), Lp))
 265       return Ptr;
 266   return GEP->getOperand(InductionOperand);
 267 }
 268
 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) {
 275       if (!UniqueCast)
 276         UniqueCast = CI;
 277       else
 278         return nullptr;
 279     }
 280   }
 281   return UniqueCast;
 282 }
 283
 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())
 289     return nullptr;
 290
 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;
 295
 296   // The size of the pointer access.
 297   int64_t PtrAccessSize = 1;
 298
 299   Ptr = stripGetElementPtr(Ptr, SE, Lp);
 300   const SCEV *V = SE->getSCEV(Ptr);
 301
 302   if (Ptr != OrigPtr)
 303     // Strip off casts.
 304     while (const SCEVCastExpr *C = dyn_cast<SCEVCastExpr>(V))
 305       V = C->getOperand();
 306
 307   const SCEVAddRecExpr *S = dyn_cast<SCEVAddRecExpr>(V);
 308   if (!S)
 309     return nullptr;
 310
 311   V = S->getStepRecurrence(*SE);
 312   if (!V)
 313     return nullptr;
 314
 315   // Strip off the size of access multiplication if we are still analyzing the
 316   // pointer.
 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)
 322         return nullptr;
 323
 324       const APInt &APStepVal =
 325           cast<SCEVConstant>(M->getOperand(0))->getValue()->getValue();
 326
 327       // Huge step value - give up.
 328       if (APStepVal.getBitWidth() > 64)
 329         return nullptr;
 330
 331       int64_t StepVal = APStepVal.getSExtValue();
 332       if (PtrAccessSize != StepVal)
 333         return nullptr;
 334       V = M->getOperand(1);
 335     }
 336   }
 337
 338   // Strip off casts.
 339   Type *StripedOffRecurrenceCast = nullptr;
 340   if (const SCEVCastExpr *C = dyn_cast<SCEVCastExpr>(V)) {
 341     StripedOffRecurrenceCast = C->getType();
 342     V = C->getOperand();
 343   }
 344
 345   // Look for the loop invariant symbolic value.
 346   const SCEVUnknown *U = dyn_cast<SCEVUnknown>(V);
 347   if (!U)
 348     return nullptr;
 349
 350   Value *Stride = U->getValue();
 351   if (!Lp->isLoopInvariant(Stride))
 352     return nullptr;
 353
 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);
 358
 359   return Stride;
 360 }
 361
 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
 364 /// from the vector.
 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());
 371
 372   if (Constant *C = dyn_cast<Constant>(V))
 373     return C->getAggregateElement(EltNo);
 374
 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)))
 378       return nullptr;
 379     unsigned IIElt = cast<ConstantInt>(III->getOperand(2))->getZExtValue();
 380
 381     // If this is an insert to the element we are looking for, return the
 382     // inserted value.
 383     if (EltNo == IIElt)
 384       return III->getOperand(1);
 385
 386     // Otherwise, the insertelement doesn't modify the value, recurse on its
 387     // vector input.
 388     return findScalarElement(III->getOperand(0), EltNo);
 389   }
 390
 391   if (ShuffleVectorInst *SVI = dyn_cast<ShuffleVectorInst>(V)) {
 392     unsigned LHSWidth = SVI->getOperand(0)->getType()->getVectorNumElements();
 393     int InEl = SVI->getMaskValue(EltNo);
 394     if (InEl < 0)
 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);
 399   }
 400
 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);
 407
 408   // Otherwise, we don't know.
 409   return nullptr;
 410 }
 411
 412 /// \brief Get splat value if the input is a splat vector or return nullptr.
 413 /// This function is not fully general. It checks only 2 cases:
 414 /// the input value is (1) a splat constants vector or (2) a sequence
 415 /// of instructions that broadcast a single value into a vector.
 416 ///
 417 llvm::Value *llvm::getSplatValue(Value *V) {
 418   if (auto *CV = dyn_cast<ConstantDataVector>(V))
 419     return CV->getSplatValue();
 420
 421   auto *ShuffleInst = dyn_cast<ShuffleVectorInst>(V);
 422   if (!ShuffleInst)
 423     return nullptr;
 424   // All-zero (or undef) shuffle mask elements.
 425   for (int MaskElt : ShuffleInst->getShuffleMask())
 426     if (MaskElt != 0 && MaskElt != -1)
 427       return nullptr;
 428   // The first shuffle source is 'insertelement' with index 0.
 429   auto *InsertEltInst =
 430     dyn_cast<InsertElementInst>(ShuffleInst->getOperand(0));
 431   if (!InsertEltInst || !isa<ConstantInt>(InsertEltInst->getOperand(2)) ||
 432       !cast<ConstantInt>(InsertEltInst->getOperand(2))->isNullValue())
 433     return nullptr;
 434
 435   return InsertEltInst->getOperand(1);
 436 }