CbC/CbC_gcc: gcc/matrix-reorg.c comparison

comparison gcc/matrix-reorg.c @ 0:a06113de4d67

first commit

author	kent <kent@cr.ie.u-ryukyu.ac.jp>
date	Fri, 17 Jul 2009 14:47:48 +0900
parents
children	77e2b8dfacca

comparison

equal deleted inserted replaced

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

Mercurial > hg > CbC > CbC_gcc

comparison gcc/matrix-reorg.c @ 0:a06113de4d67