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

SCM Repository

[diderot] Diff of /branches/vis15/src/compiler/cfg-ir/check-ir-fn.sml
ViewVC logotype

Diff of /branches/vis15/src/compiler/cfg-ir/check-ir-fn.sml

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

branches/vis15/src/compiler/cfg-ir/check-il-fn.sml revision 3473, Wed Dec 2 17:57:53 2015 UTC branches/vis15/src/compiler/cfg-ir/check-ir-fn.sml revision 3475, Wed Dec 2 18:48:58 2015 UTC
# Line 1  Line 1 
1  (* check-il-fn.sml  (* check-ir-fn.sml
2   *   *
3   * This code is part of the Diderot Project (http://diderot-language.cs.uchicago.edu)   * This code is part of the Diderot Project (http://diderot-language.cs.uchicago.edu)
4   *   *
5   * COPYRIGHT (c) 2015 The University of Chicago   * COPYRIGHT (c) 2015 The University of Chicago
6   * All rights reserved.   * All rights reserved.
7   *   *
8   * Correctness checker for SSA-based ILs.   * Correctness checker for SSA-based IRs.
9   *   *
10   * TODO:   * TODO:
11   *      check that the state variables and method stateOut variables are all defined.   *      check that the state variables and method stateOut variables are all defined.
# Line 27  Line 27 
27    
28    end    end
29    
30  functor CheckILFn (  functor CheckIRFn (
31    
32      structure IL : SSA      structure IR : SSA
33      structure OpTy : OPERATOR_TY      structure OpTy : OPERATOR_TY
34          where type rator = IL.Op.rator          where type rator = IR.Op.rator
35          where type ty = IL.Ty.ty          where type ty = IR.Ty.ty
36    
37    ) : sig    ) : sig
38    
# Line 40  Line 40 
40     * identify the phase that the check follows and the return result will be true     * identify the phase that the check follows and the return result will be true
41     * if any errors were detected.     * if any errors were detected.
42     *)     *)
43      val check : string * IL.program -> bool      val check : string * IR.program -> bool
44    
45    end = struct    end = struct
46    
47      structure IL = IL      structure IR = IR
48      structure Ty = IL.Ty      structure Ty = IR.Ty
49      structure V = IL.Var      structure V = IR.Var
50      structure VSet = V.Set      structure VSet = V.Set
51    
52    (* forward analysis to determine the variables that are available in blocks *)    (* forward analysis to determine the variables that are available in blocks *)
53      structure Avail = ForwardDFAFn (      structure Avail = ForwardDFAFn (
54        struct        struct
55    
56          structure IL = IL          structure IR = IR
57          type t = VSet.set          type t = VSet.set
58    
59          val bottom = VSet.empty          val bottom = VSet.empty
60    
61          fun join inputs = List.foldl VSet.union bottom inputs          fun join inputs = List.foldl VSet.union bottom inputs
62    
63          fun transfer (input, nd as IL.ND{kind, ...}) = (case kind          fun transfer (input, nd as IR.ND{kind, ...}) = (case kind
64                 of IL.JOIN{phis, ...} => let                 of IR.JOIN{phis, ...} => let
65                    (* add the lhs of the phi node.  We do not remove the rhs variables, since                    (* add the lhs of the phi node.  We do not remove the rhs variables, since
66                     * after value numbering, they may have further uses.                     * after value numbering, they may have further uses.
67                     *)                     *)
# Line 70  Line 70 
70                      in                      in
71                        output                        output
72                      end                      end
73                  | IL.ASSIGN{stm=(y, _), ...} => VSet.add(input, y)                  | IR.ASSIGN{stm=(y, _), ...} => VSet.add(input, y)
74                  | IL.MASSIGN{stm=(ys, _, _), ...} => VSet.addList(input, ys)                  | IR.MASSIGN{stm=(ys, _, _), ...} => VSet.addList(input, ys)
75                  | _ => input                  | _ => input
76                 (* end case *))                 (* end case *))
77    
78          val same = VSet.equal          val same = VSet.equal
79    
80          fun toString vs = let          fun toString vs = let
81                fun f (v, []) = [IL.Var.toString v, "}"]                fun f (v, []) = [IR.Var.toString v, "}"]
82                  | f (v, l) = IL.Var.toString v :: "," :: l                  | f (v, l) = IR.Var.toString v :: "," :: l
83                in                in
84                  if VSet.isEmpty vs then "{}" else String.concat("{" :: VSet.foldl f [] vs)                  if VSet.isEmpty vs then "{}" else String.concat("{" :: VSet.foldl f [] vs)
85                end                end
# Line 87  Line 87 
87        end)        end)
88    
89      datatype token      datatype token
90        = NL | S of string | A of Atom.atom | V of IL.var | VTYS of IL.var list        = NL | S of string | A of Atom.atom | V of IR.var | VTYS of IR.var list
91        | TY of Ty.ty | TYS of Ty.ty list        | TY of Ty.ty | TYS of Ty.ty list
92        | ND of IL.node        | ND of IR.node
93    
94      fun error errBuf toks = let      fun error errBuf toks = let
95            fun tok2str NL = "\n  ** "            fun tok2str NL = "\n  ** "
# Line 103  Line 103 
103              | tok2str (TYS tys) = String.concat[              | tok2str (TYS tys) = String.concat[
104                    "(", String.concatWith " * " (List.map Ty.toString tys), ")"                    "(", String.concatWith " * " (List.map Ty.toString tys), ")"
105                  ]                  ]
106              | tok2str (ND nd) = IL.Node.toString nd              | tok2str (ND nd) = IR.Node.toString nd
107            in            in
108              errBuf := concat ("**** Error: " :: List.map tok2str toks)              errBuf := concat ("**** Error: " :: List.map tok2str toks)
109                :: !errBuf                :: !errBuf
# Line 115  Line 115 
115                  then ()                  then ()
116                  else errFn [                  else errFn [
117                      S "variable ", V x, S " is not bound in", NL,                      S "variable ", V x, S " is not bound in", NL,
118                      S(IL.assignToString(y, rhs))                      S(IR.assignToString(y, rhs))
119                    ]                    ]
120            fun tyError (ty1, ty2) = errFn [            fun tyError (ty1, ty2) = errFn [
121                    S "type mismatch in \"", S(IL.assignToString (y, rhs)), S "\"",                    S "type mismatch in \"", S(IR.assignToString (y, rhs)), S "\"",
122                    NL, S "lhs: ", TY ty1, NL, S "rhs: ", TY ty2                    NL, S "lhs: ", TY ty1, NL, S "rhs: ", TY ty2
123                  ]                  ]
124            fun checkTys (ty1, ty2) = if Ty.same(ty1, ty2)            fun checkTys (ty1, ty2) = if Ty.same(ty1, ty2)
# Line 129  Line 129 
129                if VSet.member(bvs, y)                if VSet.member(bvs, y)
130                  then errFn [                  then errFn [
131                      S "variable ", V y, S " is bound twice in", NL,                      S "variable ", V y, S " is bound twice in", NL,
132                      S(IL.assignToString (y, rhs))                      S(IR.assignToString (y, rhs))
133                    ]                    ]
134                  else ();                  else ();
135                case rhs                case rhs
136                 of IL.GLOBAL x => checkTys(V.ty y, IL.GlobalVar.ty x)                 of IR.GLOBAL x => checkTys(V.ty y, IR.GlobalVar.ty x)
137                  | IL.STATE x => checkTys(V.ty y, IL.StateVar.ty x)                  | IR.STATE x => checkTys(V.ty y, IR.StateVar.ty x)
138                  | IL.VAR x => (                  | IR.VAR x => (
139                      checkVar x;                      checkVar x;
140                      checkTys (V.ty y, V.ty x))                      checkTys (V.ty y, V.ty x))
141                  | IL.LIT lit => let                  | IR.LIT lit => let
142                      val ty = (case lit                      val ty = (case lit
143                             of Literal.Int _ => Ty.intTy                             of Literal.Int _ => Ty.intTy
144                              | Literal.Real _ => Ty.realTy                              | Literal.Real _ => Ty.realTy
# Line 148  Line 148 
148                      in                      in
149                        checkTys (V.ty y, ty)                        checkTys (V.ty y, ty)
150                      end                      end
151                  | IL.OP(rator, xs) => let                  | IR.OP(rator, xs) => let
152                      val (resTy, argTys) = OpTy.sigOf rator                      val (resTy, argTys) = OpTy.sigOf rator
153                      in                      in
154                        List.app checkVar xs;                        List.app checkVar xs;
# Line 156  Line 156 
156                        if ListPair.allEq (fn (x, ty) => Ty.same(V.ty x, ty)) (xs, argTys)                        if ListPair.allEq (fn (x, ty) => Ty.same(V.ty x, ty)) (xs, argTys)
157                          then ()                          then ()
158                          else errFn [                          else errFn [
159                              S "argument type mismatch in \"", S(IL.assignToString (y, rhs)), S "\"",                              S "argument type mismatch in \"", S(IR.assignToString (y, rhs)), S "\"",
160                              NL, S "expected: ", TYS argTys,                              NL, S "expected: ", TYS argTys,
161                              NL, S "found:    ", VTYS xs                              NL, S "found:    ", VTYS xs
162                            ]                            ]
163                      end                      end
164                  | IL.CONS(xs, ty) => (                  | IR.CONS(xs, ty) => (
165                      List.app checkVar xs;                      List.app checkVar xs;
166                      if OpTy.typeOfCons (ty, List.map V.ty xs)                      if OpTy.typeOfCons (ty, List.map V.ty xs)
167                        then checkTys (V.ty y, ty)                        then checkTys (V.ty y, ty)
168                        else errFn [S "invalid ", S(IL.assignToString(y, rhs))])                        else errFn [S "invalid ", S(IR.assignToString(y, rhs))])
169                  | IL.SEQ(xs, ty) => (                  | IR.SEQ(xs, ty) => (
170                      List.app checkVar xs;                      List.app checkVar xs;
171  (* FIXME: check types of sequence elements *)())  (* FIXME: check types of sequence elements *)())
172                  | IL.EINAPP(ein, xs) => (                  | IR.EINAPP(ein, xs) => (
173                      List.app checkVar xs;                      List.app checkVar xs;
174  (* FIXME: check ein *)())  (* FIXME: check ein *)())
175                (* end case *);                (* end case *);
# Line 181  Line 181 
181            fun checkBind y = if VSet.member(bvs, y)            fun checkBind y = if VSet.member(bvs, y)
182                  then errFn [                  then errFn [
183                      S "variable ", V y, S " is bound twice in", NL,                      S "variable ", V y, S " is bound twice in", NL,
184                      S(IL.massignToString stm)                      S(IR.massignToString stm)
185                    ]                    ]
186                  else ()                  else ()
187          (* check a variable use *)          (* check a variable use *)
# Line 189  Line 189 
189                  then ()                  then ()
190                  else errFn [                  else errFn [
191                      S "variable ", V x, S " is not bound in", NL,                      S "variable ", V x, S " is not bound in", NL,
192                      S(IL.massignToString stm)                      S(IR.massignToString stm)
193                    ]                    ]
194            fun tyError (ty1, ty2) = errFn [            fun tyError (ty1, ty2) = errFn [
195                    S "type mismatch in \"", S(IL.massignToString stm), S "\"",                    S "type mismatch in \"", S(IR.massignToString stm), S "\"",
196                    NL, S "lhs: ", TY ty1, NL, S "rhs: ", TY ty2                    NL, S "lhs: ", TY ty1, NL, S "rhs: ", TY ty2
197                  ]                  ]
198            in            in
# Line 209  Line 209 
209                  if ListPair.allEq (fn (x, ty) => Ty.same(V.ty x, ty)) (xs, argTys)                  if ListPair.allEq (fn (x, ty) => Ty.same(V.ty x, ty)) (xs, argTys)
210                    then ()                    then ()
211                    else errFn [                    else errFn [
212                        S "argument type mismatch in \"", S(IL.massignToString stm), S "\"",                        S "argument type mismatch in \"", S(IR.massignToString stm), S "\"",
213                        NL, S "expected: ", TYS argTys,                        NL, S "expected: ", TYS argTys,
214                        NL, S "found:    ", VTYS xs                        NL, S "found:    ", VTYS xs
215                      ]                      ]
# Line 223  Line 223 
223            fun chkTy x = if Ty.same(V.ty x, ty)            fun chkTy x = if Ty.same(V.ty x, ty)
224                    then ()                    then ()
225                    else errFn [                    else errFn [
226                        S "type mismatch in \"", S(IL.phiToString (y, xs)), S "\"", NL,                        S "type mismatch in \"", S(IR.phiToString (y, xs)), S "\"", NL,
227                        S "typeof(", V y, S "): ", TY ty, NL,                        S "typeof(", V y, S "): ", TY ty, NL,
228                        S "typeof(", V x, S "): ", TY(V.ty x)                        S "typeof(", V x, S "): ", TY(V.ty x)
229                      ]                      ]
# Line 236  Line 236 
236              if VSet.member(bvs, y)              if VSet.member(bvs, y)
237                then errFn [                then errFn [
238                    S "variable ", V y, S " is bound twice in", NL,                    S "variable ", V y, S " is bound twice in", NL,
239                    S(IL.phiToString (y, xs))                    S(IR.phiToString (y, xs))
240                  ]                  ]
241                else ();                else ();
242            (* check that rhs vars have the correct type *)            (* check that rhs vars have the correct type *)
243              chkRHS (mask, xs)              chkRHS (mask, xs)
244            end            end
245    
246      fun check (phase, IL.Program{globals, props, inputInit, globalInit, initially, strands}) = let      fun check (phase, IR.Program{globals, props, inputInit, globalInit, initially, strands}) = let
247            val errBuf = ref []            val errBuf = ref []
248            val errFn = error errBuf            val errFn = error errBuf
249            fun final () = (case !errBuf            fun final () = (case !errBuf
250                   of [] => false                   of [] => false
251                    | errs => (                    | errs => (
252                        Log.msg(concat["********** IL Errors detected after ", phase, " **********\n"]);                        Log.msg(concat["********** IR Errors detected after ", phase, " **********\n"]);
253                        List.app (fn msg => Log.msg(msg ^ "\n")) (List.rev errs);                        List.app (fn msg => Log.msg(msg ^ "\n")) (List.rev errs);
254                        true)                        true)
255                  (* end case *))                  (* end case *))
# Line 265  Line 265 
265                 * list.                 * list.
266                 *)                 *)
267                  fun checkEdges nd = let                  fun checkEdges nd = let
268                        fun eqNd nd' = IL.Node.same(nd, nd')                        fun eqNd nd' = IR.Node.same(nd, nd')
269                        fun chkPred src = if List.exists eqNd (IL.Node.succs src)                        fun chkPred src = if List.exists eqNd (IR.Node.succs src)
270                              then ()                              then ()
271                              else errFn [                              else errFn [
272                                  S "predecessor edge from ", ND nd, S " -> ", ND src,                                  S "predecessor edge from ", ND nd, S " -> ", ND src,
273                                  S " not matched by successor edge"                                  S " not matched by successor edge"
274                                ]                                ]
275                        fun chkSucc dst = if List.exists eqNd (IL.Node.preds dst)                        fun chkSucc dst = if List.exists eqNd (IR.Node.preds dst)
276                              then ()                              then ()
277                              else errFn [                              else errFn [
278                                  S "successor edge from ", ND nd, S " -> ", ND dst,                                  S "successor edge from ", ND nd, S " -> ", ND dst,
279                                  S " not matched by predecessor edge"                                  S " not matched by predecessor edge"
280                                ]                                ]
281                        in                        in
282                          List.app chkPred (IL.Node.preds nd);                          List.app chkPred (IR.Node.preds nd);
283                          List.app chkSucc (IL.Node.succs nd)                          List.app chkSucc (IR.Node.succs nd)
284                        end                        end
285                  fun checkNd (nd as IL.ND{kind, ...}) = (case kind                  fun checkNd (nd as IR.ND{kind, ...}) = (case kind
286                         of IL.NULL => errFn [S "unexpected ", ND nd]                         of IR.NULL => errFn [S "unexpected ", ND nd]
287                          | IL.JOIN{mask, phis, ...} =>                          | IR.JOIN{mask, phis, ...} =>
288                              List.app                              List.app
289                                (checkPhi (nd, VSet.union(Avail.inValue nd, bvs), !mask))                                (checkPhi (nd, VSet.union(Avail.inValue nd, bvs), !mask))
290                                  (!phis)                                  (!phis)
291                          | IL.COND{cond, ...} =>                          | IR.COND{cond, ...} =>
292                              if VSet.member(Avail.inValue nd, cond)                              if VSet.member(Avail.inValue nd, cond)
293                              orelse VSet.member(bvs, cond)                              orelse VSet.member(bvs, cond)
294                                then ()                                then ()
295                                else errFn [S "unbound variable ", V cond, S " in conditional"]                                else errFn [S "unbound variable ", V cond, S " in conditional"]
296                          | IL.FOREACH{phis, mask, var, src, ...} => (                          | IR.FOREACH{phis, mask, var, src, ...} => (
297                              if VSet.member(Avail.inValue nd, src)                              if VSet.member(Avail.inValue nd, src)
298                              orelse VSet.member(bvs, src)                              orelse VSet.member(bvs, src)
299                                then ()                                then ()
# Line 301  Line 301 
301                              List.app                              List.app
302                                (checkPhi (nd, VSet.union(Avail.inValue nd, bvs), !mask))                                (checkPhi (nd, VSet.union(Avail.inValue nd, bvs), !mask))
303                                  (!phis))                                  (!phis))
304                          | IL.ASSIGN{stm, ...} =>                          | IR.ASSIGN{stm, ...} =>
305                              ignore (checkAssign (stm, VSet.union(Avail.inValue nd, bvs)))                              ignore (checkAssign (stm, VSet.union(Avail.inValue nd, bvs)))
306                          | IL.MASSIGN{stm, ...} =>                          | IR.MASSIGN{stm, ...} =>
307                              ignore (checkMAssign (stm, VSet.union(Avail.inValue nd, bvs)))                              ignore (checkMAssign (stm, VSet.union(Avail.inValue nd, bvs)))
308                          | IL.GASSIGN{lhs, rhs, ...} => let                          | IR.GASSIGN{lhs, rhs, ...} => let
309                              val bvs = VSet.union(Avail.inValue nd, bvs)                              val bvs = VSet.union(Avail.inValue nd, bvs)
310                              in                              in
311                                if VSet.member(bvs, rhs)                                if VSet.member(bvs, rhs)
312                                  then ()                                  then ()
313                                  else errFn [                                  else errFn [
314                                      S "variable ", V rhs, S " is not bound in global assignment ",                                      S "variable ", V rhs, S " is not bound in global assignment ",
315                                      S(IL.GlobalVar.toString lhs)                                      S(IR.GlobalVar.toString lhs)
316                                    ];                                    ];
317                                if Ty.same(IL.GlobalVar.ty lhs, V.ty rhs)                                if Ty.same(IR.GlobalVar.ty lhs, V.ty rhs)
318                                  then ()                                  then ()
319                                  else errFn [                                  else errFn [
320                                      S "type mismatch in \"", S(IL.GlobalVar.toString lhs),                                      S "type mismatch in \"", S(IR.GlobalVar.toString lhs),
321                                      S " = ", S(V.toString rhs), S "\"",                                      S " = ", S(V.toString rhs), S "\"",
322                                      NL, S "lhs: ", TY(IL.GlobalVar.ty lhs),                                      NL, S "lhs: ", TY(IR.GlobalVar.ty lhs),
323                                      NL, S "rhs: ", TY(V.ty rhs)                                      NL, S "rhs: ", TY(V.ty rhs)
324                                    ]                                    ]
325                              end                              end
326                          | IL.NEW{strand, args, ...} => let                          | IR.NEW{strand, args, ...} => let
327                              val bvs = VSet.union(Avail.inValue nd, bvs)                              val bvs = VSet.union(Avail.inValue nd, bvs)
328                            (* check a variable use *)                            (* check a variable use *)
329                              fun checkVar x = if VSet.member(bvs, x)                              fun checkVar x = if VSet.member(bvs, x)
# Line 335  Line 335 
335                              in                              in
336                                List.app checkVar args                                List.app checkVar args
337                              end                              end
338                          | IL.SAVE{lhs, rhs, ...} => let                          | IR.SAVE{lhs, rhs, ...} => let
339                              val bvs = VSet.union(Avail.inValue nd, bvs)                              val bvs = VSet.union(Avail.inValue nd, bvs)
340                              in                              in
341                                if VSet.member(bvs, rhs)                                if VSet.member(bvs, rhs)
342                                  then ()                                  then ()
343                                  else errFn [                                  else errFn [
344                                      S "variable ", V rhs, S " is not bound in save ",                                      S "variable ", V rhs, S " is not bound in save ",
345                                      S(IL.StateVar.toString lhs)                                      S(IR.StateVar.toString lhs)
346                                    ];                                    ];
347                                if Ty.same(IL.StateVar.ty lhs, V.ty rhs)                                if Ty.same(IR.StateVar.ty lhs, V.ty rhs)
348                                  then ()                                  then ()
349                                  else errFn [                                  else errFn [
350                                      S "type mismatch in \"", S(IL.StateVar.toString lhs),                                      S "type mismatch in \"", S(IR.StateVar.toString lhs),
351                                      S " = ", S(V.toString rhs), S "\"",                                      S " = ", S(V.toString rhs), S "\"",
352                                      NL, S "lhs: ", TY(IL.StateVar.ty lhs),                                      NL, S "lhs: ", TY(IR.StateVar.ty lhs),
353                                      NL, S "rhs: ", TY(V.ty rhs)                                      NL, S "rhs: ", TY(V.ty rhs)
354                                    ]                                    ]
355                              end                              end
# Line 362  Line 362 
362                    Avail.scrub nodes                    Avail.scrub nodes
363                  end                  end
364          (* check a strand definition *)          (* check a strand definition *)
365            fun checkStrand (IL.Strand{name, params, state, stateInit, methods}) = let            fun checkStrand (IR.Strand{name, params, state, stateInit, methods}) = let
366                  val nStateVars = List.length state                  val nStateVars = List.length state
367                  val extraVars = params                  val extraVars = params
368                  fun checkMethod (IL.Method{name, body, ...}) = checkCFG (extraVars, body)                  fun checkMethod (IR.Method{name, body, ...}) = checkCFG (extraVars, body)
369  (*DEBUG*)handle ex => raise ex  (*DEBUG*)handle ex => raise ex
370                  in                  in
371                    checkCFG (extraVars, stateInit)                    checkCFG (extraVars, stateInit)

Legend:
Removed from v.3473  
changed lines
  Added in v.3475

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