Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

//===- Transforms/Utils/SampleProfileInference.h ----------*- C++ -*-===//

//

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

//

//===----------------------------------------------------------------------===//

//

/// \file

/// This file provides the interface for the profile inference algorithm, profi.

//

//===----------------------------------------------------------------------===//

#ifndef LLVM_TRANSFORMS_UTILS_SAMPLEPROFILEINFERENCE_H

#define LLVM_TRANSFORMS_UTILS_SAMPLEPROFILEINFERENCE_H

#include "llvm/ADT/DenseMap.h"

#include "llvm/ADT/DepthFirstIterator.h"

#include "llvm/ADT/SmallVector.h"

#include "llvm/IR/BasicBlock.h"

#include "llvm/IR/Instruction.h"

#include "llvm/IR/Instructions.h"

namespace llvm {

class Function;

class MachineBasicBlock;

class MachineFunction;

namespace afdo_detail {

template <class BlockT> struct TypeMap {};

template <> struct TypeMap<BasicBlock> {

  using BasicBlockT = BasicBlock;

  using FunctionT = Function;

};

template <> struct TypeMap<MachineBasicBlock> {

  using BasicBlockT = MachineBasicBlock;

  using FunctionT = MachineFunction;

};

} // end namespace afdo_detail

struct FlowJump;

/// A wrapper of a binary basic block.

struct FlowBlock {

  uint64_t Index;

  uint64_t Weight{0};

  bool HasUnknownWeight{true};

  bool IsUnlikely{false};

  uint64_t Flow{0};

  std::vector<FlowJump *> SuccJumps;

  std::vector<FlowJump *> PredJumps;

  /// Check if it is the entry block in the function.

  bool isEntry() const { return PredJumps.empty(); }

  /// Check if it is an exit block in the function.

  bool isExit() const { return SuccJumps.empty(); }

};

/// A wrapper of a jump between two basic blocks.

struct FlowJump {

  uint64_t Source;

  uint64_t Target;

  uint64_t Weight{0};

  bool HasUnknownWeight{true};

  bool IsUnlikely{false};

  uint64_t Flow{0};

};

/// A wrapper of binary function with basic blocks and jumps.

struct FlowFunction {

  /// Basic blocks in the function.

  std::vector<FlowBlock> Blocks;

  /// Jumps between the basic blocks.

  std::vector<FlowJump> Jumps;

  /// The index of the entry block.

  uint64_t Entry{0};

};

/// Various thresholds and options controlling the behavior of the profile

/// inference algorithm. Default values are tuned for several large-scale

/// applications, and can be modified via corresponding command-line flags.

struct ProfiParams {

  /// Evenly distribute flow when there are multiple equally likely options.

  bool EvenFlowDistribution{false};

  /// Evenly re-distribute flow among unknown subgraphs.

  bool RebalanceUnknown{false};

  /// Join isolated components having positive flow.

  bool JoinIslands{false};

  /// The cost of increasing a block's count by one.

  unsigned CostBlockInc{0};

  /// The cost of decreasing a block's count by one.

  unsigned CostBlockDec{0};

  /// The cost of increasing a count of zero-weight block by one.

  unsigned CostBlockZeroInc{0};

  /// The cost of increasing the entry block's count by one.

  unsigned CostBlockEntryInc{0};

  /// The cost of decreasing the entry block's count by one.

  unsigned CostBlockEntryDec{0};

  /// The cost of increasing an unknown block's count by one.

  unsigned CostBlockUnknownInc{0};

  /// The cost of increasing a jump's count by one.

  unsigned CostJumpInc{0};

  /// The cost of increasing a fall-through jump's count by one.

  unsigned CostJumpFTInc{0};

  /// The cost of decreasing a jump's count by one.

  unsigned CostJumpDec{0};

  /// The cost of decreasing a fall-through jump's count by one.

  unsigned CostJumpFTDec{0};

  /// The cost of increasing an unknown jump's count by one.

  unsigned CostJumpUnknownInc{0};

  /// The cost of increasing an unknown fall-through jump's count by one.

  unsigned CostJumpUnknownFTInc{0};

  /// The cost of taking an unlikely block/jump.

  const int64_t CostUnlikely = ((int64_t)1) << 30;

};

void applyFlowInference(const ProfiParams &Params, FlowFunction &Func);

void applyFlowInference(FlowFunction &Func);

/// Sample profile inference pass.

template <typename BT> class SampleProfileInference {

public:

  using BasicBlockT = typename afdo_detail::TypeMap<BT>::BasicBlockT;

  using FunctionT = typename afdo_detail::TypeMap<BT>::FunctionT;

  using Edge = std::pair<const BasicBlockT *, const BasicBlockT *>;

  using BlockWeightMap = DenseMap<const BasicBlockT *, uint64_t>;

  using EdgeWeightMap = DenseMap<Edge, uint64_t>;

  using BlockEdgeMap =

      DenseMap<const BasicBlockT *, SmallVector<const BasicBlockT *, 8>>;

  SampleProfileInference(FunctionT &F, BlockEdgeMap &Successors,

                         BlockWeightMap &SampleBlockWeights)

      : F(F), Successors(Successors), SampleBlockWeights(SampleBlockWeights) {}

  /// Apply the profile inference algorithm for a given function

  void apply(BlockWeightMap &BlockWeights, EdgeWeightMap &EdgeWeights);

private:

  /// Initialize flow function blocks, jumps and misc metadata.

  void initFunction(FlowFunction &Func,

                    const std::vector<const BasicBlockT *> &BasicBlocks,

                    DenseMap<const BasicBlockT *, uint64_t> &BlockIndex);

  /// Try to infer branch probabilities mimicking implementation of

  /// BranchProbabilityInfo. Unlikely taken branches are marked so that the

  /// inference algorithm can avoid sending flow along corresponding edges.

  void findUnlikelyJumps(const std::vector<const BasicBlockT *> &BasicBlocks,

                         BlockEdgeMap &Successors, FlowFunction &Func);

  /// Determine whether the block is an exit in the CFG.

  bool isExit(const BasicBlockT *BB);

  /// Function.

  const FunctionT &F;

  /// Successors for each basic block in the CFG.

  BlockEdgeMap &Successors;

  /// Map basic blocks to their sampled weights.

  BlockWeightMap &SampleBlockWeights;

};

template <typename BT>

void SampleProfileInference<BT>::apply(BlockWeightMap &BlockWeights,

                                       EdgeWeightMap &EdgeWeights) {

  // Find all forwards reachable blocks which the inference algorithm will be

  // applied on.

  df_iterator_default_set<const BasicBlockT *> Reachable;

  for (auto *BB : depth_first_ext(&F, Reachable))

    (void)BB /* Mark all reachable blocks */;

  // Find all backwards reachable blocks which the inference algorithm will be

  // applied on.

  df_iterator_default_set<const BasicBlockT *> InverseReachable;

  for (const auto &BB : F) {

    // An exit block is a block without any successors.

    if (isExit(&BB)) {

      for (auto *RBB : inverse_depth_first_ext(&BB, InverseReachable))

        (void)RBB;

    }

  }

  // Keep a stable order for reachable blocks

  DenseMap<const BasicBlockT *, uint64_t> BlockIndex;

  std::vector<const BasicBlockT *> BasicBlocks;

  BlockIndex.reserve(Reachable.size());

  BasicBlocks.reserve(Reachable.size());

  for (const auto &BB : F) {

    if (Reachable.count(&BB) && InverseReachable.count(&BB)) {

      BlockIndex[&BB] = BasicBlocks.size();

      BasicBlocks.push_back(&BB);

    }

  }

  BlockWeights.clear();

  EdgeWeights.clear();

  bool HasSamples = false;

  for (const auto *BB : BasicBlocks) {

    auto It = SampleBlockWeights.find(BB);

    if (It != SampleBlockWeights.end() && It->second > 0) {

      HasSamples = true;

      BlockWeights[BB] = It->second;

    }

  }

  // Quit early for functions with a single block or ones w/o samples

  if (BasicBlocks.size() <= 1 || !HasSamples) {

    return;

  }

  // Create necessary objects

  FlowFunction Func;

  initFunction(Func, BasicBlocks, BlockIndex);

  // Create and apply the inference network model.

  applyFlowInference(Func);

  // Extract the resulting weights from the control flow

  // All weights are increased by one to avoid propagation errors introduced by

  // zero weights.

  for (const auto *BB : BasicBlocks) {

    BlockWeights[BB] = Func.Blocks[BlockIndex[BB]].Flow;

  }

  for (auto &Jump : Func.Jumps) {

    Edge E = std::make_pair(BasicBlocks[Jump.Source], BasicBlocks[Jump.Target]);

    EdgeWeights[E] = Jump.Flow;

  }

#ifndef NDEBUG

  // Unreachable blocks and edges should not have a weight.

  for (auto &I : BlockWeights) {

    assert(Reachable.contains(I.first));

    assert(InverseReachable.contains(I.first));

  }

  for (auto &I : EdgeWeights) {

    assert(Reachable.contains(I.first.first) &&

           Reachable.contains(I.first.second));

    assert(InverseReachable.contains(I.first.first) &&

           InverseReachable.contains(I.first.second));

  }

#endif

}

template <typename BT>

void SampleProfileInference<BT>::initFunction(

    FlowFunction &Func, const std::vector<const BasicBlockT *> &BasicBlocks,

    DenseMap<const BasicBlockT *, uint64_t> &BlockIndex) {

  Func.Blocks.reserve(BasicBlocks.size());

  // Create FlowBlocks

  for (const auto *BB : BasicBlocks) {

    FlowBlock Block;

    if (SampleBlockWeights.find(BB) != SampleBlockWeights.end()) {

      Block.HasUnknownWeight = false;

      Block.Weight = SampleBlockWeights[BB];

    } else {

      Block.HasUnknownWeight = true;

      Block.Weight = 0;

    }

    Block.Index = Func.Blocks.size();

    Func.Blocks.push_back(Block);

  }

  // Create FlowEdges

  for (const auto *BB : BasicBlocks) {

    for (auto *Succ : Successors[BB]) {

      if (!BlockIndex.count(Succ))

        continue;

      FlowJump Jump;

      Jump.Source = BlockIndex[BB];

      Jump.Target = BlockIndex[Succ];

      Func.Jumps.push_back(Jump);

    }

  }

  for (auto &Jump : Func.Jumps) {

    uint64_t Src = Jump.Source;

    uint64_t Dst = Jump.Target;

    Func.Blocks[Src].SuccJumps.push_back(&Jump);

    Func.Blocks[Dst].PredJumps.push_back(&Jump);

  }

  // Try to infer probabilities of jumps based on the content of basic block

  findUnlikelyJumps(BasicBlocks, Successors, Func);

  // Find the entry block

  for (size_t I = 0; I < Func.Blocks.size(); I++) {

    if (Func.Blocks[I].isEntry()) {

      Func.Entry = I;

      break;

    }

  }

  assert(Func.Entry == 0 && "incorrect index of the entry block");

  // Pre-process data: make sure the entry weight is at least 1

  auto &EntryBlock = Func.Blocks[Func.Entry];

  if (EntryBlock.Weight == 0 && !EntryBlock.HasUnknownWeight) {

    EntryBlock.Weight = 1;

    EntryBlock.HasUnknownWeight = false;

  }

}

template <typename BT>

inline void SampleProfileInference<BT>::findUnlikelyJumps(

    const std::vector<const BasicBlockT *> &BasicBlocks,

    BlockEdgeMap &Successors, FlowFunction &Func) {}

template <>

inline void SampleProfileInference<BasicBlock>::findUnlikelyJumps(

    const std::vector<const BasicBlockT *> &BasicBlocks,

    BlockEdgeMap &Successors, FlowFunction &Func) {

  for (auto &Jump : Func.Jumps) {

    const auto *BB = BasicBlocks[Jump.Source];

    const auto *Succ = BasicBlocks[Jump.Target];

    const Instruction *TI = BB->getTerminator();

    // Check if a block ends with InvokeInst and mark non-taken branch unlikely.

    // In that case block Succ should be a landing pad

    if (Successors[BB].size() == 2 && Successors[BB].back() == Succ) {

      if (isa<InvokeInst>(TI)) {

        Jump.IsUnlikely = true;

      }

    }

    const Instruction *SuccTI = Succ->getTerminator();

    // Check if the target block contains UnreachableInst and mark it unlikely

    if (SuccTI->getNumSuccessors() == 0) {

      if (isa<UnreachableInst>(SuccTI)) {

        Jump.IsUnlikely = true;

      }

    }

  }

}

template <typename BT>

inline bool SampleProfileInference<BT>::isExit(const BasicBlockT *BB) {

  return BB->succ_empty();

}

template <>

inline bool SampleProfileInference<BasicBlock>::isExit(const BasicBlock *BB) {

  return succ_empty(BB);

}

} // end namespace llvm

#endif // LLVM_TRANSFORMS_UTILS_SAMPLEPROFILEINFERENCE_H