X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Ftree-vect-patterns.c;h=c1ce14c4bbb91b1aacf84d1b1a6fde43ff0fe11a;hb=ffc0b1edcad561e7c8304c3f6cb38ec31502b024;hp=b6e5ef0ccd5554ccd6bc7a5b6d28a125dcb33a7f;hpb=9ca2c29a3651d0d31a0f4821744d20a91f787acd;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/tree-vect-patterns.c b/gcc/tree-vect-patterns.c index b6e5ef0ccd5..c1ce14c4bbb 100644 --- a/gcc/tree-vect-patterns.c +++ b/gcc/tree-vect-patterns.c @@ -1,12 +1,12 @@ /* Analysis Utilities for Loop Vectorization. - Copyright (C) 2006 Free Software Foundation, Inc. + Copyright (C) 2006, 2007 Free Software Foundation, Inc. Contributed by Dorit Nuzman This file is part of GCC. GCC is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free -Software Foundation; either version 2, or (at your option) any later +Software Foundation; either version 3, or (at your option) any later version. GCC is distributed in the hope that it will be useful, but WITHOUT ANY @@ -15,9 +15,8 @@ FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License -along with GCC; see the file COPYING. If not, write to the Free -Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA -02110-1301, USA. */ +along with GCC; see the file COPYING3. If not see +. */ #include "config.h" #include "system.h" @@ -50,10 +49,12 @@ static bool widened_name_p (tree, tree, tree *, tree *); static tree vect_recog_widen_sum_pattern (tree, tree *, tree *); static tree vect_recog_widen_mult_pattern (tree, tree *, tree *); static tree vect_recog_dot_prod_pattern (tree, tree *, tree *); +static tree vect_recog_pow_pattern (tree, tree *, tree *); static vect_recog_func_ptr vect_vect_recog_func_ptrs[NUM_PATTERNS] = { vect_recog_widen_mult_pattern, vect_recog_widen_sum_pattern, - vect_recog_dot_prod_pattern}; + vect_recog_dot_prod_pattern, + vect_recog_pow_pattern}; /* Function widened_name_p @@ -89,10 +90,10 @@ widened_name_p (tree name, tree use_stmt, tree *half_type, tree *def_stmt) if (! *def_stmt) return false; - if (TREE_CODE (*def_stmt) != MODIFY_EXPR) + if (TREE_CODE (*def_stmt) != GIMPLE_MODIFY_STMT) return false; - expr = TREE_OPERAND (*def_stmt, 1); + expr = GIMPLE_STMT_OPERAND (*def_stmt, 1); if (TREE_CODE (expr) != NOP_EXPR) return false; @@ -107,10 +108,6 @@ widened_name_p (tree name, tree use_stmt, tree *half_type, tree *def_stmt) if (!vect_is_simple_use (oprnd0, loop_vinfo, &dummy, &dummy, &dt)) return false; - if (dt != vect_invariant_def && dt != vect_constant_def - && dt != vect_loop_def) - return false; - return true; } @@ -151,7 +148,14 @@ widened_name_p (tree name, tree use_stmt, tree *half_type, tree *def_stmt) * Return value: A new stmt that will be used to replace the sequence of stmts that constitute the pattern. In this case it will be: WIDEN_DOT_PRODUCT -*/ + + Note: The dot-prod idiom is a widening reduction pattern that is + vectorized without preserving all the intermediate results. It + produces only N/2 (widened) results (by summing up pairs of + intermediate results) rather than all N results. Therefore, we + cannot allow this pattern when we want to get all the results and in + the correct order (as is the case when this computation is in an + inner-loop nested in an outer-loop that us being vectorized). */ static tree vect_recog_dot_prod_pattern (tree last_stmt, tree *type_in, tree *type_out) @@ -163,11 +167,13 @@ vect_recog_dot_prod_pattern (tree last_stmt, tree *type_in, tree *type_out) tree type, half_type; tree pattern_expr; tree prod_type; + loop_vec_info loop_info = STMT_VINFO_LOOP_VINFO (stmt_vinfo); + struct loop *loop = LOOP_VINFO_LOOP (loop_info); - if (TREE_CODE (last_stmt) != MODIFY_EXPR) + if (TREE_CODE (last_stmt) != GIMPLE_MODIFY_STMT) return NULL; - expr = TREE_OPERAND (last_stmt, 1); + expr = GIMPLE_STMT_OPERAND (last_stmt, 1); type = TREE_TYPE (expr); /* Look for the following pattern @@ -202,7 +208,7 @@ vect_recog_dot_prod_pattern (tree last_stmt, tree *type_in, tree *type_out) /* Has been detected as widening-summation? */ stmt = STMT_VINFO_RELATED_STMT (stmt_vinfo); - expr = TREE_OPERAND (stmt, 1); + expr = GIMPLE_STMT_OPERAND (stmt, 1); type = TREE_TYPE (expr); if (TREE_CODE (expr) != WIDEN_SUM_EXPR) return NULL; @@ -226,7 +232,7 @@ vect_recog_dot_prod_pattern (tree last_stmt, tree *type_in, tree *type_out) if (widened_name_p (oprnd0, stmt, &half_type, &def_stmt)) { stmt = def_stmt; - expr = TREE_OPERAND (stmt, 1); + expr = GIMPLE_STMT_OPERAND (stmt, 1); oprnd0 = TREE_OPERAND (expr, 0); } else @@ -240,12 +246,15 @@ vect_recog_dot_prod_pattern (tree last_stmt, tree *type_in, tree *type_out) prod_type = half_type; stmt = SSA_NAME_DEF_STMT (oprnd0); - gcc_assert (stmt); + /* FORNOW. Can continue analyzing the def-use chain when this stmt in a phi + inside the loop (in case we are analyzing an outer-loop). */ + if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT) + return NULL; stmt_vinfo = vinfo_for_stmt (stmt); gcc_assert (stmt_vinfo); if (STMT_VINFO_DEF_TYPE (stmt_vinfo) != vect_loop_def) return NULL; - expr = TREE_OPERAND (stmt, 1); + expr = GIMPLE_STMT_OPERAND (stmt, 1); if (TREE_CODE (expr) != MULT_EXPR) return NULL; if (STMT_VINFO_IN_PATTERN_P (stmt_vinfo)) @@ -253,7 +262,7 @@ vect_recog_dot_prod_pattern (tree last_stmt, tree *type_in, tree *type_out) /* Has been detected as a widening multiplication? */ stmt = STMT_VINFO_RELATED_STMT (stmt_vinfo); - expr = TREE_OPERAND (stmt, 1); + expr = GIMPLE_STMT_OPERAND (stmt, 1); if (TREE_CODE (expr) != WIDEN_MULT_EXPR) return NULL; stmt_vinfo = vinfo_for_stmt (stmt); @@ -277,10 +286,10 @@ vect_recog_dot_prod_pattern (tree last_stmt, tree *type_in, tree *type_out) return NULL; if (!widened_name_p (oprnd0, stmt, &half_type0, &def_stmt)) return NULL; - oprnd00 = TREE_OPERAND (TREE_OPERAND (def_stmt, 1), 0); + oprnd00 = TREE_OPERAND (GIMPLE_STMT_OPERAND (def_stmt, 1), 0); if (!widened_name_p (oprnd1, stmt, &half_type1, &def_stmt)) return NULL; - oprnd01 = TREE_OPERAND (TREE_OPERAND (def_stmt, 1), 0); + oprnd01 = TREE_OPERAND (GIMPLE_STMT_OPERAND (def_stmt, 1), 0); if (TYPE_MAIN_VARIANT (half_type0) != TYPE_MAIN_VARIANT (half_type1)) return NULL; if (TYPE_PRECISION (prod_type) != TYPE_PRECISION (half_type0) * 2) @@ -298,6 +307,16 @@ vect_recog_dot_prod_pattern (tree last_stmt, tree *type_in, tree *type_out) fprintf (vect_dump, "vect_recog_dot_prod_pattern: detected: "); print_generic_expr (vect_dump, pattern_expr, TDF_SLIM); } + + /* We don't allow changing the order of the computation in the inner-loop + when doing outer-loop vectorization. */ + if (nested_in_vect_loop_p (loop, last_stmt)) + { + if (vect_print_dump_info (REPORT_DETAILS)) + fprintf (vect_dump, "vect_recog_dot_prod_pattern: not allowed."); + return NULL; + } + return pattern_expr; } @@ -334,12 +353,163 @@ vect_recog_dot_prod_pattern (tree last_stmt, tree *type_in, tree *type_out) */ static tree -vect_recog_widen_mult_pattern (tree last_stmt ATTRIBUTE_UNUSED, - tree *type_in ATTRIBUTE_UNUSED, - tree *type_out ATTRIBUTE_UNUSED) +vect_recog_widen_mult_pattern (tree last_stmt, + tree *type_in, + tree *type_out) { - /* Yet to be implemented. */ - return NULL; + tree expr; + tree def_stmt0, def_stmt1; + tree oprnd0, oprnd1; + tree type, half_type0, half_type1; + tree pattern_expr; + tree vectype; + tree dummy; + enum tree_code dummy_code; + + if (TREE_CODE (last_stmt) != GIMPLE_MODIFY_STMT) + return NULL; + + expr = GIMPLE_STMT_OPERAND (last_stmt, 1); + type = TREE_TYPE (expr); + + /* Starting from LAST_STMT, follow the defs of its uses in search + of the above pattern. */ + + if (TREE_CODE (expr) != MULT_EXPR) + return NULL; + + oprnd0 = TREE_OPERAND (expr, 0); + oprnd1 = TREE_OPERAND (expr, 1); + if (TYPE_MAIN_VARIANT (TREE_TYPE (oprnd0)) != TYPE_MAIN_VARIANT (type) + || TYPE_MAIN_VARIANT (TREE_TYPE (oprnd1)) != TYPE_MAIN_VARIANT (type)) + return NULL; + + /* Check argument 0 */ + if (!widened_name_p (oprnd0, last_stmt, &half_type0, &def_stmt0)) + return NULL; + oprnd0 = TREE_OPERAND (GIMPLE_STMT_OPERAND (def_stmt0, 1), 0); + + /* Check argument 1 */ + if (!widened_name_p (oprnd1, last_stmt, &half_type1, &def_stmt1)) + return NULL; + oprnd1 = TREE_OPERAND (GIMPLE_STMT_OPERAND (def_stmt1, 1), 0); + + if (TYPE_MAIN_VARIANT (half_type0) != TYPE_MAIN_VARIANT (half_type1)) + return NULL; + + /* Pattern detected. */ + if (vect_print_dump_info (REPORT_DETAILS)) + fprintf (vect_dump, "vect_recog_widen_mult_pattern: detected: "); + + /* Check target support */ + vectype = get_vectype_for_scalar_type (half_type0); + if (!vectype + || !supportable_widening_operation (WIDEN_MULT_EXPR, last_stmt, vectype, + &dummy, &dummy, &dummy_code, + &dummy_code)) + return NULL; + + *type_in = vectype; + *type_out = NULL_TREE; + + /* Pattern supported. Create a stmt to be used to replace the pattern: */ + pattern_expr = build2 (WIDEN_MULT_EXPR, type, oprnd0, oprnd1); + if (vect_print_dump_info (REPORT_DETAILS)) + print_generic_expr (vect_dump, pattern_expr, TDF_SLIM); + return pattern_expr; +} + + +/* Function vect_recog_pow_pattern + + Try to find the following pattern: + + x = POW (y, N); + + with POW being one of pow, powf, powi, powif and N being + either 2 or 0.5. + + Input: + + * LAST_STMT: A stmt from which the pattern search begins. + + Output: + + * TYPE_IN: The type of the input arguments to the pattern. + + * TYPE_OUT: The type of the output of this pattern. + + * Return value: A new stmt that will be used to replace the sequence of + stmts that constitute the pattern. In this case it will be: + x * x + or + sqrt (x) +*/ + +static tree +vect_recog_pow_pattern (tree last_stmt, tree *type_in, tree *type_out) +{ + tree expr; + tree type; + tree fn, base, exp; + + if (TREE_CODE (last_stmt) != GIMPLE_MODIFY_STMT) + return NULL; + + expr = GIMPLE_STMT_OPERAND (last_stmt, 1); + type = TREE_TYPE (expr); + + if (TREE_CODE (expr) != CALL_EXPR) + return NULL_TREE; + + fn = get_callee_fndecl (expr); + switch (DECL_FUNCTION_CODE (fn)) + { + case BUILT_IN_POWIF: + case BUILT_IN_POWI: + case BUILT_IN_POWF: + case BUILT_IN_POW: + base = CALL_EXPR_ARG (expr, 0); + exp = CALL_EXPR_ARG (expr, 1); + if (TREE_CODE (exp) != REAL_CST + && TREE_CODE (exp) != INTEGER_CST) + return NULL_TREE; + break; + + default:; + return NULL_TREE; + } + + /* We now have a pow or powi builtin function call with a constant + exponent. */ + + *type_out = NULL_TREE; + + /* Catch squaring. */ + if ((host_integerp (exp, 0) + && tree_low_cst (exp, 0) == 2) + || (TREE_CODE (exp) == REAL_CST + && REAL_VALUES_EQUAL (TREE_REAL_CST (exp), dconst2))) + { + *type_in = TREE_TYPE (base); + return build2 (MULT_EXPR, TREE_TYPE (base), base, base); + } + + /* Catch square root. */ + if (TREE_CODE (exp) == REAL_CST + && REAL_VALUES_EQUAL (TREE_REAL_CST (exp), dconsthalf)) + { + tree newfn = mathfn_built_in (TREE_TYPE (base), BUILT_IN_SQRT); + *type_in = get_vectype_for_scalar_type (TREE_TYPE (base)); + if (*type_in) + { + newfn = build_call_expr (newfn, 1, base); + if (vectorizable_function (newfn, *type_in, *type_in) != NULL_TREE) + return newfn; + } + } + + return NULL_TREE; } @@ -373,7 +543,14 @@ vect_recog_widen_mult_pattern (tree last_stmt ATTRIBUTE_UNUSED, * Return value: A new stmt that will be used to replace the sequence of stmts that constitute the pattern. In this case it will be: WIDEN_SUM -*/ + + Note: The widening-sum idiom is a widening reduction pattern that is + vectorized without preserving all the intermediate results. It + produces only N/2 (widened) results (by summing up pairs of + intermediate results) rather than all N results. Therefore, we + cannot allow this pattern when we want to get all the results and in + the correct order (as is the case when this computation is in an + inner-loop nested in an outer-loop that us being vectorized). */ static tree vect_recog_widen_sum_pattern (tree last_stmt, tree *type_in, tree *type_out) @@ -383,11 +560,13 @@ vect_recog_widen_sum_pattern (tree last_stmt, tree *type_in, tree *type_out) stmt_vec_info stmt_vinfo = vinfo_for_stmt (last_stmt); tree type, half_type; tree pattern_expr; + loop_vec_info loop_info = STMT_VINFO_LOOP_VINFO (stmt_vinfo); + struct loop *loop = LOOP_VINFO_LOOP (loop_info); - if (TREE_CODE (last_stmt) != MODIFY_EXPR) + if (TREE_CODE (last_stmt) != GIMPLE_MODIFY_STMT) return NULL; - expr = TREE_OPERAND (last_stmt, 1); + expr = GIMPLE_STMT_OPERAND (last_stmt, 1); type = TREE_TYPE (expr); /* Look for the following pattern @@ -421,7 +600,7 @@ vect_recog_widen_sum_pattern (tree last_stmt, tree *type_in, tree *type_out) if (!widened_name_p (oprnd0, last_stmt, &half_type, &stmt)) return NULL; - oprnd0 = TREE_OPERAND (TREE_OPERAND (stmt, 1), 0); + oprnd0 = TREE_OPERAND (GIMPLE_STMT_OPERAND (stmt, 1), 0); *type_in = half_type; *type_out = type; @@ -432,6 +611,16 @@ vect_recog_widen_sum_pattern (tree last_stmt, tree *type_in, tree *type_out) fprintf (vect_dump, "vect_recog_widen_sum_pattern: detected: "); print_generic_expr (vect_dump, pattern_expr, TDF_SLIM); } + + /* We don't allow changing the order of the computation in the inner-loop + when doing outer-loop vectorization. */ + if (nested_in_vect_loop_p (loop, last_stmt)) + { + if (vect_print_dump_info (REPORT_DETAILS)) + fprintf (vect_dump, "vect_recog_widen_sum_pattern: not allowed."); + return NULL; + } + return pattern_expr; } @@ -493,14 +682,18 @@ vect_pattern_recog_1 ( /* Check target support */ pattern_vectype = get_vectype_for_scalar_type (type_in); + if (!pattern_vectype) + return; + optab = optab_for_tree_code (TREE_CODE (pattern_expr), pattern_vectype); vec_mode = TYPE_MODE (pattern_vectype); if (!optab - || (icode = optab->handlers[(int) vec_mode].insn_code) == + || (icode = optab_handler (optab, vec_mode)->insn_code) == CODE_FOR_nothing || (type_out - && (insn_data[icode].operand[0].mode != - TYPE_MODE (get_vectype_for_scalar_type (type_out))))) + && (!get_vectype_for_scalar_type (type_out) + || (insn_data[icode].operand[0].mode != + TYPE_MODE (get_vectype_for_scalar_type (type_out)))))) return; } @@ -516,13 +709,13 @@ vect_pattern_recog_1 ( code = TREE_CODE (pattern_expr); pattern_type = TREE_TYPE (pattern_expr); var = create_tmp_var (pattern_type, "patt"); - add_referenced_tmp_var (var); + add_referenced_var (var); var_name = make_ssa_name (var, NULL_TREE); - pattern_expr = build2 (MODIFY_EXPR, void_type_node, var_name, pattern_expr); + pattern_expr = build_gimple_modify_stmt (var_name, pattern_expr); SSA_NAME_DEF_STMT (var_name) = pattern_expr; bsi_insert_before (&si, pattern_expr, BSI_SAME_STMT); ann = stmt_ann (pattern_expr); - set_stmt_info ((tree_ann_t)ann, new_stmt_vec_info (pattern_expr, loop_vinfo)); + set_stmt_info (ann, new_stmt_vec_info (pattern_expr, loop_vinfo)); pattern_stmt_info = vinfo_for_stmt (pattern_expr); STMT_VINFO_RELATED_STMT (pattern_stmt_info) = stmt;