diff mbox

New automaton_option "collapse-ndfa"

Message ID 4E56CAE7.4010400@codesourcery.com
State New
Headers show

Commit Message

Bernd Schmidt Aug. 25, 2011, 10:21 p.m. UTC 
On 07/18/11 18:47, Vladimir Makarov wrote:
> But I guess comb-vector is popular for a reason.  We could tolerate slow
> compression time because it is done once but worse compression and
> slower access would have a really bad impact on the compiler time.

With some fixes that I need to make to the C6X machine description, comb
vector generation time is no longer tolerable. Ok to apply the following
patch? (Bootstrapped and tested on i686-linux).


Bernd
* genautomata.c (NO_COMB_OPTION): New macro.
	(no_comb_flag): New static variable.
	(gen_automata_option): Handle NO_COMB_OPTION.
	(comb_vect_p): False if no_comb_flag.
	(add_vect): Move computation of min/max values.  Return early if
	no_comb_flag.
	* doc/md.texi (automata_option): Document no-comb-vect.

Comments

Vladimir Makarov Aug. 26, 2011, 2:10 p.m. UTC | #1 
On 08/25/2011 06:21 PM, Bernd Schmidt wrote:
> On 07/18/11 18:47, Vladimir Makarov wrote:
>> But I guess comb-vector is popular for a reason.  We could tolerate slow
>> compression time because it is done once but worse compression and
>> slower access would have a really bad impact on the compiler time.
> With some fixes that I need to make to the C6X machine description, comb
> vector generation time is no longer tolerable. Ok to apply the following
> patch? (Bootstrapped and tested on i686-linux).
>
Ok.  Thanks, Bernd.
diff mbox

Patch

Index: gcc/genautomata.c
===================================================================
--- gcc/genautomata.c	(revision 332057)
+++ gcc/genautomata.c	(working copy)
@@ -252,6 +252,7 @@  static arc_t next_out_arc              (
 #define W_OPTION "-w"
 #define NDFA_OPTION "-ndfa"
 #define COLLAPSE_OPTION "-collapse-ndfa"
+#define NO_COMB_OPTION "-no-comb-vect"
 #define PROGRESS_OPTION "-progress"
 
 /* The following flags are set up by function `initiate_automaton_gen'.  */
@@ -267,6 +268,9 @@  static int collapse_flag;
 /* Do not make minimization of DFA (`-no-minimization').  */
 static int no_minimization_flag;
 
+/* Do not try to generate a comb vector (`-no-comb-vect').  */
+static int no_comb_flag;
+
 /* Value of this variable is number of automata being generated.  The
    actual number of automata may be less this value if there is not
    sufficient number of units.  This value is defined by argument of
@@ -1538,6 +1542,8 @@  gen_automata_option (rtx def)
     ndfa_flag = 1;
   else if (strcmp (XSTR (def, 0), COLLAPSE_OPTION + 1) == 0)
     collapse_flag = 1;
+  else if (strcmp (XSTR (def, 0), NO_COMB_OPTION + 1) == 0)
+    no_comb_flag = 1;
   else if (strcmp (XSTR (def, 0), PROGRESS_OPTION + 1) == 0)
     progress_flag = 1;
   else
@@ -7190,6 +7196,8 @@  static int undefined_vect_el_value;
 static int
 comb_vect_p (state_ainsn_table_t tab)
 {
+  if (no_comb_flag)
+    return false;
   return  (2 * VEC_length (vect_el_t, tab->full_vect)
            > 5 * VEC_length (vect_el_t, tab->comb_vect));
 }
@@ -7308,6 +7316,22 @@  add_vect (state_ainsn_table_t tab, int v
       VEC_replace (vect_el_t, tab->full_vect, full_base + i,
 		   VEC_index (vect_el_t, vect, i));
   }
+
+  /* The comb_vect min/max values are also used for the full vector, so
+     compute them now.  */
+  for (vect_index = 0; vect_index < vect_length; vect_index++)
+    if (VEC_index (vect_el_t, vect, vect_index) != undefined_vect_el_value)
+      {
+	vect_el_t x = VEC_index (vect_el_t, vect, vect_index);
+        gcc_assert (x >= 0);
+        if (tab->max_comb_vect_el_value < x)
+          tab->max_comb_vect_el_value = x;
+        if (tab->min_comb_vect_el_value > x)
+          tab->min_comb_vect_el_value = x;
+      }
+  if (no_comb_flag)
+    return;
+
   /* Form comb vector in the table: */
   gcc_assert (VEC_length (vect_el_t, tab->comb_vect)
 	      == VEC_length (vect_el_t, tab->check_vect));
@@ -7417,10 +7441,6 @@  add_vect (state_ainsn_table_t tab, int v
 			       comb_vect_index + vect_index)
 		    == undefined_vect_el_value);
         gcc_assert (x >= 0);
-        if (tab->max_comb_vect_el_value < x)
-          tab->max_comb_vect_el_value = x;
-        if (tab->min_comb_vect_el_value > x)
-          tab->min_comb_vect_el_value = x;
 	VEC_replace (vect_el_t, tab->comb_vect,
 		     comb_vect_index + vect_index, x);
 	VEC_replace (vect_el_t, tab->check_vect,
Index: gcc/doc/md.texi
===================================================================
--- gcc/doc/md.texi	(revision 332057)
+++ gcc/doc/md.texi	(working copy)
@@ -7795,6 +7795,13 @@  verification and debugging.
 non-critical errors.
 
 @item
+@dfn{no-comb-vect} prevents the automaton generator from generating
+two data structures and comparing them for space efficiency.  Using
+a comb vector to represent transitions may be better, but it can be
+very expensive to construct.  This option is useful if the build
+process spends an unacceptably long time in genautomata.
+
+@item
 @dfn{ndfa} makes nondeterministic finite state automata.  This affects
 the treatment of operator @samp{|} in the regular expressions.  The
 usual treatment of the operator is to try the first alternative and,