git.sur5r.net Git - cc65/blob - src/ld65/expr.c

   1 /*****************************************************************************/
   2 /*                                                                           */
   3 /*                                  expr.c                                   */
   4 /*                                                                           */
   5 /*                 Expression evaluation for the ld65 linker                 */
   6 /*                                                                           */
   7 /*                                                                           */
   8 /*                                                                           */
   9 /* (C) 1998-2000 Ullrich von Bassewitz                                       */
  10 /*               Wacholderweg 14                                             */
  11 /*               D-70597 Stuttgart                                           */
  12 /* EMail:        uz@musoftware.de                                            */
  13 /*                                                                           */
  14 /*                                                                           */
  15 /* This software is provided 'as-is', without any expressed or implied       */
  16 /* warranty.  In no event will the authors be held liable for any damages    */
  17 /* arising from the use of this software.                                    */
  18 /*                                                                           */
  19 /* Permission is granted to anyone to use this software for any purpose,     */
  20 /* including commercial applications, and to alter it and redistribute it    */
  21 /* freely, subject to the following restrictions:                            */
  22 /*                                                                           */
  23 /* 1. The origin of this software must not be misrepresented; you must not   */
  24 /*    claim that you wrote the original software. If you use this software   */
  25 /*    in a product, an acknowledgment in the product documentation would be  */
  26 /*    appreciated but is not required.                                       */
  27 /* 2. Altered source versions must be plainly marked as such, and must not   */
  28 /*    be misrepresented as being the original software.                      */
  29 /* 3. This notice may not be removed or altered from any source              */
  30 /*    distribution.                                                          */
  31 /*                                                                           */
  32 /*****************************************************************************/
  33
  34
  35
  36 /* common */
  37 #include "exprdefs.h"
  38 #include "xmalloc.h"
  39
  40 /* ld65 */
  41 #include "global.h"
  42 #include "error.h"
  43 #include "fileio.h"
  44 #include "segments.h"
  45 #include "expr.h"
  46
  47
  48
  49 /*****************************************************************************/
  50 /*                                  Helpers                                  */
  51 /*****************************************************************************/
  52
  53
  54
  55 static ExprNode* NewExprNode (ObjData* O)
  56 /* Create a new expression node */
  57 {
  58     /* Allocate fresh memory */
  59     ExprNode* N = xmalloc (sizeof (ExprNode));
  60     N->Op       = EXPR_NULL;
  61     N->Left     = 0;
  62     N->Right    = 0;
  63     N->Obj      = O;
  64     N->V.Val    = 0;
  65
  66     return N;
  67 }
  68
  69
  70
  71 static void FreeExprNode (ExprNode* E)
  72 /* Free a node */
  73 {
  74     /* Free the memory */
  75     xfree (E);
  76 }
  77
  78
  79
  80 /*****************************************************************************/
  81 /*              Dump an expression tree on stdout for debugging              */
  82 /*****************************************************************************/
  83
  84
  85
  86 static void InternalDumpExpr (const ExprNode* Expr)
  87 /* Dump an expression in UPN */
  88 {
  89     if (Expr == 0) {
  90         return;
  91     }
  92     InternalDumpExpr (Expr->Left);
  93     InternalDumpExpr (Expr->Right);
  94
  95     switch (Expr->Op) {
  96
  97         case EXPR_LITERAL:
  98             printf (" $%04lX", Expr->V.Val & 0xFFFF);
  99             break;
 100
 101         case EXPR_SYMBOL:
 102             printf (" SYM");
 103             break;
 104
 105         case EXPR_SEGMENT:
 106             printf (" SEG");
 107             break;
 108
 109         case EXPR_PLUS:
 110             printf (" +");
 111             break;
 112
 113         case EXPR_MINUS:
 114             printf (" -");
 115             break;
 116
 117         case EXPR_MUL:
 118             printf (" *");
 119             break;
 120
 121         case EXPR_DIV:
 122             printf (" /");
 123             break;
 124
 125         case EXPR_MOD:
 126             printf (" %%");
 127             break;
 128
 129         case EXPR_OR:
 130             printf (" OR");
 131             break;
 132
 133         case EXPR_XOR:
 134             printf (" XOR");
 135             break;
 136
 137         case EXPR_AND:
 138             printf (" AND");
 139             break;
 140
 141         case EXPR_SHL:
 142             printf (" SHL");
 143             break;
 144
 145         case EXPR_SHR:
 146             printf (" SHR");
 147             break;
 148
 149         case EXPR_EQ:
 150             printf (" =");
 151             break;
 152
 153         case EXPR_NE:
 154             printf ("<>");
 155             break;
 156
 157         case EXPR_LT:
 158             printf (" <");
 159             break;
 160
 161         case EXPR_GT:
 162             printf (" >");
 163             break;
 164
 165         case EXPR_UNARY_MINUS:
 166             printf (" NEG");
 167             break;
 168
 169         case EXPR_NOT:
 170             printf (" ~");
 171             break;
 172
 173         case EXPR_LOBYTE:
 174             printf (" LO");
 175             break;
 176
 177         case EXPR_HIBYTE:
 178             printf (" HI");
 179             break;
 180
 181         case EXPR_SWAP:
 182             printf (" SWAP");
 183             break;
 184
 185         case EXPR_BAND:
 186             printf (" BOOL_AND");
 187             break;
 188
 189         case EXPR_BOR:
 190             printf (" BOOL_OR");
 191             break;
 192
 193         case EXPR_BXOR:
 194             printf (" BOOL_XOR");
 195             break;
 196
 197         case EXPR_BNOT:
 198             printf (" BOOL_NOT");
 199             break;
 200
 201         default:
 202             Internal ("Unknown Op type: %u", Expr->Op);
 203
 204     }
 205 }
 206
 207
 208
 209 void DumpExpr (const ExprNode* Expr)
 210 /* Dump an expression tree to stdout */
 211 {
 212     InternalDumpExpr (Expr);
 213     printf ("\n");
 214 }
 215
 216
 217
 218 /*****************************************************************************/
 219 /*                                   Code                                    */
 220 /*****************************************************************************/
 221
 222
 223
 224 void FreeExpr (ExprNode* Root)
 225 /* Free the expression, Root is pointing to. */
 226 {
 227     if (Root) {
 228         FreeExpr (Root->Left);
 229         FreeExpr (Root->Right);
 230         FreeExprNode (Root);
 231     }
 232 }
 233
 234
 235
 236 int IsConstExpr (ExprNode* Root)
 237 /* Return true if the given expression is a constant expression, that is, one
 238  * with no references to external symbols.
 239  */
 240 {
 241     int Const;
 242     Export* E;
 243
 244     if (EXPR_IS_LEAF (Root->Op)) {
 245         switch (Root->Op) {
 246
 247             case EXPR_LITERAL:
 248                 return 1;
 249
 250             case EXPR_SYMBOL:
 251                 /* Get the referenced export */
 252                 E = GetExprExport (Root);
 253                 /* If this export has a mark set, we've already encountered it.
 254                  * This means that the export is used to define it's own value,
 255                  * which in turn means, that we have a circular reference.
 256                  */
 257                 if (ExportHasMark (E)) {
 258                     Error ("Circular reference for symbol `%s', %s(%lu)",
 259                            E->Name, E->Obj->Files [E->Pos.Name], E->Pos.Line);
 260                     Const = 0;
 261                 } else {
 262                     MarkExport (E);
 263                     Const = IsConstExport (E);
 264                     UnmarkExport (E);
 265                 }
 266                 return Const;
 267
 268             default:
 269                 return 0;
 270
 271         }
 272     } else if (EXPR_IS_UNARY (Root->Op)) {
 273
 274         return IsConstExpr (Root->Left);
 275
 276     } else {
 277
 278         /* We must handle shortcut boolean expressions here */
 279         switch (Root->Op) {
 280
 281             case EXPR_BAND:
 282                 if (IsConstExpr (Root->Left)) {
 283                     /* lhs is const, if it is zero, don't eval right */
 284                     if (GetExprVal (Root->Left) == 0) {
 285                         return 1;
 286                     } else {
 287                         return IsConstExpr (Root->Right);
 288                     }
 289                 } else {
 290                     /* lhs not const --> tree not const */
 291                     return 0;
 292                 }
 293                 break;
 294
 295             case EXPR_BOR:
 296                 if (IsConstExpr (Root->Left)) {
 297                     /* lhs is const, if it is not zero, don't eval right */
 298                     if (GetExprVal (Root->Left) != 0) {
 299                         return 1;
 300                     } else {
 301                         return IsConstExpr (Root->Right);
 302                     }
 303                 } else {
 304                     /* lhs not const --> tree not const */
 305                     return 0;
 306                 }
 307                 break;
 308
 309             default:
 310                 /* All others are handled normal */
 311                 return IsConstExpr (Root->Left) && IsConstExpr (Root->Right);
 312         }
 313     }
 314 }
 315
 316
 317
 318 Import* GetExprImport (ExprNode* Expr)
 319 /* Get the import data structure for a symbol expression node */
 320 {
 321     /* Check that this is really a symbol */
 322     PRECONDITION (Expr->Op == EXPR_SYMBOL);
 323
 324     /* Return the import */
 325     return Expr->Obj->Imports [Expr->V.ImpNum];
 326 }
 327
 328
 329
 330 Export* GetExprExport (ExprNode* Expr)
 331 /* Get the exported symbol for a symbol expression node */
 332 {
 333     /* Check that this is really a symbol */
 334     PRECONDITION (Expr->Op == EXPR_SYMBOL);
 335
 336     /* Return the export */
 337     return Expr->Obj->Imports [Expr->V.ImpNum]->V.Exp;
 338 }
 339
 340
 341
 342 Section* GetExprSection (ExprNode* Expr)
 343 /* Get the segment for a segment expression node */
 344 {
 345     /* Check that this is really a segment node */
 346     PRECONDITION (Expr->Op == EXPR_SEGMENT);
 347
 348     /* Return the export */
 349     return Expr->Obj->Sections [Expr->V.SegNum];
 350 }
 351
 352
 353
 354 long GetExprVal (ExprNode* Expr)
 355 /* Get the value of a constant expression */
 356 {
 357     long Right, Left, Val;
 358     Section* S;
 359     Export* E;
 360
 361     switch (Expr->Op) {
 362
 363         case EXPR_LITERAL:
 364             return Expr->V.Val;
 365
 366         case EXPR_SYMBOL:
 367             /* Get the referenced export */
 368             E = GetExprExport (Expr);
 369             /* If this export has a mark set, we've already encountered it.
 370              * This means that the export is used to define it's own value,
 371              * which in turn means, that we have a circular reference.
 372              */
 373             if (ExportHasMark (E)) {
 374                 CircularRefError (E);
 375                 Val = 0;
 376             } else {
 377                 MarkExport (E);
 378                 Val = GetExportVal (E);
 379                 UnmarkExport (E);
 380             }
 381             return Val;
 382
 383         case EXPR_SEGMENT:
 384             S = GetExprSection (Expr);
 385             return S->Offs + S->Seg->PC;
 386
 387         case EXPR_MEMAREA:
 388             return Expr->V.MemArea->Start;
 389
 390         case EXPR_PLUS:
 391             return GetExprVal (Expr->Left) + GetExprVal (Expr->Right);
 392
 393         case EXPR_MINUS:
 394             return GetExprVal (Expr->Left) - GetExprVal (Expr->Right);
 395
 396         case EXPR_MUL:
 397             return GetExprVal (Expr->Left) * GetExprVal (Expr->Right);
 398
 399         case EXPR_DIV:
 400             Left  = GetExprVal (Expr->Left);
 401             Right = GetExprVal (Expr->Right);
 402             if (Right == 0) {
 403                 Error ("Division by zero");
 404             }
 405             return Left / Right;
 406
 407         case EXPR_MOD:
 408             Left  = GetExprVal (Expr->Left);
 409             Right = GetExprVal (Expr->Right);
 410             if (Right == 0) {
 411                 Error ("Modulo operation with zero");
 412             }
 413             return Left % Right;
 414
 415         case EXPR_OR:
 416             return GetExprVal (Expr->Left) | GetExprVal (Expr->Right);
 417
 418         case EXPR_XOR:
 419             return GetExprVal (Expr->Left) ^ GetExprVal (Expr->Right);
 420
 421         case EXPR_AND:
 422             return GetExprVal (Expr->Left) & GetExprVal (Expr->Right);
 423
 424         case EXPR_SHL:
 425             return GetExprVal (Expr->Left) << GetExprVal (Expr->Right);
 426
 427         case EXPR_SHR:
 428             return GetExprVal (Expr->Left) >> GetExprVal (Expr->Right);
 429
 430         case EXPR_EQ:
 431             return (GetExprVal (Expr->Left) == GetExprVal (Expr->Right));
 432
 433         case EXPR_NE:
 434             return (GetExprVal (Expr->Left) != GetExprVal (Expr->Right));
 435
 436         case EXPR_LT:
 437             return (GetExprVal (Expr->Left) < GetExprVal (Expr->Right));
 438
 439         case EXPR_GT:
 440             return (GetExprVal (Expr->Left) > GetExprVal (Expr->Right));
 441
 442         case EXPR_LE:
 443             return (GetExprVal (Expr->Left) <= GetExprVal (Expr->Right));
 444
 445         case EXPR_GE:
 446             return (GetExprVal (Expr->Left) >= GetExprVal (Expr->Right));
 447
 448         case EXPR_UNARY_MINUS:
 449             return -GetExprVal (Expr->Left);
 450
 451         case EXPR_NOT:
 452             return ~GetExprVal (Expr->Left);
 453
 454         case EXPR_LOBYTE:
 455             return GetExprVal (Expr->Left) & 0xFF;
 456
 457         case EXPR_HIBYTE:
 458             return (GetExprVal (Expr->Left) >> 8) & 0xFF;
 459
 460         case EXPR_SWAP:
 461             Left = GetExprVal (Expr->Left);
 462             return ((Left >> 8) & 0x00FF) | ((Left << 8) & 0xFF00);
 463
 464         case EXPR_BAND:
 465             return GetExprVal (Expr->Left) && GetExprVal (Expr->Right);
 466
 467         case EXPR_BOR:
 468             return GetExprVal (Expr->Left) || GetExprVal (Expr->Right);
 469
 470         case EXPR_BXOR:
 471             return (GetExprVal (Expr->Left) != 0) ^ (GetExprVal (Expr->Right) != 0);
 472
 473         case EXPR_BNOT:
 474             return !GetExprVal (Expr->Left);
 475
 476         default:
 477             Internal ("Unknown expression Op type: %u", Expr->Op);
 478             /* NOTREACHED */
 479             return 0;
 480     }
 481 }
 482
 483
 484
 485 ExprNode* LiteralExpr (long Val, ObjData* O)
 486 /* Return an expression tree that encodes the given literal value */
 487 {
 488     ExprNode* Expr = NewExprNode (O);
 489     Expr->Op = EXPR_LITERAL;
 490     Expr->V.Val = Val;
 491     return Expr;
 492 }
 493
 494
 495
 496 ExprNode* MemExpr (Memory* Mem, long Offs, ObjData* O)
 497 /* Return an expression tree that encodes an offset into the memory area */
 498 {
 499     ExprNode* Root;
 500
 501     ExprNode* Expr = NewExprNode (O);
 502     Expr->Op = EXPR_MEMAREA;
 503     Expr->V.MemArea = Mem;
 504
 505     Root = NewExprNode (O);
 506     Root->Op = EXPR_PLUS;
 507     Root->Left = Expr;
 508     Root->Right = LiteralExpr (Offs, O);
 509
 510     return Root;
 511 }
 512
 513
 514
 515 ExprNode* ReadExpr (FILE* F, ObjData* O)
 516 /* Read an expression from the given file */
 517 {
 518     ExprNode* Expr;
 519
 520     /* Read the node tag and handle NULL nodes */
 521     unsigned char Op = Read8 (F);
 522     if (Op == EXPR_NULL) {
 523         return 0;
 524     }
 525
 526     /* Create a new node */
 527     Expr = NewExprNode (O);
 528     Expr->Op = Op;
 529
 530     /* Check the tag and handle the different expression types */
 531     if (EXPR_IS_LEAF (Op)) {
 532         switch (Op) {
 533
 534             case EXPR_LITERAL:
 535                 Expr->V.Val = Read32Signed (F);
 536                 break;
 537
 538             case EXPR_SYMBOL:
 539                 /* Read the import number */
 540                 Expr->V.ImpNum = Read16 (F);
 541                 break;
 542
 543             case EXPR_SEGMENT:
 544                 /* Read the segment number */
 545                 Expr->V.SegNum = Read8 (F);
 546                 break;
 547
 548             default:
 549                 Error ("Invalid expression op: %02X", Op);
 550
 551         }
 552
 553     } else {
 554
 555         /* Not a leaf node */
 556         Expr->Left = ReadExpr (F, O);
 557         Expr->Right = ReadExpr (F, O);
 558
 559     }
 560
 561     /* Return the tree */
 562     return Expr;
 563 }
 564
 565
 566
 567 int EqualExpr (ExprNode* E1, ExprNode* E2)
 568 /* Check if two expressions are identical. */
 569 {
 570     /* If one pointer is NULL, both must be NULL */
 571     if ((E1 == 0) ^ (E2 == 0)) {
 572         return 0;
 573     }
 574     if (E1 == 0) {
 575         return 1;
 576     }
 577
 578     /* Both pointers not NULL, check OP */
 579     if (E1->Op != E2->Op) {
 580         return 0;
 581     }
 582
 583     /* OPs are identical, check data for leafs, or subtrees */
 584     switch (E1->Op) {
 585
 586         case EXPR_LITERAL:
 587             /* Value must be identical */
 588             return (E1->V.Val == E2->V.Val);
 589
 590         case EXPR_SYMBOL:
 591             /* Import number must be identical */
 592             return (E1->V.ImpNum == E2->V.ImpNum);
 593
 594         case EXPR_SEGMENT:
 595             /* Segment number must be identical */
 596             return (E1->V.SegNum == E2->V.SegNum);
 597
 598         case EXPR_MEMAREA:
 599             /* Memory area must be identical */
 600             return (E1->V.MemArea == E2->V.MemArea);
 601
 602         default:
 603             /* Not a leaf node */
 604             return EqualExpr (E1->Left, E2->Left) && EqualExpr (E1->Right, E2->Right);
 605     }
 606
 607 }
 608
 609
 610
 611
 612
 613
 614
 615
 616
 617
 618
 619
 620
 621
 622
 623
 624