306 lines · c
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-exception6//7//===----------------------------------------------------------------------===//8//9// This class gives values and types Unique ID's.10//11//===----------------------------------------------------------------------===//12 13#ifndef LLVM_LIB_BITCODE_WRITER_VALUEENUMERATOR_H14#define LLVM_LIB_BITCODE_WRITER_VALUEENUMERATOR_H15 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 26namespace llvm {27 28class BasicBlock;29class Comdat;30class DIArgList;31class Function;32class Instruction;33class LocalAsMetadata;34class MDNode;35class Metadata;36class Module;37class NamedMDNode;38class raw_ostream;39class Type;40class Value;41class ValueSymbolTable;42 43class ValueEnumerator {44public: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 they51 /// include the AttributeList index, so we have to track that in our map.52 using IndexAndAttrSet = std::pair<unsigned, AttributeSet>;53 54 UseListOrderStack UseListOrders;55 56private:57 using TypeMapType = DenseMap<Type *, unsigned>;58 TypeMapType TypeMap;59 TypeList Types;60 61 using ValueMapType = DenseMap<const Value *, unsigned>;62 ValueMapType ValueMap;63 ValueList Values;64 65 using ComdatSetType = UniqueVector<const Comdat *>;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 by117 /// 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 currently125 /// 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 list129 /// before incorporation.130 unsigned NumModuleValues;131 132 /// When a function is incorporated, this is the size of the Metadatas list133 /// before incorporation.134 unsigned NumModuleMDs = 0;135 unsigned NumMDStrings = 0;136 137 unsigned FirstFuncConstantID;138 unsigned FirstInstID;139 140public: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 to191 /// 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.203 ArrayRef<const Metadata *> getMDStrings() const {204 return ArrayRef(MDs).slice(NumModuleMDs, NumMDStrings);205 }206 207 /// Get the non-MDString metadata for this block.208 ArrayRef<const Metadata *> getNonMDStrings() const {209 return ArrayRef(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 the228 /// specified basic block. This is relatively expensive information, so it229 /// 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();237 uint64_t computeBitsRequiredForTypeIndices() const;238 239private: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 MDString245 /// 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 the254 /// 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 its260 /// function tag. If not, call \a dropFunctionFromMetadata().261 ///262 /// Otherwise, mark \c MD as visited. Assign it an ID, or just return it if263 /// 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 the271 /// cost of reading bitcode records, and so the primary consideration is that272 /// operands of uniqued nodes are resolved before the nodes are read. This273 /// avoids re-uniquing them on the context and factors away RAUW support.274 ///275 /// This algorithm guarantees that subgraphs of uniqued nodes are in276 /// post-order. Distinct subgraphs reachable only from a single uniqued node277 /// 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 of281 /// 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 llvm304 305#endif // LLVM_LIB_BITCODE_WRITER_VALUEENUMERATOR_H306