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