1 //===- VecUtils.h - Vectorization Utilities -------------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This family of classes and functions manipulate vectors and chains of
13 //===----------------------------------------------------------------------===//
15 #ifndef LLVM_TRANSFORMS_VECTORIZE_VECUTILS_H
16 #define LLVM_TRANSFORMS_VECTORIZE_VECUTILS_H
18 #include "llvm/ADT/DenseMap.h"
19 #include "llvm/ADT/SetVector.h"
20 #include "llvm/ADT/SmallPtrSet.h"
21 #include "llvm/ADT/SmallVector.h"
22 #include "llvm/Analysis/AliasAnalysis.h"
23 #include "llvm/IR/IRBuilder.h"
28 class BasicBlock; class Instruction; class Type;
29 class VectorType; class StoreInst; class Value;
30 class ScalarEvolution; class DataLayout;
31 class TargetTransformInfo; class AliasAnalysis;
34 /// Bottom Up SLP vectorization utility class.
36 typedef SmallVector<Value*, 8> ValueList;
37 typedef SmallVector<Instruction*, 16> InstrList;
38 typedef SmallPtrSet<Value*, 16> ValueSet;
39 typedef SmallVector<StoreInst*, 8> StoreList;
40 static const int max_cost = 1<<20;
43 BoUpSLP(BasicBlock *Bb, ScalarEvolution *Se, DataLayout *Dl,
44 TargetTransformInfo *Tti, AliasAnalysis *Aa, Loop *Lp);
46 /// \brief Take the pointer operand from the Load/Store instruction.
47 /// \returns NULL if this is not a valid Load/Store instruction.
48 static Value *getPointerOperand(Value *I);
50 /// \brief Take the address space operand from the Load/Store instruction.
51 /// \returns -1 if this is not a valid Load/Store instruction.
52 static unsigned getAddressSpaceOperand(Value *I);
54 /// \returns true if the memory operations A and B are consecutive.
55 bool isConsecutiveAccess(Value *A, Value *B);
57 /// \brief Vectorize the tree that starts with the elements in \p VL.
58 /// \returns the vectorized value.
59 Value *vectorizeTree(ArrayRef<Value *> VL, int VF);
61 /// \returns the vectorization cost of the subtree that starts at \p VL.
62 /// A negative number means that this is profitable.
63 int getTreeCost(ArrayRef<Value *> VL);
65 /// \returns the scalarization cost for this list of values. Assuming that
66 /// this subtree gets vectorized, we may need to extract the values from the
67 /// roots. This method calculates the cost of extracting the values.
68 int getScalarizationCost(ArrayRef<Value *> VL);
70 /// \brief Attempts to order and vectorize a sequence of stores. This
71 /// function does a quadratic scan of the given stores.
72 /// \returns true if the basic block was modified.
73 bool vectorizeStores(ArrayRef<StoreInst *> Stores, int costThreshold);
75 /// \brief Vectorize a group of scalars into a vector tree.
76 /// \returns the vectorized value.
77 Value *vectorizeArith(ArrayRef<Value *> Operands);
79 /// \returns the list of new instructions that were added in order to collect
80 /// scalars into vectors. This list can be used to further optimize the gather
82 InstrList &getGatherSeqInstructions() {return GatherInstructions; }
85 /// \brief This method contains the recursive part of getTreeCost.
86 int getTreeCost_rec(ArrayRef<Value *> VL, unsigned Depth);
88 /// \brief This recursive method looks for vectorization hazards such as
89 /// values that are used by multiple users and checks that values are used
90 /// by only one vector lane. It updates the variables LaneMap, MultiUserVals.
91 void getTreeUses_rec(ArrayRef<Value *> VL, unsigned Depth);
93 /// \brief This method contains the recursive part of vectorizeTree.
94 Value *vectorizeTree_rec(ArrayRef<Value *> VL, int VF);
96 /// \brief Number all of the instructions in the block.
97 void numberInstructions();
99 /// \brief Vectorize a sorted sequence of stores.
100 bool vectorizeStoreChain(ArrayRef<Value *> Chain, int CostThreshold);
102 /// \returns the scalarization cost for this type. Scalarization in this
103 /// context means the creation of vectors from a group of scalars.
104 int getScalarizationCost(Type *Ty);
106 /// \returns the AA location that is being access by the instruction.
107 AliasAnalysis::Location getLocation(Instruction *I);
109 /// \brief Checks if it is possible to sink an instruction from
110 /// \p Src to \p Dst.
111 /// \returns the pointer to the barrier instruction if we can't sink.
112 Value *isUnsafeToSink(Instruction *Src, Instruction *Dst);
114 /// \returns the index of the last instrucion in the BB from \p VL.
115 /// Only consider the first \p VF elements.
116 int getLastIndex(ArrayRef<Value *> VL, unsigned VF);
118 /// \returns the index of the first User of \p VL.
119 /// Only consider the first \p VF elements.
120 int getFirstUserIndex(ArrayRef<Value *> VL, unsigned VF);
122 /// \returns the instruction \p I or \p J that appears last in the BB .
123 int getLastIndex(Instruction *I, Instruction *J);
125 /// \returns the insertion point for \p Index.
126 Instruction *getInsertionPoint(unsigned Index);
128 /// \returns a vector from a collection of scalars in \p VL.
129 Value *Scalarize(ArrayRef<Value *> VL, VectorType *Ty);
132 /// Maps instructions to numbers and back.
133 SmallDenseMap<Value*, int> InstrIdx;
134 /// Maps integers to Instructions.
135 std::vector<Instruction*> InstrVec;
137 // -- containers that are used during getTreeCost -- //
139 /// Contains values that must be scalarized because they are used
140 /// by multiple lanes, or by users outside the tree.
141 /// NOTICE: The vectorization methods also use this set.
142 ValueSet MustScalarize;
144 /// Contains values that have users outside of the vectorized graph.
145 /// We need to generate extract instructions for these values.
146 /// NOTICE: The vectorization methods also use this set.
147 SetVector<Value*> MustExtract;
149 /// Contains a list of values that are used outside the current tree. This
150 /// set must be reset between runs.
151 SetVector<Value*> MultiUserVals;
152 /// Maps values in the tree to the vector lanes that uses them. This map must
153 /// be reset between runs of getCost.
154 std::map<Value*, int> LaneMap;
155 /// A list of instructions to ignore while sinking
156 /// memory instructions. This map must be reset between runs of getCost.
157 ValueSet MemBarrierIgnoreList;
159 // -- Containers that are used during vectorizeTree -- //
161 /// Maps between the first scalar to the vector. This map must be reset
163 DenseMap<Value*, Value*> VectorizedValues;
165 // -- Containers that are used after vectorization by the caller -- //
167 /// A list of instructions that are used when gathering scalars into vectors.
168 /// In many cases these instructions can be hoisted outside of the BB.
169 /// Iterating over this list is faster than calling LICM.
170 /// Notice: We insert NULL ptrs to separate between the different gather
172 InstrList GatherInstructions;
174 /// Instruction builder to construct the vectorized tree.
177 // Analysis and block reference.
181 TargetTransformInfo *TTI;
186 } // end of namespace
188 #endif // LLVM_TRANSFORMS_VECTORIZE_VECUTILS_H