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/Metadata.h" 21 #include "llvm/IR/Type.h" 22 #include "llvm/IR/UseListOrder.h" 23 #include <cassert> 24 #include <cstdint> 25 #include <utility> 26 #include <vector> 27 28 namespace llvm { 29 30 class BasicBlock; 31 class Comdat; 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 class ValueEnumerator { 45 public: 46 using TypeList = std::vector<Type *>; 47 48 // For each value, we remember its Value* and occurrence frequency. 49 using ValueList = std::vector<std::pair<const Value *, unsigned>>; 50 51 /// Attribute groups as encoded in bitcode are almost AttributeSets, but they 52 /// include the AttributeList index, so we have to track that in our map. 53 using IndexAndAttrSet = std::pair<unsigned, AttributeSet>; 54 55 UseListOrderStack UseListOrders; 56 57 private: 58 using TypeMapType = DenseMap<Type *, unsigned>; 59 TypeMapType TypeMap; 60 TypeList Types; 61 62 using ValueMapType = DenseMap<const Value *, unsigned>; 63 ValueMapType ValueMap; 64 ValueList Values; 65 66 using ComdatSetType = UniqueVector<const Comdat *>; 67 ComdatSetType Comdats; 68 69 std::vector<const Metadata *> MDs; 70 std::vector<const Metadata *> FunctionMDs; 71 72 /// Index of information about a piece of metadata. 73 struct MDIndex { 74 unsigned F = 0; ///< The ID of the function for this metadata, if any. 75 unsigned ID = 0; ///< The implicit ID of this metadata in bitcode. 76 77 MDIndex() = default; MDIndexMDIndex78 explicit MDIndex(unsigned F) : F(F) {} 79 80 /// Check if this has a function tag, and it's different from NewF. hasDifferentFunctionMDIndex81 bool hasDifferentFunction(unsigned NewF) const { return F && F != NewF; } 82 83 /// Fetch the MD this references out of the given metadata array. getMDIndex84 const Metadata *get(ArrayRef<const Metadata *> MDs) const { 85 assert(ID && "Expected non-zero ID"); 86 assert(ID <= MDs.size() && "Expected valid ID"); 87 return MDs[ID - 1]; 88 } 89 }; 90 91 using MetadataMapType = DenseMap<const Metadata *, MDIndex>; 92 MetadataMapType MetadataMap; 93 94 /// Range of metadata IDs, as a half-open range. 95 struct MDRange { 96 unsigned First = 0; 97 unsigned Last = 0; 98 99 /// Number of strings in the prefix of the metadata range. 100 unsigned NumStrings = 0; 101 102 MDRange() = default; MDRangeMDRange103 explicit MDRange(unsigned First) : First(First) {} 104 }; 105 SmallDenseMap<unsigned, MDRange, 1> FunctionMDInfo; 106 107 bool ShouldPreserveUseListOrder; 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, bool ShouldPreserveUseListOrder); 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 getMetadataID(const Metadata * MD)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 getMetadataOrNullID(const Metadata * MD)159 unsigned getMetadataOrNullID(const Metadata *MD) const { 160 return MetadataMap.lookup(MD).ID; 161 } 162 numMDs()163 unsigned numMDs() const { return MDs.size(); } 164 shouldPreserveUseListOrder()165 bool shouldPreserveUseListOrder() const { return ShouldPreserveUseListOrder; } 166 getTypeID(Type * T)167 unsigned getTypeID(Type *T) const { 168 TypeMapType::const_iterator I = TypeMap.find(T); 169 assert(I != TypeMap.end() && "Type not in ValueEnumerator!"); 170 return I->second-1; 171 } 172 173 unsigned getInstructionID(const Instruction *I) const; 174 void setInstructionID(const Instruction *I); 175 getAttributeListID(AttributeList PAL)176 unsigned getAttributeListID(AttributeList PAL) const { 177 if (PAL.isEmpty()) return 0; // Null maps to zero. 178 AttributeListMapType::const_iterator I = AttributeListMap.find(PAL); 179 assert(I != AttributeListMap.end() && "Attribute not in ValueEnumerator!"); 180 return I->second; 181 } 182 getAttributeGroupID(IndexAndAttrSet Group)183 unsigned getAttributeGroupID(IndexAndAttrSet Group) const { 184 if (!Group.second.hasAttributes()) 185 return 0; // Null maps to zero. 186 AttributeGroupMapType::const_iterator I = AttributeGroupMap.find(Group); 187 assert(I != AttributeGroupMap.end() && "Attribute not in ValueEnumerator!"); 188 return I->second; 189 } 190 191 /// getFunctionConstantRange - Return the range of values that corresponds to 192 /// function-local constants. getFunctionConstantRange(unsigned & Start,unsigned & End)193 void getFunctionConstantRange(unsigned &Start, unsigned &End) const { 194 Start = FirstFuncConstantID; 195 End = FirstInstID; 196 } 197 getValues()198 const ValueList &getValues() const { return Values; } 199 200 /// Check whether the current block has any metadata to emit. hasMDs()201 bool hasMDs() const { return NumModuleMDs < MDs.size(); } 202 203 /// Get the MDString metadata for this block. getMDStrings()204 ArrayRef<const Metadata *> getMDStrings() const { 205 return makeArrayRef(MDs).slice(NumModuleMDs, NumMDStrings); 206 } 207 208 /// Get the non-MDString metadata for this block. getNonMDStrings()209 ArrayRef<const Metadata *> getNonMDStrings() const { 210 return makeArrayRef(MDs).slice(NumModuleMDs).slice(NumMDStrings); 211 } 212 getTypes()213 const TypeList &getTypes() const { return Types; } 214 getBasicBlocks()215 const std::vector<const BasicBlock*> &getBasicBlocks() const { 216 return BasicBlocks; 217 } 218 getAttributeLists()219 const std::vector<AttributeList> &getAttributeLists() const { return AttributeLists; } 220 getAttributeGroups()221 const std::vector<IndexAndAttrSet> &getAttributeGroups() const { 222 return AttributeGroups; 223 } 224 getComdats()225 const ComdatSetType &getComdats() const { return Comdats; } 226 unsigned getComdatID(const Comdat *C) const; 227 228 /// getGlobalBasicBlockID - This returns the function-specific ID for the 229 /// specified basic block. This is relatively expensive information, so it 230 /// should only be used by rare constructs such as address-of-label. 231 unsigned getGlobalBasicBlockID(const BasicBlock *BB) const; 232 233 /// incorporateFunction/purgeFunction - If you'd like to deal with a function, 234 /// use these two methods to get its data into the ValueEnumerator! 235 void incorporateFunction(const Function &F); 236 237 void purgeFunction(); 238 uint64_t computeBitsRequiredForTypeIndicies() const; 239 240 private: 241 void OptimizeConstants(unsigned CstStart, unsigned CstEnd); 242 243 /// Reorder the reachable metadata. 244 /// 245 /// This is not just an optimization, but is mandatory for emitting MDString 246 /// correctly. 247 void organizeMetadata(); 248 249 /// Drop the function tag from the transitive operands of the given node. 250 void dropFunctionFromMetadata(MetadataMapType::value_type &FirstMD); 251 252 /// Incorporate the function metadata. 253 /// 254 /// This should be called before enumerating LocalAsMetadata for the 255 /// function. 256 void incorporateFunctionMetadata(const Function &F); 257 258 /// Enumerate a single instance of metadata with the given function tag. 259 /// 260 /// If \c MD has already been enumerated, check that \c F matches its 261 /// function tag. If not, call \a dropFunctionFromMetadata(). 262 /// 263 /// Otherwise, mark \c MD as visited. Assign it an ID, or just return it if 264 /// it's an \a MDNode. 265 const MDNode *enumerateMetadataImpl(unsigned F, const Metadata *MD); 266 267 unsigned getMetadataFunctionID(const Function *F) const; 268 269 /// Enumerate reachable metadata in (almost) post-order. 270 /// 271 /// Enumerate all the metadata reachable from MD. We want to minimize the 272 /// cost of reading bitcode records, and so the primary consideration is that 273 /// operands of uniqued nodes are resolved before the nodes are read. This 274 /// avoids re-uniquing them on the context and factors away RAUW support. 275 /// 276 /// This algorithm guarantees that subgraphs of uniqued nodes are in 277 /// post-order. Distinct subgraphs reachable only from a single uniqued node 278 /// will be in post-order. 279 /// 280 /// \note The relative order of a distinct and uniqued node is irrelevant. 281 /// \a organizeMetadata() will later partition distinct nodes ahead of 282 /// uniqued ones. 283 ///{ 284 void EnumerateMetadata(const Function *F, const Metadata *MD); 285 void EnumerateMetadata(unsigned F, const Metadata *MD); 286 ///} 287 288 void EnumerateFunctionLocalMetadata(const Function &F, 289 const LocalAsMetadata *Local); 290 void EnumerateFunctionLocalMetadata(unsigned F, const LocalAsMetadata *Local); 291 void EnumerateNamedMDNode(const NamedMDNode *NMD); 292 void EnumerateValue(const Value *V); 293 void EnumerateType(Type *T); 294 void EnumerateOperandType(const Value *V); 295 void EnumerateAttributes(AttributeList PAL); 296 297 void EnumerateValueSymbolTable(const ValueSymbolTable &ST); 298 void EnumerateNamedMetadata(const Module &M); 299 }; 300 301 } // end namespace llvm 302 303 #endif // LLVM_LIB_BITCODE_WRITER_VALUEENUMERATOR_H 304