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

SCM Repository

[diderot] View of /branches/vis12-cl/src/compiler/high-il/border-control.sml
ViewVC logotype

View of /branches/vis12-cl/src/compiler/high-il/border-control.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 3050 - (download) (annotate)
Thu Mar 12 13:40:58 2015 UTC (4 years, 3 months ago) by jhr
File size: 6504 byte(s)
  updates to OpenCL branch from vis12 branch
(* border-control.sml
 *
 * COPYRIGHT (c) 2015 The Diderot Project (http://diderot-language.cs.uchicago.edu)
 * All rights reserved.
 *
 * This pass inserts Inside tests to the HighIL representation to 
 *
 * TODO:
 *      merge inside tests for situations like F(x)+F(x).
 *)

structure BorderControl : sig

    val transform  : HighIL.program -> HighIL.program

  end = struct

    structure IL = HighIL
    structure Op = HighOps
    structure Ty = HighILTypes
    structure V = IL.Var
    structure DT = DomTree

  (* an environment that tracks available inside tests *)
    structure Env = RedBlackSetFn (struct
        type ord_key = IL.var * IL.var
        fun compare ((x, f), (y, g)) = (case V.compare(f, g)
               of EQUAL => V.compare(x, y)
                | order => order
              (* end case *))
      end)

    fun getRHS x = (case V.binding x
           of IL.VB_RHS(IL.OP arg) => SOME arg
            | IL.VB_RHS(IL.VAR x') => getRHS x'
            | IL.VB_RHS(IL.GLOBAL x') => getRHS(IL.GlobalVar.binding x')
            | _ => NONE
          (* end case *))

    fun getInsideTest cond = (case getRHS cond
           of SOME(Op.Inside _, [pos, fld]) => SOME(pos, fld)
            | _ => NONE
          (* end case *))

  (* return true of a base field definition has border control *)
    fun hasBorderCtl f = (case getRHS f
           of SOME(Op.Field _, [img, kern]) => let
                fun get img = (case getRHS img
                       of SOME(Op.Input _, _) => false
                        | SOME(Op.LoadImage _, _) => false
                        | SOME(Op.BorderCtlDefault _, _) => true
                        | SOME(Op.BorderCtlClamp _, _) => true
                        | SOME(Op.BorderCtlMirror _, _) => true
                        | SOME(Op.BorderCtlWrap _, _) => true
                        | _ => raise Fail(concat[
                              "bogus image binding ", V.toString img, " = ", IL.vbToString(V.binding img)
                            ])
                      (* end case *))
                in
                  get img
                end
            | _ => raise Fail(concat[
                  "bogus field binding ", V.toString f, " = ", IL.vbToString(V.binding f)
                ])
          (* end case *))

  (* for a node "x = Probe(f, pos)", replace it with
   *
   *    if Inside(pos, f)
   *      then x1 = Probe(f, pos)
   *      else x2 = ProbeWithCtl(f, pos)
   *    x = phi(x1, x2)
   *)
    fun rewriteProbe origNd = let
          val IL.ASSIGN{stm=(y, IL.OP(Op.Probe arg, [f, pos])), ...} = IL.Node.kind origNd
          val Ty.TensorTy[d] = V.ty pos
          val y1 = V.copy y
          val y2 = V.copy y
          val cond = V.new("isInside", Ty.BoolTy)
          val probeNd = IL.Node.mkASSIGN(y1, IL.OP(Op.Probe arg, [f, pos]))
          val probeWithCtlNd = IL.Node.mkASSIGN(y2, IL.OP(Op.ProbeWithCtl arg, [f, pos]))
          val insideTstNd = IL.Node.mkASSIGN(cond, IL.OP(Op.Inside d, [pos, f]))
          val condNd = IL.Node.mkCOND cond
          val joinNd = IL.Node.mkJOIN[(y, [SOME y1, SOME y2])]
          in
          (* update use counts *)
            HighILCensus.inc f; HighILCensus.inc f;
            HighILCensus.inc pos; HighILCensus.inc pos;
            HighILCensus.inc y1; HighILCensus.inc y2;
          (* hook up edges *)
            IL.Node.addEdge(insideTstNd, condNd);
            IL.Node.setTrueBranch(condNd, probeNd);
            IL.Node.setPred(probeNd, condNd);
            IL.Node.setFalseBranch(condNd, probeWithCtlNd);
            IL.Node.setPred(probeWithCtlNd, condNd);
            IL.Node.setEdgeMask(joinNd, [false, false]);
            IL.Node.addEdge(probeNd, joinNd);
            IL.Node.addEdge(probeWithCtlNd, joinNd);
          (* replace the original node with the new CFG *)
            IL.CFG.replaceNodeWithCFG(origNd, IL.CFG{entry=insideTstNd, exit=joinNd})
          end

    fun transformCFG cfg = let
        (* a list of nodes that need to be rewritten *)
          val workList = ref[]
        (* walk the dominator tree computing value numbers *)
          fun walk (env, nd) = let
                fun kids env = List.app (fn nd => walk (env, nd)) (DT.children nd)
                in
                  case IL.Node.kind nd
                   of IL.COND{cond, ...} => (case getInsideTest cond
                         of SOME inTst => (case DT.children nd
                               of [trueBr, falseBr] => (
                                  (* add the this test to the walk of the true branch *)
                                    walk (Env.add (env, inTst), trueBr);
                                    walk (env, falseBr))
                                | _ => kids env
                              (* end case *))
                          | NONE => kids env
                        (* end case *))
                    | IL.ASSIGN{stm=(y, IL.OP(Op.Probe _, [f, pos])), ...} =>
                        if Env.member(env, (pos, f))
                          then kids env (* no need for an inside test! *)
                        else if hasBorderCtl f
                          then (workList := nd :: !workList; kids env)
                          else kids env
                    | _ => kids env
                  (* end case *)
                end
          in
            DT.computeTree cfg;
          (* compute border control info *)
            walk (Env.empty, IL.CFG.entry cfg);
            DT.clear cfg;
          (* add inside tests to protect border control *)
            List.app rewriteProbe (!workList)
          end

    fun transform prog = let
          val IL.Program{props, globals, inputInit, globalInit, initially, strands} = prog
          val IL.Initially{isArray, rangeInit, iters, create} = initially
        (* transform a strand *)
          fun transformStrand (IL.Strand{name, params, state, stateInit, methods}) = let
                fun transformMeth (IL.Method{name, body}) = transformCFG body
                in
                  transformCFG stateInit;
                  List.app transformMeth methods
                end
          in
            (* NOTE: we don't process the inputInit code, because it is trivial *)
            transformCFG globalInit;
          (* transform the strand initialization code *)
            transformCFG rangeInit;
            transformCFG (#1 create);
          (* transform the strands *)
            List.app transformStrand strands;
            prog
          end

  end

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