[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 ↗

(On Diff #111631)

Can we make these forward declarations alphabetically ordered?

lib/Target/RISCV/RISCVInstrInfo.h

39 ↗

(On Diff #111631)

IsKill should start with a capital letter

lib/Target/RISCV/RISCVRegisterInfo.cpp

59 ↗

(On Diff #111631)

Can we make this assertion message better?

72 ↗

(On Diff #111631)

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

80 ↗

(On Diff #111631)

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 ↗

(On Diff #111970)

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 ↗

(On Diff #111970)

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 ↗

(On Diff #111970)

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 ↗

(On Diff #112450)

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

[asb]

lib/Target/RISCV/RISCVInstrInfo.td

63 ↗

(On Diff #112450)

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

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

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.

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

def CC_RISCV32 : CallingConv<[
   // All arguments get passed in integer registers if there is space.
   CCIfType<[i32], CCAssignToReg<[ X10, X11, X12, X13, X14, X15, X16, X17]>>,
 
   // Could be assigned to the stack in 8-byte aligned units, but unsupported
   CCAssignToStack<8, 8>
 ]>;
 
 def CSR : CalleeSavedRegs<(add X1, X3, X4, X8, X9, (sequence "X%u", 18, 27))>;
+
+// Needed for implementation of RISCVRegisterInfo::getNoPreservedMask()
+def CSR_NoRegs : CalleeSavedRegs<(add)>;

llvm/trunk/lib/Target/RISCV/RISCVISelLowering.cpp

RISCVTargetLowering::RISCVTargetLowering(const TargetMachine &TM,
   setStackPointerRegisterToSaveRestore(RISCV::X2);
 
   for (auto N : {ISD::EXTLOAD, ISD::SEXTLOAD, ISD::ZEXTLOAD})
     setLoadExtAction(N, XLenVT, MVT::i1, Promote);
 
   // TODO: add all necessary setOperationAction calls.
   setOperationAction(ISD::GlobalAddress, XLenVT, Custom);
 
+  setOperationAction(ISD::BR_CC, XLenVT, Expand);
   setBooleanContents(ZeroOrOneBooleanContent);
 
   // Function alignments (log2).
   setMinFunctionAlignment(3);
   setPrefFunctionAlignment(3);
 }
 
 SDValue RISCVTargetLowering::LowerOperation(SDValue Op,

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

 class RISCVInstrInfo : public RISCVGenInstrInfo {
 
 public:
   RISCVInstrInfo();
 
   void copyPhysReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator MBBI,
                    const DebugLoc &DL, unsigned DstReg, unsigned SrcReg,
                    bool KillSrc) 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 DstReg,
+                            int FrameIndex, const TargetRegisterClass *RC,
+                            const TargetRegisterInfo *TRI) const override;
 };
 }
-
 #endif

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

void RISCVInstrInfo::copyPhysReg(MachineBasicBlock &MBB,
                                  unsigned SrcReg, bool KillSrc) const {
   assert(RISCV::GPRRegClass.contains(DstReg, SrcReg) &&
          "Impossible reg-to-reg copy");
 
   BuildMI(MBB, MBBI, DL, get(RISCV::ADDI), DstReg)
       .addReg(SrcReg, getKillRegState(KillSrc))
       .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 DstReg, 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), DstReg).addFrameIndex(FI).addImm(0);
+  else
+    llvm_unreachable("Can't load this register from stack slot");
+}

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

 }
 
 def uimm12 : Operand<XLenVT> {
   let ParserMatchClass = UImmAsmOperand<12>;
   let DecoderMethod = "decodeUImmOperand<12>";
 }
 
 // A 13-bit signed immediate where the least significant bit is zero.
-def simm13_lsb0 : Operand<XLenVT> {
+def simm13_lsb0 : Operand<OtherVT> {
   let ParserMatchClass = SImmAsmOperand<13, "Lsb0">;
   let EncoderMethod = "getImmOpValueAsr1";
   let DecoderMethod = "decodeSImmOperandAndLsl1<13>";
 }
 
 def uimm20 : Operand<XLenVT> {
   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<XLenVT> {
+def simm21_lsb0 : Operand<OtherVT> {
   let ParserMatchClass = SImmAsmOperand<21, "Lsb0">;
   let EncoderMethod = "getImmOpValueAsr1";
   let DecoderMethod = "decodeSImmOperandAndLsl1<21>";
 }
 
 // Standalone (codegen-only) immleaf patterns.
 def simm32 : ImmLeaf<XLenVT, [{return isInt<32>(Imm);}]>;
 

 
 def : PatGprGpr<setlt, SLT>;
 def : PatGprSimm12<setlt, SLTI>;
 def : PatGprGpr<setult, SLTU>;
 def : PatGprSimm12<setult, SLTIU>;
 
 /// Branches and jumps
 
+// Match `(brcond (CondOp ..), ..)` and lower to the appropriate RISC-V branch
+// instruction.
+class BccPat<PatFrag CondOp, RVInstB Inst>
+    : Pat<(brcond (i32 (CondOp GPR:$rs1, GPR:$rs2)), bb:$imm12),
+          (Inst GPR:$rs1, GPR:$rs2, simm13_lsb0:$imm12)>;
+
+def : BccPat<seteq, BEQ>;
+def : BccPat<setne, BNE>;
+def : BccPat<setlt, BLT>;
+def : BccPat<setge, BGE>;
+def : BccPat<setult, BLTU>;
+def : BccPat<setuge, BGEU>;
+
+class BccSwapPat<PatFrag CondOp, RVInst 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 : BccSwapPat<setgt, BLT>;
+def : BccSwapPat<setle, BGE>;
+def : BccSwapPat<setugt, BLTU>;
+def : BccSwapPat<setule, BGEU>;
+
+// An extra pattern is needed for a brcond without a setcc (i.e. where the
+// condition was calculated elsewhere).
+def : Pat<(brcond GPR:$cond, bb:$imm12), (BNE GPR:$cond, X0, bb:$imm12)>;
+
+let isBarrier = 1, isBranch = 1, isTerminator = 1 in
+def PseudoBR : Pseudo<(outs), (ins simm21_lsb0:$imm20), [(br bb:$imm20)]>,
+               PseudoInstExpansion<(JAL X0, simm21_lsb0:$imm20)>;
+
 let isBarrier = 1, isReturn = 1, isTerminator = 1 in
 def PseudoRET : Pseudo<(outs), (ins), [(RetFlag)]>,
                 PseudoInstExpansion<(JALR X0, X1, 0)>;
 
 /// Loads
 
 multiclass LdPat<PatFrag LoadOp, RVInst Inst> {
   def : Pat<(LoadOp GPR:$rs1), (Inst GPR:$rs1, 0)>;

llvm/trunk/lib/Target/RISCV/RISCVMCInstLower.cpp

case MachineOperand::MO_Register:
     // Ignore all implicit register operands.
     if (MO.isImplicit())
       return false;
     MCOp = MCOperand::createReg(MO.getReg());
     break;
   case MachineOperand::MO_Immediate:
     MCOp = MCOperand::createImm(MO.getImm());
     break;
+  case MachineOperand::MO_MachineBasicBlock:
+    MCOp = MCOperand::createExpr(
+        MCSymbolRefExpr::create(MO.getMBB()->getSymbol(), AP.OutContext));
+    break;
   case MachineOperand::MO_GlobalAddress:
     MCOp = lowerSymbolOperand(MO, AP.getSymbol(MO.getGlobal()), AP);
     break;
   }
   return true;
 }
 
 void llvm::LowerRISCVMachineInstrToMCInst(const MachineInstr *MI, MCInst &OutMI,

llvm/trunk/lib/Target/RISCV/RISCVRegisterInfo.h

 struct RISCVRegisterInfo : public RISCVGenRegisterInfo {
 
   RISCVRegisterInfo(unsigned HwMode);
 
   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

llvm/trunk/lib/Target/RISCV/RISCVRegisterInfo.cpp

BitVector RISCVRegisterInfo::getReservedRegs(const MachineFunction &MF) const {
   markSuperRegs(Reserved, RISCV::X2); // sp
   markSuperRegs(Reserved, RISCV::X3); // gp
   markSuperRegs(Reserved, RISCV::X4); // tp
   markSuperRegs(Reserved, RISCV::X8); // fp
   assert(checkAllSuperRegsMarked(Reserved));
   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");
+  // TODO: this implementation is a temporary placeholder which does just
+  // enough to allow other aspects of code generation to be tested
+
+  assert(SPAdj == 0 && "Unexpected non-zero SPAdj value");
+
+  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();
+
+  assert(TFI->hasFP(MF) && "eliminateFrameIndex currently requires hasFP");
+
+  // Offsets must be directly encoded in a 12-bit immediate field
+  if (!isInt<12>(Offset)) {
+    report_fatal_error(
+        "Frame offsets outside of the signed 12-bit range not supported");
+  }
+
+  MI.getOperand(FIOperandNum).ChangeToRegister(FrameReg, false);
+  MI.getOperand(FIOperandNum + 1).ChangeToImmediate(Offset);
+  return;
 }
 
 unsigned RISCVRegisterInfo::getFrameRegister(const MachineFunction &MF) const {
   return RISCV::X8;
 }

llvm/trunk/test/CodeGen/RISCV/branch.ll

+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
+; RUN: llc -mtriple=riscv32 -verify-machineinstrs < %s \
+; RUN:   | FileCheck -check-prefix=RV32I %s
+
+define void @foo(i32 %a, i32 *%b, i1 %c) {
+; RV32I-LABEL: foo:
+; RV32I:       # BB#0:
+; RV32I-NEXT:    lw a3, 0(a1)
+; RV32I-NEXT:    beq a3, a0, .LBB0_12
+; RV32I-NEXT:    jal zero, .LBB0_1
+; RV32I-NEXT:  .LBB0_1: # %test2
+; RV32I-NEXT:    lw a3, 0(a1)
+; RV32I-NEXT:    bne a3, a0, .LBB0_12
+; RV32I-NEXT:    jal zero, .LBB0_2
+; RV32I-NEXT:  .LBB0_2: # %test3
+; RV32I-NEXT:    lw a3, 0(a1)
+; RV32I-NEXT:    blt a3, a0, .LBB0_12
+; RV32I-NEXT:    jal zero, .LBB0_3
+; RV32I-NEXT:  .LBB0_3: # %test4
+; RV32I-NEXT:    lw a3, 0(a1)
+; RV32I-NEXT:    bge a3, a0, .LBB0_12
+; RV32I-NEXT:    jal zero, .LBB0_4
+; RV32I-NEXT:  .LBB0_4: # %test5
+; RV32I-NEXT:    lw a3, 0(a1)
+; RV32I-NEXT:    bltu a3, a0, .LBB0_12
+; RV32I-NEXT:    jal zero, .LBB0_5
+; RV32I-NEXT:  .LBB0_5: # %test6
+; RV32I-NEXT:    lw a3, 0(a1)
+; RV32I-NEXT:    bgeu a3, a0, .LBB0_12
+; RV32I-NEXT:    jal zero, .LBB0_6
+; RV32I-NEXT:  .LBB0_6: # %test7
+; RV32I-NEXT:    lw a3, 0(a1)
+; RV32I-NEXT:    blt a0, a3, .LBB0_12
+; RV32I-NEXT:    jal zero, .LBB0_7
+; RV32I-NEXT:  .LBB0_7: # %test8
+; RV32I-NEXT:    lw a3, 0(a1)
+; RV32I-NEXT:    bge a0, a3, .LBB0_12
+; RV32I-NEXT:    jal zero, .LBB0_8
+; RV32I-NEXT:  .LBB0_8: # %test9
+; RV32I-NEXT:    lw a3, 0(a1)
+; RV32I-NEXT:    bltu a0, a3, .LBB0_12
+; RV32I-NEXT:    jal zero, .LBB0_9
+; RV32I-NEXT:  .LBB0_9: # %test10
+; RV32I-NEXT:    lw a3, 0(a1)
+; RV32I-NEXT:    bgeu a0, a3, .LBB0_12
+; RV32I-NEXT:    jal zero, .LBB0_10
+; RV32I-NEXT:  .LBB0_10: # %test11
+; RV32I-NEXT:    lw a0, 0(a1)
+; RV32I-NEXT:    andi a0, a2, 1
+; RV32I-NEXT:    bne a0, zero, .LBB0_12
+; RV32I-NEXT:    jal zero, .LBB0_11
+; RV32I-NEXT:  .LBB0_11: # %test12
+; RV32I-NEXT:    lw a0, 0(a1)
+; RV32I-NEXT:  .LBB0_12: # %end
+; RV32I-NEXT:    jalr zero, ra, 0
+
+  %val1 = load volatile i32, i32* %b
+  %tst1 = icmp eq i32 %val1, %a
+  br i1 %tst1, label %end, label %test2
+
+test2:
+  %val2 = load volatile i32, i32* %b
+  %tst2 = icmp ne i32 %val2, %a
+  br i1 %tst2, label %end, label %test3
+
+test3:
+  %val3 = load volatile i32, i32* %b
+  %tst3 = icmp slt i32 %val3, %a
+  br i1 %tst3, label %end, label %test4
+
+test4:
+  %val4 = load volatile i32, i32* %b
+  %tst4 = icmp sge i32 %val4, %a
+  br i1 %tst4, label %end, label %test5
+
+test5:
+  %val5 = load volatile i32, i32* %b
+  %tst5 = icmp ult i32 %val5, %a
+  br i1 %tst5, label %end, label %test6
+
+test6:
+  %val6 = load volatile i32, i32* %b
+  %tst6 = icmp uge i32 %val6, %a
+  br i1 %tst6, label %end, label %test7
+
+; 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
+
+test8:
+  %val8 = load volatile i32, i32* %b
+  %tst8 = icmp sle i32 %val8, %a
+  br i1 %tst8, label %end, label %test9
+
+test9:
+  %val9 = load volatile i32, i32* %b
+  %tst9 = icmp ugt i32 %val9, %a
+  br i1 %tst9, label %end, label %test10
+
+test10:
+  %val10 = load volatile i32, i32* %b
+  %tst10 = icmp ule i32 %val10, %a
+  br i1 %tst10, label %end, label %test11
+
+; Check the case of a branch where the condition was generated in another
+; function
+
+test11:
+  %val11 = load volatile i32, i32* %b
+  br i1 %c, label %end, label %test12
+
+test12:
+  %val12 = load volatile i32, i32* %b
+  br label %end
+
+end:
+  ret void
+}