1 //===- SLPVectorizer.cpp - A bottom up SLP Vectorizer ---------------------===// 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 // This pass implements the Bottom Up SLP vectorizer. It detects consecutive 10 // stores that can be put together into vector-stores. Next, it attempts to 11 // construct vectorizable tree using the use-def chains. If a profitable tree 12 // was found, the SLP vectorizer performs vectorization on the tree. 13 // 14 // The pass is inspired by the work described in the paper: 15 // "Loop-Aware SLP in GCC" by Ira Rosen, Dorit Nuzman, Ayal Zaks. 16 // 17 //===----------------------------------------------------------------------===// 18 #include "llvm/Transforms/Vectorize/SLPVectorizer.h" 19 #include "llvm/ADT/Optional.h" 20 #include "llvm/ADT/PostOrderIterator.h" 21 #include "llvm/ADT/SetVector.h" 22 #include "llvm/ADT/Statistic.h" 23 #include "llvm/Analysis/CodeMetrics.h" 24 #include "llvm/Analysis/GlobalsModRef.h" 25 #include "llvm/Analysis/LoopAccessAnalysis.h" 26 #include "llvm/Analysis/ScalarEvolutionExpressions.h" 27 #include "llvm/Analysis/ValueTracking.h" 28 #include "llvm/Analysis/VectorUtils.h" 29 #include "llvm/IR/DataLayout.h" 30 #include "llvm/IR/Dominators.h" 31 #include "llvm/IR/IRBuilder.h" 32 #include "llvm/IR/Instructions.h" 33 #include "llvm/IR/IntrinsicInst.h" 34 #include "llvm/IR/Module.h" 35 #include "llvm/IR/NoFolder.h" 36 #include "llvm/IR/Type.h" 37 #include "llvm/IR/Value.h" 38 #include "llvm/IR/Verifier.h" 39 #include "llvm/Pass.h" 40 #include "llvm/Support/CommandLine.h" 41 #include "llvm/Support/Debug.h" 42 #include "llvm/Support/raw_ostream.h" 43 #include "llvm/Transforms/Vectorize.h" 44 #include <algorithm> 45 #include <memory> 46 47 using namespace llvm; 48 using namespace slpvectorizer; 49 50 #define SV_NAME "slp-vectorizer" 51 #define DEBUG_TYPE "SLP" 52 53 STATISTIC(NumVectorInstructions, "Number of vector instructions generated"); 54 55 static cl::opt<int> 56 SLPCostThreshold("slp-threshold", cl::init(0), cl::Hidden, 57 cl::desc("Only vectorize if you gain more than this " 58 "number ")); 59 60 static cl::opt<bool> 61 ShouldVectorizeHor("slp-vectorize-hor", cl::init(true), cl::Hidden, 62 cl::desc("Attempt to vectorize horizontal reductions")); 63 64 static cl::opt<bool> ShouldStartVectorizeHorAtStore( 65 "slp-vectorize-hor-store", cl::init(false), cl::Hidden, 66 cl::desc( 67 "Attempt to vectorize horizontal reductions feeding into a store")); 68 69 static cl::opt<int> 70 MaxVectorRegSizeOption("slp-max-reg-size", cl::init(128), cl::Hidden, 71 cl::desc("Attempt to vectorize for this register size in bits")); 72 73 /// Limits the size of scheduling regions in a block. 74 /// It avoid long compile times for _very_ large blocks where vector 75 /// instructions are spread over a wide range. 76 /// This limit is way higher than needed by real-world functions. 77 static cl::opt<int> 78 ScheduleRegionSizeBudget("slp-schedule-budget", cl::init(100000), cl::Hidden, 79 cl::desc("Limit the size of the SLP scheduling region per block")); 80 81 static cl::opt<int> MinVectorRegSizeOption( 82 "slp-min-reg-size", cl::init(128), cl::Hidden, 83 cl::desc("Attempt to vectorize for this register size in bits")); 84 85 // FIXME: Set this via cl::opt to allow overriding. 86 static const unsigned RecursionMaxDepth = 12; 87 88 // Limit the number of alias checks. The limit is chosen so that 89 // it has no negative effect on the llvm benchmarks. 90 static const unsigned AliasedCheckLimit = 10; 91 92 // Another limit for the alias checks: The maximum distance between load/store 93 // instructions where alias checks are done. 94 // This limit is useful for very large basic blocks. 95 static const unsigned MaxMemDepDistance = 160; 96 97 /// If the ScheduleRegionSizeBudget is exhausted, we allow small scheduling 98 /// regions to be handled. 99 static const int MinScheduleRegionSize = 16; 100 101 /// \brief Predicate for the element types that the SLP vectorizer supports. 102 /// 103 /// The most important thing to filter here are types which are invalid in LLVM 104 /// vectors. We also filter target specific types which have absolutely no 105 /// meaningful vectorization path such as x86_fp80 and ppc_f128. This just 106 /// avoids spending time checking the cost model and realizing that they will 107 /// be inevitably scalarized. 108 static bool isValidElementType(Type *Ty) { 109 return VectorType::isValidElementType(Ty) && !Ty->isX86_FP80Ty() && 110 !Ty->isPPC_FP128Ty(); 111 } 112 113 /// \returns the parent basic block if all of the instructions in \p VL 114 /// are in the same block or null otherwise. 115 static BasicBlock *getSameBlock(ArrayRef<Value *> VL) { 116 Instruction *I0 = dyn_cast<Instruction>(VL[0]); 117 if (!I0) 118 return nullptr; 119 BasicBlock *BB = I0->getParent(); 120 for (int i = 1, e = VL.size(); i < e; i++) { 121 Instruction *I = dyn_cast<Instruction>(VL[i]); 122 if (!I) 123 return nullptr; 124 125 if (BB != I->getParent()) 126 return nullptr; 127 } 128 return BB; 129 } 130 131 /// \returns True if all of the values in \p VL are constants. 132 static bool allConstant(ArrayRef<Value *> VL) { 133 for (Value *i : VL) 134 if (!isa<Constant>(i)) 135 return false; 136 return true; 137 } 138 139 /// \returns True if all of the values in \p VL are identical. 140 static bool isSplat(ArrayRef<Value *> VL) { 141 for (unsigned i = 1, e = VL.size(); i < e; ++i) 142 if (VL[i] != VL[0]) 143 return false; 144 return true; 145 } 146 147 ///\returns Opcode that can be clubbed with \p Op to create an alternate 148 /// sequence which can later be merged as a ShuffleVector instruction. 149 static unsigned getAltOpcode(unsigned Op) { 150 switch (Op) { 151 case Instruction::FAdd: 152 return Instruction::FSub; 153 case Instruction::FSub: 154 return Instruction::FAdd; 155 case Instruction::Add: 156 return Instruction::Sub; 157 case Instruction::Sub: 158 return Instruction::Add; 159 default: 160 return 0; 161 } 162 } 163 164 ///\returns bool representing if Opcode \p Op can be part 165 /// of an alternate sequence which can later be merged as 166 /// a ShuffleVector instruction. 167 static bool canCombineAsAltInst(unsigned Op) { 168 return Op == Instruction::FAdd || Op == Instruction::FSub || 169 Op == Instruction::Sub || Op == Instruction::Add; 170 } 171 172 /// \returns ShuffleVector instruction if instructions in \p VL have 173 /// alternate fadd,fsub / fsub,fadd/add,sub/sub,add sequence. 174 /// (i.e. e.g. opcodes of fadd,fsub,fadd,fsub...) 175 static unsigned isAltInst(ArrayRef<Value *> VL) { 176 Instruction *I0 = dyn_cast<Instruction>(VL[0]); 177 unsigned Opcode = I0->getOpcode(); 178 unsigned AltOpcode = getAltOpcode(Opcode); 179 for (int i = 1, e = VL.size(); i < e; i++) { 180 Instruction *I = dyn_cast<Instruction>(VL[i]); 181 if (!I || I->getOpcode() != ((i & 1) ? AltOpcode : Opcode)) 182 return 0; 183 } 184 return Instruction::ShuffleVector; 185 } 186 187 /// \returns The opcode if all of the Instructions in \p VL have the same 188 /// opcode, or zero. 189 static unsigned getSameOpcode(ArrayRef<Value *> VL) { 190 Instruction *I0 = dyn_cast<Instruction>(VL[0]); 191 if (!I0) 192 return 0; 193 unsigned Opcode = I0->getOpcode(); 194 for (int i = 1, e = VL.size(); i < e; i++) { 195 Instruction *I = dyn_cast<Instruction>(VL[i]); 196 if (!I || Opcode != I->getOpcode()) { 197 if (canCombineAsAltInst(Opcode) && i == 1) 198 return isAltInst(VL); 199 return 0; 200 } 201 } 202 return Opcode; 203 } 204 205 /// Get the intersection (logical and) of all of the potential IR flags 206 /// of each scalar operation (VL) that will be converted into a vector (I). 207 /// Flag set: NSW, NUW, exact, and all of fast-math. 208 static void propagateIRFlags(Value *I, ArrayRef<Value *> VL) { 209 if (auto *VecOp = dyn_cast<BinaryOperator>(I)) { 210 if (auto *Intersection = dyn_cast<BinaryOperator>(VL[0])) { 211 // Intersection is initialized to the 0th scalar, 212 // so start counting from index '1'. 213 for (int i = 1, e = VL.size(); i < e; ++i) { 214 if (auto *Scalar = dyn_cast<BinaryOperator>(VL[i])) 215 Intersection->andIRFlags(Scalar); 216 } 217 VecOp->copyIRFlags(Intersection); 218 } 219 } 220 } 221 222 /// \returns The type that all of the values in \p VL have or null if there 223 /// are different types. 224 static Type* getSameType(ArrayRef<Value *> VL) { 225 Type *Ty = VL[0]->getType(); 226 for (int i = 1, e = VL.size(); i < e; i++) 227 if (VL[i]->getType() != Ty) 228 return nullptr; 229 230 return Ty; 231 } 232 233 /// \returns True if Extract{Value,Element} instruction extracts element Idx. 234 static bool matchExtractIndex(Instruction *E, unsigned Idx, unsigned Opcode) { 235 assert(Opcode == Instruction::ExtractElement || 236 Opcode == Instruction::ExtractValue); 237 if (Opcode == Instruction::ExtractElement) { 238 ConstantInt *CI = dyn_cast<ConstantInt>(E->getOperand(1)); 239 return CI && CI->getZExtValue() == Idx; 240 } else { 241 ExtractValueInst *EI = cast<ExtractValueInst>(E); 242 return EI->getNumIndices() == 1 && *EI->idx_begin() == Idx; 243 } 244 } 245 246 /// \returns True if in-tree use also needs extract. This refers to 247 /// possible scalar operand in vectorized instruction. 248 static bool InTreeUserNeedToExtract(Value *Scalar, Instruction *UserInst, 249 TargetLibraryInfo *TLI) { 250 251 unsigned Opcode = UserInst->getOpcode(); 252 switch (Opcode) { 253 case Instruction::Load: { 254 LoadInst *LI = cast<LoadInst>(UserInst); 255 return (LI->getPointerOperand() == Scalar); 256 } 257 case Instruction::Store: { 258 StoreInst *SI = cast<StoreInst>(UserInst); 259 return (SI->getPointerOperand() == Scalar); 260 } 261 case Instruction::Call: { 262 CallInst *CI = cast<CallInst>(UserInst); 263 Intrinsic::ID ID = getVectorIntrinsicIDForCall(CI, TLI); 264 if (hasVectorInstrinsicScalarOpd(ID, 1)) { 265 return (CI->getArgOperand(1) == Scalar); 266 } 267 } 268 default: 269 return false; 270 } 271 } 272 273 /// \returns the AA location that is being access by the instruction. 274 static MemoryLocation getLocation(Instruction *I, AliasAnalysis *AA) { 275 if (StoreInst *SI = dyn_cast<StoreInst>(I)) 276 return MemoryLocation::get(SI); 277 if (LoadInst *LI = dyn_cast<LoadInst>(I)) 278 return MemoryLocation::get(LI); 279 return MemoryLocation(); 280 } 281 282 /// \returns True if the instruction is not a volatile or atomic load/store. 283 static bool isSimple(Instruction *I) { 284 if (LoadInst *LI = dyn_cast<LoadInst>(I)) 285 return LI->isSimple(); 286 if (StoreInst *SI = dyn_cast<StoreInst>(I)) 287 return SI->isSimple(); 288 if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I)) 289 return !MI->isVolatile(); 290 return true; 291 } 292 293 namespace llvm { 294 namespace slpvectorizer { 295 /// Bottom Up SLP Vectorizer. 296 class BoUpSLP { 297 public: 298 typedef SmallVector<Value *, 8> ValueList; 299 typedef SmallVector<Instruction *, 16> InstrList; 300 typedef SmallPtrSet<Value *, 16> ValueSet; 301 typedef SmallVector<StoreInst *, 8> StoreList; 302 303 BoUpSLP(Function *Func, ScalarEvolution *Se, TargetTransformInfo *Tti, 304 TargetLibraryInfo *TLi, AliasAnalysis *Aa, LoopInfo *Li, 305 DominatorTree *Dt, AssumptionCache *AC, DemandedBits *DB, 306 const DataLayout *DL) 307 : NumLoadsWantToKeepOrder(0), NumLoadsWantToChangeOrder(0), F(Func), 308 SE(Se), TTI(Tti), TLI(TLi), AA(Aa), LI(Li), DT(Dt), AC(AC), DB(DB), 309 DL(DL), Builder(Se->getContext()) { 310 CodeMetrics::collectEphemeralValues(F, AC, EphValues); 311 // Use the vector register size specified by the target unless overridden 312 // by a command-line option. 313 // TODO: It would be better to limit the vectorization factor based on 314 // data type rather than just register size. For example, x86 AVX has 315 // 256-bit registers, but it does not support integer operations 316 // at that width (that requires AVX2). 317 if (MaxVectorRegSizeOption.getNumOccurrences()) 318 MaxVecRegSize = MaxVectorRegSizeOption; 319 else 320 MaxVecRegSize = TTI->getRegisterBitWidth(true); 321 322 MinVecRegSize = MinVectorRegSizeOption; 323 } 324 325 /// \brief Vectorize the tree that starts with the elements in \p VL. 326 /// Returns the vectorized root. 327 Value *vectorizeTree(); 328 329 /// \returns the cost incurred by unwanted spills and fills, caused by 330 /// holding live values over call sites. 331 int getSpillCost(); 332 333 /// \returns the vectorization cost of the subtree that starts at \p VL. 334 /// A negative number means that this is profitable. 335 int getTreeCost(); 336 337 /// Construct a vectorizable tree that starts at \p Roots, ignoring users for 338 /// the purpose of scheduling and extraction in the \p UserIgnoreLst. 339 void buildTree(ArrayRef<Value *> Roots, 340 ArrayRef<Value *> UserIgnoreLst = None); 341 342 /// Clear the internal data structures that are created by 'buildTree'. 343 void deleteTree() { 344 VectorizableTree.clear(); 345 ScalarToTreeEntry.clear(); 346 MustGather.clear(); 347 ExternalUses.clear(); 348 NumLoadsWantToKeepOrder = 0; 349 NumLoadsWantToChangeOrder = 0; 350 for (auto &Iter : BlocksSchedules) { 351 BlockScheduling *BS = Iter.second.get(); 352 BS->clear(); 353 } 354 MinBWs.clear(); 355 } 356 357 /// \brief Perform LICM and CSE on the newly generated gather sequences. 358 void optimizeGatherSequence(); 359 360 /// \returns true if it is beneficial to reverse the vector order. 361 bool shouldReorder() const { 362 return NumLoadsWantToChangeOrder > NumLoadsWantToKeepOrder; 363 } 364 365 /// \return The vector element size in bits to use when vectorizing the 366 /// expression tree ending at \p V. If V is a store, the size is the width of 367 /// the stored value. Otherwise, the size is the width of the largest loaded 368 /// value reaching V. This method is used by the vectorizer to calculate 369 /// vectorization factors. 370 unsigned getVectorElementSize(Value *V); 371 372 /// Compute the minimum type sizes required to represent the entries in a 373 /// vectorizable tree. 374 void computeMinimumValueSizes(); 375 376 // \returns maximum vector register size as set by TTI or overridden by cl::opt. 377 unsigned getMaxVecRegSize() const { 378 return MaxVecRegSize; 379 } 380 381 // \returns minimum vector register size as set by cl::opt. 382 unsigned getMinVecRegSize() const { 383 return MinVecRegSize; 384 } 385 386 /// \brief Check if ArrayType or StructType is isomorphic to some VectorType. 387 /// 388 /// \returns number of elements in vector if isomorphism exists, 0 otherwise. 389 unsigned canMapToVector(Type *T, const DataLayout &DL) const; 390 391 private: 392 struct TreeEntry; 393 394 /// \returns the cost of the vectorizable entry. 395 int getEntryCost(TreeEntry *E); 396 397 /// This is the recursive part of buildTree. 398 void buildTree_rec(ArrayRef<Value *> Roots, unsigned Depth); 399 400 /// \returns True if the ExtractElement/ExtractValue instructions in VL can 401 /// be vectorized to use the original vector (or aggregate "bitcast" to a vector). 402 bool canReuseExtract(ArrayRef<Value *> VL, unsigned Opcode) const; 403 404 /// Vectorize a single entry in the tree. 405 Value *vectorizeTree(TreeEntry *E); 406 407 /// Vectorize a single entry in the tree, starting in \p VL. 408 Value *vectorizeTree(ArrayRef<Value *> VL); 409 410 /// \returns the pointer to the vectorized value if \p VL is already 411 /// vectorized, or NULL. They may happen in cycles. 412 Value *alreadyVectorized(ArrayRef<Value *> VL) const; 413 414 /// \returns the scalarization cost for this type. Scalarization in this 415 /// context means the creation of vectors from a group of scalars. 416 int getGatherCost(Type *Ty); 417 418 /// \returns the scalarization cost for this list of values. Assuming that 419 /// this subtree gets vectorized, we may need to extract the values from the 420 /// roots. This method calculates the cost of extracting the values. 421 int getGatherCost(ArrayRef<Value *> VL); 422 423 /// \brief Set the Builder insert point to one after the last instruction in 424 /// the bundle 425 void setInsertPointAfterBundle(ArrayRef<Value *> VL); 426 427 /// \returns a vector from a collection of scalars in \p VL. 428 Value *Gather(ArrayRef<Value *> VL, VectorType *Ty); 429 430 /// \returns whether the VectorizableTree is fully vectorizable and will 431 /// be beneficial even the tree height is tiny. 432 bool isFullyVectorizableTinyTree(); 433 434 /// \reorder commutative operands in alt shuffle if they result in 435 /// vectorized code. 436 void reorderAltShuffleOperands(ArrayRef<Value *> VL, 437 SmallVectorImpl<Value *> &Left, 438 SmallVectorImpl<Value *> &Right); 439 /// \reorder commutative operands to get better probability of 440 /// generating vectorized code. 441 void reorderInputsAccordingToOpcode(ArrayRef<Value *> VL, 442 SmallVectorImpl<Value *> &Left, 443 SmallVectorImpl<Value *> &Right); 444 struct TreeEntry { 445 TreeEntry() : Scalars(), VectorizedValue(nullptr), 446 NeedToGather(0) {} 447 448 /// \returns true if the scalars in VL are equal to this entry. 449 bool isSame(ArrayRef<Value *> VL) const { 450 assert(VL.size() == Scalars.size() && "Invalid size"); 451 return std::equal(VL.begin(), VL.end(), Scalars.begin()); 452 } 453 454 /// A vector of scalars. 455 ValueList Scalars; 456 457 /// The Scalars are vectorized into this value. It is initialized to Null. 458 Value *VectorizedValue; 459 460 /// Do we need to gather this sequence ? 461 bool NeedToGather; 462 }; 463 464 /// Create a new VectorizableTree entry. 465 TreeEntry *newTreeEntry(ArrayRef<Value *> VL, bool Vectorized) { 466 VectorizableTree.emplace_back(); 467 int idx = VectorizableTree.size() - 1; 468 TreeEntry *Last = &VectorizableTree[idx]; 469 Last->Scalars.insert(Last->Scalars.begin(), VL.begin(), VL.end()); 470 Last->NeedToGather = !Vectorized; 471 if (Vectorized) { 472 for (int i = 0, e = VL.size(); i != e; ++i) { 473 assert(!ScalarToTreeEntry.count(VL[i]) && "Scalar already in tree!"); 474 ScalarToTreeEntry[VL[i]] = idx; 475 } 476 } else { 477 MustGather.insert(VL.begin(), VL.end()); 478 } 479 return Last; 480 } 481 482 /// -- Vectorization State -- 483 /// Holds all of the tree entries. 484 std::vector<TreeEntry> VectorizableTree; 485 486 /// Maps a specific scalar to its tree entry. 487 SmallDenseMap<Value*, int> ScalarToTreeEntry; 488 489 /// A list of scalars that we found that we need to keep as scalars. 490 ValueSet MustGather; 491 492 /// This POD struct describes one external user in the vectorized tree. 493 struct ExternalUser { 494 ExternalUser (Value *S, llvm::User *U, int L) : 495 Scalar(S), User(U), Lane(L){} 496 // Which scalar in our function. 497 Value *Scalar; 498 // Which user that uses the scalar. 499 llvm::User *User; 500 // Which lane does the scalar belong to. 501 int Lane; 502 }; 503 typedef SmallVector<ExternalUser, 16> UserList; 504 505 /// Checks if two instructions may access the same memory. 506 /// 507 /// \p Loc1 is the location of \p Inst1. It is passed explicitly because it 508 /// is invariant in the calling loop. 509 bool isAliased(const MemoryLocation &Loc1, Instruction *Inst1, 510 Instruction *Inst2) { 511 512 // First check if the result is already in the cache. 513 AliasCacheKey key = std::make_pair(Inst1, Inst2); 514 Optional<bool> &result = AliasCache[key]; 515 if (result.hasValue()) { 516 return result.getValue(); 517 } 518 MemoryLocation Loc2 = getLocation(Inst2, AA); 519 bool aliased = true; 520 if (Loc1.Ptr && Loc2.Ptr && isSimple(Inst1) && isSimple(Inst2)) { 521 // Do the alias check. 522 aliased = AA->alias(Loc1, Loc2); 523 } 524 // Store the result in the cache. 525 result = aliased; 526 return aliased; 527 } 528 529 typedef std::pair<Instruction *, Instruction *> AliasCacheKey; 530 531 /// Cache for alias results. 532 /// TODO: consider moving this to the AliasAnalysis itself. 533 DenseMap<AliasCacheKey, Optional<bool>> AliasCache; 534 535 /// Removes an instruction from its block and eventually deletes it. 536 /// It's like Instruction::eraseFromParent() except that the actual deletion 537 /// is delayed until BoUpSLP is destructed. 538 /// This is required to ensure that there are no incorrect collisions in the 539 /// AliasCache, which can happen if a new instruction is allocated at the 540 /// same address as a previously deleted instruction. 541 void eraseInstruction(Instruction *I) { 542 I->removeFromParent(); 543 I->dropAllReferences(); 544 DeletedInstructions.push_back(std::unique_ptr<Instruction>(I)); 545 } 546 547 /// Temporary store for deleted instructions. Instructions will be deleted 548 /// eventually when the BoUpSLP is destructed. 549 SmallVector<std::unique_ptr<Instruction>, 8> DeletedInstructions; 550 551 /// A list of values that need to extracted out of the tree. 552 /// This list holds pairs of (Internal Scalar : External User). 553 UserList ExternalUses; 554 555 /// Values used only by @llvm.assume calls. 556 SmallPtrSet<const Value *, 32> EphValues; 557 558 /// Holds all of the instructions that we gathered. 559 SetVector<Instruction *> GatherSeq; 560 /// A list of blocks that we are going to CSE. 561 SetVector<BasicBlock *> CSEBlocks; 562 563 /// Contains all scheduling relevant data for an instruction. 564 /// A ScheduleData either represents a single instruction or a member of an 565 /// instruction bundle (= a group of instructions which is combined into a 566 /// vector instruction). 567 struct ScheduleData { 568 569 // The initial value for the dependency counters. It means that the 570 // dependencies are not calculated yet. 571 enum { InvalidDeps = -1 }; 572 573 ScheduleData() 574 : Inst(nullptr), FirstInBundle(nullptr), NextInBundle(nullptr), 575 NextLoadStore(nullptr), SchedulingRegionID(0), SchedulingPriority(0), 576 Dependencies(InvalidDeps), UnscheduledDeps(InvalidDeps), 577 UnscheduledDepsInBundle(InvalidDeps), IsScheduled(false) {} 578 579 void init(int BlockSchedulingRegionID) { 580 FirstInBundle = this; 581 NextInBundle = nullptr; 582 NextLoadStore = nullptr; 583 IsScheduled = false; 584 SchedulingRegionID = BlockSchedulingRegionID; 585 UnscheduledDepsInBundle = UnscheduledDeps; 586 clearDependencies(); 587 } 588 589 /// Returns true if the dependency information has been calculated. 590 bool hasValidDependencies() const { return Dependencies != InvalidDeps; } 591 592 /// Returns true for single instructions and for bundle representatives 593 /// (= the head of a bundle). 594 bool isSchedulingEntity() const { return FirstInBundle == this; } 595 596 /// Returns true if it represents an instruction bundle and not only a 597 /// single instruction. 598 bool isPartOfBundle() const { 599 return NextInBundle != nullptr || FirstInBundle != this; 600 } 601 602 /// Returns true if it is ready for scheduling, i.e. it has no more 603 /// unscheduled depending instructions/bundles. 604 bool isReady() const { 605 assert(isSchedulingEntity() && 606 "can't consider non-scheduling entity for ready list"); 607 return UnscheduledDepsInBundle == 0 && !IsScheduled; 608 } 609 610 /// Modifies the number of unscheduled dependencies, also updating it for 611 /// the whole bundle. 612 int incrementUnscheduledDeps(int Incr) { 613 UnscheduledDeps += Incr; 614 return FirstInBundle->UnscheduledDepsInBundle += Incr; 615 } 616 617 /// Sets the number of unscheduled dependencies to the number of 618 /// dependencies. 619 void resetUnscheduledDeps() { 620 incrementUnscheduledDeps(Dependencies - UnscheduledDeps); 621 } 622 623 /// Clears all dependency information. 624 void clearDependencies() { 625 Dependencies = InvalidDeps; 626 resetUnscheduledDeps(); 627 MemoryDependencies.clear(); 628 } 629 630 void dump(raw_ostream &os) const { 631 if (!isSchedulingEntity()) { 632 os << "/ " << *Inst; 633 } else if (NextInBundle) { 634 os << '[' << *Inst; 635 ScheduleData *SD = NextInBundle; 636 while (SD) { 637 os << ';' << *SD->Inst; 638 SD = SD->NextInBundle; 639 } 640 os << ']'; 641 } else { 642 os << *Inst; 643 } 644 } 645 646 Instruction *Inst; 647 648 /// Points to the head in an instruction bundle (and always to this for 649 /// single instructions). 650 ScheduleData *FirstInBundle; 651 652 /// Single linked list of all instructions in a bundle. Null if it is a 653 /// single instruction. 654 ScheduleData *NextInBundle; 655 656 /// Single linked list of all memory instructions (e.g. load, store, call) 657 /// in the block - until the end of the scheduling region. 658 ScheduleData *NextLoadStore; 659 660 /// The dependent memory instructions. 661 /// This list is derived on demand in calculateDependencies(). 662 SmallVector<ScheduleData *, 4> MemoryDependencies; 663 664 /// This ScheduleData is in the current scheduling region if this matches 665 /// the current SchedulingRegionID of BlockScheduling. 666 int SchedulingRegionID; 667 668 /// Used for getting a "good" final ordering of instructions. 669 int SchedulingPriority; 670 671 /// The number of dependencies. Constitutes of the number of users of the 672 /// instruction plus the number of dependent memory instructions (if any). 673 /// This value is calculated on demand. 674 /// If InvalidDeps, the number of dependencies is not calculated yet. 675 /// 676 int Dependencies; 677 678 /// The number of dependencies minus the number of dependencies of scheduled 679 /// instructions. As soon as this is zero, the instruction/bundle gets ready 680 /// for scheduling. 681 /// Note that this is negative as long as Dependencies is not calculated. 682 int UnscheduledDeps; 683 684 /// The sum of UnscheduledDeps in a bundle. Equals to UnscheduledDeps for 685 /// single instructions. 686 int UnscheduledDepsInBundle; 687 688 /// True if this instruction is scheduled (or considered as scheduled in the 689 /// dry-run). 690 bool IsScheduled; 691 }; 692 693 #ifndef NDEBUG 694 friend inline raw_ostream &operator<<(raw_ostream &os, 695 const BoUpSLP::ScheduleData &SD) { 696 SD.dump(os); 697 return os; 698 } 699 #endif 700 701 /// Contains all scheduling data for a basic block. 702 /// 703 struct BlockScheduling { 704 705 BlockScheduling(BasicBlock *BB) 706 : BB(BB), ChunkSize(BB->size()), ChunkPos(ChunkSize), 707 ScheduleStart(nullptr), ScheduleEnd(nullptr), 708 FirstLoadStoreInRegion(nullptr), LastLoadStoreInRegion(nullptr), 709 ScheduleRegionSize(0), 710 ScheduleRegionSizeLimit(ScheduleRegionSizeBudget), 711 // Make sure that the initial SchedulingRegionID is greater than the 712 // initial SchedulingRegionID in ScheduleData (which is 0). 713 SchedulingRegionID(1) {} 714 715 void clear() { 716 ReadyInsts.clear(); 717 ScheduleStart = nullptr; 718 ScheduleEnd = nullptr; 719 FirstLoadStoreInRegion = nullptr; 720 LastLoadStoreInRegion = nullptr; 721 722 // Reduce the maximum schedule region size by the size of the 723 // previous scheduling run. 724 ScheduleRegionSizeLimit -= ScheduleRegionSize; 725 if (ScheduleRegionSizeLimit < MinScheduleRegionSize) 726 ScheduleRegionSizeLimit = MinScheduleRegionSize; 727 ScheduleRegionSize = 0; 728 729 // Make a new scheduling region, i.e. all existing ScheduleData is not 730 // in the new region yet. 731 ++SchedulingRegionID; 732 } 733 734 ScheduleData *getScheduleData(Value *V) { 735 ScheduleData *SD = ScheduleDataMap[V]; 736 if (SD && SD->SchedulingRegionID == SchedulingRegionID) 737 return SD; 738 return nullptr; 739 } 740 741 bool isInSchedulingRegion(ScheduleData *SD) { 742 return SD->SchedulingRegionID == SchedulingRegionID; 743 } 744 745 /// Marks an instruction as scheduled and puts all dependent ready 746 /// instructions into the ready-list. 747 template <typename ReadyListType> 748 void schedule(ScheduleData *SD, ReadyListType &ReadyList) { 749 SD->IsScheduled = true; 750 DEBUG(dbgs() << "SLP: schedule " << *SD << "\n"); 751 752 ScheduleData *BundleMember = SD; 753 while (BundleMember) { 754 // Handle the def-use chain dependencies. 755 for (Use &U : BundleMember->Inst->operands()) { 756 ScheduleData *OpDef = getScheduleData(U.get()); 757 if (OpDef && OpDef->hasValidDependencies() && 758 OpDef->incrementUnscheduledDeps(-1) == 0) { 759 // There are no more unscheduled dependencies after decrementing, 760 // so we can put the dependent instruction into the ready list. 761 ScheduleData *DepBundle = OpDef->FirstInBundle; 762 assert(!DepBundle->IsScheduled && 763 "already scheduled bundle gets ready"); 764 ReadyList.insert(DepBundle); 765 DEBUG(dbgs() << "SLP: gets ready (def): " << *DepBundle << "\n"); 766 } 767 } 768 // Handle the memory dependencies. 769 for (ScheduleData *MemoryDepSD : BundleMember->MemoryDependencies) { 770 if (MemoryDepSD->incrementUnscheduledDeps(-1) == 0) { 771 // There are no more unscheduled dependencies after decrementing, 772 // so we can put the dependent instruction into the ready list. 773 ScheduleData *DepBundle = MemoryDepSD->FirstInBundle; 774 assert(!DepBundle->IsScheduled && 775 "already scheduled bundle gets ready"); 776 ReadyList.insert(DepBundle); 777 DEBUG(dbgs() << "SLP: gets ready (mem): " << *DepBundle << "\n"); 778 } 779 } 780 BundleMember = BundleMember->NextInBundle; 781 } 782 } 783 784 /// Put all instructions into the ReadyList which are ready for scheduling. 785 template <typename ReadyListType> 786 void initialFillReadyList(ReadyListType &ReadyList) { 787 for (auto *I = ScheduleStart; I != ScheduleEnd; I = I->getNextNode()) { 788 ScheduleData *SD = getScheduleData(I); 789 if (SD->isSchedulingEntity() && SD->isReady()) { 790 ReadyList.insert(SD); 791 DEBUG(dbgs() << "SLP: initially in ready list: " << *I << "\n"); 792 } 793 } 794 } 795 796 /// Checks if a bundle of instructions can be scheduled, i.e. has no 797 /// cyclic dependencies. This is only a dry-run, no instructions are 798 /// actually moved at this stage. 799 bool tryScheduleBundle(ArrayRef<Value *> VL, BoUpSLP *SLP); 800 801 /// Un-bundles a group of instructions. 802 void cancelScheduling(ArrayRef<Value *> VL); 803 804 /// Extends the scheduling region so that V is inside the region. 805 /// \returns true if the region size is within the limit. 806 bool extendSchedulingRegion(Value *V); 807 808 /// Initialize the ScheduleData structures for new instructions in the 809 /// scheduling region. 810 void initScheduleData(Instruction *FromI, Instruction *ToI, 811 ScheduleData *PrevLoadStore, 812 ScheduleData *NextLoadStore); 813 814 /// Updates the dependency information of a bundle and of all instructions/ 815 /// bundles which depend on the original bundle. 816 void calculateDependencies(ScheduleData *SD, bool InsertInReadyList, 817 BoUpSLP *SLP); 818 819 /// Sets all instruction in the scheduling region to un-scheduled. 820 void resetSchedule(); 821 822 BasicBlock *BB; 823 824 /// Simple memory allocation for ScheduleData. 825 std::vector<std::unique_ptr<ScheduleData[]>> ScheduleDataChunks; 826 827 /// The size of a ScheduleData array in ScheduleDataChunks. 828 int ChunkSize; 829 830 /// The allocator position in the current chunk, which is the last entry 831 /// of ScheduleDataChunks. 832 int ChunkPos; 833 834 /// Attaches ScheduleData to Instruction. 835 /// Note that the mapping survives during all vectorization iterations, i.e. 836 /// ScheduleData structures are recycled. 837 DenseMap<Value *, ScheduleData *> ScheduleDataMap; 838 839 struct ReadyList : SmallVector<ScheduleData *, 8> { 840 void insert(ScheduleData *SD) { push_back(SD); } 841 }; 842 843 /// The ready-list for scheduling (only used for the dry-run). 844 ReadyList ReadyInsts; 845 846 /// The first instruction of the scheduling region. 847 Instruction *ScheduleStart; 848 849 /// The first instruction _after_ the scheduling region. 850 Instruction *ScheduleEnd; 851 852 /// The first memory accessing instruction in the scheduling region 853 /// (can be null). 854 ScheduleData *FirstLoadStoreInRegion; 855 856 /// The last memory accessing instruction in the scheduling region 857 /// (can be null). 858 ScheduleData *LastLoadStoreInRegion; 859 860 /// The current size of the scheduling region. 861 int ScheduleRegionSize; 862 863 /// The maximum size allowed for the scheduling region. 864 int ScheduleRegionSizeLimit; 865 866 /// The ID of the scheduling region. For a new vectorization iteration this 867 /// is incremented which "removes" all ScheduleData from the region. 868 int SchedulingRegionID; 869 }; 870 871 /// Attaches the BlockScheduling structures to basic blocks. 872 MapVector<BasicBlock *, std::unique_ptr<BlockScheduling>> BlocksSchedules; 873 874 /// Performs the "real" scheduling. Done before vectorization is actually 875 /// performed in a basic block. 876 void scheduleBlock(BlockScheduling *BS); 877 878 /// List of users to ignore during scheduling and that don't need extracting. 879 ArrayRef<Value *> UserIgnoreList; 880 881 // Number of load-bundles, which contain consecutive loads. 882 int NumLoadsWantToKeepOrder; 883 884 // Number of load-bundles of size 2, which are consecutive loads if reversed. 885 int NumLoadsWantToChangeOrder; 886 887 // Analysis and block reference. 888 Function *F; 889 ScalarEvolution *SE; 890 TargetTransformInfo *TTI; 891 TargetLibraryInfo *TLI; 892 AliasAnalysis *AA; 893 LoopInfo *LI; 894 DominatorTree *DT; 895 AssumptionCache *AC; 896 DemandedBits *DB; 897 const DataLayout *DL; 898 unsigned MaxVecRegSize; // This is set by TTI or overridden by cl::opt. 899 unsigned MinVecRegSize; // Set by cl::opt (default: 128). 900 /// Instruction builder to construct the vectorized tree. 901 IRBuilder<> Builder; 902 903 /// A map of scalar integer values to the smallest bit width with which they 904 /// can legally be represented. 905 MapVector<Value *, uint64_t> MinBWs; 906 }; 907 908 } // end namespace llvm 909 } // end namespace slpvectorizer 910 911 void BoUpSLP::buildTree(ArrayRef<Value *> Roots, 912 ArrayRef<Value *> UserIgnoreLst) { 913 deleteTree(); 914 UserIgnoreList = UserIgnoreLst; 915 if (!getSameType(Roots)) 916 return; 917 buildTree_rec(Roots, 0); 918 919 // Collect the values that we need to extract from the tree. 920 for (TreeEntry &EIdx : VectorizableTree) { 921 TreeEntry *Entry = &EIdx; 922 923 // For each lane: 924 for (int Lane = 0, LE = Entry->Scalars.size(); Lane != LE; ++Lane) { 925 Value *Scalar = Entry->Scalars[Lane]; 926 927 // No need to handle users of gathered values. 928 if (Entry->NeedToGather) 929 continue; 930 931 for (User *U : Scalar->users()) { 932 DEBUG(dbgs() << "SLP: Checking user:" << *U << ".\n"); 933 934 Instruction *UserInst = dyn_cast<Instruction>(U); 935 if (!UserInst) 936 continue; 937 938 // Skip in-tree scalars that become vectors 939 if (ScalarToTreeEntry.count(U)) { 940 int Idx = ScalarToTreeEntry[U]; 941 TreeEntry *UseEntry = &VectorizableTree[Idx]; 942 Value *UseScalar = UseEntry->Scalars[0]; 943 // Some in-tree scalars will remain as scalar in vectorized 944 // instructions. If that is the case, the one in Lane 0 will 945 // be used. 946 if (UseScalar != U || 947 !InTreeUserNeedToExtract(Scalar, UserInst, TLI)) { 948 DEBUG(dbgs() << "SLP: \tInternal user will be removed:" << *U 949 << ".\n"); 950 assert(!VectorizableTree[Idx].NeedToGather && "Bad state"); 951 continue; 952 } 953 } 954 955 // Ignore users in the user ignore list. 956 if (std::find(UserIgnoreList.begin(), UserIgnoreList.end(), UserInst) != 957 UserIgnoreList.end()) 958 continue; 959 960 DEBUG(dbgs() << "SLP: Need to extract:" << *U << " from lane " << 961 Lane << " from " << *Scalar << ".\n"); 962 ExternalUses.push_back(ExternalUser(Scalar, U, Lane)); 963 } 964 } 965 } 966 } 967 968 969 void BoUpSLP::buildTree_rec(ArrayRef<Value *> VL, unsigned Depth) { 970 bool SameTy = allConstant(VL) || getSameType(VL); (void)SameTy; 971 bool isAltShuffle = false; 972 assert(SameTy && "Invalid types!"); 973 974 if (Depth == RecursionMaxDepth) { 975 DEBUG(dbgs() << "SLP: Gathering due to max recursion depth.\n"); 976 newTreeEntry(VL, false); 977 return; 978 } 979 980 // Don't handle vectors. 981 if (VL[0]->getType()->isVectorTy()) { 982 DEBUG(dbgs() << "SLP: Gathering due to vector type.\n"); 983 newTreeEntry(VL, false); 984 return; 985 } 986 987 if (StoreInst *SI = dyn_cast<StoreInst>(VL[0])) 988 if (SI->getValueOperand()->getType()->isVectorTy()) { 989 DEBUG(dbgs() << "SLP: Gathering due to store vector type.\n"); 990 newTreeEntry(VL, false); 991 return; 992 } 993 unsigned Opcode = getSameOpcode(VL); 994 995 // Check that this shuffle vector refers to the alternate 996 // sequence of opcodes. 997 if (Opcode == Instruction::ShuffleVector) { 998 Instruction *I0 = dyn_cast<Instruction>(VL[0]); 999 unsigned Op = I0->getOpcode(); 1000 if (Op != Instruction::ShuffleVector) 1001 isAltShuffle = true; 1002 } 1003 1004 // If all of the operands are identical or constant we have a simple solution. 1005 if (allConstant(VL) || isSplat(VL) || !getSameBlock(VL) || !Opcode) { 1006 DEBUG(dbgs() << "SLP: Gathering due to C,S,B,O. \n"); 1007 newTreeEntry(VL, false); 1008 return; 1009 } 1010 1011 // We now know that this is a vector of instructions of the same type from 1012 // the same block. 1013 1014 // Don't vectorize ephemeral values. 1015 for (unsigned i = 0, e = VL.size(); i != e; ++i) { 1016 if (EphValues.count(VL[i])) { 1017 DEBUG(dbgs() << "SLP: The instruction (" << *VL[i] << 1018 ") is ephemeral.\n"); 1019 newTreeEntry(VL, false); 1020 return; 1021 } 1022 } 1023 1024 // Check if this is a duplicate of another entry. 1025 if (ScalarToTreeEntry.count(VL[0])) { 1026 int Idx = ScalarToTreeEntry[VL[0]]; 1027 TreeEntry *E = &VectorizableTree[Idx]; 1028 for (unsigned i = 0, e = VL.size(); i != e; ++i) { 1029 DEBUG(dbgs() << "SLP: \tChecking bundle: " << *VL[i] << ".\n"); 1030 if (E->Scalars[i] != VL[i]) { 1031 DEBUG(dbgs() << "SLP: Gathering due to partial overlap.\n"); 1032 newTreeEntry(VL, false); 1033 return; 1034 } 1035 } 1036 DEBUG(dbgs() << "SLP: Perfect diamond merge at " << *VL[0] << ".\n"); 1037 return; 1038 } 1039 1040 // Check that none of the instructions in the bundle are already in the tree. 1041 for (unsigned i = 0, e = VL.size(); i != e; ++i) { 1042 if (ScalarToTreeEntry.count(VL[i])) { 1043 DEBUG(dbgs() << "SLP: The instruction (" << *VL[i] << 1044 ") is already in tree.\n"); 1045 newTreeEntry(VL, false); 1046 return; 1047 } 1048 } 1049 1050 // If any of the scalars is marked as a value that needs to stay scalar then 1051 // we need to gather the scalars. 1052 for (unsigned i = 0, e = VL.size(); i != e; ++i) { 1053 if (MustGather.count(VL[i])) { 1054 DEBUG(dbgs() << "SLP: Gathering due to gathered scalar.\n"); 1055 newTreeEntry(VL, false); 1056 return; 1057 } 1058 } 1059 1060 // Check that all of the users of the scalars that we want to vectorize are 1061 // schedulable. 1062 Instruction *VL0 = cast<Instruction>(VL[0]); 1063 BasicBlock *BB = cast<Instruction>(VL0)->getParent(); 1064 1065 if (!DT->isReachableFromEntry(BB)) { 1066 // Don't go into unreachable blocks. They may contain instructions with 1067 // dependency cycles which confuse the final scheduling. 1068 DEBUG(dbgs() << "SLP: bundle in unreachable block.\n"); 1069 newTreeEntry(VL, false); 1070 return; 1071 } 1072 1073 // Check that every instructions appears once in this bundle. 1074 for (unsigned i = 0, e = VL.size(); i < e; ++i) 1075 for (unsigned j = i+1; j < e; ++j) 1076 if (VL[i] == VL[j]) { 1077 DEBUG(dbgs() << "SLP: Scalar used twice in bundle.\n"); 1078 newTreeEntry(VL, false); 1079 return; 1080 } 1081 1082 auto &BSRef = BlocksSchedules[BB]; 1083 if (!BSRef) { 1084 BSRef = llvm::make_unique<BlockScheduling>(BB); 1085 } 1086 BlockScheduling &BS = *BSRef.get(); 1087 1088 if (!BS.tryScheduleBundle(VL, this)) { 1089 DEBUG(dbgs() << "SLP: We are not able to schedule this bundle!\n"); 1090 assert((!BS.getScheduleData(VL[0]) || 1091 !BS.getScheduleData(VL[0])->isPartOfBundle()) && 1092 "tryScheduleBundle should cancelScheduling on failure"); 1093 newTreeEntry(VL, false); 1094 return; 1095 } 1096 DEBUG(dbgs() << "SLP: We are able to schedule this bundle.\n"); 1097 1098 switch (Opcode) { 1099 case Instruction::PHI: { 1100 PHINode *PH = dyn_cast<PHINode>(VL0); 1101 1102 // Check for terminator values (e.g. invoke). 1103 for (unsigned j = 0; j < VL.size(); ++j) 1104 for (unsigned i = 0, e = PH->getNumIncomingValues(); i < e; ++i) { 1105 TerminatorInst *Term = dyn_cast<TerminatorInst>( 1106 cast<PHINode>(VL[j])->getIncomingValueForBlock(PH->getIncomingBlock(i))); 1107 if (Term) { 1108 DEBUG(dbgs() << "SLP: Need to swizzle PHINodes (TerminatorInst use).\n"); 1109 BS.cancelScheduling(VL); 1110 newTreeEntry(VL, false); 1111 return; 1112 } 1113 } 1114 1115 newTreeEntry(VL, true); 1116 DEBUG(dbgs() << "SLP: added a vector of PHINodes.\n"); 1117 1118 for (unsigned i = 0, e = PH->getNumIncomingValues(); i < e; ++i) { 1119 ValueList Operands; 1120 // Prepare the operand vector. 1121 for (Value *j : VL) 1122 Operands.push_back(cast<PHINode>(j)->getIncomingValueForBlock( 1123 PH->getIncomingBlock(i))); 1124 1125 buildTree_rec(Operands, Depth + 1); 1126 } 1127 return; 1128 } 1129 case Instruction::ExtractValue: 1130 case Instruction::ExtractElement: { 1131 bool Reuse = canReuseExtract(VL, Opcode); 1132 if (Reuse) { 1133 DEBUG(dbgs() << "SLP: Reusing extract sequence.\n"); 1134 } else { 1135 BS.cancelScheduling(VL); 1136 } 1137 newTreeEntry(VL, Reuse); 1138 return; 1139 } 1140 case Instruction::Load: { 1141 // Check that a vectorized load would load the same memory as a scalar 1142 // load. 1143 // For example we don't want vectorize loads that are smaller than 8 bit. 1144 // Even though we have a packed struct {<i2, i2, i2, i2>} LLVM treats 1145 // loading/storing it as an i8 struct. If we vectorize loads/stores from 1146 // such a struct we read/write packed bits disagreeing with the 1147 // unvectorized version. 1148 Type *ScalarTy = VL[0]->getType(); 1149 1150 if (DL->getTypeSizeInBits(ScalarTy) != 1151 DL->getTypeAllocSizeInBits(ScalarTy)) { 1152 BS.cancelScheduling(VL); 1153 newTreeEntry(VL, false); 1154 DEBUG(dbgs() << "SLP: Gathering loads of non-packed type.\n"); 1155 return; 1156 } 1157 // Check if the loads are consecutive or of we need to swizzle them. 1158 for (unsigned i = 0, e = VL.size() - 1; i < e; ++i) { 1159 LoadInst *L = cast<LoadInst>(VL[i]); 1160 if (!L->isSimple()) { 1161 BS.cancelScheduling(VL); 1162 newTreeEntry(VL, false); 1163 DEBUG(dbgs() << "SLP: Gathering non-simple loads.\n"); 1164 return; 1165 } 1166 1167 if (!isConsecutiveAccess(VL[i], VL[i + 1], *DL, *SE)) { 1168 if (VL.size() == 2 && isConsecutiveAccess(VL[1], VL[0], *DL, *SE)) { 1169 ++NumLoadsWantToChangeOrder; 1170 } 1171 BS.cancelScheduling(VL); 1172 newTreeEntry(VL, false); 1173 DEBUG(dbgs() << "SLP: Gathering non-consecutive loads.\n"); 1174 return; 1175 } 1176 } 1177 ++NumLoadsWantToKeepOrder; 1178 newTreeEntry(VL, true); 1179 DEBUG(dbgs() << "SLP: added a vector of loads.\n"); 1180 return; 1181 } 1182 case Instruction::ZExt: 1183 case Instruction::SExt: 1184 case Instruction::FPToUI: 1185 case Instruction::FPToSI: 1186 case Instruction::FPExt: 1187 case Instruction::PtrToInt: 1188 case Instruction::IntToPtr: 1189 case Instruction::SIToFP: 1190 case Instruction::UIToFP: 1191 case Instruction::Trunc: 1192 case Instruction::FPTrunc: 1193 case Instruction::BitCast: { 1194 Type *SrcTy = VL0->getOperand(0)->getType(); 1195 for (unsigned i = 0; i < VL.size(); ++i) { 1196 Type *Ty = cast<Instruction>(VL[i])->getOperand(0)->getType(); 1197 if (Ty != SrcTy || !isValidElementType(Ty)) { 1198 BS.cancelScheduling(VL); 1199 newTreeEntry(VL, false); 1200 DEBUG(dbgs() << "SLP: Gathering casts with different src types.\n"); 1201 return; 1202 } 1203 } 1204 newTreeEntry(VL, true); 1205 DEBUG(dbgs() << "SLP: added a vector of casts.\n"); 1206 1207 for (unsigned i = 0, e = VL0->getNumOperands(); i < e; ++i) { 1208 ValueList Operands; 1209 // Prepare the operand vector. 1210 for (Value *j : VL) 1211 Operands.push_back(cast<Instruction>(j)->getOperand(i)); 1212 1213 buildTree_rec(Operands, Depth+1); 1214 } 1215 return; 1216 } 1217 case Instruction::ICmp: 1218 case Instruction::FCmp: { 1219 // Check that all of the compares have the same predicate. 1220 CmpInst::Predicate P0 = cast<CmpInst>(VL0)->getPredicate(); 1221 Type *ComparedTy = cast<Instruction>(VL[0])->getOperand(0)->getType(); 1222 for (unsigned i = 1, e = VL.size(); i < e; ++i) { 1223 CmpInst *Cmp = cast<CmpInst>(VL[i]); 1224 if (Cmp->getPredicate() != P0 || 1225 Cmp->getOperand(0)->getType() != ComparedTy) { 1226 BS.cancelScheduling(VL); 1227 newTreeEntry(VL, false); 1228 DEBUG(dbgs() << "SLP: Gathering cmp with different predicate.\n"); 1229 return; 1230 } 1231 } 1232 1233 newTreeEntry(VL, true); 1234 DEBUG(dbgs() << "SLP: added a vector of compares.\n"); 1235 1236 for (unsigned i = 0, e = VL0->getNumOperands(); i < e; ++i) { 1237 ValueList Operands; 1238 // Prepare the operand vector. 1239 for (Value *j : VL) 1240 Operands.push_back(cast<Instruction>(j)->getOperand(i)); 1241 1242 buildTree_rec(Operands, Depth+1); 1243 } 1244 return; 1245 } 1246 case Instruction::Select: 1247 case Instruction::Add: 1248 case Instruction::FAdd: 1249 case Instruction::Sub: 1250 case Instruction::FSub: 1251 case Instruction::Mul: 1252 case Instruction::FMul: 1253 case Instruction::UDiv: 1254 case Instruction::SDiv: 1255 case Instruction::FDiv: 1256 case Instruction::URem: 1257 case Instruction::SRem: 1258 case Instruction::FRem: 1259 case Instruction::Shl: 1260 case Instruction::LShr: 1261 case Instruction::AShr: 1262 case Instruction::And: 1263 case Instruction::Or: 1264 case Instruction::Xor: { 1265 newTreeEntry(VL, true); 1266 DEBUG(dbgs() << "SLP: added a vector of bin op.\n"); 1267 1268 // Sort operands of the instructions so that each side is more likely to 1269 // have the same opcode. 1270 if (isa<BinaryOperator>(VL0) && VL0->isCommutative()) { 1271 ValueList Left, Right; 1272 reorderInputsAccordingToOpcode(VL, Left, Right); 1273 buildTree_rec(Left, Depth + 1); 1274 buildTree_rec(Right, Depth + 1); 1275 return; 1276 } 1277 1278 for (unsigned i = 0, e = VL0->getNumOperands(); i < e; ++i) { 1279 ValueList Operands; 1280 // Prepare the operand vector. 1281 for (Value *j : VL) 1282 Operands.push_back(cast<Instruction>(j)->getOperand(i)); 1283 1284 buildTree_rec(Operands, Depth+1); 1285 } 1286 return; 1287 } 1288 case Instruction::GetElementPtr: { 1289 // We don't combine GEPs with complicated (nested) indexing. 1290 for (unsigned j = 0; j < VL.size(); ++j) { 1291 if (cast<Instruction>(VL[j])->getNumOperands() != 2) { 1292 DEBUG(dbgs() << "SLP: not-vectorizable GEP (nested indexes).\n"); 1293 BS.cancelScheduling(VL); 1294 newTreeEntry(VL, false); 1295 return; 1296 } 1297 } 1298 1299 // We can't combine several GEPs into one vector if they operate on 1300 // different types. 1301 Type *Ty0 = cast<Instruction>(VL0)->getOperand(0)->getType(); 1302 for (unsigned j = 0; j < VL.size(); ++j) { 1303 Type *CurTy = cast<Instruction>(VL[j])->getOperand(0)->getType(); 1304 if (Ty0 != CurTy) { 1305 DEBUG(dbgs() << "SLP: not-vectorizable GEP (different types).\n"); 1306 BS.cancelScheduling(VL); 1307 newTreeEntry(VL, false); 1308 return; 1309 } 1310 } 1311 1312 // We don't combine GEPs with non-constant indexes. 1313 for (unsigned j = 0; j < VL.size(); ++j) { 1314 auto Op = cast<Instruction>(VL[j])->getOperand(1); 1315 if (!isa<ConstantInt>(Op)) { 1316 DEBUG( 1317 dbgs() << "SLP: not-vectorizable GEP (non-constant indexes).\n"); 1318 BS.cancelScheduling(VL); 1319 newTreeEntry(VL, false); 1320 return; 1321 } 1322 } 1323 1324 newTreeEntry(VL, true); 1325 DEBUG(dbgs() << "SLP: added a vector of GEPs.\n"); 1326 for (unsigned i = 0, e = 2; i < e; ++i) { 1327 ValueList Operands; 1328 // Prepare the operand vector. 1329 for (Value *j : VL) 1330 Operands.push_back(cast<Instruction>(j)->getOperand(i)); 1331 1332 buildTree_rec(Operands, Depth + 1); 1333 } 1334 return; 1335 } 1336 case Instruction::Store: { 1337 // Check if the stores are consecutive or of we need to swizzle them. 1338 for (unsigned i = 0, e = VL.size() - 1; i < e; ++i) 1339 if (!isConsecutiveAccess(VL[i], VL[i + 1], *DL, *SE)) { 1340 BS.cancelScheduling(VL); 1341 newTreeEntry(VL, false); 1342 DEBUG(dbgs() << "SLP: Non-consecutive store.\n"); 1343 return; 1344 } 1345 1346 newTreeEntry(VL, true); 1347 DEBUG(dbgs() << "SLP: added a vector of stores.\n"); 1348 1349 ValueList Operands; 1350 for (Value *j : VL) 1351 Operands.push_back(cast<Instruction>(j)->getOperand(0)); 1352 1353 buildTree_rec(Operands, Depth + 1); 1354 return; 1355 } 1356 case Instruction::Call: { 1357 // Check if the calls are all to the same vectorizable intrinsic. 1358 CallInst *CI = cast<CallInst>(VL[0]); 1359 // Check if this is an Intrinsic call or something that can be 1360 // represented by an intrinsic call 1361 Intrinsic::ID ID = getVectorIntrinsicIDForCall(CI, TLI); 1362 if (!isTriviallyVectorizable(ID)) { 1363 BS.cancelScheduling(VL); 1364 newTreeEntry(VL, false); 1365 DEBUG(dbgs() << "SLP: Non-vectorizable call.\n"); 1366 return; 1367 } 1368 Function *Int = CI->getCalledFunction(); 1369 Value *A1I = nullptr; 1370 if (hasVectorInstrinsicScalarOpd(ID, 1)) 1371 A1I = CI->getArgOperand(1); 1372 for (unsigned i = 1, e = VL.size(); i != e; ++i) { 1373 CallInst *CI2 = dyn_cast<CallInst>(VL[i]); 1374 if (!CI2 || CI2->getCalledFunction() != Int || 1375 getVectorIntrinsicIDForCall(CI2, TLI) != ID || 1376 !CI->hasIdenticalOperandBundleSchema(*CI2)) { 1377 BS.cancelScheduling(VL); 1378 newTreeEntry(VL, false); 1379 DEBUG(dbgs() << "SLP: mismatched calls:" << *CI << "!=" << *VL[i] 1380 << "\n"); 1381 return; 1382 } 1383 // ctlz,cttz and powi are special intrinsics whose second argument 1384 // should be same in order for them to be vectorized. 1385 if (hasVectorInstrinsicScalarOpd(ID, 1)) { 1386 Value *A1J = CI2->getArgOperand(1); 1387 if (A1I != A1J) { 1388 BS.cancelScheduling(VL); 1389 newTreeEntry(VL, false); 1390 DEBUG(dbgs() << "SLP: mismatched arguments in call:" << *CI 1391 << " argument "<< A1I<<"!=" << A1J 1392 << "\n"); 1393 return; 1394 } 1395 } 1396 // Verify that the bundle operands are identical between the two calls. 1397 if (CI->hasOperandBundles() && 1398 !std::equal(CI->op_begin() + CI->getBundleOperandsStartIndex(), 1399 CI->op_begin() + CI->getBundleOperandsEndIndex(), 1400 CI2->op_begin() + CI2->getBundleOperandsStartIndex())) { 1401 BS.cancelScheduling(VL); 1402 newTreeEntry(VL, false); 1403 DEBUG(dbgs() << "SLP: mismatched bundle operands in calls:" << *CI << "!=" 1404 << *VL[i] << '\n'); 1405 return; 1406 } 1407 } 1408 1409 newTreeEntry(VL, true); 1410 for (unsigned i = 0, e = CI->getNumArgOperands(); i != e; ++i) { 1411 ValueList Operands; 1412 // Prepare the operand vector. 1413 for (Value *j : VL) { 1414 CallInst *CI2 = dyn_cast<CallInst>(j); 1415 Operands.push_back(CI2->getArgOperand(i)); 1416 } 1417 buildTree_rec(Operands, Depth + 1); 1418 } 1419 return; 1420 } 1421 case Instruction::ShuffleVector: { 1422 // If this is not an alternate sequence of opcode like add-sub 1423 // then do not vectorize this instruction. 1424 if (!isAltShuffle) { 1425 BS.cancelScheduling(VL); 1426 newTreeEntry(VL, false); 1427 DEBUG(dbgs() << "SLP: ShuffleVector are not vectorized.\n"); 1428 return; 1429 } 1430 newTreeEntry(VL, true); 1431 DEBUG(dbgs() << "SLP: added a ShuffleVector op.\n"); 1432 1433 // Reorder operands if reordering would enable vectorization. 1434 if (isa<BinaryOperator>(VL0)) { 1435 ValueList Left, Right; 1436 reorderAltShuffleOperands(VL, Left, Right); 1437 buildTree_rec(Left, Depth + 1); 1438 buildTree_rec(Right, Depth + 1); 1439 return; 1440 } 1441 1442 for (unsigned i = 0, e = VL0->getNumOperands(); i < e; ++i) { 1443 ValueList Operands; 1444 // Prepare the operand vector. 1445 for (Value *j : VL) 1446 Operands.push_back(cast<Instruction>(j)->getOperand(i)); 1447 1448 buildTree_rec(Operands, Depth + 1); 1449 } 1450 return; 1451 } 1452 default: 1453 BS.cancelScheduling(VL); 1454 newTreeEntry(VL, false); 1455 DEBUG(dbgs() << "SLP: Gathering unknown instruction.\n"); 1456 return; 1457 } 1458 } 1459 1460 unsigned BoUpSLP::canMapToVector(Type *T, const DataLayout &DL) const { 1461 unsigned N; 1462 Type *EltTy; 1463 auto *ST = dyn_cast<StructType>(T); 1464 if (ST) { 1465 N = ST->getNumElements(); 1466 EltTy = *ST->element_begin(); 1467 } else { 1468 N = cast<ArrayType>(T)->getNumElements(); 1469 EltTy = cast<ArrayType>(T)->getElementType(); 1470 } 1471 if (!isValidElementType(EltTy)) 1472 return 0; 1473 uint64_t VTSize = DL.getTypeStoreSizeInBits(VectorType::get(EltTy, N)); 1474 if (VTSize < MinVecRegSize || VTSize > MaxVecRegSize || VTSize != DL.getTypeStoreSizeInBits(T)) 1475 return 0; 1476 if (ST) { 1477 // Check that struct is homogeneous. 1478 for (const auto *Ty : ST->elements()) 1479 if (Ty != EltTy) 1480 return 0; 1481 } 1482 return N; 1483 } 1484 1485 bool BoUpSLP::canReuseExtract(ArrayRef<Value *> VL, unsigned Opcode) const { 1486 assert(Opcode == Instruction::ExtractElement || 1487 Opcode == Instruction::ExtractValue); 1488 assert(Opcode == getSameOpcode(VL) && "Invalid opcode"); 1489 // Check if all of the extracts come from the same vector and from the 1490 // correct offset. 1491 Value *VL0 = VL[0]; 1492 Instruction *E0 = cast<Instruction>(VL0); 1493 Value *Vec = E0->getOperand(0); 1494 1495 // We have to extract from a vector/aggregate with the same number of elements. 1496 unsigned NElts; 1497 if (Opcode == Instruction::ExtractValue) { 1498 const DataLayout &DL = E0->getModule()->getDataLayout(); 1499 NElts = canMapToVector(Vec->getType(), DL); 1500 if (!NElts) 1501 return false; 1502 // Check if load can be rewritten as load of vector. 1503 LoadInst *LI = dyn_cast<LoadInst>(Vec); 1504 if (!LI || !LI->isSimple() || !LI->hasNUses(VL.size())) 1505 return false; 1506 } else { 1507 NElts = Vec->getType()->getVectorNumElements(); 1508 } 1509 1510 if (NElts != VL.size()) 1511 return false; 1512 1513 // Check that all of the indices extract from the correct offset. 1514 if (!matchExtractIndex(E0, 0, Opcode)) 1515 return false; 1516 1517 for (unsigned i = 1, e = VL.size(); i < e; ++i) { 1518 Instruction *E = cast<Instruction>(VL[i]); 1519 if (!matchExtractIndex(E, i, Opcode)) 1520 return false; 1521 if (E->getOperand(0) != Vec) 1522 return false; 1523 } 1524 1525 return true; 1526 } 1527 1528 int BoUpSLP::getEntryCost(TreeEntry *E) { 1529 ArrayRef<Value*> VL = E->Scalars; 1530 1531 Type *ScalarTy = VL[0]->getType(); 1532 if (StoreInst *SI = dyn_cast<StoreInst>(VL[0])) 1533 ScalarTy = SI->getValueOperand()->getType(); 1534 VectorType *VecTy = VectorType::get(ScalarTy, VL.size()); 1535 1536 // If we have computed a smaller type for the expression, update VecTy so 1537 // that the costs will be accurate. 1538 if (MinBWs.count(VL[0])) 1539 VecTy = VectorType::get(IntegerType::get(F->getContext(), MinBWs[VL[0]]), 1540 VL.size()); 1541 1542 if (E->NeedToGather) { 1543 if (allConstant(VL)) 1544 return 0; 1545 if (isSplat(VL)) { 1546 return TTI->getShuffleCost(TargetTransformInfo::SK_Broadcast, VecTy, 0); 1547 } 1548 return getGatherCost(E->Scalars); 1549 } 1550 unsigned Opcode = getSameOpcode(VL); 1551 assert(Opcode && getSameType(VL) && getSameBlock(VL) && "Invalid VL"); 1552 Instruction *VL0 = cast<Instruction>(VL[0]); 1553 switch (Opcode) { 1554 case Instruction::PHI: { 1555 return 0; 1556 } 1557 case Instruction::ExtractValue: 1558 case Instruction::ExtractElement: { 1559 if (canReuseExtract(VL, Opcode)) { 1560 int DeadCost = 0; 1561 for (unsigned i = 0, e = VL.size(); i < e; ++i) { 1562 Instruction *E = cast<Instruction>(VL[i]); 1563 if (E->hasOneUse()) 1564 // Take credit for instruction that will become dead. 1565 DeadCost += 1566 TTI->getVectorInstrCost(Instruction::ExtractElement, VecTy, i); 1567 } 1568 return -DeadCost; 1569 } 1570 return getGatherCost(VecTy); 1571 } 1572 case Instruction::ZExt: 1573 case Instruction::SExt: 1574 case Instruction::FPToUI: 1575 case Instruction::FPToSI: 1576 case Instruction::FPExt: 1577 case Instruction::PtrToInt: 1578 case Instruction::IntToPtr: 1579 case Instruction::SIToFP: 1580 case Instruction::UIToFP: 1581 case Instruction::Trunc: 1582 case Instruction::FPTrunc: 1583 case Instruction::BitCast: { 1584 Type *SrcTy = VL0->getOperand(0)->getType(); 1585 1586 // Calculate the cost of this instruction. 1587 int ScalarCost = VL.size() * TTI->getCastInstrCost(VL0->getOpcode(), 1588 VL0->getType(), SrcTy); 1589 1590 VectorType *SrcVecTy = VectorType::get(SrcTy, VL.size()); 1591 int VecCost = TTI->getCastInstrCost(VL0->getOpcode(), VecTy, SrcVecTy); 1592 return VecCost - ScalarCost; 1593 } 1594 case Instruction::FCmp: 1595 case Instruction::ICmp: 1596 case Instruction::Select: { 1597 // Calculate the cost of this instruction. 1598 VectorType *MaskTy = VectorType::get(Builder.getInt1Ty(), VL.size()); 1599 int ScalarCost = VecTy->getNumElements() * 1600 TTI->getCmpSelInstrCost(Opcode, ScalarTy, Builder.getInt1Ty()); 1601 int VecCost = TTI->getCmpSelInstrCost(Opcode, VecTy, MaskTy); 1602 return VecCost - ScalarCost; 1603 } 1604 case Instruction::Add: 1605 case Instruction::FAdd: 1606 case Instruction::Sub: 1607 case Instruction::FSub: 1608 case Instruction::Mul: 1609 case Instruction::FMul: 1610 case Instruction::UDiv: 1611 case Instruction::SDiv: 1612 case Instruction::FDiv: 1613 case Instruction::URem: 1614 case Instruction::SRem: 1615 case Instruction::FRem: 1616 case Instruction::Shl: 1617 case Instruction::LShr: 1618 case Instruction::AShr: 1619 case Instruction::And: 1620 case Instruction::Or: 1621 case Instruction::Xor: { 1622 // Certain instructions can be cheaper to vectorize if they have a 1623 // constant second vector operand. 1624 TargetTransformInfo::OperandValueKind Op1VK = 1625 TargetTransformInfo::OK_AnyValue; 1626 TargetTransformInfo::OperandValueKind Op2VK = 1627 TargetTransformInfo::OK_UniformConstantValue; 1628 TargetTransformInfo::OperandValueProperties Op1VP = 1629 TargetTransformInfo::OP_None; 1630 TargetTransformInfo::OperandValueProperties Op2VP = 1631 TargetTransformInfo::OP_None; 1632 1633 // If all operands are exactly the same ConstantInt then set the 1634 // operand kind to OK_UniformConstantValue. 1635 // If instead not all operands are constants, then set the operand kind 1636 // to OK_AnyValue. If all operands are constants but not the same, 1637 // then set the operand kind to OK_NonUniformConstantValue. 1638 ConstantInt *CInt = nullptr; 1639 for (unsigned i = 0; i < VL.size(); ++i) { 1640 const Instruction *I = cast<Instruction>(VL[i]); 1641 if (!isa<ConstantInt>(I->getOperand(1))) { 1642 Op2VK = TargetTransformInfo::OK_AnyValue; 1643 break; 1644 } 1645 if (i == 0) { 1646 CInt = cast<ConstantInt>(I->getOperand(1)); 1647 continue; 1648 } 1649 if (Op2VK == TargetTransformInfo::OK_UniformConstantValue && 1650 CInt != cast<ConstantInt>(I->getOperand(1))) 1651 Op2VK = TargetTransformInfo::OK_NonUniformConstantValue; 1652 } 1653 // FIXME: Currently cost of model modification for division by power of 1654 // 2 is handled for X86 and AArch64. Add support for other targets. 1655 if (Op2VK == TargetTransformInfo::OK_UniformConstantValue && CInt && 1656 CInt->getValue().isPowerOf2()) 1657 Op2VP = TargetTransformInfo::OP_PowerOf2; 1658 1659 int ScalarCost = VecTy->getNumElements() * 1660 TTI->getArithmeticInstrCost(Opcode, ScalarTy, Op1VK, 1661 Op2VK, Op1VP, Op2VP); 1662 int VecCost = TTI->getArithmeticInstrCost(Opcode, VecTy, Op1VK, Op2VK, 1663 Op1VP, Op2VP); 1664 return VecCost - ScalarCost; 1665 } 1666 case Instruction::GetElementPtr: { 1667 TargetTransformInfo::OperandValueKind Op1VK = 1668 TargetTransformInfo::OK_AnyValue; 1669 TargetTransformInfo::OperandValueKind Op2VK = 1670 TargetTransformInfo::OK_UniformConstantValue; 1671 1672 int ScalarCost = 1673 VecTy->getNumElements() * 1674 TTI->getArithmeticInstrCost(Instruction::Add, ScalarTy, Op1VK, Op2VK); 1675 int VecCost = 1676 TTI->getArithmeticInstrCost(Instruction::Add, VecTy, Op1VK, Op2VK); 1677 1678 return VecCost - ScalarCost; 1679 } 1680 case Instruction::Load: { 1681 // Cost of wide load - cost of scalar loads. 1682 unsigned alignment = dyn_cast<LoadInst>(VL0)->getAlignment(); 1683 int ScalarLdCost = VecTy->getNumElements() * 1684 TTI->getMemoryOpCost(Instruction::Load, ScalarTy, alignment, 0); 1685 int VecLdCost = TTI->getMemoryOpCost(Instruction::Load, 1686 VecTy, alignment, 0); 1687 return VecLdCost - ScalarLdCost; 1688 } 1689 case Instruction::Store: { 1690 // We know that we can merge the stores. Calculate the cost. 1691 unsigned alignment = dyn_cast<StoreInst>(VL0)->getAlignment(); 1692 int ScalarStCost = VecTy->getNumElements() * 1693 TTI->getMemoryOpCost(Instruction::Store, ScalarTy, alignment, 0); 1694 int VecStCost = TTI->getMemoryOpCost(Instruction::Store, 1695 VecTy, alignment, 0); 1696 return VecStCost - ScalarStCost; 1697 } 1698 case Instruction::Call: { 1699 CallInst *CI = cast<CallInst>(VL0); 1700 Intrinsic::ID ID = getVectorIntrinsicIDForCall(CI, TLI); 1701 1702 // Calculate the cost of the scalar and vector calls. 1703 SmallVector<Type*, 4> ScalarTys, VecTys; 1704 for (unsigned op = 0, opc = CI->getNumArgOperands(); op!= opc; ++op) { 1705 ScalarTys.push_back(CI->getArgOperand(op)->getType()); 1706 VecTys.push_back(VectorType::get(CI->getArgOperand(op)->getType(), 1707 VecTy->getNumElements())); 1708 } 1709 1710 FastMathFlags FMF; 1711 if (auto *FPMO = dyn_cast<FPMathOperator>(CI)) 1712 FMF = FPMO->getFastMathFlags(); 1713 1714 int ScalarCallCost = VecTy->getNumElements() * 1715 TTI->getIntrinsicInstrCost(ID, ScalarTy, ScalarTys, FMF); 1716 1717 int VecCallCost = TTI->getIntrinsicInstrCost(ID, VecTy, VecTys, FMF); 1718 1719 DEBUG(dbgs() << "SLP: Call cost "<< VecCallCost - ScalarCallCost 1720 << " (" << VecCallCost << "-" << ScalarCallCost << ")" 1721 << " for " << *CI << "\n"); 1722 1723 return VecCallCost - ScalarCallCost; 1724 } 1725 case Instruction::ShuffleVector: { 1726 TargetTransformInfo::OperandValueKind Op1VK = 1727 TargetTransformInfo::OK_AnyValue; 1728 TargetTransformInfo::OperandValueKind Op2VK = 1729 TargetTransformInfo::OK_AnyValue; 1730 int ScalarCost = 0; 1731 int VecCost = 0; 1732 for (Value *i : VL) { 1733 Instruction *I = cast<Instruction>(i); 1734 if (!I) 1735 break; 1736 ScalarCost += 1737 TTI->getArithmeticInstrCost(I->getOpcode(), ScalarTy, Op1VK, Op2VK); 1738 } 1739 // VecCost is equal to sum of the cost of creating 2 vectors 1740 // and the cost of creating shuffle. 1741 Instruction *I0 = cast<Instruction>(VL[0]); 1742 VecCost = 1743 TTI->getArithmeticInstrCost(I0->getOpcode(), VecTy, Op1VK, Op2VK); 1744 Instruction *I1 = cast<Instruction>(VL[1]); 1745 VecCost += 1746 TTI->getArithmeticInstrCost(I1->getOpcode(), VecTy, Op1VK, Op2VK); 1747 VecCost += 1748 TTI->getShuffleCost(TargetTransformInfo::SK_Alternate, VecTy, 0); 1749 return VecCost - ScalarCost; 1750 } 1751 default: 1752 llvm_unreachable("Unknown instruction"); 1753 } 1754 } 1755 1756 bool BoUpSLP::isFullyVectorizableTinyTree() { 1757 DEBUG(dbgs() << "SLP: Check whether the tree with height " << 1758 VectorizableTree.size() << " is fully vectorizable .\n"); 1759 1760 // We only handle trees of height 2. 1761 if (VectorizableTree.size() != 2) 1762 return false; 1763 1764 // Handle splat and all-constants stores. 1765 if (!VectorizableTree[0].NeedToGather && 1766 (allConstant(VectorizableTree[1].Scalars) || 1767 isSplat(VectorizableTree[1].Scalars))) 1768 return true; 1769 1770 // Gathering cost would be too much for tiny trees. 1771 if (VectorizableTree[0].NeedToGather || VectorizableTree[1].NeedToGather) 1772 return false; 1773 1774 return true; 1775 } 1776 1777 int BoUpSLP::getSpillCost() { 1778 // Walk from the bottom of the tree to the top, tracking which values are 1779 // live. When we see a call instruction that is not part of our tree, 1780 // query TTI to see if there is a cost to keeping values live over it 1781 // (for example, if spills and fills are required). 1782 unsigned BundleWidth = VectorizableTree.front().Scalars.size(); 1783 int Cost = 0; 1784 1785 SmallPtrSet<Instruction*, 4> LiveValues; 1786 Instruction *PrevInst = nullptr; 1787 1788 for (const auto &N : VectorizableTree) { 1789 Instruction *Inst = dyn_cast<Instruction>(N.Scalars[0]); 1790 if (!Inst) 1791 continue; 1792 1793 if (!PrevInst) { 1794 PrevInst = Inst; 1795 continue; 1796 } 1797 1798 // Update LiveValues. 1799 LiveValues.erase(PrevInst); 1800 for (auto &J : PrevInst->operands()) { 1801 if (isa<Instruction>(&*J) && ScalarToTreeEntry.count(&*J)) 1802 LiveValues.insert(cast<Instruction>(&*J)); 1803 } 1804 1805 DEBUG( 1806 dbgs() << "SLP: #LV: " << LiveValues.size(); 1807 for (auto *X : LiveValues) 1808 dbgs() << " " << X->getName(); 1809 dbgs() << ", Looking at "; 1810 Inst->dump(); 1811 ); 1812 1813 // Now find the sequence of instructions between PrevInst and Inst. 1814 BasicBlock::reverse_iterator InstIt(Inst->getIterator()), 1815 PrevInstIt(PrevInst->getIterator()); 1816 --PrevInstIt; 1817 while (InstIt != PrevInstIt) { 1818 if (PrevInstIt == PrevInst->getParent()->rend()) { 1819 PrevInstIt = Inst->getParent()->rbegin(); 1820 continue; 1821 } 1822 1823 if (isa<CallInst>(&*PrevInstIt) && &*PrevInstIt != PrevInst) { 1824 SmallVector<Type*, 4> V; 1825 for (auto *II : LiveValues) 1826 V.push_back(VectorType::get(II->getType(), BundleWidth)); 1827 Cost += TTI->getCostOfKeepingLiveOverCall(V); 1828 } 1829 1830 ++PrevInstIt; 1831 } 1832 1833 PrevInst = Inst; 1834 } 1835 1836 return Cost; 1837 } 1838 1839 int BoUpSLP::getTreeCost() { 1840 int Cost = 0; 1841 DEBUG(dbgs() << "SLP: Calculating cost for tree of size " << 1842 VectorizableTree.size() << ".\n"); 1843 1844 // We only vectorize tiny trees if it is fully vectorizable. 1845 if (VectorizableTree.size() < 3 && !isFullyVectorizableTinyTree()) { 1846 if (VectorizableTree.empty()) { 1847 assert(!ExternalUses.size() && "We should not have any external users"); 1848 } 1849 return INT_MAX; 1850 } 1851 1852 unsigned BundleWidth = VectorizableTree[0].Scalars.size(); 1853 1854 for (TreeEntry &TE : VectorizableTree) { 1855 int C = getEntryCost(&TE); 1856 DEBUG(dbgs() << "SLP: Adding cost " << C << " for bundle that starts with " 1857 << *TE.Scalars[0] << ".\n"); 1858 Cost += C; 1859 } 1860 1861 SmallSet<Value *, 16> ExtractCostCalculated; 1862 int ExtractCost = 0; 1863 for (ExternalUser &EU : ExternalUses) { 1864 // We only add extract cost once for the same scalar. 1865 if (!ExtractCostCalculated.insert(EU.Scalar).second) 1866 continue; 1867 1868 // Uses by ephemeral values are free (because the ephemeral value will be 1869 // removed prior to code generation, and so the extraction will be 1870 // removed as well). 1871 if (EphValues.count(EU.User)) 1872 continue; 1873 1874 // If we plan to rewrite the tree in a smaller type, we will need to sign 1875 // extend the extracted value back to the original type. Here, we account 1876 // for the extract and the added cost of the sign extend if needed. 1877 auto *VecTy = VectorType::get(EU.Scalar->getType(), BundleWidth); 1878 auto *ScalarRoot = VectorizableTree[0].Scalars[0]; 1879 if (MinBWs.count(ScalarRoot)) { 1880 auto *MinTy = IntegerType::get(F->getContext(), MinBWs[ScalarRoot]); 1881 VecTy = VectorType::get(MinTy, BundleWidth); 1882 ExtractCost += TTI->getExtractWithExtendCost( 1883 Instruction::SExt, EU.Scalar->getType(), VecTy, EU.Lane); 1884 } else { 1885 ExtractCost += 1886 TTI->getVectorInstrCost(Instruction::ExtractElement, VecTy, EU.Lane); 1887 } 1888 } 1889 1890 int SpillCost = getSpillCost(); 1891 Cost += SpillCost + ExtractCost; 1892 1893 DEBUG(dbgs() << "SLP: Spill Cost = " << SpillCost << ".\n" 1894 << "SLP: Extract Cost = " << ExtractCost << ".\n" 1895 << "SLP: Total Cost = " << Cost << ".\n"); 1896 return Cost; 1897 } 1898 1899 int BoUpSLP::getGatherCost(Type *Ty) { 1900 int Cost = 0; 1901 for (unsigned i = 0, e = cast<VectorType>(Ty)->getNumElements(); i < e; ++i) 1902 Cost += TTI->getVectorInstrCost(Instruction::InsertElement, Ty, i); 1903 return Cost; 1904 } 1905 1906 int BoUpSLP::getGatherCost(ArrayRef<Value *> VL) { 1907 // Find the type of the operands in VL. 1908 Type *ScalarTy = VL[0]->getType(); 1909 if (StoreInst *SI = dyn_cast<StoreInst>(VL[0])) 1910 ScalarTy = SI->getValueOperand()->getType(); 1911 VectorType *VecTy = VectorType::get(ScalarTy, VL.size()); 1912 // Find the cost of inserting/extracting values from the vector. 1913 return getGatherCost(VecTy); 1914 } 1915 1916 // Reorder commutative operations in alternate shuffle if the resulting vectors 1917 // are consecutive loads. This would allow us to vectorize the tree. 1918 // If we have something like- 1919 // load a[0] - load b[0] 1920 // load b[1] + load a[1] 1921 // load a[2] - load b[2] 1922 // load a[3] + load b[3] 1923 // Reordering the second load b[1] load a[1] would allow us to vectorize this 1924 // code. 1925 void BoUpSLP::reorderAltShuffleOperands(ArrayRef<Value *> VL, 1926 SmallVectorImpl<Value *> &Left, 1927 SmallVectorImpl<Value *> &Right) { 1928 // Push left and right operands of binary operation into Left and Right 1929 for (Value *i : VL) { 1930 Left.push_back(cast<Instruction>(i)->getOperand(0)); 1931 Right.push_back(cast<Instruction>(i)->getOperand(1)); 1932 } 1933 1934 // Reorder if we have a commutative operation and consecutive access 1935 // are on either side of the alternate instructions. 1936 for (unsigned j = 0; j < VL.size() - 1; ++j) { 1937 if (LoadInst *L = dyn_cast<LoadInst>(Left[j])) { 1938 if (LoadInst *L1 = dyn_cast<LoadInst>(Right[j + 1])) { 1939 Instruction *VL1 = cast<Instruction>(VL[j]); 1940 Instruction *VL2 = cast<Instruction>(VL[j + 1]); 1941 if (VL1->isCommutative() && isConsecutiveAccess(L, L1, *DL, *SE)) { 1942 std::swap(Left[j], Right[j]); 1943 continue; 1944 } else if (VL2->isCommutative() && 1945 isConsecutiveAccess(L, L1, *DL, *SE)) { 1946 std::swap(Left[j + 1], Right[j + 1]); 1947 continue; 1948 } 1949 // else unchanged 1950 } 1951 } 1952 if (LoadInst *L = dyn_cast<LoadInst>(Right[j])) { 1953 if (LoadInst *L1 = dyn_cast<LoadInst>(Left[j + 1])) { 1954 Instruction *VL1 = cast<Instruction>(VL[j]); 1955 Instruction *VL2 = cast<Instruction>(VL[j + 1]); 1956 if (VL1->isCommutative() && isConsecutiveAccess(L, L1, *DL, *SE)) { 1957 std::swap(Left[j], Right[j]); 1958 continue; 1959 } else if (VL2->isCommutative() && 1960 isConsecutiveAccess(L, L1, *DL, *SE)) { 1961 std::swap(Left[j + 1], Right[j + 1]); 1962 continue; 1963 } 1964 // else unchanged 1965 } 1966 } 1967 } 1968 } 1969 1970 // Return true if I should be commuted before adding it's left and right 1971 // operands to the arrays Left and Right. 1972 // 1973 // The vectorizer is trying to either have all elements one side being 1974 // instruction with the same opcode to enable further vectorization, or having 1975 // a splat to lower the vectorizing cost. 1976 static bool shouldReorderOperands(int i, Instruction &I, 1977 SmallVectorImpl<Value *> &Left, 1978 SmallVectorImpl<Value *> &Right, 1979 bool AllSameOpcodeLeft, 1980 bool AllSameOpcodeRight, bool SplatLeft, 1981 bool SplatRight) { 1982 Value *VLeft = I.getOperand(0); 1983 Value *VRight = I.getOperand(1); 1984 // If we have "SplatRight", try to see if commuting is needed to preserve it. 1985 if (SplatRight) { 1986 if (VRight == Right[i - 1]) 1987 // Preserve SplatRight 1988 return false; 1989 if (VLeft == Right[i - 1]) { 1990 // Commuting would preserve SplatRight, but we don't want to break 1991 // SplatLeft either, i.e. preserve the original order if possible. 1992 // (FIXME: why do we care?) 1993 if (SplatLeft && VLeft == Left[i - 1]) 1994 return false; 1995 return true; 1996 } 1997 } 1998 // Symmetrically handle Right side. 1999 if (SplatLeft) { 2000 if (VLeft == Left[i - 1]) 2001 // Preserve SplatLeft 2002 return false; 2003 if (VRight == Left[i - 1]) 2004 return true; 2005 } 2006 2007 Instruction *ILeft = dyn_cast<Instruction>(VLeft); 2008 Instruction *IRight = dyn_cast<Instruction>(VRight); 2009 2010 // If we have "AllSameOpcodeRight", try to see if the left operands preserves 2011 // it and not the right, in this case we want to commute. 2012 if (AllSameOpcodeRight) { 2013 unsigned RightPrevOpcode = cast<Instruction>(Right[i - 1])->getOpcode(); 2014 if (IRight && RightPrevOpcode == IRight->getOpcode()) 2015 // Do not commute, a match on the right preserves AllSameOpcodeRight 2016 return false; 2017 if (ILeft && RightPrevOpcode == ILeft->getOpcode()) { 2018 // We have a match and may want to commute, but first check if there is 2019 // not also a match on the existing operands on the Left to preserve 2020 // AllSameOpcodeLeft, i.e. preserve the original order if possible. 2021 // (FIXME: why do we care?) 2022 if (AllSameOpcodeLeft && ILeft && 2023 cast<Instruction>(Left[i - 1])->getOpcode() == ILeft->getOpcode()) 2024 return false; 2025 return true; 2026 } 2027 } 2028 // Symmetrically handle Left side. 2029 if (AllSameOpcodeLeft) { 2030 unsigned LeftPrevOpcode = cast<Instruction>(Left[i - 1])->getOpcode(); 2031 if (ILeft && LeftPrevOpcode == ILeft->getOpcode()) 2032 return false; 2033 if (IRight && LeftPrevOpcode == IRight->getOpcode()) 2034 return true; 2035 } 2036 return false; 2037 } 2038 2039 void BoUpSLP::reorderInputsAccordingToOpcode(ArrayRef<Value *> VL, 2040 SmallVectorImpl<Value *> &Left, 2041 SmallVectorImpl<Value *> &Right) { 2042 2043 if (VL.size()) { 2044 // Peel the first iteration out of the loop since there's nothing 2045 // interesting to do anyway and it simplifies the checks in the loop. 2046 auto VLeft = cast<Instruction>(VL[0])->getOperand(0); 2047 auto VRight = cast<Instruction>(VL[0])->getOperand(1); 2048 if (!isa<Instruction>(VRight) && isa<Instruction>(VLeft)) 2049 // Favor having instruction to the right. FIXME: why? 2050 std::swap(VLeft, VRight); 2051 Left.push_back(VLeft); 2052 Right.push_back(VRight); 2053 } 2054 2055 // Keep track if we have instructions with all the same opcode on one side. 2056 bool AllSameOpcodeLeft = isa<Instruction>(Left[0]); 2057 bool AllSameOpcodeRight = isa<Instruction>(Right[0]); 2058 // Keep track if we have one side with all the same value (broadcast). 2059 bool SplatLeft = true; 2060 bool SplatRight = true; 2061 2062 for (unsigned i = 1, e = VL.size(); i != e; ++i) { 2063 Instruction *I = cast<Instruction>(VL[i]); 2064 assert(I->isCommutative() && "Can only process commutative instruction"); 2065 // Commute to favor either a splat or maximizing having the same opcodes on 2066 // one side. 2067 if (shouldReorderOperands(i, *I, Left, Right, AllSameOpcodeLeft, 2068 AllSameOpcodeRight, SplatLeft, SplatRight)) { 2069 Left.push_back(I->getOperand(1)); 2070 Right.push_back(I->getOperand(0)); 2071 } else { 2072 Left.push_back(I->getOperand(0)); 2073 Right.push_back(I->getOperand(1)); 2074 } 2075 // Update Splat* and AllSameOpcode* after the insertion. 2076 SplatRight = SplatRight && (Right[i - 1] == Right[i]); 2077 SplatLeft = SplatLeft && (Left[i - 1] == Left[i]); 2078 AllSameOpcodeLeft = AllSameOpcodeLeft && isa<Instruction>(Left[i]) && 2079 (cast<Instruction>(Left[i - 1])->getOpcode() == 2080 cast<Instruction>(Left[i])->getOpcode()); 2081 AllSameOpcodeRight = AllSameOpcodeRight && isa<Instruction>(Right[i]) && 2082 (cast<Instruction>(Right[i - 1])->getOpcode() == 2083 cast<Instruction>(Right[i])->getOpcode()); 2084 } 2085 2086 // If one operand end up being broadcast, return this operand order. 2087 if (SplatRight || SplatLeft) 2088 return; 2089 2090 // Finally check if we can get longer vectorizable chain by reordering 2091 // without breaking the good operand order detected above. 2092 // E.g. If we have something like- 2093 // load a[0] load b[0] 2094 // load b[1] load a[1] 2095 // load a[2] load b[2] 2096 // load a[3] load b[3] 2097 // Reordering the second load b[1] load a[1] would allow us to vectorize 2098 // this code and we still retain AllSameOpcode property. 2099 // FIXME: This load reordering might break AllSameOpcode in some rare cases 2100 // such as- 2101 // add a[0],c[0] load b[0] 2102 // add a[1],c[2] load b[1] 2103 // b[2] load b[2] 2104 // add a[3],c[3] load b[3] 2105 for (unsigned j = 0; j < VL.size() - 1; ++j) { 2106 if (LoadInst *L = dyn_cast<LoadInst>(Left[j])) { 2107 if (LoadInst *L1 = dyn_cast<LoadInst>(Right[j + 1])) { 2108 if (isConsecutiveAccess(L, L1, *DL, *SE)) { 2109 std::swap(Left[j + 1], Right[j + 1]); 2110 continue; 2111 } 2112 } 2113 } 2114 if (LoadInst *L = dyn_cast<LoadInst>(Right[j])) { 2115 if (LoadInst *L1 = dyn_cast<LoadInst>(Left[j + 1])) { 2116 if (isConsecutiveAccess(L, L1, *DL, *SE)) { 2117 std::swap(Left[j + 1], Right[j + 1]); 2118 continue; 2119 } 2120 } 2121 } 2122 // else unchanged 2123 } 2124 } 2125 2126 void BoUpSLP::setInsertPointAfterBundle(ArrayRef<Value *> VL) { 2127 Instruction *VL0 = cast<Instruction>(VL[0]); 2128 BasicBlock::iterator NextInst(VL0); 2129 ++NextInst; 2130 Builder.SetInsertPoint(VL0->getParent(), NextInst); 2131 Builder.SetCurrentDebugLocation(VL0->getDebugLoc()); 2132 } 2133 2134 Value *BoUpSLP::Gather(ArrayRef<Value *> VL, VectorType *Ty) { 2135 Value *Vec = UndefValue::get(Ty); 2136 // Generate the 'InsertElement' instruction. 2137 for (unsigned i = 0; i < Ty->getNumElements(); ++i) { 2138 Vec = Builder.CreateInsertElement(Vec, VL[i], Builder.getInt32(i)); 2139 if (Instruction *Insrt = dyn_cast<Instruction>(Vec)) { 2140 GatherSeq.insert(Insrt); 2141 CSEBlocks.insert(Insrt->getParent()); 2142 2143 // Add to our 'need-to-extract' list. 2144 if (ScalarToTreeEntry.count(VL[i])) { 2145 int Idx = ScalarToTreeEntry[VL[i]]; 2146 TreeEntry *E = &VectorizableTree[Idx]; 2147 // Find which lane we need to extract. 2148 int FoundLane = -1; 2149 for (unsigned Lane = 0, LE = VL.size(); Lane != LE; ++Lane) { 2150 // Is this the lane of the scalar that we are looking for ? 2151 if (E->Scalars[Lane] == VL[i]) { 2152 FoundLane = Lane; 2153 break; 2154 } 2155 } 2156 assert(FoundLane >= 0 && "Could not find the correct lane"); 2157 ExternalUses.push_back(ExternalUser(VL[i], Insrt, FoundLane)); 2158 } 2159 } 2160 } 2161 2162 return Vec; 2163 } 2164 2165 Value *BoUpSLP::alreadyVectorized(ArrayRef<Value *> VL) const { 2166 SmallDenseMap<Value*, int>::const_iterator Entry 2167 = ScalarToTreeEntry.find(VL[0]); 2168 if (Entry != ScalarToTreeEntry.end()) { 2169 int Idx = Entry->second; 2170 const TreeEntry *En = &VectorizableTree[Idx]; 2171 if (En->isSame(VL) && En->VectorizedValue) 2172 return En->VectorizedValue; 2173 } 2174 return nullptr; 2175 } 2176 2177 Value *BoUpSLP::vectorizeTree(ArrayRef<Value *> VL) { 2178 if (ScalarToTreeEntry.count(VL[0])) { 2179 int Idx = ScalarToTreeEntry[VL[0]]; 2180 TreeEntry *E = &VectorizableTree[Idx]; 2181 if (E->isSame(VL)) 2182 return vectorizeTree(E); 2183 } 2184 2185 Type *ScalarTy = VL[0]->getType(); 2186 if (StoreInst *SI = dyn_cast<StoreInst>(VL[0])) 2187 ScalarTy = SI->getValueOperand()->getType(); 2188 VectorType *VecTy = VectorType::get(ScalarTy, VL.size()); 2189 2190 return Gather(VL, VecTy); 2191 } 2192 2193 Value *BoUpSLP::vectorizeTree(TreeEntry *E) { 2194 IRBuilder<>::InsertPointGuard Guard(Builder); 2195 2196 if (E->VectorizedValue) { 2197 DEBUG(dbgs() << "SLP: Diamond merged for " << *E->Scalars[0] << ".\n"); 2198 return E->VectorizedValue; 2199 } 2200 2201 Instruction *VL0 = cast<Instruction>(E->Scalars[0]); 2202 Type *ScalarTy = VL0->getType(); 2203 if (StoreInst *SI = dyn_cast<StoreInst>(VL0)) 2204 ScalarTy = SI->getValueOperand()->getType(); 2205 VectorType *VecTy = VectorType::get(ScalarTy, E->Scalars.size()); 2206 2207 if (E->NeedToGather) { 2208 setInsertPointAfterBundle(E->Scalars); 2209 return Gather(E->Scalars, VecTy); 2210 } 2211 2212 unsigned Opcode = getSameOpcode(E->Scalars); 2213 2214 switch (Opcode) { 2215 case Instruction::PHI: { 2216 PHINode *PH = dyn_cast<PHINode>(VL0); 2217 Builder.SetInsertPoint(PH->getParent()->getFirstNonPHI()); 2218 Builder.SetCurrentDebugLocation(PH->getDebugLoc()); 2219 PHINode *NewPhi = Builder.CreatePHI(VecTy, PH->getNumIncomingValues()); 2220 E->VectorizedValue = NewPhi; 2221 2222 // PHINodes may have multiple entries from the same block. We want to 2223 // visit every block once. 2224 SmallSet<BasicBlock*, 4> VisitedBBs; 2225 2226 for (unsigned i = 0, e = PH->getNumIncomingValues(); i < e; ++i) { 2227 ValueList Operands; 2228 BasicBlock *IBB = PH->getIncomingBlock(i); 2229 2230 if (!VisitedBBs.insert(IBB).second) { 2231 NewPhi->addIncoming(NewPhi->getIncomingValueForBlock(IBB), IBB); 2232 continue; 2233 } 2234 2235 // Prepare the operand vector. 2236 for (Value *V : E->Scalars) 2237 Operands.push_back(cast<PHINode>(V)->getIncomingValueForBlock(IBB)); 2238 2239 Builder.SetInsertPoint(IBB->getTerminator()); 2240 Builder.SetCurrentDebugLocation(PH->getDebugLoc()); 2241 Value *Vec = vectorizeTree(Operands); 2242 NewPhi->addIncoming(Vec, IBB); 2243 } 2244 2245 assert(NewPhi->getNumIncomingValues() == PH->getNumIncomingValues() && 2246 "Invalid number of incoming values"); 2247 return NewPhi; 2248 } 2249 2250 case Instruction::ExtractElement: { 2251 if (canReuseExtract(E->Scalars, Instruction::ExtractElement)) { 2252 Value *V = VL0->getOperand(0); 2253 E->VectorizedValue = V; 2254 return V; 2255 } 2256 return Gather(E->Scalars, VecTy); 2257 } 2258 case Instruction::ExtractValue: { 2259 if (canReuseExtract(E->Scalars, Instruction::ExtractValue)) { 2260 LoadInst *LI = cast<LoadInst>(VL0->getOperand(0)); 2261 Builder.SetInsertPoint(LI); 2262 PointerType *PtrTy = PointerType::get(VecTy, LI->getPointerAddressSpace()); 2263 Value *Ptr = Builder.CreateBitCast(LI->getOperand(0), PtrTy); 2264 LoadInst *V = Builder.CreateAlignedLoad(Ptr, LI->getAlignment()); 2265 E->VectorizedValue = V; 2266 return propagateMetadata(V, E->Scalars); 2267 } 2268 return Gather(E->Scalars, VecTy); 2269 } 2270 case Instruction::ZExt: 2271 case Instruction::SExt: 2272 case Instruction::FPToUI: 2273 case Instruction::FPToSI: 2274 case Instruction::FPExt: 2275 case Instruction::PtrToInt: 2276 case Instruction::IntToPtr: 2277 case Instruction::SIToFP: 2278 case Instruction::UIToFP: 2279 case Instruction::Trunc: 2280 case Instruction::FPTrunc: 2281 case Instruction::BitCast: { 2282 ValueList INVL; 2283 for (Value *V : E->Scalars) 2284 INVL.push_back(cast<Instruction>(V)->getOperand(0)); 2285 2286 setInsertPointAfterBundle(E->Scalars); 2287 2288 Value *InVec = vectorizeTree(INVL); 2289 2290 if (Value *V = alreadyVectorized(E->Scalars)) 2291 return V; 2292 2293 CastInst *CI = dyn_cast<CastInst>(VL0); 2294 Value *V = Builder.CreateCast(CI->getOpcode(), InVec, VecTy); 2295 E->VectorizedValue = V; 2296 ++NumVectorInstructions; 2297 return V; 2298 } 2299 case Instruction::FCmp: 2300 case Instruction::ICmp: { 2301 ValueList LHSV, RHSV; 2302 for (Value *V : E->Scalars) { 2303 LHSV.push_back(cast<Instruction>(V)->getOperand(0)); 2304 RHSV.push_back(cast<Instruction>(V)->getOperand(1)); 2305 } 2306 2307 setInsertPointAfterBundle(E->Scalars); 2308 2309 Value *L = vectorizeTree(LHSV); 2310 Value *R = vectorizeTree(RHSV); 2311 2312 if (Value *V = alreadyVectorized(E->Scalars)) 2313 return V; 2314 2315 CmpInst::Predicate P0 = cast<CmpInst>(VL0)->getPredicate(); 2316 Value *V; 2317 if (Opcode == Instruction::FCmp) 2318 V = Builder.CreateFCmp(P0, L, R); 2319 else 2320 V = Builder.CreateICmp(P0, L, R); 2321 2322 E->VectorizedValue = V; 2323 ++NumVectorInstructions; 2324 return V; 2325 } 2326 case Instruction::Select: { 2327 ValueList TrueVec, FalseVec, CondVec; 2328 for (Value *V : E->Scalars) { 2329 CondVec.push_back(cast<Instruction>(V)->getOperand(0)); 2330 TrueVec.push_back(cast<Instruction>(V)->getOperand(1)); 2331 FalseVec.push_back(cast<Instruction>(V)->getOperand(2)); 2332 } 2333 2334 setInsertPointAfterBundle(E->Scalars); 2335 2336 Value *Cond = vectorizeTree(CondVec); 2337 Value *True = vectorizeTree(TrueVec); 2338 Value *False = vectorizeTree(FalseVec); 2339 2340 if (Value *V = alreadyVectorized(E->Scalars)) 2341 return V; 2342 2343 Value *V = Builder.CreateSelect(Cond, True, False); 2344 E->VectorizedValue = V; 2345 ++NumVectorInstructions; 2346 return V; 2347 } 2348 case Instruction::Add: 2349 case Instruction::FAdd: 2350 case Instruction::Sub: 2351 case Instruction::FSub: 2352 case Instruction::Mul: 2353 case Instruction::FMul: 2354 case Instruction::UDiv: 2355 case Instruction::SDiv: 2356 case Instruction::FDiv: 2357 case Instruction::URem: 2358 case Instruction::SRem: 2359 case Instruction::FRem: 2360 case Instruction::Shl: 2361 case Instruction::LShr: 2362 case Instruction::AShr: 2363 case Instruction::And: 2364 case Instruction::Or: 2365 case Instruction::Xor: { 2366 ValueList LHSVL, RHSVL; 2367 if (isa<BinaryOperator>(VL0) && VL0->isCommutative()) 2368 reorderInputsAccordingToOpcode(E->Scalars, LHSVL, RHSVL); 2369 else 2370 for (Value *V : E->Scalars) { 2371 LHSVL.push_back(cast<Instruction>(V)->getOperand(0)); 2372 RHSVL.push_back(cast<Instruction>(V)->getOperand(1)); 2373 } 2374 2375 setInsertPointAfterBundle(E->Scalars); 2376 2377 Value *LHS = vectorizeTree(LHSVL); 2378 Value *RHS = vectorizeTree(RHSVL); 2379 2380 if (LHS == RHS && isa<Instruction>(LHS)) { 2381 assert((VL0->getOperand(0) == VL0->getOperand(1)) && "Invalid order"); 2382 } 2383 2384 if (Value *V = alreadyVectorized(E->Scalars)) 2385 return V; 2386 2387 BinaryOperator *BinOp = cast<BinaryOperator>(VL0); 2388 Value *V = Builder.CreateBinOp(BinOp->getOpcode(), LHS, RHS); 2389 E->VectorizedValue = V; 2390 propagateIRFlags(E->VectorizedValue, E->Scalars); 2391 ++NumVectorInstructions; 2392 2393 if (Instruction *I = dyn_cast<Instruction>(V)) 2394 return propagateMetadata(I, E->Scalars); 2395 2396 return V; 2397 } 2398 case Instruction::Load: { 2399 // Loads are inserted at the head of the tree because we don't want to 2400 // sink them all the way down past store instructions. 2401 setInsertPointAfterBundle(E->Scalars); 2402 2403 LoadInst *LI = cast<LoadInst>(VL0); 2404 Type *ScalarLoadTy = LI->getType(); 2405 unsigned AS = LI->getPointerAddressSpace(); 2406 2407 Value *VecPtr = Builder.CreateBitCast(LI->getPointerOperand(), 2408 VecTy->getPointerTo(AS)); 2409 2410 // The pointer operand uses an in-tree scalar so we add the new BitCast to 2411 // ExternalUses list to make sure that an extract will be generated in the 2412 // future. 2413 if (ScalarToTreeEntry.count(LI->getPointerOperand())) 2414 ExternalUses.push_back( 2415 ExternalUser(LI->getPointerOperand(), cast<User>(VecPtr), 0)); 2416 2417 unsigned Alignment = LI->getAlignment(); 2418 LI = Builder.CreateLoad(VecPtr); 2419 if (!Alignment) { 2420 Alignment = DL->getABITypeAlignment(ScalarLoadTy); 2421 } 2422 LI->setAlignment(Alignment); 2423 E->VectorizedValue = LI; 2424 ++NumVectorInstructions; 2425 return propagateMetadata(LI, E->Scalars); 2426 } 2427 case Instruction::Store: { 2428 StoreInst *SI = cast<StoreInst>(VL0); 2429 unsigned Alignment = SI->getAlignment(); 2430 unsigned AS = SI->getPointerAddressSpace(); 2431 2432 ValueList ValueOp; 2433 for (Value *V : E->Scalars) 2434 ValueOp.push_back(cast<StoreInst>(V)->getValueOperand()); 2435 2436 setInsertPointAfterBundle(E->Scalars); 2437 2438 Value *VecValue = vectorizeTree(ValueOp); 2439 Value *VecPtr = Builder.CreateBitCast(SI->getPointerOperand(), 2440 VecTy->getPointerTo(AS)); 2441 StoreInst *S = Builder.CreateStore(VecValue, VecPtr); 2442 2443 // The pointer operand uses an in-tree scalar so we add the new BitCast to 2444 // ExternalUses list to make sure that an extract will be generated in the 2445 // future. 2446 if (ScalarToTreeEntry.count(SI->getPointerOperand())) 2447 ExternalUses.push_back( 2448 ExternalUser(SI->getPointerOperand(), cast<User>(VecPtr), 0)); 2449 2450 if (!Alignment) { 2451 Alignment = DL->getABITypeAlignment(SI->getValueOperand()->getType()); 2452 } 2453 S->setAlignment(Alignment); 2454 E->VectorizedValue = S; 2455 ++NumVectorInstructions; 2456 return propagateMetadata(S, E->Scalars); 2457 } 2458 case Instruction::GetElementPtr: { 2459 setInsertPointAfterBundle(E->Scalars); 2460 2461 ValueList Op0VL; 2462 for (Value *V : E->Scalars) 2463 Op0VL.push_back(cast<GetElementPtrInst>(V)->getOperand(0)); 2464 2465 Value *Op0 = vectorizeTree(Op0VL); 2466 2467 std::vector<Value *> OpVecs; 2468 for (int j = 1, e = cast<GetElementPtrInst>(VL0)->getNumOperands(); j < e; 2469 ++j) { 2470 ValueList OpVL; 2471 for (Value *V : E->Scalars) 2472 OpVL.push_back(cast<GetElementPtrInst>(V)->getOperand(j)); 2473 2474 Value *OpVec = vectorizeTree(OpVL); 2475 OpVecs.push_back(OpVec); 2476 } 2477 2478 Value *V = Builder.CreateGEP( 2479 cast<GetElementPtrInst>(VL0)->getSourceElementType(), Op0, OpVecs); 2480 E->VectorizedValue = V; 2481 ++NumVectorInstructions; 2482 2483 if (Instruction *I = dyn_cast<Instruction>(V)) 2484 return propagateMetadata(I, E->Scalars); 2485 2486 return V; 2487 } 2488 case Instruction::Call: { 2489 CallInst *CI = cast<CallInst>(VL0); 2490 setInsertPointAfterBundle(E->Scalars); 2491 Function *FI; 2492 Intrinsic::ID IID = Intrinsic::not_intrinsic; 2493 Value *ScalarArg = nullptr; 2494 if (CI && (FI = CI->getCalledFunction())) { 2495 IID = FI->getIntrinsicID(); 2496 } 2497 std::vector<Value *> OpVecs; 2498 for (int j = 0, e = CI->getNumArgOperands(); j < e; ++j) { 2499 ValueList OpVL; 2500 // ctlz,cttz and powi are special intrinsics whose second argument is 2501 // a scalar. This argument should not be vectorized. 2502 if (hasVectorInstrinsicScalarOpd(IID, 1) && j == 1) { 2503 CallInst *CEI = cast<CallInst>(E->Scalars[0]); 2504 ScalarArg = CEI->getArgOperand(j); 2505 OpVecs.push_back(CEI->getArgOperand(j)); 2506 continue; 2507 } 2508 for (Value *V : E->Scalars) { 2509 CallInst *CEI = cast<CallInst>(V); 2510 OpVL.push_back(CEI->getArgOperand(j)); 2511 } 2512 2513 Value *OpVec = vectorizeTree(OpVL); 2514 DEBUG(dbgs() << "SLP: OpVec[" << j << "]: " << *OpVec << "\n"); 2515 OpVecs.push_back(OpVec); 2516 } 2517 2518 Module *M = F->getParent(); 2519 Intrinsic::ID ID = getVectorIntrinsicIDForCall(CI, TLI); 2520 Type *Tys[] = { VectorType::get(CI->getType(), E->Scalars.size()) }; 2521 Function *CF = Intrinsic::getDeclaration(M, ID, Tys); 2522 SmallVector<OperandBundleDef, 1> OpBundles; 2523 CI->getOperandBundlesAsDefs(OpBundles); 2524 Value *V = Builder.CreateCall(CF, OpVecs, OpBundles); 2525 2526 // The scalar argument uses an in-tree scalar so we add the new vectorized 2527 // call to ExternalUses list to make sure that an extract will be 2528 // generated in the future. 2529 if (ScalarArg && ScalarToTreeEntry.count(ScalarArg)) 2530 ExternalUses.push_back(ExternalUser(ScalarArg, cast<User>(V), 0)); 2531 2532 E->VectorizedValue = V; 2533 ++NumVectorInstructions; 2534 return V; 2535 } 2536 case Instruction::ShuffleVector: { 2537 ValueList LHSVL, RHSVL; 2538 assert(isa<BinaryOperator>(VL0) && "Invalid Shuffle Vector Operand"); 2539 reorderAltShuffleOperands(E->Scalars, LHSVL, RHSVL); 2540 setInsertPointAfterBundle(E->Scalars); 2541 2542 Value *LHS = vectorizeTree(LHSVL); 2543 Value *RHS = vectorizeTree(RHSVL); 2544 2545 if (Value *V = alreadyVectorized(E->Scalars)) 2546 return V; 2547 2548 // Create a vector of LHS op1 RHS 2549 BinaryOperator *BinOp0 = cast<BinaryOperator>(VL0); 2550 Value *V0 = Builder.CreateBinOp(BinOp0->getOpcode(), LHS, RHS); 2551 2552 // Create a vector of LHS op2 RHS 2553 Instruction *VL1 = cast<Instruction>(E->Scalars[1]); 2554 BinaryOperator *BinOp1 = cast<BinaryOperator>(VL1); 2555 Value *V1 = Builder.CreateBinOp(BinOp1->getOpcode(), LHS, RHS); 2556 2557 // Create shuffle to take alternate operations from the vector. 2558 // Also, gather up odd and even scalar ops to propagate IR flags to 2559 // each vector operation. 2560 ValueList OddScalars, EvenScalars; 2561 unsigned e = E->Scalars.size(); 2562 SmallVector<Constant *, 8> Mask(e); 2563 for (unsigned i = 0; i < e; ++i) { 2564 if (i & 1) { 2565 Mask[i] = Builder.getInt32(e + i); 2566 OddScalars.push_back(E->Scalars[i]); 2567 } else { 2568 Mask[i] = Builder.getInt32(i); 2569 EvenScalars.push_back(E->Scalars[i]); 2570 } 2571 } 2572 2573 Value *ShuffleMask = ConstantVector::get(Mask); 2574 propagateIRFlags(V0, EvenScalars); 2575 propagateIRFlags(V1, OddScalars); 2576 2577 Value *V = Builder.CreateShuffleVector(V0, V1, ShuffleMask); 2578 E->VectorizedValue = V; 2579 ++NumVectorInstructions; 2580 if (Instruction *I = dyn_cast<Instruction>(V)) 2581 return propagateMetadata(I, E->Scalars); 2582 2583 return V; 2584 } 2585 default: 2586 llvm_unreachable("unknown inst"); 2587 } 2588 return nullptr; 2589 } 2590 2591 Value *BoUpSLP::vectorizeTree() { 2592 2593 // All blocks must be scheduled before any instructions are inserted. 2594 for (auto &BSIter : BlocksSchedules) { 2595 scheduleBlock(BSIter.second.get()); 2596 } 2597 2598 Builder.SetInsertPoint(&F->getEntryBlock().front()); 2599 auto *VectorRoot = vectorizeTree(&VectorizableTree[0]); 2600 2601 // If the vectorized tree can be rewritten in a smaller type, we truncate the 2602 // vectorized root. InstCombine will then rewrite the entire expression. We 2603 // sign extend the extracted values below. 2604 auto *ScalarRoot = VectorizableTree[0].Scalars[0]; 2605 if (MinBWs.count(ScalarRoot)) { 2606 if (auto *I = dyn_cast<Instruction>(VectorRoot)) 2607 Builder.SetInsertPoint(&*++BasicBlock::iterator(I)); 2608 auto BundleWidth = VectorizableTree[0].Scalars.size(); 2609 auto *MinTy = IntegerType::get(F->getContext(), MinBWs[ScalarRoot]); 2610 auto *VecTy = VectorType::get(MinTy, BundleWidth); 2611 auto *Trunc = Builder.CreateTrunc(VectorRoot, VecTy); 2612 VectorizableTree[0].VectorizedValue = Trunc; 2613 } 2614 2615 DEBUG(dbgs() << "SLP: Extracting " << ExternalUses.size() << " values .\n"); 2616 2617 // Extract all of the elements with the external uses. 2618 for (const auto &ExternalUse : ExternalUses) { 2619 Value *Scalar = ExternalUse.Scalar; 2620 llvm::User *User = ExternalUse.User; 2621 2622 // Skip users that we already RAUW. This happens when one instruction 2623 // has multiple uses of the same value. 2624 if (std::find(Scalar->user_begin(), Scalar->user_end(), User) == 2625 Scalar->user_end()) 2626 continue; 2627 assert(ScalarToTreeEntry.count(Scalar) && "Invalid scalar"); 2628 2629 int Idx = ScalarToTreeEntry[Scalar]; 2630 TreeEntry *E = &VectorizableTree[Idx]; 2631 assert(!E->NeedToGather && "Extracting from a gather list"); 2632 2633 Value *Vec = E->VectorizedValue; 2634 assert(Vec && "Can't find vectorizable value"); 2635 2636 Value *Lane = Builder.getInt32(ExternalUse.Lane); 2637 // Generate extracts for out-of-tree users. 2638 // Find the insertion point for the extractelement lane. 2639 if (auto *VecI = dyn_cast<Instruction>(Vec)) { 2640 if (PHINode *PH = dyn_cast<PHINode>(User)) { 2641 for (int i = 0, e = PH->getNumIncomingValues(); i != e; ++i) { 2642 if (PH->getIncomingValue(i) == Scalar) { 2643 TerminatorInst *IncomingTerminator = 2644 PH->getIncomingBlock(i)->getTerminator(); 2645 if (isa<CatchSwitchInst>(IncomingTerminator)) { 2646 Builder.SetInsertPoint(VecI->getParent(), 2647 std::next(VecI->getIterator())); 2648 } else { 2649 Builder.SetInsertPoint(PH->getIncomingBlock(i)->getTerminator()); 2650 } 2651 Value *Ex = Builder.CreateExtractElement(Vec, Lane); 2652 if (MinBWs.count(ScalarRoot)) 2653 Ex = Builder.CreateSExt(Ex, Scalar->getType()); 2654 CSEBlocks.insert(PH->getIncomingBlock(i)); 2655 PH->setOperand(i, Ex); 2656 } 2657 } 2658 } else { 2659 Builder.SetInsertPoint(cast<Instruction>(User)); 2660 Value *Ex = Builder.CreateExtractElement(Vec, Lane); 2661 if (MinBWs.count(ScalarRoot)) 2662 Ex = Builder.CreateSExt(Ex, Scalar->getType()); 2663 CSEBlocks.insert(cast<Instruction>(User)->getParent()); 2664 User->replaceUsesOfWith(Scalar, Ex); 2665 } 2666 } else { 2667 Builder.SetInsertPoint(&F->getEntryBlock().front()); 2668 Value *Ex = Builder.CreateExtractElement(Vec, Lane); 2669 if (MinBWs.count(ScalarRoot)) 2670 Ex = Builder.CreateSExt(Ex, Scalar->getType()); 2671 CSEBlocks.insert(&F->getEntryBlock()); 2672 User->replaceUsesOfWith(Scalar, Ex); 2673 } 2674 2675 DEBUG(dbgs() << "SLP: Replaced:" << *User << ".\n"); 2676 } 2677 2678 // For each vectorized value: 2679 for (TreeEntry &EIdx : VectorizableTree) { 2680 TreeEntry *Entry = &EIdx; 2681 2682 // For each lane: 2683 for (int Lane = 0, LE = Entry->Scalars.size(); Lane != LE; ++Lane) { 2684 Value *Scalar = Entry->Scalars[Lane]; 2685 // No need to handle users of gathered values. 2686 if (Entry->NeedToGather) 2687 continue; 2688 2689 assert(Entry->VectorizedValue && "Can't find vectorizable value"); 2690 2691 Type *Ty = Scalar->getType(); 2692 if (!Ty->isVoidTy()) { 2693 #ifndef NDEBUG 2694 for (User *U : Scalar->users()) { 2695 DEBUG(dbgs() << "SLP: \tvalidating user:" << *U << ".\n"); 2696 2697 assert((ScalarToTreeEntry.count(U) || 2698 // It is legal to replace users in the ignorelist by undef. 2699 (std::find(UserIgnoreList.begin(), UserIgnoreList.end(), U) != 2700 UserIgnoreList.end())) && 2701 "Replacing out-of-tree value with undef"); 2702 } 2703 #endif 2704 Value *Undef = UndefValue::get(Ty); 2705 Scalar->replaceAllUsesWith(Undef); 2706 } 2707 DEBUG(dbgs() << "SLP: \tErasing scalar:" << *Scalar << ".\n"); 2708 eraseInstruction(cast<Instruction>(Scalar)); 2709 } 2710 } 2711 2712 Builder.ClearInsertionPoint(); 2713 2714 return VectorizableTree[0].VectorizedValue; 2715 } 2716 2717 void BoUpSLP::optimizeGatherSequence() { 2718 DEBUG(dbgs() << "SLP: Optimizing " << GatherSeq.size() 2719 << " gather sequences instructions.\n"); 2720 // LICM InsertElementInst sequences. 2721 for (Instruction *it : GatherSeq) { 2722 InsertElementInst *Insert = dyn_cast<InsertElementInst>(it); 2723 2724 if (!Insert) 2725 continue; 2726 2727 // Check if this block is inside a loop. 2728 Loop *L = LI->getLoopFor(Insert->getParent()); 2729 if (!L) 2730 continue; 2731 2732 // Check if it has a preheader. 2733 BasicBlock *PreHeader = L->getLoopPreheader(); 2734 if (!PreHeader) 2735 continue; 2736 2737 // If the vector or the element that we insert into it are 2738 // instructions that are defined in this basic block then we can't 2739 // hoist this instruction. 2740 Instruction *CurrVec = dyn_cast<Instruction>(Insert->getOperand(0)); 2741 Instruction *NewElem = dyn_cast<Instruction>(Insert->getOperand(1)); 2742 if (CurrVec && L->contains(CurrVec)) 2743 continue; 2744 if (NewElem && L->contains(NewElem)) 2745 continue; 2746 2747 // We can hoist this instruction. Move it to the pre-header. 2748 Insert->moveBefore(PreHeader->getTerminator()); 2749 } 2750 2751 // Make a list of all reachable blocks in our CSE queue. 2752 SmallVector<const DomTreeNode *, 8> CSEWorkList; 2753 CSEWorkList.reserve(CSEBlocks.size()); 2754 for (BasicBlock *BB : CSEBlocks) 2755 if (DomTreeNode *N = DT->getNode(BB)) { 2756 assert(DT->isReachableFromEntry(N)); 2757 CSEWorkList.push_back(N); 2758 } 2759 2760 // Sort blocks by domination. This ensures we visit a block after all blocks 2761 // dominating it are visited. 2762 std::stable_sort(CSEWorkList.begin(), CSEWorkList.end(), 2763 [this](const DomTreeNode *A, const DomTreeNode *B) { 2764 return DT->properlyDominates(A, B); 2765 }); 2766 2767 // Perform O(N^2) search over the gather sequences and merge identical 2768 // instructions. TODO: We can further optimize this scan if we split the 2769 // instructions into different buckets based on the insert lane. 2770 SmallVector<Instruction *, 16> Visited; 2771 for (auto I = CSEWorkList.begin(), E = CSEWorkList.end(); I != E; ++I) { 2772 assert((I == CSEWorkList.begin() || !DT->dominates(*I, *std::prev(I))) && 2773 "Worklist not sorted properly!"); 2774 BasicBlock *BB = (*I)->getBlock(); 2775 // For all instructions in blocks containing gather sequences: 2776 for (BasicBlock::iterator it = BB->begin(), e = BB->end(); it != e;) { 2777 Instruction *In = &*it++; 2778 if (!isa<InsertElementInst>(In) && !isa<ExtractElementInst>(In)) 2779 continue; 2780 2781 // Check if we can replace this instruction with any of the 2782 // visited instructions. 2783 for (Instruction *v : Visited) { 2784 if (In->isIdenticalTo(v) && 2785 DT->dominates(v->getParent(), In->getParent())) { 2786 In->replaceAllUsesWith(v); 2787 eraseInstruction(In); 2788 In = nullptr; 2789 break; 2790 } 2791 } 2792 if (In) { 2793 assert(std::find(Visited.begin(), Visited.end(), In) == Visited.end()); 2794 Visited.push_back(In); 2795 } 2796 } 2797 } 2798 CSEBlocks.clear(); 2799 GatherSeq.clear(); 2800 } 2801 2802 // Groups the instructions to a bundle (which is then a single scheduling entity) 2803 // and schedules instructions until the bundle gets ready. 2804 bool BoUpSLP::BlockScheduling::tryScheduleBundle(ArrayRef<Value *> VL, 2805 BoUpSLP *SLP) { 2806 if (isa<PHINode>(VL[0])) 2807 return true; 2808 2809 // Initialize the instruction bundle. 2810 Instruction *OldScheduleEnd = ScheduleEnd; 2811 ScheduleData *PrevInBundle = nullptr; 2812 ScheduleData *Bundle = nullptr; 2813 bool ReSchedule = false; 2814 DEBUG(dbgs() << "SLP: bundle: " << *VL[0] << "\n"); 2815 2816 // Make sure that the scheduling region contains all 2817 // instructions of the bundle. 2818 for (Value *V : VL) { 2819 if (!extendSchedulingRegion(V)) 2820 return false; 2821 } 2822 2823 for (Value *V : VL) { 2824 ScheduleData *BundleMember = getScheduleData(V); 2825 assert(BundleMember && 2826 "no ScheduleData for bundle member (maybe not in same basic block)"); 2827 if (BundleMember->IsScheduled) { 2828 // A bundle member was scheduled as single instruction before and now 2829 // needs to be scheduled as part of the bundle. We just get rid of the 2830 // existing schedule. 2831 DEBUG(dbgs() << "SLP: reset schedule because " << *BundleMember 2832 << " was already scheduled\n"); 2833 ReSchedule = true; 2834 } 2835 assert(BundleMember->isSchedulingEntity() && 2836 "bundle member already part of other bundle"); 2837 if (PrevInBundle) { 2838 PrevInBundle->NextInBundle = BundleMember; 2839 } else { 2840 Bundle = BundleMember; 2841 } 2842 BundleMember->UnscheduledDepsInBundle = 0; 2843 Bundle->UnscheduledDepsInBundle += BundleMember->UnscheduledDeps; 2844 2845 // Group the instructions to a bundle. 2846 BundleMember->FirstInBundle = Bundle; 2847 PrevInBundle = BundleMember; 2848 } 2849 if (ScheduleEnd != OldScheduleEnd) { 2850 // The scheduling region got new instructions at the lower end (or it is a 2851 // new region for the first bundle). This makes it necessary to 2852 // recalculate all dependencies. 2853 // It is seldom that this needs to be done a second time after adding the 2854 // initial bundle to the region. 2855 for (auto *I = ScheduleStart; I != ScheduleEnd; I = I->getNextNode()) { 2856 ScheduleData *SD = getScheduleData(I); 2857 SD->clearDependencies(); 2858 } 2859 ReSchedule = true; 2860 } 2861 if (ReSchedule) { 2862 resetSchedule(); 2863 initialFillReadyList(ReadyInsts); 2864 } 2865 2866 DEBUG(dbgs() << "SLP: try schedule bundle " << *Bundle << " in block " 2867 << BB->getName() << "\n"); 2868 2869 calculateDependencies(Bundle, true, SLP); 2870 2871 // Now try to schedule the new bundle. As soon as the bundle is "ready" it 2872 // means that there are no cyclic dependencies and we can schedule it. 2873 // Note that's important that we don't "schedule" the bundle yet (see 2874 // cancelScheduling). 2875 while (!Bundle->isReady() && !ReadyInsts.empty()) { 2876 2877 ScheduleData *pickedSD = ReadyInsts.back(); 2878 ReadyInsts.pop_back(); 2879 2880 if (pickedSD->isSchedulingEntity() && pickedSD->isReady()) { 2881 schedule(pickedSD, ReadyInsts); 2882 } 2883 } 2884 if (!Bundle->isReady()) { 2885 cancelScheduling(VL); 2886 return false; 2887 } 2888 return true; 2889 } 2890 2891 void BoUpSLP::BlockScheduling::cancelScheduling(ArrayRef<Value *> VL) { 2892 if (isa<PHINode>(VL[0])) 2893 return; 2894 2895 ScheduleData *Bundle = getScheduleData(VL[0]); 2896 DEBUG(dbgs() << "SLP: cancel scheduling of " << *Bundle << "\n"); 2897 assert(!Bundle->IsScheduled && 2898 "Can't cancel bundle which is already scheduled"); 2899 assert(Bundle->isSchedulingEntity() && Bundle->isPartOfBundle() && 2900 "tried to unbundle something which is not a bundle"); 2901 2902 // Un-bundle: make single instructions out of the bundle. 2903 ScheduleData *BundleMember = Bundle; 2904 while (BundleMember) { 2905 assert(BundleMember->FirstInBundle == Bundle && "corrupt bundle links"); 2906 BundleMember->FirstInBundle = BundleMember; 2907 ScheduleData *Next = BundleMember->NextInBundle; 2908 BundleMember->NextInBundle = nullptr; 2909 BundleMember->UnscheduledDepsInBundle = BundleMember->UnscheduledDeps; 2910 if (BundleMember->UnscheduledDepsInBundle == 0) { 2911 ReadyInsts.insert(BundleMember); 2912 } 2913 BundleMember = Next; 2914 } 2915 } 2916 2917 bool BoUpSLP::BlockScheduling::extendSchedulingRegion(Value *V) { 2918 if (getScheduleData(V)) 2919 return true; 2920 Instruction *I = dyn_cast<Instruction>(V); 2921 assert(I && "bundle member must be an instruction"); 2922 assert(!isa<PHINode>(I) && "phi nodes don't need to be scheduled"); 2923 if (!ScheduleStart) { 2924 // It's the first instruction in the new region. 2925 initScheduleData(I, I->getNextNode(), nullptr, nullptr); 2926 ScheduleStart = I; 2927 ScheduleEnd = I->getNextNode(); 2928 assert(ScheduleEnd && "tried to vectorize a TerminatorInst?"); 2929 DEBUG(dbgs() << "SLP: initialize schedule region to " << *I << "\n"); 2930 return true; 2931 } 2932 // Search up and down at the same time, because we don't know if the new 2933 // instruction is above or below the existing scheduling region. 2934 BasicBlock::reverse_iterator UpIter(ScheduleStart->getIterator()); 2935 BasicBlock::reverse_iterator UpperEnd = BB->rend(); 2936 BasicBlock::iterator DownIter(ScheduleEnd); 2937 BasicBlock::iterator LowerEnd = BB->end(); 2938 for (;;) { 2939 if (++ScheduleRegionSize > ScheduleRegionSizeLimit) { 2940 DEBUG(dbgs() << "SLP: exceeded schedule region size limit\n"); 2941 return false; 2942 } 2943 2944 if (UpIter != UpperEnd) { 2945 if (&*UpIter == I) { 2946 initScheduleData(I, ScheduleStart, nullptr, FirstLoadStoreInRegion); 2947 ScheduleStart = I; 2948 DEBUG(dbgs() << "SLP: extend schedule region start to " << *I << "\n"); 2949 return true; 2950 } 2951 UpIter++; 2952 } 2953 if (DownIter != LowerEnd) { 2954 if (&*DownIter == I) { 2955 initScheduleData(ScheduleEnd, I->getNextNode(), LastLoadStoreInRegion, 2956 nullptr); 2957 ScheduleEnd = I->getNextNode(); 2958 assert(ScheduleEnd && "tried to vectorize a TerminatorInst?"); 2959 DEBUG(dbgs() << "SLP: extend schedule region end to " << *I << "\n"); 2960 return true; 2961 } 2962 DownIter++; 2963 } 2964 assert((UpIter != UpperEnd || DownIter != LowerEnd) && 2965 "instruction not found in block"); 2966 } 2967 return true; 2968 } 2969 2970 void BoUpSLP::BlockScheduling::initScheduleData(Instruction *FromI, 2971 Instruction *ToI, 2972 ScheduleData *PrevLoadStore, 2973 ScheduleData *NextLoadStore) { 2974 ScheduleData *CurrentLoadStore = PrevLoadStore; 2975 for (Instruction *I = FromI; I != ToI; I = I->getNextNode()) { 2976 ScheduleData *SD = ScheduleDataMap[I]; 2977 if (!SD) { 2978 // Allocate a new ScheduleData for the instruction. 2979 if (ChunkPos >= ChunkSize) { 2980 ScheduleDataChunks.push_back( 2981 llvm::make_unique<ScheduleData[]>(ChunkSize)); 2982 ChunkPos = 0; 2983 } 2984 SD = &(ScheduleDataChunks.back()[ChunkPos++]); 2985 ScheduleDataMap[I] = SD; 2986 SD->Inst = I; 2987 } 2988 assert(!isInSchedulingRegion(SD) && 2989 "new ScheduleData already in scheduling region"); 2990 SD->init(SchedulingRegionID); 2991 2992 if (I->mayReadOrWriteMemory()) { 2993 // Update the linked list of memory accessing instructions. 2994 if (CurrentLoadStore) { 2995 CurrentLoadStore->NextLoadStore = SD; 2996 } else { 2997 FirstLoadStoreInRegion = SD; 2998 } 2999 CurrentLoadStore = SD; 3000 } 3001 } 3002 if (NextLoadStore) { 3003 if (CurrentLoadStore) 3004 CurrentLoadStore->NextLoadStore = NextLoadStore; 3005 } else { 3006 LastLoadStoreInRegion = CurrentLoadStore; 3007 } 3008 } 3009 3010 void BoUpSLP::BlockScheduling::calculateDependencies(ScheduleData *SD, 3011 bool InsertInReadyList, 3012 BoUpSLP *SLP) { 3013 assert(SD->isSchedulingEntity()); 3014 3015 SmallVector<ScheduleData *, 10> WorkList; 3016 WorkList.push_back(SD); 3017 3018 while (!WorkList.empty()) { 3019 ScheduleData *SD = WorkList.back(); 3020 WorkList.pop_back(); 3021 3022 ScheduleData *BundleMember = SD; 3023 while (BundleMember) { 3024 assert(isInSchedulingRegion(BundleMember)); 3025 if (!BundleMember->hasValidDependencies()) { 3026 3027 DEBUG(dbgs() << "SLP: update deps of " << *BundleMember << "\n"); 3028 BundleMember->Dependencies = 0; 3029 BundleMember->resetUnscheduledDeps(); 3030 3031 // Handle def-use chain dependencies. 3032 for (User *U : BundleMember->Inst->users()) { 3033 if (isa<Instruction>(U)) { 3034 ScheduleData *UseSD = getScheduleData(U); 3035 if (UseSD && isInSchedulingRegion(UseSD->FirstInBundle)) { 3036 BundleMember->Dependencies++; 3037 ScheduleData *DestBundle = UseSD->FirstInBundle; 3038 if (!DestBundle->IsScheduled) { 3039 BundleMember->incrementUnscheduledDeps(1); 3040 } 3041 if (!DestBundle->hasValidDependencies()) { 3042 WorkList.push_back(DestBundle); 3043 } 3044 } 3045 } else { 3046 // I'm not sure if this can ever happen. But we need to be safe. 3047 // This lets the instruction/bundle never be scheduled and 3048 // eventually disable vectorization. 3049 BundleMember->Dependencies++; 3050 BundleMember->incrementUnscheduledDeps(1); 3051 } 3052 } 3053 3054 // Handle the memory dependencies. 3055 ScheduleData *DepDest = BundleMember->NextLoadStore; 3056 if (DepDest) { 3057 Instruction *SrcInst = BundleMember->Inst; 3058 MemoryLocation SrcLoc = getLocation(SrcInst, SLP->AA); 3059 bool SrcMayWrite = BundleMember->Inst->mayWriteToMemory(); 3060 unsigned numAliased = 0; 3061 unsigned DistToSrc = 1; 3062 3063 while (DepDest) { 3064 assert(isInSchedulingRegion(DepDest)); 3065 3066 // We have two limits to reduce the complexity: 3067 // 1) AliasedCheckLimit: It's a small limit to reduce calls to 3068 // SLP->isAliased (which is the expensive part in this loop). 3069 // 2) MaxMemDepDistance: It's for very large blocks and it aborts 3070 // the whole loop (even if the loop is fast, it's quadratic). 3071 // It's important for the loop break condition (see below) to 3072 // check this limit even between two read-only instructions. 3073 if (DistToSrc >= MaxMemDepDistance || 3074 ((SrcMayWrite || DepDest->Inst->mayWriteToMemory()) && 3075 (numAliased >= AliasedCheckLimit || 3076 SLP->isAliased(SrcLoc, SrcInst, DepDest->Inst)))) { 3077 3078 // We increment the counter only if the locations are aliased 3079 // (instead of counting all alias checks). This gives a better 3080 // balance between reduced runtime and accurate dependencies. 3081 numAliased++; 3082 3083 DepDest->MemoryDependencies.push_back(BundleMember); 3084 BundleMember->Dependencies++; 3085 ScheduleData *DestBundle = DepDest->FirstInBundle; 3086 if (!DestBundle->IsScheduled) { 3087 BundleMember->incrementUnscheduledDeps(1); 3088 } 3089 if (!DestBundle->hasValidDependencies()) { 3090 WorkList.push_back(DestBundle); 3091 } 3092 } 3093 DepDest = DepDest->NextLoadStore; 3094 3095 // Example, explaining the loop break condition: Let's assume our 3096 // starting instruction is i0 and MaxMemDepDistance = 3. 3097 // 3098 // +--------v--v--v 3099 // i0,i1,i2,i3,i4,i5,i6,i7,i8 3100 // +--------^--^--^ 3101 // 3102 // MaxMemDepDistance let us stop alias-checking at i3 and we add 3103 // dependencies from i0 to i3,i4,.. (even if they are not aliased). 3104 // Previously we already added dependencies from i3 to i6,i7,i8 3105 // (because of MaxMemDepDistance). As we added a dependency from 3106 // i0 to i3, we have transitive dependencies from i0 to i6,i7,i8 3107 // and we can abort this loop at i6. 3108 if (DistToSrc >= 2 * MaxMemDepDistance) 3109 break; 3110 DistToSrc++; 3111 } 3112 } 3113 } 3114 BundleMember = BundleMember->NextInBundle; 3115 } 3116 if (InsertInReadyList && SD->isReady()) { 3117 ReadyInsts.push_back(SD); 3118 DEBUG(dbgs() << "SLP: gets ready on update: " << *SD->Inst << "\n"); 3119 } 3120 } 3121 } 3122 3123 void BoUpSLP::BlockScheduling::resetSchedule() { 3124 assert(ScheduleStart && 3125 "tried to reset schedule on block which has not been scheduled"); 3126 for (Instruction *I = ScheduleStart; I != ScheduleEnd; I = I->getNextNode()) { 3127 ScheduleData *SD = getScheduleData(I); 3128 assert(isInSchedulingRegion(SD)); 3129 SD->IsScheduled = false; 3130 SD->resetUnscheduledDeps(); 3131 } 3132 ReadyInsts.clear(); 3133 } 3134 3135 void BoUpSLP::scheduleBlock(BlockScheduling *BS) { 3136 3137 if (!BS->ScheduleStart) 3138 return; 3139 3140 DEBUG(dbgs() << "SLP: schedule block " << BS->BB->getName() << "\n"); 3141 3142 BS->resetSchedule(); 3143 3144 // For the real scheduling we use a more sophisticated ready-list: it is 3145 // sorted by the original instruction location. This lets the final schedule 3146 // be as close as possible to the original instruction order. 3147 struct ScheduleDataCompare { 3148 bool operator()(ScheduleData *SD1, ScheduleData *SD2) { 3149 return SD2->SchedulingPriority < SD1->SchedulingPriority; 3150 } 3151 }; 3152 std::set<ScheduleData *, ScheduleDataCompare> ReadyInsts; 3153 3154 // Ensure that all dependency data is updated and fill the ready-list with 3155 // initial instructions. 3156 int Idx = 0; 3157 int NumToSchedule = 0; 3158 for (auto *I = BS->ScheduleStart; I != BS->ScheduleEnd; 3159 I = I->getNextNode()) { 3160 ScheduleData *SD = BS->getScheduleData(I); 3161 assert( 3162 SD->isPartOfBundle() == (ScalarToTreeEntry.count(SD->Inst) != 0) && 3163 "scheduler and vectorizer have different opinion on what is a bundle"); 3164 SD->FirstInBundle->SchedulingPriority = Idx++; 3165 if (SD->isSchedulingEntity()) { 3166 BS->calculateDependencies(SD, false, this); 3167 NumToSchedule++; 3168 } 3169 } 3170 BS->initialFillReadyList(ReadyInsts); 3171 3172 Instruction *LastScheduledInst = BS->ScheduleEnd; 3173 3174 // Do the "real" scheduling. 3175 while (!ReadyInsts.empty()) { 3176 ScheduleData *picked = *ReadyInsts.begin(); 3177 ReadyInsts.erase(ReadyInsts.begin()); 3178 3179 // Move the scheduled instruction(s) to their dedicated places, if not 3180 // there yet. 3181 ScheduleData *BundleMember = picked; 3182 while (BundleMember) { 3183 Instruction *pickedInst = BundleMember->Inst; 3184 if (LastScheduledInst->getNextNode() != pickedInst) { 3185 BS->BB->getInstList().remove(pickedInst); 3186 BS->BB->getInstList().insert(LastScheduledInst->getIterator(), 3187 pickedInst); 3188 } 3189 LastScheduledInst = pickedInst; 3190 BundleMember = BundleMember->NextInBundle; 3191 } 3192 3193 BS->schedule(picked, ReadyInsts); 3194 NumToSchedule--; 3195 } 3196 assert(NumToSchedule == 0 && "could not schedule all instructions"); 3197 3198 // Avoid duplicate scheduling of the block. 3199 BS->ScheduleStart = nullptr; 3200 } 3201 3202 unsigned BoUpSLP::getVectorElementSize(Value *V) { 3203 // If V is a store, just return the width of the stored value without 3204 // traversing the expression tree. This is the common case. 3205 if (auto *Store = dyn_cast<StoreInst>(V)) 3206 return DL->getTypeSizeInBits(Store->getValueOperand()->getType()); 3207 3208 // If V is not a store, we can traverse the expression tree to find loads 3209 // that feed it. The type of the loaded value may indicate a more suitable 3210 // width than V's type. We want to base the vector element size on the width 3211 // of memory operations where possible. 3212 SmallVector<Instruction *, 16> Worklist; 3213 SmallPtrSet<Instruction *, 16> Visited; 3214 if (auto *I = dyn_cast<Instruction>(V)) 3215 Worklist.push_back(I); 3216 3217 // Traverse the expression tree in bottom-up order looking for loads. If we 3218 // encounter an instruciton we don't yet handle, we give up. 3219 auto MaxWidth = 0u; 3220 auto FoundUnknownInst = false; 3221 while (!Worklist.empty() && !FoundUnknownInst) { 3222 auto *I = Worklist.pop_back_val(); 3223 Visited.insert(I); 3224 3225 // We should only be looking at scalar instructions here. If the current 3226 // instruction has a vector type, give up. 3227 auto *Ty = I->getType(); 3228 if (isa<VectorType>(Ty)) 3229 FoundUnknownInst = true; 3230 3231 // If the current instruction is a load, update MaxWidth to reflect the 3232 // width of the loaded value. 3233 else if (isa<LoadInst>(I)) 3234 MaxWidth = std::max<unsigned>(MaxWidth, DL->getTypeSizeInBits(Ty)); 3235 3236 // Otherwise, we need to visit the operands of the instruction. We only 3237 // handle the interesting cases from buildTree here. If an operand is an 3238 // instruction we haven't yet visited, we add it to the worklist. 3239 else if (isa<PHINode>(I) || isa<CastInst>(I) || isa<GetElementPtrInst>(I) || 3240 isa<CmpInst>(I) || isa<SelectInst>(I) || isa<BinaryOperator>(I)) { 3241 for (Use &U : I->operands()) 3242 if (auto *J = dyn_cast<Instruction>(U.get())) 3243 if (!Visited.count(J)) 3244 Worklist.push_back(J); 3245 } 3246 3247 // If we don't yet handle the instruction, give up. 3248 else 3249 FoundUnknownInst = true; 3250 } 3251 3252 // If we didn't encounter a memory access in the expression tree, or if we 3253 // gave up for some reason, just return the width of V. 3254 if (!MaxWidth || FoundUnknownInst) 3255 return DL->getTypeSizeInBits(V->getType()); 3256 3257 // Otherwise, return the maximum width we found. 3258 return MaxWidth; 3259 } 3260 3261 // Determine if a value V in a vectorizable expression Expr can be demoted to a 3262 // smaller type with a truncation. We collect the values that will be demoted 3263 // in ToDemote and additional roots that require investigating in Roots. 3264 static bool collectValuesToDemote(Value *V, SmallPtrSetImpl<Value *> &Expr, 3265 SmallVectorImpl<Value *> &ToDemote, 3266 SmallVectorImpl<Value *> &Roots) { 3267 3268 // We can always demote constants. 3269 if (isa<Constant>(V)) { 3270 ToDemote.push_back(V); 3271 return true; 3272 } 3273 3274 // If the value is not an instruction in the expression with only one use, it 3275 // cannot be demoted. 3276 auto *I = dyn_cast<Instruction>(V); 3277 if (!I || !I->hasOneUse() || !Expr.count(I)) 3278 return false; 3279 3280 switch (I->getOpcode()) { 3281 3282 // We can always demote truncations and extensions. Since truncations can 3283 // seed additional demotion, we save the truncated value. 3284 case Instruction::Trunc: 3285 Roots.push_back(I->getOperand(0)); 3286 case Instruction::ZExt: 3287 case Instruction::SExt: 3288 break; 3289 3290 // We can demote certain binary operations if we can demote both of their 3291 // operands. 3292 case Instruction::Add: 3293 case Instruction::Sub: 3294 case Instruction::Mul: 3295 case Instruction::And: 3296 case Instruction::Or: 3297 case Instruction::Xor: 3298 if (!collectValuesToDemote(I->getOperand(0), Expr, ToDemote, Roots) || 3299 !collectValuesToDemote(I->getOperand(1), Expr, ToDemote, Roots)) 3300 return false; 3301 break; 3302 3303 // We can demote selects if we can demote their true and false values. 3304 case Instruction::Select: { 3305 SelectInst *SI = cast<SelectInst>(I); 3306 if (!collectValuesToDemote(SI->getTrueValue(), Expr, ToDemote, Roots) || 3307 !collectValuesToDemote(SI->getFalseValue(), Expr, ToDemote, Roots)) 3308 return false; 3309 break; 3310 } 3311 3312 // We can demote phis if we can demote all their incoming operands. Note that 3313 // we don't need to worry about cycles since we ensure single use above. 3314 case Instruction::PHI: { 3315 PHINode *PN = cast<PHINode>(I); 3316 for (Value *IncValue : PN->incoming_values()) 3317 if (!collectValuesToDemote(IncValue, Expr, ToDemote, Roots)) 3318 return false; 3319 break; 3320 } 3321 3322 // Otherwise, conservatively give up. 3323 default: 3324 return false; 3325 } 3326 3327 // Record the value that we can demote. 3328 ToDemote.push_back(V); 3329 return true; 3330 } 3331 3332 void BoUpSLP::computeMinimumValueSizes() { 3333 // If there are no external uses, the expression tree must be rooted by a 3334 // store. We can't demote in-memory values, so there is nothing to do here. 3335 if (ExternalUses.empty()) 3336 return; 3337 3338 // We only attempt to truncate integer expressions. 3339 auto &TreeRoot = VectorizableTree[0].Scalars; 3340 auto *TreeRootIT = dyn_cast<IntegerType>(TreeRoot[0]->getType()); 3341 if (!TreeRootIT) 3342 return; 3343 3344 // If the expression is not rooted by a store, these roots should have 3345 // external uses. We will rely on InstCombine to rewrite the expression in 3346 // the narrower type. However, InstCombine only rewrites single-use values. 3347 // This means that if a tree entry other than a root is used externally, it 3348 // must have multiple uses and InstCombine will not rewrite it. The code 3349 // below ensures that only the roots are used externally. 3350 SmallPtrSet<Value *, 32> Expr(TreeRoot.begin(), TreeRoot.end()); 3351 for (auto &EU : ExternalUses) 3352 if (!Expr.erase(EU.Scalar)) 3353 return; 3354 if (!Expr.empty()) 3355 return; 3356 3357 // Collect the scalar values of the vectorizable expression. We will use this 3358 // context to determine which values can be demoted. If we see a truncation, 3359 // we mark it as seeding another demotion. 3360 for (auto &Entry : VectorizableTree) 3361 Expr.insert(Entry.Scalars.begin(), Entry.Scalars.end()); 3362 3363 // Ensure the roots of the vectorizable tree don't form a cycle. They must 3364 // have a single external user that is not in the vectorizable tree. 3365 for (auto *Root : TreeRoot) 3366 if (!Root->hasOneUse() || Expr.count(*Root->user_begin())) 3367 return; 3368 3369 // Conservatively determine if we can actually truncate the roots of the 3370 // expression. Collect the values that can be demoted in ToDemote and 3371 // additional roots that require investigating in Roots. 3372 SmallVector<Value *, 32> ToDemote; 3373 SmallVector<Value *, 4> Roots; 3374 for (auto *Root : TreeRoot) 3375 if (!collectValuesToDemote(Root, Expr, ToDemote, Roots)) 3376 return; 3377 3378 // The maximum bit width required to represent all the values that can be 3379 // demoted without loss of precision. It would be safe to truncate the roots 3380 // of the expression to this width. 3381 auto MaxBitWidth = 8u; 3382 3383 // We first check if all the bits of the roots are demanded. If they're not, 3384 // we can truncate the roots to this narrower type. 3385 for (auto *Root : TreeRoot) { 3386 auto Mask = DB->getDemandedBits(cast<Instruction>(Root)); 3387 MaxBitWidth = std::max<unsigned>( 3388 Mask.getBitWidth() - Mask.countLeadingZeros(), MaxBitWidth); 3389 } 3390 3391 // If all the bits of the roots are demanded, we can try a little harder to 3392 // compute a narrower type. This can happen, for example, if the roots are 3393 // getelementptr indices. InstCombine promotes these indices to the pointer 3394 // width. Thus, all their bits are technically demanded even though the 3395 // address computation might be vectorized in a smaller type. 3396 // 3397 // We start by looking at each entry that can be demoted. We compute the 3398 // maximum bit width required to store the scalar by using ValueTracking to 3399 // compute the number of high-order bits we can truncate. 3400 if (MaxBitWidth == DL->getTypeSizeInBits(TreeRoot[0]->getType())) { 3401 MaxBitWidth = 8u; 3402 for (auto *Scalar : ToDemote) { 3403 auto NumSignBits = ComputeNumSignBits(Scalar, *DL, 0, AC, 0, DT); 3404 auto NumTypeBits = DL->getTypeSizeInBits(Scalar->getType()); 3405 MaxBitWidth = std::max<unsigned>(NumTypeBits - NumSignBits, MaxBitWidth); 3406 } 3407 } 3408 3409 // Round MaxBitWidth up to the next power-of-two. 3410 if (!isPowerOf2_64(MaxBitWidth)) 3411 MaxBitWidth = NextPowerOf2(MaxBitWidth); 3412 3413 // If the maximum bit width we compute is less than the with of the roots' 3414 // type, we can proceed with the narrowing. Otherwise, do nothing. 3415 if (MaxBitWidth >= TreeRootIT->getBitWidth()) 3416 return; 3417 3418 // If we can truncate the root, we must collect additional values that might 3419 // be demoted as a result. That is, those seeded by truncations we will 3420 // modify. 3421 while (!Roots.empty()) 3422 collectValuesToDemote(Roots.pop_back_val(), Expr, ToDemote, Roots); 3423 3424 // Finally, map the values we can demote to the maximum bit with we computed. 3425 for (auto *Scalar : ToDemote) 3426 MinBWs[Scalar] = MaxBitWidth; 3427 } 3428 3429 namespace { 3430 /// The SLPVectorizer Pass. 3431 struct SLPVectorizer : public FunctionPass { 3432 SLPVectorizerPass Impl; 3433 3434 /// Pass identification, replacement for typeid 3435 static char ID; 3436 3437 explicit SLPVectorizer() : FunctionPass(ID) { 3438 initializeSLPVectorizerPass(*PassRegistry::getPassRegistry()); 3439 } 3440 3441 3442 bool doInitialization(Module &M) override { 3443 return false; 3444 } 3445 3446 bool runOnFunction(Function &F) override { 3447 if (skipFunction(F)) 3448 return false; 3449 3450 auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE(); 3451 auto *TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F); 3452 auto *TLIP = getAnalysisIfAvailable<TargetLibraryInfoWrapperPass>(); 3453 auto *TLI = TLIP ? &TLIP->getTLI() : nullptr; 3454 auto *AA = &getAnalysis<AAResultsWrapperPass>().getAAResults(); 3455 auto *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); 3456 auto *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 3457 auto *AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F); 3458 auto *DB = &getAnalysis<DemandedBitsWrapperPass>().getDemandedBits(); 3459 3460 return Impl.runImpl(F, SE, TTI, TLI, AA, LI, DT, AC, DB); 3461 } 3462 3463 void getAnalysisUsage(AnalysisUsage &AU) const override { 3464 FunctionPass::getAnalysisUsage(AU); 3465 AU.addRequired<AssumptionCacheTracker>(); 3466 AU.addRequired<ScalarEvolutionWrapperPass>(); 3467 AU.addRequired<AAResultsWrapperPass>(); 3468 AU.addRequired<TargetTransformInfoWrapperPass>(); 3469 AU.addRequired<LoopInfoWrapperPass>(); 3470 AU.addRequired<DominatorTreeWrapperPass>(); 3471 AU.addRequired<DemandedBitsWrapperPass>(); 3472 AU.addPreserved<LoopInfoWrapperPass>(); 3473 AU.addPreserved<DominatorTreeWrapperPass>(); 3474 AU.addPreserved<AAResultsWrapperPass>(); 3475 AU.addPreserved<GlobalsAAWrapperPass>(); 3476 AU.setPreservesCFG(); 3477 } 3478 }; 3479 } // end anonymous namespace 3480 3481 PreservedAnalyses SLPVectorizerPass::run(Function &F, FunctionAnalysisManager &AM) { 3482 auto *SE = &AM.getResult<ScalarEvolutionAnalysis>(F); 3483 auto *TTI = &AM.getResult<TargetIRAnalysis>(F); 3484 auto *TLI = AM.getCachedResult<TargetLibraryAnalysis>(F); 3485 auto *AA = &AM.getResult<AAManager>(F); 3486 auto *LI = &AM.getResult<LoopAnalysis>(F); 3487 auto *DT = &AM.getResult<DominatorTreeAnalysis>(F); 3488 auto *AC = &AM.getResult<AssumptionAnalysis>(F); 3489 auto *DB = &AM.getResult<DemandedBitsAnalysis>(F); 3490 3491 bool Changed = runImpl(F, SE, TTI, TLI, AA, LI, DT, AC, DB); 3492 if (!Changed) 3493 return PreservedAnalyses::all(); 3494 PreservedAnalyses PA; 3495 PA.preserve<LoopAnalysis>(); 3496 PA.preserve<DominatorTreeAnalysis>(); 3497 PA.preserve<AAManager>(); 3498 PA.preserve<GlobalsAA>(); 3499 return PA; 3500 } 3501 3502 bool SLPVectorizerPass::runImpl(Function &F, ScalarEvolution *SE_, 3503 TargetTransformInfo *TTI_, 3504 TargetLibraryInfo *TLI_, AliasAnalysis *AA_, 3505 LoopInfo *LI_, DominatorTree *DT_, 3506 AssumptionCache *AC_, DemandedBits *DB_) { 3507 SE = SE_; 3508 TTI = TTI_; 3509 TLI = TLI_; 3510 AA = AA_; 3511 LI = LI_; 3512 DT = DT_; 3513 AC = AC_; 3514 DB = DB_; 3515 DL = &F.getParent()->getDataLayout(); 3516 3517 Stores.clear(); 3518 GEPs.clear(); 3519 bool Changed = false; 3520 3521 // If the target claims to have no vector registers don't attempt 3522 // vectorization. 3523 if (!TTI->getNumberOfRegisters(true)) 3524 return false; 3525 3526 // Don't vectorize when the attribute NoImplicitFloat is used. 3527 if (F.hasFnAttribute(Attribute::NoImplicitFloat)) 3528 return false; 3529 3530 DEBUG(dbgs() << "SLP: Analyzing blocks in " << F.getName() << ".\n"); 3531 3532 // Use the bottom up slp vectorizer to construct chains that start with 3533 // store instructions. 3534 BoUpSLP R(&F, SE, TTI, TLI, AA, LI, DT, AC, DB, DL); 3535 3536 // A general note: the vectorizer must use BoUpSLP::eraseInstruction() to 3537 // delete instructions. 3538 3539 // Scan the blocks in the function in post order. 3540 for (auto BB : post_order(&F.getEntryBlock())) { 3541 collectSeedInstructions(BB); 3542 3543 // Vectorize trees that end at stores. 3544 if (!Stores.empty()) { 3545 DEBUG(dbgs() << "SLP: Found stores for " << Stores.size() 3546 << " underlying objects.\n"); 3547 Changed |= vectorizeStoreChains(R); 3548 } 3549 3550 // Vectorize trees that end at reductions. 3551 Changed |= vectorizeChainsInBlock(BB, R); 3552 3553 // Vectorize the index computations of getelementptr instructions. This 3554 // is primarily intended to catch gather-like idioms ending at 3555 // non-consecutive loads. 3556 if (!GEPs.empty()) { 3557 DEBUG(dbgs() << "SLP: Found GEPs for " << GEPs.size() 3558 << " underlying objects.\n"); 3559 Changed |= vectorizeGEPIndices(BB, R); 3560 } 3561 } 3562 3563 if (Changed) { 3564 R.optimizeGatherSequence(); 3565 DEBUG(dbgs() << "SLP: vectorized \"" << F.getName() << "\"\n"); 3566 DEBUG(verifyFunction(F)); 3567 } 3568 return Changed; 3569 } 3570 3571 /// \brief Check that the Values in the slice in VL array are still existent in 3572 /// the WeakVH array. 3573 /// Vectorization of part of the VL array may cause later values in the VL array 3574 /// to become invalid. We track when this has happened in the WeakVH array. 3575 static bool hasValueBeenRAUWed(ArrayRef<Value *> VL, ArrayRef<WeakVH> VH, 3576 unsigned SliceBegin, unsigned SliceSize) { 3577 VL = VL.slice(SliceBegin, SliceSize); 3578 VH = VH.slice(SliceBegin, SliceSize); 3579 return !std::equal(VL.begin(), VL.end(), VH.begin()); 3580 } 3581 3582 bool SLPVectorizerPass::vectorizeStoreChain(ArrayRef<Value *> Chain, 3583 int CostThreshold, BoUpSLP &R, 3584 unsigned VecRegSize) { 3585 unsigned ChainLen = Chain.size(); 3586 DEBUG(dbgs() << "SLP: Analyzing a store chain of length " << ChainLen 3587 << "\n"); 3588 unsigned Sz = R.getVectorElementSize(Chain[0]); 3589 unsigned VF = VecRegSize / Sz; 3590 3591 if (!isPowerOf2_32(Sz) || VF < 2) 3592 return false; 3593 3594 // Keep track of values that were deleted by vectorizing in the loop below. 3595 SmallVector<WeakVH, 8> TrackValues(Chain.begin(), Chain.end()); 3596 3597 bool Changed = false; 3598 // Look for profitable vectorizable trees at all offsets, starting at zero. 3599 for (unsigned i = 0, e = ChainLen; i < e; ++i) { 3600 if (i + VF > e) 3601 break; 3602 3603 // Check that a previous iteration of this loop did not delete the Value. 3604 if (hasValueBeenRAUWed(Chain, TrackValues, i, VF)) 3605 continue; 3606 3607 DEBUG(dbgs() << "SLP: Analyzing " << VF << " stores at offset " << i 3608 << "\n"); 3609 ArrayRef<Value *> Operands = Chain.slice(i, VF); 3610 3611 R.buildTree(Operands); 3612 R.computeMinimumValueSizes(); 3613 3614 int Cost = R.getTreeCost(); 3615 3616 DEBUG(dbgs() << "SLP: Found cost=" << Cost << " for VF=" << VF << "\n"); 3617 if (Cost < CostThreshold) { 3618 DEBUG(dbgs() << "SLP: Decided to vectorize cost=" << Cost << "\n"); 3619 R.vectorizeTree(); 3620 3621 // Move to the next bundle. 3622 i += VF - 1; 3623 Changed = true; 3624 } 3625 } 3626 3627 return Changed; 3628 } 3629 3630 bool SLPVectorizerPass::vectorizeStores(ArrayRef<StoreInst *> Stores, 3631 int costThreshold, BoUpSLP &R) { 3632 SetVector<StoreInst *> Heads, Tails; 3633 SmallDenseMap<StoreInst *, StoreInst *> ConsecutiveChain; 3634 3635 // We may run into multiple chains that merge into a single chain. We mark the 3636 // stores that we vectorized so that we don't visit the same store twice. 3637 BoUpSLP::ValueSet VectorizedStores; 3638 bool Changed = false; 3639 3640 // Do a quadratic search on all of the given stores and find 3641 // all of the pairs of stores that follow each other. 3642 SmallVector<unsigned, 16> IndexQueue; 3643 for (unsigned i = 0, e = Stores.size(); i < e; ++i) { 3644 IndexQueue.clear(); 3645 // If a store has multiple consecutive store candidates, search Stores 3646 // array according to the sequence: from i+1 to e, then from i-1 to 0. 3647 // This is because usually pairing with immediate succeeding or preceding 3648 // candidate create the best chance to find slp vectorization opportunity. 3649 unsigned j = 0; 3650 for (j = i + 1; j < e; ++j) 3651 IndexQueue.push_back(j); 3652 for (j = i; j > 0; --j) 3653 IndexQueue.push_back(j - 1); 3654 3655 for (auto &k : IndexQueue) { 3656 if (isConsecutiveAccess(Stores[i], Stores[k], *DL, *SE)) { 3657 Tails.insert(Stores[k]); 3658 Heads.insert(Stores[i]); 3659 ConsecutiveChain[Stores[i]] = Stores[k]; 3660 break; 3661 } 3662 } 3663 } 3664 3665 // For stores that start but don't end a link in the chain: 3666 for (SetVector<StoreInst *>::iterator it = Heads.begin(), e = Heads.end(); 3667 it != e; ++it) { 3668 if (Tails.count(*it)) 3669 continue; 3670 3671 // We found a store instr that starts a chain. Now follow the chain and try 3672 // to vectorize it. 3673 BoUpSLP::ValueList Operands; 3674 StoreInst *I = *it; 3675 // Collect the chain into a list. 3676 while (Tails.count(I) || Heads.count(I)) { 3677 if (VectorizedStores.count(I)) 3678 break; 3679 Operands.push_back(I); 3680 // Move to the next value in the chain. 3681 I = ConsecutiveChain[I]; 3682 } 3683 3684 // FIXME: Is division-by-2 the correct step? Should we assert that the 3685 // register size is a power-of-2? 3686 for (unsigned Size = R.getMaxVecRegSize(); Size >= R.getMinVecRegSize(); Size /= 2) { 3687 if (vectorizeStoreChain(Operands, costThreshold, R, Size)) { 3688 // Mark the vectorized stores so that we don't vectorize them again. 3689 VectorizedStores.insert(Operands.begin(), Operands.end()); 3690 Changed = true; 3691 break; 3692 } 3693 } 3694 } 3695 3696 return Changed; 3697 } 3698 3699 void SLPVectorizerPass::collectSeedInstructions(BasicBlock *BB) { 3700 3701 // Initialize the collections. We will make a single pass over the block. 3702 Stores.clear(); 3703 GEPs.clear(); 3704 3705 // Visit the store and getelementptr instructions in BB and organize them in 3706 // Stores and GEPs according to the underlying objects of their pointer 3707 // operands. 3708 for (Instruction &I : *BB) { 3709 3710 // Ignore store instructions that are volatile or have a pointer operand 3711 // that doesn't point to a scalar type. 3712 if (auto *SI = dyn_cast<StoreInst>(&I)) { 3713 if (!SI->isSimple()) 3714 continue; 3715 if (!isValidElementType(SI->getValueOperand()->getType())) 3716 continue; 3717 Stores[GetUnderlyingObject(SI->getPointerOperand(), *DL)].push_back(SI); 3718 } 3719 3720 // Ignore getelementptr instructions that have more than one index, a 3721 // constant index, or a pointer operand that doesn't point to a scalar 3722 // type. 3723 else if (auto *GEP = dyn_cast<GetElementPtrInst>(&I)) { 3724 auto Idx = GEP->idx_begin()->get(); 3725 if (GEP->getNumIndices() > 1 || isa<Constant>(Idx)) 3726 continue; 3727 if (!isValidElementType(Idx->getType())) 3728 continue; 3729 if (GEP->getType()->isVectorTy()) 3730 continue; 3731 GEPs[GetUnderlyingObject(GEP->getPointerOperand(), *DL)].push_back(GEP); 3732 } 3733 } 3734 } 3735 3736 bool SLPVectorizerPass::tryToVectorizePair(Value *A, Value *B, BoUpSLP &R) { 3737 if (!A || !B) 3738 return false; 3739 Value *VL[] = { A, B }; 3740 return tryToVectorizeList(VL, R, None, true); 3741 } 3742 3743 bool SLPVectorizerPass::tryToVectorizeList(ArrayRef<Value *> VL, BoUpSLP &R, 3744 ArrayRef<Value *> BuildVector, 3745 bool allowReorder) { 3746 if (VL.size() < 2) 3747 return false; 3748 3749 DEBUG(dbgs() << "SLP: Vectorizing a list of length = " << VL.size() << ".\n"); 3750 3751 // Check that all of the parts are scalar instructions of the same type. 3752 Instruction *I0 = dyn_cast<Instruction>(VL[0]); 3753 if (!I0) 3754 return false; 3755 3756 unsigned Opcode0 = I0->getOpcode(); 3757 3758 // FIXME: Register size should be a parameter to this function, so we can 3759 // try different vectorization factors. 3760 unsigned Sz = R.getVectorElementSize(I0); 3761 unsigned VF = R.getMinVecRegSize() / Sz; 3762 3763 for (Value *V : VL) { 3764 Type *Ty = V->getType(); 3765 if (!isValidElementType(Ty)) 3766 return false; 3767 Instruction *Inst = dyn_cast<Instruction>(V); 3768 if (!Inst || Inst->getOpcode() != Opcode0) 3769 return false; 3770 } 3771 3772 bool Changed = false; 3773 3774 // Keep track of values that were deleted by vectorizing in the loop below. 3775 SmallVector<WeakVH, 8> TrackValues(VL.begin(), VL.end()); 3776 3777 for (unsigned i = 0, e = VL.size(); i < e; ++i) { 3778 unsigned OpsWidth = 0; 3779 3780 if (i + VF > e) 3781 OpsWidth = e - i; 3782 else 3783 OpsWidth = VF; 3784 3785 if (!isPowerOf2_32(OpsWidth) || OpsWidth < 2) 3786 break; 3787 3788 // Check that a previous iteration of this loop did not delete the Value. 3789 if (hasValueBeenRAUWed(VL, TrackValues, i, OpsWidth)) 3790 continue; 3791 3792 DEBUG(dbgs() << "SLP: Analyzing " << OpsWidth << " operations " 3793 << "\n"); 3794 ArrayRef<Value *> Ops = VL.slice(i, OpsWidth); 3795 3796 ArrayRef<Value *> BuildVectorSlice; 3797 if (!BuildVector.empty()) 3798 BuildVectorSlice = BuildVector.slice(i, OpsWidth); 3799 3800 R.buildTree(Ops, BuildVectorSlice); 3801 // TODO: check if we can allow reordering also for other cases than 3802 // tryToVectorizePair() 3803 if (allowReorder && R.shouldReorder()) { 3804 assert(Ops.size() == 2); 3805 assert(BuildVectorSlice.empty()); 3806 Value *ReorderedOps[] = { Ops[1], Ops[0] }; 3807 R.buildTree(ReorderedOps, None); 3808 } 3809 R.computeMinimumValueSizes(); 3810 int Cost = R.getTreeCost(); 3811 3812 if (Cost < -SLPCostThreshold) { 3813 DEBUG(dbgs() << "SLP: Vectorizing list at cost:" << Cost << ".\n"); 3814 Value *VectorizedRoot = R.vectorizeTree(); 3815 3816 // Reconstruct the build vector by extracting the vectorized root. This 3817 // way we handle the case where some elements of the vector are undefined. 3818 // (return (inserelt <4 xi32> (insertelt undef (opd0) 0) (opd1) 2)) 3819 if (!BuildVectorSlice.empty()) { 3820 // The insert point is the last build vector instruction. The vectorized 3821 // root will precede it. This guarantees that we get an instruction. The 3822 // vectorized tree could have been constant folded. 3823 Instruction *InsertAfter = cast<Instruction>(BuildVectorSlice.back()); 3824 unsigned VecIdx = 0; 3825 for (auto &V : BuildVectorSlice) { 3826 IRBuilder<NoFolder> Builder(InsertAfter->getParent(), 3827 ++BasicBlock::iterator(InsertAfter)); 3828 Instruction *I = cast<Instruction>(V); 3829 assert(isa<InsertElementInst>(I) || isa<InsertValueInst>(I)); 3830 Instruction *Extract = cast<Instruction>(Builder.CreateExtractElement( 3831 VectorizedRoot, Builder.getInt32(VecIdx++))); 3832 I->setOperand(1, Extract); 3833 I->removeFromParent(); 3834 I->insertAfter(Extract); 3835 InsertAfter = I; 3836 } 3837 } 3838 // Move to the next bundle. 3839 i += VF - 1; 3840 Changed = true; 3841 } 3842 } 3843 3844 return Changed; 3845 } 3846 3847 bool SLPVectorizerPass::tryToVectorize(BinaryOperator *V, BoUpSLP &R) { 3848 if (!V) 3849 return false; 3850 3851 // Try to vectorize V. 3852 if (tryToVectorizePair(V->getOperand(0), V->getOperand(1), R)) 3853 return true; 3854 3855 BinaryOperator *A = dyn_cast<BinaryOperator>(V->getOperand(0)); 3856 BinaryOperator *B = dyn_cast<BinaryOperator>(V->getOperand(1)); 3857 // Try to skip B. 3858 if (B && B->hasOneUse()) { 3859 BinaryOperator *B0 = dyn_cast<BinaryOperator>(B->getOperand(0)); 3860 BinaryOperator *B1 = dyn_cast<BinaryOperator>(B->getOperand(1)); 3861 if (tryToVectorizePair(A, B0, R)) { 3862 return true; 3863 } 3864 if (tryToVectorizePair(A, B1, R)) { 3865 return true; 3866 } 3867 } 3868 3869 // Try to skip A. 3870 if (A && A->hasOneUse()) { 3871 BinaryOperator *A0 = dyn_cast<BinaryOperator>(A->getOperand(0)); 3872 BinaryOperator *A1 = dyn_cast<BinaryOperator>(A->getOperand(1)); 3873 if (tryToVectorizePair(A0, B, R)) { 3874 return true; 3875 } 3876 if (tryToVectorizePair(A1, B, R)) { 3877 return true; 3878 } 3879 } 3880 return 0; 3881 } 3882 3883 /// \brief Generate a shuffle mask to be used in a reduction tree. 3884 /// 3885 /// \param VecLen The length of the vector to be reduced. 3886 /// \param NumEltsToRdx The number of elements that should be reduced in the 3887 /// vector. 3888 /// \param IsPairwise Whether the reduction is a pairwise or splitting 3889 /// reduction. A pairwise reduction will generate a mask of 3890 /// <0,2,...> or <1,3,..> while a splitting reduction will generate 3891 /// <2,3, undef,undef> for a vector of 4 and NumElts = 2. 3892 /// \param IsLeft True will generate a mask of even elements, odd otherwise. 3893 static Value *createRdxShuffleMask(unsigned VecLen, unsigned NumEltsToRdx, 3894 bool IsPairwise, bool IsLeft, 3895 IRBuilder<> &Builder) { 3896 assert((IsPairwise || !IsLeft) && "Don't support a <0,1,undef,...> mask"); 3897 3898 SmallVector<Constant *, 32> ShuffleMask( 3899 VecLen, UndefValue::get(Builder.getInt32Ty())); 3900 3901 if (IsPairwise) 3902 // Build a mask of 0, 2, ... (left) or 1, 3, ... (right). 3903 for (unsigned i = 0; i != NumEltsToRdx; ++i) 3904 ShuffleMask[i] = Builder.getInt32(2 * i + !IsLeft); 3905 else 3906 // Move the upper half of the vector to the lower half. 3907 for (unsigned i = 0; i != NumEltsToRdx; ++i) 3908 ShuffleMask[i] = Builder.getInt32(NumEltsToRdx + i); 3909 3910 return ConstantVector::get(ShuffleMask); 3911 } 3912 3913 3914 /// Model horizontal reductions. 3915 /// 3916 /// A horizontal reduction is a tree of reduction operations (currently add and 3917 /// fadd) that has operations that can be put into a vector as its leaf. 3918 /// For example, this tree: 3919 /// 3920 /// mul mul mul mul 3921 /// \ / \ / 3922 /// + + 3923 /// \ / 3924 /// + 3925 /// This tree has "mul" as its reduced values and "+" as its reduction 3926 /// operations. A reduction might be feeding into a store or a binary operation 3927 /// feeding a phi. 3928 /// ... 3929 /// \ / 3930 /// + 3931 /// | 3932 /// phi += 3933 /// 3934 /// Or: 3935 /// ... 3936 /// \ / 3937 /// + 3938 /// | 3939 /// *p = 3940 /// 3941 class HorizontalReduction { 3942 SmallVector<Value *, 16> ReductionOps; 3943 SmallVector<Value *, 32> ReducedVals; 3944 3945 BinaryOperator *ReductionRoot; 3946 PHINode *ReductionPHI; 3947 3948 /// The opcode of the reduction. 3949 unsigned ReductionOpcode; 3950 /// The opcode of the values we perform a reduction on. 3951 unsigned ReducedValueOpcode; 3952 /// Should we model this reduction as a pairwise reduction tree or a tree that 3953 /// splits the vector in halves and adds those halves. 3954 bool IsPairwiseReduction; 3955 3956 public: 3957 /// The width of one full horizontal reduction operation. 3958 unsigned ReduxWidth; 3959 3960 /// Minimal width of available vector registers. It's used to determine 3961 /// ReduxWidth. 3962 unsigned MinVecRegSize; 3963 3964 HorizontalReduction(unsigned MinVecRegSize) 3965 : ReductionRoot(nullptr), ReductionPHI(nullptr), ReductionOpcode(0), 3966 ReducedValueOpcode(0), IsPairwiseReduction(false), ReduxWidth(0), 3967 MinVecRegSize(MinVecRegSize) {} 3968 3969 /// \brief Try to find a reduction tree. 3970 bool matchAssociativeReduction(PHINode *Phi, BinaryOperator *B) { 3971 assert((!Phi || 3972 std::find(Phi->op_begin(), Phi->op_end(), B) != Phi->op_end()) && 3973 "Thi phi needs to use the binary operator"); 3974 3975 // We could have a initial reductions that is not an add. 3976 // r *= v1 + v2 + v3 + v4 3977 // In such a case start looking for a tree rooted in the first '+'. 3978 if (Phi) { 3979 if (B->getOperand(0) == Phi) { 3980 Phi = nullptr; 3981 B = dyn_cast<BinaryOperator>(B->getOperand(1)); 3982 } else if (B->getOperand(1) == Phi) { 3983 Phi = nullptr; 3984 B = dyn_cast<BinaryOperator>(B->getOperand(0)); 3985 } 3986 } 3987 3988 if (!B) 3989 return false; 3990 3991 Type *Ty = B->getType(); 3992 if (!isValidElementType(Ty)) 3993 return false; 3994 3995 const DataLayout &DL = B->getModule()->getDataLayout(); 3996 ReductionOpcode = B->getOpcode(); 3997 ReducedValueOpcode = 0; 3998 // FIXME: Register size should be a parameter to this function, so we can 3999 // try different vectorization factors. 4000 ReduxWidth = MinVecRegSize / DL.getTypeSizeInBits(Ty); 4001 ReductionRoot = B; 4002 ReductionPHI = Phi; 4003 4004 if (ReduxWidth < 4) 4005 return false; 4006 4007 // We currently only support adds. 4008 if (ReductionOpcode != Instruction::Add && 4009 ReductionOpcode != Instruction::FAdd) 4010 return false; 4011 4012 // Post order traverse the reduction tree starting at B. We only handle true 4013 // trees containing only binary operators or selects. 4014 SmallVector<std::pair<Instruction *, unsigned>, 32> Stack; 4015 Stack.push_back(std::make_pair(B, 0)); 4016 while (!Stack.empty()) { 4017 Instruction *TreeN = Stack.back().first; 4018 unsigned EdgeToVist = Stack.back().second++; 4019 bool IsReducedValue = TreeN->getOpcode() != ReductionOpcode; 4020 4021 // Only handle trees in the current basic block. 4022 if (TreeN->getParent() != B->getParent()) 4023 return false; 4024 4025 // Each tree node needs to have one user except for the ultimate 4026 // reduction. 4027 if (!TreeN->hasOneUse() && TreeN != B) 4028 return false; 4029 4030 // Postorder vist. 4031 if (EdgeToVist == 2 || IsReducedValue) { 4032 if (IsReducedValue) { 4033 // Make sure that the opcodes of the operations that we are going to 4034 // reduce match. 4035 if (!ReducedValueOpcode) 4036 ReducedValueOpcode = TreeN->getOpcode(); 4037 else if (ReducedValueOpcode != TreeN->getOpcode()) 4038 return false; 4039 ReducedVals.push_back(TreeN); 4040 } else { 4041 // We need to be able to reassociate the adds. 4042 if (!TreeN->isAssociative()) 4043 return false; 4044 ReductionOps.push_back(TreeN); 4045 } 4046 // Retract. 4047 Stack.pop_back(); 4048 continue; 4049 } 4050 4051 // Visit left or right. 4052 Value *NextV = TreeN->getOperand(EdgeToVist); 4053 // We currently only allow BinaryOperator's and SelectInst's as reduction 4054 // values in our tree. 4055 if (isa<BinaryOperator>(NextV) || isa<SelectInst>(NextV)) 4056 Stack.push_back(std::make_pair(cast<Instruction>(NextV), 0)); 4057 else if (NextV != Phi) 4058 return false; 4059 } 4060 return true; 4061 } 4062 4063 /// \brief Attempt to vectorize the tree found by 4064 /// matchAssociativeReduction. 4065 bool tryToReduce(BoUpSLP &V, TargetTransformInfo *TTI) { 4066 if (ReducedVals.empty()) 4067 return false; 4068 4069 unsigned NumReducedVals = ReducedVals.size(); 4070 if (NumReducedVals < ReduxWidth) 4071 return false; 4072 4073 Value *VectorizedTree = nullptr; 4074 IRBuilder<> Builder(ReductionRoot); 4075 FastMathFlags Unsafe; 4076 Unsafe.setUnsafeAlgebra(); 4077 Builder.setFastMathFlags(Unsafe); 4078 unsigned i = 0; 4079 4080 for (; i < NumReducedVals - ReduxWidth + 1; i += ReduxWidth) { 4081 V.buildTree(makeArrayRef(&ReducedVals[i], ReduxWidth), ReductionOps); 4082 V.computeMinimumValueSizes(); 4083 4084 // Estimate cost. 4085 int Cost = V.getTreeCost() + getReductionCost(TTI, ReducedVals[i]); 4086 if (Cost >= -SLPCostThreshold) 4087 break; 4088 4089 DEBUG(dbgs() << "SLP: Vectorizing horizontal reduction at cost:" << Cost 4090 << ". (HorRdx)\n"); 4091 4092 // Vectorize a tree. 4093 DebugLoc Loc = cast<Instruction>(ReducedVals[i])->getDebugLoc(); 4094 Value *VectorizedRoot = V.vectorizeTree(); 4095 4096 // Emit a reduction. 4097 Value *ReducedSubTree = emitReduction(VectorizedRoot, Builder); 4098 if (VectorizedTree) { 4099 Builder.SetCurrentDebugLocation(Loc); 4100 VectorizedTree = createBinOp(Builder, ReductionOpcode, VectorizedTree, 4101 ReducedSubTree, "bin.rdx"); 4102 } else 4103 VectorizedTree = ReducedSubTree; 4104 } 4105 4106 if (VectorizedTree) { 4107 // Finish the reduction. 4108 for (; i < NumReducedVals; ++i) { 4109 Builder.SetCurrentDebugLocation( 4110 cast<Instruction>(ReducedVals[i])->getDebugLoc()); 4111 VectorizedTree = createBinOp(Builder, ReductionOpcode, VectorizedTree, 4112 ReducedVals[i]); 4113 } 4114 // Update users. 4115 if (ReductionPHI) { 4116 assert(ReductionRoot && "Need a reduction operation"); 4117 ReductionRoot->setOperand(0, VectorizedTree); 4118 ReductionRoot->setOperand(1, ReductionPHI); 4119 } else 4120 ReductionRoot->replaceAllUsesWith(VectorizedTree); 4121 } 4122 return VectorizedTree != nullptr; 4123 } 4124 4125 unsigned numReductionValues() const { 4126 return ReducedVals.size(); 4127 } 4128 4129 private: 4130 /// \brief Calculate the cost of a reduction. 4131 int getReductionCost(TargetTransformInfo *TTI, Value *FirstReducedVal) { 4132 Type *ScalarTy = FirstReducedVal->getType(); 4133 Type *VecTy = VectorType::get(ScalarTy, ReduxWidth); 4134 4135 int PairwiseRdxCost = TTI->getReductionCost(ReductionOpcode, VecTy, true); 4136 int SplittingRdxCost = TTI->getReductionCost(ReductionOpcode, VecTy, false); 4137 4138 IsPairwiseReduction = PairwiseRdxCost < SplittingRdxCost; 4139 int VecReduxCost = IsPairwiseReduction ? PairwiseRdxCost : SplittingRdxCost; 4140 4141 int ScalarReduxCost = 4142 ReduxWidth * TTI->getArithmeticInstrCost(ReductionOpcode, VecTy); 4143 4144 DEBUG(dbgs() << "SLP: Adding cost " << VecReduxCost - ScalarReduxCost 4145 << " for reduction that starts with " << *FirstReducedVal 4146 << " (It is a " 4147 << (IsPairwiseReduction ? "pairwise" : "splitting") 4148 << " reduction)\n"); 4149 4150 return VecReduxCost - ScalarReduxCost; 4151 } 4152 4153 static Value *createBinOp(IRBuilder<> &Builder, unsigned Opcode, Value *L, 4154 Value *R, const Twine &Name = "") { 4155 if (Opcode == Instruction::FAdd) 4156 return Builder.CreateFAdd(L, R, Name); 4157 return Builder.CreateBinOp((Instruction::BinaryOps)Opcode, L, R, Name); 4158 } 4159 4160 /// \brief Emit a horizontal reduction of the vectorized value. 4161 Value *emitReduction(Value *VectorizedValue, IRBuilder<> &Builder) { 4162 assert(VectorizedValue && "Need to have a vectorized tree node"); 4163 assert(isPowerOf2_32(ReduxWidth) && 4164 "We only handle power-of-two reductions for now"); 4165 4166 Value *TmpVec = VectorizedValue; 4167 for (unsigned i = ReduxWidth / 2; i != 0; i >>= 1) { 4168 if (IsPairwiseReduction) { 4169 Value *LeftMask = 4170 createRdxShuffleMask(ReduxWidth, i, true, true, Builder); 4171 Value *RightMask = 4172 createRdxShuffleMask(ReduxWidth, i, true, false, Builder); 4173 4174 Value *LeftShuf = Builder.CreateShuffleVector( 4175 TmpVec, UndefValue::get(TmpVec->getType()), LeftMask, "rdx.shuf.l"); 4176 Value *RightShuf = Builder.CreateShuffleVector( 4177 TmpVec, UndefValue::get(TmpVec->getType()), (RightMask), 4178 "rdx.shuf.r"); 4179 TmpVec = createBinOp(Builder, ReductionOpcode, LeftShuf, RightShuf, 4180 "bin.rdx"); 4181 } else { 4182 Value *UpperHalf = 4183 createRdxShuffleMask(ReduxWidth, i, false, false, Builder); 4184 Value *Shuf = Builder.CreateShuffleVector( 4185 TmpVec, UndefValue::get(TmpVec->getType()), UpperHalf, "rdx.shuf"); 4186 TmpVec = createBinOp(Builder, ReductionOpcode, TmpVec, Shuf, "bin.rdx"); 4187 } 4188 } 4189 4190 // The result is in the first element of the vector. 4191 return Builder.CreateExtractElement(TmpVec, Builder.getInt32(0)); 4192 } 4193 }; 4194 4195 /// \brief Recognize construction of vectors like 4196 /// %ra = insertelement <4 x float> undef, float %s0, i32 0 4197 /// %rb = insertelement <4 x float> %ra, float %s1, i32 1 4198 /// %rc = insertelement <4 x float> %rb, float %s2, i32 2 4199 /// %rd = insertelement <4 x float> %rc, float %s3, i32 3 4200 /// 4201 /// Returns true if it matches 4202 /// 4203 static bool findBuildVector(InsertElementInst *FirstInsertElem, 4204 SmallVectorImpl<Value *> &BuildVector, 4205 SmallVectorImpl<Value *> &BuildVectorOpds) { 4206 if (!isa<UndefValue>(FirstInsertElem->getOperand(0))) 4207 return false; 4208 4209 InsertElementInst *IE = FirstInsertElem; 4210 while (true) { 4211 BuildVector.push_back(IE); 4212 BuildVectorOpds.push_back(IE->getOperand(1)); 4213 4214 if (IE->use_empty()) 4215 return false; 4216 4217 InsertElementInst *NextUse = dyn_cast<InsertElementInst>(IE->user_back()); 4218 if (!NextUse) 4219 return true; 4220 4221 // If this isn't the final use, make sure the next insertelement is the only 4222 // use. It's OK if the final constructed vector is used multiple times 4223 if (!IE->hasOneUse()) 4224 return false; 4225 4226 IE = NextUse; 4227 } 4228 4229 return false; 4230 } 4231 4232 /// \brief Like findBuildVector, but looks backwards for construction of aggregate. 4233 /// 4234 /// \return true if it matches. 4235 static bool findBuildAggregate(InsertValueInst *IV, 4236 SmallVectorImpl<Value *> &BuildVector, 4237 SmallVectorImpl<Value *> &BuildVectorOpds) { 4238 if (!IV->hasOneUse()) 4239 return false; 4240 Value *V = IV->getAggregateOperand(); 4241 if (!isa<UndefValue>(V)) { 4242 InsertValueInst *I = dyn_cast<InsertValueInst>(V); 4243 if (!I || !findBuildAggregate(I, BuildVector, BuildVectorOpds)) 4244 return false; 4245 } 4246 BuildVector.push_back(IV); 4247 BuildVectorOpds.push_back(IV->getInsertedValueOperand()); 4248 return true; 4249 } 4250 4251 static bool PhiTypeSorterFunc(Value *V, Value *V2) { 4252 return V->getType() < V2->getType(); 4253 } 4254 4255 /// \brief Try and get a reduction value from a phi node. 4256 /// 4257 /// Given a phi node \p P in a block \p ParentBB, consider possible reductions 4258 /// if they come from either \p ParentBB or a containing loop latch. 4259 /// 4260 /// \returns A candidate reduction value if possible, or \code nullptr \endcode 4261 /// if not possible. 4262 static Value *getReductionValue(const DominatorTree *DT, PHINode *P, 4263 BasicBlock *ParentBB, LoopInfo *LI) { 4264 // There are situations where the reduction value is not dominated by the 4265 // reduction phi. Vectorizing such cases has been reported to cause 4266 // miscompiles. See PR25787. 4267 auto DominatedReduxValue = [&](Value *R) { 4268 return ( 4269 dyn_cast<Instruction>(R) && 4270 DT->dominates(P->getParent(), dyn_cast<Instruction>(R)->getParent())); 4271 }; 4272 4273 Value *Rdx = nullptr; 4274 4275 // Return the incoming value if it comes from the same BB as the phi node. 4276 if (P->getIncomingBlock(0) == ParentBB) { 4277 Rdx = P->getIncomingValue(0); 4278 } else if (P->getIncomingBlock(1) == ParentBB) { 4279 Rdx = P->getIncomingValue(1); 4280 } 4281 4282 if (Rdx && DominatedReduxValue(Rdx)) 4283 return Rdx; 4284 4285 // Otherwise, check whether we have a loop latch to look at. 4286 Loop *BBL = LI->getLoopFor(ParentBB); 4287 if (!BBL) 4288 return nullptr; 4289 BasicBlock *BBLatch = BBL->getLoopLatch(); 4290 if (!BBLatch) 4291 return nullptr; 4292 4293 // There is a loop latch, return the incoming value if it comes from 4294 // that. This reduction pattern occassionaly turns up. 4295 if (P->getIncomingBlock(0) == BBLatch) { 4296 Rdx = P->getIncomingValue(0); 4297 } else if (P->getIncomingBlock(1) == BBLatch) { 4298 Rdx = P->getIncomingValue(1); 4299 } 4300 4301 if (Rdx && DominatedReduxValue(Rdx)) 4302 return Rdx; 4303 4304 return nullptr; 4305 } 4306 4307 /// \brief Attempt to reduce a horizontal reduction. 4308 /// If it is legal to match a horizontal reduction feeding 4309 /// the phi node P with reduction operators BI, then check if it 4310 /// can be done. 4311 /// \returns true if a horizontal reduction was matched and reduced. 4312 /// \returns false if a horizontal reduction was not matched. 4313 static bool canMatchHorizontalReduction(PHINode *P, BinaryOperator *BI, 4314 BoUpSLP &R, TargetTransformInfo *TTI, 4315 unsigned MinRegSize) { 4316 if (!ShouldVectorizeHor) 4317 return false; 4318 4319 HorizontalReduction HorRdx(MinRegSize); 4320 if (!HorRdx.matchAssociativeReduction(P, BI)) 4321 return false; 4322 4323 // If there is a sufficient number of reduction values, reduce 4324 // to a nearby power-of-2. Can safely generate oversized 4325 // vectors and rely on the backend to split them to legal sizes. 4326 HorRdx.ReduxWidth = 4327 std::max((uint64_t)4, PowerOf2Floor(HorRdx.numReductionValues())); 4328 4329 return HorRdx.tryToReduce(R, TTI); 4330 } 4331 4332 bool SLPVectorizerPass::vectorizeChainsInBlock(BasicBlock *BB, BoUpSLP &R) { 4333 bool Changed = false; 4334 SmallVector<Value *, 4> Incoming; 4335 SmallSet<Value *, 16> VisitedInstrs; 4336 4337 bool HaveVectorizedPhiNodes = true; 4338 while (HaveVectorizedPhiNodes) { 4339 HaveVectorizedPhiNodes = false; 4340 4341 // Collect the incoming values from the PHIs. 4342 Incoming.clear(); 4343 for (Instruction &I : *BB) { 4344 PHINode *P = dyn_cast<PHINode>(&I); 4345 if (!P) 4346 break; 4347 4348 if (!VisitedInstrs.count(P)) 4349 Incoming.push_back(P); 4350 } 4351 4352 // Sort by type. 4353 std::stable_sort(Incoming.begin(), Incoming.end(), PhiTypeSorterFunc); 4354 4355 // Try to vectorize elements base on their type. 4356 for (SmallVector<Value *, 4>::iterator IncIt = Incoming.begin(), 4357 E = Incoming.end(); 4358 IncIt != E;) { 4359 4360 // Look for the next elements with the same type. 4361 SmallVector<Value *, 4>::iterator SameTypeIt = IncIt; 4362 while (SameTypeIt != E && 4363 (*SameTypeIt)->getType() == (*IncIt)->getType()) { 4364 VisitedInstrs.insert(*SameTypeIt); 4365 ++SameTypeIt; 4366 } 4367 4368 // Try to vectorize them. 4369 unsigned NumElts = (SameTypeIt - IncIt); 4370 DEBUG(errs() << "SLP: Trying to vectorize starting at PHIs (" << NumElts << ")\n"); 4371 if (NumElts > 1 && tryToVectorizeList(makeArrayRef(IncIt, NumElts), R)) { 4372 // Success start over because instructions might have been changed. 4373 HaveVectorizedPhiNodes = true; 4374 Changed = true; 4375 break; 4376 } 4377 4378 // Start over at the next instruction of a different type (or the end). 4379 IncIt = SameTypeIt; 4380 } 4381 } 4382 4383 VisitedInstrs.clear(); 4384 4385 for (BasicBlock::iterator it = BB->begin(), e = BB->end(); it != e; it++) { 4386 // We may go through BB multiple times so skip the one we have checked. 4387 if (!VisitedInstrs.insert(&*it).second) 4388 continue; 4389 4390 if (isa<DbgInfoIntrinsic>(it)) 4391 continue; 4392 4393 // Try to vectorize reductions that use PHINodes. 4394 if (PHINode *P = dyn_cast<PHINode>(it)) { 4395 // Check that the PHI is a reduction PHI. 4396 if (P->getNumIncomingValues() != 2) 4397 return Changed; 4398 4399 Value *Rdx = getReductionValue(DT, P, BB, LI); 4400 4401 // Check if this is a Binary Operator. 4402 BinaryOperator *BI = dyn_cast_or_null<BinaryOperator>(Rdx); 4403 if (!BI) 4404 continue; 4405 4406 // Try to match and vectorize a horizontal reduction. 4407 if (canMatchHorizontalReduction(P, BI, R, TTI, R.getMinVecRegSize())) { 4408 Changed = true; 4409 it = BB->begin(); 4410 e = BB->end(); 4411 continue; 4412 } 4413 4414 Value *Inst = BI->getOperand(0); 4415 if (Inst == P) 4416 Inst = BI->getOperand(1); 4417 4418 if (tryToVectorize(dyn_cast<BinaryOperator>(Inst), R)) { 4419 // We would like to start over since some instructions are deleted 4420 // and the iterator may become invalid value. 4421 Changed = true; 4422 it = BB->begin(); 4423 e = BB->end(); 4424 continue; 4425 } 4426 4427 continue; 4428 } 4429 4430 if (ShouldStartVectorizeHorAtStore) 4431 if (StoreInst *SI = dyn_cast<StoreInst>(it)) 4432 if (BinaryOperator *BinOp = 4433 dyn_cast<BinaryOperator>(SI->getValueOperand())) { 4434 if (canMatchHorizontalReduction(nullptr, BinOp, R, TTI, 4435 R.getMinVecRegSize()) || 4436 tryToVectorize(BinOp, R)) { 4437 Changed = true; 4438 it = BB->begin(); 4439 e = BB->end(); 4440 continue; 4441 } 4442 } 4443 4444 // Try to vectorize horizontal reductions feeding into a return. 4445 if (ReturnInst *RI = dyn_cast<ReturnInst>(it)) 4446 if (RI->getNumOperands() != 0) 4447 if (BinaryOperator *BinOp = 4448 dyn_cast<BinaryOperator>(RI->getOperand(0))) { 4449 DEBUG(dbgs() << "SLP: Found a return to vectorize.\n"); 4450 if (tryToVectorizePair(BinOp->getOperand(0), 4451 BinOp->getOperand(1), R)) { 4452 Changed = true; 4453 it = BB->begin(); 4454 e = BB->end(); 4455 continue; 4456 } 4457 } 4458 4459 // Try to vectorize trees that start at compare instructions. 4460 if (CmpInst *CI = dyn_cast<CmpInst>(it)) { 4461 if (tryToVectorizePair(CI->getOperand(0), CI->getOperand(1), R)) { 4462 Changed = true; 4463 // We would like to start over since some instructions are deleted 4464 // and the iterator may become invalid value. 4465 it = BB->begin(); 4466 e = BB->end(); 4467 continue; 4468 } 4469 4470 for (int i = 0; i < 2; ++i) { 4471 if (BinaryOperator *BI = dyn_cast<BinaryOperator>(CI->getOperand(i))) { 4472 if (tryToVectorizePair(BI->getOperand(0), BI->getOperand(1), R)) { 4473 Changed = true; 4474 // We would like to start over since some instructions are deleted 4475 // and the iterator may become invalid value. 4476 it = BB->begin(); 4477 e = BB->end(); 4478 break; 4479 } 4480 } 4481 } 4482 continue; 4483 } 4484 4485 // Try to vectorize trees that start at insertelement instructions. 4486 if (InsertElementInst *FirstInsertElem = dyn_cast<InsertElementInst>(it)) { 4487 SmallVector<Value *, 16> BuildVector; 4488 SmallVector<Value *, 16> BuildVectorOpds; 4489 if (!findBuildVector(FirstInsertElem, BuildVector, BuildVectorOpds)) 4490 continue; 4491 4492 // Vectorize starting with the build vector operands ignoring the 4493 // BuildVector instructions for the purpose of scheduling and user 4494 // extraction. 4495 if (tryToVectorizeList(BuildVectorOpds, R, BuildVector)) { 4496 Changed = true; 4497 it = BB->begin(); 4498 e = BB->end(); 4499 } 4500 4501 continue; 4502 } 4503 4504 // Try to vectorize trees that start at insertvalue instructions feeding into 4505 // a store. 4506 if (StoreInst *SI = dyn_cast<StoreInst>(it)) { 4507 if (InsertValueInst *LastInsertValue = dyn_cast<InsertValueInst>(SI->getValueOperand())) { 4508 const DataLayout &DL = BB->getModule()->getDataLayout(); 4509 if (R.canMapToVector(SI->getValueOperand()->getType(), DL)) { 4510 SmallVector<Value *, 16> BuildVector; 4511 SmallVector<Value *, 16> BuildVectorOpds; 4512 if (!findBuildAggregate(LastInsertValue, BuildVector, BuildVectorOpds)) 4513 continue; 4514 4515 DEBUG(dbgs() << "SLP: store of array mappable to vector: " << *SI << "\n"); 4516 if (tryToVectorizeList(BuildVectorOpds, R, BuildVector, false)) { 4517 Changed = true; 4518 it = BB->begin(); 4519 e = BB->end(); 4520 } 4521 continue; 4522 } 4523 } 4524 } 4525 } 4526 4527 return Changed; 4528 } 4529 4530 bool SLPVectorizerPass::vectorizeGEPIndices(BasicBlock *BB, BoUpSLP &R) { 4531 auto Changed = false; 4532 for (auto &Entry : GEPs) { 4533 4534 // If the getelementptr list has fewer than two elements, there's nothing 4535 // to do. 4536 if (Entry.second.size() < 2) 4537 continue; 4538 4539 DEBUG(dbgs() << "SLP: Analyzing a getelementptr list of length " 4540 << Entry.second.size() << ".\n"); 4541 4542 // We process the getelementptr list in chunks of 16 (like we do for 4543 // stores) to minimize compile-time. 4544 for (unsigned BI = 0, BE = Entry.second.size(); BI < BE; BI += 16) { 4545 auto Len = std::min<unsigned>(BE - BI, 16); 4546 auto GEPList = makeArrayRef(&Entry.second[BI], Len); 4547 4548 // Initialize a set a candidate getelementptrs. Note that we use a 4549 // SetVector here to preserve program order. If the index computations 4550 // are vectorizable and begin with loads, we want to minimize the chance 4551 // of having to reorder them later. 4552 SetVector<Value *> Candidates(GEPList.begin(), GEPList.end()); 4553 4554 // Some of the candidates may have already been vectorized after we 4555 // initially collected them. If so, the WeakVHs will have nullified the 4556 // values, so remove them from the set of candidates. 4557 Candidates.remove(nullptr); 4558 4559 // Remove from the set of candidates all pairs of getelementptrs with 4560 // constant differences. Such getelementptrs are likely not good 4561 // candidates for vectorization in a bottom-up phase since one can be 4562 // computed from the other. We also ensure all candidate getelementptr 4563 // indices are unique. 4564 for (int I = 0, E = GEPList.size(); I < E && Candidates.size() > 1; ++I) { 4565 auto *GEPI = cast<GetElementPtrInst>(GEPList[I]); 4566 if (!Candidates.count(GEPI)) 4567 continue; 4568 auto *SCEVI = SE->getSCEV(GEPList[I]); 4569 for (int J = I + 1; J < E && Candidates.size() > 1; ++J) { 4570 auto *GEPJ = cast<GetElementPtrInst>(GEPList[J]); 4571 auto *SCEVJ = SE->getSCEV(GEPList[J]); 4572 if (isa<SCEVConstant>(SE->getMinusSCEV(SCEVI, SCEVJ))) { 4573 Candidates.remove(GEPList[I]); 4574 Candidates.remove(GEPList[J]); 4575 } else if (GEPI->idx_begin()->get() == GEPJ->idx_begin()->get()) { 4576 Candidates.remove(GEPList[J]); 4577 } 4578 } 4579 } 4580 4581 // We break out of the above computation as soon as we know there are 4582 // fewer than two candidates remaining. 4583 if (Candidates.size() < 2) 4584 continue; 4585 4586 // Add the single, non-constant index of each candidate to the bundle. We 4587 // ensured the indices met these constraints when we originally collected 4588 // the getelementptrs. 4589 SmallVector<Value *, 16> Bundle(Candidates.size()); 4590 auto BundleIndex = 0u; 4591 for (auto *V : Candidates) { 4592 auto *GEP = cast<GetElementPtrInst>(V); 4593 auto *GEPIdx = GEP->idx_begin()->get(); 4594 assert(GEP->getNumIndices() == 1 || !isa<Constant>(GEPIdx)); 4595 Bundle[BundleIndex++] = GEPIdx; 4596 } 4597 4598 // Try and vectorize the indices. We are currently only interested in 4599 // gather-like cases of the form: 4600 // 4601 // ... = g[a[0] - b[0]] + g[a[1] - b[1]] + ... 4602 // 4603 // where the loads of "a", the loads of "b", and the subtractions can be 4604 // performed in parallel. It's likely that detecting this pattern in a 4605 // bottom-up phase will be simpler and less costly than building a 4606 // full-blown top-down phase beginning at the consecutive loads. 4607 Changed |= tryToVectorizeList(Bundle, R); 4608 } 4609 } 4610 return Changed; 4611 } 4612 4613 bool SLPVectorizerPass::vectorizeStoreChains(BoUpSLP &R) { 4614 bool Changed = false; 4615 // Attempt to sort and vectorize each of the store-groups. 4616 for (StoreListMap::iterator it = Stores.begin(), e = Stores.end(); it != e; 4617 ++it) { 4618 if (it->second.size() < 2) 4619 continue; 4620 4621 DEBUG(dbgs() << "SLP: Analyzing a store chain of length " 4622 << it->second.size() << ".\n"); 4623 4624 // Process the stores in chunks of 16. 4625 // TODO: The limit of 16 inhibits greater vectorization factors. 4626 // For example, AVX2 supports v32i8. Increasing this limit, however, 4627 // may cause a significant compile-time increase. 4628 for (unsigned CI = 0, CE = it->second.size(); CI < CE; CI+=16) { 4629 unsigned Len = std::min<unsigned>(CE - CI, 16); 4630 Changed |= vectorizeStores(makeArrayRef(&it->second[CI], Len), 4631 -SLPCostThreshold, R); 4632 } 4633 } 4634 return Changed; 4635 } 4636 4637 char SLPVectorizer::ID = 0; 4638 static const char lv_name[] = "SLP Vectorizer"; 4639 INITIALIZE_PASS_BEGIN(SLPVectorizer, SV_NAME, lv_name, false, false) 4640 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) 4641 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass) 4642 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) 4643 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass) 4644 INITIALIZE_PASS_DEPENDENCY(LoopSimplify) 4645 INITIALIZE_PASS_DEPENDENCY(DemandedBitsWrapperPass) 4646 INITIALIZE_PASS_END(SLPVectorizer, SV_NAME, lv_name, false, false) 4647 4648 namespace llvm { 4649 Pass *createSLPVectorizerPass() { return new SLPVectorizer(); } 4650 } 4651