[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

141

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

193

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

210

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

242

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

244

Didn't you already do this above?

248

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

6

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

248

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

6

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.

189

Ditto.

195

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

172

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

187

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

172

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

187

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().
   MaxStoresPerMemset = MaxStoresPerMemsetOptSize = 128;
   MaxStoresPerMemcpy = MaxStoresPerMemcpyOptSize = 128;
   MaxStoresPerMemmove = MaxStoresPerMemmoveOptSize = 128;
 }
 
+// Changes the condition code and swaps operands if necessary, so the SetCC
+// operation matches one of the comparisons supported directly in the RISC-V
+// ISA.
+static void normaliseSetCC(SDValue &LHS, SDValue &RHS, ISD::CondCode &CC) {
+  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;
+  }
+}
+
+// Return the RISC-V branch opcode that matches the given DAG integer
+// condition code. The CondCode must be one of those supported by the RISC-V
+// ISA (see normaliseSetCC).
+static unsigned getBranchOpcodeForIntCondCode(ISD::CondCode CC) {
+  switch (CC) {
+  default:
+    llvm_unreachable("Unsupported CondCode");
+  case ISD::SETEQ:
+    return RISCV::BEQ;
+  case ISD::SETNE:
+    return RISCV::BNE;
+  case ISD::SETLT:
+    return RISCV::BLT;
+  case ISD::SETGE:
+    return RISCV::BGE;
+  case ISD::SETULT:
+    return RISCV::BLTU;
+  case ISD::SETUGE:
+    return RISCV::BGEU;
+  }
+}
+
 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);
if (!isPositionIndependent() && !Subtarget->is64Bit()) {
     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);
+
+  normaliseSetCC(LHS, RHS, CC);
+
+  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 triangle
+  // 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 the condcode to use to select the appropriate branch.
+  //
+  // We produce the following control flow:
+  //     HeadMBB
+  //     |  \
+  //     |  IfFalseMBB
+  //     | /
+  //    TailMBB
+  const BasicBlock *LLVM_BB = BB->getBasicBlock();
+  MachineFunction::iterator I = ++BB->getIterator();
+
+  MachineBasicBlock *HeadMBB = BB;
+  MachineFunction *F = BB->getParent();
+  MachineBasicBlock *TailMBB = F->CreateMachineBasicBlock(LLVM_BB);
+  MachineBasicBlock *IfFalseMBB = F->CreateMachineBasicBlock(LLVM_BB);
+
+  F->insert(I, IfFalseMBB);
+  F->insert(I, TailMBB);
+  // Move all remaining instructions to TailMBB.
+  TailMBB->splice(TailMBB->begin(), HeadMBB,
+                  std::next(MachineBasicBlock::iterator(MI)), HeadMBB->end());
+  // 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.
+  TailMBB->transferSuccessorsAndUpdatePHIs(HeadMBB);
+  // Set the successors for HeadMBB.
+  HeadMBB->addSuccessor(IfFalseMBB);
+  HeadMBB->addSuccessor(TailMBB);
+
+  // Insert appropriate branch.
+  unsigned LHS = MI.getOperand(1).getReg();
+  unsigned RHS = MI.getOperand(2).getReg();
+  auto CC = static_cast<ISD::CondCode>(MI.getOperand(3).getImm());
+  unsigned Opcode = getBranchOpcodeForIntCondCode(CC);
+
+  BuildMI(HeadMBB, DL, TII.get(Opcode))
+    .addReg(LHS)
+    .addReg(RHS)
+    .addMBB(TailMBB);
+
+  // IfFalseMBB just falls through to TailMBB.
+  IfFalseMBB->addSuccessor(TailMBB);
+
+  // %Result = phi [ %TrueValue, HeadMBB ], [ %FalseValue, IfFalseMBB ]
+  BuildMI(*TailMBB, TailMBB->begin(), DL, TII.get(RISCV::PHI),
+          MI.getOperand(0).getReg())
+      .addReg(MI.getOperand(4).getReg())
+      .addMBB(HeadMBB)
+      .addReg(MI.getOperand(5).getReg())
+      .addMBB(IfFalseMBB);
+
+  MI.eraseFromParent(); // The pseudo instruction is gone now.
+  return TailMBB;
+}
+
 // 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 {
 
   switch (CallConv) {
   default:
     report_fatal_error("Unsupported calling convention");
   case CallingConv::C:
     break;
   }
 
   MachineFunction &MF = DAG.getMachineFunction();
   MachineRegisterInfo &RegInfo = MF.getRegInfo();
 
   if (IsVarArg)
     report_fatal_error("VarArg not supported");
 
   // Assign locations to all of the incoming arguments.
   SmallVector<CCValAssign, 16> ArgLocs;
   CCState CCInfo(CallConv, IsVarArg, MF, ArgLocs, *DAG.getContext());
   CCInfo.AnalyzeFormalArguments(Ins, CC_RISCV32);
 
   for (auto &VA : ArgLocs) {
     if (VA.isRegLoc()) {
       // Arguments passed in registers.
       EVT RegVT = VA.getLocVT();
       switch (RegVT.getSimpleVT().SimpleTy) {

 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
+}