source: liacs/coco/assignment3/ICGenerator.cc@ 393

Last change on this file since 393 was 2, checked in by Rick van der Zwet, 15 years ago

Initial import of data of old repository ('data') worth keeping (e.g. tracking
means of URL access statistics)
File size: 35.1 KB
RevLine 
[2]1/*
2 * ICGenerator.cc - Implementation of the ICGenerator class
3 *
4 * Part of the assignment of the Compiler Construction course
5 * LIACS, Leiden University
6 *
7 * This file will contain most of your work for assignment 3.
8 */
9
10#include "ICGenerator.h"
11
12#include <sstream>
13#include <cassert>
14#include <list>
15#include <iostream>
16
17extern bool bOptimize1;
18extern IntermediateCode *icode;
19extern SymbolTable *symtab;
20
21/* Macro to allow pretty display of parser tree calling stack debug print calls */
22#define picg(x) pmesg(100, "Parser: '"); pmesg(100, x); pmesg(100, "'\n")
23
24// Constructor
25ICGenerator::ICGenerator() {
26}
27
28
29// Destructor
30ICGenerator::~ICGenerator() {
31}
32
33
34// Preprocesses the syntax tree; this method is called before
35// GenerateIntermediateCode() if optimizations are enabled
36void ICGenerator::Preprocess (SyntaxTree * tree, SymbolTable * symtab) {
37}
38
39
40// Takes a SyntaxTree and converts it into an IntermediateCode structure
41IntermediateCode * ICGenerator::GenerateIntermediateCode (SyntaxTree * inputTree, SymbolTable * symtab) {
42 IStatement * istmt;
43
44 icode = new IntermediateCode;
45
46 /* Process program body */
47 /* Make sure temponary generated variables are added to the right scope */
48 symtab->SetCurrentScope(inputTree->GetProgramName());
49 icode->SetProgramName(inputTree->GetProgramName());
50 delete Treewalk(inputTree->GetProgramBody());
51
52 /* Indicate end of program body */
53 istmt = new IStatement (IOP_RETURN);
54 icode->AppendStatement(istmt);
55
56 /* Now walk through the list of subprograms, and process them one by one */
57 for (int i = 0; i < inputTree->GetSubprogramCount(); i++) {
58 // add subprogram code
59 Symbol *subprogram = symtab->GetSymbol(inputTree->GetSubprogramName(i));
60 /* Make sure temponary generated variables are added to the right scope */
61 symtab->SetCurrentScope(inputTree->GetSubprogramName(i));
62 icode->AppendStatement(new IStatement(IOP_SUBPROG, new IOperand_Symbol(subprogram), NULL, NULL));
63
64 // add subprogram body code
65 delete Treewalk(inputTree->GetSubprogram(i));
66
67 // add code for return value
68 IOperator op;
69 switch (subprogram->GetReturnType()) {
70 case RT_INT:
71 op = IOP_RETURN_I;
72 break;
73 case RT_REAL:
74 op = IOP_RETURN_R;
75 break;
76 case RT_VOID:
77 op = IOP_RETURN;
78 break;
79 default:
80 assert(0); // can't happen
81 }
82 icode->AppendStatement(new IStatement(op, (op == IOP_RETURN) ? NULL : new IOperand_Symbol(subprogram), NULL, NULL));
83 }
84
85 return icode;
86}
87
88
89// Postprocesses the intermediate code; this method is called after
90// GenerateIntermediateCode() if optimizations are enabled
91void ICGenerator::Postprocess (IntermediateCode * code, SymbolTable * symtab) {
92 /* Some trivial optimalisations which could be implemented */
93
94 /* 1) LABEL X
95 * 2) GOTO :Y
96 * Alter GOTO :X to GOTO :Y directly
97 */
98
99 /* 1) LABEL X
100 * 2) RETURN tX
101 * Alter GOTO :X to RETURN tX directly
102 */
103
104 /* 1) ASSIGN foo tX
105 * ... no use of tX, in the meantime ...
106 * X) ASSIGN bar tX
107 * Delete line 1)
108 */
109
110 /* Less trivials optimalisations which could be implemented*/
111
112 /* Unfold small for loops */
113
114 /* Delete/mangle branching code if TEST expression to always to be evaluated TRUE of FALSE */
115
116 /* Detect and remove useless IOP_ASSIGN_[IR] statements */
117
118 /* When parameters of function are not used, do not assign */
119
120 /* 1) ASSIGN int(1) tX
121 * 2) ASSIGN int(2) tY
122 * 3) ADD_I tX tY tZ
123 * Convert line 3) to ASSIGN int(3) tZ
124 */
125
126 /* 1) LABEL L_1
127 * 2) LABEL L_2
128 * Convert all GOTO L_2 to GOTO L_1 and delete L_2
129 */
130}
131
132
133// Generate a temporary symbol
134Symbol * ICGenerator::GenerateTempVar(ReturnType type) {
135 /* Keep track of variables given out, make all generated unique for the sake
136 * of debugging
137 */
138 static int count = 0;
139 count++;
140
141 Symbol *symbol = new Symbol();
142 symbol->SetSymbolType(ST_TEMPVAR);
143 symbol->SetReturnType(type);
144 std::stringstream ss;
145 ss << "t" << count;
146 symbol->SetName(ss.str());
147
148 /* Make sure to add it to the symbol table */
149 symtab->AddSymbol(symbol);
150 return symbol;
151}
152
153
154// Generates a Symbol for a label
155Symbol * ICGenerator::GenerateLabel() {
156 /* Keep track of variables given out, make all generated unique for the sake
157 * of debugging
158 */
159 static int count = 0;
160 count++;
161
162 Symbol *symbol = new Symbol();
163 symbol->SetSymbolType(ST_LABEL);
164 std::stringstream ss;
165 ss << "L_" << count;
166 symbol->SetName(ss.str());
167
168 /* Make sure to add it to the symbol table */
169 symtab->AddSymbol(symbol);
170 return symbol;
171}
172
173IOperand *ICGenerator::Treewalk (Node * node, IOperand *dest, IOperand *constant)
174{
175 switch (node->GetNodeType ())
176 {
177 case NODE_UNKNOWN: // Unknown (yet)
178 assert (0); // can't happen
179 break;
180 case NODE_ERROR: // Error
181 assert (0); // can't happen
182 break;
183
184 /*
185 * Statement list
186 * left child One of, NODE_ASSIGNMENT, NODE_IF, NODE_WHILE,
187 * NODE_PROCCALL, NODE_FUNCTIONCALL, NODE_STATEMENT_LIST.
188 * right child One of, NODE_ASSIGNMENT, NODE_IF, NODE_WHILE,
189 * NODE_PROCCALL, NODE_FUNCTIONCALL, NODE_STATEMENT_LIST, or
190 * NODE_EMPTY if no more statements follow.
191 */
192 case NODE_STATEMENT_LIST:
193 {
194 delete Treewalk(node->GetLeftChild());
195 delete Treewalk(node->GetRightChild());
196 return NULL;
197 }
198 break;
199
200 /*
201 * Assignment
202 * left child A NODE_ID that identifies the destination variable
203 * right child A subtree representing an expression
204 */
205 case NODE_ASSIGNMENT:
206 {
207 IOperand *result = Treewalk(node->GetLeftChild());
208 IOperand *operand = Treewalk(node->GetRightChild(), bOptimize1 ? result : NULL);
209 if (operand != result) {
210 IOperator op = ( (node->GetLeftChild()->GetReturnType() == RT_REAL) ? IOP_ASSIGN_R : IOP_ASSIGN_I );
211 icode->AppendStatement(new IStatement(op, operand, NULL, result));
212 }
213 return NULL;
214 }
215 break;
216
217 /*
218 * If statement
219 * left child A NODE_BOOLEXPR that provides the if condition
220 * right child A NODE_IF_TARGETS subtree (if there is an else clause) or
221 * a subtree consisting of statements (if there's no else)
222 */
223 case NODE_IF:
224 {
225 // generate labels
226 Symbol *false_label = GenerateLabel();
227 Symbol *end_label = GenerateLabel();
228
229 // add evaluation code
230 IOperand *evaluation = Treewalk(node->GetLeftChild());
231 icode->AppendStatement(new IStatement(IOP_BEQ_I, evaluation, new IOperand_Int(0), new IOperand_Symbol(false_label)));
232
233 // add code for true case
234 Node *rightchild = node->GetRightChild();
235 if (rightchild->GetNodeType() == NODE_IF_TARGETS) {
236 delete Treewalk(rightchild->GetLeftChild());
237 // there is a else part so skip over it
238 icode->AppendStatement(new IStatement(IOP_GOTO, new IOperand_Symbol(end_label), NULL, NULL));
239 } else {
240 delete Treewalk(rightchild);
241 }
242
243 // add label for false part
244 icode->AppendStatement(new IStatement(IOP_LABEL, new IOperand_Symbol(false_label), NULL, NULL));
245
246 // add code for false/else case if any
247 if (rightchild->GetNodeType() == NODE_IF_TARGETS) {
248 delete Treewalk(rightchild->GetRightChild ());
249 // add end label
250 icode->AppendStatement(new IStatement(IOP_LABEL, new IOperand_Symbol(end_label), NULL, NULL));
251 }
252
253 return NULL;
254 }
255 break;
256
257 /*
258 * Targets of an if-else-statement
259 * left child The statements that have to be executed when the condition
260 * of the parent if-statement is true.
261 * right child The statements that have to be executed when the condition
262 * of the parent if-statement is false: that is: the else
263 * part.
264 */
265 case NODE_IF_TARGETS:
266 assert(0); // handled in NODE_IF
267 break;
268
269 /*
270 * While loop
271 * left child A NODE_BOOLEXPR that provides the loop condition
272 * right child A subtree consisting of statements
273 */
274 case NODE_WHILE:
275 {
276 /* Method while tree
277 * :START
278 * if <expr> = 0 GOTO END
279 * <body>
280 * GOTO START
281 * :END
282 */
283 // generate labels
284 Symbol *start_label = GenerateLabel();
285 Symbol *end_label = GenerateLabel();
286
287 // add start label
288 icode->AppendStatement(new IStatement(IOP_LABEL, new IOperand_Symbol(start_label), NULL, NULL));
289
290 // add evaluation code
291 IOperand *evaluation = Treewalk(node->GetLeftChild());
292 icode->AppendStatement(new IStatement(IOP_BEQ_I, evaluation, new IOperand_Int(0), new IOperand_Symbol(end_label)));
293
294 // add code
295 delete Treewalk(node->GetLeftChild());
296
297 // add jump back to start
298 icode->AppendStatement(new IStatement(IOP_GOTO, new IOperand_Symbol(start_label), NULL, NULL));
299
300 // add end label
301 icode->AppendStatement(new IStatement(IOP_LABEL, new IOperand_Symbol(end_label), NULL, NULL));
302
303 return NULL;
304 }
305 break;
306
307 /*
308 * Subprogram calls
309 * left child A NODE_ID that identifies the called function/procedure
310 * right child A NODE_EXPRLIST that specifies the actual arguments: or
311 * NODE_EMPTY if no arguments required.
312 */
313 case NODE_PROCCALL:
314 {
315 // pass parameters
316 delete Treewalk(node->GetRightChild());
317
318 // add call statement
319 IOperand *id = Treewalk(node->GetLeftChild());
320 icode->AppendStatement(new IStatement(IOP_PROCCALL, id, NULL, NULL));
321
322 return NULL;
323 }
324 break;
325 case NODE_FUNCTIONCALL:
326 {
327 // pass parameters
328 delete Treewalk(node->GetRightChild());
329
330 // add call statement
331 IOperand *id = Treewalk(node->GetLeftChild());
332 IOperand *result = (dest != NULL) ? dest : new IOperand_Symbol(GenerateTempVar(node->GetReturnType()));
333 icode->AppendStatement(new IStatement(IOP_FUNCCALL, id, NULL, result));
334
335 return (dest != NULL) ? dest : result->Clone();
336 }
337 break;
338
339 /*
340 * Expression list
341 * left child A subtree representing an expression
342 * right child A subtree representing an expression: another
343 * NODE_EXPRLIST: or NODE_EMPTY if no more expressions follow
344 * in the expression list.
345 */
346 case NODE_EXPRLIST:
347 {
348 // pass parameter
349 IOperand *parameter = Treewalk(node->GetLeftChild());
350 ReturnType type = node->GetLeftChild()->GetReturnType();
351 IOperator op = ( (type == RT_REAL) ? IOP_PARAM_R : IOP_PARAM_I );
352 icode->AppendStatement(new IStatement(op, parameter, NULL, NULL));
353
354 // pass any other parameters
355 delete Treewalk(node->GetRightChild());
356
357 return NULL;
358 }
359 break;
360
361 /*
362 * Boolean-like expression
363 * child A subtree with any NODE_REL_ node as parent
364 */
365 case NODE_BOOLEXPR:
366 {
367 return Treewalk(node->GetChild());
368 }
369 break;
370
371 /*
372 * Relational operators
373 * left child Left-hand side of the comparison
374 * right child Right-hand side of the comparison
375 */
376 case NODE_REL_EQUAL: // = operator
377 {
378 ReturnType type = node->GetLeftChild()->GetReturnType();
379 IOperator op = ((type == RT_INT) ? IOP_BEQ_I : IOP_BEQ_R);
380 return GenerateRelopCode(op, node);
381 }
382 break;
383 case NODE_REL_LT: // < operator
384 {
385 ReturnType type = node->GetLeftChild()->GetReturnType();
386 IOperator op = ((type == RT_INT) ? IOP_BLT_I : IOP_BLT_R);
387 return GenerateRelopCode(op, node);
388 }
389 break;
390 case NODE_REL_GT: // > operator
391 {
392 ReturnType type = node->GetLeftChild()->GetReturnType();
393 IOperator op = ((type == RT_INT) ? IOP_BGT_I : IOP_BGT_R);
394 return GenerateRelopCode(op, node);
395 }
396 break;
397 case NODE_REL_LTE: // <= operator
398 {
399 ReturnType type = node->GetLeftChild()->GetReturnType();
400 IOperator op = ((type == RT_INT) ? IOP_BLE_I : IOP_BLE_R);
401 return GenerateRelopCode(op, node);
402 }
403 break;
404 case NODE_REL_GTE: // >= operator
405 {
406 ReturnType type = node->GetLeftChild()->GetReturnType();
407 IOperator op = ((type == RT_INT) ? IOP_BGE_I : IOP_BGE_R);
408 return GenerateRelopCode(op, node);
409 }
410 break;
411 case NODE_REL_NOTEQUAL: // <> operator
412 {
413 ReturnType type = node->GetLeftChild()->GetReturnType();
414 IOperator op = ((type == RT_INT) ? IOP_BNE_I : IOP_BNE_R);
415 return GenerateRelopCode(op, node);
416 }
417 break;
418
419 /*
420 * Binary arithmetic & logic operations
421 * left child Left-hand side of the operation
422 * right child Right-hand side of the operation
423 */
424 case NODE_ADD: // Add
425 {
426 IOperand *lhs = NULL;
427 IOperand *rhs = NULL;
428
429 // attempt optimizations
430 if (bOptimize1) {
431 /* reverse evaluation of operands, due to the fact the tree is always
432 * set to be on the left and we like to fold constants where ever
433 * possible
434 */
435 rhs = Treewalk(node->GetRightChild());
436 // check if we need to push any constant down the tree
437 if (node->GetLeftChild()->GetNodeType() == NODE_ADD ||
438 node->GetLeftChild()->GetNodeType() == NODE_SUB ) {
439 if (IsConstant(rhs)) {
440 // right hand side is also constant
441 if (constant != NULL) {
442 if (IsInt(rhs)) {
443 rhs->SetIntValue(rhs->GetIntValue() + constant->GetIntValue());
444 } else {
445 rhs->SetRealValue(rhs->GetRealValue() + constant->GetRealValue());
446 }
447 }
448 // evaluate left hand side passing constant value
449 lhs = Treewalk(node->GetLeftChild(), dest, rhs);
450 return lhs;
451 } else {
452 // generate add instruction for the right hand side
453 IOperator op = ( (node->GetReturnType() == RT_INT) ? IOP_ADD_I : IOP_ADD_R );
454 lhs = Treewalk(node->GetLeftChild(), NULL, constant);
455 IOperand *result = (dest != NULL) ? dest : new IOperand_Symbol(GenerateTempVar(node->GetReturnType()));
456 icode->AppendStatement(new IStatement(op, lhs, rhs, result));
457 return (dest != NULL) ? dest : result->Clone();
458 }
459 } else {
460 // can't push down constant
461 lhs = Treewalk(node->GetLeftChild());
462 }
463
464 // try to add the constant, if any, to any constant lhs or rhs
465 if (constant != NULL) {
466 if (IsConstant(lhs)) {
467 if (IsInt(lhs)) {
468 lhs->SetIntValue(lhs->GetIntValue() + constant->GetIntValue());
469 } else {
470 lhs->SetRealValue(lhs->GetRealValue() + constant->GetRealValue());
471 }
472 delete constant;
473 constant = NULL;
474 } else if (IsConstant(rhs)) {
475 if (IsInt(rhs)) {
476 rhs->SetIntValue(rhs->GetIntValue() + constant->GetIntValue());
477 } else {
478 rhs->SetRealValue(rhs->GetRealValue() + constant->GetRealValue());
479 }
480 delete constant;
481 constant = NULL;
482 }
483 }
484
485 // algebraic identity
486 if (IsZero(lhs)) {
487 delete lhs;
488 return rhs;
489 }
490 if (IsZero(rhs)) {
491 delete rhs;
492 return lhs;
493 }
494
495 // constant folding
496 if (IsConstant(lhs) && IsConstant(rhs)) {
497 IOperand *result = NULL;
498 if (IsInt(lhs)) {
499 result = new IOperand_Int(lhs->GetIntValue() + rhs->GetIntValue() + ((constant==NULL) ? 0 : constant->GetIntValue()));
500 } else {
501 result = new IOperand_Real(lhs->GetRealValue() + rhs->GetRealValue() + ((constant==NULL) ? 0 : constant->GetRealValue()));
502 }
503 delete lhs;
504 delete rhs;
505 return result;
506 }
507 } else {
508
509 // calculate operands for unoptimized case
510 lhs = Treewalk(node->GetLeftChild());
511 rhs = Treewalk(node->GetRightChild());
512 }
513
514 // generate add code
515 IOperand *result = (dest != NULL) ? dest : new IOperand_Symbol(GenerateTempVar(node->GetReturnType()));
516 IOperator op = ( (node->GetReturnType() == RT_INT) ? IOP_ADD_I : IOP_ADD_R );
517 if (constant == NULL) {
518 icode->AppendStatement(new IStatement(op, lhs, rhs, result));
519 } else {
520 IOperand *temp = new IOperand_Symbol(GenerateTempVar(node->GetReturnType()));
521 icode->AppendStatement(new IStatement(op, lhs, rhs, temp));
522 icode->AppendStatement(new IStatement(op, temp->Clone(), constant, result));
523 }
524 return (dest != NULL) ? dest : result->Clone();
525 }
526 break;
527 case NODE_SUB: // Substract
528 {
529 // calculate operands
530 IOperand *lhs = NULL;
531 IOperand *rhs = NULL;
532
533 // attempt optimizations
534 if (bOptimize1) {
535 /* reverse evaluation of operands, due to the fact the tree is always
536 * set to be on the left and we like to fold constants where ever
537 * possible
538 */
539 rhs = Treewalk(node->GetRightChild());
540 // check if we need to push any constant down the tree
541 if (node->GetLeftChild()->GetNodeType() == NODE_ADD ||
542 node->GetLeftChild()->GetNodeType() == NODE_SUB ) {
543 if (IsConstant(rhs)) {
544 // right hand side is also constant
545 if (constant != NULL) {
546 if (IsInt(rhs)) {
547 rhs->SetIntValue((rhs->GetIntValue() * -1) + constant->GetIntValue());
548 } else {
549 rhs->SetRealValue((rhs->GetRealValue() * -1) + constant->GetRealValue());
550 }
551 } else {
552 /* Negate fresh new minus knob, if it is gonna be the first constant */
553 if (IsInt(rhs)) {
554 rhs->SetIntValue(rhs->GetIntValue() * -1);
555 } else {
556 rhs->SetRealValue(rhs->GetRealValue() * -1);
557 }
558 }
559
560 // evaluate left hand side passing constant value
561 lhs = Treewalk(node->GetLeftChild(), dest, rhs);
562 return lhs;
563 } else {
564 // generate add instruction for the right hand side
565 IOperator op = ( (node->GetReturnType() == RT_INT) ? IOP_SUB_I : IOP_SUB_R );
566 lhs = Treewalk(node->GetLeftChild(), NULL, constant);
567 IOperand *result = (dest != NULL) ? dest : new IOperand_Symbol(GenerateTempVar(node->GetReturnType()));
568 icode->AppendStatement(new IStatement(op, lhs, rhs, result));
569 return (dest != NULL) ? dest : result->Clone();
570 }
571 } else {
572 // can't push down constant
573 lhs = Treewalk(node->GetLeftChild());
574 }
575
576 // try to sub the constant, if any, to any constant lhs or rhs
577 if (constant != NULL) {
578 if (IsConstant(lhs)) {
579 if (IsInt(lhs)) {
580 lhs->SetIntValue(lhs->GetIntValue() + constant->GetIntValue());
581 } else {
582 lhs->SetRealValue(lhs->GetRealValue() + constant->GetRealValue());
583 }
584 delete constant;
585 constant = NULL;
586 } else if (IsConstant(rhs)) {
587 /* Negate right side as it is going to be negative constant value */
588 if (IsInt(rhs)) {
589 rhs->SetIntValue((rhs->GetIntValue() * -1) + constant->GetIntValue());
590 } else {
591 rhs->SetRealValue((rhs->GetRealValue() * -1) + constant->GetRealValue());
592 }
593 delete constant;
594 constant = NULL;
595 }
596 }
597
598 // algebraic identity right side
599 if (IsZero(rhs)) {
600 delete rhs;
601 return lhs;
602 }
603
604 // constant folding
605 if (IsConstant(lhs) && IsConstant(rhs)) {
606 IOperand *result = NULL;
607 if (IsInt(lhs)) {
608 result = new IOperand_Int(lhs->GetIntValue() - rhs->GetIntValue());
609 } else {
610 result = new IOperand_Real(lhs->GetRealValue() - rhs->GetRealValue());
611 }
612 delete lhs;
613 delete rhs;
614 return result;
615 }
616
617 // algebraic identity left side
618 if (IsZero(lhs)) {
619 delete lhs;
620
621 // generate unary minus code
622 IOperand *result = (dest != NULL) ? dest : new IOperand_Symbol(GenerateTempVar(node->GetReturnType()));
623 IOperator op = ( (node->GetReturnType() == RT_INT) ? IOP_UNARY_MINUS_I : IOP_UNARY_MINUS_R );
624 icode->AppendStatement(new IStatement(op, rhs, NULL, result));
625 return (dest != NULL) ? dest : result->Clone();
626 }
627 } else {
628
629 // calculate operands for unoptimized case
630 lhs = Treewalk(node->GetLeftChild());
631 rhs = Treewalk(node->GetRightChild());
632 }
633
634 // generate subtraction code
635 IOperand *result = (dest != NULL) ? dest : new IOperand_Symbol(GenerateTempVar(node->GetReturnType()));
636 IOperator op = ( (node->GetReturnType() == RT_INT) ? IOP_SUB_I : IOP_SUB_R );
637 if (constant == NULL) {
638 icode->AppendStatement(new IStatement(op, lhs, rhs, result));
639 } else {
640 IOperand *temp = new IOperand_Symbol(GenerateTempVar(node->GetReturnType()));
641 icode->AppendStatement(new IStatement(op, lhs, rhs, temp));
642 /* Constant could be negative, so always all value */
643 IOperator op = ( (node->GetReturnType() == RT_INT) ? IOP_ADD_I : IOP_ADD_R );
644 icode->AppendStatement(new IStatement(op, temp->Clone(), constant, result));
645 }
646
647 return (dest != NULL) ? dest : result->Clone();
648 }
649 break;
650 case NODE_OR: // Bitwise OR operation
651 {
652 // calculate operands
653 IOperand *lhs = Treewalk(node->GetLeftChild());
654 IOperand *rhs = Treewalk(node->GetRightChild());
655
656 // attempt optimizations
657 if (bOptimize1) {
658 // 0 or X will always evaluate to X
659 if (IsZero(lhs)) {
660 delete lhs;
661 return rhs;
662 }
663
664 // X or 0 will always evaluate to X
665 if (IsZero(rhs)) {
666 delete rhs;
667 return lhs;
668 }
669
670 // constant folding
671 if (IsConstant(lhs) && IsConstant(rhs)) {
672 IOperand *result = new IOperand_Int(lhs->GetIntValue() | rhs->GetIntValue());
673 delete lhs;
674 delete rhs;
675 return result;
676 }
677 }
678
679 // generate bitwise or code
680 IOperand *result = (dest != NULL) ? dest : new IOperand_Symbol(GenerateTempVar(RT_INT));
681 icode->AppendStatement(new IStatement(IOP_OR, lhs, rhs, result));
682 return (dest != NULL) ? dest : result->Clone();
683 }
684 break;
685 case NODE_MUL: // Multiply
686 {
687 // calculate operands
688 IOperand *lhs = Treewalk(node->GetLeftChild());
689 IOperand *rhs = Treewalk(node->GetRightChild());
690
691 // attempt optimizations
692 if (bOptimize1) {
693 // zero product
694 if (IsZero(lhs) || IsZero(rhs)) {
695 delete lhs;
696 delete rhs;
697 return new IOperand_Int(0);
698 }
699
700 // algebraic identity
701 if (IsOne(lhs)) {
702 delete lhs;
703 return rhs;
704 }
705 if (IsOne(rhs)) {
706 delete rhs;
707 return lhs;
708 }
709
710 // constant folding
711 if (IsConstant(lhs) && IsConstant(rhs)) {
712 IOperand *result = NULL;
713 if (IsInt(lhs)) {
714 result = new IOperand_Int(lhs->GetIntValue() * rhs->GetIntValue());
715 } else {
716 result = new IOperand_Real(lhs->GetRealValue() * rhs->GetRealValue());
717 }
718 delete lhs;
719 delete rhs;
720 return result;
721 }
722 }
723
724 // generate multiply code
725 IOperand *result = (dest != NULL) ? dest : new IOperand_Symbol(GenerateTempVar(node->GetReturnType()));
726 IOperator op = ( (node->GetReturnType() == RT_INT) ? IOP_MUL_I : IOP_MUL_R );
727 icode->AppendStatement(new IStatement(op, lhs, rhs, result));
728 return (dest != NULL) ? dest : result->Clone();
729 }
730 break;
731 case NODE_DIV: // Divide
732 {
733 // calculate operands
734 IOperand *lhs = Treewalk(node->GetLeftChild());
735 IOperand *rhs = Treewalk(node->GetRightChild());
736
737 // attempt optimizations
738 if (bOptimize1) {
739 // 0 / X will always evaluate to zero
740 if (IsZero(lhs)) {
741 delete lhs;
742 delete rhs;
743 return new IOperand_Real(0);
744 }
745
746 // X / 1 will always evuluate to X
747 if (IsOne(rhs)) {
748 delete rhs;
749 return lhs;
750 }
751
752 // XXX: How to act on X / 0, which should not be possible
753
754 // constant folding
755 if (IsConstant(lhs) && IsConstant(rhs)) {
756 IOperand *result = NULL;
757 result = new IOperand_Real(lhs->GetRealValue() / rhs->GetRealValue());
758 delete lhs;
759 delete rhs;
760 return result;
761 }
762 }
763
764 // generate division code
765 IOperand *result = (dest != NULL) ? dest : new IOperand_Symbol(GenerateTempVar(node->GetReturnType()));
766 icode->AppendStatement(new IStatement(IOP_DIV_R, lhs, rhs, result));
767 return (dest != NULL) ? dest : result->Clone();
768 }
769 break;
770 case NODE_IDIV: // Integer division
771 {
772 // calculate operands
773 IOperand *lhs = Treewalk(node->GetLeftChild());
774 IOperand *rhs = Treewalk(node->GetRightChild());
775
776 // attempt optimizations
777 if (bOptimize1) {
778 // 0 / X will always evaluate to zero
779 if (IsZero(lhs)) {
780 delete lhs;
781 delete rhs;
782 return new IOperand_Int(0);
783 }
784
785 // X / 1 will always evuluate to X
786 if (IsOne(rhs)) {
787 delete rhs;
788 return lhs;
789 }
790
791 // XXX: How to act on X / 0, which should not be possible
792
793 // constant folding
794 if (IsConstant(lhs) && IsConstant(rhs)) {
795 IOperand *result = NULL;
796 result = new IOperand_Int(lhs->GetIntValue() / rhs->GetIntValue());
797 delete lhs;
798 delete rhs;
799 return result;
800 }
801 }
802
803 // generate division code
804 IOperand *result = (dest != NULL) ? dest : new IOperand_Symbol(GenerateTempVar(node->GetReturnType()));
805 icode->AppendStatement(new IStatement(IOP_DIV_I, lhs, rhs, result));
806 return (dest != NULL) ? dest : result->Clone();
807 }
808 break;
809 case NODE_MOD: // Modulo
810 {
811 // calculate operands
812 IOperand *lhs = Treewalk (node->GetLeftChild ());
813 IOperand *rhs = Treewalk (node->GetRightChild ());
814
815 // attempt optimizations
816 if (bOptimize1) {
817 // 0 mod X will always evaluate to zero
818 if (IsZero (lhs)) {
819 delete lhs;
820 delete rhs;
821 return new IOperand_Int (0);
822 }
823
824 // X mod 1 will always evaluate to zero
825 if (IsOne (rhs)) {
826 delete lhs;
827 delete rhs;
828 return new IOperand_Int (0);
829 }
830 // X mod -1 will always evaluate to zero
831 if (IsMinusOne (rhs)) {
832 delete lhs;
833 delete rhs;
834 return new IOperand_Int (0);
835 }
836 }
837
838 // generate modulus code
839 IOperand *result = (dest != NULL) ? dest : new IOperand_Symbol(GenerateTempVar(node->GetReturnType()));
840 icode->AppendStatement (new IStatement (IOP_MOD, lhs, rhs, result));
841 return (dest != NULL) ? dest : result->Clone();
842 }
843 break;
844 case NODE_AND: // Bitwise AND operation
845 {
846 // calculate operands
847 IOperand *lhs = Treewalk (node->GetLeftChild ());
848 IOperand *rhs = Treewalk (node->GetRightChild ());
849
850 // attempt optimizations
851 if (bOptimize1) {
852 // X and 0 will always evaluate to zero
853 if (IsZero (lhs) || IsZero (rhs)) {
854 delete lhs;
855 delete rhs;
856 return new IOperand_Int (0);
857 }
858 }
859
860 // generate bitwise and code
861 IOperand *result = (dest != NULL) ? dest : new IOperand_Symbol(GenerateTempVar(node->GetReturnType()));
862 icode->AppendStatement (new IStatement (IOP_AND, lhs, rhs, result));
863 return (dest != NULL) ? dest : result->Clone();
864 }
865 break;
866
867 /*
868 * Leafs
869 * these nodes have no child nodes
870 */
871 case NODE_NUM_INT: // Integer number
872 {
873 /* return the integer value */
874 return new IOperand_Int(node->GetIntValue());
875 }
876 break;
877 case NODE_NUM_REAL: // Real number
878 {
879 /* return the real value */
880 return new IOperand_Real(node->GetRealValue());
881 }
882 break;
883 case NODE_ID: // Identifier
884 {
885 /* ID requires returning its symbol */
886 return new IOperand_Symbol(node->GetSymbol());
887 }
888 break;
889 case NODE_EMPTY: // Empty leaf (terminates lists etc.)
890 {
891 return (NULL);
892 }
893 break;
894
895 /*
896 * Unary nodes
897 * child The subtree to which the operation has to be applied
898 */
899 case NODE_NOT: // NOT operation
900 {
901 IOperand *operand = ICGenerator::Treewalk (node->GetChild ());
902
903 // attempt optimizations
904 if (bOptimize1) {
905 // constant folding
906 if (IsConstant(operand)) {
907 IOperand *result = new IOperand_Int(~operand->GetIntValue());
908 delete operand;
909 return result;
910 }
911 }
912
913 IOperand *result = (dest != NULL) ? dest : new IOperand_Symbol(GenerateTempVar(node->GetReturnType()));
914 icode->AppendStatement (new IStatement (IOP_NOT, operand, NULL, result));
915
916 return (dest != NULL) ? dest : result->Clone();
917 }
918 break;
919 case NODE_SIGNPLUS: // Unary plus
920 {
921 /* Unary plus does not require any work, direct pass trough */
922 IOperand *operand = ICGenerator::Treewalk (node->GetChild ());
923 return (operand);
924 }
925 break;
926 case NODE_SIGNMINUS: // Unary minus
927 {
928 IOperand *operand = ICGenerator::Treewalk (node->GetChild ());
929
930 // attempt optimizations
931 if (bOptimize1) {
932 // constant folding
933 if (IsConstant(operand)) {
934 IOperand *result = NULL;
935 if (IsInt(operand)) {
936 result = new IOperand_Int(-operand->GetIntValue());
937 } else {
938 result = new IOperand_Real(-operand->GetRealValue());
939 }
940 delete operand;
941 return result;
942 }
943 }
944
945 ReturnType type = node->GetReturnType();
946 IOperator op = ( (type == RT_REAL) ? IOP_UNARY_MINUS_R : IOP_UNARY_MINUS_I );
947 IOperand *result = (dest != NULL) ? dest : new IOperand_Symbol(GenerateTempVar(type));
948 icode->AppendStatement (new IStatement (op, operand, NULL, result));
949 return (dest != NULL) ? dest : result->Clone();
950 }
951 break;
952 case NODE_COERCION: // Int to Real coercion
953 {
954 IOperand *operand = ICGenerator::Treewalk (node->GetChild ());
955
956 // attempt optimizations
957 if (bOptimize1) {
958 // constant folding
959 if (IsConstant(operand)) {
960 IOperand *result = new IOperand_Real(operand->GetIntValue());
961 delete operand;
962 return result;
963 }
964 }
965
966 IOperand *result = (dest != NULL) ? dest : new IOperand_Symbol(GenerateTempVar(RT_REAL));
967 icode->AppendStatement (new IStatement (IOP_INT_TO_REAL, operand, NULL, result));
968 return (dest != NULL) ? dest : result->Clone();
969 }
970 break;
971 default:
972 assert (0); // can't happen
973
974 }
975 return NULL; // silences warning
976}
977
978IOperand * ICGenerator::GenerateRelopCode(IOperator op, Node *node)
979{
980 // generate labels
981 Symbol *true_label = GenerateLabel();
982
983 // get operands
984 IOperand *lhs = Treewalk(node->GetLeftChild());
985 IOperand *rhs = Treewalk(node->GetRightChild());
986
987 // attempt optimizations
988 if (bOptimize1) {
989 // constant folding
990 if (IsConstant(lhs) && IsConstant(rhs)) {
991 int value;
992 switch (op) {
993 case IOP_BEQ_I: value = lhs->GetIntValue() == rhs->GetIntValue(); break;
994 case IOP_BLT_I: value = lhs->GetIntValue() < rhs->GetIntValue(); break;
995 case IOP_BGT_I: value = lhs->GetIntValue() > rhs->GetIntValue(); break;
996 case IOP_BLE_I: value = lhs->GetIntValue() <= rhs->GetIntValue(); break;
997 case IOP_BGE_I: value = lhs->GetIntValue() >= rhs->GetIntValue(); break;
998 case IOP_BNE_I: value = lhs->GetIntValue() != rhs->GetIntValue(); break;
999 case IOP_BEQ_R: value = lhs->GetRealValue() == rhs->GetRealValue(); break;
1000 case IOP_BLT_R: value = lhs->GetRealValue() < rhs->GetRealValue(); break;
1001 case IOP_BGT_R: value = lhs->GetRealValue() > rhs->GetRealValue(); break;
1002 case IOP_BLE_R: value = lhs->GetRealValue() <= rhs->GetRealValue(); break;
1003 case IOP_BGE_R: value = lhs->GetRealValue() >= rhs->GetRealValue(); break;
1004 case IOP_BNE_R: value = lhs->GetRealValue() != rhs->GetRealValue(); break;
1005 default:
1006 assert(0); // can't happen
1007 }
1008 IOperand *result = new IOperand_Int(value);
1009 delete lhs;
1010 delete rhs;
1011 return result;
1012 }
1013 }
1014
1015 /* generate code */
1016 /* Methode 1 | Methode 2
1017 * -------------------------------------
1018 * b = 0 goto TRUE | ret = 1
1019 * ret = 0 | b = 0 GOTO TRUE
1020 * goto END | ret = 0
1021 * :TRUE | :TRUE
1022 * ret = 1 |
1023 * :END |
1024 */
1025 /* Method 2 used */
1026 IOperand *result = new IOperand_Symbol(GenerateTempVar(RT_INT));
1027 icode->AppendStatement(new IStatement(IOP_ASSIGN_I, new IOperand_Int(1), NULL, result));
1028 icode->AppendStatement(new IStatement(op, lhs, rhs, new IOperand_Symbol(true_label)));
1029 icode->AppendStatement(new IStatement(IOP_ASSIGN_I, new IOperand_Int(0), NULL, result->Clone()));
1030 icode->AppendStatement(new IStatement(IOP_LABEL, new IOperand_Symbol(true_label), NULL, NULL));
1031 return result->Clone();
1032}
1033
1034bool ICGenerator::IsZero(IOperand *operand) const
1035{
1036 return (IsInt(operand) && operand->GetIntValue() == 0) ||
1037 (IsReal(operand) && operand->GetRealValue() == 0.0);
1038}
1039
1040bool ICGenerator::IsOne(IOperand *operand) const
1041{
1042 return (IsInt(operand) && operand->GetIntValue() == 1) ||
1043 (IsReal(operand) && operand->GetRealValue() == 1.0);
1044}
1045
1046bool ICGenerator::IsMinusOne(IOperand *operand) const
1047{
1048 return (IsInt(operand) && operand->GetIntValue() == -1) ||
1049 (IsReal(operand) && operand->GetRealValue() == -1.0);
1050}
1051
1052bool ICGenerator::IsConstant(IOperand *operand) const
1053{
1054 return IsInt(operand) || IsReal(operand);
1055}
1056
1057bool ICGenerator::IsInt(IOperand *operand) const
1058{
1059 return operand->GetOperandType() == OT_INT;
1060}
1061
1062bool ICGenerator::IsReal(IOperand *operand) const
1063{
1064 return operand->GetOperandType() == OT_REAL;
1065}
Note: See TracBrowser for help on using the repository browser.