Lowering non-branch instruction to branch instruction


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
    addi x6, x6, -1
    add x5, x5, x5
    bnez x6, .loop
    # 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);


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.

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.

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)