bolt/include/bolt/Passes/ReorderUtils.h

//===- bolt/Passes/ReorderUtils.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
//
//===----------------------------------------------------------------------===//
//
// This file contains classes and functions to assist function and basic block
// reordering.
//
//===----------------------------------------------------------------------===//

#ifndef BOLT_PASSES_REORDER_UTILS_H
#define BOLT_PASSES_REORDER_UTILS_H

#include <memory>
#include <vector>

#include "llvm/ADT/BitVector.h"

namespace llvm {
namespace bolt {

// This class maintains adjacency information for all Clusters being
// processed. It is used for visiting all neighbors of any given Cluster
// while merging pairs of Clusters. Every Cluster must implement the id() method
template <typename Cluster> class AdjacencyMatrix {
public:
  explicit AdjacencyMatrix(size_t Size) : Bits(Size, BitVector(Size, false)) {}

  void initialize(std::vector<Cluster *> &_Clusters) { Clusters = _Clusters; }

  template <typename F> void forAllAdjacent(const Cluster *C, F Func) const {
    const_cast<AdjacencyMatrix *>(this)->forallAdjacent(C, Func);
  }

  template <typename F> void forAllAdjacent(const Cluster *C, F Func) {
    for (int I : Bits[C->id()].set_bits())
      Func(Clusters[I]);
  }

  /// Merge adjacency info from cluster B into cluster A.  Info for cluster B is
  /// left in an undefined state.
  void merge(const Cluster *A, const Cluster *B) {
    Bits[A->id()] |= Bits[B->id()];
    Bits[A->id()][A->id()] = false;
    Bits[A->id()][B->id()] = false;
    Bits[B->id()][A->id()] = false;
    for (int I : Bits[B->id()].set_bits()) {
      Bits[I][A->id()] = true;
      Bits[I][B->id()] = false;
    }
  }

  void set(const Cluster *A, const Cluster *B) { set(A, B, true); }

private:
  void set(const Cluster *A, const Cluster *B, bool Value) {
    assert(A != B);
    Bits[A->id()][B->id()] = Value;
    Bits[B->id()][A->id()] = Value;
  }

  std::vector<Cluster *> Clusters;
  std::vector<BitVector> Bits;
};

// This class holds cached results of specified type for a pair of Clusters.
// It can invalidate all cache entries associated with a given Cluster.
template <typename Cluster, typename ValueType> class ClusterPairCache {
public:
  explicit ClusterPairCache(size_t Size)
      : Size(Size), Cache(Size * Size), Valid(Size * Size, false) {}

  bool contains(const Cluster *First, const Cluster *Second) const {
    return Valid[index(First, Second)];
  }

  ValueType get(const Cluster *First, const Cluster *Second) const {
    assert(contains(First, Second));
    return Cache[index(First, Second)];
  }

  void set(const Cluster *First, const Cluster *Second, ValueType Value) {
    const size_t Index = index(First, Second);
    Cache[Index] = Value;
    Valid[Index] = true;
  }

  void invalidate(const Cluster *C) {
    Valid.reset(C->id() * Size, (C->id() + 1) * Size);
    for (size_t Id = 0; Id < Size; Id++)
      Valid.reset((Id * Size) + C->id());
  }

private:
  size_t index(const Cluster *First, const Cluster *Second) const {
    return (First->id() * Size) + Second->id();
  }

  size_t Size;
  std::vector<ValueType> Cache;
  BitVector Valid;
};

// This class holds cached results of specified type for a pair of Clusters.
// It can invalidate all cache entries associated with a given Cluster.
// The functions set, get and contains are thread safe when called with
// distinct keys.
template <typename Cluster, typename ValueType>
class ClusterPairCacheThreadSafe {
public:
  explicit ClusterPairCacheThreadSafe(size_t Size)
      : Size(Size), Cache(Size * Size), Valid(Size * Size, false) {}

  bool contains(const Cluster *First, const Cluster *Second) const {
    return Valid[index(First, Second)];
  }

  ValueType get(const Cluster *First, const Cluster *Second) const {
    assert(contains(First, Second));
    return Cache[index(First, Second)];
  }

  void set(const Cluster *First, const Cluster *Second, ValueType Value) {
    const size_t Index = index(First, Second);
    Cache[Index] = Value;
    Valid[Index] = true;
  }

  void invalidate(const Cluster *C) {
    for (size_t Idx = C->id() * Size; Idx < (C->id() + 1) * Size; Idx++)
      Valid[Idx] = false;

    for (size_t Id = 0; Id < Size; Id++)
      Valid[(Id * Size) + C->id()] = false;
  }

private:
  size_t Size;
  std::vector<ValueType> Cache;
  BitVector Valid;

  size_t index(const Cluster *First, const Cluster *Second) const {
    return (First->id() * Size) + Second->id();
  }
};

} // namespace bolt
} // namespace llvm

#endif