LoopVectorize.cpp revision 36b56886974eae4f9c5ebc96befd3e7bfe5de338
1//===- LoopVectorize.cpp - A Loop 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// 10// This is the LLVM loop vectorizer. This pass modifies 'vectorizable' loops 11// and generates target-independent LLVM-IR. 12// The vectorizer uses the TargetTransformInfo analysis to estimate the costs 13// of instructions in order to estimate the profitability of vectorization. 14// 15// The loop vectorizer combines consecutive loop iterations into a single 16// 'wide' iteration. After this transformation the index is incremented 17// by the SIMD vector width, and not by one. 18// 19// This pass has three parts: 20// 1. The main loop pass that drives the different parts. 21// 2. LoopVectorizationLegality - A unit that checks for the legality 22// of the vectorization. 23// 3. InnerLoopVectorizer - A unit that performs the actual 24// widening of instructions. 25// 4. LoopVectorizationCostModel - A unit that checks for the profitability 26// of vectorization. It decides on the optimal vector width, which 27// can be one, if vectorization is not profitable. 28// 29//===----------------------------------------------------------------------===// 30// 31// The reduction-variable vectorization is based on the paper: 32// D. Nuzman and R. Henderson. Multi-platform Auto-vectorization. 33// 34// Variable uniformity checks are inspired by: 35// Karrenberg, R. and Hack, S. Whole Function Vectorization. 36// 37// Other ideas/concepts are from: 38// A. Zaks and D. Nuzman. Autovectorization in GCC-two years later. 39// 40// S. Maleki, Y. Gao, M. Garzaran, T. Wong and D. Padua. An Evaluation of 41// Vectorizing Compilers. 42// 43//===----------------------------------------------------------------------===// 44 45#define LV_NAME "loop-vectorize" 46#define DEBUG_TYPE LV_NAME 47 48#include "llvm/Transforms/Vectorize.h" 49#include "llvm/ADT/DenseMap.h" 50#include "llvm/ADT/EquivalenceClasses.h" 51#include "llvm/ADT/Hashing.h" 52#include "llvm/ADT/MapVector.h" 53#include "llvm/ADT/SetVector.h" 54#include "llvm/ADT/SmallPtrSet.h" 55#include "llvm/ADT/SmallSet.h" 56#include "llvm/ADT/SmallVector.h" 57#include "llvm/ADT/StringExtras.h" 58#include "llvm/Analysis/AliasAnalysis.h" 59#include "llvm/Analysis/BlockFrequencyInfo.h" 60#include "llvm/Analysis/LoopInfo.h" 61#include "llvm/Analysis/LoopIterator.h" 62#include "llvm/Analysis/LoopPass.h" 63#include "llvm/Analysis/ScalarEvolution.h" 64#include "llvm/Analysis/ScalarEvolutionExpander.h" 65#include "llvm/Analysis/ScalarEvolutionExpressions.h" 66#include "llvm/Analysis/TargetTransformInfo.h" 67#include "llvm/Analysis/ValueTracking.h" 68#include "llvm/IR/Constants.h" 69#include "llvm/IR/DataLayout.h" 70#include "llvm/IR/DerivedTypes.h" 71#include "llvm/IR/Dominators.h" 72#include "llvm/IR/Function.h" 73#include "llvm/IR/IRBuilder.h" 74#include "llvm/IR/Instructions.h" 75#include "llvm/IR/IntrinsicInst.h" 76#include "llvm/IR/LLVMContext.h" 77#include "llvm/IR/Module.h" 78#include "llvm/IR/PatternMatch.h" 79#include "llvm/IR/Type.h" 80#include "llvm/IR/Value.h" 81#include "llvm/IR/ValueHandle.h" 82#include "llvm/IR/Verifier.h" 83#include "llvm/Pass.h" 84#include "llvm/Support/BranchProbability.h" 85#include "llvm/Support/CommandLine.h" 86#include "llvm/Support/Debug.h" 87#include "llvm/Support/raw_ostream.h" 88#include "llvm/Target/TargetLibraryInfo.h" 89#include "llvm/Transforms/Scalar.h" 90#include "llvm/Transforms/Utils/BasicBlockUtils.h" 91#include "llvm/Transforms/Utils/Local.h" 92#include <algorithm> 93#include <map> 94 95using namespace llvm; 96using namespace llvm::PatternMatch; 97 98static cl::opt<unsigned> 99VectorizationFactor("force-vector-width", cl::init(0), cl::Hidden, 100 cl::desc("Sets the SIMD width. Zero is autoselect.")); 101 102static cl::opt<unsigned> 103VectorizationUnroll("force-vector-unroll", cl::init(0), cl::Hidden, 104 cl::desc("Sets the vectorization unroll count. " 105 "Zero is autoselect.")); 106 107static cl::opt<bool> 108EnableIfConversion("enable-if-conversion", cl::init(true), cl::Hidden, 109 cl::desc("Enable if-conversion during vectorization.")); 110 111/// We don't vectorize loops with a known constant trip count below this number. 112static cl::opt<unsigned> 113TinyTripCountVectorThreshold("vectorizer-min-trip-count", cl::init(16), 114 cl::Hidden, 115 cl::desc("Don't vectorize loops with a constant " 116 "trip count that is smaller than this " 117 "value.")); 118 119/// This enables versioning on the strides of symbolically striding memory 120/// accesses in code like the following. 121/// for (i = 0; i < N; ++i) 122/// A[i * Stride1] += B[i * Stride2] ... 123/// 124/// Will be roughly translated to 125/// if (Stride1 == 1 && Stride2 == 1) { 126/// for (i = 0; i < N; i+=4) 127/// A[i:i+3] += ... 128/// } else 129/// ... 130static cl::opt<bool> EnableMemAccessVersioning( 131 "enable-mem-access-versioning", cl::init(true), cl::Hidden, 132 cl::desc("Enable symblic stride memory access versioning")); 133 134/// We don't unroll loops with a known constant trip count below this number. 135static const unsigned TinyTripCountUnrollThreshold = 128; 136 137/// When performing memory disambiguation checks at runtime do not make more 138/// than this number of comparisons. 139static const unsigned RuntimeMemoryCheckThreshold = 8; 140 141/// Maximum simd width. 142static const unsigned MaxVectorWidth = 64; 143 144static cl::opt<unsigned> ForceTargetNumScalarRegs( 145 "force-target-num-scalar-regs", cl::init(0), cl::Hidden, 146 cl::desc("A flag that overrides the target's number of scalar registers.")); 147 148static cl::opt<unsigned> ForceTargetNumVectorRegs( 149 "force-target-num-vector-regs", cl::init(0), cl::Hidden, 150 cl::desc("A flag that overrides the target's number of vector registers.")); 151 152/// Maximum vectorization unroll count. 153static const unsigned MaxUnrollFactor = 16; 154 155static cl::opt<unsigned> ForceTargetMaxScalarUnrollFactor( 156 "force-target-max-scalar-unroll", cl::init(0), cl::Hidden, 157 cl::desc("A flag that overrides the target's max unroll factor for scalar " 158 "loops.")); 159 160static cl::opt<unsigned> ForceTargetMaxVectorUnrollFactor( 161 "force-target-max-vector-unroll", cl::init(0), cl::Hidden, 162 cl::desc("A flag that overrides the target's max unroll factor for " 163 "vectorized loops.")); 164 165static cl::opt<unsigned> ForceTargetInstructionCost( 166 "force-target-instruction-cost", cl::init(0), cl::Hidden, 167 cl::desc("A flag that overrides the target's expected cost for " 168 "an instruction to a single constant value. Mostly " 169 "useful for getting consistent testing.")); 170 171static cl::opt<unsigned> SmallLoopCost( 172 "small-loop-cost", cl::init(20), cl::Hidden, 173 cl::desc("The cost of a loop that is considered 'small' by the unroller.")); 174 175static cl::opt<bool> LoopVectorizeWithBlockFrequency( 176 "loop-vectorize-with-block-frequency", cl::init(false), cl::Hidden, 177 cl::desc("Enable the use of the block frequency analysis to access PGO " 178 "heuristics minimizing code growth in cold regions and being more " 179 "aggressive in hot regions.")); 180 181// Runtime unroll loops for load/store throughput. 182static cl::opt<bool> EnableLoadStoreRuntimeUnroll( 183 "enable-loadstore-runtime-unroll", cl::init(true), cl::Hidden, 184 cl::desc("Enable runtime unrolling until load/store ports are saturated")); 185 186/// The number of stores in a loop that are allowed to need predication. 187static cl::opt<unsigned> NumberOfStoresToPredicate( 188 "vectorize-num-stores-pred", cl::init(1), cl::Hidden, 189 cl::desc("Max number of stores to be predicated behind an if.")); 190 191static cl::opt<bool> EnableIndVarRegisterHeur( 192 "enable-ind-var-reg-heur", cl::init(true), cl::Hidden, 193 cl::desc("Count the induction variable only once when unrolling")); 194 195static cl::opt<bool> EnableCondStoresVectorization( 196 "enable-cond-stores-vec", cl::init(false), cl::Hidden, 197 cl::desc("Enable if predication of stores during vectorization.")); 198 199namespace { 200 201// Forward declarations. 202class LoopVectorizationLegality; 203class LoopVectorizationCostModel; 204 205/// InnerLoopVectorizer vectorizes loops which contain only one basic 206/// block to a specified vectorization factor (VF). 207/// This class performs the widening of scalars into vectors, or multiple 208/// scalars. This class also implements the following features: 209/// * It inserts an epilogue loop for handling loops that don't have iteration 210/// counts that are known to be a multiple of the vectorization factor. 211/// * It handles the code generation for reduction variables. 212/// * Scalarization (implementation using scalars) of un-vectorizable 213/// instructions. 214/// InnerLoopVectorizer does not perform any vectorization-legality 215/// checks, and relies on the caller to check for the different legality 216/// aspects. The InnerLoopVectorizer relies on the 217/// LoopVectorizationLegality class to provide information about the induction 218/// and reduction variables that were found to a given vectorization factor. 219class InnerLoopVectorizer { 220public: 221 InnerLoopVectorizer(Loop *OrigLoop, ScalarEvolution *SE, LoopInfo *LI, 222 DominatorTree *DT, const DataLayout *DL, 223 const TargetLibraryInfo *TLI, unsigned VecWidth, 224 unsigned UnrollFactor) 225 : OrigLoop(OrigLoop), SE(SE), LI(LI), DT(DT), DL(DL), TLI(TLI), 226 VF(VecWidth), UF(UnrollFactor), Builder(SE->getContext()), Induction(0), 227 OldInduction(0), WidenMap(UnrollFactor), Legal(0) {} 228 229 // Perform the actual loop widening (vectorization). 230 void vectorize(LoopVectorizationLegality *L) { 231 Legal = L; 232 // Create a new empty loop. Unlink the old loop and connect the new one. 233 createEmptyLoop(); 234 // Widen each instruction in the old loop to a new one in the new loop. 235 // Use the Legality module to find the induction and reduction variables. 236 vectorizeLoop(); 237 // Register the new loop and update the analysis passes. 238 updateAnalysis(); 239 } 240 241 virtual ~InnerLoopVectorizer() {} 242 243protected: 244 /// A small list of PHINodes. 245 typedef SmallVector<PHINode*, 4> PhiVector; 246 /// When we unroll loops we have multiple vector values for each scalar. 247 /// This data structure holds the unrolled and vectorized values that 248 /// originated from one scalar instruction. 249 typedef SmallVector<Value*, 2> VectorParts; 250 251 // When we if-convert we need create edge masks. We have to cache values so 252 // that we don't end up with exponential recursion/IR. 253 typedef DenseMap<std::pair<BasicBlock*, BasicBlock*>, 254 VectorParts> EdgeMaskCache; 255 256 /// \brief Add code that checks at runtime if the accessed arrays overlap. 257 /// 258 /// Returns a pair of instructions where the first element is the first 259 /// instruction generated in possibly a sequence of instructions and the 260 /// second value is the final comparator value or NULL if no check is needed. 261 std::pair<Instruction *, Instruction *> addRuntimeCheck(Instruction *Loc); 262 263 /// \brief Add checks for strides that where assumed to be 1. 264 /// 265 /// Returns the last check instruction and the first check instruction in the 266 /// pair as (first, last). 267 std::pair<Instruction *, Instruction *> addStrideCheck(Instruction *Loc); 268 269 /// Create an empty loop, based on the loop ranges of the old loop. 270 void createEmptyLoop(); 271 /// Copy and widen the instructions from the old loop. 272 virtual void vectorizeLoop(); 273 274 /// \brief The Loop exit block may have single value PHI nodes where the 275 /// incoming value is 'Undef'. While vectorizing we only handled real values 276 /// that were defined inside the loop. Here we fix the 'undef case'. 277 /// See PR14725. 278 void fixLCSSAPHIs(); 279 280 /// A helper function that computes the predicate of the block BB, assuming 281 /// that the header block of the loop is set to True. It returns the *entry* 282 /// mask for the block BB. 283 VectorParts createBlockInMask(BasicBlock *BB); 284 /// A helper function that computes the predicate of the edge between SRC 285 /// and DST. 286 VectorParts createEdgeMask(BasicBlock *Src, BasicBlock *Dst); 287 288 /// A helper function to vectorize a single BB within the innermost loop. 289 void vectorizeBlockInLoop(BasicBlock *BB, PhiVector *PV); 290 291 /// Vectorize a single PHINode in a block. This method handles the induction 292 /// variable canonicalization. It supports both VF = 1 for unrolled loops and 293 /// arbitrary length vectors. 294 void widenPHIInstruction(Instruction *PN, VectorParts &Entry, 295 unsigned UF, unsigned VF, PhiVector *PV); 296 297 /// Insert the new loop to the loop hierarchy and pass manager 298 /// and update the analysis passes. 299 void updateAnalysis(); 300 301 /// This instruction is un-vectorizable. Implement it as a sequence 302 /// of scalars. If \p IfPredicateStore is true we need to 'hide' each 303 /// scalarized instruction behind an if block predicated on the control 304 /// dependence of the instruction. 305 virtual void scalarizeInstruction(Instruction *Instr, 306 bool IfPredicateStore=false); 307 308 /// Vectorize Load and Store instructions, 309 virtual void vectorizeMemoryInstruction(Instruction *Instr); 310 311 /// Create a broadcast instruction. This method generates a broadcast 312 /// instruction (shuffle) for loop invariant values and for the induction 313 /// value. If this is the induction variable then we extend it to N, N+1, ... 314 /// this is needed because each iteration in the loop corresponds to a SIMD 315 /// element. 316 virtual Value *getBroadcastInstrs(Value *V); 317 318 /// This function adds 0, 1, 2 ... to each vector element, starting at zero. 319 /// If Negate is set then negative numbers are added e.g. (0, -1, -2, ...). 320 /// The sequence starts at StartIndex. 321 virtual Value *getConsecutiveVector(Value* Val, int StartIdx, bool Negate); 322 323 /// When we go over instructions in the basic block we rely on previous 324 /// values within the current basic block or on loop invariant values. 325 /// When we widen (vectorize) values we place them in the map. If the values 326 /// are not within the map, they have to be loop invariant, so we simply 327 /// broadcast them into a vector. 328 VectorParts &getVectorValue(Value *V); 329 330 /// Generate a shuffle sequence that will reverse the vector Vec. 331 virtual Value *reverseVector(Value *Vec); 332 333 /// This is a helper class that holds the vectorizer state. It maps scalar 334 /// instructions to vector instructions. When the code is 'unrolled' then 335 /// then a single scalar value is mapped to multiple vector parts. The parts 336 /// are stored in the VectorPart type. 337 struct ValueMap { 338 /// C'tor. UnrollFactor controls the number of vectors ('parts') that 339 /// are mapped. 340 ValueMap(unsigned UnrollFactor) : UF(UnrollFactor) {} 341 342 /// \return True if 'Key' is saved in the Value Map. 343 bool has(Value *Key) const { return MapStorage.count(Key); } 344 345 /// Initializes a new entry in the map. Sets all of the vector parts to the 346 /// save value in 'Val'. 347 /// \return A reference to a vector with splat values. 348 VectorParts &splat(Value *Key, Value *Val) { 349 VectorParts &Entry = MapStorage[Key]; 350 Entry.assign(UF, Val); 351 return Entry; 352 } 353 354 ///\return A reference to the value that is stored at 'Key'. 355 VectorParts &get(Value *Key) { 356 VectorParts &Entry = MapStorage[Key]; 357 if (Entry.empty()) 358 Entry.resize(UF); 359 assert(Entry.size() == UF); 360 return Entry; 361 } 362 363 private: 364 /// The unroll factor. Each entry in the map stores this number of vector 365 /// elements. 366 unsigned UF; 367 368 /// Map storage. We use std::map and not DenseMap because insertions to a 369 /// dense map invalidates its iterators. 370 std::map<Value *, VectorParts> MapStorage; 371 }; 372 373 /// The original loop. 374 Loop *OrigLoop; 375 /// Scev analysis to use. 376 ScalarEvolution *SE; 377 /// Loop Info. 378 LoopInfo *LI; 379 /// Dominator Tree. 380 DominatorTree *DT; 381 /// Data Layout. 382 const DataLayout *DL; 383 /// Target Library Info. 384 const TargetLibraryInfo *TLI; 385 386 /// The vectorization SIMD factor to use. Each vector will have this many 387 /// vector elements. 388 unsigned VF; 389 390protected: 391 /// The vectorization unroll factor to use. Each scalar is vectorized to this 392 /// many different vector instructions. 393 unsigned UF; 394 395 /// The builder that we use 396 IRBuilder<> Builder; 397 398 // --- Vectorization state --- 399 400 /// The vector-loop preheader. 401 BasicBlock *LoopVectorPreHeader; 402 /// The scalar-loop preheader. 403 BasicBlock *LoopScalarPreHeader; 404 /// Middle Block between the vector and the scalar. 405 BasicBlock *LoopMiddleBlock; 406 ///The ExitBlock of the scalar loop. 407 BasicBlock *LoopExitBlock; 408 ///The vector loop body. 409 SmallVector<BasicBlock *, 4> LoopVectorBody; 410 ///The scalar loop body. 411 BasicBlock *LoopScalarBody; 412 /// A list of all bypass blocks. The first block is the entry of the loop. 413 SmallVector<BasicBlock *, 4> LoopBypassBlocks; 414 415 /// The new Induction variable which was added to the new block. 416 PHINode *Induction; 417 /// The induction variable of the old basic block. 418 PHINode *OldInduction; 419 /// Holds the extended (to the widest induction type) start index. 420 Value *ExtendedIdx; 421 /// Maps scalars to widened vectors. 422 ValueMap WidenMap; 423 EdgeMaskCache MaskCache; 424 425 LoopVectorizationLegality *Legal; 426}; 427 428class InnerLoopUnroller : public InnerLoopVectorizer { 429public: 430 InnerLoopUnroller(Loop *OrigLoop, ScalarEvolution *SE, LoopInfo *LI, 431 DominatorTree *DT, const DataLayout *DL, 432 const TargetLibraryInfo *TLI, unsigned UnrollFactor) : 433 InnerLoopVectorizer(OrigLoop, SE, LI, DT, DL, TLI, 1, UnrollFactor) { } 434 435private: 436 void scalarizeInstruction(Instruction *Instr, 437 bool IfPredicateStore = false) override; 438 void vectorizeMemoryInstruction(Instruction *Instr) override; 439 Value *getBroadcastInstrs(Value *V) override; 440 Value *getConsecutiveVector(Value* Val, int StartIdx, bool Negate) override; 441 Value *reverseVector(Value *Vec) override; 442}; 443 444/// \brief Look for a meaningful debug location on the instruction or it's 445/// operands. 446static Instruction *getDebugLocFromInstOrOperands(Instruction *I) { 447 if (!I) 448 return I; 449 450 DebugLoc Empty; 451 if (I->getDebugLoc() != Empty) 452 return I; 453 454 for (User::op_iterator OI = I->op_begin(), OE = I->op_end(); OI != OE; ++OI) { 455 if (Instruction *OpInst = dyn_cast<Instruction>(*OI)) 456 if (OpInst->getDebugLoc() != Empty) 457 return OpInst; 458 } 459 460 return I; 461} 462 463/// \brief Set the debug location in the builder using the debug location in the 464/// instruction. 465static void setDebugLocFromInst(IRBuilder<> &B, const Value *Ptr) { 466 if (const Instruction *Inst = dyn_cast_or_null<Instruction>(Ptr)) 467 B.SetCurrentDebugLocation(Inst->getDebugLoc()); 468 else 469 B.SetCurrentDebugLocation(DebugLoc()); 470} 471 472/// LoopVectorizationLegality checks if it is legal to vectorize a loop, and 473/// to what vectorization factor. 474/// This class does not look at the profitability of vectorization, only the 475/// legality. This class has two main kinds of checks: 476/// * Memory checks - The code in canVectorizeMemory checks if vectorization 477/// will change the order of memory accesses in a way that will change the 478/// correctness of the program. 479/// * Scalars checks - The code in canVectorizeInstrs and canVectorizeMemory 480/// checks for a number of different conditions, such as the availability of a 481/// single induction variable, that all types are supported and vectorize-able, 482/// etc. This code reflects the capabilities of InnerLoopVectorizer. 483/// This class is also used by InnerLoopVectorizer for identifying 484/// induction variable and the different reduction variables. 485class LoopVectorizationLegality { 486public: 487 unsigned NumLoads; 488 unsigned NumStores; 489 unsigned NumPredStores; 490 491 LoopVectorizationLegality(Loop *L, ScalarEvolution *SE, const DataLayout *DL, 492 DominatorTree *DT, TargetLibraryInfo *TLI) 493 : NumLoads(0), NumStores(0), NumPredStores(0), TheLoop(L), SE(SE), DL(DL), 494 DT(DT), TLI(TLI), Induction(0), WidestIndTy(0), HasFunNoNaNAttr(false), 495 MaxSafeDepDistBytes(-1U) {} 496 497 /// This enum represents the kinds of reductions that we support. 498 enum ReductionKind { 499 RK_NoReduction, ///< Not a reduction. 500 RK_IntegerAdd, ///< Sum of integers. 501 RK_IntegerMult, ///< Product of integers. 502 RK_IntegerOr, ///< Bitwise or logical OR of numbers. 503 RK_IntegerAnd, ///< Bitwise or logical AND of numbers. 504 RK_IntegerXor, ///< Bitwise or logical XOR of numbers. 505 RK_IntegerMinMax, ///< Min/max implemented in terms of select(cmp()). 506 RK_FloatAdd, ///< Sum of floats. 507 RK_FloatMult, ///< Product of floats. 508 RK_FloatMinMax ///< Min/max implemented in terms of select(cmp()). 509 }; 510 511 /// This enum represents the kinds of inductions that we support. 512 enum InductionKind { 513 IK_NoInduction, ///< Not an induction variable. 514 IK_IntInduction, ///< Integer induction variable. Step = 1. 515 IK_ReverseIntInduction, ///< Reverse int induction variable. Step = -1. 516 IK_PtrInduction, ///< Pointer induction var. Step = sizeof(elem). 517 IK_ReversePtrInduction ///< Reverse ptr indvar. Step = - sizeof(elem). 518 }; 519 520 // This enum represents the kind of minmax reduction. 521 enum MinMaxReductionKind { 522 MRK_Invalid, 523 MRK_UIntMin, 524 MRK_UIntMax, 525 MRK_SIntMin, 526 MRK_SIntMax, 527 MRK_FloatMin, 528 MRK_FloatMax 529 }; 530 531 /// This struct holds information about reduction variables. 532 struct ReductionDescriptor { 533 ReductionDescriptor() : StartValue(0), LoopExitInstr(0), 534 Kind(RK_NoReduction), MinMaxKind(MRK_Invalid) {} 535 536 ReductionDescriptor(Value *Start, Instruction *Exit, ReductionKind K, 537 MinMaxReductionKind MK) 538 : StartValue(Start), LoopExitInstr(Exit), Kind(K), MinMaxKind(MK) {} 539 540 // The starting value of the reduction. 541 // It does not have to be zero! 542 TrackingVH<Value> StartValue; 543 // The instruction who's value is used outside the loop. 544 Instruction *LoopExitInstr; 545 // The kind of the reduction. 546 ReductionKind Kind; 547 // If this a min/max reduction the kind of reduction. 548 MinMaxReductionKind MinMaxKind; 549 }; 550 551 /// This POD struct holds information about a potential reduction operation. 552 struct ReductionInstDesc { 553 ReductionInstDesc(bool IsRedux, Instruction *I) : 554 IsReduction(IsRedux), PatternLastInst(I), MinMaxKind(MRK_Invalid) {} 555 556 ReductionInstDesc(Instruction *I, MinMaxReductionKind K) : 557 IsReduction(true), PatternLastInst(I), MinMaxKind(K) {} 558 559 // Is this instruction a reduction candidate. 560 bool IsReduction; 561 // The last instruction in a min/max pattern (select of the select(icmp()) 562 // pattern), or the current reduction instruction otherwise. 563 Instruction *PatternLastInst; 564 // If this is a min/max pattern the comparison predicate. 565 MinMaxReductionKind MinMaxKind; 566 }; 567 568 /// This struct holds information about the memory runtime legality 569 /// check that a group of pointers do not overlap. 570 struct RuntimePointerCheck { 571 RuntimePointerCheck() : Need(false) {} 572 573 /// Reset the state of the pointer runtime information. 574 void reset() { 575 Need = false; 576 Pointers.clear(); 577 Starts.clear(); 578 Ends.clear(); 579 IsWritePtr.clear(); 580 DependencySetId.clear(); 581 } 582 583 /// Insert a pointer and calculate the start and end SCEVs. 584 void insert(ScalarEvolution *SE, Loop *Lp, Value *Ptr, bool WritePtr, 585 unsigned DepSetId, ValueToValueMap &Strides); 586 587 /// This flag indicates if we need to add the runtime check. 588 bool Need; 589 /// Holds the pointers that we need to check. 590 SmallVector<TrackingVH<Value>, 2> Pointers; 591 /// Holds the pointer value at the beginning of the loop. 592 SmallVector<const SCEV*, 2> Starts; 593 /// Holds the pointer value at the end of the loop. 594 SmallVector<const SCEV*, 2> Ends; 595 /// Holds the information if this pointer is used for writing to memory. 596 SmallVector<bool, 2> IsWritePtr; 597 /// Holds the id of the set of pointers that could be dependent because of a 598 /// shared underlying object. 599 SmallVector<unsigned, 2> DependencySetId; 600 }; 601 602 /// A struct for saving information about induction variables. 603 struct InductionInfo { 604 InductionInfo(Value *Start, InductionKind K) : StartValue(Start), IK(K) {} 605 InductionInfo() : StartValue(0), IK(IK_NoInduction) {} 606 /// Start value. 607 TrackingVH<Value> StartValue; 608 /// Induction kind. 609 InductionKind IK; 610 }; 611 612 /// ReductionList contains the reduction descriptors for all 613 /// of the reductions that were found in the loop. 614 typedef DenseMap<PHINode*, ReductionDescriptor> ReductionList; 615 616 /// InductionList saves induction variables and maps them to the 617 /// induction descriptor. 618 typedef MapVector<PHINode*, InductionInfo> InductionList; 619 620 /// Returns true if it is legal to vectorize this loop. 621 /// This does not mean that it is profitable to vectorize this 622 /// loop, only that it is legal to do so. 623 bool canVectorize(); 624 625 /// Returns the Induction variable. 626 PHINode *getInduction() { return Induction; } 627 628 /// Returns the reduction variables found in the loop. 629 ReductionList *getReductionVars() { return &Reductions; } 630 631 /// Returns the induction variables found in the loop. 632 InductionList *getInductionVars() { return &Inductions; } 633 634 /// Returns the widest induction type. 635 Type *getWidestInductionType() { return WidestIndTy; } 636 637 /// Returns True if V is an induction variable in this loop. 638 bool isInductionVariable(const Value *V); 639 640 /// Return true if the block BB needs to be predicated in order for the loop 641 /// to be vectorized. 642 bool blockNeedsPredication(BasicBlock *BB); 643 644 /// Check if this pointer is consecutive when vectorizing. This happens 645 /// when the last index of the GEP is the induction variable, or that the 646 /// pointer itself is an induction variable. 647 /// This check allows us to vectorize A[idx] into a wide load/store. 648 /// Returns: 649 /// 0 - Stride is unknown or non-consecutive. 650 /// 1 - Address is consecutive. 651 /// -1 - Address is consecutive, and decreasing. 652 int isConsecutivePtr(Value *Ptr); 653 654 /// Returns true if the value V is uniform within the loop. 655 bool isUniform(Value *V); 656 657 /// Returns true if this instruction will remain scalar after vectorization. 658 bool isUniformAfterVectorization(Instruction* I) { return Uniforms.count(I); } 659 660 /// Returns the information that we collected about runtime memory check. 661 RuntimePointerCheck *getRuntimePointerCheck() { return &PtrRtCheck; } 662 663 /// This function returns the identity element (or neutral element) for 664 /// the operation K. 665 static Constant *getReductionIdentity(ReductionKind K, Type *Tp); 666 667 unsigned getMaxSafeDepDistBytes() { return MaxSafeDepDistBytes; } 668 669 bool hasStride(Value *V) { return StrideSet.count(V); } 670 bool mustCheckStrides() { return !StrideSet.empty(); } 671 SmallPtrSet<Value *, 8>::iterator strides_begin() { 672 return StrideSet.begin(); 673 } 674 SmallPtrSet<Value *, 8>::iterator strides_end() { return StrideSet.end(); } 675 676private: 677 /// Check if a single basic block loop is vectorizable. 678 /// At this point we know that this is a loop with a constant trip count 679 /// and we only need to check individual instructions. 680 bool canVectorizeInstrs(); 681 682 /// When we vectorize loops we may change the order in which 683 /// we read and write from memory. This method checks if it is 684 /// legal to vectorize the code, considering only memory constrains. 685 /// Returns true if the loop is vectorizable 686 bool canVectorizeMemory(); 687 688 /// Return true if we can vectorize this loop using the IF-conversion 689 /// transformation. 690 bool canVectorizeWithIfConvert(); 691 692 /// Collect the variables that need to stay uniform after vectorization. 693 void collectLoopUniforms(); 694 695 /// Return true if all of the instructions in the block can be speculatively 696 /// executed. \p SafePtrs is a list of addresses that are known to be legal 697 /// and we know that we can read from them without segfault. 698 bool blockCanBePredicated(BasicBlock *BB, SmallPtrSet<Value *, 8>& SafePtrs); 699 700 /// Returns True, if 'Phi' is the kind of reduction variable for type 701 /// 'Kind'. If this is a reduction variable, it adds it to ReductionList. 702 bool AddReductionVar(PHINode *Phi, ReductionKind Kind); 703 /// Returns a struct describing if the instruction 'I' can be a reduction 704 /// variable of type 'Kind'. If the reduction is a min/max pattern of 705 /// select(icmp()) this function advances the instruction pointer 'I' from the 706 /// compare instruction to the select instruction and stores this pointer in 707 /// 'PatternLastInst' member of the returned struct. 708 ReductionInstDesc isReductionInstr(Instruction *I, ReductionKind Kind, 709 ReductionInstDesc &Desc); 710 /// Returns true if the instruction is a Select(ICmp(X, Y), X, Y) instruction 711 /// pattern corresponding to a min(X, Y) or max(X, Y). 712 static ReductionInstDesc isMinMaxSelectCmpPattern(Instruction *I, 713 ReductionInstDesc &Prev); 714 /// Returns the induction kind of Phi. This function may return NoInduction 715 /// if the PHI is not an induction variable. 716 InductionKind isInductionVariable(PHINode *Phi); 717 718 /// \brief Collect memory access with loop invariant strides. 719 /// 720 /// Looks for accesses like "a[i * StrideA]" where "StrideA" is loop 721 /// invariant. 722 void collectStridedAcccess(Value *LoadOrStoreInst); 723 724 /// The loop that we evaluate. 725 Loop *TheLoop; 726 /// Scev analysis. 727 ScalarEvolution *SE; 728 /// DataLayout analysis. 729 const DataLayout *DL; 730 /// Dominators. 731 DominatorTree *DT; 732 /// Target Library Info. 733 TargetLibraryInfo *TLI; 734 735 // --- vectorization state --- // 736 737 /// Holds the integer induction variable. This is the counter of the 738 /// loop. 739 PHINode *Induction; 740 /// Holds the reduction variables. 741 ReductionList Reductions; 742 /// Holds all of the induction variables that we found in the loop. 743 /// Notice that inductions don't need to start at zero and that induction 744 /// variables can be pointers. 745 InductionList Inductions; 746 /// Holds the widest induction type encountered. 747 Type *WidestIndTy; 748 749 /// Allowed outside users. This holds the reduction 750 /// vars which can be accessed from outside the loop. 751 SmallPtrSet<Value*, 4> AllowedExit; 752 /// This set holds the variables which are known to be uniform after 753 /// vectorization. 754 SmallPtrSet<Instruction*, 4> Uniforms; 755 /// We need to check that all of the pointers in this list are disjoint 756 /// at runtime. 757 RuntimePointerCheck PtrRtCheck; 758 /// Can we assume the absence of NaNs. 759 bool HasFunNoNaNAttr; 760 761 unsigned MaxSafeDepDistBytes; 762 763 ValueToValueMap Strides; 764 SmallPtrSet<Value *, 8> StrideSet; 765}; 766 767/// LoopVectorizationCostModel - estimates the expected speedups due to 768/// vectorization. 769/// In many cases vectorization is not profitable. This can happen because of 770/// a number of reasons. In this class we mainly attempt to predict the 771/// expected speedup/slowdowns due to the supported instruction set. We use the 772/// TargetTransformInfo to query the different backends for the cost of 773/// different operations. 774class LoopVectorizationCostModel { 775public: 776 LoopVectorizationCostModel(Loop *L, ScalarEvolution *SE, LoopInfo *LI, 777 LoopVectorizationLegality *Legal, 778 const TargetTransformInfo &TTI, 779 const DataLayout *DL, const TargetLibraryInfo *TLI) 780 : TheLoop(L), SE(SE), LI(LI), Legal(Legal), TTI(TTI), DL(DL), TLI(TLI) {} 781 782 /// Information about vectorization costs 783 struct VectorizationFactor { 784 unsigned Width; // Vector width with best cost 785 unsigned Cost; // Cost of the loop with that width 786 }; 787 /// \return The most profitable vectorization factor and the cost of that VF. 788 /// This method checks every power of two up to VF. If UserVF is not ZERO 789 /// then this vectorization factor will be selected if vectorization is 790 /// possible. 791 VectorizationFactor selectVectorizationFactor(bool OptForSize, 792 unsigned UserVF); 793 794 /// \return The size (in bits) of the widest type in the code that 795 /// needs to be vectorized. We ignore values that remain scalar such as 796 /// 64 bit loop indices. 797 unsigned getWidestType(); 798 799 /// \return The most profitable unroll factor. 800 /// If UserUF is non-zero then this method finds the best unroll-factor 801 /// based on register pressure and other parameters. 802 /// VF and LoopCost are the selected vectorization factor and the cost of the 803 /// selected VF. 804 unsigned selectUnrollFactor(bool OptForSize, unsigned UserUF, unsigned VF, 805 unsigned LoopCost); 806 807 /// \brief A struct that represents some properties of the register usage 808 /// of a loop. 809 struct RegisterUsage { 810 /// Holds the number of loop invariant values that are used in the loop. 811 unsigned LoopInvariantRegs; 812 /// Holds the maximum number of concurrent live intervals in the loop. 813 unsigned MaxLocalUsers; 814 /// Holds the number of instructions in the loop. 815 unsigned NumInstructions; 816 }; 817 818 /// \return information about the register usage of the loop. 819 RegisterUsage calculateRegisterUsage(); 820 821private: 822 /// Returns the expected execution cost. The unit of the cost does 823 /// not matter because we use the 'cost' units to compare different 824 /// vector widths. The cost that is returned is *not* normalized by 825 /// the factor width. 826 unsigned expectedCost(unsigned VF); 827 828 /// Returns the execution time cost of an instruction for a given vector 829 /// width. Vector width of one means scalar. 830 unsigned getInstructionCost(Instruction *I, unsigned VF); 831 832 /// A helper function for converting Scalar types to vector types. 833 /// If the incoming type is void, we return void. If the VF is 1, we return 834 /// the scalar type. 835 static Type* ToVectorTy(Type *Scalar, unsigned VF); 836 837 /// Returns whether the instruction is a load or store and will be a emitted 838 /// as a vector operation. 839 bool isConsecutiveLoadOrStore(Instruction *I); 840 841 /// The loop that we evaluate. 842 Loop *TheLoop; 843 /// Scev analysis. 844 ScalarEvolution *SE; 845 /// Loop Info analysis. 846 LoopInfo *LI; 847 /// Vectorization legality. 848 LoopVectorizationLegality *Legal; 849 /// Vector target information. 850 const TargetTransformInfo &TTI; 851 /// Target data layout information. 852 const DataLayout *DL; 853 /// Target Library Info. 854 const TargetLibraryInfo *TLI; 855}; 856 857/// Utility class for getting and setting loop vectorizer hints in the form 858/// of loop metadata. 859struct LoopVectorizeHints { 860 /// Vectorization width. 861 unsigned Width; 862 /// Vectorization unroll factor. 863 unsigned Unroll; 864 /// Vectorization forced (-1 not selected, 0 force disabled, 1 force enabled) 865 int Force; 866 867 LoopVectorizeHints(const Loop *L, bool DisableUnrolling) 868 : Width(VectorizationFactor) 869 , Unroll(DisableUnrolling ? 1 : VectorizationUnroll) 870 , Force(-1) 871 , LoopID(L->getLoopID()) { 872 getHints(L); 873 // The command line options override any loop metadata except for when 874 // width == 1 which is used to indicate the loop is already vectorized. 875 if (VectorizationFactor.getNumOccurrences() > 0 && Width != 1) 876 Width = VectorizationFactor; 877 if (VectorizationUnroll.getNumOccurrences() > 0) 878 Unroll = VectorizationUnroll; 879 880 DEBUG(if (DisableUnrolling && Unroll == 1) 881 dbgs() << "LV: Unrolling disabled by the pass manager\n"); 882 } 883 884 /// Return the loop vectorizer metadata prefix. 885 static StringRef Prefix() { return "llvm.vectorizer."; } 886 887 MDNode *createHint(LLVMContext &Context, StringRef Name, unsigned V) { 888 SmallVector<Value*, 2> Vals; 889 Vals.push_back(MDString::get(Context, Name)); 890 Vals.push_back(ConstantInt::get(Type::getInt32Ty(Context), V)); 891 return MDNode::get(Context, Vals); 892 } 893 894 /// Mark the loop L as already vectorized by setting the width to 1. 895 void setAlreadyVectorized(Loop *L) { 896 LLVMContext &Context = L->getHeader()->getContext(); 897 898 Width = 1; 899 900 // Create a new loop id with one more operand for the already_vectorized 901 // hint. If the loop already has a loop id then copy the existing operands. 902 SmallVector<Value*, 4> Vals(1); 903 if (LoopID) 904 for (unsigned i = 1, ie = LoopID->getNumOperands(); i < ie; ++i) 905 Vals.push_back(LoopID->getOperand(i)); 906 907 Vals.push_back(createHint(Context, Twine(Prefix(), "width").str(), Width)); 908 Vals.push_back(createHint(Context, Twine(Prefix(), "unroll").str(), 1)); 909 910 MDNode *NewLoopID = MDNode::get(Context, Vals); 911 // Set operand 0 to refer to the loop id itself. 912 NewLoopID->replaceOperandWith(0, NewLoopID); 913 914 L->setLoopID(NewLoopID); 915 if (LoopID) 916 LoopID->replaceAllUsesWith(NewLoopID); 917 918 LoopID = NewLoopID; 919 } 920 921private: 922 MDNode *LoopID; 923 924 /// Find hints specified in the loop metadata. 925 void getHints(const Loop *L) { 926 if (!LoopID) 927 return; 928 929 // First operand should refer to the loop id itself. 930 assert(LoopID->getNumOperands() > 0 && "requires at least one operand"); 931 assert(LoopID->getOperand(0) == LoopID && "invalid loop id"); 932 933 for (unsigned i = 1, ie = LoopID->getNumOperands(); i < ie; ++i) { 934 const MDString *S = 0; 935 SmallVector<Value*, 4> Args; 936 937 // The expected hint is either a MDString or a MDNode with the first 938 // operand a MDString. 939 if (const MDNode *MD = dyn_cast<MDNode>(LoopID->getOperand(i))) { 940 if (!MD || MD->getNumOperands() == 0) 941 continue; 942 S = dyn_cast<MDString>(MD->getOperand(0)); 943 for (unsigned i = 1, ie = MD->getNumOperands(); i < ie; ++i) 944 Args.push_back(MD->getOperand(i)); 945 } else { 946 S = dyn_cast<MDString>(LoopID->getOperand(i)); 947 assert(Args.size() == 0 && "too many arguments for MDString"); 948 } 949 950 if (!S) 951 continue; 952 953 // Check if the hint starts with the vectorizer prefix. 954 StringRef Hint = S->getString(); 955 if (!Hint.startswith(Prefix())) 956 continue; 957 // Remove the prefix. 958 Hint = Hint.substr(Prefix().size(), StringRef::npos); 959 960 if (Args.size() == 1) 961 getHint(Hint, Args[0]); 962 } 963 } 964 965 // Check string hint with one operand. 966 void getHint(StringRef Hint, Value *Arg) { 967 const ConstantInt *C = dyn_cast<ConstantInt>(Arg); 968 if (!C) return; 969 unsigned Val = C->getZExtValue(); 970 971 if (Hint == "width") { 972 if (isPowerOf2_32(Val) && Val <= MaxVectorWidth) 973 Width = Val; 974 else 975 DEBUG(dbgs() << "LV: ignoring invalid width hint metadata\n"); 976 } else if (Hint == "unroll") { 977 if (isPowerOf2_32(Val) && Val <= MaxUnrollFactor) 978 Unroll = Val; 979 else 980 DEBUG(dbgs() << "LV: ignoring invalid unroll hint metadata\n"); 981 } else if (Hint == "enable") { 982 if (C->getBitWidth() == 1) 983 Force = Val; 984 else 985 DEBUG(dbgs() << "LV: ignoring invalid enable hint metadata\n"); 986 } else { 987 DEBUG(dbgs() << "LV: ignoring unknown hint " << Hint << '\n'); 988 } 989 } 990}; 991 992static void addInnerLoop(Loop &L, SmallVectorImpl<Loop *> &V) { 993 if (L.empty()) 994 return V.push_back(&L); 995 996 for (Loop *InnerL : L) 997 addInnerLoop(*InnerL, V); 998} 999 1000/// The LoopVectorize Pass. 1001struct LoopVectorize : public FunctionPass { 1002 /// Pass identification, replacement for typeid 1003 static char ID; 1004 1005 explicit LoopVectorize(bool NoUnrolling = false, bool AlwaysVectorize = true) 1006 : FunctionPass(ID), 1007 DisableUnrolling(NoUnrolling), 1008 AlwaysVectorize(AlwaysVectorize) { 1009 initializeLoopVectorizePass(*PassRegistry::getPassRegistry()); 1010 } 1011 1012 ScalarEvolution *SE; 1013 const DataLayout *DL; 1014 LoopInfo *LI; 1015 TargetTransformInfo *TTI; 1016 DominatorTree *DT; 1017 BlockFrequencyInfo *BFI; 1018 TargetLibraryInfo *TLI; 1019 bool DisableUnrolling; 1020 bool AlwaysVectorize; 1021 1022 BlockFrequency ColdEntryFreq; 1023 1024 bool runOnFunction(Function &F) override { 1025 SE = &getAnalysis<ScalarEvolution>(); 1026 DataLayoutPass *DLP = getAnalysisIfAvailable<DataLayoutPass>(); 1027 DL = DLP ? &DLP->getDataLayout() : 0; 1028 LI = &getAnalysis<LoopInfo>(); 1029 TTI = &getAnalysis<TargetTransformInfo>(); 1030 DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 1031 BFI = &getAnalysis<BlockFrequencyInfo>(); 1032 TLI = getAnalysisIfAvailable<TargetLibraryInfo>(); 1033 1034 // Compute some weights outside of the loop over the loops. Compute this 1035 // using a BranchProbability to re-use its scaling math. 1036 const BranchProbability ColdProb(1, 5); // 20% 1037 ColdEntryFreq = BlockFrequency(BFI->getEntryFreq()) * ColdProb; 1038 1039 // If the target claims to have no vector registers don't attempt 1040 // vectorization. 1041 if (!TTI->getNumberOfRegisters(true)) 1042 return false; 1043 1044 if (DL == NULL) { 1045 DEBUG(dbgs() << "LV: Not vectorizing: Missing data layout\n"); 1046 return false; 1047 } 1048 1049 // Build up a worklist of inner-loops to vectorize. This is necessary as 1050 // the act of vectorizing or partially unrolling a loop creates new loops 1051 // and can invalidate iterators across the loops. 1052 SmallVector<Loop *, 8> Worklist; 1053 1054 for (Loop *L : *LI) 1055 addInnerLoop(*L, Worklist); 1056 1057 // Now walk the identified inner loops. 1058 bool Changed = false; 1059 while (!Worklist.empty()) 1060 Changed |= processLoop(Worklist.pop_back_val()); 1061 1062 // Process each loop nest in the function. 1063 return Changed; 1064 } 1065 1066 bool processLoop(Loop *L) { 1067 assert(L->empty() && "Only process inner loops."); 1068 DEBUG(dbgs() << "LV: Checking a loop in \"" << 1069 L->getHeader()->getParent()->getName() << "\"\n"); 1070 1071 LoopVectorizeHints Hints(L, DisableUnrolling); 1072 1073 if (Hints.Force == 0) { 1074 DEBUG(dbgs() << "LV: Not vectorizing: #pragma vectorize disable.\n"); 1075 return false; 1076 } 1077 1078 if (!AlwaysVectorize && Hints.Force != 1) { 1079 DEBUG(dbgs() << "LV: Not vectorizing: No #pragma vectorize enable.\n"); 1080 return false; 1081 } 1082 1083 if (Hints.Width == 1 && Hints.Unroll == 1) { 1084 DEBUG(dbgs() << "LV: Not vectorizing: Disabled/already vectorized.\n"); 1085 return false; 1086 } 1087 1088 // Check if it is legal to vectorize the loop. 1089 LoopVectorizationLegality LVL(L, SE, DL, DT, TLI); 1090 if (!LVL.canVectorize()) { 1091 DEBUG(dbgs() << "LV: Not vectorizing: Cannot prove legality.\n"); 1092 return false; 1093 } 1094 1095 // Use the cost model. 1096 LoopVectorizationCostModel CM(L, SE, LI, &LVL, *TTI, DL, TLI); 1097 1098 // Check the function attributes to find out if this function should be 1099 // optimized for size. 1100 Function *F = L->getHeader()->getParent(); 1101 bool OptForSize = 1102 Hints.Force != 1 && F->hasFnAttribute(Attribute::OptimizeForSize); 1103 1104 // Compute the weighted frequency of this loop being executed and see if it 1105 // is less than 20% of the function entry baseline frequency. Note that we 1106 // always have a canonical loop here because we think we *can* vectoriez. 1107 // FIXME: This is hidden behind a flag due to pervasive problems with 1108 // exactly what block frequency models. 1109 if (LoopVectorizeWithBlockFrequency) { 1110 BlockFrequency LoopEntryFreq = BFI->getBlockFreq(L->getLoopPreheader()); 1111 if (Hints.Force != 1 && LoopEntryFreq < ColdEntryFreq) 1112 OptForSize = true; 1113 } 1114 1115 // Check the function attributes to see if implicit floats are allowed.a 1116 // FIXME: This check doesn't seem possibly correct -- what if the loop is 1117 // an integer loop and the vector instructions selected are purely integer 1118 // vector instructions? 1119 if (F->hasFnAttribute(Attribute::NoImplicitFloat)) { 1120 DEBUG(dbgs() << "LV: Can't vectorize when the NoImplicitFloat" 1121 "attribute is used.\n"); 1122 return false; 1123 } 1124 1125 // Select the optimal vectorization factor. 1126 LoopVectorizationCostModel::VectorizationFactor VF; 1127 VF = CM.selectVectorizationFactor(OptForSize, Hints.Width); 1128 // Select the unroll factor. 1129 unsigned UF = CM.selectUnrollFactor(OptForSize, Hints.Unroll, VF.Width, 1130 VF.Cost); 1131 1132 DEBUG(dbgs() << "LV: Found a vectorizable loop ("<< VF.Width << ") in "<< 1133 F->getParent()->getModuleIdentifier() << '\n'); 1134 DEBUG(dbgs() << "LV: Unroll Factor is " << UF << '\n'); 1135 1136 if (VF.Width == 1) { 1137 DEBUG(dbgs() << "LV: Vectorization is possible but not beneficial.\n"); 1138 if (UF == 1) 1139 return false; 1140 DEBUG(dbgs() << "LV: Trying to at least unroll the loops.\n"); 1141 // We decided not to vectorize, but we may want to unroll. 1142 InnerLoopUnroller Unroller(L, SE, LI, DT, DL, TLI, UF); 1143 Unroller.vectorize(&LVL); 1144 } else { 1145 // If we decided that it is *legal* to vectorize the loop then do it. 1146 InnerLoopVectorizer LB(L, SE, LI, DT, DL, TLI, VF.Width, UF); 1147 LB.vectorize(&LVL); 1148 } 1149 1150 // Mark the loop as already vectorized to avoid vectorizing again. 1151 Hints.setAlreadyVectorized(L); 1152 1153 DEBUG(verifyFunction(*L->getHeader()->getParent())); 1154 return true; 1155 } 1156 1157 void getAnalysisUsage(AnalysisUsage &AU) const override { 1158 AU.addRequiredID(LoopSimplifyID); 1159 AU.addRequiredID(LCSSAID); 1160 AU.addRequired<BlockFrequencyInfo>(); 1161 AU.addRequired<DominatorTreeWrapperPass>(); 1162 AU.addRequired<LoopInfo>(); 1163 AU.addRequired<ScalarEvolution>(); 1164 AU.addRequired<TargetTransformInfo>(); 1165 AU.addPreserved<LoopInfo>(); 1166 AU.addPreserved<DominatorTreeWrapperPass>(); 1167 } 1168 1169}; 1170 1171} // end anonymous namespace 1172 1173//===----------------------------------------------------------------------===// 1174// Implementation of LoopVectorizationLegality, InnerLoopVectorizer and 1175// LoopVectorizationCostModel. 1176//===----------------------------------------------------------------------===// 1177 1178static Value *stripIntegerCast(Value *V) { 1179 if (CastInst *CI = dyn_cast<CastInst>(V)) 1180 if (CI->getOperand(0)->getType()->isIntegerTy()) 1181 return CI->getOperand(0); 1182 return V; 1183} 1184 1185///\brief Replaces the symbolic stride in a pointer SCEV expression by one. 1186/// 1187/// If \p OrigPtr is not null, use it to look up the stride value instead of 1188/// \p Ptr. 1189static const SCEV *replaceSymbolicStrideSCEV(ScalarEvolution *SE, 1190 ValueToValueMap &PtrToStride, 1191 Value *Ptr, Value *OrigPtr = 0) { 1192 1193 const SCEV *OrigSCEV = SE->getSCEV(Ptr); 1194 1195 // If there is an entry in the map return the SCEV of the pointer with the 1196 // symbolic stride replaced by one. 1197 ValueToValueMap::iterator SI = PtrToStride.find(OrigPtr ? OrigPtr : Ptr); 1198 if (SI != PtrToStride.end()) { 1199 Value *StrideVal = SI->second; 1200 1201 // Strip casts. 1202 StrideVal = stripIntegerCast(StrideVal); 1203 1204 // Replace symbolic stride by one. 1205 Value *One = ConstantInt::get(StrideVal->getType(), 1); 1206 ValueToValueMap RewriteMap; 1207 RewriteMap[StrideVal] = One; 1208 1209 const SCEV *ByOne = 1210 SCEVParameterRewriter::rewrite(OrigSCEV, *SE, RewriteMap, true); 1211 DEBUG(dbgs() << "LV: Replacing SCEV: " << *OrigSCEV << " by: " << *ByOne 1212 << "\n"); 1213 return ByOne; 1214 } 1215 1216 // Otherwise, just return the SCEV of the original pointer. 1217 return SE->getSCEV(Ptr); 1218} 1219 1220void LoopVectorizationLegality::RuntimePointerCheck::insert( 1221 ScalarEvolution *SE, Loop *Lp, Value *Ptr, bool WritePtr, unsigned DepSetId, 1222 ValueToValueMap &Strides) { 1223 // Get the stride replaced scev. 1224 const SCEV *Sc = replaceSymbolicStrideSCEV(SE, Strides, Ptr); 1225 const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Sc); 1226 assert(AR && "Invalid addrec expression"); 1227 const SCEV *Ex = SE->getBackedgeTakenCount(Lp); 1228 const SCEV *ScEnd = AR->evaluateAtIteration(Ex, *SE); 1229 Pointers.push_back(Ptr); 1230 Starts.push_back(AR->getStart()); 1231 Ends.push_back(ScEnd); 1232 IsWritePtr.push_back(WritePtr); 1233 DependencySetId.push_back(DepSetId); 1234} 1235 1236Value *InnerLoopVectorizer::getBroadcastInstrs(Value *V) { 1237 // We need to place the broadcast of invariant variables outside the loop. 1238 Instruction *Instr = dyn_cast<Instruction>(V); 1239 bool NewInstr = 1240 (Instr && std::find(LoopVectorBody.begin(), LoopVectorBody.end(), 1241 Instr->getParent()) != LoopVectorBody.end()); 1242 bool Invariant = OrigLoop->isLoopInvariant(V) && !NewInstr; 1243 1244 // Place the code for broadcasting invariant variables in the new preheader. 1245 IRBuilder<>::InsertPointGuard Guard(Builder); 1246 if (Invariant) 1247 Builder.SetInsertPoint(LoopVectorPreHeader->getTerminator()); 1248 1249 // Broadcast the scalar into all locations in the vector. 1250 Value *Shuf = Builder.CreateVectorSplat(VF, V, "broadcast"); 1251 1252 return Shuf; 1253} 1254 1255Value *InnerLoopVectorizer::getConsecutiveVector(Value* Val, int StartIdx, 1256 bool Negate) { 1257 assert(Val->getType()->isVectorTy() && "Must be a vector"); 1258 assert(Val->getType()->getScalarType()->isIntegerTy() && 1259 "Elem must be an integer"); 1260 // Create the types. 1261 Type *ITy = Val->getType()->getScalarType(); 1262 VectorType *Ty = cast<VectorType>(Val->getType()); 1263 int VLen = Ty->getNumElements(); 1264 SmallVector<Constant*, 8> Indices; 1265 1266 // Create a vector of consecutive numbers from zero to VF. 1267 for (int i = 0; i < VLen; ++i) { 1268 int64_t Idx = Negate ? (-i) : i; 1269 Indices.push_back(ConstantInt::get(ITy, StartIdx + Idx, Negate)); 1270 } 1271 1272 // Add the consecutive indices to the vector value. 1273 Constant *Cv = ConstantVector::get(Indices); 1274 assert(Cv->getType() == Val->getType() && "Invalid consecutive vec"); 1275 return Builder.CreateAdd(Val, Cv, "induction"); 1276} 1277 1278/// \brief Find the operand of the GEP that should be checked for consecutive 1279/// stores. This ignores trailing indices that have no effect on the final 1280/// pointer. 1281static unsigned getGEPInductionOperand(const DataLayout *DL, 1282 const GetElementPtrInst *Gep) { 1283 unsigned LastOperand = Gep->getNumOperands() - 1; 1284 unsigned GEPAllocSize = DL->getTypeAllocSize( 1285 cast<PointerType>(Gep->getType()->getScalarType())->getElementType()); 1286 1287 // Walk backwards and try to peel off zeros. 1288 while (LastOperand > 1 && match(Gep->getOperand(LastOperand), m_Zero())) { 1289 // Find the type we're currently indexing into. 1290 gep_type_iterator GEPTI = gep_type_begin(Gep); 1291 std::advance(GEPTI, LastOperand - 1); 1292 1293 // If it's a type with the same allocation size as the result of the GEP we 1294 // can peel off the zero index. 1295 if (DL->getTypeAllocSize(*GEPTI) != GEPAllocSize) 1296 break; 1297 --LastOperand; 1298 } 1299 1300 return LastOperand; 1301} 1302 1303int LoopVectorizationLegality::isConsecutivePtr(Value *Ptr) { 1304 assert(Ptr->getType()->isPointerTy() && "Unexpected non-ptr"); 1305 // Make sure that the pointer does not point to structs. 1306 if (Ptr->getType()->getPointerElementType()->isAggregateType()) 1307 return 0; 1308 1309 // If this value is a pointer induction variable we know it is consecutive. 1310 PHINode *Phi = dyn_cast_or_null<PHINode>(Ptr); 1311 if (Phi && Inductions.count(Phi)) { 1312 InductionInfo II = Inductions[Phi]; 1313 if (IK_PtrInduction == II.IK) 1314 return 1; 1315 else if (IK_ReversePtrInduction == II.IK) 1316 return -1; 1317 } 1318 1319 GetElementPtrInst *Gep = dyn_cast_or_null<GetElementPtrInst>(Ptr); 1320 if (!Gep) 1321 return 0; 1322 1323 unsigned NumOperands = Gep->getNumOperands(); 1324 Value *GpPtr = Gep->getPointerOperand(); 1325 // If this GEP value is a consecutive pointer induction variable and all of 1326 // the indices are constant then we know it is consecutive. We can 1327 Phi = dyn_cast<PHINode>(GpPtr); 1328 if (Phi && Inductions.count(Phi)) { 1329 1330 // Make sure that the pointer does not point to structs. 1331 PointerType *GepPtrType = cast<PointerType>(GpPtr->getType()); 1332 if (GepPtrType->getElementType()->isAggregateType()) 1333 return 0; 1334 1335 // Make sure that all of the index operands are loop invariant. 1336 for (unsigned i = 1; i < NumOperands; ++i) 1337 if (!SE->isLoopInvariant(SE->getSCEV(Gep->getOperand(i)), TheLoop)) 1338 return 0; 1339 1340 InductionInfo II = Inductions[Phi]; 1341 if (IK_PtrInduction == II.IK) 1342 return 1; 1343 else if (IK_ReversePtrInduction == II.IK) 1344 return -1; 1345 } 1346 1347 unsigned InductionOperand = getGEPInductionOperand(DL, Gep); 1348 1349 // Check that all of the gep indices are uniform except for our induction 1350 // operand. 1351 for (unsigned i = 0; i != NumOperands; ++i) 1352 if (i != InductionOperand && 1353 !SE->isLoopInvariant(SE->getSCEV(Gep->getOperand(i)), TheLoop)) 1354 return 0; 1355 1356 // We can emit wide load/stores only if the last non-zero index is the 1357 // induction variable. 1358 const SCEV *Last = 0; 1359 if (!Strides.count(Gep)) 1360 Last = SE->getSCEV(Gep->getOperand(InductionOperand)); 1361 else { 1362 // Because of the multiplication by a stride we can have a s/zext cast. 1363 // We are going to replace this stride by 1 so the cast is safe to ignore. 1364 // 1365 // %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ] 1366 // %0 = trunc i64 %indvars.iv to i32 1367 // %mul = mul i32 %0, %Stride1 1368 // %idxprom = zext i32 %mul to i64 << Safe cast. 1369 // %arrayidx = getelementptr inbounds i32* %B, i64 %idxprom 1370 // 1371 Last = replaceSymbolicStrideSCEV(SE, Strides, 1372 Gep->getOperand(InductionOperand), Gep); 1373 if (const SCEVCastExpr *C = dyn_cast<SCEVCastExpr>(Last)) 1374 Last = 1375 (C->getSCEVType() == scSignExtend || C->getSCEVType() == scZeroExtend) 1376 ? C->getOperand() 1377 : Last; 1378 } 1379 if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Last)) { 1380 const SCEV *Step = AR->getStepRecurrence(*SE); 1381 1382 // The memory is consecutive because the last index is consecutive 1383 // and all other indices are loop invariant. 1384 if (Step->isOne()) 1385 return 1; 1386 if (Step->isAllOnesValue()) 1387 return -1; 1388 } 1389 1390 return 0; 1391} 1392 1393bool LoopVectorizationLegality::isUniform(Value *V) { 1394 return (SE->isLoopInvariant(SE->getSCEV(V), TheLoop)); 1395} 1396 1397InnerLoopVectorizer::VectorParts& 1398InnerLoopVectorizer::getVectorValue(Value *V) { 1399 assert(V != Induction && "The new induction variable should not be used."); 1400 assert(!V->getType()->isVectorTy() && "Can't widen a vector"); 1401 1402 // If we have a stride that is replaced by one, do it here. 1403 if (Legal->hasStride(V)) 1404 V = ConstantInt::get(V->getType(), 1); 1405 1406 // If we have this scalar in the map, return it. 1407 if (WidenMap.has(V)) 1408 return WidenMap.get(V); 1409 1410 // If this scalar is unknown, assume that it is a constant or that it is 1411 // loop invariant. Broadcast V and save the value for future uses. 1412 Value *B = getBroadcastInstrs(V); 1413 return WidenMap.splat(V, B); 1414} 1415 1416Value *InnerLoopVectorizer::reverseVector(Value *Vec) { 1417 assert(Vec->getType()->isVectorTy() && "Invalid type"); 1418 SmallVector<Constant*, 8> ShuffleMask; 1419 for (unsigned i = 0; i < VF; ++i) 1420 ShuffleMask.push_back(Builder.getInt32(VF - i - 1)); 1421 1422 return Builder.CreateShuffleVector(Vec, UndefValue::get(Vec->getType()), 1423 ConstantVector::get(ShuffleMask), 1424 "reverse"); 1425} 1426 1427void InnerLoopVectorizer::vectorizeMemoryInstruction(Instruction *Instr) { 1428 // Attempt to issue a wide load. 1429 LoadInst *LI = dyn_cast<LoadInst>(Instr); 1430 StoreInst *SI = dyn_cast<StoreInst>(Instr); 1431 1432 assert((LI || SI) && "Invalid Load/Store instruction"); 1433 1434 Type *ScalarDataTy = LI ? LI->getType() : SI->getValueOperand()->getType(); 1435 Type *DataTy = VectorType::get(ScalarDataTy, VF); 1436 Value *Ptr = LI ? LI->getPointerOperand() : SI->getPointerOperand(); 1437 unsigned Alignment = LI ? LI->getAlignment() : SI->getAlignment(); 1438 // An alignment of 0 means target abi alignment. We need to use the scalar's 1439 // target abi alignment in such a case. 1440 if (!Alignment) 1441 Alignment = DL->getABITypeAlignment(ScalarDataTy); 1442 unsigned AddressSpace = Ptr->getType()->getPointerAddressSpace(); 1443 unsigned ScalarAllocatedSize = DL->getTypeAllocSize(ScalarDataTy); 1444 unsigned VectorElementSize = DL->getTypeStoreSize(DataTy)/VF; 1445 1446 if (SI && Legal->blockNeedsPredication(SI->getParent())) 1447 return scalarizeInstruction(Instr, true); 1448 1449 if (ScalarAllocatedSize != VectorElementSize) 1450 return scalarizeInstruction(Instr); 1451 1452 // If the pointer is loop invariant or if it is non-consecutive, 1453 // scalarize the load. 1454 int ConsecutiveStride = Legal->isConsecutivePtr(Ptr); 1455 bool Reverse = ConsecutiveStride < 0; 1456 bool UniformLoad = LI && Legal->isUniform(Ptr); 1457 if (!ConsecutiveStride || UniformLoad) 1458 return scalarizeInstruction(Instr); 1459 1460 Constant *Zero = Builder.getInt32(0); 1461 VectorParts &Entry = WidenMap.get(Instr); 1462 1463 // Handle consecutive loads/stores. 1464 GetElementPtrInst *Gep = dyn_cast<GetElementPtrInst>(Ptr); 1465 if (Gep && Legal->isInductionVariable(Gep->getPointerOperand())) { 1466 setDebugLocFromInst(Builder, Gep); 1467 Value *PtrOperand = Gep->getPointerOperand(); 1468 Value *FirstBasePtr = getVectorValue(PtrOperand)[0]; 1469 FirstBasePtr = Builder.CreateExtractElement(FirstBasePtr, Zero); 1470 1471 // Create the new GEP with the new induction variable. 1472 GetElementPtrInst *Gep2 = cast<GetElementPtrInst>(Gep->clone()); 1473 Gep2->setOperand(0, FirstBasePtr); 1474 Gep2->setName("gep.indvar.base"); 1475 Ptr = Builder.Insert(Gep2); 1476 } else if (Gep) { 1477 setDebugLocFromInst(Builder, Gep); 1478 assert(SE->isLoopInvariant(SE->getSCEV(Gep->getPointerOperand()), 1479 OrigLoop) && "Base ptr must be invariant"); 1480 1481 // The last index does not have to be the induction. It can be 1482 // consecutive and be a function of the index. For example A[I+1]; 1483 unsigned NumOperands = Gep->getNumOperands(); 1484 unsigned InductionOperand = getGEPInductionOperand(DL, Gep); 1485 // Create the new GEP with the new induction variable. 1486 GetElementPtrInst *Gep2 = cast<GetElementPtrInst>(Gep->clone()); 1487 1488 for (unsigned i = 0; i < NumOperands; ++i) { 1489 Value *GepOperand = Gep->getOperand(i); 1490 Instruction *GepOperandInst = dyn_cast<Instruction>(GepOperand); 1491 1492 // Update last index or loop invariant instruction anchored in loop. 1493 if (i == InductionOperand || 1494 (GepOperandInst && OrigLoop->contains(GepOperandInst))) { 1495 assert((i == InductionOperand || 1496 SE->isLoopInvariant(SE->getSCEV(GepOperandInst), OrigLoop)) && 1497 "Must be last index or loop invariant"); 1498 1499 VectorParts &GEPParts = getVectorValue(GepOperand); 1500 Value *Index = GEPParts[0]; 1501 Index = Builder.CreateExtractElement(Index, Zero); 1502 Gep2->setOperand(i, Index); 1503 Gep2->setName("gep.indvar.idx"); 1504 } 1505 } 1506 Ptr = Builder.Insert(Gep2); 1507 } else { 1508 // Use the induction element ptr. 1509 assert(isa<PHINode>(Ptr) && "Invalid induction ptr"); 1510 setDebugLocFromInst(Builder, Ptr); 1511 VectorParts &PtrVal = getVectorValue(Ptr); 1512 Ptr = Builder.CreateExtractElement(PtrVal[0], Zero); 1513 } 1514 1515 // Handle Stores: 1516 if (SI) { 1517 assert(!Legal->isUniform(SI->getPointerOperand()) && 1518 "We do not allow storing to uniform addresses"); 1519 setDebugLocFromInst(Builder, SI); 1520 // We don't want to update the value in the map as it might be used in 1521 // another expression. So don't use a reference type for "StoredVal". 1522 VectorParts StoredVal = getVectorValue(SI->getValueOperand()); 1523 1524 for (unsigned Part = 0; Part < UF; ++Part) { 1525 // Calculate the pointer for the specific unroll-part. 1526 Value *PartPtr = Builder.CreateGEP(Ptr, Builder.getInt32(Part * VF)); 1527 1528 if (Reverse) { 1529 // If we store to reverse consecutive memory locations then we need 1530 // to reverse the order of elements in the stored value. 1531 StoredVal[Part] = reverseVector(StoredVal[Part]); 1532 // If the address is consecutive but reversed, then the 1533 // wide store needs to start at the last vector element. 1534 PartPtr = Builder.CreateGEP(Ptr, Builder.getInt32(-Part * VF)); 1535 PartPtr = Builder.CreateGEP(PartPtr, Builder.getInt32(1 - VF)); 1536 } 1537 1538 Value *VecPtr = Builder.CreateBitCast(PartPtr, 1539 DataTy->getPointerTo(AddressSpace)); 1540 Builder.CreateStore(StoredVal[Part], VecPtr)->setAlignment(Alignment); 1541 } 1542 return; 1543 } 1544 1545 // Handle loads. 1546 assert(LI && "Must have a load instruction"); 1547 setDebugLocFromInst(Builder, LI); 1548 for (unsigned Part = 0; Part < UF; ++Part) { 1549 // Calculate the pointer for the specific unroll-part. 1550 Value *PartPtr = Builder.CreateGEP(Ptr, Builder.getInt32(Part * VF)); 1551 1552 if (Reverse) { 1553 // If the address is consecutive but reversed, then the 1554 // wide store needs to start at the last vector element. 1555 PartPtr = Builder.CreateGEP(Ptr, Builder.getInt32(-Part * VF)); 1556 PartPtr = Builder.CreateGEP(PartPtr, Builder.getInt32(1 - VF)); 1557 } 1558 1559 Value *VecPtr = Builder.CreateBitCast(PartPtr, 1560 DataTy->getPointerTo(AddressSpace)); 1561 Value *LI = Builder.CreateLoad(VecPtr, "wide.load"); 1562 cast<LoadInst>(LI)->setAlignment(Alignment); 1563 Entry[Part] = Reverse ? reverseVector(LI) : LI; 1564 } 1565} 1566 1567void InnerLoopVectorizer::scalarizeInstruction(Instruction *Instr, bool IfPredicateStore) { 1568 assert(!Instr->getType()->isAggregateType() && "Can't handle vectors"); 1569 // Holds vector parameters or scalars, in case of uniform vals. 1570 SmallVector<VectorParts, 4> Params; 1571 1572 setDebugLocFromInst(Builder, Instr); 1573 1574 // Find all of the vectorized parameters. 1575 for (unsigned op = 0, e = Instr->getNumOperands(); op != e; ++op) { 1576 Value *SrcOp = Instr->getOperand(op); 1577 1578 // If we are accessing the old induction variable, use the new one. 1579 if (SrcOp == OldInduction) { 1580 Params.push_back(getVectorValue(SrcOp)); 1581 continue; 1582 } 1583 1584 // Try using previously calculated values. 1585 Instruction *SrcInst = dyn_cast<Instruction>(SrcOp); 1586 1587 // If the src is an instruction that appeared earlier in the basic block 1588 // then it should already be vectorized. 1589 if (SrcInst && OrigLoop->contains(SrcInst)) { 1590 assert(WidenMap.has(SrcInst) && "Source operand is unavailable"); 1591 // The parameter is a vector value from earlier. 1592 Params.push_back(WidenMap.get(SrcInst)); 1593 } else { 1594 // The parameter is a scalar from outside the loop. Maybe even a constant. 1595 VectorParts Scalars; 1596 Scalars.append(UF, SrcOp); 1597 Params.push_back(Scalars); 1598 } 1599 } 1600 1601 assert(Params.size() == Instr->getNumOperands() && 1602 "Invalid number of operands"); 1603 1604 // Does this instruction return a value ? 1605 bool IsVoidRetTy = Instr->getType()->isVoidTy(); 1606 1607 Value *UndefVec = IsVoidRetTy ? 0 : 1608 UndefValue::get(VectorType::get(Instr->getType(), VF)); 1609 // Create a new entry in the WidenMap and initialize it to Undef or Null. 1610 VectorParts &VecResults = WidenMap.splat(Instr, UndefVec); 1611 1612 Instruction *InsertPt = Builder.GetInsertPoint(); 1613 BasicBlock *IfBlock = Builder.GetInsertBlock(); 1614 BasicBlock *CondBlock = 0; 1615 1616 VectorParts Cond; 1617 Loop *VectorLp = 0; 1618 if (IfPredicateStore) { 1619 assert(Instr->getParent()->getSinglePredecessor() && 1620 "Only support single predecessor blocks"); 1621 Cond = createEdgeMask(Instr->getParent()->getSinglePredecessor(), 1622 Instr->getParent()); 1623 VectorLp = LI->getLoopFor(IfBlock); 1624 assert(VectorLp && "Must have a loop for this block"); 1625 } 1626 1627 // For each vector unroll 'part': 1628 for (unsigned Part = 0; Part < UF; ++Part) { 1629 // For each scalar that we create: 1630 for (unsigned Width = 0; Width < VF; ++Width) { 1631 1632 // Start if-block. 1633 Value *Cmp = 0; 1634 if (IfPredicateStore) { 1635 Cmp = Builder.CreateExtractElement(Cond[Part], Builder.getInt32(Width)); 1636 Cmp = Builder.CreateICmp(ICmpInst::ICMP_EQ, Cmp, ConstantInt::get(Cmp->getType(), 1)); 1637 CondBlock = IfBlock->splitBasicBlock(InsertPt, "cond.store"); 1638 LoopVectorBody.push_back(CondBlock); 1639 VectorLp->addBasicBlockToLoop(CondBlock, LI->getBase()); 1640 // Update Builder with newly created basic block. 1641 Builder.SetInsertPoint(InsertPt); 1642 } 1643 1644 Instruction *Cloned = Instr->clone(); 1645 if (!IsVoidRetTy) 1646 Cloned->setName(Instr->getName() + ".cloned"); 1647 // Replace the operands of the cloned instructions with extracted scalars. 1648 for (unsigned op = 0, e = Instr->getNumOperands(); op != e; ++op) { 1649 Value *Op = Params[op][Part]; 1650 // Param is a vector. Need to extract the right lane. 1651 if (Op->getType()->isVectorTy()) 1652 Op = Builder.CreateExtractElement(Op, Builder.getInt32(Width)); 1653 Cloned->setOperand(op, Op); 1654 } 1655 1656 // Place the cloned scalar in the new loop. 1657 Builder.Insert(Cloned); 1658 1659 // If the original scalar returns a value we need to place it in a vector 1660 // so that future users will be able to use it. 1661 if (!IsVoidRetTy) 1662 VecResults[Part] = Builder.CreateInsertElement(VecResults[Part], Cloned, 1663 Builder.getInt32(Width)); 1664 // End if-block. 1665 if (IfPredicateStore) { 1666 BasicBlock *NewIfBlock = CondBlock->splitBasicBlock(InsertPt, "else"); 1667 LoopVectorBody.push_back(NewIfBlock); 1668 VectorLp->addBasicBlockToLoop(NewIfBlock, LI->getBase()); 1669 Builder.SetInsertPoint(InsertPt); 1670 Instruction *OldBr = IfBlock->getTerminator(); 1671 BranchInst::Create(CondBlock, NewIfBlock, Cmp, OldBr); 1672 OldBr->eraseFromParent(); 1673 IfBlock = NewIfBlock; 1674 } 1675 } 1676 } 1677} 1678 1679static Instruction *getFirstInst(Instruction *FirstInst, Value *V, 1680 Instruction *Loc) { 1681 if (FirstInst) 1682 return FirstInst; 1683 if (Instruction *I = dyn_cast<Instruction>(V)) 1684 return I->getParent() == Loc->getParent() ? I : 0; 1685 return 0; 1686} 1687 1688std::pair<Instruction *, Instruction *> 1689InnerLoopVectorizer::addStrideCheck(Instruction *Loc) { 1690 Instruction *tnullptr = 0; 1691 if (!Legal->mustCheckStrides()) 1692 return std::pair<Instruction *, Instruction *>(tnullptr, tnullptr); 1693 1694 IRBuilder<> ChkBuilder(Loc); 1695 1696 // Emit checks. 1697 Value *Check = 0; 1698 Instruction *FirstInst = 0; 1699 for (SmallPtrSet<Value *, 8>::iterator SI = Legal->strides_begin(), 1700 SE = Legal->strides_end(); 1701 SI != SE; ++SI) { 1702 Value *Ptr = stripIntegerCast(*SI); 1703 Value *C = ChkBuilder.CreateICmpNE(Ptr, ConstantInt::get(Ptr->getType(), 1), 1704 "stride.chk"); 1705 // Store the first instruction we create. 1706 FirstInst = getFirstInst(FirstInst, C, Loc); 1707 if (Check) 1708 Check = ChkBuilder.CreateOr(Check, C); 1709 else 1710 Check = C; 1711 } 1712 1713 // We have to do this trickery because the IRBuilder might fold the check to a 1714 // constant expression in which case there is no Instruction anchored in a 1715 // the block. 1716 LLVMContext &Ctx = Loc->getContext(); 1717 Instruction *TheCheck = 1718 BinaryOperator::CreateAnd(Check, ConstantInt::getTrue(Ctx)); 1719 ChkBuilder.Insert(TheCheck, "stride.not.one"); 1720 FirstInst = getFirstInst(FirstInst, TheCheck, Loc); 1721 1722 return std::make_pair(FirstInst, TheCheck); 1723} 1724 1725std::pair<Instruction *, Instruction *> 1726InnerLoopVectorizer::addRuntimeCheck(Instruction *Loc) { 1727 LoopVectorizationLegality::RuntimePointerCheck *PtrRtCheck = 1728 Legal->getRuntimePointerCheck(); 1729 1730 Instruction *tnullptr = 0; 1731 if (!PtrRtCheck->Need) 1732 return std::pair<Instruction *, Instruction *>(tnullptr, tnullptr); 1733 1734 unsigned NumPointers = PtrRtCheck->Pointers.size(); 1735 SmallVector<TrackingVH<Value> , 2> Starts; 1736 SmallVector<TrackingVH<Value> , 2> Ends; 1737 1738 LLVMContext &Ctx = Loc->getContext(); 1739 SCEVExpander Exp(*SE, "induction"); 1740 Instruction *FirstInst = 0; 1741 1742 for (unsigned i = 0; i < NumPointers; ++i) { 1743 Value *Ptr = PtrRtCheck->Pointers[i]; 1744 const SCEV *Sc = SE->getSCEV(Ptr); 1745 1746 if (SE->isLoopInvariant(Sc, OrigLoop)) { 1747 DEBUG(dbgs() << "LV: Adding RT check for a loop invariant ptr:" << 1748 *Ptr <<"\n"); 1749 Starts.push_back(Ptr); 1750 Ends.push_back(Ptr); 1751 } else { 1752 DEBUG(dbgs() << "LV: Adding RT check for range:" << *Ptr << '\n'); 1753 unsigned AS = Ptr->getType()->getPointerAddressSpace(); 1754 1755 // Use this type for pointer arithmetic. 1756 Type *PtrArithTy = Type::getInt8PtrTy(Ctx, AS); 1757 1758 Value *Start = Exp.expandCodeFor(PtrRtCheck->Starts[i], PtrArithTy, Loc); 1759 Value *End = Exp.expandCodeFor(PtrRtCheck->Ends[i], PtrArithTy, Loc); 1760 Starts.push_back(Start); 1761 Ends.push_back(End); 1762 } 1763 } 1764 1765 IRBuilder<> ChkBuilder(Loc); 1766 // Our instructions might fold to a constant. 1767 Value *MemoryRuntimeCheck = 0; 1768 for (unsigned i = 0; i < NumPointers; ++i) { 1769 for (unsigned j = i+1; j < NumPointers; ++j) { 1770 // No need to check if two readonly pointers intersect. 1771 if (!PtrRtCheck->IsWritePtr[i] && !PtrRtCheck->IsWritePtr[j]) 1772 continue; 1773 1774 // Only need to check pointers between two different dependency sets. 1775 if (PtrRtCheck->DependencySetId[i] == PtrRtCheck->DependencySetId[j]) 1776 continue; 1777 1778 unsigned AS0 = Starts[i]->getType()->getPointerAddressSpace(); 1779 unsigned AS1 = Starts[j]->getType()->getPointerAddressSpace(); 1780 1781 assert((AS0 == Ends[j]->getType()->getPointerAddressSpace()) && 1782 (AS1 == Ends[i]->getType()->getPointerAddressSpace()) && 1783 "Trying to bounds check pointers with different address spaces"); 1784 1785 Type *PtrArithTy0 = Type::getInt8PtrTy(Ctx, AS0); 1786 Type *PtrArithTy1 = Type::getInt8PtrTy(Ctx, AS1); 1787 1788 Value *Start0 = ChkBuilder.CreateBitCast(Starts[i], PtrArithTy0, "bc"); 1789 Value *Start1 = ChkBuilder.CreateBitCast(Starts[j], PtrArithTy1, "bc"); 1790 Value *End0 = ChkBuilder.CreateBitCast(Ends[i], PtrArithTy1, "bc"); 1791 Value *End1 = ChkBuilder.CreateBitCast(Ends[j], PtrArithTy0, "bc"); 1792 1793 Value *Cmp0 = ChkBuilder.CreateICmpULE(Start0, End1, "bound0"); 1794 FirstInst = getFirstInst(FirstInst, Cmp0, Loc); 1795 Value *Cmp1 = ChkBuilder.CreateICmpULE(Start1, End0, "bound1"); 1796 FirstInst = getFirstInst(FirstInst, Cmp1, Loc); 1797 Value *IsConflict = ChkBuilder.CreateAnd(Cmp0, Cmp1, "found.conflict"); 1798 FirstInst = getFirstInst(FirstInst, IsConflict, Loc); 1799 if (MemoryRuntimeCheck) { 1800 IsConflict = ChkBuilder.CreateOr(MemoryRuntimeCheck, IsConflict, 1801 "conflict.rdx"); 1802 FirstInst = getFirstInst(FirstInst, IsConflict, Loc); 1803 } 1804 MemoryRuntimeCheck = IsConflict; 1805 } 1806 } 1807 1808 // We have to do this trickery because the IRBuilder might fold the check to a 1809 // constant expression in which case there is no Instruction anchored in a 1810 // the block. 1811 Instruction *Check = BinaryOperator::CreateAnd(MemoryRuntimeCheck, 1812 ConstantInt::getTrue(Ctx)); 1813 ChkBuilder.Insert(Check, "memcheck.conflict"); 1814 FirstInst = getFirstInst(FirstInst, Check, Loc); 1815 return std::make_pair(FirstInst, Check); 1816} 1817 1818void InnerLoopVectorizer::createEmptyLoop() { 1819 /* 1820 In this function we generate a new loop. The new loop will contain 1821 the vectorized instructions while the old loop will continue to run the 1822 scalar remainder. 1823 1824 [ ] <-- vector loop bypass (may consist of multiple blocks). 1825 / | 1826 / v 1827 | [ ] <-- vector pre header. 1828 | | 1829 | v 1830 | [ ] \ 1831 | [ ]_| <-- vector loop. 1832 | | 1833 \ v 1834 >[ ] <--- middle-block. 1835 / | 1836 / v 1837 | [ ] <--- new preheader. 1838 | | 1839 | v 1840 | [ ] \ 1841 | [ ]_| <-- old scalar loop to handle remainder. 1842 \ | 1843 \ v 1844 >[ ] <-- exit block. 1845 ... 1846 */ 1847 1848 BasicBlock *OldBasicBlock = OrigLoop->getHeader(); 1849 BasicBlock *BypassBlock = OrigLoop->getLoopPreheader(); 1850 BasicBlock *ExitBlock = OrigLoop->getExitBlock(); 1851 assert(ExitBlock && "Must have an exit block"); 1852 1853 // Some loops have a single integer induction variable, while other loops 1854 // don't. One example is c++ iterators that often have multiple pointer 1855 // induction variables. In the code below we also support a case where we 1856 // don't have a single induction variable. 1857 OldInduction = Legal->getInduction(); 1858 Type *IdxTy = Legal->getWidestInductionType(); 1859 1860 // Find the loop boundaries. 1861 const SCEV *ExitCount = SE->getBackedgeTakenCount(OrigLoop); 1862 assert(ExitCount != SE->getCouldNotCompute() && "Invalid loop count"); 1863 1864 // The exit count might have the type of i64 while the phi is i32. This can 1865 // happen if we have an induction variable that is sign extended before the 1866 // compare. The only way that we get a backedge taken count is that the 1867 // induction variable was signed and as such will not overflow. In such a case 1868 // truncation is legal. 1869 if (ExitCount->getType()->getPrimitiveSizeInBits() > 1870 IdxTy->getPrimitiveSizeInBits()) 1871 ExitCount = SE->getTruncateOrNoop(ExitCount, IdxTy); 1872 1873 ExitCount = SE->getNoopOrZeroExtend(ExitCount, IdxTy); 1874 // Get the total trip count from the count by adding 1. 1875 ExitCount = SE->getAddExpr(ExitCount, 1876 SE->getConstant(ExitCount->getType(), 1)); 1877 1878 // Expand the trip count and place the new instructions in the preheader. 1879 // Notice that the pre-header does not change, only the loop body. 1880 SCEVExpander Exp(*SE, "induction"); 1881 1882 // Count holds the overall loop count (N). 1883 Value *Count = Exp.expandCodeFor(ExitCount, ExitCount->getType(), 1884 BypassBlock->getTerminator()); 1885 1886 // The loop index does not have to start at Zero. Find the original start 1887 // value from the induction PHI node. If we don't have an induction variable 1888 // then we know that it starts at zero. 1889 Builder.SetInsertPoint(BypassBlock->getTerminator()); 1890 Value *StartIdx = ExtendedIdx = OldInduction ? 1891 Builder.CreateZExt(OldInduction->getIncomingValueForBlock(BypassBlock), 1892 IdxTy): 1893 ConstantInt::get(IdxTy, 0); 1894 1895 assert(BypassBlock && "Invalid loop structure"); 1896 LoopBypassBlocks.push_back(BypassBlock); 1897 1898 // Split the single block loop into the two loop structure described above. 1899 BasicBlock *VectorPH = 1900 BypassBlock->splitBasicBlock(BypassBlock->getTerminator(), "vector.ph"); 1901 BasicBlock *VecBody = 1902 VectorPH->splitBasicBlock(VectorPH->getTerminator(), "vector.body"); 1903 BasicBlock *MiddleBlock = 1904 VecBody->splitBasicBlock(VecBody->getTerminator(), "middle.block"); 1905 BasicBlock *ScalarPH = 1906 MiddleBlock->splitBasicBlock(MiddleBlock->getTerminator(), "scalar.ph"); 1907 1908 // Create and register the new vector loop. 1909 Loop* Lp = new Loop(); 1910 Loop *ParentLoop = OrigLoop->getParentLoop(); 1911 1912 // Insert the new loop into the loop nest and register the new basic blocks 1913 // before calling any utilities such as SCEV that require valid LoopInfo. 1914 if (ParentLoop) { 1915 ParentLoop->addChildLoop(Lp); 1916 ParentLoop->addBasicBlockToLoop(ScalarPH, LI->getBase()); 1917 ParentLoop->addBasicBlockToLoop(VectorPH, LI->getBase()); 1918 ParentLoop->addBasicBlockToLoop(MiddleBlock, LI->getBase()); 1919 } else { 1920 LI->addTopLevelLoop(Lp); 1921 } 1922 Lp->addBasicBlockToLoop(VecBody, LI->getBase()); 1923 1924 // Use this IR builder to create the loop instructions (Phi, Br, Cmp) 1925 // inside the loop. 1926 Builder.SetInsertPoint(VecBody->getFirstNonPHI()); 1927 1928 // Generate the induction variable. 1929 setDebugLocFromInst(Builder, getDebugLocFromInstOrOperands(OldInduction)); 1930 Induction = Builder.CreatePHI(IdxTy, 2, "index"); 1931 // The loop step is equal to the vectorization factor (num of SIMD elements) 1932 // times the unroll factor (num of SIMD instructions). 1933 Constant *Step = ConstantInt::get(IdxTy, VF * UF); 1934 1935 // This is the IR builder that we use to add all of the logic for bypassing 1936 // the new vector loop. 1937 IRBuilder<> BypassBuilder(BypassBlock->getTerminator()); 1938 setDebugLocFromInst(BypassBuilder, 1939 getDebugLocFromInstOrOperands(OldInduction)); 1940 1941 // We may need to extend the index in case there is a type mismatch. 1942 // We know that the count starts at zero and does not overflow. 1943 if (Count->getType() != IdxTy) { 1944 // The exit count can be of pointer type. Convert it to the correct 1945 // integer type. 1946 if (ExitCount->getType()->isPointerTy()) 1947 Count = BypassBuilder.CreatePointerCast(Count, IdxTy, "ptrcnt.to.int"); 1948 else 1949 Count = BypassBuilder.CreateZExtOrTrunc(Count, IdxTy, "cnt.cast"); 1950 } 1951 1952 // Add the start index to the loop count to get the new end index. 1953 Value *IdxEnd = BypassBuilder.CreateAdd(Count, StartIdx, "end.idx"); 1954 1955 // Now we need to generate the expression for N - (N % VF), which is 1956 // the part that the vectorized body will execute. 1957 Value *R = BypassBuilder.CreateURem(Count, Step, "n.mod.vf"); 1958 Value *CountRoundDown = BypassBuilder.CreateSub(Count, R, "n.vec"); 1959 Value *IdxEndRoundDown = BypassBuilder.CreateAdd(CountRoundDown, StartIdx, 1960 "end.idx.rnd.down"); 1961 1962 // Now, compare the new count to zero. If it is zero skip the vector loop and 1963 // jump to the scalar loop. 1964 Value *Cmp = BypassBuilder.CreateICmpEQ(IdxEndRoundDown, StartIdx, 1965 "cmp.zero"); 1966 1967 BasicBlock *LastBypassBlock = BypassBlock; 1968 1969 // Generate the code to check that the strides we assumed to be one are really 1970 // one. We want the new basic block to start at the first instruction in a 1971 // sequence of instructions that form a check. 1972 Instruction *StrideCheck; 1973 Instruction *FirstCheckInst; 1974 std::tie(FirstCheckInst, StrideCheck) = 1975 addStrideCheck(BypassBlock->getTerminator()); 1976 if (StrideCheck) { 1977 // Create a new block containing the stride check. 1978 BasicBlock *CheckBlock = 1979 BypassBlock->splitBasicBlock(FirstCheckInst, "vector.stridecheck"); 1980 if (ParentLoop) 1981 ParentLoop->addBasicBlockToLoop(CheckBlock, LI->getBase()); 1982 LoopBypassBlocks.push_back(CheckBlock); 1983 1984 // Replace the branch into the memory check block with a conditional branch 1985 // for the "few elements case". 1986 Instruction *OldTerm = BypassBlock->getTerminator(); 1987 BranchInst::Create(MiddleBlock, CheckBlock, Cmp, OldTerm); 1988 OldTerm->eraseFromParent(); 1989 1990 Cmp = StrideCheck; 1991 LastBypassBlock = CheckBlock; 1992 } 1993 1994 // Generate the code that checks in runtime if arrays overlap. We put the 1995 // checks into a separate block to make the more common case of few elements 1996 // faster. 1997 Instruction *MemRuntimeCheck; 1998 std::tie(FirstCheckInst, MemRuntimeCheck) = 1999 addRuntimeCheck(LastBypassBlock->getTerminator()); 2000 if (MemRuntimeCheck) { 2001 // Create a new block containing the memory check. 2002 BasicBlock *CheckBlock = 2003 LastBypassBlock->splitBasicBlock(MemRuntimeCheck, "vector.memcheck"); 2004 if (ParentLoop) 2005 ParentLoop->addBasicBlockToLoop(CheckBlock, LI->getBase()); 2006 LoopBypassBlocks.push_back(CheckBlock); 2007 2008 // Replace the branch into the memory check block with a conditional branch 2009 // for the "few elements case". 2010 Instruction *OldTerm = LastBypassBlock->getTerminator(); 2011 BranchInst::Create(MiddleBlock, CheckBlock, Cmp, OldTerm); 2012 OldTerm->eraseFromParent(); 2013 2014 Cmp = MemRuntimeCheck; 2015 LastBypassBlock = CheckBlock; 2016 } 2017 2018 LastBypassBlock->getTerminator()->eraseFromParent(); 2019 BranchInst::Create(MiddleBlock, VectorPH, Cmp, 2020 LastBypassBlock); 2021 2022 // We are going to resume the execution of the scalar loop. 2023 // Go over all of the induction variables that we found and fix the 2024 // PHIs that are left in the scalar version of the loop. 2025 // The starting values of PHI nodes depend on the counter of the last 2026 // iteration in the vectorized loop. 2027 // If we come from a bypass edge then we need to start from the original 2028 // start value. 2029 2030 // This variable saves the new starting index for the scalar loop. 2031 PHINode *ResumeIndex = 0; 2032 LoopVectorizationLegality::InductionList::iterator I, E; 2033 LoopVectorizationLegality::InductionList *List = Legal->getInductionVars(); 2034 // Set builder to point to last bypass block. 2035 BypassBuilder.SetInsertPoint(LoopBypassBlocks.back()->getTerminator()); 2036 for (I = List->begin(), E = List->end(); I != E; ++I) { 2037 PHINode *OrigPhi = I->first; 2038 LoopVectorizationLegality::InductionInfo II = I->second; 2039 2040 Type *ResumeValTy = (OrigPhi == OldInduction) ? IdxTy : OrigPhi->getType(); 2041 PHINode *ResumeVal = PHINode::Create(ResumeValTy, 2, "resume.val", 2042 MiddleBlock->getTerminator()); 2043 // We might have extended the type of the induction variable but we need a 2044 // truncated version for the scalar loop. 2045 PHINode *TruncResumeVal = (OrigPhi == OldInduction) ? 2046 PHINode::Create(OrigPhi->getType(), 2, "trunc.resume.val", 2047 MiddleBlock->getTerminator()) : 0; 2048 2049 Value *EndValue = 0; 2050 switch (II.IK) { 2051 case LoopVectorizationLegality::IK_NoInduction: 2052 llvm_unreachable("Unknown induction"); 2053 case LoopVectorizationLegality::IK_IntInduction: { 2054 // Handle the integer induction counter. 2055 assert(OrigPhi->getType()->isIntegerTy() && "Invalid type"); 2056 2057 // We have the canonical induction variable. 2058 if (OrigPhi == OldInduction) { 2059 // Create a truncated version of the resume value for the scalar loop, 2060 // we might have promoted the type to a larger width. 2061 EndValue = 2062 BypassBuilder.CreateTrunc(IdxEndRoundDown, OrigPhi->getType()); 2063 // The new PHI merges the original incoming value, in case of a bypass, 2064 // or the value at the end of the vectorized loop. 2065 for (unsigned I = 0, E = LoopBypassBlocks.size(); I != E; ++I) 2066 TruncResumeVal->addIncoming(II.StartValue, LoopBypassBlocks[I]); 2067 TruncResumeVal->addIncoming(EndValue, VecBody); 2068 2069 // We know what the end value is. 2070 EndValue = IdxEndRoundDown; 2071 // We also know which PHI node holds it. 2072 ResumeIndex = ResumeVal; 2073 break; 2074 } 2075 2076 // Not the canonical induction variable - add the vector loop count to the 2077 // start value. 2078 Value *CRD = BypassBuilder.CreateSExtOrTrunc(CountRoundDown, 2079 II.StartValue->getType(), 2080 "cast.crd"); 2081 EndValue = BypassBuilder.CreateAdd(CRD, II.StartValue , "ind.end"); 2082 break; 2083 } 2084 case LoopVectorizationLegality::IK_ReverseIntInduction: { 2085 // Convert the CountRoundDown variable to the PHI size. 2086 Value *CRD = BypassBuilder.CreateSExtOrTrunc(CountRoundDown, 2087 II.StartValue->getType(), 2088 "cast.crd"); 2089 // Handle reverse integer induction counter. 2090 EndValue = BypassBuilder.CreateSub(II.StartValue, CRD, "rev.ind.end"); 2091 break; 2092 } 2093 case LoopVectorizationLegality::IK_PtrInduction: { 2094 // For pointer induction variables, calculate the offset using 2095 // the end index. 2096 EndValue = BypassBuilder.CreateGEP(II.StartValue, CountRoundDown, 2097 "ptr.ind.end"); 2098 break; 2099 } 2100 case LoopVectorizationLegality::IK_ReversePtrInduction: { 2101 // The value at the end of the loop for the reverse pointer is calculated 2102 // by creating a GEP with a negative index starting from the start value. 2103 Value *Zero = ConstantInt::get(CountRoundDown->getType(), 0); 2104 Value *NegIdx = BypassBuilder.CreateSub(Zero, CountRoundDown, 2105 "rev.ind.end"); 2106 EndValue = BypassBuilder.CreateGEP(II.StartValue, NegIdx, 2107 "rev.ptr.ind.end"); 2108 break; 2109 } 2110 }// end of case 2111 2112 // The new PHI merges the original incoming value, in case of a bypass, 2113 // or the value at the end of the vectorized loop. 2114 for (unsigned I = 0, E = LoopBypassBlocks.size(); I != E; ++I) { 2115 if (OrigPhi == OldInduction) 2116 ResumeVal->addIncoming(StartIdx, LoopBypassBlocks[I]); 2117 else 2118 ResumeVal->addIncoming(II.StartValue, LoopBypassBlocks[I]); 2119 } 2120 ResumeVal->addIncoming(EndValue, VecBody); 2121 2122 // Fix the scalar body counter (PHI node). 2123 unsigned BlockIdx = OrigPhi->getBasicBlockIndex(ScalarPH); 2124 // The old inductions phi node in the scalar body needs the truncated value. 2125 if (OrigPhi == OldInduction) 2126 OrigPhi->setIncomingValue(BlockIdx, TruncResumeVal); 2127 else 2128 OrigPhi->setIncomingValue(BlockIdx, ResumeVal); 2129 } 2130 2131 // If we are generating a new induction variable then we also need to 2132 // generate the code that calculates the exit value. This value is not 2133 // simply the end of the counter because we may skip the vectorized body 2134 // in case of a runtime check. 2135 if (!OldInduction){ 2136 assert(!ResumeIndex && "Unexpected resume value found"); 2137 ResumeIndex = PHINode::Create(IdxTy, 2, "new.indc.resume.val", 2138 MiddleBlock->getTerminator()); 2139 for (unsigned I = 0, E = LoopBypassBlocks.size(); I != E; ++I) 2140 ResumeIndex->addIncoming(StartIdx, LoopBypassBlocks[I]); 2141 ResumeIndex->addIncoming(IdxEndRoundDown, VecBody); 2142 } 2143 2144 // Make sure that we found the index where scalar loop needs to continue. 2145 assert(ResumeIndex && ResumeIndex->getType()->isIntegerTy() && 2146 "Invalid resume Index"); 2147 2148 // Add a check in the middle block to see if we have completed 2149 // all of the iterations in the first vector loop. 2150 // If (N - N%VF) == N, then we *don't* need to run the remainder. 2151 Value *CmpN = CmpInst::Create(Instruction::ICmp, CmpInst::ICMP_EQ, IdxEnd, 2152 ResumeIndex, "cmp.n", 2153 MiddleBlock->getTerminator()); 2154 2155 BranchInst::Create(ExitBlock, ScalarPH, CmpN, MiddleBlock->getTerminator()); 2156 // Remove the old terminator. 2157 MiddleBlock->getTerminator()->eraseFromParent(); 2158 2159 // Create i+1 and fill the PHINode. 2160 Value *NextIdx = Builder.CreateAdd(Induction, Step, "index.next"); 2161 Induction->addIncoming(StartIdx, VectorPH); 2162 Induction->addIncoming(NextIdx, VecBody); 2163 // Create the compare. 2164 Value *ICmp = Builder.CreateICmpEQ(NextIdx, IdxEndRoundDown); 2165 Builder.CreateCondBr(ICmp, MiddleBlock, VecBody); 2166 2167 // Now we have two terminators. Remove the old one from the block. 2168 VecBody->getTerminator()->eraseFromParent(); 2169 2170 // Get ready to start creating new instructions into the vectorized body. 2171 Builder.SetInsertPoint(VecBody->getFirstInsertionPt()); 2172 2173 // Save the state. 2174 LoopVectorPreHeader = VectorPH; 2175 LoopScalarPreHeader = ScalarPH; 2176 LoopMiddleBlock = MiddleBlock; 2177 LoopExitBlock = ExitBlock; 2178 LoopVectorBody.push_back(VecBody); 2179 LoopScalarBody = OldBasicBlock; 2180 2181 LoopVectorizeHints Hints(Lp, true); 2182 Hints.setAlreadyVectorized(Lp); 2183} 2184 2185/// This function returns the identity element (or neutral element) for 2186/// the operation K. 2187Constant* 2188LoopVectorizationLegality::getReductionIdentity(ReductionKind K, Type *Tp) { 2189 switch (K) { 2190 case RK_IntegerXor: 2191 case RK_IntegerAdd: 2192 case RK_IntegerOr: 2193 // Adding, Xoring, Oring zero to a number does not change it. 2194 return ConstantInt::get(Tp, 0); 2195 case RK_IntegerMult: 2196 // Multiplying a number by 1 does not change it. 2197 return ConstantInt::get(Tp, 1); 2198 case RK_IntegerAnd: 2199 // AND-ing a number with an all-1 value does not change it. 2200 return ConstantInt::get(Tp, -1, true); 2201 case RK_FloatMult: 2202 // Multiplying a number by 1 does not change it. 2203 return ConstantFP::get(Tp, 1.0L); 2204 case RK_FloatAdd: 2205 // Adding zero to a number does not change it. 2206 return ConstantFP::get(Tp, 0.0L); 2207 default: 2208 llvm_unreachable("Unknown reduction kind"); 2209 } 2210} 2211 2212static Intrinsic::ID checkUnaryFloatSignature(const CallInst &I, 2213 Intrinsic::ID ValidIntrinsicID) { 2214 if (I.getNumArgOperands() != 1 || 2215 !I.getArgOperand(0)->getType()->isFloatingPointTy() || 2216 I.getType() != I.getArgOperand(0)->getType() || 2217 !I.onlyReadsMemory()) 2218 return Intrinsic::not_intrinsic; 2219 2220 return ValidIntrinsicID; 2221} 2222 2223static Intrinsic::ID checkBinaryFloatSignature(const CallInst &I, 2224 Intrinsic::ID ValidIntrinsicID) { 2225 if (I.getNumArgOperands() != 2 || 2226 !I.getArgOperand(0)->getType()->isFloatingPointTy() || 2227 !I.getArgOperand(1)->getType()->isFloatingPointTy() || 2228 I.getType() != I.getArgOperand(0)->getType() || 2229 I.getType() != I.getArgOperand(1)->getType() || 2230 !I.onlyReadsMemory()) 2231 return Intrinsic::not_intrinsic; 2232 2233 return ValidIntrinsicID; 2234} 2235 2236 2237static Intrinsic::ID 2238getIntrinsicIDForCall(CallInst *CI, const TargetLibraryInfo *TLI) { 2239 // If we have an intrinsic call, check if it is trivially vectorizable. 2240 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(CI)) { 2241 switch (II->getIntrinsicID()) { 2242 case Intrinsic::sqrt: 2243 case Intrinsic::sin: 2244 case Intrinsic::cos: 2245 case Intrinsic::exp: 2246 case Intrinsic::exp2: 2247 case Intrinsic::log: 2248 case Intrinsic::log10: 2249 case Intrinsic::log2: 2250 case Intrinsic::fabs: 2251 case Intrinsic::copysign: 2252 case Intrinsic::floor: 2253 case Intrinsic::ceil: 2254 case Intrinsic::trunc: 2255 case Intrinsic::rint: 2256 case Intrinsic::nearbyint: 2257 case Intrinsic::round: 2258 case Intrinsic::pow: 2259 case Intrinsic::fma: 2260 case Intrinsic::fmuladd: 2261 case Intrinsic::lifetime_start: 2262 case Intrinsic::lifetime_end: 2263 return II->getIntrinsicID(); 2264 default: 2265 return Intrinsic::not_intrinsic; 2266 } 2267 } 2268 2269 if (!TLI) 2270 return Intrinsic::not_intrinsic; 2271 2272 LibFunc::Func Func; 2273 Function *F = CI->getCalledFunction(); 2274 // We're going to make assumptions on the semantics of the functions, check 2275 // that the target knows that it's available in this environment and it does 2276 // not have local linkage. 2277 if (!F || F->hasLocalLinkage() || !TLI->getLibFunc(F->getName(), Func)) 2278 return Intrinsic::not_intrinsic; 2279 2280 // Otherwise check if we have a call to a function that can be turned into a 2281 // vector intrinsic. 2282 switch (Func) { 2283 default: 2284 break; 2285 case LibFunc::sin: 2286 case LibFunc::sinf: 2287 case LibFunc::sinl: 2288 return checkUnaryFloatSignature(*CI, Intrinsic::sin); 2289 case LibFunc::cos: 2290 case LibFunc::cosf: 2291 case LibFunc::cosl: 2292 return checkUnaryFloatSignature(*CI, Intrinsic::cos); 2293 case LibFunc::exp: 2294 case LibFunc::expf: 2295 case LibFunc::expl: 2296 return checkUnaryFloatSignature(*CI, Intrinsic::exp); 2297 case LibFunc::exp2: 2298 case LibFunc::exp2f: 2299 case LibFunc::exp2l: 2300 return checkUnaryFloatSignature(*CI, Intrinsic::exp2); 2301 case LibFunc::log: 2302 case LibFunc::logf: 2303 case LibFunc::logl: 2304 return checkUnaryFloatSignature(*CI, Intrinsic::log); 2305 case LibFunc::log10: 2306 case LibFunc::log10f: 2307 case LibFunc::log10l: 2308 return checkUnaryFloatSignature(*CI, Intrinsic::log10); 2309 case LibFunc::log2: 2310 case LibFunc::log2f: 2311 case LibFunc::log2l: 2312 return checkUnaryFloatSignature(*CI, Intrinsic::log2); 2313 case LibFunc::fabs: 2314 case LibFunc::fabsf: 2315 case LibFunc::fabsl: 2316 return checkUnaryFloatSignature(*CI, Intrinsic::fabs); 2317 case LibFunc::copysign: 2318 case LibFunc::copysignf: 2319 case LibFunc::copysignl: 2320 return checkBinaryFloatSignature(*CI, Intrinsic::copysign); 2321 case LibFunc::floor: 2322 case LibFunc::floorf: 2323 case LibFunc::floorl: 2324 return checkUnaryFloatSignature(*CI, Intrinsic::floor); 2325 case LibFunc::ceil: 2326 case LibFunc::ceilf: 2327 case LibFunc::ceill: 2328 return checkUnaryFloatSignature(*CI, Intrinsic::ceil); 2329 case LibFunc::trunc: 2330 case LibFunc::truncf: 2331 case LibFunc::truncl: 2332 return checkUnaryFloatSignature(*CI, Intrinsic::trunc); 2333 case LibFunc::rint: 2334 case LibFunc::rintf: 2335 case LibFunc::rintl: 2336 return checkUnaryFloatSignature(*CI, Intrinsic::rint); 2337 case LibFunc::nearbyint: 2338 case LibFunc::nearbyintf: 2339 case LibFunc::nearbyintl: 2340 return checkUnaryFloatSignature(*CI, Intrinsic::nearbyint); 2341 case LibFunc::round: 2342 case LibFunc::roundf: 2343 case LibFunc::roundl: 2344 return checkUnaryFloatSignature(*CI, Intrinsic::round); 2345 case LibFunc::pow: 2346 case LibFunc::powf: 2347 case LibFunc::powl: 2348 return checkBinaryFloatSignature(*CI, Intrinsic::pow); 2349 } 2350 2351 return Intrinsic::not_intrinsic; 2352} 2353 2354/// This function translates the reduction kind to an LLVM binary operator. 2355static unsigned 2356getReductionBinOp(LoopVectorizationLegality::ReductionKind Kind) { 2357 switch (Kind) { 2358 case LoopVectorizationLegality::RK_IntegerAdd: 2359 return Instruction::Add; 2360 case LoopVectorizationLegality::RK_IntegerMult: 2361 return Instruction::Mul; 2362 case LoopVectorizationLegality::RK_IntegerOr: 2363 return Instruction::Or; 2364 case LoopVectorizationLegality::RK_IntegerAnd: 2365 return Instruction::And; 2366 case LoopVectorizationLegality::RK_IntegerXor: 2367 return Instruction::Xor; 2368 case LoopVectorizationLegality::RK_FloatMult: 2369 return Instruction::FMul; 2370 case LoopVectorizationLegality::RK_FloatAdd: 2371 return Instruction::FAdd; 2372 case LoopVectorizationLegality::RK_IntegerMinMax: 2373 return Instruction::ICmp; 2374 case LoopVectorizationLegality::RK_FloatMinMax: 2375 return Instruction::FCmp; 2376 default: 2377 llvm_unreachable("Unknown reduction operation"); 2378 } 2379} 2380 2381Value *createMinMaxOp(IRBuilder<> &Builder, 2382 LoopVectorizationLegality::MinMaxReductionKind RK, 2383 Value *Left, 2384 Value *Right) { 2385 CmpInst::Predicate P = CmpInst::ICMP_NE; 2386 switch (RK) { 2387 default: 2388 llvm_unreachable("Unknown min/max reduction kind"); 2389 case LoopVectorizationLegality::MRK_UIntMin: 2390 P = CmpInst::ICMP_ULT; 2391 break; 2392 case LoopVectorizationLegality::MRK_UIntMax: 2393 P = CmpInst::ICMP_UGT; 2394 break; 2395 case LoopVectorizationLegality::MRK_SIntMin: 2396 P = CmpInst::ICMP_SLT; 2397 break; 2398 case LoopVectorizationLegality::MRK_SIntMax: 2399 P = CmpInst::ICMP_SGT; 2400 break; 2401 case LoopVectorizationLegality::MRK_FloatMin: 2402 P = CmpInst::FCMP_OLT; 2403 break; 2404 case LoopVectorizationLegality::MRK_FloatMax: 2405 P = CmpInst::FCMP_OGT; 2406 break; 2407 } 2408 2409 Value *Cmp; 2410 if (RK == LoopVectorizationLegality::MRK_FloatMin || 2411 RK == LoopVectorizationLegality::MRK_FloatMax) 2412 Cmp = Builder.CreateFCmp(P, Left, Right, "rdx.minmax.cmp"); 2413 else 2414 Cmp = Builder.CreateICmp(P, Left, Right, "rdx.minmax.cmp"); 2415 2416 Value *Select = Builder.CreateSelect(Cmp, Left, Right, "rdx.minmax.select"); 2417 return Select; 2418} 2419 2420namespace { 2421struct CSEDenseMapInfo { 2422 static bool canHandle(Instruction *I) { 2423 return isa<InsertElementInst>(I) || isa<ExtractElementInst>(I) || 2424 isa<ShuffleVectorInst>(I) || isa<GetElementPtrInst>(I); 2425 } 2426 static inline Instruction *getEmptyKey() { 2427 return DenseMapInfo<Instruction *>::getEmptyKey(); 2428 } 2429 static inline Instruction *getTombstoneKey() { 2430 return DenseMapInfo<Instruction *>::getTombstoneKey(); 2431 } 2432 static unsigned getHashValue(Instruction *I) { 2433 assert(canHandle(I) && "Unknown instruction!"); 2434 return hash_combine(I->getOpcode(), hash_combine_range(I->value_op_begin(), 2435 I->value_op_end())); 2436 } 2437 static bool isEqual(Instruction *LHS, Instruction *RHS) { 2438 if (LHS == getEmptyKey() || RHS == getEmptyKey() || 2439 LHS == getTombstoneKey() || RHS == getTombstoneKey()) 2440 return LHS == RHS; 2441 return LHS->isIdenticalTo(RHS); 2442 } 2443}; 2444} 2445 2446/// \brief Check whether this block is a predicated block. 2447/// Due to if predication of stores we might create a sequence of "if(pred) a[i] 2448/// = ...; " blocks. We start with one vectorized basic block. For every 2449/// conditional block we split this vectorized block. Therefore, every second 2450/// block will be a predicated one. 2451static bool isPredicatedBlock(unsigned BlockNum) { 2452 return BlockNum % 2; 2453} 2454 2455///\brief Perform cse of induction variable instructions. 2456static void cse(SmallVector<BasicBlock *, 4> &BBs) { 2457 // Perform simple cse. 2458 SmallDenseMap<Instruction *, Instruction *, 4, CSEDenseMapInfo> CSEMap; 2459 for (unsigned i = 0, e = BBs.size(); i != e; ++i) { 2460 BasicBlock *BB = BBs[i]; 2461 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E;) { 2462 Instruction *In = I++; 2463 2464 if (!CSEDenseMapInfo::canHandle(In)) 2465 continue; 2466 2467 // Check if we can replace this instruction with any of the 2468 // visited instructions. 2469 if (Instruction *V = CSEMap.lookup(In)) { 2470 In->replaceAllUsesWith(V); 2471 In->eraseFromParent(); 2472 continue; 2473 } 2474 // Ignore instructions in conditional blocks. We create "if (pred) a[i] = 2475 // ...;" blocks for predicated stores. Every second block is a predicated 2476 // block. 2477 if (isPredicatedBlock(i)) 2478 continue; 2479 2480 CSEMap[In] = In; 2481 } 2482 } 2483} 2484 2485/// \brief Adds a 'fast' flag to floating point operations. 2486static Value *addFastMathFlag(Value *V) { 2487 if (isa<FPMathOperator>(V)){ 2488 FastMathFlags Flags; 2489 Flags.setUnsafeAlgebra(); 2490 cast<Instruction>(V)->setFastMathFlags(Flags); 2491 } 2492 return V; 2493} 2494 2495void InnerLoopVectorizer::vectorizeLoop() { 2496 //===------------------------------------------------===// 2497 // 2498 // Notice: any optimization or new instruction that go 2499 // into the code below should be also be implemented in 2500 // the cost-model. 2501 // 2502 //===------------------------------------------------===// 2503 Constant *Zero = Builder.getInt32(0); 2504 2505 // In order to support reduction variables we need to be able to vectorize 2506 // Phi nodes. Phi nodes have cycles, so we need to vectorize them in two 2507 // stages. First, we create a new vector PHI node with no incoming edges. 2508 // We use this value when we vectorize all of the instructions that use the 2509 // PHI. Next, after all of the instructions in the block are complete we 2510 // add the new incoming edges to the PHI. At this point all of the 2511 // instructions in the basic block are vectorized, so we can use them to 2512 // construct the PHI. 2513 PhiVector RdxPHIsToFix; 2514 2515 // Scan the loop in a topological order to ensure that defs are vectorized 2516 // before users. 2517 LoopBlocksDFS DFS(OrigLoop); 2518 DFS.perform(LI); 2519 2520 // Vectorize all of the blocks in the original loop. 2521 for (LoopBlocksDFS::RPOIterator bb = DFS.beginRPO(), 2522 be = DFS.endRPO(); bb != be; ++bb) 2523 vectorizeBlockInLoop(*bb, &RdxPHIsToFix); 2524 2525 // At this point every instruction in the original loop is widened to 2526 // a vector form. We are almost done. Now, we need to fix the PHI nodes 2527 // that we vectorized. The PHI nodes are currently empty because we did 2528 // not want to introduce cycles. Notice that the remaining PHI nodes 2529 // that we need to fix are reduction variables. 2530 2531 // Create the 'reduced' values for each of the induction vars. 2532 // The reduced values are the vector values that we scalarize and combine 2533 // after the loop is finished. 2534 for (PhiVector::iterator it = RdxPHIsToFix.begin(), e = RdxPHIsToFix.end(); 2535 it != e; ++it) { 2536 PHINode *RdxPhi = *it; 2537 assert(RdxPhi && "Unable to recover vectorized PHI"); 2538 2539 // Find the reduction variable descriptor. 2540 assert(Legal->getReductionVars()->count(RdxPhi) && 2541 "Unable to find the reduction variable"); 2542 LoopVectorizationLegality::ReductionDescriptor RdxDesc = 2543 (*Legal->getReductionVars())[RdxPhi]; 2544 2545 setDebugLocFromInst(Builder, RdxDesc.StartValue); 2546 2547 // We need to generate a reduction vector from the incoming scalar. 2548 // To do so, we need to generate the 'identity' vector and override 2549 // one of the elements with the incoming scalar reduction. We need 2550 // to do it in the vector-loop preheader. 2551 Builder.SetInsertPoint(LoopBypassBlocks.front()->getTerminator()); 2552 2553 // This is the vector-clone of the value that leaves the loop. 2554 VectorParts &VectorExit = getVectorValue(RdxDesc.LoopExitInstr); 2555 Type *VecTy = VectorExit[0]->getType(); 2556 2557 // Find the reduction identity variable. Zero for addition, or, xor, 2558 // one for multiplication, -1 for And. 2559 Value *Identity; 2560 Value *VectorStart; 2561 if (RdxDesc.Kind == LoopVectorizationLegality::RK_IntegerMinMax || 2562 RdxDesc.Kind == LoopVectorizationLegality::RK_FloatMinMax) { 2563 // MinMax reduction have the start value as their identify. 2564 if (VF == 1) { 2565 VectorStart = Identity = RdxDesc.StartValue; 2566 } else { 2567 VectorStart = Identity = Builder.CreateVectorSplat(VF, 2568 RdxDesc.StartValue, 2569 "minmax.ident"); 2570 } 2571 } else { 2572 // Handle other reduction kinds: 2573 Constant *Iden = 2574 LoopVectorizationLegality::getReductionIdentity(RdxDesc.Kind, 2575 VecTy->getScalarType()); 2576 if (VF == 1) { 2577 Identity = Iden; 2578 // This vector is the Identity vector where the first element is the 2579 // incoming scalar reduction. 2580 VectorStart = RdxDesc.StartValue; 2581 } else { 2582 Identity = ConstantVector::getSplat(VF, Iden); 2583 2584 // This vector is the Identity vector where the first element is the 2585 // incoming scalar reduction. 2586 VectorStart = Builder.CreateInsertElement(Identity, 2587 RdxDesc.StartValue, Zero); 2588 } 2589 } 2590 2591 // Fix the vector-loop phi. 2592 // We created the induction variable so we know that the 2593 // preheader is the first entry. 2594 BasicBlock *VecPreheader = Induction->getIncomingBlock(0); 2595 2596 // Reductions do not have to start at zero. They can start with 2597 // any loop invariant values. 2598 VectorParts &VecRdxPhi = WidenMap.get(RdxPhi); 2599 BasicBlock *Latch = OrigLoop->getLoopLatch(); 2600 Value *LoopVal = RdxPhi->getIncomingValueForBlock(Latch); 2601 VectorParts &Val = getVectorValue(LoopVal); 2602 for (unsigned part = 0; part < UF; ++part) { 2603 // Make sure to add the reduction stat value only to the 2604 // first unroll part. 2605 Value *StartVal = (part == 0) ? VectorStart : Identity; 2606 cast<PHINode>(VecRdxPhi[part])->addIncoming(StartVal, VecPreheader); 2607 cast<PHINode>(VecRdxPhi[part])->addIncoming(Val[part], 2608 LoopVectorBody.back()); 2609 } 2610 2611 // Before each round, move the insertion point right between 2612 // the PHIs and the values we are going to write. 2613 // This allows us to write both PHINodes and the extractelement 2614 // instructions. 2615 Builder.SetInsertPoint(LoopMiddleBlock->getFirstInsertionPt()); 2616 2617 VectorParts RdxParts; 2618 setDebugLocFromInst(Builder, RdxDesc.LoopExitInstr); 2619 for (unsigned part = 0; part < UF; ++part) { 2620 // This PHINode contains the vectorized reduction variable, or 2621 // the initial value vector, if we bypass the vector loop. 2622 VectorParts &RdxExitVal = getVectorValue(RdxDesc.LoopExitInstr); 2623 PHINode *NewPhi = Builder.CreatePHI(VecTy, 2, "rdx.vec.exit.phi"); 2624 Value *StartVal = (part == 0) ? VectorStart : Identity; 2625 for (unsigned I = 0, E = LoopBypassBlocks.size(); I != E; ++I) 2626 NewPhi->addIncoming(StartVal, LoopBypassBlocks[I]); 2627 NewPhi->addIncoming(RdxExitVal[part], 2628 LoopVectorBody.back()); 2629 RdxParts.push_back(NewPhi); 2630 } 2631 2632 // Reduce all of the unrolled parts into a single vector. 2633 Value *ReducedPartRdx = RdxParts[0]; 2634 unsigned Op = getReductionBinOp(RdxDesc.Kind); 2635 setDebugLocFromInst(Builder, ReducedPartRdx); 2636 for (unsigned part = 1; part < UF; ++part) { 2637 if (Op != Instruction::ICmp && Op != Instruction::FCmp) 2638 // Floating point operations had to be 'fast' to enable the reduction. 2639 ReducedPartRdx = addFastMathFlag( 2640 Builder.CreateBinOp((Instruction::BinaryOps)Op, RdxParts[part], 2641 ReducedPartRdx, "bin.rdx")); 2642 else 2643 ReducedPartRdx = createMinMaxOp(Builder, RdxDesc.MinMaxKind, 2644 ReducedPartRdx, RdxParts[part]); 2645 } 2646 2647 if (VF > 1) { 2648 // VF is a power of 2 so we can emit the reduction using log2(VF) shuffles 2649 // and vector ops, reducing the set of values being computed by half each 2650 // round. 2651 assert(isPowerOf2_32(VF) && 2652 "Reduction emission only supported for pow2 vectors!"); 2653 Value *TmpVec = ReducedPartRdx; 2654 SmallVector<Constant*, 32> ShuffleMask(VF, 0); 2655 for (unsigned i = VF; i != 1; i >>= 1) { 2656 // Move the upper half of the vector to the lower half. 2657 for (unsigned j = 0; j != i/2; ++j) 2658 ShuffleMask[j] = Builder.getInt32(i/2 + j); 2659 2660 // Fill the rest of the mask with undef. 2661 std::fill(&ShuffleMask[i/2], ShuffleMask.end(), 2662 UndefValue::get(Builder.getInt32Ty())); 2663 2664 Value *Shuf = 2665 Builder.CreateShuffleVector(TmpVec, 2666 UndefValue::get(TmpVec->getType()), 2667 ConstantVector::get(ShuffleMask), 2668 "rdx.shuf"); 2669 2670 if (Op != Instruction::ICmp && Op != Instruction::FCmp) 2671 // Floating point operations had to be 'fast' to enable the reduction. 2672 TmpVec = addFastMathFlag(Builder.CreateBinOp( 2673 (Instruction::BinaryOps)Op, TmpVec, Shuf, "bin.rdx")); 2674 else 2675 TmpVec = createMinMaxOp(Builder, RdxDesc.MinMaxKind, TmpVec, Shuf); 2676 } 2677 2678 // The result is in the first element of the vector. 2679 ReducedPartRdx = Builder.CreateExtractElement(TmpVec, 2680 Builder.getInt32(0)); 2681 } 2682 2683 // Now, we need to fix the users of the reduction variable 2684 // inside and outside of the scalar remainder loop. 2685 // We know that the loop is in LCSSA form. We need to update the 2686 // PHI nodes in the exit blocks. 2687 for (BasicBlock::iterator LEI = LoopExitBlock->begin(), 2688 LEE = LoopExitBlock->end(); LEI != LEE; ++LEI) { 2689 PHINode *LCSSAPhi = dyn_cast<PHINode>(LEI); 2690 if (!LCSSAPhi) break; 2691 2692 // All PHINodes need to have a single entry edge, or two if 2693 // we already fixed them. 2694 assert(LCSSAPhi->getNumIncomingValues() < 3 && "Invalid LCSSA PHI"); 2695 2696 // We found our reduction value exit-PHI. Update it with the 2697 // incoming bypass edge. 2698 if (LCSSAPhi->getIncomingValue(0) == RdxDesc.LoopExitInstr) { 2699 // Add an edge coming from the bypass. 2700 LCSSAPhi->addIncoming(ReducedPartRdx, LoopMiddleBlock); 2701 break; 2702 } 2703 }// end of the LCSSA phi scan. 2704 2705 // Fix the scalar loop reduction variable with the incoming reduction sum 2706 // from the vector body and from the backedge value. 2707 int IncomingEdgeBlockIdx = 2708 (RdxPhi)->getBasicBlockIndex(OrigLoop->getLoopLatch()); 2709 assert(IncomingEdgeBlockIdx >= 0 && "Invalid block index"); 2710 // Pick the other block. 2711 int SelfEdgeBlockIdx = (IncomingEdgeBlockIdx ? 0 : 1); 2712 (RdxPhi)->setIncomingValue(SelfEdgeBlockIdx, ReducedPartRdx); 2713 (RdxPhi)->setIncomingValue(IncomingEdgeBlockIdx, RdxDesc.LoopExitInstr); 2714 }// end of for each redux variable. 2715 2716 fixLCSSAPHIs(); 2717 2718 // Remove redundant induction instructions. 2719 cse(LoopVectorBody); 2720} 2721 2722void InnerLoopVectorizer::fixLCSSAPHIs() { 2723 for (BasicBlock::iterator LEI = LoopExitBlock->begin(), 2724 LEE = LoopExitBlock->end(); LEI != LEE; ++LEI) { 2725 PHINode *LCSSAPhi = dyn_cast<PHINode>(LEI); 2726 if (!LCSSAPhi) break; 2727 if (LCSSAPhi->getNumIncomingValues() == 1) 2728 LCSSAPhi->addIncoming(UndefValue::get(LCSSAPhi->getType()), 2729 LoopMiddleBlock); 2730 } 2731} 2732 2733InnerLoopVectorizer::VectorParts 2734InnerLoopVectorizer::createEdgeMask(BasicBlock *Src, BasicBlock *Dst) { 2735 assert(std::find(pred_begin(Dst), pred_end(Dst), Src) != pred_end(Dst) && 2736 "Invalid edge"); 2737 2738 // Look for cached value. 2739 std::pair<BasicBlock*, BasicBlock*> Edge(Src, Dst); 2740 EdgeMaskCache::iterator ECEntryIt = MaskCache.find(Edge); 2741 if (ECEntryIt != MaskCache.end()) 2742 return ECEntryIt->second; 2743 2744 VectorParts SrcMask = createBlockInMask(Src); 2745 2746 // The terminator has to be a branch inst! 2747 BranchInst *BI = dyn_cast<BranchInst>(Src->getTerminator()); 2748 assert(BI && "Unexpected terminator found"); 2749 2750 if (BI->isConditional()) { 2751 VectorParts EdgeMask = getVectorValue(BI->getCondition()); 2752 2753 if (BI->getSuccessor(0) != Dst) 2754 for (unsigned part = 0; part < UF; ++part) 2755 EdgeMask[part] = Builder.CreateNot(EdgeMask[part]); 2756 2757 for (unsigned part = 0; part < UF; ++part) 2758 EdgeMask[part] = Builder.CreateAnd(EdgeMask[part], SrcMask[part]); 2759 2760 MaskCache[Edge] = EdgeMask; 2761 return EdgeMask; 2762 } 2763 2764 MaskCache[Edge] = SrcMask; 2765 return SrcMask; 2766} 2767 2768InnerLoopVectorizer::VectorParts 2769InnerLoopVectorizer::createBlockInMask(BasicBlock *BB) { 2770 assert(OrigLoop->contains(BB) && "Block is not a part of a loop"); 2771 2772 // Loop incoming mask is all-one. 2773 if (OrigLoop->getHeader() == BB) { 2774 Value *C = ConstantInt::get(IntegerType::getInt1Ty(BB->getContext()), 1); 2775 return getVectorValue(C); 2776 } 2777 2778 // This is the block mask. We OR all incoming edges, and with zero. 2779 Value *Zero = ConstantInt::get(IntegerType::getInt1Ty(BB->getContext()), 0); 2780 VectorParts BlockMask = getVectorValue(Zero); 2781 2782 // For each pred: 2783 for (pred_iterator it = pred_begin(BB), e = pred_end(BB); it != e; ++it) { 2784 VectorParts EM = createEdgeMask(*it, BB); 2785 for (unsigned part = 0; part < UF; ++part) 2786 BlockMask[part] = Builder.CreateOr(BlockMask[part], EM[part]); 2787 } 2788 2789 return BlockMask; 2790} 2791 2792void InnerLoopVectorizer::widenPHIInstruction(Instruction *PN, 2793 InnerLoopVectorizer::VectorParts &Entry, 2794 unsigned UF, unsigned VF, PhiVector *PV) { 2795 PHINode* P = cast<PHINode>(PN); 2796 // Handle reduction variables: 2797 if (Legal->getReductionVars()->count(P)) { 2798 for (unsigned part = 0; part < UF; ++part) { 2799 // This is phase one of vectorizing PHIs. 2800 Type *VecTy = (VF == 1) ? PN->getType() : 2801 VectorType::get(PN->getType(), VF); 2802 Entry[part] = PHINode::Create(VecTy, 2, "vec.phi", 2803 LoopVectorBody.back()-> getFirstInsertionPt()); 2804 } 2805 PV->push_back(P); 2806 return; 2807 } 2808 2809 setDebugLocFromInst(Builder, P); 2810 // Check for PHI nodes that are lowered to vector selects. 2811 if (P->getParent() != OrigLoop->getHeader()) { 2812 // We know that all PHIs in non-header blocks are converted into 2813 // selects, so we don't have to worry about the insertion order and we 2814 // can just use the builder. 2815 // At this point we generate the predication tree. There may be 2816 // duplications since this is a simple recursive scan, but future 2817 // optimizations will clean it up. 2818 2819 unsigned NumIncoming = P->getNumIncomingValues(); 2820 2821 // Generate a sequence of selects of the form: 2822 // SELECT(Mask3, In3, 2823 // SELECT(Mask2, In2, 2824 // ( ...))) 2825 for (unsigned In = 0; In < NumIncoming; In++) { 2826 VectorParts Cond = createEdgeMask(P->getIncomingBlock(In), 2827 P->getParent()); 2828 VectorParts &In0 = getVectorValue(P->getIncomingValue(In)); 2829 2830 for (unsigned part = 0; part < UF; ++part) { 2831 // We might have single edge PHIs (blocks) - use an identity 2832 // 'select' for the first PHI operand. 2833 if (In == 0) 2834 Entry[part] = Builder.CreateSelect(Cond[part], In0[part], 2835 In0[part]); 2836 else 2837 // Select between the current value and the previous incoming edge 2838 // based on the incoming mask. 2839 Entry[part] = Builder.CreateSelect(Cond[part], In0[part], 2840 Entry[part], "predphi"); 2841 } 2842 } 2843 return; 2844 } 2845 2846 // This PHINode must be an induction variable. 2847 // Make sure that we know about it. 2848 assert(Legal->getInductionVars()->count(P) && 2849 "Not an induction variable"); 2850 2851 LoopVectorizationLegality::InductionInfo II = 2852 Legal->getInductionVars()->lookup(P); 2853 2854 switch (II.IK) { 2855 case LoopVectorizationLegality::IK_NoInduction: 2856 llvm_unreachable("Unknown induction"); 2857 case LoopVectorizationLegality::IK_IntInduction: { 2858 assert(P->getType() == II.StartValue->getType() && "Types must match"); 2859 Type *PhiTy = P->getType(); 2860 Value *Broadcasted; 2861 if (P == OldInduction) { 2862 // Handle the canonical induction variable. We might have had to 2863 // extend the type. 2864 Broadcasted = Builder.CreateTrunc(Induction, PhiTy); 2865 } else { 2866 // Handle other induction variables that are now based on the 2867 // canonical one. 2868 Value *NormalizedIdx = Builder.CreateSub(Induction, ExtendedIdx, 2869 "normalized.idx"); 2870 NormalizedIdx = Builder.CreateSExtOrTrunc(NormalizedIdx, PhiTy); 2871 Broadcasted = Builder.CreateAdd(II.StartValue, NormalizedIdx, 2872 "offset.idx"); 2873 } 2874 Broadcasted = getBroadcastInstrs(Broadcasted); 2875 // After broadcasting the induction variable we need to make the vector 2876 // consecutive by adding 0, 1, 2, etc. 2877 for (unsigned part = 0; part < UF; ++part) 2878 Entry[part] = getConsecutiveVector(Broadcasted, VF * part, false); 2879 return; 2880 } 2881 case LoopVectorizationLegality::IK_ReverseIntInduction: 2882 case LoopVectorizationLegality::IK_PtrInduction: 2883 case LoopVectorizationLegality::IK_ReversePtrInduction: 2884 // Handle reverse integer and pointer inductions. 2885 Value *StartIdx = ExtendedIdx; 2886 // This is the normalized GEP that starts counting at zero. 2887 Value *NormalizedIdx = Builder.CreateSub(Induction, StartIdx, 2888 "normalized.idx"); 2889 2890 // Handle the reverse integer induction variable case. 2891 if (LoopVectorizationLegality::IK_ReverseIntInduction == II.IK) { 2892 IntegerType *DstTy = cast<IntegerType>(II.StartValue->getType()); 2893 Value *CNI = Builder.CreateSExtOrTrunc(NormalizedIdx, DstTy, 2894 "resize.norm.idx"); 2895 Value *ReverseInd = Builder.CreateSub(II.StartValue, CNI, 2896 "reverse.idx"); 2897 2898 // This is a new value so do not hoist it out. 2899 Value *Broadcasted = getBroadcastInstrs(ReverseInd); 2900 // After broadcasting the induction variable we need to make the 2901 // vector consecutive by adding ... -3, -2, -1, 0. 2902 for (unsigned part = 0; part < UF; ++part) 2903 Entry[part] = getConsecutiveVector(Broadcasted, -(int)VF * part, 2904 true); 2905 return; 2906 } 2907 2908 // Handle the pointer induction variable case. 2909 assert(P->getType()->isPointerTy() && "Unexpected type."); 2910 2911 // Is this a reverse induction ptr or a consecutive induction ptr. 2912 bool Reverse = (LoopVectorizationLegality::IK_ReversePtrInduction == 2913 II.IK); 2914 2915 // This is the vector of results. Notice that we don't generate 2916 // vector geps because scalar geps result in better code. 2917 for (unsigned part = 0; part < UF; ++part) { 2918 if (VF == 1) { 2919 int EltIndex = (part) * (Reverse ? -1 : 1); 2920 Constant *Idx = ConstantInt::get(Induction->getType(), EltIndex); 2921 Value *GlobalIdx; 2922 if (Reverse) 2923 GlobalIdx = Builder.CreateSub(Idx, NormalizedIdx, "gep.ridx"); 2924 else 2925 GlobalIdx = Builder.CreateAdd(NormalizedIdx, Idx, "gep.idx"); 2926 2927 Value *SclrGep = Builder.CreateGEP(II.StartValue, GlobalIdx, 2928 "next.gep"); 2929 Entry[part] = SclrGep; 2930 continue; 2931 } 2932 2933 Value *VecVal = UndefValue::get(VectorType::get(P->getType(), VF)); 2934 for (unsigned int i = 0; i < VF; ++i) { 2935 int EltIndex = (i + part * VF) * (Reverse ? -1 : 1); 2936 Constant *Idx = ConstantInt::get(Induction->getType(), EltIndex); 2937 Value *GlobalIdx; 2938 if (!Reverse) 2939 GlobalIdx = Builder.CreateAdd(NormalizedIdx, Idx, "gep.idx"); 2940 else 2941 GlobalIdx = Builder.CreateSub(Idx, NormalizedIdx, "gep.ridx"); 2942 2943 Value *SclrGep = Builder.CreateGEP(II.StartValue, GlobalIdx, 2944 "next.gep"); 2945 VecVal = Builder.CreateInsertElement(VecVal, SclrGep, 2946 Builder.getInt32(i), 2947 "insert.gep"); 2948 } 2949 Entry[part] = VecVal; 2950 } 2951 return; 2952 } 2953} 2954 2955void InnerLoopVectorizer::vectorizeBlockInLoop(BasicBlock *BB, PhiVector *PV) { 2956 // For each instruction in the old loop. 2957 for (BasicBlock::iterator it = BB->begin(), e = BB->end(); it != e; ++it) { 2958 VectorParts &Entry = WidenMap.get(it); 2959 switch (it->getOpcode()) { 2960 case Instruction::Br: 2961 // Nothing to do for PHIs and BR, since we already took care of the 2962 // loop control flow instructions. 2963 continue; 2964 case Instruction::PHI:{ 2965 // Vectorize PHINodes. 2966 widenPHIInstruction(it, Entry, UF, VF, PV); 2967 continue; 2968 }// End of PHI. 2969 2970 case Instruction::Add: 2971 case Instruction::FAdd: 2972 case Instruction::Sub: 2973 case Instruction::FSub: 2974 case Instruction::Mul: 2975 case Instruction::FMul: 2976 case Instruction::UDiv: 2977 case Instruction::SDiv: 2978 case Instruction::FDiv: 2979 case Instruction::URem: 2980 case Instruction::SRem: 2981 case Instruction::FRem: 2982 case Instruction::Shl: 2983 case Instruction::LShr: 2984 case Instruction::AShr: 2985 case Instruction::And: 2986 case Instruction::Or: 2987 case Instruction::Xor: { 2988 // Just widen binops. 2989 BinaryOperator *BinOp = dyn_cast<BinaryOperator>(it); 2990 setDebugLocFromInst(Builder, BinOp); 2991 VectorParts &A = getVectorValue(it->getOperand(0)); 2992 VectorParts &B = getVectorValue(it->getOperand(1)); 2993 2994 // Use this vector value for all users of the original instruction. 2995 for (unsigned Part = 0; Part < UF; ++Part) { 2996 Value *V = Builder.CreateBinOp(BinOp->getOpcode(), A[Part], B[Part]); 2997 2998 // Update the NSW, NUW and Exact flags. Notice: V can be an Undef. 2999 BinaryOperator *VecOp = dyn_cast<BinaryOperator>(V); 3000 if (VecOp && isa<OverflowingBinaryOperator>(BinOp)) { 3001 VecOp->setHasNoSignedWrap(BinOp->hasNoSignedWrap()); 3002 VecOp->setHasNoUnsignedWrap(BinOp->hasNoUnsignedWrap()); 3003 } 3004 if (VecOp && isa<PossiblyExactOperator>(VecOp)) 3005 VecOp->setIsExact(BinOp->isExact()); 3006 3007 // Copy the fast-math flags. 3008 if (VecOp && isa<FPMathOperator>(V)) 3009 VecOp->setFastMathFlags(it->getFastMathFlags()); 3010 3011 Entry[Part] = V; 3012 } 3013 break; 3014 } 3015 case Instruction::Select: { 3016 // Widen selects. 3017 // If the selector is loop invariant we can create a select 3018 // instruction with a scalar condition. Otherwise, use vector-select. 3019 bool InvariantCond = SE->isLoopInvariant(SE->getSCEV(it->getOperand(0)), 3020 OrigLoop); 3021 setDebugLocFromInst(Builder, it); 3022 3023 // The condition can be loop invariant but still defined inside the 3024 // loop. This means that we can't just use the original 'cond' value. 3025 // We have to take the 'vectorized' value and pick the first lane. 3026 // Instcombine will make this a no-op. 3027 VectorParts &Cond = getVectorValue(it->getOperand(0)); 3028 VectorParts &Op0 = getVectorValue(it->getOperand(1)); 3029 VectorParts &Op1 = getVectorValue(it->getOperand(2)); 3030 3031 Value *ScalarCond = (VF == 1) ? Cond[0] : 3032 Builder.CreateExtractElement(Cond[0], Builder.getInt32(0)); 3033 3034 for (unsigned Part = 0; Part < UF; ++Part) { 3035 Entry[Part] = Builder.CreateSelect( 3036 InvariantCond ? ScalarCond : Cond[Part], 3037 Op0[Part], 3038 Op1[Part]); 3039 } 3040 break; 3041 } 3042 3043 case Instruction::ICmp: 3044 case Instruction::FCmp: { 3045 // Widen compares. Generate vector compares. 3046 bool FCmp = (it->getOpcode() == Instruction::FCmp); 3047 CmpInst *Cmp = dyn_cast<CmpInst>(it); 3048 setDebugLocFromInst(Builder, it); 3049 VectorParts &A = getVectorValue(it->getOperand(0)); 3050 VectorParts &B = getVectorValue(it->getOperand(1)); 3051 for (unsigned Part = 0; Part < UF; ++Part) { 3052 Value *C = 0; 3053 if (FCmp) 3054 C = Builder.CreateFCmp(Cmp->getPredicate(), A[Part], B[Part]); 3055 else 3056 C = Builder.CreateICmp(Cmp->getPredicate(), A[Part], B[Part]); 3057 Entry[Part] = C; 3058 } 3059 break; 3060 } 3061 3062 case Instruction::Store: 3063 case Instruction::Load: 3064 vectorizeMemoryInstruction(it); 3065 break; 3066 case Instruction::ZExt: 3067 case Instruction::SExt: 3068 case Instruction::FPToUI: 3069 case Instruction::FPToSI: 3070 case Instruction::FPExt: 3071 case Instruction::PtrToInt: 3072 case Instruction::IntToPtr: 3073 case Instruction::SIToFP: 3074 case Instruction::UIToFP: 3075 case Instruction::Trunc: 3076 case Instruction::FPTrunc: 3077 case Instruction::BitCast: { 3078 CastInst *CI = dyn_cast<CastInst>(it); 3079 setDebugLocFromInst(Builder, it); 3080 /// Optimize the special case where the source is the induction 3081 /// variable. Notice that we can only optimize the 'trunc' case 3082 /// because: a. FP conversions lose precision, b. sext/zext may wrap, 3083 /// c. other casts depend on pointer size. 3084 if (CI->getOperand(0) == OldInduction && 3085 it->getOpcode() == Instruction::Trunc) { 3086 Value *ScalarCast = Builder.CreateCast(CI->getOpcode(), Induction, 3087 CI->getType()); 3088 Value *Broadcasted = getBroadcastInstrs(ScalarCast); 3089 for (unsigned Part = 0; Part < UF; ++Part) 3090 Entry[Part] = getConsecutiveVector(Broadcasted, VF * Part, false); 3091 break; 3092 } 3093 /// Vectorize casts. 3094 Type *DestTy = (VF == 1) ? CI->getType() : 3095 VectorType::get(CI->getType(), VF); 3096 3097 VectorParts &A = getVectorValue(it->getOperand(0)); 3098 for (unsigned Part = 0; Part < UF; ++Part) 3099 Entry[Part] = Builder.CreateCast(CI->getOpcode(), A[Part], DestTy); 3100 break; 3101 } 3102 3103 case Instruction::Call: { 3104 // Ignore dbg intrinsics. 3105 if (isa<DbgInfoIntrinsic>(it)) 3106 break; 3107 setDebugLocFromInst(Builder, it); 3108 3109 Module *M = BB->getParent()->getParent(); 3110 CallInst *CI = cast<CallInst>(it); 3111 Intrinsic::ID ID = getIntrinsicIDForCall(CI, TLI); 3112 assert(ID && "Not an intrinsic call!"); 3113 switch (ID) { 3114 case Intrinsic::lifetime_end: 3115 case Intrinsic::lifetime_start: 3116 scalarizeInstruction(it); 3117 break; 3118 default: 3119 for (unsigned Part = 0; Part < UF; ++Part) { 3120 SmallVector<Value *, 4> Args; 3121 for (unsigned i = 0, ie = CI->getNumArgOperands(); i != ie; ++i) { 3122 VectorParts &Arg = getVectorValue(CI->getArgOperand(i)); 3123 Args.push_back(Arg[Part]); 3124 } 3125 Type *Tys[] = {CI->getType()}; 3126 if (VF > 1) 3127 Tys[0] = VectorType::get(CI->getType()->getScalarType(), VF); 3128 3129 Function *F = Intrinsic::getDeclaration(M, ID, Tys); 3130 Entry[Part] = Builder.CreateCall(F, Args); 3131 } 3132 break; 3133 } 3134 break; 3135 } 3136 3137 default: 3138 // All other instructions are unsupported. Scalarize them. 3139 scalarizeInstruction(it); 3140 break; 3141 }// end of switch. 3142 }// end of for_each instr. 3143} 3144 3145void InnerLoopVectorizer::updateAnalysis() { 3146 // Forget the original basic block. 3147 SE->forgetLoop(OrigLoop); 3148 3149 // Update the dominator tree information. 3150 assert(DT->properlyDominates(LoopBypassBlocks.front(), LoopExitBlock) && 3151 "Entry does not dominate exit."); 3152 3153 for (unsigned I = 1, E = LoopBypassBlocks.size(); I != E; ++I) 3154 DT->addNewBlock(LoopBypassBlocks[I], LoopBypassBlocks[I-1]); 3155 DT->addNewBlock(LoopVectorPreHeader, LoopBypassBlocks.back()); 3156 3157 // Due to if predication of stores we might create a sequence of "if(pred) 3158 // a[i] = ...; " blocks. 3159 for (unsigned i = 0, e = LoopVectorBody.size(); i != e; ++i) { 3160 if (i == 0) 3161 DT->addNewBlock(LoopVectorBody[0], LoopVectorPreHeader); 3162 else if (isPredicatedBlock(i)) { 3163 DT->addNewBlock(LoopVectorBody[i], LoopVectorBody[i-1]); 3164 } else { 3165 DT->addNewBlock(LoopVectorBody[i], LoopVectorBody[i-2]); 3166 } 3167 } 3168 3169 DT->addNewBlock(LoopMiddleBlock, LoopBypassBlocks.front()); 3170 DT->addNewBlock(LoopScalarPreHeader, LoopMiddleBlock); 3171 DT->changeImmediateDominator(LoopScalarBody, LoopScalarPreHeader); 3172 DT->changeImmediateDominator(LoopExitBlock, LoopMiddleBlock); 3173 3174 DEBUG(DT->verifyDomTree()); 3175} 3176 3177/// \brief Check whether it is safe to if-convert this phi node. 3178/// 3179/// Phi nodes with constant expressions that can trap are not safe to if 3180/// convert. 3181static bool canIfConvertPHINodes(BasicBlock *BB) { 3182 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) { 3183 PHINode *Phi = dyn_cast<PHINode>(I); 3184 if (!Phi) 3185 return true; 3186 for (unsigned p = 0, e = Phi->getNumIncomingValues(); p != e; ++p) 3187 if (Constant *C = dyn_cast<Constant>(Phi->getIncomingValue(p))) 3188 if (C->canTrap()) 3189 return false; 3190 } 3191 return true; 3192} 3193 3194bool LoopVectorizationLegality::canVectorizeWithIfConvert() { 3195 if (!EnableIfConversion) 3196 return false; 3197 3198 assert(TheLoop->getNumBlocks() > 1 && "Single block loops are vectorizable"); 3199 3200 // A list of pointers that we can safely read and write to. 3201 SmallPtrSet<Value *, 8> SafePointes; 3202 3203 // Collect safe addresses. 3204 for (Loop::block_iterator BI = TheLoop->block_begin(), 3205 BE = TheLoop->block_end(); BI != BE; ++BI) { 3206 BasicBlock *BB = *BI; 3207 3208 if (blockNeedsPredication(BB)) 3209 continue; 3210 3211 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) { 3212 if (LoadInst *LI = dyn_cast<LoadInst>(I)) 3213 SafePointes.insert(LI->getPointerOperand()); 3214 else if (StoreInst *SI = dyn_cast<StoreInst>(I)) 3215 SafePointes.insert(SI->getPointerOperand()); 3216 } 3217 } 3218 3219 // Collect the blocks that need predication. 3220 BasicBlock *Header = TheLoop->getHeader(); 3221 for (Loop::block_iterator BI = TheLoop->block_begin(), 3222 BE = TheLoop->block_end(); BI != BE; ++BI) { 3223 BasicBlock *BB = *BI; 3224 3225 // We don't support switch statements inside loops. 3226 if (!isa<BranchInst>(BB->getTerminator())) 3227 return false; 3228 3229 // We must be able to predicate all blocks that need to be predicated. 3230 if (blockNeedsPredication(BB)) { 3231 if (!blockCanBePredicated(BB, SafePointes)) 3232 return false; 3233 } else if (BB != Header && !canIfConvertPHINodes(BB)) 3234 return false; 3235 3236 } 3237 3238 // We can if-convert this loop. 3239 return true; 3240} 3241 3242bool LoopVectorizationLegality::canVectorize() { 3243 // We must have a loop in canonical form. Loops with indirectbr in them cannot 3244 // be canonicalized. 3245 if (!TheLoop->getLoopPreheader()) 3246 return false; 3247 3248 // We can only vectorize innermost loops. 3249 if (TheLoop->getSubLoopsVector().size()) 3250 return false; 3251 3252 // We must have a single backedge. 3253 if (TheLoop->getNumBackEdges() != 1) 3254 return false; 3255 3256 // We must have a single exiting block. 3257 if (!TheLoop->getExitingBlock()) 3258 return false; 3259 3260 // We need to have a loop header. 3261 DEBUG(dbgs() << "LV: Found a loop: " << 3262 TheLoop->getHeader()->getName() << '\n'); 3263 3264 // Check if we can if-convert non-single-bb loops. 3265 unsigned NumBlocks = TheLoop->getNumBlocks(); 3266 if (NumBlocks != 1 && !canVectorizeWithIfConvert()) { 3267 DEBUG(dbgs() << "LV: Can't if-convert the loop.\n"); 3268 return false; 3269 } 3270 3271 // ScalarEvolution needs to be able to find the exit count. 3272 const SCEV *ExitCount = SE->getBackedgeTakenCount(TheLoop); 3273 if (ExitCount == SE->getCouldNotCompute()) { 3274 DEBUG(dbgs() << "LV: SCEV could not compute the loop exit count.\n"); 3275 return false; 3276 } 3277 3278 // Do not loop-vectorize loops with a tiny trip count. 3279 BasicBlock *Latch = TheLoop->getLoopLatch(); 3280 unsigned TC = SE->getSmallConstantTripCount(TheLoop, Latch); 3281 if (TC > 0u && TC < TinyTripCountVectorThreshold) { 3282 DEBUG(dbgs() << "LV: Found a loop with a very small trip count. " << 3283 "This loop is not worth vectorizing.\n"); 3284 return false; 3285 } 3286 3287 // Check if we can vectorize the instructions and CFG in this loop. 3288 if (!canVectorizeInstrs()) { 3289 DEBUG(dbgs() << "LV: Can't vectorize the instructions or CFG\n"); 3290 return false; 3291 } 3292 3293 // Go over each instruction and look at memory deps. 3294 if (!canVectorizeMemory()) { 3295 DEBUG(dbgs() << "LV: Can't vectorize due to memory conflicts\n"); 3296 return false; 3297 } 3298 3299 // Collect all of the variables that remain uniform after vectorization. 3300 collectLoopUniforms(); 3301 3302 DEBUG(dbgs() << "LV: We can vectorize this loop" << 3303 (PtrRtCheck.Need ? " (with a runtime bound check)" : "") 3304 <<"!\n"); 3305 3306 // Okay! We can vectorize. At this point we don't have any other mem analysis 3307 // which may limit our maximum vectorization factor, so just return true with 3308 // no restrictions. 3309 return true; 3310} 3311 3312static Type *convertPointerToIntegerType(const DataLayout &DL, Type *Ty) { 3313 if (Ty->isPointerTy()) 3314 return DL.getIntPtrType(Ty); 3315 3316 // It is possible that char's or short's overflow when we ask for the loop's 3317 // trip count, work around this by changing the type size. 3318 if (Ty->getScalarSizeInBits() < 32) 3319 return Type::getInt32Ty(Ty->getContext()); 3320 3321 return Ty; 3322} 3323 3324static Type* getWiderType(const DataLayout &DL, Type *Ty0, Type *Ty1) { 3325 Ty0 = convertPointerToIntegerType(DL, Ty0); 3326 Ty1 = convertPointerToIntegerType(DL, Ty1); 3327 if (Ty0->getScalarSizeInBits() > Ty1->getScalarSizeInBits()) 3328 return Ty0; 3329 return Ty1; 3330} 3331 3332/// \brief Check that the instruction has outside loop users and is not an 3333/// identified reduction variable. 3334static bool hasOutsideLoopUser(const Loop *TheLoop, Instruction *Inst, 3335 SmallPtrSet<Value *, 4> &Reductions) { 3336 // Reduction instructions are allowed to have exit users. All other 3337 // instructions must not have external users. 3338 if (!Reductions.count(Inst)) 3339 //Check that all of the users of the loop are inside the BB. 3340 for (User *U : Inst->users()) { 3341 Instruction *UI = cast<Instruction>(U); 3342 // This user may be a reduction exit value. 3343 if (!TheLoop->contains(UI)) { 3344 DEBUG(dbgs() << "LV: Found an outside user for : " << *UI << '\n'); 3345 return true; 3346 } 3347 } 3348 return false; 3349} 3350 3351bool LoopVectorizationLegality::canVectorizeInstrs() { 3352 BasicBlock *PreHeader = TheLoop->getLoopPreheader(); 3353 BasicBlock *Header = TheLoop->getHeader(); 3354 3355 // Look for the attribute signaling the absence of NaNs. 3356 Function &F = *Header->getParent(); 3357 if (F.hasFnAttribute("no-nans-fp-math")) 3358 HasFunNoNaNAttr = F.getAttributes().getAttribute( 3359 AttributeSet::FunctionIndex, 3360 "no-nans-fp-math").getValueAsString() == "true"; 3361 3362 // For each block in the loop. 3363 for (Loop::block_iterator bb = TheLoop->block_begin(), 3364 be = TheLoop->block_end(); bb != be; ++bb) { 3365 3366 // Scan the instructions in the block and look for hazards. 3367 for (BasicBlock::iterator it = (*bb)->begin(), e = (*bb)->end(); it != e; 3368 ++it) { 3369 3370 if (PHINode *Phi = dyn_cast<PHINode>(it)) { 3371 Type *PhiTy = Phi->getType(); 3372 // Check that this PHI type is allowed. 3373 if (!PhiTy->isIntegerTy() && 3374 !PhiTy->isFloatingPointTy() && 3375 !PhiTy->isPointerTy()) { 3376 DEBUG(dbgs() << "LV: Found an non-int non-pointer PHI.\n"); 3377 return false; 3378 } 3379 3380 // If this PHINode is not in the header block, then we know that we 3381 // can convert it to select during if-conversion. No need to check if 3382 // the PHIs in this block are induction or reduction variables. 3383 if (*bb != Header) { 3384 // Check that this instruction has no outside users or is an 3385 // identified reduction value with an outside user. 3386 if(!hasOutsideLoopUser(TheLoop, it, AllowedExit)) 3387 continue; 3388 return false; 3389 } 3390 3391 // We only allow if-converted PHIs with more than two incoming values. 3392 if (Phi->getNumIncomingValues() != 2) { 3393 DEBUG(dbgs() << "LV: Found an invalid PHI.\n"); 3394 return false; 3395 } 3396 3397 // This is the value coming from the preheader. 3398 Value *StartValue = Phi->getIncomingValueForBlock(PreHeader); 3399 // Check if this is an induction variable. 3400 InductionKind IK = isInductionVariable(Phi); 3401 3402 if (IK_NoInduction != IK) { 3403 // Get the widest type. 3404 if (!WidestIndTy) 3405 WidestIndTy = convertPointerToIntegerType(*DL, PhiTy); 3406 else 3407 WidestIndTy = getWiderType(*DL, PhiTy, WidestIndTy); 3408 3409 // Int inductions are special because we only allow one IV. 3410 if (IK == IK_IntInduction) { 3411 // Use the phi node with the widest type as induction. Use the last 3412 // one if there are multiple (no good reason for doing this other 3413 // than it is expedient). 3414 if (!Induction || PhiTy == WidestIndTy) 3415 Induction = Phi; 3416 } 3417 3418 DEBUG(dbgs() << "LV: Found an induction variable.\n"); 3419 Inductions[Phi] = InductionInfo(StartValue, IK); 3420 3421 // Until we explicitly handle the case of an induction variable with 3422 // an outside loop user we have to give up vectorizing this loop. 3423 if (hasOutsideLoopUser(TheLoop, it, AllowedExit)) 3424 return false; 3425 3426 continue; 3427 } 3428 3429 if (AddReductionVar(Phi, RK_IntegerAdd)) { 3430 DEBUG(dbgs() << "LV: Found an ADD reduction PHI."<< *Phi <<"\n"); 3431 continue; 3432 } 3433 if (AddReductionVar(Phi, RK_IntegerMult)) { 3434 DEBUG(dbgs() << "LV: Found a MUL reduction PHI."<< *Phi <<"\n"); 3435 continue; 3436 } 3437 if (AddReductionVar(Phi, RK_IntegerOr)) { 3438 DEBUG(dbgs() << "LV: Found an OR reduction PHI."<< *Phi <<"\n"); 3439 continue; 3440 } 3441 if (AddReductionVar(Phi, RK_IntegerAnd)) { 3442 DEBUG(dbgs() << "LV: Found an AND reduction PHI."<< *Phi <<"\n"); 3443 continue; 3444 } 3445 if (AddReductionVar(Phi, RK_IntegerXor)) { 3446 DEBUG(dbgs() << "LV: Found a XOR reduction PHI."<< *Phi <<"\n"); 3447 continue; 3448 } 3449 if (AddReductionVar(Phi, RK_IntegerMinMax)) { 3450 DEBUG(dbgs() << "LV: Found a MINMAX reduction PHI."<< *Phi <<"\n"); 3451 continue; 3452 } 3453 if (AddReductionVar(Phi, RK_FloatMult)) { 3454 DEBUG(dbgs() << "LV: Found an FMult reduction PHI."<< *Phi <<"\n"); 3455 continue; 3456 } 3457 if (AddReductionVar(Phi, RK_FloatAdd)) { 3458 DEBUG(dbgs() << "LV: Found an FAdd reduction PHI."<< *Phi <<"\n"); 3459 continue; 3460 } 3461 if (AddReductionVar(Phi, RK_FloatMinMax)) { 3462 DEBUG(dbgs() << "LV: Found an float MINMAX reduction PHI."<< *Phi << 3463 "\n"); 3464 continue; 3465 } 3466 3467 DEBUG(dbgs() << "LV: Found an unidentified PHI."<< *Phi <<"\n"); 3468 return false; 3469 }// end of PHI handling 3470 3471 // We still don't handle functions. However, we can ignore dbg intrinsic 3472 // calls and we do handle certain intrinsic and libm functions. 3473 CallInst *CI = dyn_cast<CallInst>(it); 3474 if (CI && !getIntrinsicIDForCall(CI, TLI) && !isa<DbgInfoIntrinsic>(CI)) { 3475 DEBUG(dbgs() << "LV: Found a call site.\n"); 3476 return false; 3477 } 3478 3479 // Check that the instruction return type is vectorizable. 3480 // Also, we can't vectorize extractelement instructions. 3481 if ((!VectorType::isValidElementType(it->getType()) && 3482 !it->getType()->isVoidTy()) || isa<ExtractElementInst>(it)) { 3483 DEBUG(dbgs() << "LV: Found unvectorizable type.\n"); 3484 return false; 3485 } 3486 3487 // Check that the stored type is vectorizable. 3488 if (StoreInst *ST = dyn_cast<StoreInst>(it)) { 3489 Type *T = ST->getValueOperand()->getType(); 3490 if (!VectorType::isValidElementType(T)) 3491 return false; 3492 if (EnableMemAccessVersioning) 3493 collectStridedAcccess(ST); 3494 } 3495 3496 if (EnableMemAccessVersioning) 3497 if (LoadInst *LI = dyn_cast<LoadInst>(it)) 3498 collectStridedAcccess(LI); 3499 3500 // Reduction instructions are allowed to have exit users. 3501 // All other instructions must not have external users. 3502 if (hasOutsideLoopUser(TheLoop, it, AllowedExit)) 3503 return false; 3504 3505 } // next instr. 3506 3507 } 3508 3509 if (!Induction) { 3510 DEBUG(dbgs() << "LV: Did not find one integer induction var.\n"); 3511 if (Inductions.empty()) 3512 return false; 3513 } 3514 3515 return true; 3516} 3517 3518///\brief Remove GEPs whose indices but the last one are loop invariant and 3519/// return the induction operand of the gep pointer. 3520static Value *stripGetElementPtr(Value *Ptr, ScalarEvolution *SE, 3521 const DataLayout *DL, Loop *Lp) { 3522 GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Ptr); 3523 if (!GEP) 3524 return Ptr; 3525 3526 unsigned InductionOperand = getGEPInductionOperand(DL, GEP); 3527 3528 // Check that all of the gep indices are uniform except for our induction 3529 // operand. 3530 for (unsigned i = 0, e = GEP->getNumOperands(); i != e; ++i) 3531 if (i != InductionOperand && 3532 !SE->isLoopInvariant(SE->getSCEV(GEP->getOperand(i)), Lp)) 3533 return Ptr; 3534 return GEP->getOperand(InductionOperand); 3535} 3536 3537///\brief Look for a cast use of the passed value. 3538static Value *getUniqueCastUse(Value *Ptr, Loop *Lp, Type *Ty) { 3539 Value *UniqueCast = 0; 3540 for (User *U : Ptr->users()) { 3541 CastInst *CI = dyn_cast<CastInst>(U); 3542 if (CI && CI->getType() == Ty) { 3543 if (!UniqueCast) 3544 UniqueCast = CI; 3545 else 3546 return 0; 3547 } 3548 } 3549 return UniqueCast; 3550} 3551 3552///\brief Get the stride of a pointer access in a loop. 3553/// Looks for symbolic strides "a[i*stride]". Returns the symbolic stride as a 3554/// pointer to the Value, or null otherwise. 3555static Value *getStrideFromPointer(Value *Ptr, ScalarEvolution *SE, 3556 const DataLayout *DL, Loop *Lp) { 3557 const PointerType *PtrTy = dyn_cast<PointerType>(Ptr->getType()); 3558 if (!PtrTy || PtrTy->isAggregateType()) 3559 return 0; 3560 3561 // Try to remove a gep instruction to make the pointer (actually index at this 3562 // point) easier analyzable. If OrigPtr is equal to Ptr we are analzying the 3563 // pointer, otherwise, we are analyzing the index. 3564 Value *OrigPtr = Ptr; 3565 3566 // The size of the pointer access. 3567 int64_t PtrAccessSize = 1; 3568 3569 Ptr = stripGetElementPtr(Ptr, SE, DL, Lp); 3570 const SCEV *V = SE->getSCEV(Ptr); 3571 3572 if (Ptr != OrigPtr) 3573 // Strip off casts. 3574 while (const SCEVCastExpr *C = dyn_cast<SCEVCastExpr>(V)) 3575 V = C->getOperand(); 3576 3577 const SCEVAddRecExpr *S = dyn_cast<SCEVAddRecExpr>(V); 3578 if (!S) 3579 return 0; 3580 3581 V = S->getStepRecurrence(*SE); 3582 if (!V) 3583 return 0; 3584 3585 // Strip off the size of access multiplication if we are still analyzing the 3586 // pointer. 3587 if (OrigPtr == Ptr) { 3588 DL->getTypeAllocSize(PtrTy->getElementType()); 3589 if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(V)) { 3590 if (M->getOperand(0)->getSCEVType() != scConstant) 3591 return 0; 3592 3593 const APInt &APStepVal = 3594 cast<SCEVConstant>(M->getOperand(0))->getValue()->getValue(); 3595 3596 // Huge step value - give up. 3597 if (APStepVal.getBitWidth() > 64) 3598 return 0; 3599 3600 int64_t StepVal = APStepVal.getSExtValue(); 3601 if (PtrAccessSize != StepVal) 3602 return 0; 3603 V = M->getOperand(1); 3604 } 3605 } 3606 3607 // Strip off casts. 3608 Type *StripedOffRecurrenceCast = 0; 3609 if (const SCEVCastExpr *C = dyn_cast<SCEVCastExpr>(V)) { 3610 StripedOffRecurrenceCast = C->getType(); 3611 V = C->getOperand(); 3612 } 3613 3614 // Look for the loop invariant symbolic value. 3615 const SCEVUnknown *U = dyn_cast<SCEVUnknown>(V); 3616 if (!U) 3617 return 0; 3618 3619 Value *Stride = U->getValue(); 3620 if (!Lp->isLoopInvariant(Stride)) 3621 return 0; 3622 3623 // If we have stripped off the recurrence cast we have to make sure that we 3624 // return the value that is used in this loop so that we can replace it later. 3625 if (StripedOffRecurrenceCast) 3626 Stride = getUniqueCastUse(Stride, Lp, StripedOffRecurrenceCast); 3627 3628 return Stride; 3629} 3630 3631void LoopVectorizationLegality::collectStridedAcccess(Value *MemAccess) { 3632 Value *Ptr = 0; 3633 if (LoadInst *LI = dyn_cast<LoadInst>(MemAccess)) 3634 Ptr = LI->getPointerOperand(); 3635 else if (StoreInst *SI = dyn_cast<StoreInst>(MemAccess)) 3636 Ptr = SI->getPointerOperand(); 3637 else 3638 return; 3639 3640 Value *Stride = getStrideFromPointer(Ptr, SE, DL, TheLoop); 3641 if (!Stride) 3642 return; 3643 3644 DEBUG(dbgs() << "LV: Found a strided access that we can version"); 3645 DEBUG(dbgs() << " Ptr: " << *Ptr << " Stride: " << *Stride << "\n"); 3646 Strides[Ptr] = Stride; 3647 StrideSet.insert(Stride); 3648} 3649 3650void LoopVectorizationLegality::collectLoopUniforms() { 3651 // We now know that the loop is vectorizable! 3652 // Collect variables that will remain uniform after vectorization. 3653 std::vector<Value*> Worklist; 3654 BasicBlock *Latch = TheLoop->getLoopLatch(); 3655 3656 // Start with the conditional branch and walk up the block. 3657 Worklist.push_back(Latch->getTerminator()->getOperand(0)); 3658 3659 // Also add all consecutive pointer values; these values will be uniform 3660 // after vectorization (and subsequent cleanup) and, until revectorization is 3661 // supported, all dependencies must also be uniform. 3662 for (Loop::block_iterator B = TheLoop->block_begin(), 3663 BE = TheLoop->block_end(); B != BE; ++B) 3664 for (BasicBlock::iterator I = (*B)->begin(), IE = (*B)->end(); 3665 I != IE; ++I) 3666 if (I->getType()->isPointerTy() && isConsecutivePtr(I)) 3667 Worklist.insert(Worklist.end(), I->op_begin(), I->op_end()); 3668 3669 while (Worklist.size()) { 3670 Instruction *I = dyn_cast<Instruction>(Worklist.back()); 3671 Worklist.pop_back(); 3672 3673 // Look at instructions inside this loop. 3674 // Stop when reaching PHI nodes. 3675 // TODO: we need to follow values all over the loop, not only in this block. 3676 if (!I || !TheLoop->contains(I) || isa<PHINode>(I)) 3677 continue; 3678 3679 // This is a known uniform. 3680 Uniforms.insert(I); 3681 3682 // Insert all operands. 3683 Worklist.insert(Worklist.end(), I->op_begin(), I->op_end()); 3684 } 3685} 3686 3687namespace { 3688/// \brief Analyses memory accesses in a loop. 3689/// 3690/// Checks whether run time pointer checks are needed and builds sets for data 3691/// dependence checking. 3692class AccessAnalysis { 3693public: 3694 /// \brief Read or write access location. 3695 typedef PointerIntPair<Value *, 1, bool> MemAccessInfo; 3696 typedef SmallPtrSet<MemAccessInfo, 8> MemAccessInfoSet; 3697 3698 /// \brief Set of potential dependent memory accesses. 3699 typedef EquivalenceClasses<MemAccessInfo> DepCandidates; 3700 3701 AccessAnalysis(const DataLayout *Dl, DepCandidates &DA) : 3702 DL(Dl), DepCands(DA), AreAllWritesIdentified(true), 3703 AreAllReadsIdentified(true), IsRTCheckNeeded(false) {} 3704 3705 /// \brief Register a load and whether it is only read from. 3706 void addLoad(Value *Ptr, bool IsReadOnly) { 3707 Accesses.insert(MemAccessInfo(Ptr, false)); 3708 if (IsReadOnly) 3709 ReadOnlyPtr.insert(Ptr); 3710 } 3711 3712 /// \brief Register a store. 3713 void addStore(Value *Ptr) { 3714 Accesses.insert(MemAccessInfo(Ptr, true)); 3715 } 3716 3717 /// \brief Check whether we can check the pointers at runtime for 3718 /// non-intersection. 3719 bool canCheckPtrAtRT(LoopVectorizationLegality::RuntimePointerCheck &RtCheck, 3720 unsigned &NumComparisons, ScalarEvolution *SE, 3721 Loop *TheLoop, ValueToValueMap &Strides, 3722 bool ShouldCheckStride = false); 3723 3724 /// \brief Goes over all memory accesses, checks whether a RT check is needed 3725 /// and builds sets of dependent accesses. 3726 void buildDependenceSets() { 3727 // Process read-write pointers first. 3728 processMemAccesses(false); 3729 // Next, process read pointers. 3730 processMemAccesses(true); 3731 } 3732 3733 bool isRTCheckNeeded() { return IsRTCheckNeeded; } 3734 3735 bool isDependencyCheckNeeded() { return !CheckDeps.empty(); } 3736 void resetDepChecks() { CheckDeps.clear(); } 3737 3738 MemAccessInfoSet &getDependenciesToCheck() { return CheckDeps; } 3739 3740private: 3741 typedef SetVector<MemAccessInfo> PtrAccessSet; 3742 typedef DenseMap<Value*, MemAccessInfo> UnderlyingObjToAccessMap; 3743 3744 /// \brief Go over all memory access or only the deferred ones if 3745 /// \p UseDeferred is true and check whether runtime pointer checks are needed 3746 /// and build sets of dependency check candidates. 3747 void processMemAccesses(bool UseDeferred); 3748 3749 /// Set of all accesses. 3750 PtrAccessSet Accesses; 3751 3752 /// Set of access to check after all writes have been processed. 3753 PtrAccessSet DeferredAccesses; 3754 3755 /// Map of pointers to last access encountered. 3756 UnderlyingObjToAccessMap ObjToLastAccess; 3757 3758 /// Set of accesses that need a further dependence check. 3759 MemAccessInfoSet CheckDeps; 3760 3761 /// Set of pointers that are read only. 3762 SmallPtrSet<Value*, 16> ReadOnlyPtr; 3763 3764 /// Set of underlying objects already written to. 3765 SmallPtrSet<Value*, 16> WriteObjects; 3766 3767 const DataLayout *DL; 3768 3769 /// Sets of potentially dependent accesses - members of one set share an 3770 /// underlying pointer. The set "CheckDeps" identfies which sets really need a 3771 /// dependence check. 3772 DepCandidates &DepCands; 3773 3774 bool AreAllWritesIdentified; 3775 bool AreAllReadsIdentified; 3776 bool IsRTCheckNeeded; 3777}; 3778 3779} // end anonymous namespace 3780 3781/// \brief Check whether a pointer can participate in a runtime bounds check. 3782static bool hasComputableBounds(ScalarEvolution *SE, ValueToValueMap &Strides, 3783 Value *Ptr) { 3784 const SCEV *PtrScev = replaceSymbolicStrideSCEV(SE, Strides, Ptr); 3785 const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(PtrScev); 3786 if (!AR) 3787 return false; 3788 3789 return AR->isAffine(); 3790} 3791 3792/// \brief Check the stride of the pointer and ensure that it does not wrap in 3793/// the address space. 3794static int isStridedPtr(ScalarEvolution *SE, const DataLayout *DL, Value *Ptr, 3795 const Loop *Lp, ValueToValueMap &StridesMap); 3796 3797bool AccessAnalysis::canCheckPtrAtRT( 3798 LoopVectorizationLegality::RuntimePointerCheck &RtCheck, 3799 unsigned &NumComparisons, ScalarEvolution *SE, Loop *TheLoop, 3800 ValueToValueMap &StridesMap, bool ShouldCheckStride) { 3801 // Find pointers with computable bounds. We are going to use this information 3802 // to place a runtime bound check. 3803 unsigned NumReadPtrChecks = 0; 3804 unsigned NumWritePtrChecks = 0; 3805 bool CanDoRT = true; 3806 3807 bool IsDepCheckNeeded = isDependencyCheckNeeded(); 3808 // We assign consecutive id to access from different dependence sets. 3809 // Accesses within the same set don't need a runtime check. 3810 unsigned RunningDepId = 1; 3811 DenseMap<Value *, unsigned> DepSetId; 3812 3813 for (PtrAccessSet::iterator AI = Accesses.begin(), AE = Accesses.end(); 3814 AI != AE; ++AI) { 3815 const MemAccessInfo &Access = *AI; 3816 Value *Ptr = Access.getPointer(); 3817 bool IsWrite = Access.getInt(); 3818 3819 // Just add write checks if we have both. 3820 if (!IsWrite && Accesses.count(MemAccessInfo(Ptr, true))) 3821 continue; 3822 3823 if (IsWrite) 3824 ++NumWritePtrChecks; 3825 else 3826 ++NumReadPtrChecks; 3827 3828 if (hasComputableBounds(SE, StridesMap, Ptr) && 3829 // When we run after a failing dependency check we have to make sure we 3830 // don't have wrapping pointers. 3831 (!ShouldCheckStride || 3832 isStridedPtr(SE, DL, Ptr, TheLoop, StridesMap) == 1)) { 3833 // The id of the dependence set. 3834 unsigned DepId; 3835 3836 if (IsDepCheckNeeded) { 3837 Value *Leader = DepCands.getLeaderValue(Access).getPointer(); 3838 unsigned &LeaderId = DepSetId[Leader]; 3839 if (!LeaderId) 3840 LeaderId = RunningDepId++; 3841 DepId = LeaderId; 3842 } else 3843 // Each access has its own dependence set. 3844 DepId = RunningDepId++; 3845 3846 RtCheck.insert(SE, TheLoop, Ptr, IsWrite, DepId, StridesMap); 3847 3848 DEBUG(dbgs() << "LV: Found a runtime check ptr:" << *Ptr << '\n'); 3849 } else { 3850 CanDoRT = false; 3851 } 3852 } 3853 3854 if (IsDepCheckNeeded && CanDoRT && RunningDepId == 2) 3855 NumComparisons = 0; // Only one dependence set. 3856 else { 3857 NumComparisons = (NumWritePtrChecks * (NumReadPtrChecks + 3858 NumWritePtrChecks - 1)); 3859 } 3860 3861 // If the pointers that we would use for the bounds comparison have different 3862 // address spaces, assume the values aren't directly comparable, so we can't 3863 // use them for the runtime check. We also have to assume they could 3864 // overlap. In the future there should be metadata for whether address spaces 3865 // are disjoint. 3866 unsigned NumPointers = RtCheck.Pointers.size(); 3867 for (unsigned i = 0; i < NumPointers; ++i) { 3868 for (unsigned j = i + 1; j < NumPointers; ++j) { 3869 // Only need to check pointers between two different dependency sets. 3870 if (RtCheck.DependencySetId[i] == RtCheck.DependencySetId[j]) 3871 continue; 3872 3873 Value *PtrI = RtCheck.Pointers[i]; 3874 Value *PtrJ = RtCheck.Pointers[j]; 3875 3876 unsigned ASi = PtrI->getType()->getPointerAddressSpace(); 3877 unsigned ASj = PtrJ->getType()->getPointerAddressSpace(); 3878 if (ASi != ASj) { 3879 DEBUG(dbgs() << "LV: Runtime check would require comparison between" 3880 " different address spaces\n"); 3881 return false; 3882 } 3883 } 3884 } 3885 3886 return CanDoRT; 3887} 3888 3889static bool isFunctionScopeIdentifiedObject(Value *Ptr) { 3890 return isNoAliasArgument(Ptr) || isNoAliasCall(Ptr) || isa<AllocaInst>(Ptr); 3891} 3892 3893void AccessAnalysis::processMemAccesses(bool UseDeferred) { 3894 // We process the set twice: first we process read-write pointers, last we 3895 // process read-only pointers. This allows us to skip dependence tests for 3896 // read-only pointers. 3897 3898 PtrAccessSet &S = UseDeferred ? DeferredAccesses : Accesses; 3899 for (PtrAccessSet::iterator AI = S.begin(), AE = S.end(); AI != AE; ++AI) { 3900 const MemAccessInfo &Access = *AI; 3901 Value *Ptr = Access.getPointer(); 3902 bool IsWrite = Access.getInt(); 3903 3904 DepCands.insert(Access); 3905 3906 // Memorize read-only pointers for later processing and skip them in the 3907 // first round (they need to be checked after we have seen all write 3908 // pointers). Note: we also mark pointer that are not consecutive as 3909 // "read-only" pointers (so that we check "a[b[i]] +="). Hence, we need the 3910 // second check for "!IsWrite". 3911 bool IsReadOnlyPtr = ReadOnlyPtr.count(Ptr) && !IsWrite; 3912 if (!UseDeferred && IsReadOnlyPtr) { 3913 DeferredAccesses.insert(Access); 3914 continue; 3915 } 3916 3917 bool NeedDepCheck = false; 3918 // Check whether there is the possibility of dependency because of 3919 // underlying objects being the same. 3920 typedef SmallVector<Value*, 16> ValueVector; 3921 ValueVector TempObjects; 3922 GetUnderlyingObjects(Ptr, TempObjects, DL); 3923 for (ValueVector::iterator UI = TempObjects.begin(), UE = TempObjects.end(); 3924 UI != UE; ++UI) { 3925 Value *UnderlyingObj = *UI; 3926 3927 // If this is a write then it needs to be an identified object. If this a 3928 // read and all writes (so far) are identified function scope objects we 3929 // don't need an identified underlying object but only an Argument (the 3930 // next write is going to invalidate this assumption if it is 3931 // unidentified). 3932 // This is a micro-optimization for the case where all writes are 3933 // identified and we have one argument pointer. 3934 // Otherwise, we do need a runtime check. 3935 if ((IsWrite && !isFunctionScopeIdentifiedObject(UnderlyingObj)) || 3936 (!IsWrite && (!AreAllWritesIdentified || 3937 !isa<Argument>(UnderlyingObj)) && 3938 !isIdentifiedObject(UnderlyingObj))) { 3939 DEBUG(dbgs() << "LV: Found an unidentified " << 3940 (IsWrite ? "write" : "read" ) << " ptr: " << *UnderlyingObj << 3941 "\n"); 3942 IsRTCheckNeeded = (IsRTCheckNeeded || 3943 !isIdentifiedObject(UnderlyingObj) || 3944 !AreAllReadsIdentified); 3945 3946 if (IsWrite) 3947 AreAllWritesIdentified = false; 3948 if (!IsWrite) 3949 AreAllReadsIdentified = false; 3950 } 3951 3952 // If this is a write - check other reads and writes for conflicts. If 3953 // this is a read only check other writes for conflicts (but only if there 3954 // is no other write to the ptr - this is an optimization to catch "a[i] = 3955 // a[i] + " without having to do a dependence check). 3956 if ((IsWrite || IsReadOnlyPtr) && WriteObjects.count(UnderlyingObj)) 3957 NeedDepCheck = true; 3958 3959 if (IsWrite) 3960 WriteObjects.insert(UnderlyingObj); 3961 3962 // Create sets of pointers connected by shared underlying objects. 3963 UnderlyingObjToAccessMap::iterator Prev = 3964 ObjToLastAccess.find(UnderlyingObj); 3965 if (Prev != ObjToLastAccess.end()) 3966 DepCands.unionSets(Access, Prev->second); 3967 3968 ObjToLastAccess[UnderlyingObj] = Access; 3969 } 3970 3971 if (NeedDepCheck) 3972 CheckDeps.insert(Access); 3973 } 3974} 3975 3976namespace { 3977/// \brief Checks memory dependences among accesses to the same underlying 3978/// object to determine whether there vectorization is legal or not (and at 3979/// which vectorization factor). 3980/// 3981/// This class works under the assumption that we already checked that memory 3982/// locations with different underlying pointers are "must-not alias". 3983/// We use the ScalarEvolution framework to symbolically evalutate access 3984/// functions pairs. Since we currently don't restructure the loop we can rely 3985/// on the program order of memory accesses to determine their safety. 3986/// At the moment we will only deem accesses as safe for: 3987/// * A negative constant distance assuming program order. 3988/// 3989/// Safe: tmp = a[i + 1]; OR a[i + 1] = x; 3990/// a[i] = tmp; y = a[i]; 3991/// 3992/// The latter case is safe because later checks guarantuee that there can't 3993/// be a cycle through a phi node (that is, we check that "x" and "y" is not 3994/// the same variable: a header phi can only be an induction or a reduction, a 3995/// reduction can't have a memory sink, an induction can't have a memory 3996/// source). This is important and must not be violated (or we have to 3997/// resort to checking for cycles through memory). 3998/// 3999/// * A positive constant distance assuming program order that is bigger 4000/// than the biggest memory access. 4001/// 4002/// tmp = a[i] OR b[i] = x 4003/// a[i+2] = tmp y = b[i+2]; 4004/// 4005/// Safe distance: 2 x sizeof(a[0]), and 2 x sizeof(b[0]), respectively. 4006/// 4007/// * Zero distances and all accesses have the same size. 4008/// 4009class MemoryDepChecker { 4010public: 4011 typedef PointerIntPair<Value *, 1, bool> MemAccessInfo; 4012 typedef SmallPtrSet<MemAccessInfo, 8> MemAccessInfoSet; 4013 4014 MemoryDepChecker(ScalarEvolution *Se, const DataLayout *Dl, const Loop *L) 4015 : SE(Se), DL(Dl), InnermostLoop(L), AccessIdx(0), 4016 ShouldRetryWithRuntimeCheck(false) {} 4017 4018 /// \brief Register the location (instructions are given increasing numbers) 4019 /// of a write access. 4020 void addAccess(StoreInst *SI) { 4021 Value *Ptr = SI->getPointerOperand(); 4022 Accesses[MemAccessInfo(Ptr, true)].push_back(AccessIdx); 4023 InstMap.push_back(SI); 4024 ++AccessIdx; 4025 } 4026 4027 /// \brief Register the location (instructions are given increasing numbers) 4028 /// of a write access. 4029 void addAccess(LoadInst *LI) { 4030 Value *Ptr = LI->getPointerOperand(); 4031 Accesses[MemAccessInfo(Ptr, false)].push_back(AccessIdx); 4032 InstMap.push_back(LI); 4033 ++AccessIdx; 4034 } 4035 4036 /// \brief Check whether the dependencies between the accesses are safe. 4037 /// 4038 /// Only checks sets with elements in \p CheckDeps. 4039 bool areDepsSafe(AccessAnalysis::DepCandidates &AccessSets, 4040 MemAccessInfoSet &CheckDeps, ValueToValueMap &Strides); 4041 4042 /// \brief The maximum number of bytes of a vector register we can vectorize 4043 /// the accesses safely with. 4044 unsigned getMaxSafeDepDistBytes() { return MaxSafeDepDistBytes; } 4045 4046 /// \brief In same cases when the dependency check fails we can still 4047 /// vectorize the loop with a dynamic array access check. 4048 bool shouldRetryWithRuntimeCheck() { return ShouldRetryWithRuntimeCheck; } 4049 4050private: 4051 ScalarEvolution *SE; 4052 const DataLayout *DL; 4053 const Loop *InnermostLoop; 4054 4055 /// \brief Maps access locations (ptr, read/write) to program order. 4056 DenseMap<MemAccessInfo, std::vector<unsigned> > Accesses; 4057 4058 /// \brief Memory access instructions in program order. 4059 SmallVector<Instruction *, 16> InstMap; 4060 4061 /// \brief The program order index to be used for the next instruction. 4062 unsigned AccessIdx; 4063 4064 // We can access this many bytes in parallel safely. 4065 unsigned MaxSafeDepDistBytes; 4066 4067 /// \brief If we see a non-constant dependence distance we can still try to 4068 /// vectorize this loop with runtime checks. 4069 bool ShouldRetryWithRuntimeCheck; 4070 4071 /// \brief Check whether there is a plausible dependence between the two 4072 /// accesses. 4073 /// 4074 /// Access \p A must happen before \p B in program order. The two indices 4075 /// identify the index into the program order map. 4076 /// 4077 /// This function checks whether there is a plausible dependence (or the 4078 /// absence of such can't be proved) between the two accesses. If there is a 4079 /// plausible dependence but the dependence distance is bigger than one 4080 /// element access it records this distance in \p MaxSafeDepDistBytes (if this 4081 /// distance is smaller than any other distance encountered so far). 4082 /// Otherwise, this function returns true signaling a possible dependence. 4083 bool isDependent(const MemAccessInfo &A, unsigned AIdx, 4084 const MemAccessInfo &B, unsigned BIdx, 4085 ValueToValueMap &Strides); 4086 4087 /// \brief Check whether the data dependence could prevent store-load 4088 /// forwarding. 4089 bool couldPreventStoreLoadForward(unsigned Distance, unsigned TypeByteSize); 4090}; 4091 4092} // end anonymous namespace 4093 4094static bool isInBoundsGep(Value *Ptr) { 4095 if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Ptr)) 4096 return GEP->isInBounds(); 4097 return false; 4098} 4099 4100/// \brief Check whether the access through \p Ptr has a constant stride. 4101static int isStridedPtr(ScalarEvolution *SE, const DataLayout *DL, Value *Ptr, 4102 const Loop *Lp, ValueToValueMap &StridesMap) { 4103 const Type *Ty = Ptr->getType(); 4104 assert(Ty->isPointerTy() && "Unexpected non-ptr"); 4105 4106 // Make sure that the pointer does not point to aggregate types. 4107 const PointerType *PtrTy = cast<PointerType>(Ty); 4108 if (PtrTy->getElementType()->isAggregateType()) { 4109 DEBUG(dbgs() << "LV: Bad stride - Not a pointer to a scalar type" << *Ptr << 4110 "\n"); 4111 return 0; 4112 } 4113 4114 const SCEV *PtrScev = replaceSymbolicStrideSCEV(SE, StridesMap, Ptr); 4115 4116 const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(PtrScev); 4117 if (!AR) { 4118 DEBUG(dbgs() << "LV: Bad stride - Not an AddRecExpr pointer " 4119 << *Ptr << " SCEV: " << *PtrScev << "\n"); 4120 return 0; 4121 } 4122 4123 // The accesss function must stride over the innermost loop. 4124 if (Lp != AR->getLoop()) { 4125 DEBUG(dbgs() << "LV: Bad stride - Not striding over innermost loop " << 4126 *Ptr << " SCEV: " << *PtrScev << "\n"); 4127 } 4128 4129 // The address calculation must not wrap. Otherwise, a dependence could be 4130 // inverted. 4131 // An inbounds getelementptr that is a AddRec with a unit stride 4132 // cannot wrap per definition. The unit stride requirement is checked later. 4133 // An getelementptr without an inbounds attribute and unit stride would have 4134 // to access the pointer value "0" which is undefined behavior in address 4135 // space 0, therefore we can also vectorize this case. 4136 bool IsInBoundsGEP = isInBoundsGep(Ptr); 4137 bool IsNoWrapAddRec = AR->getNoWrapFlags(SCEV::NoWrapMask); 4138 bool IsInAddressSpaceZero = PtrTy->getAddressSpace() == 0; 4139 if (!IsNoWrapAddRec && !IsInBoundsGEP && !IsInAddressSpaceZero) { 4140 DEBUG(dbgs() << "LV: Bad stride - Pointer may wrap in the address space " 4141 << *Ptr << " SCEV: " << *PtrScev << "\n"); 4142 return 0; 4143 } 4144 4145 // Check the step is constant. 4146 const SCEV *Step = AR->getStepRecurrence(*SE); 4147 4148 // Calculate the pointer stride and check if it is consecutive. 4149 const SCEVConstant *C = dyn_cast<SCEVConstant>(Step); 4150 if (!C) { 4151 DEBUG(dbgs() << "LV: Bad stride - Not a constant strided " << *Ptr << 4152 " SCEV: " << *PtrScev << "\n"); 4153 return 0; 4154 } 4155 4156 int64_t Size = DL->getTypeAllocSize(PtrTy->getElementType()); 4157 const APInt &APStepVal = C->getValue()->getValue(); 4158 4159 // Huge step value - give up. 4160 if (APStepVal.getBitWidth() > 64) 4161 return 0; 4162 4163 int64_t StepVal = APStepVal.getSExtValue(); 4164 4165 // Strided access. 4166 int64_t Stride = StepVal / Size; 4167 int64_t Rem = StepVal % Size; 4168 if (Rem) 4169 return 0; 4170 4171 // If the SCEV could wrap but we have an inbounds gep with a unit stride we 4172 // know we can't "wrap around the address space". In case of address space 4173 // zero we know that this won't happen without triggering undefined behavior. 4174 if (!IsNoWrapAddRec && (IsInBoundsGEP || IsInAddressSpaceZero) && 4175 Stride != 1 && Stride != -1) 4176 return 0; 4177 4178 return Stride; 4179} 4180 4181bool MemoryDepChecker::couldPreventStoreLoadForward(unsigned Distance, 4182 unsigned TypeByteSize) { 4183 // If loads occur at a distance that is not a multiple of a feasible vector 4184 // factor store-load forwarding does not take place. 4185 // Positive dependences might cause troubles because vectorizing them might 4186 // prevent store-load forwarding making vectorized code run a lot slower. 4187 // a[i] = a[i-3] ^ a[i-8]; 4188 // The stores to a[i:i+1] don't align with the stores to a[i-3:i-2] and 4189 // hence on your typical architecture store-load forwarding does not take 4190 // place. Vectorizing in such cases does not make sense. 4191 // Store-load forwarding distance. 4192 const unsigned NumCyclesForStoreLoadThroughMemory = 8*TypeByteSize; 4193 // Maximum vector factor. 4194 unsigned MaxVFWithoutSLForwardIssues = MaxVectorWidth*TypeByteSize; 4195 if(MaxSafeDepDistBytes < MaxVFWithoutSLForwardIssues) 4196 MaxVFWithoutSLForwardIssues = MaxSafeDepDistBytes; 4197 4198 for (unsigned vf = 2*TypeByteSize; vf <= MaxVFWithoutSLForwardIssues; 4199 vf *= 2) { 4200 if (Distance % vf && Distance / vf < NumCyclesForStoreLoadThroughMemory) { 4201 MaxVFWithoutSLForwardIssues = (vf >>=1); 4202 break; 4203 } 4204 } 4205 4206 if (MaxVFWithoutSLForwardIssues< 2*TypeByteSize) { 4207 DEBUG(dbgs() << "LV: Distance " << Distance << 4208 " that could cause a store-load forwarding conflict\n"); 4209 return true; 4210 } 4211 4212 if (MaxVFWithoutSLForwardIssues < MaxSafeDepDistBytes && 4213 MaxVFWithoutSLForwardIssues != MaxVectorWidth*TypeByteSize) 4214 MaxSafeDepDistBytes = MaxVFWithoutSLForwardIssues; 4215 return false; 4216} 4217 4218bool MemoryDepChecker::isDependent(const MemAccessInfo &A, unsigned AIdx, 4219 const MemAccessInfo &B, unsigned BIdx, 4220 ValueToValueMap &Strides) { 4221 assert (AIdx < BIdx && "Must pass arguments in program order"); 4222 4223 Value *APtr = A.getPointer(); 4224 Value *BPtr = B.getPointer(); 4225 bool AIsWrite = A.getInt(); 4226 bool BIsWrite = B.getInt(); 4227 4228 // Two reads are independent. 4229 if (!AIsWrite && !BIsWrite) 4230 return false; 4231 4232 const SCEV *AScev = replaceSymbolicStrideSCEV(SE, Strides, APtr); 4233 const SCEV *BScev = replaceSymbolicStrideSCEV(SE, Strides, BPtr); 4234 4235 int StrideAPtr = isStridedPtr(SE, DL, APtr, InnermostLoop, Strides); 4236 int StrideBPtr = isStridedPtr(SE, DL, BPtr, InnermostLoop, Strides); 4237 4238 const SCEV *Src = AScev; 4239 const SCEV *Sink = BScev; 4240 4241 // If the induction step is negative we have to invert source and sink of the 4242 // dependence. 4243 if (StrideAPtr < 0) { 4244 //Src = BScev; 4245 //Sink = AScev; 4246 std::swap(APtr, BPtr); 4247 std::swap(Src, Sink); 4248 std::swap(AIsWrite, BIsWrite); 4249 std::swap(AIdx, BIdx); 4250 std::swap(StrideAPtr, StrideBPtr); 4251 } 4252 4253 const SCEV *Dist = SE->getMinusSCEV(Sink, Src); 4254 4255 DEBUG(dbgs() << "LV: Src Scev: " << *Src << "Sink Scev: " << *Sink 4256 << "(Induction step: " << StrideAPtr << ")\n"); 4257 DEBUG(dbgs() << "LV: Distance for " << *InstMap[AIdx] << " to " 4258 << *InstMap[BIdx] << ": " << *Dist << "\n"); 4259 4260 // Need consecutive accesses. We don't want to vectorize 4261 // "A[B[i]] += ..." and similar code or pointer arithmetic that could wrap in 4262 // the address space. 4263 if (!StrideAPtr || !StrideBPtr || StrideAPtr != StrideBPtr){ 4264 DEBUG(dbgs() << "Non-consecutive pointer access\n"); 4265 return true; 4266 } 4267 4268 const SCEVConstant *C = dyn_cast<SCEVConstant>(Dist); 4269 if (!C) { 4270 DEBUG(dbgs() << "LV: Dependence because of non-constant distance\n"); 4271 ShouldRetryWithRuntimeCheck = true; 4272 return true; 4273 } 4274 4275 Type *ATy = APtr->getType()->getPointerElementType(); 4276 Type *BTy = BPtr->getType()->getPointerElementType(); 4277 unsigned TypeByteSize = DL->getTypeAllocSize(ATy); 4278 4279 // Negative distances are not plausible dependencies. 4280 const APInt &Val = C->getValue()->getValue(); 4281 if (Val.isNegative()) { 4282 bool IsTrueDataDependence = (AIsWrite && !BIsWrite); 4283 if (IsTrueDataDependence && 4284 (couldPreventStoreLoadForward(Val.abs().getZExtValue(), TypeByteSize) || 4285 ATy != BTy)) 4286 return true; 4287 4288 DEBUG(dbgs() << "LV: Dependence is negative: NoDep\n"); 4289 return false; 4290 } 4291 4292 // Write to the same location with the same size. 4293 // Could be improved to assert type sizes are the same (i32 == float, etc). 4294 if (Val == 0) { 4295 if (ATy == BTy) 4296 return false; 4297 DEBUG(dbgs() << "LV: Zero dependence difference but different types\n"); 4298 return true; 4299 } 4300 4301 assert(Val.isStrictlyPositive() && "Expect a positive value"); 4302 4303 // Positive distance bigger than max vectorization factor. 4304 if (ATy != BTy) { 4305 DEBUG(dbgs() << 4306 "LV: ReadWrite-Write positive dependency with different types\n"); 4307 return false; 4308 } 4309 4310 unsigned Distance = (unsigned) Val.getZExtValue(); 4311 4312 // Bail out early if passed-in parameters make vectorization not feasible. 4313 unsigned ForcedFactor = VectorizationFactor ? VectorizationFactor : 1; 4314 unsigned ForcedUnroll = VectorizationUnroll ? VectorizationUnroll : 1; 4315 4316 // The distance must be bigger than the size needed for a vectorized version 4317 // of the operation and the size of the vectorized operation must not be 4318 // bigger than the currrent maximum size. 4319 if (Distance < 2*TypeByteSize || 4320 2*TypeByteSize > MaxSafeDepDistBytes || 4321 Distance < TypeByteSize * ForcedUnroll * ForcedFactor) { 4322 DEBUG(dbgs() << "LV: Failure because of Positive distance " 4323 << Val.getSExtValue() << '\n'); 4324 return true; 4325 } 4326 4327 MaxSafeDepDistBytes = Distance < MaxSafeDepDistBytes ? 4328 Distance : MaxSafeDepDistBytes; 4329 4330 bool IsTrueDataDependence = (!AIsWrite && BIsWrite); 4331 if (IsTrueDataDependence && 4332 couldPreventStoreLoadForward(Distance, TypeByteSize)) 4333 return true; 4334 4335 DEBUG(dbgs() << "LV: Positive distance " << Val.getSExtValue() << 4336 " with max VF = " << MaxSafeDepDistBytes / TypeByteSize << '\n'); 4337 4338 return false; 4339} 4340 4341bool MemoryDepChecker::areDepsSafe(AccessAnalysis::DepCandidates &AccessSets, 4342 MemAccessInfoSet &CheckDeps, 4343 ValueToValueMap &Strides) { 4344 4345 MaxSafeDepDistBytes = -1U; 4346 while (!CheckDeps.empty()) { 4347 MemAccessInfo CurAccess = *CheckDeps.begin(); 4348 4349 // Get the relevant memory access set. 4350 EquivalenceClasses<MemAccessInfo>::iterator I = 4351 AccessSets.findValue(AccessSets.getLeaderValue(CurAccess)); 4352 4353 // Check accesses within this set. 4354 EquivalenceClasses<MemAccessInfo>::member_iterator AI, AE; 4355 AI = AccessSets.member_begin(I), AE = AccessSets.member_end(); 4356 4357 // Check every access pair. 4358 while (AI != AE) { 4359 CheckDeps.erase(*AI); 4360 EquivalenceClasses<MemAccessInfo>::member_iterator OI = std::next(AI); 4361 while (OI != AE) { 4362 // Check every accessing instruction pair in program order. 4363 for (std::vector<unsigned>::iterator I1 = Accesses[*AI].begin(), 4364 I1E = Accesses[*AI].end(); I1 != I1E; ++I1) 4365 for (std::vector<unsigned>::iterator I2 = Accesses[*OI].begin(), 4366 I2E = Accesses[*OI].end(); I2 != I2E; ++I2) { 4367 if (*I1 < *I2 && isDependent(*AI, *I1, *OI, *I2, Strides)) 4368 return false; 4369 if (*I2 < *I1 && isDependent(*OI, *I2, *AI, *I1, Strides)) 4370 return false; 4371 } 4372 ++OI; 4373 } 4374 AI++; 4375 } 4376 } 4377 return true; 4378} 4379 4380bool LoopVectorizationLegality::canVectorizeMemory() { 4381 4382 typedef SmallVector<Value*, 16> ValueVector; 4383 typedef SmallPtrSet<Value*, 16> ValueSet; 4384 4385 // Holds the Load and Store *instructions*. 4386 ValueVector Loads; 4387 ValueVector Stores; 4388 4389 // Holds all the different accesses in the loop. 4390 unsigned NumReads = 0; 4391 unsigned NumReadWrites = 0; 4392 4393 PtrRtCheck.Pointers.clear(); 4394 PtrRtCheck.Need = false; 4395 4396 const bool IsAnnotatedParallel = TheLoop->isAnnotatedParallel(); 4397 MemoryDepChecker DepChecker(SE, DL, TheLoop); 4398 4399 // For each block. 4400 for (Loop::block_iterator bb = TheLoop->block_begin(), 4401 be = TheLoop->block_end(); bb != be; ++bb) { 4402 4403 // Scan the BB and collect legal loads and stores. 4404 for (BasicBlock::iterator it = (*bb)->begin(), e = (*bb)->end(); it != e; 4405 ++it) { 4406 4407 // If this is a load, save it. If this instruction can read from memory 4408 // but is not a load, then we quit. Notice that we don't handle function 4409 // calls that read or write. 4410 if (it->mayReadFromMemory()) { 4411 // Many math library functions read the rounding mode. We will only 4412 // vectorize a loop if it contains known function calls that don't set 4413 // the flag. Therefore, it is safe to ignore this read from memory. 4414 CallInst *Call = dyn_cast<CallInst>(it); 4415 if (Call && getIntrinsicIDForCall(Call, TLI)) 4416 continue; 4417 4418 LoadInst *Ld = dyn_cast<LoadInst>(it); 4419 if (!Ld) return false; 4420 if (!Ld->isSimple() && !IsAnnotatedParallel) { 4421 DEBUG(dbgs() << "LV: Found a non-simple load.\n"); 4422 return false; 4423 } 4424 NumLoads++; 4425 Loads.push_back(Ld); 4426 DepChecker.addAccess(Ld); 4427 continue; 4428 } 4429 4430 // Save 'store' instructions. Abort if other instructions write to memory. 4431 if (it->mayWriteToMemory()) { 4432 StoreInst *St = dyn_cast<StoreInst>(it); 4433 if (!St) return false; 4434 if (!St->isSimple() && !IsAnnotatedParallel) { 4435 DEBUG(dbgs() << "LV: Found a non-simple store.\n"); 4436 return false; 4437 } 4438 NumStores++; 4439 Stores.push_back(St); 4440 DepChecker.addAccess(St); 4441 } 4442 } // Next instr. 4443 } // Next block. 4444 4445 // Now we have two lists that hold the loads and the stores. 4446 // Next, we find the pointers that they use. 4447 4448 // Check if we see any stores. If there are no stores, then we don't 4449 // care if the pointers are *restrict*. 4450 if (!Stores.size()) { 4451 DEBUG(dbgs() << "LV: Found a read-only loop!\n"); 4452 return true; 4453 } 4454 4455 AccessAnalysis::DepCandidates DependentAccesses; 4456 AccessAnalysis Accesses(DL, DependentAccesses); 4457 4458 // Holds the analyzed pointers. We don't want to call GetUnderlyingObjects 4459 // multiple times on the same object. If the ptr is accessed twice, once 4460 // for read and once for write, it will only appear once (on the write 4461 // list). This is okay, since we are going to check for conflicts between 4462 // writes and between reads and writes, but not between reads and reads. 4463 ValueSet Seen; 4464 4465 ValueVector::iterator I, IE; 4466 for (I = Stores.begin(), IE = Stores.end(); I != IE; ++I) { 4467 StoreInst *ST = cast<StoreInst>(*I); 4468 Value* Ptr = ST->getPointerOperand(); 4469 4470 if (isUniform(Ptr)) { 4471 DEBUG(dbgs() << "LV: We don't allow storing to uniform addresses\n"); 4472 return false; 4473 } 4474 4475 // If we did *not* see this pointer before, insert it to the read-write 4476 // list. At this phase it is only a 'write' list. 4477 if (Seen.insert(Ptr)) { 4478 ++NumReadWrites; 4479 Accesses.addStore(Ptr); 4480 } 4481 } 4482 4483 if (IsAnnotatedParallel) { 4484 DEBUG(dbgs() 4485 << "LV: A loop annotated parallel, ignore memory dependency " 4486 << "checks.\n"); 4487 return true; 4488 } 4489 4490 for (I = Loads.begin(), IE = Loads.end(); I != IE; ++I) { 4491 LoadInst *LD = cast<LoadInst>(*I); 4492 Value* Ptr = LD->getPointerOperand(); 4493 // If we did *not* see this pointer before, insert it to the 4494 // read list. If we *did* see it before, then it is already in 4495 // the read-write list. This allows us to vectorize expressions 4496 // such as A[i] += x; Because the address of A[i] is a read-write 4497 // pointer. This only works if the index of A[i] is consecutive. 4498 // If the address of i is unknown (for example A[B[i]]) then we may 4499 // read a few words, modify, and write a few words, and some of the 4500 // words may be written to the same address. 4501 bool IsReadOnlyPtr = false; 4502 if (Seen.insert(Ptr) || !isStridedPtr(SE, DL, Ptr, TheLoop, Strides)) { 4503 ++NumReads; 4504 IsReadOnlyPtr = true; 4505 } 4506 Accesses.addLoad(Ptr, IsReadOnlyPtr); 4507 } 4508 4509 // If we write (or read-write) to a single destination and there are no 4510 // other reads in this loop then is it safe to vectorize. 4511 if (NumReadWrites == 1 && NumReads == 0) { 4512 DEBUG(dbgs() << "LV: Found a write-only loop!\n"); 4513 return true; 4514 } 4515 4516 // Build dependence sets and check whether we need a runtime pointer bounds 4517 // check. 4518 Accesses.buildDependenceSets(); 4519 bool NeedRTCheck = Accesses.isRTCheckNeeded(); 4520 4521 // Find pointers with computable bounds. We are going to use this information 4522 // to place a runtime bound check. 4523 unsigned NumComparisons = 0; 4524 bool CanDoRT = false; 4525 if (NeedRTCheck) 4526 CanDoRT = Accesses.canCheckPtrAtRT(PtrRtCheck, NumComparisons, SE, TheLoop, 4527 Strides); 4528 4529 DEBUG(dbgs() << "LV: We need to do " << NumComparisons << 4530 " pointer comparisons.\n"); 4531 4532 // If we only have one set of dependences to check pointers among we don't 4533 // need a runtime check. 4534 if (NumComparisons == 0 && NeedRTCheck) 4535 NeedRTCheck = false; 4536 4537 // Check that we did not collect too many pointers or found an unsizeable 4538 // pointer. 4539 if (!CanDoRT || NumComparisons > RuntimeMemoryCheckThreshold) { 4540 PtrRtCheck.reset(); 4541 CanDoRT = false; 4542 } 4543 4544 if (CanDoRT) { 4545 DEBUG(dbgs() << "LV: We can perform a memory runtime check if needed.\n"); 4546 } 4547 4548 if (NeedRTCheck && !CanDoRT) { 4549 DEBUG(dbgs() << "LV: We can't vectorize because we can't find " << 4550 "the array bounds.\n"); 4551 PtrRtCheck.reset(); 4552 return false; 4553 } 4554 4555 PtrRtCheck.Need = NeedRTCheck; 4556 4557 bool CanVecMem = true; 4558 if (Accesses.isDependencyCheckNeeded()) { 4559 DEBUG(dbgs() << "LV: Checking memory dependencies\n"); 4560 CanVecMem = DepChecker.areDepsSafe( 4561 DependentAccesses, Accesses.getDependenciesToCheck(), Strides); 4562 MaxSafeDepDistBytes = DepChecker.getMaxSafeDepDistBytes(); 4563 4564 if (!CanVecMem && DepChecker.shouldRetryWithRuntimeCheck()) { 4565 DEBUG(dbgs() << "LV: Retrying with memory checks\n"); 4566 NeedRTCheck = true; 4567 4568 // Clear the dependency checks. We assume they are not needed. 4569 Accesses.resetDepChecks(); 4570 4571 PtrRtCheck.reset(); 4572 PtrRtCheck.Need = true; 4573 4574 CanDoRT = Accesses.canCheckPtrAtRT(PtrRtCheck, NumComparisons, SE, 4575 TheLoop, Strides, true); 4576 // Check that we did not collect too many pointers or found an unsizeable 4577 // pointer. 4578 if (!CanDoRT || NumComparisons > RuntimeMemoryCheckThreshold) { 4579 DEBUG(dbgs() << "LV: Can't vectorize with memory checks\n"); 4580 PtrRtCheck.reset(); 4581 return false; 4582 } 4583 4584 CanVecMem = true; 4585 } 4586 } 4587 4588 DEBUG(dbgs() << "LV: We" << (NeedRTCheck ? "" : " don't") << 4589 " need a runtime memory check.\n"); 4590 4591 return CanVecMem; 4592} 4593 4594static bool hasMultipleUsesOf(Instruction *I, 4595 SmallPtrSet<Instruction *, 8> &Insts) { 4596 unsigned NumUses = 0; 4597 for(User::op_iterator Use = I->op_begin(), E = I->op_end(); Use != E; ++Use) { 4598 if (Insts.count(dyn_cast<Instruction>(*Use))) 4599 ++NumUses; 4600 if (NumUses > 1) 4601 return true; 4602 } 4603 4604 return false; 4605} 4606 4607static bool areAllUsesIn(Instruction *I, SmallPtrSet<Instruction *, 8> &Set) { 4608 for(User::op_iterator Use = I->op_begin(), E = I->op_end(); Use != E; ++Use) 4609 if (!Set.count(dyn_cast<Instruction>(*Use))) 4610 return false; 4611 return true; 4612} 4613 4614bool LoopVectorizationLegality::AddReductionVar(PHINode *Phi, 4615 ReductionKind Kind) { 4616 if (Phi->getNumIncomingValues() != 2) 4617 return false; 4618 4619 // Reduction variables are only found in the loop header block. 4620 if (Phi->getParent() != TheLoop->getHeader()) 4621 return false; 4622 4623 // Obtain the reduction start value from the value that comes from the loop 4624 // preheader. 4625 Value *RdxStart = Phi->getIncomingValueForBlock(TheLoop->getLoopPreheader()); 4626 4627 // ExitInstruction is the single value which is used outside the loop. 4628 // We only allow for a single reduction value to be used outside the loop. 4629 // This includes users of the reduction, variables (which form a cycle 4630 // which ends in the phi node). 4631 Instruction *ExitInstruction = 0; 4632 // Indicates that we found a reduction operation in our scan. 4633 bool FoundReduxOp = false; 4634 4635 // We start with the PHI node and scan for all of the users of this 4636 // instruction. All users must be instructions that can be used as reduction 4637 // variables (such as ADD). We must have a single out-of-block user. The cycle 4638 // must include the original PHI. 4639 bool FoundStartPHI = false; 4640 4641 // To recognize min/max patterns formed by a icmp select sequence, we store 4642 // the number of instruction we saw from the recognized min/max pattern, 4643 // to make sure we only see exactly the two instructions. 4644 unsigned NumCmpSelectPatternInst = 0; 4645 ReductionInstDesc ReduxDesc(false, 0); 4646 4647 SmallPtrSet<Instruction *, 8> VisitedInsts; 4648 SmallVector<Instruction *, 8> Worklist; 4649 Worklist.push_back(Phi); 4650 VisitedInsts.insert(Phi); 4651 4652 // A value in the reduction can be used: 4653 // - By the reduction: 4654 // - Reduction operation: 4655 // - One use of reduction value (safe). 4656 // - Multiple use of reduction value (not safe). 4657 // - PHI: 4658 // - All uses of the PHI must be the reduction (safe). 4659 // - Otherwise, not safe. 4660 // - By one instruction outside of the loop (safe). 4661 // - By further instructions outside of the loop (not safe). 4662 // - By an instruction that is not part of the reduction (not safe). 4663 // This is either: 4664 // * An instruction type other than PHI or the reduction operation. 4665 // * A PHI in the header other than the initial PHI. 4666 while (!Worklist.empty()) { 4667 Instruction *Cur = Worklist.back(); 4668 Worklist.pop_back(); 4669 4670 // No Users. 4671 // If the instruction has no users then this is a broken chain and can't be 4672 // a reduction variable. 4673 if (Cur->use_empty()) 4674 return false; 4675 4676 bool IsAPhi = isa<PHINode>(Cur); 4677 4678 // A header PHI use other than the original PHI. 4679 if (Cur != Phi && IsAPhi && Cur->getParent() == Phi->getParent()) 4680 return false; 4681 4682 // Reductions of instructions such as Div, and Sub is only possible if the 4683 // LHS is the reduction variable. 4684 if (!Cur->isCommutative() && !IsAPhi && !isa<SelectInst>(Cur) && 4685 !isa<ICmpInst>(Cur) && !isa<FCmpInst>(Cur) && 4686 !VisitedInsts.count(dyn_cast<Instruction>(Cur->getOperand(0)))) 4687 return false; 4688 4689 // Any reduction instruction must be of one of the allowed kinds. 4690 ReduxDesc = isReductionInstr(Cur, Kind, ReduxDesc); 4691 if (!ReduxDesc.IsReduction) 4692 return false; 4693 4694 // A reduction operation must only have one use of the reduction value. 4695 if (!IsAPhi && Kind != RK_IntegerMinMax && Kind != RK_FloatMinMax && 4696 hasMultipleUsesOf(Cur, VisitedInsts)) 4697 return false; 4698 4699 // All inputs to a PHI node must be a reduction value. 4700 if(IsAPhi && Cur != Phi && !areAllUsesIn(Cur, VisitedInsts)) 4701 return false; 4702 4703 if (Kind == RK_IntegerMinMax && (isa<ICmpInst>(Cur) || 4704 isa<SelectInst>(Cur))) 4705 ++NumCmpSelectPatternInst; 4706 if (Kind == RK_FloatMinMax && (isa<FCmpInst>(Cur) || 4707 isa<SelectInst>(Cur))) 4708 ++NumCmpSelectPatternInst; 4709 4710 // Check whether we found a reduction operator. 4711 FoundReduxOp |= !IsAPhi; 4712 4713 // Process users of current instruction. Push non-PHI nodes after PHI nodes 4714 // onto the stack. This way we are going to have seen all inputs to PHI 4715 // nodes once we get to them. 4716 SmallVector<Instruction *, 8> NonPHIs; 4717 SmallVector<Instruction *, 8> PHIs; 4718 for (User *U : Cur->users()) { 4719 Instruction *UI = cast<Instruction>(U); 4720 4721 // Check if we found the exit user. 4722 BasicBlock *Parent = UI->getParent(); 4723 if (!TheLoop->contains(Parent)) { 4724 // Exit if you find multiple outside users or if the header phi node is 4725 // being used. In this case the user uses the value of the previous 4726 // iteration, in which case we would loose "VF-1" iterations of the 4727 // reduction operation if we vectorize. 4728 if (ExitInstruction != 0 || Cur == Phi) 4729 return false; 4730 4731 // The instruction used by an outside user must be the last instruction 4732 // before we feed back to the reduction phi. Otherwise, we loose VF-1 4733 // operations on the value. 4734 if (std::find(Phi->op_begin(), Phi->op_end(), Cur) == Phi->op_end()) 4735 return false; 4736 4737 ExitInstruction = Cur; 4738 continue; 4739 } 4740 4741 // Process instructions only once (termination). Each reduction cycle 4742 // value must only be used once, except by phi nodes and min/max 4743 // reductions which are represented as a cmp followed by a select. 4744 ReductionInstDesc IgnoredVal(false, 0); 4745 if (VisitedInsts.insert(UI)) { 4746 if (isa<PHINode>(UI)) 4747 PHIs.push_back(UI); 4748 else 4749 NonPHIs.push_back(UI); 4750 } else if (!isa<PHINode>(UI) && 4751 ((!isa<FCmpInst>(UI) && 4752 !isa<ICmpInst>(UI) && 4753 !isa<SelectInst>(UI)) || 4754 !isMinMaxSelectCmpPattern(UI, IgnoredVal).IsReduction)) 4755 return false; 4756 4757 // Remember that we completed the cycle. 4758 if (UI == Phi) 4759 FoundStartPHI = true; 4760 } 4761 Worklist.append(PHIs.begin(), PHIs.end()); 4762 Worklist.append(NonPHIs.begin(), NonPHIs.end()); 4763 } 4764 4765 // This means we have seen one but not the other instruction of the 4766 // pattern or more than just a select and cmp. 4767 if ((Kind == RK_IntegerMinMax || Kind == RK_FloatMinMax) && 4768 NumCmpSelectPatternInst != 2) 4769 return false; 4770 4771 if (!FoundStartPHI || !FoundReduxOp || !ExitInstruction) 4772 return false; 4773 4774 // We found a reduction var if we have reached the original phi node and we 4775 // only have a single instruction with out-of-loop users. 4776 4777 // This instruction is allowed to have out-of-loop users. 4778 AllowedExit.insert(ExitInstruction); 4779 4780 // Save the description of this reduction variable. 4781 ReductionDescriptor RD(RdxStart, ExitInstruction, Kind, 4782 ReduxDesc.MinMaxKind); 4783 Reductions[Phi] = RD; 4784 // We've ended the cycle. This is a reduction variable if we have an 4785 // outside user and it has a binary op. 4786 4787 return true; 4788} 4789 4790/// Returns true if the instruction is a Select(ICmp(X, Y), X, Y) instruction 4791/// pattern corresponding to a min(X, Y) or max(X, Y). 4792LoopVectorizationLegality::ReductionInstDesc 4793LoopVectorizationLegality::isMinMaxSelectCmpPattern(Instruction *I, 4794 ReductionInstDesc &Prev) { 4795 4796 assert((isa<ICmpInst>(I) || isa<FCmpInst>(I) || isa<SelectInst>(I)) && 4797 "Expect a select instruction"); 4798 Instruction *Cmp = 0; 4799 SelectInst *Select = 0; 4800 4801 // We must handle the select(cmp()) as a single instruction. Advance to the 4802 // select. 4803 if ((Cmp = dyn_cast<ICmpInst>(I)) || (Cmp = dyn_cast<FCmpInst>(I))) { 4804 if (!Cmp->hasOneUse() || !(Select = dyn_cast<SelectInst>(*I->user_begin()))) 4805 return ReductionInstDesc(false, I); 4806 return ReductionInstDesc(Select, Prev.MinMaxKind); 4807 } 4808 4809 // Only handle single use cases for now. 4810 if (!(Select = dyn_cast<SelectInst>(I))) 4811 return ReductionInstDesc(false, I); 4812 if (!(Cmp = dyn_cast<ICmpInst>(I->getOperand(0))) && 4813 !(Cmp = dyn_cast<FCmpInst>(I->getOperand(0)))) 4814 return ReductionInstDesc(false, I); 4815 if (!Cmp->hasOneUse()) 4816 return ReductionInstDesc(false, I); 4817 4818 Value *CmpLeft; 4819 Value *CmpRight; 4820 4821 // Look for a min/max pattern. 4822 if (m_UMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select)) 4823 return ReductionInstDesc(Select, MRK_UIntMin); 4824 else if (m_UMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select)) 4825 return ReductionInstDesc(Select, MRK_UIntMax); 4826 else if (m_SMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select)) 4827 return ReductionInstDesc(Select, MRK_SIntMax); 4828 else if (m_SMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select)) 4829 return ReductionInstDesc(Select, MRK_SIntMin); 4830 else if (m_OrdFMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select)) 4831 return ReductionInstDesc(Select, MRK_FloatMin); 4832 else if (m_OrdFMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select)) 4833 return ReductionInstDesc(Select, MRK_FloatMax); 4834 else if (m_UnordFMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select)) 4835 return ReductionInstDesc(Select, MRK_FloatMin); 4836 else if (m_UnordFMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select)) 4837 return ReductionInstDesc(Select, MRK_FloatMax); 4838 4839 return ReductionInstDesc(false, I); 4840} 4841 4842LoopVectorizationLegality::ReductionInstDesc 4843LoopVectorizationLegality::isReductionInstr(Instruction *I, 4844 ReductionKind Kind, 4845 ReductionInstDesc &Prev) { 4846 bool FP = I->getType()->isFloatingPointTy(); 4847 bool FastMath = (FP && I->isCommutative() && I->isAssociative()); 4848 switch (I->getOpcode()) { 4849 default: 4850 return ReductionInstDesc(false, I); 4851 case Instruction::PHI: 4852 if (FP && (Kind != RK_FloatMult && Kind != RK_FloatAdd && 4853 Kind != RK_FloatMinMax)) 4854 return ReductionInstDesc(false, I); 4855 return ReductionInstDesc(I, Prev.MinMaxKind); 4856 case Instruction::Sub: 4857 case Instruction::Add: 4858 return ReductionInstDesc(Kind == RK_IntegerAdd, I); 4859 case Instruction::Mul: 4860 return ReductionInstDesc(Kind == RK_IntegerMult, I); 4861 case Instruction::And: 4862 return ReductionInstDesc(Kind == RK_IntegerAnd, I); 4863 case Instruction::Or: 4864 return ReductionInstDesc(Kind == RK_IntegerOr, I); 4865 case Instruction::Xor: 4866 return ReductionInstDesc(Kind == RK_IntegerXor, I); 4867 case Instruction::FMul: 4868 return ReductionInstDesc(Kind == RK_FloatMult && FastMath, I); 4869 case Instruction::FAdd: 4870 return ReductionInstDesc(Kind == RK_FloatAdd && FastMath, I); 4871 case Instruction::FCmp: 4872 case Instruction::ICmp: 4873 case Instruction::Select: 4874 if (Kind != RK_IntegerMinMax && 4875 (!HasFunNoNaNAttr || Kind != RK_FloatMinMax)) 4876 return ReductionInstDesc(false, I); 4877 return isMinMaxSelectCmpPattern(I, Prev); 4878 } 4879} 4880 4881LoopVectorizationLegality::InductionKind 4882LoopVectorizationLegality::isInductionVariable(PHINode *Phi) { 4883 Type *PhiTy = Phi->getType(); 4884 // We only handle integer and pointer inductions variables. 4885 if (!PhiTy->isIntegerTy() && !PhiTy->isPointerTy()) 4886 return IK_NoInduction; 4887 4888 // Check that the PHI is consecutive. 4889 const SCEV *PhiScev = SE->getSCEV(Phi); 4890 const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(PhiScev); 4891 if (!AR) { 4892 DEBUG(dbgs() << "LV: PHI is not a poly recurrence.\n"); 4893 return IK_NoInduction; 4894 } 4895 const SCEV *Step = AR->getStepRecurrence(*SE); 4896 4897 // Integer inductions need to have a stride of one. 4898 if (PhiTy->isIntegerTy()) { 4899 if (Step->isOne()) 4900 return IK_IntInduction; 4901 if (Step->isAllOnesValue()) 4902 return IK_ReverseIntInduction; 4903 return IK_NoInduction; 4904 } 4905 4906 // Calculate the pointer stride and check if it is consecutive. 4907 const SCEVConstant *C = dyn_cast<SCEVConstant>(Step); 4908 if (!C) 4909 return IK_NoInduction; 4910 4911 assert(PhiTy->isPointerTy() && "The PHI must be a pointer"); 4912 uint64_t Size = DL->getTypeAllocSize(PhiTy->getPointerElementType()); 4913 if (C->getValue()->equalsInt(Size)) 4914 return IK_PtrInduction; 4915 else if (C->getValue()->equalsInt(0 - Size)) 4916 return IK_ReversePtrInduction; 4917 4918 return IK_NoInduction; 4919} 4920 4921bool LoopVectorizationLegality::isInductionVariable(const Value *V) { 4922 Value *In0 = const_cast<Value*>(V); 4923 PHINode *PN = dyn_cast_or_null<PHINode>(In0); 4924 if (!PN) 4925 return false; 4926 4927 return Inductions.count(PN); 4928} 4929 4930bool LoopVectorizationLegality::blockNeedsPredication(BasicBlock *BB) { 4931 assert(TheLoop->contains(BB) && "Unknown block used"); 4932 4933 // Blocks that do not dominate the latch need predication. 4934 BasicBlock* Latch = TheLoop->getLoopLatch(); 4935 return !DT->dominates(BB, Latch); 4936} 4937 4938bool LoopVectorizationLegality::blockCanBePredicated(BasicBlock *BB, 4939 SmallPtrSet<Value *, 8>& SafePtrs) { 4940 for (BasicBlock::iterator it = BB->begin(), e = BB->end(); it != e; ++it) { 4941 // We might be able to hoist the load. 4942 if (it->mayReadFromMemory()) { 4943 LoadInst *LI = dyn_cast<LoadInst>(it); 4944 if (!LI || !SafePtrs.count(LI->getPointerOperand())) 4945 return false; 4946 } 4947 4948 // We don't predicate stores at the moment. 4949 if (it->mayWriteToMemory()) { 4950 StoreInst *SI = dyn_cast<StoreInst>(it); 4951 // We only support predication of stores in basic blocks with one 4952 // predecessor. 4953 if (!SI || ++NumPredStores > NumberOfStoresToPredicate || 4954 !SafePtrs.count(SI->getPointerOperand()) || 4955 !SI->getParent()->getSinglePredecessor()) 4956 return false; 4957 } 4958 if (it->mayThrow()) 4959 return false; 4960 4961 // Check that we don't have a constant expression that can trap as operand. 4962 for (Instruction::op_iterator OI = it->op_begin(), OE = it->op_end(); 4963 OI != OE; ++OI) { 4964 if (Constant *C = dyn_cast<Constant>(*OI)) 4965 if (C->canTrap()) 4966 return false; 4967 } 4968 4969 // The instructions below can trap. 4970 switch (it->getOpcode()) { 4971 default: continue; 4972 case Instruction::UDiv: 4973 case Instruction::SDiv: 4974 case Instruction::URem: 4975 case Instruction::SRem: 4976 return false; 4977 } 4978 } 4979 4980 return true; 4981} 4982 4983LoopVectorizationCostModel::VectorizationFactor 4984LoopVectorizationCostModel::selectVectorizationFactor(bool OptForSize, 4985 unsigned UserVF) { 4986 // Width 1 means no vectorize 4987 VectorizationFactor Factor = { 1U, 0U }; 4988 if (OptForSize && Legal->getRuntimePointerCheck()->Need) { 4989 DEBUG(dbgs() << "LV: Aborting. Runtime ptr check is required in Os.\n"); 4990 return Factor; 4991 } 4992 4993 if (!EnableCondStoresVectorization && Legal->NumPredStores) { 4994 DEBUG(dbgs() << "LV: No vectorization. There are conditional stores.\n"); 4995 return Factor; 4996 } 4997 4998 // Find the trip count. 4999 unsigned TC = SE->getSmallConstantTripCount(TheLoop, TheLoop->getLoopLatch()); 5000 DEBUG(dbgs() << "LV: Found trip count: " << TC << '\n'); 5001 5002 unsigned WidestType = getWidestType(); 5003 unsigned WidestRegister = TTI.getRegisterBitWidth(true); 5004 unsigned MaxSafeDepDist = -1U; 5005 if (Legal->getMaxSafeDepDistBytes() != -1U) 5006 MaxSafeDepDist = Legal->getMaxSafeDepDistBytes() * 8; 5007 WidestRegister = ((WidestRegister < MaxSafeDepDist) ? 5008 WidestRegister : MaxSafeDepDist); 5009 unsigned MaxVectorSize = WidestRegister / WidestType; 5010 DEBUG(dbgs() << "LV: The Widest type: " << WidestType << " bits.\n"); 5011 DEBUG(dbgs() << "LV: The Widest register is: " 5012 << WidestRegister << " bits.\n"); 5013 5014 if (MaxVectorSize == 0) { 5015 DEBUG(dbgs() << "LV: The target has no vector registers.\n"); 5016 MaxVectorSize = 1; 5017 } 5018 5019 assert(MaxVectorSize <= 32 && "Did not expect to pack so many elements" 5020 " into one vector!"); 5021 5022 unsigned VF = MaxVectorSize; 5023 5024 // If we optimize the program for size, avoid creating the tail loop. 5025 if (OptForSize) { 5026 // If we are unable to calculate the trip count then don't try to vectorize. 5027 if (TC < 2) { 5028 DEBUG(dbgs() << "LV: Aborting. A tail loop is required in Os.\n"); 5029 return Factor; 5030 } 5031 5032 // Find the maximum SIMD width that can fit within the trip count. 5033 VF = TC % MaxVectorSize; 5034 5035 if (VF == 0) 5036 VF = MaxVectorSize; 5037 5038 // If the trip count that we found modulo the vectorization factor is not 5039 // zero then we require a tail. 5040 if (VF < 2) { 5041 DEBUG(dbgs() << "LV: Aborting. A tail loop is required in Os.\n"); 5042 return Factor; 5043 } 5044 } 5045 5046 if (UserVF != 0) { 5047 assert(isPowerOf2_32(UserVF) && "VF needs to be a power of two"); 5048 DEBUG(dbgs() << "LV: Using user VF " << UserVF << ".\n"); 5049 5050 Factor.Width = UserVF; 5051 return Factor; 5052 } 5053 5054 float Cost = expectedCost(1); 5055 unsigned Width = 1; 5056 DEBUG(dbgs() << "LV: Scalar loop costs: " << (int)Cost << ".\n"); 5057 for (unsigned i=2; i <= VF; i*=2) { 5058 // Notice that the vector loop needs to be executed less times, so 5059 // we need to divide the cost of the vector loops by the width of 5060 // the vector elements. 5061 float VectorCost = expectedCost(i) / (float)i; 5062 DEBUG(dbgs() << "LV: Vector loop of width " << i << " costs: " << 5063 (int)VectorCost << ".\n"); 5064 if (VectorCost < Cost) { 5065 Cost = VectorCost; 5066 Width = i; 5067 } 5068 } 5069 5070 DEBUG(dbgs() << "LV: Selecting VF = : "<< Width << ".\n"); 5071 Factor.Width = Width; 5072 Factor.Cost = Width * Cost; 5073 return Factor; 5074} 5075 5076unsigned LoopVectorizationCostModel::getWidestType() { 5077 unsigned MaxWidth = 8; 5078 5079 // For each block. 5080 for (Loop::block_iterator bb = TheLoop->block_begin(), 5081 be = TheLoop->block_end(); bb != be; ++bb) { 5082 BasicBlock *BB = *bb; 5083 5084 // For each instruction in the loop. 5085 for (BasicBlock::iterator it = BB->begin(), e = BB->end(); it != e; ++it) { 5086 Type *T = it->getType(); 5087 5088 // Only examine Loads, Stores and PHINodes. 5089 if (!isa<LoadInst>(it) && !isa<StoreInst>(it) && !isa<PHINode>(it)) 5090 continue; 5091 5092 // Examine PHI nodes that are reduction variables. 5093 if (PHINode *PN = dyn_cast<PHINode>(it)) 5094 if (!Legal->getReductionVars()->count(PN)) 5095 continue; 5096 5097 // Examine the stored values. 5098 if (StoreInst *ST = dyn_cast<StoreInst>(it)) 5099 T = ST->getValueOperand()->getType(); 5100 5101 // Ignore loaded pointer types and stored pointer types that are not 5102 // consecutive. However, we do want to take consecutive stores/loads of 5103 // pointer vectors into account. 5104 if (T->isPointerTy() && !isConsecutiveLoadOrStore(it)) 5105 continue; 5106 5107 MaxWidth = std::max(MaxWidth, 5108 (unsigned)DL->getTypeSizeInBits(T->getScalarType())); 5109 } 5110 } 5111 5112 return MaxWidth; 5113} 5114 5115unsigned 5116LoopVectorizationCostModel::selectUnrollFactor(bool OptForSize, 5117 unsigned UserUF, 5118 unsigned VF, 5119 unsigned LoopCost) { 5120 5121 // -- The unroll heuristics -- 5122 // We unroll the loop in order to expose ILP and reduce the loop overhead. 5123 // There are many micro-architectural considerations that we can't predict 5124 // at this level. For example frontend pressure (on decode or fetch) due to 5125 // code size, or the number and capabilities of the execution ports. 5126 // 5127 // We use the following heuristics to select the unroll factor: 5128 // 1. If the code has reductions the we unroll in order to break the cross 5129 // iteration dependency. 5130 // 2. If the loop is really small then we unroll in order to reduce the loop 5131 // overhead. 5132 // 3. We don't unroll if we think that we will spill registers to memory due 5133 // to the increased register pressure. 5134 5135 // Use the user preference, unless 'auto' is selected. 5136 if (UserUF != 0) 5137 return UserUF; 5138 5139 // When we optimize for size we don't unroll. 5140 if (OptForSize) 5141 return 1; 5142 5143 // We used the distance for the unroll factor. 5144 if (Legal->getMaxSafeDepDistBytes() != -1U) 5145 return 1; 5146 5147 // Do not unroll loops with a relatively small trip count. 5148 unsigned TC = SE->getSmallConstantTripCount(TheLoop, 5149 TheLoop->getLoopLatch()); 5150 if (TC > 1 && TC < TinyTripCountUnrollThreshold) 5151 return 1; 5152 5153 unsigned TargetNumRegisters = TTI.getNumberOfRegisters(VF > 1); 5154 DEBUG(dbgs() << "LV: The target has " << TargetNumRegisters << 5155 " registers\n"); 5156 5157 if (VF == 1) { 5158 if (ForceTargetNumScalarRegs.getNumOccurrences() > 0) 5159 TargetNumRegisters = ForceTargetNumScalarRegs; 5160 } else { 5161 if (ForceTargetNumVectorRegs.getNumOccurrences() > 0) 5162 TargetNumRegisters = ForceTargetNumVectorRegs; 5163 } 5164 5165 LoopVectorizationCostModel::RegisterUsage R = calculateRegisterUsage(); 5166 // We divide by these constants so assume that we have at least one 5167 // instruction that uses at least one register. 5168 R.MaxLocalUsers = std::max(R.MaxLocalUsers, 1U); 5169 R.NumInstructions = std::max(R.NumInstructions, 1U); 5170 5171 // We calculate the unroll factor using the following formula. 5172 // Subtract the number of loop invariants from the number of available 5173 // registers. These registers are used by all of the unrolled instances. 5174 // Next, divide the remaining registers by the number of registers that is 5175 // required by the loop, in order to estimate how many parallel instances 5176 // fit without causing spills. All of this is rounded down if necessary to be 5177 // a power of two. We want power of two unroll factors to simplify any 5178 // addressing operations or alignment considerations. 5179 unsigned UF = PowerOf2Floor((TargetNumRegisters - R.LoopInvariantRegs) / 5180 R.MaxLocalUsers); 5181 5182 // Don't count the induction variable as unrolled. 5183 if (EnableIndVarRegisterHeur) 5184 UF = PowerOf2Floor((TargetNumRegisters - R.LoopInvariantRegs - 1) / 5185 std::max(1U, (R.MaxLocalUsers - 1))); 5186 5187 // Clamp the unroll factor ranges to reasonable factors. 5188 unsigned MaxUnrollSize = TTI.getMaximumUnrollFactor(); 5189 5190 // Check if the user has overridden the unroll max. 5191 if (VF == 1) { 5192 if (ForceTargetMaxScalarUnrollFactor.getNumOccurrences() > 0) 5193 MaxUnrollSize = ForceTargetMaxScalarUnrollFactor; 5194 } else { 5195 if (ForceTargetMaxVectorUnrollFactor.getNumOccurrences() > 0) 5196 MaxUnrollSize = ForceTargetMaxVectorUnrollFactor; 5197 } 5198 5199 // If we did not calculate the cost for VF (because the user selected the VF) 5200 // then we calculate the cost of VF here. 5201 if (LoopCost == 0) 5202 LoopCost = expectedCost(VF); 5203 5204 // Clamp the calculated UF to be between the 1 and the max unroll factor 5205 // that the target allows. 5206 if (UF > MaxUnrollSize) 5207 UF = MaxUnrollSize; 5208 else if (UF < 1) 5209 UF = 1; 5210 5211 // Unroll if we vectorized this loop and there is a reduction that could 5212 // benefit from unrolling. 5213 if (VF > 1 && Legal->getReductionVars()->size()) { 5214 DEBUG(dbgs() << "LV: Unrolling because of reductions.\n"); 5215 return UF; 5216 } 5217 5218 // Note that if we've already vectorized the loop we will have done the 5219 // runtime check and so unrolling won't require further checks. 5220 bool UnrollingRequiresRuntimePointerCheck = 5221 (VF == 1 && Legal->getRuntimePointerCheck()->Need); 5222 5223 // We want to unroll small loops in order to reduce the loop overhead and 5224 // potentially expose ILP opportunities. 5225 DEBUG(dbgs() << "LV: Loop cost is " << LoopCost << '\n'); 5226 if (!UnrollingRequiresRuntimePointerCheck && 5227 LoopCost < SmallLoopCost) { 5228 // We assume that the cost overhead is 1 and we use the cost model 5229 // to estimate the cost of the loop and unroll until the cost of the 5230 // loop overhead is about 5% of the cost of the loop. 5231 unsigned SmallUF = std::min(UF, (unsigned)PowerOf2Floor(SmallLoopCost / LoopCost)); 5232 5233 // Unroll until store/load ports (estimated by max unroll factor) are 5234 // saturated. 5235 unsigned StoresUF = UF / (Legal->NumStores ? Legal->NumStores : 1); 5236 unsigned LoadsUF = UF / (Legal->NumLoads ? Legal->NumLoads : 1); 5237 5238 if (EnableLoadStoreRuntimeUnroll && std::max(StoresUF, LoadsUF) > SmallUF) { 5239 DEBUG(dbgs() << "LV: Unrolling to saturate store or load ports.\n"); 5240 return std::max(StoresUF, LoadsUF); 5241 } 5242 5243 DEBUG(dbgs() << "LV: Unrolling to reduce branch cost.\n"); 5244 return SmallUF; 5245 } 5246 5247 DEBUG(dbgs() << "LV: Not Unrolling.\n"); 5248 return 1; 5249} 5250 5251LoopVectorizationCostModel::RegisterUsage 5252LoopVectorizationCostModel::calculateRegisterUsage() { 5253 // This function calculates the register usage by measuring the highest number 5254 // of values that are alive at a single location. Obviously, this is a very 5255 // rough estimation. We scan the loop in a topological order in order and 5256 // assign a number to each instruction. We use RPO to ensure that defs are 5257 // met before their users. We assume that each instruction that has in-loop 5258 // users starts an interval. We record every time that an in-loop value is 5259 // used, so we have a list of the first and last occurrences of each 5260 // instruction. Next, we transpose this data structure into a multi map that 5261 // holds the list of intervals that *end* at a specific location. This multi 5262 // map allows us to perform a linear search. We scan the instructions linearly 5263 // and record each time that a new interval starts, by placing it in a set. 5264 // If we find this value in the multi-map then we remove it from the set. 5265 // The max register usage is the maximum size of the set. 5266 // We also search for instructions that are defined outside the loop, but are 5267 // used inside the loop. We need this number separately from the max-interval 5268 // usage number because when we unroll, loop-invariant values do not take 5269 // more register. 5270 LoopBlocksDFS DFS(TheLoop); 5271 DFS.perform(LI); 5272 5273 RegisterUsage R; 5274 R.NumInstructions = 0; 5275 5276 // Each 'key' in the map opens a new interval. The values 5277 // of the map are the index of the 'last seen' usage of the 5278 // instruction that is the key. 5279 typedef DenseMap<Instruction*, unsigned> IntervalMap; 5280 // Maps instruction to its index. 5281 DenseMap<unsigned, Instruction*> IdxToInstr; 5282 // Marks the end of each interval. 5283 IntervalMap EndPoint; 5284 // Saves the list of instruction indices that are used in the loop. 5285 SmallSet<Instruction*, 8> Ends; 5286 // Saves the list of values that are used in the loop but are 5287 // defined outside the loop, such as arguments and constants. 5288 SmallPtrSet<Value*, 8> LoopInvariants; 5289 5290 unsigned Index = 0; 5291 for (LoopBlocksDFS::RPOIterator bb = DFS.beginRPO(), 5292 be = DFS.endRPO(); bb != be; ++bb) { 5293 R.NumInstructions += (*bb)->size(); 5294 for (BasicBlock::iterator it = (*bb)->begin(), e = (*bb)->end(); it != e; 5295 ++it) { 5296 Instruction *I = it; 5297 IdxToInstr[Index++] = I; 5298 5299 // Save the end location of each USE. 5300 for (unsigned i = 0; i < I->getNumOperands(); ++i) { 5301 Value *U = I->getOperand(i); 5302 Instruction *Instr = dyn_cast<Instruction>(U); 5303 5304 // Ignore non-instruction values such as arguments, constants, etc. 5305 if (!Instr) continue; 5306 5307 // If this instruction is outside the loop then record it and continue. 5308 if (!TheLoop->contains(Instr)) { 5309 LoopInvariants.insert(Instr); 5310 continue; 5311 } 5312 5313 // Overwrite previous end points. 5314 EndPoint[Instr] = Index; 5315 Ends.insert(Instr); 5316 } 5317 } 5318 } 5319 5320 // Saves the list of intervals that end with the index in 'key'. 5321 typedef SmallVector<Instruction*, 2> InstrList; 5322 DenseMap<unsigned, InstrList> TransposeEnds; 5323 5324 // Transpose the EndPoints to a list of values that end at each index. 5325 for (IntervalMap::iterator it = EndPoint.begin(), e = EndPoint.end(); 5326 it != e; ++it) 5327 TransposeEnds[it->second].push_back(it->first); 5328 5329 SmallSet<Instruction*, 8> OpenIntervals; 5330 unsigned MaxUsage = 0; 5331 5332 5333 DEBUG(dbgs() << "LV(REG): Calculating max register usage:\n"); 5334 for (unsigned int i = 0; i < Index; ++i) { 5335 Instruction *I = IdxToInstr[i]; 5336 // Ignore instructions that are never used within the loop. 5337 if (!Ends.count(I)) continue; 5338 5339 // Remove all of the instructions that end at this location. 5340 InstrList &List = TransposeEnds[i]; 5341 for (unsigned int j=0, e = List.size(); j < e; ++j) 5342 OpenIntervals.erase(List[j]); 5343 5344 // Count the number of live interals. 5345 MaxUsage = std::max(MaxUsage, OpenIntervals.size()); 5346 5347 DEBUG(dbgs() << "LV(REG): At #" << i << " Interval # " << 5348 OpenIntervals.size() << '\n'); 5349 5350 // Add the current instruction to the list of open intervals. 5351 OpenIntervals.insert(I); 5352 } 5353 5354 unsigned Invariant = LoopInvariants.size(); 5355 DEBUG(dbgs() << "LV(REG): Found max usage: " << MaxUsage << '\n'); 5356 DEBUG(dbgs() << "LV(REG): Found invariant usage: " << Invariant << '\n'); 5357 DEBUG(dbgs() << "LV(REG): LoopSize: " << R.NumInstructions << '\n'); 5358 5359 R.LoopInvariantRegs = Invariant; 5360 R.MaxLocalUsers = MaxUsage; 5361 return R; 5362} 5363 5364unsigned LoopVectorizationCostModel::expectedCost(unsigned VF) { 5365 unsigned Cost = 0; 5366 5367 // For each block. 5368 for (Loop::block_iterator bb = TheLoop->block_begin(), 5369 be = TheLoop->block_end(); bb != be; ++bb) { 5370 unsigned BlockCost = 0; 5371 BasicBlock *BB = *bb; 5372 5373 // For each instruction in the old loop. 5374 for (BasicBlock::iterator it = BB->begin(), e = BB->end(); it != e; ++it) { 5375 // Skip dbg intrinsics. 5376 if (isa<DbgInfoIntrinsic>(it)) 5377 continue; 5378 5379 unsigned C = getInstructionCost(it, VF); 5380 5381 // Check if we should override the cost. 5382 if (ForceTargetInstructionCost.getNumOccurrences() > 0) 5383 C = ForceTargetInstructionCost; 5384 5385 BlockCost += C; 5386 DEBUG(dbgs() << "LV: Found an estimated cost of " << C << " for VF " << 5387 VF << " For instruction: " << *it << '\n'); 5388 } 5389 5390 // We assume that if-converted blocks have a 50% chance of being executed. 5391 // When the code is scalar then some of the blocks are avoided due to CF. 5392 // When the code is vectorized we execute all code paths. 5393 if (VF == 1 && Legal->blockNeedsPredication(*bb)) 5394 BlockCost /= 2; 5395 5396 Cost += BlockCost; 5397 } 5398 5399 return Cost; 5400} 5401 5402/// \brief Check whether the address computation for a non-consecutive memory 5403/// access looks like an unlikely candidate for being merged into the indexing 5404/// mode. 5405/// 5406/// We look for a GEP which has one index that is an induction variable and all 5407/// other indices are loop invariant. If the stride of this access is also 5408/// within a small bound we decide that this address computation can likely be 5409/// merged into the addressing mode. 5410/// In all other cases, we identify the address computation as complex. 5411static bool isLikelyComplexAddressComputation(Value *Ptr, 5412 LoopVectorizationLegality *Legal, 5413 ScalarEvolution *SE, 5414 const Loop *TheLoop) { 5415 GetElementPtrInst *Gep = dyn_cast<GetElementPtrInst>(Ptr); 5416 if (!Gep) 5417 return true; 5418 5419 // We are looking for a gep with all loop invariant indices except for one 5420 // which should be an induction variable. 5421 unsigned NumOperands = Gep->getNumOperands(); 5422 for (unsigned i = 1; i < NumOperands; ++i) { 5423 Value *Opd = Gep->getOperand(i); 5424 if (!SE->isLoopInvariant(SE->getSCEV(Opd), TheLoop) && 5425 !Legal->isInductionVariable(Opd)) 5426 return true; 5427 } 5428 5429 // Now we know we have a GEP ptr, %inv, %ind, %inv. Make sure that the step 5430 // can likely be merged into the address computation. 5431 unsigned MaxMergeDistance = 64; 5432 5433 const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(Ptr)); 5434 if (!AddRec) 5435 return true; 5436 5437 // Check the step is constant. 5438 const SCEV *Step = AddRec->getStepRecurrence(*SE); 5439 // Calculate the pointer stride and check if it is consecutive. 5440 const SCEVConstant *C = dyn_cast<SCEVConstant>(Step); 5441 if (!C) 5442 return true; 5443 5444 const APInt &APStepVal = C->getValue()->getValue(); 5445 5446 // Huge step value - give up. 5447 if (APStepVal.getBitWidth() > 64) 5448 return true; 5449 5450 int64_t StepVal = APStepVal.getSExtValue(); 5451 5452 return StepVal > MaxMergeDistance; 5453} 5454 5455static bool isStrideMul(Instruction *I, LoopVectorizationLegality *Legal) { 5456 if (Legal->hasStride(I->getOperand(0)) || Legal->hasStride(I->getOperand(1))) 5457 return true; 5458 return false; 5459} 5460 5461unsigned 5462LoopVectorizationCostModel::getInstructionCost(Instruction *I, unsigned VF) { 5463 // If we know that this instruction will remain uniform, check the cost of 5464 // the scalar version. 5465 if (Legal->isUniformAfterVectorization(I)) 5466 VF = 1; 5467 5468 Type *RetTy = I->getType(); 5469 Type *VectorTy = ToVectorTy(RetTy, VF); 5470 5471 // TODO: We need to estimate the cost of intrinsic calls. 5472 switch (I->getOpcode()) { 5473 case Instruction::GetElementPtr: 5474 // We mark this instruction as zero-cost because the cost of GEPs in 5475 // vectorized code depends on whether the corresponding memory instruction 5476 // is scalarized or not. Therefore, we handle GEPs with the memory 5477 // instruction cost. 5478 return 0; 5479 case Instruction::Br: { 5480 return TTI.getCFInstrCost(I->getOpcode()); 5481 } 5482 case Instruction::PHI: 5483 //TODO: IF-converted IFs become selects. 5484 return 0; 5485 case Instruction::Add: 5486 case Instruction::FAdd: 5487 case Instruction::Sub: 5488 case Instruction::FSub: 5489 case Instruction::Mul: 5490 case Instruction::FMul: 5491 case Instruction::UDiv: 5492 case Instruction::SDiv: 5493 case Instruction::FDiv: 5494 case Instruction::URem: 5495 case Instruction::SRem: 5496 case Instruction::FRem: 5497 case Instruction::Shl: 5498 case Instruction::LShr: 5499 case Instruction::AShr: 5500 case Instruction::And: 5501 case Instruction::Or: 5502 case Instruction::Xor: { 5503 // Since we will replace the stride by 1 the multiplication should go away. 5504 if (I->getOpcode() == Instruction::Mul && isStrideMul(I, Legal)) 5505 return 0; 5506 // Certain instructions can be cheaper to vectorize if they have a constant 5507 // second vector operand. One example of this are shifts on x86. 5508 TargetTransformInfo::OperandValueKind Op1VK = 5509 TargetTransformInfo::OK_AnyValue; 5510 TargetTransformInfo::OperandValueKind Op2VK = 5511 TargetTransformInfo::OK_AnyValue; 5512 Value *Op2 = I->getOperand(1); 5513 5514 // Check for a splat of a constant or for a non uniform vector of constants. 5515 if (isa<ConstantInt>(Op2)) 5516 Op2VK = TargetTransformInfo::OK_UniformConstantValue; 5517 else if (isa<ConstantVector>(Op2) || isa<ConstantDataVector>(Op2)) { 5518 Op2VK = TargetTransformInfo::OK_NonUniformConstantValue; 5519 if (cast<Constant>(Op2)->getSplatValue() != NULL) 5520 Op2VK = TargetTransformInfo::OK_UniformConstantValue; 5521 } 5522 5523 return TTI.getArithmeticInstrCost(I->getOpcode(), VectorTy, Op1VK, Op2VK); 5524 } 5525 case Instruction::Select: { 5526 SelectInst *SI = cast<SelectInst>(I); 5527 const SCEV *CondSCEV = SE->getSCEV(SI->getCondition()); 5528 bool ScalarCond = (SE->isLoopInvariant(CondSCEV, TheLoop)); 5529 Type *CondTy = SI->getCondition()->getType(); 5530 if (!ScalarCond) 5531 CondTy = VectorType::get(CondTy, VF); 5532 5533 return TTI.getCmpSelInstrCost(I->getOpcode(), VectorTy, CondTy); 5534 } 5535 case Instruction::ICmp: 5536 case Instruction::FCmp: { 5537 Type *ValTy = I->getOperand(0)->getType(); 5538 VectorTy = ToVectorTy(ValTy, VF); 5539 return TTI.getCmpSelInstrCost(I->getOpcode(), VectorTy); 5540 } 5541 case Instruction::Store: 5542 case Instruction::Load: { 5543 StoreInst *SI = dyn_cast<StoreInst>(I); 5544 LoadInst *LI = dyn_cast<LoadInst>(I); 5545 Type *ValTy = (SI ? SI->getValueOperand()->getType() : 5546 LI->getType()); 5547 VectorTy = ToVectorTy(ValTy, VF); 5548 5549 unsigned Alignment = SI ? SI->getAlignment() : LI->getAlignment(); 5550 unsigned AS = SI ? SI->getPointerAddressSpace() : 5551 LI->getPointerAddressSpace(); 5552 Value *Ptr = SI ? SI->getPointerOperand() : LI->getPointerOperand(); 5553 // We add the cost of address computation here instead of with the gep 5554 // instruction because only here we know whether the operation is 5555 // scalarized. 5556 if (VF == 1) 5557 return TTI.getAddressComputationCost(VectorTy) + 5558 TTI.getMemoryOpCost(I->getOpcode(), VectorTy, Alignment, AS); 5559 5560 // Scalarized loads/stores. 5561 int ConsecutiveStride = Legal->isConsecutivePtr(Ptr); 5562 bool Reverse = ConsecutiveStride < 0; 5563 unsigned ScalarAllocatedSize = DL->getTypeAllocSize(ValTy); 5564 unsigned VectorElementSize = DL->getTypeStoreSize(VectorTy)/VF; 5565 if (!ConsecutiveStride || ScalarAllocatedSize != VectorElementSize) { 5566 bool IsComplexComputation = 5567 isLikelyComplexAddressComputation(Ptr, Legal, SE, TheLoop); 5568 unsigned Cost = 0; 5569 // The cost of extracting from the value vector and pointer vector. 5570 Type *PtrTy = ToVectorTy(Ptr->getType(), VF); 5571 for (unsigned i = 0; i < VF; ++i) { 5572 // The cost of extracting the pointer operand. 5573 Cost += TTI.getVectorInstrCost(Instruction::ExtractElement, PtrTy, i); 5574 // In case of STORE, the cost of ExtractElement from the vector. 5575 // In case of LOAD, the cost of InsertElement into the returned 5576 // vector. 5577 Cost += TTI.getVectorInstrCost(SI ? Instruction::ExtractElement : 5578 Instruction::InsertElement, 5579 VectorTy, i); 5580 } 5581 5582 // The cost of the scalar loads/stores. 5583 Cost += VF * TTI.getAddressComputationCost(PtrTy, IsComplexComputation); 5584 Cost += VF * TTI.getMemoryOpCost(I->getOpcode(), ValTy->getScalarType(), 5585 Alignment, AS); 5586 return Cost; 5587 } 5588 5589 // Wide load/stores. 5590 unsigned Cost = TTI.getAddressComputationCost(VectorTy); 5591 Cost += TTI.getMemoryOpCost(I->getOpcode(), VectorTy, Alignment, AS); 5592 5593 if (Reverse) 5594 Cost += TTI.getShuffleCost(TargetTransformInfo::SK_Reverse, 5595 VectorTy, 0); 5596 return Cost; 5597 } 5598 case Instruction::ZExt: 5599 case Instruction::SExt: 5600 case Instruction::FPToUI: 5601 case Instruction::FPToSI: 5602 case Instruction::FPExt: 5603 case Instruction::PtrToInt: 5604 case Instruction::IntToPtr: 5605 case Instruction::SIToFP: 5606 case Instruction::UIToFP: 5607 case Instruction::Trunc: 5608 case Instruction::FPTrunc: 5609 case Instruction::BitCast: { 5610 // We optimize the truncation of induction variable. 5611 // The cost of these is the same as the scalar operation. 5612 if (I->getOpcode() == Instruction::Trunc && 5613 Legal->isInductionVariable(I->getOperand(0))) 5614 return TTI.getCastInstrCost(I->getOpcode(), I->getType(), 5615 I->getOperand(0)->getType()); 5616 5617 Type *SrcVecTy = ToVectorTy(I->getOperand(0)->getType(), VF); 5618 return TTI.getCastInstrCost(I->getOpcode(), VectorTy, SrcVecTy); 5619 } 5620 case Instruction::Call: { 5621 CallInst *CI = cast<CallInst>(I); 5622 Intrinsic::ID ID = getIntrinsicIDForCall(CI, TLI); 5623 assert(ID && "Not an intrinsic call!"); 5624 Type *RetTy = ToVectorTy(CI->getType(), VF); 5625 SmallVector<Type*, 4> Tys; 5626 for (unsigned i = 0, ie = CI->getNumArgOperands(); i != ie; ++i) 5627 Tys.push_back(ToVectorTy(CI->getArgOperand(i)->getType(), VF)); 5628 return TTI.getIntrinsicInstrCost(ID, RetTy, Tys); 5629 } 5630 default: { 5631 // We are scalarizing the instruction. Return the cost of the scalar 5632 // instruction, plus the cost of insert and extract into vector 5633 // elements, times the vector width. 5634 unsigned Cost = 0; 5635 5636 if (!RetTy->isVoidTy() && VF != 1) { 5637 unsigned InsCost = TTI.getVectorInstrCost(Instruction::InsertElement, 5638 VectorTy); 5639 unsigned ExtCost = TTI.getVectorInstrCost(Instruction::ExtractElement, 5640 VectorTy); 5641 5642 // The cost of inserting the results plus extracting each one of the 5643 // operands. 5644 Cost += VF * (InsCost + ExtCost * I->getNumOperands()); 5645 } 5646 5647 // The cost of executing VF copies of the scalar instruction. This opcode 5648 // is unknown. Assume that it is the same as 'mul'. 5649 Cost += VF * TTI.getArithmeticInstrCost(Instruction::Mul, VectorTy); 5650 return Cost; 5651 } 5652 }// end of switch. 5653} 5654 5655Type* LoopVectorizationCostModel::ToVectorTy(Type *Scalar, unsigned VF) { 5656 if (Scalar->isVoidTy() || VF == 1) 5657 return Scalar; 5658 return VectorType::get(Scalar, VF); 5659} 5660 5661char LoopVectorize::ID = 0; 5662static const char lv_name[] = "Loop Vectorization"; 5663INITIALIZE_PASS_BEGIN(LoopVectorize, LV_NAME, lv_name, false, false) 5664INITIALIZE_AG_DEPENDENCY(TargetTransformInfo) 5665INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfo) 5666INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 5667INITIALIZE_PASS_DEPENDENCY(ScalarEvolution) 5668INITIALIZE_PASS_DEPENDENCY(LCSSA) 5669INITIALIZE_PASS_DEPENDENCY(LoopInfo) 5670INITIALIZE_PASS_DEPENDENCY(LoopSimplify) 5671INITIALIZE_PASS_END(LoopVectorize, LV_NAME, lv_name, false, false) 5672 5673namespace llvm { 5674 Pass *createLoopVectorizePass(bool NoUnrolling, bool AlwaysVectorize) { 5675 return new LoopVectorize(NoUnrolling, AlwaysVectorize); 5676 } 5677} 5678 5679bool LoopVectorizationCostModel::isConsecutiveLoadOrStore(Instruction *Inst) { 5680 // Check for a store. 5681 if (StoreInst *ST = dyn_cast<StoreInst>(Inst)) 5682 return Legal->isConsecutivePtr(ST->getPointerOperand()) != 0; 5683 5684 // Check for a load. 5685 if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) 5686 return Legal->isConsecutivePtr(LI->getPointerOperand()) != 0; 5687 5688 return false; 5689} 5690 5691 5692void InnerLoopUnroller::scalarizeInstruction(Instruction *Instr, 5693 bool IfPredicateStore) { 5694 assert(!Instr->getType()->isAggregateType() && "Can't handle vectors"); 5695 // Holds vector parameters or scalars, in case of uniform vals. 5696 SmallVector<VectorParts, 4> Params; 5697 5698 setDebugLocFromInst(Builder, Instr); 5699 5700 // Find all of the vectorized parameters. 5701 for (unsigned op = 0, e = Instr->getNumOperands(); op != e; ++op) { 5702 Value *SrcOp = Instr->getOperand(op); 5703 5704 // If we are accessing the old induction variable, use the new one. 5705 if (SrcOp == OldInduction) { 5706 Params.push_back(getVectorValue(SrcOp)); 5707 continue; 5708 } 5709 5710 // Try using previously calculated values. 5711 Instruction *SrcInst = dyn_cast<Instruction>(SrcOp); 5712 5713 // If the src is an instruction that appeared earlier in the basic block 5714 // then it should already be vectorized. 5715 if (SrcInst && OrigLoop->contains(SrcInst)) { 5716 assert(WidenMap.has(SrcInst) && "Source operand is unavailable"); 5717 // The parameter is a vector value from earlier. 5718 Params.push_back(WidenMap.get(SrcInst)); 5719 } else { 5720 // The parameter is a scalar from outside the loop. Maybe even a constant. 5721 VectorParts Scalars; 5722 Scalars.append(UF, SrcOp); 5723 Params.push_back(Scalars); 5724 } 5725 } 5726 5727 assert(Params.size() == Instr->getNumOperands() && 5728 "Invalid number of operands"); 5729 5730 // Does this instruction return a value ? 5731 bool IsVoidRetTy = Instr->getType()->isVoidTy(); 5732 5733 Value *UndefVec = IsVoidRetTy ? 0 : 5734 UndefValue::get(Instr->getType()); 5735 // Create a new entry in the WidenMap and initialize it to Undef or Null. 5736 VectorParts &VecResults = WidenMap.splat(Instr, UndefVec); 5737 5738 Instruction *InsertPt = Builder.GetInsertPoint(); 5739 BasicBlock *IfBlock = Builder.GetInsertBlock(); 5740 BasicBlock *CondBlock = 0; 5741 5742 VectorParts Cond; 5743 Loop *VectorLp = 0; 5744 if (IfPredicateStore) { 5745 assert(Instr->getParent()->getSinglePredecessor() && 5746 "Only support single predecessor blocks"); 5747 Cond = createEdgeMask(Instr->getParent()->getSinglePredecessor(), 5748 Instr->getParent()); 5749 VectorLp = LI->getLoopFor(IfBlock); 5750 assert(VectorLp && "Must have a loop for this block"); 5751 } 5752 5753 // For each vector unroll 'part': 5754 for (unsigned Part = 0; Part < UF; ++Part) { 5755 // For each scalar that we create: 5756 5757 // Start an "if (pred) a[i] = ..." block. 5758 Value *Cmp = 0; 5759 if (IfPredicateStore) { 5760 if (Cond[Part]->getType()->isVectorTy()) 5761 Cond[Part] = 5762 Builder.CreateExtractElement(Cond[Part], Builder.getInt32(0)); 5763 Cmp = Builder.CreateICmp(ICmpInst::ICMP_EQ, Cond[Part], 5764 ConstantInt::get(Cond[Part]->getType(), 1)); 5765 CondBlock = IfBlock->splitBasicBlock(InsertPt, "cond.store"); 5766 LoopVectorBody.push_back(CondBlock); 5767 VectorLp->addBasicBlockToLoop(CondBlock, LI->getBase()); 5768 // Update Builder with newly created basic block. 5769 Builder.SetInsertPoint(InsertPt); 5770 } 5771 5772 Instruction *Cloned = Instr->clone(); 5773 if (!IsVoidRetTy) 5774 Cloned->setName(Instr->getName() + ".cloned"); 5775 // Replace the operands of the cloned instructions with extracted scalars. 5776 for (unsigned op = 0, e = Instr->getNumOperands(); op != e; ++op) { 5777 Value *Op = Params[op][Part]; 5778 Cloned->setOperand(op, Op); 5779 } 5780 5781 // Place the cloned scalar in the new loop. 5782 Builder.Insert(Cloned); 5783 5784 // If the original scalar returns a value we need to place it in a vector 5785 // so that future users will be able to use it. 5786 if (!IsVoidRetTy) 5787 VecResults[Part] = Cloned; 5788 5789 // End if-block. 5790 if (IfPredicateStore) { 5791 BasicBlock *NewIfBlock = CondBlock->splitBasicBlock(InsertPt, "else"); 5792 LoopVectorBody.push_back(NewIfBlock); 5793 VectorLp->addBasicBlockToLoop(NewIfBlock, LI->getBase()); 5794 Builder.SetInsertPoint(InsertPt); 5795 Instruction *OldBr = IfBlock->getTerminator(); 5796 BranchInst::Create(CondBlock, NewIfBlock, Cmp, OldBr); 5797 OldBr->eraseFromParent(); 5798 IfBlock = NewIfBlock; 5799 } 5800 } 5801} 5802 5803void InnerLoopUnroller::vectorizeMemoryInstruction(Instruction *Instr) { 5804 StoreInst *SI = dyn_cast<StoreInst>(Instr); 5805 bool IfPredicateStore = (SI && Legal->blockNeedsPredication(SI->getParent())); 5806 5807 return scalarizeInstruction(Instr, IfPredicateStore); 5808} 5809 5810Value *InnerLoopUnroller::reverseVector(Value *Vec) { 5811 return Vec; 5812} 5813 5814Value *InnerLoopUnroller::getBroadcastInstrs(Value *V) { 5815 return V; 5816} 5817 5818Value *InnerLoopUnroller::getConsecutiveVector(Value* Val, int StartIdx, 5819 bool Negate) { 5820 // When unrolling and the VF is 1, we only need to add a simple scalar. 5821 Type *ITy = Val->getType(); 5822 assert(!ITy->isVectorTy() && "Val must be a scalar"); 5823 Constant *C = ConstantInt::get(ITy, StartIdx, Negate); 5824 return Builder.CreateAdd(Val, C, "induction"); 5825} 5826 5827