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-2002 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 "global.h"
  43 #include "hashstr.h"
  44 #include "strutil.h"
  45 #include "xmalloc.h"
  46 #include "xsprintf.h"
  47
  48 /* cc65 */
  49 #include "asmlabel.h"
  50 #include "codeent.h"
  51 #include "codeinfo.h"
  52 #include "datatype.h"
  53 #include "error.h"
  54 #include "ident.h"
  55 #include "symentry.h"
  56 #include "codeseg.h"
  57
  58
  59
  60 /*****************************************************************************/
  61 /*                             Helper functions                              */
  62 /*****************************************************************************/
  63
  64
  65
  66 static void CS_PrintFunctionHeader (const CodeSeg* S, FILE* F)
  67 /* Print a comment with the function signature to the given file */
  68 {
  69     /* Get the associated function */
  70     const SymEntry* Func = S->Func;
  71
  72     /* If this is a global code segment, do nothing */
  73     if (Func) {
  74         fprintf (F,
  75                  "; ---------------------------------------------------------------\n"
  76                  "; ");
  77         PrintFuncSig (F, Func->Name, Func->Type);
  78         fprintf (F,
  79                  "\n"
  80                  "; ---------------------------------------------------------------\n"
  81                  "\n");
  82     }
  83 }
  84
  85
  86
  87 static void CS_MoveLabelsToEntry (CodeSeg* S, CodeEntry* E)
  88 /* Move all labels from the label pool to the given entry and remove them
  89  * from the pool.
  90  */
  91 {
  92     /* Transfer the labels if we have any */
  93     unsigned I;
  94     unsigned LabelCount = CollCount (&S->Labels);
  95     for (I = 0; I < LabelCount; ++I) {
  96
  97         /* Get the label */
  98         CodeLabel* L = CollAt (&S->Labels, I);
  99
 100         /* Attach it to the entry */
 101         CE_AttachLabel (E, L);
 102     }
 103
 104     /* Delete the transfered labels */
 105     CollDeleteAll (&S->Labels);
 106 }
 107
 108
 109
 110 static void CS_MoveLabelsToPool (CodeSeg* S, CodeEntry* E)
 111 /* Move the labels of the code entry E to the label pool of the code segment */
 112 {
 113     unsigned LabelCount = CE_GetLabelCount (E);
 114     while (LabelCount--) {
 115         CodeLabel* L = CE_GetLabel (E, LabelCount);
 116         L->Owner = 0;
 117         CollAppend (&S->Labels, L);
 118     }
 119     CollDeleteAll (&E->Labels);
 120 }
 121
 122
 123
 124 static CodeLabel* CS_FindLabel (CodeSeg* S, const char* Name, unsigned Hash)
 125 /* Find the label with the given name. Return the label or NULL if not found */
 126 {
 127     /* Get the first hash chain entry */
 128     CodeLabel* L = S->LabelHash[Hash];
 129
 130     /* Search the list */
 131     while (L) {
 132         if (strcmp (Name, L->Name) == 0) {
 133             /* Found */
 134             break;
 135         }
 136         L = L->Next;
 137     }
 138     return L;
 139 }
 140
 141
 142
 143 static CodeLabel* CS_NewCodeLabel (CodeSeg* S, const char* Name, unsigned Hash)
 144 /* Create a new label and insert it into the label hash table */
 145 {
 146     /* Create a new label */
 147     CodeLabel* L = NewCodeLabel (Name, Hash);
 148
 149     /* Enter the label into the hash table */
 150     L->Next = S->LabelHash[L->Hash];
 151     S->LabelHash[L->Hash] = L;
 152
 153     /* Return the new label */
 154     return L;
 155 }
 156
 157
 158
 159 static void CS_RemoveLabelFromHash (CodeSeg* S, CodeLabel* L)
 160 /* Remove the given code label from the hash list */
 161 {
 162     /* Get the first entry in the hash chain */
 163     CodeLabel* List = S->LabelHash[L->Hash];
 164     CHECK (List != 0);
 165
 166     /* First, remove the label from the hash chain */
 167     if (List == L) {
 168         /* First entry in hash chain */
 169         S->LabelHash[L->Hash] = L->Next;
 170     } else {
 171         /* Must search through the chain */
 172         while (List->Next != L) {
 173             /* If we've reached the end of the chain, something is *really* wrong */
 174             CHECK (List->Next != 0);
 175             /* Next entry */
 176             List = List->Next;
 177         }
 178         /* The next entry is the one, we have been searching for */
 179         List->Next = L->Next;
 180     }
 181 }
 182
 183
 184
 185 static CodeLabel* CS_AddLabelInternal (CodeSeg* S, const char* Name,
 186                                        void (*ErrorFunc) (const char*, ...))
 187 /* Add a code label for the next instruction to follow */
 188 {
 189     /* Calculate the hash from the name */
 190     unsigned Hash = HashStr (Name) % CS_LABEL_HASH_SIZE;
 191
 192     /* Try to find the code label if it does already exist */
 193     CodeLabel* L = CS_FindLabel (S, Name, Hash);
 194
 195     /* Did we find it? */
 196     if (L) {
 197         /* We found it - be sure it does not already have an owner */
 198         if (L->Owner) {
 199             ErrorFunc ("ASM label `%s' is already defined", Name);
 200         }
 201     } else {
 202         /* Not found - create a new one */
 203         L = CS_NewCodeLabel (S, Name, Hash);
 204     }
 205
 206     /* Safety. This call is quite costly, but safety is better */
 207     if (CollIndex (&S->Labels, L) >= 0) {
 208         ErrorFunc ("ASM label `%s' is already defined", Name);
 209     }
 210
 211     /* We do now have a valid label. Remember it for later */
 212     CollAppend (&S->Labels, L);
 213
 214     /* Return the label */
 215     return L;
 216 }
 217
 218
 219
 220 /*****************************************************************************/
 221 /*                    Functions for parsing instructions                     */
 222 /*****************************************************************************/
 223
 224
 225
 226 static const char* SkipSpace (const char* S)
 227 /* Skip white space and return an updated pointer */
 228 {
 229     while (IsSpace (*S)) {
 230         ++S;
 231     }
 232     return S;
 233 }
 234
 235
 236
 237 static const char* ReadToken (const char* L, const char* Term,
 238                               char* Buf, unsigned BufSize)
 239 /* Read the next token into Buf, return the updated line pointer. The
 240  * token is terminated by one of the characters given in term.
 241  */
 242 {
 243     /* Read/copy the token */
 244     unsigned I = 0;
 245     unsigned ParenCount = 0;
 246     while (*L && (ParenCount > 0 || strchr (Term, *L) == 0)) {
 247         if (I < BufSize-1) {
 248             Buf[I] = *L;
 249         } else if (I == BufSize-1) {
 250             /* Cannot store this character, this is an input error (maybe
 251              * identifier too long or similar).
 252              */
 253             Error ("ASM code error: syntax error");
 254         }
 255         ++I;
 256         if (*L == ')') {
 257             --ParenCount;
 258         } else if (*L == '(') {
 259             ++ParenCount;
 260         }
 261         ++L;
 262     }
 263
 264     /* Terminate the buffer contents */
 265     Buf[I] = '\0';
 266
 267     /* Return the updated line pointer */
 268     return L;
 269 }
 270
 271
 272
 273 static CodeEntry* ParseInsn (CodeSeg* S, LineInfo* LI, const char* L)
 274 /* Parse an instruction nnd generate a code entry from it. If the line contains
 275  * errors, output an error message and return NULL.
 276  * For simplicity, we don't accept the broad range of input a "real" assembler
 277  * does. The instruction and the argument are expected to be separated by
 278  * white space, for example.
 279  */
 280 {
 281     char                Mnemo[IDENTSIZE+10];
 282     const OPCDesc*      OPC;
 283     am_t                AM = 0;         /* Initialize to keep gcc silent */
 284     char                Arg[IDENTSIZE+10];
 285     char                Reg;
 286     CodeEntry*          E;
 287     CodeLabel*          Label;
 288
 289     /* Read the first token and skip white space after it */
 290     L = SkipSpace (ReadToken (L, " \t:", Mnemo, sizeof (Mnemo)));
 291
 292     /* Check if we have a label */
 293     if (*L == ':') {
 294
 295         /* Skip the colon and following white space */
 296         L = SkipSpace (L+1);
 297
 298         /* Add the label */
 299         CS_AddLabelInternal (S, Mnemo, Error);
 300
 301         /* If we have reached end of line, bail out, otherwise a mnemonic
 302          * may follow.
 303          */
 304         if (*L == '\0') {
 305             return 0;
 306         }
 307
 308         L = SkipSpace (ReadToken (L, " \t", Mnemo, sizeof (Mnemo)));
 309     }
 310
 311     /* Try to find the opcode description for the mnemonic */
 312     OPC = FindOP65 (Mnemo);
 313
 314     /* If we didn't find the opcode, print an error and bail out */
 315     if (OPC == 0) {
 316         Error ("ASM code error: %s is not a valid mnemonic", Mnemo);
 317         return 0;
 318     }
 319
 320     /* Get the addressing mode */
 321     Arg[0] = '\0';
 322     switch (*L) {
 323
 324         case '\0':
 325             /* Implicit */
 326             AM = AM65_IMP;
 327             break;
 328
 329         case '#':
 330             /* Immidiate */
 331             StrCopy (Arg, sizeof (Arg), L+1);
 332             AM = AM65_IMM;
 333             break;
 334
 335         case '(':
 336             /* Indirect */
 337             L = ReadToken (L+1, ",)", Arg, sizeof (Arg));
 338
 339             /* Check for errors */
 340             if (*L == '\0') {
 341                 Error ("ASM code error: syntax error");
 342                 return 0;
 343             }
 344
 345             /* Check the different indirect modes */
 346             if (*L == ',') {
 347                 /* Expect zp x indirect */
 348                 L = SkipSpace (L+1);
 349                 if (toupper (*L) != 'X') {
 350                     Error ("ASM code error: `X' expected");
 351                     return 0;
 352                 }
 353                 L = SkipSpace (L+1);
 354                 if (*L != ')') {
 355                     Error ("ASM code error: `)' expected");
 356                     return 0;
 357                 }
 358                 L = SkipSpace (L+1);
 359                 if (*L != '\0') {
 360                     Error ("ASM code error: syntax error");
 361                     return 0;
 362                 }
 363                 AM = AM65_ZPX_IND;
 364             } else if (*L == ')') {
 365                 /* zp indirect or zp indirect, y */
 366                 L = SkipSpace (L+1);
 367                 if (*L == ',') {
 368                     L = SkipSpace (L+1);
 369                     if (toupper (*L) != 'Y') {
 370                         Error ("ASM code error: `Y' expected");
 371                         return 0;
 372                     }
 373                     L = SkipSpace (L+1);
 374                     if (*L != '\0') {
 375                         Error ("ASM code error: syntax error");
 376                         return 0;
 377                     }
 378                     AM = AM65_ZP_INDY;
 379                 } else if (*L == '\0') {
 380                     AM = AM65_ZP_IND;
 381                 } else {
 382                     Error ("ASM code error: syntax error");
 383                     return 0;
 384                 }
 385             }
 386             break;
 387
 388         case 'a':
 389         case 'A':
 390             /* Accumulator? */
 391             if (L[1] == '\0') {
 392                 AM = AM65_ACC;
 393                 break;
 394             }
 395             /* FALLTHROUGH */
 396
 397         default:
 398             /* Absolute, maybe indexed */
 399             L = ReadToken (L, ",", Arg, sizeof (Arg));
 400             if (*L == '\0') {
 401                 /* Absolute, zeropage or branch */
 402                 if ((OPC->Info & OF_BRA) != 0) {
 403                     /* Branch */
 404                     AM = AM65_BRA;
 405                 } else if (GetZPInfo(Arg) != 0) {
 406                     AM = AM65_ZP;
 407                 } else {
 408                     AM = AM65_ABS;
 409                 }
 410             } else if (*L == ',') {
 411                 /* Indexed */
 412                 L = SkipSpace (L+1);
 413                 if (*L == '\0') {
 414                     Error ("ASM code error: syntax error");
 415                     return 0;
 416                 } else {
 417                     Reg = toupper (*L);
 418                     L = SkipSpace (L+1);
 419                     if (Reg == 'X') {
 420                         if (GetZPInfo(Arg) != 0) {
 421                             AM = AM65_ZPX;
 422                         } else {
 423                             AM = AM65_ABSX;
 424                         }
 425                     } else if (Reg == 'Y') {
 426                         AM = AM65_ABSY;
 427                     } else {
 428                         Error ("ASM code error: syntax error");
 429                         return 0;
 430                     }
 431                     if (*L != '\0') {
 432                         Error ("ASM code error: syntax error");
 433                         return 0;
 434                     }
 435                 }
 436             }
 437             break;
 438
 439     }
 440
 441     /* If the instruction is a branch, check for the label and generate it
 442      * if it does not exist. This may lead to unused labels (if the label
 443      * is actually an external one) which are removed by the CS_MergeLabels
 444      * function later.
 445      */
 446     Label = 0;
 447     if (AM == AM65_BRA) {
 448
 449         /* Generate the hash over the label, then search for the label */
 450         unsigned Hash = HashStr (Arg) % CS_LABEL_HASH_SIZE;
 451         Label = CS_FindLabel (S, Arg, Hash);
 452
 453         /* If we don't have the label, it's a forward ref - create it */
 454         if (Label == 0) {
 455             /* Generate a new label */
 456             Label = CS_NewCodeLabel (S, Arg, Hash);
 457         }
 458     }
 459
 460     /* We do now have the addressing mode in AM. Allocate a new CodeEntry
 461      * structure and initialize it.
 462      */
 463     E = NewCodeEntry (OPC->OPC, AM, Arg, Label, LI);
 464
 465     /* Return the new code entry */
 466     return E;
 467 }
 468
 469
 470
 471 /*****************************************************************************/
 472 /*                                   Code                                    */
 473 /*****************************************************************************/
 474
 475
 476
 477 CodeSeg* NewCodeSeg (const char* SegName, SymEntry* Func)
 478 /* Create a new code segment, initialize and return it */
 479 {
 480     unsigned I;
 481     const type* RetType;
 482
 483     /* Allocate memory */
 484     CodeSeg* S = xmalloc (sizeof (CodeSeg));
 485
 486     /* Initialize the fields */
 487     S->SegName  = xstrdup (SegName);
 488     S->Func     = Func;
 489     InitCollection (&S->Entries);
 490     InitCollection (&S->Labels);
 491     for (I = 0; I < sizeof(S->LabelHash) / sizeof(S->LabelHash[0]); ++I) {
 492         S->LabelHash[I] = 0;
 493     }
 494
 495     /* If we have a function given, get the return type of the function.
 496      * Assume ANY return type besides void will use the A and X registers.
 497      */
 498     if (S->Func && !IsTypeVoid ((RetType = GetFuncReturn (Func->Type)))) {
 499         if (SizeOf (RetType) == SizeOf (type_long)) {
 500             S->ExitRegs = REG_EAX;
 501         } else {
 502             S->ExitRegs = REG_AX;
 503         }
 504     } else {
 505         S->ExitRegs = REG_NONE;
 506     }
 507
 508     /* Return the new struct */
 509     return S;
 510 }
 511
 512
 513
 514 void CS_AddEntry (CodeSeg* S, struct CodeEntry* E)
 515 /* Add an entry to the given code segment */
 516 {
 517     /* Transfer the labels if we have any */
 518     CS_MoveLabelsToEntry (S, E);
 519
 520     /* Add the entry to the list of code entries in this segment */
 521     CollAppend (&S->Entries, E);
 522 }
 523
 524
 525
 526 void CS_AddVLine (CodeSeg* S, LineInfo* LI, const char* Format, va_list ap)
 527 /* Add a line to the given code segment */
 528 {
 529     const char* L;
 530     CodeEntry*  E;
 531     char        Token[IDENTSIZE+10];
 532
 533     /* Format the line */
 534     char Buf [256];
 535     xvsprintf (Buf, sizeof (Buf), Format, ap);
 536
 537     /* Skip whitespace */
 538     L = SkipSpace (Buf);
 539
 540     /* Check which type of instruction we have */
 541     E = 0;      /* Assume no insn created */
 542     switch (*L) {
 543
 544         case '\0':
 545             /* Empty line, just ignore it */
 546             break;
 547
 548         case ';':
 549             /* Comment or hint, ignore it for now */
 550             break;
 551
 552         case '.':
 553             /* Control instruction */
 554             ReadToken (L, " \t", Token, sizeof (Token));
 555             Error ("ASM code error: Pseudo instruction `%s' not supported", Token);
 556             break;
 557
 558         default:
 559             E = ParseInsn (S, LI, L);
 560             break;
 561     }
 562
 563     /* If we have a code entry, transfer the labels and insert it */
 564     if (E) {
 565         CS_AddEntry (S, E);
 566     }
 567 }
 568
 569
 570
 571 void CS_AddLine (CodeSeg* S, LineInfo* LI, const char* Format, ...)
 572 /* Add a line to the given code segment */
 573 {
 574     va_list ap;
 575     va_start (ap, Format);
 576     CS_AddVLine (S, LI, Format, ap);
 577     va_end (ap);
 578 }
 579
 580
 581
 582 void CS_InsertEntry (CodeSeg* S, struct CodeEntry* E, unsigned Index)
 583 /* Insert the code entry at the index given. Following code entries will be
 584  * moved to slots with higher indices.
 585  */
 586 {
 587     /* Insert the entry into the collection */
 588     CollInsert (&S->Entries, E, Index);
 589 }
 590
 591
 592
 593 void CS_DelEntry (CodeSeg* S, unsigned Index)
 594 /* Delete an entry from the code segment. This includes moving any associated
 595  * labels, removing references to labels and even removing the referenced labels
 596  * if the reference count drops to zero.
 597  * Note: Labels are moved forward if possible, that is, they are moved to the
 598  * next insn (not the preceeding one).
 599  */
 600 {
 601     /* Get the code entry for the given index */
 602     CodeEntry* E = CS_GetEntry (S, Index);
 603
 604     /* If the entry has a labels, we have to move this label to the next insn.
 605      * If there is no next insn, move the label into the code segement label
 606      * pool. The operation is further complicated by the fact that the next
 607      * insn may already have a label. In that case change all reference to
 608      * this label and delete the label instead of moving it.
 609      */
 610     unsigned Count = CE_GetLabelCount (E);
 611     if (Count > 0) {
 612
 613         /* The instruction has labels attached. Check if there is a next
 614          * instruction.
 615          */
 616         if (Index == CS_GetEntryCount (S)-1) {
 617
 618             /* No next instruction, move to the codeseg label pool */
 619             CS_MoveLabelsToPool (S, E);
 620
 621         } else {
 622
 623             /* There is a next insn, get it */
 624             CodeEntry* N = CS_GetEntry (S, Index+1);
 625
 626             /* Move labels to the next entry */
 627             CS_MoveLabels (S, E, N);
 628
 629         }
 630     }
 631
 632     /* If this insn references a label, remove the reference. And, if the
 633      * the reference count for this label drops to zero, remove this label.
 634      */
 635     if (E->JumpTo) {
 636         /* Remove the reference */
 637         CS_RemoveLabelRef (S, E);
 638     }
 639
 640     /* Delete the pointer to the insn */
 641     CollDelete (&S->Entries, Index);
 642
 643     /* Delete the instruction itself */
 644     FreeCodeEntry (E);
 645 }
 646
 647
 648
 649 void CS_DelEntries (CodeSeg* S, unsigned Start, unsigned Count)
 650 /* Delete a range of code entries. This includes removing references to labels,
 651  * labels attached to the entries and so on.
 652  */
 653 {
 654     /* Start deleting the entries from the rear, because this involves less
 655      * memory moving.
 656      */
 657     while (Count--) {
 658         CS_DelEntry (S, Start + Count);
 659     }
 660 }
 661
 662
 663
 664 void CS_MoveEntries (CodeSeg* S, unsigned Start, unsigned Count, unsigned NewPos)
 665 /* Move a range of entries from one position to another. Start is the index
 666  * of the first entry to move, Count is the number of entries and NewPos is
 667  * the index of the target entry. The entry with the index Start will later
 668  * have the index NewPos. All entries with indices NewPos and above are
 669  * moved to higher indices. If the code block is moved to the end of the
 670  * current code, and if pending labels exist, these labels will get attached
 671  * to the first instruction of the moved block (the first one after the
 672  * current code end)
 673  */
 674 {
 675     /* If NewPos is at the end of the code segment, move any labels from the
 676      * label pool to the first instruction of the moved range.
 677      */
 678     if (NewPos == CS_GetEntryCount (S)) {
 679         CS_MoveLabelsToEntry (S, CS_GetEntry (S, Start));
 680     }
 681
 682     /* Move the code block to the destination */
 683     CollMoveMultiple (&S->Entries, Start, Count, NewPos);
 684 }
 685
 686
 687
 688 struct CodeEntry* CS_GetPrevEntry (CodeSeg* S, unsigned Index)
 689 /* Get the code entry preceeding the one with the index Index. If there is no
 690  * preceeding code entry, return NULL.
 691  */
 692 {
 693     if (Index == 0) {
 694         /* This is the first entry */
 695         return 0;
 696     } else {
 697         /* Previous entry available */
 698         return CollAtUnchecked (&S->Entries, Index-1);
 699     }
 700 }
 701
 702
 703
 704 struct CodeEntry* CS_GetNextEntry (CodeSeg* S, unsigned Index)
 705 /* Get the code entry following the one with the index Index. If there is no
 706  * following code entry, return NULL.
 707  */
 708 {
 709     if (Index >= CollCount (&S->Entries)-1) {
 710         /* This is the last entry */
 711         return 0;
 712     } else {
 713         /* Code entries left */
 714         return CollAtUnchecked (&S->Entries, Index+1);
 715     }
 716 }
 717
 718
 719
 720 int CS_GetEntries (CodeSeg* S, struct CodeEntry** List,
 721                    unsigned Start, unsigned Count)
 722 /* Get Count code entries into List starting at index start. Return true if
 723  * we got the lines, return false if not enough lines were available.
 724  */
 725 {
 726     /* Check if enough entries are available */
 727     if (Start + Count > CollCount (&S->Entries)) {
 728         return 0;
 729     }
 730
 731     /* Copy the entries */
 732     while (Count--) {
 733         *List++ = CollAtUnchecked (&S->Entries, Start++);
 734     }
 735
 736     /* We have the entries */
 737     return 1;
 738 }
 739
 740
 741
 742 unsigned CS_GetEntryIndex (CodeSeg* S, struct CodeEntry* E)
 743 /* Return the index of a code entry */
 744 {
 745     int Index = CollIndex (&S->Entries, E);
 746     CHECK (Index >= 0);
 747     return Index;
 748 }
 749
 750
 751
 752 int CS_RangeHasLabel (CodeSeg* S, unsigned Start, unsigned Count)
 753 /* Return true if any of the code entries in the given range has a label
 754  * attached. If the code segment does not span the given range, check the
 755  * possible span instead.
 756  */
 757 {
 758     unsigned EntryCount = CS_GetEntryCount(S);
 759
 760     /* Adjust count. We expect at least Start to be valid. */
 761     CHECK (Start < EntryCount);
 762     if (Start + Count > EntryCount) {
 763         Count = EntryCount - Start;
 764     }
 765
 766     /* Check each entry. Since we have validated the index above, we may
 767      * use the unchecked access function in the loop which is faster.
 768      */
 769     while (Count--) {
 770         const CodeEntry* E = CollAtUnchecked (&S->Entries, Start++);
 771         if (CE_HasLabel (E)) {
 772             return 1;
 773         }
 774     }
 775
 776     /* No label in the complete range */
 777     return 0;
 778 }
 779
 780
 781
 782 CodeLabel* CS_AddLabel (CodeSeg* S, const char* Name)
 783 /* Add a code label for the next instruction to follow */
 784 {
 785     return CS_AddLabelInternal (S, Name, Internal);
 786 }
 787
 788
 789
 790 CodeLabel* CS_GenLabel (CodeSeg* S, struct CodeEntry* E)
 791 /* If the code entry E does already have a label, return it. Otherwise
 792  * create a new label, attach it to E and return it.
 793  */
 794 {
 795     CodeLabel* L;
 796
 797     if (CE_HasLabel (E)) {
 798
 799         /* Get the label from this entry */
 800         L = CE_GetLabel (E, 0);
 801
 802     } else {
 803
 804         /* Get a new name */
 805         const char* Name = LocalLabelName (GetLocalLabel ());
 806
 807         /* Generate the hash over the name */
 808         unsigned Hash = HashStr (Name) % CS_LABEL_HASH_SIZE;
 809
 810         /* Create a new label */
 811         L = CS_NewCodeLabel (S, Name, Hash);
 812
 813         /* Attach this label to the code entry */
 814         CE_AttachLabel (E, L);
 815
 816     }
 817
 818     /* Return the label */
 819     return L;
 820 }
 821
 822
 823
 824 void CS_DelLabel (CodeSeg* S, CodeLabel* L)
 825 /* Remove references from this label and delete it. */
 826 {
 827     unsigned Count, I;
 828
 829     /* First, remove the label from the hash chain */
 830     CS_RemoveLabelFromHash (S, L);
 831
 832     /* Remove references from insns jumping to this label */
 833     Count = CollCount (&L->JumpFrom);
 834     for (I = 0; I < Count; ++I) {
 835         /* Get the insn referencing this label */
 836         CodeEntry* E = CollAt (&L->JumpFrom, I);
 837         /* Remove the reference */
 838         E->JumpTo = 0;
 839     }
 840     CollDeleteAll (&L->JumpFrom);
 841
 842     /* Remove the reference to the owning instruction if it has one. The
 843      * function may be called for a label without an owner when deleting
 844      * unfinished parts of the code. This is unfortunate since it allows
 845      * errors to slip through.
 846      */
 847     if (L->Owner) {
 848         CollDeleteItem (&L->Owner->Labels, L);
 849     }
 850
 851     /* All references removed, delete the label itself */
 852     FreeCodeLabel (L);
 853 }
 854
 855
 856
 857 void CS_MergeLabels (CodeSeg* S)
 858 /* Merge code labels. That means: For each instruction, remove all labels but
 859  * one and adjust references accordingly.
 860  */
 861 {
 862     unsigned I;
 863     unsigned J;
 864
 865     /* First, remove all labels from the label symbol table that don't have an
 866      * owner (this means that they are actually external labels but we didn't
 867      * know that previously since they may have also been forward references).
 868      */
 869     for (I = 0; I < CS_LABEL_HASH_SIZE; ++I) {
 870
 871         /* Get the first label in this hash chain */
 872         CodeLabel** L = &S->LabelHash[I];
 873         while (*L) {
 874             if ((*L)->Owner == 0) {
 875
 876                 /* The label does not have an owner, remove it from the chain */
 877                 CodeLabel* X = *L;
 878                 *L = X->Next;
 879
 880                 /* Cleanup any entries jumping to this label */
 881                 for (J = 0; J < CL_GetRefCount (X); ++J) {
 882                     /* Get the entry referencing this label */
 883                     CodeEntry* E = CL_GetRef (X, J);
 884                     /* And remove the reference */
 885                     E->JumpTo = 0;
 886                 }
 887
 888                 /* Print some debugging output */
 889                 if (Debug) {
 890                     printf ("Removing unused global label `%s'", X->Name);
 891                 }
 892
 893                 /* And free the label */
 894                 FreeCodeLabel (X);
 895             } else {
 896                 /* Label is owned, point to next code label pointer */
 897                 L = &((*L)->Next);
 898             }
 899         }
 900     }
 901
 902     /* Walk over all code entries */
 903     for (I = 0; I < CS_GetEntryCount (S); ++I) {
 904
 905         CodeLabel* RefLab;
 906         unsigned   J;
 907
 908         /* Get a pointer to the next entry */
 909         CodeEntry* E = CS_GetEntry (S, I);
 910
 911         /* If this entry has zero labels, continue with the next one */
 912         unsigned LabelCount = CE_GetLabelCount (E);
 913         if (LabelCount == 0) {
 914             continue;
 915         }
 916
 917         /* We have at least one label. Use the first one as reference label. */
 918         RefLab = CE_GetLabel (E, 0);
 919
 920         /* Walk through the remaining labels and change references to these
 921          * labels to a reference to the one and only label. Delete the labels
 922          * that are no longer used. To increase performance, walk backwards
 923          * through the list.
 924          */
 925         for (J = LabelCount-1; J >= 1; --J) {
 926
 927             /* Get the next label */
 928             CodeLabel* L = CE_GetLabel (E, J);
 929
 930             /* Move all references from this label to the reference label */
 931             CL_MoveRefs (L, RefLab);
 932
 933             /* Remove the label completely. */
 934             CS_DelLabel (S, L);
 935         }
 936
 937         /* The reference label is the only remaining label. Check if there
 938          * are any references to this label, and delete it if this is not
 939          * the case.
 940          */
 941         if (CollCount (&RefLab->JumpFrom) == 0) {
 942             /* Delete the label */
 943             CS_DelLabel (S, RefLab);
 944         }
 945     }
 946 }
 947
 948
 949
 950 void CS_MoveLabels (CodeSeg* S, struct CodeEntry* Old, struct CodeEntry* New)
 951 /* Move all labels from Old to New. The routine will move the labels itself
 952  * if New does not have any labels, and move references if there is at least
 953  * a label for new. If references are moved, the old label is deleted
 954  * afterwards.
 955  */
 956 {
 957     /* Get the number of labels to move */
 958     unsigned OldLabelCount = CE_GetLabelCount (Old);
 959
 960     /* Does the new entry have itself a label? */
 961     if (CE_HasLabel (New)) {
 962
 963         /* The new entry does already have a label - move references */
 964         CodeLabel* NewLabel = CE_GetLabel (New, 0);
 965         while (OldLabelCount--) {
 966
 967             /* Get the next label */
 968             CodeLabel* OldLabel = CE_GetLabel (Old, OldLabelCount);
 969
 970             /* Move references */
 971             CL_MoveRefs (OldLabel, NewLabel);
 972
 973             /* Delete the label */
 974             CS_DelLabel (S, OldLabel);
 975
 976         }
 977
 978     } else {
 979
 980         /* The new entry does not have a label, just move them */
 981         while (OldLabelCount--) {
 982
 983             /* Move the label to the new entry */
 984             CE_MoveLabel (CE_GetLabel (Old, OldLabelCount), New);
 985
 986         }
 987
 988     }
 989 }
 990
 991
 992
 993 void CS_RemoveLabelRef (CodeSeg* S, struct CodeEntry* E)
 994 /* Remove the reference between E and the label it jumps to. The reference
 995  * will be removed on both sides and E->JumpTo will be 0 after that. If
 996  * the reference was the only one for the label, the label will get
 997  * deleted.
 998  */
 999 {
1000     /* Get a pointer to the label and make sure it exists */
1001     CodeLabel* L = E->JumpTo;
1002     CHECK (L != 0);
1003
1004     /* Delete the entry from the label */
1005     CollDeleteItem (&L->JumpFrom, E);
1006
1007     /* The entry jumps no longer to L */
1008     E->JumpTo = 0;
1009
1010     /* If there are no more references, delete the label */
1011     if (CollCount (&L->JumpFrom) == 0) {
1012         CS_DelLabel (S, L);
1013     }
1014 }
1015
1016
1017
1018 void CS_MoveLabelRef (CodeSeg* S, struct CodeEntry* E, CodeLabel* L)
1019 /* Change the reference of E to L instead of the current one. If this
1020  * was the only reference to the old label, the old label will get
1021  * deleted.
1022  */
1023 {
1024     /* Get the old label */
1025     CodeLabel* OldLabel = E->JumpTo;
1026
1027     /* Be sure that code entry references a label */
1028     PRECONDITION (OldLabel != 0);
1029
1030     /* Remove the reference to our label */
1031     CS_RemoveLabelRef (S, E);
1032
1033     /* Use the new label */
1034     CL_AddRef (L, E);
1035 }
1036
1037
1038
1039 void CS_DelCodeAfter (CodeSeg* S, unsigned Last)
1040 /* Delete all entries including the given one */
1041 {
1042     /* Get the number of entries in this segment */
1043     unsigned Count = CS_GetEntryCount (S);
1044
1045     /* First pass: Delete all references to labels. If the reference count
1046      * for a label drops to zero, delete it.
1047      */
1048     unsigned C = Count;
1049     while (Last < C--) {
1050
1051         /* Get the next entry */
1052         CodeEntry* E = CS_GetEntry (S, C);
1053
1054         /* Check if this entry has a label reference */
1055         if (E->JumpTo) {
1056             /* If the label is a label in the label pool and this is the last
1057              * reference to the label, remove the label from the pool.
1058              */
1059             CodeLabel* L = E->JumpTo;
1060             int Index = CollIndex (&S->Labels, L);
1061             if (Index >= 0 && CollCount (&L->JumpFrom) == 1) {
1062                 /* Delete it from the pool */
1063                 CollDelete (&S->Labels, Index);
1064             }
1065
1066             /* Remove the reference to the label */
1067             CS_RemoveLabelRef (S, E);
1068         }
1069
1070     }
1071
1072     /* Second pass: Delete the instructions. If a label attached to an
1073      * instruction still has references, it must be references from outside
1074      * the deleted area. Don't delete the label in this case, just make it
1075      * ownerless and move it to the label pool.
1076      */
1077     C = Count;
1078     while (Last < C--) {
1079
1080         /* Get the next entry */
1081         CodeEntry* E = CS_GetEntry (S, C);
1082
1083         /* Check if this entry has a label attached */
1084         if (CE_HasLabel (E)) {
1085             /* Move the labels to the pool and clear the owner pointer */
1086             CS_MoveLabelsToPool (S, E);
1087         }
1088
1089         /* Delete the pointer to the entry */
1090         CollDelete (&S->Entries, C);
1091
1092         /* Delete the entry itself */
1093         FreeCodeEntry (E);
1094     }
1095 }
1096
1097
1098
1099 void CS_OutputPrologue (const CodeSeg* S, FILE* F)
1100 /* If the given code segment is a code segment for a function, output the
1101  * assembler prologue into the file. That is: Output a comment header, switch
1102  * to the correct segment and enter the local function scope. If the code
1103  * segment is global, do nothing.
1104  */
1105 {
1106     /* Get the function associated with the code segment */
1107     SymEntry* Func = S->Func;
1108
1109     /* If the code segment is associated with a function, print a function
1110      * header and enter a local scope. Be sure to switch to the correct
1111      * segment before outputing the function label.
1112      */
1113     if (Func) {
1114         CS_PrintFunctionHeader (S, F);
1115         fprintf (F, ".segment\t\"%s\"\n\n.proc\t_%s\n\n", S->SegName, Func->Name);
1116     }
1117
1118 }
1119
1120
1121
1122 void CS_OutputEpilogue (const CodeSeg* S, FILE* F)
1123 /* If the given code segment is a code segment for a function, output the
1124  * assembler epilogue into the file. That is: Close the local function scope.
1125  */
1126 {
1127     if (S->Func) {
1128         fprintf (F, "\n.endproc\n\n");
1129     }
1130 }
1131
1132
1133
1134 void CS_Output (const CodeSeg* S, FILE* F)
1135 /* Output the code segment data to a file */
1136 {
1137     unsigned I;
1138     const LineInfo* LI;
1139
1140     /* Get the number of entries in this segment */
1141     unsigned Count = CS_GetEntryCount (S);
1142
1143     /* If the code segment is empty, bail out here */
1144     if (Count == 0) {
1145         return;
1146     }
1147
1148     /* Output the segment directive */
1149     fprintf (F, ".segment\t\"%s\"\n\n", S->SegName);
1150
1151     /* Output all entries, prepended by the line information if it has changed */
1152     LI = 0;
1153     for (I = 0; I < Count; ++I) {
1154         /* Get the next entry */
1155         const CodeEntry* E = CollConstAt (&S->Entries, I);
1156         /* Check if the line info has changed. If so, output the source line
1157          * if the option is enabled and output debug line info if the debug
1158          * option is enabled.
1159          */
1160         if (E->LI != LI) {
1161             /* Line info has changed, remember the new line info */
1162             LI = E->LI;
1163
1164             /* Add the source line as a comment */
1165             if (AddSource) {
1166                 fprintf (F, ";\n; %s\n;\n", LI->Line);
1167             }
1168
1169             /* Add line debug info */
1170             if (DebugInfo) {
1171                 fprintf (F, "\t.dbg\tline, \"%s\", %u\n",
1172                          GetInputName (LI), GetInputLine (LI));
1173             }
1174         }
1175         /* Output the code */
1176         CE_Output (E, F);
1177     }
1178
1179     /* If debug info is enabled, terminate the last line number information */
1180     if (DebugInfo) {
1181         fprintf (F, "\t.dbg\tline\n");
1182     }
1183 }
1184
1185
1186
1187 void CS_FreeRegInfo (CodeSeg* S)
1188 /* Free register infos for all instructions */
1189 {
1190     unsigned I;
1191     for (I = 0; I < CS_GetEntryCount (S); ++I) {
1192         CE_FreeRegInfo (CS_GetEntry(S, I));
1193     }
1194 }
1195
1196
1197
1198 void CS_GenRegInfo (CodeSeg* S)
1199 /* Generate register infos for all instructions */
1200 {
1201     unsigned I;
1202     RegContents Regs;           /* Initial register contents */
1203     RegContents* CurrentRegs;   /* Current register contents */
1204     int WasJump;                /* True if last insn was a jump */
1205     int Done;                   /* All runs done flag */
1206
1207     /* Be sure to delete all register infos */
1208     CS_FreeRegInfo (S);
1209
1210     /* We may need two runs to get back references right */
1211     do {
1212
1213         /* Assume we're done after this run */
1214         Done = 1;
1215
1216         /* On entry, the register contents are unknown */
1217         RC_Invalidate (&Regs);
1218         CurrentRegs = &Regs;
1219
1220         /* Walk over all insns and note just the changes from one insn to the
1221          * next one.
1222          */
1223         WasJump = 0;
1224         for (I = 0; I < CS_GetEntryCount (S); ++I) {
1225
1226             CodeEntry* P;
1227
1228             /* Get the next instruction */
1229             CodeEntry* E = CollAtUnchecked (&S->Entries, I);
1230
1231             /* If the instruction has a label, we need some special handling */
1232             unsigned LabelCount = CE_GetLabelCount (E);
1233             if (LabelCount > 0) {
1234
1235                 /* Loop over all entry points that jump here. If these entry
1236                  * points already have register info, check if all values are
1237                  * known and identical. If all values are identical, and the
1238                  * preceeding instruction was not an unconditional branch, check
1239                  * if the register value on exit of the preceeding instruction
1240                  * is also identical. If all these values are identical, the
1241                  * value of a register is known, otherwise it is unknown.
1242                  */
1243                 CodeLabel* Label = CE_GetLabel (E, 0);
1244                 unsigned Entry;
1245                 if (WasJump) {
1246                     /* Preceeding insn was an unconditional branch */
1247                     CodeEntry* J = CL_GetRef(Label, 0);
1248                     if (J->RI) {
1249                         Regs = J->RI->Out2;
1250                     } else {
1251                         RC_Invalidate (&Regs);
1252                     }
1253                     Entry = 1;
1254                 } else {
1255                     Regs = *CurrentRegs;
1256                     Entry = 0;
1257                 }
1258
1259                 while (Entry < CL_GetRefCount (Label)) {
1260                     /* Get this entry */
1261                     CodeEntry* J = CL_GetRef (Label, Entry);
1262                     if (J->RI == 0) {
1263                         /* No register info for this entry. This means that the
1264                          * instruction that jumps here is at higher addresses and
1265                          * the jump is a backward jump. We need a second run to
1266                          * get the register info right in this case. Until then,
1267                          * assume unknown register contents.
1268                          */
1269                         Done = 0;
1270                         RC_Invalidate (&Regs);
1271                         break;
1272                     }
1273                     if (J->RI->Out2.RegA != Regs.RegA) {
1274                         Regs.RegA = -1;
1275                     }
1276                     if (J->RI->Out2.RegX != Regs.RegX) {
1277                         Regs.RegX = -1;
1278                     }
1279                     if (J->RI->Out2.RegY != Regs.RegY) {
1280                         Regs.RegY = -1;
1281                     }
1282                     if (J->RI->Out2.SRegLo != Regs.SRegLo) {
1283                         Regs.SRegLo = -1;
1284                     }
1285                     if (J->RI->Out2.SRegHi != Regs.SRegHi) {
1286                         Regs.SRegHi = -1;
1287                     }
1288                     ++Entry;
1289                 }
1290
1291                 /* Use this register info */
1292                 CurrentRegs = &Regs;
1293
1294             }
1295
1296             /* Generate register info for this instruction */
1297             CE_GenRegInfo (E, CurrentRegs);
1298
1299             /* Remember for the next insn if this insn was an uncondition branch */
1300             WasJump = (E->Info & OF_UBRA) != 0;
1301
1302             /* Output registers for this insn are input for the next */
1303             CurrentRegs = &E->RI->Out;
1304
1305             /* If this insn is a branch on zero flag, we may have more info on
1306              * register contents for one of both flow directions, but only if
1307              * there is a previous instruction.
1308              */
1309             if ((E->Info & OF_ZBRA) != 0 && (P = CS_GetPrevEntry (S, I)) != 0) {
1310
1311                 /* Get the branch condition */
1312                 bc_t BC = GetBranchCond (E->OPC);
1313
1314                 /* Check the previous instruction */
1315                 switch (P->OPC) {
1316
1317                     case OP65_ADC:
1318                     case OP65_AND:
1319                     case OP65_DEA:
1320                     case OP65_EOR:
1321                     case OP65_INA:
1322                     case OP65_LDA:
1323                     case OP65_ORA:
1324                     case OP65_PLA:
1325                     case OP65_SBC:
1326                         /* A is zero in one execution flow direction */
1327                         if (BC == BC_EQ) {
1328                             E->RI->Out2.RegA = 0;
1329                         } else {
1330                             E->RI->Out.RegA = 0;
1331                         }
1332                         break;
1333
1334                     case OP65_CMP:
1335                         /* If this is an immidiate compare, the A register has
1336                          * the value of the compare later.
1337                          */
1338                         if (CE_KnownImm (P)) {
1339                             if (BC == BC_EQ) {
1340                                 E->RI->Out2.RegA = (unsigned char)P->Num;
1341                             } else {
1342                                 E->RI->Out.RegA = (unsigned char)P->Num;
1343                             }
1344                         }
1345                         break;
1346
1347                     case OP65_CPX:
1348                         /* If this is an immidiate compare, the X register has
1349                          * the value of the compare later.
1350                          */
1351                         if (CE_KnownImm (P)) {
1352                             if (BC == BC_EQ) {
1353                                 E->RI->Out2.RegX = (unsigned char)P->Num;
1354                             } else {
1355                                 E->RI->Out.RegX = (unsigned char)P->Num;
1356                             }
1357                         }
1358                         break;
1359
1360                     case OP65_CPY:
1361                         /* If this is an immidiate compare, the Y register has
1362                          * the value of the compare later.
1363                          */
1364                         if (CE_KnownImm (P)) {
1365                             if (BC == BC_EQ) {
1366                                 E->RI->Out2.RegY = (unsigned char)P->Num;
1367                             } else {
1368                                 E->RI->Out.RegY = (unsigned char)P->Num;
1369                             }
1370                         }
1371                         break;
1372
1373                     case OP65_DEX:
1374                     case OP65_INX:
1375                     case OP65_LDX:
1376                     case OP65_PLX:
1377                         /* X is zero in one execution flow direction */
1378                         if (BC == BC_EQ) {
1379                             E->RI->Out2.RegX = 0;
1380                         } else {
1381                             E->RI->Out.RegX = 0;
1382                         }
1383                         break;
1384
1385                     case OP65_DEY:
1386                     case OP65_INY:
1387                     case OP65_LDY:
1388                     case OP65_PLY:
1389                         /* X is zero in one execution flow direction */
1390                         if (BC == BC_EQ) {
1391                             E->RI->Out2.RegY = 0;
1392                         } else {
1393                             E->RI->Out.RegY = 0;
1394                         }
1395                         break;
1396
1397                     case OP65_TAX:
1398                     case OP65_TXA:
1399                         /* If the branch is a beq, both A and X are zero at the
1400                          * branch target, otherwise they are zero at the next
1401                          * insn.
1402                          */
1403                         if (BC == BC_EQ) {
1404                             E->RI->Out2.RegA = E->RI->Out2.RegX = 0;
1405                         } else {
1406                             E->RI->Out.RegA = E->RI->Out.RegX = 0;
1407                         }
1408                         break;
1409
1410                     case OP65_TAY:
1411                     case OP65_TYA:
1412                         /* If the branch is a beq, both A and Y are zero at the
1413                          * branch target, otherwise they are zero at the next
1414                          * insn.
1415                          */
1416                         if (BC == BC_EQ) {
1417                             E->RI->Out2.RegA = E->RI->Out2.RegY = 0;
1418                         } else {
1419                             E->RI->Out.RegA = E->RI->Out.RegY = 0;
1420                         }
1421                         break;
1422
1423                     default:
1424                         break;
1425
1426                 }
1427             }
1428         }
1429     } while (!Done);
1430
1431 }
1432
1433
1434