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
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
|
/*========================== begin_copyright_notice ============================
Copyright (C) 2023 Intel Corporation
SPDX-License-Identifier: MIT
============================= end_copyright_notice ===========================*/
//
/// GenXLiveElements
/// --------------------
///
/// GenXLiveElements is an analysis pass that stores information about
/// live (i.e. possibly used in future) lanes of vector instructions and
/// their uses inside a function. Pass starts its work from root instructions
/// (terminators and side-effect instructions) and propagates this information
/// backwards until some stable point is not reached. Propagation function for
/// each instruction gets live elements of its result and estimates what
/// elements in operands are required to it. For unknown types of instructions
/// there is a safe fallback to estimate "all-live" result, but this can be
/// improved in future to get more precise results
//===----------------------------------------------------------------------===//
#ifndef GENXLIVEELEMENTS_H
#define GENXLIVEELEMENTS_H
#include "FunctionGroup.h"
#include "llvm/ADT/SmallBitVector.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/IR/ValueMap.h"
#include "llvm/Pass.h"
#include "llvm/Support/raw_ostream.h"
namespace llvm {
namespace genx {
// LiveElements is an utility class to represent information about used elements
// inside some type, possibly aggregate. It contains bit masks for each simple
// (scalar or vector) value in flattened order for complex nested types. The
// special case is void type, which doesn't have any bit mask (even empty). Such
// empty LiveElements is treated as always used
class LiveElements {
private:
using LiveElementsTy = SmallVector<SmallBitVector, 2>;
LiveElementsTy LiveElems;
public:
using size_type = LiveElementsTy::size_type;
using iterator = LiveElementsTy::iterator;
using const_iterator = LiveElementsTy::const_iterator;
using reference = LiveElementsTy::reference;
using const_reference = LiveElementsTy::const_reference;
LiveElements() = default;
LiveElements(Type *Ty, bool IsLive = false);
LiveElements(const ArrayRef<SmallBitVector> LE)
: LiveElems(LE.begin(), LE.end()) {}
LiveElements(SmallBitVector &&LE) : LiveElems({std::move(LE)}) {}
LiveElements(const SmallBitVector &LE) = delete;
LiveElements &operator=(const SmallBitVector &) = delete;
iterator begin() { return LiveElems.begin(); }
const_iterator begin() const { return LiveElems.begin(); }
iterator end() { return LiveElems.end(); }
const_iterator end() const { return LiveElems.end(); }
reference operator[](size_type Idx) { return LiveElems[Idx]; }
const_reference operator[](size_type Idx) const { return LiveElems[Idx]; }
size_type size() const { return LiveElems.size(); }
bool isAllDead() const {
return !LiveElems.empty() && all_of(LiveElems, [](const auto &LiveBits) {
return !LiveBits.empty() && LiveBits.none();
});
}
bool isAnyDead() const {
return !LiveElems.empty() && any_of(LiveElems, [](const auto &LiveBits) {
return !LiveBits.empty() && !LiveBits.all();
});
}
bool operator==(const LiveElements &Rhs) const {
return LiveElems == Rhs.LiveElems;
}
bool operator!=(const LiveElements &Rhs) const { return !(*this == Rhs); }
LiveElements operator|=(const LiveElements &Rhs);
void print(raw_ostream &OS) const;
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
void dump() const;
#endif // if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
};
inline LiveElements operator|(const LiveElements &Lhs,
const LiveElements &Rhs) {
LiveElements Res(Lhs);
Res |= Rhs;
return Res;
}
inline raw_ostream &operator<<(raw_ostream &OS, const LiveElements &LE) {
LE.print(OS);
return OS;
}
} // namespace genx
// GenXLiveElements - analysis that can give information for 2 types of
// queries:
// 1. What elements of instruction result or function argument are live (i.e.
// can be used later)
// 2. What elements of value are live in some particular use. This gives
// more precise result that live elements of whole value, because
// multiple uses of same value can use different elements
class GenXLiveElements {
public:
void processFunction(const Function &F);
void clear() { LiveMap.clear(); }
genx::LiveElements getLiveElements(const Value *V) const;
genx::LiveElements getLiveElements(const Use *U) const;
private:
ValueMap<const Value *, genx::LiveElements> LiveMap;
genx::LiveElements
getBitCastLiveElements(const BitCastInst *BCI,
const genx::LiveElements &InstLiveElems) const;
genx::LiveElements
getExtractValueLiveElements(const ExtractValueInst *EVI, unsigned OperandNo,
const genx::LiveElements &InstLiveElems) const;
genx::LiveElements
getInsertValueLiveElements(const InsertValueInst *IVI, unsigned OperandNo,
const genx::LiveElements &InstLiveElems) const;
genx::LiveElements
getRdRegionLiveElements(const Instruction *RdR, unsigned OperandNo,
const genx::LiveElements &InstLiveElems) const;
genx::LiveElements
getWrRegionLiveElements(const Instruction *WrR, unsigned OperandNo,
const genx::LiveElements &InstLiveElems) const;
genx::LiveElements
getTwoDstInstLiveElements(const genx::LiveElements &InstLiveElems) const;
genx::LiveElements
getOperandLiveElements(const Instruction *Inst, unsigned OperandNo,
const genx::LiveElements &InstLiveElems) const;
};
// Function pass wrapper for GenXLiveElements
class GenXFuncLiveElements : public FunctionPass,
public GenXLiveElements {
public:
static char ID;
explicit GenXFuncLiveElements() : FunctionPass(ID) {}
StringRef getPassName() const override {
return "GenX live elements analysis for a function";
}
void releaseMemory() override { clear(); }
void getAnalysisUsage(AnalysisUsage &AU) const override {
AU.setPreservesAll();
}
bool runOnFunction(Function &F) override {
clear();
processFunction(F);
return false;
}
};
void initializeGenXFuncLiveElementsPass(PassRegistry &);
// FunctionGroup pass wrapper for GenXLiveElements
class GenXGroupLiveElements : public FGPassImplInterface,
public IDMixin<GenXGroupLiveElements>,
public GenXLiveElements {
public:
static StringRef getPassName() {
return "GenX live elements analysis for a function group";
}
void releaseMemory() override { clear(); }
static void getAnalysisUsage(AnalysisUsage &AU) { AU.setPreservesAll(); }
bool runOnFunctionGroup(FunctionGroup &FG) override {
clear();
for (auto &F : FG)
processFunction(*F);
return false;
}
};
void initializeGenXGroupLiveElementsWrapperPass(PassRegistry &);
using GenXGroupLiveElementsWrapper =
FunctionGroupWrapperPass<GenXGroupLiveElements>;
} // namespace llvm
#endif
|
