1 /*****************************************************************************/
5 /* Expression evaluation for the ld65 linker */
9 /* (C) 1998-2012, Ullrich von Bassewitz */
10 /* Roemerstrasse 52 */
11 /* D-70794 Filderstadt */
12 /* EMail: uz@cc65.org */
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. */
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: */
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 */
32 /*****************************************************************************/
51 /*****************************************************************************/
53 /*****************************************************************************/
57 ExprNode* NewExprNode (ObjData* O, unsigned char Op)
58 /* Create a new expression node */
60 /* Allocate fresh memory */
61 ExprNode* N = xmalloc (sizeof (ExprNode));
73 static void FreeExprNode (ExprNode* E)
82 void FreeExpr (ExprNode* Root)
83 /* Free the expression, Root is pointing to. */
86 FreeExpr (Root->Left);
87 FreeExpr (Root->Right);
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.
104 if (EXPR_IS_LEAF (Root->Op)) {
111 /* Get the referenced export */
112 E = GetExprExport (Root);
113 /* If this export has a mark set, we've already encountered it.
114 * This means that the export is used to define it's own value,
115 * which in turn means, that we have a circular reference.
117 if (ExportHasMark (E)) {
118 CircularRefError (E);
122 Const = IsConstExport (E);
128 /* A section expression is const if the segment it is in is
129 * not relocatable and already placed.
131 S = GetExprSection (Root);
133 return M != 0 && (M->Flags & MF_PLACED) != 0 && !M->Relocatable;
136 /* A segment is const if it is not relocatable and placed */
137 M = Root->V.Seg->MemArea;
138 return M != 0 && (M->Flags & MF_PLACED) != 0 && !M->Relocatable;
141 /* A memory area is const if it is not relocatable and placed */
142 return !Root->V.Mem->Relocatable &&
143 (Root->V.Mem->Flags & MF_PLACED);
146 /* A bank expression is const if the section, the segment is
147 * part of, is already placed, and the memory area has a
148 * constant bank expression.
150 S = GetExprSection (Root);
152 return M != 0 && (M->Flags & MF_PLACED) != 0 &&
153 M->BankExpr != 0 && IsConstExpr (M->BankExpr);
156 /* Anything else is not const */
161 } else if (EXPR_IS_UNARY (Root->Op)) {
163 return IsConstExpr (Root->Left);
167 /* We must handle shortcut boolean expressions here */
171 if (IsConstExpr (Root->Left)) {
172 /* lhs is const, if it is zero, don't eval right */
173 if (GetExprVal (Root->Left) == 0) {
176 return IsConstExpr (Root->Right);
179 /* lhs not const --> tree not const */
185 if (IsConstExpr (Root->Left)) {
186 /* lhs is const, if it is not zero, don't eval right */
187 if (GetExprVal (Root->Left) != 0) {
190 return IsConstExpr (Root->Right);
193 /* lhs not const --> tree not const */
199 /* All others are handled normal */
200 return IsConstExpr (Root->Left) && IsConstExpr (Root->Right);
207 Import* GetExprImport (ExprNode* Expr)
208 /* Get the import data structure for a symbol expression node */
210 /* Check that this is really a symbol */
211 PRECONDITION (Expr->Op == EXPR_SYMBOL);
213 /* If we have an object file, get the import from it, otherwise
214 * (internally generated expressions), get the import from the
218 /* Return the Import */
219 return GetObjImport (Expr->Obj, Expr->V.ImpNum);
227 Export* GetExprExport (ExprNode* Expr)
228 /* Get the exported symbol for a symbol expression node */
230 /* Check that this is really a symbol */
231 PRECONDITION (Expr->Op == EXPR_SYMBOL);
233 /* Return the export for an import*/
234 return GetExprImport (Expr)->Exp;
239 Section* GetExprSection (ExprNode* Expr)
240 /* Get the segment for a section expression node */
242 /* Check that this is really a section node */
243 PRECONDITION (Expr->Op == EXPR_SECTION || Expr->Op == EXPR_BANK);
245 /* If we have an object file, get the section from it, otherwise
246 * (internally generated expressions), get the section from the
250 /* Return the export */
251 return CollAt (&Expr->Obj->Sections, Expr->V.SecNum);
259 long GetExprVal (ExprNode* Expr)
260 /* Get the value of a constant expression */
274 /* Get the referenced export */
275 E = GetExprExport (Expr);
276 /* If this export has a mark set, we've already encountered it.
277 * This means that the export is used to define it's own value,
278 * which in turn means, that we have a circular reference.
280 if (ExportHasMark (E)) {
281 CircularRefError (E);
285 Val = GetExportVal (E);
291 S = GetExprSection (Expr);
292 return S->Offs + S->Seg->PC;
295 return Expr->V.Seg->PC;
298 return Expr->V.Mem->Start;
301 S = GetExprSection (Expr);
302 return GetExprVal (S->Seg->MemArea->BankExpr);
305 return GetExprVal (Expr->Left) + GetExprVal (Expr->Right);
308 return GetExprVal (Expr->Left) - GetExprVal (Expr->Right);
311 return GetExprVal (Expr->Left) * GetExprVal (Expr->Right);
314 Left = GetExprVal (Expr->Left);
315 Right = GetExprVal (Expr->Right);
317 Error ("Division by zero");
322 Left = GetExprVal (Expr->Left);
323 Right = GetExprVal (Expr->Right);
325 Error ("Modulo operation with zero");
330 return GetExprVal (Expr->Left) | GetExprVal (Expr->Right);
333 return GetExprVal (Expr->Left) ^ GetExprVal (Expr->Right);
336 return GetExprVal (Expr->Left) & GetExprVal (Expr->Right);
339 return GetExprVal (Expr->Left) << GetExprVal (Expr->Right);
342 return GetExprVal (Expr->Left) >> GetExprVal (Expr->Right);
345 return (GetExprVal (Expr->Left) == GetExprVal (Expr->Right));
348 return (GetExprVal (Expr->Left) != GetExprVal (Expr->Right));
351 return (GetExprVal (Expr->Left) < GetExprVal (Expr->Right));
354 return (GetExprVal (Expr->Left) > GetExprVal (Expr->Right));
357 return (GetExprVal (Expr->Left) <= GetExprVal (Expr->Right));
360 return (GetExprVal (Expr->Left) >= GetExprVal (Expr->Right));
363 return GetExprVal (Expr->Left) && GetExprVal (Expr->Right);
366 return GetExprVal (Expr->Left) || GetExprVal (Expr->Right);
369 return (GetExprVal (Expr->Left) != 0) ^ (GetExprVal (Expr->Right) != 0);
372 Left = GetExprVal (Expr->Left);
373 Right = GetExprVal (Expr->Right);
374 return (Left > Right)? Left : Right;
377 Left = GetExprVal (Expr->Left);
378 Right = GetExprVal (Expr->Right);
379 return (Left < Right)? Left : Right;
381 case EXPR_UNARY_MINUS:
382 return -GetExprVal (Expr->Left);
385 return ~GetExprVal (Expr->Left);
388 Left = GetExprVal (Expr->Left);
389 return ((Left >> 8) & 0x00FF) | ((Left << 8) & 0xFF00);
392 return !GetExprVal (Expr->Left);
395 return GetExprVal (Expr->Left) & 0xFF;
398 return (GetExprVal (Expr->Left) >> 8) & 0xFF;
401 return (GetExprVal (Expr->Left) >> 16) & 0xFF;
404 return (GetExprVal (Expr->Left) >> 24) & 0xFF;
407 return GetExprVal (Expr->Left) & 0xFFFF;
410 return (GetExprVal (Expr->Left) >> 16) & 0xFFFF;
413 return GetExprVal (Expr->Left) & 0xFFFFFF;
416 return GetExprVal (Expr->Left) & 0xFFFFFFFF;
419 Internal ("Unknown expression Op type: %u", Expr->Op);
427 static void GetSegExprValInternal (ExprNode* Expr, SegExprDesc* D, int Sign)
428 /* Check if the given expression consists of a segment reference and only
429 * constant values, additions and subtractions. If anything else is found,
430 * set D->TooComplex to true.
431 * Internal, recursive routine.
439 D->Val += (Sign * Expr->V.IVal);
443 /* Get the referenced export */
444 E = GetExprExport (Expr);
445 /* If this export has a mark set, we've already encountered it.
446 * This means that the export is used to define it's own value,
447 * which in turn means, that we have a circular reference.
449 if (ExportHasMark (E)) {
450 CircularRefError (E);
453 GetSegExprValInternal (E->Expr, D, Sign);
460 /* We cannot handle more than one segment reference in o65 */
463 /* Get the section from the expression */
464 Section* S = GetExprSection (Expr);
465 /* Remember the segment reference */
467 /* Add the offset of the section to the constant value */
468 D->Val += Sign * (S->Offs + D->Seg->PC);
474 /* We cannot handle more than one segment reference in o65 */
477 /* Remember the segment reference */
478 D->Seg = Expr->V.Seg;
479 /* Add the offset of the segment to the constant value */
480 D->Val += (Sign * D->Seg->PC);
485 GetSegExprValInternal (Expr->Left, D, Sign);
486 GetSegExprValInternal (Expr->Right, D, Sign);
490 GetSegExprValInternal (Expr->Left, D, Sign);
491 GetSegExprValInternal (Expr->Right, D, -Sign);
495 /* Expression contains illegal operators */
504 void GetSegExprVal (ExprNode* Expr, SegExprDesc* D)
505 /* Check if the given expression consists of a segment reference and only
506 * constant values, additions and subtractions. If anything else is found,
507 * set D->TooComplex to true. The function will initialize D.
510 /* Initialize the given structure */
515 /* Call our recursive calculation routine */
516 GetSegExprValInternal (Expr, D, 1);
521 ExprNode* LiteralExpr (long Val, ObjData* O)
522 /* Return an expression tree that encodes the given literal value */
524 ExprNode* Expr = NewExprNode (O, EXPR_LITERAL);
531 ExprNode* MemoryExpr (MemoryArea* Mem, long Offs, ObjData* O)
532 /* Return an expression tree that encodes an offset into a memory area */
536 ExprNode* Expr = NewExprNode (O, EXPR_MEMAREA);
540 Root = NewExprNode (O, EXPR_PLUS);
542 Root->Right = LiteralExpr (Offs, O);
552 ExprNode* SegmentExpr (Segment* Seg, long Offs, ObjData* O)
553 /* Return an expression tree that encodes an offset into a segment */
557 ExprNode* Expr = NewExprNode (O, EXPR_SEGMENT);
561 Root = NewExprNode (O, EXPR_PLUS);
563 Root->Right = LiteralExpr (Offs, O);
573 ExprNode* SectionExpr (Section* Sec, long Offs, ObjData* O)
574 /* Return an expression tree that encodes an offset into a section */
578 ExprNode* Expr = NewExprNode (O, EXPR_SECTION);
582 Root = NewExprNode (O, EXPR_PLUS);
584 Root->Right = LiteralExpr (Offs, O);
594 ExprNode* ReadExpr (FILE* F, ObjData* O)
595 /* Read an expression from the given file */
599 /* Read the node tag and handle NULL nodes */
600 unsigned char Op = Read8 (F);
601 if (Op == EXPR_NULL) {
605 /* Create a new node */
606 Expr = NewExprNode (O, Op);
608 /* Check the tag and handle the different expression types */
609 if (EXPR_IS_LEAF (Op)) {
613 Expr->V.IVal = Read32Signed (F);
617 /* Read the import number */
618 Expr->V.ImpNum = ReadVar (F);
623 /* Read the section number */
624 Expr->V.SecNum = ReadVar (F);
628 Error ("Invalid expression op: %02X", Op);
634 /* Not a leaf node */
635 Expr->Left = ReadExpr (F, O);
636 Expr->Right = ReadExpr (F, O);
640 /* Return the tree */
646 int EqualExpr (ExprNode* E1, ExprNode* E2)
647 /* Check if two expressions are identical. */
649 /* If one pointer is NULL, both must be NULL */
650 if ((E1 == 0) ^ (E2 == 0)) {
657 /* Both pointers not NULL, check OP */
658 if (E1->Op != E2->Op) {
662 /* OPs are identical, check data for leafs, or subtrees */
666 /* Value must be identical */
667 return (E1->V.IVal == E2->V.IVal);
670 /* Import must be identical */
671 return (GetExprImport (E1) == GetExprImport (E2));
674 /* Section must be identical */
675 return (GetExprSection (E1) == GetExprSection (E2));
678 /* Segment must be identical */
679 return (E1->V.Seg == E2->V.Seg);
682 /* Memory area must be identical */
683 return (E1->V.Mem == E2->V.Mem);
686 /* Not a leaf node */
687 return EqualExpr (E1->Left, E2->Left) && EqualExpr (E1->Right, E2->Right);