M68kInstrInfo.cpp

Go to the documentation of this file.

//===-- M68kInstrInfo.cpp - M68k Instruction Information --------*- C++ -*-===//
//
// 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
//
//===----------------------------------------------------------------------===//
///
/// \file
/// This file contains the M68k declaration of the TargetInstrInfo class.
///
//===----------------------------------------------------------------------===//
 
#include "M68kInstrInfo.h"
 
#include "M68kInstrBuilder.h"
#include "M68kMachineFunction.h"
#include "M68kRegisterInfo.h"
#include "M68kTargetMachine.h"
#include "MCTargetDesc/M68kMCCodeEmitter.h"
#include "MCTargetDesc/M68kMCTargetDesc.h"
 
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/ScopeExit.h"
#include "llvm/CodeGen/LivePhysRegs.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineOperand.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGenTypes/MachineValueType.h"
#include "llvm/MC/TargetRegistry.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/Regex.h"
 
#include <functional>
 
using namespace llvm;
 
#define DEBUG_TYPE "M68k-instr-info"
 
#define GET_INSTRINFO_CTOR_DTOR
#include "M68kGenInstrInfo.inc"
 
// Pin the vtable to this file.
void M68kInstrInfo::anchor() {}
 
M68kInstrInfo::M68kInstrInfo(const M68kSubtarget &STI)
    : M68kGenInstrInfo(STI, RI, M68k::ADJCALLSTACKDOWN, M68k::ADJCALLSTACKUP, 0,
                       M68k::RET),
      Subtarget(STI), RI(STI) {}
 
static M68k::CondCode getCondFromBranchOpc(unsigned BrOpc) {
  switch (BrOpc) {
  default:
    return M68k::COND_INVALID;
  case M68k::Beq8:
    return M68k::COND_EQ;
  case M68k::Bne8:
    return M68k::COND_NE;
  case M68k::Blt8:
    return M68k::COND_LT;
  case M68k::Ble8:
    return M68k::COND_LE;
  case M68k::Bgt8:
    return M68k::COND_GT;
  case M68k::Bge8:
    return M68k::COND_GE;
  case M68k::Bcs8:
    return M68k::COND_CS;
  case M68k::Bls8:
    return M68k::COND_LS;
  case M68k::Bhi8:
    return M68k::COND_HI;
  case M68k::Bcc8:
    return M68k::COND_CC;
  case M68k::Bmi8:
    return M68k::COND_MI;
  case M68k::Bpl8:
    return M68k::COND_PL;
  case M68k::Bvs8:
    return M68k::COND_VS;
  case M68k::Bvc8:
    return M68k::COND_VC;
  }
}
 
bool M68kInstrInfo::AnalyzeBranchImpl(MachineBasicBlock &MBB,
                                      MachineBasicBlock *&TBB,
                                      MachineBasicBlock *&FBB,
                                      SmallVectorImpl<MachineOperand> &Cond,
                                      bool AllowModify) const {
 
  auto UncondBranch =
      std::pair<MachineBasicBlock::reverse_iterator, MachineBasicBlock *>{
          MBB.rend(), nullptr};
 
  // Erase any instructions if allowed at the end of the scope.
  std::vector<std::reference_wrapper<llvm::MachineInstr>> EraseList;
  llvm::scope_exit FinalizeOnReturn([&EraseList] {
    for (auto &Ref : EraseList)
      Ref.get().eraseFromParent();
  });
 
  // Start from the bottom of the block and work up, examining the
  // terminator instructions.
  for (auto iter = MBB.rbegin(); iter != MBB.rend(); iter = std::next(iter)) {
 
    unsigned Opcode = iter->getOpcode();
 
    if (iter->isDebugInstr())
      continue;
 
    // Working from the bottom, when we see a non-terminator instruction, we're
    // done.
    if (!isUnpredicatedTerminator(*iter))
      break;
 
    // A terminator that isn't a branch can't easily be handled by this
    // analysis.
    if (!iter->isBranch())
      return true;
 
    // Handle unconditional branches.
    if (Opcode == M68k::BRA8 || Opcode == M68k::BRA16) {
      if (!iter->getOperand(0).isMBB())
        return true;
      UncondBranch = {iter, iter->getOperand(0).getMBB()};
 
      // TBB is used to indicate the unconditional destination.
      TBB = UncondBranch.second;
 
      if (!AllowModify)
        continue;
 
      // If the block has any instructions after a JMP, erase them.
      EraseList.insert(EraseList.begin(), MBB.rbegin(), iter);
 
      Cond.clear();
      FBB = nullptr;
 
      // Erase the JMP if it's equivalent to a fall-through.
      if (MBB.isLayoutSuccessor(UncondBranch.second)) {
        TBB = nullptr;
        EraseList.push_back(*iter);
        UncondBranch = {MBB.rend(), nullptr};
      }
 
      continue;
    }
 
    // Handle conditional branches.
    auto BranchCode = M68k::GetCondFromBranchOpc(Opcode);
 
    // Can't handle indirect branch.
    if (BranchCode == M68k::COND_INVALID)
      return true;
 
    // In practice we should never have an undef CCR operand, if we do
    // abort here as we are not prepared to preserve the flag.
    // ??? Is this required?
    // if (iter->getOperand(1).isUndef())
    //   return true;
 
    // Working from the bottom, handle the first conditional branch.
    if (Cond.empty()) {
      if (!iter->getOperand(0).isMBB())
        return true;
      MachineBasicBlock *CondBranchTarget = iter->getOperand(0).getMBB();
 
      // If we see something like this:
      //
      //     bcc l1
      //     bra l2
      //     ...
      //   l1:
      //     ...
      //   l2:
      if (UncondBranch.first != MBB.rend()) {
 
        assert(std::next(UncondBranch.first) == iter && "Wrong block layout.");
 
        // And we are allowed to modify the block and the target block of the
        // conditional branch is the direct successor of this block:
        //
        //     bcc l1
        //     bra l2
        //   l1:
        //     ...
        //   l2:
        //
        // we change it to this if allowed:
        //
        //     bncc l2
        //   l1:
        //     ...
        //   l2:
        //
        // Which is a bit more efficient.
        if (AllowModify && MBB.isLayoutSuccessor(CondBranchTarget)) {
 
          BranchCode = GetOppositeBranchCondition(BranchCode);
          unsigned BNCC = GetCondBranchFromCond(BranchCode);
 
          BuildMI(MBB, *UncondBranch.first, MBB.rfindDebugLoc(iter), get(BNCC))
              .addMBB(UncondBranch.second);
 
          EraseList.push_back(*iter);
          EraseList.push_back(*UncondBranch.first);
 
          TBB = UncondBranch.second;
          FBB = nullptr;
          Cond.push_back(MachineOperand::CreateImm(BranchCode));
 
          // Otherwise preserve TBB, FBB and Cond as requested
        } else {
          TBB = CondBranchTarget;
          FBB = UncondBranch.second;
          Cond.push_back(MachineOperand::CreateImm(BranchCode));
        }
 
        UncondBranch = {MBB.rend(), nullptr};
        continue;
      }
 
      TBB = CondBranchTarget;
      FBB = nullptr;
      Cond.push_back(MachineOperand::CreateImm(BranchCode));
 
      continue;
    }
 
    // Handle subsequent conditional branches. Only handle the case where all
    // conditional branches branch to the same destination and their condition
    // opcodes fit one of the special multi-branch idioms.
    assert(Cond.size() == 1);
    assert(TBB);
 
    // If the conditions are the same, we can leave them alone.
    auto OldBranchCode = static_cast<M68k::CondCode>(Cond[0].getImm());
    if (!iter->getOperand(0).isMBB())
      return true;
    auto NewTBB = iter->getOperand(0).getMBB();
    if (OldBranchCode == BranchCode && TBB == NewTBB)
      continue;
 
    // If they differ we cannot do much here.
    return true;
  }
 
  return false;
}
 
bool M68kInstrInfo::analyzeBranch(MachineBasicBlock &MBB,
                                  MachineBasicBlock *&TBB,
                                  MachineBasicBlock *&FBB,
                                  SmallVectorImpl<MachineOperand> &Cond,
                                  bool AllowModify) const {
  return AnalyzeBranchImpl(MBB, TBB, FBB, Cond, AllowModify);
}
 
unsigned M68kInstrInfo::removeBranch(MachineBasicBlock &MBB,
                                     int *BytesRemoved) const {
  assert(!BytesRemoved && "code size not handled");
 
  MachineBasicBlock::iterator I = MBB.end();
  unsigned Count = 0;
 
  while (I != MBB.begin()) {
    --I;
    if (I->isDebugValue())
      continue;
    if (I->getOpcode() != M68k::BRA8 &&
        getCondFromBranchOpc(I->getOpcode()) == M68k::COND_INVALID)
      break;
    // Remove the branch.
    I->eraseFromParent();
    I = MBB.end();
    ++Count;
  }
 
  return Count;
}
 
unsigned M68kInstrInfo::insertBranch(
    MachineBasicBlock &MBB, MachineBasicBlock *TBB, MachineBasicBlock *FBB,
    ArrayRef<MachineOperand> Cond, const DebugLoc &DL, int *BytesAdded) const {
  // Shouldn't be a fall through.
  assert(TBB && "InsertBranch must not be told to insert a fallthrough");
  assert((Cond.size() == 1 || Cond.size() == 0) &&
         "M68k branch conditions have one component!");
  assert(!BytesAdded && "code size not handled");
 
  if (Cond.empty()) {
    // Unconditional branch?
    assert(!FBB && "Unconditional branch with multiple successors!");
    BuildMI(&MBB, DL, get(M68k::BRA8)).addMBB(TBB);
    return 1;
  }
 
  // If FBB is null, it is implied to be a fall-through block.
  bool FallThru = FBB == nullptr;
 
  // Conditional branch.
  unsigned Count = 0;
  M68k::CondCode CC = (M68k::CondCode)Cond[0].getImm();
  unsigned Opc = GetCondBranchFromCond(CC);
  BuildMI(&MBB, DL, get(Opc)).addMBB(TBB);
  ++Count;
  if (!FallThru) {
    // Two-way Conditional branch. Insert the second branch.
    BuildMI(&MBB, DL, get(M68k::BRA8)).addMBB(FBB);
    ++Count;
  }
  return Count;
}
 
void M68kInstrInfo::AddSExt(MachineBasicBlock &MBB,
                            MachineBasicBlock::iterator I, DebugLoc DL,
                            unsigned Reg, MVT From, MVT To) const {
  if (From == MVT::i8) {
    unsigned R = Reg;
    // EXT16 requires i16 register
    if (To == MVT::i32) {
      R = RI.getSubReg(Reg, M68k::MxSubRegIndex16Lo);
      assert(R && "No viable SUB register available");
    }
    BuildMI(MBB, I, DL, get(M68k::EXT16), R).addReg(R);
  }
 
  if (To == MVT::i32)
    BuildMI(MBB, I, DL, get(M68k::EXT32), Reg).addReg(Reg);
}
 
void M68kInstrInfo::AddZExt(MachineBasicBlock &MBB,
                            MachineBasicBlock::iterator I, DebugLoc DL,
                            unsigned Reg, MVT From, MVT To) const {
 
  // On pre-020 (16-bit bus) CPUs, SWAP -> CLR -> SWAP is faster than AND with
  // mask.
  if (!Subtarget.atLeastM68020() && From == MVT::i16 && To == MVT::i32 &&
      M68k::DR32RegClass.contains(Reg)) {
    unsigned SubReg = RI.getSubReg(Reg, M68k::MxSubRegIndex16Lo);
    BuildMI(MBB, I, DL, get(M68k::SWAP), Reg).addReg(Reg);
    BuildMI(MBB, I, DL, get(M68k::CLR16d), SubReg);
    BuildMI(MBB, I, DL, get(M68k::SWAP), Reg).addReg(Reg);
    return;
  }
 
  unsigned Mask, And;
  if (From == MVT::i8)
    Mask = 0xFF;
  else
    Mask = 0xFFFF;
 
  if (To == MVT::i16)
    And = M68k::AND16di;
  else // i32
    And = M68k::AND32di;
 
  // TODO use xor r,r to decrease size
  BuildMI(MBB, I, DL, get(And), Reg).addReg(Reg).addImm(Mask);
}
 
// Convert MOVI to the appropriate instruction (sequence) for setting
// the register to an immediate value.
bool M68kInstrInfo::ExpandMOVI(MachineInstrBuilder &MIB, MVT MVTSize) const {
  Register Reg = MIB->getOperand(0).getReg();
  int64_t Imm = MIB->getOperand(1).getImm();
 
  const auto *DR32 = RI.getRegClass(M68k::DR32RegClassID);
  const auto *AR32 = RI.getRegClass(M68k::AR32RegClassID);
  const auto *AR16 = RI.getRegClass(M68k::AR16RegClassID);
  bool IsAddressReg = AR16->contains(Reg) || AR32->contains(Reg);
 
  MachineBasicBlock &MBB = *MIB->getParent();
  DebugLoc DL = MIB->getDebugLoc();
 
  // We need to assign to the full register to make IV happy
  Register SReg =
      MVTSize == MVT::i32
          ? Reg
          : Register(RI.getMatchingMegaReg(Reg, IsAddressReg ? AR32 : DR32));
  assert(SReg && "No viable MEGA register available");
 
  LLVM_DEBUG(dbgs() << "Expand " << *MIB.getInstr() << " to ");
 
  if (Imm == 0) {
    buildClearRegister(Reg, MBB, MIB, DL);
    MachineInstr &NewMI = *std::prev((MachineBasicBlock::iterator)MIB);
    LLVM_DEBUG(dbgs() << NewMI << "\n");
    MIB->removeFromParent();
 
    // Sign extention doesn't matter if we only use the bottom 8 bits
  } else if (MVTSize == MVT::i8 ||
             (!IsAddressReg && Imm >= -128 && Imm <= 127)) {
    LLVM_DEBUG(dbgs() << "MOVEQ\n");
 
    MIB->setDesc(get(M68k::MOVQ));
    MIB->getOperand(0).setReg(SReg);
 
    // Counter the effects of sign-extension with a bitwise not.
    // This is only faster and smaller for 32 bit values.
  } else if (DR32->contains(Reg) && isUInt<8>(Imm)) {
    LLVM_DEBUG(dbgs() << "MOVEQ and NOT\n");
 
    unsigned SubReg = RI.getSubReg(Reg, M68k::MxSubRegIndex8Lo);
    assert(SubReg && "No viable SUB register available");
 
    BuildMI(MBB, MIB.getInstr(), DL, get(M68k::MOVQ), SReg).addImm(~Imm & 0xFF);
    BuildMI(MBB, MIB.getInstr(), DL, get(M68k::NOT8d), SubReg).addReg(SubReg);
 
    MIB->removeFromParent();
 
    // movea.w implicitly sign extends to the full register width,
    // so exploit that if the immediate fits in the correct range.
    //
    // TODO: use lea imm.w, %an for further constants when 16-bit
    // absolute addressing is implemented.
  } else if (AR32->contains(Reg) && isUInt<16>(Imm)) {
    LLVM_DEBUG(dbgs() << "MOVEA w/ implicit extend\n");
 
    unsigned SubReg = RI.getSubReg(Reg, M68k::MxSubRegIndex16Lo);
    assert(SubReg && "No viable SUB register available");
 
    MIB->setDesc(get(M68k::MOV16ai));
    MIB->getOperand(0).setReg(SubReg);
 
    // Fall back to a move with immediate
  } else {
    LLVM_DEBUG(dbgs() << "MOVE\n");
    MIB->setDesc(get(MVTSize == MVT::i16 ? M68k::MOV16ri : M68k::MOV32ri));
  }
 
  return true;
}
 
bool M68kInstrInfo::ExpandMOVX_RR(MachineInstrBuilder &MIB, MVT MVTDst,
                                  MVT MVTSrc) const {
  unsigned Move = MVTDst == MVT::i16 ? M68k::MOV16rr : M68k::MOV32rr;
  Register Dst = MIB->getOperand(0).getReg();
  Register Src = MIB->getOperand(1).getReg();
 
  assert(Dst != Src && "You cannot use the same Regs with MOVX_RR");
 
  const auto &TRI = getRegisterInfo();
 
  const auto *RCDst = TRI.getMaximalPhysRegClass(Dst, MVTDst);
  const auto *RCSrc = TRI.getMaximalPhysRegClass(Src, MVTSrc);
 
  assert(RCDst && RCSrc && "Wrong use of MOVX_RR");
  assert(RCDst != RCSrc && "You cannot use the same Reg Classes with MOVX_RR");
  (void)RCSrc;
 
  // We need to find the super source register that matches the size of Dst
  unsigned SSrc = RI.getMatchingMegaReg(Src, RCDst);
  assert(SSrc && "No viable MEGA register available");
 
  // If it happens to that super source register is the destination register
  // we do nothing
  if (Dst == SSrc) {
    LLVM_DEBUG(dbgs() << "Remove " << *MIB.getInstr() << '\n');
    MIB->eraseFromParent();
  } else { // otherwise we need to MOV
    LLVM_DEBUG(dbgs() << "Expand " << *MIB.getInstr() << " to MOV\n");
    MIB->setDesc(get(Move));
    MIB->getOperand(1).setReg(SSrc);
  }
 
  return true;
}
 
/// Expand SExt MOVE pseudos into a MOV and a EXT if the operands are two
/// different registers or just EXT if it is the same register
bool M68kInstrInfo::ExpandMOVSZX_RR(MachineInstrBuilder &MIB, bool IsSigned,
                                    MVT MVTDst, MVT MVTSrc) const {
  LLVM_DEBUG(dbgs() << "Expand " << *MIB.getInstr() << " to ");
 
  Register Dst = MIB->getOperand(0).getReg();
  Register Src = MIB->getOperand(1).getReg();
 
  assert(Dst != Src && "You cannot use the same Regs with MOVSX_RR");
 
  const auto &TRI = getRegisterInfo();
 
  const auto *RCDst = TRI.getMaximalPhysRegClass(Dst, MVTDst);
  const auto *RCSrc = TRI.getMaximalPhysRegClass(Src, MVTSrc);
 
  assert(RCDst && RCSrc && "Wrong use of MOVSX_RR");
  assert(RCDst != RCSrc && "You cannot use the same Reg Classes with MOVSX_RR");
  (void)RCSrc;
 
  // We need to find the super source register that matches the size of Dst
  unsigned SSrc = RI.getMatchingMegaReg(Src, RCDst);
  assert(SSrc && "No viable MEGA register available");
 
  MachineBasicBlock &MBB = *MIB->getParent();
  DebugLoc DL = MIB->getDebugLoc();
 
  // It's more efficient to clear the destination and *then* move, rather than
  // move and zext.
  if (Dst != SSrc && !IsSigned) {
    LLVM_DEBUG(dbgs() << "Clear and Move" << '\n');
 
    buildClearRegister(Dst, MBB, MIB.getInstr(), DL);
 
    if (MVTSrc == MVT::i8) {
      unsigned SubDst = RI.getSubReg(Dst, M68k::MxSubRegIndex8Lo);
      BuildMI(MBB, MIB.getInstr(), DL, get(M68k::MOV8dd), SubDst).addReg(Src);
    } else { // i16
      unsigned SubDst = RI.getSubReg(Dst, M68k::MxSubRegIndex16Lo);
      BuildMI(MBB, MIB.getInstr(), DL, get(M68k::MOV16dd), SubDst).addReg(Src);
    }
  } else {
 
    unsigned Move;
    if (MVTDst == MVT::i16)
      Move = M68k::MOV16dd;
    else // i32
      Move = M68k::MOV32dd;
 
    if (Dst != SSrc) {
      LLVM_DEBUG(dbgs() << "Move and " << '\n');
      BuildMI(MBB, MIB.getInstr(), DL, get(Move), Dst).addReg(SSrc);
    }
 
    if (IsSigned) {
      LLVM_DEBUG(dbgs() << "Sign Extend" << '\n');
      AddSExt(MBB, MIB.getInstr(), DL, Dst, MVTSrc, MVTDst);
    } else {
      LLVM_DEBUG(dbgs() << "Zero Extend" << '\n');
      AddZExt(MBB, MIB.getInstr(), DL, Dst, MVTSrc, MVTDst);
    }
  }
 
  MIB->eraseFromParent();
 
  return true;
}
 
bool M68kInstrInfo::ExpandMOVSZX_RM(MachineInstrBuilder &MIB, bool IsSigned,
                                    const MCInstrDesc &Desc, MVT MVTDst,
                                    MVT MVTSrc) const {
  LLVM_DEBUG(dbgs() << "Expand " << *MIB.getInstr() << " to ");
 
  Register Dst = MIB->getOperand(0).getReg();
 
  // We need the subreg of Dst to make instruction verifier happy because the
  // real machine instruction consumes and produces values of the same size and
  // the registers the will be used here fall into different classes and this
  // makes IV cry. We could use a bigger operation, but this will put some
  // pressure on cache and memory, so no.
  unsigned SubDst =
      RI.getSubReg(Dst, MVTSrc == MVT::i8 ? M68k::MxSubRegIndex8Lo
                                          : M68k::MxSubRegIndex16Lo);
  assert(SubDst && "No viable SUB register available");
 
  // Make this a plain move
  MIB->setDesc(Desc);
  MIB->getOperand(0).setReg(SubDst);
 
  MachineBasicBlock::iterator I = MIB.getInstr();
  MachineBasicBlock &MBB = *MIB->getParent();
  DebugLoc DL = MIB->getDebugLoc();
 
  // We can only clear before loading if the destination register isn't being
  // used as an index for the load.
  if (!IsSigned && !MIB->readsRegister(Dst, &RI)) {
    LLVM_DEBUG(dbgs() << "Clear and LOAD" << '\n');
    buildClearRegister(Dst, MBB, I, DL);
 
    // Extend after load
  } else {
    I++;
    if (IsSigned) {
      LLVM_DEBUG(dbgs() << "LOAD and Sign Extend" << '\n');
      AddSExt(MBB, I, DL, Dst, MVTSrc, MVTDst);
    } else {
      LLVM_DEBUG(dbgs() << "Zero Extend" << '\n');
      AddZExt(MBB, I, DL, Dst, MVTSrc, MVTDst);
    }
  }
 
  return true;
}
 
bool M68kInstrInfo::ExpandPUSH_POP(MachineInstrBuilder &MIB,
                                   const MCInstrDesc &Desc, bool IsPush) const {
  MachineBasicBlock::iterator I = MIB.getInstr();
  I++;
  MachineBasicBlock &MBB = *MIB->getParent();
  MachineOperand MO = MIB->getOperand(0);
  DebugLoc DL = MIB->getDebugLoc();
  if (IsPush)
    BuildMI(MBB, I, DL, Desc).addReg(RI.getStackRegister()).add(MO);
  else
    BuildMI(MBB, I, DL, Desc, MO.getReg()).addReg(RI.getStackRegister());
 
  MIB->eraseFromParent();
  return true;
}
 
bool M68kInstrInfo::ExpandMOVEM(MachineInstrBuilder &MIB,
                                const MCInstrDesc &Desc, bool IsRM) const {
  int Reg = 0, Offset = 0, Base = 0;
  auto DL = MIB->getDebugLoc();
  auto MI = MIB.getInstr();
  auto &MBB = *MIB->getParent();
 
  if (IsRM) {
    Reg = MIB->getOperand(0).getReg();
    Offset = MIB->getOperand(1).getImm();
    Base = MIB->getOperand(2).getReg();
  } else {
    Offset = MIB->getOperand(0).getImm();
    Base = MIB->getOperand(1).getReg();
    Reg = MIB->getOperand(2).getReg();
  }
 
  unsigned Mask = 1 << RI.getSpillRegisterOrder(Reg);
  if (IsRM) {
    BuildMI(MBB, MI, DL, Desc)
        .addImm(Mask)
        .addImm(Offset)
        .addReg(Base)
        .addReg(Reg, RegState::ImplicitDefine)
        .copyImplicitOps(*MIB);
  } else {
    BuildMI(MBB, MI, DL, Desc)
        .addImm(Offset)
        .addReg(Base)
        .addImm(Mask)
        .addReg(Reg, RegState::Implicit)
        .copyImplicitOps(*MIB);
  }
 
  MIB->eraseFromParent();
 
  return true;
}
 
void M68kInstrInfo::buildClearRegister(Register Reg, MachineBasicBlock &MBB,
                                       MachineBasicBlock::iterator Iter,
                                       DebugLoc &DL,
                                       bool AllowSideEffects) const {
  // Clear an address register by subtracting it from itself.
  if (M68k::AR32RegClass.contains(Reg)) {
    BuildMI(MBB, Iter, DL, get(M68k::SUB32ar), Reg)
        .addReg(Reg, RegState::Undef)
        .addReg(Reg, RegState::Undef);
    return;
  }
 
  if (M68k::DR8RegClass.contains(Reg))
    BuildMI(MBB, Iter, DL, get(M68k::CLR8d), Reg);
  else if (M68k::DR16RegClass.contains(Reg))
    BuildMI(MBB, Iter, DL, get(M68k::CLR16d), Reg);
  else if (M68k::DR32RegClass.contains(Reg))
    BuildMI(MBB, Iter, DL, get(M68k::MOVQ), Reg).addImm(0);
  else
    llvm::reportFatalInternalError(
        "buildClearRegister is not implemented for " + RI.getRegAsmName(Reg));
}
 
/// Expand a single-def pseudo instruction to a two-addr
/// instruction with two undef reads of the register being defined.
/// This is used for mapping:
///   %d0 = SETCS_C32d
/// to:
///   %d0 = SUBX32dd %d0<undef>, %d0<undef>
///
static bool Expand2AddrUndef(MachineInstrBuilder &MIB,
                             const MCInstrDesc &Desc) {
  assert(Desc.getNumOperands() == 3 && "Expected two-addr instruction.");
  Register Reg = MIB->getOperand(0).getReg();
  MIB->setDesc(Desc);
 
  // MachineInstr::addOperand() will insert explicit operands before any
  // implicit operands.
  MIB.addReg(Reg, RegState::Undef).addReg(Reg, RegState::Undef);
  // But we don't trust that.
  assert(MIB->getOperand(1).getReg() == Reg &&
         MIB->getOperand(2).getReg() == Reg && "Misplaced operand");
  return true;
}
 
bool M68kInstrInfo::expandPostRAPseudo(MachineInstr &MI) const {
  MachineInstrBuilder MIB(*MI.getParent()->getParent(), MI);
  switch (MI.getOpcode()) {
  case M68k::PUSH8d:
    return ExpandPUSH_POP(MIB, get(M68k::MOV8ed), true);
  case M68k::PUSH16d:
    return ExpandPUSH_POP(MIB, get(M68k::MOV16er), true);
  case M68k::PUSH32r:
    return ExpandPUSH_POP(MIB, get(M68k::MOV32er), true);
 
  case M68k::POP8d:
    return ExpandPUSH_POP(MIB, get(M68k::MOV8do), false);
  case M68k::POP16d:
    return ExpandPUSH_POP(MIB, get(M68k::MOV16ro), false);
  case M68k::POP32r:
    return ExpandPUSH_POP(MIB, get(M68k::MOV32ro), false);
 
  case M68k::SETCS_C8d:
    return Expand2AddrUndef(MIB, get(M68k::SUBX8dd));
  case M68k::SETCS_C16d:
    return Expand2AddrUndef(MIB, get(M68k::SUBX16dd));
  case M68k::SETCS_C32d:
    return Expand2AddrUndef(MIB, get(M68k::SUBX32dd));
  }
  return false;
}
 
bool M68kInstrInfo::isPCRelRegisterOperandLegal(const MachineInstr &MI,
                                                unsigned OpIdx) const {
  assert(MI.getOperand(OpIdx).isReg());
 
  // Check whether this operand belongs to an instruction with addressing mode
  // 'k', Refer to TargetInstrInfo.h for more information about this function.
 
  const unsigned NameIndices = M68kInstrNameIndices[MI.getOpcode()];
  StringRef InstrName(&M68kInstrNameData[NameIndices]);
 
  // If this machine operand is the 2nd operand, then check
  // whether the instruction has destination addressing mode 'k'.
  if (OpIdx == 1)
    return Regex("[A-Z]+(8|16|32)k[a-z](_TC)?$").match(InstrName);
 
  // If this machine operand is the last one, then check
  // whether the instruction has source addressing mode 'k'.
  if (OpIdx == MI.getNumExplicitOperands() - 1)
    return Regex("[A-Z]+(8|16|32)[a-z]k(_TC)?$").match(InstrName);
 
  return false;
}
 
void M68kInstrInfo::copyPhysReg(MachineBasicBlock &MBB,
                                MachineBasicBlock::iterator MI,
                                const DebugLoc &DL, Register DstReg,
                                Register SrcReg, bool KillSrc,
                                bool RenamableDest, bool RenamableSrc) const {
  unsigned Opc = 0;
  MachineFunction &MF = *MBB.getParent();
  const M68kSubtarget &STI = MF.getSubtarget<M68kSubtarget>();
 
  // Symmetric register copies
  if (M68k::XR32RegClass.contains(DstReg, SrcReg)) {
    Opc = M68k::MOV32rr;
  } else if (M68k::XR16RegClass.contains(DstReg, SrcReg)) {
    Opc = M68k::MOV16rr;
  } else if (M68k::DR8RegClass.contains(DstReg, SrcReg)) {
    Opc = M68k::MOV8dd;
  }
 
  // Asymmetric register copies
  // NOTE: There is no implicit sext/zext occurring during these moves, so the
  // upper bits will be undefined.
  // 8 -> 16
  else if (M68k::DR8RegClass.contains(SrcReg) &&
           M68k::XR16RegClass.contains(DstReg)) {
    Opc = M68k::MOVXd16d8;
    // 8 -> 32
  } else if (M68k::DR8RegClass.contains(SrcReg) &&
             M68k::XR32RegClass.contains(DstReg)) {
    Opc = M68k::MOVXd32d8;
    // 16 -> 32
  } else if (M68k::XR16RegClass.contains(SrcReg) &&
             M68k::XR32RegClass.contains(DstReg)) {
    Opc = M68k::MOVXd32d16;
  }
 
  // Copy from CCR
  // NOTE: M68000 uses MOVE from SR to copy from CCR, all other variants use
  // MOVE from CCR.
  else if (SrcReg == M68k::CCR) {
    if (M68k::DR8RegClass.contains(DstReg) ||
        M68k::DR16RegClass.contains(DstReg) ||
        M68k::DR32RegClass.contains(DstReg)) {
      Opc = STI.isM68000() ? M68k::MOV16ds : M68k::MOV16dc;
    } else {
      LLVM_DEBUG(dbgs() << "Cannot copy CCR to " << RI.getName(DstReg) << '\n');
      llvm_unreachable("Invalid register for MOVE from CCR");
    }
  }
 
  // Copy to CCR
  else if (DstReg == M68k::CCR) {
    if (M68k::DR8RegClass.contains(SrcReg) ||
        M68k::DR16RegClass.contains(SrcReg) ||
        M68k::DR32RegClass.contains(SrcReg)) {
      Opc = M68k::MOV16cd;
    } else {
      LLVM_DEBUG(dbgs() << "Cannot copy " << RI.getName(SrcReg) << " to CCR\n");
      llvm_unreachable("Invalid register for MOVE to CCR");
    }
  }
 
  // SR should never be a valid register for copying
  else if (SrcReg == M68k::SR || DstReg == M68k::SR)
    llvm_unreachable("Cannot explicitly copy to/from SR");
 
  // We should now have our opcode
  if (!Opc) {
    LLVM_DEBUG(dbgs() << "Cannot copy " << RI.getName(SrcReg) << " to "
                      << RI.getName(DstReg) << '\n');
    llvm_unreachable("Cannot emit physreg copy instruction");
  }
 
  // FIXME
  // Below is a workaround to prevent a live CCR from being killed by the COPY
  // instruction. LLVM sometimes inserts a COPY pseudo instruction between
  // compare and branch during MIR generation (e.g. during PHI node elimination)
  // without any idea that on M68k, this is extremely likely to implicitly kill
  // the CCR.
  // The workaround checks whether CCR is live during this copy, and if so,
  // backs up CCR and restores it after the copy. It's inefficient and prevents
  // M68000-targeted builds from running on 010+ (because 000 uses MOVE from SR
  // and 010+ uses MOVE from CCR).
  // The fix condition is to prevent COPY from ever being inserted while CCR is
  // live (which would also stop this workaround from ever triggering).
 
  unsigned CCRSrcReg = STI.isM68000() ? M68k::SR : M68k::CCR;
 
  // Get the live registers right before the COPY instruction. If CCR is
  // live, the MOVE is going to kill it, so we will need to preserve it.
  LiveRegUnits UsedRegs(RI);
  UsedRegs.addLiveOuts(MBB);
  auto InstUpToI = MBB.end();
  while (InstUpToI != MI) {
    UsedRegs.stepBackward(*--InstUpToI);
  }
 
  if (SrcReg == M68k::CCR) {
    BuildMI(MBB, MI, DL, get(Opc), DstReg).addReg(CCRSrcReg);
    return;
  }
  if (DstReg == M68k::CCR) {
    BuildMI(MBB, MI, DL, get(Opc), M68k::CCR)
        .addReg(SrcReg, getKillRegState(KillSrc));
    return;
  }
  if (UsedRegs.available(M68k::CCR)) {
    BuildMI(MBB, MI, DL, get(Opc), DstReg)
        .addReg(SrcReg, getKillRegState(KillSrc));
    return;
  }
 
  // CCR is live, so we must restore it after the copy. Prepare push/pop ops.
  // 68000 must use MOVE from SR, 68010+ must use MOVE from CCR. In either
  // case, upon moving back, MOVE to CCR will mask out the upper byte anyway.
 
  // Look for an available data register for the CCR, or push to stack if
  // there are none
  BitVector Allocatable =
      RI.getAllocatableSet(MF, RI.getRegClass(M68k::DR16RegClassID));
  for (Register Reg : Allocatable.set_bits()) {
    if (!RI.regsOverlap(DstReg, Reg) && (UsedRegs.available(Reg))) {
      unsigned CCRPushOp = STI.isM68000() ? M68k::MOV16ds : M68k::MOV16dc;
      unsigned CCRPopOp = M68k::MOV16cd;
      BuildMI(MBB, MI, DL, get(CCRPushOp), Reg).addReg(CCRSrcReg);
      BuildMI(MBB, MI, DL, get(Opc), DstReg)
          .addReg(SrcReg, getKillRegState(KillSrc));
      BuildMI(MBB, MI, DL, get(CCRPopOp), M68k::CCR).addReg(Reg);
      return;
    }
  }
 
  unsigned CCRPushOp = STI.isM68000() ? M68k::MOV16es : M68k::MOV16ec;
  unsigned CCRPopOp = M68k::MOV16co;
 
  BuildMI(MBB, MI, DL, get(CCRPushOp))
      .addReg(RI.getStackRegister())
      .addReg(CCRSrcReg);
  BuildMI(MBB, MI, DL, get(Opc), DstReg)
      .addReg(SrcReg, getKillRegState(KillSrc));
  BuildMI(MBB, MI, DL, get(CCRPopOp), M68k::CCR).addReg(RI.getStackRegister());
  return;
}
 
namespace {
unsigned getLoadStoreRegOpcode(unsigned Reg, const TargetRegisterClass *RC,
                               const TargetRegisterInfo *TRI,
                               const M68kSubtarget &STI, bool load) {
  switch (TRI->getSpillSize(*RC)) {
  default:
    LLVM_DEBUG(
        dbgs() << "Cannot determine appropriate opcode for load/store to/from "
               << TRI->getName(Reg) << " of class " << TRI->getRegClassName(RC)
               << " with spill size " << TRI->getSpillSize(*RC) << '\n');
    llvm_unreachable("Unknown spill size");
  case 2:
    if (M68k::XR16RegClass.hasSubClassEq(RC))
      return load ? M68k::MOVM16mp_P : M68k::MOVM16pm_P;
    if (M68k::DR8RegClass.hasSubClassEq(RC))
      return load ? M68k::MOVM8mp_P : M68k::MOVM8pm_P;
    if (M68k::CCRCRegClass.hasSubClassEq(RC))
      return load ? M68k::MOVM16mp_P : M68k::MOVM16pm_P;
    llvm_unreachable("Unknown 2-byte regclass");
  case 4:
    if (M68k::XR32RegClass.hasSubClassEq(RC))
      return load ? M68k::MOVM32mp_P : M68k::MOVM32pm_P;
    llvm_unreachable("Unknown 4-byte regclass");
  }
}
 
unsigned getStoreRegOpcode(unsigned SrcReg, const TargetRegisterClass *RC,
                           const TargetRegisterInfo *TRI,
                           const M68kSubtarget &STI) {
  return getLoadStoreRegOpcode(SrcReg, RC, TRI, STI, false);
}
 
unsigned getLoadRegOpcode(unsigned DstReg, const TargetRegisterClass *RC,
                          const TargetRegisterInfo *TRI,
                          const M68kSubtarget &STI) {
  return getLoadStoreRegOpcode(DstReg, RC, TRI, STI, true);
}
} // end anonymous namespace
 
bool M68kInstrInfo::getStackSlotRange(const TargetRegisterClass *RC,
                                      unsigned SubIdx, unsigned &Size,
                                      unsigned &Offset,
                                      const MachineFunction &MF) const {
  // The slot size must be the maximum size so we can easily use MOVEM.L
  Size = 4;
  Offset = 0;
  return true;
}
 
void M68kInstrInfo::storeRegToStackSlot(
    MachineBasicBlock &MBB, MachineBasicBlock::iterator MI, Register SrcReg,
    bool IsKill, int FrameIndex, const TargetRegisterClass *RC, Register VReg,
    MachineInstr::MIFlag Flags) const {
  const MachineFrameInfo &MFI = MBB.getParent()->getFrameInfo();
  assert(MFI.getObjectSize(FrameIndex) >= TRI.getSpillSize(*RC) &&
         "Stack slot is too small to store");
  (void)MFI;
 
  unsigned Opc = getStoreRegOpcode(SrcReg, RC, &TRI, Subtarget);
  DebugLoc DL = MBB.findDebugLoc(MI);
  // (0,FrameIndex) <- $reg
  M68k::addFrameReference(BuildMI(MBB, MI, DL, get(Opc)), FrameIndex)
      .addReg(SrcReg, getKillRegState(IsKill));
}
 
void M68kInstrInfo::loadRegFromStackSlot(MachineBasicBlock &MBB,
                                         MachineBasicBlock::iterator MI,
                                         Register DstReg, int FrameIndex,
                                         const TargetRegisterClass *RC,
                                         Register VReg, unsigned SubReg,
                                         MachineInstr::MIFlag Flags) const {
  const MachineFrameInfo &MFI = MBB.getParent()->getFrameInfo();
  assert(MFI.getObjectSize(FrameIndex) >= TRI.getSpillSize(*RC) &&
         "Stack slot is too small to load");
  (void)MFI;
 
  unsigned Opc = getLoadRegOpcode(DstReg, RC, &TRI, Subtarget);
  DebugLoc DL = MBB.findDebugLoc(MI);
  M68k::addFrameReference(BuildMI(MBB, MI, DL, get(Opc), DstReg), FrameIndex);
}
 
/// Return a virtual register initialized with the global base register
/// value. Output instructions required to initialize the register in the
/// function entry block, if necessary.
///
/// TODO Move this function to M68kMachineFunctionInfo.
unsigned M68kInstrInfo::getGlobalBaseReg(MachineFunction *MF) const {
  M68kMachineFunctionInfo *MxFI = MF->getInfo<M68kMachineFunctionInfo>();
  unsigned GlobalBaseReg = MxFI->getGlobalBaseReg();
  if (GlobalBaseReg != 0)
    return GlobalBaseReg;
 
  // Create the register. The code to initialize it is inserted later,
  // by the M68kGlobalBaseReg pass (below).
  //
  // NOTE
  // Normally M68k uses A5 register as global base pointer but this will
  // create unnecessary spill if we use less then 4 registers in code; since A5
  // is callee-save anyway we could try to allocate caller-save first and if
  // lucky get one, otherwise it does not really matter which callee-save to
  // use.
  MachineRegisterInfo &RegInfo = MF->getRegInfo();
  GlobalBaseReg = RegInfo.createVirtualRegister(&M68k::AR32_NOSPRegClass);
  MxFI->setGlobalBaseReg(GlobalBaseReg);
  return GlobalBaseReg;
}
 
std::pair<unsigned, unsigned>
M68kInstrInfo::decomposeMachineOperandsTargetFlags(unsigned TF) const {
  return std::make_pair(TF, 0u);
}
 
ArrayRef<std::pair<unsigned, const char *>>
M68kInstrInfo::getSerializableDirectMachineOperandTargetFlags() const {
  using namespace M68kII;
  static const std::pair<unsigned, const char *> TargetFlags[] = {
      {MO_ABSOLUTE_ADDRESS, "m68k-absolute"},
      {MO_PC_RELATIVE_ADDRESS, "m68k-pcrel"},
      {MO_GOT, "m68k-got"},
      {MO_GOTOFF, "m68k-gotoff"},
      {MO_GOTPCREL, "m68k-gotpcrel"},
      {MO_PLT, "m68k-plt"},
      {MO_TLSGD, "m68k-tlsgd"},
      {MO_TLSLD, "m68k-tlsld"},
      {MO_TLSLDM, "m68k-tlsldm"},
      {MO_TLSIE, "m68k-tlsie"},
      {MO_TLSLE, "m68k-tlsle"}};
  return ArrayRef(TargetFlags);
}
 
#undef DEBUG_TYPE
#define DEBUG_TYPE "m68k-create-global-base-reg"
 
#define PASS_NAME "M68k PIC Global Base Reg Initialization"
 
namespace {
/// This initializes the PIC global base register
struct M68kGlobalBaseReg : public MachineFunctionPass {
  static char ID;
  M68kGlobalBaseReg() : MachineFunctionPass(ID) {}
 
  bool runOnMachineFunction(MachineFunction &MF) override {
    const M68kSubtarget &STI = MF.getSubtarget<M68kSubtarget>();
    M68kMachineFunctionInfo *MxFI = MF.getInfo<M68kMachineFunctionInfo>();
 
    unsigned GlobalBaseReg = MxFI->getGlobalBaseReg();
 
    // If we didn't need a GlobalBaseReg, don't insert code.
    if (GlobalBaseReg == 0)
      return false;
 
    // Insert the set of GlobalBaseReg into the first MBB of the function
    MachineBasicBlock &FirstMBB = MF.front();
    MachineBasicBlock::iterator MBBI = FirstMBB.begin();
    DebugLoc DL = FirstMBB.findDebugLoc(MBBI);
    const M68kInstrInfo *TII = STI.getInstrInfo();
 
    // Generate lea (__GLOBAL_OFFSET_TABLE_,%PC), %A5
    BuildMI(FirstMBB, MBBI, DL, TII->get(M68k::LEA32q), GlobalBaseReg)
        .addExternalSymbol("_GLOBAL_OFFSET_TABLE_", M68kII::MO_GOTPCREL);
 
    return true;
  }
 
  void getAnalysisUsage(AnalysisUsage &AU) const override {
    AU.setPreservesCFG();
    MachineFunctionPass::getAnalysisUsage(AU);
  }
};
char M68kGlobalBaseReg::ID = 0;
} // namespace
 
INITIALIZE_PASS(M68kGlobalBaseReg, DEBUG_TYPE, PASS_NAME, false, false)
 
FunctionPass *llvm::createM68kGlobalBaseRegPass() {
  return new M68kGlobalBaseReg();
}