From 1d943da0cf9154e7ce78ce867cdbb91531c5d78e Mon Sep 17 00:00:00 2001 From: Matthew Sotoudeh Date: Tue, 25 Jul 2023 14:58:33 -0700 Subject: initial dietc commit --- typegen.c | 304 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 304 insertions(+) create mode 100644 typegen.c (limited to 'typegen.c') diff --git a/typegen.c b/typegen.c new file mode 100644 index 0000000..75b3cff --- /dev/null +++ b/typegen.c @@ -0,0 +1,304 @@ +#include "chibicc.h" + +static Type **HASH_MAP = 0; +static int CAP_HASH_MAP = 0; +static int N_HASH_MAP = 0; +Type *hash_lookup(Type *type) { + if (!CAP_HASH_MAP) return 0; + + size_t idx = hash_type(type) % CAP_HASH_MAP; + while (HASH_MAP[idx]) { + if (definitely_same_type(HASH_MAP[idx], type)) { + return HASH_MAP[idx]; + } + if (++idx == CAP_HASH_MAP) idx = 0; + } + return 0; +} + +void hash_insert(Type *type) { + if ((N_HASH_MAP + 1) >= (CAP_HASH_MAP / 2)) { + // RESIZE AND REHASH + int old_cap = CAP_HASH_MAP; + Type **old_hash_map = HASH_MAP; + + CAP_HASH_MAP = (CAP_HASH_MAP + 1) * 4; + N_HASH_MAP = 0; + HASH_MAP = calloc(CAP_HASH_MAP, sizeof(HASH_MAP[0])); + for (int i = 0; i < old_cap; i++) { + if (old_hash_map[i]) + hash_insert(old_hash_map[i]); + } + if (old_hash_map) free(old_hash_map); + } + + N_HASH_MAP++; + size_t idx = hash_type(type) % CAP_HASH_MAP; + while (HASH_MAP[idx]) { + if (++idx == CAP_HASH_MAP) idx = 0; + } + HASH_MAP[idx] = type; +} + +static int count(void) { + static int i = 1; + return i++; +} + +static void printnoln(char *fmt, ...); +static void println(char *fmt, ...); + +static void print_tok(Token *tok) { + if (tok->str) printnoln("%s", tok->str); + else { + assert(tok->loc); + for (int i = 0; i < tok->len; i++) + printnoln("%c", tok->loc[i]); + } +} + +const void addrdecl(Type *type); +const void typedecl(Type *type) { + if (type->id) return; + if (type->kind == TY_ARRAY) + addrdecl(type->base); + Type *hashed = hash_lookup(type); + if (hashed && !(hashed->typedecling)) { + assert(hashed->id); + type->id = hashed->id; + if (hashed->pointer_type) + type->pointer_type = hashed->pointer_type; + if (hashed->return_ty) + type->return_ty = hashed->return_ty; + if (hashed->params) + type->params = hashed->params; + return; + } + type->typedecling = 1; + type->id = count(); + hash_insert(type); + switch (type->kind) { + case TY_FLOAT: + println("typedef float Type_%d ;", type->id); + break; + case TY_DOUBLE: + println("typedef double Type_%d ;", type->id); + break; + case TY_LDOUBLE: + println("typedef long double Type_%d ;", type->id); + break; + case TY_INT: + if (type->is_unsigned) + println("typedef unsigned int Type_%d ;", type->id); + else + println("typedef int Type_%d ;", type->id); + break; + case TY_LONG: + if (type->is_unsigned) + println("typedef unsigned long Type_%d ;", type->id); + else + println("typedef long Type_%d ;", type->id); + break; + case TY_SHORT: + if (type->is_unsigned) + println("typedef unsigned short Type_%d ;", type->id); + else + println("typedef short Type_%d ;", type->id); + break; + case TY_VOID: + println("typedef void Type_%d ;", type->id); + break; + case TY_BOOL: + println("typedef _Bool Type_%d ;", type->id); + break; + case TY_CHAR: + println("typedef char Type_%d ;", type->id); + break; + case TY_PTR: + typedecl(type->base); + println("typedef Type_%d * Type_%d ;", type->base->id, type->id); + break; + case TY_FUNC: { + typedecl(type->return_ty); + for (Type *p = type->params; p; p = p->next) + typedecl(p); + printnoln("typedef Type_%d Type_%d ( ", type->return_ty->id, type->id); + + int i = 0; + for (Type *p = type->params; p; p = p->next, i++) + if (i) printnoln(", Type_%d ", p->id); + else printnoln("Type_%d ", p->id); + + if (type->is_variadic) { + if (i) printnoln(", ... "); + // else printnoln("... "); + } + println(") ;"); + addrdecl(type); + break; + } + case TY_ARRAY: + typedecl(type->base); + if (type->array_len == -1) + println("typedef Type_%d Type_%d [ ] ;", type->base->id, type->id); + else + println("typedef Type_%d Type_%d [ %d ] ;", type->base->id, type->id, + type->array_len); + break; + case TY_STRUCT: + case TY_UNION: + if (type->kind == TY_STRUCT) + println("typedef struct Struct_%d Type_%d ;", type->id, type->id); + else + println("typedef union Union_%d Type_%d ;", type->id, type->id); + + for (Member *m = type->members; m; m = m->next) + typedecl(m->ty); + + if (type->kind == TY_STRUCT) printnoln("struct Struct_%d { ", type->id); + else printnoln("union Union_%d { ", type->id); + for (Member *m = type->members; m; m = m->next) { + printnoln("Type_%d ", m->ty->id); + if (m->name) + print_tok(m->name); + else if (m->ty->kind == TY_STRUCT || m->ty->kind == TY_UNION) + printnoln("___dietc_f%d", m->idx); + else + printnoln("__field_%d", count()); + printnoln(" ; "); + } + println("} ;"); + break; + case TY_ENUM: + println("typedef enum Enum_%d { EN_%d } Type_%d ;", type->id, type->id, type->id); + break; + case TY_VLA: + assert(!"unimplemented vla?"); + break; + default: + assert(!"unimplemented?"); + break; + } + type->typedecling = 0; +} + +static FILE *output_file; +static Obj *current_fn; + +__attribute__((format(printf, 1, 2))) +static void println(char *fmt, ...) { + va_list ap; + va_start(ap, fmt); + vfprintf(output_file, fmt, ap); + va_end(ap); + fprintf(output_file, "\n"); +} + +__attribute__((format(printf, 1, 2))) +static void printnoln(char *fmt, ...) { + va_list ap; + va_start(ap, fmt); + vfprintf(output_file, fmt, ap); + va_end(ap); +} + +const void addrdecl(Type *type) { + if (type->pointer_type) return; + type->pointer_type = pointer_to(type); + typedecl(type->pointer_type); +} + +static void gen_addr_decls(Node *node) { + switch (node->kind) { + case ND_VAR: + addrdecl(node->ty); + return; + case ND_COMMA: + gen_addr_decls(node->rhs); + return; + case ND_MEMBER: + gen_addr_decls(node->lhs); + addrdecl(node->ty); + return; + } +} + +// Generate code for a given node. +static void gen_typedecls(Node *node) { + if (!node) return; + if (node->ty) typedecl(node->ty); + gen_typedecls(node->lhs); + gen_typedecls(node->rhs); + gen_typedecls(node->cond); + gen_typedecls(node->then); + gen_typedecls(node->els); + gen_typedecls(node->init); + gen_typedecls(node->inc); + for (Node *n = node->body; n; n = n->next) + gen_typedecls(n); + for (Node *arg = node->args; arg; arg = arg->next) + gen_typedecls(arg); + if (node->kind == ND_SWITCH) + for (Node *n = node->case_next; n; n = n->case_next) + gen_typedecls(n); + + switch (node->kind) { + case ND_VAR: + if (node->ty->kind == TY_ARRAY) + addrdecl(node->ty->base); + break; + case ND_CAST: + if (node->lhs->ty->kind == TY_UNION) + gen_addr_decls(node->lhs); + addrdecl(node->ty); + break; + case ND_MEMBER: + gen_addr_decls(node); + if (node->ty->kind == TY_ARRAY) + addrdecl(node->ty->base); + break; + case ND_ADDR: + case ND_ASSIGN: + gen_addr_decls(node->lhs); + break; + } +} + +static void typedecl_data(Obj *prog) { + for (Obj *var = prog; var; var = var->next) { + // if (var->is_function || !var->is_definition) + // continue; + typedecl(var->ty); + } +} + +static void typedecl_text(Obj *prog) { + for (Obj *fn = prog; fn; fn = fn->next) { + if (!fn->is_function || !fn->is_definition) + continue; + + // No code is emitted for "static inline" functions + // if no one is referencing them. + if (!fn->is_live) + continue; + + current_fn = fn; + + typedecl(fn->ty); + gen_typedecls(fn->body); + + // ensure function params & locals are typegened + for (Obj *var = fn->locals; var; var = var->next) { + typedecl(var->ty); + } + } +} + +void typegen(Obj *prog, FILE *out) { + output_file = out; + + printnoln("#include \"%s/scripts/dietc_helpers.h\"\n", DIETC_ROOT); + typedecl(ty_int); + typedecl_data(prog); + typedecl_text(prog); +} -- cgit v1.2.3