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 
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 
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 
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 
67 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 
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 
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 
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 
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