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-2003 Ullrich von Bassewitz                                       */
  10 /*               Römerstrasse 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.Val    = 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
 107     if (EXPR_IS_LEAF (Root->Op)) {
 108         switch (Root->Op) {
 109
 110             case EXPR_LITERAL:
 111                 return 1;
 112
 113             case EXPR_SYMBOL:
 114                 /* Get the referenced export */
 115                 E = GetExprExport (Root);
 116                 /* If this export has a mark set, we've already encountered it.
 117                  * This means that the export is used to define it's own value,
 118                  * which in turn means, that we have a circular reference.
 119                  */
 120                 if (ExportHasMark (E)) {
 121                     CircularRefError (E);
 122                     Const = 0;
 123                 } else {
 124                     MarkExport (E);
 125                     Const = IsConstExport (E);
 126                     UnmarkExport (E);
 127                 }
 128                 return Const;
 129
 130             default:
 131                 return 0;
 132
 133         }
 134     } else if (EXPR_IS_UNARY (Root->Op)) {
 135
 136         return IsConstExpr (Root->Left);
 137
 138     } else {
 139
 140         /* We must handle shortcut boolean expressions here */
 141         switch (Root->Op) {
 142
 143             case EXPR_BAND:
 144                 if (IsConstExpr (Root->Left)) {
 145                     /* lhs is const, if it is zero, don't eval right */
 146                     if (GetExprVal (Root->Left) == 0) {
 147                         return 1;
 148                     } else {
 149                         return IsConstExpr (Root->Right);
 150                     }
 151                 } else {
 152                     /* lhs not const --> tree not const */
 153                     return 0;
 154                 }
 155                 break;
 156
 157             case EXPR_BOR:
 158                 if (IsConstExpr (Root->Left)) {
 159                     /* lhs is const, if it is not zero, don't eval right */
 160                     if (GetExprVal (Root->Left) != 0) {
 161                         return 1;
 162                     } else {
 163                         return IsConstExpr (Root->Right);
 164                     }
 165                 } else {
 166                     /* lhs not const --> tree not const */
 167                     return 0;
 168                 }
 169                 break;
 170
 171             default:
 172                 /* All others are handled normal */
 173                 return IsConstExpr (Root->Left) && IsConstExpr (Root->Right);
 174         }
 175     }
 176 }
 177
 178
 179
 180 Import* GetExprImport (ExprNode* Expr)
 181 /* Get the import data structure for a symbol expression node */
 182 {
 183     /* Check that this is really a symbol */
 184     PRECONDITION (Expr->Op == EXPR_SYMBOL);
 185
 186     /* Return the import */
 187     return Expr->Obj->Imports [Expr->V.ImpNum];
 188 }
 189
 190
 191
 192 Export* GetExprExport (ExprNode* Expr)
 193 /* Get the exported symbol for a symbol expression node */
 194 {
 195     /* Check that this is really a symbol */
 196     PRECONDITION (Expr->Op == EXPR_SYMBOL);
 197
 198     /* Return the export */
 199     return Expr->Obj->Imports [Expr->V.ImpNum]->Exp;
 200 }
 201
 202
 203
 204 Section* GetExprSection (ExprNode* Expr)
 205 /* Get the segment for a section expression node */
 206 {
 207     /* Check that this is really a section node */
 208     PRECONDITION (Expr->Op == EXPR_SECTION);
 209
 210     /* If we have an object file, get the section from it, otherwise
 211      * (internally generated expressions), get the section from the
 212      * section pointer.
 213      */
 214     if (Expr->Obj) {
 215         /* Return the export */
 216         return Expr->Obj->Sections [Expr->V.SegNum];
 217     } else {
 218         return Expr->V.Sec;
 219     }
 220 }
 221
 222
 223
 224 long GetExprVal (ExprNode* Expr)
 225 /* Get the value of a constant expression */
 226 {
 227     long Right, Left, Val;
 228     Section* S;
 229     Export* E;
 230
 231     switch (Expr->Op) {
 232
 233         case EXPR_LITERAL:
 234             return Expr->V.Val;
 235
 236         case EXPR_SYMBOL:
 237             /* Get the referenced export */
 238             E = GetExprExport (Expr);
 239             /* If this export has a mark set, we've already encountered it.
 240              * This means that the export is used to define it's own value,
 241              * which in turn means, that we have a circular reference.
 242              */
 243             if (ExportHasMark (E)) {
 244                 CircularRefError (E);
 245                 Val = 0;
 246             } else {
 247                 MarkExport (E);
 248                 Val = GetExportVal (E);
 249                 UnmarkExport (E);
 250             }
 251             return Val;
 252
 253         case EXPR_SECTION:
 254             S = GetExprSection (Expr);
 255             return S->Offs + S->Seg->PC;
 256
 257         case EXPR_SEGMENT:
 258             return Expr->V.Seg->PC;
 259
 260         case EXPR_MEMAREA:
 261             return Expr->V.Mem->Start;
 262
 263         case EXPR_PLUS:
 264             return GetExprVal (Expr->Left) + GetExprVal (Expr->Right);
 265
 266         case EXPR_MINUS:
 267             return GetExprVal (Expr->Left) - GetExprVal (Expr->Right);
 268
 269         case EXPR_MUL:
 270             return GetExprVal (Expr->Left) * GetExprVal (Expr->Right);
 271
 272         case EXPR_DIV:
 273             Left  = GetExprVal (Expr->Left);
 274             Right = GetExprVal (Expr->Right);
 275             if (Right == 0) {
 276                 Error ("Division by zero");
 277             }
 278             return Left / Right;
 279
 280         case EXPR_MOD:
 281             Left  = GetExprVal (Expr->Left);
 282             Right = GetExprVal (Expr->Right);
 283             if (Right == 0) {
 284                 Error ("Modulo operation with zero");
 285             }
 286             return Left % Right;
 287
 288         case EXPR_OR:
 289             return GetExprVal (Expr->Left) | GetExprVal (Expr->Right);
 290
 291         case EXPR_XOR:
 292             return GetExprVal (Expr->Left) ^ GetExprVal (Expr->Right);
 293
 294         case EXPR_AND:
 295             return GetExprVal (Expr->Left) & GetExprVal (Expr->Right);
 296
 297         case EXPR_SHL:
 298             return GetExprVal (Expr->Left) << GetExprVal (Expr->Right);
 299
 300         case EXPR_SHR:
 301             return GetExprVal (Expr->Left) >> GetExprVal (Expr->Right);
 302
 303         case EXPR_EQ:
 304             return (GetExprVal (Expr->Left) == GetExprVal (Expr->Right));
 305
 306         case EXPR_NE:
 307             return (GetExprVal (Expr->Left) != GetExprVal (Expr->Right));
 308
 309         case EXPR_LT:
 310             return (GetExprVal (Expr->Left) < GetExprVal (Expr->Right));
 311
 312         case EXPR_GT:
 313             return (GetExprVal (Expr->Left) > GetExprVal (Expr->Right));
 314
 315         case EXPR_LE:
 316             return (GetExprVal (Expr->Left) <= GetExprVal (Expr->Right));
 317
 318         case EXPR_GE:
 319             return (GetExprVal (Expr->Left) >= GetExprVal (Expr->Right));
 320
 321         case EXPR_UNARY_MINUS:
 322             return -GetExprVal (Expr->Left);
 323
 324         case EXPR_NOT:
 325             return ~GetExprVal (Expr->Left);
 326
 327         case EXPR_BYTE0:
 328             return GetExprVal (Expr->Left) & 0xFF;
 329
 330         case EXPR_BYTE1:
 331             return (GetExprVal (Expr->Left) >> 8) & 0xFF;
 332
 333         case EXPR_BYTE2:
 334             return (GetExprVal (Expr->Left) >> 16) & 0xFF;
 335
 336         case EXPR_BYTE3:
 337             return (GetExprVal (Expr->Left) >> 24) & 0xFF;
 338
 339         case EXPR_SWAP:
 340             Left = GetExprVal (Expr->Left);
 341             return ((Left >> 8) & 0x00FF) | ((Left << 8) & 0xFF00);
 342
 343         case EXPR_BAND:
 344             return GetExprVal (Expr->Left) && GetExprVal (Expr->Right);
 345
 346         case EXPR_BOR:
 347             return GetExprVal (Expr->Left) || GetExprVal (Expr->Right);
 348
 349         case EXPR_BXOR:
 350             return (GetExprVal (Expr->Left) != 0) ^ (GetExprVal (Expr->Right) != 0);
 351
 352         case EXPR_BNOT:
 353             return !GetExprVal (Expr->Left);
 354
 355         default:
 356             Internal ("Unknown expression Op type: %u", Expr->Op);
 357             /* NOTREACHED */
 358             return 0;
 359     }
 360 }
 361
 362
 363
 364 ExprNode* LiteralExpr (long Val, ObjData* O)
 365 /* Return an expression tree that encodes the given literal value */
 366 {
 367     ExprNode* Expr = NewExprNode (O);
 368     Expr->Op = EXPR_LITERAL;
 369     Expr->V.Val = Val;
 370     return Expr;
 371 }
 372
 373
 374
 375 ExprNode* MemoryExpr (Memory* Mem, long Offs, ObjData* O)
 376 /* Return an expression tree that encodes an offset into a memory area */
 377 {
 378     ExprNode* Root;
 379
 380     ExprNode* Expr = NewExprNode (O);
 381     Expr->Op = EXPR_MEMAREA;
 382     Expr->V.Mem = Mem;
 383
 384     if (Offs != 0) {
 385         Root = NewExprNode (O);
 386         Root->Op = EXPR_PLUS;
 387         Root->Left = Expr;
 388         Root->Right = LiteralExpr (Offs, O);
 389     } else {
 390         Root = Expr;
 391     }
 392
 393     return Root;
 394 }
 395
 396
 397
 398 ExprNode* SegmentExpr (Segment* Seg, long Offs, ObjData* O)
 399 /* Return an expression tree that encodes an offset into a segment */
 400 {
 401     ExprNode* Root;
 402
 403     ExprNode* Expr = NewExprNode (O);
 404     Expr->Op = EXPR_SEGMENT;
 405     Expr->V.Seg = Seg;
 406
 407     if (Offs != 0) {
 408         Root = NewExprNode (O);
 409         Root->Op = EXPR_PLUS;
 410         Root->Left = Expr;
 411         Root->Right = LiteralExpr (Offs, O);
 412     } else {
 413         Root = Expr;
 414     }
 415
 416     return Root;
 417 }
 418
 419
 420
 421 ExprNode* SectionExpr (Section* Sec, long Offs, ObjData* O)
 422 /* Return an expression tree that encodes an offset into a section */
 423 {
 424     ExprNode* Root;
 425
 426     ExprNode* Expr = NewExprNode (O);
 427     Expr->Op = EXPR_SECTION;
 428     Expr->V.Sec = Sec;
 429
 430     if (Offs != 0) {
 431         Root = NewExprNode (O);
 432         Root->Op = EXPR_PLUS;
 433         Root->Left = Expr;
 434         Root->Right = LiteralExpr (Offs, O);
 435     } else {
 436         Root = Expr;
 437     }
 438
 439     return Root;
 440 }
 441
 442
 443
 444 ExprNode* ReadExpr (FILE* F, ObjData* O)
 445 /* Read an expression from the given file */
 446 {
 447     ExprNode* Expr;
 448
 449     /* Read the node tag and handle NULL nodes */
 450     unsigned char Op = Read8 (F);
 451     if (Op == EXPR_NULL) {
 452         return 0;
 453     }
 454
 455     /* Create a new node */
 456     Expr = NewExprNode (O);
 457     Expr->Op = Op;
 458
 459     /* Check the tag and handle the different expression types */
 460     if (EXPR_IS_LEAF (Op)) {
 461         switch (Op) {
 462
 463             case EXPR_LITERAL:
 464                 Expr->V.Val = Read32Signed (F);
 465                 break;
 466
 467             case EXPR_SYMBOL:
 468                 /* Read the import number */
 469                 Expr->V.ImpNum = ReadVar (F);
 470                 break;
 471
 472             case EXPR_SECTION:
 473                 /* Read the segment number */
 474                 Expr->V.SegNum = Read8 (F);
 475                 break;
 476
 477             default:
 478                 Error ("Invalid expression op: %02X", Op);
 479
 480         }
 481
 482     } else {
 483
 484         /* Not a leaf node */
 485         Expr->Left = ReadExpr (F, O);
 486         Expr->Right = ReadExpr (F, O);
 487
 488     }
 489
 490     /* Return the tree */
 491     return Expr;
 492 }
 493
 494
 495
 496 int EqualExpr (ExprNode* E1, ExprNode* E2)
 497 /* Check if two expressions are identical. */
 498 {
 499     /* If one pointer is NULL, both must be NULL */
 500     if ((E1 == 0) ^ (E2 == 0)) {
 501         return 0;
 502     }
 503     if (E1 == 0) {
 504         return 1;
 505     }
 506
 507     /* Both pointers not NULL, check OP */
 508     if (E1->Op != E2->Op) {
 509         return 0;
 510     }
 511
 512     /* OPs are identical, check data for leafs, or subtrees */
 513     switch (E1->Op) {
 514
 515         case EXPR_LITERAL:
 516             /* Value must be identical */
 517             return (E1->V.Val == E2->V.Val);
 518
 519         case EXPR_SYMBOL:
 520             /* Import number must be identical */
 521             return (E1->V.ImpNum == E2->V.ImpNum);
 522
 523         case EXPR_SECTION:
 524             /* Section must be identical */
 525             return (GetExprSection (E1) == GetExprSection (E2));
 526
 527         case EXPR_SEGMENT:
 528             /* Segment must be identical */
 529             return (E1->V.Seg == E2->V.Seg);
 530
 531         case EXPR_MEMAREA:
 532             /* Memory area must be identical */
 533             return (E1->V.Mem == E2->V.Mem );
 534
 535         default:
 536             /* Not a leaf node */
 537             return EqualExpr (E1->Left, E2->Left) && EqualExpr (E1->Right, E2->Right);
 538     }
 539
 540 }
 541
 542
 543
 544
 545
 546
 547
 548
 549
 550
 551
 552
 553
 554
 555
 556
 557