home *** CD-ROM | disk | FTP | other *** search
/ Mac Mania 2 / MacMania 2.toast / Demo's / Tools&Utilities / Programming / SPIM Folder / Sources / sym_tbl.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-04-30  |  9.1 KB  |  399 lines  |  [TEXT/ttxt]
  1. /* SPIM S20 MIPS simulator.
  2.    Code to maintain symbol table to resolve symbolic labels.
  3.    Copyright (C) 1990 by James Larus (larus@cs.wisc.edu).
  4.  
  5.    SPIM is free software; you can redistribute it and/or modify it
  6.    under the terms of the GNU General Public License as published by the
  7.    Free Software Foundation; either version 1, or (at your option) any
  8.    later version.
  9.  
  10.    SPIM is distributed in the hope that it will be useful, but WITHOUT
  11.    ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  12.    FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  13.    for more details.
  14.  
  15.    You should have received a copy of the GNU General Public License
  16.    along with GNU CC; see the file COPYING.  If not, write to James R.
  17.    Larus, Computer Sciences Department, University of Wisconsin--Madison,
  18.    1210 West Dayton Street, Madison, WI 53706, USA or to the Free
  19.    Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */
  20.  
  21.  
  22. /* $Header: /var/home/cs354/.spim/RCS/sym_tbl.c,v 1.4 1992/10/12 11:34:44 cs354 Exp $
  23. */
  24.  
  25.  
  26. #include <stdio.h>
  27. #include "spim.h"
  28. #include "inst.h"
  29. #include "mem.h"
  30. #include "sym_tbl.h"
  31.  
  32.  
  33. extern int data_dir;
  34.  
  35. /* Local functions: */
  36.  
  37. static void get_hash (const char *name, int *slot_no, label **entry);
  38. static void resolve_label_uses (const label *sym);
  39.  
  40.  
  41. /* Keep track of the memory location that a label represents.  If we
  42.    see a reference to a label that is not yet defined, then record the
  43.    reference so that we can patch up the instruction when the label is
  44.    defined.
  45.  
  46.    At the end of a file, we flush the hash table of all non-global
  47.    labels so they can't be seen in other files.     */
  48.  
  49.  
  50. static label *local_labels = NULL; /* Labels local to current file. */
  51.  
  52.  
  53. #define HASHBITS 30
  54.  
  55. #ifdef MACINTOSH
  56. #define LABEL_HASH_TABLE_SIZE 4001
  57. #else
  58. #define LABEL_HASH_TABLE_SIZE 8191
  59. #endif
  60.  
  61. /* Map from name of a label to a label structure. */
  62.  
  63. static label *label_hash_table [LABEL_HASH_TABLE_SIZE];
  64.  
  65.  
  66. /* Initialize the symbol table by removing and freeing old entries. */
  67.  
  68. void initialize_symbol_table (void)
  69. {
  70.   register int i = LABEL_HASH_TABLE_SIZE;
  71.   register label **l = label_hash_table;
  72.  
  73.   for ( ; i > 0; i--, l ++)
  74.     {
  75.       register label *x, *n;
  76.  
  77.       for (x = *l; x != NULL; x = n)
  78.     {
  79.       free (x->name);
  80.       n = x->next;
  81.       free (x);
  82.     }
  83.       *l = NULL;
  84.     }
  85.   local_labels = NULL;
  86. }
  87.  
  88.  
  89.  
  90. /* Lookup for a label with the given NAME.  Set the SLOT_NO to be the hash
  91.    table bucket that contains (or would contain) the label's record.  If the
  92.    record is already in the table, set ENTRY to point to it.  Otherwise,
  93.    set ENTRY to be NULL. */
  94.  
  95. static void get_hash (const char *name, int *slot_no, label **entry)
  96. {
  97.   register int hi;
  98.   register int i;
  99.   register label *lab;
  100.   register int len;
  101.  
  102.   /* Compute length of name in len.  */
  103.   for (len = 0; name[len]; len++);
  104.  
  105.   /* Compute hash code */
  106.   hi = len;
  107.   for (i = 0; i < len; i++)
  108.     hi = ((hi * 613) + (unsigned)(name[i]));
  109.  
  110.   hi &= (1 << HASHBITS) - 1;
  111.   hi %= LABEL_HASH_TABLE_SIZE;
  112.  
  113.   *slot_no = hi;
  114.   /* Search table for entry */
  115.   for (lab = label_hash_table [hi]; lab; lab = lab->next)
  116.     if (streq (lab->name, name))
  117.       {
  118.     *entry = lab;        /* <-- return if found */
  119.     return;
  120.       }
  121.   *entry = NULL;
  122. }
  123.  
  124.  
  125. /* Return a label with a given NAME.  If an label with that name has
  126.    previously been looked-up, the same node is returned this time.  */
  127.  
  128. label *lookup_label (char *name)
  129. {
  130.   int hi;
  131.   label *entry, *lab;
  132.  
  133.   get_hash (name, &hi, &entry);
  134.  
  135.   if (entry != NULL)
  136.     return (entry);
  137.  
  138.   /* Not found, create one, add to chain */
  139.   lab = (label *) malloc (sizeof (label));
  140.   if ( !lab ) {
  141.   }
  142.  
  143.   lab->name = (char *) strcpy (malloc (strlen (name) + 1), name);
  144.   lab->addr = 0;
  145.   lab->global_flag = 0;
  146.   lab->gp_flag = 0;
  147.   lab->uses = NULL;
  148.   lab->type = UNKNOWN_A_TYPE;
  149.  
  150.   lab->next = label_hash_table [hi];
  151.   label_hash_table [hi] = lab;
  152.   return lab;            /* <-- return if created */
  153. }
  154.  
  155.  
  156. /* Record that the label named NAME refers to ADDRESS.    Return the label
  157.    structure. */
  158.  
  159. label * record_label (char *name, mem_addr address)
  160. {
  161.   label *l = lookup_label (name);
  162.  
  163.   free (name);
  164.   if (!l->gp_flag)
  165.     {
  166.       if (l->addr != 0)
  167.     {
  168.       yyerror ("Label is defined for the second time");
  169.       return (l);
  170.     }
  171.       l->addr = address;
  172.     }
  173.   resolve_label_uses (l);
  174.   l->uses = NULL;
  175.   if (!l->global_flag)
  176.     {
  177.       l->next_local = local_labels;
  178.       local_labels = l;
  179.     }
  180.   return (l);
  181. }
  182.  
  183. label *set_label_type (label *l, unsigned char type)
  184. {
  185.   l->type = type;
  186.   return l;
  187. }
  188.  
  189. int get_label_type (char *name)
  190. {
  191.   label *l;
  192.   if (0 == strcmp(name, "m")) return BYTE_A_TYPE;
  193.   if (0 == strcmp(name, "M")) return WORD_A_TYPE;
  194.   l = lookup_label (name);
  195.   return l->type;
  196. }
  197.  
  198.  
  199. /* Make the label named NAME global.  Return its symbol. */
  200.  
  201. label * make_label_global (char *name)
  202. {
  203.   label *l = lookup_label (name);
  204.  
  205.   free (name);
  206.   l->global_flag = 1;
  207.   return (l);
  208. }
  209.  
  210.  
  211. /* Record that an INSTRUCTION uses the as-yet undefined SYMBOL. */
  212.  
  213. void record_inst_uses_symbol (instruction *inst, mem_addr pc, label *sym)
  214. {
  215.   label_use *u = (label_use *) malloc (sizeof (label_use));
  216.  
  217.   u->inst = inst;
  218.   if (data_dir) {
  219.       u->inst = (instruction *) malloc (sizeof (inst));
  220.       bcopy (inst, u->inst, sizeof (inst));
  221.       EXPR (u->inst) = copy_imm_expr (EXPR (inst));
  222.   }
  223.   u->addr = pc;
  224.   u->next = sym->uses;
  225.   sym->uses = u;
  226. }
  227.  
  228.  
  229. /* Record that a memory LOCATION uses the as-yet undefined SYMBOL. */
  230.  
  231. void record_data_uses_symbol (mem_addr location, label *sym)
  232. {
  233.   label_use *u = (label_use *) malloc (sizeof (label_use));
  234.  
  235.   u->inst = NULL;
  236.   u->addr = location;
  237.   u->next = sym->uses;
  238.   sym->uses = u;
  239. }
  240.  
  241.  
  242. /* Given a newly-defined LABEL, resolve the previously encountered
  243.    instructions and data locations that refer to the label. */
  244.  
  245. static void resolve_label_uses (const label *sym)
  246. {
  247.   register label_use *uses = sym->uses;
  248.   register label_use *next_use;
  249.  
  250.   for ( ; uses != NULL; uses = next_use)
  251.     {
  252.       resolve_a_label (sym, uses->inst, uses->addr);
  253.       next_use = uses->next;
  254.       free (uses);
  255.     }
  256. }
  257.  
  258.  
  259. /* Resolve the use of a newly-defined label in INSTRUCTION. */
  260.  
  261. void resolve_a_label (const label *sym, instruction *inst, mem_addr pc)
  262. {
  263.   if (inst == NULL)
  264.     {
  265.       /* Memory data: */
  266.       SET_MEM_WORD (pc, sym->addr);
  267.     }
  268.   else
  269.     {
  270.       /* Instruction: */
  271.       if (EXPR (inst)->pc_relative)
  272.     EXPR (inst)->offset = -(pc+4); /* Instruction may have moved */
  273.  
  274.       if (EXPR (inst)->symbol == NULL
  275.       || SYMBOL_IS_DEFINED (EXPR (inst)->symbol))
  276.     {
  277.       long value;
  278.       int mask;
  279.  
  280.       if (opcode_is_branch (OPCODE (inst)))
  281.         {
  282.           short val;
  283.  
  284.           /* Drop low two bits since instructions are on word
  285.          boundaries. */
  286.           val = eval_imm_expr (EXPR (inst));
  287.           val >>= 2;    /* Seperate to force sign-extension */
  288.           if (bare_machine)    /* Delayed branch */
  289.         {
  290.           if (val < 0)
  291.             val += 1;
  292.           else
  293.             val -= 1;
  294.         }
  295.           value = val;
  296.           mask = 0xffff;
  297.         }
  298.       else if (opcode_is_jump (OPCODE (inst)))
  299.         {
  300.           /* Drop low two bits since instructions are on word
  301.          boundaries. */
  302.           value = eval_imm_expr (EXPR (inst)) >> 2;
  303.           mask = 0x03fffffff;
  304.         }
  305.       else if (opcode_is_load_store (OPCODE (inst)))
  306.         {
  307.           /* Label's location is an address */
  308.           value = eval_imm_expr (EXPR (inst));
  309.           mask = 0xffff;
  310.         }
  311.       else
  312.         {
  313.           /* Label's location is a value */
  314.           value = eval_imm_expr (EXPR (inst));
  315.           mask = 0xffff;
  316.         }
  317.  
  318.       if ((value & ~mask) != 0 && (value & ~mask) != 0xffff0000)
  319.         {
  320.           error ("Immediate value is too large for field: ");
  321.           print_inst (pc);
  322.         }
  323.       if (opcode_is_jump (OPCODE (inst)))
  324.         TARGET (inst) = value; /* Don't mask so it is sign-extended */
  325.       else
  326.         IMM (inst) = value;    /* Ditto */
  327.     }
  328.       else {
  329.     sprintf(mess_buff, "Resolving undefined symbol: %s\n",
  330.           (EXPR (inst)->symbol == NULL) ? "" : EXPR (inst)->symbol->name);
  331.     error (mess_buff);
  332.       }
  333.     }
  334. }
  335.  
  336.  
  337. /* Remove all local (non-global) label from the table. */
  338.  
  339. void flush_local_labels (void)
  340. {
  341.   register label *l;
  342.  
  343.   for (l = local_labels; l != NULL; l = l->next_local)
  344.     {
  345.       int hi;
  346.       label *entry, *lab, *p;
  347.  
  348.       get_hash (l->name, &hi, &entry);
  349.  
  350.       for (lab = label_hash_table [hi], p = NULL;
  351.        lab;
  352.        p = lab, lab = lab->next)
  353.     if (lab == entry)
  354.       {
  355.         if (p == NULL)
  356.           label_hash_table [hi] = lab->next;
  357.         else
  358.           p->next = lab->next;
  359.         if (entry->addr == 0) {
  360.           sprintf(mess_buff,
  361.                 "Warning: local symbol %s was not defined\n", entry->name);
  362.           error (mess_buff);
  363.         }
  364.         /* Can't free label since IMM_EXPR's still reference it */
  365.         break;
  366.       }
  367.     }
  368.   local_labels = NULL;
  369. }
  370.  
  371.  
  372. /* Return the address of SYMBOL or 0 if it is undefined. */
  373.  
  374. mem_addr find_symbol_address (char *symbol)
  375. {
  376.   label *l = lookup_label (symbol);
  377.  
  378.   if (l == NULL || l->addr == 0)
  379.     return 0;
  380.   else
  381.     return (l->addr);
  382. }
  383.  
  384.  
  385. /* Print all symbols in the table. */
  386.  
  387. void print_symbols (void)
  388. {
  389.   register int i;
  390.   register label *l;
  391.  
  392.   for (i = 0; i < LABEL_HASH_TABLE_SIZE; i ++)
  393.     for (l = label_hash_table [i]; l != NULL; l = l->next) {
  394.       sprintf(mess_buff, "%s%s at 0x%08x\n",
  395.         l->global_flag ? "g " : "     ", l->name, l->addr);
  396.       write_output (message_out, mess_buff);
  397.     }
  398. }
  399.