Line data Source code
1 : //===- Bitcode/Writer/ValueEnumerator.h - Number values ---------*- C++ -*-===//
2 : //
3 : // The LLVM Compiler Infrastructure
4 : //
5 : // This file is distributed under the University of Illinois Open Source
6 : // License. See LICENSE.TXT for details.
7 : //
8 : //===----------------------------------------------------------------------===//
9 : //
10 : // This class gives values and types Unique ID's.
11 : //
12 : //===----------------------------------------------------------------------===//
13 :
14 : #ifndef LLVM_LIB_BITCODE_WRITER_VALUEENUMERATOR_H
15 : #define LLVM_LIB_BITCODE_WRITER_VALUEENUMERATOR_H
16 :
17 : #include "llvm/ADT/ArrayRef.h"
18 : #include "llvm/ADT/DenseMap.h"
19 : #include "llvm/ADT/UniqueVector.h"
20 : #include "llvm/IR/Attributes.h"
21 : #include "llvm/IR/Metadata.h"
22 : #include "llvm/IR/Type.h"
23 : #include "llvm/IR/UseListOrder.h"
24 : #include <cassert>
25 : #include <cstdint>
26 : #include <utility>
27 : #include <vector>
28 :
29 : namespace llvm {
30 :
31 : class BasicBlock;
32 : class Comdat;
33 : class Function;
34 : class Instruction;
35 : class LocalAsMetadata;
36 : class MDNode;
37 : class Metadata;
38 : class Module;
39 : class NamedMDNode;
40 : class raw_ostream;
41 : class Type;
42 : class Value;
43 : class ValueSymbolTable;
44 :
45 : class ValueEnumerator {
46 : public:
47 : using TypeList = std::vector<Type *>;
48 :
49 : // For each value, we remember its Value* and occurrence frequency.
50 : using ValueList = std::vector<std::pair<const Value *, unsigned>>;
51 :
52 : /// Attribute groups as encoded in bitcode are almost AttributeSets, but they
53 : /// include the AttributeList index, so we have to track that in our map.
54 : using IndexAndAttrSet = std::pair<unsigned, AttributeSet>;
55 :
56 : UseListOrderStack UseListOrders;
57 :
58 : private:
59 : using TypeMapType = DenseMap<Type *, unsigned>;
60 : TypeMapType TypeMap;
61 : TypeList Types;
62 :
63 : using ValueMapType = DenseMap<const Value *, unsigned>;
64 : ValueMapType ValueMap;
65 : ValueList Values;
66 :
67 : using ComdatSetType = UniqueVector<const Comdat *>;
68 : ComdatSetType Comdats;
69 :
70 : std::vector<const Metadata *> MDs;
71 : std::vector<const Metadata *> FunctionMDs;
72 :
73 : /// Index of information about a piece of metadata.
74 : struct MDIndex {
75 : unsigned F = 0; ///< The ID of the function for this metadata, if any.
76 : unsigned ID = 0; ///< The implicit ID of this metadata in bitcode.
77 :
78 : MDIndex() = default;
79 : explicit MDIndex(unsigned F) : F(F) {}
80 :
81 : /// Check if this has a function tag, and it's different from NewF.
82 22235 : bool hasDifferentFunction(unsigned NewF) const { return F && F != NewF; }
83 :
84 : /// Fetch the MD this references out of the given metadata array.
85 0 : const Metadata *get(ArrayRef<const Metadata *> MDs) const {
86 : assert(ID && "Expected non-zero ID");
87 : assert(ID <= MDs.size() && "Expected valid ID");
88 56286 : return MDs[ID - 1];
89 : }
90 : };
91 :
92 : using MetadataMapType = DenseMap<const Metadata *, MDIndex>;
93 : MetadataMapType MetadataMap;
94 :
95 : /// Range of metadata IDs, as a half-open range.
96 : struct MDRange {
97 : unsigned First = 0;
98 : unsigned Last = 0;
99 :
100 : /// Number of strings in the prefix of the metadata range.
101 : unsigned NumStrings = 0;
102 :
103 : MDRange() = default;
104 : explicit MDRange(unsigned First) : First(First) {}
105 : };
106 : SmallDenseMap<unsigned, MDRange, 1> FunctionMDInfo;
107 :
108 : bool ShouldPreserveUseListOrder;
109 :
110 : using AttributeGroupMapType = DenseMap<IndexAndAttrSet, unsigned>;
111 : AttributeGroupMapType AttributeGroupMap;
112 : std::vector<IndexAndAttrSet> AttributeGroups;
113 :
114 : using AttributeListMapType = DenseMap<AttributeList, unsigned>;
115 : AttributeListMapType AttributeListMap;
116 : std::vector<AttributeList> AttributeLists;
117 :
118 : /// GlobalBasicBlockIDs - This map memoizes the basic block ID's referenced by
119 : /// the "getGlobalBasicBlockID" method.
120 : mutable DenseMap<const BasicBlock*, unsigned> GlobalBasicBlockIDs;
121 :
122 : using InstructionMapType = DenseMap<const Instruction *, unsigned>;
123 : InstructionMapType InstructionMap;
124 : unsigned InstructionCount;
125 :
126 : /// BasicBlocks - This contains all the basic blocks for the currently
127 : /// incorporated function. Their reverse mapping is stored in ValueMap.
128 : std::vector<const BasicBlock*> BasicBlocks;
129 :
130 : /// When a function is incorporated, this is the size of the Values list
131 : /// before incorporation.
132 : unsigned NumModuleValues;
133 :
134 : /// When a function is incorporated, this is the size of the Metadatas list
135 : /// before incorporation.
136 : unsigned NumModuleMDs = 0;
137 : unsigned NumMDStrings = 0;
138 :
139 : unsigned FirstFuncConstantID;
140 : unsigned FirstInstID;
141 :
142 : public:
143 : ValueEnumerator(const Module &M, bool ShouldPreserveUseListOrder);
144 : ValueEnumerator(const ValueEnumerator &) = delete;
145 : ValueEnumerator &operator=(const ValueEnumerator &) = delete;
146 :
147 : void dump() const;
148 : void print(raw_ostream &OS, const ValueMapType &Map, const char *Name) const;
149 : void print(raw_ostream &OS, const MetadataMapType &Map,
150 : const char *Name) const;
151 :
152 : unsigned getValueID(const Value *V) const;
153 :
154 : unsigned getMetadataID(const Metadata *MD) const {
155 : auto ID = getMetadataOrNullID(MD);
156 : assert(ID != 0 && "Metadata not in slotcalculator!");
157 13457 : return ID - 1;
158 : }
159 :
160 : unsigned getMetadataOrNullID(const Metadata *MD) const {
161 62501 : return MetadataMap.lookup(MD).ID;
162 : }
163 :
164 : unsigned numMDs() const { return MDs.size(); }
165 :
166 0 : bool shouldPreserveUseListOrder() const { return ShouldPreserveUseListOrder; }
167 :
168 : unsigned getTypeID(Type *T) const {
169 261120 : TypeMapType::const_iterator I = TypeMap.find(T);
170 : assert(I != TypeMap.end() && "Type not in ValueEnumerator!");
171 261120 : return I->second-1;
172 : }
173 :
174 : unsigned getInstructionID(const Instruction *I) const;
175 : void setInstructionID(const Instruction *I);
176 :
177 : unsigned getAttributeListID(AttributeList PAL) const {
178 37487 : if (PAL.isEmpty()) return 0; // Null maps to zero.
179 11906 : AttributeListMapType::const_iterator I = AttributeListMap.find(PAL);
180 : assert(I != AttributeListMap.end() && "Attribute not in ValueEnumerator!");
181 11906 : return I->second;
182 : }
183 :
184 : unsigned getAttributeGroupID(IndexAndAttrSet Group) const {
185 4806 : if (!Group.second.hasAttributes())
186 : return 0; // Null maps to zero.
187 11171 : AttributeGroupMapType::const_iterator I = AttributeGroupMap.find(Group);
188 : assert(I != AttributeGroupMap.end() && "Attribute not in ValueEnumerator!");
189 11171 : return I->second;
190 : }
191 :
192 : /// getFunctionConstantRange - Return the range of values that corresponds to
193 : /// function-local constants.
194 0 : void getFunctionConstantRange(unsigned &Start, unsigned &End) const {
195 0 : Start = FirstFuncConstantID;
196 12178 : End = FirstInstID;
197 0 : }
198 :
199 : const ValueList &getValues() const { return Values; }
200 :
201 : /// Check whether the current block has any metadata to emit.
202 4708 : bool hasMDs() const { return NumModuleMDs < MDs.size(); }
203 :
204 : /// Get the MDString metadata for this block.
205 : ArrayRef<const Metadata *> getMDStrings() const {
206 1249 : return makeArrayRef(MDs).slice(NumModuleMDs, NumMDStrings);
207 : }
208 :
209 : /// Get the non-MDString metadata for this block.
210 : ArrayRef<const Metadata *> getNonMDStrings() const {
211 2766 : return makeArrayRef(MDs).slice(NumModuleMDs).slice(NumMDStrings);
212 : }
213 :
214 : const TypeList &getTypes() const { return Types; }
215 :
216 : const std::vector<const BasicBlock*> &getBasicBlocks() const {
217 : return BasicBlocks;
218 : }
219 :
220 : const std::vector<AttributeList> &getAttributeLists() const { return AttributeLists; }
221 :
222 : const std::vector<IndexAndAttrSet> &getAttributeGroups() const {
223 : return AttributeGroups;
224 : }
225 :
226 : const ComdatSetType &getComdats() const { return Comdats; }
227 : unsigned getComdatID(const Comdat *C) const;
228 :
229 : /// getGlobalBasicBlockID - This returns the function-specific ID for the
230 : /// specified basic block. This is relatively expensive information, so it
231 : /// should only be used by rare constructs such as address-of-label.
232 : unsigned getGlobalBasicBlockID(const BasicBlock *BB) const;
233 :
234 : /// incorporateFunction/purgeFunction - If you'd like to deal with a function,
235 : /// use these two methods to get its data into the ValueEnumerator!
236 : void incorporateFunction(const Function &F);
237 :
238 : void purgeFunction();
239 : uint64_t computeBitsRequiredForTypeIndicies() const;
240 :
241 : private:
242 : void OptimizeConstants(unsigned CstStart, unsigned CstEnd);
243 :
244 : /// Reorder the reachable metadata.
245 : ///
246 : /// This is not just an optimization, but is mandatory for emitting MDString
247 : /// correctly.
248 : void organizeMetadata();
249 :
250 : /// Drop the function tag from the transitive operands of the given node.
251 : void dropFunctionFromMetadata(MetadataMapType::value_type &FirstMD);
252 :
253 : /// Incorporate the function metadata.
254 : ///
255 : /// This should be called before enumerating LocalAsMetadata for the
256 : /// function.
257 : void incorporateFunctionMetadata(const Function &F);
258 :
259 : /// Enumerate a single instance of metadata with the given function tag.
260 : ///
261 : /// If \c MD has already been enumerated, check that \c F matches its
262 : /// function tag. If not, call \a dropFunctionFromMetadata().
263 : ///
264 : /// Otherwise, mark \c MD as visited. Assign it an ID, or just return it if
265 : /// it's an \a MDNode.
266 : const MDNode *enumerateMetadataImpl(unsigned F, const Metadata *MD);
267 :
268 : unsigned getMetadataFunctionID(const Function *F) const;
269 :
270 : /// Enumerate reachable metadata in (almost) post-order.
271 : ///
272 : /// Enumerate all the metadata reachable from MD. We want to minimize the
273 : /// cost of reading bitcode records, and so the primary consideration is that
274 : /// operands of uniqued nodes are resolved before the nodes are read. This
275 : /// avoids re-uniquing them on the context and factors away RAUW support.
276 : ///
277 : /// This algorithm guarantees that subgraphs of uniqued nodes are in
278 : /// post-order. Distinct subgraphs reachable only from a single uniqued node
279 : /// will be in post-order.
280 : ///
281 : /// \note The relative order of a distinct and uniqued node is irrelevant.
282 : /// \a organizeMetadata() will later partition distinct nodes ahead of
283 : /// uniqued ones.
284 : ///{
285 : void EnumerateMetadata(const Function *F, const Metadata *MD);
286 : void EnumerateMetadata(unsigned F, const Metadata *MD);
287 : ///}
288 :
289 : void EnumerateFunctionLocalMetadata(const Function &F,
290 : const LocalAsMetadata *Local);
291 : void EnumerateFunctionLocalMetadata(unsigned F, const LocalAsMetadata *Local);
292 : void EnumerateNamedMDNode(const NamedMDNode *NMD);
293 : void EnumerateValue(const Value *V);
294 : void EnumerateType(Type *T);
295 : void EnumerateOperandType(const Value *V);
296 : void EnumerateAttributes(AttributeList PAL);
297 :
298 : void EnumerateValueSymbolTable(const ValueSymbolTable &ST);
299 : void EnumerateNamedMetadata(const Module &M);
300 : };
301 :
302 : } // end namespace llvm
303 :
304 : #endif // LLVM_LIB_BITCODE_WRITER_VALUEENUMERATOR_H
|
