From da34700998cbaf705c761a3d5b3a4e14994623e4 Mon Sep 17 00:00:00 2001
From: Yann Herklotz <git@yannherklotz.com>
Date: Wed, 6 Jan 2021 18:59:07 +0000
Subject: Add comments to pipelining code

---
 src/SoftwarePipelining/SPBasic.ml            |  8 ++++----
 src/SoftwarePipelining/SPIMS.ml              | 20 ++++++++++++++++----
 src/SoftwarePipelining/SoftwarePipelining.ml |  6 +++++-
 3 files changed, 25 insertions(+), 9 deletions(-)

(limited to 'src')

diff --git a/src/SoftwarePipelining/SPBasic.ml b/src/SoftwarePipelining/SPBasic.ml
index df7342f..32234b8 100644
--- a/src/SoftwarePipelining/SPBasic.ml
+++ b/src/SoftwarePipelining/SPBasic.ml
@@ -1,5 +1,5 @@
 (***********************************************************************)
-(*                                                                     *)
+ (*                                                                     *)
 (*                        Compcert Extensions                          *)
 (*                                                                     *)
 (*                       Jean-Baptiste Tristan                         *)
@@ -604,12 +604,12 @@ let latency n = (* A raffiner *)
       | Omove -> 1
       (*| Oaddimm _ -> 1*)
       (*| Oadd -> 2*)
-      | Omul -> 3
+      | Omul -> 4
       | Odiv -> 30
-      | Omulimm _ -> 5
+      | Omulimm _ -> 4
       | _ -> 2
     end
-  | Iload _ -> 10
+  | Iload _ -> 1
   (*    | Ialloc _ -> 20*)
   | _ -> 1
 
diff --git a/src/SoftwarePipelining/SPIMS.ml b/src/SoftwarePipelining/SPIMS.ml
index 1933268..0e19dec 100644
--- a/src/SoftwarePipelining/SPIMS.ml
+++ b/src/SoftwarePipelining/SPIMS.ml
@@ -82,7 +82,7 @@ let bad_successors ddg schedule node ii =
       | None -> bad
     ) succs []
 
-let get_condition ddg = 
+let get_condition ddg =
   let cond = G.fold_vertex (fun node cond ->
       if is_cond node then Some node else cond
     ) ddg None in
@@ -90,6 +90,10 @@ let get_condition ddg =
   | Some cond -> cond
   | None -> failwith "The loop does not contain a condition. Aborting\n"
 
+(* Perform iterative modulo scheduling, using a heuristic for the next instruction to schedule
+ * [heightr], the data dependency graph to schedule [ddg], the minimum II [min_ii] and the maximum
+ * II [max_interval].
+ *)
 let modulo_schedule heightr ddg min_ii max_interval =
 
   let ii = ref (min_ii - 1) in 
@@ -104,12 +108,18 @@ let modulo_schedule heightr ddg min_ii max_interval =
     (* Printf.printf "NOUVEAU II %i \n" !ii; *)
     let budget = ref (G.nb_vertex ddg * 10) in
     let lasttime = ref NI.empty in
+    (* Create the map with schedules, and add the schedule for the condition.  This should go at the
+     * end, but in this case is set to the start. *)
     let schedtime = ref (NI.add cond (Some 0) NI.empty) in
+    (* Create an array that is as large as the current II, which will determine where each
+     * instruction will be placed. *)
     let mrt = Array.make !ii None in
+    (* Set the condition to be the initial instruction at time 0. *)
     Array.set mrt 0 (Some cond);
 
     while (!budget > 0 && not (finished ddg !schedtime)) do (* Pretty inefficient *)
-      budget := !budget - 1; 
+      budget := !budget - 1;
+      (* Get next instruction to schedule. *)
       let h = heightr ddg !schedtime in
       let mintime = estart ddg !schedtime h !ii in
       (* Printf.printf "tmin (%s) = %i \n" (string_of_node h) mintime; *)
@@ -123,7 +133,7 @@ let modulo_schedule heightr ddg min_ii max_interval =
       in
       (* Printf.printf "Chosen time for %s : %i \n" (string_of_node h) time; *)
       schedtime := NI.add h (Some time) !schedtime;
-      lasttime := NI.add h time !lasttime; 
+      lasttime := NI.add h time !lasttime;
 
       let killed = bad_successors ddg !schedtime h !ii in
       List.iter (fun n -> (* Printf.printf "Killing %s" (string_of_node n) ; *)schedtime := NI.add n None !schedtime) killed;
@@ -158,12 +168,14 @@ let modulo_schedule heightr ddg min_ii max_interval =
   then (!sched,!ii)
   else failwith "IMS failure"
 
-
+(* Take the number of vertices as the minimum resource-constrained II.  However, the II might
+   actually be less than that in some cases, so this should be adjusted accordingly. *)
 let res_m_ii ddg =
   G.nb_vertex ddg
 
 let pipeliner ddg heightr =
   let mii = res_m_ii ddg in
+  Printf.fprintf SPDebug.dc "MII: %i\n" mii;
   let (schedule,ii) = modulo_schedule heightr ddg mii (10 * mii) in
   (NI.fold (fun n v map -> 
        match v with
diff --git a/src/SoftwarePipelining/SoftwarePipelining.ml b/src/SoftwarePipelining/SoftwarePipelining.ml
index fd95134..0ba6d9d 100644
--- a/src/SoftwarePipelining/SoftwarePipelining.ml
+++ b/src/SoftwarePipelining/SoftwarePipelining.ml
@@ -38,6 +38,10 @@ let find node schedule opt =
   try NI.find node schedule with
   | Not_found -> opt
 
+(* A random heuristic is used to pick the next instruction to be scheduled from the unscheduled
+ * instructions.  The scheduled instructions are given to the function, and the unscheduled
+ * instructions are created by taking all the instructions that are not in the scheduled list.
+ *)
 let random ddg schedule = 
   let unscheduled = G.fold_vertex (fun node l ->
       match find node schedule None with
@@ -55,7 +59,7 @@ module Scc = Graph.Components.Make (G)
 
 let order = ref []
 
-let pipeliner ddg =  
+let pipeliner ddg =
   order := List.flatten (Scc.scc_list ddg);
   let (sched,ii) = SPIMS.pipeliner ddg random in
   let (steady,prolog,epilog,min,unroll,entrance,way_out) = SPMVE.mve ddg sched ii in
-- 
cgit