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

SCM Repository

[diderot] Diff of /branches/vis12-cl/src/compiler/translate/translate.sml
ViewVC logotype

Diff of /branches/vis12-cl/src/compiler/translate/translate.sml

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

revision 2824, Mon Nov 10 17:06:01 2014 UTC revision 2825, Mon Nov 10 21:06:31 2014 UTC
# Line 81  Line 81 
81                                          (* associated with this node. *)                                          (* associated with this node. *)
82          arity : int ref,                (* actual number of predecessors *)          arity : int ref,                (* actual number of predecessors *)
83          nd : IL.node,                   (* the CFG node for this pending join *)          nd : IL.node,                   (* the CFG node for this pending join *)
84          phiMap : IL.phi VMap.map ref,   (* a mapping from Simple AST variables that are assigned *)          phiMap : (IL.var * IL.var list) VMap.map ref,
85                                            (* a mapping from Simple AST variables that are assigned *)
86                                          (* to their phi nodes. *)                                          (* to their phi nodes. *)
87          predKill : bool array           (* killed predecessor edges (because of DIE or STABILIZE *)          predKill : bool array           (* killed predecessor edges (because of DIE or STABILIZE *)
88        }        }
# Line 140  Line 141 
141    (* complete a pending join operation by filling in the phi nodes from the phi map and    (* complete a pending join operation by filling in the phi nodes from the phi map and
142     * updating the environment.     * updating the environment.
143     *)     *)
144      fun commitJoin (joinStk, JOIN{env, arity, nd, phiMap, predKill}) = (case !arity      fun commitJoin (joinStk, JOIN{env, arity, nd, phiMap, predKill}) = let
145             of 0 => (env, NONE)            val IL.JOIN{preds, mask, phis, ...} = IL.Node.kind nd
146            (* update the predKill array based on reachability *)
147              val _ = let
148                    fun update (_, []) = ()
149                      | update (i, nd::nds) = (
150                          if IL.Node.isReachable nd then ()
151                          else if Array.sub(predKill, i) then ()
152                          else (arity := !arity-1; Array.update(predKill, i, true));
153                          update (i+1, nds))
154                    in
155                      update (0, !preds)
156                    end
157            (* compute the predecessor mask *)
158              val mask' = Array.foldr (op ::) [] predKill
159              in
160                mask := mask';
161                case !arity
162                 of 0 => env (* all incoming edges are fake *)
163              | 1 => let              | 1 => let
164                (* there is only one path to the join, so we do not need phi nodes, but                (* there is only one path to the join, so we do not need phi nodes, but
165                 * we still need to propogate assignments to the next join on the stack.                 * we still need to propogate assignments to the next join on the stack.
166                 *)                 *)
167                  val IL.ND{kind=IL.JOIN{phis, ...}, ...} = nd                    val ix = let (* find pred index of this join *)
                 val ix = let (* find pred of this join *)  
168                        fun find i = if Array.sub(predKill, i) then find(i+1) else i                        fun find i = if Array.sub(predKill, i) then find(i+1) else i
169                        in                        in
170                          find 0                          find 0
# Line 163  Line 180 
180                        end                        end
181                  val env = VMap.foldli doVar env (!phiMap)                  val env = VMap.foldli doVar env (!phiMap)
182                  in                  in
183                    (env, SOME nd)                      env
184                  end                  end
185              | n => if (n = Array.length predKill)                | nPreds => if (nPreds < Array.length predKill)
186                  then let                  then let
187                    val IL.ND{kind=IL.JOIN{phis, ...}, ...} = nd                      (* filter out variables that correspond to fake preds from the RHS of a phi *)
188                    fun doVar (srcVar, phi as (dstVar, _), (env, phis)) = (                        fun filterPhiRHS xs = let
189                                fun f ([], _, xs') = List.rev xs'
190                                  | f (x::xs, i, xs') = if Array.sub(predKill, i)
191                                        then f (xs, i+1, NONE :: xs')
192                                        else f (xs, i+1, (SOME x) :: xs')
193                                in
194                                  f (xs, 0, [])
195                                end
196                          fun doVar (srcVar, phi as (dstVar, srcVars), (env, phis)) = (
197  (*  (*
198  print(concat["doVar (", SimpleVar.uniqueNameOf srcVar, ", ", IL.phiToString phi, ", _) @ ", IL.Node.toString nd, "\n"]);  print(concat["doVar (", SimpleVar.uniqueNameOf srcVar, ", ", IL.phiToString phi, ", _) @ ", IL.Node.toString nd, "\n"]);
199  *)  *)
200                          recordAssign (joinStk, srcVar, dstVar);                          recordAssign (joinStk, srcVar, dstVar);
201                          (VMap.insert (env, srcVar, dstVar), phi::phis))                              (VMap.insert (env, srcVar, dstVar), (dstVar, filterPhiRHS srcVars) ::phis))
202                    val (env, phis') = VMap.foldli doVar (env, []) (!phiMap)                    val (env, phis') = VMap.foldli doVar (env, []) (!phiMap)
203                    in                    in
204                      phis := phis';                      phis := phis';
205                      (env, SOME nd)                          env
206                          end
207                      else let
208                        fun doVar (srcVar, phi as (dstVar, xs), (env, phis)) = let
209                              val xs = List.map SOME xs
210                              in
211    (*
212    print(concat["doVar (", SimpleVar.uniqueNameOf srcVar, ", ", IL.phiToString phi, ", _) @ ", IL.Node.toString nd, "\n"]);
213    *)
214                                recordAssign (joinStk, srcVar, dstVar);
215                                IL.Var.setBinding (dstVar, IL.VB_PHI xs);
216                                (VMap.insert (env, srcVar, dstVar), (dstVar, xs)::phis)
217                              end
218                        val (env, phis') = VMap.foldli doVar (env, []) (!phiMap)
219                        in
220                          phis := phis';
221                          env
222                        end
223                (* end case *)
224                    end                    end
                 else raise Fail "FIXME: prune killed paths."  
           (* end case *))  
225    
226    (* expression translation *)    (* expression translation *)
227      fun cvtExp (env : env, lhs, exp) = (case exp      fun cvtExp (env : env, lhs, exp) = (case exp
# Line 257  Line 298 
298                        end                        end
299                    | S.S_IfThenElse(x, b0, b1) => let                    | S.S_IfThenElse(x, b0, b1) => let
300                        val x' = lookup env x                        val x' = lookup env x
301                        val join = newJoin (env, 2)                        val join as JOIN{nd=joinNd, ...} = newJoin (env, 2)
302                        val (cfg0, _) = cvtBlock (state, env, (0, join)::joinStk, b0)                        val (cfg0, _) = cvtBlock (state, env, (0, join)::joinStk, b0)
303                        val (cfg1, _) = cvtBlock (state, env, (1, join)::joinStk, b1)                        val (cfg1, _) = cvtBlock (state, env, (1, join)::joinStk, b1)
304                        val cond = IL.Node.mkCOND {                        val cond = IL.Node.mkCOND {
# Line 265  Line 306 
306                                trueBranch = IL.Node.dummy,                                trueBranch = IL.Node.dummy,
307                                falseBranch = IL.Node.dummy                                falseBranch = IL.Node.dummy
308                              }                              }
309                        in                        fun addEdgeToJoin nd = (case IL.Node.kind nd
310                          IL.Node.addEdge (IL.CFG.exit cfg, cond);                               of IL.EXIT{succ, ...} => (
311                          case commitJoin (joinStk, join)                                    succ := SOME joinNd;
312                           of (env, SOME joinNd) => (                                    IL.Node.setPred (joinNd, nd))  (* will be converted to fake later *)
313                                  | _ => IL.Node.addEdge(nd, joinNd)
314                                (* end case *))
315                        (* package the CFG the represents the conditional (cond, two blocks, and join) *)
316    (* QUESTION: under what conditions do we insert an UNREACHABLE exit node?  Is it when there
317     * are no real predecessors to the join and the join stack is empty?
318     *)
319                          val condCFG = (
320                                if IL.CFG.isEmpty cfg0                                if IL.CFG.isEmpty cfg0
321                                  then (                                  then (
322                                    IL.Node.setTrueBranch (cond, joinNd);                                    IL.Node.setTrueBranch (cond, joinNd);
# Line 276  Line 324 
324                                  else (                                  else (
325                                    IL.Node.setTrueBranch (cond, IL.CFG.entry cfg0);                                    IL.Node.setTrueBranch (cond, IL.CFG.entry cfg0);
326                                    IL.Node.setPred (IL.CFG.entry cfg0, cond);                                    IL.Node.setPred (IL.CFG.entry cfg0, cond);
327                                    IL.Node.addEdge (IL.CFG.exit cfg0, joinNd));                                  addEdgeToJoin (IL.CFG.exit cfg0));
328                                if IL.CFG.isEmpty cfg1                                if IL.CFG.isEmpty cfg1
329                                  then (                                  then (
330                                    IL.Node.setFalseBranch (cond, joinNd);                                    IL.Node.setFalseBranch (cond, joinNd);
# Line 284  Line 332 
332                                  else (                                  else (
333                                    IL.Node.setFalseBranch (cond, IL.CFG.entry cfg1);                                    IL.Node.setFalseBranch (cond, IL.CFG.entry cfg1);
334                                    IL.Node.setPred (IL.CFG.entry cfg1, cond);                                    IL.Node.setPred (IL.CFG.entry cfg1, cond);
335                                    IL.Node.addEdge (IL.CFG.exit cfg1, joinNd));                                  addEdgeToJoin (IL.CFG.exit cfg1));
336                                cvt (                              IL.CFG{entry = cond, exit = joinNd})
337                                  env,                        val env = commitJoin (joinStk, join)
338                                  IL.CFG.concat (                        in
339                                    cfg,                          cvt (env, IL.CFG.concat (cfg, condCFG), stms)
                                   IL.CFG{entry = cond, exit = joinNd}),  
                                 stms))  
                         (* the join node has only zero predecessors, so  
                          * it was killed.  
                          *)  
                           | (env, NONE) => raise Fail "unimplemented" (* FIXME *)  
                         (* end case *)  
340                        end                        end
341                    | S.S_New(strandId, args) => let                    | S.S_New(strandId, args) => let
342                        val nd = IL.Node.mkNEW{                        val nd = IL.Node.mkNEW{

Legend:
Removed from v.2824  
changed lines
  Added in v.2825

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