1 /*****************************************************************************/
5 /* Symbol table management for the cc65 C compiler */
9 /* (C) 2000-2013, Ullrich von Bassewitz */
10 /* Roemerstrasse 52 */
11 /* D-70794 Filderstadt */
12 /* EMail: uz@cc65.org */
15 /* This software is provided 'as-is', without any expressed or implied */
16 /* warranty. In no event will the authors be held liable for any damages */
17 /* arising from the use of this software. */
19 /* Permission is granted to anyone to use this software for any purpose, */
20 /* including commercial applications, and to alter it and redistribute it */
21 /* freely, subject to the following restrictions: */
23 /* 1. The origin of this software must not be misrepresented; you must not */
24 /* claim that you wrote the original software. If you use this software */
25 /* in a product, an acknowledgment in the product documentation would be */
26 /* appreciated but is not required. */
27 /* 2. Altered source versions must be plainly marked as such, and must not */
28 /* be misrepresented as being the original software. */
29 /* 3. This notice may not be removed or altered from any source */
32 /*****************************************************************************/
43 #include "debugflag.h"
63 /*****************************************************************************/
65 /*****************************************************************************/
69 /* An empty symbol table */
70 SymTable EmptySymTab = {
79 /* Symbol table sizes */
80 #define SYMTAB_SIZE_GLOBAL 211U
81 #define SYMTAB_SIZE_FUNCTION 29U
82 #define SYMTAB_SIZE_BLOCK 13U
83 #define SYMTAB_SIZE_STRUCT 19U
84 #define SYMTAB_SIZE_LABEL 7U
86 /* The current and root symbol tables */
87 static unsigned LexicalLevel = 0; /* For safety checks */
88 static SymTable* SymTab0 = 0;
89 static SymTable* SymTab = 0;
90 static SymTable* TagTab0 = 0;
91 static SymTable* TagTab = 0;
92 static SymTable* LabelTab = 0;
96 /*****************************************************************************/
98 /*****************************************************************************/
102 static SymTable* NewSymTable (unsigned Size)
103 /* Create and return a symbol table for the given lexical level */
107 /* Allocate memory for the table */
108 SymTable* S = xmalloc (sizeof (SymTable) + (Size-1) * sizeof (SymEntry*));
110 /* Initialize the symbol table structure */
116 for (I = 0; I < Size; ++I) {
120 /* Return the symbol table */
126 static void FreeSymTable (SymTable* S)
127 /* Free the given symbo table including all symbols */
129 /* Free all symbols */
130 SymEntry* Sym = S->SymHead;
132 SymEntry* NextSym = Sym->NextSym;
137 /* Free the table itself */
143 /*****************************************************************************/
144 /* Check symbols in a table */
145 /*****************************************************************************/
149 static void CheckSymTable (SymTable* Tab)
150 /* Check a symbol table for open references, unused symbols ... */
152 SymEntry* Entry = Tab->SymHead;
155 /* Get the storage flags for tne entry */
156 unsigned Flags = Entry->Flags;
158 /* Ignore typedef entries */
159 if (!SymIsTypeDef (Entry)) {
161 /* Check if the symbol is one with storage, and it if it was
162 ** defined but not used.
164 if (((Flags & SC_AUTO) || (Flags & SC_STATIC)) && (Flags & SC_EXTERN) == 0) {
165 if (SymIsDef (Entry) && !SymIsRef (Entry) &&
166 !SymHasAttr (Entry, atUnused)) {
167 if (Flags & SC_PARAM) {
168 if (IS_Get (&WarnUnusedParam)) {
169 Warning ("Parameter `%s' is never used", Entry->Name);
172 if (IS_Get (&WarnUnusedVar)) {
173 Warning ("`%s' is defined but never used", Entry->Name);
179 /* If the entry is a label, check if it was defined in the function */
180 if (Flags & SC_LABEL) {
181 if (!SymIsDef (Entry)) {
182 /* Undefined label */
183 Error ("Undefined label: `%s'", Entry->Name);
184 } else if (!SymIsRef (Entry)) {
185 /* Defined but not used */
186 if (IS_Get (&WarnUnusedLabel)) {
187 Warning ("`%s' is defined but never used", Entry->Name);
195 Entry = Entry->NextSym;
201 /*****************************************************************************/
202 /* Handling of lexical levels */
203 /*****************************************************************************/
207 unsigned GetLexicalLevel (void)
208 /* Return the current lexical level */
215 void EnterGlobalLevel (void)
216 /* Enter the program global lexical level */
219 PRECONDITION (++LexicalLevel == LEX_LEVEL_GLOBAL);
221 /* Create and assign the symbol table */
222 SymTab0 = SymTab = NewSymTable (SYMTAB_SIZE_GLOBAL);
224 /* Create and assign the tag table */
225 TagTab0 = TagTab = NewSymTable (SYMTAB_SIZE_GLOBAL);
230 void LeaveGlobalLevel (void)
231 /* Leave the program global lexical level */
234 PRECONDITION (LexicalLevel-- == LEX_LEVEL_GLOBAL);
236 /* Check the tables */
237 CheckSymTable (SymTab0);
239 /* Dump the tables if requested */
241 PrintSymTable (SymTab0, stdout, "Global symbol table");
242 PrintSymTable (TagTab0, stdout, "Global tag table");
245 /* Don't delete the symbol and struct tables! */
252 void EnterFunctionLevel (void)
253 /* Enter function lexical level */
257 /* New lexical level */
260 /* Get a new symbol table and make it current */
261 S = NewSymTable (SYMTAB_SIZE_FUNCTION);
265 /* Get a new tag table and make it current */
266 S = NewSymTable (SYMTAB_SIZE_FUNCTION);
270 /* Create and assign a new label table */
271 S = NewSymTable (SYMTAB_SIZE_LABEL);
272 S->PrevTab = LabelTab;
278 void RememberFunctionLevel (struct FuncDesc* F)
279 /* Remember the symbol tables for the level and leave the level without checks */
281 /* Leave the lexical level */
284 /* Remember the tables */
288 /* Don't delete the tables */
289 SymTab = SymTab->PrevTab;
290 TagTab = TagTab->PrevTab;
291 LabelTab = LabelTab->PrevTab;
296 void ReenterFunctionLevel (struct FuncDesc* F)
297 /* Reenter the function lexical level using the existing tables from F */
299 /* New lexical level */
302 /* Make the tables current again */
303 F->SymTab->PrevTab = SymTab;
306 F->TagTab->PrevTab = TagTab;
309 /* Create and assign a new label table */
310 LabelTab = NewSymTable (SYMTAB_SIZE_LABEL);
315 void LeaveFunctionLevel (void)
316 /* Leave function lexical level */
318 /* Leave the lexical level */
321 /* Check the tables */
322 CheckSymTable (SymTab);
323 CheckSymTable (LabelTab);
325 /* Drop the label table if it is empty */
326 if (LabelTab->SymCount == 0) {
327 FreeSymTable (LabelTab);
330 /* Don't delete the tables */
331 SymTab = SymTab->PrevTab;
332 TagTab = TagTab->PrevTab;
338 void EnterBlockLevel (void)
339 /* Enter a nested block in a function */
343 /* New lexical level */
346 /* Get a new symbol table and make it current */
347 S = NewSymTable (SYMTAB_SIZE_BLOCK);
351 /* Get a new tag table and make it current */
352 S = NewSymTable (SYMTAB_SIZE_BLOCK);
359 void LeaveBlockLevel (void)
360 /* Leave a nested block in a function */
362 /* Leave the lexical level */
365 /* Check the tables */
366 CheckSymTable (SymTab);
368 /* Don't delete the tables */
369 SymTab = SymTab->PrevTab;
370 TagTab = TagTab->PrevTab;
375 void EnterStructLevel (void)
376 /* Enter a nested block for a struct definition */
380 /* Get a new symbol table and make it current. Note: Structs and enums
381 ** nested in struct scope are NOT local to the struct but visible in the
382 ** outside scope. So we will NOT create a new struct or enum table.
384 S = NewSymTable (SYMTAB_SIZE_BLOCK);
391 void LeaveStructLevel (void)
392 /* Leave a nested block for a struct definition */
394 /* Don't delete the table */
395 SymTab = SymTab->PrevTab;
400 /*****************************************************************************/
402 /*****************************************************************************/
406 static SymEntry* FindSymInTable (const SymTable* T, const char* Name, unsigned Hash)
407 /* Search for an entry in one table */
409 /* Get the start of the hash chain */
410 SymEntry* E = T->Tab [Hash % T->Size];
412 /* Compare the name */
413 if (strcmp (E->Name, Name) == 0) {
417 /* Not found, next entry in hash chain */
427 static SymEntry* FindSymInTree (const SymTable* Tab, const char* Name)
428 /* Find the symbol with the given name in the table tree that starts with T */
430 /* Get the hash over the name */
431 unsigned Hash = HashStr (Name);
433 /* Check all symbol tables for the symbol */
435 /* Try to find the symbol in this table */
436 SymEntry* E = FindSymInTable (Tab, Name, Hash);
438 /* Bail out if we found it */
443 /* Repeat the search in the next higher lexical level */
453 SymEntry* FindSym (const char* Name)
454 /* Find the symbol with the given name */
456 return FindSymInTree (SymTab, Name);
461 SymEntry* FindGlobalSym (const char* Name)
462 /* Find the symbol with the given name in the global symbol table only */
464 return FindSymInTable (SymTab0, Name, HashStr (Name));
469 SymEntry* FindLocalSym (const char* Name)
470 /* Find the symbol with the given name in the current symbol table only */
472 return FindSymInTable (SymTab, Name, HashStr (Name));
477 SymEntry* FindTagSym (const char* Name)
478 /* Find the symbol with the given name in the tag table */
480 return FindSymInTree (TagTab, Name);
485 SymEntry* FindStructField (const Type* T, const char* Name)
486 /* Find a struct field in the fields list */
490 /* The given type may actually be a pointer to struct */
495 /* Non-structs do not have any struct fields... */
496 if (IsClassStruct (T)) {
498 /* Get a pointer to the struct/union type */
499 const SymEntry* Struct = GetSymEntry (T);
502 /* Now search in the struct symbol table. Beware: The table may not
505 if (Struct->V.S.SymTab) {
506 Field = FindSymInTable (Struct->V.S.SymTab, Name, HashStr (Name));
515 /*****************************************************************************/
516 /* Add stuff to the symbol table */
517 /*****************************************************************************/
521 static void AddSymEntry (SymTable* T, SymEntry* S)
522 /* Add a symbol to a symbol table */
524 /* Get the hash value for the name */
525 unsigned Hash = HashStr (S->Name) % T->Size;
527 /* Insert the symbol into the list of all symbols in this level */
529 T->SymTail->NextSym = S;
531 S->PrevSym = T->SymTail;
533 if (T->SymHead == 0) {
539 /* Insert the symbol into the hash chain */
540 S->NextHash = T->Tab[Hash];
543 /* Tell the symbol in which table it is */
549 SymEntry* AddStructSym (const char* Name, unsigned Type, unsigned Size, SymTable* Tab)
550 /* Add a struct/union entry and return it */
554 /* Type must be struct or union */
555 PRECONDITION (Type == SC_STRUCT || Type == SC_UNION);
557 /* Do we have an entry with this name already? */
558 Entry = FindSymInTable (TagTab, Name, HashStr (Name));
561 /* We do have an entry. This may be a forward, so check it. */
562 if ((Entry->Flags & SC_TYPEMASK) != Type) {
563 /* Existing symbol is not a struct */
564 Error ("Symbol `%s' is already different kind", Name);
565 } else if (Size > 0 && Entry->V.S.Size > 0) {
566 /* Both structs are definitions. */
567 Error ("Multiple definition for `%s'", Name);
569 /* Define the struct size if it is given */
571 Entry->V.S.SymTab = Tab;
572 Entry->V.S.Size = Size;
578 /* Create a new entry */
579 Entry = NewSymEntry (Name, Type);
581 /* Set the struct data */
582 Entry->V.S.SymTab = Tab;
583 Entry->V.S.Size = Size;
585 /* Add it to the current table */
586 AddSymEntry (TagTab, Entry);
589 /* Return the entry */
595 SymEntry* AddBitField (const char* Name, unsigned Offs, unsigned BitOffs, unsigned Width)
596 /* Add a bit field to the local symbol table and return the symbol entry */
598 /* Do we have an entry with this name already? */
599 SymEntry* Entry = FindSymInTable (SymTab, Name, HashStr (Name));
602 /* We have a symbol with this name already */
603 Error ("Multiple definition for `%s'", Name);
607 /* Create a new entry */
608 Entry = NewSymEntry (Name, SC_BITFIELD);
610 /* Set the symbol attributes. Bit-fields are always of type unsigned */
611 Entry->Type = type_uint;
612 Entry->V.B.Offs = Offs;
613 Entry->V.B.BitOffs = BitOffs;
614 Entry->V.B.BitWidth = Width;
616 /* Add the entry to the symbol table */
617 AddSymEntry (SymTab, Entry);
621 /* Return the entry */
627 SymEntry* AddConstSym (const char* Name, const Type* T, unsigned Flags, long Val)
628 /* Add an constant symbol to the symbol table and return it */
630 /* Enums must be inserted in the global symbol table */
631 SymTable* Tab = ((Flags & SC_ENUM) == SC_ENUM)? SymTab0 : SymTab;
633 /* Do we have an entry with this name already? */
634 SymEntry* Entry = FindSymInTable (Tab, Name, HashStr (Name));
636 if ((Entry->Flags & SC_CONST) != SC_CONST) {
637 Error ("Symbol `%s' is already different kind", Name);
639 Error ("Multiple definition for `%s'", Name);
644 /* Create a new entry */
645 Entry = NewSymEntry (Name, Flags);
647 /* Enum values are ints */
648 Entry->Type = TypeDup (T);
650 /* Set the enum data */
651 Entry->V.ConstVal = Val;
653 /* Add the entry to the symbol table */
654 AddSymEntry (Tab, Entry);
656 /* Return the entry */
662 SymEntry* AddLabelSym (const char* Name, unsigned Flags)
663 /* Add a goto label to the label table */
665 /* Do we have an entry with this name already? */
666 SymEntry* Entry = FindSymInTable (LabelTab, Name, HashStr (Name));
669 if (SymIsDef (Entry) && (Flags & SC_DEF) != 0) {
670 /* Trying to define the label more than once */
671 Error ("Label `%s' is defined more than once", Name);
673 Entry->Flags |= Flags;
677 /* Create a new entry */
678 Entry = NewSymEntry (Name, SC_LABEL | Flags);
680 /* Set a new label number */
681 Entry->V.Label = GetLocalLabel ();
683 /* Generate the assembler name of the label */
684 Entry->AsmName = xstrdup (LocalLabelName (Entry->V.Label));
686 /* Add the entry to the label table */
687 AddSymEntry (LabelTab, Entry);
691 /* Return the entry */
697 SymEntry* AddLocalSym (const char* Name, const Type* T, unsigned Flags, int Offs)
698 /* Add a local symbol and return the symbol entry */
700 /* Do we have an entry with this name already? */
701 SymEntry* Entry = FindSymInTable (SymTab, Name, HashStr (Name));
704 /* We have a symbol with this name already */
705 Error ("Multiple definition for `%s'", Name);
709 /* Create a new entry */
710 Entry = NewSymEntry (Name, Flags);
712 /* Set the symbol attributes */
713 Entry->Type = TypeDup (T);
714 if ((Flags & SC_AUTO) == SC_AUTO) {
715 Entry->V.Offs = Offs;
716 } else if ((Flags & SC_REGISTER) == SC_REGISTER) {
717 Entry->V.R.RegOffs = Offs;
718 Entry->V.R.SaveOffs = StackPtr;
719 } else if ((Flags & SC_EXTERN) == SC_EXTERN) {
720 Entry->V.Label = Offs;
721 SymSetAsmName (Entry);
722 } else if ((Flags & SC_STATIC) == SC_STATIC) {
723 /* Generate the assembler name from the label number */
724 Entry->V.Label = Offs;
725 Entry->AsmName = xstrdup (LocalLabelName (Entry->V.Label));
726 } else if ((Flags & SC_STRUCTFIELD) == SC_STRUCTFIELD) {
727 Entry->V.Offs = Offs;
729 Internal ("Invalid flags in AddLocalSym: %04X", Flags);
732 /* Add the entry to the symbol table */
733 AddSymEntry (SymTab, Entry);
737 /* Return the entry */
743 SymEntry* AddGlobalSym (const char* Name, const Type* T, unsigned Flags)
744 /* Add an external or global symbol to the symbol table and return the entry */
746 /* There is some special handling for functions, so check if it is one */
747 int IsFunc = IsTypeFunc (T);
749 /* Functions must be inserted in the global symbol table */
750 SymTable* Tab = IsFunc? SymTab0 : SymTab;
752 /* Do we have an entry with this name already? */
753 SymEntry* Entry = FindSymInTable (Tab, Name, HashStr (Name));
758 /* We have a symbol with this name already */
759 if (Entry->Flags & SC_TYPE) {
760 Error ("Multiple definition for `%s'", Name);
764 /* Get the type string of the existing symbol */
767 /* If we are handling arrays, the old entry or the new entry may be an
768 ** incomplete declaration. Accept this, and if the exsting entry is
769 ** incomplete, complete it.
771 if (IsTypeArray (T) && IsTypeArray (EType)) {
773 /* Get the array sizes */
774 long Size = GetElementCount (T);
775 long ESize = GetElementCount (EType);
777 if ((Size != UNSPECIFIED && ESize != UNSPECIFIED && Size != ESize) ||
778 TypeCmp (T + 1, EType + 1) < TC_EQUAL) {
779 /* Types not identical: Conflicting types */
780 Error ("Conflicting types for `%s'", Name);
783 /* Check if we have a size in the existing definition */
784 if (ESize == UNSPECIFIED) {
785 /* Existing, size not given, use size from new def */
786 SetElementCount (EType, Size);
791 /* New type must be identical */
792 if (TypeCmp (EType, T) < TC_EQUAL) {
793 Error ("Conflicting types for `%s'", Name);
797 /* In case of a function, use the new type descriptor, since it
798 ** contains pointers to the new symbol tables that are needed if
799 ** an actual function definition follows. Be sure not to use the
800 ** new descriptor if it contains a function declaration with an
801 ** empty parameter list.
804 /* Get the function descriptor from the new type */
805 FuncDesc* F = GetFuncDesc (T);
806 /* Use this new function descriptor if it doesn't contain
807 ** an empty parameter list.
809 if ((F->Flags & FD_EMPTY) == 0) {
811 SetFuncDesc (EType, F);
816 /* If a static declaration follows a non-static declaration, then
817 ** warn about the conflict. (It will compile a public declaration.)
819 if ((Flags & SC_EXTERN) == 0 && (Entry->Flags & SC_EXTERN) != 0) {
820 Warning ("static declaration follows non-static declaration of `%s'.", Name);
823 /* An extern declaration must not change the current linkage. */
824 if (IsFunc || (Flags & (SC_EXTERN | SC_STORAGE)) == SC_EXTERN) {
828 /* If a public declaration follows a static declaration, then
829 ** warn about the conflict. (It will compile a public declaration.)
831 if ((Flags & SC_EXTERN) != 0 && (Entry->Flags & SC_EXTERN) == 0) {
832 Warning ("public declaration follows static declaration of `%s'.", Name);
835 /* Add the new flags */
836 Entry->Flags |= Flags;
840 /* Create a new entry */
841 Entry = NewSymEntry (Name, Flags);
843 /* Set the symbol attributes */
844 Entry->Type = TypeDup (T);
846 /* If this is a function, set the function descriptor and clear
847 ** additional fields.
850 Entry->V.F.Func = GetFuncDesc (Entry->Type);
854 /* Add the assembler name of the symbol */
855 SymSetAsmName (Entry);
857 /* Add the entry to the symbol table */
858 AddSymEntry (Tab, Entry);
861 /* Return the entry */
867 /*****************************************************************************/
869 /*****************************************************************************/
873 SymTable* GetSymTab (void)
874 /* Return the current symbol table */
881 SymTable* GetGlobalSymTab (void)
882 /* Return the global symbol table */
889 int SymIsLocal (SymEntry* Sym)
890 /* Return true if the symbol is defined in the highest lexical level */
892 return (Sym->Owner == SymTab || Sym->Owner == TagTab);
897 void MakeZPSym (const char* Name)
898 /* Mark the given symbol as zero page symbol */
900 /* Get the symbol table entry */
901 SymEntry* Entry = FindSymInTable (SymTab, Name, HashStr (Name));
903 /* Mark the symbol as zeropage */
905 Entry->Flags |= SC_ZEROPAGE;
907 Error ("Undefined symbol: `%s'", Name);
913 void PrintSymTable (const SymTable* Tab, FILE* F, const char* Header, ...)
914 /* Write the symbol table to the given file */
917 const SymEntry* Entry;
919 /* Print the header */
921 va_start (ap, Header);
923 Len = vfprintf (F, Header, ap);
927 /* Underline the header */
934 Entry = Tab->SymHead;
936 fprintf (F, "(empty)\n");
939 DumpSymEntry (F, Entry);
940 Entry = Entry->NextSym;
943 fprintf (F, "\n\n\n");
948 void EmitExternals (void)
949 /* Write import/export statements for external symbols */
953 Entry = SymTab->SymHead;
955 unsigned Flags = Entry->Flags;
956 if (Flags & SC_EXTERN) {
957 /* Only defined or referenced externs */
958 if (SymIsRef (Entry) && !SymIsDef (Entry)) {
960 g_defimport (Entry->Name, Flags & SC_ZEROPAGE);
961 } else if (SymIsDef (Entry)) {
963 g_defexport (Entry->Name, Flags & SC_ZEROPAGE);
966 Entry = Entry->NextSym;
972 void EmitDebugInfo (void)
973 /* Emit debug infos for the locals of the current scope */
978 /* Output info for locals if enabled */
980 /* For cosmetic reasons in the output file, we will insert two tabs
981 ** on global level and just one on local level.
983 if (LexicalLevel == LEX_LEVEL_GLOBAL) {
984 Head = "\t.dbg\t\tsym";
986 Head = "\t.dbg\tsym";
988 Sym = SymTab->SymHead;
990 if ((Sym->Flags & (SC_CONST|SC_TYPE)) == 0) {
991 if (Sym->Flags & SC_AUTO) {
992 AddTextLine ("%s, \"%s\", \"00\", auto, %d",
993 Head, Sym->Name, Sym->V.Offs);
994 } else if (Sym->Flags & SC_REGISTER) {
995 AddTextLine ("%s, \"%s\", \"00\", register, \"regbank\", %d",
996 Head, Sym->Name, Sym->V.R.RegOffs);
998 } else if (SymIsRef (Sym) && !SymIsDef (Sym)) {
999 AddTextLine ("%s, \"%s\", \"00\", %s, \"%s\"",
1001 (Sym->Flags & SC_EXTERN)? "extern" : "static",