bolt/lib/Core/CallGraph.cpp

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