1 /*****************************************************************************/
5 /* Expression evaluation for the ld65 linker */
9 /* (C) 1998-2003 Ullrich von Bassewitz */
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 /*****************************************************************************/
50 /*****************************************************************************/
52 /*****************************************************************************/
56 static ExprNode* NewExprNode (ObjData* O)
57 /* Create a new expression node */
59 /* Allocate fresh memory */
60 ExprNode* N = xmalloc (sizeof (ExprNode));
72 static void FreeExprNode (ExprNode* E)
81 /*****************************************************************************/
83 /*****************************************************************************/
87 void FreeExpr (ExprNode* Root)
88 /* Free the expression, Root is pointing to. */
91 FreeExpr (Root->Left);
92 FreeExpr (Root->Right);
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.
108 if (EXPR_IS_LEAF (Root->Op)) {
115 /* Get the referenced export */
116 E = GetExprExport (Root);
117 /* If this export has a mark set, we've already encountered it.
118 * This means that the export is used to define it's own value,
119 * which in turn means, that we have a circular reference.
121 if (ExportHasMark (E)) {
122 CircularRefError (E);
126 Const = IsConstExport (E);
132 /* A section expression is const if the segment it is in is
135 S = GetExprSection (Root);
136 return !S->Seg->Relocatable;
139 /* A segment is const if it is not relocatable */
140 return !Root->V.Seg->Relocatable;
143 /* A memory area is const if it is not relocatable */
144 return !Root->V.Mem->Relocatable;
147 /* Anything else is not const */
151 } else if (EXPR_IS_UNARY (Root->Op)) {
153 return IsConstExpr (Root->Left);
157 /* We must handle shortcut boolean expressions here */
161 if (IsConstExpr (Root->Left)) {
162 /* lhs is const, if it is zero, don't eval right */
163 if (GetExprVal (Root->Left) == 0) {
166 return IsConstExpr (Root->Right);
169 /* lhs not const --> tree not const */
175 if (IsConstExpr (Root->Left)) {
176 /* lhs is const, if it is not zero, don't eval right */
177 if (GetExprVal (Root->Left) != 0) {
180 return IsConstExpr (Root->Right);
183 /* lhs not const --> tree not const */
189 /* All others are handled normal */
190 return IsConstExpr (Root->Left) && IsConstExpr (Root->Right);
197 Import* GetExprImport (ExprNode* Expr)
198 /* Get the import data structure for a symbol expression node */
200 /* Check that this is really a symbol */
201 PRECONDITION (Expr->Op == EXPR_SYMBOL);
203 /* Return the import */
204 return Expr->Obj->Imports [Expr->V.ImpNum];
209 Export* GetExprExport (ExprNode* Expr)
210 /* Get the exported symbol for a symbol expression node */
212 /* Check that this is really a symbol */
213 PRECONDITION (Expr->Op == EXPR_SYMBOL);
215 /* Return the export */
216 return Expr->Obj->Imports [Expr->V.ImpNum]->Exp;
221 Section* GetExprSection (ExprNode* Expr)
222 /* Get the segment for a section expression node */
224 /* Check that this is really a section node */
225 PRECONDITION (Expr->Op == EXPR_SECTION);
227 /* If we have an object file, get the section from it, otherwise
228 * (internally generated expressions), get the section from the
232 /* Return the export */
233 return Expr->Obj->Sections[Expr->V.SegNum];
241 long GetExprVal (ExprNode* Expr)
242 /* Get the value of a constant expression */
244 long Right, Left, Val;
254 /* Get the referenced export */
255 E = GetExprExport (Expr);
256 /* If this export has a mark set, we've already encountered it.
257 * This means that the export is used to define it's own value,
258 * which in turn means, that we have a circular reference.
260 if (ExportHasMark (E)) {
261 CircularRefError (E);
265 Val = GetExportVal (E);
271 S = GetExprSection (Expr);
272 return S->Offs + S->Seg->PC;
275 return Expr->V.Seg->PC;
278 return Expr->V.Mem->Start;
281 return GetExprVal (Expr->Left) + GetExprVal (Expr->Right);
284 return GetExprVal (Expr->Left) - GetExprVal (Expr->Right);
287 return GetExprVal (Expr->Left) * GetExprVal (Expr->Right);
290 Left = GetExprVal (Expr->Left);
291 Right = GetExprVal (Expr->Right);
293 Error ("Division by zero");
298 Left = GetExprVal (Expr->Left);
299 Right = GetExprVal (Expr->Right);
301 Error ("Modulo operation with zero");
306 return GetExprVal (Expr->Left) | GetExprVal (Expr->Right);
309 return GetExprVal (Expr->Left) ^ GetExprVal (Expr->Right);
312 return GetExprVal (Expr->Left) & GetExprVal (Expr->Right);
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 return (GetExprVal (Expr->Left) != GetExprVal (Expr->Right));
327 return (GetExprVal (Expr->Left) < GetExprVal (Expr->Right));
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) != 0) ^ (GetExprVal (Expr->Right) != 0);
347 case EXPR_UNARY_MINUS:
348 return -GetExprVal (Expr->Left);
351 return ~GetExprVal (Expr->Left);
354 Left = GetExprVal (Expr->Left);
355 return ((Left >> 8) & 0x00FF) | ((Left << 8) & 0xFF00);
358 return !GetExprVal (Expr->Left);
361 return GetExprVal (Expr->Left) & 0xFF;
364 return (GetExprVal (Expr->Left) >> 8) & 0xFF;
367 return (GetExprVal (Expr->Left) >> 16) & 0xFF;
370 return (GetExprVal (Expr->Left) >> 24) & 0xFF;
373 return GetExprVal (Expr->Left) & 0xFFFF;
376 return (GetExprVal (Expr->Left) >> 16) & 0xFFFF;
379 Internal ("Unknown expression Op type: %u", Expr->Op);
387 ExprNode* LiteralExpr (long Val, ObjData* O)
388 /* Return an expression tree that encodes the given literal value */
390 ExprNode* Expr = NewExprNode (O);
391 Expr->Op = EXPR_LITERAL;
398 ExprNode* MemoryExpr (Memory* Mem, long Offs, ObjData* O)
399 /* Return an expression tree that encodes an offset into a memory area */
403 ExprNode* Expr = NewExprNode (O);
404 Expr->Op = EXPR_MEMAREA;
408 Root = NewExprNode (O);
409 Root->Op = EXPR_PLUS;
411 Root->Right = LiteralExpr (Offs, O);
421 ExprNode* SegmentExpr (Segment* Seg, long Offs, ObjData* O)
422 /* Return an expression tree that encodes an offset into a segment */
426 ExprNode* Expr = NewExprNode (O);
427 Expr->Op = EXPR_SEGMENT;
431 Root = NewExprNode (O);
432 Root->Op = EXPR_PLUS;
434 Root->Right = LiteralExpr (Offs, O);
444 ExprNode* SectionExpr (Section* Sec, long Offs, ObjData* O)
445 /* Return an expression tree that encodes an offset into a section */
449 ExprNode* Expr = NewExprNode (O);
450 Expr->Op = EXPR_SECTION;
454 Root = NewExprNode (O);
455 Root->Op = EXPR_PLUS;
457 Root->Right = LiteralExpr (Offs, O);
467 ExprNode* ReadExpr (FILE* F, ObjData* O)
468 /* Read an expression from the given file */
472 /* Read the node tag and handle NULL nodes */
473 unsigned char Op = Read8 (F);
474 if (Op == EXPR_NULL) {
478 /* Create a new node */
479 Expr = NewExprNode (O);
482 /* Check the tag and handle the different expression types */
483 if (EXPR_IS_LEAF (Op)) {
487 Expr->V.Val = Read32Signed (F);
491 /* Read the import number */
492 Expr->V.ImpNum = ReadVar (F);
496 /* Read the segment number */
497 Expr->V.SegNum = Read8 (F);
501 Error ("Invalid expression op: %02X", Op);
507 /* Not a leaf node */
508 Expr->Left = ReadExpr (F, O);
509 Expr->Right = ReadExpr (F, O);
513 /* Return the tree */
519 int EqualExpr (ExprNode* E1, ExprNode* E2)
520 /* Check if two expressions are identical. */
522 /* If one pointer is NULL, both must be NULL */
523 if ((E1 == 0) ^ (E2 == 0)) {
530 /* Both pointers not NULL, check OP */
531 if (E1->Op != E2->Op) {
535 /* OPs are identical, check data for leafs, or subtrees */
539 /* Value must be identical */
540 return (E1->V.Val == E2->V.Val);
543 /* Import number must be identical */
544 return (E1->V.ImpNum == E2->V.ImpNum);
547 /* Section must be identical */
548 return (GetExprSection (E1) == GetExprSection (E2));
551 /* Segment must be identical */
552 return (E1->V.Seg == E2->V.Seg);
555 /* Memory area must be identical */
556 return (E1->V.Mem == E2->V.Mem );
559 /* Not a leaf node */
560 return EqualExpr (E1->Left, E2->Left) && EqualExpr (E1->Right, E2->Right);