path: root/binary_code_generation.c

#if 0
SRC=${0##*/}
BIN=${SRC%.*}
gcc -o $BIN.tmp $SRC && ./$BIN.tmp $@ && rm $BIN.tmp
exit $?
#endif

//  ================================================================
//
//    Binary code generation compiler backend
//
//  Traits
//
//  - Single source file
//  - Simple and flexible API
//  - No external dependencies
//  - No configuration required
//  - No dynamic memory management
//
//  TODO
//
//  - ELF + x86_64 executable
//  - x86_64 object file
//  - Linking libraries
//  - Effective entity allocation
//  - Linked lists for large entities
//  - Sea of Nodes
//  - Optimization layers
//  - Multithreading
//
//  ================================================================
//
//    Basic declarations
//
//  ================================================================

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

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;
typedef int                b32;
typedef char               c8;

//  ================================================================
//
//    Intermediate representation
//
//  ================================================================

//  Declarations
//

enum {
  //  For indices
  UNDEFINED = -1,

  //  Sea of Nodes flow type
  //

  FLOW_DATA = 0,
  FLOW_CONTROL,

  //  Semantic node operations
  //

  OP_I64 = 0,
  OP_RET,

  //  Object file
  UNIT_OBJ = 0,

  //  Executable
  UNIT_EXE,

  //  Entity types
  //

  TYPE_NODE = 0,
  TYPE_PROC,
  TYPE_UNIT,

  //  Limits
  //
  //    NOTE
  //
  //    All limits can be exceeded using the linked list of entities
  //    (see `entity_t::tail`), except for `MAX_ENTITY_COUNT`.
  //

  MAX_LITERAL_SIZE = 512,
  MAX_NAME_SIZE    = 128,
  MAX_PROC_COUNT   = 126,
  MAX_NODE_COUNT   = 110,
  MAX_ENTITY_COUNT = 16384,
};

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

typedef struct {
  i16 op;
  i8  flow;
  union {
    u8  lit_bytes[MAX_LITERAL_SIZE]; // byte array literal
    i64 lit_int;                     // integer literal
    i64 ref_node[4];                 // references to other nodes
  };
} node_t;

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

typedef struct {
  i64 name_size;
  c8  name[MAX_NAME_SIZE];
  i64 node_count;
  i64 nodes[MAX_NODE_COUNT];
} proc_t;

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

typedef struct {
  i16 type;
  i64 proc_count;
  i64 procs[MAX_PROC_COUNT];
} unit_t;

//  An entity can be any of:
//  - `node_t`
//  - `proc_t`
//  - `unit_t`
//
//  Every entity can be referenced by it's unique index
//  in the entity pool.
//
//  If the entity's data doesn't fit in one entity, tail is
//  an index that leads to the entity with the rest of the
//  data, forming a linked list.
//

typedef struct {
  b8  is_enabled;
  i16 type;
  i64 tail;
  union {
    node_t node;
    proc_t proc;
    unit_t unit;
  };
} entity_t;

//  Pool, a collection of all entities.
//

typedef struct {
  i64      entity_count;
  entity_t entities[MAX_ENTITY_COUNT];
} entity_pool_t;

//  IR building procs
//

i64 pool_entity_add(entity_pool_t *pool, entity_t data) {
  assert(pool != NULL);
  assert(pool->entity_count < MAX_ENTITY_COUNT);

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

  return id;
}

void pool_entity_remove(entity_pool_t *pool, i64 entity, i16 type) {
  assert(pool != NULL);
  assert(pool->entities[entity].is_enabled);
  assert(pool->entities[entity].type == type);

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

i64 node_init(entity_pool_t *pool, node_t data) {
  return pool_entity_add(pool, (entity_t) {
    .type = TYPE_NODE,
    .tail = UNDEFINED,
    .node = data,
  });
}

void node_destroy(entity_pool_t *pool, i64 node) {
  pool_entity_remove(pool, node, TYPE_NODE);
}

i64 proc_init(entity_pool_t *pool) {
  return pool_entity_add(pool, (entity_t) {
    .type = TYPE_PROC,
    .tail = UNDEFINED,
  });
}

void proc_destroy(entity_pool_t *pool, i64 proc) {
  pool_entity_remove(pool, proc, TYPE_PROC);
}

void proc_set_name(entity_pool_t *pool, i64 proc, i64 name_size, c8 *name) {
  assert(pool != NULL);
  assert(pool->entities[proc].is_enabled);
  assert(pool->entities[proc].type == TYPE_PROC);

  //  TODO
  //  Implement large entities.
  assert(name_size <= MAX_NAME_SIZE);
  assert(name_size > 0);

  proc_t *p    = &pool->entities[proc].proc;
  p->name_size = name_size;
  memcpy(p->name, name, name_size);
}

void proc_node_add(entity_pool_t *pool, i64 proc, i64 node) {
  assert(pool != NULL);
  assert(pool->entities[proc].is_enabled);
  assert(pool->entities[proc].type == TYPE_PROC);
  assert(pool->entities[node].is_enabled);
  assert(pool->entities[node].type == TYPE_NODE);

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

  //  TODO
  //  Implement large entities.
  assert(p->node_count < MAX_NODE_COUNT);

  p->nodes[p->node_count++] = node;
}

void proc_node_remove(entity_pool_t *pool, i64 proc, i64 node) {
  assert(pool != NULL);
  assert(pool->entities[proc].is_enabled);
  assert(pool->entities[proc].type == TYPE_PROC);
  assert(pool->entities[node].type == TYPE_NODE);

  pool->entities[proc].proc.nodes[node] = UNDEFINED;
}

i64 unit_init(entity_pool_t *pool) {
  return pool_entity_add(pool, (entity_t) {
    .type = TYPE_UNIT,
    .tail = UNDEFINED,
  });
}

void unit_destroy(entity_pool_t *pool, i64 unit) {
  pool_entity_remove(pool, unit, TYPE_UNIT);
}

void unit_proc_add(entity_pool_t *pool, i64 unit, i64 proc) {
  assert(pool != NULL);
  assert(pool->entities[unit].is_enabled);
  assert(pool->entities[unit].type == TYPE_UNIT);
  assert(pool->entities[proc].is_enabled);
  assert(pool->entities[proc].type == TYPE_PROC);

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

  //  TODO
  //  Implement large entities.
  assert(u->proc_count < MAX_PROC_COUNT);

  u->procs[u->proc_count++] = proc;
}

void unit_proc_remove(entity_pool_t *pool, i64 unit, i64 proc) {
  assert(pool != NULL);
  assert(pool->entities[unit].is_enabled);
  assert(pool->entities[unit].type == TYPE_UNIT);
  assert(pool->entities[proc].type == TYPE_PROC);

  pool->entities[unit].unit.procs[proc] = UNDEFINED;
}

//  Global state
//

static entity_pool_t g_pool = { 0 };

//  Helper functions
//

i64 op_i64(i64 value) {
  return node_init(&g_pool, (node_t) {
    .op      = OP_I64,
    .flow    = FLOW_DATA,
    .lit_int = value,
  });
}

i64 op_ret(i64 node_return_value) {
  return node_init(&g_pool, (node_t) {
    .op       = OP_RET,
    .flow     = FLOW_CONTROL,
    .ref_node = node_return_value,
  });
}

//  ================================================================
//
//    Code generation proc
//
//  ================================================================

int main(int argc, char **argv) {
  printf("node - %d bytes\n", (i32) sizeof(node_t));
  printf("proc - %d bytes\n", (i32) sizeof(proc_t));
  printf("unit - %d bytes\n", (i32) sizeof(unit_t));

  printf("\nBye!\n");
  return 0;
}