codegen/solidify.sml

   1 (* L3 Compiler
   2  * Takes a list of mappings of temporaries to colors and a pseudoasm listing,
   3  * then produces x86 code.
   4  * Author: Chris Lu <czl@andrew.cmu.edu>
   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 *)
  29       val maxreg = X.regtonum X.R14D
  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)
  38             (List.filter (fn (a, _) => (Temp.eq (a, t))) regmap)))
  39
  40       fun temptoreg (t: T.temp) : x86.reg =
  41         numtoreg (temptonum t)
  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
  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 *)
  64         | isspilled (X.STACKARG _) = true
  65         | isspilled (X.REL _) = true
  66         | isspilled _ = false
  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
  84       fun spill (X.TEMP temp, xreg: x86.reg) =  (* Spill a register if need be. *)
  85         if (isspilled (X.TEMP temp))
  86           then [X.MOV (X.REL (X.RSP, stackpos (temptonum temp)), X.REG xreg)]
  87           else nil
  88         | spill (X.STACKARG _, _) = raise ErrorMsg.InternalError "Cannot spill to a stack arg"
  89         | spill (a as X.REL _, xreg) = [X.MOV (a, X.REG xreg)]
  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))
  93           then [X.MOV (X.REG xreg, X.REL (X.RSP, stackpos (temptonum temp)))]
  94           else nil
  95         | unspill (X.STACKARG arg, xreg) = [X.MOV (X.REG xreg, X.REL (X.RSP, stacksz + 8 + (arg * 8)))]
  96         | unspill (a as X.REL _, xreg) = [X.MOV (X.REG xreg, a)]
  97         | unspill _ = nil
  98
  99       fun realoper (X.TEMP temp) = X.REG (temptoreg temp)       (* Makes a operand 'real'. *)
 100         | realoper (X.STACKARG arg) = raise Spilled
 101         | realoper (X.REL _) = raise Spilled
 102         | realoper r = r
 103
 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))
 107         | stackoper (X.STACKARG arg) = X.REL (X.RSP, stacksz + 8 + (arg * 8))
 108         | stackoper (a as X.REL _) = a
 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]
 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)) =
 116             if (isspilled dest)
 117             then
 118               unspill (src, spillreg1) @
 119               [X.MOV(
 120                   realoper dest handle Spilled => stackoper dest,
 121                   realoper src handle Spilled => X.REG spillreg1)]
 122             else
 123               [X.MOV(
 124                   realoper dest handle Spilled => raise ErrorMsg.InternalError "But we said that wasn't spilled?",
 125                   realoper src handle Spilled => stackoper src)]
 126         | transform (X.SUB (dest, src)) =
 127             unspill (src, spillreg1) @
 128             [ X.SUB(
 129                 realoper dest handle Spilled => stackoper dest,
 130                 realoper src handle Spilled => X.REG spillreg1)]
 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)
 143         | transform (X.ADD (dest, src)) =       (* You can have either operand spilled, but not both. Pick one. *)
 144             if (isspilled dest)
 145             then
 146               unspill (src, spillreg1) @
 147               [ X.ADD(
 148                   realoper dest handle Spilled => stackoper dest,
 149                   realoper src handle Spilled => X.REG spillreg1)]
 150             else
 151               [ X.ADD(
 152                   realoper dest handle Spilled => raise ErrorMsg.InternalError "But we said that wasn't spilled?",
 153                   realoper src handle Spilled => stackoper src)]
 154         | transform (X.IDIV (src)) = [ X.IDIV(realoper src handle Spilled => stackoper src)]
 155         | transform (X.NEG (src)) = [ X.NEG(realoper src handle Spilled => stackoper src)]
 156         | transform (X.NOT (src)) = [ X.NOT(realoper src handle Spilled => stackoper src)]
 157         | transform (X.SAL (dest, shft)) =
 158             [ X.SAL (
 159                 realoper dest handle Spilled => stackoper dest,
 160                 shft)]
 161         | transform (X.SAR (dest, shft)) =
 162             [ X.SAR (
 163                 realoper dest handle Spilled => stackoper dest,
 164                 shft)]
 165         | transform (X.CLTD) = [ X.CLTD ]
 166         | transform (X.AND (dest, src)) =
 167             unspill (src, spillreg1) @
 168             [ X.AND(
 169                 realoper dest handle Spilled => stackoper dest,
 170                 realoper src handle Spilled => X.REG spillreg1)]
 171         | transform (X.OR (dest, src)) =
 172             unspill (src, spillreg1) @
 173             [ X.OR(
 174                 realoper dest handle Spilled => stackoper dest,
 175                 realoper src handle Spilled => X.REG spillreg1)]
 176         | transform (X.XOR (dest, src)) =
 177             unspill (src, spillreg1) @
 178             [ X.XOR(
 179                 realoper dest handle Spilled => stackoper dest,
 180                 realoper src handle Spilled => X.REG spillreg1)]
 181         | transform (X.CMP (op1, op2)) =
 182             unspill (op2, spillreg1) @
 183             [ X.CMP(
 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)]
 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(
 195                 realoper dest handle Spilled => X.REG spillreg1,
 196                 realoper src handle Spilled => stackoper src)]
 197             @ spill (dest, spillreg1)
 198         | transform (X.RET) = if nsave < 2 then (epilogue @ [X.RET]) else [X.JMP endlbl]
 199         | transform (X.LABEL l) = [ X.LABEL l ]
 200         | transform (X.JMP l) = [ X.JMP l ]
 201         | transform (X.Jcc (c,l)) = [X.Jcc (c,l)]
 202     in
 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]]))
 207     end
 208 end