169 lines · 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-exception6//7//===----------------------------------------------------------------------===//8//9// This defines the OutlinedHashTreeRecord class. This class holds the outlined10// hash tree for both serialization and deserialization processes. It utilizes11// 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 23using namespace llvm;24using namespace llvm::support;25 26namespace llvm {27namespace yaml {28 29template <> 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 37template <> struct CustomMappingTraits<IdHashNodeStableMapTy> {38 static void inputOne(IO &io, StringRef Key, IdHashNodeStableMapTy &V) {39 HashNodeStable NodeStable;40 io.mapRequired(Key, 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), Iter->second);52 }53};54 55} // namespace yaml56} // namespace llvm57 58void 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 74void 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 98void OutlinedHashTreeRecord::serializeYAML(yaml::Output &YOS) const {99 IdHashNodeStableMapTy IdNodeStableMap;100 convertToStableData(IdNodeStableMap);101 102 YOS << IdNodeStableMap;103}104 105void OutlinedHashTreeRecord::deserializeYAML(yaml::Input &YIS) {106 IdHashNodeStableMapTy IdNodeStableMap;107 108 YIS >> IdNodeStableMap;109 YIS.nextDocument();110 111 convertFromStableData(IdNodeStableMap);112}113 114void OutlinedHashTreeRecord::convertToStableData(115 IdHashNodeStableMapTy &IdNodeStableMap) const {116 // Build NodeIdMap117 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 NodeStableMap128 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 144void 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}169