diff options
Diffstat (limited to 'binary_code_generation.c')
| -rwxr-xr-x | binary_code_generation.c | 333 |
1 files changed, 333 insertions, 0 deletions
diff --git a/binary_code_generation.c b/binary_code_generation.c new file mode 100755 index 0000000..0f0d374 --- /dev/null +++ b/binary_code_generation.c @@ -0,0 +1,333 @@ +#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; +} |