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