/* Lower vector operations to scalar operations. Copyright (C) 2004, 2005, 2006, 2007 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 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 "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 "tree-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) (block_stmt_iterator *, tree, tree, tree, tree, tree, enum tree_code); static inline tree tree_vec_extract (block_stmt_iterator *bsi, tree type, tree t, tree bitsize, tree bitpos) { if (bitpos) return gimplify_build3 (bsi, BIT_FIELD_REF, type, t, bitsize, bitpos); else return gimplify_build1 (bsi, VIEW_CONVERT_EXPR, type, t); } static tree do_unop (block_stmt_iterator *bsi, tree inner_type, tree a, tree b ATTRIBUTE_UNUSED, tree bitpos, tree bitsize, enum tree_code code) { a = tree_vec_extract (bsi, inner_type, a, bitsize, bitpos); return gimplify_build1 (bsi, code, inner_type, a); } static tree do_binop (block_stmt_iterator *bsi, tree inner_type, tree a, tree b, tree bitpos, tree bitsize, enum tree_code code) { a = tree_vec_extract (bsi, inner_type, a, bitsize, bitpos); b = tree_vec_extract (bsi, inner_type, b, bitsize, bitpos); return gimplify_build2 (bsi, 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 (block_stmt_iterator *bsi, 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 (bsi, word_type, a, bitsize, bitpos); b = tree_vec_extract (bsi, word_type, b, bitsize, bitpos); signs = gimplify_build2 (bsi, BIT_XOR_EXPR, word_type, a, b); b_low = gimplify_build2 (bsi, BIT_AND_EXPR, word_type, b, low_bits); if (code == PLUS_EXPR) a_low = gimplify_build2 (bsi, BIT_AND_EXPR, word_type, a, low_bits); else { a_low = gimplify_build2 (bsi, BIT_IOR_EXPR, word_type, a, high_bits); signs = gimplify_build1 (bsi, BIT_NOT_EXPR, word_type, signs); } signs = gimplify_build2 (bsi, BIT_AND_EXPR, word_type, signs, high_bits); result_low = gimplify_build2 (bsi, code, word_type, a_low, b_low); return gimplify_build2 (bsi, BIT_XOR_EXPR, word_type, result_low, signs); } static tree do_negate (block_stmt_iterator *bsi, 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 (bsi, word_type, b, bitsize, bitpos); b_low = gimplify_build2 (bsi, BIT_AND_EXPR, word_type, b, low_bits); signs = gimplify_build1 (bsi, BIT_NOT_EXPR, word_type, b); signs = gimplify_build2 (bsi, BIT_AND_EXPR, word_type, signs, high_bits); result_low = gimplify_build2 (bsi, MINUS_EXPR, word_type, high_bits, b_low); return gimplify_build2 (bsi, 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 (block_stmt_iterator *bsi, 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 (bsi, 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 (block_stmt_iterator *bsi, 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 (bsi, 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 (bsi, f, word_type, TREE_TYPE (word_type), a, b, code); result = gimplify_val (bsi, word_type, result); } 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 (bsi, 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 (block_stmt_iterator *bsi, 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 (bsi, f_parallel, type, a, b, code); else return expand_vector_piecewise (bsi, f, type, TREE_TYPE (type), a, b, code); } static tree expand_vector_operation (block_stmt_iterator *bsi, tree type, tree compute_type, tree rhs, 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) switch (code) { case PLUS_EXPR: case MINUS_EXPR: if (!TYPE_OVERFLOW_TRAPS (type)) return expand_vector_addition (bsi, do_binop, do_plus_minus, type, TREE_OPERAND (rhs, 0), TREE_OPERAND (rhs, 1), code); break; case NEGATE_EXPR: if (!TYPE_OVERFLOW_TRAPS (type)) return expand_vector_addition (bsi, do_unop, do_negate, type, TREE_OPERAND (rhs, 0), NULL_TREE, code); break; case BIT_AND_EXPR: case BIT_IOR_EXPR: case BIT_XOR_EXPR: return expand_vector_parallel (bsi, do_binop, type, TREE_OPERAND (rhs, 0), TREE_OPERAND (rhs, 1), code); case BIT_NOT_EXPR: return expand_vector_parallel (bsi, do_unop, type, TREE_OPERAND (rhs, 0), NULL_TREE, code); default: break; } if (TREE_CODE_CLASS (code) == tcc_unary) return expand_vector_piecewise (bsi, do_unop, type, compute_type, TREE_OPERAND (rhs, 0), NULL_TREE, code); else return expand_vector_piecewise (bsi, do_binop, type, compute_type, TREE_OPERAND (rhs, 0), TREE_OPERAND (rhs, 1), code); } /* Return a type for the widest vector mode whose components are of mode INNER_MODE, or NULL_TREE if none is found. */ static tree type_for_widest_vector_mode (enum machine_mode inner_mode, optab op) { enum machine_mode best_mode = VOIDmode, mode; int best_nunits = 0; if (SCALAR_FLOAT_MODE_P (inner_mode)) mode = MIN_MODE_VECTOR_FLOAT; 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 && op->handlers[mode].insn_code != CODE_FOR_nothing) best_mode = mode, best_nunits = GET_MODE_NUNITS (mode); if (best_mode == VOIDmode) return NULL_TREE; else 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 (block_stmt_iterator *bsi) { tree stmt = bsi_stmt (*bsi); tree *p_lhs, *p_rhs, lhs, rhs, type, compute_type; enum tree_code code; enum machine_mode compute_mode; optab op; switch (TREE_CODE (stmt)) { case RETURN_EXPR: stmt = TREE_OPERAND (stmt, 0); if (!stmt || TREE_CODE (stmt) != MODIFY_EXPR) return; /* FALLTHRU */ case MODIFY_EXPR: p_lhs = &TREE_OPERAND (stmt, 0); p_rhs = &TREE_OPERAND (stmt, 1); lhs = *p_lhs; rhs = *p_rhs; break; default: return; } type = TREE_TYPE (rhs); if (TREE_CODE (type) != VECTOR_TYPE) return; code = TREE_CODE (rhs); if (TREE_CODE_CLASS (code) != tcc_unary && TREE_CODE_CLASS (code) != tcc_binary) return; if (code == NOP_EXPR || code == VIEW_CONVERT_EXPR) return; gcc_assert (code != CONVERT_EXPR); op = optab_for_tree_code (code, type); /* For widening vector operations, the relevant type is of the arguments, not the widened result. */ if (code == WIDEN_SUM_EXPR) type = TREE_TYPE (TREE_OPERAND (rhs, 0)); /* 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); /* 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); if (vector_compute_type != NULL_TREE) 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) && op != NULL && op->handlers[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); rhs = expand_vector_operation (bsi, type, compute_type, rhs, code); if (lang_hooks.types_compatible_p (TREE_TYPE (lhs), TREE_TYPE (rhs))) *p_rhs = rhs; else *p_rhs = gimplify_build1 (bsi, VIEW_CONVERT_EXPR, TREE_TYPE (lhs), rhs); mark_stmt_modified (bsi_stmt (*bsi)); } /* 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) { block_stmt_iterator bsi; basic_block bb; FOR_EACH_BB (bb) { for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) { expand_vector_operations_1 (&bsi); update_stmt_if_modified (bsi_stmt (bsi)); } } return 0; } struct tree_opt_pass pass_lower_vector = { "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 */ 0 /* letter */ }; struct tree_opt_pass pass_lower_vector_ssa = { "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, 0 /* letter */ }; #include "gt-tree-vect-generic.h"