[PATCH][GRAPHITE] Rewrite PHI handling in code-gen
Richard Biener
rguenther@suse.de
Thu Oct 5 11:43:00 GMT 2017
On Wed, 4 Oct 2017, Richard Biener wrote:
>
> 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.
So I messed up the testsuite update and it turns out all code-gen
issues are fixed in all graphite.exp testsuites. Yay.
> 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.
The CE was on purpose, std=legacy brings it back, now it seems to
miscompare.
> 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?
Thus the following updated patch (only the testsuite part changed).
Bootstrapped with -fgraphite-identity -floop-nest-optimize and tested
on x86_64-unknown-linux-gnu.
Ok?
There are two parts worth working on after this - one is creating
a versioning condition to fend off alias-set compute fails, the
other one is working on the proximity constraints.
After this is in I'll extract testcases for the remaining
code-generation issues in SPEC.
Thanks,
Richard.
2017-10-05 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/id-17.f: Likewise.
* gfortran.dg/graphite/id-19.f: Likewise.
* gfortran.dg/graphite/run-id-2.f90: Likewise.
* gfortran.dg/graphite/pr42326-1.f90: Likewise.
* gfortran.dg/graphite/pr42326.f90: Likewise.
* gfortran.dg/graphite/pr68550-2.f90: Likewise.
* gfortran.dg/graphite/pr29581.f90: Likewise. No longer expect
a code generation error.
* gfortran.dg/graphite/run-id-3.f90: Likewise.
* gfortran.dg/graphite/pr29832.f90: Likewise.
Index: gcc/graphite-isl-ast-to-gimple.c
===================================================================
--- gcc/graphite-isl-ast-to-gimple.c (revision 253437)
+++ 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 253437)
+++ 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 253437)
+++ 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 253437)
+++ 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 253437)
+++ 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 253437)
+++ 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 253437)
+++ 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 253437)
+++ 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 253437)
+++ 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 253437)
+++ 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 253437)
+++ 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 253437)
+++ 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 -fdump-tree-graphite-all" } */
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 253437)
+++ 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/id-17.f
===================================================================
--- gcc/testsuite/gfortran.dg/graphite/id-17.f (revision 253437)
+++ gcc/testsuite/gfortran.dg/graphite/id-17.f (working copy)
@@ -1,4 +1,3 @@
-! { dg-additional-options "-fdump-tree-graphite-details --param graphite-allow-codegen-errors=1" { target ilp32 } }
SUBROUTINE SPECTOP(Dr,N)
DIMENSION d1(0:32,0:32) , Dr(0:32,0:32) , x(0:32)
DO k = 0 , N
@@ -15,4 +14,3 @@
ENDDO
ENDDO
END
-! { dg-final { scan-tree-dump-times "code generation error" 1 "graphite" { target ilp32 } } }
Index: gcc/testsuite/gfortran.dg/graphite/id-19.f
===================================================================
--- gcc/testsuite/gfortran.dg/graphite/id-19.f (revision 253437)
+++ gcc/testsuite/gfortran.dg/graphite/id-19.f (working copy)
@@ -1,4 +1,3 @@
-! { dg-additional-options "-fdump-tree-graphite-details --param graphite-allow-codegen-errors=1" { target ilp32 } }
SUBROUTINE ECCODR(FPQR)
DIMENSION FPQR(25,25,25)
INTEGER P,Q,R
@@ -14,4 +13,3 @@
140 QM2= QM2+TWO
150 PM2= PM2+TWO
END
-! { dg-final { scan-tree-dump-times "code generation error" 1 "graphite" { target ilp32 } } }
Index: gcc/testsuite/gfortran.dg/graphite/interchange-1.f
===================================================================
--- gcc/testsuite/gfortran.dg/graphite/interchange-1.f (revision 253437)
+++ 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 253437)
+++ 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 253437)
+++ gcc/testsuite/gfortran.dg/graphite/pr29832.f90 (working copy)
@@ -1,6 +1,6 @@
! { dg-do run }
-! { dg-options "-O2 -ftree-loop-linear" }
-! { dg-additional-options "-fdump-tree-graphite-details --param graphite-allow-codegen-errors=1" { target ilp32 } }
+! { dg-skip-if "" { *-*-* } { "-O0" } { "" } }
+! { dg-additional-options "-ftree-loop-linear" }
! Program to test the scalarizer
program testarray
@@ -24,5 +24,3 @@ program testarray
if (b(4, n) .ne. (6 - n)) call abort
end do
end program
-
-! { dg-final { scan-tree-dump-times "code generation error" 1 "graphite" { target ilp32 } } }
Index: gcc/testsuite/gfortran.dg/graphite/pr42326-1.f90
===================================================================
--- gcc/testsuite/gfortran.dg/graphite/pr42326-1.f90 (revision 253437)
+++ gcc/testsuite/gfortran.dg/graphite/pr42326-1.f90 (working copy)
@@ -1,7 +1,7 @@
! { dg-do compile { target i?86-*-* x86_64-*-* } }
! { dg-require-effective-target ilp32 }
! { dg-require-effective-target sse2 }
-! { dg-options "-O2 -floop-parallelize-all -fprefetch-loop-arrays -msse2 -fdump-tree-graphite-details --param graphite-allow-codegen-errors=1" }
+! { dg-options "-O2 -floop-parallelize-all -fprefetch-loop-arrays -msse2" }
subroutine phasad(t,i,ium)
implicit none
@@ -16,5 +16,3 @@ subroutine phasad(t,i,ium)
enddo
return
end subroutine phasad
-
-! { dg-final { scan-tree-dump-times "code generation error" 1 "graphite" } }
Index: gcc/testsuite/gfortran.dg/graphite/pr42326.f90
===================================================================
--- gcc/testsuite/gfortran.dg/graphite/pr42326.f90 (revision 253437)
+++ gcc/testsuite/gfortran.dg/graphite/pr42326.f90 (working copy)
@@ -1,7 +1,7 @@
! { dg-do compile { target i?86-*-* x86_64-*-* } }
! { dg-require-effective-target ilp32 }
! { dg-require-effective-target sse2 }
-! { dg-options "-O2 -floop-strip-mine -fprefetch-loop-arrays -msse2 -fdump-tree-graphite-details --param graphite-allow-codegen-errors=1" }
+! { dg-options "-O2 -floop-strip-mine -fprefetch-loop-arrays -msse2" }
subroutine blts ( ldmx, ldmy, v, tmp1, i, j, k)
implicit none
@@ -33,5 +33,3 @@ subroutine phasad(t,i,ium)
enddo
return
end subroutine phasad
-
-! { dg-final { scan-tree-dump-times "code generation error" 1 "graphite" } }
Index: gcc/testsuite/gfortran.dg/graphite/pr42334-1.f
===================================================================
--- gcc/testsuite/gfortran.dg/graphite/pr42334-1.f (revision 253437)
+++ 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 253437)
+++ 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 253437)
+++ 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 253437)
+++ 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/pr68550-2.f90
===================================================================
--- gcc/testsuite/gfortran.dg/graphite/pr68550-2.f90 (revision 253437)
+++ gcc/testsuite/gfortran.dg/graphite/pr68550-2.f90 (working copy)
@@ -1,6 +1,5 @@
! { dg-do compile }
! { dg-options "-floop-nest-optimize -fcheck=bounds -O1" }
-! { dg-additional-options "-fdump-tree-graphite-details --param graphite-allow-codegen-errors=1" { target ilp32 } }
SUBROUTINE PD2VAL(RES,NDERIV,TG1,TG2,C0)
INTEGER, PARAMETER :: dp=8
@@ -13,5 +12,3 @@ SUBROUTINE PD2VAL(RES,NDERIV,TG1,TG2,C0)
RES(K)=RES(K)+DOT_PRODUCT(T1(0:3),C0(96:99,K))*T2(10)
ENDDO
END SUBROUTINE PD2VAL
-
-! { dg-final { scan-tree-dump-times "code generation error" 1 "graphite" { target ilp32 } } }
Index: gcc/testsuite/gfortran.dg/graphite/run-id-2.f90
===================================================================
--- gcc/testsuite/gfortran.dg/graphite/run-id-2.f90 (revision 253437)
+++ gcc/testsuite/gfortran.dg/graphite/run-id-2.f90 (working copy)
@@ -1,4 +1,3 @@
-! { dg-additional-options "-fdump-tree-graphite-details --param graphite-allow-codegen-errors=1" { target ilp32 } }
IMPLICIT NONE
INTEGER, PARAMETER :: dp=KIND(0.0D0)
REAL(KIND=dp) :: res
@@ -65,4 +64,3 @@ CONTAINS
END FUNCTION exp_radius_very_extended
END
-! { dg-final { scan-tree-dump-times "code generation error" 1 "graphite" { target ilp32 } } }
Index: gcc/testsuite/gfortran.dg/graphite/run-id-3.f90
===================================================================
--- gcc/testsuite/gfortran.dg/graphite/run-id-3.f90 (revision 253437)
+++ gcc/testsuite/gfortran.dg/graphite/run-id-3.f90 (working copy)
@@ -1,6 +1,6 @@
! { dg-do run }
-! { dg-options "-ffrontend-optimize -floop-nest-optimize" }
-! { dg-additional-options "-fdump-tree-graphite-details --param graphite-allow-codegen-errors=1" { target ilp32 } }
+! { dg-skip-if "" { *-*-* } { "-O0" } { "" } }
+! { dg-additional-options "-ffrontend-optimize -floop-nest-optimize" }
! PR 56872 - wrong front-end optimization with a single constructor.
! Original bug report by Rich Townsend.
integer :: k
@@ -11,4 +11,3 @@
res = SUM([(s**(REAL(k-1)/REAL(m-1)),k=1,m)])
if (abs(res - 5.84732246) > 1e-6) call abort
end
-! { dg-final { scan-tree-dump-times "code generation error" 1 "graphite" { target ilp32 } } }
Index: gcc/tree-into-ssa.c
===================================================================
--- gcc/tree-into-ssa.c (revision 253437)
+++ 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);
}
More information about the Gcc-patches
mailing list