Home My Page Projects Code Snippets Project Openings diderot
Summary Activity Tracker Tasks SCM

SCM Repository

[diderot] View of /branches/vis12-cl/src/compiler/IL/promote-fn.sml
ViewVC logotype

View of /branches/vis12-cl/src/compiler/IL/promote-fn.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 3349 - (download) (annotate)
Tue Oct 27 15:16:36 2015 UTC (3 years, 11 months ago) by jhr
File size: 8616 byte(s)
making copyrights consistent for all code in the repository
(* promote-fn.sml
 *
 * This code is part of the Diderot Project (http://diderot-language.cs.uchicago.edu)
 *
 * COPYRIGHT (c) 2015 The University of Chicago
 * All rights reserved.
 *
 * Transformations, such as normalization, can create references to variables defined
 * in the global initialization section from nested scopes (e.g., inside strands).
 * This functor implements a pass that promotes such variables to be globals.
 *)

functor PromoteFn (IL : SSA) : sig

    val transform : IL.program -> IL.program

  end = struct

    structure V = IL.Var
    structure VTbl = V.Tbl
    structure VMap = V.Map

  (* adjust a variable's use count *)
    fun incUse (IL.V{useCnt, ...}) = (useCnt := !useCnt + 1)
    fun decUse (IL.V{useCnt, ...}) = (useCnt := !useCnt - 1)
    fun incGlobal (IL.GV{useCnt, ...}) = (useCnt := !useCnt + 1)

  (* variables in the global initialization section are either just used locally
   * or used to define a global (via GASSIGN).
   *)
    datatype info = LOCAL | GLOBAL of IL.global_var

    fun initTbl (inputInit, globalInit) = let
          val tbl = VTbl.mkTable (64, Fail "promote")
          val insert = VTbl.insert tbl
          fun doNode nd = (case IL.Node.kind nd
                 of IL.GASSIGN{lhs, rhs, ...} => insert (rhs, GLOBAL lhs)
                  | _ => List.app (fn x => insert (x, LOCAL)) (IL.Node.defs nd)
                (* end case *))
          in
            IL.CFG.apply doNode inputInit;
            IL.CFG.apply doNode globalInit;
            tbl
          end

    fun transform (prog as IL.Program{globals=[], ...}) = prog
      | transform (IL.Program{props, globals, inputInit, globalInit, initially, strands}) = let
        (* table mapping locals in the globalInit to info *)
          val promoteTbl = initTbl (inputInit, globalInit)
        (* newly defined globals paired with their globalInit local definition *)
          val newGlobs : (IL.global_var * IL.var) list ref = ref []
        (* update a CFG as necessary to references to globalInit locals with references to new
         * globals.
         *)
          fun doCFG cfg = let
              (* assignment statements to load local copies of the new globals; these get put
               * at the beginning of the block.
               *)
                val initStms = ref []
                fun doNode (nd as IL.ND{id, props, kind}, env) = let
                      fun doUse (false, [], _, env, _) = env
                        | doUse (true, [], ys, env, mkNode) = (
                            IL.CFG.replaceNode (nd, mkNode(List.rev ys));
                            env)
                        | doUse (changed, x::xs, ys, env, mkNode) = (case VTbl.find promoteTbl x
                             of SOME LOCAL => let
                                  val x' = V.copy x
                                  val gx = IL.GlobalVar.new(false, V.name x, V.ty x)
                                  in
                                    decUse x; incUse x'; incGlobal gx;
                                    initStms := IL.ASSGN(x', IL.GLOBAL gx) :: !initStms;
                                    newGlobs := (gx, x) :: !newGlobs;
                                    VTbl.insert promoteTbl (x, GLOBAL gx);
                                    doUse (true, xs, x'::ys, VMap.insert(env, x, x'), mkNode)
                                  end
                              | SOME(GLOBAL gx) => (case VMap.find(env, x)
                                   of SOME x' => (
                                        decUse x; incUse x';
                                        doUse (true, xs, x'::ys, env, mkNode))
                                    | NONE => let (* no previous use of g in this CFG *)
                                        val x' = V.copy x
                                        in
                                          decUse x; incUse x'; incGlobal gx;
                                          initStms := IL.ASSGN(x', IL.GLOBAL gx) :: !initStms;
                                          doUse (true, xs, x'::ys, VMap.insert(env, x, x'), mkNode)
                                        end
                                  (* end case *))
                              | NONE => doUse (changed, xs, x::ys, env, mkNode)
                            (* end case *))
                      fun doArgs (args, mkNode) = doUse (false, args, [], env, mkNode)
                      in
                        case kind
                         of IL.NULL => env
                          | IL.ENTRY _ => env
                          | IL.JOIN _ => env
                          | IL.COND _ => env
                          | IL.COM _ => env
                          | IL.ASSIGN{stm=(lhs, rhs), ...} => (case rhs
                               of IL.GLOBAL _ => env
                                | IL.STATE _ => env
                                | IL.VAR x => doArgs ([x], fn [x] => IL.Node.mkASSIGN(lhs, IL.VAR x))
                                | IL.LIT _ => env
                                | IL.OP(rator, args) =>
                                    doArgs (args, fn args => IL.Node.mkASSIGN(lhs, IL.OP(rator, args)))
                                | IL.APPLY(f, args) =>
                                    doArgs (args, fn args => IL.Node.mkASSIGN(lhs, IL.APPLY(f, args)))
                                | IL.CONS(ty, args) =>
                                    doArgs (args, fn args => IL.Node.mkASSIGN(lhs, IL.CONS(ty, args)))
                              (* end case *))
                          | IL.MASSIGN{stm=(lhs, rator, rhs), ...} =>
                              doArgs (rhs, fn rhs => IL.Node.mkMASSIGN(lhs, rator, rhs))
                          | IL.GASSIGN _ => raise Fail "unexpected GASSIGN"
                          | IL.NEW{strand, args, ...} =>
                              doArgs (args, fn args => IL.Node.mkNEW{strand=strand, args=args})
                          | IL.SAVE{lhs, rhs, ...} =>
                              doArgs ([rhs], fn [rhs] => IL.Node.mkSAVE(lhs, rhs))
                          | IL.EXIT{live=[], ...} => env
                          | IL.EXIT{kind, live, ...} =>
                              doArgs (live, fn live => IL.Node.mkEXIT(kind, live))
                        (* end case *)
                      end
                in
                  List.foldl doNode VMap.empty (IL.CFG.sort cfg);
                  case !initStms
                   of [] => cfg
                    | stms => IL.CFG.prependBlock(List.rev stms, cfg)
                  (* end case *)
                end
        (* process the initially code *)
          val initially' = let
                val IL.Initially{isArray, rangeInit, iters, create=(cfg, strand, args)} = initially
                in
                  IL.Initially{
                      isArray = isArray,
                      rangeInit = doCFG rangeInit,
                      iters = iters,
                      create = (doCFG cfg, strand, args)
                    }
                end
        (* process a strand method *)
          fun doMeth (IL.Method{name, body}) = IL.Method{name = name, body = doCFG body}
        (* process a strand *)
          fun doStrand (IL.Strand{name, params, state, stateInit, methods}) = IL.Strand{
                  name = name, params = params, state = state,
                  stateInit = doCFG stateInit,
                  methods = List.map doMeth methods
                }
          val strands' = List.map doStrand strands
        (* check to see if we have created new globals and thus need to update the globalInit block *)
          val (globals', globalInit') = (case !newGlobs
                 of [] => (globals, globalInit)
                  | globs => let
                      fun f ([], globals, stms) = (globals, stms)
                        | f ((gx, x)::globs, globals, stms) = (
                              incUse x;
                              IL.GlobalVar.setBinding(gx, x);
                              f (globs, gx::globals, IL.GASSGN(gx, x)::stms))
                      val (globals', stms) = f (globs, [], [])
                      in
                        (globals @ globals', IL.CFG.appendBlock (globalInit, stms))
                      end
                (* end case *))
          in
            IL.Program{
                props = props,
                globals = globals',
                inputInit = inputInit,
                globalInit = globalInit',
                initially = initially',
                strands = strands'
              }
          end
          
  end

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