lib/Bitcode/Writer/ValueEnumerator.h

   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;
  78     explicit MDIndex(unsigned F) : F(F) {}
  79
  80     /// Check if this has a function tag, and it's different from NewF.
  81     bool hasDifferentFunction(unsigned NewF) const { return F && F != NewF; }
  82
  83     /// Fetch the MD this references out of the given metadata array.
  84     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;
 103     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
 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
 159   unsigned getMetadataOrNullID(const Metadata *MD) const {
 160     return MetadataMap.lookup(MD).ID;
 161   }
 162
 163   unsigned numMDs() const { return MDs.size(); }
 164
 165   bool shouldPreserveUseListOrder() const { return ShouldPreserveUseListOrder; }
 166
 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
 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
 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.
 193   void getFunctionConstantRange(unsigned &Start, unsigned &End) const {
 194     Start = FirstFuncConstantID;
 195     End = FirstInstID;
 196   }
 197
 198   const ValueList &getValues() const { return Values; }
 199
 200   /// Check whether the current block has any metadata to emit.
 201   bool hasMDs() const { return NumModuleMDs < MDs.size(); }
 202
 203   /// Get the MDString metadata for this block.
 204   ArrayRef<const Metadata *> getMDStrings() const {
 205     return makeArrayRef(MDs).slice(NumModuleMDs, NumMDStrings);
 206   }
 207
 208   /// Get the non-MDString metadata for this block.
 209   ArrayRef<const Metadata *> getNonMDStrings() const {
 210     return makeArrayRef(MDs).slice(NumModuleMDs).slice(NumMDStrings);
 211   }
 212
 213   const TypeList &getTypes() const { return Types; }
 214
 215   const std::vector<const BasicBlock*> &getBasicBlocks() const {
 216     return BasicBlocks;
 217   }
 218
 219   const std::vector<AttributeList> &getAttributeLists() const { return AttributeLists; }
 220
 221   const std::vector<IndexAndAttrSet> &getAttributeGroups() const {
 222     return AttributeGroups;
 223   }
 224
 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