1 //===- Bitcode/Writer/ValueEnumerator.h - Number values ---------*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This class gives values and types Unique ID's.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #ifndef LLVM_LIB_BITCODE_WRITER_VALUEENUMERATOR_H
14 #define LLVM_LIB_BITCODE_WRITER_VALUEENUMERATOR_H
15 
16 #include "llvm/ADT/ArrayRef.h"
17 #include "llvm/ADT/DenseMap.h"
18 #include "llvm/ADT/UniqueVector.h"
19 #include "llvm/IR/Attributes.h"
20 #include "llvm/IR/UseListOrder.h"
21 #include <cassert>
22 #include <cstdint>
23 #include <utility>
24 #include <vector>
25 
26 namespace llvm {
27 
28 class BasicBlock;
29 class Comdat;
30 class DIArgList;
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     MDIndex() = default;
77     explicit MDIndex(unsigned F) : F(F) {}
78 
79     /// Check if this has a function tag, and it's different from NewF.
80     bool hasDifferentFunction(unsigned NewF) const { return F && F != NewF; }
81 
82     /// Fetch the MD this references out of the given metadata array.
83     const Metadata *get(ArrayRef<const Metadata *> MDs) const {
84       assert(ID && "Expected non-zero ID");
85       assert(ID <= MDs.size() && "Expected valid ID");
86       return MDs[ID - 1];
87     }
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     MDRange() = default;
102     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   unsigned getMetadataID(const Metadata *MD) const {
153     auto ID = getMetadataOrNullID(MD);
154     assert(ID != 0 && "Metadata not in slotcalculator!");
155     return ID - 1;
156   }
157 
158   unsigned getMetadataOrNullID(const Metadata *MD) const {
159     return MetadataMap.lookup(MD).ID;
160   }
161 
162   unsigned numMDs() const { return MDs.size(); }
163 
164   bool shouldPreserveUseListOrder() const { return ShouldPreserveUseListOrder; }
165 
166   unsigned getTypeID(Type *T) const {
167     TypeMapType::const_iterator I = TypeMap.find(T);
168     assert(I != TypeMap.end() && "Type not in ValueEnumerator!");
169     return I->second-1;
170   }
171 
172   unsigned getInstructionID(const Instruction *I) const;
173   void setInstructionID(const Instruction *I);
174 
175   unsigned getAttributeListID(AttributeList PAL) const {
176     if (PAL.isEmpty()) return 0;  // Null maps to zero.
177     AttributeListMapType::const_iterator I = AttributeListMap.find(PAL);
178     assert(I != AttributeListMap.end() && "Attribute not in ValueEnumerator!");
179     return I->second;
180   }
181 
182   unsigned getAttributeGroupID(IndexAndAttrSet Group) const {
183     if (!Group.second.hasAttributes())
184       return 0; // Null maps to zero.
185     AttributeGroupMapType::const_iterator I = AttributeGroupMap.find(Group);
186     assert(I != AttributeGroupMap.end() && "Attribute not in ValueEnumerator!");
187     return I->second;
188   }
189 
190   /// getFunctionConstantRange - Return the range of values that corresponds to
191   /// function-local constants.
192   void getFunctionConstantRange(unsigned &Start, unsigned &End) const {
193     Start = FirstFuncConstantID;
194     End = FirstInstID;
195   }
196 
197   const ValueList &getValues() const { return Values; }
198 
199   /// Check whether the current block has any metadata to emit.
200   bool hasMDs() const { return NumModuleMDs < MDs.size(); }
201 
202   /// Get the MDString metadata for this block.
203   ArrayRef<const Metadata *> getMDStrings() const {
204     return makeArrayRef(MDs).slice(NumModuleMDs, NumMDStrings);
205   }
206 
207   /// Get the non-MDString metadata for this block.
208   ArrayRef<const Metadata *> getNonMDStrings() const {
209     return makeArrayRef(MDs).slice(NumModuleMDs).slice(NumMDStrings);
210   }
211 
212   const TypeList &getTypes() const { return Types; }
213 
214   const std::vector<const BasicBlock*> &getBasicBlocks() const {
215     return BasicBlocks;
216   }
217 
218   const std::vector<AttributeList> &getAttributeLists() const { return AttributeLists; }
219 
220   const std::vector<IndexAndAttrSet> &getAttributeGroups() const {
221     return AttributeGroups;
222   }
223 
224   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 EnumerateFunctionLocalListMetadata(const Function &F,
291                                           const DIArgList *ArgList);
292   void EnumerateFunctionLocalListMetadata(unsigned F, const DIArgList *Arglist);
293   void EnumerateNamedMDNode(const NamedMDNode *NMD);
294   void EnumerateValue(const Value *V);
295   void EnumerateType(Type *T);
296   void EnumerateOperandType(const Value *V);
297   void EnumerateAttributes(AttributeList PAL);
298 
299   void EnumerateValueSymbolTable(const ValueSymbolTable &ST);
300   void EnumerateNamedMetadata(const Module &M);
301 };
302 
303 } // end namespace llvm
304 
305 #endif // LLVM_LIB_BITCODE_WRITER_VALUEENUMERATOR_H
306