diff options
author | Cyril SIX <cyril.six@kalray.eu> | 2019-05-03 14:32:36 +0200 |
---|---|---|
committer | Cyril SIX <cyril.six@kalray.eu> | 2019-05-03 14:32:36 +0200 |
commit | 452da0d77523d15830d7a78198092d72822063a6 (patch) | |
tree | 273bf5fc7e715d80a75f5c83d06cfd32e9266d74 /mppa_k1c/InstructionScheduler.ml | |
parent | 24e97bd87918f2c487416744ba12a78aba35a9e5 (diff) | |
parent | 9976dba5412be7e834abb63ac2293f1da288a185 (diff) | |
download | compcert-kvx-452da0d77523d15830d7a78198092d72822063a6.tar.gz compcert-kvx-452da0d77523d15830d7a78198092d72822063a6.zip |
Merge branch 'mppa-work' into mppa_k1c
Diffstat (limited to 'mppa_k1c/InstructionScheduler.ml')
-rw-r--r-- | mppa_k1c/InstructionScheduler.ml | 61 |
1 files changed, 59 insertions, 2 deletions
diff --git a/mppa_k1c/InstructionScheduler.ml b/mppa_k1c/InstructionScheduler.ml index dca4b8ff..1fa55c9b 100644 --- a/mppa_k1c/InstructionScheduler.ml +++ b/mppa_k1c/InstructionScheduler.ml @@ -307,10 +307,67 @@ 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 nr_instructions = get_nr_instructions problem in + if (index >= nr_instructions) then (bundle, index+1) else + 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) (nr_instructions+4) 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 greedy_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 |