/* 
                    Abstract Machine AM7C

AM7C is an abstract, register-memory computer.  There are at least four
general purpose registers, determined by am7c.regpool.length. In addition 
there are the following special registers:

am7c.bp   : points to base of stack
am7c.sp   : points to top of stack
am7c.rtp  : reserved to hold return value from functions
am7c.thisp : reserved to hold address of "this" object, also used to pass
             target object pointer to function calls.
am7c.reserverd : general purpose reserved register, cannot be assumed to
                 hold its value beyond local operation.  We can also call
		 this register the accumulator

There is also the following constant:
am7c.wordsize : size in bits of each word (default 32)

All of these values can be changed when generating actual code (see x86coder).

AM7C Operands:

immediate : integer or string constant (for label)
register  : can be an index into regpool, or a name as a string
memory : contains base register, index register, scale factor,
         and integer offset

AM7C Operations:

move src,dst
push src
pop dst
unpush   :  fictitious instruction to deallocate stack space
fcall    :  function call (atomic instruction - no operands)
freturn  :  function return
jump dst  : can be conditional or unconditional
            jump.cond is condition string ("e", "ne", "l",etc). null means jmp
label : string label representing static memory location
stackalloc : move stack pointer am7c.sp up or down
nop : no operation but consumes clock cycle
nothing :  better than null for ignoring during code generation
directive : special, for reserved use
aluop(opcode,src,dst) : dst will be changed unless opcode is "cmp", "<"
  or "==".  Destructive opcodes include at least "+", "-", "*", "&&", "||"
  and "!" (negation).

codeblock: ArrayList of operations.  This is what really distinguishes AM7C
  as an intermediate language.  Each codeblock also points to the abstract
  syntax structure that it belongs to.  It also has a String comment,
  and pointer to parent block.  In addition to the operations, there is
  a field called "result" which is an operand representing the result of
  the block.  For example, if the code block represents an expression 3+x,
  then the result will be the register or mem location that the result is
  stored in.  codeblock.finish is a convenient procedure that sets the 
  result and returns the codeblock.

  Most importantly, a codeblock can contain nested codeblocks.

===================================================================
The next stage of your assignment is to generate an AM7C codeblock for
a minijava program (start with one that one has main). If you choose
to not use nested codeblocks, then you will limit yourself to what kind
of optimization can be done later.  If you generate a flat codeblock, then
about the only kind of optimization that can be done will be "peephole"
optimization.  

****changed since original post:****

In order to use my x86 coder to generate a .s file, you need to create a
codeblock for the entire program.  Included in the overall codeblock there
must be a codeblock for the main function which starts with the label
for main.  This codeblock must have comment.equals("main") so my coder
will know to write ".globl main" to the file.  Please note that the 
codeblock for the entire program should not have comment "main", only
the block for the main function itself.

In addition, at some point in your program you need to construct an
ArrayList<String> of all the string constants found in your program,
so they can be written to the .rodata section.  This should be an
easy modification to your existing code: just add the string to a global
list each time you visit a string expression in the abstract syntax.
The string constants will have labels .STR0, .STR1, etc.  Thus it would
be helpful to insert an index into your abstract syntax structure for
string expressions to help generate the correct label for each string.
Now:

codeblock abscode = ...;  // code block for the entire program
ArrayList<String> strconsts = ...; // string constants in the program
x86coder realcoder = new x86coder("prefix",abscode,strconsts);
realcoder.visitall(); 

will generate prefix.s   Use gcc prefix.s to produce a.out or a.exe

You may have to change x86coder.java to suit your own system, however.
My file will work on 32bit linux (fedora).

Graduate students are required to implement a register-allocation algorithm
similar to the Sethi-Ullman algorithm.  Undergrads can use a stack-based
code generation scheme where all general purpose registers are only used 
locally, as I have explained in class.  


ADDITIONAL CODING HINTS.

You may find it convenient to modify your abstract syntax and symbol table
entries to contain new information that would be helpful during code 
generation.

When writing a visitor for am7c (see interface and skeleton below), sometimes
you will find the need to pass additional parameters to visit.  The way to
do is to simulate it.  Let's say you want to add another integer parameter
to visit.  Declare a new instance var in the visitor class:
int extra; // name of extra parameter
Object eaccept(am7c construct, int x)
{
  int save = extra;  extra = x;
  Object r = construct.accept(this);
  extra = save;
}
Assuming that the visitor returns Object.

Some of the extra parameters I had to use include indicating whether an
operand must be a register. Since AM7c uses two operands in ALU operations,
the destination (dst) operand will usually be modified.  So when you compile
the expression (x+y), be sure that x is not modified (not same as x=x+y),
so you must find a register to hold the tempory result of the addition, and
only assign it to memory when compiling an assignment statement.
*/

public abstract class am7c // superclass of all AM7C constructs
{
    // general purpose register pool
    public static String[] regpool = {"r0","r1","r2","r3"};  // can change
    public static int gsize = 4; // general purpose registers regpool[0:3].
    public static int wordsize=32; // size of registers (32 or 64);
    // special registers
    public static register sp = new register("sp"); // top of stack
    public static register bp = new register("bp"); // base of stack
    public static register thisp = new register("thisp"); // "this" object
    public static register rtp = new register("rtp"); // return val 
    public static register reserved = new register("reserved");

    boolean cancel = false; // can be used to ignore construct
    boolean fixed = false;  // can't be changed by optimization
    int line; // absolute line number in generated code
    public abstract <T> T accept(amvisitor<T> v);
}//am7c top abstract class

interface operand extends Comparable<operand>
{
     <T> T accept(amvisitor<T> av);
}
interface operation 
{
     <T> T accept(amvisitor<T> ov);
}

// immediate operands or constants
class immediate extends am7c implements operand
{
    int val; // ignored if label!=null
    String lab=null;
    public immediate(int v) {val=v; fixed=true;}
    public immediate(String s) {lab=s; fixed = true;}
    public <T> T accept(amvisitor<T> v) { return v.visit(this); }
    public boolean equals(Object x)
    {
	if (!(x instanceof immediate)) return false;
	immediate xi = (immediate)x;
	if (lab!=null) return lab.equals(xi.lab);
	else return val==xi.val;
    }
    public String toString() 
      { if (lab!=null) return "label:"+lab; else return "$"+val; }
    public int compareTo(operand x)
    { return toString().compareTo(x.toString()); }
}

class mem extends am7c implements operand   // memory address
{
    register base;
    register index=null;  // can be null
    int increment = 4;    // scale  mem addr = offset+(base +(increment*index))
    int offset = 0;
    public mem(register b, int f) {base=b; offset=f;}
    public mem(register b, register i, int f) {base=b; offset=f; index=i;}
    public mem(register b, int f, boolean x) {base=b; offset=f; fixed=x;}
    public mem(register b, register i, int f, boolean x) 
    {base=b; offset=f; index=i; fixed=x;}

    public static Hashtable<String,register> cache = 
	new Hashtable<String,register>();  // may be useful...
    public register regassigned() { return cache.get(this.toString()); }
    
    public String toString()  // for debugging, not coding
    {
	String bs = base.toString();
	String ins = "";
	if (index!=null) ins = index.toString();
	return offset+"("+bs+","+ins+","+increment+")";
    }
    public boolean equals(Object x)
    {
	if (x==null || !(x instanceof mem)) return false;
	mem mx = (mem)x;
	return ((base==null && mx.base==null) || base.equals(mx.base)) && 
	    ((index==null && mx.index==null) || index.equals(mx.index)) && (offset==mx.offset) && (increment==mx.increment);
    }
    public <T> T accept(amvisitor<T> v) { return v.visit(this); }
    public int compareTo(operand x)
    { return toString().compareTo(x.toString()); }
}//mem


class register extends am7c implements operand
{
    int ri = -1; // register index , -1 means register is special
    String special = null;  // null only if ri>=0
    boolean fixed = false; // can be changed by optimization?
    public register(int r) {ri=r;}
    public register(String s) {special=s;}
    public register clone() 
    { register r = new register(0); r.ri=ri; r.special=special; r.fixed=fixed;
	return r;
    }

    public static int freeregs = regpool.length;
    public static boolean[] used = new boolean[regpool.length]; // all false
    public static register findreg() // returns null if non available.
    {
	if (freeregs<1) return null;
	freeregs--;
	int r = 0;
	while (used[r]) r++;
	used[r] = true;
	//System.out.println("allocated register "+am7c.regpool[r]);
	return new register(r);
    }
    public static register findregexcept(operand re)
    {
	if (freeregs<1) return null;
	int ei = -1; // exception
	if (re instanceof register) 
	    { 
		ei = ((register)re).ri;
		if (ei>=0 && freeregs<2) return null;
	    }
	freeregs--;
	int r = 0;
	while (used[r] || r==ei) r++;
	used[r] = true;
	return new register(r);
    }
    public static void freeall() // return previously saved registers
    {
	for(int i=0;i<regpool.length;i++) 
	    { used[i]=false; }
	freeregs = regpool.length;
    }
    public static int restoreused(boolean[] B)
    {
	used = B;
	freeregs = 0;
	for(boolean b:B) if (!b) freeregs++;
	return freeregs;
    }

    public String toString()
    { if (special!=null) return special;
	else return regpool[ri]; 
    }

    public boolean equals(Object x)
    {
	if (!(x instanceof register) || x==null) return false;
	register rx = (register)x;
	//	return this.toString().equals(rx);
	if (ri>=0) return ri==rx.ri;
	if (special!=null) return special.equals(rx.special);
	throw new Error("weird register "+this.toString());
    }
    public int compareTo(operand x)
    { return toString().compareTo(x.toString()); }
    public <T> T accept(amvisitor<T> v) { return v.visit(this); }
}//register


//// operations ////
class label extends am7c implements operation
{
    String val;
    public static int lcx=0; // counter for generating new labels.
    public static label newlabel() 
    { lcx++; return new label("LAB"+lcx); }
    public static label newlabel(String s, boolean inc) 
    { if (inc) lcx++; return new label(s+lcx); }    
    public label(String v) {val=v;}
    public <T> T accept(amvisitor<T> v) { return v.visit(this); }
}


class fcall extends am7c implements operation
{
    label dst;
    operand operdst;
    public fcall(label d) {dst=d;}
    public fcall(operand d) {operdst=d;}
    public <T> T accept(amvisitor<T> v) { return v.visit(this); }
}

class freturn extends am7c implements operation  // return
{
    public <T> T accept(amvisitor<T> v) { return v.visit(this); }
}


// we shall allow mem-mem operations, 2 addr instead of 3 addr, since
// we can always generate 3 addr from 2 addr

// ALU operations 
class aluop extends am7c implements operation // generic superclass
{
    static String[] nondestructive = {"cmp","<","=="};
    String opcode; 
    operand src;  // source 2 (might not be used)
    operand dst;  // destination, also takes result
    boolean destructive = true; // changes dst
    public aluop(String p, operand a, operand c)
    {opcode=p; src=a; dst=c;  if (p.equals("cmp")) destructive=false; }
    public aluop(String p, operand c)
    {opcode=p; src=null; dst=c; if (p.equals("cmp")) destructive=false; }
    public <T> T accept(amvisitor<T> v) { return v.visit(this); }
}// alu


// for stack allocation:
class stackalloc extends am7c implements operation
{
    public static int unit = 16; // 16 bytes alignment
    public static int direction = -1; // stack grows upwards
    public static int align(int x)
    {
	int rem = x%unit;
	if (rem==0) return x; 
	else return x + (unit - rem);
    }
    int size; //number of **bytes** to allocate
    public stackalloc(int s) {size=s;}
    public <T> T accept(amvisitor<T> v) { return v.visit(this); }
}//stackalloc

class move extends am7c implements operation // could be mem-mem
{
    operand src;  // source 
    operand dst;  // destination
    public move(operand a, operand b) { src=a; dst=b; }
    public <T> T accept(amvisitor<T> v) { return v.visit(this); }
}

class push extends am7c implements operation
{
    operand src=null;  // null means push all registers
    public push(operand r) {src=r;}
    public push() {}// pushall
    public <T> T accept(amvisitor<T> v) { return v.visit(this); }
}

class pop extends am7c implements operation
{
    operand dst=null; // null means push all registers
    public pop(operand d) {dst=d;}
    public pop() {}
    public <T> T accept(amvisitor<T> v) { return v.visit(this); }
}

class jump extends am7c implements operation
{
    String cond;  // something like (==, !=, <, etc), null for unconditional
    operand operdst=null;  // jump destination could also be operand.
    label dst; 
    public jump(String c, operand s, label d) {cond=c; operdst=s; dst=d; }
    public jump(String c, label d) {cond=c; dst=d; }
    public jump(label d) {dst=d;}
    public <T> T accept(amvisitor<T> v) { return v.visit(this); }
}

class nop extends am7c implements operation 
{
    public <T> T accept(amvisitor<T> v) { return v.visit(this); }
}

class directive extends am7c implements operation // assembler directive
{
    String val;
    public directive(String v) {val=v;}
    public <T> T accept(amvisitor<T> v) { return v.visit(this); }
}

class unpush extends am7c implements operation
{
    public <T> T accept(amvisitor<T> v) { return v.visit(this); }
}

class nothing extends am7c implements operation // != nop
{
    public <T> T accept(amvisitor<T> v) { return v.visit(this); }
}

class codeblock extends am7c implements operation
{
    public ArrayList<operation> ops = new ArrayList<operation>();
    public operand result=null;
    //public construct absyn;  // may not be consistent with your own absyn
    public String comment=""; 
    public boolean pureblock = true; // no nested codeblocks
    public boolean usingreg = false; // using a non-reserved register
    public codeblock parent;  // parent block (might not be used)
    public codeblock(String s) {comment=s;} 
    public codeblock() {}

    public void add(operation x)
    { if (x==null) throw new Error("null op being added!");
      ops.add(x); if (x instanceof codeblock) pureblock=false; 
    }
    public void merge(codeblock cb)
    {
	if (cb==null || cb.ops.size()==0) return;
	ops.addAll(cb.ops);
	pureblock = pureblock && cb.pureblock;
	//	comment += ":"+cb.comment;
    }
    public codeblock finish(operand c) 
    {   result=c;  usingreg = usingregs(c);
	return this;
    }
    public boolean freereg() // return true if result register was freed
    {
	if (result==null || !(result instanceof register)) return false;
	register r= (register)result;
	if (r.ri>=0) 
	    {   register.used[r.ri]=false;
		register.freeregs++;
		usingreg = false;
		return true;
	    }
	else return false;
    }
    public <T> T accept(amvisitor<T> v) { return v.visit(this); }

    // utility
    boolean usingregs(operand c) // does operand use a register:
    {
	if (c instanceof register) return ((register)c).ri>=0;
	if (c instanceof mem) 
	    return usingregs(((mem)c).base) || usingregs(((mem)c).index);
        return false;
    }

    // flatten an arraylist to not contain nested codeblocks
    public static ArrayList<operation> flatten(ArrayList<operation> B)
    {
	ArrayList<operation> A = new ArrayList<operation>();
	for(operation op: B)
	    {
		if (op instanceof codeblock) 
		    {  
			if (((codeblock)op).pureblock)
			    A.addAll(((codeblock)op).ops);
			else 
			    A.addAll( flatten(((codeblock)op).ops) );
		    }
		else A.add(op);
	    }//for
	return A;
    }

}//codeblock

// superclass that traverses am7c constructs
interface amvisitor<T>
{
    T visit(immediate x);
    T visit(label x);
    T visit(mem x);
    T visit(register x);
    T visit(fcall x);
    T visit(freturn x);
    T visit(aluop x);
    T visit(stackalloc x);
    T visit(move x);
    T visit(push x);
    T visit(pop x);
    T visit(jump x);
    T visit(nop x);
    T visit(directive x);
    T visit(unpush x);
    T visit(nothing x);
    // for improved intermediate representation:
    T visit(codeblock x);
}

class amvbase<T> implements amvisitor<T>
{
    public T visit(immediate x) { return null; }
    public T visit(label x) { return null; }
    public T visit(mem x) { return null; }
    public T visit(register x) { return null; }
    public T visit(fcall x) {return null;}
    public T visit(freturn x) {return null;}
    public T visit(aluop x) {return null;}
    public T visit(stackalloc x) { return null; }
    public T visit(move x) { return null; }
    public T visit(push x) { return null; }
    public T visit(pop x) { return null; }
    public T visit(jump x) { return null; }
    public T visit(nop x) {return null;}
    public T visit(nothing x) {return null;}
    public T visit(directive x) {return null;}
    public T visit(unpush x) {return null;}
    public T visit(codeblock cb) {return null;}
}

// class codeblock defined externally.