LoopVectorize.cpp revision 5f7d81022398f332b222552f5d980c4e3f1c542c
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. Legalization of the IR is done 12// in the codegen. However, the vectorizes uses (will use) the codegen 13// interfaces to generate IR that is likely to result in an optimal binary. 14// 15// The loop vectorizer combines consecutive loop iteration 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 helper class that checks for the legality 22// of the vectorization. 23// 3. SingleBlockLoopVectorizer - A helper class that performs the actual 24// widening of instructions. 25//===----------------------------------------------------------------------===// 26// 27// The reduction-variable vectorization is based on the paper: 28// D. Nuzman and R. Henderson. Multi-platform Auto-vectorization. 29// 30// Variable uniformity checks are inspired by: 31// Karrenberg, R. and Hack, S. Whole Function Vectorization. 32// 33// Other ideas/concepts are from: 34// A. Zaks and D. Nuzman. Autovectorization in GCC-two years later. 35// 36//===----------------------------------------------------------------------===// 37#define LV_NAME "loop-vectorize" 38#define DEBUG_TYPE LV_NAME 39#include "llvm/Constants.h" 40#include "llvm/DerivedTypes.h" 41#include "llvm/Instructions.h" 42#include "llvm/LLVMContext.h" 43#include "llvm/Pass.h" 44#include "llvm/Analysis/LoopPass.h" 45#include "llvm/Value.h" 46#include "llvm/Function.h" 47#include "llvm/Analysis/Verifier.h" 48#include "llvm/Module.h" 49#include "llvm/Type.h" 50#include "llvm/ADT/SmallVector.h" 51#include "llvm/ADT/StringExtras.h" 52#include "llvm/Analysis/AliasAnalysis.h" 53#include "llvm/Analysis/AliasSetTracker.h" 54#include "llvm/Transforms/Scalar.h" 55#include "llvm/Analysis/ScalarEvolution.h" 56#include "llvm/Analysis/ScalarEvolutionExpressions.h" 57#include "llvm/Analysis/ScalarEvolutionExpander.h" 58#include "llvm/Transforms/Utils/BasicBlockUtils.h" 59#include "llvm/Analysis/ValueTracking.h" 60#include "llvm/Analysis/LoopInfo.h" 61#include "llvm/Support/CommandLine.h" 62#include "llvm/Support/Debug.h" 63#include "llvm/Support/raw_ostream.h" 64#include "llvm/DataLayout.h" 65#include "llvm/Transforms/Utils/Local.h" 66#include <algorithm> 67using namespace llvm; 68 69static cl::opt<unsigned> 70DefaultVectorizationFactor("default-loop-vectorize-width", 71 cl::init(4), cl::Hidden, 72 cl::desc("Set the default loop vectorization width")); 73namespace { 74 75// Forward declaration. 76class LoopVectorizationLegality; 77 78/// SingleBlockLoopVectorizer vectorizes loops which contain only one basic 79/// block to a specified vectorization factor (VF). 80/// This class performs the widening of scalars into vectors, or multiple 81/// scalars. This class also implements the following features: 82/// * It inserts an epilogue loop for handling loops that don't have iteration 83/// counts that are known to be a multiple of the vectorization factor. 84/// * It handles the code generation for reduction variables. 85/// * Scalarization (implementation using scalars) of un-vectorizable 86/// instructions. 87/// SingleBlockLoopVectorizer does not perform any vectorization-legality 88/// checks, and relies on the caller to check for the different legality 89/// aspects. The SingleBlockLoopVectorizer relies on the 90/// LoopVectorizationLegality class to provide information about the induction 91/// and reduction variables that were found to a given vectorization factor. 92class SingleBlockLoopVectorizer { 93public: 94 /// Ctor. 95 SingleBlockLoopVectorizer(Loop *Orig, ScalarEvolution *Se, LoopInfo *Li, 96 LPPassManager *Lpm, unsigned VecWidth): 97 OrigLoop(Orig), SE(Se), LI(Li), LPM(Lpm), VF(VecWidth), 98 Builder(Se->getContext()), Induction(0), OldInduction(0) { } 99 100 // Perform the actual loop widening (vectorization). 101 void vectorize(LoopVectorizationLegality *Legal) { 102 ///Create a new empty loop. Unlink the old loop and connect the new one. 103 createEmptyLoop(Legal); 104 /// Widen each instruction in the old loop to a new one in the new loop. 105 /// Use the Legality module to find the induction and reduction variables. 106 vectorizeLoop(Legal); 107 // register the new loop. 108 cleanup(); 109 } 110 111private: 112 /// Create an empty loop, based on the loop ranges of the old loop. 113 void createEmptyLoop(LoopVectorizationLegality *Legal); 114 /// Copy and widen the instructions from the old loop. 115 void vectorizeLoop(LoopVectorizationLegality *Legal); 116 /// Insert the new loop to the loop hierarchy and pass manager. 117 void cleanup(); 118 119 /// This instruction is un-vectorizable. Implement it as a sequence 120 /// of scalars. 121 void scalarizeInstruction(Instruction *Instr); 122 123 /// Create a broadcast instruction. This method generates a broadcast 124 /// instruction (shuffle) for loop invariant values and for the induction 125 /// value. If this is the induction variable then we extend it to N, N+1, ... 126 /// this is needed because each iteration in the loop corresponds to a SIMD 127 /// element. 128 Value *getBroadcastInstrs(Value *V); 129 130 /// This is a helper function used by getBroadcastInstrs. It adds 0, 1, 2 .. 131 /// for each element in the vector. Starting from zero. 132 Value *getConsecutiveVector(Value* Val); 133 134 /// When we go over instructions in the basic block we rely on previous 135 /// values within the current basic block or on loop invariant values. 136 /// When we widen (vectorize) values we place them in the map. If the values 137 /// are not within the map, they have to be loop invariant, so we simply 138 /// broadcast them into a vector. 139 Value *getVectorValue(Value *V); 140 141 /// Get a uniform vector of constant integers. We use this to get 142 /// vectors of ones and zeros for the reduction code. 143 Constant* getUniformVector(unsigned Val, Type* ScalarTy); 144 145 typedef DenseMap<Value*, Value*> ValueMap; 146 147 /// The original loop. 148 Loop *OrigLoop; 149 // Scev analysis to use. 150 ScalarEvolution *SE; 151 // Loop Info. 152 LoopInfo *LI; 153 // Loop Pass Manager; 154 LPPassManager *LPM; 155 // The vectorization factor to use. 156 unsigned VF; 157 158 // The builder that we use 159 IRBuilder<> Builder; 160 161 // --- Vectorization state --- 162 163 /// Middle Block between the vector and the scalar. 164 BasicBlock *LoopMiddleBlock; 165 ///The ExitBlock of the scalar loop. 166 BasicBlock *LoopExitBlock; 167 ///The vector loop body. 168 BasicBlock *LoopVectorBody; 169 ///The scalar loop body. 170 BasicBlock *LoopScalarBody; 171 ///The first bypass block. 172 BasicBlock *LoopBypassBlock; 173 174 /// The new Induction variable which was added to the new block. 175 PHINode *Induction; 176 /// The induction variable of the old basic block. 177 PHINode *OldInduction; 178 // Maps scalars to widened vectors. 179 ValueMap WidenMap; 180}; 181 182/// LoopVectorizationLegality checks if it is legal to vectorize a loop, and 183/// to what vectorization factor. 184/// This class does not look at the profitability of vectorization, only the 185/// legality. This class has two main kinds of checks: 186/// * Memory checks - The code in canVectorizeMemory checks if vectorization 187/// will change the order of memory accesses in a way that will change the 188/// correctness of the program. 189/// * Scalars checks - The code in canVectorizeBlock checks for a number 190/// of different conditions, such as the availability of a single induction 191/// variable, that all types are supported and vectorize-able, etc. 192/// This code reflects the capabilities of SingleBlockLoopVectorizer. 193/// This class is also used by SingleBlockLoopVectorizer for identifying 194/// induction variable and the different reduction variables. 195class LoopVectorizationLegality { 196public: 197 LoopVectorizationLegality(Loop *Lp, ScalarEvolution *Se, DataLayout *Dl): 198 TheLoop(Lp), SE(Se), DL(Dl), Induction(0) { } 199 200 /// This represents the kinds of reductions that we support. 201 /// We use the enum values to hold the 'identity' value for 202 /// each operand. This value does not change the result if applied. 203 enum ReductionKind { 204 NoReduction = -1, /// Not a reduction. 205 IntegerAdd = 0, /// Sum of numbers. 206 IntegerMult = 1 /// Product of numbers. 207 }; 208 209 /// This POD struct holds information about reduction variables. 210 struct ReductionDescriptor { 211 // Default C'tor 212 ReductionDescriptor(): 213 StartValue(0), LoopExitInstr(0), Kind(NoReduction) {} 214 215 // C'tor. 216 ReductionDescriptor(Value *Start, Instruction *Exit, ReductionKind K): 217 StartValue(Start), LoopExitInstr(Exit), Kind(K) {} 218 219 // The starting value of the reduction. 220 // It does not have to be zero! 221 Value *StartValue; 222 // The instruction who's value is used outside the loop. 223 Instruction *LoopExitInstr; 224 // The kind of the reduction. 225 ReductionKind Kind; 226 }; 227 228 /// ReductionList contains the reduction descriptors for all 229 /// of the reductions that were found in the loop. 230 typedef DenseMap<PHINode*, ReductionDescriptor> ReductionList; 231 232 /// Returns the maximum vectorization factor that we *can* use to vectorize 233 /// this loop. This does not mean that it is profitable to vectorize this 234 /// loop, only that it is legal to do so. This may be a large number. We 235 /// can vectorize to any SIMD width below this number. 236 unsigned getLoopMaxVF(); 237 238 /// Returns the Induction variable. 239 PHINode *getInduction() {return Induction;} 240 241 /// Returns the reduction variables found in the loop. 242 ReductionList *getReductionVars() { return &Reductions; } 243 244 /// Check if the pointer returned by this GEP is consecutive 245 /// when the index is vectorized. This happens when the last 246 /// index of the GEP is consecutive, like the induction variable. 247 /// This check allows us to vectorize A[idx] into a wide load/store. 248 bool isConsecutiveGep(Value *Ptr); 249 250private: 251 /// Check if a single basic block loop is vectorizable. 252 /// At this point we know that this is a loop with a constant trip count 253 /// and we only need to check individual instructions. 254 bool canVectorizeBlock(BasicBlock &BB); 255 256 /// When we vectorize loops we may change the order in which 257 /// we read and write from memory. This method checks if it is 258 /// legal to vectorize the code, considering only memory constrains. 259 /// Returns true if BB is vectorizable 260 bool canVectorizeMemory(BasicBlock &BB); 261 262 // Check if a pointer value is known to be disjoint. 263 // Example: Alloca, Global, NoAlias. 264 bool isIdentifiedSafeObject(Value* Val); 265 266 /// Returns True, if 'Phi' is the kind of reduction variable for type 267 /// 'Kind'. If this is a reduction variable, it adds it to ReductionList. 268 bool AddReductionVar(PHINode *Phi, ReductionKind Kind); 269 /// Returns true if the instruction I can be a reduction variable of type 270 /// 'Kind'. 271 bool isReductionInstr(Instruction *I, ReductionKind Kind); 272 /// Returns True, if 'Phi' is an induction variable. 273 bool isInductionVariable(PHINode *Phi); 274 275 /// The loop that we evaluate. 276 Loop *TheLoop; 277 /// Scev analysis. 278 ScalarEvolution *SE; 279 /// DataLayout analysis. 280 DataLayout *DL; 281 282 // --- vectorization state --- // 283 284 /// Holds the induction variable. 285 PHINode *Induction; 286 /// Holds the reduction variables. 287 ReductionList Reductions; 288 /// Allowed outside users. This holds the reduction 289 /// vars which can be accessed from outside the loop. 290 SmallPtrSet<Value*, 4> AllowedExit; 291}; 292 293struct LoopVectorize : public LoopPass { 294 static char ID; // Pass identification, replacement for typeid 295 296 LoopVectorize() : LoopPass(ID) { 297 initializeLoopVectorizePass(*PassRegistry::getPassRegistry()); 298 } 299 300 ScalarEvolution *SE; 301 DataLayout *DL; 302 LoopInfo *LI; 303 304 virtual bool runOnLoop(Loop *L, LPPassManager &LPM) { 305 // We only vectorize innermost loops. 306 if (!L->empty()) 307 return false; 308 309 SE = &getAnalysis<ScalarEvolution>(); 310 DL = getAnalysisIfAvailable<DataLayout>(); 311 LI = &getAnalysis<LoopInfo>(); 312 313 DEBUG(dbgs() << "LV: Checking a loop in \"" << 314 L->getHeader()->getParent()->getName() << "\"\n"); 315 316 // Check if it is legal to vectorize the loop. 317 LoopVectorizationLegality LVL(L, SE, DL); 318 unsigned MaxVF = LVL.getLoopMaxVF(); 319 320 // Check that we can vectorize this loop using the chosen vectorization 321 // width. 322 if (MaxVF < DefaultVectorizationFactor) { 323 DEBUG(dbgs() << "LV: non-vectorizable MaxVF ("<< MaxVF << ").\n"); 324 return false; 325 } 326 327 DEBUG(dbgs() << "LV: Found a vectorizable loop ("<< MaxVF << ").\n"); 328 329 // If we decided that it is *legal* to vectorizer the loop then do it. 330 SingleBlockLoopVectorizer LB(L, SE, LI, &LPM, DefaultVectorizationFactor); 331 LB.vectorize(&LVL); 332 333 DEBUG(verifyFunction(*L->getHeader()->getParent())); 334 return true; 335 } 336 337 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 338 LoopPass::getAnalysisUsage(AU); 339 AU.addRequiredID(LoopSimplifyID); 340 AU.addRequiredID(LCSSAID); 341 AU.addRequired<LoopInfo>(); 342 AU.addRequired<ScalarEvolution>(); 343 } 344 345}; 346 347Value *SingleBlockLoopVectorizer::getBroadcastInstrs(Value *V) { 348 // Instructions that access the old induction variable 349 // actually want to get the new one. 350 if (V == OldInduction) 351 V = Induction; 352 // Create the types. 353 LLVMContext &C = V->getContext(); 354 Type *VTy = VectorType::get(V->getType(), VF); 355 Type *I32 = IntegerType::getInt32Ty(C); 356 Constant *Zero = ConstantInt::get(I32, 0); 357 Value *Zeros = ConstantAggregateZero::get(VectorType::get(I32, VF)); 358 Value *UndefVal = UndefValue::get(VTy); 359 // Insert the value into a new vector. 360 Value *SingleElem = Builder.CreateInsertElement(UndefVal, V, Zero); 361 // Broadcast the scalar into all locations in the vector. 362 Value *Shuf = Builder.CreateShuffleVector(SingleElem, UndefVal, Zeros, 363 "broadcast"); 364 // We are accessing the induction variable. Make sure to promote the 365 // index for each consecutive SIMD lane. This adds 0,1,2 ... to all lanes. 366 if (V == Induction) 367 return getConsecutiveVector(Shuf); 368 return Shuf; 369} 370 371Value *SingleBlockLoopVectorizer::getConsecutiveVector(Value* Val) { 372 assert(Val->getType()->isVectorTy() && "Must be a vector"); 373 assert(Val->getType()->getScalarType()->isIntegerTy() && 374 "Elem must be an integer"); 375 // Create the types. 376 Type *ITy = Val->getType()->getScalarType(); 377 VectorType *Ty = cast<VectorType>(Val->getType()); 378 unsigned VLen = Ty->getNumElements(); 379 SmallVector<Constant*, 8> Indices; 380 381 // Create a vector of consecutive numbers from zero to VF. 382 for (unsigned i = 0; i < VLen; ++i) 383 Indices.push_back(ConstantInt::get(ITy, i)); 384 385 // Add the consecutive indices to the vector value. 386 Constant *Cv = ConstantVector::get(Indices); 387 assert(Cv->getType() == Val->getType() && "Invalid consecutive vec"); 388 return Builder.CreateAdd(Val, Cv, "induction"); 389} 390 391bool LoopVectorizationLegality::isConsecutiveGep(Value *Ptr) { 392 GetElementPtrInst *Gep = dyn_cast<GetElementPtrInst>(Ptr); 393 if (!Gep) 394 return false; 395 396 unsigned NumOperands = Gep->getNumOperands(); 397 Value *LastIndex = Gep->getOperand(NumOperands - 1); 398 399 // Check that all of the gep indices are uniform except for the last. 400 for (unsigned i = 0; i < NumOperands - 1; ++i) 401 if (!SE->isLoopInvariant(SE->getSCEV(Gep->getOperand(i)), TheLoop)) 402 return false; 403 404 // We can emit wide load/stores only of the last index is the induction 405 // variable. 406 const SCEV *Last = SE->getSCEV(LastIndex); 407 if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Last)) { 408 const SCEV *Step = AR->getStepRecurrence(*SE); 409 410 // The memory is consecutive because the last index is consecutive 411 // and all other indices are loop invariant. 412 if (Step->isOne()) 413 return true; 414 } 415 416 return false; 417} 418 419Value *SingleBlockLoopVectorizer::getVectorValue(Value *V) { 420 assert(!V->getType()->isVectorTy() && "Can't widen a vector"); 421 // If we saved a vectorized copy of V, use it. 422 Value *&MapEntry = WidenMap[V]; 423 if (MapEntry) 424 return MapEntry; 425 426 // Broadcast V and save the value for future uses. 427 Value *B = getBroadcastInstrs(V); 428 MapEntry = B; 429 return B; 430} 431 432Constant* 433SingleBlockLoopVectorizer::getUniformVector(unsigned Val, Type* ScalarTy) { 434 SmallVector<Constant*, 8> Indices; 435 // Create a vector of consecutive numbers from zero to VF. 436 for (unsigned i = 0; i < VF; ++i) 437 Indices.push_back(ConstantInt::get(ScalarTy, Val)); 438 439 // Add the consecutive indices to the vector value. 440 return ConstantVector::get(Indices); 441} 442 443void SingleBlockLoopVectorizer::scalarizeInstruction(Instruction *Instr) { 444 assert(!Instr->getType()->isAggregateType() && "Can't handle vectors"); 445 // Holds vector parameters or scalars, in case of uniform vals. 446 SmallVector<Value*, 8> Params; 447 448 // Find all of the vectorized parameters. 449 for (unsigned op = 0, e = Instr->getNumOperands(); op != e; ++op) { 450 Value *SrcOp = Instr->getOperand(op); 451 452 // If we are accessing the old induction variable, use the new one. 453 if (SrcOp == OldInduction) { 454 Params.push_back(getBroadcastInstrs(Induction)); 455 continue; 456 } 457 458 // Try using previously calculated values. 459 Instruction *SrcInst = dyn_cast<Instruction>(SrcOp); 460 461 // If the src is an instruction that appeared earlier in the basic block 462 // then it should already be vectorized. 463 if (SrcInst && SrcInst->getParent() == Instr->getParent()) { 464 assert(WidenMap.count(SrcInst) && "Source operand is unavailable"); 465 // The parameter is a vector value from earlier. 466 Params.push_back(WidenMap[SrcInst]); 467 } else { 468 // The parameter is a scalar from outside the loop. Maybe even a constant. 469 Params.push_back(SrcOp); 470 } 471 } 472 473 assert(Params.size() == Instr->getNumOperands() && 474 "Invalid number of operands"); 475 476 // Does this instruction return a value ? 477 bool IsVoidRetTy = Instr->getType()->isVoidTy(); 478 Value *VecResults = 0; 479 480 // If we have a return value, create an empty vector. We place the scalarized 481 // instructions in this vector. 482 if (!IsVoidRetTy) 483 VecResults = UndefValue::get(VectorType::get(Instr->getType(), VF)); 484 485 // For each scalar that we create: 486 for (unsigned i = 0; i < VF; ++i) { 487 Instruction *Cloned = Instr->clone(); 488 if (!IsVoidRetTy) 489 Cloned->setName(Instr->getName() + ".cloned"); 490 // Replace the operands of the cloned instrucions with extracted scalars. 491 for (unsigned op = 0, e = Instr->getNumOperands(); op != e; ++op) { 492 Value *Op = Params[op]; 493 // Param is a vector. Need to extract the right lane. 494 if (Op->getType()->isVectorTy()) 495 Op = Builder.CreateExtractElement(Op, Builder.getInt32(i)); 496 Cloned->setOperand(op, Op); 497 } 498 499 // Place the cloned scalar in the new loop. 500 Builder.Insert(Cloned); 501 502 // If the original scalar returns a value we need to place it in a vector 503 // so that future users will be able to use it. 504 if (!IsVoidRetTy) 505 VecResults = Builder.CreateInsertElement(VecResults, Cloned, 506 Builder.getInt32(i)); 507 } 508 509 if (!IsVoidRetTy) 510 WidenMap[Instr] = VecResults; 511} 512 513void SingleBlockLoopVectorizer::createEmptyLoop(LoopVectorizationLegality *Legal) { 514 /* 515 In this function we generate a new loop. The new loop will contain 516 the vectorized instructions while the old loop will continue to run the 517 scalar remainder. 518 519 [ ] <-- vector loop bypass. 520 / | 521 / v 522| [ ] <-- vector pre header. 523| | 524| v 525| [ ] \ 526| [ ]_| <-- vector loop. 527| | 528 \ v 529 >[ ] <--- middle-block. 530 / | 531 / v 532| [ ] <--- new preheader. 533| | 534| v 535| [ ] \ 536| [ ]_| <-- old scalar loop to handle remainder. 537 \ | 538 \ v 539 >[ ] <-- exit block. 540 ... 541 */ 542 543 // This is the original scalar-loop preheader. 544 BasicBlock *BypassBlock = OrigLoop->getLoopPreheader(); 545 BasicBlock *ExitBlock = OrigLoop->getExitBlock(); 546 assert(ExitBlock && "Must have an exit block"); 547 548 assert(OrigLoop->getNumBlocks() == 1 && "Invalid loop"); 549 assert(BypassBlock && "Invalid loop structure"); 550 551 BasicBlock *VectorPH = 552 BypassBlock->splitBasicBlock(BypassBlock->getTerminator(), "vector.ph"); 553 BasicBlock *VecBody = VectorPH->splitBasicBlock(VectorPH->getTerminator(), 554 "vector.body"); 555 556 BasicBlock *MiddleBlock = VecBody->splitBasicBlock(VecBody->getTerminator(), 557 "middle.block"); 558 BasicBlock *ScalarPH = 559 MiddleBlock->splitBasicBlock(MiddleBlock->getTerminator(), 560 "scalar.preheader"); 561 // Find the induction variable. 562 BasicBlock *OldBasicBlock = OrigLoop->getHeader(); 563 OldInduction = Legal->getInduction(); 564 assert(OldInduction && "We must have a single phi node."); 565 Type *IdxTy = OldInduction->getType(); 566 567 // Use this IR builder to create the loop instructions (Phi, Br, Cmp) 568 // inside the loop. 569 Builder.SetInsertPoint(VecBody->getFirstInsertionPt()); 570 571 // Generate the induction variable. 572 Induction = Builder.CreatePHI(IdxTy, 2, "index"); 573 Constant *Zero = ConstantInt::get(IdxTy, 0); 574 Constant *Step = ConstantInt::get(IdxTy, VF); 575 576 // Find the loop boundaries. 577 const SCEV *ExitCount = SE->getExitCount(OrigLoop, OrigLoop->getHeader()); 578 assert(ExitCount != SE->getCouldNotCompute() && "Invalid loop count"); 579 580 // Get the total trip count from the count by adding 1. 581 ExitCount = SE->getAddExpr(ExitCount, 582 SE->getConstant(ExitCount->getType(), 1)); 583 584 // Expand the trip count and place the new instructions in the preheader. 585 // Notice that the pre-header does not change, only the loop body. 586 SCEVExpander Exp(*SE, "induction"); 587 Instruction *Loc = BypassBlock->getTerminator(); 588 589 // We may need to extend the index in case there is a type mismatch. 590 // We know that the count starts at zero and does not overflow. 591 // We are using Zext because it should be less expensive. 592 if (ExitCount->getType() != Induction->getType()) 593 ExitCount = SE->getZeroExtendExpr(ExitCount, IdxTy); 594 595 // Count holds the overall loop count (N). 596 Value *Count = Exp.expandCodeFor(ExitCount, Induction->getType(), Loc); 597 // Now we need to generate the expression for N - (N % VF), which is 598 // the part that the vectorized body will execute. 599 Constant *CIVF = ConstantInt::get(IdxTy, VF); 600 Value *R = BinaryOperator::CreateURem(Count, CIVF, "n.mod.vf", Loc); 601 Value *CountRoundDown = BinaryOperator::CreateSub(Count, R, "n.vec", Loc); 602 603 // Now, compare the new count to zero. If it is zero, jump to the scalar part. 604 Value *Cmp = CmpInst::Create(Instruction::ICmp, CmpInst::ICMP_EQ, 605 CountRoundDown, ConstantInt::getNullValue(IdxTy), 606 "cmp.zero", Loc); 607 BranchInst::Create(MiddleBlock, VectorPH, Cmp, Loc); 608 // Remove the old terminator. 609 Loc->eraseFromParent(); 610 611 // Add a check in the middle block to see if we have completed 612 // all of the iterations in the first vector loop. 613 // If (N - N%VF) == N, then we *don't* need to run the remainder. 614 Value *CmpN = CmpInst::Create(Instruction::ICmp, CmpInst::ICMP_EQ, Count, 615 CountRoundDown, "cmp.n", 616 MiddleBlock->getTerminator()); 617 618 BranchInst::Create(ExitBlock, ScalarPH, CmpN, MiddleBlock->getTerminator()); 619 // Remove the old terminator. 620 MiddleBlock->getTerminator()->eraseFromParent(); 621 622 // Create i+1 and fill the PHINode. 623 Value *NextIdx = Builder.CreateAdd(Induction, Step, "index.next"); 624 Induction->addIncoming(Zero, VectorPH); 625 Induction->addIncoming(NextIdx, VecBody); 626 // Create the compare. 627 Value *ICmp = Builder.CreateICmpEQ(NextIdx, CountRoundDown); 628 Builder.CreateCondBr(ICmp, MiddleBlock, VecBody); 629 630 // Now we have two terminators. Remove the old one from the block. 631 VecBody->getTerminator()->eraseFromParent(); 632 633 // Fix the scalar body iteration count. 634 unsigned BlockIdx = OldInduction->getBasicBlockIndex(ScalarPH); 635 OldInduction->setIncomingValue(BlockIdx, CountRoundDown); 636 637 // Get ready to start creating new instructions into the vectorized body. 638 Builder.SetInsertPoint(VecBody->getFirstInsertionPt()); 639 640 // Register the new loop. 641 Loop* Lp = new Loop(); 642 LPM->insertLoop(Lp, OrigLoop->getParentLoop()); 643 644 Lp->addBasicBlockToLoop(VecBody, LI->getBase()); 645 646 Loop *ParentLoop = OrigLoop->getParentLoop(); 647 if (ParentLoop) { 648 ParentLoop->addBasicBlockToLoop(ScalarPH, LI->getBase()); 649 ParentLoop->addBasicBlockToLoop(VectorPH, LI->getBase()); 650 ParentLoop->addBasicBlockToLoop(MiddleBlock, LI->getBase()); 651 } 652 653 // Save the state. 654 LoopMiddleBlock = MiddleBlock; 655 LoopExitBlock = ExitBlock; 656 LoopVectorBody = VecBody; 657 LoopScalarBody = OldBasicBlock; 658 LoopBypassBlock = BypassBlock; 659} 660 661void 662SingleBlockLoopVectorizer::vectorizeLoop(LoopVectorizationLegality *Legal) { 663 typedef SmallVector<PHINode*, 4> PhiVector; 664 BasicBlock &BB = *OrigLoop->getHeader(); 665 Constant *Zero = ConstantInt::get( 666 IntegerType::getInt32Ty(BB.getContext()), 0); 667 668 // In order to support reduction variables we need to be able to vectorize 669 // Phi nodes. Phi nodes have cycles, so we need to vectorize them in two 670 // steages. First, we create a new vector PHI node with no incoming edges. 671 // We use this value when we vectorize all of the instructions that use the 672 // PHI. Next, after all of the instructions in the block are complete we 673 // add the new incoming edges to the PHI. At this point all of the 674 // instructions in the basic block are vectorized, so we can use them to 675 // construct the PHI. 676 PhiVector PHIsToFix; 677 678 // For each instruction in the old loop. 679 for (BasicBlock::iterator it = BB.begin(), e = BB.end(); it != e; ++it) { 680 Instruction *Inst = it; 681 682 switch (Inst->getOpcode()) { 683 case Instruction::Br: 684 // Nothing to do for PHIs and BR, since we already took care of the 685 // loop control flow instructions. 686 continue; 687 case Instruction::PHI:{ 688 PHINode* P = cast<PHINode>(Inst); 689 // Special handling for the induction var. 690 if (OldInduction == Inst) 691 continue; 692 // This is phase one of vectorizing PHIs. 693 // This has to be a reduction variable. 694 assert(Legal->getReductionVars()->count(P) && "Not a Reduction"); 695 Type *VecTy = VectorType::get(Inst->getType(), VF); 696 WidenMap[Inst] = Builder.CreatePHI(VecTy, 2, "vec.phi"); 697 PHIsToFix.push_back(P); 698 continue; 699 } 700 case Instruction::Add: 701 case Instruction::FAdd: 702 case Instruction::Sub: 703 case Instruction::FSub: 704 case Instruction::Mul: 705 case Instruction::FMul: 706 case Instruction::UDiv: 707 case Instruction::SDiv: 708 case Instruction::FDiv: 709 case Instruction::URem: 710 case Instruction::SRem: 711 case Instruction::FRem: 712 case Instruction::Shl: 713 case Instruction::LShr: 714 case Instruction::AShr: 715 case Instruction::And: 716 case Instruction::Or: 717 case Instruction::Xor: { 718 // Just widen binops. 719 BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Inst); 720 Value *A = getVectorValue(Inst->getOperand(0)); 721 Value *B = getVectorValue(Inst->getOperand(1)); 722 // Use this vector value for all users of the original instruction. 723 WidenMap[Inst] = Builder.CreateBinOp(BinOp->getOpcode(), A, B); 724 break; 725 } 726 case Instruction::Select: { 727 // Widen selects. 728 // If the selector is loop invariant we can create a select 729 // instruction with a scalar condition. Otherwise, use vector-select. 730 Value *Cond = Inst->getOperand(0); 731 bool InvariantCond = SE->isLoopInvariant(SE->getSCEV(Cond), OrigLoop); 732 733 // The condition can be loop invariant but still defined inside the 734 // loop. This means that we can't just use the original 'cond' value. 735 // We have to take the 'vectorized' value and pick the first lane. 736 // Instcombine will make this a no-op. 737 Cond = getVectorValue(Cond); 738 if (InvariantCond) 739 Cond = Builder.CreateExtractElement(Cond, Builder.getInt32(0)); 740 741 Value *Op0 = getVectorValue(Inst->getOperand(1)); 742 Value *Op1 = getVectorValue(Inst->getOperand(2)); 743 WidenMap[Inst] = Builder.CreateSelect(Cond, Op0, Op1); 744 break; 745 } 746 747 case Instruction::ICmp: 748 case Instruction::FCmp: { 749 // Widen compares. Generate vector compares. 750 bool FCmp = (Inst->getOpcode() == Instruction::FCmp); 751 CmpInst *Cmp = dyn_cast<CmpInst>(Inst); 752 Value *A = getVectorValue(Inst->getOperand(0)); 753 Value *B = getVectorValue(Inst->getOperand(1)); 754 if (FCmp) 755 WidenMap[Inst] = Builder.CreateFCmp(Cmp->getPredicate(), A, B); 756 else 757 WidenMap[Inst] = Builder.CreateICmp(Cmp->getPredicate(), A, B); 758 break; 759 } 760 761 case Instruction::Store: { 762 // Attempt to issue a wide store. 763 StoreInst *SI = dyn_cast<StoreInst>(Inst); 764 Type *StTy = VectorType::get(SI->getValueOperand()->getType(), VF); 765 Value *Ptr = SI->getPointerOperand(); 766 unsigned Alignment = SI->getAlignment(); 767 GetElementPtrInst *Gep = dyn_cast<GetElementPtrInst>(Ptr); 768 // This store does not use GEPs. 769 if (!Legal->isConsecutiveGep(Gep)) { 770 scalarizeInstruction(Inst); 771 break; 772 } 773 774 // The last index does not have to be the induction. It can be 775 // consecutive and be a function of the index. For example A[I+1]; 776 unsigned NumOperands = Gep->getNumOperands(); 777 Value *LastIndex = getVectorValue(Gep->getOperand(NumOperands -1)); 778 LastIndex = Builder.CreateExtractElement(LastIndex, Builder.getInt32(0)); 779 780 // Create the new GEP with the new induction variable. 781 GetElementPtrInst *Gep2 = cast<GetElementPtrInst>(Gep->clone()); 782 Gep2->setOperand(NumOperands - 1, LastIndex); 783 Ptr = Builder.Insert(Gep2); 784 Ptr = Builder.CreateBitCast(Ptr, StTy->getPointerTo()); 785 Value *Val = getVectorValue(SI->getValueOperand()); 786 Builder.CreateStore(Val, Ptr)->setAlignment(Alignment); 787 break; 788 } 789 case Instruction::Load: { 790 // Attempt to issue a wide load. 791 LoadInst *LI = dyn_cast<LoadInst>(Inst); 792 Type *RetTy = VectorType::get(LI->getType(), VF); 793 Value *Ptr = LI->getPointerOperand(); 794 unsigned Alignment = LI->getAlignment(); 795 GetElementPtrInst *Gep = dyn_cast<GetElementPtrInst>(Ptr); 796 797 // We don't have a gep. Scalarize the load. 798 if (!Legal->isConsecutiveGep(Gep)) { 799 scalarizeInstruction(Inst); 800 break; 801 } 802 803 // The last index does not have to be the induction. It can be 804 // consecutive and be a function of the index. For example A[I+1]; 805 unsigned NumOperands = Gep->getNumOperands(); 806 Value *LastIndex = getVectorValue(Gep->getOperand(NumOperands -1)); 807 LastIndex = Builder.CreateExtractElement(LastIndex, Builder.getInt32(0)); 808 809 // Create the new GEP with the new induction variable. 810 GetElementPtrInst *Gep2 = cast<GetElementPtrInst>(Gep->clone()); 811 Gep2->setOperand(NumOperands - 1, LastIndex); 812 Ptr = Builder.Insert(Gep2); 813 Ptr = Builder.CreateBitCast(Ptr, RetTy->getPointerTo()); 814 LI = Builder.CreateLoad(Ptr); 815 LI->setAlignment(Alignment); 816 // Use this vector value for all users of the load. 817 WidenMap[Inst] = LI; 818 break; 819 } 820 case Instruction::ZExt: 821 case Instruction::SExt: 822 case Instruction::FPToUI: 823 case Instruction::FPToSI: 824 case Instruction::FPExt: 825 case Instruction::PtrToInt: 826 case Instruction::IntToPtr: 827 case Instruction::SIToFP: 828 case Instruction::UIToFP: 829 case Instruction::Trunc: 830 case Instruction::FPTrunc: 831 case Instruction::BitCast: { 832 /// Vectorize bitcasts. 833 CastInst *CI = dyn_cast<CastInst>(Inst); 834 Value *A = getVectorValue(Inst->getOperand(0)); 835 Type *DestTy = VectorType::get(CI->getType()->getScalarType(), VF); 836 WidenMap[Inst] = Builder.CreateCast(CI->getOpcode(), A, DestTy); 837 break; 838 } 839 840 default: 841 /// All other instructions are unsupported. Scalarize them. 842 scalarizeInstruction(Inst); 843 break; 844 }// end of switch. 845 }// end of for_each instr. 846 847 // At this point every instruction in the original loop is widended to 848 // a vector form. We are almost done. Now, we need to fix the PHI nodes 849 // that we vectorized. The PHI nodes are currently empty because we did 850 // not want to introduce cycles. Notice that the remaining PHI nodes 851 // that we need to fix are reduction variables. 852 853 // Create the 'reduced' values for each of the induction vars. 854 // The reduced values are the vector values that we scalarize and combine 855 // after the loop is finished. 856 for (PhiVector::iterator it = PHIsToFix.begin(), e = PHIsToFix.end(); 857 it != e; ++it) { 858 PHINode *RdxPhi = *it; 859 PHINode *VecRdxPhi = dyn_cast<PHINode>(WidenMap[RdxPhi]); 860 assert(RdxPhi && "Unable to recover vectorized PHI"); 861 862 // Find the reduction variable descriptor. 863 assert(Legal->getReductionVars()->count(RdxPhi) && 864 "Unable to find the reduction variable"); 865 LoopVectorizationLegality::ReductionDescriptor RdxDesc = 866 (*Legal->getReductionVars())[RdxPhi]; 867 868 // We need to generate a reduction vector from the incoming scalar. 869 // To do so, we need to generate the 'identity' vector and overide 870 // one of the elements with the incoming scalar reduction. We need 871 // to do it in the vector-loop preheader. 872 Builder.SetInsertPoint(LoopBypassBlock->getTerminator()); 873 874 // This is the vector-clone of the value that leaves the loop. 875 Value *VectorExit = getVectorValue(RdxDesc.LoopExitInstr); 876 Type *VecTy = VectorExit->getType(); 877 878 // Find the reduction identity variable. The value of the enum is the 879 // identity. Zero for addition. One for Multiplication. 880 unsigned IdentitySclr = RdxDesc.Kind; 881 Constant *Identity = getUniformVector(IdentitySclr, 882 VecTy->getScalarType()); 883 884 // This vector is the Identity vector where the first element is the 885 // incoming scalar reduction. 886 Value *VectorStart = Builder.CreateInsertElement(Identity, 887 RdxDesc.StartValue, Zero); 888 889 890 // Fix the vector-loop phi. 891 // We created the induction variable so we know that the 892 // preheader is the first entry. 893 BasicBlock *VecPreheader = Induction->getIncomingBlock(0); 894 895 // Reductions do not have to start at zero. They can start with 896 // any loop invariant values. 897 VecRdxPhi->addIncoming(VectorStart, VecPreheader); 898 unsigned SelfEdgeIdx = (RdxPhi)->getBasicBlockIndex(LoopScalarBody); 899 Value *Val = getVectorValue(RdxPhi->getIncomingValue(SelfEdgeIdx)); 900 VecRdxPhi->addIncoming(Val, LoopVectorBody); 901 902 // Before each round, move the insertion point right between 903 // the PHIs and the values we are going to write. 904 // This allows us to write both PHINodes and the extractelement 905 // instructions. 906 Builder.SetInsertPoint(LoopMiddleBlock->getFirstInsertionPt()); 907 908 // This PHINode contains the vectorized reduction variable, or 909 // the initial value vector, if we bypass the vector loop. 910 PHINode *NewPhi = Builder.CreatePHI(VecTy, 2, "rdx.vec.exit.phi"); 911 NewPhi->addIncoming(VectorStart, LoopBypassBlock); 912 NewPhi->addIncoming(getVectorValue(RdxDesc.LoopExitInstr), LoopVectorBody); 913 914 // Extract the first scalar. 915 Value *Scalar0 = 916 Builder.CreateExtractElement(NewPhi, Builder.getInt32(0)); 917 // Extract and sum the remaining vector elements. 918 for (unsigned i=1; i < VF; ++i) { 919 Value *Scalar1 = 920 Builder.CreateExtractElement(NewPhi, Builder.getInt32(i)); 921 if (RdxDesc.Kind == LoopVectorizationLegality::IntegerAdd) { 922 Scalar0 = Builder.CreateAdd(Scalar0, Scalar1); 923 } else { 924 Scalar0 = Builder.CreateMul(Scalar0, Scalar1); 925 } 926 } 927 928 // Now, we need to fix the users of the reduction variable 929 // inside and outside of the scalar remainder loop. 930 // We know that the loop is in LCSSA form. We need to update the 931 // PHI nodes in the exit blocks. 932 for (BasicBlock::iterator LEI = LoopExitBlock->begin(), 933 LEE = LoopExitBlock->end(); LEI != LEE; ++LEI) { 934 PHINode *LCSSAPhi = dyn_cast<PHINode>(LEI); 935 if (!LCSSAPhi) continue; 936 937 // All PHINodes need to have a single entry edge, or two if 938 // we already fixed them. 939 assert(LCSSAPhi->getNumIncomingValues() < 3 && "Invalid LCSSA PHI"); 940 941 // We found our reduction value exit-PHI. Update it with the 942 // incoming bypass edge. 943 if (LCSSAPhi->getIncomingValue(0) == RdxDesc.LoopExitInstr) { 944 // Add an edge coming from the bypass. 945 LCSSAPhi->addIncoming(Scalar0, LoopMiddleBlock); 946 break; 947 } 948 }// end of the LCSSA phi scan. 949 950 // Fix the scalar loop reduction variable with the incoming reduction sum 951 // from the vector body and from the backedge value. 952 int IncomingEdgeBlockIdx = (RdxPhi)->getBasicBlockIndex(LoopScalarBody); 953 int SelfEdgeBlockIdx = (IncomingEdgeBlockIdx ? 0 : 1); // The other block. 954 (RdxPhi)->setIncomingValue(SelfEdgeBlockIdx, Scalar0); 955 (RdxPhi)->setIncomingValue(IncomingEdgeBlockIdx, RdxDesc.LoopExitInstr); 956 }// end of for each redux variable. 957} 958 959void SingleBlockLoopVectorizer::cleanup() { 960 // The original basic block. 961 SE->forgetLoop(OrigLoop); 962} 963 964unsigned LoopVectorizationLegality::getLoopMaxVF() { 965 if (!TheLoop->getLoopPreheader()) { 966 assert(false && "No preheader!!"); 967 DEBUG(dbgs() << "LV: Loop not normalized." << "\n"); 968 return 1; 969 } 970 971 // We can only vectorize single basic block loops. 972 unsigned NumBlocks = TheLoop->getNumBlocks(); 973 if (NumBlocks != 1) { 974 DEBUG(dbgs() << "LV: Too many blocks:" << NumBlocks << "\n"); 975 return 1; 976 } 977 978 // We need to have a loop header. 979 BasicBlock *BB = TheLoop->getHeader(); 980 DEBUG(dbgs() << "LV: Found a loop: " << BB->getName() << "\n"); 981 982 // Go over each instruction and look at memory deps. 983 if (!canVectorizeBlock(*BB)) { 984 DEBUG(dbgs() << "LV: Can't vectorize this loop header\n"); 985 return 1; 986 } 987 988 // ScalarEvolution needs to be able to find the exit count. 989 const SCEV *ExitCount = SE->getExitCount(TheLoop, BB); 990 if (ExitCount == SE->getCouldNotCompute()) { 991 DEBUG(dbgs() << "LV: SCEV could not compute the loop exit count.\n"); 992 return 1; 993 } 994 995 DEBUG(dbgs() << "LV: We can vectorize this loop!\n"); 996 997 // Okay! We can vectorize. At this point we don't have any other mem analysis 998 // which may limit our maximum vectorization factor, so just return the 999 // maximum SIMD size. 1000 return DefaultVectorizationFactor; 1001} 1002 1003bool LoopVectorizationLegality::canVectorizeBlock(BasicBlock &BB) { 1004 // Scan the instructions in the block and look for hazards. 1005 for (BasicBlock::iterator it = BB.begin(), e = BB.end(); it != e; ++it) { 1006 Instruction *I = it; 1007 1008 PHINode *Phi = dyn_cast<PHINode>(I); 1009 if (Phi) { 1010 // This should not happen because the loop should be normalized. 1011 if (Phi->getNumIncomingValues() != 2) { 1012 DEBUG(dbgs() << "LV: Found an invalid PHI.\n"); 1013 return false; 1014 } 1015 // We only look at integer phi nodes. 1016 if (!Phi->getType()->isIntegerTy()) { 1017 DEBUG(dbgs() << "LV: Found an non-int PHI.\n"); 1018 return false; 1019 } 1020 1021 if (isInductionVariable(Phi)) { 1022 if (Induction) { 1023 DEBUG(dbgs() << "LV: Found too many inductions."<< *Phi <<"\n"); 1024 return false; 1025 } 1026 DEBUG(dbgs() << "LV: Found the induction PHI."<< *Phi <<"\n"); 1027 Induction = Phi; 1028 continue; 1029 } 1030 if (AddReductionVar(Phi, IntegerAdd)) { 1031 DEBUG(dbgs() << "LV: Found an ADD reduction PHI."<< *Phi <<"\n"); 1032 continue; 1033 } 1034 if (AddReductionVar(Phi, IntegerMult)) { 1035 DEBUG(dbgs() << "LV: Found an Mult reduction PHI."<< *Phi <<"\n"); 1036 continue; 1037 } 1038 1039 DEBUG(dbgs() << "LV: Found an unidentified PHI."<< *Phi <<"\n"); 1040 return false; 1041 }// end of PHI handling 1042 1043 // We still don't handle functions. 1044 CallInst *CI = dyn_cast<CallInst>(I); 1045 if (CI) { 1046 DEBUG(dbgs() << "LV: Found a call site:"<< 1047 CI->getCalledFunction()->getName() << "\n"); 1048 return false; 1049 } 1050 1051 // We do not re-vectorize vectors. 1052 if (!VectorType::isValidElementType(I->getType()) && 1053 !I->getType()->isVoidTy()) { 1054 DEBUG(dbgs() << "LV: Found unvectorizable type." << "\n"); 1055 return false; 1056 } 1057 1058 // Reduction instructions are allowed to have exit users. 1059 // All other instructions must not have external users. 1060 if (!AllowedExit.count(I)) 1061 //Check that all of the users of the loop are inside the BB. 1062 for (Value::use_iterator it = I->use_begin(), e = I->use_end(); 1063 it != e; ++it) { 1064 Instruction *U = cast<Instruction>(*it); 1065 // This user may be a reduction exit value. 1066 BasicBlock *Parent = U->getParent(); 1067 if (Parent != &BB) { 1068 DEBUG(dbgs() << "LV: Found an outside user for : "<< *U << "\n"); 1069 return false; 1070 } 1071 } 1072 } // next instr. 1073 1074 if (!Induction) { 1075 DEBUG(dbgs() << "LV: Did not find an induction var.\n"); 1076 return false; 1077 } 1078 1079 // If the memory dependencies do not prevent us from 1080 // vectorizing, then vectorize. 1081 return canVectorizeMemory(BB); 1082} 1083 1084bool LoopVectorizationLegality::canVectorizeMemory(BasicBlock &BB) { 1085 typedef SmallVector<Value*, 16> ValueVector; 1086 typedef SmallPtrSet<Value*, 16> ValueSet; 1087 // Holds the Load and Store *instructions*. 1088 ValueVector Loads; 1089 ValueVector Stores; 1090 1091 // Scan the BB and collect legal loads and stores. 1092 for (BasicBlock::iterator it = BB.begin(), e = BB.end(); it != e; ++it) { 1093 Instruction *I = it; 1094 1095 // If this is a load, save it. If this instruction can read from memory 1096 // but is not a load, then we quit. Notice that we don't handle function 1097 // calls that read or write. 1098 if (I->mayReadFromMemory()) { 1099 LoadInst *Ld = dyn_cast<LoadInst>(I); 1100 if (!Ld) return false; 1101 if (!Ld->isSimple()) { 1102 DEBUG(dbgs() << "LV: Found a non-simple load.\n"); 1103 return false; 1104 } 1105 Loads.push_back(Ld); 1106 continue; 1107 } 1108 1109 // Save store instructions. Abort if other instructions write to memory. 1110 if (I->mayWriteToMemory()) { 1111 StoreInst *St = dyn_cast<StoreInst>(I); 1112 if (!St) return false; 1113 if (!St->isSimple()) { 1114 DEBUG(dbgs() << "LV: Found a non-simple store.\n"); 1115 return false; 1116 } 1117 Stores.push_back(St); 1118 } 1119 } // next instr. 1120 1121 // Now we have two lists that hold the loads and the stores. 1122 // Next, we find the pointers that they use. 1123 1124 // Check if we see any stores. If there are no stores, then we don't 1125 // care if the pointers are *restrict*. 1126 if (!Stores.size()) { 1127 DEBUG(dbgs() << "LV: Found a read-only loop!\n"); 1128 return true; 1129 } 1130 1131 // Holds the read and read-write *pointers* that we find. 1132 ValueVector Reads; 1133 ValueVector ReadWrites; 1134 1135 // Holds the analyzed pointers. We don't want to call GetUnderlyingObjects 1136 // multiple times on the same object. If the ptr is accessed twice, once 1137 // for read and once for write, it will only appear once (on the write 1138 // list). This is okay, since we are going to check for conflicts between 1139 // writes and between reads and writes, but not between reads and reads. 1140 ValueSet Seen; 1141 1142 ValueVector::iterator I, IE; 1143 for (I = Stores.begin(), IE = Stores.end(); I != IE; ++I) { 1144 StoreInst *ST = dyn_cast<StoreInst>(*I); 1145 assert(ST && "Bad StoreInst"); 1146 Value* Ptr = ST->getPointerOperand(); 1147 // If we did *not* see this pointer before, insert it to 1148 // the read-write list. At this phase it is only a 'write' list. 1149 if (Seen.insert(Ptr)) 1150 ReadWrites.push_back(Ptr); 1151 } 1152 1153 for (I = Loads.begin(), IE = Loads.end(); I != IE; ++I) { 1154 LoadInst *LD = dyn_cast<LoadInst>(*I); 1155 assert(LD && "Bad LoadInst"); 1156 Value* Ptr = LD->getPointerOperand(); 1157 // If we did *not* see this pointer before, insert it to the 1158 // read list. If we *did* see it before, then it is already in 1159 // the read-write list. This allows us to vectorize expressions 1160 // such as A[i] += x; Because the address of A[i] is a read-write 1161 // pointer. This only works if the index of A[i] is consecutive. 1162 // If the address of i is unknown (for example A[B[i]]) then we may 1163 // read a few words, modify, and write a few words, and some of the 1164 // words may be written to the same address. 1165 if (Seen.insert(Ptr) || !isConsecutiveGep(Ptr)) 1166 Reads.push_back(Ptr); 1167 } 1168 1169 // Now that the pointers are in two lists (Reads and ReadWrites), we 1170 // can check that there are no conflicts between each of the writes and 1171 // between the writes to the reads. 1172 ValueSet WriteObjects; 1173 ValueVector TempObjects; 1174 1175 // Check that the read-writes do not conflict with other read-write 1176 // pointers. 1177 for (I = ReadWrites.begin(), IE = ReadWrites.end(); I != IE; ++I) { 1178 GetUnderlyingObjects(*I, TempObjects, DL); 1179 for (ValueVector::iterator it=TempObjects.begin(), e=TempObjects.end(); 1180 it != e; ++it) { 1181 if (!isIdentifiedSafeObject(*it)) { 1182 DEBUG(dbgs() << "LV: Found an unidentified write ptr:"<< **it <<"\n"); 1183 return false; 1184 } 1185 if (!WriteObjects.insert(*it)) { 1186 DEBUG(dbgs() << "LV: Found a possible write-write reorder:" 1187 << **it <<"\n"); 1188 return false; 1189 } 1190 } 1191 TempObjects.clear(); 1192 } 1193 1194 /// Check that the reads don't conflict with the read-writes. 1195 for (I = Reads.begin(), IE = Reads.end(); I != IE; ++I) { 1196 GetUnderlyingObjects(*I, TempObjects, DL); 1197 for (ValueVector::iterator it=TempObjects.begin(), e=TempObjects.end(); 1198 it != e; ++it) { 1199 if (!isIdentifiedSafeObject(*it)) { 1200 DEBUG(dbgs() << "LV: Found an unidentified read ptr:"<< **it <<"\n"); 1201 return false; 1202 } 1203 if (WriteObjects.count(*it)) { 1204 DEBUG(dbgs() << "LV: Found a possible read/write reorder:" 1205 << **it <<"\n"); 1206 return false; 1207 } 1208 } 1209 TempObjects.clear(); 1210 } 1211 1212 // All is okay. 1213 return true; 1214} 1215 1216/// Checks if the value is a Global variable or if it is an Arguments 1217/// marked with the NoAlias attribute. 1218bool LoopVectorizationLegality::isIdentifiedSafeObject(Value* Val) { 1219 assert(Val && "Invalid value"); 1220 if (isa<GlobalValue>(Val)) 1221 return true; 1222 if (isa<AllocaInst>(Val)) 1223 return true; 1224 if (Argument *A = dyn_cast<Argument>(Val)) 1225 return A->hasNoAliasAttr(); 1226 return false; 1227} 1228 1229bool LoopVectorizationLegality::AddReductionVar(PHINode *Phi, 1230 ReductionKind Kind) { 1231 if (Phi->getNumIncomingValues() != 2) 1232 return false; 1233 1234 // Find the possible incoming reduction variable. 1235 BasicBlock *BB = Phi->getParent(); 1236 int SelfEdgeIdx = Phi->getBasicBlockIndex(BB); 1237 int InEdgeBlockIdx = (SelfEdgeIdx ? 0 : 1); // The other entry. 1238 Value *RdxStart = Phi->getIncomingValue(InEdgeBlockIdx); 1239 1240 // ExitInstruction is the single value which is used outside the loop. 1241 // We only allow for a single reduction value to be used outside the loop. 1242 // This includes users of the reduction, variables (which form a cycle 1243 // which ends in the phi node). 1244 Instruction *ExitInstruction = 0; 1245 1246 // Iter is our iterator. We start with the PHI node and scan for all of the 1247 // users of this instruction. All users must be instructions which can be 1248 // used as reduction variables (such as ADD). We may have a single 1249 // out-of-block user. They cycle must end with the original PHI. 1250 // Also, we can't have multiple block-local users. 1251 Instruction *Iter = Phi; 1252 while (true) { 1253 // Any reduction instr must be of one of the allowed kinds. 1254 if (!isReductionInstr(Iter, Kind)) 1255 return false; 1256 1257 // Did we found a user inside this block ? 1258 bool FoundInBlockUser = false; 1259 // Did we reach the initial PHI node ? 1260 bool FoundStartPHI = false; 1261 1262 // If the instruction has no users then this is a broken 1263 // chain and can't be a reduction variable. 1264 if (Iter->use_empty()) 1265 return false; 1266 1267 // For each of the *users* of iter. 1268 for (Value::use_iterator it = Iter->use_begin(), e = Iter->use_end(); 1269 it != e; ++it) { 1270 Instruction *U = cast<Instruction>(*it); 1271 // We already know that the PHI is a user. 1272 if (U == Phi) { 1273 FoundStartPHI = true; 1274 continue; 1275 } 1276 // Check if we found the exit user. 1277 BasicBlock *Parent = U->getParent(); 1278 if (Parent != BB) { 1279 // We must have a single exit instruction. 1280 if (ExitInstruction != 0) 1281 return false; 1282 ExitInstruction = Iter; 1283 } 1284 // We can't have multiple inside users. 1285 if (FoundInBlockUser) 1286 return false; 1287 FoundInBlockUser = true; 1288 Iter = U; 1289 } 1290 1291 // We found a reduction var if we have reached the original 1292 // phi node and we only have a single instruction with out-of-loop 1293 // users. 1294 if (FoundStartPHI && ExitInstruction) { 1295 // This instruction is allowed to have out-of-loop users. 1296 AllowedExit.insert(ExitInstruction); 1297 1298 // Save the description of this reduction variable. 1299 ReductionDescriptor RD(RdxStart, ExitInstruction, Kind); 1300 Reductions[Phi] = RD; 1301 return true; 1302 } 1303 } 1304} 1305 1306bool 1307LoopVectorizationLegality::isReductionInstr(Instruction *I, 1308 ReductionKind Kind) { 1309 switch (I->getOpcode()) { 1310 default: 1311 return false; 1312 case Instruction::PHI: 1313 // possibly. 1314 return true; 1315 case Instruction::Add: 1316 case Instruction::Sub: 1317 return Kind == IntegerAdd; 1318 case Instruction::Mul: 1319 case Instruction::UDiv: 1320 case Instruction::SDiv: 1321 return Kind == IntegerMult; 1322 } 1323} 1324 1325bool LoopVectorizationLegality::isInductionVariable(PHINode *Phi) { 1326 // Check that the PHI is consecutive and starts at zero. 1327 const SCEV *PhiScev = SE->getSCEV(Phi); 1328 const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(PhiScev); 1329 if (!AR) { 1330 DEBUG(dbgs() << "LV: PHI is not a poly recurrence.\n"); 1331 return false; 1332 } 1333 const SCEV *Step = AR->getStepRecurrence(*SE); 1334 const SCEV *Start = AR->getStart(); 1335 1336 if (!Step->isOne() || !Start->isZero()) { 1337 DEBUG(dbgs() << "LV: PHI does not start at zero or steps by one.\n"); 1338 return false; 1339 } 1340 return true; 1341} 1342 1343} // namespace 1344 1345char LoopVectorize::ID = 0; 1346static const char lv_name[] = "Loop Vectorization"; 1347INITIALIZE_PASS_BEGIN(LoopVectorize, LV_NAME, lv_name, false, false) 1348INITIALIZE_AG_DEPENDENCY(AliasAnalysis) 1349INITIALIZE_PASS_DEPENDENCY(ScalarEvolution) 1350INITIALIZE_PASS_DEPENDENCY(LoopSimplify) 1351INITIALIZE_PASS_END(LoopVectorize, LV_NAME, lv_name, false, false) 1352 1353namespace llvm { 1354 Pass *createLoopVectorizePass() { 1355 return new LoopVectorize(); 1356 } 1357} 1358 1359