LLVM  14.0.0git
ValueEnumerator.h
Go to the documentation of this file.
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 
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 
55 
56 private:
58  TypeMapType TypeMap;
59  TypeList Types;
60 
63  ValueList Values;
64 
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.
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 { 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();
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
llvm::ValueEnumerator::getAttributeGroups
const std::vector< IndexAndAttrSet > & getAttributeGroups() const
Definition: ValueEnumerator.h:220
llvm::ValueEnumerator::getTypes
const TypeList & getTypes() const
Definition: ValueEnumerator.h:212
llvm::DIArgList
List of ValueAsMetadata, to be used as an argument to a dbg.value intrinsic.
Definition: DebugInfoMetadata.h:3604
llvm
This file implements support for optimizing divisions by a constant.
Definition: AllocatorList.h:23
llvm::ValueEnumerator::getAttributeLists
const std::vector< AttributeList > & getAttributeLists() const
Definition: ValueEnumerator.h:218
llvm::NamedMDNode
A tuple of MDNodes.
Definition: Metadata.h:1421
llvm::ValueEnumerator::IndexAndAttrSet
std::pair< unsigned, AttributeSet > IndexAndAttrSet
Attribute groups as encoded in bitcode are almost AttributeSets, but they include the AttributeList i...
Definition: ValueEnumerator.h:52
llvm::Function
Definition: Function.h:62
llvm::DenseMapIterator
Definition: DenseMap.h:56
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:399
llvm::ValueEnumerator::getMetadataID
unsigned getMetadataID(const Metadata *MD) const
Definition: ValueEnumerator.h:152
T
#define T
Definition: Mips16ISelLowering.cpp:341
llvm::LocalAsMetadata
Definition: Metadata.h:436
llvm::ValueEnumerator::getTypeID
unsigned getTypeID(Type *T) const
Definition: ValueEnumerator.h:166
llvm::ValueEnumerator::numMDs
unsigned numMDs() const
Definition: ValueEnumerator.h:162
llvm::ValueEnumerator::getValues
const ValueList & getValues() const
Definition: ValueEnumerator.h:197
llvm::ValueEnumerator::UseListOrders
UseListOrderStack UseListOrders
Definition: ValueEnumerator.h:54
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::ValueEnumerator::getBasicBlocks
const std::vector< const BasicBlock * > & getBasicBlocks() const
Definition: ValueEnumerator.h:214
llvm::ValueEnumerator::getInstructionID
unsigned getInstructionID(const Instruction *I) const
Definition: ValueEnumerator.cpp:506
llvm::ValueEnumerator::getNonMDStrings
ArrayRef< const Metadata * > getNonMDStrings() const
Get the non-MDString metadata for this block.
Definition: ValueEnumerator.h:208
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::ValueEnumerator::computeBitsRequiredForTypeIndicies
uint64_t computeBitsRequiredForTypeIndicies() const
Definition: ValueEnumerator.cpp:1179
llvm::ValueEnumerator::getAttributeGroupID
unsigned getAttributeGroupID(IndexAndAttrSet Group) const
Definition: ValueEnumerator.h:182
First
into llvm powi allowing the code generator to produce balanced multiplication trees First
Definition: README.txt:54
llvm::ValueEnumerator
Definition: ValueEnumerator.h:43
llvm::Instruction
Definition: Instruction.h:45
UniqueVector.h
llvm::UniqueVector< const Comdat * >
llvm::Comdat
Definition: Comdat.h:31
llvm::Metadata
Root of the metadata hierarchy.
Definition: Metadata.h:62
llvm::ValueEnumerator::getValueID
unsigned getValueID(const Value *V) const
Definition: ValueEnumerator.cpp:522
llvm::ValueEnumerator::print
void print(raw_ostream &OS, const ValueMapType &Map, const char *Name) const
Definition: ValueEnumerator.cpp:540
llvm::ValueEnumerator::shouldPreserveUseListOrder
bool shouldPreserveUseListOrder() const
Definition: ValueEnumerator.h:164
llvm::ValueEnumerator::getMetadataOrNullID
unsigned getMetadataOrNullID(const Metadata *MD) const
Definition: ValueEnumerator.h:158
llvm::ValueEnumerator::getAttributeListID
unsigned getAttributeListID(AttributeList PAL) const
Definition: ValueEnumerator.h:175
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:68
llvm::DenseMap< Type *, unsigned >
I
#define I(x, y, z)
Definition: MD5.cpp:59
ArrayRef.h
TemplateParamKind::Type
@ Type
llvm::DenseMapBase::find
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:150
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::ValueEnumerator::incorporateFunction
void incorporateFunction(const Function &F)
incorporateFunction/purgeFunction - If you'd like to deal with a function, use these two methods to g...
Definition: ValueEnumerator.cpp:1060
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:67
llvm::MDNode
Metadata node.
Definition: Metadata.h:906
llvm::ValueEnumerator::dump
void dump() const
Definition: ValueEnumerator.cpp:532
llvm::ValueEnumerator::setInstructionID
void setInstructionID(const Instruction *I)
Definition: ValueEnumerator.cpp:518
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::ValueEnumerator::hasMDs
bool hasMDs() const
Check whether the current block has any metadata to emit.
Definition: ValueEnumerator.h:200
Module
Machine Check Debug Module
Definition: MachineCheckDebugify.cpp:122
llvm::ValueMap
See the file comment.
Definition: ValueMap.h:85
Attributes.h
llvm::UseListOrderStack
std::vector< UseListOrder > UseListOrderStack
Definition: UseListOrder.h:39
llvm::GraphProgram::Name
Name
Definition: GraphWriter.h:52
get
Should compile to something r4 addze r3 instead we get
Definition: README.txt:24
llvm::DenseMapBase::end
iterator end()
Definition: DenseMap.h:83
llvm::TargetStackID::Value
Value
Definition: TargetFrameLowering.h:27
llvm::ValueEnumerator::operator=
ValueEnumerator & operator=(const ValueEnumerator &)=delete
llvm::ValueEnumerator::getComdatID
unsigned getComdatID(const Comdat *C) const
Definition: ValueEnumerator.cpp:512
llvm::makeArrayRef
ArrayRef< T > makeArrayRef(const T &OneElt)
Construct an ArrayRef from a single element.
Definition: ArrayRef.h:476
llvm::ValueEnumerator::getGlobalBasicBlockID
unsigned getGlobalBasicBlockID(const BasicBlock *BB) const
getGlobalBasicBlockID - This returns the function-specific ID for the specified basic block.
Definition: ValueEnumerator.cpp:1170
llvm::ValueEnumerator::ValueList
std::vector< std::pair< const Value *, unsigned > > ValueList
Definition: ValueEnumerator.h:48
llvm::ValueEnumerator::ValueEnumerator
ValueEnumerator(const Module &M, bool ShouldPreserveUseListOrder)
Definition: ValueEnumerator.cpp:364
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:165
llvm::ValueEnumerator::getMDStrings
ArrayRef< const Metadata * > getMDStrings() const
Get the MDString metadata for this block.
Definition: ValueEnumerator.h:203
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::ValueEnumerator::purgeFunction
void purgeFunction()
Definition: ValueEnumerator.cpp:1145
llvm::ValueEnumerator::getFunctionConstantRange
void getFunctionConstantRange(unsigned &Start, unsigned &End) const
getFunctionConstantRange - Return the range of values that corresponds to function-local constants.
Definition: ValueEnumerator.h:192
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
llvm::ValueEnumerator::TypeList
std::vector< Type * > TypeList
Definition: ValueEnumerator.h:45
llvm::AttributeList::isEmpty
bool isEmpty() const
Return true if there are no attributes.
Definition: Attributes.h:892
llvm::ValueEnumerator::getComdats
const ComdatSetType & getComdats() const
Definition: ValueEnumerator.h:224
llvm::codeview::PublicSymFlags::Function
@ Function
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37