cannam@95: (* cannam@95: * Copyright (c) 1997-1999 Massachusetts Institute of Technology cannam@95: * Copyright (c) 2003, 2007-11 Matteo Frigo cannam@95: * Copyright (c) 2003, 2007-11 Massachusetts Institute of Technology cannam@95: * cannam@95: * This program is free software; you can redistribute it and/or modify cannam@95: * it under the terms of the GNU General Public License as published by cannam@95: * the Free Software Foundation; either version 2 of the License, or cannam@95: * (at your option) any later version. cannam@95: * cannam@95: * This program is distributed in the hope that it will be useful, cannam@95: * but WITHOUT ANY WARRANTY; without even the implied warranty of cannam@95: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the cannam@95: * GNU General Public License for more details. cannam@95: * cannam@95: * You should have received a copy of the GNU General Public License cannam@95: * along with this program; if not, write to the Free Software cannam@95: * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA cannam@95: * cannam@95: *) cannam@95: cannam@95: (* cannam@95: * This module contains the definition of a C-like abstract cannam@95: * syntax tree, and functions to convert ML values into C cannam@95: * programs cannam@95: *) cannam@95: cannam@95: open Expr cannam@95: open Annotate cannam@95: open List cannam@95: cannam@95: let realtype = "R" cannam@95: let realtypep = realtype ^ " *" cannam@95: let extended_realtype = "E" cannam@95: let constrealtype = "const " ^ realtype cannam@95: let constrealtypep = constrealtype ^ " *" cannam@95: cannam@95: let stridetype = "stride" cannam@95: cannam@95: (*********************************** cannam@95: * C program structure cannam@95: ***********************************) cannam@95: type c_decl = cannam@95: | Decl of string * string cannam@95: | Tdecl of string (* arbitrary text declaration *) cannam@95: cannam@95: and c_ast = cannam@95: | Asch of annotated_schedule cannam@95: | Simd_leavefun cannam@95: | Return of c_ast cannam@95: | For of c_ast * c_ast * c_ast * c_ast cannam@95: | If of c_ast * c_ast cannam@95: | Block of (c_decl list) * (c_ast list) cannam@95: | Binop of string * c_ast * c_ast cannam@95: | Expr_assign of c_ast * c_ast cannam@95: | Stmt_assign of c_ast * c_ast cannam@95: | Comma of c_ast * c_ast cannam@95: | Integer of int cannam@95: | CVar of string cannam@95: | CCall of string * c_ast cannam@95: | CPlus of c_ast list cannam@95: | ITimes of c_ast * c_ast cannam@95: | CUminus of c_ast cannam@95: and c_fcn = Fcn of string * string * (c_decl list) * c_ast cannam@95: cannam@95: cannam@95: let ctimes = function cannam@95: | (Integer 1), a -> a cannam@95: | a, (Integer 1) -> a cannam@95: | a, b -> ITimes (a, b) cannam@95: cannam@95: (* cannam@95: * C AST unparser cannam@95: *) cannam@95: let foldr_string_concat l = fold_right (^) l "" cannam@95: cannam@95: let rec unparse_expr_c = cannam@95: let yes x = x and no x = "" in cannam@95: cannam@95: let rec unparse_plus maybe = cannam@95: let maybep = maybe " + " in cannam@95: function cannam@95: | [] -> "" cannam@95: | (Uminus (Times (a, b))) :: (Uminus c) :: d -> cannam@95: maybep ^ (op "FNMA" a b c) ^ (unparse_plus yes d) cannam@95: | (Uminus c) :: (Uminus (Times (a, b))) :: d -> cannam@95: maybep ^ (op "FNMA" a b c) ^ (unparse_plus yes d) cannam@95: | (Uminus (Times (a, b))) :: c :: d -> cannam@95: maybep ^ (op "FNMS" a b c) ^ (unparse_plus yes d) cannam@95: | c :: (Uminus (Times (a, b))) :: d -> cannam@95: maybep ^ (op "FNMS" a b c) ^ (unparse_plus yes d) cannam@95: | (Times (a, b)) :: (Uminus c) :: d -> cannam@95: maybep ^ (op "FMS" a b c) ^ (unparse_plus yes d) cannam@95: | (Uminus c) :: (Times (a, b)) :: d -> cannam@95: maybep ^ (op "FMS" a b c) ^ (unparse_plus yes d) cannam@95: | (Times (a, b)) :: c :: d -> cannam@95: maybep ^ (op "FMA" a b c) ^ (unparse_plus yes d) cannam@95: | c :: (Times (a, b)) :: d -> cannam@95: maybep ^ (op "FMA" a b c) ^ (unparse_plus yes d) cannam@95: | (Uminus a :: b) -> cannam@95: " - " ^ (parenthesize a) ^ (unparse_plus yes b) cannam@95: | (a :: b) -> cannam@95: maybep ^ (parenthesize a) ^ (unparse_plus yes b) cannam@95: and parenthesize x = match x with cannam@95: | (Load _) -> unparse_expr_c x cannam@95: | (Num _) -> unparse_expr_c x cannam@95: | _ -> "(" ^ (unparse_expr_c x) ^ ")" cannam@95: and op nam a b c = cannam@95: nam ^ "(" ^ (unparse_expr_c a) ^ ", " ^ (unparse_expr_c b) ^ ", " ^ cannam@95: (unparse_expr_c c) ^ ")" cannam@95: cannam@95: in function cannam@95: | Load v -> Variable.unparse v cannam@95: | Num n -> Number.to_konst n cannam@95: | Plus [] -> "0.0 /* bug */" cannam@95: | Plus [a] -> " /* bug */ " ^ (unparse_expr_c a) cannam@95: | Plus a -> (unparse_plus no a) cannam@95: | Times (a, b) -> (parenthesize a) ^ " * " ^ (parenthesize b) cannam@95: | Uminus (Plus [a; Uminus b]) -> unparse_plus no [b; Uminus a] cannam@95: | Uminus a -> "- " ^ (parenthesize a) cannam@95: | _ -> failwith "unparse_expr_c" cannam@95: cannam@95: and unparse_expr_generic = cannam@95: let rec u x = unparse_expr_generic x cannam@95: and unary op a = Printf.sprintf "%s(%s)" op (u a) cannam@95: and binary op a b = Printf.sprintf "%s(%s, %s)" op (u a) (u b) cannam@95: and ternary op a b c = Printf.sprintf "%s(%s, %s, %s)" op (u a) (u b) (u c) cannam@95: and quaternary op a b c d = cannam@95: Printf.sprintf "%s(%s, %s, %s, %s)" op (u a) (u b) (u c) (u d) cannam@95: and unparse_plus = function cannam@95: | [(Uminus (Times (a, b))); Times (c, d)] -> quaternary "FNMMS" a b c d cannam@95: | [Times (c, d); (Uminus (Times (a, b)))] -> quaternary "FNMMS" a b c d cannam@95: | [Times (c, d); (Times (a, b))] -> quaternary "FMMA" a b c d cannam@95: | [(Uminus (Times (a, b))); c] -> ternary "FNMS" a b c cannam@95: | [c; (Uminus (Times (a, b)))] -> ternary "FNMS" a b c cannam@95: | [(Uminus c); (Times (a, b))] -> ternary "FMS" a b c cannam@95: | [(Times (a, b)); (Uminus c)] -> ternary "FMS" a b c cannam@95: | [c; (Times (a, b))] -> ternary "FMA" a b c cannam@95: | [(Times (a, b)); c] -> ternary "FMA" a b c cannam@95: | [a; Uminus b] -> binary "SUB" a b cannam@95: | [a; b] -> binary "ADD" a b cannam@95: | a :: b :: c -> binary "ADD" a (Plus (b :: c)) cannam@95: | _ -> failwith "unparse_plus" cannam@95: in function cannam@95: | Load v -> Variable.unparse v cannam@95: | Num n -> Number.to_konst n cannam@95: | Plus a -> unparse_plus a cannam@95: | Times (a, b) -> binary "MUL" a b cannam@95: | Uminus a -> unary "NEG" a cannam@95: | _ -> failwith "unparse_expr" cannam@95: cannam@95: and unparse_expr x = cannam@95: if !Magic.generic_arith then cannam@95: unparse_expr_generic x cannam@95: else cannam@95: unparse_expr_c x cannam@95: cannam@95: and unparse_assignment (Assign (v, x)) = cannam@95: (Variable.unparse v) ^ " = " ^ (unparse_expr x) ^ ";\n" cannam@95: cannam@95: and unparse_annotated force_bracket = cannam@95: let rec unparse_code = function cannam@95: ADone -> "" cannam@95: | AInstr i -> unparse_assignment i cannam@95: | ASeq (a, b) -> cannam@95: (unparse_annotated false a) ^ (unparse_annotated false b) cannam@95: and declare_variables l = cannam@95: let rec uvar = function cannam@95: [] -> failwith "uvar" cannam@95: | [v] -> (Variable.unparse v) ^ ";\n" cannam@95: | a :: b -> (Variable.unparse a) ^ ", " ^ (uvar b) cannam@95: in let rec vvar l = cannam@95: let s = if !Magic.compact then 15 else 1 in cannam@95: if (List.length l <= s) then cannam@95: match l with cannam@95: [] -> "" cannam@95: | _ -> extended_realtype ^ " " ^ (uvar l) cannam@95: else cannam@95: (vvar (Util.take s l)) ^ (vvar (Util.drop s l)) cannam@95: in vvar (List.filter Variable.is_temporary l) cannam@95: in function cannam@95: Annotate (_, _, decl, _, code) -> cannam@95: if (not force_bracket) && (Util.null decl) then cannam@95: unparse_code code cannam@95: else "{\n" ^ cannam@95: (declare_variables decl) ^ cannam@95: (unparse_code code) ^ cannam@95: "}\n" cannam@95: cannam@95: and unparse_decl = function cannam@95: | Decl (a, b) -> a ^ " " ^ b ^ ";\n" cannam@95: | Tdecl x -> x cannam@95: cannam@95: and unparse_ast = cannam@95: let rec unparse_plus = function cannam@95: | [] -> "" cannam@95: | (CUminus a :: b) -> " - " ^ (parenthesize a) ^ (unparse_plus b) cannam@95: | (a :: b) -> " + " ^ (parenthesize a) ^ (unparse_plus b) cannam@95: and parenthesize x = match x with cannam@95: | (CVar _) -> unparse_ast x cannam@95: | (CCall _) -> unparse_ast x cannam@95: | (Integer _) -> unparse_ast x cannam@95: | _ -> "(" ^ (unparse_ast x) ^ ")" cannam@95: cannam@95: in cannam@95: function cannam@95: | Asch a -> (unparse_annotated true a) cannam@95: | Simd_leavefun -> "" (* used only in SIMD code *) cannam@95: | Return x -> "return " ^ unparse_ast x ^ ";" cannam@95: | For (a, b, c, d) -> cannam@95: "for (" ^ cannam@95: unparse_ast a ^ "; " ^ unparse_ast b ^ "; " ^ unparse_ast c cannam@95: ^ ")" ^ unparse_ast d cannam@95: | If (a, d) -> cannam@95: "if (" ^ cannam@95: unparse_ast a cannam@95: ^ ")" ^ unparse_ast d cannam@95: | Block (d, s) -> cannam@95: if (s == []) then "" cannam@95: else cannam@95: "{\n" ^ cannam@95: foldr_string_concat (map unparse_decl d) ^ cannam@95: foldr_string_concat (map unparse_ast s) ^ cannam@95: "}\n" cannam@95: | Binop (op, a, b) -> (unparse_ast a) ^ op ^ (unparse_ast b) cannam@95: | Expr_assign (a, b) -> (unparse_ast a) ^ " = " ^ (unparse_ast b) cannam@95: | Stmt_assign (a, b) -> (unparse_ast a) ^ " = " ^ (unparse_ast b) ^ ";\n" cannam@95: | Comma (a, b) -> (unparse_ast a) ^ ", " ^ (unparse_ast b) cannam@95: | Integer i -> string_of_int i cannam@95: | CVar s -> s cannam@95: | CCall (s, x) -> s ^ "(" ^ (unparse_ast x) ^ ")" cannam@95: | CPlus [] -> "0 /* bug */" cannam@95: | CPlus [a] -> " /* bug */ " ^ (unparse_ast a) cannam@95: | CPlus (a::b) -> (parenthesize a) ^ (unparse_plus b) cannam@95: | ITimes (a, b) -> (parenthesize a) ^ " * " ^ (parenthesize b) cannam@95: | CUminus a -> "- " ^ (parenthesize a) cannam@95: cannam@95: and unparse_function = function cannam@95: Fcn (typ, name, args, body) -> cannam@95: let rec unparse_args = function cannam@95: [Decl (a, b)] -> a ^ " " ^ b cannam@95: | (Decl (a, b)) :: s -> a ^ " " ^ b ^ ", " cannam@95: ^ unparse_args s cannam@95: | [] -> "" cannam@95: | _ -> failwith "unparse_function" cannam@95: in cannam@95: (typ ^ " " ^ name ^ "(" ^ unparse_args args ^ ")\n" ^ cannam@95: unparse_ast body) cannam@95: cannam@95: cannam@95: (************************************************************* cannam@95: * traverse a a function and return a list of all expressions, cannam@95: * in the execution order cannam@95: **************************************************************) cannam@95: let rec fcn_to_expr_list = fun (Fcn (_, _, _, body)) -> ast_to_expr_list body cannam@95: and acode_to_expr_list = function cannam@95: AInstr (Assign (_, x)) -> [x] cannam@95: | ASeq (a, b) -> cannam@95: (asched_to_expr_list a) @ (asched_to_expr_list b) cannam@95: | _ -> [] cannam@95: and asched_to_expr_list (Annotate (_, _, _, _, code)) = cannam@95: acode_to_expr_list code cannam@95: and ast_to_expr_list = function cannam@95: Asch a -> asched_to_expr_list a cannam@95: | Block (_, a) -> flatten (map ast_to_expr_list a) cannam@95: | For (_, _, _, body) -> ast_to_expr_list body cannam@95: | If (_, body) -> ast_to_expr_list body cannam@95: | _ -> [] cannam@95: cannam@95: (*********************** cannam@95: * Extracting Constants cannam@95: ***********************) cannam@95: cannam@95: (* add a new key & value to a list of (key,value) pairs, where cannam@95: the keys are floats and each key is unique up to almost_equal *) cannam@95: cannam@95: let extract_constants f = cannam@95: let constlist = flatten (map expr_to_constants (ast_to_expr_list f)) cannam@95: in map cannam@95: (fun n -> cannam@95: Tdecl cannam@95: ("DK(" ^ (Number.to_konst n) ^ ", " ^ (Number.to_string n) ^ cannam@95: ");\n")) cannam@95: (unique_constants constlist) cannam@95: cannam@95: (****************************** cannam@95: Extracting operation counts cannam@95: ******************************) cannam@95: cannam@95: let count_stack_vars = cannam@95: let rec count_acode = function cannam@95: | ASeq (a, b) -> max (count_asched a) (count_asched b) cannam@95: | _ -> 0 cannam@95: and count_asched (Annotate (_, _, decl, _, code)) = cannam@95: (length decl) + (count_acode code) cannam@95: and count_ast = function cannam@95: | Asch a -> count_asched a cannam@95: | Block (d, a) -> (length d) + (Util.max_list (map count_ast a)) cannam@95: | For (_, _, _, body) -> count_ast body cannam@95: | If (_, body) -> count_ast body cannam@95: | _ -> 0 cannam@95: in function (Fcn (_, _, _, body)) -> count_ast body cannam@95: cannam@95: let count_memory_acc f = cannam@95: let rec count_var v = cannam@95: if (Variable.is_locative v) then 1 else 0 cannam@95: and count_acode = function cannam@95: | AInstr (Assign (v, _)) -> count_var v cannam@95: | ASeq (a, b) -> (count_asched a) + (count_asched b) cannam@95: | _ -> 0 cannam@95: and count_asched = function cannam@95: Annotate (_, _, _, _, code) -> count_acode code cannam@95: and count_ast = function cannam@95: | Asch a -> count_asched a cannam@95: | Block (_, a) -> (Util.sum_list (map count_ast a)) cannam@95: | Comma (a, b) -> (count_ast a) + (count_ast b) cannam@95: | For (_, _, _, body) -> count_ast body cannam@95: | If (_, body) -> count_ast body cannam@95: | _ -> 0 cannam@95: and count_acc_expr_func acc = function cannam@95: | Load v -> acc + (count_var v) cannam@95: | Plus a -> fold_left count_acc_expr_func acc a cannam@95: | Times (a, b) -> fold_left count_acc_expr_func acc [a; b] cannam@95: | Uminus a -> count_acc_expr_func acc a cannam@95: | _ -> acc cannam@95: in let (Fcn (typ, name, args, body)) = f cannam@95: in (count_ast body) + cannam@95: fold_left count_acc_expr_func 0 (fcn_to_expr_list f) cannam@95: cannam@95: let good_for_fma = To_alist.good_for_fma cannam@95: cannam@95: let build_fma = function cannam@95: | [a; Times (b, c)] when good_for_fma (b, c) -> Some (a, b, c) cannam@95: | [Times (b, c); a] when good_for_fma (b, c) -> Some (a, b, c) cannam@95: | [a; Uminus (Times (b, c))] when good_for_fma (b, c) -> Some (a, b, c) cannam@95: | [Uminus (Times (b, c)); a] when good_for_fma (b, c) -> Some (a, b, c) cannam@95: | _ -> None cannam@95: cannam@95: let rec count_flops_expr_func (adds, mults, fmas) = function cannam@95: | Plus [] -> (adds, mults, fmas) cannam@95: | Plus ([_; _] as a) -> cannam@95: begin cannam@95: match build_fma a with cannam@95: | None -> cannam@95: fold_left count_flops_expr_func cannam@95: (adds + (length a) - 1, mults, fmas) a cannam@95: | Some (a, b, c) -> cannam@95: fold_left count_flops_expr_func (adds, mults, fmas+1) [a; b; c] cannam@95: end cannam@95: | Plus (a :: b) -> cannam@95: count_flops_expr_func (adds, mults, fmas) (Plus [a; Plus b]) cannam@95: | Times (NaN MULTI_A,_) -> (adds, mults, fmas) cannam@95: | Times (NaN MULTI_B,_) -> (adds, mults, fmas) cannam@95: | Times (NaN I,b) -> count_flops_expr_func (adds, mults, fmas) b cannam@95: | Times (NaN CONJ,b) -> count_flops_expr_func (adds, mults, fmas) b cannam@95: | Times (a,b) -> fold_left count_flops_expr_func (adds, mults+1, fmas) [a; b] cannam@95: | CTimes (a,b) -> cannam@95: fold_left count_flops_expr_func (adds+1, mults+2, fmas) [a; b] cannam@95: | CTimesJ (a,b) -> cannam@95: fold_left count_flops_expr_func (adds+1, mults+2, fmas) [a; b] cannam@95: | Uminus a -> count_flops_expr_func (adds, mults, fmas) a cannam@95: | _ -> (adds, mults, fmas) cannam@95: cannam@95: let count_flops f = cannam@95: fold_left count_flops_expr_func (0, 0, 0) (fcn_to_expr_list f) cannam@95: cannam@95: let count_constants f = cannam@95: length (unique_constants (flatten (map expr_to_constants (fcn_to_expr_list f)))) cannam@95: cannam@95: let arith_complexity f = cannam@95: let (a, m, fmas) = count_flops f cannam@95: and v = count_stack_vars f cannam@95: and c = count_constants f cannam@95: and mem = count_memory_acc f cannam@95: in (a, m, fmas, v, c, mem) cannam@95: cannam@95: (* print the operation costs *) cannam@95: let print_cost f = cannam@95: let Fcn (_, _, _, _) = f cannam@95: and (a, m, fmas, v, c, mem) = arith_complexity f cannam@95: in cannam@95: "/*\n"^ cannam@95: " * This function contains " ^ cannam@95: (string_of_int (a + fmas)) ^ " FP additions, " ^ cannam@95: (string_of_int (m + fmas)) ^ " FP multiplications,\n" ^ cannam@95: " * (or, " ^ cannam@95: (string_of_int a) ^ " additions, " ^ cannam@95: (string_of_int m) ^ " multiplications, " ^ cannam@95: (string_of_int fmas) ^ " fused multiply/add),\n" ^ cannam@95: " * " ^ (string_of_int v) ^ " stack variables, " ^ cannam@95: (string_of_int c) ^ " constants, and " ^ cannam@95: (string_of_int mem) ^ " memory accesses\n" ^ cannam@95: " */\n" cannam@95: cannam@95: (***************************************** cannam@95: * functions that create C arrays cannam@95: *****************************************) cannam@95: type stride = cannam@95: | SVar of string cannam@95: | SConst of string cannam@95: | SInteger of int cannam@95: | SNeg of stride cannam@95: cannam@95: type sstride = cannam@95: | Simple of int cannam@95: | Constant of (string * int) cannam@95: | Composite of (string * int) cannam@95: | Negative of sstride cannam@95: cannam@95: let rec simplify_stride stride i = cannam@95: match (stride, i) with cannam@95: (_, 0) -> Simple 0 cannam@95: | (SInteger n, i) -> Simple (n * i) cannam@95: | (SConst s, i) -> Constant (s, i) cannam@95: | (SVar s, i) -> Composite (s, i) cannam@95: | (SNeg x, i) -> cannam@95: match (simplify_stride x i) with cannam@95: | Negative y -> y cannam@95: | y -> Negative y cannam@95: cannam@95: let rec cstride_to_string = function cannam@95: | Simple i -> string_of_int i cannam@95: | Constant (s, i) -> cannam@95: if !Magic.lisp_syntax then cannam@95: "(* " ^ s ^ " " ^ (string_of_int i) ^ ")" cannam@95: else cannam@95: s ^ " * " ^ (string_of_int i) cannam@95: | Composite (s, i) -> cannam@95: if !Magic.lisp_syntax then cannam@95: "(* " ^ s ^ " " ^ (string_of_int i) ^ ")" cannam@95: else cannam@95: "WS(" ^ s ^ ", " ^ (string_of_int i) ^ ")" cannam@95: | Negative x -> "-" ^ cstride_to_string x cannam@95: cannam@95: let aref name index = cannam@95: if !Magic.lisp_syntax then cannam@95: Printf.sprintf "(aref %s %s)" name index cannam@95: else cannam@95: Printf.sprintf "%s[%s]" name index cannam@95: cannam@95: let array_subscript name stride k = cannam@95: aref name (cstride_to_string (simplify_stride stride k)) cannam@95: cannam@95: let varray_subscript name vstride stride v i = cannam@95: let vindex = simplify_stride vstride v cannam@95: and iindex = simplify_stride stride i cannam@95: in cannam@95: let index = cannam@95: match (vindex, iindex) with cannam@95: (Simple vi, Simple ii) -> string_of_int (vi + ii) cannam@95: | (Simple 0, x) -> cstride_to_string x cannam@95: | (x, Simple 0) -> cstride_to_string x cannam@95: | _ -> (cstride_to_string vindex) ^ " + " ^ (cstride_to_string iindex) cannam@95: in aref name index cannam@95: cannam@95: let real_of s = "c_re(" ^ s ^ ")" cannam@95: let imag_of s = "c_im(" ^ s ^ ")" cannam@95: cannam@95: let flops_of f = cannam@95: let (add, mul, fma) = count_flops f in cannam@95: Printf.sprintf "{ %d, %d, %d, 0 }" add mul fma