/* SPIM S20 MIPS simulator. Code to maintain symbol table to resolve symbolic labels. Copyright (C) 1990 by James Larus (larus@cs.wisc.edu). SPIM is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 1, or (at your option) any later version. SPIM is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with GNU CC; see the file COPYING. If not, write to James R. Larus, Computer Sciences Department, University of Wisconsin--Madison, 1210 West Dayton Street, Madison, WI 53706, USA or to the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */ /* $Header: /home/aa/projects/spim/public_html/cvsroot/spimsal/sym_tbl.c,v 1.1.1.1 1999/08/21 19:31:25 brg Exp $ */ #include #include "spim.h" #include "inst.h" #include "mem.h" #include "sym_tbl.h" int data_dir; /* Local functions: */ static void get_hash (const char *name, int *slot_no, label **entry); static void resolve_label_uses (const label *sym); /* Keep track of the memory location that a label represents. If we see a reference to a label that is not yet defined, then record the reference so that we can patch up the instruction when the label is defined. At the end of a file, we flush the hash table of all non-global labels so they can't be seen in other files. */ static label *local_labels = NULL; /* Labels local to current file. */ #define HASHBITS 30 #define LABEL_HASH_TABLE_SIZE 8191 /* Map from name of a label to a label structure. */ static label *label_hash_table [LABEL_HASH_TABLE_SIZE]; /* Initialize the symbol table by removing and freeing old entries. */ void initialize_symbol_table (void) { register int i = LABEL_HASH_TABLE_SIZE; register label **l = label_hash_table; for ( ; i > 0; i--, l ++) { register label *x, *n; for (x = *l; x != NULL; x = n) { free (x->name); n = x->next; free (x); } *l = NULL; } local_labels = NULL; } /* Lookup for a label with the given NAME. Set the SLOT_NO to be the hash table bucket that contains (or would contain) the label's record. If the record is already in the table, set ENTRY to point to it. Otherwise, set ENTRY to be NULL. */ static void get_hash (const char *name, int *slot_no, label **entry) { register int hi; register int i; register label *lab; register int len; /* Compute length of name in len. */ for (len = 0; name[len]; len++); /* Compute hash code */ hi = len; for (i = 0; i < len; i++) hi = ((hi * 613) + (unsigned)(name[i])); hi &= (1 << HASHBITS) - 1; hi %= LABEL_HASH_TABLE_SIZE; *slot_no = hi; /* Search table for entry */ for (lab = label_hash_table [hi]; lab; lab = lab->next) if (streq (lab->name, name)) { *entry = lab; /* <-- return if found */ return; } *entry = NULL; } /* Return a label with a given NAME. If an label with that name has previously been looked-up, the same node is returned this time. */ label *lookup_label (char *name) { int hi; label *entry, *lab; get_hash (name, &hi, &entry); if (entry != NULL) return (entry); /* Not found, create one, add to chain */ lab = (label *) malloc (sizeof (label)); lab->name = (char *) strcpy ((char *)malloc (strlen (name) + 1), name); lab->addr = 0; lab->global_flag = 0; lab->gp_flag = 0; lab->uses = NULL; lab->type = UNKNOWN_A_TYPE; lab->next = label_hash_table [hi]; label_hash_table [hi] = lab; return lab; /* <-- return if created */ } /* Record that the label named NAME refers to ADDRESS. Return the label structure. */ label * record_label (char *name, mem_addr address) { label *l = lookup_label (name); free (name); if (!l->gp_flag) { if (l->addr != 0) { yyerror ("Label is defined for the second time"); return (l); } l->addr = address; } resolve_label_uses (l); l->uses = NULL; if (!l->global_flag) { l->next_local = local_labels; local_labels = l; } return (l); } label *set_label_type (label *l, unsigned char type) { l->type = type; return l; } int get_label_type (char *name) { label *l; if (0 == strcmp(name, "m")) return BYTE_A_TYPE; if (0 == strcmp(name, "M")) return WORD_A_TYPE; l = lookup_label (name); return l->type; } /* Make the label named NAME global. Return its symbol. */ label * make_label_global (char *name) { label *l = lookup_label (name); free (name); l->global_flag = 1; return (l); } /* Record that an INSTRUCTION uses the as-yet undefined SYMBOL. */ void record_inst_uses_symbol (instruction *inst, mem_addr pc, label *sym) { label_use *u = (label_use *) malloc (sizeof (label_use)); u->inst = inst; if (data_dir) { u->inst = (instruction *) malloc (sizeof (instruction)); bcopy (inst, u->inst, sizeof (inst)); EXPR (u->inst) = copy_imm_expr (EXPR (inst)); } u->addr = pc; u->next = sym->uses; sym->uses = u; } /* Record that a memory LOCATION uses the as-yet undefined SYMBOL. */ void record_data_uses_symbol (mem_addr location, label *sym) { label_use *u = (label_use *) malloc (sizeof (label_use)); u->inst = NULL; u->addr = location; u->next = sym->uses; sym->uses = u; } /* Given a newly-defined LABEL, resolve the previously encountered instructions and data locations that refer to the label. */ static void resolve_label_uses (const label *sym) { register label_use *uses = sym->uses; register label_use *next_use; for ( ; uses != NULL; uses = next_use) { resolve_a_label (sym, uses->inst, uses->addr); next_use = uses->next; free (uses); } } /* Resolve the use of a newly-defined label in INSTRUCTION. */ void resolve_a_label (const label *sym, instruction *inst, mem_addr pc) { if (inst == NULL) { /* Memory data: */ SET_MEM_WORD (pc, sym->addr); } else { /* Instruction: */ if (EXPR (inst)->pc_relative) EXPR (inst)->offset = -(pc+4); /* Instruction may have moved */ if (EXPR (inst)->symbol == NULL || SYMBOL_IS_DEFINED (EXPR (inst)->symbol)) { long value; int mask; if (opcode_is_branch (OPCODE (inst))) { short val; /* Drop low two bits since instructions are on word boundaries. */ val = eval_imm_expr (EXPR (inst)); val >>= 2; /* Seperate to force sign-extension */ if (bare_machine) /* Delayed branch */ { if (val < 0) val += 1; else val -= 1; } value = val; mask = 0xffff; } else if (opcode_is_jump (OPCODE (inst))) { /* Drop low two bits since instructions are on word boundaries. */ value = eval_imm_expr (EXPR (inst)); if ((value & 0xf0000000) != (pc & 0xf0000000)) { error ("Jump too long: "); print_inst (pc); } value = (value >> 2) & 0x03ffffff; mask = 0x03fffffff; } else if (opcode_is_load_store (OPCODE (inst))) { /* Label's location is an address */ value = eval_imm_expr (EXPR (inst)); mask = 0xffff; } else { /* Label's location is a value */ value = eval_imm_expr (EXPR (inst)); mask = 0xffff; } if ((value & ~mask) != 0 && (value & ~mask) != 0xffff0000) { error ("Immediate value is too large for field: "); print_inst (pc); } if (opcode_is_jump (OPCODE (inst))) TARGET (inst) = value; /* Don't mask so it is sign-extended */ else IMM (inst) = value; /* Ditto */ } else { sprintf(mess_buff, "Resolving undefined symbol: %s\n", (EXPR (inst)->symbol == NULL) ? "" : EXPR (inst)->symbol->name); error (mess_buff); } } } /* Remove all local (non-global) label from the table. */ void flush_local_labels (void) { register label *l; for (l = local_labels; l != NULL; l = l->next_local) { int hi; label *entry, *lab, *p; get_hash (l->name, &hi, &entry); for (lab = label_hash_table [hi], p = NULL; lab; p = lab, lab = lab->next) if (lab == entry) { if (p == NULL) label_hash_table [hi] = lab->next; else p->next = lab->next; if (entry->addr == 0) { sprintf(mess_buff, "Warning: local symbol was not defined: %s\n", entry->name); error (mess_buff); } /* Can't free label since IMM_EXPR's still reference it */ break; } } local_labels = NULL; } /* Return the address of SYMBOL or 0 if it is undefined. */ mem_addr find_symbol_address (char *symbol) { label *l = lookup_label (symbol); if (l == NULL || l->addr == 0) return 0; else return (l->addr); } /* Print all symbols in the table. */ void print_symbols (void) { register int i; register label *l; for (i = 0; i < LABEL_HASH_TABLE_SIZE; i ++) for (l = label_hash_table [i]; l != NULL; l = l->next) { sprintf(mess_buff, "%s%s at 0x%08x\n", l->global_flag ? "g " : " ", l->name, l->addr); write_output (message_out, mess_buff); } } void warn_undef(void) { register int hi; register label *lab; for (hi = 0; hi < LABEL_HASH_TABLE_SIZE; hi++) { for (lab = label_hash_table [hi]; lab; lab = lab->next) { if (lab->addr == 0) { sprintf(mess_buff, "Warning: symbol was not defined: %s\n", lab->name); error (mess_buff); } } } }