Home My Page Projects Code Snippets Project Openings SML/NJ
Summary Activity Forums Tracker Lists Tasks Docs Surveys News SCM Files

SCM Repository

[smlnj] Annotation of /sml/trunk/src/MLRISC/SSA/ssa-instrgen.sml
ViewVC logotype

Annotation of /sml/trunk/src/MLRISC/SSA/ssa-instrgen.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 744 - (view) (download)

1 : leunga 695 (*
2 :     * This module is responsible for generating new instructions from
3 :     * MLTREE and inserting them into the SSA graph. This is useful for
4 :     * patching in new instructions as the SSA graph is being transformed.
5 :     *
6 :     * Special MLRISC Magic(tm) for invoking the instruction selection
7 :     * module and ssa-ifying the output code are all hidden here.
8 :     *
9 :     * -- Allen (leunga@cs.nyu.edu)
10 :     *
11 :     *)
12 :     functor SSAInstrGen(SSA : SSA) : SSA_INSTRGEN =
13 :     struct
14 :    
15 :     structure SSA = SSA
16 :     structure MLTreeComp = SSA.MLTreeComp
17 :     structure RTL = SSA.RTL
18 :     structure T = MLTreeComp.T
19 :     structure T' = RTL.T
20 :     structure S = T.Stream
21 :     structure SP = SSA.SP
22 :     structure P = SP.RTLProps
23 :     structure G = Graph
24 :     structure R = T.Region
25 :     structure A = Array
26 :     structure W8A = Word8Array
27 :    
28 :     fun error msg = MLRiscErrorMsg.error("SSAInstrGen", msg)
29 :    
30 :     exception Illegal
31 :    
32 :     (* Translate RTL mltree into the normal SSA form *)
33 :     fun translate SSA {defs,uses,rtl} =
34 :     let fun defOf(x) = List.nth(defs,x)
35 :     val const = SSA.const SSA
36 :     fun useOf(ty,x) =
37 :     let val v = List.nth(uses,x)
38 :     in if v < 0 then
39 :     (case const v of
40 : leunga 744 SP.OT.INT i => T.LI i
41 :     | SP.OT.INTINF i => T.LIInf i
42 : leunga 695 | SP.OT.OPERAND opnd => error "useOf"
43 :     )
44 :     else T.REG(ty,v)
45 :     end
46 : leunga 744 fun (* stm(T'.MV(ty,x,e)) = T.MV(ty,defOf x,rexp e)
47 :     | stm(T'.STORE(ty,a,b,mem)) = T.STORE(ty,rexp a,rexp b,R.memory)
48 :     | *) stm(T'.RTL{e, ...}) = stm e
49 : leunga 695 | stm s = error("stm: "^RTL.rtlToString s)
50 : leunga 744 and (* rexp(T'.REG(ty,x)) = useOf(ty, x)
51 : leunga 695 | rexp(T'.LI i) = T.LI i
52 :     | rexp(T'.LI32 i) = T.LI32 i
53 :     | rexp(T'.ADD(ty,a,b)) = T.ADD(ty,rexp a, rexp b)
54 :     | rexp(T'.SUB(ty,a,b)) = T.SUB(ty,rexp a, rexp b)
55 :     | rexp(T'.MULS(ty,a,b)) = T.MULS(ty,rexp a, rexp b)
56 :     | rexp(T'.DIVS(ty,a,b)) = T.DIVS(ty,rexp a, rexp b)
57 :     | rexp(T'.QUOTS(ty,a,b)) = T.QUOTS(ty,rexp a, rexp b)
58 :     | rexp(T'.REMS(ty,a,b)) = T.REMS(ty,rexp a, rexp b)
59 :     | rexp(T'.MULU(ty,a,b)) = T.MULU(ty,rexp a, rexp b)
60 :     | rexp(T'.DIVU(ty,a,b)) = T.DIVU(ty,rexp a, rexp b)
61 :     | rexp(T'.REMU(ty,a,b)) = T.REMU(ty,rexp a, rexp b)
62 :     | rexp(T'.ADDT(ty,a,b)) = T.ADDT(ty,rexp a, rexp b)
63 :     | rexp(T'.SUBT(ty,a,b)) = T.SUBT(ty,rexp a, rexp b)
64 :     | rexp(T'.MULT(ty,a,b)) = T.MULT(ty,rexp a, rexp b)
65 :     | rexp(T'.DIVT(ty,a,b)) = T.DIVT(ty,rexp a, rexp b)
66 :     | rexp(T'.QUOTT(ty,a,b)) = T.QUOTT(ty,rexp a, rexp b)
67 :     | rexp(T'.REMT(ty,a,b)) = T.REMT(ty,rexp a, rexp b)
68 :     | rexp(T'.ANDB(ty,a,b)) = T.ANDB(ty,rexp a, rexp b)
69 :     | rexp(T'.ORB(ty,a,b)) = T.ORB(ty,rexp a, rexp b)
70 :     | rexp(T'.XORB(ty,a,b)) = T.XORB(ty,rexp a, rexp b)
71 :     | rexp(T'.NOTB(ty,a)) = T.NOTB(ty,rexp a)
72 :     | rexp(T'.SRA(ty,a,b)) = T.SRA(ty,rexp a,rexp b)
73 :     | rexp(T'.SRL(ty,a,b)) = T.SRL(ty,rexp a,rexp b)
74 :     | rexp(T'.SLL(ty,a,b)) = T.SLL(ty,rexp a,rexp b)
75 :     | rexp(T'.CVTI2I(ty,ext,ty',a)) = T.CVTI2I(ty,ext,ty',rexp a)
76 : leunga 744 | rexp(T'.LOAD(ty,a,mem)) = T.LOAD(ty,rexp a,R.memory)
77 :     | *) rexp e = error("rexp: "^RTL.expToString e)
78 : leunga 695 in stm rtl end
79 :    
80 :     (*
81 :     * Translate mltree into instructions
82 :     *)
83 :     fun instrGen (SSA as G.GRAPH ssa) =
84 :     let val instrs = ref []
85 :     fun emit i = instrs := i :: !instrs
86 :     fun can'tUse _ = raise Illegal
87 :     val instrStream =
88 :     S.STREAM
89 :     { beginCluster = can'tUse,
90 :     endCluster = can'tUse,
91 :     emit = emit,
92 :     pseudoOp = can'tUse,
93 :     defineLabel = can'tUse,
94 :     entryLabel = can'tUse,
95 :     comment = can'tUse,
96 :     annotation = can'tUse,
97 : leunga 744 exitBlock = can'tUse
98 : leunga 695 }
99 :    
100 :     val S.STREAM{emit, ...} = MLTreeComp.selectInstructions instrStream
101 :    
102 :     (* Translate instructions into SSA form *)
103 :     fun translate instrs = ()
104 :    
105 :     (* Generate instructions *)
106 :     fun gen mltree =
107 :     (instrs := [];
108 :     emit mltree;
109 :     rev(!instrs)
110 :     )
111 :    
112 :     in gen
113 :     end
114 :    
115 :     (*
116 :     * Replace the instruction with a new mltree
117 :     *)
118 :     fun replace (SSA as G.GRAPH ssa) =
119 :     let val instrGen = instrGen SSA
120 :     val ssaOpTbl = SSA.ssaOpTbl SSA
121 :     fun doit{id, mltree} =
122 :     case instrGen mltree of
123 :     [i] => (A.update(ssaOpTbl, id, i); true)
124 :     | _ => false
125 :     in doit
126 :     end
127 :    
128 :     (*
129 :     * Insert instructions into the SSA graph
130 :     *)
131 :     fun insert (SSA as G.GRAPH ssa) =
132 :     let val getOperands =
133 : leunga 744 P.defUse(SP.OT.makeNewValueNumbers(SSA.operandTbl SSA))
134 : leunga 695 val pinnedUseTbl = SSA.pinnedUseTbl
135 :     val pinnedDefTbl = SSA.pinnedDefTbl
136 :     fun isPinnedUse r = W8A.sub(pinnedUseTbl,r) <> 0w0 handle _ => false
137 :     fun isPinnedDef r = W8A.sub(pinnedDefTbl,r) <> 0w0 handle _ => false
138 :     fun hasPinnedUse [] = false
139 :     | hasPinnedUse (r::rs) = isPinnedUse r orelse hasPinnedUse rs
140 :     fun hasPinnedDef [] = false
141 :     | hasPinnedDef (r::rs) = isPinnedDef r orelse hasPinnedDef rs
142 :    
143 :     fun isZero r = W8A.sub(SSA.zeroRegs,r) <> 0w0 handle _ => false
144 :    
145 :     val renameVar = SSA.newRenamedVar SSA
146 :    
147 :     exception Renaming
148 : leunga 744 val renameMap = IntHashTable.mkTable(32, Renaming)
149 :     val lookupRenaming = IntHashTable.lookup renameMap
150 :     val addRenaming = IntHashTable.insert renameMap
151 : leunga 695
152 :     fun addInstrs(block, instrs) =
153 :     let val n = length instrs
154 :     val m = #capacity ssa ()
155 :     val _ = SSA.reserve SSA (n+m)
156 :     val newOp = SSA.newOp SSA
157 :    
158 :     fun renameUse v = if v < 0 then v else lookupRenaming v
159 :     fun renameDef v =
160 :     let val v' = renameVar v
161 :     in if isZero v then v'
162 :     else (addRenaming(v,v'); v')
163 :     end
164 :    
165 :     fun scan([], id, pos) = ()
166 :     | scan(instr::rest, id, pos) =
167 :     let val (defs, uses) = getOperands instr
168 :     val rtl = P.rtl instr
169 :     val rtl = if hasPinnedUse uses orelse
170 :     hasPinnedDef defs then
171 :     RTL.pin rtl else rtl
172 :     val uses = map renameUse uses
173 :     val defs = map renameDef defs
174 :     in newOp{id=id, instr=instr, pos=pos, rtl=rtl,
175 :     block=block, defs=defs, uses=uses};
176 :     scan(rest, id+1, pos+128)
177 :     end
178 :     in scan(instrs, m, 0 (* XXX *))
179 :     end
180 :     in ()
181 :     end
182 :    
183 :     end

root@smlnj-gforge.cs.uchicago.edu
ViewVC Help
Powered by ViewVC 1.0.0