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?

    • Any code change will be tested against all existing (mostly unchanged) features of the system, to make sure new changes do not affect the existing features.

From writing an llvm backend:

  • Important backend (parent) classes:
    • TargetMachine class (SparcTargetMachine.cpp);
    • TableGen, RegisterInfo.td, TargetRegisterInfo class;
    • TargetInstrFormats.td, TargetInstrInfo.td, TargetInstrInfo class;
    • _XXX_ISelDAGToDAG.cpp, _XXX_ISelLowering.cpp (LLVM IR to native instructions)
    • AsmPrinter class, TargetAsmInfo classs (LLVM IR to assembly strings)
    • [optional] TargetSubtarget class (for -mcpu= and -mattr)
    • [optional] TargetJITInfo class (for JIT support, emmitting binary code directly into memory).

Create Backend

From Tutorial: Creating an LLVM Backend for the Cpu0 Architecture

To create a new backend:

Machine ID and Relocations

  • in LLVM root dir:
    • machine ID & name.
    • relocation records.

Root CMake

# cmake/config-ix.cmake
...
elseif (LLVM_NATIVE_ARCH MATCHES "mips")
  set(LLVM_NATIVE_ARCH Mips)
elseif (LLVM_NATIVE_ARCH MATCHES "cpu0")
  set(LLVM_NATIVE_ARCH Cpu0)
...

# CMakeLists.txt
set(LLVM_ALL_TARGETS
  ...
  Mips
  Cpu0
  ...
  )

Target triple.

// include/llvm/ADT/Triple.h

#undef mips

class Triple {
public:
  enum ArchType {
    ...
    mips,           // MIPS: mips, mipsallegrex, mipsr6
    mipsel,         // MIPSEL: mipsel, mipsallegrexe, mipsr6el
    mips64,         // MIPS64: mips64, mips64r6, mipsn32, mipsn32r6
    mips64el,       // MIPS64EL: mips64el, mips64r6el, mipsn32el, mipsn32r6el
    cheri,          // Capability Hardware Enhanced RISC Instructions
    ...
  }
  enum SubArchType {
    ...
    MipsSubArch_r6,
    MipsSubArch_cheri64,
    MipsSubArch_cheri128,
    MipsSubArch_cheri256,
    ...
  }

// lib/Support/Tripple.cpp

StringRef Triple::getArchTypeName(ArchType Kind) {
  switch (Kind) {
    case cheri:          return "cheri";
    case mips64:         return "mips64";
    case mips64el:       return "mips64el";
    case mips:           return "mips";
    case mipsel:         return "mipsel";
  }

static Triple::ArchType parseArch(StringRef ArchName) {
  auto AT = StringSwitch<Triple::ArchType>(ArchName)
    .Cases("mips64", "mips64eb", "mipsn32", "mipsisa64r6",
           "mips64r6", "mipsn32r6", Triple::mips64)
    .StartsWith("mips64c", Triple::mips64) // purecap/hybrid CHERI
    .Case("cheri", Triple::cheri)          // TODO: remove
    ...
    .Default(Triple::UnknownArch);
}

StringRef Triple::getEnvironmentTypeName(EnvironmentType Kind) {
  switch (Kind) {
  case UnknownEnvironment: return "unknown";
  case Android: return "android";
  case CheriPurecap: return "purecap";
  ...
  }

static Triple::EnvironmentType parseEnvironment(StringRef EnvironmentName) {
  return StringSwitch<Triple::EnvironmentType>(EnvironmentName)
    .StartsWith("cheripurecap", Triple::CheriPurecap)
    .StartsWith("purecap", Triple::CheriPurecap)
    .StartsWith("android", Triple::Android)
    ...
}

Relocation records

basics of relocation records

// include/llvm/Object/ELFObjectFile.h

template <class ELFT>
symbol_iterator
ELFObjectFile<ELFT>::getRelocationSymbol(DataRefImpl Rel) const {
}

template <class ELFT>
uint64_t ELFObjectFile<ELFT>::getRelocationType(DataRefImpl Rel) const {
}

template <class ELFT>
StringRef ELFObjectFile<ELFT>::getFileFormatName() const {
  bool IsLittleEndian = ELFT::TargetEndianness == support::little;
  switch (EF.getHeader()->e_ident[ELF::EI_CLASS]) {
  case ELF::ELFCLASS32:
    switch (EF.getHeader()->e_machine) {
    case ELF::EM_386:
      return "ELF32-i386";
    case ELF::EM_X86_64:
      return "ELF32-x86-64";
    case ELF::EM_MIPS:
      return "ELF32-mips";
    case ELF::EM_CPU0:        // llvm-objdump -t -r
      return "ELF32-cpu0";
    ...
    }
  case ELF::ELFCLASS64:
    switch (EF.getHeader()->e_machine) {
    case ELF::EM_386:
      return "ELF64-i386";
    case ELF::EM_X86_64:
      return "ELF64-x86-64";
    case ELF::EM_MIPS:
      return "ELF64-mips";
    ...
    }
  }

template <class ELFT> Triple::ArchType ELFObjectFile<ELFT>::getArch() const {
  bool IsLittleEndian = ELFT::TargetEndianness == support::little;
  switch (EF.getHeader()->e_machine) {
    case ELF::EM_X86_64:
    return Triple::x86_64;
    case ELF::EM_CHERI256: // CheriABI created with old compiler
      if (EF.getHeader()->e_ident[ELF::EI_CLASS] != ELF::ELFCLASS64)
        report_fatal_error("Invalid ELFCLASS!");
      if (IsLittleEndian)
        report_fatal_error("CHERI must be big endian!");
      return Triple::cheri;
    case ELF::EM_MIPS:
      switch (EF.getHeader()->e_ident[ELF::EI_CLASS]) {
        case ELF::ELFCLASS32:
          return IsLittleEndian ? Triple::mipsel : Triple::mips;
        case ELF::ELFCLASS64: {
          unsigned Arch = EF.getHeader()->e_flags & ELF::EF_MIPS_MACH;
          if (Arch == ELF::EF_MIPS_MACH_CHERI256 || Arch == ELF::EF_MIPS_MACH_CHERI128 || Arch == ELF::EF_MIPS_MACH_BERI) {
            if (IsLittleEndian)
              report_fatal_error("BERI/CHERI must be big endian!");
            return Triple::cheri;
          }
          return IsLittleEndian ? Triple::mips64el : Triple::mips64;
        }
        default:
          report_fatal_error("Invalid ELFCLASS!");
      }
    ...
    default:
      return Triple::UnknownArch;
  }
}
  
// include/llvm/BinaryFormat/ELF.h
enum{
  ...
  EM_MIPS = 8,           // MIPS R3000
  EM_RISCV = 243,         // RISC-V
  EM_CHERI256      = 0xC256, // 256-bit CHERI
  ...
}

enum : unsinged {
  EF_MIPS_NOREORDER = 0x00000001, // Don't reorder instructions
  EF_MIPS_PIC = 0x00000002,       // Position independent code
  EF_MIPS_CPIC = 0x00000004,      // Call object with Position independent code
  EF_MIPS_ABI2 = 0x00000020,      // File uses N32 ABI
  ...
   // ABI flags
  EF_MIPS_ABI_EABI32 = 0x00003000, // EABI in 32 bit mode.
  EF_MIPS_ABI_EABI64 = 0x00004000, // EABI in 64 bit mode.
  EF_MIPS_ABI_CHERIABI = 0x0000c000, // CHERIABI
  EF_MIPS_ABI = 0x0000f000,        // Mask for selecting EF_MIPS_ABI_ variant.

  // MIPS machine variant
  EF_MIPS_MACH_5500 = 0x00980000,    // NEC VR5500
  EF_MIPS_MACH_BERI = 0x00be0000, // BERI MIPS
  EF_MIPS_MACH_CHERI128 = 0x00c10000, // CHERI 128-bit
  EF_MIPS_MACH_CHERI256 = 0x00c20000, // CHERI 256-bit
  EF_MIPS_MACH = 0x00ff0000,         // EF_MIPS_MACH_xxx selection mask
  ...
}


// ELF Relocation types for Mips
enum {
#include "ELFRelocs/Mips.def"
};

Initial .td Files

.td files may be used to describe

  • a target’s register set, instruction set;
  • scheduling information for instructions;
  • calling conventions;

.td files will be translated into C++ source code (.inc) by tablegen.

Every backend has its own .td file to define target infromation.

For Mips:

  • lib/Target/Mips/Mips.td
  • lib/Target/Mips/MipsRegisterInfo.td
  • lib/Target/Mips/MipsInstrInfo.td
  • lib/Target/Mips/MipsInstrFormats.td
  • lib/Target/Mips/MipsInstrCheri.td
  • lib/Target/Mips/MipsInstrFormatsCheri.td

    // lib/Target/Mips/Mips.td
    
    def Cap64      : HwMode<"+cheri64,-cheri128,-cheri256">;
    def Cap128     : HwMode<"+cheri128,-cheri64,-cheri256">;
    def Cap256     : HwMode<"+cheri256,-cheri128,-cheri64">;
    
    def FeatureMipsCheri   : SubtargetFeature<"chericap", "IsCheri", "true",
                                "Supports the CHERI capability coprocessor",
                                [FeatureMipsBeri]>;
    def FeatureMipsCheri64 : SubtargetFeature<"cheri64", "IsCheri64", "true",
                                "Capabilities are 64 bits",
                                [FeatureMipsCheri]>;
    def FeatureMipsCheri128 : SubtargetFeature<"cheri128", "IsCheri128", "true",
                                "Capabilities are 128 bits",
                                [FeatureMipsCheri]>;
    def FeatureMipsCheri256 : SubtargetFeature<"cheri256", "IsCheri256", "true",
                                "Capabilities are 256 bits",
                                [FeatureMipsCheri]>;
    def FeatureCheriExactEquals :
    SubtargetFeature<"cheri-exact-equals", "UseCheriExactEquals", "true",
                   "CHERI capability comparison are exact (comparing all bits"
                   " instead of just the address).", [FeatureMipsCheri]>;
    
    
    class Proc<string Name, list<SubtargetFeature> Features>
    : ProcessorModel<Name, MipsGenericModel, Features>;
    
    def : Proc<"generic", [FeatureMips32]>;
    def : ProcessorModel<"beri", BeriModel,
                     [FeatureMipsBeri]>;
    def : ProcessorModel<"cheri256", BeriModel,
                     [FeatureMipsCheri256, FeatureMipsCheri, FeatureMipsBeri]>;
    def : ProcessorModel<"cheri128", BeriModel,
                     [FeatureMipsCheri128, FeatureMipsCheri, FeatureMipsBeri]>;
    
    // MipsRegisterInfo.td
    
    // We have banks of 32 registers each.
    class MipsReg<bits<16> Enc, string n> : Register<n> {
    let HWEncoding = Enc;
    let Namespace = "Mips";
    }
    ...
    
    // Mips Hardware Registers
    class HWR<bits<16> Enc, string n> : MipsReg<Enc, n>;
    
    // CHERI Hardware Registers
    class CheriHWR<bits<16> Enc, string n> : MipsReg<Enc, n>;
    
    // CHERI capability registers
    // Uncomment the subregs lines to pretend we are super-registers of the MIPS
    // integer registers. This is not true but could simulate a merged register file
    class CAP<bits<16> Enc, string n, list<Register> subregs = []>
    // : MipsRegWithSubRegs<Enc, n, subregs> {
    : MipsRegWithSubRegs<Enc, n, []> {
    // Pretend that we have sub-registers for the purpose of register allocation
    // let SubRegIndices = [sub_64];
    let SubRegIndices = [];
    }
    
    // A capability register that "aliases" one of the MIPS registers
    // We use this to simulate a merged register file for the purpose of regalloc.
    // Note: This is a poor approximation, but if we mark the callee-saved registers
    // as aliased we should no longer get large performance wins over MIPS
    class AliasCAP<bits<16> Enc, string n, list<Register> aliases = []>
    : MipsRegWithSubRegs<Enc, n, []> {
    // Pretend that we have sub-registers for the purpose of register allocation
    // Unfortunately, this means that $s0 will also be saved if we write to $c18
    // There must be an easier way to tell regalloc to avoid allocating one
    // let Aliases = aliases;
    }
    
    ...
    
    def CapRegType : ValueTypeByHwMode<[Cap64, Cap128, Cap256, DefaultMode],
                                   [iFATPTR64, iFATPTR128, iFATPTR256, iFATPTR128]>;
    
    def CheriGPR : RegisterClass<"Mips", [CapRegType], 256, (add
    C1, C2, C3, C4, C5, C6, C7, C8, C9,
    C10, C11, C12, C13, C14, C15, C16, C17, C18, C19,
    C20, C21, C22, C23, C24, C25, C26, C27, C28, C29,
    C30, C31)> {
    let RegInfos = RegInfoByHwMode<[Cap64, Cap128, Cap256, DefaultMode],
       [RegInfo<64,64,64>, RegInfo<128,128,128>, RegInfo<256,256,256>, RegInfo<128,128,128>]>;
    }
    def FakeCheriRegs : RegisterClass<"Mips", [iFATPTR256], 256, (add DDC)>, Unallocatable;
    
    // Cap register class which includes both CNULL and DDC. This is not a
    // constraint used by any instructions, it is used as a common super-class.
    // This approach is copied from AArch64RegisterInfo.td
    def CheriRegsAll : RegisterClass<"Mips", [CapRegType], 256, (add CheriGPR, CNULL, DDC)>, Unallocatable {
    let RegInfos = RegInfoByHwMode<[Cap64, Cap128, Cap256, DefaultMode],
       [RegInfo<64,64,64>, RegInfo<128,128,128>, RegInfo<256,256,256>, RegInfo<128,128,128>]>;
    }
    
    def CheriGPROrCNull : RegisterClass<"Mips", [CapRegType], 256, (add CNULL, CheriGPR)>, Unallocatable {
    let RegInfos = RegInfoByHwMode<[Cap64, Cap128, Cap256, DefaultMode],
       [RegInfo<64,64,64>, RegInfo<128,128,128>, RegInfo<256,256,256>, RegInfo<128,128,128>]>;
    }
    def CheriGPROrDDC : RegisterClass<"Mips", [CapRegType], 256, (add DDC, CheriGPR)>, Unallocatable {
    let RegInfos = RegInfoByHwMode<[Cap64, Cap128, Cap256, DefaultMode],
       [RegInfo<64,64,64>, RegInfo<128,128,128>, RegInfo<256,256,256>, RegInfo<128,128,128>]>;
    }
    
    def CheriHWRegs : RegisterClass<"Mips", [CapRegType], 256, (sequence "CAPHWR%u", 0, 31)>, Unallocatable {
    let RegInfos = RegInfoByHwMode<[Cap64, Cap128, Cap256, DefaultMode],
         [RegInfo<64,64,64>, RegInfo<128,128,128>, RegInfo<256,256,256>, RegInfo<128,128,128>]>;
    }
    
    - lib/Target/Mips/MipsInstrFormats.td
    ...
    
    def CheriAsmOperand : MipsAsmRegOperand {
    let Name = "CheriAsmReg";
    let PredicateMethod = "isCheriAsmReg";
    let DiagnosticType = "CheriAsmReg";
    }
    
    def CheriAsmOperand0IsDDC : MipsAsmRegOperand {
    let Name = "CheriAsmReg0IsDDC";
    let PredicateMethod = "isCheriAsmReg0IsDDC";
    let DiagnosticType = "CheriAsmReg0IsDDC";
    }
    
    ...
    
    def CheriHWRegsAsmOperand : MipsAsmRegOperand {
    let Name = "CheriHWRegsAsmReg";
    let PredicateMethod = "isCheriHWAsmReg";
    }
    
    ...
    
    def CheriOpnd : RegisterOperand<CheriGPROrCNull> {
    let ParserMatchClass = CheriAsmOperand;
    let OperandNamespace = "Mips";
    let OperandType = "OPERAND_CHERI_GPR_OR_NULL";
    }
    
    def CheriOpnd0IsDDC : RegisterOperand<CheriGPROrDDC> {
    let ParserMatchClass = CheriAsmOperand0IsDDC;
    let OperandNamespace = "Mips";
    let OperandType = "OPERAND_CHERI_GPR_OR_DDC";
    }
    
    ...
    
    def CheriHWRegsOpnd : RegisterOperand<CheriHWRegs> {
    let ParserMatchClass = CheriHWRegsAsmOperand;
    }

.td files basics

the class definition describes how data is laid out, and definitions act as the specific instance of the class.

def is used to create instance of class.

let to override the existed field from parent class;

declare a new field for a class:

cmake changes for td

in lib/Target/Mips/

  • CMakeLists.txt:

    • add .td file name;
    • add tablegen command to generate .inc
    • use add_public_tablegen_target(xxxCommonTableGen) to define xxxCommonTableGen using tablegen (see cmake/modules/TableGen.cmake)
  • LLVMBuild.txt

    • subdirs, name, required libs, etc.

Register Target

see here

MIPS call

MIPS stack frame

pass arguments in function call:

  • pass in registers
  • pass in stack

    int gI = 100;
    
    int sum_i(int x1, int x2, int x3, int x4, int x5, int x6)
    {
    int sum = gI + x1 + x2 + x3 + x4 + x5 + x6;
      
    return sum; 
    }
    
    int main()
    { 
    int a = sum_i(1, 2, 3, 4, 5, 6);  
      
    return a;
    }
    # clang -target mips-unknown-linux-gnu -c ch9_1.cpp -emit-llvm -o ch9_1.bc
    # llc -march=mips -relocation-model=pic -filetype=asm ch9_1.bc -o ch9_1.mips.s
    # cat ch9_1.mips.s
    
    .section .mdebug.abi32
    .previous
    .file "ch9_1.bc"
    .text
    .globl  _Z5sum_iiiiiii
    .align  2
    .type _Z5sum_iiiiiii,@function
    .set  nomips16                # @_Z5sum_iiiiiii
    .ent  _Z5sum_iiiiiii
    _Z5sum_iiiiiii:
    .cfi_startproc
    .frame  $sp,32,$ra
    .mask   0x00000000,0
    .fmask  0x00000000,0
    .set  noreorder
    .set  nomacro
    .set  noat
    # BB#0:
    addiu $sp, $sp, -32
    $tmp1:
    .cfi_def_cfa_offset 32
    sw  $4, 28($sp)
    sw  $5, 24($sp)
    sw  $t9, 20($sp)
    sw  $7, 16($sp)
    lw  $1, 48($sp) // load argument 5
    sw  $1, 12($sp)
    lw  $1, 52($sp) // load argument 6
    sw  $1, 8($sp)
    lw  $2, 24($sp)
    lw  $3, 28($sp)
    addu  $2, $3, $2
    lw  $3, 20($sp)
    addu  $2, $2, $3
    lw  $3, 16($sp)
    addu  $2, $2, $3
    lw  $3, 12($sp)
    addu  $2, $2, $3
    addu  $2, $2, $1
    sw  $2, 4($sp)
    jr  $ra
    addiu $sp, $sp, 32
    .set  at
    .set  macro
    .set  reorder
    .end  _Z5sum_iiiiiii
    $tmp2:
    .size _Z5sum_iiiiiii, ($tmp2)-_Z5sum_iiiiiii
    .cfi_endproc
    
    .globl  main
    .align  2
    .type main,@function
    .set  nomips16                # @main
    .ent  main
    main:
    .cfi_startproc
    .frame  $sp,40,$ra
    .mask   0x80000000,-4
    .fmask  0x00000000,0
    .set  noreorder
    .set  nomacro
    .set  noat
    # BB#0:
    lui $2, %hi(_gp_disp)
    ori $2, $2, %lo(_gp_disp)
    addiu $sp, $sp, -40
    $tmp5:
    .cfi_def_cfa_offset 40
    sw  $ra, 36($sp)            # 4-byte Folded Spill
    $tmp6:
    .cfi_offset 31, -4
    addu  $gp, $2, $25
    sw  $zero, 32($sp)
    addiu $1, $zero, 6
    sw  $1, 20($sp) // Save argument 6 to 20($sp)
    addiu $1, $zero, 5
    sw  $1, 16($sp) // Save argument 5 to 16($sp)
    lw  $25, %call16(_Z5sum_iiiiiii)($gp)
    addiu $4, $zero, 1    // Pass argument 1 to $4 (=$a0)
    addiu $5, $zero, 2    // Pass argument 2 to $5 (=$a1)
    addiu $t9, $zero, 3
    jalr  $25
    addiu $7, $zero, 4
    sw  $2, 28($sp)
    lw  $ra, 36($sp)            # 4-byte Folded Reload
    jr  $ra
    addiu $sp, $sp, 40
    .set  at
    .set  macro
    .set  reorder
    .end  main
    $tmp7:
    .size main, ($tmp7)-main
    .cfi_endproc

argument passing mechanism implementation

More documentation/tutorials:

  • How Globals are written to the object files by Compilers?
  • Notes $gp value can be a fixed address (static or pic relocation with static link), the start of global address table. All global varaible names in C are statically linked 1 a dyn loaded address (pic relocation with dynamic link) Reference: Cpu0 – Global Variables The global variable DAG translation is different from local variable ones. It creates IR DAG nodes at run time in backend C++ code according to llc -relocation-model option while the other DAG just do IR DAG to Machine DAG translation directly according to the input file of IR DAGs(except the Pseudo instruction REtLR used in Chapter 3_4).

  • Obj Gen
  • Reference 1 llc -march=cpu0 llc -march=cpu0 -relocation-model=pic -filetype=obj ch4_1_match.bc -o ch4_1_match.cpu0.o LLVM Code: Cpu0InstPrinter.cpp MCTargetDesc/CMakeLists.txt MCTargetDesc/Cpu0AsmBackend.h MCTargetDesc/Cpu0AsmBackend.cpp MCTargetDesc/Cpu0BaseInfo.h MCTargetDesc/Cpu0ELFObjectWriter.cpp MCTargetDesc/Cpu0FixupKinds.h MCTargetDesc/Cpu0MCCodeEmitter.h MCTargetDesc/Cpu0MCCodeEmitter.cpp MCTargetDesc/Cpu0MCExpr.h MCTargetDesc/Cpu0MCExpr.cpp MCTargetDesc/Cpu0MCTargetDesc.h MCTargetDesc/Cpu0MCTargetDesc.cpp MCTargetDesc/Cpu0MCInstLower.h include/llvm/MC/MCRegisterInfo.h Cpu0RegisterInfo.td cmake_debug_build/lib/Target/Cpu0/Cpu0GenRegisterInfo.inc Cpu0InstrInfo.td src/lib/MC/MCELFStreamer.cpp Cpu0 – Generating Object Files ↩

  • Regression
  • LLVM has its test cases (regression test) for each backend to verify the backend compiler without implementing any simulator or real hardware platform. regression test for arch in ./llvm/test/src/test/CodeGen/ To run: cheri# pwd /root/cheri/llvm-project/llvm/test/CodeGen/Mips/cheri cheri# /llvm-build-bin/llvm-lit cheri-sandbox-vaargs.ll llvm-lit: /root/cheri/llvm-project/llvm/utils/lit/lit/llvm/config.py:317: note: Running tests for CHERI_CAP_SIZE=16 llvm-lit: /root/cheri/llvm-project/llvm/utils/lit/lit/llvm/config.py:405: note: using clang: /root/sva/cheri/bsd112_sync_root/root/cheri/build/llvm-project-build/bin/clang llvm-lit: /root/cheri/llvm-project/llvm/utils/lit/lit/llvm/subst.py:127: note: Did not find llvm-exegesis in /root/sva/cheri/bsd112_sync_root/root/cheri/build/llvm-project-build/./bin llvm-lit: /root/cheri/llvm-project/llvm/utils/lit/lit/llvm/subst.py:127: note: Did not find llvm-mca in /root/sva/cheri/bsd112_sync_root/root/cheri/build/llvm-project-build/./bin llvm-lit: /root/cheri/llvm-project/llvm/utils/lit/lit/llvm/subst.py:127: note: Did not find llvm-rc in /root/sva/cheri/bsd112_sync_root/root/cheri/build/llvm-project-build/.

Created Aug 7, 2019 // Last Updated Jul 15, 2020

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

... what would you change?