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