llvm/llvm/lib/Target/SystemZ/SystemZElimCompare.cpp

//===-- SystemZElimCompare.cpp - Eliminate comparison 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 pass:
// (1) tries to remove compares if CC already contains the required information
// (2) fuses compares and branches into COMPARE AND BRANCH instructions
//
//===----------------------------------------------------------------------===//

#include "SystemZ.h"
#include "SystemZInstrInfo.h"
#include "SystemZTargetMachine.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/CodeGen/LiveRegUnits.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/TargetRegisterInfo.h"
#include "llvm/CodeGen/TargetSubtargetInfo.h"
#include "llvm/MC/MCInstrDesc.h"
#include <cassert>
#include <cstdint>

usingnamespacellvm;

#define DEBUG_TYPE …

STATISTIC(BranchOnCounts, "Number of branch-on-count instructions");
STATISTIC(LoadAndTraps, "Number of load-and-trap instructions");
STATISTIC(EliminatedComparisons, "Number of eliminated comparisons");
STATISTIC(FusedComparisons, "Number of fused compare-and-branch instructions");

namespace {

// Represents the references to a particular register in one or more
// instructions.
struct Reference { … };

class SystemZElimCompare : public MachineFunctionPass { … };

char SystemZElimCompare::ID = …;

} // end anonymous namespace

INITIALIZE_PASS(…)

// Returns true if MI is an instruction whose output equals the value in Reg.
static bool preservesValueOf(MachineInstr &MI, unsigned Reg) { … }

// Return true if any CC result of MI would (perhaps after conversion)
// reflect the value of Reg.
static bool resultTests(MachineInstr &MI, unsigned Reg) { … }

// Describe the references to Reg or any of its aliases in MI.
Reference SystemZElimCompare::getRegReferences(MachineInstr &MI, unsigned Reg) { … }

// Return true if this is a load and test which can be optimized the
// same way as compare instruction.
static bool isLoadAndTestAsCmp(MachineInstr &MI) { … }

// Return the source register of Compare, which is the unknown value
// being tested.
static unsigned getCompareSourceReg(MachineInstr &Compare) { … }

// Compare compares the result of MI against zero.  If MI is an addition
// of -1 and if CCUsers is a single branch on nonzero, eliminate the addition
// and convert the branch to a BRCT(G) or BRCTH.  Return true on success.
bool SystemZElimCompare::convertToBRCT(
    MachineInstr &MI, MachineInstr &Compare,
    SmallVectorImpl<MachineInstr *> &CCUsers) { … }

// Compare compares the result of MI against zero.  If MI is a suitable load
// instruction and if CCUsers is a single conditional trap on zero, eliminate
// the load and convert the branch to a load-and-trap.  Return true on success.
bool SystemZElimCompare::convertToLoadAndTrap(
    MachineInstr &MI, MachineInstr &Compare,
    SmallVectorImpl<MachineInstr *> &CCUsers) { … }

// If MI is a load instruction, try to convert it into a LOAD AND TEST.
// Return true on success.
bool SystemZElimCompare::convertToLoadAndTest(
    MachineInstr &MI, MachineInstr &Compare,
    SmallVectorImpl<MachineInstr *> &CCUsers) { … }

// See if MI is an instruction with an equivalent "logical" opcode that can
// be used and replace MI. This is useful for EQ/NE comparisons where the
// "nsw" flag is missing since the "logical" opcode always sets CC to reflect
// the result being zero or non-zero.
bool SystemZElimCompare::convertToLogical(
    MachineInstr &MI, MachineInstr &Compare,
    SmallVectorImpl<MachineInstr *> &CCUsers) { … }

#ifndef NDEBUG
static bool isAddWithImmediate(unsigned Opcode) {
  switch(Opcode) {
  case SystemZ::AHI:
  case SystemZ::AHIK:
  case SystemZ::AGHI:
  case SystemZ::AGHIK:
  case SystemZ::AFI:
  case SystemZ::AIH:
  case SystemZ::AGFI:
    return true;
  default: break;
  }
  return false;
}
#endif

// The CC users in CCUsers are testing the result of a comparison of some
// value X against zero and we know that any CC value produced by MI would
// also reflect the value of X.  ConvOpc may be used to pass the transfomed
// opcode MI will have if this succeeds.  Try to adjust CCUsers so that they
// test the result of MI directly, returning true on success.  Leave
// everything unchanged on failure.
bool SystemZElimCompare::adjustCCMasksForInstr(
    MachineInstr &MI, MachineInstr &Compare,
    SmallVectorImpl<MachineInstr *> &CCUsers,
    unsigned ConvOpc) { … }

// Return true if Compare is a comparison against zero.
static bool isCompareZero(MachineInstr &Compare) { … }

// Try to optimize cases where comparison instruction Compare is testing
// a value against zero.  Return true on success and if Compare should be
// deleted as dead.  CCUsers is the list of instructions that use the CC
// value produced by Compare.
bool SystemZElimCompare::optimizeCompareZero(
    MachineInstr &Compare, SmallVectorImpl<MachineInstr *> &CCUsers) { … }

// Try to fuse comparison instruction Compare into a later branch.
// Return true on success and if Compare is therefore redundant.
bool SystemZElimCompare::fuseCompareOperations(
    MachineInstr &Compare, SmallVectorImpl<MachineInstr *> &CCUsers) { … }

// Process all comparison instructions in MBB.  Return true if something
// changed.
bool SystemZElimCompare::processBlock(MachineBasicBlock &MBB) { … }

bool SystemZElimCompare::runOnMachineFunction(MachineFunction &F) { … }

FunctionPass *llvm::createSystemZElimComparePass(SystemZTargetMachine &TM) { … }