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         default:
 413             Internal ("Unknown expression Op type: %u", Expr->Op);
 414             /* NOTREACHED */
 415             return 0;
 416     }
 417 }
 418
 419
 420
 421 static void GetSegExprValInternal (ExprNode* Expr, SegExprDesc* D, int Sign)
 422 /* Check if the given expression consists of a segment reference and only
 423  * constant values, additions and subtractions. If anything else is found,
 424  * set D->TooComplex to true.
 425  * Internal, recursive routine.
 426  */
 427 {
 428     Export* E;
 429
 430     switch (Expr->Op) {
 431
 432         case EXPR_LITERAL:
 433             D->Val += (Sign * Expr->V.IVal);
 434             break;
 435
 436         case EXPR_SYMBOL:
 437             /* Get the referenced export */
 438             E = GetExprExport (Expr);
 439             /* If this export has a mark set, we've already encountered it.
 440              * This means that the export is used to define it's own value,
 441              * which in turn means, that we have a circular reference.
 442              */
 443             if (ExportHasMark (E)) {
 444                 CircularRefError (E);
 445             } else {
 446                 MarkExport (E);
 447                 GetSegExprValInternal (E->Expr, D, Sign);
 448                 UnmarkExport (E);
 449             }
 450             break;
 451
 452         case EXPR_SECTION:
 453             if (D->Seg) {
 454                 /* We cannot handle more than one segment reference in o65 */
 455                 D->TooComplex = 1;
 456             } else {
 457                 /* Get the section from the expression */
 458                 Section* S = GetExprSection (Expr);
 459                 /* Remember the segment reference */
 460                 D->Seg = S->Seg;
 461                 /* Add the offset of the section to the constant value */
 462                 D->Val += Sign * (S->Offs + D->Seg->PC);
 463             }
 464             break;
 465
 466         case EXPR_SEGMENT:
 467             if (D->Seg) {
 468                 /* We cannot handle more than one segment reference in o65 */
 469                 D->TooComplex = 1;
 470             } else {
 471                 /* Remember the segment reference */
 472                 D->Seg = Expr->V.Seg;
 473                 /* Add the offset of the segment to the constant value */
 474                 D->Val += (Sign * D->Seg->PC);
 475             }
 476             break;
 477
 478         case EXPR_PLUS:
 479             GetSegExprValInternal (Expr->Left, D, Sign);
 480             GetSegExprValInternal (Expr->Right, D, Sign);
 481             break;
 482
 483         case EXPR_MINUS:
 484             GetSegExprValInternal (Expr->Left, D, Sign);
 485             GetSegExprValInternal (Expr->Right, D, -Sign);
 486             break;
 487
 488         default:
 489             /* Expression contains illegal operators */
 490             D->TooComplex = 1;
 491             break;
 492
 493     }
 494 }
 495
 496
 497
 498 void GetSegExprVal (ExprNode* Expr, SegExprDesc* D)
 499 /* Check if the given expression consists of a segment reference and only
 500  * constant values, additions and subtractions. If anything else is found,
 501  * set D->TooComplex to true. The function will initialize D.
 502  */
 503 {
 504     /* Initialize the given structure */
 505     D->Val        = 0;
 506     D->TooComplex = 0;
 507     D->Seg        = 0;
 508
 509     /* Call our recursive calculation routine */
 510     GetSegExprValInternal (Expr, D, 1);
 511 }
 512
 513
 514
 515 ExprNode* LiteralExpr (long Val, ObjData* O)
 516 /* Return an expression tree that encodes the given literal value */
 517 {
 518     ExprNode* Expr = NewExprNode (O, EXPR_LITERAL);
 519     Expr->V.IVal = Val;
 520     return Expr;
 521 }
 522
 523
 524
 525 ExprNode* MemoryExpr (MemoryArea* Mem, long Offs, ObjData* O)
 526 /* Return an expression tree that encodes an offset into a memory area */
 527 {
 528     ExprNode* Root;
 529
 530     ExprNode* Expr = NewExprNode (O, EXPR_MEMAREA);
 531     Expr->V.Mem = Mem;
 532
 533     if (Offs != 0) {
 534         Root = NewExprNode (O, EXPR_PLUS);
 535         Root->Left = Expr;
 536         Root->Right = LiteralExpr (Offs, O);
 537     } else {
 538         Root = Expr;
 539     }
 540
 541     return Root;
 542 }
 543
 544
 545
 546 ExprNode* SegmentExpr (Segment* Seg, long Offs, ObjData* O)
 547 /* Return an expression tree that encodes an offset into a segment */
 548 {
 549     ExprNode* Root;
 550
 551     ExprNode* Expr = NewExprNode (O, EXPR_SEGMENT);
 552     Expr->V.Seg = Seg;
 553
 554     if (Offs != 0) {
 555         Root = NewExprNode (O, EXPR_PLUS);
 556         Root->Left = Expr;
 557         Root->Right = LiteralExpr (Offs, O);
 558     } else {
 559         Root = Expr;
 560     }
 561
 562     return Root;
 563 }
 564
 565
 566
 567 ExprNode* SectionExpr (Section* Sec, long Offs, ObjData* O)
 568 /* Return an expression tree that encodes an offset into a section */
 569 {
 570     ExprNode* Root;
 571
 572     ExprNode* Expr = NewExprNode (O, EXPR_SECTION);
 573     Expr->V.Sec = Sec;
 574
 575     if (Offs != 0) {
 576         Root = NewExprNode (O, EXPR_PLUS);
 577         Root->Left = Expr;
 578         Root->Right = LiteralExpr (Offs, O);
 579     } else {
 580         Root = Expr;
 581     }
 582
 583     return Root;
 584 }
 585
 586
 587
 588 ExprNode* ReadExpr (FILE* F, ObjData* O)
 589 /* Read an expression from the given file */
 590 {
 591     ExprNode* Expr;
 592     Section*  S;
 593
 594     /* Read the node tag and handle NULL nodes */
 595     unsigned char Op = Read8 (F);
 596     if (Op == EXPR_NULL) {
 597         return 0;
 598     }
 599
 600     /* Create a new node */
 601     Expr = NewExprNode (O, Op);
 602
 603     /* Check the tag and handle the different expression types */
 604     if (EXPR_IS_LEAF (Op)) {
 605         switch (Op) {
 606
 607             case EXPR_LITERAL:
 608                 Expr->V.IVal = Read32Signed (F);
 609                 break;
 610
 611             case EXPR_SYMBOL:
 612                 /* Read the import number */
 613                 Expr->V.ImpNum = ReadVar (F);
 614                 break;
 615
 616             case EXPR_SECTION:
 617                 /* Read the section number */
 618                 Expr->V.SecNum = ReadVar (F);
 619                 break;
 620
 621             case EXPR_BANK:
 622                 /* Read the section number */
 623                 Expr->V.SecNum = ReadVar (F);
 624                 /* Mark the section so we know it must be placed into a memory
 625                  * area with the "bank" attribute.
 626                  */
 627                 S = GetExprSection (Expr);
 628                 S->Seg->BankRef = 1;
 629                 break;
 630
 631             default:
 632                 Error ("Invalid expression op: %02X", Op);
 633
 634         }
 635
 636     } else {
 637
 638         /* Not a leaf node */
 639         Expr->Left = ReadExpr (F, O);
 640         Expr->Right = ReadExpr (F, O);
 641
 642     }
 643
 644     /* Return the tree */
 645     return Expr;
 646 }
 647
 648
 649
 650 int EqualExpr (ExprNode* E1, ExprNode* E2)
 651 /* Check if two expressions are identical. */
 652 {
 653     /* If one pointer is NULL, both must be NULL */
 654     if ((E1 == 0) ^ (E2 == 0)) {
 655         return 0;
 656     }
 657     if (E1 == 0) {
 658         return 1;
 659     }
 660
 661     /* Both pointers not NULL, check OP */
 662     if (E1->Op != E2->Op) {
 663         return 0;
 664     }
 665
 666     /* OPs are identical, check data for leafs, or subtrees */
 667     switch (E1->Op) {
 668
 669         case EXPR_LITERAL:
 670             /* Value must be identical */
 671             return (E1->V.IVal == E2->V.IVal);
 672
 673         case EXPR_SYMBOL:
 674             /* Import must be identical */
 675             return (GetExprImport (E1) == GetExprImport (E2));
 676
 677         case EXPR_SECTION:
 678             /* Section must be identical */
 679             return (GetExprSection (E1) == GetExprSection (E2));
 680
 681         case EXPR_SEGMENT:
 682             /* Segment must be identical */
 683             return (E1->V.Seg == E2->V.Seg);
 684
 685         case EXPR_MEMAREA:
 686             /* Memory area must be identical */
 687             return (E1->V.Mem == E2->V.Mem);
 688
 689         default:
 690             /* Not a leaf node */
 691             return EqualExpr (E1->Left, E2->Left) && EqualExpr (E1->Right, E2->Right);
 692     }
 693
 694 }
 695
 696
 697