PATCH: Loop to builtin call pass (builtinizer)

[Tomas Bily <tbily at suse dot cz>]

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

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
Description: Text document

/* { dg-do compile } */
/* { dg-options "-O2 -ftree-loop-builtinize -fdump-tree-builtinize-details" } */

int a [200];
int b [200];
int c [100][200];

int
main (int argc, char** argv)
{
    int* p = a + 16;
    int i;
    
    for (i = 0; i < 10; i ++)
    {
	a [i] = c [0] [i];
	a [i + 100] = 0;
    }
    
    for (i = 0; i < 10; i ++, p ++)
    {
	c [0] [i] = 0;
    }
    
    return 0;
}

/* { dg-final { scan-tree-dump "builtinized 2 loops" "builtinize" } } */                                                                             
/* { dg-final { cleanup-tree-dump "builtinize" } } */