adamc@443: (* Copyright (c) 2008, Adam Chlipala
adamc@443:  * All rights reserved.
adamc@443:  *
adamc@443:  * Redistribution and use in source and binary forms, with or without
adamc@443:  * modification, are permitted provided that the following conditions are met:
adamc@443:  *
adamc@443:  * - Redistributions of source code must retain the above copyright notice,
adamc@443:  *   this list of conditions and the following disclaimer.
adamc@443:  * - Redistributions in binary form must reproduce the above copyright notice,
adamc@443:  *   this list of conditions and the following disclaimer in the documentation
adamc@443:  *   and/or other materials provided with the distribution.
adamc@443:  * - The names of contributors may not be used to endorse or promote products
adamc@443:  *   derived from this software without specific prior written permission.
adamc@443:  *
adamc@443:  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
adamc@443:  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
adamc@443:  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
adamc@443:  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
adamc@443:  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 
adamc@443:  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
adamc@443:  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
adamc@443:  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
adamc@443:  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
adamc@443:  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
adamc@443:  * POSSIBILITY OF SUCH DAMAGE.
adamc@443:  *)
adamc@443: 
adamc@443: structure ESpecialize :> ESPECIALIZE = struct
adamc@443: 
adamc@443: open Core
adamc@443: 
adamc@443: structure E = CoreEnv
adamc@443: structure U = CoreUtil
adamc@443: 
adamc@479: type skey = exp
adamc@453: 
adamc@453: structure K = struct
adamc@479: type ord_key = exp list
adamc@479: val compare = Order.joinL U.Exp.compare
adamc@443: end
adamc@443: 
adamc@453: structure KM = BinaryMapFn(K)
adamc@443: structure IM = IntBinaryMap
adamc@482: structure IS = IntBinarySet
adamc@443: 
adamc@479: val sizeOf = U.Exp.fold {kind = fn (_, n) => n,
adamc@479:                          con = fn (_, n) => n,
adamc@479:                          exp = fn (_, n) => n + 1}
adamc@479:                         0
adamc@479: 
adamc@479: val isOpen = U.Exp.existsB {kind = fn _ => false,
adamc@479:                             con = fn ((nc, _), c) =>
adamc@479:                                     case c of
adamc@479:                                         CRel n => n >= nc
adamc@479:                                       | _ => false,
adamc@479:                             exp = fn ((_, ne), e) =>
adamc@479:                                      case e of
adamc@479:                                          ERel n => n >= ne
adamc@479:                                        | _ => false,
adamc@479:                             bind = fn ((nc, ne), b) =>
adamc@479:                                       case b of
adamc@479:                                           U.Exp.RelC _ => (nc + 1, ne)
adamc@479:                                         | U.Exp.RelE _ => (nc, ne + 1)
adamc@479:                                         | _ => (nc, ne)}
adamc@479:              (0, 0)
adamc@479: 
adamc@479: fun baseBad (e, _) =
adamc@453:     case e of
adamc@479:         EAbs (_, _, _, e) => sizeOf e > 20
adamc@479:       | ENamed _ => false
adamc@479:       | _ => true
adamc@453: 
adamc@479: fun isBad e =
adamc@479:     case e of
adamc@479:         (ERecord xes, _) =>
adamc@479:         length xes > 10
adamc@479:         orelse List.exists (fn (_, e, _) => baseBad e) xes
adamc@479:       | _ => baseBad e
adamc@479: 
adamc@479: fun skeyIn e =
adamc@479:     if isBad e orelse isOpen e then
adamc@479:         NONE
adamc@479:     else
adamc@479:         SOME e
adamc@479: 
adamc@479: fun skeyOut e = e
adamc@453: 
adamc@443: type func = {
adamc@443:      name : string,
adamc@453:      args : int KM.map,
adamc@443:      body : exp,
adamc@443:      typ : con,
adamc@443:      tag : string
adamc@443: }
adamc@443: 
adamc@443: type state = {
adamc@443:      maxName : int,
adamc@443:      funcs : func IM.map,
adamc@443:      decls : (string * int * con * exp * string) list
adamc@443: }
adamc@443: 
adamc@443: fun kind (k, st) = (k, st)
adamc@443: fun con (c, st) = (c, st)
adamc@443: 
adamc@453: fun specialize' file =
adamc@443:     let
adamc@482:         fun default (_, fs) = fs
adamc@482: 
adamc@482:         fun actionableExp (e, fs) =
adamc@482:             case e of
adamc@482:                 ERecord xes =>
adamc@482:                 foldl (fn (((CName s, _), e, _), fs) =>
adamc@482:                           if s = "Action" orelse s = "Link" then
adamc@482:                               let
adamc@482:                                   fun findHead (e, _) =
adamc@482:                                       case e of
adamc@482:                                           ENamed n => IS.add (fs, n)
adamc@482:                                         | EApp (e, _) => findHead e
adamc@482:                                         | _ => fs
adamc@482:                               in
adamc@482:                                   findHead e
adamc@482:                               end
adamc@482:                           else
adamc@482:                               fs
adamc@482:                         | (_, fs) => fs)
adamc@482:                 fs xes
adamc@482:               | _ => fs
adamc@482: 
adamc@482:         val actionable =
adamc@482:             U.File.fold {kind = default,
adamc@482:                          con = default,
adamc@482:                          exp = actionableExp,
adamc@482:                          decl = default}
adamc@482:             IS.empty file
adamc@482: 
adamc@482:         fun exp (e, st : state) =
adamc@482:             let
adamc@485:                 fun getApp' e =
adamc@482:                     case e of
adamc@482:                         ENamed f => SOME (f, [], [])
adamc@482:                       | EApp (e1, e2) =>
adamc@485:                         (case getApp' (#1 e1) of
adamc@482:                              NONE => NONE
adamc@482:                            | SOME (f, xs, xs') =>
adamc@482:                              let
adamc@482:                                  val k =
adamc@482:                                      if List.null xs' then
adamc@482:                                          skeyIn e2
adamc@482:                                      else
adamc@482:                                          NONE
adamc@482:                              in
adamc@482:                                  case k of
adamc@482:                                      NONE => SOME (f, xs, xs' @ [e2])
adamc@482:                                    | SOME k => SOME (f, xs @ [k], xs')
adamc@482:                              end)
adamc@482:                       | _ => NONE
adamc@485: 
adamc@485:                 fun getApp e =
adamc@485:                     case getApp' e of
adamc@485:                         NONE => NONE
adamc@485:                       | SOME (f, xs, xs') =>
adamc@485:                         if List.all (fn (ERecord [], _) => true | _ => false) xs then
adamc@485:                             SOME (f, [], xs @ xs')
adamc@485:                         else
adamc@485:                             SOME (f, xs, xs')
adamc@482:             in
adamc@482:                 case getApp e of
adamc@482:                     NONE => (e, st)
adamc@482:                   | SOME (f, [], []) => (e, st)
adamc@482:                   | SOME (f, [], xs') =>
adamc@482:                     (case IM.find (#funcs st, f) of
adamc@482:                          NONE => (e, st)
adamc@482:                        | SOME {typ, body, ...} =>
adamc@482:                          let
adamc@482:                              val functionInside = U.Con.exists {kind = fn _ => false,
adamc@482:                                                                 con = fn TFun _ => true
adamc@482:                                                                        | CFfi ("Basis", "transaction") => true
adamc@482:                                                                        | _ => false}
adamc@482: 
adamc@482:                              fun hasFunarg (t, xs) =
adamc@482:                                  case (t, xs) of
adamc@482:                                      ((TFun (dom, ran), _), _ :: xs) =>
adamc@482:                                      functionInside dom
adamc@482:                                      orelse hasFunarg (ran, xs)
adamc@482:                                    | _ => false
adamc@482:                          in
adamc@482:                              if List.all (fn (ERel _, _) => false | _ => true) xs'
adamc@485:                                 andalso List.exists (fn (ERecord [], _) => false | _ => true) xs'
adamc@482:                                 andalso not (IS.member (actionable, f))
adamc@482:                                 andalso hasFunarg (typ, xs') then
adamc@487:                                  let
adamc@487:                                      val e = foldl (fn (arg, e) => (EApp (e, arg), ErrorMsg.dummySpan))
adamc@487:                                                    body xs'
adamc@487:                                  in
adamc@487:                                      (*Print.prefaces "Unfolded"
adamc@487:                                                     [("e", CorePrint.p_exp CoreEnv.empty e)];*)
adamc@487:                                      (#1 e, st)
adamc@487:                                  end
adamc@482:                              else
adamc@482:                                  (e, st)
adamc@482:                          end)
adamc@485:                   | SOME (f, xs, xs') =>
adamc@485:                     case IM.find (#funcs st, f) of
adamc@485:                         NONE => (e, st)
adamc@485:                       | SOME {name, args, body, typ, tag} =>
adamc@485:                         case KM.find (args, xs) of
adamc@485:                             SOME f' => (#1 (foldl (fn (arg, e) => (EApp (e, arg), ErrorMsg.dummySpan))
adamc@485:                                                   (ENamed f', ErrorMsg.dummySpan) xs'),
adamc@485:                                         st)
adamc@485:                           | NONE =>
adamc@485:                             let
adamc@485:                                 fun subBody (body, typ, xs) =
adamc@485:                                     case (#1 body, #1 typ, xs) of
adamc@485:                                         (_, _, []) => SOME (body, typ)
adamc@485:                                       | (EAbs (_, _, _, body'), TFun (_, typ'), x :: xs) =>
adamc@485:                                         let
adamc@485:                                             val body'' = E.subExpInExp (0, skeyOut x) body'
adamc@485:                                         in
adamc@485:                                             subBody (body'',
adamc@485:                                                      typ',
adamc@485:                                                      xs)
adamc@485:                                         end
adamc@485:                                       | _ => NONE
adamc@485:                             in
adamc@485:                                 case subBody (body, typ, xs) of
adamc@485:                                     NONE => (e, st)
adamc@485:                                   | SOME (body', typ') =>
adamc@485:                                     let
adamc@487:                                         (*val () = Print.prefaces "sub'd"
adamc@487:                                                  [("body'", CorePrint.p_exp CoreEnv.empty body')]*)
adamc@487: 
adamc@485:                                         val f' = #maxName st
adamc@485:                                         val funcs = IM.insert (#funcs st, f, {name = name,
adamc@485:                                                                               args = KM.insert (args,
adamc@485:                                                                                                 xs, f'),
adamc@485:                                                                               body = body,
adamc@485:                                                                               typ = typ,
adamc@485:                                                                               tag = tag})
adamc@485:                                         val st = {
adamc@485:                                             maxName = f' + 1,
adamc@485:                                             funcs = funcs,
adamc@485:                                             decls = #decls st
adamc@485:                                         }
adamc@482: 
adamc@487:                                         (*val () = print ("Created " ^ Int.toString f' ^ " from "
adamc@487:                                                         ^ Int.toString f ^ "\n")
adamc@487:                                         val () = Print.prefaces "body'"
adamc@487:                                                  [("body'", CorePrint.p_exp CoreEnv.empty body')]*)
adamc@485:                                         val (body', st) = specExp st body'
adamc@487:                                         (*val () = Print.prefaces "body''"
adamc@487:                                                  [("body'", CorePrint.p_exp CoreEnv.empty body')]*)
adamc@485:                                         val e' = foldl (fn (arg, e) => (EApp (e, arg), ErrorMsg.dummySpan))
adamc@485:                                                        (ENamed f', ErrorMsg.dummySpan) xs'
adamc@485:                                     in
adamc@485:                                         (#1 e',
adamc@485:                                          {maxName = #maxName st,
adamc@485:                                           funcs = #funcs st,
adamc@485:                                           decls = (name, f', typ', body', tag) :: #decls st})
adamc@485:                                     end
adamc@485:                             end
adamc@485:             end
adamc@482: 
adamc@482:         and specExp st = U.Exp.foldMap {kind = kind, con = con, exp = exp} st
adamc@482: 
adamc@482:         fun decl (d, st) = (d, st)
adamc@482: 
adamc@482:         val specDecl = U.Decl.foldMap {kind = kind, con = con, exp = exp, decl = decl}
adamc@482: 
adamc@482: 
adamc@482: 
adamc@453:         fun doDecl (d, (st : state, changed)) =
adamc@443:             let
adamc@453:                 val funcs = #funcs st
adamc@453:                 val funcs = 
adamc@453:                     case #1 d of
adamc@453:                         DValRec vis =>
adamc@453:                         foldl (fn ((x, n, c, e, tag), funcs) =>
adamc@453:                                   IM.insert (funcs, n, {name = x,
adamc@453:                                                         args = KM.empty,
adamc@453:                                                         body = e,
adamc@453:                                                         typ = c,
adamc@453:                                                         tag = tag}))
adamc@453:                               funcs vis
adamc@453:                       | _ => funcs
adamc@453: 
adamc@453:                 val st = {maxName = #maxName st,
adamc@453:                           funcs = funcs,
adamc@453:                           decls = []}
adamc@453: 
adamc@482:                 (*val () = Print.prefaces "decl" [("d", CorePrint.p_decl CoreEnv.empty d)]*)
adamc@443:                 val (d', st) = specDecl st d
adamc@482:                 (*val () = print "/decl\n"*)
adamc@443: 
adamc@443:                 val funcs = #funcs st
adamc@443:                 val funcs =
adamc@443:                     case #1 d of
adamc@443:                         DVal (x, n, c, e as (EAbs _, _), tag) =>
adamc@443:                         IM.insert (funcs, n, {name = x,
adamc@453:                                               args = KM.empty,
adamc@443:                                               body = e,
adamc@443:                                               typ = c,
adamc@443:                                               tag = tag})
adamc@469:                       | DVal (_, n, _, (ENamed n', _), _) =>
adamc@469:                         (case IM.find (funcs, n') of
adamc@469:                              NONE => funcs
adamc@469:                            | SOME v => IM.insert (funcs, n, v))
adamc@443:                       | _ => funcs
adamc@443: 
adamc@453:                 val (changed, ds) =
adamc@443:                     case #decls st of
adamc@453:                         [] => (changed, [d'])
adamc@453:                       | vis =>
adamc@453:                         (true, case d' of
adamc@453:                                    (DValRec vis', _) => [(DValRec (vis @ vis'), ErrorMsg.dummySpan)]
adamc@453:                                  | _ => [(DValRec vis, ErrorMsg.dummySpan), d'])
adamc@443:             in
adamc@453:                 (ds, ({maxName = #maxName st,
adamc@453:                        funcs = funcs,
adamc@453:                        decls = []}, changed))
adamc@443:             end
adamc@443: 
adamc@453:         val (ds, (_, changed)) = ListUtil.foldlMapConcat doDecl
adamc@453:                                                          ({maxName = U.File.maxName file + 1,
adamc@453:                                                            funcs = IM.empty,
adamc@453:                                                            decls = []}, false)
adamc@453:                                                          file
adamc@443:     in
adamc@453:         (changed, ds)
adamc@443:     end
adamc@443: 
adamc@453: fun specialize file =
adamc@453:     let
adamc@487:         (*val () = Print.prefaces "Intermediate" [("file", CorePrint.p_file CoreEnv.empty file)];*)
adamc@453:         val (changed, file) = specialize' file
adamc@453:     in
adamc@453:         if changed then
adamc@482:             specialize (ReduceLocal.reduce file)
adamc@453:         else
adamc@453:             file
adamc@453:     end
adamc@453: 
adamc@443: end