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