This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[PATCH][GRAPHITE] Rewrite PHI handling in code-gen
- From: Richard Biener <rguenther at suse dot de>
- To: gcc-patches at gcc dot gnu dot org
- Cc: sebpop at gmail dot com
- Date: Wed, 4 Oct 2017 16:31:07 +0200 (CEST)
- Subject: [PATCH][GRAPHITE] Rewrite PHI handling in code-gen
- Authentication-results: sourceware.org; auth=none
The following patch completely re-does PHI handling during
code-generation. PHI handling is currently responsible for 99% of
all code-generation issues. With the patch the number of code-generation
issues in SPEC 2k6 decreases from 180 to 5, similar adjustments happen
to the testsuite - only gfortran.dg/graphite has some expected code-gen
issues left.
The current idea of categorizing PHIs and doing code-gen based on
pattern matching with the original GIMPLE IL isn't feasible given
ISL can do transforms like peeling, optimizing away conditions and
creating arbitrary number of GBB copies. The current code fences
off a lot of cases by simply giving up.
To fix the current code one would need to basically replicate the
update-SSA machinery we already have (and pointlessly exercise
from the graphite code-gen at the moment).
Thus the patch rips out all manual handling of PHIs during code-generation
and leaves all cross-BB scalar updates to update-SSA.
This means "going out-of-SSA" again, but instead of applying out-of-SSA
on the original GIMPLE IL I'm just doing this on-the-fly during
scalar dependence generation and code generation.
bb3:
goto bb5;
bb4:
bb5:
_2 = PHI <_3(3), _4(4)>
becomes (for an identity rewrite) before update-SSA:
bb3':
D.1234 = _3;
bb4':
D.1234 = _4;
bb5':
_5 = D.1234;
with _5 being a new def for _2. update-SSA then re-writes the
_3 and _4 uses with available new defs we have registered during
code generation of the _3 and _4 def copies and rewrites D.1234
into SSA, inserting PHIs where necessary.
This scheme of course relies on ISL outputting a correct schedule
which of course relies on us setting proper dependence constraints.
I've fixed quite a few issues there, for example missing constraints
for the SESE liveout variables.
One awkward thing is that to not confuse ISL with PHI edge copies
placed in latch blocks, like
for (int c0 = 0; c0 < P_22; c0 += 1) {
S_6(0, c0);
if (P_22 >= c0 + 2)
S_7(0, c0);
}
and ISL then happilly peeling off the last iteration where the latch S_7
containing only the out-of-SSA copy is not needed. So I'm trying to
detect empty latches and instead insert the out-of-SSA copy in its
predecessor instead (I know it doesn't matter if we execute the stmt
in the last iteration).
The patch as-is ends up with quite some useless SSA copies which
is cleaned up by the copyprop pass inside the graphite pipeline
but can also be improved by teaching the into-SSA rewrite to
eliminate copies.
I do expect issues with the patch (I'm seeing CE 416.gamess, but not
sure why and 403.gcc miscompare), but it's already become somewhat too big
to handle.
Currently re-bootstrapping and testing after some cosmetic changes,
testsuites ran successfully, SPEC CPU 2006 built and run (with test data).
Statistics (with all graphite params set to unlimited) are
loop nest optimized: 119
loop nest not optimized, code generation error: 5
loop nest not optimized, optimized schedule is identical to original
schedule: 110
loop nest not optimized, optimization timed out: 31
loop nest not optimized, ISL signalled an error: 6
loop nest: 271
Ok for trunk?
Thanks,
Richard.
2017-10-04 Richard Biener <rguenther@suse.de>
* graphite-isl-ast-to-gimple.c: Include ssa.h and tree-ssa.h.
(translate_isl_ast_to_gimple::translate_pending_phi_nodes,
translate_isl_ast_to_gimple::is_valid_rename,
translate_isl_ast_to_gimple::get_rename,
translate_isl_ast_to_gimple::get_def_bb_for_const,
translate_isl_ast_to_gimple::get_new_name,
translate_isl_ast_to_gimple::collect_all_ssa_names,
translate_isl_ast_to_gimple::copy_loop_phi_args,
translate_isl_ast_to_gimple::collect_all_ssa_names,
translate_isl_ast_to_gimple::copy_loop_phi_args,
translate_isl_ast_to_gimple::copy_loop_phi_nodes,
translate_isl_ast_to_gimple::add_close_phis_to_merge_points,
translate_isl_ast_to_gimple::add_close_phis_to_outer_loops,
translate_isl_ast_to_gimple::copy_loop_close_phi_args,
translate_isl_ast_to_gimple::copy_loop_close_phi_nodes,
translate_isl_ast_to_gimple::copy_cond_phi_args,
translate_isl_ast_to_gimple::copy_cond_phi_nodes,
translate_isl_ast_to_gimple::edge_for_new_close_phis,
translate_isl_ast_to_gimple::add_phi_arg_for_new_expr,
translate_isl_ast_to_gimple::rename_uses,
translate_isl_ast_to_gimple::rename_all_uses): Remove.
(translate_isl_ast_to_gimple::get_rename_from_scev): Simplify.
(set_rename_for_each_def): Likewise.
(graphite_copy_stmts_from_block): Handle debug stmt resetting
here. Handle rewriting SCEV analyzable uses here.
(copy_bb_and_scalar_dependences): Generate code for PHI
copy-in/outs.
(graphite_regenerate_ast_isl): Adjust.
* graphite-scop-detection.c (trivially_empty_bb_p): Move to sese.[ch].
(add_write, add_read): New functions.
(build_cross_bb_scalars_def): Use it and simplify.
(build_cross_bb_scalars_use): Likewise.
(graphite_find_cross_bb_scalar_vars): Inline into...
(try_generate_gimple_bb): ...here. Add dependences for PHIs,
simulating out-of-SSA. Compute liveout and add dependencies.
(build_scops): Force an empty entry block.
* sese.h (sese_info_t::liveout, sese_info_t::debug_liveout): New
members.
(sese_build_liveouts): Declare.
(sese_trivially_empty_bb_p): Likewise.
* sese.c (sese_build_liveouts_bb): Properly handle PHIs,
compute liveout and debug_liveout.
(sese_bad_liveouts_use): Remove.
(sese_reset_debug_liveouts_bb): Likewise.
(sese_reset_debug_liveouts): Rewrite in terms of debug_liveout.
(sese_build_liveouts): Build liveout and debug_liveout and store
it in region.
(new_sese_info): Adjust.
(free_sese_info): Likewise.
(sese_insert_phis_for_liveouts): Reset debug stmts from here,
do not build liveout here.
(move_sese_in_condition): Adjust region entry.
(scev_analyzable_p): Match up with chrec_apply requirements.
(sese_trivially_empty_bb_p): New.
* tree-into-ssa.c (get_reaching_def): Properly support generating
default-defs for incremental rewrite of anonymous names.
* gcc.dg/graphite/id-15.c: No longer expect a code generation error.
* gcc.dg/graphite/id-16.c: Likewise.
* gcc.dg/graphite/pr46168.c: Likewise.
* gcc.dg/graphite/pr68756.c: Likewise.
* gcc.dg/graphite/pr69728.c: Likewise.
* gcc.dg/graphite/pr71575-2.c: Likewise.
* gcc.dg/graphite/pr77362.c: Likewise.
* gcc.dg/graphite/pr81373.c: Likewise.
* gcc.dg/graphite/run-id-pr67700-1.c: Likewise.
* gfortran.dg/graphite/interchange-1.f: Likewise.
* gfortran.dg/graphite/pr42334-1.f: Likewise.
* gfortran.dg/graphite/pr42393-1.f90: Likewise.
* gfortran.dg/graphite/pr42393.f90: Likewise.
* gfortran.dg/graphite/pr47019.f: Likewise.
* gfortran.dg/graphite/run-id-3.f90: Properly run all options.
* gfortran.dg/graphite/pr29832.f90: Likewise.
* gfortran.dg/graphite/pr29581.f90: Likewise. No longer expect
a code generation error.
Index: gcc/graphite-isl-ast-to-gimple.c
===================================================================
--- gcc/graphite-isl-ast-to-gimple.c (revision 253394)
+++ gcc/graphite-isl-ast-to-gimple.c (working copy)
@@ -31,6 +31,7 @@ along with GCC; see the file COPYING3.
#include "cfghooks.h"
#include "tree.h"
#include "gimple.h"
+#include "ssa.h"
#include "params.h"
#include "fold-const.h"
#include "gimple-fold.h"
@@ -54,6 +55,7 @@ along with GCC; see the file COPYING3.
#include "gimple-pretty-print.h"
#include "cfganal.h"
#include "value-prof.h"
+#include "tree-ssa.h"
#include "graphite.h"
/* We always try to use signed 128 bit types, but fall back to smaller types
@@ -190,55 +192,21 @@ class translate_isl_ast_to_gimple
void build_iv_mapping (vec<tree> iv_map, gimple_poly_bb_p gbb,
__isl_keep isl_ast_expr *user_expr, ivs_params &ip,
sese_l ®ion);
- void translate_pending_phi_nodes (void);
void add_parameters_to_ivs_params (scop_p scop, ivs_params &ip);
__isl_give isl_ast_build *generate_isl_context (scop_p scop);
__isl_give isl_ast_node * scop_to_isl_ast (scop_p scop);
- bool is_valid_rename (tree rename, basic_block def_bb, basic_block use_bb,
- phi_node_kind, tree old_name, basic_block old_bb) const;
- tree get_rename (basic_block new_bb, tree old_name,
- basic_block old_bb, phi_node_kind) const;
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);
- basic_block get_def_bb_for_const (basic_block bb, basic_block old_bb) const;
- tree get_new_name (basic_block new_bb, tree op,
- basic_block old_bb, phi_node_kind) const;
- void collect_all_ssa_names (tree new_expr, vec<tree> *vec_ssa);
- bool copy_loop_phi_args (gphi *old_phi, init_back_edge_pair_t &ibp_old_bb,
- gphi *new_phi, init_back_edge_pair_t &ibp_new_bb,
- bool postpone);
- bool copy_loop_phi_nodes (basic_block bb, basic_block new_bb);
- bool add_close_phis_to_merge_points (gphi *old_phi, gphi *new_phi,
- tree default_value);
- tree add_close_phis_to_outer_loops (tree last_merge_name, edge merge_e,
- gimple *old_close_phi);
- bool copy_loop_close_phi_args (basic_block old_bb, basic_block new_bb,
- vec<tree> iv_map, bool postpone);
- bool copy_loop_close_phi_nodes (basic_block old_bb, basic_block new_bb,
- vec<tree> iv_map);
- bool copy_cond_phi_args (gphi *phi, gphi *new_phi, vec<tree> iv_map,
- bool postpone);
- bool copy_cond_phi_nodes (basic_block bb, basic_block new_bb,
- vec<tree> iv_map);
bool 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);
- edge edge_for_new_close_phis (basic_block bb);
- bool add_phi_arg_for_new_expr (tree old_phi_args[2], tree new_phi_args[2],
- edge old_bb_dominating_edge,
- edge old_bb_non_dominating_edge,
- gphi *phi, gphi *new_phi,
- basic_block new_bb);
- bool rename_uses (gimple *copy, gimple_stmt_iterator *gsi_tgt,
- basic_block old_bb, loop_p loop, 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);
- tree rename_all_uses (tree new_expr, basic_block new_bb, basic_block old_bb);
bool codegen_error_p () const { return codegen_error; }
void set_codegen_error ()
@@ -955,206 +923,6 @@ translate_isl_ast (loop_p context_loop,
}
}
-/* Return true when BB contains loop close phi nodes. A loop close phi node is
- at the exit of loop which takes one argument that is the last value of the
- variable being used out of the loop. */
-
-static bool
-bb_contains_loop_close_phi_nodes (basic_block bb)
-{
- return single_pred_p (bb)
- && bb->loop_father != single_pred_edge (bb)->src->loop_father;
-}
-
-/* Return true when BB contains loop phi nodes. A loop phi node is the loop
- header containing phi nodes which has one init-edge and one back-edge. */
-
-static bool
-bb_contains_loop_phi_nodes (basic_block bb)
-{
- if (EDGE_COUNT (bb->preds) != 2)
- return false;
-
- unsigned depth = loop_depth (bb->loop_father);
-
- edge preds[2] = { (*bb->preds)[0], (*bb->preds)[1] };
-
- if (depth > loop_depth (preds[0]->src->loop_father)
- || depth > loop_depth (preds[1]->src->loop_father))
- return true;
-
- /* When one of the edges correspond to the same loop father and other
- doesn't. */
- if (bb->loop_father != preds[0]->src->loop_father
- && bb->loop_father == preds[1]->src->loop_father)
- return true;
-
- if (bb->loop_father != preds[1]->src->loop_father
- && bb->loop_father == preds[0]->src->loop_father)
- return true;
-
- return false;
-}
-
-/* Check if USE is defined in a basic block from where the definition of USE can
- propagate from all the paths. FIXME: Verify checks for virtual operands. */
-
-static bool
-is_loop_closed_ssa_use (basic_block bb, tree use)
-{
- if (TREE_CODE (use) != SSA_NAME || virtual_operand_p (use))
- return true;
-
- /* For close-phi nodes def always comes from a loop which has a back-edge. */
- if (bb_contains_loop_close_phi_nodes (bb))
- return true;
-
- gimple *def = SSA_NAME_DEF_STMT (use);
- basic_block def_bb = gimple_bb (def);
- return (!def_bb
- || flow_bb_inside_loop_p (def_bb->loop_father, bb));
-}
-
-/* Return the number of phi nodes in BB. */
-
-static int
-number_of_phi_nodes (basic_block bb)
-{
- int num_phis = 0;
- for (gphi_iterator psi = gsi_start_phis (bb); !gsi_end_p (psi);
- gsi_next (&psi))
- num_phis++;
- return num_phis;
-}
-
-/* Returns true if BB uses name in one of its PHIs. */
-
-static bool
-phi_uses_name (basic_block bb, tree name)
-{
- for (gphi_iterator psi = gsi_start_phis (bb); !gsi_end_p (psi);
- gsi_next (&psi))
- {
- gphi *phi = psi.phi ();
- for (unsigned i = 0; i < gimple_phi_num_args (phi); i++)
- {
- tree use_arg = gimple_phi_arg_def (phi, i);
- if (use_arg == name)
- return true;
- }
- }
- return false;
-}
-
-/* Return true if RENAME (defined in BB) is a valid use in NEW_BB. The
- definition should flow into use, and the use should respect the loop-closed
- SSA form. */
-
-bool translate_isl_ast_to_gimple::
-is_valid_rename (tree rename, basic_block def_bb, basic_block use_bb,
- phi_node_kind phi_kind, tree old_name, basic_block old_bb) const
-{
- if (SSA_NAME_IS_DEFAULT_DEF (rename))
- return true;
-
- /* The def of the rename must either dominate the uses or come from a
- back-edge. Also the def must respect the loop closed ssa form. */
- if (!is_loop_closed_ssa_use (use_bb, rename))
- {
- if (dump_file)
- {
- fprintf (dump_file, "[codegen] rename not in loop closed ssa: ");
- print_generic_expr (dump_file, rename);
- fprintf (dump_file, "\n");
- }
- return false;
- }
-
- if (dominated_by_p (CDI_DOMINATORS, use_bb, def_bb))
- return true;
-
- if (bb_contains_loop_phi_nodes (use_bb) && phi_kind == loop_phi)
- {
- /* The loop-header dominates the loop-body. */
- if (!dominated_by_p (CDI_DOMINATORS, def_bb, use_bb))
- return false;
-
- /* RENAME would be used in loop-phi. */
- gcc_assert (number_of_phi_nodes (use_bb));
-
- /* For definitions coming from back edges, we should check that
- old_name is used in a loop PHI node.
- FIXME: Verify if this is true. */
- if (phi_uses_name (old_bb, old_name))
- return true;
- }
- return false;
-}
-
-/* Returns the expression associated to OLD_NAME (which is used in OLD_BB), in
- NEW_BB from RENAME_MAP. PHI_KIND determines the kind of phi node. */
-
-tree translate_isl_ast_to_gimple::
-get_rename (basic_block new_bb, tree old_name, basic_block old_bb,
- phi_node_kind phi_kind) const
-{
- gcc_assert (TREE_CODE (old_name) == SSA_NAME);
- vec <tree> *renames = region->rename_map->get (old_name);
-
- if (!renames || renames->is_empty ())
- return NULL_TREE;
-
- if (1 == renames->length ())
- {
- tree rename = (*renames)[0];
- if (TREE_CODE (rename) == SSA_NAME)
- {
- basic_block bb = gimple_bb (SSA_NAME_DEF_STMT (rename));
- if (is_valid_rename (rename, bb, new_bb, phi_kind, old_name, old_bb)
- && (phi_kind == close_phi
- || ! bb
- || flow_bb_inside_loop_p (bb->loop_father, new_bb)))
- return rename;
- return NULL_TREE;
- }
-
- if (is_constant (rename))
- return rename;
-
- return NULL_TREE;
- }
-
- /* More than one renames corresponding to the old_name. Find the rename for
- which the definition flows into usage at new_bb. */
- int i;
- tree t1 = NULL_TREE, t2;
- basic_block t1_bb = NULL;
- FOR_EACH_VEC_ELT (*renames, i, t2)
- {
- basic_block t2_bb = gimple_bb (SSA_NAME_DEF_STMT (t2));
-
- /* Defined in the same basic block as used. */
- if (t2_bb == new_bb)
- return t2;
-
- /* NEW_BB and T2_BB are in two unrelated if-clauses. */
- if (!dominated_by_p (CDI_DOMINATORS, new_bb, t2_bb))
- continue;
-
- if (!flow_bb_inside_loop_p (t2_bb->loop_father, new_bb))
- continue;
-
- /* Compute the nearest dominator. */
- if (!t1 || dominated_by_p (CDI_DOMINATORS, t2_bb, t1_bb))
- {
- t1_bb = t2_bb;
- t1 = t2;
- }
- }
-
- return t1;
-}
-
/* Register in RENAME_MAP the rename tuple (OLD_NAME, EXPR).
When OLD_NAME and EXPR are the same we assert. */
@@ -1193,1243 +961,172 @@ set_rename (tree old_name, tree expr)
region->parameter_rename_map->put(old_name, expr);
}
-/* Return an iterator to the instructions comes last in the execution order.
- Either GSI1 and GSI2 should belong to the same basic block or one of their
- respective basic blocks should dominate the other. */
-
-gimple_stmt_iterator
-later_of_the_two (gimple_stmt_iterator gsi1, gimple_stmt_iterator gsi2)
-{
- basic_block bb1 = gsi_bb (gsi1);
- basic_block bb2 = gsi_bb (gsi2);
-
- /* Find the iterator which is the latest. */
- if (bb1 == bb2)
- {
- gimple *stmt1 = gsi_stmt (gsi1);
- gimple *stmt2 = gsi_stmt (gsi2);
-
- if (stmt1 != NULL && stmt2 != NULL)
- {
- bool is_phi1 = gimple_code (stmt1) == GIMPLE_PHI;
- bool is_phi2 = gimple_code (stmt2) == GIMPLE_PHI;
-
- if (is_phi1 != is_phi2)
- return is_phi1 ? gsi2 : gsi1;
- }
-
- /* For empty basic blocks gsis point to the end of the sequence. Since
- there is no operator== defined for gimple_stmt_iterator and for gsis
- not pointing to a valid statement gsi_next would assert. */
- gimple_stmt_iterator gsi = gsi1;
- do {
- if (gsi_stmt (gsi) == gsi_stmt (gsi2))
- return gsi2;
- gsi_next (&gsi);
- } while (!gsi_end_p (gsi));
-
- return gsi1;
- }
-
- /* Find the basic block closest to the basic block which defines stmt. */
- if (dominated_by_p (CDI_DOMINATORS, bb1, bb2))
- return gsi1;
-
- gcc_assert (dominated_by_p (CDI_DOMINATORS, bb2, bb1));
- return gsi2;
-}
-
-/* Insert each statement from SEQ at its earliest insertion p. */
-
-void translate_isl_ast_to_gimple::
-gsi_insert_earliest (gimple_seq seq)
-{
- update_modified_stmts (seq);
- sese_l &codegen_region = region->if_region->true_region->region;
- basic_block begin_bb = get_entry_bb (codegen_region);
-
- /* Inserting the gimple statements in a vector because gimple_seq behave
- in strage ways when inserting the stmts from it into different basic
- blocks one at a time. */
- auto_vec<gimple *, 3> stmts;
- for (gimple_stmt_iterator gsi = gsi_start (seq); !gsi_end_p (gsi);
- gsi_next (&gsi))
- stmts.safe_push (gsi_stmt (gsi));
-
- int i;
- gimple *use_stmt;
- 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);
-
- use_operand_p use_p;
- ssa_op_iter op_iter;
- FOR_EACH_SSA_USE_OPERAND (use_p, use_stmt, op_iter, SSA_OP_USE)
- {
- /* Iterator to the current def of use_p. For function parameters or
- anything where def is not found, insert at the beginning of the
- generated region. */
- gimple_stmt_iterator gsi_stmt = gsi_def_stmt;
-
- tree op = USE_FROM_PTR (use_p);
- gimple *stmt = SSA_NAME_DEF_STMT (op);
- if (stmt && (gimple_code (stmt) != GIMPLE_NOP))
- gsi_stmt = gsi_for_stmt (stmt);
-
- /* For region parameters, insert at the beginning of the generated
- region. */
- if (!bb_in_sese_p (gsi_bb (gsi_stmt), codegen_region))
- gsi_stmt = gsi_def_stmt;
-
- gsi_def_stmt = later_of_the_two (gsi_stmt, gsi_def_stmt);
- }
-
- if (!gsi_stmt (gsi_def_stmt))
- {
- gimple_stmt_iterator gsi = gsi_after_labels (gsi_bb (gsi_def_stmt));
- gsi_insert_before (&gsi, use_stmt, GSI_NEW_STMT);
- }
- else if (gimple_code (gsi_stmt (gsi_def_stmt)) == GIMPLE_PHI)
- {
- gimple_stmt_iterator bsi
- = gsi_start_bb_nondebug (gsi_bb (gsi_def_stmt));
- /* Insert right after the PHI statements. */
- gsi_insert_before (&bsi, use_stmt, GSI_NEW_STMT);
- }
- else
- gsi_insert_after (&gsi_def_stmt, use_stmt, GSI_NEW_STMT);
-
- if (dump_file)
- {
- fprintf (dump_file, "[codegen] inserting statement: ");
- print_gimple_stmt (dump_file, use_stmt, 0, TDF_VOPS | TDF_MEMSYMS);
- print_loops_bb (dump_file, gimple_bb (use_stmt), 0, 3);
- }
- }
-}
-
-/* Collect all the operands of NEW_EXPR by recursively visiting each
- operand. */
-
-void translate_isl_ast_to_gimple::
-collect_all_ssa_names (tree new_expr, vec<tree> *vec_ssa)
-{
- if (new_expr == NULL_TREE)
- return;
-
- /* Rename all uses in new_expr. */
- if (TREE_CODE (new_expr) == SSA_NAME)
- {
- vec_ssa->safe_push (new_expr);
- return;
- }
-
- /* Iterate over SSA_NAMES in NEW_EXPR. */
- for (int i = 0; i < (TREE_CODE_LENGTH (TREE_CODE (new_expr))); i++)
- {
- tree op = TREE_OPERAND (new_expr, i);
- collect_all_ssa_names (op, vec_ssa);
- }
-}
-
-/* This is abridged version of the function copied from:
- tree.c:substitute_in_expr (tree exp, tree f, tree r). */
-
-static tree
-substitute_ssa_name (tree exp, tree f, tree r)
-{
- enum tree_code code = TREE_CODE (exp);
- tree op0, op1, op2, op3;
- tree new_tree;
-
- /* We handle TREE_LIST and COMPONENT_REF separately. */
- if (code == TREE_LIST)
- {
- op0 = substitute_ssa_name (TREE_CHAIN (exp), f, r);
- op1 = substitute_ssa_name (TREE_VALUE (exp), f, r);
- if (op0 == TREE_CHAIN (exp) && op1 == TREE_VALUE (exp))
- return exp;
-
- return tree_cons (TREE_PURPOSE (exp), op1, op0);
- }
- else if (code == COMPONENT_REF)
- {
- tree inner;
-
- /* If this expression is getting a value from a PLACEHOLDER_EXPR
- and it is the right field, replace it with R. */
- for (inner = TREE_OPERAND (exp, 0);
- REFERENCE_CLASS_P (inner);
- inner = TREE_OPERAND (inner, 0))
- ;
-
- /* The field. */
- op1 = TREE_OPERAND (exp, 1);
-
- if (TREE_CODE (inner) == PLACEHOLDER_EXPR && op1 == f)
- return r;
-
- /* If this expression hasn't been completed let, leave it alone. */
- if (TREE_CODE (inner) == PLACEHOLDER_EXPR && !TREE_TYPE (inner))
- return exp;
-
- op0 = substitute_ssa_name (TREE_OPERAND (exp, 0), f, r);
- if (op0 == TREE_OPERAND (exp, 0))
- return exp;
-
- new_tree
- = fold_build3 (COMPONENT_REF, TREE_TYPE (exp), op0, op1, NULL_TREE);
- }
- else
- switch (TREE_CODE_CLASS (code))
- {
- case tcc_constant:
- return exp;
-
- case tcc_declaration:
- if (exp == f)
- return r;
- else
- return exp;
-
- case tcc_expression:
- if (exp == f)
- return r;
-
- /* Fall through. */
-
- case tcc_exceptional:
- case tcc_unary:
- case tcc_binary:
- case tcc_comparison:
- case tcc_reference:
- switch (TREE_CODE_LENGTH (code))
- {
- case 0:
- if (exp == f)
- return r;
- return exp;
-
- case 1:
- op0 = substitute_ssa_name (TREE_OPERAND (exp, 0), f, r);
- if (op0 == TREE_OPERAND (exp, 0))
- return exp;
-
- new_tree = fold_build1 (code, TREE_TYPE (exp), op0);
- break;
-
- case 2:
- op0 = substitute_ssa_name (TREE_OPERAND (exp, 0), f, r);
- op1 = substitute_ssa_name (TREE_OPERAND (exp, 1), f, r);
-
- if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1))
- return exp;
-
- new_tree = fold_build2 (code, TREE_TYPE (exp), op0, op1);
- break;
-
- case 3:
- op0 = substitute_ssa_name (TREE_OPERAND (exp, 0), f, r);
- op1 = substitute_ssa_name (TREE_OPERAND (exp, 1), f, r);
- op2 = substitute_ssa_name (TREE_OPERAND (exp, 2), f, r);
-
- if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1)
- && op2 == TREE_OPERAND (exp, 2))
- return exp;
-
- new_tree = fold_build3 (code, TREE_TYPE (exp), op0, op1, op2);
- break;
-
- case 4:
- op0 = substitute_ssa_name (TREE_OPERAND (exp, 0), f, r);
- op1 = substitute_ssa_name (TREE_OPERAND (exp, 1), f, r);
- op2 = substitute_ssa_name (TREE_OPERAND (exp, 2), f, r);
- op3 = substitute_ssa_name (TREE_OPERAND (exp, 3), f, r);
-
- if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1)
- && op2 == TREE_OPERAND (exp, 2)
- && op3 == TREE_OPERAND (exp, 3))
- return exp;
-
- new_tree
- = fold (build4 (code, TREE_TYPE (exp), op0, op1, op2, op3));
- break;
-
- default:
- gcc_unreachable ();
- }
- break;
-
- case tcc_vl_exp:
- default:
- gcc_unreachable ();
- }
-
- TREE_READONLY (new_tree) |= TREE_READONLY (exp);
-
- if (code == INDIRECT_REF || code == ARRAY_REF || code == ARRAY_RANGE_REF)
- TREE_THIS_NOTRAP (new_tree) |= TREE_THIS_NOTRAP (exp);
-
- return new_tree;
-}
-
-/* Rename all the operands of NEW_EXPR by recursively visiting each operand. */
-
-tree translate_isl_ast_to_gimple::
-rename_all_uses (tree new_expr, basic_block new_bb, basic_block old_bb)
-{
- auto_vec<tree, 2> ssa_names;
- collect_all_ssa_names (new_expr, &ssa_names);
- tree t;
- int i;
- FOR_EACH_VEC_ELT (ssa_names, i, t)
- if (tree r = get_rename (new_bb, t, old_bb, unknown_phi))
- new_expr = substitute_ssa_name (new_expr, t, r);
-
- return new_expr;
-}
-
-/* For ops which are scev_analyzeable, we can regenerate a new name from its
- scalar evolution around LOOP. */
-
-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 old_bb,
- vec<tree> iv_map)
-{
- tree scev = 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
- SSA_NAMEs should have been translated out of SSA using
- arrays with one element. */
- tree new_expr;
- if (chrec_contains_undetermined (scev))
- {
- set_codegen_error ();
- return build_zero_cst (TREE_TYPE (old_name));
- }
-
- new_expr = chrec_apply_map (scev, iv_map);
-
- /* The apply should produce an expression tree containing
- the uses of the new induction variables. We should be
- able to use new_expr instead of the old_name in the newly
- generated loop nest. */
- if (chrec_contains_undetermined (new_expr)
- || tree_contains_chrecs (new_expr, NULL))
- {
- set_codegen_error ();
- 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));
- }
- }
-
- new_expr = rename_all_uses (new_expr, new_bb, old_bb);
-
- /* We check all the operands and all of them should dominate the use at
- new_expr. */
- auto_vec <tree, 2> new_ssa_names;
- collect_all_ssa_names (new_expr, &new_ssa_names);
- int i;
- tree new_ssa_name;
- FOR_EACH_VEC_ELT (new_ssa_names, i, new_ssa_name)
- {
- if (TREE_CODE (new_ssa_name) == SSA_NAME)
- {
- basic_block bb = gimple_bb (SSA_NAME_DEF_STMT (new_ssa_name));
- 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);
-}
-
-/* Renames the scalar uses of the statement COPY, using the
- substitution map RENAME_MAP, inserting the gimplification code at
- GSI_TGT, for the translation REGION, with the original copied
- statement in LOOP, and using the induction variable renaming map
- IV_MAP. Returns true when something has been renamed. */
-
-bool translate_isl_ast_to_gimple::
-rename_uses (gimple *copy, gimple_stmt_iterator *gsi_tgt, basic_block old_bb,
- loop_p loop, vec<tree> iv_map)
-{
- bool changed = false;
-
- if (is_gimple_debug (copy))
- {
- if (gimple_debug_bind_p (copy))
- gimple_debug_bind_reset_value (copy);
- else if (gimple_debug_source_bind_p (copy))
- return false;
- else
- gcc_unreachable ();
-
- return false;
- }
-
- if (dump_file)
- {
- fprintf (dump_file, "[codegen] renaming uses of stmt: ");
- print_gimple_stmt (dump_file, copy, 0);
- }
-
- use_operand_p use_p;
- ssa_op_iter op_iter;
- FOR_EACH_SSA_USE_OPERAND (use_p, copy, op_iter, SSA_OP_USE)
- {
- tree old_name = USE_FROM_PTR (use_p);
-
- if (dump_file)
- {
- fprintf (dump_file, "[codegen] renaming old_name = ");
- print_generic_expr (dump_file, old_name);
- fprintf (dump_file, "\n");
- }
-
- if (TREE_CODE (old_name) != SSA_NAME
- || SSA_NAME_IS_DEFAULT_DEF (old_name))
- continue;
-
- changed = true;
- tree new_expr = get_rename (gsi_tgt->bb, old_name,
- old_bb, unknown_phi);
-
- if (new_expr)
- {
- tree type_old_name = TREE_TYPE (old_name);
- tree type_new_expr = TREE_TYPE (new_expr);
-
- if (dump_file)
- {
- fprintf (dump_file, "[codegen] from rename_map: new_name = ");
- print_generic_expr (dump_file, new_expr);
- fprintf (dump_file, "\n");
- }
-
- if (type_old_name != type_new_expr
- || TREE_CODE (new_expr) != SSA_NAME)
- {
- tree var = create_tmp_var (type_old_name, "var");
-
- if (!useless_type_conversion_p (type_old_name, type_new_expr))
- new_expr = fold_convert (type_old_name, new_expr);
-
- gimple_seq stmts;
- new_expr = force_gimple_operand (new_expr, &stmts, true, var);
- gsi_insert_earliest (stmts);
- }
-
- replace_exp (use_p, new_expr);
- continue;
- }
-
- gimple_seq stmts;
- new_expr = get_rename_from_scev (old_name, &stmts, loop, gimple_bb (copy),
- old_bb, iv_map);
- if (!new_expr || codegen_error_p ())
- return false;
-
- if (dump_file)
- {
- fprintf (dump_file, "[codegen] not in rename map, scev: ");
- print_generic_expr (dump_file, new_expr);
- fprintf (dump_file, "\n");
- }
-
- gsi_insert_earliest (stmts);
- replace_exp (use_p, new_expr);
-
- if (TREE_CODE (new_expr) == INTEGER_CST
- && is_gimple_assign (copy))
- {
- tree rhs = gimple_assign_rhs1 (copy);
-
- if (TREE_CODE (rhs) == ADDR_EXPR)
- recompute_tree_invariant_for_addr_expr (rhs);
- }
-
- set_rename (old_name, new_expr);
- }
-
- return changed;
-}
-
-/* Returns a basic block that could correspond to where a constant was defined
- in the original code. In the original code OLD_BB had the definition, we
- need to find which basic block out of the copies of old_bb, in the new
- region, should a definition correspond to if it has to reach BB. */
-
-basic_block translate_isl_ast_to_gimple::
-get_def_bb_for_const (basic_block bb, basic_block old_bb) const
-{
- vec <basic_block> *bbs = region->copied_bb_map->get (old_bb);
-
- if (!bbs || bbs->is_empty ())
- return NULL;
-
- if (1 == bbs->length ())
- return (*bbs)[0];
-
- int i;
- basic_block b1 = NULL, b2;
- FOR_EACH_VEC_ELT (*bbs, i, b2)
- {
- if (b2 == bb)
- return bb;
-
- /* BB and B2 are in two unrelated if-clauses. */
- if (!dominated_by_p (CDI_DOMINATORS, bb, b2))
- continue;
-
- /* Compute the nearest dominator. */
- if (!b1 || dominated_by_p (CDI_DOMINATORS, b2, b1))
- b1 = b2;
- }
-
- return b1;
-}
-
-/* Get the new name of OP (from OLD_BB) to be used in NEW_BB. PHI_KIND
- determines the kind of phi node. */
-
-tree translate_isl_ast_to_gimple::
-get_new_name (basic_block new_bb, tree op,
- basic_block old_bb, phi_node_kind phi_kind) const
-{
- /* For constants the names are the same. */
- if (TREE_CODE (op) != SSA_NAME)
- return op;
-
- return get_rename (new_bb, op, old_bb, phi_kind);
-}
-
-/* Return a debug location for OP. */
-
-static location_t
-get_loc (tree op)
-{
- location_t loc = UNKNOWN_LOCATION;
-
- if (TREE_CODE (op) == SSA_NAME)
- loc = gimple_location (SSA_NAME_DEF_STMT (op));
- return loc;
-}
-
-/* Returns the incoming edges of basic_block BB in the pair. The first edge is
- the init edge (from outside the loop) and the second one is the back edge
- from the same loop. */
-
-std::pair<edge, edge>
-get_edges (basic_block bb)
-{
- std::pair<edge, edge> edges;
- edge e;
- edge_iterator ei;
- FOR_EACH_EDGE (e, ei, bb->preds)
- if (bb->loop_father != e->src->loop_father)
- edges.first = e;
- else
- edges.second = e;
- return edges;
-}
-
-/* Copy the PHI arguments from OLD_PHI to the NEW_PHI. The arguments to NEW_PHI
- must be found unless they can be POSTPONEd for later. */
-
-bool translate_isl_ast_to_gimple::
-copy_loop_phi_args (gphi *old_phi, init_back_edge_pair_t &ibp_old_bb,
- gphi *new_phi, init_back_edge_pair_t &ibp_new_bb,
- bool postpone)
-{
- gcc_assert (gimple_phi_num_args (old_phi) == gimple_phi_num_args (new_phi));
-
- basic_block new_bb = gimple_bb (new_phi);
- for (unsigned i = 0; i < gimple_phi_num_args (old_phi); i++)
- {
- edge e;
- if (gimple_phi_arg_edge (old_phi, i) == ibp_old_bb.first)
- e = ibp_new_bb.first;
- else
- e = ibp_new_bb.second;
-
- tree old_name = gimple_phi_arg_def (old_phi, i);
- tree new_name = get_new_name (new_bb, old_name,
- gimple_bb (old_phi), loop_phi);
- if (new_name)
- {
- add_phi_arg (new_phi, new_name, e, get_loc (old_name));
- continue;
- }
-
- gimple *old_def_stmt = SSA_NAME_DEF_STMT (old_name);
- if (!old_def_stmt || gimple_code (old_def_stmt) == GIMPLE_NOP)
- /* If the phi arg was a function arg, or wasn't defined, just use the
- old name. */
- add_phi_arg (new_phi, old_name, e, get_loc (old_name));
- else if (postpone)
- {
- /* Postpone code gen for later for those back-edges we don't have the
- names yet. */
- region->incomplete_phis.safe_push (std::make_pair (old_phi, new_phi));
- if (dump_file)
- fprintf (dump_file, "[codegen] postpone loop phi nodes.\n");
- }
- else
- /* Either we should add the arg to phi or, we should postpone. */
- return false;
- }
- return true;
-}
-
-/* Copy loop phi nodes from BB to NEW_BB. */
-
-bool translate_isl_ast_to_gimple::
-copy_loop_phi_nodes (basic_block bb, basic_block new_bb)
-{
- if (dump_file)
- fprintf (dump_file, "[codegen] copying loop phi nodes in bb_%d.\n",
- new_bb->index);
-
- /* Loop phi nodes should have only two arguments. */
- gcc_assert (2 == EDGE_COUNT (bb->preds));
-
- /* First edge is the init edge and second is the back edge. */
- init_back_edge_pair_t ibp_old_bb = get_edges (bb);
-
- /* First edge is the init edge and second is the back edge. */
- init_back_edge_pair_t ibp_new_bb = get_edges (new_bb);
-
- for (gphi_iterator psi = gsi_start_phis (bb); !gsi_end_p (psi);
- gsi_next (&psi))
- {
- gphi *phi = psi.phi ();
- tree res = gimple_phi_result (phi);
- if (virtual_operand_p (res))
- continue;
- if (is_gimple_reg (res) && scev_analyzable_p (res, region->region))
- continue;
-
- gphi *new_phi = create_phi_node (NULL_TREE, new_bb);
- tree new_res = create_new_def_for (res, new_phi,
- gimple_phi_result_ptr (new_phi));
- set_rename (res, new_res);
- if (!copy_loop_phi_args (phi, ibp_old_bb, new_phi, ibp_new_bb, true))
- set_codegen_error ();
- update_stmt (new_phi);
-
- if (dump_file)
- {
- fprintf (dump_file, "[codegen] creating loop-phi node: ");
- print_gimple_stmt (dump_file, new_phi, 0);
- }
- }
-
- return true;
-}
-
-/* Return the init value of PHI, the value coming from outside the loop. */
-
-static tree
-get_loop_init_value (gphi *phi)
-{
-
- loop_p loop = gimple_bb (phi)->loop_father;
-
- edge e;
- edge_iterator ei;
- FOR_EACH_EDGE (e, ei, gimple_bb (phi)->preds)
- if (e->src->loop_father != loop)
- return gimple_phi_arg_def (phi, e->dest_idx);
-
- return NULL_TREE;
-}
-
-/* Find the init value (the value which comes from outside the loop), of one of
- the operands of DEF which is defined by a loop phi. */
-
-static tree
-find_init_value (gimple *def)
-{
- if (gimple_code (def) == GIMPLE_PHI)
- return get_loop_init_value (as_a <gphi*> (def));
-
- if (gimple_vuse (def))
- return NULL_TREE;
-
- ssa_op_iter iter;
- use_operand_p use_p;
- FOR_EACH_SSA_USE_OPERAND (use_p, def, iter, SSA_OP_USE)
- {
- tree use = USE_FROM_PTR (use_p);
- if (TREE_CODE (use) == SSA_NAME)
- {
- if (tree res = find_init_value (SSA_NAME_DEF_STMT (use)))
- return res;
- }
- }
-
- return NULL_TREE;
-}
-
-/* Return the init value, the value coming from outside the loop. */
-
-static tree
-find_init_value_close_phi (gphi *phi)
-{
- gcc_assert (gimple_phi_num_args (phi) == 1);
- tree use_arg = gimple_phi_arg_def (phi, 0);
- gimple *def = SSA_NAME_DEF_STMT (use_arg);
- return find_init_value (def);
-}
-
-
-tree translate_isl_ast_to_gimple::
-add_close_phis_to_outer_loops (tree last_merge_name, edge last_e,
- gimple *old_close_phi)
-{
- sese_l &codegen_region = region->if_region->true_region->region;
- gimple *stmt = SSA_NAME_DEF_STMT (last_merge_name);
- basic_block bb = gimple_bb (stmt);
- if (!bb_in_sese_p (bb, codegen_region))
- return last_merge_name;
-
- loop_p loop = bb->loop_father;
- if (!loop_in_sese_p (loop, codegen_region))
- return last_merge_name;
-
- edge e = single_exit (loop);
-
- if (dominated_by_p (CDI_DOMINATORS, e->dest, last_e->src))
- return last_merge_name;
-
- tree old_name = gimple_phi_arg_def (old_close_phi, 0);
- tree old_close_phi_name = gimple_phi_result (old_close_phi);
-
- bb = e->dest;
- if (!bb_contains_loop_close_phi_nodes (bb) || !single_succ_p (bb))
- bb = split_edge (e);
-
- gphi *close_phi = create_phi_node (NULL_TREE, bb);
- tree res = create_new_def_for (last_merge_name, close_phi,
- gimple_phi_result_ptr (close_phi));
- set_rename (old_close_phi_name, res);
- add_phi_arg (close_phi, last_merge_name, e, get_loc (old_name));
- last_merge_name = res;
-
- return add_close_phis_to_outer_loops (last_merge_name, last_e, old_close_phi);
-}
-
-/* Add phi nodes to all merge points of all the diamonds enclosing the loop of
- the close phi node PHI. */
-
-bool translate_isl_ast_to_gimple::
-add_close_phis_to_merge_points (gphi *old_close_phi, gphi *new_close_phi,
- tree default_value)
-{
- sese_l &codegen_region = region->if_region->true_region->region;
- basic_block default_value_bb = get_entry_bb (codegen_region);
- if (SSA_NAME == TREE_CODE (default_value))
- {
- gimple *stmt = SSA_NAME_DEF_STMT (default_value);
- if (!stmt || gimple_code (stmt) == GIMPLE_NOP)
- return false;
- default_value_bb = gimple_bb (stmt);
- }
-
- basic_block new_close_phi_bb = gimple_bb (new_close_phi);
-
- tree old_close_phi_name = gimple_phi_result (old_close_phi);
- tree new_close_phi_name = gimple_phi_result (new_close_phi);
- tree last_merge_name = new_close_phi_name;
- tree old_name = gimple_phi_arg_def (old_close_phi, 0);
-
- int i;
- edge merge_e;
- FOR_EACH_VEC_ELT_REVERSE (merge_points, i, merge_e)
- {
- basic_block new_merge_bb = merge_e->src;
- if (!dominated_by_p (CDI_DOMINATORS, new_merge_bb, default_value_bb))
- continue;
-
- last_merge_name = add_close_phis_to_outer_loops (last_merge_name, merge_e,
- old_close_phi);
-
- gphi *merge_phi = create_phi_node (NULL_TREE, new_merge_bb);
- tree merge_res = create_new_def_for (old_close_phi_name, merge_phi,
- gimple_phi_result_ptr (merge_phi));
- set_rename (old_close_phi_name, merge_res);
-
- edge from_loop = NULL, from_default_value = NULL;
- edge e;
- edge_iterator ei;
- FOR_EACH_EDGE (e, ei, new_merge_bb->preds)
- if (dominated_by_p (CDI_DOMINATORS, e->src, new_close_phi_bb))
- from_loop = e;
- else
- from_default_value = e;
-
- /* Because CDI_POST_DOMINATORS are not updated, we only rely on
- CDI_DOMINATORS, which may not handle all cases where new_close_phi_bb
- is contained in another condition. */
- if (!from_default_value || !from_loop)
- return false;
-
- add_phi_arg (merge_phi, last_merge_name, from_loop, get_loc (old_name));
- add_phi_arg (merge_phi, default_value, from_default_value, get_loc (old_name));
-
- if (dump_file)
- {
- fprintf (dump_file, "[codegen] Adding guard-phi: ");
- print_gimple_stmt (dump_file, merge_phi, 0);
- }
-
- update_stmt (merge_phi);
- last_merge_name = merge_res;
- }
-
- return true;
-}
-
-/* Copy all the loop-close phi args from BB to NEW_BB. */
-
-bool translate_isl_ast_to_gimple::
-copy_loop_close_phi_args (basic_block old_bb, basic_block new_bb,
- vec<tree> iv_map, bool postpone)
-{
- for (gphi_iterator psi = gsi_start_phis (old_bb); !gsi_end_p (psi);
- gsi_next (&psi))
- {
- gphi *old_close_phi = psi.phi ();
- tree res = gimple_phi_result (old_close_phi);
- if (virtual_operand_p (res))
- continue;
-
- gphi *new_close_phi = create_phi_node (NULL_TREE, new_bb);
- tree new_res = create_new_def_for (res, new_close_phi,
- gimple_phi_result_ptr (new_close_phi));
- set_rename (res, new_res);
-
- tree old_name = gimple_phi_arg_def (old_close_phi, 0);
- tree new_name;
- if (is_gimple_reg (res) && scev_analyzable_p (res, region->region))
- {
- gimple_seq stmts;
- new_name = get_rename_from_scev (old_name, &stmts,
- old_bb->loop_father,
- new_bb, old_bb, iv_map);
- if (! codegen_error_p ())
- gsi_insert_earliest (stmts);
- }
- else
- new_name = get_new_name (new_bb, old_name, old_bb, close_phi);
-
- /* Predecessor basic blocks of a loop close phi should have been code
- generated before. FIXME: This is fixable by merging PHIs from inner
- loops as well. See: gfortran.dg/graphite/interchange-3.f90. */
- if (!new_name || codegen_error_p ())
- return false;
-
- add_phi_arg (new_close_phi, new_name, single_pred_edge (new_bb),
- get_loc (old_name));
- if (dump_file)
- {
- fprintf (dump_file, "[codegen] Adding loop close phi: ");
- print_gimple_stmt (dump_file, new_close_phi, 0);
- }
-
- update_stmt (new_close_phi);
-
- /* When there is no loop guard around this codegenerated loop, there is no
- need to collect the close-phi arg. */
- if (merge_points.is_empty ())
- continue;
-
- /* Add a PHI in the succ_new_bb for each close phi of the loop. */
- tree default_value = find_init_value_close_phi (new_close_phi);
-
- /* A close phi must come from a loop-phi having a default value. */
- if (!default_value)
- {
- if (!postpone)
- return false;
-
- region->incomplete_phis.safe_push (std::make_pair (old_close_phi,
- new_close_phi));
- if (dump_file)
- {
- fprintf (dump_file, "[codegen] postpone close phi nodes: ");
- print_gimple_stmt (dump_file, new_close_phi, 0);
- }
- continue;
- }
-
- if (!add_close_phis_to_merge_points (old_close_phi, new_close_phi,
- default_value))
- return false;
- }
-
- return true;
-}
-
-/* Copy loop close phi nodes from BB to NEW_BB. */
-
-bool translate_isl_ast_to_gimple::
-copy_loop_close_phi_nodes (basic_block old_bb, basic_block new_bb,
- vec<tree> iv_map)
-{
- if (dump_file)
- fprintf (dump_file, "[codegen] copying loop close phi nodes in bb_%d.\n",
- new_bb->index);
- /* Loop close phi nodes should have only one argument. */
- gcc_assert (1 == EDGE_COUNT (old_bb->preds));
-
- return copy_loop_close_phi_args (old_bb, new_bb, iv_map, true);
-}
-
-
-/* Add NEW_NAME as the ARGNUM-th arg of NEW_PHI which is in NEW_BB.
- DOMINATING_PRED is the predecessor basic block of OLD_BB which dominates the
- other pred of OLD_BB as well. If no such basic block exists then it is NULL.
- NON_DOMINATING_PRED is a pred which does not dominate OLD_BB, it cannot be
- NULL.
-
- Case1: OLD_BB->preds {BB1, BB2} and BB1 does not dominate BB2 and vice versa.
- In this case DOMINATING_PRED = NULL.
-
- Case2: OLD_BB->preds {BB1, BB2} and BB1 dominates BB2.
-
- Returns true on successful copy of the args, false otherwise. */
-
-bool translate_isl_ast_to_gimple::
-add_phi_arg_for_new_expr (tree old_phi_args[2], tree new_phi_args[2],
- edge old_bb_dominating_edge,
- edge old_bb_non_dominating_edge,
- gphi *phi, gphi *new_phi,
- basic_block new_bb)
-{
- basic_block def_pred[2] = { NULL, NULL };
- int not_found_bb_index = -1;
- for (int i = 0; i < 2; i++)
- {
- /* If the corresponding def_bb could not be found the entry will be
- NULL. */
- if (TREE_CODE (old_phi_args[i]) == INTEGER_CST)
- def_pred[i] = get_def_bb_for_const (new_bb,
- gimple_phi_arg_edge (phi, i)->src);
- else if (new_phi_args[i] && (TREE_CODE (new_phi_args[i]) == SSA_NAME))
- def_pred[i] = gimple_bb (SSA_NAME_DEF_STMT (new_phi_args[i]));
-
- if (!def_pred[i])
- {
- /* When non are available bail out. */
- if (not_found_bb_index != -1)
- return false;
- not_found_bb_index = i;
- }
- }
-
- /* Here we are pattern matching on the structure of CFG w.r.t. old one. */
- if (old_bb_dominating_edge)
- {
- if (not_found_bb_index != -1)
- return false;
-
- basic_block new_pred1 = (*new_bb->preds)[0]->src;
- basic_block new_pred2 = (*new_bb->preds)[1]->src;
- vec <basic_block> *bbs
- = region->copied_bb_map->get (old_bb_non_dominating_edge->src);
-
- /* Could not find a mapping. */
- if (!bbs)
- return false;
-
- basic_block new_pred = NULL;
- basic_block b;
- int i;
- FOR_EACH_VEC_ELT (*bbs, i, b)
- {
- if (dominated_by_p (CDI_DOMINATORS, new_pred1, b))
- {
- /* FIXME: If we have already found new_pred then we have to
- disambiguate, bail out for now. */
- if (new_pred)
- return false;
- new_pred = new_pred1;
- }
- if (dominated_by_p (CDI_DOMINATORS, new_pred2, b))
- {
- /* FIXME: If we have already found new_pred then we have to either
- it dominates both or we have to disambiguate, bail out. */
- if (new_pred)
- return false;
- new_pred = new_pred2;
- }
- }
-
- if (!new_pred)
- return false;
-
- edge new_non_dominating_edge = find_edge (new_pred, new_bb);
- gcc_assert (new_non_dominating_edge);
- /* FIXME: Validate each args just like in loop-phis. */
- /* By the process of elimination we first insert insert phi-edge for
- non-dominating pred which is computed above and then we insert the
- remaining one. */
- int inserted_edge = 0;
- for (; inserted_edge < 2; inserted_edge++)
- {
- edge new_bb_pred_edge = gimple_phi_arg_edge (new_phi, inserted_edge);
- if (new_non_dominating_edge == new_bb_pred_edge)
- {
- add_phi_arg (new_phi, new_phi_args[inserted_edge],
- new_non_dominating_edge,
- get_loc (old_phi_args[inserted_edge]));
- break;
- }
- }
- if (inserted_edge == 2)
- return false;
-
- int edge_dominating = inserted_edge == 0 ? 1 : 0;
-
- edge new_dominating_edge = NULL;
- for (inserted_edge = 0; inserted_edge < 2; inserted_edge++)
- {
- edge e = gimple_phi_arg_edge (new_phi, inserted_edge);
- if (e != new_non_dominating_edge)
- {
- new_dominating_edge = e;
- add_phi_arg (new_phi, new_phi_args[edge_dominating],
- new_dominating_edge,
- get_loc (old_phi_args[inserted_edge]));
- break;
- }
- }
- gcc_assert (new_dominating_edge);
- }
- else
- {
- /* Classic diamond structure: both edges are non-dominating. We need to
- find one unique edge then the other can be found be elimination. If
- any definition (def_pred) dominates both the preds of new_bb then we
- bail out. Entries of def_pred maybe NULL, in that case we must
- uniquely find pred with help of only one entry. */
- edge new_e[2] = { NULL, NULL };
- for (int i = 0; i < 2; i++)
- {
- edge e;
- edge_iterator ei;
- FOR_EACH_EDGE (e, ei, new_bb->preds)
- if (def_pred[i]
- && dominated_by_p (CDI_DOMINATORS, e->src, def_pred[i]))
- {
- if (new_e[i])
- /* We do not know how to handle the case when def_pred
- dominates more than a predecessor. */
- return false;
- new_e[i] = e;
- }
- }
+/* Return an iterator to the instructions comes last in the execution order.
+ Either GSI1 and GSI2 should belong to the same basic block or one of their
+ respective basic blocks should dominate the other. */
+
+gimple_stmt_iterator
+later_of_the_two (gimple_stmt_iterator gsi1, gimple_stmt_iterator gsi2)
+{
+ basic_block bb1 = gsi_bb (gsi1);
+ basic_block bb2 = gsi_bb (gsi2);
- gcc_assert (new_e[0] || new_e[1]);
+ /* Find the iterator which is the latest. */
+ if (bb1 == bb2)
+ {
+ gimple *stmt1 = gsi_stmt (gsi1);
+ gimple *stmt2 = gsi_stmt (gsi2);
- /* Find the other edge by process of elimination. */
- if (not_found_bb_index != -1)
+ if (stmt1 != NULL && stmt2 != NULL)
{
- gcc_assert (!new_e[not_found_bb_index]);
- int found_bb_index = not_found_bb_index == 1 ? 0 : 1;
- edge e;
- edge_iterator ei;
- FOR_EACH_EDGE (e, ei, new_bb->preds)
- {
- if (new_e[found_bb_index] == e)
- continue;
- new_e[not_found_bb_index] = e;
- }
+ bool is_phi1 = gimple_code (stmt1) == GIMPLE_PHI;
+ bool is_phi2 = gimple_code (stmt2) == GIMPLE_PHI;
+
+ if (is_phi1 != is_phi2)
+ return is_phi1 ? gsi2 : gsi1;
}
- /* Add edges to phi args. */
- for (int i = 0; i < 2; i++)
- add_phi_arg (new_phi, new_phi_args[i], new_e[i],
- get_loc (old_phi_args[i]));
+ /* For empty basic blocks gsis point to the end of the sequence. Since
+ there is no operator== defined for gimple_stmt_iterator and for gsis
+ not pointing to a valid statement gsi_next would assert. */
+ gimple_stmt_iterator gsi = gsi1;
+ do {
+ if (gsi_stmt (gsi) == gsi_stmt (gsi2))
+ return gsi2;
+ gsi_next (&gsi);
+ } while (!gsi_end_p (gsi));
+
+ return gsi1;
}
- return true;
+ /* Find the basic block closest to the basic block which defines stmt. */
+ if (dominated_by_p (CDI_DOMINATORS, bb1, bb2))
+ return gsi1;
+
+ gcc_assert (dominated_by_p (CDI_DOMINATORS, bb2, bb1));
+ return gsi2;
}
-/* Copy the arguments of cond-phi node PHI, to NEW_PHI in the codegenerated
- region. If postpone is true and it isn't possible to copy any arg of PHI,
- the PHI is added to the REGION->INCOMPLETE_PHIS to be codegenerated later.
- Returns false if the copying was unsuccessful. */
+/* Insert each statement from SEQ at its earliest insertion p. */
-bool translate_isl_ast_to_gimple::
-copy_cond_phi_args (gphi *phi, gphi *new_phi, vec<tree> iv_map, bool postpone)
+void translate_isl_ast_to_gimple::
+gsi_insert_earliest (gimple_seq seq)
{
- if (dump_file)
- fprintf (dump_file, "[codegen] copying cond phi args.\n");
- gcc_assert (2 == gimple_phi_num_args (phi));
+ update_modified_stmts (seq);
+ sese_l &codegen_region = region->if_region->true_region->region;
+ basic_block begin_bb = get_entry_bb (codegen_region);
- basic_block new_bb = gimple_bb (new_phi);
- loop_p loop = gimple_bb (phi)->loop_father;
+ /* Inserting the gimple statements in a vector because gimple_seq behave
+ in strage ways when inserting the stmts from it into different basic
+ blocks one at a time. */
+ auto_vec<gimple *, 3> stmts;
+ for (gimple_stmt_iterator gsi = gsi_start (seq); !gsi_end_p (gsi);
+ gsi_next (&gsi))
+ stmts.safe_push (gsi_stmt (gsi));
- basic_block old_bb = gimple_bb (phi);
- edge old_bb_non_dominating_edge = NULL, old_bb_dominating_edge = NULL;
+ int i;
+ gimple *use_stmt;
+ 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);
- edge e;
- edge_iterator ei;
- FOR_EACH_EDGE (e, ei, old_bb->preds)
- if (!dominated_by_p (CDI_DOMINATORS, old_bb, e->src))
- old_bb_non_dominating_edge = e;
- else
- old_bb_dominating_edge = e;
-
- gcc_assert (!dominated_by_p (CDI_DOMINATORS, old_bb,
- old_bb_non_dominating_edge->src));
-
- tree new_phi_args[2];
- tree old_phi_args[2];
-
- for (unsigned i = 0; i < gimple_phi_num_args (phi); i++)
- {
- tree old_name = gimple_phi_arg_def (phi, i);
- tree new_name = get_new_name (new_bb, old_name, old_bb, cond_phi);
- old_phi_args[i] = old_name;
- if (new_name)
+ use_operand_p use_p;
+ ssa_op_iter op_iter;
+ FOR_EACH_SSA_USE_OPERAND (use_p, use_stmt, op_iter, SSA_OP_USE)
{
- new_phi_args [i] = new_name;
- continue;
+ /* Iterator to the current def of use_p. For function parameters or
+ anything where def is not found, insert at the beginning of the
+ generated region. */
+ gimple_stmt_iterator gsi_stmt = gsi_def_stmt;
+
+ tree op = USE_FROM_PTR (use_p);
+ gimple *stmt = SSA_NAME_DEF_STMT (op);
+ if (stmt && (gimple_code (stmt) != GIMPLE_NOP))
+ gsi_stmt = gsi_for_stmt (stmt);
+
+ /* For region parameters, insert at the beginning of the generated
+ region. */
+ if (!bb_in_sese_p (gsi_bb (gsi_stmt), codegen_region))
+ gsi_stmt = gsi_def_stmt;
+
+ gsi_def_stmt = later_of_the_two (gsi_stmt, gsi_def_stmt);
}
- /* If the phi-arg was a parameter. */
- if (vec_find (region->params, old_name) != -1)
+ if (!gsi_stmt (gsi_def_stmt))
{
- new_phi_args [i] = old_name;
- if (dump_file)
- {
- fprintf (dump_file,
- "[codegen] parameter argument to phi, new_expr: ");
- print_generic_expr (dump_file, new_phi_args[i]);
- fprintf (dump_file, "\n");
- }
- continue;
+ gimple_stmt_iterator gsi = gsi_after_labels (gsi_bb (gsi_def_stmt));
+ gsi_insert_before (&gsi, use_stmt, GSI_NEW_STMT);
}
-
- gimple *old_def_stmt = SSA_NAME_DEF_STMT (old_name);
- if (!old_def_stmt || gimple_code (old_def_stmt) == GIMPLE_NOP)
- /* FIXME: If the phi arg was a function arg, or wasn't defined, just use
- the old name. */
- return false;
-
- if (postpone)
+ else if (gimple_code (gsi_stmt (gsi_def_stmt)) == GIMPLE_PHI)
{
- /* If the phi-arg is scev-analyzeable but only in the first stage. */
- if (is_gimple_reg (old_name)
- && scev_analyzable_p (old_name, region->region))
- {
- gimple_seq stmts;
- tree new_expr = get_rename_from_scev (old_name, &stmts, loop,
- new_bb, old_bb, iv_map);
- if (codegen_error_p ())
- return false;
-
- gcc_assert (new_expr);
- if (dump_file)
- {
- fprintf (dump_file,
- "[codegen] scev analyzeable, new_expr: ");
- print_generic_expr (dump_file, new_expr);
- fprintf (dump_file, "\n");
- }
- gsi_insert_earliest (stmts);
- new_phi_args[i] = new_expr;
- continue;
- }
-
- /* Postpone code gen for later for back-edges. */
- region->incomplete_phis.safe_push (std::make_pair (phi, new_phi));
-
- if (dump_file)
- {
- fprintf (dump_file, "[codegen] postpone cond phi nodes: ");
- print_gimple_stmt (dump_file, new_phi, 0);
- }
-
- new_phi_args [i] = NULL_TREE;
- continue;
+ gimple_stmt_iterator bsi
+ = gsi_start_bb_nondebug (gsi_bb (gsi_def_stmt));
+ /* Insert right after the PHI statements. */
+ gsi_insert_before (&bsi, use_stmt, GSI_NEW_STMT);
}
else
- /* Either we should add the arg to phi or, we should postpone. */
- return false;
- }
+ gsi_insert_after (&gsi_def_stmt, use_stmt, GSI_NEW_STMT);
- /* If none of the args have been determined in the first stage then wait until
- later. */
- if (postpone && !new_phi_args[0] && !new_phi_args[1])
- return true;
-
- return add_phi_arg_for_new_expr (old_phi_args, new_phi_args,
- old_bb_dominating_edge,
- old_bb_non_dominating_edge,
- phi, new_phi, new_bb);
+ if (dump_file)
+ {
+ fprintf (dump_file, "[codegen] inserting statement: ");
+ print_gimple_stmt (dump_file, use_stmt, 0, TDF_VOPS | TDF_MEMSYMS);
+ print_loops_bb (dump_file, gimple_bb (use_stmt), 0, 3);
+ }
+ }
}
-/* Copy cond phi nodes from BB to NEW_BB. A cond-phi node is a basic block
- containing phi nodes coming from two predecessors, and none of them are back
- edges. */
+/* For ops which are scev_analyzeable, we can regenerate a new name from its
+ scalar evolution around LOOP. */
-bool translate_isl_ast_to_gimple::
-copy_cond_phi_nodes (basic_block bb, basic_block new_bb, vec<tree> iv_map)
+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);
- gcc_assert (!bb_contains_loop_close_phi_nodes (bb));
-
- /* TODO: Handle cond phi nodes with more than 2 predecessors. */
- if (EDGE_COUNT (bb->preds) != 2)
- return false;
-
- if (dump_file)
- fprintf (dump_file, "[codegen] copying cond phi nodes in bb_%d.\n",
- new_bb->index);
-
- for (gphi_iterator psi = gsi_start_phis (bb); !gsi_end_p (psi);
- gsi_next (&psi))
+ /* At this point we should know the exact scev for each
+ scalar SSA_NAME used in the scop: all the other scalar
+ SSA_NAMEs should have been translated out of SSA using
+ arrays with one element. */
+ tree new_expr;
+ if (chrec_contains_undetermined (scev))
{
- gphi *phi = psi.phi ();
- tree res = gimple_phi_result (phi);
- if (virtual_operand_p (res))
- continue;
+ set_codegen_error ();
+ return build_zero_cst (TREE_TYPE (old_name));
+ }
- gphi *new_phi = create_phi_node (NULL_TREE, new_bb);
- tree new_res = create_new_def_for (res, new_phi,
- gimple_phi_result_ptr (new_phi));
- set_rename (res, new_res);
+ new_expr = chrec_apply_map (scev, iv_map);
- if (!copy_cond_phi_args (phi, new_phi, iv_map, true))
- return false;
+ /* The apply should produce an expression tree containing
+ the uses of the new induction variables. We should be
+ able to use new_expr instead of the old_name in the newly
+ generated loop nest. */
+ if (chrec_contains_undetermined (new_expr)
+ || tree_contains_chrecs (new_expr, NULL))
+ {
+ set_codegen_error ();
+ return build_zero_cst (TREE_TYPE (old_name));
+ }
- update_stmt (new_phi);
+ 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));
+ }
}
- return true;
+ /* Replace the old_name with the new_expr. */
+ return force_gimple_operand (unshare_expr (new_expr), stmts,
+ true, NULL_TREE);
}
+
/* Return true if STMT should be copied from region to the new code-generated
region. LABELs, CONDITIONS, induction-variables and region parameters need
not be copied. */
@@ -2473,8 +1170,7 @@ set_rename_for_each_def (gimple *stmt)
FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, op_iter, SSA_OP_ALL_DEFS)
{
tree old_name = DEF_FROM_PTR (def_p);
- tree new_name = create_new_def_for (old_name, stmt, def_p);
- set_rename (old_name, new_name);
+ create_new_def_for (old_name, stmt, def_p);
}
}
@@ -2500,6 +1196,19 @@ graphite_copy_stmts_from_block (basic_bl
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
+ stmts we could simply do that. */
+ if (is_gimple_debug (copy))
+ {
+ if (gimple_debug_bind_p (copy))
+ gimple_debug_bind_reset_value (copy);
+ else if (gimple_debug_source_bind_p (copy))
+ ;
+ else
+ gcc_unreachable ();
+ }
+
if (dump_file)
{
fprintf (dump_file, "[codegen] inserting statement: ");
@@ -2512,13 +1221,6 @@ graphite_copy_stmts_from_block (basic_bl
/* Crete new names for each def in the copied stmt. */
set_rename_for_each_def (copy);
- loop_p loop = bb->loop_father;
- if (rename_uses (copy, &gsi_tgt, bb, loop, iv_map))
- {
- fold_stmt_inplace (&gsi_tgt);
- gcc_assert (gsi_stmt (gsi_tgt) == copy);
- }
-
if (codegen_error_p ())
return false;
@@ -2535,6 +1237,19 @@ graphite_copy_stmts_from_block (basic_bl
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;
@@ -2548,46 +1263,6 @@ graphite_copy_stmts_from_block (basic_bl
}
-/* Given a basic block containing close-phi it returns the new basic block where
- to insert a copy of the close-phi nodes. All the uses in close phis should
- come from a single loop otherwise it returns NULL. */
-
-edge translate_isl_ast_to_gimple::
-edge_for_new_close_phis (basic_block bb)
-{
- /* Make sure that NEW_BB is the new_loop->exit->dest. We find the definition
- of close phi in the original code and then find the mapping of basic block
- defining that variable. If there are multiple close-phis and they are
- defined in different loops (in the original or in the new code) because of
- loop splitting, then we bail out. */
- loop_p new_loop = NULL;
- for (gphi_iterator psi = gsi_start_phis (bb); !gsi_end_p (psi);
- gsi_next (&psi))
- {
- gphi *phi = psi.phi ();
- tree name = gimple_phi_arg_def (phi, 0);
- basic_block old_loop_bb = gimple_bb (SSA_NAME_DEF_STMT (name));
-
- vec <basic_block> *bbs = region->copied_bb_map->get (old_loop_bb);
- if (!bbs || bbs->length () != 1)
- /* This is one of the places which shows preserving original structure
- is not always possible, as we may need to insert close PHI for a loop
- where the latch does not have any mapping, or the mapping is
- ambiguous. */
- return NULL;
-
- if (!new_loop)
- new_loop = (*bbs)[0]->loop_father;
- else if (new_loop != (*bbs)[0]->loop_father)
- return NULL;
- }
-
- if (!new_loop)
- return NULL;
-
- return single_exit (new_loop);
-}
-
/* Copies BB and includes in the copied BB all the statements that can
be reached following the use-def chains from the memory accesses,
and returns the next edge following this new block. */
@@ -2595,113 +1270,34 @@ edge_for_new_close_phis (basic_block bb)
edge translate_isl_ast_to_gimple::
copy_bb_and_scalar_dependences (basic_block bb, edge next_e, vec<tree> iv_map)
{
- int num_phis = number_of_phi_nodes (bb);
- basic_block new_bb = NULL;
- if (bb_contains_loop_close_phi_nodes (bb))
+ basic_block new_bb = split_edge (next_e);
+ gimple_stmt_iterator gsi_tgt = gsi_last_bb (new_bb);
+ for (gphi_iterator psi = gsi_start_phis (bb); !gsi_end_p (psi);
+ gsi_next (&psi))
{
- if (dump_file)
- fprintf (dump_file, "[codegen] bb_%d contains close phi nodes.\n",
- bb->index);
-
- edge e = edge_for_new_close_phis (bb);
- if (!e)
- {
- set_codegen_error ();
- return NULL;
- }
-
- basic_block phi_bb = e->dest;
-
- if (!bb_contains_loop_close_phi_nodes (phi_bb) || !single_succ_p (phi_bb))
- phi_bb = split_edge (e);
-
- gcc_assert (single_pred_edge (phi_bb)->src->loop_father
- != single_pred_edge (phi_bb)->dest->loop_father);
+ gphi *phi = psi.phi ();
+ tree res = gimple_phi_result (phi);
+ if (virtual_operand_p (res)
+ || scev_analyzable_p (res, region->region))
+ continue;
- if (!copy_loop_close_phi_nodes (bb, phi_bb, iv_map))
+ tree new_phi_def;
+ vec <tree> *renames = region->rename_map->get (res);
+ if (! renames || renames->is_empty ())
{
- set_codegen_error ();
- return NULL;
+ new_phi_def = create_tmp_reg (TREE_TYPE (res));
+ set_rename (res, new_phi_def);
}
-
- if (e == next_e)
- new_bb = phi_bb;
else
- new_bb = split_edge (next_e);
- }
- else
- {
- new_bb = split_edge (next_e);
- if (num_phis > 0 && bb_contains_loop_phi_nodes (bb))
{
- basic_block phi_bb = next_e->dest->loop_father->header;
-
- /* At this point we are unable to codegenerate by still preserving the SSA
- structure because maybe the loop is completely unrolled and the PHIs
- and cross-bb scalar dependencies are untrackable w.r.t. the original
- code. See gfortran.dg/graphite/pr29832.f90. */
- if (EDGE_COUNT (bb->preds) != EDGE_COUNT (phi_bb->preds))
- {
- set_codegen_error ();
- return NULL;
- }
-
- /* In case isl did some loop peeling, like this:
-
- S_8(0);
- for (int c1 = 1; c1 <= 5; c1 += 1) {
- S_8(c1);
- }
- S_8(6);
-
- there should be no loop-phi nodes in S_8(0).
-
- FIXME: We need to reason about dynamic instances of S_8, i.e., the
- values of all scalar variables: for the moment we instantiate only
- SCEV analyzable expressions on the iteration domain, and we need to
- extend that to reductions that cannot be analyzed by SCEV. */
- if (!bb_in_sese_p (phi_bb, region->if_region->true_region->region))
- {
- set_codegen_error ();
- return NULL;
- }
-
- if (dump_file)
- fprintf (dump_file, "[codegen] bb_%d contains loop phi nodes.\n",
- bb->index);
- if (!copy_loop_phi_nodes (bb, phi_bb))
- {
- set_codegen_error ();
- return NULL;
- }
- }
- else if (num_phis > 0)
- {
- if (dump_file)
- fprintf (dump_file, "[codegen] bb_%d contains cond phi nodes.\n",
- bb->index);
-
- basic_block phi_bb = single_pred (new_bb);
- loop_p loop_father = new_bb->loop_father;
-
- /* Move back until we find the block with two predecessors. */
- while (single_pred_p (phi_bb))
- phi_bb = single_pred_edge (phi_bb)->src;
-
- /* If a corresponding merge-point was not found, then abort codegen. */
- if (phi_bb->loop_father != loop_father
- || !bb_in_sese_p (phi_bb, region->if_region->true_region->region)
- || !copy_cond_phi_nodes (bb, phi_bb, iv_map))
- {
- set_codegen_error ();
- return NULL;
- }
+ gcc_assert (renames->length () == 1);
+ new_phi_def = (*renames)[0];
}
- }
- if (dump_file)
- fprintf (dump_file, "[codegen] copying from bb_%d to bb_%d.\n",
- bb->index, new_bb->index);
+ 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)
@@ -2720,57 +1316,66 @@ copy_bb_and_scalar_dependences (basic_bl
return NULL;
}
- return single_succ_edge (new_bb);
-}
-
-/* Patch the missing arguments of the phi nodes. */
-
-void translate_isl_ast_to_gimple::
-translate_pending_phi_nodes ()
-{
- int i;
- phi_rename *rename;
- FOR_EACH_VEC_ELT (region->incomplete_phis, i, rename)
+ /* Insert out-of SSA copies on the original BB outgoing edges. */
+ gsi_tgt = gsi_last_bb (new_bb);
+ basic_block bb_for_succs = bb;
+ if (bb_for_succs == bb_for_succs->loop_father->latch
+ && bb_in_sese_p (bb_for_succs, region->region)
+ && sese_trivially_empty_bb_p (bb_for_succs))
+ bb_for_succs = NULL;
+ while (bb_for_succs)
{
- gphi *old_phi = rename->first;
- gphi *new_phi = rename->second;
- basic_block old_bb = gimple_bb (old_phi);
- basic_block new_bb = gimple_bb (new_phi);
-
- /* First edge is the init edge and second is the back edge. */
- init_back_edge_pair_t ibp_old_bb = get_edges (old_bb);
- init_back_edge_pair_t ibp_new_bb = get_edges (new_bb);
-
- if (dump_file)
+ basic_block latch = NULL;
+ edge_iterator ei;
+ edge e;
+ FOR_EACH_EDGE (e, ei, bb_for_succs->succs)
{
- fprintf (dump_file, "[codegen] translating pending old-phi: ");
- print_gimple_stmt (dump_file, old_phi, 0);
- }
+ for (gphi_iterator psi = gsi_start_phis (e->dest); !gsi_end_p (psi);
+ gsi_next (&psi))
+ {
+ gphi *phi = psi.phi ();
+ tree res = gimple_phi_result (phi);
+ if (virtual_operand_p (res)
+ || scev_analyzable_p (res, region->region))
+ continue;
- auto_vec <tree, 1> iv_map;
- if (bb_contains_loop_phi_nodes (new_bb)
- && bb_contains_loop_phi_nodes (old_bb))
- {
- if (!copy_loop_phi_args (old_phi, ibp_old_bb, new_phi,
- ibp_new_bb, false))
- set_codegen_error ();
- }
- else if (bb_contains_loop_close_phi_nodes (new_bb))
- {
- if (!copy_loop_close_phi_args (old_bb, new_bb, iv_map, false))
- set_codegen_error ();
- }
- else if (!copy_cond_phi_args (old_phi, new_phi, iv_map, false))
- set_codegen_error ();
+ tree new_phi_def;
+ vec <tree> *renames = region->rename_map->get (res);
+ if (! renames || renames->is_empty ())
+ {
+ 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];
+ }
- if (dump_file)
- {
- fprintf (dump_file, "[codegen] to new-phi: ");
- print_gimple_stmt (dump_file, new_phi, 0);
+ tree arg = PHI_ARG_DEF_FROM_EDGE (phi, e);
+ if (TREE_CODE (arg) == SSA_NAME
+ && scev_analyzable_p (arg, region->region))
+ {
+ gimple_seq stmts = NULL;
+ tree new_name = get_rename_from_scev (arg, &stmts,
+ bb->loop_father,
+ new_bb, bb, iv_map);
+ if (! codegen_error_p ())
+ gsi_insert_earliest (stmts);
+ arg = new_name;
+ }
+ gassign *ass = gimple_build_assign (new_phi_def, arg);
+ gsi_insert_after (&gsi_tgt, ass, GSI_NEW_STMT);
+ }
+ if (e->dest == bb_for_succs->loop_father->latch
+ && bb_in_sese_p (e->dest, region->region)
+ && sese_trivially_empty_bb_p (e->dest))
+ latch = e->dest;
}
- if (codegen_error_p ())
- return;
+ bb_for_succs = latch;
}
+
+ return single_succ_edge (new_bb);
}
/* Add isl's parameter identifiers and corresponding trees to ivs_params. */
@@ -2953,8 +1558,6 @@ graphite_regenerate_ast_isl (scop_p scop
t.translate_isl_ast (context_loop, root_node, e, ip);
if (! t.codegen_error_p ())
- t.translate_pending_phi_nodes ();
- if (! t.codegen_error_p ())
{
sese_insert_phis_for_liveouts (region,
if_region->region->region.exit->src,
@@ -2965,6 +1568,8 @@ graphite_regenerate_ast_isl (scop_p scop
mark_virtual_operands_for_renaming (cfun);
update_ssa (TODO_update_ssa);
+ checking_verify_ssa (true, true);
+ rewrite_into_loop_closed_ssa (NULL, 0);
}
if (t.codegen_error_p ())
Index: gcc/graphite-scop-detection.c
===================================================================
--- gcc/graphite-scop-detection.c (revision 253394)
+++ gcc/graphite-scop-detection.c (working copy)
@@ -254,21 +254,6 @@ dot_cfg ()
scops.release ();
}
-/* Return true if BB is empty, contains only DEBUG_INSNs. */
-
-static bool
-trivially_empty_bb_p (basic_block bb)
-{
- gimple_stmt_iterator gsi;
-
- for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
- if (gimple_code (gsi_stmt (gsi)) != GIMPLE_DEBUG
- && gimple_code (gsi_stmt (gsi)) != GIMPLE_LABEL)
- return false;
-
- return true;
-}
-
/* Can all ivs be represented by a signed integer?
As isl might generate negative values in its expressions, signed loop ivs
are required in the backend. */
@@ -471,7 +456,7 @@ scop_detection::get_sese (loop_p loop)
canonicalize_loop_closed_ssa makes sure that is in proper shape. */
if (! single_pred_p (scop_end->dest)
|| ! single_succ_p (scop_end->dest)
- || ! trivially_empty_bb_p (scop_end->dest))
+ || ! sese_trivially_empty_bb_p (scop_end->dest))
gcc_unreachable ();
scop_end = single_succ_edge (scop_end->dest);
@@ -1346,13 +1331,35 @@ find_scop_parameters (scop_p scop)
scop_set_nb_params (scop, nbp);
}
+static void
+add_write (vec<tree> *writes, tree def)
+{
+ writes->safe_push (def);
+ DEBUG_PRINT (dp << "Adding scalar write: ";
+ print_generic_expr (dump_file, def);
+ dp << "\nFrom stmt: ";
+ print_gimple_stmt (dump_file,
+ SSA_NAME_DEF_STMT (def), 0));
+}
+
+static void
+add_read (vec<scalar_use> *reads, tree use, gimple *use_stmt)
+{
+ DEBUG_PRINT (dp << "Adding scalar read: ";
+ print_generic_expr (dump_file, use);
+ dp << "\nFrom stmt: ";
+ print_gimple_stmt (dump_file, use_stmt, 0));
+ reads->safe_push (std::make_pair (use_stmt, use));
+}
+
+
/* Record DEF if it is used in other bbs different than DEF_BB in the SCOP. */
static void
build_cross_bb_scalars_def (scop_p scop, tree def, basic_block def_bb,
vec<tree> *writes)
{
- if (!def || !is_gimple_reg (def))
+ if (!is_gimple_reg (def))
return;
bool scev_analyzable = scev_analyzable_p (def, scop->scop_info->region);
@@ -1366,16 +1373,9 @@ build_cross_bb_scalars_def (scop_p scop,
/* But gather SESE liveouts as we otherwise fail to rewrite their
exit PHIs. */
|| ! bb_in_sese_p (gimple_bb (use_stmt), scop->scop_info->region))
- && ((def_bb != gimple_bb (use_stmt) && !is_gimple_debug (use_stmt))
- /* PHIs have their effect at "BBs" on the edges. See PR79622. */
- || gimple_code (SSA_NAME_DEF_STMT (def)) == GIMPLE_PHI))
+ && (def_bb != gimple_bb (use_stmt) && !is_gimple_debug (use_stmt)))
{
- writes->safe_push (def);
- DEBUG_PRINT (dp << "Adding scalar write: ";
- print_generic_expr (dump_file, def);
- dp << "\nFrom stmt: ";
- print_gimple_stmt (dump_file,
- SSA_NAME_DEF_STMT (def), 0));
+ add_write (writes, def);
/* This is required by the FOR_EACH_IMM_USE_STMT when we want to break
before all the uses have been visited. */
BREAK_FROM_IMM_USE_STMT (imm_iter);
@@ -1389,7 +1389,6 @@ static void
build_cross_bb_scalars_use (scop_p scop, tree use, gimple *use_stmt,
vec<scalar_use> *reads)
{
- gcc_assert (use);
if (!is_gimple_reg (use))
return;
@@ -1399,46 +1398,8 @@ build_cross_bb_scalars_use (scop_p scop,
return;
gimple *def_stmt = SSA_NAME_DEF_STMT (use);
- if (gimple_bb (def_stmt) != gimple_bb (use_stmt)
- /* PHIs have their effect at "BBs" on the edges. See PR79622. */
- || gimple_code (def_stmt) == GIMPLE_PHI)
- {
- DEBUG_PRINT (dp << "Adding scalar read: ";
- print_generic_expr (dump_file, use);
- dp << "\nFrom stmt: ";
- print_gimple_stmt (dump_file, use_stmt, 0));
- reads->safe_push (std::make_pair (use_stmt, use));
- }
-}
-
-/* Record all scalar variables that are defined and used in different BBs of the
- SCOP. */
-
-static void
-graphite_find_cross_bb_scalar_vars (scop_p scop, gimple *stmt,
- vec<scalar_use> *reads, vec<tree> *writes)
-{
- tree def;
-
- if (gimple_code (stmt) == GIMPLE_ASSIGN)
- def = gimple_assign_lhs (stmt);
- else if (gimple_code (stmt) == GIMPLE_CALL)
- def = gimple_call_lhs (stmt);
- else if (gimple_code (stmt) == GIMPLE_PHI)
- def = gimple_phi_result (stmt);
- else
- return;
-
-
- build_cross_bb_scalars_def (scop, def, gimple_bb (stmt), writes);
-
- ssa_op_iter iter;
- use_operand_p use_p;
- FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE)
- {
- tree use = USE_FROM_PTR (use_p);
- build_cross_bb_scalars_use (scop, use, stmt, reads);
- }
+ if (gimple_bb (def_stmt) != gimple_bb (use_stmt))
+ add_read (reads, use, use_stmt);
}
/* Generates a polyhedral black box only if the bb contains interesting
@@ -1467,13 +1428,89 @@ try_generate_gimple_bb (scop_p scop, bas
continue;
graphite_find_data_references_in_stmt (nest, loop, stmt, &drs);
- graphite_find_cross_bb_scalar_vars (scop, stmt, &reads, &writes);
+
+ tree def = gimple_get_lhs (stmt);
+ if (def)
+ build_cross_bb_scalars_def (scop, def, gimple_bb (stmt), &writes);
+
+ ssa_op_iter iter;
+ tree use;
+ FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
+ build_cross_bb_scalars_use (scop, use, stmt, &reads);
}
+ /* Handle defs and uses in PHIs. Those need special treatment given
+ that we have to present ISL with sth that looks like we've rewritten
+ the IL out-of-SSA. */
for (gphi_iterator psi = gsi_start_phis (bb); !gsi_end_p (psi);
gsi_next (&psi))
- if (!virtual_operand_p (gimple_phi_result (psi.phi ())))
- graphite_find_cross_bb_scalar_vars (scop, psi.phi (), &reads, &writes);
+ {
+ gphi *phi = psi.phi ();
+ tree res = gimple_phi_result (phi);
+ if (virtual_operand_p (res)
+ || scev_analyzable_p (res, scop->scop_info->region))
+ continue;
+ /* To simulate out-of-SSA the block containing the PHI node has
+ reads of the PHI destination. And to preserve SSA dependences
+ we also write to it (the out-of-SSA decl and the SSA result
+ are coalesced for dependence purposes which is good enough). */
+ add_read (&reads, res, phi);
+ add_write (&writes, res);
+ }
+ basic_block bb_for_succs = bb;
+ if (bb_for_succs == bb_for_succs->loop_father->latch
+ && bb_in_sese_p (bb_for_succs, scop->scop_info->region)
+ && sese_trivially_empty_bb_p (bb_for_succs))
+ bb_for_succs = NULL;
+ while (bb_for_succs)
+ {
+ basic_block latch = NULL;
+ edge_iterator ei;
+ edge e;
+ FOR_EACH_EDGE (e, ei, bb_for_succs->succs)
+ {
+ for (gphi_iterator psi = gsi_start_phis (e->dest); !gsi_end_p (psi);
+ gsi_next (&psi))
+ {
+ gphi *phi = psi.phi ();
+ tree res = gimple_phi_result (phi);
+ if (virtual_operand_p (res))
+ continue;
+ /* To simulate out-of-SSA the predecessor of edges into PHI nodes
+ has a copy from the PHI argument to the PHI destination. */
+ if (! scev_analyzable_p (res, scop->scop_info->region))
+ add_write (&writes, res);
+ tree use = PHI_ARG_DEF_FROM_EDGE (phi, e);
+ if (TREE_CODE (use) == SSA_NAME
+ && ! SSA_NAME_IS_DEFAULT_DEF (use)
+ && gimple_bb (SSA_NAME_DEF_STMT (use)) != bb_for_succs
+ && ! scev_analyzable_p (use, scop->scop_info->region))
+ add_read (&reads, use, phi);
+ }
+ if (e->dest == bb_for_succs->loop_father->latch
+ && bb_in_sese_p (e->dest, scop->scop_info->region)
+ && sese_trivially_empty_bb_p (e->dest))
+ latch = e->dest;
+ }
+ /* Handle empty latch block PHIs here, otherwise we confuse ISL
+ with extra conditional code where it then peels off the last
+ iteration just because of that. It would be simplest if we
+ just didn't force simple latches (thus remove the forwarder). */
+ bb_for_succs = latch;
+ }
+
+ /* For the region exit block add reads for all live-out vars. */
+ if (bb == scop->scop_info->region.exit->src)
+ {
+ sese_build_liveouts (scop->scop_info);
+ unsigned i;
+ bitmap_iterator bi;
+ EXECUTE_IF_SET_IN_BITMAP (scop->scop_info->liveout, 0, i, bi)
+ {
+ tree use = ssa_name (i);
+ add_read (&reads, use, NULL);
+ }
+ }
if (drs.is_empty () && writes.is_empty () && reads.is_empty ())
return NULL;
@@ -1700,6 +1737,10 @@ build_scops (vec<scop_p> *scops)
sese_l *s;
FOR_EACH_VEC_ELT (scops_l, i, s)
{
+ /* For our out-of-SSA we need a block on s->entry, similar to how
+ we include the LCSSA block in the region. */
+ s->entry = single_pred_edge (split_edge (s->entry));
+
scop_p scop = new_scop (s->entry, s->exit);
/* Record all basic blocks and their conditions in REGION. */
Index: gcc/sese.c
===================================================================
--- gcc/sese.c (revision 253394)
+++ gcc/sese.c (working copy)
@@ -68,106 +68,80 @@ sese_build_liveouts_use (sese_info_p reg
used in BB that is outside of the REGION. */
static void
-sese_build_liveouts_bb (sese_info_p region, bitmap liveouts, basic_block bb)
+sese_build_liveouts_bb (sese_info_p region, basic_block bb)
{
- edge e;
- edge_iterator ei;
ssa_op_iter iter;
use_operand_p use_p;
- FOR_EACH_EDGE (e, ei, bb->succs)
- for (gphi_iterator bsi = gsi_start_phis (e->dest); !gsi_end_p (bsi);
- gsi_next (&bsi))
- sese_build_liveouts_use (region, liveouts, bb,
- PHI_ARG_DEF_FROM_EDGE (bsi.phi (), e));
+ for (gphi_iterator bsi = gsi_start_phis (bb); !gsi_end_p (bsi);
+ gsi_next (&bsi))
+ FOR_EACH_PHI_ARG (use_p, bsi.phi (), iter, SSA_OP_USE)
+ sese_build_liveouts_use (region, region->liveout,
+ bb, USE_FROM_PTR (use_p));
for (gimple_stmt_iterator bsi = gsi_start_bb (bb); !gsi_end_p (bsi);
gsi_next (&bsi))
{
gimple *stmt = gsi_stmt (bsi);
+ bitmap liveouts = region->liveout;
if (is_gimple_debug (stmt))
- continue;
+ liveouts = region->debug_liveout;
- FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
+ FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
sese_build_liveouts_use (region, liveouts, bb, USE_FROM_PTR (use_p));
}
}
-/* For a USE in BB, return true if BB is outside REGION and it's not
- in the LIVEOUTS set. */
-
-static bool
-sese_bad_liveouts_use (sese_info_p region, bitmap liveouts, basic_block bb,
- tree use)
-{
- gcc_assert (!bb_in_sese_p (bb, region->region));
-
- if (TREE_CODE (use) != SSA_NAME)
- return false;
-
- unsigned ver = SSA_NAME_VERSION (use);
-
- /* If it's in liveouts, the variable will get a new PHI node, and
- the debug use will be properly adjusted. */
- if (bitmap_bit_p (liveouts, ver))
- return false;
-
- basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (use));
-
- if (!def_bb || !bb_in_sese_p (def_bb, region->region))
- return false;
-
- return true;
-}
-
/* Reset debug stmts that reference SSA_NAMES defined in REGION that
are not marked as liveouts. */
static void
-sese_reset_debug_liveouts_bb (sese_info_p region, bitmap liveouts,
- basic_block bb)
+sese_reset_debug_liveouts (sese_info_p region)
{
- gimple_stmt_iterator bsi;
- ssa_op_iter iter;
- use_operand_p use_p;
-
- for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
+ bitmap_iterator bi;
+ unsigned i;
+ EXECUTE_IF_AND_COMPL_IN_BITMAP (region->debug_liveout, region->liveout,
+ 0, i, bi)
{
- gimple *stmt = gsi_stmt (bsi);
-
- if (!is_gimple_debug (stmt))
- continue;
-
- FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
- if (sese_bad_liveouts_use (region, liveouts, bb,
- USE_FROM_PTR (use_p)))
- {
- gimple_debug_bind_reset_value (stmt);
- update_stmt (stmt);
- break;
- }
+ tree name = ssa_name (i);
+ auto_vec<gimple *, 4> stmts;
+ gimple *use_stmt;
+ imm_use_iterator use_iter;
+ FOR_EACH_IMM_USE_STMT (use_stmt, use_iter, name)
+ {
+ if (! is_gimple_debug (use_stmt)
+ || bb_in_sese_p (gimple_bb (use_stmt), region->region))
+ continue;
+ stmts.safe_push (use_stmt);
+ }
+ while (!stmts.is_empty ())
+ {
+ gimple *stmt = stmts.pop ();
+ gimple_debug_bind_reset_value (stmt);
+ update_stmt (stmt);
+ }
}
}
/* Build the LIVEOUTS of REGION: the set of variables defined inside
and used outside the REGION. */
-static void
-sese_build_liveouts (sese_info_p region, bitmap liveouts)
+void
+sese_build_liveouts (sese_info_p region)
{
basic_block bb;
+ gcc_assert (region->liveout == NULL
+ && region->debug_liveout == NULL);
+
+ region->liveout = BITMAP_ALLOC (NULL);
+ region->debug_liveout = BITMAP_ALLOC (NULL);
+
/* FIXME: We could start iterating form the successor of sese. */
FOR_EACH_BB_FN (bb, cfun)
if (!bb_in_sese_p (bb, region->region))
- sese_build_liveouts_bb (region, liveouts, bb);
-
- /* FIXME: We could start iterating form the successor of sese. */
- if (MAY_HAVE_DEBUG_STMTS)
- FOR_EACH_BB_FN (bb, cfun)
- if (!bb_in_sese_p (bb, region->region))
- sese_reset_debug_liveouts_bb (region, liveouts, bb);
+ sese_build_liveouts_bb (region, bb);
}
/* Builds a new SESE region from edges ENTRY and EXIT. */
@@ -179,6 +153,8 @@ new_sese_info (edge entry, edge exit)
region->region.entry = entry;
region->region.exit = exit;
+ region->liveout = NULL;
+ region->debug_liveout = NULL;
region->params.create (3);
region->rename_map = new rename_map_t;
region->parameter_rename_map = new parameter_rename_map_t;
@@ -196,6 +172,8 @@ void
free_sese_info (sese_info_p region)
{
region->params.release ();
+ BITMAP_FREE (region->liveout);
+ BITMAP_FREE (region->debug_liveout);
for (rename_map_t::iterator it = region->rename_map->begin ();
it != region->rename_map->end (); ++it)
@@ -246,17 +224,14 @@ void
sese_insert_phis_for_liveouts (sese_info_p region, basic_block bb,
edge false_e, edge true_e)
{
+ if (MAY_HAVE_DEBUG_STMTS)
+ sese_reset_debug_liveouts (region);
+
unsigned i;
bitmap_iterator bi;
- bitmap liveouts = BITMAP_ALLOC (NULL);
-
- sese_build_liveouts (region, liveouts);
-
- EXECUTE_IF_SET_IN_BITMAP (liveouts, 0, i, bi)
+ EXECUTE_IF_SET_IN_BITMAP (region->liveout, 0, i, bi)
if (!virtual_operand_p (ssa_name (i)))
sese_add_exit_phis_edge (bb, ssa_name (i), false_e, true_e);
-
- BITMAP_FREE (liveouts);
}
/* Returns the outermost loop in SCOP that contains BB. */
@@ -369,6 +344,8 @@ move_sese_in_condition (sese_info_p regi
if_region->true_region->region.exit
= single_succ_edge (split_edge (true_edge));
+ region->region = if_region->false_region->region;
+
return if_region;
}
@@ -471,7 +448,10 @@ scev_analyzable_p (tree def, sese_l ®
&& (TREE_CODE (scev) != SSA_NAME
|| !defined_in_sese_p (scev, region))
&& (tree_does_not_contain_chrecs (scev)
- || evolution_function_is_affine_p (scev));
+ || evolution_function_is_affine_p (scev))
+ && (! loop
+ || ! loop_in_sese_p (loop, region)
+ || ! chrec_contains_symbols_defined_in_loop (scev, loop->num));
}
/* Returns the scalar evolution of T in REGION. Every variable that
@@ -518,6 +498,21 @@ scalar_evolution_in_region (const sese_l
return instantiate_scev (before, loop, t);
}
+/* Return true if BB is empty, contains only DEBUG_INSNs. */
+
+bool
+sese_trivially_empty_bb_p (basic_block bb)
+{
+ gimple_stmt_iterator gsi;
+
+ for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+ if (gimple_code (gsi_stmt (gsi)) != GIMPLE_DEBUG
+ && gimple_code (gsi_stmt (gsi)) != GIMPLE_LABEL)
+ return false;
+
+ return true;
+}
+
/* Pretty print edge E to FILE. */
void
Index: gcc/sese.h
===================================================================
--- gcc/sese.h (revision 253394)
+++ gcc/sese.h (working copy)
@@ -83,6 +83,12 @@ typedef struct sese_info_t
/* The SESE region. */
sese_l region;
+ /* Liveout vars. */
+ bitmap liveout;
+
+ /* Liveout in debug stmts. */
+ bitmap debug_liveout;
+
/* Parameters used within the SCOP. */
vec<tree> params;
@@ -116,6 +122,8 @@ extern struct loop *outermost_loop_in_se
extern tree scalar_evolution_in_region (const sese_l &, loop_p, tree);
extern bool scev_analyzable_p (tree, sese_l &);
extern bool invariant_in_sese_p_rec (tree, const sese_l &, bool *);
+extern void sese_build_liveouts (sese_info_p);
+extern bool sese_trivially_empty_bb_p (basic_block);
/* The number of parameters in REGION. */
Index: gcc/testsuite/gcc.dg/graphite/id-15.c
===================================================================
--- gcc/testsuite/gcc.dg/graphite/id-15.c (revision 253394)
+++ gcc/testsuite/gcc.dg/graphite/id-15.c (working copy)
@@ -1,5 +1,4 @@
/* { dg-require-effective-target int32plus } */
-/* { dg-additional-options "--param graphite-allow-codegen-errors=1" { target ilp32 } } */
typedef long unsigned int size_t;
extern void *memset (void *__s, int __c, size_t __n) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1)));
@@ -118,5 +117,3 @@ mul_double (l1, h1, l2, h2, lv, hv)
}
return (*hv < 0 ? ~(toplow & tophigh) : toplow | tophigh) != 0;
}
-
-/* { dg-final { scan-tree-dump-times "code generation error" 1 "graphite" { target ilp32 } } } */
Index: gcc/testsuite/gcc.dg/graphite/id-16.c
===================================================================
--- gcc/testsuite/gcc.dg/graphite/id-16.c (revision 253394)
+++ gcc/testsuite/gcc.dg/graphite/id-16.c (working copy)
@@ -1,5 +1,3 @@
-/* { dg-additional-options "--param graphite-allow-codegen-errors=1" } */
-
int transformation[(2*19 - 1) * (2*19 - 1)][8];
const int transformation2[8][2][2] = {
@@ -44,5 +42,3 @@ transformation_init (void)
}
}
}
-
-/* { dg-final { scan-tree-dump-times "code generation error" 1 "graphite" } } */
Index: gcc/testsuite/gcc.dg/graphite/pr46168.c
===================================================================
--- gcc/testsuite/gcc.dg/graphite/pr46168.c (revision 253394)
+++ gcc/testsuite/gcc.dg/graphite/pr46168.c (working copy)
@@ -1,5 +1,5 @@
/* { dg-do compile } */
-/* { dg-options "-O -ftree-loop-linear -fdump-tree-graphite-details --param graphite-allow-codegen-errors=1" } */
+/* { dg-options "-O -ftree-loop-linear" } */
int
foo (int a[4096], int mi, int mj)
@@ -13,5 +13,3 @@ foo (int a[4096], int mi, int mj)
}
return i16;
}
-
-/* { dg-final { scan-tree-dump-times "code generation error" 1 "graphite" } } */
Index: gcc/testsuite/gcc.dg/graphite/pr68756.c
===================================================================
--- gcc/testsuite/gcc.dg/graphite/pr68756.c (revision 253394)
+++ gcc/testsuite/gcc.dg/graphite/pr68756.c (working copy)
@@ -1,5 +1,5 @@
/* { dg-do compile } */
-/* { dg-options "-O1 -floop-nest-optimize -fdump-tree-graphite-details --param graphite-allow-codegen-errors=1" } */
+/* { dg-options "-O1 -floop-nest-optimize" } */
unsigned int z4, pz;
int nn[2];
@@ -24,5 +24,3 @@ la (void)
pz = xq (hn);
}
}
-
-/* { dg-final { scan-tree-dump-times "code generation error" 1 "graphite" } } */
Index: gcc/testsuite/gcc.dg/graphite/pr69728.c
===================================================================
--- gcc/testsuite/gcc.dg/graphite/pr69728.c (revision 253394)
+++ gcc/testsuite/gcc.dg/graphite/pr69728.c (working copy)
@@ -1,5 +1,5 @@
/* { dg-do compile } */
-/* { dg-options "-O3 -floop-nest-optimize -fdump-tree-graphite-details --param graphite-allow-codegen-errors=1" } */
+/* { dg-options "-O3 -floop-nest-optimize" } */
int a[1];
int b, c, d, e;
@@ -19,5 +19,3 @@ fn1 ()
}
}
}
-
-/* { dg-final { scan-tree-dump-times "code generation error" 1 "graphite" } } */
Index: gcc/testsuite/gcc.dg/graphite/pr71575-2.c
===================================================================
--- gcc/testsuite/gcc.dg/graphite/pr71575-2.c (revision 253394)
+++ gcc/testsuite/gcc.dg/graphite/pr71575-2.c (working copy)
@@ -1,5 +1,5 @@
/* { dg-do compile } */
-/* { dg-options "-Ofast -floop-nest-optimize -fdump-tree-graphite-details --param graphite-allow-codegen-errors=1" } */
+/* { dg-options "-Ofast -floop-nest-optimize" } */
int *a;
int b, c, d, e, g;
@@ -14,5 +14,3 @@ void fn1() {
}
}
}
-
-/* { dg-final { scan-tree-dump-times "code generation error" 1 "graphite" } } */
Index: gcc/testsuite/gcc.dg/graphite/pr77362.c
===================================================================
--- gcc/testsuite/gcc.dg/graphite/pr77362.c (revision 253394)
+++ gcc/testsuite/gcc.dg/graphite/pr77362.c (working copy)
@@ -1,5 +1,5 @@
/* { dg-do compile } */
-/* { dg-options "-O2 -floop-nest-optimize -fdump-tree-graphite-details --param graphite-allow-codegen-errors=1" } */
+/* { dg-options "-O2 -floop-nest-optimize" } */
int mc[2];
int f2, sk;
@@ -18,5 +18,3 @@ zm (void)
++hm;
}
}
-
-/* { dg-final { scan-tree-dump-times "code generation error" 1 "graphite" } } */
Index: gcc/testsuite/gcc.dg/graphite/pr81373.c
===================================================================
--- gcc/testsuite/gcc.dg/graphite/pr81373.c (revision 253394)
+++ gcc/testsuite/gcc.dg/graphite/pr81373.c (working copy)
@@ -1,4 +1,4 @@
-/* { dg-options "-fno-tree-scev-cprop -fgraphite-identity -O -fdump-tree-graphite-all --param graphite-allow-codegen-errors=1" } */
+/* { dg-options "-fno-tree-scev-cprop -fgraphite-identity -O" } */
void bar (void);
@@ -38,4 +38,3 @@ int toto()
}
/* { dg-final { scan-tree-dump-times "number of SCoPs: 2" 1 "graphite"} } */
-/* { dg-final { scan-tree-dump-times "code generation error" 1 "graphite" } } */
Index: gcc/testsuite/gcc.dg/graphite/run-id-pr67700-1.c
===================================================================
--- gcc/testsuite/gcc.dg/graphite/run-id-pr67700-1.c (revision 253394)
+++ gcc/testsuite/gcc.dg/graphite/run-id-pr67700-1.c (working copy)
@@ -1,5 +1,3 @@
-/* { dg-additional-options "--param graphite-allow-codegen-errors=1" } */
-
#include <stdlib.h>
#include <assert.h>
@@ -47,5 +45,3 @@ int main()
assert (obj->elem1[8] == 45);
return 0;
}
-
-/* { dg-final { scan-tree-dump-times "code generation error" 1 "graphite" } } */
Index: gcc/testsuite/gfortran.dg/graphite/interchange-1.f
===================================================================
--- gcc/testsuite/gfortran.dg/graphite/interchange-1.f (revision 253394)
+++ gcc/testsuite/gfortran.dg/graphite/interchange-1.f (working copy)
@@ -1,4 +1,3 @@
-! { dg-additional-options "--param graphite-allow-codegen-errors=1" }
subroutine foo(f1,f2,f3,f4,f5,f6,f7,f8,f9,f0,g1,g2,g3)
implicit none
integer f4,f3,f2,f1
@@ -43,4 +42,3 @@
! kernel from bwaves.
! { dg-final { scan-tree-dump-times "will be interchanged" 1 "graphite" { xfail *-*-* } } }
-! { dg-final { scan-tree-dump-times "code generation error" 1 "graphite" } }
Index: gcc/testsuite/gfortran.dg/graphite/pr29581.f90
===================================================================
--- gcc/testsuite/gfortran.dg/graphite/pr29581.f90 (revision 253394)
+++ gcc/testsuite/gfortran.dg/graphite/pr29581.f90 (working copy)
@@ -1,6 +1,7 @@
! PR tree-optimization/29581
! { dg-do run }
-! { dg-options "-O2 -ftree-loop-linear -fdump-tree-graphite-details --param graphite-allow-codegen-errors=1" }
+! { dg-skip-if "" { *-*-* } { "-O0" } { "" } }
+! { dg-additional-options "-ftree-loop-linear" }
SUBROUTINE FOO (K)
INTEGER I, J, K, A(5,5), B
@@ -25,5 +26,3 @@
A(1,1) = 0
IF (ANY(A.NE.0)) CALL ABORT
END
-
-! { dg-final { scan-tree-dump-times "code generation error" 1 "graphite" } }
Index: gcc/testsuite/gfortran.dg/graphite/pr29832.f90
===================================================================
--- gcc/testsuite/gfortran.dg/graphite/pr29832.f90 (revision 253394)
+++ gcc/testsuite/gfortran.dg/graphite/pr29832.f90 (working copy)
@@ -1,5 +1,6 @@
! { dg-do run }
-! { dg-options "-O2 -ftree-loop-linear" }
+! { dg-skip-if "" { *-*-* } { "-O0" } { "" } }
+! { dg-additional-options "-ftree-loop-linear" }
! { dg-additional-options "-fdump-tree-graphite-details --param graphite-allow-codegen-errors=1" { target ilp32 } }
! Program to test the scalarizer
Index: gcc/testsuite/gfortran.dg/graphite/pr42334-1.f
===================================================================
--- gcc/testsuite/gfortran.dg/graphite/pr42334-1.f (revision 253394)
+++ gcc/testsuite/gfortran.dg/graphite/pr42334-1.f (working copy)
@@ -1,4 +1,4 @@
-! { dg-options "-O2 -floop-interchange -fdump-tree-graphite-details --param graphite-allow-codegen-errors=1" }
+! { dg-options "-O2 -floop-interchange" }
subroutine linel(icmdl,stre,anisox)
real*8 stre(6),tkl(3,3),ekl(3,3),anisox(3,3,3,3)
@@ -14,5 +14,3 @@
enddo
stre(1)=tkl(1,1)
end
-
-! { dg-final { scan-tree-dump-times "code generation error" 1 "graphite" } }
Index: gcc/testsuite/gfortran.dg/graphite/pr42393-1.f90
===================================================================
--- gcc/testsuite/gfortran.dg/graphite/pr42393-1.f90 (revision 253394)
+++ gcc/testsuite/gfortran.dg/graphite/pr42393-1.f90 (working copy)
@@ -1,4 +1,4 @@
-! { dg-options "-O2 -fgraphite-identity -fno-loop-block -fno-loop-interchange -fno-loop-strip-mine -fdump-tree-graphite-details --param graphite-allow-codegen-errors=1" }
+! { dg-options "-O2 -fgraphite-identity -fno-loop-block -fno-loop-interchange -fno-loop-strip-mine" }
MODULE beta_gamma_psi
INTEGER, PARAMETER :: dp=KIND(0.0D0)
@@ -22,5 +22,3 @@ CONTAINS
fn_val = sum
END FUNCTION basym
END MODULE beta_gamma_psi
-
-! { dg-final { scan-tree-dump-times "code generation error" 1 "graphite" } }
Index: gcc/testsuite/gfortran.dg/graphite/pr42393.f90
===================================================================
--- gcc/testsuite/gfortran.dg/graphite/pr42393.f90 (revision 253394)
+++ gcc/testsuite/gfortran.dg/graphite/pr42393.f90 (working copy)
@@ -1,4 +1,4 @@
-! { dg-options "-O2 -fgraphite-identity -fno-loop-block -fno-loop-interchange -fno-loop-strip-mine -fdump-tree-graphite-details --param graphite-allow-codegen-errors=1" }
+! { dg-options "-O2 -fgraphite-identity -fno-loop-block -fno-loop-interchange -fno-loop-strip-mine" }
MODULE beta_gamma_psi
INTEGER, PARAMETER :: dp=KIND(0.0D0)
@@ -28,5 +28,3 @@ CONTAINS
fn_val = e0*t*u*sum
END FUNCTION basym
END MODULE beta_gamma_psi
-
-! { dg-final { scan-tree-dump-times "code generation error" 1 "graphite" } }
Index: gcc/testsuite/gfortran.dg/graphite/pr47019.f
===================================================================
--- gcc/testsuite/gfortran.dg/graphite/pr47019.f (revision 253394)
+++ gcc/testsuite/gfortran.dg/graphite/pr47019.f (working copy)
@@ -1,4 +1,4 @@
-! { dg-options "-O -ftree-pre -fgraphite-identity -fno-tree-copy-prop -fdump-tree-graphite-details --param graphite-allow-codegen-errors=1" }
+! { dg-options "-O -ftree-pre -fgraphite-identity -fno-tree-copy-prop" }
subroutine foo (ldmx,ldmy,v)
integer :: ldmx, ldmy, v, l, m
@@ -10,5 +10,3 @@
v(m,3,2) = m
end do
end
-
-! { dg-final { scan-tree-dump-times "code generation error" 1 "graphite" } }
Index: gcc/testsuite/gfortran.dg/graphite/run-id-3.f90
===================================================================
--- gcc/testsuite/gfortran.dg/graphite/run-id-3.f90 (revision 253394)
+++ gcc/testsuite/gfortran.dg/graphite/run-id-3.f90 (working copy)
@@ -1,5 +1,6 @@
! { dg-do run }
-! { dg-options "-ffrontend-optimize -floop-nest-optimize" }
+! { dg-skip-if "" { *-*-* } { "-O0" } { "" } }
+! { dg-additional-options "-ffrontend-optimize -floop-nest-optimize" }
! { dg-additional-options "-fdump-tree-graphite-details --param graphite-allow-codegen-errors=1" { target ilp32 } }
! PR 56872 - wrong front-end optimization with a single constructor.
! Original bug report by Rich Townsend.
Index: gcc/tree-into-ssa.c
===================================================================
--- gcc/tree-into-ssa.c (revision 253394)
+++ gcc/tree-into-ssa.c (working copy)
@@ -1226,6 +1226,8 @@ get_reaching_def (tree var)
if (currdef == NULL_TREE)
{
tree sym = DECL_P (var) ? var : SSA_NAME_VAR (var);
+ if (! sym)
+ sym = create_tmp_reg (TREE_TYPE (var));
currdef = get_or_create_ssa_default_def (cfun, sym);
}