Back-end

Target-Specific Information

Certain constants depend on the target ISA and/or the machine (the size of an int, for example). MachineTargetData instances contain all this information.

MachineTargetData is also responsible for generating various macros used in stdlib headers (such as __PTRDIFF_T_TYPE for stddef.h).

This class is technically part of the backend, but certain features handled in the front-end (eg sizeof) also depend on this target-specific data.

For now, only x64 Linux is supported, but the infrastructure for x86 and other platforms exists.

The MachineInstruction class

This class represents an instruction along with its operands (IRValue), so it is still target-independent. All the target-dependent aspects of an instruction are contained within the InstructionTemplate stored by the MI (see below for more).

The Instruction Graph

A CFG is sufficient to represent the control flow, but in order to more cleanly separate responsibilities, and to avoid turning the CFG class into a god object, a new graph representation is introduced, InstructionGraph.

This class is the CFG’s analogue in the backend (and is actually created by copying the structure of the existing CFG). Similarly, InstrBlock is the analogue for BasicBlock.

InstrBlock implements the MutableList<MachineInstruction> interface, for easily interacting with the instructions in a block.

The Code Generation Interfaces

These interfaces describe the code generation process in a target-independent manner. The code can be found in MachineTarget.kt.

  1. MachineTarget: This interface describes a particular compilation target. It contains the relevant MachineTargetData instance, and data about the register file of the target ISA.

  2. TargetOptions: Represents the set of CLI options passed to a target.

  3. MachineRegisterClass: Describes a type of register in the ISA. For example, x64 distinguishes between general purpose integer registers (rax, rbp, etc) and SSE/AVX registers (xmm4, ymm1, etc).

  4. MachineRegister: A description of a particular register in the ISA. Stores size, class, aliases.

  5. TargetFunGenerator: Implementors of this interface are code generators for a single function graph, for a particular MachineTarget. An instance of this class holds all the state required for all the code generation stages before emission.

  6. AsmEmitter: Takes the result of all the function generators in a translation unit and emits the actual assembly string. Currently, this means it emits NASM.

  7. PeepholeOptimizer: Takes a list of AsmInstruction, and optimizes them in isolation. Used by AsmEmitter.

  8. InstructionTemplate: Represents a particular instruction from an ISA. For example: mov r/m64, r64 or add r32, imm32.

  9. AsmInstruction: Final generated instruction, ready for emission.

Code Generation Process

First, TargetFunGenerator is created for each function in the translation unit. They are passed to an AsmEmitter, which returns the assembled code. The emitter is the one who triggers the actual generation process for each function’s generator.

Generation starts with instruction selection. Instruction selection creates MachineInstruction lists for each block, which are stored in the corresponding InstrBlock. The block has overridden methods for adding to the list: they also incrementally update the last uses map to account for the operands of the instruction.

The next step is register allocation. Note that the code is still in SSA form: φ functions have not been removed, and variables are only assigned once per version. The register allocator is based on this paper, and is target-independent (code in RegisterAllocation.kt).

The allocator is a graph coloring register allocator (GCRA), but it allocates directly over SSA. Other GCRAs run an SSA destruction algorithm before allocation, but this actually introduces additional complexity: the coloring influences spilling, and coalescing influences both. A graph that is not k-colorable will have to be rebuilt after a spill. Both coloring and coalescing will have to run after spills.

Allocation over SSA allows this process to be decoupled: SSA interference graphs are chordal (also from here), so k-colorability can be determined in polynomial time. That is, register pressure at all labels in the program can be known beforehand. That information is used to figure out spill locations before coloring (all labels where the register pressure is higher than the available registers). The resulting graph can be then colored (also in polynomial time), and it is guaranteed that coloring will not fail, because we forcefully reduced the chromatic number via spilling. Coalescing runs after coloring, but before implementing φs.

The register allocator alters the blocks of the InstructionGraph. Copies and/or spills are inserted, even new blocks might be inserted. The allocator also produces a list of spilled variables, as well its primary purpose, the actual allocation of registers to variables/temporaries.

After this is done, the function generator creates the function prologue/epilogue, and the final AsmInstruction list by replacing every IRValue with actual registers and memory locations.

Finally, the AsmEmitter emits the actual assembly from the AsmInstruction lists created by the generator.

--mi-debug mode

Like the --cfg-mode option for the graphviz CFG, the backend has a debugging option. By default, it prints the code at various execution points (MachineInstruction, InstrBlock and/or AsmInstruction). It also prints the list of allocations made, and any allocation violations (eg same register used for multiple live values).

The --mi-html prints this information in pretty HTML instead: example page.