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