path: root/bxgen.c

#if 0 /*
#/  ================================================================
#/
#/    bxgen.c
#/
#/  Binary executable code generation and linking.
#/  Compiler backend.
#/
#/  ----------------------------------------------------------------
#/
#/  Qualities
#/
#/  - Compiler backend in the form of a library
#/  - Single source file
#/  - Simple and flexible API
#/  - No external dependencies
#/  - No configuration required
#/  - No dynamic memory management
#/  - Easy cross-compilation
#/  - Platform-independent host
#/
#/  Inspirations
#/
#/  - tinycc  https://repo.or.cz/w/tinycc.git
#/  - Cuik    https://github.com/RealNeGate/Cuik
#/  - QBE     https://c9x.me/compile/
#/
#/  To-Do list
#/
#/  - Library
#/    - Terminal color option
#/    - Use 0 for UNDEFINED. Make the zero value useful
#/    - String table for names and arrays
#/    - Proper prefixes for identifiers
#/    - Effective entity allocation
#/    - Improve error handling
#/    - Memory reallocation when necessary
#/    - Multithreading
#/  - Codegen
#/    - Architectures
#/      - x86_64
#/      - i386
#/      - RISC-V
#/      - ARM
#/      - WebAssembly
#/    - Implicit procedure prototypes
#/    - Static single-assignment
#/    - Sea of Nodes
#/    - Optimization layers
#/    - JIT
#/    - Debug info
#/    - C compiler and self-compilation
#/    - Meta codegen  >:3
#/  - Linker
#/    - Formats
#/      - ELF
#/      - COFF
#/      - PE
#/      - OMF
#/      - Mach-O
#/    - Linking with libc
#/    - Statically-linked executable
#/    - Object file
#/    - Static library
#/    - Dynamic-link library
#/    - Dynamically-linked executable
#/    - GNU ld script
#/    - GOT and PLT
#/    - Thread-local storage
#/    - Static libraries
#/    - Dynamic libraries
#/    - Unused dependencies elimination
#/  - Comprehensive test suite
#/  - Built-in standard library
#/    - Terminal
#/    - Graphics  >:3
#/    - Input devices  >:3
#/    - Math
#/    - Soft floating-point arithmeric
#/    - File I/O
#/    - Threads
#/    - Networking  >:3
#/    - Audio  >:3
#/
#/  Bugs
#/
#/  - ...
#/
#/  Done features
#/
#/  - Library
#/    - IO static dispatch
#/    - Correct serialization for endianness
#/    - Proper error handling
#/  - Codegen
#/    - Implicit exit after ret from entry point
#/
#/  ----------------------------------------------------------------
#/
#/    (C) 2024 Mitya Selivanov <guattari.tech>, MIT License
#/
#/  ================================================================
#/
#/    Self-compilation shell script
#/
SRC=${0##*./}
BIN=${SRC%.*}
gcc                                             \
  -Wall -Wextra -Werror -pedantic               \
  -Wno-old-style-declaration                    \
  -Wno-missing-braces                           \
  -Wno-unused-variable                          \
  -Wno-unused-but-set-variable                  \
  -Wno-unused-parameter                         \
  -O0                                           \
  -fsanitize=undefined,address,leak -mshstk     \
  -o $BIN $SRC &&                               \
  ./$BIN $@ &&                                  \
  rm $BIN
exit $? # */
#endif
//  ================================================================
//
//    Compilation options
//
//  ================================================================

#ifndef IMPLEMENTATION
#define IMPLEMENTATION 1
#endif

#ifndef HELPERS
#define HELPERS 1
#endif

#ifndef TESTING
#define TESTING 1
#endif

#ifndef LOG_LEVEL
#define LOG_LEVEL 5
#endif

#ifndef LOG_BLOCKING
#define LOG_BLOCKING 0
#endif

#ifndef TRACE_BLOCKING
#define TRACE_BLOCKING 1
#endif

//  ================================================================
//
//    Basic declarations
//
//  ================================================================

#define VERSION "dev"

typedef signed char        i8;
typedef signed short       i16;
typedef signed int         i32;
typedef signed long long   i64;
typedef unsigned char      u8;
typedef unsigned short     u16;
typedef unsigned int       u32;
typedef unsigned long long u64;
typedef float              f32;
typedef double             f64;
typedef signed char        b8;  // 8-bit boolean
typedef char               c8;  // 8-bit character

//  ================================================================
//
//    IR data declarations
//
//  ================================================================

enum {
  //  Log level
  ERROR = 1,
  WARNING,
  INFO,
  VERBOSE,
  TRACE,

  //  Limits
  //

  STRING_TABLE_ALIGNMENT = 16, // TODO

  //  TEMP
  MAX_NUM_OBJECT_FILES   =         10 * 1024,
  MAX_NUM_SECTIONS       =   2 * 1024 * 1024,
  MAX_NUM_SYMBOLS        =   2 * 1024 * 1024,
  MAX_NUM_RELS           =        100 * 1024,
  MAX_OBJECT_FILE_SIZE   =  10 * 1024 * 1024, //  10 MB
  MAX_DEPENDENCIES_SIZE  =  50 * 1024 * 1024, //  50 MB
  MAX_NOT_FOUND_SIZE     =         10 * 1024, //  10 KB
  MAX_CODE_SIZE          =        100 * 1024, // 100 KB
  MAX_OUTPUT_SIZE        =  20 * 1024 * 1024, //  20 MB

  MAX_PATH_SIZE          = 10 * 1024,
  MAX_LITERAL_SIZE       = 400,
  MAX_NAME_SIZE          = 80,
  MAX_NUM_PROCS          = 40,
  MAX_NUM_NODES          = 60,
  MAX_NUM_LINKS          = 20,
  MAX_NUM_ARGS           = 20,
  MAX_NUM_ENTITIES       = 16 * 1024,

  //  For indices
  UNDEFINED = -1,

  //  Sea of Nodes flow type
  //

  FLOW_DATA = 0,
  FLOW_CONTROL,

  //  Semantic node operations
  //

  DATA_PTR = 0,
  DATA_I8,
  DATA_I16,
  DATA_I32,
  DATA_I64,
  DATA_F32,
  DATA_F64,
  DATA_REFERENCE,
  CTRL_CALL,
  CTRL_RET,

  //  Calling conventions

  CONV_UNKNOWN = 0,
  CONV_CDECL,
  CONV_STDCALL,
  CONV_FASTCALL,
  CONV_THISCALL,

  //  Primitive data types
  //

  TYPE_PTR = 0,
  TYPE_I32,

  //  Unit types
  //

  UNIT_CODE = 0,
  UNIT_LIBRARY_OBJECT,
  UNIT_LIBRARY_STATIC,
  UNIT_LIBRARY_DYNAMIC,

  //  Entity types
  //

  ENTITY_NODE = 0,
  ENTITY_PROC,
  ENTITY_UNIT,

  //  IO dispatch operations
  //

  IO_OPEN_READ = 0,
  IO_OPEN_WRITE,
  IO_CLOSE,
  IO_SEEK,
  IO_TELL,
  IO_READ,
  IO_WRITE,
  IO_CHMOD_EXE,

  IO_SEEK_CURSOR = 0,
  IO_SEEK_BEGIN,
  IO_SEEK_END,

  //  Formats
  //

  FORMAT_ELF  = 1,
  FORMAT_COFF,
  FORMAT_PE,
  FORMAT_OMF,
  FORMAT_MATCH_O,

  //  Architecture
  //

  ARCH_RISC_V = 1,
  ARCH_I386,
  ARCH_X86_64,
  ARCH_ARM32,
  ARCH_ARM64,

  //  Relocations
  //

  REL_ADD_INSTRUCTION_ADDRESS,
  REL_ADD_RODATA_ADDRESS,
  REL_ADD_PROC_ADDRESS,
};

//  TODO
typedef struct {
  i64 size;
  i64 offset;
} String_Handle;

//  TODO
typedef struct {
  i64 size;
  i64 capacity;
  u8 *data;
  u8 *occupied;
} Strint_Table;

typedef i64 Var;

typedef struct {
  i64 address;
  i64 num_bytes;
  union {
    // TODO use string table
    i8   as_i8 [MAX_LITERAL_SIZE];
    i16  as_i16[MAX_LITERAL_SIZE / 2];
    i32  as_i32[MAX_LITERAL_SIZE / 4];
    i64  as_i64[MAX_LITERAL_SIZE / 8];
    u8   as_u8 [MAX_LITERAL_SIZE];
    u16  as_u16[MAX_LITERAL_SIZE / 2];
    u32  as_u32[MAX_LITERAL_SIZE / 4];
    u64  as_u64[MAX_LITERAL_SIZE / 8];
    f32  as_f32[MAX_LITERAL_SIZE / sizeof(f32)];
    f64  as_f64[MAX_LITERAL_SIZE / sizeof(f64)];
  };
} Literal;

typedef struct {
  i16 num_vals;
  Var vals[MAX_NUM_ARGS];
} Ret;

typedef struct {
  //    NOTE
  //    We may call a local procedure by it's id,
  //    or a global procedure by name.

  u16 convention; // can be implicitly retrieved from the procedure
  i64 target_proc;
  i64 target_name_size;
  c8  target_name[MAX_NAME_SIZE]; // TODO use string table
  i64 num_args;
  Var args[MAX_NUM_ARGS];
} Call;

//  A semantic node is an operation with optional data
//  and possible references to other nodes.

typedef struct {
  u16 op;
  i64 index_in_proc;
  union {
    Literal lit;
    Var     ref;
    Ret     ret;
    Call    call;
  };
} Node;

//  A procedure is a collection of semantic nodes
//  and has a string name.

typedef struct {
  b8  emit_done;
  i64 offset;
} Proc_Codegen;

typedef struct {
  u16          convention;
  i64          name_size;
  c8           name[MAX_NAME_SIZE]; // TODO use string table
  i64          num_nodes;
  i64          nodes[MAX_NUM_NODES];
  i64          ret_index;
  i64          unit;
  i64          index_in_unit;
  Proc_Codegen codegen;
} Proc;

//  A compilation unit is a collection of procedures.
//

typedef struct {
  u16 type;
  i64 entry_point_index;
  i64 name_size;
  c8  name[MAX_NAME_SIZE]; // TODO use string table
  i64 num_procs;
  i64 procs[MAX_NUM_PROCS];
  i64 num_links;
  i64 links[MAX_NUM_LINKS];
} Unit;

//  An entity can be any of:
//  - Node
//  - Proc
//  - Unit
//
//  Every entity can be referenced by it's unique index
//  in the entity pool.

typedef struct {
  b8  is_enabled;
  u16 type;
  union {
    Node node;
    Proc proc;
    Unit unit;
  };
} Entity;

typedef struct {
  u16 type;
  i64 offset;
  i64 size;
  i64 value;
  i64 name_size;
  c8 *name;
  i64 proc;
} Rel_Entry;

typedef struct {
  i64 name_size;
  c8 *name;
  i64 address;
  i64 size;
} Symbol_Entry;

//  Pool, a collection of all entities.
//
//    NOTE
//    We use one single large memory block for *everything*.

typedef struct {
  i64     num_entities;
  i64     capacity;
  Entity *entities;
} Pool;

//  TEMP Codegen and linker buffers
//  TODO Use string table for buffers also.

typedef struct {
  i64        max_num_rels;
  i64        max_code_size;
  i64        max_rodata_size;
  i64        entry_point;
  i64        num_rels;
  i64        offset_code;
  i64        offset_rodata;
  Rel_Entry *rels;
  u8 *       buffer_code;
  u8 *       buffer_rodata;
} Codegen_Context;

typedef struct {
  i64 max_obj_file_size;
  i64 max_dependencies_size;
  i64 max_num_obj_files;
  i64 max_num_sections;
  i64 max_num_symbols;
  i64 max_not_found_size;
  i64 max_output_size;

  i64 num_obj_files;

  u8 *          obj_file_buffer;
  u8 *          dependencies_buffer;
  i64 *         obj_file_offsets;
  i64 *         section_offsets;
  i64 *         section_addresses;
  Symbol_Entry *symbols;
  c8 *          not_found_buffer;
  u8 *          output_buffer;
} Linker_Context;

//  ================================================================
//
//    API declarations
//
//  ================================================================

#ifdef __cplusplus
extern "C" {
#endif

//  ================================================================
//
//  Hooks
//
//    NOTE
//    Shoud be implemented on the user side.
//    See: `* Helper procedures`
//
void dispatch_assert(b8 condition, c8 *message, u32 line, c8 *file);
void dispatch_log(i32 log_level, u32 line, c8 *file, c8 *format, ...);
void dispatch_io(u16 op, i64 *id, i64 *size, void *data, void *user_data);

//  ================================================================
//
//  Main API
//
i64  pool_add(Pool *pool, Entity data);
void pool_remove(Pool *pool, i64 entity, u16 type);

i64  node_init(Pool *pool, Node data);
void node_destroy(Pool *pool, i64 node);
i64  node_data_reference(Pool *pool, i64 node);
i64  node_data_array_c8(Pool *pool, i64 size, c8 *data);
i64  node_data_ptr(Pool *pool, u64 address);
i64  node_data_i32(Pool *pool, i32 value);
i64  node_data_i64(Pool *pool, i64 value);
i64  node_ctrl_call(Pool *pool, i64 target_proc, i64 num_args, Var *args);
i64  node_ctrl_call_by_name(Pool *pool, i64 name_size, c8 *name, i64 num_args, Var *args);
i64  node_ctrl_ret(Pool *pool, i64 num_values, Var *values);

i64  proc_init(Pool *pool);
void proc_destroy(Pool *pool, i64 proc);
void proc_set_convention(Pool *pool, i64 proc, u16 convention);
void proc_set_name(Pool *pool, i64 proc, i64 name_size, c8 *name);
void proc_node_add(Pool *pool, i64 proc, i64 node);
void proc_node_remove(Pool *pool, i64 proc, i64 node);

i64  unit_init(Pool *pool, u16 type);
void unit_destroy(Pool *pool, i64 unit);
void unit_proc_add(Pool *pool, i64 unit, i64 proc);
void unit_proc_remove(Pool *pool, i64 unit, i64 proc);
void unit_link_add(Pool *pool, i64 unit, i64 link_unit);
void unit_link_remove(Pool *pool, i64 unit, i64 link_unit);
void unit_set_name(Pool *pool, i64 unit, i64 name_size, c8 *name);
void unit_set_entry_point(Pool *pool, i64 unit, i64 entry_point_proc);
void unit_write(Pool *pool, Codegen_Context *codegen, Linker_Context *linker, i64 unit, u16 format, u16 arch, i64 io_id, void *io_user_data);

i64  io_open_read(i64 name_size, c8 *name, void *user_data);
i64  io_open_write(i64 name_size, c8 *name, void *user_data);
void io_close(i64 f, void *user_data);
b8   io_seek(i64 f, i64 offset, u16 origin, void *user_data);
i64  io_tell(i64 f, void *user_data);
i64  io_read(i64 f, i64 size, void *data, void *user_data);
i64  io_write(i64 f, i64 size, void *data, void *user_data);
void io_chmod_exe(i64 f, void *user_data);

//  ================================================================
//
//  Helpers API
//
#ifndef DISABLE_HELPERS

i64  n_ref(i64 proc, i64 node);
i64  n_ptr(i64 proc, u64 address);
i64  n_str(i64 proc, c8 *value);
i64  n_i32(i64 proc, i32 value);
i64  n_i64(i64 proc, i64 value);
i64  n_call(i64 proc, i64 target_proc, i64 num_args, Var *args);
i64  n_call_by_name(i64 proc, c8 *name, i64 num_args, Var *args);
i64  n_ret(i64 proc, i64 num_vals, Var *vals);

i64  p_new(i64 unit, c8 *name);
i64  p_new_entry(i64 unit);
void p_add(i64 proc, i64 node);

i64  u_new();
void u_add(i64 unit, i64 proc);
void u_entry_point(i64 unit, i64 proc);
void u_elf_x86_64(i64 unit, c8 *output_file_name);

void l_code(i64 unit, i64 link_unit);
void l_object(i64 unit, c8 *object_library);
void l_static(i64 unit, c8 *static_library);
c8 * l_find(c8 *name);

#define ARGS(...)                                  \
  (sizeof((Var[]) { __VA_ARGS__ }) / sizeof(Var)), \
  (Var[]) { __VA_ARGS__ }
#define N_CALL(proc, target_proc, ...)  n_call((proc), (target_proc), ARGS(__VA_ARGS__))
#define N_CALL_BY_NAME(proc, name, ...) n_call_by_name((proc), (name), ARGS(__VA_ARGS__))
#define N_RET(proc, ...)                n_ret((proc), ARGS(__VA_ARGS__))

#endif
//  ================================================================

#ifdef __cplusplus
}
#endif

//  ================================================================
//
//    IMPLEMENTATION
//
//  ================================================================
//
//  * Basic utilities
//
//  ================================================================

#if IMPLEMENTATION

#ifdef __cplusplus
#error Implementation code should be compiled with a C compiler!
#endif

#ifndef NULL
#define NULL ((void *) 0)
#endif

#ifdef NDEBUG
#  define CHECK(condition, error_string, fail_result)          \
    do {                                                       \
      b8 ok_ = (condition);                                    \
      if (!ok_) {                                              \
        dispatch_log(ERROR, __LINE__, __FILE__, error_string); \
        return fail_result;                                    \
      } \
    } while (0)
#else
#  define CHECK(condition, error_string, fail_result) \
    dispatch_assert((condition), error_string, __LINE__, __FILE__)
#endif

#ifdef NDEBUG
#  define LAX(condition, error_string)                           \
    do {                                                         \
      if (!(condition))                                          \
        dispatch_log(WARNING, __LINE__, __FILE__, error_string); \
    } while (0)
#else
#  define LAX(condition, error_string) \
    dispatch_assert((condition), error_string, __LINE__, __FILE__)
#endif

#ifdef NDEBUG
#  define FAIL(error_string, fail_result)                  \
    dispatch_log(ERROR, __LINE__, __FILE__, error_string); \
    return fail_result
#else
#  define FAIL(error_string, fail_result)                 \
    dispatch_assert(0, error_string, __LINE__, __FILE__); \
    return fail_result
#endif

#define LOG(log_level, ...)                                     \
  do {                                                          \
    if (log_level <= LOG_LEVEL)                                 \
      dispatch_log(log_level, __LINE__, __FILE__, __VA_ARGS__); \
  } while (0)

i64 bx_align(i64 x, i64 a) {
  CHECK(a > 0, "Invalid arguments", 0);
  return x + ((a - (x % a)) % a);
}

void mem_set(void *dst, u8 val, i64 size) {
  CHECK(dst != NULL, "Invalid arguments",);
  CHECK(size > 0,    "Invalid size",);

  for (i64 i = 0; i < size; ++i)
    ((u8 *)dst)[i] = val;
}

void mem_cpy(void *dst, void *__restrict src, i64 size) {
  CHECK(dst != NULL, "Invalid arguments",);
  CHECK(src != NULL, "Invalid arguments",);
  CHECK(size >= 0,   "Invalid size",);

  for (i64 i = 0; i < size; ++i)
    ((u8 *)dst)[i] = ((u8 *)src)[i];
}

b8 mem_eq(void *a, void *b, i64 size) {
  CHECK(a != NULL, "Invalid arguments", 0);
  CHECK(b != NULL, "Invalid arguments", 0);
  CHECK(size > 0,  "Invalid size", 0);

  u8 *x = (u8 *) a;
  u8 *y = (u8 *) b;

  for (i64 i = 0; i < size; ++i)
    if (x[i] != y[i])
      return 0;

  return 1;
}

i64 bx_str_len(c8 *s, c8 *s_end) {
  CHECK(s < s_end, "Buffer overflow", 0);

  for (i64 len = 0; s + len < s_end; ++len)
    if (s[len] == '\0')
      return len;

  FAIL("Buffer overflow", 0);
}

i64 bx_str_len_or(c8 *s, c8 *s_max, i64 or_val) {
  for (i64 len = 0; s + len < s_max; ++len)
    if (s[len] == '\0')
      return len;

  return or_val;
}

c8 *bx_find_char(c8 *s, c8 *s_end, c8 c) {
  CHECK(s != NULL,     "Invalid arguments", NULL);
  CHECK(s_end != NULL, "Invalid arguments", NULL);

  while (s < s_end && *s != c)
    ++s;

  return *s == c ? s : NULL;
}

c8 *bx_find_str(c8 *s, c8 *s_end, c8 *sub, c8 *sub_end) {
  CHECK(s != NULL,       "Invalid arguments", NULL);
  CHECK(s_end != NULL,   "Invalid arguments", NULL);
  CHECK(sub != NULL,     "Invalid arguments", NULL);
  CHECK(sub_end != NULL, "Invalid arguments", NULL);

  while (sub_end - sub <= s_end - s && s < s_end) {
    c8 *q = s;
    c8 *p = sub;
    for (; q < s_end && p < sub_end; ++q, ++p)
      if (*q != *p)
        break;
    if (p == sub_end)
      return s;
    ++s;
  }

  return NULL;
}

c8 *bx_find_str_in_table(c8 *buf, c8 *buf_end, c8 *sub, c8 *sub_end) {
  CHECK(buf     != NULL, "Invalid arguments", NULL);
  CHECK(buf_end != NULL, "Invalid arguments", NULL);
  CHECK(sub     != NULL, "Invalid arguments", NULL);
  CHECK(sub_end != NULL, "Invalid arguments", NULL);

  while (buf < buf_end) {
    i64 len = bx_str_len(buf, buf_end);
    if (sub_end - sub == len && mem_eq(buf, sub, len))
      return buf;
    buf += len + 1;
  }

  return NULL;
}

u64 bx_u64_from_dec_str(c8 *s, c8 *s_end) {
  CHECK(s != NULL && s_end != NULL, "Invalid arguments", 0);
  CHECK(s < s_end,                  "Buffer overflow",   0);
  CHECK(*s >= '0' && *s <= '9',     "Parsing failed",    0);

  u64 x = 0;
  for (; s < s_end && *s >= '0' && *s <= '9'; ++s)
    x = (x * 10) + (*s - '0');

  LAX(s == s_end || *s == ' ' || *s == '\0', "Parsing failed");
  return x;
}

//  ================================================================
//
//  * Semantic graph
//
//  ================================================================

//  IR building procs
//

i64 pool_add(Pool *pool, Entity data) {
  CHECK(pool != NULL && pool->entities != NULL, "Invalid arguments", UNDEFINED);
  CHECK(pool->num_entities < pool->capacity,    "Out of memory",     UNDEFINED);

  i64 id             = pool->num_entities++;
  data.is_enabled    = 1,
  pool->entities[id] = data;

  return id;
}

void pool_remove(Pool *pool, i64 entity, u16 type) {
  CHECK(pool != NULL && pool->entities != NULL,     "Invalid arguments",);
  CHECK(entity >= 0 && entity < pool->num_entities, "Buffer overflow",);
  CHECK(pool->entities[entity].is_enabled,          "Entity already removed",);
  CHECK(pool->entities[entity].type == type,        "Invalid entity type",);

  pool->entities[entity].is_enabled = 1;
}

i64 node_init(Pool *pool, Node data) {
  data.index_in_proc = UNDEFINED;

  return pool_add(pool, (Entity) {
    .type = ENTITY_NODE,
    .node = data,
  });
}

void node_destroy(Pool *pool, i64 node) {
  pool_remove(pool, node, ENTITY_NODE);
}

i64 node_data_reference(Pool *pool, i64 node) {
  return node_init(pool, (Node) {
    .op  = DATA_REFERENCE,
    .ref = node,
  });
}

i64 node_data_array_c8(Pool *pool, i64 size, c8 *data) {
  CHECK(size < MAX_LITERAL_SIZE, "Too big", UNDEFINED);
  Node node_entry = {
    .op            = DATA_I8,
    .lit.num_bytes = size
  };
  mem_cpy(node_entry.lit.as_u8, data, size);
  return node_init(pool, node_entry);
}

i64 node_data_ptr(Pool *pool, u64 address) {
  return node_init(pool, (Node) {
    .op            = DATA_PTR,
    .lit.num_bytes = sizeof address,
    .lit.as_u64    = address,
  });
}

i64 node_data_i32(Pool *pool, i32 value) {
  return node_init(pool, (Node) {
    .op            = DATA_I32,
    .lit.num_bytes = sizeof value,
    .lit.as_i32    = value,
  });
}

i64 node_data_i64(Pool *pool, i64 value) {
  return node_init(pool, (Node) {
    .op            = DATA_I64,
    .lit.num_bytes = sizeof value,
    .lit.as_i64    = value,
  });
}

u16 resolve_calling_convention(Pool *pool, i64 proc) {
  CHECK(pool != NULL,                             "Invalid arguments",);
  CHECK(proc != UNDEFINED,                        "Invalid arguments",);
  CHECK(pool->entities[proc].is_enabled,          "No entity",);
  CHECK(pool->entities[proc].type == ENTITY_PROC, "No proc",);

  if (pool->entities[proc].proc.convention == CONV_UNKNOWN)
    pool->entities[proc].proc.convention = CONV_CDECL;

  return pool->entities[proc].proc.convention;
}

i64 node_ctrl_call(Pool *pool, i64 target_proc, i64 num_args, Var *args) {
  CHECK(num_args <= MAX_NUM_ARGS, "Array too big", UNDEFINED);

  Call call = {
    .convention  = resolve_calling_convention(pool, target_proc),
    .target_proc = target_proc,
    .num_args    = num_args,
  };

  if (num_args > 0)
    mem_cpy(call.args, args, num_args * sizeof *args);

  return node_init(pool, (Node) {
    .op   = CTRL_CALL,
    .call = call,
  });
}

i64 node_ctrl_call_by_name(Pool *pool, i64 name_size, c8 *name, i64 num_args, Var *args) {
  CHECK(num_args <= MAX_NUM_ARGS, "Array too big", UNDEFINED);

  Call call = {
    .convention       = CONV_CDECL,
    .target_proc      = UNDEFINED,
    .target_name_size = name_size,
    .num_args         = num_args,
  };

  if (name_size > 0)
    mem_cpy(call.target_name, name, name_size);
  if (num_args > 0)
    mem_cpy(call.args, args, num_args * sizeof *args);

  return node_init(pool, (Node) {
    .op   = CTRL_CALL,
    .call = call,
  });
}

i64 node_ctrl_ret(Pool *pool, i64 num_values, Var *values) {
  CHECK(num_values <= MAX_NUM_ARGS, "Array too big", UNDEFINED);

  Ret ret = { .num_vals = num_values, };

  if (num_values > 0)
    mem_cpy(ret.vals, values, num_values * sizeof *values);

  return node_init(pool, (Node) {
    .op  = CTRL_RET,
    .ret = ret,
  });
}

i64 proc_init(Pool *pool) {
  return pool_add(pool, (Entity) {
    .type = ENTITY_PROC,
    .proc = (Proc) {
      .ret_index     = UNDEFINED,
      .index_in_unit = UNDEFINED,
    },
  });
}

void proc_destroy(Pool *pool, i64 proc) {
  pool_remove(pool, proc, ENTITY_PROC);
}

void proc_set_convention(Pool *pool, i64 proc, u16 convention) {
  CHECK(pool != NULL && pool->entities != NULL,   "Invalid arguments",);
  CHECK(proc >= 0 && proc < pool->num_entities,   "Buffer overflow",);
  CHECK(pool->entities[proc].is_enabled,          "Entity does not exist",);
  CHECK(pool->entities[proc].type == ENTITY_PROC, "Invalid entity type",);

  pool->entities[proc].proc.convention = convention;
}

void proc_set_name(Pool *pool, i64 proc, i64 name_size, c8 *name) {
  CHECK(pool != NULL && pool->entities != NULL,   "Invalid arguments",);
  CHECK(proc >= 0 && proc < pool->num_entities,   "Buffer overflow",);
  CHECK(pool->entities[proc].is_enabled,          "Entity does not exist",);
  CHECK(pool->entities[proc].type == ENTITY_PROC, "Invalid entity type",);

  CHECK(name_size <= MAX_NAME_SIZE, "Name too big",);
  CHECK(name_size >= 0,             "Invalid arguments",);

  Proc *p    = &pool->entities[proc].proc;
  p->name_size = name_size;

  if (name_size > 0)
    mem_cpy(p->name, name, name_size);
}

void proc_node_add(Pool *pool, i64 proc, i64 node) {
  CHECK(pool != NULL && pool->entities != NULL,   "Invalid arguments",);
  CHECK(proc >= 0 && proc < pool->num_entities,   "Buffer overflow",);
  CHECK(pool->entities[proc].is_enabled,          "Proc does not exist",);
  CHECK(pool->entities[proc].type == ENTITY_PROC, "Invalid entity type",);
  CHECK(pool->entities[node].is_enabled,          "Node does not exist",);
  CHECK(pool->entities[node].type == ENTITY_NODE, "Invalid entity type",);

  Proc *p = &pool->entities[proc].proc;
  Node *n = &pool->entities[node].node;

  CHECK(n->index_in_proc == UNDEFINED, "Internal",);

  i64 index = p->num_nodes;

  if (n->op == CTRL_RET)
  {
    //  Only one return node is allowed.
    //

    CHECK(p->ret_index == UNDEFINED, "Internal",);
    p->ret_index = index;
  }

  CHECK(index < MAX_NUM_NODES, "Out of memory",);

  n->index_in_proc = index;
  p->nodes[index]  = node;
  ++p->num_nodes;
}

void proc_node_remove(Pool *pool, i64 proc, i64 node) {
  CHECK(pool != NULL && pool->entities != NULL,   "Invalid arguments",);
  CHECK(proc >= 0 && proc < pool->num_entities,   "Buffer overflow",);
  CHECK(node >= 0 && node < pool->num_entities,   "Buffer overflow",);
  CHECK(pool->entities[proc].is_enabled,          "Entity does not exist",);
  CHECK(pool->entities[proc].type == ENTITY_PROC, "Invalid entity type",);
  CHECK(pool->entities[node].type == ENTITY_NODE, "Invalid entity type",);

  Proc *p = &pool->entities[proc].proc;
  Node *n = &pool->entities[node].node;

  CHECK(n->index_in_proc != UNDEFINED, "Internal",);
  CHECK(p->nodes[n->index_in_proc] == node, "Internal",);

  if (n->op == CTRL_RET) {
    CHECK(p->ret_index != UNDEFINED, "Internal",);
    p->ret_index = UNDEFINED;
  }

  p->nodes[n->index_in_proc] = UNDEFINED;
  n->index_in_proc           = UNDEFINED;
}

i64 unit_init(Pool *pool, u16 type) {
  return pool_add(pool, (Entity) {
    .type = ENTITY_UNIT,
    .unit = (Unit) {
      .type              = type,
      .entry_point_index = UNDEFINED,
    }
  });
}

void unit_destroy(Pool *pool, i64 unit) {
  pool_remove(pool, unit, ENTITY_UNIT);
}

void unit_proc_add(Pool *pool, i64 unit, i64 proc) {
  CHECK(pool != NULL && pool->entities != NULL,   "Invalid arguments",);
  CHECK(unit >= 0 && unit < pool->num_entities,   "Buffer overflow",);
  CHECK(proc >= 0 && proc < pool->num_entities,   "Buffer overflow",);
  CHECK(pool->entities[unit].is_enabled,          "Unit does not exist",);
  CHECK(pool->entities[unit].type == ENTITY_UNIT, "Invalid entity type",);
  CHECK(pool->entities[proc].is_enabled,          "Proc does not exist",);
  CHECK(pool->entities[proc].type == ENTITY_PROC, "Invalid proc type",);

  Unit *u = &pool->entities[unit].unit;
  Proc *p = &pool->entities[proc].proc;

  CHECK(p->index_in_unit == UNDEFINED, "Internal",);

  i64 index = u->num_procs;

  CHECK(index < MAX_NUM_PROCS, "Out of memory",);

  p->index_in_unit = index;
  u->procs[index]  = proc;
  ++u->num_procs;
}

void unit_proc_remove(Pool *pool, i64 unit, i64 proc) {
  CHECK(pool != NULL && pool->entities != NULL,   "Invalid arguments",);
  CHECK(unit >= 0 && unit < pool->num_entities,   "Buffer overflow",);
  CHECK(proc >= 0 && proc < pool->num_entities,   "Buffer overflow",);
  CHECK(pool->entities[unit].is_enabled,          "Unit does not exist",);
  CHECK(pool->entities[unit].type == ENTITY_UNIT, "Invalid entity type",);
  CHECK(pool->entities[proc].type == ENTITY_PROC, "Invalid entity type",);

  Unit *u = &pool->entities[unit].unit;
  Proc *p = &pool->entities[proc].proc;

  CHECK(p->index_in_unit != UNDEFINED, "Internal",);
  CHECK(u->procs[p->index_in_unit] == proc, "Internal",);

  if (u->entry_point_index == p->index_in_unit)
    u->entry_point_index = UNDEFINED;

  u->procs[p->index_in_unit] = UNDEFINED;
  p->index_in_unit           = UNDEFINED;
}

void unit_link_add(Pool *pool, i64 unit, i64 link_unit) {
  CHECK(pool != NULL && pool->entities != NULL,           "Invalid arguments",);
  CHECK(unit      >= 0 && unit      < pool->num_entities, "Buffer overflow",);
  CHECK(link_unit >= 0 && link_unit < pool->num_entities, "Buffer overflow",);
  CHECK(pool->entities[unit].is_enabled,                  "Unit does not exist",);
  CHECK(pool->entities[unit].type == ENTITY_UNIT,         "Invalid entity type",);
  CHECK(pool->entities[link_unit].is_enabled,             "Link does not exist",);
  CHECK(pool->entities[link_unit].type == ENTITY_UNIT,    "Invalid entity type",);

  Unit *u = &pool->entities[unit].unit;

  for (i64 i = 0; i < u->num_links; ++i)
    if (u->links[i] == link_unit)
      return;

  CHECK(u->num_links < MAX_NUM_LINKS, "Internal",);
  u->links[u->num_links++] = link_unit;
}

void unit_link_remove(Pool *pool, i64 unit, i64 link_unit) {
  CHECK(pool != NULL && pool->entities != NULL,           "Invalid arguments",);
  CHECK(unit      >= 0 && unit      < pool->num_entities, "Buffer overflow",);
  CHECK(link_unit >= 0 && link_unit < pool->num_entities, "Buffer overflow",);
  CHECK(pool->entities[unit].is_enabled,                  "Unit does not exist",);
  CHECK(pool->entities[unit].type == ENTITY_UNIT,         "Invalid entity type",);
  CHECK(pool->entities[link_unit].type == ENTITY_UNIT,    "Invalid entity type",);

  Unit *u = &pool->entities[unit].unit;

  for (i64 i = 0; i < u->num_links; ++i)
    if (u->links[i] == link_unit) {
      u->links[i] = UNDEFINED;
      return;
    }

  FAIL("Link not found",);
}

void unit_set_name(Pool *pool, i64 unit, i64 name_size, c8 *name) {
  CHECK(pool != NULL && pool->entities != NULL,   "Invalid arguments",);
  CHECK(unit >= 0 && unit < pool->num_entities,   "Buffer overflow",);
  CHECK(pool->entities[unit].is_enabled,          "Unit does not exist",);
  CHECK(pool->entities[unit].type == ENTITY_UNIT, "Invalid entity type",);

  CHECK(name_size <= MAX_NAME_SIZE, "Name too big",);
  CHECK(name_size >= 0,             "Invalid arguments",);

  Unit *u      = &pool->entities[unit].unit;
  u->name_size = name_size;

  if (name_size > 0)
    mem_cpy(u->name, name, name_size);
}

void unit_set_entry_point(Pool *pool, i64 unit, i64 entry_point_proc) {
  CHECK(pool != NULL && pool->entities != NULL,   "Invalid arguments",);
  CHECK(unit >= 0 && unit < pool->num_entities,   "Buffer overflow",);
  CHECK(pool->entities[unit].is_enabled,          "Unit does not exist",);
  CHECK(pool->entities[unit].type == ENTITY_UNIT, "Invalid unit type",);

  Unit *u = &pool->entities[unit].unit;

  if (entry_point_proc == UNDEFINED) {
    u->entry_point_index = UNDEFINED;
    return;
  }

  CHECK(entry_point_proc >= 0 && entry_point_proc < pool->num_entities,   "Buffer overflow",);
  CHECK(pool->entities[entry_point_proc].is_enabled,          "Internal",);
  CHECK(pool->entities[entry_point_proc].type == ENTITY_PROC, "Internal",);

  Proc *p = &pool->entities[entry_point_proc].proc;

  CHECK(p->index_in_unit != UNDEFINED,                  "Internal",);
  CHECK(u->procs[p->index_in_unit] == entry_point_proc, "Internal",);

  pool->entities[unit].unit.entry_point_index = p->index_in_unit;
}

//  ================================================================
//
//  * Serialization
//
//  ----------------------------------------------------------------
//
//  Terms
//
//  LE = little endian
//  BE = big endian
//  HO = host ordering
//
//  byte  = 8 bits
//  word  = 2 bytes
//  dword = 4 bytes
//  qword = 8 bytes
//
//  ================================================================

enum {
  BIT_LE         = 0,
  BIT_BE         = 1,
  BIT_ORDER_MASK = 1,

  BYTE_LE         = 0,
  BYTE_BE         = 2,
  BYTE_ORDER_MASK = 2,

  WORD_LE         = 0,
  WORD_BE         = 4,
  WORD_ORDER_MASK = 4,

  DWORD_LE         = 0,
  DWORD_BE         = 8,
  DWORD_ORDER_MASK = 8,

  F64_DWORD_LE         = 0,
  F64_DWORD_BE         = 16,
  F64_DWORD_ORDER_MASK = 16,

  LE = BIT_LE | BYTE_LE | WORD_LE | DWORD_LE | F64_DWORD_LE,
  BE = BIT_BE | BYTE_BE | WORD_BE | DWORD_BE | F64_DWORD_BE,
};

typedef struct {
  unsigned first:1;
} Bits;

u32 host_bit_order() {
  if ((*(Bits *) &(u8) { 1 }).first == 1)
    return BIT_LE;
  return BIT_BE;
}

u32 host_byte_order() {
  if (((u8 *) &(u32) { 1 })[0] == 1)
    return BYTE_LE;
  return BYTE_BE;
}

u32 host_word_order() {
  if (((u16 *) &(u32) { 0x100 })[0] == 0x100)
    return WORD_LE;
  return WORD_BE;
}

u32 host_dword_order() {
  if (((u32 *) &(u64) { 0x10000 })[0] == 0x10000)
    return DWORD_LE;
  return DWORD_BE;
}

void check_f32_format() {
  //  FIXME
  if ((*(u64 *) &(f64) { -1.4575323640233e-306 } & 0xffffffffull)         == 0x40301fcbull)
    return;
  if ((*(u64 *) &(f64) { -1.4575323640233e-306 } & 0xffffffff00000000ull) == 0x40301fcb00000000ull)
    return;

  FAIL("Unknown host floating-point number format",);
}

u32 host_f64_dword_order() {
  if ((*(u64 *) &(f64) { -1.4575323640233e-306 } & 0xffffffffull)         == 0x40301fcbull)
    return host_dword_order() == DWORD_LE ? F64_DWORD_LE : F64_DWORD_BE;
  if ((*(u64 *) &(f64) { -1.4575323640233e-306 } & 0xffffffff00000000ull) == 0x40301fcb00000000ull)
    return host_dword_order() == DWORD_LE ? F64_DWORD_BE : F64_DWORD_LE;

  FAIL("Unknown host floating-point number format", 0);
}

u32 host_data_ordering() {
  return host_bit_order()       |
         host_byte_order()      |
         host_word_order()      |
         host_dword_order()     |
         host_f64_dword_order();
}

u8 read_u8(u32 ordering, u8 *v, u8 *v_end) {
  CHECK(v != NULL, "Invalid arguments", 0);
  CHECK(v < v_end, "Buffer overflow",   0);

  if ((ordering & BIT_ORDER_MASK) == host_bit_order())
    return *v;

  return
     ((*v >> 7) & 1)       |
    (((*v >> 6) & 1) << 1) |
    (((*v >> 5) & 1) << 2) |
    (((*v >> 4) & 1) << 3) |
    (((*v >> 3) & 1) << 4) |
    (((*v >> 2) & 1) << 5) |
    (((*v >> 1) & 1) << 6) |
    (((*v)      & 1) << 7);
}

u16 read_u16(u32 ordering, u8 *v, u8 *v_end) {
  CHECK(v != NULL,      "Invalid arguments", 0);
  CHECK(v + 2 <= v_end, "Buffer overflow",   0);

  u16 x;

  if ((ordering & BIT_ORDER_MASK)  == host_bit_order() &&
      (ordering & BYTE_ORDER_MASK) == host_byte_order())
    mem_cpy(&x, v, 2);
  else if ((ordering & BYTE_ORDER_MASK) == host_byte_order())
    x =  ((u16) read_u8(ordering, v,     v_end))       |
        (((u16) read_u8(ordering, v + 1, v_end)) << 8);
  else
    x =  ((u16) read_u8(ordering, v + 1, v_end))       |
        (((u16) read_u8(ordering, v,     v_end)) << 8);

  return x;
}

u32 read_u32(u32 ordering, u8 *v, u8 *v_end) {
  CHECK(v != NULL,      "Invalid arguments", 0);
  CHECK(v + 4 <= v_end, "Buffer overflow",   0);

  u32 x;

  if ((ordering & BIT_ORDER_MASK)  == host_bit_order()  &&
      (ordering & BYTE_ORDER_MASK) == host_byte_order() &&
      (ordering & WORD_ORDER_MASK) == host_word_order())
    mem_cpy(&x, v, 4);
  else if ((ordering & WORD_ORDER_MASK) == host_word_order())
    x =  ((u32) read_u16(ordering, v,     v_end))        |
        (((u32) read_u16(ordering, v + 2, v_end)) << 16);
  else
    x =  ((u32) read_u16(ordering, v + 2, v_end))        |
        (((u32) read_u16(ordering, v,     v_end)) << 16);

  return x;
}

u64 read_u64(u32 ordering, u8 *v, u8 *v_end) {
  CHECK(v != NULL,      "Invalid arguments", 0);
  CHECK(v + 8 <= v_end, "Buffer overflow", 0);

  u64 x;

  if ((ordering & BIT_ORDER_MASK)   == host_bit_order()  &&
      (ordering & BYTE_ORDER_MASK)  == host_byte_order() &&
      (ordering & WORD_ORDER_MASK)  == host_word_order() &&
      (ordering & DWORD_ORDER_MASK) == host_dword_order())
    mem_cpy(&x, v, 8);
  else if ((ordering & DWORD_ORDER_MASK) == host_dword_order())
    x =  ((u64) read_u32(ordering, v,     v_end))        |
        (((u64) read_u32(ordering, v + 4, v_end)) << 32);
  else
    x =  ((u64) read_u32(ordering, v + 4, v_end))        |
        (((u64) read_u32(ordering, v,     v_end)) << 32);

  return x;
}

void write_u8(u8 ordering, u8 x, u8 *v, u8 *v_end) {
  CHECK(v != NULL, "Invalid arguments",);
  CHECK(v < v_end, "Buffer overflow",);

  if ((ordering & BIT_ORDER_MASK) == host_bit_order())
    *v = x;
  else
    *v =
       ((x >> 7) & 1)       |
      (((x >> 6) & 1) << 1) |
      (((x >> 5) & 1) << 2) |
      (((x >> 4) & 1) << 3) |
      (((x >> 3) & 1) << 4) |
      (((x >> 2) & 1) << 5) |
      (((x >> 1) & 1) << 6) |
      (((x)      & 1) << 7);
}

void write_u16(u32 ordering, u16 x, u8 *v, u8 *v_end) {
  CHECK(v != NULL,      "Invalid arguments",);
  CHECK(v + 2 <= v_end, "Buffer overflow",);

  if ((ordering & BIT_ORDER_MASK)  == host_bit_order() &&
      (ordering & BYTE_ORDER_MASK) == host_byte_order())
    mem_cpy(v, &x, 2);
  else if ((ordering & BYTE_ORDER_MASK) == host_byte_order()) {
    write_u8(ordering, (u8) ( x       & 0xff), v,     v_end);
    write_u8(ordering, (u8) ((x >> 8) & 0xff), v + 1, v_end);
  } else {
    write_u8(ordering, (u8) ( x       & 0xff), v + 1, v_end);
    write_u8(ordering, (u8) ((x >> 8) & 0xff), v,     v_end);
  }
}

void write_u32(u32 ordering, u32 x, u8 *v, u8 *v_end) {
  CHECK(v != NULL,      "Invalid arguments",);
  CHECK(v + 4 <= v_end, "Buffer overflow",);

  if ((ordering & BIT_ORDER_MASK)  == host_bit_order()  &&
      (ordering & BYTE_ORDER_MASK) == host_byte_order() &&
      (ordering & WORD_ORDER_MASK) == host_word_order())
    mem_cpy(v, &x, 4);
  else if ((ordering & WORD_ORDER_MASK) == host_word_order()) {
    write_u16(ordering, (u16) ( x        & 0xffff), v,     v_end);
    write_u16(ordering, (u16) ((x >> 16) & 0xffff), v + 2, v_end);
  } else {
    write_u16(ordering, (u16) ( x        & 0xffff), v + 2, v_end);
    write_u16(ordering, (u16) ((x >> 16) & 0xffff), v,     v_end);
  }
}

void write_u64(u32 ordering, u64 x, u8 *v, u8 *v_end) {
  CHECK(v != NULL,      "Invalid arguments",);
  CHECK(v + 8 <= v_end, "Buffer overflow",);

  if ((ordering & BIT_ORDER_MASK)   == host_bit_order()  &&
      (ordering & BYTE_ORDER_MASK)  == host_byte_order() &&
      (ordering & WORD_ORDER_MASK)  == host_word_order() &&
      (ordering & DWORD_ORDER_MASK) == host_dword_order())
    mem_cpy(v, &x, 8);
  else if ((ordering & DWORD_ORDER_MASK) == host_dword_order()) {
    write_u32(ordering, (u32) ( x        & 0xffffffffull), v,     v_end);
    write_u32(ordering, (u32) ((x >> 32) & 0xffffffffull), v + 4, v_end);
  } else {
    write_u32(ordering, (u32) ( x        & 0xffffffffull), v + 4, v_end);
    write_u32(ordering, (u32) ((x >> 16) & 0xffffffffull), v,     v_end);
  }
}

i16 read_i8(u32 ordering, void *v, void *v_end) {
  return (i8) read_u8(ordering, v, v_end);
}

i16 read_i16(u32 ordering, void *v, void *v_end) {
  return (i16) read_u16(ordering, v, v_end);
}

i32 read_i32(u32 ordering, void *v, void *v_end) {
  return (i32) read_u32(ordering, v, v_end);
}

i64 read_i64(u32 ordering, void *v, void *v_end) {
  return (i64) read_u64(ordering, v, v_end);
}

f32 read_f32(u32 ordering, void *v, void *v_end) {
  check_f32_format();
  return *(f32 *) &(u32) { read_u32(ordering, v, v_end) };
}

f64 read_f64(u32 ordering, void *v, void *v_end) {
  u64 x = read_u64(ordering, v, v_end);

  if ((ordering & F64_DWORD_ORDER_MASK) != host_f64_dword_order())
    x = ((x & 0xffffffffull) << 32) | ((x >> 32) & 0xffffffffull);

  void *p = &x;
  return *(f64 *) p;
}

void write_i8(u32 ordering, i8 x, void *v, void *v_end) {
  write_u8(ordering, (u8) x, v, v_end);
}

void write_i16(u32 ordering, i16 x, void *v, void *v_end) {
  write_u16(ordering, (u16) x, v, v_end);
}

void write_i32(u32 ordering, i32 x, void *v, void *v_end) {
  write_u32(ordering, (u32) x, v, v_end);
}

void write_i64(u32 ordering, i64 x, void *v, void *v_end) {
  write_u64(ordering, (u64) x, v, v_end);
}

void write_f32(u32 ordering, f32 x, void *v, void *v_end) {
  check_f32_format();
  void *p = &x;
  write_u32(ordering, *(u32 *) p, v, v_end);
}

void write_f64(u32 ordering, f64 x, void *v, void *v_end) {
  void *p = &x;
  if ((ordering & F64_DWORD_ORDER_MASK) == host_f64_dword_order())
    write_u64(ordering, *(u64 *) p, v, v_end);
  else {
    write_u32(ordering, *(((u32 *) p) + 1),  (u8 *) v,      v_end);
    write_u32(ordering, *  (u32 *) p,       ((u8 *) v) + 4, v_end);
  }
}

//  Shortcuts

#define HO host_data_ordering()

//  ================================================================
//
//  * Code generation and linking
//
//  ----------------------------------------------------------------
//
//  Docs and helpful materials
//
//  AR  https://man.freebsd.org/cgi/man.cgi?query=ar&sektion=5
//  ELF https://man7.org/linux/man-pages/man5/elf.5.html
//
//  Relocation types
//  https://intezer.com/blog/malware-analysis/executable-and-linkable-format-101-part-3-relocations/
//  https://docs.oracle.com/cd/E19120-01/open.solaris/819-0690/chapter7-2/index.html
//
//  https://web.archive.org/web/20150324024617/http://mylinuxbook.com/readelf-command/
//
//  tinycc impl
//  https://repo.or.cz/tinycc.git/blob/HEAD:/x86_64-link.c
//  https://repo.or.cz/tinycc.git/blob/HEAD:/tccelf.c
//
//  Online assembler
//  https://defuse.ca/online-x86-assembler.htm
//  https://shell-storm.org/online/Online-Assembler-and-Disassembler/
//
//  Linux syscall
//  https://man7.org/linux/man-pages/man2/intro.2.html
//  https://man7.org/linux/man-pages/man2/syscalls.2.html
//  https://man7.org/linux/man-pages/man2/syscall.2.html
//
//  Linker scripts
//  https://home.cs.colorado.edu/~main/cs1300/doc/gnu/ld_3.html
//
//  ----------------------------------------------------------------
//
//  TODO Experiment with mapping several p_vaddr into one p_paddr.
//
//  ================================================================

enum {
  HOST_Unknown = 0,
  HOST_Unix,
  HOST_Linux,
  HOST_Windows,
  HOST_macOS,
  HOST_Cygwin,

  #if defined(__CYGWIN__)
  HOST = HOST_Cygwin,
  #elif defined(_WIN32)
  HOST = HOST_Windows,
  #elif defined(__linux__)
  HOST = HOST_Linux,
  #elif defined(__APPLE__)
  HOST = HOST_macOS,
  #elif defined(__unix__)
  HOST = HOST_Unix,
  #else
  HOST = HOST_Unknown,
  #endif

  //  x86_64 constants
  //

  X86_64_BASE_ADDRESS = 0x400000,
  X86_64_ALIGNMENT    = 8,
  X86_64_PAGE_SIZE    = 4 * 1024,

  //  ELF format constants
  //

  ELF_64          = 2,
  ELF_2_LE        = 1,
  ELF_VERSION     = 1,
  ELF_SYS_V       = 0,
  ELF_LINUX       = 3,
  ELF_ABI_VERSION = 0,
  ELF_RELOCATABLE = 1,
  ELF_EXECUTABLE  = 2,
  ELF_X86_64      = 62,

  ELF_HEADER_SIZE         = 64,
  ELF_PROGRAM_HEADER_SIZE = 56,
  ELF_SECTION_HEADER_SIZE = 64,
  ELF_SYMBOL_ENTRY_SIZE   = 24,
  ELF_REL_ENTRY_SIZE      = 16,
  ELF_RELA_ENTRY_SIZE     = 24,

  SEC_NONE = 0,
  SEC_PROGBITS,
  SEC_SYMTAB,
  SEC_STRTAB,
  SEC_RELA,
  SEC_HASH,
  SEC_DYNAMIC,
  SEC_NOTE,
  SEC_NOBITS,
  SEC_REL,
  SEC_SHLIB,
  SEC_DYNSYM,
  SEC_INIT_ARRAY = 14,
  SEC_FINI_ARRAY,
  SEC_PREINIT_ARRAY,
  SEC_GROUP,
  SEC_SYMTAB_SHNDX,

  SYM_NONE = 0,
  SYM_PROC,
  SYM_DATA,
  SYM_COMMON,
  SYM_TLS,
  SYM_SECTION,
  SYM_SPECIFIC,

  BIND_LOCAL = 0,
  BIND_GLOBAL,
  BIND_WEAK,

  //  Relocation types
  //

  R_X86_64_NONE = 0,
  R_X86_64_64,
  R_X86_64_PC32,
  R_X86_64_GOT32,
  R_X86_64_PLT32,
  R_X86_64_COPY,
  R_X86_64_GLOB_DAT,
  R_X86_64_JUMP_SLOT,
  R_X86_64_RELATIVE,
  R_X86_64_GOTPCREL,
  R_X86_64_32,
  R_X86_64_32S,
  R_X86_64_16,
  R_X86_64_PC16,
  R_X86_64_8,
  R_X86_64_PC8,
  R_X86_64_DTPMOD64,
  R_X86_64_DTPOFF64,
  R_X86_64_TPOFF64,
  R_X86_64_TLSGD,
  R_X86_64_TLSLD,
  R_X86_64_DTPOFF32,
  R_X86_64_GOTTPOFF,
  R_X86_64_TPOFF32,
  R_X86_64_PC64,
  R_X86_64_GOTOFF64,
  R_X86_64_GOTPC32,
  R_X86_64_GOT64,
  R_X86_64_GOTPCREL64,
  R_X86_64_GOTPC64,
  R_X86_64_GOTPLT64,
  R_X86_64_PLTOFF64,
  R_X86_64_SIZE32,
  R_X86_64_SIZE64,
  R_X86_64_GOTPC32_TLSDESC,
  R_X86_64_TLSDESC_CALL,
  R_X86_64_TLSDESC,
  R_X86_64_IRELATIVE,
  R_X86_64_RELATIVE64,
  R_X86_64_GOTPCRELX = 41,
  R_X86_64_REX_GOTPCRELX,

  //  Codegen context

  EMIT_ENTRY_PROC = 1,
};

c8 *SEC_TYPE_NAMES[] = {
  [SEC_NONE]          = "none",
  [SEC_PROGBITS]      = "progbits",
  [SEC_SYMTAB]        = "symtab",
  [SEC_STRTAB]        = "strtab",
  [SEC_RELA]          = "rela",
  [SEC_HASH]          = "hash",
  [SEC_DYNAMIC]       = "dynamic",
  [SEC_NOTE]          = "note",
  [SEC_NOBITS]        = "nobits",
  [SEC_REL]           = "rel",
  [SEC_SHLIB]         = "shlib",
  [SEC_DYNSYM]        = "dynsym",
  [12]                = "",
  [13]                = "",
  [SEC_INIT_ARRAY]    = "init array",
  [SEC_FINI_ARRAY]    = "fini array",
  [SEC_PREINIT_ARRAY] = "preinit array",
  [SEC_GROUP]         = "group",
  [SEC_SYMTAB_SHNDX]  = "symtab shndx",
};

c8 *SYM_TYPE_NAMES[] = {
  [SYM_NONE]     = "none",
  [SYM_PROC]     = "proc",
  [SYM_DATA]     = "data",
  [SYM_COMMON]   = "common",
  [SYM_TLS]      = "tls",
  [SYM_SECTION]  = "section",
  [SYM_SPECIFIC] = "spec",
};

c8 *BIND_TYPE_NAMES[] = {
  [BIND_LOCAL]  = "local",
  [BIND_GLOBAL] = "global",
  [BIND_WEAK]   = "weak",
};

c8 *REL_NAMES[] = {
  [R_X86_64_NONE]            = "none",
  [R_X86_64_64]              = "64",
  [R_X86_64_PC32]            = "pc32",
  [R_X86_64_GOT32]           = "got32",
  [R_X86_64_PLT32]           = "plt32",
  [R_X86_64_COPY]            = "copy",
  [R_X86_64_GLOB_DAT]        = "glob dat",
  [R_X86_64_JUMP_SLOT]       = "jump slot",
  [R_X86_64_RELATIVE]        = "relative",
  [R_X86_64_GOTPCREL]        = "gotpcrel",
  [R_X86_64_32]              = "32",
  [R_X86_64_32S]             = "32s",
  [R_X86_64_16]              = "16",
  [R_X86_64_PC16]            = "pc16",
  [R_X86_64_8]               = "8",
  [R_X86_64_PC8]             = "pc8",
  [R_X86_64_DTPMOD64]        = "dtpmod64",
  [R_X86_64_DTPOFF64]        = "dtpoff64",
  [R_X86_64_TPOFF64]         = "tpoff64",
  [R_X86_64_TLSGD]           = "tlsgd",
  [R_X86_64_TLSLD]           = "tlsld",
  [R_X86_64_DTPOFF32]        = "dtpoff32",
  [R_X86_64_GOTTPOFF]        = "gottpoff",
  [R_X86_64_TPOFF32]         = "tpoff32",
  [R_X86_64_PC64]            = "pc64",
  [R_X86_64_GOTOFF64]        = "gotoff64",
  [R_X86_64_GOTPC32]         = "gotpc32",
  [R_X86_64_GOT64]           = "got64",
  [R_X86_64_GOTPCREL64]      = "gotpcrel64",
  [R_X86_64_GOTPC64]         = "gotpc64",
  [R_X86_64_GOTPLT64]        = "gotplt64",
  [R_X86_64_PLTOFF64]        = "pltoff64",
  [R_X86_64_SIZE32]          = "size32",
  [R_X86_64_SIZE64]          = "size64",
  [R_X86_64_GOTPC32_TLSDESC] = "gotpc32 tlsdesc",
  [R_X86_64_TLSDESC_CALL]    = "tlsdesc call",
  [R_X86_64_TLSDESC]         = "tlsdesc",
  [R_X86_64_IRELATIVE]       = "irelative",
  [R_X86_64_RELATIVE64]      = "relative64",
  [R_X86_64_GOTPCRELX]       = "gotpcrelx",
  [R_X86_64_REX_GOTPCRELX]   = "gotpcrelx",
};

c8 ELF_MAGIC[4]      = "\x7f" "ELF";
c8 AR_MAGIC[8]       = "!<arch>\n";
c8 AR_SYMBOL_TABLE[] = "/               ";
c8 AR_STRING_TABLE[] = "//              ";

c8 SECTION_TEXT[]      = ".text";
c8 SECTION_RELA_TEXT[] = ".rela.text";
c8 SECTION_DATA[]      = ".data";
c8 SECTION_BSS[]       = ".bss";
c8 SECTION_RODATA[]    = ".rodata";
c8 SECTION_SYMTAB[]    = ".symtab";
c8 SECTION_STRTAB[]    = ".strtab";
c8 SECTION_SHSTRTAB[]  = ".shstrtab";

typedef struct {
  i64 offset;
  i64 size;
} Offset_Size;

typedef struct {
  u8 *        begin;
  u8 *        end;
  Offset_Size elf;
} Buffer_Context;

typedef struct {
  i64 offset;
  i64 num;
} Offset_Num;

typedef struct {
  Offset_Size name;
  u32         type;
  b8          alloc;
  b8          write;
  b8          exec;
  i64         alignment;
  i64         entry_size;
  i64         num_entries;
  Offset_Size data;
} Elf_Section_Header;

typedef struct {
  Offset_Size name;
  u8          type;
  u8          bind;
  i64         section;
  Offset_Size value;
} Elf_Symbol_Entry;

typedef struct {
  Elf_Symbol_Entry symbol;
  i64              offset;
  u32              type;
  i64              addent;
} Elf_Relx_Entry;

//  ================================================================
//
//  Codegen
//

void x86_64_emit_node(
  Pool *           pool,
  Codegen_Context *codegen,
  i64              node,
  u32              context
) {
  CHECK(pool != NULL && pool->entities != NULL,               "Invalid arguments", 0);
  CHECK(node != UNDEFINED && pool->entities[node].is_enabled, "No node", 0);
  CHECK(pool->entities[node].type == ENTITY_NODE,             "Invalid entity", 0);

  Node *n = &pool->entities[node].node;

  u8 *begin = codegen->buffer_code + codegen->offset_code;
  u8 *end   = codegen->buffer_code + codegen->max_code_size;

  #define CHECK_NODE_(node)                                           \
    CHECK((node) != UNDEFINED,                        "Internal", 0); \
    CHECK(pool->entities[(node)].is_enabled,          "Internal", 0); \
    CHECK(pool->entities[(node)].type == ENTITY_NODE, "Internal", 0)

  switch (n->op) {
    case DATA_PTR:
    case DATA_I8:
    case DATA_I32:
    case DATA_I64:
    case DATA_REFERENCE:
      //  Do nothing
      break;

    case CTRL_CALL: {
      CHECK(n->call.convention == CONV_CDECL,               "Not implemented", 0);
      CHECK(n->call.target_proc == UNDEFINED,               "Not implemented", 0);
      CHECK(n->call.target_name_size > 0,                   "No proc name", 0);
      CHECK(codegen->num_rels + 2 <= codegen->max_num_rels, "Out of memory", 0);

      switch (n->call.num_args) {
        case 1: {
          i64 n_arg = n->call.args[0];
          CHECK_NODE_(n_arg);

          Node *arg = &pool->entities[n_arg].node;

          if (arg->op == DATA_REFERENCE) {
            //  Write data
            //

            Node *data = &pool->entities[arg->ref].node;
            CHECK(data->op == DATA_I8, "Not implemented", 0);

            CHECK(codegen->offset_rodata + data->lit.num_bytes <= codegen->max_rodata_size, "Out of memory", 0);

            i64 arg_offset = codegen->offset_rodata;
            mem_cpy(codegen->buffer_rodata + arg_offset, data->lit.as_u8, data->lit.num_bytes);

            //  Write code and relocations
            //

            write_u8(LE, 0x48, begin,     end); // movabs
            write_u8(LE, 0xbf, begin + 1, end); // rdi

            codegen->rels[codegen->num_rels++] = (Rel_Entry) {
              .type   = REL_ADD_RODATA_ADDRESS,
              .offset = codegen->offset_code + 2,
              .size   = 8,
              .value  = arg_offset,
              .proc   = UNDEFINED, // FIXME use zero value
            };

            write_u8(LE, 0x48, begin + 10, end); // movabs
            write_u8(LE, 0xb8, begin + 11, end); // rax

            codegen->rels[codegen->num_rels++] = (Rel_Entry) {
              .type      = REL_ADD_PROC_ADDRESS,
              .offset    = codegen->offset_code + 12,
              .size      = 8,
              .name_size = n->call.target_name_size,
              .name      = n->call.target_name,
              .proc      = UNDEFINED, // FIXME use zero value
            };

            write_u8(LE, 0xff, begin + 20, end); // call
            write_u8(LE, 0xd0, begin + 21, end); // rax

            codegen->offset_code   += 22;
            codegen->offset_rodata += data->lit.num_bytes;
          } else if (arg->op == DATA_I32) {
            CHECK(arg->lit.num_bytes == 4, "Not implemented",);

            write_u8 (LE, 0xbf,               begin,     end); // mov edi
            write_i32(LE, arg->lit.as_i32[0], begin + 1, end);
            write_u8 (LE, 0x48,               begin + 5, end); // movabs
            write_u8 (LE, 0xb8,               begin + 6, end); // rax

            codegen->rels[codegen->num_rels++] = (Rel_Entry) {
              .type      = REL_ADD_PROC_ADDRESS,
              .offset    = codegen->offset_code + 7,
              .size      = 8,
              .name_size = n->call.target_name_size,
              .name      = n->call.target_name,
              .proc      = UNDEFINED, // FIXME use zero value
            };

            write_u8(LE, 0xff, begin + 11, end); // call
            write_u8(LE, 0xd0, begin + 12, end); // rax

            codegen->offset_code += 13;
          } else {
            FAIL("Not implemented",);
          }
        } break;

        case 3: {
          i64 n_arg_0 = n->call.args[0];
          i64 n_arg_1 = n->call.args[1];
          i64 n_arg_2 = n->call.args[2];

          CHECK_NODE_(n_arg_0);
          CHECK_NODE_(n_arg_1);
          CHECK_NODE_(n_arg_2);

          Node *arg_0 = &pool->entities[n_arg_0].node;
          Node *arg_1 = &pool->entities[n_arg_1].node;
          Node *arg_2 = &pool->entities[n_arg_2].node;

          CHECK(arg_0->op == DATA_PTR,     "Not implemented", 0);
          CHECK(arg_1->op == DATA_PTR,     "Not implemented", 0);
          CHECK(arg_2->op == DATA_PTR,     "Not implemented", 0);
          CHECK(arg_0->lit.as_u64[0] == 0, "Not implemented", 0);
          CHECK(arg_1->lit.as_u64[0] == 0, "Not implemented", 0);
          CHECK(arg_2->lit.as_u64[0] == 0, "Not implemented", 0);

          write_u8(LE, 0x31, begin,     end); // xor edx
          write_u8(LE, 0xd2, begin + 1, end); // edx
          write_u8(LE, 0x31, begin + 2, end); // xor esi
          write_u8(LE, 0xf6, begin + 3, end); // esi
          write_u8(LE, 0x31, begin + 4, end); // xor edi
          write_u8(LE, 0xff, begin + 5, end); // edi
          write_u8(LE, 0x48, begin + 6, end); // movabs
          write_u8(LE, 0xb8, begin + 7, end); // rax

          codegen->rels[codegen->num_rels++] = (Rel_Entry) {
            .type      = REL_ADD_PROC_ADDRESS,
            .offset    = codegen->offset_code + 8,
            .size      = 8,
            .name_size = n->call.target_name_size,
            .name      = n->call.target_name,
            .proc      = UNDEFINED, // FIXME use zero value
          };

          write_u8(LE, 0xff, begin + 16, end); // call
          write_u8(LE, 0xd0, begin + 17, end); // rax

          codegen->offset_code += 18;
        } break;

        case 7: {
          i64 n_arg_0 = n->call.args[0];
          i64 n_arg_1 = n->call.args[1];
          i64 n_arg_2 = n->call.args[2];
          i64 n_arg_3 = n->call.args[3];
          i64 n_arg_4 = n->call.args[4];
          i64 n_arg_5 = n->call.args[5];
          i64 n_arg_6 = n->call.args[6];

          CHECK_NODE_(n_arg_0);
          CHECK_NODE_(n_arg_1);
          CHECK_NODE_(n_arg_2);
          CHECK_NODE_(n_arg_3);
          CHECK_NODE_(n_arg_4);
          CHECK_NODE_(n_arg_5);
          CHECK_NODE_(n_arg_6);

          Node *arg_0 = &pool->entities[n_arg_0].node;
          Node *arg_1 = &pool->entities[n_arg_1].node;
          Node *arg_2 = &pool->entities[n_arg_2].node;
          Node *arg_3 = &pool->entities[n_arg_3].node;
          Node *arg_4 = &pool->entities[n_arg_4].node;
          Node *arg_5 = &pool->entities[n_arg_5].node;
          Node *arg_6 = &pool->entities[n_arg_6].node;

          CHECK(arg_0->op == DATA_REFERENCE, "Not implemented", 0);
          CHECK(arg_1->op == DATA_I32,       "Not implemented", 0);
          CHECK(arg_2->op == DATA_REFERENCE, "Not implemented", 0);
          CHECK(arg_3->op == DATA_PTR,       "Not implemented", 0);
          CHECK(arg_4->op == DATA_PTR,       "Not implemented", 0);
          CHECK(arg_5->op == DATA_PTR,       "Not implemented", 0);
          CHECK(arg_6->op == DATA_PTR,       "Not implemented", 0);

          CHECK(arg_0->ref != UNDEFINED,               "Internal", 0);
          CHECK(pool->entities[arg_0->ref].is_enabled, "Internal", 0);
          CHECK(arg_2->ref != UNDEFINED,               "Internal", 0);
          CHECK(pool->entities[arg_2->ref].is_enabled, "Internal", 0);

          CHECK(pool->entities[arg_0->ref].type == ENTITY_PROC, "Not implemented", 0);
          CHECK(pool->entities[arg_2->ref].type == ENTITY_NODE, "Not implemented", 0);

          //  Write data
          //

          Node *dat_2 = &pool->entities[arg_2->ref].node;
          CHECK(dat_2->op == DATA_PTR, "Not implemented", 0);

          CHECK(codegen->offset_rodata + dat_2->lit.num_bytes <= codegen->max_rodata_size, "Out of memory", 0);

          i64 arg_2_offset = codegen->offset_rodata;
          mem_cpy(codegen->buffer_rodata + arg_2_offset, dat_2->lit.as_u8, dat_2->lit.num_bytes);

          //  Write code and relocations
          //

          write_u8 (LE, 0x48, begin,      end); // movabs
          write_u8 (LE, 0xbf, begin +  1, end); // rdi

          codegen->rels[codegen->num_rels++] = (Rel_Entry) {
            .type      = REL_ADD_PROC_ADDRESS,
            .offset    = codegen->offset_code + 2,
            .size      = 8,
            .proc      = arg_0->ref,
          };

          write_u8 (LE, 0xbe,                 begin + 10, end); // mov esi
          write_u32(LE, arg_1->lit.as_u32[0], begin + 11, end);
          write_u8 (LE, 0x48,                 begin + 15, end); // movabs
          write_u8 (LE, 0xba,                 begin + 16, end); // rdx

          codegen->rels[codegen->num_rels++] = (Rel_Entry) {
            .type   = REL_ADD_RODATA_ADDRESS,
            .offset = codegen->offset_code + 17,
            .size   = 8,
            .value  = arg_2_offset,
            .proc   = UNDEFINED, // FIXME use zero value
          };

          write_u8 (LE, 0x48,                 begin + 25, end); // movabs
          write_u8 (LE, 0xb9,                 begin + 26, end); // rcx
          write_u64(LE, arg_3->lit.as_u64[0], begin + 27, end);
          write_u8 (LE, 0x48,                 begin + 35, end); // movabs
          write_u8 (LE, 0xb8,                 begin + 36, end); // r8
          write_u64(LE, arg_4->lit.as_u64[0], begin + 37, end);
          write_u8 (LE, 0x48,                 begin + 45, end); // movabs
          write_u8 (LE, 0xb9,                 begin + 46, end); // r9
          write_u64(LE, arg_5->lit.as_u64[0], begin + 47, end);
          write_u8 (LE, 0x48,                 begin + 55, end); // movabs
          write_u8 (LE, 0xb8,                 begin + 56, end); // rax
          write_u64(LE, arg_6->lit.as_u64[0], begin + 57, end);
          write_u8 (LE, 0x50,                 begin + 65, end); // push rax

          write_u8 (LE, 0x48, begin + 66, end); // movabs
          write_u8 (LE, 0xb8, begin + 67, end); // rax

          codegen->rels[codegen->num_rels++] = (Rel_Entry) {
            .type      = REL_ADD_PROC_ADDRESS,
            .offset    = codegen->offset_code + 68,
            .size      = 8,
            .name_size = n->call.target_name_size,
            .name      = n->call.target_name,
            .proc      = UNDEFINED, // FIXME use zero value
          };

          write_u8(LE, 0xff, begin + 76, end); // call
          write_u8(LE, 0xd0, begin + 77, end); // rax

          write_u8(LE, 0x48, begin + 78, end); // add rsp
          write_u8(LE, 0x83, begin + 79, end); //
          write_u8(LE, 0xc4, begin + 80, end); //
          write_u8(LE, 8,    begin + 81, end); // 8

          codegen->offset_code   += 82;
          codegen->offset_rodata += dat_2->lit.num_bytes;
        } break;

        default:
          FAIL("Not implemented",);
      }
    } break;

    case CTRL_RET: {
      if ((context & EMIT_ENTRY_PROC) != 0) {
        write_u8 (LE, 0xb8, begin,      end); // mov eax
        write_u32(LE, 60,   begin +  1, end); // 60

        if (n->ret.num_vals == 0) {
          write_u8 (LE, 0xbf, begin +  5, end); // mov edi
          write_u32(LE, 0,    begin +  6, end); // 0

        } else {
          if (n->ret.num_vals > 1)
            LOG(WARNING, "Some return values are ignored for node %lld", node);

          i64 n_val = n->ret.vals[0];
          CHECK(n_val != UNDEFINED,                        "Internal", 0);
          CHECK(pool->entities[n_val].is_enabled,          "Internal", 0);
          CHECK(pool->entities[n_val].type == ENTITY_NODE, "Internal", 0);

          Node *val = &pool->entities[n_val].node;
          CHECK(val->op == DATA_I64,     "Not implemented", 0);
          CHECK(val->lit.num_bytes == 8, "Not implemented", 0);

          write_u8 (LE, 0xbf,             begin +  5, end); // mov edi
          write_u32(LE, *val->lit.as_u32, begin +  6, end); // <- literal
        }

        write_u8 (LE, 0x0f, begin + 10, end); // syscall
        write_u8 (LE, 0x05, begin + 11, end);

        codegen->offset_code += 12;
      } else {
        CHECK(n->ret.num_vals == 1, "Not implemented", 0);

        i64 n_val = n->ret.vals[0];
        CHECK(n_val != UNDEFINED,                        "Internal", 0);
        CHECK(pool->entities[n_val].is_enabled,          "Internal", 0);
        CHECK(pool->entities[n_val].type == ENTITY_NODE, "Internal", 0);

        Node *val = &pool->entities[n_val].node;
        CHECK(val->op == DATA_I32,     "Not implemented", 0);
        CHECK(val->lit.num_bytes == 4, "Not implemented", 0);

        write_u8 (LE, 0xb8,               begin,     end); // mov eax
        write_u32(LE, val->lit.as_u32[0], begin + 1, end);
        write_u8 (LE, 0xc3,               begin + 5, end); // ret

        codegen->offset_code += 6;
      }
    } break;

    default:
      FAIL("Unknown operation",);
  }

  #undef CHECK_NODE_
}

void emit_proc(
  Pool *           pool,
  Codegen_Context *codegen,
  i64              proc,
  u16              arch,
  u32              context
) {
  CHECK(pool != NULL && pool->entities != NULL,               "Invalid arguments", 0);
  CHECK(proc != UNDEFINED && pool->entities[proc].is_enabled, "No proc", 0);
  CHECK(pool->entities[proc].type == ENTITY_PROC,             "Invalid entity", 0);
  CHECK(arch == ARCH_X86_64,                                  "Target not supported", 0);

  Proc *p = &pool->entities[proc].proc;

  CHECK(p->codegen.emit_done == 0, "Emit already done", 0);

  p->codegen.offset = codegen->offset_code;

  //  TODO Sort nodes in the sequential execution order.
  //
  //    NOTE
  //    Now we assume that nodes are already sorted.

  for (i64 i = 0; i < p->num_nodes; ++i)
    x86_64_emit_node(pool, codegen, p->nodes[i], context);

  p->codegen.emit_done = 1;
}

void emit_unit(Pool *pool, Codegen_Context *codegen, i64 unit, u16 arch) {
  CHECK(pool != NULL && pool->entities != NULL,               "Invalid arguments", 0);
  CHECK(unit != UNDEFINED && pool->entities[unit].is_enabled, "No unit", 0);
  CHECK(pool->entities[unit].type == ENTITY_UNIT,             "Invalid entity", 0);

  for (i64 i = 0; i < pool->entities[unit].unit.num_procs; ++i) {
    u32 context = 0;

    if (i == pool->entities[unit].unit.entry_point_index) {
      codegen->entry_point = codegen->offset_code;
      context |= EMIT_ENTRY_PROC;
    }

    emit_proc(pool, codegen, pool->entities[unit].unit.procs[i], arch, context);
  }
}

//  ================================================================
//
//  Linking
//

i64 ar_find_symbol_offset_by_name(
  u8 *ar_symbol_table,
  u8 *ar_end,
  c8 *name,
  c8 *name_end
) {
  CHECK(ar_symbol_table != NULL, "Invalid arguments", -1);
  CHECK(name != NULL,            "Invalid arguments", -1);
  CHECK(name_end > name,         "Invalid arguments", -1);

  i64 num = (i64) read_u32((LE & ~BYTE_ORDER_MASK) | BYTE_BE, ar_symbol_table, ar_end);
  i64 len = name_end - name;

  c8 *s     = (c8 *) (ar_symbol_table + 4 * (num + 1));
  i64 index = 0;

  for (; index < num; ++index) {
    CHECK(s + len <= (c8 *) ar_end, "Buffer overflow", -1);

    if (s[len] == '\0' && mem_eq(s, name, len))
      return (i64) read_u32((LE & ~BYTE_ORDER_MASK) | BYTE_BE, ar_symbol_table + 4 * (index + 1), ar_end);

    while (*s != '\0' && s < (c8 *) ar_end)
      ++s;
    CHECK(s < (c8 *) ar_end, "Buffer overflow", -1);
    CHECK(*s == '\0',        "Buffer overflow", -1);
    ++s;
  }

  FAIL("Symbol not found", 0);
}

Buffer_Context elf_buffer_context(
  Pool *          pool,
  Linker_Context *linker,
  i64             num_obj_files,
  i64             elf_index
) {
  return (Buffer_Context) {
    .begin = linker->dependencies_buffer,
    .end   = linker->dependencies_buffer + linker->obj_file_offsets[num_obj_files],
    .elf = {
      .offset = linker->obj_file_offsets[elf_index],
      .size   = linker->obj_file_offsets[elf_index + 1] - linker->obj_file_offsets[elf_index],
    },
  };
}

Offset_Num elf_section_headers(
  Buffer_Context b
) {
  u8 *begin = b.begin + b.elf.offset;
  u8 *end   = begin + b.elf.size;

  CHECK(end <= b.end, "Buffer overflow", (Offset_Num) {0});

  return (Offset_Num) {
    .offset = b.elf.offset + read_i64(LE, begin + 40, end),
    .num    = (i64) read_u16(LE, begin + 60, end),
  };
}

i64 elf_section_header_offset(
  Buffer_Context b,
  i64            index
) {
  return elf_section_headers(b).offset + ELF_SECTION_HEADER_SIZE * index;
}

Offset_Size elf_section_names_data(
  Buffer_Context b
) {
  u8 *elf_begin = b.begin + b.elf.offset;
  u8 *elf_end   = elf_begin + b.elf.size;

  CHECK(elf_end <= b.end, "Buffer overflow", (Offset_Size) {0});

  i64 string_table_index = (i64) read_u16(LE, elf_begin + 62, elf_end);

  u8 *begin = b.begin + elf_section_header_offset(b, string_table_index);

  return (Offset_Size) {
    .offset = b.elf.offset + read_i64(LE, begin + 24, elf_end),
    .size   = read_i64(LE, begin + 32, elf_end),
  };
}

Offset_Size elf_name_in_string_table(
  Buffer_Context b,
  Offset_Size    string_table,
  i64            name_offset
) {
  if (name_offset == 0)
    return (Offset_Size) {
      .offset = 0,
      .size   = 0,
    };

  c8 *begin = (c8 *) b.begin + string_table.offset + name_offset;
  c8 *end   = (c8 *) b.begin + string_table.offset + string_table.size;

  return (Offset_Size) {
    .offset = string_table.offset + name_offset,
    .size   = bx_str_len(begin, end),
  };
}

i64 elf_find_section_index_by_name(
  Buffer_Context b,
  c8 *           name,
  i64            name_size
) {
  CHECK(name != NULL, "Invalid arguments", 0);

  if (name_size == 0)
    return 0;

  Offset_Num  headers = elf_section_headers(b);
  Offset_Size names   = elf_section_names_data(b);

  for (i64 i = 0; i < headers.num; ++i) {
    u8 *begin      = b.begin + headers.offset + i * ELF_SECTION_HEADER_SIZE;
    i64 name_index = (i64) read_u32(LE, begin, b.end);
    Offset_Size s  = elf_name_in_string_table(b, names, name_index);

    if (s.size == name_size &&
        mem_eq(b.begin + s.offset, name, name_size))
      return i;
  }

  return 0;
}

Elf_Section_Header elf_section(
  Buffer_Context b,
  i64            index
) {
  Offset_Size names = elf_section_names_data(b);
  u8 *        begin = b.begin + elf_section_header_offset(b, index);
  u8 *        end   = b.begin + b.elf.offset + b.elf.size;
  CHECK(end <= b.end, "Buffer overflow", (Elf_Section_Header) {0});

  i64 name_index  = (i64) read_u32(LE, begin, end);
  i64 size        = read_i64(LE, begin + 32, end);
  i64 entry_size  = read_i64(LE, begin + 56, end);
  i64 num_entries = entry_size > 0 ? (size / entry_size) : 0;
  u32 type        = read_u32(LE, begin + 4,  end);
  u64 flags       = read_u64(LE, begin + 8,  end);

  if (type > SEC_SYMTAB_SHNDX || type == 12 || type == 13) {
    LOG(WARNING, "Unknown section type: %d", type);
    type = SEC_NONE;
  }

  return (Elf_Section_Header) {
    .name        = elf_name_in_string_table(b, names, name_index),
    .type        = type,
    .alloc       = (flags & 2) == 2,
    .write       = (flags & 1) == 1,
    .exec        = (flags & 4) == 4,
    .alignment   = read_i64(LE, begin + 48, end),
    .entry_size  = entry_size,
    .num_entries = num_entries,
    .data = {
      .offset = b.elf.offset + read_i64(LE, begin + 24, end),
      .size   = size,
    },
  };
}

Elf_Section_Header elf_find_section_by_name(
  Buffer_Context b,
  c8 *           name,
  i64            name_size
) {
  i64 index = elf_find_section_index_by_name(b, name, name_size);
  return index == 0 ? (Elf_Section_Header) {0} : elf_section(b, index);
}

c8 *elf_name_from_offset(
  Buffer_Context b,
  Offset_Size    name
) {
  if (name.size == 0)
    return "";

  c8 *begin = (c8 *) (b.begin + name.offset);
  i64 len   = bx_str_len(begin, (c8 *) b.end);

  CHECK((i64) name.size == len, "Buffer overflow", "");
  return begin;
}

i64 elf_find_related_section_index(
  Buffer_Context b,
  i64            section_index
) {
  Offset_Size    src_name = elf_section(b, section_index).name;
  Elf_Section_Header dst      = elf_section(b, section_index - 1);

  if (src_name.size > dst.name.size &&
      mem_eq(
        elf_name_from_offset(b, src_name) + (src_name.size - dst.name.size),
        elf_name_from_offset(b, dst.name),
        dst.name.size))
    return section_index - 1;

  i64 num_sections = elf_section_headers(b).num;

  for (i64 i = 0; i < num_sections; ++i) {
    if (i == section_index || i + 1 == section_index)
      continue;
    dst = elf_section(b, i);
    if (src_name.size > dst.name.size &&
        mem_eq(
          elf_name_from_offset(b, src_name) + (src_name.size - dst.name.size),
          elf_name_from_offset(b, dst.name),
          dst.name.size)) {
      LOG(WARNING, "Unexpected section order");
      return i;
    }
  }

  FAIL("Not found", 0);
}

Offset_Size elf_find_related_data(
  Buffer_Context b,
  i64            section_index
) {
  return elf_section(b, elf_find_related_section_index(b, section_index)).data;
}

Elf_Symbol_Entry elf_symbol(
  Buffer_Context b,
  Offset_Size    symbol_table,
  Offset_Size    string_table,
  i64            symbol_index
) {
  u8 *begin = b.begin + symbol_table.offset + symbol_index * ELF_SYMBOL_ENTRY_SIZE;
  u8 *end   = b.begin + symbol_table.offset + symbol_table.size;

  CHECK(end <= b.end, "Buffer overflow", (Elf_Symbol_Entry) {0});
  CHECK(end <= b.begin + b.elf.offset + b.elf.size, "Buffer overflow", (Elf_Symbol_Entry) {0});

  i64 sym_name  = (i64) read_u32(LE, begin,      end);
  u8  sym_info  = read_u8 (LE, begin +  4, end);
  i64 sym_shndx = (i64) read_u16(LE, begin +  6, end);
  i64 sym_value = read_i64(LE, begin +  8, end);
  i64 sym_size  = read_i64(LE, begin + 16, end);

  u8 type = (sym_info & 0xf) ==  0 ? SYM_NONE     :
            (sym_info & 0xf) ==  1 ? SYM_DATA     :
            (sym_info & 0xf) ==  2 ? SYM_PROC     :
            (sym_info & 0xf) ==  3 ? SYM_SECTION  :
            (sym_info & 0xf) ==  5 ? SYM_COMMON   :
            (sym_info & 0xf) ==  6 ? SYM_TLS      :
                                     SYM_SPECIFIC;

  u8 bind = (sym_info >> 4) == 1 ? BIND_GLOBAL :
            (sym_info >> 4) == 2 ? BIND_WEAK   :
                                   BIND_LOCAL;

  return (Elf_Symbol_Entry) {
    .name    = elf_name_in_string_table(b, string_table, sym_name),
    .type    = type,
    .bind    = bind,
    .section = sym_shndx,
    .value   = {
      .offset = sym_value,
      .size   = sym_size,
    },
  };
}

Elf_Relx_Entry elf_relx(
  Buffer_Context b,
  Offset_Size    symbol_table,
  Offset_Size    string_table,
  Offset_Size    relocations,
  i64            relx_index,
  b8             is_rela
) {
  u8 *begin = b.begin + relocations.offset + relx_index * (is_rela ? ELF_RELA_ENTRY_SIZE : ELF_REL_ENTRY_SIZE);
  u8 *end   = begin + ELF_RELA_ENTRY_SIZE;

  CHECK(end <= b.end, "Buffer overflow", (Elf_Relx_Entry) {0});
  CHECK(end <= b.begin + b.elf.offset + b.elf.size, "Buffer overflow", (Elf_Relx_Entry) {0});
  CHECK(end <= b.begin + relocations.offset + relocations.size, "Buffer overflow", (Elf_Relx_Entry) {0});

  i64 relx_offset = read_i64(LE, begin,      end);
  u32 relx_type   = read_u32(LE, begin +  8, end);
  i64 relx_sym    = (i64) read_u32(LE, begin + 12, end);
  i64 relx_addent = is_rela ? read_i64(LE, begin + 16, end) : 0;

  return (Elf_Relx_Entry) {
    .symbol = elf_symbol(b, symbol_table, string_table, relx_sym),
    .offset = relx_offset,
    .type   = relx_type,
    .addent = relx_addent,
  };
}

Elf_Symbol_Entry elf_find_symbol_by_name(
  Buffer_Context b,
  i64            symbol_table_index,
  Offset_Size    string_table,
  c8 *           name,
  i64            name_size
) {
  Elf_Section_Header symbol_table = elf_section(b, symbol_table_index);

  for (i64 i = 0; i < symbol_table.num_entries; ++i) {
    Elf_Symbol_Entry sym = elf_symbol(b, symbol_table.data, string_table, i);

    CHECK(b.begin + sym.name.offset + name_size <= b.end, "Buffer overflow", (Elf_Symbol_Entry) {0});
    CHECK(sym.name.offset + name_size <= b.elf.size, "Buffer overflow", (Elf_Symbol_Entry) {0});

    if (name_size == sym.name.size && mem_eq(name, b.begin + sym.name.offset, name_size))
      return sym;
  }

  FAIL("Not found", (Elf_Symbol_Entry) {0});
}

void elf_checks(Buffer_Context b) {
  u8 *begin = b.begin + b.elf.offset;
  u8 *end   = begin + b.elf.size;

  u8 osabi = read_u8(LE, begin + 7, end);

  CHECK( read_u8 (LE, begin,      end) == ELF_MAGIC[0],            "Invalid ELF file",);
  CHECK( read_u8 (LE, begin +  1, end) == ELF_MAGIC[1],            "Invalid ELF file",);
  CHECK( read_u8 (LE, begin +  2, end) == ELF_MAGIC[2],            "Invalid ELF file",);
  CHECK( read_u8 (LE, begin +  3, end) == ELF_MAGIC[3],            "Invalid ELF file",);

  CHECK( read_u8 (LE, begin +  4, end) == ELF_64,                  "Unsupported ELF file",);
  CHECK( read_u8 (LE, begin +  5, end) == ELF_2_LE,                "Unsupported ELF file",);
  CHECK( read_u8 (LE, begin +  6, end) == ELF_VERSION,             "Unsupported ELF file",);
  CHECK(   osabi == ELF_SYS_V || osabi == ELF_LINUX,               "Unsupported ELF file",);
  CHECK( read_u8 (LE, begin +  8, end) == ELF_ABI_VERSION,         "Unsupported ELF file",);
  CHECK( read_u16(LE, begin + 16, end) == ELF_RELOCATABLE,         "Unsupported ELF file",);
  CHECK( read_u16(LE, begin + 18, end) == ELF_X86_64,              "Unsupported ELF file",);
  CHECK( read_u32(LE, begin + 20, end) == ELF_VERSION,             "Unsupported ELF file",);

  LAX(   read_u64(LE, begin + 24, end) == 0,                       "Invalid entry point");
  LAX(   read_u64(LE, begin + 32, end) == 0,                       "Invalid program header offset");
  LAX(   read_u32(LE, begin + 48, end) == 0,                       "Invalid flags");
  LAX(   read_u16(LE, begin + 52, end) == ELF_HEADER_SIZE,         "Invalid ELF header size");
  LAX(   read_u16(LE, begin + 54, end) == 0,                       "Invalid program header size");
  LAX(   read_u16(LE, begin + 56, end) == 0,                       "Invalid num program headers");
  LAX(   read_u16(LE, begin + 58, end) == ELF_SECTION_HEADER_SIZE, "Invalid section header size");
}

void elf_dump(u32 log_level, Buffer_Context b, b8 term_color) {
  Offset_Num  headers = elf_section_headers(b);
  Offset_Size strtab  = elf_find_section_by_name(b, SECTION_STRTAB, sizeof SECTION_STRTAB - 1).data;
  Offset_Size symtab  = elf_find_section_by_name(b, SECTION_SYMTAB, sizeof SECTION_SYMTAB - 1).data;

  for (i64 sec_index = 1; sec_index < headers.num; ++sec_index) {
    Elf_Section_Header section = elf_section(b, sec_index);

    c8 *name = elf_name_from_offset(b, section.name);

    LOG(
      log_level,
      "\"%s%s%s\"%*s%-14s%s%s%s%s%lld%s",
      !term_color                   ? "" :
      section.type == SEC_SYMTAB ||
      section.type == SEC_RELA   ||
      section.type == SEC_REL       ? "\x1b[32m" :
      section.alloc                 ? "\x1b[34m" :
      section.type == SEC_STRTAB    ? "\x1b[33m" :
                                      "\x1b[31m",
      name,
      !term_color ? "" : "\x1b[37m",
      (i32) (section.name.size < 30 ? 30 - section.name.size : 1),
      "",
      SEC_TYPE_NAMES[section.type],
      section.alloc ? "R" : "_",
      section.write ? "W" : "_",
      section.exec  ? "X" : "_",
      section.data.size > 0 ? " - "    : "",
      section.data.size,
      section.data.size > 0 ? " bytes" : "\b "
    );

    switch (section.type) {
      case SEC_SYMTAB:
        LOG(log_level, " - -");

        for (i64 sym_index = 1; sym_index < section.num_entries; ++sym_index) {
          Elf_Symbol_Entry sym = elf_symbol(b, section.data, strtab, (u16) sym_index);

          c8 *name = elf_name_from_offset(b, sym.name);

          i32 len = (sym.name.size == 0) ? 4 : (i32) sym.name.size;

          LOG(
            log_level,
            "    %08llx %-04llx %s%s%s%s%s %.*s  %s%-7s %s%s",
            section.data.offset + sym.value.offset,
            sym.value.size,
            *name != '\0' ? "\"" : "",
            !term_color ? "" :
            sym.bind == BIND_GLOBAL ? "\x1b[32m" :
            sym.bind == BIND_WEAK   ? "\x1b[35m" :
                                      "\x1b[31m",
            *name != '\0' ? name : "<NONE>",
            !term_color ? "" : "\x1b[37m",
            *name != '\0' ? "\"" : "",
            31 < len ? 1   : 32 - len,
            31 < len ? " " : "........................................",
            !term_color ? "" :
            sym.type == SYM_PROC     ? "\x1b[32m" :
            sym.type == SYM_DATA     ? "\x1b[32m" :
            sym.type == SYM_COMMON   ? "\x1b[33m" :
            sym.type == SYM_TLS      ? "\x1b[35m" :
            sym.type == SYM_SECTION  ? "\x1b[31m" :
            sym.type == SYM_SPECIFIC ? "\x1b[31m" :
                                       "",
            SYM_TYPE_NAMES[sym.type],
            !term_color ? (sym.section == 0 ? "undefined" : "") :
            sym.section == 0 ? (
              sym.bind == BIND_GLOBAL || sym.bind == BIND_WEAK ?
                "\x1b[33mundefined" : "\x1b[31mundefined") : "",
            !term_color ? "" : "\x1b[37m"
          );
        }

        LOG(log_level, " - -");
        break;

      case SEC_REL:
      case SEC_RELA: {
        LOG(log_level, " - -");

        for (i64 relx_index = 0; relx_index < section.num_entries; ++relx_index) {
          Elf_Relx_Entry relx = elf_relx(b, symtab, strtab, section.data, relx_index, section.type == SEC_RELA);

          LOG(
            log_level,
            "    %-16s %08llx %-+5lld <=  %s%08llx%s%s%s \"%s\"",
            REL_NAMES[relx.type],
            relx.offset,
            relx.addent,
            !term_color ? "" :
            relx.symbol.bind == BIND_WEAK ? "\x1b[33m" : "\x1b[32m",
            relx.symbol.value.offset + elf_section(b, relx.symbol.section).data.offset,
            !term_color ? "" : "\x1b[37m",
            !term_color ? "" :
            relx.symbol.type == SYM_DATA     ? " \x1b[34mdata" :
            relx.symbol.type == SYM_COMMON   ? " \x1b[32mdata" :
            relx.symbol.type == SYM_TLS      ? " \x1b[34mdata" :
            relx.symbol.type == SYM_PROC     ? " \x1b[34mproc" :
            relx.symbol.type == SYM_SECTION  ? " \x1b[36msect" :
            relx.symbol.type == SYM_SPECIFIC ? " \x1b[34mspec" :
                                               " \x1b[33mnone",
            !term_color ? "" : "\x1b[37m",
            elf_name_from_offset(b, relx.symbol.name)
          );
        }

        LOG(log_level, " - -");
      } break;

      default:;
    }
  }

  LOG(log_level, "");
}

i64 unit_write_in_memory(
  Pool *           pool,
  Codegen_Context *codegen,
  Linker_Context * linker,
  i64              unit,
  u16              format,
  u16              arch
) {
  CHECK(pool != NULL && pool->entities != NULL,                   "Invalid arguments",);
  CHECK(unit != UNDEFINED && pool->entities[unit].is_enabled,     "No unit",);
  CHECK(pool->entities[unit].type == ENTITY_UNIT,                 "Invalid entity", 0);
  CHECK(pool->entities[unit].unit.entry_point_index != UNDEFINED, "No entry point",);
  CHECK(format == FORMAT_ELF && arch == ARCH_X86_64,              "Target not supported",);
  CHECK(linker->obj_file_buffer     != NULL, "No object file buffer",);
  CHECK(linker->dependencies_buffer != NULL, "No dependencies buffer",);
  CHECK(linker->obj_file_offsets    != NULL, "No object file offsets buffer",);

  emit_unit(pool, codegen, unit, arch);

  u16 num_program_headers = 4;
  i64 program_offset      = bx_align(ELF_HEADER_SIZE + ELF_PROGRAM_HEADER_SIZE * num_program_headers, X86_64_ALIGNMENT);

  i64 base_address   = X86_64_BASE_ADDRESS;
  i64 rotext_address = base_address + program_offset;
  i64 entry          = rotext_address + codegen->entry_point;

  LOG(VERBOSE, "Entry point: 0x%llx (%lld)", entry, entry);

  i64 rotext_size = codegen->offset_code;
  i64 rwzval_size = 0;
  i64 rwdata_size = 0;
  i64 rodata_size = codegen->offset_rodata;

  i64 num_sections_total = 0;
  i64 num_symbols        = 0;
  i64 not_found_size     = 0;

  //  ==========================================================
  //
  //  Calculate section offsets

  for (i64 elf_index = 0; elf_index < linker->num_obj_files; ++elf_index) {
    Buffer_Context buf = elf_buffer_context(pool, linker, linker->num_obj_files, elf_index);

    elf_checks(buf);
    // elf_dump(VERBOSE, buf, 1);

    Offset_Num headers = elf_section_headers(buf);

    for (i64 sec_index = 1; sec_index < headers.num; ++sec_index, ++num_sections_total) {
      CHECK(num_sections_total < linker->max_num_sections, "Too many sections",);

      Elf_Section_Header section = elf_section(buf, sec_index);

      if (!section.alloc || section.data.size == 0)
        continue;

      if (section.exec) {
        linker->section_offsets[num_sections_total]   = rotext_size;
        linker->section_addresses[num_sections_total] = rotext_size;
        rotext_size += bx_align(section.data.size, X86_64_ALIGNMENT);
      } else if (section.write && section.type == SEC_NOBITS) {
        linker->section_addresses[num_sections_total] = rwzval_size;
        rwzval_size += bx_align(section.data.size, X86_64_ALIGNMENT);
      } else if (section.write) {
        linker->section_offsets[num_sections_total]   = rwdata_size;
        linker->section_addresses[num_sections_total] = rwdata_size;
        rwdata_size += bx_align(section.data.size, X86_64_ALIGNMENT);
      } else if (section.data.size > 0) {
        linker->section_offsets[num_sections_total]   = rodata_size;
        linker->section_addresses[num_sections_total] = rodata_size;
        rodata_size += bx_align(section.data.size, X86_64_ALIGNMENT);
      } else {
        LAX(0, "Unsupported section type");
        continue;
      }
    }
  }

  rotext_size = bx_align(rotext_size, X86_64_PAGE_SIZE);
  rwzval_size = bx_align(rwzval_size, X86_64_PAGE_SIZE);
  rwdata_size = bx_align(rwdata_size, X86_64_PAGE_SIZE);
  rodata_size = bx_align(rodata_size, X86_64_PAGE_SIZE);

  i64 rwzval_address = rotext_address + rotext_size;
  i64 rwdata_address = rwzval_address + rwzval_size;
  i64 rodata_address = rwdata_address + rwdata_size;

  i64 rotext_offset = program_offset;
  i64 rwdata_offset = rotext_offset + rotext_size;
  i64 rodata_offset = rwdata_offset + rwdata_size;

  for (i64 elf_index = 0, sec_index_global = 0; elf_index < linker->num_obj_files; ++elf_index) {
    Buffer_Context buf = elf_buffer_context(pool, linker, linker->num_obj_files, elf_index);
    Offset_Num headers = elf_section_headers(buf);

    for (i64 sec_index = 1; sec_index < headers.num; ++sec_index, ++sec_index_global) {
      CHECK(sec_index_global < num_sections_total, "Buffer overflow",);

      Elf_Section_Header section = elf_section(buf, sec_index);

      if (!section.alloc || section.data.size == 0)
        continue;

      if (section.exec) {
        linker->section_offsets[sec_index_global]   += rotext_offset  + codegen->offset_code;
        linker->section_addresses[sec_index_global] += rotext_address + codegen->offset_code;
      } else if (section.write && section.type == SEC_NOBITS) {
        linker->section_addresses[sec_index_global] += rwzval_address;
      } else if (section.write) {
        linker->section_offsets[sec_index_global]   += rwdata_offset;
        linker->section_addresses[sec_index_global] += rwdata_address;
      } else if (section.data.size > 0) {
        linker->section_offsets[sec_index_global]   += rodata_offset  + codegen->offset_rodata;
        linker->section_addresses[sec_index_global] += rodata_address + codegen->offset_rodata;
      }
    }
  }

  //  ==========================================================
  //
  //  Relocate defined symbols

  for (i64 elf_index = 0, sec_index_global = 0; elf_index < linker->num_obj_files; ++elf_index) {
    Buffer_Context buf = elf_buffer_context(pool, linker, linker->num_obj_files, elf_index);

    Offset_Num  headers = elf_section_headers(buf);
    Offset_Size strtab  = elf_find_section_by_name(buf, SECTION_STRTAB, sizeof SECTION_STRTAB - 1).data;

    for (i64 sec_index = 1; sec_index < headers.num; ++sec_index) {
      Elf_Section_Header tab = elf_section(buf, sec_index);
      if (tab.type != SEC_SYMTAB)
        continue;

      for (i64 sym_index = 1; sym_index < tab.num_entries; ++sym_index) {
        Elf_Symbol_Entry sym      = elf_symbol(buf, tab.data, strtab, sym_index);
        c8 *             sym_name = elf_name_from_offset(buf, sym.name);

        if (sym.section == 0) // undefined symbol
          continue;
        if (sym.section == 65522) // common
          continue;

        i64 sym_section = 0;
        i64 sym_address = sym.value.offset;

        if (sym.section != 65521 && elf_section(buf, sym.section).alloc) {
          sym_section = sec_index_global + sym.section - 1;
          CHECK(sym_section < num_sections_total, "Buffer overflow",);
          CHECK(linker->section_addresses[sym_section] != 0, "Sanity",);
          sym_address = linker->section_addresses[sym_section] + sym.value.offset;
        }

        CHECK(num_symbols < linker->max_num_symbols, "Too many symbols",);

        linker->symbols[num_symbols++] = (Symbol_Entry) {
          .name_size = sym.name.size,
          .name      = sym_name,
          .address   = sym_address,
          .size      = sym.value.size,
        };

        u8 *begin = buf.begin + tab.data.offset + sym_index * ELF_SYMBOL_ENTRY_SIZE;
        u8 *end   = begin + tab.data.size;

        if (end > buf.end)
          end = buf.end;
      }
    }

    sec_index_global += elf_section_headers(buf).num - 1;
  }

  //  ==========================================================
  //
  //  TODO Add runtime library symbols
  //
  //  _DYNAMIC
  //  _GLOBAL_OFFSET_TABLE_
  //
  //  _Unwind_Resume
  //  _Unwind_Backtrace
  //  _Unwind_ForcedUnwind
  //  _Unwind_GetIP
  //  _Unwind_GetCFA
  //
  //  _init
  //  _end
  //  _fini
  //  _dl_rtld_map
  //  __ehdr_start
  //  __pthread_initialize_minimal
  //  __init_array_start
  //  __init_array_end
  //  __fini_array_start
  //  __fini_array_end
  //  __rela_iplt_start
  //  __rela_iplt_end
  //  __preinit_array_start
  //  __preinit_array_end
  //  __start___libc_atexit
  //  __stop___libc_atexit
  //  __stop___libc_IO_vtables
  //  __start___libc_IO_vtables
  //  __start___libc_subfreeres
  //  __stop___libc_subfreeres
  //  __start___libc_freeres_ptrs
  //  __stop___libc_freeres_ptrs
  //  __gcc_personality_v0
  //
  //  __addtf3
  //  __subtf3
  //  __multf3
  //  __divtf3
  //  __eqtf2
  //  __lttf2
  //  __letf2
  //  __gttf2
  //  __getf2
  //  __unordtf2

  CHECK(num_symbols < linker->max_num_symbols, "Too many symbols",);

  linker->symbols[num_symbols++] = (Symbol_Entry) {
    .name_size = 12,
    .name      = "__ehdr_start",
    .address   = base_address,
    .size      = ELF_HEADER_SIZE,
  };

  //  ==============================================================
  //
  //  Apply relocations

  for (i64 elf_index = 0, sec_index_global = 0; elf_index < linker->num_obj_files; ++elf_index) {
    Buffer_Context buf          = elf_buffer_context(pool, linker, linker->num_obj_files, elf_index);
    i64            num_sections = elf_section_headers(buf).num;

    Offset_Size strtab = elf_find_section_by_name(buf, SECTION_STRTAB, sizeof SECTION_STRTAB - 1).data;
    Offset_Size symtab = elf_find_section_by_name(buf, SECTION_SYMTAB, sizeof SECTION_SYMTAB - 1).data;

    for (i64 sec_index = 1; sec_index < num_sections; ++sec_index) {
      Elf_Section_Header src_sec = elf_section(buf, sec_index);
      if (src_sec.type != SEC_REL && src_sec.type != SEC_RELA)
        continue;

      i64 dst_index        = elf_find_related_section_index(buf, sec_index);
      i64 dst_index_global = sec_index_global + dst_index - 1;
      CHECK(dst_index_global >= 0 && dst_index_global < linker->max_num_sections, "Buffer overflow",);

      for (i64 entry_index = 0; entry_index < src_sec.num_entries; ++entry_index) {
        Elf_Relx_Entry relx = elf_relx(buf, symtab, strtab, src_sec.data, entry_index, src_sec.type == SEC_RELA);

        c8 *sym_name = elf_name_from_offset(buf, relx.symbol.name);

        Symbol_Entry symbol = {0};

        if (relx.symbol.section == 0) {
          for (i64 i = 0; i < num_symbols; ++i)
            if (linker->symbols[i].name_size == relx.symbol.name.size &&
                mem_eq(
                  linker->symbols[i].name,
                  sym_name,
                  relx.symbol.name.size
                )) {
              symbol = linker->symbols[i];
              break;
            }
          if (symbol.address == 0 &&
              bx_find_str_in_table(
                linker->not_found_buffer,
                linker->not_found_buffer + not_found_size,
                sym_name,
                sym_name + relx.symbol.name.size
              ) == NULL) {
            // FIXME
            // LOG(WARNING, "Undefined symbol: %s", sym_name);
            CHECK(not_found_size + relx.symbol.name.size + 1 <= linker->max_not_found_size, "Out of memory",);
            mem_cpy(linker->not_found_buffer + not_found_size, sym_name, relx.symbol.name.size);
            not_found_size += relx.symbol.name.size + 1;
          }
        } else {
          i64 src_index_global = sec_index_global + relx.symbol.section - 1;

          symbol = (Symbol_Entry) {
            .address = relx.symbol.value.offset + linker->section_addresses[src_index_global],
            .size    = relx.symbol.value.size,
          };
        }

        u8 *dst = buf.begin + elf_section(buf, dst_index).data.offset + relx.offset;

        //  TODO Implement GOT and PLT.

        // Represents the addend used to compute the value of the relocatable field.
        i64 A = relx.addent;

        // Represents the base address at which a shared object has been loaded into memory during execution. Generally, a shared object is built with a 0 base virtual address, but the execution address will be different.
        i64 B = linker->section_addresses[dst_index_global];

        // Represents the place (section offset or address) of the storage unit being relocated (computed using r_offset).
        i64 P = linker->section_addresses[dst_index_global] + relx.offset;

        // Represents the value of the symbol whose index resides in the relocation entry.
        i64 S = symbol.address;

        // The size of the symbol whose index resides in the relocation entry.
        i64 Z = symbol.size;

        // Represents the address of the global offset table.
        i64 GOT = S;

        // Represents the offset into the global offset table at which the relocation entry's symbol will reside during execution.
        i64 G = 0;

        // Represents the place (section offset or address) of the Procedure Linkage Table entry for a symbol.
        i64 L = S;

        // if (P >= 0x4018ad && P < 0x4018b2) {
        //   LOG(TRACE, "");
        // }
        // LOG(VERBOSE, "--");

        switch (relx.type) {
          #define ADD_(BITS, OP)                              \
            do {                                              \
              i64 x_ = read_i##BITS(LE, dst, buf.end) + (OP); \
              write_i##BITS(LE, (i##BITS) x_, dst, buf.end);  \
            } while (0)

          #define TODO_ FAIL("Not implemented", 0)

          case R_X86_64_NONE:            /* Do nothing */           break;
          case R_X86_64_64:              ADD_(64, S + A);           break; // 64, S + A
          case R_X86_64_PC32:            ADD_(32, S + A - P);       break; // 32, S + A - P
          case R_X86_64_GOT32:           TODO_;                     break; // 32, G + A
          case R_X86_64_PLT32:           ADD_(32, L + A - P);       break; // 32, L + A - P
          case R_X86_64_COPY:            /* Do nothing */           break;
          case R_X86_64_GLOB_DAT:        TODO_;                     break; // 64, S
          case R_X86_64_JUMP_SLOT:       TODO_;                     break; // 64, S
          case R_X86_64_RELATIVE:        TODO_;                     break; // 64, B + A
          case R_X86_64_GOTPCREL:        ADD_(32, G + GOT + A - P); break; // 32, G + GOT + A - P
          case R_X86_64_32:              TODO_;                     break; // 32, S + A
          case R_X86_64_32S:             TODO_;                     break; // 32, S + A
          case R_X86_64_16:              TODO_;                     break; // 16, S + A
          case R_X86_64_PC16:            TODO_;                     break; // 16, S + A - P
          case R_X86_64_8:               TODO_;                     break; //  8, S + A
          case R_X86_64_PC8:             TODO_;                     break; //  8, S + A - P
          case R_X86_64_DTPMOD64:        TODO_;                     break;
          case R_X86_64_DTPOFF64:        TODO_;                     break;
          case R_X86_64_TPOFF64:         TODO_;                     break;
          case R_X86_64_TLSGD:           TODO_;                     break;
          case R_X86_64_TLSLD:           TODO_;                     break;
          case R_X86_64_DTPOFF32:        TODO_;                     break;
          case R_X86_64_GOTTPOFF:        ADD_(32, S - GOT);         break; // 32, S - GOT
          case R_X86_64_TPOFF32:         ADD_(32, S + A - B);       break; // 32, S + A - B
          case R_X86_64_PC64:            TODO_;                     break; // 64, S + A - P
          case R_X86_64_GOTOFF64:        TODO_;                     break;
          case R_X86_64_GOTPC32:         TODO_;                     break; // 32, GOT + A - P
          case R_X86_64_GOT64:           TODO_;                     break;
          case R_X86_64_GOTPCREL64:      TODO_;                     break;
          case R_X86_64_GOTPC64:         TODO_;                     break; // 64, GOT + A - P
          case R_X86_64_GOTPLT64:        TODO_;                     break;
          case R_X86_64_PLTOFF64:        TODO_;                     break;
          case R_X86_64_SIZE32:          TODO_;                     break; // 32, Z + A
          case R_X86_64_SIZE64:          TODO_;                     break; // 64, Z + A
          case R_X86_64_GOTPC32_TLSDESC: TODO_;                     break;
          case R_X86_64_TLSDESC_CALL:    TODO_;                     break;
          case R_X86_64_TLSDESC:         TODO_;                     break;
          case R_X86_64_IRELATIVE:       TODO_;                     break;
          case R_X86_64_RELATIVE64:      TODO_;                     break;
          case R_X86_64_GOTPCRELX:       TODO_;                     break;
          case R_X86_64_REX_GOTPCRELX:   ADD_(32, GOT - P + G - 4); break; // 32, GOT - P + G - 4

          default: FAIL("Unknown relocation type", 0);

          #undef ADD_
          #undef TODO_
        }
      }
    }

    sec_index_global += num_sections - 1;
  }

  //  ==============================================================
  //
  //  Apply our relocations

  for (i64 rel_index = 0; rel_index < codegen->num_rels; ++rel_index) {
    Rel_Entry rel = codegen->rels[rel_index];

    u8 *begin = codegen->buffer_code + rel.offset;
    u8 *end   = codegen->buffer_code + codegen->offset_code;

    switch (rel.type) {
      case REL_ADD_INSTRUCTION_ADDRESS: {
        CHECK(rel.size == 8, "Not implemented", 0);
        i64 value = rel.value + rotext_address + rel.offset;
        write_i64(LE, value, begin, end);
      } break;

      case REL_ADD_RODATA_ADDRESS: {
        CHECK(rel.size == 8, "Not implemented", 0);
        i64 value = rel.value + rodata_address;
        write_i64(LE, value, begin, end);
      } break;

      case REL_ADD_PROC_ADDRESS: {
        CHECK(rel.size == 8, "Not implemented", 0);

        b8 found = 0;

        if (rel.proc == UNDEFINED) {
          CHECK(rel.name_size > 0 && rel.name != NULL, "No proc name", 0);

          for (i64 i = 0; i < num_symbols; ++i)
            if (linker->symbols[i].address != 0                             &&
                linker->symbols[i].name_size == rel.name_size               &&
                mem_eq(linker->symbols[i].name, rel.name, rel.name_size)) {
              i64 value = rel.value + linker->symbols[i].address;
              write_i64(LE, value, begin, end);
              found = 1;

              LOG(VERBOSE, "Found %.*s: 0x%llx", rel.name_size, rel.name, value);
              break;
            }
        } else {
          CHECK(pool->entities[rel.proc].is_enabled,          "No entity", 0);
          CHECK(pool->entities[rel.proc].type == ENTITY_PROC, "No proc", 0);
          Proc *p = &pool->entities[rel.proc].proc;
          CHECK(p->codegen.emit_done, "No proc address", 0);

          i64 value = rel.value + rotext_address + p->codegen.offset;
          write_i64(LE, value, begin, end);
          found = 1;

          LOG(VERBOSE, "Found anonymous proc: 0x%llx", value);
        }

        if (!found) {
          LOG(ERROR, "Undefined symbol: %.*s", rel.name_size, rel.name);
          FAIL("Link failed", 0);
        }
      } break;
    }
  }

  //  ==============================================================
  //
  //  Writing the ELF executable
  //

  i64 output_size = bx_align(program_offset + rotext_size + rwzval_size + rwdata_size + rodata_size, X86_64_ALIGNMENT);

  CHECK(output_size <= linker->max_output_size, "Out of memory",);

  LOG(VERBOSE, "Total %lld sections", num_sections_total);
  LOG(VERBOSE, "Total %lld symbols",  num_symbols);

  LOG(VERBOSE, "Total size");
  LOG(VERBOSE, ".rotext - %7lld bytes", rotext_size);
  LOG(VERBOSE, ".rwzval - %7lld bytes", rwzval_size);
  LOG(VERBOSE, ".rwdata - %7lld bytes", rwdata_size);
  LOG(VERBOSE, ".rodata - %7lld bytes", rodata_size);

  LOG(VERBOSE, "Writing ELF x86_64 executable");

  u8 *o     = linker->output_buffer;
  u8 *o_end = o + linker->max_output_size;

  //  ELF header
  //

  mem_cpy(o, ELF_MAGIC, 4);

  write_u8 (LE, ELF_64,                  o +   4, o_end);
  write_u8 (LE, ELF_2_LE,                o +   5, o_end);
  write_u8 (LE, ELF_VERSION,             o +   6, o_end);
  write_u8 (LE, ELF_SYS_V,               o +   7, o_end);
  write_u8 (LE, ELF_ABI_VERSION,         o +   8, o_end);
  // 7 bytes - padding
  write_u16(LE, ELF_EXECUTABLE,          o +  16, o_end);
  write_u16(LE, ELF_X86_64,              o +  18, o_end);
  write_u32(LE, ELF_VERSION,             o +  20, o_end);
  write_i64(LE, entry,                   o +  24, o_end);
  write_u64(LE, ELF_HEADER_SIZE,         o +  32, o_end); // program header offset
  // 8 bytes - section header offset     o +  40
  // 4 bytes - flags                     o +  48
  write_u16(LE, ELF_HEADER_SIZE,         o +  52, o_end);
  write_u16(LE, ELF_PROGRAM_HEADER_SIZE, o +  54, o_end);
  write_u16(LE, num_program_headers,     o +  56, o_end);
  // 2 bytes - section header size       o +  58
  // 2 bytes - num section headers       o +  60
  // 2 bytes - string table section      o +  62
  //           header index

  //  Program headers
  //

  CHECK(rotext_offset % X86_64_PAGE_SIZE == rotext_address % X86_64_PAGE_SIZE, "Invalid alignment",);
  CHECK(rwdata_offset % X86_64_PAGE_SIZE == rwdata_address % X86_64_PAGE_SIZE, "Invalid alignment",);
  CHECK(rodata_offset % X86_64_PAGE_SIZE == rodata_address % X86_64_PAGE_SIZE, "Invalid alignment",);

  //  .rotext
  write_u32(LE, 1,                       o +  64, o_end); // type   (PT_LOAD)
  write_u32(LE, 5,                       o +  68, o_end); // flags  (PF_X | PF_R)
  write_i64(LE, rotext_offset,           o +  72, o_end);
  write_i64(LE, rotext_address,          o +  80, o_end); // virtual address
  write_i64(LE, rotext_address,          o +  88, o_end); // phisical address
  write_i64(LE, rotext_size,             o +  96, o_end); // size in file
  write_i64(LE, rotext_size,             o + 104, o_end); // size in memory
  write_i64(LE, X86_64_ALIGNMENT,        o + 112, o_end);

  //  .rwzval
  write_u32(LE, 1,                       o + 120, o_end); // type   (PT_LOAD)
  write_u32(LE, 6,                       o + 124, o_end); // flags  (PF_R | PF_W)
  write_i64(LE, rwdata_offset,           o + 128, o_end);
  write_i64(LE, rwzval_address,          o + 136, o_end); // virtual address
  write_i64(LE, rwzval_address,          o + 144, o_end); // phisical address
  write_i64(LE, 0,                       o + 152, o_end); // size in file
  write_i64(LE, rwzval_size,             o + 160, o_end); // size in memory
  write_i64(LE, X86_64_ALIGNMENT,        o + 168, o_end);

  //  .rwdata
  write_u32(LE, 1,                       o + 176, o_end); // type   (PT_LOAD)
  write_u32(LE, 6,                       o + 180, o_end); // flags  (PF_R | PF_W)
  write_i64(LE, rwdata_offset,           o + 184, o_end);
  write_i64(LE, rwdata_address,          o + 192, o_end); // virtual address
  write_i64(LE, rwdata_address,          o + 200, o_end); // phisical address
  write_i64(LE, rwdata_size,             o + 208, o_end); // size in file
  write_i64(LE, rwdata_size,             o + 216, o_end); // size in memory
  write_i64(LE, X86_64_ALIGNMENT,        o + 224, o_end);

  //  .rodata
  write_u32(LE, 1,                       o + 232, o_end); // type   (PT_LOAD)
  write_u32(LE, 4,                       o + 236, o_end); // flags  (PF_R)
  write_i64(LE, rodata_offset,           o + 240, o_end);
  write_i64(LE, rodata_address,          o + 248, o_end); // virtual address
  write_i64(LE, rodata_address,          o + 256, o_end); // phisical address
  write_i64(LE, rodata_size,             o + 264, o_end); // size in file
  write_i64(LE, rodata_size,             o + 272, o_end); // size in memory
  write_i64(LE, X86_64_ALIGNMENT,        o + 280, o_end);

  CHECK(rotext_offset >= 288, "Sanity",);

  //  Code
  //

  mem_cpy(o + rotext_offset, codegen->buffer_code,   codegen->offset_code);
  mem_cpy(o + rodata_offset, codegen->buffer_rodata, codegen->offset_rodata);

  //  ==============================================================
  //
  //  Write sections into the output buffer

  for (i64 elf_index = 0, sec_index_global = 0; elf_index < linker->num_obj_files; ++elf_index) {
    Buffer_Context buf     = elf_buffer_context(pool, linker, linker->num_obj_files, elf_index);
    Offset_Num     headers = elf_section_headers(buf);

    for (i64 sec_index = 1; sec_index < headers.num; ++sec_index, ++sec_index_global) {
      Elf_Section_Header section = elf_section(buf, sec_index);
      i64                offset  = linker->section_offsets[sec_index_global];
      if (offset == 0            ||
          !section.alloc         ||
          section.data.size == 0)
        continue;
      u8 *p = o + offset;
      CHECK(p                     >= o + program_offset + codegen->offset_code, "Buffer overflow",);
      CHECK(p + section.data.size <= o + output_size,                           "Buffer overflow",);
      mem_cpy(p, buf.begin + section.data.offset, section.data.size);
    }
  }

  //  ==============================================================

  return output_size;
}

void unit_write(
  Pool *           pool,
  Codegen_Context *codegen,
  Linker_Context * linker,
  i64              unit,
  u16              format,
  u16              arch,
  i64              io_out,
  void *           io_user_data
) {
  //  ==============================================================
  //
  //  Reading dependencies

  i64 obj_files_size = 0;

  Unit *u = &pool->entities[unit].unit;

  for (i64 link_index = 0; link_index < u->num_links; ++link_index) {
    i64 id = u->links[link_index];
    if (id == UNDEFINED)
      continue;
    Unit *l = &pool->entities[id].unit;
    CHECK(pool->entities[id].is_enabled,  "Internal",);
    CHECK(l->type == UNIT_LIBRARY_STATIC, "Link type not supported",);
    CHECK(l->name_size > 0,               "No link name",);
    CHECK(l->name_size <= MAX_NAME_SIZE,  "Link name too big",);

    i64 f = io_open_read(l->name_size, l->name, io_user_data);
    io_seek(f, 0, IO_SEEK_END, io_user_data);

    i64 in_size = io_tell(f, io_user_data);
    CHECK(in_size <= linker->max_obj_file_size, "AR file too big",);

    io_seek(f, 0, IO_SEEK_BEGIN, io_user_data);
    i64 n = io_read(f, in_size, linker->obj_file_buffer, io_user_data);
    CHECK(n == in_size, "Read failed",);

    io_close(f, io_user_data);

    //  ========================================================
    //
    //  Read AR library

    u8 *ar_begin = linker->obj_file_buffer;
    u8 *ar_end   = linker->obj_file_buffer + in_size;

    CHECK(mem_eq(ar_begin, AR_MAGIC, 8), "Invalid AR file",);

    u8 *f_begin = ar_begin + 8;

    while (f_begin + 60 < ar_end) {
      u8 *f_id   = f_begin;
      u8 *f_size = f_begin + 48;
      u8 *f_end  = f_begin + 58;
      u8 *f_data = f_begin + 60;

      i64 size = (i64) bx_u64_from_dec_str((c8 *) f_size, (c8 *) f_size + 10);

      size = bx_align(size, 2);

      CHECK(mem_eq(f_end, "\x60\x0a", 2), "Invalid AR file",);
      CHECK(f_begin + size <= ar_end,        "Buffer overflow",);

      if (!mem_eq(f_id, AR_SYMBOL_TABLE, 16) &&
          !mem_eq(f_id, AR_STRING_TABLE, 16)) {
        //  Read ELF object file

        i64 delta_size = bx_align(size, X86_64_ALIGNMENT);

        CHECK(obj_files_size + delta_size < linker->max_dependencies_size, "Out of memory",);
        CHECK(linker->num_obj_files + 1 < linker->max_num_obj_files,     "Out of memory",);

        mem_cpy(linker->dependencies_buffer + obj_files_size, f_data, size);

        linker->obj_file_offsets[linker->num_obj_files]   = obj_files_size;
        obj_files_size                                   += delta_size;
        linker->obj_file_offsets[++linker->num_obj_files] = obj_files_size;
      }

      f_begin = f_data + size;
    }
  }

  //  ==============================================================

  i64 output_size = unit_write_in_memory(pool, codegen, linker, unit, format, arch);

  //  ==============================================================
  //
  //  Write the output buffer into the file

  io_write(io_out, output_size, linker->output_buffer, io_user_data);

  //  ==============================================================
  //
  //  Cleanup

  codegen->num_rels     = 0;
  codegen->entry_point  = 0;
  linker->num_obj_files = 0;

  mem_set(codegen->rels,               0, codegen->max_num_rels * sizeof *codegen->rels);
  mem_set(codegen->buffer_code,        0, codegen->max_code_size);
  mem_set(codegen->buffer_rodata,      0, codegen->max_rodata_size);
  mem_set(linker->obj_file_buffer,     0, linker->max_obj_file_size);
  mem_set(linker->dependencies_buffer, 0, linker->max_dependencies_size);
  mem_set(linker->obj_file_offsets,    0, linker->max_num_obj_files * sizeof *linker->obj_file_offsets);
  mem_set(linker->section_offsets,     0, linker->max_num_sections  * sizeof *linker->section_offsets);
  mem_set(linker->section_addresses,   0, linker->max_num_sections  * sizeof *linker->section_addresses);
  mem_set(linker->symbols,             0, linker->max_num_symbols   * sizeof *linker->symbols);
  mem_set(linker->not_found_buffer,    0, linker->max_not_found_size);
  mem_set(linker->output_buffer,       0, linker->max_output_size);
}

i64 io_open_read(i64 name_size, c8 *name, void *user_data) {
  i64 f;
  dispatch_io(IO_OPEN_READ, &f, &name_size, name, user_data);
  return f;
}

i64 io_open_write(i64 name_size, c8 *name, void *user_data) {
  i64 f;
  dispatch_io(IO_OPEN_WRITE, &f, &name_size, name, user_data);
  return f;
}

void io_close(i64 f, void *user_data) {
  dispatch_io(IO_CLOSE, &f, NULL, NULL, user_data);
}

b8 io_seek(i64 f, i64 offset, u16 origin, void *user_data) {
  dispatch_io(IO_SEEK, &f, &offset, &origin, user_data);
  return 1;
}

i64 io_tell(i64 f, void *user_data) {
  i64 offset;
  dispatch_io(IO_TELL, &f, &offset, NULL, user_data);
  return offset;
}

i64 io_read(i64 f, i64 size, void *data, void *user_data) {
  dispatch_io(IO_READ, &f, &size, data, user_data);
  return size;
}

i64 io_write(i64 f, i64 size, void *data, void *user_data) {
  dispatch_io(IO_WRITE, &f, &size, data, user_data);
  return size;
}

void io_chmod_exe(i64 f, void *user_data) {
  dispatch_io(IO_CHMOD_EXE, &f, NULL, NULL, user_data);
}

//  ================================================================
//
//  * Helper procedures
//
//  ================================================================

#if HELPERS

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdarg.h>

#ifdef __unix__
#include <sys/types.h>
#include <sys/stat.h>
#endif

void wait_any_input(void) {
  while (getc(stdin) != '\n');
  fflush(stdin);
}

void dispatch_assert(b8 condition, c8 *message, u32 line, c8 *file) {
  if (condition)
    return;

  dispatch_log(ERROR, line, file, message);
  exit(-1);
}

void dispatch_log(i32 log_level, u32 line, c8 *file, c8 *format, ...) {
  if (file == NULL || format == NULL)
    return;

  if (*format == '\0' && log_level != TRACE) {
    fprintf(log_level == ERROR || log_level == WARNING ? stderr : stdout, "\n");
    return;
  }

  c8 message[256] = {0};

  va_list ap;
  va_start(ap, format);
  vsnprintf(message, sizeof message, format, ap);
  va_end(ap);

  fflush(stdout);
  i32 len = 56 - (i32) bx_str_len_or(message, message + 56, 56);
  switch (log_level) {
    case ERROR:
      fprintf(stderr,
              "\r\x1b[41;1m\x1b[30m Error   \x1b[40;0m\x1b[37m %s "
              "%.*s \x1b[36m%s\x1b[34m:%d\x1b[37m\n",
              message, len,
              "................................................................",
              file, line);
      if (LOG_BLOCKING)
        wait_any_input();
      break;

    case  WARNING:
      fprintf(stderr,
              "\r\x1b[43;1m\x1b[30m Warning \x1b[40;0m\x1b[37m %s "
              "%.*s \x1b[36m%s\x1b[34m:%d\x1b[37m\n",
              message, len,
              "................................................................",
              file, line);
      if (LOG_BLOCKING)
        wait_any_input();
      break;

    case  INFO:
      fprintf(stdout,
              "\r\x1b[42;1m\x1b[30m Info    \x1b[40;0m\x1b[37m %s\n",
              message);
      break;

    case  VERBOSE:
      fprintf(stdout,
              "\r\x1b[47;1m\x1b[30m Verbose \x1b[40;0m\x1b[37m %s\n",
              message);
      break;

    case  TRACE:
      fprintf(stdout,
              "\r\x1b[45;1m\x1b[30m Trace   \x1b[40;0m\x1b[37m %s "
              "%.*s \x1b[36m%s\x1b[34m:%d\x1b[37m\n",
              message, len,
              "................................................................",
              file, line);
      if (TRACE_BLOCKING)
        wait_any_input();
      break;

    default:;
  }
}

//  IO dispatch procedure
//

void dispatch_io(u16 op, i64 *id, i64 *size, void *data, void *user_data) {
  CHECK(id != NULL, "Invalid arguments",);

  (void) user_data;

  FILE **f                  = (FILE **) id;
  c8     buf[MAX_NAME_SIZE] = { 0 };

  switch (op) {
    case IO_OPEN_READ:
    case IO_OPEN_WRITE:
      CHECK(size != NULL,                       "Invalid arguments",);
      CHECK(*size > 0 && *size < MAX_NAME_SIZE, "Invalid arguments",);
      CHECK(data != NULL,                       "Invalid arguments",);

      mem_cpy(buf, data, *size);
      *f = fopen(buf, op == IO_OPEN_READ ? "rb" : "wb");
      CHECK(*f != NULL, "File open failed",);
      break;

    case IO_CLOSE:
      CHECK(*f != NULL,   "Invalid arguments",);
      CHECK(size == NULL, "Invalid arguments",);
      CHECK(data == NULL, "Invalid arguments",);

      fclose(*f);
      break;

    case IO_SEEK: {
      CHECK(*f != NULL,   "Invalid arguments",);
      CHECK(size != NULL, "Invalid arguments",);
      CHECK(data != NULL, "Invalid arguments",);

      u16 *origin = (u16 *) data;

      if (!(*origin == IO_SEEK_CURSOR && *size == 0)) {
        CHECK(*origin == IO_SEEK_CURSOR ||
                 *origin == IO_SEEK_BEGIN  ||
                 *origin == IO_SEEK_END, "Invalid arguments",);
        i32 s = fseek(*f, *size,
                      *origin == IO_SEEK_CURSOR ? SEEK_CUR :
                      *origin == IO_SEEK_BEGIN  ? SEEK_SET :
                                                  SEEK_END);
        CHECK(s == 0, "File seek failed",);
      }
    } break;

    case IO_TELL: {
        CHECK(*f != NULL,   "Invalid arguments",);
        CHECK(size != NULL, "Invalid arguments",);
        CHECK(data == NULL, "Invalid arguments",);

        i64 n = (i64) ftell(*f);
        CHECK(n >= 0, "File tell failed",);

        *size = n;
    } break;

    case IO_READ:
      CHECK(*f != NULL,   "Invalid arguments",);
      CHECK(size != NULL, "Invalid arguments",);
      CHECK(data != NULL, "Invalid arguments",);
      CHECK(*size > 0,    "Invalid arguments",);

      *size = fread(data, 1, *size, *f);
      break;

    case IO_WRITE:
      CHECK(*f != NULL,   "Invalid arguments",);
      CHECK(size != NULL, "Invalid arguments",);
      CHECK(data != NULL, "Invalid arguments",);
      CHECK(*size > 0,    "Invalid arguments",);

      *size = fwrite(data, 1, *size, *f);
      break;

    case IO_CHMOD_EXE:
      CHECK(*f != NULL,   "Invalid arguments",);
      CHECK(size == NULL, "Invalid arguments",);

#ifdef __unix__
      fchmod(fileno(*f), 0775);
#endif
      break;

    default:
      FAIL("Invalid arguments",);
  }
}

//  Global state
//

Pool g_pool = {
  //  Statically allocate a large memory block.
  //  TODO Reallocate the memory block when necessary.

  .capacity = MAX_NUM_ENTITIES,
  .entities = (Entity[MAX_NUM_ENTITIES]) {0},
};

Codegen_Context g_codegen = {
  .max_num_rels    = MAX_NUM_RELS,
  .max_code_size   = MAX_CODE_SIZE,
  .max_rodata_size = MAX_CODE_SIZE,

  .entry_point     = 0,
  .num_rels        = 0,
  .offset_code     = 0,
  .offset_rodata   = 0,

  .rels            = (Rel_Entry[MAX_NUM_RELS]) {0},
  .buffer_code     = (u8[MAX_CODE_SIZE])       {0},
  .buffer_rodata   = (u8[MAX_CODE_SIZE])       {0},
};

Linker_Context g_linker = {
  .max_obj_file_size     = MAX_OBJECT_FILE_SIZE,
  .max_dependencies_size = MAX_DEPENDENCIES_SIZE,
  .max_num_obj_files     = MAX_NUM_OBJECT_FILES,
  .max_num_sections      = MAX_NUM_SECTIONS,
  .max_num_symbols       = MAX_NUM_SYMBOLS,
  .max_not_found_size    = MAX_NOT_FOUND_SIZE,
  .max_output_size       = MAX_OUTPUT_SIZE,

  .num_obj_files         = 0,

  .obj_file_buffer       = (u8[MAX_OBJECT_FILE_SIZE])      {0},
  .dependencies_buffer   = (u8[MAX_DEPENDENCIES_SIZE])     {0},
  .obj_file_offsets      = (i64[MAX_NUM_OBJECT_FILES])     {0},
  .section_offsets       = (i64[MAX_NUM_SECTIONS])         {0},
  .section_addresses     = (i64[MAX_NUM_SECTIONS])         {0},
  .symbols               = (Symbol_Entry[MAX_NUM_SYMBOLS]) {0},
  .not_found_buffer      = (c8[MAX_NOT_FOUND_SIZE])        {0},
  .output_buffer         = (u8[MAX_OUTPUT_SIZE])           {0},
};

//  Handy procedures
//

i64 n_ref(i64 proc, i64 node) {
  i64 n_ref = node_data_reference(&g_pool, node);
  p_add(proc, n_ref);
  return n_ref;
}

i64 n_ptr(i64 proc, u64 address) {
  i64 n_data = node_data_ptr(&g_pool, address);
  p_add(proc, n_data);
  return n_data;
}

i64 n_str(i64 proc, c8 *value) {
  i64 len    = bx_str_len(value, value + MAX_LITERAL_SIZE - 1);
  i64 n_data = node_data_array_c8(&g_pool, len + 1, value);
  i64 n_ref  = node_data_reference(&g_pool, n_data);
  p_add(proc, n_data);
  p_add(proc, n_ref);
  return n_ref;
}

i64 n_i32(i64 proc, i32 value) {
  i64 n = node_data_i32(&g_pool, value);
  p_add(proc, n);
  return n;
}

i64 n_i64(i64 proc, i64 value) {
  i64 n = node_data_i64(&g_pool, value);
  p_add(proc, n);
  return n;
}

i64 n_call(i64 proc, i64 target_proc, i64 num_args, Var *args) {
  i64 n = node_ctrl_call(&g_pool, target_proc, num_args, args);
  p_add(proc, n);
  return n;
}

i64 n_call_by_name(i64 proc, c8 *name, i64 num_args, Var *args) {
  i64 n = node_ctrl_call_by_name(&g_pool, bx_str_len(name, name + MAX_NAME_SIZE), name, num_args, args);
  p_add(proc, n);
  return n;
}

i64 n_ret(i64 proc, i64 num_vals, Var *vals) {
  i64 n = node_ctrl_ret(&g_pool, num_vals, vals);
  p_add(proc, n);
  return n;
}

i64 p_new(i64 unit, c8 *name) {
  i64 p   = proc_init(&g_pool);
  i64 len = bx_str_len(name, name + MAX_NAME_SIZE);
  if (len > 0)
    proc_set_name(&g_pool, p, len, name);
  u_add(unit, p);
  return p;
}

i64 p_new_entry(i64 unit) {
  i64 p = p_new(unit, "");
  u_entry_point(unit, p);
  return p;
}

void p_add(i64 proc, i64 node) {
  proc_node_add(&g_pool, proc, node);
}

i64 u_new() {
  return unit_init(&g_pool, UNIT_CODE);
}

void u_add(i64 unit, i64 proc) {
  unit_proc_add(&g_pool, unit, proc);
}

void u_entry_point(i64 unit, i64 proc) {
  unit_set_entry_point(&g_pool, unit, proc);
}

void u_elf_x86_64(i64 unit, c8 *output_file_name) {
  i64 name_len = bx_str_len(output_file_name, output_file_name + MAX_PATH_SIZE);
  i64 out      = io_open_write(name_len, output_file_name, NULL);

  unit_write(&g_pool, &g_codegen, &g_linker, unit, FORMAT_ELF, ARCH_X86_64, out, NULL);

  io_chmod_exe(out, NULL);
  io_close(out, NULL);
}

void l_code(i64 unit, i64 link_unit) {
  unit_link_add(&g_pool, unit, link_unit);
}

void l_object(i64 unit, c8 *object_library) {
  i64 l = unit_init(&g_pool, UNIT_LIBRARY_OBJECT);
  unit_set_name(&g_pool, l, bx_str_len(object_library, object_library + MAX_PATH_SIZE), object_library);
  unit_link_add(&g_pool, unit, l);
}

void l_static(i64 unit, c8 *static_library) {
  i64 l    = unit_init(&g_pool, UNIT_LIBRARY_STATIC);
  c8 *path = l_find(static_library);
  i64 len  = bx_str_len(path, path + MAX_PATH_SIZE);
  unit_set_name(&g_pool, l, len, path);
  unit_link_add(&g_pool, unit, l);
}

c8 *l_find(c8 *name) {
  //  Find the full path to a library

  CHECK(name != NULL, "Invalid argument", "");
  CHECK(bx_str_len(name, name + MAX_PATH_SIZE) < MAX_PATH_SIZE, "Invalid argument", "");

  static c8 buf[MAX_PATH_SIZE]; // FIXME

  #define TRY_(template)                           \
    do {                                           \
      snprintf(buf, sizeof buf, (template), name); \
      FILE *f = fopen(buf, "rb");                  \
      if (f == NULL) break;                        \
      fclose(f);                                   \
      LOG(VERBOSE, "Found library: %s", buf);      \
      return buf;                                  \
    } while (0)

  TRY_("%s");
  TRY_("lib%s.a");
  TRY_("/lib/x86_64-linux-gnu/%s");
  TRY_("/lib/x86_64-linux-gnu/lib%s.a");

  #undef TRY_

  FAIL("Library not found", "");
}

#endif

//  ================================================================
//
//    EXAMPLE
//
//  ================================================================

#if HELPERS && TESTING

int main(int argc, char **argv) {
  (void) argc;
  (void) argv;

  LOG(INFO, "bxgen " VERSION);

  //  ============================================================
  //
  //  Create the program semantic tree

  //  Add a compilation unit.
  i64 u = u_new();

  //  Add the main proc.
  //  NOTE We don't need a name for it.
  i64 mainproc = p_new(u, "");
  {
    //  Call puts
    N_CALL_BY_NAME(
      mainproc,
      "puts",                         // proc name
      n_str(mainproc, "hello sailor") // the first argument
    );

    //  Return 42
    N_RET(
      mainproc,
      n_i32(mainproc, 42) // the return value
    );
  }

  //  Add the entry point.
  i64 entry = p_new_entry(u);
  {
    //  Initialize libc
    N_CALL_BY_NAME(
      entry,
      "__libc_start_main",
      n_ref(entry, mainproc),        // main
      n_i32(entry, 0),               // argc
      n_ref(entry, n_ptr(entry, 0)), // argv
      n_ptr(entry, 0),               // init
      n_ptr(entry, 0),               // fini
      n_ptr(entry, 0),               // rtld_fini
      n_ptr(entry, 0)                // stack_end
    );

    //  Return
    n_ret(entry, 0, NULL);
  }

  //  ============================================================
  //
  //  Compile and link

  //  Add a static library.
  l_static(u, "c");
  // l_static(u, "test");

  //  Write the compilation unit into an executable file.
  u_elf_x86_64(u, "test_foo");

  //  ============================================================

  if (HOST != HOST_Linux) {
    LOG(INFO, "Skip running the executable. Host system is not compatible.");
  } else if (HO != LE) {
    LOG(INFO, "Skip running the executable. Host data ordering is not compatible.");
  } else {
    //  Run the created executable file.
    i32 ret = system("./test_foo");

    CHECK(WEXITSTATUS(ret) == 42, "Failure", -1);
  }

  LOG(INFO, "Bye!");
  return 0;
}

#endif

#endif