llvm/bolt/lib/Passes/IdenticalCodeFolding.cpp

//===- bolt/Passes/IdenticalCodeFolding.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 IdenticalCodeFolding class.
//
//===----------------------------------------------------------------------===//

#include "bolt/Passes/IdenticalCodeFolding.h"
#include "bolt/Core/HashUtilities.h"
#include "bolt/Core/ParallelUtilities.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/ThreadPool.h"
#include "llvm/Support/Timer.h"
#include <atomic>
#include <iterator>
#include <map>
#include <set>
#include <unordered_map>

#define DEBUG_TYPE …

usingnamespacellvm;
usingnamespacebolt;

namespace opts {

extern cl::OptionCategory BoltOptCategory;

static cl::opt<bool>
    ICFUseDFS("icf-dfs", cl::desc("use DFS ordering when using -icf option"),
              cl::ReallyHidden, cl::cat(BoltOptCategory));

static cl::opt<bool>
TimeICF("time-icf",
  cl::desc("time icf steps"),
  cl::ReallyHidden,
  cl::ZeroOrMore,
  cl::cat(BoltOptCategory));
} // namespace opts

/// Compare two jump tables in 2 functions. The function relies on consistent
/// ordering of basic blocks in both binary functions (e.g. DFS).
static bool equalJumpTables(const JumpTable &JumpTableA,
                            const JumpTable &JumpTableB,
                            const BinaryFunction &FunctionA,
                            const BinaryFunction &FunctionB) { … }

/// Helper function that compares an instruction of this function to the
/// given instruction of the given function. The functions should have
/// identical CFG.
template <class Compare>
static bool isInstrEquivalentWith(const MCInst &InstA,
                                  const BinaryBasicBlock &BBA,
                                  const MCInst &InstB,
                                  const BinaryBasicBlock &BBB, Compare Comp) { … }

/// Returns true if this function has identical code and CFG with
/// the given function \p BF.
///
/// If \p CongruentSymbols is set to true, then symbolic operands that reference
/// potentially identical but different functions are ignored during the
/// comparison.
static bool isIdenticalWith(const BinaryFunction &A, const BinaryFunction &B,
                            bool CongruentSymbols) { … }

// This hash table is used to identify identical functions. It maps
// a function to a bucket of functions identical to it.
struct KeyHash { … };

/// Identify two congruent functions. Two functions are considered congruent,
/// if they are identical/equal except for some of their instruction operands
/// that reference potentially identical functions, i.e. functions that could
/// be folded later. Congruent functions are candidates for folding in our
/// iterative ICF algorithm.
///
/// Congruent functions are required to have identical hash.
struct KeyCongruent { … };

struct KeyEqual { … };

CongruentBucketsMap;

IdenticalBucketsMap;

namespace llvm {
namespace bolt {

Error IdenticalCodeFolding::runOnFunctions(BinaryContext &BC) { … }

} // namespace bolt
} // namespace llvm