/* Translation of isl AST to Gimple.
- Copyright (C) 2014-2017 Free Software Foundation, Inc.
+ Copyright (C) 2014-2019 Free Software Foundation, Inc.
Contributed by Roman Gareev <gareevroman@gmail.com>.
This file is part of GCC.
#include "tree.h"
#include "gimple.h"
#include "ssa.h"
-#include "params.h"
#include "fold-const.h"
#include "gimple-fold.h"
#include "gimple-iterator.h"
#include "cfganal.h"
#include "value-prof.h"
#include "tree-ssa.h"
+#include "tree-vectorizer.h"
#include "graphite.h"
struct ast_build_info
__isl_give isl_ast_node * scop_to_isl_ast (scop_p scop);
tree get_rename_from_scev (tree old_name, gimple_seq *stmts, loop_p loop,
- basic_block new_bb, basic_block old_bb,
vec<tree> iv_map);
- bool graphite_copy_stmts_from_block (basic_block bb, basic_block new_bb,
+ void graphite_copy_stmts_from_block (basic_block bb, basic_block new_bb,
vec<tree> iv_map);
edge copy_bb_and_scalar_dependences (basic_block bb, edge next_e,
vec<tree> iv_map);
void set_rename (tree old_name, tree expr);
- void set_rename_for_each_def (gimple *stmt);
void gsi_insert_earliest (gimple_seq seq);
bool codegen_error_p () const { return codegen_error; }
{
codegen_error = true;
gcc_assert (! flag_checking
- || PARAM_VALUE (PARAM_GRAPHITE_ALLOW_CODEGEN_ERRORS));
+ || param_graphite_allow_codegen_errors);
}
bool is_constant (tree op) const
"Could not map isl_id to tree expression");
isl_ast_expr_free (expr_id);
tree t = res->second;
- tree *val = region->parameter_rename_map->get(t);
-
- if (!val)
- val = &t;
- return fold_convert (type, *val);
+ if (useless_type_conversion_p (type, TREE_TYPE (t)))
+ return t;
+ return fold_convert (type, t);
}
/* Converts an isl_ast_expr_int expression E to a widest_int.
/* From our constraint generation we may get modulo operations that
we cannot represent explicitely but that are no-ops for TYPE.
Elide those. */
- if (expr_type == isl_ast_op_pdiv_r
+ if ((expr_type == isl_ast_op_pdiv_r
+ || expr_type == isl_ast_op_zdiv_r
+ || expr_type == isl_ast_op_add)
&& isl_ast_expr_get_type (arg_expr) == isl_ast_expr_int
&& (wi::exact_log2 (widest_int_from_isl_expr_int (arg_expr))
>= TYPE_PRECISION (type)))
if (codegen_error_p ())
return NULL_TREE;
- return fold_build3 (COND_EXPR, type, a, b, c);
+ return fold_build3 (COND_EXPR, type, a,
+ rewrite_to_non_trapping_overflow (b),
+ rewrite_to_non_trapping_overflow (c));
}
/* Converts a unary isl_ast_expr_op expression E to a GCC expression tree of
ub = integer_zero_node;
edge last_e = single_succ_edge (split_edge (next_e));
+
+ /* Compensate for the fact that we emit a do { } while loop from
+ a for ISL AST.
+ ??? We often miss constraints on niter because the SESE region
+ doesn't cover loop header copies. Ideally we'd add constraints
+ for all relevant dominating conditions. */
+ if (TREE_CODE (lb) == INTEGER_CST && TREE_CODE (ub) == INTEGER_CST
+ && tree_int_cst_compare (lb, ub) <= 0)
+ ;
+ else
+ {
+ tree one = build_one_cst (POINTER_TYPE_P (type) ? sizetype : type);
+ /* Adding +1 and using LT_EXPR helps with loop latches that have a
+ loop iteration count of "PARAMETER - 1". For PARAMETER == 0 this
+ becomes 2^k-1 due to integer overflow, and the condition lb <= ub
+ is true, even if we do not want this. However lb < ub + 1 is false,
+ as expected. */
+ tree ub_one = fold_build2 (POINTER_TYPE_P (type)
+ ? POINTER_PLUS_EXPR : PLUS_EXPR,
+ type, unshare_expr (ub), one);
+ create_empty_if_region_on_edge (next_e,
+ fold_build2 (LT_EXPR, boolean_type_node,
+ unshare_expr (lb), ub_one));
+ next_e = get_true_edge_from_guard_bb (next_e->dest);
+ }
+
translate_isl_ast_for_loop (context_loop, node, next_e,
type, lb, ub, ip);
return last_e;
isl_ast_expr_free (user_expr);
basic_block old_bb = GBB_BB (gbb);
- if (dump_file)
+ if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file,
"[codegen] copying from bb_%d on edge (bb_%d, bb_%d)\n",
old_bb->index, next_e->src->index, next_e->dest->index);
print_loops_bb (dump_file, GBB_BB (gbb), 0, 3);
-
}
next_e = copy_bb_and_scalar_dependences (old_bb, next_e, iv_map);
if (codegen_error_p ())
return NULL;
- if (dump_file)
+ if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "[codegen] (after copy) new basic block\n");
print_loops_bb (dump_file, next_e->src, 0, 3);
{
fprintf (dump_file, "[codegen] setting rename: old_name = ");
print_generic_expr (dump_file, old_name);
- fprintf (dump_file, ", new_name = ");
+ fprintf (dump_file, ", new decl = ");
print_generic_expr (dump_file, expr);
fprintf (dump_file, "\n");
}
-
- if (old_name == expr)
- return;
-
- vec <tree> *renames = region->rename_map->get (old_name);
-
- if (renames)
- renames->safe_push (expr);
- else
- {
- vec<tree> r;
- r.create (2);
- r.safe_push (expr);
- region->rename_map->put (old_name, r);
- }
-
- tree t;
- int i;
- /* For a parameter of a scop we don't want to rename it. */
- FOR_EACH_VEC_ELT (region->params, i, t)
- if (old_name == t)
- region->parameter_rename_map->put(old_name, expr);
+ bool res = region->rename_map->put (old_name, expr);
+ gcc_assert (! res);
}
/* Return an iterator to the instructions comes last in the execution order.
FOR_EACH_VEC_ELT (stmts, i, use_stmt)
{
gcc_assert (gimple_code (use_stmt) != GIMPLE_PHI);
- gimple_stmt_iterator gsi_def_stmt = gsi_start_bb_nondebug (begin_bb);
+ gimple_stmt_iterator gsi_def_stmt = gsi_start_nondebug_bb (begin_bb);
use_operand_p use_p;
ssa_op_iter op_iter;
else if (gimple_code (gsi_stmt (gsi_def_stmt)) == GIMPLE_PHI)
{
gimple_stmt_iterator bsi
- = gsi_start_bb_nondebug (gsi_bb (gsi_def_stmt));
+ = gsi_start_nondebug_bb (gsi_bb (gsi_def_stmt));
/* Insert right after the PHI statements. */
gsi_insert_before (&bsi, use_stmt, GSI_NEW_STMT);
}
if (dump_file)
{
- fprintf (dump_file, "[codegen] inserting statement: ");
+ fprintf (dump_file, "[codegen] inserting statement in BB %d: ",
+ gimple_bb (use_stmt)->index);
print_gimple_stmt (dump_file, use_stmt, 0, TDF_VOPS | TDF_MEMSYMS);
- print_loops_bb (dump_file, gimple_bb (use_stmt), 0, 3);
}
}
}
tree translate_isl_ast_to_gimple::
get_rename_from_scev (tree old_name, gimple_seq *stmts, loop_p loop,
- basic_block new_bb, basic_block,
vec<tree> iv_map)
{
- tree scev = scalar_evolution_in_region (region->region, loop, old_name);
+ tree scev = cached_scalar_evolution_in_region (region->region,
+ loop, old_name);
/* At this point we should know the exact scev for each
scalar SSA_NAME used in the scop: all the other scalar
return build_zero_cst (TREE_TYPE (old_name));
}
- if (TREE_CODE (new_expr) == SSA_NAME)
- {
- basic_block bb = gimple_bb (SSA_NAME_DEF_STMT (new_expr));
- if (bb && !dominated_by_p (CDI_DOMINATORS, new_bb, bb))
- {
- set_codegen_error ();
- return build_zero_cst (TREE_TYPE (old_name));
- }
- }
-
/* Replace the old_name with the new_expr. */
return force_gimple_operand (unshare_expr (new_expr), stmts,
true, NULL_TREE);
if (is_gimple_assign (stmt)
&& (lhs = gimple_assign_lhs (stmt))
&& TREE_CODE (lhs) == SSA_NAME
- && is_gimple_reg (lhs)
- && scev_analyzable_p (lhs, region->region))
- return false;
-
- /* Do not copy parameters that have been generated in the header of the
- scop. */
- if (is_gimple_assign (stmt)
- && (lhs = gimple_assign_lhs (stmt))
- && TREE_CODE (lhs) == SSA_NAME
- && region->parameter_rename_map->get(lhs))
+ && scev_analyzable_p (lhs, region->region)
+ /* But to code-generate liveouts - liveout PHI generation is
+ in generic sese.c code that cannot do code generation. */
+ && ! bitmap_bit_p (region->liveout, SSA_NAME_VERSION (lhs)))
return false;
return true;
}
-/* Create new names for all the definitions created by COPY and add replacement
- mappings for each new name. */
-
-void translate_isl_ast_to_gimple::
-set_rename_for_each_def (gimple *stmt)
-{
- def_operand_p def_p;
- ssa_op_iter op_iter;
- FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, op_iter, SSA_OP_ALL_DEFS)
- {
- tree old_name = DEF_FROM_PTR (def_p);
- create_new_def_for (old_name, stmt, def_p);
- }
-}
-
/* Duplicates the statements of basic block BB into basic block NEW_BB
and compute the new induction variables according to the IV_MAP. */
-bool translate_isl_ast_to_gimple::
+void translate_isl_ast_to_gimple::
graphite_copy_stmts_from_block (basic_block bb, basic_block new_bb,
vec<tree> iv_map)
{
/* Create a new copy of STMT and duplicate STMT's virtual
operands. */
gimple *copy = gimple_copy (stmt);
- gsi_insert_after (&gsi_tgt, copy, GSI_NEW_STMT);
/* Rather than not copying debug stmts we reset them.
??? Where we can rewrite uses without inserting new
{
if (gimple_debug_bind_p (copy))
gimple_debug_bind_reset_value (copy);
- else if (gimple_debug_source_bind_p (copy))
+ else if (gimple_debug_source_bind_p (copy)
+ || gimple_debug_nonbind_marker_p (copy))
;
else
gcc_unreachable ();
}
- if (dump_file)
- {
- fprintf (dump_file, "[codegen] inserting statement: ");
- print_gimple_stmt (dump_file, copy, 0);
- }
-
maybe_duplicate_eh_stmt (copy, stmt);
gimple_duplicate_stmt_histograms (cfun, copy, cfun, stmt);
/* Crete new names for each def in the copied stmt. */
- set_rename_for_each_def (copy);
+ def_operand_p def_p;
+ ssa_op_iter op_iter;
+ FOR_EACH_SSA_DEF_OPERAND (def_p, copy, op_iter, SSA_OP_ALL_DEFS)
+ {
+ tree old_name = DEF_FROM_PTR (def_p);
+ create_new_def_for (old_name, copy, def_p);
+ }
- if (codegen_error_p ())
- return false;
+ gsi_insert_after (&gsi_tgt, copy, GSI_NEW_STMT);
+ if (dump_file)
+ {
+ fprintf (dump_file, "[codegen] inserting statement: ");
+ print_gimple_stmt (dump_file, copy, 0);
+ }
- /* For each SSA_NAME in the parameter_rename_map rename their usage. */
+ /* For each SCEV analyzable SSA_NAME, rename their usage. */
ssa_op_iter iter;
use_operand_p use_p;
if (!is_gimple_debug (copy))
- FOR_EACH_SSA_USE_OPERAND (use_p, copy, iter, SSA_OP_USE)
- {
- tree old_name = USE_FROM_PTR (use_p);
-
- if (TREE_CODE (old_name) != SSA_NAME
- || SSA_NAME_IS_DEFAULT_DEF (old_name))
- continue;
-
- tree *new_expr = region->parameter_rename_map->get (old_name);
- tree new_name;
- if (!new_expr
- && scev_analyzable_p (old_name, region->region))
- {
- gimple_seq stmts = NULL;
- new_name = get_rename_from_scev (old_name, &stmts,
- bb->loop_father,
- new_bb, bb, iv_map);
- if (! codegen_error_p ())
- gsi_insert_earliest (stmts);
- new_expr = &new_name;
- }
-
- if (!new_expr)
- continue;
-
- replace_exp (use_p, *new_expr);
- }
+ {
+ bool changed = false;
+ FOR_EACH_SSA_USE_OPERAND (use_p, copy, iter, SSA_OP_USE)
+ {
+ tree old_name = USE_FROM_PTR (use_p);
+
+ if (TREE_CODE (old_name) != SSA_NAME
+ || SSA_NAME_IS_DEFAULT_DEF (old_name)
+ || ! scev_analyzable_p (old_name, region->region))
+ continue;
+
+ gimple_seq stmts = NULL;
+ tree new_name = get_rename_from_scev (old_name, &stmts,
+ bb->loop_father, iv_map);
+ if (! codegen_error_p ())
+ gsi_insert_earliest (stmts);
+ replace_exp (use_p, new_name);
+ changed = true;
+ }
+ if (changed)
+ fold_stmt_inplace (&gsi_tgt);
+ }
update_stmt (copy);
}
-
- return true;
}
continue;
tree new_phi_def;
- vec <tree> *renames = region->rename_map->get (res);
- if (! renames || renames->is_empty ())
+ tree *rename = region->rename_map->get (res);
+ if (! rename)
{
new_phi_def = create_tmp_reg (TREE_TYPE (res));
set_rename (res, new_phi_def);
}
else
- {
- gcc_assert (renames->length () == 1);
- new_phi_def = (*renames)[0];
- }
+ new_phi_def = *rename;
gassign *ass = gimple_build_assign (NULL_TREE, new_phi_def);
create_new_def_for (res, ass, NULL);
gsi_insert_after (&gsi_tgt, ass, GSI_NEW_STMT);
}
- vec <basic_block> *copied_bbs = region->copied_bb_map->get (bb);
- if (copied_bbs)
- copied_bbs->safe_push (new_bb);
- else
- {
- vec<basic_block> bbs;
- bbs.create (2);
- bbs.safe_push (new_bb);
- region->copied_bb_map->put (bb, bbs);
- }
-
- if (!graphite_copy_stmts_from_block (bb, new_bb, iv_map))
- {
- set_codegen_error ();
- return NULL;
- }
+ graphite_copy_stmts_from_block (bb, new_bb, iv_map);
/* Insert out-of SSA copies on the original BB outgoing edges. */
gsi_tgt = gsi_last_bb (new_bb);
continue;
tree new_phi_def;
- vec <tree> *renames = region->rename_map->get (res);
- if (! renames || renames->is_empty ())
+ tree *rename = region->rename_map->get (res);
+ if (! rename)
{
new_phi_def = create_tmp_reg (TREE_TYPE (res));
set_rename (res, new_phi_def);
}
else
- {
- gcc_assert (renames->length () == 1);
- new_phi_def = (*renames)[0];
- }
+ new_phi_def = *rename;
tree arg = PHI_ARG_DEF_FROM_EDGE (phi, e);
if (TREE_CODE (arg) == SSA_NAME
gimple_seq stmts = NULL;
tree new_name = get_rename_from_scev (arg, &stmts,
bb->loop_father,
- new_bb, bb, iv_map);
+ iv_map);
if (! codegen_error_p ())
gsi_insert_earliest (stmts);
arg = new_name;
{
sese_info_p region = scop->scop_info;
unsigned nb_parameters = isl_set_dim (scop->param_context, isl_dim_param);
- gcc_assert (nb_parameters == region->params.length ());
+ gcc_assert (nb_parameters == sese_nb_params (region));
unsigned i;
- for (i = 0; i < nb_parameters; i++)
+ tree param;
+ FOR_EACH_VEC_ELT (region->params, i, param)
{
isl_id *tmp_id = isl_set_get_dim_id (scop->param_context,
isl_dim_param, i);
- ip[tmp_id] = region->params[i];
+ ip[tmp_id] = param;
}
}
__isl_give isl_ast_node *translate_isl_ast_to_gimple::
scop_to_isl_ast (scop_p scop)
{
+ int old_err = isl_options_get_on_error (scop->isl_context);
+ int old_max_operations = isl_ctx_get_max_operations (scop->isl_context);
+ int max_operations = param_max_isl_operations;
+ if (max_operations)
+ isl_ctx_set_max_operations (scop->isl_context, max_operations);
+ isl_options_set_on_error (scop->isl_context, ISL_ON_ERROR_CONTINUE);
+
gcc_assert (scop->transformed_schedule);
/* Set the separate option to reduce control flow overhead. */
isl_ast_node *ast_isl = isl_ast_build_node_from_schedule
(context_isl, schedule);
isl_ast_build_free (context_isl);
- return ast_isl;
-}
-/* Copy def from sese REGION to the newly created TO_REGION. TR is defined by
- DEF_STMT. GSI points to entry basic block of the TO_REGION. */
-
-static void
-copy_def (tree tr, gimple *def_stmt, sese_info_p region, sese_info_p to_region,
- gimple_stmt_iterator *gsi)
-{
- if (!defined_in_sese_p (tr, region->region))
- return;
-
- ssa_op_iter iter;
- use_operand_p use_p;
- FOR_EACH_SSA_USE_OPERAND (use_p, def_stmt, iter, SSA_OP_USE)
+ isl_options_set_on_error (scop->isl_context, old_err);
+ isl_ctx_reset_operations (scop->isl_context);
+ isl_ctx_set_max_operations (scop->isl_context, old_max_operations);
+ if (isl_ctx_last_error (scop->isl_context) != isl_error_none)
{
- tree use_tr = USE_FROM_PTR (use_p);
-
- /* Do not copy parameters that have been generated in the header of the
- scop. */
- if (region->parameter_rename_map->get(use_tr))
- continue;
-
- gimple *def_of_use = SSA_NAME_DEF_STMT (use_tr);
- if (!def_of_use)
- continue;
-
- copy_def (use_tr, def_of_use, region, to_region, gsi);
- }
-
- gimple *copy = gimple_copy (def_stmt);
- gsi_insert_after (gsi, copy, GSI_NEW_STMT);
-
- /* Create new names for all the definitions created by COPY and
- add replacement mappings for each new name. */
- def_operand_p def_p;
- ssa_op_iter op_iter;
- FOR_EACH_SSA_DEF_OPERAND (def_p, copy, op_iter, SSA_OP_ALL_DEFS)
- {
- tree old_name = DEF_FROM_PTR (def_p);
- tree new_name = create_new_def_for (old_name, copy, def_p);
- region->parameter_rename_map->put(old_name, new_name);
+ if (dump_enabled_p ())
+ {
+ dump_user_location_t loc = find_loop_location
+ (scop->scop_info->region.entry->dest->loop_father);
+ if (isl_ctx_last_error (scop->isl_context) == isl_error_quota)
+ dump_printf_loc (MSG_MISSED_OPTIMIZATION, loc,
+ "loop nest not optimized, AST generation timed out "
+ "after %d operations [--param max-isl-operations]\n",
+ max_operations);
+ else
+ dump_printf_loc (MSG_MISSED_OPTIMIZATION, loc,
+ "loop nest not optimized, ISL AST generation "
+ "signalled an error\n");
+ }
+ isl_ast_node_free (ast_isl);
+ return NULL;
}
- update_stmt (copy);
+ return ast_isl;
}
+/* Generate out-of-SSA copies for the entry edge FALSE_ENTRY/TRUE_ENTRY
+ in REGION. */
+
static void
-copy_internal_parameters (sese_info_p region, sese_info_p to_region)
+generate_entry_out_of_ssa_copies (edge false_entry,
+ edge true_entry,
+ sese_info_p region)
{
- /* For all the parameters which definitino is in the if_region->false_region,
- insert code on true_region (if_region->true_region->entry). */
-
- int i;
- tree tr;
- gimple_stmt_iterator gsi = gsi_start_bb(to_region->region.entry->dest);
-
- FOR_EACH_VEC_ELT (region->params, i, tr)
+ gimple_stmt_iterator gsi_tgt = gsi_start_bb (true_entry->dest);
+ for (gphi_iterator psi = gsi_start_phis (false_entry->dest);
+ !gsi_end_p (psi); gsi_next (&psi))
{
- // If def is not in region.
- gimple *def_stmt = SSA_NAME_DEF_STMT (tr);
- if (def_stmt)
- copy_def (tr, def_stmt, region, to_region, &gsi);
+ gphi *phi = psi.phi ();
+ tree res = gimple_phi_result (phi);
+ if (virtual_operand_p (res))
+ continue;
+ /* When there's no out-of-SSA var registered do not bother
+ to create one. */
+ tree *rename = region->rename_map->get (res);
+ if (! rename)
+ continue;
+ tree new_phi_def = *rename;
+ gassign *ass = gimple_build_assign (new_phi_def,
+ PHI_ARG_DEF_FROM_EDGE (phi,
+ false_entry));
+ gsi_insert_after (&gsi_tgt, ass, GSI_NEW_STMT);
}
}
timevar_push (TV_GRAPHITE_CODE_GEN);
t.add_parameters_to_ivs_params (scop, ip);
root_node = t.scop_to_isl_ast (scop);
+ if (! root_node)
+ {
+ ivs_params_clear (ip);
+ timevar_pop (TV_GRAPHITE_CODE_GEN);
+ return false;
+ }
if (dump_file && (dump_flags & TDF_DETAILS))
{
region->if_region = if_region;
loop_p context_loop = region->region.entry->src->loop_father;
-
- /* Copy all the parameters which are defined in the region. */
- copy_internal_parameters(if_region->false_region, if_region->true_region);
-
edge e = single_succ_edge (if_region->true_region->region.entry->dest);
basic_block bb = split_edge (e);
t.translate_isl_ast (context_loop, root_node, e, ip);
if (! t.codegen_error_p ())
{
+ generate_entry_out_of_ssa_copies (if_region->false_region->region.entry,
+ if_region->true_region->region.entry,
+ region);
sese_insert_phis_for_liveouts (region,
if_region->region->region.exit->src,
if_region->false_region->region.exit,
if_region->true_region->region.exit);
if (dump_file)
fprintf (dump_file, "[codegen] isl AST to Gimple succeeded.\n");
-
- mark_virtual_operands_for_renaming (cfun);
- update_ssa (TODO_update_ssa);
- checking_verify_ssa (true, true);
- rewrite_into_loop_closed_ssa (NULL, 0);
- /* We analyzed evolutions of all SCOPs during SCOP detection
- which cached evolutions. Now we've introduced PHIs for
- liveouts which causes those cached solutions to be invalid
- for code-generation purposes given we'd insert references
- to SSA names not dominating their new use. */
- scev_reset ();
}
if (t.codegen_error_p ())
{
- if (dump_file)
- fprintf (dump_file, "codegen error: "
- "reverting back to the original code.\n");
- set_ifsese_condition (if_region, integer_zero_node);
+ if (dump_enabled_p ())
+ {
+ dump_user_location_t loc = find_loop_location
+ (scop->scop_info->region.entry->dest->loop_father);
+ dump_printf_loc (MSG_MISSED_OPTIMIZATION, loc,
+ "loop nest not optimized, code generation error\n");
+ }
- /* We registered new names, scrap that. */
- if (need_ssa_update_p (cfun))
- delete_update_ssa ();
/* Remove the unreachable region. */
remove_edge_and_dominated_blocks (if_region->true_region->region.entry);
basic_block ifb = if_region->false_region->region.entry->src;
delete_loop (loop);
}
- /* Verifies properties that GRAPHITE should maintain during translation. */
- checking_verify_loop_structure ();
- checking_verify_loop_closed_ssa (true);
+ /* We are delaying SSA update to after code-generating all SCOPs.
+ This is because we analyzed DRs and parameters on the unmodified
+ IL and thus rely on SSA update to pick up new dominating definitions
+ from for example SESE liveout PHIs. This is also for efficiency
+ as SSA update does work depending on the size of the function. */
free (if_region->true_region);
free (if_region->region);
projects / gcc.git / blobdiff