Patchwork Fix PR54489 - FRE needing AVAIL_OUT

login
register
mail settings
Submitter Richard Guenther
Date Sept. 14, 2012, 9:16 a.m.
Message ID <alpine.LNX.2.00.1209141057470.28649@zhemvz.fhfr.qr>
Download mbox | patch
Permalink /patch/183853/
State New
Headers show

Comments

Richard Guenther - Sept. 14, 2012, 9:16 a.m.
On Thu, 13 Sep 2012, Steven Bosscher wrote:

> On Wed, Sep 12, 2012 at 4:52 PM, Steven Bosscher wrote:
> > On Wed, Sep 12, 2012 at 4:02 PM, Richard Guenther wrote:
> >> for a followup (and I bet sth else than PRE blows up at -O2 as well).
> >
> > Actually, the only thing that really blows up is that enemy of scalability, VRP.
> 
> FWIW, this appears to be due to the well-known problem with the equiv
> set, but also due to the liveness computations that tree-vrp performs,
> since your commit in r139263.
> 
> Any reason why you didn't just re-use the tree-ssa-live machinery?

Probably I didn't know about it or didn't want to keep the full life
problem life (it tries to free things as soon as possible).

> And any reason why you don't let a DEF kill a live SSA name? AFAICT
> you're exposing all SSA names up without ever killing a USE :-)

Eh ;)  We also should traverse blocks backward I suppose.  Also
the RPO traversal suffers from the same issue I noticed in PRE
and for what I invented my_rev_post_order_compute ...
(pre_and_rev_post_order_compute doesn't compute an optimal
reverse post order).

Patch fixing the liveness below, untested sofar, apart from on
tree-ssa.exp where it seems to regress gcc.dg/tree-ssa/pr21086.c :/

As for the equiv sets - yes, that's known.  I wanted to investigate
at some point what happens if we instead record the SSA name we
registered the assert for (thus look up a chain of lattice values
instead of recording all relevant entries in a bitmap).  ISTR there
were some correctness issues, but if we restrict the chaining maybe
we cat get a good compromise here.

Richard.
Richard Guenther - Sept. 14, 2012, 11:09 a.m.
On Fri, 14 Sep 2012, Richard Guenther wrote:

> As for the equiv sets - yes, that's known.  I wanted to investigate
> at some point what happens if we instead record the SSA name we
> registered the assert for (thus look up a chain of lattice values
> instead of recording all relevant entries in a bitmap).  ISTR there
> were some correctness issues, but if we restrict the chaining maybe
> we cat get a good compromise here.

Actually the only users are compare_name_with_value and
compare_names.  The idea with a simple chain, thus

struct value_range_d
{
...
  /* SSA name whose value range is equivalent to this one.  */
  tree equiv;
};

is only non-trivial for intersections (thus PHI nodes).  Still
there the equivalent range is the nearest dominating one from
the chains of all PHI arguments.  I can only think of the way
we do iteration that would mess up the chains (but not sure
if we need to require them to be in dom order).

Probably best to try implement the above alongside the bitmaps
and compare the results in compare_name_with_value / compare_names.

Richard.

Patch

Index: gcc/tree-vrp.c
===================================================================
--- gcc/tree-vrp.c	(revision 191289)
+++ gcc/tree-vrp.c	(working copy)
@@ -5439,7 +5439,6 @@  find_assert_locations_1 (basic_block bb,
 {
   gimple_stmt_iterator si;
   gimple last;
-  gimple phi;
   bool need_assert;
 
   need_assert = false;
@@ -5462,7 +5461,7 @@  find_assert_locations_1 (basic_block bb,
 
   /* Traverse all the statements in BB marking used names and looking
      for statements that may infer assertions for their used operands.  */
-  for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
+  for (si = gsi_last_bb (bb); !gsi_end_p (si); gsi_prev (&si))
     {
       gimple stmt;
       tree op;
@@ -5531,6 +5530,9 @@  find_assert_locations_1 (basic_block bb,
 		}
 	    }
 	}
+
+      FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_DEF)
+	RESET_BIT (live, SSA_NAME_VERSION (op));
     }
 
   /* Traverse all PHI nodes in BB marking used operands.  */
@@ -5538,7 +5540,11 @@  find_assert_locations_1 (basic_block bb,
     {
       use_operand_p arg_p;
       ssa_op_iter i;
-      phi = gsi_stmt (si);
+      gimple phi = gsi_stmt (si);
+      tree res = gimple_phi_result (phi);
+
+      if (virtual_operand_p (res))
+	continue;
 
       FOR_EACH_PHI_ARG (arg_p, phi, i, SSA_OP_USE)
 	{
@@ -5546,6 +5552,8 @@  find_assert_locations_1 (basic_block bb,
 	  if (TREE_CODE (arg) == SSA_NAME)
 	    SET_BIT (live, SSA_NAME_VERSION (arg));
 	}
+
+      RESET_BIT (live, SSA_NAME_VERSION (res));
     }
 
   return need_assert;