Re: [PR52001] too many cse reverse equiv exprs (take2)

2012-02-26 Thread Richard Sandiford
Alexandre Oliva aol...@redhat.com writes:
 On Feb 19, 2012, Richard Sandiford rdsandif...@googlemail.com wrote:
 and it still isn't obvious to me when canonical_cselib_val is supposed
 to be used.

 For comparison of VALUEs, it avoids the need for recursive or
 combinatorial compares, for all equivalent VALUEs map directly to the
 single canonical value.  For recursive searches and other the like, it's just
 an optimization to avoid an additional recursion (avoiding recursing
 into *any* VALUEs is recommended along with it).

 Other algorithms that iterate over loc lists and recurse should take
 care to avoid infinite recursion, by marking already-visited nodes
 (cselib and var-tracking do some of this), temporarily zeroing out their
 loc lists (like find_base_term), or using other mechanisms to break
 recursion cycles (like get_addr).

 Algorithms that didn't expect naked VALUEs in loc lists (like get_addr)
 may need adjusting to iterate over the loc lists of the canonical value
 (for non-canonical values have a single loc, the canonical value), and
 to disregard values in canonical value's lists (unless e.g. we happen to
 be looking for VALUEs that turn out to be noncanonical).

 In other cases, the use of canonical values instead of noncanonical ones
 when filling in data structures (say, building expressions to record in
 cselib) may save memory by avoiding duplication, but since it causes
 cselib to compute different hashes, we'd better use whatever is most
 likely to be searched for by hashing.  (We could tweak lookups to use
 canonical values and to recompute hashes when adding equivalences
 between values already used in expressions, but this hasn't been done
 yet).

 I hope this makes some sense ;-)

Yeah, it does, thanks.  It seemed that when we recorded two values V1
and V2 were equivalent, we added V1 to V2's location list and V2 to V1's
location list.  But it sounds from the above like the canonical value is
what we want in almost all cases, so if V2 is the one that becomes
noncanonical, is it really worth adding V2 to V1's location list?

Richard


Re: [PR52001] too many cse reverse equiv exprs (take2)

2012-02-26 Thread Alexandre Oliva
On Feb 26, 2012, Richard Sandiford rdsandif...@googlemail.com wrote:

 It seemed that when we recorded two values V1 and V2 were equivalent,
 we added V1 to V2's location list and V2 to V1's location list.  But
 it sounds from the above like the canonical value is what we want in
 almost all cases, so if V2 is the one that becomes noncanonical, is
 it really worth adding V2 to V1's location list?

I'd given that some thought and concluded that it wasn't safe to take V2
out of V1's list, in case what we were searching for among V1's
locations was precisely V2.  Now, maybe there are ways around that that
(say, canonicalizing a value before searching for it) that I haven't
given much thought.  I didn't think it would buy us much, but I could
easily be wrong, and I'd be glad to look into this given evidence that I
am.

-- 
Alexandre Oliva, freedom fighterhttp://FSFLA.org/~lxoliva/
You must be the change you wish to see in the world. -- Gandhi
Be Free! -- http://FSFLA.org/   FSF Latin America board member
Free Software Evangelist  Red Hat Brazil Compiler Engineer


Re: [PR52001] too many cse reverse equiv exprs (take2)

2012-02-25 Thread Alexandre Oliva
On Feb 19, 2012, Richard Sandiford rdsandif...@googlemail.com wrote:

 I have to admit I still don't like these changes
 I'd much rather we kept to the original dag.

I'm not sure I mentioned before, but it remains a DAG unless
cselib_add_permanent_equiv is called.  Only var-tracking calls it, and
even then, only when VTA is enabled, so if anyone ever runs into a
problem, it's easy enough to disable VTA, var-tracking or even -g
altogether to work around the problem.

Now, I confess I didn't expect problems in the first place, for I'd
missed this use of alias.c by var-tracking.  The other use, in
find_base_term, had been properly adjusted already.  There aren't any
other uses of CSELIB_VAL_PTR, so I'm now pretty confident we won't run
into any other problems like this.  (famous last words ;-)

 and it still isn't obvious to me when canonical_cselib_val is supposed
 to be used.

For comparison of VALUEs, it avoids the need for recursive or
combinatorial compares, for all equivalent VALUEs map directly to the
single canonical value.  For recursive searches and other the like, it's just
an optimization to avoid an additional recursion (avoiding recursing
into *any* VALUEs is recommended along with it).

Other algorithms that iterate over loc lists and recurse should take
care to avoid infinite recursion, by marking already-visited nodes
(cselib and var-tracking do some of this), temporarily zeroing out their
loc lists (like find_base_term), or using other mechanisms to break
recursion cycles (like get_addr).

Algorithms that didn't expect naked VALUEs in loc lists (like get_addr)
may need adjusting to iterate over the loc lists of the canonical value
(for non-canonical values have a single loc, the canonical value), and
to disregard values in canonical value's lists (unless e.g. we happen to
be looking for VALUEs that turn out to be noncanonical).

In other cases, the use of canonical values instead of noncanonical ones
when filling in data structures (say, building expressions to record in
cselib) may save memory by avoiding duplication, but since it causes
cselib to compute different hashes, we'd better use whatever is most
likely to be searched for by hashing.  (We could tweak lookups to use
canonical values and to recompute hashes when adding equivalences
between values already used in expressions, but this hasn't been done
yet).

I hope this makes some sense ;-)

-- 
Alexandre Oliva, freedom fighterhttp://FSFLA.org/~lxoliva/
You must be the change you wish to see in the world. -- Gandhi
Be Free! -- http://FSFLA.org/   FSF Latin America board member
Free Software Evangelist  Red Hat Brazil Compiler Engineer


Re: [PR52001] too many cse reverse equiv exprs (take2)

2012-02-20 Thread Jakub Jelinek
On Fri, Feb 17, 2012 at 02:01:36AM -0200, Alexandre Oliva wrote:
 for gcc/ChangeLog
 from  Alexandre Oliva  aol...@redhat.com
 
   PR debug/52001
   * cselib.c (preserve_only_constants): Rename to...
   (preserve_constants_and_equivs): ... this.  Split out...
   (invariant_or_equiv_p): ... this.  Preserve plus expressions
   of other preserved expressions too.
   (cselib_reset_table): Adjust.
   * var-tracking.c (reverse_op): Use canonical value to build
   reverse operation.

This patch is ok for the trunk, provided testing was successful.

Jakub


Re: [PR52001] too many cse reverse equiv exprs (take2)

2012-02-19 Thread Richard Sandiford
Alexandre Oliva aol...@redhat.com writes:
 On Feb 15, 2012, Richard Sandiford rdsandif...@googlemail.com wrote:

 I'm fine with putting it in and seeing what breaks.  But I'd really
 prefer if we knew in theory. :-)

 Ok, I dove into the problem without a testcase, and I managed to trigger
 it on other platforms after tweaking get_addr a bit so as use loc lists
 form canonical values, and to avoid returning other VALUEs if other
 alternatives exist.

 Like I say, my understanding before this patch series went in was that
 cselib values weren't supposed to be cyclic.  Now that they are, what
 should consumers like memrefs_conflict_p do to avoid getting stuck?

 I'm now testing the following heuristic: only use an expr instead of a
 value if the expr doesn't reference any value whose uid is greater than
 that of the value.  This worked for libgcc so far; regstrapping now.

 Here's the revised patch that addresses Jakub's and your comments, that
 regstrapped on x86_64-linux-gnu and i686-linux-gnu, followed by the
 patch I'm testing now on both platforms.

Thanks for tackling this.  I agree it looks like the patch should work.

I have to admit I still don't like these changes, and it still isn't
obvious to me when canonical_cselib_val is supposed to be used.
I'd much rather we kept to the original dag.  But I realise that
probably isn't a useful attitude to take, and I don't know
vartracking well enough to understand the constraints,
so I'll shut up now.

Richard


Re: [PR52001] too many cse reverse equiv exprs (take2)

2012-02-16 Thread Alexandre Oliva
On Feb 15, 2012, Richard Sandiford rdsandif...@googlemail.com wrote:

 I'm fine with putting it in and seeing what breaks.  But I'd really
 prefer if we knew in theory. :-)

Ok, I dove into the problem without a testcase, and I managed to trigger
it on other platforms after tweaking get_addr a bit so as use loc lists
form canonical values, and to avoid returning other VALUEs if other
alternatives exist.

 Like I say, my understanding before this patch series went in was that
 cselib values weren't supposed to be cyclic.  Now that they are, what
 should consumers like memrefs_conflict_p do to avoid getting stuck?

I'm now testing the following heuristic: only use an expr instead of a
value if the expr doesn't reference any value whose uid is greater than
that of the value.  This worked for libgcc so far; regstrapping now.

Here's the revised patch that addresses Jakub's and your comments, that
regstrapped on x86_64-linux-gnu and i686-linux-gnu, followed by the
patch I'm testing now on both platforms.

for gcc/ChangeLog
from  Alexandre Oliva  aol...@redhat.com

	PR debug/52001
	* cselib.c (preserve_only_constants): Rename to...
	(preserve_constants_and_equivs): ... this.  Split out...
	(invariant_or_equiv_p): ... this.  Preserve plus expressions
	of other preserved expressions too.
	(cselib_reset_table): Adjust.
	* var-tracking.c (reverse_op): Use canonical value to build
	reverse operation.

Index: gcc/cselib.c
===
--- gcc/cselib.c.orig	2012-02-12 06:13:40.676385499 -0200
+++ gcc/cselib.c	2012-02-15 00:40:46.0 -0200
@@ -383,22 +383,29 @@ cselib_clear_table (void)
   cselib_reset_table (1);
 }
 
-/* Remove from hash table all VALUEs except constants
-   and function invariants.  */
+/* Return TRUE if V is a constant, a function invariant or a VALUE
+   equivalence; FALSE otherwise.  */
 
-static int
-preserve_only_constants (void **x, void *info ATTRIBUTE_UNUSED)
+static bool
+invariant_or_equiv_p (cselib_val *v)
 {
-  cselib_val *v = (cselib_val *)*x;
   struct elt_loc_list *l;
 
+  if (v == cfa_base_preserved_val)
+return true;
+
+  /* Keep VALUE equivalences around.  */
+  for (l = v-locs; l; l = l-next)
+if (GET_CODE (l-loc) == VALUE)
+  return true;
+
   if (v-locs != NULL
v-locs-next == NULL)
 {
   if (CONSTANT_P (v-locs-loc)
 	   (GET_CODE (v-locs-loc) != CONST
 	  || !references_value_p (v-locs-loc, 0)))
-	return 1;
+	return true;
   /* Although a debug expr may be bound to different expressions,
 	 we can preserve it as if it was constant, to get unification
 	 and proper merging within var-tracking.  */
@@ -406,24 +413,29 @@ preserve_only_constants (void **x, void 
 	  || GET_CODE (v-locs-loc) == DEBUG_IMPLICIT_PTR
 	  || GET_CODE (v-locs-loc) == ENTRY_VALUE
 	  || GET_CODE (v-locs-loc) == DEBUG_PARAMETER_REF)
-	return 1;
-  if (cfa_base_preserved_val)
-	{
-	  if (v == cfa_base_preserved_val)
-	return 1;
-	  if (GET_CODE (v-locs-loc) == PLUS
-	   CONST_INT_P (XEXP (v-locs-loc, 1))
-	   XEXP (v-locs-loc, 0) == cfa_base_preserved_val-val_rtx)
-	return 1;
-	}
+	return true;
+
+  /* (plus (value V) (const_int C)) is invariant iff V is invariant.  */
+  if (GET_CODE (v-locs-loc) == PLUS
+	   CONST_INT_P (XEXP (v-locs-loc, 1))
+	   GET_CODE (XEXP (v-locs-loc, 0)) == VALUE
+	   invariant_or_equiv_p (CSELIB_VAL_PTR (XEXP (v-locs-loc, 0
+	return true;
 }
 
-  /* Keep VALUE equivalences around.  */
-  for (l = v-locs; l; l = l-next)
-if (GET_CODE (l-loc) == VALUE)
-  return 1;
+  return false;
+}
+
+/* Remove from hash table all VALUEs except constants, function
+   invariants and VALUE equivalences.  */
+
+static int
+preserve_constants_and_equivs (void **x, void *info ATTRIBUTE_UNUSED)
+{
+  cselib_val *v = (cselib_val *)*x;
 
-  htab_clear_slot (cselib_hash_table, x);
+  if (!invariant_or_equiv_p (v))
+htab_clear_slot (cselib_hash_table, x);
   return 1;
 }
 
@@ -463,7 +475,7 @@ cselib_reset_table (unsigned int num)
 }
 
   if (cselib_preserve_constants)
-htab_traverse (cselib_hash_table, preserve_only_constants, NULL);
+htab_traverse (cselib_hash_table, preserve_constants_and_equivs, NULL);
   else
 htab_empty (cselib_hash_table);
 
Index: gcc/var-tracking.c
===
--- gcc/var-tracking.c.orig	2012-02-12 06:13:38.633412886 -0200
+++ gcc/var-tracking.c	2012-02-14 23:56:52.0 -0200
@@ -5334,6 +5334,10 @@ reverse_op (rtx val, const_rtx expr, rtx
   if (!v || !cselib_preserved_value_p (v))
 return;
 
+  /* Use canonical V to avoid creating multiple redundant expressions
+ for different VALUES equivalent to V.  */
+  v = canonical_cselib_val (v);
+
   /* Adding a reverse op isn't useful if V already has an always valid
  location.  Ignore ENTRY_VALUE, while it is always constant, we should
  prefer non-ENTRY_VALUE locations whenever possible.  */
for  

Re: [PR52001] too many cse reverse equiv exprs (take2)

2012-02-15 Thread Richard Sandiford
Alexandre Oliva aol...@redhat.com writes:
 On Feb 13, 2012, Richard Sandiford rdsandif...@googlemail.com wrote:
 does this avoid the kind of memrefs_conflict_p cycle I was seeing in:

 I don't know that it does, I'd missed that bit.

 If you still have a preprocessed testcase, I'd be glad to give it a
 quick try.  Failing that, I can try a build on my yeeloong, but... that
 takes forever minus a few days ;-)

Unfortunately, I've not kept the preprocessed source, and I'd need to
wind back to an old compiler to get it.  If it's in practice rather
than in theory that we're talking about, then I'm fine with putting
it in and seeing what breaks.  But I'd really prefer if we knew in
theory. :-)  Like I say, my understanding before this patch series went
in was that cselib values weren't supposed to be cyclic.  Now that they are,
what should consumers like memrefs_conflict_p do to avoid getting stuck?

Thanks,
Richard


Re: [PR52001] too many cse reverse equiv exprs (take2)

2012-02-14 Thread Alexandre Oliva
On Feb 13, 2012, Richard Sandiford rdsandif...@googlemail.com wrote:

 does this avoid the kind of memrefs_conflict_p cycle I was seeing in:

I don't know that it does, I'd missed that bit.

If you still have a preprocessed testcase, I'd be glad to give it a
quick try.  Failing that, I can try a build on my yeeloong, but... that
takes forever minus a few days ;-)

-- 
Alexandre Oliva, freedom fighterhttp://FSFLA.org/~lxoliva/
You must be the change you wish to see in the world. -- Gandhi
Be Free! -- http://FSFLA.org/   FSF Latin America board member
Free Software Evangelist  Red Hat Brazil Compiler Engineer


Re: [PR52001] too many cse reverse equiv exprs (take2)

2012-02-14 Thread Alexandre Oliva
On Feb 13, 2012, Jakub Jelinek ja...@redhat.com wrote:

 I'm not convinced you want the
 +  /* Keep VALUE equivalences around.  */
 +  for (l = v-locs; l; l = l-next)
 +if (GET_CODE (l-loc) == VALUE)
 +  return true;
 hunk in invariant_p,

Yeah, maybe “invariant_p” is a misnomer.  The thinking is that, if we
preserve a value, we preserve other values based on it, and we do
preserve values with equivalences to avoid having to carry the
equivalences in the var-tracking dataflow sets.

 Otherwise the cselib.c changes look ok to me, but I don't understand
 why are you removing the var-tracking.c loop.

I thought completeness called for retaining those equivalences, but now
I see that, since they're always going to be computed values, rather
than locations, the constant value provides sufficient and better
information for completeness, rendering them irrelevant indeed.  I'll
put that hunk back in and retest.

Thanks,

-- 
Alexandre Oliva, freedom fighterhttp://FSFLA.org/~lxoliva/
You must be the change you wish to see in the world. -- Gandhi
Be Free! -- http://FSFLA.org/   FSF Latin America board member
Free Software Evangelist  Red Hat Brazil Compiler Engineer


[PR52001] too many cse reverse equiv exprs (take2)

2012-02-13 Thread Alexandre Oliva
Jakub asked to have a closer look at the problem, and I found we could
do somewhat better.  The first thing I noticed was that the problem was
that, in each block that computed a (base+const), we created a new VALUE
for the expression (with the same const and global base), and a new
reverse operation.

This was wrong.  Clearly we should reuse the same expression.  I had to
arrange for the expression to be retained across basic blocks, for it
was function invariant.  I split out the code to detect invariants from
the function that removes entries from the cselib hash table across
blocks, and made it recursive so that a VALUE equivalent to (plus
(value) (const_int)) will be retained, if the base value fits (maybe
recursively) the definition of invariant.

An earlier attempt to address this issue remained in cselib: using the
canonical value to build the reverse expression.  I believe it has a
potential of avoiding the creation of redundant reverse expressions, for
expressions involving equivalent but different VALUEs will evaluate to
different hashes.  I haven't observed effects WRT the given testcase,
before or after the change that actually fixed the problem, because we
now find the same base expression and thus reuse the reverse_op as well,
but I figured I'd keep it in for it is very cheap and possibly useful.

Regstrapped on x86_64-linux-gnu and i686-pc-linux-gnu.  Ok to install?

for gcc/ChangeLog
from  Alexandre Oliva  aol...@redhat.com

	PR debug/52001
	* cselib.c (invariant_p): Split out of...
	(preserve_only_constants): ... this.  Preserve plus expressions
	of invariant values and constants.
	* var-tracking.c (reverse_op): Don't drop equivs of constants.
	Use canonical value to build reverse operation.

Index: gcc/cselib.c
===
--- gcc/cselib.c.orig	2012-02-12 06:13:40.676385499 -0200
+++ gcc/cselib.c	2012-02-12 09:07:00.653579375 -0200
@@ -383,22 +383,29 @@ cselib_clear_table (void)
   cselib_reset_table (1);
 }
 
-/* Remove from hash table all VALUEs except constants
-   and function invariants.  */
+/* Return TRUE if V is a constant or a function invariant, FALSE
+   otherwise.  */
 
-static int
-preserve_only_constants (void **x, void *info ATTRIBUTE_UNUSED)
+static bool
+invariant_p (cselib_val *v)
 {
-  cselib_val *v = (cselib_val *)*x;
   struct elt_loc_list *l;
 
+  if (v == cfa_base_preserved_val)
+return true;
+
+  /* Keep VALUE equivalences around.  */
+  for (l = v-locs; l; l = l-next)
+if (GET_CODE (l-loc) == VALUE)
+  return true;
+
   if (v-locs != NULL
v-locs-next == NULL)
 {
   if (CONSTANT_P (v-locs-loc)
 	   (GET_CODE (v-locs-loc) != CONST
 	  || !references_value_p (v-locs-loc, 0)))
-	return 1;
+	return true;
   /* Although a debug expr may be bound to different expressions,
 	 we can preserve it as if it was constant, to get unification
 	 and proper merging within var-tracking.  */
@@ -406,24 +413,29 @@ preserve_only_constants (void **x, void 
 	  || GET_CODE (v-locs-loc) == DEBUG_IMPLICIT_PTR
 	  || GET_CODE (v-locs-loc) == ENTRY_VALUE
 	  || GET_CODE (v-locs-loc) == DEBUG_PARAMETER_REF)
-	return 1;
-  if (cfa_base_preserved_val)
-	{
-	  if (v == cfa_base_preserved_val)
-	return 1;
-	  if (GET_CODE (v-locs-loc) == PLUS
-	   CONST_INT_P (XEXP (v-locs-loc, 1))
-	   XEXP (v-locs-loc, 0) == cfa_base_preserved_val-val_rtx)
-	return 1;
-	}
+	return true;
+
+  /* (plus (value V) (const_int C)) is invariant iff V is invariant.  */
+  if (GET_CODE (v-locs-loc) == PLUS
+	   CONST_INT_P (XEXP (v-locs-loc, 1))
+	   GET_CODE (XEXP (v-locs-loc, 0)) == VALUE
+	   invariant_p (CSELIB_VAL_PTR (XEXP (v-locs-loc, 0
+	return true;
 }
 
-  /* Keep VALUE equivalences around.  */
-  for (l = v-locs; l; l = l-next)
-if (GET_CODE (l-loc) == VALUE)
-  return 1;
+  return false;
+}
+
+/* Remove from hash table all VALUEs except constants
+   and function invariants.  */
+
+static int
+preserve_only_constants (void **x, void *info ATTRIBUTE_UNUSED)
+{
+  cselib_val *v = (cselib_val *)*x;
 
-  htab_clear_slot (cselib_hash_table, x);
+  if (!invariant_p (v))
+htab_clear_slot (cselib_hash_table, x);
   return 1;
 }
 
Index: gcc/var-tracking.c
===
--- gcc/var-tracking.c.orig	2012-02-12 06:13:38.633412886 -0200
+++ gcc/var-tracking.c	2012-02-12 10:09:49.0 -0200
@@ -5298,7 +5298,6 @@ reverse_op (rtx val, const_rtx expr, rtx
 {
   rtx src, arg, ret;
   cselib_val *v;
-  struct elt_loc_list *l;
   enum rtx_code code;
 
   if (GET_CODE (expr) != SET)
@@ -5334,13 +5333,9 @@ reverse_op (rtx val, const_rtx expr, rtx
   if (!v || !cselib_preserved_value_p (v))
 return;
 
-  /* Adding a reverse op isn't useful if V already has an always valid
- location.  Ignore ENTRY_VALUE, while it is always constant, we should
- prefer non-ENTRY_VALUE locations whenever possible.  */
-  for (l = v-locs; 

Re: [PR52001] too many cse reverse equiv exprs (take2)

2012-02-13 Thread Jakub Jelinek
On Mon, Feb 13, 2012 at 12:27:35PM -0200, Alexandre Oliva wrote:
 Jakub asked to have a closer look at the problem, and I found we could
 do somewhat better.  The first thing I noticed was that the problem was
 that, in each block that computed a (base+const), we created a new VALUE
 for the expression (with the same const and global base), and a new
 reverse operation.

I'm not convinced you want the
 +  /* Keep VALUE equivalences around.  */
 +  for (l = v-locs; l; l = l-next)
 +if (GET_CODE (l-loc) == VALUE)
 +  return true;
hunk in invariant_p, I'd say it should stay in preserve_only_values,
a value equivalence isn't necessarily invariant.
Otherwise the cselib.c changes look ok to me, but I don't understand why are you
removing the var-tracking.c loop.  While cselib will with your changes
handle the situation better, for values that are already invariant
(guess canonical_cselib_val should be called before that loop and perhaps
instead of testing CONSTANT_P it could test invatiant_p if you rename
it to cselib_invariant_p and export) adding any reverse ops for it is really
just a waste of resources, because we have a better location already in the
list.  Adding the extra loc doesn't improve it in any way.

Jakub


Re: [PR52001] too many cse reverse equiv exprs (take2)

2012-02-13 Thread Richard Sandiford
Alexandre Oliva aol...@redhat.com writes:
 Jakub asked to have a closer look at the problem, and I found we could
 do somewhat better.  The first thing I noticed was that the problem was
 that, in each block that computed a (base+const), we created a new VALUE
 for the expression (with the same const and global base), and a new
 reverse operation.

 This was wrong.  Clearly we should reuse the same expression.  I had to
 arrange for the expression to be retained across basic blocks, for it
 was function invariant.  I split out the code to detect invariants from
 the function that removes entries from the cselib hash table across
 blocks, and made it recursive so that a VALUE equivalent to (plus
 (value) (const_int)) will be retained, if the base value fits (maybe
 recursively) the definition of invariant.

 An earlier attempt to address this issue remained in cselib: using the
 canonical value to build the reverse expression.  I believe it has a
 potential of avoiding the creation of redundant reverse expressions, for
 expressions involving equivalent but different VALUEs will evaluate to
 different hashes.  I haven't observed effects WRT the given testcase,
 before or after the change that actually fixed the problem, because we
 now find the same base expression and thus reuse the reverse_op as well,
 but I figured I'd keep it in for it is very cheap and possibly useful.

Thanks for looking at this.  Just to be sure: does this avoid the kind
of memrefs_conflict_p cycle I was seeing in:

http://gcc.gnu.org/ml/gcc-patches/2012-01/msg01051.html

(in theory, I mean).

Richard