llvm/llvm/lib/Target/Hexagon/HexagonBitSimplify.cpp

//===- HexagonBitSimplify.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
//
//===----------------------------------------------------------------------===//

#include "BitTracker.h"
#include "HexagonBitTracker.h"
#include "HexagonInstrInfo.h"
#include "HexagonRegisterInfo.h"
#include "HexagonSubtarget.h"
#include "llvm/ADT/BitVector.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/GraphTraits.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineDominators.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/TargetRegisterInfo.h"
#include "llvm/IR/DebugLoc.h"
#include "llvm/InitializePasses.h"
#include "llvm/MC/MCInstrDesc.h"
#include "llvm/Pass.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <deque>
#include <iterator>
#include <limits>
#include <utility>
#include <vector>

#define DEBUG_TYPE …

usingnamespacellvm;

static cl::opt<bool> PreserveTiedOps("hexbit-keep-tied", cl::Hidden,
  cl::init(true), cl::desc("Preserve subregisters in tied operands"));
static cl::opt<bool> GenExtract("hexbit-extract", cl::Hidden,
  cl::init(true), cl::desc("Generate extract instructions"));
static cl::opt<bool> GenBitSplit("hexbit-bitsplit", cl::Hidden,
  cl::init(true), cl::desc("Generate bitsplit instructions"));

static cl::opt<unsigned> MaxExtract("hexbit-max-extract", cl::Hidden,
  cl::init(std::numeric_limits<unsigned>::max()));
static unsigned CountExtract = …;
static cl::opt<unsigned> MaxBitSplit("hexbit-max-bitsplit", cl::Hidden,
  cl::init(std::numeric_limits<unsigned>::max()));
static unsigned CountBitSplit = …;

static cl::opt<unsigned> RegisterSetLimit("hexbit-registerset-limit",
  cl::Hidden, cl::init(1000));

namespace llvm {

  void initializeHexagonBitSimplifyPass(PassRegistry& Registry);
  FunctionPass *createHexagonBitSimplify();

} // end namespace llvm

namespace {

  // Set of virtual registers, based on BitVector.
  struct RegisterSet { … };

  struct PrintRegSet { … };

  raw_ostream &operator<< (raw_ostream &OS, const PrintRegSet &P)
    LLVM_ATTRIBUTE_UNUSED;
  raw_ostream &operator<< (raw_ostream &OS, const PrintRegSet &P) { … }

  class Transformation;

  class HexagonBitSimplify : public MachineFunctionPass { … };

  HBS;

  // The purpose of this class is to provide a common facility to traverse
  // the function top-down or bottom-up via the dominator tree, and keep
  // track of the available registers.
  class Transformation { … };

} // end anonymous namespace

char HexagonBitSimplify::ID = …;

INITIALIZE_PASS_BEGIN(HexagonBitSimplify, "hexagon-bit-simplify",
      "Hexagon bit simplification", false, false)
INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass)
INITIALIZE_PASS_END(HexagonBitSimplify, "hexagon-bit-simplify",
      "Hexagon bit simplification", false, false)

bool HexagonBitSimplify::visitBlock(MachineBasicBlock &B, Transformation &T,
      RegisterSet &AVs) { … }

//
// Utility functions:
//
void HexagonBitSimplify::getInstrDefs(const MachineInstr &MI,
      RegisterSet &Defs) { … }

void HexagonBitSimplify::getInstrUses(const MachineInstr &MI,
      RegisterSet &Uses) { … }

// Check if all the bits in range [B, E) in both cells are equal.
bool HexagonBitSimplify::isEqual(const BitTracker::RegisterCell &RC1,
      uint16_t B1, const BitTracker::RegisterCell &RC2, uint16_t B2,
      uint16_t W) { … }

bool HexagonBitSimplify::isZero(const BitTracker::RegisterCell &RC,
      uint16_t B, uint16_t W) { … }

bool HexagonBitSimplify::getConst(const BitTracker::RegisterCell &RC,
        uint16_t B, uint16_t W, uint64_t &U) { … }

bool HexagonBitSimplify::replaceReg(Register OldR, Register NewR,
                                    MachineRegisterInfo &MRI) { … }

bool HexagonBitSimplify::replaceRegWithSub(Register OldR, Register NewR,
                                           unsigned NewSR,
                                           MachineRegisterInfo &MRI) { … }

bool HexagonBitSimplify::replaceSubWithSub(Register OldR, unsigned OldSR,
                                           Register NewR, unsigned NewSR,
                                           MachineRegisterInfo &MRI) { … }

// For a register ref (pair Reg:Sub), set Begin to the position of the LSB
// of Sub in Reg, and set Width to the size of Sub in bits. Return true,
// if this succeeded, otherwise return false.
bool HexagonBitSimplify::getSubregMask(const BitTracker::RegisterRef &RR,
      unsigned &Begin, unsigned &Width, MachineRegisterInfo &MRI) { … }


// For a REG_SEQUENCE, set SL to the low subregister and SH to the high
// subregister.
bool HexagonBitSimplify::parseRegSequence(const MachineInstr &I,
      BitTracker::RegisterRef &SL, BitTracker::RegisterRef &SH,
      const MachineRegisterInfo &MRI) { … }

// All stores (except 64-bit stores) take a 32-bit register as the source
// of the value to be stored. If the instruction stores into a location
// that is shorter than 32 bits, some bits of the source register are not
// used. For each store instruction, calculate the set of used bits in
// the source register, and set appropriate bits in Bits. Return true if
// the bits are calculated, false otherwise.
bool HexagonBitSimplify::getUsedBitsInStore(unsigned Opc, BitVector &Bits,
      uint16_t Begin) { … }

// For an instruction with opcode Opc, calculate the set of bits that it
// uses in a register in operand OpN. This only calculates the set of used
// bits for cases where it does not depend on any operands (as is the case
// in shifts, for example). For concrete instructions from a program, the
// operand may be a subregister of a larger register, while Bits would
// correspond to the larger register in its entirety. Because of that,
// the parameter Begin can be used to indicate which bit of Bits should be
// considered the LSB of the operand.
bool HexagonBitSimplify::getUsedBits(unsigned Opc, unsigned OpN,
      BitVector &Bits, uint16_t Begin, const HexagonInstrInfo &HII) { … }

// Calculate the register class that matches Reg:Sub. For example, if
// %1 is a double register, then %1:isub_hi would match the "int"
// register class.
const TargetRegisterClass *HexagonBitSimplify::getFinalVRegClass(
      const BitTracker::RegisterRef &RR, MachineRegisterInfo &MRI) { … }

// Check if RD could be replaced with RS at any possible use of RD.
// For example a predicate register cannot be replaced with a integer
// register, but a 64-bit register with a subregister can be replaced
// with a 32-bit register.
bool HexagonBitSimplify::isTransparentCopy(const BitTracker::RegisterRef &RD,
      const BitTracker::RegisterRef &RS, MachineRegisterInfo &MRI) { … }

bool HexagonBitSimplify::hasTiedUse(unsigned Reg, MachineRegisterInfo &MRI,
      unsigned NewSub) { … }

namespace {

  class DeadCodeElimination { … };

} // end anonymous namespace

bool DeadCodeElimination::isDead(unsigned R) const { … }

bool DeadCodeElimination::runOnNode(MachineDomTreeNode *N) { … }

namespace {

// Eliminate redundant instructions
//
// This transformation will identify instructions where the output register
// is the same as one of its input registers. This only works on instructions
// that define a single register (unlike post-increment loads, for example).
// The equality check is actually more detailed: the code calculates which
// bits of the output are used, and only compares these bits with the input
// registers.
// If the output matches an input, the instruction is replaced with COPY.
// The copies will be removed by another transformation.
  class RedundantInstrElimination : public Transformation { … };

} // end anonymous namespace

// Check if the instruction is a lossy shift left, where the input being
// shifted is the operand OpN of MI. If true, [LostB, LostE) is the range
// of bit indices that are lost.
bool RedundantInstrElimination::isLossyShiftLeft(const MachineInstr &MI,
      unsigned OpN, unsigned &LostB, unsigned &LostE) { … }

// Check if the instruction is a lossy shift right, where the input being
// shifted is the operand OpN of MI. If true, [LostB, LostE) is the range
// of bit indices that are lost.
bool RedundantInstrElimination::isLossyShiftRight(const MachineInstr &MI,
      unsigned OpN, unsigned &LostB, unsigned &LostE) { … }

// Calculate the bit vector that corresponds to the used bits of register Reg.
// The vector Bits has the same size, as the size of Reg in bits. If the cal-
// culation fails (i.e. the used bits are unknown), it returns false. Other-
// wise, it returns true and sets the corresponding bits in Bits.
bool RedundantInstrElimination::computeUsedBits(unsigned Reg, BitVector &Bits) { … }

// Calculate the bits used by instruction MI in a register in operand OpN.
// Return true/false if the calculation succeeds/fails. If is succeeds, set
// used bits in Bits. This function does not reset any bits in Bits, so
// subsequent calls over different instructions will result in the union
// of the used bits in all these instructions.
// The register in question may be used with a sub-register, whereas Bits
// holds the bits for the entire register. To keep track of that, the
// argument Begin indicates where in Bits is the lowest-significant bit
// of the register used in operand OpN. For example, in instruction:
//   %1 = S2_lsr_i_r %2:isub_hi, 10
// the operand 1 is a 32-bit register, which happens to be a subregister
// of the 64-bit register %2, and that subregister starts at position 32.
// In this case Begin=32, since Bits[32] would be the lowest-significant bit
// of %2:isub_hi.
bool RedundantInstrElimination::computeUsedBits(const MachineInstr &MI,
      unsigned OpN, BitVector &Bits, uint16_t Begin) { … }

// Calculates the used bits in RD ("defined register"), and checks if these
// bits in RS ("used register") and RD are identical.
bool RedundantInstrElimination::usedBitsEqual(BitTracker::RegisterRef RD,
      BitTracker::RegisterRef RS) { … }

bool RedundantInstrElimination::processBlock(MachineBasicBlock &B,
      const RegisterSet&) { … }

namespace {

// Recognize instructions that produce constant values known at compile-time.
// Replace them with register definitions that load these constants directly.
  class ConstGeneration : public Transformation { … };

} // end anonymous namespace

bool ConstGeneration::isTfrConst(const MachineInstr &MI) { … }

// Generate a transfer-immediate instruction that is appropriate for the
// register class and the actual value being transferred.
Register ConstGeneration::genTfrConst(const TargetRegisterClass *RC, int64_t C,
                                      MachineBasicBlock &B,
                                      MachineBasicBlock::iterator At,
                                      DebugLoc &DL) { … }

bool ConstGeneration::processBlock(MachineBasicBlock &B, const RegisterSet&) { … }

namespace {

// Identify pairs of available registers which hold identical values.
// In such cases, only one of them needs to be calculated, the other one
// will be defined as a copy of the first.
  class CopyGeneration : public Transformation { … };

// Eliminate register copies RD = RS, by replacing the uses of RD with
// with uses of RS.
  class CopyPropagation : public Transformation { … };

} // end anonymous namespace

/// Check if there is a register in AVs that is identical to Inp. If so,
/// set Out to the found register. The output may be a pair Reg:Sub.
bool CopyGeneration::findMatch(const BitTracker::RegisterRef &Inp,
      BitTracker::RegisterRef &Out, const RegisterSet &AVs) { … }

bool CopyGeneration::processBlock(MachineBasicBlock &B,
      const RegisterSet &AVs) { … }

bool CopyPropagation::isCopyReg(unsigned Opc, bool NoConv) { … }

bool CopyPropagation::propagateRegCopy(MachineInstr &MI) { … }

bool CopyPropagation::processBlock(MachineBasicBlock &B, const RegisterSet&) { … }

namespace {

// Recognize patterns that can be simplified and replace them with the
// simpler forms.
// This is by no means complete
  class BitSimplification : public Transformation { … };

} // end anonymous namespace

// Check if the bits [B..B+16) in register cell RC form a valid halfword,
// i.e. [0..16), [16..32), etc. of some register. If so, return true and
// set the information about the found register in RH.
bool BitSimplification::matchHalf(unsigned SelfR,
      const BitTracker::RegisterCell &RC, unsigned B, RegHalf &RH) { … }

bool BitSimplification::validateReg(BitTracker::RegisterRef R, unsigned Opc,
      unsigned OpNum) { … }

// Check if RC matches the pattern of a S2_packhl. If so, return true and
// set the inputs Rs and Rt.
bool BitSimplification::matchPackhl(unsigned SelfR,
      const BitTracker::RegisterCell &RC, BitTracker::RegisterRef &Rs,
      BitTracker::RegisterRef &Rt) { … }

unsigned BitSimplification::getCombineOpcode(bool HLow, bool LLow) { … }

// If MI stores the upper halfword of a register (potentially obtained via
// shifts or extracts), replace it with a storerf instruction. This could
// cause the "extraction" code to become dead.
bool BitSimplification::genStoreUpperHalf(MachineInstr *MI) { … }

// If MI stores a value known at compile-time, and the value is within a range
// that avoids using constant-extenders, replace it with a store-immediate.
bool BitSimplification::genStoreImmediate(MachineInstr *MI) { … }

// If MI is equivalent o S2_packhl, generate the S2_packhl. MI could be the
// last instruction in a sequence that results in something equivalent to
// the pack-halfwords. The intent is to cause the entire sequence to become
// dead.
bool BitSimplification::genPackhl(MachineInstr *MI,
      BitTracker::RegisterRef RD, const BitTracker::RegisterCell &RC) { … }

// If MI produces halfword of the input in the low half of the output,
// replace it with zero-extend or extractu.
bool BitSimplification::genExtractHalf(MachineInstr *MI,
      BitTracker::RegisterRef RD, const BitTracker::RegisterCell &RC) { … }

// If MI is equivalent to a combine(.L/.H, .L/.H) replace with with the
// combine.
bool BitSimplification::genCombineHalf(MachineInstr *MI,
      BitTracker::RegisterRef RD, const BitTracker::RegisterCell &RC) { … }

// If MI resets high bits of a register and keeps the lower ones, replace it
// with zero-extend byte/half, and-immediate, or extractu, as appropriate.
bool BitSimplification::genExtractLow(MachineInstr *MI,
      BitTracker::RegisterRef RD, const BitTracker::RegisterCell &RC) { … }

bool BitSimplification::genBitSplit(MachineInstr *MI,
      BitTracker::RegisterRef RD, const BitTracker::RegisterCell &RC,
      const RegisterSet &AVs) { … }

// Check for tstbit simplification opportunity, where the bit being checked
// can be tracked back to another register. For example:
//   %2 = S2_lsr_i_r  %1, 5
//   %3 = S2_tstbit_i %2, 0
// =>
//   %3 = S2_tstbit_i %1, 5
bool BitSimplification::simplifyTstbit(MachineInstr *MI,
      BitTracker::RegisterRef RD, const BitTracker::RegisterCell &RC) { … }

// Detect whether RD is a bitfield extract (sign- or zero-extended) of
// some register from the AVs set. Create a new corresponding instruction
// at the location of MI. The intent is to recognize situations where
// a sequence of instructions performs an operation that is equivalent to
// an extract operation, such as a shift left followed by a shift right.
bool BitSimplification::simplifyExtractLow(MachineInstr *MI,
      BitTracker::RegisterRef RD, const BitTracker::RegisterCell &RC,
      const RegisterSet &AVs) { … }

bool BitSimplification::simplifyRCmp0(MachineInstr *MI,
      BitTracker::RegisterRef RD) { … }

bool BitSimplification::processBlock(MachineBasicBlock &B,
      const RegisterSet &AVs) { … }

bool HexagonBitSimplify::runOnMachineFunction(MachineFunction &MF) { … }

// Recognize loops where the code at the end of the loop matches the code
// before the entry of the loop, and the matching code is such that is can
// be simplified. This pass relies on the bit simplification above and only
// prepares code in a way that can be handled by the bit simplifcation.
//
// This is the motivating testcase (and explanation):
//
// {
//   loop0(.LBB0_2, r1)      // %for.body.preheader
//   r5:4 = memd(r0++#8)
// }
// {
//   r3 = lsr(r4, #16)
//   r7:6 = combine(r5, r5)
// }
// {
//   r3 = insert(r5, #16, #16)
//   r7:6 = vlsrw(r7:6, #16)
// }
// .LBB0_2:
// {
//   memh(r2+#4) = r5
//   memh(r2+#6) = r6            # R6 is really R5.H
// }
// {
//   r2 = add(r2, #8)
//   memh(r2+#0) = r4
//   memh(r2+#2) = r3            # R3 is really R4.H
// }
// {
//   r5:4 = memd(r0++#8)
// }
// {                             # "Shuffling" code that sets up R3 and R6
//   r3 = lsr(r4, #16)           # so that their halves can be stored in the
//   r7:6 = combine(r5, r5)      # next iteration. This could be folded into
// }                             # the stores if the code was at the beginning
// {                             # of the loop iteration. Since the same code
//   r3 = insert(r5, #16, #16)   # precedes the loop, it can actually be moved
//   r7:6 = vlsrw(r7:6, #16)     # there.
// }:endloop0
//
//
// The outcome:
//
// {
//   loop0(.LBB0_2, r1)
//   r5:4 = memd(r0++#8)
// }
// .LBB0_2:
// {
//   memh(r2+#4) = r5
//   memh(r2+#6) = r5.h
// }
// {
//   r2 = add(r2, #8)
//   memh(r2+#0) = r4
//   memh(r2+#2) = r4.h
// }
// {
//   r5:4 = memd(r0++#8)
// }:endloop0

namespace llvm {

  FunctionPass *createHexagonLoopRescheduling();
  void initializeHexagonLoopReschedulingPass(PassRegistry&);

} // end namespace llvm

namespace {

  class HexagonLoopRescheduling : public MachineFunctionPass { … };

} // end anonymous namespace

char HexagonLoopRescheduling::ID = …;

INITIALIZE_PASS(…)

HexagonLoopRescheduling::PhiInfo::PhiInfo(MachineInstr &P,
      MachineBasicBlock &B) { … }

unsigned HexagonLoopRescheduling::getDefReg(const MachineInstr *MI) { … }

bool HexagonLoopRescheduling::isConst(unsigned Reg) const { … }

bool HexagonLoopRescheduling::isBitShuffle(const MachineInstr *MI,
      unsigned DefR) const { … }

bool HexagonLoopRescheduling::isStoreInput(const MachineInstr *MI,
      unsigned InpR) const { … }

bool HexagonLoopRescheduling::isShuffleOf(unsigned OutR, unsigned InpR) const { … }

bool HexagonLoopRescheduling::isSameShuffle(unsigned OutR1, unsigned InpR1,
      unsigned OutR2, unsigned &InpR2) const { … }

void HexagonLoopRescheduling::moveGroup(InstrGroup &G, MachineBasicBlock &LB,
      MachineBasicBlock &PB, MachineBasicBlock::iterator At, unsigned OldPhiR,
      unsigned NewPredR) { … }

bool HexagonLoopRescheduling::processLoop(LoopCand &C) { … }

bool HexagonLoopRescheduling::runOnMachineFunction(MachineFunction &MF) { … }

//===----------------------------------------------------------------------===//
//                         Public Constructor Functions
//===----------------------------------------------------------------------===//

FunctionPass *llvm::createHexagonLoopRescheduling() { … }

FunctionPass *llvm::createHexagonBitSimplify() { … }