[PATCH 1/3] Support get_or_insert in ordered_hash_map

2023-07-31 Thread Andrzej Turko via Gcc-patches 
Get_or_insert method is already supported by the unordered hash map.
Adding it to the ordered map enables us to replace the unordered map
with the ordered one in cases where ordering may be useful.

Signed-off-by: Andrzej Turko 

gcc/ChangeLog:

* ordered-hash-map.h: Add get_or_insert.
* Makefile.in: Require the ordered map header for genmatch.o.
* ordered-hash-map-tests.cc: Use get_or_insert in tests.

Signed-off-by: Andrzej Turko 
---
 gcc/Makefile.in   |  4 ++--
 gcc/ordered-hash-map-tests.cc | 19 +++
 gcc/ordered-hash-map.h| 26 ++
 3 files changed, 43 insertions(+), 6 deletions(-)

diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index e99628cec07..2429128cbf2 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -3004,8 +3004,8 @@ build/genhooks.o : genhooks.cc $(TARGET_DEF) 
$(C_TARGET_DEF)  \
   $(COMMON_TARGET_DEF) $(D_TARGET_DEF) $(BCONFIG_H) $(SYSTEM_H) errors.h
 build/genmddump.o : genmddump.cc $(RTL_BASE_H) $(BCONFIG_H) $(SYSTEM_H)
\
   $(CORETYPES_H) $(GTM_H) errors.h $(READ_MD_H) $(GENSUPPORT_H)
-build/genmatch.o : genmatch.cc $(BCONFIG_H) $(SYSTEM_H) \
-  $(CORETYPES_H) errors.h $(HASH_TABLE_H) hash-map.h $(GGC_H) is-a.h \
+build/genmatch.o : genmatch.cc $(BCONFIG_H) $(SYSTEM_H) $(CORETYPES_H) \
+  errors.h $(HASH_TABLE_H) hash-map.h $(GGC_H) is-a.h ordered-hash-map.h \
   tree.def builtins.def internal-fn.def case-cfn-macros.h $(CPPLIB_H)
 build/gencfn-macros.o : gencfn-macros.cc $(BCONFIG_H) $(SYSTEM_H)  \
   $(CORETYPES_H) errors.h $(HASH_TABLE_H) hash-set.h builtins.def  \
diff --git a/gcc/ordered-hash-map-tests.cc b/gcc/ordered-hash-map-tests.cc
index 1c26bbfa979..55894c25fa0 100644
--- a/gcc/ordered-hash-map-tests.cc
+++ b/gcc/ordered-hash-map-tests.cc
@@ -58,6 +58,7 @@ static void
 test_map_of_strings_to_int ()
 {
   ordered_hash_map  m;
+  bool existed;
 
   const char *ostrich = "ostrich";
   const char *elephant = "elephant";
@@ -74,17 +75,23 @@ test_map_of_strings_to_int ()
   ASSERT_EQ (false, m.put (ostrich, 2));
   ASSERT_EQ (false, m.put (elephant, 4));
   ASSERT_EQ (false, m.put (ant, 6));
-  ASSERT_EQ (false, m.put (spider, 8));
+  existed = true;
+  int &value = m.get_or_insert (spider, &existed);
+  value = 8;
+  ASSERT_EQ (false, existed);
   ASSERT_EQ (false, m.put (millipede, 750));
   ASSERT_EQ (false, m.put (eric, 3));
 
+
   /* Verify that we can recover the stored values.  */
   ASSERT_EQ (6, m.elements ());
   ASSERT_EQ (2, *m.get (ostrich));
   ASSERT_EQ (4, *m.get (elephant));
   ASSERT_EQ (6, *m.get (ant));
   ASSERT_EQ (8, *m.get (spider));
-  ASSERT_EQ (750, *m.get (millipede));
+  existed = false;
+  ASSERT_EQ (750, m.get_or_insert (millipede, &existed));
+  ASSERT_EQ (true, existed);
   ASSERT_EQ (3, *m.get (eric));
 
   /* Verify that the order of insertion is preserved.  */
@@ -113,6 +120,7 @@ test_map_of_int_to_strings ()
 {
   const int EMPTY = -1;
   const int DELETED = -2;
+  bool existed;
   typedef int_hash  int_hash_t;
   ordered_hash_map  m;
 
@@ -131,7 +139,9 @@ test_map_of_int_to_strings ()
   ASSERT_EQ (false, m.put (2, ostrich));
   ASSERT_EQ (false, m.put (4, elephant));
   ASSERT_EQ (false, m.put (6, ant));
-  ASSERT_EQ (false, m.put (8, spider));
+  const char* &value = m.get_or_insert (8, &existed);
+  value = spider;
+  ASSERT_EQ (false, existed);
   ASSERT_EQ (false, m.put (750, millipede));
   ASSERT_EQ (false, m.put (3, eric));
 
@@ -141,7 +151,8 @@ test_map_of_int_to_strings ()
   ASSERT_EQ (*m.get (4), elephant);
   ASSERT_EQ (*m.get (6), ant);
   ASSERT_EQ (*m.get (8), spider);
-  ASSERT_EQ (*m.get (750), millipede);
+  ASSERT_EQ (m.get_or_insert (750, &existed), millipede);
+  ASSERT_EQ (existed, TRUE);
   ASSERT_EQ (*m.get (3), eric);
 
   /* Verify that the order of insertion is preserved.  */
diff --git a/gcc/ordered-hash-map.h b/gcc/ordered-hash-map.h
index 6b68cc96305..9fc875182e1 100644
--- a/gcc/ordered-hash-map.h
+++ b/gcc/ordered-hash-map.h
@@ -76,6 +76,32 @@ public:
 return m_map.get (k);
   }
 
+  /* Return a reference to the value for the passed in key, creating the entry
+if it doesn't already exist.  If existed is not NULL then it is set to
+false if the key was not previously in the map, and true otherwise.  */
+
+  Value &get_or_insert (const Key &k, bool *existed = NULL)
+  {
+bool _existed;
+Value &ret = m_map.get_or_insert (k, &_existed);
+
+if (!_existed)
+  {
+   bool key_present;
+   int &slot = m_key_index.get_or_insert (k, &key_present);
+   if (!key_present)
+ {
+   slot = m_keys.length ();
+   m_keys.safe_push (k);
+ }
+  }
+
+if (existed)
+  *existed = _existed;
+
+return ret;
+  }
+
   /* Removing a key removes it from the map, but retains the insertion
  order.  */
 
-- 
2.34.1

[PATCH 2/3] genmatch: Reduce variability of generated code

2023-07-31 Thread Andrzej Turko via Gcc-patches 
So far genmatch has been using an unordered map to store information about
functions to be generated. Since corresponding locations from match.pd were
used as keys in the map, even small changes to match.pd which caused
line number changes would change the order in which the functions are
generated. This would reshuffle the functions between the generated .cc files.
This way even a minimal modification to match.pd forces recompilation of all
object files originating from match.pd on rebuild.

This commit makes sure that functions are generated in the order of their
processing (in contrast to the random order based on hashes of their
locations in match.pd). This is done by replacing the unordered map with an
ordered one. This way small changes to match.pd does not cause function
renaming and reshuffling among generated source files.
Together with the subsequent change to logging fprintf calls, this
removes unnecessary changes to the files generated by genmatch allowing
for reuse of already built object files during rebuild. The aim is to
make editing of match.pd and subsequent testing easier.

Signed-off-by: Andrzej Turko 

gcc/ChangeLog:

* genmatch.cc: Make sinfo map ordered.

Signed-off-by: Andrzej Turko 
---
 gcc/genmatch.cc | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/gcc/genmatch.cc b/gcc/genmatch.cc
index 2302f2a7ff0..1deca505603 100644
--- a/gcc/genmatch.cc
+++ b/gcc/genmatch.cc
@@ -29,6 +29,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "hash-table.h"
 #include "hash-set.h"
 #include "is-a.h"
+#include "ordered-hash-map.h"
 
 
 /* Stubs for GGC referenced through instantiations triggered by hash-map.  */
@@ -1684,7 +1685,7 @@ struct sinfo_hashmap_traits : 
simple_hashmap_traits,
   template  static inline void remove (T &) {}
 };
 
-typedef hash_map
+typedef ordered_hash_map
   sinfo_map_t;
 
 /* Current simplifier ID we are processing during insertion into the
-- 
2.34.1

[PATCH 0/3] genmatch: Speed up recompilation after changes to match.pd

2023-07-31 Thread Andrzej Turko via Gcc-patches 
The following reduces the number of object files that need to be rebuilt
after match.pd has been modified. Right now a change to match.pd which
adds/removes a line almost always forces recompilation of all files that
genmatch generates from it. This is because of unnecessary changes to
the generated .cc files:

1. Function names and ordering change as does the way the functions are
distributed across multiple source files.
2. Code locations from match.pd are quoted directly (including line
numbers) by logging fprintf calls.

This patch addresses the those issues without changing the behaviour
of the generated code. The first one is solved by making sure that minor
changes to match.pd do not influence the order in which functions are
generated. The second one by using a lookup table with line numbers.

Now a change to a single function will trigger a rebuild of 4 object
files (one with the function  and the one with the lookup table both for
gimple and generic) instead all of them (20 by default).
For reference, this decreased the rebuild time with 48 threads from 3.5
minutes to 1.5 minutes on my machine.


Note for reviewers: I do not have write access.

Andrzej Turko (3):
  Support get_or_insert in ordered_hash_map
  genmatch: Reduce variability of generated code
  genmatch: Log line numbers indirectly

 gcc/Makefile.in   |  4 +-
 gcc/genmatch.cc   | 76 ++-
 gcc/ordered-hash-map-tests.cc | 19 +++--
 gcc/ordered-hash-map.h| 26 
 4 files changed, 110 insertions(+), 15 deletions(-)

-- 
2.34.1

[PATCH 3/3] genmatch: Log line numbers indirectly

2023-07-31 Thread Andrzej Turko via Gcc-patches 
Currently fprintf calls logging to a dump file take line numbers
in the match.pd file directly as arguments.
When match.pd is edited, referenced code changes line numbers,
which causes changes to many fprintf calls and, thus, to many
(usually all) .cc files generated by genmatch. This forces make
to (unnecessarily) rebuild many .o files.

With this change those logging fprintf calls reference an array
of line numbers, which is defined in one of the produced files.
Thanks to this, when match.pd changes, it is enough to rebuild
that single file and, of course, those actually affected by the
change.

Signed-off-by: Andrzej Turko 

gcc/ChangeLog:

* genmatch.cc: Keep line numbers from match.pd in an array.

Signed-off-by: Andrzej Turko 
---
 gcc/genmatch.cc | 73 +++--
 1 file changed, 65 insertions(+), 8 deletions(-)

diff --git a/gcc/genmatch.cc b/gcc/genmatch.cc
index 1deca505603..0a480a140c9 100644
--- a/gcc/genmatch.cc
+++ b/gcc/genmatch.cc
@@ -217,9 +217,48 @@ fp_decl_done (FILE *f, const char *trailer)
 fprintf (header_file, "%s;", trailer);
 }
 
+/* Line numbers for use by indirect line directives.  */
+static vec dbg_line_numbers;
+
+static void
+write_header_declarations (bool gimple, FILE *f)
+{
+  if (gimple)
+fprintf (f, "\nextern int __gimple_dbg_line_numbers[];\n");
+  else
+fprintf (f, "\nextern int __generic_dbg_line_numbers[];\n");
+}
+
+static void
+define_dbg_line_numbers (bool gimple, FILE *f)
+{
+  if (gimple)
+fprintf (f, "\nint __gimple_dbg_line_numbers[%d] = {",
+   dbg_line_numbers.length ());
+  else
+fprintf (f, "\nint __generic_dbg_line_numbers[%d] = {",
+   dbg_line_numbers.length ());
+
+   if (dbg_line_numbers.is_empty ())
+{
+  fprintf (f, "};\n\n");
+  return;
+}
+
+  for (int i = 0; i < (int)dbg_line_numbers.length () - 1; i++)
+{
+  if (i % 20 == 0)
+   fprintf (f, "\n\t");
+
+  fprintf (f, "%d, ", dbg_line_numbers[i]);
+}
+  fprintf (f, "%d\n};\n\n", dbg_line_numbers.last ());
+}
+
 static void
 output_line_directive (FILE *f, location_t location,
-  bool dumpfile = false, bool fnargs = false)
+ bool dumpfile = false, bool fnargs = false,
+ bool indirect_line_numbers = false, bool gimple = false)
 {
   const line_map_ordinary *map;
   linemap_resolve_location (line_table, location, LRK_SPELLING_LOCATION, &map);
@@ -239,7 +278,20 @@ output_line_directive (FILE *f, location_t location,
++file;
 
   if (fnargs)
-   fprintf (f, "\"%s\", %d", file, loc.line);
+  {
+  if (indirect_line_numbers)
+{
+  if (gimple)
+  fprintf (f, "\"%s\", __gimple_dbg_line_numbers[%d]",
+ file, dbg_line_numbers.length ());
+  else
+  fprintf (f, "\"%s\", __generic_dbg_line_numbers[%d]",
+ file, dbg_line_numbers.length ());
+  dbg_line_numbers.safe_push (loc.line);
+}
+  else
+fprintf (f, "\"%s\", %d", file, loc.line);
+  }
   else
fprintf (f, "%s:%d", file, loc.line);
 }
@@ -3378,7 +3430,8 @@ dt_operand::gen (FILE *f, int indent, bool gimple, int 
depth)
 /* Emit a fprintf to the debug file to the file F, with the INDENT from
either the RESULT location or the S's match location if RESULT is null. */
 static void
-emit_debug_printf (FILE *f, int indent, class simplify *s, operand *result)
+emit_debug_printf (FILE *f, int indent, class simplify *s, operand *result,
+ bool gimple)
 {
   fprintf_indent (f, indent, "if (UNLIKELY (debug_dump)) "
   "fprintf (dump_file, \"%s ",
@@ -3387,7 +3440,7 @@ emit_debug_printf (FILE *f, int indent, class simplify 
*s, operand *result)
   fprintf (f, "%%s:%%d, %%s:%%d\\n\", ");
   output_line_directive (f,
 result ? result->location : s->match->location, true,
-true);
+true, true, gimple);
   fprintf (f, ", __FILE__, __LINE__);\n");
 }
 
@@ -3524,7 +3577,7 @@ dt_simplify::gen_1 (FILE *f, int indent, bool gimple, 
operand *result)
   if (!result)
 {
   /* If there is no result then this is a predicate implementation.  */
-  emit_debug_printf (f, indent, s, result);
+  emit_debug_printf (f, indent, s, result, gimple);
   fprintf_indent (f, indent, "return true;\n");
 }
   else if (gimple)
@@ -3615,7 +3668,7 @@ dt_simplify::gen_1 (FILE *f, int indent, bool gimple, 
operand *result)
}
   else
gcc_unreachable ();
-  emit_debug_printf (f, indent, s, result);
+  emit_debug_printf (f, indent, s, result, gimple);
   fprintf_indent (f, indent, "return true;\n");
 }
   else /* GENERIC */
@@ -3670,7 +3723,7 @@ dt_simplify::gen_1 (FILE *f, int indent, bool gimple, 
operand *result)
}
  if (is_predicate)
{
- emit_debug_printf (f, indent, s, result);
+ emit_debug_printf (f, indent, s, result, gimple);

[PATCH 0/3 v2] genmatch: Speed up recompilation after changes to match.pd

2023-08-02 Thread Andrzej Turko via Gcc-patches 
The following reduces the number of object files that need to be rebuilt
after match.pd has been modified. Right now a change to match.pd which
adds/removes a line almost always forces recompilation of all files that
genmatch generates from it. This is because of unnecessary changes to
the generated .cc files:

1. Function names and ordering change as does the way the functions are
distributed across multiple source files.
2. Code locations from match.pd are quoted directly (including line
numbers) by logging fprintf calls.

This patch addresses the those issues without changing the behaviour
of the generated code. The first one is solved by making sure that minor
changes to match.pd do not influence the order in which functions are
generated. The second one by using a lookup table with line numbers.

Now a change to a single function will trigger a rebuild of 4 object
files (one with the function  and the one with the lookup table both for
gimple and generic) instead all of them (20 by default).
For reference, this decreased the rebuild time with 48 threads from 3.5
minutes to 1.5 minutes on my machine.

V2:
* Placed the change in Makefile.in in the correct commit.
* Used a separate logging function to reduce size of the
executable.

As for Richard Biener's remarks on executable size:

1. The previous version of the change increased the sizes of executables
by 8-12 kB.
2. The current version (with an extra indirection step) did so by
around 150 kB (I suspect that the reason for it may be adding
an additional functions and its overhead, in which case the
actual number of instructions may be smaller in this case).


One can choose between those variants just by taking the third commit either
from this or the previous version of the patch series.

Note for reviewers: I do not have write access.

Andrzej Turko (3):
  Support get_or_insert in ordered_hash_map
  genmatch: Reduce variability of generated code
  genmatch: Log line numbers indirectly

 gcc/Makefile.in   |  4 +-
 gcc/genmatch.cc   | 91 +--
 gcc/ordered-hash-map-tests.cc | 19 ++--
 gcc/ordered-hash-map.h| 26 ++
 4 files changed, 118 insertions(+), 22 deletions(-)

-- 
2.34.1

[PATCH 2/3 v2] genmatch: Reduce variability of generated code

2023-08-02 Thread Andrzej Turko via Gcc-patches 
So far genmatch has been using an unordered map to store information about
functions to be generated. Since corresponding locations from match.pd were
used as keys in the map, even small changes to match.pd which caused
line number changes would change the order in which the functions are
generated. This would reshuffle the functions between the generated .cc files.
This way even a minimal modification to match.pd forces recompilation of all
object files originating from match.pd on rebuild.

This commit makes sure that functions are generated in the order of their
processing (in contrast to the random order based on hashes of their
locations in match.pd). This is done by replacing the unordered map with an
ordered one. This way small changes to match.pd does not cause function
renaming and reshuffling among generated source files.
Together with the subsequent change to logging fprintf calls, this
removes unnecessary changes to the files generated by genmatch allowing
for reuse of already built object files during rebuild. The aim is to
make editing of match.pd and subsequent testing easier.

Signed-off-by: Andrzej Turko 

gcc/ChangeLog:

* genmatch.cc: Make sinfo map ordered.
* Makefile.in: Require the ordered map header for genmatch.o.
---
 gcc/Makefile.in | 4 ++--
 gcc/genmatch.cc | 3 ++-
 2 files changed, 4 insertions(+), 3 deletions(-)

diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index e99628cec07..2429128cbf2 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -3004,8 +3004,8 @@ build/genhooks.o : genhooks.cc $(TARGET_DEF) 
$(C_TARGET_DEF)  \
   $(COMMON_TARGET_DEF) $(D_TARGET_DEF) $(BCONFIG_H) $(SYSTEM_H) errors.h
 build/genmddump.o : genmddump.cc $(RTL_BASE_H) $(BCONFIG_H) $(SYSTEM_H)
\
   $(CORETYPES_H) $(GTM_H) errors.h $(READ_MD_H) $(GENSUPPORT_H)
-build/genmatch.o : genmatch.cc $(BCONFIG_H) $(SYSTEM_H) \
-  $(CORETYPES_H) errors.h $(HASH_TABLE_H) hash-map.h $(GGC_H) is-a.h \
+build/genmatch.o : genmatch.cc $(BCONFIG_H) $(SYSTEM_H) $(CORETYPES_H) \
+  errors.h $(HASH_TABLE_H) hash-map.h $(GGC_H) is-a.h ordered-hash-map.h \
   tree.def builtins.def internal-fn.def case-cfn-macros.h $(CPPLIB_H)
 build/gencfn-macros.o : gencfn-macros.cc $(BCONFIG_H) $(SYSTEM_H)  \
   $(CORETYPES_H) errors.h $(HASH_TABLE_H) hash-set.h builtins.def  \
diff --git a/gcc/genmatch.cc b/gcc/genmatch.cc
index 2302f2a7ff0..1deca505603 100644
--- a/gcc/genmatch.cc
+++ b/gcc/genmatch.cc
@@ -29,6 +29,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "hash-table.h"
 #include "hash-set.h"
 #include "is-a.h"
+#include "ordered-hash-map.h"
 
 
 /* Stubs for GGC referenced through instantiations triggered by hash-map.  */
@@ -1684,7 +1685,7 @@ struct sinfo_hashmap_traits : 
simple_hashmap_traits,
   template  static inline void remove (T &) {}
 };
 
-typedef hash_map
+typedef ordered_hash_map
   sinfo_map_t;
 
 /* Current simplifier ID we are processing during insertion into the
-- 
2.34.1

[PATCH 3/3 v2] genmatch: Log line numbers indirectly

2023-08-02 Thread Andrzej Turko via Gcc-patches 
Currently fprintf calls logging to a dump file take line numbers
in the match.pd file directly as arguments.
When match.pd is edited, referenced code changes line numbers,
which causes changes to many fprintf calls and, thus, to many
(usually all) .cc files generated by genmatch. This forces make
to (unnecessarily) rebuild many .o files.

This change replaces those logging fprintf calls with calls to
a dedicated logging function. Because it reads the line numbers
from the lookup table, it is enough to pass a corresponding index.
Thanks to this, when match.pd changes, it is enough to rebuild
the file containing the lookup table and, of course, those
actually affected by the change.

Signed-off-by: Andrzej Turko 

gcc/ChangeLog:

* genmatch.cc: Log line numbers indirectly.
---
 gcc/genmatch.cc | 88 -
 1 file changed, 73 insertions(+), 15 deletions(-)

diff --git a/gcc/genmatch.cc b/gcc/genmatch.cc
index 1deca505603..be6c11c347f 100644
--- a/gcc/genmatch.cc
+++ b/gcc/genmatch.cc
@@ -217,9 +217,56 @@ fp_decl_done (FILE *f, const char *trailer)
 fprintf (header_file, "%s;", trailer);
 }
 
+/* Line numbers for use by indirect line directives.  */
+static vec dbg_line_numbers;
+
+static void
+write_header_declarations (bool gimple, FILE *f)
+{
+  fprintf (f, "\nextern void\n%s_dump_logs (const char *file1, int line1_id, "
+ "const char *file2, int line2, bool simplify);\n",
+ gimple ? "gimple" : "generic");
+}
+
+static void
+define_dbg_line_numbers (bool gimple, FILE *f)
+{
+
+  if (dbg_line_numbers.is_empty ())
+{
+  fprintf (f, "};\n\n");
+  return;
+}
+
+  fprintf (f , "void\n%s_dump_logs (const char *file1, int line1_id,"
+   "const char *file2, int line2, bool simplify)\n{\n",
+   gimple ? "gimple" : "generic");
+
+  fprintf_indent (f, 2, "static int __dbg_line_numbers[%d] = {",
+ dbg_line_numbers.length ());
+
+  for (int i = 0; i < (int)dbg_line_numbers.length () - 1; i++)
+{
+  if (i % 20 == 0)
+   fprintf (f, "\n\t");
+
+  fprintf (f, "%d, ", dbg_line_numbers[i]);
+}
+  fprintf (f, "%d\n  };\n\n", dbg_line_numbers.last ());
+
+
+  fprintf_indent (f, 2, "fprintf (dump_file, \"%%s "
+ "%%s: __dbg_line_numbers[%%d], %%s:%%d\\n\",\n");
+  fprintf_indent (f, 10, "simplify ? \"Applying pattern\" : "
+ "\"Matching expression\", file1, line1_id, file2, line2);");
+
+  fprintf (f, "\n}\n\n");
+}
+
 static void
 output_line_directive (FILE *f, location_t location,
-  bool dumpfile = false, bool fnargs = false)
+ bool dumpfile = false, bool fnargs = false,
+ bool indirect_line_numbers = false)
 {
   const line_map_ordinary *map;
   linemap_resolve_location (line_table, location, LRK_SPELLING_LOCATION, &map);
@@ -239,7 +286,15 @@ output_line_directive (FILE *f, location_t location,
++file;
 
   if (fnargs)
-   fprintf (f, "\"%s\", %d", file, loc.line);
+  {
+  if (indirect_line_numbers)
+{
+  fprintf (f, "\"%s\", %d", file, dbg_line_numbers.length ());
+  dbg_line_numbers.safe_push (loc.line);
+}
+  else
+fprintf (f, "\"%s\", %d", file, loc.line);
+  }
   else
fprintf (f, "%s:%d", file, loc.line);
 }
@@ -3375,20 +3430,19 @@ dt_operand::gen (FILE *f, int indent, bool gimple, int 
depth)
 }
 }
 
-/* Emit a fprintf to the debug file to the file F, with the INDENT from
+/* Emit a logging call to the debug file to the file F, with the INDENT from
either the RESULT location or the S's match location if RESULT is null. */
 static void
-emit_debug_printf (FILE *f, int indent, class simplify *s, operand *result)
+emit_logging_call (FILE *f, int indent, class simplify *s, operand *result,
+ bool gimple)
 {
   fprintf_indent (f, indent, "if (UNLIKELY (debug_dump)) "
-  "fprintf (dump_file, \"%s ",
-  s->kind == simplify::SIMPLIFY
-  ? "Applying pattern" : "Matching expression");
-  fprintf (f, "%%s:%%d, %%s:%%d\\n\", ");
+  "%s_dump_logs (", gimple ? "gimple" : "generic");
   output_line_directive (f,
-result ? result->location : s->match->location, true,
-true);
-  fprintf (f, ", __FILE__, __LINE__);\n");
+   result ? result->location : s->match->location,
+   true, true, true);
+  fprintf (f, ", __FILE__, __LINE__, %s);\n",
+ s->kind == simplify::SIMPLIFY ? "true" : "false");
 }
 
 /* Generate code for the '(if ...)', '(with ..)' and actual transform
@@ -3524,7 +3578,7 @@ dt_simplify::gen_1 (FILE *f, int indent, bool gimple, 
operand *result)
   if (!result)
 {
   /* If there is no result then this is a predicate implementation.  */
-  emit_debug_printf (f, indent, s, result);
+  emit_logging_call (f, indent, s, result, gimple);
   fprin

[PATCH 1/3 v2] Support get_or_insert in ordered_hash_map

2023-08-02 Thread Andrzej Turko via Gcc-patches 
Get_or_insert method is already supported by the unordered hash map.
Adding it to the ordered map enables us to replace the unordered map
with the ordered one in cases where ordering may be useful.

Signed-off-by: Andrzej Turko 

gcc/ChangeLog:

* ordered-hash-map.h: Add get_or_insert.
* ordered-hash-map-tests.cc: Use get_or_insert in tests.
---
 gcc/ordered-hash-map-tests.cc | 19 +++
 gcc/ordered-hash-map.h| 26 ++
 2 files changed, 41 insertions(+), 4 deletions(-)

diff --git a/gcc/ordered-hash-map-tests.cc b/gcc/ordered-hash-map-tests.cc
index 1c26bbfa979..55894c25fa0 100644
--- a/gcc/ordered-hash-map-tests.cc
+++ b/gcc/ordered-hash-map-tests.cc
@@ -58,6 +58,7 @@ static void
 test_map_of_strings_to_int ()
 {
   ordered_hash_map  m;
+  bool existed;
 
   const char *ostrich = "ostrich";
   const char *elephant = "elephant";
@@ -74,17 +75,23 @@ test_map_of_strings_to_int ()
   ASSERT_EQ (false, m.put (ostrich, 2));
   ASSERT_EQ (false, m.put (elephant, 4));
   ASSERT_EQ (false, m.put (ant, 6));
-  ASSERT_EQ (false, m.put (spider, 8));
+  existed = true;
+  int &value = m.get_or_insert (spider, &existed);
+  value = 8;
+  ASSERT_EQ (false, existed);
   ASSERT_EQ (false, m.put (millipede, 750));
   ASSERT_EQ (false, m.put (eric, 3));
 
+
   /* Verify that we can recover the stored values.  */
   ASSERT_EQ (6, m.elements ());
   ASSERT_EQ (2, *m.get (ostrich));
   ASSERT_EQ (4, *m.get (elephant));
   ASSERT_EQ (6, *m.get (ant));
   ASSERT_EQ (8, *m.get (spider));
-  ASSERT_EQ (750, *m.get (millipede));
+  existed = false;
+  ASSERT_EQ (750, m.get_or_insert (millipede, &existed));
+  ASSERT_EQ (true, existed);
   ASSERT_EQ (3, *m.get (eric));
 
   /* Verify that the order of insertion is preserved.  */
@@ -113,6 +120,7 @@ test_map_of_int_to_strings ()
 {
   const int EMPTY = -1;
   const int DELETED = -2;
+  bool existed;
   typedef int_hash  int_hash_t;
   ordered_hash_map  m;
 
@@ -131,7 +139,9 @@ test_map_of_int_to_strings ()
   ASSERT_EQ (false, m.put (2, ostrich));
   ASSERT_EQ (false, m.put (4, elephant));
   ASSERT_EQ (false, m.put (6, ant));
-  ASSERT_EQ (false, m.put (8, spider));
+  const char* &value = m.get_or_insert (8, &existed);
+  value = spider;
+  ASSERT_EQ (false, existed);
   ASSERT_EQ (false, m.put (750, millipede));
   ASSERT_EQ (false, m.put (3, eric));
 
@@ -141,7 +151,8 @@ test_map_of_int_to_strings ()
   ASSERT_EQ (*m.get (4), elephant);
   ASSERT_EQ (*m.get (6), ant);
   ASSERT_EQ (*m.get (8), spider);
-  ASSERT_EQ (*m.get (750), millipede);
+  ASSERT_EQ (m.get_or_insert (750, &existed), millipede);
+  ASSERT_EQ (existed, TRUE);
   ASSERT_EQ (*m.get (3), eric);
 
   /* Verify that the order of insertion is preserved.  */
diff --git a/gcc/ordered-hash-map.h b/gcc/ordered-hash-map.h
index 6b68cc96305..9fc875182e1 100644
--- a/gcc/ordered-hash-map.h
+++ b/gcc/ordered-hash-map.h
@@ -76,6 +76,32 @@ public:
 return m_map.get (k);
   }
 
+  /* Return a reference to the value for the passed in key, creating the entry
+if it doesn't already exist.  If existed is not NULL then it is set to
+false if the key was not previously in the map, and true otherwise.  */
+
+  Value &get_or_insert (const Key &k, bool *existed = NULL)
+  {
+bool _existed;
+Value &ret = m_map.get_or_insert (k, &_existed);
+
+if (!_existed)
+  {
+   bool key_present;
+   int &slot = m_key_index.get_or_insert (k, &key_present);
+   if (!key_present)
+ {
+   slot = m_keys.length ();
+   m_keys.safe_push (k);
+ }
+  }
+
+if (existed)
+  *existed = _existed;
+
+return ret;
+  }
+
   /* Removing a key removes it from the map, but retains the insertion
  order.  */
 
-- 
2.34.1

[PATCH 2/3 v3] genmatch: Reduce variability of generated code

2023-08-03 Thread Andrzej Turko via Gcc-patches 
So far genmatch has been using an unordered map to store information about
functions to be generated. Since corresponding locations from match.pd were
used as keys in the map, even small changes to match.pd which caused
line number changes would change the order in which the functions are
generated. This would reshuffle the functions between the generated .cc files.
This way even a minimal modification to match.pd forces recompilation of all
object files originating from match.pd on rebuild.

This commit makes sure that functions are generated in the order of their
processing (in contrast to the random order based on hashes of their
locations in match.pd). This is done by replacing the unordered map with an
ordered one. This way small changes to match.pd does not cause function
renaming and reshuffling among generated source files.
Together with the subsequent change to logging fprintf calls, this
removes unnecessary changes to the files generated by genmatch allowing
for reuse of already built object files during rebuild. The aim is to
make editing of match.pd and subsequent testing easier.

Signed-off-by: Andrzej Turko 

gcc/ChangeLog:

* genmatch.cc: Make sinfo map ordered.
* Makefile.in: Require the ordered map header for genmatch.o.
---
 gcc/Makefile.in | 4 ++--
 gcc/genmatch.cc | 3 ++-
 2 files changed, 4 insertions(+), 3 deletions(-)

diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index e99628cec07..2429128cbf2 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -3004,8 +3004,8 @@ build/genhooks.o : genhooks.cc $(TARGET_DEF) 
$(C_TARGET_DEF)  \
   $(COMMON_TARGET_DEF) $(D_TARGET_DEF) $(BCONFIG_H) $(SYSTEM_H) errors.h
 build/genmddump.o : genmddump.cc $(RTL_BASE_H) $(BCONFIG_H) $(SYSTEM_H)
\
   $(CORETYPES_H) $(GTM_H) errors.h $(READ_MD_H) $(GENSUPPORT_H)
-build/genmatch.o : genmatch.cc $(BCONFIG_H) $(SYSTEM_H) \
-  $(CORETYPES_H) errors.h $(HASH_TABLE_H) hash-map.h $(GGC_H) is-a.h \
+build/genmatch.o : genmatch.cc $(BCONFIG_H) $(SYSTEM_H) $(CORETYPES_H) \
+  errors.h $(HASH_TABLE_H) hash-map.h $(GGC_H) is-a.h ordered-hash-map.h \
   tree.def builtins.def internal-fn.def case-cfn-macros.h $(CPPLIB_H)
 build/gencfn-macros.o : gencfn-macros.cc $(BCONFIG_H) $(SYSTEM_H)  \
   $(CORETYPES_H) errors.h $(HASH_TABLE_H) hash-set.h builtins.def  \
diff --git a/gcc/genmatch.cc b/gcc/genmatch.cc
index 2302f2a7ff0..1deca505603 100644
--- a/gcc/genmatch.cc
+++ b/gcc/genmatch.cc
@@ -29,6 +29,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "hash-table.h"
 #include "hash-set.h"
 #include "is-a.h"
+#include "ordered-hash-map.h"
 
 
 /* Stubs for GGC referenced through instantiations triggered by hash-map.  */
@@ -1684,7 +1685,7 @@ struct sinfo_hashmap_traits : 
simple_hashmap_traits,
   template  static inline void remove (T &) {}
 };
 
-typedef hash_map
+typedef ordered_hash_map
   sinfo_map_t;
 
 /* Current simplifier ID we are processing during insertion into the
-- 
2.34.1

[PATCH 3/3 v3] genmatch: Log line numbers indirectly

2023-08-03 Thread Andrzej Turko via Gcc-patches 
Currently fprintf calls logging to a dump file take line numbers
in the match.pd file directly as arguments.
When match.pd is edited, referenced code changes line numbers,
which causes changes to many fprintf calls and, thus, to many
(usually all) .cc files generated by genmatch. This forces make
to (unnecessarily) rebuild many .o files.

This change replaces those logging fprintf calls with calls to
a dedicated logging function. Because it reads the line numbers
from the lookup table, it is enough to pass a corresponding index.
Thanks to this, when match.pd changes, it is enough to rebuild
the file containing the lookup table and, of course, those
actually affected by the change.

Signed-off-by: Andrzej Turko 

gcc/ChangeLog:

* genmatch.cc: Log line numbers indirectly.
---
 gcc/genmatch.cc | 89 -
 1 file changed, 74 insertions(+), 15 deletions(-)

diff --git a/gcc/genmatch.cc b/gcc/genmatch.cc
index 1deca505603..63d6ba6dab0 100644
--- a/gcc/genmatch.cc
+++ b/gcc/genmatch.cc
@@ -217,9 +217,57 @@ fp_decl_done (FILE *f, const char *trailer)
 fprintf (header_file, "%s;", trailer);
 }
 
+/* Line numbers for use by indirect line directives.  */
+static vec dbg_line_numbers;
+
+static void
+write_header_declarations (bool gimple, FILE *f)
+{
+  fprintf (f, "\nextern void\n%s_dump_logs (const char *file1, int line1_id, "
+ "const char *file2, int line2, bool simplify);\n",
+ gimple ? "gimple" : "generic");
+}
+
+static void
+define_dump_logs (bool gimple, FILE *f)
+{
+
+  if (dbg_line_numbers.is_empty ())
+{
+  fprintf (f, "};\n\n");
+  return;
+}
+
+  fprintf (f , "void\n%s_dump_logs (const char *file1, int line1_id, "
+   "const char *file2, int line2, bool simplify)\n{\n",
+   gimple ? "gimple" : "generic");
+
+  fprintf_indent (f, 2, "static int dbg_line_numbers[%d] = {",
+ dbg_line_numbers.length ());
+
+  for (int i = 0; i < (int)dbg_line_numbers.length () - 1; i++)
+{
+  if (i % 20 == 0)
+   fprintf (f, "\n\t");
+
+  fprintf (f, "%d, ", dbg_line_numbers[i]);
+}
+  fprintf (f, "%d\n  };\n\n", dbg_line_numbers.last ());
+
+
+  fprintf_indent (f, 2, "fprintf (dump_file, \"%%s "
+ "%%s:%%d, %%s:%%d\\n\",\n");
+  fprintf_indent (f, 10, "simplify ? \"Applying pattern\" : "
+ "\"Matching expression\", file1, "
+ "dbg_line_numbers[line1_id], file2, line2);");
+
+  fprintf (f, "\n}\n\n");
+}
+
 static void
 output_line_directive (FILE *f, location_t location,
-  bool dumpfile = false, bool fnargs = false)
+ bool dumpfile = false, bool fnargs = false,
+ bool indirect_line_numbers = false)
 {
   const line_map_ordinary *map;
   linemap_resolve_location (line_table, location, LRK_SPELLING_LOCATION, &map);
@@ -239,7 +287,15 @@ output_line_directive (FILE *f, location_t location,
++file;
 
   if (fnargs)
-   fprintf (f, "\"%s\", %d", file, loc.line);
+  {
+if (indirect_line_numbers)
+  {
+   fprintf (f, "\"%s\", %d", file, dbg_line_numbers.length ());
+   dbg_line_numbers.safe_push (loc.line);
+  }
+else
+  fprintf (f, "\"%s\", %d", file, loc.line);
+  }
   else
fprintf (f, "%s:%d", file, loc.line);
 }
@@ -3375,20 +3431,19 @@ dt_operand::gen (FILE *f, int indent, bool gimple, int 
depth)
 }
 }
 
-/* Emit a fprintf to the debug file to the file F, with the INDENT from
+/* Emit a logging call to the debug file to the file F, with the INDENT from
either the RESULT location or the S's match location if RESULT is null. */
 static void
-emit_debug_printf (FILE *f, int indent, class simplify *s, operand *result)
+emit_logging_call (FILE *f, int indent, class simplify *s, operand *result,
+ bool gimple)
 {
   fprintf_indent (f, indent, "if (UNLIKELY (debug_dump)) "
-  "fprintf (dump_file, \"%s ",
-  s->kind == simplify::SIMPLIFY
-  ? "Applying pattern" : "Matching expression");
-  fprintf (f, "%%s:%%d, %%s:%%d\\n\", ");
+  "%s_dump_logs (", gimple ? "gimple" : "generic");
   output_line_directive (f,
-result ? result->location : s->match->location, true,
-true);
-  fprintf (f, ", __FILE__, __LINE__);\n");
+   result ? result->location : s->match->location,
+   true, true, true);
+  fprintf (f, ", __FILE__, __LINE__, %s);\n",
+ s->kind == simplify::SIMPLIFY ? "true" : "false");
 }
 
 /* Generate code for the '(if ...)', '(with ..)' and actual transform
@@ -3524,7 +3579,7 @@ dt_simplify::gen_1 (FILE *f, int indent, bool gimple, 
operand *result)
   if (!result)
 {
   /* If there is no result then this is a predicate implementation.  */
-  emit_debug_printf (f, indent, s, result);
+  emit_logging_call (f, indent, s, result,

[PATCH 0/3 v3] genmatch: Speed up recompilation after changes to match.pd

2023-08-03 Thread Andrzej Turko via Gcc-patches 
The following reduces the number of object files that need to be rebuilt
after match.pd has been modified. Right now a change to match.pd which
adds/removes a line almost always forces recompilation of all files that
genmatch generates from it. This is because of unnecessary changes to
the generated .cc files:

1. Function names and ordering change as does the way the functions are
distributed across multiple source files.
2. Code locations from match.pd are quoted directly (including line
numbers) by logging fprintf calls.

This patch addresses the those issues without changing the behaviour
of the generated code. The first one is solved by making sure that minor
changes to match.pd do not influence the order in which functions are
generated. The second one by using a lookup table with line numbers.

Now a change to a single function will trigger a rebuild of 4 object
files (one with the function  and the one with the lookup table both for
gimple and generic) instead all of them (20 by default).
For reference, this decreased the rebuild time with 48 threads from 3.5
minutes to 1.5 minutes on my machine.

V2:
* Placed the change in Makefile.in in the correct commit.
* Used a separate logging function to reduce size of the
executable.

V3:
* Fix a bug from 'genmatch: Log line numbers indirectly',
which was introduced in V2.
   

As for Richard Biener's remarks on executable size (cc1plus):

1. The first version of the change decreased (sic!) the executable size
by approximately 120 kB (.text and .data sections grew by
correspondingly 14 and 2 kB, but .debug_info section shrank by
roughly 170 kB).
2. In the current version (V3) the binary size increases by 36 kB (.text
grows by 3 kB and .rodata by 14 kB, the rest of the increase can
be mostly attributed to debug sections).

One can choose between those variants just by taking the third commit
either from this or the first version of the patch series.


Possible optimization:

Currently, the lookup table for line numbers contains duplicate values.
If I remove them, the table would shrink by 40-50% reducing the increase
in .data sections. Is it worth pursuing? And if so, would it be better
if I integrate this into this patch series or implement it separately?
Also, can I assume that genmatch is producing source code using a single
input file per invocation? Currently, this is the case.


Note for reviewers: I do not have write access.


Andrzej Turko (3):
  Support get_or_insert in ordered_hash_map
  genmatch: Reduce variability of generated code
  genmatch: Log line numbers indirectly

 gcc/Makefile.in   |  4 +-
 gcc/genmatch.cc   | 92 +--
 gcc/ordered-hash-map-tests.cc | 19 ++--
 gcc/ordered-hash-map.h| 26 ++
 4 files changed, 119 insertions(+), 22 deletions(-)

-- 
2.34.1

[PATCH 1/3 v3] Support get_or_insert in ordered_hash_map

2023-08-03 Thread Andrzej Turko via Gcc-patches 
Get_or_insert method is already supported by the unordered hash map.
Adding it to the ordered map enables us to replace the unordered map
with the ordered one in cases where ordering may be useful.

Signed-off-by: Andrzej Turko 

gcc/ChangeLog:

* ordered-hash-map.h: Add get_or_insert.
* ordered-hash-map-tests.cc: Use get_or_insert in tests.
---
 gcc/ordered-hash-map-tests.cc | 19 +++
 gcc/ordered-hash-map.h| 26 ++
 2 files changed, 41 insertions(+), 4 deletions(-)

diff --git a/gcc/ordered-hash-map-tests.cc b/gcc/ordered-hash-map-tests.cc
index 1c26bbfa979..55894c25fa0 100644
--- a/gcc/ordered-hash-map-tests.cc
+++ b/gcc/ordered-hash-map-tests.cc
@@ -58,6 +58,7 @@ static void
 test_map_of_strings_to_int ()
 {
   ordered_hash_map  m;
+  bool existed;
 
   const char *ostrich = "ostrich";
   const char *elephant = "elephant";
@@ -74,17 +75,23 @@ test_map_of_strings_to_int ()
   ASSERT_EQ (false, m.put (ostrich, 2));
   ASSERT_EQ (false, m.put (elephant, 4));
   ASSERT_EQ (false, m.put (ant, 6));
-  ASSERT_EQ (false, m.put (spider, 8));
+  existed = true;
+  int &value = m.get_or_insert (spider, &existed);
+  value = 8;
+  ASSERT_EQ (false, existed);
   ASSERT_EQ (false, m.put (millipede, 750));
   ASSERT_EQ (false, m.put (eric, 3));
 
+
   /* Verify that we can recover the stored values.  */
   ASSERT_EQ (6, m.elements ());
   ASSERT_EQ (2, *m.get (ostrich));
   ASSERT_EQ (4, *m.get (elephant));
   ASSERT_EQ (6, *m.get (ant));
   ASSERT_EQ (8, *m.get (spider));
-  ASSERT_EQ (750, *m.get (millipede));
+  existed = false;
+  ASSERT_EQ (750, m.get_or_insert (millipede, &existed));
+  ASSERT_EQ (true, existed);
   ASSERT_EQ (3, *m.get (eric));
 
   /* Verify that the order of insertion is preserved.  */
@@ -113,6 +120,7 @@ test_map_of_int_to_strings ()
 {
   const int EMPTY = -1;
   const int DELETED = -2;
+  bool existed;
   typedef int_hash  int_hash_t;
   ordered_hash_map  m;
 
@@ -131,7 +139,9 @@ test_map_of_int_to_strings ()
   ASSERT_EQ (false, m.put (2, ostrich));
   ASSERT_EQ (false, m.put (4, elephant));
   ASSERT_EQ (false, m.put (6, ant));
-  ASSERT_EQ (false, m.put (8, spider));
+  const char* &value = m.get_or_insert (8, &existed);
+  value = spider;
+  ASSERT_EQ (false, existed);
   ASSERT_EQ (false, m.put (750, millipede));
   ASSERT_EQ (false, m.put (3, eric));
 
@@ -141,7 +151,8 @@ test_map_of_int_to_strings ()
   ASSERT_EQ (*m.get (4), elephant);
   ASSERT_EQ (*m.get (6), ant);
   ASSERT_EQ (*m.get (8), spider);
-  ASSERT_EQ (*m.get (750), millipede);
+  ASSERT_EQ (m.get_or_insert (750, &existed), millipede);
+  ASSERT_EQ (existed, TRUE);
   ASSERT_EQ (*m.get (3), eric);
 
   /* Verify that the order of insertion is preserved.  */
diff --git a/gcc/ordered-hash-map.h b/gcc/ordered-hash-map.h
index 6b68cc96305..9fc875182e1 100644
--- a/gcc/ordered-hash-map.h
+++ b/gcc/ordered-hash-map.h
@@ -76,6 +76,32 @@ public:
 return m_map.get (k);
   }
 
+  /* Return a reference to the value for the passed in key, creating the entry
+if it doesn't already exist.  If existed is not NULL then it is set to
+false if the key was not previously in the map, and true otherwise.  */
+
+  Value &get_or_insert (const Key &k, bool *existed = NULL)
+  {
+bool _existed;
+Value &ret = m_map.get_or_insert (k, &_existed);
+
+if (!_existed)
+  {
+   bool key_present;
+   int &slot = m_key_index.get_or_insert (k, &key_present);
+   if (!key_present)
+ {
+   slot = m_keys.length ();
+   m_keys.safe_push (k);
+ }
+  }
+
+if (existed)
+  *existed = _existed;
+
+return ret;
+  }
+
   /* Removing a key removes it from the map, but retains the insertion
  order.  */
 
-- 
2.34.1

Re: [PATCH 3/3] genmatch: Log line numbers indirectly

2023-08-03 Thread Andrzej Turko via Gcc-patches 
Thank you for the review.

Yes, this increases the binary size.
I have implemented this in the third version of this patch series, is that
what you had in mind?

Originally, this change increased the sizes of binaries 8-12 kB, but after
updating the master branch, this change would actually decrease the
executable size. I described in more detail in the new cover letter.

Andrzej

On Mon, Jul 31, 2023, 15:49 Richard Biener 
wrote:

> On Mon, Jul 31, 2023 at 1:07 PM Andrzej Turko via Gcc-patches
>  wrote:
> >
> > Currently fprintf calls logging to a dump file take line numbers
> > in the match.pd file directly as arguments.
> > When match.pd is edited, referenced code changes line numbers,
> > which causes changes to many fprintf calls and, thus, to many
> > (usually all) .cc files generated by genmatch. This forces make
> > to (unnecessarily) rebuild many .o files.
> >
> > With this change those logging fprintf calls reference an array
> > of line numbers, which is defined in one of the produced files.
> > Thanks to this, when match.pd changes, it is enough to rebuild
> > that single file and, of course, those actually affected by the
> > change.
> >
> > Signed-off-by: Andrzej Turko 
>
> How does this affect the size of the executable?  We are replacing
> pushing a small immediate to the stack with an indexed load plus push.
>
> Maybe further indirecting the whole dumping, passing an index of the
> match and __FILE__/__LINE__ would help here, so instead of
>
>   if (UNLIKELY (debug_dump)) fprintf
> (dump_file, "Matching expression %s:%d, %s:%d\n", "match.pd", 2522,
> __FILE__, __LINE__);
>
> we emit sth like
>
>   if (UNLIKELY (debug_dump)) dump_match (2522,
> __FILE__, __LINE__);
>
> with 2522 replaced by the ID?  That would also get rid of the inline
> varargs invocation which might help code size as well (on some targets).
>
> Richard.
>
> > gcc/ChangeLog:
> >
> > * genmatch.cc: Keep line numbers from match.pd in an array.
> >
> > Signed-off-by: Andrzej Turko 
> > ---
> >  gcc/genmatch.cc | 73 +++--
> >  1 file changed, 65 insertions(+), 8 deletions(-)
> >
> > diff --git a/gcc/genmatch.cc b/gcc/genmatch.cc
> > index 1deca505603..0a480a140c9 100644
> > --- a/gcc/genmatch.cc
> > +++ b/gcc/genmatch.cc
> > @@ -217,9 +217,48 @@ fp_decl_done (FILE *f, const char *trailer)
> >  fprintf (header_file, "%s;", trailer);
> >  }
> >
> > +/* Line numbers for use by indirect line directives.  */
> > +static vec dbg_line_numbers;
> > +
> > +static void
> > +write_header_declarations (bool gimple, FILE *f)
> > +{
> > +  if (gimple)
> > +fprintf (f, "\nextern int __gimple_dbg_line_numbers[];\n");
> > +  else
> > +fprintf (f, "\nextern int __generic_dbg_line_numbers[];\n");
> > +}
> > +
> > +static void
> > +define_dbg_line_numbers (bool gimple, FILE *f)
> > +{
> > +  if (gimple)
> > +fprintf (f, "\nint __gimple_dbg_line_numbers[%d] = {",
> > +   dbg_line_numbers.length ());
> > +  else
> > +fprintf (f, "\nint __generic_dbg_line_numbers[%d] = {",
> > +   dbg_line_numbers.length ());
> > +
> > +   if (dbg_line_numbers.is_empty ())
> > +{
> > +  fprintf (f, "};\n\n");
> > +  return;
> > +}
> > +
> > +  for (int i = 0; i < (int)dbg_line_numbers.length () - 1; i++)
> > +{
> > +  if (i % 20 == 0)
> > +   fprintf (f, "\n\t");
> > +
> > +  fprintf (f, "%d, ", dbg_line_numbers[i]);
> > +}
> > +  fprintf (f, "%d\n};\n\n", dbg_line_numbers.last ());
> > +}
> > +
> >  static void
> >  output_line_directive (FILE *f, location_t location,
> > -  bool dumpfile = false, bool fnargs = false)
> > + bool dumpfile = false, bool fnargs = false,
> > + bool indirect_line_numbers = false, bool gimple =
> false)
> >  {
> >const line_map_ordinary *map;
> >linemap_resolve_location (line_table, location,
> LRK_SPELLING_LOCATION, &map);
> > @@ -239,7 +278,20 @@ output_line_directive (FILE *f, location_t location,
> > ++file;
> >
> >if (fnargs)
> > -   fprintf (f, "\"%s\", %d", file, loc.line);
> > +  {
> > +  if (indirect_line_numbers)
> > +{
> > +  if (gimple)
>

[PATCH 1/3 v4] Support get_or_insert in ordered_hash_map

2023-08-07 Thread Andrzej Turko via Gcc-patches 
Get_or_insert method is already supported by the unordered hash map.
Adding it to the ordered map enables us to replace the unordered map
with the ordered one in cases where ordering may be useful.

Signed-off-by: Andrzej Turko 

gcc/ChangeLog:

* ordered-hash-map.h: Add get_or_insert.
* ordered-hash-map-tests.cc: Use get_or_insert in tests.
---
 gcc/ordered-hash-map-tests.cc | 19 +++
 gcc/ordered-hash-map.h| 26 ++
 2 files changed, 41 insertions(+), 4 deletions(-)

diff --git a/gcc/ordered-hash-map-tests.cc b/gcc/ordered-hash-map-tests.cc
index 1c26bbfa979..55894c25fa0 100644
--- a/gcc/ordered-hash-map-tests.cc
+++ b/gcc/ordered-hash-map-tests.cc
@@ -58,6 +58,7 @@ static void
 test_map_of_strings_to_int ()
 {
   ordered_hash_map  m;
+  bool existed;
 
   const char *ostrich = "ostrich";
   const char *elephant = "elephant";
@@ -74,17 +75,23 @@ test_map_of_strings_to_int ()
   ASSERT_EQ (false, m.put (ostrich, 2));
   ASSERT_EQ (false, m.put (elephant, 4));
   ASSERT_EQ (false, m.put (ant, 6));
-  ASSERT_EQ (false, m.put (spider, 8));
+  existed = true;
+  int &value = m.get_or_insert (spider, &existed);
+  value = 8;
+  ASSERT_EQ (false, existed);
   ASSERT_EQ (false, m.put (millipede, 750));
   ASSERT_EQ (false, m.put (eric, 3));
 
+
   /* Verify that we can recover the stored values.  */
   ASSERT_EQ (6, m.elements ());
   ASSERT_EQ (2, *m.get (ostrich));
   ASSERT_EQ (4, *m.get (elephant));
   ASSERT_EQ (6, *m.get (ant));
   ASSERT_EQ (8, *m.get (spider));
-  ASSERT_EQ (750, *m.get (millipede));
+  existed = false;
+  ASSERT_EQ (750, m.get_or_insert (millipede, &existed));
+  ASSERT_EQ (true, existed);
   ASSERT_EQ (3, *m.get (eric));
 
   /* Verify that the order of insertion is preserved.  */
@@ -113,6 +120,7 @@ test_map_of_int_to_strings ()
 {
   const int EMPTY = -1;
   const int DELETED = -2;
+  bool existed;
   typedef int_hash  int_hash_t;
   ordered_hash_map  m;
 
@@ -131,7 +139,9 @@ test_map_of_int_to_strings ()
   ASSERT_EQ (false, m.put (2, ostrich));
   ASSERT_EQ (false, m.put (4, elephant));
   ASSERT_EQ (false, m.put (6, ant));
-  ASSERT_EQ (false, m.put (8, spider));
+  const char* &value = m.get_or_insert (8, &existed);
+  value = spider;
+  ASSERT_EQ (false, existed);
   ASSERT_EQ (false, m.put (750, millipede));
   ASSERT_EQ (false, m.put (3, eric));
 
@@ -141,7 +151,8 @@ test_map_of_int_to_strings ()
   ASSERT_EQ (*m.get (4), elephant);
   ASSERT_EQ (*m.get (6), ant);
   ASSERT_EQ (*m.get (8), spider);
-  ASSERT_EQ (*m.get (750), millipede);
+  ASSERT_EQ (m.get_or_insert (750, &existed), millipede);
+  ASSERT_EQ (existed, TRUE);
   ASSERT_EQ (*m.get (3), eric);
 
   /* Verify that the order of insertion is preserved.  */
diff --git a/gcc/ordered-hash-map.h b/gcc/ordered-hash-map.h
index 6b68cc96305..9fc875182e1 100644
--- a/gcc/ordered-hash-map.h
+++ b/gcc/ordered-hash-map.h
@@ -76,6 +76,32 @@ public:
 return m_map.get (k);
   }
 
+  /* Return a reference to the value for the passed in key, creating the entry
+if it doesn't already exist.  If existed is not NULL then it is set to
+false if the key was not previously in the map, and true otherwise.  */
+
+  Value &get_or_insert (const Key &k, bool *existed = NULL)
+  {
+bool _existed;
+Value &ret = m_map.get_or_insert (k, &_existed);
+
+if (!_existed)
+  {
+   bool key_present;
+   int &slot = m_key_index.get_or_insert (k, &key_present);
+   if (!key_present)
+ {
+   slot = m_keys.length ();
+   m_keys.safe_push (k);
+ }
+  }
+
+if (existed)
+  *existed = _existed;
+
+return ret;
+  }
+
   /* Removing a key removes it from the map, but retains the insertion
  order.  */
 
-- 
2.34.1

[PATCH 0/3 v4] genmatch: Speed up recompilation after changes to match.pd

2023-08-07 Thread Andrzej Turko via Gcc-patches 
The following reduces the number of object files that need to be rebuilt
after match.pd has been modified. Right now a change to match.pd which
adds/removes a line almost always forces recompilation of all files that
genmatch generates from it. This is because of unnecessary changes to
the generated .cc files:

1. Function names and ordering change as does the way the functions are
distributed across multiple source files.
2. Code locations from match.pd are quoted directly (including line
numbers) by logging fprintf calls.

This patch addresses the those issues without changing the behaviour
of the generated code. The first one is solved by making sure that minor
changes to match.pd do not influence the order in which functions are
generated. The second one by using a lookup table with line numbers.

Now a change to a single function will trigger a rebuild of 4 object
files (one with the function  and the one with the lookup table both for
gimple and generic) instead all of them (20 by default).
For reference, this decreased the rebuild time with 48 threads from 3.5
minutes to 1.5 minutes on my machine.

V2:
* Placed the change in Makefile.in in the correct commit.
* Used a separate logging function to reduce size of the
executable.

V3:
* Fix a bug from 'genmatch: Log line numbers indirectly',
which was introduced in V2.

V4:
* Remove duplicate line numbers in the lookup table.
* Do not define dump_log functions if they are not called.
   

Note for reviewers: I do not have write access.

Andrzej Turko (3):
  Support get_or_insert in ordered_hash_map
  genmatch: Reduce variability of generated code
  genmatch: Log line numbers indirectly

 gcc/Makefile.in   |  4 +-
 gcc/genmatch.cc   | 98 +--
 gcc/ordered-hash-map-tests.cc | 19 +--
 gcc/ordered-hash-map.h| 26 ++
 4 files changed, 125 insertions(+), 22 deletions(-)

-- 
2.34.1

[PATCH 3/3 v4] genmatch: Log line numbers indirectly

2023-08-07 Thread Andrzej Turko via Gcc-patches 
Currently fprintf calls logging to a dump file take line numbers
in the match.pd file directly as arguments.
When match.pd is edited, referenced code changes line numbers,
which causes changes to many fprintf calls and, thus, to many
(usually all) .cc files generated by genmatch. This forces make
to (unnecessarily) rebuild many .o files.

This change replaces those logging fprintf calls with calls to
a dedicated logging function. Because it reads the line numbers
from the lookup table, it is enough to pass a corresponding index.
Thanks to this, when match.pd changes, it is enough to rebuild
the file containing the lookup table and, of course, those
actually affected by the change.

Signed-off-by: Andrzej Turko 

gcc/ChangeLog:

* genmatch.cc: Log line numbers indirectly.
---
 gcc/genmatch.cc | 95 +
 1 file changed, 80 insertions(+), 15 deletions(-)

diff --git a/gcc/genmatch.cc b/gcc/genmatch.cc
index 1deca505603..f46d2e1520d 100644
--- a/gcc/genmatch.cc
+++ b/gcc/genmatch.cc
@@ -217,10 +217,56 @@ fp_decl_done (FILE *f, const char *trailer)
 fprintf (header_file, "%s;", trailer);
 }
 
+/* Line numbers for use by indirect line directives.  */
+static vec dbg_line_numbers;
+
+static void
+write_header_declarations (bool gimple, FILE *f)
+{
+  fprintf (f, "\nextern void\n%s_dump_logs (const char *file1, int line1_id, "
+ "const char *file2, int line2, bool simplify);\n",
+ gimple ? "gimple" : "generic");
+}
+
+static void
+define_dump_logs (bool gimple, FILE *f)
+{
+  if (dbg_line_numbers.is_empty ())
+  return;
+
+  fprintf (f , "void\n%s_dump_logs (const char *file1, int line1_id, "
+   "const char *file2, int line2, bool simplify)\n{\n",
+   gimple ? "gimple" : "generic");
+
+  fprintf_indent (f, 2, "static int dbg_line_numbers[%d] = {",
+ dbg_line_numbers.length ());
+
+  for (unsigned i = 0; i < dbg_line_numbers.length () - 1; i++)
+{
+  if (i % 20 == 0)
+   fprintf (f, "\n\t");
+
+  fprintf (f, "%d, ", dbg_line_numbers[i]);
+}
+  fprintf (f, "%d\n  };\n\n", dbg_line_numbers.last ());
+
+
+  fprintf_indent (f, 2, "fprintf (dump_file, \"%%s "
+ "%%s:%%d, %%s:%%d\\n\",\n");
+  fprintf_indent (f, 10, "simplify ? \"Applying pattern\" : "
+ "\"Matching expression\", file1, "
+ "dbg_line_numbers[line1_id], file2, line2);");
+
+  fprintf (f, "\n}\n\n");
+}
+
 static void
 output_line_directive (FILE *f, location_t location,
-  bool dumpfile = false, bool fnargs = false)
+ bool dumpfile = false, bool fnargs = false,
+ bool indirect_line_numbers = false)
 {
+  typedef pair_hash> location_hash;
+  static hash_map loc_id_map;
   const line_map_ordinary *map;
   linemap_resolve_location (line_table, location, LRK_SPELLING_LOCATION, &map);
   expanded_location loc = linemap_expand_location (line_table, map, location);
@@ -239,7 +285,23 @@ output_line_directive (FILE *f, location_t location,
++file;
 
   if (fnargs)
-   fprintf (f, "\"%s\", %d", file, loc.line);
+   {
+ if (indirect_line_numbers)
+   {
+ bool existed;
+ int &loc_id = loc_id_map.get_or_insert (
+   std::make_pair (file, loc.line), &existed);
+   if (!existed)
+   {
+ loc_id = dbg_line_numbers.length ();
+ dbg_line_numbers.safe_push (loc.line);
+   }
+
+   fprintf (f, "\"%s\", %d", file, loc_id);
+   }
+ else
+   fprintf (f, "\"%s\", %d", file, loc.line);
+   }
   else
fprintf (f, "%s:%d", file, loc.line);
 }
@@ -3375,20 +3437,19 @@ dt_operand::gen (FILE *f, int indent, bool gimple, int 
depth)
 }
 }
 
-/* Emit a fprintf to the debug file to the file F, with the INDENT from
+/* Emit a logging call to the debug file to the file F, with the INDENT from
either the RESULT location or the S's match location if RESULT is null. */
 static void
-emit_debug_printf (FILE *f, int indent, class simplify *s, operand *result)
+emit_logging_call (FILE *f, int indent, class simplify *s, operand *result,
+ bool gimple)
 {
   fprintf_indent (f, indent, "if (UNLIKELY (debug_dump)) "
-  "fprintf (dump_file, \"%s ",
-  s->kind == simplify::SIMPLIFY
-  ? "Applying pattern" : "Matching expression");
-  fprintf (f, "%%s:%%d, %%s:%%d\\n\", ");
+  "%s_dump_logs (", gimple ? "gimple" : "generic");
   output_line_directive (f,
-result ? result->location : s->match->location, true,
-true);
-  fprintf (f, ", __FILE__, __LINE__);\n");
+   result ? result->location : s->match->location,
+   true, true, true);
+  fprintf (f, ", __FILE__, __LINE__, %s);\n",
+

[PATCH 2/3 v4] genmatch: Reduce variability of generated code

2023-08-07 Thread Andrzej Turko via Gcc-patches 
So far genmatch has been using an unordered map to store information about
functions to be generated. Since corresponding locations from match.pd were
used as keys in the map, even small changes to match.pd which caused
line number changes would change the order in which the functions are
generated. This would reshuffle the functions between the generated .cc files.
This way even a minimal modification to match.pd forces recompilation of all
object files originating from match.pd on rebuild.

This commit makes sure that functions are generated in the order of their
processing (in contrast to the random order based on hashes of their
locations in match.pd). This is done by replacing the unordered map with an
ordered one. This way small changes to match.pd does not cause function
renaming and reshuffling among generated source files.
Together with the subsequent change to logging fprintf calls, this
removes unnecessary changes to the files generated by genmatch allowing
for reuse of already built object files during rebuild. The aim is to
make editing of match.pd and subsequent testing easier.

Signed-off-by: Andrzej Turko 

gcc/ChangeLog:

* genmatch.cc: Make sinfo map ordered.
* Makefile.in: Require the ordered map header for genmatch.o.
---
 gcc/Makefile.in | 4 ++--
 gcc/genmatch.cc | 3 ++-
 2 files changed, 4 insertions(+), 3 deletions(-)

diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index e99628cec07..2429128cbf2 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -3004,8 +3004,8 @@ build/genhooks.o : genhooks.cc $(TARGET_DEF) 
$(C_TARGET_DEF)  \
   $(COMMON_TARGET_DEF) $(D_TARGET_DEF) $(BCONFIG_H) $(SYSTEM_H) errors.h
 build/genmddump.o : genmddump.cc $(RTL_BASE_H) $(BCONFIG_H) $(SYSTEM_H)
\
   $(CORETYPES_H) $(GTM_H) errors.h $(READ_MD_H) $(GENSUPPORT_H)
-build/genmatch.o : genmatch.cc $(BCONFIG_H) $(SYSTEM_H) \
-  $(CORETYPES_H) errors.h $(HASH_TABLE_H) hash-map.h $(GGC_H) is-a.h \
+build/genmatch.o : genmatch.cc $(BCONFIG_H) $(SYSTEM_H) $(CORETYPES_H) \
+  errors.h $(HASH_TABLE_H) hash-map.h $(GGC_H) is-a.h ordered-hash-map.h \
   tree.def builtins.def internal-fn.def case-cfn-macros.h $(CPPLIB_H)
 build/gencfn-macros.o : gencfn-macros.cc $(BCONFIG_H) $(SYSTEM_H)  \
   $(CORETYPES_H) errors.h $(HASH_TABLE_H) hash-set.h builtins.def  \
diff --git a/gcc/genmatch.cc b/gcc/genmatch.cc
index 2302f2a7ff0..1deca505603 100644
--- a/gcc/genmatch.cc
+++ b/gcc/genmatch.cc
@@ -29,6 +29,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "hash-table.h"
 #include "hash-set.h"
 #include "is-a.h"
+#include "ordered-hash-map.h"
 
 
 /* Stubs for GGC referenced through instantiations triggered by hash-map.  */
@@ -1684,7 +1685,7 @@ struct sinfo_hashmap_traits : 
simple_hashmap_traits,
   template  static inline void remove (T &) {}
 };
 
-typedef hash_map
+typedef ordered_hash_map
   sinfo_map_t;
 
 /* Current simplifier ID we are processing during insertion into the
-- 
2.34.1