[vta] stabilize loop-unroll across insn uid variations

[vta] stabilize loop-unroll across insn uid variations

[Alexandre Oliva]

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

compare-debug detected some differences causes by RTL loop unrolling,
because debug insns changed the insn uids it uses as hashes.  Because
of this change, insns were walked in different orders, and different
decisions were made.

I couldn't find a simple way to stabilize the uids or compute good and
stable hashes without using them.  This is the only place AFAICT that
uses them as hashes, so I came up with a solution that will waste a
bit of memory, but that will ensure we walk the insns in a consistent
order, regardless of changes to insn uids.  To make up for the
(little) additional memory, we should get a slight speedup when
walking the lists with type-safe inlinable calls, rather than walking
every entry of a hashtable that's designed to be about half empty,
with a type-unsafe non-inlinable callback.

This is the patch I'm installing in the VTA branch.


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: vta-loop-unroll-stabilize.patch --]
[-- Type: text/x-patch, Size: 12308 bytes --]

for  gcc/ChangeLog.vta
from  Alexandre Oliva  <aoliva@redhat.com>

	* loop-unroll.c (struct iv_to_split): Add pointer to next.
	(struct var_to_expand): Likewise.
	(struct opt_info): Add head and tail for linked lists of the above.
	(analyze_insn_to_expand_var): Initialize next.
	(analyze_iv_to_split_insn): Likewise.
	(analyze_insns_in_loop): Create linked lists.
	(allocate_basic_variable): Simplify for use without hash table.
	(insert_var_expansion_initialization): Likewise, make it type-safer.
	(combine_var_copies_in_loop_exit): Likewise.
	(apply_opt_in_copies): Walk lists rather than hash tables.
	(release_var_copies): Simplified and inlined by hand into...
	(free_opt_info): ... this function.

Index: gcc/loop-unroll.c
===================================================================
--- gcc/loop-unroll.c.orig	2008-10-03 15:38:23.000000000 -0300
+++ gcc/loop-unroll.c	2008-10-07 05:21:58.000000000 -0300
@@ -1,5 +1,6 @@
 /* Loop unrolling and peeling.
-   Copyright (C) 2002, 2003, 2004, 2005, 2007 Free Software Foundation, Inc.
+   Copyright (C) 2002, 2003, 2004, 2005, 2007, 2008
+   Free Software Foundation, Inc.
 
 This file is part of GCC.
 
@@ -76,6 +77,7 @@ struct iv_to_split
   rtx base_var;		/* The variable on that the values in the further
 			   iterations are based.  */
   rtx step;		/* Step of the induction variable.  */
+  struct iv_to_split *next; /* Next entry in walking order.  */
   unsigned n_loc;
   unsigned loc[3];	/* Location where the definition of the induction
 			   variable occurs in the insn.  For example if
@@ -90,6 +92,7 @@ struct var_to_expand
   rtx insn;		           /* The insn in that the variable expansion occurs.  */
   rtx reg;                         /* The accumulator which is expanded.  */
   VEC(rtx,heap) *var_expansions;   /* The copies of the accumulator which is expanded.  */ 
+  struct var_to_expand *next;	   /* Next entry in walking order.  */
   enum rtx_code op;                /* The type of the accumulation - addition, subtraction 
                                       or multiplication.  */
   int expansion_count;             /* Count the number of expansions generated so far.  */
@@ -109,8 +112,12 @@ struct var_to_expand
 struct opt_info
 {
   htab_t insns_to_split;           /* A hashtable of insns to split.  */
+  struct iv_to_split *iv_to_split_head; /* The first iv to split.  */
+  struct iv_to_split **iv_to_split_tail; /* Pointer to the tail of the list.  */
   htab_t insns_with_var_to_expand; /* A hashtable of insns with accumulators
                                       to expand.  */
+  struct var_to_expand *var_to_expand_head; /* The first var to expand.  */
+  struct var_to_expand **var_to_expand_tail; /* Pointer to the tail of the list.  */
   unsigned first_new_block;        /* The first basic block that was
                                       duplicated.  */
   basic_block loop_exit;           /* The loop exit basic block.  */
@@ -138,9 +145,10 @@ static struct var_to_expand *analyze_ins
 static bool referenced_in_one_insn_in_loop_p (struct loop *, rtx);
 static struct iv_to_split *analyze_iv_to_split_insn (rtx);
 static void expand_var_during_unrolling (struct var_to_expand *, rtx);
-static int insert_var_expansion_initialization (void **, void *);
-static int combine_var_copies_in_loop_exit (void **, void *);
-static int release_var_copies (void **, void *);
+static void insert_var_expansion_initialization (struct var_to_expand *,
+						 basic_block);
+static void combine_var_copies_in_loop_exit (struct var_to_expand *,
+					     basic_block);
 static rtx get_expansion (struct var_to_expand *);
 
 /* Unroll and/or peel (depending on FLAGS) LOOPS.  */
@@ -1645,8 +1653,9 @@ analyze_insn_to_expand_var (struct loop 
   /* Record the accumulator to expand.  */
   ves = XNEW (struct var_to_expand);
   ves->insn = insn;
-  ves->var_expansions = VEC_alloc (rtx, heap, 1);
   ves->reg = copy_rtx (dest);
+  ves->var_expansions = VEC_alloc (rtx, heap, 1);
+  ves->next = NULL;
   ves->op = GET_CODE (src);
   ves->expansion_count = 0;
   ves->reuse_expansion = 0;
@@ -1722,6 +1731,7 @@ analyze_iv_to_split_insn (rtx insn)
   ivts->insn = insn;
   ivts->base_var = NULL_RTX;
   ivts->step = iv.step;
+  ivts->next = NULL;
   ivts->n_loc = 1;
   ivts->loc[0] = 1;
   
@@ -1753,8 +1763,12 @@ analyze_insns_in_loop (struct loop *loop
   body = get_loop_body (loop);
 
   if (flag_split_ivs_in_unroller)
-    opt_info->insns_to_split = htab_create (5 * loop->num_nodes,
-                                            si_info_hash, si_info_eq, free);
+    {
+      opt_info->insns_to_split = htab_create (5 * loop->num_nodes,
+					      si_info_hash, si_info_eq, free);
+      opt_info->iv_to_split_head = NULL;
+      opt_info->iv_to_split_tail = &opt_info->iv_to_split_head;
+    }
   
   /* Record the loop exit bb and loop preheader before the unrolling.  */
   opt_info->loop_preheader = loop_preheader_edge (loop)->src;
@@ -1771,8 +1785,13 @@ analyze_insns_in_loop (struct loop *loop
   
   if (flag_variable_expansion_in_unroller
       && can_apply)
-    opt_info->insns_with_var_to_expand = htab_create (5 * loop->num_nodes,
-						      ve_info_hash, ve_info_eq, free);
+    {
+      opt_info->insns_with_var_to_expand = htab_create (5 * loop->num_nodes,
+							ve_info_hash,
+							ve_info_eq, free);
+      opt_info->var_to_expand_head = NULL;
+      opt_info->var_to_expand_tail = &opt_info->var_to_expand_head;
+    }
   
   for (i = 0; i < loop->num_nodes; i++)
     {
@@ -1791,7 +1810,10 @@ analyze_insns_in_loop (struct loop *loop
         if (ivts)
           {
             slot1 = htab_find_slot (opt_info->insns_to_split, ivts, INSERT);
+	    gcc_assert (*slot1 == NULL);
             *slot1 = ivts;
+	    *opt_info->iv_to_split_tail = ivts;
+	    opt_info->iv_to_split_tail = &ivts->next;
             continue;
           }
         
@@ -1801,7 +1823,10 @@ analyze_insns_in_loop (struct loop *loop
         if (ves)
           {
             slot2 = htab_find_slot (opt_info->insns_with_var_to_expand, ves, INSERT);
+	    gcc_assert (*slot2 == NULL);
             *slot2 = ves;
+	    *opt_info->var_to_expand_tail = ves;
+	    opt_info->var_to_expand_tail = &ves->next;
           }
       }
     }
@@ -1861,18 +1886,14 @@ get_ivts_expr (rtx expr, struct iv_to_sp
   return ret;
 }
 
-/* Allocate basic variable for the induction variable chain.  Callback for
-   htab_traverse.  */
+/* Allocate basic variable for the induction variable chain.  */
 
-static int
-allocate_basic_variable (void **slot, void *data ATTRIBUTE_UNUSED)
+static void
+allocate_basic_variable (struct iv_to_split *ivts)
 {
-  struct iv_to_split *ivts = (struct iv_to_split *) *slot;
   rtx expr = *get_ivts_expr (single_set (ivts->insn), ivts);
 
   ivts->base_var = gen_reg_rtx (GET_MODE (expr));
-
-  return 1;
 }
 
 /* Insert initialization of basic variable of IVTS before INSN, taking
@@ -2009,14 +2030,13 @@ expand_var_during_unrolling (struct var_
       }
 }
 
-/* Initialize the variable expansions in loop preheader.  
-   Callbacks for htab_traverse.  PLACE_P is the loop-preheader 
-   basic block where the initialization of the expansions 
-   should take place.  The expansions are initialized with (-0)
-   when the operation is plus or minus to honor sign zero.
-   This way we can prevent cases where the sign of the final result is
-   effected by the sign of the expansion.
-   Here is an example to demonstrate this:
+/* Initialize the variable expansions in loop preheader.  PLACE is the
+   loop-preheader basic block where the initialization of the
+   expansions should take place.  The expansions are initialized with
+   (-0) when the operation is plus or minus to honor sign zero.  This
+   way we can prevent cases where the sign of the final result is
+   effected by the sign of the expansion.  Here is an example to
+   demonstrate this:
    
    for (i = 0 ; i < n; i++)
      sum += something;
@@ -2037,18 +2057,17 @@ expand_var_during_unrolling (struct var_
    should be initialized with -zero as well (otherwise we will get +zero
    as the final result).  */
 
-static int
-insert_var_expansion_initialization (void **slot, void *place_p)
+static void
+insert_var_expansion_initialization (struct var_to_expand *ve,
+				     basic_block place)
 {
-  struct var_to_expand *ve = (struct var_to_expand *) *slot;
-  basic_block place = (basic_block)place_p;
   rtx seq, var, zero_init, insn;
   unsigned i;
   enum machine_mode mode = GET_MODE (ve->reg);
   bool honor_signed_zero_p = HONOR_SIGNED_ZEROS (mode);
 
   if (VEC_length (rtx, ve->var_expansions) == 0)
-    return 1;
+    return;
   
   start_sequence ();
   if (ve->op == PLUS || ve->op == MINUS) 
@@ -2076,26 +2095,21 @@ insert_var_expansion_initialization (voi
     insn = NEXT_INSN (insn);
   
   emit_insn_after (seq, insn); 
-  /* Continue traversing the hash table.  */
-  return 1;   
 }
 
-/*  Combine the variable expansions at the loop exit.  
-    Callbacks for htab_traverse.  PLACE_P is the loop exit
-    basic block where the summation of the expansions should 
-    take place.  */
+/* Combine the variable expansions at the loop exit.  PLACE is the
+   loop exit basic block where the summation of the expansions should
+   take place.  */
 
-static int
-combine_var_copies_in_loop_exit (void **slot, void *place_p)
+static void
+combine_var_copies_in_loop_exit (struct var_to_expand *ve, basic_block place)
 {
-  struct var_to_expand *ve = (struct var_to_expand *) *slot;
-  basic_block place = (basic_block)place_p;
   rtx sum = ve->reg;
   rtx expr, seq, var, insn;
   unsigned i;
 
   if (VEC_length (rtx, ve->var_expansions) == 0)
-    return 1;
+    return;
   
   start_sequence ();
   if (ve->op == PLUS || ve->op == MINUS)
@@ -2122,9 +2136,6 @@ combine_var_copies_in_loop_exit (void **
     insn = NEXT_INSN (insn);
 
   emit_insn_after (seq, insn);
-  
-  /* Continue traversing the hash table.  */
-  return 1;
 }
 
 /* Apply loop optimizations in loop copies using the 
@@ -2153,7 +2164,8 @@ apply_opt_in_copies (struct opt_info *op
   
   /* Allocate the basic variables (i0).  */
   if (opt_info->insns_to_split)
-    htab_traverse (opt_info->insns_to_split, allocate_basic_variable, NULL);
+    for (ivts = opt_info->iv_to_split_head; ivts; ivts = ivts->next)
+      allocate_basic_variable (ivts);
   
   for (i = opt_info->first_new_block; i < (unsigned) last_basic_block; i++)
     {
@@ -2217,12 +2229,10 @@ apply_opt_in_copies (struct opt_info *op
      and take care of combining them at the loop exit.  */ 
   if (opt_info->insns_with_var_to_expand)
     {
-      htab_traverse (opt_info->insns_with_var_to_expand, 
-                     insert_var_expansion_initialization, 
-                     opt_info->loop_preheader);
-      htab_traverse (opt_info->insns_with_var_to_expand, 
-                     combine_var_copies_in_loop_exit, 
-                     opt_info->loop_exit);
+      for (ves = opt_info->var_to_expand_head; ves; ves = ves->next)
+	insert_var_expansion_initialization (ves, opt_info->loop_preheader);
+      for (ves = opt_info->var_to_expand_head; ves; ves = ves->next)
+	combine_var_copies_in_loop_exit (ves, opt_info->loop_exit);
     }
   
   /* Rewrite also the original loop body.  Find them as originals of the blocks
@@ -2263,20 +2273,6 @@ apply_opt_in_copies (struct opt_info *op
     }
 }
 
-/*  Release the data structures used for the variable expansion
-    optimization.  Callbacks for htab_traverse.  */
-
-static int
-release_var_copies (void **slot, void *data ATTRIBUTE_UNUSED)
-{
-  struct var_to_expand *ve = (struct var_to_expand *) *slot;
-  
-  VEC_free (rtx, heap, ve->var_expansions);
-  
-  /* Continue traversing the hash table.  */
-  return 1;
-}
-
 /* Release OPT_INFO.  */
 
 static void
@@ -2286,8 +2282,10 @@ free_opt_info (struct opt_info *opt_info
     htab_delete (opt_info->insns_to_split);
   if (opt_info->insns_with_var_to_expand)
     {
-      htab_traverse (opt_info->insns_with_var_to_expand, 
-                     release_var_copies, NULL);
+      struct var_to_expand *ves;
+
+      for (ves = opt_info->var_to_expand_head; ves; ves = ves->next)
+	VEC_free (rtx, heap, ves->var_expansions);
       htab_delete (opt_info->insns_with_var_to_expand);
     }
   free (opt_info);

[-- Attachment #3: Type: text/plain, Size: 257 bytes --]


-- 
Alexandre Oliva         http://www.lsd.ic.unicamp.br/~oliva/
Free Software Evangelist  oliva@{lsd.ic.unicamp.br, gnu.org}
FSFLA Board Member       ¡Sé Libre! => http://www.fsfla.org/
Red Hat Compiler Engineer   aoliva@{redhat.com, gcc.gnu.org}

Re: [vta] stabilize loop-unroll across insn uid variations

[Paolo Bonzini]

Alexandre Oliva wrote:
> compare-debug detected some differences causes by RTL loop unrolling,
> because debug insns changed the insn uids it uses as hashes.  Because
> of this change, insns were walked in different orders, and different
> decisions were made.

This should also go in trunk IMO.

Paolo

Re: [vta] stabilize loop-unroll across insn uid variations

[Richard Guenther]

On Tue, Oct 7, 2008 at 11:36 AM, Paolo Bonzini <bonzini@gnu.org> wrote:
> Alexandre Oliva wrote:
>> compare-debug detected some differences causes by RTL loop unrolling,
>> because debug insns changed the insn uids it uses as hashes.  Because
>> of this change, insns were walked in different orders, and different
>> decisions were made.
>
> This should also go in trunk IMO.

To prevent ordering changes we should never walk hashtables
(we could walk std::map, which provides ordered keys).  One
cheap way out is to walk a bitmap of the UIDs - I didn't look
too closely at the patch, but maybe using bitmaps are cheaper
than a linked list.

Richard.

> Paolo
>
>

Re: [vta] stabilize loop-unroll across insn uid variations

[Alexandre Oliva]

On Oct  7, 2008, "Richard Guenther" <richard.guenther@gmail.com> wrote:

> On Tue, Oct 7, 2008 at 11:36 AM, Paolo Bonzini <bonzini@gnu.org> wrote:
>> Alexandre Oliva wrote:
>>> compare-debug detected some differences causes by RTL loop unrolling,
>>> because debug insns changed the insn uids it uses as hashes.  Because
>>> of this change, insns were walked in different orders, and different
>>> decisions were made.

>> This should also go in trunk IMO.

I don't see that it would have any noticeable effect in the trunk,
but I surely don't oppose reducing the divergence :-)

> One cheap way out is to walk a bitmap of the UIDs - I didn't look
> too closely at the patch, but maybe using bitmaps are cheaper than a
> linked list.

I actually considered that.  IIRC I even implemented something, using
DF_INSN_UID_GET, but I wasn't sure this would reach all insns at that
point.  IIRC I actually tested for that and got failures for
newly-added insns, but I'm not sure, this was almost a month ago.

Anyhow, extending the array used by DF to maintain the UID-to-INSN map
complete would waste more memory than any savings we might obtain with
a bitmap at this point.  So it would get worse performance (walking
bitmaps is worse than walking a list, even if still O(n)), possibly
worse memory (O(N) rather than O(n), with N >> n, if df->insns isn't
complete), and still somewhat impredictable ordering (UID ordering is
not necessarily the same as sequential ordering).

Nevertheless, if trunk *does* maintain a complete df->insns map,
updated on the fly, then it might make sense to use it.  Whatever
works, I don't have strong feelings either way.

-- 
Alexandre Oliva         http://www.lsd.ic.unicamp.br/~oliva/
Free Software Evangelist  oliva@{lsd.ic.unicamp.br, gnu.org}
FSFLA Board Member       ¡Sé Libre! => http://www.fsfla.org/
Red Hat Compiler Engineer   aoliva@{redhat.com, gcc.gnu.org}

[trunk<-vta] Re: [vta] stabilize loop-unroll across insn uid variations

[Alexandre Oliva]

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

On Oct  7, 2008, Alexandre Oliva <aoliva@redhat.com> wrote:

> compare-debug detected some differences causes by RTL loop unrolling,
> because debug insns changed the insn uids it uses as hashes.  Because
> of this change, insns were walked in different orders, and different
> decisions were made.

> I couldn't find a simple way to stabilize the uids or compute good and
> stable hashes without using them.  This is the only place AFAICT that
> uses them as hashes, so I came up with a solution that will waste a
> bit of memory, but that will ensure we walk the insns in a consistent
> order, regardless of changes to insn uids.  To make up for the
> (little) additional memory, we should get a slight speedup when
> walking the lists with type-safe inlinable calls, rather than walking
> every entry of a hashtable that's designed to be about half empty,
> with a type-unsafe non-inlinable callback.

Ok for trunk?


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: vta-loop-unroll-stabilize.patch --]
[-- Type: text/x-patch, Size: 12059 bytes --]

for  gcc/ChangeLog
from  Alexandre Oliva  <aoliva@redhat.com>

	* loop-unroll.c (struct iv_to_split): Add pointer to next.
	(struct var_to_expand): Likewise.
	(struct opt_info): Add head and tail for linked lists of the above.
	(analyze_insn_to_expand_var): Initialize next.
	(analyze_iv_to_split_insn): Likewise.
	(analyze_insns_in_loop): Create linked lists.
	(allocate_basic_variable): Simplify for use without hash table.
	(insert_var_expansion_initialization): Likewise, make it type-safer.
	(combine_var_copies_in_loop_exit): Likewise.
	(apply_opt_in_copies): Walk lists rather than hash tables.
	(release_var_copies): Simplified and inlined by hand into...
	(free_opt_info): ... this function.

Index: gcc/loop-unroll.c
===================================================================
--- gcc/loop-unroll.c.orig	2009-03-01 02:16:18.000000000 -0300
+++ gcc/loop-unroll.c	2009-05-28 04:07:22.000000000 -0300
@@ -77,6 +77,7 @@ struct iv_to_split
   rtx base_var;		/* The variable on that the values in the further
 			   iterations are based.  */
   rtx step;		/* Step of the induction variable.  */
+  struct iv_to_split *next; /* Next entry in walking order.  */
   unsigned n_loc;
   unsigned loc[3];	/* Location where the definition of the induction
 			   variable occurs in the insn.  For example if
@@ -91,6 +92,7 @@ struct var_to_expand
   rtx insn;		           /* The insn in that the variable expansion occurs.  */
   rtx reg;                         /* The accumulator which is expanded.  */
   VEC(rtx,heap) *var_expansions;   /* The copies of the accumulator which is expanded.  */ 
+  struct var_to_expand *next;	   /* Next entry in walking order.  */
   enum rtx_code op;                /* The type of the accumulation - addition, subtraction 
                                       or multiplication.  */
   int expansion_count;             /* Count the number of expansions generated so far.  */
@@ -110,8 +112,12 @@ struct var_to_expand
 struct opt_info
 {
   htab_t insns_to_split;           /* A hashtable of insns to split.  */
+  struct iv_to_split *iv_to_split_head; /* The first iv to split.  */
+  struct iv_to_split **iv_to_split_tail; /* Pointer to the tail of the list.  */
   htab_t insns_with_var_to_expand; /* A hashtable of insns with accumulators
                                       to expand.  */
+  struct var_to_expand *var_to_expand_head; /* The first var to expand.  */
+  struct var_to_expand **var_to_expand_tail; /* Pointer to the tail of the list.  */
   unsigned first_new_block;        /* The first basic block that was
                                       duplicated.  */
   basic_block loop_exit;           /* The loop exit basic block.  */
@@ -139,9 +145,10 @@ static struct var_to_expand *analyze_ins
 static bool referenced_in_one_insn_in_loop_p (struct loop *, rtx);
 static struct iv_to_split *analyze_iv_to_split_insn (rtx);
 static void expand_var_during_unrolling (struct var_to_expand *, rtx);
-static int insert_var_expansion_initialization (void **, void *);
-static int combine_var_copies_in_loop_exit (void **, void *);
-static int release_var_copies (void **, void *);
+static void insert_var_expansion_initialization (struct var_to_expand *,
+						 basic_block);
+static void combine_var_copies_in_loop_exit (struct var_to_expand *,
+					     basic_block);
 static rtx get_expansion (struct var_to_expand *);
 
 /* Unroll and/or peel (depending on FLAGS) LOOPS.  */
@@ -1646,8 +1653,9 @@ analyze_insn_to_expand_var (struct loop 
   /* Record the accumulator to expand.  */
   ves = XNEW (struct var_to_expand);
   ves->insn = insn;
-  ves->var_expansions = VEC_alloc (rtx, heap, 1);
   ves->reg = copy_rtx (dest);
+  ves->var_expansions = VEC_alloc (rtx, heap, 1);
+  ves->next = NULL;
   ves->op = GET_CODE (src);
   ves->expansion_count = 0;
   ves->reuse_expansion = 0;
@@ -1723,6 +1731,7 @@ analyze_iv_to_split_insn (rtx insn)
   ivts->insn = insn;
   ivts->base_var = NULL_RTX;
   ivts->step = iv.step;
+  ivts->next = NULL;
   ivts->n_loc = 1;
   ivts->loc[0] = 1;
   
@@ -1754,8 +1763,12 @@ analyze_insns_in_loop (struct loop *loop
   body = get_loop_body (loop);
 
   if (flag_split_ivs_in_unroller)
-    opt_info->insns_to_split = htab_create (5 * loop->num_nodes,
-                                            si_info_hash, si_info_eq, free);
+    {
+      opt_info->insns_to_split = htab_create (5 * loop->num_nodes,
+					      si_info_hash, si_info_eq, free);
+      opt_info->iv_to_split_head = NULL;
+      opt_info->iv_to_split_tail = &opt_info->iv_to_split_head;
+    }
   
   /* Record the loop exit bb and loop preheader before the unrolling.  */
   opt_info->loop_preheader = loop_preheader_edge (loop)->src;
@@ -1772,8 +1785,13 @@ analyze_insns_in_loop (struct loop *loop
   
   if (flag_variable_expansion_in_unroller
       && can_apply)
-    opt_info->insns_with_var_to_expand = htab_create (5 * loop->num_nodes,
-						      ve_info_hash, ve_info_eq, free);
+    {
+      opt_info->insns_with_var_to_expand = htab_create (5 * loop->num_nodes,
+							ve_info_hash,
+							ve_info_eq, free);
+      opt_info->var_to_expand_head = NULL;
+      opt_info->var_to_expand_tail = &opt_info->var_to_expand_head;
+    }
   
   for (i = 0; i < loop->num_nodes; i++)
     {
@@ -1792,7 +1810,10 @@ analyze_insns_in_loop (struct loop *loop
         if (ivts)
           {
             slot1 = htab_find_slot (opt_info->insns_to_split, ivts, INSERT);
+	    gcc_assert (*slot1 == NULL);
             *slot1 = ivts;
+	    *opt_info->iv_to_split_tail = ivts;
+	    opt_info->iv_to_split_tail = &ivts->next;
             continue;
           }
         
@@ -1802,7 +1823,10 @@ analyze_insns_in_loop (struct loop *loop
         if (ves)
           {
             slot2 = htab_find_slot (opt_info->insns_with_var_to_expand, ves, INSERT);
+	    gcc_assert (*slot2 == NULL);
             *slot2 = ves;
+	    *opt_info->var_to_expand_tail = ves;
+	    opt_info->var_to_expand_tail = &ves->next;
           }
       }
     }
@@ -1862,18 +1886,14 @@ get_ivts_expr (rtx expr, struct iv_to_sp
   return ret;
 }
 
-/* Allocate basic variable for the induction variable chain.  Callback for
-   htab_traverse.  */
+/* Allocate basic variable for the induction variable chain.  */
 
-static int
-allocate_basic_variable (void **slot, void *data ATTRIBUTE_UNUSED)
+static void
+allocate_basic_variable (struct iv_to_split *ivts)
 {
-  struct iv_to_split *ivts = (struct iv_to_split *) *slot;
   rtx expr = *get_ivts_expr (single_set (ivts->insn), ivts);
 
   ivts->base_var = gen_reg_rtx (GET_MODE (expr));
-
-  return 1;
 }
 
 /* Insert initialization of basic variable of IVTS before INSN, taking
@@ -2010,14 +2030,13 @@ expand_var_during_unrolling (struct var_
       }
 }
 
-/* Initialize the variable expansions in loop preheader.  
-   Callbacks for htab_traverse.  PLACE_P is the loop-preheader 
-   basic block where the initialization of the expansions 
-   should take place.  The expansions are initialized with (-0)
-   when the operation is plus or minus to honor sign zero.
-   This way we can prevent cases where the sign of the final result is
-   effected by the sign of the expansion.
-   Here is an example to demonstrate this:
+/* Initialize the variable expansions in loop preheader.  PLACE is the
+   loop-preheader basic block where the initialization of the
+   expansions should take place.  The expansions are initialized with
+   (-0) when the operation is plus or minus to honor sign zero.  This
+   way we can prevent cases where the sign of the final result is
+   effected by the sign of the expansion.  Here is an example to
+   demonstrate this:
    
    for (i = 0 ; i < n; i++)
      sum += something;
@@ -2038,18 +2057,17 @@ expand_var_during_unrolling (struct var_
    should be initialized with -zero as well (otherwise we will get +zero
    as the final result).  */
 
-static int
-insert_var_expansion_initialization (void **slot, void *place_p)
+static void
+insert_var_expansion_initialization (struct var_to_expand *ve,
+				     basic_block place)
 {
-  struct var_to_expand *ve = (struct var_to_expand *) *slot;
-  basic_block place = (basic_block)place_p;
   rtx seq, var, zero_init, insn;
   unsigned i;
   enum machine_mode mode = GET_MODE (ve->reg);
   bool honor_signed_zero_p = HONOR_SIGNED_ZEROS (mode);
 
   if (VEC_length (rtx, ve->var_expansions) == 0)
-    return 1;
+    return;
   
   start_sequence ();
   if (ve->op == PLUS || ve->op == MINUS) 
@@ -2077,26 +2095,21 @@ insert_var_expansion_initialization (voi
     insn = NEXT_INSN (insn);
   
   emit_insn_after (seq, insn); 
-  /* Continue traversing the hash table.  */
-  return 1;   
 }
 
-/*  Combine the variable expansions at the loop exit.  
-    Callbacks for htab_traverse.  PLACE_P is the loop exit
-    basic block where the summation of the expansions should 
-    take place.  */
+/* Combine the variable expansions at the loop exit.  PLACE is the
+   loop exit basic block where the summation of the expansions should
+   take place.  */
 
-static int
-combine_var_copies_in_loop_exit (void **slot, void *place_p)
+static void
+combine_var_copies_in_loop_exit (struct var_to_expand *ve, basic_block place)
 {
-  struct var_to_expand *ve = (struct var_to_expand *) *slot;
-  basic_block place = (basic_block)place_p;
   rtx sum = ve->reg;
   rtx expr, seq, var, insn;
   unsigned i;
 
   if (VEC_length (rtx, ve->var_expansions) == 0)
-    return 1;
+    return;
   
   start_sequence ();
   if (ve->op == PLUS || ve->op == MINUS)
@@ -2123,9 +2136,6 @@ combine_var_copies_in_loop_exit (void **
     insn = NEXT_INSN (insn);
 
   emit_insn_after (seq, insn);
-  
-  /* Continue traversing the hash table.  */
-  return 1;
 }
 
 /* Apply loop optimizations in loop copies using the 
@@ -2154,7 +2164,8 @@ apply_opt_in_copies (struct opt_info *op
   
   /* Allocate the basic variables (i0).  */
   if (opt_info->insns_to_split)
-    htab_traverse (opt_info->insns_to_split, allocate_basic_variable, NULL);
+    for (ivts = opt_info->iv_to_split_head; ivts; ivts = ivts->next)
+      allocate_basic_variable (ivts);
   
   for (i = opt_info->first_new_block; i < (unsigned) last_basic_block; i++)
     {
@@ -2218,12 +2229,10 @@ apply_opt_in_copies (struct opt_info *op
      and take care of combining them at the loop exit.  */ 
   if (opt_info->insns_with_var_to_expand)
     {
-      htab_traverse (opt_info->insns_with_var_to_expand, 
-                     insert_var_expansion_initialization, 
-                     opt_info->loop_preheader);
-      htab_traverse (opt_info->insns_with_var_to_expand, 
-                     combine_var_copies_in_loop_exit, 
-                     opt_info->loop_exit);
+      for (ves = opt_info->var_to_expand_head; ves; ves = ves->next)
+	insert_var_expansion_initialization (ves, opt_info->loop_preheader);
+      for (ves = opt_info->var_to_expand_head; ves; ves = ves->next)
+	combine_var_copies_in_loop_exit (ves, opt_info->loop_exit);
     }
   
   /* Rewrite also the original loop body.  Find them as originals of the blocks
@@ -2264,20 +2273,6 @@ apply_opt_in_copies (struct opt_info *op
     }
 }
 
-/*  Release the data structures used for the variable expansion
-    optimization.  Callbacks for htab_traverse.  */
-
-static int
-release_var_copies (void **slot, void *data ATTRIBUTE_UNUSED)
-{
-  struct var_to_expand *ve = (struct var_to_expand *) *slot;
-  
-  VEC_free (rtx, heap, ve->var_expansions);
-  
-  /* Continue traversing the hash table.  */
-  return 1;
-}
-
 /* Release OPT_INFO.  */
 
 static void
@@ -2287,8 +2282,10 @@ free_opt_info (struct opt_info *opt_info
     htab_delete (opt_info->insns_to_split);
   if (opt_info->insns_with_var_to_expand)
     {
-      htab_traverse (opt_info->insns_with_var_to_expand, 
-                     release_var_copies, NULL);
+      struct var_to_expand *ves;
+
+      for (ves = opt_info->var_to_expand_head; ves; ves = ves->next)
+	VEC_free (rtx, heap, ves->var_expansions);
       htab_delete (opt_info->insns_with_var_to_expand);
     }
   free (opt_info);

[-- Attachment #3: Type: text/plain, Size: 258 bytes --]



-- 
Alexandre Oliva, freedom fighter    http://FSFLA.org/~lxoliva/
You must be the change you wish to see in the world. -- Gandhi
Be Free! -- http://FSFLA.org/   FSF Latin America board member
Free Software Evangelist      Red Hat Brazil Compiler Engineer

Re: [trunk<-vta] Re: [vta] stabilize loop-unroll across insn uid variations

[Richard Guenther]

On Mon, Jun 1, 2009 at 10:14 AM, Alexandre Oliva <aoliva@redhat.com> wrote:
> On Oct  7, 2008, Alexandre Oliva <aoliva@redhat.com> wrote:
>
>> compare-debug detected some differences causes by RTL loop unrolling,
>> because debug insns changed the insn uids it uses as hashes.  Because
>> of this change, insns were walked in different orders, and different
>> decisions were made.
>
>> I couldn't find a simple way to stabilize the uids or compute good and
>> stable hashes without using them.  This is the only place AFAICT that
>> uses them as hashes, so I came up with a solution that will waste a
>> bit of memory, but that will ensure we walk the insns in a consistent
>> order, regardless of changes to insn uids.  To make up for the
>> (little) additional memory, we should get a slight speedup when
>> walking the lists with type-safe inlinable calls, rather than walking
>> every entry of a hashtable that's designed to be about half empty,
>> with a type-unsafe non-inlinable callback.
>
> Ok for trunk?

I'll defer to Zdenek.

Richard.

Re: [trunk<-vta] Re: [vta] stabilize loop-unroll across insn uid variations

[Zdenek Dvorak]

Hi,

> On Mon, Jun 1, 2009 at 10:14 AM, Alexandre Oliva <aoliva@redhat.com> wrote:
> > On Oct  7, 2008, Alexandre Oliva <aoliva@redhat.com> wrote:
> >
> >> compare-debug detected some differences causes by RTL loop unrolling,
> >> because debug insns changed the insn uids it uses as hashes.  Because
> >> of this change, insns were walked in different orders, and different
> >> decisions were made.
> >
> >> I couldn't find a simple way to stabilize the uids or compute good and
> >> stable hashes without using them.  This is the only place AFAICT that
> >> uses them as hashes, so I came up with a solution that will waste a
> >> bit of memory, but that will ensure we walk the insns in a consistent
> >> order, regardless of changes to insn uids.  To make up for the
> >> (little) additional memory, we should get a slight speedup when
> >> walking the lists with type-safe inlinable calls, rather than walking
> >> every entry of a hashtable that's designed to be about half empty,
> >> with a type-unsafe non-inlinable callback.
> >
> > Ok for trunk?
> 
> I'll defer to Zdenek.

looks OK to me,

Zdenek