Lowering non-branch instruction to branch instruction

Code Generation RISCV
1

Hi,

I’m trying to replace a shift left instruction with multiple add instructions in LLVM’s RISCV backend, since my target RISCV processor might not contain an implementation of the shift left instruction. (This question is a follow-on to this one.)

For example:

sll x5, x5, x6

should be replaced by

    blez x6, .end
.loop:
    addi x6, x6, -1
    add x5, x5, x5
    bnez x6, .loop
.end:
    # next instruction

However, I’m struggling to create a branch instruction. Here’s what I have so far (specific questions are in the code comments).
In RISCVTargetLowering::RISCVTargetLowering:

setOperationAction(ISD::SHL, MVT::i32, Custom);

In RISCVTargetLowering::LowerOperation:

case ISD::SHL:
    return replaceShlWithAdd(Op, DAG);

And

SDValue RISCVTargetLowering::replaceShlWithAdd(SDValue Op, SelectionDAG &DAG) const {
  SDLoc DL(Op);
  SDValue finalReplacement;

  SDValue num = Op.getOperand(0);
  SDValue shamtOp = Op.getOperand(1);
  EVT VT = num.getValueType();

  if (DAG.isConstantIntBuildVectorOrConstantInt(shamtOp)) {
    // Already solved in https://discourse.llvm.org/t/replacing-instruction-with-multiple-substitute-instructions/72612
  }
  else {
    SDValue zero = DAG.getConstant(0, DL, VT);
    SDValue minusOne = DAG.getConstant(-1, DL, VT);
    SDValue ccle = DAG.getCondCode(ISD::SETOLE);
    SDValue ccgt = DAG.getCondCode(ISD::SETOGT);

    // How do I put these two instructions into an SDValue that corresponds to a basic block?
    num = DAG.getNode(ISD::ADD, DL, VT, num, num);
    shamtOp = DAG.getNode(ISD::ADD, DL, VT, shamtOp, minusOne);

    // I have no idea how to set chain, exitBlock or loopStart
    SDValue br0 = DAG.getNode(ISD::BR_CC, DL, VT, chain, ccle, shamtOp, zero, exitBlock);
    SDValue br1 = DAG.getNode(ISD::BR_CC, DL, VT, chain, ccgt, shamtOp, zero, loopStart);

    // Not sure if this should be set to br1, br0, or something else
    finalReplacement = br1;
  }
  return finalReplacement;
}

Let me know if any further details are required.

Thank you.

2

SelectionDAG can’t create new basic blocks or change the control flow graph.

Perhaps you can look at how we handle RISCVISD::SELECT which also needs to emit new basic blocks. During isel, we select it to a PseudoInstruction (for example Select_GPR_Using_CC_GPR) that has the “UsesCustomInserter” property. After SelectionDAG finishes, the “Finalize ISel and expand pseudo-instructions” pass will run and call RISCVTargetLowering::EmitInstrWithCustomInserter.

From RISCVTargetLowering::EmitInstrWithCustomInserter we expand the Select_GPR_Using_CC_GPR into control flow using MachineIR.

3

Thanks. It took me a while to familiarize myself with Machine Basic Blocks and the like, but I got it to work. I also moved SLLI replacements to this phase since it seemed more appropriate. For anyone interested, the full patch is attached.
replace_sll_i.patch (5.6 KB)