Re: [GSoC] decision tree first steps

[ludo at gnu dot org (Ludovic CourtÃs)]

Hi,

Prathamesh Kulkarni <bilbotheelffriend@gmail.com> skribis:

> Example:
> /* x & 0 -> 0 */
> (match_and_simplify
>   (bit_and @0 @1)
>   if (INTEGRAL_TYPE_P (TREE_TYPE (@0)) && (@1 == integer_zero_node))
>   { integer_zero_node; })
>
> /* x & -1 -> x */
> (match_and_simplify
>   (bit_and @0 @1)
>   if (INTEGRAL_TYPE_P (TREE_TYPE (@0))
>      && (@1 == integer_minus_one_node)
>   @0)

(Apologies if this has already been discussed/decided before.)

With my Scheme background, two things come to mind:

  1. Wouldnât it be nicer to have a single language, rather than
     intermingle C expressions in the middle of the s-expression
     language?

  2. Wouldnât it be useful to allow multiple clauses in a single
     âmatchâ?

Hereâs a hypothetical simplification pass one could write:

  ;; Match tree node âexpâ against a series of patterns, and return
  ;; a (possibly identical) tree node.
  (match exp
    ((bitwise-and first second)
     (if (and (integral-type? (tree-type first))
              (eq? integer-zero-node second))
         integer-zero-node    ; simplify to zero
         exp))                ; return âexpâ unchanged
    ((bitwise-and first second)
     (if (and (integral-type? (tree-type first))
              (eq? integer-minus-one-node second))
         first
         exp))
    (else                     ; no simplification pattern matched
     exp))

The language for expression rewriting (the âifâ expressions above) could
consist of very few constructs directly translatable to C + tree.

As an example, Guileâs compiler simplification passes look very much
like this [0], built around a generic pattern matcher [1].  Pattern
matching in MELT should also be a good source of inspiration, obviously [2].

Thanks,
Ludoâ.

[0] http://git.savannah.gnu.org/cgit/guile.git/tree/module/language/tree-il/peval.scm#n1082
[1] http://www.gnu.org/software/guile/manual/html_node/Pattern-Matching.html
[2] http://gcc-melt.org/tutomeltimplem.html