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