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/backpatch/vlBackPatch.sml
ViewVC logotype

Annotation of /sml/trunk/src/MLRISC/backpatch/vlBackPatch.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 984 - (view) (download)

1 : monnier 247 (* vlBackPatch.sml -- variable length back patching.
2 :     *
3 :     * Copyright 1999 by Bell Laboratories
4 :     *)
5 : george 976
6 :     (* NOTE on maxIter:
7 :     *
8 :     * maxIter -- is the number of times a span-dependent instruction
9 :     * is allowed to expand in a non-monotonic way.
10 :     *
11 :     * This table shows the number of span-dependent instructions
12 :     * whose size was over-estimated as a function of maxIter, for the
13 :     * file Parse/parse/ml.grm.sml:
14 :     *
15 :     * maxIter # of instructions:
16 :     * 10 687
17 :     * 20 438
18 :     * 30 198
19 :     * 40 0
20 :     *
21 :     * In compiling the compiler, there is no significant difference in
22 :     * compilation speed between maxIter=10 and maxIter=40.
23 :     * Indeed 96% of the files in the compiler reach a fix point within
24 :     * 13 iterations.
25 :     *)
26 : monnier 247 signature MC_EMIT = sig
27 :     structure I : INSTRUCTIONS
28 :    
29 : leunga 744 val emitInstr : I.instruction -> Word8Vector.vector
30 : monnier 247 end
31 :    
32 :    
33 :     functor BackPatch
34 :     (structure CodeString : CODE_STRING
35 : george 909 structure Jumps : SDI_JUMPS
36 :     structure Props : INSN_PROPERTIES
37 : george 976 where I = Jumps.I
38 : george 909 structure Emitter : MC_EMIT
39 : george 976 where I = Props.I
40 : george 909 structure CFG : CONTROL_FLOW_GRAPH
41 : george 976 where I = Emitter.I
42 :     structure Asm : INSTRUCTION_EMITTER
43 :     where I = CFG.I
44 : george 909 structure Placement : BLOCK_PLACEMENT
45 : george 976 where CFG = CFG) : BBSCHED =
46 : monnier 247 struct
47 : george 909 structure I = Jumps.I
48 :     structure C = I.C
49 :     structure CFG = CFG
50 :     structure P = CFG.P
51 :     structure G = Graph
52 : monnier 247 structure W8V = Word8Vector
53 :    
54 :     datatype desc =
55 :     BYTES of W8V.vector * desc
56 :     | PSEUDO of P.pseudo_op * desc
57 :     | SDI of I.instruction * int ref * desc
58 :     | LABEL of Label.label * desc
59 :     | NIL
60 :    
61 : leunga 744 datatype cluster = CLUSTER of {cluster: desc}
62 : monnier 247
63 : george 976 val maxIter = MLRiscControl.getInt "variable-length-backpatch-iterations"
64 :     val _ = maxIter := 40
65 :    
66 : monnier 411 fun error msg = MLRiscErrorMsg.error("vlBackPatch",msg)
67 : monnier 247
68 : george 984 val clusterList : cluster list ref = ref []
69 :     val dataList : P.pseudo_op list ref = ref []
70 :     fun cleanUp() = (clusterList := []; dataList := [])
71 : monnier 247
72 : george 909 val Asm.S.STREAM{emit,...} = Asm.makeStream []
73 :    
74 : george 984 fun bbsched(cfg as G.GRAPH{graph_info=CFG.INFO{data, ...}, ...}) = let
75 : george 909 val blocks = map #2 (Placement.blockPlacement cfg)
76 : monnier 247 fun bytes([], p) = p
77 :     | bytes([s], p) = BYTES(s, p)
78 :     | bytes(s, p) = BYTES(W8V.concat s, p)
79 : george 909
80 : george 984 fun f(CFG.BLOCK{align, labels, insns, ...}::rest) = let
81 : george 976 fun instrs([], b) = bytes(rev b, f rest)
82 :     | instrs(i::rest, b) =
83 :     if Jumps.isSdi i then
84 :     bytes(rev b, SDI(i, ref(Jumps.minSize i), instrs(rest, [])))
85 :     else
86 :     instrs(rest, Emitter.emitInstr(i)::b)
87 :     fun doLabels(lab::rest) = LABEL(lab, doLabels rest)
88 :     | doLabels [] = instrs(rev(!insns), [])
89 : george 984 fun alignIt(NONE) = doLabels(!labels)
90 :     | alignIt(SOME p) = PSEUDO(p, alignIt(NONE))
91 :     in
92 :     alignIt(!align)
93 : george 976 end
94 : monnier 247 | f [] = NIL
95 : george 909 in
96 : george 984 clusterList :=
97 :     CLUSTER{cluster=f blocks}:: !clusterList;
98 :     dataList := !data @ !dataList
99 : monnier 247 end
100 :    
101 : george 976
102 : monnier 247 fun finish() = let
103 : george 976 val iter = ref 0 (* iteration count *)
104 : monnier 247 fun labels (BYTES(s,rest), pos, chgd) = labels(rest, pos+W8V.length s, chgd)
105 : george 976 | labels (SDI(instr, r as ref size, rest), pos, chgd) =
106 :     let val s = Jumps.sdiSize(instr, Label.addrOf, pos)
107 :     (* Allow contraction in the first two passes;
108 :     * after which only allows expansion to ensure termination.
109 :     *)
110 :     in
111 :     if (!iter <= !maxIter andalso s <> size) orelse s > size then
112 :     (r := s; labels(rest, pos + s, true))
113 :     else labels(rest, pos + size, chgd)
114 :     end
115 : monnier 247 | labels (LABEL(l,rest), pos, changed) =
116 :     if Label.addrOf(l) = pos then labels(rest, pos, changed)
117 : george 976 else (Label.setAddr(l, pos); labels(rest, pos, true))
118 : monnier 247 | labels (PSEUDO(pOp, rest), pos, chgd) = let
119 : george 976 val oldSz = P.sizeOf(pOp, pos)
120 :     val newSz = (P.adjustLabels(pOp, pos); P.sizeOf(pOp, pos))
121 : monnier 247 in labels(rest, pos + newSz, chgd orelse newSz<>oldSz)
122 : george 976 end
123 : monnier 247 | labels (NIL, pos, chgd) = (pos, chgd)
124 :    
125 :     fun clusterLabels clusters = let
126 :     fun f (CLUSTER{cluster, ...}, (pos,chgd)) = labels(cluster, pos, chgd)
127 :     in List.foldl f (0, false) clusters
128 :     end
129 :    
130 :     val nop = Props.nop()
131 :    
132 :     val loc = ref 0
133 :    
134 :     fun output v =
135 :     W8V.app (fn v => (CodeString.update(!loc, v); loc:= !loc+1)) v
136 :    
137 : monnier 411
138 : monnier 247 fun chunk(pos, []) = ()
139 : leunga 744 | chunk(pos, CLUSTER{cluster}::rest) = let
140 :     fun outputInstr i = output (Emitter.emitInstr(nop))
141 : monnier 247 fun nops 0 = ()
142 : george 976 | nops n = (outputInstr(nop); nops(n-1))
143 :     fun f(pos, BYTES(s,r)) = (output s; f(pos+W8V.length s,r))
144 :     | f(pos, SDI(instr, ref size, r)) = let
145 :     val emitInstrs = map (fn i => Emitter.emitInstr(i))
146 :     val instrs = emitInstrs (Jumps.expand(instr, size, pos))
147 :     val sum = List.foldl (fn (a,b) => (W8V.length a + b)) 0
148 :     val n = size - sum instrs
149 : monnier 247 in
150 : george 976 (*
151 :     if n > 0 then
152 :     (print ("\t\t\t Inserting " ^ Int.toString n ^ "nops\n");
153 :     emit instr)
154 :     else ();
155 :     *)
156 :     app output instrs;
157 :     nops(n);
158 :     f(pos+size, r)
159 : monnier 247 end
160 : george 976 | f(pos, LABEL(lab, rest)) =
161 :     if pos = Label.addrOf lab then f(pos,rest)
162 :     else error "chunk: LABEL"
163 :     | f(pos, PSEUDO(pOp, rest)) = let
164 :     val s : Word8.word list ref = ref []
165 :     in
166 :     P.emitValue{pOp=pOp, loc=pos,
167 :     emit=(fn w => s := w :: (!s))};
168 :     output(W8V.fromList(rev(!s)));
169 :     f(pos + P.sizeOf(pOp, pos), rest)
170 :     end
171 :     | f(pos, NIL) = chunk(pos, rest)
172 : monnier 247
173 :     in f(pos, cluster)
174 : george 976 end
175 : monnier 247
176 :     fun fix clusters = let
177 :     val (pos, changed) = clusterLabels clusters
178 : george 909 in
179 : george 976 if changed then (iter := !iter + 1; fix clusters) else pos
180 : monnier 247 end
181 :    
182 : george 976 (*
183 :     * Initialize labels so that they have
184 :     * some reasonable value to begin with.
185 :     *)
186 :     fun initLabels (clusters) = let
187 :     fun init(BYTES(bytes, rest), loc) = init(rest, loc + W8V.length bytes)
188 :     | init(PSEUDO(pOp, rest), loc) =
189 :     (P.adjustLabels(pOp, loc); init(rest, loc + P.sizeOf(pOp, loc)))
190 :     | init(SDI(sdi, size, rest), loc) = init(rest, loc + !size)
191 :     | init(LABEL(lab, rest), loc) =
192 :     (Label.setAddr(lab, loc); init(rest, loc))
193 :     | init(NIL, loc) = loc
194 :     in
195 :     List.foldl
196 :     (fn (CLUSTER{cluster, ...}, loc) => init(cluster, loc)) 0 clusters
197 :     end
198 :    
199 : george 984 (* The dataList is in reverse order, and the entries in each
200 :     * are also in reverse
201 :     *)
202 :     fun compUnit(d::dl, cl, acc) = compUnit(dl, cl, PSEUDO(d, acc))
203 :     | compUnit([], cl, acc) = let
204 :     fun revCl(c::cl, acc) = revCl(cl, c::acc)
205 :     | revCl([], acc) = acc
206 :     in revCl(cl, [CLUSTER{cluster=acc}])
207 :     end
208 :    
209 :     val compressed = compUnit(!dataList, !clusterList, NIL) before cleanUp()
210 : monnier 247 in
211 : george 984 initLabels(compressed);
212 :     CodeString.init(fix compressed);
213 :     loc := 0; chunk(0, compressed)
214 : monnier 247 end (* finish *)
215 :    
216 :     end (* functor BackPatch *)
217 :    

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