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 "exprdefs.h"
  38 #include "xmalloc.h"
  39
  40 /* ld65 */
  41 #include "global.h"
  42 #include "error.h"
  43 #include "fileio.h"
  44 #include "segments.h"
  45 #include "expr.h"
  46
  47
  48
  49 /*****************************************************************************/
  50 /*                                  Helpers                                  */
  51 /*****************************************************************************/
  52
  53
  54
  55 static ExprNode* NewExprNode (ObjData* O)
  56 /* Create a new expression node */
  57 {
  58     /* Allocate fresh memory */
  59     ExprNode* N = xmalloc (sizeof (ExprNode));
  60     N->Op       = EXPR_NULL;
  61     N->Left     = 0;
  62     N->Right    = 0;
  63     N->Obj      = O;
  64     N->V.Val    = 0;
  65
  66     return N;
  67 }
  68
  69
  70
  71 static void FreeExprNode (ExprNode* E)
  72 /* Free a node */
  73 {
  74     /* Free the memory */
  75     xfree (E);
  76 }
  77
  78
  79
  80 /*****************************************************************************/
  81 /*                                   Code                                    */
  82 /*****************************************************************************/
  83
  84
  85
  86 void FreeExpr (ExprNode* Root)
  87 /* Free the expression, Root is pointing to. */
  88 {
  89     if (Root) {
  90         FreeExpr (Root->Left);
  91         FreeExpr (Root->Right);
  92         FreeExprNode (Root);
  93     }
  94 }
  95
  96
  97
  98 int IsConstExpr (ExprNode* Root)
  99 /* Return true if the given expression is a constant expression, that is, one
 100  * with no references to external symbols.
 101  */
 102 {
 103     int Const;
 104     Export* E;
 105
 106     if (EXPR_IS_LEAF (Root->Op)) {
 107         switch (Root->Op) {
 108
 109             case EXPR_LITERAL:
 110                 return 1;
 111
 112             case EXPR_SYMBOL:
 113                 /* Get the referenced export */
 114                 E = GetExprExport (Root);
 115                 /* If this export has a mark set, we've already encountered it.
 116                  * This means that the export is used to define it's own value,
 117                  * which in turn means, that we have a circular reference.
 118                  */
 119                 if (ExportHasMark (E)) {
 120                     Error ("Circular reference for symbol `%s', %s(%lu)",
 121                            E->Name, E->Obj->Files [E->Pos.Name], E->Pos.Line);
 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]->V.Exp;
 200 }
 201
 202
 203
 204 Section* GetExprSection (ExprNode* Expr)
 205 /* Get the segment for a segment expression node */
 206 {
 207     /* Check that this is really a segment node */
 208     PRECONDITION (Expr->Op == EXPR_SEGMENT);
 209
 210     /* Return the export */
 211     return Expr->Obj->Sections [Expr->V.SegNum];
 212 }
 213
 214
 215
 216 long GetExprVal (ExprNode* Expr)
 217 /* Get the value of a constant expression */
 218 {
 219     long Right, Left, Val;
 220     Section* S;
 221     Export* E;
 222
 223     switch (Expr->Op) {
 224
 225         case EXPR_LITERAL:
 226             return Expr->V.Val;
 227
 228         case EXPR_SYMBOL:
 229             /* Get the referenced export */
 230             E = GetExprExport (Expr);
 231             /* If this export has a mark set, we've already encountered it.
 232              * This means that the export is used to define it's own value,
 233              * which in turn means, that we have a circular reference.
 234              */
 235             if (ExportHasMark (E)) {
 236                 CircularRefError (E);
 237                 Val = 0;
 238             } else {
 239                 MarkExport (E);
 240                 Val = GetExportVal (E);
 241                 UnmarkExport (E);
 242             }
 243             return Val;
 244
 245         case EXPR_SEGMENT:
 246             S = GetExprSection (Expr);
 247             return S->Offs + S->Seg->PC;
 248
 249         case EXPR_MEMAREA:
 250             return Expr->V.MemArea->Start;
 251
 252         case EXPR_PLUS:
 253             return GetExprVal (Expr->Left) + GetExprVal (Expr->Right);
 254
 255         case EXPR_MINUS:
 256             return GetExprVal (Expr->Left) - GetExprVal (Expr->Right);
 257
 258         case EXPR_MUL:
 259             return GetExprVal (Expr->Left) * GetExprVal (Expr->Right);
 260
 261         case EXPR_DIV:
 262             Left  = GetExprVal (Expr->Left);
 263             Right = GetExprVal (Expr->Right);
 264             if (Right == 0) {
 265                 Error ("Division by zero");
 266             }
 267             return Left / Right;
 268
 269         case EXPR_MOD:
 270             Left  = GetExprVal (Expr->Left);
 271             Right = GetExprVal (Expr->Right);
 272             if (Right == 0) {
 273                 Error ("Modulo operation with zero");
 274             }
 275             return Left % Right;
 276
 277         case EXPR_OR:
 278             return GetExprVal (Expr->Left) | GetExprVal (Expr->Right);
 279
 280         case EXPR_XOR:
 281             return GetExprVal (Expr->Left) ^ GetExprVal (Expr->Right);
 282
 283         case EXPR_AND:
 284             return GetExprVal (Expr->Left) & GetExprVal (Expr->Right);
 285
 286         case EXPR_SHL:
 287             return GetExprVal (Expr->Left) << GetExprVal (Expr->Right);
 288
 289         case EXPR_SHR:
 290             return GetExprVal (Expr->Left) >> GetExprVal (Expr->Right);
 291
 292         case EXPR_EQ:
 293             return (GetExprVal (Expr->Left) == GetExprVal (Expr->Right));
 294
 295         case EXPR_NE:
 296             return (GetExprVal (Expr->Left) != GetExprVal (Expr->Right));
 297
 298         case EXPR_LT:
 299             return (GetExprVal (Expr->Left) < GetExprVal (Expr->Right));
 300
 301         case EXPR_GT:
 302             return (GetExprVal (Expr->Left) > GetExprVal (Expr->Right));
 303
 304         case EXPR_LE:
 305             return (GetExprVal (Expr->Left) <= GetExprVal (Expr->Right));
 306
 307         case EXPR_GE:
 308             return (GetExprVal (Expr->Left) >= GetExprVal (Expr->Right));
 309
 310         case EXPR_UNARY_MINUS:
 311             return -GetExprVal (Expr->Left);
 312
 313         case EXPR_NOT:
 314             return ~GetExprVal (Expr->Left);
 315
 316         case EXPR_BYTE0:
 317             return GetExprVal (Expr->Left) & 0xFF;
 318
 319         case EXPR_BYTE1:
 320             return (GetExprVal (Expr->Left) >> 8) & 0xFF;
 321
 322         case EXPR_BYTE2:
 323             return (GetExprVal (Expr->Left) >> 16) & 0xFF;
 324
 325         case EXPR_BYTE3:
 326             return (GetExprVal (Expr->Left) >> 24) & 0xFF;
 327
 328         case EXPR_SWAP:
 329             Left = GetExprVal (Expr->Left);
 330             return ((Left >> 8) & 0x00FF) | ((Left << 8) & 0xFF00);
 331
 332         case EXPR_BAND:
 333             return GetExprVal (Expr->Left) && GetExprVal (Expr->Right);
 334
 335         case EXPR_BOR:
 336             return GetExprVal (Expr->Left) || GetExprVal (Expr->Right);
 337
 338         case EXPR_BXOR:
 339             return (GetExprVal (Expr->Left) != 0) ^ (GetExprVal (Expr->Right) != 0);
 340
 341         case EXPR_BNOT:
 342             return !GetExprVal (Expr->Left);
 343
 344         default:
 345             Internal ("Unknown expression Op type: %u", Expr->Op);
 346             /* NOTREACHED */
 347             return 0;
 348     }
 349 }
 350
 351
 352
 353 ExprNode* LiteralExpr (long Val, ObjData* O)
 354 /* Return an expression tree that encodes the given literal value */
 355 {
 356     ExprNode* Expr = NewExprNode (O);
 357     Expr->Op = EXPR_LITERAL;
 358     Expr->V.Val = Val;
 359     return Expr;
 360 }
 361
 362
 363
 364 ExprNode* MemExpr (Memory* Mem, long Offs, ObjData* O)
 365 /* Return an expression tree that encodes an offset into the memory area */
 366 {
 367     ExprNode* Root;
 368
 369     ExprNode* Expr = NewExprNode (O);
 370     Expr->Op = EXPR_MEMAREA;
 371     Expr->V.MemArea = Mem;
 372
 373     Root = NewExprNode (O);
 374     Root->Op = EXPR_PLUS;
 375     Root->Left = Expr;
 376     Root->Right = LiteralExpr (Offs, O);
 377
 378     return Root;
 379 }
 380
 381
 382
 383 ExprNode* ReadExpr (FILE* F, ObjData* O)
 384 /* Read an expression from the given file */
 385 {
 386     ExprNode* Expr;
 387
 388     /* Read the node tag and handle NULL nodes */
 389     unsigned char Op = Read8 (F);
 390     if (Op == EXPR_NULL) {
 391         return 0;
 392     }
 393
 394     /* Create a new node */
 395     Expr = NewExprNode (O);
 396     Expr->Op = Op;
 397
 398     /* Check the tag and handle the different expression types */
 399     if (EXPR_IS_LEAF (Op)) {
 400         switch (Op) {
 401
 402             case EXPR_LITERAL:
 403                 Expr->V.Val = Read32Signed (F);
 404                 break;
 405
 406             case EXPR_SYMBOL:
 407                 /* Read the import number */
 408                 Expr->V.ImpNum = Read16 (F);
 409                 break;
 410
 411             case EXPR_SEGMENT:
 412                 /* Read the segment number */
 413                 Expr->V.SegNum = Read8 (F);
 414                 break;
 415
 416             default:
 417                 Error ("Invalid expression op: %02X", Op);
 418
 419         }
 420
 421     } else {
 422
 423         /* Not a leaf node */
 424         Expr->Left = ReadExpr (F, O);
 425         Expr->Right = ReadExpr (F, O);
 426
 427     }
 428
 429     /* Return the tree */
 430     return Expr;
 431 }
 432
 433
 434
 435 int EqualExpr (ExprNode* E1, ExprNode* E2)
 436 /* Check if two expressions are identical. */
 437 {
 438     /* If one pointer is NULL, both must be NULL */
 439     if ((E1 == 0) ^ (E2 == 0)) {
 440         return 0;
 441     }
 442     if (E1 == 0) {
 443         return 1;
 444     }
 445
 446     /* Both pointers not NULL, check OP */
 447     if (E1->Op != E2->Op) {
 448         return 0;
 449     }
 450
 451     /* OPs are identical, check data for leafs, or subtrees */
 452     switch (E1->Op) {
 453
 454         case EXPR_LITERAL:
 455             /* Value must be identical */
 456             return (E1->V.Val == E2->V.Val);
 457
 458         case EXPR_SYMBOL:
 459             /* Import number must be identical */
 460             return (E1->V.ImpNum == E2->V.ImpNum);
 461
 462         case EXPR_SEGMENT:
 463             /* Segment number must be identical */
 464             return (E1->V.SegNum == E2->V.SegNum);
 465
 466         case EXPR_MEMAREA:
 467             /* Memory area must be identical */
 468             return (E1->V.MemArea == E2->V.MemArea);
 469
 470         default:
 471             /* Not a leaf node */
 472             return EqualExpr (E1->Left, E2->Left) && EqualExpr (E1->Right, E2->Right);
 473     }
 474
 475 }
 476
 477
 478
 479
 480
 481
 482
 483
 484
 485
 486
 487
 488
 489
 490
 491
 492