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