[Xtensa] Implement support for the BranchRelaxation

[arsenm]

Needs test coverage

llvm/lib/Target/Xtensa/XtensaInstrInfo.h

class XtensaInstrInfo : public XtensaGenInstrInfo {
   const XtensaRegisterInfo RI;
   XtensaSubtarget &STI;
 
 public:
   XtensaInstrInfo(XtensaSubtarget &STI);
 
   void adjustStackPtr(unsigned SP, int64_t Amount, MachineBasicBlock &MBB,
                       MachineBasicBlock::iterator I) const;
+  unsigned getInstSizeInBytes(const MachineInstr &MI) const override;
 
   // Return the XtensaRegisterInfo, which this class owns.
   const XtensaRegisterInfo &getRegisterInfo() const { return RI; }
 
   void copyPhysReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator MBBI,
                    const DebugLoc &DL, MCRegister DestReg, MCRegister SrcReg,
                    bool KillSrc) const override;
   void storeRegToStackSlot(MachineBasicBlock &MBB,
void getLoadStoreOpcodes(const TargetRegisterClass *RC, unsigned &LoadOpcode,
                            unsigned &StoreOpcode, int64_t offset) const;
 
   // Emit code before MBBI in MI to move immediate value Value into
   // physical register Reg.
   void loadImmediate(MachineBasicBlock &MBB, MachineBasicBlock::iterator MBBI,
                      unsigned *Reg, int64_t Value) const;
   bool
   reverseBranchCondition(SmallVectorImpl<MachineOperand> &Cond) const override;
+  MachineBasicBlock *getBranchDestBlock(const MachineInstr &MI) const override;
+
+  bool isBranchOffsetInRange(unsigned BranchOpc,
+                             int64_t BrOffset) const override;
   bool analyzeBranch(MachineBasicBlock &MBB, MachineBasicBlock *&TBB,
                      MachineBasicBlock *&FBB,
                      SmallVectorImpl<MachineOperand> &Cond,
                      bool AllowModify) const override;
   unsigned removeBranch(MachineBasicBlock &MBB,
                         int *BytesRemoved = nullptr) const override;
   unsigned insertBranch(MachineBasicBlock &MBB, MachineBasicBlock *TBB,
                         MachineBasicBlock *FBB, ArrayRef<MachineOperand> Cond,
                         const DebugLoc &DL,
                         int *BytesAdded = nullptr) const override;
-
+  void insertIndirectBranch(MachineBasicBlock &MBB, MachineBasicBlock &DestBB,
+                            MachineBasicBlock &RestoreBB, const DebugLoc &DL,
+                            int64_t BrOffset = 0,
+                            RegScavenger *RS = nullptr) const override;
   unsigned InsertBranchAtInst(MachineBasicBlock &MBB,
                               MachineBasicBlock::iterator I,
                               MachineBasicBlock *TBB,
                               ArrayRef<MachineOperand> Cond, const DebugLoc &DL,
                               int *BytesAdded) const;
-
+  unsigned InsertConstBranchAtInst(MachineBasicBlock &MBB, MachineInstr *I,
+                                   int64_t offset,
+                                   ArrayRef<MachineOperand> Cond, DebugLoc DL,
+                                   int *BytesAdded) const;
   // Return true if MI is a conditional or unconditional branch.
   // When returning true, set Cond to the mask of condition-code
   // values on which the instruction will branch, and set Target
   // to the operand that contains the branch target.  This target
   // can be a register or a basic block.
   bool isBranch(const MachineBasicBlock::iterator &MI,
                 SmallVectorImpl<MachineOperand> &Cond,
                 const MachineOperand *&Target) const;
 };
 } // end namespace llvm
 
 #endif /* LLVM_LIB_TARGET_XTENSA_XTENSAINSTRINFO_H */

llvm/lib/Target/Xtensa/XtensaInstrInfo.cpp

 //===- XtensaInstrInfo.cpp - Xtensa Instruction Information ---------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // 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 contains the Xtensa implementation of the TargetInstrInfo class.
 //
 //===----------------------------------------------------------------------===//
 
 #include "XtensaInstrInfo.h"
+#include "XtensaConstantPoolValue.h"
 #include "XtensaMachineFunctionInfo.h"
 #include "XtensaTargetMachine.h"
 #include "llvm/CodeGen/MachineConstantPool.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/CodeGen/RegisterScavenging.h"
 
 #define GET_INSTRINFO_CTOR_DTOR
 #include "XtensaGenInstrInfo.inc"
 
 using namespace llvm;
 
 static inline const MachineInstrBuilder &
 addFrameReference(const MachineInstrBuilder &MIB, int FI) {
if (Value >= -2048 && Value <= 2047) {
     BuildMI(MBB, MBBI, DL, get(Xtensa::L32R), *Reg).addConstantPoolIndex(Idx);
   } else {
     // use L32R to let assembler load immediate best
     // TODO replace to L32R
     llvm_unreachable("Unsupported load immediate value");
   }
 }
 
+unsigned XtensaInstrInfo::getInstSizeInBytes(const MachineInstr &MI) const {
+  switch (MI.getOpcode()) {
+  case TargetOpcode::INLINEASM: { // Inline Asm: Variable size.
+    const MachineFunction *MF = MI.getParent()->getParent();
+    const char *AsmStr = MI.getOperand(0).getSymbolName();
+    return getInlineAsmLength(AsmStr, *MF->getTarget().getMCAsmInfo());
+  }
+  default:
+    return MI.getDesc().getSize();
+  }
+}
+
 bool XtensaInstrInfo::reverseBranchCondition(
     SmallVectorImpl<MachineOperand> &Cond) const {
   assert(Cond.size() <= 4 && "Invalid branch condition!");
 
   switch (Cond[0].getImm()) {
   case Xtensa::BEQ:
     Cond[0].setImm(Xtensa::BNE);
     return false;
case Xtensa::BGEZ:
     Cond[0].setImm(Xtensa::BLTZ);
     return false;
 
   default:
     llvm_unreachable("Invalid branch condition!");
   }
 }
 
+MachineBasicBlock *
+XtensaInstrInfo::getBranchDestBlock(const MachineInstr &MI) const {
+  unsigned OpCode = MI.getOpcode();
+  switch (OpCode) {
+  case Xtensa::BR_JT:
+  case Xtensa::JX:
+    return nullptr;
+  case Xtensa::J:
+    return MI.getOperand(0).getMBB();
+  case Xtensa::BEQ:
+  case Xtensa::BNE:
+  case Xtensa::BLT:
+  case Xtensa::BLTU:
+  case Xtensa::BGE:
+  case Xtensa::BGEU:
+    return MI.getOperand(2).getMBB();
+
+  case Xtensa::BEQI:
+  case Xtensa::BNEI:
+  case Xtensa::BLTI:
+  case Xtensa::BLTUI:
+  case Xtensa::BGEI:
+  case Xtensa::BGEUI:
+    return MI.getOperand(2).getMBB();
+
+  case Xtensa::BEQZ:
+  case Xtensa::BNEZ:
+  case Xtensa::BLTZ:
+  case Xtensa::BGEZ:
+    return MI.getOperand(1).getMBB();
+
+  default:
+    llvm_unreachable("Unknown branch opcode");
+  }
+}
+
+bool XtensaInstrInfo::isBranchOffsetInRange(unsigned BranchOp,
+                                            int64_t BrOffset) const {
+  switch (BranchOp) {
+  case Xtensa::J:
+    BrOffset -= 4;
+    return isIntN(18, BrOffset);
+  case Xtensa::JX:
+    return true;
+  case Xtensa::BR_JT:
+    return true;
+  case Xtensa::BEQ:
+  case Xtensa::BNE:
+  case Xtensa::BLT:
+  case Xtensa::BLTU:
+  case Xtensa::BGE:
+  case Xtensa::BGEU:
+  case Xtensa::BEQI:
+  case Xtensa::BNEI:
+  case Xtensa::BLTI:
+  case Xtensa::BLTUI:
+  case Xtensa::BGEI:
+  case Xtensa::BGEUI:
+    BrOffset -= 4;
+    return isIntN(8, BrOffset);
+  case Xtensa::BEQZ:
+  case Xtensa::BNEZ:
+  case Xtensa::BLTZ:
+  case Xtensa::BGEZ:
+    BrOffset -= 4;
+    return isIntN(12, BrOffset);
+  default:
+    llvm_unreachable("Unknown branch opcode");
+  }
+}
+
 bool XtensaInstrInfo::analyzeBranch(MachineBasicBlock &MBB,
                                     MachineBasicBlock *&TBB,
                                     MachineBasicBlock *&FBB,
                                     SmallVectorImpl<MachineOperand> &Cond,
                                     bool AllowModify = false) const {
   // Most of the code and comments here are boilerplate.
 
   // Start from the bottom of the block and work up, examining the
if (BytesAdded)
       *BytesAdded += getInstSizeInBytes(MI);
     return Count;
   }
   // This function inserts the branch at the end of the MBB
   Count += InsertBranchAtInst(MBB, MBB.end(), TBB, Cond, DL, BytesAdded);
   return Count;
 }
 
+void XtensaInstrInfo::insertIndirectBranch(MachineBasicBlock &MBB,
+                                           MachineBasicBlock &DestBB,
+                                           MachineBasicBlock &RestoreBB,
+                                           const DebugLoc &DL, int64_t BrOffset,
+                                           RegScavenger *RS) const {
+  assert(RS && "RegScavenger required for long branching");
+  assert(MBB.empty() &&
+         "new block should be inserted for expanding unconditional branch");
+  assert(MBB.pred_size() == 1);
+
+  MachineFunction *MF = MBB.getParent();
+  MachineRegisterInfo &MRI = MF->getRegInfo();
+  MachineConstantPool *ConstantPool = MF->getConstantPool();
+
+  if (!isInt<32>(BrOffset))
+    report_fatal_error(
+        "Branch offsets outside of the signed 32-bit range not supported");
+  XtensaConstantPoolValue *C =
+      XtensaConstantPoolMBB::Create(MF->getFunction().getContext(), &DestBB, 0);
+  unsigned Idx = ConstantPool->getConstantPoolIndex(C, Align(4));
+
+  // FIXME: A virtual register must be used initially, as the register
+  // scavenger won't work with empty blocks (SIInstrInfo::insertIndirectBranch
+  // uses the same workaround).
+  Register ScratchReg = MRI.createVirtualRegister(&Xtensa::ARRegClass);
+  auto II = MBB.end();
+
+  MachineInstr &L32R = *BuildMI(MBB, II, DL, get(Xtensa::L32R), ScratchReg)
+                            .addConstantPoolIndex(Idx);
+  BuildMI(MBB, II, DL, get(Xtensa::JX)).addReg(ScratchReg, RegState::Kill);
+  RS->enterBasicBlockEnd(MBB);
+  unsigned Scav = RS->scavengeRegisterBackwards(Xtensa::ARRegClass,
+                                                L32R.getIterator(), false, 0);
+  MRI.replaceRegWith(ScratchReg, Scav);
+  MRI.clearVirtRegs();
+  RS->setRegUsed(Scav);
+}
+
+unsigned XtensaInstrInfo::InsertConstBranchAtInst(
+    MachineBasicBlock &MBB, MachineInstr *I, int64_t offset,
+    ArrayRef<MachineOperand> Cond, DebugLoc DL, int *BytesAdded) const {
+  // Shouldn't be a fall through.
+  assert(&MBB && "InsertBranch must not be told to insert a fallthrough");
+  assert(Cond.size() <= 4 &&
+         "Xtensa branch conditions have less than four components!");
+
+  if (Cond.empty() || (Cond[0].getImm() == Xtensa::J)) {
+    // Unconditional branch
+    MachineInstr *MI = BuildMI(MBB, I, DL, get(Xtensa::J)).addImm(offset);
+    if (BytesAdded && MI)
+      *BytesAdded += getInstSizeInBytes(*MI);
+    return 1;
+  }
+
+  unsigned Count = 0;
+  unsigned BR_C = Cond[0].getImm();
+  MachineInstr *MI = nullptr;
+  switch (BR_C) {
+  case Xtensa::BEQ:
+  case Xtensa::BNE:
+  case Xtensa::BLT:
+  case Xtensa::BLTU:
+  case Xtensa::BGE:
+  case Xtensa::BGEU:
+    MI = BuildMI(MBB, I, DL, get(BR_C))
+             .addImm(offset)
+             .addReg(Cond[1].getReg())
+             .addReg(Cond[2].getReg());
+    break;
+  case Xtensa::BEQI:
+  case Xtensa::BNEI:
+  case Xtensa::BLTI:
+  case Xtensa::BLTUI:
+  case Xtensa::BGEI:
+  case Xtensa::BGEUI:
+    MI = BuildMI(MBB, I, DL, get(BR_C))
+             .addImm(offset)
+             .addReg(Cond[1].getReg())
+             .addImm(Cond[2].getImm());
+    break;
+  case Xtensa::BEQZ:
+  case Xtensa::BNEZ:
+  case Xtensa::BLTZ:
+  case Xtensa::BGEZ:
+    MI = BuildMI(MBB, I, DL, get(BR_C)).addImm(offset).addReg(Cond[1].getReg());
+    break;
+  default:
+    llvm_unreachable("Invalid branch type!");
+  }
+  if (BytesAdded && MI)
+    *BytesAdded += getInstSizeInBytes(*MI);
+  ++Count;
+  return Count;
+}
+
 unsigned XtensaInstrInfo::InsertBranchAtInst(MachineBasicBlock &MBB,
                                              MachineBasicBlock::iterator I,
                                              MachineBasicBlock *TBB,
                                              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");

llvm/lib/Target/Xtensa/XtensaRegisterInfo.h

public:
   bool requiresRegisterScavenging(const MachineFunction &MF) const override {
     return true;
   }
 
   bool requiresFrameIndexScavenging(const MachineFunction &MF) const override {
     return true;
   }
 
+  bool trackLivenessAfterRegAlloc(const MachineFunction &) const override {
+    return true;
+  }
+
   const uint16_t *
   getCalleeSavedRegs(const MachineFunction *MF = 0) const override;
   const uint32_t *getCallPreservedMask(const MachineFunction &MF,
                                        CallingConv::ID) const override;
   BitVector getReservedRegs(const MachineFunction &MF) const override;
   bool eliminateFrameIndex(MachineBasicBlock::iterator MI, int SPAdj,
                            unsigned FIOperandNum,
                            RegScavenger *RS = nullptr) const override;

llvm/lib/Target/Xtensa/XtensaTargetMachine.cpp

public:
   XtensaPassConfig(XtensaTargetMachine &TM, PassManagerBase &PM)
       : TargetPassConfig(TM, PM) {}
 
   XtensaTargetMachine &getXtensaTargetMachine() const {
      return getTM<XtensaTargetMachine>();
   }
 
   bool addInstSelector() override;
+  void addPreEmitPass() override;
 };
 } // end anonymous namespace
 
 bool XtensaPassConfig::addInstSelector() {
   addPass(createXtensaISelDag(getXtensaTargetMachine(), getOptLevel()));
   return false;
 }
 
+void XtensaPassConfig::addPreEmitPass() { addPass(&BranchRelaxationPassID); }
+
 TargetPassConfig *XtensaTargetMachine::createPassConfig(PassManagerBase &PM) {
   return new XtensaPassConfig(*this, PM);
 }