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