[RFA] Minor cleanup to VRP/EVRP handling of deferred edge/switch optimization

Message ID 6aacd581-5c9f-fb7b-3939-67be559d1c00@redhat.com
State New
Headers show
Series
  • [RFA] Minor cleanup to VRP/EVRP handling of deferred edge/switch optimization
Related show

Commit Message

Jeff Law Sept. 17, 2018, 2:50 p.m.
This is a relatively minor cleanup that I should have caught last cycle,
but somehow missed.

We have two structures TO_REMOVE_EDGES and TO_UPDATE_SWITCH_STMTS which
are used by the VRP/EVRP code to record edges to remove and switch
statements that need updating.

They are currently implemented as globals within tree-vrp.c with an
appropriate extern within tree-vrp.h.

The code to walk those vectors was only implemented in VRP, but we can
(and do) add to those vectors within EVRP.   So EVRP would detect
certain edges as dead or switches that were needed simplification, but
they were left as-is because EVRP never walked the vectors to do the
necessary cleanup.

This change pushes the vectors into the vr_values structure.  They're
initialized in the ctor and we verify they're properly cleaned up in the
dtor.  This obviously avoids the global object carrying state, but also
catches cases where we record that an optimization was possible but
failed to update the IL appropriately.

As a side effect, we don't need to bother with initializing and wiping
EDGE_IGNORE for jump threading in VRP.  We just mark the appropriate
edges at the same time we put them in TO_REMOVE_EDGES within vr_values.

vrp113.c is an example of where EVRP detected optimizations should be
possible, but failed to update the IL.  Given the test really wanted to
check VRP's behavior, I've disabled EVRP for that test.

Bootstrapped and regression tested on x86_64-linux-gnu.

OK for the trunk?

Jeff
* gimple-ssa-evrp.c (evrp_dom_walker::cleanup): Call
	vr_values::cleanup_edges_and_switches.
	* tree-vrp.c (to_remove_edges, to_update_switch_stmts): Moved into
	vr_values class.
	(identify_jump_threads): Remove EDGE_IGNORE handling.
	(execute_vrp): Move handling of to_remove_edges and
	to_update_switch_stmts into vr_values class member functions.
	* tree-vrp.h (switch_update, to_remove_edges): Remove declarations.
	(to_update_switch_stmts): Likewise.
	* vr-values.c: Include cfghooks.h. 
	(vr_values::vr_values): Initialize to_remove_edges and
	to_update_switch_stmts.
	(vr_values::~vr_values): Verify to_remove_edges and
	to_update_switch_stmts are empty.
	(vr_values::simplify_switch_using_ranges): Set EDGE_IGNORE as needed.
	(vr_values::cleanup_edges_and_switches): New member function.
	* vr-values.h (vr_values): Add cleanup_edges_and_switches member
	function.  Add new data members.

	* gcc.dg/tree-ssa/vrp113.c: Disable EVRP.

Comments

Richard Biener Sept. 20, 2018, 12:51 p.m. | #1
On Mon, Sep 17, 2018 at 4:50 PM Jeff Law <law@redhat.com> wrote:
>

> This is a relatively minor cleanup that I should have caught last cycle,

> but somehow missed.

>

> We have two structures TO_REMOVE_EDGES and TO_UPDATE_SWITCH_STMTS which

> are used by the VRP/EVRP code to record edges to remove and switch

> statements that need updating.

>

> They are currently implemented as globals within tree-vrp.c with an

> appropriate extern within tree-vrp.h.

>

> The code to walk those vectors was only implemented in VRP, but we can

> (and do) add to those vectors within EVRP.   So EVRP would detect

> certain edges as dead or switches that were needed simplification, but

> they were left as-is because EVRP never walked the vectors to do the

> necessary cleanup.

>

> This change pushes the vectors into the vr_values structure.  They're

> initialized in the ctor and we verify they're properly cleaned up in the

> dtor.  This obviously avoids the global object carrying state, but also

> catches cases where we record that an optimization was possible but

> failed to update the IL appropriately.

>

> As a side effect, we don't need to bother with initializing and wiping

> EDGE_IGNORE for jump threading in VRP.  We just mark the appropriate

> edges at the same time we put them in TO_REMOVE_EDGES within vr_values.

>

> vrp113.c is an example of where EVRP detected optimizations should be

> possible, but failed to update the IL.  Given the test really wanted to

> check VRP's behavior, I've disabled EVRP for that test.

>

> Bootstrapped and regression tested on x86_64-linux-gnu.

>

> OK for the trunk?


OK.  Maybe you can duplicate vrp113.c to also have a EVRP testing variant
of this functionality?

Thanks,
Richard.

> Jeff

>
Jeff Law Sept. 20, 2018, 2:41 p.m. | #2
On 9/20/18 6:51 AM, Richard Biener wrote:
> On Mon, Sep 17, 2018 at 4:50 PM Jeff Law <law@redhat.com> wrote:

>>

>> This is a relatively minor cleanup that I should have caught last cycle,

>> but somehow missed.

>>

>> We have two structures TO_REMOVE_EDGES and TO_UPDATE_SWITCH_STMTS which

>> are used by the VRP/EVRP code to record edges to remove and switch

>> statements that need updating.

>>

>> They are currently implemented as globals within tree-vrp.c with an

>> appropriate extern within tree-vrp.h.

>>

>> The code to walk those vectors was only implemented in VRP, but we can

>> (and do) add to those vectors within EVRP.   So EVRP would detect

>> certain edges as dead or switches that were needed simplification, but

>> they were left as-is because EVRP never walked the vectors to do the

>> necessary cleanup.

>>

>> This change pushes the vectors into the vr_values structure.  They're

>> initialized in the ctor and we verify they're properly cleaned up in the

>> dtor.  This obviously avoids the global object carrying state, but also

>> catches cases where we record that an optimization was possible but

>> failed to update the IL appropriately.

>>

>> As a side effect, we don't need to bother with initializing and wiping

>> EDGE_IGNORE for jump threading in VRP.  We just mark the appropriate

>> edges at the same time we put them in TO_REMOVE_EDGES within vr_values.

>>

>> vrp113.c is an example of where EVRP detected optimizations should be

>> possible, but failed to update the IL.  Given the test really wanted to

>> check VRP's behavior, I've disabled EVRP for that test.

>>

>> Bootstrapped and regression tested on x86_64-linux-gnu.

>>

>> OK for the trunk?

> 

> OK.  Maybe you can duplicate vrp113.c to also have a EVRP testing variant

> of this functionality?

Sure.  I'd pondered doing something like that anyway.  We can verify
that EVRP collapses the test and that we do not trigger the "did you
fail to clean up properly" assert.

jeff

Patch

diff --git a/gcc/gimple-ssa-evrp.c b/gcc/gimple-ssa-evrp.c
index b9a054fd2ee..50e8adc1aad 100644
--- a/gcc/gimple-ssa-evrp.c
+++ b/gcc/gimple-ssa-evrp.c
@@ -287,6 +287,8 @@  evrp_dom_walker::cleanup (void)
       gimple *stmt = stmts_to_fixup.pop ();
       fixup_noreturn_call (stmt);
     }
+
+  evrp_folder.vr_values->cleanup_edges_and_switches ();
 }
 
 /* Main entry point for the early vrp pass which is a simplified non-iterative
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp113.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp113.c
index 5069fdfa784..ab8d91e0f10 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/vrp113.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp113.c
@@ -1,5 +1,5 @@ 
 /* { dg-do compile } */
-/* { dg-options "-O2 -fdump-tree-vrp1" } */
+/* { dg-options "-O2 -fdump-tree-vrp1 -fdisable-tree-evrp" } */
 
 int f(int a) {
     switch (a & 1) {
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index 622ccbc2df7..ab222a385f6 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -121,10 +121,6 @@  static bitmap need_assert_for;
    ASSERT_EXPRs for SSA name N_I should be inserted.  */
 static assert_locus **asserts_for;
 
-vec<edge> to_remove_edges;
-vec<switch_update> to_update_switch_stmts;
-
-
 /* Return the maximum value for TYPE.  */
 
 tree
@@ -6404,9 +6400,6 @@  vrp_dom_walker::after_dom_children (basic_block bb)
 static void
 identify_jump_threads (class vr_values *vr_values)
 {
-  int i;
-  edge e;
-
   /* Ugh.  When substituting values earlier in this pass we can
      wipe the dominance information.  So rebuild the dominator
      information as we need it within the jump threading code.  */
@@ -6419,11 +6412,6 @@  identify_jump_threads (class vr_values *vr_values)
      recompute it.  */
   mark_dfs_back_edges ();
 
-  /* Do not thread across edges we are about to remove.  Just marking
-     them as EDGE_IGNORE will do.  */
-  FOR_EACH_VEC_ELT (to_remove_edges, i, e)
-    e->flags |= EDGE_IGNORE;
-
   /* Allocate our unwinder stack to unwind any temporary equivalences
      that might be recorded.  */
   const_and_copies *equiv_stack = new const_and_copies ();
@@ -6437,10 +6425,6 @@  identify_jump_threads (class vr_values *vr_values)
   walker.vr_values = vr_values;
   walker.walk (cfun->cfg->x_entry_block_ptr);
 
-  /* Clear EDGE_IGNORE.  */
-  FOR_EACH_VEC_ELT (to_remove_edges, i, e)
-    e->flags &= ~EDGE_IGNORE;
-
   /* We do not actually update the CFG or SSA graphs at this point as
      ASSERT_EXPRs are still in the IL and cfg cleanup code does not yet
      handle ASSERT_EXPRs gracefully.  */
@@ -6557,9 +6541,6 @@  vrp_prop::vrp_finalize (bool warn_array_bounds_p)
 static unsigned int
 execute_vrp (bool warn_array_bounds_p)
 {
-  int i;
-  edge e;
-  switch_update *su;
 
   loop_optimizer_init (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS);
   rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
@@ -6570,8 +6551,6 @@  execute_vrp (bool warn_array_bounds_p)
      EDGE_DFS_BACK.  */
   insert_range_assertions ();
 
-  to_remove_edges.create (10);
-  to_update_switch_stmts.create (5);
   threadedge_initialize_values ();
 
   /* For visiting PHI nodes we need EDGE_DFS_BACK computed.  */
@@ -6623,35 +6602,7 @@  execute_vrp (bool warn_array_bounds_p)
      processing by the pass manager.  */
   thread_through_all_blocks (false);
 
-  /* Remove dead edges from SWITCH_EXPR optimization.  This leaves the
-     CFG in a broken state and requires a cfg_cleanup run.  */
-  FOR_EACH_VEC_ELT (to_remove_edges, i, e)
-    remove_edge (e);
-  /* Update SWITCH_EXPR case label vector.  */
-  FOR_EACH_VEC_ELT (to_update_switch_stmts, i, su)
-    {
-      size_t j;
-      size_t n = TREE_VEC_LENGTH (su->vec);
-      tree label;
-      gimple_switch_set_num_labels (su->stmt, n);
-      for (j = 0; j < n; j++)
-	gimple_switch_set_label (su->stmt, j, TREE_VEC_ELT (su->vec, j));
-      /* As we may have replaced the default label with a regular one
-	 make sure to make it a real default label again.  This ensures
-	 optimal expansion.  */
-      label = gimple_switch_label (su->stmt, 0);
-      CASE_LOW (label) = NULL_TREE;
-      CASE_HIGH (label) = NULL_TREE;
-    }
-
-  if (to_remove_edges.length () > 0)
-    {
-      free_dominance_info (CDI_DOMINATORS);
-      loops_state_set (LOOPS_NEED_FIXUP);
-    }
-
-  to_remove_edges.release ();
-  to_update_switch_stmts.release ();
+  vrp_prop.vr_values.cleanup_edges_and_switches ();
   threadedge_finalize_values ();
 
   scev_finalize ();
diff --git a/gcc/tree-vrp.h b/gcc/tree-vrp.h
index 2f661613dfc..655cf055f0a 100644
--- a/gcc/tree-vrp.h
+++ b/gcc/tree-vrp.h
@@ -122,13 +122,4 @@  extern int value_inside_range (tree, tree, tree);
 extern tree get_single_symbol (tree, bool *, tree *);
 extern void maybe_set_nonzero_bits (edge, tree);
 extern value_range_type determine_value_range (tree, wide_int *, wide_int *);
-
-struct switch_update {
-  gswitch *stmt;
-  tree vec;
-};
-
-extern vec<edge> to_remove_edges;
-extern vec<switch_update> to_update_switch_stmts;
-
 #endif /* GCC_TREE_VRP_H */
diff --git a/gcc/vr-values.c b/gcc/vr-values.c
index 11df1023b6e..e28e259a8b1 100644
--- a/gcc/vr-values.c
+++ b/gcc/vr-values.c
@@ -47,6 +47,7 @@  along with GCC; see the file COPYING3.  If not see
 #include "alloc-pool.h"
 #include "attribs.h"
 #include "vr-values.h"
+#include "cfghooks.h"
 
 /* Set value range VR to a non-negative range of type TYPE.  */
 
@@ -1918,6 +1919,8 @@  vr_values::vr_values () : vrp_value_range_pool ("Tree VRP value ranges")
   vr_value = XCNEWVEC (value_range *, num_vr_values);
   vr_phi_edge_counts = XCNEWVEC (int, num_ssa_names);
   bitmap_obstack_initialize (&vrp_equiv_obstack);
+  to_remove_edges.create (10);
+  to_update_switch_stmts.create (5);
 }
 
 /* Free VRP lattice.  */
@@ -1934,6 +1937,12 @@  vr_values::~vr_values ()
      and not available.  */
   vr_value = NULL;
   vr_phi_edge_counts = NULL;
+
+  /* If there are entries left in TO_REMOVE_EDGES or TO_UPDATE_SWITCH_STMTS
+     then an EVRP client did not clean up properly.  Catch it now rather
+     than seeing something more obscure later.  */
+  gcc_assert (to_remove_edges.length () == 0
+	      && to_update_switch_stmts.length () == 0);
 }
 
 
@@ -3780,6 +3789,7 @@  vr_values::simplify_switch_using_ranges (gswitch *stmt)
 	}
       to_remove_edges.safe_push (e);
       e->flags &= ~EDGE_EXECUTABLE;
+      e->flags |= EDGE_IGNORE;
     }
 
   /* And queue an update for the stmt.  */
@@ -3789,6 +3799,48 @@  vr_values::simplify_switch_using_ranges (gswitch *stmt)
   return false;
 }
 
+/* Remove any edges in TO_REMOVE_EDGES from the CFG.
+   Update any switch statements in TO_UPDATE_SWITCH_STMTS.  */
+
+void
+vr_values::cleanup_edges_and_switches (void)
+{
+  int i;
+  edge e;
+  switch_update *su;
+
+  /* Remove dead edges from SWITCH_EXPR optimization.  This leaves the
+     CFG in a broken state and requires a cfg_cleanup run.  */
+  FOR_EACH_VEC_ELT (to_remove_edges, i, e)
+    remove_edge (e);
+
+  /* Update SWITCH_EXPR case label vector.  */
+  FOR_EACH_VEC_ELT (to_update_switch_stmts, i, su)
+    {
+      size_t j;
+      size_t n = TREE_VEC_LENGTH (su->vec);
+      tree label;
+      gimple_switch_set_num_labels (su->stmt, n);
+      for (j = 0; j < n; j++)
+	gimple_switch_set_label (su->stmt, j, TREE_VEC_ELT (su->vec, j));
+      /* As we may have replaced the default label with a regular one
+	 make sure to make it a real default label again.  This ensures
+	 optimal expansion.  */
+      label = gimple_switch_label (su->stmt, 0);
+      CASE_LOW (label) = NULL_TREE;
+      CASE_HIGH (label) = NULL_TREE;
+    }
+
+  if (to_remove_edges.length () > 0)
+    {
+      free_dominance_info (CDI_DOMINATORS);
+      loops_state_set (LOOPS_NEED_FIXUP);
+    }
+
+  to_remove_edges.release ();
+  to_update_switch_stmts.release ();
+}
+
 /* Simplify an integral conversion from an SSA name in STMT.  */
 
 static bool
diff --git a/gcc/vr-values.h b/gcc/vr-values.h
index 80b16cacefc..ff26d53a079 100644
--- a/gcc/vr-values.h
+++ b/gcc/vr-values.h
@@ -68,6 +68,10 @@  class vr_values
   value_range *allocate_value_range (void)
     { return vrp_value_range_pool.allocate (); }
 
+  /* Handle queued cleanups, must be called before the class is
+     destructed.  */
+  void cleanup_edges_and_switches (void);
+
  private:
   void add_equivalence (bitmap *, const_tree);
   bool vrp_stmt_computes_nonzero (gimple *);
@@ -124,6 +128,19 @@  class vr_values
      number of executable edges we saw the last time we visited the
      node.  */
   int *vr_phi_edge_counts;
+
+  /* Vectors of edges that need removing and switch statements that
+     need updating.  It is expected that a pass using the simplification
+     routines will, at the end of the pass, clean up the edges and
+     switch statements.  The class dtor will try to detect cases
+     that do not follow that expectation.  */
+  struct switch_update {
+    gswitch *stmt;
+    tree vec;
+  };
+
+  vec<edge> to_remove_edges;
+  vec<switch_update> to_update_switch_stmts;
 };
 
 #define VR_INITIALIZER { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL }