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