summaryrefslogtreecommitdiff
path: root/src/untangle.sml
diff options
context:
space:
mode:
authorGravatar Adam Chlipala <adamc@hcoop.net>2008-07-17 12:19:44 -0400
committerGravatar Adam Chlipala <adamc@hcoop.net>2008-07-17 12:19:44 -0400
commit1527e77c3c2c99fbb9fb832250a6cc00c06d70b0 (patch)
treefd4a0b102dcd522d169c716f72d4f16971ddeada /src/untangle.sml
parentd5fd0e7403767670197f0422c99ba62176323624 (diff)
Untangle
Diffstat (limited to 'src/untangle.sml')
-rw-r--r--src/untangle.sml192
1 files changed, 192 insertions, 0 deletions
diff --git a/src/untangle.sml b/src/untangle.sml
new file mode 100644
index 00000000..f3e220b2
--- /dev/null
+++ b/src/untangle.sml
@@ -0,0 +1,192 @@
+(* Copyright (c) 2008, Adam Chlipala
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are met:
+ *
+ * - Redistributions of source code must retain the above copyright notice,
+ * this list of conditions and the following disclaimer.
+ * - Redistributions in binary form must reproduce the above copyright notice,
+ * this list of conditions and the following disclaimer in the documentation
+ * and/or other materials provided with the distribution.
+ * - The names of contributors may not be used to endorse or promote products
+ * derived from this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ *)
+
+structure Untangle :> UNTANGLE = struct
+
+open Mono
+
+structure U = MonoUtil
+structure E = MonoEnv
+
+structure IS = IntBinarySet
+structure IM = IntBinaryMap
+
+fun typ (k, s) = s
+
+fun exp (e, s) =
+ case e of
+ ENamed n => IS.add (s, n)
+
+ | _ => s
+
+fun untangle file =
+ let
+ fun decl (dAll as (d, loc)) =
+ case d of
+ DValRec vis =>
+ let
+ val thisGroup = foldl (fn ((_, n, _, _, _), thisGroup) =>
+ IS.add (thisGroup, n)) IS.empty vis
+
+ val used = foldl (fn ((_, n, _, e, _), used) =>
+ let
+ val usedHere = U.Exp.fold {typ = typ,
+ exp = exp} IS.empty e
+ in
+ IM.insert (used, n, IS.intersection (usedHere, thisGroup))
+ end)
+ IM.empty vis
+
+ fun p_graph reachable =
+ IM.appi (fn (n, reachableHere) =>
+ (print (Int.toString n);
+ print ":";
+ IS.app (fn n' => (print " ";
+ print (Int.toString n'))) reachableHere;
+ print "\n")) reachable
+
+ (*val () = print "used:\n"
+ val () = p_graph used*)
+
+ fun expand reachable =
+ let
+ val changed = ref false
+
+ val reachable =
+ IM.mapi (fn (n, reachableHere) =>
+ IS.foldl (fn (n', reachableHere) =>
+ let
+ val more = valOf (IM.find (reachable, n'))
+ in
+ if IS.isEmpty (IS.difference (more, reachableHere)) then
+ reachableHere
+ else
+ (changed := true;
+ IS.union (more, reachableHere))
+ end)
+ reachableHere reachableHere) reachable
+ in
+ (reachable, !changed)
+ end
+
+ fun iterate reachable =
+ let
+ val (reachable, changed) = expand reachable
+ in
+ if changed then
+ iterate reachable
+ else
+ reachable
+ end
+
+ val reachable = iterate used
+
+ (*val () = print "reachable:\n"
+ val () = p_graph reachable*)
+
+ fun sccs (nodes, acc) =
+ case IS.find (fn _ => true) nodes of
+ NONE => acc
+ | SOME rep =>
+ let
+ val reachableHere = valOf (IM.find (reachable, rep))
+
+ val (nodes, scc) = IS.foldl (fn (node, (nodes, scc)) =>
+ if node = rep then
+ (nodes, scc)
+ else
+ let
+ val reachableThere =
+ valOf (IM.find (reachable, node))
+ in
+ if IS.member (reachableThere, rep) then
+ (IS.delete (nodes, node),
+ IS.add (scc, node))
+ else
+ (nodes, scc)
+ end)
+ (IS.delete (nodes, rep), IS.singleton rep) reachableHere
+ in
+ sccs (nodes, scc :: acc)
+ end
+
+ val sccs = rev (sccs (thisGroup, []))
+ (*val () = app (fn nodes => (print "SCC:";
+ IS.app (fn i => (print " ";
+ print (Int.toString i))) nodes;
+ print "\n")) sccs*)
+
+ val sccs = ListMergeSort.sort (fn (nodes1, nodes2) =>
+ let
+ val node1 = valOf (IS.find (fn _ => true) nodes1)
+ val node2 = valOf (IS.find (fn _ => true) nodes2)
+ val reachable1 = valOf (IM.find (reachable, node1))
+ in
+ IS.member (reachable1, node2)
+ end) sccs
+ (*val () = app (fn nodes => (print "SCC':";
+ IS.app (fn i => (print " ";
+ print (Int.toString i))) nodes;
+ print "\n")) sccs*)
+
+ fun isNonrec nodes =
+ case IS.find (fn _ => true) nodes of
+ NONE => NONE
+ | SOME node =>
+ let
+ val nodes = IS.delete (nodes, node)
+ val reachableHere = valOf (IM.find (reachable, node))
+ in
+ if IS.isEmpty nodes then
+ if IS.member (reachableHere, node) then
+ NONE
+ else
+ SOME node
+ else
+ NONE
+ end
+
+ val ds = map (fn nodes =>
+ case isNonrec nodes of
+ SOME node =>
+ let
+ val vi = valOf (List.find (fn (_, n, _, _, _) => n = node) vis)
+ in
+ (DVal vi, loc)
+ end
+ | NONE =>
+ (DValRec (List.filter (fn (_, n, _, _, _) => IS.member (nodes, n)) vis), loc))
+ sccs
+ in
+ ds
+ end
+ | _ => [dAll]
+ in
+ ListUtil.mapConcat decl file
+ end
+
+end