gcc newbie and open projects

gcc newbie and open projects

[Brian Makin]

Hello all!

I would very much like to contribute to the gcc
project and as such have been monitoring the gcc list
and perusing the documentation.

One project in particular looks interesting.

Make insn-recog.c use a byte-coded DFA.

Richard Henderson and I started this back in 1999 but
never finished. I may still be able to find the code.
It produces an order of magnitude size reduction in
insn-recog.o, which is huge (432KB on i386).


Is this still an open project?  and if so can anyone
give me more information on what is needed?


I am an experienced c/c++ programmer but will
obviously need to come up to speed on the gcc compiler
internals.

If anyone is feeling generous please let me know of
projects which I could start with.

hope to be talking with you all alot more,

regards,
Brian N. Makin


__________________________________________________
Do You Yahoo!?
Tired of spam?  Yahoo! Mail has the best spam protection around 
http://mail.yahoo.com 

Re: gcc newbie and open projects

[Paolo Bonzini]

> Is this still an open project?  and if so can anyone
> give me more information on what is needed?

Yes, it is.

Basically, insn-recog.c is a huge decision tree.  genrecog.c builds it 
and outputs it as C code.  It uses variables like "x0, x1, x2, ..., xn" 
which would become the virtual machine's registers.  It should be 
possible to linearize into something like bytecodes (more likely an 
array of structs).

Some of the bytecodes are already visible from the "decision_type" enum 
in genrecog.c:

       DT_mode, DT_code, DT_veclen,
       DT_elt_zero_int, DT_elt_one_int, DT_elt_zero_wide,
       DT_elt_zero_wide_safe,
       DT_const_int,
       DT_veclen_ge, DT_dup, DT_pred, DT_c_test,
       DT_accept_op, DT_accept_insn

To these, you should add some for control flow.  In the end you may have 
something like

- one bytecode for each of DT_mode ... DT_dup
- if ... goto ...
- switch (maybe more than one bytecode, see later)
- xK = PATTERN (peep2_next_insn (N))
- if peep2_next_insn (N) == NULL_RTX goto ... else same as above
- xK = XVECEXP (xJ, 0, N)
- xK = XEXP (xJ, N)
- operands[K] = N (this is DT_accept_op
- at least three bytecodes for DT_accept_insn, depending on 
subroutine_type (see write_action in genrecog.c)
- one bytecode per predicate (not sure about this)

The moderately complex part of it should be:
- the switch statements, where it is mostly a matter of efficiently 
encoding them.  Most of them have a handful of cases, but few have 20 or so.

- the labels, where genrecog can already associate each decision tree 
node with a C label.  I guess you can do two compilation passes, one to 
linearize the tree, and one to put in the "virtual program counter" 
values and actually output the bytecoded description.

- DT_c_test: these are embedded C predicates.  You can also have one 
bytecode per test there.  Anyway, you're already going to write at least 
"part" of the virtual machine interpreter in your rewritten genrecog, if 
you have one bytecode per predicate.  Luckily, if the host compiler is 
3.0.1 or later, insn-conditions.c has most of the work already done! 
gensupport.c has this code

   int
   maybe_eval_c_test (const char *expr)
   {
     const struct c_test *test;
     struct c_test dummy;

     if (expr[0] == 0)
       return 1;

     if (insn_elision_unavailable)
       return -1;

     dummy.expr = expr;
     test = (const struct c_test *)htab_find (condition_table, &dummy);
     gcc_assert (test);

     return test->value;
   }

which gives this function

   int
   c_test_id (const char *expr)
   {
     const struct c_test *test;
     struct c_test dummy;

     if (expr[0] == 0)
       return -1;

     dummy.expr = expr;
     test = (const struct c_test *)htab_find (condition_table, &dummy);
     gcc_assert (test);
     return test - insn_conditions;
   }

With a GCC earlier than 3.0.1, dummy-conditions.c is used instead, but 
you can ditch this.  You'll have to modify write_one_condition in 
genconditions.c, so that instead of

    { "! optimize_size && ! TARGET_READ_MODIFY",
      __builtin_constant_p (! optimize_size && ! TARGET_READ_MODIFY)
      ? (int) (! optimize_size && ! TARGET_READ_MODIFY)
      : -1) },

it outputs something like

    { "! optimize_size && ! TARGET_READ_MODIFY",
#if GCC_VERSION < 3001
      __builtin_constant_p (! optimize_size && ! TARGET_READ_MODIFY)
      ? (int) (! optimize_size && ! TARGET_READ_MODIFY) :
#endif
      -1) },

Similarly in write_conditions, instead of

    const int insn_elision_unavailable = 0;

you can output

#if GCC_VERSION < 3001
    const int insn_elision_unavailable = 1;
#else
    const int insn_elision_unavailable = 0;
#endif

I guess the only complicated part is really the switch statements.

Paolo