int sub(int n; int a[]) {
  int remain; remain = 1;
  while(remain) {
    remain = 0; int i; i = 1;
    while(i < n) {
      if(a[i-1]>a[i]) { int z; z=a[i-1]; a[i-1]=a[i]; a[i]=z; remain=1; }
      i = i + 1; } } }

Package samc1;

Helpers
  digit = ['0'..'9'] ;
  lcase = ['a'..'z'] ;
  ucase = ['A'..'Z'] ;
  letter = lcase | ucase ;

Tokens
  iconst = digit+ ;
  blank = (' '|13|10)+ ;
  int = 'int' ;
  if = 'if' ;
  while = 'while' ;
  semi = ';' ;
  assign = '=' ;
  add = '+' ;
  sub = '-' ;
  aster = '*' ;
  slash = '/' ;
  lt = '<' ;
  gt = '>' ;
  lbra = '{' ;
  rbra = '}' ;
  lpar = '(' ;
  rpar = ')' ;
  lsbr = '[' ;
  rsbr = ']' ;
  ident = letter (letter|digit)* ;

Ignored Tokens
  blank;

Productions
  prog = {main} int ident lpar dcls rpar stat
       ;
  dcls = {lst} dcls semi dcl
       | {one} dcl
       ;
  dcl  = {idcl} int ident
       | {adcl} int ident lsbr rsbr
       ;
  stlist = {stat} stlist stat
         | {empty}
         ;
  stat = {idcl}    int ident semi
       | {assign}  ident assign expr semi
       | {aassign} ident lsbr [idx]:expr rsbr assign expr semi
       | {if}      if lpar expr rpar stat
       | {while}   while lpar expr rpar stat
       | {block}   lbra stlist rbra
       ;
  expr = {gt}  [left]:nexp gt [right]:nexp
       | {lt}  [left]:nexp lt [right]:nexp
       | {one} nexp
       ;
  nexp = {add}  nexp add term
       | {sub}  nexp sub term
       | {one}  term
       ;
  term = {mul}  term aster fact
       | {div}  term slash fact
       | {one}  fact
       ;
  fact = {iconst} iconst
       | {ident}  ident
       | {aref}   ident lsbr expr rsbr
       | {one}    lpar expr rpar
       ;

package samc1;
import java.util.*;

public class IntCode {
  List<Block> code = new ArrayList<Block>();
  Block cb;
  int lblno = 1000;
  public IntCode() {
    cb = new Block("L1000", code.size()); code.add(cb);
  }
  public List<Block> getBlocks() { return code; }
  public void gLabel(int l) {
    if(cb.getTmp() && cb.getSize()==0) { cb.setLabel("L"+l); }
    else { cb = new Block("L"+l, code.size()); code.add(cb); }
  }
  public void gMovereg(int t1, String r) { cb.add(new Movereg(t1, r)); }
  public void gMoveint(int t1, int v) { cb.add(new Moveint(t1, v)); }
  public void gMove(int t1, int t2) { cb.add(new Move(t1, t2)); }
  public void gAdef(int t1, int t2, int t3) { cb.add(new Adef(t1, t2, t3)); }
  public void gAref(int t1, int t2, int t3) { cb.add(new Aref(t1, t2, t3)); }
  public void gAdd(int t1, int t2, int t3) { cb.add(new Add(t1, t2, t3)); }
  public void gSub(int t1, int t2, int t3) { cb.add(new Sub(t1, t2, t3)); }
  public void gMul(int t1, int t2, int t3) { cb.add(new Mul(t1, t2, t3)); }
  public void gDiv(int t1, int t2, int t3) { cb.add(new Div(t1, t2, t3)); }
  public void gJump(int l) { cb.add(new Jump(l)); eb(); }
  public void gIfz(int t1, int l) { cb.add(new Ifz(t1, l)); eb(); }
  public void gIfnz(int t1, int l) { cb.add(new Ifnz(t1, l)); eb(); }
  public void gIfne(int t1, int t2, int l) { cb.add(new Ifne(t1,t2,l)); eb(); }
  public void gIfeq(int t1, int t2, int l) { cb.add(new Ifeq(t1,t2,l)); eb(); }
  public void gIfgt(int t1, int t2, int l) { cb.add(new Ifgt(t1,t2,l)); eb(); }
  public void gIflt(int t1, int t2, int l) { cb.add(new Iflt(t1,t2,l)); eb(); }
  public void gIfge(int t1, int t2, int l) { cb.add(new Ifge(t1,t2,l)); eb(); }
  public void gIfle(int t1, int t2, int l) { cb.add(new Ifle(t1,t2,l)); eb(); }
  private void eb() { gLabel(++lblno); cb.setTmp(true); }
  public void show() { for(Block b: code) { b.show(); } }
  public void calcconnect() {
    Map<String,Block> map = new HashMap<String,Block>();
    for(Block b: code) { map.put(b.getLabel(), b); }
    for(int i = 0; i < code.size(); ++i) {
      Block b1 = code.get(i);
      for(int j: b1.getJdsts()) {
        if(j < 0 && i < code.size()-1) { b1.connect(code.get(i+1)); }
        if(j >= 0) { b1.connect(map.get("L"+j)); }
      }
    }
  }
  public void showconnect() { for(Block b: code) { b.showconnect(); } }
  public static class Block {
    String label;
    List<Inst> body = new ArrayList<Inst>();
    Set<Integer> prev = new TreeSet<Integer>();
    Set<Integer> succ = new TreeSet<Integer>();
    Set<Integer> ref = null;
    Set<Integer> def = null;
    int bid = 0;
    boolean tmp = false;
    public Block(String l, int i) { label = l; bid = i; }
    public int getId() { return bid; }
    public String getLabel() { return label; }
    public void setLabel(String lbl) { label = lbl; }
    public boolean getTmp() { return tmp; }
    public void setTmp(boolean t) { tmp = t; }
    public int getSize() { return body.size(); }
    public void add(Inst i) { body.add(i); }
    public List<Inst> getBody() { return body; }
    public Set<Integer> getPrev() { return prev; }
    public Set<Integer> getSucc() { return succ; }
    public Set<Integer> getRef() { if(ref==null) { calcDR(); } return ref; }
    public Set<Integer> getDef() { if(def==null) { calcDR(); } return def; }
    private void calcDR() {
      def = new TreeSet<Integer>(); ref = new TreeSet<Integer>();
      for(Inst op: body) {
        for(Integer i: op.getRefs()) { if(!def.contains(i)) { ref.add(i); }}
        for(Integer i: op.getDefs()) { def.add(i); }
      }
    }
    public void connect(Block b1) { succ.add(b1.getId()); b1.prev.add(bid); }
    public int[] getJdsts() {
      if(body.size() == 0) { return new int[]{ -1 }; }
      Inst last = body.get(body.size()-1);
      int dst = last.getJdst();
      if(last instanceof Jump || dst < 0) { return new int[]{ dst }; }
      return new int[]{ dst, -1 };
    }
    public void show() {
      System.out.println(label + ": // B" + bid);
      for(Inst i: body) { System.out.println("  "+i); }
    }
    public void showconnect() {
      System.out.print("B" + bid);
      System.out.print(" prev(");
      for(int i: prev) { System.out.printf(" B%d", i); }
      System.out.print(" ) succ(");
      for(int i: succ) { System.out.printf(" B%d", i); }
      System.out.println(" )");
    }
  }
  public static class Inst {
    int[] defs = {};
    int[] refs = {};
    String s;
    int jdst = -1, val;
    protected void sd(int... a) { defs = a; }
    protected void sr(int... a) { refs = a; }
    public int[] getDefs() { return defs; }
    public int[] getRefs() { return refs; }
    public int getJdst() { return jdst; }
    public String toString() { return s; }
    public int assDest() { return -1; }
    public int refNum() { return 0; }
    public String refExp() { return null; }
    public String refExp(String v1) { return null; }
    public String refExp(String v1, String v2) { return null; }
    public Inst renew() { return this; }
    public Inst renew(int t1) { return this; }
    public Inst renew(int t1, int t2) { return this; }
  }
  static class Movereg extends Inst {
    public Movereg(int t1, String reg) {
      s = String.format("t%d = %s", t1, reg); sd(t1);
    }
  }
  static class Move extends Inst {
    public Move(int t1, int t2) {
      s = String.format("t%d = t%d", t1, t2); sd(t1); sr(t2);
    }
    public int assDest() { return defs[0]; }
    public int refNum() { return 1; }
    public String refExp(String v1) { return v1; }
  }
  static class Moveint extends Inst {
    public Moveint(int t1, int v) {
      val = v; s = String.format("t%d = %d", t1, val); sd(t1);
    }
    public int assDest() { return defs[0]; }
    public int refNum() { return 0; }
    public String refExp() { return val+""; }
  }
  static class Adef extends Inst {
    public Adef(int t1, int t2, int t3) {
      s = String.format("t%d[t%d] = t%d", t1, t2, t3); sd(t1); sr(t2, t3);
    }
    public int refNum() { return 2; }
    public Inst renew(int t1, int t2) { return new Adef(defs[0], t1, t2); }
  }
  static class Aref extends Inst {
    public Aref(int t1, int t2, int t3) {
      s = String.format("t%d = t%d[t%d]", t1, t2, t3); sd(t1); sr(t2, t3);
    }
    public int assDest() { return defs[0]; }
    public int refNum() { return 2; }
    public String refExp(String v1, String v2) { return v1+"["+v2+"]"; }
    public Inst renew(int t1, int t2) { return new Aref(defs[0], t1, t2); }
  }
  static class Add extends Inst {
    public Add(int t1, int t2, int t3) {
      s = String.format("t%d = t%d + t%d", t1, t2, t3); sd(t1); sr(t2, t3);
    }
    public int assDest() { return defs[0]; }
    public int refNum() { return 2; }
    public String refExp(String v1, String v2) { return v1+"+"+v2; }
    public Inst renew(int t1, int t2) { return new Add(defs[0], t1, t2); }
  }
  static class Sub extends Inst {
    public Sub(int t1, int t2, int t3) {
      s = String.format("t%d = t%d - t%d", t1, t2, t3); sd(t1); sr(t2, t3);
    }
    public int assDest() { return defs[0]; }
    public int refNum() { return 2; }
    public String refExp(String v1, String v2) { return v1+"-"+v2; }
    public Inst renew(int t1, int t2) { return new Sub(defs[0], t1, t2); }
  }
  static class Mul extends Inst {
    public Mul(int t1, int t2, int t3) {
      s = String.format("t%d = t%d * t%d", t1, t2, t3); sd(t1); sr(t2, t3);
    }
    public int assDest() { return defs[0]; }
    public int refNum() { return 2; }
    public String refExp(String v1, String v2) { return v1+"*"+v2; }
    public Inst renew(int t1, int t2) { return new Mul(defs[0], t1, t2); }
  }
  static class Div extends Inst {
    public Div(int t1, int t2, int t3) {
      s = String.format("t%d = t%d / t%d", t1, t2, t3); sd(t1); sr(t2, t3);
    }
    public int assDest() { return defs[0]; }
    public int refNum() { return 2; }
    public String refExp(String v1, String v2) { return v1+"/"+v2; }
    public Inst renew(int t1, int t2) { return new Div(defs[0], t1, t2); }
  }
  static class Jump extends Inst {
    public Jump(int lbl) {
      s = String.format("jmp L%d", lbl); jdst = lbl;
    }
  }
  static class Ifz extends Inst {
    public Ifz(int t1, int lbl) {
      s = String.format("ifz t%d then L%d", t1, lbl); sr(t1); jdst = lbl;
    }
    public int refNum() { return 1; }
    public Inst renew(int t1) { return new Ifz(t1, jdst); }
  }
  static class Ifnz extends Inst {
    public Ifnz(int t1, int lbl) {
      s = String.format("ifnz t%d then L%d", t1, lbl); sr(t1); jdst = lbl;
    }
    public int refNum() { return 1; }
    public Inst renew(int t1) { return new Ifnz(t1, jdst); }
  }
  static class Ifeq extends Inst {
    public Ifeq(int t1, int t2, int lbl) {
      s = String.format("if t%d == t%d then L%d", t1, t2, lbl); sr(t1, t2);
     jdst = lbl;
    }
    public int refNum() { return 2; }
    public Inst renew(int t1, int t2) { return new Ifeq(t1, t2, jdst); }
  }
  static class Ifne extends Inst {
    public Ifne(int t1, int t2, int lbl) {
      s = String.format("if t%d != t%d then L%d", t1, t2, lbl); sr(t1, t2);
     jdst = lbl;
    }
    public int refNum() { return 2; }
    public Inst renew(int t1, int t2) { return new Ifne(t1, t2, jdst); }
  }
  static class Ifgt extends Inst {
    public Ifgt(int t1, int t2, int lbl) {
      s = String.format("if t%d > t%d then L%d", t1, t2, lbl); sr(t1, t2);
     jdst = lbl;
    }
    public int refNum() { return 2; }
    public Inst renew(int t1, int t2) { return new Ifgt(t1, t2, jdst); }
  }
  static class Iflt extends Inst {
    public Iflt(int t1, int t2, int lbl) {
      s = String.format("if t%d < t%d then L%d", t1, t2, lbl); sr(t1, t2);
     jdst = lbl;
    }
    public int refNum() { return 2; }
    public Inst renew(int t1, int t2) { return new Iflt(t1, t2, jdst); }
  }
  static class Ifge extends Inst {
    public Ifge(int t1, int t2, int lbl) {
      s = String.format("if t%d >= t%d then L%d", t1, t2, lbl); sr(t1, t2);
     jdst = lbl;
    }
    public int refNum() { return 2; }
    public Inst renew(int t1, int t2) { return new Ifge(t1, t2, jdst); }
  }
  static class Ifle extends Inst {
    public Ifle(int t1, int t2, int lbl) {
      s = String.format("if t%d <= t%d then L%d", t1, t2, lbl); sr(t1, t2);
     jdst = lbl;
    }
    public int refNum() { return 2; }
    public Inst renew(int t1, int t2) { return new Ifle(t1, t2, jdst); }
  }
}

package samc1;
import samc1.analysis.*;
import samc1.node.*;
import java.io.*;
import java.util.*;

class GenIntcode extends DepthFirstAdapter {
  HashMap<Node,Integer> pos;
  Symtab st;
  IntCode ic;
  int pcnt = 0, lcnt = 0;
  static String preg[] = {"%rdi", "%rsi", "%rdx", "%rcx", "%r8", "%r9"};
  private int ti(Object o) { return (Integer)o; }
  public GenIntcode(Symtab s, HashMap<Node,Integer> p, IntCode i) {
    st = s; pos = p; ic = i;
  }
  @Override
  public void outAIdclDcl(AIdclDcl node) {
    ic.gMovereg(pos.get(node), preg[pcnt++]);
  }
  @Override
  public void outAAdclDcl(AAdclDcl node) {
    ic.gMovereg(pos.get(node), preg[pcnt++]);
  }
  @Override
  public void outAAssignStat(AAssignStat node) {
    ic.gMove(pos.get(node), ti(getOut(node.getExpr())));
  }
  @Override
  public void outAAassignStat(AAassignStat node) {
    ic.gAdef(pos.get(node), ti(getOut(node.getIdx())), ti(getOut(node.getExpr())));
  }
  @Override
  public void caseAIfStat(AIfStat node) {
    int lbl = lcnt; lcnt += 1;
    node.getExpr().apply(this);
    ic.gIfnz(ti(getOut(node.getExpr())), lbl);
    node.getStat().apply(this);
    ic.gLabel(lbl);
  }
  @Override
  public void caseAWhileStat(AWhileStat node) {
    int lbl = lcnt; lcnt += 2;
    ic.gLabel(lbl);
    node.getExpr().apply(this);
    ic.gIfz(ti(getOut(node.getExpr())), lbl+1);
    node.getStat().apply(this);
    ic.gJump(lbl);
    ic.gLabel(lbl+1);
  }
  @Override
  public void outAGtExpr(AGtExpr node) {
    Symtab.Ent f = st.addDef(".t" + pcnt++, Symtab.ITYPE);
    ic.gIfgt(ti(getOut(node.getLeft())), ti(getOut(node.getRight())), lcnt);
    ic.gMoveint(f.pos, 0);
    ic.gJump(lcnt+1);
    ic.gLabel(lcnt++);
    ic.gMoveint(f.pos, 1);
    ic.gLabel(lcnt++);
    setOut(node, new Integer(f.pos));
  }
  @Override
  public void outALtExpr(ALtExpr node) {
    Symtab.Ent f = st.addDef(".t" + pcnt++, Symtab.ITYPE);
    ic.gIflt(ti(getOut(node.getLeft())), ti(getOut(node.getRight())), lcnt);
    ic.gMoveint(f.pos, 0);
    ic.gJump(lcnt+1);
    ic.gLabel(lcnt++);
    ic.gMoveint(f.pos, 1);
    ic.gLabel(lcnt++);
    setOut(node, new Integer(f.pos));
  }
  @Override
  public void outAOneExpr(AOneExpr node) { setOut(node, getOut(node.getNexp())); }
  @Override
  public void outAAddNexp(AAddNexp node) {
    Symtab.Ent f = st.addDef(".t" + pcnt++, Symtab.ITYPE);
    ic.gAdd(f.pos, ti(getOut(node.getNexp())), ti(getOut(node.getTerm())));
    setOut(node, new Integer(f.pos));
  }
  @Override
  public void outASubNexp(ASubNexp node) {
    Symtab.Ent f = st.addDef(".t" + pcnt++, Symtab.ITYPE);
    ic.gSub(f.pos, ti(getOut(node.getNexp())), ti(getOut(node.getTerm())));
    setOut(node, new Integer(f.pos));
  }
  @Override
  public void outAOneNexp(AOneNexp node) { setOut(node, getOut(node.getTerm())); }
  @Override
  public void outAMulTerm(AMulTerm node) {
    Symtab.Ent f = st.addDef(".t" + pcnt++, Symtab.ITYPE);
    ic.gMul(f.pos, ti(getOut(node.getTerm())), ti(getOut(node.getFact())));
    setOut(node, new Integer(f.pos));
  }
  @Override
  public void outADivTerm(ADivTerm node) {
    Symtab.Ent f = st.addDef(".t" + pcnt++, Symtab.ITYPE);
    ic.gDiv(f.pos, ti(getOut(node.getTerm())), ti(getOut(node.getFact())));
    setOut(node, new Integer(f.pos));
  }
  @Override
  public void outAOneTerm(AOneTerm node) { setOut(node, getOut(node.getFact())); }
  @Override
  public void outAIconstFact(AIconstFact node) {
    Symtab.Ent e = st.addDef(".t" + pcnt++, Symtab.ITYPE);
    ic.gMoveint(e.pos, new Integer(node.getIconst().getText()));
    setOut(node, new Integer(e.pos));
  }
  @Override
  public void outAIdentFact(AIdentFact node) {
    setOut(node, new Integer(pos.get(node)));
  }
  @Override
  public void outAArefFact(AArefFact node) {
    Symtab.Ent f = st.addDef(".t" + pcnt++, Symtab.ITYPE);
    ic.gAref(f.pos, pos.get(node), ti(getOut(node.getExpr())));
    setOut(node, new Integer(f.pos));
  }
  @Override
  public void outAOneFact(AOneFact node) { setOut(node, getOut(node.getExpr())); }
}

package samc1;
import samc1.parser.*;
import samc1.lexer.*;
import samc1.node.*;
import java.io.*;
import java.util.*;

public class SamC1 {
  public static void main(String[] args) throws Exception {
    if(args.length == 0) { showoptions(); return; }
    Parser p = new Parser(new Lexer(new PushbackReader(
      new InputStreamReader(new FileInputStream(args[0]), "JISAutoDetect"),
        1024)));
    Start tree = p.parse();
    Symtab st = new Symtab();
    HashMap<Node,Integer> vtbl = new HashMap<Node,Integer>();
    TypeChecker tck = new TypeChecker(st, vtbl); tree.apply(tck);
    if(Log.getError() > 0) { return; }
    IntCode ic = new IntCode();
    GenIntcode gen = new GenIntcode(st, vtbl, ic); tree.apply(gen);
    ic.calcconnect();
//    Dataflow df = new Dataflow(ic.getBlocks());
    for(int i = 1; i < args.length; ++i) {
      if(args[i].equals("pt")) { st.show(); }
      else if(args[i].equals("pi")) { ic.show(); }
      else if(args[i].equals("pc")) { ic.showconnect(); }
//      else if(args[i].equals("vn")) { ValNumber.run(ic, false); }
//      else if(args[i].equals("pvn")) { ValNumber.run(ic, true); }
//      else if(args[i].equals("clio")) { df.calcLiveInOut(); }
//      else if(args[i].equals("plio")) { df.showLiveInOut(); }
      else { System.err.println("unknown command: "+args[i]); }
    }
  }
  private static void showoptions() {
    String[] msg = {
      "pt: print table",
      "pi: print intcode",
      "pc: print block-connection",
//      "vn: value numbering",
//      "pvn: value numvering with printout",
//      "clio: calculate LiveIn/LIveOut",
//      "plio: print LiveIn/LiveOut",
    };
    System.out.println("usage: java samc1/SamC1 <source> <option>...");
    for(String s: msg) { System.out.println("  " + s); }
  }
}
class Log {
  public static int err = 0;
  public static void pError(String s) { System.out.println(s); ++err; }
  public static int getError() { return err; }
}
class Symtab {
  public static final int ITYPE = 1, ATYPE = 2, UNDEF = -1;
  List<Ent> tbl = new ArrayList<Ent>();
  Stack<Integer> stk = new Stack<Integer>();
  int mark;

  private boolean duplCheck(String n) {
    for(int i = mark; i < tbl.size(); ++i) {
      Ent e = tbl.get(i);
      if(e.alive && e.name.equals(n)) { return true; }
    }
    return false;
  }
  public Ent addDef(String n, int t) {
    if(duplCheck(n)) {
      Log.pError("dublicate: "+n); return new Ent(n, UNDEF, 0);
    }
    Ent e = new Ent(n, t, tbl.size()); tbl.add(e); return e;
  }
  public void enterScope() { stk.push(mark); mark = tbl.size(); }
  public void exitScope() {
    for(int i = mark; i < tbl.size(); ++i) { tbl.get(i).alive = false; }
    mark = stk.pop();
  }
  public Ent lookup(String n) {
    for(int i = tbl.size()-1; i >= 0; --i) {
      Ent e = tbl.get(i);
      if(e.alive && e.name.equals(n)) { return e; }
    }
    return new Ent(n, UNDEF, 0);
  }
  public int getGsize() { return tbl.size(); }
  public void show() { for(Ent e: tbl) { System.out.println(" " + e); } }
  public static class Ent {
    public String name;
    public boolean alive = true;
    public int type, pos = 0;
    public Ent(String n, int t, int p) { name = n; type = t; pos = p; }
    public String toString() {
      return String.format("%s%s[%d %d]", name, alive?"_":"!", type, pos);
    }
  }
}

package samc1;
import samc1.analysis.*;
import samc1.node.*;
import java.io.*;
import java.util.*;

class TypeChecker extends DepthFirstAdapter {
Symtab st;
HashMap vtbl;
public TypeChecker(Symtab tb, HashMap vt) { st = tb; vtbl = vt; }
private void ckv(Node n, int t, int l, String s) {
  if(getOut(n) instanceof Integer && (Integer)getOut(n) == t) { return; }
  Log.pError(l+": "+s);
}
private int cki(String i, int t, int l) {
  Symtab.Ent e = st.lookup(i);
  if(e.type != t) { Log.pError(l+": identyfier is not of expexted type: "+i); }
  return e.pos;
}
@Override
public void inAMainProg(AMainProg node) {
  st.addDef("$dummy$", Symtab.ITYPE);
  st.addDef(node.getIdent().getText(), Symtab.ITYPE);
}
@Override
public void outAIdclDcl(AIdclDcl node) {
  Symtab.Ent e = st.addDef(node.getIdent().getText(), Symtab.ITYPE);
  vtbl.put(node, e.pos);
}
@Override
public void outAAdclDcl(AAdclDcl node) {
  Symtab.Ent e = st.addDef(node.getIdent().getText(), Symtab.ATYPE);
  vtbl.put(node, e.pos);
}
@Override
public void outAIdclStat(AIdclStat node) {
  st.addDef(node.getIdent().getText(), Symtab.ITYPE);
}
@Override
public void outAAssignStat(AAssignStat node) {
  int p = cki(node.getIdent().getText(), Symtab.ITYPE, node.getIdent().getLine());
  ckv(node.getExpr(), Symtab.ITYPE, node.getAssign().getLine(), "non-int val");
  vtbl.put(node, p);
}
@Override
public void outAAassignStat(AAassignStat node) {
  int p = cki(node.getIdent().getText(), Symtab.ATYPE, node.getIdent().getLine());
  ckv(node.getIdx(), Symtab.ITYPE, node.getLsbr().getLine(), "non-int index");
  ckv(node.getExpr(), Symtab.ITYPE, node.getAssign().getLine(), "non-int val");
  vtbl.put(node, p);
}
@Override
public void outAIfStat(AIfStat node) {
  ckv(node.getExpr(), Symtab.ITYPE, node.getLpar().getLine(), "non-int cond");
}
@Override
public void outAWhileStat(AWhileStat node) {
  ckv(node.getExpr(), Symtab.ITYPE, node.getLpar().getLine(), "non-int cond");
}
@Override
public void inABlockStat(ABlockStat node) { st.enterScope(); }
@Override
public void outABlockStat(ABlockStat node) { st.exitScope(); }
@Override
public void outAGtExpr(AGtExpr node) {
  ckv(node.getLeft(), Symtab.ITYPE, node.getGt().getLine(), "non-int val");
  ckv(node.getRight(), Symtab.ITYPE, node.getGt().getLine(), "non-int val");
  setOut(node, new Integer(Symtab.ITYPE));
}
@Override
public void outALtExpr(ALtExpr node) {
  ckv(node.getLeft(), Symtab.ITYPE, node.getLt().getLine(), "non-int val");
  ckv(node.getRight(), Symtab.ITYPE, node.getLt().getLine(), "non-int val");
  setOut(node, new Integer(Symtab.ITYPE));
}
@Override
public void outAOneExpr(AOneExpr node) { setOut(node, getOut(node.getNexp())); }
@Override
public void outAAddNexp(AAddNexp node) {
  ckv(node.getNexp(), Symtab.ITYPE, node.getAdd().getLine(), "non-int val");
  ckv(node.getTerm(), Symtab.ITYPE, node.getAdd().getLine(), "non-int val");
  setOut(node, new Integer(Symtab.ITYPE));
}
@Override
public void outASubNexp(ASubNexp node) {
  ckv(node.getNexp(), Symtab.ITYPE, node.getSub().getLine(), "non-int val");
  ckv(node.getTerm(), Symtab.ITYPE, node.getSub().getLine(), "non-int val");
  setOut(node, new Integer(Symtab.ITYPE));
}
@Override
public void outAOneNexp(AOneNexp node) { setOut(node, getOut(node.getTerm())); }
@Override
public void outAMulTerm(AMulTerm node) {
  ckv(node.getTerm(), Symtab.ITYPE, node.getAster().getLine(), "non-int val");
  ckv(node.getFact(), Symtab.ITYPE, node.getAster().getLine(), "non-int val");
  setOut(node, new Integer(Symtab.ITYPE));
}
@Override
public void outADivTerm(ADivTerm node) {
  ckv(node.getTerm(), Symtab.ITYPE, node.getSlash().getLine(), "non-int val");
  ckv(node.getFact(), Symtab.ITYPE, node.getSlash().getLine(), "non-int val");
  setOut(node, new Integer(Symtab.ITYPE));
}
@Override
public void outAOneTerm(AOneTerm node) { setOut(node, getOut(node.getFact())); }
@Override
public void outAIconstFact(AIconstFact node) {
  setOut(node, new Integer(Symtab.ITYPE));
}
@Override
public void outAIdentFact(AIdentFact node) {
  Symtab.Ent e = st.lookup(node.getIdent().getText());
  setOut(node, new Integer(e.type)); vtbl.put(node, e.pos);
}
@Override
public void outAArefFact(AArefFact node) {
  int p = cki(node.getIdent().getText(), Symtab.ATYPE, node.getIdent().getLine());
  ckv(node.getExpr(), Symtab.ITYPE, node.getLsbr().getLine(), "non-int index");
  setOut(node, new Integer(Symtab.ITYPE)); vtbl.put(node, p);
}
@Override
public void outAOneFact(AOneFact node) { setOut(node, getOut(node.getExpr())); }
}

package samc1;
import java.util.*;

public class ValNumber {
  Map<Integer, String> tmpval = new HashMap<Integer,String>();
  Map<String, Integer> valtmp = new HashMap<String,Integer>();
  Map<String, String> expval = new HashMap<String,String>();
  int vcnt = 1;
  public void exec(List<IntCode.Inst> lst, boolean pr) {
    for(int k = 0; k < lst.size(); ++k) {
      IntCode.Inst op = lst.get(k), op1 = op;  insttmp(op);
      int d = op.assDest();
      if(d < 0) {
        op1 = renew(op);
      } else {
        String exp = newexp(op), v = exp2val(exp);
        if(!valtmp.containsKey(v)) {
          op1 = renew(op);
          tmpval.put(d, v); valtmp.put(v, d);
          if(pr) { System.out.printf(" t%d:%s = %s\n", d, v, exp); }
        } else {
          int t = valtmp.get(v);
          if(tmpval.get(t).equals(v)) {
            op1 = new IntCode.Move(d, t);
            tmpval.put(d, v);
            if(pr) { System.out.printf(" t%d:%s = t%d\n", d, v, t); }
          } else {
            op1 = renew(op);
            tmpval.put(d, v); valtmp.put(v, t);
            if(pr) { System.out.printf(" t%d:%s = %s\n", d, v, exp); }
          }
        }
      }
      if(pr) { System.out.println("        " + op + " ==> " + op1); }
      lst.set(k, op1);
    }
    if(!pr) { return; }
    System.out.println("--------");
    for(Integer i: tmpval.keySet()) { pl("  t"+i+" = "+tmpval.get(i)); }
    System.out.println("--------");
    for(String e: valtmp.keySet()) { pl("  "+e+" = t"+valtmp.get(e)); }
    System.out.println("--------");
    for(String e: expval.keySet()) { pl("  "+e+" = "+expval.get(e)); }
    System.out.println("--------");
  }
  private void pl(String s) { System.out.println(s); }
  private boolean alldigit(String s) { return s.matches("^[0-9]+$"); }
  private String exp2val(String e) {
    if(expval.containsKey(e)) { return expval.get(e); }
    if(alldigit(e)) { return e; }
    if(e.charAt(0) == 'v' && alldigit(e.substring(1))) { return e; }
    String v = "v"+vcnt++; expval.put(e, v); return v;
  }
  private void insttmp(IntCode.Inst op) {
    for(int i = 0; i < op.refNum(); ++i) {
      int t = op.getRefs()[i];
      if(!tmpval.containsKey(t)) {
        String v = "v"+vcnt++; tmpval.put(t, v); valtmp.put(v, t);
      }
    }
  }
  private String newexp(IntCode.Inst op) {
    String e = "?";
    int[] ref = op.getRefs();
    if(op.refNum() == 0) {
      e = op.refExp();
    } else if(op.refNum() == 1) {
      e = op.refExp(tmpval.get(ref[0]));
    } else {
      e = op.refExp(tmpval.get(ref[0]), tmpval.get(ref[1]));
    }
    return e;
  }
  private IntCode.Inst renew(IntCode.Inst op) {
    int[] r = op.getRefs();
    if(op.refNum() == 0) {
      return op.renew();
    } else if(op.refNum() == 1) {
      Integer i1 = valtmp.get(tmpval.get(r[0]));
      return i1 == null ? op : op.renew(i1);
    } else {
      Integer i1 = valtmp.get(tmpval.get(r[0]));
      Integer i2 = valtmp.get(tmpval.get(r[1]));
      return i1 == null || i2 == null ? op : op.renew(i1, i2);
    }
  }
  public static void run(IntCode ic, boolean pr) {
    for(IntCode.Block b: ic.getBlocks()) {
      if(pr) { System.out.println(b.getLabel()); }
      new ValNumber().exec(b.getBody(), pr);
    }
  }
}

package samc1;
import java.util.*;
public class Dataflow {
  List<IntCode.Block> blocks;
  public Dataflow(List<IntCode.Block> b) { blocks = b; }
  private List<Set<Integer>> newListSet() {
    List<Set<Integer>> lst = new ArrayList<Set<Integer>>();
    for(IntCode.Block b: blocks) { lst.add(new TreeSet<Integer>()); }
    return lst;
  }
  private static Set<Integer> add(Set<Integer> s1, Set<Integer> s2) {
    Set<Integer> s3 = new TreeSet<Integer>();
    for(Integer i: s1) { s3.add(i); }
    for(Integer i: s2) { s3.add(i); }
    return s3;
  }
  private static Set<Integer> sub(Set<Integer> s1, Set<Integer> s2) {
    Set<Integer> s3 = new TreeSet<Integer>();
    for(Integer i: s1) { if(!s2.contains(i)) { s3.add(i); } }
    return s3;
  }

  List<Set<Integer>> liveIn, liveOut;
  List<Set<Integer>> blkRef, blkDef;
  public List<Set<Integer>> getLiveIn() { return liveIn; }
  public List<Set<Integer>> getLiveOut() { return liveOut; }
  public void calcLiveInOut() {
    liveIn = newListSet(); liveOut = newListSet();
    boolean chg = true;
    while(chg) {
      chg = false;
      for(IntCode.Block b: blocks) {
        Set<Integer> li1, lo1 = new TreeSet<Integer>();
        for(Integer i: b.getSucc()) { lo1 = add(lo1, liveIn.get(i)); }
        li1 = add(b.getRef(), sub(lo1, b.getDef()));
        int i = b.getId();
        if(!(liveIn.get(i).equals(li1))) { liveIn.set(i, li1); chg = true; }
        if(!(liveOut.get(i).equals(lo1))) { liveOut.set(i, lo1); chg = true; }
      }
    }
  }
  public void showLiveInOut() {
    for(IntCode.Block b: blocks) {
      int id = b.getId();
      System.out.printf("LiveIn/Out[B%d] = {", id);
      for(Integer i: liveIn.get(id)) { System.out.print(" "+i); }
      System.out.print(" } {");
      for(Integer i: liveOut.get(id)) { System.out.print(" "+i); }
      System.out.println(" }");
    }
  }
}