The LLVM Target Independent Code Generator

Reference: LLVM Code Generator

Design of Code Generator

  1. Instruction Selection. Expression LLVM code input in the target instruction set.
    • Initial code in the target ISA;
    • required register assignments due to target constraints or calling conventions;
    • turns LLVM code into a DAG of target instructions: SelectionDAG.
  2. Scheduling and Formation. Take DAG as input.
    • determine order of instructions;
    • emit code as MachineInstrs;
  3. SSA-based Machine Code Optimizations. Machine code optimization on SSA-form.
    • eg. Modulo-scheduing; peephole optimization.
  4. Register Allocation. Transform the code from infinite virtual register file in SSA form to the concrete register file used by the target.
    • spill code
    • eliminates all virtual register reference from the program
  5. Prolog/Epilog Code Insertion. Once the machine code has been generated for the function and the amount of stack space required is known (used for LLVM alloca’s and spill slots), the prolog and epilog code can be inserted.
    • eliminate the “abstract stack location references”
    • e.g. OPTs such as frame-pointer elimination and stack packing.
  6. Late Machine Code Optimizations. operates on “final” machine code.
    • e.g. spill code scheduling and peephole optimizations.
  7. Code Emission. either in assembler format or in machine code.

To work on any of the above components, it is necessary to be familiar with the two classes:

Code Overview

  1. include/llvm/Target/. Defines the Target Description classes. They capture important properties about various aspects of the machine, independently of how they will be used.

  2. include/llvm/CodeGen/: Define Machine Code Description classes used to represent the code being generated for a target, both SSA form and Non-SSA form representation for machine code. These classes are intended to be abstract enough to represent the machine code for any target machine. At this level, concepts like “constant pool entries” and “jump tables” are explicitly exposed.

  3. include/llvm/MC/: define classes and algorithms used to represent code at the object file level, the MC layer. These classes represent assembly level contructs like labels, sections, and instructions. At this level, concepts like “constant pool entries” and “jump tables” don’t exist.

  4. lib/CodeGen/: Define the target-independent algorithms used to implement various phases of native code generation.

  5. lib/Target/: Implement the abstract target description interfaces for particular targets. These machine descriptions make use of the components provided by LLVM, and can optionally provide custom target-specific passes, to build complete code generators for a specific target.

  6. lib/ExecutionEngine/JIT: defines the target independent JIT components. The LLVM JIT is completely target independent. It uses the TargetJITInfo structure to interface for target-specific issues.

The components in CodeGen

Note: need to focus on the following parts:

  • code emission
  • prolog/epilog code insertion.

Required components in the CodeGen

Two pieces: high-level interface to the code generator & set of reusable components that can be used to build target-specific backends.

Two most important interfaces, TargetMachine and DataLayout, are the only ones that are required to be defined for a backend to fit into the LLVM system, but the others must be defined if the reusable code generator components are going to be used.

This design allows to implement radically different code generator that do not make use of any of the built-in components. This could be required for radically different target that do not fit into the LLVM machine description model: FPGAs for example.

Target Description Classes

Located in include/llvm/Target/. Provides an abstract description of the target machine independent of any particular client. Designed to capture the abstract properties of the target, such as the instructions and registers it has. It does not incorporate any particular pieces of code generation algorithms.

  • TargetMachine
  • DataLayout
  • TargetLowering
  • TargetRegisterInfo
  • TargetInstrInfo
  • TargetFrameLowering
  • TargetSubtarget
  • TargetJITInfo

Machine Code Description Classes

LLVM code is translated to a machine specific representation formed out of instances of the following classes:

  • MachineFunction.
  • MachineBasicBlock.
  • MachineInstr.

However, this reprentation is completely target agnostic, representing instructions in their most abstract form: an opcode and a series of operands. The representation is designed to support both an SSA form for machine code, as well as a register allocated, non-SSA form.

MachineInstr class

Used to represent target machine instructions. Only keep track of an opcode number and a set of operands.

  • Does not have any information about how to interpret the instruction (i.e., what the semantics of the instruction are); for that you must refer to the TargetInstrInfo class.
  • MachineInstr’s are initially selected in SSA-form, and are maintained in SSA-form until register allocation happens.

To create a MachineInstr, use BuildMI functions (in include/llvm/CodeGen/MachineInstrBuilder.h):

// Create a 'DestReg = mov 42' (rendered in X86 assembly as 'mov DestReg, 42')
// instruction and insert it at the end of the given MachineBasicBlock.
const TargetInstrInfo &TII = ...
MachineBasicBlock &MBB = ...
DebugLoc DL;
MachineInstr *MI = BuildMI(MBB, DL, TII.get(X86::MOV32ri), DestReg).addImm(42);

// Create the same instr, but insert it before a specified iterator point.
MachineBasicBlock::iterator MBBI = ...
BuildMI(MBB, MBBI, DL, TII.get(X86::MOV32ri), DestReg).addImm(42);

// Create a 'cmp Reg, 0' instruction, no destination reg.
MI = BuildMI(MBB, DL, TII.get(X86::CMP32ri8)).addReg(Reg).addImm(42);

// Create an 'sahf' instruction which takes no operands and stores nothing.
MI = BuildMI(MBB, DL, TII.get(X86::SAHF));

// Create a self looping branch instruction.
BuildMI(MBB, DL, TII.get(X86::JNE)).addMBB(&MBB);
MachineBasicBlock class

Contains a list of MachineInstr instances.

Roughly corresponds to the LLVM IR basic block, but there can be one to many mapping: one LLVM basic block map to multiple machine basic blocks.

Has a getBasicBlock method, which returns the LLVM basic block that it comes from.

MachineFunction class

Contains:

  • a list of MachineBasicBlocks instances,
  • a MachineConstantPool
  • a MachineFrameInfo, represents an abstract stack frame until prolog/epilog is inserted.
  • a MachineFunctionInfo
  • a MachineRegisterInfo

Corresponds one-to-one with the LLVM IR function input.

Passes in CodeGen

MachineFunctionPass:

~ 265 passes lives in llvm/include/llvm/CodeGen and llvm/lib/Target/*

  • class AsmPrinter; a driving class for all asm writers.
  • class MachineFunctionPrinterPass; a pass to dump the IR of a machine function.
  • class MIRPrintingPass; a pass prints out LLVM IR to an output stream using the MIR serialization format.
  • class PeepholeOptimizer
  • class IRTranslator
  • class InstructionSelect, SelectionDAGISel, FinalizeISel
  • class PEI, prolog epilog inserter. // llvm/lib/CodeGen/PrologEpilogInserter.cpp
  • class RegAllocFast, RegAllocPBQP,
  • class RegisterCoalescer
  • class ReachingDefAnalysis, LiveIntervals, LiveRegMatrix
  • class LiveStack, LiveVariables, Localizer
  • …

Initialization code in llvm/lib/CodeGen/CodeGen.cpp

llvm::initializeCodeGen()

Code Emission

reference LLVM CodeGen - Code Emission

Code emission is responsible for lowering from code generator abstractions (MachineFunction, MachineInstr, etc) down the the abstractions used by the MC Layer (MCInst, MCStreamer, etc). This is done by the following classes:

  • the (misnamed) target-independent AsmPrinter class.
    • It implements the general lowering process converting MachineFunction’s into MC label constructs.
    • target-specific subclasses of AsmPrinter, such as SparcAsmPrinter, MipsAsmPrinter
  • the .td files used to generate instruction printer automatically.
    • add $dst, $src, $src2
    • Need routines to print operands. Where???
  • <target>MCInstLower.cpp: code that lowers a MachineInstr to an MCInst
    • often target specific
    • is responsible for turning jump table entries, constant pool indicies, global variable address, etc, into MCLabels as appropriate.
    • is responsible for expanding pseudo ops used by the code generator into the actual machine instructions they corresponding to.
    • The MCInst that are generated by this are fed into the instructtion printer or the encoder.
  • the TargetLoweringObjectFile class

MC layer works at the level of abstraction of object files, it does not have a notion of functions, global variables, etc. Instead, it thinks about labels, directives, and instructions.

More info at MC Layer

CodeGen [MachineInstr] –> MC [MCInst] –> Object [ISA]

Automatic Instruction Emission
  • Target.td
  • TargetSelectionDAT.td
  • XXXInstrFormats.td
  • XXXInstrInfo.td
  • XXX.td

Prolog/Epilog insertion

Reference

  • Relocations in CodeGen

    • References: [](#) Relocation basics Relocation Sections in ELF Relocation during Linking in LLD ELFRelocationEntry // llvm/include/llvm/MC/MCELFObjectWriter.h struct ELFRelocationEntry { uint64_t Offset; // Where is the relocation. const MCSymbolELF *Symbol; // The symbol to relocate with. unsigned Type; // The type of the relocation. uint64_t Addend; // The addend to use. const MCSymbolELF *OriginalSymbol; // The original value of Symbol if we changed it.

  • lld

    • Reference [lld/ELF/Driver.cpp] lld/ELF/LinkerScript.cpp lld xxx.o -o xxx.exe lld –verbose How to determine which sections to write to exe LinkerDriver::link<ELFT> is the driving entry for the link to prepare different sections needed for the final executable. inputSecions hold a list of all sections from all object files. outputSections tracking sections in/out // lld/ELF/Driver.cpp // Do actual linking. Note that when this function is called, // all linker scripts have already been parsed.

  • Prolog Epilog

    • Q&A/Top Where is the return address being spilled? Where is the allocated stack frame being ‘destroyed’? Reference reference llvm/lib/CodeGen/PrologEpilogInserter.cpp Pass overview PEI (Prolog Epilog Inserter) pass creation: // void TargetPassConfig::addMachinePasses() { //... // Insert prolog/epilog code. Eliminate abstract frame index references... if (getOptLevel() != CodeGenOpt::None) { addPass(&PostRAMachineSinkingID); // sink COPY instructions which should be handled after RA. addPass(&ShrinkWrapID); // determine where the safe point to insert the prologue and epilogue.

  • Core ISel

    • References: llvm/lib/CodeGen/TargetPassConfig.cpp TargetPassConfig::addCoreISelPasses() will create the core passes needed for instruction selection in LLVM. It will choose one of three instruction selectors (FastISel, SelectionDAG, or GlobalISel) for the compilation, whichever is available or meets the configuration options. add finalization pass addPass(&FinalizeISelID); to expand pseudo-instructions emitted by ISel. print and verify the instructions selected machine code: printAndVerify("After Instruction Selection");. code TargetPassConfig::addCoreISelPasses() ```C++

  • Stack Frame

    • References: Target Code Generation Class of variables: Temporary variables: Local variables: Global variables: Stack Frame Layout Frame pointer (FP): ptr to beginning of stack frame (fixed) Stack pointer (SP): ptr to end of stack (can move). Stack frame hold space for: formals local variables return addresses (maybe) dynamic link (ptr to calling stack frame) (maybe) static link (ptr to lexically-enclosing stack frame) other run-time data (e.

  • ELF (OS side)

    • References: ELF specification ELF Tutorial (i386). 目的档格式（ELF）. two ELF views: linking and execution. a list of widely used sections in ELF. Linker and Libraries Guide – Object File Format CTOR/DTOR CFI (Call Frame Information) directives .cfi_personality directives, etc. Exception Frames .eh_frame section. Format is similar to .debug_frame section specified by DWARF standard. The .eh_frame and .eh_framehdr describes the call frames

  • Calling Convention

    • References: LLVM Language Reference – Calling Conventions Writing an llvm backend – Calling Convention TableGen for Calling Convention TargetCallingConv.td Calling convention from writing an llvm backend: To support target-specific calling conventions, _XXX_GenCallingConv.td uses interfaces (such as CCIfType and CCAssignToReg) that are defined in lib/Target/TargetCallingConv.td. TableGen uses the target descriptor file _XXX_GenCallingConv.td to generate the header file _XXX_GenCallingConv.inc, which is typically included in _XXX_ISelLowering.cpp. The inferfaces in _XXX_GenCalllingConv.

  • Linkers Loaders

    • References: Assemblers, Linkers, and Loaders, slides from Hakim Weatherspoon, Cornell, 2013. linkers and loaders, blog post. How to add a new target to LLD, slides from Peter Smith, Linaro, 2016. a figure of calling dynamic libraries over PLT/GOT Linker/Loader: binds more abstract names to more concrete names. Example: getline –> “the location 612 bytes from the beginning of the executable code in module iosys”. “the location 450 bytes beyond the beginning of the static data from this module” –> numberic address.

  • The `MC` Layer in LLVM

    • Q & A Where is the symbol table section being composed and written to the object file? References: llvm-mc LLVM the x86 disassembler LLVM CodeGen The LLVM MC Project This section is mostly from: llvm-mc, with partial info from LLVM CodeGen. Instruction Printer. MCInstPrint: MCInst -> textual representation. Not aware of sections/directives, so independent of object file format. A new lowering pass: MachineInstr -> MCInst.

  • Machine IR

    • Q&A How does it handle .got addressing? References: Machine IR Language Reference Welcome to the back end: the LLVM Machine Representation Tasks for LLVM Machine Representation: Resource Allocation: registers, stack space, … Lowering: ABI, Exception Handling, Debug Info, … Optimization: Peephole, Instruction/Block Scheduling, .. Basics Pass Manage Setup Pass manager pipeline is setup in TargetPassConfig. Target overrides methods to add, remove or replace passes.

  • Reg Alloc

    • Reference 1 https://web.stanford.edu/class/archive/cs/cs143/cs143.1128/lectures/17/Slides17.pdf Silhouette: https://github.com/jzhou76/Silhouette/blob/silhouette_llvm9/lib/Target/ARM/ARMSilhouetteLabelCFI.cpp#L59 https://github.com/jzhou76/Silhouette/blob/silhouette_llvm9/lib/Target/ARM/ARMSilhouetteSFI.cpp#L148 https://github.com/jzhou76/Silhouette/blob/silhouette_llvm9/lib/Target/ARM/ARMSilhouetteSTR2STRT.cpp#L65 reference ↩

  • Arch - Basics - Assembly

    • Assembler Directives Reference: GNU AS - assembler directives Pseudo Op-Codes .cpload directives, etc. CFI (Call Frame Information) directives .cfi_personality directives, etc. Exception Frames .eh_frame section. TI - MSP430 - Assembler Directives Assembler directives supply data to the program and control the assembly process. Directives are commands that are part of the assmbler syntax but are not related to the processor ISA. Assembler directives enable you to do the following:

  • Creating Backend for Cpu0

    • Q&A How to create a new section and store instruction and data’s metadata? like a new symbol table section? how to implement a new calling convention? Intrinsics? what is tablegen .td file? How it is used in LLVM infra? A domain specific language that describes functional modules and can be used to generate C++ code autotmatically. In LLVM, current usage of TableGen is to generate LLVM code generation code, and clang diagnostics and attributes; Instrinsics; Calling conventions; Register set, instruction set; More at TableGen what is regression test and how does it work?

Created Sep 29, 2019 // Last Updated Jul 8, 2021

If you could revise
the fundmental principles of
computer system design
to improve security...

... what would you change?