Mercurial > urweb

annotate src/especialize.sml @ 520:3f20c22098af

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Untangle and shake within Especialize loop
author Adam Chlipala <adamc@hcoop.net>
date Thu, 27 Nov 2008 12:04:54 -0500
parents 5521bb0b4014
children 31aba58a5b5b
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@488 46 val freeVars = U.Exp.foldB {kind = fn (_, xs) => xs,
adamc@488 47 con = fn (_, _, xs) => xs,
adamc@488 48 exp = fn (bound, e, xs) =>
adamc@488 49 case e of
adamc@488 50 ERel x =>
adamc@488 51 if x >= bound then
adamc@488 52 IS.add (xs, x - bound)
adamc@488 53 else
adamc@488 54 xs
adamc@488 55 | _ => xs,
adamc@488 56 bind = fn (bound, b) =>
adamc@488 57 case b of
adamc@488 58 U.Exp.RelE _ => bound + 1
adamc@488 59 | _ => bound}
adamc@488 60 0 IS.empty
adamc@479 61
adamc@488 62 fun positionOf (v : int, ls) =
adamc@488 63 let
adamc@488 64 fun pof (pos, ls) =
adamc@488 65 case ls of
adamc@488 66 [] => raise Fail "Defunc.positionOf"
adamc@488 67 | v' :: ls' =>
adamc@488 68 if v = v' then
adamc@488 69 pos
adamc@488 70 else
adamc@488 71 pof (pos + 1, ls')
adamc@488 72 in
adamc@488 73 pof (0, ls)
adamc@488 74 end
adamc@488 75
adamc@488 76 fun squish fvs =
adamc@488 77 U.Exp.mapB {kind = fn k => k,
adamc@488 78 con = fn _ => fn c => c,
adamc@488 79 exp = fn bound => fn e =>
adamc@479 80 case e of
adamc@488 81 ERel x =>
adamc@488 82 if x >= bound then
adamc@488 83 ERel (positionOf (x - bound, fvs) + bound)
adamc@488 84 else
adamc@488 85 e
adamc@488 86 | _ => e,
adamc@488 87 bind = fn (bound, b) =>
adamc@488 88 case b of
adamc@488 89 U.Exp.RelE _ => bound + 1
adamc@488 90 | _ => bound}
adamc@488 91 0
adamc@453 92
adamc@443 93 type func = {
adamc@443 94 name : string,
adamc@453 95 args : int KM.map,
adamc@443 96 body : exp,
adamc@443 97 typ : con,
adamc@443 98 tag : string
adamc@443 99 }
adamc@443 100
adamc@443 101 type state = {
adamc@443 102 maxName : int,
adamc@443 103 funcs : func IM.map,
adamc@443 104 decls : (string * int * con * exp * string) list
adamc@443 105 }
adamc@443 106
adamc@488 107 fun kind x = x
adamc@488 108 fun default (_, x, st) = (x, st)
adamc@443 109
adamc@453 110 fun specialize' file =
adamc@443 111 let
adamc@488 112 fun default' (_, fs) = fs
adamc@482 113
adamc@482 114 fun actionableExp (e, fs) =
adamc@482 115 case e of
adamc@482 116 ERecord xes =>
adamc@482 117 foldl (fn (((CName s, _), e, _), fs) =>
adamc@482 118 if s = "Action" orelse s = "Link" then
adamc@482 119 let
adamc@482 120 fun findHead (e, _) =
adamc@482 121 case e of
adamc@482 122 ENamed n => IS.add (fs, n)
adamc@482 123 | EApp (e, _) => findHead e
adamc@482 124 | _ => fs
adamc@482 125 in
adamc@482 126 findHead e
adamc@482 127 end
adamc@482 128 else
adamc@482 129 fs
adamc@482 130 | (_, fs) => fs)
adamc@482 131 fs xes
adamc@482 132 | _ => fs
adamc@482 133
adamc@482 134 val actionable =
adamc@488 135 U.File.fold {kind = default',
adamc@488 136 con = default',
adamc@482 137 exp = actionableExp,
adamc@488 138 decl = default'}
adamc@482 139 IS.empty file
adamc@482 140
adamc@488 141 fun bind (env, b) =
adamc@488 142 case b of
adamc@488 143 U.Decl.RelC (x, k) => E.pushCRel env x k
adamc@488 144 | U.Decl.NamedC (x, n, k, co) => E.pushCNamed env x n k co
adamc@488 145 | U.Decl.RelE (x, t) => E.pushERel env x t
adamc@488 146 | U.Decl.NamedE (x, n, t, eo, s) => E.pushENamed env x n t eo s
adamc@488 147
adamc@488 148 fun exp (env, e, st : state) =
adamc@482 149 let
adamc@488 150 fun getApp e =
adamc@482 151 case e of
adamc@488 152 ENamed f => SOME (f, [])
adamc@482 153 | EApp (e1, e2) =>
adamc@488 154 (case getApp (#1 e1) of
adamc@482 155 NONE => NONE
adamc@488 156 | SOME (f, xs) => SOME (f, xs @ [e2]))
adamc@482 157 | _ => NONE
adamc@482 158 in
adamc@482 159 case getApp e of
adamc@482 160 NONE => (e, st)
adamc@488 161 | SOME (f, xs) =>
adamc@485 162 case IM.find (#funcs st, f) of
adamc@485 163 NONE => (e, st)
adamc@485 164 | SOME {name, args, body, typ, tag} =>
adamc@488 165 let
adamc@488 166 val functionInside = U.Con.exists {kind = fn _ => false,
adamc@488 167 con = fn TFun _ => true
adamc@488 168 | CFfi ("Basis", "transaction") => true
adamc@488 169 | _ => false}
adamc@488 170 val loc = ErrorMsg.dummySpan
adamc@488 171
adamc@488 172 fun findSplit (xs, typ, fxs, fvs) =
adamc@488 173 case (#1 typ, xs) of
adamc@488 174 (TFun (dom, ran), e :: xs') =>
adamc@488 175 if functionInside dom then
adamc@488 176 findSplit (xs',
adamc@488 177 ran,
adamc@488 178 e :: fxs,
adamc@488 179 IS.union (fvs, freeVars e))
adamc@488 180 else
adamc@488 181 (rev fxs, xs, fvs)
adamc@488 182 | _ => (rev fxs, xs, fvs)
adamc@488 183
adamc@488 184 val (fxs, xs, fvs) = findSplit (xs, typ, [], IS.empty)
adamc@488 185
adamc@488 186 val fxs' = map (squish (IS.listItems fvs)) fxs
adamc@488 187
adamc@488 188 fun firstRel () =
adamc@488 189 case fxs' of
adamc@488 190 (ERel _, _) :: _ => true
adamc@488 191 | _ => false
adamc@488 192 in
adamc@488 193 if firstRel ()
adamc@488 194 orelse List.all (fn (ERel _, _) => true
adamc@488 195 | _ => false) fxs' then
adamc@488 196 (e, st)
adamc@488 197 else
adamc@488 198 case KM.find (args, fxs') of
adamc@488 199 SOME f' =>
adamc@485 200 let
adamc@488 201 val e = (ENamed f', loc)
adamc@488 202 val e = IS.foldr (fn (arg, e) => (EApp (e, (ERel arg, loc)), loc))
adamc@488 203 e fvs
adamc@488 204 val e = foldl (fn (arg, e) => (EApp (e, arg), loc))
adamc@488 205 e xs
adamc@488 206 in
adamc@488 207 (*Print.prefaces "Brand new (reuse)"
adamc@488 208 [("e'", CorePrint.p_exp env e)];*)
adamc@488 209 (#1 e, st)
adamc@488 210 end
adamc@488 211 | NONE =>
adamc@488 212 let
adamc@488 213 fun subBody (body, typ, fxs') =
adamc@488 214 case (#1 body, #1 typ, fxs') of
adamc@488 215 (_, _, []) => SOME (body, typ)
adamc@488 216 | (EAbs (_, _, _, body'), TFun (_, typ'), x :: fxs'') =>
adamc@488 217 let
adamc@488 218 val body'' = E.subExpInExp (0, x) body'
adamc@488 219 in
adamc@488 220 subBody (body'',
adamc@488 221 typ',
adamc@488 222 fxs'')
adamc@488 223 end
adamc@488 224 | _ => NONE
adamc@488 225 in
adamc@488 226 case subBody (body, typ, fxs') of
adamc@488 227 NONE => (e, st)
adamc@488 228 | SOME (body', typ') =>
adamc@488 229 let
adamc@488 230 val f' = #maxName st
adamc@488 231 val args = KM.insert (args, fxs', f')
adamc@488 232 val funcs = IM.insert (#funcs st, f, {name = name,
adamc@488 233 args = args,
adamc@488 234 body = body,
adamc@488 235 typ = typ,
adamc@488 236 tag = tag})
adamc@488 237 val st = {
adamc@488 238 maxName = f' + 1,
adamc@488 239 funcs = funcs,
adamc@488 240 decls = #decls st
adamc@488 241 }
adamc@487 242
adamc@488 243 (*val () = Print.prefaces "specExp"
adamc@488 244 [("f", CorePrint.p_exp env (ENamed f, loc)),
adamc@488 245 ("f'", CorePrint.p_exp env (ENamed f', loc)),
adamc@488 246 ("xs", Print.p_list (CorePrint.p_exp env) xs),
adamc@488 247 ("fxs'", Print.p_list
adamc@488 248 (CorePrint.p_exp E.empty) fxs'),
adamc@488 249 ("e", CorePrint.p_exp env (e, loc))]*)
adamc@488 250 val (body', typ') = IS.foldl (fn (n, (body', typ')) =>
adamc@488 251 let
adamc@488 252 val (x, xt) = E.lookupERel env n
adamc@488 253 in
adamc@488 254 ((EAbs (x, xt, typ', body'),
adamc@488 255 loc),
adamc@488 256 (TFun (xt, typ'), loc))
adamc@488 257 end)
adamc@488 258 (body', typ') fvs
adamc@488 259 val (body', st) = specExp env st body'
adamc@482 260
adamc@488 261 val e' = (ENamed f', loc)
adamc@488 262 val e' = IS.foldr (fn (arg, e) => (EApp (e, (ERel arg, loc)), loc))
adamc@488 263 e' fvs
adamc@488 264 val e' = foldl (fn (arg, e) => (EApp (e, arg), loc))
adamc@488 265 e' xs
adamc@488 266 (*val () = Print.prefaces "Brand new"
adamc@488 267 [("e'", CorePrint.p_exp env e'),
adamc@488 268 ("e", CorePrint.p_exp env (e, loc)),
adamc@488 269 ("body'", CorePrint.p_exp env body')]*)
adamc@488 270 in
adamc@488 271 (#1 e',
adamc@488 272 {maxName = #maxName st,
adamc@488 273 funcs = #funcs st,
adamc@488 274 decls = (name, f', typ', body', tag) :: #decls st})
adamc@488 275 end
adamc@485 276 end
adamc@488 277 end
adamc@485 278 end
adamc@482 279
adamc@488 280 and specExp env = U.Exp.foldMapB {kind = kind, con = default, exp = exp, bind = bind} env
adamc@482 281
adamc@488 282 val specDecl = U.Decl.foldMapB {kind = kind, con = default, exp = exp, decl = default, bind = bind}
adamc@482 283
adamc@488 284 fun doDecl (d, (env, st : state, changed)) =
adamc@488 285 let
adamc@488 286 val env = E.declBinds env d
adamc@482 287
adamc@453 288 val funcs = #funcs st
adamc@453 289 val funcs =
adamc@453 290 case #1 d of
adamc@453 291 DValRec vis =>
adamc@453 292 foldl (fn ((x, n, c, e, tag), funcs) =>
adamc@453 293 IM.insert (funcs, n, {name = x,
adamc@453 294 args = KM.empty,
adamc@453 295 body = e,
adamc@453 296 typ = c,
adamc@453 297 tag = tag}))
adamc@453 298 funcs vis
adamc@453 299 | _ => funcs
adamc@453 300
adamc@453 301 val st = {maxName = #maxName st,
adamc@453 302 funcs = funcs,
adamc@453 303 decls = []}
adamc@453 304
adamc@482 305 (*val () = Print.prefaces "decl" [("d", CorePrint.p_decl CoreEnv.empty d)]*)
adamc@488 306 val (d', st) = specDecl env st d
adamc@482 307 (*val () = print "/decl\n"*)
adamc@443 308
adamc@443 309 val funcs = #funcs st
adamc@443 310 val funcs =
adamc@443 311 case #1 d of
adamc@443 312 DVal (x, n, c, e as (EAbs _, _), tag) =>
adamc@443 313 IM.insert (funcs, n, {name = x,
adamc@453 314 args = KM.empty,
adamc@443 315 body = e,
adamc@443 316 typ = c,
adamc@443 317 tag = tag})
adamc@469 318 | DVal (_, n, _, (ENamed n', _), _) =>
adamc@469 319 (case IM.find (funcs, n') of
adamc@469 320 NONE => funcs
adamc@469 321 | SOME v => IM.insert (funcs, n, v))
adamc@443 322 | _ => funcs
adamc@443 323
adamc@453 324 val (changed, ds) =
adamc@443 325 case #decls st of
adamc@453 326 [] => (changed, [d'])
adamc@453 327 | vis =>
adamc@453 328 (true, case d' of
adamc@453 329 (DValRec vis', _) => [(DValRec (vis @ vis'), ErrorMsg.dummySpan)]
adamc@453 330 | _ => [(DValRec vis, ErrorMsg.dummySpan), d'])
adamc@443 331 in
adamc@488 332 (ds, (env,
adamc@488 333 {maxName = #maxName st,
adamc@453 334 funcs = funcs,
adamc@453 335 decls = []}, changed))
adamc@443 336 end
adamc@443 337
adamc@488 338 val (ds, (_, _, changed)) = ListUtil.foldlMapConcat doDecl
adamc@488 339 (E.empty,
adamc@488 340 {maxName = U.File.maxName file + 1,
adamc@488 341 funcs = IM.empty,
adamc@488 342 decls = []},
adamc@488 343 false)
adamc@488 344 file
adamc@443 345 in
adamc@453 346 (changed, ds)
adamc@443 347 end
adamc@443 348
adamc@453 349 fun specialize file =
adamc@453 350 let
adamc@487 351 (*val () = Print.prefaces "Intermediate" [("file", CorePrint.p_file CoreEnv.empty file)];*)
adamc@520 352 (*val file = ReduceLocal.reduce file*)
adamc@453 353 val (changed, file) = specialize' file
adamc@520 354 (*val file = ReduceLocal.reduce file
adamc@520 355 val file = CoreUntangle.untangle file
adamc@488 356 val file = Shake.shake file*)
adamc@453 357 in
adamc@488 358 (*print "Round over\n";*)
adamc@453 359 if changed then
adamc@520 360 let
adamc@520 361 val file = ReduceLocal.reduce file
adamc@520 362 val file = CoreUntangle.untangle file
adamc@520 363 val file = Shake.shake file
adamc@520 364 in
adamc@520 365 (*print "Again!\n";*)
adamc@520 366 specialize file
adamc@520 367 end
adamc@453 368 else
adamc@453 369 file
adamc@453 370 end
adamc@453 371
adamc@443 372 end