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 segment expression node */
 208 {
 209     /* Check that this is really a segment node */
 210     PRECONDITION (Expr->Op == EXPR_SEGMENT);
 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_SEGMENT:
 256             S = GetExprSection (Expr);
 257             return S->Offs + S->Seg->PC;
 258
 259         case EXPR_MEMAREA:
 260             return Expr->V.MemArea->Start;
 261
 262         case EXPR_PLUS:
 263             return GetExprVal (Expr->Left) + GetExprVal (Expr->Right);
 264
 265         case EXPR_MINUS:
 266             return GetExprVal (Expr->Left) - GetExprVal (Expr->Right);
 267
 268         case EXPR_MUL:
 269             return GetExprVal (Expr->Left) * GetExprVal (Expr->Right);
 270
 271         case EXPR_DIV:
 272             Left  = GetExprVal (Expr->Left);
 273             Right = GetExprVal (Expr->Right);
 274             if (Right == 0) {
 275                 Error ("Division by zero");
 276             }
 277             return Left / Right;
 278
 279         case EXPR_MOD:
 280             Left  = GetExprVal (Expr->Left);
 281             Right = GetExprVal (Expr->Right);
 282             if (Right == 0) {
 283                 Error ("Modulo operation with zero");
 284             }
 285             return Left % Right;
 286
 287         case EXPR_OR:
 288             return GetExprVal (Expr->Left) | GetExprVal (Expr->Right);
 289
 290         case EXPR_XOR:
 291             return GetExprVal (Expr->Left) ^ GetExprVal (Expr->Right);
 292
 293         case EXPR_AND:
 294             return GetExprVal (Expr->Left) & GetExprVal (Expr->Right);
 295
 296         case EXPR_SHL:
 297             return GetExprVal (Expr->Left) << GetExprVal (Expr->Right);
 298
 299         case EXPR_SHR:
 300             return GetExprVal (Expr->Left) >> GetExprVal (Expr->Right);
 301
 302         case EXPR_EQ:
 303             return (GetExprVal (Expr->Left) == GetExprVal (Expr->Right));
 304
 305         case EXPR_NE:
 306             return (GetExprVal (Expr->Left) != GetExprVal (Expr->Right));
 307
 308         case EXPR_LT:
 309             return (GetExprVal (Expr->Left) < GetExprVal (Expr->Right));
 310
 311         case EXPR_GT:
 312             return (GetExprVal (Expr->Left) > GetExprVal (Expr->Right));
 313
 314         case EXPR_LE:
 315             return (GetExprVal (Expr->Left) <= GetExprVal (Expr->Right));
 316
 317         case EXPR_GE:
 318             return (GetExprVal (Expr->Left) >= GetExprVal (Expr->Right));
 319
 320         case EXPR_UNARY_MINUS:
 321             return -GetExprVal (Expr->Left);
 322
 323         case EXPR_NOT:
 324             return ~GetExprVal (Expr->Left);
 325
 326         case EXPR_BYTE0:
 327             return GetExprVal (Expr->Left) & 0xFF;
 328
 329         case EXPR_BYTE1:
 330             return (GetExprVal (Expr->Left) >> 8) & 0xFF;
 331
 332         case EXPR_BYTE2:
 333             return (GetExprVal (Expr->Left) >> 16) & 0xFF;
 334
 335         case EXPR_BYTE3:
 336             return (GetExprVal (Expr->Left) >> 24) & 0xFF;
 337
 338         case EXPR_SWAP:
 339             Left = GetExprVal (Expr->Left);
 340             return ((Left >> 8) & 0x00FF) | ((Left << 8) & 0xFF00);
 341
 342         case EXPR_BAND:
 343             return GetExprVal (Expr->Left) && GetExprVal (Expr->Right);
 344
 345         case EXPR_BOR:
 346             return GetExprVal (Expr->Left) || GetExprVal (Expr->Right);
 347
 348         case EXPR_BXOR:
 349             return (GetExprVal (Expr->Left) != 0) ^ (GetExprVal (Expr->Right) != 0);
 350
 351         case EXPR_BNOT:
 352             return !GetExprVal (Expr->Left);
 353
 354         default:
 355             Internal ("Unknown expression Op type: %u", Expr->Op);
 356             /* NOTREACHED */
 357             return 0;
 358     }
 359 }
 360
 361
 362
 363 ExprNode* LiteralExpr (long Val, ObjData* O)
 364 /* Return an expression tree that encodes the given literal value */
 365 {
 366     ExprNode* Expr = NewExprNode (O);
 367     Expr->Op = EXPR_LITERAL;
 368     Expr->V.Val = Val;
 369     return Expr;
 370 }
 371
 372
 373
 374 ExprNode* MemExpr (Memory* Mem, long Offs, ObjData* O)
 375 /* Return an expression tree that encodes an offset into the memory area */
 376 {
 377     ExprNode* Root;
 378
 379     ExprNode* Expr = NewExprNode (O);
 380     Expr->Op = EXPR_MEMAREA;
 381     Expr->V.MemArea = Mem;
 382
 383     Root = NewExprNode (O);
 384     Root->Op = EXPR_PLUS;
 385     Root->Left = Expr;
 386     Root->Right = LiteralExpr (Offs, O);
 387
 388     return Root;
 389 }
 390
 391
 392
 393 ExprNode* SegExpr (Section* Sec, long Offs, ObjData* O)
 394 /* Return an expression tree that encodes an offset into a segment */
 395 {
 396     ExprNode* Root;
 397
 398     ExprNode* Expr = NewExprNode (O);
 399     Expr->Op = EXPR_SEGMENT;
 400     Expr->V.Sec = Sec;
 401
 402     Root = NewExprNode (O);
 403     Root->Op = EXPR_PLUS;
 404     Root->Left = Expr;
 405     Root->Right = LiteralExpr (Offs, O);
 406
 407     return Root;
 408 }
 409
 410
 411
 412 ExprNode* ReadExpr (FILE* F, ObjData* O)
 413 /* Read an expression from the given file */
 414 {
 415     ExprNode* Expr;
 416
 417     /* Read the node tag and handle NULL nodes */
 418     unsigned char Op = Read8 (F);
 419     if (Op == EXPR_NULL) {
 420         return 0;
 421     }
 422
 423     /* Create a new node */
 424     Expr = NewExprNode (O);
 425     Expr->Op = Op;
 426
 427     /* Check the tag and handle the different expression types */
 428     if (EXPR_IS_LEAF (Op)) {
 429         switch (Op) {
 430
 431             case EXPR_LITERAL:
 432                 Expr->V.Val = Read32Signed (F);
 433                 break;
 434
 435             case EXPR_SYMBOL:
 436                 /* Read the import number */
 437                 Expr->V.ImpNum = Read16 (F);
 438                 break;
 439
 440             case EXPR_SEGMENT:
 441                 /* Read the segment number */
 442                 Expr->V.SegNum = Read8 (F);
 443                 break;
 444
 445             default:
 446                 Error ("Invalid expression op: %02X", Op);
 447
 448         }
 449
 450     } else {
 451
 452         /* Not a leaf node */
 453         Expr->Left = ReadExpr (F, O);
 454         Expr->Right = ReadExpr (F, O);
 455
 456     }
 457
 458     /* Return the tree */
 459     return Expr;
 460 }
 461
 462
 463
 464 int EqualExpr (ExprNode* E1, ExprNode* E2)
 465 /* Check if two expressions are identical. */
 466 {
 467     /* If one pointer is NULL, both must be NULL */
 468     if ((E1 == 0) ^ (E2 == 0)) {
 469         return 0;
 470     }
 471     if (E1 == 0) {
 472         return 1;
 473     }
 474
 475     /* Both pointers not NULL, check OP */
 476     if (E1->Op != E2->Op) {
 477         return 0;
 478     }
 479
 480     /* OPs are identical, check data for leafs, or subtrees */
 481     switch (E1->Op) {
 482
 483         case EXPR_LITERAL:
 484             /* Value must be identical */
 485             return (E1->V.Val == E2->V.Val);
 486
 487         case EXPR_SYMBOL:
 488             /* Import number must be identical */
 489             return (E1->V.ImpNum == E2->V.ImpNum);
 490
 491         case EXPR_SEGMENT:
 492             /* Section must be identical */
 493             return (GetExprSection (E1) == GetExprSection (E2));
 494
 495         case EXPR_MEMAREA:
 496             /* Memory area must be identical */
 497             return (E1->V.MemArea == E2->V.MemArea);
 498
 499         default:
 500             /* Not a leaf node */
 501             return EqualExpr (E1->Left, E2->Left) && EqualExpr (E1->Right, E2->Right);
 502     }
 503
 504 }
 505
 506
 507
 508
 509
 510
 511
 512
 513
 514
 515
 516
 517
 518
 519
 520
 521