chromium/v8/src/snapshot/sort-builtins.h

// Copyright 2023 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef V8_SNAPSHOT_SORT_BUILTINS_H_
#define V8_SNAPSHOT_SORT_BUILTINS_H_

#include <unordered_map>
#include <vector>

#include "src/builtins/builtins.h"
#include "src/diagnostics/basic-block-profiler.h"

// The inputs were the builtin size, call graph and basic block execution count.
// There are 3 steps in this sorting algorithm:
// 1. Initializing cluster and sorting:
//  A cluster represents a group of functions. At the beginning, each
//  function was in an individual cluster, and we sort these clusters
//  by their density (which means how much probabilities this function was
//  invoked).
//
// 2. Merge the best predecessor:
//  After step 1, we will get lots of clusters which may contain only
//  one function. According to this order, we iterate each function
//  and merge cluster with some conditions, like:
//   1) The most incoming probability.
//   2) Incoming probability must be bigger than a threshold, like 0.1
//   3) Merged cluster size couldn't be bigger than a threshold, like 1 mb.
//   4) Predecessor cluster density couldn't be bigger N times than the new
//   merged cluster, N is 8 now.
//
// 3. Sorting clusters:
//  After step 2, we obtain lots of clusters which comprise several functions.
//  We will finally sort these clusters by their density.

namespace v8 {
namespace internal {

class Cluster;
struct CallProbability { … };
// The key is the callee builtin, the value is call probabilities in percent
// (mostly range in 0 ~ 100, except one call happend in a loop block which was
// executed more times than block 0 of this builtin).
using CallProbabilities = std::unordered_map<Builtin, CallProbability>;
// The key is the caller builtin.
using CallGraph = std::unordered_map<Builtin, CallProbabilities>;
// The key is the builtin id, the value is density of builtin (range in 0 ~
// 10000).
using BuiltinDensityMap = std::unordered_map<Builtin, uint32_t>;
// The index is the builtin id, the value is size of builtin (in bytes).
using BuiltinSize = std::vector<uint32_t>;
// The key is the builtin id, the value is the cluster which it was comprised.
using BuiltinClusterMap = std::unordered_map<Builtin, Cluster*>;

class BuiltinsSorter { … };

class Cluster { … };

}  // namespace internal

}  // namespace v8

#endif  // V8_SNAPSHOT_SORT_BUILTINS_H_