123 lines · cpp
1//===- bolt/Core/CallGraph.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 file implements the CallGraph class.10//11//===----------------------------------------------------------------------===//12 13#include "bolt/Core/CallGraph.h"14 15#define DEBUG_TYPE "callgraph"16 17#if defined(__x86_64__) && !defined(_MSC_VER)18#if (!defined USE_SSECRC)19#define USE_SSECRC20#endif21#else22#undef USE_SSECRC23#endif24 25[[maybe_unused]] static inline size_t hash_int64_fallback(int64_t k) {26 uint64_t key = (unsigned long long)k;27 // "64 bit Mix Functions", from Thomas Wang's "Integer Hash Function."28 // http://www.concentric.net/~ttwang/tech/inthash.htm29 key = (~key) + (key << 21); // key = (key << 21) - key - 1;30 key = key ^ (key >> 24);31 key = (key + (key << 3)) + (key << 8); // key * 26532 key = key ^ (key >> 14);33 key = (key + (key << 2)) + (key << 4); // key * 2134 key = key ^ (key >> 28);35 return static_cast<size_t>(static_cast<uint32_t>(key));36}37 38[[maybe_unused]] static inline size_t hash_int64(int64_t k) {39#if defined(USE_SSECRC) && defined(__SSE4_2__)40 size_t h = 0;41 __asm("crc32q %1, %0\n" : "+r"(h) : "rm"(k));42 return h;43#else44 return hash_int64_fallback(k);45#endif46}47 48static inline size_t hash_int64_pair(int64_t k1, int64_t k2) {49#if defined(USE_SSECRC) && defined(__SSE4_2__)50 // crc32 is commutative, so we need to perturb k1 so that (k1, k2) hashes51 // differently from (k2, k1).52 k1 += k1;53 __asm("crc32q %1, %0\n" : "+r"(k1) : "rm"(k2));54 return k1;55#else56 return (hash_int64(k1) << 1) ^ hash_int64(k2);57#endif58}59 60namespace llvm {61namespace bolt {62 63int64_t CallGraph::Arc::Hash::operator()(const Arc &Arc) const {64#ifdef USE_STD_HASH65 std::hash<int64_t> Hasher;66 return hashCombine(Hasher(Arc.src()), Arc.dst());67#else68 return hash_int64_pair(int64_t(Arc.src()), int64_t(Arc.dst()));69#endif70}71 72CallGraph::NodeId CallGraph::addNode(uint32_t Size, uint64_t Samples) {73 NodeId Id = Nodes.size();74 Nodes.emplace_back(Size, Samples);75 return Id;76}77 78const CallGraph::Arc &CallGraph::incArcWeight(NodeId Src, NodeId Dst, double W,79 double Offset) {80 assert(Offset <= size(Src) && "Call offset exceeds function size");81 82 std::pair<ArcIterator, bool> Res = Arcs.emplace(Src, Dst, W);83 if (!Res.second) {84 Res.first->Weight += W;85 Res.first->AvgCallOffset += Offset * W;86 return *Res.first;87 }88 Res.first->AvgCallOffset = Offset * W;89 Nodes[Src].Succs.push_back(Dst);90 Nodes[Dst].Preds.push_back(Src);91 return *Res.first;92}93 94void CallGraph::normalizeArcWeights() {95 for (NodeId FuncId = 0; FuncId < numNodes(); ++FuncId) {96 const Node &Func = getNode(FuncId);97 for (NodeId Caller : Func.predecessors()) {98 ArcIterator Arc = findArc(Caller, FuncId);99 Arc->NormalizedWeight = Arc->weight() / Func.samples();100 if (Arc->weight() > 0)101 Arc->AvgCallOffset /= Arc->weight();102 assert(Arc->AvgCallOffset <= size(Caller) &&103 "Avg call offset exceeds function size");104 }105 }106}107 108void CallGraph::adjustArcWeights() {109 for (NodeId FuncId = 0; FuncId < numNodes(); ++FuncId) {110 const Node &Func = getNode(FuncId);111 uint64_t InWeight = 0;112 for (NodeId Caller : Func.predecessors()) {113 ArcIterator Arc = findArc(Caller, FuncId);114 InWeight += (uint64_t)Arc->weight();115 }116 if (Func.samples() < InWeight)117 setSamples(FuncId, InWeight);118 }119}120 121} // namespace bolt122} // namespace llvm123