[RISCV 15/n] Implement lowering of ISD::SELECT

[asb]

Summary

There's nothing particular novel here, every backend without a conditional move has something similar to the custom inserter for SELECT_CC. Some backends try to use a mix of tablegen patterns and C++ code, for instance to deal with the condition code. I feel it's simpler when just handled in RISCVTargetLowering.

Although ISD::SELECT_CC is a more natural match for RISCVISD::SELECT_CC (and
ultimately the integer RISC-V conditional branch instructions), we choose to
expand ISD::SELECT_CC and lower ISD::SELECT. The appropriate compare+branch
will be created in the case where an ISD::SELECT condition value is created by
an ISD::SETCC node, which operates on XLen types. Other datatypes such as
floating point don't have conditional branch instructions, and lowering
ISD::SELECT allows more flexibility for handling these cases.

[dylanmckay]

lib/Target/RISCV/RISCVISelLowering.cpp

102

Over 80 char limit

[asb]

Update to fix line > 80 chars.

[asb]

Instruction definition and patterns have been split, as discussed in http://lists.llvm.org/pipermail/llvm-dev/2017-August/116635.html.

[reames]

lib/Target/RISCV/RISCVISelLowering.cpp

154

A better name here would be more clear, maybe FallthroughMBB?

171

Extracting this switch out as a helper function or lambda would aid readability. getBranchOpcodeForSetCCOpcode?

203

Yuck. Please just use the names and don't update a variable in place. This is just confusing.

205

Didn't you already do this above?

209

Hm, as written, isn't this basically making a static prediction the true value is common? Is there profiling available on the SETCC instruction?

test/CodeGen/RISCV/select-cc.ll

5

Please expand your test to cover the whole diamond.

[asb]

Hi Philip, many many thanks for the review - this code has been copied around several backends, and we can certainly do better (patches for those backends to follow!). This is exactly the sort of thing I'm trying to avoid with this backend project, so I really appreciate you calling it this case where the code fell short. The code comment was incorrect to say a diamond control flow pattern is being inserted, as it's actually just a triangle. Hopefully the Head/IfFalse/Tail names make more sense. I've made normaliseSetCC a separate helper function in addition to your suggested CondCode->BranchOpcode helper (this felt sensible, given getBranchOpcodeForIntCondCode expects its argument has been normalised in this way).

lib/Target/RISCV/RISCVISelLowering.cpp

209

I believe MachineBlockPlacement should handle this. RISC-V compilers should assume a forward branch is predicted not-taken, so the assumption would actually be the false path is the common case.

test/CodeGen/RISCV/select-cc.ll

5

The comment was incorrect, we're actually inserting a triangle (though as you point out, the confusing variable naming makes it really hard to see what is going on!)

[reames]

Much, much cleaner. Thanks!

LGTM if you want to land as is, but you might consider waiting for one other review. I'm not super familiar with the tablegen and customer inserter stuff, so I may have missed something.

[apazos]

lib/Target/RISCV/RISCVISelLowering.cpp

89

You might want to be consistent in code standard in the file and put the default case as the top one like done above.

[asb]

Update to put the 'default:' case first in a switch (thanks @apazos).

[mgrang]

lib/Target/RISCV/RISCVISelLowering.cpp

70

Period at the end of comment.

150

Ditto.

156

Ditto.

[asb]

Full stops at end of comments.

[reames]

Reflecting previous LGTM again.

[asb]

This minor revision of the patch switches to lowering ISD::SELECT. This is motivated by future support for the floating point instruction set extensions and the coarse-grained nature of setOperationAction. See the updated patch description and new code comments for more discussion, but essentially we need to ensure that a RISC-V compare+branch instruction is generated whenever the comparison is between two XLEN integers.

[johnrusso]

lib/Target/RISCV/RISCVISelLowering.cpp

133

I noticed that the select-cc.ll test didn't cover this code.
This little snip with the correct matching pattern should cover it.
...

%val20 = select i1 %tst10, i32 %val18, i32 %val19

%tr3 = trunc i32 %val3 to i1
%val21 = select i1 %tr3, i32 %val20, i32 %val19

ret i32 %val21

148

Could we use a 'switch(MI.getOpcode())' here and assert on an unhandled opcode if it occurs. I suspect other pseudos may require a custom inserter in the future.

[asb]

Adds a bare-select.ll test case, ensuring all code paths in lowerSELECT are tested.

lib/Target/RISCV/RISCVISelLowering.cpp

133

Well spotted, I've moved the bare-select.ll test from D29938 in to this patch to ensure the code path is exercised.

148

Future patches move to doing this. For previous patches, reviewers have asked to not have single-element switches. I don't have a particularly strong view either way. The single-element switch minimises the diff in the future patches and is easier to extend, but has the disadvantage of looking a little odd.

[apazos]

This looks ready to merge. Can we have this in today?

lib/Target/RISCV/RISCVISelLowering.h

 #include "llvm/Target/TargetLowering.h"
 
 namespace llvm {
 class RISCVSubtarget;
 namespace RISCVISD {
 enum NodeType : unsigned {
   FIRST_NUMBER = ISD::BUILTIN_OP_END,
   RET_FLAG,
-  CALL
+  CALL,
+  SELECT_CC
 };
 }
 
 class RISCVTargetLowering : public TargetLowering {
   const RISCVSubtarget *Subtarget;
 
 public:
   explicit RISCVTargetLowering(const TargetMachine &TM,
                                const RISCVSubtarget &STI);
 
   // Provide custom lowering hooks for some operations.
   SDValue LowerOperation(SDValue Op, SelectionDAG &DAG) const override;
 
   // This method returns the name of a target specific DAG node.
   const char *getTargetNodeName(unsigned Opcode) const override;
 
+  MachineBasicBlock *
+  EmitInstrWithCustomInserter(MachineInstr &MI,
+                              MachineBasicBlock *BB) const override;
+
 private:
   // Lower incoming arguments, copy physregs into vregs
   SDValue LowerFormalArguments(SDValue Chain, CallingConv::ID CallConv,
                                bool IsVarArg,
                                const SmallVectorImpl<ISD::InputArg> &Ins,
                                const SDLoc &DL, SelectionDAG &DAG,
                                SmallVectorImpl<SDValue> &InVals) const override;
   SDValue LowerReturn(SDValue Chain, CallingConv::ID CallConv, bool IsVarArg,
                       const SmallVectorImpl<ISD::OutputArg> &Outs,
                       const SmallVectorImpl<SDValue> &OutVals, const SDLoc &DL,
                       SelectionDAG &DAG) const override;
   SDValue LowerCall(TargetLowering::CallLoweringInfo &CLI,
                     SmallVectorImpl<SDValue> &InVals) const override;
   bool shouldConvertConstantLoadToIntImm(const APInt &Imm,
                                          Type *Ty) const override {
     return true;
   }
   SDValue lowerGlobalAddress(SDValue Op, SelectionDAG &DAG) const;
+  SDValue lowerSELECT_CC(SDValue Op, SelectionDAG &DAG) const;
 };
 }
 
 #endif

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);
+  setOperationAction(ISD::SELECT_CC, MVT::i32, Custom);
   setBooleanContents(ZeroOrOneBooleanContent);
 
   setOperationAction(ISD::GlobalAddress, MVT::i32, Custom);
 
   // Function alignments (log2)
   setMinFunctionAlignment(3);
   setPrefFunctionAlignment(3);
 
   // inline memcpy() for kernel to see explicit copy
   MaxStoresPerMemset = MaxStoresPerMemsetOptSize = 128;
   MaxStoresPerMemcpy = MaxStoresPerMemcpyOptSize = 128;
   MaxStoresPerMemmove = MaxStoresPerMemmoveOptSize = 128;
 }
 
 SDValue RISCVTargetLowering::LowerOperation(SDValue Op,
                                             SelectionDAG &DAG) const {
   switch (Op.getOpcode()) {
   case ISD::GlobalAddress:
     return lowerGlobalAddress(Op, DAG);
+  case ISD::SELECT_CC:
+    return lowerSELECT_CC(Op, DAG);
   default:
     report_fatal_error("unimplemented operand");
   }
 }
 
 SDValue RISCVTargetLowering::lowerGlobalAddress(SDValue Op,
                                                 SelectionDAG &DAG) const {
   SDLoc DL(Op);
   EVT Ty = Op.getValueType();
   GlobalAddressSDNode *N = cast<GlobalAddressSDNode>(Op);
   const GlobalValue *GV = N->getGlobal();
   int64_t Offset = N->getOffset();
 
   if (!isPositionIndependent() && !Subtarget->is64Bit()) {
     SDValue GAHi =
         DAG.getTargetGlobalAddress(GV, DL, Ty, Offset, RISCVII::MO_HI);
     SDValue GALo =
         DAG.getTargetGlobalAddress(GV, DL, Ty, Offset, RISCVII::MO_LO);
     SDValue MNHi = SDValue(DAG.getMachineNode(RISCV::LUI, DL, Ty, GAHi), 0);
     SDValue MNLo =
         SDValue(DAG.getMachineNode(RISCV::ADDI, DL, Ty, MNHi, GALo), 0);
     return MNLo;
   } else {
     report_fatal_error("Unable to lowerGlobalAddress");
   }
 }
 
+SDValue RISCVTargetLowering::lowerSELECT_CC(SDValue Op,
+                                            SelectionDAG &DAG) const {
+  SDValue LHS = Op.getOperand(0);
+  SDValue RHS = Op.getOperand(1);
+  SDValue TrueV = Op.getOperand(2);
+  SDValue FalseV = Op.getOperand(3);
+  ISD::CondCode CC = cast<CondCodeSDNode>(Op.getOperand(4))->get();
+  SDLoc DL(Op);
+
+  switch (CC) {
+  default:
+    break;
+  case ISD::SETGT:
+  case ISD::SETLE:
+  case ISD::SETUGT:
+  case ISD::SETULE:
+    CC = ISD::getSetCCSwappedOperands(CC);
+    std::swap(LHS, RHS);
+    break;
+  }
+
+  SDValue TargetCC = DAG.getConstant(CC, DL, MVT::i32);
+
+  SDVTList VTs = DAG.getVTList(Op.getValueType(), MVT::Glue);
+  SDValue Ops[] = {LHS, RHS, TargetCC, TrueV, FalseV};
+
+  return DAG.getNode(RISCVISD::SELECT_CC, DL, VTs, Ops);
+}
+
+MachineBasicBlock *
+RISCVTargetLowering::EmitInstrWithCustomInserter(MachineInstr &MI,
+                                                 MachineBasicBlock *BB) const {
+  const TargetInstrInfo &TII = *BB->getParent()->getSubtarget().getInstrInfo();
+  DebugLoc DL = MI.getDebugLoc();
+
+  assert(MI.getOpcode() == RISCV::Select && "Unexpected instr type to insert");
+
+  // To "insert" a SELECT instruction, we actually have to insert the diamond
+  // control-flow pattern.  The incoming instruction knows the destination vreg
+  // to set, the condition code register to branch on, the true/false values to
+  // select between, and a branch opcode to use.
+  const BasicBlock *LLVM_BB = BB->getBasicBlock();
+  MachineFunction::iterator I = ++BB->getIterator();
+
+  // ThisMBB:
+  // ...
+  //  TrueVal = ...
+  //  jmp_XX r1, r2 goto Copy1MBB
+  //  fallthrough --> Copy0MBB
+  MachineBasicBlock *ThisMBB = BB;
+  MachineFunction *F = BB->getParent();
+  MachineBasicBlock *Copy0MBB = F->CreateMachineBasicBlock(LLVM_BB);
+  MachineBasicBlock *Copy1MBB = F->CreateMachineBasicBlock(LLVM_BB);
+
+  F->insert(I, Copy0MBB);
+  F->insert(I, Copy1MBB);
+  // Update machine-CFG edges by transferring all successors of the current
+  // block to the new block which will contain the Phi node for the select.
+  Copy1MBB->splice(Copy1MBB->begin(), BB,
+                   std::next(MachineBasicBlock::iterator(MI)), BB->end());
+  Copy1MBB->transferSuccessorsAndUpdatePHIs(BB);
+  // Next, add the true and fallthrough blocks as its successors.
+  BB->addSuccessor(Copy0MBB);
+  BB->addSuccessor(Copy1MBB);
+
+  // Insert Branch if Flag
+  unsigned LHS = MI.getOperand(1).getReg();
+  unsigned RHS = MI.getOperand(2).getReg();
+  int CC = MI.getOperand(3).getImm();
+  unsigned Opcode = -1;
+  switch (CC) {
+  case ISD::SETEQ:
+    Opcode = RISCV::BEQ;
+    break;
+  case ISD::SETNE:
+    Opcode = RISCV::BNE;
+    break;
+  case ISD::SETLT:
+    Opcode = RISCV::BLT;
+    break;
+  case ISD::SETGE:
+    Opcode = RISCV::BGE;
+    break;
+  case ISD::SETULT:
+    Opcode = RISCV::BLTU;
+    break;
+  case ISD::SETUGE:
+    Opcode = RISCV::BGEU;
+    break;
+  default:
+    report_fatal_error("unimplemented select CondCode " + Twine(CC));
+  }
+
+  BuildMI(BB, DL, TII.get(Opcode))
+    .addReg(LHS)
+    .addReg(RHS)
+    .addMBB(Copy1MBB);
+
+  // Copy0MBB:
+  //  %FalseValue = ...
+  //  # fallthrough to Copy1MBB
+  BB = Copy0MBB;
+
+  // Update machine-CFG edges
+  BB->addSuccessor(Copy1MBB);
+
+  // Copy1MBB:
+  //  %Result = phi [ %FalseValue, Copy0MBB ], [ %TrueValue, ThisMBB ]
+  // ...
+  BB = Copy1MBB;
+  BuildMI(*BB, BB->begin(), DL, TII.get(RISCV::PHI), MI.getOperand(0).getReg())
+      .addReg(MI.getOperand(5).getReg())
+      .addMBB(Copy0MBB)
+      .addReg(MI.getOperand(4).getReg())
+      .addMBB(ThisMBB);
+
+  MI.eraseFromParent(); // The pseudo instruction is gone now.
+  return BB;
+}
+
 // Calling Convention Implementation
 #include "RISCVGenCallingConv.inc"
 
 // Transform physical registers into virtual registers
 SDValue RISCVTargetLowering::LowerFormalArguments(
     SDValue Chain, CallingConv::ID CallConv, bool IsVarArg,
     const SmallVectorImpl<ISD::InputArg> &Ins, const SDLoc &DL,
     SelectionDAG &DAG, SmallVectorImpl<SDValue> &InVals) const {

 const char *RISCVTargetLowering::getTargetNodeName(unsigned Opcode) const {
   switch ((RISCVISD::NodeType)Opcode) {
   case RISCVISD::FIRST_NUMBER:
     break;
   case RISCVISD::RET_FLAG:
     return "RISCVISD::RET_FLAG";
   case RISCVISD::CALL:
     return "RISCVISD::CALL";
+  case RISCVISD::SELECT_CC:
+    return "RISCVISD::SELECT_CC";
   }
   return nullptr;
 }

lib/Target/RISCV/RISCVInstrInfo.td

 
 include "RISCVInstrFormats.td"
 
 def SDT_RISCVCallSeqStart : SDCallSeqStart<[SDTCisVT<0, i32>,
                                             SDTCisVT<1, i32>]>;
 def SDT_RISCVCallSeqEnd   : SDCallSeqEnd<[SDTCisVT<0, i32>,
                                          SDTCisVT<1, i32>]>;
 def SDT_RISCVCall         : SDTypeProfile<0, -1, [SDTCisVT<0, i32>]>;
+def SDT_RISCVSelectCC     : SDTypeProfile<1, 5, [SDTCisSameAs<1, 2>,
+                                                 SDTCisSameAs<0, 4>,
+                                                 SDTCisSameAs<4, 5>]>;
 
 
 def Call             : SDNode<"RISCVISD::CALL", SDT_RISCVCall,
                               [SDNPHasChain, SDNPOptInGlue, SDNPOutGlue,
                                SDNPVariadic]>;
 def RetFlag : SDNode<"RISCVISD::RET_FLAG", SDTNone,
                      [SDNPHasChain, SDNPOptInGlue, SDNPVariadic]>;
 def CallSeqStart     : SDNode<"ISD::CALLSEQ_START", SDT_RISCVCallSeqStart,
                               [SDNPHasChain, SDNPOutGlue]>;
 def CallSeqEnd       : SDNode<"ISD::CALLSEQ_END", SDT_RISCVCallSeqEnd,
                               [SDNPHasChain, SDNPOptInGlue, SDNPOutGlue]>;
+def SelectCC         : SDNode<"RISCVISD::SELECT_CC", SDT_RISCVSelectCC, [SDNPInGlue]>;
 
 // Operands
 class ImmAsmOperand<string prefix, int width, string suffix> : AsmOperandClass {
   let Name = prefix # "Imm" # width # suffix;
   let RenderMethod = "addImmOperands";
   let DiagnosticType = !strconcat("Invalid", Name);
 }
 

 
 /// Setcc
 
 def : PatGprGpr<setlt, SLT>;
 def : PatGprSimm12<setlt, SLTI>;
 def : PatGprGpr<setult, SLTU>;
 def : PatGprSimm12<setult, SLTIU>;
 
+let usesCustomInserter = 1 in
+def Select : Pseudo<(outs GPR:$dst),
+                    (ins GPR:$lhs, GPR:$rhs, i32imm:$imm, GPR:$src, GPR:$src2),
+                    [(set i32:$dst,
+                     (SelectCC GPR:$lhs, GPR:$rhs, (i32 imm:$imm), GPR:$src, GPR:$src2))]>;
+
 /// Branches and jumps
 
 // Match `(brcond (CondOp ..), ..)` and lower to the appropriate RISC-V branch
 // instruction.
 class BccPat<PatFrag CondOp, FSB Inst> :
       Pat<(brcond (i32 (CondOp GPR:$rs1, GPR:$rs2)), bb:$imm12),
           (Inst GPR:$rs1, GPR:$rs2, simm13_lsb0:$imm12)>;
 

test/CodeGen/RISCV/select-cc.ll

+; RUN: llc -mtriple=riscv32 -verify-machineinstrs < %s | FileCheck %s
+
+define i32 @foo(i32 %a, i32 *%b) {
+; CHECK-LABEL: foo:
+; CHECK: beq a0, a2, .LBB{{.+}}
+  %val1 = load volatile i32, i32* %b
+  %tst1 = icmp eq i32 %a, %val1
+  %val2 = select i1 %tst1, i32 %a, i32 %val1
+
+; CHECK: bne a0, a2, .LBB{{.+}}
+  %val3 = load volatile i32, i32* %b
+  %tst2 = icmp ne i32 %val2, %val3
+  %val4 = select i1 %tst2, i32 %val2, i32 %val3
+
+; CHECK: bltu a2, a0, .LBB{{.+}}
+  %val5 = load volatile i32, i32* %b
+  %tst3 = icmp ugt i32 %val4, %val5
+  %val6 = select i1 %tst3, i32 %val4, i32 %val5
+
+; CHECK: bgeu a0, a2, .LBB{{.+}}
+  %val7 = load volatile i32, i32* %b
+  %tst4 = icmp uge i32 %val6, %val7
+  %val8 = select i1 %tst4, i32 %val6, i32 %val7
+
+; CHECK: bltu a0, a2, .LBB{{.+}}
+  %val9 = load volatile i32, i32* %b
+  %tst5 = icmp ult i32 %val8, %val9
+  %val10 = select i1 %tst5, i32 %val8, i32 %val9
+
+; CHECK: bgeu a2, a0, .LBB{{.+}}
+  %val11 = load volatile i32, i32* %b
+  %tst6 = icmp ule i32 %val10, %val11
+  %val12 = select i1 %tst6, i32 %val10, i32 %val11
+
+; CHECK: blt a2, a0, .LBB{{.+}}
+  %val13 = load volatile i32, i32* %b
+  %tst7 = icmp sgt i32 %val12, %val13
+  %val14 = select i1 %tst7, i32 %val12, i32 %val13
+
+; CHECK: bge a0, a2, .LBB{{.+}}
+  %val15 = load volatile i32, i32* %b
+  %tst8 = icmp sge i32 %val14, %val15
+  %val16 = select i1 %tst8, i32 %val14, i32 %val15
+
+; CHECK: blt a0, a2, .LBB{{.+}}
+  %val17 = load volatile i32, i32* %b
+  %tst9 = icmp slt i32 %val16, %val17
+  %val18 = select i1 %tst9, i32 %val16, i32 %val17
+
+; CHECK: bge a1, a0, .LBB{{.+}}
+  %val19 = load volatile i32, i32* %b
+  %tst10 = icmp sle i32 %val18, %val19
+  %val20 = select i1 %tst10, i32 %val18, i32 %val19
+
+  ret i32 %val20
+}