Until the previous chapter, we saw how a frontend language can be converted to LLVM IR. We also saw how IR can be transformed into more optimized code. After a series of analysis and transformation passes, the final IR is the most optimized machine independent code. However, the IR is still an abstract representation of the actual machine code. The compiler has to generate target architecture code for execution.
LLVM uses DAG—a directed acyclic graph representation for code generation. The idea is to convert IR into a SelectionDAG and then go over a series of phases—DAG combine, legalization, instruction selection, instruction scheduling, etc—to finally allocate registers and emit machine code. Note that register allocation and instruction scheduling take place in an intertwined manner.
We are going to cover following topics in this chapter:
- Converting IR to selectionDAG
- Legalizing selectionDAG
- Optimizing selectionDAG
- Instruction selection
- Scheduling and emitting machine instructions
- Register allocation
- Code emission
An IR instruction can be represented by an SDAG node. The whole set of instructions thus forms an interconnected directed acyclic graph, with each node corresponding to an IR instruction.
For example, consider the following LLVM IR:
$ 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 }
LLVM provides a SelectionDAGBuilder interface to create DAG nodes corresponding to IR instructions. Consider the binary operation:
%add = add nsw i32 %a, %b
The following function is called when the given IR is encountered:
void SelectionDAGBuilder::visit(unsigned Opcode, const User &I) {
// Note: this doesn't use InstVisitor, because it has to work with
// ConstantExpr's in addition to instructions.
switch (Opcode) {
default: llvm_unreachable("Unknown instruction type encountered!");
// Build the switch statement using the Instruction.def file.
#define HANDLE_INST(NUM, OPCODE, CLASS)
case Instruction::OPCODE: visit##OPCODE((const CLASS&)I); break;
#include "llvm/IR/Instruction.def"
}
}Depending on the opcode—which is Add here—the corresponding visit function is invoked. In this case, visitAdd() is invoked, which further invokes the visitBinary() function. The visitBinary() function is as follows:
void SelectionDAGBuilder::visitBinary(const User &I, unsigned OpCode) {
SDValue Op1 = getValue(I.getOperand(0));
SDValue Op2 = getValue(I.getOperand(1));
bool nuw = false;
bool nsw = false;
bool exact = false;
FastMathFlags FMF;
if (const OverflowingBinaryOperator *OFBinOp =
dyn_cast<const OverflowingBinaryOperator>(&I)) {
nuw = OFBinOp->hasNoUnsignedWrap();
nsw = OFBinOp->hasNoSignedWrap();
}
if (const PossiblyExactOperator *ExactOp =
dyn_cast<const PossiblyExactOperator>(&I))
exact = ExactOp->isExact();
if (const FPMathOperator *FPOp = dyn_cast<const FPMathOperator>(&I))
FMF = FPOp->getFastMathFlags();
SDNodeFlags Flags;
Flags.setExact(exact);
Flags.setNoSignedWrap(nsw);
Flags.setNoUnsignedWrap(nuw);
if (EnableFMFInDAG) {
Flags.setAllowReciprocal(FMF.allowReciprocal());
Flags.setNoInfs(FMF.noInfs());
Flags.setNoNaNs(FMF.noNaNs());
Flags.setNoSignedZeros(FMF.noSignedZeros());
Flags.setUnsafeAlgebra(FMF.unsafeAlgebra());
}
SDValue BinNodeValue = DAG.getNode(OpCode, getCurSDLoc(), Op1.getValueType(), Op1, Op2, &Flags);
setValue(&I, BinNodeValue);
}This function takes two operands of the binary operator from IR and stores them into SDValue type. Then it invokes the DAG.getNode() function with opcode of the binary operator. This results in formation of a DAG node, which somewhat looks like the following:
The operands 0 and 1 are load DAG nodes.
Consider the IR:
%div = sdiv i32 %add, %c
On encountering the sdiv instruction, the function visitSDiv() is invoked.
void SelectionDAGBuilder::visitSDiv(const User &I) {
SDValue Op1 = getValue(I.getOperand(0));
SDValue Op2 = getValue(I.getOperand(1));
SDNodeFlags Flags;
Flags.setExact(isa<PossiblyExactOperator>(&I) &&
cast<PossiblyExactOperator>(&I)->isExact());
setValue(&I, DAG.getNode(ISD::SDIV, getCurSDLoc(), Op1.getValueType(), Op1, Op2, &Flags));
}Similar to visitBinary(), this function also stores the two operands into SDValue gets a DAG node with ISD::SDIV as its operator. The node looks like the following:
In our IR, the operand 0 is %add. Operand 1 is %c, which is passed as an argument to the function, which transforms to a load node when converting IR to SelectionDAG. For implementation of Load DAG node, go through the visitLoad() function in the lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp file.
After visiting all the IR instructions mentioned earlier, finally the IR is converted to SelectionDAG as follows:
In the preceding diagram, note the following:
Glue prevents the two nodes from being broken up during scheduling. Chain dependencies prevent nodes with side effects. A data dependency indicates when an instruction depends on the result of a previous instruction.