From 6ee3ecb0edc17d61a515054952827c495cc03979 Mon Sep 17 00:00:00 2001
From: Cyril SIX <cyril.six@kalray.eu>
Date: Fri, 2 Apr 2021 11:41:41 +0200
Subject: Simple backedge detection (modified code from get_loop_headers)

---
 backend/LICMaux.ml | 40 ++++++++++++++++++++++++++++++++++++++++
 1 file changed, 40 insertions(+)

(limited to 'backend/LICMaux.ml')

diff --git a/backend/LICMaux.ml b/backend/LICMaux.ml
index 1f6b8817..96e8e8ae 100644
--- a/backend/LICMaux.ml
+++ b/backend/LICMaux.ml
@@ -80,6 +80,46 @@ let get_loop_headers code entrypoint = begin
   end
 end
 
+let get_loop_backedges code entrypoint = begin
+  debug "get_loop_backedges\n";
+  let visited = ref (PTree.map (fun n i -> Unvisited) code)
+  and loop_backedge = ref (PTree.map (fun n i -> None) code)
+  in let rec dfs_visit code origin = function
+  | [] -> ()
+  | node :: ln ->
+      debug "ENTERING node %d, REM are %a\n" (P.to_int node) print_intlist ln;
+      match (get_some @@ PTree.get node !visited) with
+      | Visited -> begin
+          debug "\tNode %d is already Visited, skipping\n" (P.to_int node);
+          dfs_visit code origin ln
+        end
+      | Processed -> begin
+          debug "Node %d is a loop header\n" (P.to_int node);
+          debug "The backedge is from %d\n" (P.to_int @@ get_some origin);
+          loop_backedge := PTree.set node origin !loop_backedge;
+          visited := PTree.set node Visited !visited;
+          dfs_visit code origin ln
+        end
+      | Unvisited -> begin
+          visited := PTree.set node Processed !visited;
+          debug "Node %d is Processed\n" (P.to_int node);
+          (match PTree.get node code with
+          | None -> failwith "No such node"
+          | Some i -> let next_visits = rtl_successors i in begin
+              debug "About to visit: %a\n" print_intlist next_visits;
+              dfs_visit code (Some node) next_visits
+            end);
+          debug "Node %d is Visited!\n" (P.to_int node);
+          visited := PTree.set node Visited !visited;
+          dfs_visit code origin ln
+        end
+  in begin
+    dfs_visit code None [entrypoint];
+    debug "LOOP BACKEDGES: %a\n" print_ptree_opint !loop_backedge;
+    !loop_backedge
+  end
+end
+
 
 module Dominator =
   struct
-- 
cgit 


From b042bca17696a9cb6e2be7bbdac9f08953fff527 Mon Sep 17 00:00:00 2001
From: Cyril SIX <cyril.six@kalray.eu>
Date: Fri, 2 Apr 2021 11:44:42 +0200
Subject: get_loop_headers simplification (using the new get_loop_backedges)

---
 backend/LICMaux.ml | 46 +++++++---------------------------------------
 1 file changed, 7 insertions(+), 39 deletions(-)

(limited to 'backend/LICMaux.ml')

diff --git a/backend/LICMaux.ml b/backend/LICMaux.ml
index 96e8e8ae..b88dbc2d 100644
--- a/backend/LICMaux.ml
+++ b/backend/LICMaux.ml
@@ -41,45 +41,6 @@ let rtl_successors = function
   *
   * If we come accross an edge to a Processed node, it's a loop!
   *)
-let get_loop_headers code entrypoint = begin
-  debug "get_loop_headers\n";
-  let visited = ref (PTree.map (fun n i -> Unvisited) code)
-  and is_loop_header = ref (PTree.map (fun n i -> false) code)
-  in let rec dfs_visit code = function
-  | [] -> ()
-  | node :: ln ->
-      debug "ENTERING node %d, REM are %a\n" (P.to_int node) print_intlist ln;
-      match (get_some @@ PTree.get node !visited) with
-      | Visited -> begin
-          debug "\tNode %d is already Visited, skipping\n" (P.to_int node);
-          dfs_visit code ln
-        end
-      | Processed -> begin
-          debug "Node %d is a loop header\n" (P.to_int node);
-          is_loop_header := PTree.set node true !is_loop_header;
-          visited := PTree.set node Visited !visited;
-          dfs_visit code ln
-        end
-      | Unvisited -> begin
-          visited := PTree.set node Processed !visited;
-          debug "Node %d is Processed\n" (P.to_int node);
-          (match PTree.get node code with
-          | None -> failwith "No such node"
-          | Some i -> let next_visits = rtl_successors i in begin
-              debug "About to visit: %a\n" print_intlist next_visits;
-              dfs_visit code next_visits
-            end);
-          debug "Node %d is Visited!\n" (P.to_int node);
-          visited := PTree.set node Visited !visited;
-          dfs_visit code ln
-        end
-  in begin
-    dfs_visit code [entrypoint];
-    debug "LOOP HEADERS: %a\n" print_ptree_bool !is_loop_header;
-    !is_loop_header
-  end
-end
-
 let get_loop_backedges code entrypoint = begin
   debug "get_loop_backedges\n";
   let visited = ref (PTree.map (fun n i -> Unvisited) code)
@@ -120,6 +81,13 @@ let get_loop_backedges code entrypoint = begin
   end
 end
 
+let get_loop_headers code entrypoint =
+  let backedges = get_loop_backedges code entrypoint in
+  PTree.map (fun _ ob ->
+    match ob with
+    | None -> false
+    | Some _ -> true
+  ) backedges
 
 module Dominator =
   struct
-- 
cgit