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