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