Split `transitive_dependencies` into its own function

Might be very slow

1 files changed, 31 insertions, 17 deletions

diff --git a/scheduling/MyRTLpathScheduleraux.ml b/scheduling/MyRTLpathScheduleraux.ml
index 2ec2fddc..b770de77 100644
--- a/scheduling/MyRTLpathScheduleraux.ml
+++ b/scheduling/MyRTLpathScheduleraux.ml
@@ -352,34 +352,48 @@ let intra_path_dependencies (sb : superblock) (code : code) =
   debug_flag := old_debug_flag;
   deps
 
-let moved_dependencies deps order side_exit_pc =
+let transitive_dependencies deps pc =
   let old_debug_flag = !debug_flag in
-  let side_exit_pc_idx = apply_map' order side_exit_pc in
-  let immediate_deps = ptree_get_or_default deps side_exit_pc HashedSet.PSet.empty in
-  let rec iter acc todo seen =
+  let immediate_deps = ptree_get_or_default deps pc HashedSet.PSet.empty in
+
+  let rec iter ~acc ~todo ~seen =
     match todo with
     | [] -> acc
-    | pc::todo -> (* NB: todo has just shrunk *)
-      if HashedSet.PSet.contains seen pc then
-        iter acc todo seen
+    | pc'::todo -> (* NB: todo has just shrunk *)
+      if HashedSet.PSet.contains seen pc' then
+        iter ~acc ~todo ~seen
       else
-
-      let dep_idx = apply_map' order pc in
-      if dep_idx > side_exit_pc_idx then (* begin
-        (* The former dependency has moved below the side exit *)
-        debug "pc: %d has moved below side exit with pc %d\n" (Camlcoq.P.to_int pc) (Camlcoq.P.to_int side_exit_pc); *)
-        let deps_of_dep = ptree_get_or_default deps pc HashedSet.PSet.empty in
+        let deps_of_dep = ptree_get_or_default deps pc' HashedSet.PSet.empty in
         let new_todo = HashedSet.PSet.subtract deps_of_dep acc |> HashedSet.PSet.elements in
-        iter (HashedSet.PSet.add pc acc) (new_todo @ todo) (HashedSet.PSet.add pc seen)
-      (* end *) else
-        iter acc todo (HashedSet.PSet.add pc seen)
+        iter
+          ~acc:(HashedSet.PSet.add pc' acc)
+          ~todo:(new_todo @ todo)
+          ~seen:(HashedSet.PSet.add pc' seen)
   in
   let transitive_dependencies =
-    iter HashedSet.PSet.empty (HashedSet.PSet.elements immediate_deps) HashedSet.PSet.empty
+    iter
+      ~acc:HashedSet.PSet.empty
+      ~todo:(HashedSet.PSet.elements immediate_deps)
+      ~seen:HashedSet.PSet.empty
   in
   debug_flag := old_debug_flag;
   transitive_dependencies
 
+let moved_dependencies deps order side_exit_pc =
+  let old_debug_flag = !debug_flag in
+
+  let dependencies = transitive_dependencies deps side_exit_pc in
+  let side_exit_pc_idx = apply_map' order side_exit_pc in
+  let moved_dependencies =
+    HashedSet.PSet.filter
+      (fun pc ->
+        let dep_idx = apply_map' order pc in
+        dep_idx > side_exit_pc_idx )
+      dependencies
+  in
+  debug_flag := old_debug_flag;
+  moved_dependencies
+
 let update_liveins liveins live_renames =
   PTree.map
   (fun pc liveregs ->