/*
 * ICGenerator.cc - Implementation of the ICGenerator class
 *
 * Part of the assignment of the Compiler Construction course
 * LIACS, Leiden University
 *
 * This file will contain most of your work for assignment 3.
 */

#include "ICGenerator.h"

#include <sstream>
#include <cassert>
#include <list>
#include <iostream>

extern bool bOptimize1;
extern IntermediateCode *icode;
extern SymbolTable *symtab;

/* Macro to allow pretty display of parser tree calling stack debug print calls */
#define picg(x) pmesg(100, "Parser: '"); pmesg(100, x); pmesg(100, "'\n")

// Constructor
ICGenerator::ICGenerator() {
}


// Destructor
ICGenerator::~ICGenerator() {
}


// Preprocesses the syntax tree; this method is called before
// GenerateIntermediateCode() if optimizations are enabled
void ICGenerator::Preprocess (SyntaxTree * tree, SymbolTable * symtab) {
}


// Takes a SyntaxTree and converts it into an IntermediateCode structure
IntermediateCode * ICGenerator::GenerateIntermediateCode (SyntaxTree * inputTree, SymbolTable * symtab) {
  IStatement * istmt;

  icode = new IntermediateCode;

  /* Process program body */
  /* Make sure temponary generated variables are added to the right scope */
  symtab->SetCurrentScope(inputTree->GetProgramName());
  icode->SetProgramName(inputTree->GetProgramName());
  delete Treewalk(inputTree->GetProgramBody());

  /* Indicate end of program body */
  istmt = new IStatement (IOP_RETURN);
  icode->AppendStatement(istmt);

  /* Now walk through the list of subprograms, and process them one by one */
  for (int i = 0; i < inputTree->GetSubprogramCount(); i++) {
    // add subprogram code
    Symbol *subprogram = symtab->GetSymbol(inputTree->GetSubprogramName(i));
    /* Make sure temponary generated variables are added to the right scope */
    symtab->SetCurrentScope(inputTree->GetSubprogramName(i));
    icode->AppendStatement(new IStatement(IOP_SUBPROG, new IOperand_Symbol(subprogram), NULL, NULL));

    // add subprogram body code
    delete Treewalk(inputTree->GetSubprogram(i));

    // add code for return value
    IOperator op;
    switch (subprogram->GetReturnType()) {
      case RT_INT:
        op = IOP_RETURN_I;
        break;
      case RT_REAL:
        op = IOP_RETURN_R;
        break;
      case RT_VOID:
        op = IOP_RETURN;
        break;
      default:
        assert(0); // can't happen
    }
    icode->AppendStatement(new IStatement(op, (op == IOP_RETURN) ? NULL : new IOperand_Symbol(subprogram), NULL, NULL));
  }

  return icode;
}


// Postprocesses the intermediate code; this method is called after
// GenerateIntermediateCode() if optimizations are enabled
void ICGenerator::Postprocess (IntermediateCode * code, SymbolTable * symtab) {
  /* Some trivial optimalisations which could be implemented */

  /* 1) LABEL X
   * 2) GOTO :Y
   * Alter GOTO :X to GOTO :Y directly
   */

  /* 1) LABEL X
   * 2) RETURN tX
   * Alter GOTO :X to RETURN tX directly
   */

  /* 1) ASSIGN foo tX
   * ... no use of tX, in the meantime ...
   * X) ASSIGN bar tX
   * Delete line 1)
   */

  /* Less trivials optimalisations which could be implemented*/

  /* Unfold small for loops */

  /* Delete/mangle branching code if TEST expression to always to be evaluated TRUE of FALSE */

  /* Detect and remove useless IOP_ASSIGN_[IR] statements */

  /* When parameters of function are not used, do not assign */

  /* 1) ASSIGN int(1) tX
   * 2) ASSIGN int(2) tY
   * 3) ADD_I tX tY tZ
   * Convert line 3) to ASSIGN int(3) tZ
   */

  /* 1) LABEL L_1
   * 2) LABEL L_2
   * Convert all GOTO L_2 to GOTO L_1 and delete L_2
   */
}


// Generate a temporary symbol
Symbol * ICGenerator::GenerateTempVar(ReturnType type) {
  /* Keep track of variables given out, make all generated unique for the sake
   * of debugging
   */
  static int count = 0;
  count++;

  Symbol *symbol = new Symbol();
  symbol->SetSymbolType(ST_TEMPVAR);
  symbol->SetReturnType(type);
  std::stringstream ss;
  ss << "t" << count;
  symbol->SetName(ss.str());

  /* Make sure to add it to the symbol table */
  symtab->AddSymbol(symbol);
  return symbol;
}


// Generates a Symbol for a label
Symbol * ICGenerator::GenerateLabel() {
  /* Keep track of variables given out, make all generated unique for the sake
   * of debugging
   */
  static int count = 0;
  count++;

  Symbol *symbol = new Symbol();
  symbol->SetSymbolType(ST_LABEL);
  std::stringstream ss;
  ss << "L_" << count;
  symbol->SetName(ss.str());

  /* Make sure to add it to the symbol table */
  symtab->AddSymbol(symbol);
  return symbol;
}

IOperand *ICGenerator::Treewalk (Node * node, IOperand *dest, IOperand *constant)
{
  switch (node->GetNodeType ())
    {
    case NODE_UNKNOWN:		// Unknown (yet)
      assert (0);		// can't happen
      break;
    case NODE_ERROR:		// Error
      assert (0);		// can't happen
      break;

      /*
       * Statement list
       * left child     One of, NODE_ASSIGNMENT, NODE_IF, NODE_WHILE,
       * NODE_PROCCALL, NODE_FUNCTIONCALL, NODE_STATEMENT_LIST.
       * right child    One of, NODE_ASSIGNMENT, NODE_IF, NODE_WHILE,
       * NODE_PROCCALL, NODE_FUNCTIONCALL, NODE_STATEMENT_LIST, or
       * NODE_EMPTY if no more statements follow.
       */
    case NODE_STATEMENT_LIST:
      {
        delete Treewalk(node->GetLeftChild());
        delete Treewalk(node->GetRightChild());
        return NULL;
      }
      break;

      /*
       * Assignment
       * left child     A NODE_ID that identifies the destination variable
       * right child    A subtree representing an expression
       */
    case NODE_ASSIGNMENT:
      {
        IOperand *result = Treewalk(node->GetLeftChild());
        IOperand *operand = Treewalk(node->GetRightChild(), bOptimize1 ? result : NULL);
        if (operand != result) {
          IOperator op = ( (node->GetLeftChild()->GetReturnType() == RT_REAL) ? IOP_ASSIGN_R : IOP_ASSIGN_I );
          icode->AppendStatement(new IStatement(op, operand, NULL, result));
        }
        return NULL;
      }
      break;

      /*
       * If statement
       * left child     A NODE_BOOLEXPR that provides the if condition
       * right child    A NODE_IF_TARGETS subtree (if there is an else clause) or
       * a subtree consisting of statements (if there's no else)
       */
    case NODE_IF:
      {
        // generate labels
        Symbol *false_label = GenerateLabel();
        Symbol *end_label = GenerateLabel();

        // add evaluation code
        IOperand *evaluation = Treewalk(node->GetLeftChild());
        icode->AppendStatement(new IStatement(IOP_BEQ_I, evaluation, new IOperand_Int(0), new IOperand_Symbol(false_label)));

        // add code for true case
        Node *rightchild = node->GetRightChild();
        if (rightchild->GetNodeType() == NODE_IF_TARGETS) {
                delete Treewalk(rightchild->GetLeftChild());
                // there is a else part so skip over it
                icode->AppendStatement(new IStatement(IOP_GOTO, new IOperand_Symbol(end_label), NULL, NULL));
        } else {
                delete Treewalk(rightchild);
        }

        // add label for false part
        icode->AppendStatement(new IStatement(IOP_LABEL, new IOperand_Symbol(false_label), NULL, NULL));

        // add code for false/else case if any
        if (rightchild->GetNodeType() == NODE_IF_TARGETS) {
                delete Treewalk(rightchild->GetRightChild ());
               // add end label
                icode->AppendStatement(new IStatement(IOP_LABEL, new IOperand_Symbol(end_label), NULL, NULL));
        }

        return NULL;
      }
      break;

      /*
       * Targets of an if-else-statement
       * left child     The statements that have to be executed when the condition
       * of the parent if-statement is true.
       * right child    The statements that have to be executed when the condition
       * of the parent if-statement is false: that is: the else
       * part.
       */
    case NODE_IF_TARGETS:
      assert(0);        // handled in NODE_IF
      break;

      /*
       * While loop
       * left child     A NODE_BOOLEXPR that provides the loop condition
       * right child    A subtree consisting of statements
       */
    case NODE_WHILE:
      {
        /* Method while tree
         * :START
         * if <expr> = 0 GOTO END
         * <body>
         * GOTO START
         * :END
         */
        // generate labels
        Symbol *start_label = GenerateLabel();
        Symbol *end_label = GenerateLabel();

        // add start label
        icode->AppendStatement(new IStatement(IOP_LABEL, new IOperand_Symbol(start_label), NULL, NULL));

        // add evaluation code
        IOperand *evaluation = Treewalk(node->GetLeftChild());
        icode->AppendStatement(new IStatement(IOP_BEQ_I, evaluation, new IOperand_Int(0), new IOperand_Symbol(end_label)));

        // add code
        delete Treewalk(node->GetLeftChild());

        // add jump back to start
        icode->AppendStatement(new IStatement(IOP_GOTO, new IOperand_Symbol(start_label), NULL, NULL));

        // add end label
        icode->AppendStatement(new IStatement(IOP_LABEL, new IOperand_Symbol(end_label), NULL, NULL));

        return NULL;
      }
      break;

      /*
       * Subprogram calls
       * left child     A NODE_ID that identifies the called function/procedure
       * right child    A NODE_EXPRLIST that specifies the actual arguments: or
       * NODE_EMPTY if no arguments required.
       */
    case NODE_PROCCALL:
      {
        // pass parameters
        delete Treewalk(node->GetRightChild());

        // add call statement
        IOperand *id = Treewalk(node->GetLeftChild());
        icode->AppendStatement(new IStatement(IOP_PROCCALL, id, NULL, NULL));

        return NULL;
      }
      break;
    case NODE_FUNCTIONCALL:
      {
        // pass parameters
        delete Treewalk(node->GetRightChild());

        // add call statement
        IOperand *id = Treewalk(node->GetLeftChild());
        IOperand *result = (dest != NULL) ? dest : new IOperand_Symbol(GenerateTempVar(node->GetReturnType()));
        icode->AppendStatement(new IStatement(IOP_FUNCCALL, id, NULL, result));

        return (dest != NULL) ? dest : result->Clone();
      }
      break;

      /*
       * Expression list
       * left child     A subtree representing an expression
       * right child    A subtree representing an expression: another
       * NODE_EXPRLIST: or NODE_EMPTY if no more expressions follow
       * in the expression list.
       */
    case NODE_EXPRLIST:
      {
        // pass parameter
        IOperand *parameter = Treewalk(node->GetLeftChild());
        ReturnType type = node->GetLeftChild()->GetReturnType();
        IOperator op = ( (type == RT_REAL) ? IOP_PARAM_R : IOP_PARAM_I );
        icode->AppendStatement(new IStatement(op, parameter, NULL, NULL));

        // pass any other parameters
        delete Treewalk(node->GetRightChild());

        return NULL;
      }
      break;

      /*
       * Boolean-like expression
       * child          A subtree with any NODE_REL_ node as parent
       */
    case NODE_BOOLEXPR:
      {
        return Treewalk(node->GetChild());
      }
      break;

      /*
       * Relational operators
       * left child     Left-hand side of the comparison
       * right child    Right-hand side of the comparison
       */
    case NODE_REL_EQUAL:	//  = operator
      {
        ReturnType type = node->GetLeftChild()->GetReturnType();
        IOperator op = ((type == RT_INT) ? IOP_BEQ_I : IOP_BEQ_R);
        return GenerateRelopCode(op, node);
      }
      break;
    case NODE_REL_LT:		//  < operator
      {
        ReturnType type = node->GetLeftChild()->GetReturnType();
        IOperator op = ((type == RT_INT) ? IOP_BLT_I : IOP_BLT_R);
        return GenerateRelopCode(op, node);
      }
      break;
    case NODE_REL_GT:		//  > operator
      {
        ReturnType type = node->GetLeftChild()->GetReturnType();
        IOperator op = ((type == RT_INT) ? IOP_BGT_I : IOP_BGT_R);
        return GenerateRelopCode(op, node);
      }
      break;
    case NODE_REL_LTE:		//  <= operator
      {
        ReturnType type = node->GetLeftChild()->GetReturnType();
        IOperator op = ((type == RT_INT) ? IOP_BLE_I : IOP_BLE_R);
        return GenerateRelopCode(op, node);
      }
      break;
    case NODE_REL_GTE:		//  >= operator
      {
        ReturnType type = node->GetLeftChild()->GetReturnType();
        IOperator op = ((type == RT_INT) ? IOP_BGE_I : IOP_BGE_R);
        return GenerateRelopCode(op, node);
      }
      break;
    case NODE_REL_NOTEQUAL:	//  <> operator
      {
        ReturnType type = node->GetLeftChild()->GetReturnType();
        IOperator op = ((type == RT_INT) ? IOP_BNE_I : IOP_BNE_R);
        return GenerateRelopCode(op, node);
      }
      break;

      /*
       * Binary arithmetic & logic operations
       * left child     Left-hand side of the operation
       * right child    Right-hand side of the operation
       */
    case NODE_ADD:		// Add
      {
        IOperand *lhs = NULL;
        IOperand *rhs = NULL;

        // attempt optimizations
        if (bOptimize1) {
          /* reverse evaluation of operands, due to the fact the tree is always
           * set to be on the left and we like to fold constants where ever
           * possible
           */
          rhs = Treewalk(node->GetRightChild());
          // check if we need to push any constant down the tree
          if (node->GetLeftChild()->GetNodeType() == NODE_ADD ||
              node->GetLeftChild()->GetNodeType() == NODE_SUB ) {
            if (IsConstant(rhs)) {
              // right hand side is also constant
              if (constant != NULL) {
                if (IsInt(rhs)) {
                  rhs->SetIntValue(rhs->GetIntValue() + constant->GetIntValue());
                } else {
                  rhs->SetRealValue(rhs->GetRealValue() + constant->GetRealValue());
                }
              }
              // evaluate left hand side passing constant value
              lhs = Treewalk(node->GetLeftChild(), dest, rhs);
              return lhs;
            } else {
              // generate add instruction for the right hand side
              IOperator op = ( (node->GetReturnType() == RT_INT) ? IOP_ADD_I : IOP_ADD_R );
              lhs = Treewalk(node->GetLeftChild(), NULL, constant);
              IOperand *result = (dest != NULL) ? dest : new IOperand_Symbol(GenerateTempVar(node->GetReturnType()));
              icode->AppendStatement(new IStatement(op, lhs, rhs, result));
              return (dest != NULL) ? dest : result->Clone(); 
            }
          } else {
            // can't push down constant
            lhs = Treewalk(node->GetLeftChild());
          }

          // try to add the constant, if any, to any constant lhs or rhs
          if (constant != NULL) {
            if (IsConstant(lhs)) {
              if (IsInt(lhs)) {
                lhs->SetIntValue(lhs->GetIntValue() + constant->GetIntValue());
              } else {
                lhs->SetRealValue(lhs->GetRealValue() + constant->GetRealValue());
              }
              delete constant;
              constant = NULL;
            } else if (IsConstant(rhs)) {
              if (IsInt(rhs)) {
                rhs->SetIntValue(rhs->GetIntValue() + constant->GetIntValue());
              } else {
                rhs->SetRealValue(rhs->GetRealValue() + constant->GetRealValue());
              }
              delete constant;
              constant = NULL;
            }
          }

          // algebraic identity
          if (IsZero(lhs)) {
            delete lhs;
            return rhs;
          }
          if (IsZero(rhs)) {
            delete rhs;
            return lhs;
          }

          // constant folding
          if (IsConstant(lhs) && IsConstant(rhs)) {
            IOperand *result = NULL;
            if (IsInt(lhs)) {
              result = new IOperand_Int(lhs->GetIntValue() + rhs->GetIntValue() + ((constant==NULL) ? 0 : constant->GetIntValue()));
            } else {
              result = new IOperand_Real(lhs->GetRealValue() + rhs->GetRealValue() + ((constant==NULL) ? 0 : constant->GetRealValue()));
            }
            delete lhs;
            delete rhs;
            return result;
          }
        } else {

          // calculate operands for unoptimized case
          lhs = Treewalk(node->GetLeftChild());
          rhs = Treewalk(node->GetRightChild());
        }

        // generate add code
        IOperand *result = (dest != NULL) ? dest : new IOperand_Symbol(GenerateTempVar(node->GetReturnType()));
        IOperator op = ( (node->GetReturnType() == RT_INT) ? IOP_ADD_I : IOP_ADD_R );
        if (constant == NULL) {
          icode->AppendStatement(new IStatement(op, lhs, rhs, result));
        } else {
          IOperand *temp = new IOperand_Symbol(GenerateTempVar(node->GetReturnType()));
          icode->AppendStatement(new IStatement(op, lhs, rhs, temp));
          icode->AppendStatement(new IStatement(op, temp->Clone(), constant, result));
        }
        return (dest != NULL) ? dest : result->Clone();
      }
      break;
    case NODE_SUB:		// Substract
      {
        // calculate operands
        IOperand *lhs = NULL;
        IOperand *rhs = NULL;

        // attempt optimizations
        if (bOptimize1) {
          /* reverse evaluation of operands, due to the fact the tree is always
           * set to be on the left and we like to fold constants where ever
           * possible
           */
          rhs = Treewalk(node->GetRightChild());
          // check if we need to push any constant down the tree
          if (node->GetLeftChild()->GetNodeType() == NODE_ADD ||
              node->GetLeftChild()->GetNodeType() == NODE_SUB ) {
            if (IsConstant(rhs)) {
              // right hand side is also constant
              if (constant != NULL) {
                if (IsInt(rhs)) {
                  rhs->SetIntValue((rhs->GetIntValue() * -1) + constant->GetIntValue());
                } else {
                  rhs->SetRealValue((rhs->GetRealValue() * -1) + constant->GetRealValue());
                }
              } else {
                /* Negate fresh new minus knob, if it is gonna be the first constant */
                if (IsInt(rhs)) {
                  rhs->SetIntValue(rhs->GetIntValue() * -1);
                } else {
                  rhs->SetRealValue(rhs->GetRealValue() * -1);
                }
              }

              // evaluate left hand side passing constant value
              lhs = Treewalk(node->GetLeftChild(), dest, rhs);
              return lhs;
            } else {
              // generate add instruction for the right hand side
              IOperator op = ( (node->GetReturnType() == RT_INT) ? IOP_SUB_I : IOP_SUB_R );
              lhs = Treewalk(node->GetLeftChild(), NULL, constant);
              IOperand *result = (dest != NULL) ? dest : new IOperand_Symbol(GenerateTempVar(node->GetReturnType()));
              icode->AppendStatement(new IStatement(op, lhs, rhs, result));
              return (dest != NULL) ? dest : result->Clone(); 
            }
          } else {
            // can't push down constant
            lhs = Treewalk(node->GetLeftChild());
          }

          // try to sub the constant, if any, to any constant lhs or rhs
          if (constant != NULL) {
            if (IsConstant(lhs)) {
              if (IsInt(lhs)) {
                lhs->SetIntValue(lhs->GetIntValue() + constant->GetIntValue());
              } else {
                lhs->SetRealValue(lhs->GetRealValue() + constant->GetRealValue());
              }
              delete constant;
              constant = NULL;
            } else if (IsConstant(rhs)) {
              /* Negate right side as it is going to be negative constant value */
              if (IsInt(rhs)) {
                rhs->SetIntValue((rhs->GetIntValue() * -1) + constant->GetIntValue());
              } else {
                rhs->SetRealValue((rhs->GetRealValue() * -1) + constant->GetRealValue());
              }
              delete constant;
              constant = NULL;
            }
          }

          // algebraic identity right side
          if (IsZero(rhs)) {
            delete rhs;
            return lhs;
          }

          // constant folding
          if (IsConstant(lhs) && IsConstant(rhs)) {
            IOperand *result = NULL;
            if (IsInt(lhs)) {
              result = new IOperand_Int(lhs->GetIntValue() - rhs->GetIntValue());
            } else {
              result = new IOperand_Real(lhs->GetRealValue() - rhs->GetRealValue());
            }
            delete lhs;
            delete rhs;
            return result;
          }

          // algebraic identity left side
          if (IsZero(lhs)) {
            delete lhs;

            // generate unary minus code
            IOperand *result = (dest != NULL) ? dest : new IOperand_Symbol(GenerateTempVar(node->GetReturnType()));
            IOperator op = ( (node->GetReturnType() == RT_INT) ? IOP_UNARY_MINUS_I : IOP_UNARY_MINUS_R );
            icode->AppendStatement(new IStatement(op, rhs, NULL, result));
            return (dest != NULL) ? dest : result->Clone();
          }
        } else {

          // calculate operands for unoptimized case
          lhs = Treewalk(node->GetLeftChild());
          rhs = Treewalk(node->GetRightChild());
        }

        // generate subtraction code
        IOperand *result = (dest != NULL) ? dest : new IOperand_Symbol(GenerateTempVar(node->GetReturnType()));
        IOperator op = ( (node->GetReturnType() == RT_INT) ? IOP_SUB_I : IOP_SUB_R );
        if (constant == NULL) {
          icode->AppendStatement(new IStatement(op, lhs, rhs, result));
        } else {
          IOperand *temp = new IOperand_Symbol(GenerateTempVar(node->GetReturnType()));
          icode->AppendStatement(new IStatement(op, lhs, rhs, temp));
          /* Constant could be negative, so always all value */
          IOperator op = ( (node->GetReturnType() == RT_INT) ? IOP_ADD_I : IOP_ADD_R );
          icode->AppendStatement(new IStatement(op, temp->Clone(), constant, result));
        }

        return (dest != NULL) ? dest : result->Clone();
      }
      break;
    case NODE_OR:		// Bitwise OR operation
      {
        // calculate operands
        IOperand *lhs = Treewalk(node->GetLeftChild());
        IOperand *rhs = Treewalk(node->GetRightChild());

        // attempt optimizations
        if (bOptimize1) {
          // 0 or X will always evaluate to X
          if (IsZero(lhs)) {
            delete lhs;
            return rhs;
          }

          // X or 0 will always evaluate to X
          if (IsZero(rhs)) {
            delete rhs;
            return lhs;
          }

          // constant folding
          if (IsConstant(lhs) && IsConstant(rhs)) {
            IOperand *result = new IOperand_Int(lhs->GetIntValue() | rhs->GetIntValue());
            delete lhs;
            delete rhs;
            return result;
          }
        }

        // generate bitwise or code
        IOperand *result = (dest != NULL) ? dest : new IOperand_Symbol(GenerateTempVar(RT_INT));
        icode->AppendStatement(new IStatement(IOP_OR, lhs, rhs, result));
        return (dest != NULL) ? dest : result->Clone();
      }
      break;
    case NODE_MUL:		// Multiply
      {
        // calculate operands
        IOperand *lhs = Treewalk(node->GetLeftChild());
        IOperand *rhs = Treewalk(node->GetRightChild());

        // attempt optimizations
        if (bOptimize1) {
          // zero product
          if (IsZero(lhs) || IsZero(rhs)) {
            delete lhs;
            delete rhs;
            return new IOperand_Int(0);
          }

          // algebraic identity
          if (IsOne(lhs)) {
            delete lhs;
            return rhs;
          }
          if (IsOne(rhs)) {
            delete rhs;
            return lhs;
          }

          // constant folding
          if (IsConstant(lhs) && IsConstant(rhs)) {
            IOperand *result = NULL;
            if (IsInt(lhs)) {
              result = new IOperand_Int(lhs->GetIntValue() * rhs->GetIntValue());
            } else {
              result = new IOperand_Real(lhs->GetRealValue() * rhs->GetRealValue());
            }
            delete lhs;
            delete rhs;
            return result;
          }
        }

        // generate multiply code
        IOperand *result = (dest != NULL) ? dest : new IOperand_Symbol(GenerateTempVar(node->GetReturnType()));
        IOperator op = ( (node->GetReturnType() == RT_INT) ? IOP_MUL_I : IOP_MUL_R );
        icode->AppendStatement(new IStatement(op, lhs, rhs, result));
        return (dest != NULL) ? dest : result->Clone();
      }
      break;
    case NODE_DIV:		// Divide
      {
        // calculate operands
        IOperand *lhs = Treewalk(node->GetLeftChild());
        IOperand *rhs = Treewalk(node->GetRightChild());

        // attempt optimizations
        if (bOptimize1) {
          // 0 / X  will always evaluate to zero
          if (IsZero(lhs)) {
            delete lhs;
            delete rhs;
            return new IOperand_Real(0);
          }

          // X / 1 will always evuluate to X
          if (IsOne(rhs)) {
            delete rhs;
            return lhs;
          }

          // XXX: How to act on X / 0, which should not be possible

          // constant folding
          if (IsConstant(lhs) && IsConstant(rhs)) {
            IOperand *result = NULL;
            result = new IOperand_Real(lhs->GetRealValue() / rhs->GetRealValue());
            delete lhs;
            delete rhs;
            return result;
          }
        }

        // generate division code
        IOperand *result = (dest != NULL) ? dest : new IOperand_Symbol(GenerateTempVar(node->GetReturnType()));
        icode->AppendStatement(new IStatement(IOP_DIV_R, lhs, rhs, result));
        return (dest != NULL) ? dest : result->Clone();
      }
      break;
    case NODE_IDIV:		// Integer division
      {
        // calculate operands
        IOperand *lhs = Treewalk(node->GetLeftChild());
        IOperand *rhs = Treewalk(node->GetRightChild());

        // attempt optimizations
        if (bOptimize1) {
          // 0 / X  will always evaluate to zero
          if (IsZero(lhs)) {
            delete lhs;
            delete rhs;
            return new IOperand_Int(0);
          }

          // X / 1 will always evuluate to X
          if (IsOne(rhs)) {
            delete rhs;
            return lhs;
          }

          // XXX: How to act on X / 0, which should not be possible

          // constant folding
          if (IsConstant(lhs) && IsConstant(rhs)) {
            IOperand *result = NULL;
            result = new IOperand_Int(lhs->GetIntValue() / rhs->GetIntValue());
            delete lhs;
            delete rhs;
            return result;
          }
        }

        // generate division code
        IOperand *result = (dest != NULL) ? dest : new IOperand_Symbol(GenerateTempVar(node->GetReturnType()));
        icode->AppendStatement(new IStatement(IOP_DIV_I, lhs, rhs, result));
        return (dest != NULL) ? dest : result->Clone();
      }
      break;
    case NODE_MOD:		// Modulo
      {
        // calculate operands
        IOperand *lhs = Treewalk (node->GetLeftChild ());
        IOperand *rhs = Treewalk (node->GetRightChild ());

        // attempt optimizations
        if (bOptimize1) {
            // 0 mod X will always evaluate to zero
            if (IsZero (lhs)) {
                delete lhs;
                delete rhs;
                return new IOperand_Int (0);
              }

            // X mod 1 will always evaluate to zero
            if (IsOne (rhs)) {
                delete lhs;
                delete rhs;
                return new IOperand_Int (0);
            }
            // X mod -1 will always evaluate to zero
            if (IsMinusOne (rhs)) {
                delete lhs;
                delete rhs;
                return new IOperand_Int (0);
            }
          }

        // generate modulus code
        IOperand *result = (dest != NULL) ? dest : new IOperand_Symbol(GenerateTempVar(node->GetReturnType()));
        icode->AppendStatement (new IStatement (IOP_MOD, lhs, rhs, result));
        return (dest != NULL) ? dest : result->Clone();
      }
      break;
    case NODE_AND:		// Bitwise AND operation
      {
        // calculate operands
        IOperand *lhs = Treewalk (node->GetLeftChild ());
        IOperand *rhs = Treewalk (node->GetRightChild ());

        // attempt optimizations
        if (bOptimize1) {
            // X and 0 will always evaluate to zero
            if (IsZero (lhs) || IsZero (rhs)) {
                delete lhs;
                delete rhs;
                return new IOperand_Int (0);
              }
          }

        // generate bitwise and code
        IOperand *result = (dest != NULL) ? dest : new IOperand_Symbol(GenerateTempVar(node->GetReturnType()));
        icode->AppendStatement (new IStatement (IOP_AND, lhs, rhs, result));
        return (dest != NULL) ? dest : result->Clone();
      }
      break;

      /*
       * Leafs
       * these nodes have no child nodes
       */
    case NODE_NUM_INT:		// Integer number
      {
        /* return the integer value */
        return new IOperand_Int(node->GetIntValue());
      }
      break;
    case NODE_NUM_REAL:		// Real number
      {
        /* return the real value */
        return new IOperand_Real(node->GetRealValue());
      }
      break;
    case NODE_ID:		// Identifier
      {
        /* ID requires returning its symbol */
        return new IOperand_Symbol(node->GetSymbol());
      }
      break;
    case NODE_EMPTY:		// Empty leaf (terminates lists etc.)
      {
        return (NULL);
      }
      break;

      /*
       * Unary nodes
       * child          The subtree to which the operation has to be applied
       */
    case NODE_NOT:		// NOT operation
      {
        IOperand *operand = ICGenerator::Treewalk (node->GetChild ());

        // attempt optimizations
        if (bOptimize1) {
          // constant folding
          if (IsConstant(operand)) {
            IOperand *result = new IOperand_Int(~operand->GetIntValue());
            delete operand;
            return result;
          }
        }

        IOperand *result = (dest != NULL) ? dest : new IOperand_Symbol(GenerateTempVar(node->GetReturnType()));
        icode->AppendStatement (new IStatement (IOP_NOT, operand, NULL, result));

        return (dest != NULL) ? dest : result->Clone();
      }
      break;
    case NODE_SIGNPLUS:	// Unary plus
      {
        /* Unary plus does not require any work, direct pass trough */
        IOperand *operand = ICGenerator::Treewalk (node->GetChild ());
        return (operand);
      }
      break;
    case NODE_SIGNMINUS:	// Unary minus
      {
        IOperand *operand = ICGenerator::Treewalk (node->GetChild ());

        // attempt optimizations
        if (bOptimize1) {
          // constant folding
          if (IsConstant(operand)) {
            IOperand *result = NULL;
            if (IsInt(operand)) {
              result = new IOperand_Int(-operand->GetIntValue());
            } else {
              result = new IOperand_Real(-operand->GetRealValue());
            }
            delete operand;
            return result;
          }
        }

        ReturnType type = node->GetReturnType();
        IOperator op = ( (type == RT_REAL) ? IOP_UNARY_MINUS_R : IOP_UNARY_MINUS_I );
        IOperand *result = (dest != NULL) ? dest : new IOperand_Symbol(GenerateTempVar(type));
        icode->AppendStatement (new IStatement (op, operand, NULL, result));
        return (dest != NULL) ? dest : result->Clone();
      }
      break;
    case NODE_COERCION:	// Int to Real coercion
      {
        IOperand *operand = ICGenerator::Treewalk (node->GetChild ());

        // attempt optimizations
        if (bOptimize1) {
          // constant folding
          if (IsConstant(operand)) {
            IOperand *result = new IOperand_Real(operand->GetIntValue());
            delete operand;
            return result;
          }
        }

        IOperand *result = (dest != NULL) ? dest : new IOperand_Symbol(GenerateTempVar(RT_REAL));
        icode->AppendStatement (new IStatement (IOP_INT_TO_REAL, operand, NULL, result));
        return (dest != NULL) ? dest : result->Clone();
      }
      break;
    default:
      assert (0);		// can't happen

    }
    return NULL;                // silences warning
}

IOperand * ICGenerator::GenerateRelopCode(IOperator op, Node *node)
{
  // generate labels
  Symbol *true_label = GenerateLabel();

  // get operands
  IOperand *lhs = Treewalk(node->GetLeftChild());
  IOperand *rhs = Treewalk(node->GetRightChild());

  // attempt optimizations
  if (bOptimize1) {
    // constant folding
    if (IsConstant(lhs) && IsConstant(rhs)) {
      int value;
      switch (op) {
        case IOP_BEQ_I: value = lhs->GetIntValue() == rhs->GetIntValue(); break;
        case IOP_BLT_I: value = lhs->GetIntValue() < rhs->GetIntValue(); break;
        case IOP_BGT_I: value = lhs->GetIntValue() > rhs->GetIntValue(); break;
        case IOP_BLE_I: value = lhs->GetIntValue() <= rhs->GetIntValue(); break;
        case IOP_BGE_I: value = lhs->GetIntValue() >= rhs->GetIntValue(); break;
        case IOP_BNE_I: value = lhs->GetIntValue() != rhs->GetIntValue(); break;
        case IOP_BEQ_R: value = lhs->GetRealValue() == rhs->GetRealValue(); break;
        case IOP_BLT_R: value = lhs->GetRealValue() < rhs->GetRealValue(); break;
        case IOP_BGT_R: value = lhs->GetRealValue() > rhs->GetRealValue(); break;
        case IOP_BLE_R: value = lhs->GetRealValue() <= rhs->GetRealValue(); break;
        case IOP_BGE_R: value = lhs->GetRealValue() >= rhs->GetRealValue(); break;
        case IOP_BNE_R: value = lhs->GetRealValue() != rhs->GetRealValue(); break;
        default:
          assert(0); // can't happen
      }
      IOperand *result = new IOperand_Int(value);
      delete lhs;
      delete rhs;
      return result;
    }
  }

  /* generate code */
  /* Methode 1          |   Methode 2
   * -------------------------------------
   * b = 0 goto TRUE    |   ret = 1
   * ret = 0            |   b = 0 GOTO TRUE
   * goto END           |   ret = 0
   * :TRUE              |   :TRUE
   * ret = 1            |
   * :END               |
   */
  /* Method 2 used */
  IOperand *result = new IOperand_Symbol(GenerateTempVar(RT_INT));
  icode->AppendStatement(new IStatement(IOP_ASSIGN_I, new IOperand_Int(1), NULL, result));
  icode->AppendStatement(new IStatement(op, lhs, rhs, new IOperand_Symbol(true_label)));
  icode->AppendStatement(new IStatement(IOP_ASSIGN_I, new IOperand_Int(0), NULL, result->Clone()));
  icode->AppendStatement(new IStatement(IOP_LABEL, new IOperand_Symbol(true_label), NULL, NULL));
  return result->Clone();
}

bool ICGenerator::IsZero(IOperand *operand) const
{
  return (IsInt(operand) && operand->GetIntValue() == 0) ||
         (IsReal(operand) && operand->GetRealValue() == 0.0);
}

bool ICGenerator::IsOne(IOperand *operand) const
{
  return (IsInt(operand) && operand->GetIntValue() == 1) ||
         (IsReal(operand) && operand->GetRealValue() == 1.0);
}

bool ICGenerator::IsMinusOne(IOperand *operand) const
{
  return (IsInt(operand) && operand->GetIntValue() == -1) ||
         (IsReal(operand) && operand->GetRealValue() == -1.0);
}

bool ICGenerator::IsConstant(IOperand *operand) const
{
  return IsInt(operand) || IsReal(operand);
}

bool ICGenerator::IsInt(IOperand *operand) const
{
  return operand->GetOperandType() == OT_INT;
}

bool ICGenerator::IsReal(IOperand *operand) const
{
  return operand->GetOperandType() == OT_REAL;
}