* genautomata.c (add_vect): Speedup by using integers as

        bit-vectors for walking through the comb_vect and finding
        a match.


git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@84811 138bc75d-0d04-0410-961f-82ee72b054a4

2 files changed, 76 insertions, 15 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 52c646fe2ef..532695d03dd 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,9 @@
+2004-07-16  Segher Boessenkool  <segher@kernel.crashing.org>
+
+	* genautomata.c (add_vect): Speedup by using integers as
+	bit-vectors for walking through the comb_vect and finding
+	a match.
+
 2004-07-16  Richard Sandiford  <rsandifo@redhat.com>
 
 	* config/mips/mips.c (mips_zero_if_equal): Only use XORs if the second
diff --git a/gcc/genautomata.c b/gcc/genautomata.c
index 88f7a91c3cc..292a2de1400 100644
--- a/gcc/genautomata.c
+++ b/gcc/genautomata.c
@@ -7578,6 +7578,7 @@ add_vect (state_ainsn_table_t tab, int vect_num, vect_el_t *vect,
   int no_state_value;
   vect_el_t vect_el;
   int i;
+  unsigned long vect_mask, comb_vect_mask;
 
   if (vect_length == 0)
     abort ();
@@ -7599,23 +7600,77 @@ add_vect (state_ainsn_table_t tab, int vect_num, vect_el_t *vect,
        first_unempty_vect_index++)
     if (vect [first_unempty_vect_index] != undefined_vect_el_value)
       break;
+
   /* Search for the place in comb vect for the inserted vect.  */
-  for (comb_vect_index = 0;
-       comb_vect_index < comb_vect_els_num;
-       comb_vect_index++)
-    {
-      for (vect_index = first_unempty_vect_index;
-           vect_index < vect_length
-             && vect_index + comb_vect_index < comb_vect_els_num;
-           vect_index++)
-        if (vect [vect_index] != undefined_vect_el_value
-            && (comb_vect_start [vect_index + comb_vect_index]
-		!= undefined_vect_el_value))
-          break;
-      if (vect_index >= vect_length
-          || vect_index + comb_vect_index >= comb_vect_els_num)
-        break;
+
+  /* Slow case.  */
+  if (vect_length - first_unempty_vect_index >= SIZEOF_LONG * CHAR_BIT)
+    {
+      for (comb_vect_index = 0;
+           comb_vect_index < comb_vect_els_num;
+           comb_vect_index++)
+        {
+          for (vect_index = first_unempty_vect_index;
+               vect_index < vect_length
+               && vect_index + comb_vect_index < comb_vect_els_num;
+               vect_index++)
+            if (vect [vect_index] != undefined_vect_el_value
+                && (comb_vect_start [vect_index + comb_vect_index]
+		    != undefined_vect_el_value))
+              break;
+          if (vect_index >= vect_length
+              || vect_index + comb_vect_index >= comb_vect_els_num)
+            break;
+        }
+      goto found;
+    }
+
+  /* Fast case.  */
+  vect_mask = 0;
+  for (vect_index = first_unempty_vect_index;
+       vect_index < vect_length;
+       vect_index++)
+    {
+      vect_mask = vect_mask << 1;
+      if (vect [vect_index] != undefined_vect_el_value)
+	vect_mask |= 1;
     }
+
+  /* Search for the place in comb vect for the inserted vect.  */
+  comb_vect_index = 0;
+  if (comb_vect_els_num == 0)
+    goto found;
+
+  comb_vect_mask = 0;
+  for (vect_index = first_unempty_vect_index;
+       vect_index < vect_length && vect_index < comb_vect_els_num;
+       vect_index++)
+    {
+      comb_vect_mask <<= 1;
+      if (vect_index + comb_vect_index < comb_vect_els_num
+	  && comb_vect_start [vect_index + comb_vect_index]
+	     != undefined_vect_el_value)
+	comb_vect_mask |= 1;
+    }
+  if ((vect_mask & comb_vect_mask) == 0)
+    goto found;
+
+  for (comb_vect_index = 1, i = vect_length; i < comb_vect_els_num;
+       comb_vect_index++, i++)
+    {
+      comb_vect_mask = (comb_vect_mask << 1) | 1;
+      comb_vect_mask ^= comb_vect_start [i] == undefined_vect_el_value;
+      if ((vect_mask & comb_vect_mask) == 0)
+	goto found;
+    }
+  for ( ; comb_vect_index < comb_vect_els_num; comb_vect_index++)
+    {
+      comb_vect_mask <<= 1;
+      if ((vect_mask & comb_vect_mask) == 0)
+	goto found;
+    }
+
+found:
   /* Slot was found.  */
   additional_els_num = comb_vect_index + real_vect_length - comb_vect_els_num;
   if (additional_els_num < 0)