SampleProfileInference.cpp | Explore in Territory

//===- SampleProfileInference.cpp - Adjust sample profiles in the IR ------===//
//
// 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 a profile inference algorithm. Given an incomplete and
// possibly imprecise block counts, the algorithm reconstructs realistic block
// and edge counts that satisfy flow conservation rules, while minimally modify
// input block counts.
//
//===----------------------------------------------------------------------===//

#include "llvm/Transforms/Utils/SampleProfileInference.h"
#include "llvm/ADT/BitVector.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include <queue>
#include <set>
#include <stack>
#include <unordered_set>

usingnamespacellvm;
#define DEBUG_TYPE …

namespace {

static cl::opt<bool> SampleProfileEvenFlowDistribution(
    "sample-profile-even-flow-distribution", cl::init(true), cl::Hidden,
    cl::desc("Try to evenly distribute flow when there are multiple equally "
             "likely options."));

static cl::opt<bool> SampleProfileRebalanceUnknown(
    "sample-profile-rebalance-unknown", cl::init(true), cl::Hidden,
    cl::desc("Evenly re-distribute flow among unknown subgraphs."));

static cl::opt<bool> SampleProfileJoinIslands(
    "sample-profile-join-islands", cl::init(true), cl::Hidden,
    cl::desc("Join isolated components having positive flow."));

static cl::opt<unsigned> SampleProfileProfiCostBlockInc(
    "sample-profile-profi-cost-block-inc", cl::init(10), cl::Hidden,
    cl::desc("The cost of increasing a block's count by one."));

static cl::opt<unsigned> SampleProfileProfiCostBlockDec(
    "sample-profile-profi-cost-block-dec", cl::init(20), cl::Hidden,
    cl::desc("The cost of decreasing a block's count by one."));

static cl::opt<unsigned> SampleProfileProfiCostBlockEntryInc(
    "sample-profile-profi-cost-block-entry-inc", cl::init(40), cl::Hidden,
    cl::desc("The cost of increasing the entry block's count by one."));

static cl::opt<unsigned> SampleProfileProfiCostBlockEntryDec(
    "sample-profile-profi-cost-block-entry-dec", cl::init(10), cl::Hidden,
    cl::desc("The cost of decreasing the entry block's count by one."));

static cl::opt<unsigned> SampleProfileProfiCostBlockZeroInc(
    "sample-profile-profi-cost-block-zero-inc", cl::init(11), cl::Hidden,
    cl::desc("The cost of increasing a count of zero-weight block by one."));

static cl::opt<unsigned> SampleProfileProfiCostBlockUnknownInc(
    "sample-profile-profi-cost-block-unknown-inc", cl::init(0), cl::Hidden,
    cl::desc("The cost of increasing an unknown block's count by one."));

/// A value indicating an infinite flow/capacity/weight of a block/edge.
/// Not using numeric_limits<int64_t>::max(), as the values can be summed up
/// during the execution.
static constexpr int64_t INF = …;

/// The minimum-cost maximum flow algorithm.
///
/// The algorithm finds the maximum flow of minimum cost on a given (directed)
/// network using a modified version of the classical Moore-Bellman-Ford
/// approach. The algorithm applies a number of augmentation iterations in which
/// flow is sent along paths of positive capacity from the source to the sink.
/// The worst-case time complexity of the implementation is O(v(f)*m*n), where
/// where m is the number of edges, n is the number of vertices, and v(f) is the
/// value of the maximum flow. However, the observed running time on typical
/// instances is sub-quadratic, that is, o(n^2).
///
/// The input is a set of edges with specified costs and capacities, and a pair
/// of nodes (source and sink). The output is the flow along each edge of the
/// minimum total cost respecting the given edge capacities.
class MinCostMaxFlow { … };

/// A post-processing adjustment of the control flow. It applies two steps by
/// rerouting some flow and making it more realistic:
///
/// - First, it removes all isolated components ("islands") with a positive flow
///   that are unreachable from the entry block. For every such component, we
///   find the shortest from the entry to an exit passing through the component,
///   and increase the flow by one unit along the path.
///
/// - Second, it identifies all "unknown subgraphs" consisting of basic blocks
///   with no sampled counts. Then it rebalnces the flow that goes through such
///   a subgraph so that each branch is taken with probability 50%.
///   An unknown subgraph is such that for every two nodes u and v:
///     - u dominates v and u is not unknown;
///     - v post-dominates u; and
///     - all inner-nodes of all (u,v)-paths are unknown.
///
class FlowAdjuster { … };

std::pair<int64_t, int64_t> assignBlockCosts(const ProfiParams &Params,
                                             const FlowBlock &Block);
std::pair<int64_t, int64_t> assignJumpCosts(const ProfiParams &Params,
                                            const FlowJump &Jump);

/// Initializing flow network for a given function.
///
/// Every block is split into two nodes that are responsible for (i) an
/// incoming flow, (ii) an outgoing flow; they penalize an increase or a
/// reduction of the block weight.
void initializeNetwork(const ProfiParams &Params, MinCostMaxFlow &Network,
                       FlowFunction &Func) { … }

/// Assign costs for increasing/decreasing the block counts.
std::pair<int64_t, int64_t> assignBlockCosts(const ProfiParams &Params,
                                             const FlowBlock &Block) { … }

/// Assign costs for increasing/decreasing the jump counts.
std::pair<int64_t, int64_t> assignJumpCosts(const ProfiParams &Params,
                                            const FlowJump &Jump) { … }

/// Extract resulting block and edge counts from the flow network.
void extractWeights(const ProfiParams &Params, MinCostMaxFlow &Network,
                    FlowFunction &Func) { … }

#ifndef NDEBUG
/// Verify that the provided block/jump weights are as expected.
void verifyInput(const FlowFunction &Func) {
  // Verify entry and exit blocks
  assert(Func.Entry == 0 && Func.Blocks[0].isEntry());
  size_t NumExitBlocks = 0;
  for (size_t I = 1; I < Func.Blocks.size(); I++) {
    assert(!Func.Blocks[I].isEntry() && "multiple entry blocks");
    if (Func.Blocks[I].isExit())
      NumExitBlocks++;
  }
  assert(NumExitBlocks > 0 && "cannot find exit blocks");

  // Verify that there are no parallel edges
  for (auto &Block : Func.Blocks) {
    std::unordered_set<uint64_t> UniqueSuccs;
    for (auto &Jump : Block.SuccJumps) {
      auto It = UniqueSuccs.insert(Jump->Target);
      assert(It.second && "input CFG contains parallel edges");
    }
  }
  // Verify CFG jumps
  for (auto &Block : Func.Blocks) {
    assert((!Block.isEntry() || !Block.isExit()) &&
           "a block cannot be an entry and an exit");
  }
  // Verify input block weights
  for (auto &Block : Func.Blocks) {
    assert((!Block.HasUnknownWeight || Block.Weight == 0 || Block.isEntry()) &&
           "non-zero weight of a block w/o weight except for an entry");
  }
  // Verify input jump weights
  for (auto &Jump : Func.Jumps) {
    assert((!Jump.HasUnknownWeight || Jump.Weight == 0) &&
           "non-zero weight of a jump w/o weight");
  }
}

/// Verify that the computed flow values satisfy flow conservation rules.
void verifyOutput(const FlowFunction &Func) {
  const uint64_t NumBlocks = Func.Blocks.size();
  auto InFlow = std::vector<uint64_t>(NumBlocks, 0);
  auto OutFlow = std::vector<uint64_t>(NumBlocks, 0);
  for (const auto &Jump : Func.Jumps) {
    InFlow[Jump.Target] += Jump.Flow;
    OutFlow[Jump.Source] += Jump.Flow;
  }

  uint64_t TotalInFlow = 0;
  uint64_t TotalOutFlow = 0;
  for (uint64_t I = 0; I < NumBlocks; I++) {
    auto &Block = Func.Blocks[I];
    if (Block.isEntry()) {
      TotalInFlow += Block.Flow;
      assert(Block.Flow == OutFlow[I] && "incorrectly computed control flow");
    } else if (Block.isExit()) {
      TotalOutFlow += Block.Flow;
      assert(Block.Flow == InFlow[I] && "incorrectly computed control flow");
    } else {
      assert(Block.Flow == OutFlow[I] && "incorrectly computed control flow");
      assert(Block.Flow == InFlow[I] && "incorrectly computed control flow");
    }
  }
  assert(TotalInFlow == TotalOutFlow && "incorrectly computed control flow");

  // Verify that there are no isolated flow components
  // One could modify FlowFunction to hold edges indexed by the sources, which
  // will avoid a creation of the object
  auto PositiveFlowEdges = std::vector<std::vector<uint64_t>>(NumBlocks);
  for (const auto &Jump : Func.Jumps) {
    if (Jump.Flow > 0) {
      PositiveFlowEdges[Jump.Source].push_back(Jump.Target);
    }
  }

  // Run BFS from the source along edges with positive flow
  std::queue<uint64_t> Queue;
  auto Visited = BitVector(NumBlocks, false);
  Queue.push(Func.Entry);
  Visited[Func.Entry] = true;
  while (!Queue.empty()) {
    uint64_t Src = Queue.front();
    Queue.pop();
    for (uint64_t Dst : PositiveFlowEdges[Src]) {
      if (!Visited[Dst]) {
        Queue.push(Dst);
        Visited[Dst] = true;
      }
    }
  }

  // Verify that every block that has a positive flow is reached from the source
  // along edges with a positive flow
  for (uint64_t I = 0; I < NumBlocks; I++) {
    auto &Block = Func.Blocks[I];
    assert((Visited[I] || Block.Flow == 0) && "an isolated flow component");
  }
}
#endif

} // end of anonymous namespace

/// Apply the profile inference algorithm for a given function and provided
/// profi options
void llvm::applyFlowInference(const ProfiParams &Params, FlowFunction &Func) { … }

/// Apply the profile inference algorithm for a given flow function
void llvm::applyFlowInference(FlowFunction &Func) { … }
llvm/llvm/lib/Transforms/Utils/SampleProfileInference.cpp
