From f9abaa2c4c5c77c5b6bdcfc0149c0af5adc8cc39 Mon Sep 17 00:00:00 2001 From: Akim Demaille Date: Mon, 4 Mar 2002 12:05:30 +0000 Subject: [PATCH] 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. --- ChangeLog | 11 ++++++++ src/conflicts.c | 11 +++----- src/print.c | 72 +++++++++++++++++++++---------------------------- src/reduce.c | 16 +++++------ src/warshall.c | 6 ++--- 5 files changed, 53 insertions(+), 63 deletions(-) diff --git a/ChangeLog b/ChangeLog index 90c60875..c816b007 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,14 @@ +2002-03-04 Akim Demaille + + 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. + + 2002-03-04 Akim Demaille * src/lalr.h, src/lalr.c (tokensetsize): Remove, unused. diff --git a/src/conflicts.c b/src/conflicts.c index 6d9562bc..e08256a1 100644 --- a/src/conflicts.c +++ b/src/conflicts.c @@ -186,14 +186,13 @@ set_conflicts (state_t *state) 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 @@ solve_conflicts (void) 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 @@ count_sr_conflicts (state_t *state) 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); diff --git a/src/print.c b/src/print.c index 17823f8e..6dd25096 100644 --- a/src/print.c +++ b/src/print.c @@ -215,12 +215,7 @@ print_reductions (FILE *out, state_t *state) { 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 @@ print_reductions (FILE *out, state_t *state) 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 @@ print_reductions (FILE *out, state_t *state) 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) diff --git a/src/reduce.c b/src/reduce.c index 05d15d23..973e5ede 100644 --- a/src/reduce.c +++ b/src/reduce.c @@ -126,16 +126,12 @@ useless_nonterminals (void) { 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; diff --git a/src/warshall.c b/src/warshall.c index ff41d5ba..c962bc7f 100644 --- a/src/warshall.c +++ b/src/warshall.c @@ -79,7 +79,7 @@ bitmatrix_print (const char *title, bitset *matrix, size_t size) 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 @@ TC (bitset *matrix, int n) 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); -- 2.45.2