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