1 /*****************************************************************************/
5 /* Expression evaluation for the ld65 linker */
9 /* (C) 1998-2000 Ullrich von Bassewitz */
11 /* D-70597 Stuttgart */
12 /* EMail: uz@musoftware.de */
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.
107 if (EXPR_IS_LEAF (Root->Op)) {
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.
120 if (ExportHasMark (E)) {
121 Error ("Circular reference for symbol `%s', %s(%lu)",
122 E->Name, GetSourceFileName (E->Obj, E->Pos.Name),
127 Const = IsConstExport (E);
136 } else if (EXPR_IS_UNARY (Root->Op)) {
138 return IsConstExpr (Root->Left);
142 /* We must handle shortcut boolean expressions here */
146 if (IsConstExpr (Root->Left)) {
147 /* lhs is const, if it is zero, don't eval right */
148 if (GetExprVal (Root->Left) == 0) {
151 return IsConstExpr (Root->Right);
154 /* lhs not const --> tree not const */
160 if (IsConstExpr (Root->Left)) {
161 /* lhs is const, if it is not zero, don't eval right */
162 if (GetExprVal (Root->Left) != 0) {
165 return IsConstExpr (Root->Right);
168 /* lhs not const --> tree not const */
174 /* All others are handled normal */
175 return IsConstExpr (Root->Left) && IsConstExpr (Root->Right);
182 Import* GetExprImport (ExprNode* Expr)
183 /* Get the import data structure for a symbol expression node */
185 /* Check that this is really a symbol */
186 PRECONDITION (Expr->Op == EXPR_SYMBOL);
188 /* Return the import */
189 return Expr->Obj->Imports [Expr->V.ImpNum];
194 Export* GetExprExport (ExprNode* Expr)
195 /* Get the exported symbol for a symbol expression node */
197 /* Check that this is really a symbol */
198 PRECONDITION (Expr->Op == EXPR_SYMBOL);
200 /* Return the export */
201 return Expr->Obj->Imports [Expr->V.ImpNum]->V.Exp;
206 Section* GetExprSection (ExprNode* Expr)
207 /* Get the segment for a segment expression node */
209 /* Check that this is really a segment node */
210 PRECONDITION (Expr->Op == EXPR_SEGMENT);
212 /* If we have an object file, get the section from it, otherwise
213 * (internally generated expressions), get the section from the
217 /* Return the export */
218 return Expr->Obj->Sections [Expr->V.SegNum];
226 long GetExprVal (ExprNode* Expr)
227 /* Get the value of a constant expression */
229 long Right, Left, Val;
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.
245 if (ExportHasMark (E)) {
246 CircularRefError (E);
250 Val = GetExportVal (E);
256 S = GetExprSection (Expr);
257 return S->Offs + S->Seg->PC;
260 return Expr->V.MemArea->Start;
263 return GetExprVal (Expr->Left) + GetExprVal (Expr->Right);
266 return GetExprVal (Expr->Left) - GetExprVal (Expr->Right);
269 return GetExprVal (Expr->Left) * GetExprVal (Expr->Right);
272 Left = GetExprVal (Expr->Left);
273 Right = GetExprVal (Expr->Right);
275 Error ("Division by zero");
280 Left = GetExprVal (Expr->Left);
281 Right = GetExprVal (Expr->Right);
283 Error ("Modulo operation with zero");
288 return GetExprVal (Expr->Left) | GetExprVal (Expr->Right);
291 return GetExprVal (Expr->Left) ^ GetExprVal (Expr->Right);
294 return GetExprVal (Expr->Left) & GetExprVal (Expr->Right);
297 return GetExprVal (Expr->Left) << GetExprVal (Expr->Right);
300 return GetExprVal (Expr->Left) >> GetExprVal (Expr->Right);
303 return (GetExprVal (Expr->Left) == GetExprVal (Expr->Right));
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));
320 case EXPR_UNARY_MINUS:
321 return -GetExprVal (Expr->Left);
324 return ~GetExprVal (Expr->Left);
327 return GetExprVal (Expr->Left) & 0xFF;
330 return (GetExprVal (Expr->Left) >> 8) & 0xFF;
333 return (GetExprVal (Expr->Left) >> 16) & 0xFF;
336 return (GetExprVal (Expr->Left) >> 24) & 0xFF;
339 Left = GetExprVal (Expr->Left);
340 return ((Left >> 8) & 0x00FF) | ((Left << 8) & 0xFF00);
343 return GetExprVal (Expr->Left) && GetExprVal (Expr->Right);
346 return GetExprVal (Expr->Left) || GetExprVal (Expr->Right);
349 return (GetExprVal (Expr->Left) != 0) ^ (GetExprVal (Expr->Right) != 0);
352 return !GetExprVal (Expr->Left);
355 Internal ("Unknown expression Op type: %u", Expr->Op);
363 ExprNode* LiteralExpr (long Val, ObjData* O)
364 /* Return an expression tree that encodes the given literal value */
366 ExprNode* Expr = NewExprNode (O);
367 Expr->Op = EXPR_LITERAL;
374 ExprNode* MemExpr (Memory* Mem, long Offs, ObjData* O)
375 /* Return an expression tree that encodes an offset into the memory area */
379 ExprNode* Expr = NewExprNode (O);
380 Expr->Op = EXPR_MEMAREA;
381 Expr->V.MemArea = Mem;
383 Root = NewExprNode (O);
384 Root->Op = EXPR_PLUS;
386 Root->Right = LiteralExpr (Offs, O);
393 ExprNode* SegExpr (Section* Sec, long Offs, ObjData* O)
394 /* Return an expression tree that encodes an offset into a segment */
398 ExprNode* Expr = NewExprNode (O);
399 Expr->Op = EXPR_SEGMENT;
402 Root = NewExprNode (O);
403 Root->Op = EXPR_PLUS;
405 Root->Right = LiteralExpr (Offs, O);
412 ExprNode* ReadExpr (FILE* F, ObjData* O)
413 /* Read an expression from the given file */
417 /* Read the node tag and handle NULL nodes */
418 unsigned char Op = Read8 (F);
419 if (Op == EXPR_NULL) {
423 /* Create a new node */
424 Expr = NewExprNode (O);
427 /* Check the tag and handle the different expression types */
428 if (EXPR_IS_LEAF (Op)) {
432 Expr->V.Val = Read32Signed (F);
436 /* Read the import number */
437 Expr->V.ImpNum = Read16 (F);
441 /* Read the segment number */
442 Expr->V.SegNum = Read8 (F);
446 Error ("Invalid expression op: %02X", Op);
452 /* Not a leaf node */
453 Expr->Left = ReadExpr (F, O);
454 Expr->Right = ReadExpr (F, O);
458 /* Return the tree */
464 int EqualExpr (ExprNode* E1, ExprNode* E2)
465 /* Check if two expressions are identical. */
467 /* If one pointer is NULL, both must be NULL */
468 if ((E1 == 0) ^ (E2 == 0)) {
475 /* Both pointers not NULL, check OP */
476 if (E1->Op != E2->Op) {
480 /* OPs are identical, check data for leafs, or subtrees */
484 /* Value must be identical */
485 return (E1->V.Val == E2->V.Val);
488 /* Import number must be identical */
489 return (E1->V.ImpNum == E2->V.ImpNum);
492 /* Section must be identical */
493 return (GetExprSection (E1) == GetExprSection (E2));
496 /* Memory area must be identical */
497 return (E1->V.MemArea == E2->V.MemArea);
500 /* Not a leaf node */
501 return EqualExpr (E1->Left, E2->Left) && EqualExpr (E1->Right, E2->Right);