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"
65 /*****************************************************************************/
67 /*****************************************************************************/
71 /* An empty symbol table */
72 SymTable EmptySymTab = {
81 /* Symbol table sizes */
82 #define SYMTAB_SIZE_GLOBAL 211U
83 #define SYMTAB_SIZE_FUNCTION 29U
84 #define SYMTAB_SIZE_BLOCK 13U
85 #define SYMTAB_SIZE_STRUCT 19U
86 #define SYMTAB_SIZE_LABEL 7U
88 /* The current and root symbol tables */
89 static unsigned LexicalLevel = 0; /* For safety checks */
90 static SymTable* SymTab0 = 0;
91 static SymTable* SymTab = 0;
92 static SymTable* TagTab0 = 0;
93 static SymTable* TagTab = 0;
94 static SymTable* LabelTab = 0;
98 /*****************************************************************************/
100 /*****************************************************************************/
104 static SymTable* NewSymTable (unsigned Size)
105 /* Create and return a symbol table for the given lexical level */
109 /* Allocate memory for the table */
110 SymTable* S = xmalloc (sizeof (SymTable) + (Size-1) * sizeof (SymEntry*));
112 /* Initialize the symbol table structure */
118 for (I = 0; I < Size; ++I) {
122 /* Return the symbol table */
128 static void FreeSymTable (SymTable* S)
129 /* Free the given symbo table including all symbols */
131 /* Free all symbols */
132 SymEntry* Sym = S->SymHead;
134 SymEntry* NextSym = Sym->NextSym;
139 /* Free the table itself */
145 /*****************************************************************************/
146 /* Check symbols in a table */
147 /*****************************************************************************/
151 static void CheckSymTable (SymTable* Tab)
152 /* Check a symbol table for open references, unused symbols ... */
154 SymEntry* Entry = Tab->SymHead;
157 /* Get the storage flags for tne entry */
158 unsigned Flags = Entry->Flags;
160 /* Ignore typedef entries */
161 if (!SymIsTypeDef (Entry)) {
163 /* Check if the symbol is one with storage, and it if it was
164 ** defined but not used.
166 if (((Flags & SC_AUTO) || (Flags & SC_STATIC)) && (Flags & SC_EXTERN) == 0) {
167 if (SymIsDef (Entry) && !SymIsRef (Entry) &&
168 !SymHasAttr (Entry, atUnused)) {
169 if (Flags & SC_PARAM) {
170 if (IS_Get (&WarnUnusedParam)) {
171 Warning ("Parameter `%s' is never used", Entry->Name);
174 if (IS_Get (&WarnUnusedVar)) {
175 Warning ("`%s' is defined but never used", Entry->Name);
181 /* If the entry is a label, check if it was defined in the function */
182 if (Flags & SC_LABEL) {
183 if (!SymIsDef (Entry)) {
184 /* Undefined label */
185 Error ("Undefined label: `%s'", Entry->Name);
186 } else if (!SymIsRef (Entry)) {
187 /* Defined but not used */
188 if (IS_Get (&WarnUnusedLabel)) {
189 Warning ("`%s' is defined but never used", Entry->Name);
197 Entry = Entry->NextSym;
203 /*****************************************************************************/
204 /* Handling of lexical levels */
205 /*****************************************************************************/
209 unsigned GetLexicalLevel (void)
210 /* Return the current lexical level */
217 void EnterGlobalLevel (void)
218 /* Enter the program global lexical level */
221 PRECONDITION (++LexicalLevel == LEX_LEVEL_GLOBAL);
223 /* Create and assign the symbol table */
224 SymTab0 = SymTab = NewSymTable (SYMTAB_SIZE_GLOBAL);
226 /* Create and assign the tag table */
227 TagTab0 = TagTab = NewSymTable (SYMTAB_SIZE_GLOBAL);
232 void LeaveGlobalLevel (void)
233 /* Leave the program global lexical level */
236 PRECONDITION (LexicalLevel-- == LEX_LEVEL_GLOBAL);
238 /* Check the tables */
239 CheckSymTable (SymTab0);
241 /* Dump the tables if requested */
243 PrintSymTable (SymTab0, stdout, "Global symbol table");
244 PrintSymTable (TagTab0, stdout, "Global tag table");
247 /* Don't delete the symbol and struct tables! */
254 void EnterFunctionLevel (void)
255 /* Enter function lexical level */
259 /* New lexical level */
262 /* Get a new symbol table and make it current */
263 S = NewSymTable (SYMTAB_SIZE_FUNCTION);
267 /* Get a new tag table and make it current */
268 S = NewSymTable (SYMTAB_SIZE_FUNCTION);
272 /* Create and assign a new label table */
273 S = NewSymTable (SYMTAB_SIZE_LABEL);
274 S->PrevTab = LabelTab;
280 void RememberFunctionLevel (struct FuncDesc* F)
281 /* Remember the symbol tables for the level and leave the level without checks */
283 /* Leave the lexical level */
286 /* Remember the tables */
290 /* Don't delete the tables */
291 SymTab = SymTab->PrevTab;
292 TagTab = TagTab->PrevTab;
293 LabelTab = LabelTab->PrevTab;
298 void ReenterFunctionLevel (struct FuncDesc* F)
299 /* Reenter the function lexical level using the existing tables from F */
301 /* New lexical level */
304 /* Make the tables current again */
305 F->SymTab->PrevTab = SymTab;
308 F->TagTab->PrevTab = TagTab;
311 /* Create and assign a new label table */
312 LabelTab = NewSymTable (SYMTAB_SIZE_LABEL);
317 void LeaveFunctionLevel (void)
318 /* Leave function lexical level */
320 /* Leave the lexical level */
323 /* Check the tables */
324 CheckSymTable (SymTab);
325 CheckSymTable (LabelTab);
327 /* Drop the label table if it is empty */
328 if (LabelTab->SymCount == 0) {
329 FreeSymTable (LabelTab);
332 /* Don't delete the tables */
333 SymTab = SymTab->PrevTab;
334 TagTab = TagTab->PrevTab;
340 void EnterBlockLevel (void)
341 /* Enter a nested block in a function */
345 /* New lexical level */
348 /* Get a new symbol table and make it current */
349 S = NewSymTable (SYMTAB_SIZE_BLOCK);
353 /* Get a new tag table and make it current */
354 S = NewSymTable (SYMTAB_SIZE_BLOCK);
361 void LeaveBlockLevel (void)
362 /* Leave a nested block in a function */
364 /* Leave the lexical level */
367 /* Check the tables */
368 CheckSymTable (SymTab);
370 /* Don't delete the tables */
371 SymTab = SymTab->PrevTab;
372 TagTab = TagTab->PrevTab;
377 void EnterStructLevel (void)
378 /* Enter a nested block for a struct definition */
382 /* Get a new symbol table and make it current. Note: Structs and enums
383 ** nested in struct scope are NOT local to the struct but visible in the
384 ** outside scope. So we will NOT create a new struct or enum table.
386 S = NewSymTable (SYMTAB_SIZE_BLOCK);
393 void LeaveStructLevel (void)
394 /* Leave a nested block for a struct definition */
396 /* Don't delete the table */
397 SymTab = SymTab->PrevTab;
402 /*****************************************************************************/
404 /*****************************************************************************/
408 static SymEntry* FindSymInTable (const SymTable* T, const char* Name, unsigned Hash)
409 /* Search for an entry in one table */
411 /* Get the start of the hash chain */
412 SymEntry* E = T->Tab [Hash % T->Size];
414 /* Compare the name */
415 if (strcmp (E->Name, Name) == 0) {
419 /* Not found, next entry in hash chain */
429 static SymEntry* FindSymInTree (const SymTable* Tab, const char* Name)
430 /* Find the symbol with the given name in the table tree that starts with T */
432 /* Get the hash over the name */
433 unsigned Hash = HashStr (Name);
435 /* Check all symbol tables for the symbol */
437 /* Try to find the symbol in this table */
438 SymEntry* E = FindSymInTable (Tab, Name, Hash);
440 /* Bail out if we found it */
445 /* Repeat the search in the next higher lexical level */
455 SymEntry* FindSym (const char* Name)
456 /* Find the symbol with the given name */
458 return FindSymInTree (SymTab, Name);
463 SymEntry* FindGlobalSym (const char* Name)
464 /* Find the symbol with the given name in the global symbol table only */
466 return FindSymInTable (SymTab0, Name, HashStr (Name));
471 SymEntry* FindLocalSym (const char* Name)
472 /* Find the symbol with the given name in the current symbol table only */
474 return FindSymInTable (SymTab, Name, HashStr (Name));
479 SymEntry* FindTagSym (const char* Name)
480 /* Find the symbol with the given name in the tag table */
482 return FindSymInTree (TagTab, Name);
487 SymEntry* FindStructField (const Type* T, const char* Name)
488 /* Find a struct field in the fields list */
492 /* The given type may actually be a pointer to struct */
497 /* Non-structs do not have any struct fields... */
498 if (IsClassStruct (T)) {
500 /* Get a pointer to the struct/union type */
501 const SymEntry* Struct = GetSymEntry (T);
504 /* Now search in the struct symbol table. Beware: The table may not
507 if (Struct->V.S.SymTab) {
508 Field = FindSymInTable (Struct->V.S.SymTab, Name, HashStr (Name));
517 /*****************************************************************************/
518 /* Add stuff to the symbol table */
519 /*****************************************************************************/
523 static void AddSymEntry (SymTable* T, SymEntry* S)
524 /* Add a symbol to a symbol table */
526 /* Get the hash value for the name */
527 unsigned Hash = HashStr (S->Name) % T->Size;
529 /* Insert the symbol into the list of all symbols in this level */
531 T->SymTail->NextSym = S;
533 S->PrevSym = T->SymTail;
535 if (T->SymHead == 0) {
541 /* Insert the symbol into the hash chain */
542 S->NextHash = T->Tab[Hash];
545 /* Tell the symbol in which table it is */
551 SymEntry* AddStructSym (const char* Name, unsigned Type, unsigned Size, SymTable* Tab)
552 /* Add a struct/union entry and return it */
556 /* Type must be struct or union */
557 PRECONDITION (Type == SC_STRUCT || Type == SC_UNION);
559 /* Do we have an entry with this name already? */
560 Entry = FindSymInTable (TagTab, Name, HashStr (Name));
563 /* We do have an entry. This may be a forward, so check it. */
564 if ((Entry->Flags & SC_TYPEMASK) != Type) {
565 /* Existing symbol is not a struct */
566 Error ("Symbol `%s' is already different kind", Name);
567 } else if (Size > 0 && Entry->V.S.Size > 0) {
568 /* Both structs are definitions. */
569 Error ("Multiple definition for `%s'", Name);
571 /* Define the struct size if it is given */
573 Entry->V.S.SymTab = Tab;
574 Entry->V.S.Size = Size;
580 /* Create a new entry */
581 Entry = NewSymEntry (Name, Type);
583 /* Set the struct data */
584 Entry->V.S.SymTab = Tab;
585 Entry->V.S.Size = Size;
587 /* Add it to the current table */
588 AddSymEntry (TagTab, Entry);
591 /* Return the entry */
597 SymEntry* AddBitField (const char* Name, unsigned Offs, unsigned BitOffs, unsigned Width)
598 /* Add a bit field to the local symbol table and return the symbol entry */
600 /* Do we have an entry with this name already? */
601 SymEntry* Entry = FindSymInTable (SymTab, Name, HashStr (Name));
604 /* We have a symbol with this name already */
605 Error ("Multiple definition for `%s'", Name);
609 /* Create a new entry */
610 Entry = NewSymEntry (Name, SC_BITFIELD);
612 /* Set the symbol attributes. Bit-fields are always of type unsigned */
613 Entry->Type = type_uint;
614 Entry->V.B.Offs = Offs;
615 Entry->V.B.BitOffs = BitOffs;
616 Entry->V.B.BitWidth = Width;
618 /* Add the entry to the symbol table */
619 AddSymEntry (SymTab, Entry);
623 /* Return the entry */
629 SymEntry* AddConstSym (const char* Name, const Type* T, unsigned Flags, long Val)
630 /* Add an constant symbol to the symbol table and return it */
632 /* Enums must be inserted in the global symbol table */
633 SymTable* Tab = ((Flags & SC_ENUM) == SC_ENUM)? SymTab0 : SymTab;
635 /* Do we have an entry with this name already? */
636 SymEntry* Entry = FindSymInTable (Tab, Name, HashStr (Name));
638 if ((Entry->Flags & SC_CONST) != SC_CONST) {
639 Error ("Symbol `%s' is already different kind", Name);
641 Error ("Multiple definition for `%s'", Name);
646 /* Create a new entry */
647 Entry = NewSymEntry (Name, Flags);
649 /* Enum values are ints */
650 Entry->Type = TypeDup (T);
652 /* Set the enum data */
653 Entry->V.ConstVal = Val;
655 /* Add the entry to the symbol table */
656 AddSymEntry (Tab, Entry);
658 /* Return the entry */
663 DefOrRef* AddDefOrRef(SymEntry* E, unsigned Flags)
664 /* Add definition or reference to the SymEntry and preserve its attributes */
668 DOR = xmalloc (sizeof (DefOrRef));
669 CollAppend (E->V.L.DefsOrRefs, DOR);
670 DOR->Line = GetCurrentLine ();
671 DOR->LocalsBlockNum = (long)CollLast (&CurrentFunc->LocalsBlockStack);
678 SymEntry* AddLabelSym (const char* Name, unsigned Flags)
679 /* Add a goto label to the label table */
683 /* Do we have an entry with this name already? */
684 SymEntry* Entry = FindSymInTable (LabelTab, Name, HashStr (Name));
687 if (SymIsDef (Entry) && (Flags & SC_DEF) != 0) {
688 /* Trying to define the label more than once */
689 Error ("Label `%s' is defined more than once", Name);
692 /* Walk through all occurrences of the label so far and check
693 if any of them is in a region that would be risky to jump from/to
694 from the place where we are right now. */
695 for (i = 0; i < CollCount (Entry->V.L.DefsOrRefs); i++) {
696 DOR = CollAt (Entry->V.L.DefsOrRefs, i);
697 /* We are only interested in label occurences of type opposite to
698 the one currently being added, i.e. if we are processing the
699 definition, we will only check the gotos; if we are processing
700 a goto statement, we will only look for the label definition. */
701 if (((DOR->Flags & SC_DEF) != (Flags & SC_DEF)) &&
702 (DOR->LocalsBlockNum != (long)CollLast (&CurrentFunc->LocalsBlockStack)))
703 Warning ("Goto from line %d to label \'%s\' can result in a "
704 "trashed stack", Flags & SC_DEF ? DOR->Line : GetCurrentLine (), Name);
707 AddDefOrRef (Entry, Flags);
709 Entry->Flags |= Flags;
713 /* Create a new entry */
714 Entry = NewSymEntry (Name, SC_LABEL | Flags);
716 /* Set a new label number */
717 Entry->V.L.Label = GetLocalLabel ();
719 /* Create Collection for label definition and references */
720 Entry->V.L.DefsOrRefs = NewCollection ();
721 AddDefOrRef (Entry, Flags);
723 /* Generate the assembler name of the label */
724 Entry->AsmName = xstrdup (LocalLabelName (Entry->V.L.Label));
726 /* Add the entry to the label table */
727 AddSymEntry (LabelTab, Entry);
731 /* Return the entry */
737 SymEntry* AddLocalSym (const char* Name, const Type* T, unsigned Flags, int Offs)
738 /* Add a local symbol and return the symbol entry */
740 /* Do we have an entry with this name already? */
741 SymEntry* Entry = FindSymInTable (SymTab, Name, HashStr (Name));
744 /* We have a symbol with this name already */
745 Error ("Multiple definition for `%s'", Name);
749 /* Create a new entry */
750 Entry = NewSymEntry (Name, Flags);
752 /* Set the symbol attributes */
753 Entry->Type = TypeDup (T);
754 if ((Flags & SC_AUTO) == SC_AUTO) {
755 Entry->V.Offs = Offs;
756 } else if ((Flags & SC_REGISTER) == SC_REGISTER) {
757 Entry->V.R.RegOffs = Offs;
758 Entry->V.R.SaveOffs = StackPtr;
759 } else if ((Flags & SC_EXTERN) == SC_EXTERN) {
760 Entry->V.L.Label = Offs;
761 SymSetAsmName (Entry);
762 } else if ((Flags & SC_STATIC) == SC_STATIC) {
763 /* Generate the assembler name from the label number */
764 Entry->V.L.Label = Offs;
765 Entry->AsmName = xstrdup (LocalLabelName (Entry->V.L.Label));
766 } else if ((Flags & SC_STRUCTFIELD) == SC_STRUCTFIELD) {
767 Entry->V.Offs = Offs;
769 Internal ("Invalid flags in AddLocalSym: %04X", Flags);
772 /* Add the entry to the symbol table */
773 AddSymEntry (SymTab, Entry);
777 /* Return the entry */
783 SymEntry* AddGlobalSym (const char* Name, const Type* T, unsigned Flags)
784 /* Add an external or global symbol to the symbol table and return the entry */
786 /* There is some special handling for functions, so check if it is one */
787 int IsFunc = IsTypeFunc (T);
789 /* Functions must be inserted in the global symbol table */
790 SymTable* Tab = IsFunc? SymTab0 : SymTab;
792 /* Do we have an entry with this name already? */
793 SymEntry* Entry = FindSymInTable (Tab, Name, HashStr (Name));
798 /* We have a symbol with this name already */
799 if (Entry->Flags & SC_TYPE) {
800 Error ("Multiple definition for `%s'", Name);
804 /* Get the type string of the existing symbol */
807 /* If we are handling arrays, the old entry or the new entry may be an
808 ** incomplete declaration. Accept this, and if the exsting entry is
809 ** incomplete, complete it.
811 if (IsTypeArray (T) && IsTypeArray (EType)) {
813 /* Get the array sizes */
814 long Size = GetElementCount (T);
815 long ESize = GetElementCount (EType);
817 if ((Size != UNSPECIFIED && ESize != UNSPECIFIED && Size != ESize) ||
818 TypeCmp (T + 1, EType + 1) < TC_EQUAL) {
819 /* Types not identical: Conflicting types */
820 Error ("Conflicting types for `%s'", Name);
823 /* Check if we have a size in the existing definition */
824 if (ESize == UNSPECIFIED) {
825 /* Existing, size not given, use size from new def */
826 SetElementCount (EType, Size);
831 /* New type must be identical */
832 if (TypeCmp (EType, T) < TC_EQUAL) {
833 Error ("Conflicting types for `%s'", Name);
837 /* In case of a function, use the new type descriptor, since it
838 ** contains pointers to the new symbol tables that are needed if
839 ** an actual function definition follows. Be sure not to use the
840 ** new descriptor if it contains a function declaration with an
841 ** empty parameter list.
844 /* Get the function descriptor from the new type */
845 FuncDesc* F = GetFuncDesc (T);
846 /* Use this new function descriptor if it doesn't contain
847 ** an empty parameter list.
849 if ((F->Flags & FD_EMPTY) == 0) {
851 SetFuncDesc (EType, F);
856 /* If a static declaration follows a non-static declaration, then
857 ** warn about the conflict. (It will compile a public declaration.)
859 if ((Flags & SC_EXTERN) == 0 && (Entry->Flags & SC_EXTERN) != 0) {
860 Warning ("static declaration follows non-static declaration of `%s'.", Name);
863 /* An extern declaration must not change the current linkage. */
864 if (IsFunc || (Flags & (SC_EXTERN | SC_STORAGE)) == SC_EXTERN) {
868 /* If a public declaration follows a static declaration, then
869 ** warn about the conflict. (It will compile a public declaration.)
871 if ((Flags & SC_EXTERN) != 0 && (Entry->Flags & SC_EXTERN) == 0) {
872 Warning ("public declaration follows static declaration of `%s'.", Name);
875 /* Add the new flags */
876 Entry->Flags |= Flags;
880 /* Create a new entry */
881 Entry = NewSymEntry (Name, Flags);
883 /* Set the symbol attributes */
884 Entry->Type = TypeDup (T);
886 /* If this is a function, set the function descriptor and clear
887 ** additional fields.
890 Entry->V.F.Func = GetFuncDesc (Entry->Type);
894 /* Add the assembler name of the symbol */
895 SymSetAsmName (Entry);
897 /* Add the entry to the symbol table */
898 AddSymEntry (Tab, Entry);
901 /* Return the entry */
907 /*****************************************************************************/
909 /*****************************************************************************/
913 SymTable* GetSymTab (void)
914 /* Return the current symbol table */
921 SymTable* GetGlobalSymTab (void)
922 /* Return the global symbol table */
929 int SymIsLocal (SymEntry* Sym)
930 /* Return true if the symbol is defined in the highest lexical level */
932 return (Sym->Owner == SymTab || Sym->Owner == TagTab);
937 void MakeZPSym (const char* Name)
938 /* Mark the given symbol as zero page symbol */
940 /* Get the symbol table entry */
941 SymEntry* Entry = FindSymInTable (SymTab, Name, HashStr (Name));
943 /* Mark the symbol as zeropage */
945 Entry->Flags |= SC_ZEROPAGE;
947 Error ("Undefined symbol: `%s'", Name);
953 void PrintSymTable (const SymTable* Tab, FILE* F, const char* Header, ...)
954 /* Write the symbol table to the given file */
957 const SymEntry* Entry;
959 /* Print the header */
961 va_start (ap, Header);
963 Len = vfprintf (F, Header, ap);
967 /* Underline the header */
974 Entry = Tab->SymHead;
976 fprintf (F, "(empty)\n");
979 DumpSymEntry (F, Entry);
980 Entry = Entry->NextSym;
983 fprintf (F, "\n\n\n");
988 void EmitExternals (void)
989 /* Write import/export statements for external symbols */
993 Entry = SymTab->SymHead;
995 unsigned Flags = Entry->Flags;
996 if (Flags & SC_EXTERN) {
997 /* Only defined or referenced externs */
998 if (SymIsRef (Entry) && !SymIsDef (Entry)) {
1000 g_defimport (Entry->Name, Flags & SC_ZEROPAGE);
1001 } else if (SymIsDef (Entry)) {
1003 g_defexport (Entry->Name, Flags & SC_ZEROPAGE);
1006 Entry = Entry->NextSym;
1012 void EmitDebugInfo (void)
1013 /* Emit debug infos for the locals of the current scope */
1016 const SymEntry* Sym;
1018 /* Output info for locals if enabled */
1020 /* For cosmetic reasons in the output file, we will insert two tabs
1021 ** on global level and just one on local level.
1023 if (LexicalLevel == LEX_LEVEL_GLOBAL) {
1024 Head = "\t.dbg\t\tsym";
1026 Head = "\t.dbg\tsym";
1028 Sym = SymTab->SymHead;
1030 if ((Sym->Flags & (SC_CONST|SC_TYPE)) == 0) {
1031 if (Sym->Flags & SC_AUTO) {
1032 AddTextLine ("%s, \"%s\", \"00\", auto, %d",
1033 Head, Sym->Name, Sym->V.Offs);
1034 } else if (Sym->Flags & SC_REGISTER) {
1035 AddTextLine ("%s, \"%s\", \"00\", register, \"regbank\", %d",
1036 Head, Sym->Name, Sym->V.R.RegOffs);
1038 } else if (SymIsRef (Sym) && !SymIsDef (Sym)) {
1039 AddTextLine ("%s, \"%s\", \"00\", %s, \"%s\"",
1041 (Sym->Flags & SC_EXTERN)? "extern" : "static",