Commit | Line | Data |
---|---|---|
7f918cf1 CE |
1 | (* Copyright (C) 1999-2006 Henry Cejtin, Matthew Fluet, Suresh |
2 | * Jagannathan, and Stephen Weeks. | |
3 | * Copyright (C) 1997-2000 NEC Research Institute. | |
4 | * | |
5 | * MLton is released under a BSD-style license. | |
6 | * See the file MLton-LICENSE for details. | |
7 | *) | |
8 | ||
9 | functor Chunkify (S: CHUNKIFY_STRUCTS): CHUNKIFY = | |
10 | struct | |
11 | ||
12 | open S | |
13 | datatype z = datatype Transfer.t | |
14 | ||
15 | (* A chunkifier that puts each function in its own chunk. *) | |
16 | fun chunkPerFunc (Program.T {functions, main, ...}) = | |
17 | Vector.fromListMap | |
18 | (main :: functions, fn f => | |
19 | let | |
20 | val {name, blocks, ...} = Function.dest f | |
21 | in | |
22 | {funcs = Vector.new1 name, | |
23 | labels = Vector.map (blocks, Block.label)} | |
24 | end) | |
25 | ||
26 | (* A simple chunkifier that puts all code in the same chunk. | |
27 | *) | |
28 | fun oneChunk (Program.T {functions, main, ...}) = | |
29 | let | |
30 | val functions = main :: functions | |
31 | in | |
32 | Vector.new1 | |
33 | {funcs = Vector.fromListMap (functions, Function.name), | |
34 | labels = Vector.concatV (Vector.fromListMap | |
35 | (functions, fn f => | |
36 | Vector.map (Function.blocks f, Block.label)))} | |
37 | end | |
38 | ||
39 | fun blockSize (Block.T {statements, transfer, ...}): int = | |
40 | let | |
41 | val transferSize = | |
42 | case transfer of | |
43 | Switch (Switch.T {cases, ...}) => 1 + Vector.length cases | |
44 | | _ => 1 | |
45 | val statementsSize = | |
46 | if !Control.profile = Control.ProfileNone | |
47 | then Vector.length statements | |
48 | else Vector.fold (statements, 0, fn (s, ac) => | |
49 | case s of | |
50 | Statement.ProfileLabel _ => ac | |
51 | | _ => 1 + ac) | |
52 | in | |
53 | statementsSize + transferSize | |
54 | end | |
55 | ||
56 | (* Compute the list of functions that each function returns to *) | |
57 | fun returnsTo (Program.T {functions, main, ...}) = | |
58 | let | |
59 | val functions = main :: functions | |
60 | val {get: Func.t -> {returnsTo: Label.t list ref, | |
61 | tailCalls: Func.t list ref}, | |
62 | rem, ...} = | |
63 | Property.get (Func.plist, | |
64 | Property.initFun (fn _ => | |
65 | {returnsTo = ref [], | |
66 | tailCalls = ref []})) | |
67 | fun returnTo (f: Func.t, j: Label.t): unit = | |
68 | let | |
69 | val {returnsTo, tailCalls} = get f | |
70 | in | |
71 | if List.exists (!returnsTo, fn j' => Label.equals (j, j')) | |
72 | then () | |
73 | else (List.push (returnsTo, j) | |
74 | ; List.foreach (!tailCalls, fn f => returnTo (f, j))) | |
75 | end | |
76 | fun tailCall (from: Func.t, to: Func.t): unit = | |
77 | let | |
78 | val {returnsTo, tailCalls} = get from | |
79 | in | |
80 | if List.exists (!tailCalls, fn f => Func.equals (to, f)) | |
81 | then () | |
82 | else (List.push (tailCalls, to) | |
83 | ; List.foreach (!returnsTo, fn j => returnTo (to, j))) | |
84 | end | |
85 | val _ = | |
86 | List.foreach | |
87 | (functions, fn f => | |
88 | let | |
89 | val {name, blocks, ...} = Function.dest f | |
90 | in | |
91 | Vector.foreach | |
92 | (blocks, fn Block.T {transfer, ...} => | |
93 | case transfer of | |
94 | Call {func, return, ...} => (case return of | |
95 | Return.NonTail {cont, ...} => | |
96 | returnTo (func, cont) | |
97 | | _ => tailCall (name, func)) | |
98 | ||
99 | | _ => ()) | |
100 | end) | |
101 | in | |
102 | {rem = rem, | |
103 | returnsTo = ! o #returnsTo o get} | |
104 | end | |
105 | ||
106 | structure Graph = EquivalenceGraph | |
107 | structure Class = Graph.Class | |
108 | fun coalesce (program as Program.T {functions, main, ...}, limit) = | |
109 | let | |
110 | val functions = main :: functions | |
111 | val graph = Graph.new () | |
112 | val {get = funcClass: Func.t -> Class.t, set = setFuncClass, | |
113 | rem = remFuncClass, ...} = | |
114 | Property.getSetOnce (Func.plist, | |
115 | Property.initRaise ("class", Func.layout)) | |
116 | val {get = labelClass: Label.t -> Class.t, set = setLabelClass, | |
117 | rem = remLabelClass, ...} = | |
118 | Property.getSetOnce (Label.plist, | |
119 | Property.initRaise ("class", Label.layout)) | |
120 | (* Build the initial partition. | |
121 | * Ensure that all Ssa labels that jump to one another are in the same | |
122 | * equivalence class. | |
123 | *) | |
124 | val _ = | |
125 | List.foreach | |
126 | (functions, fn f => | |
127 | let | |
128 | val {name, blocks, start, ...} = Function.dest f | |
129 | val _ = | |
130 | Vector.foreach | |
131 | (blocks, fn b as Block.T {label, ...} => | |
132 | setLabelClass (label, | |
133 | Graph.newClass (graph, {size = blockSize b}))) | |
134 | val _ = setFuncClass (name, labelClass start) | |
135 | val _ = | |
136 | Vector.foreach | |
137 | (blocks, fn Block.T {label, transfer, ...} => | |
138 | let | |
139 | val c = labelClass label | |
140 | fun same (j: Label.t): unit = | |
141 | Graph.== (graph, c, labelClass j) | |
142 | in | |
143 | case transfer of | |
144 | Arith {overflow, success, ...} => | |
145 | (same overflow; same success) | |
146 | | CCall {return, ...} => Option.app (return, same) | |
147 | | Goto {dst, ...} => same dst | |
148 | | Switch s => Switch.foreachLabel (s, same) | |
149 | | _ => () | |
150 | end) | |
151 | in | |
152 | () | |
153 | end) | |
154 | val {returnsTo, rem = remReturnsTo} = returnsTo program | |
155 | (* Add edges, and then coalesce the graph. *) | |
156 | val _ = | |
157 | List.foreach | |
158 | (functions, fn f => | |
159 | let | |
160 | val {name, blocks, ...} = Function.dest f | |
161 | val returnsTo = List.revMap (returnsTo name, labelClass) | |
162 | val _ = | |
163 | Vector.foreach | |
164 | (blocks, fn Block.T {label, transfer, ...} => | |
165 | case transfer of | |
166 | Call {func, ...} => | |
167 | Graph.addEdge (graph, labelClass label, | |
168 | funcClass func) | |
169 | | Return _ => | |
170 | let | |
171 | val from = labelClass label | |
172 | in | |
173 | List.foreach | |
174 | (returnsTo, fn c => | |
175 | Graph.addEdge (graph, from, c)) | |
176 | end | |
177 | | _ => ()) | |
178 | in | |
179 | () | |
180 | end) | |
181 | val _ = | |
182 | if limit = 0 | |
183 | then () | |
184 | else Graph.coarsen (graph, {maxClassSize = limit}) | |
185 | type chunk = {funcs: Func.t list ref, | |
186 | labels: Label.t list ref} | |
187 | val chunks: chunk list ref = ref [] | |
188 | val {get = classChunk: Class.t -> chunk, ...} = | |
189 | Property.get | |
190 | (Class.plist, | |
191 | Property.initFun (fn _ => | |
192 | let | |
193 | val c = {funcs = ref [], | |
194 | labels = ref []} | |
195 | val _ = List.push (chunks, c) | |
196 | in | |
197 | c | |
198 | end)) | |
199 | val _ = | |
200 | let | |
201 | fun 'a new (l: 'a, | |
202 | get: 'a -> Class.t, | |
203 | sel: chunk -> 'a list ref): unit = | |
204 | List.push (sel (classChunk (get l)), l) | |
205 | val _ = | |
206 | List.foreach | |
207 | (functions, fn f => | |
208 | let | |
209 | val {name, blocks, ...} = Function.dest f | |
210 | val _ = new (name, funcClass, #funcs) | |
211 | val _ = | |
212 | Vector.foreach | |
213 | (blocks, fn Block.T {label, ...} => | |
214 | new (label, labelClass, #labels)) | |
215 | in () | |
216 | end) | |
217 | in () | |
218 | end | |
219 | val _ = | |
220 | List.foreach | |
221 | (functions, fn f => | |
222 | let | |
223 | val {blocks, name, ...} = Function.dest f | |
224 | val _ = remFuncClass name | |
225 | val _ = remReturnsTo name | |
226 | val _ = Vector.foreach (blocks, remLabelClass o Block.label) | |
227 | in | |
228 | () | |
229 | end) | |
230 | in | |
231 | Vector.fromListMap (!chunks, fn {funcs, labels} => | |
232 | {funcs = Vector.fromList (!funcs), | |
233 | labels = Vector.fromList (!labels)}) | |
234 | end | |
235 | ||
236 | fun chunkify p = | |
237 | case !Control.chunk of | |
238 | Control.ChunkPerFunc => chunkPerFunc p | |
239 | | Control.OneChunk => oneChunk p | |
240 | | Control.Coalesce {limit} => coalesce (p, limit) | |
241 | ||
242 | val chunkify = | |
243 | fn p => | |
244 | let | |
245 | val chunks = chunkify p | |
246 | val _ = | |
247 | Control.diagnostics | |
248 | (fn display => | |
249 | let | |
250 | open Layout | |
251 | val _ = display (str "Chunkification:") | |
252 | val _ = | |
253 | Vector.foreach | |
254 | (chunks, fn {funcs, labels} => | |
255 | display | |
256 | (record ([("funcs", Vector.layout Func.layout funcs), | |
257 | ("jumps", Vector.layout Label.layout labels)]))) | |
258 | in | |
259 | () | |
260 | end) | |
261 | in | |
262 | chunks | |
263 | end | |
264 | ||
265 | end |