struct-reorg optimization

[Olga Golovanevsky]

This patch implements structure peeling, that is one of struct-reorg
optimizations developed on struct-reorg-branch. A structure type can be
peeled into separate fields, or groups of them, according to profile
information, or  deliberately. The gain is to utilize spatial locality,
when, for example, one of the fields is sequentially accessed through
array elements. Then separating this field from others allows to make
separation in array allocation, and thus release cache from irrelevant
data fetched with other fields.

The full description of this optimization is at the beginning of
struct-reorg.c (attached below).

The optimization is global, both types of accesses - through pointers
and  array refs - are handled. When allocation is made through malloc,
it is replaced by allocations of peeled structures. Only build-in malloc
is supported right now, but it can be easily extended.

In this patch, the decision how to peel is made by frequency based model,
where frequency of field accesses can be calculated through profiling or
statically predicted as with -fbranch-probabilitied flag. When there is
no such info, structure gets completely peeled. (The struct-reorg-branch
contains much more accurate model which is based on the calculation of
distance between accesses, but it's also heavier.)
The -fipa-struct-reorg flag activates this optimization.

The patch makes strong use of ipa-type-escape analysis, that provide
safety of this optimization. Also changes required for ipa-type-escape
to support POITER_PLUS_EXPR are part of this patch.

With this patch:
      - two structures f1_neuron and  xyz got peeled in 179. art ,
      +44% w/o profiling and +33% with profiling

      - the structures  NEXT_MOVE got peeled, the structure CHESS_POSITION
      can be peeled, but interfere with another optimization that
      generated BIT_FIELD_REFs in 186.crafty; many other structures escape,
      no influence on performance

      - the structure MMNODE got peeled; many others escape,
      no influence on performance

Bootstraped and tested (except  fortran) on ppc .

:ADDPATCH ipa ssa:

Ok for mainline?

2007-07-09  Olga Golovanevsky  <olga@il.ibm.com>

      * struct-reorg.c, struct-reorg.h: New files.
      * ipa-type-escape.h: Expose function
      is_array_access_through_pointer_and_index.
      * ipa-type-escape.c
      (is_array_access_through_pointer_and_index):
      Add three new parameters. Add support of
      POINTER_PLUS_EXPR code.
      * tree.h: Add pass_ipa_struct_reorg.
      * common.opt: Add ipa-struct-reorg flag.
      * Makefile.in: Add strcut-reorg.o compilation.
      * passes.c: Add pass pass_ipa_struct_reorg.

(See attached file: struct-reorg.txt)(See attached file: struct-reorg.c)
(See attached file: struct-reorg.h)
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: struct-reorg.txt
URL: <http://gcc.gnu.org/pipermail/gcc-patches/attachments/20070710/d6bf120d/attachment.txt>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: struct-reorg.c
Type: application/octet-stream
Size: 84522 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/gcc-patches/attachments/20070710/d6bf120d/attachment.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: struct-reorg.h
Type: application/octet-stream
Size: 3720 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/gcc-patches/attachments/20070710/d6bf120d/attachment-0001.obj>