X86OptimizeLEAs.cpp | Explore in Territory

//===- X86OptimizeLEAs.cpp - optimize usage of LEA instructions -----------===//
//
// 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 defines the pass that performs some optimizations with LEA
// instructions in order to improve performance and code size.
// Currently, it does two things:
// 1) If there are two LEA instructions calculating addresses which only differ
//    by displacement inside a basic block, one of them is removed.
// 2) Address calculations in load and store instructions are replaced by
//    existing LEA def registers where possible.
//
//===----------------------------------------------------------------------===//

#include "MCTargetDesc/X86BaseInfo.h"
#include "X86.h"
#include "X86InstrInfo.h"
#include "X86Subtarget.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DenseMapInfo.h"
#include "llvm/ADT/Hashing.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/ProfileSummaryInfo.h"
#include "llvm/CodeGen/LazyMachineBlockFrequencyInfo.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineOperand.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/MachineSizeOpts.h"
#include "llvm/CodeGen/TargetOpcodes.h"
#include "llvm/CodeGen/TargetRegisterInfo.h"
#include "llvm/IR/DebugInfoMetadata.h"
#include "llvm/IR/DebugLoc.h"
#include "llvm/IR/Function.h"
#include "llvm/MC/MCInstrDesc.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/raw_ostream.h"
#include <cassert>
#include <cstdint>
#include <iterator>

usingnamespacellvm;

#define DEBUG_TYPE …

static cl::opt<bool>
    DisableX86LEAOpt("disable-x86-lea-opt", cl::Hidden,
                     cl::desc("X86: Disable LEA optimizations."),
                     cl::init(false));

STATISTIC(NumSubstLEAs, "Number of LEA instruction substitutions");
STATISTIC(NumRedundantLEAs, "Number of redundant LEA instructions removed");

/// Returns true if two machine operands are identical and they are not
/// physical registers.
static inline bool isIdenticalOp(const MachineOperand &MO1,
                                 const MachineOperand &MO2);

/// Returns true if two address displacement operands are of the same
/// type and use the same symbol/index/address regardless of the offset.
static bool isSimilarDispOp(const MachineOperand &MO1,
                            const MachineOperand &MO2);

/// Returns true if the instruction is LEA.
static inline bool isLEA(const MachineInstr &MI);

namespace {

/// A key based on instruction's memory operands.
class MemOpKey { … };

} // end anonymous namespace

namespace llvm {

/// Provide DenseMapInfo for MemOpKey.
template <> struct DenseMapInfo<MemOpKey> { … };

} // end namespace llvm

/// Returns a hash table key based on memory operands of \p MI. The
/// number of the first memory operand of \p MI is specified through \p N.
static inline MemOpKey getMemOpKey(const MachineInstr &MI, unsigned N) { … }

static inline bool isIdenticalOp(const MachineOperand &MO1,
                                 const MachineOperand &MO2) { … }

#ifndef NDEBUG
static bool isValidDispOp(const MachineOperand &MO) {
  return MO.isImm() || MO.isCPI() || MO.isJTI() || MO.isSymbol() ||
         MO.isGlobal() || MO.isBlockAddress() || MO.isMCSymbol() || MO.isMBB();
}
#endif

static bool isSimilarDispOp(const MachineOperand &MO1,
                            const MachineOperand &MO2) { … }

static inline bool isLEA(const MachineInstr &MI) { … }

namespace {

class X86OptimizeLEAPass : public MachineFunctionPass { … };

} // end anonymous namespace

char X86OptimizeLEAPass::ID = …;

FunctionPass *llvm::createX86OptimizeLEAs() { … }
INITIALIZE_PASS(…)

int X86OptimizeLEAPass::calcInstrDist(const MachineInstr &First,
                                      const MachineInstr &Last) { … }

// Find the best LEA instruction in the List to replace address recalculation in
// MI. Such LEA must meet these requirements:
// 1) The address calculated by the LEA differs only by the displacement from
//    the address used in MI.
// 2) The register class of the definition of the LEA is compatible with the
//    register class of the address base register of MI.
// 3) Displacement of the new memory operand should fit in 1 byte if possible.
// 4) The LEA should be as close to MI as possible, and prior to it if
//    possible.
bool X86OptimizeLEAPass::chooseBestLEA(
    const SmallVectorImpl<MachineInstr *> &List, const MachineInstr &MI,
    MachineInstr *&BestLEA, int64_t &AddrDispShift, int &Dist) { … }

// Get the difference between the addresses' displacements of the two
// instructions \p MI1 and \p MI2. The numbers of the first memory operands are
// passed through \p N1 and \p N2.
int64_t X86OptimizeLEAPass::getAddrDispShift(const MachineInstr &MI1,
                                             unsigned N1,
                                             const MachineInstr &MI2,
                                             unsigned N2) const { … }

// Check that the Last LEA can be replaced by the First LEA. To be so,
// these requirements must be met:
// 1) Addresses calculated by LEAs differ only by displacement.
// 2) Def registers of LEAs belong to the same class.
// 3) All uses of the Last LEA def register are replaceable, thus the
//    register is used only as address base.
bool X86OptimizeLEAPass::isReplaceable(const MachineInstr &First,
                                       const MachineInstr &Last,
                                       int64_t &AddrDispShift) const { … }

void X86OptimizeLEAPass::findLEAs(const MachineBasicBlock &MBB,
                                  MemOpMap &LEAs) { … }

// Try to find load and store instructions which recalculate addresses already
// calculated by some LEA and replace their memory operands with its def
// register.
bool X86OptimizeLEAPass::removeRedundantAddrCalc(MemOpMap &LEAs) { … }

MachineInstr *X86OptimizeLEAPass::replaceDebugValue(MachineInstr &MI,
                                                    unsigned OldReg,
                                                    unsigned NewReg,
                                                    int64_t AddrDispShift) { … }

// Try to find similar LEAs in the list and replace one with another.
bool X86OptimizeLEAPass::removeRedundantLEAs(MemOpMap &LEAs) { … }

bool X86OptimizeLEAPass::runOnMachineFunction(MachineFunction &MF) { … }
llvm/llvm/lib/Target/X86/X86OptimizeLEAs.cpp
