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/CodeGenData/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 ? *Node->Terminals : 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 } 169