[RFC] Matrix Flattening optimization

[Razya Ladelsky <RAZYA at il dot ibm dot com>]

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.

Attachment: diff
Description: Binary data

Attachment: matrix-1.c
Description: Binary data

Attachment: matrix-2.c
Description: Binary data

Attachment: matrix-reorg.c
Description: Binary data