OSDN Git Service

Fogot to commit ipa-struct-reorg.c ipa-struct-reorg.h.
authorolga <olga@138bc75d-0d04-0410-961f-82ee72b054a4>
Wed, 24 Oct 2007 12:48:41 +0000 (12:48 +0000)
committerolga <olga@138bc75d-0d04-0410-961f-82ee72b054a4>
Wed, 24 Oct 2007 12:48:41 +0000 (12:48 +0000)
git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@129601 138bc75d-0d04-0410-961f-82ee72b054a4

gcc/ipa-struct-reorg.c [new file with mode: 0644]
gcc/ipa-struct-reorg.h [new file with mode: 0644]

diff --git a/gcc/ipa-struct-reorg.c b/gcc/ipa-struct-reorg.c
new file mode 100644 (file)
index 0000000..9a04289
--- /dev/null
@@ -0,0 +1,3932 @@
+/* Struct-reorg optimization.
+   Copyright (C) 2007 Free Software Foundation, Inc.
+   Contributed by Olga Golovanevsky <olga@il.ibm.com>
+   (Initial version of this code was developed
+   by Caroline Tice and Mostafa 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 2, 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 COPYING.  If not, write to the Free
+Software Foundation, 59 Temple Place - Suite 330, Boston, MA
+02111-1307, USA.  */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
+#include "ggc.h"
+#include "tree.h"
+#include "rtl.h"
+#include "tree-gimple.h"
+#include "tree-inline.h"
+#include "tree-flow.h"
+#include "tree-flow-inline.h"
+#include "langhooks.h"
+#include "pointer-set.h"
+#include "hashtab.h"
+#include "c-tree.h"
+#include "toplev.h"
+#include "flags.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 "tree-iterator.h"
+#include "tree-pass.h"
+#include "ipa-struct-reorg.h"
+#include "opts.h"
+#include "ipa-type-escape.h"
+#include "tree-dump.h"
+#include "c-common.h"
+
+/* This optimization implements structure peeling.
+
+   For example, given a structure type:
+   typedef struct
+   {
+     int a;
+     float b;
+     int c;
+   }str_t;
+
+   it can be peeled into two structure types as follows:
+
+   typedef struct  and  typedef struct
+   {                    {
+     int a;               float b;
+     int c;             } str_t_1;
+   }str_t_0;
+
+   or can be fully peeled:
+
+   typedef struct
+   {
+     int a;
+   }str_t_0;
+
+   typedef struct
+   {
+     float b;
+   }str_t_1;
+
+   typedef struct
+   {
+     int c;
+   }str_t_2;
+
+   When structure type is peeled all instances and their accesses
+   in the program are updated accordingly. For example, if there is
+   array of structures:
+
+   str_t A[N];
+
+   and structure type str_t was peeled into two structures str_t_0
+   and str_t_1 as it was shown above, then array A will be replaced
+   by two arrays as follows:
+
+   str_t_0 A_0[N];
+   str_t_1 A_1[N];
+
+   The field access of field a of element i of array A: A[i].a will be
+   replaced by an access to field a of element i of array A_0: A_0[i].a.
+
+   This optimization also supports dynamically allocated arrays.
+   If array of structures was allocated by malloc function:
+
+   str_t * p = (str_t *) malloc (sizeof (str_t) * N)
+
+   the allocation site will be replaced to reflect new structure types:
+
+   str_t_0 * p_0 = (str_t_0 *) malloc (sizeof (str_t_0) * N)
+   str_t_1 * p_1 = (str_t_1 *) malloc (sizeof (str_t_1) * N)
+
+   The field access through the pointer p[i].a will be changed by p_0[i].a.
+
+   The goal of structure peeling is to improve spatial locality.
+   For example, if one of the fields of a structure is accessed frequently
+   in the loop:
+
+   for (i = 0; i < N; i++)
+   {
+     ... = A[i].a;
+   }
+
+   the allocation of field a of str_t contiguously in memory will
+   increase the chances of fetching the field from cache.
+
+   The analysis part of this optimization is based on the frequency of
+   field accesses, which are collected all over the program.
+   Then the fields with the frequencies that satisfy the following condition
+   get peeled out of the structure:
+
+   freq(f) > C * max_field_freq_in_struct
+
+   where max_field_freq_in_struct is the maximum field frequency
+   in the structure. C is a constant defining which portion of
+   max_field_freq_in_struct the fields should have in order to be peeled.
+
+   If profiling information is provided, it is used to calculate the
+   frequency of field accesses. Otherwise, the structure is fully peeled.
+
+   IPA type-escape analysis is used to determine when it is safe
+   to peel a structure.
+
+   The optimization is activated by flag -fipa-struct-reorg.  */
+
+/* New variables created by this optimization.
+   When doing struct peeling, each variable of
+   the original struct type will be replaced by
+   the set of new variables corresponding to
+   the new structure types.  */
+struct new_var_data {
+  /* VAR_DECL for original struct type.  */
+  tree orig_var;
+  /* Vector of new variables.  */
+  VEC(tree, heap) *new_vars;
+};
+
+typedef struct new_var_data *new_var;
+typedef const struct new_var_data *const_new_var;
+
+/* This structure represents allocation site of the structure.  */
+typedef struct alloc_site
+{
+  tree stmt;
+  d_str str;
+} alloc_site_t;
+
+DEF_VEC_O (alloc_site_t);
+DEF_VEC_ALLOC_O (alloc_site_t, heap);
+
+/* Allocation sites that belong to the same function.  */
+struct func_alloc_sites
+{
+  tree func;
+  /* Vector of allocation sites for function.  */
+  VEC (alloc_site_t, heap) *allocs;
+};
+
+typedef struct func_alloc_sites *fallocs_t;
+typedef const struct func_alloc_sites *const_fallocs_t;
+
+/* All allocation sites in the program.  */
+htab_t alloc_sites;
+
+/* New global variables. Generated once for whole program.  */
+htab_t new_global_vars;
+
+/* New local variables. Generated per-function.  */
+htab_t new_local_vars;
+
+/* Vector of structures to be transformed.  */
+typedef struct data_structure structure;
+DEF_VEC_O (structure);
+DEF_VEC_ALLOC_O (structure, heap);
+VEC (structure, heap) *structures;
+
+/* Forward declarations.  */
+static bool is_equal_types (tree, tree);
+
+/* Strip structure TYPE from pointers and arrays.  */
+
+static inline tree
+strip_type (tree type)
+{
+  gcc_assert (TYPE_P (type));
+
+  while (POINTER_TYPE_P (type)
+        || TREE_CODE (type) == ARRAY_TYPE)
+    type = TREE_TYPE (type);
+
+  return  type;
+}
+
+/* This function returns type of VAR.  */
+
+static inline tree
+get_type_of_var (tree var)
+{
+  if (!var)
+    return NULL;
+  
+  if (TREE_CODE (var) == PARM_DECL)
+      return DECL_ARG_TYPE (var);
+  else 
+    return TREE_TYPE (var);
+}
+
+/* Set of actions we do for each newly generated STMT.  */ 
+
+static inline void
+finalize_stmt (tree stmt)
+{
+  update_stmt (stmt);
+  mark_symbols_for_renaming (stmt);
+}
+
+/* This function finalizes STMT and appends it to the list STMTS.  */
+
+static inline void
+finalize_stmt_and_append (tree *stmts, tree stmt)
+{
+  append_to_statement_list (stmt, stmts);
+  finalize_stmt (stmt);
+}
+
+/* Given structure type SRT_TYPE and field FIELD, 
+   this function is looking for a field with the same name 
+   and type as FIELD in STR_TYPE. It returns it if found,
+   or NULL_TREE otherwise.  */
+
+static tree
+find_field_in_struct_1 (tree str_type, tree field)
+{
+  tree str_field;
+
+  for (str_field = TYPE_FIELDS (str_type); str_field; 
+       str_field = TREE_CHAIN (str_field))
+    {
+      const char * str_field_name;
+      const char * field_name;
+
+      str_field_name = IDENTIFIER_POINTER (DECL_NAME (str_field));
+      field_name = IDENTIFIER_POINTER (DECL_NAME (field));
+      
+      gcc_assert (str_field_name);
+      gcc_assert (field_name);
+
+      if (!strcmp (str_field_name, field_name))
+       {
+         /* Check field types.  */       
+         if (is_equal_types (TREE_TYPE (str_field), TREE_TYPE (field)))
+             return str_field;
+       }
+    }
+
+  return NULL_TREE;
+}
+
+/* Given a field declaration FIELD_DECL, this function 
+   returns corresponding field entry in structure STR.  */
+
+static struct field_entry *
+find_field_in_struct (d_str str, tree field_decl)
+{
+  int i;
+  
+  tree field = find_field_in_struct_1 (str->decl, field_decl);
+
+  for (i = 0; i < str->num_fields; i++)
+    if (str->fields[i].decl == field)
+      return &(str->fields[i]);
+
+  return NULL;
+}
+
+/* This function checks whether ARG is a result of multiplication 
+   of some number by STRUCT_SIZE. If yes, the function returns true 
+   and this number is filled into NUM.  */
+
+static bool
+is_result_of_mult (tree arg, tree *num, tree struct_size)
+{
+  tree size_def_stmt = SSA_NAME_DEF_STMT (arg);
+
+  /* If allocation  statementt was of the form 
+     D.2229_10 = <alloc_func> (D.2228_9);
+     then size_def_stmt can be D.2228_9 = num.3_8 * 8;  */
+
+  if (size_def_stmt && TREE_CODE (size_def_stmt) == GIMPLE_MODIFY_STMT)
+    {
+      tree lhs = GIMPLE_STMT_OPERAND (size_def_stmt, 0);
+      tree rhs = GIMPLE_STMT_OPERAND (size_def_stmt, 1);
+
+      /* We expect temporary here.  */
+      if (!is_gimple_reg (lhs))        
+       return false;
+
+      if (TREE_CODE (rhs) == MULT_EXPR)
+       {
+         tree arg0 = TREE_OPERAND (rhs, 0);
+         tree arg1 = TREE_OPERAND (rhs, 1);
+
+         if (operand_equal_p (arg0, struct_size, OEP_ONLY_CONST))
+           {
+             *num = arg1;
+             return true;
+           }
+
+         if (operand_equal_p (arg1, struct_size, OEP_ONLY_CONST))
+           {
+             *num = arg0;
+             return true;
+           }
+       }
+    }
+
+  *num = NULL_TREE;
+  return false;
+}
+
+
+/* This function returns true if access ACC corresponds to the pattern
+   generated by compiler when an address of element i of an array 
+   of structures STR_DECL (pointed by p) is calculated (p[i]). If this 
+   pattern is recognized correctly, this function returns true
+   and fills missing fields in ACC. Otherwise it returns false.  */
+
+static bool
+decompose_indirect_ref_acc (tree str_decl, struct field_access_site *acc)
+{
+  tree ref_var;
+  tree rhs, struct_size, op0, op1;
+  tree before_cast;
+  ref_var = TREE_OPERAND (acc->ref, 0);
+
+  if (TREE_CODE (ref_var) != SSA_NAME)
+    return false;
+
+  acc->ref_def_stmt = SSA_NAME_DEF_STMT (ref_var);
+  if (!(acc->ref_def_stmt)
+      || (TREE_CODE (acc->ref_def_stmt) != GIMPLE_MODIFY_STMT))
+    return false;
+
+  rhs = GIMPLE_STMT_OPERAND (acc->ref_def_stmt, 1);
+
+  if (TREE_CODE (rhs) != PLUS_EXPR
+      && TREE_CODE (rhs)!= MINUS_EXPR
+      && TREE_CODE (rhs) != POINTER_PLUS_EXPR)
+    return false;
+
+  op0 = TREE_OPERAND (rhs, 0);
+  op1 = TREE_OPERAND (rhs, 1);
+
+  if (!is_array_access_through_pointer_and_index (TREE_CODE (rhs), op0, op1, 
+                                                &acc->base, &acc->offset, 
+                                                &acc->cast_stmt))
+    return false;
+
+  if (acc->cast_stmt)
+    before_cast = SINGLE_SSA_TREE_OPERAND (acc->cast_stmt, SSA_OP_USE);
+  else
+    before_cast = acc->offset;
+
+  if (!before_cast)
+    return false;
+
+
+  if (SSA_NAME_IS_DEFAULT_DEF (before_cast))
+    return false; 
+
+  struct_size = TYPE_SIZE_UNIT (str_decl);
+
+  if (!is_result_of_mult (before_cast, &acc->num, struct_size))
+    return false;
+
+  return true;
+}
+
+
+/* This function checks whether the access ACC of structure type STR 
+   is of the form suitable for tranformation. If yes, it returns true. 
+   False otherwise.  */
+
+static bool
+decompose_access (tree str_decl, struct field_access_site *acc)
+{
+  gcc_assert (acc->ref);
+
+  if (TREE_CODE (acc->ref) == INDIRECT_REF)
+    return decompose_indirect_ref_acc (str_decl, acc);
+  else if (TREE_CODE (acc->ref) == ARRAY_REF)
+    return true;
+  else if (TREE_CODE (acc->ref) == VAR_DECL)
+    return true;
+
+  return false;
+}
+
+/* This function creates empty field_access_site node.  */
+
+static inline struct field_access_site *
+make_field_acc_node (void)
+{
+  int size = sizeof (struct field_access_site);
+
+  return (struct field_access_site *) xcalloc (1, size);
+}
+
+/* This function returns the structure field access, defined by STMT,
+   if it is aready in hashtable of function accesses F_ACCS.  */
+
+static struct field_access_site *
+is_in_field_accs (tree stmt, htab_t f_accs)
+{
+  return (struct field_access_site *) 
+    htab_find_with_hash (f_accs, stmt, htab_hash_pointer (stmt));
+}
+
+/* This function adds an access ACC to the hashtable 
+   F_ACCS of field accesses.  */
+
+static void
+add_field_acc_to_acc_sites (struct field_access_site *acc, 
+                           htab_t f_accs)
+{
+  void **slot;
+  
+  gcc_assert (!is_in_field_accs (acc->stmt, f_accs));
+  slot = htab_find_slot_with_hash (f_accs, acc->stmt,
+                                  htab_hash_pointer (acc->stmt), 
+                                  INSERT);
+  *slot = acc;  
+}
+
+/* This function adds the VAR to vector of variables of 
+   an access site defined by statement STMT. If access entry 
+   with statement STMT does not exist in hashtable of 
+   accesses ACCS, this function creates it.  */ 
+
+static void
+add_access_to_acc_sites (tree stmt, tree var, htab_t accs)
+{
+   struct access_site *acc;
+
+   acc = (struct access_site *) 
+     htab_find_with_hash (accs,        stmt, htab_hash_pointer (stmt));
+
+   if (!acc)
+     {
+       void **slot;
+
+       acc = (struct access_site *) xmalloc (sizeof (struct access_site));
+       acc->stmt = stmt;
+       acc->vars = VEC_alloc (tree, heap, 10);
+       slot = htab_find_slot_with_hash (accs, stmt,
+                                       htab_hash_pointer (stmt), INSERT);
+       *slot = acc;
+
+     }  
+   VEC_safe_push (tree, heap, acc->vars, var);
+}
+
+/* This function adds NEW_DECL to function 
+   referenced vars, and marks it for renaming.  */
+
+static void
+finalize_var_creation (tree new_decl)
+{
+  add_referenced_var (new_decl);  
+  if (is_global_var (new_decl))
+    mark_call_clobbered (new_decl, ESCAPE_UNKNOWN);
+  mark_sym_for_renaming (new_decl); 
+}
+
+/* This function finalizes VAR creation if it is a global VAR_DECL.  */
+
+static void
+finalize_global_creation (tree var)
+{
+  if (TREE_CODE (var) == VAR_DECL
+      && is_global_var (var))
+    finalize_var_creation (var);
+}
+
+/* This function inserts NEW_DECL to varpool.  */
+
+static inline void
+insert_global_to_varpool (tree new_decl)
+{
+  struct varpool_node *new_node;
+
+  new_node = varpool_node (new_decl);
+  notice_global_symbol (new_decl);
+  varpool_mark_needed_node (new_node);
+  varpool_finalize_decl (new_decl);
+}
+
+/* This function finalizes the creation of new variables, 
+   defined by *SLOT->new_vars.  */ 
+
+static int
+finalize_new_vars_creation (void **slot, void *data ATTRIBUTE_UNUSED)
+{
+  new_var n_var = *(new_var *) slot;
+  unsigned i;
+  tree var;
+
+  for (i = 0; VEC_iterate (tree, n_var->new_vars, i, var); i++)
+    finalize_var_creation (var);
+  return 1;
+}
+
+/* This funciton updates statements in STMT_LIST with BB info.  */
+
+static void
+add_bb_info (basic_block bb, tree stmt_list)
+{
+  if (TREE_CODE (stmt_list) == STATEMENT_LIST)
+    {
+      tree_stmt_iterator tsi;
+      for (tsi = tsi_start (stmt_list); !tsi_end_p (tsi); tsi_next (&tsi))
+       {
+         tree stmt = tsi_stmt (tsi);
+
+         set_bb_for_stmt (stmt, bb);
+       }
+    }
+}
+
+/* This function looks for the variable of NEW_TYPE type, stored in VAR.
+   It returns it, if found, and NULL_TREE otherwise.  */
+
+static tree
+find_var_in_new_vars_vec (new_var var, tree new_type)
+{
+  tree n_var;
+  unsigned i;
+
+  for (i = 0; VEC_iterate (tree, var->new_vars, i, n_var); i++)
+    {
+      tree type = strip_type(get_type_of_var (n_var));
+      gcc_assert (type);
+      
+      if (type == new_type)
+       return n_var;
+    }
+
+  return NULL_TREE;
+}
+
+/* This function returns new_var node, the orig_var of which is DECL.
+   It looks for new_var's in NEW_VARS_HTAB. If not found, 
+   the function returns NULL.  */
+
+static new_var
+is_in_new_vars_htab (tree decl, htab_t new_vars_htab)
+{
+  return (new_var) htab_find_with_hash (new_vars_htab, decl,
+                                       htab_hash_pointer (decl));
+}
+
+/* Given original varaiable ORIG_VAR, this function returns
+   new variable corresponding to it of NEW_TYPE type. */
+
+static tree
+find_new_var_of_type (tree orig_var, tree new_type)
+{
+  new_var var;
+  gcc_assert (orig_var && new_type);
+
+  if (TREE_CODE (orig_var) == SSA_NAME)
+    orig_var = SSA_NAME_VAR (orig_var);
+
+  var = is_in_new_vars_htab (orig_var, new_global_vars);
+  if (!var)
+    var = is_in_new_vars_htab (orig_var, new_local_vars);
+  gcc_assert (var);
+  return find_var_in_new_vars_vec (var, new_type);
+}
+
+/* This function generates stmt:
+   res = NUM * sizeof(TYPE) and returns it.
+   res is filled into RES.  */
+
+static tree
+gen_size (tree num, tree type, tree *res)
+{
+  tree struct_size = TYPE_SIZE_UNIT (type);
+  HOST_WIDE_INT struct_size_int = TREE_INT_CST_LOW (struct_size);
+  tree new_stmt;
+
+  *res = create_tmp_var (TREE_TYPE (num), NULL);
+
+  if (*res)
+    add_referenced_var (*res);
+
+  if (exact_log2 (struct_size_int) == -1)
+    new_stmt = build_gimple_modify_stmt (num, struct_size);
+  else
+    {
+      tree C = build_int_cst (TREE_TYPE (num), exact_log2 (struct_size_int));
+      new_stmt = build_gimple_modify_stmt (*res, build2 (LSHIFT_EXPR, 
+                                                        TREE_TYPE (num),
+                                                        num, C));
+    }
+
+  finalize_stmt (new_stmt);
+  return new_stmt;
+}
+
+/* This function generates and returns a statement, that cast variable 
+   BEFORE_CAST to NEW_TYPE. The cast result variable is stored 
+   into RES_P. ORIG_CAST_STMT is the original cast statement.  */
+
+static tree
+gen_cast_stmt (tree before_cast, tree new_type, tree orig_cast_stmt,
+              tree *res_p)
+{
+  tree lhs, new_lhs, new_stmt;
+  gcc_assert (TREE_CODE (orig_cast_stmt) == GIMPLE_MODIFY_STMT);
+    
+  lhs = GIMPLE_STMT_OPERAND (orig_cast_stmt, 0);
+  new_lhs = find_new_var_of_type (lhs, new_type);
+  gcc_assert (new_lhs);
+
+  new_stmt = build_gimple_modify_stmt (new_lhs, 
+                                      build1 (NOP_EXPR, 
+                                              TREE_TYPE (new_lhs),
+                                              before_cast));
+  finalize_stmt (new_stmt);
+  *res_p = new_lhs;
+  return new_stmt;
+}
+
+/* This function builds an edge between BB and E->dest and updates
+   phi nodes of E->dest. It returns newly created edge.  */
+
+static edge
+make_edge_and_fix_phis_of_dest (basic_block bb, edge e)
+{
+  edge new_e;
+  tree phi, arg;
+                     
+  new_e = make_edge (bb, e->dest, e->flags);
+
+  for (phi = phi_nodes (new_e->dest); phi; phi = PHI_CHAIN (phi))
+    {
+      arg = PHI_ARG_DEF_FROM_EDGE (phi, e);
+      add_phi_arg (phi, arg, new_e); 
+    }
+
+  return new_e;
+}
+
+/* This function inserts NEW_STMTS before STMT.  */
+
+static void
+insert_before_stmt (tree stmt, tree new_stmts)
+{
+  block_stmt_iterator bsi;
+
+  if (!stmt || !new_stmts)
+    return;
+
+  bsi = bsi_for_stmt (stmt); 
+  bsi_insert_before (&bsi, new_stmts, BSI_SAME_STMT);   
+}
+
+/* Insert NEW_STMTS after STMT.  */
+
+static void
+insert_after_stmt (tree stmt, tree new_stmts)
+{
+  block_stmt_iterator bsi;
+
+  if (!stmt || !new_stmts)
+    return;
+
+  bsi = bsi_for_stmt (stmt); 
+  bsi_insert_after (&bsi, new_stmts, BSI_SAME_STMT);   
+}
+
+/* This function returns vector of allocation sites
+   that appear in function FN_DECL.  */
+
+static fallocs_t
+get_fallocs (tree fn_decl)
+{  
+  return (fallocs_t) htab_find_with_hash (alloc_sites, fn_decl,
+                                        htab_hash_pointer (fn_decl));
+}
+
+/* If ALLOC_STMT is D.2225_7 = <alloc_func> (D.2224_6);
+   and it is a part of allocation of a structure,
+   then it is usually followed by a cast stmt 
+   p_8 = (struct str_t *) D.2225_7;
+   which is returned by this function.  */
+
+static tree
+get_final_alloc_stmt (tree alloc_stmt)
+{
+  tree final_stmt;
+  use_operand_p use_p;
+  tree alloc_res;
+
+  if (!alloc_stmt)
+    return NULL;
+  
+  if (TREE_CODE (alloc_stmt) != GIMPLE_MODIFY_STMT)
+    return NULL;
+
+  alloc_res = GIMPLE_STMT_OPERAND (alloc_stmt, 0);
+
+  if (TREE_CODE (alloc_res) != SSA_NAME)
+    return NULL;
+
+  if (!single_imm_use (alloc_res, &use_p, &final_stmt))
+    return NULL;
+  else
+    return final_stmt;
+}
+
+/* This function returns true if STMT is one of allocation 
+   sites of function FN_DECL. It returns false otherwise.  */
+
+static bool
+is_part_of_malloc (tree stmt, tree fn_decl)
+{
+  fallocs_t fallocs = get_fallocs (fn_decl);
+  
+  if (fallocs)
+    {
+      alloc_site_t *call;
+      unsigned i;
+
+      for (i = 0;
+          VEC_iterate (alloc_site_t, fallocs->allocs, i, call); i++)
+       if (call->stmt == stmt
+           || get_final_alloc_stmt (call->stmt) == stmt)
+         return true;
+    }
+  return false;
+}
+
+/* Auxiliary structure for a lookup over field accesses. */
+struct find_stmt_data
+{
+  bool found;
+  tree stmt;
+};
+
+/* This function looks for DATA->stmt among 
+   the statements involved in the field access, 
+   defined by SLOT. It stops when it's found. */
+
+static int
+find_in_field_accs (void **slot, void *data)
+{
+  struct field_access_site *f_acc = 
+    *(struct field_access_site **) slot;
+  tree stmt = ((struct find_stmt_data *)data)->stmt;
+
+  if (f_acc->stmt == stmt
+      || f_acc->ref_def_stmt == stmt
+      || f_acc->cast_stmt == stmt)
+    {
+      ((struct find_stmt_data *)data)->found = true;
+      return 0;
+    }
+  else
+    return 1;
+}
+
+/* This function checks whether STMT is part of field
+   accesses of structure STR. It returns true, if found,
+   and false otherwise.  */
+
+static bool
+is_part_of_field_access (tree stmt, d_str str)
+{
+  int i;
+
+  for (i = 0; i < str->num_fields; i++)
+    {
+      struct find_stmt_data data;
+      data.found = false;
+      data.stmt = stmt;
+
+      if (str->fields[i].acc_sites)
+       htab_traverse (str->fields[i].acc_sites, find_in_field_accs, &data);
+
+      if (data.found)
+       return true;
+    }
+
+  return false;
+}
+
+/* Auxiliary data for exclude_from_accs function.  */
+
+struct exclude_data
+{
+  tree fn_decl;
+  d_str str;
+};
+
+/* This function returns component_ref with the BASE and 
+   field named FIELD_ID from structure TYPE.  */
+
+static inline tree
+build_comp_ref (tree base, tree field_id, tree type)
+{
+  tree field;
+  bool found = false;
+  
+
+  /* Find field of structure type with the same name as field_id. */
+  for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
+    {
+      if (DECL_NAME (field) == field_id)
+       {
+         found = true;
+         break;
+       }
+    }
+
+  gcc_assert (found);
+
+  return build3 (COMPONENT_REF, TREE_TYPE (field), base, field, NULL_TREE);
+}
+
+
+/* This struct represent data used for walk_tree 
+   called from function find_pos_in_stmt.
+   - ref is a tree to be found, 
+   - and pos is a pointer that points to ref in stmt.  */
+struct ref_pos
+{
+  tree *pos;
+  tree ref;
+};
+
+
+/* This is a callback function for walk_tree, called from 
+   collect_accesses_in_bb function. DATA is a pointer to ref_pos structure.
+   When *TP is equal to DATA->ref, the walk_tree stops,
+   and found position, equal to TP, is assigned to DATA->pos.  */
+
+static tree
+find_pos_in_stmt_1 (tree *tp, int *walk_subtrees, void * data)
+{
+  struct ref_pos * r_pos = (struct ref_pos *) data;
+  tree ref = r_pos->ref;
+  tree t = *tp;
+
+  if (t == ref)
+    {
+      r_pos->pos = tp;
+      return t;
+    }
+
+  switch (TREE_CODE (t))
+    {
+    case GIMPLE_MODIFY_STMT:
+      {
+       tree lhs = GIMPLE_STMT_OPERAND (t, 0);
+       tree rhs = GIMPLE_STMT_OPERAND (t, 1);
+       *walk_subtrees = 1;
+       walk_tree (&lhs, find_pos_in_stmt_1, data, NULL);
+       walk_tree (&rhs, find_pos_in_stmt_1, data, NULL);
+       *walk_subtrees = 0;         
+      }
+      break;
+
+    default:
+      *walk_subtrees = 1;      
+    }
+    return NULL_TREE;
+}
+
+
+/* This function looks for the pointer of REF in STMT,
+   It returns it, if found, and NULL otherwise.  */
+
+static tree *
+find_pos_in_stmt (tree stmt, tree ref)
+{
+  struct ref_pos r_pos;
+
+  r_pos.ref = ref;
+  r_pos.pos = NULL;
+  walk_tree (&stmt, find_pos_in_stmt_1, &r_pos, NULL);
+
+  return r_pos.pos;
+}
+
+/* This structure is used to represent array 
+   or pointer-to wrappers of structure type.
+   For example, if type1 is structure type, 
+   then for type1 ** we generate two type_wrapper 
+   structures with wrap = 0 each one.  
+   It's used to unwind the original type up to 
+   structure type, replace it with the new structure type 
+   and wrap it back in the opposite order.  */
+
+typedef struct type_wrapper
+{
+  /* 0 stand for pointer wrapper, and 1 for array wrapper.  */
+  bool wrap;
+
+  /* Relevant for arrays as domain or index.  */
+  tree domain; 
+}type_wrapper_t;
+
+DEF_VEC_O (type_wrapper_t);
+DEF_VEC_ALLOC_O (type_wrapper_t, heap);
+
+/* This function replace field access ACC by the new 
+   field access of structure type NEW_TYPE.  */
+
+static void
+replace_field_acc (struct field_access_site *acc, tree new_type)
+{
+  tree ref_var = acc->ref;
+  tree new_ref;
+  tree lhs, rhs;
+  tree *pos;
+  tree new_acc;
+  tree field_id = DECL_NAME (acc->field_decl);
+  VEC (type_wrapper_t, heap) *wrapper = VEC_alloc (type_wrapper_t, heap, 10);
+  type_wrapper_t wr;
+  type_wrapper_t *wr_p = NULL;
+  
+  while (TREE_CODE (ref_var) == INDIRECT_REF
+        || TREE_CODE (ref_var) == ARRAY_REF)
+    {
+      if ( TREE_CODE (ref_var) == INDIRECT_REF)
+       {
+         wr.wrap = 0;
+         wr.domain = 0;
+       }
+      else if (TREE_CODE (ref_var) == ARRAY_REF)
+       {
+         wr.wrap = 1;
+         wr.domain = TREE_OPERAND (ref_var, 1);
+       }
+
+      VEC_safe_push (type_wrapper_t, heap, wrapper, &wr);
+      ref_var = TREE_OPERAND (ref_var, 0);
+    }
+
+  new_ref = find_new_var_of_type (ref_var, new_type);
+  finalize_global_creation (new_ref);
+
+  while (VEC_length (type_wrapper_t, wrapper) != 0)
+    {
+      tree type = TREE_TYPE (TREE_TYPE (new_ref));
+
+      wr_p = VEC_last (type_wrapper_t, wrapper); 
+      if (wr_p->wrap) /* Array.  */
+       new_ref = build4 (ARRAY_REF, type, new_ref, 
+                         wr_p->domain, NULL_TREE, NULL_TREE);
+      else /* Pointer.  */
+       new_ref = build1 (INDIRECT_REF, type, new_ref);
+      VEC_pop (type_wrapper_t, wrapper);
+    }
+
+  new_acc = build_comp_ref (new_ref, field_id, new_type);
+  VEC_free (type_wrapper_t, heap, wrapper);  
+
+  if (TREE_CODE (acc->stmt) == GIMPLE_MODIFY_STMT)
+    {      
+      lhs = GIMPLE_STMT_OPERAND (acc->stmt, 0);
+      rhs = GIMPLE_STMT_OPERAND (acc->stmt, 1);
+      
+       
+      if (lhs == acc->comp_ref)
+       GIMPLE_STMT_OPERAND (acc->stmt, 0) = new_acc;
+      else if (rhs == acc->comp_ref)
+       GIMPLE_STMT_OPERAND (acc->stmt, 1) = new_acc;
+      else
+       {
+         pos = find_pos_in_stmt (acc->stmt, acc->comp_ref);
+         gcc_assert (pos);
+         *pos = new_acc;
+       }
+    }
+  else
+    {
+      pos = find_pos_in_stmt (acc->stmt, acc->comp_ref);
+      gcc_assert (pos);
+      *pos = new_acc;
+    }
+  
+  finalize_stmt (acc->stmt);
+}
+
+/* This function replace field access ACC by a new field access 
+   of structure type NEW_TYPE.  */
+
+static void
+replace_field_access_stmt (struct field_access_site *acc, tree new_type)
+{
+
+  if (TREE_CODE (acc->ref) == INDIRECT_REF
+      ||TREE_CODE (acc->ref) == ARRAY_REF
+      ||TREE_CODE (acc->ref) == VAR_DECL)
+    replace_field_acc (acc, new_type);
+  else
+    gcc_unreachable ();
+}
+
+/* This function looks for d_str, represented by TYPE, in the structures 
+   vector. If found, it returns an index of found structure. Otherwise 
+   it returns a length of the structures vector.  */
+static unsigned
+find_structure (tree type)
+{
+  d_str str;
+  unsigned i;
+
+  type = TYPE_MAIN_VARIANT (type);
+
+  for (i = 0; VEC_iterate (structure, structures, i, str); i++)
+    if (is_equal_types (str->decl, type))
+      return i;
+
+  return VEC_length (structure, structures);
+}
+
+/* In this function we create new statements that have the same
+   form as ORIG_STMT, but of type NEW_TYPE. The statements 
+   treated by this function are simple assignments, 
+   like assignments:  p.8_7 = p; or statements with rhs of 
+   tree codes PLUS_EXPR and MINUS_EXPR.  */
+
+static tree
+create_base_plus_offset (tree orig_stmt, tree new_type, 
+                        tree offset)
+{
+  tree lhs, rhs;
+  tree new_lhs, new_rhs;
+  tree new_stmt;
+
+  gcc_assert (TREE_CODE (orig_stmt) == GIMPLE_MODIFY_STMT);
+
+  lhs = GIMPLE_STMT_OPERAND (orig_stmt, 0);
+  rhs = GIMPLE_STMT_OPERAND (orig_stmt, 1);
+
+  gcc_assert (TREE_CODE (lhs) == VAR_DECL
+             || TREE_CODE (lhs) == SSA_NAME);
+  
+  new_lhs = find_new_var_of_type (lhs, new_type);
+  gcc_assert (new_lhs);
+  finalize_var_creation (new_lhs);
+
+  switch (TREE_CODE (rhs))
+    {
+    case PLUS_EXPR:
+    case MINUS_EXPR:
+    case POINTER_PLUS_EXPR:
+      {
+       tree op0 = TREE_OPERAND (rhs, 0);
+       tree op1 = TREE_OPERAND (rhs, 1);
+       tree new_op0 = NULL_TREE, new_op1 = NULL_TREE;
+       unsigned str0, str1;
+       unsigned length = VEC_length (structure, structures);
+       
+
+       str0 = find_structure (strip_type (get_type_of_var (op0)));     
+       str1 = find_structure (strip_type (get_type_of_var (op1)));
+       gcc_assert ((str0 != length) || (str1 != length));
+       
+       if (str0 != length)
+         new_op0 = find_new_var_of_type (op0, new_type);
+       if (str1 != length)
+         new_op1 = find_new_var_of_type (op1, new_type);
+
+       if (!new_op0)
+         new_op0 = offset;
+       if (!new_op1)
+         new_op1 = offset;
+
+       new_rhs = build2 (TREE_CODE (rhs), TREE_TYPE (new_op0), 
+                         new_op0, new_op1);
+      }
+      break;
+
+    default:
+      gcc_unreachable();
+    }
+  
+  new_stmt = build_gimple_modify_stmt (new_lhs, new_rhs);
+  finalize_stmt (new_stmt);    
+
+  return new_stmt;
+}
+
+/* Given a field access F_ACC of the FIELD, this function 
+   replaces it by the new field access.  */
+
+static void
+create_new_field_access (struct field_access_site *f_acc,
+                        struct field_entry field)
+{
+  tree new_type = field.field_mapping;
+  tree new_stmt;
+  tree size_res;
+  tree mult_stmt, cast_stmt;
+  tree cast_res = NULL;
+  
+  if (f_acc->num)
+    {
+      mult_stmt = gen_size (f_acc->num, new_type, &size_res);
+      insert_before_stmt (f_acc->ref_def_stmt, mult_stmt);
+    }
+
+  if (f_acc->cast_stmt)
+    {
+      cast_stmt = gen_cast_stmt (size_res, new_type, 
+                                f_acc->cast_stmt, &cast_res);
+      insert_after_stmt (f_acc->cast_stmt, cast_stmt);
+    }
+
+  if (f_acc->ref_def_stmt)
+    {
+      tree offset;
+      if (cast_res)
+       offset = cast_res;
+      else
+       offset = size_res;
+
+      new_stmt = create_base_plus_offset (f_acc->ref_def_stmt, 
+                                         new_type, offset);
+      insert_after_stmt (f_acc->ref_def_stmt, new_stmt);
+    }
+
+  /* In stmt D.2163_19 = D.2162_18->b; we replace variable
+   D.2162_18 by an appropriate variable of new_type type.  */
+  replace_field_access_stmt (f_acc, new_type);
+}
+
+/* This function creates a new condition statement 
+   corresponding to the original COND_STMT, adds new basic block
+   and redirects condition edges. NEW_VAR is a new condition 
+   variable located in the condition statement at the position POS.  */
+
+static void
+create_new_stmts_for_cond_expr_1 (tree new_var, tree cond_stmt, bool pos)
+{
+  tree new_cond;
+  tree new_stmt;
+  edge true_e = NULL, false_e = NULL;
+  basic_block new_bb;
+  tree stmt_list;
+
+  extract_true_false_edges_from_block (bb_for_stmt (cond_stmt),
+                                      &true_e, &false_e);
+
+  new_cond = unshare_expr (COND_EXPR_COND (cond_stmt));
+
+  TREE_OPERAND (new_cond, pos) = new_var;
+                                     
+  new_stmt = build3 (COND_EXPR, TREE_TYPE (cond_stmt),
+                    new_cond, NULL_TREE, NULL_TREE);
+
+  finalize_stmt (new_stmt);
+
+  /* Create new basic block after bb.  */
+  new_bb = create_empty_bb (bb_for_stmt (cond_stmt));
+
+  /* Add new condition stmt to the new_bb.  */
+  stmt_list = bb_stmt_list (new_bb);
+  append_to_statement_list (new_stmt, &stmt_list);
+  add_bb_info (new_bb, stmt_list);
+
+                 
+  /* Create false and true edges from new_bb.  */
+  make_edge_and_fix_phis_of_dest (new_bb, true_e);
+  make_edge_and_fix_phis_of_dest (new_bb, false_e);
+                 
+  /* Redirect one of original edges to point to new_bb.  */
+  if (TREE_CODE (cond_stmt) == NE_EXPR)
+    redirect_edge_succ (true_e, new_bb);
+  else
+    redirect_edge_succ (false_e, new_bb);
+}
+
+/* This function creates new condition statements corresponding 
+   to original condition STMT, one for each new type, and 
+   recursively redirect edges to newly generated basic blocks.  */
+
+static void
+create_new_stmts_for_cond_expr (tree stmt)
+{
+  tree cond = COND_EXPR_COND (stmt);
+  tree arg0, arg1, arg;
+  unsigned str0, str1;
+  bool s0, s1;
+  d_str str;
+  tree type;
+  bool pos;
+  int i;
+  unsigned length = VEC_length (structure, structures);
+
+  gcc_assert (TREE_CODE (cond) == EQ_EXPR
+             || TREE_CODE (cond) == NE_EXPR);
+
+  arg0 = TREE_OPERAND (cond, 0);
+  arg1 = TREE_OPERAND (cond, 1);
+
+  str0 = find_structure (strip_type (get_type_of_var (arg0)));
+  str1 = find_structure (strip_type (get_type_of_var (arg1)));
+
+  s0 = (str0 != length) ? true : false;
+  s1 = (str1 != length) ? true : false;
+
+  gcc_assert ((!s0 && s1) || (!s1 && s0));
+  
+  str = s0 ? VEC_index (structure, structures, str0): 
+    VEC_index (structure, structures, str1);
+  arg = s0 ? arg0 : arg1;
+  pos = s0 ? 0 : 1;
+  
+  for (i = 0; VEC_iterate (tree, str->new_types, i, type); i++)
+    {
+      tree new_arg;
+
+      new_arg = find_new_var_of_type (arg, type);
+      create_new_stmts_for_cond_expr_1 (new_arg, stmt, pos);
+    }
+}
+
+/* Create a new general access to replace original access ACC
+   for structure type NEW_TYPE.  */
+
+static tree
+create_general_new_stmt (struct access_site *acc, tree new_type)
+{
+  tree old_stmt = acc->stmt;
+  tree var;
+  tree new_stmt = unshare_expr (old_stmt);
+  unsigned i;
+
+  
+  for (i = 0; VEC_iterate (tree, acc->vars, i, var); i++)
+    {
+      tree *pos;
+      tree new_var = find_new_var_of_type (var, new_type);
+      tree lhs, rhs;
+
+      gcc_assert (new_var);
+      finalize_var_creation (new_var);
+
+      if (TREE_CODE (new_stmt) == GIMPLE_MODIFY_STMT)
+       {
+      
+         lhs = GIMPLE_STMT_OPERAND (new_stmt, 0);
+         rhs = GIMPLE_STMT_OPERAND (new_stmt, 1);
+         
+         if (TREE_CODE (lhs) == SSA_NAME)
+           lhs = SSA_NAME_VAR (lhs);
+         if (TREE_CODE (rhs) == SSA_NAME)
+           rhs = SSA_NAME_VAR (rhs); 
+
+         /* It can happen that rhs is a constructor.
+          Then we have to replace it to be of new_type.  */
+         if (TREE_CODE (rhs) == CONSTRUCTOR)
+           {
+             /* Dealing only with empty constructors right now.  */
+             gcc_assert (VEC_empty (constructor_elt, 
+                                    CONSTRUCTOR_ELTS (rhs)));
+             rhs = build_constructor (new_type, 0);
+             GIMPLE_STMT_OPERAND (new_stmt, 1) = rhs;
+           }
+         
+         if (lhs == var)
+           GIMPLE_STMT_OPERAND (new_stmt, 0) = new_var;
+         else if (rhs == var)
+           GIMPLE_STMT_OPERAND (new_stmt, 1) = new_var;
+         else
+           {
+             pos = find_pos_in_stmt (new_stmt, var);
+             gcc_assert (pos);
+             *pos = new_var;
+           }      
+       }
+      else
+       {
+         pos = find_pos_in_stmt (new_stmt, var);
+         gcc_assert (pos);
+         *pos = new_var;
+       }
+    }
+
+  finalize_stmt (new_stmt);
+  return new_stmt;
+}
+
+/* For each new type in STR this function creates new general accesses
+   corresponding to the original access ACC.  */
+
+static void
+create_new_stmts_for_general_acc (struct access_site *acc, d_str str)
+{
+  tree type;
+  tree stmt = acc->stmt;
+  unsigned i;
+
+  for (i = 0; VEC_iterate (tree, str->new_types, i, type); i++)
+    {
+      tree new_stmt;
+
+      new_stmt = create_general_new_stmt (acc, type);
+      insert_after_stmt (stmt, new_stmt);
+    }
+}
+
+/* This function creates a new general access of structure STR 
+   to replace the access ACC.  */
+
+static void
+create_new_general_access (struct access_site *acc, d_str str)
+{
+  tree stmt = acc->stmt;
+  switch (TREE_CODE (stmt))
+    {
+    case COND_EXPR:
+      create_new_stmts_for_cond_expr (stmt);
+      break;
+
+    default:
+      create_new_stmts_for_general_acc (acc, str);
+    }
+}
+
+/* Auxiliary data for creation of accesses.  */
+struct create_acc_data
+{
+  basic_block bb;
+  d_str str;
+  int field_index;
+};
+
+/* This function creates a new general access, defined by SLOT.
+   DATA is a pointer to create_acc_data structure.  */
+
+static int
+create_new_acc (void **slot, void *data)
+{
+  struct access_site *acc = *(struct access_site **) slot;
+  basic_block bb = ((struct create_acc_data *)data)->bb;
+  d_str str = ((struct create_acc_data *)data)->str;
+
+  if (bb_for_stmt (acc->stmt) == bb)
+    create_new_general_access (acc, str);
+  return 1;
+}
+
+/* This function creates a new field access, defined by SLOT.
+   DATA is a pointer to create_acc_data structure.  */
+
+static int
+create_new_field_acc (void **slot, void *data)
+{
+  struct field_access_site *f_acc = *(struct field_access_site **) slot;
+  basic_block bb = ((struct create_acc_data *)data)->bb;
+  d_str str = ((struct create_acc_data *)data)->str;
+  int i = ((struct create_acc_data *)data)->field_index;
+
+  if (bb_for_stmt (f_acc->stmt) == bb)
+    create_new_field_access (f_acc, str->fields[i]);
+  return 1;
+}
+
+/* This function creates new accesses for the structure 
+   type STR in basic block BB.  */
+
+static void
+create_new_accs_for_struct (d_str str, basic_block bb)
+{
+  int i;
+  struct create_acc_data dt;
+
+  dt.str = str;
+  dt.bb = bb;
+  dt.field_index = -1;
+      
+  for (i = 0; i < str->num_fields; i++)
+    {
+      dt.field_index = i;
+
+      if (str->fields[i].acc_sites)
+       htab_traverse (str->fields[i].acc_sites, 
+                      create_new_field_acc, &dt);
+    }  
+  if (str->accs)
+    htab_traverse (str->accs, create_new_acc, &dt);
+}
+
+/* This function inserts new variables from new_var, 
+   defined by SLOT, into varpool.  */ 
+
+static int
+update_varpool_with_new_var (void **slot, void *data ATTRIBUTE_UNUSED)
+{
+  new_var n_var = *(new_var *) slot;
+  tree var;
+  unsigned i;
+
+  for (i = 0; VEC_iterate (tree, n_var->new_vars, i, var); i++)
+    insert_global_to_varpool (var);
+  return 1;
+}
+
+/* This function prints a field access site, defined by SLOT.  */ 
+
+static int
+dump_field_acc (void **slot, void *data ATTRIBUTE_UNUSED)
+{
+  struct field_access_site *f_acc =
+    *(struct field_access_site **) slot;
+
+  fprintf(dump_file, "\n");
+  if (f_acc->stmt)
+    print_generic_stmt (dump_file, f_acc->stmt, 0);
+  if (f_acc->ref_def_stmt)
+    print_generic_stmt (dump_file, f_acc->ref_def_stmt, 0);
+  if (f_acc->cast_stmt)
+    print_generic_stmt (dump_file, f_acc->cast_stmt, 0);
+  return 1;
+}
+
+/* Print field accesses from hashtable F_ACCS.  */
+
+static void
+dump_field_acc_sites (htab_t f_accs)
+{
+  if (!dump_file)
+    return;
+
+  if (f_accs)
+    htab_traverse (f_accs, dump_field_acc, NULL);
+}
+
+/* Hash value for fallocs_t.  */
+
+static hashval_t
+malloc_hash (const void *x)
+{
+  return htab_hash_pointer (((const_fallocs_t)x)->func);
+}
+
+/* This function returns nonzero if function of func_alloc_sites' X 
+   is equal to Y.  */
+
+static int
+malloc_eq (const void *x, const void *y)
+{
+  return ((const_fallocs_t)x)->func == (const_tree)y;
+}
+
+/* This function is a callback for traversal over a structure accesses.
+   It frees an access represented by SLOT.  */
+
+static int
+free_accs (void **slot, void *data ATTRIBUTE_UNUSED)
+{
+  struct access_site * acc = *(struct access_site **) slot;
+
+  VEC_free (tree, heap, acc->vars);
+  free (acc);
+  return 1;
+}
+
+/* This is a callback function for traversal over field accesses. 
+   It frees a field access represented by SLOT.  */
+
+static int
+free_field_accs (void **slot, void *data ATTRIBUTE_UNUSED)
+{
+  struct field_access_site *f_acc = *(struct field_access_site **) slot;
+
+  free (f_acc);
+  return 1;
+}
+
+/* This function inserts TYPE into vector of UNSUITABLE_TYPES, 
+   if it is not there yet.  */
+
+static void
+add_unsuitable_type (VEC (tree, heap) **unsuitable_types, tree type)
+{
+  unsigned i;
+  tree t;
+
+  if (!type)
+    return;
+
+  type = TYPE_MAIN_VARIANT (type);
+
+  for (i = 0; VEC_iterate (tree, *unsuitable_types, i, t); i++)
+    if (is_equal_types (t, type))
+      break;
+  
+  if (i == VEC_length (tree, *unsuitable_types))
+    VEC_safe_push (tree, heap, *unsuitable_types, type);
+}
+
+/* Given a type TYPE, this function returns the name of the type.  */
+
+static const char *
+get_type_name (tree type)
+{
+  if (! TYPE_NAME (type))
+    return NULL;
+
+  if (TREE_CODE (TYPE_NAME (type)) == IDENTIFIER_NODE)
+    return IDENTIFIER_POINTER (TYPE_NAME (type));
+  else if (TREE_CODE (TYPE_NAME (type)) == TYPE_DECL
+          && DECL_NAME (TYPE_NAME (type)))
+    return IDENTIFIER_POINTER (DECL_NAME (TYPE_NAME (type)));
+  else
+    return NULL;
+}
+
+/* This function is a temporary hack to overcome the types problem.
+   When several compilation units are compiled together
+   with -combine, the TYPE_MAIN_VARIANT of the same type 
+   can appear differently in different compilation units.
+   Therefore this function first compares type names.
+   If there are no names, structure bodies are recursively 
+   compared.  */
+
+static bool
+is_equal_types (tree type1, tree type2)
+{
+  const char * name1,* name2;
+
+  if ((!type1 && type2)
+      ||(!type2 && type1))
+    return false;
+
+  if (!type1 && !type2)
+    return true;
+
+  if (TREE_CODE (type1) != TREE_CODE (type2))
+    return false;
+
+  if (type1 == type2)
+      return true;
+
+  if (TYPE_MAIN_VARIANT (type1) == TYPE_MAIN_VARIANT (type2))
+      return true;
+
+  name1 = get_type_name (type1);
+  name2 = get_type_name (type2);
+  
+  if (name1 && name2 && !strcmp (name1, name2))
+    return true;
+
+  if (name1 && name2 && strcmp (name1, name2))
+    return false;
+  
+  switch (TREE_CODE (type1))
+    {
+    case POINTER_TYPE:
+    case REFERENCE_TYPE:
+      {
+       return is_equal_types (TREE_TYPE (type1), TREE_TYPE (type2));
+      }
+      break;
+
+    case RECORD_TYPE:
+    case UNION_TYPE:
+    case QUAL_UNION_TYPE:
+    case ENUMERAL_TYPE:
+      {
+       tree field1;
+       /* Compare fields of struture.  */
+       for (field1 = TYPE_FIELDS (type1); field1; 
+            field1 = TREE_CHAIN (field1))
+         {
+           tree field2 = find_field_in_struct_1 (type2, field1);
+           if (!field2)
+             return false;
+         }
+       return true;
+      }
+      break;
+
+    case INTEGER_TYPE:
+      {
+       if (TYPE_UNSIGNED (type1) == TYPE_UNSIGNED (type2)
+           && TYPE_PRECISION (type1) == TYPE_PRECISION (type2))
+         return true;
+      }
+      break;
+
+    case ARRAY_TYPE:
+      {
+       tree d1, d2;
+       tree max1, min1, max2, min2;
+
+       if (!is_equal_types (TREE_TYPE (type1), TREE_TYPE (type2)))
+         return false;
+
+       d1 = TYPE_DOMAIN (type1);
+       d2 = TYPE_DOMAIN (type2);
+
+       if (!d1 || !d2)
+         return false;
+
+       max1 = TYPE_MAX_VALUE (d1);
+       max2 = TYPE_MAX_VALUE (d2);
+       min1 = TYPE_MIN_VALUE (d1);
+       min2 = TYPE_MIN_VALUE (d2);
+
+       if (max1 && max2 && min1 && min2
+           && TREE_CODE (max1) == TREE_CODE (max2)
+           && TREE_CODE (max1) == INTEGER_CST
+           && TREE_CODE (min1) == TREE_CODE (min2)
+           && TREE_CODE (min1) == INTEGER_CST
+           && tree_int_cst_equal (max1, max2)
+           && tree_int_cst_equal (min1, min2))
+         return true;
+      }
+      break;
+
+    default:
+       gcc_unreachable();
+    }
+
+  return false;
+}
+
+/* This function free non-field accesses from hashtable ACCS.  */
+
+static void
+free_accesses (htab_t accs)
+{
+  if (accs)
+    htab_traverse (accs, free_accs, NULL);  
+  htab_delete (accs);
+}
+
+/* This function free field accesses hashtable F_ACCS.  */
+
+static void
+free_field_accesses (htab_t f_accs)
+{
+  if (f_accs)
+    htab_traverse (f_accs, free_field_accs, NULL);  
+  htab_delete (f_accs);
+}
+
+/* Update call graph with new edge generated by new MALLOC_STMT.
+   The edge origin is CONTEXT function.  */
+
+static void
+update_cgraph_with_malloc_call (tree malloc_stmt, tree context)
+{
+  tree call_expr;
+  struct cgraph_node *src, *dest;
+  tree malloc_fn_decl;
+
+  if (!malloc_stmt)
+    return;
+
+  call_expr = get_call_expr_in (malloc_stmt);
+  malloc_fn_decl = get_callee_fndecl (call_expr);
+    
+  src = cgraph_node (context);
+  dest = cgraph_node (malloc_fn_decl);
+  cgraph_create_edge (src, dest, malloc_stmt, 
+                     0, 0, bb_for_stmt (malloc_stmt)->loop_depth);
+}
+
+/* This function generates set of statements required 
+   to allocate number NUM of structures of type NEW_TYPE.
+   The statements are stored in NEW_STMTS. The statement that contain
+   call to malloc is returned. MALLOC_STMT is an original call to malloc.  */
+
+static tree
+create_new_malloc (tree malloc_stmt, tree new_type, tree *new_stmts, tree num)
+{
+  tree new_malloc_size;
+  tree call_expr, malloc_fn_decl;
+  tree new_stmt, malloc_res;
+  tree call_stmt, final_stmt;
+  tree cast_res;
+
+  gcc_assert (num && malloc_stmt && new_type);
+  *new_stmts = alloc_stmt_list ();
+
+  /* Generate argument to malloc as multiplication of num 
+     and size of new_type.  */
+  new_stmt = gen_size (num, new_type, &new_malloc_size);
+  append_to_statement_list (new_stmt, new_stmts);
+
+  /* Generate new call for malloc.  */
+  malloc_res = create_tmp_var (integer_type_node, NULL);
+
+  if (malloc_res)
+    add_referenced_var (malloc_res);
+
+  call_expr = get_call_expr_in (malloc_stmt);
+  malloc_fn_decl = get_callee_fndecl (call_expr);
+  call_expr = build_call_expr (malloc_fn_decl, 1, new_malloc_size); 
+  call_stmt = build_gimple_modify_stmt (malloc_res, call_expr);
+  finalize_stmt_and_append (new_stmts, call_stmt);
+
+  /* Create new cast statement. */
+  final_stmt = get_final_alloc_stmt (malloc_stmt);
+  gcc_assert (final_stmt);
+  new_stmt = gen_cast_stmt (malloc_res, new_type, final_stmt, &cast_res);
+  append_to_statement_list (new_stmt, new_stmts);
+  return call_stmt;      
+}
+
+/* This function returns a tree representing 
+   the number of instances of structure STR_DECL allocated 
+   by allocation STMT. If new statments are generated, 
+   they are filled into NEW_STMTS_P.  */
+
+static tree 
+gen_num_of_structs_in_malloc (tree stmt, tree str_decl, tree *new_stmts_p)
+{
+  call_expr_arg_iterator iter;
+  tree arg;
+  tree call_expr;
+  tree struct_size;
+  HOST_WIDE_INT struct_size_int;
+
+  if (!stmt)
+    return NULL_TREE;
+
+  /* Get malloc argument.  */
+  call_expr = get_call_expr_in (stmt);
+  if (!call_expr)
+    return NULL_TREE;
+
+  arg = first_call_expr_arg (call_expr, &iter);
+
+  if (TREE_CODE (arg) != SSA_NAME
+      && !TREE_CONSTANT (arg))
+    return NULL_TREE;
+  
+  struct_size = TYPE_SIZE_UNIT (str_decl);
+  struct_size_int = TREE_INT_CST_LOW (struct_size);
+  
+  gcc_assert (struct_size);
+
+  if (TREE_CODE (arg) == SSA_NAME)
+    {
+      tree num, div_stmt;
+
+      if (is_result_of_mult (arg, &num, struct_size))
+         return num;      
+
+      num = create_tmp_var (integer_type_node, NULL);
+
+      if (num)
+       add_referenced_var (num);
+
+      if (exact_log2 (struct_size_int) == -1)
+       div_stmt = build_gimple_modify_stmt (num, 
+                                            build2 (TRUNC_DIV_EXPR, 
+                                                    integer_type_node,
+                                                    arg, struct_size));
+      else
+       {
+         tree C =  build_int_cst (integer_type_node,
+                                  exact_log2 (struct_size_int)); 
+
+         div_stmt = 
+           build_gimple_modify_stmt (num, build2 (RSHIFT_EXPR, 
+                                                  integer_type_node,
+                                                  arg, C)); 
+       }
+      *new_stmts_p = alloc_stmt_list ();
+      append_to_statement_list (div_stmt, 
+                               new_stmts_p);
+      finalize_stmt (div_stmt);
+      return num;
+    }
+
+  if (CONSTANT_CLASS_P (arg)
+      && multiple_of_p (TREE_TYPE (struct_size), arg, struct_size))   
+    return int_const_binop (TRUNC_DIV_EXPR, arg, struct_size, 0);
+
+  return NULL_TREE; 
+}
+
+/* This function is a callback for traversal on new_var's hashtable.
+   SLOT is a pointer to new_var. This function prints to dump_file 
+   an original variable and all new variables from the new_var 
+   pointed by *SLOT.  */ 
+
+static int
+dump_new_var (void **slot, void *data ATTRIBUTE_UNUSED)
+{
+  new_var n_var = *(new_var *) slot;
+  tree var_type;
+  tree var;
+  unsigned i;
+
+  var_type = get_type_of_var (n_var->orig_var);
+
+  fprintf (dump_file, "\nOrig var: ");
+  print_generic_expr (dump_file, n_var->orig_var, 0);
+  fprintf (dump_file, " of type ");
+  print_generic_expr (dump_file, var_type, 0);
+  fprintf (dump_file, "\n");
+
+  for (i = 0;
+       VEC_iterate (tree, n_var->new_vars, i, var); i++)
+    {    
+      var_type = get_type_of_var (var);
+                 
+      fprintf (dump_file, "      ");
+      print_generic_expr (dump_file, var, 0);
+      fprintf (dump_file, " of type ");
+      print_generic_expr (dump_file, var_type, 0);
+      fprintf (dump_file, "\n");
+    }
+  return 1;
+}
+
+/* This function copies attributes form ORIG_DECL to NEW_DECL.  */
+
+static inline void 
+copy_decl_attributes (tree new_decl, tree orig_decl)
+{
+
+  DECL_ARTIFICIAL (new_decl) = 1;
+  DECL_EXTERNAL (new_decl) = DECL_EXTERNAL (orig_decl);
+  TREE_STATIC (new_decl) = TREE_STATIC (orig_decl);
+  TREE_PUBLIC (new_decl) = TREE_PUBLIC (orig_decl);
+  TREE_USED (new_decl) = TREE_USED (orig_decl);
+  DECL_CONTEXT (new_decl) = DECL_CONTEXT (orig_decl);
+  TREE_THIS_VOLATILE (new_decl) = TREE_THIS_VOLATILE (orig_decl);
+  TREE_ADDRESSABLE (new_decl) = TREE_ADDRESSABLE (orig_decl);
+  
+  if (TREE_CODE (orig_decl) == VAR_DECL)
+    {
+      TREE_READONLY (new_decl) = TREE_READONLY (orig_decl);
+      DECL_TLS_MODEL (new_decl) = DECL_TLS_MODEL (orig_decl);
+    }
+}
+
+/* This function wraps NEW_STR_TYPE in pointers or arrays wrapper 
+   the same way as a structure type is wrapped in DECL. 
+   It returns the generated type.  */
+
+static inline tree
+gen_struct_type (tree decl, tree new_str_type)
+{
+  tree type_orig = get_type_of_var (decl);
+  tree new_type = new_str_type;
+  VEC (type_wrapper_t, heap) *wrapper = VEC_alloc (type_wrapper_t, heap, 10);
+  type_wrapper_t wr;
+  type_wrapper_t *wr_p;
+  
+  while (POINTER_TYPE_P (type_orig)
+        || TREE_CODE (type_orig) == ARRAY_TYPE)
+    {      
+      if (POINTER_TYPE_P (type_orig))
+       {
+         wr.wrap = 0;
+         wr.domain = NULL_TREE;
+       }
+      else if (TREE_CODE (type_orig) == ARRAY_TYPE)
+       {
+         wr.wrap = 1;
+         wr.domain = TYPE_DOMAIN (type_orig);
+       }
+      VEC_safe_push (type_wrapper_t, heap, wrapper, &wr);
+      type_orig = TREE_TYPE (type_orig);
+    }
+
+  while (VEC_length (type_wrapper_t, wrapper) != 0)
+    {
+      wr_p = VEC_last (type_wrapper_t, wrapper); 
+
+      if (wr_p->wrap) /* Array.  */
+       new_type = build_array_type (new_type, wr_p->domain);
+      else /* Pointer.  */
+       new_type = build_pointer_type (new_type);
+      
+      VEC_pop (type_wrapper_t, wrapper);
+    }
+
+  VEC_free (type_wrapper_t, heap, wrapper);  
+  return new_type;
+}
+
+/* This function generates and returns new variable name based on
+   ORIG_DECL name, combined with index I.
+   The form of the new name is <orig_name>.<I> .  */
+
+static tree
+gen_var_name (tree orig_decl, unsigned HOST_WIDE_INT i)
+{
+  const char *old_name;
+  char *prefix;
+  char *new_name;
+
+  if (!DECL_NAME (orig_decl)
+      || !IDENTIFIER_POINTER (DECL_NAME (orig_decl)))
+     return NULL;
+
+  /* If the original variable has a name, create an 
+     appropriate new name for the new variable.  */
+
+  old_name = IDENTIFIER_POINTER (DECL_NAME (orig_decl));
+  prefix = alloca (strlen (old_name) + 1);
+  strcpy (prefix, old_name);
+  ASM_FORMAT_PRIVATE_NAME (new_name, prefix, i);
+  return get_identifier (new_name);
+}
+
+/* This function adds NEW_NODE to hashtable of new_var's NEW_VARS_HTAB. */
+
+static void
+add_to_new_vars_htab (new_var new_node, htab_t new_vars_htab)
+{
+  void **slot;
+
+  slot = htab_find_slot_with_hash (new_vars_htab, new_node->orig_var,
+                                  htab_hash_pointer (new_node->orig_var), 
+                                  INSERT);
+  *slot = new_node;
+}
+
+/* This function creates and returns new_var_data node 
+   with empty new_vars and orig_var equal to VAR.  */
+
+static new_var
+create_new_var_node (tree var, d_str str)
+{
+  new_var node;
+
+  node = (new_var) xmalloc (sizeof (struct new_var_data));
+  node->orig_var = var;
+  node->new_vars = VEC_alloc (tree, heap, VEC_length (tree, str->new_types));
+  return node;
+}
+
+/* Check whether the type of VAR is potential candidate for peeling.
+   Returns true if yes, false otherwise.  If yes, TYPE_P will contain
+   candidate type. If VAR is initialized, the type of VAR will be added
+   to UNSUITABLE_TYPES.  */
+
+static bool
+is_candidate (tree var, tree *type_p, VEC (tree, heap) **unsuitable_types)
+{
+  tree type;
+  bool initialized = false;
+
+  *type_p = NULL;
+
+  if (!var)
+    return false;
+
+  /* There is no support of initialized vars.  */
+  if (TREE_CODE (var) == VAR_DECL
+      && DECL_INITIAL (var) != NULL_TREE)
+    initialized = true;
+  
+  type = get_type_of_var (var);
+
+  if (type)
+    {
+      type = TYPE_MAIN_VARIANT (strip_type (type));
+      if (TREE_CODE (type) != RECORD_TYPE)
+         return false; 
+      else
+       {
+         if (initialized && unsuitable_types && *unsuitable_types)
+           add_unsuitable_type (unsuitable_types, type);
+         *type_p = type;
+         return true;
+      }
+    }
+  else
+    return false;
+}
+
+/* Hash value for field_access_site.  */
+
+static hashval_t
+field_acc_hash (const void *x)
+{
+  return htab_hash_pointer (((const struct field_access_site *)x)->stmt);
+}
+
+/* This function returns nonzero if stmt of field_access_site X 
+   is equal to Y.  */
+
+static int
+field_acc_eq (const void *x, const void *y)
+{
+  return ((const struct field_access_site *)x)->stmt == (const_tree)y;
+}
+
+/* This function prints an access site, defined by SLOT.  */ 
+
+static int
+dump_acc (void **slot, void *data ATTRIBUTE_UNUSED)
+{
+  struct access_site *acc = *(struct access_site **) slot;
+  tree var;
+  unsigned i;
+
+  fprintf(dump_file, "\n");
+  if (acc->stmt)
+    print_generic_stmt (dump_file, acc->stmt, 0);
+  fprintf(dump_file, " : ");
+
+  for (i = 0; VEC_iterate (tree, acc->vars, i, var); i++)
+    {
+      print_generic_expr (dump_file, var, 0);
+      fprintf(dump_file, ", ");          
+    }
+  return 1;
+}
+
+/* This function frees memory allocated for strcuture clusters, 
+   starting from CLUSTER.  */
+
+static void
+free_struct_cluster (struct field_cluster* cluster)
+{
+  if (cluster)
+    {
+      if (cluster->fields_in_cluster)
+       sbitmap_free (cluster->fields_in_cluster);          
+      if (cluster->sibling)
+       free_struct_cluster (cluster->sibling);
+      free (cluster);
+    }
+}
+
+/* Free all allocated memory under the structure node pointed by D_NODE.  */
+
+static void
+free_data_struct (d_str d_node)
+{
+  int i;
+
+  if (!d_node)
+    return;
+  if (dump_file)
+    {
+      fprintf (dump_file, "\nRemoving data structure \"");
+      print_generic_expr (dump_file, d_node->decl, 0); 
+      fprintf (dump_file, "\" from data_struct_list.");
+    }
+
+  /* Free all space under d_node.  */
+  if (d_node->fields)
+    {
+      for (i = 0; i < d_node->num_fields; i++)
+       free_field_accesses (d_node->fields[i].acc_sites);
+      free (d_node->fields);
+    }
+
+  if (d_node->accs)
+     free_accesses (d_node->accs);
+
+  if (d_node->struct_clustering)
+    free_struct_cluster (d_node->struct_clustering);
+
+  if (d_node->new_types)
+    VEC_free (tree, heap, d_node->new_types);
+}
+
+/* This function creates new general and field accesses in BB.  */
+
+static void
+create_new_accesses_in_bb (basic_block bb)
+{
+  d_str str;
+  unsigned i;
+
+  for (i = 0; VEC_iterate (structure, structures, i, str); i++)
+    create_new_accs_for_struct (str, bb);
+}
+
+/* This function adds allocation sites for peeled structures.
+   M_DATA is vector of allocation sites of function CONTEXT.  */
+
+static void
+create_new_alloc_sites (fallocs_t m_data, tree context)
+{
+  alloc_site_t *call;
+  unsigned j;
+  
+  for (j = 0;
+       VEC_iterate (alloc_site_t, m_data->allocs, j, call); j++)
+    {
+      tree stmt = call->stmt;
+      d_str str = call->str;
+      tree num;
+      tree new_stmts = NULL_TREE;
+      tree last_stmt = get_final_alloc_stmt (stmt);
+      unsigned i;
+      tree type;
+
+      num = gen_num_of_structs_in_malloc (stmt, str->decl, &new_stmts);
+      if (new_stmts)
+       {
+         last_stmt = tsi_stmt (tsi_last (new_stmts));
+         insert_after_stmt (last_stmt, new_stmts);
+       }
+      
+      /* Generate an allocation sites for each new structure type.  */      
+      for (i = 0; 
+          VEC_iterate (tree, str->new_types, i, type); i++)    
+       {
+         tree new_malloc_stmt = NULL_TREE;
+         tree last_stmt_tmp = NULL_TREE;
+
+         new_stmts = NULL_TREE;
+         new_malloc_stmt = create_new_malloc (stmt, type, &new_stmts, num);
+         last_stmt_tmp = tsi_stmt (tsi_last (new_stmts));
+         insert_after_stmt (last_stmt, new_stmts);
+         update_cgraph_with_malloc_call (new_malloc_stmt, context);
+         last_stmt = last_stmt_tmp;
+       }
+    }
+}
+
+/* This function prints new variables from hashtable  
+   NEW_VARS_HTAB to dump_file.  */
+
+static void
+dump_new_vars (htab_t new_vars_htab)
+{
+  if (!dump_file)
+    return;
+
+  if (new_vars_htab)
+    htab_traverse (new_vars_htab, dump_new_var, NULL);
+}
+
+/* Given an original variable ORIG_DECL of structure type STR,
+   this function generates new variables of the types defined 
+   by STR->new_type. Generated types are saved in new_var node NODE.
+   ORIG_DECL should has VAR_DECL tree_code.  */
+
+static void
+create_new_var_1 (tree orig_decl, d_str str, new_var node)
+{
+  unsigned i;
+  tree type;
+
+  for (i = 0; 
+       VEC_iterate (tree, str->new_types, i, type); i++)
+    {
+      tree new_decl = NULL;
+      tree new_name;
+
+      new_name = gen_var_name (orig_decl, i);
+      type = gen_struct_type (orig_decl, type); 
+
+      if (is_global_var (orig_decl))
+       new_decl = build_decl (VAR_DECL, new_name, type); 
+      else
+       {
+         const char *name = new_name ? IDENTIFIER_POINTER (new_name) : NULL;
+         new_decl = create_tmp_var (type, name);                                  
+       }
+      
+      copy_decl_attributes (new_decl, orig_decl);
+      VEC_safe_push (tree, heap, node->new_vars, new_decl);
+    }
+}
+
+/* This function creates new variables to 
+   substitute the original variable VAR_DECL and adds 
+   them to the new_var's hashtable NEW_VARS_HTAB.  */
+
+static void
+create_new_var (tree var_decl, htab_t new_vars_htab)
+{
+  new_var node;
+  d_str str;
+  tree type;
+  unsigned i;
+
+  if (!var_decl || is_in_new_vars_htab (var_decl, new_vars_htab))
+    return;
+
+  if (!is_candidate (var_decl, &type, NULL))
+    return;
+  
+  i = find_structure (type);
+  if (i == VEC_length (structure, structures))
+    return;
+
+  str = VEC_index (structure, structures, i);
+  node = create_new_var_node (var_decl, str);
+  create_new_var_1 (var_decl, str, node);
+  add_to_new_vars_htab (node, new_vars_htab);
+}
+
+/* Hash value for new_var.  */
+
+static hashval_t
+new_var_hash (const void *x)
+{
+  return htab_hash_pointer (((const_new_var)x)->orig_var);
+}
+
+/* This function returns nonzero if orig_var of new_var X is equal to Y.  */
+
+static int
+new_var_eq (const void *x, const void *y)
+{
+  return ((const_new_var)x)->orig_var == (const_tree)y;
+}
+
+/* This function check whether a structure type represented by STR 
+   escapes due to ipa-type-escape analysis. If yes, this type is added 
+   to UNSUITABLE_TYPES vector.  */ 
+
+static void
+check_type_escape (d_str str, VEC (tree, heap) **unsuitable_types)
+{
+  tree type = str->decl;
+
+  if (!ipa_type_escape_type_contained_p (type))
+    {
+      if (dump_file)
+       {
+         fprintf (dump_file, "\nEscaping type is ");
+         print_generic_expr (dump_file, type, 0);
+       }
+      add_unsuitable_type (unsuitable_types, type);
+    }
+}
+
+/* Hash value for access_site.  */
+
+static hashval_t
+acc_hash (const void *x)
+{
+  return htab_hash_pointer (((const struct access_site *)x)->stmt);
+}
+
+/* Return nonzero if stmt of access_site X is equal to Y.  */
+
+static int
+acc_eq (const void *x, const void *y)
+{
+  return ((const struct access_site *)x)->stmt == (const_tree)y;
+}
+
+/* Given a structure declaration STRUCT_DECL, and number of fields 
+   in the structure NUM_FIELDS, this function creates and returns 
+   corresponding field_entry's.  */
+
+static struct field_entry *
+get_fields (tree struct_decl, int num_fields)
+{
+  struct field_entry *list;
+  tree t = TYPE_FIELDS (struct_decl);
+  int idx = 0;
+
+  list = 
+    (struct field_entry *) xmalloc (num_fields * sizeof (struct field_entry));
+
+  for (idx = 0 ; t; t = TREE_CHAIN (t), idx++)
+    if (TREE_CODE (t) == FIELD_DECL)
+      {
+       list[idx].index = idx;
+       list[idx].decl = t;
+       list[idx].acc_sites = 
+         htab_create (32, field_acc_hash, field_acc_eq, NULL);
+       list[idx].count = 0;
+       list[idx].field_mapping = NULL_TREE;
+      }
+
+  return list;
+}
+
+/* Print non-field accesses from hashtable ACCS of structure.  */
+
+static void
+dump_access_sites (htab_t accs)
+{
+  if (!dump_file)
+    return;
+
+  if (accs)
+    htab_traverse (accs, dump_acc, NULL);
+}
+
+/* This function removes the structure with index I from structures vector.  */
+
+static void 
+remove_structure (unsigned i)
+{    
+  d_str str;
+
+  if (i >= VEC_length (structure, structures))
+    return;
+
+  str = VEC_index (structure, structures, i);  
+  free_data_struct (str);
+  VEC_ordered_remove (structure, structures, i);
+}
+
+/* Currently we support only EQ_EXPR or NE_EXPR conditions.
+   COND_STNT is a condition statement to check.  */
+
+static bool
+is_safe_cond_expr (tree cond_stmt)
+{
+
+  tree arg0, arg1;
+  unsigned str0, str1;
+  bool s0, s1;
+  unsigned length = VEC_length (structure, structures);
+
+  tree cond = COND_EXPR_COND (cond_stmt);
+
+  if (TREE_CODE (cond) != EQ_EXPR
+      && TREE_CODE (cond) != NE_EXPR)
+    return false;
+  
+  if (TREE_CODE_LENGTH (TREE_CODE (cond)) != 2)
+    return false;
+
+  arg0 = TREE_OPERAND (cond, 0);
+  arg1 = TREE_OPERAND (cond, 1);
+
+  str0 = find_structure (strip_type (get_type_of_var (arg0)));
+  str1 = find_structure (strip_type (get_type_of_var (arg1)));
+
+  s0 = (str0 != length) ? true : false;
+  s1 = (str1 != length) ? true : false;
+
+  if (!((!s0 && s1) || (!s1 && s0)))
+    return false;
+
+  return true;
+}
+
+/* This function excludes statements, that are 
+   part of allocation sites or field accesses, from the
+   hashtable of general accesses. SLOT represents general 
+   access that will be checked. DATA is a pointer to 
+   exclude_data structure.  */
+
+static int
+exclude_from_accs (void **slot, void *data)
+{
+  struct access_site *acc = *(struct access_site **) slot;
+  tree fn_decl = ((struct exclude_data *)data)->fn_decl;
+  d_str str = ((struct exclude_data *)data)->str;
+
+  if (is_part_of_malloc (acc->stmt, fn_decl)
+      || is_part_of_field_access (acc->stmt, str))
+    {
+      VEC_free (tree, heap, acc->vars);
+      free (acc);
+      htab_clear_slot (str->accs, slot);
+    }
+  return 1;
+}
+
+/* Callback function for walk_tree called from collect_accesses_in_bb 
+   function. DATA is the statement which is analyzed.  */
+
+static tree
+get_stmt_accesses (tree *tp, int *walk_subtrees, void *data)
+{
+  tree stmt = (tree) data;
+  tree t = *tp;
+
+  if (!t)
+    return NULL;
+
+  switch (TREE_CODE (t))
+    {
+    case GIMPLE_MODIFY_STMT:
+      {
+       tree lhs = GIMPLE_STMT_OPERAND (t, 0);
+       tree rhs = GIMPLE_STMT_OPERAND (t, 1);
+       *walk_subtrees = 1;
+       walk_tree (&lhs, get_stmt_accesses, data, NULL);
+       walk_tree (&rhs, get_stmt_accesses, data, NULL);
+       *walk_subtrees = 0;         
+      }
+      break;
+
+    case BIT_FIELD_REF:
+      {
+       tree var = TREE_OPERAND(t, 0);
+       tree type = TYPE_MAIN_VARIANT (strip_type (get_type_of_var (var)));
+       unsigned i = find_structure (type);
+
+       if (i != VEC_length (structure, structures))
+         remove_structure (i); 
+      }
+      break;
+
+    case COMPONENT_REF:
+      {
+       tree ref = TREE_OPERAND (t, 0);
+       tree field_decl = TREE_OPERAND (t, 1);
+
+
+       if ((TREE_CODE (ref) == INDIRECT_REF
+            || TREE_CODE (ref) == ARRAY_REF
+            || TREE_CODE (ref) == VAR_DECL)
+           && TREE_CODE (field_decl) == FIELD_DECL)
+         {
+           tree type = TYPE_MAIN_VARIANT (TREE_TYPE (ref));
+           unsigned i = find_structure (type);
+
+           if (i != VEC_length (structure, structures))
+             {
+               d_str str = VEC_index (structure, structures, i);
+               struct field_entry * field = 
+                 find_field_in_struct (str, field_decl);
+
+               if (field)
+                 {
+                   struct field_access_site *acc = make_field_acc_node ();
+
+                   gcc_assert (acc);
+
+                   acc->stmt = stmt;
+                   acc->comp_ref = t;
+                   acc->ref = ref;
+                   acc->field_decl = field_decl;
+
+                   /* Check whether the access is of the form 
+                      we can deal with.  */
+                   if (!decompose_access (str->decl, acc))
+                     {
+                       remove_structure (i);
+                       free (acc);
+                     }
+                   else
+                     {
+                       /* Increase count of field.  */
+                       basic_block bb = bb_for_stmt (stmt);
+                       field->count += bb->count;
+
+                       /* Add stmt to the acc_sites of field.  */
+                       add_field_acc_to_acc_sites (acc, field->acc_sites);
+                     }
+                   *walk_subtrees = 0;
+                 }
+             }       
+         }
+      }
+      break;
+
+    case MINUS_EXPR:
+    case PLUS_EXPR:
+      {
+       tree op0 = TREE_OPERAND (t, 0);
+       tree op1 = TREE_OPERAND (t, 1);
+       *walk_subtrees = 1;         
+       walk_tree (&op0, get_stmt_accesses, data, NULL);
+       walk_tree (&op1, get_stmt_accesses, data, NULL);        
+       *walk_subtrees = 0;         
+      }
+      break;
+
+    case COND_EXPR:
+      {
+       tree cond = COND_EXPR_COND (t);
+       int i;
+       for (i = 0; i < TREE_CODE_LENGTH (TREE_CODE (cond)); i++)
+         {
+           tree t = TREE_OPERAND (cond, i);
+
+           *walk_subtrees = 1;
+           walk_tree (&t, get_stmt_accesses, data, NULL);
+         }
+       *walk_subtrees = 0;         
+      }
+      break;
+
+    case VAR_DECL:
+    case SSA_NAME:
+      {
+       unsigned i;
+
+       if (TREE_CODE (t) == SSA_NAME)
+         t = SSA_NAME_VAR (t);
+
+       i = find_structure (strip_type (get_type_of_var (t)));
+       if (i != VEC_length (structure, structures))
+         {
+           d_str str;
+
+           str = VEC_index (structure, structures, i);
+           add_access_to_acc_sites (stmt, t, str->accs);
+         }
+       *walk_subtrees = 0;
+      }
+      break;
+
+    case CALL_EXPR:
+      {
+       /* It was checked as part of stage1 that structures 
+          to be transformed cannot be passed as parameters of functions.  */
+       *walk_subtrees = 0;         
+      }
+      break;
+
+    default:
+      return NULL;
+    }
+
+  return NULL;
+}
+
+/* Free structures hashtable.  */
+
+static void
+free_structures (void)
+{
+  d_str str;
+  unsigned i;
+
+  for (i = 0; VEC_iterate (structure, structures, i, str); i++)
+    free_data_struct (str);
+
+  VEC_free (structure, heap, structures);
+  structures = NULL;
+}
+
+/* This function is a callback for traversal over new_var's hashtable.
+   SLOT is a pointer to new_var. This function frees memory allocated 
+   for new_var and pointed by *SLOT.  */
+
+static int
+free_new_var (void **slot, void *data ATTRIBUTE_UNUSED)
+{
+  new_var n_var = *(new_var *) slot;
+
+  /* Free vector of new_vars.  */
+  VEC_free (tree, heap, n_var->new_vars);
+  free (n_var);
+  return 1;
+}
+
+/* Free new_vars hashtable NEW_VARS_HTAB.  */
+
+static void
+free_new_vars_htab (htab_t new_vars_htab)
+{
+  if (new_vars_htab)
+    htab_traverse (new_vars_htab, free_new_var, NULL);  
+  htab_delete (new_vars_htab);
+  new_vars_htab = NULL;
+}
+
+/* This function creates new general and field accesses that appear in cfun.  */
+
+static void
+create_new_accesses_for_func (void)
+{
+  basic_block bb;
+
+  FOR_EACH_BB_FN (bb, cfun)
+    create_new_accesses_in_bb (bb);
+}
+
+/* Create new allocation sites for the function represented by NODE.  */
+
+static void
+create_new_alloc_sites_for_func (struct cgraph_node *node)
+{
+  fallocs_t fallocs = get_fallocs (node->decl);
+
+  if (fallocs)
+    create_new_alloc_sites (fallocs, node->decl);
+}
+
+/* For each local variable of structure type from the vector of structures
+   this function generates new variable(s) to replace it.  */
+
+static void
+create_new_local_vars (void)
+{
+  tree var;
+  referenced_var_iterator rvi;
+   
+  new_local_vars = htab_create (num_referenced_vars, 
+                               new_var_hash, new_var_eq, NULL);
+
+  FOR_EACH_REFERENCED_VAR (var, rvi)
+    {
+      if (!is_global_var (var))
+       create_new_var (var, new_local_vars);
+    }
+
+  if (new_local_vars)
+    htab_traverse (new_local_vars, finalize_new_vars_creation, NULL); 
+  dump_new_vars (new_local_vars);
+}
+
+/* This function prints the SHIFT number of spaces to the DUMP_FILE.  */
+
+static inline void
+print_shift (unsigned HOST_WIDE_INT shift)
+{
+  unsigned HOST_WIDE_INT sh = shift;
+
+  while (sh--)
+    fprintf (dump_file, " ");    
+}
+
+/* This function updates field_mapping of FIELDS in CLUSTER with NEW_TYPE.  */
+
+static inline void
+update_fields_mapping (struct field_cluster *cluster, tree new_type,
+                      struct field_entry * fields, int num_fields)
+{
+  int i;
+
+  for (i = 0; i < num_fields; i++)
+    if (TEST_BIT (cluster->fields_in_cluster, i))
+       fields[i].field_mapping = new_type;  
+}
+
+/* This functions builds structure with FIELDS, 
+   NAME and attributes similar to ORIG_STRUCT. 
+   It returns the newly created structure.  */
+
+static tree
+build_basic_struct (tree fields, tree name, tree orig_struct)
+{
+  tree attributes = NULL_TREE;
+  tree ref = 0;
+  tree x;
+
+  if (TYPE_ATTRIBUTES (orig_struct))
+    attributes = unshare_expr (TYPE_ATTRIBUTES (orig_struct));
+  ref = make_node (RECORD_TYPE);
+  TYPE_SIZE (ref) = 0;
+  decl_attributes (&ref, attributes, (int) ATTR_FLAG_TYPE_IN_PLACE); 
+  TYPE_PACKED (ref) = TYPE_PACKED (orig_struct);
+  for (x = fields; x; x = TREE_CHAIN (x))
+    {
+      DECL_CONTEXT (x) = ref;
+      DECL_PACKED (x) |= TYPE_PACKED (ref);
+    }
+  TYPE_FIELDS (ref) = fields;
+  layout_type (ref);
+  TYPE_NAME (ref) = name;
+
+  return ref;
+}
+
+/* This function copies FIELDS from CLUSTER into TREE_CHAIN as part 
+   of preparation for new structure building. NUM_FIELDS is a total 
+   number of fields in the structure. The function returns newly 
+   generated fields.  */
+
+static tree
+create_fields (struct field_cluster * cluster, 
+              struct field_entry * fields, int num_fields)
+{
+  int i;
+  tree new_types = NULL_TREE;
+  tree last = NULL_TREE;
+
+  for (i = 0; i < num_fields; i++)
+    if (TEST_BIT (cluster->fields_in_cluster, i))
+      {
+       tree new_decl = unshare_expr (fields[i].decl);
+
+       if (!new_types)
+         new_types = new_decl;
+       else
+         TREE_CHAIN (last) = new_decl;
+       last = new_decl;
+      }
+
+  TREE_CHAIN (last) = NULL_TREE;
+  return new_types;
+
+}
+
+/* This function creates a cluster name. The name is based on 
+   the original structure name, if it is present. It has a form:
+   
+   <original_struct_name>_sub.<CLUST_NUM>
+
+   The original structure name is taken from the type of DECL.
+   If an original structure name is not present, it's generated to be:
+
+   struct.<STR_NUM>
+
+   The function returns identifier of the new cluster name.  */
+
+static inline tree
+gen_cluster_name (tree decl, int clust_num, int str_num)
+{
+  const char * orig_name = get_type_name (decl);
+  char * tmp_name = NULL;
+  char * prefix;
+  char * new_name;
+  size_t len;
+  
+  if (!orig_name)
+    ASM_FORMAT_PRIVATE_NAME(tmp_name, "struct", str_num);
+
+  len = strlen (tmp_name ? tmp_name : orig_name) + strlen ("_sub");
+  prefix = alloca (len + 1);
+  memcpy (prefix, tmp_name ? tmp_name : orig_name, 
+         strlen (tmp_name ? tmp_name : orig_name));
+  strcpy (prefix + strlen (tmp_name ? tmp_name : orig_name), "_sub");      
+  
+  ASM_FORMAT_PRIVATE_NAME (new_name, prefix, clust_num);
+  return get_identifier (new_name);
+}
+
+/* This function checks whether the structure STR has bitfields.
+   If yes, this structure type is added to UNSUITABLE_TYPES vector.  */
+
+static void
+check_bitfields (d_str str, VEC (tree, heap) **unsuitable_types)
+{
+  tree type = str->decl;
+  int i;
+
+  for (i = 0; i < str->num_fields; i++)
+    if (DECL_BIT_FIELD (str->fields[i].decl))
+      {
+       add_unsuitable_type (unsuitable_types, type);
+       if (dump_file)
+       {
+         fprintf (dump_file, "\nType ");
+         print_generic_expr (dump_file, type, 0);
+         fprintf (dump_file, "\nescapes due to bitfield ");
+         print_generic_expr (dump_file, str->fields[i].decl, 0);
+       }
+       break;
+      }
+}
+
+/* This function adds to UNSUITABLE_TYPES those types that escape 
+   due to results of ipa-type-escpae analysis. See ipa-type-escpae.[c,h].  */
+
+static void
+exclude_escaping_types_1 (VEC (tree, heap) **unsuitable_types)
+{
+  d_str str;
+  unsigned i;
+
+  for (i = 0; VEC_iterate (structure, structures, i, str); i++)
+    check_type_escape (str, unsuitable_types);
+}
+
+/* If a structure type is a return type of any function,
+   we cannot transform it. Such type is added to UNSUITABLE_TYPES vector.  */
+
+static void
+exclude_returned_types (VEC (tree, heap) **unsuitable_types)
+{
+  struct cgraph_node *c_node;
+
+  for (c_node = cgraph_nodes; c_node; c_node = c_node->next)
+    {
+      tree ret_t = TREE_TYPE (TREE_TYPE (c_node->decl));
+
+      if (ret_t)
+       {
+         ret_t = strip_type (ret_t);
+         if (TREE_CODE (ret_t) == RECORD_TYPE)
+           {
+             add_unsuitable_type (unsuitable_types, TYPE_MAIN_VARIANT (ret_t));
+             if (dump_file)
+               {
+                 fprintf (dump_file, "\nThe type \"");
+                 print_generic_expr (dump_file, ret_t, 0);
+                 fprintf (dump_file,
+                          "\" is return type of function...Excluded.");
+               }
+           }
+       }
+    }
+}
+
+/* This function looks for parameters of local functions 
+   which are of structure types, or derived from them (arrays 
+   of structures, pointers to structures, or their combinations).
+   We are not handling peeling of such structures right now.
+   The found structures types are added to UNSUITABLE_TYPES vector.  */
+
+static void
+exclude_types_passed_to_local_func (VEC (tree, heap) **unsuitable_types)
+{
+  struct cgraph_node *c_node;
+
+  for (c_node = cgraph_nodes; c_node; c_node = c_node->next)
+    if (cgraph_function_body_availability (c_node) == AVAIL_LOCAL)
+      {
+       tree fn = c_node->decl;
+       tree arg;
+       
+       for (arg = DECL_ARGUMENTS (fn); arg; arg = TREE_CHAIN (arg))
+         {
+           tree type = TREE_TYPE (arg);
+
+           type = strip_type (type);
+           if (TREE_CODE (type) == RECORD_TYPE)
+             {
+               add_unsuitable_type (unsuitable_types, 
+                                    TYPE_MAIN_VARIANT (type));
+               if (dump_file)
+                 {
+                   fprintf (dump_file, "\nPointer to type \"");
+                   print_generic_expr (dump_file, type, 0);
+                   fprintf (dump_file, 
+                            "\" is passed to local function...Excluded.");                              
+                 }
+             }
+         }
+      }
+}
+
+/* This function analyzes structure form of structures 
+   potential for transformation. If we are not capable to transform
+   structure of some form, we remove it from the structures hashtable.
+   Right now we cannot handle nested structs, when nesting is 
+   through any level of pointers or arrays.  
+
+   TBD: release these constrains in future.
+
+   Note, that in this function we suppose that all structures 
+   in the program are members of the structures hashtable right now, 
+   without excluding escaping types.  */
+
+static void
+check_struct_form (d_str str, VEC (tree, heap) **unsuitable_types)
+{
+  int i;
+
+  for (i = 0; i < str->num_fields; i++)
+    {
+      tree f_type = strip_type(TREE_TYPE (str->fields[i].decl));
+         
+      if (TREE_CODE (f_type) == RECORD_TYPE)
+       {
+         add_unsuitable_type (unsuitable_types, TYPE_MAIN_VARIANT (f_type));
+         add_unsuitable_type (unsuitable_types, str->decl);
+         if (dump_file)
+           {
+             fprintf (dump_file, "\nType ");
+             print_generic_expr (dump_file, f_type, 0);
+             fprintf (dump_file, " is a field in the structure ");
+             print_generic_expr (dump_file, str->decl, 0);
+             fprintf (dump_file, ". Escaping...");
+           }
+       }
+    }
+}
+
+/* This function adds a structure TYPE to the vector of structures,
+   if it's not already there.  */
+
+static void
+add_structure (tree type)
+{
+  struct data_structure node;
+  unsigned i;
+  int num_fields;
+
+  type = TYPE_MAIN_VARIANT (type);
+
+  i = find_structure (type);
+
+  if (i != VEC_length (structure, structures))
+    return;
+
+  num_fields = fields_length (type);
+  node.decl = type;
+  node.num_fields = num_fields;
+  node.fields = get_fields (type, num_fields);
+  node.struct_clustering = NULL;
+  node.accs = htab_create (32, acc_hash, acc_eq, NULL);
+  node.new_types = VEC_alloc (tree, heap, num_fields);
+  node.count = 0;
+
+  VEC_safe_push (structure, heap, structures, &node);
+
+  if (dump_file)
+    {
+      fprintf (dump_file, "\nAdding data structure \"");
+      print_generic_expr (dump_file, type, 0); 
+      fprintf (dump_file, "\" to data_struct_list.");
+    }
+}
+
+/* This function adds an allocation site to alloc_sites hashtable.
+   The allocation site appears in STMT of function FN_DECL and 
+   allocates the structure represented by STR.  */
+
+static void
+add_alloc_site (tree fn_decl, tree stmt, d_str str)
+{
+  fallocs_t fallocs = NULL;
+  alloc_site_t m_call;
+
+  m_call.stmt = stmt;
+  m_call.str = str;
+
+  fallocs = 
+    (fallocs_t) htab_find_with_hash (alloc_sites,
+                                    fn_decl, htab_hash_pointer (fn_decl));
+
+  if (!fallocs)
+    {
+      void **slot;
+
+      fallocs = (fallocs_t) 
+       xmalloc (sizeof (struct func_alloc_sites));
+      fallocs->func = fn_decl;
+      fallocs->allocs = VEC_alloc (alloc_site_t, heap, 1);
+      slot = htab_find_slot_with_hash (alloc_sites, fn_decl,
+                                     htab_hash_pointer (fn_decl), INSERT);
+      *slot = fallocs;
+    }
+  VEC_safe_push (alloc_site_t, heap, 
+                fallocs->allocs, &m_call);
+  
+  if (dump_file)
+    {
+      fprintf (dump_file, "\nAdding stmt ");
+      print_generic_stmt (dump_file, stmt, 0);
+      fprintf (dump_file, " to list of mallocs.");
+    }
+}
+
+/* This function returns true if the result of STMT, that contains a call
+   to an allocation function, is cast to one of the structure types.
+   STMT should be of the form:    T.2 = <alloc_func> (T.1);
+   If true, I_P contains an index of an allocated structure. 
+   Otherwise I_P contains the length of the vector of structures.  */
+
+static bool
+is_alloc_of_struct (tree stmt, unsigned *i_p)
+{
+  tree lhs;
+  tree type;
+  tree final_stmt;
+
+  final_stmt = get_final_alloc_stmt (stmt);
+
+  if (!final_stmt)
+    return false;
+
+  /* final_stmt should be of the form:
+     T.3 = (struct_type *) T.2; */
+
+  if (TREE_CODE (final_stmt) != GIMPLE_MODIFY_STMT)
+    return false;
+
+  lhs = GIMPLE_STMT_OPERAND (final_stmt, 0);      
+
+  type = get_type_of_var (lhs);
+      
+  if (!type)
+    return false;
+
+  if (!POINTER_TYPE_P (type)
+      || TREE_CODE (strip_type (type)) != RECORD_TYPE)
+    return false;
+
+  *i_p = find_structure (strip_type (type));
+
+  if (*i_p == VEC_length (structure, structures))
+    return false;
+
+  return true;
+}
+
+/* This function prints non-field and field accesses 
+   of the structure STR.  */ 
+
+static void
+dump_accs (d_str str)
+{
+  int i;
+
+  fprintf (dump_file, "\nAccess sites of struct ");
+  print_generic_expr (dump_file, str->decl, 0);
+
+  for (i = 0; i < str->num_fields; i++)
+    {
+      fprintf (dump_file, "\nAccess site of field ");
+      print_generic_expr (dump_file, str->fields[i].decl, 0);
+      dump_field_acc_sites (str->fields[i].acc_sites);   
+      fprintf (dump_file, ":\n");
+    }
+  fprintf (dump_file, "\nGeneral access sites\n");
+  dump_access_sites (str->accs);   
+}
+
+/* This function checks whether an access statement, pointed by SLOT,
+   is a condition we are capable to transform. If not, it removes
+   the structure with index, represented by DATA, from the vector
+   of structures.  */
+static int
+safe_cond_expr_check (void **slot, void *data)
+{
+  struct access_site *acc = *(struct access_site **) slot;
+
+  if (TREE_CODE (acc->stmt) == COND_EXPR)
+    {
+      if (!is_safe_cond_expr (acc->stmt))
+       remove_structure (*(unsigned *) data);
+    }
+  return 1;
+}
+
+/* This function excludes statements that are part of allocation sites and
+   field accesses from the hashtable of general accesses of the structure
+   type STR. Only accesses that belong to the function represented by
+   NODE are treated.  */
+
+static void
+exclude_alloc_and_field_accs_1 (d_str str, struct cgraph_node *node)
+{
+  struct exclude_data dt;
+  dt.str = str;
+  dt.fn_decl = node->decl;
+
+  if (dt.str->accs)
+    htab_traverse (dt.str->accs, exclude_from_accs, &dt);  
+}
+
+/* Collect accesses to the structure types that apear in basic bloack BB.  */
+
+static void
+collect_accesses_in_bb (basic_block bb)
+{
+  block_stmt_iterator bsi;
+
+  for (bsi = bsi_start (bb); ! bsi_end_p (bsi); bsi_next (&bsi))
+    {
+      tree stmt = bsi_stmt (bsi);
+
+      /* In asm stmt we cannot always track the arguments,
+        so we just give up.  */
+      if (TREE_CODE (stmt) == ASM_EXPR)
+       {
+         free_structures ();
+         break;
+       }
+
+      walk_tree (&stmt, get_stmt_accesses, stmt, NULL);
+    }
+}
+
+/* This function generates cluster substructure that cointains FIELDS.
+   The cluster added to the set of clusters of the structure SRT.  */
+
+static void
+gen_cluster (sbitmap fields, d_str str)
+{
+  struct field_cluster *crr_cluster = NULL;
+
+  crr_cluster = 
+    (struct field_cluster *) xcalloc (1, sizeof (struct field_cluster));
+  crr_cluster->sibling = str->struct_clustering;
+  str->struct_clustering = crr_cluster;
+  crr_cluster->fields_in_cluster = fields;
+}
+
+/* This function peels a field with the index I from the structure DS.  */
+
+static void
+peel_field (int i, d_str ds)
+{
+  struct field_cluster *crr_cluster = NULL;
+
+  crr_cluster = 
+    (struct field_cluster *) xcalloc (1, sizeof (struct field_cluster));
+  crr_cluster->sibling = ds->struct_clustering;
+  ds->struct_clustering = crr_cluster;
+  crr_cluster->fields_in_cluster =
+    sbitmap_alloc ((unsigned int) ds->num_fields);
+  sbitmap_zero (crr_cluster->fields_in_cluster);
+  SET_BIT (crr_cluster->fields_in_cluster, i);  
+}
+
+/* This function calculates maximum field count in 
+   the structure STR.  */
+
+static gcov_type
+get_max_field_count (d_str str)
+{
+  gcov_type max = 0;
+  int i;
+
+  for (i = 0; i < str->num_fields; i++)
+    if (str->fields[i].count > max)
+      max = str->fields[i].count; 
+
+  return max;
+}
+
+/* Do struct-reorg transformation for individual function 
+   represented by NODE. All structure types relevant 
+   for this function are transformed.  */
+
+static void
+do_reorg_for_func (struct cgraph_node *node)
+{
+  create_new_local_vars ();  
+  create_new_alloc_sites_for_func (node);
+  create_new_accesses_for_func ();
+  update_ssa (TODO_update_ssa);
+  cleanup_tree_cfg ();
+
+  /* Free auxiliary data representing local variables.  */
+  free_new_vars_htab (new_local_vars); 
+}
+
+/* Print structure TYPE, its name, if it exists, and body.
+   INDENT defines the level of indentation (similar 
+   to the option -i of indent command). SHIFT parameter 
+   defines a number of spaces by which a structure will 
+   be shifted right.  */
+
+static void
+dump_struct_type (tree type, unsigned HOST_WIDE_INT indent,
+                  unsigned HOST_WIDE_INT shift)
+{
+  const char *struct_name;
+  tree field;
+
+  if (!type || !dump_file)
+    return;
+
+  if (TREE_CODE (type) != RECORD_TYPE)
+    {
+      print_generic_expr (dump_file, type, 0);
+      return;
+    }
+  
+  print_shift (shift);
+  struct_name = get_type_name (type);  
+  fprintf (dump_file, "struct ");
+  if (struct_name)    
+    fprintf (dump_file, "%s\n",struct_name);
+  print_shift (shift);
+  fprintf (dump_file, "{\n");
+       
+  for (field = TYPE_FIELDS (type); field; 
+       field = TREE_CHAIN (field))
+    {
+      unsigned HOST_WIDE_INT s = indent;
+      tree f_type = TREE_TYPE (field);
+      
+      print_shift (shift);
+      while (s--)
+       fprintf (dump_file, " ");
+      dump_struct_type (f_type, indent, shift + indent);
+      fprintf(dump_file, " ");
+      print_generic_expr (dump_file, field, 0);
+      fprintf(dump_file, ";\n");
+    }
+  print_shift (shift);
+  fprintf (dump_file, "}\n");
+}
+
+/* This function creates new structure types to replace original type, 
+   indicated by STR->decl. The names of the new structure types are 
+   derived from the original structure type. If the original structure 
+   type has no name, we assume that its name is 'struct.<STR_NUM>'.  */
+
+static void
+create_new_type (d_str str, int *str_num)
+{
+  int cluster_num = 0;
+
+  struct field_cluster *cluster = str->struct_clustering;
+  while (cluster)
+    {    
+      tree  name = gen_cluster_name (str->decl, cluster_num, 
+                                    *str_num);
+      tree fields;
+      tree new_type;
+      cluster_num++;
+          
+      fields = create_fields (cluster, str->fields, 
+                             str->num_fields);
+      new_type = build_basic_struct (fields, name, str->decl);
+         
+      update_fields_mapping (cluster, new_type, 
+                            str->fields, str->num_fields);
+
+      VEC_safe_push (tree, heap, str->new_types, new_type);
+      cluster = cluster->sibling; 
+    }
+  (*str_num)++;
+}
+
+/* This function is a callback for alloc_sites hashtable 
+   traversal. SLOT is a pointer to fallocs_t. 
+   This function frees memory pointed by *SLOT.  */
+
+static int
+free_falloc_sites (void **slot, void *data ATTRIBUTE_UNUSED)
+{
+  fallocs_t fallocs = *(fallocs_t *) slot;
+
+  VEC_free (alloc_site_t, heap, fallocs->allocs);
+  free (fallocs);
+  return 1;
+}
+
+/* Remove structures collected in UNSUITABLE_TYPES
+   from structures vector.  */
+
+static void
+remove_unsuitable_types (VEC (tree, heap) *unsuitable_types)
+{
+  d_str str;
+  tree type;
+  unsigned i, j;
+
+  for (j = 0; VEC_iterate (tree, unsuitable_types, j, type); j++)
+    for (i = 0; VEC_iterate (structure, structures, i, str); i++)
+      if (is_equal_types (str->decl, type))
+       {
+         remove_structure (i);
+         break;
+       }
+}
+
+/* Exclude structure types with bitfields.
+   We would not want to interfere with other optimizations 
+   that can be done in this case. The structure types with 
+   bitfields are added to UNSUITABLE_TYPES vector.  */
+
+static void
+exclude_types_with_bit_fields (VEC (tree, heap) **unsuitable_types)
+{
+  d_str str;
+  unsigned i;
+
+  for (i = 0; VEC_iterate (structure, structures, i, str); i++)
+    check_bitfields (str, unsuitable_types);
+}
+
+/* This function checks three types of escape. A structure type escapes:
+
+   1. if it's a type of parameter of a local function.
+   2. if it's a type of function return value.
+   3. if it escapes as a result of ipa-type-escape analysis.  
+
+  The escaping structure types are added to UNSUITABLE_TYPES vector.  */
+
+static void
+exclude_escaping_types (VEC (tree, heap) **unsuitable_types)
+{
+  exclude_types_passed_to_local_func (unsuitable_types);
+  exclude_returned_types (unsuitable_types);
+  exclude_escaping_types_1 (unsuitable_types);
+}
+
+/* This function analyzes whether the form of 
+   structure is such that we are capable to transform it. 
+   Nested structures are checked here. Unsuitable structure
+   types are added to UNSUITABLE_TYPE vector.  */
+
+static void
+analyze_struct_form (VEC (tree, heap) **unsuitable_types)
+{
+  d_str str;
+  unsigned i;
+
+  for (i = 0; VEC_iterate (structure, structures, i, str); i++)
+    check_struct_form (str, unsuitable_types);
+}
+
+/* This function looks for structure types instantiated in the program. 
+   The candidate types are added to the structures vector. 
+   Unsuitable types are collected into UNSUITABLE_TYPES vector.  */
+
+static void
+build_data_structure (VEC (tree, heap) **unsuitable_types)
+{
+  tree var, type;
+  tree var_list;
+  struct varpool_node *current_varpool;
+  struct cgraph_node *c_node;
+
+  /* Check global variables.  */ 
+  FOR_EACH_STATIC_VARIABLE (current_varpool)
+    {
+      var = current_varpool->decl;
+      if (is_candidate (var, &type, unsuitable_types))
+       add_structure (type);
+    }
+
+  /* Now add structures that are types of function parameters and 
+     local variables.  */
+  for (c_node = cgraph_nodes; c_node; c_node = c_node->next)
+    {
+      enum availability avail = 
+       cgraph_function_body_availability (c_node);
+
+      /* We need AVAIL_AVAILABLE for main function.  */
+      if (avail == AVAIL_LOCAL || avail == AVAIL_AVAILABLE)
+       {
+         struct function *fn = DECL_STRUCT_FUNCTION (c_node->decl);
+
+         for (var = DECL_ARGUMENTS (c_node->decl); var; 
+              var = TREE_CHAIN (var))
+             if (is_candidate (var, &type, unsuitable_types))
+               add_structure (type);
+
+         /* Check function local variables.  */
+         for (var_list = fn->unexpanded_var_list; var_list; 
+              var_list = TREE_CHAIN (var_list))
+           {
+             var = TREE_VALUE (var_list);
+
+             if (is_candidate (var, &type, unsuitable_types))
+               add_structure (type);
+           }
+       }
+    }
+}
+
+/* This function returns true if the program contains 
+   a call to user defined allocation function, or other
+   functions that can interfere with struct-reorg optimizations.  */
+
+static bool
+program_redefines_malloc_p (void)
+{
+  struct cgraph_node *c_node;
+  struct cgraph_node *c_node2;
+  struct cgraph_edge *c_edge;
+  tree fndecl;
+  tree fndecl2;
+  tree call_expr;
+  
+  for (c_node = cgraph_nodes; c_node; c_node = c_node->next)
+    {
+      fndecl = c_node->decl;
+
+      for (c_edge = c_node->callees; c_edge; c_edge = c_edge->next_callee)
+       {
+         call_expr = get_call_expr_in (c_edge->call_stmt);
+         c_node2 = c_edge->callee;
+         fndecl2 = c_node2->decl;
+         if (call_expr)
+           {
+             const char * fname = get_name (fndecl2);
+
+             if ((call_expr_flags (call_expr) & ECF_MALLOC) &&
+                 (DECL_FUNCTION_CODE (fndecl2) != BUILT_IN_MALLOC) &&
+                 (DECL_FUNCTION_CODE (fndecl2) != BUILT_IN_CALLOC) &&
+                 (DECL_FUNCTION_CODE (fndecl2) != BUILT_IN_ALLOCA))
+               return true;
+
+             /* Check that there is no __builtin_object_size,
+              __builtin_offsetof, or realloc's in the program.  */
+             if (DECL_FUNCTION_CODE (fndecl2) == BUILT_IN_OBJECT_SIZE
+                 || !strcmp (fname, "__builtin_offsetof")
+                 || !strcmp (fname, "realloc"))
+               return true;            
+           }
+       }
+    }
+  
+  return false;
+}
+
+/* In this function we assume that an allocation statement 
+
+   var = (type_cast) malloc (size);
+   
+   is converted into the following set of statements:
+
+   T.1 = size;
+   T.2 = malloc (T.1);
+   T.3 = (type_cast) T.2;
+   var = T.3;
+
+   In this function we collect into alloc_sites the allocation 
+   sites of variables of structure types that are present 
+   in structures vector.  */
+
+static void
+collect_alloc_sites (void)
+{
+  struct cgraph_node *node;
+  struct cgraph_edge *cs;
+
+  for (node = cgraph_nodes; node; node = node->next)
+    if (node->analyzed && node->decl)
+      {
+       for (cs = node->callees; cs; cs = cs->next_callee)
+         {
+           tree stmt = cs->call_stmt;
+
+           if (stmt)
+             {
+               tree call = get_call_expr_in (stmt);
+               tree decl;
+
+               if (call && (decl = get_callee_fndecl (call)) 
+                   && TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
+                 {
+                   unsigned i;
+
+                   if (is_alloc_of_struct (stmt, &i))
+                     {
+                       /* We support only malloc now.  */
+                       if (DECL_FUNCTION_CODE (decl) == BUILT_IN_MALLOC)
+                         {
+                           d_str str;
+                           
+                           str = VEC_index (structure, structures, i);
+                           add_alloc_site (node->decl, stmt, str);
+                         }
+                       else
+                         remove_structure (i);         
+                     }
+                 }
+             }       
+         }
+      }
+}
+
+/* Print collected accesses.  */
+
+static void
+dump_accesses (void)
+{
+  d_str str;
+  unsigned i;
+
+  if (!dump_file)
+    return;
+
+  for (i = 0; VEC_iterate (structure, structures, i, str); i++)
+    dump_accs (str);
+}
+
+/* This function checks whether the accesses of structures in condition 
+   expressions are of the kind we are capable to transform. 
+   If not, such structures are removed from the vector of structures.  */
+
+static void
+check_cond_exprs (void)
+{
+  d_str str;
+  unsigned i;
+
+  for (i = 0; VEC_iterate (structure, structures, i, str); i++)
+    if (str->accs)
+      htab_traverse (str->accs, safe_cond_expr_check, &i);
+}
+
+/* We exclude from non-field accesses of the structure 
+   all statements that will be treated as part of the structure 
+   allocation sites or field accesses.  */
+
+static void
+exclude_alloc_and_field_accs (struct cgraph_node *node)
+{
+  d_str str;
+  unsigned i;
+
+  for (i = 0; VEC_iterate (structure, structures, i, str); i++)
+    exclude_alloc_and_field_accs_1 (str, node);
+}
+
+/* This function collects accesses of the fields of the structures 
+   that appear at function FN.  */
+
+static void
+collect_accesses_in_func (struct function *fn)
+{
+  basic_block bb;
+
+  if (! fn)
+    return;
+
+  /* Collect accesses for each basic blocks separately.  */
+  FOR_EACH_BB_FN (bb, fn)
+    collect_accesses_in_bb (bb);
+}
+
+/* This function summarizes counts of the fields into the structure count.  */
+
+static void
+sum_counts (d_str str, gcov_type *hotest)
+{
+  int i;
+      
+  str->count = 0;
+  for (i = 0; i < str->num_fields; i++)
+    {
+      if (dump_file)
+       {
+         fprintf (dump_file, "\nCounter of field \"");
+         print_generic_expr (dump_file, str->fields[i].decl, 0);
+         fprintf (dump_file, "\" is " HOST_WIDE_INT_PRINT_DEC, 
+                  str->fields[i].count);
+       }
+      str->count += str->fields[i].count;
+    }
+
+  if (dump_file)
+    {
+      fprintf (dump_file, "\nCounter of struct \"");
+      print_generic_expr (dump_file, str->decl, 0);
+      fprintf (dump_file, "\" is " HOST_WIDE_INT_PRINT_DEC, str->count);
+    }
+
+  if (str->count > *hotest)
+    *hotest = str->count;
+}
+
+/* This function peels the field into separate structure if it's
+   sufficiently hot, i.e. if its count provides at least 90% of 
+   the maximum field count in the structure.  */
+
+static void
+peel_hot_fields (d_str str)
+{
+  gcov_type max_field_count;
+  sbitmap fields_left = sbitmap_alloc (str->num_fields);
+  int i;
+
+  sbitmap_ones (fields_left);
+  max_field_count = 
+    (gcov_type) (get_max_field_count (str)/100)*90;
+
+  str->struct_clustering = NULL;
+
+  for (i = 0; i < str->num_fields; i++)
+    {
+      if (str->count >= max_field_count)
+       {
+         RESET_BIT (fields_left, i);     
+         peel_field (i, str);
+       }
+    }
+
+  i = sbitmap_first_set_bit (fields_left);
+  if (i != -1)
+    gen_cluster (fields_left, str);
+  else
+    sbitmap_free (fields_left);
+} 
+
+/* This function is a helper for do_reorg. It goes over 
+   functions in call graph and performs actual transformation 
+   on them.  */
+
+static void
+do_reorg_1 (void)
+{
+  struct cgraph_node *node;
+
+  /* Initialize the default bitmap obstack.  */
+  bitmap_obstack_initialize (NULL);
+
+  for (node = cgraph_nodes; node; node = node->next)
+    if (node->analyzed && node->decl && !node->next_clone)
+      {
+       push_cfun (DECL_STRUCT_FUNCTION (node->decl));
+       current_function_decl = node->decl;
+       if (dump_file)
+         fprintf (dump_file, "\nFunction to do reorg is  %s: \n",
+                  (const char *) IDENTIFIER_POINTER (DECL_NAME (node->decl)));
+       do_reorg_for_func (node);
+       free_dominance_info (CDI_DOMINATORS);
+       free_dominance_info (CDI_POST_DOMINATORS);
+       current_function_decl = NULL;
+       pop_cfun ();
+      }
+
+  cfun = NULL;
+}
+
+/* This function creates new global struct variables.
+   For each original variable, the set of new variables 
+   is created with the new structure types corresponding 
+   to the structure type of original variable. 
+   Only VAR_DECL variables are treated by this function.  */
+
+static void 
+create_new_global_vars (void)
+{
+  struct varpool_node *current_varpool;
+  unsigned HOST_WIDE_INT i;
+  unsigned HOST_WIDE_INT varpool_size = 0;
+
+  for (i = 0; i < 2; i++)
+    {
+      if (i)
+       new_global_vars = htab_create (varpool_size, 
+                                      new_var_hash, new_var_eq, NULL);
+      FOR_EACH_STATIC_VARIABLE(current_varpool)
+       {
+         tree  var_decl = current_varpool->decl;
+
+         if (!var_decl || TREE_CODE (var_decl) != VAR_DECL)
+           continue;
+         if (!i)
+           varpool_size++;
+         else
+           create_new_var (var_decl, new_global_vars);
+       }
+    }
+
+  if (new_global_vars)
+    htab_traverse (new_global_vars, update_varpool_with_new_var, NULL);
+}
+
+/* Dump all new types generated by this optimization.  */
+
+static void
+dump_new_types (void)
+{
+  d_str str;
+  tree type;
+  unsigned i, j;
+
+  if (!dump_file)
+    return;
+
+  fprintf (dump_file, "\nThe following are the new types generated by"
+          " this optimization:\n");
+
+  for (i = 0; VEC_iterate (structure, structures, i, str); i++)
+    for (j = 0; VEC_iterate (tree, str->new_types, j, type); j++)
+      dump_struct_type (type, 2, 0); 
+}
+
+/* This function creates new types to replace old structure types.  */
+
+static void
+create_new_types (void)
+{
+  d_str str;
+  unsigned i;
+  int str_num = 0;
+
+  for (i = 0; VEC_iterate (structure, structures, i, str); i++)
+    create_new_type (str, &str_num);
+}
+
+/* Free allocation sites hashtable.  */
+
+static void
+free_alloc_sites (void)
+{
+  if (alloc_sites)
+    htab_traverse (alloc_sites, free_falloc_sites, NULL);  
+  htab_delete (alloc_sites);
+  alloc_sites = NULL;
+}
+
+/* This function collects structures potential 
+   for peeling transformation, and inserts 
+   them into structures hashtable.  */
+
+static void 
+collect_structures (void)
+{
+  VEC (tree, heap) *unsuitable_types = VEC_alloc (tree, heap, 32);
+
+  structures = VEC_alloc (structure, heap, 32);
+   
+  /* If program contains user defined mallocs, we give up.  */
+  if (program_redefines_malloc_p ())
+     return; 
+
+  /* Build data structures hashtable of all data structures 
+     in the program.  */
+  build_data_structure (&unsuitable_types);
+
+  /* This function analyzes whether the form of 
+     structure is such that we are capable to transform it. 
+     Nested structures are checked here.  */
+  analyze_struct_form (&unsuitable_types);
+
+  /* This function excludes those structure types 
+     that escape compilation unit.  */
+  exclude_escaping_types (&unsuitable_types);
+
+  /* We do not want to change data layout of the structures with bitfields.  */
+  exclude_types_with_bit_fields (&unsuitable_types);
+
+  remove_unsuitable_types (unsuitable_types);
+  VEC_free (tree, heap, unsuitable_types);
+
+  if (!VEC_length (structure, structures))
+    {
+      if (dump_file)
+       fprintf (dump_file, "\nNo structures to transform. Exiting...");
+      return;
+    }
+}
+
+/* Collect structure allocation sites. In case of arrays
+   we have nothing to do.  */
+
+static void
+collect_allocation_sites (void)
+{
+  alloc_sites = htab_create (32, malloc_hash, malloc_eq, NULL);
+  collect_alloc_sites ();
+}
+
+/* This function collects data accesses for the 
+   structures to be transformed. For each structure 
+   field it updates the count field in field_entry.  */
+
+static void 
+collect_data_accesses (void)
+{
+  struct cgraph_node *c_node;
+
+  for (c_node = cgraph_nodes; c_node; c_node = c_node->next)
+    {
+      enum availability avail = cgraph_function_body_availability (c_node);
+
+      if (avail == AVAIL_LOCAL || avail == AVAIL_AVAILABLE)
+       {
+         struct function *func = DECL_STRUCT_FUNCTION (c_node->decl);
+
+         if (!c_node->next_clone)
+           collect_accesses_in_func (func);
+         exclude_alloc_and_field_accs (c_node);
+       }
+    }
+
+  check_cond_exprs ();
+  /* Print collected accesses.  */
+  dump_accesses ();
+}
+
+/* We do not bother to transform cold structures.
+   Coldness of the structure is defined relatively 
+   to the highest structure count among the structures 
+   to be transformed. It's triggered by the compiler parameter
+
+   --param struct-reorg-cold-struct-ratio=<value>
+
+   where <value> ranges from 0 to 100. Structures with count ratios
+   that are less than this parameter are considered to be cold.  */
+
+static void
+exclude_cold_structs (void)
+{
+  gcov_type hotest = 0;
+  unsigned i;
+  d_str str;
+
+  /* We summarize counts of fields of a structure into the structure count.  */
+  for (i = 0; VEC_iterate (structure, structures, i, str); i++)
+    sum_counts (str, &hotest);
+
+  /* Remove cold structures from structures vector.  */
+  for (i = 0; VEC_iterate (structure, structures, i, str); i++)
+    if (str->count * 100 < (hotest * STRUCT_REORG_COLD_STRUCT_RATIO))
+      remove_structure (i);
+}
+
+/* This function decomposes original structure into substructures, 
+   i.e.clusters.  */
+
+static void
+peel_structs (void)
+{
+  d_str str;
+  unsigned i;
+
+  for (i = 0; VEC_iterate (structure, structures, i, str); i++)
+    peel_hot_fields (str);
+}
+
+/* Stage 3.  */
+/* Do the actual transformation for each structure
+   from the structures hashtable.  */
+
+static void
+do_reorg (void)
+{
+  /* Check that there is a work to do.  */
+  if (!VEC_length (structure, structures))
+    return;
+
+  /* Generate new types.  */
+  create_new_types ();
+  dump_new_types ();
+
+  /* Create new global variables.  */
+  create_new_global_vars ();
+  dump_new_vars (new_global_vars); 
+
+  /* Decompose structures for each function separately.  */
+  do_reorg_1 ();
+
+  /* Free auxiliary data collected for global variables.  */
+  free_new_vars_htab (new_global_vars);   
+}
+
+/* Free all auxiliary data used by this optimization.  */
+
+static void
+free_data_structs (void)
+{
+  free_structures ();
+  free_alloc_sites (); 
+}
+
+/* Perform structure decomposition (peeling).  */
+
+static void
+reorg_structs (void)
+{
+
+  /* Stage1.  */  
+  /* Collect structure types.  */
+  collect_structures ();
+
+  /* Collect structure allocation sites.  */
+  collect_allocation_sites (); 
+
+  /* Collect structure accesses.  */
+  collect_data_accesses (); 
+
+  /* We transform only hot structures.  */
+  exclude_cold_structs ();
+
+  /* Stage2.  */
+  /* Decompose structures into substructures, i.e. clusters.  */
+  peel_structs ();
+
+  /* Stage3. */  
+  /* Do the actual transformation for each structure
+     from the structures hashtable.  */
+  do_reorg ();
+
+  /* Free all auxiliary data used by this optimization.  */
+  free_data_structs ();  
+}
+
+/* Struct-reorg optimization entry point function.  */
+
+static unsigned int
+reorg_structs_drive (void)
+{
+  reorg_structs ();
+  return 0;
+}
+
+/* Struct-reorg optimization gate function.  */
+
+static bool
+struct_reorg_gate (void)
+{
+  return flag_ipa_struct_reorg && flag_whole_program 
+    && (optimize > 0);
+}
+
+struct tree_opt_pass pass_ipa_struct_reorg = 
+{
+  "ipa_struct_reorg",            /* name */
+  struct_reorg_gate,             /* gate */
+  reorg_structs_drive,           /* execute */
+  NULL,                                  /* sub */
+  NULL,                                  /* next */
+  0,                             /* static_pass_number */
+  TV_INTEGRATION,                /* tv_id */
+  0,                             /* properties_required */
+  0,                             /* properties_provided */
+  0,                             /* properties_destroyed */
+  TODO_verify_ssa,               /* todo_flags_start */
+  TODO_dump_func | TODO_verify_ssa,    /* todo_flags_finish */
+  0                                    /* letter */
+};
diff --git a/gcc/ipa-struct-reorg.h b/gcc/ipa-struct-reorg.h
new file mode 100644 (file)
index 0000000..6f4c5b8
--- /dev/null
@@ -0,0 +1,113 @@
+/* Struct-reorg optimization.
+   Copyright (C) 2002, 2003-2007 Free Software Foundation, Inc.
+   Contributed by Olga Golovanevsky <olga@il.ibm.com>
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify
+under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 2 of the License, 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; if not, write to the Free Software
+Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
+02110-1301, USA.  */
+
+#ifndef IPA_STRUCT_REORG_H
+#define IPA_STRUCT_REORG_H
+
+/* This file contains data structures and interfaces required
+   for struct-reorg optimizations.  */
+
+/* An access site of the structure field.
+   We consider an access to be of the following form:
+
+   D.2166_21 = i.6_20 * 8;
+   D.2167_22 = (struct str_t *) D.2166_21;
+   D.2168_24 = D.2167_22 + p.5_23;
+   D.2169_25 = D.2168_24->b;
+*/
+
+struct field_access_site
+{
+  /* Statement in which the access site occurs.  */
+  tree stmt;             /* D.2169_25 = D.2168_24->b;  */
+  tree comp_ref;         /* D.2168_24->b  */
+  tree field_decl;       /* b */
+  tree ref;              /* D.2168_24  */
+  tree num;              /* i.6_20  */
+  tree offset;           /* D2167_22  */
+  tree base;             /* p.5_23  */
+  tree ref_def_stmt;     /* D.2168_24 = D.2167_22 + p.5_23;  */
+  tree cast_stmt;        /* D.2167_22 = (struct str_t *) D.2166_21;
+                            This statement is not always present.  */
+};
+
+/* A non-field structure access site.  */
+struct access_site
+{
+  /* A statement in which the access site occurs.  */
+  tree stmt;
+  /* A list of structure variables in the access site.  */
+  VEC (tree, heap) *vars;
+};
+
+/* A field of the structure.  */
+struct field_entry
+{
+  /* A field index.  */
+  int index;
+  /* Number of times the field is accessed (according to profiling).  */
+  gcov_type count;
+  tree decl;
+  /* A type of a new structure this field belongs to.  */
+  tree field_mapping;
+  htab_t acc_sites;
+};
+
+/* This structure represents a result of the structure peeling.
+   The original structure is decomposed into substructures, or clusters.  */
+struct field_cluster
+{
+  /* A bitmap of field indices. The set bit indicates that the field 
+     corresponding to it is a part of this cluster.  */
+  sbitmap fields_in_cluster;
+  struct field_cluster *sibling;
+};
+
+/* An information about an individual structure type (RECORD_TYPE) required
+   by struct-reorg optimizations to perform a transformation.  */
+struct data_structure
+{
+
+  /* A main variant of the structure type.  */
+  tree decl;
+
+  /* Number of fields in the structure.  */
+  int num_fields;
+
+  /* A structure access count collected through profiling.  */
+  gcov_type count;
+
+  /* An array of the structure fields, indexed by field ID.  */
+  struct field_entry *fields;
+
+  /* Non-field accesses of the structure.  */
+  htab_t accs;
+
+  /* A data structure representing a reorganization decision.  */
+  struct field_cluster *struct_clustering;
+
+  /* New types to replace an the original structure type.  */
+  VEC(tree, heap) *new_types;
+};
+
+typedef struct data_structure * d_str;
+
+#endif /* IPA_STRUCT_REORG_H */