From ab0e5308484abccb6c21d3a6593ab653a02784a2 Mon Sep 17 00:00:00 2001 From: Richard Biener Date: Fri, 22 Sep 2017 07:31:32 +0000 Subject: [PATCH] graphite-isl-ast-to-gimple.c (translate_pending_phi_nodes): Verify both BBs contain loop PHI nodes before dispatching to copy_loop_phi_args. 2017-09-21 Richard Biener * graphite-isl-ast-to-gimple.c (translate_pending_phi_nodes): Verify both BBs contain loop PHI nodes before dispatching to copy_loop_phi_args. (graphite_regenerate_ast_isl): Do not recompute dominators, do not verify three times. Restructure for clarity. * graphite-scop-detection.c (same_close_phi_node, remove_duplicate_close_phi, make_close_phi_nodes_unique, defined_in_loop_p, canonicalize_loop_closed_ssa, canonicalize_loop_closed_ssa_form): Simplify, remove excess checking and SSA rewrite, move to ... * graphite.c: ... here. Include ssa.h and tree-ssa-loop-manip.h. (graphite_initialize): Do not pass in ctx, do not reset the SCEV cache, compute only dominators. (graphite_transform_loops): Allocate ISL ctx after graphite_initialize. Call canonicalize_loop_closed_ssa_form. Maintain post-dominators only around build_scops. * sese.c (if_region_set_false_region): Make static. Free and recompute dominators. (move_sese_in_condition): Assert we don't get called with post-dominators computed. * sese.h (if_region_set_false_region): Remove. From-SVN: r253090 --- gcc/ChangeLog | 24 +++++ gcc/graphite-isl-ast-to-gimple.c | 57 +++++------- gcc/graphite-scop-detection.c | 183 --------------------------------------- gcc/graphite.c | 176 +++++++++++++++++++++++++++++++++++-- gcc/sese.c | 12 ++- gcc/sese.h | 1 - 6 files changed, 222 insertions(+), 231 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 75b309c..bcb5a2a 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,27 @@ +2017-09-22 Richard Biener + + * graphite-isl-ast-to-gimple.c (translate_pending_phi_nodes): + Verify both BBs contain loop PHI nodes before dispatching to + copy_loop_phi_args. + (graphite_regenerate_ast_isl): Do not recompute dominators, + do not verify three times. Restructure for clarity. + * graphite-scop-detection.c (same_close_phi_node, + remove_duplicate_close_phi, make_close_phi_nodes_unique, + defined_in_loop_p, canonicalize_loop_closed_ssa, + canonicalize_loop_closed_ssa_form): Simplify, remove excess + checking and SSA rewrite, move to ... + * graphite.c: ... here. Include ssa.h and tree-ssa-loop-manip.h. + (graphite_initialize): Do not pass in ctx, do not reset the + SCEV cache, compute only dominators. + (graphite_transform_loops): Allocate ISL ctx after + graphite_initialize. Call canonicalize_loop_closed_ssa_form. + Maintain post-dominators only around build_scops. + * sese.c (if_region_set_false_region): Make static. Free + and recompute dominators. + (move_sese_in_condition): Assert we don't get called with + post-dominators computed. + * sese.h (if_region_set_false_region): Remove. + 2017-09-22 Sergey Shalnov * config/i386/sse.md ("mov_internal"): Use diff --git a/gcc/graphite-isl-ast-to-gimple.c b/gcc/graphite-isl-ast-to-gimple.c index 87a1b06..1fb1bbd 100644 --- a/gcc/graphite-isl-ast-to-gimple.c +++ b/gcc/graphite-isl-ast-to-gimple.c @@ -2759,7 +2759,8 @@ translate_pending_phi_nodes () } auto_vec iv_map; - if (bb_contains_loop_phi_nodes (new_bb)) + if (bb_contains_loop_phi_nodes (new_bb) + && bb_contains_loop_phi_nodes (old_bb)) codegen_error = !copy_loop_phi_args (old_phi, ibp_old_bb, new_phi, ibp_new_bb, false); else if (bb_contains_loop_close_phi_nodes (new_bb)) @@ -2941,12 +2942,8 @@ graphite_regenerate_ast_isl (scop_p scop) print_isl_ast (dump_file, root_node); } - recompute_all_dominators (); - graphite_verify (); - if_region = move_sese_in_condition (region); region->if_region = if_region; - recompute_all_dominators (); loop_p context_loop = region->region.entry->src->loop_father; @@ -2960,45 +2957,28 @@ graphite_regenerate_ast_isl (scop_p scop) region->if_region->true_region->region.exit = single_succ_edge (bb); 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, + if_region->false_region->region.exit, + if_region->true_region->region.exit); + if (dump_file) + fprintf (dump_file, "[codegen] isl AST to Gimple succeeded.\n"); + + mark_virtual_operands_for_renaming (cfun); + update_ssa (TODO_update_ssa); + } + if (t.codegen_error_p ()) { if (dump_file) fprintf (dump_file, "codegen error: " "reverting back to the original code.\n"); set_ifsese_condition (if_region, integer_zero_node); - } - else - { - t.translate_pending_phi_nodes (); - if (!t.codegen_error_p ()) - { - sese_insert_phis_for_liveouts (region, - if_region->region->region.exit->src, - if_region->false_region->region.exit, - if_region->true_region->region.exit); - mark_virtual_operands_for_renaming (cfun); - update_ssa (TODO_update_ssa); - - - graphite_verify (); - scev_reset (); - recompute_all_dominators (); - graphite_verify (); - if (dump_file) - fprintf (dump_file, "[codegen] isl AST to Gimple succeeded.\n"); - } - else - { - if (dump_file) - fprintf (dump_file, "[codegen] unsuccessful in translating" - " pending phis, reverting back to the original code.\n"); - set_ifsese_condition (if_region, integer_zero_node); - } - } - - if (t.codegen_error_p ()) - { /* We registered new names, scrap that. */ if (need_ssa_update_p (cfun)) delete_update_ssa (); @@ -3017,6 +2997,9 @@ graphite_regenerate_ast_isl (scop_p scop) delete_loop (loop); } + graphite_verify (); + scev_reset (); + free (if_region->true_region); free (if_region->region); free (if_region); diff --git a/gcc/graphite-scop-detection.c b/gcc/graphite-scop-detection.c index 68e86ec..594cf89 100644 --- a/gcc/graphite-scop-detection.c +++ b/gcc/graphite-scop-detection.c @@ -268,187 +268,6 @@ trivially_empty_bb_p (basic_block bb) return true; } -/* Returns true when P1 and P2 are close phis with the same - argument. */ - -static inline bool -same_close_phi_node (gphi *p1, gphi *p2) -{ - return (types_compatible_p (TREE_TYPE (gimple_phi_result (p1)), - TREE_TYPE (gimple_phi_result (p2))) - && operand_equal_p (gimple_phi_arg_def (p1, 0), - gimple_phi_arg_def (p2, 0), 0)); -} - -static void make_close_phi_nodes_unique (basic_block bb); - -/* Remove the close phi node at GSI and replace its rhs with the rhs - of PHI. */ - -static void -remove_duplicate_close_phi (gphi *phi, gphi_iterator *gsi) -{ - gimple *use_stmt; - use_operand_p use_p; - imm_use_iterator imm_iter; - tree res = gimple_phi_result (phi); - tree def = gimple_phi_result (gsi->phi ()); - - gcc_assert (same_close_phi_node (phi, gsi->phi ())); - - FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def) - { - FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter) - SET_USE (use_p, res); - - update_stmt (use_stmt); - - /* It is possible that we just created a duplicate close-phi - for an already-processed containing loop. Check for this - case and clean it up. */ - if (gimple_code (use_stmt) == GIMPLE_PHI - && gimple_phi_num_args (use_stmt) == 1) - make_close_phi_nodes_unique (gimple_bb (use_stmt)); - } - - remove_phi_node (gsi, true); -} - -/* Removes all the close phi duplicates from BB. */ - -static void -make_close_phi_nodes_unique (basic_block bb) -{ - gphi_iterator psi; - - for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi)) - { - gphi_iterator gsi = psi; - gphi *phi = psi.phi (); - - /* At this point, PHI should be a close phi in normal form. */ - gcc_assert (gimple_phi_num_args (phi) == 1); - - /* Iterate over the next phis and remove duplicates. */ - gsi_next (&gsi); - while (!gsi_end_p (gsi)) - if (same_close_phi_node (phi, gsi.phi ())) - remove_duplicate_close_phi (phi, &gsi); - else - gsi_next (&gsi); - } -} - -/* Return true when NAME is defined in LOOP. */ - -static bool -defined_in_loop_p (tree name, loop_p loop) -{ - gcc_assert (TREE_CODE (name) == SSA_NAME); - return loop == loop_containing_stmt (SSA_NAME_DEF_STMT (name)); -} - -/* Transforms LOOP to the canonical loop closed SSA form. */ - -static void -canonicalize_loop_closed_ssa (loop_p loop) -{ - edge e = single_exit (loop); - basic_block bb; - - if (!e || (e->flags & EDGE_COMPLEX)) - return; - - bb = e->dest; - - if (single_pred_p (bb)) - { - e = split_block_after_labels (bb); - DEBUG_PRINT (dp << "Splitting bb_" << bb->index << ".\n"); - make_close_phi_nodes_unique (e->src); - } - else - { - gphi_iterator psi; - basic_block close = split_edge (e); - - e = single_succ_edge (close); - DEBUG_PRINT (dp << "Splitting edge (" << e->src->index << "," - << e->dest->index << ")\n"); - - for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi)) - { - gphi *phi = psi.phi (); - unsigned i; - - for (i = 0; i < gimple_phi_num_args (phi); i++) - if (gimple_phi_arg_edge (phi, i) == e) - { - tree res, arg = gimple_phi_arg_def (phi, i); - use_operand_p use_p; - gphi *close_phi; - - /* Only add close phi nodes for SSA_NAMEs defined in LOOP. */ - if (TREE_CODE (arg) != SSA_NAME - || !defined_in_loop_p (arg, loop)) - continue; - - close_phi = create_phi_node (NULL_TREE, close); - res = create_new_def_for (arg, close_phi, - gimple_phi_result_ptr (close_phi)); - add_phi_arg (close_phi, arg, - gimple_phi_arg_edge (close_phi, 0), - UNKNOWN_LOCATION); - use_p = gimple_phi_arg_imm_use_ptr (phi, i); - replace_exp (use_p, res); - update_stmt (phi); - } - } - - make_close_phi_nodes_unique (close); - } - - /* The code above does not properly handle changes in the post dominance - information (yet). */ - recompute_all_dominators (); -} - -/* Converts the current loop closed SSA form to a canonical form - expected by the Graphite code generation. - - The loop closed SSA form has the following invariant: a variable - defined in a loop that is used outside the loop appears only in the - phi nodes in the destination of the loop exit. These phi nodes are - called close phi nodes. - - The canonical loop closed SSA form contains the extra invariants: - - - when the loop contains only one exit, the close phi nodes contain - only one argument. That implies that the basic block that contains - the close phi nodes has only one predecessor, that is a basic block - in the loop. - - - the basic block containing the close phi nodes does not contain - other statements. - - - there exist only one phi node per definition in the loop. -*/ - -static void -canonicalize_loop_closed_ssa_form (void) -{ - checking_verify_loop_closed_ssa (true); - - loop_p loop; - FOR_EACH_LOOP (loop, 0) - canonicalize_loop_closed_ssa (loop); - - rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa); - update_ssa (TODO_update_ssa); - - checking_verify_loop_closed_ssa (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. */ @@ -2038,8 +1857,6 @@ build_scops (vec *scops) if (dump_file) dp.set_dump_file (dump_file); - canonicalize_loop_closed_ssa_form (); - /* ??? We walk the loop tree assuming loop->next is ordered. This is not so but we'd be free to order it here. */ scop_detection sb; diff --git a/gcc/graphite.c b/gcc/graphite.c index d8777f0..bce3240 100644 --- a/gcc/graphite.c +++ b/gcc/graphite.c @@ -43,6 +43,7 @@ along with GCC; see the file COPYING3. If not see #include "cfghooks.h" #include "tree.h" #include "gimple.h" +#include "ssa.h" #include "fold-const.h" #include "gimple-iterator.h" #include "tree-cfg.h" @@ -53,6 +54,7 @@ along with GCC; see the file COPYING3. If not see #include "tree-parloops.h" #include "tree-cfgcleanup.h" #include "tree-vectorizer.h" +#include "tree-ssa-loop-manip.h" #include "graphite.h" /* Print global statistics to FILE. */ @@ -213,7 +215,7 @@ print_graphite_statistics (FILE* file, vec scops) /* Initialize graphite: when there are no loops returns false. */ static bool -graphite_initialize (isl_ctx *ctx) +graphite_initialize (void) { int min_loops = PARAM_VALUE (PARAM_GRAPHITE_MIN_LOOPS_PER_FUNCTION); int max_bbs = PARAM_VALUE (PARAM_GRAPHITE_MAX_BBS_PER_FUNCTION); @@ -240,12 +242,10 @@ graphite_initialize (isl_ctx *ctx) print_global_statistics (dump_file); } - isl_ctx_free (ctx); return false; } - scev_reset (); - recompute_all_dominators (); + calculate_dominance_info (CDI_DOMINATORS); initialize_original_copy_tables (); if (dump_file && dump_flags) @@ -263,7 +263,6 @@ graphite_initialize (isl_ctx *ctx) static void graphite_finalize (bool need_cfg_cleanup_p) { - free_dominance_info (CDI_POST_DOMINATORS); if (need_cfg_cleanup_p) { free_dominance_info (CDI_DOMINATORS); @@ -294,6 +293,162 @@ free_scops (vec scops) scops.release (); } +/* Returns true when P1 and P2 are close phis with the same + argument. */ + +static inline bool +same_close_phi_node (gphi *p1, gphi *p2) +{ + return (types_compatible_p (TREE_TYPE (gimple_phi_result (p1)), + TREE_TYPE (gimple_phi_result (p2))) + && operand_equal_p (gimple_phi_arg_def (p1, 0), + gimple_phi_arg_def (p2, 0), 0)); +} + +static void make_close_phi_nodes_unique (basic_block bb); + +/* Remove the close phi node at GSI and replace its rhs with the rhs + of PHI. */ + +static void +remove_duplicate_close_phi (gphi *phi, gphi_iterator *gsi) +{ + gimple *use_stmt; + use_operand_p use_p; + imm_use_iterator imm_iter; + tree res = gimple_phi_result (phi); + tree def = gimple_phi_result (gsi->phi ()); + + gcc_assert (same_close_phi_node (phi, gsi->phi ())); + + FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def) + { + FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter) + SET_USE (use_p, res); + + update_stmt (use_stmt); + + /* It is possible that we just created a duplicate close-phi + for an already-processed containing loop. Check for this + case and clean it up. */ + if (gimple_code (use_stmt) == GIMPLE_PHI + && gimple_phi_num_args (use_stmt) == 1) + make_close_phi_nodes_unique (gimple_bb (use_stmt)); + } + + remove_phi_node (gsi, true); +} + +/* Removes all the close phi duplicates from BB. */ + +static void +make_close_phi_nodes_unique (basic_block bb) +{ + gphi_iterator psi; + + for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi)) + { + gphi_iterator gsi = psi; + gphi *phi = psi.phi (); + + /* At this point, PHI should be a close phi in normal form. */ + gcc_assert (gimple_phi_num_args (phi) == 1); + + /* Iterate over the next phis and remove duplicates. */ + gsi_next (&gsi); + while (!gsi_end_p (gsi)) + if (same_close_phi_node (phi, gsi.phi ())) + remove_duplicate_close_phi (phi, &gsi); + else + gsi_next (&gsi); + } +} + +/* Return true when NAME is defined in LOOP. */ + +static bool +defined_in_loop_p (tree name, loop_p loop) +{ + gcc_assert (TREE_CODE (name) == SSA_NAME); + return loop == loop_containing_stmt (SSA_NAME_DEF_STMT (name)); +} + +/* Transforms LOOP to the canonical loop closed SSA form. */ + +static void +canonicalize_loop_closed_ssa (loop_p loop) +{ + edge e = single_exit (loop); + basic_block bb; + + if (!e || (e->flags & EDGE_COMPLEX)) + return; + + bb = e->dest; + + if (single_pred_p (bb)) + { + e = split_block_after_labels (bb); + make_close_phi_nodes_unique (e->src); + } + else + { + gphi_iterator psi; + basic_block close = split_edge (e); + e = single_succ_edge (close); + for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi)) + { + gphi *phi = psi.phi (); + use_operand_p use_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e); + tree arg = USE_FROM_PTR (use_p); + + /* Only add close phi nodes for SSA_NAMEs defined in LOOP. */ + if (TREE_CODE (arg) != SSA_NAME + || !defined_in_loop_p (arg, loop)) + continue; + + tree res = copy_ssa_name (arg); + gphi *close_phi = create_phi_node (res, close); + add_phi_arg (close_phi, arg, gimple_phi_arg_edge (close_phi, 0), + UNKNOWN_LOCATION); + SET_USE (use_p, res); + } + + make_close_phi_nodes_unique (close); + } +} + +/* Converts the current loop closed SSA form to a canonical form + expected by the Graphite code generation. + + The loop closed SSA form has the following invariant: a variable + defined in a loop that is used outside the loop appears only in the + phi nodes in the destination of the loop exit. These phi nodes are + called close phi nodes. + + The canonical loop closed SSA form contains the extra invariants: + + - when the loop contains only one exit, the close phi nodes contain + only one argument. That implies that the basic block that contains + the close phi nodes has only one predecessor, that is a basic block + in the loop. + + - the basic block containing the close phi nodes does not contain + other statements. + + - there exist only one phi node per definition in the loop. +*/ + +static void +canonicalize_loop_closed_ssa_form (void) +{ + loop_p loop; + FOR_EACH_LOOP (loop, 0) + canonicalize_loop_closed_ssa (loop); + + checking_verify_loop_closed_ssa (true); +} + isl_ctx *the_isl_ctx; /* Perform a set of linear transforms on the loops of the current @@ -313,13 +468,18 @@ graphite_transform_loops (void) if (parallelized_function_p (cfun->decl)) return; - ctx = isl_ctx_alloc (); - isl_options_set_on_error (ctx, ISL_ON_ERROR_ABORT); - if (!graphite_initialize (ctx)) + if (!graphite_initialize ()) return; + ctx = isl_ctx_alloc (); + isl_options_set_on_error (ctx, ISL_ON_ERROR_ABORT); the_isl_ctx = ctx; + + canonicalize_loop_closed_ssa_form (); + + calculate_dominance_info (CDI_POST_DOMINATORS); build_scops (&scops); + free_dominance_info (CDI_POST_DOMINATORS); if (dump_file && (dump_flags & TDF_DETAILS)) { diff --git a/gcc/sese.c b/gcc/sese.c index 3279ead..4be7d34 100644 --- a/gcc/sese.c +++ b/gcc/sese.c @@ -335,9 +335,11 @@ get_false_edge_from_guard_bb (basic_block bb) /* Sets the false region of an IF_REGION to REGION. */ -void +static void if_region_set_false_region (ifsese if_region, sese_info_p region) { + free_dominance_info (CDI_DOMINATORS); + basic_block condition = if_region_get_condition_block (if_region); edge false_edge = get_false_edge_from_guard_bb (condition); basic_block dummy = false_edge->dest; @@ -348,6 +350,8 @@ if_region_set_false_region (ifsese if_region, sese_info_p region) hashval_t hash = htab_hash_pointer (exit_region); loop_exit **slot = current_loops->exits->find_slot_with_hash (exit_region, hash, NO_INSERT); + bool latch_p + = exit_region->dest->loop_father->latch == exit_region->src; entry_region->flags = false_edge->flags; false_edge->flags = exit_region->flags; @@ -359,7 +363,6 @@ if_region_set_false_region (ifsese if_region, sese_info_p region) delete_basic_block (dummy); exit_region->flags = EDGE_FALLTHRU; - recompute_all_dominators (); region->region.exit = false_edge; @@ -381,6 +384,10 @@ if_region_set_false_region (ifsese if_region, sese_info_p region) *slot = loop_exit; false_edge->src->loop_father->exits->next = loop_exit; } + if (latch_p) + exit_region->dest->loop_father->latch = before_region; + + calculate_dominance_info (CDI_DOMINATORS); } /* Creates an IFSESE with CONDITION on edge ENTRY. */ @@ -429,6 +436,7 @@ create_if_region_on_edge (edge entry, tree condition) ifsese move_sese_in_condition (sese_info_p region) { + gcc_assert (! dom_info_available_p (cfun, CDI_POST_DOMINATORS)); basic_block pred_block = split_edge (region->region.entry); ifsese if_region; diff --git a/gcc/sese.h b/gcc/sese.h index e51f1b4..025e733 100644 --- a/gcc/sese.h +++ b/gcc/sese.h @@ -233,7 +233,6 @@ typedef struct ifsese_s { sese_info_p false_region; } *ifsese; -extern void if_region_set_false_region (ifsese, sese_info_p); extern ifsese move_sese_in_condition (sese_info_p); extern void set_ifsese_condition (ifsese, tree); extern edge get_true_edge_from_guard_bb (basic_block); -- 2.7.4