codegen/codegen.sml

   1 (* L3 Compiler
   2  * Assembly code generator for fake x86 assembly
   3  * Author: Joshua Wise <jwise@andrew.cmu.edu>
   4  * Author: Chris Lu <czl@andrew.cmu.edu>
   5  *)
   6
   7 signature CODEGEN =
   8 sig
   9   val codegen : Tree.stm list -> x86.insn list
  10 end
  11
  12 structure Codegen :> CODEGEN =
  13 struct
  14   structure T = Tree
  15   structure X = x86
  16
  17   (* effect : T.exp -> bool
  18    * true iff the given expression has an effect.
  19    *)
  20   fun effect (T.BINOP(T.DIV, _, _)) = true
  21     | effect (T.BINOP(T.MOD, _, _)) = true
  22     | effect (T.CALL _) = true
  23     | effect (T.BINOP(_, a, b)) = (effect a) orelse (effect b)
  24     | effect (T.UNOP (_, a)) = effect a
  25     | effect (T.MEMORY m) = true
  26     | effect (T.ALLOC(_)) = true
  27     | effect _ = false
  28
  29   (* hasfixed : T.exp -> bool
  30    * true iff the given expression has an hasfixed. Somewhat like effect, hmm?
  31    *)
  32   fun hasfixed (T.BINOP(T.DIV, _, _)) = true
  33     | hasfixed (T.BINOP(T.MOD, _, _)) = true
  34     | hasfixed (T.BINOP(T.LSH, _, _)) = true
  35     | hasfixed (T.BINOP(T.RSH, _, _)) = true
  36     | hasfixed (T.CALL _) = true
  37     | hasfixed (T.BINOP(_, a, b)) = (hasfixed a) orelse (hasfixed b)
  38     | hasfixed (T.UNOP (_, a)) = hasfixed a
  39     | hasfixed (T.ALLOC(_)) = true
  40     | hasfixed (T.MEMORY m) = hasfixed m
  41     | hasfixed _ = false
  42
  43   (* munch_exp : prex86oper -> T.exp -> prex86insn list *)
  44   (* munch_exp d e
  45    * generates instructions to achieve d <- e
  46    * d must be TEMP(t) or REG(r)
  47    *)
  48   and munch_exp d (T.CONST(n)) = [X.MOV(d, X.CONST n)]
  49     | munch_exp d (T.TEMP(t)) = [X.MOV(d, X.TEMP t)]
  50     | munch_exp d (T.ARG(0, sz)) = [X.MOV(d, X.OSIZE (X.sts sz, X.REG X.EDI))]
  51     | munch_exp d (T.ARG(1, sz)) = [X.MOV(d, X.OSIZE (X.sts sz, X.REG X.ESI))]
  52     | munch_exp d (T.ARG(2, sz)) = [X.MOV(d, X.OSIZE (X.sts sz, X.REG X.EDX))]
  53     | munch_exp d (T.ARG(3, sz)) = [X.MOV(d, X.OSIZE (X.sts sz, X.REG X.ECX))]
  54     | munch_exp d (T.ARG(4, sz)) = [X.MOV(d, X.OSIZE (X.sts sz, X.REG X.R8D))]
  55     | munch_exp d (T.ARG(5, sz)) = [X.MOV(d, X.OSIZE (X.sts sz, X.REG X.R9D))]
  56     | munch_exp d (T.ARG(t, sz)) = [X.MOV(d, X.OSIZE (X.sts sz, X.STACKARG (t - 6)))]
  57     | munch_exp d (T.CALL(name, l, rsz)) =      (* Scary demons live here. *)
  58         let
  59           val nargs = length l
  60           val nstack = if (nargs <= 6)
  61                        then 0
  62                        else nargs - 6
  63           val stackb = nstack * 8
  64           fun argdest 1 = X.REG X.EDI
  65             | argdest 2 = X.REG X.ESI
  66             | argdest 3 = X.REG X.EDX
  67             | argdest 4 = X.REG X.ECX
  68             | argdest 5 = X.REG X.R8D
  69             | argdest 6 = X.REG X.R9D
  70             | argdest n = X.REL (X.REG X.RSP, X.CONST (Word32.fromInt (~(stackb - 8 * (n - 7)))) )
  71
  72           val dests = List.tabulate (nargs, fn x => argdest (x+1))
  73           val (exps,_) = ListPair.unzip l
  74           val hf = List.map hasfixed exps
  75           val (d_hf, l_hf) = ListPair.unzip (ListPair.foldr
  76             (fn (a,b,c) => if b then a::c else c)
  77             nil
  78             (ListPair.zip (dests,l), hf)
  79           )
  80           val (d_nohf, l_nohf) = ListPair.unzip (ListPair.foldr
  81             (fn (a,b,c) => if b then c else a::c)
  82             nil
  83             (ListPair.zip (dests,l), hf)
  84           )
  85           val temps = List.map (fn (_, sz) => Temp.new ("arg") sz (* xxx? *)) l_hf
  86           val argevals_hf = List.map
  87             (fn (t,(exp,_)) => munch_exp (X.TEMP t) exp)
  88             (ListPair.zip (temps, l_hf))
  89           val argpushes = List.map
  90             (fn (dest, t) => [(X.MOV (X.OSIZE(X.sts (Temp.size t), dest), X.TEMP t))])
  91             (ListPair.zip (d_hf, temps))
  92           val argevals_nohf = List.map
  93             (fn (d,(exp,sz)) => munch_exp (X.OSIZE (X.sts sz, d)) exp)
  94             (ListPair.zip (d_nohf, l_nohf))
  95         in
  96           List.concat argevals_hf @
  97           List.concat argpushes @
  98           List.concat argevals_nohf @
  99           [ X.SUB (X.OSIZE (X.Qword, X.REG X.RSP), X.CONST (Word32.fromInt stackb)),
 100             X.CALL (name, nargs),
 101             X.ADD (X.OSIZE (X.Qword, X.REG X.RSP), X.CONST (Word32.fromInt stackb)),
 102             X.MOV (d, X.OSIZE (X.sts rsz, X.REG X.EAX)) ]       (* Finally! *)
 103         end
 104 (*    | munch_exp d (T.BINOP(T.ADD, e1, T.CONST 0w0)) = munch_exp d e1
 105     | munch_exp d (T.BINOP(T.ADD, T.CONST 0w0, e1)) = munch_exp d e1
 106     | munch_exp d (T.BINOP(T.ADD, e1, T.CONST n)) = (munch_exp d e1) @ [X.ADD(d, X.CONST n)]
 107     | munch_exp d (T.BINOP(T.ADD, T.CONST n, e1)) = (munch_exp d e1) @ [X.ADD(d, X.CONST n)]
 108     | munch_exp d (T.BINOP(T.ADD, e1, T.TEMP t)) = (munch_exp d e1) @ [X.ADD(d, X.TEMP t)]
 109     | munch_exp d (T.BINOP(T.ADD, T.TEMP t, e2)) = (munch_exp d e2) @ [X.ADD(d, X.TEMP t)] *)
 110     | munch_exp d (T.BINOP(T.ADD, e1, e2)) =
 111         let
 112           val t1 = X.TEMP (Temp.new ("add") 4)
 113         in
 114           (munch_exp d e1) @ (munch_exp t1 e2) @ [X.ADD(d, t1)]
 115         end
 116 (*    | munch_exp d (T.BINOP(T.SUB, T.CONST 0w0, e1)) = (munch_exp d e1) @ [X.NEG d]
 117     | munch_exp d (T.BINOP(T.SUB, e1, T.CONST 0w0)) = munch_exp d e1
 118     | munch_exp d (T.BINOP(T.SUB, e1, T.CONST(n))) = (munch_exp d e1) @ [X.SUB(d, X.CONST n)]
 119     | munch_exp d (T.BINOP(T.SUB, e1, T.TEMP t)) = (munch_exp d e1) @ [X.SUB(d, X.TEMP t)] *)
 120     | munch_exp d (T.BINOP(T.SUB, e1, e2)) =
 121         let
 122           val t1 = X.TEMP (Temp.new ("sub") 4)
 123         in
 124           (munch_exp d e1) @ (munch_exp t1 e2) @ [X.SUB(d, t1)]
 125         end
 126     | munch_exp d (T.BINOP(T.MUL, T.TEMP t, T.CONST n)) = [X.IMUL3(d, X.TEMP t, n)]
 127     | munch_exp d (T.BINOP(T.MUL, T.CONST n, T.TEMP t)) = [X.IMUL3(d, X.TEMP t, n)]
 128 (*
 129     | munch_exp d (T.BINOP(T.MUL, e1, T.CONST 0w1)) = munch_exp d e1
 130     | munch_exp d (T.BINOP(T.MUL, T.CONST 0w1, e1)) = munch_exp d e1
 131     | munch_exp d (T.BINOP(T.MUL, e1, T.CONST n)) = (munch_exp d e1) @ [X.IMUL(d, X.CONST n)]
 132     | munch_exp d (T.BINOP(T.MUL, T.CONST n, e1)) = (munch_exp d e1) @ [X.IMUL(d, X.CONST n)] *)
 133     | munch_exp d (T.BINOP(T.MUL, e1, e2)) =
 134         let
 135           val t1 = X.TEMP (Temp.new ("mul") 4)
 136         in
 137           (munch_exp d e1) @ (munch_exp t1 e2) @ [X.IMUL(d, t1)]
 138         end
 139     | munch_exp d (T.BINOP(T.DIV, e1, e2)) =
 140         let
 141           val t1 = X.TEMP (Temp.new ("div") 4)
 142         in
 143           (munch_exp t1 e1) @ (munch_exp d e2) @
 144           [X.MOV (X.REG X.EAX, t1), X.CLTD, X.IDIV d, X.MOV (d, X.REG X.EAX)]
 145         end
 146     | munch_exp d (T.BINOP(T.MOD, e1, e2)) =
 147         let
 148           val t1 = X.TEMP (Temp.new ("mod") 4)
 149         in
 150           (munch_exp t1 e1) @ (munch_exp d e2) @
 151           [X.MOV (X.REG X.EAX, t1), X.CLTD, X.IDIV d, X.MOV (d, X.REG X.EDX)]
 152         end
 153     | munch_exp d (T.BINOP(T.LSH, e1, T.CONST n)) = (munch_exp d e1) @ [X.SAL (d, X.CONST (n mod 0w32))]
 154     | munch_exp d (T.BINOP(T.LSH, e1, T.TEMP t)) = (munch_exp d e1) @ [X.MOV (X.REG X.ECX, X.TEMP t), X.SAL (d, X.REG X.ECX)]
 155     | munch_exp d (T.BINOP(T.LSH, e1, e2)) =
 156         let
 157           val t = X.TEMP (Temp.new ("lsh") 4)
 158         in
 159           (munch_exp d e1) @ (munch_exp t e2) @ [X.MOV (X.REG X.ECX, t), X.SAL (d, X.REG X.ECX)]
 160         end
 161     | munch_exp d (T.BINOP(T.RSH, e1, T.CONST n)) = (munch_exp d e1) @ [X.SAR (d, X.CONST (n mod 0w32))]
 162     | munch_exp d (T.BINOP(T.RSH, e1, T.TEMP t)) = (munch_exp d e1) @ [X.MOV (X.REG X.ECX, X.TEMP t), X.SAR (d, X.REG X.ECX)]
 163     | munch_exp d (T.BINOP(T.RSH, e1, e2)) =
 164         let
 165           val t = X.TEMP (Temp.new ("rsh") 4)
 166         in
 167           (munch_exp d e1) @ (munch_exp t e2) @ [X.MOV (X.REG X.ECX, t), X.SAR (d, X.REG X.ECX)]
 168         end
 169     | munch_exp d (T.BINOP(T.BITAND, T.CONST n, e1)) = (munch_exp d e1) @ [X.AND (d, X.CONST n)]
 170     | munch_exp d (T.BINOP(T.BITAND, e1, T.CONST n)) = (munch_exp d e1) @ [X.AND (d, X.CONST n)]
 171     | munch_exp d (T.BINOP(T.BITAND, T.TEMP t, e1)) = (munch_exp d e1) @ [X.AND (d, X.TEMP t)]
 172     | munch_exp d (T.BINOP(T.BITAND, e1, T.TEMP t)) = (munch_exp d e1) @ [X.AND (d, X.TEMP t)]
 173     | munch_exp d (T.BINOP(T.BITAND, e1, e2)) =
 174         let
 175           val t1 = X.TEMP (Temp.new ("bitand") 4)
 176         in
 177           (munch_exp d e1) @ (munch_exp t1 e2) @ [X.AND(d, t1)]
 178         end
 179     | munch_exp d (T.BINOP(T.BITOR, T.CONST n, e1)) = (munch_exp d e1) @ [X.OR (d, X.CONST n)]
 180     | munch_exp d (T.BINOP(T.BITOR, e1, T.CONST n)) = (munch_exp d e1) @ [X.OR (d, X.CONST n)]
 181     | munch_exp d (T.BINOP(T.BITOR, T.TEMP t, e1)) = (munch_exp d e1) @ [X.OR (d, X.TEMP t)]
 182     | munch_exp d (T.BINOP(T.BITOR, e1, T.TEMP t)) = (munch_exp d e1) @ [X.OR (d, X.TEMP t)]
 183     | munch_exp d (T.BINOP(T.BITOR, e1, e2)) =
 184         let
 185           val t1 = X.TEMP (Temp.new ("bitor") 4)
 186         in
 187           (munch_exp d e1) @ (munch_exp t1 e2) @ [X.OR(d, t1)]
 188         end
 189     | munch_exp d (T.BINOP(T.BITXOR, T.CONST n, e1)) = (munch_exp d e1) @ [X.XOR (d, X.CONST n)]
 190     | munch_exp d (T.BINOP(T.BITXOR, e1, T.CONST n)) = (munch_exp d e1) @ [X.XOR (d, X.CONST n)]
 191     | munch_exp d (T.BINOP(T.BITXOR, T.TEMP t, e1)) = (munch_exp d e1) @ [X.XOR (d, X.TEMP t)]
 192     | munch_exp d (T.BINOP(T.BITXOR, e1, T.TEMP t)) = (munch_exp d e1) @ [X.XOR (d, X.TEMP t)]
 193     | munch_exp d (T.BINOP(T.BITXOR, e1, e2)) =
 194         let
 195           val t1 = X.TEMP (Temp.new ("bitxor") 4)
 196         in
 197           (munch_exp d e1) @ (munch_exp t1 e2) @ [X.XOR(d, t1)]
 198         end
 199     | munch_exp d (a as T.BINOP(T.LOGAND, e1, e2)) =
 200         let
 201           val (insn1, pos1, neg1) = munch_cond e1
 202           val (insn2, pos2, neg2) = munch_cond e2
 203           val t1 = X.TEMP (Temp.new("logand 1") 4)
 204           val t2 = X.TEMP (Temp.new("logand 2") 4)
 205           val l = Label.new ()
 206         in
 207           if (effect e2 orelse (length insn2 > 10))
 208           then (insn1) @
 209                [X.SETcc(pos1, t1), X.Jcc (neg1, l)] @
 210                (insn2) @
 211                [X.SETcc(pos2, t1), X.LABEL l, X.MOVZB(d, t1)]
 212           else insn1 @ [X.SETcc (pos1, t1)] @ insn2 @ [X.SETcc (pos2, t2), X.AND(X.OSIZE (X.Byte, t1), X.OSIZE (X.Byte, t2)), X.MOVZB(d, t1)]
 213         end
 214     | munch_exp d (a as T.BINOP(T.LOGOR, e1, e2)) =
 215         let
 216           val (insn1, pos1, neg1) = munch_cond e1
 217           val (insn2, pos2, neg2) = munch_cond e2
 218           val t1 = X.TEMP (Temp.new("logor 1") 4)
 219           val t2 = X.TEMP (Temp.new("logor 2") 4)
 220           val l = Label.new ()
 221         in
 222           if (effect e2 orelse (length insn2 > 10))
 223           then (insn1) @
 224                [X.SETcc(pos1, t1), X.Jcc (pos1, l)] @
 225                (insn2) @
 226                [X.SETcc(pos2, t1), X.LABEL l, X.MOVZB(d, t1)]
 227           else insn1 @ [X.SETcc (pos1, t1)] @ insn2 @ [X.SETcc (pos2, t2), X.OR(X.OSIZE (X.Byte, t1), X.OSIZE (X.Byte, t2)), X.MOVZB(d, t1)]
 228         end
 229     | munch_exp d (a as T.BINOP(T.EQ, _, _)) =
 230         let val (insns, pos, neg) = munch_cond a in insns @ [X.SETcc (pos, d), X.MOVZB(d, d)] end
 231     | munch_exp d (a as T.BINOP(T.NEQ, _, _)) =
 232         let val (insns, pos, neg) = munch_cond a in insns @ [X.SETcc (pos, d), X.MOVZB(d, d)] end
 233     | munch_exp d (a as T.BINOP(T.LE, _, _)) =
 234         let val (insns, pos, neg) = munch_cond a in insns @ [X.SETcc (pos, d), X.MOVZB(d, d)] end
 235     | munch_exp d (a as T.BINOP(T.LT, _, _)) =
 236         let val (insns, pos, neg) = munch_cond a in insns @ [X.SETcc (pos, d), X.MOVZB(d, d)] end
 237     | munch_exp d (a as T.BINOP(T.GE, _, _)) =
 238         let val (insns, pos, neg) = munch_cond a in insns @ [X.SETcc (pos, d), X.MOVZB(d, d)] end
 239     | munch_exp d (a as T.BINOP(T.GT, _, _)) =
 240         let val (insns, pos, neg) = munch_cond a in insns @ [X.SETcc (pos, d), X.MOVZB(d, d)] end
 241     | munch_exp d (T.UNOP(T.NEG, T.CONST n)) = [X.MOV (d, X.CONST (~n))]
 242     | munch_exp d (T.UNOP(T.NEG, e1)) = (munch_exp d e1) @ [X.NEG d]
 243     | munch_exp d (T.UNOP(T.BITNOT, T.CONST n)) = [X.MOV (d, X.CONST (Word32.notb n))]
 244     | munch_exp d (T.UNOP(T.BITNOT, e1)) = (munch_exp d e1) @ [X.NOT d]
 245     | munch_exp d (T.UNOP(T.BANG, T.CONST n)) = if (n = 0w0) then [X.MOV (d, X.CONST 0w1)] else [X.MOV (d, X.CONST 0w0)]
 246     | munch_exp d (T.UNOP(T.BANG, e)) =
 247         let
 248           val (insns, pos, neg) = munch_cond e
 249         in
 250           insns @ [X.SETcc (neg, d), X.MOVZB(d, d)]
 251         end
 252     | munch_exp d (T.MEMORY e1) =
 253         let
 254           val a = X.TEMP (Temp.new "addr" 8)
 255         in
 256           munch_exp a e1 @ [X.MOV (d, X.REL (a, X.CONST 0w0))]
 257         end
 258     | munch_exp d (T.ALLOC(exp)) = (munch_exp d (T.CALL (Symbol.symbol "calloc", [(exp, 4), (T.CONST 0w1, 4)], 8)))
 259                                    @ [X.MOV (X.REL (d, X.CONST 0w0), X.CONST 0w0)]
 260
 261   (* munch_cond : T.exp -> X.insn list * X.cond * X.cond
 262    * munch_cond stm generates code to set flags, and then returns a conditional
 263    * to test if the expression was true and for if it was false.
 264    *)
 265   and munch_cond (T.UNOP (T.BANG, e)) =
 266         let
 267           val (insns, pos, neg) = munch_cond e
 268         in
 269           (insns, neg, pos)
 270         end
 271     | munch_cond (T.BINOP(T.NEQ, T.TEMP t, T.CONST n)) = ([X.CMP(X.TEMP t, X.CONST n)], X.NE, X.E)
 272     | munch_cond (T.BINOP(T.NEQ, T.CONST n, T.TEMP t)) = ([X.CMP(X.TEMP t, X.CONST n)], X.NE, X.E)
 273     | munch_cond (T.BINOP(T.NEQ, T.CONST n, e1)) =
 274         let val t = X.TEMP (Temp.new ("const neq") 4) in (munch_exp t e1 @ [X.CMP(t, X.CONST n)], X.NE, X.E) end
 275     | munch_cond (T.BINOP(T.NEQ, e1, T.CONST n)) =
 276         let val t = X.TEMP (Temp.new ("const neq") 4) in (munch_exp t e1 @ [X.CMP(t, X.CONST n)], X.NE, X.E) end
 277     | munch_cond (T.BINOP(T.NEQ, T.TEMP t, e1)) =
 278         let val t1 = X.TEMP (Temp.new ("const neq") 4) in (munch_exp t1 e1 @ [X.CMP(t1, X.TEMP t)], X.NE, X.E) end
 279     | munch_cond (T.BINOP(T.NEQ, e1, T.TEMP t)) =
 280         let val t1 = X.TEMP (Temp.new ("const neq") 4) in (munch_exp t1 e1 @ [X.CMP(t1, X.TEMP t)], X.NE, X.E) end
 281     | munch_cond (T.BINOP(T.NEQ, e1, e2)) =
 282         let
 283           val t1 = X.TEMP (Temp.new ("var neq 1") 4)
 284           val t2 = X.TEMP (Temp.new ("var neq 2") 4)
 285         in
 286           (munch_exp t1 e1 @ munch_exp t2 e2 @
 287            [X.CMP(t1, t2)], X.NE, X.E)
 288         end
 289     | munch_cond (T.BINOP(T.EQ, T.TEMP t, T.CONST n)) = ([X.CMP(X.TEMP t, X.CONST n)], X.E, X.NE)
 290     | munch_cond (T.BINOP(T.EQ, T.CONST n, T.TEMP t)) = ([X.CMP(X.TEMP t, X.CONST n)], X.E, X.NE)
 291     | munch_cond (T.BINOP(T.EQ, T.CONST n, e1)) =
 292         let val t = X.TEMP (Temp.new ("const eq") 4) in (munch_exp t e1 @ [X.CMP(t, X.CONST n)], X.E, X.NE) end
 293     | munch_cond (T.BINOP(T.EQ, e1, T.CONST n)) =
 294         let val t = X.TEMP (Temp.new ("const eq") 4) in (munch_exp t e1 @ [X.CMP(t, X.CONST n)], X.E, X.NE) end
 295     | munch_cond (T.BINOP(T.EQ, T.TEMP t, e1)) =
 296         let val t1 = X.TEMP (Temp.new ("const eq") 4) in (munch_exp t1 e1 @ [X.CMP(t1, X.TEMP t)], X.E, X.NE) end
 297     | munch_cond (T.BINOP(T.EQ, e1, T.TEMP t)) =
 298         let val t1 = X.TEMP (Temp.new ("const eq") 4) in (munch_exp t1 e1 @ [X.CMP(t1, X.TEMP t)], X.E, X.NE) end
 299     | munch_cond (T.BINOP(T.EQ, e1, e2)) =
 300         let
 301           val t1 = X.TEMP (Temp.new ("var eq 1") 4)
 302           val t2 = X.TEMP (Temp.new ("var eq 2") 4)
 303         in
 304           (munch_exp t1 e1 @ munch_exp t2 e2 @
 305            [X.CMP(t1, t2)], X.E, X.NE)
 306         end
 307     | munch_cond (T.BINOP(T.LE, T.TEMP t, T.CONST n)) = ([X.CMP(X.TEMP t, X.CONST n)], X.LE, X.G)
 308     | munch_cond (T.BINOP(T.LE, T.CONST n, T.TEMP t)) = ([X.CMP(X.TEMP t, X.CONST n)], X.GE, X.L)
 309     | munch_cond (T.BINOP(T.LE, T.CONST n, e1)) =
 310         let val t = X.TEMP (Temp.new ("const le") 4) in (munch_exp t e1 @ [X.CMP(t, X.CONST n)], X.GE, X.L) end
 311     | munch_cond (T.BINOP(T.LE, e1, T.CONST n)) =
 312         let val t = X.TEMP (Temp.new ("const le") 4) in (munch_exp t e1 @ [X.CMP(t, X.CONST n)], X.LE, X.G) end
 313     | munch_cond (T.BINOP(T.LE, T.TEMP t, e1)) =
 314         let val t1 = X.TEMP (Temp.new ("const le") 4) in (munch_exp t1 e1 @ [X.CMP(t1, X.TEMP t)], X.GE, X.L) end
 315     | munch_cond (T.BINOP(T.LE, e1, T.TEMP t)) =
 316         let val t1 = X.TEMP (Temp.new ("const le") 4) in (munch_exp t1 e1 @ [X.CMP(t1, X.TEMP t)], X.LE, X.G) end
 317     | munch_cond (T.BINOP(T.LE, e1, e2)) =
 318         let
 319           val t1 = X.TEMP (Temp.new ("var le 1") 4)
 320           val t2 = X.TEMP (Temp.new ("var le 2") 4)
 321         in
 322           (munch_exp t1 e1 @ munch_exp t2 e2 @
 323            [X.CMP(t1, t2)], X.LE, X.G)
 324         end
 325     | munch_cond (T.BINOP(T.LT, T.TEMP t, T.CONST n)) = ([X.CMP(X.TEMP t, X.CONST n)], X.L, X.GE)
 326     | munch_cond (T.BINOP(T.LT, T.CONST n, T.TEMP t)) = ([X.CMP(X.TEMP t, X.CONST n)], X.G, X.LE)
 327     | munch_cond (T.BINOP(T.LT, T.CONST n, e1)) =
 328         let val t = X.TEMP (Temp.new ("const lt") 4) in (munch_exp t e1 @ [X.CMP(t, X.CONST n)], X.G, X.LE) end
 329     | munch_cond (T.BINOP(T.LT, e1, T.CONST n)) =
 330         let val t = X.TEMP (Temp.new ("const lt") 4) in (munch_exp t e1 @ [X.CMP(t, X.CONST n)], X.L, X.GE) end
 331     | munch_cond (T.BINOP(T.LT, T.TEMP t, e1)) =
 332         let val t1 = X.TEMP (Temp.new ("const lt") 4) in (munch_exp t1 e1 @ [X.CMP(t1, X.TEMP t)], X.G, X.LE) end
 333     | munch_cond (T.BINOP(T.LT, e1, T.TEMP t)) =
 334         let val t1 = X.TEMP (Temp.new ("const lt") 4) in (munch_exp t1 e1 @ [X.CMP(t1, X.TEMP t)], X.L, X.GE) end
 335     | munch_cond (T.BINOP(T.LT, e1, e2)) =
 336         let
 337           val t1 = X.TEMP (Temp.new ("var lt 1") 4)
 338           val t2 = X.TEMP (Temp.new ("var lt 2") 4)
 339         in
 340           (munch_exp t1 e1 @ munch_exp t2 e2 @
 341            [X.CMP(t1, t2)], X.L, X.GE)
 342         end
 343     | munch_cond (T.BINOP(T.GT, T.TEMP t, T.CONST n)) = ([X.CMP(X.TEMP t, X.CONST n)], X.G, X.LE)
 344     | munch_cond (T.BINOP(T.GT, T.CONST n, T.TEMP t)) = ([X.CMP(X.TEMP t, X.CONST n)], X.L, X.GE)
 345     | munch_cond (T.BINOP(T.GT, e1, T.CONST n)) =
 346         let val t = X.TEMP (Temp.new ("const gt") 4) in (munch_exp t e1 @ [X.CMP(t, X.CONST n)], X.G, X.LE) end
 347     | munch_cond (T.BINOP(T.GT, T.CONST n, e1)) =
 348         let val t = X.TEMP (Temp.new ("const gt") 4) in (munch_exp t e1 @ [X.CMP(t, X.CONST n)], X.L, X.GE) end
 349     | munch_cond (T.BINOP(T.GT, e1, T.TEMP t)) =
 350         let val t1 = X.TEMP (Temp.new ("const gt") 4) in (munch_exp t1 e1 @ [X.CMP(t1, X.TEMP t)], X.G, X.LE) end
 351     | munch_cond (T.BINOP(T.GT, T.TEMP t, e1)) =
 352         let val t1 = X.TEMP (Temp.new ("const gt") 4) in (munch_exp t1 e1 @ [X.CMP(t1, X.TEMP t)], X.L, X.GE) end
 353     | munch_cond (T.BINOP(T.GT, e1, e2)) =
 354         let
 355           val t1 = X.TEMP (Temp.new ("var gt 1") 4)
 356           val t2 = X.TEMP (Temp.new ("var gt 2") 4)
 357         in
 358           (munch_exp t1 e1 @ munch_exp t2 e2 @
 359            [X.CMP(t1, t2)], X.G, X.LE)
 360         end
 361     | munch_cond (T.BINOP(T.GE, T.TEMP t, T.CONST n)) = ([X.CMP(X.TEMP t, X.CONST n)], X.GE, X.L)
 362     | munch_cond (T.BINOP(T.GE, T.CONST n, T.TEMP t)) = ([X.CMP(X.TEMP t, X.CONST n)], X.LE, X.G)
 363     | munch_cond (T.BINOP(T.GE, e1, T.CONST n)) =
 364         let val t = X.TEMP (Temp.new ("const ge") 4) in (munch_exp t e1 @ [X.CMP(t, X.CONST n)], X.GE, X.L) end
 365     | munch_cond (T.BINOP(T.GE, T.CONST n, e1)) =
 366         let val t = X.TEMP (Temp.new ("const ge") 4) in (munch_exp t e1 @ [X.CMP(t, X.CONST n)], X.LE, X.G) end
 367     | munch_cond (T.BINOP(T.GE, e1, T.TEMP t)) =
 368         let val t1 = X.TEMP (Temp.new ("const ge") 4) in (munch_exp t1 e1 @ [X.CMP(t1, X.TEMP t)], X.GE, X.L) end
 369     | munch_cond (T.BINOP(T.GE, T.TEMP t, e1)) =
 370         let val t1 = X.TEMP (Temp.new ("const ge") 4) in (munch_exp t1 e1 @ [X.CMP(t1, X.TEMP t)], X.LE, X.G) end
 371     | munch_cond (T.BINOP(T.GE, e1, e2)) =
 372         let
 373           val t1 = X.TEMP (Temp.new ("var ge 1") 4)
 374           val t2 = X.TEMP (Temp.new ("var ge 2") 4)
 375         in
 376           (munch_exp t1 e1 @ munch_exp t2 e2 @
 377            [X.CMP(t1, t2)], X.GE, X.L)
 378         end
 379     | munch_cond (T.BINOP(T.LOGOR, e1, e2)) =
 380         let
 381           val (insn1, pos1, neg1) = munch_cond e1
 382           val (insn2, pos2, neg2) = munch_cond e2
 383           val t1 = X.TEMP (Temp.new("logor c 1") 4)
 384           val t2 = X.TEMP (Temp.new("logor c 2") 4)
 385           val l = Label.new ()
 386         in
 387           if (effect e2 orelse (length insn2 > 10))
 388           then ((insn1) @
 389                 [X.SETcc (pos1, t1), X.Jcc (pos1, l)] @
 390                 (insn2) @
 391                 [X.SETcc (pos2, t1), X.LABEL l, X.TEST(X.OSIZE (X.Byte, t1), X.OSIZE (X.Byte, t1))],
 392                 X.NE, X.E)
 393           else (insn1 @ [X.SETcc (pos1, t1)] @ insn2 @ [X.SETcc (pos2, t2), X.OR(X.OSIZE (X.Byte, t1), X.OSIZE (X.Byte, t2))], X.NE, X.E)
 394         end
 395     | munch_cond (T.BINOP(T.LOGAND, e1, e2)) =
 396         let
 397           val (insn1, pos1, neg1) = munch_cond e1
 398           val (insn2, pos2, neg2) = munch_cond e2
 399           val t1 = X.TEMP (Temp.new("logand c 1") 4)
 400           val t2 = X.TEMP (Temp.new("logand c 2") 4)
 401           val l = Label.new ()
 402         in
 403           if (effect e2 orelse (length insn2 > 10))
 404           then ((insn1) @
 405                 [X.SETcc (pos1, t1), X.Jcc (neg1, l)] @
 406                 (insn2) @
 407                 [X.SETcc (pos2, t1), X.LABEL l, X.TEST(X.OSIZE (X.Byte, t1), X.OSIZE (X.Byte, t1))],
 408                 X.NE, X.E)
 409           else (insn1 @ [X.SETcc (pos1, t1)] @ insn2 @ [X.SETcc (pos2, t2), X.AND(X.OSIZE (X.Byte, t1), X.OSIZE (X.Byte, t2))], X.NE, X.E)
 410         end
 411     | munch_cond e =
 412       let
 413         val t = X.TEMP (Temp.new ("munch c") 4)
 414       in
 415         (munch_exp t e @ [ X.TEST (t,t) ], X.NE, X.E)
 416       end
 417
 418   (* munch_lval : T.exp -> (X.insn list * X.operand)
 419    * Takes an expression that has been typechecked as being a valid lvalue, and then returns an instruction list and an operand to store your shit in.
 420    *)
 421   fun munch_lval (T.TEMP t) = ([], X.TEMP t)
 422     | munch_lval (T.MEMORY m) =
 423       let
 424         val t = Temp.new "lv addr" 8
 425       in
 426         (munch_exp (X.TEMP t) m, X.REL (X.TEMP t, X.CONST 0w0))
 427       end
 428     | munch_lval _ = raise ErrorMsg.InternalError "That wasn't really a valid lvalue..."
 429
 430   (* munch_stm : T.stm -> X.insn list *)
 431   (* munch_stm stm generates code to execute stm *)
 432   fun munch_stm (T.MOVE (T.TEMP t, a as T.TEMP _, _)) = munch_exp (X.TEMP t) a
 433     | munch_stm (T.MOVE (T.TEMP t, a as T.CONST _, _)) = munch_exp (X.TEMP t) a
 434     | munch_stm (T.MOVE (T.TEMP t, a as T.ARG (an, sz), _)) = munch_exp (X.TEMP t) a
 435     | munch_stm (T.MOVE (T.TEMP t, a as T.CALL _, _)) = munch_exp (X.TEMP t) a
 436     | munch_stm (T.MOVE (a, e2, sz)) =
 437         let
 438           val t = Temp.new ("assign") sz
 439           val (m, r) = munch_lval a
 440         in
 441           m @ munch_exp (X.TEMP t) e2
 442           @ [X.MOV(X.OSIZE (X.sts sz, r), X.TEMP t)]
 443         end
 444     | munch_stm (T.RETURN(e, sz)) =
 445         let
 446           val t = Temp.new ("retval") sz
 447         in
 448           munch_exp (X.TEMP t) e
 449           @ [X.MOV(X.OSIZE (X.sts sz, X.REG X.EAX), X.TEMP t), X.RET]
 450         end
 451     | munch_stm (T.LABEL(l)) = [X.LABEL l]
 452     | munch_stm (T.JUMP(l)) = [X.JMP l]
 453     | munch_stm (T.JUMPIFN(e, l)) =
 454        let
 455          val (insns, pos, neg) = munch_cond e
 456        in
 457          insns @ [X.Jcc (neg, l)]
 458        end
 459     | munch_stm (T.EFFECT(exp, sz)) = let val t = X.TEMP (Temp.new "throwaway" sz) in munch_exp t exp end
 460
 461   fun codegen nil = nil
 462     | codegen (stm::stms) = munch_stm stm @ codegen stms
 463 end