1de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar//===----- LoadStoreVectorizer.cpp - GPU Load & Store Vectorizer ----------===// 2de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// 3de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// The LLVM Compiler Infrastructure 4de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// 5de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// This file is distributed under the University of Illinois Open Source 6de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// License. See LICENSE.TXT for details. 7de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// 8de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar//===----------------------------------------------------------------------===// 9de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// 10de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar//===----------------------------------------------------------------------===// 11de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 12de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar#include "llvm/ADT/MapVector.h" 13de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar#include "llvm/ADT/PostOrderIterator.h" 14de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar#include "llvm/ADT/SetVector.h" 15de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar#include "llvm/ADT/Statistic.h" 16de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar#include "llvm/ADT/Triple.h" 17de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar#include "llvm/Analysis/AliasAnalysis.h" 18de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar#include "llvm/Analysis/ScalarEvolution.h" 19de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar#include "llvm/Analysis/ScalarEvolutionExpressions.h" 20de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar#include "llvm/Analysis/TargetTransformInfo.h" 21de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar#include "llvm/Analysis/ValueTracking.h" 22de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar#include "llvm/Analysis/VectorUtils.h" 23de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar#include "llvm/IR/DataLayout.h" 24de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar#include "llvm/IR/Dominators.h" 25de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar#include "llvm/IR/IRBuilder.h" 26de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar#include "llvm/IR/Instructions.h" 27de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar#include "llvm/IR/Module.h" 28de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar#include "llvm/IR/Type.h" 29de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar#include "llvm/IR/Value.h" 30de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar#include "llvm/Support/CommandLine.h" 31de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar#include "llvm/Support/Debug.h" 32de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar#include "llvm/Support/raw_ostream.h" 33de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar#include "llvm/Transforms/Vectorize.h" 34de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 35de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarusing namespace llvm; 36de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 37de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar#define DEBUG_TYPE "load-store-vectorizer" 38de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga NainarSTATISTIC(NumVectorInstructions, "Number of vector accesses generated"); 39de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga NainarSTATISTIC(NumScalarsVectorized, "Number of scalar accesses vectorized"); 40de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 41de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarnamespace { 42de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 43de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// TODO: Remove this 44de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarstatic const unsigned TargetBaseAlign = 4; 45de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 46de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarclass Vectorizer { 47de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar typedef SmallVector<Value *, 8> ValueList; 48de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar typedef MapVector<Value *, ValueList> ValueListMap; 49de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 50de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Function &F; 51de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar AliasAnalysis &AA; 52de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar DominatorTree &DT; 53de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar ScalarEvolution &SE; 54de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar TargetTransformInfo &TTI; 55de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar const DataLayout &DL; 56de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar IRBuilder<> Builder; 57de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar ValueListMap StoreRefs; 58de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar ValueListMap LoadRefs; 59de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 60de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarpublic: 61de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Vectorizer(Function &F, AliasAnalysis &AA, DominatorTree &DT, 62de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar ScalarEvolution &SE, TargetTransformInfo &TTI) 63de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar : F(F), AA(AA), DT(DT), SE(SE), TTI(TTI), 64de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar DL(F.getParent()->getDataLayout()), Builder(SE.getContext()) {} 65de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 66de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar bool run(); 67de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 68de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarprivate: 69de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Value *getPointerOperand(Value *I); 70de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 71de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar unsigned getPointerAddressSpace(Value *I); 72de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 73de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar unsigned getAlignment(LoadInst *LI) const { 74de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar unsigned Align = LI->getAlignment(); 75de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (Align != 0) 76de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return Align; 77de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 78de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return DL.getABITypeAlignment(LI->getType()); 79de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 80de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 81de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar unsigned getAlignment(StoreInst *SI) const { 82de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar unsigned Align = SI->getAlignment(); 83de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (Align != 0) 84de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return Align; 85de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 86de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return DL.getABITypeAlignment(SI->getValueOperand()->getType()); 87de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 88de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 89de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar bool isConsecutiveAccess(Value *A, Value *B); 90de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 91de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// After vectorization, reorder the instructions that I depends on 92de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// (the instructions defining its operands), to ensure they dominate I. 93de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar void reorder(Instruction *I); 94de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 95de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// Returns the first and the last instructions in Chain. 96de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar std::pair<BasicBlock::iterator, BasicBlock::iterator> 97de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar getBoundaryInstrs(ArrayRef<Value *> Chain); 98de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 99de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// Erases the original instructions after vectorizing. 100de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar void eraseInstructions(ArrayRef<Value *> Chain); 101de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 102de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// "Legalize" the vector type that would be produced by combining \p 103de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// ElementSizeBits elements in \p Chain. Break into two pieces such that the 104de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// total size of each piece is 1, 2 or a multiple of 4 bytes. \p Chain is 105de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// expected to have more than 4 elements. 106de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar std::pair<ArrayRef<Value *>, ArrayRef<Value *>> 107de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar splitOddVectorElts(ArrayRef<Value *> Chain, unsigned ElementSizeBits); 108de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 109de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// Checks for instructions which may affect the memory accessed 110de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// in the chain between \p From and \p To. Returns Index, where 111de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// \p Chain[0, Index) is the largest vectorizable chain prefix. 112de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// The elements of \p Chain should be all loads or all stores. 113de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar unsigned getVectorizablePrefixEndIdx(ArrayRef<Value *> Chain, 114de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar BasicBlock::iterator From, 115de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar BasicBlock::iterator To); 116de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 117de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// Collects load and store instructions to vectorize. 118de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar void collectInstructions(BasicBlock *BB); 119de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 120de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// Processes the collected instructions, the \p Map. The elements of \p Map 121de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// should be all loads or all stores. 122de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar bool vectorizeChains(ValueListMap &Map); 123de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 124de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// Finds the load/stores to consecutive memory addresses and vectorizes them. 125de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar bool vectorizeInstructions(ArrayRef<Value *> Instrs); 126de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 127de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// Vectorizes the load instructions in Chain. 128de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar bool vectorizeLoadChain(ArrayRef<Value *> Chain, 129de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar SmallPtrSet<Value *, 16> *InstructionsProcessed); 130de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 131de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// Vectorizes the store instructions in Chain. 132de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar bool vectorizeStoreChain(ArrayRef<Value *> Chain, 133de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar SmallPtrSet<Value *, 16> *InstructionsProcessed); 134de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 135de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// Check if this load/store access is misaligned accesses 136de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar bool accessIsMisaligned(unsigned SzInBytes, unsigned AddressSpace, 137de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar unsigned Alignment); 138de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar}; 139de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 140de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarclass LoadStoreVectorizer : public FunctionPass { 141de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarpublic: 142de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar static char ID; 143de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 144de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar LoadStoreVectorizer() : FunctionPass(ID) { 145de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar initializeLoadStoreVectorizerPass(*PassRegistry::getPassRegistry()); 146de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 147de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 148de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar bool runOnFunction(Function &F) override; 149de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 150de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar const char *getPassName() const override { 151de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return "GPU Load and Store Vectorizer"; 152de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 153de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 154de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar void getAnalysisUsage(AnalysisUsage &AU) const override { 155de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar AU.addRequired<AAResultsWrapperPass>(); 156de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar AU.addRequired<ScalarEvolutionWrapperPass>(); 157de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar AU.addRequired<DominatorTreeWrapperPass>(); 158de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar AU.addRequired<TargetTransformInfoWrapperPass>(); 159de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar AU.setPreservesCFG(); 160de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 161de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar}; 162de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar} 163de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 164de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga NainarINITIALIZE_PASS_BEGIN(LoadStoreVectorizer, DEBUG_TYPE, 165de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar "Vectorize load and Store instructions", false, false) 166de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga NainarINITIALIZE_PASS_DEPENDENCY(SCEVAAWrapperPass) 167de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga NainarINITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 168de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga NainarINITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) 169de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga NainarINITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass) 170de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga NainarINITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass) 171de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga NainarINITIALIZE_PASS_END(LoadStoreVectorizer, DEBUG_TYPE, 172de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar "Vectorize load and store instructions", false, false) 173de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 174de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarchar LoadStoreVectorizer::ID = 0; 175de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 176de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga NainarPass *llvm::createLoadStoreVectorizerPass() { 177de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return new LoadStoreVectorizer(); 178de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar} 179de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 180de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarbool LoadStoreVectorizer::runOnFunction(Function &F) { 181de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Don't vectorize when the attribute NoImplicitFloat is used. 182de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (skipFunction(F) || F.hasFnAttribute(Attribute::NoImplicitFloat)) 183de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return false; 184de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 185de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar AliasAnalysis &AA = getAnalysis<AAResultsWrapperPass>().getAAResults(); 186de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 187de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE(); 188de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar TargetTransformInfo &TTI = 189de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F); 190de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 191de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Vectorizer V(F, AA, DT, SE, TTI); 192de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return V.run(); 193de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar} 194de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 195de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// Vectorizer Implementation 196de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarbool Vectorizer::run() { 197de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar bool Changed = false; 198de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 199de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Scan the blocks in the function in post order. 200de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (BasicBlock *BB : post_order(&F)) { 201de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar collectInstructions(BB); 202de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Changed |= vectorizeChains(LoadRefs); 203de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Changed |= vectorizeChains(StoreRefs); 204de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 205de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 206de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return Changed; 207de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar} 208de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 209de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga NainarValue *Vectorizer::getPointerOperand(Value *I) { 210de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (LoadInst *LI = dyn_cast<LoadInst>(I)) 211de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return LI->getPointerOperand(); 212de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (StoreInst *SI = dyn_cast<StoreInst>(I)) 213de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return SI->getPointerOperand(); 214de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return nullptr; 215de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar} 216de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 217de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarunsigned Vectorizer::getPointerAddressSpace(Value *I) { 218de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (LoadInst *L = dyn_cast<LoadInst>(I)) 219de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return L->getPointerAddressSpace(); 220de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (StoreInst *S = dyn_cast<StoreInst>(I)) 221de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return S->getPointerAddressSpace(); 222de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return -1; 223de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar} 224de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 225de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// FIXME: Merge with llvm::isConsecutiveAccess 226de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarbool Vectorizer::isConsecutiveAccess(Value *A, Value *B) { 227de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Value *PtrA = getPointerOperand(A); 228de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Value *PtrB = getPointerOperand(B); 229de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar unsigned ASA = getPointerAddressSpace(A); 230de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar unsigned ASB = getPointerAddressSpace(B); 231de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 232de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Check that the address spaces match and that the pointers are valid. 233de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (!PtrA || !PtrB || (ASA != ASB)) 234de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return false; 235de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 236de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Make sure that A and B are different pointers of the same size type. 237de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar unsigned PtrBitWidth = DL.getPointerSizeInBits(ASA); 238de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Type *PtrATy = PtrA->getType()->getPointerElementType(); 239de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Type *PtrBTy = PtrB->getType()->getPointerElementType(); 240de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (PtrA == PtrB || 241de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar DL.getTypeStoreSize(PtrATy) != DL.getTypeStoreSize(PtrBTy) || 242de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar DL.getTypeStoreSize(PtrATy->getScalarType()) != 243de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar DL.getTypeStoreSize(PtrBTy->getScalarType())) 244de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return false; 245de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 246de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar APInt Size(PtrBitWidth, DL.getTypeStoreSize(PtrATy)); 247de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 248de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar APInt OffsetA(PtrBitWidth, 0), OffsetB(PtrBitWidth, 0); 249de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar PtrA = PtrA->stripAndAccumulateInBoundsConstantOffsets(DL, OffsetA); 250de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar PtrB = PtrB->stripAndAccumulateInBoundsConstantOffsets(DL, OffsetB); 251de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 252de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar APInt OffsetDelta = OffsetB - OffsetA; 253de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 254de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Check if they are based on the same pointer. That makes the offsets 255de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // sufficient. 256de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (PtrA == PtrB) 257de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return OffsetDelta == Size; 258de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 259de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Compute the necessary base pointer delta to have the necessary final delta 260de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // equal to the size. 261de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar APInt BaseDelta = Size - OffsetDelta; 262de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 263de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Compute the distance with SCEV between the base pointers. 264de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar const SCEV *PtrSCEVA = SE.getSCEV(PtrA); 265de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar const SCEV *PtrSCEVB = SE.getSCEV(PtrB); 266de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar const SCEV *C = SE.getConstant(BaseDelta); 267de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar const SCEV *X = SE.getAddExpr(PtrSCEVA, C); 268de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (X == PtrSCEVB) 269de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return true; 270de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 271de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Sometimes even this doesn't work, because SCEV can't always see through 272de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // patterns that look like (gep (ext (add (shl X, C1), C2))). Try checking 273de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // things the hard way. 274de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 275de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Look through GEPs after checking they're the same except for the last 276de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // index. 277de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar GetElementPtrInst *GEPA = dyn_cast<GetElementPtrInst>(getPointerOperand(A)); 278de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar GetElementPtrInst *GEPB = dyn_cast<GetElementPtrInst>(getPointerOperand(B)); 279de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (!GEPA || !GEPB || GEPA->getNumOperands() != GEPB->getNumOperands()) 280de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return false; 281de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar unsigned FinalIndex = GEPA->getNumOperands() - 1; 282de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (unsigned i = 0; i < FinalIndex; i++) 283de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (GEPA->getOperand(i) != GEPB->getOperand(i)) 284de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return false; 285de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 286de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Instruction *OpA = dyn_cast<Instruction>(GEPA->getOperand(FinalIndex)); 287de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Instruction *OpB = dyn_cast<Instruction>(GEPB->getOperand(FinalIndex)); 288de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (!OpA || !OpB || OpA->getOpcode() != OpB->getOpcode() || 289de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar OpA->getType() != OpB->getType()) 290de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return false; 291de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 292de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Only look through a ZExt/SExt. 293de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (!isa<SExtInst>(OpA) && !isa<ZExtInst>(OpA)) 294de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return false; 295de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 296de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar bool Signed = isa<SExtInst>(OpA); 297de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 298de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar OpA = dyn_cast<Instruction>(OpA->getOperand(0)); 299de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar OpB = dyn_cast<Instruction>(OpB->getOperand(0)); 300de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (!OpA || !OpB || OpA->getType() != OpB->getType()) 301de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return false; 302de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 303de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Now we need to prove that adding 1 to OpA won't overflow. 304de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar bool Safe = false; 305de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // First attempt: if OpB is an add with NSW/NUW, and OpB is 1 added to OpA, 306de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // we're okay. 307de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (OpB->getOpcode() == Instruction::Add && 308de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar isa<ConstantInt>(OpB->getOperand(1)) && 309de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar cast<ConstantInt>(OpB->getOperand(1))->getSExtValue() > 0) { 310de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (Signed) 311de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Safe = cast<BinaryOperator>(OpB)->hasNoSignedWrap(); 312de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar else 313de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Safe = cast<BinaryOperator>(OpB)->hasNoUnsignedWrap(); 314de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 315de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 316de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar unsigned BitWidth = OpA->getType()->getScalarSizeInBits(); 317de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 318de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Second attempt: 319de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // If any bits are known to be zero other than the sign bit in OpA, we can 320de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // add 1 to it while guaranteeing no overflow of any sort. 321de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (!Safe) { 322de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar APInt KnownZero(BitWidth, 0); 323de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar APInt KnownOne(BitWidth, 0); 324de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar computeKnownBits(OpA, KnownZero, KnownOne, DL, 0, nullptr, OpA, &DT); 325de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar KnownZero &= ~APInt::getHighBitsSet(BitWidth, 1); 326de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (KnownZero != 0) 327de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Safe = true; 328de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 329de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 330de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (!Safe) 331de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return false; 332de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 333de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar const SCEV *OffsetSCEVA = SE.getSCEV(OpA); 334de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar const SCEV *OffsetSCEVB = SE.getSCEV(OpB); 335de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar const SCEV *One = SE.getConstant(APInt(BitWidth, 1)); 336de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar const SCEV *X2 = SE.getAddExpr(OffsetSCEVA, One); 337de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return X2 == OffsetSCEVB; 338de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar} 339de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 340de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarvoid Vectorizer::reorder(Instruction *I) { 341de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar SmallPtrSet<Instruction *, 16> InstructionsToMove; 342de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar SmallVector<Instruction *, 16> Worklist; 343de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 344de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Worklist.push_back(I); 345de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar while (!Worklist.empty()) { 346de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Instruction *IW = Worklist.pop_back_val(); 347de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar int NumOperands = IW->getNumOperands(); 348de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (int i = 0; i < NumOperands; i++) { 349de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Instruction *IM = dyn_cast<Instruction>(IW->getOperand(i)); 350de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (!IM || IM->getOpcode() == Instruction::PHI) 351de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar continue; 352de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 353de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (!DT.dominates(IM, I)) { 354de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar InstructionsToMove.insert(IM); 355de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Worklist.push_back(IM); 356de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar assert(IM->getParent() == IW->getParent() && 357de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar "Instructions to move should be in the same basic block"); 358de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 359de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 360de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 361de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 362de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // All instructions to move should follow I. Start from I, not from begin(). 363de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (auto BBI = I->getIterator(), E = I->getParent()->end(); BBI != E; 364de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar ++BBI) { 365de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (!is_contained(InstructionsToMove, &*BBI)) 366de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar continue; 367de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Instruction *IM = &*BBI; 368de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar --BBI; 369de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar IM->removeFromParent(); 370de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar IM->insertBefore(I); 371de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 372de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar} 373de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 374de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarstd::pair<BasicBlock::iterator, BasicBlock::iterator> 375de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga NainarVectorizer::getBoundaryInstrs(ArrayRef<Value *> Chain) { 376de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Instruction *C0 = cast<Instruction>(Chain[0]); 377de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar BasicBlock::iterator FirstInstr = C0->getIterator(); 378de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar BasicBlock::iterator LastInstr = C0->getIterator(); 379de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 380de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar BasicBlock *BB = C0->getParent(); 381de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar unsigned NumFound = 0; 382de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (Instruction &I : *BB) { 383de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (!is_contained(Chain, &I)) 384de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar continue; 385de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 386de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar ++NumFound; 387de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (NumFound == 1) { 388de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar FirstInstr = I.getIterator(); 389de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 390de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (NumFound == Chain.size()) { 391de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar LastInstr = I.getIterator(); 392de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar break; 393de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 394de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 395de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 396de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Range is [first, last). 397de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return std::make_pair(FirstInstr, ++LastInstr); 398de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar} 399de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 400de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarvoid Vectorizer::eraseInstructions(ArrayRef<Value *> Chain) { 401de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar SmallVector<Instruction *, 16> Instrs; 402de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (Value *V : Chain) { 403de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Value *PtrOperand = getPointerOperand(V); 404de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar assert(PtrOperand && "Instruction must have a pointer operand."); 405de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Instrs.push_back(cast<Instruction>(V)); 406de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(PtrOperand)) 407de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Instrs.push_back(GEP); 408de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 409de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 410de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Erase instructions. 411de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (Value *V : Instrs) { 412de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Instruction *Instr = cast<Instruction>(V); 413de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (Instr->use_empty()) 414de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Instr->eraseFromParent(); 415de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 416de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar} 417de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 418de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarstd::pair<ArrayRef<Value *>, ArrayRef<Value *>> 419de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga NainarVectorizer::splitOddVectorElts(ArrayRef<Value *> Chain, 420de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar unsigned ElementSizeBits) { 421de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar unsigned ElemSizeInBytes = ElementSizeBits / 8; 422de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar unsigned SizeInBytes = ElemSizeInBytes * Chain.size(); 423de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar unsigned NumRight = (SizeInBytes % 4) / ElemSizeInBytes; 424de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar unsigned NumLeft = Chain.size() - NumRight; 425de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return std::make_pair(Chain.slice(0, NumLeft), Chain.slice(NumLeft)); 426de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar} 427de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 428de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarunsigned Vectorizer::getVectorizablePrefixEndIdx(ArrayRef<Value *> Chain, 429de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar BasicBlock::iterator From, 430de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar BasicBlock::iterator To) { 431de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar SmallVector<std::pair<Value *, unsigned>, 16> MemoryInstrs; 432de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar SmallVector<std::pair<Value *, unsigned>, 16> ChainInstrs; 433de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 434de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar unsigned InstrIdx = 0; 435de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (auto I = From; I != To; ++I, ++InstrIdx) { 436de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (isa<LoadInst>(I) || isa<StoreInst>(I)) { 437de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (!is_contained(Chain, &*I)) 438de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar MemoryInstrs.push_back({&*I, InstrIdx}); 439de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar else 440de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar ChainInstrs.push_back({&*I, InstrIdx}); 441de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } else if (I->mayHaveSideEffects()) { 442de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar DEBUG(dbgs() << "LSV: Found side-effecting operation: " << *I << '\n'); 443de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return 0; 444de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 445de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 446de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 447de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar assert(Chain.size() == ChainInstrs.size() && 448de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar "All instructions in the Chain must exist in [From, To)."); 449de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 450de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar unsigned ChainIdx = 0; 451de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (auto EntryChain : ChainInstrs) { 452de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Value *ChainInstrValue = EntryChain.first; 453de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar unsigned ChainInstrIdx = EntryChain.second; 454de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (auto EntryMem : MemoryInstrs) { 455de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Value *MemInstrValue = EntryMem.first; 456de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar unsigned MemInstrIdx = EntryMem.second; 457de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (isa<LoadInst>(MemInstrValue) && isa<LoadInst>(ChainInstrValue)) 458de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar continue; 459de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 460de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // We can ignore the alias as long as the load comes before the store, 461de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // because that means we won't be moving the load past the store to 462de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // vectorize it (the vectorized load is inserted at the location of the 463de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // first load in the chain). 464de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (isa<StoreInst>(MemInstrValue) && isa<LoadInst>(ChainInstrValue) && 465de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar ChainInstrIdx < MemInstrIdx) 466de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar continue; 467de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 468de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Same case, but in reverse. 469de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (isa<LoadInst>(MemInstrValue) && isa<StoreInst>(ChainInstrValue) && 470de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar ChainInstrIdx > MemInstrIdx) 471de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar continue; 472de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 473de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Instruction *M0 = cast<Instruction>(MemInstrValue); 474de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Instruction *M1 = cast<Instruction>(ChainInstrValue); 475de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 476de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (!AA.isNoAlias(MemoryLocation::get(M0), MemoryLocation::get(M1))) { 477de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar DEBUG({ 478de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Value *Ptr0 = getPointerOperand(M0); 479de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Value *Ptr1 = getPointerOperand(M1); 480de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 481de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar dbgs() << "LSV: Found alias.\n" 482de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar " Aliasing instruction and pointer:\n" 483de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar << *MemInstrValue << " aliases " << *Ptr0 << '\n' 484de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar << " Aliased instruction and pointer:\n" 485de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar << *ChainInstrValue << " aliases " << *Ptr1 << '\n'; 486de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar }); 487de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 488de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return ChainIdx; 489de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 490de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 491de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar ChainIdx++; 492de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 493de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return Chain.size(); 494de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar} 495de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 496de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarvoid Vectorizer::collectInstructions(BasicBlock *BB) { 497de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar LoadRefs.clear(); 498de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar StoreRefs.clear(); 499de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 500de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (Instruction &I : *BB) { 501de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (!I.mayReadOrWriteMemory()) 502de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar continue; 503de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 504de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (LoadInst *LI = dyn_cast<LoadInst>(&I)) { 505de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (!LI->isSimple()) 506de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar continue; 507de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 508de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Type *Ty = LI->getType(); 509de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (!VectorType::isValidElementType(Ty->getScalarType())) 510de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar continue; 511de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 512de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Skip weird non-byte sizes. They probably aren't worth the effort of 513de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // handling correctly. 514de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar unsigned TySize = DL.getTypeSizeInBits(Ty); 515de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (TySize < 8) 516de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar continue; 517de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 518de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Value *Ptr = LI->getPointerOperand(); 519de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar unsigned AS = Ptr->getType()->getPointerAddressSpace(); 520de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar unsigned VecRegSize = TTI.getLoadStoreVecRegBitWidth(AS); 521de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 522de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // No point in looking at these if they're too big to vectorize. 523de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (TySize > VecRegSize / 2) 524de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar continue; 525de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 526de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Make sure all the users of a vector are constant-index extracts. 527de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (isa<VectorType>(Ty) && !all_of(LI->users(), [LI](const User *U) { 528de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar const Instruction *UI = cast<Instruction>(U); 529de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return isa<ExtractElementInst>(UI) && 530de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar isa<ConstantInt>(UI->getOperand(1)); 531de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar })) 532de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar continue; 533de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 534de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // TODO: Target hook to filter types. 535de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 536de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Save the load locations. 537de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Value *ObjPtr = GetUnderlyingObject(Ptr, DL); 538de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar LoadRefs[ObjPtr].push_back(LI); 539de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 540de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } else if (StoreInst *SI = dyn_cast<StoreInst>(&I)) { 541de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (!SI->isSimple()) 542de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar continue; 543de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 544de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Type *Ty = SI->getValueOperand()->getType(); 545de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (!VectorType::isValidElementType(Ty->getScalarType())) 546de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar continue; 547de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 548de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Skip weird non-byte sizes. They probably aren't worth the effort of 549de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // handling correctly. 550de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar unsigned TySize = DL.getTypeSizeInBits(Ty); 551de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (TySize < 8) 552de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar continue; 553de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 554de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Value *Ptr = SI->getPointerOperand(); 555de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar unsigned AS = Ptr->getType()->getPointerAddressSpace(); 556de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar unsigned VecRegSize = TTI.getLoadStoreVecRegBitWidth(AS); 557de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (TySize > VecRegSize / 2) 558de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar continue; 559de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 560de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (isa<VectorType>(Ty) && !all_of(SI->users(), [SI](const User *U) { 561de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar const Instruction *UI = cast<Instruction>(U); 562de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return isa<ExtractElementInst>(UI) && 563de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar isa<ConstantInt>(UI->getOperand(1)); 564de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar })) 565de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar continue; 566de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 567de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Save store location. 568de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Value *ObjPtr = GetUnderlyingObject(Ptr, DL); 569de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar StoreRefs[ObjPtr].push_back(SI); 570de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 571de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 572de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar} 573de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 574de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarbool Vectorizer::vectorizeChains(ValueListMap &Map) { 575de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar bool Changed = false; 576de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 577de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (const std::pair<Value *, ValueList> &Chain : Map) { 578de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar unsigned Size = Chain.second.size(); 579de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (Size < 2) 580de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar continue; 581de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 582de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar DEBUG(dbgs() << "LSV: Analyzing a chain of length " << Size << ".\n"); 583de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 584de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Process the stores in chunks of 64. 585de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (unsigned CI = 0, CE = Size; CI < CE; CI += 64) { 586de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar unsigned Len = std::min<unsigned>(CE - CI, 64); 587de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar ArrayRef<Value *> Chunk(&Chain.second[CI], Len); 588de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Changed |= vectorizeInstructions(Chunk); 589de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 590de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 591de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 592de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return Changed; 593de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar} 594de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 595de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarbool Vectorizer::vectorizeInstructions(ArrayRef<Value *> Instrs) { 596de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar DEBUG(dbgs() << "LSV: Vectorizing " << Instrs.size() << " instructions.\n"); 597de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar SmallSetVector<int, 16> Heads, Tails; 598de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar int ConsecutiveChain[64]; 599de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 600de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Do a quadratic search on all of the given stores and find all of the pairs 601de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // of stores that follow each other. 602de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (int i = 0, e = Instrs.size(); i < e; ++i) { 603de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar ConsecutiveChain[i] = -1; 604de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (int j = e - 1; j >= 0; --j) { 605de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (i == j) 606de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar continue; 607de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 608de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (isConsecutiveAccess(Instrs[i], Instrs[j])) { 609de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (ConsecutiveChain[i] != -1) { 610de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar int CurDistance = std::abs(ConsecutiveChain[i] - i); 611de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar int NewDistance = std::abs(ConsecutiveChain[i] - j); 612de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (j < i || NewDistance > CurDistance) 613de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar continue; // Should not insert. 614de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 615de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 616de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Tails.insert(j); 617de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Heads.insert(i); 618de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar ConsecutiveChain[i] = j; 619de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 620de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 621de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 622de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 623de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar bool Changed = false; 624de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar SmallPtrSet<Value *, 16> InstructionsProcessed; 625de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 626de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (int Head : Heads) { 627de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (InstructionsProcessed.count(Instrs[Head])) 628de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar continue; 629de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar bool longerChainExists = false; 630de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (unsigned TIt = 0; TIt < Tails.size(); TIt++) 631de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (Head == Tails[TIt] && 632de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar !InstructionsProcessed.count(Instrs[Heads[TIt]])) { 633de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar longerChainExists = true; 634de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar break; 635de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 636de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (longerChainExists) 637de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar continue; 638de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 639de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // We found an instr that starts a chain. Now follow the chain and try to 640de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // vectorize it. 641de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar SmallVector<Value *, 16> Operands; 642de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar int I = Head; 643de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar while (I != -1 && (Tails.count(I) || Heads.count(I))) { 644de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (InstructionsProcessed.count(Instrs[I])) 645de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar break; 646de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 647de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Operands.push_back(Instrs[I]); 648de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar I = ConsecutiveChain[I]; 649de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 650de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 651de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar bool Vectorized = false; 652de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (isa<LoadInst>(*Operands.begin())) 653de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Vectorized = vectorizeLoadChain(Operands, &InstructionsProcessed); 654de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar else 655de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Vectorized = vectorizeStoreChain(Operands, &InstructionsProcessed); 656de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 657de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Changed |= Vectorized; 658de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 659de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 660de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return Changed; 661de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar} 662de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 663de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarbool Vectorizer::vectorizeStoreChain( 664de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar ArrayRef<Value *> Chain, SmallPtrSet<Value *, 16> *InstructionsProcessed) { 665de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar StoreInst *S0 = cast<StoreInst>(Chain[0]); 666de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 667de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // If the vector has an int element, default to int for the whole load. 668de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Type *StoreTy; 669de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (const auto &V : Chain) { 670de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar StoreTy = cast<StoreInst>(V)->getValueOperand()->getType(); 671de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (StoreTy->isIntOrIntVectorTy()) 672de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar break; 673de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 674de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (StoreTy->isPtrOrPtrVectorTy()) { 675de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar StoreTy = Type::getIntNTy(F.getParent()->getContext(), 676de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar DL.getTypeSizeInBits(StoreTy)); 677de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar break; 678de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 679de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 680de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 681de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar unsigned Sz = DL.getTypeSizeInBits(StoreTy); 682de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar unsigned AS = S0->getPointerAddressSpace(); 683de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar unsigned VecRegSize = TTI.getLoadStoreVecRegBitWidth(AS); 684de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar unsigned VF = VecRegSize / Sz; 685de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar unsigned ChainSize = Chain.size(); 686de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 687de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (!isPowerOf2_32(Sz) || VF < 2 || ChainSize < 2) { 688de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar InstructionsProcessed->insert(Chain.begin(), Chain.end()); 689de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return false; 690de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 691de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 692de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar BasicBlock::iterator First, Last; 693de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar std::tie(First, Last) = getBoundaryInstrs(Chain); 694de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar unsigned StopChain = getVectorizablePrefixEndIdx(Chain, First, Last); 695de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (StopChain == 0) { 696de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // There exists a side effect instruction, no vectorization possible. 697de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar InstructionsProcessed->insert(Chain.begin(), Chain.end()); 698de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return false; 699de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 700de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (StopChain == 1) { 701de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Failed after the first instruction. Discard it and try the smaller chain. 702de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar InstructionsProcessed->insert(Chain.front()); 703de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return false; 704de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 705de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 706de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Update Chain to the valid vectorizable subchain. 707de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Chain = Chain.slice(0, StopChain); 708de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar ChainSize = Chain.size(); 709de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 710de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Store size should be 1B, 2B or multiple of 4B. 711de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // TODO: Target hook for size constraint? 712de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar unsigned SzInBytes = (Sz / 8) * ChainSize; 713de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (SzInBytes > 2 && SzInBytes % 4 != 0) { 714de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar DEBUG(dbgs() << "LSV: Size should be 1B, 2B " 715de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar "or multiple of 4B. Splitting.\n"); 716de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (SzInBytes == 3) 717de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return vectorizeStoreChain(Chain.slice(0, ChainSize - 1), 718de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar InstructionsProcessed); 719de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 720de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar auto Chains = splitOddVectorElts(Chain, Sz); 721de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return vectorizeStoreChain(Chains.first, InstructionsProcessed) | 722de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar vectorizeStoreChain(Chains.second, InstructionsProcessed); 723de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 724de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 725de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar VectorType *VecTy; 726de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar VectorType *VecStoreTy = dyn_cast<VectorType>(StoreTy); 727de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (VecStoreTy) 728de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar VecTy = VectorType::get(StoreTy->getScalarType(), 729de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Chain.size() * VecStoreTy->getNumElements()); 730de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar else 731de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar VecTy = VectorType::get(StoreTy, Chain.size()); 732de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 733de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // If it's more than the max vector size, break it into two pieces. 734de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // TODO: Target hook to control types to split to. 735de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (ChainSize > VF) { 736de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar DEBUG(dbgs() << "LSV: Vector factor is too big." 737de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar " Creating two separate arrays.\n"); 738de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return vectorizeStoreChain(Chain.slice(0, VF), InstructionsProcessed) | 739de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar vectorizeStoreChain(Chain.slice(VF), InstructionsProcessed); 740de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 741de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 742de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar DEBUG({ 743de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar dbgs() << "LSV: Stores to vectorize:\n"; 744de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (Value *V : Chain) 745de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar V->dump(); 746de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar }); 747de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 748de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // We won't try again to vectorize the elements of the chain, regardless of 749de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // whether we succeed below. 750de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar InstructionsProcessed->insert(Chain.begin(), Chain.end()); 751de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 752de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Check alignment restrictions. 753de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar unsigned Alignment = getAlignment(S0); 754de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 755de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // If the store is going to be misaligned, don't vectorize it. 756de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (accessIsMisaligned(SzInBytes, AS, Alignment)) { 757de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (S0->getPointerAddressSpace() != 0) 758de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return false; 759de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 760de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // If we're storing to an object on the stack, we control its alignment, 761de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // so we can cheat and change it! 762de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Value *V = GetUnderlyingObject(S0->getPointerOperand(), DL); 763de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (AllocaInst *AI = dyn_cast_or_null<AllocaInst>(V)) { 764de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar AI->setAlignment(TargetBaseAlign); 765de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Alignment = TargetBaseAlign; 766de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } else { 767de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return false; 768de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 769de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 770de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 771de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Set insert point. 772de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Builder.SetInsertPoint(&*Last); 773de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 774de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Value *Vec = UndefValue::get(VecTy); 775de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 776de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (VecStoreTy) { 777de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar unsigned VecWidth = VecStoreTy->getNumElements(); 778de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (unsigned I = 0, E = Chain.size(); I != E; ++I) { 779de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar StoreInst *Store = cast<StoreInst>(Chain[I]); 780de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (unsigned J = 0, NE = VecStoreTy->getNumElements(); J != NE; ++J) { 781de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar unsigned NewIdx = J + I * VecWidth; 782de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Value *Extract = Builder.CreateExtractElement(Store->getValueOperand(), 783de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Builder.getInt32(J)); 784de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (Extract->getType() != StoreTy->getScalarType()) 785de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Extract = Builder.CreateBitCast(Extract, StoreTy->getScalarType()); 786de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 787de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Value *Insert = 788de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Builder.CreateInsertElement(Vec, Extract, Builder.getInt32(NewIdx)); 789de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Vec = Insert; 790de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 791de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 792de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } else { 793de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (unsigned I = 0, E = Chain.size(); I != E; ++I) { 794de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar StoreInst *Store = cast<StoreInst>(Chain[I]); 795de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Value *Extract = Store->getValueOperand(); 796de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (Extract->getType() != StoreTy->getScalarType()) 797de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Extract = 798de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Builder.CreateBitOrPointerCast(Extract, StoreTy->getScalarType()); 799de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 800de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Value *Insert = 801de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Builder.CreateInsertElement(Vec, Extract, Builder.getInt32(I)); 802de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Vec = Insert; 803de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 804de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 805de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 806de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Value *Bitcast = 807de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Builder.CreateBitCast(S0->getPointerOperand(), VecTy->getPointerTo(AS)); 808de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar StoreInst *SI = cast<StoreInst>(Builder.CreateStore(Vec, Bitcast)); 809de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar propagateMetadata(SI, Chain); 810de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar SI->setAlignment(Alignment); 811de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 812de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar eraseInstructions(Chain); 813de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar ++NumVectorInstructions; 814de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar NumScalarsVectorized += Chain.size(); 815de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return true; 816de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar} 817de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 818de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarbool Vectorizer::vectorizeLoadChain( 819de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar ArrayRef<Value *> Chain, SmallPtrSet<Value *, 16> *InstructionsProcessed) { 820de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar LoadInst *L0 = cast<LoadInst>(Chain[0]); 821de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 822de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // If the vector has an int element, default to int for the whole load. 823de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Type *LoadTy; 824de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (const auto &V : Chain) { 825de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar LoadTy = cast<LoadInst>(V)->getType(); 826de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (LoadTy->isIntOrIntVectorTy()) 827de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar break; 828de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 829de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (LoadTy->isPtrOrPtrVectorTy()) { 830de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar LoadTy = Type::getIntNTy(F.getParent()->getContext(), 831de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar DL.getTypeSizeInBits(LoadTy)); 832de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar break; 833de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 834de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 835de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 836de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar unsigned Sz = DL.getTypeSizeInBits(LoadTy); 837de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar unsigned AS = L0->getPointerAddressSpace(); 838de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar unsigned VecRegSize = TTI.getLoadStoreVecRegBitWidth(AS); 839de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar unsigned VF = VecRegSize / Sz; 840de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar unsigned ChainSize = Chain.size(); 841de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 842de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (!isPowerOf2_32(Sz) || VF < 2 || ChainSize < 2) { 843de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar InstructionsProcessed->insert(Chain.begin(), Chain.end()); 844de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return false; 845de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 846de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 847de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar BasicBlock::iterator First, Last; 848de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar std::tie(First, Last) = getBoundaryInstrs(Chain); 849de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar unsigned StopChain = getVectorizablePrefixEndIdx(Chain, First, Last); 850de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (StopChain == 0) { 851de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // There exists a side effect instruction, no vectorization possible. 852de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar InstructionsProcessed->insert(Chain.begin(), Chain.end()); 853de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return false; 854de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 855de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (StopChain == 1) { 856de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Failed after the first instruction. Discard it and try the smaller chain. 857de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar InstructionsProcessed->insert(Chain.front()); 858de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return false; 859de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 860de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 861de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Update Chain to the valid vectorizable subchain. 862de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Chain = Chain.slice(0, StopChain); 863de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar ChainSize = Chain.size(); 864de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 865de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Load size should be 1B, 2B or multiple of 4B. 866de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // TODO: Should size constraint be a target hook? 867de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar unsigned SzInBytes = (Sz / 8) * ChainSize; 868de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (SzInBytes > 2 && SzInBytes % 4 != 0) { 869de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar DEBUG(dbgs() << "LSV: Size should be 1B, 2B " 870de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar "or multiple of 4B. Splitting.\n"); 871de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (SzInBytes == 3) 872de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return vectorizeLoadChain(Chain.slice(0, ChainSize - 1), 873de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar InstructionsProcessed); 874de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar auto Chains = splitOddVectorElts(Chain, Sz); 875de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return vectorizeLoadChain(Chains.first, InstructionsProcessed) | 876de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar vectorizeLoadChain(Chains.second, InstructionsProcessed); 877de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 878de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 879de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar VectorType *VecTy; 880de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar VectorType *VecLoadTy = dyn_cast<VectorType>(LoadTy); 881de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (VecLoadTy) 882de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar VecTy = VectorType::get(LoadTy->getScalarType(), 883de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Chain.size() * VecLoadTy->getNumElements()); 884de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar else 885de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar VecTy = VectorType::get(LoadTy, Chain.size()); 886de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 887de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // If it's more than the max vector size, break it into two pieces. 888de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // TODO: Target hook to control types to split to. 889de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (ChainSize > VF) { 890de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar DEBUG(dbgs() << "LSV: Vector factor is too big. " 891de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar "Creating two separate arrays.\n"); 892de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return vectorizeLoadChain(Chain.slice(0, VF), InstructionsProcessed) | 893de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar vectorizeLoadChain(Chain.slice(VF), InstructionsProcessed); 894de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 895de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 896de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // We won't try again to vectorize the elements of the chain, regardless of 897de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // whether we succeed below. 898de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar InstructionsProcessed->insert(Chain.begin(), Chain.end()); 899de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 900de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Check alignment restrictions. 901de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar unsigned Alignment = getAlignment(L0); 902de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 903de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // If the load is going to be misaligned, don't vectorize it. 904de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (accessIsMisaligned(SzInBytes, AS, Alignment)) { 905de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (L0->getPointerAddressSpace() != 0) 906de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return false; 907de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 908de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // If we're loading from an object on the stack, we control its alignment, 909de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // so we can cheat and change it! 910de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Value *V = GetUnderlyingObject(L0->getPointerOperand(), DL); 911de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (AllocaInst *AI = dyn_cast_or_null<AllocaInst>(V)) { 912de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar AI->setAlignment(TargetBaseAlign); 913de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Alignment = TargetBaseAlign; 914de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } else { 915de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return false; 916de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 917de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 918de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 919de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar DEBUG({ 920de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar dbgs() << "LSV: Loads to vectorize:\n"; 921de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (Value *V : Chain) 922de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar V->dump(); 923de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar }); 924de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 925de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Set insert point. 926de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Builder.SetInsertPoint(&*First); 927de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 928de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Value *Bitcast = 929de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Builder.CreateBitCast(L0->getPointerOperand(), VecTy->getPointerTo(AS)); 930de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 931de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar LoadInst *LI = cast<LoadInst>(Builder.CreateLoad(Bitcast)); 932de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar propagateMetadata(LI, Chain); 933de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar LI->setAlignment(Alignment); 934de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 935de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (VecLoadTy) { 936de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar SmallVector<Instruction *, 16> InstrsToErase; 937de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar SmallVector<Instruction *, 16> InstrsToReorder; 938de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar InstrsToReorder.push_back(cast<Instruction>(Bitcast)); 939de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 940de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar unsigned VecWidth = VecLoadTy->getNumElements(); 941de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (unsigned I = 0, E = Chain.size(); I != E; ++I) { 942de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (auto Use : Chain[I]->users()) { 943de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Instruction *UI = cast<Instruction>(Use); 944de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar unsigned Idx = cast<ConstantInt>(UI->getOperand(1))->getZExtValue(); 945de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar unsigned NewIdx = Idx + I * VecWidth; 946de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Value *V = Builder.CreateExtractElement(LI, Builder.getInt32(NewIdx)); 947de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Instruction *Extracted = cast<Instruction>(V); 948de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (Extracted->getType() != UI->getType()) 949de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Extracted = cast<Instruction>( 950de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Builder.CreateBitCast(Extracted, UI->getType())); 951de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 952de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Replace the old instruction. 953de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar UI->replaceAllUsesWith(Extracted); 954de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar InstrsToErase.push_back(UI); 955de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 956de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 957de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 958de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (Instruction *ModUser : InstrsToReorder) 959de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar reorder(ModUser); 960de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 961de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (auto I : InstrsToErase) 962de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar I->eraseFromParent(); 963de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } else { 964de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar SmallVector<Instruction *, 16> InstrsToReorder; 965de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar InstrsToReorder.push_back(cast<Instruction>(Bitcast)); 966de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 967de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (unsigned I = 0, E = Chain.size(); I != E; ++I) { 968de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Value *V = Builder.CreateExtractElement(LI, Builder.getInt32(I)); 969de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Instruction *Extracted = cast<Instruction>(V); 970de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Instruction *UI = cast<Instruction>(Chain[I]); 971de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (Extracted->getType() != UI->getType()) { 972de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Extracted = cast<Instruction>( 973de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Builder.CreateBitOrPointerCast(Extracted, UI->getType())); 974de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 975de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 976de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Replace the old instruction. 977de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar UI->replaceAllUsesWith(Extracted); 978de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 979de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 980de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (Instruction *ModUser : InstrsToReorder) 981de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar reorder(ModUser); 982de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 983de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 984de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar eraseInstructions(Chain); 985de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 986de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar ++NumVectorInstructions; 987de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar NumScalarsVectorized += Chain.size(); 988de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return true; 989de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar} 990de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 991de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarbool Vectorizer::accessIsMisaligned(unsigned SzInBytes, unsigned AddressSpace, 992de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar unsigned Alignment) { 993de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar bool Fast = false; 994de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar bool Allows = TTI.allowsMisalignedMemoryAccesses(SzInBytes * 8, AddressSpace, 995de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Alignment, &Fast); 996de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // TODO: Remove TargetBaseAlign 997de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return !(Allows && Fast) && (Alignment % SzInBytes) != 0 && 998de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar (Alignment % TargetBaseAlign) != 0; 999de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar} 1000