[patch] speed up ifcvt:cond_move_convert_if_block

[patch] speed up ifcvt:cond_move_convert_if_block

[Steven Bosscher]

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

Hello,

In PR54146, ifcvt spends a lot of time just clearing memory. This
patch changes the value maps to pointer-maps to fix this issue.

Bootstrapped&tested on x86_64-unknown-linux-gnu. OK?

Ciao!
Steven

[-- Attachment #2: PR54146_ifcvt.diff --]
[-- Type: application/octet-stream, Size: 9333 bytes --]

	PR tree-optimization/54146
	* ifcvt.c: Include pointer-set.h.
	(cond_move_process_if_block): Change type of then_regs and
	else_regs from alloca'd array to pointer_sets.
	(check_cond_move_block): Update for this change.
	(cond_move_convert_if_block): Likewise.
	* Makefile.in: Fix dependencies for ifcvt.o.

Index: ifcvt.c
===================================================================
--- ifcvt.c	(revision 190150)
+++ ifcvt.c	(working copy)
@@ -43,6 +43,7 @@
 #include "tree-pass.h"
 #include "df.h"
 #include "vec.h"
+#include "pointer-set.h"
 #include "vecprim.h"
 #include "dbgcnt.h"
 
@@ -2687,12 +2688,14 @@ noce_process_if_block (struct noce_if_in
 
 /* Check whether a block is suitable for conditional move conversion.
    Every insn must be a simple set of a register to a constant or a
-   register.  For each assignment, store the value in the array VALS,
-   indexed by register number, then store the register number in
-   REGS.  COND is the condition we will test.  */
+   register.  For each assignment, store the value in the pointer map
+   VALS, keyed indexed by register pointer, then store the register
+   pointer in REGS.  COND is the condition we will test.  */
 
 static int
-check_cond_move_block (basic_block bb, rtx *vals, VEC (int, heap) **regs,
+check_cond_move_block (basic_block bb,
+		       struct pointer_map_t *vals,
+		       VEC (rtx, heap) **regs,
 		       rtx cond)
 {
   rtx insn;
@@ -2706,6 +2709,7 @@ check_cond_move_block (basic_block bb, r
   FOR_BB_INSNS (bb, insn)
     {
       rtx set, dest, src;
+      void **slot;
 
       if (!NONDEBUG_INSN_P (insn) || JUMP_P (insn))
 	continue;
@@ -2732,14 +2736,14 @@ check_cond_move_block (basic_block bb, r
       /* Don't try to handle this if the source register was
 	 modified earlier in the block.  */
       if ((REG_P (src)
-	   && vals[REGNO (src)] != NULL)
+	   && pointer_map_contains (vals, src))
 	  || (GET_CODE (src) == SUBREG && REG_P (SUBREG_REG (src))
-	      && vals[REGNO (SUBREG_REG (src))] != NULL))
+	      && pointer_map_contains (vals, SUBREG_REG (src))))
 	return FALSE;
 
       /* Don't try to handle this if the destination register was
 	 modified earlier in the block.  */
-      if (vals[REGNO (dest)] != NULL)
+      if (pointer_map_contains (vals, dest))
 	return FALSE;
 
       /* Don't try to handle this if the condition uses the
@@ -2753,17 +2757,18 @@ check_cond_move_block (basic_block bb, r
 	  && modified_between_p (src, insn, NEXT_INSN (BB_END (bb))))
 	return FALSE;
 
-      vals[REGNO (dest)] = src;
+      slot = pointer_map_insert (vals, (void *) dest);
+      *slot = (void *) src;
 
-      VEC_safe_push (int, heap, *regs, REGNO (dest));
+      VEC_safe_push (rtx, heap, *regs, dest);
     }
 
   return TRUE;
 }
 
 /* Given a basic block BB suitable for conditional move conversion,
-   a condition COND, and arrays THEN_VALS and ELSE_VALS containing the
-   register values depending on COND, emit the insns in the block as
+   a condition COND, and pointer maps THEN_VALS and ELSE_VALS containing
+   the register values depending on COND, emit the insns in the block as
    conditional moves.  If ELSE_BLOCK is true, THEN_BB was already
    processed.  The caller has started a sequence for the conversion.
    Return true if successful, false if something goes wrong.  */
@@ -2771,7 +2776,8 @@ check_cond_move_block (basic_block bb, r
 static bool
 cond_move_convert_if_block (struct noce_if_info *if_infop,
 			    basic_block bb, rtx cond,
-			    rtx *then_vals, rtx *else_vals,
+			    struct pointer_map_t *then_vals,
+			    struct pointer_map_t *else_vals,
 			    bool else_block_p)
 {
   enum rtx_code code;
@@ -2784,7 +2790,7 @@ cond_move_convert_if_block (struct noce_
   FOR_BB_INSNS (bb, insn)
     {
       rtx set, target, dest, t, e;
-      unsigned int regno;
+      void **then_slot, **else_slot;
 
       /* ??? Maybe emit conditional debug insn?  */
       if (!NONDEBUG_INSN_P (insn) || JUMP_P (insn))
@@ -2793,10 +2799,11 @@ cond_move_convert_if_block (struct noce_
       gcc_assert (set && REG_P (SET_DEST (set)));
 
       dest = SET_DEST (set);
-      regno = REGNO (dest);
 
-      t = then_vals[regno];
-      e = else_vals[regno];
+      then_slot = pointer_map_contains (then_vals, dest);
+      else_slot = pointer_map_contains (else_vals, dest);
+      t = then_slot ? (rtx) *then_slot : NULL_RTX;
+      e = else_slot ? (rtx) *else_slot : NULL_RTX;
 
       if (else_block_p)
 	{
@@ -2840,31 +2847,25 @@ cond_move_process_if_block (struct noce_
   rtx jump = if_info->jump;
   rtx cond = if_info->cond;
   rtx seq, loc_insn;
-  int max_reg, size, c, reg;
-  rtx *then_vals;
-  rtx *else_vals;
-  VEC (int, heap) *then_regs = NULL;
-  VEC (int, heap) *else_regs = NULL;
+  rtx reg;
+  int c;
+  struct pointer_map_t *then_vals;
+  struct pointer_map_t *else_vals;
+  VEC (rtx, heap) *then_regs = NULL;
+  VEC (rtx, heap) *else_regs = NULL;
   unsigned int i;
+  int success_p = FALSE;
 
   /* Build a mapping for each block to the value used for each
      register.  */
-  max_reg = max_reg_num ();
-  size = (max_reg + 1) * sizeof (rtx);
-  then_vals = (rtx *) alloca (size);
-  else_vals = (rtx *) alloca (size);
-  memset (then_vals, 0, size);
-  memset (else_vals, 0, size);
+  then_vals = pointer_map_create ();
+  else_vals = pointer_map_create ();
 
   /* Make sure the blocks are suitable.  */
   if (!check_cond_move_block (then_bb, then_vals, &then_regs, cond)
       || (else_bb
 	  && !check_cond_move_block (else_bb, else_vals, &else_regs, cond)))
-    {
-      VEC_free (int, heap, then_regs);
-      VEC_free (int, heap, else_regs);
-      return FALSE;
-    }
+    goto done;
 
   /* Make sure the blocks can be used together.  If the same register
      is set in both blocks, and is not set to a constant in both
@@ -2873,41 +2874,38 @@ cond_move_process_if_block (struct noce_
      source register does not change after the assignment.  Also count
      the number of registers set in only one of the blocks.  */
   c = 0;
-  FOR_EACH_VEC_ELT (int, then_regs, i, reg)
+  FOR_EACH_VEC_ELT (rtx, then_regs, i, reg)
     {
-      if (!then_vals[reg] && !else_vals[reg])
-	continue;
+      void **then_slot = pointer_map_contains (then_vals, reg);
+      void **else_slot = pointer_map_contains (else_vals, reg);
 
-      if (!else_vals[reg])
+      gcc_checking_assert (then_slot);
+      if (!else_slot)
 	++c;
       else
 	{
-	  if (!CONSTANT_P (then_vals[reg])
-	      && !CONSTANT_P (else_vals[reg])
-	      && !rtx_equal_p (then_vals[reg], else_vals[reg]))
-	    {
-	      VEC_free (int, heap, then_regs);
-	      VEC_free (int, heap, else_regs);
-	      return FALSE;
-	    }
+	  rtx then_val = (rtx) *then_slot;
+	  rtx else_val = (rtx) *else_slot;
+	  if (!CONSTANT_P (then_val) && !CONSTANT_P (else_val)
+	      && !rtx_equal_p (then_val, else_val))
+	    goto done;
 	}
     }
 
   /* Finish off c for MAX_CONDITIONAL_EXECUTE.  */
-  FOR_EACH_VEC_ELT (int, else_regs, i, reg)
-    if (!then_vals[reg])
-      ++c;
+  FOR_EACH_VEC_ELT (rtx, else_regs, i, reg)
+    {
+      gcc_checking_assert (pointer_map_contains (else_vals, reg));
+      if (!pointer_map_contains (then_vals, reg))
+	++c;
+    }
 
   /* Make sure it is reasonable to convert this block.  What matters
      is the number of assignments currently made in only one of the
      branches, since if we convert we are going to always execute
      them.  */
   if (c > MAX_CONDITIONAL_EXECUTE)
-    {
-      VEC_free (int, heap, then_regs);
-      VEC_free (int, heap, else_regs);
-      return FALSE;
-    }
+    goto done;
 
   /* Try to emit the conditional moves.  First do the then block,
      then do anything left in the else blocks.  */
@@ -2919,17 +2917,11 @@ cond_move_process_if_block (struct noce_
 					  then_vals, else_vals, true)))
     {
       end_sequence ();
-      VEC_free (int, heap, then_regs);
-      VEC_free (int, heap, else_regs);
-      return FALSE;
+      goto done;
     }
   seq = end_ifcvt_sequence (if_info);
   if (!seq)
-    {
-      VEC_free (int, heap, then_regs);
-      VEC_free (int, heap, else_regs);
-      return FALSE;
-    }
+    goto done;
 
   loc_insn = first_active_insn (then_bb);
   if (!loc_insn)
@@ -2960,9 +2952,14 @@ cond_move_process_if_block (struct noce_
 
   num_updated_if_blocks++;
 
-  VEC_free (int, heap, then_regs);
-  VEC_free (int, heap, else_regs);
-  return TRUE;
+  success_p = TRUE;
+
+done:
+  pointer_map_destroy (then_vals);
+  pointer_map_destroy (else_vals);
+  VEC_free (rtx, heap, then_regs);
+  VEC_free (rtx, heap, else_regs);
+  return success_p;
 }
 
 \f
Index: Makefile.in
===================================================================
--- Makefile.in	(revision 190150)
+++ Makefile.in	(working copy)
@@ -3350,7 +3350,7 @@ regrename.o : regrename.c $(CONFIG_H) $(
 ifcvt.o : ifcvt.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) \
    $(REGS_H) $(DIAGNOSTIC_CORE_H) $(FLAGS_H) insn-config.h $(FUNCTION_H) $(RECOG_H) \
    $(TARGET_H) $(BASIC_BLOCK_H) $(EXPR_H) output.h $(EXCEPT_H) $(TM_P_H) \
-   $(OPTABS_H) $(CFGLOOP_H) hard-reg-set.h \
+   $(OPTABS_H) $(CFGLOOP_H) hard-reg-set.h pointer-set.h \
    $(TREE_PASS_H) $(DF_H) $(DBGCNT_H)
 params.o : params.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(COMMON_TARGET_H) \
    $(PARAMS_H) $(DIAGNOSTIC_CORE_H)

Re: [patch] speed up ifcvt:cond_move_convert_if_block

[Richard Guenther]

On Mon, Aug 6, 2012 at 8:54 AM, Steven Bosscher <stevenb.gcc@gmail.com> wrote:
> Hello,
>
> In PR54146, ifcvt spends a lot of time just clearing memory. This
> patch changes the value maps to pointer-maps to fix this issue.
>
> Bootstrapped&tested on x86_64-unknown-linux-gnu. OK?

Ok!

Thanks,
Richard.

> Ciao!
> Steven

Re: [patch] speed up ifcvt:cond_move_convert_if_block

[Paolo Bonzini]

Il 06/08/2012 08:54, Steven Bosscher ha scritto:
> Hello,
> 
> In PR54146, ifcvt spends a lot of time just clearing memory. This
> patch changes the value maps to pointer-maps to fix this issue.
> 
> Bootstrapped&tested on x86_64-unknown-linux-gnu. OK?

Nice, but perhaps we need a sparsemap to do even better?

Paolo

Re: [patch] speed up ifcvt:cond_move_convert_if_block

[Steven Bosscher]

On Mon, Aug 6, 2012 at 1:07 PM, Paolo Bonzini <bonzini@gnu.org> wrote:
> Il 06/08/2012 08:54, Steven Bosscher ha scritto:
>> Hello,
>>
>> In PR54146, ifcvt spends a lot of time just clearing memory. This
>> patch changes the value maps to pointer-maps to fix this issue.
>>
>> Bootstrapped&tested on x86_64-unknown-linux-gnu. OK?
>
> Nice, but perhaps we need a sparsemap to do even better?

If you mean sparseset: no, it won't do any better.

My first idea was to use a sparseset, but:

1. The amount of memory allocated is simply too big. In fact, it'd be
even worse than before: 4*max_regno*sizeof(rtx) instead of "only"
2*max_regno*sizeof(rtx).

2. sparseset has the same problem of memory clearing (for valgrind,
see sparseset_alloc).

Remember, we can call this function cond_move_convert_if_block
O(n_basic_block) times: On a CFG with mostly regular control flow,
i.e. no or few computed jumps, jump tables, and exception handlers,
the number of IF-THEN-{,ELSE_}-JOIN blocks will be O(n_basic_blocks)
and cond_move_convert_if_block is called on almost all of them.

What could work, is to allocate a sparseset once at the beginning of
if_convert, but I don't see any good reason to add a pair of global
variables for this. My patch reduces the time spent in ifcvt to almost
nothing (down from ~250s, which is still not so bad, considering we're
looking at a function with >260000 basic blocks!).

Ciao!
Steven

Re: [patch] speed up ifcvt:cond_move_convert_if_block

[Paolo Bonzini]

Il 06/08/2012 13:15, Steven Bosscher ha scritto:
> On Mon, Aug 6, 2012 at 1:07 PM, Paolo Bonzini <bonzini@gnu.org> wrote:
>> Il 06/08/2012 08:54, Steven Bosscher ha scritto:
>>> Hello,
>>>
>>> In PR54146, ifcvt spends a lot of time just clearing memory. This
>>> patch changes the value maps to pointer-maps to fix this issue.
>>>
>>> Bootstrapped&tested on x86_64-unknown-linux-gnu. OK?
>>
>> Nice, but perhaps we need a sparsemap to do even better?
> 
> If you mean sparseset: no, it won't do any better.

No, I mean "inventing" a sparseset that cannot do boolean operations,
but can store an associative value in a second dense array.  That is

   sparsemap_insert(m, k, v)
   {
     if (!sparsemap_contains(m, k)) {
       s->sparse[k] = s->members++;
       s->dense_keys[i] = k;
     }
     i = s->sparse[k];
     s->dense_values[i] = v;
   }

   sparsemap_contains(m, k)
   {
     if (!sparsemap_contains(m, k)) {
       return -1;
     } else {
       return s->dense_values[i];
     }

> My first idea was to use a sparseset, but:
> 
> 1. The amount of memory allocated is simply too big. In fact, it'd be
> even worse than before: 4*max_regno*sizeof(rtx) instead of "only"
> 2*max_regno*sizeof(rtx).

Yeah, sparseset wastes some memory.  I wonder if the dense array should
be allocated separately and even made dynamically resizable, also because...

> 2. sparseset has the same problem of memory clearing (for valgrind,
> see sparseset_alloc).

... only the sparse array needs this clearing, but currently we do it
for both.

> What could work, is to allocate a sparseset once at the beginning of
> if_convert, but I don't see any good reason to add a pair of global
> variables for this.

Yes, this is what I meant.  Fast clearing is where sparsesets behave
well, so it makes sense to make them global in that case.  What I missed
was that the maps remain small.  Otherwise they would also need clearing.

Paolo

Re: [patch] speed up ifcvt:cond_move_convert_if_block

[Steven Bosscher]

On Mon, Aug 6, 2012 at 1:27 PM, Paolo Bonzini <bonzini@gnu.org> wrote:
>> 2. sparseset has the same problem of memory clearing (for valgrind,
>> see sparseset_alloc).
>
> ... only the sparse array needs this clearing, but currently we do it
> for both.

And according to the fat comment before the xcalloc, it's not even
really needed. Why can't we just tell valgrind to treat the memory as
defined, like in this patchlet:

Index: sparseset.c
===================================================================
--- sparseset.c (revision 190418)
+++ sparseset.c (working copy)
@@ -30,12 +30,14 @@ sparseset_alloc (SPARSESET_ELT_TYPE n_elms)
   unsigned int n_bytes = sizeof (struct sparseset_def)
                         + ((n_elms - 1) * 2 * sizeof (SPARSESET_ELT_TYPE));

-  /* We use xcalloc rather than xmalloc to silence some valgrind uninitialized
+  sparseset set = XNEWVAR(sparseset, n_bytes);
+
+  /* Mark the sparseset as defined to silence some valgrind uninitialized
      read errors when accessing set->sparse[n] when "n" is not, and never has
      been, in the set.  These uninitialized reads are expected, by design and
-     harmless.  If this turns into a performance problem due to some future
-     additional users of sparseset, we can revisit this decision.  */
-  sparseset set = (sparseset) xcalloc (1, n_bytes);
+     harmless.  */
+  VALGRIND_DISCARD (VALGRIND_MAKE_MEM_DEFINED (set, n_bytes));
+
   set->dense = &(set->elms[0]);
   set->sparse = &(set->elms[n_elms]);
   set->size = n_elms;


I have never built GCC with valgrind checking, so I don't know if this
is correct. But there has to be a better solution than calling
xcalloc...

Ciao!
Steven

Re: [patch] speed up ifcvt:cond_move_convert_if_block

[Richard Guenther]

On Thu, Aug 16, 2012 at 1:11 AM, Steven Bosscher <stevenb.gcc@gmail.com> wrote:
> On Mon, Aug 6, 2012 at 1:27 PM, Paolo Bonzini <bonzini@gnu.org> wrote:
>>> 2. sparseset has the same problem of memory clearing (for valgrind,
>>> see sparseset_alloc).
>>
>> ... only the sparse array needs this clearing, but currently we do it
>> for both.
>
> And according to the fat comment before the xcalloc, it's not even
> really needed. Why can't we just tell valgrind to treat the memory as
> defined, like in this patchlet:

Indeed ... I suppose ok if it bootstraps / tests w/o valgrind checking and
if a cc1 builds with valgrind checking.

Thanks,
Richard.

> Index: sparseset.c
> ===================================================================
> --- sparseset.c (revision 190418)
> +++ sparseset.c (working copy)
> @@ -30,12 +30,14 @@ sparseset_alloc (SPARSESET_ELT_TYPE n_elms)
>    unsigned int n_bytes = sizeof (struct sparseset_def)
>                          + ((n_elms - 1) * 2 * sizeof (SPARSESET_ELT_TYPE));
>
> -  /* We use xcalloc rather than xmalloc to silence some valgrind uninitialized
> +  sparseset set = XNEWVAR(sparseset, n_bytes);
> +
> +  /* Mark the sparseset as defined to silence some valgrind uninitialized
>       read errors when accessing set->sparse[n] when "n" is not, and never has
>       been, in the set.  These uninitialized reads are expected, by design and
> -     harmless.  If this turns into a performance problem due to some future
> -     additional users of sparseset, we can revisit this decision.  */
> -  sparseset set = (sparseset) xcalloc (1, n_bytes);
> +     harmless.  */
> +  VALGRIND_DISCARD (VALGRIND_MAKE_MEM_DEFINED (set, n_bytes));
> +
>    set->dense = &(set->elms[0]);
>    set->sparse = &(set->elms[n_elms]);
>    set->size = n_elms;
>
>
> I have never built GCC with valgrind checking, so I don't know if this
> is correct. But there has to be a better solution than calling
> xcalloc...
>
> Ciao!
> Steven

Re: [patch] speed up ifcvt:cond_move_convert_if_block

[Steven Bosscher]

On Thu, Aug 16, 2012 at 12:06 PM, Richard Guenther
<richard.guenther@gmail.com> wrote:
> On Thu, Aug 16, 2012 at 1:11 AM, Steven Bosscher <stevenb.gcc@gmail.com> wrote:
>> On Mon, Aug 6, 2012 at 1:27 PM, Paolo Bonzini <bonzini@gnu.org> wrote:
>>>> 2. sparseset has the same problem of memory clearing (for valgrind,
>>>> see sparseset_alloc).
>>>
>>> ... only the sparse array needs this clearing, but currently we do it
>>> for both.
>>
>> And according to the fat comment before the xcalloc, it's not even
>> really needed. Why can't we just tell valgrind to treat the memory as
>> defined, like in this patchlet:
>
> Indeed ... I suppose ok if it bootstraps / tests w/o valgrind checking and
> if a cc1 builds with valgrind checking.

Here's what I'll commit:

Index: sparseset.c
===================================================================
--- sparseset.c (revision 190474)
+++ sparseset.c (working copy)
@@ -30,12 +30,14 @@
   unsigned int n_bytes = sizeof (struct sparseset_def)
                         + ((n_elms - 1) * 2 * sizeof (SPARSESET_ELT_TYPE));

-  /* We use xcalloc rather than xmalloc to silence some valgrind uninitialized
+  sparseset set = XNEWVAR(struct sparseset_def, n_bytes);
+
+  /* Mark the sparseset as defined to silence some valgrind uninitialized
      read errors when accessing set->sparse[n] when "n" is not, and never has
      been, in the set.  These uninitialized reads are expected, by design and
-     harmless.  If this turns into a performance problem due to some future
-     additional users of sparseset, we can revisit this decision.  */
-  sparseset set = (sparseset) xcalloc (1, n_bytes);
+     harmless.  */
+  VALGRIND_DISCARD (VALGRIND_MAKE_MEM_DEFINED (set, n_bytes));
+
   set->dense = &(set->elms[0]);
   set->sparse = &(set->elms[n_elms]);
   set->size = n_elms;