]> git.sur5r.net Git - cc65/blob - src/cc65/codeseg.c
62642e0bf101f686ca070ecc9652b773226264c5
[cc65] / src / cc65 / codeseg.c
1 /*****************************************************************************/
2 /*                                                                           */
3 /*                                 codeseg.c                                 */
4 /*                                                                           */
5 /*                          Code segment structure                           */
6 /*                                                                           */
7 /*                                                                           */
8 /*                                                                           */
9 /* (C) 2001      Ullrich von Bassewitz                                       */
10 /*               Wacholderweg 14                                             */
11 /*               D-70597 Stuttgart                                           */
12 /* EMail:        uz@cc65.org                                                 */
13 /*                                                                           */
14 /*                                                                           */
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.                                    */
18 /*                                                                           */
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:                            */
22 /*                                                                           */
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              */
30 /*    distribution.                                                          */
31 /*                                                                           */
32 /*****************************************************************************/
33
34
35
36 #include <string.h>
37 #include <ctype.h>
38
39 /* common */
40 #include "chartype.h"
41 #include "check.h"
42 #include "hashstr.h"
43 #include "strutil.h"
44 #include "xmalloc.h"
45 #include "xsprintf.h"
46
47 /* cc65 */
48 #include "asmlabel.h"
49 #include "codeent.h"
50 #include "codeinfo.h"
51 #include "error.h"
52 #include "codeseg.h"
53
54
55
56 /*****************************************************************************/
57 /*                             Helper functions                              */
58 /*****************************************************************************/
59
60
61
62 static void MoveLabelsToPool (CodeSeg* S, CodeEntry* E)
63 /* Move the labels of the code entry E to the label pool of the code segment */
64 {
65     unsigned LabelCount = GetCodeLabelCount (E);
66     while (LabelCount--) {
67         CodeLabel* L = GetCodeLabel (E, LabelCount);
68         L->Flags &= ~LF_DEF;
69         L->Owner = 0;
70         CollAppend (&S->Labels, L);
71     }
72     CollDeleteAll (&E->Labels);
73 }
74
75
76
77 static CodeLabel* FindCodeLabel (CodeSeg* S, const char* Name, unsigned Hash)
78 /* Find the label with the given name. Return the label or NULL if not found */
79 {
80     /* Get the first hash chain entry */
81     CodeLabel* L = S->LabelHash[Hash];
82
83     /* Search the list */
84     while (L) {
85         if (strcmp (Name, L->Name) == 0) {
86             /* Found */
87             break;
88         }
89         L = L->Next;
90     }
91     return L;
92 }
93
94
95
96 /*****************************************************************************/
97 /*                    Functions for parsing instructions                     */
98 /*****************************************************************************/
99
100
101
102 static CodeLabel* NewCodeSegLabel (CodeSeg* S, const char* Name, unsigned Hash)
103 /* Create a new label and insert it into the label hash table */
104 {
105     /* Not found - create a new one */
106     CodeLabel* L = NewCodeLabel (Name, Hash);
107
108     /* Enter the label into the hash table */
109     L->Next = S->LabelHash[L->Hash];
110     S->LabelHash[L->Hash] = L;
111
112     /* Return the new label */
113     return L;
114 }
115
116
117
118 static const char* SkipSpace (const char* S)
119 /* Skip white space and return an updated pointer */
120 {
121     while (IsSpace (*S)) {
122         ++S;
123     }
124     return S;
125 }
126
127
128
129 static const char* ReadToken (const char* L, const char* Term,
130                               char* Buf, unsigned BufSize)
131 /* Read the next token into Buf, return the updated line pointer. The
132  * token is terminated by one of the characters given in term.
133  */
134 {
135     /* Read/copy the token */
136     unsigned I = 0;
137     unsigned ParenCount = 0;
138     while (*L && (ParenCount > 0 || strchr (Term, *L) == 0)) {
139         if (I < BufSize-1) {
140             Buf[I++] = *L;
141         }
142         if (*L == ')') {
143             --ParenCount;
144         } else if (*L == '(') {
145             ++ParenCount;
146         }
147         ++L;
148     }
149
150     /* Terminate the buffer contents */
151     Buf[I] = '\0';
152
153     /* Return the updated line pointer */
154     return L;
155 }
156
157
158
159 static CodeEntry* ParseInsn (CodeSeg* S, const char* L)
160 /* Parse an instruction nnd generate a code entry from it. If the line contains
161  * errors, output an error message and return NULL.
162  * For simplicity, we don't accept the broad range of input a "real" assembler
163  * does. The instruction and the argument are expected to be separated by
164  * white space, for example.
165  */
166 {
167     char                Mnemo[16];
168     const OPCDesc*      OPC;
169     am_t                AM = 0;         /* Initialize to keep gcc silent */
170     char                Arg[64];
171     char                Reg;
172     CodeEntry*          E;
173     CodeLabel*          Label;
174
175     /* Mnemonic */
176     L = ReadToken (L, " \t", Mnemo, sizeof (Mnemo));
177
178     /* Try to find the opcode description for the mnemonic */
179     OPC = FindOpcode (Mnemo);
180
181     /* If we didn't find the opcode, print an error and bail out */
182     if (OPC == 0) {
183         Error ("ASM code error: %s is not a valid mnemonic", Mnemo);
184         return 0;
185     }
186
187     /* Skip separator white space */
188     L = SkipSpace (L);
189
190     /* Get the addressing mode */
191     Arg[0] = '\0';
192     switch (*L) {
193
194         case '\0':
195             /* Implicit */
196             AM = AM_IMP;
197             break;
198
199         case '#':
200             /* Immidiate */
201             StrCopy (Arg, sizeof (Arg), L+1);
202             AM = AM_IMM;
203             break;
204
205         case '(':
206             /* Indirect */
207             L = ReadToken (L+1, ",)", Arg, sizeof (Arg));
208
209             /* Check for errors */
210             if (*L == '\0') {
211                 Error ("ASM code error: syntax error");
212                 return 0;
213             }
214
215             /* Check the different indirect modes */
216             if (*L == ',') {
217                 /* Expect zp x indirect */
218                 L = SkipSpace (L+1);
219                 if (toupper (*L) != 'X') {
220                     Error ("ASM code error: `X' expected");
221                     return 0;
222                 }
223                 L = SkipSpace (L+1);
224                 if (*L != ')') {
225                     Error ("ASM code error: `)' expected");
226                     return 0;
227                 }
228                 L = SkipSpace (L+1);
229                 if (*L != '\0') {
230                     Error ("ASM code error: syntax error");
231                     return 0;
232                 }
233                 AM = AM_ZPX_IND;
234             } else if (*L == ')') {
235                 /* zp indirect or zp indirect, y */
236                 L = SkipSpace (L+1);
237                 if (*L == ',') {
238                     L = SkipSpace (L+1);
239                     if (toupper (*L) != 'Y') {
240                         Error ("ASM code error: `Y' expected");
241                         return 0;
242                     }
243                     L = SkipSpace (L+1);
244                     if (*L != '\0') {
245                         Error ("ASM code error: syntax error");
246                         return 0;
247                     }
248                     AM = AM_ZP_INDY;
249                 } else if (*L == '\0') {
250                     AM = AM_ZP_IND;
251                 } else {
252                     Error ("ASM code error: syntax error");
253                     return 0;
254                 }
255             }
256             break;
257
258         case 'a':
259         case 'A':
260             /* Accumulator? */
261             if (L[1] == '\0') {
262                 AM = AM_ACC;
263                 break;
264             }
265             /* FALLTHROUGH */
266
267         default:
268             /* Absolute, maybe indexed */
269             L = ReadToken (L, ",", Arg, sizeof (Arg));
270             if (*L == '\0') {
271                 /* Assume absolute */
272                 AM = AM_ABS;
273             } else if (*L == ',') {
274                 /* Indexed */
275                 L = SkipSpace (L+1);
276                 if (*L == '\0') {
277                     Error ("ASM code error: syntax error");
278                     return 0;
279                 } else {
280                     Reg = toupper (*L);
281                     L = SkipSpace (L+1);
282                     if (Reg == 'X') {
283                         AM = AM_ABSX;
284                     } else if (Reg == 'Y') {
285                         AM = AM_ABSY;
286                     } else {
287                         Error ("ASM code error: syntax error");
288                         return 0;
289                     }
290                     if (*L != '\0') {
291                         Error ("ASM code error: syntax error");
292                         return 0;
293                     }
294                 }
295             }
296             break;
297
298     }
299
300     /* If the instruction is a branch, check for the label and generate it
301      * if it does not exist. Ignore anything but local labels here.
302      */
303     Label = 0;
304     if ((OPC->Info & OF_BRA) != 0 && Arg[0] == 'L') {
305
306         unsigned Hash;
307
308         /* Addressing mode must be alsobute or something is really wrong */
309         CHECK (AM == AM_ABS);
310
311         /* Addressing mode is a branch/jump */
312         AM = AM_BRA;
313
314         /* Generate the hash over the label, then search for the label */
315         Hash = HashStr (Arg) % CS_LABEL_HASH_SIZE;
316         Label = FindCodeLabel (S, Arg, Hash);
317
318         /* If we don't have the label, it's a forward ref - create it */
319         if (Label == 0) {
320             /* Generate a new label */
321             Label = NewCodeSegLabel (S, Arg, Hash);
322         }
323     }
324
325     /* We do now have the addressing mode in AM. Allocate a new CodeEntry
326      * structure and initialize it.
327      */
328     E = NewCodeEntry (OPC, AM, Arg, Label);
329
330     /* Return the new code entry */
331     return E;
332 }
333
334
335
336 /*****************************************************************************/
337 /*                                   Code                                    */
338 /*****************************************************************************/
339
340
341
342 CodeSeg* NewCodeSeg (const char* SegName, SymEntry* Func)
343 /* Create a new code segment, initialize and return it */
344 {
345     unsigned I;
346
347     /* Allocate memory */
348     CodeSeg* S = xmalloc (sizeof (CodeSeg));
349
350     /* Initialize the fields */
351     S->SegName  = xstrdup (SegName);
352     S->Func     = Func;
353     InitCollection (&S->Entries);
354     InitCollection (&S->Labels);
355     for (I = 0; I < sizeof(S->LabelHash) / sizeof(S->LabelHash[0]); ++I) {
356         S->LabelHash[I] = 0;
357     }
358
359     /* Return the new struct */
360     return S;
361 }
362
363
364
365 void AddCodeEntry (CodeSeg* S, const char* Format, va_list ap)
366 /* Add a line to the given code segment */
367 {
368     const char* L;
369     CodeEntry*  E;
370     char        Token[64];
371
372     /* Format the line */
373     char Buf [256];
374     xvsprintf (Buf, sizeof (Buf), Format, ap);
375
376     /* Skip whitespace */
377     L = SkipSpace (Buf);
378
379     /* Check which type of instruction we have */
380     E = 0;      /* Assume no insn created */
381     switch (*L) {
382
383         case '\0':
384             /* Empty line, just ignore it */
385             break;
386
387         case ';':
388             /* Comment or hint, ignore it for now */
389             break;
390
391         case '.':
392             /* Control instruction */
393             ReadToken (L, " \t", Token, sizeof (Token));
394             Error ("ASM code error: Pseudo instruction `%s' not supported", Token);
395             break;
396
397         default:
398             E = ParseInsn (S, L);
399             break;
400     }
401
402     /* If we have a code entry, transfer the labels and insert it */
403     if (E) {
404
405         /* Transfer the labels if we have any */
406         unsigned I;
407         unsigned LabelCount = CollCount (&S->Labels);
408         for (I = 0; I < LabelCount; ++I) {
409
410             /* Get the label */
411             CodeLabel* L = CollAt (&S->Labels, I);
412
413             /* Attach it to the entry */
414             AttachCodeLabel (E, L);
415         }
416
417         /* Delete the transfered labels */
418         CollDeleteAll (&S->Labels);
419
420         /* Add the entry to the list of code entries in this segment */
421         CollAppend (&S->Entries, E);
422
423     }
424 }
425
426
427
428 void DelCodeEntry (CodeSeg* S, unsigned Index)
429 /* Delete an entry from the code segment. This includes moving any associated
430  * labels, removing references to labels and even removing the referenced labels
431  * if the reference count drops to zero.
432  */
433 {
434     /* Get the code entry for the given index */
435     CodeEntry* E = GetCodeEntry (S, Index);
436
437     /* If the entry has a labels, we have to move this label to the next insn.
438      * If there is no next insn, move the label into the code segement label
439      * pool. The operation is further complicated by the fact that the next
440      * insn may already have a label. In that case change all reference to
441      * this label and delete the label instead of moving it.
442      */
443     unsigned Count = GetCodeLabelCount (E);
444     if (Count > 0) {
445
446         /* The instruction has labels attached. Check if there is a next
447          * instruction.
448          */
449         if (Index == GetCodeEntryCount (S)-1) {
450
451             /* No next instruction, move to the codeseg label pool */
452             MoveLabelsToPool (S, E);
453
454         } else {
455
456             /* There is a next insn, get it */
457             CodeEntry* N = GetCodeEntry (S, Index+1);
458
459             /* Move labels to the next entry */
460             MoveCodeLabels (S, E, N);
461
462         }
463     }
464
465     /* If this insn references a label, remove the reference. And, if the
466      * the reference count for this label drops to zero, remove this label.
467      */
468     if (E->JumpTo) {
469         /* Remove the reference */
470         RemoveCodeLabelRef (S, E);
471     }
472
473     /* Delete the pointer to the insn */
474     CollDelete (&S->Entries, Index);
475
476     /* Delete the instruction itself */
477     FreeCodeEntry (E);
478 }
479
480
481
482 struct CodeEntry* GetCodeEntry (CodeSeg* S, unsigned Index)
483 /* Get an entry from the given code segment */
484 {
485     return CollAt (&S->Entries, Index);
486 }
487
488
489
490 unsigned GetCodeEntryIndex (CodeSeg* S, struct CodeEntry* E)
491 /* Return the index of a code entry */
492 {
493     int Index = CollIndex (&S->Entries, E);
494     CHECK (Index >= 0);
495     return Index;
496 }
497
498
499
500 void AddCodeLabel (CodeSeg* S, const char* Name)
501 /* Add a code label for the next instruction to follow */
502 {
503     /* Calculate the hash from the name */
504     unsigned Hash = HashStr (Name) % CS_LABEL_HASH_SIZE;
505
506     /* Try to find the code label if it does already exist */
507     CodeLabel* L = FindCodeLabel (S, Name, Hash);
508
509     /* Did we find it? */
510     if (L) {
511         /* We found it - be sure it does not already have an owner */
512         CHECK (L->Owner == 0);
513     } else {
514         /* Not found - create a new one */
515         L = NewCodeSegLabel (S, Name, Hash);
516     }
517
518     /* We do now have a valid label. Remember it for later */
519     CollAppend (&S->Labels, L);
520 }
521
522
523
524 CodeLabel* GenCodeLabel (CodeSeg* S, struct CodeEntry* E)
525 /* If the code entry E does already have a label, return it. Otherwise
526  * create a new label, attach it to E and return it.
527  */
528 {
529     CodeLabel* L;
530
531     if (CodeEntryHasLabel (E)) {
532
533         /* Get the label from this entry */
534         L = GetCodeLabel (E, 0);
535
536     } else {
537
538         /* Get a new name */
539         const char* Name = LocalLabelName (GetLocalLabel ());
540
541         /* Generate the hash over the name */
542         unsigned Hash = HashStr (Name) % CS_LABEL_HASH_SIZE;
543
544         /* Create a new label */
545         L = NewCodeSegLabel (S, Name, Hash);
546
547         /* Attach this label to the code entry */
548         AttachCodeLabel (E, L);
549
550     }
551
552     /* Return the label */
553     return L;
554 }
555
556
557
558 void DelCodeLabel (CodeSeg* S, CodeLabel* L)
559 /* Remove references from this label and delete it. */
560 {
561     unsigned Count, I;
562
563     /* Get the first entry in the hash chain */
564     CodeLabel* List = S->LabelHash[L->Hash];
565
566     /* First, remove the label from the hash chain */
567     if (List == L) {
568         /* First entry in hash chain */
569         S->LabelHash[L->Hash] = L->Next;
570     } else {
571         /* Must search through the chain */
572         while (List->Next != L) {
573             /* If we've reached the end of the chain, something is *really* wrong */
574             CHECK (List->Next != 0);
575             /* Next entry */
576             List = List->Next;
577         }
578         /* The next entry is the one, we have been searching for */
579         List->Next = L->Next;
580     }
581
582     /* Remove references from insns jumping to this label */
583     Count = CollCount (&L->JumpFrom);
584     for (I = 0; I < Count; ++I) {
585         /* Get the insn referencing this label */
586         CodeEntry* E = CollAt (&L->JumpFrom, I);
587         /* Remove the reference */
588         E->JumpTo = 0;
589     }
590     CollDeleteAll (&L->JumpFrom);
591
592     /* Remove the reference to the owning instruction */
593     CollDeleteItem (&L->Owner->Labels, L);
594
595     /* All references removed, delete the label itself */
596     FreeCodeLabel (L);
597 }
598
599
600
601 void MergeCodeLabels (CodeSeg* S)
602 /* Merge code labels. That means: For each instruction, remove all labels but
603  * one and adjust references accordingly.
604  */
605 {
606     unsigned I;
607
608     /* Walk over all code entries */
609     unsigned EntryCount = GetCodeEntryCount (S);
610     for (I = 0; I < EntryCount; ++I) {
611
612         CodeLabel* RefLab;
613         unsigned   J;
614
615         /* Get a pointer to the next entry */
616         CodeEntry* E = GetCodeEntry (S, I);
617
618         /* If this entry has zero labels, continue with the next one */
619         unsigned LabelCount = GetCodeLabelCount (E);
620         if (LabelCount == 0) {
621             continue;
622         }
623
624         /* We have at least one label. Use the first one as reference label. */
625         RefLab = GetCodeLabel (E, 0);
626
627         /* Walk through the remaining labels and change references to these
628          * labels to a reference to the one and only label. Delete the labels
629          * that are no longer used. To increase performance, walk backwards
630          * through the list.
631          */
632         for (J = LabelCount-1; J >= 1; --J) {
633
634             /* Get the next label */
635             CodeLabel* L = GetCodeLabel (E, J);
636
637             /* Move all references from this label to the reference label */
638             MoveLabelRefs (L, RefLab);
639
640             /* Remove the label completely. */
641             DelCodeLabel (S, L);
642         }
643
644         /* The reference label is the only remaining label. Check if there
645          * are any references to this label, and delete it if this is not
646          * the case.
647          */
648         if (CollCount (&RefLab->JumpFrom) == 0) {
649             /* Delete the label */
650             DelCodeLabel (S, RefLab);
651         }
652     }
653 }
654
655
656
657 void MoveCodeLabels (CodeSeg* S, struct CodeEntry* Old, struct CodeEntry* New)
658 /* Move all labels from Old to New. The routine will move the labels itself
659  * if New does not have any labels, and move references if there is at least
660  * a label for new. If references are moved, the old label is deleted
661  * afterwards.
662  */
663 {
664     /* Get the number of labels to move */
665     unsigned OldLabelCount = GetCodeLabelCount (Old);
666
667     /* Does the new entry have itself a label? */
668     if (CodeEntryHasLabel (New)) {
669
670         /* The new entry does already have a label - move references */
671         CodeLabel* NewLabel = GetCodeLabel (New, 0);
672         while (OldLabelCount--) {
673
674             /* Get the next label */
675             CodeLabel* OldLabel = GetCodeLabel (Old, OldLabelCount);
676
677             /* Move references */
678             MoveLabelRefs (OldLabel, NewLabel);
679
680             /* Delete the label */
681             DelCodeLabel (S, OldLabel);
682
683         }
684
685     } else {
686
687         /* The new entry does not have a label, just move them */
688         while (OldLabelCount--) {
689
690             /* Move the label to the new entry */
691             MoveCodeLabel (GetCodeLabel (Old, OldLabelCount), New);
692
693         }
694
695     }
696 }
697
698
699
700 void RemoveCodeLabelRef (CodeSeg* S, struct CodeEntry* E)                         
701 /* Remove the reference between E and the label it jumps to. The reference
702  * will be removed on both sides and E->JumpTo will be 0 after that. If
703  * the reference was the only one for the label, the label will get
704  * deleted.
705  */
706 {
707     /* Get a pointer to the label and make sure it exists */
708     CodeLabel* L = E->JumpTo;
709     CHECK (L != 0);
710
711     /* Delete the entry from the label */
712     CollDeleteItem (&L->JumpFrom, E);
713
714     /* The entry jumps no longer to L */
715     E->JumpTo = 0;
716
717     /* If there are no more references, delete the label */
718     if (CollCount (&L->JumpFrom) == 0) {
719         DelCodeLabel (S, L);
720     }
721 }
722
723
724
725 void MoveCodeLabelRef (CodeSeg* S, struct CodeEntry* E, CodeLabel* L)
726 /* Change the reference of E to L instead of the current one. If this
727  * was the only reference to the old label, the old label will get
728  * deleted.
729  */
730 {
731     /* Get the old label */
732     CodeLabel* OldLabel = E->JumpTo;
733
734     /* Be sure that code entry references a label */
735     PRECONDITION (OldLabel != 0);
736
737     /* Remove the reference to our label */
738     RemoveCodeLabelRef (S, E);
739
740     /* Use the new label */
741     AddLabelRef (L, E);
742 }
743
744
745
746 void AddCodeSegHint (CodeSeg* S, unsigned Hint)
747 /* Add a hint for the preceeding instruction */
748 {
749     CodeEntry* E;
750
751     /* Get the number of entries in this segment */
752     unsigned EntryCount = GetCodeEntryCount (S);
753
754     /* Must have at least one entry */
755     CHECK (EntryCount > 0);
756
757     /* Get the last entry */
758     E = GetCodeEntry (S, EntryCount-1);
759
760     /* Add the hint */
761     E->Hints |= Hint;
762 }
763
764
765
766 void DelCodeSegAfter (CodeSeg* S, unsigned Last)
767 /* Delete all entries including the given one */
768 {
769     /* Get the number of entries in this segment */
770     unsigned Count = GetCodeEntryCount (S);
771
772     /* Remove all entries after the given one */
773     while (Last < Count) {
774
775         /* Get the next entry */
776         CodeEntry* E = GetCodeEntry (S, Count-1);
777
778         /* We have to transfer all labels to the code segment label pool */
779         MoveLabelsToPool (S, E);
780
781         /* Remove the code entry */
782         FreeCodeEntry (E);
783         CollDelete (&S->Entries, Count-1);
784         --Count;
785     }
786 }
787
788
789
790 void OutputCodeSeg (const CodeSeg* S, FILE* F)
791 /* Output the code segment data to a file */
792 {
793     unsigned I;
794
795     /* Get the number of entries in this segment */
796     unsigned Count = GetCodeEntryCount (S);
797
798     /* If the code segment is empty, bail out here */
799     if (Count == 0) {
800         return;
801     }
802
803     /* Output the segment directive */
804     fprintf (F, ".segment\t\"%s\"\n\n", S->SegName);
805
806     /* If this is a segment for a function, enter a function */
807     if (S->Func) {
808         fprintf (F, ".proc\t_%s\n\n", S->Func->Name);
809     }
810
811     /* Output all entries */
812     for (I = 0; I < Count; ++I) {
813         OutputCodeEntry (CollConstAt (&S->Entries, I), F);
814     }
815
816     /* If this is a segment for a function, leave the function */
817     if (S->Func) {
818         fprintf (F, "\n.endproc\n\n");
819     }
820 }
821
822
823
824 unsigned GetCodeEntryCount (const CodeSeg* S)
825 /* Return the number of entries for the given code segment */
826 {
827     return CollCount (&S->Entries);
828 }
829
830
831
832