19-fyi-use-bitset-ops.patch

[Akim Demaille]

Index: ChangeLog
from  Akim Demaille  <address@hidden>
        Use bitset operations when possible, not loops over bits.
        
        * src/conflicts.c (set_conflicts, count_sr_conflicts): Use
        bitset_or.
        * src/print.c (print_reductions): Use bitset_and, bitset_andn.
        * src/reduce.c (useless_nonterminals): Formatting changes.
        * src/warshall.c (TC): Use bitset_or.
        
        
Index: src/conflicts.c
--- src/conflicts.c Fri, 01 Mar 2002 15:32:00 +0100 akim
+++ src/conflicts.c Fri, 01 Mar 2002 15:57:08 +0100 akim
@@ -186,14 +186,13 @@
      for conflicts not resolved above.  */
   for (i = 0; i < state->nlookaheads; ++i)
     {
+      /* FIXME: Here, I need something like `bitset_disjoint_p'. */
       for (j = 0; j < ntokens; ++j)
        if (bitset_test (LA[state->lookaheadsp + i], j)
            && bitset_test (lookaheadset, j))
          conflicts[state->number] = 1;
 
-      for (j = 0; j < ntokens; ++j)
-       if (bitset_test (LA[state->lookaheadsp + i], j))
-         bitset_set (lookaheadset, j);
+      bitset_or (lookaheadset, lookaheadset, LA[state->lookaheadsp + i]);
     }
 }
 
@@ -220,7 +219,7 @@
 static int
 count_sr_conflicts (state_t *state)
 {
-  int i, k;
+  int i;
   int src_count = 0;
   shifts *shiftp = state->shifts;
 
@@ -235,9 +234,7 @@
       bitset_set (shiftset, SHIFT_SYMBOL (shiftp, i));
 
   for (i = 0; i < state->nlookaheads; ++i)
-    for (k = 0; k < ntokens; ++k)
-      if (bitset_test (LA[state->lookaheadsp + i], k))
-       bitset_set (lookaheadset, k);
+    bitset_or (lookaheadset, lookaheadset, LA[state->lookaheadsp + i]);
 
   bitset_and (lookaheadset, lookaheadset, shiftset);
 
Index: src/print.c
--- src/print.c Fri, 01 Mar 2002 15:24:29 +0100 akim
+++ src/print.c Fri, 01 Mar 2002 15:57:05 +0100 akim
@@ -215,12 +215,7 @@
     {
       int default_rule = LAruleno[state->lookaheadsp];
 
-      for (i = 0; i < ntokens; ++i)
-       if (bitset_test (LA[state->lookaheadsp], i)
-           && bitset_test (shiftset, i))
-         bitset_set (lookaheadset, i);
-       else
-         bitset_reset (lookaheadset, i);
+      bitset_and (lookaheadset, LA[state->lookaheadsp], shiftset);
 
       for (i = 0; i < ntokens; i++)
        if (bitset_test (lookaheadset, i))
@@ -241,14 +236,9 @@
        for (i = 0; i < state->nlookaheads; ++i)
          {
            int count = 0;
-           int j, k;
+           int j;
 
-           for (k = 0; k < ntokens; ++k)
-             if (bitset_test (LA[state->lookaheadsp + i], k)
-                 && ! bitset_test (shiftset, k))
-               bitset_set (lookaheadset, k);
-             else
-               bitset_reset (lookaheadset, k);
+           bitset_andn (lookaheadset, LA[state->lookaheadsp + i], shiftset);
 
            for (j = 0; j < ntokens; j++)
              if (bitset_test (lookaheadset, j))
@@ -277,39 +267,37 @@
          int count = bitset_test (shiftset, i);
 
          for (j = 0; j < state->nlookaheads; ++j)
-           {
-             if (bitset_test (LA[state->lookaheadsp + j], i))
-               {
-                 if (count == 0)
-                   {
-                     if (state->lookaheadsp + j != default_LA)
-                       fprintf (out,
-                                _("    %-4s\treduce using rule %d (%s)\n"),
-                                escape (symbols[i]->tag),
-                                LAruleno[state->lookaheadsp + j] - 1,
-                                escape2 
(symbols[rules[LAruleno[state->lookaheadsp + j]].lhs]->tag));
-                     else
-                       defaulted = 1;
-
-                     count++;
-                   }
-                 else
-                   {
-                     if (defaulted)
-                       fprintf (out,
-                                _("    %-4s\treduce using rule %d (%s)\n"),
-                                escape (symbols[i]->tag),
-                                LAruleno[default_LA] - 1,
-                                escape2 
(symbols[rules[LAruleno[default_LA]].lhs]->tag));
-                     defaulted = 0;
+           if (bitset_test (LA[state->lookaheadsp + j], i))
+             {
+               if (count == 0)
+                 {
+                   if (state->lookaheadsp + j != default_LA)
                      fprintf (out,
-                              _("    %-4s\t[reduce using rule %d (%s)]\n"),
+                              _("    %-4s\treduce using rule %d (%s)\n"),
                               escape (symbols[i]->tag),
                               LAruleno[state->lookaheadsp + j] - 1,
                               escape2 
(symbols[rules[LAruleno[state->lookaheadsp + j]].lhs]->tag));
-                   }
-               }
-           }
+                   else
+                     defaulted = 1;
+
+                   count++;
+                 }
+               else
+                 {
+                   if (defaulted)
+                     fprintf (out,
+                              _("    %-4s\treduce using rule %d (%s)\n"),
+                              escape (symbols[i]->tag),
+                              LAruleno[default_LA] - 1,
+                              escape2 
(symbols[rules[LAruleno[default_LA]].lhs]->tag));
+                   defaulted = 0;
+                   fprintf (out,
+                            _("    %-4s\t[reduce using rule %d (%s)]\n"),
+                            escape (symbols[i]->tag),
+                            LAruleno[state->lookaheadsp + j] - 1,
+                            escape2 (symbols[rules[LAruleno[state->lookaheadsp 
+ j]].lhs]->tag));
+                 }
+             }
        }
 
       if (default_LA >= 0)
Index: src/reduce.c
--- src/reduce.c Tue, 26 Feb 2002 23:12:54 +0100 akim
+++ src/reduce.c Fri, 01 Mar 2002 15:52:10 +0100 akim
@@ -126,16 +126,12 @@
     {
       bitset_copy (Np, N);
       for (i = 1; i <= nrules; i++)
-       {
-         if (!bitset_test (P, i))
-           {
-             if (useful_production (i, N))
-               {
-                 bitset_set (Np, rules[i].lhs - ntokens);
-                 bitset_set (P, i);
-               }
-           }
-       }
+       if (!bitset_test (P, i)
+           && useful_production (i, N))
+         {
+           bitset_set (Np, rules[i].lhs - ntokens);
+           bitset_set (P, i);
+         }
       if (bitset_equal_p (N, Np))
        break;
       Ns = Np;
Index: src/warshall.c
--- src/warshall.c Fri, 01 Mar 2002 14:02:26 +0100 akim
+++ src/warshall.c Fri, 01 Mar 2002 15:54:02 +0100 akim
@@ -79,7 +79,7 @@
 static void
 TC (bitset *matrix, int n)
 {
-  int i, j, k;
+  int i, j;
 
   if (trace_flag)
     bitmatrix_print ("TC: Input", matrix, n);
@@ -90,9 +90,7 @@
   for (i = 0; i < n; ++i)
     for (j = 0; j < n; ++j)
       if (bitset_test (matrix[j], i))
-       for (k = 0; k < n; ++k)
-         if (bitset_test (matrix[i], k))
-           bitset_set (matrix[j], k);
+       bitset_or (matrix[j], matrix[j], matrix[i]);
 
   if (trace_flag)
     bitmatrix_print ("TC: Output", matrix, n);