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-2007 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 "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.IVal   = 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.IVal;
 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_MAX:
 348             Left = GetExprVal (Expr->Left);
 349             Right = GetExprVal (Expr->Right);
 350             return (Left > Right)? Left : Right;
 351
 352         case EXPR_MIN:
 353             Left = GetExprVal (Expr->Left);
 354             Right = GetExprVal (Expr->Right);
 355             return (Left < Right)? Left : Right;
 356
 357         case EXPR_UNARY_MINUS:
 358             return -GetExprVal (Expr->Left);
 359
 360         case EXPR_NOT:
 361             return ~GetExprVal (Expr->Left);
 362
 363         case EXPR_SWAP:
 364             Left = GetExprVal (Expr->Left);
 365             return ((Left >> 8) & 0x00FF) | ((Left << 8) & 0xFF00);
 366
 367         case EXPR_BOOLNOT:
 368             return !GetExprVal (Expr->Left);
 369
 370         case EXPR_BYTE0:
 371             return GetExprVal (Expr->Left) & 0xFF;
 372
 373         case EXPR_BYTE1:
 374             return (GetExprVal (Expr->Left) >> 8) & 0xFF;
 375
 376         case EXPR_BYTE2:
 377             return (GetExprVal (Expr->Left) >> 16) & 0xFF;
 378
 379         case EXPR_BYTE3:
 380             return (GetExprVal (Expr->Left) >> 24) & 0xFF;
 381
 382         case EXPR_WORD0:
 383             return GetExprVal (Expr->Left) & 0xFFFF;
 384
 385         case EXPR_WORD1:
 386             return (GetExprVal (Expr->Left) >> 16) & 0xFFFF;
 387
 388         default:
 389             Internal ("Unknown expression Op type: %u", Expr->Op);
 390             /* NOTREACHED */
 391             return 0;
 392     }
 393 }
 394
 395
 396
 397 ExprNode* LiteralExpr (long Val, ObjData* O)
 398 /* Return an expression tree that encodes the given literal value */
 399 {
 400     ExprNode* Expr = NewExprNode (O);
 401     Expr->Op = EXPR_LITERAL;
 402     Expr->V.IVal = Val;
 403     return Expr;
 404 }
 405
 406
 407
 408 ExprNode* MemoryExpr (Memory* Mem, long Offs, ObjData* O)
 409 /* Return an expression tree that encodes an offset into a memory area */
 410 {
 411     ExprNode* Root;
 412
 413     ExprNode* Expr = NewExprNode (O);
 414     Expr->Op = EXPR_MEMAREA;
 415     Expr->V.Mem = Mem;
 416
 417     if (Offs != 0) {
 418         Root = NewExprNode (O);
 419         Root->Op = EXPR_PLUS;
 420         Root->Left = Expr;
 421         Root->Right = LiteralExpr (Offs, O);
 422     } else {
 423         Root = Expr;
 424     }
 425
 426     return Root;
 427 }
 428
 429
 430
 431 ExprNode* SegmentExpr (Segment* Seg, long Offs, ObjData* O)
 432 /* Return an expression tree that encodes an offset into a segment */
 433 {
 434     ExprNode* Root;
 435
 436     ExprNode* Expr = NewExprNode (O);
 437     Expr->Op = EXPR_SEGMENT;
 438     Expr->V.Seg = Seg;
 439
 440     if (Offs != 0) {
 441         Root = NewExprNode (O);
 442         Root->Op = EXPR_PLUS;
 443         Root->Left = Expr;
 444         Root->Right = LiteralExpr (Offs, O);
 445     } else {
 446         Root = Expr;
 447     }
 448
 449     return Root;
 450 }
 451
 452
 453
 454 ExprNode* SectionExpr (Section* Sec, long Offs, ObjData* O)
 455 /* Return an expression tree that encodes an offset into a section */
 456 {
 457     ExprNode* Root;
 458
 459     ExprNode* Expr = NewExprNode (O);
 460     Expr->Op = EXPR_SECTION;
 461     Expr->V.Sec = Sec;
 462
 463     if (Offs != 0) {
 464         Root = NewExprNode (O);
 465         Root->Op = EXPR_PLUS;
 466         Root->Left = Expr;
 467         Root->Right = LiteralExpr (Offs, O);
 468     } else {
 469         Root = Expr;
 470     }
 471
 472     return Root;
 473 }
 474
 475
 476
 477 ExprNode* ReadExpr (FILE* F, ObjData* O)
 478 /* Read an expression from the given file */
 479 {
 480     ExprNode* Expr;
 481
 482     /* Read the node tag and handle NULL nodes */
 483     unsigned char Op = Read8 (F);
 484     if (Op == EXPR_NULL) {
 485         return 0;
 486     }
 487
 488     /* Create a new node */
 489     Expr = NewExprNode (O);
 490     Expr->Op = Op;
 491
 492     /* Check the tag and handle the different expression types */
 493     if (EXPR_IS_LEAF (Op)) {
 494         switch (Op) {
 495
 496             case EXPR_LITERAL:
 497                 Expr->V.IVal = Read32Signed (F);
 498                 break;
 499
 500             case EXPR_SYMBOL:
 501                 /* Read the import number */
 502                 Expr->V.ImpNum = ReadVar (F);
 503                 break;
 504
 505             case EXPR_SECTION:
 506                 /* Read the segment number */
 507                 Expr->V.SegNum = Read8 (F);
 508                 break;
 509
 510             default:
 511                 Error ("Invalid expression op: %02X", Op);
 512
 513         }
 514
 515     } else {
 516
 517         /* Not a leaf node */
 518         Expr->Left = ReadExpr (F, O);
 519         Expr->Right = ReadExpr (F, O);
 520
 521     }
 522
 523     /* Return the tree */
 524     return Expr;
 525 }
 526
 527
 528
 529 int EqualExpr (ExprNode* E1, ExprNode* E2)
 530 /* Check if two expressions are identical. */
 531 {
 532     /* If one pointer is NULL, both must be NULL */
 533     if ((E1 == 0) ^ (E2 == 0)) {
 534         return 0;
 535     }
 536     if (E1 == 0) {
 537         return 1;
 538     }
 539
 540     /* Both pointers not NULL, check OP */
 541     if (E1->Op != E2->Op) {
 542         return 0;
 543     }
 544
 545     /* OPs are identical, check data for leafs, or subtrees */
 546     switch (E1->Op) {
 547
 548         case EXPR_LITERAL:
 549             /* Value must be identical */
 550             return (E1->V.IVal == E2->V.IVal);
 551
 552         case EXPR_SYMBOL:
 553             /* Import number must be identical */
 554             return (E1->V.ImpNum == E2->V.ImpNum);
 555
 556         case EXPR_SECTION:
 557             /* Section must be identical */
 558             return (GetExprSection (E1) == GetExprSection (E2));
 559
 560         case EXPR_SEGMENT:
 561             /* Segment must be identical */
 562             return (E1->V.Seg == E2->V.Seg);
 563
 564         case EXPR_MEMAREA:
 565             /* Memory area must be identical */
 566             return (E1->V.Mem == E2->V.Mem );
 567
 568         default:
 569             /* Not a leaf node */
 570             return EqualExpr (E1->Left, E2->Left) && EqualExpr (E1->Right, E2->Right);
 571     }
 572
 573 }
 574
 575
 576