[07/nn] Add unique CONSTs

This patch adds a way of treating certain kinds of CONST as unique,
so that pointer equality is equivalent to value equality.  For now it
is restricted to VEC_DUPLICATE and VEC_SERIES, although the code to
generate them remains in the else arm of an "if (1)" until a later
patch.

This is needed so that (const (vec_duplicate xx)) can used as the
CONSTxx_RTX of a variable-length vector.


2017-10-23  Richard Sandiford  <richard.sandiford@linaro.org>
	    Alan Hayward  <alan.hayward@arm.com>
	    David Sherwood  <david.sherwood@arm.com>

gcc/
	* rtl.h (unique_const_p): New function.
	(gen_rtx_CONST): Declare.
	* emit-rtl.c (const_hasher): New struct.
	(const_htab): New variable.
	(init_emit_once): Initialize it.
	(const_hasher::hash, const_hasher::equal): New functions.
	(gen_rtx_CONST): New function.
	(spare_vec_duplicate, spare_vec_series): New variables.
	(gen_const_vec_duplicate_1): Add code for use (const (vec_duplicate)),
	but disable it for now.
	(gen_const_vec_series): Likewise (const (vec_series)).
	* gengenrtl.c (special_rtx): Return true for CONST.
	* rtl.c (shared_const_p): Return true if unique_const_p.

On 10/23/2017 05:21 AM, Richard Sandiford wrote:
> This patch adds a way of treating certain kinds of CONST as unique,

> so that pointer equality is equivalent to value equality.  For now it

> is restricted to VEC_DUPLICATE and VEC_SERIES, although the code to

> generate them remains in the else arm of an "if (1)" until a later

> patch.

> 

> This is needed so that (const (vec_duplicate xx)) can used as the

> CONSTxx_RTX of a variable-length vector.

You're brave :-)  I know we looked at making CONST_INTs behave in this
manner eons ago in an effort to reduce memory consumption and it was
just plain painful.   There may still be comments from that project
littering the source code.

I do wonder if we might want to revisit this again as we have better
infrastructure in place.


> 

> 

> 2017-10-23  Richard Sandiford  <richard.sandiford@linaro.org>

> 	    Alan Hayward  <alan.hayward@arm.com>

> 	    David Sherwood  <david.sherwood@arm.com>

> 

> gcc/

> 	* rtl.h (unique_const_p): New function.

> 	(gen_rtx_CONST): Declare.

> 	* emit-rtl.c (const_hasher): New struct.

> 	(const_htab): New variable.

> 	(init_emit_once): Initialize it.

> 	(const_hasher::hash, const_hasher::equal): New functions.

> 	(gen_rtx_CONST): New function.

> 	(spare_vec_duplicate, spare_vec_series): New variables.

> 	(gen_const_vec_duplicate_1): Add code for use (const (vec_duplicate)),

> 	but disable it for now.

> 	(gen_const_vec_series): Likewise (const (vec_series)).

> 	* gengenrtl.c (special_rtx): Return true for CONST.

> 	* rtl.c (shared_const_p): Return true if unique_const_p.

ISTM that you need an update the rtl.texi's structure sharing
assumptions section to describe the new rules around CONSTs.

So what's the purpose of the sparc_vec_* stuff that you're going to use
in the future?  It looks like a single element cache to me.    Am I
missing something?

jeff

Jeff Law <law@redhat.com> writes:
> On 10/23/2017 05:21 AM, Richard Sandiford wrote:

>> This patch adds a way of treating certain kinds of CONST as unique,

>> so that pointer equality is equivalent to value equality.  For now it

>> is restricted to VEC_DUPLICATE and VEC_SERIES, although the code to

>> generate them remains in the else arm of an "if (1)" until a later

>> patch.

>> 

>> This is needed so that (const (vec_duplicate xx)) can used as the

>> CONSTxx_RTX of a variable-length vector.

> You're brave :-)  I know we looked at making CONST_INTs behave in this

> manner eons ago in an effort to reduce memory consumption and it was

> just plain painful.   There may still be comments from that project

> littering the source code.

>

> I do wonder if we might want to revisit this again as we have better

> infrastructure in place.


For vectors it isn't so bad, since we already do the same thing
for CONST_VECTOR.  Fortunately CONST_VECTOR and CONST always have
a mode, so there's no awkward sharing between modes...

>> 2017-10-23  Richard Sandiford  <richard.sandiford@linaro.org>

>> 	    Alan Hayward  <alan.hayward@arm.com>

>> 	    David Sherwood  <david.sherwood@arm.com>

>> 

>> gcc/

>> 	* rtl.h (unique_const_p): New function.

>> 	(gen_rtx_CONST): Declare.

>> 	* emit-rtl.c (const_hasher): New struct.

>> 	(const_htab): New variable.

>> 	(init_emit_once): Initialize it.

>> 	(const_hasher::hash, const_hasher::equal): New functions.

>> 	(gen_rtx_CONST): New function.

>> 	(spare_vec_duplicate, spare_vec_series): New variables.

>> 	(gen_const_vec_duplicate_1): Add code for use (const (vec_duplicate)),

>> 	but disable it for now.

>> 	(gen_const_vec_series): Likewise (const (vec_series)).

>> 	* gengenrtl.c (special_rtx): Return true for CONST.

>> 	* rtl.c (shared_const_p): Return true if unique_const_p.

> ISTM that you need an update the rtl.texi's structure sharing

> assumptions section to describe the new rules around CONSTs.


Oops, yeah.  How about the attached?

> So what's the purpose of the sparc_vec_* stuff that you're going to use

> in the future?  It looks like a single element cache to me.    Am I

> missing something?


No, that's right.  When looking up the const for (vec_duplicate x), say,
it's easier to create the vec_duplicate rtx first.  But if the lookup
succeeds (and so we already have an rtx with that value), we keep the
discarded vec_duplicate around so that we can reuse it for the next
lookup.

Thanks for the reviews,

Richard


2017-10-27  Richard Sandiford  <richard.sandiford@linaro.org>
	    Alan Hayward  <alan.hayward@arm.com>
	    David Sherwood  <david.sherwood@arm.com>

gcc/
	* doc/rtl.texi: Document rtl sharing rules.
	* rtl.h (unique_const_p): New function.
	(gen_rtx_CONST): Declare.
	* emit-rtl.c (const_hasher): New struct.
	(const_htab): New variable.
	(init_emit_once): Initialize it.
	(const_hasher::hash, const_hasher::equal): New functions.
	(gen_rtx_CONST): New function.
	(spare_vec_duplicate, spare_vec_series): New variables.
	(gen_const_vec_duplicate_1): Add code for use (const (vec_duplicate)),
	but disable it for now.
	(gen_const_vec_series): Likewise (const (vec_series)).
	* gengenrtl.c (special_rtx): Return true for CONST.
	* rtl.c (shared_const_p): Return true if unique_const_p.

Index: gcc/doc/rtl.texi
===================================================================
--- gcc/doc/rtl.texi	2017-10-27 16:48:35.827706696 +0100
+++ gcc/doc/rtl.texi	2017-10-27 16:48:37.617270148 +0100
@@ -4197,6 +4197,20 @@ There is only one @code{pc} expression.
 @item
 There is only one @code{cc0} expression.
 
+@cindex @code{const}, RTL sharing
+@item
+There is only one instance of the following structures for a given
+@var{m}, @var{x} and @var{y}:
+@example
+(const:@var{m} (vec_duplicate:@var{m} @var{x}))
+(const:@var{m} (vec_series:@var{m} @var{x} @var{y}))
+@end example
+This means, for example, that for a given @var{n} there is only ever a
+single instance of an expression like:
+@example
+(const:V@var{n}DI (vec_duplicate:V@var{n}DI (const_int 0)))
+@end example
+
 @cindex @code{const_double}, RTL sharing
 @item
 There is only one @code{const_double} expression with value 0 for
Index: gcc/rtl.h
===================================================================
--- gcc/rtl.h	2017-10-27 16:48:37.433286940 +0100
+++ gcc/rtl.h	2017-10-27 16:48:37.619280894 +0100
@@ -2861,6 +2861,23 @@ vec_series_p (const_rtx x, rtx *base_out
   return const_vec_series_p (x, base_out, step_out);
 }
 
+/* Return true if there should only ever be one instance of (const X),
+   so that constants of this type can be compared using pointer equality.  */
+
+inline bool
+unique_const_p (const_rtx x)
+{
+  switch (GET_CODE (x))
+    {
+    case VEC_DUPLICATE:
+    case VEC_SERIES:
+      return true;
+
+    default:
+      return false;
+    }
+}
+
 /* Return the unpromoted (outer) mode of SUBREG_PROMOTED_VAR_P subreg X.  */
 
 inline scalar_int_mode
@@ -3560,6 +3577,7 @@ extern rtx_insn_list *gen_rtx_INSN_LIST
 gen_rtx_INSN (machine_mode mode, rtx_insn *prev_insn, rtx_insn *next_insn,
 	      basic_block bb, rtx pattern, int location, int code,
 	      rtx reg_notes);
+extern rtx gen_rtx_CONST (machine_mode, rtx);
 extern rtx gen_rtx_CONST_INT (machine_mode, HOST_WIDE_INT);
 extern rtx gen_rtx_CONST_VECTOR (machine_mode, rtvec);
 extern void set_mode_and_regno (rtx, machine_mode, unsigned int);
Index: gcc/emit-rtl.c
===================================================================
--- gcc/emit-rtl.c	2017-10-27 16:48:37.433286940 +0100
+++ gcc/emit-rtl.c	2017-10-27 16:48:37.618275521 +0100
@@ -175,6 +175,15 @@ struct const_fixed_hasher : ggc_cache_pt
 
 static GTY ((cache)) hash_table<const_fixed_hasher> *const_fixed_htab;
 
+/* A hash table storing unique CONSTs.  */
+struct const_hasher : ggc_cache_ptr_hash<rtx_def>
+{
+  static hashval_t hash (rtx x);
+  static bool equal (rtx x, rtx y);
+};
+
+static GTY ((cache)) hash_table<const_hasher> *const_htab;
+
 #define cur_insn_uid (crtl->emit.x_cur_insn_uid)
 #define cur_debug_insn_uid (crtl->emit.x_cur_debug_insn_uid)
 #define first_label_num (crtl->emit.x_first_label_num)
@@ -310,6 +319,28 @@ const_fixed_hasher::equal (rtx x, rtx y)
   return fixed_identical (CONST_FIXED_VALUE (a), CONST_FIXED_VALUE (b));
 }
 
+/* Returns a hash code for X (which is either an existing unique CONST
+   or an operand to gen_rtx_CONST).  */
+
+hashval_t
+const_hasher::hash (rtx x)
+{
+  if (GET_CODE (x) == CONST)
+    x = XEXP (x, 0);
+
+  int do_not_record_p = 0;
+  return hash_rtx (x, GET_MODE (x), &do_not_record_p, NULL, false);
+}
+
+/* Returns true if the operand of unique CONST X is equal to Y.  */
+
+bool
+const_hasher::equal (rtx x, rtx y)
+{
+  gcc_checking_assert (GET_CODE (x) == CONST);
+  return rtx_equal_p (XEXP (x, 0), y);
+}
+
 /* Return true if the given memory attributes are equal.  */
 
 bool
@@ -5772,16 +5803,55 @@ init_emit (void)
 #endif
 }
 
+rtx
+gen_rtx_CONST (machine_mode mode, rtx val)
+{
+  if (unique_const_p (val))
+    {
+      /* Look up the CONST in the hash table.  */
+      rtx *slot = const_htab->find_slot (val, INSERT);
+      if (*slot == 0)
+	*slot = gen_rtx_raw_CONST (mode, val);
+      return *slot;
+    }
+
+  return gen_rtx_raw_CONST (mode, val);
+}
+
+/* Temporary rtx used by gen_const_vec_duplicate_1.  */
+static GTY((deletable)) rtx spare_vec_duplicate;
+
 /* Like gen_const_vec_duplicate, but ignore const_tiny_rtx.  */
 
 static rtx
 gen_const_vec_duplicate_1 (machine_mode mode, rtx el)
 {
   int nunits = GET_MODE_NUNITS (mode);
-  rtvec v = rtvec_alloc (nunits);
-  for (int i = 0; i < nunits; ++i)
-    RTVEC_ELT (v, i) = el;
-  return gen_rtx_raw_CONST_VECTOR (mode, v);
+  if (1)
+    {
+      rtvec v = rtvec_alloc (nunits);
+
+      for (int i = 0; i < nunits; ++i)
+	RTVEC_ELT (v, i) = el;
+
+      return gen_rtx_raw_CONST_VECTOR (mode, v);
+    }
+  else
+    {
+      if (spare_vec_duplicate)
+	{
+	  PUT_MODE (spare_vec_duplicate, mode);
+	  XEXP (spare_vec_duplicate, 0) = el;
+	}
+      else
+	spare_vec_duplicate = gen_rtx_VEC_DUPLICATE (mode, el);
+
+      rtx res = gen_rtx_CONST (mode, spare_vec_duplicate);
+      if (XEXP (res, 0) == spare_vec_duplicate)
+	spare_vec_duplicate = NULL_RTX;
+
+      return res;
+    }
 }
 
 /* Generate a vector constant of mode MODE in which every element has
@@ -5843,6 +5913,9 @@ const_vec_series_p_1 (const_rtx x, rtx *
   return true;
 }
 
+/* Temporary rtx used by gen_const_vec_series.  */
+static GTY((deletable)) rtx spare_vec_series;
+
 /* Generate a vector constant of mode MODE in which element I has
    the value BASE + I * STEP.  */
 
@@ -5852,13 +5925,33 @@ gen_const_vec_series (machine_mode mode,
   gcc_assert (CONSTANT_P (base) && CONSTANT_P (step));
 
   int nunits = GET_MODE_NUNITS (mode);
-  rtvec v = rtvec_alloc (nunits);
-  scalar_mode inner_mode = GET_MODE_INNER (mode);
-  RTVEC_ELT (v, 0) = base;
-  for (int i = 1; i < nunits; ++i)
-    RTVEC_ELT (v, i) = simplify_gen_binary (PLUS, inner_mode,
-					    RTVEC_ELT (v, i - 1), step);
-  return gen_rtx_raw_CONST_VECTOR (mode, v);
+  if (1)
+    {
+      rtvec v = rtvec_alloc (nunits);
+      scalar_mode inner_mode = GET_MODE_INNER (mode);
+      RTVEC_ELT (v, 0) = base;
+      for (int i = 1; i < nunits; ++i)
+	RTVEC_ELT (v, i) = simplify_gen_binary (PLUS, inner_mode,
+						RTVEC_ELT (v, i - 1), step);
+      return gen_rtx_raw_CONST_VECTOR (mode, v);
+    }
+  else
+    {
+      if (spare_vec_series)
+	{
+	  PUT_MODE (spare_vec_series, mode);
+	  XEXP (spare_vec_series, 0) = base;
+	  XEXP (spare_vec_series, 1) = step;
+	}
+      else
+	spare_vec_series = gen_rtx_VEC_SERIES (mode, base, step);
+
+      rtx res = gen_rtx_CONST (mode, spare_vec_series);
+      if (XEXP (res, 0) == spare_vec_series)
+	spare_vec_series = NULL_RTX;
+
+      return res;
+    }
 }
 
 /* Generate a vector of mode MODE in which element I has the value
@@ -6016,6 +6109,8 @@ init_emit_once (void)
 
   reg_attrs_htab = hash_table<reg_attr_hasher>::create_ggc (37);
 
+  const_htab = hash_table<const_hasher>::create_ggc (37);
+
 #ifdef INIT_EXPANDERS
   /* This is to initialize {init|mark|free}_machine_status before the first
      call to push_function_context_to.  This is needed by the Chill front
Index: gcc/gengenrtl.c
===================================================================
--- gcc/gengenrtl.c	2017-10-27 16:48:37.433286940 +0100
+++ gcc/gengenrtl.c	2017-10-27 16:48:37.618275521 +0100
@@ -143,7 +143,8 @@ special_rtx (int idx)
 	  || strcmp (defs[idx].enumname, "CC0") == 0
 	  || strcmp (defs[idx].enumname, "RETURN") == 0
 	  || strcmp (defs[idx].enumname, "SIMPLE_RETURN") == 0
-	  || strcmp (defs[idx].enumname, "CONST_VECTOR") == 0);
+	  || strcmp (defs[idx].enumname, "CONST_VECTOR") == 0
+	  || strcmp (defs[idx].enumname, "CONST") == 0);
 }
 
 /* Return nonzero if the RTL code given by index IDX is one that we should
Index: gcc/rtl.c
===================================================================
--- gcc/rtl.c	2017-10-27 16:48:37.433286940 +0100
+++ gcc/rtl.c	2017-10-27 16:48:37.618275521 +0100
@@ -252,6 +252,9 @@ shared_const_p (const_rtx orig)
 {
   gcc_assert (GET_CODE (orig) == CONST);
 
+  if (unique_const_p (XEXP (orig, 0)))
+    return true;
+
   /* CONST can be shared if it contains a SYMBOL_REF.  If it contains
      a LABEL_REF, it isn't sharable.  */
   return (GET_CODE (XEXP (orig, 0)) == PLUS

On 10/27/2017 09:56 AM, Richard Sandiford wrote:
> Jeff Law <law@redhat.com> writes:

>> On 10/23/2017 05:21 AM, Richard Sandiford wrote:

>>> This patch adds a way of treating certain kinds of CONST as unique,

>>> so that pointer equality is equivalent to value equality.  For now it

>>> is restricted to VEC_DUPLICATE and VEC_SERIES, although the code to

>>> generate them remains in the else arm of an "if (1)" until a later

>>> patch.

>>>

>>> This is needed so that (const (vec_duplicate xx)) can used as the

>>> CONSTxx_RTX of a variable-length vector.

>> You're brave :-)  I know we looked at making CONST_INTs behave in this

>> manner eons ago in an effort to reduce memory consumption and it was

>> just plain painful.   There may still be comments from that project

>> littering the source code.

>>

>> I do wonder if we might want to revisit this again as we have better

>> infrastructure in place.

> 

> For vectors it isn't so bad, since we already do the same thing

> for CONST_VECTOR.  Fortunately CONST_VECTOR and CONST always have

> a mode, so there's no awkward sharing between modes...

> 

>>> 2017-10-23  Richard Sandiford  <richard.sandiford@linaro.org>

>>> 	    Alan Hayward  <alan.hayward@arm.com>

>>> 	    David Sherwood  <david.sherwood@arm.com>

>>>

>>> gcc/

>>> 	* rtl.h (unique_const_p): New function.

>>> 	(gen_rtx_CONST): Declare.

>>> 	* emit-rtl.c (const_hasher): New struct.

>>> 	(const_htab): New variable.

>>> 	(init_emit_once): Initialize it.

>>> 	(const_hasher::hash, const_hasher::equal): New functions.

>>> 	(gen_rtx_CONST): New function.

>>> 	(spare_vec_duplicate, spare_vec_series): New variables.

>>> 	(gen_const_vec_duplicate_1): Add code for use (const (vec_duplicate)),

>>> 	but disable it for now.

>>> 	(gen_const_vec_series): Likewise (const (vec_series)).

>>> 	* gengenrtl.c (special_rtx): Return true for CONST.

>>> 	* rtl.c (shared_const_p): Return true if unique_const_p.

>> ISTM that you need an update the rtl.texi's structure sharing

>> assumptions section to describe the new rules around CONSTs.

> 

> Oops, yeah.  How about the attached?

OK.

> 

>> So what's the purpose of the sparc_vec_* stuff that you're going to use

>> in the future?  It looks like a single element cache to me.    Am I

>> missing something?

> 

> No, that's right.  When looking up the const for (vec_duplicate x), say,

> it's easier to create the vec_duplicate rtx first.  But if the lookup

> succeeds (and so we already have an rtx with that value), we keep the

> discarded vec_duplicate around so that we can reuse it for the next

> lookup.

OK.

Jeff