[PATCH] Improve PR44563

[PATCH] Improve PR44563

[Richard Biener]

This reduces the time spent in cgraph call-site hash by providing
inline version of htab_hash_pointer.

Bootstrap / regtest on x86_64-unknown-linux-gnu in progress.

Ok?

Thanks,
Richard.

2015-03-09  Richard Biener  <rguenther@suse.de>

	PR middle-end/44563
	* cgraph.h (struct cgraph_edge_hasher): Add hash overload
	for compare_type.
	* cgraph.c (cgraph_edge_hasher::hash): Inline htab_hash_pointer.
	(cgraph_update_edge_in_call_site_hash): Use cgraph_edge_hasher::hash.
	(cgraph_add_edge_to_call_site_hash): Likewise.
	(cgraph_node::get_edge): Likewise.
	(cgraph_edge::set_call_stmt): Likewise.
	(cgraph_edge::remove_caller): Likewise.

Index: gcc/cgraph.c
===================================================================
*** gcc/cgraph.c	(revision 221277)
--- gcc/cgraph.c	(working copy)
*************** cgraph_node::get_for_asmname (tree asmna
*** 663,669 ****
  hashval_t
  cgraph_edge_hasher::hash (cgraph_edge *e)
  {
!   return htab_hash_pointer (e->call_stmt);
  }
  
  /* Return nonzero if the call_stmt of of cgraph_edge X is stmt *Y.  */
--- 663,681 ----
  hashval_t
  cgraph_edge_hasher::hash (cgraph_edge *e)
  {
!   /* This is a really poor hash function, but it is what the current code uses,
!      so I am reusing it to avoid an additional axis in testing.  */
!   return (hashval_t) ((intptr_t)e->call_stmt >> 3);
! }
! 
! /* Returns a hash value for X (which really is a cgraph_edge).  */
! 
! hashval_t
! cgraph_edge_hasher::hash (gimple call_stmt)
! {
!   /* This is a really poor hash function, but it is what the current code uses,
!      so I am reusing it to avoid an additional axis in testing.  */
!   return (hashval_t) ((intptr_t)call_stmt >> 3);
  }
  
  /* Return nonzero if the call_stmt of of cgraph_edge X is stmt *Y.  */
*************** static inline void
*** 680,688 ****
  cgraph_update_edge_in_call_site_hash (cgraph_edge *e)
  {
    gimple call = e->call_stmt;
!   *e->caller->call_site_hash->find_slot_with_hash (call,
! 						   htab_hash_pointer (call),
! 						   INSERT) = e;
  }
  
  /* Add call graph edge E to call site hash of its caller.  */
--- 692,699 ----
  cgraph_update_edge_in_call_site_hash (cgraph_edge *e)
  {
    gimple call = e->call_stmt;
!   *e->caller->call_site_hash->find_slot_with_hash
!       (call, cgraph_edge_hasher::hash (call), INSERT) = e;
  }
  
  /* Add call graph edge E to call site hash of its caller.  */
*************** cgraph_add_edge_to_call_site_hash (cgrap
*** 695,702 ****
    if (e->speculative && e->indirect_unknown_callee)
      return;
    cgraph_edge **slot = e->caller->call_site_hash->find_slot_with_hash
! 				   (e->call_stmt,
! 				    htab_hash_pointer (e->call_stmt), INSERT);
    if (*slot)
      {
        gcc_assert (((cgraph_edge *)*slot)->speculative);
--- 706,712 ----
    if (e->speculative && e->indirect_unknown_callee)
      return;
    cgraph_edge **slot = e->caller->call_site_hash->find_slot_with_hash
!       (e->call_stmt, cgraph_edge_hasher::hash (e->call_stmt), INSERT);
    if (*slot)
      {
        gcc_assert (((cgraph_edge *)*slot)->speculative);
*************** cgraph_node::get_edge (gimple call_stmt)
*** 718,725 ****
    int n = 0;
  
    if (call_site_hash)
!     return call_site_hash->find_with_hash (call_stmt,
! 					   htab_hash_pointer (call_stmt));
  
    /* This loop may turn out to be performance problem.  In such case adding
       hashtables into call nodes with very many edges is probably best
--- 728,735 ----
    int n = 0;
  
    if (call_site_hash)
!     return call_site_hash->find_with_hash
! 	(call_stmt, cgraph_edge_hasher::hash (call_stmt));
  
    /* This loop may turn out to be performance problem.  In such case adding
       hashtables into call nodes with very many edges is probably best
*************** cgraph_edge::set_call_stmt (gcall *new_s
*** 782,788 ****
        && (!speculative || !indirect_unknown_callee))
      {
        caller->call_site_hash->remove_elt_with_hash
! 	(call_stmt, htab_hash_pointer (call_stmt));
      }
  
    cgraph_edge *e = this;
--- 792,798 ----
        && (!speculative || !indirect_unknown_callee))
      {
        caller->call_site_hash->remove_elt_with_hash
! 	(call_stmt, cgraph_edge_hasher::hash (call_stmt));
      }
  
    cgraph_edge *e = this;
*************** cgraph_edge::remove_caller (void)
*** 987,994 ****
  	caller->callees = next_callee;
      }
    if (caller->call_site_hash)
!     caller->call_site_hash->remove_elt_with_hash (call_stmt,
! 						  htab_hash_pointer (call_stmt));
  }
  
  /* Put the edge onto the free list.  */
--- 997,1004 ----
  	caller->callees = next_callee;
      }
    if (caller->call_site_hash)
!     caller->call_site_hash->remove_elt_with_hash
! 	(call_stmt, cgraph_edge_hasher::hash (call_stmt));
  }
  
  /* Put the edge onto the free list.  */
Index: gcc/cgraph.h
===================================================================
*** gcc/cgraph.h	(revision 221277)
--- gcc/cgraph.h	(working copy)
*************** struct cgraph_edge_hasher : ggc_hasher<c
*** 788,793 ****
--- 788,794 ----
    typedef gimple compare_type;
  
    static hashval_t hash (cgraph_edge *);
+   static hashval_t hash (gimple);
    static bool equal (cgraph_edge *, gimple);
  };
  

Re: [PATCH] Improve PR44563

[Steven Bosscher]

On Mon, Mar 9, 2015 at 4:12 PM, Richard Biener wrote:
> !   /* This is a really poor hash function, but it is what the current code uses,
> !      so I am reusing it to avoid an additional axis in testing.  */

This is a bit silly as a comment, because after your patch the
"current" code is the patched code. Better to reference the
htab_hash_pointer function.

But can't we add an inline version in hashtab.h instead?

Ciao!
Steven

Re: [PATCH] Improve PR44563

[Jan Hubicka]

> 
> This reduces the time spent in cgraph call-site hash by providing
> inline version of htab_hash_pointer.
> 
> Bootstrap / regtest on x86_64-unknown-linux-gnu in progress.
> 
> Ok?
> 
> Thanks,
> Richard.
> 
> 2015-03-09  Richard Biener  <rguenther@suse.de>
> 
> 	PR middle-end/44563
> 	* cgraph.h (struct cgraph_edge_hasher): Add hash overload
> 	for compare_type.
> 	* cgraph.c (cgraph_edge_hasher::hash): Inline htab_hash_pointer.
> 	(cgraph_update_edge_in_call_site_hash): Use cgraph_edge_hasher::hash.
> 	(cgraph_add_edge_to_call_site_hash): Likewise.
> 	(cgraph_node::get_edge): Likewise.
> 	(cgraph_edge::set_call_stmt): Likewise.
> 	(cgraph_edge::remove_caller): Likewise.

Seems reosnable to me and patch is OK.  Since hash-map is now GGC safe, won't
it be faster to use it instead? The hash is really mapping stmts to edges, so
hash-map seems most fitting datastructure in our grand new C++ world.

Honza

Re: [PATCH] Improve PR44563

[Richard Biener]

On Tue, 10 Mar 2015, Jan Hubicka wrote:

> > 
> > This reduces the time spent in cgraph call-site hash by providing
> > inline version of htab_hash_pointer.
> > 
> > Bootstrap / regtest on x86_64-unknown-linux-gnu in progress.
> > 
> > Ok?
> > 
> > Thanks,
> > Richard.
> > 
> > 2015-03-09  Richard Biener  <rguenther@suse.de>
> > 
> > 	PR middle-end/44563
> > 	* cgraph.h (struct cgraph_edge_hasher): Add hash overload
> > 	for compare_type.
> > 	* cgraph.c (cgraph_edge_hasher::hash): Inline htab_hash_pointer.
> > 	(cgraph_update_edge_in_call_site_hash): Use cgraph_edge_hasher::hash.
> > 	(cgraph_add_edge_to_call_site_hash): Likewise.
> > 	(cgraph_node::get_edge): Likewise.
> > 	(cgraph_edge::set_call_stmt): Likewise.
> > 	(cgraph_edge::remove_caller): Likewise.
> 
> Seems reosnable to me and patch is OK.  Since hash-map is now GGC safe, won't
> it be faster to use it instead? The hash is really mapping stmts to edges, so
> hash-map seems most fitting datastructure in our grand new C++ world.

hash-map is just a wrapper around hash-table, so it would be a code 
cleanup at most.  Not sure if it gets any nicer with using that.

I have applied the patch with adjusted comments on the hash functions
as requested by Steven.

Richard.

Re: [PATCH] Improve PR44563

[Jan Hubicka]

Hi,
the g++.dg/tree-ssa/pr61034.C has turned out to be sensitive to PUSH_ARGS
settings so fixing it on PPC64 caused x86_64 to regress. This patch introduce
temporary so the code is consistent between PPC64 and x86_64.

Comitted after ICR dicussion with Richard.

Honza

Index: ChangeLog
===================================================================
--- ChangeLog	(revision 222526)
+++ ChangeLog	(working copy)
@@ -1,3 +1,7 @@
+2015-04-28  Jan Hubicka  <hubicka@ucw.cz>
+
+	* g++.dg/tree-ssa/pr61034.C: Add temporary; fix template.
+
 2015-04-28  Marek Polacek  <polacek@redhat.com>
 
 	PR c/65901
Index: g++.dg/tree-ssa/pr61034.C
===================================================================
--- g++.dg/tree-ssa/pr61034.C	(revision 222526)
+++ g++.dg/tree-ssa/pr61034.C	(working copy)
@@ -34,7 +34,8 @@ inline I operator- (I a, I const&b) { re
 inline bool operator< (I const&a, I const&b) { return a.o->num < b.o->num; }
 
 bool f(I a, I b, I c, I d) {
-    return (a * d - b * c) * (a * b - c * d) < 42;
+    I tmp = (a * d - b * c) * (a * b - c * d);
+    return tmp < 42;
 }
 
 // We should be able to CSE most references to count and thus remove