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 /* Anything else is not const */
151 } else if (EXPR_IS_UNARY (Root->Op)) {
155 /* Special handling for the BANK pseudo function */
159 /* Get segment references for the expression */
160 GetSegExprVal (Root->Left, &D);
162 /* The expression is const if the expression contains exactly
163 ** one segment that is assigned to a memory area which has a
164 ** bank attribute that is constant.
166 return (D.TooComplex == 0 &&
168 D.Seg->MemArea != 0 &&
169 D.Seg->MemArea->BankExpr != 0 &&
170 IsConstExpr (D.Seg->MemArea->BankExpr));
173 /* All others handled normal */
174 return IsConstExpr (Root->Left);
180 /* We must handle shortcut boolean expressions here */
184 if (IsConstExpr (Root->Left)) {
185 /* lhs is const, if it is zero, don't eval right */
186 if (GetExprVal (Root->Left) == 0) {
189 return IsConstExpr (Root->Right);
192 /* lhs not const --> tree not const */
198 if (IsConstExpr (Root->Left)) {
199 /* lhs is const, if it is not zero, don't eval right */
200 if (GetExprVal (Root->Left) != 0) {
203 return IsConstExpr (Root->Right);
206 /* lhs not const --> tree not const */
212 /* All others are handled normal */
213 return IsConstExpr (Root->Left) && IsConstExpr (Root->Right);
220 Import* GetExprImport (ExprNode* Expr)
221 /* Get the import data structure for a symbol expression node */
223 /* Check that this is really a symbol */
224 PRECONDITION (Expr->Op == EXPR_SYMBOL);
226 /* If we have an object file, get the import from it, otherwise
227 ** (internally generated expressions), get the import from the
231 /* Return the Import */
232 return GetObjImport (Expr->Obj, Expr->V.ImpNum);
240 Export* GetExprExport (ExprNode* Expr)
241 /* Get the exported symbol for a symbol expression node */
243 /* Check that this is really a symbol */
244 PRECONDITION (Expr->Op == EXPR_SYMBOL);
246 /* Return the export for an import*/
247 return GetExprImport (Expr)->Exp;
252 Section* GetExprSection (ExprNode* Expr)
253 /* Get the segment for a section expression node */
255 /* Check that this is really a section node */
256 PRECONDITION (Expr->Op == EXPR_SECTION);
258 /* If we have an object file, get the section from it, otherwise
259 ** (internally generated expressions), get the section from the
263 /* Return the export */
264 return CollAt (&Expr->Obj->Sections, Expr->V.SecNum);
272 long GetExprVal (ExprNode* Expr)
273 /* Get the value of a constant expression */
288 /* Get the referenced export */
289 E = GetExprExport (Expr);
290 /* If this export has a mark set, we've already encountered it.
291 ** This means that the export is used to define it's own value,
292 ** which in turn means, that we have a circular reference.
294 if (ExportHasMark (E)) {
295 CircularRefError (E);
299 Val = GetExportVal (E);
305 S = GetExprSection (Expr);
306 return S->Offs + S->Seg->PC;
309 return Expr->V.Seg->PC;
312 return Expr->V.Mem->Start;
315 return GetExprVal (Expr->Left) + GetExprVal (Expr->Right);
318 return GetExprVal (Expr->Left) - GetExprVal (Expr->Right);
321 return GetExprVal (Expr->Left) * GetExprVal (Expr->Right);
324 Left = GetExprVal (Expr->Left);
325 Right = GetExprVal (Expr->Right);
327 Error ("Division by zero");
332 Left = GetExprVal (Expr->Left);
333 Right = GetExprVal (Expr->Right);
335 Error ("Modulo operation with zero");
340 return GetExprVal (Expr->Left) | GetExprVal (Expr->Right);
343 return GetExprVal (Expr->Left) ^ GetExprVal (Expr->Right);
346 return GetExprVal (Expr->Left) & GetExprVal (Expr->Right);
349 return GetExprVal (Expr->Left) << GetExprVal (Expr->Right);
352 return GetExprVal (Expr->Left) >> GetExprVal (Expr->Right);
355 return (GetExprVal (Expr->Left) == GetExprVal (Expr->Right));
358 return (GetExprVal (Expr->Left) != GetExprVal (Expr->Right));
361 return (GetExprVal (Expr->Left) < GetExprVal (Expr->Right));
364 return (GetExprVal (Expr->Left) > GetExprVal (Expr->Right));
367 return (GetExprVal (Expr->Left) <= GetExprVal (Expr->Right));
370 return (GetExprVal (Expr->Left) >= GetExprVal (Expr->Right));
373 return GetExprVal (Expr->Left) && GetExprVal (Expr->Right);
376 return GetExprVal (Expr->Left) || GetExprVal (Expr->Right);
379 return (GetExprVal (Expr->Left) != 0) ^ (GetExprVal (Expr->Right) != 0);
382 Left = GetExprVal (Expr->Left);
383 Right = GetExprVal (Expr->Right);
384 return (Left > Right)? Left : Right;
387 Left = GetExprVal (Expr->Left);
388 Right = GetExprVal (Expr->Right);
389 return (Left < Right)? Left : Right;
391 case EXPR_UNARY_MINUS:
392 return -GetExprVal (Expr->Left);
395 return ~GetExprVal (Expr->Left);
398 Left = GetExprVal (Expr->Left);
399 return ((Left >> 8) & 0x00FF) | ((Left << 8) & 0xFF00);
402 return !GetExprVal (Expr->Left);
405 GetSegExprVal (Expr->Left, &D);
406 if (D.TooComplex || D.Seg == 0) {
407 Error ("Argument for .BANK is not segment relative or too complex");
409 if (D.Seg->MemArea == 0) {
410 Error ("Segment `%s' is referenced by .BANK but "
411 "not assigned to a memory area",
412 GetString (D.Seg->Name));
414 if (D.Seg->MemArea->BankExpr == 0) {
415 Error ("Memory area `%s' is referenced by .BANK but "
416 "has no BANK attribute",
417 GetString (D.Seg->MemArea->Name));
419 return GetExprVal (D.Seg->MemArea->BankExpr);
422 return GetExprVal (Expr->Left) & 0xFF;
425 return (GetExprVal (Expr->Left) >> 8) & 0xFF;
428 return (GetExprVal (Expr->Left) >> 16) & 0xFF;
431 return (GetExprVal (Expr->Left) >> 24) & 0xFF;
434 return GetExprVal (Expr->Left) & 0xFFFF;
437 return (GetExprVal (Expr->Left) >> 16) & 0xFFFF;
440 return GetExprVal (Expr->Left) & 0xFFFFFF;
443 return GetExprVal (Expr->Left) & 0xFFFFFFFF;
446 Internal ("Unknown expression Op type: %u", Expr->Op);
454 static void GetSegExprValInternal (ExprNode* Expr, SegExprDesc* D, int Sign)
455 /* Check if the given expression consists of a segment reference and only
456 ** constant values, additions and subtractions. If anything else is found,
457 ** set D->TooComplex to true.
458 ** Internal, recursive routine.
466 D->Val += (Sign * Expr->V.IVal);
470 /* Get the referenced export */
471 E = GetExprExport (Expr);
472 /* If this export has a mark set, we've already encountered it.
473 ** This means that the export is used to define it's own value,
474 ** which in turn means, that we have a circular reference.
476 if (ExportHasMark (E)) {
477 CircularRefError (E);
480 GetSegExprValInternal (E->Expr, D, Sign);
487 /* We cannot handle more than one segment reference in o65 */
490 /* Get the section from the expression */
491 Section* S = GetExprSection (Expr);
492 /* Remember the segment reference */
494 /* Add the offset of the section to the constant value */
495 D->Val += Sign * (S->Offs + D->Seg->PC);
501 /* We cannot handle more than one segment reference in o65 */
504 /* Remember the segment reference */
505 D->Seg = Expr->V.Seg;
506 /* Add the offset of the segment to the constant value */
507 D->Val += (Sign * D->Seg->PC);
512 GetSegExprValInternal (Expr->Left, D, Sign);
513 GetSegExprValInternal (Expr->Right, D, Sign);
517 GetSegExprValInternal (Expr->Left, D, Sign);
518 GetSegExprValInternal (Expr->Right, D, -Sign);
522 /* Expression contains illegal operators */
531 void GetSegExprVal (ExprNode* Expr, SegExprDesc* D)
532 /* Check if the given expression consists of a segment reference and only
533 ** constant values, additions and subtractions. If anything else is found,
534 ** set D->TooComplex to true. The function will initialize D.
537 /* Initialize the given structure */
542 /* Call our recursive calculation routine */
543 GetSegExprValInternal (Expr, D, 1);
548 ExprNode* LiteralExpr (long Val, ObjData* O)
549 /* Return an expression tree that encodes the given literal value */
551 ExprNode* Expr = NewExprNode (O, EXPR_LITERAL);
558 ExprNode* MemoryExpr (MemoryArea* Mem, long Offs, ObjData* O)
559 /* Return an expression tree that encodes an offset into a memory area */
563 ExprNode* Expr = NewExprNode (O, EXPR_MEMAREA);
567 Root = NewExprNode (O, EXPR_PLUS);
569 Root->Right = LiteralExpr (Offs, O);
579 ExprNode* SegmentExpr (Segment* Seg, long Offs, ObjData* O)
580 /* Return an expression tree that encodes an offset into a segment */
584 ExprNode* Expr = NewExprNode (O, EXPR_SEGMENT);
588 Root = NewExprNode (O, EXPR_PLUS);
590 Root->Right = LiteralExpr (Offs, O);
600 ExprNode* SectionExpr (Section* Sec, long Offs, ObjData* O)
601 /* Return an expression tree that encodes an offset into a section */
605 ExprNode* Expr = NewExprNode (O, EXPR_SECTION);
609 Root = NewExprNode (O, EXPR_PLUS);
611 Root->Right = LiteralExpr (Offs, O);
621 ExprNode* ReadExpr (FILE* F, ObjData* O)
622 /* Read an expression from the given file */
626 /* Read the node tag and handle NULL nodes */
627 unsigned char Op = Read8 (F);
628 if (Op == EXPR_NULL) {
632 /* Create a new node */
633 Expr = NewExprNode (O, Op);
635 /* Check the tag and handle the different expression types */
636 if (EXPR_IS_LEAF (Op)) {
640 Expr->V.IVal = Read32Signed (F);
644 /* Read the import number */
645 Expr->V.ImpNum = ReadVar (F);
649 /* Read the section number */
650 Expr->V.SecNum = ReadVar (F);
654 Error ("Invalid expression op: %02X", Op);
660 /* Not a leaf node */
661 Expr->Left = ReadExpr (F, O);
662 Expr->Right = ReadExpr (F, O);
666 /* Return the tree */
672 int EqualExpr (ExprNode* E1, ExprNode* E2)
673 /* Check if two expressions are identical. */
675 /* If one pointer is NULL, both must be NULL */
676 if ((E1 == 0) ^ (E2 == 0)) {
683 /* Both pointers not NULL, check OP */
684 if (E1->Op != E2->Op) {
688 /* OPs are identical, check data for leafs, or subtrees */
692 /* Value must be identical */
693 return (E1->V.IVal == E2->V.IVal);
696 /* Import must be identical */
697 return (GetExprImport (E1) == GetExprImport (E2));
700 /* Section must be identical */
701 return (GetExprSection (E1) == GetExprSection (E2));
704 /* Segment must be identical */
705 return (E1->V.Seg == E2->V.Seg);
708 /* Memory area must be identical */
709 return (E1->V.Mem == E2->V.Mem);
712 /* Not a leaf node */
713 return EqualExpr (E1->Left, E2->Left) && EqualExpr (E1->Right, E2->Right);