| | 1 | (* L1 Compiler |
| | 2 | * Gathers tiberium, fires rockets |
| | 3 | * Turns pseudoasm into liveness-annotated pseudoasm |
| | 4 | * Author: Joshua Wise <jwise@andrew.cmu.edu> |
| | 5 | *) |
| | 6 | |
| | 7 | signature LIVENESS = |
| | 8 | sig |
| | 9 | type tiberium = x86.insn list |
| | 10 | type rockets = x86.oper list list |
| | 11 | |
| | 12 | val liveness : tiberium -> rockets |
| | 13 | end |
| | 14 | |
| | 15 | structure Liveness :> LIVENESS = |
| | 16 | struct |
| | 17 | structure T = Temp |
| | 18 | structure X = x86 |
| | 19 | |
| | 20 | type tiberium = x86.insn list |
| | 21 | type rockets = x86.oper list list |
| | 22 | |
| | 23 | (* This does not 'follow the rules'. |
| | 24 | * |
| | 25 | * Since this is a straight line, we can just fold starting at the right, |
| | 26 | * and accumulate variables. Thus, the accumulator has two parts: one to |
| | 27 | * represent all of the line / liveness pairs that we've accumulated so far; |
| | 28 | * and one to represent what was live at the previous line. |
| | 29 | *) |
| | 30 | fun mashinstr ((instr : x86.insn), (curtemps, output) : x86.oper list * rockets) : x86.oper list * rockets = |
| | 31 | let |
| | 32 | |
| | 33 | (* Removes an element from a list. *) |
| | 34 | fun blast (X.TEMP(elt)) l = |
| | 35 | List.filter (fn a => case a of X.TEMP(b) => (T.compare (b, elt)) <> EQUAL | _ => true) l |
| | 36 | | blast (X.REG(reg)) l = |
| | 37 | List.filter (fn a => case a of X.REG(b) => b <> reg | _ => true) l |
| | 38 | | blast _ l = raise ErrorMsg.InternalError "Why have we declared a CONST as live?" |
| | 39 | |
| | 40 | (* Adds an element to a list iff the element doesn't exist already. *) |
| | 41 | fun addonce (X.CONST(_)) l = l |
| | 42 | | addonce oper l = oper :: blast oper l |
| | 43 | |
| | 44 | val newtemps = |
| | 45 | case instr |
| | 46 | of X.DIRECTIVE(_) => curtemps |
| | 47 | | X.COMMENT(_) => curtemps |
| | 48 | | X.MOVL(dest, src) => addonce src (blast dest curtemps) |
| | 49 | | X.SUBL(dest, src) => addonce src (addonce dest curtemps) |
| | 50 | | X.IMUL(dest, src) => addonce src (addonce dest curtemps) |
| | 51 | | X.IMUL3(dest, src, _) => addonce src (blast dest curtemps) |
| | 52 | | X.ADDL(dest, src) => addonce src (addonce dest curtemps) |
| | 53 | | X.LEAL(dest, src1, src2) => addonce src1 (addonce src2 (blast dest curtemps)) |
| | 54 | | X.IDIVL(src) => addonce src (addonce (X.REG X.EAX) (addonce (X.REG X.EDX) curtemps)) |
| | 55 | | X.CLTD => blast (X.REG X.EDX) (addonce (X.REG X.EAX) curtemps) |
| | 56 | | X.NEG(src) => (* meh *) curtemps |
| | 57 | | X.RET => addonce (X.REG X.EAX) curtemps |
| | 58 | (* | _ => raise ErrorMsg.InternalError "Unable to compute liveness for unused instruction form";*) |
| | 59 | in |
| | 60 | (newtemps, newtemps :: output) |
| | 61 | end |
| | 62 | |
| | 63 | fun liveness (instrs : tiberium) : rockets = |
| | 64 | let |
| | 65 | val (_, livelist) = foldr mashinstr (nil, nil) instrs |
| | 66 | in |
| | 67 | livelist |
| | 68 | end |
| | 69 | end |
git.joshuawise.com / snipe.git / blame_incremental