OSDN Git Service

2008-01-25 Golovanevsky Olga <olga@il.ibm.com>
[pf3gnuchains/gcc-fork.git] / gcc / ipa-struct-reorg.c
1 /* Struct-reorg optimization.
2    Copyright (C) 2007 Free Software Foundation, Inc.
3    Contributed by Olga Golovanevsky <olga@il.ibm.com>
4    (Initial version of this code was developed
5    by Caroline Tice and Mostafa Hagog.)
6
7 This file is part of GCC.
8
9 GCC is free software; you can redistribute it and/or modify it under
10 the terms of the GNU General Public License as published by the Free
11 Software Foundation; either version 2, or (at your option) any later
12 version.
13
14 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
15 WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
17 for more details.
18
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING.  If not, write to the Free
21 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
22 02111-1307, USA.  */
23
24 #include "config.h"
25 #include "system.h"
26 #include "coretypes.h"
27 #include "tm.h"
28 #include "ggc.h"
29 #include "tree.h"
30 #include "rtl.h"
31 #include "tree-gimple.h"
32 #include "tree-inline.h"
33 #include "tree-flow.h"
34 #include "tree-flow-inline.h"
35 #include "langhooks.h"
36 #include "pointer-set.h"
37 #include "hashtab.h"
38 #include "c-tree.h"
39 #include "toplev.h"
40 #include "flags.h"
41 #include "debug.h"
42 #include "target.h"
43 #include "cgraph.h"
44 #include "diagnostic.h"
45 #include "timevar.h"
46 #include "params.h"
47 #include "fibheap.h"
48 #include "intl.h"
49 #include "function.h"
50 #include "basic-block.h"
51 #include "tree-iterator.h"
52 #include "tree-pass.h"
53 #include "ipa-struct-reorg.h"
54 #include "opts.h"
55 #include "ipa-type-escape.h"
56 #include "tree-dump.h"
57 #include "c-common.h"
58
59 /* This optimization implements structure peeling.
60
61    For example, given a structure type:
62    typedef struct
63    {
64      int a;
65      float b;
66      int c;
67    }str_t;
68
69    it can be peeled into two structure types as follows:
70
71    typedef struct  and  typedef struct
72    {                    {
73      int a;               float b;
74      int c;             } str_t_1;
75    }str_t_0;
76
77    or can be fully peeled:
78
79    typedef struct
80    {
81      int a;
82    }str_t_0;
83
84    typedef struct
85    {
86      float b;
87    }str_t_1;
88
89    typedef struct
90    {
91      int c;
92    }str_t_2;
93
94    When structure type is peeled all instances and their accesses
95    in the program are updated accordingly. For example, if there is
96    array of structures:
97
98    str_t A[N];
99
100    and structure type str_t was peeled into two structures str_t_0
101    and str_t_1 as it was shown above, then array A will be replaced
102    by two arrays as follows:
103
104    str_t_0 A_0[N];
105    str_t_1 A_1[N];
106
107    The field access of field a of element i of array A: A[i].a will be
108    replaced by an access to field a of element i of array A_0: A_0[i].a.
109
110    This optimization also supports dynamically allocated arrays.
111    If array of structures was allocated by malloc function:
112
113    str_t * p = (str_t *) malloc (sizeof (str_t) * N)
114
115    the allocation site will be replaced to reflect new structure types:
116
117    str_t_0 * p_0 = (str_t_0 *) malloc (sizeof (str_t_0) * N)
118    str_t_1 * p_1 = (str_t_1 *) malloc (sizeof (str_t_1) * N)
119
120    The field access through the pointer p[i].a will be changed by p_0[i].a.
121
122    The goal of structure peeling is to improve spatial locality.
123    For example, if one of the fields of a structure is accessed frequently
124    in the loop:
125
126    for (i = 0; i < N; i++)
127    {
128      ... = A[i].a;
129    }
130
131    the allocation of field a of str_t contiguously in memory will
132    increase the chances of fetching the field from cache.
133
134    The analysis part of this optimization is based on the frequency of
135    field accesses, which are collected all over the program.
136    Then the fields with the frequencies that satisfy the following condition
137    get peeled out of the structure:
138
139    freq(f) > C * max_field_freq_in_struct
140
141    where max_field_freq_in_struct is the maximum field frequency
142    in the structure. C is a constant defining which portion of
143    max_field_freq_in_struct the fields should have in order to be peeled.
144
145    If profiling information is provided, it is used to calculate the
146    frequency of field accesses. Otherwise, the structure is fully peeled.
147
148    IPA type-escape analysis is used to determine when it is safe
149    to peel a structure.
150
151    The optimization is activated by flag -fipa-struct-reorg.  */
152
153 /* New variables created by this optimization.
154    When doing struct peeling, each variable of
155    the original struct type will be replaced by
156    the set of new variables corresponding to
157    the new structure types.  */
158 struct new_var_data {
159   /* VAR_DECL for original struct type.  */
160   tree orig_var;
161   /* Vector of new variables.  */
162   VEC(tree, heap) *new_vars;
163 };
164
165 typedef struct new_var_data *new_var;
166 typedef const struct new_var_data *const_new_var;
167
168 /* This structure represents allocation site of the structure.  */
169 typedef struct alloc_site
170 {
171   tree stmt;
172   d_str str;
173 } alloc_site_t;
174
175 DEF_VEC_O (alloc_site_t);
176 DEF_VEC_ALLOC_O (alloc_site_t, heap);
177
178 /* Allocation sites that belong to the same function.  */
179 struct func_alloc_sites
180 {
181   tree func;
182   /* Vector of allocation sites for function.  */
183   VEC (alloc_site_t, heap) *allocs;
184 };
185
186 typedef struct func_alloc_sites *fallocs_t;
187 typedef const struct func_alloc_sites *const_fallocs_t;
188
189 /* All allocation sites in the program.  */
190 htab_t alloc_sites = NULL;
191
192 /* New global variables. Generated once for whole program.  */
193 htab_t new_global_vars;
194
195 /* New local variables. Generated per-function.  */
196 htab_t new_local_vars;
197
198 /* Vector of structures to be transformed.  */
199 typedef struct data_structure structure;
200 DEF_VEC_O (structure);
201 DEF_VEC_ALLOC_O (structure, heap);
202 VEC (structure, heap) *structures;
203
204 /* Forward declarations.  */
205 static bool is_equal_types (tree, tree);
206
207 /* Strip structure TYPE from pointers and arrays.  */
208
209 static inline tree
210 strip_type (tree type)
211 {
212   gcc_assert (TYPE_P (type));
213
214   while (POINTER_TYPE_P (type)
215          || TREE_CODE (type) == ARRAY_TYPE)
216     type = TREE_TYPE (type);
217
218   return  type;
219 }
220
221 /* This function returns type of VAR.  */
222
223 static inline tree
224 get_type_of_var (tree var)
225 {
226   if (!var)
227     return NULL;
228   
229   if (TREE_CODE (var) == PARM_DECL)
230       return DECL_ARG_TYPE (var);
231   else 
232     return TREE_TYPE (var);
233 }
234
235 /* Set of actions we do for each newly generated STMT.  */ 
236
237 static inline void
238 finalize_stmt (tree stmt)
239 {
240   update_stmt (stmt);
241   mark_symbols_for_renaming (stmt);
242 }
243
244 /* This function finalizes STMT and appends it to the list STMTS.  */
245
246 static inline void
247 finalize_stmt_and_append (tree *stmts, tree stmt)
248 {
249   append_to_statement_list (stmt, stmts);
250   finalize_stmt (stmt);
251 }
252
253 /* Given structure type SRT_TYPE and field FIELD, 
254    this function is looking for a field with the same name 
255    and type as FIELD in STR_TYPE. It returns it if found,
256    or NULL_TREE otherwise.  */
257
258 static tree
259 find_field_in_struct_1 (tree str_type, tree field)
260 {
261   tree str_field;
262
263   for (str_field = TYPE_FIELDS (str_type); str_field; 
264        str_field = TREE_CHAIN (str_field))
265     {
266       const char * str_field_name;
267       const char * field_name;
268
269       str_field_name = IDENTIFIER_POINTER (DECL_NAME (str_field));
270       field_name = IDENTIFIER_POINTER (DECL_NAME (field));
271       
272       gcc_assert (str_field_name);
273       gcc_assert (field_name);
274
275       if (!strcmp (str_field_name, field_name))
276         {
277           /* Check field types.  */       
278           if (is_equal_types (TREE_TYPE (str_field), TREE_TYPE (field)))
279               return str_field;
280         }
281     }
282
283   return NULL_TREE;
284 }
285
286 /* Given a field declaration FIELD_DECL, this function 
287    returns corresponding field entry in structure STR.  */
288
289 static struct field_entry *
290 find_field_in_struct (d_str str, tree field_decl)
291 {
292   int i;
293   
294   tree field = find_field_in_struct_1 (str->decl, field_decl);
295
296   for (i = 0; i < str->num_fields; i++)
297     if (str->fields[i].decl == field)
298       return &(str->fields[i]);
299
300   return NULL;
301 }
302
303 /* This function checks whether ARG is a result of multiplication 
304    of some number by STRUCT_SIZE. If yes, the function returns true 
305    and this number is filled into NUM.  */
306
307 static bool
308 is_result_of_mult (tree arg, tree *num, tree struct_size)
309 {
310   tree size_def_stmt = SSA_NAME_DEF_STMT (arg);
311
312   /* If allocation  statementt was of the form 
313      D.2229_10 = <alloc_func> (D.2228_9);
314      then size_def_stmt can be D.2228_9 = num.3_8 * 8;  */
315
316   if (size_def_stmt && TREE_CODE (size_def_stmt) == GIMPLE_MODIFY_STMT)
317     {
318       tree lhs = GIMPLE_STMT_OPERAND (size_def_stmt, 0);
319       tree rhs = GIMPLE_STMT_OPERAND (size_def_stmt, 1);
320
321       /* We expect temporary here.  */
322       if (!is_gimple_reg (lhs)) 
323         return false;
324
325       if (TREE_CODE (rhs) == MULT_EXPR)
326         {
327           tree arg0 = TREE_OPERAND (rhs, 0);
328           tree arg1 = TREE_OPERAND (rhs, 1);
329
330           if (operand_equal_p (arg0, struct_size, OEP_ONLY_CONST))
331             {
332               *num = arg1;
333               return true;
334             }
335
336           if (operand_equal_p (arg1, struct_size, OEP_ONLY_CONST))
337             {
338               *num = arg0;
339               return true;
340             }
341         }
342     }
343
344   *num = NULL_TREE;
345   return false;
346 }
347
348
349 /* This function returns true if access ACC corresponds to the pattern
350    generated by compiler when an address of element i of an array 
351    of structures STR_DECL (pointed by p) is calculated (p[i]). If this 
352    pattern is recognized correctly, this function returns true
353    and fills missing fields in ACC. Otherwise it returns false.  */
354
355 static bool
356 decompose_indirect_ref_acc (tree str_decl, struct field_access_site *acc)
357 {
358   tree ref_var;
359   tree rhs, struct_size, op0, op1;
360   tree before_cast;
361  
362   ref_var = TREE_OPERAND (acc->ref, 0);
363
364   if (TREE_CODE (ref_var) != SSA_NAME)
365     return false;
366
367   acc->ref_def_stmt = SSA_NAME_DEF_STMT (ref_var);
368   if (!(acc->ref_def_stmt)
369       || (TREE_CODE (acc->ref_def_stmt) != GIMPLE_MODIFY_STMT))
370     return false;
371
372   rhs = GIMPLE_STMT_OPERAND (acc->ref_def_stmt, 1);
373
374   if (TREE_CODE (rhs) != PLUS_EXPR
375       && TREE_CODE (rhs)!= MINUS_EXPR
376       && TREE_CODE (rhs) != POINTER_PLUS_EXPR)
377     return false;
378
379   op0 = TREE_OPERAND (rhs, 0);
380   op1 = TREE_OPERAND (rhs, 1);
381
382   if (!is_array_access_through_pointer_and_index (TREE_CODE (rhs), op0, op1, 
383                                                  &acc->base, &acc->offset, 
384                                                  &acc->cast_stmt))
385     return false;
386
387   if (acc->cast_stmt)
388     before_cast = SINGLE_SSA_TREE_OPERAND (acc->cast_stmt, SSA_OP_USE);
389   else
390     before_cast = acc->offset;
391
392   if (!before_cast)
393     return false;
394
395
396   if (SSA_NAME_IS_DEFAULT_DEF (before_cast))
397     return false; 
398
399   struct_size = TYPE_SIZE_UNIT (str_decl);
400
401   if (!is_result_of_mult (before_cast, &acc->num, struct_size))
402     return false;
403
404   return true;
405 }
406
407
408 /* This function checks whether the access ACC of structure type STR 
409    is of the form suitable for tranformation. If yes, it returns true. 
410    False otherwise.  */
411
412 static bool
413 decompose_access (tree str_decl, struct field_access_site *acc)
414 {
415   gcc_assert (acc->ref);
416
417   if (TREE_CODE (acc->ref) == INDIRECT_REF)
418     return decompose_indirect_ref_acc (str_decl, acc);
419   else if (TREE_CODE (acc->ref) == ARRAY_REF)
420     return true;
421   else if (TREE_CODE (acc->ref) == VAR_DECL)
422     return true;
423
424   return false;
425 }
426
427 /* This function creates empty field_access_site node.  */
428
429 static inline struct field_access_site *
430 make_field_acc_node (void)
431 {
432   int size = sizeof (struct field_access_site);
433
434   return (struct field_access_site *) xcalloc (1, size);
435 }
436
437 /* This function returns the structure field access, defined by STMT,
438    if it is aready in hashtable of function accesses F_ACCS.  */
439
440 static struct field_access_site *
441 is_in_field_accs (tree stmt, htab_t f_accs)
442 {
443   return (struct field_access_site *) 
444     htab_find_with_hash (f_accs, stmt, htab_hash_pointer (stmt));
445 }
446
447 /* This function adds an access ACC to the hashtable 
448    F_ACCS of field accesses.  */
449
450 static void
451 add_field_acc_to_acc_sites (struct field_access_site *acc, 
452                             htab_t f_accs)
453 {
454   void **slot;
455   
456   gcc_assert (!is_in_field_accs (acc->stmt, f_accs));
457   slot = htab_find_slot_with_hash (f_accs, acc->stmt,
458                                    htab_hash_pointer (acc->stmt), 
459                                    INSERT);
460   *slot = acc;  
461 }
462
463 /* This function adds the VAR to vector of variables of 
464    an access site defined by statement STMT. If access entry 
465    with statement STMT does not exist in hashtable of 
466    accesses ACCS, this function creates it.  */ 
467
468 static void
469 add_access_to_acc_sites (tree stmt, tree var, htab_t accs)
470 {
471    struct access_site *acc;
472
473    acc = (struct access_site *) 
474      htab_find_with_hash (accs, stmt, htab_hash_pointer (stmt));
475
476    if (!acc)
477      {
478        void **slot;
479
480        acc = (struct access_site *) xmalloc (sizeof (struct access_site));
481        acc->stmt = stmt;
482        acc->vars = VEC_alloc (tree, heap, 10);
483        slot = htab_find_slot_with_hash (accs, stmt,
484                                         htab_hash_pointer (stmt), INSERT);
485        *slot = acc;
486
487      }  
488    VEC_safe_push (tree, heap, acc->vars, var);
489 }
490
491 /* This function adds NEW_DECL to function 
492    referenced vars, and marks it for renaming.  */
493
494 static void
495 finalize_var_creation (tree new_decl)
496 {
497   add_referenced_var (new_decl);  
498   if (is_global_var (new_decl))
499     mark_call_clobbered (new_decl, ESCAPE_UNKNOWN);
500   mark_sym_for_renaming (new_decl); 
501 }
502
503 /* This function finalizes VAR creation if it is a global VAR_DECL.  */
504
505 static void
506 finalize_global_creation (tree var)
507 {
508   if (TREE_CODE (var) == VAR_DECL
509       && is_global_var (var))
510     finalize_var_creation (var);
511 }
512
513 /* This function inserts NEW_DECL to varpool.  */
514
515 static inline void
516 insert_global_to_varpool (tree new_decl)
517 {
518   struct varpool_node *new_node;
519
520   new_node = varpool_node (new_decl);
521   notice_global_symbol (new_decl);
522   varpool_mark_needed_node (new_node);
523   varpool_finalize_decl (new_decl);
524 }
525
526 /* This function finalizes the creation of new variables, 
527    defined by *SLOT->new_vars.  */ 
528
529 static int
530 finalize_new_vars_creation (void **slot, void *data ATTRIBUTE_UNUSED)
531 {
532   new_var n_var = *(new_var *) slot;
533   unsigned i;
534   tree var;
535
536   for (i = 0; VEC_iterate (tree, n_var->new_vars, i, var); i++)
537     finalize_var_creation (var);
538   return 1;
539 }
540
541 /* This funciton updates statements in STMT_LIST with BB info.  */
542
543 static void
544 add_bb_info (basic_block bb, tree stmt_list)
545 {
546   if (TREE_CODE (stmt_list) == STATEMENT_LIST)
547     {
548       tree_stmt_iterator tsi;
549       for (tsi = tsi_start (stmt_list); !tsi_end_p (tsi); tsi_next (&tsi))
550         {
551           tree stmt = tsi_stmt (tsi);
552
553           set_bb_for_stmt (stmt, bb);
554         }
555     }
556 }
557
558 /* This function looks for the variable of NEW_TYPE type, stored in VAR.
559    It returns it, if found, and NULL_TREE otherwise.  */
560
561 static tree
562 find_var_in_new_vars_vec (new_var var, tree new_type)
563 {
564   tree n_var;
565   unsigned i;
566
567   for (i = 0; VEC_iterate (tree, var->new_vars, i, n_var); i++)
568     {
569       tree type = strip_type(get_type_of_var (n_var));
570       gcc_assert (type);
571       
572       if (type == new_type)
573         return n_var;
574     }
575
576   return NULL_TREE;
577 }
578
579 /* This function returns new_var node, the orig_var of which is DECL.
580    It looks for new_var's in NEW_VARS_HTAB. If not found, 
581    the function returns NULL.  */
582
583 static new_var
584 is_in_new_vars_htab (tree decl, htab_t new_vars_htab)
585 {
586   return (new_var) htab_find_with_hash (new_vars_htab, decl,
587                                         htab_hash_pointer (decl));
588 }
589
590 /* Given original varaiable ORIG_VAR, this function returns
591    new variable corresponding to it of NEW_TYPE type. */
592
593 static tree
594 find_new_var_of_type (tree orig_var, tree new_type)
595 {
596   new_var var;
597   gcc_assert (orig_var && new_type);
598
599   if (TREE_CODE (orig_var) == SSA_NAME)
600     orig_var = SSA_NAME_VAR (orig_var);
601
602   var = is_in_new_vars_htab (orig_var, new_global_vars);
603   if (!var)
604     var = is_in_new_vars_htab (orig_var, new_local_vars);
605   gcc_assert (var);
606   return find_var_in_new_vars_vec (var, new_type);
607 }
608
609 /* This function generates stmt:
610    res = NUM * sizeof(TYPE) and returns it.
611    res is filled into RES.  */
612
613 static tree
614 gen_size (tree num, tree type, tree *res)
615 {
616   tree struct_size = TYPE_SIZE_UNIT (type);
617   HOST_WIDE_INT struct_size_int = TREE_INT_CST_LOW (struct_size);
618   tree new_stmt;
619
620   *res = create_tmp_var (TREE_TYPE (num), NULL);
621
622   if (*res)
623     add_referenced_var (*res);
624
625   if (exact_log2 (struct_size_int) == -1)
626     {
627       tree size = build_int_cst (TREE_TYPE (num), struct_size_int);
628       new_stmt = build_gimple_modify_stmt (*res, build2 (MULT_EXPR,
629                                                          TREE_TYPE (num),
630                                                          num, size));
631     }
632   else
633     {
634       tree C = build_int_cst (TREE_TYPE (num), exact_log2 (struct_size_int));
635  
636       new_stmt = build_gimple_modify_stmt (*res, build2 (LSHIFT_EXPR, 
637                                                          TREE_TYPE (num),
638                                                          num, C));
639     }
640
641   finalize_stmt (new_stmt);
642   return new_stmt;
643 }
644
645 /* This function generates and returns a statement, that cast variable 
646    BEFORE_CAST to NEW_TYPE. The cast result variable is stored 
647    into RES_P. ORIG_CAST_STMT is the original cast statement.  */
648
649 static tree
650 gen_cast_stmt (tree before_cast, tree new_type, tree orig_cast_stmt,
651                tree *res_p)
652 {
653   tree lhs, new_lhs, new_stmt;
654   gcc_assert (TREE_CODE (orig_cast_stmt) == GIMPLE_MODIFY_STMT);
655     
656   lhs = GIMPLE_STMT_OPERAND (orig_cast_stmt, 0);
657   new_lhs = find_new_var_of_type (lhs, new_type);
658   gcc_assert (new_lhs);
659
660   new_stmt = build_gimple_modify_stmt (new_lhs, 
661                                        build1 (NOP_EXPR, 
662                                                TREE_TYPE (new_lhs),
663                                                before_cast));
664   finalize_stmt (new_stmt);
665   *res_p = new_lhs;
666   return new_stmt;
667 }
668
669 /* This function builds an edge between BB and E->dest and updates
670    phi nodes of E->dest. It returns newly created edge.  */
671
672 static edge
673 make_edge_and_fix_phis_of_dest (basic_block bb, edge e)
674 {
675   edge new_e;
676   tree phi, arg;
677                       
678   new_e = make_edge (bb, e->dest, e->flags);
679
680   for (phi = phi_nodes (new_e->dest); phi; phi = PHI_CHAIN (phi))
681     {
682       arg = PHI_ARG_DEF_FROM_EDGE (phi, e);
683       add_phi_arg (phi, arg, new_e); 
684     }
685
686   return new_e;
687 }
688
689 /* This function inserts NEW_STMTS before STMT.  */
690
691 static void
692 insert_before_stmt (tree stmt, tree new_stmts)
693 {
694   block_stmt_iterator bsi;
695
696   if (!stmt || !new_stmts)
697     return;
698
699   bsi = bsi_for_stmt (stmt); 
700   bsi_insert_before (&bsi, new_stmts, BSI_SAME_STMT);   
701 }
702
703 /* Insert NEW_STMTS after STMT.  */
704
705 static void
706 insert_after_stmt (tree stmt, tree new_stmts)
707 {
708   block_stmt_iterator bsi;
709
710   if (!stmt || !new_stmts)
711     return;
712
713   bsi = bsi_for_stmt (stmt); 
714   bsi_insert_after (&bsi, new_stmts, BSI_SAME_STMT);   
715 }
716
717 /* This function returns vector of allocation sites
718    that appear in function FN_DECL.  */
719
720 static fallocs_t
721 get_fallocs (tree fn_decl)
722 {  
723   return (fallocs_t) htab_find_with_hash (alloc_sites, fn_decl,
724                                          htab_hash_pointer (fn_decl));
725 }
726
727 /* If ALLOC_STMT is D.2225_7 = <alloc_func> (D.2224_6);
728    and it is a part of allocation of a structure,
729    then it is usually followed by a cast stmt 
730    p_8 = (struct str_t *) D.2225_7;
731    which is returned by this function.  */
732
733 static tree
734 get_final_alloc_stmt (tree alloc_stmt)
735 {
736   tree final_stmt;
737   use_operand_p use_p;
738   tree alloc_res;
739
740   if (!alloc_stmt)
741     return NULL;
742   
743   if (TREE_CODE (alloc_stmt) != GIMPLE_MODIFY_STMT)
744     return NULL;
745
746   alloc_res = GIMPLE_STMT_OPERAND (alloc_stmt, 0);
747
748   if (TREE_CODE (alloc_res) != SSA_NAME)
749     return NULL;
750
751   if (!single_imm_use (alloc_res, &use_p, &final_stmt))
752     return NULL;
753   else
754     return final_stmt;
755 }
756
757 /* This function returns true if STMT is one of allocation 
758    sites of function FN_DECL. It returns false otherwise.  */
759
760 static bool
761 is_part_of_malloc (tree stmt, tree fn_decl)
762 {
763   fallocs_t fallocs = get_fallocs (fn_decl);
764   
765   if (fallocs)
766     {
767       alloc_site_t *call;
768       unsigned i;
769
770       for (i = 0;
771            VEC_iterate (alloc_site_t, fallocs->allocs, i, call); i++)
772         if (call->stmt == stmt
773             || get_final_alloc_stmt (call->stmt) == stmt)
774           return true;
775     }
776   return false;
777 }
778
779 /* Auxiliary structure for a lookup over field accesses. */
780 struct find_stmt_data
781 {
782   bool found;
783   tree stmt;
784 };
785
786 /* This function looks for DATA->stmt among 
787    the statements involved in the field access, 
788    defined by SLOT. It stops when it's found. */
789
790 static int
791 find_in_field_accs (void **slot, void *data)
792 {
793   struct field_access_site *f_acc = 
794     *(struct field_access_site **) slot;
795   tree stmt = ((struct find_stmt_data *)data)->stmt;
796
797   if (f_acc->stmt == stmt
798       || f_acc->ref_def_stmt == stmt
799       || f_acc->cast_stmt == stmt)
800     {
801       ((struct find_stmt_data *)data)->found = true;
802       return 0;
803     }
804   else
805     return 1;
806 }
807
808 /* This function checks whether STMT is part of field
809    accesses of structure STR. It returns true, if found,
810    and false otherwise.  */
811
812 static bool
813 is_part_of_field_access (tree stmt, d_str str)
814 {
815   int i;
816
817   for (i = 0; i < str->num_fields; i++)
818     {
819       struct find_stmt_data data;
820       data.found = false;
821       data.stmt = stmt;
822
823       if (str->fields[i].acc_sites)
824         htab_traverse (str->fields[i].acc_sites, find_in_field_accs, &data);
825
826       if (data.found)
827         return true;
828     }
829
830   return false;
831 }
832
833 /* Auxiliary data for exclude_from_accs function.  */
834
835 struct exclude_data
836 {
837   tree fn_decl;
838   d_str str;
839 };
840
841 /* This function returns component_ref with the BASE and 
842    field named FIELD_ID from structure TYPE.  */
843
844 static inline tree
845 build_comp_ref (tree base, tree field_id, tree type)
846 {
847   tree field;
848   bool found = false;
849   
850
851   /* Find field of structure type with the same name as field_id. */
852   for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
853     {
854       if (DECL_NAME (field) == field_id)
855         {
856           found = true;
857           break;
858         }
859     }
860
861   gcc_assert (found);
862
863   return build3 (COMPONENT_REF, TREE_TYPE (field), base, field, NULL_TREE);
864 }
865
866
867 /* This struct represent data used for walk_tree 
868    called from function find_pos_in_stmt.
869    - ref is a tree to be found, 
870    - and pos is a pointer that points to ref in stmt.  */
871 struct ref_pos
872 {
873   tree *pos;
874   tree ref;
875 };
876
877
878 /* This is a callback function for walk_tree, called from 
879    collect_accesses_in_bb function. DATA is a pointer to ref_pos structure.
880    When *TP is equal to DATA->ref, the walk_tree stops,
881    and found position, equal to TP, is assigned to DATA->pos.  */
882
883 static tree
884 find_pos_in_stmt_1 (tree *tp, int *walk_subtrees, void * data)
885 {
886   struct ref_pos * r_pos = (struct ref_pos *) data;
887   tree ref = r_pos->ref;
888   tree t = *tp;
889
890   if (t == ref)
891     {
892       r_pos->pos = tp;
893       return t;
894     }
895
896   switch (TREE_CODE (t))
897     {
898     case GIMPLE_MODIFY_STMT:
899       {
900         tree lhs = GIMPLE_STMT_OPERAND (t, 0);
901         tree rhs = GIMPLE_STMT_OPERAND (t, 1);
902         *walk_subtrees = 1;
903         walk_tree (&lhs, find_pos_in_stmt_1, data, NULL);
904         walk_tree (&rhs, find_pos_in_stmt_1, data, NULL);
905         *walk_subtrees = 0;         
906       }
907       break;
908
909     default:
910       *walk_subtrees = 1;      
911     }
912     return NULL_TREE;
913 }
914
915
916 /* This function looks for the pointer of REF in STMT,
917    It returns it, if found, and NULL otherwise.  */
918
919 static tree *
920 find_pos_in_stmt (tree stmt, tree ref)
921 {
922   struct ref_pos r_pos;
923
924   r_pos.ref = ref;
925   r_pos.pos = NULL;
926   walk_tree (&stmt, find_pos_in_stmt_1, &r_pos, NULL);
927
928   return r_pos.pos;
929 }
930
931 /* This structure is used to represent array 
932    or pointer-to wrappers of structure type.
933    For example, if type1 is structure type, 
934    then for type1 ** we generate two type_wrapper 
935    structures with wrap = 0 each one.  
936    It's used to unwind the original type up to 
937    structure type, replace it with the new structure type 
938    and wrap it back in the opposite order.  */
939
940 typedef struct type_wrapper
941 {
942   /* 0 stand for pointer wrapper, and 1 for array wrapper.  */
943   bool wrap;
944
945   /* Relevant for arrays as domain or index.  */
946   tree domain; 
947 }type_wrapper_t;
948
949 DEF_VEC_O (type_wrapper_t);
950 DEF_VEC_ALLOC_O (type_wrapper_t, heap);
951
952 /* This function replace field access ACC by the new 
953    field access of structure type NEW_TYPE.  */
954
955 static void
956 replace_field_acc (struct field_access_site *acc, tree new_type)
957 {
958   tree ref_var = acc->ref;
959   tree new_ref;
960   tree lhs, rhs;
961   tree *pos;
962   tree new_acc;
963   tree field_id = DECL_NAME (acc->field_decl);
964   VEC (type_wrapper_t, heap) *wrapper = VEC_alloc (type_wrapper_t, heap, 10);
965   type_wrapper_t *wr_p = NULL;
966   
967   while (TREE_CODE (ref_var) == INDIRECT_REF
968          || TREE_CODE (ref_var) == ARRAY_REF)
969     {
970       type_wrapper_t wr;
971
972       if ( TREE_CODE (ref_var) == INDIRECT_REF)
973         {
974           wr.wrap = 0;
975           wr.domain = 0;
976         }
977       else
978         {
979           wr.wrap = 1;
980           wr.domain = TREE_OPERAND (ref_var, 1);
981         }
982
983       VEC_safe_push (type_wrapper_t, heap, wrapper, &wr);
984       ref_var = TREE_OPERAND (ref_var, 0);
985     }
986
987   new_ref = find_new_var_of_type (ref_var, new_type);
988   finalize_global_creation (new_ref);
989
990   while (VEC_length (type_wrapper_t, wrapper) != 0)
991     {
992       tree type = TREE_TYPE (TREE_TYPE (new_ref));
993
994       wr_p = VEC_last (type_wrapper_t, wrapper); 
995       if (wr_p->wrap) /* Array.  */
996         new_ref = build4 (ARRAY_REF, type, new_ref, 
997                           wr_p->domain, NULL_TREE, NULL_TREE);
998       else /* Pointer.  */
999         new_ref = build1 (INDIRECT_REF, type, new_ref);
1000       VEC_pop (type_wrapper_t, wrapper);
1001     }
1002
1003   new_acc = build_comp_ref (new_ref, field_id, new_type);
1004   VEC_free (type_wrapper_t, heap, wrapper);  
1005
1006   if (TREE_CODE (acc->stmt) == GIMPLE_MODIFY_STMT)
1007     {      
1008       lhs = GIMPLE_STMT_OPERAND (acc->stmt, 0);
1009       rhs = GIMPLE_STMT_OPERAND (acc->stmt, 1);
1010       
1011         
1012       if (lhs == acc->comp_ref)
1013         GIMPLE_STMT_OPERAND (acc->stmt, 0) = new_acc;
1014       else if (rhs == acc->comp_ref)
1015         GIMPLE_STMT_OPERAND (acc->stmt, 1) = new_acc;
1016       else
1017         {
1018           pos = find_pos_in_stmt (acc->stmt, acc->comp_ref);
1019           gcc_assert (pos);
1020           *pos = new_acc;
1021         }
1022     }
1023   else
1024     {
1025       pos = find_pos_in_stmt (acc->stmt, acc->comp_ref);
1026       gcc_assert (pos);
1027       *pos = new_acc;
1028     }
1029   
1030   finalize_stmt (acc->stmt);
1031 }
1032
1033 /* This function replace field access ACC by a new field access 
1034    of structure type NEW_TYPE.  */
1035
1036 static void
1037 replace_field_access_stmt (struct field_access_site *acc, tree new_type)
1038 {
1039
1040   if (TREE_CODE (acc->ref) == INDIRECT_REF
1041       ||TREE_CODE (acc->ref) == ARRAY_REF
1042       ||TREE_CODE (acc->ref) == VAR_DECL)
1043     replace_field_acc (acc, new_type);
1044   else
1045     gcc_unreachable ();
1046 }
1047
1048 /* This function looks for d_str, represented by TYPE, in the structures 
1049    vector. If found, it returns an index of found structure. Otherwise 
1050    it returns a length of the structures vector.  */
1051  
1052 static unsigned
1053 find_structure (tree type)
1054 {
1055   d_str str;
1056   unsigned i;
1057
1058   type = TYPE_MAIN_VARIANT (type);
1059
1060   for (i = 0; VEC_iterate (structure, structures, i, str); i++)
1061     if (is_equal_types (str->decl, type))
1062       return i;
1063
1064   return VEC_length (structure, structures);
1065 }
1066
1067 /* In this function we create new statements that have the same
1068    form as ORIG_STMT, but of type NEW_TYPE. The statements 
1069    treated by this function are simple assignments, 
1070    like assignments:  p.8_7 = p; or statements with rhs of 
1071    tree codes PLUS_EXPR and MINUS_EXPR.  */
1072
1073 static tree
1074 create_base_plus_offset (tree orig_stmt, tree new_type, 
1075                          tree offset)
1076 {
1077   tree lhs, rhs;
1078   tree new_lhs, new_rhs;
1079   tree new_stmt;
1080
1081   gcc_assert (TREE_CODE (orig_stmt) == GIMPLE_MODIFY_STMT);
1082
1083   lhs = GIMPLE_STMT_OPERAND (orig_stmt, 0);
1084   rhs = GIMPLE_STMT_OPERAND (orig_stmt, 1);
1085
1086   gcc_assert (TREE_CODE (lhs) == VAR_DECL
1087               || TREE_CODE (lhs) == SSA_NAME);
1088   
1089   new_lhs = find_new_var_of_type (lhs, new_type);
1090   gcc_assert (new_lhs);
1091   finalize_var_creation (new_lhs);
1092
1093   switch (TREE_CODE (rhs))
1094     {
1095     case PLUS_EXPR:
1096     case MINUS_EXPR:
1097     case POINTER_PLUS_EXPR:
1098       {
1099         tree op0 = TREE_OPERAND (rhs, 0);
1100         tree op1 = TREE_OPERAND (rhs, 1);
1101         tree new_op0 = NULL_TREE, new_op1 = NULL_TREE;
1102         unsigned str0, str1;
1103         unsigned length = VEC_length (structure, structures);
1104         
1105
1106         str0 = find_structure (strip_type (get_type_of_var (op0)));     
1107         str1 = find_structure (strip_type (get_type_of_var (op1)));
1108         gcc_assert ((str0 != length) || (str1 != length));
1109         
1110         if (str0 != length)
1111           new_op0 = find_new_var_of_type (op0, new_type);
1112         if (str1 != length)
1113           new_op1 = find_new_var_of_type (op1, new_type);
1114
1115         if (!new_op0)
1116           new_op0 = offset;
1117         if (!new_op1)
1118           new_op1 = offset;
1119
1120         new_rhs = build2 (TREE_CODE (rhs), TREE_TYPE (new_op0), 
1121                           new_op0, new_op1);
1122       }
1123       break;
1124
1125     default:
1126       gcc_unreachable();
1127     }
1128   
1129   new_stmt = build_gimple_modify_stmt (new_lhs, new_rhs);
1130   finalize_stmt (new_stmt);     
1131
1132   return new_stmt;
1133 }
1134
1135 /* Given a field access F_ACC of the FIELD, this function 
1136    replaces it by the new field access.  */
1137
1138 static void
1139 create_new_field_access (struct field_access_site *f_acc,
1140                          struct field_entry field)
1141 {
1142   tree new_type = field.field_mapping;
1143   tree new_stmt;
1144   tree size_res;
1145   tree mult_stmt, cast_stmt;
1146   tree cast_res = NULL;
1147   
1148   if (f_acc->num)
1149     {
1150       mult_stmt = gen_size (f_acc->num, new_type, &size_res);
1151       insert_before_stmt (f_acc->ref_def_stmt, mult_stmt);
1152     }
1153
1154   if (f_acc->cast_stmt)
1155     {
1156       cast_stmt = gen_cast_stmt (size_res, new_type, 
1157                                  f_acc->cast_stmt, &cast_res);
1158       insert_after_stmt (f_acc->cast_stmt, cast_stmt);
1159     }
1160
1161   if (f_acc->ref_def_stmt)
1162     {
1163       tree offset;
1164       if (cast_res)
1165         offset = cast_res;
1166       else
1167         offset = size_res;
1168
1169       new_stmt = create_base_plus_offset (f_acc->ref_def_stmt, 
1170                                           new_type, offset);
1171       insert_after_stmt (f_acc->ref_def_stmt, new_stmt);
1172     }
1173
1174   /* In stmt D.2163_19 = D.2162_18->b; we replace variable
1175    D.2162_18 by an appropriate variable of new_type type.  */
1176   replace_field_access_stmt (f_acc, new_type);
1177 }
1178
1179 /* This function creates a new condition statement 
1180    corresponding to the original COND_STMT, adds new basic block
1181    and redirects condition edges. NEW_VAR is a new condition 
1182    variable located in the condition statement at the position POS.  */
1183
1184 static void
1185 create_new_stmts_for_cond_expr_1 (tree new_var, tree cond_stmt, bool pos)
1186 {
1187   tree new_cond;
1188   tree new_stmt;
1189   edge true_e = NULL, false_e = NULL;
1190   basic_block new_bb;
1191   tree stmt_list;
1192
1193   extract_true_false_edges_from_block (bb_for_stmt (cond_stmt),
1194                                        &true_e, &false_e);
1195
1196   new_cond = unshare_expr (COND_EXPR_COND (cond_stmt));
1197
1198   TREE_OPERAND (new_cond, pos) = new_var;
1199                                       
1200   new_stmt = build3 (COND_EXPR, TREE_TYPE (cond_stmt),
1201                      new_cond, NULL_TREE, NULL_TREE);
1202
1203   finalize_stmt (new_stmt);
1204
1205   /* Create new basic block after bb.  */
1206   new_bb = create_empty_bb (bb_for_stmt (cond_stmt));
1207
1208   /* Add new condition stmt to the new_bb.  */
1209   stmt_list = bb_stmt_list (new_bb);
1210   append_to_statement_list (new_stmt, &stmt_list);
1211   add_bb_info (new_bb, stmt_list);
1212
1213                   
1214   /* Create false and true edges from new_bb.  */
1215   make_edge_and_fix_phis_of_dest (new_bb, true_e);
1216   make_edge_and_fix_phis_of_dest (new_bb, false_e);
1217                   
1218   /* Redirect one of original edges to point to new_bb.  */
1219   if (TREE_CODE (cond_stmt) == NE_EXPR)
1220     redirect_edge_succ (true_e, new_bb);
1221   else
1222     redirect_edge_succ (false_e, new_bb);
1223 }
1224
1225 /* This function creates new condition statements corresponding 
1226    to original condition STMT, one for each new type, and 
1227    recursively redirect edges to newly generated basic blocks.  */
1228
1229 static void
1230 create_new_stmts_for_cond_expr (tree stmt)
1231 {
1232   tree cond = COND_EXPR_COND (stmt);
1233   tree arg0, arg1, arg;
1234   unsigned str0, str1;
1235   bool s0, s1;
1236   d_str str;
1237   tree type;
1238   bool pos;
1239   int i;
1240   unsigned length = VEC_length (structure, structures);
1241
1242   gcc_assert (TREE_CODE (cond) == EQ_EXPR
1243               || TREE_CODE (cond) == NE_EXPR);
1244
1245   arg0 = TREE_OPERAND (cond, 0);
1246   arg1 = TREE_OPERAND (cond, 1);
1247
1248   str0 = find_structure (strip_type (get_type_of_var (arg0)));
1249   str1 = find_structure (strip_type (get_type_of_var (arg1)));
1250
1251   s0 = (str0 != length) ? true : false;
1252   s1 = (str1 != length) ? true : false;
1253
1254   gcc_assert (s0 || s1);
1255   /* For now we allow only comparison with 0 or NULL.  */
1256   gcc_assert (integer_zerop (arg0) || integer_zerop (arg1));
1257   
1258   str = integer_zerop (arg0) ?
1259     VEC_index (structure, structures, str1): 
1260     VEC_index (structure, structures, str0);
1261   arg = integer_zerop (arg0) ? arg1 : arg0;
1262   pos = integer_zerop (arg0) ? 1 : 0;
1263   
1264   for (i = 0; VEC_iterate (tree, str->new_types, i, type); i++)
1265     {
1266       tree new_arg;
1267
1268       new_arg = find_new_var_of_type (arg, type);
1269       create_new_stmts_for_cond_expr_1 (new_arg, stmt, pos);
1270     }
1271 }
1272
1273 /* Create a new general access to replace original access ACC
1274    for structure type NEW_TYPE.  */
1275
1276 static tree
1277 create_general_new_stmt (struct access_site *acc, tree new_type)
1278 {
1279   tree old_stmt = acc->stmt;
1280   tree var;
1281   tree new_stmt = unshare_expr (old_stmt);
1282   unsigned i;
1283
1284   
1285   for (i = 0; VEC_iterate (tree, acc->vars, i, var); i++)
1286     {
1287       tree *pos;
1288       tree new_var = find_new_var_of_type (var, new_type);
1289       tree lhs, rhs;
1290
1291       gcc_assert (new_var);
1292       finalize_var_creation (new_var);
1293
1294       if (TREE_CODE (new_stmt) == GIMPLE_MODIFY_STMT)
1295         {
1296       
1297           lhs = GIMPLE_STMT_OPERAND (new_stmt, 0);
1298           rhs = GIMPLE_STMT_OPERAND (new_stmt, 1);
1299           
1300           if (TREE_CODE (lhs) == SSA_NAME)
1301             lhs = SSA_NAME_VAR (lhs);
1302           if (TREE_CODE (rhs) == SSA_NAME)
1303             rhs = SSA_NAME_VAR (rhs); 
1304
1305           /* It can happen that rhs is a constructor.
1306            Then we have to replace it to be of new_type.  */
1307           if (TREE_CODE (rhs) == CONSTRUCTOR)
1308             {
1309               /* Dealing only with empty constructors right now.  */
1310               gcc_assert (VEC_empty (constructor_elt, 
1311                                      CONSTRUCTOR_ELTS (rhs)));
1312               rhs = build_constructor (new_type, 0);
1313               GIMPLE_STMT_OPERAND (new_stmt, 1) = rhs;
1314             }
1315           
1316           if (lhs == var)
1317             GIMPLE_STMT_OPERAND (new_stmt, 0) = new_var;
1318           else if (rhs == var)
1319             GIMPLE_STMT_OPERAND (new_stmt, 1) = new_var;
1320           else
1321             {
1322               pos = find_pos_in_stmt (new_stmt, var);
1323               gcc_assert (pos);
1324               *pos = new_var;
1325             }      
1326         }
1327       else
1328         {
1329           pos = find_pos_in_stmt (new_stmt, var);
1330           gcc_assert (pos);
1331           *pos = new_var;
1332         }
1333     }
1334
1335   finalize_stmt (new_stmt);
1336   return new_stmt;
1337 }
1338
1339 /* For each new type in STR this function creates new general accesses
1340    corresponding to the original access ACC.  */
1341
1342 static void
1343 create_new_stmts_for_general_acc (struct access_site *acc, d_str str)
1344 {
1345   tree type;
1346   tree stmt = acc->stmt;
1347   unsigned i;
1348
1349   for (i = 0; VEC_iterate (tree, str->new_types, i, type); i++)
1350     {
1351       tree new_stmt;
1352
1353       new_stmt = create_general_new_stmt (acc, type);
1354       insert_after_stmt (stmt, new_stmt);
1355     }
1356 }
1357
1358 /* This function creates a new general access of structure STR 
1359    to replace the access ACC.  */
1360
1361 static void
1362 create_new_general_access (struct access_site *acc, d_str str)
1363 {
1364   tree stmt = acc->stmt;
1365   switch (TREE_CODE (stmt))
1366     {
1367     case COND_EXPR:
1368       create_new_stmts_for_cond_expr (stmt);
1369       break;
1370
1371     default:
1372       create_new_stmts_for_general_acc (acc, str);
1373     }
1374 }
1375
1376 /* Auxiliary data for creation of accesses.  */
1377 struct create_acc_data
1378 {
1379   basic_block bb;
1380   d_str str;
1381   int field_index;
1382 };
1383
1384 /* This function creates a new general access, defined by SLOT.
1385    DATA is a pointer to create_acc_data structure.  */
1386
1387 static int
1388 create_new_acc (void **slot, void *data)
1389 {
1390   struct access_site *acc = *(struct access_site **) slot;
1391   basic_block bb = ((struct create_acc_data *)data)->bb;
1392   d_str str = ((struct create_acc_data *)data)->str;
1393
1394   if (bb_for_stmt (acc->stmt) == bb)
1395     create_new_general_access (acc, str);
1396   return 1;
1397 }
1398
1399 /* This function creates a new field access, defined by SLOT.
1400    DATA is a pointer to create_acc_data structure.  */
1401
1402 static int
1403 create_new_field_acc (void **slot, void *data)
1404 {
1405   struct field_access_site *f_acc = *(struct field_access_site **) slot;
1406   basic_block bb = ((struct create_acc_data *)data)->bb;
1407   d_str str = ((struct create_acc_data *)data)->str;
1408   int i = ((struct create_acc_data *)data)->field_index;
1409
1410   if (bb_for_stmt (f_acc->stmt) == bb)
1411     create_new_field_access (f_acc, str->fields[i]);
1412   return 1;
1413 }
1414
1415 /* This function creates new accesses for the structure 
1416    type STR in basic block BB.  */
1417
1418 static void
1419 create_new_accs_for_struct (d_str str, basic_block bb)
1420 {
1421   int i;
1422   struct create_acc_data dt;
1423
1424   dt.str = str;
1425   dt.bb = bb;
1426   dt.field_index = -1;
1427       
1428   for (i = 0; i < str->num_fields; i++)
1429     {
1430       dt.field_index = i;
1431
1432       if (str->fields[i].acc_sites)
1433         htab_traverse (str->fields[i].acc_sites, 
1434                        create_new_field_acc, &dt);
1435     }  
1436   if (str->accs)
1437     htab_traverse (str->accs, create_new_acc, &dt);
1438 }
1439
1440 /* This function inserts new variables from new_var, 
1441    defined by SLOT, into varpool.  */ 
1442
1443 static int
1444 update_varpool_with_new_var (void **slot, void *data ATTRIBUTE_UNUSED)
1445 {
1446   new_var n_var = *(new_var *) slot;
1447   tree var;
1448   unsigned i;
1449
1450   for (i = 0; VEC_iterate (tree, n_var->new_vars, i, var); i++)
1451     insert_global_to_varpool (var);
1452   return 1;
1453 }
1454
1455 /* This function prints a field access site, defined by SLOT.  */ 
1456
1457 static int
1458 dump_field_acc (void **slot, void *data ATTRIBUTE_UNUSED)
1459 {
1460   struct field_access_site *f_acc =
1461     *(struct field_access_site **) slot;
1462
1463   fprintf(dump_file, "\n");
1464   if (f_acc->stmt)
1465     print_generic_stmt (dump_file, f_acc->stmt, 0);
1466   if (f_acc->ref_def_stmt)
1467     print_generic_stmt (dump_file, f_acc->ref_def_stmt, 0);
1468   if (f_acc->cast_stmt)
1469     print_generic_stmt (dump_file, f_acc->cast_stmt, 0);
1470   return 1;
1471 }
1472
1473 /* Print field accesses from hashtable F_ACCS.  */
1474
1475 static void
1476 dump_field_acc_sites (htab_t f_accs)
1477 {
1478   if (!dump_file)
1479     return;
1480
1481   if (f_accs)
1482     htab_traverse (f_accs, dump_field_acc, NULL);
1483 }
1484
1485 /* Hash value for fallocs_t.  */
1486
1487 static hashval_t
1488 malloc_hash (const void *x)
1489 {
1490   return htab_hash_pointer (((const_fallocs_t)x)->func);
1491 }
1492
1493 /* This function returns nonzero if function of func_alloc_sites' X 
1494    is equal to Y.  */
1495
1496 static int
1497 malloc_eq (const void *x, const void *y)
1498 {
1499   return ((const_fallocs_t)x)->func == (const_tree)y;
1500 }
1501
1502 /* This function is a callback for traversal over a structure accesses.
1503    It frees an access represented by SLOT.  */
1504
1505 static int
1506 free_accs (void **slot, void *data ATTRIBUTE_UNUSED)
1507 {
1508   struct access_site * acc = *(struct access_site **) slot;
1509
1510   VEC_free (tree, heap, acc->vars);
1511   free (acc);
1512   return 1;
1513 }
1514
1515 /* This is a callback function for traversal over field accesses. 
1516    It frees a field access represented by SLOT.  */
1517
1518 static int
1519 free_field_accs (void **slot, void *data ATTRIBUTE_UNUSED)
1520 {
1521   struct field_access_site *f_acc = *(struct field_access_site **) slot;
1522
1523   free (f_acc);
1524   return 1;
1525 }
1526
1527 /* This function inserts TYPE into vector of UNSUITABLE_TYPES, 
1528    if it is not there yet.  */
1529
1530 static void
1531 add_unsuitable_type (VEC (tree, heap) **unsuitable_types, tree type)
1532 {
1533   unsigned i;
1534   tree t;
1535
1536   if (!type)
1537     return;
1538
1539   type = TYPE_MAIN_VARIANT (type);
1540
1541   for (i = 0; VEC_iterate (tree, *unsuitable_types, i, t); i++)
1542     if (is_equal_types (t, type))
1543       break;
1544   
1545   if (i == VEC_length (tree, *unsuitable_types))
1546     VEC_safe_push (tree, heap, *unsuitable_types, type);
1547 }
1548
1549 /* Given a type TYPE, this function returns the name of the type.  */
1550
1551 static const char *
1552 get_type_name (tree type)
1553 {
1554   if (! TYPE_NAME (type))
1555     return NULL;
1556
1557   if (TREE_CODE (TYPE_NAME (type)) == IDENTIFIER_NODE)
1558     return IDENTIFIER_POINTER (TYPE_NAME (type));
1559   else if (TREE_CODE (TYPE_NAME (type)) == TYPE_DECL
1560            && DECL_NAME (TYPE_NAME (type)))
1561     return IDENTIFIER_POINTER (DECL_NAME (TYPE_NAME (type)));
1562   else
1563     return NULL;
1564 }
1565
1566 /* This function is a temporary hack to overcome the types problem.
1567    When several compilation units are compiled together
1568    with -combine, the TYPE_MAIN_VARIANT of the same type 
1569    can appear differently in different compilation units.
1570    Therefore this function first compares type names.
1571    If there are no names, structure bodies are recursively 
1572    compared.  */
1573
1574 static bool
1575 is_equal_types (tree type1, tree type2)
1576 {
1577   const char * name1,* name2;
1578
1579   if ((!type1 && type2)
1580       ||(!type2 && type1))
1581     return false;
1582
1583   if (!type1 && !type2)
1584     return true;
1585
1586   if (TREE_CODE (type1) != TREE_CODE (type2))
1587     return false;
1588
1589   if (type1 == type2)
1590       return true;
1591
1592   if (TYPE_MAIN_VARIANT (type1) == TYPE_MAIN_VARIANT (type2))
1593       return true;
1594
1595   name1 = get_type_name (type1);
1596   name2 = get_type_name (type2);
1597   
1598   if (name1 && name2 && !strcmp (name1, name2))
1599     return true;
1600
1601   if (name1 && name2 && strcmp (name1, name2))
1602     return false;
1603   
1604   switch (TREE_CODE (type1))
1605     {
1606     case POINTER_TYPE:
1607     case REFERENCE_TYPE:
1608       {
1609         return is_equal_types (TREE_TYPE (type1), TREE_TYPE (type2));
1610       }
1611       break;
1612
1613     case RECORD_TYPE:
1614     case UNION_TYPE:
1615     case QUAL_UNION_TYPE:
1616     case ENUMERAL_TYPE:
1617       {
1618         tree field1;
1619         /* Compare fields of struture.  */
1620         for (field1 = TYPE_FIELDS (type1); field1; 
1621              field1 = TREE_CHAIN (field1))
1622           {
1623             tree field2 = find_field_in_struct_1 (type2, field1);
1624             if (!field2)
1625               return false;
1626           }
1627         return true;
1628       }
1629       break;
1630
1631     case INTEGER_TYPE:
1632       {
1633         if (TYPE_UNSIGNED (type1) == TYPE_UNSIGNED (type2)
1634             && TYPE_PRECISION (type1) == TYPE_PRECISION (type2))
1635           return true;
1636       }
1637       break;
1638
1639     case ARRAY_TYPE:
1640       {
1641         tree d1, d2;
1642         tree max1, min1, max2, min2;
1643
1644         if (!is_equal_types (TREE_TYPE (type1), TREE_TYPE (type2)))
1645           return false;
1646
1647         d1 = TYPE_DOMAIN (type1);
1648         d2 = TYPE_DOMAIN (type2);
1649
1650         if (!d1 || !d2)
1651           return false;
1652
1653         max1 = TYPE_MAX_VALUE (d1);
1654         max2 = TYPE_MAX_VALUE (d2);
1655         min1 = TYPE_MIN_VALUE (d1);
1656         min2 = TYPE_MIN_VALUE (d2);
1657
1658         if (max1 && max2 && min1 && min2
1659             && TREE_CODE (max1) == TREE_CODE (max2)
1660             && TREE_CODE (max1) == INTEGER_CST
1661             && TREE_CODE (min1) == TREE_CODE (min2)
1662             && TREE_CODE (min1) == INTEGER_CST
1663             && tree_int_cst_equal (max1, max2)
1664             && tree_int_cst_equal (min1, min2))
1665           return true;
1666       }
1667       break;
1668
1669     default:
1670         gcc_unreachable();
1671     }
1672
1673   return false;
1674 }
1675
1676 /* This function free non-field accesses from hashtable ACCS.  */
1677
1678 static void
1679 free_accesses (htab_t accs)
1680 {
1681   if (accs)
1682     htab_traverse (accs, free_accs, NULL);  
1683   htab_delete (accs);
1684 }
1685
1686 /* This function free field accesses hashtable F_ACCS.  */
1687
1688 static void
1689 free_field_accesses (htab_t f_accs)
1690 {
1691   if (f_accs)
1692     htab_traverse (f_accs, free_field_accs, NULL);  
1693   htab_delete (f_accs);
1694 }
1695
1696 /* Update call graph with new edge generated by new MALLOC_STMT.
1697    The edge origin is CONTEXT function.  */
1698
1699 static void
1700 update_cgraph_with_malloc_call (tree malloc_stmt, tree context)
1701 {
1702   tree call_expr;
1703   struct cgraph_node *src, *dest;
1704   tree malloc_fn_decl;
1705
1706   if (!malloc_stmt)
1707     return;
1708
1709   call_expr = get_call_expr_in (malloc_stmt);
1710   malloc_fn_decl = get_callee_fndecl (call_expr);
1711     
1712   src = cgraph_node (context);
1713   dest = cgraph_node (malloc_fn_decl);
1714   cgraph_create_edge (src, dest, malloc_stmt, 
1715                       0, 0, bb_for_stmt (malloc_stmt)->loop_depth);
1716 }
1717
1718 /* This function generates set of statements required 
1719    to allocate number NUM of structures of type NEW_TYPE.
1720    The statements are stored in NEW_STMTS. The statement that contain
1721    call to malloc is returned. MALLOC_STMT is an original call to malloc.  */
1722
1723 static tree
1724 create_new_malloc (tree malloc_stmt, tree new_type, tree *new_stmts, tree num)
1725 {
1726   tree new_malloc_size;
1727   tree call_expr, malloc_fn_decl;
1728   tree new_stmt, malloc_res;
1729   tree call_stmt, final_stmt;
1730   tree cast_res;
1731
1732   gcc_assert (num && malloc_stmt && new_type);
1733   *new_stmts = alloc_stmt_list ();
1734
1735   /* Generate argument to malloc as multiplication of num 
1736      and size of new_type.  */
1737   new_stmt = gen_size (num, new_type, &new_malloc_size);
1738   append_to_statement_list (new_stmt, new_stmts);
1739
1740   /* Generate new call for malloc.  */
1741   malloc_res = create_tmp_var (ptr_type_node, NULL);
1742
1743   if (malloc_res)
1744     add_referenced_var (malloc_res);
1745
1746   call_expr = get_call_expr_in (malloc_stmt);
1747   malloc_fn_decl = get_callee_fndecl (call_expr);
1748   call_expr = build_call_expr (malloc_fn_decl, 1, new_malloc_size); 
1749   call_stmt = build_gimple_modify_stmt (malloc_res, call_expr);
1750   finalize_stmt_and_append (new_stmts, call_stmt);
1751
1752   /* Create new cast statement. */
1753   final_stmt = get_final_alloc_stmt (malloc_stmt);
1754   gcc_assert (final_stmt);
1755   new_stmt = gen_cast_stmt (malloc_res, new_type, final_stmt, &cast_res);
1756   append_to_statement_list (new_stmt, new_stmts);
1757  
1758   return call_stmt;      
1759 }
1760
1761 /* This function returns a tree representing 
1762    the number of instances of structure STR_DECL allocated 
1763    by allocation STMT. If new statments are generated, 
1764    they are filled into NEW_STMTS_P.  */
1765
1766 static tree 
1767 gen_num_of_structs_in_malloc (tree stmt, tree str_decl, tree *new_stmts_p)
1768 {
1769   call_expr_arg_iterator iter;
1770   tree arg;
1771   tree call_expr;
1772   tree struct_size;
1773   HOST_WIDE_INT struct_size_int;
1774
1775   if (!stmt)
1776     return NULL_TREE;
1777
1778   /* Get malloc argument.  */
1779   call_expr = get_call_expr_in (stmt);
1780   if (!call_expr)
1781     return NULL_TREE;
1782
1783   arg = first_call_expr_arg (call_expr, &iter);
1784
1785   if (TREE_CODE (arg) != SSA_NAME
1786       && !TREE_CONSTANT (arg))
1787     return NULL_TREE;
1788   
1789   struct_size = TYPE_SIZE_UNIT (str_decl);
1790   struct_size_int = TREE_INT_CST_LOW (struct_size);
1791   
1792   gcc_assert (struct_size);
1793
1794   if (TREE_CODE (arg) == SSA_NAME)
1795     {
1796       tree num, div_stmt;
1797
1798       if (is_result_of_mult (arg, &num, struct_size))
1799           return num;      
1800
1801       num = create_tmp_var (integer_type_node, NULL);
1802
1803       if (num)
1804         add_referenced_var (num);
1805
1806       if (exact_log2 (struct_size_int) == -1)
1807         div_stmt = build_gimple_modify_stmt (num, 
1808                                              build2 (TRUNC_DIV_EXPR, 
1809                                                      integer_type_node,
1810                                                      arg, struct_size));
1811       else
1812         {
1813           tree C =  build_int_cst (integer_type_node,
1814                                    exact_log2 (struct_size_int)); 
1815
1816           div_stmt = 
1817             build_gimple_modify_stmt (num, build2 (RSHIFT_EXPR, 
1818                                                    integer_type_node,
1819                                                    arg, C)); 
1820         }
1821       *new_stmts_p = alloc_stmt_list ();
1822       append_to_statement_list (div_stmt, 
1823                                 new_stmts_p);
1824       finalize_stmt (div_stmt);
1825       return num;
1826     }
1827
1828   if (CONSTANT_CLASS_P (arg)
1829       && multiple_of_p (TREE_TYPE (struct_size), arg, struct_size))   
1830     return int_const_binop (TRUNC_DIV_EXPR, arg, struct_size, 0);
1831
1832   return NULL_TREE; 
1833 }
1834
1835 /* This function is a callback for traversal on new_var's hashtable.
1836    SLOT is a pointer to new_var. This function prints to dump_file 
1837    an original variable and all new variables from the new_var 
1838    pointed by *SLOT.  */ 
1839
1840 static int
1841 dump_new_var (void **slot, void *data ATTRIBUTE_UNUSED)
1842 {
1843   new_var n_var = *(new_var *) slot;
1844   tree var_type;
1845   tree var;
1846   unsigned i;
1847
1848   var_type = get_type_of_var (n_var->orig_var);
1849
1850   fprintf (dump_file, "\nOrig var: ");
1851   print_generic_expr (dump_file, n_var->orig_var, 0);
1852   fprintf (dump_file, " of type ");
1853   print_generic_expr (dump_file, var_type, 0);
1854   fprintf (dump_file, "\n");
1855
1856   for (i = 0;
1857        VEC_iterate (tree, n_var->new_vars, i, var); i++)
1858     {     
1859       var_type = get_type_of_var (var);
1860                   
1861       fprintf (dump_file, "      ");
1862       print_generic_expr (dump_file, var, 0);
1863       fprintf (dump_file, " of type ");
1864       print_generic_expr (dump_file, var_type, 0);
1865       fprintf (dump_file, "\n");
1866     }
1867   return 1;
1868 }
1869
1870 /* This function copies attributes form ORIG_DECL to NEW_DECL.  */
1871
1872 static inline void 
1873 copy_decl_attributes (tree new_decl, tree orig_decl)
1874 {
1875
1876   DECL_ARTIFICIAL (new_decl) = 1;
1877   DECL_EXTERNAL (new_decl) = DECL_EXTERNAL (orig_decl);
1878   TREE_STATIC (new_decl) = TREE_STATIC (orig_decl);
1879   TREE_PUBLIC (new_decl) = TREE_PUBLIC (orig_decl);
1880   TREE_USED (new_decl) = TREE_USED (orig_decl);
1881   DECL_CONTEXT (new_decl) = DECL_CONTEXT (orig_decl);
1882   TREE_THIS_VOLATILE (new_decl) = TREE_THIS_VOLATILE (orig_decl);
1883   TREE_ADDRESSABLE (new_decl) = TREE_ADDRESSABLE (orig_decl);
1884   
1885   if (TREE_CODE (orig_decl) == VAR_DECL)
1886     {
1887       TREE_READONLY (new_decl) = TREE_READONLY (orig_decl);
1888       DECL_TLS_MODEL (new_decl) = DECL_TLS_MODEL (orig_decl);
1889     }
1890 }
1891
1892 /* This function wraps NEW_STR_TYPE in pointers or arrays wrapper 
1893    the same way as a structure type is wrapped in DECL. 
1894    It returns the generated type.  */
1895
1896 static inline tree
1897 gen_struct_type (tree decl, tree new_str_type)
1898 {
1899   tree type_orig = get_type_of_var (decl);
1900   tree new_type = new_str_type;
1901   VEC (type_wrapper_t, heap) *wrapper = VEC_alloc (type_wrapper_t, heap, 10);
1902   type_wrapper_t wr;
1903   type_wrapper_t *wr_p;
1904   
1905   while (POINTER_TYPE_P (type_orig)
1906          || TREE_CODE (type_orig) == ARRAY_TYPE)
1907     {      
1908       if (POINTER_TYPE_P (type_orig))
1909         {
1910           wr.wrap = 0;
1911           wr.domain = NULL_TREE;
1912         }
1913       else if (TREE_CODE (type_orig) == ARRAY_TYPE)
1914         {
1915           wr.wrap = 1;
1916           wr.domain = TYPE_DOMAIN (type_orig);
1917         }
1918       VEC_safe_push (type_wrapper_t, heap, wrapper, &wr);
1919       type_orig = TREE_TYPE (type_orig);
1920     }
1921
1922   while (VEC_length (type_wrapper_t, wrapper) != 0)
1923     {
1924       wr_p = VEC_last (type_wrapper_t, wrapper); 
1925
1926       if (wr_p->wrap) /* Array.  */
1927         new_type = build_array_type (new_type, wr_p->domain);
1928       else /* Pointer.  */
1929         new_type = build_pointer_type (new_type);
1930       
1931       VEC_pop (type_wrapper_t, wrapper);
1932     }
1933
1934   VEC_free (type_wrapper_t, heap, wrapper);  
1935   return new_type;
1936 }
1937
1938 /* This function generates and returns new variable name based on
1939    ORIG_DECL name, combined with index I.
1940    The form of the new name is <orig_name>.<I> .  */
1941
1942 static tree
1943 gen_var_name (tree orig_decl, unsigned HOST_WIDE_INT i)
1944 {
1945   const char *old_name;
1946   char *prefix;
1947   char *new_name;
1948
1949   if (!DECL_NAME (orig_decl)
1950       || !IDENTIFIER_POINTER (DECL_NAME (orig_decl)))
1951      return NULL;
1952
1953   /* If the original variable has a name, create an 
1954      appropriate new name for the new variable.  */
1955
1956   old_name = IDENTIFIER_POINTER (DECL_NAME (orig_decl));
1957   prefix = alloca (strlen (old_name) + 1);
1958   strcpy (prefix, old_name);
1959   ASM_FORMAT_PRIVATE_NAME (new_name, prefix, i);
1960   return get_identifier (new_name);
1961 }
1962
1963 /* This function adds NEW_NODE to hashtable of new_var's NEW_VARS_HTAB. */
1964
1965 static void
1966 add_to_new_vars_htab (new_var new_node, htab_t new_vars_htab)
1967 {
1968   void **slot;
1969
1970   slot = htab_find_slot_with_hash (new_vars_htab, new_node->orig_var,
1971                                    htab_hash_pointer (new_node->orig_var), 
1972                                    INSERT);
1973   *slot = new_node;
1974 }
1975
1976 /* This function creates and returns new_var_data node 
1977    with empty new_vars and orig_var equal to VAR.  */
1978
1979 static new_var
1980 create_new_var_node (tree var, d_str str)
1981 {
1982   new_var node;
1983
1984   node = (new_var) xmalloc (sizeof (struct new_var_data));
1985   node->orig_var = var;
1986   node->new_vars = VEC_alloc (tree, heap, VEC_length (tree, str->new_types));
1987   return node;
1988 }
1989
1990 /* Check whether the type of VAR is potential candidate for peeling.
1991    Returns true if yes, false otherwise.  If yes, TYPE_P will contain
1992    candidate type. If VAR is initialized, the type of VAR will be added
1993    to UNSUITABLE_TYPES.  */
1994
1995 static bool
1996 is_candidate (tree var, tree *type_p, VEC (tree, heap) **unsuitable_types)
1997 {
1998   tree type;
1999   bool initialized = false;
2000
2001   *type_p = NULL;
2002
2003   if (!var)
2004     return false;
2005
2006   /* There is no support of initialized vars.  */
2007   if (TREE_CODE (var) == VAR_DECL
2008       && DECL_INITIAL (var) != NULL_TREE)
2009     initialized = true;
2010   
2011   type = get_type_of_var (var);
2012
2013   if (type)
2014     {
2015       type = TYPE_MAIN_VARIANT (strip_type (type));
2016       if (TREE_CODE (type) != RECORD_TYPE)
2017           return false; 
2018       else
2019         {
2020           if (initialized && unsuitable_types && *unsuitable_types)
2021             {
2022               if (dump_file)
2023                 {
2024                   fprintf (dump_file, "The type ");
2025                   print_generic_expr (dump_file, type, 0);
2026                   fprintf (dump_file, " is initialized...Excluded.");             
2027                 }
2028               add_unsuitable_type (unsuitable_types, type);
2029             }
2030           *type_p = type;
2031           return true;
2032       }
2033     }
2034   else
2035     return false;
2036 }
2037
2038 /* Hash value for field_access_site.  */
2039
2040 static hashval_t
2041 field_acc_hash (const void *x)
2042 {
2043   return htab_hash_pointer (((const struct field_access_site *)x)->stmt);
2044 }
2045
2046 /* This function returns nonzero if stmt of field_access_site X 
2047    is equal to Y.  */
2048
2049 static int
2050 field_acc_eq (const void *x, const void *y)
2051 {
2052   return ((const struct field_access_site *)x)->stmt == (const_tree)y;
2053 }
2054
2055 /* This function prints an access site, defined by SLOT.  */ 
2056
2057 static int
2058 dump_acc (void **slot, void *data ATTRIBUTE_UNUSED)
2059 {
2060   struct access_site *acc = *(struct access_site **) slot;
2061   tree var;
2062   unsigned i;
2063
2064   fprintf(dump_file, "\n");
2065   if (acc->stmt)
2066     print_generic_stmt (dump_file, acc->stmt, 0);
2067   fprintf(dump_file, " : ");
2068
2069   for (i = 0; VEC_iterate (tree, acc->vars, i, var); i++)
2070     {
2071       print_generic_expr (dump_file, var, 0);
2072       fprintf(dump_file, ", ");   
2073     }
2074   return 1;
2075 }
2076
2077 /* This function frees memory allocated for strcuture clusters, 
2078    starting from CLUSTER.  */
2079
2080 static void
2081 free_struct_cluster (struct field_cluster* cluster)
2082 {
2083   if (cluster)
2084     {
2085       if (cluster->fields_in_cluster)
2086         sbitmap_free (cluster->fields_in_cluster);          
2087       if (cluster->sibling)
2088         free_struct_cluster (cluster->sibling);
2089       free (cluster);
2090     }
2091 }
2092
2093 /* Free all allocated memory under the structure node pointed by D_NODE.  */
2094
2095 static void
2096 free_data_struct (d_str d_node)
2097 {
2098   int i;
2099
2100   if (!d_node)
2101     return;
2102  
2103   if (dump_file)
2104     {
2105       fprintf (dump_file, "\nRemoving data structure \"");
2106       print_generic_expr (dump_file, d_node->decl, 0); 
2107       fprintf (dump_file, "\" from data_struct_list.");
2108     }
2109
2110   /* Free all space under d_node.  */
2111   if (d_node->fields)
2112     {
2113       for (i = 0; i < d_node->num_fields; i++)
2114         free_field_accesses (d_node->fields[i].acc_sites);
2115       free (d_node->fields);
2116     }
2117
2118   if (d_node->accs)
2119      free_accesses (d_node->accs);
2120
2121   if (d_node->struct_clustering)
2122     free_struct_cluster (d_node->struct_clustering);
2123
2124   if (d_node->new_types)
2125     VEC_free (tree, heap, d_node->new_types);
2126 }
2127
2128 /* This function creates new general and field accesses in BB.  */
2129
2130 static void
2131 create_new_accesses_in_bb (basic_block bb)
2132 {
2133   d_str str;
2134   unsigned i;
2135
2136   for (i = 0; VEC_iterate (structure, structures, i, str); i++)
2137     create_new_accs_for_struct (str, bb);
2138 }
2139
2140 /* This function adds allocation sites for peeled structures.
2141    M_DATA is vector of allocation sites of function CONTEXT.  */
2142
2143 static void
2144 create_new_alloc_sites (fallocs_t m_data, tree context)
2145 {
2146   alloc_site_t *call;
2147   unsigned j;
2148   
2149   for (j = 0;
2150        VEC_iterate (alloc_site_t, m_data->allocs, j, call); j++)
2151     {
2152       tree stmt = call->stmt;
2153       d_str str = call->str;
2154       tree num;
2155       tree new_stmts = NULL_TREE;
2156       tree last_stmt = get_final_alloc_stmt (stmt);
2157       unsigned i;
2158       tree type;
2159
2160       num = gen_num_of_structs_in_malloc (stmt, str->decl, &new_stmts);
2161       if (new_stmts)
2162         {
2163           last_stmt = tsi_stmt (tsi_last (new_stmts));
2164           insert_after_stmt (last_stmt, new_stmts);
2165         }
2166       
2167       /* Generate an allocation sites for each new structure type.  */      
2168       for (i = 0; 
2169            VEC_iterate (tree, str->new_types, i, type); i++)    
2170         {
2171           tree new_malloc_stmt = NULL_TREE;
2172           tree last_stmt_tmp = NULL_TREE;
2173
2174           new_stmts = NULL_TREE;
2175           new_malloc_stmt = create_new_malloc (stmt, type, &new_stmts, num);
2176           last_stmt_tmp = tsi_stmt (tsi_last (new_stmts));
2177           insert_after_stmt (last_stmt, new_stmts);
2178           update_cgraph_with_malloc_call (new_malloc_stmt, context);
2179           last_stmt = last_stmt_tmp;
2180         }
2181     }
2182 }
2183
2184 /* This function prints new variables from hashtable  
2185    NEW_VARS_HTAB to dump_file.  */
2186
2187 static void
2188 dump_new_vars (htab_t new_vars_htab)
2189 {
2190   if (!dump_file)
2191     return;
2192
2193   if (new_vars_htab)
2194     htab_traverse (new_vars_htab, dump_new_var, NULL);
2195 }
2196
2197 /* Given an original variable ORIG_DECL of structure type STR,
2198    this function generates new variables of the types defined 
2199    by STR->new_type. Generated types are saved in new_var node NODE.
2200    ORIG_DECL should has VAR_DECL tree_code.  */
2201
2202 static void
2203 create_new_var_1 (tree orig_decl, d_str str, new_var node)
2204 {
2205   unsigned i;
2206   tree type;
2207
2208   for (i = 0; 
2209        VEC_iterate (tree, str->new_types, i, type); i++)
2210     {
2211       tree new_decl = NULL;
2212       tree new_name;
2213
2214       new_name = gen_var_name (orig_decl, i);
2215       type = gen_struct_type (orig_decl, type); 
2216
2217       if (is_global_var (orig_decl))
2218         new_decl = build_decl (VAR_DECL, new_name, type); 
2219       else
2220         {
2221           const char *name = new_name ? IDENTIFIER_POINTER (new_name) : NULL;
2222           new_decl = create_tmp_var (type, name);                                  
2223         }
2224       
2225       copy_decl_attributes (new_decl, orig_decl);
2226       VEC_safe_push (tree, heap, node->new_vars, new_decl);
2227     }
2228 }
2229
2230 /* This function creates new variables to 
2231    substitute the original variable VAR_DECL and adds 
2232    them to the new_var's hashtable NEW_VARS_HTAB.  */
2233
2234 static void
2235 create_new_var (tree var_decl, htab_t new_vars_htab)
2236 {
2237   new_var node;
2238   d_str str;
2239   tree type;
2240   unsigned i;
2241
2242   if (!var_decl || is_in_new_vars_htab (var_decl, new_vars_htab))
2243     return;
2244
2245   if (!is_candidate (var_decl, &type, NULL))
2246     return;
2247   
2248   i = find_structure (type);
2249   if (i == VEC_length (structure, structures))
2250     return;
2251
2252   str = VEC_index (structure, structures, i);
2253   node = create_new_var_node (var_decl, str);
2254   create_new_var_1 (var_decl, str, node);
2255   add_to_new_vars_htab (node, new_vars_htab);
2256 }
2257
2258 /* Hash value for new_var.  */
2259
2260 static hashval_t
2261 new_var_hash (const void *x)
2262 {
2263   return htab_hash_pointer (((const_new_var)x)->orig_var);
2264 }
2265
2266 /* This function returns nonzero if orig_var of new_var X is equal to Y.  */
2267
2268 static int
2269 new_var_eq (const void *x, const void *y)
2270 {
2271   return ((const_new_var)x)->orig_var == (const_tree)y;
2272 }
2273
2274 /* This function check whether a structure type represented by STR 
2275    escapes due to ipa-type-escape analysis. If yes, this type is added 
2276    to UNSUITABLE_TYPES vector.  */ 
2277
2278 static void
2279 check_type_escape (d_str str, VEC (tree, heap) **unsuitable_types)
2280 {
2281   tree type = str->decl;
2282
2283   if (!ipa_type_escape_type_contained_p (type))
2284     {
2285       if (dump_file)
2286         {
2287           fprintf (dump_file, "\nEscaping type is ");
2288           print_generic_expr (dump_file, type, 0);
2289         }
2290       add_unsuitable_type (unsuitable_types, type);
2291     }
2292 }
2293
2294 /* Hash value for access_site.  */
2295
2296 static hashval_t
2297 acc_hash (const void *x)
2298 {
2299   return htab_hash_pointer (((const struct access_site *)x)->stmt);
2300 }
2301
2302 /* Return nonzero if stmt of access_site X is equal to Y.  */
2303
2304 static int
2305 acc_eq (const void *x, const void *y)
2306 {
2307   return ((const struct access_site *)x)->stmt == (const_tree)y;
2308 }
2309
2310 /* Given a structure declaration STRUCT_DECL, and number of fields 
2311    in the structure NUM_FIELDS, this function creates and returns 
2312    corresponding field_entry's.  */
2313
2314 static struct field_entry *
2315 get_fields (tree struct_decl, int num_fields)
2316 {
2317   struct field_entry *list;
2318   tree t = TYPE_FIELDS (struct_decl);
2319   int idx = 0;
2320
2321   list = 
2322     (struct field_entry *) xmalloc (num_fields * sizeof (struct field_entry));
2323
2324   for (idx = 0 ; t; t = TREE_CHAIN (t), idx++)
2325     if (TREE_CODE (t) == FIELD_DECL)
2326       {
2327         list[idx].index = idx;
2328         list[idx].decl = t;
2329         list[idx].acc_sites = 
2330           htab_create (32, field_acc_hash, field_acc_eq, NULL);
2331         list[idx].count = 0;
2332         list[idx].field_mapping = NULL_TREE;
2333       }
2334
2335   return list;
2336 }
2337
2338 /* Print non-field accesses from hashtable ACCS of structure.  */
2339
2340 static void
2341 dump_access_sites (htab_t accs)
2342 {
2343   if (!dump_file)
2344     return;
2345
2346   if (accs)
2347     htab_traverse (accs, dump_acc, NULL);
2348 }
2349
2350 /* This function is a callback for alloc_sites hashtable 
2351    traversal. SLOT is a pointer to fallocs_t. This function
2352    removes all allocations of the structure defined by DATA.  */
2353
2354 static int
2355 remove_str_allocs_in_func (void **slot, void *data)
2356 {
2357   fallocs_t fallocs = *(fallocs_t *) slot;
2358   unsigned i = 0;
2359   alloc_site_t *call;
2360
2361   while (VEC_iterate (alloc_site_t, fallocs->allocs, i, call))
2362     {
2363       if (call->str == (d_str) data)
2364         VEC_ordered_remove (alloc_site_t, fallocs->allocs, i);
2365       else
2366         i++;
2367     }
2368
2369   return 1;
2370 }
2371
2372 /* This function remove all entries corresponding to the STR structure
2373    from alloc_sites hashtable.   */
2374
2375 static void
2376 remove_str_allocs (d_str str)
2377 {
2378   if (!str)
2379     return;
2380
2381   if (alloc_sites)
2382     htab_traverse (alloc_sites, remove_str_allocs_in_func, str);
2383 }
2384
2385 /* This function removes the structure with index I from structures vector.  */
2386
2387 static void 
2388 remove_structure (unsigned i)
2389 {    
2390   d_str str;
2391
2392   if (i >= VEC_length (structure, structures))
2393     return;
2394
2395   str = VEC_index (structure, structures, i);
2396   
2397   /* Before removing the structure str, we have to remove its
2398      allocations from alloc_sites hashtable.  */
2399   remove_str_allocs (str);
2400   free_data_struct (str);
2401   VEC_ordered_remove (structure, structures, i);
2402 }
2403
2404 /* Currently we support only EQ_EXPR or NE_EXPR conditions.
2405    COND_STNT is a condition statement to check.  */
2406
2407 static bool
2408 is_safe_cond_expr (tree cond_stmt)
2409 {
2410
2411   tree arg0, arg1;
2412   unsigned str0, str1;
2413   bool s0, s1;
2414   unsigned length = VEC_length (structure, structures);
2415
2416   tree cond = COND_EXPR_COND (cond_stmt);
2417
2418   if (TREE_CODE (cond) != EQ_EXPR
2419       && TREE_CODE (cond) != NE_EXPR)
2420     return false;
2421   
2422   if (TREE_CODE_LENGTH (TREE_CODE (cond)) != 2)
2423     return false;
2424
2425   arg0 = TREE_OPERAND (cond, 0);
2426   arg1 = TREE_OPERAND (cond, 1);
2427
2428   str0 = find_structure (strip_type (get_type_of_var (arg0)));
2429   str1 = find_structure (strip_type (get_type_of_var (arg1)));
2430
2431   s0 = (str0 != length) ? true : false;
2432   s1 = (str1 != length) ? true : false;
2433   
2434   if (!s0 && !s1)
2435     return false;
2436
2437   /* For now we allow only comparison with 0 or NULL.  */
2438   if (!integer_zerop (arg0) && !integer_zerop (arg1))
2439     return false;
2440
2441   return true;
2442 }
2443
2444 /* This function excludes statements, that are 
2445    part of allocation sites or field accesses, from the
2446    hashtable of general accesses. SLOT represents general 
2447    access that will be checked. DATA is a pointer to 
2448    exclude_data structure.  */
2449
2450 static int
2451 exclude_from_accs (void **slot, void *data)
2452 {
2453   struct access_site *acc = *(struct access_site **) slot;
2454   tree fn_decl = ((struct exclude_data *)data)->fn_decl;
2455   d_str str = ((struct exclude_data *)data)->str;
2456
2457   if (is_part_of_malloc (acc->stmt, fn_decl)
2458       || is_part_of_field_access (acc->stmt, str))
2459     {
2460       VEC_free (tree, heap, acc->vars);
2461       free (acc);
2462       htab_clear_slot (str->accs, slot);
2463     }
2464   return 1;
2465 }
2466
2467 /* Callback function for walk_tree called from collect_accesses_in_bb 
2468    function. DATA is the statement which is analyzed.  */
2469
2470 static tree
2471 get_stmt_accesses (tree *tp, int *walk_subtrees, void *data)
2472 {
2473   tree stmt = (tree) data;
2474   tree t = *tp;
2475
2476   if (!t)
2477     return NULL;
2478
2479   switch (TREE_CODE (t))
2480     {
2481     case GIMPLE_MODIFY_STMT:
2482       {
2483         tree lhs = GIMPLE_STMT_OPERAND (t, 0);
2484         tree rhs = GIMPLE_STMT_OPERAND (t, 1);
2485         *walk_subtrees = 1;
2486         walk_tree (&lhs, get_stmt_accesses, data, NULL);
2487         walk_tree (&rhs, get_stmt_accesses, data, NULL);
2488         *walk_subtrees = 0;         
2489       }
2490       break;
2491
2492     case BIT_FIELD_REF:
2493       {
2494         tree var = TREE_OPERAND(t, 0);
2495         tree type = TYPE_MAIN_VARIANT (strip_type (get_type_of_var (var)));
2496         unsigned i = find_structure (type);
2497
2498         if (i != VEC_length (structure, structures))
2499           {
2500             if (dump_file)
2501               {
2502                 fprintf (dump_file, "\nThe type ");
2503                 print_generic_expr (dump_file, type, 0);
2504                 fprintf (dump_file, " has bitfield.");
2505               }     
2506             remove_structure (i);
2507           }
2508       }
2509       break;
2510
2511     case COMPONENT_REF:
2512       {
2513         tree ref = TREE_OPERAND (t, 0);
2514         tree field_decl = TREE_OPERAND (t, 1);
2515
2516
2517         if ((TREE_CODE (ref) == INDIRECT_REF
2518              || TREE_CODE (ref) == ARRAY_REF
2519              || TREE_CODE (ref) == VAR_DECL)
2520             && TREE_CODE (field_decl) == FIELD_DECL)
2521           {
2522             tree type = TYPE_MAIN_VARIANT (TREE_TYPE (ref));
2523             unsigned i = find_structure (type);
2524
2525             if (i != VEC_length (structure, structures))
2526               {
2527                 d_str str = VEC_index (structure, structures, i);
2528                 struct field_entry * field = 
2529                   find_field_in_struct (str, field_decl);
2530
2531                 if (field)
2532                   {
2533                     struct field_access_site *acc = make_field_acc_node ();
2534
2535                     gcc_assert (acc);
2536
2537                     acc->stmt = stmt;
2538                     acc->comp_ref = t;
2539                     acc->ref = ref;
2540                     acc->field_decl = field_decl;
2541
2542                     /* Check whether the access is of the form 
2543                        we can deal with.  */
2544                     if (!decompose_access (str->decl, acc))
2545                       {
2546                         if (dump_file)
2547                           {
2548                             fprintf (dump_file, "\nThe type ");
2549                             print_generic_expr (dump_file, type, 0);
2550                             fprintf (dump_file, 
2551                                      " has complicate access in statement ");
2552                             print_generic_stmt (dump_file, stmt, 0);
2553                           }
2554                         
2555                         remove_structure (i);
2556                         free (acc);
2557                       }
2558                     else
2559                       {
2560                         /* Increase count of field.  */
2561                         basic_block bb = bb_for_stmt (stmt);
2562                         field->count += bb->count;
2563
2564                         /* Add stmt to the acc_sites of field.  */
2565                         add_field_acc_to_acc_sites (acc, field->acc_sites);
2566                       }
2567                     *walk_subtrees = 0;
2568                   }
2569               }       
2570           }
2571       }
2572       break;
2573
2574     case MINUS_EXPR:
2575     case PLUS_EXPR:
2576       {
2577         tree op0 = TREE_OPERAND (t, 0);
2578         tree op1 = TREE_OPERAND (t, 1);
2579         *walk_subtrees = 1;         
2580         walk_tree (&op0, get_stmt_accesses, data, NULL);
2581         walk_tree (&op1, get_stmt_accesses, data, NULL);        
2582         *walk_subtrees = 0;         
2583       }
2584       break;
2585
2586     case COND_EXPR:
2587       {
2588         tree cond = COND_EXPR_COND (t);
2589         int i;
2590         for (i = 0; i < TREE_CODE_LENGTH (TREE_CODE (cond)); i++)
2591           {
2592             tree t = TREE_OPERAND (cond, i);
2593
2594             *walk_subtrees = 1;
2595             walk_tree (&t, get_stmt_accesses, data, NULL);
2596           }
2597         *walk_subtrees = 0;         
2598       }
2599       break;
2600
2601     case VAR_DECL:
2602     case SSA_NAME:
2603       {
2604         unsigned i;
2605
2606         if (TREE_CODE (t) == SSA_NAME)
2607           t = SSA_NAME_VAR (t);
2608
2609         i = find_structure (strip_type (get_type_of_var (t)));
2610         if (i != VEC_length (structure, structures))
2611           {
2612             d_str str;
2613
2614             str = VEC_index (structure, structures, i);
2615             add_access_to_acc_sites (stmt, t, str->accs);
2616           }
2617         *walk_subtrees = 0;
2618       }
2619       break;
2620
2621     case CALL_EXPR:
2622       {
2623         /* It was checked as part of stage1 that structures 
2624            to be transformed cannot be passed as parameters of functions.  */
2625         *walk_subtrees = 0;         
2626       }
2627       break;
2628
2629     default:
2630       return NULL;
2631     }
2632
2633   return NULL;
2634 }
2635
2636 /* Free structures hashtable.  */
2637
2638 static void
2639 free_structures (void)
2640 {
2641   d_str str;
2642   unsigned i;
2643
2644   for (i = 0; VEC_iterate (structure, structures, i, str); i++)
2645     free_data_struct (str);
2646
2647   VEC_free (structure, heap, structures);
2648   structures = NULL;
2649 }
2650
2651 /* This function is a callback for traversal over new_var's hashtable.
2652    SLOT is a pointer to new_var. This function frees memory allocated 
2653    for new_var and pointed by *SLOT.  */
2654
2655 static int
2656 free_new_var (void **slot, void *data ATTRIBUTE_UNUSED)
2657 {
2658   new_var n_var = *(new_var *) slot;
2659
2660   /* Free vector of new_vars.  */
2661   VEC_free (tree, heap, n_var->new_vars);
2662   free (n_var);
2663   return 1;
2664 }
2665
2666 /* Free new_vars hashtable NEW_VARS_HTAB.  */
2667
2668 static void
2669 free_new_vars_htab (htab_t new_vars_htab)
2670 {
2671   if (new_vars_htab)
2672     htab_traverse (new_vars_htab, free_new_var, NULL);  
2673   htab_delete (new_vars_htab);
2674   new_vars_htab = NULL;
2675 }
2676
2677 /* This function creates new general and field accesses that appear in cfun.  */
2678
2679 static void
2680 create_new_accesses_for_func (void)
2681 {
2682   basic_block bb;
2683
2684   FOR_EACH_BB_FN (bb, cfun)
2685     create_new_accesses_in_bb (bb);
2686 }
2687
2688 /* Create new allocation sites for the function represented by NODE.  */
2689
2690 static void
2691 create_new_alloc_sites_for_func (struct cgraph_node *node)
2692 {
2693   fallocs_t fallocs = get_fallocs (node->decl);
2694
2695   if (fallocs)
2696     create_new_alloc_sites (fallocs, node->decl);
2697 }
2698
2699 /* For each local variable of structure type from the vector of structures
2700    this function generates new variable(s) to replace it.  */
2701
2702 static void
2703 create_new_local_vars (void)
2704 {
2705   tree var;
2706   referenced_var_iterator rvi;
2707    
2708   new_local_vars = htab_create (num_referenced_vars, 
2709                                 new_var_hash, new_var_eq, NULL);
2710
2711   FOR_EACH_REFERENCED_VAR (var, rvi)
2712     {
2713       if (!is_global_var (var))
2714         create_new_var (var, new_local_vars);
2715     }
2716
2717   if (new_local_vars)
2718     htab_traverse (new_local_vars, finalize_new_vars_creation, NULL); 
2719   dump_new_vars (new_local_vars);
2720 }
2721
2722 /* This function prints the SHIFT number of spaces to the DUMP_FILE.  */
2723
2724 static inline void
2725 print_shift (unsigned HOST_WIDE_INT shift)
2726 {
2727   unsigned HOST_WIDE_INT sh = shift;
2728
2729   while (sh--)
2730     fprintf (dump_file, " ");    
2731 }
2732
2733 /* This function updates field_mapping of FIELDS in CLUSTER with NEW_TYPE.  */
2734
2735 static inline void
2736 update_fields_mapping (struct field_cluster *cluster, tree new_type,
2737                        struct field_entry * fields, int num_fields)
2738 {
2739   int i;
2740
2741   for (i = 0; i < num_fields; i++)
2742     if (TEST_BIT (cluster->fields_in_cluster, i))
2743         fields[i].field_mapping = new_type;  
2744 }
2745
2746 /* This functions builds structure with FIELDS, 
2747    NAME and attributes similar to ORIG_STRUCT. 
2748    It returns the newly created structure.  */
2749
2750 static tree
2751 build_basic_struct (tree fields, tree name, tree orig_struct)
2752 {
2753   tree attributes = NULL_TREE;
2754   tree ref = 0;
2755   tree x;
2756
2757   if (TYPE_ATTRIBUTES (orig_struct))
2758     attributes = unshare_expr (TYPE_ATTRIBUTES (orig_struct));
2759   ref = make_node (RECORD_TYPE);
2760   TYPE_SIZE (ref) = 0;
2761   decl_attributes (&ref, attributes, (int) ATTR_FLAG_TYPE_IN_PLACE); 
2762   TYPE_PACKED (ref) = TYPE_PACKED (orig_struct);
2763   for (x = fields; x; x = TREE_CHAIN (x))
2764     {
2765       DECL_CONTEXT (x) = ref;
2766       DECL_PACKED (x) |= TYPE_PACKED (ref);
2767     }
2768   TYPE_FIELDS (ref) = fields;
2769   layout_type (ref);
2770   TYPE_NAME (ref) = name;
2771
2772   return ref;
2773 }
2774
2775 /* This function copies FIELDS from CLUSTER into TREE_CHAIN as part 
2776    of preparation for new structure building. NUM_FIELDS is a total 
2777    number of fields in the structure. The function returns newly 
2778    generated fields.  */
2779
2780 static tree
2781 create_fields (struct field_cluster * cluster, 
2782                struct field_entry * fields, int num_fields)
2783 {
2784   int i;
2785   tree new_types = NULL_TREE;
2786   tree last = NULL_TREE;
2787
2788   for (i = 0; i < num_fields; i++)
2789     if (TEST_BIT (cluster->fields_in_cluster, i))
2790       {
2791         tree new_decl = unshare_expr (fields[i].decl);
2792
2793         if (!new_types)
2794           new_types = new_decl;
2795         else
2796           TREE_CHAIN (last) = new_decl;
2797         last = new_decl;
2798       }
2799
2800   TREE_CHAIN (last) = NULL_TREE;
2801   return new_types;
2802
2803 }
2804
2805 /* This function creates a cluster name. The name is based on 
2806    the original structure name, if it is present. It has a form:
2807    
2808    <original_struct_name>_sub.<CLUST_NUM>
2809
2810    The original structure name is taken from the type of DECL.
2811    If an original structure name is not present, it's generated to be:
2812
2813    struct.<STR_NUM>
2814
2815    The function returns identifier of the new cluster name.  */
2816
2817 static inline tree
2818 gen_cluster_name (tree decl, int clust_num, int str_num)
2819 {
2820   const char * orig_name = get_type_name (decl);
2821   char * tmp_name = NULL;
2822   char * prefix;
2823   char * new_name;
2824   size_t len;
2825   
2826   if (!orig_name)
2827     ASM_FORMAT_PRIVATE_NAME(tmp_name, "struct", str_num);
2828
2829   len = strlen (tmp_name ? tmp_name : orig_name) + strlen ("_sub");
2830   prefix = alloca (len + 1);
2831   memcpy (prefix, tmp_name ? tmp_name : orig_name, 
2832           strlen (tmp_name ? tmp_name : orig_name));
2833   strcpy (prefix + strlen (tmp_name ? tmp_name : orig_name), "_sub");      
2834   
2835   ASM_FORMAT_PRIVATE_NAME (new_name, prefix, clust_num);
2836   return get_identifier (new_name);
2837 }
2838
2839 /* This function checks whether the structure STR has bitfields.
2840    If yes, this structure type is added to UNSUITABLE_TYPES vector.  */
2841
2842 static void
2843 check_bitfields (d_str str, VEC (tree, heap) **unsuitable_types)
2844 {
2845   tree type = str->decl;
2846   int i;
2847
2848   for (i = 0; i < str->num_fields; i++)
2849     if (DECL_BIT_FIELD (str->fields[i].decl))
2850       {
2851         add_unsuitable_type (unsuitable_types, type);
2852         if (dump_file)
2853         {
2854           fprintf (dump_file, "\nType ");
2855           print_generic_expr (dump_file, type, 0);
2856           fprintf (dump_file, "\nescapes due to bitfield ");
2857           print_generic_expr (dump_file, str->fields[i].decl, 0);
2858         }
2859         break;
2860       }
2861 }
2862
2863 /* This function adds to UNSUITABLE_TYPES those types that escape 
2864    due to results of ipa-type-escpae analysis. See ipa-type-escpae.[c,h].  */
2865
2866 static void
2867 exclude_escaping_types_1 (VEC (tree, heap) **unsuitable_types)
2868 {
2869   d_str str;
2870   unsigned i;
2871
2872   for (i = 0; VEC_iterate (structure, structures, i, str); i++)
2873     check_type_escape (str, unsuitable_types);
2874 }
2875
2876 /* If a structure type is a return type of any function,
2877    we cannot transform it. Such type is added to UNSUITABLE_TYPES vector.  */
2878
2879 static void
2880 exclude_returned_types (VEC (tree, heap) **unsuitable_types)
2881 {
2882   struct cgraph_node *c_node;
2883
2884   for (c_node = cgraph_nodes; c_node; c_node = c_node->next)
2885     {
2886       tree ret_t = TREE_TYPE (TREE_TYPE (c_node->decl));
2887
2888       if (ret_t)
2889         {
2890           ret_t = strip_type (ret_t);
2891           if (TREE_CODE (ret_t) == RECORD_TYPE)
2892             {
2893               add_unsuitable_type (unsuitable_types, TYPE_MAIN_VARIANT (ret_t));
2894               if (dump_file)
2895                 {
2896                   fprintf (dump_file, "\nThe type \"");
2897                   print_generic_expr (dump_file, ret_t, 0);
2898                   fprintf (dump_file,
2899                            "\" is return type of function...Excluded.");
2900                 }
2901             }
2902         }
2903     }
2904 }
2905
2906 /* This function looks for parameters of local functions 
2907    which are of structure types, or derived from them (arrays 
2908    of structures, pointers to structures, or their combinations).
2909    We are not handling peeling of such structures right now.
2910    The found structures types are added to UNSUITABLE_TYPES vector.  */
2911
2912 static void
2913 exclude_types_passed_to_local_func (VEC (tree, heap) **unsuitable_types)
2914 {
2915   struct cgraph_node *c_node;
2916
2917   for (c_node = cgraph_nodes; c_node; c_node = c_node->next)
2918     if (cgraph_function_body_availability (c_node) == AVAIL_LOCAL)
2919       {
2920         tree fn = c_node->decl;
2921         tree arg;
2922         
2923         for (arg = DECL_ARGUMENTS (fn); arg; arg = TREE_CHAIN (arg))
2924           {
2925             tree type = TREE_TYPE (arg);
2926
2927             type = strip_type (type);
2928             if (TREE_CODE (type) == RECORD_TYPE)
2929               {
2930                 add_unsuitable_type (unsuitable_types, 
2931                                      TYPE_MAIN_VARIANT (type));
2932                 if (dump_file)
2933                   {
2934                     fprintf (dump_file, "\nPointer to type \"");
2935                     print_generic_expr (dump_file, type, 0);
2936                     fprintf (dump_file, 
2937                              "\" is passed to local function...Excluded.");                              
2938                   }
2939               }
2940           }
2941       }
2942 }
2943
2944 /* This function analyzes structure form of structures 
2945    potential for transformation. If we are not capable to transform
2946    structure of some form, we remove it from the structures hashtable.
2947    Right now we cannot handle nested structs, when nesting is 
2948    through any level of pointers or arrays.  
2949
2950    TBD: release these constrains in future.
2951
2952    Note, that in this function we suppose that all structures 
2953    in the program are members of the structures hashtable right now, 
2954    without excluding escaping types.  */
2955
2956 static void
2957 check_struct_form (d_str str, VEC (tree, heap) **unsuitable_types)
2958 {
2959   int i;
2960
2961   for (i = 0; i < str->num_fields; i++)
2962     {
2963       tree f_type = strip_type(TREE_TYPE (str->fields[i].decl));
2964           
2965       if (TREE_CODE (f_type) == RECORD_TYPE)
2966         {
2967           add_unsuitable_type (unsuitable_types, TYPE_MAIN_VARIANT (f_type));
2968           add_unsuitable_type (unsuitable_types, str->decl);
2969           if (dump_file)
2970             {
2971               fprintf (dump_file, "\nType ");
2972               print_generic_expr (dump_file, f_type, 0);
2973               fprintf (dump_file, " is a field in the structure ");
2974               print_generic_expr (dump_file, str->decl, 0);
2975               fprintf (dump_file, ". Escaping...");
2976             }
2977         }
2978     }
2979 }
2980
2981 /* This function adds a structure TYPE to the vector of structures,
2982    if it's not already there.  */
2983
2984 static void
2985 add_structure (tree type)
2986 {
2987   struct data_structure node;
2988   unsigned i;
2989   int num_fields;
2990
2991   type = TYPE_MAIN_VARIANT (type);
2992
2993   i = find_structure (type);
2994
2995   if (i != VEC_length (structure, structures))
2996     return;
2997
2998   num_fields = fields_length (type);
2999   node.decl = type;
3000   node.num_fields = num_fields;
3001   node.fields = get_fields (type, num_fields);
3002   node.struct_clustering = NULL;
3003   node.accs = htab_create (32, acc_hash, acc_eq, NULL);
3004   node.new_types = VEC_alloc (tree, heap, num_fields);
3005   node.count = 0;
3006
3007   VEC_safe_push (structure, heap, structures, &node);
3008
3009   if (dump_file)
3010     {
3011       fprintf (dump_file, "\nAdding data structure \"");
3012       print_generic_expr (dump_file, type, 0); 
3013       fprintf (dump_file, "\" to data_struct_list.");
3014     }
3015 }
3016
3017 /* This function adds an allocation site to alloc_sites hashtable.
3018    The allocation site appears in STMT of function FN_DECL and 
3019    allocates the structure represented by STR.  */
3020
3021 static void
3022 add_alloc_site (tree fn_decl, tree stmt, d_str str)
3023 {
3024   fallocs_t fallocs = NULL;
3025   alloc_site_t m_call;
3026
3027   m_call.stmt = stmt;
3028   m_call.str = str;
3029
3030   fallocs = 
3031     (fallocs_t) htab_find_with_hash (alloc_sites,
3032                                      fn_decl, htab_hash_pointer (fn_decl));
3033
3034   if (!fallocs)
3035     {
3036       void **slot;
3037
3038       fallocs = (fallocs_t) 
3039         xmalloc (sizeof (struct func_alloc_sites));
3040       fallocs->func = fn_decl;
3041       fallocs->allocs = VEC_alloc (alloc_site_t, heap, 1);
3042       slot = htab_find_slot_with_hash (alloc_sites, fn_decl,
3043                                       htab_hash_pointer (fn_decl), INSERT);
3044       *slot = fallocs;
3045     }
3046   VEC_safe_push (alloc_site_t, heap, 
3047                  fallocs->allocs, &m_call);
3048   
3049   if (dump_file)
3050     {
3051       fprintf (dump_file, "\nAdding stmt ");
3052       print_generic_stmt (dump_file, stmt, 0);
3053       fprintf (dump_file, " to list of mallocs.");
3054     }
3055 }
3056
3057 /* This function returns true if the result of STMT, that contains a call
3058    to an allocation function, is cast to one of the structure types.
3059    STMT should be of the form:    T.2 = <alloc_func> (T.1);
3060    If true, I_P contains an index of an allocated structure. 
3061    Otherwise I_P contains the length of the vector of structures.  */
3062
3063 static bool
3064 is_alloc_of_struct (tree stmt, unsigned *i_p)
3065 {
3066   tree lhs;
3067   tree type;
3068   tree final_stmt;
3069
3070   final_stmt = get_final_alloc_stmt (stmt);
3071
3072   if (!final_stmt)
3073     return false;
3074
3075   /* final_stmt should be of the form:
3076      T.3 = (struct_type *) T.2; */
3077
3078   if (TREE_CODE (final_stmt) != GIMPLE_MODIFY_STMT)
3079     return false;
3080
3081   lhs = GIMPLE_STMT_OPERAND (final_stmt, 0);      
3082
3083   type = get_type_of_var (lhs);
3084       
3085   if (!type)
3086     return false;
3087
3088   if (!POINTER_TYPE_P (type)
3089       || TREE_CODE (strip_type (type)) != RECORD_TYPE)
3090     return false;
3091
3092   *i_p = find_structure (strip_type (type));
3093
3094   if (*i_p == VEC_length (structure, structures))
3095     return false;
3096
3097   return true;
3098 }
3099
3100 /* This function prints non-field and field accesses 
3101    of the structure STR.  */ 
3102
3103 static void
3104 dump_accs (d_str str)
3105 {
3106   int i;
3107
3108   fprintf (dump_file, "\nAccess sites of struct ");
3109   print_generic_expr (dump_file, str->decl, 0);
3110
3111   for (i = 0; i < str->num_fields; i++)
3112     {
3113       fprintf (dump_file, "\nAccess site of field ");
3114       print_generic_expr (dump_file, str->fields[i].decl, 0);
3115       dump_field_acc_sites (str->fields[i].acc_sites);   
3116       fprintf (dump_file, ":\n");
3117     }
3118   fprintf (dump_file, "\nGeneral access sites\n");
3119   dump_access_sites (str->accs);   
3120 }
3121
3122 /* This function checks whether an access statement, pointed by SLOT,
3123    is a condition we are capable to transform.  It returns false if not,
3124    setting bool *DATA to false.  */
3125  
3126 static int
3127 safe_cond_expr_check (void **slot, void *data)
3128 {
3129   struct access_site *acc = *(struct access_site **) slot;
3130
3131   if (TREE_CODE (acc->stmt) == COND_EXPR
3132       && !is_safe_cond_expr (acc->stmt))
3133     {
3134       if (dump_file)
3135         {
3136           fprintf (dump_file, "\nUnsafe conditional statement ");
3137           print_generic_stmt (dump_file, acc->stmt, 0);
3138         }
3139       *(bool *) data = false;
3140       return 0;
3141     }
3142   return 1;
3143 }
3144
3145 /* This function excludes statements that are part of allocation sites and
3146    field accesses from the hashtable of general accesses of the structure
3147    type STR. Only accesses that belong to the function represented by
3148    NODE are treated.  */
3149
3150 static void
3151 exclude_alloc_and_field_accs_1 (d_str str, struct cgraph_node *node)
3152 {
3153   struct exclude_data dt;
3154   dt.str = str;
3155   dt.fn_decl = node->decl;
3156
3157   if (dt.str->accs)
3158     htab_traverse (dt.str->accs, exclude_from_accs, &dt);  
3159 }
3160
3161 /* Collect accesses to the structure types that apear in basic bloack BB.  */
3162
3163 static void
3164 collect_accesses_in_bb (basic_block bb)
3165 {
3166   block_stmt_iterator bsi;
3167
3168   for (bsi = bsi_start (bb); ! bsi_end_p (bsi); bsi_next (&bsi))
3169     {
3170       tree stmt = bsi_stmt (bsi);
3171
3172       /* In asm stmt we cannot always track the arguments,
3173          so we just give up.  */
3174       if (TREE_CODE (stmt) == ASM_EXPR)
3175         {
3176           free_structures ();
3177           break;
3178         }
3179
3180       walk_tree (&stmt, get_stmt_accesses, stmt, NULL);
3181     }
3182 }
3183
3184 /* This function generates cluster substructure that cointains FIELDS.
3185    The cluster added to the set of clusters of the structure SRT.  */
3186
3187 static void
3188 gen_cluster (sbitmap fields, d_str str)
3189 {
3190   struct field_cluster *crr_cluster = NULL;
3191
3192   crr_cluster = 
3193     (struct field_cluster *) xcalloc (1, sizeof (struct field_cluster));
3194   crr_cluster->sibling = str->struct_clustering;
3195   str->struct_clustering = crr_cluster;
3196   crr_cluster->fields_in_cluster = fields;
3197 }
3198
3199 /* This function peels a field with the index I from the structure DS.  */
3200
3201 static void
3202 peel_field (int i, d_str ds)
3203 {
3204   struct field_cluster *crr_cluster = NULL;
3205
3206   crr_cluster = 
3207     (struct field_cluster *) xcalloc (1, sizeof (struct field_cluster));
3208   crr_cluster->sibling = ds->struct_clustering;
3209   ds->struct_clustering = crr_cluster;
3210   crr_cluster->fields_in_cluster =
3211     sbitmap_alloc ((unsigned int) ds->num_fields);
3212   sbitmap_zero (crr_cluster->fields_in_cluster);
3213   SET_BIT (crr_cluster->fields_in_cluster, i);  
3214 }
3215
3216 /* This function calculates maximum field count in 
3217    the structure STR.  */
3218
3219 static gcov_type
3220 get_max_field_count (d_str str)
3221 {
3222   gcov_type max = 0;
3223   int i;
3224
3225   for (i = 0; i < str->num_fields; i++)
3226     if (str->fields[i].count > max)
3227       max = str->fields[i].count; 
3228
3229   return max;
3230 }
3231
3232 /* Do struct-reorg transformation for individual function 
3233    represented by NODE. All structure types relevant 
3234    for this function are transformed.  */
3235
3236 static void
3237 do_reorg_for_func (struct cgraph_node *node)
3238 {
3239   create_new_local_vars ();  
3240   create_new_alloc_sites_for_func (node);
3241   create_new_accesses_for_func ();
3242   update_ssa (TODO_update_ssa);
3243   cleanup_tree_cfg ();
3244
3245   /* Free auxiliary data representing local variables.  */
3246   free_new_vars_htab (new_local_vars); 
3247 }
3248
3249 /* Print structure TYPE, its name, if it exists, and body.
3250    INDENT defines the level of indentation (similar 
3251    to the option -i of indent command). SHIFT parameter 
3252    defines a number of spaces by which a structure will 
3253    be shifted right.  */
3254
3255 static void
3256 dump_struct_type (tree type, unsigned HOST_WIDE_INT indent,
3257                    unsigned HOST_WIDE_INT shift)
3258 {
3259   const char *struct_name;
3260   tree field;
3261
3262   if (!type || !dump_file)
3263     return;
3264
3265   if (TREE_CODE (type) != RECORD_TYPE)
3266     {
3267       print_generic_expr (dump_file, type, 0);
3268       return;
3269     }
3270   
3271   print_shift (shift);
3272   struct_name = get_type_name (type);  
3273   fprintf (dump_file, "struct ");
3274   if (struct_name)    
3275     fprintf (dump_file, "%s\n",struct_name);
3276   print_shift (shift);
3277   fprintf (dump_file, "{\n");
3278        
3279   for (field = TYPE_FIELDS (type); field; 
3280        field = TREE_CHAIN (field))
3281     {
3282       unsigned HOST_WIDE_INT s = indent;
3283       tree f_type = TREE_TYPE (field);
3284       
3285       print_shift (shift);
3286       while (s--)
3287         fprintf (dump_file, " ");
3288       dump_struct_type (f_type, indent, shift + indent);
3289       fprintf(dump_file, " ");
3290       print_generic_expr (dump_file, field, 0);
3291       fprintf(dump_file, ";\n");
3292     }
3293   print_shift (shift);
3294   fprintf (dump_file, "}\n");
3295 }
3296
3297 /* This function creates new structure types to replace original type, 
3298    indicated by STR->decl. The names of the new structure types are 
3299    derived from the original structure type. If the original structure 
3300    type has no name, we assume that its name is 'struct.<STR_NUM>'.  */
3301
3302 static void
3303 create_new_type (d_str str, int *str_num)
3304 {
3305   int cluster_num = 0;
3306
3307   struct field_cluster *cluster = str->struct_clustering;
3308   while (cluster)
3309     {     
3310       tree  name = gen_cluster_name (str->decl, cluster_num, 
3311                                      *str_num);
3312       tree fields;
3313       tree new_type;
3314       cluster_num++;
3315            
3316       fields = create_fields (cluster, str->fields, 
3317                               str->num_fields);
3318       new_type = build_basic_struct (fields, name, str->decl);
3319           
3320       update_fields_mapping (cluster, new_type, 
3321                              str->fields, str->num_fields);
3322
3323       VEC_safe_push (tree, heap, str->new_types, new_type);
3324       cluster = cluster->sibling; 
3325     }
3326   (*str_num)++;
3327 }
3328
3329 /* This function is a callback for alloc_sites hashtable 
3330    traversal. SLOT is a pointer to fallocs_t. 
3331    This function frees memory pointed by *SLOT.  */
3332
3333 static int
3334 free_falloc_sites (void **slot, void *data ATTRIBUTE_UNUSED)
3335 {
3336   fallocs_t fallocs = *(fallocs_t *) slot;
3337
3338   VEC_free (alloc_site_t, heap, fallocs->allocs);
3339   free (fallocs);
3340   return 1;
3341 }
3342
3343 /* Remove structures collected in UNSUITABLE_TYPES
3344    from structures vector.  */
3345
3346 static void
3347 remove_unsuitable_types (VEC (tree, heap) *unsuitable_types)
3348 {
3349   d_str str;
3350   tree type;
3351   unsigned i, j;
3352
3353   for (j = 0; VEC_iterate (tree, unsuitable_types, j, type); j++)
3354     for (i = 0; VEC_iterate (structure, structures, i, str); i++)
3355       if (is_equal_types (str->decl, type))
3356         {
3357           remove_structure (i);
3358           break;
3359         }
3360 }
3361
3362 /* Exclude structure types with bitfields.
3363    We would not want to interfere with other optimizations 
3364    that can be done in this case. The structure types with 
3365    bitfields are added to UNSUITABLE_TYPES vector.  */
3366
3367 static void
3368 exclude_types_with_bit_fields (VEC (tree, heap) **unsuitable_types)
3369 {
3370   d_str str;
3371   unsigned i;
3372
3373   for (i = 0; VEC_iterate (structure, structures, i, str); i++)
3374     check_bitfields (str, unsuitable_types);
3375 }
3376
3377 /* This function checks three types of escape. A structure type escapes:
3378
3379    1. if it's a type of parameter of a local function.
3380    2. if it's a type of function return value.
3381    3. if it escapes as a result of ipa-type-escape analysis.  
3382
3383   The escaping structure types are added to UNSUITABLE_TYPES vector.  */
3384
3385 static void
3386 exclude_escaping_types (VEC (tree, heap) **unsuitable_types)
3387 {
3388   exclude_types_passed_to_local_func (unsuitable_types);
3389   exclude_returned_types (unsuitable_types);
3390   exclude_escaping_types_1 (unsuitable_types);
3391 }
3392
3393 /* This function analyzes whether the form of 
3394    structure is such that we are capable to transform it. 
3395    Nested structures are checked here. Unsuitable structure
3396    types are added to UNSUITABLE_TYPE vector.  */
3397
3398 static void
3399 analyze_struct_form (VEC (tree, heap) **unsuitable_types)
3400 {
3401   d_str str;
3402   unsigned i;
3403
3404   for (i = 0; VEC_iterate (structure, structures, i, str); i++)
3405     check_struct_form (str, unsuitable_types);
3406 }
3407
3408 /* This function looks for structure types instantiated in the program. 
3409    The candidate types are added to the structures vector. 
3410    Unsuitable types are collected into UNSUITABLE_TYPES vector.  */
3411
3412 static void
3413 build_data_structure (VEC (tree, heap) **unsuitable_types)
3414 {
3415   tree var, type;
3416   tree var_list;
3417   struct varpool_node *current_varpool;
3418   struct cgraph_node *c_node;
3419
3420   /* Check global variables.  */ 
3421   FOR_EACH_STATIC_VARIABLE (current_varpool)
3422     {
3423       var = current_varpool->decl;
3424       if (is_candidate (var, &type, unsuitable_types))
3425         add_structure (type);
3426     }
3427
3428   /* Now add structures that are types of function parameters and 
3429      local variables.  */
3430   for (c_node = cgraph_nodes; c_node; c_node = c_node->next)
3431     {
3432       enum availability avail = 
3433         cgraph_function_body_availability (c_node);
3434
3435       /* We need AVAIL_AVAILABLE for main function.  */
3436       if (avail == AVAIL_LOCAL || avail == AVAIL_AVAILABLE)
3437         {
3438           struct function *fn = DECL_STRUCT_FUNCTION (c_node->decl);
3439
3440           for (var = DECL_ARGUMENTS (c_node->decl); var; 
3441                var = TREE_CHAIN (var))
3442               if (is_candidate (var, &type, unsuitable_types))
3443                 add_structure (type);
3444
3445           /* Check function local variables.  */
3446           for (var_list = fn->unexpanded_var_list; var_list; 
3447                var_list = TREE_CHAIN (var_list))
3448             {
3449               var = TREE_VALUE (var_list);
3450
3451               if (is_candidate (var, &type, unsuitable_types))
3452                 add_structure (type);
3453             }
3454         }
3455     }
3456 }
3457
3458 /* This function returns true if the program contains 
3459    a call to user defined allocation function, or other
3460    functions that can interfere with struct-reorg optimizations.  */
3461
3462 static bool
3463 program_redefines_malloc_p (void)
3464 {
3465   struct cgraph_node *c_node;
3466   struct cgraph_node *c_node2;
3467   struct cgraph_edge *c_edge;
3468   tree fndecl;
3469   tree fndecl2;
3470   tree call_expr;
3471   
3472   for (c_node = cgraph_nodes; c_node; c_node = c_node->next)
3473     {
3474       fndecl = c_node->decl;
3475
3476       for (c_edge = c_node->callees; c_edge; c_edge = c_edge->next_callee)
3477         {
3478           call_expr = get_call_expr_in (c_edge->call_stmt);
3479           c_node2 = c_edge->callee;
3480           fndecl2 = c_node2->decl;
3481           if (call_expr)
3482             {
3483               const char * fname = get_name (fndecl2);
3484
3485               if ((call_expr_flags (call_expr) & ECF_MALLOC) &&
3486                   (DECL_FUNCTION_CODE (fndecl2) != BUILT_IN_MALLOC) &&
3487                   (DECL_FUNCTION_CODE (fndecl2) != BUILT_IN_CALLOC) &&
3488                   (DECL_FUNCTION_CODE (fndecl2) != BUILT_IN_ALLOCA))
3489                 return true;
3490
3491               /* Check that there is no __builtin_object_size,
3492                __builtin_offsetof, or realloc's in the program.  */
3493               if (DECL_FUNCTION_CODE (fndecl2) == BUILT_IN_OBJECT_SIZE
3494                   || !strcmp (fname, "__builtin_offsetof")
3495                   || !strcmp (fname, "realloc"))
3496                 return true;            
3497             }
3498         }
3499     }
3500   
3501   return false;
3502 }
3503
3504 /* In this function we assume that an allocation statement 
3505
3506    var = (type_cast) malloc (size);
3507    
3508    is converted into the following set of statements:
3509
3510    T.1 = size;
3511    T.2 = malloc (T.1);
3512    T.3 = (type_cast) T.2;
3513    var = T.3;
3514
3515    In this function we collect into alloc_sites the allocation 
3516    sites of variables of structure types that are present 
3517    in structures vector.  */
3518
3519 static void
3520 collect_alloc_sites (void)
3521 {
3522   struct cgraph_node *node;
3523   struct cgraph_edge *cs;
3524
3525   for (node = cgraph_nodes; node; node = node->next)
3526     if (node->analyzed && node->decl)
3527       {
3528         for (cs = node->callees; cs; cs = cs->next_callee)
3529           {
3530             tree stmt = cs->call_stmt;
3531
3532             if (stmt)
3533               {
3534                 tree call = get_call_expr_in (stmt);
3535                 tree decl;
3536
3537                 if (call && (decl = get_callee_fndecl (call)) 
3538                     && TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
3539                   {
3540                     unsigned i;
3541
3542                     if (is_alloc_of_struct (stmt, &i))
3543                       {
3544                         /* We support only malloc now.  */
3545                         if (DECL_FUNCTION_CODE (decl) == BUILT_IN_MALLOC)
3546                           {
3547                             d_str str;
3548                             
3549                             str = VEC_index (structure, structures, i);
3550                             add_alloc_site (node->decl, stmt, str);
3551                           }
3552                         else
3553                           {
3554                             if (dump_file)
3555                               {
3556                                 fprintf (dump_file, 
3557                                          "\nUnsupported allocation function ");
3558                                 print_generic_stmt (dump_file, stmt, 0);
3559                               }
3560                             remove_structure (i);               
3561                           }
3562                       }
3563                   }
3564               }       
3565           }
3566       }
3567 }
3568
3569 /* Print collected accesses.  */
3570
3571 static void
3572 dump_accesses (void)
3573 {
3574   d_str str;
3575   unsigned i;
3576
3577   if (!dump_file)
3578     return;
3579
3580   for (i = 0; VEC_iterate (structure, structures, i, str); i++)
3581     dump_accs (str);
3582 }
3583
3584 /* This function checks whether the accesses of structures in condition 
3585    expressions are of the kind we are capable to transform. 
3586    If not, such structures are removed from the vector of structures.  */
3587
3588 static void
3589 check_cond_exprs (void)
3590 {
3591   d_str str;
3592   unsigned i;
3593
3594   i = 0;
3595   while (VEC_iterate (structure, structures, i, str))
3596     {
3597       bool safe_p = true;
3598
3599       if (str->accs)
3600         htab_traverse (str->accs, safe_cond_expr_check, &safe_p);
3601       if (!safe_p)
3602         remove_structure (i);
3603       else
3604         i++;
3605     }
3606 }
3607
3608 /* We exclude from non-field accesses of the structure 
3609    all statements that will be treated as part of the structure 
3610    allocation sites or field accesses.  */
3611
3612 static void
3613 exclude_alloc_and_field_accs (struct cgraph_node *node)
3614 {
3615   d_str str;
3616   unsigned i;
3617
3618   for (i = 0; VEC_iterate (structure, structures, i, str); i++)
3619     exclude_alloc_and_field_accs_1 (str, node);
3620 }
3621
3622 /* This function collects accesses of the fields of the structures 
3623    that appear at function FN.  */
3624
3625 static void
3626 collect_accesses_in_func (struct function *fn)
3627 {
3628   basic_block bb;
3629
3630   if (! fn)
3631     return;
3632
3633   /* Collect accesses for each basic blocks separately.  */
3634   FOR_EACH_BB_FN (bb, fn)
3635     collect_accesses_in_bb (bb);
3636 }
3637
3638 /* This function summarizes counts of the fields into the structure count.  */
3639
3640 static void
3641 sum_counts (d_str str, gcov_type *hotest)
3642 {
3643   int i;
3644       
3645   str->count = 0;
3646   for (i = 0; i < str->num_fields; i++)
3647     {
3648       if (dump_file)
3649         {
3650           fprintf (dump_file, "\nCounter of field \"");
3651           print_generic_expr (dump_file, str->fields[i].decl, 0);
3652           fprintf (dump_file, "\" is " HOST_WIDEST_INT_PRINT_DEC, 
3653                    str->fields[i].count);
3654         }
3655       str->count += str->fields[i].count;
3656     }
3657
3658   if (dump_file)
3659     {
3660       fprintf (dump_file, "\nCounter of struct \"");
3661       print_generic_expr (dump_file, str->decl, 0);
3662       fprintf (dump_file, "\" is " HOST_WIDEST_INT_PRINT_DEC, str->count);
3663     }
3664
3665   if (str