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-exception
6//
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_SSECRC
20#endif
21#else
22#undef USE_SSECRC
23#endif
24
25static LLVM_ATTRIBUTE_UNUSED 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.htm
29 key = (~key) + (key << 21); // key = (key << 21) - key - 1;
30 key = key ^ (key >> 24);
31 key = (key + (key << 3)) + (key << 8); // key * 265
32 key = key ^ (key >> 14);
33 key = (key + (key << 2)) + (key << 4); // key * 21
34 key = key ^ (key >> 28);
35 return static_cast<size_t>(static_cast<uint32_t>(key));
36}
37
38static LLVM_ATTRIBUTE_UNUSED 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#else
44 return hash_int64_fallback(k);
45#endif
46}
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) hashes
51 // differently from (k2, k1).
52 k1 += k1;
53 __asm("crc32q %1, %0\n" : "+r"(k1) : "rm"(k2));
54 return k1;
55#else
56 return (hash_int64(k: k1) << 1) ^ hash_int64(k: k2);
57#endif
58}
59
60namespace llvm {
61namespace bolt {
62
63int64_t CallGraph::Arc::Hash::operator()(const Arc &Arc) const {
64#ifdef USE_STD_HASH
65 std::hash<int64_t> Hasher;
66 return hashCombine(Hasher(Arc.src()), Arc.dst());
67#else
68 return hash_int64_pair(k1: int64_t(Arc.src()), k2: int64_t(Arc.dst()));
69#endif
70}
71
72CallGraph::NodeId CallGraph::addNode(uint32_t Size, uint64_t Samples) {
73 NodeId Id = Nodes.size();
74 Nodes.emplace_back(args&: Size, args&: 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(args&: Src, args&: Dst, args&: 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(x: Dst);
90 Nodes[Dst].Preds.push_back(x: Src);
91 return *Res.first;
92}
93
94void CallGraph::normalizeArcWeights() {
95 for (NodeId FuncId = 0; FuncId < numNodes(); ++FuncId) {
96 const Node &Func = getNode(Id: FuncId);
97 for (NodeId Caller : Func.predecessors()) {
98 ArcIterator Arc = findArc(Src: Caller, Dst: 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(Id: FuncId);
111 uint64_t InWeight = 0;
112 for (NodeId Caller : Func.predecessors()) {
113 ArcIterator Arc = findArc(Src: Caller, Dst: FuncId);
114 InWeight += (uint64_t)Arc->weight();
115 }
116 if (Func.samples() < InWeight)
117 setSamples(Id: FuncId, Samples: InWeight);
118 }
119}
120
121} // namespace bolt
122} // namespace llvm
123

source code of bolt/lib/Core/CallGraph.cpp