[RFC] Matrix Flattening optimization
Razya Ladelsky
RAZYA@il.ibm.com
Thu Mar 2 10:42:00 GMT 2006
Hi,
Matrix flattening optimization tries to replace a N-dimernsional
matrix with its equivalent M-dimensional matrix, where M < N.
This first implementation focuses on global matrices defined
dynamically.
When N==1, we actually flatten the whole matrix.
For instance consider a two-dimensional array a [dim1] [dim2].
The code for allocating space for it usually looks like:
a = (int **) malloc(dim1 * sizeof(int *));
for (i=0; i<dim1; i++)
a[i] = (int *) malloc (dim2 * sizeof(int));
If the arrays "a" is found suitable for this optimization,
its allocation is replaced by:
a = (int *) malloc (dim1 * dim2 *sizeof(int));
and all the references to a[i][j] are replaced by a[i * dim2 + j].
The two main phases of the optimization are the analysis
and transformation.
The driver of the optimization is matrix_reorg ().
Analysis phase:
===============
The analysis part of the optimization determines K, the escape
level of a N-dimensional matrix (K <= N), that allows flattening of
the external dimensions 0,1,..., K-1. Escape level 0 means that the
whole matrix escapes and no flattening is possible.
The analysis part is implemented in analyze_matrix_allocation_site()
and analyze_matrix_accesses().
Transformation phase:
=====================
In this phase we define the new flattened matrices that replace the
original matrices in the code.
Implemented in transform_allocation_sites(), transform_access_sites().
For art benchmark matrix flattening shows improvement of 35%, equake
shows 9%
on PowerPC Linux.
The patch was developed on ipa-branch.
The code is relatively stable, and its functionality could be
exemplified by the attached testcases (matrix-1.c, matrix-2.c)
The optimization should be applied with the flags :
-fmatrix-flattening (-fdump-ipa-mreorg) -fwhole-program -combine
Comments will be appreciated,
Thanks
Razya
2006-03-02 Razya Ladelsky <razya@il.ibm.com>
* matrix-reorg.c: New file. Implement matrix flattening
optimization.
* tree-pass.h: Add matrix reorg(flattening) pass.
* common.opt: Add fmatrix-flattening flag.
* Makefile.in: Add matrix-reorg.c.
* passes.c: Add matrix reorg pass.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: diff
Type: application/octet-stream
Size: 2890 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/gcc-patches/attachments/20060302/c071ea22/attachment.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: matrix-1.c
Type: application/octet-stream
Size: 1810 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/gcc-patches/attachments/20060302/c071ea22/attachment-0001.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: matrix-2.c
Type: application/octet-stream
Size: 1933 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/gcc-patches/attachments/20060302/c071ea22/attachment-0002.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: matrix-reorg.c
Type: application/octet-stream
Size: 60362 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/gcc-patches/attachments/20060302/c071ea22/attachment-0003.obj>
More information about the Gcc-patches
mailing list