Strengthen ICF hash

[Jan Hubicka <hubicka at ucw dot cz>]

Hi,
getting more familiar with ipa-icf I start to understand why it is a compile
time hog for firefox.  I assumed it spends most of time streaming in bodies and
comparing them to see they are equivalent (after all about 10% of all symbols
turns out to be and each of that needs to be read to memory). In fact most of
time is actually spent by congreuence subdivision and calling final compares
in cases that are doomed to fail.

This is caused by a weak hash fixed in this patch and the fact that congruence
solver works way too hard - it could hash in the information known at WPA
time before starting the equivalence busyness.

Grepping the ICF logs, the most common reasons for mismatched went from
about 2million hits to about 300k.

The hash itself is quite simple (borrowing incremental hash for constants adding
very simple match for other stuff + logic to skip things that may match even if
they are syntactticaly different). The hash can be strenghtened significantly,
but I suppose we may do it based on actual profiling. It also is loosely based
on varasm.c constant pool hash implementation that was OK for years.

Bootstrapped/regtested x86_64-linux, will commit it shortly.

Honza

	* ipa-icf.c (sem_function::init): Fix formating; skip GIMPLE_PREDICT.
	(sem_item::add_expr): New function.
	(sem_function::hash_stmt): Handle operands of most statements.
	(sem_variable::get_hash): Hash the actual constructor.
	* ipa-icf.h (sem_item): Add add_expr.
	(sem_function): Update prototype of hash_stmt
Index: ipa-icf.c
===================================================================
--- ipa-icf.c	(revision 221090)
+++ ipa-icf.c	(working copy)
@@ -1030,7 +1030,8 @@ sem_function::init (void)
     unsigned nondbg_stmt_count = 0;
 
     edge e;
-    for (edge_iterator ei = ei_start (bb->preds); ei_cond (ei, &e); ei_next (&ei))
+    for (edge_iterator ei = ei_start (bb->preds); ei_cond (ei, &e);
+	 ei_next (&ei))
       cfg_checksum = iterative_hash_host_wide_int (e->flags,
 		     cfg_checksum);
 
@@ -1039,9 +1040,10 @@ sem_function::init (void)
       {
 	gimple stmt = gsi_stmt (gsi);
 
-	if (gimple_code (stmt) != GIMPLE_DEBUG)
+	if (gimple_code (stmt) != GIMPLE_DEBUG
+	    && gimple_code (stmt) != GIMPLE_PREDICT)
 	  {
-	    hash_stmt (&hstate, stmt);
+	    hash_stmt (stmt, hstate);
 	    nondbg_stmt_count++;
 	  }
       }
@@ -1051,7 +1053,8 @@ sem_function::init (void)
 
     /* Inserting basic block to hash table.  */
     sem_bb *semantic_bb = new sem_bb (bb, nondbg_stmt_count,
-				      EDGE_COUNT (bb->preds) + EDGE_COUNT (bb->succs));
+				      EDGE_COUNT (bb->preds)
+				      + EDGE_COUNT (bb->succs));
 
     bb_sorted.safe_push (semantic_bb);
   }
@@ -1059,52 +1062,120 @@ sem_function::init (void)
   parse_tree_args ();
 }
 
+/* Accumulate to HSTATE a hash of expression EXP.
+   Identical to inchash::add_expr, but guaranteed to be stable across LTO
+   and DECL equality classes.  */
+
+void
+sem_item::add_expr (const_tree exp, inchash::hash &hstate)
+{
+  if (exp == NULL_TREE)
+    {
+      hstate.merge_hash (0);
+      return;
+    }
+
+  /* Handled component can be matched in a cureful way proving equivalence
+     even if they syntactically differ.  Just skip them.  */
+  STRIP_NOPS (exp);
+  while (handled_component_p (exp))
+    exp = TREE_OPERAND (exp, 0);
+
+  enum tree_code code = TREE_CODE (exp);
+  hstate.add_int (code);
+
+  switch (code)
+    {
+    /* Use inchash::add_expr for everything that is LTO stable.  */
+    case VOID_CST:
+    case INTEGER_CST:
+    case REAL_CST:
+    case FIXED_CST:
+    case STRING_CST:
+    case COMPLEX_CST:
+    case VECTOR_CST:
+      inchash::add_expr (exp, hstate);
+      break;
+    case CONSTRUCTOR:
+      {
+	unsigned HOST_WIDE_INT idx;
+	tree value;
+
+	hstate.add_wide_int (int_size_in_bytes (TREE_TYPE (exp)));
+
+	FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (exp), idx, value)
+	  if (value)
+	    add_expr (value, hstate);
+	break;
+      }
+    case ADDR_EXPR:
+    case FDESC_EXPR:
+      add_expr (get_base_address (TREE_OPERAND (exp, 0)), hstate);
+      break;
+    case SSA_NAME:
+    case VAR_DECL:
+    case CONST_DECL:
+    case PARM_DECL:
+      hstate.add_wide_int (int_size_in_bytes (TREE_TYPE (exp)));
+      break;
+    case MEM_REF:
+    case POINTER_PLUS_EXPR:
+    case MINUS_EXPR:
+    case RANGE_EXPR:
+      add_expr (TREE_OPERAND (exp, 0), hstate);
+      add_expr (TREE_OPERAND (exp, 1), hstate);
+      break;
+    case PLUS_EXPR:
+      {
+	inchash::hash one, two;
+	add_expr (TREE_OPERAND (exp, 0), one);
+	add_expr (TREE_OPERAND (exp, 1), two);
+	hstate.add_commutative (one, two);
+      }
+      break;
+    CASE_CONVERT:
+      hstate.add_wide_int (int_size_in_bytes (TREE_TYPE (exp)));
+      return add_expr (TREE_OPERAND (exp, 0), hstate);
+    default:
+      break;
+    }
+}
+
 /* Improve accumulated hash for HSTATE based on a gimple statement STMT.  */
 
 void
-sem_function::hash_stmt (inchash::hash *hstate, gimple stmt)
+sem_function::hash_stmt (gimple stmt, inchash::hash &hstate)
 {
   enum gimple_code code = gimple_code (stmt);
 
-  hstate->add_int (code);
+  hstate.add_int (code);
 
-  if (code == GIMPLE_CALL)
+  switch (code)
     {
-      /* Checking of argument.  */
-      for (unsigned i = 0; i < gimple_call_num_args (stmt); ++i)
+    case GIMPLE_ASSIGN:
+      if (commutative_tree_code (gimple_assign_rhs_code (stmt))
+	  || commutative_ternary_tree_code (gimple_assign_rhs_code (stmt)))
 	{
-	  tree argument = gimple_call_arg (stmt, i);
+	  inchash::hash one, two;
 
-	  switch (TREE_CODE (argument))
-	    {
-	    case INTEGER_CST:
-	      if (tree_fits_shwi_p (argument))
-		hstate->add_wide_int (tree_to_shwi (argument));
-	      else if (tree_fits_uhwi_p (argument))
-		hstate->add_wide_int (tree_to_uhwi (argument));
-	      break;
-	    case REAL_CST:
-	      REAL_VALUE_TYPE c;
-	      HOST_WIDE_INT n;
-
-	      c = TREE_REAL_CST (argument);
-	      n = real_to_integer (&c);
-
-	      hstate->add_wide_int (n);
-	      break;
-	    case ADDR_EXPR:
-	      {
-		tree addr_operand = TREE_OPERAND (argument, 0);
-
-		if (TREE_CODE (addr_operand) == STRING_CST)
-		  hstate->add (TREE_STRING_POINTER (addr_operand),
-			       TREE_STRING_LENGTH (addr_operand));
-		break;
-	      }
-	    default:
-	      break;
-	    }
+	  add_expr (gimple_assign_rhs1 (stmt), one);
+	  add_expr (gimple_assign_rhs2 (stmt), two);
+	  hstate.add_commutative (one, two);
+	  add_expr (gimple_assign_lhs (stmt), hstate);
+	  break;
 	}
+      /* ... fall through ... */
+    case GIMPLE_CALL:
+    case GIMPLE_ASM:
+    case GIMPLE_COND:
+    case GIMPLE_GOTO:
+    case GIMPLE_RETURN:
+      /* All these statements are equivalent if their operands are.  */
+      for (unsigned i = 0; i < gimple_num_ops (stmt); ++i)
+	add_expr (gimple_op (stmt, i), hstate);
+    default:
+      break;
     }
 }
 
@@ -1474,17 +1545,17 @@ sem_variable::get_hash (void)
   if (hash)
     return hash;
 
+  /* All WPA streamed in symbols should have their hashes computed at compile
+     time.  At this point, the constructor may not be in memory at all.
+     DECL_INITIAL (decl) would be error_mark_node in that case.  */
+  gcc_assert (!node->lto_file_data);
+  tree ctor = DECL_INITIAL (decl);
   inchash::hash hstate;
 
   hstate.add_int (456346417);
-  hstate.add_int (TREE_CODE (ctor));
-
-  if (TREE_CODE (ctor) == CONSTRUCTOR)
-    {
-      unsigned length = vec_safe_length (CONSTRUCTOR_ELTS (ctor));
-      hstate.add_int (length);
-    }
-
+  if (DECL_SIZE (decl) && tree_fits_shwi_p (DECL_SIZE (decl)))
+    hstate.add_wide_int (tree_to_shwi (DECL_SIZE (decl)));
+  add_expr (ctor, hstate);
   hash = hstate.end ();
 
   return hash;
Index: ipa-icf.h
===================================================================
--- ipa-icf.h	(revision 221090)
+++ ipa-icf.h	(working copy)
@@ -241,6 +241,8 @@ public:
 protected:
   /* Cached, once calculated hash for the item.  */
   hashval_t hash;
+  /* Accumulate to HSTATE a hash of constructor expression EXP.  */
+  static void add_expr (const_tree exp, inchash::hash &hstate);
 
 private:
   /* Initialize internal data structures. Bitmap STACK is used for
@@ -290,7 +292,7 @@ public:
   }
 
   /* Improve accumulated hash for HSTATE based on a gimple statement STMT.  */
-  void hash_stmt (inchash::hash *inchash, gimple stmt);
+  void hash_stmt (gimple stmt, inchash::hash &inchash);
 
   /* Return true if polymorphic comparison must be processed.  */
   bool compare_polymorphic_p (void);