Turn a tree of deps into a tree of uses

1 files changed, 20 insertions, 0 deletions

diff --git a/scheduling/MyRTLpathScheduleraux.ml b/scheduling/MyRTLpathScheduleraux.ml
index 183bb840..ebcbfe16 100644
--- a/scheduling/MyRTLpathScheduleraux.ml
+++ b/scheduling/MyRTLpathScheduleraux.ml
@@ -713,6 +713,26 @@ let merge_append _ x y = match x, y with
   | Some x, None | None, Some x -> Some x
   | Some x, Some y -> Some (x @ y)
 
+(* Turns a tree of dependencies (pc -> [pcs; that; depend; on pc]) into a tree of uses by
+ * "inverting" tree.
+ * Now, each pc has the pcs associated to it that depend on it, according to the original
+ * tree. *)
+let uses_of_deps p_ptree =
+  PTree.fold
+    (fun acc p vs ->
+      let acc = HashedSet.PSet.fold
+        (fun acc v ->
+          let old = ptree_get_or_default acc v HashedSet.PSet.empty in
+          let upd = HashedSet.PSet.add p old in
+          PTree.set v upd acc)
+        vs
+        acc
+      in
+      acc
+    )
+    p_ptree
+    PTree.empty
+
 (* Returns for every side-exit pc, a list of instructions that should be executed beforehand *)
 let downschedule_compensation_code sb code pm live_renames ~next_free_pc ~next_free_reg =
   (* TODO: Right now we are copying the instructions even if there are duplicates per