In the preceding topic, we saw how an IR is converted to SelectionDAG. The whole process didn't involve any knowledge of target architecture for which we are trying to generate code. A DAG node might be illegal for the given target architecture. For example, the X86 architecture doesn't support the sdiv instruction. Instead, it supports sdivrem instruction. This target specific information is conveyed to the SelectionDAG phase by the TargetLowering interface. Targets implement this interface to describe how LLVM IR instructions should be lowered to legal SelectionDAG operations.

In our IR case, we need to 'expand' the sdiv instruction to 'sdivrem' instruction. In the function void SelectionDAGLegalize::LegalizeOp(SDNode *Node), the TargetLowering::Expand case is encountered, which invokes the ExpandNode() function call on that particular node.

void SelectionDAGLegalize::LegalizeOp(SDNode *Node){
…
…
case TargetLowering::Expand:
      ExpandNode(Node);
      return;
…
…
}

This function expands SDIV into the SDIVREM node:

case ISD::SDIV: {
    bool isSigned = Node->getOpcode() == ISD::SDIV;
    unsigned DivRemOpc = isSigned ? ISD::SDIVREM : ISD::UDIVREM;
    EVT VT = Node->getValueType(0);
    SDVTList VTs = DAG.getVTList(VT, VT);
    if (TLI.isOperationLegalOrCustom(DivRemOpc, VT) ||
        (isDivRemLibcallAvailable(Node, isSigned, TLI) &&
         useDivRem(Node, isSigned, true)))
      Tmp1 = DAG.getNode(DivRemOpc, dl, VTs, Node->getOperand(0),
                         Node->getOperand(1));
    else if (isSigned)
      Tmp1 = ExpandIntLibCall(Node, true,
                              RTLIB::SDIV_I8,
                              RTLIB::SDIV_I16, RTLIB::SDIV_I32,
                              RTLIB::SDIV_I64, RTLIB::SDIV_I128);
    else
      Tmp1 = ExpandIntLibCall(Node, false,
                              RTLIB::UDIV_I8,
                              RTLIB::UDIV_I16, RTLIB::UDIV_I32,
                              RTLIB::UDIV_I64, RTLIB::UDIV_I128);
    Results.push_back(Tmp1);
    break;
  }

Finally, after legalization, the node becomes ISD::SDIVREM:

Thus the above instruction has been 'legalized' mapping to the instruction supported on the target architecture. What we saw above was an example of expand legalization. There are two other types of legalization—promotion and custom. A promotion promotes one type to a larger type. A custom legalization involves target-specific hook (maybe a custom operation—majorly seen with IR intrinsic). We leave it to the readers to explore these more in the CodeGen phase.