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