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  */
 598 {
 599     /* Get the code entry for the given index */
 600     CodeEntry* E = CS_GetEntry (S, Index);
 601
 602     /* If the entry has a labels, we have to move this label to the next insn.
 603      * If there is no next insn, move the label into the code segement label
 604      * pool. The operation is further complicated by the fact that the next
 605      * insn may already have a label. In that case change all reference to
 606      * this label and delete the label instead of moving it.
 607      */
 608     unsigned Count = CE_GetLabelCount (E);
 609     if (Count > 0) {
 610
 611         /* The instruction has labels attached. Check if there is a next
 612          * instruction.
 613          */
 614         if (Index == CS_GetEntryCount (S)-1) {
 615
 616             /* No next instruction, move to the codeseg label pool */
 617             CS_MoveLabelsToPool (S, E);
 618
 619         } else {
 620
 621             /* There is a next insn, get it */
 622             CodeEntry* N = CS_GetEntry (S, Index+1);
 623
 624             /* Move labels to the next entry */
 625             CS_MoveLabels (S, E, N);
 626
 627         }
 628     }
 629
 630     /* If this insn references a label, remove the reference. And, if the
 631      * the reference count for this label drops to zero, remove this label.
 632      */
 633     if (E->JumpTo) {
 634         /* Remove the reference */
 635         CS_RemoveLabelRef (S, E);
 636     }
 637
 638     /* Delete the pointer to the insn */
 639     CollDelete (&S->Entries, Index);
 640
 641     /* Delete the instruction itself */
 642     FreeCodeEntry (E);
 643 }
 644
 645
 646
 647 void CS_DelEntries (CodeSeg* S, unsigned Start, unsigned Count)
 648 /* Delete a range of code entries. This includes removing references to labels,
 649  * labels attached to the entries and so on.
 650  */
 651 {
 652     /* Start deleting the entries from the rear, because this involves less
 653      * memory moving.
 654      */
 655     while (Count--) {
 656         CS_DelEntry (S, Start + Count);
 657     }
 658 }
 659
 660
 661
 662 void CS_MoveEntries (CodeSeg* S, unsigned Start, unsigned Count, unsigned NewPos)
 663 /* Move a range of entries from one position to another. Start is the index
 664  * of the first entry to move, Count is the number of entries and NewPos is
 665  * the index of the target entry. The entry with the index Start will later
 666  * have the index NewPos. All entries with indices NewPos and above are
 667  * moved to higher indices. If the code block is moved to the end of the
 668  * current code, and if pending labels exist, these labels will get attached
 669  * to the first instruction of the moved block (the first one after the
 670  * current code end)
 671  */
 672 {
 673     /* If NewPos is at the end of the code segment, move any labels from the
 674      * label pool to the first instruction of the moved range.
 675      */
 676     if (NewPos == CS_GetEntryCount (S)) {
 677         CS_MoveLabelsToEntry (S, CS_GetEntry (S, Start));
 678     }
 679
 680     /* Move the code block to the destination */
 681     CollMoveMultiple (&S->Entries, Start, Count, NewPos);
 682 }
 683
 684
 685
 686 struct CodeEntry* CS_GetPrevEntry (CodeSeg* S, unsigned Index)
 687 /* Get the code entry preceeding the one with the index Index. If there is no
 688  * preceeding code entry, return NULL.
 689  */
 690 {
 691     if (Index == 0) {
 692         /* This is the first entry */
 693         return 0;
 694     } else {
 695         /* Previous entry available */
 696         return CollAtUnchecked (&S->Entries, Index-1);
 697     }
 698 }
 699
 700
 701
 702 struct CodeEntry* CS_GetNextEntry (CodeSeg* S, unsigned Index)
 703 /* Get the code entry following the one with the index Index. If there is no
 704  * following code entry, return NULL.
 705  */
 706 {
 707     if (Index >= CollCount (&S->Entries)-1) {
 708         /* This is the last entry */
 709         return 0;
 710     } else {
 711         /* Code entries left */
 712         return CollAtUnchecked (&S->Entries, Index+1);
 713     }
 714 }
 715
 716
 717
 718 int CS_GetEntries (CodeSeg* S, struct CodeEntry** List,
 719                    unsigned Start, unsigned Count)
 720 /* Get Count code entries into List starting at index start. Return true if
 721  * we got the lines, return false if not enough lines were available.
 722  */
 723 {
 724     /* Check if enough entries are available */
 725     if (Start + Count > CollCount (&S->Entries)) {
 726         return 0;
 727     }
 728
 729     /* Copy the entries */
 730     while (Count--) {
 731         *List++ = CollAtUnchecked (&S->Entries, Start++);
 732     }
 733
 734     /* We have the entries */
 735     return 1;
 736 }
 737
 738
 739
 740 unsigned CS_GetEntryIndex (CodeSeg* S, struct CodeEntry* E)
 741 /* Return the index of a code entry */
 742 {
 743     int Index = CollIndex (&S->Entries, E);
 744     CHECK (Index >= 0);
 745     return Index;
 746 }
 747
 748
 749
 750 int CS_RangeHasLabel (CodeSeg* S, unsigned Start, unsigned Count)
 751 /* Return true if any of the code entries in the given range has a label
 752  * attached. If the code segment does not span the given range, check the
 753  * possible span instead.
 754  */
 755 {
 756     unsigned EntryCount = CS_GetEntryCount(S);
 757
 758     /* Adjust count. We expect at least Start to be valid. */
 759     CHECK (Start < EntryCount);
 760     if (Start + Count > EntryCount) {
 761         Count = EntryCount - Start;
 762     }
 763
 764     /* Check each entry. Since we have validated the index above, we may
 765      * use the unchecked access function in the loop which is faster.
 766      */
 767     while (Count--) {
 768         const CodeEntry* E = CollAtUnchecked (&S->Entries, Start++);
 769         if (CE_HasLabel (E)) {
 770             return 1;
 771         }
 772     }
 773
 774     /* No label in the complete range */
 775     return 0;
 776 }
 777
 778
 779
 780 CodeLabel* CS_AddLabel (CodeSeg* S, const char* Name)
 781 /* Add a code label for the next instruction to follow */
 782 {
 783     return CS_AddLabelInternal (S, Name, Internal);
 784 }
 785
 786
 787
 788 CodeLabel* CS_GenLabel (CodeSeg* S, struct CodeEntry* E)
 789 /* If the code entry E does already have a label, return it. Otherwise
 790  * create a new label, attach it to E and return it.
 791  */
 792 {
 793     CodeLabel* L;
 794
 795     if (CE_HasLabel (E)) {
 796
 797         /* Get the label from this entry */
 798         L = CE_GetLabel (E, 0);
 799
 800     } else {
 801
 802         /* Get a new name */
 803         const char* Name = LocalLabelName (GetLocalLabel ());
 804
 805         /* Generate the hash over the name */
 806         unsigned Hash = HashStr (Name) % CS_LABEL_HASH_SIZE;
 807
 808         /* Create a new label */
 809         L = CS_NewCodeLabel (S, Name, Hash);
 810
 811         /* Attach this label to the code entry */
 812         CE_AttachLabel (E, L);
 813
 814     }
 815
 816     /* Return the label */
 817     return L;
 818 }
 819
 820
 821
 822 void CS_DelLabel (CodeSeg* S, CodeLabel* L)
 823 /* Remove references from this label and delete it. */
 824 {
 825     unsigned Count, I;
 826
 827     /* First, remove the label from the hash chain */
 828     CS_RemoveLabelFromHash (S, L);
 829
 830     /* Remove references from insns jumping to this label */
 831     Count = CollCount (&L->JumpFrom);
 832     for (I = 0; I < Count; ++I) {
 833         /* Get the insn referencing this label */
 834         CodeEntry* E = CollAt (&L->JumpFrom, I);
 835         /* Remove the reference */
 836         E->JumpTo = 0;
 837     }
 838     CollDeleteAll (&L->JumpFrom);
 839
 840     /* Remove the reference to the owning instruction if it has one. The
 841      * function may be called for a label without an owner when deleting
 842      * unfinished parts of the code. This is unfortunate since it allows
 843      * errors to slip through.
 844      */
 845     if (L->Owner) {
 846         CollDeleteItem (&L->Owner->Labels, L);
 847     }
 848
 849     /* All references removed, delete the label itself */
 850     FreeCodeLabel (L);
 851 }
 852
 853
 854
 855 void CS_MergeLabels (CodeSeg* S)
 856 /* Merge code labels. That means: For each instruction, remove all labels but
 857  * one and adjust references accordingly.
 858  */
 859 {
 860     unsigned I;
 861     unsigned J;
 862
 863     /* First, remove all labels from the label symbol table that don't have an
 864      * owner (this means that they are actually external labels but we didn't
 865      * know that previously since they may have also been forward references).
 866      */
 867     for (I = 0; I < CS_LABEL_HASH_SIZE; ++I) {
 868
 869         /* Get the first label in this hash chain */
 870         CodeLabel** L = &S->LabelHash[I];
 871         while (*L) {
 872             if ((*L)->Owner == 0) {
 873
 874                 /* The label does not have an owner, remove it from the chain */
 875                 CodeLabel* X = *L;
 876                 *L = X->Next;
 877
 878                 /* Cleanup any entries jumping to this label */
 879                 for (J = 0; J < CL_GetRefCount (X); ++J) {
 880                     /* Get the entry referencing this label */
 881                     CodeEntry* E = CL_GetRef (X, J);
 882                     /* And remove the reference */
 883                     E->JumpTo = 0;
 884                 }
 885
 886                 /* Print some debugging output */
 887                 if (Debug) {
 888                     printf ("Removing unused global label `%s'", X->Name);
 889                 }
 890
 891                 /* And free the label */
 892                 FreeCodeLabel (X);
 893             } else {
 894                 /* Label is owned, point to next code label pointer */
 895                 L = &((*L)->Next);
 896             }
 897         }
 898     }
 899
 900     /* Walk over all code entries */
 901     for (I = 0; I < CS_GetEntryCount (S); ++I) {
 902
 903         CodeLabel* RefLab;
 904         unsigned   J;
 905
 906         /* Get a pointer to the next entry */
 907         CodeEntry* E = CS_GetEntry (S, I);
 908
 909         /* If this entry has zero labels, continue with the next one */
 910         unsigned LabelCount = CE_GetLabelCount (E);
 911         if (LabelCount == 0) {
 912             continue;
 913         }
 914
 915         /* We have at least one label. Use the first one as reference label. */
 916         RefLab = CE_GetLabel (E, 0);
 917
 918         /* Walk through the remaining labels and change references to these
 919          * labels to a reference to the one and only label. Delete the labels
 920          * that are no longer used. To increase performance, walk backwards
 921          * through the list.
 922          */
 923         for (J = LabelCount-1; J >= 1; --J) {
 924
 925             /* Get the next label */
 926             CodeLabel* L = CE_GetLabel (E, J);
 927
 928             /* Move all references from this label to the reference label */
 929             CL_MoveRefs (L, RefLab);
 930
 931             /* Remove the label completely. */
 932             CS_DelLabel (S, L);
 933         }
 934
 935         /* The reference label is the only remaining label. Check if there
 936          * are any references to this label, and delete it if this is not
 937          * the case.
 938          */
 939         if (CollCount (&RefLab->JumpFrom) == 0) {
 940             /* Delete the label */
 941             CS_DelLabel (S, RefLab);
 942         }
 943     }
 944 }
 945
 946
 947
 948 void CS_MoveLabels (CodeSeg* S, struct CodeEntry* Old, struct CodeEntry* New)
 949 /* Move all labels from Old to New. The routine will move the labels itself
 950  * if New does not have any labels, and move references if there is at least
 951  * a label for new. If references are moved, the old label is deleted
 952  * afterwards.
 953  */
 954 {
 955     /* Get the number of labels to move */
 956     unsigned OldLabelCount = CE_GetLabelCount (Old);
 957
 958     /* Does the new entry have itself a label? */
 959     if (CE_HasLabel (New)) {
 960
 961         /* The new entry does already have a label - move references */
 962         CodeLabel* NewLabel = CE_GetLabel (New, 0);
 963         while (OldLabelCount--) {
 964
 965             /* Get the next label */
 966             CodeLabel* OldLabel = CE_GetLabel (Old, OldLabelCount);
 967
 968             /* Move references */
 969             CL_MoveRefs (OldLabel, NewLabel);
 970
 971             /* Delete the label */
 972             CS_DelLabel (S, OldLabel);
 973
 974         }
 975
 976     } else {
 977
 978         /* The new entry does not have a label, just move them */
 979         while (OldLabelCount--) {
 980
 981             /* Move the label to the new entry */
 982             CE_MoveLabel (CE_GetLabel (Old, OldLabelCount), New);
 983
 984         }
 985
 986     }
 987 }
 988
 989
 990
 991 void CS_RemoveLabelRef (CodeSeg* S, struct CodeEntry* E)
 992 /* Remove the reference between E and the label it jumps to. The reference
 993  * will be removed on both sides and E->JumpTo will be 0 after that. If
 994  * the reference was the only one for the label, the label will get
 995  * deleted.
 996  */
 997 {
 998     /* Get a pointer to the label and make sure it exists */
 999     CodeLabel* L = E->JumpTo;
1000     CHECK (L != 0);
1001
1002     /* Delete the entry from the label */
1003     CollDeleteItem (&L->JumpFrom, E);
1004
1005     /* The entry jumps no longer to L */
1006     E->JumpTo = 0;
1007
1008     /* If there are no more references, delete the label */
1009     if (CollCount (&L->JumpFrom) == 0) {
1010         CS_DelLabel (S, L);
1011     }
1012 }
1013
1014
1015
1016 void CS_MoveLabelRef (CodeSeg* S, struct CodeEntry* E, CodeLabel* L)
1017 /* Change the reference of E to L instead of the current one. If this
1018  * was the only reference to the old label, the old label will get
1019  * deleted.
1020  */
1021 {
1022     /* Get the old label */
1023     CodeLabel* OldLabel = E->JumpTo;
1024
1025     /* Be sure that code entry references a label */
1026     PRECONDITION (OldLabel != 0);
1027
1028     /* Remove the reference to our label */
1029     CS_RemoveLabelRef (S, E);
1030
1031     /* Use the new label */
1032     CL_AddRef (L, E);
1033 }
1034
1035
1036
1037 void CS_DelCodeAfter (CodeSeg* S, unsigned Last)
1038 /* Delete all entries including the given one */
1039 {
1040     /* Get the number of entries in this segment */
1041     unsigned Count = CS_GetEntryCount (S);
1042
1043     /* First pass: Delete all references to labels. If the reference count
1044      * for a label drops to zero, delete it.
1045      */
1046     unsigned C = Count;
1047     while (Last < C--) {
1048
1049         /* Get the next entry */
1050         CodeEntry* E = CS_GetEntry (S, C);
1051
1052         /* Check if this entry has a label reference */
1053         if (E->JumpTo) {
1054             /* If the label is a label in the label pool and this is the last
1055              * reference to the label, remove the label from the pool.
1056              */
1057             CodeLabel* L = E->JumpTo;
1058             int Index = CollIndex (&S->Labels, L);
1059             if (Index >= 0 && CollCount (&L->JumpFrom) == 1) {
1060                 /* Delete it from the pool */
1061                 CollDelete (&S->Labels, Index);
1062             }
1063
1064             /* Remove the reference to the label */
1065             CS_RemoveLabelRef (S, E);
1066         }
1067
1068     }
1069
1070     /* Second pass: Delete the instructions. If a label attached to an
1071      * instruction still has references, it must be references from outside
1072      * the deleted area. Don't delete the label in this case, just make it
1073      * ownerless and move it to the label pool.
1074      */
1075     C = Count;
1076     while (Last < C--) {
1077
1078         /* Get the next entry */
1079         CodeEntry* E = CS_GetEntry (S, C);
1080
1081         /* Check if this entry has a label attached */
1082         if (CE_HasLabel (E)) {
1083             /* Move the labels to the pool and clear the owner pointer */
1084             CS_MoveLabelsToPool (S, E);
1085         }
1086
1087         /* Delete the pointer to the entry */
1088         CollDelete (&S->Entries, C);
1089
1090         /* Delete the entry itself */
1091         FreeCodeEntry (E);
1092     }
1093 }
1094
1095
1096
1097 void CS_OutputPrologue (const CodeSeg* S, FILE* F)
1098 /* If the given code segment is a code segment for a function, output the
1099  * assembler prologue into the file. That is: Output a comment header, switch
1100  * to the correct segment and enter the local function scope. If the code
1101  * segment is global, do nothing.
1102  */
1103 {
1104     /* Get the function associated with the code segment */
1105     SymEntry* Func = S->Func;
1106
1107     /* If the code segment is associated with a function, print a function
1108      * header and enter a local scope. Be sure to switch to the correct
1109      * segment before outputing the function label.
1110      */
1111     if (Func) {
1112         CS_PrintFunctionHeader (S, F);
1113         fprintf (F, ".segment\t\"%s\"\n\n.proc\t_%s\n\n", S->SegName, Func->Name);
1114     }
1115
1116 }
1117
1118
1119
1120 void CS_OutputEpilogue (const CodeSeg* S, FILE* F)
1121 /* If the given code segment is a code segment for a function, output the
1122  * assembler epilogue into the file. That is: Close the local function scope.
1123  */
1124 {
1125     if (S->Func) {
1126         fprintf (F, "\n.endproc\n\n");
1127     }
1128 }
1129
1130
1131
1132 void CS_Output (const CodeSeg* S, FILE* F)
1133 /* Output the code segment data to a file */
1134 {
1135     unsigned I;
1136     const LineInfo* LI;
1137
1138     /* Get the number of entries in this segment */
1139     unsigned Count = CS_GetEntryCount (S);
1140
1141     /* If the code segment is empty, bail out here */
1142     if (Count == 0) {
1143         return;
1144     }
1145
1146     /* Output the segment directive */
1147     fprintf (F, ".segment\t\"%s\"\n\n", S->SegName);
1148
1149     /* Output all entries, prepended by the line information if it has changed */
1150     LI = 0;
1151     for (I = 0; I < Count; ++I) {
1152         /* Get the next entry */
1153         const CodeEntry* E = CollConstAt (&S->Entries, I);
1154         /* Check if the line info has changed. If so, output the source line
1155          * if the option is enabled and output debug line info if the debug
1156          * option is enabled.
1157          */
1158         if (E->LI != LI) {
1159             /* Line info has changed, remember the new line info */
1160             LI = E->LI;
1161
1162             /* Add the source line as a comment */
1163             if (AddSource) {
1164                 fprintf (F, ";\n; %s\n;\n", LI->Line);
1165             }
1166
1167             /* Add line debug info */
1168             if (DebugInfo) {
1169                 fprintf (F, "\t.dbg\tline, \"%s\", %u\n",
1170                          GetInputName (LI), GetInputLine (LI));
1171             }
1172         }
1173         /* Output the code */
1174         CE_Output (E, F);
1175     }
1176
1177     /* If debug info is enabled, terminate the last line number information */
1178     if (DebugInfo) {
1179         fprintf (F, "\t.dbg\tline\n");
1180     }
1181 }
1182
1183
1184
1185 void CS_FreeRegInfo (CodeSeg* S)
1186 /* Free register infos for all instructions */
1187 {
1188     unsigned I;
1189     for (I = 0; I < CS_GetEntryCount (S); ++I) {
1190         CE_FreeRegInfo (CS_GetEntry(S, I));
1191     }
1192 }
1193
1194
1195
1196 void CS_GenRegInfo (CodeSeg* S)
1197 /* Generate register infos for all instructions */
1198 {
1199     unsigned I;
1200     RegContents Regs;           /* Initial register contents */
1201     RegContents* CurrentRegs;   /* Current register contents */
1202     int WasJump;                /* True if last insn was a jump */
1203     int Done;                   /* All runs done flag */
1204
1205     /* Be sure to delete all register infos */
1206     CS_FreeRegInfo (S);
1207
1208     /* We may need two runs to get back references right */
1209     do {
1210
1211         /* Assume we're done after this run */
1212         Done = 1;
1213
1214         /* On entry, the register contents are unknown */
1215         RC_Invalidate (&Regs);
1216         CurrentRegs = &Regs;
1217
1218         /* Walk over all insns and note just the changes from one insn to the
1219          * next one.
1220          */
1221         WasJump = 0;
1222         for (I = 0; I < CS_GetEntryCount (S); ++I) {
1223
1224             CodeEntry* P;
1225
1226             /* Get the next instruction */
1227             CodeEntry* E = CollAtUnchecked (&S->Entries, I);
1228
1229             /* If the instruction has a label, we need some special handling */
1230             unsigned LabelCount = CE_GetLabelCount (E);
1231             if (LabelCount > 0) {
1232
1233                 /* Loop over all entry points that jump here. If these entry
1234                  * points already have register info, check if all values are
1235                  * known and identical. If all values are identical, and the
1236                  * preceeding instruction was not an unconditional branch, check
1237                  * if the register value on exit of the preceeding instruction
1238                  * is also identical. If all these values are identical, the
1239                  * value of a register is known, otherwise it is unknown.
1240                  */
1241                 CodeLabel* Label = CE_GetLabel (E, 0);
1242                 unsigned Entry;
1243                 if (WasJump) {
1244                     /* Preceeding insn was an unconditional branch */
1245                     CodeEntry* J = CL_GetRef(Label, 0);
1246                     if (J->RI) {
1247                         Regs = J->RI->Out2;
1248                     } else {
1249                         RC_Invalidate (&Regs);
1250                     }
1251                     Entry = 1;
1252                 } else {
1253                     Regs = *CurrentRegs;
1254                     Entry = 0;
1255                 }
1256
1257                 while (Entry < CL_GetRefCount (Label)) {
1258                     /* Get this entry */
1259                     CodeEntry* J = CL_GetRef (Label, Entry);
1260                     if (J->RI == 0) {
1261                         /* No register info for this entry. This means that the
1262                          * instruction that jumps here is at higher addresses and
1263                          * the jump is a backward jump. We need a second run to
1264                          * get the register info right in this case. Until then,
1265                          * assume unknown register contents.
1266                          */
1267                         Done = 0;
1268                         RC_Invalidate (&Regs);
1269                         break;
1270                     }
1271                     if (J->RI->Out2.RegA != Regs.RegA) {
1272                         Regs.RegA = -1;
1273                     }
1274                     if (J->RI->Out2.RegX != Regs.RegX) {
1275                         Regs.RegX = -1;
1276                     }
1277                     if (J->RI->Out2.RegY != Regs.RegY) {
1278                         Regs.RegY = -1;
1279                     }
1280                     if (J->RI->Out2.SRegLo != Regs.SRegLo) {
1281                         Regs.SRegLo = -1;
1282                     }
1283                     if (J->RI->Out2.SRegHi != Regs.SRegHi) {
1284                         Regs.SRegHi = -1;
1285                     }
1286                     ++Entry;
1287                 }
1288
1289                 /* Use this register info */
1290                 CurrentRegs = &Regs;
1291
1292             }
1293
1294             /* Generate register info for this instruction */
1295             CE_GenRegInfo (E, CurrentRegs);
1296
1297             /* Remember for the next insn if this insn was an uncondition branch */
1298             WasJump = (E->Info & OF_UBRA) != 0;
1299
1300             /* Output registers for this insn are input for the next */
1301             CurrentRegs = &E->RI->Out;
1302
1303             /* If this insn is a branch on zero flag, we may have more info on
1304              * register contents for one of both flow directions, but only if
1305              * there is a previous instruction.
1306              */
1307             if ((E->Info & OF_ZBRA) != 0 && (P = CS_GetPrevEntry (S, I)) != 0) {
1308
1309                 /* Get the branch condition */
1310                 bc_t BC = GetBranchCond (E->OPC);
1311
1312                 /* Check the previous instruction */
1313                 switch (P->OPC) {
1314
1315                     case OP65_ADC:
1316                     case OP65_AND:
1317                     case OP65_DEA:
1318                     case OP65_EOR:
1319                     case OP65_INA:
1320                     case OP65_LDA:
1321                     case OP65_ORA:
1322                     case OP65_PLA:
1323                     case OP65_SBC:
1324                         /* A is zero in one execution flow direction */
1325                         if (BC == BC_EQ) {
1326                             E->RI->Out2.RegA = 0;
1327                         } else {
1328                             E->RI->Out.RegA = 0;
1329                         }
1330                         break;
1331
1332                     case OP65_CMP:
1333                         /* If this is an immidiate compare, the A register has
1334                          * the value of the compare later.
1335                          */
1336                         if (CE_KnownImm (P)) {
1337                             if (BC == BC_EQ) {
1338                                 E->RI->Out2.RegA = (unsigned char)P->Num;
1339                             } else {
1340                                 E->RI->Out.RegA = (unsigned char)P->Num;
1341                             }
1342                         }
1343                         break;
1344
1345                     case OP65_CPX:
1346                         /* If this is an immidiate compare, the X register has
1347                          * the value of the compare later.
1348                          */
1349                         if (CE_KnownImm (P)) {
1350                             if (BC == BC_EQ) {
1351                                 E->RI->Out2.RegX = (unsigned char)P->Num;
1352                             } else {
1353                                 E->RI->Out.RegX = (unsigned char)P->Num;
1354                             }
1355                         }
1356                         break;
1357
1358                     case OP65_CPY:
1359                         /* If this is an immidiate compare, the Y register has
1360                          * the value of the compare later.
1361                          */
1362                         if (CE_KnownImm (P)) {
1363                             if (BC == BC_EQ) {
1364                                 E->RI->Out2.RegY = (unsigned char)P->Num;
1365                             } else {
1366                                 E->RI->Out.RegY = (unsigned char)P->Num;
1367                             }
1368                         }
1369                         break;
1370
1371                     case OP65_DEX:
1372                     case OP65_INX:
1373                     case OP65_LDX:
1374                     case OP65_PLX:
1375                         /* X is zero in one execution flow direction */
1376                         if (BC == BC_EQ) {
1377                             E->RI->Out2.RegX = 0;
1378                         } else {
1379                             E->RI->Out.RegX = 0;
1380                         }
1381                         break;
1382
1383                     case OP65_DEY:
1384                     case OP65_INY:
1385                     case OP65_LDY:
1386                     case OP65_PLY:
1387                         /* X is zero in one execution flow direction */
1388                         if (BC == BC_EQ) {
1389                             E->RI->Out2.RegY = 0;
1390                         } else {
1391                             E->RI->Out.RegY = 0;
1392                         }
1393                         break;
1394
1395                     case OP65_TAX:
1396                     case OP65_TXA:
1397                         /* If the branch is a beq, both A and X are zero at the
1398                          * branch target, otherwise they are zero at the next
1399                          * insn.
1400                          */
1401                         if (BC == BC_EQ) {
1402                             E->RI->Out2.RegA = E->RI->Out2.RegX = 0;
1403                         } else {
1404                             E->RI->Out.RegA = E->RI->Out.RegX = 0;
1405                         }
1406                         break;
1407
1408                     case OP65_TAY:
1409                     case OP65_TYA:
1410                         /* If the branch is a beq, both A and Y are zero at the
1411                          * branch target, otherwise they are zero at the next
1412                          * insn.
1413                          */
1414                         if (BC == BC_EQ) {
1415                             E->RI->Out2.RegA = E->RI->Out2.RegY = 0;
1416                         } else {
1417                             E->RI->Out.RegA = E->RI->Out.RegY = 0;
1418                         }
1419                         break;
1420
1421                     default:
1422                         break;
1423
1424                 }
1425             }
1426         }
1427     } while (!Done);
1428
1429 }
1430
1431
1432