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