Notes on setcc, select cc, br cc

From LLVM

These notes were gathered while working on re-implementation of a (broken) conditional branching/setcc/select_cc implementation in a target backend.

The SelectionDAGNodes of interest are:

• void BR_CC(chain, cc, lhs, rhs, target_bb)
  • Branch to target_bb if, and only if, lhs compared with rhs using condition code cc is true.
• BooleanResultType SETCC(lhs, rhs, cc)
  • The result is a 'true value' if, and only if, lhs compared with rhs using condition code cc is true.
• ResultType SELECT_CC(lhs, rhs, true_value, false_value, cc)
  • The result is true_value if, and only if, lhs compared with rhs using condition code cc is true. Otherwise, result is false_value.
• void BRCOND(chain, cond, target_bb)
  • Branch to target_bb if, and only if, cond is a 'true value'.
• ResultType SELECT(cond, true_value, false_value)
  • The result is true_value if, and only if, cond is a 'true value'. Otherwise, result is false_value.

In order to fully understand the listing above, some definitions are in order:

cc 

a condition code. This is of type CondCodeSDNode, which typically indicates the type of comparison to perform.

cond 

the result of a comparison. This is an intrinsically boolean value, which may be represented either as an i1 or as some other type which conforms to the 'boolean value' definition.

BooleanResultType 

the result of a SETCC operation. This type is the same as that of a cond.

ResultType 

the result of a selection operation. Should be of the same type as the true_value and false_value operands.

[edit] Implementing conditional branching using br_cc

Assuming a target platform which has a comparison instruction (CMP) which sets the CPU flags, and a conditional branch instruction (JCC), we can implement conditional branching using BR_CC only. In the example we also only have i32 types.

[edit] Step 1: Register for Lowering

LLVM will try to use BRCOND nodes by default. Since our target doesn't support BRCOND nodes we'll expand them to BR_CC instructions. We need to inform the TargetLowering pass that we intend to expand BRCOND nodes and custom-lower BR_CC nodes.

In the constructor for our TargetLowering implementation (MyTargetLowering), add setOperationAction calls, specifying the Custom action value for BR_CC, and the Expand action for BRCOND:

setOperationAction(ISD::BRCOND, MVT::i32, Expand);
setOperationAction(ISD::BR_CC, MVT::i32, Custom);

We also need to make sure that when MyTargetLowering::LowerOperation is called for a BR_CC node,the call gets routed to a function to perform the custom lowering:

static SDValue Lower_BR_CC(SDValue Op, SelectionDAG &DAG) {
    return Op;
}
SDValue MyTargetLowerng::LowerOperation(SDValue Op, SelectionDAG &DAG) {
    switch(Op.getOpcode()) {
        case ISD::BR_CC:        return Lower_BR_CC(Op, DAG);
        ...
    }
}

[edit] Step 2: Custom Lower BR_CC

/!\ Warning: this section is out of date, you need to define correctly Def and Uses in Machine Machine InstrInfo td file else your cmp will be removed !

We now need to write the code to actually perform the custom lowering of the BR_CC node.

We need to transform a BR_CC(chain, cc, lhs, rhs, target_bb) node into a CMP/JCC pair like:

CMP(lhs, rhs)
JCC(cc, target_bb)

Note that our target's CMP instruction doesn't have any explicit result. It only modifies the CPU flags. In addition the JCC instruction refers to the CPU flags when checking its condition. This is a very common pattern.

In order to make sure that the instruction scheduler keeps these two instructions together, we need to link them somehow - to show that the 'output' to the CPU flags resulting from the CMP is necessary for the correct operation of the JCC. At this point (2.5) this is done by making sure that the CMP node has the property SDNPOutFlag, and the JCC node has the property SDNPInFlag. ToDo: flesh this out in another page!

The final Lower_BR_CC method looks like:

static SDValue Lower_BR_CC(SDValue Op, SelectionDAG &DAG){
  DEBUG(printf("==> MyTargetLowering::Lower_BR_CC()\n"));
  SDValue chain     = Op.getOperand(0);
  ISD::CondCode cc   = cast<CondCodeSDNode>(Op.getOperand(1))->get();
  SDValue lhs    = Op.getOperand(2);
  SDValue rhs    = Op.getOperand(3);
  SDValue target_bb  = Op.getOperand(4);
 
  SDValue cmp_result_flags = DAG.getNode(MyTargetISD::CMP, MVT::Flag, lhs, rhs);
  SDValue my_cc = DAG.getConstant(IntCCToMyTargetCC(cc),MVT::i32);
 
  return DAG.getNode(MyTargetISD::JCC, Op.getValueType(), chain, target_bb, my_cc, cmp_result_flags);
}

[edit] Step 3: Custom Lower SELECT_CC

The next step is to custom lower the SELECT_CC nodes. We register for custom lowering just as we did in #Step 1 for BR_CC. We then need to implement the custom lowering code.

On many platforms, SELECT_CC can be lowered to a comparison and a conditional move instruction. We'll assume that there is no conditional move instruction on our platform, and that a SELECT_CC(lhs, rhs, true_value, false_value, cc) must therefore be lowered to a sequence like:

    CMP(lhs, rhs)
    dst = MOV(true_value)
    JCC(cc, END)
SET_FALSE:
    dst = MOV(false_value)
END:
    ...