From 00ca8311cfa7841f9d492b84a995dbc2b06cc368 Mon Sep 17 00:00:00 2001 From: Segher Boessenkool Date: Fri, 16 Jul 2004 10:12:11 +0200 Subject: [PATCH] genautomata.c (add_vect): Speedup by using integers as bit-vectors for walking through the comb_vect and... * genautomata.c (add_vect): Speedup by using integers as bit-vectors for walking through the comb_vect and finding a match. From-SVN: r84811 --- gcc/ChangeLog | 6 ++++ gcc/genautomata.c | 85 ++++++++++++++++++++++++++++++++++++++--------- 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 + + * 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 * 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) -- 2.30.2