diff options
| -rw-r--r-- | driver/Driver.ml | 2 | ||||
| -rw-r--r-- | scheduling/InstructionScheduler.ml | 84 |
2 files changed, 68 insertions, 18 deletions
diff --git a/driver/Driver.ml b/driver/Driver.ml index 7192ba4b..5a8c7f2c 100644 --- a/driver/Driver.ml +++ b/driver/Driver.ml @@ -210,7 +210,7 @@ Processing options: -mtune= Type of CPU (for scheduling on some architectures) -fprepass Perform prepass scheduling (only on some architectures) [on] -fprepass= <optim> Perform postpass scheduling with the specified optimization [list] - (<optim>=list: list scheduling, <optim>=revlist: reverse list scheduling, <optim>=zigzag: zigzag scheduling, <optim>=ilp: ILP, <optim>=greedy: just packing bundles) + (<optim>=list: list scheduling, <optim>=revlist: reverse list scheduling, <optim>=regpres: list scheduling aware of register pressure, <optim>=zigzag: zigzag scheduling, <optim>=ilp: ILP, <optim>=greedy: just packing bundles) -fpostpass Perform postpass scheduling (only for K1 architecture) [on] -fpostpass= <optim> Perform postpass scheduling with the specified optimization [list] (<optim>=list: list scheduling, <optim>=ilp: ILP, <optim>=greedy: just packing bundles) diff --git a/scheduling/InstructionScheduler.ml b/scheduling/InstructionScheduler.ml index 8d8c4267..a069de59 100644 --- a/scheduling/InstructionScheduler.ml +++ b/scheduling/InstructionScheduler.ml @@ -121,6 +121,13 @@ let vector_less_equal a b = true with Exit -> false;; +(* let vector_add a b = + * assert ((Array.length a) = (Array.length b)); + * for i=0 to (Array.length a)-1 + * do + * b.(i) <- b.(i) + a.(i) + * done;; *) + let vector_subtract a b = assert ((Array.length a) = (Array.length b)); for i=0 to (Array.length a)-1 @@ -341,6 +348,7 @@ let _ = fun x -> priority_list_scheduler INSTRUCTION_ORDER x;; (* A scheduler sensitive to register pressure *) let reg_pres_scheduler (problem : problem) : solution option = + DebugPrint.debug_flag := true; let nr_instructions = get_nr_instructions problem in let successors = get_successors problem and predecessors = get_predecessors problem @@ -381,11 +389,9 @@ let reg_pres_scheduler (problem : problem) : solution option = let empty = MSet.empty let is_empty = MSet.is_empty - let mem = MSet.mem let add = MSet.add let remove = MSet.remove let union = MSet.union - let inter = MSet.inter let iter = MSet.iter let compare_regs i x y = @@ -400,15 +406,12 @@ let reg_pres_scheduler (problem : problem) : solution option = let result = ref (-1) in iter (fun i -> if vector_less_equal usages.(i) current_resources - then if !result = -1 || (compare_regs t !result i < 0) + then if !result = -1 || (compare_regs t !result i < 0) then result := i) ready; !result end in - (* [compare i] is comp function for finding instruction with - lowest reg pres delta for reg class i *) - let max_time = bound_max_time problem in let ready = Array.make max_time InstrSet.empty in @@ -450,25 +453,71 @@ let reg_pres_scheduler (problem : problem) : solution option = if avlregs <= regs_thresholds.(i) then ( let maybe = InstrSet.sched_CSR i ready usages in - (if pressures.(maybe).(i) < 0 then + (* print_int maybe; + * print_newline (); + * flush stdout; *) + if maybe > 0 && pressures.(maybe).(i) < 0 then (vector_subtract usages.(maybe) current_resources; - result := maybe)); - raise Exit) - ) available_regs; + result := maybe; + raise Exit))) available_regs; InstrSet.iter (fun i -> if vector_less_equal usages.(i) current_resources then ( vector_subtract usages.(i) current_resources; result := i; - raise Exit)); + raise Exit)) ready; -1 - with Exit -> !result in + with Exit -> + if !result <> -1 then + vector_subtract pressures.(!result) available_regs; + !result in - (* silence warning, enable compilation while working *) - let _ = successors, predecessors, times, ready, compare, - earliest_time, advance_time, nr_types_regs in - (* PLACEHOLDER *) - None + while !current_time < max_time + do + if (InstrSet.is_empty ready.(!current_time)) + then advance_time () + else + match attempt_scheduling ready.(!current_time) + problem.instruction_usages with + | -1 -> advance_time() + | i -> (assert(times.(i) < 0); + times.(i) <- !current_time; + ready.(!current_time) + <- InstrSet.remove i (ready.(!current_time)); + List.iter (fun (instr_to, latency) -> + if instr_to < nr_instructions then + match earliest_time instr_to with + | -1 -> () + | to_time -> + ready.(to_time) + <- InstrSet.add instr_to ready.(to_time) + ) successors.(i); + successors.(i) <- [] + ) + done; + + try + let final_time = ref (-1) in + for i = 0 to nr_instructions - 1 do + (* print_int i; + * flush stdout; *) + (if times.(i) < 0 then raise Exit); + (if !final_time < times.(i) + 1 then final_time := times.(i) + 1) + done; + List.iter (fun (i, latency) -> + let target_time = latency + times.(i) in + if target_time > !final_time then + final_time := target_time) predecessors.(nr_instructions); + times.(nr_instructions) <- !final_time; + DebugPrint.debug_flag := false; + Some times + with Exit -> + DebugPrint.debug "reg_pres_sched failed\n"; + DebugPrint.debug_flag := false; + None + +;; + type bundle = int list;; @@ -1402,5 +1451,6 @@ let scheduler_by_name name = | "ilp" -> validated_scheduler cascaded_scheduler | "list" -> validated_scheduler list_scheduler | "revlist" -> validated_scheduler reverse_list_scheduler + | "regpres" -> validated_scheduler reg_pres_scheduler | "greedy" -> greedy_scheduler | s -> failwith ("unknown scheduler: " ^ s);; |