Chris@10: (* Chris@10: * Copyright (c) 1997-1999 Massachusetts Institute of Technology Chris@10: * Copyright (c) 2003, 2007-11 Matteo Frigo Chris@10: * Copyright (c) 2003, 2007-11 Massachusetts Institute of Technology Chris@10: * Chris@10: * This program is free software; you can redistribute it and/or modify Chris@10: * it under the terms of the GNU General Public License as published by Chris@10: * the Free Software Foundation; either version 2 of the License, or Chris@10: * (at your option) any later version. Chris@10: * Chris@10: * This program is distributed in the hope that it will be useful, Chris@10: * but WITHOUT ANY WARRANTY; without even the implied warranty of Chris@10: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the Chris@10: * GNU General Public License for more details. Chris@10: * Chris@10: * You should have received a copy of the GNU General Public License Chris@10: * along with this program; if not, write to the Free Software Chris@10: * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA Chris@10: * Chris@10: *) Chris@10: Chris@10: (* This file contains the instruction scheduler, which finds an Chris@10: efficient ordering for a given list of instructions. Chris@10: Chris@10: The scheduler analyzes the DAG (directed acyclic graph) formed by Chris@10: the instruction dependencies, and recursively partitions it. The Chris@10: resulting schedule data structure expresses a "good" ordering Chris@10: and structure for the computation. Chris@10: Chris@10: The scheduler makes use of utilties in Dag and other packages to Chris@10: manipulate the Dag and the instruction list. *) Chris@10: Chris@10: open Dag Chris@10: (************************************************* Chris@10: * Dag scheduler Chris@10: *************************************************) Chris@10: let to_assignment node = (Expr.Assign (node.assigned, node.expression)) Chris@10: let makedag l = Dag.makedag Chris@10: (List.map (function Expr.Assign (v, x) -> (v, x)) l) Chris@10: Chris@10: let return x = x Chris@10: let has_color c n = (n.color = c) Chris@10: let set_color c n = (n.color <- c) Chris@10: let has_either_color c1 c2 n = (n.color = c1 || n.color = c2) Chris@10: Chris@10: let infinity = 100000 Chris@10: Chris@10: let cc dag inputs = Chris@10: begin Chris@10: Dag.for_all dag (fun node -> Chris@10: node.label <- infinity); Chris@10: Chris@10: (match inputs with Chris@10: a :: _ -> bfs dag a 0 Chris@10: | _ -> failwith "connected"); Chris@10: Chris@10: return Chris@10: ((List.map to_assignment (List.filter (fun n -> n.label < infinity) Chris@10: (Dag.to_list dag))), Chris@10: (List.map to_assignment (List.filter (fun n -> n.label == infinity) Chris@10: (Dag.to_list dag)))) Chris@10: end Chris@10: Chris@10: let rec connected_components alist = Chris@10: let dag = makedag alist in Chris@10: let inputs = Chris@10: List.filter (fun node -> Util.null node.predecessors) Chris@10: (Dag.to_list dag) in Chris@10: match cc dag inputs with Chris@10: (a, []) -> [a] Chris@10: | (a, b) -> a :: connected_components b Chris@10: Chris@10: let single_load node = Chris@10: match (node.input_variables, node.predecessors) with Chris@10: ([x], []) -> Chris@10: Variable.is_constant x || Chris@10: (!Magic.locations_are_special && Variable.is_locative x) Chris@10: | _ -> false Chris@10: Chris@10: let loads_locative node = Chris@10: match (node.input_variables, node.predecessors) with Chris@10: | ([x], []) -> Variable.is_locative x Chris@10: | _ -> false Chris@10: Chris@10: let partition alist = Chris@10: let dag = makedag alist in Chris@10: let dag' = Dag.to_list dag in Chris@10: let inputs = Chris@10: List.filter (fun node -> Util.null node.predecessors) dag' Chris@10: and outputs = Chris@10: List.filter (fun node -> Util.null node.successors) dag' Chris@10: and special_inputs = List.filter single_load dag' in Chris@10: begin Chris@10: Chris@10: let c = match !Magic.schedule_type with Chris@10: | 1 -> RED; (* all nodes in the input partition *) Chris@10: | -1 -> BLUE; (* all nodes in the output partition *) Chris@10: | _ -> BLACK; (* node color determined by bisection algorithm *) Chris@10: in Dag.for_all dag (fun node -> node.color <- c); Chris@10: Chris@10: Util.for_list inputs (set_color RED); Chris@10: Chris@10: (* Chris@10: The special inputs are those input nodes that load a single Chris@10: location or twiddle factor. Special inputs can end up either Chris@10: in the blue or in the red part. These inputs are special Chris@10: because they inherit a color from their neighbors: If a red Chris@10: node needs a special input, the special input becomes red, but Chris@10: if all successors of a special input are blue, the special Chris@10: input becomes blue. Outputs are always blue, whether they be Chris@10: special or not. Chris@10: Chris@10: Because of the processing of special inputs, however, the final Chris@10: partition might end up being composed only of blue nodes (which Chris@10: is incorrect). In this case we manually reset all inputs Chris@10: (whether special or not) to be red. Chris@10: *) Chris@10: Chris@10: Util.for_list special_inputs (set_color YELLOW); Chris@10: Chris@10: Util.for_list outputs (set_color BLUE); Chris@10: Chris@10: let rec loopi donep = Chris@10: match (List.filter Chris@10: (fun node -> (has_color BLACK node) && Chris@10: List.for_all (has_either_color RED YELLOW) node.predecessors) Chris@10: dag') with Chris@10: [] -> if (donep) then () else loopo true Chris@10: | i -> Chris@10: begin Chris@10: Util.for_list i (fun node -> Chris@10: begin Chris@10: set_color RED node; Chris@10: Util.for_list node.predecessors (set_color RED); Chris@10: end); Chris@10: loopo false; Chris@10: end Chris@10: Chris@10: and loopo donep = Chris@10: match (List.filter Chris@10: (fun node -> (has_either_color BLACK YELLOW node) && Chris@10: List.for_all (has_color BLUE) node.successors) Chris@10: dag') with Chris@10: [] -> if (donep) then () else loopi true Chris@10: | o -> Chris@10: begin Chris@10: Util.for_list o (set_color BLUE); Chris@10: loopi false; Chris@10: end Chris@10: Chris@10: in loopi false; Chris@10: Chris@10: (* fix the partition if it is incorrect *) Chris@10: if not (List.exists (has_color RED) dag') then Chris@10: Util.for_list inputs (set_color RED); Chris@10: Chris@10: return Chris@10: ((List.map to_assignment (List.filter (has_color RED) dag')), Chris@10: (List.map to_assignment (List.filter (has_color BLUE) dag'))) Chris@10: end Chris@10: Chris@10: type schedule = Chris@10: Done Chris@10: | Instr of Expr.assignment Chris@10: | Seq of (schedule * schedule) Chris@10: | Par of schedule list Chris@10: Chris@10: Chris@10: Chris@10: (* produce a sequential schedule determined by the user *) Chris@10: let rec sequentially = function Chris@10: [] -> Done Chris@10: | a :: b -> Seq (Instr a, sequentially b) Chris@10: Chris@10: let schedule = Chris@10: let rec schedule_alist = function Chris@10: | [] -> Done Chris@10: | [a] -> Instr a Chris@10: | alist -> match connected_components alist with Chris@10: | ([a]) -> schedule_connected a Chris@10: | l -> Par (List.map schedule_alist l) Chris@10: Chris@10: and schedule_connected alist = Chris@10: match partition alist with Chris@10: | (a, b) -> Seq (schedule_alist a, schedule_alist b) Chris@10: Chris@10: in fun x -> Chris@10: let () = Util.info "begin schedule" in Chris@10: let res = schedule_alist x in Chris@10: let () = Util.info "end schedule" in Chris@10: res Chris@10: Chris@10: Chris@10: (* partition a dag into two parts: Chris@10: Chris@10: 1) the set of loads from locatives and their successors, Chris@10: 2) all other nodes Chris@10: Chris@10: This step separates the ``body'' of the dag, which computes the Chris@10: actual fft, from the ``precomputations'' part, which computes e.g. Chris@10: twiddle factors. Chris@10: *) Chris@10: let partition_precomputations alist = Chris@10: let dag = makedag alist in Chris@10: let dag' = Dag.to_list dag in Chris@10: let loads = List.filter loads_locative dag' in Chris@10: begin Chris@10: Chris@10: Dag.for_all dag (set_color BLUE); Chris@10: Util.for_list loads (set_color RED); Chris@10: Chris@10: let rec loop () = Chris@10: match (List.filter Chris@10: (fun node -> (has_color RED node) && Chris@10: List.exists (has_color BLUE) node.successors) Chris@10: dag') with Chris@10: [] -> () Chris@10: | i -> Chris@10: begin Chris@10: Util.for_list i Chris@10: (fun node -> Chris@10: Util.for_list node.successors (set_color RED)); Chris@10: loop () Chris@10: end Chris@10: Chris@10: in loop (); Chris@10: Chris@10: return Chris@10: ((List.map to_assignment (List.filter (has_color BLUE) dag')), Chris@10: (List.map to_assignment (List.filter (has_color RED) dag'))) Chris@10: end Chris@10: Chris@10: let isolate_precomputations_and_schedule alist = Chris@10: let (a, b) = partition_precomputations alist in Chris@10: Seq (schedule a, schedule b) Chris@10: