cannam@167: (* cannam@167: * Copyright (c) 1997-1999 Massachusetts Institute of Technology cannam@167: * Copyright (c) 2003, 2007-14 Matteo Frigo cannam@167: * Copyright (c) 2003, 2007-14 Massachusetts Institute of Technology cannam@167: * cannam@167: * This program is free software; you can redistribute it and/or modify cannam@167: * it under the terms of the GNU General Public License as published by cannam@167: * the Free Software Foundation; either version 2 of the License, or cannam@167: * (at your option) any later version. cannam@167: * cannam@167: * This program is distributed in the hope that it will be useful, cannam@167: * but WITHOUT ANY WARRANTY; without even the implied warranty of cannam@167: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the cannam@167: * GNU General Public License for more details. cannam@167: * cannam@167: * You should have received a copy of the GNU General Public License cannam@167: * along with this program; if not, write to the Free Software cannam@167: * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA cannam@167: * cannam@167: *) cannam@167: cannam@167: (************************************************************* cannam@167: * Conversion of the dag to an assignment list cannam@167: *************************************************************) cannam@167: (* cannam@167: * This function is messy. The main problem is that we want to cannam@167: * inline dag nodes conditionally, depending on how many times they cannam@167: * are used. The Right Thing to do would be to modify the cannam@167: * state monad to propagate some of the state backwards, so that cannam@167: * we know whether a given node will be used again in the future. cannam@167: * This modification is trivial in a lazy language, but it is cannam@167: * messy in a strict language like ML. cannam@167: * cannam@167: * In this implementation, we just do the obvious thing, i.e., visit cannam@167: * the dag twice, the first to count the node usages, and the second to cannam@167: * produce the output. cannam@167: *) cannam@167: cannam@167: open Monads.StateMonad cannam@167: open Monads.MemoMonad cannam@167: open Expr cannam@167: cannam@167: let fresh = Variable.make_temporary cannam@167: let node_insert x = Assoctable.insert Expr.hash x cannam@167: let node_lookup x = Assoctable.lookup Expr.hash (==) x cannam@167: let empty = Assoctable.empty cannam@167: cannam@167: let fetchAl = cannam@167: fetchState >>= (fun (al, _, _) -> returnM al) cannam@167: cannam@167: let storeAl al = cannam@167: fetchState >>= (fun (_, visited, visited') -> cannam@167: storeState (al, visited, visited')) cannam@167: cannam@167: let fetchVisited = fetchState >>= (fun (_, v, _) -> returnM v) cannam@167: cannam@167: let storeVisited visited = cannam@167: fetchState >>= (fun (al, _, visited') -> cannam@167: storeState (al, visited, visited')) cannam@167: cannam@167: let fetchVisited' = fetchState >>= (fun (_, _, v') -> returnM v') cannam@167: let storeVisited' visited' = cannam@167: fetchState >>= (fun (al, visited, _) -> cannam@167: storeState (al, visited, visited')) cannam@167: let lookupVisitedM' key = cannam@167: fetchVisited' >>= fun table -> cannam@167: returnM (node_lookup key table) cannam@167: let insertVisitedM' key value = cannam@167: fetchVisited' >>= fun table -> cannam@167: storeVisited' (node_insert key value table) cannam@167: cannam@167: let counting f x = cannam@167: fetchVisited >>= (fun v -> cannam@167: match node_lookup x v with cannam@167: Some count -> cannam@167: let incr_cnt = cannam@167: fetchVisited >>= (fun v' -> cannam@167: storeVisited (node_insert x (count + 1) v')) cannam@167: in cannam@167: begin cannam@167: match x with cannam@167: (* Uminus is always inlined. Visit child *) cannam@167: Uminus y -> f y >> incr_cnt cannam@167: | _ -> incr_cnt cannam@167: end cannam@167: | None -> cannam@167: f x >> fetchVisited >>= (fun v' -> cannam@167: storeVisited (node_insert x 1 v'))) cannam@167: cannam@167: let with_varM v x = cannam@167: fetchAl >>= (fun al -> storeAl ((v, x) :: al)) >> returnM (Load v) cannam@167: cannam@167: let inlineM = returnM cannam@167: cannam@167: let with_tempM x = match x with cannam@167: | Load v when Variable.is_temporary v -> inlineM x (* avoid trivial moves *) cannam@167: | _ -> with_varM (fresh ()) x cannam@167: cannam@167: (* declare a temporary only if node is used more than once *) cannam@167: let with_temp_maybeM node x = cannam@167: fetchVisited >>= (fun v -> cannam@167: match node_lookup node v with cannam@167: Some count -> cannam@167: if (count = 1 && !Magic.inline_single) then cannam@167: inlineM x cannam@167: else cannam@167: with_tempM x cannam@167: | None -> cannam@167: failwith "with_temp_maybeM") cannam@167: type fma = cannam@167: NO_FMA cannam@167: | FMA of expr * expr * expr (* FMA (a, b, c) => a + b * c *) cannam@167: | FMS of expr * expr * expr (* FMS (a, b, c) => -a + b * c *) cannam@167: | FNMS of expr * expr * expr (* FNMS (a, b, c) => a - b * c *) cannam@167: cannam@167: let good_for_fma (a, b) = cannam@167: let good = function cannam@167: | NaN I -> true cannam@167: | NaN CONJ -> true cannam@167: | NaN _ -> false cannam@167: | Times(NaN _, _) -> false cannam@167: | Times(_, NaN _) -> false cannam@167: | _ -> true cannam@167: in good a && good b cannam@167: cannam@167: let build_fma l = cannam@167: if (not !Magic.enable_fma) then NO_FMA cannam@167: else match l with cannam@167: | [a; Uminus (Times (b, c))] when good_for_fma (b, c) -> FNMS (a, b, c) cannam@167: | [Uminus (Times (b, c)); a] when good_for_fma (b, c) -> FNMS (a, b, c) cannam@167: | [Uminus a; Times (b, c)] when good_for_fma (b, c) -> FMS (a, b, c) cannam@167: | [Times (b, c); Uminus a] when good_for_fma (b, c) -> FMS (a, b, c) cannam@167: | [a; Times (b, c)] when good_for_fma (b, c) -> FMA (a, b, c) cannam@167: | [Times (b, c); a] when good_for_fma (b, c) -> FMA (a, b, c) cannam@167: | _ -> NO_FMA cannam@167: cannam@167: let children_fma l = match build_fma l with cannam@167: | FMA (a, b, c) -> Some (a, b, c) cannam@167: | FMS (a, b, c) -> Some (a, b, c) cannam@167: | FNMS (a, b, c) -> Some (a, b, c) cannam@167: | NO_FMA -> None cannam@167: cannam@167: cannam@167: let rec visitM x = cannam@167: counting (function cannam@167: | Load v -> returnM () cannam@167: | Num a -> returnM () cannam@167: | NaN a -> returnM () cannam@167: | Store (v, x) -> visitM x cannam@167: | Plus a -> (match children_fma a with cannam@167: None -> mapM visitM a >> returnM () cannam@167: | Some (a, b, c) -> cannam@167: (* visit fma's arguments twice to make sure they are not inlined *) cannam@167: visitM a >> visitM a >> cannam@167: visitM b >> visitM b >> cannam@167: visitM c >> visitM c) cannam@167: | Times (a, b) -> visitM a >> visitM b cannam@167: | CTimes (a, b) -> visitM a >> visitM b cannam@167: | CTimesJ (a, b) -> visitM a >> visitM b cannam@167: | Uminus a -> visitM a) cannam@167: x cannam@167: cannam@167: let visit_rootsM = mapM visitM cannam@167: cannam@167: cannam@167: let rec expr_of_nodeM x = cannam@167: memoizing lookupVisitedM' insertVisitedM' cannam@167: (function x -> match x with cannam@167: | Load v -> cannam@167: if (Variable.is_temporary v) then cannam@167: inlineM (Load v) cannam@167: else if (Variable.is_locative v && !Magic.inline_loads) then cannam@167: inlineM (Load v) cannam@167: else if (Variable.is_constant v && !Magic.inline_loads_constants) then cannam@167: inlineM (Load v) cannam@167: else cannam@167: with_tempM (Load v) cannam@167: | Num a -> cannam@167: if !Magic.inline_constants then cannam@167: inlineM (Num a) cannam@167: else cannam@167: with_temp_maybeM x (Num a) cannam@167: | NaN a -> inlineM (NaN a) cannam@167: | Store (v, x) -> cannam@167: expr_of_nodeM x >>= cannam@167: (if !Magic.trivial_stores then with_tempM else inlineM) >>= cannam@167: with_varM v cannam@167: cannam@167: | Plus a -> cannam@167: begin cannam@167: match build_fma a with cannam@167: FMA (a, b, c) -> cannam@167: expr_of_nodeM a >>= fun a' -> cannam@167: expr_of_nodeM b >>= fun b' -> cannam@167: expr_of_nodeM c >>= fun c' -> cannam@167: with_temp_maybeM x (Plus [a'; Times (b', c')]) cannam@167: | FMS (a, b, c) -> cannam@167: expr_of_nodeM a >>= fun a' -> cannam@167: expr_of_nodeM b >>= fun b' -> cannam@167: expr_of_nodeM c >>= fun c' -> cannam@167: with_temp_maybeM x cannam@167: (Plus [Times (b', c'); Uminus a']) cannam@167: | FNMS (a, b, c) -> cannam@167: expr_of_nodeM a >>= fun a' -> cannam@167: expr_of_nodeM b >>= fun b' -> cannam@167: expr_of_nodeM c >>= fun c' -> cannam@167: with_temp_maybeM x cannam@167: (Plus [a'; Uminus (Times (b', c'))]) cannam@167: | NO_FMA -> cannam@167: mapM expr_of_nodeM a >>= fun a' -> cannam@167: with_temp_maybeM x (Plus a') cannam@167: end cannam@167: | CTimes (Load _ as a, b) when !Magic.generate_bytw -> cannam@167: expr_of_nodeM b >>= fun b' -> cannam@167: with_tempM (CTimes (a, b')) cannam@167: | CTimes (a, b) -> cannam@167: expr_of_nodeM a >>= fun a' -> cannam@167: expr_of_nodeM b >>= fun b' -> cannam@167: with_tempM (CTimes (a', b')) cannam@167: | CTimesJ (Load _ as a, b) when !Magic.generate_bytw -> cannam@167: expr_of_nodeM b >>= fun b' -> cannam@167: with_tempM (CTimesJ (a, b')) cannam@167: | CTimesJ (a, b) -> cannam@167: expr_of_nodeM a >>= fun a' -> cannam@167: expr_of_nodeM b >>= fun b' -> cannam@167: with_tempM (CTimesJ (a', b')) cannam@167: | Times (a, b) -> cannam@167: expr_of_nodeM a >>= fun a' -> cannam@167: expr_of_nodeM b >>= fun b' -> cannam@167: begin cannam@167: match a' with cannam@167: Num a'' when !Magic.strength_reduce_mul && Number.is_two a'' -> cannam@167: (inlineM b' >>= fun b'' -> cannam@167: with_temp_maybeM x (Plus [b''; b''])) cannam@167: | _ -> with_temp_maybeM x (Times (a', b')) cannam@167: end cannam@167: | Uminus a -> cannam@167: expr_of_nodeM a >>= fun a' -> cannam@167: inlineM (Uminus a')) cannam@167: x cannam@167: cannam@167: let expr_of_rootsM = mapM expr_of_nodeM cannam@167: cannam@167: let peek_alistM roots = cannam@167: visit_rootsM roots >> expr_of_rootsM roots >> fetchAl cannam@167: cannam@167: let wrap_assign (a, b) = Expr.Assign (a, b) cannam@167: cannam@167: let to_assignments dag = cannam@167: let () = Util.info "begin to_alist" in cannam@167: let al = List.rev (runM ([], empty, empty) peek_alistM dag) in cannam@167: let res = List.map wrap_assign al in cannam@167: let () = Util.info "end to_alist" in cannam@167: res cannam@167: cannam@167: cannam@167: (* dump alist in `dot' format *) cannam@167: let dump print alist = cannam@167: let vs v = "\"" ^ (Variable.unparse v) ^ "\"" in cannam@167: begin cannam@167: print "digraph G {\n"; cannam@167: print "\tsize=\"6,6\";\n"; cannam@167: cannam@167: (* all input nodes have the same rank *) cannam@167: print "{ rank = same;\n"; cannam@167: List.iter (fun (Expr.Assign (v, x)) -> cannam@167: List.iter (fun y -> cannam@167: if (Variable.is_locative y) then print("\t" ^ (vs y) ^ ";\n")) cannam@167: (Expr.find_vars x)) cannam@167: alist; cannam@167: print "}\n"; cannam@167: cannam@167: (* all output nodes have the same rank *) cannam@167: print "{ rank = same;\n"; cannam@167: List.iter (fun (Expr.Assign (v, x)) -> cannam@167: if (Variable.is_locative v) then print("\t" ^ (vs v) ^ ";\n")) cannam@167: alist; cannam@167: print "}\n"; cannam@167: cannam@167: (* edges *) cannam@167: List.iter (fun (Expr.Assign (v, x)) -> cannam@167: List.iter (fun y -> print("\t" ^ (vs y) ^ " -> " ^ (vs v) ^ ";\n")) cannam@167: (Expr.find_vars x)) cannam@167: alist; cannam@167: cannam@167: print "}\n"; cannam@167: end cannam@167: