symbol.c


    1 #include <stdio.h>
    2 #include <assert.h>
    3 #include <string.h>
    4 #include "xcc.h"
    5 #include "AST.h"
    6 #include "type.h"
    7 #include "symbol.h"
    8 
    9 static struct Symbol *symbol_lookup_at(char *name, struct Symbol *head);
   10 static struct Symbol *symbol_lookup_global(char *name);
   11 static struct Symbol *symbol_lookup_arg(char *name);
   12 static struct Symbol *symbol_lookup_local(char *name);
   13 static void symbol_free(struct Symbol *symbol);
   14 static void symbol_dump(struct Symbol *symbol);
   15 static void string_dump(struct String *string);
   16 static int set_offset(struct Symbol *sym, int base);
   17 
   18 struct SymbolTable symbol_table = {NULL, NULL, NULL, NULL, -1};
   19 int total_arg_size;
   20 static int total_local_size;
   21 static int local_size[MAX_BLOCK_DEPTH];
   22 
   23 static struct Symbol *symbol_lookup_at(char *name, struct Symbol *head) {
   24 	struct Symbol *symbol;
   25 
   26 	for (symbol = head; symbol != NULL; symbol = symbol->next) {
   27 		if (!strcmp(symbol->name, name))
   28 			return symbol;
   29 	}
   30 	return NULL;
   31 }
   32 
   33 static void symbol_free(struct Symbol *symbol) {
   34 	struct Symbol *next;
   35 
   36 	if (symbol == NULL)
   37 		return;
   38 	next = symbol->next;
   39 	efree(symbol);
   40 	symbol_free(next);
   41 }
   42 
   43 static void symbol_dump(struct Symbol *symbol) {
   44 	if (symbol == NULL)
   45 		printf("\n");
   46 	else {
   47 		printf("%s, ", symbol->name);
   48 		symbol_dump(symbol->next);
   49 	}
   50 }
   51 
   52 static void string_dump(struct String *string) {
   53 	if (string == NULL)
   54 		printf("\n");
   55 	else {
   56 		printf("%s (%s), ", string->data, string->label);
   57 		string_dump(string->next);
   58 	}
   59 }
   60 
   61 static struct Symbol *symbol_lookup_global(char *name) {
   62 	return symbol_lookup_at(name, symbol_table.global);
   63 }
   64 
   65 static struct Symbol *symbol_lookup_arg(char *name) {
   66 	return symbol_lookup_at(name, symbol_table.arg);
   67 }
   68 
   69 static struct Symbol *symbol_lookup_current_local(char *name) {
   70 	return symbol_lookup_at(name, symbol_table.local[symbol_table.local_index]);
   71 }
   72 
   73 static struct Symbol *symbol_lookup_local(char *name) {
   74 	int i;
   75 	struct Symbol *symbol;
   76 
   77 	for (i = symbol_table.local_index; i >= 0; i--) {
   78 		symbol = symbol_lookup_at(name, symbol_table.local[i]);
   79 		if (symbol != NULL)
   80 			return symbol;
   81 	}
   82 	return NULL;
   83 }
   84 
   85 static int set_offset(struct Symbol *symbol, int base) {
   86 	int size;
   87 
   88 	if (symbol == NULL)
   89 		return base;
   90 	symbol->offset = set_offset(symbol->next, base);
   91 	size = ROUNDUP(symbol->type->size, 4);
   92 	return symbol->offset + size;
   93 }
   94 
   95 struct Symbol *symbol_lookup(char *name) {
   96 	struct Symbol *symbol;
   97 
   98 	symbol = symbol_lookup_local(name);
   99 	if (symbol != NULL)
  100 		return symbol;
  101 	symbol = symbol_lookup_arg(name);
  102 	if (symbol != NULL)
  103 		return symbol;
  104 	symbol = symbol_lookup_global(name);
  105 	if (symbol != NULL)
  106 		return symbol;
  107 	return NULL;
  108 }
  109 
  110 struct String *string_lookup(char *data) {
  111 	struct String *string;
  112 
  113 	for (string = symbol_table.string; string != NULL; string = string->next) {
  114 		if (!strcmp(string->data, data))
  115 			return string;
  116 	}
  117 	return NULL;
  118 }
  119 
  120 struct Symbol *symbol_lookup_label(char *name) {
  121 	return symbol_lookup_at(name, symbol_table.label);
  122 }
  123 
  124 void symbol_entry(struct AST *ast) {
  125 	struct Symbol **entry;
  126 	struct Symbol *symbol = emalloc(sizeof(struct Symbol));
  127 	struct Symbol *symbol2;
  128 
  129 	if (ast->ast_type == AST_statement_label)
  130 		symbol->name = ast->u.child[0]->u.id;
  131 	else
  132 		symbol->name = ast->type->id;
  133 	symbol->type = ast->type;
  134 	symbol->ast = ast;
  135 	symbol->offset = 0;
  136 #if 1
  137 	if (!strcmp(symbol->name, "symbol_table_dump"))
  138 		symbol_table_dump();
  139 	{
  140 		char *s = "type_dump_";
  141 		int len = strlen(s);
  142 		if (!strncmp(symbol->name, s, len)) {
  143 			struct Symbol *symbol3;
  144 			char *name = symbol->name + len;
  145 			symbol3 = symbol_lookup(name);
  146 			if (symbol3 != NULL && symbol3->type != NULL)
  147 				type_dump(symbol3->type);
  148 		}
  149 	}
  150 #endif
  151 	if (ast->ast_type == AST_statement_label) {
  152 		symbol->level = NL_LABEL;
  153 		symbol2 = symbol_lookup_label(symbol->name);
  154 		entry = &symbol_table.label;
  155 #if 0
  156 	} else if (ast->ast_type == AST_parameter_declaration) {
  157 		symbol->level = NL_ARG;
  158 		symbol2 = symbol_lookup_arg(symbol->name);
  159 		entry = &symbol_table.arg;
  160 #endif
  161 	} else if (AST_is_local) {
  162 		symbol->level = NL_LOCAL;
  163 		symbol2 = symbol_lookup_current_local(symbol->name);
  164 		entry = &symbol_table.local[symbol_table.local_index];
  165 	} else {
  166 		symbol->level = NL_GLOBAL;
  167 		symbol2 = symbol_lookup_global(symbol->name);
  168 		entry = &symbol_table.global;
  169 	}
  170 	if (symbol2 != NULL) {
  171 		fprintf(stderr, "redefinition of %s\n", symbol->name);
  172 		yyerror("");
  173 	}
  174 	symbol->next = *entry;
  175 	*entry = symbol;
  176 }
  177 
  178 static char *create_string_label(void) {
  179 	static int num = 0;
  180 	char *label = emalloc(32);
  181 
  182 	snprintf(label, 32, "LC%d", num++);
  183 	return label;
  184 }
  185 
  186 void string_entry(char *data) {
  187 	struct String *string = emalloc(sizeof(struct String));
  188 
  189 	string->data = data;
  190 	string->label = create_string_label();
  191 	string->next = symbol_table.string;
  192 	symbol_table.string = string;
  193 }
  194 
  195 void symbol_begin_function(void) {
  196 	AST_is_local = 1;
  197 	total_arg_size = 0;
  198 	total_local_size = 0;
  199 	memset(local_size, 0, sizeof(local_size));
  200 	set_offset(symbol_table.arg, 0);
  201 }
  202 
  203 void symbol_end_function(struct AST *ast) {
  204 	assert(ast->ast_type == AST_function_definition);
  205 	AST_is_local = 0;
  206 	ast->u2.func.arg = symbol_table.arg;
  207 	ast->u2.func.label = symbol_table.label;
  208 	ast->u2.func.string = symbol_table.string;
  209 	symbol_table.arg = NULL;
  210 	symbol_table.label = NULL;
  211 	symbol_table.string = NULL;
  212 	ast->u2.func.frame_size = ROUNDUP(total_arg_size + total_local_size, 8);
  213 }
  214 
  215 void symbol_begin_block(void) {
  216 	symbol_table.local_index++;
  217 	if (symbol_table.local_index >= MAX_BLOCK_DEPTH)
  218 		yyerror("MAX_BLOCK_DEPTH exceeded\n");
  219 	assert(symbol_table.local[symbol_table.local_index] == NULL);
  220 }
  221 
  222 void symbol_middle_block(void) {
  223 	int depth = symbol_table.local_index;
  224 
  225 	if (depth == 0)
  226 		local_size[depth] = set_offset(symbol_table.local[depth], 0);
  227 	else
  228 		local_size[depth] = set_offset(symbol_table.local[depth], local_size[depth - 1]);
  229 	if (local_size[depth] > total_local_size)
  230 		total_local_size = local_size[depth];
  231 }
  232 
  233 void symbol_end_block(struct AST *ast) {
  234 	assert(ast->ast_type == AST_compound_statement);
  235 	assert(symbol_table.local_index >= 0);
  236 	ast->u2.local = symbol_table.local[symbol_table.local_index];
  237 	symbol_table.local[symbol_table.local_index] = NULL;
  238 	symbol_table.local_index--;
  239 }
  240 
  241 void symbol_backpatch(struct AST *ast, struct Type *type) {
  242 	struct Symbol *symbol;
  243 
  244 	ast->type = type;
  245 	symbol = symbol_lookup_global(type->id);
  246 	assert(symbol != NULL);
  247 	symbol->ast = ast;
  248 }
  249 
  250 void symbol_entry_param(struct Type *func_type) {
  251 	int i;
  252 	int arg_num;
  253 	char **arg_name;
  254 	struct Type **arg_type;
  255 	struct Symbol *symbol;
  256 
  257 	assert(func_type->kind == TYPE_KIND_FUNCTION);
  258 	arg_num = func_type->u.t_function.arg_num;
  259 	arg_name = func_type->u.t_function.arg_name;
  260 	arg_type = func_type->u.t_function.arg_type;
  261 	for (i = 0; i < arg_num; i++) {
  262 		symbol = emalloc(sizeof(struct Symbol));
  263 		symbol->name = arg_name[i];
  264 		symbol->type = arg_type[i];
  265 		symbol->ast = NULL;
  266 		symbol->offset = 0;
  267 		symbol->level = NL_ARG;
  268 		symbol->next = symbol_table.arg;
  269 		symbol_table.arg = symbol;
  270 	}
  271 }
  272 
  273 struct Symbol *symbol_check_var_decl(struct AST *ast) {
  274 	char *id = ast->u.child[0]->u.id;
  275 	struct Symbol *symbol = symbol_lookup(id);
  276 
  277 	assert(ast->ast_type == AST_expression_id);
  278 	if (symbol == NULL) {
  279 		fprintf(stderr, "variable %s is used, but not declared\n", id);
  280 		yyerror("");
  281 	}
  282 	return symbol;
  283 }
  284 
  285 void symbol_table_dump(void) {
  286 	int i;
  287 
  288 	printf("global:   ");
  289 	symbol_dump(symbol_table.global);
  290 	printf("arg:      ");
  291 	symbol_dump(symbol_table.arg);
  292 	printf("label:    ");
  293 	symbol_dump(symbol_table.label);
  294 	printf("string:   ");
  295 	string_dump(symbol_table.string);
  296 	for (i = 0; i <= symbol_table.local_index; i++) {
  297 		printf("local[%d]: ", i);
  298 		symbol_dump(symbol_table.local[i]);
  299 	}
  300 }