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/ADT/EquivalenceClasses.h" 15 #include "llvm/Analysis/DemandedBits.h" 16 #include "llvm/Analysis/LoopInfo.h" 17 #include "llvm/Analysis/ScalarEvolutionExpressions.h" 18 #include "llvm/Analysis/ScalarEvolution.h" 19 #include "llvm/Analysis/TargetTransformInfo.h" 20 #include "llvm/Analysis/VectorUtils.h" 21 #include "llvm/IR/GetElementPtrTypeIterator.h" 22 #include "llvm/IR/PatternMatch.h" 23 #include "llvm/IR/Value.h" 24 #include "llvm/IR/Constants.h" 25 26 using namespace llvm; 27 using namespace llvm::PatternMatch; 28 29 /// \brief Identify if the intrinsic is trivially vectorizable. 30 /// This method returns true if the intrinsic's argument types are all 31 /// scalars for the scalar form of the intrinsic and all vectors for 32 /// the vector form of the intrinsic. 33 bool llvm::isTriviallyVectorizable(Intrinsic::ID ID) { 34 switch (ID) { 35 case Intrinsic::sqrt: 36 case Intrinsic::sin: 37 case Intrinsic::cos: 38 case Intrinsic::exp: 39 case Intrinsic::exp2: 40 case Intrinsic::log: 41 case Intrinsic::log10: 42 case Intrinsic::log2: 43 case Intrinsic::fabs: 44 case Intrinsic::minnum: 45 case Intrinsic::maxnum: 46 case Intrinsic::copysign: 47 case Intrinsic::floor: 48 case Intrinsic::ceil: 49 case Intrinsic::trunc: 50 case Intrinsic::rint: 51 case Intrinsic::nearbyint: 52 case Intrinsic::round: 53 case Intrinsic::bswap: 54 case Intrinsic::ctpop: 55 case Intrinsic::pow: 56 case Intrinsic::fma: 57 case Intrinsic::fmuladd: 58 case Intrinsic::ctlz: 59 case Intrinsic::cttz: 60 case Intrinsic::powi: 61 return true; 62 default: 63 return false; 64 } 65 } 66 67 /// \brief Identifies if the intrinsic has a scalar operand. It check for 68 /// ctlz,cttz and powi special intrinsics whose argument is scalar. 69 bool llvm::hasVectorInstrinsicScalarOpd(Intrinsic::ID ID, 70 unsigned ScalarOpdIdx) { 71 switch (ID) { 72 case Intrinsic::ctlz: 73 case Intrinsic::cttz: 74 case Intrinsic::powi: 75 return (ScalarOpdIdx == 1); 76 default: 77 return false; 78 } 79 } 80 81 /// \brief Check call has a unary float signature 82 /// It checks following: 83 /// a) call should have a single argument 84 /// b) argument type should be floating point type 85 /// c) call instruction type and argument type should be same 86 /// d) call should only reads memory. 87 /// If all these condition is met then return ValidIntrinsicID 88 /// else return not_intrinsic. 89 Intrinsic::ID 90 llvm::checkUnaryFloatSignature(const CallInst &I, 91 Intrinsic::ID ValidIntrinsicID) { 92 if (I.getNumArgOperands() != 1 || 93 !I.getArgOperand(0)->getType()->isFloatingPointTy() || 94 I.getType() != I.getArgOperand(0)->getType() || !I.onlyReadsMemory()) 95 return Intrinsic::not_intrinsic; 96 97 return ValidIntrinsicID; 98 } 99 100 /// \brief Check call has a binary float signature 101 /// It checks following: 102 /// a) call should have 2 arguments. 103 /// b) arguments type should be floating point type 104 /// c) call instruction type and arguments type should be same 105 /// d) call should only reads memory. 106 /// If all these condition is met then return ValidIntrinsicID 107 /// else return not_intrinsic. 108 Intrinsic::ID 109 llvm::checkBinaryFloatSignature(const CallInst &I, 110 Intrinsic::ID ValidIntrinsicID) { 111 if (I.getNumArgOperands() != 2 || 112 !I.getArgOperand(0)->getType()->isFloatingPointTy() || 113 !I.getArgOperand(1)->getType()->isFloatingPointTy() || 114 I.getType() != I.getArgOperand(0)->getType() || 115 I.getType() != I.getArgOperand(1)->getType() || !I.onlyReadsMemory()) 116 return Intrinsic::not_intrinsic; 117 118 return ValidIntrinsicID; 119 } 120 121 /// \brief Returns intrinsic ID for call. 122 /// For the input call instruction it finds mapping intrinsic and returns 123 /// its ID, in case it does not found it return not_intrinsic. 124 Intrinsic::ID llvm::getIntrinsicIDForCall(CallInst *CI, 125 const TargetLibraryInfo *TLI) { 126 // If we have an intrinsic call, check if it is trivially vectorizable. 127 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(CI)) { 128 Intrinsic::ID ID = II->getIntrinsicID(); 129 if (isTriviallyVectorizable(ID) || ID == Intrinsic::lifetime_start || 130 ID == Intrinsic::lifetime_end || ID == Intrinsic::assume) 131 return ID; 132 return Intrinsic::not_intrinsic; 133 } 134 135 if (!TLI) 136 return Intrinsic::not_intrinsic; 137 138 LibFunc::Func Func; 139 Function *F = CI->getCalledFunction(); 140 // We're going to make assumptions on the semantics of the functions, check 141 // that the target knows that it's available in this environment and it does 142 // not have local linkage. 143 if (!F || F->hasLocalLinkage() || !TLI->getLibFunc(F->getName(), Func)) 144 return Intrinsic::not_intrinsic; 145 146 // Otherwise check if we have a call to a function that can be turned into a 147 // vector intrinsic. 148 switch (Func) { 149 default: 150 break; 151 case LibFunc::sin: 152 case LibFunc::sinf: 153 case LibFunc::sinl: 154 return checkUnaryFloatSignature(*CI, Intrinsic::sin); 155 case LibFunc::cos: 156 case LibFunc::cosf: 157 case LibFunc::cosl: 158 return checkUnaryFloatSignature(*CI, Intrinsic::cos); 159 case LibFunc::exp: 160 case LibFunc::expf: 161 case LibFunc::expl: 162 return checkUnaryFloatSignature(*CI, Intrinsic::exp); 163 case LibFunc::exp2: 164 case LibFunc::exp2f: 165 case LibFunc::exp2l: 166 return checkUnaryFloatSignature(*CI, Intrinsic::exp2); 167 case LibFunc::log: 168 case LibFunc::logf: 169 case LibFunc::logl: 170 return checkUnaryFloatSignature(*CI, Intrinsic::log); 171 case LibFunc::log10: 172 case LibFunc::log10f: 173 case LibFunc::log10l: 174 return checkUnaryFloatSignature(*CI, Intrinsic::log10); 175 case LibFunc::log2: 176 case LibFunc::log2f: 177 case LibFunc::log2l: 178 return checkUnaryFloatSignature(*CI, Intrinsic::log2); 179 case LibFunc::fabs: 180 case LibFunc::fabsf: 181 case LibFunc::fabsl: 182 return checkUnaryFloatSignature(*CI, Intrinsic::fabs); 183 case LibFunc::fmin: 184 case LibFunc::fminf: 185 case LibFunc::fminl: 186 return checkBinaryFloatSignature(*CI, Intrinsic::minnum); 187 case LibFunc::fmax: 188 case LibFunc::fmaxf: 189 case LibFunc::fmaxl: 190 return checkBinaryFloatSignature(*CI, Intrinsic::maxnum); 191 case LibFunc::copysign: 192 case LibFunc::copysignf: 193 case LibFunc::copysignl: 194 return checkBinaryFloatSignature(*CI, Intrinsic::copysign); 195 case LibFunc::floor: 196 case LibFunc::floorf: 197 case LibFunc::floorl: 198 return checkUnaryFloatSignature(*CI, Intrinsic::floor); 199 case LibFunc::ceil: 200 case LibFunc::ceilf: 201 case LibFunc::ceill: 202 return checkUnaryFloatSignature(*CI, Intrinsic::ceil); 203 case LibFunc::trunc: 204 case LibFunc::truncf: 205 case LibFunc::truncl: 206 return checkUnaryFloatSignature(*CI, Intrinsic::trunc); 207 case LibFunc::rint: 208 case LibFunc::rintf: 209 case LibFunc::rintl: 210 return checkUnaryFloatSignature(*CI, Intrinsic::rint); 211 case LibFunc::nearbyint: 212 case LibFunc::nearbyintf: 213 case LibFunc::nearbyintl: 214 return checkUnaryFloatSignature(*CI, Intrinsic::nearbyint); 215 case LibFunc::round: 216 case LibFunc::roundf: 217 case LibFunc::roundl: 218 return checkUnaryFloatSignature(*CI, Intrinsic::round); 219 case LibFunc::pow: 220 case LibFunc::powf: 221 case LibFunc::powl: 222 return checkBinaryFloatSignature(*CI, Intrinsic::pow); 223 } 224 225 return Intrinsic::not_intrinsic; 226 } 227 228 /// \brief Find the operand of the GEP that should be checked for consecutive 229 /// stores. This ignores trailing indices that have no effect on the final 230 /// pointer. 231 unsigned llvm::getGEPInductionOperand(const GetElementPtrInst *Gep) { 232 const DataLayout &DL = Gep->getModule()->getDataLayout(); 233 unsigned LastOperand = Gep->getNumOperands() - 1; 234 unsigned GEPAllocSize = DL.getTypeAllocSize( 235 cast<PointerType>(Gep->getType()->getScalarType())->getElementType()); 236 237 // Walk backwards and try to peel off zeros. 238 while (LastOperand > 1 && match(Gep->getOperand(LastOperand), m_Zero())) { 239 // Find the type we're currently indexing into. 240 gep_type_iterator GEPTI = gep_type_begin(Gep); 241 std::advance(GEPTI, LastOperand - 1); 242 243 // If it's a type with the same allocation size as the result of the GEP we 244 // can peel off the zero index. 245 if (DL.getTypeAllocSize(*GEPTI) != GEPAllocSize) 246 break; 247 --LastOperand; 248 } 249 250 return LastOperand; 251 } 252 253 /// \brief If the argument is a GEP, then returns the operand identified by 254 /// getGEPInductionOperand. However, if there is some other non-loop-invariant 255 /// operand, it returns that instead. 256 Value *llvm::stripGetElementPtr(Value *Ptr, ScalarEvolution *SE, Loop *Lp) { 257 GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Ptr); 258 if (!GEP) 259 return Ptr; 260 261 unsigned InductionOperand = getGEPInductionOperand(GEP); 262 263 // Check that all of the gep indices are uniform except for our induction 264 // operand. 265 for (unsigned i = 0, e = GEP->getNumOperands(); i != e; ++i) 266 if (i != InductionOperand && 267 !SE->isLoopInvariant(SE->getSCEV(GEP->getOperand(i)), Lp)) 268 return Ptr; 269 return GEP->getOperand(InductionOperand); 270 } 271 272 /// \brief If a value has only one user that is a CastInst, return it. 273 Value *llvm::getUniqueCastUse(Value *Ptr, Loop *Lp, Type *Ty) { 274 Value *UniqueCast = nullptr; 275 for (User *U : Ptr->users()) { 276 CastInst *CI = dyn_cast<CastInst>(U); 277 if (CI && CI->getType() == Ty) { 278 if (!UniqueCast) 279 UniqueCast = CI; 280 else 281 return nullptr; 282 } 283 } 284 return UniqueCast; 285 } 286 287 /// \brief Get the stride of a pointer access in a loop. Looks for symbolic 288 /// strides "a[i*stride]". Returns the symbolic stride, or null otherwise. 289 Value *llvm::getStrideFromPointer(Value *Ptr, ScalarEvolution *SE, Loop *Lp) { 290 auto *PtrTy = dyn_cast<PointerType>(Ptr->getType()); 291 if (!PtrTy || PtrTy->isAggregateType()) 292 return nullptr; 293 294 // Try to remove a gep instruction to make the pointer (actually index at this 295 // point) easier analyzable. If OrigPtr is equal to Ptr we are analzying the 296 // pointer, otherwise, we are analyzing the index. 297 Value *OrigPtr = Ptr; 298 299 // The size of the pointer access. 300 int64_t PtrAccessSize = 1; 301 302 Ptr = stripGetElementPtr(Ptr, SE, Lp); 303 const SCEV *V = SE->getSCEV(Ptr); 304 305 if (Ptr != OrigPtr) 306 // Strip off casts. 307 while (const SCEVCastExpr *C = dyn_cast<SCEVCastExpr>(V)) 308 V = C->getOperand(); 309 310 const SCEVAddRecExpr *S = dyn_cast<SCEVAddRecExpr>(V); 311 if (!S) 312 return nullptr; 313 314 V = S->getStepRecurrence(*SE); 315 if (!V) 316 return nullptr; 317 318 // Strip off the size of access multiplication if we are still analyzing the 319 // pointer. 320 if (OrigPtr == Ptr) { 321 const DataLayout &DL = Lp->getHeader()->getModule()->getDataLayout(); 322 DL.getTypeAllocSize(PtrTy->getElementType()); 323 if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(V)) { 324 if (M->getOperand(0)->getSCEVType() != scConstant) 325 return nullptr; 326 327 const APInt &APStepVal = cast<SCEVConstant>(M->getOperand(0))->getAPInt(); 328 329 // Huge step value - give up. 330 if (APStepVal.getBitWidth() > 64) 331 return nullptr; 332 333 int64_t StepVal = APStepVal.getSExtValue(); 334 if (PtrAccessSize != StepVal) 335 return nullptr; 336 V = M->getOperand(1); 337 } 338 } 339 340 // Strip off casts. 341 Type *StripedOffRecurrenceCast = nullptr; 342 if (const SCEVCastExpr *C = dyn_cast<SCEVCastExpr>(V)) { 343 StripedOffRecurrenceCast = C->getType(); 344 V = C->getOperand(); 345 } 346 347 // Look for the loop invariant symbolic value. 348 const SCEVUnknown *U = dyn_cast<SCEVUnknown>(V); 349 if (!U) 350 return nullptr; 351 352 Value *Stride = U->getValue(); 353 if (!Lp->isLoopInvariant(Stride)) 354 return nullptr; 355 356 // If we have stripped off the recurrence cast we have to make sure that we 357 // return the value that is used in this loop so that we can replace it later. 358 if (StripedOffRecurrenceCast) 359 Stride = getUniqueCastUse(Stride, Lp, StripedOffRecurrenceCast); 360 361 return Stride; 362 } 363 364 /// \brief Given a vector and an element number, see if the scalar value is 365 /// already around as a register, for example if it were inserted then extracted 366 /// from the vector. 367 Value *llvm::findScalarElement(Value *V, unsigned EltNo) { 368 assert(V->getType()->isVectorTy() && "Not looking at a vector?"); 369 VectorType *VTy = cast<VectorType>(V->getType()); 370 unsigned Width = VTy->getNumElements(); 371 if (EltNo >= Width) // Out of range access. 372 return UndefValue::get(VTy->getElementType()); 373 374 if (Constant *C = dyn_cast<Constant>(V)) 375 return C->getAggregateElement(EltNo); 376 377 if (InsertElementInst *III = dyn_cast<InsertElementInst>(V)) { 378 // If this is an insert to a variable element, we don't know what it is. 379 if (!isa<ConstantInt>(III->getOperand(2))) 380 return nullptr; 381 unsigned IIElt = cast<ConstantInt>(III->getOperand(2))->getZExtValue(); 382 383 // If this is an insert to the element we are looking for, return the 384 // inserted value. 385 if (EltNo == IIElt) 386 return III->getOperand(1); 387 388 // Otherwise, the insertelement doesn't modify the value, recurse on its 389 // vector input. 390 return findScalarElement(III->getOperand(0), EltNo); 391 } 392 393 if (ShuffleVectorInst *SVI = dyn_cast<ShuffleVectorInst>(V)) { 394 unsigned LHSWidth = SVI->getOperand(0)->getType()->getVectorNumElements(); 395 int InEl = SVI->getMaskValue(EltNo); 396 if (InEl < 0) 397 return UndefValue::get(VTy->getElementType()); 398 if (InEl < (int)LHSWidth) 399 return findScalarElement(SVI->getOperand(0), InEl); 400 return findScalarElement(SVI->getOperand(1), InEl - LHSWidth); 401 } 402 403 // Extract a value from a vector add operation with a constant zero. 404 Value *Val = nullptr; Constant *Con = nullptr; 405 if (match(V, m_Add(m_Value(Val), m_Constant(Con)))) 406 if (Constant *Elt = Con->getAggregateElement(EltNo)) 407 if (Elt->isNullValue()) 408 return findScalarElement(Val, EltNo); 409 410 // Otherwise, we don't know. 411 return nullptr; 412 } 413 414 /// \brief Get splat value if the input is a splat vector or return nullptr. 415 /// This function is not fully general. It checks only 2 cases: 416 /// the input value is (1) a splat constants vector or (2) a sequence 417 /// of instructions that broadcast a single value into a vector. 418 /// 419 const llvm::Value *llvm::getSplatValue(const Value *V) { 420 421 if (auto *C = dyn_cast<Constant>(V)) 422 if (isa<VectorType>(V->getType())) 423 return C->getSplatValue(); 424 425 auto *ShuffleInst = dyn_cast<ShuffleVectorInst>(V); 426 if (!ShuffleInst) 427 return nullptr; 428 // All-zero (or undef) shuffle mask elements. 429 for (int MaskElt : ShuffleInst->getShuffleMask()) 430 if (MaskElt != 0 && MaskElt != -1) 431 return nullptr; 432 // The first shuffle source is 'insertelement' with index 0. 433 auto *InsertEltInst = 434 dyn_cast<InsertElementInst>(ShuffleInst->getOperand(0)); 435 if (!InsertEltInst || !isa<ConstantInt>(InsertEltInst->getOperand(2)) || 436 !cast<ConstantInt>(InsertEltInst->getOperand(2))->isNullValue()) 437 return nullptr; 438 439 return InsertEltInst->getOperand(1); 440 } 441 442 MapVector<Instruction *, uint64_t> 443 llvm::computeMinimumValueSizes(ArrayRef<BasicBlock *> Blocks, DemandedBits &DB, 444 const TargetTransformInfo *TTI) { 445 446 // DemandedBits will give us every value's live-out bits. But we want 447 // to ensure no extra casts would need to be inserted, so every DAG 448 // of connected values must have the same minimum bitwidth. 449 EquivalenceClasses<Value *> ECs; 450 SmallVector<Value *, 16> Worklist; 451 SmallPtrSet<Value *, 4> Roots; 452 SmallPtrSet<Value *, 16> Visited; 453 DenseMap<Value *, uint64_t> DBits; 454 SmallPtrSet<Instruction *, 4> InstructionSet; 455 MapVector<Instruction *, uint64_t> MinBWs; 456 457 // Determine the roots. We work bottom-up, from truncs or icmps. 458 bool SeenExtFromIllegalType = false; 459 for (auto *BB : Blocks) 460 for (auto &I : *BB) { 461 InstructionSet.insert(&I); 462 463 if (TTI && (isa<ZExtInst>(&I) || isa<SExtInst>(&I)) && 464 !TTI->isTypeLegal(I.getOperand(0)->getType())) 465 SeenExtFromIllegalType = true; 466 467 // Only deal with non-vector integers up to 64-bits wide. 468 if ((isa<TruncInst>(&I) || isa<ICmpInst>(&I)) && 469 !I.getType()->isVectorTy() && 470 I.getOperand(0)->getType()->getScalarSizeInBits() <= 64) { 471 // Don't make work for ourselves. If we know the loaded type is legal, 472 // don't add it to the worklist. 473 if (TTI && isa<TruncInst>(&I) && TTI->isTypeLegal(I.getType())) 474 continue; 475 476 Worklist.push_back(&I); 477 Roots.insert(&I); 478 } 479 } 480 // Early exit. 481 if (Worklist.empty() || (TTI && !SeenExtFromIllegalType)) 482 return MinBWs; 483 484 // Now proceed breadth-first, unioning values together. 485 while (!Worklist.empty()) { 486 Value *Val = Worklist.pop_back_val(); 487 Value *Leader = ECs.getOrInsertLeaderValue(Val); 488 489 if (Visited.count(Val)) 490 continue; 491 Visited.insert(Val); 492 493 // Non-instructions terminate a chain successfully. 494 if (!isa<Instruction>(Val)) 495 continue; 496 Instruction *I = cast<Instruction>(Val); 497 498 // If we encounter a type that is larger than 64 bits, we can't represent 499 // it so bail out. 500 if (DB.getDemandedBits(I).getBitWidth() > 64) 501 return MapVector<Instruction *, uint64_t>(); 502 503 uint64_t V = DB.getDemandedBits(I).getZExtValue(); 504 DBits[Leader] |= V; 505 506 // Casts, loads and instructions outside of our range terminate a chain 507 // successfully. 508 if (isa<SExtInst>(I) || isa<ZExtInst>(I) || isa<LoadInst>(I) || 509 !InstructionSet.count(I)) 510 continue; 511 512 // Unsafe casts terminate a chain unsuccessfully. We can't do anything 513 // useful with bitcasts, ptrtoints or inttoptrs and it'd be unsafe to 514 // transform anything that relies on them. 515 if (isa<BitCastInst>(I) || isa<PtrToIntInst>(I) || isa<IntToPtrInst>(I) || 516 !I->getType()->isIntegerTy()) { 517 DBits[Leader] |= ~0ULL; 518 continue; 519 } 520 521 // We don't modify the types of PHIs. Reductions will already have been 522 // truncated if possible, and inductions' sizes will have been chosen by 523 // indvars. 524 if (isa<PHINode>(I)) 525 continue; 526 527 if (DBits[Leader] == ~0ULL) 528 // All bits demanded, no point continuing. 529 continue; 530 531 for (Value *O : cast<User>(I)->operands()) { 532 ECs.unionSets(Leader, O); 533 Worklist.push_back(O); 534 } 535 } 536 537 // Now we've discovered all values, walk them to see if there are 538 // any users we didn't see. If there are, we can't optimize that 539 // chain. 540 for (auto &I : DBits) 541 for (auto *U : I.first->users()) 542 if (U->getType()->isIntegerTy() && DBits.count(U) == 0) 543 DBits[ECs.getOrInsertLeaderValue(I.first)] |= ~0ULL; 544 545 for (auto I = ECs.begin(), E = ECs.end(); I != E; ++I) { 546 uint64_t LeaderDemandedBits = 0; 547 for (auto MI = ECs.member_begin(I), ME = ECs.member_end(); MI != ME; ++MI) 548 LeaderDemandedBits |= DBits[*MI]; 549 550 uint64_t MinBW = (sizeof(LeaderDemandedBits) * 8) - 551 llvm::countLeadingZeros(LeaderDemandedBits); 552 // Round up to a power of 2 553 if (!isPowerOf2_64((uint64_t)MinBW)) 554 MinBW = NextPowerOf2(MinBW); 555 for (auto MI = ECs.member_begin(I), ME = ECs.member_end(); MI != ME; ++MI) { 556 if (!isa<Instruction>(*MI)) 557 continue; 558 Type *Ty = (*MI)->getType(); 559 if (Roots.count(*MI)) 560 Ty = cast<Instruction>(*MI)->getOperand(0)->getType(); 561 if (MinBW < Ty->getScalarSizeInBits()) 562 MinBWs[cast<Instruction>(*MI)] = MinBW; 563 } 564 } 565 566 return MinBWs; 567 } 568
