[RISCV 13/n] Codegen for conditional branches

[asb]

Summary

A good portion of this patch is the extra functions that needed to be implemented to support the test case. e.g. storeRegToStackSlot, loadRegFromStackSlot, eliminateFrameIndex.

Setting ISD::BR_CC to Expand may appear non-obvious on an architecture with branch+cmp instructions. However, I found it much easier to deal with matching the expanded form.

I had to change simm13_lsb0 and simm21_lsb0 to use the Operand<OtherVT> class rather than Operand<i32> in order to keep tablegen happy. This isn't a big deal, but it does seem a shame to lose the uniformity across immediate types when there's not an obvious benefit (I'm hoping a tablegen expert will educate me on what I'm missing here!).

[asb]

Update after auditing for inappropriate use of llvm_unreachable. Replace these uses with report_fatal_error.

[dylanmckay]

lib/Target/RISCV/RISCV.h

26

Can we make these forward declarations alphabetically ordered?

lib/Target/RISCV/RISCVInstrInfo.h

39

IsKill should start with a capital letter

lib/Target/RISCV/RISCVRegisterInfo.cpp

59

Can we make this assertion message better?

72

This sounds less like a fatal error and more like an assertion

80

No else after return

[asb]

Updated to address review comments from @dylanmckay (thanks!).

[dylanmckay]

Are there any tests for the stack slot loading/storing? If there are some in a later patch, that's fine too.

lib/Target/RISCV/RISCVRegisterInfo.cpp

78

I think it makes more sense for report_fatal_error to live outside of the else entirely, and then the else can be removed as well.

[asb]

In D29935#847458, @dylanmckay wrote:

Are there any tests for the stack slot loading/storing? If there are some in a later patch, that's fine too.

They come later. There should really be a comment in eliminateFrameIndex to indicate that it is a placeholder implementation to allow codegen for conditional branches to be testable.

lib/Target/RISCV/RISCVRegisterInfo.cpp

78

Just to clarify, are you suggesting the following?:

if (!isInt<12>(Offset)) {
  report_fatal_error(...)
}

MI.getOperand(FIOperandNum).ChangeToRegister(FrameReg, false);
MI.getOperand(FIOperandNum + 1).ChangeToImmediate(Offset);
return;

[dylanmckay]

LGTM with minor error-handling nitpick

lib/Target/RISCV/RISCVRegisterInfo.cpp

78

I was thinking something more like the following

cpp
  if (isInt<12>(Offset)) {
    MI.getOperand(FIOperandNum).ChangeToRegister(FrameReg, false);
    MI.getOperand(FIOperandNum + 1).ChangeToImmediate(Offset);
  }

  report_fatal_error("Frame offsets outside of the signed 12-bit range not supported");
  return;

But now that you mention it, handling the error case early like your mockup seems better

[asb]

Update to address review comments. Thanks again @dylanmckay. If you're happy with this, please mark it accepted in Phabricator (makes it a little easier for seeing the current status of the RISC-V patchset at a glance).

[asb]

Instruction definitions and patterns have been split, as discussed in http://lists.llvm.org/pipermail/llvm-dev/2017-August/116635.html. There is no functional change vs the accepted patch revision.

[apazos]

lib/Target/RISCV/RISCVInstrInfo.td

63

Maybe these td file changes should move to a separate patch?

[asb]

lib/Target/RISCV/RISCVInstrInfo.td

63

I think they belong here, as the change is made necessary by the codegen implementation. Or perhaps I'm misunderstanding your concern?

[sabuasal]

llvm/trunk/lib/Target/RISCV/RISCVInstrInfo.td

70 ↗

(On Diff #122067)

Hi Alex,

I have two questions about this:

1. Why don't we have this type inherting from ImmLeaf?
2. Why is this not using XLenVT?

I am trying to add ImmLeaf since I need them for some checks for that type but it is causing a crash while running table gen about some type compatibility ("Type set is empty for each HW mode")

[asb]

llvm/trunk/lib/Target/RISCV/RISCVInstrInfo.td

70 ↗

(On Diff #122067)

As you've noted, it doesn't work when defined as an immediate type. I noted this in the patch description for this review, but nobody seems to have had any ideas on retaining def simm21_lsb0 : Operand<XLenVT>. Ultimately, branch operands are always symbols during codegen rather than immediates. Every other backend I checked ended up using Operand<OtherVT> for branch targets which at least implies I'm not missing something obvious. I think ideally we'd be able to specify that symbol operands are coerced to XLenVT.

If there's no cleaner solution, I suppose you could define a simm13_lsb0pred and use that in pattern definitions for instruction compression transformations. I don't like that we lose consistency with other operand definitions of course...

@kparzysz may be able to give more insight into the TableGen type check error.

lib/Target/RISCV/RISCV.h

 #include "MCTargetDesc/RISCVBaseInfo.h"
 #include "MCTargetDesc/RISCVMCTargetDesc.h"
 #include "llvm/CodeGen/MachineOperand.h"
 #include "llvm/MC/MCInst.h"
 #include "llvm/Target/TargetMachine.h"
 
 namespace llvm {
 class AsmPrinter;
 class RISCVTargetMachine;
+class MCContext;
 class MCInst;
+class MCOperand;
 class MachineInstr;
+class MachineOperand;
 
 void LowerRISCVMachineInstrToMCInst(const MachineInstr *MI, MCInst &OutMI,
                                     const AsmPrinter &AP);
 bool LowerRISCVMachineOperandToMCOperand(const MachineOperand &MO,
                                          MCOperand &MCOp, const AsmPrinter &AP);
 
 FunctionPass *createRISCVISelDag(RISCVTargetMachine &TM);
 }
 
 #endif

lib/Target/RISCV/RISCVCallingConv.td

CCIfType<[i32], CCAssignToReg<[ X10_32, X11_32, X12_32, X13_32, X14_32,
                                   X15_32, X16_32, X17_32 ]>>,
 
   // Could be assigned to the stack in 8-byte aligned units, but unsupported
   CCAssignToStack<8, 8>
 ]>;
 
 def CSR : CalleeSavedRegs<(add X1_32, X3_32, X4_32, X8_32, X9_32,
                           (sequence "X%u_32", 18, 27))>;
+
+// Needed for implementation of RISCVRegisterInfo::getNoPreservedMask()
+def CSR_NoRegs : CalleeSavedRegs<(add)>;

lib/Target/RISCV/RISCVISelLowering.cpp

RISCVTargetLowering::RISCVTargetLowering(const TargetMachine &TM,
 
   // Compute derived properties from the register classes
   computeRegisterProperties(STI.getRegisterInfo());
 
   setStackPointerRegisterToSaveRestore(RISCV::X2_32);
 
   // TODO: add all necessary setOperationAction calls
 
+  setOperationAction(ISD::BR_CC, MVT::i32, Expand);
   setBooleanContents(ZeroOrOneBooleanContent);
 
   setOperationAction(ISD::GlobalAddress, MVT::i32, Custom);
 
   // Function alignments (log2)
   setMinFunctionAlignment(3);
   setPrefFunctionAlignment(3);
 

lib/Target/RISCV/RISCVInstrInfo.h

 public:
   RISCVInstrInfo();
 
   const RISCVRegisterInfo &getRegisterInfo() const { return RI; }
 
   void copyPhysReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator Position,
                    const DebugLoc &DL, unsigned DestinationRegister,
                    unsigned SourceRegister, bool KillSource) const override;
+
+  void storeRegToStackSlot(MachineBasicBlock &MBB,
+                           MachineBasicBlock::iterator MBBI, unsigned SrcReg,
+                           bool isKill, int FrameIndex,
+                           const TargetRegisterClass *RC,
+                           const TargetRegisterInfo *TRI) const override;
+
+  void loadRegFromStackSlot(MachineBasicBlock &MBB,
+                            MachineBasicBlock::iterator MBBI, unsigned DestReg,
+                            int FrameIndex, const TargetRegisterClass *RC,
+                            const TargetRegisterInfo *TRI) const override;
 };
 }
 
 #endif

lib/Target/RISCV/RISCVInstrInfo.cpp

void RISCVInstrInfo::copyPhysReg(MachineBasicBlock &MBB,
   if (!RISCV::GPRRegClass.contains(DestinationRegister, SourceRegister)) {
     llvm_unreachable("Impossible reg-to-reg copy");
   }
 
   BuildMI(MBB, Position, DL, get(RISCV::ADDI), DestinationRegister)
       .addReg(SourceRegister, getKillRegState(KillSource))
       .addImm(0);
 }
+
+void RISCVInstrInfo::storeRegToStackSlot(MachineBasicBlock &MBB,
+                                         MachineBasicBlock::iterator I,
+                                         unsigned SrcReg, bool IsKill, int FI,
+                                         const TargetRegisterClass *RC,
+                                         const TargetRegisterInfo *TRI) const {
+  DebugLoc DL;
+  if (I != MBB.end())
+    DL = I->getDebugLoc();
+
+  if (RC == &RISCV::GPRRegClass)
+    BuildMI(MBB, I, DL, get(RISCV::SW))
+        .addReg(SrcReg, getKillRegState(IsKill))
+        .addFrameIndex(FI)
+        .addImm(0);
+  else
+    llvm_unreachable("Can't store this register to stack slot");
+}
+
+void RISCVInstrInfo::loadRegFromStackSlot(MachineBasicBlock &MBB,
+                                          MachineBasicBlock::iterator I,
+                                          unsigned DestReg, int FI,
+                                          const TargetRegisterClass *RC,
+                                          const TargetRegisterInfo *TRI) const {
+  DebugLoc DL;
+  if (I != MBB.end())
+    DL = I->getDebugLoc();
+
+  if (RC == &RISCV::GPRRegClass)
+    BuildMI(MBB, I, DL, get(RISCV::LW), DestReg).addFrameIndex(FI).addImm(0);
+  else
+    llvm_unreachable("Can't load this register from stack slot");
+}

lib/Target/RISCV/RISCVInstrInfo.td

 }
 
 def uimm12 : Operand<i32> {
   let ParserMatchClass = UImmAsmOperand<12>;
   let DecoderMethod = "decodeUImmOperand<12>";
 }
 
 // A 13-bit signed immediate where the least significant bit is zero.
-def simm13_lsb0 : Operand<i32> {
+def simm13_lsb0 : Operand<OtherVT> {
   let ParserMatchClass = SImmAsmOperand<13, "Lsb0">;
   let EncoderMethod = "getImmOpValueAsr1";
   let DecoderMethod = "decodeSImmOperandAndLsl1<13>";
 }
 
 def uimm20 : Operand<i32> {
   let ParserMatchClass = UImmAsmOperand<20>;
   let EncoderMethod = "getImmOpValue";
   let DecoderMethod = "decodeUImmOperand<20>";
 }
 
 // A 21-bit signed immediate where the least significant bit is zero.
-def simm21_lsb0 : Operand<i32> {
+def simm21_lsb0 : Operand<OtherVT> {
   let ParserMatchClass = SImmAsmOperand<21, "Lsb0">;
   let EncoderMethod = "getImmOpValueAsr1";
   let DecoderMethod = "decodeSImmOperandAndLsl1<21>";
 }
 
 // Extract least significant 12 bits from an immediate value and sign extend
 // them.
 def LO12Sext : SDNodeXForm<imm, [{
def LUI : FU<0b0110111, (outs GPR:$rd), (ins uimm20:$imm20),
              "lui\t$rd, $imm20", []>;
 
 def AUIPC : FU<0b0010111, (outs GPR:$rd), (ins uimm20:$imm20),
              "auipc\t$rd, $imm20", []>;
 
 def JAL : FUJ<0b1101111, (outs GPR:$rd), (ins simm21_lsb0:$imm20),
               "jal\t$rd, $imm20", []>;
 
+let isTerminator=1, isBarrier=1 in {
+def PseudoBR : Pseudo<(outs), (ins simm21_lsb0:$imm20), [(br bb:$imm20)]>,
+               PseudoInstExpansion<(JAL X0_32, simm21_lsb0:$imm20)>;
+}
+
 def JALR : FI<0b000, 0b1100111, (outs GPR:$rd), (ins GPR:$rs1, simm12:$imm12),
               "jalr\t$rd, $rs1, $imm12", []>;
 
 let isReturn=1, isTerminator=1, isBarrier=1 in {
   def PseudoRET : Pseudo<(outs), (ins), [(RetFlag)]>,
                   PseudoInstExpansion<(JALR X0_32, X1_32, 0)>;
 }
 
-class Bcc<bits<3> funct3, string OpcodeStr> :
+class Bcc<bits<3> funct3, string OpcodeStr, PatFrag CondOp> :
       FSB<funct3, 0b1100011, (outs), (ins GPR:$rs1, GPR:$rs2, simm13_lsb0:$imm12),
-         OpcodeStr#"\t$rs1, $rs2, $imm12", []> {
-}
+         OpcodeStr#"\t$rs1, $rs2, $imm12", [(brcond (i32 (CondOp GPR:$rs1, GPR:$rs2)), bb:$imm12)]> {
+  let isBranch = 1;
+  let isTerminator = 1;
+}
+
+def BEQ   : Bcc<0b000, "beq", seteq>;
+def BNE   : Bcc<0b001, "bne", setne>;
+def BLT   : Bcc<0b100, "blt", setlt>;
+def BGE   : Bcc<0b101, "bge", setge>;
+def BLTU  : Bcc<0b110, "bltu", setult>;
+def BGEU  : Bcc<0b111, "bgeu", setuge>;
+
+class Bcc_SwapPat<PatFrag CondOp, RISCVInst InstBcc> : Pat<
+  (brcond (i32 (CondOp GPR:$rs1, GPR:$rs2)), bb:$imm12),
+  (InstBcc GPR:$rs2, GPR:$rs1, bb:$imm12)>;
+
+// Condition codes that don't have matching RISC-V branch instructions, but
+// are trivially supported by swapping the two input operands
+def : Bcc_SwapPat<setgt, BLT>;
+def : Bcc_SwapPat<setle, BGE>;
+def : Bcc_SwapPat<setugt, BLTU>;
+def : Bcc_SwapPat<setule, BGEU>;
 
-def BEQ   : Bcc<0b000, "beq">;
-def BNE   : Bcc<0b001, "bne">;
-def BLT   : Bcc<0b100, "blt">;
-def BGE   : Bcc<0b101, "bge">;
-def BLTU  : Bcc<0b110, "bltu">;
-def BGEU  : Bcc<0b111, "bgeu">;
+def : Pat<(brcond GPR:$cond, bb:$imm12), (BNE GPR:$cond, X0_32, bb:$imm12)>;
 
 class LD_ri<bits<3> funct3, string OpcodeStr> :
       FI<funct3, 0b0000011, (outs GPR:$rd), (ins GPR:$rs1, simm12:$imm12),
          OpcodeStr#"\t$rd, ${imm12}(${rs1})", []> {
   let mayLoad = 1;
 }
 
 def LB   : LD_ri<0b000, "lb">;

lib/Target/RISCV/RISCVRegisterInfo.h

 struct RISCVRegisterInfo : public RISCVGenRegisterInfo {
 
   RISCVRegisterInfo();
 
   const MCPhysReg *getCalleeSavedRegs(const MachineFunction *MF) const override;
 
   BitVector getReservedRegs(const MachineFunction &MF) const override;
 
+  const uint32_t *getNoPreservedMask() const override;
+
   void eliminateFrameIndex(MachineBasicBlock::iterator MI, int SPAdj,
                            unsigned FIOperandNum,
                            RegScavenger *RS = nullptr) const override;
 
   unsigned getFrameRegister(const MachineFunction &MF) const override;
 };
 }
 
 #endif

lib/Target/RISCV/RISCVRegisterInfo.cpp

BitVector RISCVRegisterInfo::getReservedRegs(const MachineFunction &MF) const {
   Reserved.set(RISCV::X3_32); // gp
   Reserved.set(RISCV::X4_64); // tp
   Reserved.set(RISCV::X4_32); // tp
   Reserved.set(RISCV::X8_64); // fp
   Reserved.set(RISCV::X8_32); // fp
   return Reserved;
 }
 
+const uint32_t *RISCVRegisterInfo::getNoPreservedMask() const {
+  return CSR_NoRegs_RegMask;
+}
+
 void RISCVRegisterInfo::eliminateFrameIndex(MachineBasicBlock::iterator II,
                                             int SPAdj, unsigned FIOperandNum,
                                             RegScavenger *RS) const {
-  report_fatal_error("Subroutines not supported yet");
+  assert(SPAdj == 0 && "Unexpected");
+
+  MachineInstr &MI = *II;
+  MachineFunction &MF = *MI.getParent()->getParent();
+  const TargetFrameLowering *TFI = MF.getSubtarget().getFrameLowering();
+  DebugLoc DL = MI.getDebugLoc();
+
+  unsigned FrameReg = getFrameRegister(MF);
+  int FrameIndex = MI.getOperand(FIOperandNum).getIndex();
+  int Offset = TFI->getFrameIndexReference(MF, FrameIndex, FrameReg);
+  Offset += MI.getOperand(FIOperandNum + 1).getImm();
+
+  if (!TFI->hasFP(MF)) {
+    report_fatal_error("eliminateFrameIndex currently requires hasFP");
+  }
+
+  // If the offset fits in an immediate, then directly encode it
+  if (isInt<12>(Offset)) {
+    MI.getOperand(FIOperandNum).ChangeToRegister(FrameReg, false);
+    MI.getOperand(FIOperandNum + 1).ChangeToImmediate(Offset);
+    return;
+  } else {
+    report_fatal_error(
+        "Frame offsets outside of the signed 12-bit range not supported");
+  }
 }
 
 unsigned RISCVRegisterInfo::getFrameRegister(const MachineFunction &MF) const {
   return RISCV::X8_32;
 }

test/CodeGen/RISCV/branch.ll

+; RUN: llc -mtriple=riscv32 -verify-machineinstrs < %s | FileCheck %s
+
+define void @foo(i32 %a, i32 *%b, i1 %c) {
+; CHECK-LABEL: foo:
+
+  %val1 = load volatile i32, i32* %b
+  %tst1 = icmp eq i32 %val1, %a
+  br i1 %tst1, label %end, label %test2
+; CHECK: beq {{[a-z0-9]+}}, {{[a-z0-9]+}}, .LBB
+
+test2:
+  %val2 = load volatile i32, i32* %b
+  %tst2 = icmp ne i32 %val2, %a
+  br i1 %tst2, label %end, label %test3
+; CHECK: bne {{[a-z0-9]+}}, {{[a-z0-9]+}}, .LBB
+
+test3:
+  %val3 = load volatile i32, i32* %b
+  %tst3 = icmp slt i32 %val3, %a
+  br i1 %tst3, label %end, label %test4
+; CHECK: blt {{[a-z0-9]+}}, {{[a-z0-9]+}}, .LBB
+
+test4:
+  %val4 = load volatile i32, i32* %b
+  %tst4 = icmp sge i32 %val4, %a
+  br i1 %tst4, label %end, label %test5
+; CHECK: bge {{[a-z0-9]+}}, {{[a-z0-9]+}}, .LBB
+
+test5:
+  %val5 = load volatile i32, i32* %b
+  %tst5 = icmp ult i32 %val5, %a
+  br i1 %tst5, label %end, label %test6
+; CHECK: bltu {{[a-z0-9]+}}, {{[a-z0-9]+}}, .LBB
+
+test6:
+  %val6 = load volatile i32, i32* %b
+  %tst6 = icmp uge i32 %val6, %a
+  br i1 %tst6, label %end, label %test7
+; CHECK: bgeu {{[a-z0-9]+}}, {{[a-z0-9]+}}, .LBB
+
+; Check for condition codes that don't have a matching instruction
+
+test7:
+  %val7 = load volatile i32, i32* %b
+  %tst7 = icmp sgt i32 %val7, %a
+  br i1 %tst7, label %end, label %test8
+; CHECK: blt {{[a-z0-9]+}}, {{[a-z0-9]+}}, .LBB
+
+test8:
+  %val8 = load volatile i32, i32* %b
+  %tst8 = icmp sle i32 %val8, %a
+  br i1 %tst8, label %end, label %test9
+; CHECK: bge {{[a-z0-9]+}}, {{[a-z0-9]+}}, .LBB
+
+test9:
+  %val9 = load volatile i32, i32* %b
+  %tst9 = icmp ugt i32 %val9, %a
+  br i1 %tst9, label %end, label %test10
+; CHECK: bltu {{[a-z0-9]+}}, {{[a-z0-9]+}}, .LBB
+
+test10:
+  %val10 = load volatile i32, i32* %b
+  %tst10 = icmp ule i32 %val10, %a
+  br i1 %tst10, label %end, label %test11
+; CHECK: bgeu {{[a-z0-9]+}}, {{[a-z0-9]+}}, .LBB
+
+; Check the case of a branch where the condition was generated in another
+; function
+
+test11:
+; CHECK: andi {{[a-z0-9]+}}, {{[a-z0-9]+}}, 1
+; CHECK: bne {{[a-z0-9]+}}, zero, .LBB
+  %val11 = load volatile i32, i32* %b
+  br i1 %c, label %end, label %test12
+
+test12:
+  %val12 = load volatile i32, i32* %b
+; CHECK: jalr zero, ra, 0
+  br label %end
+
+end:
+  ret void
+}