PPCMIPeephole.cpp | Explore in Territory

//===-------------- PPCMIPeephole.cpp - MI Peephole Cleanups -------------===//
//
// 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 performs peephole optimizations to clean up ugly code
// sequences at the MachineInstruction layer.  It runs at the end of
// the SSA phases, following VSX swap removal.  A pass of dead code
// elimination follows this one for quick clean-up of any dead
// instructions introduced here.  Although we could do this as callbacks
// from the generic peephole pass, this would have a couple of bad
// effects:  it might remove optimization opportunities for VSX swap
// removal, and it would miss cleanups made possible following VSX
// swap removal.
//
// NOTE: We run the verifier after this pass in Asserts/Debug builds so it
//       is important to keep the code valid after transformations.
//       Common causes of errors stem from violating the contract specified
//       by kill flags. Whenever a transformation changes the live range of
//       a register, that register should be added to the work list using
//       addRegToUpdate(RegsToUpdate, <Reg>). Furthermore, if a transformation
//       is changing the definition of a register (i.e. removing the single
//       definition of the original vreg), it needs to provide a dummy
//       definition of that register using addDummyDef(<MBB>, <Reg>).
//===---------------------------------------------------------------------===//

#include "MCTargetDesc/PPCMCTargetDesc.h"
#include "MCTargetDesc/PPCPredicates.h"
#include "PPC.h"
#include "PPCInstrBuilder.h"
#include "PPCInstrInfo.h"
#include "PPCMachineFunctionInfo.h"
#include "PPCTargetMachine.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/CodeGen/LiveVariables.h"
#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineFrameInfo.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachinePostDominators.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/InitializePasses.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/DebugCounter.h"

usingnamespacellvm;

#define DEBUG_TYPE …

STATISTIC(RemoveTOCSave, "Number of TOC saves removed");
STATISTIC(MultiTOCSaves,
          "Number of functions with multiple TOC saves that must be kept");
STATISTIC(NumTOCSavesInPrologue, "Number of TOC saves placed in the prologue");
STATISTIC(NumEliminatedSExt, "Number of eliminated sign-extensions");
STATISTIC(NumEliminatedZExt, "Number of eliminated zero-extensions");
STATISTIC(NumOptADDLIs, "Number of optimized ADD instruction fed by LI");
STATISTIC(NumConvertedToImmediateForm,
          "Number of instructions converted to their immediate form");
STATISTIC(NumFunctionsEnteredInMIPeephole,
          "Number of functions entered in PPC MI Peepholes");
STATISTIC(NumFixedPointIterations,
          "Number of fixed-point iterations converting reg-reg instructions "
          "to reg-imm ones");
STATISTIC(NumRotatesCollapsed,
          "Number of pairs of rotate left, clear left/right collapsed");
STATISTIC(NumEXTSWAndSLDICombined,
          "Number of pairs of EXTSW and SLDI combined as EXTSWSLI");
STATISTIC(NumLoadImmZeroFoldedAndRemoved,
          "Number of LI(8) reg, 0 that are folded to r0 and removed");

static cl::opt<bool>
FixedPointRegToImm("ppc-reg-to-imm-fixed-point", cl::Hidden, cl::init(true),
                   cl::desc("Iterate to a fixed point when attempting to "
                            "convert reg-reg instructions to reg-imm"));

static cl::opt<bool>
ConvertRegReg("ppc-convert-rr-to-ri", cl::Hidden, cl::init(true),
              cl::desc("Convert eligible reg+reg instructions to reg+imm"));

static cl::opt<bool>
    EnableSExtElimination("ppc-eliminate-signext",
                          cl::desc("enable elimination of sign-extensions"),
                          cl::init(true), cl::Hidden);

static cl::opt<bool>
    EnableZExtElimination("ppc-eliminate-zeroext",
                          cl::desc("enable elimination of zero-extensions"),
                          cl::init(true), cl::Hidden);

static cl::opt<bool>
    EnableTrapOptimization("ppc-opt-conditional-trap",
                           cl::desc("enable optimization of conditional traps"),
                           cl::init(false), cl::Hidden);

DEBUG_COUNTER(
    PeepholeXToICounter, "ppc-xtoi-peephole",
    "Controls whether PPC reg+reg to reg+imm peephole is performed on a MI");

DEBUG_COUNTER(PeepholePerOpCounter, "ppc-per-op-peephole",
              "Controls whether PPC per opcode peephole is performed on a MI");

namespace {

struct PPCMIPeephole : public MachineFunctionPass { … };

#define addRegToUpdate(R) …
void PPCMIPeephole::addRegToUpdateWithLine(Register Reg, int Line) { … }

// Initialize class variables.
void PPCMIPeephole::initialize(MachineFunction &MFParm) { … }

static MachineInstr *getVRegDefOrNull(MachineOperand *Op,
                                      MachineRegisterInfo *MRI) { … }

// This function returns number of known zero bits in output of MI
// starting from the most significant bit.
static unsigned getKnownLeadingZeroCount(const unsigned Reg,
                                         const PPCInstrInfo *TII,
                                         const MachineRegisterInfo *MRI) { … }

// This function maintains a map for the pairs <TOC Save Instr, Keep>
// Each time a new TOC save is encountered, it checks if any of the existing
// ones are dominated by the new one. If so, it marks the existing one as
// redundant by setting it's entry in the map as false. It then adds the new
// instruction to the map with either true or false depending on if any
// existing instructions dominated the new one.
void PPCMIPeephole::UpdateTOCSaves(
  std::map<MachineInstr *, bool> &TOCSaves, MachineInstr *MI) { … }

// This function returns a list of all PHI nodes in the tree starting from
// the RootPHI node. We perform a BFS traversal to get an ordered list of nodes.
// The list initially only contains the root PHI. When we visit a PHI node, we
// add it to the list. We continue to look for other PHI node operands while
// there are nodes to visit in the list. The function returns false if the
// optimization cannot be applied on this tree.
static bool collectUnprimedAccPHIs(MachineRegisterInfo *MRI,
                                   MachineInstr *RootPHI,
                                   SmallVectorImpl<MachineInstr *> &PHIs) { … }

// This function changes the unprimed accumulator PHI nodes in the PHIs list to
// primed accumulator PHI nodes. The list is traversed in reverse order to
// change all the PHI operands of a PHI node before changing the node itself.
// We keep a map to associate each changed PHI node to its non-changed form.
void PPCMIPeephole::convertUnprimedAccPHIs(
    const PPCInstrInfo *TII, MachineRegisterInfo *MRI,
    SmallVectorImpl<MachineInstr *> &PHIs, Register Dst) { … }

// Perform peephole optimizations.
bool PPCMIPeephole::simplifyCode() { … }

// helper functions for eliminateRedundantCompare
static bool isEqOrNe(MachineInstr *BI) { … }

static bool isSupportedCmpOp(unsigned opCode) { … }

static bool is64bitCmpOp(unsigned opCode) { … }

static bool isSignedCmpOp(unsigned opCode) { … }

static unsigned getSignedCmpOpCode(unsigned opCode) { … }

// We can decrement immediate x in (GE x) by changing it to (GT x-1) or
// (LT x) to (LE x-1)
static unsigned getPredicateToDecImm(MachineInstr *BI, MachineInstr *CMPI) { … }

// We can increment immediate x in (GT x) by changing it to (GE x+1) or
// (LE x) to (LT x+1)
static unsigned getPredicateToIncImm(MachineInstr *BI, MachineInstr *CMPI) { … }

// This takes a Phi node and returns a register value for the specified BB.
static unsigned getIncomingRegForBlock(MachineInstr *Phi,
                                       MachineBasicBlock *MBB) { … }

// This function tracks the source of the register through register copy.
// If BB1 and BB2 are non-NULL, we also track PHI instruction in BB2
// assuming that the control comes from BB1 into BB2.
static unsigned getSrcVReg(unsigned Reg, MachineBasicBlock *BB1,
                           MachineBasicBlock *BB2, MachineRegisterInfo *MRI) { … }

static bool eligibleForCompareElimination(MachineBasicBlock &MBB,
                                          MachineBasicBlock *&PredMBB,
                                          MachineBasicBlock *&MBBtoMoveCmp,
                                          MachineRegisterInfo *MRI) { … }

// This function will iterate over the input map containing a pair of TOC save
// instruction and a flag. The flag will be set to false if the TOC save is
// proven redundant. This function will erase from the basic block all the TOC
// saves marked as redundant.
bool PPCMIPeephole::eliminateRedundantTOCSaves(
    std::map<MachineInstr *, bool> &TOCSaves) { … }

// If multiple conditional branches are executed based on the (essentially)
// same comparison, we merge compare instructions into one and make multiple
// conditional branches on this comparison.
// For example,
//   if (a == 0) { ... }
//   else if (a < 0) { ... }
// can be executed by one compare and two conditional branches instead of
// two pairs of a compare and a conditional branch.
//
// This method merges two compare instructions in two MBBs and modifies the
// compare and conditional branch instructions if needed.
// For the above example, the input for this pass looks like:
//   cmplwi r3, 0
//   beq    0, .LBB0_3
//   cmpwi  r3, -1
//   bgt    0, .LBB0_4
// So, before merging two compares, we need to modify these instructions as
//   cmpwi  r3, 0       ; cmplwi and cmpwi yield same result for beq
//   beq    0, .LBB0_3
//   cmpwi  r3, 0       ; greather than -1 means greater or equal to 0
//   bge    0, .LBB0_4

bool PPCMIPeephole::eliminateRedundantCompare() { … }

// We miss the opportunity to emit an RLDIC when lowering jump tables
// since ISEL sees only a single basic block. When selecting, the clear
// and shift left will be in different blocks.
bool PPCMIPeephole::emitRLDICWhenLoweringJumpTables(MachineInstr &MI,
                                                    MachineInstr *&ToErase) { … }

// For case in LLVM IR
// entry:
//   %iconv = sext i32 %index to i64
//   br i1 undef label %true, label %false
// true:
//   %ptr = getelementptr inbounds i32, i32* null, i64 %iconv
// ...
// PPCISelLowering::combineSHL fails to combine, because sext and shl are in
// different BBs when conducting instruction selection. We can do a peephole
// optimization to combine these two instructions into extswsli after
// instruction selection.
bool PPCMIPeephole::combineSEXTAndSHL(MachineInstr &MI,
                                      MachineInstr *&ToErase) { … }

} // end default namespace

INITIALIZE_PASS_BEGIN(PPCMIPeephole, DEBUG_TYPE,
                      "PowerPC MI Peephole Optimization", false, false)
INITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfoWrapperPass)
INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass)
INITIALIZE_PASS_DEPENDENCY(MachinePostDominatorTreeWrapperPass)
INITIALIZE_PASS_DEPENDENCY(LiveVariablesWrapperPass)
INITIALIZE_PASS_END(PPCMIPeephole, DEBUG_TYPE,
                    "PowerPC MI Peephole Optimization", false, false)

char PPCMIPeephole::ID = …;
FunctionPass*
llvm::createPPCMIPeepholePass() { … }
llvm/llvm/lib/Target/PowerPC/PPCMIPeephole.cpp
