[MIPS] Initial support for MIPS-I load delay slots

[impiaaa]

Summary

LLVM so far has only supported the MIPS-II and above architectures. MIPS-II is pretty close to MIPS-I, the major difference
being that "load" instructions always take one extra instruction slot to propogate to registers. This patch adds support for
MIPS-I by adding hazard handling for load delay slots, alongside MIPSR6 forbidden slots and FPU slots, inserting a NOP
instruction between a load and any instruction immediately following that reads the load's destination register. I also
included a simple regression test. Since no existing tests target MIPS-I, those all still pass.

Issue ref: https://github.com/simias/psx-sdk-rs/issues/1

I also tested by building a simple demo app with Clang and running it in an emulator.

[djtodoro]

Hi @impiaaa, thanks for working on this!
Since this is an initial support, I was wondering is there a clear set of TODOs that need to be done?

llvm/lib/Target/Mips/MipsBranchExpansion.cpp

893

nit: . at the end of the comment

899–901

is this clang-formatted?

llvm/lib/Target/Mips/MipsInstrInfo.cpp

599–611

a comment describing the predicate?

[ayrtonm]

I believe it's only marked as initial because of the lack of MIPS-I tests. We assumed we'd have to follow up by porting over the relevant MIPS-II tests. I've also done a fair amount of testing with rustc on emulators and the change works as expected. The only other issue I've found with MIPS-I is that occasionally it'll try emitting a MIPS-II sync that crashes rustc.

[sdardis]

Hi @impiaaa, thanks for looking this.

I've highlighted a few minor things that can be improved.

@djtodoro:

I was wondering is there a clear set of TODOs that need to be done?

I believe one issue that needs addressed is that the MipsAsmParser would need to be extended in the case of .set reorder being active, as loads would need to be padded with no-ops. Unfortunately when that directive is active nops need to be added after each load as there is no look-ahead.

llvm/lib/Target/Mips/MipsBranchExpansion.cpp

40

Minor nit: 'load slots' -> 'load delay slots'.

807

STI->hasMips2() is enough here.

llvm/lib/Target/Mips/MipsInstrInfo.cpp

605

May I suggest:

return !llvm::any_of(LoadMI.defs(), [&](const MachineOperand &Op) {                             
  return Op.isReg() && MIInSlot.readsRegister(Op.getReg());                                     
});

llvm/lib/Target/Mips/MipsSubtarget.cpp

100

Add an empty line before the comment to maintain the style used in the file.

llvm/test/CodeGen/Mips/mips1-load-delay.ll

2

You can use the script in llvm/utils/update_llc_test_checks.py to produce the test checks. This is somewhat easier that writing tests by hand.

Remove the 'CHECK' prefixes here, the script will complain if two RUN lines have the same prefixes. As there will only one CHECK prefix, you can change '-check-prefixes' to '-check-prefix'.

You should also add a RUN line with '-mcpu=mips32r2' to add a case where the generate code is not MIPS-I or II.

8

You'll need to remove the 'undef' from each the argument attributes, the update_llc_test_checks.py will complain otherwise.

[impiaaa]

[MIPS] Initial support for MIPS-I load delay slots
Style fixes and comments from review.

[impiaaa]

In D122427#3407722, @djtodoro wrote:

Since this is an initial support, I was wondering is there a clear set of TODOs that need to be done?

I don't actually know right now. I assumed that this is all that was needed for MIPS-I support. I only added the warning in because I hadn't tested on hardware. I'll try to find if there are any other differences between MIPS-I and MIPS-II.

In D122427#3409287, @sdardis wrote:

I believe one issue that needs addressed is that the MipsAsmParser would need to be extended in the case of .set reorder being active, as loads would need to be padded with no-ops. Unfortunately when that directive is active nops need to be added after each load as there is no look-ahead.

Should that be a follow-up patch, or included in this one?

llvm/lib/Target/Mips/MipsBranchExpansion.cpp

899–901

Yes.

llvm/test/CodeGen/Mips/mips1-load-delay.ll

2

Is there documentation somewhere on how to get the most out of update_llc_test_checks? I tried running it with this test and it generated assertions for 3 nearly-identical copies of all 28 lines of compiled code, which, in my opinion, is harder to read than assertions that call out the difference.

[sdardis]

Should that be a follow-up patch, or included in this one?

It should be a follow up patch.

Is there documentation somewhere on how to get the most out of update_llc_test_checks?

There is some documentation in llvm/doc/TestingGuide.rst, but there's no option to common up the checks. This test case does look small enough that it should be ok.

[impiaaa]

I'll try to find if there are any other differences between MIPS-I and MIPS-II.

Ok, I did some research. Here are the differences that I can find between MIPS-I and MIPS-II:

1. Delayed loads: Done.
2. "Branch likely" instructions: As far as I can tell, these are currently never emitted.
3. Atomic update: These instructions also do not appear to be emitted.
4. sync: As @ayrtonm discovered, this instruction can be emitted from atomic loads and stores. It is lowered from the FENCE higher-level instruction. I have a patch ready that expands it to a libcall instead on MIPS-I.
5. 64-bit coprocessor transfers: Emitted in MipsFastISel::emitLoad, MipsFastISel::emitStore, MipsInstructionSelector::selectLoadStoreOpCode, MipsSEInstrInfo::loadRegFromStack, and MipsSEInstrInfo::storeRegToStack. They can currently be expanded to two single-word transfers with -mno-ldc1-sdc1. This option should be set automatically when MIPS-I is selected, or rather a hasMips2 check should be added everywhere that NoDPLoadStore is also checked.
6. Trap-on-condition: Emitted in MipsFastISel::selectDivRem, and MipsISelLowering.cpp insertDivByZeroTrap for checking for dividing by zero. The checks could be expanded to separate branch and break instructions. They can also currently be disabled entirely with -mno-check-zero-division.
7. Native directed rounding of floating-point to fixed-point: trunc_w is emitted in MipsFastISel::selectFPToInt, and MipsInstructionSelector::select. MipsAsmParser::expandTrunc already has code to expand the trunc_w pseudoinstruction, but I don't know if it's used by the assembler.
8. Floating-point square root: Emitted when -ffast-math is on. I haven't figured out yet where the code makes the decision how to lower the square-root intrinsic—there are other targets that do not have a native square-root instruction that properly expand it to a libcall.

There is some documentation in llvm/doc/TestingGuide.rst, but there's no option to common up the checks. This test case does look small enough that it should be ok.

Now I see that most of the tests in this directory only test the positive case, not both the positive and negative cases like I did. For future tests I'll do that instead.

[impiaaa]

Add mips32r2 to architectures tested by mips1-load-delay.ll

[sdardis]

LGTM. Do you have commit access?

[impiaaa]

I do not.

[sdardis]

Ok, I'll see about committing this tomorrow.

[impiaaa]

Thank you!

[sdardis]

Thank you for the patch.

llvm/lib/Target/Mips/MipsBranchExpansion.cpp

 /// to fit into its immediate field, it has to be expanded to another
 /// instruction or series of instructions.
 ///
 /// FIXME: Fix pc-region jump instructions which cross 256MB segment boundaries.
 /// TODO: Handle out of range bc, b (pseudo) instructions.
 ///
 /// Regarding compact branch hazard prevention:
 ///
-/// Hazards handled: forbidden slots for MIPSR6, FPU slots for MIPS3 and below.
+/// Hazards handled: forbidden slots for MIPSR6, FPU slots for MIPS3 and below,
+/// load delay slots for MIPS1.
 ///
 /// A forbidden slot hazard occurs when a compact branch instruction is executed
 /// and the adjacent instruction in memory is a control transfer instruction
 /// such as a branch or jump, ERET, ERETNC, DERET, WAIT and PAUSE.
 ///
 /// For example:
 ///
 /// 0x8004      bnec    a1,v0,<P+0x18>
void replaceBranch(MachineBasicBlock &MBB, Iter Br, const DebugLoc &DL,
                      MachineBasicBlock *MBBOpnd);
   bool buildProperJumpMI(MachineBasicBlock *MBB,
                          MachineBasicBlock::iterator Pos, DebugLoc DL);
   void expandToLongBranch(MBBInfo &Info);
   template <typename Pred, typename Safe>
   bool handleSlot(Pred Predicate, Safe SafeInSlot);
   bool handleForbiddenSlot();
   bool handleFPUDelaySlot();
+  bool handleLoadDelaySlot();
   bool handlePossibleLongBranch();
 
   const MipsSubtarget *STI;
   const MipsInstrInfo *TII;
 
   MachineFunction *MFp;
   SmallVector<MBBInfo, 16> MBBInfos;
   bool IsPIC;
for (Iter I = FI->begin(); I != FI->end(); ++I) {
           std::next(I) == FI->end() && std::next(FI) == MFp->end();
       if (!LastInstInFunction) {
         std::pair<Iter, bool> Res = getNextMachineInstr(std::next(I), &*FI);
         LastInstInFunction |= Res.second;
         IInSlot = Res.first;
       }
 
       if (LastInstInFunction || !SafeInSlot(*IInSlot, *I)) {
-
         MachineBasicBlock::instr_iterator Iit = I->getIterator();
         if (std::next(Iit) == FI->end() ||
             std::next(Iit)->getOpcode() != Mips::NOP) {
           Changed = true;
           MIBundleBuilder(&*I).append(
               BuildMI(*MFp, I->getDebugLoc(), TII->get(Mips::NOP)));
           NumInsertedNops++;
         }
if (STI->hasMips32() || STI->hasMips4())
     return false;
 
   return handleSlot([this](auto &I) -> bool { return TII->HasFPUDelaySlot(I); },
                     [this](auto &IInSlot, auto &I) -> bool {
                       return TII->SafeInFPUDelaySlot(IInSlot, I);
                     });
 }
 
+bool MipsBranchExpansion::handleLoadDelaySlot() {
+  // Load delay slot hazards are only for MIPS1.
+  if (STI->hasMips2())
+    return false;
+
+  return handleSlot(
+      [this](auto &I) -> bool { return TII->HasLoadDelaySlot(I); },
+      [this](auto &IInSlot, auto &I) -> bool {
+        return TII->SafeInLoadDelaySlot(IInSlot, I);
+      });
+}
+
 bool MipsBranchExpansion::handlePossibleLongBranch() {
   if (STI->inMips16Mode() || !STI->enableLongBranchPass())
     return false;
 
   if (SkipLongBranch)
     return false;
 
   bool EverMadeChange = false, MadeChange = true;
bool MipsBranchExpansion::runOnMachineFunction(MachineFunction &MF) {
 
   if (IsPIC && ABI.IsO32() &&
       MF.getInfo<MipsFunctionInfo>()->globalBaseRegSet())
     emitGPDisp(MF, TII);
 
   MFp = &MF;
 
   ForceLongBranchFirstPass = ForceLongBranch;
-  // Run these two at least once
+  // Run these at least once.
   bool longBranchChanged = handlePossibleLongBranch();
   bool forbiddenSlotChanged = handleForbiddenSlot();
   bool fpuDelaySlotChanged = handleFPUDelaySlot();
+  bool loadDelaySlotChanged = handleLoadDelaySlot();
 
-  bool Changed =
-      longBranchChanged || forbiddenSlotChanged || fpuDelaySlotChanged;
+  bool Changed = longBranchChanged || forbiddenSlotChanged ||
+                 fpuDelaySlotChanged || loadDelaySlotChanged;
 
-  // Then run them alternatively while there are changes
+  // Then run them alternatively while there are changes.
   while (forbiddenSlotChanged) {
     longBranchChanged = handlePossibleLongBranch();
     fpuDelaySlotChanged = handleFPUDelaySlot();
-    if (!longBranchChanged && !fpuDelaySlotChanged)
+    loadDelaySlotChanged = handleLoadDelaySlot();
+    if (!longBranchChanged && !fpuDelaySlotChanged && !loadDelaySlotChanged)
       break;
     forbiddenSlotChanged = handleForbiddenSlot();
   }
 
   return Changed;
 }

llvm/lib/Target/Mips/MipsInstrInfo.h

public:
 
   /// Predicate to determine if an instruction can go in a forbidden slot.
   bool SafeInForbiddenSlot(const MachineInstr &MI) const;
 
   /// Predicate to determine if an instruction can go in an FPU delay slot.
   bool SafeInFPUDelaySlot(const MachineInstr &MIInSlot,
                           const MachineInstr &FPUMI) const;
 
+  /// Predicate to determine if an instruction can go in a load delay slot.
+  bool SafeInLoadDelaySlot(const MachineInstr &MIInSlot,
+                           const MachineInstr &LoadMI) const;
+
   /// Predicate to determine if an instruction has a forbidden slot.
   bool HasForbiddenSlot(const MachineInstr &MI) const;
 
   /// Predicate to determine if an instruction has an FPU delay slot.
   bool HasFPUDelaySlot(const MachineInstr &MI) const;
 
+  /// Predicate to determine if an instruction has a load delay slot.
+  bool HasLoadDelaySlot(const MachineInstr &MI) const;
+
   /// Insert nop instruction when hazard condition is found
   void insertNoop(MachineBasicBlock &MBB,
                   MachineBasicBlock::iterator MI) const override;
 
   /// getRegisterInfo - TargetInstrInfo is a superset of MRegister info.  As
   /// such, whenever a client has an instance of instruction info, it should
   /// always be able to get register info as well (through this method).
   virtual const MipsRegisterInfo &getRegisterInfo() const = 0;

llvm/lib/Target/Mips/MipsInstrInfo.cpp

for (const MachineOperand &Op : FPUMI.defs()) {
     std::tie(Reads, Writes) = MIInSlot.readsWritesVirtualRegister(Op.getReg());
 
     if (Reads || Writes)
       return false;
   }
 
   return true;
 }
 
+/// Predicate for distinguishing instructions that are hazardous in a load delay
+/// slot. Consider inline assembly as unsafe as well.
+bool MipsInstrInfo::SafeInLoadDelaySlot(const MachineInstr &MIInSlot,
+                                        const MachineInstr &LoadMI) const {
+  if (MIInSlot.isInlineAsm())
+    return false;
+
+  return !llvm::any_of(LoadMI.defs(), [&](const MachineOperand &Op) {
+    return Op.isReg() && MIInSlot.readsRegister(Op.getReg());
+  });
+}
+
 /// Predicate for distingushing instructions that have forbidden slots.
 bool MipsInstrInfo::HasForbiddenSlot(const MachineInstr &MI) const {
   return (MI.getDesc().TSFlags & MipsII::HasForbiddenSlot) != 0;
 }
 
 /// Predicate for distingushing instructions that have FPU delay slots.
 bool MipsInstrInfo::HasFPUDelaySlot(const MachineInstr &MI) const {
   switch (MI.getOpcode()) {
   case Mips::MTC1:
   case Mips::MFC1:
   case Mips::MTC1_D64:
   case Mips::MFC1_D64:
   case Mips::DMTC1:
   case Mips::DMFC1:
   case Mips::FCMP_S32:
   case Mips::FCMP_D32:
   case Mips::FCMP_D64:
     return true;
 
   default:
     return false;
   }
 }
 
+/// Predicate for distingushing instructions that have load delay slots.
+bool MipsInstrInfo::HasLoadDelaySlot(const MachineInstr &MI) const {
+  switch (MI.getOpcode()) {
+  case Mips::LB:
+  case Mips::LBu:
+  case Mips::LH:
+  case Mips::LHu:
+  case Mips::LW:
+  case Mips::LWR:
+  case Mips::LWL:
+    return true;
+  default:
+    return false;
+  }
+}
+
 /// Return the number of bytes of code the specified instruction may be.
 unsigned MipsInstrInfo::getInstSizeInBytes(const MachineInstr &MI) const {
   switch (MI.getOpcode()) {
   default:
     return MI.getDesc().getSize();
   case  TargetOpcode::INLINEASM:
   case  TargetOpcode::INLINEASM_BR: {       // Inline Asm: Variable size.
     const MachineFunction *MF = MI.getParent()->getParent();

llvm/lib/Target/Mips/MipsSubtarget.h

class MipsSubtarget : public MipsGenSubtargetInfo {
   static bool MSAWarningPrinted;
 
   // Used to avoid printing crc warnings multiple times.
   static bool CRCWarningPrinted;
 
   // Used to avoid printing ginv warnings multiple times.
   static bool GINVWarningPrinted;
 
+  // Used to avoid printing Mips1 warnings multiple times.
+  static bool MIPS1WarningPrinted;
+
   // Used to avoid printing virt warnings multiple times.
   static bool VirtWarningPrinted;
 
   // Mips architecture version
   MipsArchEnum MipsArchVersion;
 
   // Processor implementation (unused but required to exist by
   // tablegen-erated code).

llvm/lib/Target/Mips/MipsSubtarget.cpp

static cl::opt<bool>
     GPOpt("mgpopt", cl::Hidden,
           cl::desc("Enable gp-relative addressing of mips small data items"));
 
 bool MipsSubtarget::DspWarningPrinted = false;
 bool MipsSubtarget::MSAWarningPrinted = false;
 bool MipsSubtarget::VirtWarningPrinted = false;
 bool MipsSubtarget::CRCWarningPrinted = false;
 bool MipsSubtarget::GINVWarningPrinted = false;
+bool MipsSubtarget::MIPS1WarningPrinted = false;
 
 void MipsSubtarget::anchor() {}
 
 MipsSubtarget::MipsSubtarget(const Triple &TT, StringRef CPU, StringRef FS,
                              bool little, const MipsTargetMachine &TM,
                              MaybeAlign StackAlignOverride)
     : MipsGenSubtargetInfo(TT, CPU, /*TuneCPU*/ CPU, FS),
       MipsArchVersion(MipsDefault), IsLittle(little), IsSoftFloat(false),
: MipsGenSubtargetInfo(TT, CPU, /*TuneCPU*/ CPU, FS),
       TSInfo(), InstrInfo(MipsInstrInfo::create(
                     initializeSubtargetDependencies(CPU, FS, TM))),
       FrameLowering(MipsFrameLowering::create(*this)),
       TLInfo(MipsTargetLowering::create(TM, *this)) {
 
   if (MipsArchVersion == MipsDefault)
     MipsArchVersion = Mips32;
 
-  // Don't even attempt to generate code for MIPS-I and MIPS-V. They have not
-  // been tested and currently exist for the integrated assembler only.
-  if (MipsArchVersion == Mips1)
-    report_fatal_error("Code generation for MIPS-I is not implemented", false);
+  // MIPS-I has not been tested.
+  if (MipsArchVersion == Mips1 && !MIPS1WarningPrinted) {
+    errs() << "warning: MIPS-I support is experimental\n";
+    MIPS1WarningPrinted = true;
+  }
+
+  // Don't even attempt to generate code for MIPS-V. It has not
+  // been tested and currently exists for the integrated assembler only.
   if (MipsArchVersion == Mips5)
     report_fatal_error("Code generation for MIPS-V is not implemented", false);
 
   // Check if Architecture and ABI are compatible.
   assert(((!isGP64bit() && isABI_O32()) ||
           (isGP64bit() && (isABI_N32() || isABI_N64()))) &&
          "Invalid  Arch & ABI pair.");
 

llvm/test/CodeGen/Mips/cpus.ll

 ; Check that the CPU names work.
 
 ; RUN: llc -mtriple=mips -mcpu=generic -filetype=obj < %s \
 ; RUN:   | llvm-readelf -A - | FileCheck %s --check-prefix=GENERIC
 ; GENERIC: ISA: MIPS32
 
+; RUN: llc -mtriple=mips -mcpu=mips1 -filetype=obj < %s \
+; RUN:   | llvm-readelf -A - | FileCheck %s --check-prefix=MIPS1
+; MIPS1: ISA: MIPS1
 ; RUN: llc -mtriple=mips -mcpu=mips2 -filetype=obj < %s \
 ; RUN:   | llvm-readelf -A - | FileCheck %s --check-prefix=MIPS2
 ; MIPS2: ISA: MIPS2
 ; RUN: llc -mtriple=mips64 -mcpu=mips3 -filetype=obj < %s \
 ; RUN:   | llvm-readelf -A - | FileCheck %s --check-prefix=MIPS3
 ; MIPS3: ISA: MIPS3
 ; RUN: llc -mtriple=mips64 -mcpu=mips4 -filetype=obj < %s \
 ; RUN:   | llvm-readelf -A - | FileCheck %s --check-prefix=MIPS4

 ; OCTEON: ISA Extension: Cavium Networks Octeon
 ; RUN: llc -mtriple=mips64 -mcpu=octeon+ -filetype=obj < %s \
 ; RUN:   | llvm-readelf -A - | FileCheck %s --check-prefix=OCTEONP
 ; OCTEONP: ISA: MIPS64r2
 ; OCTEONP: ISA Extension: Cavium Networks OcteonP
 
 ; Check that we reject CPUs that are not implemented.
 
-; RUN: not --crash llc < %s -o /dev/null -mtriple=mips -mcpu=mips1 2>&1 \
-; RUN:   | FileCheck %s --check-prefix=ERROR
 ; RUN: not --crash llc < %s -o /dev/null -mtriple=mips64 -mcpu=mips5 2>&1 \
 ; RUN:   | FileCheck %s --check-prefix=ERROR
 
 ; ERROR: LLVM ERROR: Code generation for MIPS-{{.}} is not implemented
 
 define void @foo() {
   ret void
 }

llvm/test/CodeGen/Mips/mips1-load-delay.ll

+; RUN: llc < %s -mtriple=mips -mcpu=mips1    | FileCheck %s -check-prefixes=ALL,MIPS1
+; RUN: llc < %s -mtriple=mips -mcpu=mips2    | FileCheck %s -check-prefixes=ALL,MIPS2
+; RUN: llc < %s -mtriple=mips -mcpu=mips32r2 | FileCheck %s -check-prefixes=ALL,MIPS32
+target datalayout = "e-m:m-p:32:32-i8:8:32-i16:16:32-i64:64-n32-S64"
+target triple = "mipsel-unknown-unknown-elf"
+
+; Function Attrs: noinline nounwind optnone
+define dso_local i32 @add_two_pointers(i32* %a, i32* %b) #0 {
+entry:
+; ALL-LABEL: add_two_pointers:
+  %a.addr = alloca i32*, align 4
+  %b.addr = alloca i32*, align 4
+  store i32* %a, i32** %a.addr, align 4
+  store i32* %b, i32** %b.addr, align 4
+  %0 = load i32*, i32** %a.addr, align 4
+  %1 = load i32, i32* %0, align 4
+  ; ALL:        lw $1, 4($fp)
+  ; MIPS1:      nop
+  ; MIPS2-NOT:  nop
+  ; MIPS32-NOT: nop
+  ; ALL:        lw $1, 0($1)
+  %2 = load i32*, i32** %b.addr, align 4
+  %3 = load i32, i32* %2, align 4
+  ; ALL:        lw $2, 0($fp)
+  ; MIPS1:      nop
+  ; MIPS2-NOT:  nop
+  ; MIPS32-NOT: nop
+  ; ALL:        lw $2, 0($2)
+  %add = add nsw i32 %1, %3
+  ret i32 %add
+  ; ALL:        lw $ra, 12($sp)
+  ; MIPS1:      nop
+  ; MIPS2-NOT:  nop
+  ; MIPS32-NOT: nop
+  ; ALL:        jr $ra
+}
+
+attributes #0 = { noinline nounwind optnone "frame-pointer"="all" "min-legal-vector-width"="0" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-features"="-noabicalls" }
+
+!llvm.module.flags = !{!0, !1}
+
+!0 = !{i32 1, !"wchar_size", i32 4}
+!1 = !{i32 7, !"frame-pointer", i32 2}
+