Mercurial > urweb

annotate src/especialize.sml @ 487:33d5bd69da00

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Get threadedBlog to work
author Adam Chlipala <adamc@hcoop.net>
date Tue, 11 Nov 2008 11:49:51 -0500
parents 3ce20b0b6914
children 5521bb0b4014
rev   line source
adamc@443 1 (* Copyright (c) 2008, Adam Chlipala
adamc@443 2 * All rights reserved.
adamc@443 3 *
adamc@443 4 * Redistribution and use in source and binary forms, with or without
adamc@443 5 * modification, are permitted provided that the following conditions are met:
adamc@443 6 *
adamc@443 7 * - Redistributions of source code must retain the above copyright notice,
adamc@443 8 * this list of conditions and the following disclaimer.
adamc@443 9 * - Redistributions in binary form must reproduce the above copyright notice,
adamc@443 10 * this list of conditions and the following disclaimer in the documentation
adamc@443 11 * and/or other materials provided with the distribution.
adamc@443 12 * - The names of contributors may not be used to endorse or promote products
adamc@443 13 * derived from this software without specific prior written permission.
adamc@443 14 *
adamc@443 15 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
adamc@443 16 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
adamc@443 17 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
adamc@443 18 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
adamc@443 19 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
adamc@443 20 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
adamc@443 21 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
adamc@443 22 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
adamc@443 23 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
adamc@443 24 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
adamc@443 25 * POSSIBILITY OF SUCH DAMAGE.
adamc@443 26 *)
adamc@443 27
adamc@443 28 structure ESpecialize :> ESPECIALIZE = struct
adamc@443 29
adamc@443 30 open Core
adamc@443 31
adamc@443 32 structure E = CoreEnv
adamc@443 33 structure U = CoreUtil
adamc@443 34
adamc@479 35 type skey = exp
adamc@453 36
adamc@453 37 structure K = struct
adamc@479 38 type ord_key = exp list
adamc@479 39 val compare = Order.joinL U.Exp.compare
adamc@443 40 end
adamc@443 41
adamc@453 42 structure KM = BinaryMapFn(K)
adamc@443 43 structure IM = IntBinaryMap
adamc@482 44 structure IS = IntBinarySet
adamc@443 45
adamc@479 46 val sizeOf = U.Exp.fold {kind = fn (_, n) => n,
adamc@479 47 con = fn (_, n) => n,
adamc@479 48 exp = fn (_, n) => n + 1}
adamc@479 49 0
adamc@479 50
adamc@479 51 val isOpen = U.Exp.existsB {kind = fn _ => false,
adamc@479 52 con = fn ((nc, _), c) =>
adamc@479 53 case c of
adamc@479 54 CRel n => n >= nc
adamc@479 55 | _ => false,
adamc@479 56 exp = fn ((_, ne), e) =>
adamc@479 57 case e of
adamc@479 58 ERel n => n >= ne
adamc@479 59 | _ => false,
adamc@479 60 bind = fn ((nc, ne), b) =>
adamc@479 61 case b of
adamc@479 62 U.Exp.RelC _ => (nc + 1, ne)
adamc@479 63 | U.Exp.RelE _ => (nc, ne + 1)
adamc@479 64 | _ => (nc, ne)}
adamc@479 65 (0, 0)
adamc@479 66
adamc@479 67 fun baseBad (e, _) =
adamc@453 68 case e of
adamc@479 69 EAbs (_, _, _, e) => sizeOf e > 20
adamc@479 70 | ENamed _ => false
adamc@479 71 | _ => true
adamc@453 72
adamc@479 73 fun isBad e =
adamc@479 74 case e of
adamc@479 75 (ERecord xes, _) =>
adamc@479 76 length xes > 10
adamc@479 77 orelse List.exists (fn (_, e, _) => baseBad e) xes
adamc@479 78 | _ => baseBad e
adamc@479 79
adamc@479 80 fun skeyIn e =
adamc@479 81 if isBad e orelse isOpen e then
adamc@479 82 NONE
adamc@479 83 else
adamc@479 84 SOME e
adamc@479 85
adamc@479 86 fun skeyOut e = e
adamc@453 87
adamc@443 88 type func = {
adamc@443 89 name : string,
adamc@453 90 args : int KM.map,
adamc@443 91 body : exp,
adamc@443 92 typ : con,
adamc@443 93 tag : string
adamc@443 94 }
adamc@443 95
adamc@443 96 type state = {
adamc@443 97 maxName : int,
adamc@443 98 funcs : func IM.map,
adamc@443 99 decls : (string * int * con * exp * string) list
adamc@443 100 }
adamc@443 101
adamc@443 102 fun kind (k, st) = (k, st)
adamc@443 103 fun con (c, st) = (c, st)
adamc@443 104
adamc@453 105 fun specialize' file =
adamc@443 106 let
adamc@482 107 fun default (_, fs) = fs
adamc@482 108
adamc@482 109 fun actionableExp (e, fs) =
adamc@482 110 case e of
adamc@482 111 ERecord xes =>
adamc@482 112 foldl (fn (((CName s, _), e, _), fs) =>
adamc@482 113 if s = "Action" orelse s = "Link" then
adamc@482 114 let
adamc@482 115 fun findHead (e, _) =
adamc@482 116 case e of
adamc@482 117 ENamed n => IS.add (fs, n)
adamc@482 118 | EApp (e, _) => findHead e
adamc@482 119 | _ => fs
adamc@482 120 in
adamc@482 121 findHead e
adamc@482 122 end
adamc@482 123 else
adamc@482 124 fs
adamc@482 125 | (_, fs) => fs)
adamc@482 126 fs xes
adamc@482 127 | _ => fs
adamc@482 128
adamc@482 129 val actionable =
adamc@482 130 U.File.fold {kind = default,
adamc@482 131 con = default,
adamc@482 132 exp = actionableExp,
adamc@482 133 decl = default}
adamc@482 134 IS.empty file
adamc@482 135
adamc@482 136 fun exp (e, st : state) =
adamc@482 137 let
adamc@485 138 fun getApp' e =
adamc@482 139 case e of
adamc@482 140 ENamed f => SOME (f, [], [])
adamc@482 141 | EApp (e1, e2) =>
adamc@485 142 (case getApp' (#1 e1) of
adamc@482 143 NONE => NONE
adamc@482 144 | SOME (f, xs, xs') =>
adamc@482 145 let
adamc@482 146 val k =
adamc@482 147 if List.null xs' then
adamc@482 148 skeyIn e2
adamc@482 149 else
adamc@482 150 NONE
adamc@482 151 in
adamc@482 152 case k of
adamc@482 153 NONE => SOME (f, xs, xs' @ [e2])
adamc@482 154 | SOME k => SOME (f, xs @ [k], xs')
adamc@482 155 end)
adamc@482 156 | _ => NONE
adamc@485 157
adamc@485 158 fun getApp e =
adamc@485 159 case getApp' e of
adamc@485 160 NONE => NONE
adamc@485 161 | SOME (f, xs, xs') =>
adamc@485 162 if List.all (fn (ERecord [], _) => true | _ => false) xs then
adamc@485 163 SOME (f, [], xs @ xs')
adamc@485 164 else
adamc@485 165 SOME (f, xs, xs')
adamc@482 166 in
adamc@482 167 case getApp e of
adamc@482 168 NONE => (e, st)
adamc@482 169 | SOME (f, [], []) => (e, st)
adamc@482 170 | SOME (f, [], xs') =>
adamc@482 171 (case IM.find (#funcs st, f) of
adamc@482 172 NONE => (e, st)
adamc@482 173 | SOME {typ, body, ...} =>
adamc@482 174 let
adamc@482 175 val functionInside = U.Con.exists {kind = fn _ => false,
adamc@482 176 con = fn TFun _ => true
adamc@482 177 | CFfi ("Basis", "transaction") => true
adamc@482 178 | _ => false}
adamc@482 179
adamc@482 180 fun hasFunarg (t, xs) =
adamc@482 181 case (t, xs) of
adamc@482 182 ((TFun (dom, ran), _), _ :: xs) =>
adamc@482 183 functionInside dom
adamc@482 184 orelse hasFunarg (ran, xs)
adamc@482 185 | _ => false
adamc@482 186 in
adamc@482 187 if List.all (fn (ERel _, _) => false | _ => true) xs'
adamc@485 188 andalso List.exists (fn (ERecord [], _) => false | _ => true) xs'
adamc@482 189 andalso not (IS.member (actionable, f))
adamc@482 190 andalso hasFunarg (typ, xs') then
adamc@487 191 let
adamc@487 192 val e = foldl (fn (arg, e) => (EApp (e, arg), ErrorMsg.dummySpan))
adamc@487 193 body xs'
adamc@487 194 in
adamc@487 195 (*Print.prefaces "Unfolded"
adamc@487 196 [("e", CorePrint.p_exp CoreEnv.empty e)];*)
adamc@487 197 (#1 e, st)
adamc@487 198 end
adamc@482 199 else
adamc@482 200 (e, st)
adamc@482 201 end)
adamc@485 202 | SOME (f, xs, xs') =>
adamc@485 203 case IM.find (#funcs st, f) of
adamc@485 204 NONE => (e, st)
adamc@485 205 | SOME {name, args, body, typ, tag} =>
adamc@485 206 case KM.find (args, xs) of
adamc@485 207 SOME f' => (#1 (foldl (fn (arg, e) => (EApp (e, arg), ErrorMsg.dummySpan))
adamc@485 208 (ENamed f', ErrorMsg.dummySpan) xs'),
adamc@485 209 st)
adamc@485 210 | NONE =>
adamc@485 211 let
adamc@485 212 fun subBody (body, typ, xs) =
adamc@485 213 case (#1 body, #1 typ, xs) of
adamc@485 214 (_, _, []) => SOME (body, typ)
adamc@485 215 | (EAbs (_, _, _, body'), TFun (_, typ'), x :: xs) =>
adamc@485 216 let
adamc@485 217 val body'' = E.subExpInExp (0, skeyOut x) body'
adamc@485 218 in
adamc@485 219 subBody (body'',
adamc@485 220 typ',
adamc@485 221 xs)
adamc@485 222 end
adamc@485 223 | _ => NONE
adamc@485 224 in
adamc@485 225 case subBody (body, typ, xs) of
adamc@485 226 NONE => (e, st)
adamc@485 227 | SOME (body', typ') =>
adamc@485 228 let
adamc@487 229 (*val () = Print.prefaces "sub'd"
adamc@487 230 [("body'", CorePrint.p_exp CoreEnv.empty body')]*)
adamc@487 231
adamc@485 232 val f' = #maxName st
adamc@485 233 val funcs = IM.insert (#funcs st, f, {name = name,
adamc@485 234 args = KM.insert (args,
adamc@485 235 xs, f'),
adamc@485 236 body = body,
adamc@485 237 typ = typ,
adamc@485 238 tag = tag})
adamc@485 239 val st = {
adamc@485 240 maxName = f' + 1,
adamc@485 241 funcs = funcs,
adamc@485 242 decls = #decls st
adamc@485 243 }
adamc@482 244
adamc@487 245 (*val () = print ("Created " ^ Int.toString f' ^ " from "
adamc@487 246 ^ Int.toString f ^ "\n")
adamc@487 247 val () = Print.prefaces "body'"
adamc@487 248 [("body'", CorePrint.p_exp CoreEnv.empty body')]*)
adamc@485 249 val (body', st) = specExp st body'
adamc@487 250 (*val () = Print.prefaces "body''"
adamc@487 251 [("body'", CorePrint.p_exp CoreEnv.empty body')]*)
adamc@485 252 val e' = foldl (fn (arg, e) => (EApp (e, arg), ErrorMsg.dummySpan))
adamc@485 253 (ENamed f', ErrorMsg.dummySpan) xs'
adamc@485 254 in
adamc@485 255 (#1 e',
adamc@485 256 {maxName = #maxName st,
adamc@485 257 funcs = #funcs st,
adamc@485 258 decls = (name, f', typ', body', tag) :: #decls st})
adamc@485 259 end
adamc@485 260 end
adamc@485 261 end
adamc@482 262
adamc@482 263 and specExp st = U.Exp.foldMap {kind = kind, con = con, exp = exp} st
adamc@482 264
adamc@482 265 fun decl (d, st) = (d, st)
adamc@482 266
adamc@482 267 val specDecl = U.Decl.foldMap {kind = kind, con = con, exp = exp, decl = decl}
adamc@482 268
adamc@482 269
adamc@482 270
adamc@453 271 fun doDecl (d, (st : state, changed)) =
adamc@443 272 let
adamc@453 273 val funcs = #funcs st
adamc@453 274 val funcs =
adamc@453 275 case #1 d of
adamc@453 276 DValRec vis =>
adamc@453 277 foldl (fn ((x, n, c, e, tag), funcs) =>
adamc@453 278 IM.insert (funcs, n, {name = x,
adamc@453 279 args = KM.empty,
adamc@453 280 body = e,
adamc@453 281 typ = c,
adamc@453 282 tag = tag}))
adamc@453 283 funcs vis
adamc@453 284 | _ => funcs
adamc@453 285
adamc@453 286 val st = {maxName = #maxName st,
adamc@453 287 funcs = funcs,
adamc@453 288 decls = []}
adamc@453 289
adamc@482 290 (*val () = Print.prefaces "decl" [("d", CorePrint.p_decl CoreEnv.empty d)]*)
adamc@443 291 val (d', st) = specDecl st d
adamc@482 292 (*val () = print "/decl\n"*)
adamc@443 293
adamc@443 294 val funcs = #funcs st
adamc@443 295 val funcs =
adamc@443 296 case #1 d of
adamc@443 297 DVal (x, n, c, e as (EAbs _, _), tag) =>
adamc@443 298 IM.insert (funcs, n, {name = x,
adamc@453 299 args = KM.empty,
adamc@443 300 body = e,
adamc@443 301 typ = c,
adamc@443 302 tag = tag})
adamc@469 303 | DVal (_, n, _, (ENamed n', _), _) =>
adamc@469 304 (case IM.find (funcs, n') of
adamc@469 305 NONE => funcs
adamc@469 306 | SOME v => IM.insert (funcs, n, v))
adamc@443 307 | _ => funcs
adamc@443 308
adamc@453 309 val (changed, ds) =
adamc@443 310 case #decls st of
adamc@453 311 [] => (changed, [d'])
adamc@453 312 | vis =>
adamc@453 313 (true, case d' of
adamc@453 314 (DValRec vis', _) => [(DValRec (vis @ vis'), ErrorMsg.dummySpan)]
adamc@453 315 | _ => [(DValRec vis, ErrorMsg.dummySpan), d'])
adamc@443 316 in
adamc@453 317 (ds, ({maxName = #maxName st,
adamc@453 318 funcs = funcs,
adamc@453 319 decls = []}, changed))
adamc@443 320 end
adamc@443 321
adamc@453 322 val (ds, (_, changed)) = ListUtil.foldlMapConcat doDecl
adamc@453 323 ({maxName = U.File.maxName file + 1,
adamc@453 324 funcs = IM.empty,
adamc@453 325 decls = []}, false)
adamc@453 326 file
adamc@443 327 in
adamc@453 328 (changed, ds)
adamc@443 329 end
adamc@443 330
adamc@453 331 fun specialize file =
adamc@453 332 let
adamc@487 333 (*val () = Print.prefaces "Intermediate" [("file", CorePrint.p_file CoreEnv.empty file)];*)
adamc@453 334 val (changed, file) = specialize' file
adamc@453 335 in
adamc@453 336 if changed then
adamc@482 337 specialize (ReduceLocal.reduce file)
adamc@453 338 else
adamc@453 339 file
adamc@453 340 end
adamc@453 341
adamc@443 342 end