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-2010, 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 export */
 205         return CollAt (&Expr->Obj->Imports, 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 ExprNode* LiteralExpr (long Val, ObjData* O)
 402 /* Return an expression tree that encodes the given literal value */
 403 {
 404     ExprNode* Expr = NewExprNode (O, EXPR_LITERAL);
 405     Expr->V.IVal = Val;
 406     return Expr;
 407 }
 408
 409
 410
 411 ExprNode* MemoryExpr (MemoryArea* Mem, long Offs, ObjData* O)
 412 /* Return an expression tree that encodes an offset into a memory area */
 413 {
 414     ExprNode* Root;
 415
 416     ExprNode* Expr = NewExprNode (O, EXPR_MEMAREA);
 417     Expr->V.Mem = Mem;
 418
 419     if (Offs != 0) {
 420         Root = NewExprNode (O, EXPR_PLUS);
 421         Root->Left = Expr;
 422         Root->Right = LiteralExpr (Offs, O);
 423     } else {
 424         Root = Expr;
 425     }
 426
 427     return Root;
 428 }
 429
 430
 431
 432 ExprNode* SegmentExpr (Segment* Seg, long Offs, ObjData* O)
 433 /* Return an expression tree that encodes an offset into a segment */
 434 {
 435     ExprNode* Root;
 436
 437     ExprNode* Expr = NewExprNode (O, EXPR_SEGMENT);
 438     Expr->V.Seg = Seg;
 439
 440     if (Offs != 0) {
 441         Root = NewExprNode (O, EXPR_PLUS);
 442         Root->Left = Expr;
 443         Root->Right = LiteralExpr (Offs, O);
 444     } else {
 445         Root = Expr;
 446     }
 447
 448     return Root;
 449 }
 450
 451
 452
 453 ExprNode* SectionExpr (Section* Sec, long Offs, ObjData* O)
 454 /* Return an expression tree that encodes an offset into a section */
 455 {
 456     ExprNode* Root;
 457
 458     ExprNode* Expr = NewExprNode (O, EXPR_SECTION);
 459     Expr->V.Sec = Sec;
 460
 461     if (Offs != 0) {
 462         Root = NewExprNode (O, EXPR_PLUS);
 463         Root->Left = Expr;
 464         Root->Right = LiteralExpr (Offs, O);
 465     } else {
 466         Root = Expr;
 467     }
 468
 469     return Root;
 470 }
 471
 472
 473
 474 ExprNode* ReadExpr (FILE* F, ObjData* O)
 475 /* Read an expression from the given file */
 476 {
 477     ExprNode* Expr;
 478
 479     /* Read the node tag and handle NULL nodes */
 480     unsigned char Op = Read8 (F);
 481     if (Op == EXPR_NULL) {
 482         return 0;
 483     }
 484
 485     /* Create a new node */
 486     Expr = NewExprNode (O, Op);
 487
 488     /* Check the tag and handle the different expression types */
 489     if (EXPR_IS_LEAF (Op)) {
 490         switch (Op) {
 491
 492             case EXPR_LITERAL:
 493                 Expr->V.IVal = Read32Signed (F);
 494                 break;
 495
 496             case EXPR_SYMBOL:
 497                 /* Read the import number */
 498                 Expr->V.ImpNum = ReadVar (F);
 499                 break;
 500
 501             case EXPR_SECTION:
 502                 /* Read the segment number */
 503                 Expr->V.SecNum = Read8 (F);
 504                 break;
 505
 506             default:
 507                 Error ("Invalid expression op: %02X", Op);
 508
 509         }
 510
 511     } else {
 512
 513         /* Not a leaf node */
 514         Expr->Left = ReadExpr (F, O);
 515         Expr->Right = ReadExpr (F, O);
 516
 517     }
 518
 519     /* Return the tree */
 520     return Expr;
 521 }
 522
 523
 524
 525 int EqualExpr (ExprNode* E1, ExprNode* E2)
 526 /* Check if two expressions are identical. */
 527 {
 528     /* If one pointer is NULL, both must be NULL */
 529     if ((E1 == 0) ^ (E2 == 0)) {
 530         return 0;
 531     }
 532     if (E1 == 0) {
 533         return 1;
 534     }
 535
 536     /* Both pointers not NULL, check OP */
 537     if (E1->Op != E2->Op) {
 538         return 0;
 539     }
 540
 541     /* OPs are identical, check data for leafs, or subtrees */
 542     switch (E1->Op) {
 543
 544         case EXPR_LITERAL:
 545             /* Value must be identical */
 546             return (E1->V.IVal == E2->V.IVal);
 547
 548         case EXPR_SYMBOL:
 549             /* Import must be identical */
 550             return (GetExprImport (E1) == GetExprImport (E2));
 551
 552         case EXPR_SECTION:
 553             /* Section must be identical */
 554             return (GetExprSection (E1) == GetExprSection (E2));
 555
 556         case EXPR_SEGMENT:
 557             /* Segment must be identical */
 558             return (E1->V.Seg == E2->V.Seg);
 559
 560         case EXPR_MEMAREA:
 561             /* Memory area must be identical */
 562             return (E1->V.Mem == E2->V.Mem);
 563
 564         default:
 565             /* Not a leaf node */
 566             return EqualExpr (E1->Left, E2->Left) && EqualExpr (E1->Right, E2->Right);
 567     }
 568
 569 }
 570
 571
 572