Subversion Repositories openrisc_2011-10-31

/* 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 "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 "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"

#include "tree-ssa-sccvn.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);

/* Calls to free when flattening a matrix.  */

struct free_info

{

  gimple stmt;

  tree func;

};

/* 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

  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 *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