diff options
Diffstat (limited to 'gcc-4.2.1-5666.3/gcc/tree-vect-patterns.c')
| -rw-r--r-- | gcc-4.2.1-5666.3/gcc/tree-vect-patterns.c | 638 |
1 files changed, 638 insertions, 0 deletions
diff --git a/gcc-4.2.1-5666.3/gcc/tree-vect-patterns.c b/gcc-4.2.1-5666.3/gcc/tree-vect-patterns.c new file mode 100644 index 000000000..9ac11b07b --- /dev/null +++ b/gcc-4.2.1-5666.3/gcc/tree-vect-patterns.c @@ -0,0 +1,638 @@ +/* Analysis Utilities for Loop Vectorization. + Copyright (C) 2006 Free Software Foundation, Inc. + Contributed by Dorit Nuzman <dorit@il.ibm.com> + +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 +version. + +GCC is distributed in the hope that it will be useful, but WITHOUT ANY +WARRANTY; without even the implied warranty of MERCHANTABILITY or +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. */ + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "tm.h" +#include "ggc.h" +#include "tree.h" + +#include "target.h" +#include "basic-block.h" +#include "diagnostic.h" +#include "tree-flow.h" +#include "tree-dump.h" +#include "timevar.h" +#include "cfgloop.h" +#include "expr.h" +#include "optabs.h" +#include "params.h" +#include "tree-data-ref.h" +#include "tree-vectorizer.h" +#include "recog.h" +#include "toplev.h" + +/* Function prototypes */ +static void vect_pattern_recog_1 + (tree (* ) (tree, tree *, tree *), block_stmt_iterator); +static bool widened_name_p (tree, tree, tree *, tree *); + +/* Pattern recognition functions */ +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 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}; + + +/* Function widened_name_p + + Check whether NAME, an ssa-name used in USE_STMT, + is a result of a type-promotion, such that: + DEF_STMT: NAME = NOP (name0) + where the type of name0 (HALF_TYPE) is smaller than the type of NAME. +*/ + +static bool +widened_name_p (tree name, tree use_stmt, tree *half_type, tree *def_stmt) +{ + tree dummy; + loop_vec_info loop_vinfo; + stmt_vec_info stmt_vinfo; + tree expr; + tree type = TREE_TYPE (name); + tree oprnd0; + enum vect_def_type dt; + tree def; + + stmt_vinfo = vinfo_for_stmt (use_stmt); + loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_vinfo); + + if (!vect_is_simple_use (name, loop_vinfo, def_stmt, &def, &dt)) + return false; + + if (dt != vect_loop_def + && dt != vect_invariant_def && dt != vect_constant_def) + return false; + + if (! *def_stmt) + return false; + + if (TREE_CODE (*def_stmt) != MODIFY_EXPR) + return false; + + expr = TREE_OPERAND (*def_stmt, 1); + if (TREE_CODE (expr) != NOP_EXPR) + return false; + + oprnd0 = TREE_OPERAND (expr, 0); + + *half_type = TREE_TYPE (oprnd0); + if (!INTEGRAL_TYPE_P (type) || !INTEGRAL_TYPE_P (*half_type) + || (TYPE_UNSIGNED (type) != TYPE_UNSIGNED (*half_type)) + || (TYPE_PRECISION (type) < (TYPE_PRECISION (*half_type) * 2))) + return false; + + 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; +} + + +/* Function vect_recog_dot_prod_pattern + + Try to find the following pattern: + + type x_t, y_t; + TYPE1 prod; + TYPE2 sum = init; + loop: + sum_0 = phi <init, sum_1> + S1 x_t = ... + S2 y_t = ... + S3 x_T = (TYPE1) x_t; + S4 y_T = (TYPE1) y_t; + S5 prod = x_T * y_T; + [S6 prod = (TYPE2) prod; #optional] + S7 sum_1 = prod + sum_0; + + where 'TYPE1' is exactly double the size of type 'type', and 'TYPE2' is the + same size of 'TYPE1' or bigger. This is a special case of a reduction + computation. + + Input: + + * LAST_STMT: A stmt from which the pattern search begins. In the example, + when this function is called with S7, the pattern {S3,S4,S5,S6,S7} will be + detected. + + 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: + WIDEN_DOT_PRODUCT <x_t, y_t, sum_0> +*/ + +static tree +vect_recog_dot_prod_pattern (tree last_stmt, tree *type_in, tree *type_out) +{ + tree stmt, expr; + tree oprnd0, oprnd1; + tree oprnd00, oprnd01; + stmt_vec_info stmt_vinfo = vinfo_for_stmt (last_stmt); + tree type, half_type; + tree pattern_expr; + tree prod_type; + + if (TREE_CODE (last_stmt) != MODIFY_EXPR) + return NULL; + + expr = TREE_OPERAND (last_stmt, 1); + type = TREE_TYPE (expr); + + /* Look for the following pattern + DX = (TYPE1) X; + DY = (TYPE1) Y; + DPROD = DX * DY; + DDPROD = (TYPE2) DPROD; + sum_1 = DDPROD + sum_0; + In which + - DX is double the size of X + - DY is double the size of Y + - DX, DY, DPROD all have the same type + - sum is the same size of DPROD or bigger + - sum has been recognized as a reduction variable. + + This is equivalent to: + DPROD = X w* Y; #widen mult + sum_1 = DPROD w+ sum_0; #widen summation + or + DPROD = X w* Y; #widen mult + sum_1 = DPROD + sum_0; #summation + */ + + /* Starting from LAST_STMT, follow the defs of its uses in search + of the above pattern. */ + + if (TREE_CODE (expr) != PLUS_EXPR) + return NULL; + + if (STMT_VINFO_IN_PATTERN_P (stmt_vinfo)) + { + /* Has been detected as widening-summation? */ + + stmt = STMT_VINFO_RELATED_STMT (stmt_vinfo); + expr = TREE_OPERAND (stmt, 1); + type = TREE_TYPE (expr); + if (TREE_CODE (expr) != WIDEN_SUM_EXPR) + return NULL; + oprnd0 = TREE_OPERAND (expr, 0); + oprnd1 = TREE_OPERAND (expr, 1); + half_type = TREE_TYPE (oprnd0); + } + else + { + tree def_stmt; + + if (STMT_VINFO_DEF_TYPE (stmt_vinfo) != vect_reduction_def) + 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; + stmt = last_stmt; + + if (widened_name_p (oprnd0, stmt, &half_type, &def_stmt)) + { + stmt = def_stmt; + expr = TREE_OPERAND (stmt, 1); + oprnd0 = TREE_OPERAND (expr, 0); + } + else + half_type = type; + } + + /* So far so good. Since last_stmt was detected as a (summation) reduction, + we know that oprnd1 is the reduction variable (defined by a loop-header + phi), and oprnd0 is an ssa-name defined by a stmt in the loop body. + Left to check that oprnd0 is defined by a (widen_)mult_expr */ + + prod_type = half_type; + stmt = SSA_NAME_DEF_STMT (oprnd0); + gcc_assert (stmt); + 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); + if (TREE_CODE (expr) != MULT_EXPR) + return NULL; + if (STMT_VINFO_IN_PATTERN_P (stmt_vinfo)) + { + /* Has been detected as a widening multiplication? */ + + stmt = STMT_VINFO_RELATED_STMT (stmt_vinfo); + expr = TREE_OPERAND (stmt, 1); + if (TREE_CODE (expr) != WIDEN_MULT_EXPR) + return NULL; + stmt_vinfo = vinfo_for_stmt (stmt); + gcc_assert (stmt_vinfo); + gcc_assert (STMT_VINFO_DEF_TYPE (stmt_vinfo) == vect_loop_def); + oprnd00 = TREE_OPERAND (expr, 0); + oprnd01 = TREE_OPERAND (expr, 1); + } + else + { + tree half_type0, half_type1; + tree def_stmt; + tree oprnd0, oprnd1; + + oprnd0 = TREE_OPERAND (expr, 0); + oprnd1 = TREE_OPERAND (expr, 1); + if (TYPE_MAIN_VARIANT (TREE_TYPE (oprnd0)) + != TYPE_MAIN_VARIANT (prod_type) + || TYPE_MAIN_VARIANT (TREE_TYPE (oprnd1)) + != TYPE_MAIN_VARIANT (prod_type)) + return NULL; + if (!widened_name_p (oprnd0, stmt, &half_type0, &def_stmt)) + return NULL; + oprnd00 = TREE_OPERAND (TREE_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); + if (TYPE_MAIN_VARIANT (half_type0) != TYPE_MAIN_VARIANT (half_type1)) + return NULL; + if (TYPE_PRECISION (prod_type) != TYPE_PRECISION (half_type0) * 2) + return NULL; + } + + half_type = TREE_TYPE (oprnd00); + *type_in = half_type; + *type_out = type; + + /* Pattern detected. Create a stmt to be used to replace the pattern: */ + pattern_expr = build3 (DOT_PROD_EXPR, type, oprnd00, oprnd01, oprnd1); + if (vect_print_dump_info (REPORT_DETAILS)) + { + fprintf (vect_dump, "vect_recog_dot_prod_pattern: detected: "); + print_generic_expr (vect_dump, pattern_expr, TDF_SLIM); + } + return pattern_expr; +} + + +/* Function vect_recog_widen_mult_pattern + + Try to find the following pattern: + + type a_t, b_t; + TYPE a_T, b_T, prod_T; + + S1 a_t = ; + S2 b_t = ; + S3 a_T = (TYPE) a_t; + S4 b_T = (TYPE) b_t; + S5 prod_T = a_T * b_T; + + where type 'TYPE' is at least double the size of type 'type'. + + Input: + + * LAST_STMT: A stmt from which the pattern search begins. In the example, + when this function is called with S5, the pattern {S3,S4,S5} is be detected. + + 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: + WIDEN_MULT <a_t, b_t> +*/ + +static tree +vect_recog_widen_mult_pattern (tree last_stmt ATTRIBUTE_UNUSED, + tree *type_in ATTRIBUTE_UNUSED, + tree *type_out ATTRIBUTE_UNUSED) +{ + /* Yet to be implemented. */ + return NULL; +} + + +/* Function vect_recog_widen_sum_pattern + + Try to find the following pattern: + + type x_t; + TYPE x_T, sum = init; + loop: + sum_0 = phi <init, sum_1> + S1 x_t = *p; + S2 x_T = (TYPE) x_t; + S3 sum_1 = x_T + sum_0; + + where type 'TYPE' is at least double the size of type 'type', i.e - we're + summing elements of type 'type' into an accumulator of type 'TYPE'. This is + a special case of a reduction computation. + + Input: + + * LAST_STMT: A stmt from which the pattern search begins. In the example, + when this function is called with S3, the pattern {S2,S3} will be detected. + + 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: + WIDEN_SUM <x_t, sum_0> +*/ + +static tree +vect_recog_widen_sum_pattern (tree last_stmt, tree *type_in, tree *type_out) +{ + tree stmt, expr; + tree oprnd0, oprnd1; + stmt_vec_info stmt_vinfo = vinfo_for_stmt (last_stmt); + tree type, half_type; + tree pattern_expr; + + if (TREE_CODE (last_stmt) != MODIFY_EXPR) + return NULL; + + expr = TREE_OPERAND (last_stmt, 1); + type = TREE_TYPE (expr); + + /* Look for the following pattern + DX = (TYPE) X; + sum_1 = DX + sum_0; + In which DX is at least double the size of X, and sum_1 has been + recognized as a reduction variable. + */ + + /* Starting from LAST_STMT, follow the defs of its uses in search + of the above pattern. */ + + if (TREE_CODE (expr) != PLUS_EXPR) + return NULL; + + if (STMT_VINFO_DEF_TYPE (stmt_vinfo) != vect_reduction_def) + 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; + + /* So far so good. Since last_stmt was detected as a (summation) reduction, + we know that oprnd1 is the reduction variable (defined by a loop-header + phi), and oprnd0 is an ssa-name defined by a stmt in the loop body. + Left to check that oprnd0 is defined by a cast from type 'type' to type + 'TYPE'. */ + + if (!widened_name_p (oprnd0, last_stmt, &half_type, &stmt)) + return NULL; + + oprnd0 = TREE_OPERAND (TREE_OPERAND (stmt, 1), 0); + *type_in = half_type; + *type_out = type; + + /* Pattern detected. Create a stmt to be used to replace the pattern: */ + pattern_expr = build2 (WIDEN_SUM_EXPR, type, oprnd0, oprnd1); + if (vect_print_dump_info (REPORT_DETAILS)) + { + fprintf (vect_dump, "vect_recog_widen_sum_pattern: detected: "); + print_generic_expr (vect_dump, pattern_expr, TDF_SLIM); + } + return pattern_expr; +} + + +/* Function vect_pattern_recog_1 + + Input: + PATTERN_RECOG_FUNC: A pointer to a function that detects a certain + computation pattern. + STMT: A stmt from which the pattern search should start. + + If PATTERN_RECOG_FUNC successfully detected the pattern, it creates an + expression that computes the same functionality and can be used to + replace the sequence of stmts that are involved in the pattern. + + Output: + This function checks if the expression returned by PATTERN_RECOG_FUNC is + supported in vector form by the target. We use 'TYPE_IN' to obtain the + relevant vector type. If 'TYPE_IN' is already a vector type, then this + indicates that target support had already been checked by PATTERN_RECOG_FUNC. + If 'TYPE_OUT' is also returned by PATTERN_RECOG_FUNC, we check that it fits + to the available target pattern. + + This function also does some bookkeeping, as explained in the documentation + for vect_recog_pattern. */ + +static void +vect_pattern_recog_1 ( + tree (* vect_recog_func) (tree, tree *, tree *), + block_stmt_iterator si) +{ + tree stmt = bsi_stmt (si); + stmt_vec_info stmt_info = vinfo_for_stmt (stmt); + stmt_vec_info pattern_stmt_info; + loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info); + tree pattern_expr; + tree pattern_vectype; + tree type_in, type_out; + tree pattern_type; + enum tree_code code; + tree var, var_name; + stmt_ann_t ann; + + pattern_expr = (* vect_recog_func) (stmt, &type_in, &type_out); + if (!pattern_expr) + return; + + if (VECTOR_MODE_P (TYPE_MODE (type_in))) + { + /* No need to check target support (already checked by the pattern + recognition function). */ + pattern_vectype = type_in; + } + else + { + enum tree_code vec_mode; + enum insn_code icode; + optab optab; + + /* Check target support */ + pattern_vectype = get_vectype_for_scalar_type (type_in); + 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) == + CODE_FOR_nothing + || (type_out + && (insn_data[icode].operand[0].mode != + TYPE_MODE (get_vectype_for_scalar_type (type_out))))) + return; + } + + /* Found a vectorizable pattern. */ + if (vect_print_dump_info (REPORT_DETAILS)) + { + fprintf (vect_dump, "pattern recognized: "); + print_generic_expr (vect_dump, pattern_expr, TDF_SLIM); + } + + /* Mark the stmts that are involved in the pattern, + create a new stmt to express the pattern and insert it. */ + code = TREE_CODE (pattern_expr); + pattern_type = TREE_TYPE (pattern_expr); + var = create_tmp_var (pattern_type, "patt"); + add_referenced_var (var); + var_name = make_ssa_name (var, NULL_TREE); + pattern_expr = build2 (MODIFY_EXPR, void_type_node, 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 (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; + STMT_VINFO_DEF_TYPE (pattern_stmt_info) = STMT_VINFO_DEF_TYPE (stmt_info); + STMT_VINFO_VECTYPE (pattern_stmt_info) = pattern_vectype; + STMT_VINFO_IN_PATTERN_P (stmt_info) = true; + STMT_VINFO_RELATED_STMT (stmt_info) = pattern_expr; + + return; +} + + +/* Function vect_pattern_recog + + Input: + LOOP_VINFO - a struct_loop_info of a loop in which we want to look for + computation idioms. + + Output - for each computation idiom that is detected we insert a new stmt + that provides the same functionality and that can be vectorized. We + also record some information in the struct_stmt_info of the relevant + stmts, as explained below: + + At the entry to this function we have the following stmts, with the + following initial value in the STMT_VINFO fields: + + stmt in_pattern_p related_stmt vec_stmt + S1: a_i = .... - - - + S2: a_2 = ..use(a_i).. - - - + S3: a_1 = ..use(a_2).. - - - + S4: a_0 = ..use(a_1).. - - - + S5: ... = ..use(a_0).. - - - + + Say the sequence {S1,S2,S3,S4} was detected as a pattern that can be + represented by a single stmt. We then: + - create a new stmt S6 that will replace the pattern. + - insert the new stmt S6 before the last stmt in the pattern + - fill in the STMT_VINFO fields as follows: + + in_pattern_p related_stmt vec_stmt + S1: a_i = .... - - - + S2: a_2 = ..use(a_i).. - - - + S3: a_1 = ..use(a_2).. - - - + > S6: a_new = .... - S4 - + S4: a_0 = ..use(a_1).. true S6 - + S5: ... = ..use(a_0).. - - - + + (the last stmt in the pattern (S4) and the new pattern stmt (S6) point + to each other through the RELATED_STMT field). + + S6 will be marked as relevant in vect_mark_stmts_to_be_vectorized instead + of S4 because it will replace all its uses. Stmts {S1,S2,S3} will + remain irrelevant unless used by stmts other than S4. + + If vectorization succeeds, vect_transform_stmt will skip over {S1,S2,S3} + (because they are marked as irrelevant). It will vectorize S6, and record + a pointer to the new vector stmt VS6 both from S6 (as usual), and also + from S4. We do that so that when we get to vectorizing stmts that use the + def of S4 (like S5 that uses a_0), we'll know where to take the relevant + vector-def from. S4 will be skipped, and S5 will be vectorized as usual: + + in_pattern_p related_stmt vec_stmt + S1: a_i = .... - - - + S2: a_2 = ..use(a_i).. - - - + S3: a_1 = ..use(a_2).. - - - + > VS6: va_new = .... - - - + S6: a_new = .... - S4 VS6 + S4: a_0 = ..use(a_1).. true S6 VS6 + > VS5: ... = ..vuse(va_new).. - - - + S5: ... = ..use(a_0).. - - - + + DCE could then get rid of {S1,S2,S3,S4,S5,S6} (if their defs are not used + elsewhere), and we'll end up with: + + VS6: va_new = .... + VS5: ... = ..vuse(va_new).. + + If vectorization does not succeed, DCE will clean S6 away (its def is + not used), and we'll end up with the original sequence. +*/ + +void +vect_pattern_recog (loop_vec_info loop_vinfo) +{ + struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo); + basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo); + unsigned int nbbs = loop->num_nodes; + block_stmt_iterator si; + tree stmt; + unsigned int i, j; + tree (* vect_recog_func_ptr) (tree, tree *, tree *); + + if (vect_print_dump_info (REPORT_DETAILS)) + fprintf (vect_dump, "=== vect_pattern_recog ==="); + + /* Scan through the loop stmts, applying the pattern recognition + functions starting at each stmt visited: */ + for (i = 0; i < nbbs; i++) + { + basic_block bb = bbs[i]; + for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si)) + { + stmt = bsi_stmt (si); + + /* Scan over all generic vect_recog_xxx_pattern functions. */ + for (j = 0; j < NUM_PATTERNS; j++) + { + vect_recog_func_ptr = vect_vect_recog_func_ptrs[j]; + vect_pattern_recog_1 (vect_recog_func_ptr, si); + } + } + } +} |