contrib/llvm/lib/Bitcode/Writer/ValueEnumerator.h

   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;
  74     explicit MDIndex(unsigned F) : F(F) {}
  75
  76     /// Check if this has a function tag, and it's different from NewF.
  77     bool hasDifferentFunction(unsigned NewF) const { return F && F != NewF; }
  78
  79     /// Fetch the MD this references out of the given metadata array.
  80     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() {}
  99     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;
 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   }
 153   unsigned getMetadataOrNullID(const Metadata *MD) const {
 154     return MetadataMap.lookup(MD).ID;
 155   }
 156   unsigned numMDs() const { return MDs.size(); }
 157
 158   bool shouldPreserveUseListOrder() const { return ShouldPreserveUseListOrder; }
 159
 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
 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
 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.
 185   void getFunctionConstantRange(unsigned &Start, unsigned &End) const {
 186     Start = FirstFuncConstantID;
 187     End = FirstInstID;
 188   }
 189
 190   const ValueList &getValues() const { return Values; }
 191
 192   /// Check whether the current block has any metadata to emit.
 193   bool hasMDs() const { return NumModuleMDs < MDs.size(); }
 194
 195   /// Get the MDString metadata for this block.
 196   ArrayRef<const Metadata *> getMDStrings() const {
 197     return makeArrayRef(MDs).slice(NumModuleMDs, NumMDStrings);
 198   }
 199
 200   /// Get the non-MDString metadata for this block.
 201   ArrayRef<const Metadata *> getNonMDStrings() const {
 202     return makeArrayRef(MDs).slice(NumModuleMDs).slice(NumMDStrings);
 203   }
 204
 205   const TypeList &getTypes() const { return Types; }
 206   const std::vector<const BasicBlock*> &getBasicBlocks() const {
 207     return BasicBlocks;
 208   }
 209   const std::vector<AttributeSet> &getAttributes() const {
 210     return Attribute;
 211   }
 212   const std::vector<AttributeSet> &getAttributeGroups() const {
 213     return AttributeGroups;
 214   }
 215
 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