/* Matrix layout transformations.
|
/* Matrix layout transformations.
|
Copyright (C) 2006, 2007, 2008, 2009, 2010 Free Software Foundation, Inc.
|
Copyright (C) 2006, 2007, 2008, 2009, 2010 Free Software Foundation, Inc.
|
Contributed by Razya Ladelsky <razya@il.ibm.com>
|
Contributed by Razya Ladelsky <razya@il.ibm.com>
|
Originally written by Revital Eres and Mustafa Hagog.
|
Originally written by Revital Eres and Mustafa Hagog.
|
|
|
This file is part of GCC.
|
This file is part of GCC.
|
|
|
GCC is free software; you can redistribute it and/or modify it under
|
GCC is free software; you can redistribute it and/or modify it under
|
the terms of the GNU General Public License as published by the Free
|
the terms of the GNU General Public License as published by the Free
|
Software Foundation; either version 3, or (at your option) any later
|
Software Foundation; either version 3, or (at your option) any later
|
version.
|
version.
|
|
|
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
|
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
|
WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
for more details.
|
for more details.
|
|
|
You should have received a copy of the GNU General Public License
|
You should have received a copy of the GNU General Public License
|
along with GCC; see the file COPYING3. If not see
|
along with GCC; see the file COPYING3. If not see
|
<http://www.gnu.org/licenses/>. */
|
<http://www.gnu.org/licenses/>. */
|
|
|
/*
|
/*
|
Matrix flattening optimization tries to replace a N-dimensional
|
Matrix flattening optimization tries to replace a N-dimensional
|
matrix with its equivalent M-dimensional matrix, where M < N.
|
matrix with its equivalent M-dimensional matrix, where M < N.
|
This first implementation focuses on global matrices defined dynamically.
|
This first implementation focuses on global matrices defined dynamically.
|
|
|
When N==1, we actually flatten the whole matrix.
|
When N==1, we actually flatten the whole matrix.
|
For instance consider a two-dimensional array a [dim1] [dim2].
|
For instance consider a two-dimensional array a [dim1] [dim2].
|
The code for allocating space for it usually looks like:
|
The code for allocating space for it usually looks like:
|
|
|
a = (int **) malloc(dim1 * sizeof(int *));
|
a = (int **) malloc(dim1 * sizeof(int *));
|
for (i=0; i<dim1; i++)
|
for (i=0; i<dim1; i++)
|
a[i] = (int *) malloc (dim2 * sizeof(int));
|
a[i] = (int *) malloc (dim2 * sizeof(int));
|
|
|
If the array "a" is found suitable for this optimization,
|
If the array "a" is found suitable for this optimization,
|
its allocation is replaced by:
|
its allocation is replaced by:
|
|
|
a = (int *) malloc (dim1 * dim2 *sizeof(int));
|
a = (int *) malloc (dim1 * dim2 *sizeof(int));
|
|
|
and all the references to a[i][j] are replaced by a[i * dim2 + j].
|
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
|
The two main phases of the optimization are the analysis
|
and transformation.
|
and transformation.
|
The driver of the optimization is matrix_reorg ().
|
The driver of the optimization is matrix_reorg ().
|
|
|
|
|
|
|
Analysis phase:
|
Analysis phase:
|
===============
|
===============
|
|
|
We'll number the dimensions outside-in, meaning the most external
|
We'll number the dimensions outside-in, meaning the most external
|
is 0, then 1, and so on.
|
is 0, then 1, and so on.
|
The analysis part of the optimization determines K, the escape
|
The analysis part of the optimization determines K, the escape
|
level of a N-dimensional matrix (K <= N), that allows flattening of
|
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
|
the external dimensions 0,1,..., K-1. Escape level 0 means that the
|
whole matrix escapes and no flattening is possible.
|
whole matrix escapes and no flattening is possible.
|
|
|
The analysis part is implemented in analyze_matrix_allocation_site()
|
The analysis part is implemented in analyze_matrix_allocation_site()
|
and analyze_matrix_accesses().
|
and analyze_matrix_accesses().
|
|
|
Transformation phase:
|
Transformation phase:
|
=====================
|
=====================
|
In this phase we define the new flattened matrices that replace the
|
In this phase we define the new flattened matrices that replace the
|
original matrices in the code.
|
original matrices in the code.
|
Implemented in transform_allocation_sites(),
|
Implemented in transform_allocation_sites(),
|
transform_access_sites().
|
transform_access_sites().
|
|
|
Matrix Transposing
|
Matrix Transposing
|
==================
|
==================
|
The idea of Matrix Transposing is organizing the matrix in a different
|
The idea of Matrix Transposing is organizing the matrix in a different
|
layout such that the dimensions are reordered.
|
layout such that the dimensions are reordered.
|
This could produce better cache behavior in some cases.
|
This could produce better cache behavior in some cases.
|
|
|
For example, lets look at the matrix accesses in the following loop:
|
For example, lets look at the matrix accesses in the following loop:
|
|
|
for (i=0; i<N; i++)
|
for (i=0; i<N; i++)
|
for (j=0; j<M; j++)
|
for (j=0; j<M; j++)
|
access to a[i][j]
|
access to a[i][j]
|
|
|
This loop can produce good cache behavior because the elements of
|
This loop can produce good cache behavior because the elements of
|
the inner dimension are accessed sequentially.
|
the inner dimension are accessed sequentially.
|
|
|
However, if the accesses of the matrix were of the following form:
|
However, if the accesses of the matrix were of the following form:
|
|
|
for (i=0; i<N; i++)
|
for (i=0; i<N; i++)
|
for (j=0; j<M; j++)
|
for (j=0; j<M; j++)
|
access to a[j][i]
|
access to a[j][i]
|
|
|
In this loop we iterate the columns and not the rows.
|
In this loop we iterate the columns and not the rows.
|
Therefore, replacing the rows and columns
|
Therefore, replacing the rows and columns
|
would have had an organization with better (cache) locality.
|
would have had an organization with better (cache) locality.
|
Replacing the dimensions of the matrix is called matrix transposing.
|
Replacing the dimensions of the matrix is called matrix transposing.
|
|
|
This example, of course, could be enhanced to multiple dimensions matrices
|
This example, of course, could be enhanced to multiple dimensions matrices
|
as well.
|
as well.
|
|
|
Since a program could include all kind of accesses, there is a decision
|
Since a program could include all kind of accesses, there is a decision
|
mechanism, implemented in analyze_transpose(), which implements a
|
mechanism, implemented in analyze_transpose(), which implements a
|
heuristic that tries to determine whether to transpose the matrix or not,
|
heuristic that tries to determine whether to transpose the matrix or not,
|
according to the form of the more dominant accesses.
|
according to the form of the more dominant accesses.
|
This decision is transferred to the flattening mechanism, and whether
|
This decision is transferred to the flattening mechanism, and whether
|
the matrix was transposed or not, the matrix is flattened (if possible).
|
the matrix was transposed or not, the matrix is flattened (if possible).
|
|
|
This decision making is based on profiling information and loop information.
|
This decision making is based on profiling information and loop information.
|
If profiling information is available, decision making mechanism will be
|
If profiling information is available, decision making mechanism will be
|
operated, otherwise the matrix will only be flattened (if possible).
|
operated, otherwise the matrix will only be flattened (if possible).
|
|
|
Both optimizations are described in the paper "Matrix flattening and
|
Both optimizations are described in the paper "Matrix flattening and
|
transposing in GCC" which was presented in GCC summit 2006.
|
transposing in GCC" which was presented in GCC summit 2006.
|
http://www.gccsummit.org/2006/2006-GCC-Summit-Proceedings.pdf. */
|
http://www.gccsummit.org/2006/2006-GCC-Summit-Proceedings.pdf. */
|
|
|
#include "config.h"
|
#include "config.h"
|
#include "system.h"
|
#include "system.h"
|
#include "coretypes.h"
|
#include "coretypes.h"
|
#include "tm.h"
|
#include "tm.h"
|
#include "tree.h"
|
#include "tree.h"
|
#include "rtl.h"
|
#include "rtl.h"
|
#include "tree-inline.h"
|
#include "tree-inline.h"
|
#include "tree-flow.h"
|
#include "tree-flow.h"
|
#include "tree-flow-inline.h"
|
#include "tree-flow-inline.h"
|
#include "langhooks.h"
|
#include "langhooks.h"
|
#include "hashtab.h"
|
#include "hashtab.h"
|
#include "flags.h"
|
#include "flags.h"
|
#include "ggc.h"
|
#include "ggc.h"
|
#include "debug.h"
|
#include "debug.h"
|
#include "target.h"
|
#include "target.h"
|
#include "cgraph.h"
|
#include "cgraph.h"
|
#include "diagnostic-core.h"
|
#include "diagnostic-core.h"
|
#include "timevar.h"
|
#include "timevar.h"
|
#include "params.h"
|
#include "params.h"
|
#include "fibheap.h"
|
#include "fibheap.h"
|
#include "intl.h"
|
#include "intl.h"
|
#include "function.h"
|
#include "function.h"
|
#include "basic-block.h"
|
#include "basic-block.h"
|
#include "cfgloop.h"
|
#include "cfgloop.h"
|
#include "tree-iterator.h"
|
#include "tree-iterator.h"
|
#include "tree-pass.h"
|
#include "tree-pass.h"
|
#include "opts.h"
|
#include "opts.h"
|
#include "tree-data-ref.h"
|
#include "tree-data-ref.h"
|
#include "tree-chrec.h"
|
#include "tree-chrec.h"
|
#include "tree-scalar-evolution.h"
|
#include "tree-scalar-evolution.h"
|
#include "tree-ssa-sccvn.h"
|
#include "tree-ssa-sccvn.h"
|
|
|
/* We need to collect a lot of data from the original malloc,
|
/* We need to collect a lot of data from the original malloc,
|
particularly as the gimplifier has converted:
|
particularly as the gimplifier has converted:
|
|
|
orig_var = (struct_type *) malloc (x * sizeof (struct_type *));
|
orig_var = (struct_type *) malloc (x * sizeof (struct_type *));
|
|
|
into
|
into
|
|
|
T3 = <constant> ; ** <constant> is amount to malloc; precomputed **
|
T3 = <constant> ; ** <constant> is amount to malloc; precomputed **
|
T4 = malloc (T3);
|
T4 = malloc (T3);
|
T5 = (struct_type *) T4;
|
T5 = (struct_type *) T4;
|
orig_var = T5;
|
orig_var = T5;
|
|
|
The following struct fields allow us to collect all the necessary data from
|
The following struct fields allow us to collect all the necessary data from
|
the gimplified program. The comments in the struct below are all based
|
the gimplified program. The comments in the struct below are all based
|
on the gimple example above. */
|
on the gimple example above. */
|
|
|
struct malloc_call_data
|
struct malloc_call_data
|
{
|
{
|
gimple call_stmt; /* Tree for "T4 = malloc (T3);" */
|
gimple call_stmt; /* Tree for "T4 = malloc (T3);" */
|
tree size_var; /* Var decl for T3. */
|
tree size_var; /* Var decl for T3. */
|
tree malloc_size; /* Tree for "<constant>", the rhs assigned to T3. */
|
tree malloc_size; /* Tree for "<constant>", the rhs assigned to T3. */
|
};
|
};
|
|
|
static tree can_calculate_expr_before_stmt (tree, sbitmap);
|
static tree can_calculate_expr_before_stmt (tree, sbitmap);
|
static tree can_calculate_stmt_before_stmt (gimple, sbitmap);
|
static tree can_calculate_stmt_before_stmt (gimple, sbitmap);
|
|
|
/* The front end of the compiler, when parsing statements of the form:
|
/* The front end of the compiler, when parsing statements of the form:
|
|
|
var = (type_cast) malloc (sizeof (type));
|
var = (type_cast) malloc (sizeof (type));
|
|
|
always converts this single statement into the following statements
|
always converts this single statement into the following statements
|
(GIMPLE form):
|
(GIMPLE form):
|
|
|
T.1 = sizeof (type);
|
T.1 = sizeof (type);
|
T.2 = malloc (T.1);
|
T.2 = malloc (T.1);
|
T.3 = (type_cast) T.2;
|
T.3 = (type_cast) T.2;
|
var = T.3;
|
var = T.3;
|
|
|
Since we need to create new malloc statements and modify the original
|
Since we need to create new malloc statements and modify the original
|
statements somewhat, we need to find all four of the above statements.
|
statements somewhat, we need to find all four of the above statements.
|
Currently record_call_1 (called for building cgraph edges) finds and
|
Currently record_call_1 (called for building cgraph edges) finds and
|
records the statements containing the actual call to malloc, but we
|
records the statements containing the actual call to malloc, but we
|
need to find the rest of the variables/statements on our own. That
|
need to find the rest of the variables/statements on our own. That
|
is what the following function does. */
|
is what the following function does. */
|
static void
|
static void
|
collect_data_for_malloc_call (gimple stmt, struct malloc_call_data *m_data)
|
collect_data_for_malloc_call (gimple stmt, struct malloc_call_data *m_data)
|
{
|
{
|
tree size_var = NULL;
|
tree size_var = NULL;
|
tree malloc_fn_decl;
|
tree malloc_fn_decl;
|
tree arg1;
|
tree arg1;
|
|
|
gcc_assert (is_gimple_call (stmt));
|
gcc_assert (is_gimple_call (stmt));
|
|
|
malloc_fn_decl = gimple_call_fndecl (stmt);
|
malloc_fn_decl = gimple_call_fndecl (stmt);
|
if (malloc_fn_decl == NULL
|
if (malloc_fn_decl == NULL
|
|| DECL_FUNCTION_CODE (malloc_fn_decl) != BUILT_IN_MALLOC)
|
|| DECL_FUNCTION_CODE (malloc_fn_decl) != BUILT_IN_MALLOC)
|
return;
|
return;
|
|
|
arg1 = gimple_call_arg (stmt, 0);
|
arg1 = gimple_call_arg (stmt, 0);
|
size_var = arg1;
|
size_var = arg1;
|
|
|
m_data->call_stmt = stmt;
|
m_data->call_stmt = stmt;
|
m_data->size_var = size_var;
|
m_data->size_var = size_var;
|
if (TREE_CODE (size_var) != VAR_DECL)
|
if (TREE_CODE (size_var) != VAR_DECL)
|
m_data->malloc_size = size_var;
|
m_data->malloc_size = size_var;
|
else
|
else
|
m_data->malloc_size = NULL_TREE;
|
m_data->malloc_size = NULL_TREE;
|
}
|
}
|
|
|
/* Information about matrix access site.
|
/* Information about matrix access site.
|
For example: if an access site of matrix arr is arr[i][j]
|
For example: if an access site of matrix arr is arr[i][j]
|
the ACCESS_SITE_INFO structure will have the address
|
the ACCESS_SITE_INFO structure will have the address
|
of arr as its stmt. The INDEX_INFO will hold information about the
|
of arr as its stmt. The INDEX_INFO will hold information about the
|
initial address and index of each dimension. */
|
initial address and index of each dimension. */
|
struct access_site_info
|
struct access_site_info
|
{
|
{
|
/* The statement (MEM_REF or POINTER_PLUS_EXPR). */
|
/* The statement (MEM_REF or POINTER_PLUS_EXPR). */
|
gimple stmt;
|
gimple stmt;
|
|
|
/* In case of POINTER_PLUS_EXPR, what is the offset. */
|
/* In case of POINTER_PLUS_EXPR, what is the offset. */
|
tree offset;
|
tree offset;
|
|
|
/* The index which created the offset. */
|
/* The index which created the offset. */
|
tree index;
|
tree index;
|
|
|
/* The indirection level of this statement. */
|
/* The indirection level of this statement. */
|
int level;
|
int level;
|
|
|
/* TRUE for allocation site FALSE for access site. */
|
/* TRUE for allocation site FALSE for access site. */
|
bool is_alloc;
|
bool is_alloc;
|
|
|
/* The function containing the access site. */
|
/* The function containing the access site. */
|
tree function_decl;
|
tree function_decl;
|
|
|
/* This access is iterated in the inner most loop */
|
/* This access is iterated in the inner most loop */
|
bool iterated_by_inner_most_loop_p;
|
bool iterated_by_inner_most_loop_p;
|
};
|
};
|
|
|
typedef struct access_site_info *access_site_info_p;
|
typedef struct access_site_info *access_site_info_p;
|
DEF_VEC_P (access_site_info_p);
|
DEF_VEC_P (access_site_info_p);
|
DEF_VEC_ALLOC_P (access_site_info_p, heap);
|
DEF_VEC_ALLOC_P (access_site_info_p, heap);
|
|
|
/* Calls to free when flattening a matrix. */
|
/* Calls to free when flattening a matrix. */
|
|
|
struct free_info
|
struct free_info
|
{
|
{
|
gimple stmt;
|
gimple stmt;
|
tree func;
|
tree func;
|
};
|
};
|
|
|
/* Information about matrix to flatten. */
|
/* Information about matrix to flatten. */
|
struct matrix_info
|
struct matrix_info
|
{
|
{
|
/* Decl tree of this matrix. */
|
/* Decl tree of this matrix. */
|
tree decl;
|
tree decl;
|
/* Number of dimensions; number
|
/* Number of dimensions; number
|
of "*" in the type declaration. */
|
of "*" in the type declaration. */
|
int num_dims;
|
int num_dims;
|
|
|
/* Minimum indirection level that escapes, 0 means that
|
/* Minimum indirection level that escapes, 0 means that
|
the whole matrix escapes, k means that dimensions
|
the whole matrix escapes, k means that dimensions
|
0 to ACTUAL_DIM - k escapes. */
|
0 to ACTUAL_DIM - k escapes. */
|
int min_indirect_level_escape;
|
int min_indirect_level_escape;
|
|
|
gimple min_indirect_level_escape_stmt;
|
gimple min_indirect_level_escape_stmt;
|
|
|
/* Hold the allocation site for each level (dimension).
|
/* Hold the allocation site for each level (dimension).
|
We can use NUM_DIMS as the upper bound and allocate the array
|
We can use NUM_DIMS as the upper bound and allocate the array
|
once with this number of elements and no need to use realloc and
|
once with this number of elements and no need to use realloc and
|
MAX_MALLOCED_LEVEL. */
|
MAX_MALLOCED_LEVEL. */
|
gimple *malloc_for_level;
|
gimple *malloc_for_level;
|
|
|
int max_malloced_level;
|
int max_malloced_level;
|
|
|
/* Is the matrix transposed. */
|
/* Is the matrix transposed. */
|
bool is_transposed_p;
|
bool is_transposed_p;
|
|
|
/* The location of the allocation sites (they must be in one
|
/* The location of the allocation sites (they must be in one
|
function). */
|
function). */
|
tree allocation_function_decl;
|
tree allocation_function_decl;
|
|
|
/* The calls to free for each level of indirection. */
|
/* The calls to free for each level of indirection. */
|
struct free_info *free_stmts;
|
struct free_info *free_stmts;
|
|
|
/* An array which holds for each dimension its size. where
|
/* An array which holds for each dimension its size. where
|
dimension 0 is the outer most (one that contains all the others).
|
dimension 0 is the outer most (one that contains all the others).
|
*/
|
*/
|
tree *dimension_size;
|
tree *dimension_size;
|
|
|
/* An array which holds for each dimension it's original size
|
/* An array which holds for each dimension it's original size
|
(before transposing and flattening take place). */
|
(before transposing and flattening take place). */
|
tree *dimension_size_orig;
|
tree *dimension_size_orig;
|
|
|
/* An array which holds for each dimension the size of the type of
|
/* An array which holds for each dimension the size of the type of
|
of elements accessed in that level (in bytes). */
|
of elements accessed in that level (in bytes). */
|
HOST_WIDE_INT *dimension_type_size;
|
HOST_WIDE_INT *dimension_type_size;
|
|
|
int dimension_type_size_len;
|
int dimension_type_size_len;
|
|
|
/* An array collecting the count of accesses for each dimension. */
|
/* An array collecting the count of accesses for each dimension. */
|
gcov_type *dim_hot_level;
|
gcov_type *dim_hot_level;
|
|
|
/* An array of the accesses to be flattened.
|
/* An array of the accesses to be flattened.
|
elements are of type "struct access_site_info *". */
|
elements are of type "struct access_site_info *". */
|
VEC (access_site_info_p, heap) * access_l;
|
VEC (access_site_info_p, heap) * access_l;
|
|
|
/* A map of how the dimensions will be organized at the end of
|
/* A map of how the dimensions will be organized at the end of
|
the analyses. */
|
the analyses. */
|
int *dim_map;
|
int *dim_map;
|
};
|
};
|
|
|
/* In each phi node we want to record the indirection level we have when we
|
/* In each phi node we want to record the indirection level we have when we
|
get to the phi node. Usually we will have phi nodes with more than two
|
get to the phi node. Usually we will have phi nodes with more than two
|
arguments, then we must assure that all of them get to the phi node with
|
arguments, then we must assure that all of them get to the phi node with
|
the same indirection level, otherwise it's not safe to do the flattening.
|
the same indirection level, otherwise it's not safe to do the flattening.
|
So we record the information regarding the indirection level each time we
|
So we record the information regarding the indirection level each time we
|
get to the phi node in this hash table. */
|
get to the phi node in this hash table. */
|
|
|
struct matrix_access_phi_node
|
struct matrix_access_phi_node
|
{
|
{
|
gimple phi;
|
gimple phi;
|
int indirection_level;
|
int indirection_level;
|
};
|
};
|
|
|
/* We use this structure to find if the SSA variable is accessed inside the
|
/* We use this structure to find if the SSA variable is accessed inside the
|
tree and record the tree containing it. */
|
tree and record the tree containing it. */
|
|
|
struct ssa_acc_in_tree
|
struct ssa_acc_in_tree
|
{
|
{
|
/* The variable whose accesses in the tree we are looking for. */
|
/* The variable whose accesses in the tree we are looking for. */
|
tree ssa_var;
|
tree ssa_var;
|
/* The tree and code inside it the ssa_var is accessed, currently
|
/* The tree and code inside it the ssa_var is accessed, currently
|
it could be an MEM_REF or CALL_EXPR. */
|
it could be an MEM_REF or CALL_EXPR. */
|
enum tree_code t_code;
|
enum tree_code t_code;
|
tree t_tree;
|
tree t_tree;
|
/* The place in the containing tree. */
|
/* The place in the containing tree. */
|
tree *tp;
|
tree *tp;
|
tree second_op;
|
tree second_op;
|
bool var_found;
|
bool var_found;
|
};
|
};
|
|
|
static void analyze_matrix_accesses (struct matrix_info *, tree, int, bool,
|
static void analyze_matrix_accesses (struct matrix_info *, tree, int, bool,
|
sbitmap, bool);
|
sbitmap, bool);
|
static int transform_allocation_sites (void **, void *);
|
static int transform_allocation_sites (void **, void *);
|
static int transform_access_sites (void **, void *);
|
static int transform_access_sites (void **, void *);
|
static int analyze_transpose (void **, void *);
|
static int analyze_transpose (void **, void *);
|
static int dump_matrix_reorg_analysis (void **, void *);
|
static int dump_matrix_reorg_analysis (void **, void *);
|
|
|
static bool check_transpose_p;
|
static bool check_transpose_p;
|
|
|
/* Hash function used for the phi nodes. */
|
/* Hash function used for the phi nodes. */
|
|
|
static hashval_t
|
static hashval_t
|
mat_acc_phi_hash (const void *p)
|
mat_acc_phi_hash (const void *p)
|
{
|
{
|
const struct matrix_access_phi_node *const ma_phi =
|
const struct matrix_access_phi_node *const ma_phi =
|
(const struct matrix_access_phi_node *) p;
|
(const struct matrix_access_phi_node *) p;
|
|
|
return htab_hash_pointer (ma_phi->phi);
|
return htab_hash_pointer (ma_phi->phi);
|
}
|
}
|
|
|
/* Equality means phi node pointers are the same. */
|
/* Equality means phi node pointers are the same. */
|
|
|
static int
|
static int
|
mat_acc_phi_eq (const void *p1, const void *p2)
|
mat_acc_phi_eq (const void *p1, const void *p2)
|
{
|
{
|
const struct matrix_access_phi_node *const phi1 =
|
const struct matrix_access_phi_node *const phi1 =
|
(const struct matrix_access_phi_node *) p1;
|
(const struct matrix_access_phi_node *) p1;
|
const struct matrix_access_phi_node *const phi2 =
|
const struct matrix_access_phi_node *const phi2 =
|
(const struct matrix_access_phi_node *) p2;
|
(const struct matrix_access_phi_node *) p2;
|
|
|
if (phi1->phi == phi2->phi)
|
if (phi1->phi == phi2->phi)
|
return 1;
|
return 1;
|
|
|
return 0;
|
return 0;
|
}
|
}
|
|
|
/* Hold the PHI nodes we visit during the traversal for escaping
|
/* Hold the PHI nodes we visit during the traversal for escaping
|
analysis. */
|
analysis. */
|
static htab_t htab_mat_acc_phi_nodes = NULL;
|
static htab_t htab_mat_acc_phi_nodes = NULL;
|
|
|
/* This hash-table holds the information about the matrices we are
|
/* This hash-table holds the information about the matrices we are
|
going to handle. */
|
going to handle. */
|
static htab_t matrices_to_reorg = NULL;
|
static htab_t matrices_to_reorg = NULL;
|
|
|
/* Return a hash for MTT, which is really a "matrix_info *". */
|
/* Return a hash for MTT, which is really a "matrix_info *". */
|
static hashval_t
|
static hashval_t
|
mtt_info_hash (const void *mtt)
|
mtt_info_hash (const void *mtt)
|
{
|
{
|
return htab_hash_pointer (((const struct matrix_info *) mtt)->decl);
|
return htab_hash_pointer (((const struct matrix_info *) mtt)->decl);
|
}
|
}
|
|
|
/* Return true if MTT1 and MTT2 (which are really both of type
|
/* Return true if MTT1 and MTT2 (which are really both of type
|
"matrix_info *") refer to the same decl. */
|
"matrix_info *") refer to the same decl. */
|
static int
|
static int
|
mtt_info_eq (const void *mtt1, const void *mtt2)
|
mtt_info_eq (const void *mtt1, const void *mtt2)
|
{
|
{
|
const struct matrix_info *const i1 = (const struct matrix_info *) mtt1;
|
const struct matrix_info *const i1 = (const struct matrix_info *) mtt1;
|
const struct matrix_info *const i2 = (const struct matrix_info *) mtt2;
|
const struct matrix_info *const i2 = (const struct matrix_info *) mtt2;
|
|
|
if (i1->decl == i2->decl)
|
if (i1->decl == i2->decl)
|
return true;
|
return true;
|
|
|
return false;
|
return false;
|
}
|
}
|
|
|
/* Return false if STMT may contain a vector expression.
|
/* Return false if STMT may contain a vector expression.
|
In this situation, all matrices should not be flattened. */
|
In this situation, all matrices should not be flattened. */
|
static bool
|
static bool
|
may_flatten_matrices_1 (gimple stmt)
|
may_flatten_matrices_1 (gimple stmt)
|
{
|
{
|
switch (gimple_code (stmt))
|
switch (gimple_code (stmt))
|
{
|
{
|
case GIMPLE_ASSIGN:
|
case GIMPLE_ASSIGN:
|
case GIMPLE_CALL:
|
case GIMPLE_CALL:
|
if (!gimple_has_lhs (stmt))
|
if (!gimple_has_lhs (stmt))
|
return true;
|
return true;
|
if (TREE_CODE (TREE_TYPE (gimple_get_lhs (stmt))) == VECTOR_TYPE)
|
if (TREE_CODE (TREE_TYPE (gimple_get_lhs (stmt))) == VECTOR_TYPE)
|
{
|
{
|
if (dump_file)
|
if (dump_file)
|
fprintf (dump_file,
|
fprintf (dump_file,
|
"Found vector type, don't flatten matrix\n");
|
"Found vector type, don't flatten matrix\n");
|
return false;
|
return false;
|
}
|
}
|
break;
|
break;
|
case GIMPLE_ASM:
|
case GIMPLE_ASM:
|
/* Asm code could contain vector operations. */
|
/* Asm code could contain vector operations. */
|
return false;
|
return false;
|
break;
|
break;
|
default:
|
default:
|
break;
|
break;
|
}
|
}
|
return true;
|
return true;
|
}
|
}
|
|
|
/* Return false if there are hand-written vectors in the program.
|
/* Return false if there are hand-written vectors in the program.
|
We disable the flattening in such a case. */
|
We disable the flattening in such a case. */
|
static bool
|
static bool
|
may_flatten_matrices (struct cgraph_node *node)
|
may_flatten_matrices (struct cgraph_node *node)
|
{
|
{
|
tree decl;
|
tree decl;
|
struct function *func;
|
struct function *func;
|
basic_block bb;
|
basic_block bb;
|
gimple_stmt_iterator gsi;
|
gimple_stmt_iterator gsi;
|
|
|
decl = node->decl;
|
decl = node->decl;
|
if (node->analyzed)
|
if (node->analyzed)
|
{
|
{
|
func = DECL_STRUCT_FUNCTION (decl);
|
func = DECL_STRUCT_FUNCTION (decl);
|
FOR_EACH_BB_FN (bb, func)
|
FOR_EACH_BB_FN (bb, func)
|
for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
|
for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
|
if (!may_flatten_matrices_1 (gsi_stmt (gsi)))
|
if (!may_flatten_matrices_1 (gsi_stmt (gsi)))
|
return false;
|
return false;
|
}
|
}
|
return true;
|
return true;
|
}
|
}
|
|
|
/* Given a VAR_DECL, check its type to determine whether it is
|
/* Given a VAR_DECL, check its type to determine whether it is
|
a definition of a dynamic allocated matrix and therefore is
|
a definition of a dynamic allocated matrix and therefore is
|
a suitable candidate for the matrix flattening optimization.
|
a suitable candidate for the matrix flattening optimization.
|
Return NULL if VAR_DECL is not such decl. Otherwise, allocate
|
Return NULL if VAR_DECL is not such decl. Otherwise, allocate
|
a MATRIX_INFO structure, fill it with the relevant information
|
a MATRIX_INFO structure, fill it with the relevant information
|
and return a pointer to it.
|
and return a pointer to it.
|
TODO: handle also statically defined arrays. */
|
TODO: handle also statically defined arrays. */
|
static struct matrix_info *
|
static struct matrix_info *
|
analyze_matrix_decl (tree var_decl)
|
analyze_matrix_decl (tree var_decl)
|
{
|
{
|
struct matrix_info *m_node, tmpmi, *mi;
|
struct matrix_info *m_node, tmpmi, *mi;
|
tree var_type;
|
tree var_type;
|
int dim_num = 0;
|
int dim_num = 0;
|
|
|
gcc_assert (matrices_to_reorg);
|
gcc_assert (matrices_to_reorg);
|
|
|
if (TREE_CODE (var_decl) == PARM_DECL)
|
if (TREE_CODE (var_decl) == PARM_DECL)
|
var_type = DECL_ARG_TYPE (var_decl);
|
var_type = DECL_ARG_TYPE (var_decl);
|
else if (TREE_CODE (var_decl) == VAR_DECL)
|
else if (TREE_CODE (var_decl) == VAR_DECL)
|
var_type = TREE_TYPE (var_decl);
|
var_type = TREE_TYPE (var_decl);
|
else
|
else
|
return NULL;
|
return NULL;
|
|
|
if (!POINTER_TYPE_P (var_type))
|
if (!POINTER_TYPE_P (var_type))
|
return NULL;
|
return NULL;
|
|
|
while (POINTER_TYPE_P (var_type))
|
while (POINTER_TYPE_P (var_type))
|
{
|
{
|
var_type = TREE_TYPE (var_type);
|
var_type = TREE_TYPE (var_type);
|
dim_num++;
|
dim_num++;
|
}
|
}
|
|
|
if (dim_num <= 1)
|
if (dim_num <= 1)
|
return NULL;
|
return NULL;
|
|
|
if (!COMPLETE_TYPE_P (var_type)
|
if (!COMPLETE_TYPE_P (var_type)
|
|| TREE_CODE (TYPE_SIZE_UNIT (var_type)) != INTEGER_CST)
|
|| TREE_CODE (TYPE_SIZE_UNIT (var_type)) != INTEGER_CST)
|
return NULL;
|
return NULL;
|
|
|
/* Check to see if this pointer is already in there. */
|
/* Check to see if this pointer is already in there. */
|
tmpmi.decl = var_decl;
|
tmpmi.decl = var_decl;
|
mi = (struct matrix_info *) htab_find (matrices_to_reorg, &tmpmi);
|
mi = (struct matrix_info *) htab_find (matrices_to_reorg, &tmpmi);
|
|
|
if (mi)
|
if (mi)
|
return NULL;
|
return NULL;
|
|
|
/* Record the matrix. */
|
/* Record the matrix. */
|
|
|
m_node = (struct matrix_info *) xcalloc (1, sizeof (struct matrix_info));
|
m_node = (struct matrix_info *) xcalloc (1, sizeof (struct matrix_info));
|
m_node->decl = var_decl;
|
m_node->decl = var_decl;
|
m_node->num_dims = dim_num;
|
m_node->num_dims = dim_num;
|
m_node->free_stmts
|
m_node->free_stmts
|
= (struct free_info *) xcalloc (dim_num, sizeof (struct free_info));
|
= (struct free_info *) xcalloc (dim_num, sizeof (struct free_info));
|
|
|
/* Init min_indirect_level_escape to -1 to indicate that no escape
|
/* Init min_indirect_level_escape to -1 to indicate that no escape
|
analysis has been done yet. */
|
analysis has been done yet. */
|
m_node->min_indirect_level_escape = -1;
|
m_node->min_indirect_level_escape = -1;
|
m_node->is_transposed_p = false;
|
m_node->is_transposed_p = false;
|
|
|
return m_node;
|
return m_node;
|
}
|
}
|
|
|
/* Free matrix E. */
|
/* Free matrix E. */
|
static void
|
static void
|
mat_free (void *e)
|
mat_free (void *e)
|
{
|
{
|
struct matrix_info *mat = (struct matrix_info *) e;
|
struct matrix_info *mat = (struct matrix_info *) e;
|
|
|
if (!mat)
|
if (!mat)
|
return;
|
return;
|
|
|
free (mat->free_stmts);
|
free (mat->free_stmts);
|
free (mat->dim_hot_level);
|
free (mat->dim_hot_level);
|
free (mat->malloc_for_level);
|
free (mat->malloc_for_level);
|
}
|
}
|
|
|
/* Find all potential matrices.
|
/* Find all potential matrices.
|
TODO: currently we handle only multidimensional
|
TODO: currently we handle only multidimensional
|
dynamically allocated arrays. */
|
dynamically allocated arrays. */
|
static void
|
static void
|
find_matrices_decl (void)
|
find_matrices_decl (void)
|
{
|
{
|
struct matrix_info *tmp;
|
struct matrix_info *tmp;
|
PTR *slot;
|
PTR *slot;
|
struct varpool_node *vnode;
|
struct varpool_node *vnode;
|
|
|
gcc_assert (matrices_to_reorg);
|
gcc_assert (matrices_to_reorg);
|
|
|
/* For every global variable in the program:
|
/* For every global variable in the program:
|
Check to see if it's of a candidate type and record it. */
|
Check to see if it's of a candidate type and record it. */
|
for (vnode = varpool_nodes_queue; vnode; vnode = vnode->next_needed)
|
for (vnode = varpool_nodes_queue; vnode; vnode = vnode->next_needed)
|
{
|
{
|
tree var_decl = vnode->decl;
|
tree var_decl = vnode->decl;
|
|
|
if (!var_decl || TREE_CODE (var_decl) != VAR_DECL)
|
if (!var_decl || TREE_CODE (var_decl) != VAR_DECL)
|
continue;
|
continue;
|
|
|
if (matrices_to_reorg)
|
if (matrices_to_reorg)
|
if ((tmp = analyze_matrix_decl (var_decl)))
|
if ((tmp = analyze_matrix_decl (var_decl)))
|
{
|
{
|
if (!TREE_ADDRESSABLE (var_decl))
|
if (!TREE_ADDRESSABLE (var_decl))
|
{
|
{
|
slot = htab_find_slot (matrices_to_reorg, tmp, INSERT);
|
slot = htab_find_slot (matrices_to_reorg, tmp, INSERT);
|
*slot = tmp;
|
*slot = tmp;
|
}
|
}
|
}
|
}
|
}
|
}
|
return;
|
return;
|
}
|
}
|
|
|
/* Mark that the matrix MI escapes at level L. */
|
/* Mark that the matrix MI escapes at level L. */
|
static void
|
static void
|
mark_min_matrix_escape_level (struct matrix_info *mi, int l, gimple s)
|
mark_min_matrix_escape_level (struct matrix_info *mi, int l, gimple s)
|
{
|
{
|
if (mi->min_indirect_level_escape == -1
|
if (mi->min_indirect_level_escape == -1
|
|| (mi->min_indirect_level_escape > l))
|
|| (mi->min_indirect_level_escape > l))
|
{
|
{
|
mi->min_indirect_level_escape = l;
|
mi->min_indirect_level_escape = l;
|
mi->min_indirect_level_escape_stmt = s;
|
mi->min_indirect_level_escape_stmt = s;
|
}
|
}
|
}
|
}
|
|
|
/* Find if the SSA variable is accessed inside the
|
/* Find if the SSA variable is accessed inside the
|
tree and record the tree containing it.
|
tree and record the tree containing it.
|
The only relevant uses are the case of SSA_NAME, or SSA inside
|
The only relevant uses are the case of SSA_NAME, or SSA inside
|
MEM_REF, PLUS_EXPR, POINTER_PLUS_EXPR, MULT_EXPR. */
|
MEM_REF, PLUS_EXPR, POINTER_PLUS_EXPR, MULT_EXPR. */
|
static void
|
static void
|
ssa_accessed_in_tree (tree t, struct ssa_acc_in_tree *a)
|
ssa_accessed_in_tree (tree t, struct ssa_acc_in_tree *a)
|
{
|
{
|
a->t_code = TREE_CODE (t);
|
a->t_code = TREE_CODE (t);
|
switch (a->t_code)
|
switch (a->t_code)
|
{
|
{
|
case SSA_NAME:
|
case SSA_NAME:
|
if (t == a->ssa_var)
|
if (t == a->ssa_var)
|
a->var_found = true;
|
a->var_found = true;
|
break;
|
break;
|
case MEM_REF:
|
case MEM_REF:
|
if (SSA_VAR_P (TREE_OPERAND (t, 0))
|
if (SSA_VAR_P (TREE_OPERAND (t, 0))
|
&& TREE_OPERAND (t, 0) == a->ssa_var)
|
&& TREE_OPERAND (t, 0) == a->ssa_var)
|
a->var_found = true;
|
a->var_found = true;
|
break;
|
break;
|
default:
|
default:
|
break;
|
break;
|
}
|
}
|
}
|
}
|
|
|
/* Find if the SSA variable is accessed on the right hand side of
|
/* Find if the SSA variable is accessed on the right hand side of
|
gimple call STMT. */
|
gimple call STMT. */
|
|
|
static void
|
static void
|
ssa_accessed_in_call_rhs (gimple stmt, struct ssa_acc_in_tree *a)
|
ssa_accessed_in_call_rhs (gimple stmt, struct ssa_acc_in_tree *a)
|
{
|
{
|
tree decl;
|
tree decl;
|
tree arg;
|
tree arg;
|
size_t i;
|
size_t i;
|
|
|
a->t_code = CALL_EXPR;
|
a->t_code = CALL_EXPR;
|
for (i = 0; i < gimple_call_num_args (stmt); i++)
|
for (i = 0; i < gimple_call_num_args (stmt); i++)
|
{
|
{
|
arg = gimple_call_arg (stmt, i);
|
arg = gimple_call_arg (stmt, i);
|
if (arg == a->ssa_var)
|
if (arg == a->ssa_var)
|
{
|
{
|
a->var_found = true;
|
a->var_found = true;
|
decl = gimple_call_fndecl (stmt);
|
decl = gimple_call_fndecl (stmt);
|
a->t_tree = decl;
|
a->t_tree = decl;
|
break;
|
break;
|
}
|
}
|
}
|
}
|
}
|
}
|
|
|
/* Find if the SSA variable is accessed on the right hand side of
|
/* Find if the SSA variable is accessed on the right hand side of
|
gimple assign STMT. */
|
gimple assign STMT. */
|
|
|
static void
|
static void
|
ssa_accessed_in_assign_rhs (gimple stmt, struct ssa_acc_in_tree *a)
|
ssa_accessed_in_assign_rhs (gimple stmt, struct ssa_acc_in_tree *a)
|
{
|
{
|
|
|
a->t_code = gimple_assign_rhs_code (stmt);
|
a->t_code = gimple_assign_rhs_code (stmt);
|
switch (a->t_code)
|
switch (a->t_code)
|
{
|
{
|
tree op1, op2;
|
tree op1, op2;
|
|
|
case SSA_NAME:
|
case SSA_NAME:
|
case MEM_REF:
|
case MEM_REF:
|
CASE_CONVERT:
|
CASE_CONVERT:
|
case VIEW_CONVERT_EXPR:
|
case VIEW_CONVERT_EXPR:
|
ssa_accessed_in_tree (gimple_assign_rhs1 (stmt), a);
|
ssa_accessed_in_tree (gimple_assign_rhs1 (stmt), a);
|
break;
|
break;
|
case POINTER_PLUS_EXPR:
|
case POINTER_PLUS_EXPR:
|
case PLUS_EXPR:
|
case PLUS_EXPR:
|
case MULT_EXPR:
|
case MULT_EXPR:
|
op1 = gimple_assign_rhs1 (stmt);
|
op1 = gimple_assign_rhs1 (stmt);
|
op2 = gimple_assign_rhs2 (stmt);
|
op2 = gimple_assign_rhs2 (stmt);
|
|
|
if (op1 == a->ssa_var)
|
if (op1 == a->ssa_var)
|
{
|
{
|
a->var_found = true;
|
a->var_found = true;
|
a->second_op = op2;
|
a->second_op = op2;
|
}
|
}
|
else if (op2 == a->ssa_var)
|
else if (op2 == a->ssa_var)
|
{
|
{
|
a->var_found = true;
|
a->var_found = true;
|
a->second_op = op1;
|
a->second_op = op1;
|
}
|
}
|
break;
|
break;
|
default:
|
default:
|
break;
|
break;
|
}
|
}
|
}
|
}
|
|
|
/* Record the access/allocation site information for matrix MI so we can
|
/* Record the access/allocation site information for matrix MI so we can
|
handle it later in transformation. */
|
handle it later in transformation. */
|
static void
|
static void
|
record_access_alloc_site_info (struct matrix_info *mi, gimple stmt, tree offset,
|
record_access_alloc_site_info (struct matrix_info *mi, gimple stmt, tree offset,
|
tree index, int level, bool is_alloc)
|
tree index, int level, bool is_alloc)
|
{
|
{
|
struct access_site_info *acc_info;
|
struct access_site_info *acc_info;
|
|
|
if (!mi->access_l)
|
if (!mi->access_l)
|
mi->access_l = VEC_alloc (access_site_info_p, heap, 100);
|
mi->access_l = VEC_alloc (access_site_info_p, heap, 100);
|
|
|
acc_info
|
acc_info
|
= (struct access_site_info *)
|
= (struct access_site_info *)
|
xcalloc (1, sizeof (struct access_site_info));
|
xcalloc (1, sizeof (struct access_site_info));
|
acc_info->stmt = stmt;
|
acc_info->stmt = stmt;
|
acc_info->offset = offset;
|
acc_info->offset = offset;
|
acc_info->index = index;
|
acc_info->index = index;
|
acc_info->function_decl = current_function_decl;
|
acc_info->function_decl = current_function_decl;
|
acc_info->level = level;
|
acc_info->level = level;
|
acc_info->is_alloc = is_alloc;
|
acc_info->is_alloc = is_alloc;
|
|
|
VEC_safe_push (access_site_info_p, heap, mi->access_l, acc_info);
|
VEC_safe_push (access_site_info_p, heap, mi->access_l, acc_info);
|
|
|
}
|
}
|
|
|
/* Record the malloc as the allocation site of the given LEVEL. But
|
/* Record the malloc as the allocation site of the given LEVEL. But
|
first we Make sure that all the size parameters passed to malloc in
|
first we Make sure that all the size parameters passed to malloc in
|
all the allocation sites could be pre-calculated before the call to
|
all the allocation sites could be pre-calculated before the call to
|
the malloc of level 0 (the main malloc call). */
|
the malloc of level 0 (the main malloc call). */
|
static void
|
static void
|
add_allocation_site (struct matrix_info *mi, gimple stmt, int level)
|
add_allocation_site (struct matrix_info *mi, gimple stmt, int level)
|
{
|
{
|
struct malloc_call_data mcd;
|
struct malloc_call_data mcd;
|
|
|
/* Make sure that the allocation sites are in the same function. */
|
/* Make sure that the allocation sites are in the same function. */
|
if (!mi->allocation_function_decl)
|
if (!mi->allocation_function_decl)
|
mi->allocation_function_decl = current_function_decl;
|
mi->allocation_function_decl = current_function_decl;
|
else if (mi->allocation_function_decl != current_function_decl)
|
else if (mi->allocation_function_decl != current_function_decl)
|
{
|
{
|
int min_malloc_level;
|
int min_malloc_level;
|
|
|
gcc_assert (mi->malloc_for_level);
|
gcc_assert (mi->malloc_for_level);
|
|
|
/* Find the minimum malloc level that already has been seen;
|
/* Find the minimum malloc level that already has been seen;
|
we known its allocation function must be
|
we known its allocation function must be
|
MI->allocation_function_decl since it's different than
|
MI->allocation_function_decl since it's different than
|
CURRENT_FUNCTION_DECL then the escaping level should be
|
CURRENT_FUNCTION_DECL then the escaping level should be
|
MIN (LEVEL, MIN_MALLOC_LEVEL) - 1 , and the allocation function
|
MIN (LEVEL, MIN_MALLOC_LEVEL) - 1 , and the allocation function
|
must be set accordingly. */
|
must be set accordingly. */
|
for (min_malloc_level = 0;
|
for (min_malloc_level = 0;
|
min_malloc_level < mi->max_malloced_level
|
min_malloc_level < mi->max_malloced_level
|
&& mi->malloc_for_level[min_malloc_level]; min_malloc_level++)
|
&& mi->malloc_for_level[min_malloc_level]; min_malloc_level++)
|
;
|
;
|
if (level < min_malloc_level)
|
if (level < min_malloc_level)
|
{
|
{
|
mi->allocation_function_decl = current_function_decl;
|
mi->allocation_function_decl = current_function_decl;
|
mark_min_matrix_escape_level (mi, min_malloc_level, stmt);
|
mark_min_matrix_escape_level (mi, min_malloc_level, stmt);
|
}
|
}
|
else
|
else
|
{
|
{
|
mark_min_matrix_escape_level (mi, level, stmt);
|
mark_min_matrix_escape_level (mi, level, stmt);
|
/* cannot be that (level == min_malloc_level)
|
/* cannot be that (level == min_malloc_level)
|
we would have returned earlier. */
|
we would have returned earlier. */
|
return;
|
return;
|
}
|
}
|
}
|
}
|
|
|
/* Find the correct malloc information. */
|
/* Find the correct malloc information. */
|
collect_data_for_malloc_call (stmt, &mcd);
|
collect_data_for_malloc_call (stmt, &mcd);
|
|
|
/* We accept only calls to malloc function; we do not accept
|
/* We accept only calls to malloc function; we do not accept
|
calls like calloc and realloc. */
|
calls like calloc and realloc. */
|
if (!mi->malloc_for_level)
|
if (!mi->malloc_for_level)
|
{
|
{
|
mi->malloc_for_level = XCNEWVEC (gimple, level + 1);
|
mi->malloc_for_level = XCNEWVEC (gimple, level + 1);
|
mi->max_malloced_level = level + 1;
|
mi->max_malloced_level = level + 1;
|
}
|
}
|
else if (mi->max_malloced_level <= level)
|
else if (mi->max_malloced_level <= level)
|
{
|
{
|
mi->malloc_for_level
|
mi->malloc_for_level
|
= XRESIZEVEC (gimple, mi->malloc_for_level, level + 1);
|
= XRESIZEVEC (gimple, mi->malloc_for_level, level + 1);
|
|
|
/* Zero the newly allocated items. */
|
/* Zero the newly allocated items. */
|
memset (&(mi->malloc_for_level[mi->max_malloced_level + 1]),
|
memset (&(mi->malloc_for_level[mi->max_malloced_level + 1]),
|
0, (level - mi->max_malloced_level) * sizeof (tree));
|
0, (level - mi->max_malloced_level) * sizeof (tree));
|
|
|
mi->max_malloced_level = level + 1;
|
mi->max_malloced_level = level + 1;
|
}
|
}
|
mi->malloc_for_level[level] = stmt;
|
mi->malloc_for_level[level] = stmt;
|
}
|
}
|
|
|
/* Given an assignment statement STMT that we know that its
|
/* Given an assignment statement STMT that we know that its
|
left-hand-side is the matrix MI variable, we traverse the immediate
|
left-hand-side is the matrix MI variable, we traverse the immediate
|
uses backwards until we get to a malloc site. We make sure that
|
uses backwards until we get to a malloc site. We make sure that
|
there is one and only one malloc site that sets this variable. When
|
there is one and only one malloc site that sets this variable. When
|
we are performing the flattening we generate a new variable that
|
we are performing the flattening we generate a new variable that
|
will hold the size for each dimension; each malloc that allocates a
|
will hold the size for each dimension; each malloc that allocates a
|
dimension has the size parameter; we use that parameter to
|
dimension has the size parameter; we use that parameter to
|
initialize the dimension size variable so we can use it later in
|
initialize the dimension size variable so we can use it later in
|
the address calculations. LEVEL is the dimension we're inspecting.
|
the address calculations. LEVEL is the dimension we're inspecting.
|
Return if STMT is related to an allocation site. */
|
Return if STMT is related to an allocation site. */
|
|
|
static void
|
static void
|
analyze_matrix_allocation_site (struct matrix_info *mi, gimple stmt,
|
analyze_matrix_allocation_site (struct matrix_info *mi, gimple stmt,
|
int level, sbitmap visited)
|
int level, sbitmap visited)
|
{
|
{
|
if (gimple_assign_copy_p (stmt) || gimple_assign_cast_p (stmt))
|
if (gimple_assign_copy_p (stmt) || gimple_assign_cast_p (stmt))
|
{
|
{
|
tree rhs = gimple_assign_rhs1 (stmt);
|
tree rhs = gimple_assign_rhs1 (stmt);
|
|
|
if (TREE_CODE (rhs) == SSA_NAME)
|
if (TREE_CODE (rhs) == SSA_NAME)
|
{
|
{
|
gimple def = SSA_NAME_DEF_STMT (rhs);
|
gimple def = SSA_NAME_DEF_STMT (rhs);
|
|
|
analyze_matrix_allocation_site (mi, def, level, visited);
|
analyze_matrix_allocation_site (mi, def, level, visited);
|
return;
|
return;
|
}
|
}
|
/* If we are back to the original matrix variable then we
|
/* If we are back to the original matrix variable then we
|
are sure that this is analyzed as an access site. */
|
are sure that this is analyzed as an access site. */
|
else if (rhs == mi->decl)
|
else if (rhs == mi->decl)
|
return;
|
return;
|
}
|
}
|
/* A result of call to malloc. */
|
/* A result of call to malloc. */
|
else if (is_gimple_call (stmt))
|
else if (is_gimple_call (stmt))
|
{
|
{
|
int call_flags = gimple_call_flags (stmt);
|
int call_flags = gimple_call_flags (stmt);
|
|
|
if (!(call_flags & ECF_MALLOC))
|
if (!(call_flags & ECF_MALLOC))
|
{
|
{
|
mark_min_matrix_escape_level (mi, level, stmt);
|
mark_min_matrix_escape_level (mi, level, stmt);
|
return;
|
return;
|
}
|
}
|
else
|
else
|
{
|
{
|
tree malloc_fn_decl;
|
tree malloc_fn_decl;
|
|
|
malloc_fn_decl = gimple_call_fndecl (stmt);
|
malloc_fn_decl = gimple_call_fndecl (stmt);
|
if (malloc_fn_decl == NULL_TREE)
|
if (malloc_fn_decl == NULL_TREE)
|
{
|
{
|
mark_min_matrix_escape_level (mi, level, stmt);
|
mark_min_matrix_escape_level (mi, level, stmt);
|
return;
|
return;
|
}
|
}
|
if (DECL_FUNCTION_CODE (malloc_fn_decl) != BUILT_IN_MALLOC)
|
if (DECL_FUNCTION_CODE (malloc_fn_decl) != BUILT_IN_MALLOC)
|
{
|
{
|
if (dump_file)
|
if (dump_file)
|
fprintf (dump_file,
|
fprintf (dump_file,
|
"Matrix %s is an argument to function %s\n",
|
"Matrix %s is an argument to function %s\n",
|
get_name (mi->decl), get_name (malloc_fn_decl));
|
get_name (mi->decl), get_name (malloc_fn_decl));
|
mark_min_matrix_escape_level (mi, level, stmt);
|
mark_min_matrix_escape_level (mi, level, stmt);
|
return;
|
return;
|
}
|
}
|
}
|
}
|
/* This is a call to malloc of level 'level'.
|
/* This is a call to malloc of level 'level'.
|
mi->max_malloced_level-1 == level means that we've
|
mi->max_malloced_level-1 == level means that we've
|
seen a malloc statement of level 'level' before.
|
seen a malloc statement of level 'level' before.
|
If the statement is not the same one that we've
|
If the statement is not the same one that we've
|
seen before, then there's another malloc statement
|
seen before, then there's another malloc statement
|
for the same level, which means that we need to mark
|
for the same level, which means that we need to mark
|
it escaping. */
|
it escaping. */
|
if (mi->malloc_for_level
|
if (mi->malloc_for_level
|
&& mi->max_malloced_level-1 == level
|
&& mi->max_malloced_level-1 == level
|
&& mi->malloc_for_level[level] != stmt)
|
&& mi->malloc_for_level[level] != stmt)
|
{
|
{
|
mark_min_matrix_escape_level (mi, level, stmt);
|
mark_min_matrix_escape_level (mi, level, stmt);
|
return;
|
return;
|
}
|
}
|
else
|
else
|
add_allocation_site (mi, stmt, level);
|
add_allocation_site (mi, stmt, level);
|
return;
|
return;
|
}
|
}
|
/* Looks like we don't know what is happening in this
|
/* Looks like we don't know what is happening in this
|
statement so be in the safe side and mark it as escaping. */
|
statement so be in the safe side and mark it as escaping. */
|
mark_min_matrix_escape_level (mi, level, stmt);
|
mark_min_matrix_escape_level (mi, level, stmt);
|
}
|
}
|
|
|
/* The transposing decision making.
|
/* The transposing decision making.
|
In order to calculate the profitability of transposing, we collect two
|
In order to calculate the profitability of transposing, we collect two
|
types of information regarding the accesses:
|
types of information regarding the accesses:
|
1. profiling information used to express the hotness of an access, that
|
1. profiling information used to express the hotness of an access, that
|
is how often the matrix is accessed by this access site (count of the
|
is how often the matrix is accessed by this access site (count of the
|
access site).
|
access site).
|
2. which dimension in the access site is iterated by the inner
|
2. which dimension in the access site is iterated by the inner
|
most loop containing this access.
|
most loop containing this access.
|
|
|
The matrix will have a calculated value of weighted hotness for each
|
The matrix will have a calculated value of weighted hotness for each
|
dimension.
|
dimension.
|
Intuitively the hotness level of a dimension is a function of how
|
Intuitively the hotness level of a dimension is a function of how
|
many times it was the most frequently accessed dimension in the
|
many times it was the most frequently accessed dimension in the
|
highly executed access sites of this matrix.
|
highly executed access sites of this matrix.
|
|
|
As computed by following equation:
|
As computed by following equation:
|
m n
|
m n
|
__ __
|
__ __
|
\ \ dim_hot_level[i] +=
|
\ \ dim_hot_level[i] +=
|
/_ /_
|
/_ /_
|
j i
|
j i
|
acc[j]->dim[i]->iter_by_inner_loop * count(j)
|
acc[j]->dim[i]->iter_by_inner_loop * count(j)
|
|
|
Where n is the number of dims and m is the number of the matrix
|
Where n is the number of dims and m is the number of the matrix
|
access sites. acc[j]->dim[i]->iter_by_inner_loop is 1 if acc[j]
|
access sites. acc[j]->dim[i]->iter_by_inner_loop is 1 if acc[j]
|
iterates over dim[i] in innermost loop, and is 0 otherwise.
|
iterates over dim[i] in innermost loop, and is 0 otherwise.
|
|
|
The organization of the new matrix should be according to the
|
The organization of the new matrix should be according to the
|
hotness of each dimension. The hotness of the dimension implies
|
hotness of each dimension. The hotness of the dimension implies
|
the locality of the elements.*/
|
the locality of the elements.*/
|
static int
|
static int
|
analyze_transpose (void **slot, void *data ATTRIBUTE_UNUSED)
|
analyze_transpose (void **slot, void *data ATTRIBUTE_UNUSED)
|
{
|
{
|
struct matrix_info *mi = (struct matrix_info *) *slot;
|
struct matrix_info *mi = (struct matrix_info *) *slot;
|
int min_escape_l = mi->min_indirect_level_escape;
|
int min_escape_l = mi->min_indirect_level_escape;
|
struct loop *loop;
|
struct loop *loop;
|
affine_iv iv;
|
affine_iv iv;
|
struct access_site_info *acc_info;
|
struct access_site_info *acc_info;
|
int i;
|
int i;
|
|
|
if (min_escape_l < 2 || !mi->access_l)
|
if (min_escape_l < 2 || !mi->access_l)
|
{
|
{
|
if (mi->access_l)
|
if (mi->access_l)
|
{
|
{
|
FOR_EACH_VEC_ELT (access_site_info_p, mi->access_l, i, acc_info)
|
FOR_EACH_VEC_ELT (access_site_info_p, mi->access_l, i, acc_info)
|
free (acc_info);
|
free (acc_info);
|
VEC_free (access_site_info_p, heap, mi->access_l);
|
VEC_free (access_site_info_p, heap, mi->access_l);
|
|
|
}
|
}
|
return 1;
|
return 1;
|
}
|
}
|
if (!mi->dim_hot_level)
|
if (!mi->dim_hot_level)
|
mi->dim_hot_level =
|
mi->dim_hot_level =
|
(gcov_type *) xcalloc (min_escape_l, sizeof (gcov_type));
|
(gcov_type *) xcalloc (min_escape_l, sizeof (gcov_type));
|
|
|
|
|
for (i = 0; VEC_iterate (access_site_info_p, mi->access_l, i, acc_info);
|
for (i = 0; VEC_iterate (access_site_info_p, mi->access_l, i, acc_info);
|
i++)
|
i++)
|
{
|
{
|
if (gimple_assign_rhs_code (acc_info->stmt) == POINTER_PLUS_EXPR
|
if (gimple_assign_rhs_code (acc_info->stmt) == POINTER_PLUS_EXPR
|
&& acc_info->level < min_escape_l)
|
&& acc_info->level < min_escape_l)
|
{
|
{
|
loop = loop_containing_stmt (acc_info->stmt);
|
loop = loop_containing_stmt (acc_info->stmt);
|
if (!loop || loop->inner)
|
if (!loop || loop->inner)
|
{
|
{
|
free (acc_info);
|
free (acc_info);
|
continue;
|
continue;
|
}
|
}
|
if (simple_iv (loop, loop, acc_info->offset, &iv, true))
|
if (simple_iv (loop, loop, acc_info->offset, &iv, true))
|
{
|
{
|
if (iv.step != NULL)
|
if (iv.step != NULL)
|
{
|
{
|
HOST_WIDE_INT istep;
|
HOST_WIDE_INT istep;
|
|
|
istep = int_cst_value (iv.step);
|
istep = int_cst_value (iv.step);
|
if (istep != 0)
|
if (istep != 0)
|
{
|
{
|
acc_info->iterated_by_inner_most_loop_p = 1;
|
acc_info->iterated_by_inner_most_loop_p = 1;
|
mi->dim_hot_level[acc_info->level] +=
|
mi->dim_hot_level[acc_info->level] +=
|
gimple_bb (acc_info->stmt)->count;
|
gimple_bb (acc_info->stmt)->count;
|
}
|
}
|
|
|
}
|
}
|
}
|
}
|
}
|
}
|
free (acc_info);
|
free (acc_info);
|
}
|
}
|
VEC_free (access_site_info_p, heap, mi->access_l);
|
VEC_free (access_site_info_p, heap, mi->access_l);
|
|
|
return 1;
|
return 1;
|
}
|
}
|
|
|
/* Find the index which defines the OFFSET from base.
|
/* Find the index which defines the OFFSET from base.
|
We walk from use to def until we find how the offset was defined. */
|
We walk from use to def until we find how the offset was defined. */
|
static tree
|
static tree
|
get_index_from_offset (tree offset, gimple def_stmt)
|
get_index_from_offset (tree offset, gimple def_stmt)
|
{
|
{
|
tree op1, op2, index;
|
tree op1, op2, index;
|
|
|
if (gimple_code (def_stmt) == GIMPLE_PHI)
|
if (gimple_code (def_stmt) == GIMPLE_PHI)
|
return NULL;
|
return NULL;
|
if ((gimple_assign_copy_p (def_stmt) || gimple_assign_cast_p (def_stmt))
|
if ((gimple_assign_copy_p (def_stmt) || gimple_assign_cast_p (def_stmt))
|
&& TREE_CODE (gimple_assign_rhs1 (def_stmt)) == SSA_NAME)
|
&& TREE_CODE (gimple_assign_rhs1 (def_stmt)) == SSA_NAME)
|
return get_index_from_offset (offset,
|
return get_index_from_offset (offset,
|
SSA_NAME_DEF_STMT (gimple_assign_rhs1 (def_stmt)));
|
SSA_NAME_DEF_STMT (gimple_assign_rhs1 (def_stmt)));
|
else if (is_gimple_assign (def_stmt)
|
else if (is_gimple_assign (def_stmt)
|
&& gimple_assign_rhs_code (def_stmt) == MULT_EXPR)
|
&& gimple_assign_rhs_code (def_stmt) == MULT_EXPR)
|
{
|
{
|
op1 = gimple_assign_rhs1 (def_stmt);
|
op1 = gimple_assign_rhs1 (def_stmt);
|
op2 = gimple_assign_rhs2 (def_stmt);
|
op2 = gimple_assign_rhs2 (def_stmt);
|
if (TREE_CODE (op1) != INTEGER_CST && TREE_CODE (op2) != INTEGER_CST)
|
if (TREE_CODE (op1) != INTEGER_CST && TREE_CODE (op2) != INTEGER_CST)
|
return NULL;
|
return NULL;
|
index = (TREE_CODE (op1) == INTEGER_CST) ? op2 : op1;
|
index = (TREE_CODE (op1) == INTEGER_CST) ? op2 : op1;
|
return index;
|
return index;
|
}
|
}
|
else
|
else
|
return NULL_TREE;
|
return NULL_TREE;
|
}
|
}
|
|
|
/* update MI->dimension_type_size[CURRENT_INDIRECT_LEVEL] with the size
|
/* update MI->dimension_type_size[CURRENT_INDIRECT_LEVEL] with the size
|
of the type related to the SSA_VAR, or the type related to the
|
of the type related to the SSA_VAR, or the type related to the
|
lhs of STMT, in the case that it is an MEM_REF. */
|
lhs of STMT, in the case that it is an MEM_REF. */
|
static void
|
static void
|
update_type_size (struct matrix_info *mi, gimple stmt, tree ssa_var,
|
update_type_size (struct matrix_info *mi, gimple stmt, tree ssa_var,
|
int current_indirect_level)
|
int current_indirect_level)
|
{
|
{
|
tree lhs;
|
tree lhs;
|
HOST_WIDE_INT type_size;
|
HOST_WIDE_INT type_size;
|
|
|
/* Update type according to the type of the MEM_REF expr. */
|
/* Update type according to the type of the MEM_REF expr. */
|
if (is_gimple_assign (stmt)
|
if (is_gimple_assign (stmt)
|
&& TREE_CODE (gimple_assign_lhs (stmt)) == MEM_REF)
|
&& TREE_CODE (gimple_assign_lhs (stmt)) == MEM_REF)
|
{
|
{
|
lhs = gimple_assign_lhs (stmt);
|
lhs = gimple_assign_lhs (stmt);
|
gcc_assert (POINTER_TYPE_P
|
gcc_assert (POINTER_TYPE_P
|
(TREE_TYPE (SSA_NAME_VAR (TREE_OPERAND (lhs, 0)))));
|
(TREE_TYPE (SSA_NAME_VAR (TREE_OPERAND (lhs, 0)))));
|
type_size =
|
type_size =
|
int_size_in_bytes (TREE_TYPE
|
int_size_in_bytes (TREE_TYPE
|
(TREE_TYPE
|
(TREE_TYPE
|
(SSA_NAME_VAR (TREE_OPERAND (lhs, 0)))));
|
(SSA_NAME_VAR (TREE_OPERAND (lhs, 0)))));
|
}
|
}
|
else
|
else
|
type_size = int_size_in_bytes (TREE_TYPE (ssa_var));
|
type_size = int_size_in_bytes (TREE_TYPE (ssa_var));
|
|
|
/* Record the size of elements accessed (as a whole)
|
/* Record the size of elements accessed (as a whole)
|
in the current indirection level (dimension). If the size of
|
in the current indirection level (dimension). If the size of
|
elements is not known at compile time, mark it as escaping. */
|
elements is not known at compile time, mark it as escaping. */
|
if (type_size <= 0)
|
if (type_size <= 0)
|
mark_min_matrix_escape_level (mi, current_indirect_level, stmt);
|
mark_min_matrix_escape_level (mi, current_indirect_level, stmt);
|
else
|
else
|
{
|
{
|
int l = current_indirect_level;
|
int l = current_indirect_level;
|
|
|
if (!mi->dimension_type_size)
|
if (!mi->dimension_type_size)
|
{
|
{
|
mi->dimension_type_size
|
mi->dimension_type_size
|
= (HOST_WIDE_INT *) xcalloc (l + 1, sizeof (HOST_WIDE_INT));
|
= (HOST_WIDE_INT *) xcalloc (l + 1, sizeof (HOST_WIDE_INT));
|
mi->dimension_type_size_len = l + 1;
|
mi->dimension_type_size_len = l + 1;
|
}
|
}
|
else if (mi->dimension_type_size_len < l + 1)
|
else if (mi->dimension_type_size_len < l + 1)
|
{
|
{
|
mi->dimension_type_size
|
mi->dimension_type_size
|
= (HOST_WIDE_INT *) xrealloc (mi->dimension_type_size,
|
= (HOST_WIDE_INT *) xrealloc (mi->dimension_type_size,
|
(l + 1) * sizeof (HOST_WIDE_INT));
|
(l + 1) * sizeof (HOST_WIDE_INT));
|
memset (&mi->dimension_type_size[mi->dimension_type_size_len],
|
memset (&mi->dimension_type_size[mi->dimension_type_size_len],
|
0, (l + 1 - mi->dimension_type_size_len)
|
0, (l + 1 - mi->dimension_type_size_len)
|
* sizeof (HOST_WIDE_INT));
|
* sizeof (HOST_WIDE_INT));
|
mi->dimension_type_size_len = l + 1;
|
mi->dimension_type_size_len = l + 1;
|
}
|
}
|
/* Make sure all the accesses in the same level have the same size
|
/* Make sure all the accesses in the same level have the same size
|
of the type. */
|
of the type. */
|
if (!mi->dimension_type_size[l])
|
if (!mi->dimension_type_size[l])
|
mi->dimension_type_size[l] = type_size;
|
mi->dimension_type_size[l] = type_size;
|
else if (mi->dimension_type_size[l] != type_size)
|
else if (mi->dimension_type_size[l] != type_size)
|
mark_min_matrix_escape_level (mi, l, stmt);
|
mark_min_matrix_escape_level (mi, l, stmt);
|
}
|
}
|
}
|
}
|
|
|
/* USE_STMT represents a GIMPLE_CALL, where one of the arguments is the
|
/* USE_STMT represents a GIMPLE_CALL, where one of the arguments is the
|
ssa var that we want to check because it came from some use of matrix
|
ssa var that we want to check because it came from some use of matrix
|
MI. CURRENT_INDIRECT_LEVEL is the indirection level we reached so
|
MI. CURRENT_INDIRECT_LEVEL is the indirection level we reached so
|
far. */
|
far. */
|
|
|
static int
|
static int
|
analyze_accesses_for_call_stmt (struct matrix_info *mi, tree ssa_var,
|
analyze_accesses_for_call_stmt (struct matrix_info *mi, tree ssa_var,
|
gimple use_stmt, int current_indirect_level)
|
gimple use_stmt, int current_indirect_level)
|
{
|
{
|
tree fndecl = gimple_call_fndecl (use_stmt);
|
tree fndecl = gimple_call_fndecl (use_stmt);
|
|
|
if (gimple_call_lhs (use_stmt))
|
if (gimple_call_lhs (use_stmt))
|
{
|
{
|
tree lhs = gimple_call_lhs (use_stmt);
|
tree lhs = gimple_call_lhs (use_stmt);
|
struct ssa_acc_in_tree lhs_acc, rhs_acc;
|
struct ssa_acc_in_tree lhs_acc, rhs_acc;
|
|
|
memset (&lhs_acc, 0, sizeof (lhs_acc));
|
memset (&lhs_acc, 0, sizeof (lhs_acc));
|
memset (&rhs_acc, 0, sizeof (rhs_acc));
|
memset (&rhs_acc, 0, sizeof (rhs_acc));
|
|
|
lhs_acc.ssa_var = ssa_var;
|
lhs_acc.ssa_var = ssa_var;
|
lhs_acc.t_code = ERROR_MARK;
|
lhs_acc.t_code = ERROR_MARK;
|
ssa_accessed_in_tree (lhs, &lhs_acc);
|
ssa_accessed_in_tree (lhs, &lhs_acc);
|
rhs_acc.ssa_var = ssa_var;
|
rhs_acc.ssa_var = ssa_var;
|
rhs_acc.t_code = ERROR_MARK;
|
rhs_acc.t_code = ERROR_MARK;
|
ssa_accessed_in_call_rhs (use_stmt, &rhs_acc);
|
ssa_accessed_in_call_rhs (use_stmt, &rhs_acc);
|
|
|
/* The SSA must be either in the left side or in the right side,
|
/* The SSA must be either in the left side or in the right side,
|
to understand what is happening.
|
to understand what is happening.
|
In case the SSA_NAME is found in both sides we should be escaping
|
In case the SSA_NAME is found in both sides we should be escaping
|
at this level because in this case we cannot calculate the
|
at this level because in this case we cannot calculate the
|
address correctly. */
|
address correctly. */
|
if ((lhs_acc.var_found && rhs_acc.var_found
|
if ((lhs_acc.var_found && rhs_acc.var_found
|
&& lhs_acc.t_code == MEM_REF)
|
&& lhs_acc.t_code == MEM_REF)
|
|| (!rhs_acc.var_found && !lhs_acc.var_found))
|
|| (!rhs_acc.var_found && !lhs_acc.var_found))
|
{
|
{
|
mark_min_matrix_escape_level (mi, current_indirect_level, use_stmt);
|
mark_min_matrix_escape_level (mi, current_indirect_level, use_stmt);
|
return current_indirect_level;
|
return current_indirect_level;
|
}
|
}
|
gcc_assert (!rhs_acc.var_found || !lhs_acc.var_found);
|
gcc_assert (!rhs_acc.var_found || !lhs_acc.var_found);
|
|
|
/* If we are storing to the matrix at some level, then mark it as
|
/* If we are storing to the matrix at some level, then mark it as
|
escaping at that level. */
|
escaping at that level. */
|
if (lhs_acc.var_found)
|
if (lhs_acc.var_found)
|
{
|
{
|
int l = current_indirect_level + 1;
|
int l = current_indirect_level + 1;
|
|
|
gcc_assert (lhs_acc.t_code == MEM_REF);
|
gcc_assert (lhs_acc.t_code == MEM_REF);
|
mark_min_matrix_escape_level (mi, l, use_stmt);
|
mark_min_matrix_escape_level (mi, l, use_stmt);
|
return current_indirect_level;
|
return current_indirect_level;
|
}
|
}
|
}
|
}
|
|
|
if (fndecl)
|
if (fndecl)
|
{
|
{
|
if (DECL_FUNCTION_CODE (fndecl) != BUILT_IN_FREE)
|
if (DECL_FUNCTION_CODE (fndecl) != BUILT_IN_FREE)
|
{
|
{
|
if (dump_file)
|
if (dump_file)
|
fprintf (dump_file,
|
fprintf (dump_file,
|
"Matrix %s: Function call %s, level %d escapes.\n",
|
"Matrix %s: Function call %s, level %d escapes.\n",
|
get_name (mi->decl), get_name (fndecl),
|
get_name (mi->decl), get_name (fndecl),
|
current_indirect_level);
|
current_indirect_level);
|
mark_min_matrix_escape_level (mi, current_indirect_level, use_stmt);
|
mark_min_matrix_escape_level (mi, current_indirect_level, use_stmt);
|
}
|
}
|
else if (mi->free_stmts[current_indirect_level].stmt != NULL
|
else if (mi->free_stmts[current_indirect_level].stmt != NULL
|
&& mi->free_stmts[current_indirect_level].stmt != use_stmt)
|
&& mi->free_stmts[current_indirect_level].stmt != use_stmt)
|
mark_min_matrix_escape_level (mi, current_indirect_level, use_stmt);
|
mark_min_matrix_escape_level (mi, current_indirect_level, use_stmt);
|
else
|
else
|
{
|
{
|
/*Record the free statements so we can delete them
|
/*Record the free statements so we can delete them
|
later. */
|
later. */
|
int l = current_indirect_level;
|
int l = current_indirect_level;
|
|
|
mi->free_stmts[l].stmt = use_stmt;
|
mi->free_stmts[l].stmt = use_stmt;
|
mi->free_stmts[l].func = current_function_decl;
|
mi->free_stmts[l].func = current_function_decl;
|
}
|
}
|
}
|
}
|
return current_indirect_level;
|
return current_indirect_level;
|
}
|
}
|
|
|
/* USE_STMT represents a phi node of the ssa var that we want to
|
/* USE_STMT represents a phi node of the ssa var that we want to
|
check because it came from some use of matrix
|
check because it came from some use of matrix
|
MI.
|
MI.
|
We check all the escaping levels that get to the PHI node
|
We check all the escaping levels that get to the PHI node
|
and make sure they are all the same escaping;
|
and make sure they are all the same escaping;
|
if not (which is rare) we let the escaping level be the
|
if not (which is rare) we let the escaping level be the
|
minimum level that gets into that PHI because starting from
|
minimum level that gets into that PHI because starting from
|
that level we cannot expect the behavior of the indirections.
|
that level we cannot expect the behavior of the indirections.
|
CURRENT_INDIRECT_LEVEL is the indirection level we reached so far. */
|
CURRENT_INDIRECT_LEVEL is the indirection level we reached so far. */
|
|
|
static void
|
static void
|
analyze_accesses_for_phi_node (struct matrix_info *mi, gimple use_stmt,
|
analyze_accesses_for_phi_node (struct matrix_info *mi, gimple use_stmt,
|
int current_indirect_level, sbitmap visited,
|
int current_indirect_level, sbitmap visited,
|
bool record_accesses)
|
bool record_accesses)
|
{
|
{
|
|
|
struct matrix_access_phi_node tmp_maphi, *maphi, **pmaphi;
|
struct matrix_access_phi_node tmp_maphi, *maphi, **pmaphi;
|
|
|
tmp_maphi.phi = use_stmt;
|
tmp_maphi.phi = use_stmt;
|
if ((maphi = (struct matrix_access_phi_node *)
|
if ((maphi = (struct matrix_access_phi_node *)
|
htab_find (htab_mat_acc_phi_nodes, &tmp_maphi)))
|
htab_find (htab_mat_acc_phi_nodes, &tmp_maphi)))
|
{
|
{
|
if (maphi->indirection_level == current_indirect_level)
|
if (maphi->indirection_level == current_indirect_level)
|
return;
|
return;
|
else
|
else
|
{
|
{
|
int level = MIN (maphi->indirection_level,
|
int level = MIN (maphi->indirection_level,
|
current_indirect_level);
|
current_indirect_level);
|
size_t j;
|
size_t j;
|
gimple stmt = NULL;
|
gimple stmt = NULL;
|
|
|
maphi->indirection_level = level;
|
maphi->indirection_level = level;
|
for (j = 0; j < gimple_phi_num_args (use_stmt); j++)
|
for (j = 0; j < gimple_phi_num_args (use_stmt); j++)
|
{
|
{
|
tree def = PHI_ARG_DEF (use_stmt, j);
|
tree def = PHI_ARG_DEF (use_stmt, j);
|
|
|
if (gimple_code (SSA_NAME_DEF_STMT (def)) != GIMPLE_PHI)
|
if (gimple_code (SSA_NAME_DEF_STMT (def)) != GIMPLE_PHI)
|
stmt = SSA_NAME_DEF_STMT (def);
|
stmt = SSA_NAME_DEF_STMT (def);
|
}
|
}
|
mark_min_matrix_escape_level (mi, level, stmt);
|
mark_min_matrix_escape_level (mi, level, stmt);
|
}
|
}
|
return;
|
return;
|
}
|
}
|
maphi = (struct matrix_access_phi_node *)
|
maphi = (struct matrix_access_phi_node *)
|
xcalloc (1, sizeof (struct matrix_access_phi_node));
|
xcalloc (1, sizeof (struct matrix_access_phi_node));
|
maphi->phi = use_stmt;
|
maphi->phi = use_stmt;
|
maphi->indirection_level = current_indirect_level;
|
maphi->indirection_level = current_indirect_level;
|
|
|
/* Insert to hash table. */
|
/* Insert to hash table. */
|
pmaphi = (struct matrix_access_phi_node **)
|
pmaphi = (struct matrix_access_phi_node **)
|
htab_find_slot (htab_mat_acc_phi_nodes, maphi, INSERT);
|
htab_find_slot (htab_mat_acc_phi_nodes, maphi, INSERT);
|
gcc_assert (pmaphi);
|
gcc_assert (pmaphi);
|
*pmaphi = maphi;
|
*pmaphi = maphi;
|
|
|
if (!TEST_BIT (visited, SSA_NAME_VERSION (PHI_RESULT (use_stmt))))
|
if (!TEST_BIT (visited, SSA_NAME_VERSION (PHI_RESULT (use_stmt))))
|
{
|
{
|
SET_BIT (visited, SSA_NAME_VERSION (PHI_RESULT (use_stmt)));
|
SET_BIT (visited, SSA_NAME_VERSION (PHI_RESULT (use_stmt)));
|
analyze_matrix_accesses (mi, PHI_RESULT (use_stmt),
|
analyze_matrix_accesses (mi, PHI_RESULT (use_stmt),
|
current_indirect_level, false, visited,
|
current_indirect_level, false, visited,
|
record_accesses);
|
record_accesses);
|
RESET_BIT (visited, SSA_NAME_VERSION (PHI_RESULT (use_stmt)));
|
RESET_BIT (visited, SSA_NAME_VERSION (PHI_RESULT (use_stmt)));
|
}
|
}
|
}
|
}
|
|
|
/* USE_STMT represents an assign statement (the rhs or lhs include
|
/* USE_STMT represents an assign statement (the rhs or lhs include
|
the ssa var that we want to check because it came from some use of matrix
|
the ssa var that we want to check because it came from some use of matrix
|
MI. CURRENT_INDIRECT_LEVEL is the indirection level we reached so far. */
|
MI. CURRENT_INDIRECT_LEVEL is the indirection level we reached so far. */
|
|
|
static int
|
static int
|
analyze_accesses_for_assign_stmt (struct matrix_info *mi, tree ssa_var,
|
analyze_accesses_for_assign_stmt (struct matrix_info *mi, tree ssa_var,
|
gimple use_stmt, int current_indirect_level,
|
gimple use_stmt, int current_indirect_level,
|
bool last_op, sbitmap visited,
|
bool last_op, sbitmap visited,
|
bool record_accesses)
|
bool record_accesses)
|
{
|
{
|
tree lhs = gimple_get_lhs (use_stmt);
|
tree lhs = gimple_get_lhs (use_stmt);
|
struct ssa_acc_in_tree lhs_acc, rhs_acc;
|
struct ssa_acc_in_tree lhs_acc, rhs_acc;
|
|
|
memset (&lhs_acc, 0, sizeof (lhs_acc));
|
memset (&lhs_acc, 0, sizeof (lhs_acc));
|
memset (&rhs_acc, 0, sizeof (rhs_acc));
|
memset (&rhs_acc, 0, sizeof (rhs_acc));
|
|
|
lhs_acc.ssa_var = ssa_var;
|
lhs_acc.ssa_var = ssa_var;
|
lhs_acc.t_code = ERROR_MARK;
|
lhs_acc.t_code = ERROR_MARK;
|
ssa_accessed_in_tree (lhs, &lhs_acc);
|
ssa_accessed_in_tree (lhs, &lhs_acc);
|
rhs_acc.ssa_var = ssa_var;
|
rhs_acc.ssa_var = ssa_var;
|
rhs_acc.t_code = ERROR_MARK;
|
rhs_acc.t_code = ERROR_MARK;
|
ssa_accessed_in_assign_rhs (use_stmt, &rhs_acc);
|
ssa_accessed_in_assign_rhs (use_stmt, &rhs_acc);
|
|
|
/* The SSA must be either in the left side or in the right side,
|
/* The SSA must be either in the left side or in the right side,
|
to understand what is happening.
|
to understand what is happening.
|
In case the SSA_NAME is found in both sides we should be escaping
|
In case the SSA_NAME is found in both sides we should be escaping
|
at this level because in this case we cannot calculate the
|
at this level because in this case we cannot calculate the
|
address correctly. */
|
address correctly. */
|
if ((lhs_acc.var_found && rhs_acc.var_found
|
if ((lhs_acc.var_found && rhs_acc.var_found
|
&& lhs_acc.t_code == MEM_REF)
|
&& lhs_acc.t_code == MEM_REF)
|
|| (!rhs_acc.var_found && !lhs_acc.var_found))
|
|| (!rhs_acc.var_found && !lhs_acc.var_found))
|
{
|
{
|
mark_min_matrix_escape_level (mi, current_indirect_level, use_stmt);
|
mark_min_matrix_escape_level (mi, current_indirect_level, use_stmt);
|
return current_indirect_level;
|
return current_indirect_level;
|
}
|
}
|
gcc_assert (!rhs_acc.var_found || !lhs_acc.var_found);
|
gcc_assert (!rhs_acc.var_found || !lhs_acc.var_found);
|
|
|
/* If we are storing to the matrix at some level, then mark it as
|
/* If we are storing to the matrix at some level, then mark it as
|
escaping at that level. */
|
escaping at that level. */
|
if (lhs_acc.var_found)
|
if (lhs_acc.var_found)
|
{
|
{
|
int l = current_indirect_level + 1;
|
int l = current_indirect_level + 1;
|
|
|
gcc_assert (lhs_acc.t_code == MEM_REF);
|
gcc_assert (lhs_acc.t_code == MEM_REF);
|
|
|
if (!(gimple_assign_copy_p (use_stmt)
|
if (!(gimple_assign_copy_p (use_stmt)
|
|| gimple_assign_cast_p (use_stmt))
|
|| gimple_assign_cast_p (use_stmt))
|
|| (TREE_CODE (gimple_assign_rhs1 (use_stmt)) != SSA_NAME))
|
|| (TREE_CODE (gimple_assign_rhs1 (use_stmt)) != SSA_NAME))
|
mark_min_matrix_escape_level (mi, l, use_stmt);
|
mark_min_matrix_escape_level (mi, l, use_stmt);
|
else
|
else
|
{
|
{
|
gimple def_stmt = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (use_stmt));
|
gimple def_stmt = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (use_stmt));
|
analyze_matrix_allocation_site (mi, def_stmt, l, visited);
|
analyze_matrix_allocation_site (mi, def_stmt, l, visited);
|
if (record_accesses)
|
if (record_accesses)
|
record_access_alloc_site_info (mi, use_stmt, NULL_TREE,
|
record_access_alloc_site_info (mi, use_stmt, NULL_TREE,
|
NULL_TREE, l, true);
|
NULL_TREE, l, true);
|
update_type_size (mi, use_stmt, NULL, l);
|
update_type_size (mi, use_stmt, NULL, l);
|
}
|
}
|
return current_indirect_level;
|
return current_indirect_level;
|
}
|
}
|
/* Now, check the right-hand-side, to see how the SSA variable
|
/* Now, check the right-hand-side, to see how the SSA variable
|
is used. */
|
is used. */
|
if (rhs_acc.var_found)
|
if (rhs_acc.var_found)
|
{
|
{
|
if (rhs_acc.t_code != MEM_REF
|
if (rhs_acc.t_code != MEM_REF
|
&& rhs_acc.t_code != POINTER_PLUS_EXPR && rhs_acc.t_code != SSA_NAME)
|
&& rhs_acc.t_code != POINTER_PLUS_EXPR && rhs_acc.t_code != SSA_NAME)
|
{
|
{
|
mark_min_matrix_escape_level (mi, current_indirect_level, use_stmt);
|
mark_min_matrix_escape_level (mi, current_indirect_level, use_stmt);
|
return current_indirect_level;
|
return current_indirect_level;
|
}
|
}
|
/* If the access in the RHS has an indirection increase the
|
/* If the access in the RHS has an indirection increase the
|
indirection level. */
|
indirection level. */
|
if (rhs_acc.t_code == MEM_REF)
|
if (rhs_acc.t_code == MEM_REF)
|
{
|
{
|
if (record_accesses)
|
if (record_accesses)
|
record_access_alloc_site_info (mi, use_stmt, NULL_TREE,
|
record_access_alloc_site_info (mi, use_stmt, NULL_TREE,
|
NULL_TREE,
|
NULL_TREE,
|
current_indirect_level, true);
|
current_indirect_level, true);
|
current_indirect_level += 1;
|
current_indirect_level += 1;
|
}
|
}
|
else if (rhs_acc.t_code == POINTER_PLUS_EXPR)
|
else if (rhs_acc.t_code == POINTER_PLUS_EXPR)
|
{
|
{
|
gcc_assert (rhs_acc.second_op);
|
gcc_assert (rhs_acc.second_op);
|
if (last_op)
|
if (last_op)
|
/* Currently we support only one PLUS expression on the
|
/* Currently we support only one PLUS expression on the
|
SSA_NAME that holds the base address of the current
|
SSA_NAME that holds the base address of the current
|
indirection level; to support more general case there
|
indirection level; to support more general case there
|
is a need to hold a stack of expressions and regenerate
|
is a need to hold a stack of expressions and regenerate
|
the calculation later. */
|
the calculation later. */
|
mark_min_matrix_escape_level (mi, current_indirect_level,
|
mark_min_matrix_escape_level (mi, current_indirect_level,
|
use_stmt);
|
use_stmt);
|
else
|
else
|
{
|
{
|
tree index;
|
tree index;
|
tree op1, op2;
|
tree op1, op2;
|
|
|
op1 = gimple_assign_rhs1 (use_stmt);
|
op1 = gimple_assign_rhs1 (use_stmt);
|
op2 = gimple_assign_rhs2 (use_stmt);
|
op2 = gimple_assign_rhs2 (use_stmt);
|
|
|
op2 = (op1 == ssa_var) ? op2 : op1;
|
op2 = (op1 == ssa_var) ? op2 : op1;
|
if (TREE_CODE (op2) == INTEGER_CST)
|
if (TREE_CODE (op2) == INTEGER_CST)
|
index =
|
index =
|
build_int_cst (TREE_TYPE (op1),
|
build_int_cst (TREE_TYPE (op1),
|
TREE_INT_CST_LOW (op2) /
|
TREE_INT_CST_LOW (op2) /
|
int_size_in_bytes (TREE_TYPE (op1)));
|
int_size_in_bytes (TREE_TYPE (op1)));
|
else
|
else
|
{
|
{
|
index =
|
index =
|
get_index_from_offset (op2, SSA_NAME_DEF_STMT (op2));
|
get_index_from_offset (op2, SSA_NAME_DEF_STMT (op2));
|
if (index == NULL_TREE)
|
if (index == NULL_TREE)
|
{
|
{
|
mark_min_matrix_escape_level (mi,
|
mark_min_matrix_escape_level (mi,
|
current_indirect_level,
|
current_indirect_level,
|
use_stmt);
|
use_stmt);
|
return current_indirect_level;
|
return current_indirect_level;
|
}
|
}
|
}
|
}
|
if (record_accesses)
|
if (record_accesses)
|
record_access_alloc_site_info (mi, use_stmt, op2,
|
record_access_alloc_site_info (mi, use_stmt, op2,
|
index,
|
index,
|
current_indirect_level, false);
|
current_indirect_level, false);
|
}
|
}
|
}
|
}
|
/* If we are storing this level of indirection mark it as
|
/* If we are storing this level of indirection mark it as
|
escaping. */
|
escaping. */
|
if (lhs_acc.t_code == MEM_REF || TREE_CODE (lhs) != SSA_NAME)
|
if (lhs_acc.t_code == MEM_REF || TREE_CODE (lhs) != SSA_NAME)
|
{
|
{
|
int l = current_indirect_level;
|
int l = current_indirect_level;
|
|
|
/* One exception is when we are storing to the matrix
|
/* One exception is when we are storing to the matrix
|
variable itself; this is the case of malloc, we must make
|
variable itself; this is the case of malloc, we must make
|
sure that it's the one and only one call to malloc so
|
sure that it's the one and only one call to malloc so
|
we call analyze_matrix_allocation_site to check
|
we call analyze_matrix_allocation_site to check
|
this out. */
|
this out. */
|
if (TREE_CODE (lhs) != VAR_DECL || lhs != mi->decl)
|
if (TREE_CODE (lhs) != VAR_DECL || lhs != mi->decl)
|
mark_min_matrix_escape_level (mi, current_indirect_level,
|
mark_min_matrix_escape_level (mi, current_indirect_level,
|
use_stmt);
|
use_stmt);
|
else
|
else
|
{
|
{
|
/* Also update the escaping level. */
|
/* Also update the escaping level. */
|
analyze_matrix_allocation_site (mi, use_stmt, l, visited);
|
analyze_matrix_allocation_site (mi, use_stmt, l, visited);
|
if (record_accesses)
|
if (record_accesses)
|
record_access_alloc_site_info (mi, use_stmt, NULL_TREE,
|
record_access_alloc_site_info (mi, use_stmt, NULL_TREE,
|
NULL_TREE, l, true);
|
NULL_TREE, l, true);
|
}
|
}
|
}
|
}
|
else
|
else
|
{
|
{
|
/* We are placing it in an SSA, follow that SSA. */
|
/* We are placing it in an SSA, follow that SSA. */
|
analyze_matrix_accesses (mi, lhs,
|
analyze_matrix_accesses (mi, lhs,
|
current_indirect_level,
|
current_indirect_level,
|
rhs_acc.t_code == POINTER_PLUS_EXPR,
|
rhs_acc.t_code == POINTER_PLUS_EXPR,
|
visited, record_accesses);
|
visited, record_accesses);
|
}
|
}
|
}
|
}
|
return current_indirect_level;
|
return current_indirect_level;
|
}
|
}
|
|
|
/* Given a SSA_VAR (coming from a use statement of the matrix MI),
|
/* Given a SSA_VAR (coming from a use statement of the matrix MI),
|
follow its uses and level of indirection and find out the minimum
|
follow its uses and level of indirection and find out the minimum
|
indirection level it escapes in (the highest dimension) and the maximum
|
indirection level it escapes in (the highest dimension) and the maximum
|
level it is accessed in (this will be the actual dimension of the
|
level it is accessed in (this will be the actual dimension of the
|
matrix). The information is accumulated in MI.
|
matrix). The information is accumulated in MI.
|
We look at the immediate uses, if one escapes we finish; if not,
|
We look at the immediate uses, if one escapes we finish; if not,
|
we make a recursive call for each one of the immediate uses of the
|
we make a recursive call for each one of the immediate uses of the
|
resulting SSA name. */
|
resulting SSA name. */
|
static void
|
static void
|
analyze_matrix_accesses (struct matrix_info *mi, tree ssa_var,
|
analyze_matrix_accesses (struct matrix_info *mi, tree ssa_var,
|
int current_indirect_level, bool last_op,
|
int current_indirect_level, bool last_op,
|
sbitmap visited, bool record_accesses)
|
sbitmap visited, bool record_accesses)
|
{
|
{
|
imm_use_iterator imm_iter;
|
imm_use_iterator imm_iter;
|
use_operand_p use_p;
|
use_operand_p use_p;
|
|
|
update_type_size (mi, SSA_NAME_DEF_STMT (ssa_var), ssa_var,
|
update_type_size (mi, SSA_NAME_DEF_STMT (ssa_var), ssa_var,
|
current_indirect_level);
|
current_indirect_level);
|
|
|
/* We don't go beyond the escaping level when we are performing the
|
/* We don't go beyond the escaping level when we are performing the
|
flattening. NOTE: we keep the last indirection level that doesn't
|
flattening. NOTE: we keep the last indirection level that doesn't
|
escape. */
|
escape. */
|
if (mi->min_indirect_level_escape > -1
|
if (mi->min_indirect_level_escape > -1
|
&& mi->min_indirect_level_escape <= current_indirect_level)
|
&& mi->min_indirect_level_escape <= current_indirect_level)
|
return;
|
return;
|
|
|
/* Now go over the uses of the SSA_NAME and check how it is used in
|
/* Now go over the uses of the SSA_NAME and check how it is used in
|
each one of them. We are mainly looking for the pattern MEM_REF,
|
each one of them. We are mainly looking for the pattern MEM_REF,
|
then a POINTER_PLUS_EXPR, then MEM_REF etc. while in between there could
|
then a POINTER_PLUS_EXPR, then MEM_REF etc. while in between there could
|
be any number of copies and casts. */
|
be any number of copies and casts. */
|
gcc_assert (TREE_CODE (ssa_var) == SSA_NAME);
|
gcc_assert (TREE_CODE (ssa_var) == SSA_NAME);
|
|
|
FOR_EACH_IMM_USE_FAST (use_p, imm_iter, ssa_var)
|
FOR_EACH_IMM_USE_FAST (use_p, imm_iter, ssa_var)
|
{
|
{
|
gimple use_stmt = USE_STMT (use_p);
|
gimple use_stmt = USE_STMT (use_p);
|
if (gimple_code (use_stmt) == GIMPLE_PHI)
|
if (gimple_code (use_stmt) == GIMPLE_PHI)
|
/* We check all the escaping levels that get to the PHI node
|
/* We check all the escaping levels that get to the PHI node
|
and make sure they are all the same escaping;
|
and make sure they are all the same escaping;
|
if not (which is rare) we let the escaping level be the
|
if not (which is rare) we let the escaping level be the
|
minimum level that gets into that PHI because starting from
|
minimum level that gets into that PHI because starting from
|
that level we cannot expect the behavior of the indirections. */
|
that level we cannot expect the behavior of the indirections. */
|
|
|
analyze_accesses_for_phi_node (mi, use_stmt, current_indirect_level,
|
analyze_accesses_for_phi_node (mi, use_stmt, current_indirect_level,
|
visited, record_accesses);
|
visited, record_accesses);
|
|
|
else if (is_gimple_call (use_stmt))
|
else if (is_gimple_call (use_stmt))
|
analyze_accesses_for_call_stmt (mi, ssa_var, use_stmt,
|
analyze_accesses_for_call_stmt (mi, ssa_var, use_stmt,
|
current_indirect_level);
|
current_indirect_level);
|
else if (is_gimple_assign (use_stmt))
|
else if (is_gimple_assign (use_stmt))
|
current_indirect_level =
|
current_indirect_level =
|
analyze_accesses_for_assign_stmt (mi, ssa_var, use_stmt,
|
analyze_accesses_for_assign_stmt (mi, ssa_var, use_stmt,
|
current_indirect_level, last_op,
|
current_indirect_level, last_op,
|
visited, record_accesses);
|
visited, record_accesses);
|
}
|
}
|
}
|
}
|
|
|
typedef struct
|
typedef struct
|
{
|
{
|
tree fn;
|
tree fn;
|
gimple stmt;
|
gimple stmt;
|
} check_var_data;
|
} check_var_data;
|
|
|
/* A walk_tree function to go over the VAR_DECL, PARM_DECL nodes of
|
/* A walk_tree function to go over the VAR_DECL, PARM_DECL nodes of
|
the malloc size expression and check that those aren't changed
|
the malloc size expression and check that those aren't changed
|
over the function. */
|
over the function. */
|
static tree
|
static tree
|
check_var_notmodified_p (tree * tp, int *walk_subtrees, void *data)
|
check_var_notmodified_p (tree * tp, int *walk_subtrees, void *data)
|
{
|
{
|
basic_block bb;
|
basic_block bb;
|
tree t = *tp;
|
tree t = *tp;
|
check_var_data *callback_data = (check_var_data*) data;
|
check_var_data *callback_data = (check_var_data*) data;
|
tree fn = callback_data->fn;
|
tree fn = callback_data->fn;
|
gimple_stmt_iterator gsi;
|
gimple_stmt_iterator gsi;
|
gimple stmt;
|
gimple stmt;
|
|
|
if (TREE_CODE (t) != VAR_DECL && TREE_CODE (t) != PARM_DECL)
|
if (TREE_CODE (t) != VAR_DECL && TREE_CODE (t) != PARM_DECL)
|
return NULL_TREE;
|
return NULL_TREE;
|
|
|
FOR_EACH_BB_FN (bb, DECL_STRUCT_FUNCTION (fn))
|
FOR_EACH_BB_FN (bb, DECL_STRUCT_FUNCTION (fn))
|
{
|
{
|
for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
|
for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
|
{
|
{
|
stmt = gsi_stmt (gsi);
|
stmt = gsi_stmt (gsi);
|
if (!is_gimple_assign (stmt) && !is_gimple_call (stmt))
|
if (!is_gimple_assign (stmt) && !is_gimple_call (stmt))
|
continue;
|
continue;
|
if (gimple_get_lhs (stmt) == t)
|
if (gimple_get_lhs (stmt) == t)
|
{
|
{
|
callback_data->stmt = stmt;
|
callback_data->stmt = stmt;
|
return t;
|
return t;
|
}
|
}
|
}
|
}
|
}
|
}
|
*walk_subtrees = 1;
|
*walk_subtrees = 1;
|
return NULL_TREE;
|
return NULL_TREE;
|
}
|
}
|
|
|
/* Go backwards in the use-def chains and find out the expression
|
/* Go backwards in the use-def chains and find out the expression
|
represented by the possible SSA name in STMT, until it is composed
|
represented by the possible SSA name in STMT, until it is composed
|
of only VAR_DECL, PARM_DECL and INT_CST. In case of phi nodes
|
of only VAR_DECL, PARM_DECL and INT_CST. In case of phi nodes
|
we make sure that all the arguments represent the same subexpression,
|
we make sure that all the arguments represent the same subexpression,
|
otherwise we fail. */
|
otherwise we fail. */
|
|
|
static tree
|
static tree
|
can_calculate_stmt_before_stmt (gimple stmt, sbitmap visited)
|
can_calculate_stmt_before_stmt (gimple stmt, sbitmap visited)
|
{
|
{
|
tree op1, op2, res;
|
tree op1, op2, res;
|
enum tree_code code;
|
enum tree_code code;
|
|
|
switch (gimple_code (stmt))
|
switch (gimple_code (stmt))
|
{
|
{
|
case GIMPLE_ASSIGN:
|
case GIMPLE_ASSIGN:
|
code = gimple_assign_rhs_code (stmt);
|
code = gimple_assign_rhs_code (stmt);
|
op1 = gimple_assign_rhs1 (stmt);
|
op1 = gimple_assign_rhs1 (stmt);
|
|
|
switch (code)
|
switch (code)
|
{
|
{
|
case POINTER_PLUS_EXPR:
|
case POINTER_PLUS_EXPR:
|
case PLUS_EXPR:
|
case PLUS_EXPR:
|
case MINUS_EXPR:
|
case MINUS_EXPR:
|
case MULT_EXPR:
|
case MULT_EXPR:
|
|
|
op2 = gimple_assign_rhs2 (stmt);
|
op2 = gimple_assign_rhs2 (stmt);
|
op1 = can_calculate_expr_before_stmt (op1, visited);
|
op1 = can_calculate_expr_before_stmt (op1, visited);
|
if (!op1)
|
if (!op1)
|
return NULL_TREE;
|
return NULL_TREE;
|
op2 = can_calculate_expr_before_stmt (op2, visited);
|
op2 = can_calculate_expr_before_stmt (op2, visited);
|
if (op2)
|
if (op2)
|
return fold_build2 (code, gimple_expr_type (stmt), op1, op2);
|
return fold_build2 (code, gimple_expr_type (stmt), op1, op2);
|
return NULL_TREE;
|
return NULL_TREE;
|
|
|
CASE_CONVERT:
|
CASE_CONVERT:
|
res = can_calculate_expr_before_stmt (op1, visited);
|
res = can_calculate_expr_before_stmt (op1, visited);
|
if (res != NULL_TREE)
|
if (res != NULL_TREE)
|
return build1 (code, gimple_expr_type (stmt), res);
|
return build1 (code, gimple_expr_type (stmt), res);
|
else
|
else
|
return NULL_TREE;
|
return NULL_TREE;
|
|
|
default:
|
default:
|
if (gimple_assign_single_p (stmt))
|
if (gimple_assign_single_p (stmt))
|
return can_calculate_expr_before_stmt (op1, visited);
|
return can_calculate_expr_before_stmt (op1, visited);
|
else
|
else
|
return NULL_TREE;
|
return NULL_TREE;
|
}
|
}
|
|
|
case GIMPLE_PHI:
|
case GIMPLE_PHI:
|
{
|
{
|
size_t j;
|
size_t j;
|
|
|
res = NULL_TREE;
|
res = NULL_TREE;
|
/* Make sure all the arguments represent the same value. */
|
/* Make sure all the arguments represent the same value. */
|
for (j = 0; j < gimple_phi_num_args (stmt); j++)
|
for (j = 0; j < gimple_phi_num_args (stmt); j++)
|
{
|
{
|
tree new_res;
|
tree new_res;
|
tree def = PHI_ARG_DEF (stmt, j);
|
tree def = PHI_ARG_DEF (stmt, j);
|
|
|
new_res = can_calculate_expr_before_stmt (def, visited);
|
new_res = can_calculate_expr_before_stmt (def, visited);
|
if (res == NULL_TREE)
|
if (res == NULL_TREE)
|
res = new_res;
|
res = new_res;
|
else if (!new_res || !expressions_equal_p (res, new_res))
|
else if (!new_res || !expressions_equal_p (res, new_res))
|
return NULL_TREE;
|
return NULL_TREE;
|
}
|
}
|
return res;
|
return res;
|
}
|
}
|
|
|
default:
|
default:
|
return NULL_TREE;
|
return NULL_TREE;
|
}
|
}
|
}
|
}
|
|
|
/* Go backwards in the use-def chains and find out the expression
|
/* Go backwards in the use-def chains and find out the expression
|
represented by the possible SSA name in EXPR, until it is composed
|
represented by the possible SSA name in EXPR, until it is composed
|
of only VAR_DECL, PARM_DECL and INT_CST. In case of phi nodes
|
of only VAR_DECL, PARM_DECL and INT_CST. In case of phi nodes
|
we make sure that all the arguments represent the same subexpression,
|
we make sure that all the arguments represent the same subexpression,
|
otherwise we fail. */
|
otherwise we fail. */
|
static tree
|
static tree
|
can_calculate_expr_before_stmt (tree expr, sbitmap visited)
|
can_calculate_expr_before_stmt (tree expr, sbitmap visited)
|
{
|
{
|
gimple def_stmt;
|
gimple def_stmt;
|
tree res;
|
tree res;
|
|
|
switch (TREE_CODE (expr))
|
switch (TREE_CODE (expr))
|
{
|
{
|
case SSA_NAME:
|
case SSA_NAME:
|
/* Case of loop, we don't know to represent this expression. */
|
/* Case of loop, we don't know to represent this expression. */
|
if (TEST_BIT (visited, SSA_NAME_VERSION (expr)))
|
if (TEST_BIT (visited, SSA_NAME_VERSION (expr)))
|
return NULL_TREE;
|
return NULL_TREE;
|
|
|
SET_BIT (visited, SSA_NAME_VERSION (expr));
|
SET_BIT (visited, SSA_NAME_VERSION (expr));
|
def_stmt = SSA_NAME_DEF_STMT (expr);
|
def_stmt = SSA_NAME_DEF_STMT (expr);
|
res = can_calculate_stmt_before_stmt (def_stmt, visited);
|
res = can_calculate_stmt_before_stmt (def_stmt, visited);
|
RESET_BIT (visited, SSA_NAME_VERSION (expr));
|
RESET_BIT (visited, SSA_NAME_VERSION (expr));
|
return res;
|
return res;
|
case VAR_DECL:
|
case VAR_DECL:
|
case PARM_DECL:
|
case PARM_DECL:
|
case INTEGER_CST:
|
case INTEGER_CST:
|
return expr;
|
return expr;
|
|
|
default:
|
default:
|
return NULL_TREE;
|
return NULL_TREE;
|
}
|
}
|
}
|
}
|
|
|
/* There should be only one allocation function for the dimensions
|
/* There should be only one allocation function for the dimensions
|
that don't escape. Here we check the allocation sites in this
|
that don't escape. Here we check the allocation sites in this
|
function. We must make sure that all the dimensions are allocated
|
function. We must make sure that all the dimensions are allocated
|
using malloc and that the malloc size parameter expression could be
|
using malloc and that the malloc size parameter expression could be
|
pre-calculated before the call to the malloc of dimension 0.
|
pre-calculated before the call to the malloc of dimension 0.
|
|
|
Given a candidate matrix for flattening -- MI -- check if it's
|
Given a candidate matrix for flattening -- MI -- check if it's
|
appropriate for flattening -- we analyze the allocation
|
appropriate for flattening -- we analyze the allocation
|
sites that we recorded in the previous analysis. The result of the
|
sites that we recorded in the previous analysis. The result of the
|
analysis is a level of indirection (matrix dimension) in which the
|
analysis is a level of indirection (matrix dimension) in which the
|
flattening is safe. We check the following conditions:
|
flattening is safe. We check the following conditions:
|
1. There is only one allocation site for each dimension.
|
1. There is only one allocation site for each dimension.
|
2. The allocation sites of all the dimensions are in the same
|
2. The allocation sites of all the dimensions are in the same
|
function.
|
function.
|
(The above two are being taken care of during the analysis when
|
(The above two are being taken care of during the analysis when
|
we check the allocation site).
|
we check the allocation site).
|
3. All the dimensions that we flatten are allocated at once; thus
|
3. All the dimensions that we flatten are allocated at once; thus
|
the total size must be known before the allocation of the
|
the total size must be known before the allocation of the
|
dimension 0 (top level) -- we must make sure we represent the
|
dimension 0 (top level) -- we must make sure we represent the
|
size of the allocation as an expression of global parameters or
|
size of the allocation as an expression of global parameters or
|
constants and that those doesn't change over the function. */
|
constants and that those doesn't change over the function. */
|
|
|
static int
|
static int
|
check_allocation_function (void **slot, void *data ATTRIBUTE_UNUSED)
|
check_allocation_function (void **slot, void *data ATTRIBUTE_UNUSED)
|
{
|
{
|
int level;
|
int level;
|
struct matrix_info *mi = (struct matrix_info *) *slot;
|
struct matrix_info *mi = (struct matrix_info *) *slot;
|
sbitmap visited;
|
sbitmap visited;
|
|
|
if (!mi->malloc_for_level)
|
if (!mi->malloc_for_level)
|
return 1;
|
return 1;
|
|
|
visited = sbitmap_alloc (num_ssa_names);
|
visited = sbitmap_alloc (num_ssa_names);
|
|
|
/* Do nothing if the current function is not the allocation
|
/* Do nothing if the current function is not the allocation
|
function of MI. */
|
function of MI. */
|
if (mi->allocation_function_decl != current_function_decl
|
if (mi->allocation_function_decl != current_function_decl
|
/* We aren't in the main allocation function yet. */
|
/* We aren't in the main allocation function yet. */
|
|| !mi->malloc_for_level[0])
|
|| !mi->malloc_for_level[0])
|
return 1;
|
return 1;
|
|
|
for (level = 1; level < mi->max_malloced_level; level++)
|
for (level = 1; level < mi->max_malloced_level; level++)
|
if (!mi->malloc_for_level[level])
|
if (!mi->malloc_for_level[level])
|
break;
|
break;
|
|
|
mark_min_matrix_escape_level (mi, level, NULL);
|
mark_min_matrix_escape_level (mi, level, NULL);
|
|
|
/* Check if the expression of the size passed to malloc could be
|
/* Check if the expression of the size passed to malloc could be
|
pre-calculated before the malloc of level 0. */
|
pre-calculated before the malloc of level 0. */
|
for (level = 1; level < mi->min_indirect_level_escape; level++)
|
for (level = 1; level < mi->min_indirect_level_escape; level++)
|
{
|
{
|
gimple call_stmt;
|
gimple call_stmt;
|
tree size;
|
tree size;
|
struct malloc_call_data mcd = {NULL, NULL_TREE, NULL_TREE};
|
struct malloc_call_data mcd = {NULL, NULL_TREE, NULL_TREE};
|
|
|
call_stmt = mi->malloc_for_level[level];
|
call_stmt = mi->malloc_for_level[level];
|
|
|
/* Find the correct malloc information. */
|
/* Find the correct malloc information. */
|
collect_data_for_malloc_call (call_stmt, &mcd);
|
collect_data_for_malloc_call (call_stmt, &mcd);
|
|
|
/* No need to check anticipation for constants. */
|
/* No need to check anticipation for constants. */
|
if (TREE_CODE (mcd.size_var) == INTEGER_CST)
|
if (TREE_CODE (mcd.size_var) == INTEGER_CST)
|
{
|
{
|
if (!mi->dimension_size)
|
if (!mi->dimension_size)
|
{
|
{
|
mi->dimension_size =
|
mi->dimension_size =
|
(tree *) xcalloc (mi->min_indirect_level_escape,
|
(tree *) xcalloc (mi->min_indirect_level_escape,
|
sizeof (tree));
|
sizeof (tree));
|
mi->dimension_size_orig =
|
mi->dimension_size_orig =
|
(tree *) xcalloc (mi->min_indirect_level_escape,
|
(tree *) xcalloc (mi->min_indirect_level_escape,
|
sizeof (tree));
|
sizeof (tree));
|
}
|
}
|
mi->dimension_size[level] = mcd.size_var;
|
mi->dimension_size[level] = mcd.size_var;
|
mi->dimension_size_orig[level] = mcd.size_var;
|
mi->dimension_size_orig[level] = mcd.size_var;
|
continue;
|
continue;
|
}
|
}
|
/* ??? Here we should also add the way to calculate the size
|
/* ??? Here we should also add the way to calculate the size
|
expression not only know that it is anticipated. */
|
expression not only know that it is anticipated. */
|
sbitmap_zero (visited);
|
sbitmap_zero (visited);
|
size = can_calculate_expr_before_stmt (mcd.size_var, visited);
|
size = can_calculate_expr_before_stmt (mcd.size_var, visited);
|
if (size == NULL_TREE)
|
if (size == NULL_TREE)
|
{
|
{
|
mark_min_matrix_escape_level (mi, level, call_stmt);
|
mark_min_matrix_escape_level (mi, level, call_stmt);
|
if (dump_file)
|
if (dump_file)
|
fprintf (dump_file,
|
fprintf (dump_file,
|
"Matrix %s: Cannot calculate the size of allocation, escaping at level %d\n",
|
"Matrix %s: Cannot calculate the size of allocation, escaping at level %d\n",
|
get_name (mi->decl), level);
|
get_name (mi->decl), level);
|
break;
|
break;
|
}
|
}
|
if (!mi->dimension_size)
|
if (!mi->dimension_size)
|
{
|
{
|
mi->dimension_size =
|
mi->dimension_size =
|
(tree *) xcalloc (mi->min_indirect_level_escape, sizeof (tree));
|
(tree *) xcalloc (mi->min_indirect_level_escape, sizeof (tree));
|
mi->dimension_size_orig =
|
mi->dimension_size_orig =
|
(tree *) xcalloc (mi->min_indirect_level_escape, sizeof (tree));
|
(tree *) xcalloc (mi->min_indirect_level_escape, sizeof (tree));
|
}
|
}
|
mi->dimension_size[level] = size;
|
mi->dimension_size[level] = size;
|
mi->dimension_size_orig[level] = size;
|
mi->dimension_size_orig[level] = size;
|
}
|
}
|
|
|
/* We don't need those anymore. */
|
/* We don't need those anymore. */
|
for (level = mi->min_indirect_level_escape;
|
for (level = mi->min_indirect_level_escape;
|
level < mi->max_malloced_level; level++)
|
level < mi->max_malloced_level; level++)
|
mi->malloc_for_level[level] = NULL;
|
mi->malloc_for_level[level] = NULL;
|
return 1;
|
return 1;
|
}
|
}
|
|
|
/* Track all access and allocation sites. */
|
/* Track all access and allocation sites. */
|
static void
|
static void
|
find_sites_in_func (bool record)
|
find_sites_in_func (bool record)
|
{
|
{
|
sbitmap visited_stmts_1;
|
sbitmap visited_stmts_1;
|
|
|
gimple_stmt_iterator gsi;
|
gimple_stmt_iterator gsi;
|
gimple stmt;
|
gimple stmt;
|
basic_block bb;
|
basic_block bb;
|
struct matrix_info tmpmi, *mi;
|
struct matrix_info tmpmi, *mi;
|
|
|
visited_stmts_1 = sbitmap_alloc (num_ssa_names);
|
visited_stmts_1 = sbitmap_alloc (num_ssa_names);
|
|
|
FOR_EACH_BB (bb)
|
FOR_EACH_BB (bb)
|
{
|
{
|
for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
|
for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
|
{
|
{
|
tree lhs;
|
tree lhs;
|
|
|
stmt = gsi_stmt (gsi);
|
stmt = gsi_stmt (gsi);
|
lhs = gimple_get_lhs (stmt);
|
lhs = gimple_get_lhs (stmt);
|
if (lhs != NULL_TREE
|
if (lhs != NULL_TREE
|
&& TREE_CODE (lhs) == VAR_DECL)
|
&& TREE_CODE (lhs) == VAR_DECL)
|
{
|
{
|
tmpmi.decl = lhs;
|
tmpmi.decl = lhs;
|
if ((mi = (struct matrix_info *) htab_find (matrices_to_reorg,
|
if ((mi = (struct matrix_info *) htab_find (matrices_to_reorg,
|
&tmpmi)))
|
&tmpmi)))
|
{
|
{
|
sbitmap_zero (visited_stmts_1);
|
sbitmap_zero (visited_stmts_1);
|
analyze_matrix_allocation_site (mi, stmt, 0, visited_stmts_1);
|
analyze_matrix_allocation_site (mi, stmt, 0, visited_stmts_1);
|
}
|
}
|
}
|
}
|
if (is_gimple_assign (stmt)
|
if (is_gimple_assign (stmt)
|
&& gimple_assign_single_p (stmt)
|
&& gimple_assign_single_p (stmt)
|
&& TREE_CODE (lhs) == SSA_NAME
|
&& TREE_CODE (lhs) == SSA_NAME
|
&& TREE_CODE (gimple_assign_rhs1 (stmt)) == VAR_DECL)
|
&& TREE_CODE (gimple_assign_rhs1 (stmt)) == VAR_DECL)
|
{
|
{
|
tmpmi.decl = gimple_assign_rhs1 (stmt);
|
tmpmi.decl = gimple_assign_rhs1 (stmt);
|
if ((mi = (struct matrix_info *) htab_find (matrices_to_reorg,
|
if ((mi = (struct matrix_info *) htab_find (matrices_to_reorg,
|
&tmpmi)))
|
&tmpmi)))
|
{
|
{
|
sbitmap_zero (visited_stmts_1);
|
sbitmap_zero (visited_stmts_1);
|
analyze_matrix_accesses (mi, lhs, 0,
|
analyze_matrix_accesses (mi, lhs, 0,
|
false, visited_stmts_1, record);
|
false, visited_stmts_1, record);
|
}
|
}
|
}
|
}
|
}
|
}
|
}
|
}
|
sbitmap_free (visited_stmts_1);
|
sbitmap_free (visited_stmts_1);
|
}
|
}
|
|
|
/* Traverse the use-def chains to see if there are matrices that
|
/* Traverse the use-def chains to see if there are matrices that
|
are passed through pointers and we cannot know how they are accessed.
|
are passed through pointers and we cannot know how they are accessed.
|
For each SSA-name defined by a global variable of our interest,
|
For each SSA-name defined by a global variable of our interest,
|
we traverse the use-def chains of the SSA and follow the indirections,
|
we traverse the use-def chains of the SSA and follow the indirections,
|
and record in what level of indirection the use of the variable
|
and record in what level of indirection the use of the variable
|
escapes. A use of a pointer escapes when it is passed to a function,
|
escapes. A use of a pointer escapes when it is passed to a function,
|
stored into memory or assigned (except in malloc and free calls). */
|
stored into memory or assigned (except in malloc and free calls). */
|
|
|
static void
|
static void
|
record_all_accesses_in_func (void)
|
record_all_accesses_in_func (void)
|
{
|
{
|
unsigned i;
|
unsigned i;
|
sbitmap visited_stmts_1;
|
sbitmap visited_stmts_1;
|
|
|
visited_stmts_1 = sbitmap_alloc (num_ssa_names);
|
visited_stmts_1 = sbitmap_alloc (num_ssa_names);
|
|
|
for (i = 0; i < num_ssa_names; i++)
|
for (i = 0; i < num_ssa_names; i++)
|
{
|
{
|
struct matrix_info tmpmi, *mi;
|
struct matrix_info tmpmi, *mi;
|
tree ssa_var = ssa_name (i);
|
tree ssa_var = ssa_name (i);
|
tree rhs, lhs;
|
tree rhs, lhs;
|
|
|
if (!ssa_var
|
if (!ssa_var
|
|| !is_gimple_assign (SSA_NAME_DEF_STMT (ssa_var))
|
|| !is_gimple_assign (SSA_NAME_DEF_STMT (ssa_var))
|
|| !gimple_assign_single_p (SSA_NAME_DEF_STMT (ssa_var)))
|
|| !gimple_assign_single_p (SSA_NAME_DEF_STMT (ssa_var)))
|
continue;
|
continue;
|
rhs = gimple_assign_rhs1 (SSA_NAME_DEF_STMT (ssa_var));
|
rhs = gimple_assign_rhs1 (SSA_NAME_DEF_STMT (ssa_var));
|
lhs = gimple_assign_lhs (SSA_NAME_DEF_STMT (ssa_var));
|
lhs = gimple_assign_lhs (SSA_NAME_DEF_STMT (ssa_var));
|
if (TREE_CODE (rhs) != VAR_DECL && TREE_CODE (lhs) != VAR_DECL)
|
if (TREE_CODE (rhs) != VAR_DECL && TREE_CODE (lhs) != VAR_DECL)
|
continue;
|
continue;
|
|
|
/* If the RHS is a matrix that we want to analyze, follow the def-use
|
/* If the RHS is a matrix that we want to analyze, follow the def-use
|
chain for this SSA_VAR and check for escapes or apply the
|
chain for this SSA_VAR and check for escapes or apply the
|
flattening. */
|
flattening. */
|
tmpmi.decl = rhs;
|
tmpmi.decl = rhs;
|
if ((mi = (struct matrix_info *) htab_find (matrices_to_reorg, &tmpmi)))
|
if ((mi = (struct matrix_info *) htab_find (matrices_to_reorg, &tmpmi)))
|
{
|
{
|
/* This variable will track the visited PHI nodes, so we can limit
|
/* This variable will track the visited PHI nodes, so we can limit
|
its size to the maximum number of SSA names. */
|
its size to the maximum number of SSA names. */
|
sbitmap_zero (visited_stmts_1);
|
sbitmap_zero (visited_stmts_1);
|
analyze_matrix_accesses (mi, ssa_var,
|
analyze_matrix_accesses (mi, ssa_var,
|
0, false, visited_stmts_1, true);
|
0, false, visited_stmts_1, true);
|
|
|
}
|
}
|
}
|
}
|
sbitmap_free (visited_stmts_1);
|
sbitmap_free (visited_stmts_1);
|
}
|
}
|
|
|
/* Used when we want to convert the expression: RESULT = something *
|
/* Used when we want to convert the expression: RESULT = something *
|
ORIG to RESULT = something * NEW_VAL. If ORIG and NEW_VAL are power
|
ORIG to RESULT = something * NEW_VAL. If ORIG and NEW_VAL are power
|
of 2, shift operations can be done, else division and
|
of 2, shift operations can be done, else division and
|
multiplication. */
|
multiplication. */
|
|
|
static tree
|
static tree
|
compute_offset (HOST_WIDE_INT orig, HOST_WIDE_INT new_val, tree result)
|
compute_offset (HOST_WIDE_INT orig, HOST_WIDE_INT new_val, tree result)
|
{
|
{
|
|
|
int x, y;
|
int x, y;
|
tree result1, ratio, log, orig_tree, new_tree;
|
tree result1, ratio, log, orig_tree, new_tree;
|
|
|
x = exact_log2 (orig);
|
x = exact_log2 (orig);
|
y = exact_log2 (new_val);
|
y = exact_log2 (new_val);
|
|
|
if (x != -1 && y != -1)
|
if (x != -1 && y != -1)
|
{
|
{
|
if (x == y)
|
if (x == y)
|
return result;
|
return result;
|
else if (x > y)
|
else if (x > y)
|
{
|
{
|
log = build_int_cst (TREE_TYPE (result), x - y);
|
log = build_int_cst (TREE_TYPE (result), x - y);
|
result1 =
|
result1 =
|
fold_build2 (LSHIFT_EXPR, TREE_TYPE (result), result, log);
|
fold_build2 (LSHIFT_EXPR, TREE_TYPE (result), result, log);
|
return result1;
|
return result1;
|
}
|
}
|
log = build_int_cst (TREE_TYPE (result), y - x);
|
log = build_int_cst (TREE_TYPE (result), y - x);
|
result1 = fold_build2 (RSHIFT_EXPR, TREE_TYPE (result), result, log);
|
result1 = fold_build2 (RSHIFT_EXPR, TREE_TYPE (result), result, log);
|
|
|
return result1;
|
return result1;
|
}
|
}
|
orig_tree = build_int_cst (TREE_TYPE (result), orig);
|
orig_tree = build_int_cst (TREE_TYPE (result), orig);
|
new_tree = build_int_cst (TREE_TYPE (result), new_val);
|
new_tree = build_int_cst (TREE_TYPE (result), new_val);
|
ratio = fold_build2 (TRUNC_DIV_EXPR, TREE_TYPE (result), result, orig_tree);
|
ratio = fold_build2 (TRUNC_DIV_EXPR, TREE_TYPE (result), result, orig_tree);
|
result1 = fold_build2 (MULT_EXPR, TREE_TYPE (result), ratio, new_tree);
|
result1 = fold_build2 (MULT_EXPR, TREE_TYPE (result), ratio, new_tree);
|
|
|
return result1;
|
return result1;
|
}
|
}
|
|
|
|
|
/* We know that we are allowed to perform matrix flattening (according to the
|
/* We know that we are allowed to perform matrix flattening (according to the
|
escape analysis), so we traverse the use-def chains of the SSA vars
|
escape analysis), so we traverse the use-def chains of the SSA vars
|
defined by the global variables pointing to the matrices of our interest.
|
defined by the global variables pointing to the matrices of our interest.
|
in each use of the SSA we calculate the offset from the base address
|
in each use of the SSA we calculate the offset from the base address
|
according to the following equation:
|
according to the following equation:
|
|
|
a[I1][I2]...[Ik] , where D1..Dk is the length of each dimension and the
|
a[I1][I2]...[Ik] , where D1..Dk is the length of each dimension and the
|
escaping level is m <= k, and a' is the new allocated matrix,
|
escaping level is m <= k, and a' is the new allocated matrix,
|
will be translated to :
|
will be translated to :
|
|
|
b[I(m+1)]...[Ik]
|
b[I(m+1)]...[Ik]
|
|
|
where
|
where
|
b = a' + I1*D2...*Dm + I2*D3...Dm + ... + Im
|
b = a' + I1*D2...*Dm + I2*D3...Dm + ... + Im
|
*/
|
*/
|
|
|
static int
|
static int
|
transform_access_sites (void **slot, void *data ATTRIBUTE_UNUSED)
|
transform_access_sites (void **slot, void *data ATTRIBUTE_UNUSED)
|
{
|
{
|
gimple_stmt_iterator gsi;
|
gimple_stmt_iterator gsi;
|
struct matrix_info *mi = (struct matrix_info *) *slot;
|
struct matrix_info *mi = (struct matrix_info *) *slot;
|
int min_escape_l = mi->min_indirect_level_escape;
|
int min_escape_l = mi->min_indirect_level_escape;
|
struct access_site_info *acc_info;
|
struct access_site_info *acc_info;
|
enum tree_code code;
|
enum tree_code code;
|
int i;
|
int i;
|
|
|
if (min_escape_l < 2 || !mi->access_l)
|
if (min_escape_l < 2 || !mi->access_l)
|
return 1;
|
return 1;
|
for (i = 0; VEC_iterate (access_site_info_p, mi->access_l, i, acc_info);
|
for (i = 0; VEC_iterate (access_site_info_p, mi->access_l, i, acc_info);
|
i++)
|
i++)
|
{
|
{
|
/* This is possible because we collect the access sites before
|
/* This is possible because we collect the access sites before
|
we determine the final minimum indirection level. */
|
we determine the final minimum indirection level. */
|
if (acc_info->level >= min_escape_l)
|
if (acc_info->level >= min_escape_l)
|
{
|
{
|
free (acc_info);
|
free (acc_info);
|
continue;
|
continue;
|
}
|
}
|
if (acc_info->is_alloc)
|
if (acc_info->is_alloc)
|
{
|
{
|
if (acc_info->level >= 0 && gimple_bb (acc_info->stmt))
|
if (acc_info->level >= 0 && gimple_bb (acc_info->stmt))
|
{
|
{
|
ssa_op_iter iter;
|
ssa_op_iter iter;
|
tree def;
|
tree def;
|
gimple stmt = acc_info->stmt;
|
gimple stmt = acc_info->stmt;
|
tree lhs;
|
tree lhs;
|
|
|
FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
|
FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
|
mark_sym_for_renaming (SSA_NAME_VAR (def));
|
mark_sym_for_renaming (SSA_NAME_VAR (def));
|
gsi = gsi_for_stmt (stmt);
|
gsi = gsi_for_stmt (stmt);
|
gcc_assert (is_gimple_assign (acc_info->stmt));
|
gcc_assert (is_gimple_assign (acc_info->stmt));
|
lhs = gimple_assign_lhs (acc_info->stmt);
|
lhs = gimple_assign_lhs (acc_info->stmt);
|
if (TREE_CODE (lhs) == SSA_NAME
|
if (TREE_CODE (lhs) == SSA_NAME
|
&& acc_info->level < min_escape_l - 1)
|
&& acc_info->level < min_escape_l - 1)
|
{
|
{
|
imm_use_iterator imm_iter;
|
imm_use_iterator imm_iter;
|
use_operand_p use_p;
|
use_operand_p use_p;
|
gimple use_stmt;
|
gimple use_stmt;
|
|
|
FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, lhs)
|
FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, lhs)
|
FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter)
|
FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter)
|
{
|
{
|
tree rhs, tmp;
|
tree rhs, tmp;
|
gimple new_stmt;
|
gimple new_stmt;
|
|
|
gcc_assert (gimple_assign_rhs_code (acc_info->stmt)
|
gcc_assert (gimple_assign_rhs_code (acc_info->stmt)
|
== MEM_REF);
|
== MEM_REF);
|
/* Emit convert statement to convert to type of use. */
|
/* Emit convert statement to convert to type of use. */
|
tmp = create_tmp_var (TREE_TYPE (lhs), "new");
|
tmp = create_tmp_var (TREE_TYPE (lhs), "new");
|
add_referenced_var (tmp);
|
add_referenced_var (tmp);
|
rhs = gimple_assign_rhs1 (acc_info->stmt);
|
rhs = gimple_assign_rhs1 (acc_info->stmt);
|
rhs = fold_convert (TREE_TYPE (tmp),
|
rhs = fold_convert (TREE_TYPE (tmp),
|
TREE_OPERAND (rhs, 0));
|
TREE_OPERAND (rhs, 0));
|
new_stmt = gimple_build_assign (tmp, rhs);
|
new_stmt = gimple_build_assign (tmp, rhs);
|
tmp = make_ssa_name (tmp, new_stmt);
|
tmp = make_ssa_name (tmp, new_stmt);
|
gimple_assign_set_lhs (new_stmt, tmp);
|
gimple_assign_set_lhs (new_stmt, tmp);
|
gsi = gsi_for_stmt (acc_info->stmt);
|
gsi = gsi_for_stmt (acc_info->stmt);
|
gsi_insert_after (&gsi, new_stmt, GSI_SAME_STMT);
|
gsi_insert_after (&gsi, new_stmt, GSI_SAME_STMT);
|
SET_USE (use_p, tmp);
|
SET_USE (use_p, tmp);
|
}
|
}
|
}
|
}
|
if (acc_info->level < min_escape_l - 1)
|
if (acc_info->level < min_escape_l - 1)
|
gsi_remove (&gsi, true);
|
gsi_remove (&gsi, true);
|
}
|
}
|
free (acc_info);
|
free (acc_info);
|
continue;
|
continue;
|
}
|
}
|
code = gimple_assign_rhs_code (acc_info->stmt);
|
code = gimple_assign_rhs_code (acc_info->stmt);
|
if (code == MEM_REF
|
if (code == MEM_REF
|
&& acc_info->level < min_escape_l - 1)
|
&& acc_info->level < min_escape_l - 1)
|
{
|
{
|
/* Replace the MEM_REF with NOP (cast) usually we are casting
|
/* Replace the MEM_REF with NOP (cast) usually we are casting
|
from "pointer to type" to "type". */
|
from "pointer to type" to "type". */
|
tree t =
|
tree t =
|
build1 (NOP_EXPR, TREE_TYPE (gimple_assign_rhs1 (acc_info->stmt)),
|
build1 (NOP_EXPR, TREE_TYPE (gimple_assign_rhs1 (acc_info->stmt)),
|
TREE_OPERAND (gimple_assign_rhs1 (acc_info->stmt), 0));
|
TREE_OPERAND (gimple_assign_rhs1 (acc_info->stmt), 0));
|
gimple_assign_set_rhs_code (acc_info->stmt, NOP_EXPR);
|
gimple_assign_set_rhs_code (acc_info->stmt, NOP_EXPR);
|
gimple_assign_set_rhs1 (acc_info->stmt, t);
|
gimple_assign_set_rhs1 (acc_info->stmt, t);
|
}
|
}
|
else if (code == POINTER_PLUS_EXPR
|
else if (code == POINTER_PLUS_EXPR
|
&& acc_info->level < (min_escape_l))
|
&& acc_info->level < (min_escape_l))
|
{
|
{
|
imm_use_iterator imm_iter;
|
imm_use_iterator imm_iter;
|
use_operand_p use_p;
|
use_operand_p use_p;
|
|
|
tree offset;
|
tree offset;
|
int k = acc_info->level;
|
int k = acc_info->level;
|
tree num_elements, total_elements;
|
tree num_elements, total_elements;
|
tree tmp1;
|
tree tmp1;
|
tree d_size = mi->dimension_size[k];
|
tree d_size = mi->dimension_size[k];
|
|
|
/* We already make sure in the analysis that the first operand
|
/* We already make sure in the analysis that the first operand
|
is the base and the second is the offset. */
|
is the base and the second is the offset. */
|
offset = acc_info->offset;
|
offset = acc_info->offset;
|
if (mi->dim_map[k] == min_escape_l - 1)
|
if (mi->dim_map[k] == min_escape_l - 1)
|
{
|
{
|
if (!check_transpose_p || mi->is_transposed_p == false)
|
if (!check_transpose_p || mi->is_transposed_p == false)
|
tmp1 = offset;
|
tmp1 = offset;
|
else
|
else
|
{
|
{
|
tree new_offset;
|
tree new_offset;
|
|
|
new_offset =
|
new_offset =
|
compute_offset (mi->dimension_type_size[min_escape_l],
|
compute_offset (mi->dimension_type_size[min_escape_l],
|
mi->dimension_type_size[k + 1], offset);
|
mi->dimension_type_size[k + 1], offset);
|
|
|
total_elements = new_offset;
|
total_elements = new_offset;
|
if (new_offset != offset)
|
if (new_offset != offset)
|
{
|
{
|
gsi = gsi_for_stmt (acc_info->stmt);
|
gsi = gsi_for_stmt (acc_info->stmt);
|
tmp1 = force_gimple_operand_gsi (&gsi, total_elements,
|
tmp1 = force_gimple_operand_gsi (&gsi, total_elements,
|
true, NULL,
|
true, NULL,
|
true, GSI_SAME_STMT);
|
true, GSI_SAME_STMT);
|
}
|
}
|
else
|
else
|
tmp1 = offset;
|
tmp1 = offset;
|
}
|
}
|
}
|
}
|
else
|
else
|
{
|
{
|
d_size = mi->dimension_size[mi->dim_map[k] + 1];
|
d_size = mi->dimension_size[mi->dim_map[k] + 1];
|
num_elements =
|
num_elements =
|
fold_build2 (MULT_EXPR, sizetype, fold_convert (sizetype, acc_info->index),
|
fold_build2 (MULT_EXPR, sizetype, fold_convert (sizetype, acc_info->index),
|
fold_convert (sizetype, d_size));
|
fold_convert (sizetype, d_size));
|
add_referenced_var (d_size);
|
add_referenced_var (d_size);
|
gsi = gsi_for_stmt (acc_info->stmt);
|
gsi = gsi_for_stmt (acc_info->stmt);
|
tmp1 = force_gimple_operand_gsi (&gsi, num_elements, true,
|
tmp1 = force_gimple_operand_gsi (&gsi, num_elements, true,
|
NULL, true, GSI_SAME_STMT);
|
NULL, true, GSI_SAME_STMT);
|
}
|
}
|
/* Replace the offset if needed. */
|
/* Replace the offset if needed. */
|
if (tmp1 != offset)
|
if (tmp1 != offset)
|
{
|
{
|
if (TREE_CODE (offset) == SSA_NAME)
|
if (TREE_CODE (offset) == SSA_NAME)
|
{
|
{
|
gimple use_stmt;
|
gimple use_stmt;
|
|
|
FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, offset)
|
FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, offset)
|
FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter)
|
FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter)
|
if (use_stmt == acc_info->stmt)
|
if (use_stmt == acc_info->stmt)
|
SET_USE (use_p, tmp1);
|
SET_USE (use_p, tmp1);
|
}
|
}
|
else
|
else
|
{
|
{
|
gcc_assert (TREE_CODE (offset) == INTEGER_CST);
|
gcc_assert (TREE_CODE (offset) == INTEGER_CST);
|
gimple_assign_set_rhs2 (acc_info->stmt, tmp1);
|
gimple_assign_set_rhs2 (acc_info->stmt, tmp1);
|
update_stmt (acc_info->stmt);
|
update_stmt (acc_info->stmt);
|
}
|
}
|
}
|
}
|
}
|
}
|
/* ??? meanwhile this happens because we record the same access
|
/* ??? meanwhile this happens because we record the same access
|
site more than once; we should be using a hash table to
|
site more than once; we should be using a hash table to
|
avoid this and insert the STMT of the access site only
|
avoid this and insert the STMT of the access site only
|
once.
|
once.
|
else
|
else
|
gcc_unreachable (); */
|
gcc_unreachable (); */
|
free (acc_info);
|
free (acc_info);
|
}
|
}
|
VEC_free (access_site_info_p, heap, mi->access_l);
|
VEC_free (access_site_info_p, heap, mi->access_l);
|
|
|
update_ssa (TODO_update_ssa);
|
update_ssa (TODO_update_ssa);
|
#ifdef ENABLE_CHECKING
|
#ifdef ENABLE_CHECKING
|
verify_ssa (true);
|
verify_ssa (true);
|
#endif
|
#endif
|
return 1;
|
return 1;
|
}
|
}
|
|
|
/* Sort A array of counts. Arrange DIM_MAP to reflect the new order. */
|
/* Sort A array of counts. Arrange DIM_MAP to reflect the new order. */
|
|
|
static void
|
static void
|
sort_dim_hot_level (gcov_type * a, int *dim_map, int n)
|
sort_dim_hot_level (gcov_type * a, int *dim_map, int n)
|
{
|
{
|
int i, j, tmp1;
|
int i, j, tmp1;
|
gcov_type tmp;
|
gcov_type tmp;
|
|
|
for (i = 0; i < n - 1; i++)
|
for (i = 0; i < n - 1; i++)
|
{
|
{
|
for (j = 0; j < n - 1 - i; j++)
|
for (j = 0; j < n - 1 - i; j++)
|
{
|
{
|
if (a[j + 1] < a[j])
|
if (a[j + 1] < a[j])
|
{
|
{
|
tmp = a[j]; /* swap a[j] and a[j+1] */
|
tmp = a[j]; /* swap a[j] and a[j+1] */
|
a[j] = a[j + 1];
|
a[j] = a[j + 1];
|
a[j + 1] = tmp;
|
a[j + 1] = tmp;
|
tmp1 = dim_map[j];
|
tmp1 = dim_map[j];
|
dim_map[j] = dim_map[j + 1];
|
dim_map[j] = dim_map[j + 1];
|
dim_map[j + 1] = tmp1;
|
dim_map[j + 1] = tmp1;
|
}
|
}
|
}
|
}
|
}
|
}
|
}
|
}
|
|
|
/* Replace multiple mallocs (one for each dimension) to one malloc
|
/* Replace multiple mallocs (one for each dimension) to one malloc
|
with the size of DIM1*DIM2*...*DIMN*size_of_element
|
with the size of DIM1*DIM2*...*DIMN*size_of_element
|
Make sure that we hold the size in the malloc site inside a
|
Make sure that we hold the size in the malloc site inside a
|
new global variable; this way we ensure that the size doesn't
|
new global variable; this way we ensure that the size doesn't
|
change and it is accessible from all the other functions that
|
change and it is accessible from all the other functions that
|
uses the matrix. Also, the original calls to free are deleted,
|
uses the matrix. Also, the original calls to free are deleted,
|
and replaced by a new call to free the flattened matrix. */
|
and replaced by a new call to free the flattened matrix. */
|
|
|
static int
|
static int
|
transform_allocation_sites (void **slot, void *data ATTRIBUTE_UNUSED)
|
transform_allocation_sites (void **slot, void *data ATTRIBUTE_UNUSED)
|
{
|
{
|
int i;
|
int i;
|
struct matrix_info *mi;
|
struct matrix_info *mi;
|
tree type, oldfn, prev_dim_size;
|
tree type, oldfn, prev_dim_size;
|
gimple call_stmt_0, use_stmt;
|
gimple call_stmt_0, use_stmt;
|
struct cgraph_node *c_node;
|
struct cgraph_node *c_node;
|
struct cgraph_edge *e;
|
struct cgraph_edge *e;
|
gimple_stmt_iterator gsi;
|
gimple_stmt_iterator gsi;
|
struct malloc_call_data mcd = {NULL, NULL_TREE, NULL_TREE};
|
struct malloc_call_data mcd = {NULL, NULL_TREE, NULL_TREE};
|
HOST_WIDE_INT element_size;
|
HOST_WIDE_INT element_size;
|
|
|
imm_use_iterator imm_iter;
|
imm_use_iterator imm_iter;
|
use_operand_p use_p;
|
use_operand_p use_p;
|
tree old_size_0, tmp;
|
tree old_size_0, tmp;
|
int min_escape_l;
|
int min_escape_l;
|
int id;
|
int id;
|
|
|
mi = (struct matrix_info *) *slot;
|
mi = (struct matrix_info *) *slot;
|
|
|
min_escape_l = mi->min_indirect_level_escape;
|
min_escape_l = mi->min_indirect_level_escape;
|
|
|
if (!mi->malloc_for_level)
|
if (!mi->malloc_for_level)
|
mi->min_indirect_level_escape = 0;
|
mi->min_indirect_level_escape = 0;
|
|
|
if (mi->min_indirect_level_escape < 2)
|
if (mi->min_indirect_level_escape < 2)
|
return 1;
|
return 1;
|
|
|
mi->dim_map = (int *) xcalloc (mi->min_indirect_level_escape, sizeof (int));
|
mi->dim_map = (int *) xcalloc (mi->min_indirect_level_escape, sizeof (int));
|
for (i = 0; i < mi->min_indirect_level_escape; i++)
|
for (i = 0; i < mi->min_indirect_level_escape; i++)
|
mi->dim_map[i] = i;
|
mi->dim_map[i] = i;
|
if (check_transpose_p)
|
if (check_transpose_p)
|
{
|
{
|
int i;
|
int i;
|
|
|
if (dump_file)
|
if (dump_file)
|
{
|
{
|
fprintf (dump_file, "Matrix %s:\n", get_name (mi->decl));
|
fprintf (dump_file, "Matrix %s:\n", get_name (mi->decl));
|
for (i = 0; i < min_escape_l; i++)
|
for (i = 0; i < min_escape_l; i++)
|
{
|
{
|
fprintf (dump_file, "dim %d before sort ", i);
|
fprintf (dump_file, "dim %d before sort ", i);
|
if (mi->dim_hot_level)
|
if (mi->dim_hot_level)
|
fprintf (dump_file,
|
fprintf (dump_file,
|
"count is " HOST_WIDEST_INT_PRINT_DEC " \n",
|
"count is " HOST_WIDEST_INT_PRINT_DEC " \n",
|
mi->dim_hot_level[i]);
|
mi->dim_hot_level[i]);
|
}
|
}
|
}
|
}
|
sort_dim_hot_level (mi->dim_hot_level, mi->dim_map,
|
sort_dim_hot_level (mi->dim_hot_level, mi->dim_map,
|
mi->min_indirect_level_escape);
|
mi->min_indirect_level_escape);
|
if (dump_file)
|
if (dump_file)
|
for (i = 0; i < min_escape_l; i++)
|
for (i = 0; i < min_escape_l; i++)
|
{
|
{
|
fprintf (dump_file, "dim %d after sort\n", i);
|
fprintf (dump_file, "dim %d after sort\n", i);
|
if (mi->dim_hot_level)
|
if (mi->dim_hot_level)
|
fprintf (dump_file, "count is " HOST_WIDE_INT_PRINT_DEC
|
fprintf (dump_file, "count is " HOST_WIDE_INT_PRINT_DEC
|
" \n", (HOST_WIDE_INT) mi->dim_hot_level[i]);
|
" \n", (HOST_WIDE_INT) mi->dim_hot_level[i]);
|
}
|
}
|
for (i = 0; i < mi->min_indirect_level_escape; i++)
|
for (i = 0; i < mi->min_indirect_level_escape; i++)
|
{
|
{
|
if (dump_file)
|
if (dump_file)
|
fprintf (dump_file, "dim_map[%d] after sort %d\n", i,
|
fprintf (dump_file, "dim_map[%d] after sort %d\n", i,
|
mi->dim_map[i]);
|
mi->dim_map[i]);
|
if (mi->dim_map[i] != i)
|
if (mi->dim_map[i] != i)
|
{
|
{
|
if (dump_file)
|
if (dump_file)
|
fprintf (dump_file,
|
fprintf (dump_file,
|
"Transposed dimensions: dim %d is now dim %d\n",
|
"Transposed dimensions: dim %d is now dim %d\n",
|
mi->dim_map[i], i);
|
mi->dim_map[i], i);
|
mi->is_transposed_p = true;
|
mi->is_transposed_p = true;
|
}
|
}
|
}
|
}
|
}
|
}
|
else
|
else
|
{
|
{
|
for (i = 0; i < mi->min_indirect_level_escape; i++)
|
for (i = 0; i < mi->min_indirect_level_escape; i++)
|
mi->dim_map[i] = i;
|
mi->dim_map[i] = i;
|
}
|
}
|
/* Call statement of allocation site of level 0. */
|
/* Call statement of allocation site of level 0. */
|
call_stmt_0 = mi->malloc_for_level[0];
|
call_stmt_0 = mi->malloc_for_level[0];
|
|
|
/* Finds the correct malloc information. */
|
/* Finds the correct malloc information. */
|
collect_data_for_malloc_call (call_stmt_0, &mcd);
|
collect_data_for_malloc_call (call_stmt_0, &mcd);
|
|
|
mi->dimension_size[0] = mcd.size_var;
|
mi->dimension_size[0] = mcd.size_var;
|
mi->dimension_size_orig[0] = mcd.size_var;
|
mi->dimension_size_orig[0] = mcd.size_var;
|
/* Make sure that the variables in the size expression for
|
/* Make sure that the variables in the size expression for
|
all the dimensions (above level 0) aren't modified in
|
all the dimensions (above level 0) aren't modified in
|
the allocation function. */
|
the allocation function. */
|
for (i = 1; i < mi->min_indirect_level_escape; i++)
|
for (i = 1; i < mi->min_indirect_level_escape; i++)
|
{
|
{
|
tree t;
|
tree t;
|
check_var_data data;
|
check_var_data data;
|
|
|
/* mi->dimension_size must contain the expression of the size calculated
|
/* mi->dimension_size must contain the expression of the size calculated
|
in check_allocation_function. */
|
in check_allocation_function. */
|
gcc_assert (mi->dimension_size[i]);
|
gcc_assert (mi->dimension_size[i]);
|
|
|
data.fn = mi->allocation_function_decl;
|
data.fn = mi->allocation_function_decl;
|
data.stmt = NULL;
|
data.stmt = NULL;
|
t = walk_tree_without_duplicates (&(mi->dimension_size[i]),
|
t = walk_tree_without_duplicates (&(mi->dimension_size[i]),
|
check_var_notmodified_p,
|
check_var_notmodified_p,
|
&data);
|
&data);
|
if (t != NULL_TREE)
|
if (t != NULL_TREE)
|
{
|
{
|
mark_min_matrix_escape_level (mi, i, data.stmt);
|
mark_min_matrix_escape_level (mi, i, data.stmt);
|
break;
|
break;
|
}
|
}
|
}
|
}
|
|
|
if (mi->min_indirect_level_escape < 2)
|
if (mi->min_indirect_level_escape < 2)
|
return 1;
|
return 1;
|
|
|
/* Since we should make sure that the size expression is available
|
/* Since we should make sure that the size expression is available
|
before the call to malloc of level 0. */
|
before the call to malloc of level 0. */
|
gsi = gsi_for_stmt (call_stmt_0);
|
gsi = gsi_for_stmt (call_stmt_0);
|
|
|
/* Find out the size of each dimension by looking at the malloc
|
/* Find out the size of each dimension by looking at the malloc
|
sites and create a global variable to hold it.
|
sites and create a global variable to hold it.
|
We add the assignment to the global before the malloc of level 0. */
|
We add the assignment to the global before the malloc of level 0. */
|
|
|
/* To be able to produce gimple temporaries. */
|
/* To be able to produce gimple temporaries. */
|
oldfn = current_function_decl;
|
oldfn = current_function_decl;
|
current_function_decl = mi->allocation_function_decl;
|
current_function_decl = mi->allocation_function_decl;
|
push_cfun (DECL_STRUCT_FUNCTION (mi->allocation_function_decl));
|
push_cfun (DECL_STRUCT_FUNCTION (mi->allocation_function_decl));
|
|
|
/* Set the dimension sizes as follows:
|
/* Set the dimension sizes as follows:
|
DIM_SIZE[i] = DIM_SIZE[n] * ... * DIM_SIZE[i]
|
DIM_SIZE[i] = DIM_SIZE[n] * ... * DIM_SIZE[i]
|
where n is the maximum non escaping level. */
|
where n is the maximum non escaping level. */
|
element_size = mi->dimension_type_size[mi->min_indirect_level_escape];
|
element_size = mi->dimension_type_size[mi->min_indirect_level_escape];
|
prev_dim_size = NULL_TREE;
|
prev_dim_size = NULL_TREE;
|
|
|
for (i = mi->min_indirect_level_escape - 1; i >= 0; i--)
|
for (i = mi->min_indirect_level_escape - 1; i >= 0; i--)
|
{
|
{
|
tree dim_size, dim_var;
|
tree dim_size, dim_var;
|
gimple stmt;
|
gimple stmt;
|
tree d_type_size;
|
tree d_type_size;
|
|
|
/* Now put the size expression in a global variable and initialize it to
|
/* Now put the size expression in a global variable and initialize it to
|
the size expression before the malloc of level 0. */
|
the size expression before the malloc of level 0. */
|
dim_var =
|
dim_var =
|
add_new_static_var (TREE_TYPE
|
add_new_static_var (TREE_TYPE
|
(mi->dimension_size_orig[mi->dim_map[i]]));
|
(mi->dimension_size_orig[mi->dim_map[i]]));
|
type = TREE_TYPE (mi->dimension_size_orig[mi->dim_map[i]]);
|
type = TREE_TYPE (mi->dimension_size_orig[mi->dim_map[i]]);
|
|
|
/* DIM_SIZE = MALLOC_SIZE_PARAM / TYPE_SIZE. */
|
/* DIM_SIZE = MALLOC_SIZE_PARAM / TYPE_SIZE. */
|
/* Find which dim ID becomes dim I. */
|
/* Find which dim ID becomes dim I. */
|
for (id = 0; id < mi->min_indirect_level_escape; id++)
|
for (id = 0; id < mi->min_indirect_level_escape; id++)
|
if (mi->dim_map[id] == i)
|
if (mi->dim_map[id] == i)
|
break;
|
break;
|
d_type_size =
|
d_type_size =
|
build_int_cst (type, mi->dimension_type_size[id + 1]);
|
build_int_cst (type, mi->dimension_type_size[id + 1]);
|
if (!prev_dim_size)
|
if (!prev_dim_size)
|
prev_dim_size = build_int_cst (type, element_size);
|
prev_dim_size = build_int_cst (type, element_size);
|
if (!check_transpose_p && i == mi->min_indirect_level_escape - 1)
|
if (!check_transpose_p && i == mi->min_indirect_level_escape - 1)
|
{
|
{
|
dim_size = mi->dimension_size_orig[id];
|
dim_size = mi->dimension_size_orig[id];
|
}
|
}
|
else
|
else
|
{
|
{
|
dim_size =
|
dim_size =
|
fold_build2 (TRUNC_DIV_EXPR, type, mi->dimension_size_orig[id],
|
fold_build2 (TRUNC_DIV_EXPR, type, mi->dimension_size_orig[id],
|
d_type_size);
|
d_type_size);
|
|
|
dim_size = fold_build2 (MULT_EXPR, type, dim_size, prev_dim_size);
|
dim_size = fold_build2 (MULT_EXPR, type, dim_size, prev_dim_size);
|
}
|
}
|
dim_size = force_gimple_operand_gsi (&gsi, dim_size, true, NULL,
|
dim_size = force_gimple_operand_gsi (&gsi, dim_size, true, NULL,
|
true, GSI_SAME_STMT);
|
true, GSI_SAME_STMT);
|
/* GLOBAL_HOLDING_THE_SIZE = DIM_SIZE. */
|
/* GLOBAL_HOLDING_THE_SIZE = DIM_SIZE. */
|
stmt = gimple_build_assign (dim_var, dim_size);
|
stmt = gimple_build_assign (dim_var, dim_size);
|
mark_symbols_for_renaming (stmt);
|
mark_symbols_for_renaming (stmt);
|
gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
|
gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
|
|
|
prev_dim_size = mi->dimension_size[i] = dim_var;
|
prev_dim_size = mi->dimension_size[i] = dim_var;
|
}
|
}
|
update_ssa (TODO_update_ssa);
|
update_ssa (TODO_update_ssa);
|
/* Replace the malloc size argument in the malloc of level 0 to be
|
/* Replace the malloc size argument in the malloc of level 0 to be
|
the size of all the dimensions. */
|
the size of all the dimensions. */
|
c_node = cgraph_get_node (mi->allocation_function_decl);
|
c_node = cgraph_get_node (mi->allocation_function_decl);
|
gcc_checking_assert (c_node);
|
gcc_checking_assert (c_node);
|
old_size_0 = gimple_call_arg (call_stmt_0, 0);
|
old_size_0 = gimple_call_arg (call_stmt_0, 0);
|
tmp = force_gimple_operand_gsi (&gsi, mi->dimension_size[0], true,
|
tmp = force_gimple_operand_gsi (&gsi, mi->dimension_size[0], true,
|
NULL, true, GSI_SAME_STMT);
|
NULL, true, GSI_SAME_STMT);
|
if (TREE_CODE (old_size_0) == SSA_NAME)
|
if (TREE_CODE (old_size_0) == SSA_NAME)
|
{
|
{
|
FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, old_size_0)
|
FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, old_size_0)
|
FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter)
|
FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter)
|
if (use_stmt == call_stmt_0)
|
if (use_stmt == call_stmt_0)
|
SET_USE (use_p, tmp);
|
SET_USE (use_p, tmp);
|
}
|
}
|
/* When deleting the calls to malloc we need also to remove the edge from
|
/* When deleting the calls to malloc we need also to remove the edge from
|
the call graph to keep it consistent. Notice that cgraph_edge may
|
the call graph to keep it consistent. Notice that cgraph_edge may
|
create a new node in the call graph if there is no node for the given
|
create a new node in the call graph if there is no node for the given
|
declaration; this shouldn't be the case but currently there is no way to
|
declaration; this shouldn't be the case but currently there is no way to
|
check this outside of "cgraph.c". */
|
check this outside of "cgraph.c". */
|
for (i = 1; i < mi->min_indirect_level_escape; i++)
|
for (i = 1; i < mi->min_indirect_level_escape; i++)
|
{
|
{
|
gimple_stmt_iterator gsi;
|
gimple_stmt_iterator gsi;
|
|
|
gimple call_stmt = mi->malloc_for_level[i];
|
gimple call_stmt = mi->malloc_for_level[i];
|
gcc_assert (is_gimple_call (call_stmt));
|
gcc_assert (is_gimple_call (call_stmt));
|
e = cgraph_edge (c_node, call_stmt);
|
e = cgraph_edge (c_node, call_stmt);
|
gcc_assert (e);
|
gcc_assert (e);
|
cgraph_remove_edge (e);
|
cgraph_remove_edge (e);
|
gsi = gsi_for_stmt (call_stmt);
|
gsi = gsi_for_stmt (call_stmt);
|
/* Remove the call stmt. */
|
/* Remove the call stmt. */
|
gsi_remove (&gsi, true);
|
gsi_remove (&gsi, true);
|
/* Remove the assignment of the allocated area. */
|
/* Remove the assignment of the allocated area. */
|
FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter,
|
FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter,
|
gimple_call_lhs (call_stmt))
|
gimple_call_lhs (call_stmt))
|
{
|
{
|
gsi = gsi_for_stmt (use_stmt);
|
gsi = gsi_for_stmt (use_stmt);
|
gsi_remove (&gsi, true);
|
gsi_remove (&gsi, true);
|
}
|
}
|
}
|
}
|
update_ssa (TODO_update_ssa);
|
update_ssa (TODO_update_ssa);
|
#ifdef ENABLE_CHECKING
|
#ifdef ENABLE_CHECKING
|
verify_ssa (true);
|
verify_ssa (true);
|
#endif
|
#endif
|
/* Delete the calls to free. */
|
/* Delete the calls to free. */
|
for (i = 1; i < mi->min_indirect_level_escape; i++)
|
for (i = 1; i < mi->min_indirect_level_escape; i++)
|
{
|
{
|
gimple_stmt_iterator gsi;
|
gimple_stmt_iterator gsi;
|
|
|
/* ??? wonder why this case is possible but we failed on it once. */
|
/* ??? wonder why this case is possible but we failed on it once. */
|
if (!mi->free_stmts[i].stmt)
|
if (!mi->free_stmts[i].stmt)
|
continue;
|
continue;
|
|
|
c_node = cgraph_get_node (mi->free_stmts[i].func);
|
c_node = cgraph_get_node (mi->free_stmts[i].func);
|
gcc_checking_assert (c_node);
|
gcc_checking_assert (c_node);
|
gcc_assert (is_gimple_call (mi->free_stmts[i].stmt));
|
gcc_assert (is_gimple_call (mi->free_stmts[i].stmt));
|
e = cgraph_edge (c_node, mi->free_stmts[i].stmt);
|
e = cgraph_edge (c_node, mi->free_stmts[i].stmt);
|
gcc_assert (e);
|
gcc_assert (e);
|
cgraph_remove_edge (e);
|
cgraph_remove_edge (e);
|
current_function_decl = mi->free_stmts[i].func;
|
current_function_decl = mi->free_stmts[i].func;
|
set_cfun (DECL_STRUCT_FUNCTION (mi->free_stmts[i].func));
|
set_cfun (DECL_STRUCT_FUNCTION (mi->free_stmts[i].func));
|
gsi = gsi_for_stmt (mi->free_stmts[i].stmt);
|
gsi = gsi_for_stmt (mi->free_stmts[i].stmt);
|
gsi_remove (&gsi, true);
|
gsi_remove (&gsi, true);
|
}
|
}
|
/* Return to the previous situation. */
|
/* Return to the previous situation. */
|
current_function_decl = oldfn;
|
current_function_decl = oldfn;
|
pop_cfun ();
|
pop_cfun ();
|
return 1;
|
return 1;
|
|
|
}
|
}
|
|
|
|
|
/* Print out the results of the escape analysis. */
|
/* Print out the results of the escape analysis. */
|
static int
|
static int
|
dump_matrix_reorg_analysis (void **slot, void *data ATTRIBUTE_UNUSED)
|
dump_matrix_reorg_analysis (void **slot, void *data ATTRIBUTE_UNUSED)
|
{
|
{
|
struct matrix_info *mi = (struct matrix_info *) *slot;
|
struct matrix_info *mi = (struct matrix_info *) *slot;
|
|
|
if (!dump_file)
|
if (!dump_file)
|
return 1;
|
return 1;
|
fprintf (dump_file, "Matrix \"%s\"; Escaping Level: %d, Num Dims: %d,",
|
fprintf (dump_file, "Matrix \"%s\"; Escaping Level: %d, Num Dims: %d,",
|
get_name (mi->decl), mi->min_indirect_level_escape, mi->num_dims);
|
get_name (mi->decl), mi->min_indirect_level_escape, mi->num_dims);
|
fprintf (dump_file, " Malloc Dims: %d, ", mi->max_malloced_level);
|
fprintf (dump_file, " Malloc Dims: %d, ", mi->max_malloced_level);
|
fprintf (dump_file, "\n");
|
fprintf (dump_file, "\n");
|
if (mi->min_indirect_level_escape >= 2)
|
if (mi->min_indirect_level_escape >= 2)
|
fprintf (dump_file, "Flattened %d dimensions \n",
|
fprintf (dump_file, "Flattened %d dimensions \n",
|
mi->min_indirect_level_escape);
|
mi->min_indirect_level_escape);
|
return 1;
|
return 1;
|
}
|
}
|
|
|
/* Perform matrix flattening. */
|
/* Perform matrix flattening. */
|
|
|
static unsigned int
|
static unsigned int
|
matrix_reorg (void)
|
matrix_reorg (void)
|
{
|
{
|
struct cgraph_node *node;
|
struct cgraph_node *node;
|
|
|
if (profile_info)
|
if (profile_info)
|
check_transpose_p = true;
|
check_transpose_p = true;
|
else
|
else
|
check_transpose_p = false;
|
check_transpose_p = false;
|
/* If there are hand written vectors, we skip this optimization. */
|
/* If there are hand written vectors, we skip this optimization. */
|
for (node = cgraph_nodes; node; node = node->next)
|
for (node = cgraph_nodes; node; node = node->next)
|
if (!may_flatten_matrices (node))
|
if (!may_flatten_matrices (node))
|
return 0;
|
return 0;
|
matrices_to_reorg = htab_create (37, mtt_info_hash, mtt_info_eq, mat_free);
|
matrices_to_reorg = htab_create (37, mtt_info_hash, mtt_info_eq, mat_free);
|
/* Find and record all potential matrices in the program. */
|
/* Find and record all potential matrices in the program. */
|
find_matrices_decl ();
|
find_matrices_decl ();
|
/* Analyze the accesses of the matrices (escaping analysis). */
|
/* Analyze the accesses of the matrices (escaping analysis). */
|
for (node = cgraph_nodes; node; node = node->next)
|
for (node = cgraph_nodes; node; node = node->next)
|
if (node->analyzed)
|
if (node->analyzed)
|
{
|
{
|
tree temp_fn;
|
tree temp_fn;
|
|
|
temp_fn = current_function_decl;
|
temp_fn = current_function_decl;
|
current_function_decl = node->decl;
|
current_function_decl = node->decl;
|
push_cfun (DECL_STRUCT_FUNCTION (node->decl));
|
push_cfun (DECL_STRUCT_FUNCTION (node->decl));
|
bitmap_obstack_initialize (NULL);
|
bitmap_obstack_initialize (NULL);
|
gimple_register_cfg_hooks ();
|
gimple_register_cfg_hooks ();
|
|
|
if (!gimple_in_ssa_p (cfun))
|
if (!gimple_in_ssa_p (cfun))
|
{
|
{
|
free_dominance_info (CDI_DOMINATORS);
|
free_dominance_info (CDI_DOMINATORS);
|
free_dominance_info (CDI_POST_DOMINATORS);
|
free_dominance_info (CDI_POST_DOMINATORS);
|
pop_cfun ();
|
pop_cfun ();
|
current_function_decl = temp_fn;
|
current_function_decl = temp_fn;
|
bitmap_obstack_release (NULL);
|
bitmap_obstack_release (NULL);
|
|
|
return 0;
|
return 0;
|
}
|
}
|
|
|
#ifdef ENABLE_CHECKING
|
#ifdef ENABLE_CHECKING
|
verify_flow_info ();
|
verify_flow_info ();
|
#endif
|
#endif
|
|
|
if (!matrices_to_reorg)
|
if (!matrices_to_reorg)
|
{
|
{
|
free_dominance_info (CDI_DOMINATORS);
|
free_dominance_info (CDI_DOMINATORS);
|
free_dominance_info (CDI_POST_DOMINATORS);
|
free_dominance_info (CDI_POST_DOMINATORS);
|
pop_cfun ();
|
pop_cfun ();
|
current_function_decl = temp_fn;
|
current_function_decl = temp_fn;
|
bitmap_obstack_release (NULL);
|
bitmap_obstack_release (NULL);
|
|
|
return 0;
|
return 0;
|
}
|
}
|
|
|
/* Create htap for phi nodes. */
|
/* Create htap for phi nodes. */
|
htab_mat_acc_phi_nodes = htab_create (37, mat_acc_phi_hash,
|
htab_mat_acc_phi_nodes = htab_create (37, mat_acc_phi_hash,
|
mat_acc_phi_eq, free);
|
mat_acc_phi_eq, free);
|
if (!check_transpose_p)
|
if (!check_transpose_p)
|
find_sites_in_func (false);
|
find_sites_in_func (false);
|
else
|
else
|
{
|
{
|
find_sites_in_func (true);
|
find_sites_in_func (true);
|
loop_optimizer_init (LOOPS_NORMAL);
|
loop_optimizer_init (LOOPS_NORMAL);
|
if (current_loops)
|
if (current_loops)
|
scev_initialize ();
|
scev_initialize ();
|
htab_traverse (matrices_to_reorg, analyze_transpose, NULL);
|
htab_traverse (matrices_to_reorg, analyze_transpose, NULL);
|
if (current_loops)
|
if (current_loops)
|
{
|
{
|
scev_finalize ();
|
scev_finalize ();
|
loop_optimizer_finalize ();
|
loop_optimizer_finalize ();
|
current_loops = NULL;
|
current_loops = NULL;
|
}
|
}
|
}
|
}
|
/* If the current function is the allocation function for any of
|
/* If the current function is the allocation function for any of
|
the matrices we check its allocation and the escaping level. */
|
the matrices we check its allocation and the escaping level. */
|
htab_traverse (matrices_to_reorg, check_allocation_function, NULL);
|
htab_traverse (matrices_to_reorg, check_allocation_function, NULL);
|
free_dominance_info (CDI_DOMINATORS);
|
free_dominance_info (CDI_DOMINATORS);
|
free_dominance_info (CDI_POST_DOMINATORS);
|
free_dominance_info (CDI_POST_DOMINATORS);
|
pop_cfun ();
|
pop_cfun ();
|
current_function_decl = temp_fn;
|
current_function_decl = temp_fn;
|
bitmap_obstack_release (NULL);
|
bitmap_obstack_release (NULL);
|
}
|
}
|
htab_traverse (matrices_to_reorg, transform_allocation_sites, NULL);
|
htab_traverse (matrices_to_reorg, transform_allocation_sites, NULL);
|
/* Now transform the accesses. */
|
/* Now transform the accesses. */
|
for (node = cgraph_nodes; node; node = node->next)
|
for (node = cgraph_nodes; node; node = node->next)
|
if (node->analyzed)
|
if (node->analyzed)
|
{
|
{
|
/* Remember that allocation sites have been handled. */
|
/* Remember that allocation sites have been handled. */
|
tree temp_fn;
|
tree temp_fn;
|
|
|
temp_fn = current_function_decl;
|
temp_fn = current_function_decl;
|
current_function_decl = node->decl;
|
current_function_decl = node->decl;
|
push_cfun (DECL_STRUCT_FUNCTION (node->decl));
|
push_cfun (DECL_STRUCT_FUNCTION (node->decl));
|
bitmap_obstack_initialize (NULL);
|
bitmap_obstack_initialize (NULL);
|
gimple_register_cfg_hooks ();
|
gimple_register_cfg_hooks ();
|
record_all_accesses_in_func ();
|
record_all_accesses_in_func ();
|
htab_traverse (matrices_to_reorg, transform_access_sites, NULL);
|
htab_traverse (matrices_to_reorg, transform_access_sites, NULL);
|
cgraph_rebuild_references ();
|
cgraph_rebuild_references ();
|
free_dominance_info (CDI_DOMINATORS);
|
free_dominance_info (CDI_DOMINATORS);
|
free_dominance_info (CDI_POST_DOMINATORS);
|
free_dominance_info (CDI_POST_DOMINATORS);
|
pop_cfun ();
|
pop_cfun ();
|
current_function_decl = temp_fn;
|
current_function_decl = temp_fn;
|
bitmap_obstack_release (NULL);
|
bitmap_obstack_release (NULL);
|
}
|
}
|
htab_traverse (matrices_to_reorg, dump_matrix_reorg_analysis, NULL);
|
htab_traverse (matrices_to_reorg, dump_matrix_reorg_analysis, NULL);
|
|
|
current_function_decl = NULL;
|
current_function_decl = NULL;
|
set_cfun (NULL);
|
set_cfun (NULL);
|
matrices_to_reorg = NULL;
|
matrices_to_reorg = NULL;
|
return 0;
|
return 0;
|
}
|
}
|
|
|
|
|
/* The condition for matrix flattening to be performed. */
|
/* The condition for matrix flattening to be performed. */
|
static bool
|
static bool
|
gate_matrix_reorg (void)
|
gate_matrix_reorg (void)
|
{
|
{
|
return flag_ipa_matrix_reorg && flag_whole_program;
|
return flag_ipa_matrix_reorg && flag_whole_program;
|
}
|
}
|
|
|
struct simple_ipa_opt_pass pass_ipa_matrix_reorg =
|
struct simple_ipa_opt_pass pass_ipa_matrix_reorg =
|
{
|
{
|
{
|
{
|
SIMPLE_IPA_PASS,
|
SIMPLE_IPA_PASS,
|
"matrix-reorg", /* name */
|
"matrix-reorg", /* name */
|
gate_matrix_reorg, /* gate */
|
gate_matrix_reorg, /* gate */
|
matrix_reorg, /* execute */
|
matrix_reorg, /* execute */
|
NULL, /* sub */
|
NULL, /* sub */
|
NULL, /* next */
|
NULL, /* next */
|
0, /* static_pass_number */
|
0, /* static_pass_number */
|
TV_NONE, /* tv_id */
|
TV_NONE, /* tv_id */
|
0, /* properties_required */
|
0, /* properties_required */
|
0, /* properties_provided */
|
0, /* properties_provided */
|
0, /* properties_destroyed */
|
0, /* properties_destroyed */
|
0, /* todo_flags_start */
|
0, /* todo_flags_start */
|
TODO_dump_cgraph /* todo_flags_finish */
|
TODO_dump_cgraph /* todo_flags_finish */
|
}
|
}
|
};
|
};
|
|
|
