/* Data References Analysis and Manipulation Utilities for Vectorization.
- Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009 Free Software
- Foundation, Inc.
+ Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
+ Free Software Foundation, Inc.
Contributed by Dorit Naishlos <dorit@il.ibm.com>
and Ira Rosen <irar@il.ibm.com>
#include "target.h"
#include "basic-block.h"
#include "diagnostic.h"
+#include "tree-pretty-print.h"
+#include "gimple-pretty-print.h"
#include "tree-flow.h"
#include "tree-dump.h"
#include "cfgloop.h"
static bool
vect_equal_offsets (tree offset1, tree offset2)
{
- bool res0, res1;
+ bool res;
STRIP_NOPS (offset1);
STRIP_NOPS (offset2);
return true;
if (TREE_CODE (offset1) != TREE_CODE (offset2)
- || !BINARY_CLASS_P (offset1)
- || !BINARY_CLASS_P (offset2))
+ || (!BINARY_CLASS_P (offset1) && !UNARY_CLASS_P (offset1)))
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));
+ res = vect_equal_offsets (TREE_OPERAND (offset1, 0),
+ TREE_OPERAND (offset2, 0));
- return (res0 && res1);
+ if (!res || !BINARY_CLASS_P (offset1))
+ return res;
+
+ res = vect_equal_offsets (TREE_OPERAND (offset1, 1),
+ TREE_OPERAND (offset2, 1));
+
+ return res;
}
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. */
+ dependence at run-time, return FALSE. Adjust *MAX_VF according to
+ the data dependence. */
static bool
vect_analyze_data_ref_dependence (struct data_dependence_relation *ddr,
- loop_vec_info loop_vinfo)
+ loop_vec_info loop_vinfo, int *max_vf)
{
unsigned int i;
struct loop *loop = NULL;
- int vectorization_factor = 0;
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;
+ /* Don't bother to analyze statements marked as unvectorizable. */
+ if (!STMT_VINFO_VECTORIZABLE (stmtinfo_a)
+ || !STMT_VINFO_VECTORIZABLE (stmtinfo_b))
+ return false;
+
if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
{
/* Independent data accesses. */
}
if (loop_vinfo)
- {
- loop = LOOP_VINFO_LOOP (loop_vinfo);
- vectorization_factor = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
- }
+ loop = LOOP_VINFO_LOOP (loop_vinfo);
if ((DR_IS_READ (dra) && DR_IS_READ (drb) && loop_vinfo) || dra == drb)
return false;
print_generic_expr (vect_dump, DR_REF (drb), TDF_SLIM);
}
- return true;
+ /* Mark the statements as unvectorizable. */
+ STMT_VINFO_VECTORIZABLE (stmtinfo_a) = false;
+ STMT_VINFO_VECTORIZABLE (stmtinfo_b) = false;
+
+ return false;
}
/* Versioning for alias is not yet supported for basic block SLP, and
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)
+ if (dist == 0)
{
- /* 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 ");
+ fprintf (vect_dump, "dependence distance == 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);
DR_GROUP_READ_WRITE_DEPENDENCE (stmtinfo_b) = true;
}
- continue;
+ continue;
+ }
+
+ if (dist > 0 && DDR_REVERSED_P (ddr))
+ {
+ /* 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 negative.");
+ continue;
+ }
+
+ if (abs (dist) >= 2
+ && abs (dist) < *max_vf)
+ {
+ /* The dependence distance requires reduction of the maximal
+ vectorization factor. */
+ *max_vf = abs (dist);
+ if (vect_print_dump_info (REPORT_DR_DETAILS))
+ fprintf (vect_dump, "adjusting maximal vectorization factor to %i",
+ *max_vf);
}
- if (abs (dist) >= vectorization_factor
- || (dist > 0 && DDR_REVERSED_P (ddr)))
+ if (abs (dist) >= *max_vf)
{
/* 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. */
+ vectorization is concerned, in this case. */
if (vect_print_dump_info (REPORT_DR_DETAILS))
- fprintf (vect_dump, "dependence distance >= VF or negative.");
+ fprintf (vect_dump, "dependence distance >= VF.");
continue;
}
/* 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. */
+ exist any data dependences between them. Set *MAX_VF according to
+ the maximum vectorization factor the data dependences allow. */
bool
vect_analyze_data_ref_dependences (loop_vec_info loop_vinfo,
- bb_vec_info bb_vinfo)
+ bb_vec_info bb_vinfo, int *max_vf)
{
unsigned int i;
VEC (ddr_p, heap) *ddrs = NULL;
ddrs = BB_VINFO_DDRS (bb_vinfo);
for (i = 0; VEC_iterate (ddr_p, ddrs, i, ddr); i++)
- if (vect_analyze_data_ref_dependence (ddr, loop_vinfo))
+ if (vect_analyze_data_ref_dependence (ddr, loop_vinfo, max_vf))
return false;
return true;
datarefs = BB_VINFO_DATAREFS (bb_vinfo);
for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
- if (!vect_compute_data_ref_alignment (dr))
- return false;
+ if (STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (DR_STMT (dr)))
+ && !vect_compute_data_ref_alignment (dr))
+ {
+ if (bb_vinfo)
+ {
+ /* Mark unsupported statement as unvectorizable. */
+ STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (DR_STMT (dr))) = false;
+ continue;
+ }
+ else
+ return false;
+ }
return true;
}
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)
+ /* For interleaving, only the alignment of the first access matters.
+ Skip statements marked as not vectorizable. */
+ if ((STMT_VINFO_STRIDED_ACCESS (stmt_info)
+ && DR_GROUP_FIRST_DR (stmt_info) != stmt)
+ || !STMT_VINFO_VECTORIZABLE (stmt_info))
continue;
supportable_dr_alignment = vect_supportable_dr_alignment (dr);
else
fprintf (vect_dump,
"not vectorized: unsupported unaligned store.");
+
+ print_generic_expr (vect_dump, DR_REF (dr), TDF_SLIM);
}
return false;
}
}
+/* Function vect_find_same_alignment_drs.
+
+ Update group and alignment relations according to the chosen
+ vectorization factor. */
+
+static void
+vect_find_same_alignment_drs (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)
+ return;
+
+ if ((DR_IS_READ (dra) && DR_IS_READ (drb)) || dra == drb)
+ return;
+
+ if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
+ return;
+
+ /* Loop-based vectorization and known data dependence. */
+ if (DDR_NUM_DIST_VECTS (ddr) == 0)
+ return;
+
+ 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 == 0
+ || (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);
+ }
+ }
+ }
+}
+
+
/* Function vect_analyze_data_refs_alignment
Analyze the alignment of the data-references in the loop.
if (vect_print_dump_info (REPORT_DETAILS))
fprintf (vect_dump, "=== vect_analyze_data_refs_alignment ===");
+ /* Mark groups of data references with same alignment using
+ data dependence information. */
+ if (loop_vinfo)
+ {
+ VEC (ddr_p, heap) *ddrs = LOOP_VINFO_DDRS (loop_vinfo);
+ struct data_dependence_relation *ddr;
+ unsigned int i;
+
+ for (i = 0; VEC_iterate (ddr_p, ddrs, i, ddr); i++)
+ vect_find_same_alignment_drs (ddr, loop_vinfo);
+ }
+
if (!vect_compute_data_refs_alignment (loop_vinfo, bb_vinfo))
{
if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
}
return true;
}
+
if (vect_print_dump_info (REPORT_DETAILS))
- fprintf (vect_dump, "not consecutive access");
+ {
+ fprintf (vect_dump, "not consecutive access ");
+ print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
+ }
+
+ if (bb_vinfo)
+ {
+ /* Mark the statement as unvectorizable. */
+ STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (DR_STMT (dr))) = false;
+ return true;
+ }
+
return false;
}
datarefs = BB_VINFO_DATAREFS (bb_vinfo);
for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
- if (!vect_analyze_data_ref_access (dr))
+ if (STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (DR_STMT (dr)))
+ && !vect_analyze_data_ref_access (dr))
{
if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
fprintf (vect_dump, "not vectorized: complicated access pattern.");
- return false;
+
+ if (bb_vinfo)
+ {
+ /* Mark the statement as not vectorizable. */
+ STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (DR_STMT (dr))) = false;
+ continue;
+ }
+ else
+ return false;
}
return true;
*/
bool
-vect_analyze_data_refs (loop_vec_info loop_vinfo, bb_vec_info bb_vinfo)
+vect_analyze_data_refs (loop_vec_info loop_vinfo,
+ bb_vec_info bb_vinfo,
+ int *min_vf)
{
struct loop *loop = NULL;
basic_block bb = NULL;
VEC (data_reference_p, heap) *datarefs;
struct data_reference *dr;
tree scalar_type;
+ bool res;
if (vect_print_dump_info (REPORT_DETAILS))
fprintf (vect_dump, "=== vect_analyze_data_refs ===\n");
if (loop_vinfo)
{
loop = LOOP_VINFO_LOOP (loop_vinfo);
- compute_data_dependences_for_loop (loop, true,
- &LOOP_VINFO_DATAREFS (loop_vinfo),
- &LOOP_VINFO_DDRS (loop_vinfo));
+ res = compute_data_dependences_for_loop
+ (loop, true, &LOOP_VINFO_DATAREFS (loop_vinfo),
+ &LOOP_VINFO_DDRS (loop_vinfo));
+
+ if (!res)
+ {
+ if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
+ fprintf (vect_dump, "not vectorized: loop contains function calls"
+ " or data references that cannot be analyzed");
+ return false;
+ }
+
datarefs = LOOP_VINFO_DATAREFS (loop_vinfo);
}
else
{
bb = BB_VINFO_BB (bb_vinfo);
- compute_data_dependences_for_bb (bb, true,
- &BB_VINFO_DATAREFS (bb_vinfo),
- &BB_VINFO_DDRS (bb_vinfo));
+ res = compute_data_dependences_for_bb (bb, true,
+ &BB_VINFO_DATAREFS (bb_vinfo),
+ &BB_VINFO_DDRS (bb_vinfo));
+ if (!res)
+ {
+ if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
+ fprintf (vect_dump, "not vectorized: basic block contains function"
+ " calls or data references that cannot be analyzed");
+ return false;
+ }
+
datarefs = BB_VINFO_DATAREFS (bb_vinfo);
}
{
gimple stmt;
stmt_vec_info stmt_info;
- basic_block bb;
tree base, offset, init;
+ int vf;
if (!dr || !DR_REF (dr))
{
fprintf (vect_dump, "not vectorized: data ref analysis failed ");
print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
}
- return false;
+
+ if (bb_vinfo)
+ {
+ /* Mark the statement as not vectorizable. */
+ STMT_VINFO_VECTORIZABLE (stmt_info) = false;
+ continue;
+ }
+ else
+ return false;
}
if (TREE_CODE (DR_BASE_ADDRESS (dr)) == INTEGER_CST)
if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
fprintf (vect_dump, "not vectorized: base addr of dr is a "
"constant");
- return false;
+ if (bb_vinfo)
+ {
+ /* Mark the statement as not vectorizable. */
+ STMT_VINFO_VECTORIZABLE (stmt_info) = false;
+ continue;
+ }
+ else
+ return false;
}
base = unshare_expr (DR_BASE_ADDRESS (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
fprintf (vect_dump, " scalar_type: ");
print_generic_expr (vect_dump, scalar_type, TDF_DETAILS);
}
- return false;
+
+ if (bb_vinfo)
+ {
+ /* Mark the statement as not vectorizable. */
+ STMT_VINFO_VECTORIZABLE (stmt_info) = false;
+ continue;
+ }
+ else
+ return false;
}
+
+ /* Adjust the minimal vectorization factor according to the
+ vector type. */
+ vf = TYPE_VECTOR_SUBPARTS (STMT_VINFO_VECTYPE (stmt_info));
+ if (vf > *min_vf)
+ *min_vf = vf;
}
return true;
tree perm_dest, vect1, vect2, high, low;
gimple perm_stmt;
tree vectype = STMT_VINFO_VECTYPE (vinfo_for_stmt (stmt));
- tree scalar_dest;
int i;
unsigned int j;
enum tree_code high_code, low_code;
- scalar_dest = gimple_assign_lhs (stmt);
-
/* Check that the operation is supported. */
if (!vect_strided_store_supported (vectype))
return false;
stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
tree vectype = STMT_VINFO_VECTYPE (stmt_info);
enum machine_mode mode = TYPE_MODE (vectype);
- bool invariant_in_outerloop = false;
loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
struct loop *vect_loop = NULL;
bool nested_in_vect_loop = false;
vect_loop = LOOP_VINFO_LOOP (loop_vinfo);
nested_in_vect_loop = nested_in_vect_loop_p (vect_loop, stmt);
- if (nested_in_vect_loop)
- {
- tree outerloop_step = STMT_VINFO_DR_STEP (stmt_info);
- invariant_in_outerloop =
- (tree_int_cst_compare (outerloop_step, size_zero_node) == 0);
- }
-
/* Possibly unaligned access. */
/* We can choose between using the implicit realignment scheme (generating