Re: Speedup genautomata.c

["Vladimir N. Makarov" <vmakarov at redhat dot com>]

Michael Matz wrote:

> Hi,
>
> The patch below implements the above.  It was bootstrapped and regtested 
> on i686,x86_64,ppc,ppc64,s390,s390x,ia64 .  Furthermore I built 
> cross-compilers on
>  alpha, arm, hppa, i386, ia64, mips, ppc, s390, sh, sparc, x86_64
> to look at the automatas actually built, and see for changes in compiling 
> a big code test, and the kdecore library (with -O2).  No changes in 
> assembler occured.  Also the automates itself didn't change when the 
> sorting step is not done.  When that is active only the automates for ia64 
> (slightly) and for ppc (a bit more) changed at all.
>
>  
Sorry for the delay with the approval.  I needed time to investigate why 
the automata were different.  It was just order of the arcs.

> Okay for trunk?
>  
Yes, it is ok.  Thank you for the patch.  It is really a big speed up!

> Ciao,
> Michael.
>
> 	* genautomata.c (<struct state>, num_out_arcs, presence_signature):
> 	New members.
> 	(remove_arc, add_arc): Update num_out_arcs member.
> 	(set_out_arc_insns_equiv_num): Returns instead of number of out arcs.
> 	(cache_presence): New function.
> 	(compare_states_for_equiv): New function.
> 	(state_is_differed): Don't take number of outargs, adjust callers.
> 	Use new invariant for speeding up.
> 	(init_equiv_class): Create initial classes based on sorted
> 	input.
> 	(partition_equiv_class): Don't track out_arcs_num.
> 	(evaluate_equiv_classes): Call cache_presence on all states and
> 	sort them.
>
>