[PATCH][GRAPHITE] Strip down dominator recompute, checking and friends

[Richard Biener <rguenther at suse dot de>]

The following is a quick attempt at reducing pass overhead.  The
main part is maintaining post-dominators only during scop detection
and not recomputing / verifying everything many many times for no
good reason.

Somehow this means I ran into a latent bug where ISL split
a loop into two, not mixing loop and condition PHIs and thus
confusing translate_pending_phi_nodes.

I moved lc SSA "canonicalization" and cleaned it up a bit.  I think
it would be useful to factor the requirements into the general
version.

Bootstrapped on x86_64-unknown-linux-gnu, testing in progress.

The graphite testsuites and SPEC CPU 2006 don't show any new
issues.  I'll apply this when testing finished.

The immediate plan is to look at SCOP detection and make it
more intelligently look at loop->next for the breath build
given that the loop->next chain is not necessarily ordered
in the way it thinks.

Thanks,
Richard.

2017-09-21  Richard Biener  <rguenther@suse.de>

	* 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.

Index: gcc/graphite-isl-ast-to-gimple.c
===================================================================
--- gcc/graphite-isl-ast-to-gimple.c	(revision 253064)
+++ gcc/graphite-isl-ast-to-gimple.c	(working copy)
@@ -2759,7 +2759,8 @@ translate_pending_phi_nodes ()
 	}
 
       auto_vec <tree, 1> 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);
Index: gcc/graphite-scop-detection.c
===================================================================
--- gcc/graphite-scop-detection.c	(revision 253064)
+++ gcc/graphite-scop-detection.c	(working copy)
@@ -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<scop_p> *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;
Index: gcc/graphite.c
===================================================================
--- gcc/graphite.c	(revision 253064)
+++ gcc/graphite.c	(working copy)
@@ -43,6 +43,7 @@ along with GCC; see the file COPYING3.
 #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.
 #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, v
 /* 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<scop_p> 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))
     {
Index: gcc/sese.c
===================================================================
--- gcc/sese.c	(revision 253064)
+++ gcc/sese.c	(working copy)
@@ -335,9 +335,11 @@ get_false_edge_from_guard_bb (basic_bloc
 
 /* 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_re
   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_re
   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_re
       *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, tr
 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;
 
Index: gcc/sese.h
===================================================================
--- gcc/sese.h	(revision 253064)
+++ gcc/sese.h	(working copy)
@@ -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);