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; |
-} |