LLVM  15.0.0git
DXILValueEnumerator.h
Go to the documentation of this file.
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 
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 
58 
59 private:
61  TypeMapType TypeMap;
62  TypeList Types;
63 
66  ValueList Values;
67 
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.
204  return makeArrayRef(MDs).slice(NumModuleMDs, NumMDStrings);
205  }
206 
207  /// Get the non-MDString metadata for this block.
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();
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
llvm::DIArgList
List of ValueAsMetadata, to be used as an argument to a dbg.value intrinsic.
Definition: DebugInfoMetadata.h:3565
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::dxil::ValueEnumerator::ValueEnumerator
ValueEnumerator(const Module &M, Type *PrefixType)
Definition: DXILValueEnumerator.cpp:362
llvm::NamedMDNode
A tuple of MDNodes.
Definition: Metadata.h:1588
llvm::dxil::ValueEnumerator::getAttributeGroupID
unsigned getAttributeGroupID(IndexAndAttrSet Group) const
Definition: DXILValueEnumerator.h:182
llvm::Function
Definition: Function.h:60
llvm::dxil::ValueEnumerator::purgeFunction
void purgeFunction()
llvm::DenseMapIterator
Definition: DenseMap.h:57
llvm::dxil::ValueEnumerator::getInstructionID
unsigned getInstructionID(const Instruction *I) const
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
DenseMap.h
llvm::AttributeList
Definition: Attributes.h:425
llvm::dxil::ValueEnumerator::dump
void dump() const
T
#define T
Definition: Mips16ISelLowering.cpp:341
llvm::LocalAsMetadata
Definition: Metadata.h:437
llvm::dxil::ValueEnumerator::UseListOrders
UseListOrderStack UseListOrders
Definition: DXILValueEnumerator.h:57
llvm::dxil::ValueEnumerator::TypeList
std::vector< Type * > TypeList
Definition: DXILValueEnumerator.h:48
llvm::dxil::ValueEnumerator::setInstructionID
void setInstructionID(const Instruction *I)
llvm::dxil::ValueEnumerator::getValueID
unsigned getValueID(const Value *V) const
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
llvm::dxil::ValueEnumerator::print
void print(raw_ostream &OS, const ValueMapType &Map, const char *Name) const
llvm::dxil::ValueEnumerator::getTypeID
unsigned getTypeID(Type *T) const
Definition: DXILValueEnumerator.h:165
llvm::dxil::ValueEnumerator
Definition: DXILValueEnumerator.h:46
llvm::dxil::ValueEnumerator::getAttributeGroups
const std::vector< IndexAndAttrSet > & getAttributeGroups() const
Definition: DXILValueEnumerator.h:222
llvm::dxil::ValueEnumerator::getFunctionConstantRange
void getFunctionConstantRange(unsigned &Start, unsigned &End) const
getFunctionConstantRange - Return the range of values that corresponds to function-local constants.
Definition: DXILValueEnumerator.h:192
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::dxil::ValueEnumerator::getComdatID
unsigned getComdatID(const Comdat *C) const
llvm::dxil::ValueEnumerator::getMDStrings
ArrayRef< const Metadata * > getMDStrings() const
Get the MDString metadata for this block.
Definition: DXILValueEnumerator.h:203
First
into llvm powi allowing the code generator to produce balanced multiplication trees First
Definition: README.txt:54
llvm::Instruction
Definition: Instruction.h:42
UniqueVector.h
llvm::dxil::ValueEnumerator::getBasicBlocks
const std::vector< const BasicBlock * > & getBasicBlocks() const
Definition: DXILValueEnumerator.h:214
llvm::dxil::ValueEnumerator::getAttributeListID
unsigned getAttributeListID(AttributeList PAL) const
Definition: DXILValueEnumerator.h:174
llvm::dxil::ValueEnumerator::getNonMDStrings
ArrayRef< const Metadata * > getNonMDStrings() const
Get the non-MDString metadata for this block.
Definition: DXILValueEnumerator.h:208
llvm::UniqueVector< const Comdat * >
llvm::Comdat
Definition: Comdat.h:33
llvm::Metadata
Root of the metadata hierarchy.
Definition: Metadata.h:62
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
llvm::dxil::ValueEnumerator::IndexAndAttrSet
std::pair< unsigned, AttributeSet > IndexAndAttrSet
Attribute groups as encoded in bitcode are almost AttributeSets, but they include the AttributeList i...
Definition: DXILValueEnumerator.h:55
llvm::dxil::ValueEnumerator::getValues
const ValueList & getValues() const
Definition: DXILValueEnumerator.h:197
llvm::dxil::ValueEnumerator::computeBitsRequiredForTypeIndicies
uint64_t computeBitsRequiredForTypeIndicies() const
llvm::dxil::ValueEnumerator::getTypes
const TypeList & getTypes() const
Definition: DXILValueEnumerator.h:212
uint64_t
llvm::ARM_MB::ST
@ ST
Definition: ARMBaseInfo.h:73
llvm::DenseMapBase< DenseMap< const Metadata *, MDIndex, DenseMapInfo< const Metadata * >, llvm::detail::DenseMapPair< const Metadata *, MDIndex > >, const Metadata *, MDIndex, DenseMapInfo< const Metadata * >, llvm::detail::DenseMapPair< const Metadata *, MDIndex > >::value_type
llvm::detail::DenseMapPair< const Metadata *, MDIndex > value_type
Definition: DenseMap.h:69
llvm::DenseMap< Type *, unsigned >
I
#define I(x, y, z)
Definition: MD5.cpp:58
ArrayRef.h
TemplateParamKind::Type
@ Type
llvm::DenseMapBase::find
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:152
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::ISD::BasicBlock
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:71
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
llvm::MDNode
Metadata node.
Definition: Metadata.h:944
llvm::dxil::ValueEnumerator::getAttributeLists
const std::vector< AttributeList > & getAttributeLists() const
Definition: DXILValueEnumerator.h:218
llvm::dxil::ValueEnumerator::getMetadataID
unsigned getMetadataID(const Metadata *MD) const
Definition: DXILValueEnumerator.h:153
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::dxil::ValueEnumerator::getComdats
const ComdatSetType & getComdats() const
Definition: DXILValueEnumerator.h:226
llvm::dxil::ValueEnumerator::getGlobalBasicBlockID
unsigned getGlobalBasicBlockID(const BasicBlock *BB) const
getGlobalBasicBlockID - This returns the function-specific ID for the specified basic block.
Module
Machine Check Debug Module
Definition: MachineCheckDebugify.cpp:122
llvm::ValueMap
See the file comment.
Definition: ValueMap.h:85
llvm::dxil::ValueEnumerator::ValueList
std::vector< std::pair< const Value *, unsigned > > ValueList
Definition: DXILValueEnumerator.h:51
Attributes.h
llvm::UseListOrderStack
std::vector< UseListOrder > UseListOrderStack
Definition: UseListOrder.h:39
llvm::dxil::ValueEnumerator::EnumerateType
void EnumerateType(Type *T)
llvm::GraphProgram::Name
Name
Definition: GraphWriter.h:50
llvm::dxil::ValueEnumerator::numMDs
unsigned numMDs() const
Definition: DXILValueEnumerator.h:163
get
Should compile to something r4 addze r3 instead we get
Definition: README.txt:24
llvm::DenseMapBase::end
iterator end()
Definition: DenseMap.h:84
llvm::TargetStackID::Value
Value
Definition: TargetFrameLowering.h:27
llvm::makeArrayRef
ArrayRef< T > makeArrayRef(const T &OneElt)
Construct an ArrayRef from a single element.
Definition: ArrayRef.h:475
llvm::dxil::ValueEnumerator::hasMDs
bool hasMDs() const
Check whether the current block has any metadata to emit.
Definition: DXILValueEnumerator.h:200
PrefixType
PrefixType
Definition: AsmWriter.cpp:340
llvm::ValueSymbolTable
This class provides a symbol table of name/value pairs.
Definition: ValueSymbolTable.h:37
LineType::Metadata
@ Metadata
llvm::ArrayRef::size
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:164
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
UseListOrder.h
llvm::dxil::ValueEnumerator::getMetadataOrNullID
unsigned getMetadataOrNullID(const Metadata *MD) const
Definition: DXILValueEnumerator.h:159
llvm::dxil::ValueEnumerator::incorporateFunction
void incorporateFunction(const Function &F)
incorporateFunction/purgeFunction - If you'd like to deal with a function, use these two methods to g...
llvm::dxil::ValueEnumerator::operator=
ValueEnumerator & operator=(const ValueEnumerator &)=delete
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::AttributeList::isEmpty
bool isEmpty() const
Return true if there are no attributes.
Definition: Attributes.h:926
llvm::codeview::PublicSymFlags::Function
@ Function