tree-vect-analyze.c [plain text]
#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "errors.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 "tree-chrec.h"
#include "tree-data-ref.h"
#include "tree-scalar-evolution.h"
#include "tree-vectorizer.h"
static loop_vec_info vect_analyze_loop_form (struct loop *);
static bool vect_analyze_data_refs (loop_vec_info);
static bool vect_mark_stmts_to_be_vectorized (loop_vec_info);
static bool vect_analyze_scalar_cycles (loop_vec_info);
static bool vect_analyze_data_ref_accesses (loop_vec_info);
static bool vect_analyze_data_ref_dependences (loop_vec_info);
static bool vect_analyze_data_refs_alignment (loop_vec_info);
static bool vect_compute_data_refs_alignment (loop_vec_info);
static void vect_enhance_data_refs_alignment (loop_vec_info);
static bool vect_analyze_operations (loop_vec_info);
static bool exist_non_indexing_operands_for_use_p (tree, tree);
static void vect_mark_relevant (varray_type *, tree);
static bool vect_stmt_relevant_p (tree, loop_vec_info);
extern tree vect_get_loop_niters (struct loop *, tree *);
static bool vect_analyze_data_ref_dependence
(struct data_reference *, struct data_reference *, loop_vec_info);
static bool vect_compute_data_ref_alignment (struct data_reference *);
static bool vect_analyze_data_ref_access (struct data_reference *);
extern struct data_reference * vect_analyze_pointer_ref_access
(tree, tree, bool, tree, tree *, tree *);
static bool vect_can_advance_ivs_p (loop_vec_info);
static tree vect_get_ptr_offset (tree, tree, tree *);
static bool vect_analyze_offset_expr (tree, struct loop *, tree, tree *,
tree *, tree *);
static bool vect_base_addr_differ_p (struct data_reference *,
struct data_reference *drb, bool *);
static tree vect_object_analysis (tree, tree, bool, tree,
struct data_reference **, tree *, tree *,
tree *, bool *, tree *);
static tree vect_address_analysis (tree, tree, bool, tree,
struct data_reference *, tree *, tree *,
tree *, bool *);
static tree
vect_get_ptr_offset (tree ref ATTRIBUTE_UNUSED,
tree vectype ATTRIBUTE_UNUSED,
tree *offset ATTRIBUTE_UNUSED)
{
return NULL_TREE;
}
static bool
vect_analyze_offset_expr (tree expr,
struct loop *loop,
tree vectype_alignment,
tree *initial_offset,
tree *misalign,
tree *step)
{
tree oprnd0;
tree oprnd1;
tree left_offset = ssize_int (0);
tree right_offset = ssize_int (0);
tree left_misalign = ssize_int (0);
tree right_misalign = ssize_int (0);
tree left_step = ssize_int (0);
tree right_step = ssize_int (0);
enum tree_code code;
tree init, evolution;
*step = NULL_TREE;
*misalign = NULL_TREE;
*initial_offset = NULL_TREE;
expr = vect_strip_conversion (expr);
if (!expr)
return false;
if (TREE_CODE (expr) == INTEGER_CST)
{
*initial_offset = fold_convert (ssizetype, expr);
*misalign = fold_convert (ssizetype, expr);
*step = ssize_int (0);
return true;
}
if (SSA_VAR_P (expr))
{
tree access_fn = analyze_scalar_evolution (loop, expr);
if (access_fn == chrec_dont_know)
return false;
init = initial_condition_in_loop_num (access_fn, loop->num);
if (init == expr && !expr_invariant_in_loop_p (loop, init))
return false;
evolution = evolution_part_in_loop_num (access_fn, loop->num);
if (evolution && TREE_CODE (evolution) != INTEGER_CST)
return false;
if (TREE_CODE (init) == INTEGER_CST)
*misalign = fold_convert (ssizetype, init);
else
*misalign = NULL_TREE;
*initial_offset = fold_convert (ssizetype, init);
*step = evolution ? fold_convert (ssizetype, evolution) : ssize_int (0);
return true;
}
if (!BINARY_CLASS_P (expr))
{
if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
{
fprintf (vect_dump, "Not binary expression ");
print_generic_expr (vect_dump, expr, TDF_SLIM);
}
return false;
}
oprnd0 = TREE_OPERAND (expr, 0);
oprnd1 = TREE_OPERAND (expr, 1);
if (!vect_analyze_offset_expr (oprnd0, loop, vectype_alignment, &left_offset,
&left_misalign, &left_step)
|| !vect_analyze_offset_expr (oprnd1, loop, vectype_alignment,
&right_offset, &right_misalign, &right_step))
return false;
code = TREE_CODE (expr);
switch (code)
{
case MULT_EXPR:
if (TREE_CODE (right_offset) != INTEGER_CST)
return false;
left_offset = vect_strip_conversion (left_offset);
if (!left_offset)
return false;
if (SSA_VAR_P (left_offset))
{
if (integer_zerop (size_binop (TRUNC_MOD_EXPR, right_offset,
fold_convert (ssizetype, vectype_alignment))))
*misalign = ssize_int (0);
else
*misalign = NULL_TREE;
}
else
{
if (left_misalign)
*misalign = size_binop (code, left_misalign, right_misalign);
else
*misalign = NULL_TREE;
}
*step = size_binop (MULT_EXPR, left_step, right_offset);
break;
case PLUS_EXPR:
case MINUS_EXPR:
*step = size_binop (code, left_step, right_step);
if (left_misalign && right_misalign)
*misalign = size_binop (code, left_misalign, right_misalign);
else
*misalign = NULL_TREE;
break;
default:
gcc_unreachable ();
}
*initial_offset = fold_convert (ssizetype,
fold (build2 (code, TREE_TYPE (left_offset),
left_offset,
right_offset)));
return true;
}
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;
block_stmt_iterator si;
unsigned int vectorization_factor = 0;
int i;
bool ok;
tree scalar_type;
if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
fprintf (vect_dump, "=== vect_analyze_operations ===");
for (i = 0; i < nbbs; i++)
{
basic_block bb = bbs[i];
for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
{
tree stmt = bsi_stmt (si);
unsigned int nunits;
stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
tree vectype;
if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
{
fprintf (vect_dump, "==> examining statement: ");
print_generic_expr (vect_dump, stmt, TDF_SLIM);
}
gcc_assert (stmt_info);
if (!STMT_VINFO_RELEVANT_P (stmt_info))
{
if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
fprintf (vect_dump, "irrelevant.");
continue;
}
if (VECTOR_MODE_P (TYPE_MODE (TREE_TYPE (stmt))))
{
if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
LOOP_LOC (loop_vinfo)))
{
fprintf (vect_dump, "not vectorized: vector stmt in loop:");
print_generic_expr (vect_dump, stmt, TDF_SLIM);
}
return false;
}
if (STMT_VINFO_DATA_REF (stmt_info))
scalar_type = TREE_TYPE (DR_REF (STMT_VINFO_DATA_REF (stmt_info)));
else if (TREE_CODE (stmt) == MODIFY_EXPR)
scalar_type = TREE_TYPE (TREE_OPERAND (stmt, 0));
else
scalar_type = TREE_TYPE (stmt);
if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
{
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,
LOOP_LOC (loop_vinfo)))
{
fprintf (vect_dump,
"not vectorized: unsupported data-type ");
print_generic_expr (vect_dump, scalar_type, TDF_SLIM);
}
return false;
}
if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
{
fprintf (vect_dump, "vectype: ");
print_generic_expr (vect_dump, vectype, TDF_SLIM);
}
STMT_VINFO_VECTYPE (stmt_info) = vectype;
ok = (vectorizable_operation (stmt, NULL, NULL)
|| vectorizable_assignment (stmt, NULL, NULL)
|| vectorizable_load (stmt, NULL, NULL)
|| vectorizable_select (stmt, NULL, NULL)
|| vectorizable_store (stmt, NULL, NULL));
if (!ok)
{
if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
LOOP_LOC (loop_vinfo)))
{
fprintf (vect_dump, "not vectorized: stmt not supported: ");
print_generic_expr (vect_dump, stmt, TDF_SLIM);
}
return false;
}
nunits = GET_MODE_NUNITS (TYPE_MODE (vectype));
if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
fprintf (vect_dump, "nunits = %d", nunits);
if (vectorization_factor)
{
if (nunits != vectorization_factor)
{
if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
LOOP_LOC (loop_vinfo)))
fprintf (vect_dump, "not vectorized: mixed data-types");
return false;
}
}
else
vectorization_factor = nunits;
#ifdef ENABLE_CHECKING
gcc_assert (GET_MODE_SIZE (TYPE_MODE (scalar_type))
* vectorization_factor == UNITS_PER_SIMD_WORD);
#endif
}
}
if (vectorization_factor <= 1)
{
if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
LOOP_LOC (loop_vinfo)))
fprintf (vect_dump, "not vectorized: unsupported data-type");
return false;
}
LOOP_VINFO_VECT_FACTOR (loop_vinfo) = vectorization_factor;
if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
&& vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
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,
LOOP_LOC (loop_vinfo)))
fprintf (vect_dump, "not vectorized: iteration count too small.");
return false;
}
if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
|| LOOP_VINFO_INT_NITERS (loop_vinfo) % vectorization_factor != 0)
{
if (vect_print_dump_info (REPORT_DETAILS, LOOP_LOC (loop_vinfo)))
fprintf (vect_dump, "epilog loop required.");
if (!vect_can_advance_ivs_p (loop_vinfo))
{
if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
LOOP_LOC (loop_vinfo)))
fprintf (vect_dump,
"not vectorized: can't create epilog loop 1.");
return false;
}
if (!slpeel_can_duplicate_loop_p (loop, loop->exit_edges[0]))
{
if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
LOOP_LOC (loop_vinfo)))
fprintf (vect_dump,
"not vectorized: can't create epilog loop 2.");
return false;
}
}
return true;
}
static bool
exist_non_indexing_operands_for_use_p (tree use, tree stmt)
{
tree operand;
stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
if (!STMT_VINFO_DATA_REF (stmt_info))
return true;
if (TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME)
return false;
operand = TREE_OPERAND (stmt, 1);
if (TREE_CODE (operand) != SSA_NAME)
return false;
if (operand == use)
return true;
return false;
}
static bool
vect_analyze_scalar_cycles (loop_vec_info loop_vinfo)
{
tree phi;
struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
basic_block bb = loop->header;
tree dummy;
if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
fprintf (vect_dump, "=== vect_analyze_scalar_cycles ===");
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
{
tree access_fn = NULL;
if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
{
fprintf (vect_dump, "Analyze phi: ");
print_generic_expr (vect_dump, phi, TDF_SLIM);
}
if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi))))
{
if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
fprintf (vect_dump, "virtual phi. skip.");
continue;
}
access_fn =
analyze_scalar_evolution (loop, PHI_RESULT (phi));
if (!access_fn)
{
if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
LOOP_LOC (loop_vinfo)))
fprintf (vect_dump, "not vectorized: unsupported scalar cycle.");
return false;
}
if (vect_print_dump_info (REPORT_DETAILS,
LOOP_LOC (loop_vinfo)))
{
fprintf (vect_dump, "Access function of PHI: ");
print_generic_expr (vect_dump, access_fn, TDF_SLIM);
}
if (!vect_is_simple_iv_evolution (loop->num, access_fn, &dummy, &dummy))
{
if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
LOOP_LOC (loop_vinfo)))
fprintf (vect_dump, "not vectorized: unsupported scalar cycle.");
return false;
}
}
return true;
}
static bool
record_ptr_differ_p (tree base_a, tree base_b)
{
HOST_WIDE_INT alias_set_a, alias_set_b;
if (TREE_CODE (base_b) != COMPONENT_REF)
return false;
while (TREE_CODE (base_b) == COMPONENT_REF)
base_b = TREE_OPERAND (base_b, 0);
if ((TREE_CODE (base_a) == INDIRECT_REF && TREE_CODE (base_b) == VAR_DECL)
|| (TREE_CODE (base_b) == INDIRECT_REF && TREE_CODE (base_a) == VAR_DECL))
{
alias_set_a = TREE_CODE (base_a) == INDIRECT_REF ?
get_alias_set (TREE_OPERAND (base_a, 0)) : get_alias_set (base_a);
alias_set_b = TREE_CODE (base_b) == INDIRECT_REF ?
get_alias_set (TREE_OPERAND (base_b, 0)) : get_alias_set (base_b);
if (!alias_sets_conflict_p (alias_set_a, alias_set_b))
return true;
}
return false;
}
static bool
vect_base_object_differ_p (struct data_reference *dra,
struct data_reference *drb,
bool *differ_p)
{
tree base_a = DR_BASE_NAME (dra);
tree base_b = DR_BASE_NAME (drb);
if (!base_a || !base_b)
return false;
if (base_a == base_b)
{
*differ_p = false;
return true;
}
if (TREE_CODE (base_a) == INDIRECT_REF && TREE_CODE (base_b) == INDIRECT_REF
&& TREE_OPERAND (base_a, 0) == TREE_OPERAND (base_b, 0))
{
*differ_p = false;
return true;
}
if (TREE_CODE (base_a) == COMPONENT_REF && TREE_CODE (base_b) == COMPONENT_REF
&& TREE_OPERAND (base_a, 0) == TREE_OPERAND (base_b, 0)
&& TREE_OPERAND (base_a, 1) == TREE_OPERAND (base_b, 1))
{
*differ_p = false;
return true;
}
if (TREE_CODE (base_a) == VAR_DECL && TREE_CODE (base_b) == VAR_DECL)
{
*differ_p = true;
return true;
}
if (TREE_CODE (base_a) == COMPONENT_REF && TREE_CODE (base_b) == COMPONENT_REF
&& ((TREE_CODE (TREE_OPERAND (base_a, 0)) == VAR_DECL
&& TREE_CODE (TREE_OPERAND (base_b, 0)) == VAR_DECL
&& TREE_OPERAND (base_a, 0) != TREE_OPERAND (base_b, 0))
|| (TREE_CODE (TREE_TYPE (TREE_OPERAND (base_a, 0))) == RECORD_TYPE
&& TREE_CODE (TREE_TYPE (TREE_OPERAND (base_b, 0))) == RECORD_TYPE
&& TREE_OPERAND (base_a, 1) != TREE_OPERAND (base_b, 1))))
{
*differ_p = true;
return true;
}
if (TREE_CODE (base_a) == VAR_DECL && TREE_CODE (base_b) == INDIRECT_REF)
{
HOST_WIDE_INT alias_set_a, alias_set_b;
alias_set_a = get_alias_set (base_a);
alias_set_b = get_alias_set (base_b);
if (!alias_sets_conflict_p (alias_set_a, alias_set_b))
*differ_p = true;
return true;
}
if (TREE_CODE (base_b) == VAR_DECL && TREE_CODE (base_a) == INDIRECT_REF)
{
HOST_WIDE_INT alias_set_a, alias_set_b;
alias_set_a = get_alias_set (base_a);
alias_set_b = get_alias_set (base_b);
if (!alias_sets_conflict_p (alias_set_a, alias_set_b))
*differ_p = true;
return true;
}
if (record_ptr_differ_p (base_a, base_b) ||
record_ptr_differ_p (base_b, base_a))
{
*differ_p = true;
return true;
}
return false;
}
static bool
vect_base_addr_differ_p (struct data_reference *dra,
struct data_reference *drb,
bool *differ_p)
{
tree stmt_a = DR_STMT (dra);
stmt_vec_info stmt_info_a = vinfo_for_stmt (stmt_a);
tree stmt_b = DR_STMT (drb);
stmt_vec_info stmt_info_b = vinfo_for_stmt (stmt_b);
tree addr_a = STMT_VINFO_VECT_DR_BASE_ADDRESS (stmt_info_a);
tree addr_b = STMT_VINFO_VECT_DR_BASE_ADDRESS (stmt_info_b);
tree type_a = TREE_TYPE (addr_a);
tree type_b = TREE_TYPE (addr_b);
HOST_WIDE_INT alias_set_a, alias_set_b;
gcc_assert (POINTER_TYPE_P (type_a) && POINTER_TYPE_P (type_b));
if (TREE_CODE (addr_a) == ADDR_EXPR && TREE_CODE (addr_b) == ADDR_EXPR)
return array_base_name_differ_p (dra, drb, differ_p);
alias_set_a = (TREE_CODE (addr_a) == ADDR_EXPR) ?
get_alias_set (TREE_OPERAND (addr_a, 0)) : get_alias_set (addr_a);
alias_set_b = (TREE_CODE (addr_b) == ADDR_EXPR) ?
get_alias_set (TREE_OPERAND (addr_b, 0)) : get_alias_set (addr_b);
if (!alias_sets_conflict_p (alias_set_a, alias_set_b))
{
if (DR_TYPE (dra) == ARRAY_REF_TYPE &&
DR_TYPE (drb) == ARRAY_REF_TYPE)
return vect_base_object_differ_p (dra, drb, differ_p);
*differ_p = true;
return true;
}
else if ((TYPE_RESTRICT (type_a) && !DR_IS_READ (dra))
|| (TYPE_RESTRICT (type_b) && !DR_IS_READ (drb)))
{
*differ_p = true;
return true;
}
return false;
}
static unsigned int
vect_build_dist_vector (struct loop *loop,
struct data_dependence_relation *ddr)
{
struct loop *loop_nest = loop;
unsigned int loop_depth = 1;
while (loop_nest)
{
if (loop_nest->outer && loop_nest->outer->outer)
{
loop_nest = loop_nest->outer;
loop_depth++;
}
else
break;
}
compute_subscript_distance (ddr);
build_classic_dist_vector (ddr, loops_num, loop_nest->depth);
return loop_depth - 1;
}
static bool
vect_analyze_data_ref_dependence (struct data_reference *dra,
struct data_reference *drb,
loop_vec_info loop_vinfo)
{
bool differ_p;
struct data_dependence_relation *ddr;
int vectorization_factor = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
unsigned int loop_depth = 0;
int dist;
if (!vect_base_addr_differ_p (dra, drb, &differ_p))
{
if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
LOOP_LOC (loop_vinfo)))
{
fprintf (vect_dump,
"not vectorized: 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);
}
return true;
}
if (differ_p)
return false;
ddr = initialize_data_dependence_relation (dra, drb);
compute_affine_dependence (ddr);
if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
return false;
if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
return true;
loop_depth = vect_build_dist_vector (loop, ddr);
if (!DDR_DIST_VECT (ddr))
return true;
dist = DDR_DIST_VECT (ddr)[loop_depth];
if (dist == 0)
return false;
if (abs(dist) >= vectorization_factor)
return false;
if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
LOOP_LOC (loop_vinfo)))
{
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;
}
static bool
vect_analyze_data_ref_dependences (loop_vec_info loop_vinfo)
{
unsigned int i, j;
varray_type loop_write_refs = LOOP_VINFO_DATAREF_WRITES (loop_vinfo);
varray_type loop_read_refs = LOOP_VINFO_DATAREF_READS (loop_vinfo);
if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
fprintf (vect_dump, "=== vect_analyze_dependences ===");
if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
fprintf (vect_dump, "compare all store-store pairs.");
for (i = 0; i < VARRAY_ACTIVE_SIZE (loop_write_refs); i++)
{
for (j = i + 1; j < VARRAY_ACTIVE_SIZE (loop_write_refs); j++)
{
struct data_reference *dra =
VARRAY_GENERIC_PTR (loop_write_refs, i);
struct data_reference *drb =
VARRAY_GENERIC_PTR (loop_write_refs, j);
if (vect_analyze_data_ref_dependence (dra, drb, loop_vinfo))
return false;
}
}
if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
fprintf (vect_dump, "compare all load-store pairs.");
for (i = 0; i < VARRAY_ACTIVE_SIZE (loop_read_refs); i++)
{
for (j = 0; j < VARRAY_ACTIVE_SIZE (loop_write_refs); j++)
{
struct data_reference *dra = VARRAY_GENERIC_PTR (loop_read_refs, i);
struct data_reference *drb =
VARRAY_GENERIC_PTR (loop_write_refs, j);
if (vect_analyze_data_ref_dependence (dra, drb, loop_vinfo))
return false;
}
}
return true;
}
static bool
vect_compute_data_ref_alignment (struct data_reference *dr)
{
tree stmt = DR_STMT (dr);
stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
tree ref = DR_REF (dr);
tree vectype;
tree base, alignment;
bool base_aligned_p;
tree misalign;
if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
fprintf (vect_dump, "vect_compute_data_ref_alignment:");
DR_MISALIGNMENT (dr) = -1;
misalign = STMT_VINFO_VECT_MISALIGNMENT (stmt_info);
base_aligned_p = STMT_VINFO_VECT_BASE_ALIGNED_P (stmt_info);
base = build_fold_indirect_ref (STMT_VINFO_VECT_DR_BASE_ADDRESS (stmt_info));
vectype = STMT_VINFO_VECTYPE (stmt_info);
if (misalign)
{
HOST_WIDE_INT misalign_b = int_cst_value (misalign);
HOST_WIDE_INT elm_size_b = int_cst_value (TYPE_SIZE_UNIT (TREE_TYPE (vectype)));
if (misalign_b % elm_size_b)
{
if (vect_print_dump_info (REPORT_ALIGNMENT, UNKNOWN_LOC))
{
fprintf (vect_dump, "Inappropriate alignment for vectorizer: \
misalignment = " HOST_WIDE_INT_PRINT_DEC, misalign_b);
}
return false;
}
}
if (!misalign)
{
if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
{
fprintf (vect_dump, "Unknown alignment for access: ");
print_generic_expr (vect_dump, base, TDF_SLIM);
}
return true;
}
if (!base_aligned_p)
{
if (!vect_can_force_dr_alignment_p (base, TYPE_ALIGN (vectype)))
{
if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
{
fprintf (vect_dump, "can't force alignment of ref: ");
print_generic_expr (vect_dump, ref, TDF_SLIM);
}
return true;
}
if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
fprintf (vect_dump, "force alignment");
DECL_ALIGN (base) = TYPE_ALIGN (vectype);
DECL_USER_ALIGN (base) = 1;
}
gcc_assert (base_aligned_p
|| (TREE_CODE (base) == VAR_DECL
&& DECL_ALIGN (base) >= TYPE_ALIGN (vectype)));
alignment = ssize_int (TYPE_ALIGN (vectype)/BITS_PER_UNIT);
misalign = size_binop (TRUNC_MOD_EXPR, misalign, alignment);
if (tree_int_cst_sgn (misalign) < 0)
{
if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
fprintf (vect_dump, "unexpected misalign value");
return false;
}
DR_MISALIGNMENT (dr) = tree_low_cst (misalign, 1);
if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
fprintf (vect_dump, "misalign = %d bytes", DR_MISALIGNMENT (dr));
return true;
}
static bool
vect_compute_data_refs_alignment (loop_vec_info loop_vinfo)
{
varray_type loop_write_datarefs = LOOP_VINFO_DATAREF_WRITES (loop_vinfo);
varray_type loop_read_datarefs = LOOP_VINFO_DATAREF_READS (loop_vinfo);
unsigned int i;
for (i = 0; i < VARRAY_ACTIVE_SIZE (loop_write_datarefs); i++)
{
struct data_reference *dr = VARRAY_GENERIC_PTR (loop_write_datarefs, i);
if (!vect_compute_data_ref_alignment (dr))
return false;
}
for (i = 0; i < VARRAY_ACTIVE_SIZE (loop_read_datarefs); i++)
{
struct data_reference *dr = VARRAY_GENERIC_PTR (loop_read_datarefs, i);
if (!vect_compute_data_ref_alignment (dr))
return false;
}
return true;
}
static void
vect_enhance_data_refs_alignment (loop_vec_info loop_vinfo)
{
varray_type loop_read_datarefs = LOOP_VINFO_DATAREF_READS (loop_vinfo);
varray_type loop_write_datarefs = LOOP_VINFO_DATAREF_WRITES (loop_vinfo);
unsigned int i;
for (i = 0; i < VARRAY_ACTIVE_SIZE (loop_write_datarefs); i++)
{
struct data_reference *dr = VARRAY_GENERIC_PTR (loop_write_datarefs, i);
if (unknown_alignment_for_access_p (dr))
{
tree base_type;
tree type = (TREE_TYPE (DR_REF (dr)));
tree ba = DR_BASE_NAME (dr);
bool is_packed = false;
if (ba && TREE_CODE (ba) == COMPONENT_REF)
{
base_type = TREE_TYPE (TREE_OPERAND (ba, 0));
is_packed = TYPE_PACKED (base_type);
}
if (targetm.vectorize.vector_alignment_reachable
&& targetm.vectorize.vector_alignment_reachable (type, is_packed))
{
LOOP_VINFO_UNALIGNED_DR (loop_vinfo) = dr;
LOOP_DO_PEELING_FOR_ALIGNMENT (loop_vinfo) = true;
}
else
{
LOOP_DO_PEELING_FOR_ALIGNMENT (loop_vinfo) = false;
break;
}
}
if (!aligned_access_p (dr))
{
LOOP_VINFO_UNALIGNED_DR (loop_vinfo) = dr;
LOOP_DO_PEELING_FOR_ALIGNMENT (loop_vinfo) = true;
break;
}
}
if (!LOOP_VINFO_UNALIGNED_DR (loop_vinfo))
{
if (vect_print_dump_info (REPORT_DETAILS, LOOP_LOC (loop_vinfo)))
fprintf (vect_dump, "Peeling for alignment will not be applied.");
return;
}
else
if (vect_print_dump_info (REPORT_DETAILS, LOOP_LOC (loop_vinfo)))
fprintf (vect_dump, "Peeling for alignment will be applied.");
for (i = 0; i < VARRAY_ACTIVE_SIZE (loop_write_datarefs); i++)
{
struct data_reference *dr = VARRAY_GENERIC_PTR (loop_write_datarefs, i);
if (dr == LOOP_VINFO_UNALIGNED_DR (loop_vinfo))
{
DR_MISALIGNMENT (dr) = 0;
if (vect_print_dump_info (REPORT_ALIGNMENT, LOOP_LOC (loop_vinfo)))
fprintf (vect_dump, "Alignment of access forced using peeling.");
}
else
DR_MISALIGNMENT (dr) = -1;
}
for (i = 0; i < VARRAY_ACTIVE_SIZE (loop_read_datarefs); i++)
{
struct data_reference *dr = VARRAY_GENERIC_PTR (loop_read_datarefs, i);
if (dr == LOOP_VINFO_UNALIGNED_DR (loop_vinfo))
{
DR_MISALIGNMENT (dr) = 0;
if (vect_print_dump_info (REPORT_ALIGNMENT, LOOP_LOC (loop_vinfo)))
fprintf (vect_dump, "Alignment of access forced using peeling.");
}
else
DR_MISALIGNMENT (dr) = -1;
}
}
static bool
vect_analyze_data_refs_alignment (loop_vec_info loop_vinfo)
{
varray_type loop_read_datarefs = LOOP_VINFO_DATAREF_READS (loop_vinfo);
varray_type loop_write_datarefs = LOOP_VINFO_DATAREF_WRITES (loop_vinfo);
enum dr_alignment_support supportable_dr_alignment;
unsigned int i;
if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
fprintf (vect_dump, "=== vect_analyze_data_refs_alignment ===");
if (!vect_compute_data_refs_alignment (loop_vinfo))
{
if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
LOOP_LOC (loop_vinfo)))
fprintf (vect_dump,
"not vectorized: can't calculate alignment for data ref.");
return false;
}
vect_enhance_data_refs_alignment (loop_vinfo);
for (i = 0; i < VARRAY_ACTIVE_SIZE (loop_read_datarefs); i++)
{
struct data_reference *dr = VARRAY_GENERIC_PTR (loop_read_datarefs, i);
supportable_dr_alignment = vect_supportable_dr_alignment (dr);
if (!supportable_dr_alignment)
{
if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
LOOP_LOC (loop_vinfo)))
fprintf (vect_dump, "not vectorized: unsupported unaligned load.");
return false;
}
if (supportable_dr_alignment != dr_aligned
&& (vect_print_dump_info (REPORT_ALIGNMENT, LOOP_LOC (loop_vinfo))))
fprintf (vect_dump, "Vectorizing an unaligned access.");
}
for (i = 0; i < VARRAY_ACTIVE_SIZE (loop_write_datarefs); i++)
{
struct data_reference *dr = VARRAY_GENERIC_PTR (loop_write_datarefs, i);
supportable_dr_alignment = vect_supportable_dr_alignment (dr);
if (!supportable_dr_alignment)
{
if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
LOOP_LOC (loop_vinfo)))
fprintf (vect_dump, "not vectorized: unsupported unaligned store.");
return false;
}
if (supportable_dr_alignment != dr_aligned
&& (vect_print_dump_info (REPORT_ALIGNMENT, LOOP_LOC (loop_vinfo))))
fprintf (vect_dump, "Vectorizing an unaligned access.");
}
return true;
}
static bool
vect_analyze_data_ref_access (struct data_reference *dr)
{
tree stmt = DR_STMT (dr);
stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
tree step = STMT_VINFO_VECT_STEP (stmt_info);
tree scalar_type = TREE_TYPE (DR_REF (dr));
if (!step || tree_int_cst_compare (step, TYPE_SIZE_UNIT (scalar_type)))
{
if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
fprintf (vect_dump, "not consecutive access");
return false;
}
return true;
}
static bool
vect_analyze_data_ref_accesses (loop_vec_info loop_vinfo)
{
unsigned int i;
varray_type loop_write_datarefs = LOOP_VINFO_DATAREF_WRITES (loop_vinfo);
varray_type loop_read_datarefs = LOOP_VINFO_DATAREF_READS (loop_vinfo);
if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
fprintf (vect_dump, "=== vect_analyze_data_ref_accesses ===");
for (i = 0; i < VARRAY_ACTIVE_SIZE (loop_write_datarefs); i++)
{
struct data_reference *dr = VARRAY_GENERIC_PTR (loop_write_datarefs, i);
bool ok = vect_analyze_data_ref_access (dr);
if (!ok)
{
if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
LOOP_LOC (loop_vinfo)))
fprintf (vect_dump, "not vectorized: complicated access pattern.");
return false;
}
}
for (i = 0; i < VARRAY_ACTIVE_SIZE (loop_read_datarefs); i++)
{
struct data_reference *dr = VARRAY_GENERIC_PTR (loop_read_datarefs, i);
bool ok = vect_analyze_data_ref_access (dr);
if (!ok)
{
if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
LOOP_LOC (loop_vinfo)))
fprintf (vect_dump, "not vectorized: complicated access pattern.");
return false;
}
}
return true;
}
struct data_reference *
vect_analyze_pointer_ref_access (tree memref, tree stmt, bool is_read,
tree access_fn, tree *ptr_init, tree *ptr_step)
{
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 step, init;
tree reftype, innertype;
tree indx_access_fn;
int loopnum = loop->num;
struct data_reference *dr;
if (!vect_is_simple_iv_evolution (loopnum, access_fn, &init, &step))
{
if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
LOOP_LOC (loop_vinfo)))
fprintf (vect_dump, "not vectorized: pointer access is not simple.");
return NULL;
}
STRIP_NOPS (init);
if (!expr_invariant_in_loop_p (loop, init))
{
if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
LOOP_LOC (loop_vinfo)))
fprintf (vect_dump,
"not vectorized: initial condition is not loop invariant.");
return NULL;
}
if (TREE_CODE (step) != INTEGER_CST)
{
if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
LOOP_LOC (loop_vinfo)))
fprintf (vect_dump,
"not vectorized: non constant step for pointer access.");
return NULL;
}
reftype = TREE_TYPE (TREE_OPERAND (memref, 0));
if (!POINTER_TYPE_P (reftype))
{
if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
LOOP_LOC (loop_vinfo)))
fprintf (vect_dump, "not vectorized: unexpected pointer access form.");
return NULL;
}
if (!POINTER_TYPE_P (TREE_TYPE (init)))
{
if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
LOOP_LOC (loop_vinfo)))
fprintf (vect_dump, "not vectorized: unexpected pointer access form.");
return NULL;
}
*ptr_step = fold_convert (ssizetype, step);
innertype = TREE_TYPE (reftype);
if (!COMPLETE_TYPE_P (innertype))
{
if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
LOOP_LOC (loop_vinfo)))
fprintf (vect_dump, "not vectorized: pointer to incomplete type.");
return NULL;
}
if (!integer_zerop (size_binop (TRUNC_MOD_EXPR, *ptr_step,
fold_convert (ssizetype, TYPE_SIZE_UNIT (innertype)))))
{
if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
LOOP_LOC (loop_vinfo)))
fprintf (vect_dump, "not vectorized: non consecutive access.");
return NULL;
}
indx_access_fn =
build_polynomial_chrec (loopnum, integer_zero_node, integer_one_node);
if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
{
fprintf (vect_dump, "Access function of ptr indx: ");
print_generic_expr (vect_dump, indx_access_fn, TDF_SLIM);
}
dr = init_data_ref (stmt, memref, NULL_TREE, indx_access_fn, is_read);
*ptr_init = init;
return dr;
}
static tree
vect_address_analysis (tree expr, tree stmt, bool is_read, tree vectype,
struct data_reference *dr, tree *offset, tree *misalign,
tree *step, bool *base_aligned)
{
tree oprnd0, oprnd1, base_address, offset_expr, base_addr0, base_addr1;
tree address_offset = ssize_int (0), address_misalign = ssize_int (0);
tree dummy;
switch (TREE_CODE (expr))
{
case PLUS_EXPR:
case MINUS_EXPR:
oprnd0 = TREE_OPERAND (expr, 0);
oprnd1 = TREE_OPERAND (expr, 1);
STRIP_NOPS (oprnd0);
STRIP_NOPS (oprnd1);
base_addr0 = vect_address_analysis (oprnd0, stmt, is_read, vectype, dr,
&address_offset, &address_misalign, step,
base_aligned);
base_addr1 = vect_address_analysis (oprnd1, stmt, is_read, vectype, dr,
&address_offset, &address_misalign, step,
base_aligned);
if ((base_addr0 && base_addr1) || (!base_addr0 && !base_addr1))
return NULL_TREE;
oprnd0 = TREE_OPERAND (expr, 0);
oprnd1 = TREE_OPERAND (expr, 1);
offset_expr = base_addr0 ?
fold_convert (ssizetype, oprnd1) : fold_convert (ssizetype, oprnd0);
if (TREE_CODE (offset_expr) == INTEGER_CST && address_misalign)
*misalign = size_binop (TREE_CODE (expr), address_misalign,
offset_expr);
else
*misalign = NULL_TREE;
*offset = size_binop (TREE_CODE (expr), address_offset, offset_expr);
return base_addr0 ? base_addr0 : base_addr1;
case ADDR_EXPR:
base_address = vect_object_analysis (TREE_OPERAND (expr, 0), stmt, is_read,
vectype, &dr, offset, misalign, step,
base_aligned, &dummy);
return base_address;
case SSA_NAME:
if (!POINTER_TYPE_P (TREE_TYPE (expr)))
return NULL_TREE;
if (TYPE_ALIGN (TREE_TYPE (TREE_TYPE (expr))) < TYPE_ALIGN (vectype))
{
if (vect_get_ptr_offset (expr, vectype, misalign))
*base_aligned = true;
else
*base_aligned = false;
}
else
{
*base_aligned = true;
*misalign = ssize_int (0);
}
*offset = ssize_int (0);
*step = ssize_int (0);
return expr;
default:
return NULL_TREE;
}
}
static tree
vect_object_analysis (tree memref, tree stmt, bool is_read,
tree vectype, struct data_reference **dr,
tree *offset, tree *misalign, tree *step,
bool *base_aligned, tree *memtag)
{
tree base = NULL_TREE, base_address = NULL_TREE;
tree object_offset = ssize_int (0), object_misalign = ssize_int (0);
tree object_step = ssize_int (0), address_step = ssize_int (0);
bool object_base_aligned = true, address_base_aligned = true;
tree address_offset = ssize_int (0), address_misalign = ssize_int (0);
HOST_WIDE_INT pbitsize, pbitpos;
tree poffset, bit_pos_in_bytes;
enum machine_mode pmode;
int punsignedp, pvolatilep;
tree ptr_step = ssize_int (0), ptr_init = NULL_TREE;
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);
struct data_reference *ptr_dr = NULL;
tree access_fn, evolution_part, address_to_analyze;
if (handled_component_p (memref))
{
base = get_inner_reference (memref, &pbitsize, &pbitpos, &poffset,
&pmode, &punsignedp, &pvolatilep, false);
if (!base)
return NULL_TREE;
if (poffset
&& !vect_analyze_offset_expr (poffset, loop, TYPE_SIZE_UNIT (vectype),
&object_offset, &object_misalign, &object_step))
{
if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
{
fprintf (vect_dump, "failed to compute offset or step for ");
print_generic_expr (vect_dump, memref, TDF_SLIM);
}
return NULL_TREE;
}
bit_pos_in_bytes = ssize_int (pbitpos/BITS_PER_UNIT);
if (pbitpos%BITS_PER_UNIT)
{
if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
fprintf (vect_dump, "bit offset alignment.");
return NULL_TREE;
}
object_offset = size_binop (PLUS_EXPR, bit_pos_in_bytes, object_offset);
if (object_misalign)
object_misalign = size_binop (PLUS_EXPR, object_misalign,
bit_pos_in_bytes);
if (!(*dr))
{
if (TREE_CODE (memref) == ARRAY_REF)
*dr = analyze_array (stmt, memref, is_read);
else
return NULL_TREE;
}
memref = base;
}
if (DECL_P (memref))
{
if (!(*dr))
{
if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
{
fprintf (vect_dump, "unhandled decl ");
print_generic_expr (vect_dump, memref, TDF_SLIM);
}
return NULL_TREE;
}
if (DECL_ALIGN (memref) >= TYPE_ALIGN (vectype))
object_base_aligned = true;
else
object_base_aligned = false;
if (!DR_BASE_NAME ((*dr)))
DR_BASE_NAME ((*dr)) = memref;
base_address = build_fold_addr_expr (memref);
*memtag = memref;
}
else if (TREE_CODE (memref) == INDIRECT_REF)
{
access_fn = analyze_scalar_evolution (loop, TREE_OPERAND (memref, 0));
if (!access_fn)
{
if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
LOOP_LOC (loop_vinfo)))
fprintf (vect_dump, "not vectorized: complicated pointer access.");
return NULL_TREE;
}
if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
{
fprintf (vect_dump, "Access function of ptr: ");
print_generic_expr (vect_dump, access_fn, TDF_SLIM);
}
evolution_part = evolution_part_in_loop_num (access_fn, loop->num);
if (evolution_part)
{
ptr_dr = vect_analyze_pointer_ref_access (memref, stmt, is_read,
access_fn, &ptr_init, &ptr_step);
if (!(ptr_dr))
return NULL_TREE;
object_step = size_binop (PLUS_EXPR, object_step, ptr_step);
address_to_analyze = ptr_init;
}
else
{
if (!(*dr))
{
if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
LOOP_LOC (loop_vinfo)))
fprintf (vect_dump, "not vectorized: ptr is loop invariant.");
return NULL_TREE;
}
address_to_analyze = initial_condition_in_loop_num (access_fn,
loop->num);
}
*dr = (*dr) ? *dr : ptr_dr;
base_address = vect_address_analysis (address_to_analyze, stmt, is_read,
vectype, *dr, &address_offset, &address_misalign,
&address_step, &address_base_aligned);
if (!base_address)
return NULL_TREE;
switch (TREE_CODE (base_address))
{
case SSA_NAME:
*memtag = get_var_ann (SSA_NAME_VAR (base_address))->type_mem_tag;
if (!(*memtag) && TREE_CODE (TREE_OPERAND (memref, 0)) == SSA_NAME)
*memtag = get_var_ann (
SSA_NAME_VAR (TREE_OPERAND (memref, 0)))->type_mem_tag;
break;
case ADDR_EXPR:
*memtag = TREE_OPERAND (base_address, 0);
break;
default:
if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
LOOP_LOC (loop_vinfo)))
{
fprintf (vect_dump, "not vectorized: no memtag ref: ");
print_generic_expr (vect_dump, memref, TDF_SLIM);
}
return NULL_TREE;
}
}
if (!base_address)
return NULL_TREE;
*offset = size_binop (PLUS_EXPR, object_offset, address_offset);
if (object_misalign && address_misalign)
*misalign = size_binop (PLUS_EXPR, object_misalign, address_misalign);
else
*misalign = NULL_TREE;
*step = size_binop (PLUS_EXPR, object_step, address_step);
*base_aligned = object_base_aligned && address_base_aligned;
if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
{
fprintf (vect_dump, "Results of object analysis for: ");
print_generic_expr (vect_dump, memref, TDF_SLIM);
fprintf (vect_dump, "\n\tbase_address: ");
print_generic_expr (vect_dump, base_address, TDF_SLIM);
fprintf (vect_dump, "\n\toffset: ");
print_generic_expr (vect_dump, *offset, TDF_SLIM);
fprintf (vect_dump, "\n\tstep: ");
print_generic_expr (vect_dump, *step, TDF_SLIM);
fprintf (vect_dump, "\n\tbase aligned %d\n\tmisalign: ", *base_aligned);
print_generic_expr (vect_dump, *misalign, TDF_SLIM);
}
return base_address;
}
static bool
vect_analyze_data_refs (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;
block_stmt_iterator si;
int j;
struct data_reference *dr;
if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
fprintf (vect_dump, "=== vect_analyze_data_refs ===");
for (j = 0; j < nbbs; j++)
{
basic_block bb = bbs[j];
for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
{
bool is_read = false;
tree stmt = bsi_stmt (si);
stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
v_may_def_optype v_may_defs = STMT_V_MAY_DEF_OPS (stmt);
v_must_def_optype v_must_defs = STMT_V_MUST_DEF_OPS (stmt);
vuse_optype vuses = STMT_VUSE_OPS (stmt);
varray_type *datarefs = NULL;
int nvuses, nv_may_defs, nv_must_defs;
tree memref = NULL;
tree scalar_type, vectype;
tree base, offset, misalign, step, tag;
bool base_aligned;
if (!vuses && !v_may_defs && !v_must_defs)
continue;
nvuses = NUM_VUSES (vuses);
nv_may_defs = NUM_V_MAY_DEFS (v_may_defs);
nv_must_defs = NUM_V_MUST_DEFS (v_must_defs);
if (nvuses && (nv_may_defs || nv_must_defs))
{
if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
{
fprintf (vect_dump, "unexpected vdefs and vuses in stmt: ");
print_generic_expr (vect_dump, stmt, TDF_SLIM);
}
return false;
}
if (TREE_CODE (stmt) != MODIFY_EXPR)
{
if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
{
fprintf (vect_dump, "unexpected vops in stmt: ");
print_generic_expr (vect_dump, stmt, TDF_SLIM);
}
return false;
}
if (vuses)
{
memref = TREE_OPERAND (stmt, 1);
datarefs = &(LOOP_VINFO_DATAREF_READS (loop_vinfo));
is_read = true;
}
else
{
memref = TREE_OPERAND (stmt, 0);
datarefs = &(LOOP_VINFO_DATAREF_WRITES (loop_vinfo));
is_read = false;
}
scalar_type = TREE_TYPE (memref);
vectype = get_vectype_for_scalar_type (scalar_type);
if (!vectype)
{
if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
{
fprintf (vect_dump, "no vectype for stmt: ");
print_generic_expr (vect_dump, stmt, TDF_SLIM);
fprintf (vect_dump, " scalar_type: ");
print_generic_expr (vect_dump, scalar_type, TDF_DETAILS);
}
return false;
}
dr = NULL;
base = vect_object_analysis (memref, stmt, is_read, vectype, &dr,
&offset, &misalign, &step,
&base_aligned, &tag);
if (!base)
{
if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
LOOP_LOC (loop_vinfo)))
{
fprintf (vect_dump, "not vectorized: unhandled data ref: ");
print_generic_expr (vect_dump, stmt, TDF_SLIM);
}
return false;
}
STMT_VINFO_VECT_DR_BASE_ADDRESS (stmt_info) = base;
STMT_VINFO_VECT_INIT_OFFSET (stmt_info) = offset;
STMT_VINFO_VECT_STEP (stmt_info) = step;
STMT_VINFO_VECT_MISALIGNMENT (stmt_info) = misalign;
STMT_VINFO_VECT_BASE_ALIGNED_P (stmt_info) = base_aligned;
STMT_VINFO_MEMTAG (stmt_info) = tag;
STMT_VINFO_VECTYPE (stmt_info) = vectype;
VARRAY_PUSH_GENERIC_PTR (*datarefs, dr);
STMT_VINFO_DATA_REF (stmt_info) = dr;
}
}
return true;
}
static void
vect_mark_relevant (varray_type *worklist, tree stmt)
{
stmt_vec_info stmt_info;
if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
fprintf (vect_dump, "mark relevant.");
if (TREE_CODE (stmt) == PHI_NODE)
{
VARRAY_PUSH_TREE (*worklist, stmt);
return;
}
stmt_info = vinfo_for_stmt (stmt);
if (!stmt_info)
{
if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
{
fprintf (vect_dump, "mark relevant: no stmt info!!.");
print_generic_expr (vect_dump, stmt, TDF_SLIM);
}
return;
}
if (STMT_VINFO_RELEVANT_P (stmt_info))
{
if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
fprintf (vect_dump, "already marked relevant.");
return;
}
STMT_VINFO_RELEVANT_P (stmt_info) = 1;
VARRAY_PUSH_TREE (*worklist, stmt);
}
static bool
vect_stmt_relevant_p (tree stmt, loop_vec_info loop_vinfo)
{
v_may_def_optype v_may_defs;
v_must_def_optype v_must_defs;
struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
int i;
dataflow_t df;
int num_uses;
if (is_ctrl_stmt (stmt) && (stmt != LOOP_VINFO_EXIT_COND (loop_vinfo)))
return true;
if (TREE_CODE (stmt) != PHI_NODE)
{
v_may_defs = STMT_V_MAY_DEF_OPS (stmt);
v_must_defs = STMT_V_MUST_DEF_OPS (stmt);
if (v_may_defs || v_must_defs)
{
if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
fprintf (vect_dump, "vec_stmt_relevant_p: stmt has vdefs.");
return true;
}
}
df = get_immediate_uses (stmt);
num_uses = num_immediate_uses (df);
for (i = 0; i < num_uses; i++)
{
tree use = immediate_use (df, i);
basic_block bb = bb_for_stmt (use);
if (!flow_bb_inside_loop_p (loop, bb))
{
if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
fprintf (vect_dump, "vec_stmt_relevant_p: used out of loop.");
return true;
}
}
return false;
}
static bool
vect_mark_stmts_to_be_vectorized (loop_vec_info loop_vinfo)
{
varray_type worklist;
struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo);
unsigned int nbbs = loop->num_nodes;
block_stmt_iterator si;
tree stmt;
stmt_ann_t ann;
unsigned int i;
int j;
use_optype use_ops;
stmt_vec_info stmt_info;
basic_block bb;
tree phi;
if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
fprintf (vect_dump, "=== vect_mark_stmts_to_be_vectorized ===");
bb = loop->header;
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
{
if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
{
fprintf (vect_dump, "init: phi relevant? ");
print_generic_expr (vect_dump, phi, TDF_SLIM);
}
if (vect_stmt_relevant_p (phi, loop_vinfo))
{
if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
LOOP_LOC (loop_vinfo)))
fprintf (vect_dump, "unsupported reduction/induction.");
return false;
}
}
VARRAY_TREE_INIT (worklist, 64, "work list");
for (i = 0; i < nbbs; i++)
{
bb = bbs[i];
for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
{
stmt = bsi_stmt (si);
if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
{
fprintf (vect_dump, "init: stmt relevant? ");
print_generic_expr (vect_dump, stmt, TDF_SLIM);
}
stmt_info = vinfo_for_stmt (stmt);
STMT_VINFO_RELEVANT_P (stmt_info) = 0;
if (vect_stmt_relevant_p (stmt, loop_vinfo))
vect_mark_relevant (&worklist, stmt);
}
}
while (VARRAY_ACTIVE_SIZE (worklist) > 0)
{
stmt = VARRAY_TOP_TREE (worklist);
VARRAY_POP (worklist);
if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
{
fprintf (vect_dump, "worklist: examine stmt: ");
print_generic_expr (vect_dump, stmt, TDF_SLIM);
}
if (TREE_CODE (stmt) == PHI_NODE)
{
for (j = 0; j < PHI_NUM_ARGS (stmt); j++)
{
tree arg = PHI_ARG_DEF (stmt, j);
tree def_stmt = NULL_TREE;
basic_block bb;
if (!vect_is_simple_use (arg, loop_vinfo, &def_stmt))
{
if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
LOOP_LOC (loop_vinfo)))
fprintf (vect_dump, "not vectorized: unsupported use in stmt.");
varray_clear (worklist);
return false;
}
if (!def_stmt)
continue;
if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
{
fprintf (vect_dump, "worklist: def_stmt: ");
print_generic_expr (vect_dump, def_stmt, TDF_SLIM);
}
bb = bb_for_stmt (def_stmt);
if (flow_bb_inside_loop_p (loop, bb))
vect_mark_relevant (&worklist, def_stmt);
}
}
ann = stmt_ann (stmt);
use_ops = USE_OPS (ann);
for (i = 0; i < NUM_USES (use_ops); i++)
{
tree use = USE_OP (use_ops, i);
if (exist_non_indexing_operands_for_use_p (use, stmt))
{
tree def_stmt = NULL_TREE;
basic_block bb;
if (!vect_is_simple_use (use, loop_vinfo, &def_stmt))
{
if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
LOOP_LOC (loop_vinfo)))
fprintf (vect_dump, "not vectorized: unsupported use in stmt.");
varray_clear (worklist);
return false;
}
if (!def_stmt)
continue;
if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
{
fprintf (vect_dump, "worklist: examine use %d: ", i);
print_generic_expr (vect_dump, use, TDF_SLIM);
}
bb = bb_for_stmt (def_stmt);
if (flow_bb_inside_loop_p (loop, bb))
vect_mark_relevant (&worklist, def_stmt);
}
}
}
varray_clear (worklist);
return true;
}
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;
tree phi;
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
{
tree access_fn = NULL;
tree evolution_part;
if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
{
fprintf (vect_dump, "Analyze phi: ");
print_generic_expr (vect_dump, phi, TDF_SLIM);
}
if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi))))
{
if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
fprintf (vect_dump, "virtual phi. skip.");
continue;
}
access_fn = instantiate_parameters
(loop, analyze_scalar_evolution (loop, PHI_RESULT (phi)));
if (!access_fn)
{
if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
fprintf (vect_dump, "No Access function.");
return false;
}
if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
{
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)
return false;
if (tree_is_chrec (evolution_part))
return false;
}
return true;
}
tree
vect_get_loop_niters (struct loop *loop, tree *number_of_iterations)
{
tree niters;
if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
fprintf (vect_dump, "=== get_loop_niters ===");
niters = number_of_iterations_in_loop (loop);
if (niters != NULL_TREE
&& niters != chrec_dont_know)
{
*number_of_iterations = niters;
if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
{
fprintf (vect_dump, "==> get_loop_niters:" );
print_generic_expr (vect_dump, *number_of_iterations, TDF_SLIM);
}
}
return get_loop_exit_condition (loop);
}
static loop_vec_info
vect_analyze_loop_form (struct loop *loop)
{
loop_vec_info loop_vinfo;
tree loop_cond;
tree number_of_iterations = NULL;
bool rescan = false;
LOC loop_loc;
loop_loc = find_loop_location (loop);
if (vect_print_dump_info (REPORT_DETAILS, loop_loc))
fprintf (vect_dump, "=== vect_analyze_loop_form ===");
if (loop->inner)
{
if (vect_print_dump_info (REPORT_OUTER_LOOPS, loop_loc))
fprintf (vect_dump, "not vectorized: nested loop.");
return NULL;
}
if (!loop->single_exit
|| loop->num_nodes != 2
|| EDGE_COUNT (loop->header->preds) != 2
|| loop->num_entries != 1)
{
if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS, loop_loc))
{
if (!loop->single_exit)
fprintf (vect_dump, "not vectorized: multiple exits.");
else if (loop->num_nodes != 2)
fprintf (vect_dump, "not vectorized: too many BBs in loop.");
else if (EDGE_COUNT (loop->header->preds) != 2)
fprintf (vect_dump, "not vectorized: too many incoming edges.");
else if (loop->num_entries != 1)
fprintf (vect_dump, "not vectorized: too many entries.");
}
return NULL;
}
if (!empty_block_p (loop->latch))
{
if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS, loop_loc))
fprintf (vect_dump, "not vectorized: unexpectd loop form.");
return NULL;
}
if (!loop->pre_header || EDGE_COUNT (loop->pre_header->succs) != 1)
{
edge e = loop_preheader_edge (loop);
loop_split_edge_with (e, NULL);
if (vect_print_dump_info (REPORT_DETAILS, loop_loc))
fprintf (vect_dump, "split preheader edge.");
rescan = true;
}
if (EDGE_COUNT (loop->single_exit->dest->preds) != 1)
{
edge e = loop->single_exit;
if (!(e->flags & EDGE_ABNORMAL))
{
loop_split_edge_with (e, NULL);
if (vect_print_dump_info (REPORT_DETAILS, loop_loc))
fprintf (vect_dump, "split exit edge.");
rescan = true;
}
else
{
if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS, loop_loc))
fprintf (vect_dump, "not vectorized: abnormal loop exit edge.");
return NULL;
}
}
if (rescan)
{
flow_loop_scan (loop, LOOP_ALL);
loop->single_exit = loop->exit_edges[0];
}
if (empty_block_p (loop->header))
{
if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS, loop_loc))
fprintf (vect_dump, "not vectorized: empty loop.");
return NULL;
}
loop_cond = vect_get_loop_niters (loop, &number_of_iterations);
if (!loop_cond)
{
if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS, loop_loc))
fprintf (vect_dump, "not vectorized: complicated exit condition.");
return NULL;
}
if (!number_of_iterations)
{
if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS, loop_loc))
fprintf (vect_dump,
"not vectorized: number of iterations cannot be computed.");
return NULL;
}
if (chrec_contains_undetermined (number_of_iterations))
{
if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS, loop_loc))
fprintf (vect_dump, "Infinite number of iterations.");
return false;
}
loop_vinfo = new_loop_vec_info (loop);
LOOP_VINFO_NITERS (loop_vinfo) = number_of_iterations;
if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo))
{
if (vect_print_dump_info (REPORT_DETAILS, loop_loc))
{
fprintf (vect_dump, "Symbolic number of iterations is ");
print_generic_expr (vect_dump, number_of_iterations, TDF_DETAILS);
}
}
else
if (LOOP_VINFO_INT_NITERS (loop_vinfo) == 0)
{
if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS, loop_loc))
fprintf (vect_dump, "not vectorized: number of iterations = 0.");
return NULL;
}
LOOP_VINFO_EXIT_COND (loop_vinfo) = loop_cond;
LOOP_VINFO_LOC (loop_vinfo) = loop_loc;
return loop_vinfo;
}
loop_vec_info
vect_analyze_loop (struct loop *loop)
{
bool ok;
loop_vec_info loop_vinfo;
if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
fprintf (vect_dump, "===== analyze_loop_nest =====");
loop_vinfo = vect_analyze_loop_form (loop);
if (!loop_vinfo)
{
if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
fprintf (vect_dump, "bad loop form.");
return NULL;
}
ok = vect_analyze_data_refs (loop_vinfo);
if (!ok)
{
if (vect_print_dump_info (REPORT_DETAILS, LOOP_LOC (loop_vinfo)))
fprintf (vect_dump, "bad data references.");
destroy_loop_vec_info (loop_vinfo);
return NULL;
}
ok = vect_mark_stmts_to_be_vectorized (loop_vinfo);
if (!ok)
{
if (vect_print_dump_info (REPORT_DETAILS, LOOP_LOC (loop_vinfo)))
fprintf (vect_dump, "unexpected pattern.");
destroy_loop_vec_info (loop_vinfo);
return NULL;
}
ok = vect_analyze_scalar_cycles (loop_vinfo);
if (!ok)
{
if (vect_print_dump_info (REPORT_DETAILS, LOOP_LOC (loop_vinfo)))
fprintf (vect_dump, "bad scalar cycle.");
destroy_loop_vec_info (loop_vinfo);
return NULL;
}
ok = vect_analyze_operations (loop_vinfo);
if (!ok)
{
if (vect_print_dump_info (REPORT_DETAILS, LOOP_LOC (loop_vinfo)))
fprintf (vect_dump, "bad data access.");
destroy_loop_vec_info (loop_vinfo);
return NULL;
}
ok = vect_analyze_data_ref_dependences (loop_vinfo);
if (!ok)
{
if (vect_print_dump_info (REPORT_DETAILS, LOOP_LOC (loop_vinfo)))
fprintf (vect_dump, "bad data dependence.");
destroy_loop_vec_info (loop_vinfo);
return NULL;
}
ok = vect_analyze_data_ref_accesses (loop_vinfo);
if (!ok)
{
if (vect_print_dump_info (REPORT_DETAILS, LOOP_LOC (loop_vinfo)))
fprintf (vect_dump, "bad data access.");
destroy_loop_vec_info (loop_vinfo);
return NULL;
}
ok = vect_analyze_data_refs_alignment (loop_vinfo);
if (!ok)
{
if (vect_print_dump_info (REPORT_DETAILS, LOOP_LOC (loop_vinfo)))
fprintf (vect_dump, "bad data alignment.");
destroy_loop_vec_info (loop_vinfo);
return NULL;
}
LOOP_VINFO_VECTORIZABLE_P (loop_vinfo) = 1;
return loop_vinfo;
}