1/*****************************************************************************/
2/* */
3/* expr.c */
4/* */
5/* Expression evaluation for the ld65 linker */
6/* */
7/* */
8/* */
9/* (C) 1998-2012, Ullrich von Bassewitz */
10/* Roemerstrasse 52 */
11/* D-70794 Filderstadt */
12/* EMail: uz@cc65.org */
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 "check.h"
38#include "exprdefs.h"
39#include "xmalloc.h"
40
41/* ld65 */
42#include "global.h"
43#include "error.h"
44#include "fileio.h"
45#include "memarea.h"
46#include "segments.h"
47#include "expr.h"
48
49
50
51/*****************************************************************************/
52/* Code */
53/*****************************************************************************/
54
55
56
57ExprNode* NewExprNode (ObjData* O, unsigned char Op)
58/* Create a new expression node */
59{
60 /* Allocate fresh memory */
61 ExprNode* N = xmalloc (sizeof (ExprNode));
62 N->Op = Op;
63 N->Left = 0;
64 N->Right = 0;
65 N->Obj = O;
66 N->V.IVal = 0;
67
68 return N;
69}
70
71
72
73static void FreeExprNode (ExprNode* E)
74/* Free a node */
75{
76 /* Free the memory */
77 xfree (E);
78}
79
80
81
82void FreeExpr (ExprNode* Root)
83/* Free the expression, Root is pointing to. */
84{
85 if (Root) {
86 FreeExpr (Root->Left);
87 FreeExpr (Root->Right);
88 FreeExprNode (Root);
89 }
90}
91
92
93
94int IsConstExpr (ExprNode* Root)
95/* Return true if the given expression is a constant expression, that is, one
96** with no references to external symbols.
97*/
98{
99 int Const;
100 Export* E;
101 Section* S;
102 MemoryArea* M;
103
104 if (EXPR_IS_LEAF (Root->Op)) {
105 switch (Root->Op) {
106
107 case EXPR_LITERAL:
108 return 1;
109
110 case EXPR_SYMBOL:
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.
116 */
117 if (ExportHasMark (E)) {
118 CircularRefError (E);
119 Const = 0;
120 } else {
121 MarkExport (E);
122 Const = IsConstExport (E);
123 UnmarkExport (E);
124 }
125 return Const;
126
127 case EXPR_SECTION:
128 /* A section expression is const if the segment it is in is
129 ** not relocatable and already placed.
130 */
131 S = GetExprSection (Root);
132 M = S->Seg->MemArea;
133 return M != 0 && (M->Flags & MF_PLACED) != 0 && !M->Relocatable;
134
135 case EXPR_SEGMENT:
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;
139
140 case EXPR_MEMAREA:
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);
144
145 default:
146 /* Anything else is not const */
147 return 0;
148
149 }
150
151 } else if (EXPR_IS_UNARY (Root->Op)) {
152
153 SegExprDesc D;
154
155 /* Special handling for the BANK pseudo function */
156 switch (Root->Op) {
157
158 case EXPR_BANK:
159 /* Get segment references for the expression */
160 GetSegExprVal (Root->Left, &D);
161
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.
165 */
166 return (D.TooComplex == 0 &&
167 D.Seg != 0 &&
168 D.Seg->MemArea != 0 &&
169 D.Seg->MemArea->BankExpr != 0 &&
170 IsConstExpr (D.Seg->MemArea->BankExpr));
171
172 default:
173 /* All others handled normal */
174 return IsConstExpr (Root->Left);
175
176 }
177
178 } else {
179
180 /* We must handle shortcut boolean expressions here */
181 switch (Root->Op) {
182
183 case EXPR_BOOLAND:
184 if (IsConstExpr (Root->Left)) {
185 /* lhs is const, if it is zero, don't eval right */
186 if (GetExprVal (Root->Left) == 0) {
187 return 1;
188 } else {
189 return IsConstExpr (Root->Right);
190 }
191 } else {
192 /* lhs not const --> tree not const */
193 return 0;
194 }
195 break;
196
197 case EXPR_BOOLOR:
198 if (IsConstExpr (Root->Left)) {
199 /* lhs is const, if it is not zero, don't eval right */
200 if (GetExprVal (Root->Left) != 0) {
201 return 1;
202 } else {
203 return IsConstExpr (Root->Right);
204 }
205 } else {
206 /* lhs not const --> tree not const */
207 return 0;
208 }
209 break;
210
211 default:
212 /* All others are handled normal */
213 return IsConstExpr (Root->Left) && IsConstExpr (Root->Right);
214 }
215 }
216}
217
218
219
220Import* GetExprImport (ExprNode* Expr)
221/* Get the import data structure for a symbol expression node */
222{
223 /* Check that this is really a symbol */
224 PRECONDITION (Expr->Op == EXPR_SYMBOL);
225
226 /* If we have an object file, get the import from it, otherwise
227 ** (internally generated expressions), get the import from the
228 ** import pointer.
229 */
230 if (Expr->Obj) {
231 /* Return the Import */
232 return GetObjImport (Expr->Obj, Expr->V.ImpNum);
233 } else {
234 return Expr->V.Imp;
235 }
236}
237
238
239
240Export* GetExprExport (ExprNode* Expr)
241/* Get the exported symbol for a symbol expression node */
242{
243 /* Check that this is really a symbol */
244 PRECONDITION (Expr->Op == EXPR_SYMBOL);
245
246 /* Return the export for an import*/
247 return GetExprImport (Expr)->Exp;
248}
249
250
251
252Section* GetExprSection (ExprNode* Expr)
253/* Get the segment for a section expression node */
254{
255 /* Check that this is really a section node */
256 PRECONDITION (Expr->Op == EXPR_SECTION);
257
258 /* If we have an object file, get the section from it, otherwise
259 ** (internally generated expressions), get the section from the
260 ** section pointer.
261 */
262 if (Expr->Obj) {
263 /* Return the export */
264 return CollAt (&Expr->Obj->Sections, Expr->V.SecNum);
265 } else {
266 return Expr->V.Sec;
267 }
268}
269
270
271
272long GetExprVal (ExprNode* Expr)
273/* Get the value of a constant expression */
274{
275 long Right;
276 long Left;
277 long Val;
278 Section* S;
279 Export* E;
280 SegExprDesc D;
281
282 switch (Expr->Op) {
283
284 case EXPR_LITERAL:
285 return Expr->V.IVal;
286
287 case EXPR_SYMBOL:
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.
293 */
294 if (ExportHasMark (E)) {
295 CircularRefError (E);
296 Val = 0;
297 } else {
298 MarkExport (E);
299 Val = GetExportVal (E);
300 UnmarkExport (E);
301 }
302 return Val;
303
304 case EXPR_SECTION:
305 S = GetExprSection (Expr);
306 return S->Offs + S->Seg->PC;
307
308 case EXPR_SEGMENT:
309 return Expr->V.Seg->PC;
310
311 case EXPR_MEMAREA:
312 return Expr->V.Mem->Start;
313
314 case EXPR_PLUS:
315 return GetExprVal (Expr->Left) + GetExprVal (Expr->Right);
316
317 case EXPR_MINUS:
318 return GetExprVal (Expr->Left) - GetExprVal (Expr->Right);
319
320 case EXPR_MUL:
321 return GetExprVal (Expr->Left) * GetExprVal (Expr->Right);
322
323 case EXPR_DIV:
324 Left = GetExprVal (Expr->Left);
325 Right = GetExprVal (Expr->Right);
326 if (Right == 0) {
327 Error ("Division by zero");
328 }
329 return Left / Right;
330
331 case EXPR_MOD:
332 Left = GetExprVal (Expr->Left);
333 Right = GetExprVal (Expr->Right);
334 if (Right == 0) {
335 Error ("Modulo operation with zero");
336 }
337 return Left % Right;
338
339 case EXPR_OR:
340 return GetExprVal (Expr->Left) | GetExprVal (Expr->Right);
341
342 case EXPR_XOR:
343 return GetExprVal (Expr->Left) ^ GetExprVal (Expr->Right);
344
345 case EXPR_AND:
346 return GetExprVal (Expr->Left) & GetExprVal (Expr->Right);
347
348 case EXPR_SHL:
349 return GetExprVal (Expr->Left) << GetExprVal (Expr->Right);
350
351 case EXPR_SHR:
352 return GetExprVal (Expr->Left) >> GetExprVal (Expr->Right);
353
354 case EXPR_EQ:
355 return (GetExprVal (Expr->Left) == GetExprVal (Expr->Right));
356
357 case EXPR_NE:
358 return (GetExprVal (Expr->Left) != GetExprVal (Expr->Right));
359
360 case EXPR_LT:
361 return (GetExprVal (Expr->Left) < GetExprVal (Expr->Right));
362
363 case EXPR_GT:
364 return (GetExprVal (Expr->Left) > GetExprVal (Expr->Right));
365
366 case EXPR_LE:
367 return (GetExprVal (Expr->Left) <= GetExprVal (Expr->Right));
368
369 case EXPR_GE:
370 return (GetExprVal (Expr->Left) >= GetExprVal (Expr->Right));
371
372 case EXPR_BOOLAND:
373 return GetExprVal (Expr->Left) && GetExprVal (Expr->Right);
374
375 case EXPR_BOOLOR:
376 return GetExprVal (Expr->Left) || GetExprVal (Expr->Right);
377
378 case EXPR_BOOLXOR:
379 return (GetExprVal (Expr->Left) != 0) ^ (GetExprVal (Expr->Right) != 0);
380
381 case EXPR_MAX:
382 Left = GetExprVal (Expr->Left);
383 Right = GetExprVal (Expr->Right);
384 return (Left > Right)? Left : Right;
385
386 case EXPR_MIN:
387 Left = GetExprVal (Expr->Left);
388 Right = GetExprVal (Expr->Right);
389 return (Left < Right)? Left : Right;
390
391 case EXPR_UNARY_MINUS:
392 return -GetExprVal (Expr->Left);
393
394 case EXPR_NOT:
395 return ~GetExprVal (Expr->Left);
396
397 case EXPR_SWAP:
398 Left = GetExprVal (Expr->Left);
399 return ((Left >> 8) & 0x00FF) | ((Left << 8) & 0xFF00);
400
401 case EXPR_BOOLNOT:
402 return !GetExprVal (Expr->Left);
403
404 case EXPR_BANK:
405 GetSegExprVal (Expr->Left, &D);
406 if (D.TooComplex || D.Seg == 0) {
407 Error ("Argument for .BANK is not segment relative or too complex");
408 }
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));
413 }
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));
418 }
419 return GetExprVal (D.Seg->MemArea->BankExpr);
420
421 case EXPR_BYTE0:
422 return GetExprVal (Expr->Left) & 0xFF;
423
424 case EXPR_BYTE1:
425 return (GetExprVal (Expr->Left) >> 8) & 0xFF;
426
427 case EXPR_BYTE2:
428 return (GetExprVal (Expr->Left) >> 16) & 0xFF;
429
430 case EXPR_BYTE3:
431 return (GetExprVal (Expr->Left) >> 24) & 0xFF;
432
433 case EXPR_WORD0:
434 return GetExprVal (Expr->Left) & 0xFFFF;
435
436 case EXPR_WORD1:
437 return (GetExprVal (Expr->Left) >> 16) & 0xFFFF;
438
439 case EXPR_FARADDR:
440 return GetExprVal (Expr->Left) & 0xFFFFFF;
441
442 case EXPR_DWORD:
443 return GetExprVal (Expr->Left) & 0xFFFFFFFF;
444
445 case EXPR_NEARADDR:
446 /* Assembler was expected to validate this truncation. */
447 return GetExprVal (Expr->Left) & 0xFFFF;
448
449 default:
450 Internal ("Unknown expression Op type: %u", Expr->Op);
451 /* NOTREACHED */
452 return 0;
453 }
454}
455
456
457
458static void GetSegExprValInternal (ExprNode* Expr, SegExprDesc* D, int Sign)
459/* Check if the given expression consists of a segment reference and only
460** constant values, additions and subtractions. If anything else is found,
461** set D->TooComplex to true.
462** Internal, recursive routine.
463*/
464{
465 Export* E;
466
467 switch (Expr->Op) {
468
469 case EXPR_LITERAL:
470 D->Val += (Sign * Expr->V.IVal);
471 break;
472
473 case EXPR_SYMBOL:
474 /* Get the referenced export */
475 E = GetExprExport (Expr);
476 /* If this export has a mark set, we've already encountered it.
477 ** This means that the export is used to define it's own value,
478 ** which in turn means, that we have a circular reference.
479 */
480 if (ExportHasMark (E)) {
481 CircularRefError (E);
482 } else {
483 MarkExport (E);
484 GetSegExprValInternal (E->Expr, D, Sign);
485 UnmarkExport (E);
486 }
487 break;
488
489 case EXPR_SECTION:
490 if (D->Seg) {
491 /* We cannot handle more than one segment reference in o65 */
492 D->TooComplex = 1;
493 } else {
494 /* Get the section from the expression */
495 Section* S = GetExprSection (Expr);
496 /* Remember the segment reference */
497 D->Seg = S->Seg;
498 /* Add the offset of the section to the constant value */
499 D->Val += Sign * (S->Offs + D->Seg->PC);
500 }
501 break;
502
503 case EXPR_SEGMENT:
504 if (D->Seg) {
505 /* We cannot handle more than one segment reference in o65 */
506 D->TooComplex = 1;
507 } else {
508 /* Remember the segment reference */
509 D->Seg = Expr->V.Seg;
510 /* Add the offset of the segment to the constant value */
511 D->Val += (Sign * D->Seg->PC);
512 }
513 break;
514
515 case EXPR_PLUS:
516 GetSegExprValInternal (Expr->Left, D, Sign);
517 GetSegExprValInternal (Expr->Right, D, Sign);
518 break;
519
520 case EXPR_MINUS:
521 GetSegExprValInternal (Expr->Left, D, Sign);
522 GetSegExprValInternal (Expr->Right, D, -Sign);
523 break;
524
525 default:
526 /* Expression contains illegal operators */
527 D->TooComplex = 1;
528 break;
529
530 }
531}
532
533
534
535void GetSegExprVal (ExprNode* Expr, SegExprDesc* D)
536/* Check if the given expression consists of a segment reference and only
537** constant values, additions and subtractions. If anything else is found,
538** set D->TooComplex to true. The function will initialize D.
539*/
540{
541 /* Initialize the given structure */
542 D->Val = 0;
543 D->TooComplex = 0;
544 D->Seg = 0;
545
546 /* Call our recursive calculation routine */
547 GetSegExprValInternal (Expr, D, 1);
548}
549
550
551
552ExprNode* LiteralExpr (long Val, ObjData* O)
553/* Return an expression tree that encodes the given literal value */
554{
555 ExprNode* Expr = NewExprNode (O, EXPR_LITERAL);
556 Expr->V.IVal = Val;
557 return Expr;
558}
559
560
561
562ExprNode* MemoryExpr (MemoryArea* Mem, long Offs, ObjData* O)
563/* Return an expression tree that encodes an offset into a memory area */
564{
565 ExprNode* Root;
566
567 ExprNode* Expr = NewExprNode (O, EXPR_MEMAREA);
568 Expr->V.Mem = Mem;
569
570 if (Offs != 0) {
571 Root = NewExprNode (O, EXPR_PLUS);
572 Root->Left = Expr;
573 Root->Right = LiteralExpr (Offs, O);
574 } else {
575 Root = Expr;
576 }
577
578 return Root;
579}
580
581
582
583ExprNode* SegmentExpr (Segment* Seg, long Offs, ObjData* O)
584/* Return an expression tree that encodes an offset into a segment */
585{
586 ExprNode* Root;
587
588 ExprNode* Expr = NewExprNode (O, EXPR_SEGMENT);
589 Expr->V.Seg = Seg;
590
591 if (Offs != 0) {
592 Root = NewExprNode (O, EXPR_PLUS);
593 Root->Left = Expr;
594 Root->Right = LiteralExpr (Offs, O);
595 } else {
596 Root = Expr;
597 }
598
599 return Root;
600}
601
602
603
604ExprNode* SectionExpr (Section* Sec, long Offs, ObjData* O)
605/* Return an expression tree that encodes an offset into a section */
606{
607 ExprNode* Root;
608
609 ExprNode* Expr = NewExprNode (O, EXPR_SECTION);
610 Expr->V.Sec = Sec;
611
612 if (Offs != 0) {
613 Root = NewExprNode (O, EXPR_PLUS);
614 Root->Left = Expr;
615 Root->Right = LiteralExpr (Offs, O);
616 } else {
617 Root = Expr;
618 }
619
620 return Root;
621}
622
623
624
625ExprNode* ReadExpr (FILE* F, ObjData* O)
626/* Read an expression from the given file */
627{
628 ExprNode* Expr;
629
630 /* Read the node tag and handle NULL nodes */
631 unsigned char Op = Read8 (F);
632 if (Op == EXPR_NULL) {
633 return 0;
634 }
635
636 /* Create a new node */
637 Expr = NewExprNode (O, Op);
638
639 /* Check the tag and handle the different expression types */
640 if (EXPR_IS_LEAF (Op)) {
641 switch (Op) {
642
643 case EXPR_LITERAL:
644 Expr->V.IVal = Read32Signed (F);
645 break;
646
647 case EXPR_SYMBOL:
648 /* Read the import number */
649 Expr->V.ImpNum = ReadVar (F);
650 break;
651
652 case EXPR_SECTION:
653 /* Read the section number */
654 Expr->V.SecNum = ReadVar (F);
655 break;
656
657 default:
658 Error ("Invalid expression op: %02X", Op);
659
660 }
661
662 } else {
663
664 /* Not a leaf node */
665 Expr->Left = ReadExpr (F, O);
666 Expr->Right = ReadExpr (F, O);
667
668 }
669
670 /* Return the tree */
671 return Expr;
672}
673
674
675
676int EqualExpr (ExprNode* E1, ExprNode* E2)
677/* Check if two expressions are identical. */
678{
679 /* If one pointer is NULL, both must be NULL */
680 if ((E1 == 0) ^ (E2 == 0)) {
681 return 0;
682 }
683 if (E1 == 0) {
684 return 1;
685 }
686
687 /* Both pointers not NULL, check OP */
688 if (E1->Op != E2->Op) {
689 return 0;
690 }
691
692 /* OPs are identical, check data for leafs, or subtrees */
693 switch (E1->Op) {
694
695 case EXPR_LITERAL:
696 /* Value must be identical */
697 return (E1->V.IVal == E2->V.IVal);
698
699 case EXPR_SYMBOL:
700 /* Import must be identical */
701 return (GetExprImport (E1) == GetExprImport (E2));
702
703 case EXPR_SECTION:
704 /* Section must be identical */
705 return (GetExprSection (E1) == GetExprSection (E2));
706
707 case EXPR_SEGMENT:
708 /* Segment must be identical */
709 return (E1->V.Seg == E2->V.Seg);
710
711 case EXPR_MEMAREA:
712 /* Memory area must be identical */
713 return (E1->V.Mem == E2->V.Mem);
714
715 default:
716 /* Not a leaf node */
717 return EqualExpr (E1->Left, E2->Left) && EqualExpr (E1->Right, E2->Right);
718 }
719
720}
721