[snipe.git] / codegen / solidify.sml

(* L3 Compiler
 * Takes a list of mappings of temporaries to colors and a pseudoasm listing,
 * then produces x86 code.
 * Author: Chris Lu <czl@andrew.cmu.edu>
 * Author: Joshua Wise <jwise@andrew.cmu.edu>
 *)

signature SOLIDIFY =
sig
  type colorings = (Temp.temp * int) list
  type asm = x86.insn list
  
  val solidify : colorings -> asm -> asm
end

structure Solidify :> SOLIDIFY =
struct
  structure X = x86
  structure T = Temp
  
  type colorings = (Temp.temp * int) list
  type asm = x86.insn list
  
  exception Spilled
  
  fun solidify (regmap : colorings) (instrs : asm) : asm =
    let
      (* r14d and r15d is reserved for spilling *)
      val maxreg = X.regtonum X.R14D
      fun numtoreg n =
          if (n > maxreg)
          then raise Spilled
          else X.numtoreg n
      
      fun temptonum (t: T.temp) : int =
        (List.hd
          (List.map (fn (_, n) => n)
            (List.filter (fn (a, _) => (Temp.eq (a, t))) regmap)))
      
      fun temptoreg (t: T.temp) : x86.reg =
        numtoreg (temptonum t)          
        handle Empty => raise ErrorMsg.InternalError ("Uncolored temp "^(Temp.name t)^", agh!")

      val spillreg1 = X.R15D

      (* Determine which need to be saved. *)
      val opsused = map (fn (_, n) => X.REG (numtoreg n handle Spilled => X.R15D)) regmap
      val saveregs = X.OperSet.intersection (
        X.OperSet.addList (X.OperSet.empty, opsused),
        X.OperSet.addList (
          X.OperSet.empty,
          [X.REG X.EBX,
           X.REG X.EBP,
           X.REG X.R12D,
           X.REG X.R13D,
           X.REG X.R14D,
           X.REG X.R15D]))
      val savelist = X.OperSet.listItems saveregs
      val nsave = length savelist

      val numreg = foldr (Int.max) 0 (map (fn (_, n) => n) regmap)	(* Number of registers used. *)
      val nspilled = Int.max (numreg - maxreg, 0)	(* Number of spilled registers. *)
      fun isspilled (X.TEMP temp) = (((temptonum temp) > maxreg) handle Empty => false)	(* Whether a register is spilled *)
        | isspilled (X.STACKARG _) = true
        | isspilled (X.REL _) = true
        | isspilled _ = false
      val stacksz = (nspilled + nsave) * 8
      fun stackpos (reg: int) = stacksz - (reg - maxreg + nsave) * 8	(* Stack position of some register number *)

      val prologue =
        (X.SIZE (X.Qword, X.SUB (X.REG X.RSP, X.CONST (Word32.fromInt stacksz)))) ::
        (ListPair.map
          (fn (num, reg) =>
            X.SIZE (X.Qword, X.MOV (X.REL (X.RSP, stacksz - 8*(num+1)), reg)))
          (List.tabulate (nsave, fn x => x), savelist))
      val epilogue =
        (ListPair.map
          (fn (num, reg) =>
            X.SIZE (X.Qword, X.MOV (reg, X.REL (X.RSP, stacksz - 8*(num+1)))))
          (List.tabulate (nsave, fn x => x), savelist)) @
        [X.SIZE (X.Qword, X.ADD (X.REG X.RSP, X.CONST (Word32.fromInt stacksz)))]
      val endlbl = Label.new()

      fun spill (X.TEMP temp, xreg: x86.reg) =	(* Spill a register if need be. *)
        if (isspilled (X.TEMP temp))
          then [X.MOV (X.REL (X.RSP, stackpos (temptonum temp)), X.REG xreg)]
          else nil
        | spill (X.STACKARG _, _) = raise ErrorMsg.InternalError "Cannot spill to a stack arg"
        | spill (a as X.REL _, xreg) = [X.MOV (a, X.REG xreg)]
        | spill _ = nil		(* Nothing else can be spilled. *)
      fun unspill (X.TEMP temp, xreg: x86.reg) =	(* Unspill a register if need be. *)
        if (isspilled (X.TEMP temp))
          then [X.MOV (X.REG xreg, X.REL (X.RSP, stackpos (temptonum temp)))]
          else nil
        | unspill (X.STACKARG arg, xreg) = [X.MOV (X.REG xreg, X.REL (X.RSP, stacksz + 8 + (arg * 8)))]
        | unspill (a as X.REL _, xreg) = [X.MOV (X.REG xreg, a)]
        | unspill _ = nil
      
      fun realoper (X.TEMP temp) = X.REG (temptoreg temp)	(* Makes a operand 'real'. *)
        | realoper (X.STACKARG arg) = raise Spilled
        | realoper (X.REL _) = raise Spilled
        | realoper r = r

      fun stackoper (X.TEMP temp) =
            if not (isspilled (X.TEMP temp)) then raise ErrorMsg.InternalError "stackoper on unspilled temp?"
            else X.REL (X.RSP, stackpos (temptonum temp))
        | stackoper (X.STACKARG arg) = X.REL (X.RSP, stacksz + 8 + (arg * 8))
        | stackoper (a as X.REL _) = a
        | stackoper _ = raise ErrorMsg.InternalError "stackoper on not temp?"
      
      fun transform (X.DIRECTIVE s) = [X.DIRECTIVE s]
        | transform (X.COMMENT s) = [X.COMMENT s]
        | transform (X.LIVEIGN a) = transform a
        | transform (X.SIZE (s, i)) = map (fn i' => (X.SIZE (s, i'))) (transform i)
        | transform (X.MOV (dest, src)) =
            if (isspilled dest)
            then
              unspill (src, spillreg1) @
              [X.MOV(
                  realoper dest handle Spilled => stackoper dest,
                  realoper src handle Spilled => X.REG spillreg1)]
            else
              [X.MOV(
                  realoper dest handle Spilled => raise ErrorMsg.InternalError "But we said that wasn't spilled?",
                  realoper src handle Spilled => stackoper src)]
        | transform (X.SUB (dest, src)) =
            unspill (src, spillreg1) @
            [ X.SUB(
                realoper dest handle Spilled => stackoper dest,
                realoper src handle Spilled => X.REG spillreg1)]
        | transform (X.IMUL (dest, src)) =
            unspill (dest, spillreg1) @
            [ X.IMUL(
                realoper dest handle Spilled => X.REG spillreg1,
                realoper src handle Spilled => stackoper src)] @
            spill (dest, spillreg1)
        | transform (X.IMUL3 (dest, src, const)) =
            [ X.IMUL3(
                realoper dest handle Spilled => X.REG spillreg1,
                realoper src handle Spilled => stackoper src,
                const)] @
            spill (dest, spillreg1)
        | transform (X.ADD (dest, src)) =	(* You can have either operand spilled, but not both. Pick one. *)
            if (isspilled dest)
            then
              unspill (src, spillreg1) @
              [ X.ADD(
                  realoper dest handle Spilled => stackoper dest,
                  realoper src handle Spilled => X.REG spillreg1)]
            else
              [ X.ADD(
                  realoper dest handle Spilled => raise ErrorMsg.InternalError "But we said that wasn't spilled?",
                  realoper src handle Spilled => stackoper src)]
        | transform (X.IDIV (src)) = [ X.IDIV(realoper src handle Spilled => stackoper src)]
        | transform (X.NEG (src)) = [ X.NEG(realoper src handle Spilled => stackoper src)]
        | transform (X.NOT (src)) = [ X.NOT(realoper src handle Spilled => stackoper src)]
        | transform (X.SAL (dest, shft)) =
            [ X.SAL (
                realoper dest handle Spilled => stackoper dest,
                shft)]
        | transform (X.SAR (dest, shft)) =
            [ X.SAR (
                realoper dest handle Spilled => stackoper dest,
                shft)]
        | transform (X.CLTD) = [ X.CLTD ]
        | transform (X.AND (dest, src)) =
            unspill (src, spillreg1) @
            [ X.AND(
                realoper dest handle Spilled => stackoper dest,
                realoper src handle Spilled => X.REG spillreg1)]
        | transform (X.OR (dest, src)) =
            unspill (src, spillreg1) @
            [ X.OR(
                realoper dest handle Spilled => stackoper dest,
                realoper src handle Spilled => X.REG spillreg1)]
        | transform (X.XOR (dest, src)) =
            unspill (src, spillreg1) @
            [ X.XOR(
                realoper dest handle Spilled => stackoper dest,
                realoper src handle Spilled => X.REG spillreg1)]
        | transform (X.CMP (op1, op2)) =
            unspill (op2, spillreg1) @
            [ X.CMP(
                realoper op1 handle Spilled => stackoper op1,
                realoper op2 handle Spilled => X.REG spillreg1)]
        | transform (X.TEST (op1, op2)) =
            unspill (op2, spillreg1) @
            [ X.TEST(
                realoper op1 handle Spilled => stackoper op1,
                realoper op2 handle Spilled => X.REG spillreg1)]
        | transform (X.SETcc (c,src)) = [ X.SETcc(c, realoper src handle Spilled => stackoper src)]
        | transform (X.CALL l) = [ X.CALL l ]
        | transform (X.MOVZB (dest, src)) =
            [ X.MOVZB(
                realoper dest handle Spilled => X.REG spillreg1,
                realoper src handle Spilled => stackoper src)]
            @ spill (dest, spillreg1)
        | transform (X.RET) = if nsave < 2 then (epilogue @ [X.RET]) else [X.JMP endlbl]
        | transform (X.LABEL l) = [ X.LABEL l ]
        | transform (X.JMP l) = [ X.JMP l ]
        | transform (X.Jcc (c,l)) = [X.Jcc (c,l)]
    in
      if (nsave < 2) then
        List.concat (prologue :: (map transform instrs))
      else
        List.concat (prologue :: ((map transform instrs) @ [[X.LABEL endlbl], epilogue, [X.RET]]))
    end
end
Commit	Line	Data
6ade8b0a	1	(* L3 Compiler
12aa4087 JW	2	* Takes a list of mappings of temporaries to colors and a pseudoasm listing,
12aa4087 JW	3	* then produces x86 code.
0a24e44d	4	* Author: Chris Lu <czl@andrew.cmu.edu>
12aa4087 JW	5	* Author: Joshua Wise <jwise@andrew.cmu.edu>
	6	*)
	7
	8	signature SOLIDIFY =
	9	sig
	10	type colorings = (Temp.temp * int) list
	11	type asm = x86.insn list
	12
	13	val solidify : colorings -> asm -> asm
	14	end
	15
	16	structure Solidify :> SOLIDIFY =
	17	struct
	18	structure X = x86
	19	structure T = Temp
	20
	21	type colorings = (Temp.temp * int) list
	22	type asm = x86.insn list
	23
	24	exception Spilled
	25
	26	fun solidify (regmap : colorings) (instrs : asm) : asm =
	27	let
	28	(* r14d and r15d is reserved for spilling *)
6ade8b0a	29	val maxreg = X.regtonum X.R14D
12aa4087 JW	30	fun numtoreg n =
	31	if (n > maxreg)
	32	then raise Spilled
	33	else X.numtoreg n
	34
	35	fun temptonum (t: T.temp) : int =
	36	(List.hd
	37	(List.map (fn (_, n) => n)
6ade8b0a	38	(List.filter (fn (a, _) => (Temp.eq (a, t))) regmap)))
12aa4087 JW	39
	40	fun temptoreg (t: T.temp) : x86.reg =
	41	numtoreg (temptonum t)
6ade8b0a JW	42	handle Empty => raise ErrorMsg.InternalError ("Uncolored temp "^(Temp.name t)^", agh!")
	43
	44	val spillreg1 = X.R15D
	45
	46	(* Determine which need to be saved. *)
	47	val opsused = map (fn (_, n) => X.REG (numtoreg n handle Spilled => X.R15D)) regmap
	48	val saveregs = X.OperSet.intersection (
	49	X.OperSet.addList (X.OperSet.empty, opsused),
	50	X.OperSet.addList (
	51	X.OperSet.empty,
	52	[X.REG X.EBX,
	53	X.REG X.EBP,
	54	X.REG X.R12D,
	55	X.REG X.R13D,
	56	X.REG X.R14D,
	57	X.REG X.R15D]))
	58	val savelist = X.OperSet.listItems saveregs
	59	val nsave = length savelist
	60
12aa4087 JW	61	val numreg = foldr (Int.max) 0 (map (fn (_, n) => n) regmap) (* Number of registers used. *)
	62	val nspilled = Int.max (numreg - maxreg, 0) (* Number of spilled registers. *)
	63	fun isspilled (X.TEMP temp) = (((temptonum temp) > maxreg) handle Empty => false) (* Whether a register is spilled *)
6ade8b0a JW	64	\| isspilled (X.STACKARG _) = true
6ade8b0a JW	65	\| isspilled (X.REL _) = true
12aa4087	66	\| isspilled _ = false
6ade8b0a JW	67	val stacksz = (nspilled + nsave) * 8
	68	fun stackpos (reg: int) = stacksz - (reg - maxreg + nsave) * 8 (* Stack position of some register number *)
	69
	70	val prologue =
	71	(X.SIZE (X.Qword, X.SUB (X.REG X.RSP, X.CONST (Word32.fromInt stacksz)))) ::
	72	(ListPair.map
	73	(fn (num, reg) =>
	74	X.SIZE (X.Qword, X.MOV (X.REL (X.RSP, stacksz - 8*(num+1)), reg)))
	75	(List.tabulate (nsave, fn x => x), savelist))
	76	val epilogue =
	77	(ListPair.map
	78	(fn (num, reg) =>
	79	X.SIZE (X.Qword, X.MOV (reg, X.REL (X.RSP, stacksz - 8*(num+1)))))
	80	(List.tabulate (nsave, fn x => x), savelist)) @
	81	[X.SIZE (X.Qword, X.ADD (X.REG X.RSP, X.CONST (Word32.fromInt stacksz)))]
	82	val endlbl = Label.new()
	83
12aa4087 JW	84	fun spill (X.TEMP temp, xreg: x86.reg) = (* Spill a register if need be. *)
12aa4087 JW	85	if (isspilled (X.TEMP temp))
6ade8b0a	86	then [X.MOV (X.REL (X.RSP, stackpos (temptonum temp)), X.REG xreg)]
12aa4087	87	else nil
6ade8b0a JW	88	\| spill (X.STACKARG _, _) = raise ErrorMsg.InternalError "Cannot spill to a stack arg"
6ade8b0a JW	89	\| spill (a as X.REL _, xreg) = [X.MOV (a, X.REG xreg)]
12aa4087 JW	90	\| spill _ = nil (* Nothing else can be spilled. *)
	91	fun unspill (X.TEMP temp, xreg: x86.reg) = (* Unspill a register if need be. *)
	92	if (isspilled (X.TEMP temp))
6ade8b0a	93	then [X.MOV (X.REG xreg, X.REL (X.RSP, stackpos (temptonum temp)))]
12aa4087	94	else nil
6ade8b0a JW	95	\| unspill (X.STACKARG arg, xreg) = [X.MOV (X.REG xreg, X.REL (X.RSP, stacksz + 8 + (arg * 8)))]
6ade8b0a JW	96	\| unspill (a as X.REL _, xreg) = [X.MOV (X.REG xreg, a)]
12aa4087 JW	97	\| unspill _ = nil
	98
	99	fun realoper (X.TEMP temp) = X.REG (temptoreg temp) (* Makes a operand 'real'. *)
6ade8b0a JW	100	\| realoper (X.STACKARG arg) = raise Spilled
6ade8b0a JW	101	\| realoper (X.REL _) = raise Spilled
12aa4087	102	\| realoper r = r
6ade8b0a	103
12aa4087 JW	104	fun stackoper (X.TEMP temp) =
	105	if not (isspilled (X.TEMP temp)) then raise ErrorMsg.InternalError "stackoper on unspilled temp?"
	106	else X.REL (X.RSP, stackpos (temptonum temp))
6ade8b0a JW	107	\| stackoper (X.STACKARG arg) = X.REL (X.RSP, stacksz + 8 + (arg * 8))
6ade8b0a JW	108	\| stackoper (a as X.REL _) = a
12aa4087 JW	109	\| stackoper _ = raise ErrorMsg.InternalError "stackoper on not temp?"
	110
	111	fun transform (X.DIRECTIVE s) = [X.DIRECTIVE s]
	112	\| transform (X.COMMENT s) = [X.COMMENT s]
6ade8b0a JW	113	\| transform (X.LIVEIGN a) = transform a
	114	\| transform (X.SIZE (s, i)) = map (fn i' => (X.SIZE (s, i'))) (transform i)
	115	\| transform (X.MOV (dest, src)) =
12aa4087 JW	116	if (isspilled dest)
	117	then
	118	unspill (src, spillreg1) @
6ade8b0a	119	[X.MOV(
12aa4087 JW	120	realoper dest handle Spilled => stackoper dest,
	121	realoper src handle Spilled => X.REG spillreg1)]
	122	else
6ade8b0a	123	[X.MOV(
12aa4087 JW	124	realoper dest handle Spilled => raise ErrorMsg.InternalError "But we said that wasn't spilled?",
12aa4087 JW	125	realoper src handle Spilled => stackoper src)]
6ade8b0a	126	\| transform (X.SUB (dest, src)) =
12aa4087	127	unspill (src, spillreg1) @
6ade8b0a	128	[ X.SUB(
0a24e44d JW	129	realoper dest handle Spilled => stackoper dest,
0a24e44d JW	130	realoper src handle Spilled => X.REG spillreg1)]
12aa4087 JW	131	\| transform (X.IMUL (dest, src)) =
	132	unspill (dest, spillreg1) @
	133	[ X.IMUL(
	134	realoper dest handle Spilled => X.REG spillreg1,
	135	realoper src handle Spilled => stackoper src)] @
	136	spill (dest, spillreg1)
	137	\| transform (X.IMUL3 (dest, src, const)) =
	138	[ X.IMUL3(
	139	realoper dest handle Spilled => X.REG spillreg1,
	140	realoper src handle Spilled => stackoper src,
	141	const)] @
	142	spill (dest, spillreg1)
6ade8b0a	143	\| transform (X.ADD (dest, src)) = (* You can have either operand spilled, but not both. Pick one. *)
12aa4087 JW	144	if (isspilled dest)
	145	then
	146	unspill (src, spillreg1) @
6ade8b0a	147	[ X.ADD(
12aa4087 JW	148	realoper dest handle Spilled => stackoper dest,
	149	realoper src handle Spilled => X.REG spillreg1)]
	150	else
6ade8b0a	151	[ X.ADD(
12aa4087 JW	152	realoper dest handle Spilled => raise ErrorMsg.InternalError "But we said that wasn't spilled?",
12aa4087 JW	153	realoper src handle Spilled => stackoper src)]
6ade8b0a	154	\| transform (X.IDIV (src)) = [ X.IDIV(realoper src handle Spilled => stackoper src)]
12aa4087	155	\| transform (X.NEG (src)) = [ X.NEG(realoper src handle Spilled => stackoper src)]
6ade8b0a JW	156	\| transform (X.NOT (src)) = [ X.NOT(realoper src handle Spilled => stackoper src)]
	157	\| transform (X.SAL (dest, shft)) =
	158	[ X.SAL (
0a24e44d JW	159	realoper dest handle Spilled => stackoper dest,
0a24e44d JW	160	shft)]
6ade8b0a JW	161	\| transform (X.SAR (dest, shft)) =
6ade8b0a JW	162	[ X.SAR (
0a24e44d JW	163	realoper dest handle Spilled => stackoper dest,
0a24e44d JW	164	shft)]
12aa4087	165	\| transform (X.CLTD) = [ X.CLTD ]
6ade8b0a	166	\| transform (X.AND (dest, src)) =
0a24e44d	167	unspill (src, spillreg1) @
6ade8b0a	168	[ X.AND(
0a24e44d JW	169	realoper dest handle Spilled => stackoper dest,
0a24e44d JW	170	realoper src handle Spilled => X.REG spillreg1)]
6ade8b0a	171	\| transform (X.OR (dest, src)) =
0a24e44d	172	unspill (src, spillreg1) @
6ade8b0a	173	[ X.OR(
0a24e44d JW	174	realoper dest handle Spilled => stackoper dest,
0a24e44d JW	175	realoper src handle Spilled => X.REG spillreg1)]
6ade8b0a	176	\| transform (X.XOR (dest, src)) =
0a24e44d	177	unspill (src, spillreg1) @
6ade8b0a	178	[ X.XOR(
0a24e44d JW	179	realoper dest handle Spilled => stackoper dest,
0a24e44d JW	180	realoper src handle Spilled => X.REG spillreg1)]
6ade8b0a	181	\| transform (X.CMP (op1, op2)) =
0a24e44d	182	unspill (op2, spillreg1) @
6ade8b0a	183	[ X.CMP(
0a24e44d JW	184	realoper op1 handle Spilled => stackoper op1,
	185	realoper op2 handle Spilled => X.REG spillreg1)]
	186	\| transform (X.TEST (op1, op2)) =
	187	unspill (op2, spillreg1) @
	188	[ X.TEST(
	189	realoper op1 handle Spilled => stackoper op1,
	190	realoper op2 handle Spilled => X.REG spillreg1)]
6ade8b0a JW	191	\| transform (X.SETcc (c,src)) = [ X.SETcc(c, realoper src handle Spilled => stackoper src)]
	192	\| transform (X.CALL l) = [ X.CALL l ]
	193	\| transform (X.MOVZB (dest, src)) =
	194	[ X.MOVZB(
0a24e44d JW	195	realoper dest handle Spilled => X.REG spillreg1,
	196	realoper src handle Spilled => stackoper src)]
	197	@ spill (dest, spillreg1)
6ade8b0a	198	\| transform (X.RET) = if nsave < 2 then (epilogue @ [X.RET]) else [X.JMP endlbl]
0a24e44d JW	199	\| transform (X.LABEL l) = [ X.LABEL l ]
0a24e44d JW	200	\| transform (X.JMP l) = [ X.JMP l ]
6ade8b0a	201	\| transform (X.Jcc (c,l)) = [X.Jcc (c,l)]
12aa4087	202	in
6ade8b0a JW	203	if (nsave < 2) then
	204	List.concat (prologue :: (map transform instrs))
	205	else
	206	List.concat (prologue :: ((map transform instrs) @ [[X.LABEL endlbl], epilogue, [X.RET]]))
12aa4087 JW	207	end
12aa4087 JW	208	end