CodeGenerator.java

import java.io.PrintStream;
import java.util.Date;

import absyn.*;
import symbol.FunctionNode;
import symbol.Log;
import symbol.NodeType;
import symbol.Scope;
import symbol.VariableNode;

public class CodeGenerator implements AbsynVisitor {

  // ----------------------
  public static final int
  // Registers
    PC = 7,
    GP = 6,
    FP = 5,
    AC = 0,
    AC1 = 1,
    AC2 = 2,
    AC3 = 3,
    AC4 = 4,
  // Constants
    NONE = 0,
    TRUE = 1,
    FALSE = 0,
  // Offsets
    OFP_FO = 0,
    RET_FO = -1,
    INIT_FO = -2;
  // ---------------------

  private int emitLoc = 0, highEmitLoc = 0;
  private int mainEntry, globalOffset = 0;

  private PrintStream out;
  private Scope scope;

  public CodeGenerator(PrintStream out, Scope scope, List<?> tree) {
    this.out = out;
    this.scope = scope;
    this.mainEntry = -1;

    prelude();

    visit(tree, 0, false);

    finale();
  }

  private void prelude() {
  comment("Created " + new Date());
    // Add prelude text
    comment("-> Prelude");
    emitRM("LD", GP, 0, AC, "load GP with maxaddress");
    emitRM("LDA", FP, 0, GP, "copy GP to FP");
    emitRM("ST", AC, 0, AC, "clear value at location 0");
    comment("<- Prelude");
    comment("-> I/O Functions");
    ((FunctionNode)scope.findVariable("output")).getDef().accept(this, 0, false);
    ((FunctionNode)scope.findVariable("input")).getDef().accept(this, 0, false);
    comment("<- I/O Functions");
  }

  private void finale() {
    comment("-> Finale");
    if (mainEntry == -1) {
      emitRO("HALT", NONE, NONE, NONE, "No main function. Stopping.");
    } else {
      emitRM("ST", FP, globalOffset, FP, "Push old frame pointer");
      emitRM("LDA", FP, globalOffset, FP, "Push frame");
      emitRM("LDA", AC, 1, PC, "Load AC with Ret Pointer");
      emitAbsRM("LDA", PC, mainEntry, "Start in main");
      emitRM("LD", FP, OFP_FO, FP, "Pop frame");
      emitRO("HALT", NONE, NONE, NONE, "Stop.");
    }
    comment("<- Finale");
  }

  /**
   * INS r,s,t
   * @param ins
   * @param r
   * @param s
   * @param t
   * @param note
   */
  private void emitRO(String ins, int r, int s, int t, String note) {
    out.printf("%d:        %s        %d,%d,%d        %s\n", emitLoc++, ins, r, s, t, note);
    if (emitLoc >= highEmitLoc) {
      highEmitLoc = emitLoc;
    }
  }

  /**
   * INS r,d(s)
   * a = d + reg[s]
   * @param ins
   * @param r the register to read/write to
   * @param d the offset
   * @param s
   * @param note
   */
  private void emitRM(String ins, int r, int d, int s, String note) {
    out.printf("%d:        %s        %d,%d(%d)        %s\n", emitLoc++, ins, r, d, s, note);
    if (emitLoc >= highEmitLoc) {
      highEmitLoc = emitLoc;
    }
  }

  private void emitAbsRM(String ins, int r, int a, String note) {
    out.printf("%d:        %s        %d,%d(%d)        %s\n", emitLoc, ins, r, a - (emitLoc + 1), PC, note);
    emitLoc++;
    if (emitLoc >= highEmitLoc) {
      highEmitLoc = emitLoc;
    }
  }

  private int emitSkip(int distance) {
    int i = emitLoc;
    emitLoc += distance;
    if(highEmitLoc < emitLoc) {
      highEmitLoc = emitLoc;
    }
    return i;
  }

  private void emitBackup(int loc) {
    if(loc > highEmitLoc) {
      comment("BUG in emitBackup");
    }
    emitLoc = loc;
  }

  private void emitRestore() {
    emitLoc = highEmitLoc;
  }

  private void comment(String text) {
    out.printf("* %s\n", text);
  }

  
  @Override
  public void visit(FunctionDec dec, int offset, boolean isAddr) {
    // if (dec.isPrototype()) {
    //   dec.setAddress(emitLoc);
    // }
    comment("-> function " + dec.getSignature());
    int saved = emitSkip(1);
    if (dec.isMain()) {
      mainEntry = emitLoc;
    }
    dec.setAddress(emitLoc);
    emitRM("ST", AC, RET_FO, FP, "store return for function " + dec.getName());

    int count = 0;
    for (VarDec param : dec.getParams()) {
      param.accept(this, offset - count + INIT_FO, false);
      count++;
    }

    dec.getBody().accept(this, offset - count + INIT_FO, false);
    emitRM("LD", PC, RET_FO, FP, "return to caller");
    int saved2 = emitSkip(0);
    emitBackup(saved);
    emitAbsRM("LDA", PC, saved2, "Jump around body");
    comment("<- function " + dec.getName());
    emitRestore();
  }

  @Override
  public void visit(ArrayDec dec, int offset, boolean isAddr) {
    NodeType node = scope.findByTemp(dec);
    dec.setOffset(offset);
    if (node.getLevel() == 0) { // is global
      comment("global array " + dec.getName() + " at offset " + offset);
      globalOffset -= (1 + dec.getSize());
    } else {
      comment("local array " + dec.getName() + " at offset " + offset);
    }
  }

  @Override
  public void visit(SimpleDec dec, int offset, boolean isAddr) {
    NodeType node = scope.findByTemp(dec);
    dec.setOffset(offset);
    if (node.getLevel() == 0) { // is global
      comment("global variable " + dec.getName() + " at offset " + offset);
      globalOffset -= 1;
    } else {
      comment("local variable " + dec.getName() + " at offset " + offset);
    }
  }

  @Override
  public void visit(AssignExp exp, int offset, boolean isAddr) {
    exp.getLeft().accept(this, offset - 1, true);
    Var var = exp.getLeft().getVariable();
    
    NodeType node = (VariableNode)scope.findByTemp(var.getTemp());
    int P = node.getLevel() == 0 ? GP : FP;
    exp.getRight().accept(this, offset - 2, isAddr);
    emitRM("ST", AC, ((VarDec)node.getDef()).getOffset(), P, "Set variable " + node.getName());
    emitRM("LD", AC, offset, FP, "Load assignment value in AC");
  }

  @Override
  public void visit(BoolExp exp, int offset, boolean isAddr) {
    emitRM("LDC", AC, (exp.getValue() ? TRUE : FALSE), NONE, "Load constant " + exp.getValue());
    emitRM("ST", AC, offset, FP, "Store constant " + exp.getValue());
  }

  @Override
  public void visit(CallExp exp, int offset, boolean isAddr) {
    comment("-> Call " + exp.getFunction());
    int count = 0;
    for (Exp arg : exp.getArgs()) {
      arg.accept(this, offset - count + INIT_FO, isAddr);
      String note = String.format("Load arg #%d for \"%s\" [: %s]", count, exp.getFunction(), arg.toString());
      emitRM("ST", AC, offset - count + INIT_FO, FP, note);
      ++count;
    }

    NodeType node = scope.findVariable(exp.getFunction());

    emitRM("ST", FP, offset, FP, "Push OFP");
    emitRM("LDA", FP, offset, FP, "Push frame");
    emitRM("LDA", AC, 1, PC, "Load AC with Return Pointer");
    emitAbsRM("LDA", PC, ((FunctionDec)node.getDef()).getAddress(), "jump to location of " + exp.getFunction());
    emitRM("LD", FP, OFP_FO, FP, "Pop frame");
    if (node.getType() != CMType.VOID) {
      emitRM("ST", AC, offset, FP, "Store return value of " + exp.getFunction());
    }
    comment("<- Call " + exp.getFunction());
  }

  @Override
  public void visit(CompoundExp exp, int offset, boolean isAddr) {
    comment("-> compound expression");
    int count = 0;
    for (VarDec dec : exp.getDecs()) {
      dec.accept(this, offset - count, isAddr);
      if (dec.isArray()) {
        int size = ((ArrayDec)dec).getSize();
        count += size;
      } else {
        ++count;
      }
    }
    for (Exp e : exp.getExps()) {
      e.accept(this, offset - (count++), isAddr);
    }
    comment("<- compound expression");
  }

  @Override
  public void visit(IfExp exp, int offset, boolean isAddr) {
    Exp cond = exp.getCondition();
    comment("-> IF (" + cond + ")");
    cond.accept(this, offset, isAddr);

    // Store the space to put the condition
    int condLoc = emitSkip(1);

    // write instructions for "then"
    comment("-> THEN");
    exp.getThen().accept(this, offset - 1, false);
    comment("<- THEN");

    // store a spot for an unconditional jump after "then" (prevents from moving into "else")
    int endJumpLoc = emitSkip(1);

    // store the next spot as the starting location for "else"
    int elseStartLoc = emitSkip(0);
    
    // go back to the spot for the condition
    emitBackup(condLoc);

    // write condition to jump to the start of "else"
    emitAbsRM("JEQ", AC, elseStartLoc, "Jump to else");

    emitRestore(); // continue onto "else"

    Exp elseBlock = exp.getElseBlock();
    if (!(elseBlock instanceof NilExp)) {
      // Write instructions for "else"
      comment("-> ELSE");
      elseBlock.accept(this, offset - 1, false);
      comment("<- ELSE");
    }
    // store the last instruction location of "else"
    int endOfElse = emitSkip(0);
    // go back to the location to write the unconditional jump.
    emitBackup(endJumpLoc);
    // make the unconditonal jump to jump over "else"
    emitAbsRM("LDA", PC, endOfElse, "Jump to end.");
    emitRestore(); // continue onto other instructions
    comment("<- IF");
  }

  @Override
  public void visit(WhileExp exp, int offset, boolean isAddr) {
    Exp cond = exp.getCondition();

    // Store starting address of while loop
    int start = emitSkip(0);
    
    comment("-> WHILE (" + cond + ")");
    cond.accept(this, offset, false);

    // Leave 1 space to put the jump location
    int condLoc = emitSkip(1);

    // Write body of while loop
    exp.getBody().accept(this, offset - 1, false);
    
    // Jump back to start of while loop
    emitAbsRM("LDA", PC, start, "Jump back to start of loop");

    // Store last address of while loop
    int end = emitSkip(0);

    // Write jump condition
    emitBackup(condLoc);
    emitAbsRM("JEQ", AC, end, "Break out of loop");

    // Continue onward
    emitRestore();
    comment("<- WHILE");
  }

  @Override
  public void visit(IntExp exp, int offset, boolean isAddr) {
    emitRM("LDC", AC, exp.getValue(), NONE, "Load constant " + exp.getValue());
    emitRM("ST", AC, offset, FP, "Store constant " + exp.getValue());
  }

  @Override
  public void visit(OpExp exp, int offset, boolean isAddr) {
    Exp left = exp.getLeft();
    left.accept(this, offset - 1, isAddr);
    

    if (exp.isUnary()) {
      emitRM("LD", AC, offset - 1, FP, "Load left into AC");
      if (exp.getOp() == OpExp.UMINUS) {
        emitRM("LDC", AC1, -1, NONE, "Load negative one");
        emitRO("MUL", AC, AC1, AC, "Negate number in AC");
      } else if (exp.getOp() == OpExp.NOT) {
        emitRM("JEQ", AC, 2, PC, "Jump to the proper condition");
        emitRM("LDC", AC, FALSE, NONE, "Swap \"1\" to 0");
        emitRM("LDA", PC, 1, PC, "Jump over true below");
        emitRM("LDC", AC, TRUE, NONE, "Swap 0 to 1");
      }

    } else if (exp.isLogical()) { // "||" "&&"
      emitRM("LD", AC, offset - 1, FP, "Load left into AC");
      int saved = emitSkip(1);
      comment("-> Right side of " + exp.opToString());
      exp.getRight().accept(this, offset - 2, isAddr);
      emitRM("LD", AC, offset - 2, FP, "Load right side of \"" + exp.opToString() + "\" into AC");
      comment("<- Right side of " + exp.opToString());
      int shortCircutLoc = emitSkip(0);

      emitBackup(saved);
      if (exp.getOp() == OpExp.AND) {
        emitAbsRM("JEQ", AC, shortCircutLoc, "Evaluate left side of &&");
      } else { // is OR
        emitAbsRM("JNE", AC, shortCircutLoc, "Evaluate left side of ||");
      }
      emitRestore();
    } else { // Handle all other binary operators
      Exp right = exp.getRight();
      right.accept(this, offset - 2, isAddr);
      emitRM("LD", AC1, offset - 1, FP, "Load left into AC1");
      emitRM("LD", AC, offset - 2, FP, "Load right into AC");
      if (exp.isArithetic()) {
        switch (exp.getOp()) {
          case OpExp.PLUS:
            emitRO("ADD", AC, AC1, AC, "operator +");
            break;
          case OpExp.MINUS:
            emitRO("SUB", AC, AC1, AC, "operator -");
            break;
          case OpExp.MUL:
            emitRO("MUL", AC, AC1, AC, "operator *");
            break;
          case OpExp.DIV:
            emitRO("DIV", AC, AC1, AC, "operator /");
            break;
        }
      } else if (exp.isComparison()) {
        emitRO("SUB", AC, AC1, AC, "initial sub for comparison");
        String ins = "";
        switch (exp.getOp()) {
          case OpExp.EQ:
            ins = "JEQ";
            break;
          case OpExp.NE:
            ins = "JNE";
            break;
          case OpExp.GT:
            ins = "JGT";
            break;
          case OpExp.GE:
            ins = "JGE";
            break;
          case OpExp.LT:
            ins = "JLT";
            break;
          case OpExp.LE:
            ins = "JLE";
            break;
        }
        emitRO(ins, AC, 2, PC, "jump 2 if true");
        emitRM("LDC", AC, FALSE, NONE, "Condition was false");
        emitRM("LDA", PC, 1, PC, "Jump over true below");
        emitRM("LDC", AC, TRUE, NONE, "Condition was true");
      }
    }

    emitRM("ST", AC, offset, FP, "Store outcome of \"" + exp + "\"");
  }

  @Override
  public void visit(VarExp exp, int offset, boolean isAddr) {
    exp.getVariable().accept(this, offset, isAddr);
  }

  @Override
  public void visit(ReturnExp exp, int offset, boolean isAddr) {
    comment("-> return statement");
    exp.getValue().accept(this, offset - 1, false);
    emitRM("LD", PC, RET_FO, FP, "Return to caller");
    comment("<- return statement");
  }

  @Override
  public void visit(NilExp exp, int offset, boolean isAddr) {
    // Don't do anything here
  }

  @Override
  public void visit(SynError err, int offset, boolean isAddr) {
    // If we somehow made it through with a syntax error then crash the program
    Log.critical(err.getRow(), err.getCol(), "Error when attempting to asseble code", err.getMessage());
    System.exit(1);
  }

  @Override
  public void visit(SimpleVar var, int offset, boolean isAddr) {
    NodeType node = scope.findByTemp(var.getTemp());
    int P = (node.getLevel() == 0) ? GP : FP; // Either global or frame pointer
    String ins = isAddr ? "LDA" : "LD";
    emitRM(ins, AC, ((VarDec)node.getDef()).getOffset(), P, "Load \"" + var.getName() + "\" into register");
    emitRM("ST", AC, offset, P, "Store value of \"" + var.getName() + "\" in offset");
  }

  @Override
  public void visit(IndexVar var, int offset, boolean isAddr) {
    var.getIndex().accept(this, offset - 1, isAddr);
    NodeType node = scope.findByTemp(var.getTemp());
    comment("Was unable to fully implement indexed variables :/");
  }

  @Override
  public void visit(NativeExp exp, int offset, boolean isAddr) {
    // Quick way to write the input and output of the function
    if (exp.getFunctionName().equals("output")) {
      emitRM("LD", AC, INIT_FO, FP, "Load single param into AC");
      emitRO("OUT", AC, NONE, NONE, "output AC to console");
    } else if (exp.getFunctionName().equals("input")) {
      emitRO("IN", AC, NONE, NONE, "Store input in AC");
    }
  }
}