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