llvm/lib/CGData/OutlinedHashTreeRecord.cpp

   1 //===-- OutlinedHashTreeRecord.cpp ----------------------------------------===//
   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 defines the OutlinedHashTreeRecord class. This class holds the outlined
  10 // hash tree for both serialization and deserialization processes. It utilizes
  11 // two data formats for serialization: raw binary data and YAML.
  12 // These two formats can be used interchangeably.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #include "llvm/CGData/OutlinedHashTreeRecord.h"
  17 #include "llvm/ObjectYAML/YAML.h"
  18 #include "llvm/Support/Endian.h"
  19 #include "llvm/Support/EndianStream.h"
  20
  21 #define DEBUG_TYPE "outlined-hash-tree"
  22
  23 using namespace llvm;
  24 using namespace llvm::support;
  25
  26 namespace llvm {
  27 namespace yaml {
  28
  29 template <> struct MappingTraits<HashNodeStable> {
  30   static void mapping(IO &io, HashNodeStable &res) {
  31     io.mapRequired("Hash", res.Hash);
  32     io.mapRequired("Terminals", res.Terminals);
  33     io.mapRequired("SuccessorIds", res.SuccessorIds);
  34   }
  35 };
  36
  37 template <> struct CustomMappingTraits<IdHashNodeStableMapTy> {
  38   static void inputOne(IO &io, StringRef Key, IdHashNodeStableMapTy &V) {
  39     HashNodeStable NodeStable;
  40     io.mapRequired(Key.str().c_str(), NodeStable);
  41     unsigned Id;
  42     if (Key.getAsInteger(0, Id)) {
  43       io.setError("Id not an integer");
  44       return;
  45     }
  46     V.insert({Id, NodeStable});
  47   }
  48
  49   static void output(IO &io, IdHashNodeStableMapTy &V) {
  50     for (auto Iter = V.begin(); Iter != V.end(); ++Iter)
  51       io.mapRequired(utostr(Iter->first).c_str(), Iter->second);
  52   }
  53 };
  54
  55 } // namespace yaml
  56 } // namespace llvm
  57
  58 void OutlinedHashTreeRecord::serialize(raw_ostream &OS) const {
  59   IdHashNodeStableMapTy IdNodeStableMap;
  60   convertToStableData(IdNodeStableMap);
  61   support::endian::Writer Writer(OS, endianness::little);
  62   Writer.write<uint32_t>(IdNodeStableMap.size());
  63
  64   for (const auto &[Id, NodeStable] : IdNodeStableMap) {
  65     Writer.write<uint32_t>(Id);
  66     Writer.write<uint64_t>(NodeStable.Hash);
  67     Writer.write<uint32_t>(NodeStable.Terminals);
  68     Writer.write<uint32_t>(NodeStable.SuccessorIds.size());
  69     for (auto SuccessorId : NodeStable.SuccessorIds)
  70       Writer.write<uint32_t>(SuccessorId);
  71   }
  72 }
  73
  74 void OutlinedHashTreeRecord::deserialize(const unsigned char *&Ptr) {
  75   IdHashNodeStableMapTy IdNodeStableMap;
  76   auto NumIdNodeStableMap =
  77       endian::readNext<uint32_t, endianness::little, unaligned>(Ptr);
  78
  79   for (unsigned I = 0; I < NumIdNodeStableMap; ++I) {
  80     auto Id = endian::readNext<uint32_t, endianness::little, unaligned>(Ptr);
  81     HashNodeStable NodeStable;
  82     NodeStable.Hash =
  83         endian::readNext<uint64_t, endianness::little, unaligned>(Ptr);
  84     NodeStable.Terminals =
  85         endian::readNext<uint32_t, endianness::little, unaligned>(Ptr);
  86     auto NumSuccessorIds =
  87         endian::readNext<uint32_t, endianness::little, unaligned>(Ptr);
  88     for (unsigned J = 0; J < NumSuccessorIds; ++J)
  89       NodeStable.SuccessorIds.push_back(
  90           endian::readNext<uint32_t, endianness::little, unaligned>(Ptr));
  91
  92     IdNodeStableMap[Id] = std::move(NodeStable);
  93   }
  94
  95   convertFromStableData(IdNodeStableMap);
  96 }
  97
  98 void OutlinedHashTreeRecord::serializeYAML(yaml::Output &YOS) const {
  99   IdHashNodeStableMapTy IdNodeStableMap;
 100   convertToStableData(IdNodeStableMap);
 101
 102   YOS << IdNodeStableMap;
 103 }
 104
 105 void OutlinedHashTreeRecord::deserializeYAML(yaml::Input &YIS) {
 106   IdHashNodeStableMapTy IdNodeStableMap;
 107
 108   YIS >> IdNodeStableMap;
 109   YIS.nextDocument();
 110
 111   convertFromStableData(IdNodeStableMap);
 112 }
 113
 114 void OutlinedHashTreeRecord::convertToStableData(
 115     IdHashNodeStableMapTy &IdNodeStableMap) const {
 116   // Build NodeIdMap
 117   HashNodeIdMapTy NodeIdMap;
 118   HashTree->walkGraph(
 119       [&NodeIdMap](const HashNode *Current) {
 120         size_t Index = NodeIdMap.size();
 121         NodeIdMap[Current] = Index;
 122         assert((Index + 1 == NodeIdMap.size()) &&
 123                "Duplicate key in NodeIdMap: 'Current' should be unique.");
 124       },
 125       /*EdgeCallbackFn=*/nullptr, /*SortedWork=*/true);
 126
 127   // Convert NodeIdMap to NodeStableMap
 128   for (auto &P : NodeIdMap) {
 129     auto *Node = P.first;
 130     auto Id = P.second;
 131     HashNodeStable NodeStable;
 132     NodeStable.Hash = Node->Hash;
 133     NodeStable.Terminals = Node->Terminals.value_or(0);
 134     for (auto &P : Node->Successors)
 135       NodeStable.SuccessorIds.push_back(NodeIdMap[P.second.get()]);
 136     IdNodeStableMap[Id] = NodeStable;
 137   }
 138
 139   // Sort the Successors so that they come out in the same order as in the map.
 140   for (auto &P : IdNodeStableMap)
 141     llvm::sort(P.second.SuccessorIds);
 142 }
 143
 144 void OutlinedHashTreeRecord::convertFromStableData(
 145     const IdHashNodeStableMapTy &IdNodeStableMap) {
 146   IdHashNodeMapTy IdNodeMap;
 147   // Initialize the root node at 0.
 148   IdNodeMap[0] = HashTree->getRoot();
 149   assert(IdNodeMap[0]->Successors.empty());
 150
 151   for (auto &P : IdNodeStableMap) {
 152     auto Id = P.first;
 153     const HashNodeStable &NodeStable = P.second;
 154     assert(IdNodeMap.count(Id));
 155     HashNode *Curr = IdNodeMap[Id];
 156     Curr->Hash = NodeStable.Hash;
 157     if (NodeStable.Terminals)
 158       Curr->Terminals = NodeStable.Terminals;
 159     auto &Successors = Curr->Successors;
 160     assert(Successors.empty());
 161     for (auto SuccessorId : NodeStable.SuccessorIds) {
 162       auto Sucessor = std::make_unique<HashNode>();
 163       IdNodeMap[SuccessorId] = Sucessor.get();
 164       auto Hash = IdNodeStableMap.at(SuccessorId).Hash;
 165       Successors[Hash] = std::move(Sucessor);
 166     }
 167   }
 168 }