initial dietc commit

1 files changed, 304 insertions, 0 deletions

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);
+}