Re: PATCH: Loop to builtin call pass (builtinizer)

[Dorit Nuzman <DORIT at il dot ibm dot com>]

> Hi,
>
> I am sending patch that adding pass that converts some loop
> constructions to calling builtin call.
>
> Problem description:
>
> In many programs are some loop constructions with special statement
patterns
> that could be transformed into a built-in function call and an expander
> infrastructure in GCC chooses the best possible implementation of this
> function. This is a way how a compiler could possibly take the best
> implementation of the program constructions for a specific platform and
thus a
> runtime performance can be improved.
>
> Problem solution:
>
> Builtinizer applies a set of analysis on each loop, followed by the
built-in
> call transformation for the loops that had successfully passed the
analysis
> phase.
>
> builtinizer analysis:
>
> * Probe the loop exit condition and bb structure
> * Loop bound analysis (by scev)
> * Finds all memory references in the loop and checks if an access
> function that
>   describes their modification in the loop can be constructed
> * Do memory dependence test (by data dependence analysis)
> * Scan all statements in the loop and determines if they match pattern
rules
>   for transformation to builtin call. Info about marked pattern
> chains is saved
>   into stmt_vec_info (fields 'relevant' and 'related_stmt')
> * Analyze data ref access functions and determine if they iterate over
all
>   iterations of loop
>

Hi Tomas,

I think this is a good transformation to have.

It's very evident, however, that there's *a lot* of duplication with the
vectorizer, both in code, in the data structures that are used, and also in
recomputing a lot of the same things (almost all the passes you describe
above are also done in the vectorizer). I think there's room to consider to
reuse the vectorizer pass, and just add the memset and memcopy patterns as
yet another two patterns that will be detected during the
pattern-recognition pass that the vectorizer already does (you already
implemented it almost exactly like the vectorizer's pattern recognition so
it should be easy to plug it into the vectorizer's pattern recognition
engine). There are of-course some differences that would need to be
handled, but I think it would be worth while to put some thought into how
these could be integrated into the vectorizer to avoid having to run a
whole separate pass for a lot of the same analyses. I could help with
looking into how to revise the patch to incorporate it into the vectorizer.

dorit

> Current supported patterns:
> * x[][][]...[i] = 0; -> memset (x[][][]..., 0, n)
> * tmp = y [][][]...[i]; x[][][]...[i] = tmp; -> memcpy (x[][][]...,
> y[][][]...., n)
>
> builtinizer transformation:
>
> The loop transformation phase scans all accepted statements from the
analysis
> phase and these statements grouped to patterns. The statement groups
> remove from
> the loop and insert relevant built-in call statement before the loop.
>
>
> Bootsraped and regtested on i686-linux x86_64-linux.
>
> OK?
>
> Changelog:
>
> 2007-06-29  Tomas Bily  <tbily@suse.cz>
>
>    * tree-pass.h: added pass_builtinize
>    * tree-ssa-loop-builtin.c: new file
>    * tree-vectorizer.h: added declaration of vect_get_loop_niters
>    * tree-vect-analyze.c: changed declaration of
>    vect_get_loop_niters from static to non-static
>    * common.opt: added -ftree-loop-buitlinize switch
>    * tree-flow.h: added declaration of builtinize_loops
>    * Makefile.in: added rule for tree-ssa-loop-builtinize.o
>    * passes.c(init_optimization_passes): added pass_builtinize
>    and pass_may_alias after
>
>  Greetings
>
>  Tomas
> [attachment "builtin.patch" deleted by Dorit Nuzman/Haifa/IBM]
> [attachment "bltn.c" deleted by Dorit Nuzman/Haifa/IBM]