compilers/tac/main.c

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#include "nodes.h"
#include "C.tab.h"
#include "types.h"
#include "list.h"

int asprintf(char **strp, const char *fmt, ...);
extern TOKEN* lookup_token(char*);

/*
 * Existing problems/todo:
 * return from control block, need a "return address" to jump to -- call levels
 * --multiple assignments `int x,y,z = 1`--
 * new block scope for if statements?
 * arguments for functions
 * difference between tilde and semicolon
 * while loops
 * control flow `continue` and `break` linked to return address sort of? call levels
 */

TOKEN* gen_tmp(void) {
  char* tmp;
  static char letter = 'a';
  static char num = 0;
  if (num == 100) {
    num = 0;
    if (++letter == 'r') letter++;
  }
  if (letter == '{') exit(1);
  asprintf(&tmp, "\\%c%d", letter, num);
  num++;
  return lookup_token(tmp);
}

char *named(int t)
{
    static char b[100];
    if (isgraph(t) || t==' ') {
      sprintf(b, "%c", t);
      return b;
    }
    switch (t) {
      default: return "???";
    case IDENTIFIER:
      return "id";
    case CONSTANT:
      return "constant";
    case STRING_LITERAL:
      return "string";
    case LE_OP:
      return "<=";
    case GE_OP:
      return ">=";
    case EQ_OP:
      return "==";
    case NE_OP:
      return "!=";
    case EXTERN:
      return "extern";
    case AUTO:
      return "auto";
    case INT:
      return "int";
    case VOID:
      return "void";
    case APPLY:
      return "apply";
    case LEAF:
      return "leaf";
    case IF:
      return "if";
    case ELSE:
      return "else";
    case WHILE:
      return "while";
    case CONTINUE:
      return "continue";
    case BREAK:
      return "break";
    case RETURN:
      return "return";
    }
}



void print_leaf(NODE *tree, int level)
{
    TOKEN *t = (TOKEN *)tree;
    int i;
    for (i=0; i<level; i++) putchar(' ');
    if (t->type == CONSTANT) printf("%d\n", t->value);
    else if (t->type == STRING_LITERAL) printf("\"%s\"\n", t->lexeme);
    else if (t) puts(t->lexeme);
}

void print_tree0(NODE *tree, int level)
{
    int i;
    if (tree==NULL) return;
    if (tree->type==LEAF) {
      print_leaf(tree->left, level);
    }
    else {
      for(i=0; i<level; i++) putchar(' ');
      printf("%s\n", named(tree->type));

/*       if (tree->type=='~') { */
/*         for(i=0; i<level+2; i++) putchar(' '); */
/*         printf("%p\n", tree->left); */
/*       } */
/*       else */
        print_tree0(tree->left, level+2);
      print_tree0(tree->right, level+2);
    }
}

void print_tree(NODE *tree)
{
    print_tree0(tree, 0);
}

// void add_function_to_env(NODE *tree, ENV *env_ptr) {
//   BIND* existing;
//   NODE* func_name = tree->left->right->left->left;
//   TOKEN* name_token = (TOKEN*) func_name;
//   if ((existing = find_name_in_env(name_token->lexeme, env_ptr)) == NULL) {
//     printf("Added function name %s to environment with value: \n", name_token->lexeme);
//     print_tree(tree);
//     if (env_ptr->bindings == NULL) {
//       env_ptr->bindings = create_list(create_binding(name_token->lexeme, tree, env_ptr), NULL);
//     } else {
//       append_list(env_ptr->bindings, create_binding(name_token->lexeme, tree, env_ptr));
//     }
//   } else {
//     printf("Updating function name %s with value: \n", name_token->lexeme);
//     print_tree(tree);
//     existing->tree = tree;
//     existing->env = env_ptr;
//   }
// }


// void add_var_to_env(NODE *tree, ENV *env_ptr) {
//   BIND* existing;
//   NODE* var_name = tree->left->left;
//   TOKEN* name_token = (TOKEN*) var_name;
//   TOKEN* tok = new_token(INT);
//   tok->value = recursive_interpret(tree->right, env_ptr);
//   asprintf(&tok->lexeme, "%d", tok->value);
//   if ((existing = find_name_in_env(name_token->lexeme, env_ptr)) == NULL) {
//     printf("Added variable name %s to environment with value: %s\n", name_token->lexeme, tok->lexeme);
//     if (env_ptr->bindings == NULL) {
//       env_ptr->bindings = create_list(create_binding(name_token->lexeme, (NODE*) tok, NULL), NULL);
//     } else {
//       append_list(env_ptr->bindings, create_binding(name_token->lexeme, (NODE*) tok, NULL));
//     }
//   } else {
//     printf("Updating variable name %s with value: %s\n", name_token->lexeme, tok->lexeme);
//     existing->tree = (NODE *) tok;
//   } 
// }

void new_tac(TACS* tacs, TOKEN* dst, TOKEN* src, TOKEN* tgt, int op) {
  if (tacs->list == NULL) {
    TAC_T* tac;
    tac = create_tac(op, src, tgt, dst);
    tacs->list = new_tac_list(tac, NULL);
  } else {
    add_tac(tacs->list, op, src, tgt, dst);
  }
}

char* stok(TOKEN* tok) {
  return tok->lexeme;
}

void print_tac(TLIST* tac_list) {
  TLIST *ptr = tac_list;

  while (ptr != NULL) {
    int op = ptr->elem->op;
    if (op == '=') printf("%s := %s\n", stok(ptr->elem->dst), stok(ptr->elem->src));
    if (op == '+') printf("%s := %s + %s\n", stok(ptr->elem->dst), stok(ptr->elem->src), stok(ptr->elem->tgt));
    if (op == '-') printf("%s := %s - %s\n", stok(ptr->elem->dst), stok(ptr->elem->src), stok(ptr->elem->tgt));
    if (op == '/') printf("%s := %s / %s\n", stok(ptr->elem->dst), stok(ptr->elem->src), stok(ptr->elem->tgt));
    if (op == '*') printf("%s := %s * %s\n", stok(ptr->elem->dst), stok(ptr->elem->src), stok(ptr->elem->tgt));
    if (op == '%') printf("%s := %s %% %s\n", stok(ptr->elem->dst), stok(ptr->elem->src), stok(ptr->elem->tgt));
    if (op == RETURN) printf("ret %s\n", stok(ptr->elem->src));
    ptr = ptr->next;
  }
}

TOKEN* build_tac(NODE *tree, TACS* tac) {
  if (tree == NULL) return NULL;
  int type = tree->type;
  if (type == LEAF) {
    return (TOKEN *) tree->left;
  } else if (type == '=') {
    TOKEN* dst = (TOKEN*) tree->left->left;
    TOKEN* result = build_tac(tree->right, tac);
    new_tac(tac, dst, result, NULL, tree->type);
  } else if (type=='+' || type=='-' || type=='*' || type=='/' || type =='%') {
    TOKEN* dst = gen_tmp();
    TOKEN* src = build_tac(tree->left, tac);
    TOKEN* tgt = build_tac(tree->right, tac);
    new_tac(tac, dst, src, tgt, tree->type);
    return dst;
  } else if (type == RETURN) {
    TOKEN* src = build_tac(tree->left, tac);
    new_tac(tac, NULL, src, NULL, RETURN);
  } else {
    build_tac(tree->left, tac);
    build_tac(tree->right, tac);
  }
}


int tmp_regs[10] = {8, 9, 10, 11, 12, 13, 14, 15, 24, 25};
int svd_regs[8]  = {16, 17, 18, 19, 20, 21, 22, 23};
int tmp_cntr = 0;
VARLOC** vartab;

int is_imm(TOKEN *t) {
  if (t->type==CONSTANT) return 1;
  else return 0;
}

int find_var_idx(TOKEN* var) {
  int i;
  for (i = 0; i < 8; i++) { 
    if (vartab[i]->var == var) {
      return vartab[i]->loc_idx;
    }
  }
  return -1;
}

int store_var(TOKEN* name) {
  int i;
  for (i = 0; i < 8; i++) {
    if (vartab[i]->var == NULL) {
      vartab[i]->var = name;
      vartab[i]->loc_idx = svd_regs[i];
      return vartab[i]->loc_idx;
    } else if (name == vartab[i]->var) {
      vartab[i]->loc_idx = svd_regs[i];
      return svd_regs[i];
    }
  }
  printf("bugger\n");
  exit(1);
}

void init_reg() {
  int i;
  vartab = (VARLOC**) malloc(8 * sizeof(VARLOC*));
  for (i = 0; i < 8; i++) {
    vartab[i] = (VARLOC*) malloc(sizeof(VARLOC));
    vartab[i]->var = NULL;
    vartab[i]->loc_idx = -1;
  }
}

int alloc_register(TOKEN* val) {
  int idx;
  int imm = is_imm(val);
  if (imm) {
    if (val->value <= 32767 && val->value >= -32767) {
      printf("ori $%d, $0, %d\n", tmp_regs[tmp_cntr], val->value);
      idx = tmp_regs[tmp_cntr++];
    } else {
      printf("li $%d, %d\n", tmp_regs[tmp_cntr], val->value);
      idx = tmp_regs[tmp_cntr++];
    }
  } else {
    idx = find_var_idx(val);
  }
  if (tmp_cntr == 10) tmp_cntr = 0;
  return idx;
}

void compile_tac(TLIST* tacs) {
  printf("=====\n");
  printf("main:\n");
  init_reg();
  while(tacs != NULL) {
    TAC_T* t = tacs->elem;
    if (t->op == '=') {
      int src_idx = alloc_register(t->src);
      printf("or $%d, $0, $%d\n", store_var(t->dst), src_idx);
    }
    if (t->op == '+') {
      int tgt_idx = alloc_register(t->tgt);
      int src_idx = alloc_register(t->src);
      printf("add $%d, $%d, $%d\n", store_var(t->dst), src_idx, tgt_idx);
    }
    if (t->op == '-') {
      int tgt_idx = alloc_register(t->tgt);
      int src_idx = alloc_register(t->src);
      printf("sub $%d, $%d, $%d\n", store_var(t->dst), src_idx, tgt_idx);
    }
    if (t->op == '*') {
      int tgt_idx = alloc_register(t->tgt);
      int src_idx = alloc_register(t->src);
      printf("mult $%d, $%d\n", src_idx, tgt_idx);
      printf("mflo $%d\n", store_var(t->dst));
    }
    if (t->op == '/') {
      int tgt_idx = alloc_register(t->tgt);
      int src_idx = alloc_register(t->src);
      printf("div $%d, $%d\n", src_idx, tgt_idx);
      printf("mflo $%d\n", store_var(t->dst));
    }
    if (t->op == '%') {
      int tgt_idx = alloc_register(t->tgt);
      int src_idx = alloc_register(t->src);
      printf("div $%d, $%d\n", src_idx, tgt_idx);
      printf("mfhi $%d\n", store_var(t->dst));
    }
    if (t->op == RETURN) {
      int src_idx = alloc_register(t->src);
      printf("or $k0, $0, $%d\n", src_idx);
    }
    tacs = tacs->next;
  }
  printf("ori $v0, 10\n");
  printf("syscall\n");
}

// ENV* cons_global_env(NODE *tree) {
//   ENV* global = create_new_function_env(NULL);
//   recursive_interpret(tree, global);
//   return global;
// }

void interpret_tree(NODE *tree) {
  // ENV* global_env = cons_global_env(tree);
  // BIND* ref_main = find_name_in_env("main", global_env);
  // if (ref_main == NULL) {
  //   printf("Could not find main, cannot run!\n");
  //   exit(1);
  // }
  // print ref_main to make sure we really got it
  // printf("Located %s, ready to run!\n", ref_main->name);
  // printf("%d\n", recursive_interpret(ref_main->tree->right, ref_main->env));
  TACS* gen_tac = (TACS*) malloc(sizeof(TACS));
  build_tac(tree, gen_tac);
  print_tac(gen_tac->list);
  compile_tac(gen_tac->list);
}

extern int yydebug;
/* extern NODE* yyparse(void); */
extern NODE* ans;
extern void init_symbtable(void);

int main(int argc, char** argv)
{
    NODE* tree;
    if (argc>1 && strcmp(argv[1],"-d")==0) yydebug = 1;
    init_symbtable();
    printf("--C COMPILER\n");
    yyparse();
    tree = ans;
    printf("parse finished\n");
    print_tree(tree);
    interpret_tree(tree);
    // int i;
    // for (i = 0; i < 2600; i++) printf("%s\n", gen_tmp());
    return 0;
}