[PATCH 0/3] rtl-ssa: Various extensions for the late-combine pass

[PATCH 0/3] rtl-ssa: Various extensions for the late-combine pass

[Richard Sandiford]

This series adds some RTL-SSA enhancements that are needed
by the late-combine pass.

Tested on aarch64-linux-gnu & x86_64-linux-gnu.  OK to install?

Richard

Richard Sandiford (3):
  rtl-ssa: Use frequency-weighted insn costs
  rtl-ssa: Extend make_uses_available
  rtl-ssa: Add new helper functions

 gcc/Makefile.in            |   1 +
 gcc/rtl-ssa/access-utils.h |  41 +++++++++++++++
 gcc/rtl-ssa/accesses.cc    | 100 ++++++++++++++++++++++++++++++++++++-
 gcc/rtl-ssa/changes.cc     |  28 +++++++++--
 gcc/rtl-ssa/functions.h    |   4 ++
 gcc/rtl-ssa/movement.cc    |  40 +++++++++++++++
 gcc/rtl-ssa/movement.h     |   4 ++
 7 files changed, 212 insertions(+), 6 deletions(-)
 create mode 100644 gcc/rtl-ssa/movement.cc

-- 
2.25.1

[PATCH 1/3] rtl-ssa: Use frequency-weighted insn costs

[Richard Sandiford]

rtl_ssa::changes_are_worthwhile used the standard approach
of summing up the individual costs of the old and new sequences
to see which one is better overall.  But when optimising for
speed and changing instructions in multiple blocks, it seems
better to weight the cost of each instruction by its execution
frequency.  (We already do something similar for SLP layouts.)

gcc/
	* rtl-ssa/changes.cc: Include sreal.h.
	(rtl_ssa::changes_are_worthwhile): When optimizing for speed,
	scale the cost of each instruction by its execution frequency.
---
 gcc/rtl-ssa/changes.cc | 28 ++++++++++++++++++++++++----
 1 file changed, 24 insertions(+), 4 deletions(-)

diff --git a/gcc/rtl-ssa/changes.cc b/gcc/rtl-ssa/changes.cc
index 3e14069421c..aab532b9f26 100644
--- a/gcc/rtl-ssa/changes.cc
+++ b/gcc/rtl-ssa/changes.cc
@@ -34,6 +34,7 @@
 #include "emit-rtl.h"
 #include "cfghooks.h"
 #include "cfgrtl.h"
+#include "sreal.h"
 
 using namespace rtl_ssa;
 
@@ -171,18 +172,33 @@ rtl_ssa::changes_are_worthwhile (array_slice<insn_change *const> changes,
 {
   unsigned int old_cost = 0;
   unsigned int new_cost = 0;
+  sreal weighted_old_cost = 0;
+  sreal weighted_new_cost = 0;
+  auto entry_count = ENTRY_BLOCK_PTR_FOR_FN (cfun)->count;
   for (insn_change *change : changes)
     {
       old_cost += change->old_cost ();
+      basic_block cfg_bb = change->bb ()->cfg_bb ();
+      bool for_speed = optimize_bb_for_speed_p (cfg_bb);
+      if (for_speed)
+	weighted_old_cost += (cfg_bb->count.to_sreal_scale (entry_count)
+			      * change->old_cost ());
       if (!change->is_deletion ())
 	{
-	  basic_block cfg_bb = change->bb ()->cfg_bb ();
-	  change->new_cost = insn_cost (change->rtl (),
-					optimize_bb_for_speed_p (cfg_bb));
+	  change->new_cost = insn_cost (change->rtl (), for_speed);
 	  new_cost += change->new_cost;
+	  if (for_speed)
+	    weighted_new_cost += (cfg_bb->count.to_sreal_scale (entry_count)
+				  * change->new_cost);
 	}
     }
-  bool ok_p = (strict_p ? new_cost < old_cost : new_cost <= old_cost);
+  bool ok_p;
+  if (weighted_new_cost != weighted_old_cost)
+    ok_p = weighted_new_cost < weighted_old_cost;
+  else if (strict_p)
+    ok_p = new_cost < old_cost;
+  else
+    ok_p = new_cost <= old_cost;
   if (dump_file && (dump_flags & TDF_DETAILS))
     {
       fprintf (dump_file, "original cost");
@@ -192,6 +208,8 @@ rtl_ssa::changes_are_worthwhile (array_slice<insn_change *const> changes,
 	  fprintf (dump_file, " %c %d", sep, change->old_cost ());
 	  sep = '+';
 	}
+      if (weighted_old_cost != 0)
+	fprintf (dump_file, " (weighted: %f)", weighted_old_cost.to_double ());
       fprintf (dump_file, ", replacement cost");
       sep = '=';
       for (const insn_change *change : changes)
@@ -200,6 +218,8 @@ rtl_ssa::changes_are_worthwhile (array_slice<insn_change *const> changes,
 	    fprintf (dump_file, " %c %d", sep, change->new_cost);
 	    sep = '+';
 	  }
+      if (weighted_new_cost != 0)
+	fprintf (dump_file, " (weighted: %f)", weighted_new_cost.to_double ());
       fprintf (dump_file, "; %s\n",
 	       ok_p ? "keeping replacement" : "rejecting replacement");
     }
-- 
2.25.1

[PATCH 2/3] rtl-ssa: Extend make_uses_available

[Richard Sandiford]

The first in-tree use of RTL-SSA was fwprop, and one of the goals
was to make the fwprop rewrite preserve the old behaviour as far
as possible.  The switch to RTL-SSA was supposed to be a pure
infrastructure change.  So RTL-SSA has various FIXMEs for things
that were artifically limited to faciliate the old-fwprop vs.
new-fwprop comparison.

One of the things that fwprop wants to do is extend live ranges, and
function_info::make_use_available tried to keep within the cases that
old fwprop could handle.

Since the information is built in extended basic blocks, it's easy
to handle intra-EBB queries directly.  This patch does that, and
removes the associated FIXME.

To get a flavour for how much difference this makes, I tried compiling
the testsuite at -Os for at least one target per supported CPU and OS.
For most targets, only a handful of tests changed, but the vast majority
of changes were positive.  The only target that seemed to benefit
significantly was i686-apple-darwin.

The main point of the patch is to remove the FIXME and to enable
the upcoming post-RA late-combine pass to handle more cases.

gcc/
	* rtl-ssa/functions.h (function_info::remains_available_at_insn):
	New member function.
	* rtl-ssa/accesses.cc (function_info::remains_available_at_insn):
	Likewise.
	(function_info::make_use_available): Avoid false negatives for
	queries within an EBB.
---
 gcc/rtl-ssa/accesses.cc | 37 +++++++++++++++++++++++++++++++++++--
 gcc/rtl-ssa/functions.h |  4 ++++
 2 files changed, 39 insertions(+), 2 deletions(-)

diff --git a/gcc/rtl-ssa/accesses.cc b/gcc/rtl-ssa/accesses.cc
index c35c7efb73d..1b25ecc3e23 100644
--- a/gcc/rtl-ssa/accesses.cc
+++ b/gcc/rtl-ssa/accesses.cc
@@ -1303,6 +1303,33 @@ function_info::insert_temp_clobber (obstack_watermark &watermark,
   return insert_access (watermark, clobber, old_defs);
 }
 
+// See the comment above the declaration.
+bool
+function_info::remains_available_at_insn (const set_info *set,
+					  insn_info *insn)
+{
+  auto *ebb = set->ebb ();
+  gcc_checking_assert (ebb == insn->ebb ());
+
+  def_info *next_def = set->next_def ();
+  if (next_def && *next_def->insn () < *insn)
+    return false;
+
+  if (HARD_REGISTER_NUM_P (set->regno ())
+      && TEST_HARD_REG_BIT (m_clobbered_by_calls, set->regno ()))
+    for (ebb_call_clobbers_info *call_group : ebb->call_clobbers ())
+      {
+	if (!call_group->clobbers (set->resource ()))
+	  continue;
+
+	insn_info *call_insn = next_call_clobbers (*call_group, insn);
+	if (call_insn && *call_insn < *insn)
+	  return false;
+      }
+
+  return true;
+}
+
 // See the comment above the declaration.
 bool
 function_info::remains_available_on_exit (const set_info *set, bb_info *bb)
@@ -1354,14 +1381,20 @@ function_info::make_use_available (use_info *use, bb_info *bb,
   if (is_single_dominating_def (def))
     return use;
 
-  // FIXME: Deliberately limited for fwprop compatibility testing.
+  if (def->ebb () == bb->ebb ())
+    {
+      if (remains_available_at_insn (def, bb->head_insn ()))
+	return use;
+      return nullptr;
+    }
+
   basic_block cfg_bb = bb->cfg_bb ();
   bb_info *use_bb = use->bb ();
   if (single_pred_p (cfg_bb)
       && single_pred (cfg_bb) == use_bb->cfg_bb ()
       && remains_available_on_exit (def, use_bb))
     {
-      if (def->ebb () == bb->ebb () || will_be_debug_use)
+      if (will_be_debug_use)
 	return use;
 
       resource_info resource = use->resource ();
diff --git a/gcc/rtl-ssa/functions.h b/gcc/rtl-ssa/functions.h
index ab253e750cb..ecb40fdaf57 100644
--- a/gcc/rtl-ssa/functions.h
+++ b/gcc/rtl-ssa/functions.h
@@ -121,6 +121,10 @@ public:
   // scope until the change has been aborted or successfully completed.
   obstack_watermark new_change_attempt () { return &m_temp_obstack; }
 
+  // SET and INSN belong to the same EBB, with SET occuring before INSN.
+  // Return true if SET is still available at INSN.
+  bool remains_available_at_insn (const set_info *set, insn_info *insn);
+
   // SET either occurs in BB or is known to be available on entry to BB.
   // Return true if it is also available on exit from BB.  (The value
   // might or might not be live.)
-- 
2.25.1

[PATCH 3/3] rtl-ssa: Add new helper functions

[Richard Sandiford]

This patch adds some RTL-SSA helper functions.  They will be
used by the upcoming late-combine pass.

The patch contains the first non-template out-of-line function declared
in movement.h, so it adds a movement.cc.  I realise it seems a bit
over-the-top to have a file with just one function, but it might grow
in future. :)

gcc/
	* Makefile.in (OBJS): Add rtl-ssa/movement.o.
	* rtl-ssa/access-utils.h (accesses_include_nonfixed_hard_registers)
	(single_set_info): New functions.
	(remove_uses_of_def, accesses_reference_same_resource): Declare.
	(insn_clobbers_resources): Likewise.
	* rtl-ssa/accesses.cc (rtl_ssa::remove_uses_of_def): New function.
	(rtl_ssa::accesses_reference_same_resource): Likewise.
	(rtl_ssa::insn_clobbers_resources): Likewise.
	* rtl-ssa/movement.h (can_move_insn_p): Declare.
	* rtl-ssa/movement.cc: New file.
---
 gcc/Makefile.in            |  1 +
 gcc/rtl-ssa/access-utils.h | 41 +++++++++++++++++++++++++
 gcc/rtl-ssa/accesses.cc    | 63 ++++++++++++++++++++++++++++++++++++++
 gcc/rtl-ssa/movement.cc    | 40 ++++++++++++++++++++++++
 gcc/rtl-ssa/movement.h     |  4 +++
 5 files changed, 149 insertions(+)
 create mode 100644 gcc/rtl-ssa/movement.cc

diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index 7b7a4ff789a..91d6bfbea4d 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -1635,6 +1635,7 @@ OBJS = \
 	rtl-ssa/changes.o \
 	rtl-ssa/functions.o \
 	rtl-ssa/insns.o \
+	rtl-ssa/movement.o \
 	rtl-tests.o \
 	rtl.o \
 	rtlhash.o \
diff --git a/gcc/rtl-ssa/access-utils.h b/gcc/rtl-ssa/access-utils.h
index 0d7a57f843c..f078625babf 100644
--- a/gcc/rtl-ssa/access-utils.h
+++ b/gcc/rtl-ssa/access-utils.h
@@ -33,6 +33,20 @@ accesses_include_hard_registers (const access_array &accesses)
   return accesses.size () && HARD_REGISTER_NUM_P (accesses.front ()->regno ());
 }
 
+// Return true if ACCESSES includes a reference to a non-fixed hard register.
+inline bool
+accesses_include_nonfixed_hard_registers (access_array accesses)
+{
+  for (access_info *access : accesses)
+    {
+      if (!HARD_REGISTER_NUM_P (access->regno ()))
+	break;
+      if (!fixed_regs[access->regno ()])
+	return true;
+    }
+  return false;
+}
+
 // Return true if sorted array ACCESSES includes an access to memory.
 inline bool
 accesses_include_memory (const access_array &accesses)
@@ -246,6 +260,22 @@ last_def (def_mux mux)
   return mux.last_def ();
 }
 
+// If INSN's definitions contain a single set, return that set, otherwise
+// return null.
+inline set_info *
+single_set_info (insn_info *insn)
+{
+  set_info *set = nullptr;
+  for (auto def : insn->defs ())
+    if (auto this_set = dyn_cast<set_info *> (def))
+      {
+	if (set)
+	  return nullptr;
+	set = this_set;
+      }
+  return set;
+}
+
 int lookup_use (splay_tree<use_info *> &, insn_info *);
 int lookup_def (def_splay_tree &, insn_info *);
 int lookup_clobber (clobber_tree &, insn_info *);
@@ -539,6 +569,10 @@ insert_access (obstack_watermark &watermark,
   return T (insert_access_base (watermark, access1, accesses2));
 }
 
+// Return a copy of USES that drops any use of DEF.
+use_array remove_uses_of_def (obstack_watermark &, use_array uses,
+			      def_info *def);
+
 // The underlying non-template implementation of remove_note_accesses.
 access_array remove_note_accesses_base (obstack_watermark &, access_array);
 
@@ -554,4 +588,11 @@ remove_note_accesses (obstack_watermark &watermark, T accesses)
   return T (remove_note_accesses_base (watermark, accesses));
 }
 
+// Return true if ACCESSES1 and ACCESSES2 have at least one resource in common.
+bool accesses_reference_same_resource (access_array accesses1,
+				       access_array accesses2);
+
+// Return true if INSN clobbers the value of any resources in ACCESSES.
+bool insn_clobbers_resources (insn_info *insn, access_array accesses);
+
 }
diff --git a/gcc/rtl-ssa/accesses.cc b/gcc/rtl-ssa/accesses.cc
index 1b25ecc3e23..510545a8bad 100644
--- a/gcc/rtl-ssa/accesses.cc
+++ b/gcc/rtl-ssa/accesses.cc
@@ -1569,6 +1569,19 @@ rtl_ssa::insert_access_base (obstack_watermark &watermark,
   return builder.finish ();
 }
 
+// See the comment above the declaration.
+use_array
+rtl_ssa::remove_uses_of_def (obstack_watermark &watermark, use_array uses,
+			     def_info *def)
+{
+  access_array_builder uses_builder (watermark);
+  uses_builder.reserve (uses.size ());
+  for (use_info *use : uses)
+    if (use->def () != def)
+      uses_builder.quick_push (use);
+  return use_array (uses_builder.finish ());
+}
+
 // See the comment above the declaration.
 access_array
 rtl_ssa::remove_note_accesses_base (obstack_watermark &watermark,
@@ -1587,6 +1600,56 @@ rtl_ssa::remove_note_accesses_base (obstack_watermark &watermark,
   return accesses;
 }
 
+// See the comment above the declaration.
+bool
+rtl_ssa::accesses_reference_same_resource (access_array accesses1,
+					   access_array accesses2)
+{
+  auto i1 = accesses1.begin ();
+  auto end1 = accesses1.end ();
+  auto i2 = accesses2.begin ();
+  auto end2 = accesses2.end ();
+
+  while (i1 != end1 && i2 != end2)
+    {
+      access_info *access1 = *i1;
+      access_info *access2 = *i2;
+
+      unsigned int regno1 = access1->regno ();
+      unsigned int regno2 = access2->regno ();
+      if (regno1 == regno2)
+	return true;
+
+      if (regno1 < regno2)
+	++i1;
+      else
+	++i2;
+    }
+  return false;
+}
+
+// See the comment above the declaration.
+bool
+rtl_ssa::insn_clobbers_resources (insn_info *insn, access_array accesses)
+{
+  if (accesses_reference_same_resource (insn->defs (), accesses))
+    return true;
+
+  if (insn->is_call () && accesses_include_hard_registers (accesses))
+    {
+      function_abi abi = insn_callee_abi (insn->rtl ());
+      for (const access_info *access : accesses)
+	{
+	  if (!HARD_REGISTER_NUM_P (access->regno ()))
+	    break;
+	  if (abi.clobbers_reg_p (access->mode (), access->regno ()))
+	    return true;
+	}
+    }
+
+  return false;
+}
+
 // Print RESOURCE to PP.
 void
 rtl_ssa::pp_resource (pretty_printer *pp, resource_info resource)
diff --git a/gcc/rtl-ssa/movement.cc b/gcc/rtl-ssa/movement.cc
new file mode 100644
index 00000000000..fcf5f8bc822
--- /dev/null
+++ b/gcc/rtl-ssa/movement.cc
@@ -0,0 +1,40 @@
+// RTL SSA routines for moving instructions
+// Copyright (C) 2023 Free Software Foundation, Inc.
+//
+// This file is part of GCC.
+//
+// GCC is free software; you can redistribute it and/or modify it under
+// the terms of the GNU General Public License as published by the Free
+// Software Foundation; either version 3, or (at your option) any later
+// version.
+//
+// GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+// WARRANTY; without even the implied warranty of MERCHANTABILITY or
+// FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+// for more details.
+//
+// You should have received a copy of the GNU General Public License
+// along with GCC; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+#define INCLUDE_ALGORITHM
+#define INCLUDE_FUNCTIONAL
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "backend.h"
+#include "rtl.h"
+#include "df.h"
+#include "rtl-ssa.h"
+#include "rtl-ssa/internals.h"
+#include "rtl-ssa/internals.inl"
+
+using namespace rtl_ssa;
+
+// See the comment above the declaration.
+bool
+rtl_ssa::can_move_insn_p (insn_info *insn)
+{
+  return (!control_flow_insn_p (insn->rtl ())
+	  && !may_trap_p (PATTERN (insn->rtl ())));
+}
diff --git a/gcc/rtl-ssa/movement.h b/gcc/rtl-ssa/movement.h
index 67370947dbd..ec076db406f 100644
--- a/gcc/rtl-ssa/movement.h
+++ b/gcc/rtl-ssa/movement.h
@@ -19,6 +19,10 @@
 
 namespace rtl_ssa {
 
+// Return true if INSN can in principle be moved around, and if RTL-SSA
+// has enough information to do that.
+bool can_move_insn_p (insn_info *);
+
 // Restrict movement range RANGE so that the instruction is placed later
 // than INSN.  (The movement range is the range of instructions after which
 // an instruction can be placed.)
-- 
2.25.1

Re: [PATCH 1/3] rtl-ssa: Use frequency-weighted insn costs

[Jeff Law]

On 10/24/23 11:58, Richard Sandiford wrote:
> rtl_ssa::changes_are_worthwhile used the standard approach
> of summing up the individual costs of the old and new sequences
> to see which one is better overall.  But when optimising for
> speed and changing instructions in multiple blocks, it seems
> better to weight the cost of each instruction by its execution
> frequency.  (We already do something similar for SLP layouts.)
> 
> gcc/
> 	* rtl-ssa/changes.cc: Include sreal.h.
> 	(rtl_ssa::changes_are_worthwhile): When optimizing for speed,
> 	scale the cost of each instruction by its execution frequency.
Agreed that it seems better.  OK.

Jeff

Re: [PATCH 2/3] rtl-ssa: Extend make_uses_available

[Jeff Law]

On 10/24/23 11:58, Richard Sandiford wrote:
> The first in-tree use of RTL-SSA was fwprop, and one of the goals
> was to make the fwprop rewrite preserve the old behaviour as far
> as possible.  The switch to RTL-SSA was supposed to be a pure
> infrastructure change.  So RTL-SSA has various FIXMEs for things
> that were artifically limited to faciliate the old-fwprop vs.
> new-fwprop comparison.
> 
> One of the things that fwprop wants to do is extend live ranges, and
> function_info::make_use_available tried to keep within the cases that
> old fwprop could handle.
> 
> Since the information is built in extended basic blocks, it's easy
> to handle intra-EBB queries directly.  This patch does that, and
> removes the associated FIXME.
> 
> To get a flavour for how much difference this makes, I tried compiling
> the testsuite at -Os for at least one target per supported CPU and OS.
> For most targets, only a handful of tests changed, but the vast majority
> of changes were positive.  The only target that seemed to benefit
> significantly was i686-apple-darwin.
> 
> The main point of the patch is to remove the FIXME and to enable
> the upcoming post-RA late-combine pass to handle more cases.
> 
> gcc/
> 	* rtl-ssa/functions.h (function_info::remains_available_at_insn):
> 	New member function.
> 	* rtl-ssa/accesses.cc (function_info::remains_available_at_insn):
> 	Likewise.
> 	(function_info::make_use_available): Avoid false negatives for
> 	queries within an EBB.
OK
jeff

Re: [PATCH 3/3] rtl-ssa: Add new helper functions

[Jeff Law]

On 10/24/23 11:58, Richard Sandiford wrote:
> This patch adds some RTL-SSA helper functions.  They will be
> used by the upcoming late-combine pass.
> 
> The patch contains the first non-template out-of-line function declared
> in movement.h, so it adds a movement.cc.  I realise it seems a bit
> over-the-top to have a file with just one function, but it might grow
> in future. :)
> 
> gcc/
> 	* Makefile.in (OBJS): Add rtl-ssa/movement.o.
> 	* rtl-ssa/access-utils.h (accesses_include_nonfixed_hard_registers)
> 	(single_set_info): New functions.
> 	(remove_uses_of_def, accesses_reference_same_resource): Declare.
> 	(insn_clobbers_resources): Likewise.
> 	* rtl-ssa/accesses.cc (rtl_ssa::remove_uses_of_def): New function.
> 	(rtl_ssa::accesses_reference_same_resource): Likewise.
> 	(rtl_ssa::insn_clobbers_resources): Likewise.
> 	* rtl-ssa/movement.h (can_move_insn_p): Declare.
> 	* rtl-ssa/movement.cc: New file.
I assumed that you'll end up with more code in there, so I'm certainly 
OK with having just one function in the file right now.

OK for the trunk.

jeff