| Index: gcc/gcc/tree-vect-analyze.c
|
| diff --git a/gcc/gcc/tree-vect-analyze.c b/gcc/gcc/tree-vect-analyze.c
|
| deleted file mode 100644
|
| index 8c55fa737619915329689fe7ec8f6d72aba78e8b..0000000000000000000000000000000000000000
|
| --- a/gcc/gcc/tree-vect-analyze.c
|
| +++ /dev/null
|
| @@ -1,4754 +0,0 @@
|
| -/* Analysis Utilities for Loop Vectorization.
|
| - Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008 Free Software
|
| - Foundation, Inc.
|
| - Contributed by Dorit Naishlos <dorit@il.ibm.com>
|
| -
|
| -This file is part of GCC.
|
| -
|
| -GCC is free software; you can redistribute it and/or modify it under
|
| -the terms of the GNU General Public License as published by the Free
|
| -Software Foundation; either version 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 "tm.h"
|
| -#include "ggc.h"
|
| -#include "tree.h"
|
| -#include "target.h"
|
| -#include "basic-block.h"
|
| -#include "diagnostic.h"
|
| -#include "tree-flow.h"
|
| -#include "tree-dump.h"
|
| -#include "timevar.h"
|
| -#include "cfgloop.h"
|
| -#include "expr.h"
|
| -#include "optabs.h"
|
| -#include "params.h"
|
| -#include "tree-chrec.h"
|
| -#include "tree-data-ref.h"
|
| -#include "tree-scalar-evolution.h"
|
| -#include "tree-vectorizer.h"
|
| -#include "toplev.h"
|
| -#include "recog.h"
|
| -
|
| -static bool vect_can_advance_ivs_p (loop_vec_info);
|
| -
|
| -/* Return the smallest scalar part of STMT.
|
| - This is used to determine the vectype of the stmt. We generally set the
|
| - vectype according to the type of the result (lhs). For stmts whose
|
| - result-type is different than the type of the arguments (e.g., demotion,
|
| - promotion), vectype will be reset appropriately (later). Note that we have
|
| - to visit the smallest datatype in this function, because that determines the
|
| - VF. If the smallest datatype in the loop is present only as the rhs of a
|
| - promotion operation - we'd miss it.
|
| - Such a case, where a variable of this datatype does not appear in the lhs
|
| - anywhere in the loop, can only occur if it's an invariant: e.g.:
|
| - 'int_x = (int) short_inv', which we'd expect to have been optimized away by
|
| - invariant motion. However, we cannot rely on invariant motion to always take
|
| - invariants out of the loop, and so in the case of promotion we also have to
|
| - check the rhs.
|
| - LHS_SIZE_UNIT and RHS_SIZE_UNIT contain the sizes of the corresponding
|
| - types. */
|
| -
|
| -tree
|
| -vect_get_smallest_scalar_type (gimple stmt, HOST_WIDE_INT *lhs_size_unit,
|
| - HOST_WIDE_INT *rhs_size_unit)
|
| -{
|
| - tree scalar_type = gimple_expr_type (stmt);
|
| - HOST_WIDE_INT lhs, rhs;
|
| -
|
| - lhs = rhs = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (scalar_type));
|
| -
|
| - if (is_gimple_assign (stmt)
|
| - && (gimple_assign_cast_p (stmt)
|
| - || gimple_assign_rhs_code (stmt) == WIDEN_MULT_EXPR
|
| - || gimple_assign_rhs_code (stmt) == FLOAT_EXPR))
|
| - {
|
| - tree rhs_type = TREE_TYPE (gimple_assign_rhs1 (stmt));
|
| -
|
| - rhs = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (rhs_type));
|
| - if (rhs < lhs)
|
| - scalar_type = rhs_type;
|
| - }
|
| -
|
| - *lhs_size_unit = lhs;
|
| - *rhs_size_unit = rhs;
|
| - return scalar_type;
|
| -}
|
| -
|
| -
|
| -/* Function vect_determine_vectorization_factor
|
| -
|
| - Determine the vectorization factor (VF). VF is the number of data elements
|
| - that are operated upon in parallel in a single iteration of the vectorized
|
| - loop. For example, when vectorizing a loop that operates on 4byte elements,
|
| - on a target with vector size (VS) 16byte, the VF is set to 4, since 4
|
| - elements can fit in a single vector register.
|
| -
|
| - We currently support vectorization of loops in which all types operated upon
|
| - are of the same size. Therefore this function currently sets VF according to
|
| - the size of the types operated upon, and fails if there are multiple sizes
|
| - in the loop.
|
| -
|
| - VF is also the factor by which the loop iterations are strip-mined, e.g.:
|
| - original loop:
|
| - for (i=0; i<N; i++){
|
| - a[i] = b[i] + c[i];
|
| - }
|
| -
|
| - vectorized loop:
|
| - for (i=0; i<N; i+=VF){
|
| - a[i:VF] = b[i:VF] + c[i:VF];
|
| - }
|
| -*/
|
| -
|
| -static bool
|
| -vect_determine_vectorization_factor (loop_vec_info loop_vinfo)
|
| -{
|
| - struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
|
| - basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo);
|
| - int nbbs = loop->num_nodes;
|
| - gimple_stmt_iterator si;
|
| - unsigned int vectorization_factor = 0;
|
| - tree scalar_type;
|
| - gimple phi;
|
| - tree vectype;
|
| - unsigned int nunits;
|
| - stmt_vec_info stmt_info;
|
| - int i;
|
| - HOST_WIDE_INT dummy;
|
| -
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "=== vect_determine_vectorization_factor ===");
|
| -
|
| - for (i = 0; i < nbbs; i++)
|
| - {
|
| - basic_block bb = bbs[i];
|
| -
|
| - for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
|
| - {
|
| - phi = gsi_stmt (si);
|
| - stmt_info = vinfo_for_stmt (phi);
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - {
|
| - fprintf (vect_dump, "==> examining phi: ");
|
| - print_gimple_stmt (vect_dump, phi, 0, TDF_SLIM);
|
| - }
|
| -
|
| - gcc_assert (stmt_info);
|
| -
|
| - if (STMT_VINFO_RELEVANT_P (stmt_info))
|
| - {
|
| - gcc_assert (!STMT_VINFO_VECTYPE (stmt_info));
|
| - scalar_type = TREE_TYPE (PHI_RESULT (phi));
|
| -
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - {
|
| - fprintf (vect_dump, "get vectype for scalar type: ");
|
| - print_generic_expr (vect_dump, scalar_type, TDF_SLIM);
|
| - }
|
| -
|
| - vectype = get_vectype_for_scalar_type (scalar_type);
|
| - if (!vectype)
|
| - {
|
| - if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
|
| - {
|
| - fprintf (vect_dump,
|
| - "not vectorized: unsupported data-type ");
|
| - print_generic_expr (vect_dump, scalar_type, TDF_SLIM);
|
| - }
|
| - return false;
|
| - }
|
| - STMT_VINFO_VECTYPE (stmt_info) = vectype;
|
| -
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - {
|
| - fprintf (vect_dump, "vectype: ");
|
| - print_generic_expr (vect_dump, vectype, TDF_SLIM);
|
| - }
|
| -
|
| - nunits = TYPE_VECTOR_SUBPARTS (vectype);
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "nunits = %d", nunits);
|
| -
|
| - if (!vectorization_factor
|
| - || (nunits > vectorization_factor))
|
| - vectorization_factor = nunits;
|
| - }
|
| - }
|
| -
|
| - for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
|
| - {
|
| - gimple stmt = gsi_stmt (si);
|
| - stmt_info = vinfo_for_stmt (stmt);
|
| -
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - {
|
| - fprintf (vect_dump, "==> examining statement: ");
|
| - print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
|
| - }
|
| -
|
| - if (gimple_has_volatile_ops (stmt))
|
| - {
|
| - if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
|
| - fprintf (vect_dump, "not vectorized: stmt has volatile"
|
| - " operands");
|
| -
|
| - return false;
|
| - }
|
| -
|
| - gcc_assert (stmt_info);
|
| -
|
| - /* skip stmts which do not need to be vectorized. */
|
| - if (!STMT_VINFO_RELEVANT_P (stmt_info)
|
| - && !STMT_VINFO_LIVE_P (stmt_info))
|
| - {
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "skip.");
|
| - continue;
|
| - }
|
| -
|
| - if (gimple_get_lhs (stmt) == NULL_TREE)
|
| - {
|
| - if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
|
| - {
|
| - fprintf (vect_dump, "not vectorized: irregular stmt.");
|
| - print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
|
| - }
|
| - return false;
|
| - }
|
| -
|
| - if (VECTOR_MODE_P (TYPE_MODE (gimple_expr_type (stmt))))
|
| - {
|
| - if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
|
| - {
|
| - fprintf (vect_dump, "not vectorized: vector stmt in loop:");
|
| - print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
|
| - }
|
| - return false;
|
| - }
|
| -
|
| - if (STMT_VINFO_VECTYPE (stmt_info))
|
| - {
|
| - /* The only case when a vectype had been already set is for stmts
|
| - that contain a dataref, or for "pattern-stmts" (stmts generated
|
| - by the vectorizer to represent/replace a certain idiom). */
|
| - gcc_assert (STMT_VINFO_DATA_REF (stmt_info)
|
| - || is_pattern_stmt_p (stmt_info));
|
| - vectype = STMT_VINFO_VECTYPE (stmt_info);
|
| - }
|
| - else
|
| - {
|
| -
|
| - gcc_assert (! STMT_VINFO_DATA_REF (stmt_info)
|
| - && !is_pattern_stmt_p (stmt_info));
|
| -
|
| - scalar_type = vect_get_smallest_scalar_type (stmt, &dummy,
|
| - &dummy);
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - {
|
| - fprintf (vect_dump, "get vectype for scalar type: ");
|
| - print_generic_expr (vect_dump, scalar_type, TDF_SLIM);
|
| - }
|
| -
|
| - vectype = get_vectype_for_scalar_type (scalar_type);
|
| - if (!vectype)
|
| - {
|
| - if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
|
| - {
|
| - fprintf (vect_dump,
|
| - "not vectorized: unsupported data-type ");
|
| - print_generic_expr (vect_dump, scalar_type, TDF_SLIM);
|
| - }
|
| - return false;
|
| - }
|
| - STMT_VINFO_VECTYPE (stmt_info) = vectype;
|
| - }
|
| -
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - {
|
| - fprintf (vect_dump, "vectype: ");
|
| - print_generic_expr (vect_dump, vectype, TDF_SLIM);
|
| - }
|
| -
|
| - nunits = TYPE_VECTOR_SUBPARTS (vectype);
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "nunits = %d", nunits);
|
| -
|
| - if (!vectorization_factor
|
| - || (nunits > vectorization_factor))
|
| - vectorization_factor = nunits;
|
| -
|
| - }
|
| - }
|
| -
|
| - /* TODO: Analyze cost. Decide if worth while to vectorize. */
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "vectorization factor = %d", vectorization_factor);
|
| - if (vectorization_factor <= 1)
|
| - {
|
| - if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
|
| - fprintf (vect_dump, "not vectorized: unsupported data-type");
|
| - return false;
|
| - }
|
| - LOOP_VINFO_VECT_FACTOR (loop_vinfo) = vectorization_factor;
|
| -
|
| - return true;
|
| -}
|
| -
|
| -
|
| -/* SLP costs are calculated according to SLP instance unrolling factor (i.e.,
|
| - the number of created vector stmts depends on the unrolling factor). However,
|
| - the actual number of vector stmts for every SLP node depends on VF which is
|
| - set later in vect_analyze_operations(). Hence, SLP costs should be updated.
|
| - In this function we assume that the inside costs calculated in
|
| - vect_model_xxx_cost are linear in ncopies. */
|
| -
|
| -static void
|
| -vect_update_slp_costs_according_to_vf (loop_vec_info loop_vinfo)
|
| -{
|
| - unsigned int i, vf = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
|
| - VEC (slp_instance, heap) *slp_instances = LOOP_VINFO_SLP_INSTANCES (loop_vinfo);
|
| - slp_instance instance;
|
| -
|
| - if (vect_print_dump_info (REPORT_SLP))
|
| - fprintf (vect_dump, "=== vect_update_slp_costs_according_to_vf ===");
|
| -
|
| - for (i = 0; VEC_iterate (slp_instance, slp_instances, i, instance); i++)
|
| - /* We assume that costs are linear in ncopies. */
|
| - SLP_INSTANCE_INSIDE_OF_LOOP_COST (instance) *= vf
|
| - / SLP_INSTANCE_UNROLLING_FACTOR (instance);
|
| -}
|
| -
|
| -
|
| -/* Function vect_analyze_operations.
|
| -
|
| - Scan the loop stmts and make sure they are all vectorizable. */
|
| -
|
| -static bool
|
| -vect_analyze_operations (loop_vec_info loop_vinfo)
|
| -{
|
| - struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
|
| - basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo);
|
| - int nbbs = loop->num_nodes;
|
| - gimple_stmt_iterator si;
|
| - unsigned int vectorization_factor = 0;
|
| - int i;
|
| - bool ok;
|
| - gimple phi;
|
| - stmt_vec_info stmt_info;
|
| - bool need_to_vectorize = false;
|
| - int min_profitable_iters;
|
| - int min_scalar_loop_bound;
|
| - unsigned int th;
|
| - bool only_slp_in_loop = true;
|
| -
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "=== vect_analyze_operations ===");
|
| -
|
| - gcc_assert (LOOP_VINFO_VECT_FACTOR (loop_vinfo));
|
| - vectorization_factor = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
|
| -
|
| - for (i = 0; i < nbbs; i++)
|
| - {
|
| - basic_block bb = bbs[i];
|
| -
|
| - for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
|
| - {
|
| - phi = gsi_stmt (si);
|
| - ok = true;
|
| -
|
| - stmt_info = vinfo_for_stmt (phi);
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - {
|
| - fprintf (vect_dump, "examining phi: ");
|
| - print_gimple_stmt (vect_dump, phi, 0, TDF_SLIM);
|
| - }
|
| -
|
| - if (! is_loop_header_bb_p (bb))
|
| - {
|
| - /* inner-loop loop-closed exit phi in outer-loop vectorization
|
| - (i.e. a phi in the tail of the outer-loop).
|
| - FORNOW: we currently don't support the case that these phis
|
| - are not used in the outerloop, cause this case requires
|
| - to actually do something here. */
|
| - if (!STMT_VINFO_RELEVANT_P (stmt_info)
|
| - || STMT_VINFO_LIVE_P (stmt_info))
|
| - {
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump,
|
| - "Unsupported loop-closed phi in outer-loop.");
|
| - return false;
|
| - }
|
| - continue;
|
| - }
|
| -
|
| - gcc_assert (stmt_info);
|
| -
|
| - if (STMT_VINFO_LIVE_P (stmt_info))
|
| - {
|
| - /* FORNOW: not yet supported. */
|
| - if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
|
| - fprintf (vect_dump, "not vectorized: value used after loop.");
|
| - return false;
|
| - }
|
| -
|
| - if (STMT_VINFO_RELEVANT (stmt_info) == vect_used_in_loop
|
| - && STMT_VINFO_DEF_TYPE (stmt_info) != vect_induction_def)
|
| - {
|
| - /* A scalar-dependence cycle that we don't support. */
|
| - if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
|
| - fprintf (vect_dump, "not vectorized: scalar dependence cycle.");
|
| - return false;
|
| - }
|
| -
|
| - if (STMT_VINFO_RELEVANT_P (stmt_info))
|
| - {
|
| - need_to_vectorize = true;
|
| - if (STMT_VINFO_DEF_TYPE (stmt_info) == vect_induction_def)
|
| - ok = vectorizable_induction (phi, NULL, NULL);
|
| - }
|
| -
|
| - if (!ok)
|
| - {
|
| - if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
|
| - {
|
| - fprintf (vect_dump,
|
| - "not vectorized: relevant phi not supported: ");
|
| - print_gimple_stmt (vect_dump, phi, 0, TDF_SLIM);
|
| - }
|
| - return false;
|
| - }
|
| - }
|
| -
|
| - for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
|
| - {
|
| - gimple stmt = gsi_stmt (si);
|
| - stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
|
| - enum vect_relevant relevance = STMT_VINFO_RELEVANT (stmt_info);
|
| -
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - {
|
| - fprintf (vect_dump, "==> examining statement: ");
|
| - print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
|
| - }
|
| -
|
| - gcc_assert (stmt_info);
|
| -
|
| - /* skip stmts which do not need to be vectorized.
|
| - this is expected to include:
|
| - - the COND_EXPR which is the loop exit condition
|
| - - any LABEL_EXPRs in the loop
|
| - - computations that are used only for array indexing or loop
|
| - control */
|
| -
|
| - if (!STMT_VINFO_RELEVANT_P (stmt_info)
|
| - && !STMT_VINFO_LIVE_P (stmt_info))
|
| - {
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "irrelevant.");
|
| - continue;
|
| - }
|
| -
|
| - switch (STMT_VINFO_DEF_TYPE (stmt_info))
|
| - {
|
| - case vect_loop_def:
|
| - break;
|
| -
|
| - case vect_reduction_def:
|
| - gcc_assert (relevance == vect_used_in_outer
|
| - || relevance == vect_used_in_outer_by_reduction
|
| - || relevance == vect_unused_in_loop);
|
| - break;
|
| -
|
| - case vect_induction_def:
|
| - case vect_constant_def:
|
| - case vect_invariant_def:
|
| - case vect_unknown_def_type:
|
| - default:
|
| - gcc_unreachable ();
|
| - }
|
| -
|
| - if (STMT_VINFO_RELEVANT_P (stmt_info))
|
| - {
|
| - gcc_assert (!VECTOR_MODE_P (TYPE_MODE (gimple_expr_type (stmt))));
|
| - gcc_assert (STMT_VINFO_VECTYPE (stmt_info));
|
| - need_to_vectorize = true;
|
| - }
|
| -
|
| - ok = true;
|
| - if (STMT_VINFO_RELEVANT_P (stmt_info)
|
| - || STMT_VINFO_DEF_TYPE (stmt_info) == vect_reduction_def)
|
| - ok = (vectorizable_type_promotion (stmt, NULL, NULL, NULL)
|
| - || vectorizable_type_demotion (stmt, NULL, NULL, NULL)
|
| - || vectorizable_conversion (stmt, NULL, NULL, NULL)
|
| - || vectorizable_operation (stmt, NULL, NULL, NULL)
|
| - || vectorizable_assignment (stmt, NULL, NULL, NULL)
|
| - || vectorizable_load (stmt, NULL, NULL, NULL, NULL)
|
| - || vectorizable_call (stmt, NULL, NULL)
|
| - || vectorizable_store (stmt, NULL, NULL, NULL)
|
| - || vectorizable_condition (stmt, NULL, NULL)
|
| - || vectorizable_reduction (stmt, NULL, NULL));
|
| -
|
| - if (!ok)
|
| - {
|
| - if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
|
| - {
|
| - fprintf (vect_dump, "not vectorized: relevant stmt not ");
|
| - fprintf (vect_dump, "supported: ");
|
| - print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
|
| - }
|
| - return false;
|
| - }
|
| -
|
| - /* Stmts that are (also) "live" (i.e. - that are used out of the loop)
|
| - need extra handling, except for vectorizable reductions. */
|
| - if (STMT_VINFO_LIVE_P (stmt_info)
|
| - && STMT_VINFO_TYPE (stmt_info) != reduc_vec_info_type)
|
| - ok = vectorizable_live_operation (stmt, NULL, NULL);
|
| -
|
| - if (!ok)
|
| - {
|
| - if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
|
| - {
|
| - fprintf (vect_dump, "not vectorized: live stmt not ");
|
| - fprintf (vect_dump, "supported: ");
|
| - print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
|
| - }
|
| - return false;
|
| - }
|
| -
|
| - if (!PURE_SLP_STMT (stmt_info))
|
| - {
|
| - /* STMT needs loop-based vectorization. */
|
| - only_slp_in_loop = false;
|
| -
|
| - /* Groups of strided accesses whose size is not a power of 2 are
|
| - not vectorizable yet using loop-vectorization. Therefore, if
|
| - this stmt feeds non-SLP-able stmts (i.e., this stmt has to be
|
| - both SLPed and loop-based vectorized), the loop cannot be
|
| - vectorized. */
|
| - if (STMT_VINFO_STRIDED_ACCESS (stmt_info)
|
| - && exact_log2 (DR_GROUP_SIZE (vinfo_for_stmt (
|
| - DR_GROUP_FIRST_DR (stmt_info)))) == -1)
|
| - {
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - {
|
| - fprintf (vect_dump, "not vectorized: the size of group "
|
| - "of strided accesses is not a power of 2");
|
| - print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
|
| - }
|
| - return false;
|
| - }
|
| - }
|
| - } /* stmts in bb */
|
| - } /* bbs */
|
| -
|
| - /* All operations in the loop are either irrelevant (deal with loop
|
| - control, or dead), or only used outside the loop and can be moved
|
| - out of the loop (e.g. invariants, inductions). The loop can be
|
| - optimized away by scalar optimizations. We're better off not
|
| - touching this loop. */
|
| - if (!need_to_vectorize)
|
| - {
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump,
|
| - "All the computation can be taken out of the loop.");
|
| - if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
|
| - fprintf (vect_dump,
|
| - "not vectorized: redundant loop. no profit to vectorize.");
|
| - return false;
|
| - }
|
| -
|
| - /* If all the stmts in the loop can be SLPed, we perform only SLP, and
|
| - vectorization factor of the loop is the unrolling factor required by the
|
| - SLP instances. If that unrolling factor is 1, we say, that we perform
|
| - pure SLP on loop - cross iteration parallelism is not exploited. */
|
| - if (only_slp_in_loop)
|
| - vectorization_factor = LOOP_VINFO_SLP_UNROLLING_FACTOR (loop_vinfo);
|
| - else
|
| - vectorization_factor = least_common_multiple (vectorization_factor,
|
| - LOOP_VINFO_SLP_UNROLLING_FACTOR (loop_vinfo));
|
| -
|
| - LOOP_VINFO_VECT_FACTOR (loop_vinfo) = vectorization_factor;
|
| -
|
| - if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
|
| - && vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump,
|
| - "vectorization_factor = %d, niters = " HOST_WIDE_INT_PRINT_DEC,
|
| - vectorization_factor, LOOP_VINFO_INT_NITERS (loop_vinfo));
|
| -
|
| - if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
|
| - && (LOOP_VINFO_INT_NITERS (loop_vinfo) < vectorization_factor))
|
| - {
|
| - if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
|
| - fprintf (vect_dump, "not vectorized: iteration count too small.");
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump,"not vectorized: iteration count smaller than "
|
| - "vectorization factor.");
|
| - return false;
|
| - }
|
| -
|
| - /* Analyze cost. Decide if worth while to vectorize. */
|
| -
|
| - /* Once VF is set, SLP costs should be updated since the number of created
|
| - vector stmts depends on VF. */
|
| - vect_update_slp_costs_according_to_vf (loop_vinfo);
|
| -
|
| - min_profitable_iters = vect_estimate_min_profitable_iters (loop_vinfo);
|
| - LOOP_VINFO_COST_MODEL_MIN_ITERS (loop_vinfo) = min_profitable_iters;
|
| -
|
| - if (min_profitable_iters < 0)
|
| - {
|
| - if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
|
| - fprintf (vect_dump, "not vectorized: vectorization not profitable.");
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "not vectorized: vector version will never be "
|
| - "profitable.");
|
| - return false;
|
| - }
|
| -
|
| - min_scalar_loop_bound = ((PARAM_VALUE (PARAM_MIN_VECT_LOOP_BOUND)
|
| - * vectorization_factor) - 1);
|
| -
|
| - /* Use the cost model only if it is more conservative than user specified
|
| - threshold. */
|
| -
|
| - th = (unsigned) min_scalar_loop_bound;
|
| - if (min_profitable_iters
|
| - && (!min_scalar_loop_bound
|
| - || min_profitable_iters > min_scalar_loop_bound))
|
| - th = (unsigned) min_profitable_iters;
|
| -
|
| - if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
|
| - && LOOP_VINFO_INT_NITERS (loop_vinfo) <= th)
|
| - {
|
| - if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
|
| - fprintf (vect_dump, "not vectorized: vectorization not "
|
| - "profitable.");
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "not vectorized: iteration count smaller than "
|
| - "user specified loop bound parameter or minimum "
|
| - "profitable iterations (whichever is more conservative).");
|
| - return false;
|
| - }
|
| -
|
| - if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
|
| - || LOOP_VINFO_INT_NITERS (loop_vinfo) % vectorization_factor != 0
|
| - || LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo))
|
| - {
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "epilog loop required.");
|
| - if (!vect_can_advance_ivs_p (loop_vinfo))
|
| - {
|
| - if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
|
| - fprintf (vect_dump,
|
| - "not vectorized: can't create epilog loop 1.");
|
| - return false;
|
| - }
|
| - if (!slpeel_can_duplicate_loop_p (loop, single_exit (loop)))
|
| - {
|
| - if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
|
| - fprintf (vect_dump,
|
| - "not vectorized: can't create epilog loop 2.");
|
| - return false;
|
| - }
|
| - }
|
| -
|
| - return true;
|
| -}
|
| -
|
| -
|
| -/* Function exist_non_indexing_operands_for_use_p
|
| -
|
| - USE is one of the uses attached to STMT. Check if USE is
|
| - used in STMT for anything other than indexing an array. */
|
| -
|
| -static bool
|
| -exist_non_indexing_operands_for_use_p (tree use, gimple stmt)
|
| -{
|
| - tree operand;
|
| - stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
|
| -
|
| - /* USE corresponds to some operand in STMT. If there is no data
|
| - reference in STMT, then any operand that corresponds to USE
|
| - is not indexing an array. */
|
| - if (!STMT_VINFO_DATA_REF (stmt_info))
|
| - return true;
|
| -
|
| - /* STMT has a data_ref. FORNOW this means that its of one of
|
| - the following forms:
|
| - -1- ARRAY_REF = var
|
| - -2- var = ARRAY_REF
|
| - (This should have been verified in analyze_data_refs).
|
| -
|
| - 'var' in the second case corresponds to a def, not a use,
|
| - so USE cannot correspond to any operands that are not used
|
| - for array indexing.
|
| -
|
| - Therefore, all we need to check is if STMT falls into the
|
| - first case, and whether var corresponds to USE. */
|
| -
|
| - if (TREE_CODE (gimple_assign_lhs (stmt)) == SSA_NAME)
|
| - return false;
|
| -
|
| - if (!gimple_assign_copy_p (stmt))
|
| - return false;
|
| - operand = gimple_assign_rhs1 (stmt);
|
| -
|
| - if (TREE_CODE (operand) != SSA_NAME)
|
| - return false;
|
| -
|
| - if (operand == use)
|
| - return true;
|
| -
|
| - return false;
|
| -}
|
| -
|
| -
|
| -/* Function vect_analyze_scalar_cycles_1.
|
| -
|
| - Examine the cross iteration def-use cycles of scalar variables
|
| - in LOOP. LOOP_VINFO represents the loop that is now being
|
| - considered for vectorization (can be LOOP, or an outer-loop
|
| - enclosing LOOP). */
|
| -
|
| -static void
|
| -vect_analyze_scalar_cycles_1 (loop_vec_info loop_vinfo, struct loop *loop)
|
| -{
|
| - basic_block bb = loop->header;
|
| - tree dumy;
|
| - VEC(gimple,heap) *worklist = VEC_alloc (gimple, heap, 64);
|
| - gimple_stmt_iterator gsi;
|
| -
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "=== vect_analyze_scalar_cycles ===");
|
| -
|
| - /* First - identify all inductions. */
|
| - for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
|
| - {
|
| - gimple phi = gsi_stmt (gsi);
|
| - tree access_fn = NULL;
|
| - tree def = PHI_RESULT (phi);
|
| - stmt_vec_info stmt_vinfo = vinfo_for_stmt (phi);
|
| -
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - {
|
| - fprintf (vect_dump, "Analyze phi: ");
|
| - print_gimple_stmt (vect_dump, phi, 0, TDF_SLIM);
|
| - }
|
| -
|
| - /* Skip virtual phi's. The data dependences that are associated with
|
| - virtual defs/uses (i.e., memory accesses) are analyzed elsewhere. */
|
| - if (!is_gimple_reg (SSA_NAME_VAR (def)))
|
| - continue;
|
| -
|
| - STMT_VINFO_DEF_TYPE (stmt_vinfo) = vect_unknown_def_type;
|
| -
|
| - /* Analyze the evolution function. */
|
| - access_fn = analyze_scalar_evolution (loop, def);
|
| - if (access_fn && vect_print_dump_info (REPORT_DETAILS))
|
| - {
|
| - fprintf (vect_dump, "Access function of PHI: ");
|
| - print_generic_expr (vect_dump, access_fn, TDF_SLIM);
|
| - }
|
| -
|
| - if (!access_fn
|
| - || !vect_is_simple_iv_evolution (loop->num, access_fn, &dumy, &dumy))
|
| - {
|
| - VEC_safe_push (gimple, heap, worklist, phi);
|
| - continue;
|
| - }
|
| -
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "Detected induction.");
|
| - STMT_VINFO_DEF_TYPE (stmt_vinfo) = vect_induction_def;
|
| - }
|
| -
|
| -
|
| - /* Second - identify all reductions. */
|
| - while (VEC_length (gimple, worklist) > 0)
|
| - {
|
| - gimple phi = VEC_pop (gimple, worklist);
|
| - tree def = PHI_RESULT (phi);
|
| - stmt_vec_info stmt_vinfo = vinfo_for_stmt (phi);
|
| - gimple reduc_stmt;
|
| -
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - {
|
| - fprintf (vect_dump, "Analyze phi: ");
|
| - print_gimple_stmt (vect_dump, phi, 0, TDF_SLIM);
|
| - }
|
| -
|
| - gcc_assert (is_gimple_reg (SSA_NAME_VAR (def)));
|
| - gcc_assert (STMT_VINFO_DEF_TYPE (stmt_vinfo) == vect_unknown_def_type);
|
| -
|
| - reduc_stmt = vect_is_simple_reduction (loop_vinfo, phi);
|
| - if (reduc_stmt)
|
| - {
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "Detected reduction.");
|
| - STMT_VINFO_DEF_TYPE (stmt_vinfo) = vect_reduction_def;
|
| - STMT_VINFO_DEF_TYPE (vinfo_for_stmt (reduc_stmt)) =
|
| - vect_reduction_def;
|
| - }
|
| - else
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "Unknown def-use cycle pattern.");
|
| - }
|
| -
|
| - VEC_free (gimple, heap, worklist);
|
| - return;
|
| -}
|
| -
|
| -
|
| -/* Function vect_analyze_scalar_cycles.
|
| -
|
| - Examine the cross iteration def-use cycles of scalar variables, by
|
| - analyzing the loop-header PHIs of scalar variables; Classify each
|
| - cycle as one of the following: invariant, induction, reduction, unknown.
|
| - We do that for the loop represented by LOOP_VINFO, and also to its
|
| - inner-loop, if exists.
|
| - Examples for scalar cycles:
|
| -
|
| - Example1: reduction:
|
| -
|
| - loop1:
|
| - for (i=0; i<N; i++)
|
| - sum += a[i];
|
| -
|
| - Example2: induction:
|
| -
|
| - loop2:
|
| - for (i=0; i<N; i++)
|
| - a[i] = i; */
|
| -
|
| -static void
|
| -vect_analyze_scalar_cycles (loop_vec_info loop_vinfo)
|
| -{
|
| - struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
|
| -
|
| - vect_analyze_scalar_cycles_1 (loop_vinfo, loop);
|
| -
|
| - /* When vectorizing an outer-loop, the inner-loop is executed sequentially.
|
| - Reductions in such inner-loop therefore have different properties than
|
| - the reductions in the nest that gets vectorized:
|
| - 1. When vectorized, they are executed in the same order as in the original
|
| - scalar loop, so we can't change the order of computation when
|
| - vectorizing them.
|
| - 2. FIXME: Inner-loop reductions can be used in the inner-loop, so the
|
| - current checks are too strict. */
|
| -
|
| - if (loop->inner)
|
| - vect_analyze_scalar_cycles_1 (loop_vinfo, loop->inner);
|
| -}
|
| -
|
| -
|
| -/* Find the place of the data-ref in STMT in the interleaving chain that starts
|
| - from FIRST_STMT. Return -1 if the data-ref is not a part of the chain. */
|
| -
|
| -static int
|
| -vect_get_place_in_interleaving_chain (gimple stmt, gimple first_stmt)
|
| -{
|
| - gimple next_stmt = first_stmt;
|
| - int result = 0;
|
| -
|
| - if (first_stmt != DR_GROUP_FIRST_DR (vinfo_for_stmt (stmt)))
|
| - return -1;
|
| -
|
| - while (next_stmt && next_stmt != stmt)
|
| - {
|
| - result++;
|
| - next_stmt = DR_GROUP_NEXT_DR (vinfo_for_stmt (next_stmt));
|
| - }
|
| -
|
| - if (next_stmt)
|
| - return result;
|
| - else
|
| - return -1;
|
| -}
|
| -
|
| -
|
| -/* Function vect_insert_into_interleaving_chain.
|
| -
|
| - Insert DRA into the interleaving chain of DRB according to DRA's INIT. */
|
| -
|
| -static void
|
| -vect_insert_into_interleaving_chain (struct data_reference *dra,
|
| - struct data_reference *drb)
|
| -{
|
| - gimple prev, next;
|
| - tree next_init;
|
| - stmt_vec_info stmtinfo_a = vinfo_for_stmt (DR_STMT (dra));
|
| - stmt_vec_info stmtinfo_b = vinfo_for_stmt (DR_STMT (drb));
|
| -
|
| - prev = DR_GROUP_FIRST_DR (stmtinfo_b);
|
| - next = DR_GROUP_NEXT_DR (vinfo_for_stmt (prev));
|
| - while (next)
|
| - {
|
| - next_init = DR_INIT (STMT_VINFO_DATA_REF (vinfo_for_stmt (next)));
|
| - if (tree_int_cst_compare (next_init, DR_INIT (dra)) > 0)
|
| - {
|
| - /* Insert here. */
|
| - DR_GROUP_NEXT_DR (vinfo_for_stmt (prev)) = DR_STMT (dra);
|
| - DR_GROUP_NEXT_DR (stmtinfo_a) = next;
|
| - return;
|
| - }
|
| - prev = next;
|
| - next = DR_GROUP_NEXT_DR (vinfo_for_stmt (prev));
|
| - }
|
| -
|
| - /* We got to the end of the list. Insert here. */
|
| - DR_GROUP_NEXT_DR (vinfo_for_stmt (prev)) = DR_STMT (dra);
|
| - DR_GROUP_NEXT_DR (stmtinfo_a) = NULL;
|
| -}
|
| -
|
| -
|
| -/* Function vect_update_interleaving_chain.
|
| -
|
| - For two data-refs DRA and DRB that are a part of a chain interleaved data
|
| - accesses, update the interleaving chain. DRB's INIT is smaller than DRA's.
|
| -
|
| - There are four possible cases:
|
| - 1. New stmts - both DRA and DRB are not a part of any chain:
|
| - FIRST_DR = DRB
|
| - NEXT_DR (DRB) = DRA
|
| - 2. DRB is a part of a chain and DRA is not:
|
| - no need to update FIRST_DR
|
| - no need to insert DRB
|
| - insert DRA according to init
|
| - 3. DRA is a part of a chain and DRB is not:
|
| - if (init of FIRST_DR > init of DRB)
|
| - FIRST_DR = DRB
|
| - NEXT(FIRST_DR) = previous FIRST_DR
|
| - else
|
| - insert DRB according to its init
|
| - 4. both DRA and DRB are in some interleaving chains:
|
| - choose the chain with the smallest init of FIRST_DR
|
| - insert the nodes of the second chain into the first one. */
|
| -
|
| -static void
|
| -vect_update_interleaving_chain (struct data_reference *drb,
|
| - struct data_reference *dra)
|
| -{
|
| - stmt_vec_info stmtinfo_a = vinfo_for_stmt (DR_STMT (dra));
|
| - stmt_vec_info stmtinfo_b = vinfo_for_stmt (DR_STMT (drb));
|
| - tree next_init, init_dra_chain, init_drb_chain;
|
| - gimple first_a, first_b;
|
| - tree node_init;
|
| - gimple node, prev, next, first_stmt;
|
| -
|
| - /* 1. New stmts - both DRA and DRB are not a part of any chain. */
|
| - if (!DR_GROUP_FIRST_DR (stmtinfo_a) && !DR_GROUP_FIRST_DR (stmtinfo_b))
|
| - {
|
| - DR_GROUP_FIRST_DR (stmtinfo_a) = DR_STMT (drb);
|
| - DR_GROUP_FIRST_DR (stmtinfo_b) = DR_STMT (drb);
|
| - DR_GROUP_NEXT_DR (stmtinfo_b) = DR_STMT (dra);
|
| - return;
|
| - }
|
| -
|
| - /* 2. DRB is a part of a chain and DRA is not. */
|
| - if (!DR_GROUP_FIRST_DR (stmtinfo_a) && DR_GROUP_FIRST_DR (stmtinfo_b))
|
| - {
|
| - DR_GROUP_FIRST_DR (stmtinfo_a) = DR_GROUP_FIRST_DR (stmtinfo_b);
|
| - /* Insert DRA into the chain of DRB. */
|
| - vect_insert_into_interleaving_chain (dra, drb);
|
| - return;
|
| - }
|
| -
|
| - /* 3. DRA is a part of a chain and DRB is not. */
|
| - if (DR_GROUP_FIRST_DR (stmtinfo_a) && !DR_GROUP_FIRST_DR (stmtinfo_b))
|
| - {
|
| - gimple old_first_stmt = DR_GROUP_FIRST_DR (stmtinfo_a);
|
| - tree init_old = DR_INIT (STMT_VINFO_DATA_REF (vinfo_for_stmt (
|
| - old_first_stmt)));
|
| - gimple tmp;
|
| -
|
| - if (tree_int_cst_compare (init_old, DR_INIT (drb)) > 0)
|
| - {
|
| - /* DRB's init is smaller than the init of the stmt previously marked
|
| - as the first stmt of the interleaving chain of DRA. Therefore, we
|
| - update FIRST_STMT and put DRB in the head of the list. */
|
| - DR_GROUP_FIRST_DR (stmtinfo_b) = DR_STMT (drb);
|
| - DR_GROUP_NEXT_DR (stmtinfo_b) = old_first_stmt;
|
| -
|
| - /* Update all the stmts in the list to point to the new FIRST_STMT. */
|
| - tmp = old_first_stmt;
|
| - while (tmp)
|
| - {
|
| - DR_GROUP_FIRST_DR (vinfo_for_stmt (tmp)) = DR_STMT (drb);
|
| - tmp = DR_GROUP_NEXT_DR (vinfo_for_stmt (tmp));
|
| - }
|
| - }
|
| - else
|
| - {
|
| - /* Insert DRB in the list of DRA. */
|
| - vect_insert_into_interleaving_chain (drb, dra);
|
| - DR_GROUP_FIRST_DR (stmtinfo_b) = DR_GROUP_FIRST_DR (stmtinfo_a);
|
| - }
|
| - return;
|
| - }
|
| -
|
| - /* 4. both DRA and DRB are in some interleaving chains. */
|
| - first_a = DR_GROUP_FIRST_DR (stmtinfo_a);
|
| - first_b = DR_GROUP_FIRST_DR (stmtinfo_b);
|
| - if (first_a == first_b)
|
| - return;
|
| - init_dra_chain = DR_INIT (STMT_VINFO_DATA_REF (vinfo_for_stmt (first_a)));
|
| - init_drb_chain = DR_INIT (STMT_VINFO_DATA_REF (vinfo_for_stmt (first_b)));
|
| -
|
| - if (tree_int_cst_compare (init_dra_chain, init_drb_chain) > 0)
|
| - {
|
| - /* Insert the nodes of DRA chain into the DRB chain.
|
| - After inserting a node, continue from this node of the DRB chain (don't
|
| - start from the beginning. */
|
| - node = DR_GROUP_FIRST_DR (stmtinfo_a);
|
| - prev = DR_GROUP_FIRST_DR (stmtinfo_b);
|
| - first_stmt = first_b;
|
| - }
|
| - else
|
| - {
|
| - /* Insert the nodes of DRB chain into the DRA chain.
|
| - After inserting a node, continue from this node of the DRA chain (don't
|
| - start from the beginning. */
|
| - node = DR_GROUP_FIRST_DR (stmtinfo_b);
|
| - prev = DR_GROUP_FIRST_DR (stmtinfo_a);
|
| - first_stmt = first_a;
|
| - }
|
| -
|
| - while (node)
|
| - {
|
| - node_init = DR_INIT (STMT_VINFO_DATA_REF (vinfo_for_stmt (node)));
|
| - next = DR_GROUP_NEXT_DR (vinfo_for_stmt (prev));
|
| - while (next)
|
| - {
|
| - next_init = DR_INIT (STMT_VINFO_DATA_REF (vinfo_for_stmt (next)));
|
| - if (tree_int_cst_compare (next_init, node_init) > 0)
|
| - {
|
| - /* Insert here. */
|
| - DR_GROUP_NEXT_DR (vinfo_for_stmt (prev)) = node;
|
| - DR_GROUP_NEXT_DR (vinfo_for_stmt (node)) = next;
|
| - prev = node;
|
| - break;
|
| - }
|
| - prev = next;
|
| - next = DR_GROUP_NEXT_DR (vinfo_for_stmt (prev));
|
| - }
|
| - if (!next)
|
| - {
|
| - /* We got to the end of the list. Insert here. */
|
| - DR_GROUP_NEXT_DR (vinfo_for_stmt (prev)) = node;
|
| - DR_GROUP_NEXT_DR (vinfo_for_stmt (node)) = NULL;
|
| - prev = node;
|
| - }
|
| - DR_GROUP_FIRST_DR (vinfo_for_stmt (node)) = first_stmt;
|
| - node = DR_GROUP_NEXT_DR (vinfo_for_stmt (node));
|
| - }
|
| -}
|
| -
|
| -
|
| -/* Function vect_equal_offsets.
|
| -
|
| - Check if OFFSET1 and OFFSET2 are identical expressions. */
|
| -
|
| -static bool
|
| -vect_equal_offsets (tree offset1, tree offset2)
|
| -{
|
| - bool res0, res1;
|
| -
|
| - STRIP_NOPS (offset1);
|
| - STRIP_NOPS (offset2);
|
| -
|
| - if (offset1 == offset2)
|
| - return true;
|
| -
|
| - if (TREE_CODE (offset1) != TREE_CODE (offset2)
|
| - || !BINARY_CLASS_P (offset1)
|
| - || !BINARY_CLASS_P (offset2))
|
| - return false;
|
| -
|
| - res0 = vect_equal_offsets (TREE_OPERAND (offset1, 0),
|
| - TREE_OPERAND (offset2, 0));
|
| - res1 = vect_equal_offsets (TREE_OPERAND (offset1, 1),
|
| - TREE_OPERAND (offset2, 1));
|
| -
|
| - return (res0 && res1);
|
| -}
|
| -
|
| -
|
| -/* Function vect_check_interleaving.
|
| -
|
| - Check if DRA and DRB are a part of interleaving. In case they are, insert
|
| - DRA and DRB in an interleaving chain. */
|
| -
|
| -static void
|
| -vect_check_interleaving (struct data_reference *dra,
|
| - struct data_reference *drb)
|
| -{
|
| - HOST_WIDE_INT type_size_a, type_size_b, diff_mod_size, step, init_a, init_b;
|
| -
|
| - /* Check that the data-refs have same first location (except init) and they
|
| - are both either store or load (not load and store). */
|
| - if ((DR_BASE_ADDRESS (dra) != DR_BASE_ADDRESS (drb)
|
| - && (TREE_CODE (DR_BASE_ADDRESS (dra)) != ADDR_EXPR
|
| - || TREE_CODE (DR_BASE_ADDRESS (drb)) != ADDR_EXPR
|
| - || TREE_OPERAND (DR_BASE_ADDRESS (dra), 0)
|
| - != TREE_OPERAND (DR_BASE_ADDRESS (drb),0)))
|
| - || !vect_equal_offsets (DR_OFFSET (dra), DR_OFFSET (drb))
|
| - || !tree_int_cst_compare (DR_INIT (dra), DR_INIT (drb))
|
| - || DR_IS_READ (dra) != DR_IS_READ (drb))
|
| - return;
|
| -
|
| - /* Check:
|
| - 1. data-refs are of the same type
|
| - 2. their steps are equal
|
| - 3. the step is greater than the difference between data-refs' inits */
|
| - type_size_a = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dra))));
|
| - type_size_b = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (drb))));
|
| -
|
| - if (type_size_a != type_size_b
|
| - || tree_int_cst_compare (DR_STEP (dra), DR_STEP (drb))
|
| - || !types_compatible_p (TREE_TYPE (DR_REF (dra)),
|
| - TREE_TYPE (DR_REF (drb))))
|
| - return;
|
| -
|
| - init_a = TREE_INT_CST_LOW (DR_INIT (dra));
|
| - init_b = TREE_INT_CST_LOW (DR_INIT (drb));
|
| - step = TREE_INT_CST_LOW (DR_STEP (dra));
|
| -
|
| - if (init_a > init_b)
|
| - {
|
| - /* If init_a == init_b + the size of the type * k, we have an interleaving,
|
| - and DRB is accessed before DRA. */
|
| - diff_mod_size = (init_a - init_b) % type_size_a;
|
| -
|
| - if ((init_a - init_b) > step)
|
| - return;
|
| -
|
| - if (diff_mod_size == 0)
|
| - {
|
| - vect_update_interleaving_chain (drb, dra);
|
| - if (vect_print_dump_info (REPORT_DR_DETAILS))
|
| - {
|
| - fprintf (vect_dump, "Detected interleaving ");
|
| - print_generic_expr (vect_dump, DR_REF (dra), TDF_SLIM);
|
| - fprintf (vect_dump, " and ");
|
| - print_generic_expr (vect_dump, DR_REF (drb), TDF_SLIM);
|
| - }
|
| - return;
|
| - }
|
| - }
|
| - else
|
| - {
|
| - /* If init_b == init_a + the size of the type * k, we have an
|
| - interleaving, and DRA is accessed before DRB. */
|
| - diff_mod_size = (init_b - init_a) % type_size_a;
|
| -
|
| - if ((init_b - init_a) > step)
|
| - return;
|
| -
|
| - if (diff_mod_size == 0)
|
| - {
|
| - vect_update_interleaving_chain (dra, drb);
|
| - if (vect_print_dump_info (REPORT_DR_DETAILS))
|
| - {
|
| - fprintf (vect_dump, "Detected interleaving ");
|
| - print_generic_expr (vect_dump, DR_REF (dra), TDF_SLIM);
|
| - fprintf (vect_dump, " and ");
|
| - print_generic_expr (vect_dump, DR_REF (drb), TDF_SLIM);
|
| - }
|
| - return;
|
| - }
|
| - }
|
| -}
|
| -
|
| -/* Check if data references pointed by DR_I and DR_J are same or
|
| - belong to same interleaving group. Return FALSE if drs are
|
| - different, otherwise return TRUE. */
|
| -
|
| -static bool
|
| -vect_same_range_drs (data_reference_p dr_i, data_reference_p dr_j)
|
| -{
|
| - gimple stmt_i = DR_STMT (dr_i);
|
| - gimple stmt_j = DR_STMT (dr_j);
|
| -
|
| - if (operand_equal_p (DR_REF (dr_i), DR_REF (dr_j), 0)
|
| - || (DR_GROUP_FIRST_DR (vinfo_for_stmt (stmt_i))
|
| - && DR_GROUP_FIRST_DR (vinfo_for_stmt (stmt_j))
|
| - && (DR_GROUP_FIRST_DR (vinfo_for_stmt (stmt_i))
|
| - == DR_GROUP_FIRST_DR (vinfo_for_stmt (stmt_j)))))
|
| - return true;
|
| - else
|
| - return false;
|
| -}
|
| -
|
| -/* If address ranges represented by DDR_I and DDR_J are equal,
|
| - return TRUE, otherwise return FALSE. */
|
| -
|
| -static bool
|
| -vect_vfa_range_equal (ddr_p ddr_i, ddr_p ddr_j)
|
| -{
|
| - if ((vect_same_range_drs (DDR_A (ddr_i), DDR_A (ddr_j))
|
| - && vect_same_range_drs (DDR_B (ddr_i), DDR_B (ddr_j)))
|
| - || (vect_same_range_drs (DDR_A (ddr_i), DDR_B (ddr_j))
|
| - && vect_same_range_drs (DDR_B (ddr_i), DDR_A (ddr_j))))
|
| - return true;
|
| - else
|
| - return false;
|
| -}
|
| -
|
| -/* Insert DDR into LOOP_VINFO list of ddrs that may alias and need to be
|
| - tested at run-time. Return TRUE if DDR was successfully inserted.
|
| - Return false if versioning is not supported. */
|
| -
|
| -static bool
|
| -vect_mark_for_runtime_alias_test (ddr_p ddr, loop_vec_info loop_vinfo)
|
| -{
|
| - struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
|
| -
|
| - if ((unsigned) PARAM_VALUE (PARAM_VECT_MAX_VERSION_FOR_ALIAS_CHECKS) == 0)
|
| - return false;
|
| -
|
| - if (vect_print_dump_info (REPORT_DR_DETAILS))
|
| - {
|
| - fprintf (vect_dump, "mark for run-time aliasing test between ");
|
| - print_generic_expr (vect_dump, DR_REF (DDR_A (ddr)), TDF_SLIM);
|
| - fprintf (vect_dump, " and ");
|
| - print_generic_expr (vect_dump, DR_REF (DDR_B (ddr)), TDF_SLIM);
|
| - }
|
| -
|
| - if (optimize_loop_nest_for_size_p (loop))
|
| - {
|
| - if (vect_print_dump_info (REPORT_DR_DETAILS))
|
| - fprintf (vect_dump, "versioning not supported when optimizing for size.");
|
| - return false;
|
| - }
|
| -
|
| - /* FORNOW: We don't support versioning with outer-loop vectorization. */
|
| - if (loop->inner)
|
| - {
|
| - if (vect_print_dump_info (REPORT_DR_DETAILS))
|
| - fprintf (vect_dump, "versioning not yet supported for outer-loops.");
|
| - return false;
|
| - }
|
| -
|
| - VEC_safe_push (ddr_p, heap, LOOP_VINFO_MAY_ALIAS_DDRS (loop_vinfo), ddr);
|
| - return true;
|
| -}
|
| -
|
| -/* Function vect_analyze_data_ref_dependence.
|
| -
|
| - Return TRUE if there (might) exist a dependence between a memory-reference
|
| - DRA and a memory-reference DRB. When versioning for alias may check a
|
| - dependence at run-time, return FALSE. */
|
| -
|
| -static bool
|
| -vect_analyze_data_ref_dependence (struct data_dependence_relation *ddr,
|
| - loop_vec_info loop_vinfo)
|
| -{
|
| - unsigned int i;
|
| - struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
|
| - int vectorization_factor = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
|
| - struct data_reference *dra = DDR_A (ddr);
|
| - struct data_reference *drb = DDR_B (ddr);
|
| - stmt_vec_info stmtinfo_a = vinfo_for_stmt (DR_STMT (dra));
|
| - stmt_vec_info stmtinfo_b = vinfo_for_stmt (DR_STMT (drb));
|
| - int dra_size = GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (DR_REF (dra))));
|
| - int drb_size = GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (DR_REF (drb))));
|
| - lambda_vector dist_v;
|
| - unsigned int loop_depth;
|
| -
|
| - if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
|
| - {
|
| - /* Independent data accesses. */
|
| - vect_check_interleaving (dra, drb);
|
| - return false;
|
| - }
|
| -
|
| - if ((DR_IS_READ (dra) && DR_IS_READ (drb)) || dra == drb)
|
| - return false;
|
| -
|
| - if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
|
| - {
|
| - if (vect_print_dump_info (REPORT_DR_DETAILS))
|
| - {
|
| - fprintf (vect_dump,
|
| - "versioning for alias required: can't determine dependence between ");
|
| - print_generic_expr (vect_dump, DR_REF (dra), TDF_SLIM);
|
| - fprintf (vect_dump, " and ");
|
| - print_generic_expr (vect_dump, DR_REF (drb), TDF_SLIM);
|
| - }
|
| - /* Add to list of ddrs that need to be tested at run-time. */
|
| - return !vect_mark_for_runtime_alias_test (ddr, loop_vinfo);
|
| - }
|
| -
|
| - if (DDR_NUM_DIST_VECTS (ddr) == 0)
|
| - {
|
| - if (vect_print_dump_info (REPORT_DR_DETAILS))
|
| - {
|
| - fprintf (vect_dump, "versioning for alias required: bad dist vector for ");
|
| - print_generic_expr (vect_dump, DR_REF (dra), TDF_SLIM);
|
| - fprintf (vect_dump, " and ");
|
| - print_generic_expr (vect_dump, DR_REF (drb), TDF_SLIM);
|
| - }
|
| - /* Add to list of ddrs that need to be tested at run-time. */
|
| - return !vect_mark_for_runtime_alias_test (ddr, loop_vinfo);
|
| - }
|
| -
|
| - loop_depth = index_in_loop_nest (loop->num, DDR_LOOP_NEST (ddr));
|
| - for (i = 0; VEC_iterate (lambda_vector, DDR_DIST_VECTS (ddr), i, dist_v); i++)
|
| - {
|
| - int dist = dist_v[loop_depth];
|
| -
|
| - if (vect_print_dump_info (REPORT_DR_DETAILS))
|
| - fprintf (vect_dump, "dependence distance = %d.", dist);
|
| -
|
| - /* Same loop iteration. */
|
| - if (dist % vectorization_factor == 0 && dra_size == drb_size)
|
| - {
|
| - /* Two references with distance zero have the same alignment. */
|
| - VEC_safe_push (dr_p, heap, STMT_VINFO_SAME_ALIGN_REFS (stmtinfo_a), drb);
|
| - VEC_safe_push (dr_p, heap, STMT_VINFO_SAME_ALIGN_REFS (stmtinfo_b), dra);
|
| - if (vect_print_dump_info (REPORT_ALIGNMENT))
|
| - fprintf (vect_dump, "accesses have the same alignment.");
|
| - if (vect_print_dump_info (REPORT_DR_DETAILS))
|
| - {
|
| - fprintf (vect_dump, "dependence distance modulo vf == 0 between ");
|
| - print_generic_expr (vect_dump, DR_REF (dra), TDF_SLIM);
|
| - fprintf (vect_dump, " and ");
|
| - print_generic_expr (vect_dump, DR_REF (drb), TDF_SLIM);
|
| - }
|
| -
|
| - /* For interleaving, mark that there is a read-write dependency if
|
| - necessary. We check before that one of the data-refs is store. */
|
| - if (DR_IS_READ (dra))
|
| - DR_GROUP_READ_WRITE_DEPENDENCE (stmtinfo_a) = true;
|
| - else
|
| - {
|
| - if (DR_IS_READ (drb))
|
| - DR_GROUP_READ_WRITE_DEPENDENCE (stmtinfo_b) = true;
|
| - }
|
| -
|
| - continue;
|
| - }
|
| -
|
| - if (abs (dist) >= vectorization_factor
|
| - || (dist > 0 && DDR_REVERSED_P (ddr)))
|
| - {
|
| - /* Dependence distance does not create dependence, as far as
|
| - vectorization is concerned, in this case. If DDR_REVERSED_P the
|
| - order of the data-refs in DDR was reversed (to make distance
|
| - vector positive), and the actual distance is negative. */
|
| - if (vect_print_dump_info (REPORT_DR_DETAILS))
|
| - fprintf (vect_dump, "dependence distance >= VF or negative.");
|
| - continue;
|
| - }
|
| -
|
| - if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
|
| - {
|
| - fprintf (vect_dump,
|
| - "not vectorized, possible dependence "
|
| - "between data-refs ");
|
| - print_generic_expr (vect_dump, DR_REF (dra), TDF_SLIM);
|
| - fprintf (vect_dump, " and ");
|
| - print_generic_expr (vect_dump, DR_REF (drb), TDF_SLIM);
|
| - }
|
| -
|
| - return true;
|
| - }
|
| -
|
| - return false;
|
| -}
|
| -
|
| -/* Function vect_analyze_data_ref_dependences.
|
| -
|
| - Examine all the data references in the loop, and make sure there do not
|
| - exist any data dependences between them. */
|
| -
|
| -static bool
|
| -vect_analyze_data_ref_dependences (loop_vec_info loop_vinfo)
|
| -{
|
| - unsigned int i;
|
| - VEC (ddr_p, heap) * ddrs = LOOP_VINFO_DDRS (loop_vinfo);
|
| - struct data_dependence_relation *ddr;
|
| -
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "=== vect_analyze_dependences ===");
|
| -
|
| - for (i = 0; VEC_iterate (ddr_p, ddrs, i, ddr); i++)
|
| - if (vect_analyze_data_ref_dependence (ddr, loop_vinfo))
|
| - return false;
|
| -
|
| - return true;
|
| -}
|
| -
|
| -
|
| -/* Function vect_compute_data_ref_alignment
|
| -
|
| - Compute the misalignment of the data reference DR.
|
| -
|
| - Output:
|
| - 1. If during the misalignment computation it is found that the data reference
|
| - cannot be vectorized then false is returned.
|
| - 2. DR_MISALIGNMENT (DR) is defined.
|
| -
|
| - FOR NOW: No analysis is actually performed. Misalignment is calculated
|
| - only for trivial cases. TODO. */
|
| -
|
| -static bool
|
| -vect_compute_data_ref_alignment (struct data_reference *dr)
|
| -{
|
| - gimple stmt = DR_STMT (dr);
|
| - stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
|
| - loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
|
| - struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
|
| - tree ref = DR_REF (dr);
|
| - tree vectype;
|
| - tree base, base_addr;
|
| - bool base_aligned;
|
| - tree misalign;
|
| - tree aligned_to, alignment;
|
| -
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "vect_compute_data_ref_alignment:");
|
| -
|
| - /* Initialize misalignment to unknown. */
|
| - SET_DR_MISALIGNMENT (dr, -1);
|
| -
|
| - misalign = DR_INIT (dr);
|
| - aligned_to = DR_ALIGNED_TO (dr);
|
| - base_addr = DR_BASE_ADDRESS (dr);
|
| - vectype = STMT_VINFO_VECTYPE (stmt_info);
|
| -
|
| - /* In case the dataref is in an inner-loop of the loop that is being
|
| - vectorized (LOOP), we use the base and misalignment information
|
| - relative to the outer-loop (LOOP). This is ok only if the misalignment
|
| - stays the same throughout the execution of the inner-loop, which is why
|
| - we have to check that the stride of the dataref in the inner-loop evenly
|
| - divides by the vector size. */
|
| - if (nested_in_vect_loop_p (loop, stmt))
|
| - {
|
| - tree step = DR_STEP (dr);
|
| - HOST_WIDE_INT dr_step = TREE_INT_CST_LOW (step);
|
| -
|
| - if (dr_step % GET_MODE_SIZE (TYPE_MODE (vectype)) == 0)
|
| - {
|
| - if (vect_print_dump_info (REPORT_ALIGNMENT))
|
| - fprintf (vect_dump, "inner step divides the vector-size.");
|
| - misalign = STMT_VINFO_DR_INIT (stmt_info);
|
| - aligned_to = STMT_VINFO_DR_ALIGNED_TO (stmt_info);
|
| - base_addr = STMT_VINFO_DR_BASE_ADDRESS (stmt_info);
|
| - }
|
| - else
|
| - {
|
| - if (vect_print_dump_info (REPORT_ALIGNMENT))
|
| - fprintf (vect_dump, "inner step doesn't divide the vector-size.");
|
| - misalign = NULL_TREE;
|
| - }
|
| - }
|
| -
|
| - base = build_fold_indirect_ref (base_addr);
|
| - alignment = ssize_int (TYPE_ALIGN (vectype)/BITS_PER_UNIT);
|
| -
|
| - if ((aligned_to && tree_int_cst_compare (aligned_to, alignment) < 0)
|
| - || !misalign)
|
| - {
|
| - if (vect_print_dump_info (REPORT_ALIGNMENT))
|
| - {
|
| - fprintf (vect_dump, "Unknown alignment for access: ");
|
| - print_generic_expr (vect_dump, base, TDF_SLIM);
|
| - }
|
| - return true;
|
| - }
|
| -
|
| - if ((DECL_P (base)
|
| - && tree_int_cst_compare (ssize_int (DECL_ALIGN_UNIT (base)),
|
| - alignment) >= 0)
|
| - || (TREE_CODE (base_addr) == SSA_NAME
|
| - && tree_int_cst_compare (ssize_int (TYPE_ALIGN_UNIT (TREE_TYPE (
|
| - TREE_TYPE (base_addr)))),
|
| - alignment) >= 0))
|
| - base_aligned = true;
|
| - else
|
| - base_aligned = false;
|
| -
|
| - if (!base_aligned)
|
| - {
|
| - /* Do not change the alignment of global variables if
|
| - flag_section_anchors is enabled. */
|
| - if (!vect_can_force_dr_alignment_p (base, TYPE_ALIGN (vectype))
|
| - || (TREE_STATIC (base) && flag_section_anchors))
|
| - {
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - {
|
| - fprintf (vect_dump, "can't force alignment of ref: ");
|
| - print_generic_expr (vect_dump, ref, TDF_SLIM);
|
| - }
|
| - return true;
|
| - }
|
| -
|
| - /* Force the alignment of the decl.
|
| - NOTE: This is the only change to the code we make during
|
| - the analysis phase, before deciding to vectorize the loop. */
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "force alignment");
|
| - DECL_ALIGN (base) = TYPE_ALIGN (vectype);
|
| - DECL_USER_ALIGN (base) = 1;
|
| - }
|
| -
|
| - /* At this point we assume that the base is aligned. */
|
| - gcc_assert (base_aligned
|
| - || (TREE_CODE (base) == VAR_DECL
|
| - && DECL_ALIGN (base) >= TYPE_ALIGN (vectype)));
|
| -
|
| - /* Modulo alignment. */
|
| - misalign = size_binop (TRUNC_MOD_EXPR, misalign, alignment);
|
| -
|
| - if (!host_integerp (misalign, 1))
|
| - {
|
| - /* Negative or overflowed misalignment value. */
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "unexpected misalign value");
|
| - return false;
|
| - }
|
| -
|
| - SET_DR_MISALIGNMENT (dr, TREE_INT_CST_LOW (misalign));
|
| -
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - {
|
| - fprintf (vect_dump, "misalign = %d bytes of ref ", DR_MISALIGNMENT (dr));
|
| - print_generic_expr (vect_dump, ref, TDF_SLIM);
|
| - }
|
| -
|
| - return true;
|
| -}
|
| -
|
| -
|
| -/* Function vect_compute_data_refs_alignment
|
| -
|
| - Compute the misalignment of data references in the loop.
|
| - Return FALSE if a data reference is found that cannot be vectorized. */
|
| -
|
| -static bool
|
| -vect_compute_data_refs_alignment (loop_vec_info loop_vinfo)
|
| -{
|
| - VEC (data_reference_p, heap) *datarefs = LOOP_VINFO_DATAREFS (loop_vinfo);
|
| - struct data_reference *dr;
|
| - unsigned int i;
|
| -
|
| - for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
|
| - if (!vect_compute_data_ref_alignment (dr))
|
| - return false;
|
| -
|
| - return true;
|
| -}
|
| -
|
| -
|
| -/* Function vect_update_misalignment_for_peel
|
| -
|
| - DR - the data reference whose misalignment is to be adjusted.
|
| - DR_PEEL - the data reference whose misalignment is being made
|
| - zero in the vector loop by the peel.
|
| - NPEEL - the number of iterations in the peel loop if the misalignment
|
| - of DR_PEEL is known at compile time. */
|
| -
|
| -static void
|
| -vect_update_misalignment_for_peel (struct data_reference *dr,
|
| - struct data_reference *dr_peel, int npeel)
|
| -{
|
| - unsigned int i;
|
| - VEC(dr_p,heap) *same_align_drs;
|
| - struct data_reference *current_dr;
|
| - int dr_size = GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (DR_REF (dr))));
|
| - int dr_peel_size = GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (DR_REF (dr_peel))));
|
| - stmt_vec_info stmt_info = vinfo_for_stmt (DR_STMT (dr));
|
| - stmt_vec_info peel_stmt_info = vinfo_for_stmt (DR_STMT (dr_peel));
|
| -
|
| - /* For interleaved data accesses the step in the loop must be multiplied by
|
| - the size of the interleaving group. */
|
| - if (STMT_VINFO_STRIDED_ACCESS (stmt_info))
|
| - dr_size *= DR_GROUP_SIZE (vinfo_for_stmt (DR_GROUP_FIRST_DR (stmt_info)));
|
| - if (STMT_VINFO_STRIDED_ACCESS (peel_stmt_info))
|
| - dr_peel_size *= DR_GROUP_SIZE (peel_stmt_info);
|
| -
|
| - /* It can be assumed that the data refs with the same alignment as dr_peel
|
| - are aligned in the vector loop. */
|
| - same_align_drs
|
| - = STMT_VINFO_SAME_ALIGN_REFS (vinfo_for_stmt (DR_STMT (dr_peel)));
|
| - for (i = 0; VEC_iterate (dr_p, same_align_drs, i, current_dr); i++)
|
| - {
|
| - if (current_dr != dr)
|
| - continue;
|
| - gcc_assert (DR_MISALIGNMENT (dr) / dr_size ==
|
| - DR_MISALIGNMENT (dr_peel) / dr_peel_size);
|
| - SET_DR_MISALIGNMENT (dr, 0);
|
| - return;
|
| - }
|
| -
|
| - if (known_alignment_for_access_p (dr)
|
| - && known_alignment_for_access_p (dr_peel))
|
| - {
|
| - int misal = DR_MISALIGNMENT (dr);
|
| - tree vectype = STMT_VINFO_VECTYPE (stmt_info);
|
| - misal += npeel * dr_size;
|
| - misal %= GET_MODE_SIZE (TYPE_MODE (vectype));
|
| - SET_DR_MISALIGNMENT (dr, misal);
|
| - return;
|
| - }
|
| -
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "Setting misalignment to -1.");
|
| - SET_DR_MISALIGNMENT (dr, -1);
|
| -}
|
| -
|
| -
|
| -/* Function vect_verify_datarefs_alignment
|
| -
|
| - Return TRUE if all data references in the loop can be
|
| - handled with respect to alignment. */
|
| -
|
| -static bool
|
| -vect_verify_datarefs_alignment (loop_vec_info loop_vinfo)
|
| -{
|
| - VEC (data_reference_p, heap) *datarefs = LOOP_VINFO_DATAREFS (loop_vinfo);
|
| - struct data_reference *dr;
|
| - enum dr_alignment_support supportable_dr_alignment;
|
| - unsigned int i;
|
| -
|
| - for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
|
| - {
|
| - gimple stmt = DR_STMT (dr);
|
| - stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
|
| -
|
| - /* For interleaving, only the alignment of the first access matters. */
|
| - if (STMT_VINFO_STRIDED_ACCESS (stmt_info)
|
| - && DR_GROUP_FIRST_DR (stmt_info) != stmt)
|
| - continue;
|
| -
|
| - supportable_dr_alignment = vect_supportable_dr_alignment (dr);
|
| - if (!supportable_dr_alignment)
|
| - {
|
| - if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
|
| - {
|
| - if (DR_IS_READ (dr))
|
| - fprintf (vect_dump,
|
| - "not vectorized: unsupported unaligned load.");
|
| - else
|
| - fprintf (vect_dump,
|
| - "not vectorized: unsupported unaligned store.");
|
| - }
|
| - return false;
|
| - }
|
| - if (supportable_dr_alignment != dr_aligned
|
| - && vect_print_dump_info (REPORT_ALIGNMENT))
|
| - fprintf (vect_dump, "Vectorizing an unaligned access.");
|
| - }
|
| - return true;
|
| -}
|
| -
|
| -
|
| -/* Function vector_alignment_reachable_p
|
| -
|
| - Return true if vector alignment for DR is reachable by peeling
|
| - a few loop iterations. Return false otherwise. */
|
| -
|
| -static bool
|
| -vector_alignment_reachable_p (struct data_reference *dr)
|
| -{
|
| - gimple stmt = DR_STMT (dr);
|
| - stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
|
| - tree vectype = STMT_VINFO_VECTYPE (stmt_info);
|
| -
|
| - if (STMT_VINFO_STRIDED_ACCESS (stmt_info))
|
| - {
|
| - /* For interleaved access we peel only if number of iterations in
|
| - the prolog loop ({VF - misalignment}), is a multiple of the
|
| - number of the interleaved accesses. */
|
| - int elem_size, mis_in_elements;
|
| - int nelements = TYPE_VECTOR_SUBPARTS (vectype);
|
| -
|
| - /* FORNOW: handle only known alignment. */
|
| - if (!known_alignment_for_access_p (dr))
|
| - return false;
|
| -
|
| - elem_size = GET_MODE_SIZE (TYPE_MODE (vectype)) / nelements;
|
| - mis_in_elements = DR_MISALIGNMENT (dr) / elem_size;
|
| -
|
| - if ((nelements - mis_in_elements) % DR_GROUP_SIZE (stmt_info))
|
| - return false;
|
| - }
|
| -
|
| - /* If misalignment is known at the compile time then allow peeling
|
| - only if natural alignment is reachable through peeling. */
|
| - if (known_alignment_for_access_p (dr) && !aligned_access_p (dr))
|
| - {
|
| - HOST_WIDE_INT elmsize =
|
| - int_cst_value (TYPE_SIZE_UNIT (TREE_TYPE (vectype)));
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - {
|
| - fprintf (vect_dump, "data size =" HOST_WIDE_INT_PRINT_DEC, elmsize);
|
| - fprintf (vect_dump, ". misalignment = %d. ", DR_MISALIGNMENT (dr));
|
| - }
|
| - if (DR_MISALIGNMENT (dr) % elmsize)
|
| - {
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "data size does not divide the misalignment.\n");
|
| - return false;
|
| - }
|
| - }
|
| -
|
| - if (!known_alignment_for_access_p (dr))
|
| - {
|
| - tree type = (TREE_TYPE (DR_REF (dr)));
|
| - tree ba = DR_BASE_OBJECT (dr);
|
| - bool is_packed = false;
|
| -
|
| - if (ba)
|
| - is_packed = contains_packed_reference (ba);
|
| -
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "Unknown misalignment, is_packed = %d",is_packed);
|
| - if (targetm.vectorize.vector_alignment_reachable (type, is_packed))
|
| - return true;
|
| - else
|
| - return false;
|
| - }
|
| -
|
| - return true;
|
| -}
|
| -
|
| -/* Function vect_enhance_data_refs_alignment
|
| -
|
| - This pass will use loop versioning and loop peeling in order to enhance
|
| - the alignment of data references in the loop.
|
| -
|
| - FOR NOW: we assume that whatever versioning/peeling takes place, only the
|
| - original loop is to be vectorized; Any other loops that are created by
|
| - the transformations performed in this pass - are not supposed to be
|
| - vectorized. This restriction will be relaxed.
|
| -
|
| - This pass will require a cost model to guide it whether to apply peeling
|
| - or versioning or a combination of the two. For example, the scheme that
|
| - intel uses when given a loop with several memory accesses, is as follows:
|
| - choose one memory access ('p') which alignment you want to force by doing
|
| - peeling. Then, either (1) generate a loop in which 'p' is aligned and all
|
| - other accesses are not necessarily aligned, or (2) use loop versioning to
|
| - generate one loop in which all accesses are aligned, and another loop in
|
| - which only 'p' is necessarily aligned.
|
| -
|
| - ("Automatic Intra-Register Vectorization for the Intel Architecture",
|
| - Aart J.C. Bik, Milind Girkar, Paul M. Grey and Ximmin Tian, International
|
| - Journal of Parallel Programming, Vol. 30, No. 2, April 2002.)
|
| -
|
| - Devising a cost model is the most critical aspect of this work. It will
|
| - guide us on which access to peel for, whether to use loop versioning, how
|
| - many versions to create, etc. The cost model will probably consist of
|
| - generic considerations as well as target specific considerations (on
|
| - powerpc for example, misaligned stores are more painful than misaligned
|
| - loads).
|
| -
|
| - Here are the general steps involved in alignment enhancements:
|
| -
|
| - -- original loop, before alignment analysis:
|
| - for (i=0; i<N; i++){
|
| - x = q[i]; # DR_MISALIGNMENT(q) = unknown
|
| - p[i] = y; # DR_MISALIGNMENT(p) = unknown
|
| - }
|
| -
|
| - -- After vect_compute_data_refs_alignment:
|
| - for (i=0; i<N; i++){
|
| - x = q[i]; # DR_MISALIGNMENT(q) = 3
|
| - p[i] = y; # DR_MISALIGNMENT(p) = unknown
|
| - }
|
| -
|
| - -- Possibility 1: we do loop versioning:
|
| - if (p is aligned) {
|
| - for (i=0; i<N; i++){ # loop 1A
|
| - x = q[i]; # DR_MISALIGNMENT(q) = 3
|
| - p[i] = y; # DR_MISALIGNMENT(p) = 0
|
| - }
|
| - }
|
| - else {
|
| - for (i=0; i<N; i++){ # loop 1B
|
| - x = q[i]; # DR_MISALIGNMENT(q) = 3
|
| - p[i] = y; # DR_MISALIGNMENT(p) = unaligned
|
| - }
|
| - }
|
| -
|
| - -- Possibility 2: we do loop peeling:
|
| - for (i = 0; i < 3; i++){ # (scalar loop, not to be vectorized).
|
| - x = q[i];
|
| - p[i] = y;
|
| - }
|
| - for (i = 3; i < N; i++){ # loop 2A
|
| - x = q[i]; # DR_MISALIGNMENT(q) = 0
|
| - p[i] = y; # DR_MISALIGNMENT(p) = unknown
|
| - }
|
| -
|
| - -- Possibility 3: combination of loop peeling and versioning:
|
| - for (i = 0; i < 3; i++){ # (scalar loop, not to be vectorized).
|
| - x = q[i];
|
| - p[i] = y;
|
| - }
|
| - if (p is aligned) {
|
| - for (i = 3; i<N; i++){ # loop 3A
|
| - x = q[i]; # DR_MISALIGNMENT(q) = 0
|
| - p[i] = y; # DR_MISALIGNMENT(p) = 0
|
| - }
|
| - }
|
| - else {
|
| - for (i = 3; i<N; i++){ # loop 3B
|
| - x = q[i]; # DR_MISALIGNMENT(q) = 0
|
| - p[i] = y; # DR_MISALIGNMENT(p) = unaligned
|
| - }
|
| - }
|
| -
|
| - These loops are later passed to loop_transform to be vectorized. The
|
| - vectorizer will use the alignment information to guide the transformation
|
| - (whether to generate regular loads/stores, or with special handling for
|
| - misalignment). */
|
| -
|
| -static bool
|
| -vect_enhance_data_refs_alignment (loop_vec_info loop_vinfo)
|
| -{
|
| - VEC (data_reference_p, heap) *datarefs = LOOP_VINFO_DATAREFS (loop_vinfo);
|
| - struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
|
| - enum dr_alignment_support supportable_dr_alignment;
|
| - struct data_reference *dr0 = NULL;
|
| - struct data_reference *dr;
|
| - unsigned int i;
|
| - bool do_peeling = false;
|
| - bool do_versioning = false;
|
| - bool stat;
|
| - gimple stmt;
|
| - stmt_vec_info stmt_info;
|
| - int vect_versioning_for_alias_required;
|
| -
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "=== vect_enhance_data_refs_alignment ===");
|
| -
|
| - /* While cost model enhancements are expected in the future, the high level
|
| - view of the code at this time is as follows:
|
| -
|
| - A) If there is a misaligned write then see if peeling to align this write
|
| - can make all data references satisfy vect_supportable_dr_alignment.
|
| - If so, update data structures as needed and return true. Note that
|
| - at this time vect_supportable_dr_alignment is known to return false
|
| - for a misaligned write.
|
| -
|
| - B) If peeling wasn't possible and there is a data reference with an
|
| - unknown misalignment that does not satisfy vect_supportable_dr_alignment
|
| - then see if loop versioning checks can be used to make all data
|
| - references satisfy vect_supportable_dr_alignment. If so, update
|
| - data structures as needed and return true.
|
| -
|
| - C) If neither peeling nor versioning were successful then return false if
|
| - any data reference does not satisfy vect_supportable_dr_alignment.
|
| -
|
| - D) Return true (all data references satisfy vect_supportable_dr_alignment).
|
| -
|
| - Note, Possibility 3 above (which is peeling and versioning together) is not
|
| - being done at this time. */
|
| -
|
| - /* (1) Peeling to force alignment. */
|
| -
|
| - /* (1.1) Decide whether to perform peeling, and how many iterations to peel:
|
| - Considerations:
|
| - + How many accesses will become aligned due to the peeling
|
| - - How many accesses will become unaligned due to the peeling,
|
| - and the cost of misaligned accesses.
|
| - - The cost of peeling (the extra runtime checks, the increase
|
| - in code size).
|
| -
|
| - The scheme we use FORNOW: peel to force the alignment of the first
|
| - misaligned store in the loop.
|
| - Rationale: misaligned stores are not yet supported.
|
| -
|
| - TODO: Use a cost model. */
|
| -
|
| - for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
|
| - {
|
| - stmt = DR_STMT (dr);
|
| - stmt_info = vinfo_for_stmt (stmt);
|
| -
|
| - /* For interleaving, only the alignment of the first access
|
| - matters. */
|
| - if (STMT_VINFO_STRIDED_ACCESS (stmt_info)
|
| - && DR_GROUP_FIRST_DR (stmt_info) != stmt)
|
| - continue;
|
| -
|
| - if (!DR_IS_READ (dr) && !aligned_access_p (dr))
|
| - {
|
| - do_peeling = vector_alignment_reachable_p (dr);
|
| - if (do_peeling)
|
| - dr0 = dr;
|
| - if (!do_peeling && vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "vector alignment may not be reachable");
|
| - break;
|
| - }
|
| - }
|
| -
|
| - vect_versioning_for_alias_required =
|
| - (VEC_length (ddr_p, LOOP_VINFO_MAY_ALIAS_DDRS (loop_vinfo)) > 0);
|
| -
|
| - /* Temporarily, if versioning for alias is required, we disable peeling
|
| - until we support peeling and versioning. Often peeling for alignment
|
| - will require peeling for loop-bound, which in turn requires that we
|
| - know how to adjust the loop ivs after the loop. */
|
| - if (vect_versioning_for_alias_required
|
| - || !vect_can_advance_ivs_p (loop_vinfo)
|
| - || !slpeel_can_duplicate_loop_p (loop, single_exit (loop)))
|
| - do_peeling = false;
|
| -
|
| - if (do_peeling)
|
| - {
|
| - int mis;
|
| - int npeel = 0;
|
| - gimple stmt = DR_STMT (dr0);
|
| - stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
|
| - tree vectype = STMT_VINFO_VECTYPE (stmt_info);
|
| - int nelements = TYPE_VECTOR_SUBPARTS (vectype);
|
| -
|
| - if (known_alignment_for_access_p (dr0))
|
| - {
|
| - /* Since it's known at compile time, compute the number of iterations
|
| - in the peeled loop (the peeling factor) for use in updating
|
| - DR_MISALIGNMENT values. The peeling factor is the vectorization
|
| - factor minus the misalignment as an element count. */
|
| - mis = DR_MISALIGNMENT (dr0);
|
| - mis /= GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (DR_REF (dr0))));
|
| - npeel = nelements - mis;
|
| -
|
| - /* For interleaved data access every iteration accesses all the
|
| - members of the group, therefore we divide the number of iterations
|
| - by the group size. */
|
| - stmt_info = vinfo_for_stmt (DR_STMT (dr0));
|
| - if (STMT_VINFO_STRIDED_ACCESS (stmt_info))
|
| - npeel /= DR_GROUP_SIZE (stmt_info);
|
| -
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "Try peeling by %d", npeel);
|
| - }
|
| -
|
| - /* Ensure that all data refs can be vectorized after the peel. */
|
| - for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
|
| - {
|
| - int save_misalignment;
|
| -
|
| - if (dr == dr0)
|
| - continue;
|
| -
|
| - stmt = DR_STMT (dr);
|
| - stmt_info = vinfo_for_stmt (stmt);
|
| - /* For interleaving, only the alignment of the first access
|
| - matters. */
|
| - if (STMT_VINFO_STRIDED_ACCESS (stmt_info)
|
| - && DR_GROUP_FIRST_DR (stmt_info) != stmt)
|
| - continue;
|
| -
|
| - save_misalignment = DR_MISALIGNMENT (dr);
|
| - vect_update_misalignment_for_peel (dr, dr0, npeel);
|
| - supportable_dr_alignment = vect_supportable_dr_alignment (dr);
|
| - SET_DR_MISALIGNMENT (dr, save_misalignment);
|
| -
|
| - if (!supportable_dr_alignment)
|
| - {
|
| - do_peeling = false;
|
| - break;
|
| - }
|
| - }
|
| -
|
| - if (do_peeling)
|
| - {
|
| - /* (1.2) Update the DR_MISALIGNMENT of each data reference DR_i.
|
| - If the misalignment of DR_i is identical to that of dr0 then set
|
| - DR_MISALIGNMENT (DR_i) to zero. If the misalignment of DR_i and
|
| - dr0 are known at compile time then increment DR_MISALIGNMENT (DR_i)
|
| - by the peeling factor times the element size of DR_i (MOD the
|
| - vectorization factor times the size). Otherwise, the
|
| - misalignment of DR_i must be set to unknown. */
|
| - for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
|
| - if (dr != dr0)
|
| - vect_update_misalignment_for_peel (dr, dr0, npeel);
|
| -
|
| - LOOP_VINFO_UNALIGNED_DR (loop_vinfo) = dr0;
|
| - LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo) = DR_MISALIGNMENT (dr0);
|
| - SET_DR_MISALIGNMENT (dr0, 0);
|
| - if (vect_print_dump_info (REPORT_ALIGNMENT))
|
| - fprintf (vect_dump, "Alignment of access forced using peeling.");
|
| -
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "Peeling for alignment will be applied.");
|
| -
|
| - stat = vect_verify_datarefs_alignment (loop_vinfo);
|
| - gcc_assert (stat);
|
| - return stat;
|
| - }
|
| - }
|
| -
|
| -
|
| - /* (2) Versioning to force alignment. */
|
| -
|
| - /* Try versioning if:
|
| - 1) flag_tree_vect_loop_version is TRUE
|
| - 2) optimize loop for speed
|
| - 3) there is at least one unsupported misaligned data ref with an unknown
|
| - misalignment, and
|
| - 4) all misaligned data refs with a known misalignment are supported, and
|
| - 5) the number of runtime alignment checks is within reason. */
|
| -
|
| - do_versioning =
|
| - flag_tree_vect_loop_version
|
| - && optimize_loop_nest_for_speed_p (loop)
|
| - && (!loop->inner); /* FORNOW */
|
| -
|
| - if (do_versioning)
|
| - {
|
| - for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
|
| - {
|
| - stmt = DR_STMT (dr);
|
| - stmt_info = vinfo_for_stmt (stmt);
|
| -
|
| - /* For interleaving, only the alignment of the first access
|
| - matters. */
|
| - if (aligned_access_p (dr)
|
| - || (STMT_VINFO_STRIDED_ACCESS (stmt_info)
|
| - && DR_GROUP_FIRST_DR (stmt_info) != stmt))
|
| - continue;
|
| -
|
| - supportable_dr_alignment = vect_supportable_dr_alignment (dr);
|
| -
|
| - if (!supportable_dr_alignment)
|
| - {
|
| - gimple stmt;
|
| - int mask;
|
| - tree vectype;
|
| -
|
| - if (known_alignment_for_access_p (dr)
|
| - || VEC_length (gimple,
|
| - LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo))
|
| - >= (unsigned) PARAM_VALUE (PARAM_VECT_MAX_VERSION_FOR_ALIGNMENT_CHECKS))
|
| - {
|
| - do_versioning = false;
|
| - break;
|
| - }
|
| -
|
| - stmt = DR_STMT (dr);
|
| - vectype = STMT_VINFO_VECTYPE (vinfo_for_stmt (stmt));
|
| - gcc_assert (vectype);
|
| -
|
| - /* The rightmost bits of an aligned address must be zeros.
|
| - Construct the mask needed for this test. For example,
|
| - GET_MODE_SIZE for the vector mode V4SI is 16 bytes so the
|
| - mask must be 15 = 0xf. */
|
| - mask = GET_MODE_SIZE (TYPE_MODE (vectype)) - 1;
|
| -
|
| - /* FORNOW: use the same mask to test all potentially unaligned
|
| - references in the loop. The vectorizer currently supports
|
| - a single vector size, see the reference to
|
| - GET_MODE_NUNITS (TYPE_MODE (vectype)) where the
|
| - vectorization factor is computed. */
|
| - gcc_assert (!LOOP_VINFO_PTR_MASK (loop_vinfo)
|
| - || LOOP_VINFO_PTR_MASK (loop_vinfo) == mask);
|
| - LOOP_VINFO_PTR_MASK (loop_vinfo) = mask;
|
| - VEC_safe_push (gimple, heap,
|
| - LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo),
|
| - DR_STMT (dr));
|
| - }
|
| - }
|
| -
|
| - /* Versioning requires at least one misaligned data reference. */
|
| - if (VEC_length (gimple, LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo)) == 0)
|
| - do_versioning = false;
|
| - else if (!do_versioning)
|
| - VEC_truncate (gimple, LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo), 0);
|
| - }
|
| -
|
| - if (do_versioning)
|
| - {
|
| - VEC(gimple,heap) *may_misalign_stmts
|
| - = LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo);
|
| - gimple stmt;
|
| -
|
| - /* It can now be assumed that the data references in the statements
|
| - in LOOP_VINFO_MAY_MISALIGN_STMTS will be aligned in the version
|
| - of the loop being vectorized. */
|
| - for (i = 0; VEC_iterate (gimple, may_misalign_stmts, i, stmt); i++)
|
| - {
|
| - stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
|
| - dr = STMT_VINFO_DATA_REF (stmt_info);
|
| - SET_DR_MISALIGNMENT (dr, 0);
|
| - if (vect_print_dump_info (REPORT_ALIGNMENT))
|
| - fprintf (vect_dump, "Alignment of access forced using versioning.");
|
| - }
|
| -
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "Versioning for alignment will be applied.");
|
| -
|
| - /* Peeling and versioning can't be done together at this time. */
|
| - gcc_assert (! (do_peeling && do_versioning));
|
| -
|
| - stat = vect_verify_datarefs_alignment (loop_vinfo);
|
| - gcc_assert (stat);
|
| - return stat;
|
| - }
|
| -
|
| - /* This point is reached if neither peeling nor versioning is being done. */
|
| - gcc_assert (! (do_peeling || do_versioning));
|
| -
|
| - stat = vect_verify_datarefs_alignment (loop_vinfo);
|
| - return stat;
|
| -}
|
| -
|
| -
|
| -/* Function vect_analyze_data_refs_alignment
|
| -
|
| - Analyze the alignment of the data-references in the loop.
|
| - Return FALSE if a data reference is found that cannot be vectorized. */
|
| -
|
| -static bool
|
| -vect_analyze_data_refs_alignment (loop_vec_info loop_vinfo)
|
| -{
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "=== vect_analyze_data_refs_alignment ===");
|
| -
|
| - if (!vect_compute_data_refs_alignment (loop_vinfo))
|
| - {
|
| - if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
|
| - fprintf (vect_dump,
|
| - "not vectorized: can't calculate alignment for data ref.");
|
| - return false;
|
| - }
|
| -
|
| - return true;
|
| -}
|
| -
|
| -
|
| -/* Analyze groups of strided accesses: check that DR belongs to a group of
|
| - strided accesses of legal size, step, etc. Detect gaps, single element
|
| - interleaving, and other special cases. Set strided access info.
|
| - Collect groups of strided stores for further use in SLP analysis. */
|
| -
|
| -static bool
|
| -vect_analyze_group_access (struct data_reference *dr)
|
| -{
|
| - tree step = DR_STEP (dr);
|
| - tree scalar_type = TREE_TYPE (DR_REF (dr));
|
| - HOST_WIDE_INT type_size = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (scalar_type));
|
| - gimple stmt = DR_STMT (dr);
|
| - stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
|
| - loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
|
| - HOST_WIDE_INT dr_step = TREE_INT_CST_LOW (step);
|
| - HOST_WIDE_INT stride;
|
| - bool slp_impossible = false;
|
| -
|
| - /* For interleaving, STRIDE is STEP counted in elements, i.e., the size of the
|
| - interleaving group (including gaps). */
|
| - stride = dr_step / type_size;
|
| -
|
| - /* Not consecutive access is possible only if it is a part of interleaving. */
|
| - if (!DR_GROUP_FIRST_DR (vinfo_for_stmt (stmt)))
|
| - {
|
| - /* Check if it this DR is a part of interleaving, and is a single
|
| - element of the group that is accessed in the loop. */
|
| -
|
| - /* Gaps are supported only for loads. STEP must be a multiple of the type
|
| - size. The size of the group must be a power of 2. */
|
| - if (DR_IS_READ (dr)
|
| - && (dr_step % type_size) == 0
|
| - && stride > 0
|
| - && exact_log2 (stride) != -1)
|
| - {
|
| - DR_GROUP_FIRST_DR (vinfo_for_stmt (stmt)) = stmt;
|
| - DR_GROUP_SIZE (vinfo_for_stmt (stmt)) = stride;
|
| - if (vect_print_dump_info (REPORT_DR_DETAILS))
|
| - {
|
| - fprintf (vect_dump, "Detected single element interleaving %d ",
|
| - DR_GROUP_SIZE (vinfo_for_stmt (stmt)));
|
| - print_generic_expr (vect_dump, DR_REF (dr), TDF_SLIM);
|
| - fprintf (vect_dump, " step ");
|
| - print_generic_expr (vect_dump, step, TDF_SLIM);
|
| - }
|
| - return true;
|
| - }
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "not consecutive access");
|
| - return false;
|
| - }
|
| -
|
| - if (DR_GROUP_FIRST_DR (vinfo_for_stmt (stmt)) == stmt)
|
| - {
|
| - /* First stmt in the interleaving chain. Check the chain. */
|
| - gimple next = DR_GROUP_NEXT_DR (vinfo_for_stmt (stmt));
|
| - struct data_reference *data_ref = dr;
|
| - unsigned int count = 1;
|
| - tree next_step;
|
| - tree prev_init = DR_INIT (data_ref);
|
| - gimple prev = stmt;
|
| - HOST_WIDE_INT diff, count_in_bytes, gaps = 0;
|
| -
|
| - while (next)
|
| - {
|
| - /* Skip same data-refs. In case that two or more stmts share data-ref
|
| - (supported only for loads), we vectorize only the first stmt, and
|
| - the rest get their vectorized loads from the first one. */
|
| - if (!tree_int_cst_compare (DR_INIT (data_ref),
|
| - DR_INIT (STMT_VINFO_DATA_REF (
|
| - vinfo_for_stmt (next)))))
|
| - {
|
| - if (!DR_IS_READ (data_ref))
|
| - {
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "Two store stmts share the same dr.");
|
| - return false;
|
| - }
|
| -
|
| - /* Check that there is no load-store dependencies for this loads
|
| - to prevent a case of load-store-load to the same location. */
|
| - if (DR_GROUP_READ_WRITE_DEPENDENCE (vinfo_for_stmt (next))
|
| - || DR_GROUP_READ_WRITE_DEPENDENCE (vinfo_for_stmt (prev)))
|
| - {
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump,
|
| - "READ_WRITE dependence in interleaving.");
|
| - return false;
|
| - }
|
| -
|
| - /* For load use the same data-ref load. */
|
| - DR_GROUP_SAME_DR_STMT (vinfo_for_stmt (next)) = prev;
|
| -
|
| - prev = next;
|
| - next = DR_GROUP_NEXT_DR (vinfo_for_stmt (next));
|
| - continue;
|
| - }
|
| - prev = next;
|
| -
|
| - /* Check that all the accesses have the same STEP. */
|
| - next_step = DR_STEP (STMT_VINFO_DATA_REF (vinfo_for_stmt (next)));
|
| - if (tree_int_cst_compare (step, next_step))
|
| - {
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "not consecutive access in interleaving");
|
| - return false;
|
| - }
|
| -
|
| - data_ref = STMT_VINFO_DATA_REF (vinfo_for_stmt (next));
|
| - /* Check that the distance between two accesses is equal to the type
|
| - size. Otherwise, we have gaps. */
|
| - diff = (TREE_INT_CST_LOW (DR_INIT (data_ref))
|
| - - TREE_INT_CST_LOW (prev_init)) / type_size;
|
| - if (diff != 1)
|
| - {
|
| - /* FORNOW: SLP of accesses with gaps is not supported. */
|
| - slp_impossible = true;
|
| - if (!DR_IS_READ (data_ref))
|
| - {
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "interleaved store with gaps");
|
| - return false;
|
| - }
|
| -
|
| - gaps += diff - 1;
|
| - }
|
| -
|
| - /* Store the gap from the previous member of the group. If there is no
|
| - gap in the access, DR_GROUP_GAP is always 1. */
|
| - DR_GROUP_GAP (vinfo_for_stmt (next)) = diff;
|
| -
|
| - prev_init = DR_INIT (data_ref);
|
| - next = DR_GROUP_NEXT_DR (vinfo_for_stmt (next));
|
| - /* Count the number of data-refs in the chain. */
|
| - count++;
|
| - }
|
| -
|
| - /* COUNT is the number of accesses found, we multiply it by the size of
|
| - the type to get COUNT_IN_BYTES. */
|
| - count_in_bytes = type_size * count;
|
| -
|
| - /* Check that the size of the interleaving (including gaps) is not greater
|
| - than STEP. */
|
| - if (dr_step && dr_step < count_in_bytes + gaps * type_size)
|
| - {
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - {
|
| - fprintf (vect_dump, "interleaving size is greater than step for ");
|
| - print_generic_expr (vect_dump, DR_REF (dr), TDF_SLIM);
|
| - }
|
| - return false;
|
| - }
|
| -
|
| - /* Check that the size of the interleaving is equal to STEP for stores,
|
| - i.e., that there are no gaps. */
|
| - if (dr_step != count_in_bytes)
|
| - {
|
| - if (DR_IS_READ (dr))
|
| - {
|
| - slp_impossible = true;
|
| - /* There is a gap after the last load in the group. This gap is a
|
| - difference between the stride and the number of elements. When
|
| - there is no gap, this difference should be 0. */
|
| - DR_GROUP_GAP (vinfo_for_stmt (stmt)) = stride - count;
|
| - }
|
| - else
|
| - {
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "interleaved store with gaps");
|
| - return false;
|
| - }
|
| - }
|
| -
|
| - /* Check that STEP is a multiple of type size. */
|
| - if ((dr_step % type_size) != 0)
|
| - {
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - {
|
| - fprintf (vect_dump, "step is not a multiple of type size: step ");
|
| - print_generic_expr (vect_dump, step, TDF_SLIM);
|
| - fprintf (vect_dump, " size ");
|
| - print_generic_expr (vect_dump, TYPE_SIZE_UNIT (scalar_type),
|
| - TDF_SLIM);
|
| - }
|
| - return false;
|
| - }
|
| -
|
| - /* FORNOW: we handle only interleaving that is a power of 2.
|
| - We don't fail here if it may be still possible to vectorize the
|
| - group using SLP. If not, the size of the group will be checked in
|
| - vect_analyze_operations, and the vectorization will fail. */
|
| - if (exact_log2 (stride) == -1)
|
| - {
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "interleaving is not a power of 2");
|
| -
|
| - if (slp_impossible)
|
| - return false;
|
| - }
|
| - DR_GROUP_SIZE (vinfo_for_stmt (stmt)) = stride;
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "Detected interleaving of size %d", (int)stride);
|
| -
|
| - /* SLP: create an SLP data structure for every interleaving group of
|
| - stores for further analysis in vect_analyse_slp. */
|
| - if (!DR_IS_READ (dr) && !slp_impossible)
|
| - VEC_safe_push (gimple, heap, LOOP_VINFO_STRIDED_STORES (loop_vinfo), stmt);
|
| - }
|
| -
|
| - return true;
|
| -}
|
| -
|
| -
|
| -/* Analyze the access pattern of the data-reference DR.
|
| - In case of non-consecutive accesses call vect_analyze_group_access() to
|
| - analyze groups of strided accesses. */
|
| -
|
| -static bool
|
| -vect_analyze_data_ref_access (struct data_reference *dr)
|
| -{
|
| - tree step = DR_STEP (dr);
|
| - tree scalar_type = TREE_TYPE (DR_REF (dr));
|
| - gimple stmt = DR_STMT (dr);
|
| - stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
|
| - loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
|
| - struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
|
| - HOST_WIDE_INT dr_step = TREE_INT_CST_LOW (step);
|
| -
|
| - if (!step)
|
| - {
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "bad data-ref access");
|
| - return false;
|
| - }
|
| -
|
| - /* Don't allow invariant accesses. */
|
| - if (dr_step == 0)
|
| - return false;
|
| -
|
| - if (nested_in_vect_loop_p (loop, stmt))
|
| - {
|
| - /* Interleaved accesses are not yet supported within outer-loop
|
| - vectorization for references in the inner-loop. */
|
| - DR_GROUP_FIRST_DR (vinfo_for_stmt (stmt)) = NULL;
|
| -
|
| - /* For the rest of the analysis we use the outer-loop step. */
|
| - step = STMT_VINFO_DR_STEP (stmt_info);
|
| - dr_step = TREE_INT_CST_LOW (step);
|
| -
|
| - if (dr_step == 0)
|
| - {
|
| - if (vect_print_dump_info (REPORT_ALIGNMENT))
|
| - fprintf (vect_dump, "zero step in outer loop.");
|
| - if (DR_IS_READ (dr))
|
| - return true;
|
| - else
|
| - return false;
|
| - }
|
| - }
|
| -
|
| - /* Consecutive? */
|
| - if (!tree_int_cst_compare (step, TYPE_SIZE_UNIT (scalar_type)))
|
| - {
|
| - /* Mark that it is not interleaving. */
|
| - DR_GROUP_FIRST_DR (vinfo_for_stmt (stmt)) = NULL;
|
| - return true;
|
| - }
|
| -
|
| - if (nested_in_vect_loop_p (loop, stmt))
|
| - {
|
| - if (vect_print_dump_info (REPORT_ALIGNMENT))
|
| - fprintf (vect_dump, "strided access in outer loop.");
|
| - return false;
|
| - }
|
| -
|
| - /* Not consecutive access - check if it's a part of interleaving group. */
|
| - return vect_analyze_group_access (dr);
|
| -}
|
| -
|
| -
|
| -/* Function vect_analyze_data_ref_accesses.
|
| -
|
| - Analyze the access pattern of all the data references in the loop.
|
| -
|
| - FORNOW: the only access pattern that is considered vectorizable is a
|
| - simple step 1 (consecutive) access.
|
| -
|
| - FORNOW: handle only arrays and pointer accesses. */
|
| -
|
| -static bool
|
| -vect_analyze_data_ref_accesses (loop_vec_info loop_vinfo)
|
| -{
|
| - unsigned int i;
|
| - VEC (data_reference_p, heap) *datarefs = LOOP_VINFO_DATAREFS (loop_vinfo);
|
| - struct data_reference *dr;
|
| -
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "=== vect_analyze_data_ref_accesses ===");
|
| -
|
| - for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
|
| - if (!vect_analyze_data_ref_access (dr))
|
| - {
|
| - if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
|
| - fprintf (vect_dump, "not vectorized: complicated access pattern.");
|
| - return false;
|
| - }
|
| -
|
| - return true;
|
| -}
|
| -
|
| -/* Function vect_prune_runtime_alias_test_list.
|
| -
|
| - Prune a list of ddrs to be tested at run-time by versioning for alias.
|
| - Return FALSE if resulting list of ddrs is longer then allowed by
|
| - PARAM_VECT_MAX_VERSION_FOR_ALIAS_CHECKS, otherwise return TRUE. */
|
| -
|
| -static bool
|
| -vect_prune_runtime_alias_test_list (loop_vec_info loop_vinfo)
|
| -{
|
| - VEC (ddr_p, heap) * ddrs =
|
| - LOOP_VINFO_MAY_ALIAS_DDRS (loop_vinfo);
|
| - unsigned i, j;
|
| -
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "=== vect_prune_runtime_alias_test_list ===");
|
| -
|
| - for (i = 0; i < VEC_length (ddr_p, ddrs); )
|
| - {
|
| - bool found;
|
| - ddr_p ddr_i;
|
| -
|
| - ddr_i = VEC_index (ddr_p, ddrs, i);
|
| - found = false;
|
| -
|
| - for (j = 0; j < i; j++)
|
| - {
|
| - ddr_p ddr_j = VEC_index (ddr_p, ddrs, j);
|
| -
|
| - if (vect_vfa_range_equal (ddr_i, ddr_j))
|
| - {
|
| - if (vect_print_dump_info (REPORT_DR_DETAILS))
|
| - {
|
| - fprintf (vect_dump, "found equal ranges ");
|
| - print_generic_expr (vect_dump, DR_REF (DDR_A (ddr_i)), TDF_SLIM);
|
| - fprintf (vect_dump, ", ");
|
| - print_generic_expr (vect_dump, DR_REF (DDR_B (ddr_i)), TDF_SLIM);
|
| - fprintf (vect_dump, " and ");
|
| - print_generic_expr (vect_dump, DR_REF (DDR_A (ddr_j)), TDF_SLIM);
|
| - fprintf (vect_dump, ", ");
|
| - print_generic_expr (vect_dump, DR_REF (DDR_B (ddr_j)), TDF_SLIM);
|
| - }
|
| - found = true;
|
| - break;
|
| - }
|
| - }
|
| -
|
| - if (found)
|
| - {
|
| - VEC_ordered_remove (ddr_p, ddrs, i);
|
| - continue;
|
| - }
|
| - i++;
|
| - }
|
| -
|
| - if (VEC_length (ddr_p, ddrs) >
|
| - (unsigned) PARAM_VALUE (PARAM_VECT_MAX_VERSION_FOR_ALIAS_CHECKS))
|
| - {
|
| - if (vect_print_dump_info (REPORT_DR_DETAILS))
|
| - {
|
| - fprintf (vect_dump,
|
| - "disable versioning for alias - max number of generated "
|
| - "checks exceeded.");
|
| - }
|
| -
|
| - VEC_truncate (ddr_p, LOOP_VINFO_MAY_ALIAS_DDRS (loop_vinfo), 0);
|
| -
|
| - return false;
|
| - }
|
| -
|
| - return true;
|
| -}
|
| -
|
| -/* Recursively free the memory allocated for the SLP tree rooted at NODE. */
|
| -
|
| -static void
|
| -vect_free_slp_tree (slp_tree node)
|
| -{
|
| - if (!node)
|
| - return;
|
| -
|
| - if (SLP_TREE_LEFT (node))
|
| - vect_free_slp_tree (SLP_TREE_LEFT (node));
|
| -
|
| - if (SLP_TREE_RIGHT (node))
|
| - vect_free_slp_tree (SLP_TREE_RIGHT (node));
|
| -
|
| - VEC_free (gimple, heap, SLP_TREE_SCALAR_STMTS (node));
|
| -
|
| - if (SLP_TREE_VEC_STMTS (node))
|
| - VEC_free (gimple, heap, SLP_TREE_VEC_STMTS (node));
|
| -
|
| - free (node);
|
| -}
|
| -
|
| -
|
| -/* Free the memory allocated for the SLP instance. */
|
| -
|
| -void
|
| -vect_free_slp_instance (slp_instance instance)
|
| -{
|
| - vect_free_slp_tree (SLP_INSTANCE_TREE (instance));
|
| - VEC_free (int, heap, SLP_INSTANCE_LOAD_PERMUTATION (instance));
|
| - VEC_free (slp_tree, heap, SLP_INSTANCE_LOADS (instance));
|
| -}
|
| -
|
| -
|
| -/* Get the defs for the rhs of STMT (collect them in DEF_STMTS0/1), check that
|
| - they are of a legal type and that they match the defs of the first stmt of
|
| - the SLP group (stored in FIRST_STMT_...). */
|
| -
|
| -static bool
|
| -vect_get_and_check_slp_defs (loop_vec_info loop_vinfo, slp_tree slp_node,
|
| - gimple stmt, VEC (gimple, heap) **def_stmts0,
|
| - VEC (gimple, heap) **def_stmts1,
|
| - enum vect_def_type *first_stmt_dt0,
|
| - enum vect_def_type *first_stmt_dt1,
|
| - tree *first_stmt_def0_type,
|
| - tree *first_stmt_def1_type,
|
| - tree *first_stmt_const_oprnd,
|
| - int ncopies_for_cost,
|
| - bool *pattern0, bool *pattern1)
|
| -{
|
| - tree oprnd;
|
| - unsigned int i, number_of_oprnds;
|
| - tree def;
|
| - gimple def_stmt;
|
| - enum vect_def_type dt[2] = {vect_unknown_def_type, vect_unknown_def_type};
|
| - stmt_vec_info stmt_info =
|
| - vinfo_for_stmt (VEC_index (gimple, SLP_TREE_SCALAR_STMTS (slp_node), 0));
|
| - enum gimple_rhs_class rhs_class;
|
| - struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
|
| -
|
| - rhs_class = get_gimple_rhs_class (gimple_assign_rhs_code (stmt));
|
| - number_of_oprnds = gimple_num_ops (stmt) - 1; /* RHS only */
|
| -
|
| - for (i = 0; i < number_of_oprnds; i++)
|
| - {
|
| - oprnd = gimple_op (stmt, i + 1);
|
| -
|
| - if (!vect_is_simple_use (oprnd, loop_vinfo, &def_stmt, &def, &dt[i])
|
| - || (!def_stmt && dt[i] != vect_constant_def))
|
| - {
|
| - if (vect_print_dump_info (REPORT_SLP))
|
| - {
|
| - fprintf (vect_dump, "Build SLP failed: can't find def for ");
|
| - print_generic_expr (vect_dump, oprnd, TDF_SLIM);
|
| - }
|
| -
|
| - return false;
|
| - }
|
| -
|
| - /* Check if DEF_STMT is a part of a pattern and get the def stmt from
|
| - the pattern. Check that all the stmts of the node are in the
|
| - pattern. */
|
| - if (def_stmt && gimple_bb (def_stmt)
|
| - && flow_bb_inside_loop_p (loop, gimple_bb (def_stmt))
|
| - && vinfo_for_stmt (def_stmt)
|
| - && STMT_VINFO_IN_PATTERN_P (vinfo_for_stmt (def_stmt)))
|
| - {
|
| - if (!*first_stmt_dt0)
|
| - *pattern0 = true;
|
| - else
|
| - {
|
| - if (i == 1 && !*first_stmt_dt1)
|
| - *pattern1 = true;
|
| - else if ((i == 0 && !*pattern0) || (i == 1 && !*pattern1))
|
| - {
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - {
|
| - fprintf (vect_dump, "Build SLP failed: some of the stmts"
|
| - " are in a pattern, and others are not ");
|
| - print_generic_expr (vect_dump, oprnd, TDF_SLIM);
|
| - }
|
| -
|
| - return false;
|
| - }
|
| - }
|
| -
|
| - def_stmt = STMT_VINFO_RELATED_STMT (vinfo_for_stmt (def_stmt));
|
| - dt[i] = STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt));
|
| -
|
| - if (*dt == vect_unknown_def_type)
|
| - {
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "Unsupported pattern.");
|
| - return false;
|
| - }
|
| -
|
| - switch (gimple_code (def_stmt))
|
| - {
|
| - case GIMPLE_PHI:
|
| - def = gimple_phi_result (def_stmt);
|
| - break;
|
| -
|
| - case GIMPLE_ASSIGN:
|
| - def = gimple_assign_lhs (def_stmt);
|
| - break;
|
| -
|
| - default:
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "unsupported defining stmt: ");
|
| - return false;
|
| - }
|
| - }
|
| -
|
| - if (!*first_stmt_dt0)
|
| - {
|
| - /* op0 of the first stmt of the group - store its info. */
|
| - *first_stmt_dt0 = dt[i];
|
| - if (def)
|
| - *first_stmt_def0_type = TREE_TYPE (def);
|
| - else
|
| - *first_stmt_const_oprnd = oprnd;
|
| -
|
| - /* Analyze costs (for the first stmt of the group only). */
|
| - if (rhs_class != GIMPLE_SINGLE_RHS)
|
| - /* Not memory operation (we don't call this functions for loads). */
|
| - vect_model_simple_cost (stmt_info, ncopies_for_cost, dt, slp_node);
|
| - else
|
| - /* Store. */
|
| - vect_model_store_cost (stmt_info, ncopies_for_cost, dt[0], slp_node);
|
| - }
|
| -
|
| - else
|
| - {
|
| - if (!*first_stmt_dt1 && i == 1)
|
| - {
|
| - /* op1 of the first stmt of the group - store its info. */
|
| - *first_stmt_dt1 = dt[i];
|
| - if (def)
|
| - *first_stmt_def1_type = TREE_TYPE (def);
|
| - else
|
| - {
|
| - /* We assume that the stmt contains only one constant
|
| - operand. We fail otherwise, to be on the safe side. */
|
| - if (*first_stmt_const_oprnd)
|
| - {
|
| - if (vect_print_dump_info (REPORT_SLP))
|
| - fprintf (vect_dump, "Build SLP failed: two constant "
|
| - "oprnds in stmt");
|
| - return false;
|
| - }
|
| - *first_stmt_const_oprnd = oprnd;
|
| - }
|
| - }
|
| - else
|
| - {
|
| - /* Not first stmt of the group, check that the def-stmt/s match
|
| - the def-stmt/s of the first stmt. */
|
| - if ((i == 0
|
| - && (*first_stmt_dt0 != dt[i]
|
| - || (*first_stmt_def0_type && def
|
| - && *first_stmt_def0_type != TREE_TYPE (def))))
|
| - || (i == 1
|
| - && (*first_stmt_dt1 != dt[i]
|
| - || (*first_stmt_def1_type && def
|
| - && *first_stmt_def1_type != TREE_TYPE (def))))
|
| - || (!def
|
| - && TREE_TYPE (*first_stmt_const_oprnd)
|
| - != TREE_TYPE (oprnd)))
|
| - {
|
| - if (vect_print_dump_info (REPORT_SLP))
|
| - fprintf (vect_dump, "Build SLP failed: different types ");
|
| -
|
| - return false;
|
| - }
|
| - }
|
| - }
|
| -
|
| - /* Check the types of the definitions. */
|
| - switch (dt[i])
|
| - {
|
| - case vect_constant_def:
|
| - case vect_invariant_def:
|
| - break;
|
| -
|
| - case vect_loop_def:
|
| - if (i == 0)
|
| - VEC_safe_push (gimple, heap, *def_stmts0, def_stmt);
|
| - else
|
| - VEC_safe_push (gimple, heap, *def_stmts1, def_stmt);
|
| - break;
|
| -
|
| - default:
|
| - /* FORNOW: Not supported. */
|
| - if (vect_print_dump_info (REPORT_SLP))
|
| - {
|
| - fprintf (vect_dump, "Build SLP failed: illegal type of def ");
|
| - print_generic_expr (vect_dump, def, TDF_SLIM);
|
| - }
|
| -
|
| - return false;
|
| - }
|
| - }
|
| -
|
| - return true;
|
| -}
|
| -
|
| -
|
| -/* Recursively build an SLP tree starting from NODE.
|
| - Fail (and return FALSE) if def-stmts are not isomorphic, require data
|
| - permutation or are of unsupported types of operation. Otherwise, return
|
| - TRUE. */
|
| -
|
| -static bool
|
| -vect_build_slp_tree (loop_vec_info loop_vinfo, slp_tree *node,
|
| - unsigned int group_size,
|
| - int *inside_cost, int *outside_cost,
|
| - int ncopies_for_cost, unsigned int *max_nunits,
|
| - VEC (int, heap) **load_permutation,
|
| - VEC (slp_tree, heap) **loads)
|
| -{
|
| - VEC (gimple, heap) *def_stmts0 = VEC_alloc (gimple, heap, group_size);
|
| - VEC (gimple, heap) *def_stmts1 = VEC_alloc (gimple, heap, group_size);
|
| - unsigned int i;
|
| - VEC (gimple, heap) *stmts = SLP_TREE_SCALAR_STMTS (*node);
|
| - gimple stmt = VEC_index (gimple, stmts, 0);
|
| - enum vect_def_type first_stmt_dt0 = 0, first_stmt_dt1 = 0;
|
| - enum tree_code first_stmt_code = 0, rhs_code;
|
| - tree first_stmt_def1_type = NULL_TREE, first_stmt_def0_type = NULL_TREE;
|
| - tree lhs;
|
| - bool stop_recursion = false, need_same_oprnds = false;
|
| - tree vectype, scalar_type, first_op1 = NULL_TREE;
|
| - unsigned int vectorization_factor = 0, ncopies;
|
| - optab optab;
|
| - int icode;
|
| - enum machine_mode optab_op2_mode;
|
| - enum machine_mode vec_mode;
|
| - tree first_stmt_const_oprnd = NULL_TREE;
|
| - struct data_reference *first_dr;
|
| - bool pattern0 = false, pattern1 = false;
|
| - HOST_WIDE_INT dummy;
|
| - bool permutation = false;
|
| - unsigned int load_place;
|
| - gimple first_load;
|
| -
|
| - /* For every stmt in NODE find its def stmt/s. */
|
| - for (i = 0; VEC_iterate (gimple, stmts, i, stmt); i++)
|
| - {
|
| - if (vect_print_dump_info (REPORT_SLP))
|
| - {
|
| - fprintf (vect_dump, "Build SLP for ");
|
| - print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
|
| - }
|
| -
|
| - lhs = gimple_get_lhs (stmt);
|
| - if (lhs == NULL_TREE)
|
| - {
|
| - if (vect_print_dump_info (REPORT_SLP))
|
| - {
|
| - fprintf (vect_dump,
|
| - "Build SLP failed: not GIMPLE_ASSIGN nor GIMPLE_CALL");
|
| - print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
|
| - }
|
| -
|
| - return false;
|
| - }
|
| -
|
| - scalar_type = vect_get_smallest_scalar_type (stmt, &dummy, &dummy);
|
| - vectype = get_vectype_for_scalar_type (scalar_type);
|
| - if (!vectype)
|
| - {
|
| - if (vect_print_dump_info (REPORT_SLP))
|
| - {
|
| - fprintf (vect_dump, "Build SLP failed: unsupported data-type ");
|
| - print_generic_expr (vect_dump, scalar_type, TDF_SLIM);
|
| - }
|
| - return false;
|
| - }
|
| -
|
| - gcc_assert (LOOP_VINFO_VECT_FACTOR (loop_vinfo));
|
| - vectorization_factor = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
|
| - ncopies = vectorization_factor / TYPE_VECTOR_SUBPARTS (vectype);
|
| - if (ncopies > 1 && vect_print_dump_info (REPORT_SLP))
|
| - fprintf (vect_dump, "SLP with multiple types ");
|
| -
|
| - /* In case of multiple types we need to detect the smallest type. */
|
| - if (*max_nunits < TYPE_VECTOR_SUBPARTS (vectype))
|
| - *max_nunits = TYPE_VECTOR_SUBPARTS (vectype);
|
| -
|
| - if (is_gimple_call (stmt))
|
| - rhs_code = CALL_EXPR;
|
| - else
|
| - rhs_code = gimple_assign_rhs_code (stmt);
|
| -
|
| - /* Check the operation. */
|
| - if (i == 0)
|
| - {
|
| - first_stmt_code = rhs_code;
|
| -
|
| - /* 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->handlers[(int) vec_mode].insn_code
|
| - == 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 (vect_print_dump_info (REPORT_SLP))
|
| - fprintf (vect_dump, "Build SLP failed: no optab.");
|
| - return false;
|
| - }
|
| - icode = (int) optab->handlers[(int) vec_mode].insn_code;
|
| - if (icode == CODE_FOR_nothing)
|
| - {
|
| - if (vect_print_dump_info (REPORT_SLP))
|
| - fprintf (vect_dump, "Build SLP failed: "
|
| - "op not supported by target.");
|
| - 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 (first_stmt_code != rhs_code
|
| - && (first_stmt_code != IMAGPART_EXPR
|
| - || rhs_code != REALPART_EXPR)
|
| - && (first_stmt_code != REALPART_EXPR
|
| - || rhs_code != IMAGPART_EXPR))
|
| - {
|
| - if (vect_print_dump_info (REPORT_SLP))
|
| - {
|
| - fprintf (vect_dump,
|
| - "Build SLP failed: different operation in stmt ");
|
| - print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
|
| - }
|
| -
|
| - return false;
|
| - }
|
| -
|
| - if (need_same_oprnds
|
| - && !operand_equal_p (first_op1, gimple_assign_rhs2 (stmt), 0))
|
| - {
|
| - if (vect_print_dump_info (REPORT_SLP))
|
| - {
|
| - fprintf (vect_dump,
|
| - "Build SLP failed: different shift arguments in ");
|
| - print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
|
| - }
|
| -
|
| - return false;
|
| - }
|
| - }
|
| -
|
| - /* Strided store or load. */
|
| - if (STMT_VINFO_STRIDED_ACCESS (vinfo_for_stmt (stmt)))
|
| - {
|
| - if (REFERENCE_CLASS_P (lhs))
|
| - {
|
| - /* Store. */
|
| - if (!vect_get_and_check_slp_defs (loop_vinfo, *node, stmt,
|
| - &def_stmts0, &def_stmts1,
|
| - &first_stmt_dt0,
|
| - &first_stmt_dt1,
|
| - &first_stmt_def0_type,
|
| - &first_stmt_def1_type,
|
| - &first_stmt_const_oprnd,
|
| - ncopies_for_cost,
|
| - &pattern0, &pattern1))
|
| - return false;
|
| - }
|
| - else
|
| - {
|
| - /* Load. */
|
| - /* FORNOW: Check that there is no gap between the loads. */
|
| - if ((DR_GROUP_FIRST_DR (vinfo_for_stmt (stmt)) == stmt
|
| - && DR_GROUP_GAP (vinfo_for_stmt (stmt)) != 0)
|
| - || (DR_GROUP_FIRST_DR (vinfo_for_stmt (stmt)) != stmt
|
| - && DR_GROUP_GAP (vinfo_for_stmt (stmt)) != 1))
|
| - {
|
| - if (vect_print_dump_info (REPORT_SLP))
|
| - {
|
| - fprintf (vect_dump, "Build SLP failed: strided "
|
| - "loads have gaps ");
|
| - print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
|
| - }
|
| -
|
| - return false;
|
| - }
|
| -
|
| - /* Check that the size of interleaved loads group is not
|
| - greater than the SLP group size. */
|
| - if (DR_GROUP_SIZE (vinfo_for_stmt (stmt))
|
| - > ncopies * group_size)
|
| - {
|
| - if (vect_print_dump_info (REPORT_SLP))
|
| - {
|
| - fprintf (vect_dump, "Build SLP failed: the number of "
|
| - "interleaved loads is greater than"
|
| - " the SLP group size ");
|
| - print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
|
| - }
|
| -
|
| - return false;
|
| - }
|
| -
|
| - first_load = DR_GROUP_FIRST_DR (vinfo_for_stmt (stmt));
|
| -
|
| - if (first_load == stmt)
|
| - {
|
| - first_dr = STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt));
|
| - if (vect_supportable_dr_alignment (first_dr)
|
| - == dr_unaligned_unsupported)
|
| - {
|
| - if (vect_print_dump_info (REPORT_SLP))
|
| - {
|
| - fprintf (vect_dump, "Build SLP failed: unsupported "
|
| - "unaligned load ");
|
| - print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
|
| - }
|
| -
|
| - return false;
|
| - }
|
| -
|
| - /* Analyze costs (for the first stmt in the group). */
|
| - vect_model_load_cost (vinfo_for_stmt (stmt),
|
| - ncopies_for_cost, *node);
|
| - }
|
| -
|
| - /* Store the place of this load in the interleaving chain. In
|
| - case that permutation is needed we later decide if a specific
|
| - permutation is supported. */
|
| - load_place = vect_get_place_in_interleaving_chain (stmt,
|
| - first_load);
|
| - if (load_place != i)
|
| - permutation = true;
|
| -
|
| - VEC_safe_push (int, heap, *load_permutation, load_place);
|
| -
|
| - /* We stop the tree when we reach a group of loads. */
|
| - stop_recursion = true;
|
| - continue;
|
| - }
|
| - } /* Strided access. */
|
| - else
|
| - {
|
| - if (TREE_CODE_CLASS (rhs_code) == tcc_reference)
|
| - {
|
| - /* Not strided load. */
|
| - if (vect_print_dump_info (REPORT_SLP))
|
| - {
|
| - fprintf (vect_dump, "Build SLP failed: not strided load ");
|
| - print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
|
| - }
|
| -
|
| - /* FORNOW: Not strided loads are not supported. */
|
| - return false;
|
| - }
|
| -
|
| - /* Not memory operation. */
|
| - if (TREE_CODE_CLASS (rhs_code) != tcc_binary
|
| - && TREE_CODE_CLASS (rhs_code) != tcc_unary)
|
| - {
|
| - if (vect_print_dump_info (REPORT_SLP))
|
| - {
|
| - fprintf (vect_dump, "Build SLP failed: operation");
|
| - fprintf (vect_dump, " unsupported ");
|
| - print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
|
| - }
|
| -
|
| - return false;
|
| - }
|
| -
|
| - /* Find the def-stmts. */
|
| - if (!vect_get_and_check_slp_defs (loop_vinfo, *node, stmt,
|
| - &def_stmts0, &def_stmts1,
|
| - &first_stmt_dt0, &first_stmt_dt1,
|
| - &first_stmt_def0_type,
|
| - &first_stmt_def1_type,
|
| - &first_stmt_const_oprnd,
|
| - ncopies_for_cost,
|
| - &pattern0, &pattern1))
|
| - return false;
|
| - }
|
| - }
|
| -
|
| - /* Add the costs of the node to the overall instance costs. */
|
| - *inside_cost += SLP_TREE_INSIDE_OF_LOOP_COST (*node);
|
| - *outside_cost += SLP_TREE_OUTSIDE_OF_LOOP_COST (*node);
|
| -
|
| - /* Strided loads were reached - stop the recursion. */
|
| - if (stop_recursion)
|
| - {
|
| - if (permutation)
|
| - {
|
| - VEC_safe_push (slp_tree, heap, *loads, *node);
|
| - *inside_cost += TARG_VEC_PERMUTE_COST * group_size;
|
| - }
|
| -
|
| - return true;
|
| - }
|
| -
|
| - /* Create SLP_TREE nodes for the definition node/s. */
|
| - if (first_stmt_dt0 == vect_loop_def)
|
| - {
|
| - slp_tree left_node = XNEW (struct _slp_tree);
|
| - SLP_TREE_SCALAR_STMTS (left_node) = def_stmts0;
|
| - SLP_TREE_VEC_STMTS (left_node) = NULL;
|
| - SLP_TREE_LEFT (left_node) = NULL;
|
| - SLP_TREE_RIGHT (left_node) = NULL;
|
| - SLP_TREE_OUTSIDE_OF_LOOP_COST (left_node) = 0;
|
| - SLP_TREE_INSIDE_OF_LOOP_COST (left_node) = 0;
|
| - if (!vect_build_slp_tree (loop_vinfo, &left_node, group_size,
|
| - inside_cost, outside_cost, ncopies_for_cost,
|
| - max_nunits, load_permutation, loads))
|
| - return false;
|
| -
|
| - SLP_TREE_LEFT (*node) = left_node;
|
| - }
|
| -
|
| - if (first_stmt_dt1 == vect_loop_def)
|
| - {
|
| - slp_tree right_node = XNEW (struct _slp_tree);
|
| - SLP_TREE_SCALAR_STMTS (right_node) = def_stmts1;
|
| - SLP_TREE_VEC_STMTS (right_node) = NULL;
|
| - SLP_TREE_LEFT (right_node) = NULL;
|
| - SLP_TREE_RIGHT (right_node) = NULL;
|
| - SLP_TREE_OUTSIDE_OF_LOOP_COST (right_node) = 0;
|
| - SLP_TREE_INSIDE_OF_LOOP_COST (right_node) = 0;
|
| - if (!vect_build_slp_tree (loop_vinfo, &right_node, group_size,
|
| - inside_cost, outside_cost, ncopies_for_cost,
|
| - max_nunits, load_permutation, loads))
|
| - return false;
|
| -
|
| - SLP_TREE_RIGHT (*node) = right_node;
|
| - }
|
| -
|
| - return true;
|
| -}
|
| -
|
| -
|
| -static void
|
| -vect_print_slp_tree (slp_tree node)
|
| -{
|
| - int i;
|
| - gimple stmt;
|
| -
|
| - if (!node)
|
| - return;
|
| -
|
| - fprintf (vect_dump, "node ");
|
| - for (i = 0; VEC_iterate (gimple, SLP_TREE_SCALAR_STMTS (node), i, stmt); i++)
|
| - {
|
| - fprintf (vect_dump, "\n\tstmt %d ", i);
|
| - print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
|
| - }
|
| - fprintf (vect_dump, "\n");
|
| -
|
| - vect_print_slp_tree (SLP_TREE_LEFT (node));
|
| - vect_print_slp_tree (SLP_TREE_RIGHT (node));
|
| -}
|
| -
|
| -
|
| -/* Mark the tree rooted at NODE with MARK (PURE_SLP or HYBRID).
|
| - If MARK is HYBRID, it refers to a specific stmt in NODE (the stmt at index
|
| - J). Otherwise, MARK is PURE_SLP and J is -1, which indicates that all the
|
| - stmts in NODE are to be marked. */
|
| -
|
| -static void
|
| -vect_mark_slp_stmts (slp_tree node, enum slp_vect_type mark, int j)
|
| -{
|
| - int i;
|
| - gimple stmt;
|
| -
|
| - if (!node)
|
| - return;
|
| -
|
| - for (i = 0; VEC_iterate (gimple, SLP_TREE_SCALAR_STMTS (node), i, stmt); i++)
|
| - if (j < 0 || i == j)
|
| - STMT_SLP_TYPE (vinfo_for_stmt (stmt)) = mark;
|
| -
|
| - vect_mark_slp_stmts (SLP_TREE_LEFT (node), mark, j);
|
| - vect_mark_slp_stmts (SLP_TREE_RIGHT (node), mark, j);
|
| -}
|
| -
|
| -
|
| -/* Check if the permutation required by the SLP INSTANCE is supported.
|
| - Reorganize the SLP nodes stored in SLP_INSTANCE_LOADS if needed. */
|
| -
|
| -static bool
|
| -vect_supported_slp_permutation_p (slp_instance instance)
|
| -{
|
| - slp_tree node = VEC_index (slp_tree, SLP_INSTANCE_LOADS (instance), 0);
|
| - gimple stmt = VEC_index (gimple, SLP_TREE_SCALAR_STMTS (node), 0);
|
| - gimple first_load = DR_GROUP_FIRST_DR (vinfo_for_stmt (stmt));
|
| - VEC (slp_tree, heap) *sorted_loads = NULL;
|
| - int index;
|
| - slp_tree *tmp_loads = NULL;
|
| - int group_size = SLP_INSTANCE_GROUP_SIZE (instance), i, j;
|
| - slp_tree load;
|
| -
|
| - /* FORNOW: The only supported loads permutation is loads from the same
|
| - location in all the loads in the node, when the data-refs in
|
| - nodes of LOADS constitute an interleaving chain.
|
| - Sort the nodes according to the order of accesses in the chain. */
|
| - tmp_loads = (slp_tree *) xmalloc (sizeof (slp_tree) * group_size);
|
| - for (i = 0, j = 0;
|
| - VEC_iterate (int, SLP_INSTANCE_LOAD_PERMUTATION (instance), i, index)
|
| - && VEC_iterate (slp_tree, SLP_INSTANCE_LOADS (instance), j, load);
|
| - i += group_size, j++)
|
| - {
|
| - gimple scalar_stmt = VEC_index (gimple, SLP_TREE_SCALAR_STMTS (load), 0);
|
| - /* Check that the loads are all in the same interleaving chain. */
|
| - if (DR_GROUP_FIRST_DR (vinfo_for_stmt (scalar_stmt)) != first_load)
|
| - {
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - {
|
| - fprintf (vect_dump, "Build SLP failed: unsupported data "
|
| - "permutation ");
|
| - print_gimple_stmt (vect_dump, scalar_stmt, 0, TDF_SLIM);
|
| - }
|
| -
|
| - free (tmp_loads);
|
| - return false;
|
| - }
|
| -
|
| - tmp_loads[index] = load;
|
| - }
|
| -
|
| - sorted_loads = VEC_alloc (slp_tree, heap, group_size);
|
| - for (i = 0; i < group_size; i++)
|
| - VEC_safe_push (slp_tree, heap, sorted_loads, tmp_loads[i]);
|
| -
|
| - VEC_free (slp_tree, heap, SLP_INSTANCE_LOADS (instance));
|
| - SLP_INSTANCE_LOADS (instance) = sorted_loads;
|
| - free (tmp_loads);
|
| -
|
| - if (!vect_transform_slp_perm_load (stmt, NULL, NULL,
|
| - SLP_INSTANCE_UNROLLING_FACTOR (instance),
|
| - instance, true))
|
| - return false;
|
| -
|
| - return true;
|
| -}
|
| -
|
| -
|
| -/* Check if the required load permutation is supported.
|
| - LOAD_PERMUTATION contains a list of indices of the loads.
|
| - In SLP this permutation is relative to the order of strided stores that are
|
| - the base of the SLP instance. */
|
| -
|
| -static bool
|
| -vect_supported_load_permutation_p (slp_instance slp_instn, int group_size,
|
| - VEC (int, heap) *load_permutation)
|
| -{
|
| - int i = 0, j, prev = -1, next, k;
|
| - bool supported;
|
| - sbitmap load_index;
|
| -
|
| - /* FORNOW: permutations are only supported for loop-aware SLP. */
|
| - if (!slp_instn)
|
| - return false;
|
| -
|
| - if (vect_print_dump_info (REPORT_SLP))
|
| - {
|
| - fprintf (vect_dump, "Load permutation ");
|
| - for (i = 0; VEC_iterate (int, load_permutation, i, next); i++)
|
| - fprintf (vect_dump, "%d ", next);
|
| - }
|
| -
|
| - /* FORNOW: the only supported permutation is 0..01..1.. of length equal to
|
| - GROUP_SIZE and where each sequence of same drs is of GROUP_SIZE length as
|
| - well. */
|
| - if (VEC_length (int, load_permutation)
|
| - != (unsigned int) (group_size * group_size))
|
| - return false;
|
| -
|
| - supported = true;
|
| - load_index = sbitmap_alloc (group_size);
|
| - sbitmap_zero (load_index);
|
| - for (j = 0; j < group_size; j++)
|
| - {
|
| - for (i = j * group_size, k = 0;
|
| - VEC_iterate (int, load_permutation, i, next) && k < group_size;
|
| - i++, k++)
|
| - {
|
| - if (i != j * group_size && next != prev)
|
| - {
|
| - supported = false;
|
| - break;
|
| - }
|
| -
|
| - prev = next;
|
| - }
|
| -
|
| - if (TEST_BIT (load_index, prev))
|
| - {
|
| - supported = false;
|
| - break;
|
| - }
|
| -
|
| - SET_BIT (load_index, prev);
|
| - }
|
| -
|
| - sbitmap_free (load_index);
|
| -
|
| - if (supported && i == group_size * group_size
|
| - && vect_supported_slp_permutation_p (slp_instn))
|
| - return true;
|
| -
|
| - return false;
|
| -}
|
| -
|
| -
|
| -/* Find the first load in the loop that belongs to INSTANCE.
|
| - When loads are in several SLP nodes, there can be a case in which the first
|
| - load does not appear in the first SLP node to be transformed, causing
|
| - incorrect order of statements. Since we generate all the loads together,
|
| - they must be inserted before the first load of the SLP instance and not
|
| - before the first load of the first node of the instance. */
|
| -static gimple
|
| -vect_find_first_load_in_slp_instance (slp_instance instance)
|
| -{
|
| - int i, j;
|
| - slp_tree load_node;
|
| - gimple first_load = NULL, load;
|
| -
|
| - for (i = 0;
|
| - VEC_iterate (slp_tree, SLP_INSTANCE_LOADS (instance), i, load_node);
|
| - i++)
|
| - for (j = 0;
|
| - VEC_iterate (gimple, SLP_TREE_SCALAR_STMTS (load_node), j, load);
|
| - j++)
|
| - first_load = get_earlier_stmt (load, first_load);
|
| -
|
| - return first_load;
|
| -}
|
| -
|
| -
|
| -/* Analyze an SLP instance starting from a group of strided 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 (loop_vec_info loop_vinfo, gimple stmt)
|
| -{
|
| - slp_instance new_instance;
|
| - slp_tree node = XNEW (struct _slp_tree);
|
| - unsigned int group_size = DR_GROUP_SIZE (vinfo_for_stmt (stmt));
|
| - unsigned int unrolling_factor = 1, nunits;
|
| - tree vectype, scalar_type;
|
| - gimple next;
|
| - unsigned int vectorization_factor = 0, ncopies;
|
| - bool slp_impossible = false;
|
| - int inside_cost = 0, outside_cost = 0, ncopies_for_cost;
|
| - unsigned int max_nunits = 0;
|
| - VEC (int, heap) *load_permutation;
|
| - VEC (slp_tree, heap) *loads;
|
| -
|
| - scalar_type = TREE_TYPE (DR_REF (STMT_VINFO_DATA_REF (
|
| - vinfo_for_stmt (stmt))));
|
| - vectype = get_vectype_for_scalar_type (scalar_type);
|
| - if (!vectype)
|
| - {
|
| - if (vect_print_dump_info (REPORT_SLP))
|
| - {
|
| - fprintf (vect_dump, "Build SLP failed: unsupported data-type ");
|
| - print_generic_expr (vect_dump, scalar_type, TDF_SLIM);
|
| - }
|
| - return false;
|
| - }
|
| -
|
| - nunits = TYPE_VECTOR_SUBPARTS (vectype);
|
| - vectorization_factor = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
|
| - ncopies = vectorization_factor / nunits;
|
| -
|
| - /* Create a node (a root of the SLP tree) for the packed strided stores. */
|
| - SLP_TREE_SCALAR_STMTS (node) = VEC_alloc (gimple, heap, group_size);
|
| - next = stmt;
|
| - /* Collect the stores and store them in SLP_TREE_SCALAR_STMTS. */
|
| - while (next)
|
| - {
|
| - VEC_safe_push (gimple, heap, SLP_TREE_SCALAR_STMTS (node), next);
|
| - next = DR_GROUP_NEXT_DR (vinfo_for_stmt (next));
|
| - }
|
| -
|
| - SLP_TREE_VEC_STMTS (node) = NULL;
|
| - SLP_TREE_NUMBER_OF_VEC_STMTS (node) = 0;
|
| - SLP_TREE_LEFT (node) = NULL;
|
| - SLP_TREE_RIGHT (node) = NULL;
|
| - SLP_TREE_OUTSIDE_OF_LOOP_COST (node) = 0;
|
| - SLP_TREE_INSIDE_OF_LOOP_COST (node) = 0;
|
| -
|
| - /* Calculate the unrolling factor. */
|
| - unrolling_factor = least_common_multiple (nunits, group_size) / group_size;
|
| -
|
| - /* Calculate the number of vector stmts to create based on the unrolling
|
| - factor (number of vectors is 1 if NUNITS >= GROUP_SIZE, and is
|
| - GROUP_SIZE / NUNITS otherwise. */
|
| - ncopies_for_cost = unrolling_factor * group_size / nunits;
|
| -
|
| - load_permutation = VEC_alloc (int, heap, group_size * group_size);
|
| - loads = VEC_alloc (slp_tree, heap, group_size);
|
| -
|
| - /* Build the tree for the SLP instance. */
|
| - if (vect_build_slp_tree (loop_vinfo, &node, group_size, &inside_cost,
|
| - &outside_cost, ncopies_for_cost, &max_nunits,
|
| - &load_permutation, &loads))
|
| - {
|
| - /* Create a new SLP instance. */
|
| - new_instance = XNEW (struct _slp_instance);
|
| - SLP_INSTANCE_TREE (new_instance) = node;
|
| - SLP_INSTANCE_GROUP_SIZE (new_instance) = group_size;
|
| - /* Calculate the unrolling factor based on the smallest type in the
|
| - loop. */
|
| - if (max_nunits > nunits)
|
| - unrolling_factor = least_common_multiple (max_nunits, group_size)
|
| - / group_size;
|
| -
|
| - SLP_INSTANCE_UNROLLING_FACTOR (new_instance) = unrolling_factor;
|
| - SLP_INSTANCE_OUTSIDE_OF_LOOP_COST (new_instance) = outside_cost;
|
| - SLP_INSTANCE_INSIDE_OF_LOOP_COST (new_instance) = inside_cost;
|
| - SLP_INSTANCE_LOADS (new_instance) = loads;
|
| - SLP_INSTANCE_FIRST_LOAD_STMT (new_instance) = NULL;
|
| - SLP_INSTANCE_LOAD_PERMUTATION (new_instance) = load_permutation;
|
| - if (VEC_length (slp_tree, loads))
|
| - {
|
| - if (!vect_supported_load_permutation_p (new_instance, group_size,
|
| - load_permutation))
|
| - {
|
| - if (vect_print_dump_info (REPORT_SLP))
|
| - {
|
| - fprintf (vect_dump, "Build SLP failed: unsupported load "
|
| - "permutation ");
|
| - print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
|
| - }
|
| -
|
| - vect_free_slp_instance (new_instance);
|
| - return false;
|
| - }
|
| -
|
| - SLP_INSTANCE_FIRST_LOAD_STMT (new_instance)
|
| - = vect_find_first_load_in_slp_instance (new_instance);
|
| - }
|
| - else
|
| - VEC_free (int, heap, SLP_INSTANCE_LOAD_PERMUTATION (new_instance));
|
| -
|
| - VEC_safe_push (slp_instance, heap, LOOP_VINFO_SLP_INSTANCES (loop_vinfo),
|
| - new_instance);
|
| - if (vect_print_dump_info (REPORT_SLP))
|
| - vect_print_slp_tree (node);
|
| -
|
| - return true;
|
| - }
|
| -
|
| - /* Failed to SLP. */
|
| - /* Free the allocated memory. */
|
| - vect_free_slp_tree (node);
|
| - VEC_free (int, heap, load_permutation);
|
| - VEC_free (slp_tree, heap, loads);
|
| -
|
| - if (slp_impossible)
|
| - return false;
|
| -
|
| - /* SLP failed for this instance, but it is still possible to SLP other stmts
|
| - in the loop. */
|
| - return true;
|
| -}
|
| -
|
| -
|
| -/* Check if there are stmts in the loop can be vectorized using SLP. Build SLP
|
| - trees of packed scalar stmts if SLP is possible. */
|
| -
|
| -static bool
|
| -vect_analyze_slp (loop_vec_info loop_vinfo)
|
| -{
|
| - unsigned int i;
|
| - VEC (gimple, heap) *strided_stores = LOOP_VINFO_STRIDED_STORES (loop_vinfo);
|
| - gimple store;
|
| -
|
| - if (vect_print_dump_info (REPORT_SLP))
|
| - fprintf (vect_dump, "=== vect_analyze_slp ===");
|
| -
|
| - for (i = 0; VEC_iterate (gimple, strided_stores, i, store); i++)
|
| - if (!vect_analyze_slp_instance (loop_vinfo, store))
|
| - {
|
| - /* SLP failed. No instance can be SLPed in the loop. */
|
| - if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
|
| - fprintf (vect_dump, "SLP failed.");
|
| -
|
| - return false;
|
| - }
|
| -
|
| - return true;
|
| -}
|
| -
|
| -
|
| -/* For each possible SLP instance decide whether to SLP it and calculate overall
|
| - unrolling factor needed to SLP the loop. */
|
| -
|
| -static void
|
| -vect_make_slp_decision (loop_vec_info loop_vinfo)
|
| -{
|
| - unsigned int i, unrolling_factor = 1;
|
| - VEC (slp_instance, heap) *slp_instances = LOOP_VINFO_SLP_INSTANCES (loop_vinfo);
|
| - slp_instance instance;
|
| - int decided_to_slp = 0;
|
| -
|
| - if (vect_print_dump_info (REPORT_SLP))
|
| - fprintf (vect_dump, "=== vect_make_slp_decision ===");
|
| -
|
| - for (i = 0; VEC_iterate (slp_instance, slp_instances, i, instance); i++)
|
| - {
|
| - /* FORNOW: SLP if you can. */
|
| - if (unrolling_factor < SLP_INSTANCE_UNROLLING_FACTOR (instance))
|
| - unrolling_factor = SLP_INSTANCE_UNROLLING_FACTOR (instance);
|
| -
|
| - /* Mark all the stmts that belong to INSTANCE as PURE_SLP stmts. Later we
|
| - call vect_detect_hybrid_slp () to find stmts that need hybrid SLP and
|
| - loop-based vectorization. Such stmts will be marked as HYBRID. */
|
| - vect_mark_slp_stmts (SLP_INSTANCE_TREE (instance), pure_slp, -1);
|
| - decided_to_slp++;
|
| - }
|
| -
|
| - LOOP_VINFO_SLP_UNROLLING_FACTOR (loop_vinfo) = unrolling_factor;
|
| -
|
| - if (decided_to_slp && vect_print_dump_info (REPORT_SLP))
|
| - fprintf (vect_dump, "Decided to SLP %d instances. Unrolling factor %d",
|
| - decided_to_slp, unrolling_factor);
|
| -}
|
| -
|
| -
|
| -/* Find stmts that must be both vectorized and SLPed (since they feed stmts that
|
| - can't be SLPed) in the tree rooted at NODE. Mark such stmts as HYBRID. */
|
| -
|
| -static void
|
| -vect_detect_hybrid_slp_stmts (slp_tree node)
|
| -{
|
| - int i;
|
| - gimple stmt;
|
| - imm_use_iterator imm_iter;
|
| - gimple use_stmt;
|
| -
|
| - if (!node)
|
| - return;
|
| -
|
| - for (i = 0; VEC_iterate (gimple, SLP_TREE_SCALAR_STMTS (node), i, stmt); i++)
|
| - if (PURE_SLP_STMT (vinfo_for_stmt (stmt))
|
| - && TREE_CODE (gimple_op (stmt, 0)) == SSA_NAME)
|
| - FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, gimple_op (stmt, 0))
|
| - if (vinfo_for_stmt (use_stmt)
|
| - && !STMT_SLP_TYPE (vinfo_for_stmt (use_stmt))
|
| - && STMT_VINFO_RELEVANT (vinfo_for_stmt (use_stmt)))
|
| - vect_mark_slp_stmts (node, hybrid, i);
|
| -
|
| - vect_detect_hybrid_slp_stmts (SLP_TREE_LEFT (node));
|
| - vect_detect_hybrid_slp_stmts (SLP_TREE_RIGHT (node));
|
| -}
|
| -
|
| -
|
| -/* Find stmts that must be both vectorized and SLPed. */
|
| -
|
| -static void
|
| -vect_detect_hybrid_slp (loop_vec_info loop_vinfo)
|
| -{
|
| - unsigned int i;
|
| - VEC (slp_instance, heap) *slp_instances = LOOP_VINFO_SLP_INSTANCES (loop_vinfo);
|
| - slp_instance instance;
|
| -
|
| - if (vect_print_dump_info (REPORT_SLP))
|
| - fprintf (vect_dump, "=== vect_detect_hybrid_slp ===");
|
| -
|
| - for (i = 0; VEC_iterate (slp_instance, slp_instances, i, instance); i++)
|
| - vect_detect_hybrid_slp_stmts (SLP_INSTANCE_TREE (instance));
|
| -}
|
| -
|
| -
|
| -/* Function vect_analyze_data_refs.
|
| -
|
| - Find all the data references in the loop.
|
| -
|
| - The general structure of the analysis of data refs in the vectorizer is as
|
| - follows:
|
| - 1- vect_analyze_data_refs(loop): call compute_data_dependences_for_loop to
|
| - find and analyze all data-refs in the loop and their dependences.
|
| - 2- vect_analyze_dependences(): apply dependence testing using ddrs.
|
| - 3- vect_analyze_drs_alignment(): check that ref_stmt.alignment is ok.
|
| - 4- vect_analyze_drs_access(): check that ref_stmt.step is ok.
|
| -
|
| -*/
|
| -
|
| -static bool
|
| -vect_analyze_data_refs (loop_vec_info loop_vinfo)
|
| -{
|
| - struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
|
| - unsigned int i;
|
| - VEC (data_reference_p, heap) *datarefs;
|
| - struct data_reference *dr;
|
| - tree scalar_type;
|
| -
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "=== vect_analyze_data_refs ===\n");
|
| -
|
| - compute_data_dependences_for_loop (loop, true,
|
| - &LOOP_VINFO_DATAREFS (loop_vinfo),
|
| - &LOOP_VINFO_DDRS (loop_vinfo));
|
| -
|
| - /* Go through the data-refs, check that the analysis succeeded. Update pointer
|
| - from stmt_vec_info struct to DR and vectype. */
|
| - datarefs = LOOP_VINFO_DATAREFS (loop_vinfo);
|
| -
|
| - for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
|
| - {
|
| - gimple stmt;
|
| - stmt_vec_info stmt_info;
|
| - basic_block bb;
|
| - tree base, offset, init;
|
| -
|
| - if (!dr || !DR_REF (dr))
|
| - {
|
| - if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
|
| - fprintf (vect_dump, "not vectorized: unhandled data-ref ");
|
| - return false;
|
| - }
|
| -
|
| - stmt = DR_STMT (dr);
|
| - stmt_info = vinfo_for_stmt (stmt);
|
| -
|
| - /* Check that analysis of the data-ref succeeded. */
|
| - if (!DR_BASE_ADDRESS (dr) || !DR_OFFSET (dr) || !DR_INIT (dr)
|
| - || !DR_STEP (dr))
|
| - {
|
| - if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
|
| - {
|
| - fprintf (vect_dump, "not vectorized: data ref analysis failed ");
|
| - print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
|
| - }
|
| - return false;
|
| - }
|
| -
|
| - if (TREE_CODE (DR_BASE_ADDRESS (dr)) == INTEGER_CST)
|
| - {
|
| - if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
|
| - fprintf (vect_dump, "not vectorized: base addr of dr is a "
|
| - "constant");
|
| - return false;
|
| - }
|
| -
|
| - if (!DR_SYMBOL_TAG (dr))
|
| - {
|
| - if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
|
| - {
|
| - fprintf (vect_dump, "not vectorized: no memory tag for ");
|
| - print_generic_expr (vect_dump, DR_REF (dr), TDF_SLIM);
|
| - }
|
| - return false;
|
| - }
|
| -
|
| - base = unshare_expr (DR_BASE_ADDRESS (dr));
|
| - offset = unshare_expr (DR_OFFSET (dr));
|
| - init = unshare_expr (DR_INIT (dr));
|
| -
|
| - /* Update DR field in stmt_vec_info struct. */
|
| - bb = gimple_bb (stmt);
|
| -
|
| - /* If the dataref is in an inner-loop of the loop that is considered for
|
| - for vectorization, we also want to analyze the access relative to
|
| - the outer-loop (DR contains information only relative to the
|
| - inner-most enclosing loop). We do that by building a reference to the
|
| - first location accessed by the inner-loop, and analyze it relative to
|
| - the outer-loop. */
|
| - if (nested_in_vect_loop_p (loop, stmt))
|
| - {
|
| - tree outer_step, outer_base, outer_init;
|
| - HOST_WIDE_INT pbitsize, pbitpos;
|
| - tree poffset;
|
| - enum machine_mode pmode;
|
| - int punsignedp, pvolatilep;
|
| - affine_iv base_iv, offset_iv;
|
| - tree dinit;
|
| -
|
| - /* Build a reference to the first location accessed by the
|
| - inner-loop: *(BASE+INIT). (The first location is actually
|
| - BASE+INIT+OFFSET, but we add OFFSET separately later). */
|
| - tree inner_base = build_fold_indirect_ref
|
| - (fold_build2 (POINTER_PLUS_EXPR,
|
| - TREE_TYPE (base), base,
|
| - fold_convert (sizetype, init)));
|
| -
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - {
|
| - fprintf (vect_dump, "analyze in outer-loop: ");
|
| - print_generic_expr (vect_dump, inner_base, TDF_SLIM);
|
| - }
|
| -
|
| - outer_base = get_inner_reference (inner_base, &pbitsize, &pbitpos,
|
| - &poffset, &pmode, &punsignedp, &pvolatilep, false);
|
| - gcc_assert (outer_base != NULL_TREE);
|
| -
|
| - if (pbitpos % BITS_PER_UNIT != 0)
|
| - {
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "failed: bit offset alignment.\n");
|
| - return false;
|
| - }
|
| -
|
| - outer_base = build_fold_addr_expr (outer_base);
|
| - if (!simple_iv (loop, loop_containing_stmt (stmt), outer_base,
|
| - &base_iv, false))
|
| - {
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "failed: evolution of base is not affine.\n");
|
| - return false;
|
| - }
|
| -
|
| - if (offset)
|
| - {
|
| - if (poffset)
|
| - poffset = fold_build2 (PLUS_EXPR, TREE_TYPE (offset), offset, poffset);
|
| - else
|
| - poffset = offset;
|
| - }
|
| -
|
| - if (!poffset)
|
| - {
|
| - offset_iv.base = ssize_int (0);
|
| - offset_iv.step = ssize_int (0);
|
| - }
|
| - else if (!simple_iv (loop, loop_containing_stmt (stmt), poffset,
|
| - &offset_iv, false))
|
| - {
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "evolution of offset is not affine.\n");
|
| - return false;
|
| - }
|
| -
|
| - outer_init = ssize_int (pbitpos / BITS_PER_UNIT);
|
| - split_constant_offset (base_iv.base, &base_iv.base, &dinit);
|
| - outer_init = size_binop (PLUS_EXPR, outer_init, dinit);
|
| - split_constant_offset (offset_iv.base, &offset_iv.base, &dinit);
|
| - outer_init = size_binop (PLUS_EXPR, outer_init, dinit);
|
| -
|
| - outer_step = size_binop (PLUS_EXPR,
|
| - fold_convert (ssizetype, base_iv.step),
|
| - fold_convert (ssizetype, offset_iv.step));
|
| -
|
| - STMT_VINFO_DR_STEP (stmt_info) = outer_step;
|
| - /* FIXME: Use canonicalize_base_object_address (base_iv.base); */
|
| - STMT_VINFO_DR_BASE_ADDRESS (stmt_info) = base_iv.base;
|
| - STMT_VINFO_DR_INIT (stmt_info) = outer_init;
|
| - STMT_VINFO_DR_OFFSET (stmt_info) =
|
| - fold_convert (ssizetype, offset_iv.base);
|
| - STMT_VINFO_DR_ALIGNED_TO (stmt_info) =
|
| - size_int (highest_pow2_factor (offset_iv.base));
|
| -
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - {
|
| - fprintf (vect_dump, "\touter base_address: ");
|
| - print_generic_expr (vect_dump, STMT_VINFO_DR_BASE_ADDRESS (stmt_info), TDF_SLIM);
|
| - fprintf (vect_dump, "\n\touter offset from base address: ");
|
| - print_generic_expr (vect_dump, STMT_VINFO_DR_OFFSET (stmt_info), TDF_SLIM);
|
| - fprintf (vect_dump, "\n\touter constant offset from base address: ");
|
| - print_generic_expr (vect_dump, STMT_VINFO_DR_INIT (stmt_info), TDF_SLIM);
|
| - fprintf (vect_dump, "\n\touter step: ");
|
| - print_generic_expr (vect_dump, STMT_VINFO_DR_STEP (stmt_info), TDF_SLIM);
|
| - fprintf (vect_dump, "\n\touter aligned to: ");
|
| - print_generic_expr (vect_dump, STMT_VINFO_DR_ALIGNED_TO (stmt_info), TDF_SLIM);
|
| - }
|
| - }
|
| -
|
| - if (STMT_VINFO_DATA_REF (stmt_info))
|
| - {
|
| - if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
|
| - {
|
| - fprintf (vect_dump,
|
| - "not vectorized: more than one data ref in stmt: ");
|
| - print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
|
| - }
|
| - return false;
|
| - }
|
| - STMT_VINFO_DATA_REF (stmt_info) = dr;
|
| -
|
| - /* Set vectype for STMT. */
|
| - scalar_type = TREE_TYPE (DR_REF (dr));
|
| - STMT_VINFO_VECTYPE (stmt_info) =
|
| - get_vectype_for_scalar_type (scalar_type);
|
| - if (!STMT_VINFO_VECTYPE (stmt_info))
|
| - {
|
| - if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
|
| - {
|
| - fprintf (vect_dump,
|
| - "not vectorized: no vectype for stmt: ");
|
| - print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
|
| - fprintf (vect_dump, " scalar_type: ");
|
| - print_generic_expr (vect_dump, scalar_type, TDF_DETAILS);
|
| - }
|
| - return false;
|
| - }
|
| - }
|
| -
|
| - return true;
|
| -}
|
| -
|
| -
|
| -/* Utility functions used by vect_mark_stmts_to_be_vectorized. */
|
| -
|
| -/* Function vect_mark_relevant.
|
| -
|
| - Mark STMT as "relevant for vectorization" and add it to WORKLIST. */
|
| -
|
| -static void
|
| -vect_mark_relevant (VEC(gimple,heap) **worklist, gimple stmt,
|
| - enum vect_relevant relevant, bool live_p)
|
| -{
|
| - stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
|
| - enum vect_relevant save_relevant = STMT_VINFO_RELEVANT (stmt_info);
|
| - bool save_live_p = STMT_VINFO_LIVE_P (stmt_info);
|
| -
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "mark relevant %d, live %d.", relevant, live_p);
|
| -
|
| - if (STMT_VINFO_IN_PATTERN_P (stmt_info))
|
| - {
|
| - gimple pattern_stmt;
|
| -
|
| - /* This is the last stmt in a sequence that was detected as a
|
| - pattern that can potentially be vectorized. Don't mark the stmt
|
| - as relevant/live because it's not going to be vectorized.
|
| - Instead mark the pattern-stmt that replaces it. */
|
| -
|
| - pattern_stmt = STMT_VINFO_RELATED_STMT (stmt_info);
|
| -
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "last stmt in pattern. don't mark relevant/live.");
|
| - stmt_info = vinfo_for_stmt (pattern_stmt);
|
| - gcc_assert (STMT_VINFO_RELATED_STMT (stmt_info) == stmt);
|
| - save_relevant = STMT_VINFO_RELEVANT (stmt_info);
|
| - save_live_p = STMT_VINFO_LIVE_P (stmt_info);
|
| - stmt = pattern_stmt;
|
| - }
|
| -
|
| - STMT_VINFO_LIVE_P (stmt_info) |= live_p;
|
| - if (relevant > STMT_VINFO_RELEVANT (stmt_info))
|
| - STMT_VINFO_RELEVANT (stmt_info) = relevant;
|
| -
|
| - if (STMT_VINFO_RELEVANT (stmt_info) == save_relevant
|
| - && STMT_VINFO_LIVE_P (stmt_info) == save_live_p)
|
| - {
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "already marked relevant/live.");
|
| - return;
|
| - }
|
| -
|
| - VEC_safe_push (gimple, heap, *worklist, stmt);
|
| -}
|
| -
|
| -
|
| -/* Function vect_stmt_relevant_p.
|
| -
|
| - Return true if STMT in loop that is represented by LOOP_VINFO is
|
| - "relevant for vectorization".
|
| -
|
| - A stmt is considered "relevant for vectorization" if:
|
| - - it has uses outside the loop.
|
| - - it has vdefs (it alters memory).
|
| - - control stmts in the loop (except for the exit condition).
|
| -
|
| - CHECKME: what other side effects would the vectorizer allow? */
|
| -
|
| -static bool
|
| -vect_stmt_relevant_p (gimple stmt, loop_vec_info loop_vinfo,
|
| - enum vect_relevant *relevant, bool *live_p)
|
| -{
|
| - struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
|
| - ssa_op_iter op_iter;
|
| - imm_use_iterator imm_iter;
|
| - use_operand_p use_p;
|
| - def_operand_p def_p;
|
| -
|
| - *relevant = vect_unused_in_loop;
|
| - *live_p = false;
|
| -
|
| - /* cond stmt other than loop exit cond. */
|
| - if (is_ctrl_stmt (stmt)
|
| - && STMT_VINFO_TYPE (vinfo_for_stmt (stmt)) != loop_exit_ctrl_vec_info_type)
|
| - *relevant = vect_used_in_loop;
|
| -
|
| - /* changing memory. */
|
| - if (gimple_code (stmt) != GIMPLE_PHI)
|
| - if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS))
|
| - {
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "vec_stmt_relevant_p: stmt has vdefs.");
|
| - *relevant = vect_used_in_loop;
|
| - }
|
| -
|
| - /* uses outside the loop. */
|
| - FOR_EACH_PHI_OR_STMT_DEF (def_p, stmt, op_iter, SSA_OP_DEF)
|
| - {
|
| - FOR_EACH_IMM_USE_FAST (use_p, imm_iter, DEF_FROM_PTR (def_p))
|
| - {
|
| - basic_block bb = gimple_bb (USE_STMT (use_p));
|
| - if (!flow_bb_inside_loop_p (loop, bb))
|
| - {
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "vec_stmt_relevant_p: used out of loop.");
|
| -
|
| - /* We expect all such uses to be in the loop exit phis
|
| - (because of loop closed form) */
|
| - gcc_assert (gimple_code (USE_STMT (use_p)) == GIMPLE_PHI);
|
| - gcc_assert (bb == single_exit (loop)->dest);
|
| -
|
| - *live_p = true;
|
| - }
|
| - }
|
| - }
|
| -
|
| - return (*live_p || *relevant);
|
| -}
|
| -
|
| -
|
| -/*
|
| - Function process_use.
|
| -
|
| - Inputs:
|
| - - a USE in STMT in a loop represented by LOOP_VINFO
|
| - - LIVE_P, RELEVANT - enum values to be set in the STMT_VINFO of the stmt
|
| - that defined USE. This is done by calling mark_relevant and passing it
|
| - the WORKLIST (to add DEF_STMT to the WORKLIST in case it is relevant).
|
| -
|
| - Outputs:
|
| - Generally, LIVE_P and RELEVANT are used to define the liveness and
|
| - relevance info of the DEF_STMT of this USE:
|
| - STMT_VINFO_LIVE_P (DEF_STMT_info) <-- live_p
|
| - STMT_VINFO_RELEVANT (DEF_STMT_info) <-- relevant
|
| - Exceptions:
|
| - - case 1: If USE is used only for address computations (e.g. array indexing),
|
| - which does not need to be directly vectorized, then the liveness/relevance
|
| - of the respective DEF_STMT is left unchanged.
|
| - - case 2: If STMT is a reduction phi and DEF_STMT is a reduction stmt, we
|
| - skip DEF_STMT cause it had already been processed.
|
| - - case 3: If DEF_STMT and STMT are in different nests, then "relevant" will
|
| - be modified accordingly.
|
| -
|
| - Return true if everything is as expected. Return false otherwise. */
|
| -
|
| -static bool
|
| -process_use (gimple stmt, tree use, loop_vec_info loop_vinfo, bool live_p,
|
| - enum vect_relevant relevant, VEC(gimple,heap) **worklist)
|
| -{
|
| - struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
|
| - stmt_vec_info stmt_vinfo = vinfo_for_stmt (stmt);
|
| - stmt_vec_info dstmt_vinfo;
|
| - basic_block bb, def_bb;
|
| - tree def;
|
| - gimple def_stmt;
|
| - enum vect_def_type dt;
|
| -
|
| - /* case 1: we are only interested in uses that need to be vectorized. Uses
|
| - that are used for address computation are not considered relevant. */
|
| - if (!exist_non_indexing_operands_for_use_p (use, stmt))
|
| - return true;
|
| -
|
| - if (!vect_is_simple_use (use, loop_vinfo, &def_stmt, &def, &dt))
|
| - {
|
| - if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
|
| - fprintf (vect_dump, "not vectorized: unsupported use in stmt.");
|
| - return false;
|
| - }
|
| -
|
| - if (!def_stmt || gimple_nop_p (def_stmt))
|
| - return true;
|
| -
|
| - def_bb = gimple_bb (def_stmt);
|
| - if (!flow_bb_inside_loop_p (loop, def_bb))
|
| - {
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "def_stmt is out of loop.");
|
| - return true;
|
| - }
|
| -
|
| - /* case 2: A reduction phi (STMT) defined by a reduction stmt (DEF_STMT).
|
| - DEF_STMT must have already been processed, because this should be the
|
| - only way that STMT, which is a reduction-phi, was put in the worklist,
|
| - as there should be no other uses for DEF_STMT in the loop. So we just
|
| - check that everything is as expected, and we are done. */
|
| - dstmt_vinfo = vinfo_for_stmt (def_stmt);
|
| - bb = gimple_bb (stmt);
|
| - if (gimple_code (stmt) == GIMPLE_PHI
|
| - && STMT_VINFO_DEF_TYPE (stmt_vinfo) == vect_reduction_def
|
| - && gimple_code (def_stmt) != GIMPLE_PHI
|
| - && STMT_VINFO_DEF_TYPE (dstmt_vinfo) == vect_reduction_def
|
| - && bb->loop_father == def_bb->loop_father)
|
| - {
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "reduc-stmt defining reduc-phi in the same nest.");
|
| - if (STMT_VINFO_IN_PATTERN_P (dstmt_vinfo))
|
| - dstmt_vinfo = vinfo_for_stmt (STMT_VINFO_RELATED_STMT (dstmt_vinfo));
|
| - gcc_assert (STMT_VINFO_RELEVANT (dstmt_vinfo) < vect_used_by_reduction);
|
| - gcc_assert (STMT_VINFO_LIVE_P (dstmt_vinfo)
|
| - || STMT_VINFO_RELEVANT (dstmt_vinfo) > vect_unused_in_loop);
|
| - return true;
|
| - }
|
| -
|
| - /* case 3a: outer-loop stmt defining an inner-loop stmt:
|
| - outer-loop-header-bb:
|
| - d = def_stmt
|
| - inner-loop:
|
| - stmt # use (d)
|
| - outer-loop-tail-bb:
|
| - ... */
|
| - if (flow_loop_nested_p (def_bb->loop_father, bb->loop_father))
|
| - {
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "outer-loop def-stmt defining inner-loop stmt.");
|
| - switch (relevant)
|
| - {
|
| - case vect_unused_in_loop:
|
| - relevant = (STMT_VINFO_DEF_TYPE (stmt_vinfo) == vect_reduction_def) ?
|
| - vect_used_by_reduction : vect_unused_in_loop;
|
| - break;
|
| - case vect_used_in_outer_by_reduction:
|
| - relevant = vect_used_by_reduction;
|
| - break;
|
| - case vect_used_in_outer:
|
| - relevant = vect_used_in_loop;
|
| - break;
|
| - case vect_used_by_reduction:
|
| - case vect_used_in_loop:
|
| - break;
|
| -
|
| - default:
|
| - gcc_unreachable ();
|
| - }
|
| - }
|
| -
|
| - /* case 3b: inner-loop stmt defining an outer-loop stmt:
|
| - outer-loop-header-bb:
|
| - ...
|
| - inner-loop:
|
| - d = def_stmt
|
| - outer-loop-tail-bb:
|
| - stmt # use (d) */
|
| - else if (flow_loop_nested_p (bb->loop_father, def_bb->loop_father))
|
| - {
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "inner-loop def-stmt defining outer-loop stmt.");
|
| - switch (relevant)
|
| - {
|
| - case vect_unused_in_loop:
|
| - relevant = (STMT_VINFO_DEF_TYPE (stmt_vinfo) == vect_reduction_def) ?
|
| - vect_used_in_outer_by_reduction : vect_unused_in_loop;
|
| - break;
|
| -
|
| - case vect_used_in_outer_by_reduction:
|
| - case vect_used_in_outer:
|
| - break;
|
| -
|
| - case vect_used_by_reduction:
|
| - relevant = vect_used_in_outer_by_reduction;
|
| - break;
|
| -
|
| - case vect_used_in_loop:
|
| - relevant = vect_used_in_outer;
|
| - break;
|
| -
|
| - default:
|
| - gcc_unreachable ();
|
| - }
|
| - }
|
| -
|
| - vect_mark_relevant (worklist, def_stmt, relevant, live_p);
|
| - return true;
|
| -}
|
| -
|
| -
|
| -/* Function vect_mark_stmts_to_be_vectorized.
|
| -
|
| - Not all stmts in the loop need to be vectorized. For example:
|
| -
|
| - for i...
|
| - for j...
|
| - 1. T0 = i + j
|
| - 2. T1 = a[T0]
|
| -
|
| - 3. j = j + 1
|
| -
|
| - Stmt 1 and 3 do not need to be vectorized, because loop control and
|
| - addressing of vectorized data-refs are handled differently.
|
| -
|
| - This pass detects such stmts. */
|
| -
|
| -static bool
|
| -vect_mark_stmts_to_be_vectorized (loop_vec_info loop_vinfo)
|
| -{
|
| - VEC(gimple,heap) *worklist;
|
| - struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
|
| - basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo);
|
| - unsigned int nbbs = loop->num_nodes;
|
| - gimple_stmt_iterator si;
|
| - gimple stmt;
|
| - unsigned int i;
|
| - stmt_vec_info stmt_vinfo;
|
| - basic_block bb;
|
| - gimple phi;
|
| - bool live_p;
|
| - enum vect_relevant relevant;
|
| -
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "=== vect_mark_stmts_to_be_vectorized ===");
|
| -
|
| - worklist = VEC_alloc (gimple, heap, 64);
|
| -
|
| - /* 1. Init worklist. */
|
| - for (i = 0; i < nbbs; i++)
|
| - {
|
| - bb = bbs[i];
|
| - for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
|
| - {
|
| - phi = gsi_stmt (si);
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - {
|
| - fprintf (vect_dump, "init: phi relevant? ");
|
| - print_gimple_stmt (vect_dump, phi, 0, TDF_SLIM);
|
| - }
|
| -
|
| - if (vect_stmt_relevant_p (phi, loop_vinfo, &relevant, &live_p))
|
| - vect_mark_relevant (&worklist, phi, relevant, live_p);
|
| - }
|
| - for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
|
| - {
|
| - stmt = gsi_stmt (si);
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - {
|
| - fprintf (vect_dump, "init: stmt relevant? ");
|
| - print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
|
| - }
|
| -
|
| - if (vect_stmt_relevant_p (stmt, loop_vinfo, &relevant, &live_p))
|
| - vect_mark_relevant (&worklist, stmt, relevant, live_p);
|
| - }
|
| - }
|
| -
|
| - /* 2. Process_worklist */
|
| - while (VEC_length (gimple, worklist) > 0)
|
| - {
|
| - use_operand_p use_p;
|
| - ssa_op_iter iter;
|
| -
|
| - stmt = VEC_pop (gimple, worklist);
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - {
|
| - fprintf (vect_dump, "worklist: examine stmt: ");
|
| - print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
|
| - }
|
| -
|
| - /* Examine the USEs of STMT. For each USE, mark the stmt that defines it
|
| - (DEF_STMT) as relevant/irrelevant and live/dead according to the
|
| - liveness and relevance properties of STMT. */
|
| - stmt_vinfo = vinfo_for_stmt (stmt);
|
| - relevant = STMT_VINFO_RELEVANT (stmt_vinfo);
|
| - live_p = STMT_VINFO_LIVE_P (stmt_vinfo);
|
| -
|
| - /* Generally, the liveness and relevance properties of STMT are
|
| - propagated as is to the DEF_STMTs of its USEs:
|
| - live_p <-- STMT_VINFO_LIVE_P (STMT_VINFO)
|
| - relevant <-- STMT_VINFO_RELEVANT (STMT_VINFO)
|
| -
|
| - One exception is when STMT has been identified as defining a reduction
|
| - variable; in this case we set the liveness/relevance as follows:
|
| - live_p = false
|
| - relevant = vect_used_by_reduction
|
| - This is because we distinguish between two kinds of relevant stmts -
|
| - those that are used by a reduction computation, and those that are
|
| - (also) used by a regular computation. This allows us later on to
|
| - identify stmts that are used solely by a reduction, and therefore the
|
| - order of the results that they produce does not have to be kept.
|
| -
|
| - Reduction phis are expected to be used by a reduction stmt, or by
|
| - in an outer loop; Other reduction stmts are expected to be
|
| - in the loop, and possibly used by a stmt in an outer loop.
|
| - Here are the expected values of "relevant" for reduction phis/stmts:
|
| -
|
| - relevance: phi stmt
|
| - vect_unused_in_loop ok
|
| - vect_used_in_outer_by_reduction ok ok
|
| - vect_used_in_outer ok ok
|
| - vect_used_by_reduction ok
|
| - vect_used_in_loop */
|
| -
|
| - if (STMT_VINFO_DEF_TYPE (stmt_vinfo) == vect_reduction_def)
|
| - {
|
| - enum vect_relevant tmp_relevant = relevant;
|
| - switch (tmp_relevant)
|
| - {
|
| - case vect_unused_in_loop:
|
| - gcc_assert (gimple_code (stmt) != GIMPLE_PHI);
|
| - relevant = vect_used_by_reduction;
|
| - break;
|
| -
|
| - case vect_used_in_outer_by_reduction:
|
| - case vect_used_in_outer:
|
| - gcc_assert (gimple_code (stmt) != GIMPLE_ASSIGN
|
| - || (gimple_assign_rhs_code (stmt) != WIDEN_SUM_EXPR
|
| - && (gimple_assign_rhs_code (stmt)
|
| - != DOT_PROD_EXPR)));
|
| - break;
|
| -
|
| - case vect_used_by_reduction:
|
| - if (gimple_code (stmt) == GIMPLE_PHI)
|
| - break;
|
| - /* fall through */
|
| - case vect_used_in_loop:
|
| - default:
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "unsupported use of reduction.");
|
| - VEC_free (gimple, heap, worklist);
|
| - return false;
|
| - }
|
| - live_p = false;
|
| - }
|
| -
|
| - FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE)
|
| - {
|
| - tree op = USE_FROM_PTR (use_p);
|
| - if (!process_use (stmt, op, loop_vinfo, live_p, relevant, &worklist))
|
| - {
|
| - VEC_free (gimple, heap, worklist);
|
| - return false;
|
| - }
|
| - }
|
| - } /* while worklist */
|
| -
|
| - VEC_free (gimple, heap, worklist);
|
| - return true;
|
| -}
|
| -
|
| -
|
| -/* Function vect_can_advance_ivs_p
|
| -
|
| - In case the number of iterations that LOOP iterates is unknown at compile
|
| - time, an epilog loop will be generated, and the loop induction variables
|
| - (IVs) will be "advanced" to the value they are supposed to take just before
|
| - the epilog loop. Here we check that the access function of the loop IVs
|
| - and the expression that represents the loop bound are simple enough.
|
| - These restrictions will be relaxed in the future. */
|
| -
|
| -static bool
|
| -vect_can_advance_ivs_p (loop_vec_info loop_vinfo)
|
| -{
|
| - struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
|
| - basic_block bb = loop->header;
|
| - gimple phi;
|
| - gimple_stmt_iterator gsi;
|
| -
|
| - /* Analyze phi functions of the loop header. */
|
| -
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "vect_can_advance_ivs_p:");
|
| -
|
| - for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
|
| - {
|
| - tree access_fn = NULL;
|
| - tree evolution_part;
|
| -
|
| - phi = gsi_stmt (gsi);
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - {
|
| - fprintf (vect_dump, "Analyze phi: ");
|
| - print_gimple_stmt (vect_dump, phi, 0, TDF_SLIM);
|
| - }
|
| -
|
| - /* Skip virtual phi's. The data dependences that are associated with
|
| - virtual defs/uses (i.e., memory accesses) are analyzed elsewhere. */
|
| -
|
| - if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi))))
|
| - {
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "virtual phi. skip.");
|
| - continue;
|
| - }
|
| -
|
| - /* Skip reduction phis. */
|
| -
|
| - if (STMT_VINFO_DEF_TYPE (vinfo_for_stmt (phi)) == vect_reduction_def)
|
| - {
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "reduc phi. skip.");
|
| - continue;
|
| - }
|
| -
|
| - /* Analyze the evolution function. */
|
| -
|
| - access_fn = instantiate_parameters
|
| - (loop, analyze_scalar_evolution (loop, PHI_RESULT (phi)));
|
| -
|
| - if (!access_fn)
|
| - {
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "No Access function.");
|
| - return false;
|
| - }
|
| -
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - {
|
| - fprintf (vect_dump, "Access function of PHI: ");
|
| - print_generic_expr (vect_dump, access_fn, TDF_SLIM);
|
| - }
|
| -
|
| - evolution_part = evolution_part_in_loop_num (access_fn, loop->num);
|
| -
|
| - if (evolution_part == NULL_TREE)
|
| - {
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "No evolution.");
|
| - return false;
|
| - }
|
| -
|
| - /* FORNOW: We do not transform initial conditions of IVs
|
| - which evolution functions are a polynomial of degree >= 2. */
|
| -
|
| - if (tree_is_chrec (evolution_part))
|
| - return false;
|
| - }
|
| -
|
| - return true;
|
| -}
|
| -
|
| -
|
| -/* Function vect_get_loop_niters.
|
| -
|
| - Determine how many iterations the loop is executed.
|
| - If an expression that represents the number of iterations
|
| - can be constructed, place it in NUMBER_OF_ITERATIONS.
|
| - Return the loop exit condition. */
|
| -
|
| -static gimple
|
| -vect_get_loop_niters (struct loop *loop, tree *number_of_iterations)
|
| -{
|
| - tree niters;
|
| -
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "=== get_loop_niters ===");
|
| -
|
| - niters = number_of_exit_cond_executions (loop);
|
| -
|
| - if (niters != NULL_TREE
|
| - && niters != chrec_dont_know)
|
| - {
|
| - *number_of_iterations = niters;
|
| -
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - {
|
| - fprintf (vect_dump, "==> get_loop_niters:" );
|
| - print_generic_expr (vect_dump, *number_of_iterations, TDF_SLIM);
|
| - }
|
| - }
|
| -
|
| - return get_loop_exit_condition (loop);
|
| -}
|
| -
|
| -
|
| -/* Function vect_analyze_loop_1.
|
| -
|
| - Apply a set of analyses on LOOP, and create a loop_vec_info struct
|
| - for it. The different analyses will record information in the
|
| - loop_vec_info struct. This is a subset of the analyses applied in
|
| - vect_analyze_loop, to be applied on an inner-loop nested in the loop
|
| - that is now considered for (outer-loop) vectorization. */
|
| -
|
| -static loop_vec_info
|
| -vect_analyze_loop_1 (struct loop *loop)
|
| -{
|
| - loop_vec_info loop_vinfo;
|
| -
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "===== analyze_loop_nest_1 =====");
|
| -
|
| - /* Check the CFG characteristics of the loop (nesting, entry/exit, etc. */
|
| -
|
| - loop_vinfo = vect_analyze_loop_form (loop);
|
| - if (!loop_vinfo)
|
| - {
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "bad inner-loop form.");
|
| - return NULL;
|
| - }
|
| -
|
| - return loop_vinfo;
|
| -}
|
| -
|
| -
|
| -/* Function vect_analyze_loop_form.
|
| -
|
| - Verify that certain CFG restrictions hold, including:
|
| - - the loop has a pre-header
|
| - - the loop has a single entry and exit
|
| - - the loop exit condition is simple enough, and the number of iterations
|
| - can be analyzed (a countable loop). */
|
| -
|
| -loop_vec_info
|
| -vect_analyze_loop_form (struct loop *loop)
|
| -{
|
| - loop_vec_info loop_vinfo;
|
| - gimple loop_cond;
|
| - tree number_of_iterations = NULL;
|
| - loop_vec_info inner_loop_vinfo = NULL;
|
| -
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "=== vect_analyze_loop_form ===");
|
| -
|
| - /* Different restrictions apply when we are considering an inner-most loop,
|
| - vs. an outer (nested) loop.
|
| - (FORNOW. May want to relax some of these restrictions in the future). */
|
| -
|
| - if (!loop->inner)
|
| - {
|
| - /* Inner-most loop. We currently require that the number of BBs is
|
| - exactly 2 (the header and latch). Vectorizable inner-most loops
|
| - look like this:
|
| -
|
| - (pre-header)
|
| - |
|
| - header <--------+
|
| - | | |
|
| - | +--> latch --+
|
| - |
|
| - (exit-bb) */
|
| -
|
| - if (loop->num_nodes != 2)
|
| - {
|
| - if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
|
| - fprintf (vect_dump, "not vectorized: too many BBs in loop.");
|
| - return NULL;
|
| - }
|
| -
|
| - if (empty_block_p (loop->header))
|
| - {
|
| - if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
|
| - fprintf (vect_dump, "not vectorized: empty loop.");
|
| - return NULL;
|
| - }
|
| - }
|
| - else
|
| - {
|
| - struct loop *innerloop = loop->inner;
|
| - edge backedge, entryedge;
|
| -
|
| - /* Nested loop. We currently require that the loop is doubly-nested,
|
| - contains a single inner loop, and the number of BBs is exactly 5.
|
| - Vectorizable outer-loops look like this:
|
| -
|
| - (pre-header)
|
| - |
|
| - header <---+
|
| - | |
|
| - inner-loop |
|
| - | |
|
| - tail ------+
|
| - |
|
| - (exit-bb)
|
| -
|
| - The inner-loop has the properties expected of inner-most loops
|
| - as described above. */
|
| -
|
| - if ((loop->inner)->inner || (loop->inner)->next)
|
| - {
|
| - if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
|
| - fprintf (vect_dump, "not vectorized: multiple nested loops.");
|
| - return NULL;
|
| - }
|
| -
|
| - /* Analyze the inner-loop. */
|
| - inner_loop_vinfo = vect_analyze_loop_1 (loop->inner);
|
| - if (!inner_loop_vinfo)
|
| - {
|
| - if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
|
| - fprintf (vect_dump, "not vectorized: Bad inner loop.");
|
| - return NULL;
|
| - }
|
| -
|
| - if (!expr_invariant_in_loop_p (loop,
|
| - LOOP_VINFO_NITERS (inner_loop_vinfo)))
|
| - {
|
| - if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
|
| - fprintf (vect_dump,
|
| - "not vectorized: inner-loop count not invariant.");
|
| - destroy_loop_vec_info (inner_loop_vinfo, true);
|
| - return NULL;
|
| - }
|
| -
|
| - if (loop->num_nodes != 5)
|
| - {
|
| - if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
|
| - fprintf (vect_dump, "not vectorized: too many BBs in loop.");
|
| - destroy_loop_vec_info (inner_loop_vinfo, true);
|
| - return NULL;
|
| - }
|
| -
|
| - gcc_assert (EDGE_COUNT (innerloop->header->preds) == 2);
|
| - backedge = EDGE_PRED (innerloop->header, 1);
|
| - entryedge = EDGE_PRED (innerloop->header, 0);
|
| - if (EDGE_PRED (innerloop->header, 0)->src == innerloop->latch)
|
| - {
|
| - backedge = EDGE_PRED (innerloop->header, 0);
|
| - entryedge = EDGE_PRED (innerloop->header, 1);
|
| - }
|
| -
|
| - if (entryedge->src != loop->header
|
| - || !single_exit (innerloop)
|
| - || single_exit (innerloop)->dest != EDGE_PRED (loop->latch, 0)->src)
|
| - {
|
| - if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
|
| - fprintf (vect_dump, "not vectorized: unsupported outerloop form.");
|
| - destroy_loop_vec_info (inner_loop_vinfo, true);
|
| - return NULL;
|
| - }
|
| -
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "Considering outer-loop vectorization.");
|
| - }
|
| -
|
| - if (!single_exit (loop)
|
| - || EDGE_COUNT (loop->header->preds) != 2)
|
| - {
|
| - if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
|
| - {
|
| - if (!single_exit (loop))
|
| - fprintf (vect_dump, "not vectorized: multiple exits.");
|
| - else if (EDGE_COUNT (loop->header->preds) != 2)
|
| - fprintf (vect_dump, "not vectorized: too many incoming edges.");
|
| - }
|
| - if (inner_loop_vinfo)
|
| - destroy_loop_vec_info (inner_loop_vinfo, true);
|
| - return NULL;
|
| - }
|
| -
|
| - /* We assume that the loop exit condition is at the end of the loop. i.e,
|
| - that the loop is represented as a do-while (with a proper if-guard
|
| - before the loop if needed), where the loop header contains all the
|
| - executable statements, and the latch is empty. */
|
| - if (!empty_block_p (loop->latch)
|
| - || phi_nodes (loop->latch))
|
| - {
|
| - if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
|
| - fprintf (vect_dump, "not vectorized: unexpected loop form.");
|
| - if (inner_loop_vinfo)
|
| - destroy_loop_vec_info (inner_loop_vinfo, true);
|
| - return NULL;
|
| - }
|
| -
|
| - /* Make sure there exists a single-predecessor exit bb: */
|
| - if (!single_pred_p (single_exit (loop)->dest))
|
| - {
|
| - edge e = single_exit (loop);
|
| - if (!(e->flags & EDGE_ABNORMAL))
|
| - {
|
| - split_loop_exit_edge (e);
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "split exit edge.");
|
| - }
|
| - else
|
| - {
|
| - if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
|
| - fprintf (vect_dump, "not vectorized: abnormal loop exit edge.");
|
| - if (inner_loop_vinfo)
|
| - destroy_loop_vec_info (inner_loop_vinfo, true);
|
| - return NULL;
|
| - }
|
| - }
|
| -
|
| - loop_cond = vect_get_loop_niters (loop, &number_of_iterations);
|
| - if (!loop_cond)
|
| - {
|
| - if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
|
| - fprintf (vect_dump, "not vectorized: complicated exit condition.");
|
| - if (inner_loop_vinfo)
|
| - destroy_loop_vec_info (inner_loop_vinfo, true);
|
| - return NULL;
|
| - }
|
| -
|
| - if (!number_of_iterations)
|
| - {
|
| - if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
|
| - fprintf (vect_dump,
|
| - "not vectorized: number of iterations cannot be computed.");
|
| - if (inner_loop_vinfo)
|
| - destroy_loop_vec_info (inner_loop_vinfo, true);
|
| - return NULL;
|
| - }
|
| -
|
| - if (chrec_contains_undetermined (number_of_iterations))
|
| - {
|
| - if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
|
| - fprintf (vect_dump, "Infinite number of iterations.");
|
| - if (inner_loop_vinfo)
|
| - destroy_loop_vec_info (inner_loop_vinfo, true);
|
| - return NULL;
|
| - }
|
| -
|
| - if (!NITERS_KNOWN_P (number_of_iterations))
|
| - {
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - {
|
| - fprintf (vect_dump, "Symbolic number of iterations is ");
|
| - print_generic_expr (vect_dump, number_of_iterations, TDF_DETAILS);
|
| - }
|
| - }
|
| - else if (TREE_INT_CST_LOW (number_of_iterations) == 0)
|
| - {
|
| - if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
|
| - fprintf (vect_dump, "not vectorized: number of iterations = 0.");
|
| - if (inner_loop_vinfo)
|
| - destroy_loop_vec_info (inner_loop_vinfo, false);
|
| - return NULL;
|
| - }
|
| -
|
| - loop_vinfo = new_loop_vec_info (loop);
|
| - LOOP_VINFO_NITERS (loop_vinfo) = number_of_iterations;
|
| - LOOP_VINFO_NITERS_UNCHANGED (loop_vinfo) = number_of_iterations;
|
| -
|
| - STMT_VINFO_TYPE (vinfo_for_stmt (loop_cond)) = loop_exit_ctrl_vec_info_type;
|
| -
|
| - /* CHECKME: May want to keep it around it in the future. */
|
| - if (inner_loop_vinfo)
|
| - destroy_loop_vec_info (inner_loop_vinfo, false);
|
| -
|
| - gcc_assert (!loop->aux);
|
| - loop->aux = loop_vinfo;
|
| - return loop_vinfo;
|
| -}
|
| -
|
| -
|
| -/* Function vect_analyze_loop.
|
| -
|
| - Apply a set of analyses on LOOP, and create a loop_vec_info struct
|
| - for it. The different analyses will record information in the
|
| - loop_vec_info struct. */
|
| -loop_vec_info
|
| -vect_analyze_loop (struct loop *loop)
|
| -{
|
| - bool ok;
|
| - loop_vec_info loop_vinfo;
|
| -
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "===== analyze_loop_nest =====");
|
| -
|
| - if (loop_outer (loop)
|
| - && loop_vec_info_for_loop (loop_outer (loop))
|
| - && LOOP_VINFO_VECTORIZABLE_P (loop_vec_info_for_loop (loop_outer (loop))))
|
| - {
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "outer-loop already vectorized.");
|
| - return NULL;
|
| - }
|
| -
|
| - /* Check the CFG characteristics of the loop (nesting, entry/exit, etc. */
|
| -
|
| - loop_vinfo = vect_analyze_loop_form (loop);
|
| - if (!loop_vinfo)
|
| - {
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "bad loop form.");
|
| - return NULL;
|
| - }
|
| -
|
| - /* Find all data references in the loop (which correspond to vdefs/vuses)
|
| - and analyze their evolution in the loop.
|
| -
|
| - FORNOW: Handle only simple, array references, which
|
| - alignment can be forced, and aligned pointer-references. */
|
| -
|
| - ok = vect_analyze_data_refs (loop_vinfo);
|
| - if (!ok)
|
| - {
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "bad data references.");
|
| - destroy_loop_vec_info (loop_vinfo, true);
|
| - return NULL;
|
| - }
|
| -
|
| - /* Classify all cross-iteration scalar data-flow cycles.
|
| - Cross-iteration cycles caused by virtual phis are analyzed separately. */
|
| -
|
| - vect_analyze_scalar_cycles (loop_vinfo);
|
| -
|
| - vect_pattern_recog (loop_vinfo);
|
| -
|
| - /* Data-flow analysis to detect stmts that do not need to be vectorized. */
|
| -
|
| - ok = vect_mark_stmts_to_be_vectorized (loop_vinfo);
|
| - if (!ok)
|
| - {
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "unexpected pattern.");
|
| - destroy_loop_vec_info (loop_vinfo, true);
|
| - return NULL;
|
| - }
|
| -
|
| - /* Analyze the alignment of the data-refs in the loop.
|
| - Fail if a data reference is found that cannot be vectorized. */
|
| -
|
| - ok = vect_analyze_data_refs_alignment (loop_vinfo);
|
| - if (!ok)
|
| - {
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "bad data alignment.");
|
| - destroy_loop_vec_info (loop_vinfo, true);
|
| - return NULL;
|
| - }
|
| -
|
| - ok = vect_determine_vectorization_factor (loop_vinfo);
|
| - if (!ok)
|
| - {
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "can't determine vectorization factor.");
|
| - destroy_loop_vec_info (loop_vinfo, true);
|
| - return NULL;
|
| - }
|
| -
|
| - /* Analyze data dependences between the data-refs in the loop.
|
| - FORNOW: fail at the first data dependence that we encounter. */
|
| -
|
| - ok = vect_analyze_data_ref_dependences (loop_vinfo);
|
| - if (!ok)
|
| - {
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "bad data dependence.");
|
| - destroy_loop_vec_info (loop_vinfo, true);
|
| - return NULL;
|
| - }
|
| -
|
| - /* Analyze the access patterns of the data-refs in the loop (consecutive,
|
| - complex, etc.). FORNOW: Only handle consecutive access pattern. */
|
| -
|
| - ok = vect_analyze_data_ref_accesses (loop_vinfo);
|
| - if (!ok)
|
| - {
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "bad data access.");
|
| - destroy_loop_vec_info (loop_vinfo, true);
|
| - return NULL;
|
| - }
|
| -
|
| - /* Prune the list of ddrs to be tested at run-time by versioning for alias.
|
| - It is important to call pruning after vect_analyze_data_ref_accesses,
|
| - since we use grouping information gathered by interleaving analysis. */
|
| - ok = vect_prune_runtime_alias_test_list (loop_vinfo);
|
| - if (!ok)
|
| - {
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "too long list of versioning for alias "
|
| - "run-time tests.");
|
| - destroy_loop_vec_info (loop_vinfo, true);
|
| - return NULL;
|
| - }
|
| -
|
| - /* Check the SLP opportunities in the loop, analyze and build SLP trees. */
|
| - ok = vect_analyze_slp (loop_vinfo);
|
| - if (ok)
|
| - {
|
| - /* Decide which possible SLP instances to SLP. */
|
| - vect_make_slp_decision (loop_vinfo);
|
| -
|
| - /* Find stmts that need to be both vectorized and SLPed. */
|
| - vect_detect_hybrid_slp (loop_vinfo);
|
| - }
|
| -
|
| - /* This pass will decide on using loop versioning and/or loop peeling in
|
| - order to enhance the alignment of data references in the loop. */
|
| -
|
| - ok = vect_enhance_data_refs_alignment (loop_vinfo);
|
| - if (!ok)
|
| - {
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "bad data alignment.");
|
| - destroy_loop_vec_info (loop_vinfo, true);
|
| - return NULL;
|
| - }
|
| -
|
| - /* Scan all the operations in the loop and make sure they are
|
| - vectorizable. */
|
| -
|
| - ok = vect_analyze_operations (loop_vinfo);
|
| - if (!ok)
|
| - {
|
| - if (vect_print_dump_info (REPORT_DETAILS))
|
| - fprintf (vect_dump, "bad operation or unsupported loop bound.");
|
| - destroy_loop_vec_info (loop_vinfo, true);
|
| - return NULL;
|
| - }
|
| -
|
| - LOOP_VINFO_VECTORIZABLE_P (loop_vinfo) = 1;
|
| -
|
| - return loop_vinfo;
|
| -}
|
|
|
Chromium Code Reviews
Issue 3050029:
[gcc] GCC 4.5.0=>4.5.1 (Closed)
Base URL: ssh://git@gitrw.chromium.org:9222/nacl-toolchain.git