The SelectionDAGLegalize class consists of various data members, tracking data structures to keep a track of legalized nodes, and various methods that are used to operate on nodes to legalize them. A sample snapshot of the legalize phase code from the LLVM trunk shows the basic skeleton of implementation of the legalize phase, as follows:

namespace {
class SelectionDAGLegalize : public SelectionDAG::DAGUpdateListener {

const TargetMachine &TM;

const TargetLowering &TLI;

SelectionDAG &DAG;

SelectionDAG::allnodes_iterator LegalizePosition;

// LegalizedNodes - The set of nodes which have already been legalized.
SmallPtrSet<SDNode *, 16> LegalizedNodes;

public:
explicit SelectionDAGLegalize(SelectionDAG &DAG);
void LegalizeDAG();

private:

void LegalizeOp(SDNode *Node);

SDValue OptimizeFloatStore(StoreSDNode *ST);

// Legalize Load operations
void LegalizeLoadOps(SDNode *Node);

// Legalize Store operations
void LegalizeStoreOps(SDNode *Node);

// Main legalize function which operates on Selection DAG node
void SelectionDAGLegalize::LegalizeOp(SDNode *Node) {
// A target node which is constant need not be legalized further
  if (Node->getOpcode() == ISD::TargetConstant)
    return;

  for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i)
    assert(TLI.getTypeAction(*DAG.getContext(), Node->getValueType(i)) == TargetLowering::TypeLegal && "Unexpected illegal type!");

  for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i)
    assert((TLI.getTypeAction(*DAG.getContext(),
    Node->getOperand(i).getValueType()) == TargetLowering::TypeLegal ||
      Node->getOperand(i).getOpcode() == ISD::TargetConstant) && "Unexpected illegal type!");

  TargetLowering::LegalizeAction Action = TargetLowering::Legal;
  bool SimpleFinishLegalizing = true;

// Legalize based on instruction opcode
  switch (Node->getOpcode()) {
    case ISD::INTRINSIC_W_CHAIN:
    case ISD::INTRINSIC_WO_CHAIN:
    case ISD::INTRINSIC_VOID:
    case ISD::STACKSAVE:
          Action = TLI.getOperationAction(Node->getOpcode(), MVT::Other);
    break;
…
…
}

Many function members of the SelectionDAGLegalize class, such as LegalizeOp, rely on target-specific information provided by the const TargetLowering &TLI member (other function members may also depend on the const TargetMachine &TM member) in the SelectionDAGLegalize class. Let's take an example to demonstrate how legalization works.

There are two types of legalization: type legalization and instruction legalization. Let's first see how type legalization works. Create a test.ll file using the following commands:

$ cat test.ll
define i64 @test(i64 %a, i64 %b, i64 %c) {
  %add = add nsw i64 %a, %b
  %div = sdiv i64 %add, %c
  ret i64 %div
}

The data type in this case is i64. For the x86 target, which supports only the 32-bit data type, the data type you just saw is illegal. To run the preceding code, the data type has to be converted to i32. This is done by the DAG Legalization phase.

To view the DAG before type legalization, run the following command line:

$ llc -view-dag-combine1-dags test.ll

The following figure shows the DAG before type legalization:

To see DAG after type legalization, enter the following command line:

$ llc -view-dag-combine2-dags test.ll

The following figure shows the DAG after type legalization:

On observing the DAG nodes carefully, you can see that every operation before legalization had the i64 type. This was because the IR had the data type i64—one-to-one mapping from the IR instruction to the DAG nodes. However, the target x86 machine supports only the i32 type (32-bit integer type). The DAG legalize phase converts unsupported i64 types to supported i32 types. This operation is called expanding—splitting larger types into smaller types. For example, in a target accepting only i32 values, all i64 values are broken down to pairs of i32 values. So, after legalization, you can see that all the operations now have i32 as the data type.

Let's see how instructions are legalized; create a test.ll file using the following commands:

$ cat test.ll
define i32 @test(i32 %a, i32 %b, i32 %c) {
  %add = add nsw i32 %a, %b
  %div = sdiv i32 %add, %c
  ret i32 %div
}

To view the DAG before legalization, enter the following command:

$ llc –view-dag-combine1-dags test.ll

The following figure shows the DAG before legalization:

To view the DAG after legalization, enter the following command:

$ llc -view-dag-combine2-dags test.ll

The following figure shows the DAG after the legalization phase:

The DAG, before instruction legalization, consists of sdiv instructions. Now, the x86 target does not support the sdiv instruction, hence it is illegal for the target. It does, however, support the sdivrem instruction. So, the legalization phase involves conversion of the sdiv instruction to the sdivrem instruction, as visible in the preceding two DAGs.