xref: /llvm-project/bolt/lib/Core/CallGraph.cpp (revision 2430a354bfb9e8c08e0dd5f294012b40afb75ce0)

//===- 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