[11/12] mode-switching: Add a target-configurable confluence operator

The mode-switching pass assumed that all of an entity's modes
were mutually exclusive.  However, the upcoming SME changes
have an entity with some overlapping modes, so that there is
sometimes a "superunion" mode that contains two given modes.
We can use this relationship to pass something more helpful than
"don't know" to the emit hook.

This patch adds a new hook that targets can use to specify
a mode confluence operator.

With mutually exclusive modes, it's possible to compute a block's
incoming and outgoing modes by looking at its availability sets.
With the confluence operator, we instead need to solve a full
dataflow problem.

However, when emitting a mode transition, the upcoming SME use of
mode-switching benefits from having as much information as possible
about the starting mode.  Calculating this information is definitely
worth the compile time.

The dataflow problem is written to work before and after the LCM
problem has been solved.  A later patch makes use of this.

While there (since git blame would ping me for the reindented code),
I used a lambda to avoid the cut-&-pasted loops.

gcc/
	* target.def (mode_switching.confluence): New hook.
	* doc/tm.texi (TARGET_MODE_CONFLUENCE): New @hook.
	* doc/tm.texi.in: Regenerate.
	* mode-switching.cc (confluence_info): New variable.
	(mode_confluence, forward_confluence_n, forward_transfer): New
	functions.
	(optimize_mode_switching): Use them to calculate mode_in when
	TARGET_MODE_CONFLUENCE is defined.
---
 gcc/doc/tm.texi       |  16 ++++
 gcc/doc/tm.texi.in    |   2 +
 gcc/mode-switching.cc | 179 +++++++++++++++++++++++++++++++++++-------
 gcc/target.def        |  17 ++++
 4 files changed, 186 insertions(+), 28 deletions(-)

On 11/5/23 11:50, Richard Sandiford wrote:
> The mode-switching pass assumed that all of an entity's modes
> were mutually exclusive.  However, the upcoming SME changes
> have an entity with some overlapping modes, so that there is
> sometimes a "superunion" mode that contains two given modes.
> We can use this relationship to pass something more helpful than
> "don't know" to the emit hook.
> 
> This patch adds a new hook that targets can use to specify
> a mode confluence operator.
> 
> With mutually exclusive modes, it's possible to compute a block's
> incoming and outgoing modes by looking at its availability sets.
> With the confluence operator, we instead need to solve a full
> dataflow problem.
> 
> However, when emitting a mode transition, the upcoming SME use of
> mode-switching benefits from having as much information as possible
> about the starting mode.  Calculating this information is definitely
> worth the compile time.
> 
> The dataflow problem is written to work before and after the LCM
> problem has been solved.  A later patch makes use of this.
> 
> While there (since git blame would ping me for the reindented code),
> I used a lambda to avoid the cut-&-pasted loops.
> 
> gcc/
> 	* target.def (mode_switching.confluence): New hook.
> 	* doc/tm.texi (TARGET_MODE_CONFLUENCE): New @hook.
> 	* doc/tm.texi.in: Regenerate.
> 	* mode-switching.cc (confluence_info): New variable.
> 	(mode_confluence, forward_confluence_n, forward_transfer): New
> 	functions.
> 	(optimize_mode_switching): Use them to calculate mode_in when
> 	TARGET_MODE_CONFLUENCE is defined.
OK.  There's certain similarities between this and the compatible states 
we can use to reduce vsetvl instructions in RV-V.   I wonder if Juzhe or 
Lehua could utilize this and do less custom optimization code in the RV 
backend.

jeff

Jeff Law <jeffreyalaw@gmail.com> writes:
> On 11/5/23 11:50, Richard Sandiford wrote:
>> The mode-switching pass assumed that all of an entity's modes
>> were mutually exclusive.  However, the upcoming SME changes
>> have an entity with some overlapping modes, so that there is
>> sometimes a "superunion" mode that contains two given modes.
>> We can use this relationship to pass something more helpful than
>> "don't know" to the emit hook.
>> 
>> This patch adds a new hook that targets can use to specify
>> a mode confluence operator.
>> 
>> With mutually exclusive modes, it's possible to compute a block's
>> incoming and outgoing modes by looking at its availability sets.
>> With the confluence operator, we instead need to solve a full
>> dataflow problem.
>> 
>> However, when emitting a mode transition, the upcoming SME use of
>> mode-switching benefits from having as much information as possible
>> about the starting mode.  Calculating this information is definitely
>> worth the compile time.
>> 
>> The dataflow problem is written to work before and after the LCM
>> problem has been solved.  A later patch makes use of this.
>> 
>> While there (since git blame would ping me for the reindented code),
>> I used a lambda to avoid the cut-&-pasted loops.
>> 
>> gcc/
>> 	* target.def (mode_switching.confluence): New hook.
>> 	* doc/tm.texi (TARGET_MODE_CONFLUENCE): New @hook.
>> 	* doc/tm.texi.in: Regenerate.
>> 	* mode-switching.cc (confluence_info): New variable.
>> 	(mode_confluence, forward_confluence_n, forward_transfer): New
>> 	functions.
>> 	(optimize_mode_switching): Use them to calculate mode_in when
>> 	TARGET_MODE_CONFLUENCE is defined.
> OK.  There's certain similarities between this and the compatible states 
> we can use to reduce vsetvl instructions in RV-V.   I wonder if Juzhe or 
> Lehua could utilize this and do less custom optimization code in the RV 
> backend.

Here's an update based on what you pointed out in 10/12.  The change
from last time is to add:

  if (targetm.mode_switching.backprop)
    clear_aux_for_edges ();

before the main loop.  Tested as before.

Thanks,
Richard


gcc/
	* target.def (mode_switching.confluence): New hook.
	* doc/tm.texi (TARGET_MODE_CONFLUENCE): New @hook.
	* doc/tm.texi.in: Regenerate.
	* mode-switching.cc (confluence_info): New variable.
	(mode_confluence, forward_confluence_n, forward_transfer): New
	functions.
	(optimize_mode_switching): Use them to calculate mode_in when
	TARGET_MODE_CONFLUENCE is defined.
---
 gcc/doc/tm.texi       |  16 ++++
 gcc/doc/tm.texi.in    |   2 +
 gcc/mode-switching.cc | 182 +++++++++++++++++++++++++++++++++++-------
 gcc/target.def        |  17 ++++
 4 files changed, 189 insertions(+), 28 deletions(-)

diff --git a/gcc/doc/tm.texi b/gcc/doc/tm.texi
index b730b5bf658..cd346538fe2 100644
--- a/gcc/doc/tm.texi
+++ b/gcc/doc/tm.texi
@@ -10440,6 +10440,22 @@ the number of modes if it does not know what mode @var{entity} has after
 Not defining the hook is equivalent to returning @var{mode}.
 @end deftypefn
 
+@deftypefn {Target Hook} int TARGET_MODE_CONFLUENCE (int @var{entity}, int @var{mode1}, int @var{mode2})
+By default, the mode-switching pass assumes that a given entity's modes
+are mutually exclusive.  This means that the pass can only tell
+@code{TARGET_MODE_EMIT} about an entity's previous mode if all
+incoming paths of execution leave the entity in the same state.
+
+However, some entities might have overlapping, non-exclusive modes,
+so that it is sometimes possible to represent ``mode @var{mode1} or mode
+@var{mode2}'' with something more specific than ``mode not known''.
+If this is true for at least one entity, you should define this hook
+and make it return a mode that includes @var{mode1} and @var{mode2}
+as possibilities.  (The mode can include other possibilities too.)
+The hook should return the number of modes if no suitable mode exists
+for the given arguments.
+@end deftypefn
+
 @deftypefn {Target Hook} int TARGET_MODE_ENTRY (int @var{entity})
 If this hook is defined, it is evaluated for every @var{entity} that
 needs mode switching.  It should return the mode that @var{entity} is
diff --git a/gcc/doc/tm.texi.in b/gcc/doc/tm.texi.in
index 5360c1bb2d8..ae23241ea1c 100644
--- a/gcc/doc/tm.texi.in
+++ b/gcc/doc/tm.texi.in
@@ -6975,6 +6975,8 @@ mode or ``no mode'', depending on context.
 
 @hook TARGET_MODE_AFTER
 
+@hook TARGET_MODE_CONFLUENCE
+
 @hook TARGET_MODE_ENTRY
 
 @hook TARGET_MODE_EXIT
diff --git a/gcc/mode-switching.cc b/gcc/mode-switching.cc
index 6b5661131e3..58bc1934e81 100644
--- a/gcc/mode-switching.cc
+++ b/gcc/mode-switching.cc
@@ -485,6 +485,101 @@ create_pre_exit (int n_entities, int *entity_map, const int *num_modes)
   return pre_exit;
 }
 
+/* Return the confluence of modes MODE1 and MODE2 for entity ENTITY,
+   using NO_MODE to represent an unknown mode if nothing more precise
+   is available.  */
+
+int
+mode_confluence (int entity, int mode1, int mode2, int no_mode)
+{
+  if (mode1 == mode2)
+    return mode1;
+
+  if (mode1 != no_mode
+      && mode2 != no_mode
+      && targetm.mode_switching.confluence)
+    return targetm.mode_switching.confluence (entity, mode1, mode2);
+
+  return no_mode;
+}
+
+/* Information for the dataflow problems below.  */
+struct
+{
+  /* Information about each basic block, indexed by block id.  */
+  struct bb_info *bb_info;
+
+  /* The entity that we're processing.  */
+  int entity;
+
+  /* The number of modes defined for the entity, and thus the identifier
+     of the "don't know" mode.  */
+  int no_mode;
+} confluence_info;
+
+/* Propagate information about any mode change on edge E to the
+   destination block's mode_in.  Return true if something changed.
+
+   The mode_in and mode_out fields use no_mode + 1 to mean "not yet set".  */
+
+static bool
+forward_confluence_n (edge e)
+{
+  /* The entry and exit blocks have no useful mode information.  */
+  if (e->src->index == ENTRY_BLOCK || e->dest->index == EXIT_BLOCK)
+    return false;
+
+  /* We don't control mode changes across abnormal edges.  */
+  if (e->flags & EDGE_ABNORMAL)
+    return false;
+
+  /* E->aux is nonzero if we have computed the LCM problem and scheduled
+     E to change the mode to E->aux - 1.  Otherwise model the change
+     from the source to the destination.  */
+  struct bb_info *bb_info = confluence_info.bb_info;
+  int no_mode = confluence_info.no_mode;
+  int src_mode = bb_info[e->src->index].mode_out;
+  if (e->aux)
+    src_mode = (int) (intptr_t) e->aux - 1;
+  if (src_mode == no_mode + 1)
+    return false;
+
+  int dest_mode = bb_info[e->dest->index].mode_in;
+  if (dest_mode == no_mode + 1)
+    {
+      bb_info[e->dest->index].mode_in = src_mode;
+      return true;
+    }
+
+  int entity = confluence_info.entity;
+  int new_mode = mode_confluence (entity, src_mode, dest_mode, no_mode);
+  if (dest_mode == new_mode)
+    return false;
+
+  bb_info[e->dest->index].mode_in = new_mode;
+  return true;
+}
+
+/* Update block BB_INDEX's mode_out based on its mode_in.  Return true if
+   something changed.  */
+
+static bool
+forward_transfer (int bb_index)
+{
+  /* The entry and exit blocks have no useful mode information.  */
+  if (bb_index == ENTRY_BLOCK || bb_index == EXIT_BLOCK)
+    return false;
+
+  /* Only propagate through a block if the entity is transparent.  */
+  struct bb_info *bb_info = confluence_info.bb_info;
+  if (bb_info[bb_index].computing != confluence_info.no_mode
+      || bb_info[bb_index].mode_out == bb_info[bb_index].mode_in)
+    return false;
+
+  bb_info[bb_index].mode_out = bb_info[bb_index].mode_in;
+  return true;
+}
+
 /* Find all insns that need a particular mode setting, and insert the
    necessary mode switches.  Return true if we did work.  */
 
@@ -568,6 +663,42 @@ optimize_mode_switching (void)
 
   auto_sbitmap transp_all (last_basic_block_for_fn (cfun));
 
+  auto_bitmap blocks;
+
+  /* Forward-propagate mode information through blocks where the entity
+     is transparent, so that mode_in describes the mode on entry to each
+     block and mode_out describes the mode on exit from each block.  */
+  auto forwprop_mode_info = [&](struct bb_info *info,
+				int entity, int no_mode)
+    {
+      /* Use no_mode + 1 to mean "not yet set".  */
+      FOR_EACH_BB_FN (bb, cfun)
+	{
+	  if (bb_has_abnormal_pred (bb))
+	    info[bb->index].mode_in = info[bb->index].seginfo->mode;
+	  else
+	    info[bb->index].mode_in = no_mode + 1;
+	  if (info[bb->index].computing != no_mode)
+	    info[bb->index].mode_out = info[bb->index].computing;
+	  else
+	    info[bb->index].mode_out = no_mode + 1;
+	}
+
+      confluence_info.bb_info = info;
+      confluence_info.entity = entity;
+      confluence_info.no_mode = no_mode;
+
+      bitmap_set_range (blocks, 0, last_basic_block_for_fn (cfun));
+      df_simple_dataflow (DF_FORWARD, NULL, NULL, forward_confluence_n,
+			  forward_transfer, blocks,
+			  df_get_postorder (DF_FORWARD),
+			  df_get_n_blocks (DF_FORWARD));
+
+    };
+
+  if (targetm.mode_switching.backprop)
+    clear_aux_for_edges ();
+
   for (j = n_entities - 1; j >= 0; j--)
     {
       int e = entity_map[j];
@@ -721,6 +852,7 @@ optimize_mode_switching (void)
   for (j = n_entities - 1; j >= 0; j--)
     {
       int no_mode = num_modes[entity_map[j]];
+      struct bb_info *info = bb_info[j];
 
       /* Insert all mode sets that have been inserted by lcm.  */
 
@@ -741,39 +873,33 @@ optimize_mode_switching (void)
 	    }
 	}
 
+      /* mode_in and mode_out can be calculated directly from avin and
+	 avout if all the modes are mutually exclusive.  Use the target-
+	 provided confluence function otherwise.  */
+      if (targetm.mode_switching.confluence)
+	forwprop_mode_info (info, entity_map[j], no_mode);
+
       FOR_EACH_BB_FN (bb, cfun)
 	{
-	  struct bb_info *info = bb_info[j];
-	  int last_mode = no_mode;
-
-	  /* intialize mode in availability for bb.  */
-	  for (i = 0; i < no_mode; i++)
-	    if (mode_bit_p (avout[bb->index], j, i))
-	      {
-		if (last_mode == no_mode)
-		  last_mode = i;
-		if (last_mode != i)
+	  auto modes_confluence = [&](sbitmap *av)
+	    {
+	      for (int i = 0; i < no_mode; ++i)
+		if (mode_bit_p (av[bb->index], j, i))
 		  {
-		    last_mode = no_mode;
-		    break;
+		    for (int i2 = i + 1; i2 < no_mode; ++i2)
+		      if (mode_bit_p (av[bb->index], j, i2))
+			return no_mode;
+		    return i;
 		  }
-	      }
-	  info[bb->index].mode_out = last_mode;
+	      return no_mode;
+	    };
 
-	  /* intialize mode out availability for bb.  */
-	  last_mode = no_mode;
-	  for (i = 0; i < no_mode; i++)
-	    if (mode_bit_p (avin[bb->index], j, i))
-	      {
-		if (last_mode == no_mode)
-		  last_mode = i;
-		if (last_mode != i)
-		  {
-		    last_mode = no_mode;
-		    break;
-		  }
-	      }
-	  info[bb->index].mode_in = last_mode;
+	  /* intialize mode in/out availability for bb.  */
+	  if (!targetm.mode_switching.confluence)
+	    {
+	      info[bb->index].mode_out = modes_confluence (avout);
+	      info[bb->index].mode_in = modes_confluence (avin);
+	    }
 
 	  for (i = 0; i < no_mode; i++)
 	    if (mode_bit_p (del[bb->index], j, i))
diff --git a/gcc/target.def b/gcc/target.def
index 9b14c037d3f..b08ede692f1 100644
--- a/gcc/target.def
+++ b/gcc/target.def
@@ -7053,6 +7053,23 @@ the number of modes if it does not know what mode @var{entity} has after\n\
 Not defining the hook is equivalent to returning @var{mode}.",
  int, (int entity, int mode, rtx_insn *insn, HARD_REG_SET regs_live), NULL)
 
+DEFHOOK
+(confluence,
+ "By default, the mode-switching pass assumes that a given entity's modes\n\
+are mutually exclusive.  This means that the pass can only tell\n\
+@code{TARGET_MODE_EMIT} about an entity's previous mode if all\n\
+incoming paths of execution leave the entity in the same state.\n\
+\n\
+However, some entities might have overlapping, non-exclusive modes,\n\
+so that it is sometimes possible to represent ``mode @var{mode1} or mode\n\
+@var{mode2}'' with something more specific than ``mode not known''.\n\
+If this is true for at least one entity, you should define this hook\n\
+and make it return a mode that includes @var{mode1} and @var{mode2}\n\
+as possibilities.  (The mode can include other possibilities too.)\n\
+The hook should return the number of modes if no suitable mode exists\n\
+for the given arguments.",
+ int, (int entity, int mode1, int mode2), NULL)
+
 DEFHOOK
 (entry,
  "If this hook is defined, it is evaluated for every @var{entity} that\n\

On 11/11/23 08:54, Richard Sandiford wrote:
> Jeff Law <jeffreyalaw@gmail.com> writes:
>> On 11/5/23 11:50, Richard Sandiford wrote:
>>> The mode-switching pass assumed that all of an entity's modes
>>> were mutually exclusive.  However, the upcoming SME changes
>>> have an entity with some overlapping modes, so that there is
>>> sometimes a "superunion" mode that contains two given modes.
>>> We can use this relationship to pass something more helpful than
>>> "don't know" to the emit hook.
>>>
>>> This patch adds a new hook that targets can use to specify
>>> a mode confluence operator.
>>>
>>> With mutually exclusive modes, it's possible to compute a block's
>>> incoming and outgoing modes by looking at its availability sets.
>>> With the confluence operator, we instead need to solve a full
>>> dataflow problem.
>>>
>>> However, when emitting a mode transition, the upcoming SME use of
>>> mode-switching benefits from having as much information as possible
>>> about the starting mode.  Calculating this information is definitely
>>> worth the compile time.
>>>
>>> The dataflow problem is written to work before and after the LCM
>>> problem has been solved.  A later patch makes use of this.
>>>
>>> While there (since git blame would ping me for the reindented code),
>>> I used a lambda to avoid the cut-&-pasted loops.
>>>
>>> gcc/
>>> 	* target.def (mode_switching.confluence): New hook.
>>> 	* doc/tm.texi (TARGET_MODE_CONFLUENCE): New @hook.
>>> 	* doc/tm.texi.in: Regenerate.
>>> 	* mode-switching.cc (confluence_info): New variable.
>>> 	(mode_confluence, forward_confluence_n, forward_transfer): New
>>> 	functions.
>>> 	(optimize_mode_switching): Use them to calculate mode_in when
>>> 	TARGET_MODE_CONFLUENCE is defined.
>> OK.  There's certain similarities between this and the compatible states
>> we can use to reduce vsetvl instructions in RV-V.   I wonder if Juzhe or
>> Lehua could utilize this and do less custom optimization code in the RV
>> backend.
> 
> Here's an update based on what you pointed out in 10/12.  The change
> from last time is to add:
> 
>    if (targetm.mode_switching.backprop)
>      clear_aux_for_edges ();
> 
> before the main loop.  Tested as before.
> 
> Thanks,
> Richard
> 
> 
> gcc/
> 	* target.def (mode_switching.confluence): New hook.
> 	* doc/tm.texi (TARGET_MODE_CONFLUENCE): New @hook.
> 	* doc/tm.texi.in: Regenerate.
> 	* mode-switching.cc (confluence_info): New variable.
> 	(mode_confluence, forward_confluence_n, forward_transfer): New
> 	functions.
> 	(optimize_mode_switching): Use them to calculate mode_in when
> 	TARGET_MODE_CONFLUENCE is defined.
OK.  That's the whole set, right?

jeff

Jeff Law <jeffreyalaw@gmail.com> writes:
> On 11/11/23 08:54, Richard Sandiford wrote:
>> Jeff Law <jeffreyalaw@gmail.com> writes:
>>> On 11/5/23 11:50, Richard Sandiford wrote:
>>>> The mode-switching pass assumed that all of an entity's modes
>>>> were mutually exclusive.  However, the upcoming SME changes
>>>> have an entity with some overlapping modes, so that there is
>>>> sometimes a "superunion" mode that contains two given modes.
>>>> We can use this relationship to pass something more helpful than
>>>> "don't know" to the emit hook.
>>>>
>>>> This patch adds a new hook that targets can use to specify
>>>> a mode confluence operator.
>>>>
>>>> With mutually exclusive modes, it's possible to compute a block's
>>>> incoming and outgoing modes by looking at its availability sets.
>>>> With the confluence operator, we instead need to solve a full
>>>> dataflow problem.
>>>>
>>>> However, when emitting a mode transition, the upcoming SME use of
>>>> mode-switching benefits from having as much information as possible
>>>> about the starting mode.  Calculating this information is definitely
>>>> worth the compile time.
>>>>
>>>> The dataflow problem is written to work before and after the LCM
>>>> problem has been solved.  A later patch makes use of this.
>>>>
>>>> While there (since git blame would ping me for the reindented code),
>>>> I used a lambda to avoid the cut-&-pasted loops.
>>>>
>>>> gcc/
>>>> 	* target.def (mode_switching.confluence): New hook.
>>>> 	* doc/tm.texi (TARGET_MODE_CONFLUENCE): New @hook.
>>>> 	* doc/tm.texi.in: Regenerate.
>>>> 	* mode-switching.cc (confluence_info): New variable.
>>>> 	(mode_confluence, forward_confluence_n, forward_transfer): New
>>>> 	functions.
>>>> 	(optimize_mode_switching): Use them to calculate mode_in when
>>>> 	TARGET_MODE_CONFLUENCE is defined.
>>> OK.  There's certain similarities between this and the compatible states
>>> we can use to reduce vsetvl instructions in RV-V.   I wonder if Juzhe or
>>> Lehua could utilize this and do less custom optimization code in the RV
>>> backend.
>> 
>> Here's an update based on what you pointed out in 10/12.  The change
>> from last time is to add:
>> 
>>    if (targetm.mode_switching.backprop)
>>      clear_aux_for_edges ();
>> 
>> before the main loop.  Tested as before.
>> 
>> Thanks,
>> Richard
>> 
>> 
>> gcc/
>> 	* target.def (mode_switching.confluence): New hook.
>> 	* doc/tm.texi (TARGET_MODE_CONFLUENCE): New @hook.
>> 	* doc/tm.texi.in: Regenerate.
>> 	* mode-switching.cc (confluence_info): New variable.
>> 	(mode_confluence, forward_confluence_n, forward_transfer): New
>> 	functions.
>> 	(optimize_mode_switching): Use them to calculate mode_in when
>> 	TARGET_MODE_CONFLUENCE is defined.
> OK.  That's the whole set, right?

Yeah, that's everything, thanks.  I've now pushed the series.

Richard