import java.io.*;

public class adder
{

public static abstract class expr
{  String syntax;  // original text
   expr e1, e2; // subexpressions
   abstract int eval();
}

public static class constexp extends expr
{
  String label = "";		// label for the string ; added for compiler
  constexp(String s) { syntax = s; }
  int eval()
    { return (new Integer(syntax)).intValue(); }
}  // const

public static class sumexp extends expr
{ sumexp(String s, expr a, expr b)
   { syntax = s; e1 = a; e2 = b; }
  int eval()
   { return (e1.eval()) + (e2.eval()); }
}  // sum

public static class multexp extends expr
{ multexp(String s, expr a, expr b)
   { syntax = s; e1 = a; e2 = b; }
  int eval()
   { return (e1.eval()) * (e2.eval()); }  
}  // sum

public static class varexp extends expr  // variable expressions
{ // syntax will contain name of variable
  varexp(String s) { syntax = s; }
  int eval() { return 0; }    // dummy eval - don't use
}

public static class sigexp extends expr  // summation series
{ String var;
  expr body;    // e1 and e2 are the range expressions
  sigexp(String id, expr s1, expr s2, expr e) 
   { e1 = s1;  e2 = s2; var = id;  body = e; }
  int eval() { return 0; }    // dummy eval - don't use
  
}


/* compilation code */

static PrintStream out;   // output stream to file

static SymbolTable ST;    // global symbol table

public static class VirtualStack
{   
   int tos = 0;   // offset from original sp register
                  // tos < 0 indicates stack is in use
   int freereg = 0;   // indicates first free LOCAL register
	  	              // no register available when == 8;
   
   public String vpush(String sreg)  // push value in sreg onto virtual stack
     {  int reg = getRegister();
        if (reg < 8) // register available!
            return ("\n\t mov %" + sreg + ", %l" + reg 
		+ "\t ! virtual push"); 
        else
          { tos = tos - 4;      // record extent of stack usage
            String s, t;  // temp strings;
            s = "\n\t add %sp, -4, %sp";	// allocate stack space
	    t = "\n\t st %" + sreg + ", [%sp]\t! real push";
//	    t = "\n\t st %" + sreg + ", [%fp + " + tos + "]\t! real push";
            return t;
          }
     }  // vpush

   public String vpop()
     {  if (tos >= 0)   // stack not in use
	    { freeRegister();  return "\n\t\t\t ! virtual pop"; }
        else
	    { tos = tos + 4;
//   	      return "\n\t\t\t ! real pop";
              return "\n\t add %sp, 4, %sp\t ! reap pop";
            }
     } // vpop
   
   public String vpeek(String destreg) // get value into register destreg
     {  
	if (tos >= 0)   // stack not in use
	      return 
               ("\n\t mov %l" + (freereg-1) + ", %" + destreg
			+ "\t ! virtual peek"); 
        else
	    { 
              return 
	       ("\n\t ld [%fp + " + tos + "], %" + destreg + "\t ! real peek");
            }

     } // vpeek


   public int getRegister() 
     { if (freereg < 8) { freereg++; return (freereg-1);}
	  else return freereg;
     }
   public void freeRegister()
     { freereg--; }

} // end class VirtualStatck

public static class LabelServer  // fresh label server
{  int counter = 0;
   public String getlabel() 
    { counter++; return ("label" + (counter-1)); }
} // end class LabelServer


// static VirtualStack vstack;   // can't be global anymore
static LabelServer lbsv;      // global label server

public static void genlabels(expr E) throws IOException
 { if (E != null)
     if (E instanceof constexp)
      { constexp E1 = (constexp) E;	// type cast
        int val = (new Integer(E1.syntax)).intValue();
        if ((val > 4095) || (val < -4096))
          { E1.label = lbsv.getlabel();    // get a fresh label
            out.print("\n\t .align 4");  // assume 32-bit values
            out.print("\n" + E1.label + ":\t .word " + val);
          }
      }
      else { genlabels(E.e1);  genlabels(E.e2); }
 } // genlabels
  


// gencode will perform post-order traversal of the syntax tree
public static void gencode(expr E, VirtualStack vstack) throws IOException
 { if (E != null)
   {
     if (E instanceof constexp)  // constant expression (put in o1)
      { constexp E1 = (constexp) E;	// type cast
	int val = (new Integer(E1.syntax)).intValue();
        if ((val > 4095) || (val < -4096))	// large constant
         { out.print("\n\t sethi %hi(" + E1.label + "), %o1");
           out.print("\n\t or %o1, %lo(" + E1.label + "), %o1");
           out.print("\n\t ld [%o1], %o0");
         }
        else 					// small constant
          out.print("\n\t mov " + E1.syntax + ", %o0"); 
	out.print(vstack.vpush("o0"));  // move val in o0 and push
      }  // end constexp
     else if (E instanceof sumexp)
      { gencode(E.e2,vstack);
	gencode(E.e1,vstack);
        out.print(vstack.vpeek("o0"));  // load first operand into l0
        out.print(vstack.vpop());
        out.print(vstack.vpeek("o1"));  // second operand into l1
        out.print(vstack.vpop());
        out.print("\n\t add %o0, %o1, %o0");  // sum in o0
	out.print(vstack.vpush("o0"));
      } // end sumexp
     else if (E instanceof multexp)
      { gencode(E.e2,vstack);
	gencode(E.e1,vstack);
        out.print(vstack.vpeek("o0"));  // load first operand into o0
        out.print(vstack.vpop());
        out.print(vstack.vpeek("o1"));  // second operand into o1
        out.print(vstack.vpop());
        out.print("\n\t call .mul");  // product in o0 on return
        out.print("\n\t nop");        // pipeline delay slot
	out.print(vstack.vpush("o0"));    // push result on stack
      } // end multexp
     else if (E instanceof varexp) 
      { int offset = ST.lookup(E.syntax);
        if (offset == 0)   // no such variable, value defaults to 0
          out.print(vstack.vpush("g0"));
        else  // push value of variable onto stack
          { out.print("\n\t ld [%fp + " + offset + "], %o0");
            out.print(vstack.vpush("o0"));
          }
      }   // end varexp
     else if (E instanceof sigexp)
      { sigexp SE = (sigexp) E;   // type cast sooner the better

        ST.pushframe(0 - vstack.tos);   // create new frame
           // new scope entered;           (-vstack.tos = extra stack usage)

        ST.insert(SE.var, 4); // record negative offset of new var;

        // create an internal accumulator variable to hold value of sum
        String accumulator = lbsv.getlabel(); // make sure name don't conflict
        ST.insert(accumulator, 8);

	// replace virtual stack manager with a new one, temporarily:
        VirtualStack oldstack;
        oldstack = vstack;
        vstack =  new VirtualStack();  // new stack

        // register window shift  
        out.print("\n\t save %sp, -" + ST.FramesTOS.size + ", %sp\t ! SIG expression");

        // put 0 into accumulator:
        out.print("\n\t st %g0, [%fp-8]\t ! init accumulator");  

        // now put e1 into var:   // assignment operation
        gencode(SE.e1,vstack);
        out.print(vstack.vpeek("o0"));
        out.print(vstack.vpop());
        out.print("\n\t st %o0, [%fp + " + (- (4*1)) + "]\t ! save initial value");

        String startlabel = lbsv.getlabel();
        String endlabel   = lbsv.getlabel();

        // compare if var is larger than e2:
        out.print("\n" + startlabel + ":");   // start of loop
        gencode(SE.e2,vstack);     
        out.print(vstack.vpeek("o1"));
        out.print(vstack.vpop());
	out.print("\n\t ld [%fp - 4], %o0");  // loads var into o0
        out.print("\n\t cmp %o1, %o0");
        out.print("\n\t bl " + endlabel);  // terminates loop
        out.print("\n\t nop");

        // evaluate body and add it to accumulator:  (weird way?)
        gencode(new sumexp("", new varexp(accumulator),SE.body),vstack);
        out.print(vstack.vpeek("o0"));
        out.print(vstack.vpop());
        out.print("\n\t st %o0, [%fp - 8]");  // add to accumulator

        // incremement var; go back and do it again:
        out.print("\n\t ld [%fp - 4], %o0");  // increment SE.var
        out.print("\n\t add %o0, 1, %o0");
        out.print("\n\t st %o0, [%fp - 4]");
        out.print("\n\t ba " + startlabel);  // branch back
        out.print("\n\t nop");

        // loop terminated, put accumulator in i0 (to pass back)
        out.print("\n" + endlabel + ":");   // endlabel
        out.print("\n\t ld [%fp-8], %i0");

        vstack = oldstack;   // restore old virtual stack manager

        // shift back register window, push o0 (old i0) onto (old) stack
        out.print("\n\t restore");    // shift back window
        out.print("\n\t nop");        // don't know if needed, probably not
        out.print(vstack.vpush("o0"));      // result on original stack

	ST.popframe();		// pop frame from symbol table

      } // end sigexp
   }
 } // gencode


/*    main   */
public static void main(String[] args)
{
try {
  // get expr from parser
  // expr.eval(), and print it
  expr theexp;
  parser theparser = new parser();
  theexp = (expr) theparser.parse().value;
  System.out.println(theexp.eval());

/*  NOW FOR THE COMIPILED PART */

  // open file: 
  out = new java.io.PrintStream(new java.io.FileOutputStream(args[0]));
  out.print("\n! COMPILER VERSION: \n");

  VirtualStack vstack = new VirtualStack();   // new virtual stack manager
  lbsv = new LabelServer();	 // new label server
  ST = new SymbolTable();	 // global symbol table
  ST.pushframe(0);		 // global, initial frame

  out.print("\n\t .global main \n\t .align 4");
  out.print("\nstr0: \t .asciz \"Value = %d\\n\" ");

/*   GENERATE LABELS FOR LARGE CONSTANTS    */

  out.print("\n\t .data");   // data section
  genlabels(theexp);	 	    // make labels for large constants

  out.print("\n\t .align 4");
  out.print("\nmain:");		// main body of program
//   out.print("\n\t save %sp, -800, %sp");  // reserve some memory!

  gencode(theexp, vstack);   // print compiled version
  
  out.print(vstack.vpeek("o1"));   // print the final value
  out.print("\n\t sethi %hi(str0), %o0");
  out.print("\n\t or %o0, %lo(str0), %o0");
  out.print("\n\t call printf");
  out.print("\n\t nop");

  out.print("\n\t mov 1, %g1 \n\t ta 0");
  out.print("\n ! -- End of Code --\n");
  

  out.close();		// close output file

} catch (Exception ee) {System.err.println(ee.toString());}

}  // main


}


/* new symbol table classes */

class Frame
{ String id;     // will be ID for tiger
  String type;   // not used here
  int offset;	 // offset from current fp
  Frame tail;
  Frame(String i, int t, Frame n)
   { id=i; offset=t; tail=n; }
}

class StackFrame
{ Frame head;
  int size = 96;    // size in BYTES of current frame;
  StackFrame tail;
  StackFrame(Frame h, StackFrame t) { head=h; tail=t; }
}

class SymbolTable
{ StackFrame FramesTOS;
  
  public void pushframe(int stackUsage)
   { // record extra stack usage
     if (FramesTOS != null) FramesTOS.size = FramesTOS.size + stackUsage;  
     FramesTOS = new StackFrame(null,FramesTOS); // push null frame
   }

  public void popframe()
   { if (FramesTOS != null) FramesTOS = FramesTOS.tail; }

  public void insert(String id, int offset)
   { FramesTOS.head = 
       new Frame(id,offset,FramesTOS.head);  // treated as a stack
     FramesTOS.size = FramesTOS.size + 4;
//     FramesTOS.size = FramesTOS.size + (FramesTOS.size % 8); 
   }

  public int lookup(String id)  // returns offset of id from current fp
   { boolean found = false;
     int answer = 0;     // 0 indicates variable not in table
     StackFrame currentFrame = FramesTOS;
     Frame current;
     while ( (currentFrame != null) && !(found) )  // look through all frames
      { 
	current = currentFrame.head;
        while ((current != null) && !(found))      // look through one frame
         {
          if (current.id.equals(id))  // compare id's
		{ answer = answer - current.offset; // move up from fp;
	          found = true;
 		}
          current = current.tail;  // advance within frame
         } // end inner while

	// move down a whole frame!
	if (!(found)) answer = answer + currentFrame.size;  
        currentFrame = currentFrame.tail;  // advance entire frame

      } // end outer while

     return answer;
    } // end lookup

} // end class SymbolTable