tree-ssa-loop-memset.c [plain text]
#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "ggc.h"
#include "tree.h"
#include "rtl.h"
#include "tm_p.h"
#include "hard-reg-set.h"
#include "basic-block.h"
#include "output.h"
#include "diagnostic.h"
#include "tree-flow.h"
#include "tree-dump.h"
#include "timevar.h"
#include "cfgloop.h"
#include "domwalk.h"
#include "params.h"
#include "tree-pass.h"
#include "flags.h"
#include "tree-data-ref.h"
#include "tree-scalar-evolution.h"
#include "tree-chrec.h"
#include "tree-vectorizer.h"
static bool memset_debug_stats (struct loop *loop);
static bool memset_debug_details (struct loop *loop);
static bool
memset_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 (memset_debug_details (NULL))
fprintf (dump_file, "\n<<memset_analyze_data_refs>>\n");
for (j = 0; j < nbbs; j++)
{
basic_block bb = bbs[j];
for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
{
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 array_base;
tree symbl;
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 (memset_debug_details (NULL))
{
fprintf (dump_file, "unexpected vdefs and vuses in stmt: ");
print_generic_expr (dump_file, stmt, TDF_SLIM);
}
return false;
}
if (TREE_CODE (stmt) != MODIFY_EXPR)
{
if (memset_debug_details (NULL))
{
fprintf (dump_file, "unexpected vops in stmt: ");
print_generic_expr (dump_file, stmt, TDF_SLIM);
}
return false;
}
if (vuses)
{
if (memset_debug_details (NULL))
{
fprintf (dump_file, "Memory access in the loop: ");
print_generic_expr (dump_file, stmt, TDF_SLIM);
}
return false;
}
else
{
memref = TREE_OPERAND (stmt, 0);
datarefs = &(LOOP_VINFO_DATAREF_WRITES (loop_vinfo));
}
if (TREE_CODE (memref) == INDIRECT_REF)
{
abort ();
if (! dr)
return false;
symbl = DR_BASE_NAME (dr);
}
else if (TREE_CODE (memref) == ARRAY_REF)
{
tree base;
array_base = TREE_OPERAND (memref, 0);
if (TREE_CODE (array_base) == ARRAY_REF)
{
if (memset_debug_stats (loop) || memset_debug_details (loop))
{
fprintf (dump_file,
"not vectorized: multi-dimensional array.");
print_generic_expr (dump_file, stmt, TDF_SLIM);
}
return false;
}
dr = analyze_array (stmt, memref, false);
base = DR_BASE_NAME (dr);
switch (TREE_CODE (base))
{
case VAR_DECL:
symbl = base;
break;
default:
if (memset_debug_stats (loop)
|| memset_debug_details (loop))
{
fprintf (dump_file,
"not transformed: unhandled struct/class field access ");
print_generic_expr (dump_file, stmt, TDF_SLIM);
}
return false;
}
}
else
{
if (memset_debug_stats (loop) || memset_debug_details (loop))
{
fprintf (dump_file, "not transformed: unhandled data ref: ");
print_generic_expr (dump_file, stmt, TDF_SLIM);
}
return false;
}
if (TREE_CODE (symbl) == VAR_DECL
|| (TREE_CODE (symbl) == COMPONENT_REF
&& TREE_CODE (TREE_OPERAND (symbl, 0)) == VAR_DECL))
STMT_VINFO_MEMTAG (stmt_info) = symbl;
else if (TREE_CODE (symbl) == SSA_NAME)
{
tree tag;
symbl = SSA_NAME_VAR (symbl);
tag = get_var_ann (symbl)->type_mem_tag;
if (!tag)
{
tree ptr = TREE_OPERAND (memref, 0);
if (TREE_CODE (ptr) == SSA_NAME)
tag = get_var_ann (SSA_NAME_VAR (ptr))->type_mem_tag;
}
if (!tag)
{
if (memset_debug_stats (loop) || memset_debug_details (loop))
fprintf (dump_file, "not vectorized: no memtag for ref.");
return false;
}
STMT_VINFO_MEMTAG (stmt_info) = tag;
}
else
{
if (memset_debug_stats (loop) || memset_debug_details (loop))
{
fprintf (dump_file, "not vectorized: unsupported data-ref: ");
print_generic_expr (dump_file, memref, TDF_SLIM);
}
return false;
}
VARRAY_PUSH_GENERIC_PTR (*datarefs, dr);
STMT_VINFO_DATA_REF (stmt_info) = dr;
}
}
return true;
}
static bool
memset_analyze_loop_with_symbolic_num_of_iters (tree niters,
struct loop *loop)
{
basic_block bb = loop->header;
tree phi;
if (memset_debug_details (NULL))
fprintf (dump_file,
"\n<<memset_analyze_loop_with_symbolic_num_of_iters>>\n");
if (chrec_contains_undetermined (niters))
{
if (memset_debug_details (NULL))
fprintf (dump_file, "Infinite number of iterations.");
return false;
}
if (!niters)
{
if (memset_debug_details (NULL))
fprintf (dump_file, "niters is NULL pointer.");
return false;
}
if (memset_debug_details (NULL))
{
fprintf (dump_file, "Symbolic number of iterations is ");
print_generic_expr (dump_file, niters, TDF_DETAILS);
}
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
{
tree access_fn = NULL;
tree evolution_part;
if (memset_debug_details (NULL))
{
fprintf (dump_file, "Analyze phi: ");
print_generic_expr (dump_file, phi, TDF_SLIM);
}
if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi))))
{
if (memset_debug_details (NULL))
fprintf (dump_file, "virtual phi. skip.");
continue;
}
access_fn = instantiate_parameters
(loop, analyze_scalar_evolution (loop, PHI_RESULT (phi)));
if (!access_fn)
{
if (memset_debug_details (NULL))
fprintf (dump_file, "No Access function.");
return false;
}
if (memset_debug_details (NULL))
{
fprintf (dump_file, "Access function of PHI: ");
print_generic_expr (dump_file, 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;
}
static bool
memset_debug_details (struct loop *loop)
{
basic_block bb;
block_stmt_iterator si;
tree node = NULL_TREE;
if (!dump_file || !(dump_flags & TDF_DETAILS))
return false;
if (!loop)
{
fprintf (dump_file, "\n");
return true;
}
if (!loop->header)
return false;
bb = loop->header;
for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
{
node = bsi_stmt (si);
if (node && EXPR_P (node) && EXPR_LOCUS (node))
break;
}
if (node && EXPR_P (node) && EXPR_LOCUS (node)
&& EXPR_FILENAME (node) && EXPR_LINENO (node))
{
fprintf (dump_file, "\nloop at %s:%d: ",
EXPR_FILENAME (node), EXPR_LINENO (node));
return true;
}
return false;
}
static bool
memset_debug_stats (struct loop *loop)
{
basic_block bb;
block_stmt_iterator si;
tree node = NULL_TREE;
if (!dump_file || !(dump_flags & TDF_STATS))
return false;
if (!loop)
{
fprintf (dump_file, "\n");
return true;
}
if (!loop->header)
return false;
bb = loop->header;
for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
{
node = bsi_stmt (si);
if (node && EXPR_P (node) && EXPR_LOCUS (node))
break;
}
if (node && EXPR_P (node) && EXPR_LOCUS (node)
&& EXPR_FILENAME (node) && EXPR_LINENO (node))
{
fprintf (dump_file, "\nloop at %s:%d: ",
EXPR_FILENAME (node), EXPR_LINENO (node));
return true;
}
return false;
}
static loop_vec_info
memset_analyze_loop_form (struct loop *loop)
{
loop_vec_info loop_vinfo;
tree loop_cond;
tree number_of_iterations = NULL_TREE;
if (memset_debug_details (loop))
fprintf (dump_file, "\n<<memset_analyze_loop_form>>\n");
if (loop->level > 1
|| loop->num_exits > 1 || loop->num_entries > 1 || loop->num_nodes != 2
|| !loop->pre_header || !loop->header || !loop->latch)
{
if (memset_debug_stats (loop) || memset_debug_details (loop))
{
fprintf (dump_file, "not vectorized: bad loop form.\n");
if (loop->level > 1)
fprintf (dump_file, "nested loop.\n");
else if (loop->num_exits > 1 || loop->num_entries > 1)
fprintf (dump_file, "multiple entries or exits.\n");
else if (loop->num_nodes != 2 || !loop->header || !loop->latch)
fprintf (dump_file, "too many BBs in loop.\n");
else if (!loop->pre_header)
fprintf (dump_file, "no pre-header BB for loop.\n");
}
return NULL;
}
if (!empty_block_p (loop->latch))
{
if (memset_debug_stats (loop) || memset_debug_details (loop))
fprintf (dump_file, "not vectorized: unexpectd loop form.");
return NULL;
}
if (empty_block_p (loop->header))
{
if (memset_debug_stats (loop) || memset_debug_details (loop))
fprintf (dump_file, "not transformed: empty loop.");
return NULL;
}
loop_cond = vect_get_loop_niters (loop, &number_of_iterations);
if (!loop_cond)
{
if (memset_debug_stats (loop) || memset_debug_details (loop))
fprintf (dump_file, "not vectorized: complicated exit condition.\n");
return NULL;
}
if (!number_of_iterations)
{
if (memset_debug_stats (loop) || memset_debug_details (loop))
fprintf (dump_file,
"not vectorized: number of iterations cannot be computed.");
return NULL;
}
loop_vinfo = new_loop_vec_info (loop);
LOOP_VINFO_NITERS (loop_vinfo) = number_of_iterations;
if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo))
{
if (memset_debug_details (NULL))
fprintf (dump_file, "loop bound unknown.");
if (!memset_analyze_loop_with_symbolic_num_of_iters (number_of_iterations,
loop))
{
if (memset_debug_stats (loop) || memset_debug_details (loop))
fprintf (dump_file, "not transformed: can't determine loop bound.\n");
return NULL;
}
else
{
if (loop->num_entries != 1 || !loop->pre_header)
{
if (memset_debug_stats (loop) || memset_debug_details (loop))
fprintf (dump_file,
"not transformed: more than one loop entry.");
return NULL;
}
}
}
else if (LOOP_VINFO_INT_NITERS (loop_vinfo) == 0)
{
if (memset_debug_stats (loop) || memset_debug_details (loop))
fprintf (dump_file, "not transformed: number of iterations = 0.\n");
return NULL;
}
LOOP_VINFO_EXIT_COND (loop_vinfo) = loop_cond;
return loop_vinfo;
}
static void
mark_all_v_defs (tree stmt)
{
tree sym;
ssa_op_iter iter;
get_stmt_operands (stmt);
FOR_EACH_SSA_TREE_OPERAND (sym, stmt, iter, SSA_OP_VIRTUAL_DEFS)
{
if (TREE_CODE (sym) == SSA_NAME)
sym = SSA_NAME_VAR (sym);
bitmap_set_bit (vars_to_rename, var_ann (sym)->uid);
}
}
void
tree_ssa_memset (struct loops *loops)
{
unsigned i;
for (i = 1; i < loops->num; i++)
{
struct loop *loop = loops->parray[i];
loop_vec_info vectorizer_info;
varray_type writes;
struct data_reference *drw;
tree access_chrec;
tree noi;
if (!loop)
continue;
flow_loop_scan (loop, LOOP_ALL);
vectorizer_info = memset_analyze_loop_form (loop);
if (!vectorizer_info)
continue;
if (!memset_analyze_data_refs (vectorizer_info))
{
if (memset_debug_details (loop))
fprintf (dump_file, "bad data references.");
destroy_loop_vec_info (vectorizer_info);
continue;
}
writes = LOOP_VINFO_DATAREF_WRITES (vectorizer_info);
if (VARRAY_ACTIVE_SIZE (writes) != 1)
{
if (memset_debug_details (loop))
fprintf (dump_file, "no or more than one store.");
destroy_loop_vec_info (vectorizer_info);
continue;
}
drw = VARRAY_GENERIC_PTR (writes, 0);
if (DR_NUM_DIMENSIONS (drw) != 1)
{
if (memset_debug_details (loop))
fprintf (dump_file, "cannot handle multiple dimension array.");
destroy_loop_vec_info (vectorizer_info);
continue;
}
if (TREE_CODE (TREE_OPERAND (DR_STMT (drw), 1)) != INTEGER_CST)
{
if (memset_debug_details (loop))
fprintf (dump_file, "non constant store value.");
destroy_loop_vec_info (vectorizer_info);
continue;
}
if (!integer_zerop (TREE_OPERAND (DR_STMT (drw), 1))
&& !integer_onep (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (drw)))))
{
if (memset_debug_details (loop))
fprintf (dump_file, "cannot handle other zero value for types of other than char (for now).");
destroy_loop_vec_info (vectorizer_info);
continue;
}
access_chrec = DR_ACCESS_FN (drw, 0);
noi = LOOP_VINFO_NITERS (vectorizer_info);
{
tree array = DR_BASE_NAME (drw);
tree value = TREE_OPERAND (DR_STMT (drw), 1);
tree function = implicit_built_in_decls[BUILT_IN_MEMSET];
tree args = NULL_TREE;
block_stmt_iterator bsi = bsi_last (loop->pre_header);
tree array_1 = make_rename_temp (ptr_type_node, NULL);
tree temp, stmt, var;
tree ni_name;
stmt = DR_STMT (drw);
{
block_stmt_iterator access_bsi;
mark_all_v_defs (stmt);
access_bsi = bsi_for_stmt (stmt);
bsi_remove (&access_bsi);
}
if (TREE_CODE (TREE_TYPE (array)) == ARRAY_TYPE)
{
tree type = TREE_TYPE (TREE_TYPE (array));
tree base = array;
while (TREE_CODE (base) == REALPART_EXPR
|| TREE_CODE (base) == IMAGPART_EXPR
|| handled_component_p (base))
base = TREE_OPERAND (base, 0);
if (DECL_P (base))
TREE_ADDRESSABLE (base) = 1;
array = build4 (ARRAY_REF, type, array, size_zero_node,
NULL_TREE, NULL_TREE);
array = build1 (ADDR_EXPR, build_pointer_type (TREE_TYPE (array)),
array);
}
{
tree start = CHREC_LEFT (access_chrec);
tree size_mult;
tree array_var;
start = fold_convert (TREE_TYPE (array), start);
size_mult = fold_convert (TREE_TYPE (array),
TYPE_SIZE_UNIT (TREE_TYPE (TREE_TYPE (array))));
array = fold (build2 (PLUS_EXPR,
TREE_TYPE (array),
array,
fold (build2 (MULT_EXPR,
TREE_TYPE (array),
start,
size_mult))));
array_var = create_tmp_var (TREE_TYPE (array), "tmp");
add_referenced_tmp_var (array_var);
array = force_gimple_operand (array, &stmt, false, array_var);
if (stmt)
bsi_insert_after (&bsi, stmt, BSI_CONTINUE_LINKING);
}
var = create_tmp_var (size_type_node, "tmp");
add_referenced_tmp_var (var);
noi = fold (build2 (MULT_EXPR, TREE_TYPE (noi), noi,
fold_convert (TREE_TYPE (noi),
TYPE_SIZE_UNIT (TREE_TYPE (TREE_TYPE (array))))));
stmt = NULL_TREE;
ni_name = force_gimple_operand (noi, &stmt, false, var);
if (stmt)
bsi_insert_after (&bsi, stmt, BSI_CONTINUE_LINKING);
temp = build2 (MODIFY_EXPR, void_type_node, array_1,
array);
bsi_insert_after (&bsi, temp, BSI_CONTINUE_LINKING);
args = tree_cons (NULL, ni_name, args);
args = tree_cons (NULL, fold_convert (integer_type_node, value), args);
args = tree_cons (NULL, array_1, args);
temp = build_function_call_expr (function, args);
bsi_insert_after (&bsi, temp, BSI_CONTINUE_LINKING);
}
destroy_loop_vec_info (vectorizer_info);
}
rewrite_into_ssa (false);
if (!bitmap_empty_p (vars_to_rename))
{
rewrite_into_loop_closed_ssa ();
}
bitmap_clear (vars_to_rename);
}