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