OSDN Git Service

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