1 //===- DirectX/DXILWriter/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 // Forked from lib/Bitcode/Writer
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #ifndef LLVM_DXILWRITER_VALUEENUMERATOR_H
15 #define LLVM_DXILWRITER_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 DIArgList;
32 class Function;
33 class Instruction;
34 class LocalAsMetadata;
35 class MDNode;
36 class Metadata;
37 class Module;
38 class NamedMDNode;
39 class raw_ostream;
40 class Type;
41 class Value;
42 class ValueSymbolTable;
43 
44 namespace dxil {
45 
46 class ValueEnumerator {
47 public:
48   using TypeList = std::vector<Type *>;
49 
50   // For each value, we remember its Value* and occurrence frequency.
51   using ValueList = std::vector<std::pair<const Value *, unsigned>>;
52 
53   /// Attribute groups as encoded in bitcode are almost AttributeSets, but they
54   /// include the AttributeList index, so we have to track that in our map.
55   using IndexAndAttrSet = std::pair<unsigned, AttributeSet>;
56 
57   UseListOrderStack UseListOrders;
58 
59 private:
60   using TypeMapType = DenseMap<Type *, unsigned>;
61   TypeMapType TypeMap;
62   TypeList Types;
63 
64   using ValueMapType = DenseMap<const Value *, unsigned>;
65   ValueMapType ValueMap;
66   ValueList Values;
67 
68   using ComdatSetType = UniqueVector<const Comdat *>;
69   ComdatSetType Comdats;
70 
71   std::vector<const Metadata *> MDs;
72   std::vector<const Metadata *> FunctionMDs;
73 
74   /// Index of information about a piece of metadata.
75   struct MDIndex {
76     unsigned F = 0;  ///< The ID of the function for this metadata, if any.
77     unsigned ID = 0; ///< The implicit ID of this metadata in bitcode.
78 
79     MDIndex() = default;
80     explicit MDIndex(unsigned F) : F(F) {}
81 
82     /// Check if this has a function tag, and it's different from NewF.
83     bool hasDifferentFunction(unsigned NewF) const { return F && F != NewF; }
84 
85     /// Fetch the MD this references out of the given metadata array.
86     const Metadata *get(ArrayRef<const Metadata *> MDs) const {
87       assert(ID && "Expected non-zero ID");
88       assert(ID <= MDs.size() && "Expected valid ID");
89       return MDs[ID - 1];
90     }
91   };
92 
93   using MetadataMapType = DenseMap<const Metadata *, MDIndex>;
94   MetadataMapType MetadataMap;
95 
96   /// Range of metadata IDs, as a half-open range.
97   struct MDRange {
98     unsigned First = 0;
99     unsigned Last = 0;
100 
101     /// Number of strings in the prefix of the metadata range.
102     unsigned NumStrings = 0;
103 
104     MDRange() = default;
105     explicit MDRange(unsigned First) : First(First) {}
106   };
107   SmallDenseMap<unsigned, MDRange, 1> FunctionMDInfo;
108 
109   using AttributeGroupMapType = DenseMap<IndexAndAttrSet, unsigned>;
110   AttributeGroupMapType AttributeGroupMap;
111   std::vector<IndexAndAttrSet> AttributeGroups;
112 
113   using AttributeListMapType = DenseMap<AttributeList, unsigned>;
114   AttributeListMapType AttributeListMap;
115   std::vector<AttributeList> AttributeLists;
116 
117   /// GlobalBasicBlockIDs - This map memoizes the basic block ID's referenced by
118   /// the "getGlobalBasicBlockID" method.
119   mutable DenseMap<const BasicBlock *, unsigned> GlobalBasicBlockIDs;
120 
121   using InstructionMapType = DenseMap<const Instruction *, unsigned>;
122   InstructionMapType InstructionMap;
123   unsigned InstructionCount;
124 
125   /// BasicBlocks - This contains all the basic blocks for the currently
126   /// incorporated function.  Their reverse mapping is stored in ValueMap.
127   std::vector<const BasicBlock *> BasicBlocks;
128 
129   /// When a function is incorporated, this is the size of the Values list
130   /// before incorporation.
131   unsigned NumModuleValues;
132 
133   /// When a function is incorporated, this is the size of the Metadatas list
134   /// before incorporation.
135   unsigned NumModuleMDs = 0;
136   unsigned NumMDStrings = 0;
137 
138   unsigned FirstFuncConstantID;
139   unsigned FirstInstID;
140 
141 public:
142   ValueEnumerator(const Module &M, Type *PrefixType);
143   ValueEnumerator(const ValueEnumerator &) = delete;
144   ValueEnumerator &operator=(const ValueEnumerator &) = delete;
145 
146   void dump() const;
147   void print(raw_ostream &OS, const ValueMapType &Map, const char *Name) const;
148   void print(raw_ostream &OS, const MetadataMapType &Map,
149              const char *Name) const;
150 
151   unsigned getValueID(const Value *V) const;
152 
153   unsigned getMetadataID(const Metadata *MD) const {
154     auto ID = getMetadataOrNullID(MD);
155     assert(ID != 0 && "Metadata not in slotcalculator!");
156     return ID - 1;
157   }
158 
159   unsigned getMetadataOrNullID(const Metadata *MD) const {
160     return MetadataMap.lookup(MD).ID;
161   }
162 
163   unsigned numMDs() const { return MDs.size(); }
164 
165   unsigned getTypeID(Type *T) const {
166     TypeMapType::const_iterator I = TypeMap.find(T);
167     assert(I != TypeMap.end() && "Type not in ValueEnumerator!");
168     return I->second - 1;
169   }
170 
171   unsigned getInstructionID(const Instruction *I) const;
172   void setInstructionID(const Instruction *I);
173 
174   unsigned getAttributeListID(AttributeList PAL) const {
175     if (PAL.isEmpty())
176       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 {
219     return AttributeLists;
220   }
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   void EnumerateType(Type *T);
242 
243 private:
244 
245   /// Reorder the reachable metadata.
246   ///
247   /// This is not just an optimization, but is mandatory for emitting MDString
248   /// correctly.
249   void organizeMetadata();
250 
251   /// Drop the function tag from the transitive operands of the given node.
252   void dropFunctionFromMetadata(MetadataMapType::value_type &FirstMD);
253 
254   /// Incorporate the function metadata.
255   ///
256   /// This should be called before enumerating LocalAsMetadata for the
257   /// function.
258   void incorporateFunctionMetadata(const Function &F);
259 
260   /// Enumerate a single instance of metadata with the given function tag.
261   ///
262   /// If \c MD has already been enumerated, check that \c F matches its
263   /// function tag.  If not, call \a dropFunctionFromMetadata().
264   ///
265   /// Otherwise, mark \c MD as visited.  Assign it an ID, or just return it if
266   /// it's an \a MDNode.
267   const MDNode *enumerateMetadataImpl(unsigned F, const Metadata *MD);
268 
269   unsigned getMetadataFunctionID(const Function *F) const;
270 
271   /// Enumerate reachable metadata in (almost) post-order.
272   ///
273   /// Enumerate all the metadata reachable from MD.  We want to minimize the
274   /// cost of reading bitcode records, and so the primary consideration is that
275   /// operands of uniqued nodes are resolved before the nodes are read.  This
276   /// avoids re-uniquing them on the context and factors away RAUW support.
277   ///
278   /// This algorithm guarantees that subgraphs of uniqued nodes are in
279   /// post-order.  Distinct subgraphs reachable only from a single uniqued node
280   /// will be in post-order.
281   ///
282   /// \note The relative order of a distinct and uniqued node is irrelevant.
283   /// \a organizeMetadata() will later partition distinct nodes ahead of
284   /// uniqued ones.
285   ///{
286   void EnumerateMetadata(const Function *F, const Metadata *MD);
287   void EnumerateMetadata(unsigned F, const Metadata *MD);
288   ///}
289 
290   void EnumerateFunctionLocalMetadata(const Function &F,
291                                       const LocalAsMetadata *Local);
292   void EnumerateFunctionLocalMetadata(unsigned F, const LocalAsMetadata *Local);
293   void EnumerateFunctionLocalListMetadata(const Function &F,
294                                           const DIArgList *ArgList);
295   void EnumerateFunctionLocalListMetadata(unsigned F, const DIArgList *Arglist);
296   void EnumerateNamedMDNode(const NamedMDNode *NMD);
297   void EnumerateValue(const Value *V);
298   void EnumerateOperandType(const Value *V);
299   void EnumerateAttributes(AttributeList PAL);
300 
301   void EnumerateValueSymbolTable(const ValueSymbolTable &ST);
302   void EnumerateNamedMetadata(const Module &M);
303 };
304 
305 } // end namespace dxil
306 } // end namespace llvm
307 
308 #endif // LLVM_DXILWRITER_VALUEENUMERATOR_H
309