codegen/solidify.sml

   1 (* L2 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.R13D
  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.compare (a, t) = EQUAL)) regmap)))
  39
  40       fun temptoreg (t: T.temp) : x86.reg =
  41         numtoreg (temptonum t)
  42         handle Empty =>
  43           (ErrorMsg.warn NONE ("Uncolored temp "^(Temp.name t)^" -- dead code?") ;
  44             X.R15D) (*If we don't care about the output, then it is cool to explode this; R15D is guaranteed not to be used across builtin blocks.*)
  45
  46       val spillreg1 = X.R14D
  47
  48       val prologue = [X.DIRECTIVE "\tpush %rbx\n\tpush %r12\n\tpush %r13\n\tpush %r14\n\tpush %r15"]    (* Could be done better. *)
  49       val epilogue = [X.DIRECTIVE "\tpop %r15\n\tpop %r14\n\tpop %r13\n\tpop %r12\n\tpop %rbx"]
  50
  51       val numreg = foldr (Int.max) 0 (map (fn (_, n) => n) regmap)      (* Number of registers used. *)
  52       val nspilled = Int.max (numreg - maxreg, 0)       (* Number of spilled registers. *)
  53       fun isspilled (X.TEMP temp) = (((temptonum temp) > maxreg) handle Empty => false) (* Whether a register is spilled *)
  54         | isspilled _ = false
  55       fun stackpos (reg: int) = (reg - maxreg) * ~4     (* Stack position of some register number *)
  56
  57       fun spill (X.TEMP temp, xreg: x86.reg) =  (* Spill a register if need be. *)
  58         if (isspilled (X.TEMP temp))
  59           then [X.MOVL (X.REL (X.RSP, stackpos (temptonum temp)), X.REG xreg)]
  60           else nil
  61         | spill _ = nil         (* Nothing else can be spilled. *)
  62       fun unspill (X.TEMP temp, xreg: x86.reg) =        (* Unspill a register if need be. *)
  63         if (isspilled (X.TEMP temp))
  64           then [X.MOVL (X.REG xreg, X.REL (X.RSP, stackpos (temptonum temp)))]
  65           else nil
  66         | unspill _ = nil
  67
  68       fun realoper (X.TEMP temp) = X.REG (temptoreg temp)       (* Makes a operand 'real'. *)
  69         | realoper r = r
  70       fun stackoper (X.TEMP temp) =
  71             if not (isspilled (X.TEMP temp)) then raise ErrorMsg.InternalError "stackoper on unspilled temp?"
  72             else X.REL (X.RSP, stackpos (temptonum temp))
  73         | stackoper _ = raise ErrorMsg.InternalError "stackoper on not temp?"
  74
  75       fun transform (X.DIRECTIVE s) = [X.DIRECTIVE s]
  76         | transform (X.COMMENT s) = [X.COMMENT s]
  77         | transform (X.MOVL (dest, src)) =
  78             if (isspilled dest)
  79             then
  80               unspill (src, spillreg1) @
  81               [ X.MOVL(
  82                   realoper dest handle Spilled => stackoper dest,
  83                   realoper src handle Spilled => X.REG spillreg1)]
  84             else
  85               [ X.MOVL(
  86                   realoper dest handle Spilled => raise ErrorMsg.InternalError "But we said that wasn't spilled?",
  87                   realoper src handle Spilled => stackoper src)]
  88         | transform (X.SUBL (dest, src)) =
  89             unspill (src, spillreg1) @
  90             [ X.SUBL(
  91                 realoper dest handle Spilled => stackoper dest,
  92                 realoper src handle Spilled => X.REG spillreg1)]
  93         | transform (X.IMUL (dest, src)) =
  94             unspill (dest, spillreg1) @
  95             [ X.IMUL(
  96                 realoper dest handle Spilled => X.REG spillreg1,
  97                 realoper src handle Spilled => stackoper src)] @
  98             spill (dest, spillreg1)
  99         | transform (X.IMUL3 (dest, src, const)) =
 100             [ X.IMUL3(
 101                 realoper dest handle Spilled => X.REG spillreg1,
 102                 realoper src handle Spilled => stackoper src,
 103                 const)] @
 104             spill (dest, spillreg1)
 105         | transform (X.ADDL (dest, src)) =      (* You can have either operand spilled, but not both. Pick one. *)
 106             if (isspilled dest)
 107             then
 108               unspill (src, spillreg1) @
 109               [ X.ADDL(
 110                   realoper dest handle Spilled => stackoper dest,
 111                   realoper src handle Spilled => X.REG spillreg1)]
 112             else
 113               [ X.ADDL(
 114                   realoper dest handle Spilled => raise ErrorMsg.InternalError "But we said that wasn't spilled?",
 115                   realoper src handle Spilled => stackoper src)]
 116         | transform (X.IDIVL (src)) = [ X.IDIVL(realoper src handle Spilled => stackoper src)]
 117         | transform (X.NEG (src)) = [ X.NEG(realoper src handle Spilled => stackoper src)]
 118         | transform (X.NOTL (src)) = [ X.NOTL(realoper src handle Spilled => stackoper src)]
 119         | transform (X.SALL (dest, shft)) =
 120             [ X.SALL (
 121                 realoper dest handle Spilled => stackoper dest,
 122                 shft)]
 123         | transform (X.SARL (dest, shft)) =
 124             [ X.SARL (
 125                 realoper dest handle Spilled => stackoper dest,
 126                 shft)]
 127         | transform (X.CLTD) = [ X.CLTD ]
 128         | transform (X.ANDL (dest, src)) =
 129             unspill (src, spillreg1) @
 130             [ X.ANDL(
 131                 realoper dest handle Spilled => stackoper dest,
 132                 realoper src handle Spilled => X.REG spillreg1)]
 133         | transform (X.ORL (dest, src)) =
 134             unspill (src, spillreg1) @
 135             [ X.ORL(
 136                 realoper dest handle Spilled => stackoper dest,
 137                 realoper src handle Spilled => X.REG spillreg1)]
 138         | transform (X.XORL (dest, src)) =
 139             unspill (src, spillreg1) @
 140             [ X.XORL(
 141                 realoper dest handle Spilled => stackoper dest,
 142                 realoper src handle Spilled => X.REG spillreg1)]
 143         | transform (X.CMPL (op1, op2)) =
 144             unspill (op2, spillreg1) @
 145             [ X.CMPL(
 146                 realoper op1 handle Spilled => stackoper op1,
 147                 realoper op2 handle Spilled => X.REG spillreg1)]
 148         | transform (X.TEST (op1, op2)) =
 149             unspill (op2, spillreg1) @
 150             [ X.TEST(
 151                 realoper op1 handle Spilled => stackoper op1,
 152                 realoper op2 handle Spilled => X.REG spillreg1)]
 153         | transform (X.SETNE (src)) = [ X.SETNE(realoper src handle Spilled => stackoper src)]
 154         | transform (X.SETE (src)) = [ X.SETE(realoper src handle Spilled => stackoper src)]
 155         | transform (X.SETLE (src)) = [ X.SETLE(realoper src handle Spilled => stackoper src)]
 156         | transform (X.SETL (src)) = [ X.SETL(realoper src handle Spilled => stackoper src)]
 157         | transform (X.SETGE (src)) = [ X.SETGE(realoper src handle Spilled => stackoper src)]
 158         | transform (X.SETG (src)) = [ X.SETG(realoper src handle Spilled => stackoper src)]
 159         | transform (X.MOVZBL (dest, src)) =
 160             [ X.MOVZBL(
 161                 realoper dest handle Spilled => X.REG spillreg1,
 162                 realoper src handle Spilled => stackoper src)]
 163             @ spill (dest, spillreg1)
 164         | transform (X.RET) = epilogue @ [X.RET]
 165         | transform (X.LABEL l) = [ X.LABEL l ]
 166         | transform (X.JMP l) = [ X.JMP l ]
 167         | transform (X.JE l) = [ X.JE l]
 168         | transform (X.JNE l) = [ X.JNE l]
 169 (*        | transform _ = raise ErrorMsg.InternalError ("Unimplemented transform")*)
 170     in
 171       List.concat (prologue :: (map transform instrs))
 172
 173     end
 174 end