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
hash_int64_fallback(int64_t k)25 static 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
hash_int64(int64_t k)38 static 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
hash_int64_pair(int64_t k1,int64_t k2)48 static 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(k1) << 1) ^ hash_int64(k2);
57 #endif
58 }
59
60 namespace llvm {
61 namespace bolt {
62
operator ()(const Arc & Arc) const63 int64_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(int64_t(Arc.src()), int64_t(Arc.dst()));
69 #endif
70 }
71
addNode(uint32_t Size,uint64_t Samples)72 CallGraph::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
incArcWeight(NodeId Src,NodeId Dst,double W,double Offset)78 const 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
normalizeArcWeights()94 void 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
adjustArcWeights()108 void 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 bolt
122 } // namespace llvm
123