[PATCH] Performance/size improvement to single_use when matching GIMPLE.

[PATCH] Performance/size improvement to single_use when matching GIMPLE.

[Roger Sayle]

[-- Attachment #1: Type: text/plain, Size: 1007 bytes --]

 

This patch improves the implementation of single_use as used in code

generated from match.pd for patterns using :s.  The current implementation

contains the logic "has_zero_uses (t) || has_single_use (t)" which

performs a loop over the uses to first check if there are zero non-debug

uses [which is rare], then another loop over these uses to check if there

is exactly one non-debug use.  This can be better implemented using a

single loop.

 

This function is currently inlined over 800 times in gimple-match.cc,

whose .o on x86_64-pc-linux-gnu is now up to 30 Mbytes, so speeding up

and shrinking this function should help offset the growth in match.pd

for GCC 12.

 

This patch has been tested on x86_64-pc-linux-gnu with make bootstrap

and make -k check with no new failures.  Ok for mainline?

 

 

2022-03-15  Roger Sayle  <roger@nextmovesoftware.com>

 

gcc/ChangeLog

* gimple-match-head.cc (single_use): Implement inline using a

single loop.

 

Thanks in advance,

Roger

--

 


[-- Attachment #2: patchsu.txt --]
[-- Type: text/plain, Size: 891 bytes --]

diff --git a/gcc/gimple-match-head.cc b/gcc/gimple-match-head.cc
index 74d5818..fc537b9 100644
--- a/gcc/gimple-match-head.cc
+++ b/gcc/gimple-match-head.cc
@@ -1163,7 +1163,22 @@ types_match (tree t1, tree t2)
 static inline bool
 single_use (tree t)
 {
-  return TREE_CODE (t) != SSA_NAME || has_zero_uses (t) || has_single_use (t);
+  if (TREE_CODE (t) != SSA_NAME)
+    return true;
+
+  /* Inline return has_zero_uses (t) || has_single_use (t);  */
+  const ssa_use_operand_t *const head = &(SSA_NAME_IMM_USE_NODE (t));
+  const ssa_use_operand_t *ptr;
+  bool single = false;
+
+  for (ptr = head->next; ptr != head; ptr = ptr->next)
+    if (USE_STMT(ptr) && !is_gimple_debug (USE_STMT (ptr)))
+      {
+        if (single)
+          return false;
+	single = true;
+      }
+  return true;
 }
 
 /* Return true if math operations should be canonicalized,

Re: [PATCH] Performance/size improvement to single_use when matching GIMPLE.

[Richard Biener]

On Tue, 15 Mar 2022, Roger Sayle wrote:

>  
> 
> This patch improves the implementation of single_use as used in code
> 
> generated from match.pd for patterns using :s.  The current implementation
> 
> contains the logic "has_zero_uses (t) || has_single_use (t)" which
> 
> performs a loop over the uses to first check if there are zero non-debug
> 
> uses [which is rare], then another loop over these uses to check if there
> 
> is exactly one non-debug use.  This can be better implemented using a
> 
> single loop.
> 
>  
> 
> This function is currently inlined over 800 times in gimple-match.cc,
> 
> whose .o on x86_64-pc-linux-gnu is now up to 30 Mbytes, so speeding up
> 
> and shrinking this function should help offset the growth in match.pd
> 
> for GCC 12.
> 
>  
> 
> This patch has been tested on x86_64-pc-linux-gnu with make bootstrap
> 
> and make -k check with no new failures.  Ok for mainline?

Note the intent of has_zero_uses () is even simpler - it's the case
for when there's no SSA operand info on the stmt (no update_stmt called
yet).  More precisely it wants to catch the case where the definition
of the SSA name is not in the IL.

I'm not sure if we want to twist the effective semantics at this
point (I guess we do not want that), so the patch looks like an
improvement.  But may I ask to move the function out of line for
even more savings?  Just put it in gimple-match-head.cc and have it
not declared inline.  I think we may want to go as far and
declare the function 'pure' using ATTRIBUTE_PURE.

>  
> 
>  
> 
> 2022-03-15  Roger Sayle  <roger@nextmovesoftware.com>
> 
>  
> 
> gcc/ChangeLog
> 
> * gimple-match-head.cc (single_use): Implement inline using a
> 
> single loop.
> 
>  
> 
> Thanks in advance,
> 
> Roger
> 
> --
> 
>  
> 
> 

-- 
Richard Biener <rguenther@suse.de>
SUSE Software Solutions Germany GmbH, Maxfeldstrasse 5, 90409 Nuernberg,
Germany; GF: Ivo Totev; HRB 36809 (AG Nuernberg)

RE: [PATCH] Performance/size improvement to single_use when matching GIMPLE.

[Roger Sayle]

Hi Richard,
Interestingly, I've already done a little analysis on the influence of
inlining
in gimple-match-head.cc.  With the new improved/smaller implementation
of single_use there's actually no significant change in code size from
removing
the inline.  Likewise for constant_for_folding and do_valueize/3.

The biggest improvement is from removing inline from get_def, and the
second biggest from do_valueize/2, but removing inline from types_match
is actually a size regression.

The results, sorted on size of gimple_match.o during stage1 therefore
checking the inlining of the host compiler, are:

 12215488       -types_match
 12215456      gimple-match.o        constant_for_folding/do_valueize
3/single_use
 12215080       -do_valueize 2
 12215016       -get_def

I can redo the analysis for stage3, but this was a little more inconvenient.
I do, however, have other ideas for improving the situation... stay tuned.

Cheers,
Roger
--

> -----Original Message-----
> From: Richard Biener <rguenther@suse.de>
> Sent: 15 March 2022 09:18
> To: Roger Sayle <roger@nextmovesoftware.com>
> Cc: 'GCC Patches' <gcc-patches@gcc.gnu.org>; 'Marc Glisse'
> <marc.glisse@inria.fr>
> Subject: Re: [PATCH] Performance/size improvement to single_use when
> matching GIMPLE.
> 
> On Tue, 15 Mar 2022, Roger Sayle wrote:
> 
> >
> >
> > This patch improves the implementation of single_use as used in code
> >
> > generated from match.pd for patterns using :s.  The current
> > implementation
> >
> > contains the logic "has_zero_uses (t) || has_single_use (t)" which
> >
> > performs a loop over the uses to first check if there are zero
> > non-debug
> >
> > uses [which is rare], then another loop over these uses to check if
> > there
> >
> > is exactly one non-debug use.  This can be better implemented using a
> >
> > single loop.
> >
> >
> >
> > This function is currently inlined over 800 times in gimple-match.cc,
> >
> > whose .o on x86_64-pc-linux-gnu is now up to 30 Mbytes, so speeding up
> >
> > and shrinking this function should help offset the growth in match.pd
> >
> > for GCC 12.
> >
> >
> >
> > This patch has been tested on x86_64-pc-linux-gnu with make bootstrap
> >
> > and make -k check with no new failures.  Ok for mainline?
> 
> Note the intent of has_zero_uses () is even simpler - it's the case for
when
> there's no SSA operand info on the stmt (no update_stmt called yet).  More
> precisely it wants to catch the case where the definition of the SSA name
is not
> in the IL.
> 
> I'm not sure if we want to twist the effective semantics at this point (I
guess we
> do not want that), so the patch looks like an improvement.  But may I ask
to
> move the function out of line for even more savings?  Just put it in
gimple-
> match-head.cc and have it not declared inline.  I think we may want to go
as far
> and declare the function 'pure' using ATTRIBUTE_PURE.
> 
> >
> >
> >
> >
> > 2022-03-15  Roger Sayle  <roger@nextmovesoftware.com>
> >
> >
> >
> > gcc/ChangeLog
> >
> > * gimple-match-head.cc (single_use): Implement inline using a
> >
> > single loop.
> >
> >
> >
> > Thanks in advance,
> >
> > Roger
> >
> > --
> >
> >
> >
> >
> 
> --
> Richard Biener <rguenther@suse.de>
> SUSE Software Solutions Germany GmbH, Maxfeldstrasse 5, 90409 Nuernberg,
> Germany; GF: Ivo Totev; HRB 36809 (AG Nuernberg)