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