| /* SLP - Basic Block Vectorization |
| Copyright (C) 2007-2021 Free Software Foundation, Inc. |
| Contributed by Dorit Naishlos <dorit@il.ibm.com> |
| and Ira Rosen <irar@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 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 |
| <http://www.gnu.org/licenses/>. */ |
| |
| #include "config.h" |
| #include "system.h" |
| #include "coretypes.h" |
| #include "backend.h" |
| #include "target.h" |
| #include "rtl.h" |
| #include "tree.h" |
| #include "gimple.h" |
| #include "tree-pass.h" |
| #include "ssa.h" |
| #include "optabs-tree.h" |
| #include "insn-config.h" |
| #include "recog.h" /* FIXME: for insn_data */ |
| #include "fold-const.h" |
| #include "stor-layout.h" |
| #include "gimple-iterator.h" |
| #include "cfgloop.h" |
| #include "tree-vectorizer.h" |
| #include "langhooks.h" |
| #include "gimple-walk.h" |
| #include "dbgcnt.h" |
| #include "tree-vector-builder.h" |
| #include "vec-perm-indices.h" |
| #include "gimple-fold.h" |
| #include "internal-fn.h" |
| #include "dump-context.h" |
| #include "cfganal.h" |
| #include "tree-eh.h" |
| #include "tree-cfg.h" |
| #include "alloc-pool.h" |
| |
| static bool vectorizable_slp_permutation (vec_info *, gimple_stmt_iterator *, |
| slp_tree, stmt_vector_for_cost *); |
| static void vect_print_slp_tree (dump_flags_t, dump_location_t, slp_tree); |
| |
| static object_allocator<_slp_tree> *slp_tree_pool; |
| static slp_tree slp_first_node; |
| |
| void |
| vect_slp_init (void) |
| { |
| slp_tree_pool = new object_allocator<_slp_tree> ("SLP nodes"); |
| } |
| |
| void |
| vect_slp_fini (void) |
| { |
| while (slp_first_node) |
| delete slp_first_node; |
| delete slp_tree_pool; |
| slp_tree_pool = NULL; |
| } |
| |
| void * |
| _slp_tree::operator new (size_t n) |
| { |
| gcc_assert (n == sizeof (_slp_tree)); |
| return slp_tree_pool->allocate_raw (); |
| } |
| |
| void |
| _slp_tree::operator delete (void *node, size_t n) |
| { |
| gcc_assert (n == sizeof (_slp_tree)); |
| slp_tree_pool->remove_raw (node); |
| } |
| |
| |
| /* Initialize a SLP node. */ |
| |
| _slp_tree::_slp_tree () |
| { |
| this->prev_node = NULL; |
| if (slp_first_node) |
| slp_first_node->prev_node = this; |
| this->next_node = slp_first_node; |
| slp_first_node = this; |
| SLP_TREE_SCALAR_STMTS (this) = vNULL; |
| SLP_TREE_SCALAR_OPS (this) = vNULL; |
| SLP_TREE_VEC_STMTS (this) = vNULL; |
| SLP_TREE_VEC_DEFS (this) = vNULL; |
| SLP_TREE_NUMBER_OF_VEC_STMTS (this) = 0; |
| SLP_TREE_CHILDREN (this) = vNULL; |
| SLP_TREE_LOAD_PERMUTATION (this) = vNULL; |
| SLP_TREE_LANE_PERMUTATION (this) = vNULL; |
| SLP_TREE_DEF_TYPE (this) = vect_uninitialized_def; |
| SLP_TREE_CODE (this) = ERROR_MARK; |
| SLP_TREE_VECTYPE (this) = NULL_TREE; |
| SLP_TREE_REPRESENTATIVE (this) = NULL; |
| SLP_TREE_REF_COUNT (this) = 1; |
| this->failed = NULL; |
| this->max_nunits = 1; |
| this->lanes = 0; |
| } |
| |
| /* Tear down a SLP node. */ |
| |
| _slp_tree::~_slp_tree () |
| { |
| if (this->prev_node) |
| this->prev_node->next_node = this->next_node; |
| else |
| slp_first_node = this->next_node; |
| if (this->next_node) |
| this->next_node->prev_node = this->prev_node; |
| SLP_TREE_CHILDREN (this).release (); |
| SLP_TREE_SCALAR_STMTS (this).release (); |
| SLP_TREE_SCALAR_OPS (this).release (); |
| SLP_TREE_VEC_STMTS (this).release (); |
| SLP_TREE_VEC_DEFS (this).release (); |
| SLP_TREE_LOAD_PERMUTATION (this).release (); |
| SLP_TREE_LANE_PERMUTATION (this).release (); |
| if (this->failed) |
| free (failed); |
| } |
| |
| /* Recursively free the memory allocated for the SLP tree rooted at NODE. */ |
| |
| void |
| vect_free_slp_tree (slp_tree node) |
| { |
| int i; |
| slp_tree child; |
| |
| if (--SLP_TREE_REF_COUNT (node) != 0) |
| return; |
| |
| FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node), i, child) |
| if (child) |
| vect_free_slp_tree (child); |
| |
| /* If the node defines any SLP only patterns then those patterns are no |
| longer valid and should be removed. */ |
| stmt_vec_info rep_stmt_info = SLP_TREE_REPRESENTATIVE (node); |
| if (rep_stmt_info && STMT_VINFO_SLP_VECT_ONLY_PATTERN (rep_stmt_info)) |
| { |
| stmt_vec_info stmt_info = vect_orig_stmt (rep_stmt_info); |
| STMT_VINFO_IN_PATTERN_P (stmt_info) = false; |
| STMT_SLP_TYPE (stmt_info) = STMT_SLP_TYPE (rep_stmt_info); |
| } |
| |
| delete node; |
| } |
| |
| /* Return a location suitable for dumpings related to the SLP instance. */ |
| |
| dump_user_location_t |
| _slp_instance::location () const |
| { |
| if (!root_stmts.is_empty ()) |
| return root_stmts[0]->stmt; |
| else |
| return SLP_TREE_SCALAR_STMTS (root)[0]->stmt; |
| } |
| |
| |
| /* Free the memory allocated for the SLP instance. */ |
| |
| void |
| vect_free_slp_instance (slp_instance instance) |
| { |
| vect_free_slp_tree (SLP_INSTANCE_TREE (instance)); |
| SLP_INSTANCE_LOADS (instance).release (); |
| SLP_INSTANCE_ROOT_STMTS (instance).release (); |
| instance->subgraph_entries.release (); |
| instance->cost_vec.release (); |
| free (instance); |
| } |
| |
| |
| /* Create an SLP node for SCALAR_STMTS. */ |
| |
| slp_tree |
| vect_create_new_slp_node (unsigned nops, tree_code code) |
| { |
| slp_tree node = new _slp_tree; |
| SLP_TREE_SCALAR_STMTS (node) = vNULL; |
| SLP_TREE_CHILDREN (node).create (nops); |
| SLP_TREE_DEF_TYPE (node) = vect_internal_def; |
| SLP_TREE_CODE (node) = code; |
| return node; |
| } |
| /* Create an SLP node for SCALAR_STMTS. */ |
| |
| static slp_tree |
| vect_create_new_slp_node (slp_tree node, |
| vec<stmt_vec_info> scalar_stmts, unsigned nops) |
| { |
| SLP_TREE_SCALAR_STMTS (node) = scalar_stmts; |
| SLP_TREE_CHILDREN (node).create (nops); |
| SLP_TREE_DEF_TYPE (node) = vect_internal_def; |
| SLP_TREE_REPRESENTATIVE (node) = scalar_stmts[0]; |
| SLP_TREE_LANES (node) = scalar_stmts.length (); |
| return node; |
| } |
| |
| /* Create an SLP node for SCALAR_STMTS. */ |
| |
| static slp_tree |
| vect_create_new_slp_node (vec<stmt_vec_info> scalar_stmts, unsigned nops) |
| { |
| return vect_create_new_slp_node (new _slp_tree, scalar_stmts, nops); |
| } |
| |
| /* Create an SLP node for OPS. */ |
| |
| static slp_tree |
| vect_create_new_slp_node (slp_tree node, vec<tree> ops) |
| { |
| SLP_TREE_SCALAR_OPS (node) = ops; |
| SLP_TREE_DEF_TYPE (node) = vect_external_def; |
| SLP_TREE_LANES (node) = ops.length (); |
| return node; |
| } |
| |
| /* Create an SLP node for OPS. */ |
| |
| static slp_tree |
| vect_create_new_slp_node (vec<tree> ops) |
| { |
| return vect_create_new_slp_node (new _slp_tree, ops); |
| } |
| |
| |
| /* This structure is used in creation of an SLP tree. Each instance |
| corresponds to the same operand in a group of scalar stmts in an SLP |
| node. */ |
| typedef struct _slp_oprnd_info |
| { |
| /* Def-stmts for the operands. */ |
| vec<stmt_vec_info> def_stmts; |
| /* Operands. */ |
| vec<tree> ops; |
| /* Information about the first statement, its vector def-type, type, the |
| operand itself in case it's constant, and an indication if it's a pattern |
| stmt. */ |
| tree first_op_type; |
| enum vect_def_type first_dt; |
| bool any_pattern; |
| } *slp_oprnd_info; |
| |
| |
| /* Allocate operands info for NOPS operands, and GROUP_SIZE def-stmts for each |
| operand. */ |
| static vec<slp_oprnd_info> |
| vect_create_oprnd_info (int nops, int group_size) |
| { |
| int i; |
| slp_oprnd_info oprnd_info; |
| vec<slp_oprnd_info> oprnds_info; |
| |
| oprnds_info.create (nops); |
| for (i = 0; i < nops; i++) |
| { |
| oprnd_info = XNEW (struct _slp_oprnd_info); |
| oprnd_info->def_stmts.create (group_size); |
| oprnd_info->ops.create (group_size); |
| oprnd_info->first_dt = vect_uninitialized_def; |
| oprnd_info->first_op_type = NULL_TREE; |
| oprnd_info->any_pattern = false; |
| oprnds_info.quick_push (oprnd_info); |
| } |
| |
| return oprnds_info; |
| } |
| |
| |
| /* Free operands info. */ |
| |
| static void |
| vect_free_oprnd_info (vec<slp_oprnd_info> &oprnds_info) |
| { |
| int i; |
| slp_oprnd_info oprnd_info; |
| |
| FOR_EACH_VEC_ELT (oprnds_info, i, oprnd_info) |
| { |
| oprnd_info->def_stmts.release (); |
| oprnd_info->ops.release (); |
| XDELETE (oprnd_info); |
| } |
| |
| oprnds_info.release (); |
| } |
| |
| |
| /* Return true if STMTS contains a pattern statement. */ |
| |
| static bool |
| vect_contains_pattern_stmt_p (vec<stmt_vec_info> stmts) |
| { |
| stmt_vec_info stmt_info; |
| unsigned int i; |
| FOR_EACH_VEC_ELT (stmts, i, stmt_info) |
| if (is_pattern_stmt_p (stmt_info)) |
| return true; |
| return false; |
| } |
| |
| /* Return true when all lanes in the external or constant NODE have |
| the same value. */ |
| |
| static bool |
| vect_slp_tree_uniform_p (slp_tree node) |
| { |
| gcc_assert (SLP_TREE_DEF_TYPE (node) == vect_constant_def |
| || SLP_TREE_DEF_TYPE (node) == vect_external_def); |
| |
| /* Pre-exsting vectors. */ |
| if (SLP_TREE_SCALAR_OPS (node).is_empty ()) |
| return false; |
| |
| unsigned i; |
| tree op, first = NULL_TREE; |
| FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_OPS (node), i, op) |
| if (!first) |
| first = op; |
| else if (!operand_equal_p (first, op, 0)) |
| return false; |
| |
| return true; |
| } |
| |
| /* Find the place of the data-ref in STMT_INFO in the interleaving chain |
| that starts from FIRST_STMT_INFO. Return -1 if the data-ref is not a part |
| of the chain. */ |
| |
| int |
| vect_get_place_in_interleaving_chain (stmt_vec_info stmt_info, |
| stmt_vec_info first_stmt_info) |
| { |
| stmt_vec_info next_stmt_info = first_stmt_info; |
| int result = 0; |
| |
| if (first_stmt_info != DR_GROUP_FIRST_ELEMENT (stmt_info)) |
| return -1; |
| |
| do |
| { |
| if (next_stmt_info == stmt_info) |
| return result; |
| next_stmt_info = DR_GROUP_NEXT_ELEMENT (next_stmt_info); |
| if (next_stmt_info) |
| result += DR_GROUP_GAP (next_stmt_info); |
| } |
| while (next_stmt_info); |
| |
| return -1; |
| } |
| |
| /* Check whether it is possible to load COUNT elements of type ELT_TYPE |
| using the method implemented by duplicate_and_interleave. Return true |
| if so, returning the number of intermediate vectors in *NVECTORS_OUT |
| (if nonnull) and the type of each intermediate vector in *VECTOR_TYPE_OUT |
| (if nonnull). */ |
| |
| bool |
| can_duplicate_and_interleave_p (vec_info *vinfo, unsigned int count, |
| tree elt_type, unsigned int *nvectors_out, |
| tree *vector_type_out, |
| tree *permutes) |
| { |
| tree base_vector_type = get_vectype_for_scalar_type (vinfo, elt_type, count); |
| if (!base_vector_type || !VECTOR_MODE_P (TYPE_MODE (base_vector_type))) |
| return false; |
| |
| machine_mode base_vector_mode = TYPE_MODE (base_vector_type); |
| poly_int64 elt_bytes = count * GET_MODE_UNIT_SIZE (base_vector_mode); |
| unsigned int nvectors = 1; |
| for (;;) |
| { |
| scalar_int_mode int_mode; |
| poly_int64 elt_bits = elt_bytes * BITS_PER_UNIT; |
| if (int_mode_for_size (elt_bits, 1).exists (&int_mode)) |
| { |
| /* Get the natural vector type for this SLP group size. */ |
| tree int_type = build_nonstandard_integer_type |
| (GET_MODE_BITSIZE (int_mode), 1); |
| tree vector_type |
| = get_vectype_for_scalar_type (vinfo, int_type, count); |
| if (vector_type |
| && VECTOR_MODE_P (TYPE_MODE (vector_type)) |
| && known_eq (GET_MODE_SIZE (TYPE_MODE (vector_type)), |
| GET_MODE_SIZE (base_vector_mode))) |
| { |
| /* Try fusing consecutive sequences of COUNT / NVECTORS elements |
| together into elements of type INT_TYPE and using the result |
| to build NVECTORS vectors. */ |
| poly_uint64 nelts = GET_MODE_NUNITS (TYPE_MODE (vector_type)); |
| vec_perm_builder sel1 (nelts, 2, 3); |
| vec_perm_builder sel2 (nelts, 2, 3); |
| poly_int64 half_nelts = exact_div (nelts, 2); |
| for (unsigned int i = 0; i < 3; ++i) |
| { |
| sel1.quick_push (i); |
| sel1.quick_push (i + nelts); |
| sel2.quick_push (half_nelts + i); |
| sel2.quick_push (half_nelts + i + nelts); |
| } |
| vec_perm_indices indices1 (sel1, 2, nelts); |
| vec_perm_indices indices2 (sel2, 2, nelts); |
| if (can_vec_perm_const_p (TYPE_MODE (vector_type), indices1) |
| && can_vec_perm_const_p (TYPE_MODE (vector_type), indices2)) |
| { |
| if (nvectors_out) |
| *nvectors_out = nvectors; |
| if (vector_type_out) |
| *vector_type_out = vector_type; |
| if (permutes) |
| { |
| permutes[0] = vect_gen_perm_mask_checked (vector_type, |
| indices1); |
| permutes[1] = vect_gen_perm_mask_checked (vector_type, |
| indices2); |
| } |
| return true; |
| } |
| } |
| } |
| if (!multiple_p (elt_bytes, 2, &elt_bytes)) |
| return false; |
| nvectors *= 2; |
| } |
| } |
| |
| /* Return true if DTA and DTB match. */ |
| |
| static bool |
| vect_def_types_match (enum vect_def_type dta, enum vect_def_type dtb) |
| { |
| return (dta == dtb |
| || ((dta == vect_external_def || dta == vect_constant_def) |
| && (dtb == vect_external_def || dtb == vect_constant_def))); |
| } |
| |
| /* Get the defs for the rhs of STMT (collect them in OPRNDS_INFO), check that |
| they are of a valid type and that they match the defs of the first stmt of |
| the SLP group (stored in OPRNDS_INFO). This function tries to match stmts |
| by swapping operands of STMTS[STMT_NUM] when possible. Non-zero *SWAP |
| indicates swap is required for cond_expr stmts. Specifically, *SWAP |
| is 1 if STMT is cond and operands of comparison need to be swapped; |
| *SWAP is 2 if STMT is cond and code of comparison needs to be inverted. |
| If there is any operand swap in this function, *SWAP is set to non-zero |
| value. |
| If there was a fatal error return -1; if the error could be corrected by |
| swapping operands of father node of this one, return 1; if everything is |
| ok return 0. */ |
| static int |
| vect_get_and_check_slp_defs (vec_info *vinfo, unsigned char swap, |
| bool *skip_args, |
| vec<stmt_vec_info> stmts, unsigned stmt_num, |
| vec<slp_oprnd_info> *oprnds_info) |
| { |
| stmt_vec_info stmt_info = stmts[stmt_num]; |
| tree oprnd; |
| unsigned int i, number_of_oprnds; |
| enum vect_def_type dt = vect_uninitialized_def; |
| slp_oprnd_info oprnd_info; |
| int first_op_idx = 1; |
| unsigned int commutative_op = -1U; |
| bool first_op_cond = false; |
| bool first = stmt_num == 0; |
| |
| if (gcall *stmt = dyn_cast <gcall *> (stmt_info->stmt)) |
| { |
| number_of_oprnds = gimple_call_num_args (stmt); |
| first_op_idx = 3; |
| if (gimple_call_internal_p (stmt)) |
| { |
| internal_fn ifn = gimple_call_internal_fn (stmt); |
| commutative_op = first_commutative_argument (ifn); |
| |
| /* Masked load, only look at mask. */ |
| if (ifn == IFN_MASK_LOAD) |
| { |
| number_of_oprnds = 1; |
| /* Mask operand index. */ |
| first_op_idx = 5; |
| } |
| } |
| } |
| else if (gassign *stmt = dyn_cast <gassign *> (stmt_info->stmt)) |
| { |
| enum tree_code code = gimple_assign_rhs_code (stmt); |
| number_of_oprnds = gimple_num_ops (stmt) - 1; |
| /* Swap can only be done for cond_expr if asked to, otherwise we |
| could result in different comparison code to the first stmt. */ |
| if (code == COND_EXPR |
| && COMPARISON_CLASS_P (gimple_assign_rhs1 (stmt))) |
| { |
| first_op_cond = true; |
| number_of_oprnds++; |
| } |
| else |
| commutative_op = commutative_tree_code (code) ? 0U : -1U; |
| } |
| else if (gphi *stmt = dyn_cast <gphi *> (stmt_info->stmt)) |
| number_of_oprnds = gimple_phi_num_args (stmt); |
| else |
| return -1; |
| |
| bool swapped = (swap != 0); |
| bool backedge = false; |
| gcc_assert (!swapped || first_op_cond); |
| enum vect_def_type *dts = XALLOCAVEC (enum vect_def_type, number_of_oprnds); |
| for (i = 0; i < number_of_oprnds; i++) |
| { |
| if (first_op_cond) |
| { |
| /* Map indicating how operands of cond_expr should be swapped. */ |
| int maps[3][4] = {{0, 1, 2, 3}, {1, 0, 2, 3}, {0, 1, 3, 2}}; |
| int *map = maps[swap]; |
| |
| if (i < 2) |
| oprnd = TREE_OPERAND (gimple_op (stmt_info->stmt, |
| first_op_idx), map[i]); |
| else |
| oprnd = gimple_op (stmt_info->stmt, map[i]); |
| } |
| else if (gphi *stmt = dyn_cast <gphi *> (stmt_info->stmt)) |
| { |
| oprnd = gimple_phi_arg_def (stmt, i); |
| backedge = dominated_by_p (CDI_DOMINATORS, |
| gimple_phi_arg_edge (stmt, i)->src, |
| gimple_bb (stmt_info->stmt)); |
| } |
| else |
| oprnd = gimple_op (stmt_info->stmt, first_op_idx + (swapped ? !i : i)); |
| if (TREE_CODE (oprnd) == VIEW_CONVERT_EXPR) |
| oprnd = TREE_OPERAND (oprnd, 0); |
| |
| oprnd_info = (*oprnds_info)[i]; |
| |
| stmt_vec_info def_stmt_info; |
| if (!vect_is_simple_use (oprnd, vinfo, &dts[i], &def_stmt_info)) |
| { |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, |
| "Build SLP failed: can't analyze def for %T\n", |
| oprnd); |
| |
| return -1; |
| } |
| |
| if (skip_args[i]) |
| { |
| oprnd_info->def_stmts.quick_push (NULL); |
| oprnd_info->ops.quick_push (NULL_TREE); |
| oprnd_info->first_dt = vect_uninitialized_def; |
| continue; |
| } |
| |
| oprnd_info->def_stmts.quick_push (def_stmt_info); |
| oprnd_info->ops.quick_push (oprnd); |
| |
| if (def_stmt_info |
| && is_pattern_stmt_p (def_stmt_info)) |
| { |
| if (STMT_VINFO_RELATED_STMT (vect_orig_stmt (def_stmt_info)) |
| != def_stmt_info) |
| oprnd_info->any_pattern = true; |
| else |
| /* If we promote this to external use the original stmt def. */ |
| oprnd_info->ops.last () |
| = gimple_get_lhs (vect_orig_stmt (def_stmt_info)->stmt); |
| } |
| |
| /* If there's a extern def on a backedge make sure we can |
| code-generate at the region start. |
| ??? This is another case that could be fixed by adjusting |
| how we split the function but at the moment we'd have conflicting |
| goals there. */ |
| if (backedge |
| && dts[i] == vect_external_def |
| && is_a <bb_vec_info> (vinfo) |
| && TREE_CODE (oprnd) == SSA_NAME |
| && !SSA_NAME_IS_DEFAULT_DEF (oprnd) |
| && !dominated_by_p (CDI_DOMINATORS, |
| as_a <bb_vec_info> (vinfo)->bbs[0], |
| gimple_bb (SSA_NAME_DEF_STMT (oprnd)))) |
| { |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, |
| "Build SLP failed: extern def %T only defined " |
| "on backedge\n", oprnd); |
| return -1; |
| } |
| |
| if (first) |
| { |
| tree type = TREE_TYPE (oprnd); |
| dt = dts[i]; |
| if ((dt == vect_constant_def |
| || dt == vect_external_def) |
| && !GET_MODE_SIZE (vinfo->vector_mode).is_constant () |
| && (TREE_CODE (type) == BOOLEAN_TYPE |
| || !can_duplicate_and_interleave_p (vinfo, stmts.length (), |
| type))) |
| { |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, |
| "Build SLP failed: invalid type of def " |
| "for variable-length SLP %T\n", oprnd); |
| return -1; |
| } |
| |
| /* For the swapping logic below force vect_reduction_def |
| for the reduction op in a SLP reduction group. */ |
| if (!STMT_VINFO_DATA_REF (stmt_info) |
| && REDUC_GROUP_FIRST_ELEMENT (stmt_info) |
| && (int)i == STMT_VINFO_REDUC_IDX (stmt_info) |
| && def_stmt_info) |
| dts[i] = dt = vect_reduction_def; |
| |
| /* Check the types of the definition. */ |
| switch (dt) |
| { |
| case vect_external_def: |
| case vect_constant_def: |
| case vect_internal_def: |
| case vect_reduction_def: |
| case vect_induction_def: |
| case vect_nested_cycle: |
| break; |
| |
| default: |
| /* FORNOW: Not supported. */ |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, |
| "Build SLP failed: illegal type of def %T\n", |
| oprnd); |
| return -1; |
| } |
| |
| oprnd_info->first_dt = dt; |
| oprnd_info->first_op_type = type; |
| } |
| } |
| if (first) |
| return 0; |
| |
| /* Now match the operand definition types to that of the first stmt. */ |
| for (i = 0; i < number_of_oprnds;) |
| { |
| if (skip_args[i]) |
| { |
| ++i; |
| continue; |
| } |
| |
| oprnd_info = (*oprnds_info)[i]; |
| dt = dts[i]; |
| stmt_vec_info def_stmt_info = oprnd_info->def_stmts[stmt_num]; |
| oprnd = oprnd_info->ops[stmt_num]; |
| tree type = TREE_TYPE (oprnd); |
| |
| if (!types_compatible_p (oprnd_info->first_op_type, type)) |
| { |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, |
| "Build SLP failed: different operand types\n"); |
| return 1; |
| } |
| |
| /* Not first stmt of the group, check that the def-stmt/s match |
| the def-stmt/s of the first stmt. Allow different definition |
| types for reduction chains: the first stmt must be a |
| vect_reduction_def (a phi node), and the rest |
| end in the reduction chain. */ |
| if ((!vect_def_types_match (oprnd_info->first_dt, dt) |
| && !(oprnd_info->first_dt == vect_reduction_def |
| && !STMT_VINFO_DATA_REF (stmt_info) |
| && REDUC_GROUP_FIRST_ELEMENT (stmt_info) |
| && def_stmt_info |
| && !STMT_VINFO_DATA_REF (def_stmt_info) |
| && (REDUC_GROUP_FIRST_ELEMENT (def_stmt_info) |
| == REDUC_GROUP_FIRST_ELEMENT (stmt_info)))) |
| || (!STMT_VINFO_DATA_REF (stmt_info) |
| && REDUC_GROUP_FIRST_ELEMENT (stmt_info) |
| && ((!def_stmt_info |
| || STMT_VINFO_DATA_REF (def_stmt_info) |
| || (REDUC_GROUP_FIRST_ELEMENT (def_stmt_info) |
| != REDUC_GROUP_FIRST_ELEMENT (stmt_info))) |
| != (oprnd_info->first_dt != vect_reduction_def)))) |
| { |
| /* Try swapping operands if we got a mismatch. For BB |
| vectorization only in case it will clearly improve things. */ |
| if (i == commutative_op && !swapped |
| && (!is_a <bb_vec_info> (vinfo) |
| || (!vect_def_types_match ((*oprnds_info)[i+1]->first_dt, |
| dts[i+1]) |
| && (vect_def_types_match (oprnd_info->first_dt, dts[i+1]) |
| || vect_def_types_match |
| ((*oprnds_info)[i+1]->first_dt, dts[i]))))) |
| { |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_NOTE, vect_location, |
| "trying swapped operands\n"); |
| std::swap (dts[i], dts[i+1]); |
| std::swap ((*oprnds_info)[i]->def_stmts[stmt_num], |
| (*oprnds_info)[i+1]->def_stmts[stmt_num]); |
| std::swap ((*oprnds_info)[i]->ops[stmt_num], |
| (*oprnds_info)[i+1]->ops[stmt_num]); |
| swapped = true; |
| continue; |
| } |
| |
| if (is_a <bb_vec_info> (vinfo) |
| && !oprnd_info->any_pattern) |
| { |
| /* Now for commutative ops we should see whether we can |
| make the other operand matching. */ |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, |
| "treating operand as external\n"); |
| oprnd_info->first_dt = dt = vect_external_def; |
| } |
| else |
| { |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, |
| "Build SLP failed: different types\n"); |
| return 1; |
| } |
| } |
| |
| /* Make sure to demote the overall operand to external. */ |
| if (dt == vect_external_def) |
| oprnd_info->first_dt = vect_external_def; |
| /* For a SLP reduction chain we want to duplicate the reduction to |
| each of the chain members. That gets us a sane SLP graph (still |
| the stmts are not 100% correct wrt the initial values). */ |
| else if ((dt == vect_internal_def |
| || dt == vect_reduction_def) |
| && oprnd_info->first_dt == vect_reduction_def |
| && !STMT_VINFO_DATA_REF (stmt_info) |
| && REDUC_GROUP_FIRST_ELEMENT (stmt_info) |
| && !STMT_VINFO_DATA_REF (def_stmt_info) |
| && (REDUC_GROUP_FIRST_ELEMENT (def_stmt_info) |
| == REDUC_GROUP_FIRST_ELEMENT (stmt_info))) |
| { |
| oprnd_info->def_stmts[stmt_num] = oprnd_info->def_stmts[0]; |
| oprnd_info->ops[stmt_num] = oprnd_info->ops[0]; |
| } |
| |
| ++i; |
| } |
| |
| /* Swap operands. */ |
| if (swapped) |
| { |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_NOTE, vect_location, |
| "swapped operands to match def types in %G", |
| stmt_info->stmt); |
| } |
| |
| return 0; |
| } |
| |
| /* Return true if call statements CALL1 and CALL2 are similar enough |
| to be combined into the same SLP group. */ |
| |
| static bool |
| compatible_calls_p (gcall *call1, gcall *call2) |
| { |
| unsigned int nargs = gimple_call_num_args (call1); |
| if (nargs != gimple_call_num_args (call2)) |
| return false; |
| |
| if (gimple_call_combined_fn (call1) != gimple_call_combined_fn (call2)) |
| return false; |
| |
| if (gimple_call_internal_p (call1)) |
| { |
| if (!types_compatible_p (TREE_TYPE (gimple_call_lhs (call1)), |
| TREE_TYPE (gimple_call_lhs (call2)))) |
| return false; |
| for (unsigned int i = 0; i < nargs; ++i) |
| if (!types_compatible_p (TREE_TYPE (gimple_call_arg (call1, i)), |
| TREE_TYPE (gimple_call_arg (call2, i)))) |
| return false; |
| } |
| else |
| { |
| if (!operand_equal_p (gimple_call_fn (call1), |
| gimple_call_fn (call2), 0)) |
| return false; |
| |
| if (gimple_call_fntype (call1) != gimple_call_fntype (call2)) |
| return false; |
| } |
| return true; |
| } |
| |
| /* A subroutine of vect_build_slp_tree for checking VECTYPE, which is the |
| caller's attempt to find the vector type in STMT_INFO with the narrowest |
| element type. Return true if VECTYPE is nonnull and if it is valid |
| for STMT_INFO. When returning true, update MAX_NUNITS to reflect the |
| number of units in VECTYPE. GROUP_SIZE and MAX_NUNITS are as for |
| vect_build_slp_tree. */ |
| |
| static bool |
| vect_record_max_nunits (vec_info *vinfo, stmt_vec_info stmt_info, |
| unsigned int group_size, |
| tree vectype, poly_uint64 *max_nunits) |
| { |
| if (!vectype) |
| { |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, |
| "Build SLP failed: unsupported data-type in %G\n", |
| stmt_info->stmt); |
| /* Fatal mismatch. */ |
| return false; |
| } |
| |
| /* If populating the vector type requires unrolling then fail |
| before adjusting *max_nunits for basic-block vectorization. */ |
| if (is_a <bb_vec_info> (vinfo) |
| && !multiple_p (group_size, TYPE_VECTOR_SUBPARTS (vectype))) |
| { |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, |
| "Build SLP failed: unrolling required " |
| "in basic block SLP\n"); |
| /* Fatal mismatch. */ |
| return false; |
| } |
| |
| /* In case of multiple types we need to detect the smallest type. */ |
| vect_update_max_nunits (max_nunits, vectype); |
| return true; |
| } |
| |
| /* Verify if the scalar stmts STMTS are isomorphic, require data |
| permutation or are of unsupported types of operation. Return |
| true if they are, otherwise return false and indicate in *MATCHES |
| which stmts are not isomorphic to the first one. If MATCHES[0] |
| is false then this indicates the comparison could not be |
| carried out or the stmts will never be vectorized by SLP. |
| |
| Note COND_EXPR is possibly isomorphic to another one after swapping its |
| operands. Set SWAP[i] to 1 if stmt I is COND_EXPR and isomorphic to |
| the first stmt by swapping the two operands of comparison; set SWAP[i] |
| to 2 if stmt I is isormorphic to the first stmt by inverting the code |
| of comparison. Take A1 >= B1 ? X1 : Y1 as an exmple, it can be swapped |
| to (B1 <= A1 ? X1 : Y1); or be inverted to (A1 < B1) ? Y1 : X1. */ |
| |
| static bool |
| vect_build_slp_tree_1 (vec_info *vinfo, unsigned char *swap, |
| vec<stmt_vec_info> stmts, unsigned int group_size, |
| poly_uint64 *max_nunits, bool *matches, |
| bool *two_operators, tree *node_vectype) |
| { |
| unsigned int i; |
| stmt_vec_info first_stmt_info = stmts[0]; |
| enum tree_code first_stmt_code = ERROR_MARK; |
| enum tree_code alt_stmt_code = ERROR_MARK; |
| enum tree_code rhs_code = ERROR_MARK; |
| enum tree_code first_cond_code = ERROR_MARK; |
| tree lhs; |
| bool need_same_oprnds = false; |
| tree vectype = NULL_TREE, first_op1 = NULL_TREE; |
| optab optab; |
| int icode; |
| machine_mode optab_op2_mode; |
| machine_mode vec_mode; |
| stmt_vec_info first_load = NULL, prev_first_load = NULL; |
| bool first_stmt_load_p = false, load_p = false; |
| bool first_stmt_phi_p = false, phi_p = false; |
| bool maybe_soft_fail = false; |
| tree soft_fail_nunits_vectype = NULL_TREE; |
| |
| /* For every stmt in NODE find its def stmt/s. */ |
| stmt_vec_info stmt_info; |
| FOR_EACH_VEC_ELT (stmts, i, stmt_info) |
| { |
| gimple *stmt = stmt_info->stmt; |
| swap[i] = 0; |
| matches[i] = false; |
| |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_NOTE, vect_location, "Build SLP for %G", stmt); |
| |
| /* Fail to vectorize statements marked as unvectorizable, throw |
| or are volatile. */ |
| if (!STMT_VINFO_VECTORIZABLE (stmt_info) |
| || stmt_can_throw_internal (cfun, stmt) |
| || gimple_has_volatile_ops (stmt)) |
| { |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, |
| "Build SLP failed: unvectorizable statement %G", |
| stmt); |
| /* ??? For BB vectorization we want to commutate operands in a way |
| to shuffle all unvectorizable defs into one operand and have |
| the other still vectorized. The following doesn't reliably |
| work for this though but it's the easiest we can do here. */ |
| if (is_a <bb_vec_info> (vinfo) && i != 0) |
| continue; |
| /* Fatal mismatch. */ |
| matches[0] = false; |
| return false; |
| } |
| |
| lhs = gimple_get_lhs (stmt); |
| if (lhs == NULL_TREE) |
| { |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, |
| "Build SLP failed: not GIMPLE_ASSIGN nor " |
| "GIMPLE_CALL %G", stmt); |
| if (is_a <bb_vec_info> (vinfo) && i != 0) |
| continue; |
| /* Fatal mismatch. */ |
| matches[0] = false; |
| return false; |
| } |
| |
| tree nunits_vectype; |
| if (!vect_get_vector_types_for_stmt (vinfo, stmt_info, &vectype, |
| &nunits_vectype, group_size)) |
| { |
| if (is_a <bb_vec_info> (vinfo) && i != 0) |
| continue; |
| /* Fatal mismatch. */ |
| matches[0] = false; |
| return false; |
| } |
| /* Record nunits required but continue analysis, producing matches[] |
| as if nunits was not an issue. This allows splitting of groups |
| to happen. */ |
| if (nunits_vectype |
| && !vect_record_max_nunits (vinfo, stmt_info, group_size, |
| nunits_vectype, max_nunits)) |
| { |
| gcc_assert (is_a <bb_vec_info> (vinfo)); |
| maybe_soft_fail = true; |
| soft_fail_nunits_vectype = nunits_vectype; |
| } |
| |
| gcc_assert (vectype); |
| |
| gcall *call_stmt = dyn_cast <gcall *> (stmt); |
| if (call_stmt) |
| { |
| rhs_code = CALL_EXPR; |
| |
| if (gimple_call_internal_p (stmt, IFN_MASK_LOAD)) |
| load_p = true; |
| else if ((gimple_call_internal_p (call_stmt) |
| && (!vectorizable_internal_fn_p |
| (gimple_call_internal_fn (call_stmt)))) |
| || gimple_call_tail_p (call_stmt) |
| || gimple_call_noreturn_p (call_stmt) |
| || gimple_call_chain (call_stmt)) |
| { |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, |
| "Build SLP failed: unsupported call type %G", |
| call_stmt); |
| if (is_a <bb_vec_info> (vinfo) && i != 0) |
| continue; |
| /* Fatal mismatch. */ |
| matches[0] = false; |
| return false; |
| } |
| } |
| else if (gimple_code (stmt) == GIMPLE_PHI) |
| { |
| rhs_code = ERROR_MARK; |
| phi_p = true; |
| } |
| else |
| { |
| rhs_code = gimple_assign_rhs_code (stmt); |
| load_p = gimple_vuse (stmt); |
| } |
| |
| /* Check the operation. */ |
| if (i == 0) |
| { |
| *node_vectype = vectype; |
| first_stmt_code = rhs_code; |
| first_stmt_load_p = load_p; |
| first_stmt_phi_p = phi_p; |
| |
| /* Shift arguments should be equal in all the packed stmts for a |
| vector shift with scalar shift operand. */ |
| if (rhs_code == LSHIFT_EXPR || rhs_code == RSHIFT_EXPR |
| || rhs_code == LROTATE_EXPR |
| || rhs_code == RROTATE_EXPR) |
| { |
| vec_mode = TYPE_MODE (vectype); |
| |
| /* First see if we have a vector/vector shift. */ |
| optab = optab_for_tree_code (rhs_code, vectype, |
| optab_vector); |
| |
| if (!optab |
| || optab_handler (optab, vec_mode) == CODE_FOR_nothing) |
| { |
| /* No vector/vector shift, try for a vector/scalar shift. */ |
| optab = optab_for_tree_code (rhs_code, vectype, |
| optab_scalar); |
| |
| if (!optab) |
| { |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, |
| "Build SLP failed: no optab.\n"); |
| if (is_a <bb_vec_info> (vinfo) && i != 0) |
| continue; |
| /* Fatal mismatch. */ |
| matches[0] = false; |
| return false; |
| } |
| icode = (int) optab_handler (optab, vec_mode); |
| if (icode == CODE_FOR_nothing) |
| { |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, |
| "Build SLP failed: " |
| "op not supported by target.\n"); |
| if (is_a <bb_vec_info> (vinfo) && i != 0) |
| continue; |
| /* Fatal mismatch. */ |
| matches[0] = false; |
| return false; |
| } |
| optab_op2_mode = insn_data[icode].operand[2].mode; |
| if (!VECTOR_MODE_P (optab_op2_mode)) |
| { |
| need_same_oprnds = true; |
| first_op1 = gimple_assign_rhs2 (stmt); |
| } |
| } |
| } |
| else if (rhs_code == WIDEN_LSHIFT_EXPR) |
| { |
| need_same_oprnds = true; |
| first_op1 = gimple_assign_rhs2 (stmt); |
| } |
| else if (!load_p |
| && rhs_code == BIT_FIELD_REF) |
| { |
| tree vec = TREE_OPERAND (gimple_assign_rhs1 (stmt), 0); |
| if (!is_a <bb_vec_info> (vinfo) |
| || TREE_CODE (vec) != SSA_NAME |
| || !operand_equal_p (TYPE_SIZE (vectype), |
| TYPE_SIZE (TREE_TYPE (vec)))) |
| { |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, |
| "Build SLP failed: " |
| "BIT_FIELD_REF not supported\n"); |
| /* Fatal mismatch. */ |
| matches[0] = false; |
| return false; |
| } |
| } |
| else if (call_stmt |
| && gimple_call_internal_p (call_stmt, IFN_DIV_POW2)) |
| { |
| need_same_oprnds = true; |
| first_op1 = gimple_call_arg (call_stmt, 1); |
| } |
| } |
| else |
| { |
| if (first_stmt_code != rhs_code |
| && alt_stmt_code == ERROR_MARK) |
| alt_stmt_code = rhs_code; |
| if ((first_stmt_code != rhs_code |
| && (first_stmt_code != IMAGPART_EXPR |
| || rhs_code != REALPART_EXPR) |
| && (first_stmt_code != REALPART_EXPR |
| || rhs_code != IMAGPART_EXPR) |
| /* Handle mismatches in plus/minus by computing both |
| and merging the results. */ |
| && !((first_stmt_code == PLUS_EXPR |
| || first_stmt_code == MINUS_EXPR) |
| && (alt_stmt_code == PLUS_EXPR |
| || alt_stmt_code == MINUS_EXPR) |
| && rhs_code == alt_stmt_code) |
| && !(STMT_VINFO_GROUPED_ACCESS (stmt_info) |
| && (first_stmt_code == ARRAY_REF |
| || first_stmt_code == BIT_FIELD_REF |
| || first_stmt_code == INDIRECT_REF |
| || first_stmt_code == COMPONENT_REF |
| || first_stmt_code == MEM_REF))) |
| || first_stmt_load_p != load_p |
| || first_stmt_phi_p != phi_p) |
| { |
| if (dump_enabled_p ()) |
| { |
| dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, |
| "Build SLP failed: different operation " |
| "in stmt %G", stmt); |
| dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, |
| "original stmt %G", first_stmt_info->stmt); |
| } |
| /* Mismatch. */ |
| continue; |
| } |
| |
| if (!load_p |
| && first_stmt_code == BIT_FIELD_REF |
| && (TREE_OPERAND (gimple_assign_rhs1 (first_stmt_info->stmt), 0) |
| != TREE_OPERAND (gimple_assign_rhs1 (stmt_info->stmt), 0))) |
| { |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, |
| "Build SLP failed: different BIT_FIELD_REF " |
| "arguments in %G", stmt); |
| /* Mismatch. */ |
| continue; |
| } |
| |
| if (!load_p && rhs_code == CALL_EXPR) |
| { |
| if (!compatible_calls_p (as_a <gcall *> (stmts[0]->stmt), |
| as_a <gcall *> (stmt))) |
| { |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, |
| "Build SLP failed: different calls in %G", |
| stmt); |
| /* Mismatch. */ |
| continue; |
| } |
| } |
| |
| if ((phi_p || gimple_could_trap_p (stmt_info->stmt)) |
| && (gimple_bb (first_stmt_info->stmt) |
| != gimple_bb (stmt_info->stmt))) |
| { |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, |
| "Build SLP failed: different BB for PHI " |
| "or possibly trapping operation in %G", stmt); |
| /* Mismatch. */ |
| continue; |
| } |
| |
| if (need_same_oprnds) |
| { |
| tree other_op1 = (call_stmt |
| ? gimple_call_arg (call_stmt, 1) |
| : gimple_assign_rhs2 (stmt)); |
| if (!operand_equal_p (first_op1, other_op1, 0)) |
| { |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, |
| "Build SLP failed: different shift " |
| "arguments in %G", stmt); |
| /* Mismatch. */ |
| continue; |
| } |
| } |
| |
| if (!types_compatible_p (vectype, *node_vectype)) |
| { |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, |
| "Build SLP failed: different vector type " |
| "in %G", stmt); |
| /* Mismatch. */ |
| continue; |
| } |
| } |
| |
| /* Grouped store or load. */ |
| if (STMT_VINFO_GROUPED_ACCESS (stmt_info)) |
| { |
| if (REFERENCE_CLASS_P (lhs)) |
| { |
| /* Store. */ |
| ; |
| } |
| else |
| { |
| /* Load. */ |
| first_load = DR_GROUP_FIRST_ELEMENT (stmt_info); |
| if (prev_first_load) |
| { |
| /* Check that there are no loads from different interleaving |
| chains in the same node. */ |
| if (prev_first_load != first_load) |
| { |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_MISSED_OPTIMIZATION, |
| vect_location, |
| "Build SLP failed: different " |
| "interleaving chains in one node %G", |
| stmt); |
| /* Mismatch. */ |
| continue; |
| } |
| } |
| else |
| prev_first_load = first_load; |
| } |
| } /* Grouped access. */ |
| else |
| { |
| if (load_p) |
| { |
| /* Not grouped load. */ |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, |
| "Build SLP failed: not grouped load %G", stmt); |
| |
| /* FORNOW: Not grouped loads are not supported. */ |
| if (is_a <bb_vec_info> (vinfo) && i != 0) |
| continue; |
| /* Fatal mismatch. */ |
| matches[0] = false; |
| return false; |
| } |
| |
| /* Not memory operation. */ |
| if (!phi_p |
| && TREE_CODE_CLASS (rhs_code) != tcc_binary |
| && TREE_CODE_CLASS (rhs_code) != tcc_unary |
| && TREE_CODE_CLASS (rhs_code) != tcc_expression |
| && TREE_CODE_CLASS (rhs_code) != tcc_comparison |
| && rhs_code != VIEW_CONVERT_EXPR |
| && rhs_code != CALL_EXPR |
| && rhs_code != BIT_FIELD_REF) |
| { |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, |
| "Build SLP failed: operation unsupported %G", |
| stmt); |
| if (is_a <bb_vec_info> (vinfo) && i != 0) |
| continue; |
| /* Fatal mismatch. */ |
| matches[0] = false; |
| return false; |
| } |
| |
| if (rhs_code == COND_EXPR) |
| { |
| tree cond_expr = gimple_assign_rhs1 (stmt); |
| enum tree_code cond_code = TREE_CODE (cond_expr); |
| enum tree_code swap_code = ERROR_MARK; |
| enum tree_code invert_code = ERROR_MARK; |
| |
| if (i == 0) |
| first_cond_code = TREE_CODE (cond_expr); |
| else if (TREE_CODE_CLASS (cond_code) == tcc_comparison) |
| { |
| bool honor_nans = HONOR_NANS (TREE_OPERAND (cond_expr, 0)); |
| swap_code = swap_tree_comparison (cond_code); |
| invert_code = invert_tree_comparison (cond_code, honor_nans); |
| } |
| |
| if (first_cond_code == cond_code) |
| ; |
| /* Isomorphic can be achieved by swapping. */ |
| else if (first_cond_code == swap_code) |
| swap[i] = 1; |
| /* Isomorphic can be achieved by inverting. */ |
| else if (first_cond_code == invert_code) |
| swap[i] = 2; |
| else |
| { |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, |
| "Build SLP failed: different" |
| " operation %G", stmt); |
| /* Mismatch. */ |
| continue; |
| } |
| } |
| } |
| |
| matches[i] = true; |
| } |
| |
| for (i = 0; i < group_size; ++i) |
| if (!matches[i]) |
| return false; |
| |
| /* If we allowed a two-operation SLP node verify the target can cope |
| with the permute we are going to use. */ |
| if (alt_stmt_code != ERROR_MARK |
| && TREE_CODE_CLASS (alt_stmt_code) != tcc_reference) |
| { |
| *two_operators = true; |
| } |
| |
| if (maybe_soft_fail) |
| { |
| unsigned HOST_WIDE_INT const_nunits; |
| if (!TYPE_VECTOR_SUBPARTS |
| (soft_fail_nunits_vectype).is_constant (&const_nunits) |
| || const_nunits > group_size) |
| matches[0] = false; |
| else |
| { |
| /* With constant vector elements simulate a mismatch at the |
| point we need to split. */ |
| unsigned tail = group_size & (const_nunits - 1); |
| memset (&matches[group_size - tail], 0, sizeof (bool) * tail); |
| } |
| return false; |
| } |
| |
| return true; |
| } |
| |
| /* Traits for the hash_set to record failed SLP builds for a stmt set. |
| Note we never remove apart from at destruction time so we do not |
| need a special value for deleted that differs from empty. */ |
| struct bst_traits |
| { |
| typedef vec <stmt_vec_info> value_type; |
| typedef vec <stmt_vec_info> compare_type; |
| static inline hashval_t hash (value_type); |
| static inline bool equal (value_type existing, value_type candidate); |
| static inline bool is_empty (value_type x) { return !x.exists (); } |
| static inline bool is_deleted (value_type x) { return !x.exists (); } |
| static const bool empty_zero_p = true; |
| static inline void mark_empty (value_type &x) { x.release (); } |
| static inline void mark_deleted (value_type &x) { x.release (); } |
| static inline void remove (value_type &x) { x.release (); } |
| }; |
| inline hashval_t |
| bst_traits::hash (value_type x) |
| { |
| inchash::hash h; |
| for (unsigned i = 0; i < x.length (); ++i) |
| h.add_int (gimple_uid (x[i]->stmt)); |
| return h.end (); |
| } |
| inline bool |
| bst_traits::equal (value_type existing, value_type candidate) |
| { |
| if (existing.length () != candidate.length ()) |
| return false; |
| for (unsigned i = 0; i < existing.length (); ++i) |
| if (existing[i] != candidate[i]) |
| return false; |
| return true; |
| } |
| |
| /* ??? This was std::pair<std::pair<tree_code, vect_def_type>, tree> |
| but then vec::insert does memmove and that's not compatible with |
| std::pair. */ |
| struct chain_op_t |
| { |
| chain_op_t (tree_code code_, vect_def_type dt_, tree op_) |
| : code (code_), dt (dt_), op (op_) {} |
| tree_code code; |
| vect_def_type dt; |
| tree op; |
| }; |
| |
| /* Comparator for sorting associatable chains. */ |
| |
| static int |
| dt_sort_cmp (const void *op1_, const void *op2_, void *) |
| { |
| auto *op1 = (const chain_op_t *) op1_; |
| auto *op2 = (const chain_op_t *) op2_; |
| if (op1->dt != op2->dt) |
| return (int)op1->dt - (int)op2->dt; |
| return (int)op1->code - (int)op2->code; |
| } |
| |
| /* Linearize the associatable expression chain at START with the |
| associatable operation CODE (where PLUS_EXPR also allows MINUS_EXPR), |
| filling CHAIN with the result and using WORKLIST as intermediate storage. |
| CODE_STMT and ALT_CODE_STMT are filled with the first stmt using CODE |
| or MINUS_EXPR. *CHAIN_STMTS if not NULL is filled with all computation |
| stmts, starting with START. */ |
| |
| static void |
| vect_slp_linearize_chain (vec_info *vinfo, |
| vec<std::pair<tree_code, gimple *> > &worklist, |
| vec<chain_op_t> &chain, |
| enum tree_code code, gimple *start, |
| gimple *&code_stmt, gimple *&alt_code_stmt, |
| vec<gimple *> *chain_stmts) |
| { |
| /* For each lane linearize the addition/subtraction (or other |
| uniform associatable operation) expression tree. */ |
| worklist.safe_push (std::make_pair (code, start)); |
| while (!worklist.is_empty ()) |
| { |
| auto entry = worklist.pop (); |
| gassign *stmt = as_a <gassign *> (entry.second); |
| enum tree_code in_code = entry.first; |
| enum tree_code this_code = gimple_assign_rhs_code (stmt); |
| /* Pick some stmts suitable for SLP_TREE_REPRESENTATIVE. */ |
| if (!code_stmt |
| && gimple_assign_rhs_code (stmt) == code) |
| code_stmt = stmt; |
| else if (!alt_code_stmt |
| && gimple_assign_rhs_code (stmt) == MINUS_EXPR) |
| alt_code_stmt = stmt; |
| if (chain_stmts) |
| chain_stmts->safe_push (stmt); |
| for (unsigned opnum = 1; opnum <= 2; ++opnum) |
| { |
| tree op = gimple_op (stmt, opnum); |
| vect_def_type dt; |
| stmt_vec_info def_stmt_info; |
| bool res = vect_is_simple_use (op, vinfo, &dt, &def_stmt_info); |
| gcc_assert (res); |
| if (dt == vect_internal_def |
| && is_pattern_stmt_p (def_stmt_info)) |
| op = gimple_get_lhs (def_stmt_info->stmt); |
| gimple *use_stmt; |
| use_operand_p use_p; |
| if (dt == vect_internal_def |
| && single_imm_use (op, &use_p, &use_stmt) |
| && is_gimple_assign (def_stmt_info->stmt) |
| && (gimple_assign_rhs_code (def_stmt_info->stmt) == code |
| || (code == PLUS_EXPR |
| && (gimple_assign_rhs_code (def_stmt_info->stmt) |
| == MINUS_EXPR)))) |
| { |
| tree_code op_def_code = this_code; |
| if (op_def_code == MINUS_EXPR && opnum == 1) |
| op_def_code = PLUS_EXPR; |
| if (in_code == MINUS_EXPR) |
| op_def_code = op_def_code == PLUS_EXPR ? MINUS_EXPR : PLUS_EXPR; |
| worklist.safe_push (std::make_pair (op_def_code, |
| def_stmt_info->stmt)); |
| } |
| else |
| { |
| tree_code op_def_code = this_code; |
| if (op_def_code == MINUS_EXPR && opnum == 1) |
| op_def_code = PLUS_EXPR; |
| if (in_code == MINUS_EXPR) |
| op_def_code = op_def_code == PLUS_EXPR ? MINUS_EXPR : PLUS_EXPR; |
| chain.safe_push (chain_op_t (op_def_code, dt, op)); |
| } |
| } |
| } |
| } |
| |
| typedef hash_map <vec <stmt_vec_info>, slp_tree, |
| simple_hashmap_traits <bst_traits, slp_tree> > |
| scalar_stmts_to_slp_tree_map_t; |
| |
| static slp_tree |
| vect_build_slp_tree_2 (vec_info *vinfo, slp_tree node, |
| vec<stmt_vec_info> stmts, unsigned int group_size, |
| poly_uint64 *max_nunits, |
| bool *matches, unsigned *limit, unsigned *tree_size, |
| scalar_stmts_to_slp_tree_map_t *bst_map); |
| |
| static slp_tree |
| vect_build_slp_tree (vec_info *vinfo, |
| vec<stmt_vec_info> stmts, unsigned int group_size, |
| poly_uint64 *max_nunits, |
| bool *matches, unsigned *limit, unsigned *tree_size, |
| scalar_stmts_to_slp_tree_map_t *bst_map) |
| { |
| if (slp_tree *leader = bst_map->get (stmts)) |
| { |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_NOTE, vect_location, "re-using %sSLP tree %p\n", |
| !(*leader)->failed ? "" : "failed ", *leader); |
| if (!(*leader)->failed) |
| { |
| SLP_TREE_REF_COUNT (*leader)++; |
| vect_update_max_nunits (max_nunits, (*leader)->max_nunits); |
| stmts.release (); |
| return *leader; |
| } |
| memcpy (matches, (*leader)->failed, sizeof (bool) * group_size); |
| return NULL; |
| } |
| |
| /* Seed the bst_map with a stub node to be filled by vect_build_slp_tree_2 |
| so we can pick up backedge destinations during discovery. */ |
| slp_tree res = new _slp_tree; |
| SLP_TREE_DEF_TYPE (res) = vect_internal_def; |
| SLP_TREE_SCALAR_STMTS (res) = stmts; |
| bst_map->put (stmts.copy (), res); |
| |
| if (*limit == 0) |
| { |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_NOTE, vect_location, |
| "SLP discovery limit exceeded\n"); |
| /* Mark the node invalid so we can detect those when still in use |
| as backedge destinations. */ |
| SLP_TREE_SCALAR_STMTS (res) = vNULL; |
| SLP_TREE_DEF_TYPE (res) = vect_uninitialized_def; |
| res->failed = XNEWVEC (bool, group_size); |
| memset (res->failed, 0, sizeof (bool) * group_size); |
| memset (matches, 0, sizeof (bool) * group_size); |
| return NULL; |
| } |
| --*limit; |
| |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_NOTE, vect_location, |
| "starting SLP discovery for node %p\n", res); |
| |
| poly_uint64 this_max_nunits = 1; |
| slp_tree res_ = vect_build_slp_tree_2 (vinfo, res, stmts, group_size, |
| &this_max_nunits, |
| matches, limit, tree_size, bst_map); |
| if (!res_) |
| { |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_NOTE, vect_location, |
| "SLP discovery for node %p failed\n", res); |
| /* Mark the node invalid so we can detect those when still in use |
| as backedge destinations. */ |
| SLP_TREE_SCALAR_STMTS (res) = vNULL; |
| SLP_TREE_DEF_TYPE (res) = vect_uninitialized_def; |
| res->failed = XNEWVEC (bool, group_size); |
| if (flag_checking) |
| { |
| unsigned i; |
| for (i = 0; i < group_size; ++i) |
| if (!matches[i]) |
| break; |
| gcc_assert (i < group_size); |
| } |
| memcpy (res->failed, matches, sizeof (bool) * group_size); |
| } |
| else |
| { |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_NOTE, vect_location, |
| "SLP discovery for node %p succeeded\n", res); |
| gcc_assert (res_ == res); |
| res->max_nunits = this_max_nunits; |
| vect_update_max_nunits (max_nunits, this_max_nunits); |
| /* Keep a reference for the bst_map use. */ |
| SLP_TREE_REF_COUNT (res)++; |
| } |
| return res_; |
| } |
| |
| /* Helper for building an associated SLP node chain. */ |
| |
| static void |
| vect_slp_build_two_operator_nodes (slp_tree perm, tree vectype, |
| slp_tree op0, slp_tree op1, |
| stmt_vec_info oper1, stmt_vec_info oper2, |
| vec<std::pair<unsigned, unsigned> > lperm) |
| { |
| unsigned group_size = SLP_TREE_LANES (op1); |
| |
| slp_tree child1 = new _slp_tree; |
| SLP_TREE_DEF_TYPE (child1) = vect_internal_def; |
| SLP_TREE_VECTYPE (child1) = vectype; |
| SLP_TREE_LANES (child1) = group_size; |
| SLP_TREE_CHILDREN (child1).create (2); |
| SLP_TREE_CHILDREN (child1).quick_push (op0); |
| SLP_TREE_CHILDREN (child1).quick_push (op1); |
| SLP_TREE_REPRESENTATIVE (child1) = oper1; |
| |
| slp_tree child2 = new _slp_tree; |
| SLP_TREE_DEF_TYPE (child2) = vect_internal_def; |
| SLP_TREE_VECTYPE (child2) = vectype; |
| SLP_TREE_LANES (child2) = group_size; |
| SLP_TREE_CHILDREN (child2).create (2); |
| SLP_TREE_CHILDREN (child2).quick_push (op0); |
| SLP_TREE_REF_COUNT (op0)++; |
| SLP_TREE_CHILDREN (child2).quick_push (op1); |
| SLP_TREE_REF_COUNT (op1)++; |
| SLP_TREE_REPRESENTATIVE (child2) = oper2; |
| |
| SLP_TREE_DEF_TYPE (perm) = vect_internal_def; |
| SLP_TREE_CODE (perm) = VEC_PERM_EXPR; |
| SLP_TREE_VECTYPE (perm) = vectype; |
| SLP_TREE_LANES (perm) = group_size; |
| /* ??? We should set this NULL but that's not expected. */ |
| SLP_TREE_REPRESENTATIVE (perm) = oper1; |
| SLP_TREE_LANE_PERMUTATION (perm) = lperm; |
| SLP_TREE_CHILDREN (perm).quick_push (child1); |
| SLP_TREE_CHILDREN (perm).quick_push (child2); |
| } |
| |
| /* Recursively build an SLP tree starting from NODE. |
| Fail (and return a value not equal to zero) if def-stmts are not |
| isomorphic, require data permutation or are of unsupported types of |
| operation. Otherwise, return 0. |
| The value returned is the depth in the SLP tree where a mismatch |
| was found. */ |
| |
| static slp_tree |
| vect_build_slp_tree_2 (vec_info *vinfo, slp_tree node, |
| vec<stmt_vec_info> stmts, unsigned int group_size, |
| poly_uint64 *max_nunits, |
| bool *matches, unsigned *limit, unsigned *tree_size, |
| scalar_stmts_to_slp_tree_map_t *bst_map) |
| { |
| unsigned nops, i, this_tree_size = 0; |
| poly_uint64 this_max_nunits = *max_nunits; |
| |
| matches[0] = false; |
| |
| stmt_vec_info stmt_info = stmts[0]; |
| if (gcall *stmt = dyn_cast <gcall *> (stmt_info->stmt)) |
| nops = gimple_call_num_args (stmt); |
| else if (gassign *stmt = dyn_cast <gassign *> (stmt_info->stmt)) |
| { |
| nops = gimple_num_ops (stmt) - 1; |
| if (gimple_assign_rhs_code (stmt) == COND_EXPR) |
| nops++; |
| } |
| else if (gphi *phi = dyn_cast <gphi *> (stmt_info->stmt)) |
| nops = gimple_phi_num_args (phi); |
| else |
| return NULL; |
| |
| /* If the SLP node is a PHI (induction or reduction), terminate |
| the recursion. */ |
| bool *skip_args = XALLOCAVEC (bool, nops); |
| memset (skip_args, 0, sizeof (bool) * nops); |
| if (loop_vec_info loop_vinfo = dyn_cast <loop_vec_info> (vinfo)) |
| if (gphi *stmt = dyn_cast <gphi *> (stmt_info->stmt)) |
| { |
| tree scalar_type = TREE_TYPE (PHI_RESULT (stmt)); |
| tree vectype = get_vectype_for_scalar_type (vinfo, scalar_type, |
| group_size); |
| if (!vect_record_max_nunits (vinfo, stmt_info, group_size, vectype, |
| max_nunits)) |
| return NULL; |
| |
| vect_def_type def_type = STMT_VINFO_DEF_TYPE (stmt_info); |
| if (def_type == vect_induction_def) |
| { |
| /* Induction PHIs are not cycles but walk the initial |
| value. Only for inner loops through, for outer loops |
| we need to pick up the value from the actual PHIs |
| to more easily support peeling and epilogue vectorization. */ |
| class loop *loop = LOOP_VINFO_LOOP (loop_vinfo); |
| if (!nested_in_vect_loop_p (loop, stmt_info)) |
| skip_args[loop_preheader_edge (loop)->dest_idx] = true; |
| else |
| loop = loop->inner; |
| skip_args[loop_latch_edge (loop)->dest_idx] = true; |
| } |
| else if (def_type == vect_reduction_def |
| || def_type == vect_double_reduction_def |
| || def_type == vect_nested_cycle) |
| { |
| /* Else def types have to match. */ |
| stmt_vec_info other_info; |
| bool all_same = true; |
| FOR_EACH_VEC_ELT (stmts, i, other_info) |
| { |
| if (STMT_VINFO_DEF_TYPE (other_info) != def_type) |
| return NULL; |
| if (other_info != stmt_info) |
| all_same = false; |
| } |
| class loop *loop = LOOP_VINFO_LOOP (loop_vinfo); |
| /* Reduction initial values are not explicitely represented. */ |
| if (!nested_in_vect_loop_p (loop, stmt_info)) |
| skip_args[loop_preheader_edge (loop)->dest_idx] = true; |
| /* Reduction chain backedge defs are filled manually. |
| ??? Need a better way to identify a SLP reduction chain PHI. |
| Or a better overall way to SLP match those. */ |
| if (all_same && def_type == vect_reduction_def) |
| skip_args[loop_latch_edge (loop)->dest_idx] = true; |
| } |
| else if (def_type != vect_internal_def) |
| return NULL; |
| } |
| |
| |
| bool two_operators = false; |
| unsigned char *swap = XALLOCAVEC (unsigned char, group_size); |
| tree vectype = NULL_TREE; |
| if (!vect_build_slp_tree_1 (vinfo, swap, stmts, group_size, |
| &this_max_nunits, matches, &two_operators, |
| &vectype)) |
| return NULL; |
| |
| /* If the SLP node is a load, terminate the recursion unless masked. */ |
| if (STMT_VINFO_GROUPED_ACCESS (stmt_info) |
| && DR_IS_READ (STMT_VINFO_DATA_REF (stmt_info))) |
| { |
| if (gcall *stmt = dyn_cast <gcall *> (stmt_info->stmt)) |
| { |
| /* Masked load. */ |
| gcc_assert (gimple_call_internal_p (stmt, IFN_MASK_LOAD)); |
| nops = 1; |
| } |
| else |
| { |
| *max_nunits = this_max_nunits; |
| (*tree_size)++; |
| node = vect_create_new_slp_node (node, stmts, 0); |
| SLP_TREE_VECTYPE (node) = vectype; |
| /* And compute the load permutation. Whether it is actually |
| a permutation depends on the unrolling factor which is |
| decided later. */ |
| vec<unsigned> load_permutation; |
| int j; |
| stmt_vec_info load_info; |
| load_permutation.create (group_size); |
| stmt_vec_info first_stmt_info |
| = DR_GROUP_FIRST_ELEMENT (SLP_TREE_SCALAR_STMTS (node)[0]); |
| FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node), j, load_info) |
| { |
| int load_place = vect_get_place_in_interleaving_chain |
| (load_info, first_stmt_info); |
| gcc_assert (load_place != -1); |
| load_permutation.safe_push (load_place); |
| } |
| SLP_TREE_LOAD_PERMUTATION (node) = load_permutation; |
| return node; |
| } |
| } |
| else if (gimple_assign_single_p (stmt_info->stmt) |
| && !gimple_vuse (stmt_info->stmt) |
| && gimple_assign_rhs_code (stmt_info->stmt) == BIT_FIELD_REF) |
| { |
| /* vect_build_slp_tree_2 determined all BIT_FIELD_REFs reference |
| the same SSA name vector of a compatible type to vectype. */ |
| vec<std::pair<unsigned, unsigned> > lperm = vNULL; |
| tree vec = TREE_OPERAND (gimple_assign_rhs1 (stmt_info->stmt), 0); |
| stmt_vec_info estmt_info; |
| FOR_EACH_VEC_ELT (stmts, i, estmt_info) |
| { |
| gassign *estmt = as_a <gassign *> (estmt_info->stmt); |
| tree bfref = gimple_assign_rhs1 (estmt); |
| HOST_WIDE_INT lane; |
| if (!known_eq (bit_field_size (bfref), |
| tree_to_poly_uint64 (TYPE_SIZE (TREE_TYPE (vectype)))) |
| || !constant_multiple_p (bit_field_offset (bfref), |
| bit_field_size (bfref), &lane)) |
| { |
| lperm.release (); |
| matches[0] = false; |
| return NULL; |
| } |
| lperm.safe_push (std::make_pair (0, (unsigned)lane)); |
| } |
| slp_tree vnode = vect_create_new_slp_node (vNULL); |
| /* ??? We record vectype here but we hide eventually necessary |
| punning and instead rely on code generation to materialize |
| VIEW_CONVERT_EXPRs as necessary. We instead should make |
| this explicit somehow. */ |
| SLP_TREE_VECTYPE (vnode) = vectype; |
| SLP_TREE_VEC_DEFS (vnode).safe_push (vec); |
| /* We are always building a permutation node even if it is an identity |
| permute to shield the rest of the vectorizer from the odd node |
| representing an actual vector without any scalar ops. |
| ??? We could hide it completely with making the permute node |
| external? */ |
| node = vect_create_new_slp_node (node, stmts, 1); |
| SLP_TREE_CODE (node) = VEC_PERM_EXPR; |
| SLP_TREE_LANE_PERMUTATION (node) = lperm; |
| SLP_TREE_VECTYPE (node) = vectype; |
| SLP_TREE_CHILDREN (node).quick_push (vnode); |
| return node; |
| } |
| /* When discovery reaches an associatable operation see whether we can |
| improve that to match up lanes in a way superior to the operand |
| swapping code which at most looks at two defs. |
| ??? For BB vectorization we cannot do the brute-force search |
| for matching as we can succeed by means of builds from scalars |
| and have no good way to "cost" one build against another. */ |
| else if (is_a <loop_vec_info> (vinfo) |
| /* ??? We don't handle !vect_internal_def defs below. */ |
| && STMT_VINFO_DEF_TYPE (stmt_info) == vect_internal_def |
| && is_gimple_assign (stmt_info->stmt) |
| && (associative_tree_code (gimple_assign_rhs_code (stmt_info->stmt)) |
| || gimple_assign_rhs_code (stmt_info->stmt) == MINUS_EXPR) |
| && ((FLOAT_TYPE_P (vectype) && flag_associative_math) |
| || (INTEGRAL_TYPE_P (TREE_TYPE (vectype)) |
| && TYPE_OVERFLOW_WRAPS (TREE_TYPE (vectype))))) |
| { |
| /* See if we have a chain of (mixed) adds or subtracts or other |
| associatable ops. */ |
| enum tree_code code = gimple_assign_rhs_code (stmt_info->stmt); |
| if (code == MINUS_EXPR) |
| code = PLUS_EXPR; |
| stmt_vec_info other_op_stmt_info = NULL; |
| stmt_vec_info op_stmt_info = NULL; |
| unsigned chain_len = 0; |
| auto_vec<chain_op_t> chain; |
| auto_vec<std::pair<tree_code, gimple *> > worklist; |
| auto_vec<vec<chain_op_t> > chains (group_size); |
| auto_vec<slp_tree, 4> children; |
| bool hard_fail = true; |
| for (unsigned lane = 0; lane < group_size; ++lane) |
| { |
| /* For each lane linearize the addition/subtraction (or other |
| uniform associatable operation) expression tree. */ |
| gimple *op_stmt = NULL, *other_op_stmt = NULL; |
| vect_slp_linearize_chain (vinfo, worklist, chain, code, |
| stmts[lane]->stmt, op_stmt, other_op_stmt, |
| NULL); |
| if (!op_stmt_info && op_stmt) |
| op_stmt_info = vinfo->lookup_stmt (op_stmt); |
| if (!other_op_stmt_info && other_op_stmt) |
| other_op_stmt_info = vinfo->lookup_stmt (other_op_stmt); |
| if (chain.length () == 2) |
| { |
| /* In a chain of just two elements resort to the regular |
| operand swapping scheme. If we run into a length |
| mismatch still hard-FAIL. */ |
| if (chain_len == 0) |
| hard_fail = false; |
| else |
| { |
| matches[lane] = false; |
| /* ??? We might want to process the other lanes, but |
| make sure to not give false matching hints to the |
| caller for lanes we did not process. */ |
| if (lane != group_size - 1) |
| matches[0] = false; |
| } |
| break; |
| } |
| else if (chain_len == 0) |
| chain_len = chain.length (); |
| else if (chain.length () != chain_len) |
| { |
| /* ??? Here we could slip in magic to compensate with |
| neutral operands. */ |
| matches[lane] = false; |
| if (lane != group_size - 1) |
| matches[0] = false; |
| break; |
| } |
| chains.quick_push (chain.copy ()); |
| chain.truncate (0); |
| } |
| if (chains.length () == group_size) |
| { |
| /* We cannot yet use SLP_TREE_CODE to communicate the operation. */ |
| if (!op_stmt_info) |
| { |
| hard_fail = false; |
| goto out; |
| } |
| /* Now we have a set of chains with the same length. */ |
| /* 1. pre-sort according to def_type and operation. */ |
| for (unsigned lane = 0; lane < group_size; ++lane) |
| chains[lane].stablesort (dt_sort_cmp, vinfo); |
| if (dump_enabled_p ()) |
| { |
| dump_printf_loc (MSG_NOTE, vect_location, |
| "pre-sorted chains of %s\n", |
| get_tree_code_name (code)); |
| for (unsigned lane = 0; lane < group_size; ++lane) |
| { |
| for (unsigned opnum = 0; opnum < chain_len; ++opnum) |
| dump_printf (MSG_NOTE, "%s %T ", |
| get_tree_code_name (chains[lane][opnum].code), |
| chains[lane][opnum].op); |
| dump_printf (MSG_NOTE, "\n"); |
| } |
| } |
| /* 2. try to build children nodes, associating as necessary. */ |
| for (unsigned n = 0; n < chain_len; ++n) |
| { |
| vect_def_type dt = chains[0][n].dt; |
| unsigned lane; |
| for (lane = 0; lane < group_size; ++lane) |
| if (chains[lane][n].dt != dt) |
| { |
| if (dt == vect_constant_def |
| && chains[lane][n].dt == vect_external_def) |
| dt = vect_external_def; |
| else if (dt == vect_external_def |
| && chains[lane][n].dt == vect_constant_def) |
| ; |
| else |
| break; |
| } |
| if (lane != group_size) |
| { |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_NOTE, vect_location, |
| "giving up on chain due to mismatched " |
| "def types\n"); |
| matches[lane] = false; |
| if (lane != group_size - 1) |
| matches[0] = false; |
| goto out; |
| } |
| if (dt == vect_constant_def |
| || dt == vect_external_def) |
| { |
| /* We can always build those. Might want to sort last |
| or defer building. */ |
| vec<tree> ops; |
| ops.create (group_size); |
| for (lane = 0; lane < group_size; ++lane) |
| ops.quick_push (chains[lane][n].op); |
| slp_tree child = vect_create_new_slp_node (ops); |
| SLP_TREE_DEF_TYPE (child) = dt; |
| children.safe_push (child); |
| } |
| else if (dt != vect_internal_def) |
| { |
| /* Not sure, we might need sth special. |
| gcc.dg/vect/pr96854.c, |
| gfortran.dg/vect/fast-math-pr37021.f90 |
| and gfortran.dg/vect/pr61171.f trigger. */ |
| /* Soft-fail for now. */ |
| hard_fail = false; |
| goto out; |
| } |
| else |
| { |
| vec<stmt_vec_info> op_stmts; |
| op_stmts.create (group_size); |
| slp_tree child = NULL; |
| /* Brute-force our way. We have to consider a lane |
| failing after fixing an earlier fail up in the |
| SLP discovery recursion. So track the current |
| permute per lane. */ |
| unsigned *perms = XALLOCAVEC (unsigned, group_size); |
| memset (perms, 0, sizeof (unsigned) * group_size); |
| do |
| { |
| op_stmts.truncate (0); |
| for (lane = 0; lane < group_size; ++lane) |
| op_stmts.quick_push |
| (vinfo->lookup_def (chains[lane][n].op)); |
| child = vect_build_slp_tree (vinfo, op_stmts, |
| group_size, &this_max_nunits, |
| matches, limit, |
| &this_tree_size, bst_map); |
| /* ??? We're likely getting too many fatal mismatches |
| here so maybe we want to ignore them (but then we |
| have no idea which lanes fatally mismatched). */ |
| if (child || !matches[0]) |
| break; |
| /* Swap another lane we have not yet matched up into |
| lanes that did not match. If we run out of |
| permute possibilities for a lane terminate the |
| search. */ |
| bool term = false; |
| for (lane = 1; lane < group_size; ++lane) |
| if (!matches[lane]) |
| { |
| if (n + perms[lane] + 1 == chain_len) |
| { |
| term = true; |
| break; |
| } |
| std::swap (chains[lane][n], |
| chains[lane][n + perms[lane] + 1]); |
| perms[lane]++; |
| } |
| if (term) |
| break; |
| } |
| while (1); |
| if (!child) |
| { |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_NOTE, vect_location, |
| "failed to match up op %d\n", n); |
| op_stmts.release (); |
| if (lane != group_size - 1) |
| matches[0] = false; |
| else |
| matches[lane] = false; |
| goto out; |
| } |
| if (dump_enabled_p ()) |
| { |
| dump_printf_loc (MSG_NOTE, vect_location, |
| "matched up op %d to\n", n); |
| vect_print_slp_tree (MSG_NOTE, vect_location, child); |
| } |
| children.safe_push (child); |
| } |
| } |
| /* 3. build SLP nodes to combine the chain. */ |
| for (unsigned lane = 0; lane < group_size; ++lane) |
| if (chains[lane][0].code != code) |
| { |
| /* See if there's any alternate all-PLUS entry. */ |
| unsigned n; |
| for (n = 1; n < chain_len; ++n) |
| { |
| for (lane = 0; lane < group_size; ++lane) |
| if (chains[lane][n].code != code) |
| break; |
| if (lane == group_size) |
| break; |
| } |
| if (n != chain_len) |
| { |
| /* Swap that in at first position. */ |
| std::swap (children[0], children[n]); |
| for (lane = 0; lane < group_size; ++lane) |
| std::swap (chains[lane][0], chains[lane][n]); |
| } |
| else |
| { |
| /* ??? When this triggers and we end up with two |
| vect_constant/external_def up-front things break (ICE) |
| spectacularly finding an insertion place for the |
| all-constant op. We should have a fully |
| vect_internal_def operand though(?) so we can swap |
| that into first place and then prepend the all-zero |
| constant. */ |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_NOTE, vect_location, |
| "inserting constant zero to compensate " |
| "for (partially) negated first " |
| "operand\n"); |
| chain_len++; |
| for (lane = 0; lane < group_size; ++lane) |
| chains[lane].safe_insert |
| (0, chain_op_t (code, vect_constant_def, NULL_TREE)); |
| vec<tree> zero_ops; |
| zero_ops.create (group_size); |
| zero_ops.quick_push (build_zero_cst (TREE_TYPE (vectype))); |
| for (lane = 1; lane < group_size; ++lane) |
| zero_ops.quick_push (zero_ops[0]); |
| slp_tree zero = vect_create_new_slp_node (zero_ops); |
| SLP_TREE_DEF_TYPE (zero) = vect_constant_def; |
| children.safe_insert (0, zero); |
| } |
| break; |
| } |
| for (unsigned i = 1; i < children.length (); ++i) |
| { |
| slp_tree op0 = children[i - 1]; |
| slp_tree op1 = children[i]; |
| bool this_two_op = false; |
| for (unsigned lane = 0; lane < group_size; ++lane) |
| if (chains[lane][i].code != chains[0][i].code) |
| { |
| this_two_op = true; |
| break; |
| } |
| slp_tree child; |
| if (i == children.length () - 1) |
| child = vect_create_new_slp_node (node, stmts, 2); |
| else |
| child = vect_create_new_slp_node (2, ERROR_MARK); |
| if (this_two_op) |
| { |
| vec<std::pair<unsigned, unsigned> > lperm; |
| lperm.create (group_size); |
| for (unsigned lane = 0; lane < group_size; ++lane) |
| lperm.quick_push (std::make_pair |
| (chains[lane][i].code != chains[0][i].code, lane)); |
| vect_slp_build_two_operator_nodes (child, vectype, op0, op1, |
| (chains[0][i].code == code |
| ? op_stmt_info |
| : other_op_stmt_info), |
| (chains[0][i].code == code |
| ? other_op_stmt_info |
| : op_stmt_info), |
| lperm); |
| } |
| else |
| { |
| SLP_TREE_DEF_TYPE (child) = vect_internal_def; |
| SLP_TREE_VECTYPE (child) = vectype; |
| SLP_TREE_LANES (child) = group_size; |
| SLP_TREE_CHILDREN (child).quick_push (op0); |
| SLP_TREE_CHILDREN (child).quick_push (op1); |
| SLP_TREE_REPRESENTATIVE (child) |
| = (chains[0][i].code == code |
| ? op_stmt_info : other_op_stmt_info); |
| } |
| children[i] = child; |
| } |
| *tree_size += this_tree_size + 1; |
| *max_nunits = this_max_nunits; |
| while (!chains.is_empty ()) |
| chains.pop ().release (); |
| return node; |
| } |
| out: |
| while (!children.is_empty ()) |
| vect_free_slp_tree (children.pop ()); |
| while (!chains.is_empty ()) |
| chains.pop ().release (); |
| /* Hard-fail, otherwise we might run into quadratic processing of the |
| chains starting one stmt into the chain again. */ |
| if (hard_fail) |
| return NULL; |
| /* Fall thru to normal processing. */ |
| } |
| |
| /* Get at the operands, verifying they are compatible. */ |
| vec<slp_oprnd_info> oprnds_info = vect_create_oprnd_info (nops, group_size); |
| slp_oprnd_info oprnd_info; |
| FOR_EACH_VEC_ELT (stmts, i, stmt_info) |
| { |
| int res = vect_get_and_check_slp_defs (vinfo, swap[i], skip_args, |
| stmts, i, &oprnds_info); |
| if (res != 0) |
| matches[(res == -1) ? 0 : i] = false; |
| if (!matches[0]) |
| break; |
| } |
| for (i = 0; i < group_size; ++i) |
| if (!matches[i]) |
| { |
| vect_free_oprnd_info (oprnds_info); |
| return NULL; |
| } |
| swap = NULL; |
| |
| auto_vec<slp_tree, 4> children; |
| |
| stmt_info = stmts[0]; |
| |
| /* Create SLP_TREE nodes for the definition node/s. */ |
| FOR_EACH_VEC_ELT (oprnds_info, i, oprnd_info) |
| { |
| slp_tree child; |
| unsigned int j; |
| |
| /* We're skipping certain operands from processing, for example |
| outer loop reduction initial defs. */ |
| if (skip_args[i]) |
| { |
| children.safe_push (NULL); |
| continue; |
| } |
| |
| if (oprnd_info->first_dt == vect_uninitialized_def) |
| { |
| /* COND_EXPR have one too many eventually if the condition |
| is a SSA name. */ |
| gcc_assert (i == 3 && nops == 4); |
| continue; |
| } |
| |
| if (is_a <bb_vec_info> (vinfo) |
| && oprnd_info->first_dt == vect_internal_def |
| && !oprnd_info->any_pattern) |
| { |
| /* For BB vectorization, if all defs are the same do not |
| bother to continue the build along the single-lane |
| graph but use a splat of the scalar value. */ |
| stmt_vec_info first_def = oprnd_info->def_stmts[0]; |
| for (j = 1; j < group_size; ++j) |
| if (oprnd_info->def_stmts[j] != first_def) |
| break; |
| if (j == group_size |
| /* But avoid doing this for loads where we may be |
| able to CSE things, unless the stmt is not |
| vectorizable. */ |
| && (!STMT_VINFO_VECTORIZABLE (first_def) |
| || !gimple_vuse (first_def->stmt))) |
| { |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_NOTE, vect_location, |
| "Using a splat of the uniform operand\n"); |
| oprnd_info->first_dt = vect_external_def; |
| } |
| } |
| |
| if (oprnd_info->first_dt == vect_external_def |
| || oprnd_info->first_dt == vect_constant_def) |
| { |
| slp_tree invnode = vect_create_new_slp_node (oprnd_info->ops); |
| SLP_TREE_DEF_TYPE (invnode) = oprnd_info->first_dt; |
| oprnd_info->ops = vNULL; |
| children.safe_push (invnode); |
| continue; |
| } |
| |
| if ((child = vect_build_slp_tree (vinfo, oprnd_info->def_stmts, |
| group_size, &this_max_nunits, |
| matches, limit, |
| &this_tree_size, bst_map)) != NULL) |
| { |
| oprnd_info->def_stmts = vNULL; |
| children.safe_push (child); |
| continue; |
| } |
| |
| /* If the SLP build for operand zero failed and operand zero |
| and one can be commutated try that for the scalar stmts |
| that failed the match. */ |
| if (i == 0 |
| /* A first scalar stmt mismatch signals a fatal mismatch. */ |
| && matches[0] |
| /* ??? For COND_EXPRs we can swap the comparison operands |
| as well as the arms under some constraints. */ |
| && nops == 2 |
| && oprnds_info[1]->first_dt == vect_internal_def |
| && is_gimple_assign (stmt_info->stmt) |
| /* Swapping operands for reductions breaks assumptions later on. */ |
| && STMT_VINFO_DEF_TYPE (stmt_info) != vect_reduction_def |
| && STMT_VINFO_DEF_TYPE (stmt_info) != vect_double_reduction_def) |
| { |
| /* See whether we can swap the matching or the non-matching |
| stmt operands. */ |
| bool swap_not_matching = true; |
| do |
| { |
| for (j = 0; j < group_size; ++j) |
| { |
| if (matches[j] != !swap_not_matching) |
| continue; |
| stmt_vec_info stmt_info = stmts[j]; |
| /* Verify if we can swap operands of this stmt. */ |
| gassign *stmt = dyn_cast <gassign *> (stmt_info->stmt); |
| if (!stmt |
| || !commutative_tree_code (gimple_assign_rhs_code (stmt))) |
| { |
| if (!swap_not_matching) |
| goto fail; |
| swap_not_matching = false; |
| break; |
| } |
| } |
| } |
| while (j != group_size); |
| |
| /* Swap mismatched definition stmts. */ |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_NOTE, vect_location, |
| "Re-trying with swapped operands of stmts "); |
| for (j = 0; j < group_size; ++j) |
| if (matches[j] == !swap_not_matching) |
| { |
| std::swap (oprnds_info[0]->def_stmts[j], |
| oprnds_info[1]->def_stmts[j]); |
| std::swap (oprnds_info[0]->ops[j], |
| oprnds_info[1]->ops[j]); |
| if (dump_enabled_p ()) |
| dump_printf (MSG_NOTE, "%d ", j); |
| } |
| if (dump_enabled_p ()) |
| dump_printf (MSG_NOTE, "\n"); |
| /* After swapping some operands we lost track whether an |
| operand has any pattern defs so be conservative here. */ |
| if (oprnds_info[0]->any_pattern || oprnds_info[1]->any_pattern) |
| oprnds_info[0]->any_pattern = oprnds_info[1]->any_pattern = true; |
| /* And try again with scratch 'matches' ... */ |
| bool *tem = XALLOCAVEC (bool, group_size); |
| if ((child = vect_build_slp_tree (vinfo, oprnd_info->def_stmts, |
| group_size, &this_max_nunits, |
| tem, limit, |
| &this_tree_size, bst_map)) != NULL) |
| { |
| oprnd_info->def_stmts = vNULL; |
| children.safe_push (child); |
| continue; |
| } |
| } |
| fail: |
| |
| /* If the SLP build failed and we analyze a basic-block |
| simply treat nodes we fail to build as externally defined |
| (and thus build vectors from the scalar defs). |
| The cost model will reject outright expensive cases. |
| ??? This doesn't treat cases where permutation ultimatively |
| fails (or we don't try permutation below). Ideally we'd |
| even compute a permutation that will end up with the maximum |
| SLP tree size... */ |
| if (is_a <bb_vec_info> (vinfo) |
| /* ??? Rejecting patterns this way doesn't work. We'd have to |
| do extra work to cancel the pattern so the uses see the |
| scalar version. */ |
| && !is_pattern_stmt_p (stmt_info) |
| && !oprnd_info->any_pattern) |
| { |
| /* But if there's a leading vector sized set of matching stmts |
| fail here so we can split the group. This matches the condition |
| vect_analyze_slp_instance uses. */ |
| /* ??? We might want to split here and combine the results to support |
| multiple vector sizes better. */ |
| for (j = 0; j < group_size; ++j) |
| if (!matches[j]) |
| break; |
| if (!known_ge (j, TYPE_VECTOR_SUBPARTS (vectype))) |
| { |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_NOTE, vect_location, |
| "Building vector operands from scalars\n"); |
| this_tree_size++; |
| child = vect_create_new_slp_node (oprnd_info->ops); |
| children.safe_push (child); |
| oprnd_info->ops = vNULL; |
| continue; |
| } |
| } |
| |
| gcc_assert (child == NULL); |
| FOR_EACH_VEC_ELT (children, j, child) |
| if (child) |
| vect_free_slp_tree (child); |
| vect_free_oprnd_info (oprnds_info); |
| return NULL; |
| } |
| |
| vect_free_oprnd_info (oprnds_info); |
| |
| /* If we have all children of a child built up from uniform scalars |
| or does more than one possibly expensive vector construction then |
| just throw that away, causing it built up from scalars. |
| The exception is the SLP node for the vector store. */ |
| if (is_a <bb_vec_info> (vinfo) |
| && !STMT_VINFO_GROUPED_ACCESS (stmt_info) |
| /* ??? Rejecting patterns this way doesn't work. We'd have to |
| do extra work to cancel the pattern so the uses see the |
| scalar version. */ |
| && !is_pattern_stmt_p (stmt_info)) |
| { |
| slp_tree child; |
| unsigned j; |
| bool all_uniform_p = true; |
| unsigned n_vector_builds = 0; |
| FOR_EACH_VEC_ELT (children, j, child) |
| { |
| if (!child) |
| ; |
| else if (SLP_TREE_DEF_TYPE (child) == vect_internal_def) |
| all_uniform_p = false; |
| else if (!vect_slp_tree_uniform_p (child)) |
| { |
| all_uniform_p = false; |
| if (SLP_TREE_DEF_TYPE (child) == vect_external_def) |
| n_vector_builds++; |
| } |
| } |
| if (all_uniform_p |
| || n_vector_builds > 1 |
| || (n_vector_builds == children.length () |
| && is_a <gphi *> (stmt_info->stmt))) |
| { |
| /* Roll back. */ |
| matches[0] = false; |
| FOR_EACH_VEC_ELT (children, j, child) |
| if (child) |
| vect_free_slp_tree (child); |
| |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_NOTE, vect_location, |
| "Building parent vector operands from " |
| "scalars instead\n"); |
| return NULL; |
| } |
| } |
| |
| *tree_size += this_tree_size + 1; |
| *max_nunits = this_max_nunits; |
| |
| if (two_operators) |
| { |
| /* ??? We'd likely want to either cache in bst_map sth like |
| { a+b, NULL, a+b, NULL } and { NULL, a-b, NULL, a-b } or |
| the true { a+b, a+b, a+b, a+b } ... but there we don't have |
| explicit stmts to put in so the keying on 'stmts' doesn't |
| work (but we have the same issue with nodes that use 'ops'). */ |
| slp_tree one = new _slp_tree; |
| slp_tree two = new _slp_tree; |
| SLP_TREE_DEF_TYPE (one) = vect_internal_def; |
| SLP_TREE_DEF_TYPE (two) = vect_internal_def; |
| SLP_TREE_VECTYPE (one) = vectype; |
| SLP_TREE_VECTYPE (two) = vectype; |
| SLP_TREE_CHILDREN (one).safe_splice (children); |
| SLP_TREE_CHILDREN (two).safe_splice (children); |
| slp_tree child; |
| FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (two), i, child) |
| SLP_TREE_REF_COUNT (child)++; |
| |
| /* Here we record the original defs since this |
| node represents the final lane configuration. */ |
| node = vect_create_new_slp_node (node, stmts, 2); |
| SLP_TREE_VECTYPE (node) = vectype; |
| SLP_TREE_CODE (node) = VEC_PERM_EXPR; |
| SLP_TREE_CHILDREN (node).quick_push (one); |
| SLP_TREE_CHILDREN (node).quick_push (two); |
| gassign *stmt = as_a <gassign *> (stmts[0]->stmt); |
| enum tree_code code0 = gimple_assign_rhs_code (stmt); |
| enum tree_code ocode = ERROR_MARK; |
| stmt_vec_info ostmt_info; |
| unsigned j = 0; |
| FOR_EACH_VEC_ELT (stmts, i, ostmt_info) |
| { |
| gassign *ostmt = as_a <gassign *> (ostmt_info->stmt); |
| if (gimple_assign_rhs_code (ostmt) != code0) |
| { |
| SLP_TREE_LANE_PERMUTATION (node).safe_push (std::make_pair (1, i)); |
| ocode = gimple_assign_rhs_code (ostmt); |
| j = i; |
| } |
| else |
| SLP_TREE_LANE_PERMUTATION (node).safe_push (std::make_pair (0, i)); |
| } |
| SLP_TREE_CODE (one) = code0; |
| SLP_TREE_CODE (two) = ocode; |
| SLP_TREE_LANES (one) = stmts.length (); |
| SLP_TREE_LANES (two) = stmts.length (); |
| SLP_TREE_REPRESENTATIVE (one) = stmts[0]; |
| SLP_TREE_REPRESENTATIVE (two) = stmts[j]; |
| return node; |
| } |
| |
| node = vect_create_new_slp_node (node, stmts, nops); |
| SLP_TREE_VECTYPE (node) = vectype; |
| SLP_TREE_CHILDREN (node).splice (children); |
| return node; |
| } |
| |
| /* Dump a single SLP tree NODE. */ |
| |
| static void |
| vect_print_slp_tree (dump_flags_t dump_kind, dump_location_t loc, |
| slp_tree node) |
| { |
| unsigned i, j; |
| slp_tree child; |
| stmt_vec_info stmt_info; |
| tree op; |
| |
| dump_metadata_t metadata (dump_kind, loc.get_impl_location ()); |
| dump_user_location_t user_loc = loc.get_user_location (); |
| dump_printf_loc (metadata, user_loc, "node%s %p (max_nunits=%u, refcnt=%u)\n", |
| SLP_TREE_DEF_TYPE (node) == vect_external_def |
| ? " (external)" |
| : (SLP_TREE_DEF_TYPE (node) == vect_constant_def |
| ? " (constant)" |
| : ""), node, |
| estimated_poly_value (node->max_nunits), |
| SLP_TREE_REF_COUNT (node)); |
| if (SLP_TREE_DEF_TYPE (node) == vect_internal_def) |
| { |
| if (SLP_TREE_CODE (node) == VEC_PERM_EXPR) |
| dump_printf_loc (metadata, user_loc, "op: VEC_PERM_EXPR\n"); |
| else |
| dump_printf_loc (metadata, user_loc, "op template: %G", |
| SLP_TREE_REPRESENTATIVE (node)->stmt); |
| } |
| if (SLP_TREE_SCALAR_STMTS (node).exists ()) |
| FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node), i, stmt_info) |
| dump_printf_loc (metadata, user_loc, "\tstmt %u %G", i, stmt_info->stmt); |
| else |
| { |
| dump_printf_loc (metadata, user_loc, "\t{ "); |
| FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_OPS (node), i, op) |
| dump_printf (metadata, "%T%s ", op, |
| i < SLP_TREE_SCALAR_OPS (node).length () - 1 ? "," : ""); |
| dump_printf (metadata, "}\n"); |
| } |
| if (SLP_TREE_LOAD_PERMUTATION (node).exists ()) |
| { |
| dump_printf_loc (metadata, user_loc, "\tload permutation {"); |
| FOR_EACH_VEC_ELT (SLP_TREE_LOAD_PERMUTATION (node), i, j) |
| dump_printf (dump_kind, " %u", j); |
| dump_printf (dump_kind, " }\n"); |
| } |
| if (SLP_TREE_LANE_PERMUTATION (node).exists ()) |
| { |
| dump_printf_loc (metadata, user_loc, "\tlane permutation {"); |
| for (i = 0; i < SLP_TREE_LANE_PERMUTATION (node).length (); ++i) |
| dump_printf (dump_kind, " %u[%u]", |
| SLP_TREE_LANE_PERMUTATION (node)[i].first, |
| SLP_TREE_LANE_PERMUTATION (node)[i].second); |
| dump_printf (dump_kind, " }\n"); |
| } |
| if (SLP_TREE_CHILDREN (node).is_empty ()) |
| return; |
| dump_printf_loc (metadata, user_loc, "\tchildren"); |
| FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node), i, child) |
| dump_printf (dump_kind, " %p", (void *)child); |
| dump_printf (dump_kind, "\n"); |
| } |
| |
| DEBUG_FUNCTION void |
| debug (slp_tree node) |
| { |
| debug_dump_context ctx; |
| vect_print_slp_tree (MSG_NOTE, |
| dump_location_t::from_location_t (UNKNOWN_LOCATION), |
| node); |
| } |
| |
| /* Recursive helper for the dot producer below. */ |
| |
| static void |
| dot_slp_tree (FILE *f, slp_tree node, hash_set<slp_tree> &visited) |
| { |
| if (visited.add (node)) |
| return; |
| |
| fprintf (f, "\"%p\" [label=\"", (void *)node); |
| vect_print_slp_tree (MSG_NOTE, |
| dump_location_t::from_location_t (UNKNOWN_LOCATION), |
| node); |
| fprintf (f, "\"];\n"); |
| |
| |
| for (slp_tree child : SLP_TREE_CHILDREN (node)) |
| fprintf (f, "\"%p\" -> \"%p\";", (void *)node, (void *)child); |
| |
| for (slp_tree child : SLP_TREE_CHILDREN (node)) |
| dot_slp_tree (f, child, visited); |
| } |
| |
| DEBUG_FUNCTION void |
| dot_slp_tree (const char *fname, slp_tree node) |
| { |
| FILE *f = fopen (fname, "w"); |
| fprintf (f, "digraph {\n"); |
| fflush (f); |
| { |
| debug_dump_context ctx (f); |
| hash_set<slp_tree> visited; |
| dot_slp_tree (f, node, visited); |
| } |
| fflush (f); |
| fprintf (f, "}\n"); |
| fclose (f); |
| } |
| |
| /* Dump a slp tree NODE using flags specified in DUMP_KIND. */ |
| |
| static void |
| vect_print_slp_graph (dump_flags_t dump_kind, dump_location_t loc, |
| slp_tree node, hash_set<slp_tree> &visited) |
| { |
| unsigned i; |
| slp_tree child; |
| |
| if (visited.add (node)) |
| return; |
| |
| vect_print_slp_tree (dump_kind, loc, node); |
| |
| FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node), i, child) |
| if (child) |
| vect_print_slp_graph (dump_kind, loc, child, visited); |
| } |
| |
| static void |
| vect_print_slp_graph (dump_flags_t dump_kind, dump_location_t loc, |
| slp_tree entry) |
| { |
| hash_set<slp_tree> visited; |
| vect_print_slp_graph (dump_kind, loc, entry, visited); |
| } |
| |
| /* Mark the tree rooted at NODE with PURE_SLP. */ |
| |
| static void |
| vect_mark_slp_stmts (slp_tree node, hash_set<slp_tree> &visited) |
| { |
| int i; |
| stmt_vec_info stmt_info; |
| slp_tree child; |
| |
| if (SLP_TREE_DEF_TYPE (node) != vect_internal_def) |
| return; |
| |
| if (visited.add (node)) |
| return; |
| |
| FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node), i, stmt_info) |
| STMT_SLP_TYPE (stmt_info) = pure_slp; |
| |
| FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node), i, child) |
| if (child) |
| vect_mark_slp_stmts (child, visited); |
| } |
| |
| static void |
| vect_mark_slp_stmts (slp_tree node) |
| { |
| hash_set<slp_tree> visited; |
| vect_mark_slp_stmts (node, visited); |
| } |
| |
| /* Mark the statements of the tree rooted at NODE as relevant (vect_used). */ |
| |
| static void |
| vect_mark_slp_stmts_relevant (slp_tree node, hash_set<slp_tree> &visited) |
| { |
| int i; |
| stmt_vec_info stmt_info; |
| slp_tree child; |
| |
| if (SLP_TREE_DEF_TYPE (node) != vect_internal_def) |
| return; |
| |
| if (visited.add (node)) |
| return; |
| |
| FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node), i, stmt_info) |
| { |
| gcc_assert (!STMT_VINFO_RELEVANT (stmt_info) |
| || STMT_VINFO_RELEVANT (stmt_info) == vect_used_in_scope); |
| STMT_VINFO_RELEVANT (stmt_info) = vect_used_in_scope; |
| } |
| |
| FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node), i, child) |
| if (child) |
| vect_mark_slp_stmts_relevant (child, visited); |
| } |
| |
| static void |
| vect_mark_slp_stmts_relevant (slp_tree node) |
| { |
| hash_set<slp_tree> visited; |
| vect_mark_slp_stmts_relevant (node, visited); |
| } |
| |
| |
| /* Gather loads in the SLP graph NODE and populate the INST loads array. */ |
| |
| static void |
| vect_gather_slp_loads (vec<slp_tree> &loads, slp_tree node, |
| hash_set<slp_tree> &visited) |
| { |
| if (!node || visited.add (node)) |
| return; |
| |
| if (SLP_TREE_CHILDREN (node).length () == 0) |
| { |
| if (SLP_TREE_DEF_TYPE (node) != vect_internal_def) |
| return; |
| stmt_vec_info stmt_info = SLP_TREE_SCALAR_STMTS (node)[0]; |
| if (STMT_VINFO_GROUPED_ACCESS (stmt_info) |
| && DR_IS_READ (STMT_VINFO_DATA_REF (stmt_info))) |
| loads.safe_push (node); |
| } |
| else |
| { |
| unsigned i; |
| slp_tree child; |
| FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node), i, child) |
| vect_gather_slp_loads (loads, child, visited); |
| } |
| } |
| |
| |
| /* Find the last store in SLP INSTANCE. */ |
| |
| stmt_vec_info |
| vect_find_last_scalar_stmt_in_slp (slp_tree node) |
| { |
| stmt_vec_info last = NULL; |
| stmt_vec_info stmt_vinfo; |
| |
| for (int i = 0; SLP_TREE_SCALAR_STMTS (node).iterate (i, &stmt_vinfo); i++) |
| { |
| stmt_vinfo = vect_orig_stmt (stmt_vinfo); |
| last = last ? get_later_stmt (stmt_vinfo, last) : stmt_vinfo; |
| } |
| |
| return last; |
| } |
| |
| /* Find the first stmt in NODE. */ |
| |
| stmt_vec_info |
| vect_find_first_scalar_stmt_in_slp (slp_tree node) |
| { |
| stmt_vec_info first = NULL; |
| stmt_vec_info stmt_vinfo; |
| |
| for (int i = 0; SLP_TREE_SCALAR_STMTS (node).iterate (i, &stmt_vinfo); i++) |
| { |
| stmt_vinfo = vect_orig_stmt (stmt_vinfo); |
| if (!first |
| || get_later_stmt (stmt_vinfo, first) == first) |
| first = stmt_vinfo; |
| } |
| |
| return first; |
| } |
| |
| /* Splits a group of stores, currently beginning at FIRST_VINFO, into |
| two groups: one (still beginning at FIRST_VINFO) of size GROUP1_SIZE |
| (also containing the first GROUP1_SIZE stmts, since stores are |
| consecutive), the second containing the remainder. |
| Return the first stmt in the second group. */ |
| |
| static stmt_vec_info |
| vect_split_slp_store_group (stmt_vec_info first_vinfo, unsigned group1_size) |
| { |
| gcc_assert (DR_GROUP_FIRST_ELEMENT (first_vinfo) == first_vinfo); |
| gcc_assert (group1_size > 0); |
| int group2_size = DR_GROUP_SIZE (first_vinfo) - group1_size; |
| gcc_assert (group2_size > 0); |
| DR_GROUP_SIZE (first_vinfo) = group1_size; |
| |
| stmt_vec_info stmt_info = first_vinfo; |
| for (unsigned i = group1_size; i > 1; i--) |
| { |
| stmt_info = DR_GROUP_NEXT_ELEMENT (stmt_info); |
| gcc_assert (DR_GROUP_GAP (stmt_info) == 1); |
| } |
| /* STMT is now the last element of the first group. */ |
| stmt_vec_info group2 = DR_GROUP_NEXT_ELEMENT (stmt_info); |
| DR_GROUP_NEXT_ELEMENT (stmt_info) = 0; |
| |
| DR_GROUP_SIZE (group2) = group2_size; |
| for (stmt_info = group2; stmt_info; |
| stmt_info = DR_GROUP_NEXT_ELEMENT (stmt_info)) |
| { |
| DR_GROUP_FIRST_ELEMENT (stmt_info) = group2; |
| gcc_assert (DR_GROUP_GAP (stmt_info) == 1); |
| } |
| |
| /* For the second group, the DR_GROUP_GAP is that before the original group, |
| plus skipping over the first vector. */ |
| DR_GROUP_GAP (group2) = DR_GROUP_GAP (first_vinfo) + group1_size; |
| |
| /* DR_GROUP_GAP of the first group now has to skip over the second group too. */ |
| DR_GROUP_GAP (first_vinfo) += group2_size; |
| |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_NOTE, vect_location, "Split group into %d and %d\n", |
| group1_size, group2_size); |
| |
| return group2; |
| } |
| |
| /* Calculate the unrolling factor for an SLP instance with GROUP_SIZE |
| statements and a vector of NUNITS elements. */ |
| |
| static poly_uint64 |
| calculate_unrolling_factor (poly_uint64 nunits, unsigned int group_size) |
| { |
| return exact_div (common_multiple (nunits, group_size), group_size); |
| } |
| |
| /* Helper that checks to see if a node is a load node. */ |
| |
| static inline bool |
| vect_is_slp_load_node (slp_tree root) |
| { |
| return SLP_TREE_DEF_TYPE (root) == vect_internal_def |
| && STMT_VINFO_GROUPED_ACCESS (SLP_TREE_REPRESENTATIVE (root)) |
| && DR_IS_READ (STMT_VINFO_DATA_REF (SLP_TREE_REPRESENTATIVE (root))); |
| } |
| |
| |
| /* Helper function of optimize_load_redistribution that performs the operation |
| recursively. */ |
| |
| static slp_tree |
| optimize_load_redistribution_1 (scalar_stmts_to_slp_tree_map_t *bst_map, |
| vec_info *vinfo, unsigned int group_size, |
| hash_map<slp_tree, slp_tree> *load_map, |
| slp_tree root) |
| { |
| if (slp_tree *leader = load_map->get (root)) |
| return *leader; |
| |
| slp_tree node; |
| unsigned i; |
| |
| /* For now, we don't know anything about externals so do not do anything. */ |
| if (!root || SLP_TREE_DEF_TYPE (root) != vect_internal_def) |
| return NULL; |
| else if (SLP_TREE_CODE (root) == VEC_PERM_EXPR) |
| { |
| /* First convert this node into a load node and add it to the leaves |
| list and flatten the permute from a lane to a load one. If it's |
| unneeded it will be elided later. */ |
| vec<stmt_vec_info> stmts; |
| stmts.create (SLP_TREE_LANES (root)); |
| lane_permutation_t lane_perm = SLP_TREE_LANE_PERMUTATION (root); |
| for (unsigned j = 0; j < lane_perm.length (); j++) |
| { |
| std::pair<unsigned, unsigned> perm = lane_perm[j]; |
| node = SLP_TREE_CHILDREN (root)[perm.first]; |
| |
| if (!vect_is_slp_load_node (node) |
| || SLP_TREE_CHILDREN (node).exists ()) |
| { |
| stmts.release (); |
| goto next; |
| } |
| |
| stmts.quick_push (SLP_TREE_SCALAR_STMTS (node)[perm.second]); |
| } |
| |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_NOTE, vect_location, |
| "converting stmts on permute node %p\n", root); |
| |
| bool *matches = XALLOCAVEC (bool, group_size); |
| poly_uint64 max_nunits = 1; |
| unsigned tree_size = 0, limit = 1; |
| node = vect_build_slp_tree (vinfo, stmts, group_size, &max_nunits, |
| matches, &limit, &tree_size, bst_map); |
| if (!node) |
| stmts.release (); |
| |
| load_map->put (root, node); |
| return node; |
| } |
| |
| next: |
| load_map->put (root, NULL); |
| |
| FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (root), i , node) |
| { |
| slp_tree value |
| = optimize_load_redistribution_1 (bst_map, vinfo, group_size, load_map, |
| node); |
| if (value) |
| { |
| SLP_TREE_REF_COUNT (value)++; |
| SLP_TREE_CHILDREN (root)[i] = value; |
| /* ??? We know the original leafs of the replaced nodes will |
| be referenced by bst_map, only the permutes created by |
| pattern matching are not. */ |
| if (SLP_TREE_REF_COUNT (node) == 1) |
| load_map->remove (node); |
| vect_free_slp_tree (node); |
| } |
| } |
| |
| return NULL; |
| } |
| |
| /* Temporary workaround for loads not being CSEd during SLP build. This |
| function will traverse the SLP tree rooted in ROOT for INSTANCE and find |
| VEC_PERM nodes that blend vectors from multiple nodes that all read from the |
| same DR such that the final operation is equal to a permuted load. Such |
| NODES are then directly converted into LOADS themselves. The nodes are |
| CSEd using BST_MAP. */ |
| |
| static void |
| optimize_load_redistribution (scalar_stmts_to_slp_tree_map_t *bst_map, |
| vec_info *vinfo, unsigned int group_size, |
| hash_map<slp_tree, slp_tree> *load_map, |
| slp_tree root) |
| { |
| slp_tree node; |
| unsigned i; |
| |
| FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (root), i , node) |
| { |
| slp_tree value |
| = optimize_load_redistribution_1 (bst_map, vinfo, group_size, load_map, |
| node); |
| if (value) |
| { |
| SLP_TREE_REF_COUNT (value)++; |
| SLP_TREE_CHILDREN (root)[i] = value; |
| /* ??? We know the original leafs of the replaced nodes will |
| be referenced by bst_map, only the permutes created by |
| pattern matching are not. */ |
| if (SLP_TREE_REF_COUNT (node) == 1) |
| load_map->remove (node); |
| vect_free_slp_tree (node); |
| } |
| } |
| } |
| |
| /* Helper function of vect_match_slp_patterns. |
| |
| Attempts to match patterns against the slp tree rooted in REF_NODE using |
| VINFO. Patterns are matched in post-order traversal. |
| |
| If matching is successful the value in REF_NODE is updated and returned, if |
| not then it is returned unchanged. */ |
| |
| static bool |
| vect_match_slp_patterns_2 (slp_tree *ref_node, vec_info *vinfo, |
| slp_tree_to_load_perm_map_t *perm_cache, |
| hash_set<slp_tree> *visited) |
| { |
| unsigned i; |
| slp_tree node = *ref_node; |
| bool found_p = false; |
| if (!node || visited->add (node)) |
| return false; |
| |
| slp_tree child; |
| FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node), i, child) |
| found_p |= vect_match_slp_patterns_2 (&SLP_TREE_CHILDREN (node)[i], |
| vinfo, perm_cache, visited); |
| |
| for (unsigned x = 0; x < num__slp_patterns; x++) |
| { |
| vect_pattern *pattern = slp_patterns[x] (perm_cache, ref_node); |
| if (pattern) |
| { |
| pattern->build (vinfo); |
| delete pattern; |
| found_p = true; |
| } |
| } |
| |
| return found_p; |
| } |
| |
| /* Applies pattern matching to the given SLP tree rooted in REF_NODE using |
| vec_info VINFO. |
| |
| The modified tree is returned. Patterns are tried in order and multiple |
| patterns may match. */ |
| |
| static bool |
| vect_match_slp_patterns (slp_instance instance, vec_info *vinfo, |
| hash_set<slp_tree> *visited, |
| slp_tree_to_load_perm_map_t *perm_cache) |
| { |
| DUMP_VECT_SCOPE ("vect_match_slp_patterns"); |
| slp_tree *ref_node = &SLP_INSTANCE_TREE (instance); |
| |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_NOTE, vect_location, |
| "Analyzing SLP tree %p for patterns\n", |
| SLP_INSTANCE_TREE (instance)); |
| |
| return vect_match_slp_patterns_2 (ref_node, vinfo, perm_cache, visited); |
| } |
| |
| /* STMT_INFO is a store group of size GROUP_SIZE that we are considering |
| splitting into two, with the first split group having size NEW_GROUP_SIZE. |
| Return true if we could use IFN_STORE_LANES instead and if that appears |
| to be the better approach. */ |
| |
| static bool |
| vect_slp_prefer_store_lanes_p (vec_info *vinfo, stmt_vec_info stmt_info, |
| unsigned int group_size, |
| unsigned int new_group_size) |
| { |
| tree scalar_type = TREE_TYPE (DR_REF (STMT_VINFO_DATA_REF (stmt_info))); |
| tree vectype = get_vectype_for_scalar_type (vinfo, scalar_type); |
| if (!vectype) |
| return false; |
| /* Allow the split if one of the two new groups would operate on full |
| vectors *within* rather than across one scalar loop iteration. |
| This is purely a heuristic, but it should work well for group |
| sizes of 3 and 4, where the possible splits are: |
| |
| 3->2+1: OK if the vector has exactly two elements |
| 4->2+2: Likewise |
| 4->3+1: Less clear-cut. */ |
| if (multiple_p (group_size - new_group_size, TYPE_VECTOR_SUBPARTS (vectype)) |
| || multiple_p (new_group_size, TYPE_VECTOR_SUBPARTS (vectype))) |
| return false; |
| return vect_store_lanes_supported (vectype, group_size, false); |
| } |
| |
| /* Analyze an SLP instance starting from a group of grouped stores. Call |
| vect_build_slp_tree to build a tree of packed stmts if possible. |
| Return FALSE if it's impossible to SLP any stmt in the loop. */ |
| |
| static bool |
| vect_analyze_slp_instance (vec_info *vinfo, |
| scalar_stmts_to_slp_tree_map_t *bst_map, |
| stmt_vec_info stmt_info, slp_instance_kind kind, |
| unsigned max_tree_size, unsigned *limit); |
| |
| /* Analyze an SLP instance starting from SCALAR_STMTS which are a group |
| of KIND. Return true if successful. */ |
| |
| static bool |
| vect_build_slp_instance (vec_info *vinfo, |
| slp_instance_kind kind, |
| vec<stmt_vec_info> &scalar_stmts, |
| vec<stmt_vec_info> &root_stmt_infos, |
| unsigned max_tree_size, unsigned *limit, |
| scalar_stmts_to_slp_tree_map_t *bst_map, |
| /* ??? We need stmt_info for group splitting. */ |
| stmt_vec_info stmt_info_) |
| { |
| if (dump_enabled_p ()) |
| { |
| dump_printf_loc (MSG_NOTE, vect_location, |
| "Starting SLP discovery for\n"); |
| for (unsigned i = 0; i < scalar_stmts.length (); ++i) |
| dump_printf_loc (MSG_NOTE, vect_location, |
| " %G", scalar_stmts[i]->stmt); |
| } |
| |
| /* Build the tree for the SLP instance. */ |
| unsigned int group_size = scalar_stmts.length (); |
| bool *matches = XALLOCAVEC (bool, group_size); |
| poly_uint64 max_nunits = 1; |
| unsigned tree_size = 0; |
| unsigned i; |
| slp_tree node = vect_build_slp_tree (vinfo, scalar_stmts, group_size, |
| &max_nunits, matches, limit, |
| &tree_size, bst_map); |
| if (node != NULL) |
| { |
| /* Calculate the unrolling factor based on the smallest type. */ |
| poly_uint64 unrolling_factor |
| = calculate_unrolling_factor (max_nunits, group_size); |
| |
| if (maybe_ne (unrolling_factor, 1U) |
| && is_a <bb_vec_info> (vinfo)) |
| { |
| unsigned HOST_WIDE_INT const_max_nunits; |
| if (!max_nunits.is_constant (&const_max_nunits) |
| || const_max_nunits > group_size) |
| { |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, |
| "Build SLP failed: store group " |
| "size not a multiple of the vector size " |
| "in basic block SLP\n"); |
| vect_free_slp_tree (node); |
| return false; |
| } |
| /* Fatal mismatch. */ |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_NOTE, vect_location, |
| "SLP discovery succeeded but node needs " |
| "splitting\n"); |
|
|