1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
|
//===- bolt/Core/CallGraph.cpp ------------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This file implements the CallGraph class.
//
//===----------------------------------------------------------------------===//
#include "bolt/Core/CallGraph.h"
#define DEBUG_TYPE "callgraph"
#if defined(__x86_64__) && !defined(_MSC_VER)
#if (!defined USE_SSECRC)
#define USE_SSECRC
#endif
#else
#undef USE_SSECRC
#endif
static LLVM_ATTRIBUTE_UNUSED inline size_t hash_int64_fallback(int64_t k) {
uint64_t key = (unsigned long long)k;
// "64 bit Mix Functions", from Thomas Wang's "Integer Hash Function."
// http://www.concentric.net/~ttwang/tech/inthash.htm
key = (~key) + (key << 21); // key = (key << 21) - key - 1;
key = key ^ (key >> 24);
key = (key + (key << 3)) + (key << 8); // key * 265
key = key ^ (key >> 14);
key = (key + (key << 2)) + (key << 4); // key * 21
key = key ^ (key >> 28);
return static_cast<size_t>(static_cast<uint32_t>(key));
}
static LLVM_ATTRIBUTE_UNUSED inline size_t hash_int64(int64_t k) {
#if defined(USE_SSECRC) && defined(__SSE4_2__)
size_t h = 0;
__asm("crc32q %1, %0\n" : "+r"(h) : "rm"(k));
return h;
#else
return hash_int64_fallback(k);
#endif
}
static inline size_t hash_int64_pair(int64_t k1, int64_t k2) {
#if defined(USE_SSECRC) && defined(__SSE4_2__)
// crc32 is commutative, so we need to perturb k1 so that (k1, k2) hashes
// differently from (k2, k1).
k1 += k1;
__asm("crc32q %1, %0\n" : "+r"(k1) : "rm"(k2));
return k1;
#else
return (hash_int64(k1) << 1) ^ hash_int64(k2);
#endif
}
namespace llvm {
namespace bolt {
int64_t CallGraph::Arc::Hash::operator()(const Arc &Arc) const {
#ifdef USE_STD_HASH
std::hash<int64_t> Hasher;
return hashCombine(Hasher(Arc.src()), Arc.dst());
#else
return hash_int64_pair(int64_t(Arc.src()), int64_t(Arc.dst()));
#endif
}
CallGraph::NodeId CallGraph::addNode(uint32_t Size, uint64_t Samples) {
NodeId Id = Nodes.size();
Nodes.emplace_back(Size, Samples);
return Id;
}
const CallGraph::Arc &CallGraph::incArcWeight(NodeId Src, NodeId Dst, double W,
double Offset) {
assert(Offset <= size(Src) && "Call offset exceeds function size");
std::pair<ArcIterator, bool> Res = Arcs.emplace(Src, Dst, W);
if (!Res.second) {
Res.first->Weight += W;
Res.first->AvgCallOffset += Offset * W;
return *Res.first;
}
Res.first->AvgCallOffset = Offset * W;
Nodes[Src].Succs.push_back(Dst);
Nodes[Dst].Preds.push_back(Src);
return *Res.first;
}
void CallGraph::normalizeArcWeights() {
for (NodeId FuncId = 0; FuncId < numNodes(); ++FuncId) {
const Node &Func = getNode(FuncId);
for (NodeId Caller : Func.predecessors()) {
ArcIterator Arc = findArc(Caller, FuncId);
Arc->NormalizedWeight = Arc->weight() / Func.samples();
if (Arc->weight() > 0)
Arc->AvgCallOffset /= Arc->weight();
assert(Arc->AvgCallOffset <= size(Caller) &&
"Avg call offset exceeds function size");
}
}
}
void CallGraph::adjustArcWeights() {
for (NodeId FuncId = 0; FuncId < numNodes(); ++FuncId) {
const Node &Func = getNode(FuncId);
uint64_t InWeight = 0;
for (NodeId Caller : Func.predecessors()) {
ArcIterator Arc = findArc(Caller, FuncId);
InWeight += (uint64_t)Arc->weight();
}
if (Func.samples() < InWeight)
setSamples(FuncId, InWeight);
}
}
} // namespace bolt
} // namespace llvm
|
