[PATCH 1/9] print_rtx: implement support for reuse IDs (v2)

[David Malcolm <dmalcolm@redhat.com>]

Posted earlier here:
  https://gcc.gnu.org/ml/gcc-patches/2016-11/msg00651.html
Link to earlier discussion:
  https://gcc.gnu.org/ml/gcc-patches/2016-10/msg01801.html

This version:
- eliminates the rtx_reuse_manager singleton
- eliminates print-rtl-reuse.h, moving class rtx_reuse_manager into
print-rtl.h and print-rtl.c
- fixes the formatting issues you noted in the earlier patch

gcc/ChangeLog:
	* config/i386/i386.c: Include print-rtl.h.
	(selftest::ix86_test_dumping_memory_blockage): New function.
	(selftest::ix86_run_selftests): Call it.
	* print-rtl-function.c (print_rtx_function): Create an
	rtx_reuse_manager and use it.
	* print-rtl.c: Include "rtl-iter.h".
	(rtx_writer::rtx_writer): Add reuse_manager param.
	(rtx_reuse_manager::rtx_reuse_manager): New ctor.
	(uses_rtx_reuse_p): New function.
	(rtx_reuse_manager::preprocess): New function.
	(rtx_reuse_manager::has_reuse_id): New function.
	(rtx_reuse_manager::seen_def_p): New function.
	(rtx_reuse_manager::set_seen_def): New function.
	(rtx_writer::print_rtx): If "in_rtx" has a reuse ID, print it as a
	prefix the first time in_rtx is seen, and print reuse_rtx
	subsequently.
	(print_inline_rtx): Supply NULL for new reuse_manager param.
	(debug_rtx): Likewise.
	(print_rtl): Likewise.
	(print_rtl_single): Likewise.
	(rtx_writer::print_rtl_single_with_indent): Likewise.
	* print-rtl.h: Include bitmap.h when building for host.
	(rtx_writer::rtx_writer): Add reuse_manager param.
	(rtx_writer::m_rtx_reuse_manager): New field.
	(class rtx_reuse_manager): New class.
	* rtl-tests.c (selftest::assert_rtl_dump_eq): Add reuse_manager
	param and use it when constructing rtx_writer.
	(selftest::test_dumping_rtx_reuse): New function.
	(selftest::rtl_tests_c_tests): Call it.
	* selftest-rtl.h (class rtx_reuse_manager): New forward decl.
	(selftest::assert_rtl_dump_eq): Add reuse_manager param.
	(ASSERT_RTL_DUMP_EQ): Supply NULL for reuse_manager param.
	(ASSERT_RTL_DUMP_EQ_WITH_REUSE): New macro.
---
 gcc/config/i386/i386.c   |  24 ++++++++
 gcc/print-rtl-function.c |   7 ++-
 gcc/print-rtl.c          | 139 +++++++++++++++++++++++++++++++++++++++++++----
 gcc/print-rtl.h          |  81 ++++++++++++++++++++++++++-
 gcc/rtl-tests.c          |  53 +++++++++++++++++-
 gcc/selftest-rtl.h       |  13 ++++-
 6 files changed, 300 insertions(+), 17 deletions(-)

diff --git a/gcc/config/i386/i386.c b/gcc/config/i386/i386.c
index a5c4ba7..6c608e0 100644
--- a/gcc/config/i386/i386.c
+++ b/gcc/config/i386/i386.c
@@ -82,6 +82,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "tree-ssanames.h"
 #include "selftest.h"
 #include "selftest-rtl.h"
+#include "print-rtl.h"
 
 /* This file should be included last.  */
 #include "target-def.h"
@@ -50649,12 +50650,35 @@ ix86_test_dumping_hard_regs ()
   ASSERT_RTL_DUMP_EQ ("(reg:SI dx)", gen_raw_REG (SImode, 1));
 }
 
+/* Test dumping an insn with repeated references to the same SCRATCH,
+   to verify the rtx_reuse code.  */
+
+static void
+ix86_test_dumping_memory_blockage ()
+{
+  set_new_first_and_last_insn (NULL, NULL);
+
+  rtx pat = gen_memory_blockage ();
+  rtx_reuse_manager r;
+  r.preprocess (pat);
+
+  /* Verify that the repeated references to the SCRATCH show use
+     reuse IDS.  The first should be prefixed with a reuse ID,
+     and the second should be dumped as a "reuse_rtx" of that ID.  */
+  ASSERT_RTL_DUMP_EQ_WITH_REUSE
+    ("(cinsn 1 (set (mem/v:BLK (0|scratch:DI) [0  A8])\n"
+     "        (unspec:BLK [\n"
+     "                (mem/v:BLK (reuse_rtx 0) [0  A8])\n"
+     "            ] UNSPEC_MEMORY_BLOCKAGE)))\n", pat, &r);
+}
+
 /* Run all target-specific selftests.  */
 
 static void
 ix86_run_selftests (void)
 {
   ix86_test_dumping_hard_regs ();
+  ix86_test_dumping_memory_blockage ();
 }
 
 } // namespace selftest
diff --git a/gcc/print-rtl-function.c b/gcc/print-rtl-function.c
index 8842226..dea84fe 100644
--- a/gcc/print-rtl-function.c
+++ b/gcc/print-rtl-function.c
@@ -221,7 +221,12 @@ print_param (FILE *outfile, rtx_writer &w, tree arg)
 DEBUG_FUNCTION void
 print_rtx_function (FILE *outfile, function *fn, bool compact)
 {
-  rtx_writer w (outfile, 0, false, compact);
+  rtx_reuse_manager r;
+  rtx_writer w (outfile, 0, false, compact, &r);
+
+  /* Support "reuse_rtx" in the dump.  */
+  for (rtx_insn *insn = get_insns (); insn; insn = NEXT_INSN (insn))
+    r.preprocess (insn);
 
   tree fdecl = fn->decl;
 
diff --git a/gcc/print-rtl.c b/gcc/print-rtl.c
index e7368c7..3bbd395 100644
--- a/gcc/print-rtl.c
+++ b/gcc/print-rtl.c
@@ -51,6 +51,7 @@ along with GCC; see the file COPYING3.  If not see
 #endif
 
 #include "print-rtl.h"
+#include "rtl-iter.h"
 
 /* String printed at beginning of each RTL when it is dumped.
    This string is set to ASM_COMMENT_START when the RTL is dumped in
@@ -74,13 +75,103 @@ int flag_dump_unnumbered_links = 0;
 
 /* Constructor for rtx_writer.  */
 
-rtx_writer::rtx_writer (FILE *outf, int ind, bool simple, bool compact)
+rtx_writer::rtx_writer (FILE *outf, int ind, bool simple, bool compact,
+			rtx_reuse_manager *reuse_manager)
 : m_outfile (outf), m_sawclose (0), m_indent (ind),
-  m_in_call_function_usage (false), m_simple (simple), m_compact (compact)
+  m_in_call_function_usage (false), m_simple (simple), m_compact (compact),
+  m_rtx_reuse_manager (reuse_manager)
 {
 }
 
 #ifndef GENERATOR_FILE
+
+/* rtx_reuse_manager's ctor.  */
+
+rtx_reuse_manager::rtx_reuse_manager ()
+: m_next_id (0)
+{
+  bitmap_initialize (&m_defs_seen, NULL);
+}
+
+/* Determine if X is of a kind suitable for dumping via reuse_rtx.  */
+
+static bool
+uses_rtx_reuse_p (const_rtx x)
+{
+  if (x == NULL)
+    return false;
+
+  switch (GET_CODE (x))
+    {
+    case DEBUG_EXPR:
+    case VALUE:
+    case SCRATCH:
+      return true;
+
+    /* We don't use reuse_rtx for consts.  */
+    CASE_CONST_UNIQUE:
+    default:
+      return false;
+    }
+}
+
+/* Traverse X and its descendents, determining if we see any rtx more than
+   once.  Any rtx suitable for "reuse_rtx" that is seen more than once is
+   assigned an ID.  */
+
+void
+rtx_reuse_manager::preprocess (const_rtx x)
+{
+  subrtx_iterator::array_type array;
+  FOR_EACH_SUBRTX (iter, array, x, NONCONST)
+    if (uses_rtx_reuse_p (*iter))
+      {
+	if (int *count = m_rtx_occurrence_count.get (*iter))
+	  {
+	    if (*(count++) == 1)
+	      m_rtx_reuse_ids.put (*iter, m_next_id++);
+	  }
+	else
+	  m_rtx_occurrence_count.put (*iter, 1);
+      }
+}
+
+/* Return true iff X has been assigned a reuse ID.  If it has,
+   and OUT is non-NULL, then write the reuse ID to *OUT.  */
+
+bool
+rtx_reuse_manager::has_reuse_id (const_rtx x, int *out)
+{
+  int *id = m_rtx_reuse_ids.get (x);
+  if (id)
+    {
+      if (out)
+	*out = *id;
+      return true;
+    }
+  else
+    return false;
+}
+
+/* Determine if set_seen_def has been called for the given reuse ID.  */
+
+bool
+rtx_reuse_manager::seen_def_p (int reuse_id)
+{
+  return bitmap_bit_p (&m_defs_seen, reuse_id);
+}
+
+/* Record that the definition of the given reuse ID has been seen.  */
+
+void
+rtx_reuse_manager::set_seen_def (int reuse_id)
+{
+  bitmap_set_bit (&m_defs_seen, reuse_id);
+}
+
+#endif /* #ifndef GENERATOR_FILE */
+
+#ifndef GENERATOR_FILE
 void
 print_mem_expr (FILE *outfile, const_tree expr)
 {
@@ -631,8 +722,34 @@ rtx_writer::print_rtx (const_rtx in_rtx)
        return;
     }
 
+  fputc ('(', m_outfile);
+
   /* Print name of expression code.  */
 
+  /* Handle reuse.  */
+#ifndef GENERATOR_FILE
+  if (m_rtx_reuse_manager)
+    {
+      int reuse_id;
+      if (m_rtx_reuse_manager->has_reuse_id (in_rtx, &reuse_id))
+	{
+	  /* Have we already seen the defn of this rtx?  */
+	  if (m_rtx_reuse_manager->seen_def_p (reuse_id))
+	    {
+	      fprintf (m_outfile, "reuse_rtx %i)", reuse_id);
+	      m_sawclose = 1;
+	      return;
+	    }
+	  else
+	    {
+	      /* First time we've seen this reused-rtx.  */
+	      fprintf (m_outfile, "%i|", reuse_id);
+	      m_rtx_reuse_manager->set_seen_def (reuse_id);
+	    }
+	}
+    }
+#endif /* #ifndef GENERATOR_FILE */
+
   /* In compact mode, prefix the code of insns with "c",
      giving "cinsn", "cnote" etc.  */
   if (m_compact && is_a <const rtx_insn *, const struct rtx_def> (in_rtx))
@@ -641,14 +758,14 @@ rtx_writer::print_rtx (const_rtx in_rtx)
 	 just "clabel".  */
       rtx_code code = GET_CODE (in_rtx);
       if (code == CODE_LABEL)
-	fprintf (m_outfile, "(clabel");
+	fprintf (m_outfile, "clabel");
       else
-	fprintf (m_outfile, "(c%s", GET_RTX_NAME (code));
+	fprintf (m_outfile, "c%s", GET_RTX_NAME (code));
     }
   else if (m_simple && CONST_INT_P (in_rtx))
-    fputc ('(', m_outfile);
+    ; /* no code.  */
   else
-    fprintf (m_outfile, "(%s", GET_RTX_NAME (GET_CODE (in_rtx)));
+    fprintf (m_outfile, "%s", GET_RTX_NAME (GET_CODE (in_rtx)));
 
   if (! m_simple)
     {
@@ -819,7 +936,7 @@ rtx_writer::finish_directive ()
 void
 print_inline_rtx (FILE *outf, const_rtx x, int ind)
 {
-  rtx_writer w (outf, ind, false, false);
+  rtx_writer w (outf, ind, false, false, NULL);
   w.print_rtx (x);
 }
 
@@ -828,7 +945,7 @@ print_inline_rtx (FILE *outf, const_rtx x, int ind)
 DEBUG_FUNCTION void
 debug_rtx (const_rtx x)
 {
-  rtx_writer w (stderr, 0, false, false);
+  rtx_writer w (stderr, 0, false, false, NULL);
   w.print_rtx (x);
   fprintf (stderr, "\n");
 }
@@ -975,7 +1092,7 @@ rtx_writer::print_rtl (const_rtx rtx_first)
 void
 print_rtl (FILE *outf, const_rtx rtx_first)
 {
-  rtx_writer w (outf, 0, false, false);
+  rtx_writer w (outf, 0, false, false, NULL);
   w.print_rtl (rtx_first);
 }
 
@@ -985,7 +1102,7 @@ print_rtl (FILE *outf, const_rtx rtx_first)
 int
 print_rtl_single (FILE *outf, const_rtx x)
 {
-  rtx_writer w (outf, 0, false, false);
+  rtx_writer w (outf, 0, false, false, NULL);
   return w.print_rtl_single_with_indent (x, 0);
 }
 
@@ -1016,7 +1133,7 @@ rtx_writer::print_rtl_single_with_indent (const_rtx x, int ind)
 void
 print_simple_rtl (FILE *outf, const_rtx x)
 {
-  rtx_writer w (outf, 0, true, false);
+  rtx_writer w (outf, 0, true, false, NULL);
   w.print_rtl (x);
 }
 
diff --git a/gcc/print-rtl.h b/gcc/print-rtl.h
index e722038..5f7cefb 100644
--- a/gcc/print-rtl.h
+++ b/gcc/print-rtl.h
@@ -20,12 +20,19 @@ along with GCC; see the file COPYING3.  If not see
 #ifndef GCC_PRINT_RTL_H
 #define GCC_PRINT_RTL_H
 
+#ifndef GENERATOR_FILE
+#include "bitmap.h"
+#endif /* #ifndef GENERATOR_FILE */
+
+class rtx_reuse_manager;
+
 /* A class for writing rtx to a FILE *.  */
 
 class rtx_writer
 {
  public:
-  rtx_writer (FILE *outfile, int ind, bool simple, bool compact);
+  rtx_writer (FILE *outfile, int ind, bool simple, bool compact,
+	      rtx_reuse_manager *reuse_manager);
 
   void print_rtx (const_rtx in_rtx);
   void print_rtl (const_rtx rtx_first);
@@ -60,6 +67,9 @@ class rtx_writer
        printed with a '%' sigil e.g. "%0" for (LAST_VIRTUAL_REGISTER + 1),
      - insn names are prefixed with "c" (e.g. "cinsn", "cnote", etc).  */
   bool m_compact;
+
+  /* An optional instance of rtx_reuse_manager.  */
+  rtx_reuse_manager *m_rtx_reuse_manager;
 };
 
 #ifdef BUFSIZ
@@ -80,4 +90,73 @@ extern const char *str_pattern_slim (const_rtx);
 
 extern void print_rtx_function (FILE *file, function *fn, bool compact);
 
+#ifndef GENERATOR_FILE
+
+/* For some rtx codes (such as SCRATCH), instances are defined to only be
+   equal for pointer equality: two distinct SCRATCH instances are non-equal.
+   copy_rtx preserves this equality by reusing the SCRATCH instance.
+
+   For example, in this x86 instruction:
+
+      (cinsn (set (mem/v:BLK (scratch:DI) [0  A8])
+                    (unspec:BLK [
+                            (mem/v:BLK (scratch:DI) [0  A8])
+                        ] UNSPEC_MEMORY_BLOCKAGE)) "test.c":2
+                 (nil))
+
+   the two instances of "(scratch:DI)" are actually the same underlying
+   rtx pointer (and thus "equal"), and the insn will only be recognized
+   (as "*memory_blockage") if this pointer-equality is preserved.
+
+   To be able to preserve this pointer-equality when round-tripping
+   through dumping/loading the rtl, we need some syntax.  The first
+   time a reused rtx is encountered in the dump, we prefix it with
+   a reuse ID:
+
+      (0|scratch:DI)
+
+   Subsequent references to the rtx in the dump can be expressed using
+   "reuse_rtx" e.g.:
+
+      (reuse_rtx 0)
+
+   This class is responsible for tracking a set of reuse IDs during a dump.
+
+   Dumping with reuse-support is done in two passes:
+
+   (a) a first pass in which "preprocess" is called on each top-level rtx
+       to be seen in the dump.  This traverses the rtx and its descendents,
+       identifying rtx that will be seen more than once in the actual dump,
+       and assigning them reuse IDs.
+
+   (b) the actual dump, via print_rtx etc.  print_rtx detect the presence
+       of a live rtx_reuse_manager and uses it if there is one.  Any rtx
+       that were assigned reuse IDs will be printed with it the first time
+       that they are seen, and then printed as "(reuse_rtx ID)" subsequently.
+
+   The first phase is needed since otherwise there would be no way to tell
+   if an rtx will be reused when first encountering it.  */
+
+class rtx_reuse_manager
+{
+ public:
+  rtx_reuse_manager ();
+
+  /* The first pass.  */
+  void preprocess (const_rtx x);
+
+  /* The second pass (within print_rtx).  */
+  bool has_reuse_id (const_rtx x, int *out);
+  bool seen_def_p (int reuse_id);
+  void set_seen_def (int reuse_id);
+
+ private:
+  hash_map<const_rtx, int> m_rtx_occurrence_count;
+  hash_map<const_rtx, int> m_rtx_reuse_ids;
+  bitmap_head m_defs_seen;
+  int m_next_id;
+};
+
+#endif /* #ifndef GENERATOR_FILE */
+
 #endif  // GCC_PRINT_RTL_H
diff --git a/gcc/rtl-tests.c b/gcc/rtl-tests.c
index 228226b..8edddfb 100644
--- a/gcc/rtl-tests.c
+++ b/gcc/rtl-tests.c
@@ -62,11 +62,12 @@ verify_print_pattern (const char *expected, rtx pat)
    Use LOC as the effective location when reporting errors.  */
 
 void
-assert_rtl_dump_eq (const location &loc, const char *expected_dump, rtx x)
+assert_rtl_dump_eq (const location &loc, const char *expected_dump, rtx x,
+		    rtx_reuse_manager *reuse_manager)
 {
   named_temp_file tmp_out (".rtl");
   FILE *outfile = fopen (tmp_out.get_filename (), "w");
-  rtx_writer w (outfile, 0, false, true);
+  rtx_writer w (outfile, 0, false, true, reuse_manager);
   w.print_rtl (x);
   fclose (outfile);
 
@@ -128,6 +129,53 @@ test_dumping_insns ()
   ASSERT_RTL_DUMP_EQ ("(clabel 0 42 (\"some_label\"))\n", label);
 }
 
+/* Manually exercise the rtx_reuse_manager code.  */
+
+static void
+test_dumping_rtx_reuse ()
+{
+  rtx_reuse_manager r;
+
+  rtx x = rtx_alloc (SCRATCH);
+  rtx y = rtx_alloc (SCRATCH);
+  rtx z = rtx_alloc (SCRATCH);
+
+  /* x and y will be seen more than once.  */
+  r.preprocess (x);
+  r.preprocess (x);
+  r.preprocess (y);
+  r.preprocess (y);
+
+  /* z will be only seen once.  */
+  r.preprocess (z);
+
+  /* Verify that x and y have been assigned reuse IDs.  */
+  int reuse_id_for_x;
+  ASSERT_TRUE (r.has_reuse_id (x, &reuse_id_for_x));
+  ASSERT_EQ (0, reuse_id_for_x);
+
+  int reuse_id_for_y;
+  ASSERT_TRUE (r.has_reuse_id (y, &reuse_id_for_y));
+  ASSERT_EQ (1, reuse_id_for_y);
+
+  /* z is only seen once and thus shouldn't get a reuse ID.  */
+  ASSERT_FALSE (r.has_reuse_id (z, NULL));
+
+  /* The first dumps of x and y should be prefixed by reuse ID;
+     all subsequent dumps of them should show up as "reuse_rtx".  */
+  ASSERT_RTL_DUMP_EQ_WITH_REUSE ("(0|scratch)", x, &r);
+  ASSERT_RTL_DUMP_EQ_WITH_REUSE ("(reuse_rtx 0)", x, &r);
+  ASSERT_RTL_DUMP_EQ_WITH_REUSE ("(reuse_rtx 0)", x, &r);
+
+  ASSERT_RTL_DUMP_EQ_WITH_REUSE ("(1|scratch)", y, &r);
+  ASSERT_RTL_DUMP_EQ_WITH_REUSE ("(reuse_rtx 1)", y, &r);
+  ASSERT_RTL_DUMP_EQ_WITH_REUSE ("(reuse_rtx 1)", y, &r);
+
+  /* z only appears once and thus shouldn't be prefixed with a
+     reuse ID.  */
+  ASSERT_RTL_DUMP_EQ_WITH_REUSE ("(scratch)", z, &r);
+}
+
 /* Unit testing of "single_set".  */
 
 static void
@@ -187,6 +235,7 @@ rtl_tests_c_tests ()
 {
   test_dumping_regs ();
   test_dumping_insns ();
+  test_dumping_rtx_reuse ();
   test_single_set ();
   test_uncond_jump ();
 
diff --git a/gcc/selftest-rtl.h b/gcc/selftest-rtl.h
index 0f0e167..f505018 100644
--- a/gcc/selftest-rtl.h
+++ b/gcc/selftest-rtl.h
@@ -25,18 +25,27 @@ along with GCC; see the file COPYING3.  If not see
 
 #if CHECKING_P
 
+class rtx_reuse_manager;
+
 namespace selftest {
 
 /* Verify that X is dumped as EXPECTED_DUMP, using compact mode.
    Use LOC as the effective location when reporting errors.  */
 
 extern void
-assert_rtl_dump_eq (const location &loc, const char *expected_dump, rtx x);
+assert_rtl_dump_eq (const location &loc, const char *expected_dump, rtx x,
+		    rtx_reuse_manager *reuse_manager);
 
 /* Verify that RTX is dumped as EXPECTED_DUMP, using compact mode.  */
 
 #define ASSERT_RTL_DUMP_EQ(EXPECTED_DUMP, RTX) \
-  assert_rtl_dump_eq (SELFTEST_LOCATION, (EXPECTED_DUMP), (RTX))
+  assert_rtl_dump_eq (SELFTEST_LOCATION, (EXPECTED_DUMP), (RTX), NULL)
+
+/* As above, but using REUSE_MANAGER when dumping.  */
+
+#define ASSERT_RTL_DUMP_EQ_WITH_REUSE(EXPECTED_DUMP, RTX, REUSE_MANAGER) \
+  assert_rtl_dump_eq (SELFTEST_LOCATION, (EXPECTED_DUMP), (RTX), \
+		      (REUSE_MANAGER))
 
 } /* end of namespace selftest.  */
 
-- 
1.8.5.3