[BUGGED] First attempt at a dumb scheduler ("accumulates" instructions)

3 files changed, 61 insertions, 3 deletions

diff --git a/mppa_k1c/InstructionScheduler.ml b/mppa_k1c/InstructionScheduler.ml
index dca4b8ff..1eba01d7 100644
--- a/mppa_k1c/InstructionScheduler.ml
+++ b/mppa_k1c/InstructionScheduler.ml
@@ -307,10 +307,65 @@ let priority_list_scheduler (order : list_scheduler_order)
 
 let list_scheduler = priority_list_scheduler CRITICAL_PATH_ORDER;;
 
-(* FIXME DUMMY CODE to placate warnings
- *)
+(** FIXME - warning fix *)
 let _ = priority_list_scheduler INSTRUCTION_ORDER;;
 
+type bundle = int list;;
+
+let rec extract_deps_to index = function
+  | [] -> []
+  | dep :: deps -> let extracts = extract_deps_to index deps in
+      if (dep.instr_to == index) then 
+        dep :: extracts
+      else
+        extracts
+
+exception InvalidBundle;;
+
+let dependency_check problem bundle index =
+  let index_deps = extract_deps_to index problem.latency_constraints in
+  List.iter (fun i -> 
+    List.iter (fun dep ->
+      if (dep.instr_from == i) then raise InvalidBundle
+    ) index_deps
+  ) bundle;;
+
+let rec make_bundle problem resources bundle index =
+  let resources_copy = Array.copy resources in
+  let inst_usage = problem.instruction_usages.(index) in
+  try match vector_less_equal inst_usage resources with
+  | false -> raise InvalidBundle
+  | true -> (
+      dependency_check problem bundle index;
+      vector_subtract problem.instruction_usages.(index) resources_copy;
+      make_bundle problem resources_copy (index::bundle) (index+1)
+      )
+  with InvalidBundle -> (bundle, index);;
+
+let rec make_bundles problem index : bundle list =
+  if index >= get_nr_instructions problem then
+    []
+  else
+    let (bundle, new_index) = make_bundle problem problem.resource_bounds [] index in
+    bundle :: (make_bundles problem new_index);;
+
+let bundles_to_schedule problem bundles : solution =
+  let nr_instructions = get_nr_instructions problem in
+  let schedule = Array.make nr_instructions (-1) in
+  let time = ref 0 in
+  List.iter (fun bundle ->
+    begin
+    List.iter (fun i ->
+      schedule.(i) <- !time
+    ) bundle;
+    time := !time + 1
+    end
+  ) bundles; schedule;;
+
+let dumb_scheduler (problem : problem) : solution option =
+  let bundles = make_bundles problem 0 in
+  Some (bundles_to_schedule problem bundles);;
+
 (* alternate implementation
 let swap_array_elements a i j =
   let x = a.(i) in
diff --git a/mppa_k1c/InstructionScheduler.mli b/mppa_k1c/InstructionScheduler.mli
index 629664f9..701ccb25 100644
--- a/mppa_k1c/InstructionScheduler.mli
+++ b/mppa_k1c/InstructionScheduler.mli
@@ -62,6 +62,9 @@ Once a clock tick is full go to the next.
 @return [Some solution] when a solution is found, [None] if not. *)
 val list_scheduler : problem -> solution option
 
+(** Schedule the problem using the order of instructions without any reordering *)
+val dumb_scheduler : problem -> solution option
+
 (** Schedule a problem using a scheduler applied in the opposite direction, e.g. for list scheduling from the end instead of the start. BUGGY *)
 val schedule_reversed : scheduler -> problem -> int array option
 
diff --git a/mppa_k1c/PostpassSchedulingOracle.ml b/mppa_k1c/PostpassSchedulingOracle.ml
index 87f34ee6..decb5722 100644
--- a/mppa_k1c/PostpassSchedulingOracle.ml
+++ b/mppa_k1c/PostpassSchedulingOracle.ml
@@ -759,7 +759,7 @@ let do_schedule bb =
   in let solution = validated_scheduler
                       (if !Clflags.option_fpostpass_ilp
                        then cascaded_scheduler
-                       else list_scheduler) problem
+                       else dumb_scheduler) problem
   in match solution with
   | None -> failwith "Could not find a valid schedule"
   | Some sol -> let bundles = bundlize_solution bb sol in