X-Git-Url: https://oss.titaniummirror.com/gitweb?a=blobdiff_plain;f=gcc%2Ftree-vect-generic.c;fp=gcc%2Ftree-vect-generic.c;h=c472442c6f9758c34d75dc42268944a8ea8efc2a;hb=6fed43773c9b0ce596dca5686f37ac3fc0fa11c0;hp=0000000000000000000000000000000000000000;hpb=27b11d56b743098deb193d510b337ba22dc52e5c;p=msp430-gcc.git diff --git a/gcc/tree-vect-generic.c b/gcc/tree-vect-generic.c new file mode 100644 index 00000000..c472442c --- /dev/null +++ b/gcc/tree-vect-generic.c @@ -0,0 +1,591 @@ +/* Lower vector operations to scalar operations. + Copyright (C) 2004, 2005, 2006, 2007, 2008 Free Software Foundation, Inc. + +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 3, 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 COPYING3. If not see +. */ + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "tree.h" +#include "tm.h" +#include "rtl.h" +#include "expr.h" +#include "insn-codes.h" +#include "diagnostic.h" +#include "optabs.h" +#include "machmode.h" +#include "langhooks.h" +#include "tree-flow.h" +#include "gimple.h" +#include "tree-iterator.h" +#include "tree-pass.h" +#include "flags.h" +#include "ggc.h" + + +/* Build a constant of type TYPE, made of VALUE's bits replicated + every TYPE_SIZE (INNER_TYPE) bits to fit TYPE's precision. */ +static tree +build_replicated_const (tree type, tree inner_type, HOST_WIDE_INT value) +{ + int width = tree_low_cst (TYPE_SIZE (inner_type), 1); + int n = HOST_BITS_PER_WIDE_INT / width; + unsigned HOST_WIDE_INT low, high, mask; + tree ret; + + gcc_assert (n); + + if (width == HOST_BITS_PER_WIDE_INT) + low = value; + else + { + mask = ((HOST_WIDE_INT)1 << width) - 1; + low = (unsigned HOST_WIDE_INT) ~0 / mask * (value & mask); + } + + if (TYPE_PRECISION (type) < HOST_BITS_PER_WIDE_INT) + low &= ((HOST_WIDE_INT)1 << TYPE_PRECISION (type)) - 1, high = 0; + else if (TYPE_PRECISION (type) == HOST_BITS_PER_WIDE_INT) + high = 0; + else if (TYPE_PRECISION (type) == 2 * HOST_BITS_PER_WIDE_INT) + high = low; + else + gcc_unreachable (); + + ret = build_int_cst_wide (type, low, high); + return ret; +} + +static GTY(()) tree vector_inner_type; +static GTY(()) tree vector_last_type; +static GTY(()) int vector_last_nunits; + +/* Return a suitable vector types made of SUBPARTS units each of mode + "word_mode" (the global variable). */ +static tree +build_word_mode_vector_type (int nunits) +{ + if (!vector_inner_type) + vector_inner_type = lang_hooks.types.type_for_mode (word_mode, 1); + else if (vector_last_nunits == nunits) + { + gcc_assert (TREE_CODE (vector_last_type) == VECTOR_TYPE); + return vector_last_type; + } + + /* We build a new type, but we canonicalize it nevertheless, + because it still saves some memory. */ + vector_last_nunits = nunits; + vector_last_type = type_hash_canon (nunits, + build_vector_type (vector_inner_type, + nunits)); + return vector_last_type; +} + +typedef tree (*elem_op_func) (gimple_stmt_iterator *, + tree, tree, tree, tree, tree, enum tree_code); + +static inline tree +tree_vec_extract (gimple_stmt_iterator *gsi, tree type, + tree t, tree bitsize, tree bitpos) +{ + if (bitpos) + return gimplify_build3 (gsi, BIT_FIELD_REF, type, t, bitsize, bitpos); + else + return gimplify_build1 (gsi, VIEW_CONVERT_EXPR, type, t); +} + +static tree +do_unop (gimple_stmt_iterator *gsi, tree inner_type, tree a, + tree b ATTRIBUTE_UNUSED, tree bitpos, tree bitsize, + enum tree_code code) +{ + a = tree_vec_extract (gsi, inner_type, a, bitsize, bitpos); + return gimplify_build1 (gsi, code, inner_type, a); +} + +static tree +do_binop (gimple_stmt_iterator *gsi, tree inner_type, tree a, tree b, + tree bitpos, tree bitsize, enum tree_code code) +{ + a = tree_vec_extract (gsi, inner_type, a, bitsize, bitpos); + b = tree_vec_extract (gsi, inner_type, b, bitsize, bitpos); + return gimplify_build2 (gsi, code, inner_type, a, b); +} + +/* Expand vector addition to scalars. This does bit twiddling + in order to increase parallelism: + + a + b = (((int) a & 0x7f7f7f7f) + ((int) b & 0x7f7f7f7f)) ^ + (a ^ b) & 0x80808080 + + a - b = (((int) a | 0x80808080) - ((int) b & 0x7f7f7f7f)) ^ + (a ^ ~b) & 0x80808080 + + -b = (0x80808080 - ((int) b & 0x7f7f7f7f)) ^ (~b & 0x80808080) + + This optimization should be done only if 4 vector items or more + fit into a word. */ +static tree +do_plus_minus (gimple_stmt_iterator *gsi, tree word_type, tree a, tree b, + tree bitpos ATTRIBUTE_UNUSED, tree bitsize ATTRIBUTE_UNUSED, + enum tree_code code) +{ + tree inner_type = TREE_TYPE (TREE_TYPE (a)); + unsigned HOST_WIDE_INT max; + tree low_bits, high_bits, a_low, b_low, result_low, signs; + + max = GET_MODE_MASK (TYPE_MODE (inner_type)); + low_bits = build_replicated_const (word_type, inner_type, max >> 1); + high_bits = build_replicated_const (word_type, inner_type, max & ~(max >> 1)); + + a = tree_vec_extract (gsi, word_type, a, bitsize, bitpos); + b = tree_vec_extract (gsi, word_type, b, bitsize, bitpos); + + signs = gimplify_build2 (gsi, BIT_XOR_EXPR, word_type, a, b); + b_low = gimplify_build2 (gsi, BIT_AND_EXPR, word_type, b, low_bits); + if (code == PLUS_EXPR) + a_low = gimplify_build2 (gsi, BIT_AND_EXPR, word_type, a, low_bits); + else + { + a_low = gimplify_build2 (gsi, BIT_IOR_EXPR, word_type, a, high_bits); + signs = gimplify_build1 (gsi, BIT_NOT_EXPR, word_type, signs); + } + + signs = gimplify_build2 (gsi, BIT_AND_EXPR, word_type, signs, high_bits); + result_low = gimplify_build2 (gsi, code, word_type, a_low, b_low); + return gimplify_build2 (gsi, BIT_XOR_EXPR, word_type, result_low, signs); +} + +static tree +do_negate (gimple_stmt_iterator *gsi, tree word_type, tree b, + tree unused ATTRIBUTE_UNUSED, tree bitpos ATTRIBUTE_UNUSED, + tree bitsize ATTRIBUTE_UNUSED, + enum tree_code code ATTRIBUTE_UNUSED) +{ + tree inner_type = TREE_TYPE (TREE_TYPE (b)); + HOST_WIDE_INT max; + tree low_bits, high_bits, b_low, result_low, signs; + + max = GET_MODE_MASK (TYPE_MODE (inner_type)); + low_bits = build_replicated_const (word_type, inner_type, max >> 1); + high_bits = build_replicated_const (word_type, inner_type, max & ~(max >> 1)); + + b = tree_vec_extract (gsi, word_type, b, bitsize, bitpos); + + b_low = gimplify_build2 (gsi, BIT_AND_EXPR, word_type, b, low_bits); + signs = gimplify_build1 (gsi, BIT_NOT_EXPR, word_type, b); + signs = gimplify_build2 (gsi, BIT_AND_EXPR, word_type, signs, high_bits); + result_low = gimplify_build2 (gsi, MINUS_EXPR, word_type, high_bits, b_low); + return gimplify_build2 (gsi, BIT_XOR_EXPR, word_type, result_low, signs); +} + +/* Expand a vector operation to scalars, by using many operations + whose type is the vector type's inner type. */ +static tree +expand_vector_piecewise (gimple_stmt_iterator *gsi, elem_op_func f, + tree type, tree inner_type, + tree a, tree b, enum tree_code code) +{ + VEC(constructor_elt,gc) *v; + tree part_width = TYPE_SIZE (inner_type); + tree index = bitsize_int (0); + int nunits = TYPE_VECTOR_SUBPARTS (type); + int delta = tree_low_cst (part_width, 1) + / tree_low_cst (TYPE_SIZE (TREE_TYPE (type)), 1); + int i; + + v = VEC_alloc(constructor_elt, gc, (nunits + delta - 1) / delta); + for (i = 0; i < nunits; + i += delta, index = int_const_binop (PLUS_EXPR, index, part_width, 0)) + { + tree result = f (gsi, inner_type, a, b, index, part_width, code); + constructor_elt *ce = VEC_quick_push (constructor_elt, v, NULL); + ce->index = NULL_TREE; + ce->value = result; + } + + return build_constructor (type, v); +} + +/* Expand a vector operation to scalars with the freedom to use + a scalar integer type, or to use a different size for the items + in the vector type. */ +static tree +expand_vector_parallel (gimple_stmt_iterator *gsi, elem_op_func f, tree type, + tree a, tree b, + enum tree_code code) +{ + tree result, compute_type; + enum machine_mode mode; + int n_words = tree_low_cst (TYPE_SIZE_UNIT (type), 1) / UNITS_PER_WORD; + + /* We have three strategies. If the type is already correct, just do + the operation an element at a time. Else, if the vector is wider than + one word, do it a word at a time; finally, if the vector is smaller + than one word, do it as a scalar. */ + if (TYPE_MODE (TREE_TYPE (type)) == word_mode) + return expand_vector_piecewise (gsi, f, + type, TREE_TYPE (type), + a, b, code); + else if (n_words > 1) + { + tree word_type = build_word_mode_vector_type (n_words); + result = expand_vector_piecewise (gsi, f, + word_type, TREE_TYPE (word_type), + a, b, code); + result = force_gimple_operand_gsi (gsi, result, true, NULL, true, + GSI_SAME_STMT); + } + else + { + /* Use a single scalar operation with a mode no wider than word_mode. */ + mode = mode_for_size (tree_low_cst (TYPE_SIZE (type), 1), MODE_INT, 0); + compute_type = lang_hooks.types.type_for_mode (mode, 1); + result = f (gsi, compute_type, a, b, NULL_TREE, NULL_TREE, code); + } + + return result; +} + +/* Expand a vector operation to scalars; for integer types we can use + special bit twiddling tricks to do the sums a word at a time, using + function F_PARALLEL instead of F. These tricks are done only if + they can process at least four items, that is, only if the vector + holds at least four items and if a word can hold four items. */ +static tree +expand_vector_addition (gimple_stmt_iterator *gsi, + elem_op_func f, elem_op_func f_parallel, + tree type, tree a, tree b, enum tree_code code) +{ + int parts_per_word = UNITS_PER_WORD + / tree_low_cst (TYPE_SIZE_UNIT (TREE_TYPE (type)), 1); + + if (INTEGRAL_TYPE_P (TREE_TYPE (type)) + && parts_per_word >= 4 + && TYPE_VECTOR_SUBPARTS (type) >= 4) + return expand_vector_parallel (gsi, f_parallel, + type, a, b, code); + else + return expand_vector_piecewise (gsi, f, + type, TREE_TYPE (type), + a, b, code); +} + +static tree +expand_vector_operation (gimple_stmt_iterator *gsi, tree type, tree compute_type, + gimple assign, enum tree_code code) +{ + enum machine_mode compute_mode = TYPE_MODE (compute_type); + + /* If the compute mode is not a vector mode (hence we are not decomposing + a BLKmode vector to smaller, hardware-supported vectors), we may want + to expand the operations in parallel. */ + if (GET_MODE_CLASS (compute_mode) != MODE_VECTOR_INT + && GET_MODE_CLASS (compute_mode) != MODE_VECTOR_FLOAT + && GET_MODE_CLASS (compute_mode) != MODE_VECTOR_FRACT + && GET_MODE_CLASS (compute_mode) != MODE_VECTOR_UFRACT + && GET_MODE_CLASS (compute_mode) != MODE_VECTOR_ACCUM + && GET_MODE_CLASS (compute_mode) != MODE_VECTOR_UACCUM) + switch (code) + { + case PLUS_EXPR: + case MINUS_EXPR: + if (!TYPE_OVERFLOW_TRAPS (type)) + return expand_vector_addition (gsi, do_binop, do_plus_minus, type, + gimple_assign_rhs1 (assign), + gimple_assign_rhs2 (assign), code); + break; + + case NEGATE_EXPR: + if (!TYPE_OVERFLOW_TRAPS (type)) + return expand_vector_addition (gsi, do_unop, do_negate, type, + gimple_assign_rhs1 (assign), + NULL_TREE, code); + break; + + case BIT_AND_EXPR: + case BIT_IOR_EXPR: + case BIT_XOR_EXPR: + return expand_vector_parallel (gsi, do_binop, type, + gimple_assign_rhs1 (assign), + gimple_assign_rhs2 (assign), code); + + case BIT_NOT_EXPR: + return expand_vector_parallel (gsi, do_unop, type, + gimple_assign_rhs1 (assign), + NULL_TREE, code); + + default: + break; + } + + if (TREE_CODE_CLASS (code) == tcc_unary) + return expand_vector_piecewise (gsi, do_unop, type, compute_type, + gimple_assign_rhs1 (assign), + NULL_TREE, code); + else + return expand_vector_piecewise (gsi, do_binop, type, compute_type, + gimple_assign_rhs1 (assign), + gimple_assign_rhs2 (assign), code); +} + +/* Return a type for the widest vector mode whose components are of mode + INNER_MODE, or NULL_TREE if none is found. + SATP is true for saturating fixed-point types. */ + +static tree +type_for_widest_vector_mode (enum machine_mode inner_mode, optab op, int satp) +{ + enum machine_mode best_mode = VOIDmode, mode; + int best_nunits = 0; + + if (SCALAR_FLOAT_MODE_P (inner_mode)) + mode = MIN_MODE_VECTOR_FLOAT; + else if (SCALAR_FRACT_MODE_P (inner_mode)) + mode = MIN_MODE_VECTOR_FRACT; + else if (SCALAR_UFRACT_MODE_P (inner_mode)) + mode = MIN_MODE_VECTOR_UFRACT; + else if (SCALAR_ACCUM_MODE_P (inner_mode)) + mode = MIN_MODE_VECTOR_ACCUM; + else if (SCALAR_UACCUM_MODE_P (inner_mode)) + mode = MIN_MODE_VECTOR_UACCUM; + else + mode = MIN_MODE_VECTOR_INT; + + for (; mode != VOIDmode; mode = GET_MODE_WIDER_MODE (mode)) + if (GET_MODE_INNER (mode) == inner_mode + && GET_MODE_NUNITS (mode) > best_nunits + && optab_handler (op, mode)->insn_code != CODE_FOR_nothing) + best_mode = mode, best_nunits = GET_MODE_NUNITS (mode); + + if (best_mode == VOIDmode) + return NULL_TREE; + else + { + /* For fixed-point modes, we need to pass satp as the 2nd parameter. */ + if (ALL_FIXED_POINT_MODE_P (best_mode)) + return lang_hooks.types.type_for_mode (best_mode, satp); + + return lang_hooks.types.type_for_mode (best_mode, 1); + } +} + +/* Process one statement. If we identify a vector operation, expand it. */ + +static void +expand_vector_operations_1 (gimple_stmt_iterator *gsi) +{ + gimple stmt = gsi_stmt (*gsi); + tree lhs, rhs1, rhs2 = NULL, type, compute_type; + enum tree_code code; + enum machine_mode compute_mode; + optab op; + enum gimple_rhs_class rhs_class; + tree new_rhs; + + if (gimple_code (stmt) != GIMPLE_ASSIGN) + return; + + code = gimple_assign_rhs_code (stmt); + rhs_class = get_gimple_rhs_class (code); + + if (rhs_class != GIMPLE_UNARY_RHS && rhs_class != GIMPLE_BINARY_RHS) + return; + + lhs = gimple_assign_lhs (stmt); + rhs1 = gimple_assign_rhs1 (stmt); + type = gimple_expr_type (stmt); + if (rhs_class == GIMPLE_BINARY_RHS) + rhs2 = gimple_assign_rhs2 (stmt); + + if (TREE_CODE (type) != VECTOR_TYPE) + return; + + if (code == NOP_EXPR + || code == FLOAT_EXPR + || code == FIX_TRUNC_EXPR + || code == VIEW_CONVERT_EXPR) + return; + + gcc_assert (code != CONVERT_EXPR); + + /* The signedness is determined from input argument. */ + if (code == VEC_UNPACK_FLOAT_HI_EXPR + || code == VEC_UNPACK_FLOAT_LO_EXPR) + type = TREE_TYPE (rhs1); + + /* Choose between vector shift/rotate by vector and vector shift/rotate by + scalar */ + if (code == LSHIFT_EXPR + || code == RSHIFT_EXPR + || code == LROTATE_EXPR + || code == RROTATE_EXPR) + { + /* If the 2nd argument is vector, we need a vector/vector shift */ + if (VECTOR_MODE_P (TYPE_MODE (TREE_TYPE (rhs2)))) + op = optab_for_tree_code (code, type, optab_vector); + else + { + /* Try for a vector/scalar shift, and if we don't have one, see if we + have a vector/vector shift */ + op = optab_for_tree_code (code, type, optab_scalar); + if (!op + || (op->handlers[(int) TYPE_MODE (type)].insn_code + == CODE_FOR_nothing)) + op = optab_for_tree_code (code, type, optab_vector); + } + } + else + op = optab_for_tree_code (code, type, optab_default); + + /* For widening/narrowing vector operations, the relevant type is of the + arguments, not the widened result. VEC_UNPACK_FLOAT_*_EXPR is + calculated in the same way above. */ + if (code == WIDEN_SUM_EXPR + || code == VEC_WIDEN_MULT_HI_EXPR + || code == VEC_WIDEN_MULT_LO_EXPR + || code == VEC_UNPACK_HI_EXPR + || code == VEC_UNPACK_LO_EXPR + || code == VEC_PACK_TRUNC_EXPR + || code == VEC_PACK_SAT_EXPR + || code == VEC_PACK_FIX_TRUNC_EXPR) + type = TREE_TYPE (rhs1); + + /* Optabs will try converting a negation into a subtraction, so + look for it as well. TODO: negation of floating-point vectors + might be turned into an exclusive OR toggling the sign bit. */ + if (op == NULL + && code == NEGATE_EXPR + && INTEGRAL_TYPE_P (TREE_TYPE (type))) + op = optab_for_tree_code (MINUS_EXPR, type, optab_default); + + /* For very wide vectors, try using a smaller vector mode. */ + compute_type = type; + if (TYPE_MODE (type) == BLKmode && op) + { + tree vector_compute_type + = type_for_widest_vector_mode (TYPE_MODE (TREE_TYPE (type)), op, + TYPE_SATURATING (TREE_TYPE (type))); + if (vector_compute_type != NULL_TREE + && (TYPE_VECTOR_SUBPARTS (vector_compute_type) + < TYPE_VECTOR_SUBPARTS (compute_type))) + compute_type = vector_compute_type; + } + + /* If we are breaking a BLKmode vector into smaller pieces, + type_for_widest_vector_mode has already looked into the optab, + so skip these checks. */ + if (compute_type == type) + { + compute_mode = TYPE_MODE (compute_type); + if ((GET_MODE_CLASS (compute_mode) == MODE_VECTOR_INT + || GET_MODE_CLASS (compute_mode) == MODE_VECTOR_FLOAT + || GET_MODE_CLASS (compute_mode) == MODE_VECTOR_FRACT + || GET_MODE_CLASS (compute_mode) == MODE_VECTOR_UFRACT + || GET_MODE_CLASS (compute_mode) == MODE_VECTOR_ACCUM + || GET_MODE_CLASS (compute_mode) == MODE_VECTOR_UACCUM) + && op != NULL + && optab_handler (op, compute_mode)->insn_code != CODE_FOR_nothing) + return; + else + /* There is no operation in hardware, so fall back to scalars. */ + compute_type = TREE_TYPE (type); + } + + gcc_assert (code != VEC_LSHIFT_EXPR && code != VEC_RSHIFT_EXPR); + new_rhs = expand_vector_operation (gsi, type, compute_type, stmt, code); + if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (new_rhs))) + new_rhs = gimplify_build1 (gsi, VIEW_CONVERT_EXPR, TREE_TYPE (lhs), + new_rhs); + + /* NOTE: We should avoid using gimple_assign_set_rhs_from_tree. One + way to do it is change expand_vector_operation and its callees to + return a tree_code, RHS1 and RHS2 instead of a tree. */ + gimple_assign_set_rhs_from_tree (gsi, new_rhs); + + gimple_set_modified (gsi_stmt (*gsi), true); +} + +/* Use this to lower vector operations introduced by the vectorizer, + if it may need the bit-twiddling tricks implemented in this file. */ + +static bool +gate_expand_vector_operations (void) +{ + return flag_tree_vectorize != 0; +} + +static unsigned int +expand_vector_operations (void) +{ + gimple_stmt_iterator gsi; + basic_block bb; + + FOR_EACH_BB (bb) + { + for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) + { + expand_vector_operations_1 (&gsi); + update_stmt_if_modified (gsi_stmt (gsi)); + } + } + return 0; +} + +struct gimple_opt_pass pass_lower_vector = +{ + { + GIMPLE_PASS, + "veclower", /* name */ + 0, /* gate */ + expand_vector_operations, /* execute */ + NULL, /* sub */ + NULL, /* next */ + 0, /* static_pass_number */ + 0, /* tv_id */ + PROP_cfg, /* properties_required */ + 0, /* properties_provided */ + 0, /* properties_destroyed */ + 0, /* todo_flags_start */ + TODO_dump_func | TODO_ggc_collect + | TODO_verify_stmts /* todo_flags_finish */ + } +}; + +struct gimple_opt_pass pass_lower_vector_ssa = +{ + { + GIMPLE_PASS, + "veclower2", /* name */ + gate_expand_vector_operations, /* gate */ + expand_vector_operations, /* execute */ + NULL, /* sub */ + NULL, /* next */ + 0, /* static_pass_number */ + 0, /* tv_id */ + PROP_cfg, /* properties_required */ + 0, /* properties_provided */ + 0, /* properties_destroyed */ + 0, /* todo_flags_start */ + TODO_dump_func | TODO_update_ssa /* todo_flags_finish */ + | TODO_verify_ssa + | TODO_verify_stmts | TODO_verify_flow + } +}; + +#include "gt-tree-vect-generic.h"