OSDN Git Service

* ebitmap.h (ebitmap_iter_init): Initialize all fields.
[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
1869         {
1870           gcc_assert (TREE_CODE (type_orig) == ARRAY_TYPE);
1871           wr.wrap = 1;
1872           wr.domain = TYPE_DOMAIN (type_orig);
1873         }
1874       VEC_safe_push (type_wrapper_t, heap, wrapper, &wr);
1875       type_orig = TREE_TYPE (type_orig);
1876     }
1877
1878   while (VEC_length (type_wrapper_t, wrapper) != 0)
1879     {
1880       wr_p = VEC_last (type_wrapper_t, wrapper); 
1881
1882       if (wr_p->wrap) /* Array.  */
1883         new_type = build_array_type (new_type, wr_p->domain);
1884       else /* Pointer.  */
1885         new_type = build_pointer_type (new_type);
1886       
1887       VEC_pop (type_wrapper_t, wrapper);
1888     }
1889
1890   VEC_free (type_wrapper_t, heap, wrapper);  
1891   return new_type;
1892 }
1893
1894 /* This function generates and returns new variable name based on
1895    ORIG_DECL name, combined with index I.
1896    The form of the new name is <orig_name>.<I> .  */
1897
1898 static tree
1899 gen_var_name (tree orig_decl, unsigned HOST_WIDE_INT i)
1900 {
1901   const char *old_name;
1902   char *prefix;
1903   char *new_name;
1904
1905   if (!DECL_NAME (orig_decl)
1906       || !IDENTIFIER_POINTER (DECL_NAME (orig_decl)))
1907      return NULL;
1908
1909   /* If the original variable has a name, create an 
1910      appropriate new name for the new variable.  */
1911
1912   old_name = IDENTIFIER_POINTER (DECL_NAME (orig_decl));
1913   prefix = XALLOCAVEC (char, strlen (old_name) + 1);
1914   strcpy (prefix, old_name);
1915   ASM_FORMAT_PRIVATE_NAME (new_name, prefix, i);
1916   return get_identifier (new_name);
1917 }
1918
1919 /* This function adds NEW_NODE to hashtable of new_var's NEW_VARS_HTAB. */
1920
1921 static void
1922 add_to_new_vars_htab (new_var new_node, htab_t new_vars_htab)
1923 {
1924   void **slot;
1925
1926   slot = htab_find_slot_with_hash (new_vars_htab, new_node->orig_var,
1927                                    htab_hash_pointer (new_node->orig_var), 
1928                                    INSERT);
1929   *slot = new_node;
1930 }
1931
1932 /* This function creates and returns new_var_data node 
1933    with empty new_vars and orig_var equal to VAR.  */
1934
1935 static new_var
1936 create_new_var_node (tree var, d_str str)
1937 {
1938   new_var node;
1939
1940   node = (new_var) xmalloc (sizeof (struct new_var_data));
1941   node->orig_var = var;
1942   node->new_vars = VEC_alloc (tree, heap, VEC_length (tree, str->new_types));
1943   return node;
1944 }
1945
1946 /* Check whether the type of VAR is potential candidate for peeling.
1947    Returns true if yes, false otherwise.  If yes, TYPE_P will contain
1948    candidate type. If VAR is initialized, the type of VAR will be added
1949    to UNSUITABLE_TYPES.  */
1950
1951 static bool
1952 is_candidate (tree var, tree *type_p, VEC (tree, heap) **unsuitable_types)
1953 {
1954   tree type;
1955   bool initialized = false;
1956
1957   *type_p = NULL;
1958
1959   if (!var)
1960     return false;
1961
1962   /* There is no support of initialized vars.  */
1963   if (TREE_CODE (var) == VAR_DECL
1964       && DECL_INITIAL (var) != NULL_TREE)
1965     initialized = true;
1966   
1967   type = get_type_of_var (var);
1968
1969   if (type)
1970     {
1971       type = TYPE_MAIN_VARIANT (strip_type (type));
1972       if (TREE_CODE (type) != RECORD_TYPE)
1973           return false; 
1974       else
1975         {
1976           if (initialized && unsuitable_types && *unsuitable_types)
1977             {
1978               if (dump_file)
1979                 {
1980                   fprintf (dump_file, "The type ");
1981                   print_generic_expr (dump_file, type, 0);
1982                   fprintf (dump_file, " is initialized...Excluded.");             
1983                 }
1984               add_unsuitable_type (unsuitable_types, type);
1985             }
1986           *type_p = type;
1987           return true;
1988       }
1989     }
1990   else
1991     return false;
1992 }
1993
1994 /* Hash value for field_access_site.  */
1995
1996 static hashval_t
1997 field_acc_hash (const void *x)
1998 {
1999   return htab_hash_pointer (((const struct field_access_site *)x)->stmt);
2000 }
2001
2002 /* This function returns nonzero if stmt of field_access_site X 
2003    is equal to Y.  */
2004
2005 static int
2006 field_acc_eq (const void *x, const void *y)
2007 {
2008   return ((const struct field_access_site *)x)->stmt == (const_gimple)y;
2009 }
2010
2011 /* This function prints an access site, defined by SLOT.  */ 
2012
2013 static int
2014 dump_acc (void **slot, void *data ATTRIBUTE_UNUSED)
2015 {
2016   struct access_site *acc = *(struct access_site **) slot;
2017   tree var;
2018   unsigned i;
2019
2020   fprintf(dump_file, "\n");
2021   if (acc->stmt)
2022     print_gimple_stmt (dump_file, acc->stmt, 0, 0);
2023   fprintf(dump_file, " : ");
2024
2025   for (i = 0; VEC_iterate (tree, acc->vars, i, var); i++)
2026     {
2027       print_generic_expr (dump_file, var, 0);
2028       fprintf(dump_file, ", ");   
2029     }
2030   return 1;
2031 }
2032
2033 /* This function frees memory allocated for structure clusters,
2034    starting from CLUSTER.  */
2035
2036 static void
2037 free_struct_cluster (struct field_cluster* cluster)
2038 {
2039   if (cluster)
2040     {
2041       if (cluster->fields_in_cluster)
2042         sbitmap_free (cluster->fields_in_cluster);          
2043       if (cluster->sibling)
2044         free_struct_cluster (cluster->sibling);
2045       free (cluster);
2046     }
2047 }
2048
2049 /* Free all allocated memory under the structure node pointed by D_NODE.  */
2050
2051 static void
2052 free_data_struct (d_str d_node)
2053 {
2054   int i;
2055
2056   if (!d_node)
2057     return;
2058  
2059   if (dump_file)
2060     {
2061       fprintf (dump_file, "\nRemoving data structure \"");
2062       print_generic_expr (dump_file, d_node->decl, 0); 
2063       fprintf (dump_file, "\" from data_struct_list.");
2064     }
2065
2066   /* Free all space under d_node.  */
2067   if (d_node->fields)
2068     {
2069       for (i = 0; i < d_node->num_fields; i++)
2070         free_field_accesses (d_node->fields[i].acc_sites);
2071       free (d_node->fields);
2072     }
2073
2074   if (d_node->accs)
2075      free_accesses (d_node->accs);
2076
2077   if (d_node->struct_clustering)
2078     free_struct_cluster (d_node->struct_clustering);
2079
2080   if (d_node->new_types)
2081     VEC_free (tree, heap, d_node->new_types);
2082 }
2083
2084 /* This function creates new general and field accesses in BB.  */
2085
2086 static void
2087 create_new_accesses_in_bb (basic_block bb)
2088 {
2089   d_str str;
2090   unsigned i;
2091
2092   for (i = 0; VEC_iterate (structure, structures, i, str); i++)
2093     create_new_accs_for_struct (str, bb);
2094 }
2095
2096 /* This function adds allocation sites for peeled structures.
2097    M_DATA is vector of allocation sites of function CONTEXT.  */
2098
2099 static void
2100 create_new_alloc_sites (fallocs_t m_data, tree context)
2101 {
2102   alloc_site_t *call;
2103   unsigned j;
2104   
2105   for (j = 0; VEC_iterate (alloc_site_t, m_data->allocs, j, call); j++)
2106     {
2107       gimple stmt = call->stmt;
2108       d_str str = call->str;
2109       tree num;
2110       gimple_seq new_stmts = NULL;
2111       gimple last_stmt = get_final_alloc_stmt (stmt);
2112       unsigned i;
2113       tree type;
2114
2115       num = gen_num_of_structs_in_malloc (stmt, str->decl, &new_stmts);
2116       if (new_stmts)
2117         {
2118           gimple last_stmt_tmp = gimple_seq_last_stmt (new_stmts);
2119           insert_seq_after_stmt (last_stmt, new_stmts);
2120           last_stmt = last_stmt_tmp;
2121         }
2122       
2123       /* Generate an allocation sites for each new structure type.  */      
2124       for (i = 0; VEC_iterate (tree, str->new_types, i, type); i++)     
2125         {
2126           gimple new_malloc_stmt = NULL;
2127           gimple last_stmt_tmp = NULL;
2128
2129           new_stmts = NULL;
2130           new_malloc_stmt = create_new_malloc (stmt, type, &new_stmts, num);
2131           last_stmt_tmp = gimple_seq_last_stmt (new_stmts);
2132           insert_seq_after_stmt (last_stmt, new_stmts);
2133           update_cgraph_with_malloc_call (new_malloc_stmt, context);
2134           last_stmt = last_stmt_tmp;
2135         }
2136     }
2137 }
2138
2139 /* This function prints new variables from hashtable  
2140    NEW_VARS_HTAB to dump_file.  */
2141
2142 static void
2143 dump_new_vars (htab_t new_vars_htab)
2144 {
2145   if (!dump_file)
2146     return;
2147
2148   if (new_vars_htab)
2149     htab_traverse (new_vars_htab, dump_new_var, NULL);
2150 }
2151
2152 /* Given an original variable ORIG_DECL of structure type STR,
2153    this function generates new variables of the types defined 
2154    by STR->new_type. Generated types are saved in new_var node NODE.
2155    ORIG_DECL should has VAR_DECL tree_code.  */
2156
2157 static void
2158 create_new_var_1 (tree orig_decl, d_str str, new_var node)
2159 {
2160   unsigned i;
2161   tree type;
2162
2163   for (i = 0; 
2164        VEC_iterate (tree, str->new_types, i, type); i++)
2165     {
2166       tree new_decl = NULL;
2167       tree new_name;
2168
2169       new_name = gen_var_name (orig_decl, i);
2170       type = gen_struct_type (orig_decl, type); 
2171
2172       if (is_global_var (orig_decl))
2173         new_decl = build_decl (VAR_DECL, new_name, type); 
2174       else
2175         {
2176           const char *name = new_name ? IDENTIFIER_POINTER (new_name) : NULL;
2177           new_decl = create_tmp_var (type, name);                                  
2178         }
2179       
2180       copy_decl_attributes (new_decl, orig_decl);
2181       VEC_safe_push (tree, heap, node->new_vars, new_decl);
2182     }
2183 }
2184
2185 /* This function creates new variables to 
2186    substitute the original variable VAR_DECL and adds 
2187    them to the new_var's hashtable NEW_VARS_HTAB.  */
2188
2189 static void
2190 create_new_var (tree var_decl, htab_t new_vars_htab)
2191 {
2192   new_var node;
2193   d_str str;
2194   tree type;
2195   unsigned i;
2196
2197   if (!var_decl || is_in_new_vars_htab (var_decl, new_vars_htab))
2198     return;
2199
2200   if (!is_candidate (var_decl, &type, NULL))
2201     return;
2202   
2203   i = find_structure (type);
2204   if (i == VEC_length (structure, structures))
2205     return;
2206
2207   str = VEC_index (structure, structures, i);
2208   node = create_new_var_node (var_decl, str);
2209   create_new_var_1 (var_decl, str, node);
2210   add_to_new_vars_htab (node, new_vars_htab);
2211 }
2212
2213 /* Hash value for new_var.  */
2214
2215 static hashval_t
2216 new_var_hash (const void *x)
2217 {
2218   return htab_hash_pointer (((const_new_var)x)->orig_var);
2219 }
2220
2221 /* This function returns nonzero if orig_var of new_var X is equal to Y.  */
2222
2223 static int
2224 new_var_eq (const void *x, const void *y)
2225 {
2226   return ((const_new_var)x)->orig_var == (const_tree)y;
2227 }
2228
2229 /* This function check whether a structure type represented by STR 
2230    escapes due to ipa-type-escape analysis. If yes, this type is added 
2231    to UNSUITABLE_TYPES vector.  */ 
2232
2233 static void
2234 check_type_escape (d_str str, VEC (tree, heap) **unsuitable_types)
2235 {
2236   tree type = str->decl;
2237
2238   if (!ipa_type_escape_type_contained_p (type))
2239     {
2240       if (dump_file)
2241         {
2242           fprintf (dump_file, "\nEscaping type is ");
2243           print_generic_expr (dump_file, type, 0);
2244         }
2245       add_unsuitable_type (unsuitable_types, type);
2246     }
2247 }
2248
2249 /* Hash value for access_site.  */
2250
2251 static hashval_t
2252 acc_hash (const void *x)
2253 {
2254   return htab_hash_pointer (((const struct access_site *)x)->stmt);
2255 }
2256
2257 /* Return nonzero if stmt of access_site X is equal to Y.  */
2258
2259 static int
2260 acc_eq (const void *x, const void *y)
2261 {
2262   return ((const struct access_site *)x)->stmt == (const_gimple)y;
2263 }
2264
2265 /* Given a structure declaration STRUCT_DECL, and number of fields 
2266    in the structure NUM_FIELDS, this function creates and returns 
2267    corresponding field_entry's.  */
2268
2269 static struct field_entry *
2270 get_fields (tree struct_decl, int num_fields)
2271 {
2272   struct field_entry *list;
2273   tree t = TYPE_FIELDS (struct_decl);
2274   int idx = 0;
2275
2276   list = 
2277     (struct field_entry *) xmalloc (num_fields * sizeof (struct field_entry));
2278
2279   for (idx = 0 ; t; t = TREE_CHAIN (t), idx++)
2280     if (TREE_CODE (t) == FIELD_DECL)
2281       {
2282         list[idx].index = idx;
2283         list[idx].decl = t;
2284         list[idx].acc_sites = 
2285           htab_create (32, field_acc_hash, field_acc_eq, NULL);
2286         list[idx].count = 0;
2287         list[idx].field_mapping = NULL_TREE;
2288       }
2289
2290   return list;
2291 }
2292
2293 /* Print non-field accesses from hashtable ACCS of structure.  */
2294
2295 static void
2296 dump_access_sites (htab_t accs)
2297 {
2298   if (!dump_file)
2299     return;
2300
2301   if (accs)
2302     htab_traverse (accs, dump_acc, NULL);
2303 }
2304
2305 /* This function is a callback for alloc_sites hashtable 
2306    traversal. SLOT is a pointer to fallocs_t. This function
2307    removes all allocations of the structure defined by DATA.  */
2308
2309 static int
2310 remove_str_allocs_in_func (void **slot, void *data)
2311 {
2312   fallocs_t fallocs = *(fallocs_t *) slot;
2313   unsigned i = 0;
2314   alloc_site_t *call;
2315
2316   while (VEC_iterate (alloc_site_t, fallocs->allocs, i, call))
2317     {
2318       if (call->str == (d_str) data)
2319         VEC_ordered_remove (alloc_site_t, fallocs->allocs, i);
2320       else
2321         i++;
2322     }
2323
2324   return 1;
2325 }
2326
2327 /* This function remove all entries corresponding to the STR structure
2328    from alloc_sites hashtable.   */
2329
2330 static void
2331 remove_str_allocs (d_str str)
2332 {
2333   if (!str)
2334     return;
2335
2336   if (alloc_sites)
2337     htab_traverse (alloc_sites, remove_str_allocs_in_func, str);
2338 }
2339
2340 /* This function removes the structure with index I from structures vector.  */
2341
2342 static void 
2343 remove_structure (unsigned i)
2344 {    
2345   d_str str;
2346
2347   if (i >= VEC_length (structure, structures))
2348     return;
2349
2350   str = VEC_index (structure, structures, i);
2351   
2352   /* Before removing the structure str, we have to remove its
2353      allocations from alloc_sites hashtable.  */
2354   remove_str_allocs (str);
2355   free_data_struct (str);
2356   VEC_ordered_remove (structure, structures, i);
2357 }
2358
2359 /* Currently we support only EQ_EXPR or NE_EXPR conditions.
2360    COND_STMT is a condition statement to check.  */
2361
2362 static bool
2363 is_safe_cond_expr (gimple cond_stmt)
2364 {
2365   tree arg0, arg1;
2366   unsigned str0, str1;
2367   bool s0, s1;
2368   unsigned length = VEC_length (structure, structures);
2369
2370   if (gimple_cond_code (cond_stmt) != EQ_EXPR
2371       && gimple_cond_code (cond_stmt) != NE_EXPR)
2372     return false;
2373   
2374   arg0 = gimple_cond_lhs (cond_stmt);
2375   arg1 = gimple_cond_rhs (cond_stmt);
2376
2377   str0 = find_structure (strip_type (get_type_of_var (arg0)));
2378   str1 = find_structure (strip_type (get_type_of_var (arg1)));
2379
2380   s0 = (str0 != length) ? true : false;
2381   s1 = (str1 != length) ? true : false;
2382   
2383   if (!s0 && !s1)
2384     return false;
2385
2386   /* For now we allow only comparison with 0 or NULL.  */
2387   if (!integer_zerop (arg0) && !integer_zerop (arg1))
2388     return false;
2389
2390   return true;
2391 }
2392
2393 /* This function excludes statements, that are 
2394    part of allocation sites or field accesses, from the
2395    hashtable of general accesses. SLOT represents general 
2396    access that will be checked. DATA is a pointer to 
2397    exclude_data structure.  */
2398
2399 static int
2400 exclude_from_accs (void **slot, void *data)
2401 {
2402   struct access_site *acc = *(struct access_site **) slot;
2403   tree fn_decl = ((struct exclude_data *)data)->fn_decl;
2404   d_str str = ((struct exclude_data *)data)->str;
2405
2406   if (is_part_of_malloc (acc->stmt, fn_decl)
2407       || is_part_of_field_access (acc->stmt, str))
2408     {
2409       VEC_free (tree, heap, acc->vars);
2410       free (acc);
2411       htab_clear_slot (str->accs, slot);
2412     }
2413   return 1;
2414 }
2415
2416 /* Callback function for walk_tree called from collect_accesses_in_bb 
2417    function. DATA is the statement which is analyzed.  */
2418
2419 static tree
2420 get_stmt_accesses (tree *tp, int *walk_subtrees, void *data)
2421 {
2422   struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
2423   gimple stmt = (gimple) wi->info;
2424   tree t = *tp;
2425
2426   if (!t)
2427     return NULL;
2428
2429   switch (TREE_CODE (t))
2430     {
2431     case BIT_FIELD_REF:
2432       {
2433         tree var = TREE_OPERAND(t, 0);
2434         tree type = TYPE_MAIN_VARIANT (strip_type (get_type_of_var (var)));
2435         unsigned i = find_structure (type);
2436
2437         if (i != VEC_length (structure, structures))
2438           {
2439             if (dump_file)
2440               {
2441                 fprintf (dump_file, "\nThe type ");
2442                 print_generic_expr (dump_file, type, 0);
2443                 fprintf (dump_file, " has bitfield.");
2444               }     
2445             remove_structure (i);
2446           }
2447       }
2448       break;
2449
2450     case COMPONENT_REF:
2451       {
2452         tree ref = TREE_OPERAND (t, 0);
2453         tree field_decl = TREE_OPERAND (t, 1);
2454
2455
2456         if ((TREE_CODE (ref) == INDIRECT_REF
2457              || TREE_CODE (ref) == ARRAY_REF
2458              || TREE_CODE (ref) == VAR_DECL)
2459             && TREE_CODE (field_decl) == FIELD_DECL)
2460           {
2461             tree type = TYPE_MAIN_VARIANT (TREE_TYPE (ref));
2462             unsigned i = find_structure (type);
2463
2464             if (i != VEC_length (structure, structures))
2465               {
2466                 d_str str = VEC_index (structure, structures, i);
2467                 struct field_entry * field = 
2468                   find_field_in_struct (str, field_decl);
2469
2470                 if (field)
2471                   {
2472                     struct field_access_site *acc = make_field_acc_node ();
2473
2474                     gcc_assert (acc);
2475
2476                     acc->stmt = stmt;
2477                     acc->comp_ref = t;
2478                     acc->ref = ref;
2479                     acc->field_decl = field_decl;
2480
2481                     /* Check whether the access is of the form 
2482                        we can deal with.  */
2483                     if (!decompose_access (str->decl, acc))
2484                       {
2485                         if (dump_file)
2486                           {
2487                             fprintf (dump_file, "\nThe type ");
2488                             print_generic_expr (dump_file, type, 0);
2489                             fprintf (dump_file, 
2490                                      " has complicate access in statement ");
2491                             print_gimple_stmt (dump_file, stmt, 0, 0);
2492                           }
2493                         
2494                         remove_structure (i);
2495                         free (acc);
2496                       }
2497                     else
2498                       {
2499                         /* Increase count of field.  */
2500                         basic_block bb = gimple_bb (stmt);
2501                         field->count += bb->count;
2502
2503                         /* Add stmt to the acc_sites of field.  */
2504                         add_field_acc_to_acc_sites (acc, field->acc_sites);
2505                       }
2506                     *walk_subtrees = 0;
2507                   }
2508               }       
2509           }
2510       }
2511       break;
2512
2513     case COND_EXPR:
2514       {
2515         tree cond = COND_EXPR_COND (t);
2516         int i;
2517         for (i = 0; i < TREE_CODE_LENGTH (TREE_CODE (cond)); i++)
2518           {
2519             tree t = TREE_OPERAND (cond, i);
2520
2521             *walk_subtrees = 1;
2522             walk_tree (&t, get_stmt_accesses, data, NULL);
2523           }
2524         *walk_subtrees = 0;         
2525       }
2526       break;
2527
2528     case VAR_DECL:
2529     case SSA_NAME:
2530       {
2531         unsigned i;
2532
2533         if (TREE_CODE (t) == SSA_NAME)
2534           t = SSA_NAME_VAR (t);
2535
2536         i = find_structure (strip_type (get_type_of_var (t)));
2537         if (i != VEC_length (structure, structures))
2538           {
2539             d_str str;
2540
2541             str = VEC_index (structure, structures, i);
2542             add_access_to_acc_sites (stmt, t, str->accs);
2543           }
2544         *walk_subtrees = 0;
2545       }
2546       break;
2547
2548     default:
2549       return NULL;
2550     }
2551
2552   return NULL;
2553 }
2554
2555 /* Free structures hashtable.  */
2556
2557 static void
2558 free_structures (void)
2559 {
2560   d_str str;
2561   unsigned i;
2562
2563   for (i = 0; VEC_iterate (structure, structures, i, str); i++)
2564     free_data_struct (str);
2565
2566   VEC_free (structure, heap, structures);
2567   structures = NULL;
2568 }
2569
2570 /* This function is a callback for traversal over new_var's hashtable.
2571    SLOT is a pointer to new_var. This function frees memory allocated 
2572    for new_var and pointed by *SLOT.  */
2573
2574 static int
2575 free_new_var (void **slot, void *data ATTRIBUTE_UNUSED)
2576 {
2577   new_var n_var = *(new_var *) slot;
2578
2579   /* Free vector of new_vars.  */
2580   VEC_free (tree, heap, n_var->new_vars);
2581   free (n_var);
2582   return 1;
2583 }
2584
2585 /* Free new_vars hashtable NEW_VARS_HTAB.  */
2586
2587 static void
2588 free_new_vars_htab (htab_t new_vars_htab)
2589 {
2590   if (new_vars_htab)
2591     htab_traverse (new_vars_htab, free_new_var, NULL);  
2592   htab_delete (new_vars_htab);
2593   new_vars_htab = NULL;
2594 }
2595
2596 /* This function creates new general and field accesses that appear in cfun.  */
2597
2598 static void
2599 create_new_accesses_for_func (void)
2600 {
2601   basic_block bb;
2602
2603   FOR_EACH_BB_FN (bb, cfun)
2604     create_new_accesses_in_bb (bb);
2605 }
2606
2607 /* Create new allocation sites for the function represented by NODE.  */
2608
2609 static void
2610 create_new_alloc_sites_for_func (struct cgraph_node *node)
2611 {
2612   fallocs_t fallocs = get_fallocs (node->decl);
2613
2614   if (fallocs)
2615     create_new_alloc_sites (fallocs, node->decl);
2616 }
2617
2618 /* For each local variable of structure type from the vector of structures
2619    this function generates new variable(s) to replace it.  */
2620
2621 static void
2622 create_new_local_vars (void)
2623 {
2624   tree var;
2625   referenced_var_iterator rvi;
2626    
2627   new_local_vars = htab_create (num_referenced_vars, 
2628                                 new_var_hash, new_var_eq, NULL);
2629
2630   FOR_EACH_REFERENCED_VAR (var, rvi)
2631     {
2632       if (!is_global_var (var))
2633         create_new_var (var, new_local_vars);
2634     }
2635
2636   if (new_local_vars)
2637     htab_traverse (new_local_vars, finalize_new_vars_creation, NULL); 
2638   dump_new_vars (new_local_vars);
2639 }
2640
2641 /* This function prints the SHIFT number of spaces to the DUMP_FILE.  */
2642
2643 static inline void
2644 print_shift (unsigned HOST_WIDE_INT shift)
2645 {
2646   unsigned HOST_WIDE_INT sh = shift;
2647
2648   while (sh--)
2649     fprintf (dump_file, " ");    
2650 }
2651
2652 /* This function updates field_mapping of FIELDS in CLUSTER with NEW_TYPE.  */
2653
2654 static inline void
2655 update_fields_mapping (struct field_cluster *cluster, tree new_type,
2656                        struct field_entry * fields, int num_fields)
2657 {
2658   int i;
2659
2660   for (i = 0; i < num_fields; i++)
2661     if (TEST_BIT (cluster->fields_in_cluster, i))
2662         fields[i].field_mapping = new_type;  
2663 }
2664
2665 /* This functions builds structure with FIELDS, 
2666    NAME and attributes similar to ORIG_STRUCT. 
2667    It returns the newly created structure.  */
2668
2669 static tree
2670 build_basic_struct (tree fields, tree name, tree orig_struct)
2671 {
2672   tree attributes = NULL_TREE;
2673   tree ref = 0;
2674   tree x;
2675
2676   if (TYPE_ATTRIBUTES (orig_struct))
2677     attributes = unshare_expr (TYPE_ATTRIBUTES (orig_struct));
2678   ref = make_node (RECORD_TYPE);
2679   TYPE_SIZE (ref) = 0;
2680   decl_attributes (&ref, attributes, (int) ATTR_FLAG_TYPE_IN_PLACE); 
2681   TYPE_PACKED (ref) = TYPE_PACKED (orig_struct);
2682   for (x = fields; x; x = TREE_CHAIN (x))
2683     {
2684       DECL_CONTEXT (x) = ref;
2685       DECL_PACKED (x) |= TYPE_PACKED (ref);
2686     }
2687   TYPE_FIELDS (ref) = fields;
2688   layout_type (ref);
2689   TYPE_NAME (ref) = name;
2690
2691   return ref;
2692 }
2693
2694 /* This function copies FIELDS from CLUSTER into TREE_CHAIN as part 
2695    of preparation for new structure building. NUM_FIELDS is a total 
2696    number of fields in the structure. The function returns newly 
2697    generated fields.  */
2698
2699 static tree
2700 create_fields (struct field_cluster * cluster, 
2701                struct field_entry * fields, int num_fields)
2702 {
2703   int i;
2704   tree new_types = NULL_TREE;
2705   tree last = NULL_TREE;
2706
2707   for (i = 0; i < num_fields; i++)
2708     if (TEST_BIT (cluster->fields_in_cluster, i))
2709       {
2710         tree new_decl = unshare_expr (fields[i].decl);
2711
2712         if (!new_types)
2713           new_types = new_decl;
2714         else
2715           TREE_CHAIN (last) = new_decl;
2716         last = new_decl;
2717       }
2718
2719   TREE_CHAIN (last) = NULL_TREE;
2720   return new_types;
2721
2722 }
2723
2724 /* This function creates a cluster name. The name is based on 
2725    the original structure name, if it is present. It has a form:
2726    
2727    <original_struct_name>_sub.<CLUST_NUM>
2728
2729    The original structure name is taken from the type of DECL.
2730    If an original structure name is not present, it's generated to be:
2731
2732    struct.<STR_NUM>
2733
2734    The function returns identifier of the new cluster name.  */
2735
2736 static inline tree
2737 gen_cluster_name (tree decl, int clust_num, int str_num)
2738 {
2739   const char * orig_name = get_type_name (decl);
2740   char * tmp_name = NULL;
2741   char * prefix;
2742   char * new_name;
2743   size_t len;
2744   
2745   if (!orig_name)
2746     ASM_FORMAT_PRIVATE_NAME(tmp_name, "struct", str_num);
2747
2748   len = strlen (tmp_name ? tmp_name : orig_name) + strlen ("_sub");
2749   prefix = XALLOCAVEC (char, len + 1);
2750   memcpy (prefix, tmp_name ? tmp_name : orig_name, 
2751           strlen (tmp_name ? tmp_name : orig_name));
2752   strcpy (prefix + strlen (tmp_name ? tmp_name : orig_name), "_sub");      
2753   
2754   ASM_FORMAT_PRIVATE_NAME (new_name, prefix, clust_num);
2755   return get_identifier (new_name);
2756 }
2757
2758 /* This function checks whether the structure STR has bitfields.
2759    If yes, this structure type is added to UNSUITABLE_TYPES vector.  */
2760
2761 static void
2762 check_bitfields (d_str str, VEC (tree, heap) **unsuitable_types)
2763 {
2764   tree type = str->decl;
2765   int i;
2766
2767   for (i = 0; i < str->num_fields; i++)
2768     if (DECL_BIT_FIELD (str->fields[i].decl))
2769       {
2770         add_unsuitable_type (unsuitable_types, type);
2771         if (dump_file)
2772         {
2773           fprintf (dump_file, "\nType ");
2774           print_generic_expr (dump_file, type, 0);
2775           fprintf (dump_file, "\nescapes due to bitfield ");
2776           print_generic_expr (dump_file, str->fields[i].decl, 0);
2777         }
2778         break;
2779       }
2780 }
2781
2782 /* This function adds to UNSUITABLE_TYPES those types that escape 
2783    due to results of ipa-type-escape analysis. See ipa-type-escape.[c,h].  */
2784
2785 static void
2786 exclude_escaping_types_1 (VEC (tree, heap) **unsuitable_types)
2787 {
2788   d_str str;
2789   unsigned i;
2790
2791   for (i = 0; VEC_iterate (structure, structures, i, str); i++)
2792     check_type_escape (str, unsuitable_types);
2793 }
2794
2795 /* If a structure type is a return type of any function,
2796    we cannot transform it. Such type is added to UNSUITABLE_TYPES vector.  */
2797
2798 static void
2799 exclude_returned_types (VEC (tree, heap) **unsuitable_types)
2800 {
2801   struct cgraph_node *c_node;
2802
2803   for (c_node = cgraph_nodes; c_node; c_node = c_node->next)
2804     {
2805       tree ret_t = TREE_TYPE (TREE_TYPE (c_node->decl));
2806
2807       if (ret_t)
2808         {
2809           ret_t = strip_type (ret_t);
2810           if (TREE_CODE (ret_t) == RECORD_TYPE)
2811             {
2812               add_unsuitable_type (unsuitable_types, TYPE_MAIN_VARIANT (ret_t));
2813               if (dump_file)
2814                 {
2815                   fprintf (dump_file, "\nThe type \"");
2816                   print_generic_expr (dump_file, ret_t, 0);
2817                   fprintf (dump_file,
2818                            "\" is return type of function...Excluded.");
2819                 }
2820             }
2821         }
2822     }
2823 }
2824
2825 /* This function looks for parameters of local functions 
2826    which are of structure types, or derived from them (arrays 
2827    of structures, pointers to structures, or their combinations).
2828    We are not handling peeling of such structures right now.
2829    The found structures types are added to UNSUITABLE_TYPES vector.  */
2830
2831 static void
2832 exclude_types_passed_to_local_func (VEC (tree, heap) **unsuitable_types)
2833 {
2834   struct cgraph_node *c_node;
2835
2836   for (c_node = cgraph_nodes; c_node; c_node = c_node->next)
2837     if (cgraph_function_body_availability (c_node) == AVAIL_LOCAL)
2838       {
2839         tree fn = c_node->decl;
2840         tree arg;
2841         
2842         for (arg = DECL_ARGUMENTS (fn); arg; arg = TREE_CHAIN (arg))
2843           {
2844             tree type = TREE_TYPE (arg);
2845
2846             type = strip_type (type);
2847             if (TREE_CODE (type) == RECORD_TYPE)
2848               {
2849                 add_unsuitable_type (unsuitable_types, 
2850                                      TYPE_MAIN_VARIANT (type));
2851                 if (dump_file)
2852                   {
2853                     fprintf (dump_file, "\nPointer to type \"");
2854                     print_generic_expr (dump_file, type, 0);
2855                     fprintf (dump_file, 
2856                              "\" is passed to local function...Excluded.");                              
2857                   }
2858               }
2859           }
2860       }
2861 }
2862
2863 /* This function analyzes structure form of structures 
2864    potential for transformation. If we are not capable to transform
2865    structure of some form, we remove it from the structures hashtable.
2866    Right now we cannot handle nested structs, when nesting is 
2867    through any level of pointers or arrays.  
2868
2869    TBD: release these constrains in future.
2870
2871    Note, that in this function we suppose that all structures 
2872    in the program are members of the structures hashtable right now, 
2873    without excluding escaping types.  */
2874
2875 static void
2876 check_struct_form (d_str str, VEC (tree, heap) **unsuitable_types)
2877 {
2878   int i;
2879
2880   for (i = 0; i < str->num_fields; i++)
2881     {
2882       tree f_type = strip_type(TREE_TYPE (str->fields[i].decl));
2883           
2884       if (TREE_CODE (f_type) == RECORD_TYPE)
2885         {
2886           add_unsuitable_type (unsuitable_types, TYPE_MAIN_VARIANT (f_type));
2887           add_unsuitable_type (unsuitable_types, str->decl);
2888           if (dump_file)
2889             {
2890               fprintf (dump_file, "\nType ");
2891               print_generic_expr (dump_file, f_type, 0);
2892               fprintf (dump_file, " is a field in the structure ");
2893               print_generic_expr (dump_file, str->decl, 0);
2894               fprintf (dump_file, ". Escaping...");
2895             }
2896         }
2897     }
2898 }
2899
2900 /* This function adds a structure TYPE to the vector of structures,
2901    if it's not already there.  */
2902
2903 static void
2904 add_structure (tree type)
2905 {
2906   struct data_structure node;
2907   unsigned i;
2908   int num_fields;
2909
2910   type = TYPE_MAIN_VARIANT (type);
2911
2912   i = find_structure (type);
2913
2914   if (i != VEC_length (structure, structures))
2915     return;
2916
2917   num_fields = fields_length (type);
2918   node.decl = type;
2919   node.num_fields = num_fields;
2920   node.fields = get_fields (type, num_fields);
2921   node.struct_clustering = NULL;
2922   node.accs = htab_create (32, acc_hash, acc_eq, NULL);
2923   node.new_types = VEC_alloc (tree, heap, num_fields);
2924   node.count = 0;
2925
2926   VEC_safe_push (structure, heap, structures, &node);
2927
2928   if (dump_file)
2929     {
2930       fprintf (dump_file, "\nAdding data structure \"");
2931       print_generic_expr (dump_file, type, 0); 
2932       fprintf (dump_file, "\" to data_struct_list.");
2933     }
2934 }
2935
2936 /* This function adds an allocation site to alloc_sites hashtable.
2937    The allocation site appears in STMT of function FN_DECL and 
2938    allocates the structure represented by STR.  */
2939
2940 static void
2941 add_alloc_site (tree fn_decl, gimple stmt, d_str str)
2942 {
2943   fallocs_t fallocs = NULL;
2944   alloc_site_t m_call;
2945
2946   m_call.stmt = stmt;
2947   m_call.str = str;
2948
2949   fallocs = 
2950     (fallocs_t) htab_find_with_hash (alloc_sites,
2951                                      fn_decl, htab_hash_pointer (fn_decl));
2952
2953   if (!fallocs)
2954     {
2955       void **slot;
2956
2957       fallocs = (fallocs_t) 
2958         xmalloc (sizeof (struct func_alloc_sites));
2959       fallocs->func = fn_decl;
2960       fallocs->allocs = VEC_alloc (alloc_site_t, heap, 1);
2961       slot = htab_find_slot_with_hash (alloc_sites, fn_decl,
2962                                       htab_hash_pointer (fn_decl), INSERT);
2963       *slot = fallocs;
2964     }
2965   VEC_safe_push (alloc_site_t, heap, 
2966                  fallocs->allocs, &m_call);
2967   
2968   if (dump_file)
2969     {
2970       fprintf (dump_file, "\nAdding stmt ");
2971       print_gimple_stmt (dump_file, stmt, 0, 0);
2972       fprintf (dump_file, " to list of mallocs.");
2973     }
2974 }
2975
2976 /* This function returns true if the result of STMT, that contains a call
2977    to an allocation function, is cast to one of the structure types.
2978    STMT should be of the form:    T.2 = <alloc_func> (T.1);
2979    If true, I_P contains an index of an allocated structure. 
2980    Otherwise I_P contains the length of the vector of structures.  */
2981
2982 static bool
2983 is_alloc_of_struct (gimple stmt, unsigned *i_p)
2984 {
2985   tree lhs;
2986   tree type;
2987   gimple final_stmt;
2988
2989   final_stmt = get_final_alloc_stmt (stmt);
2990
2991   if (!final_stmt)
2992     return false;
2993
2994   /* final_stmt should be of the form:
2995      T.3 = (struct_type *) T.2; */
2996
2997   if (gimple_code (final_stmt) != GIMPLE_ASSIGN)
2998     return false;
2999
3000   lhs = gimple_assign_lhs (final_stmt);
3001
3002   type = get_type_of_var (lhs);
3003       
3004   if (!type)
3005     return false;
3006
3007   if (!POINTER_TYPE_P (type)
3008       || TREE_CODE (strip_type (type)) != RECORD_TYPE)
3009     return false;
3010
3011   *i_p = find_structure (strip_type (type));
3012
3013   if (*i_p == VEC_length (structure, structures))
3014     return false;
3015
3016   return true;
3017 }
3018
3019 /* This function prints non-field and field accesses 
3020    of the structure STR.  */ 
3021
3022 static void
3023 dump_accs (d_str str)
3024 {
3025   int i;
3026
3027   fprintf (dump_file, "\nAccess sites of struct ");
3028   print_generic_expr (dump_file, str->decl, 0);
3029
3030   for (i = 0; i < str->num_fields; i++)
3031     {
3032       fprintf (dump_file, "\nAccess site of field ");
3033       print_generic_expr (dump_file, str->fields[i].decl, 0);
3034       dump_field_acc_sites (str->fields[i].acc_sites);   
3035       fprintf (dump_file, ":\n");
3036     }
3037   fprintf (dump_file, "\nGeneral access sites\n");
3038   dump_access_sites (str->accs);   
3039 }
3040
3041 /* This function checks whether an access statement, pointed by SLOT,
3042    is a condition we are capable to transform.  It returns false if not,
3043    setting bool *DATA to false.  */
3044  
3045 static int
3046 safe_cond_expr_check (void **slot, void *data)
3047 {
3048   struct access_site *acc = *(struct access_site **) slot;
3049
3050   if (gimple_code (acc->stmt) == GIMPLE_COND
3051       && !is_safe_cond_expr (acc->stmt))
3052     {
3053       if (dump_file)
3054         {
3055           fprintf (dump_file, "\nUnsafe conditional statement ");
3056           print_gimple_stmt (dump_file, acc->stmt, 0, 0);
3057         }
3058       *(bool *) data = false;
3059       return 0;
3060     }
3061   return 1;
3062 }
3063
3064 /* This function excludes statements that are part of allocation sites and
3065    field accesses from the hashtable of general accesses of the structure
3066    type STR. Only accesses that belong to the function represented by
3067    NODE are treated.  */
3068
3069 static void
3070 exclude_alloc_and_field_accs_1 (d_str str, struct cgraph_node *node)
3071 {
3072   struct exclude_data dt;
3073   dt.str = str;
3074   dt.fn_decl = node->decl;
3075
3076   if (dt.str->accs)
3077     htab_traverse (dt.str->accs, exclude_from_accs, &dt);  
3078 }
3079
3080 /* Collect accesses to the structure types that appear in basic block BB.  */
3081
3082 static void
3083 collect_accesses_in_bb (basic_block bb)
3084 {
3085   gimple_stmt_iterator bsi;
3086   struct walk_stmt_info wi;
3087
3088   memset (&wi, 0, sizeof (wi));
3089
3090   for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
3091     {
3092       gimple stmt = gsi_stmt (bsi);
3093
3094       /* In asm stmt we cannot always track the arguments,
3095          so we just give up.  */
3096       if (gimple_code (stmt) == GIMPLE_ASM)
3097         {
3098           free_structures ();
3099           break;
3100         }
3101
3102       wi.info = (void *) stmt;
3103       walk_gimple_op (stmt, get_stmt_accesses, &wi);
3104     }
3105 }
3106
3107 /* This function generates cluster substructure that contains FIELDS.
3108    The cluster added to the set of clusters of the structure STR.  */
3109
3110 static void
3111 gen_cluster (sbitmap fields, d_str str)
3112 {
3113   struct field_cluster *crr_cluster = NULL;
3114
3115   crr_cluster = 
3116     (struct field_cluster *) xcalloc (1, sizeof (struct field_cluster));
3117   crr_cluster->sibling = str->struct_clustering;
3118   str->struct_clustering = crr_cluster;
3119   crr_cluster->fields_in_cluster = fields;
3120 }
3121
3122 /* This function peels a field with the index I from the structure DS.  */
3123
3124 static void
3125 peel_field (int i, d_str ds)
3126 {
3127   struct field_cluster *crr_cluster = NULL;
3128
3129   crr_cluster = 
3130     (struct field_cluster *) xcalloc (1, sizeof (struct field_cluster));
3131   crr_cluster->sibling = ds->struct_clustering;
3132   ds->struct_clustering = crr_cluster;
3133   crr_cluster->fields_in_cluster =
3134     sbitmap_alloc ((unsigned int) ds->num_fields);
3135   sbitmap_zero (crr_cluster->fields_in_cluster);
3136   SET_BIT (crr_cluster->fields_in_cluster, i);  
3137 }
3138
3139 /* This function calculates maximum field count in 
3140    the structure STR.  */
3141
3142 static gcov_type
3143 get_max_field_count (d_str str)
3144 {
3145   gcov_type max = 0;
3146   int i;
3147
3148   for (i = 0; i < str->num_fields; i++)
3149     if (str->fields[i].count > max)
3150       max = str->fields[i].count; 
3151
3152   return max;
3153 }
3154
3155 /* Do struct-reorg transformation for individual function 
3156    represented by NODE. All structure types relevant 
3157    for this function are transformed.  */
3158
3159 static void
3160 do_reorg_for_func (struct cgraph_node *node)
3161 {
3162   create_new_local_vars ();  
3163   create_new_alloc_sites_for_func (node);
3164   create_new_accesses_for_func ();
3165   update_ssa (TODO_update_ssa);
3166   cleanup_tree_cfg ();
3167
3168   /* Free auxiliary data representing local variables.  */
3169   free_new_vars_htab (new_local_vars); 
3170 }
3171
3172 /* Print structure TYPE, its name, if it exists, and body.
3173    INDENT defines the level of indentation (similar 
3174    to the option -i of indent command). SHIFT parameter 
3175    defines a number of spaces by which a structure will 
3176    be shifted right.  */
3177
3178 static void
3179 dump_struct_type (tree type, unsigned HOST_WIDE_INT indent,
3180                    unsigned HOST_WIDE_INT shift)
3181 {
3182   const char *struct_name;
3183   tree field;
3184
3185   if (!type || !dump_file)
3186     return;
3187
3188   if (TREE_CODE (type) != RECORD_TYPE)
3189     {
3190       print_generic_expr (dump_file, type, 0);
3191       return;
3192     }
3193   
3194   print_shift (shift);
3195   struct_name = get_type_name (type);  
3196   fprintf (dump_file, "struct ");
3197   if (struct_name)    
3198     fprintf (dump_file, "%s\n",struct_name);
3199   print_shift (shift);
3200   fprintf (dump_file, "{\n");
3201        
3202   for (field = TYPE_FIELDS (type); field; 
3203        field = TREE_CHAIN (field))
3204     {
3205       unsigned HOST_WIDE_INT s = indent;
3206       tree f_type = TREE_TYPE (field);
3207       
3208       print_shift (shift);
3209       while (s--)
3210         fprintf (dump_file, " ");
3211       dump_struct_type (f_type, indent, shift + indent);
3212       fprintf(dump_file, " ");
3213       print_generic_expr (dump_file, field, 0);
3214       fprintf(dump_file, ";\n");
3215     }
3216   print_shift (shift);
3217   fprintf (dump_file, "}\n");
3218 }
3219
3220 /* This function creates new structure types to replace original type, 
3221    indicated by STR->decl. The names of the new structure types are 
3222    derived from the original structure type. If the original structure 
3223    type has no name, we assume that its name is 'struct.<STR_NUM>'.  */
3224
3225 static void
3226 create_new_type (d_str str, int *str_num)
3227 {
3228   int cluster_num = 0;
3229
3230   struct field_cluster *cluster = str->struct_clustering;
3231   while (cluster)
3232     {     
3233       tree  name = gen_cluster_name (str->decl, cluster_num, 
3234                                      *str_num);
3235       tree fields;
3236       tree new_type;
3237       cluster_num++;
3238            
3239       fields = create_fields (cluster, str->fields, 
3240                               str->num_fields);
3241       new_type = build_basic_struct (fields, name, str->decl);
3242           
3243       update_fields_mapping (cluster, new_type, 
3244                              str->fields, str->num_fields);
3245
3246       VEC_safe_push (tree, heap, str->new_types, new_type);
3247       cluster = cluster->sibling; 
3248     }
3249   (*str_num)++;
3250 }
3251
3252 /* This function is a callback for alloc_sites hashtable 
3253    traversal. SLOT is a pointer to fallocs_t. 
3254    This function frees memory pointed by *SLOT.  */
3255
3256 static int
3257 free_falloc_sites (void **slot, void *data ATTRIBUTE_UNUSED)
3258 {
3259   fallocs_t fallocs = *(fallocs_t *) slot;
3260
3261   VEC_free (alloc_site_t, heap, fallocs->allocs);
3262   free (fallocs);
3263   return 1;
3264 }
3265
3266 /* Remove structures collected in UNSUITABLE_TYPES
3267    from structures vector.  */
3268
3269 static void
3270 remove_unsuitable_types (VEC (tree, heap) *unsuitable_types)
3271 {
3272   d_str str;
3273   tree type;
3274   unsigned i, j;
3275
3276   for (j = 0; VEC_iterate (tree, unsuitable_types, j, type); j++)
3277     for (i = 0; VEC_iterate (structure, structures, i, str); i++)
3278       if (is_equal_types (str->decl, type))
3279         {
3280           remove_structure (i);
3281           break;
3282         }
3283 }
3284
3285 /* Exclude structure types with bitfields.
3286    We would not want to interfere with other optimizations 
3287    that can be done in this case. The structure types with 
3288    bitfields are added to UNSUITABLE_TYPES vector.  */
3289
3290 static void
3291 exclude_types_with_bit_fields (VEC (tree, heap) **unsuitable_types)
3292 {
3293   d_str str;
3294   unsigned i;
3295
3296   for (i = 0; VEC_iterate (structure, structures, i, str); i++)
3297     check_bitfields (str, unsuitable_types);
3298 }
3299
3300 /* This function checks three types of escape. A structure type escapes:
3301
3302    1. if it's a type of parameter of a local function.
3303    2. if it's a type of function return value.
3304    3. if it escapes as a result of ipa-type-escape analysis.  
3305
3306   The escaping structure types are added to UNSUITABLE_TYPES vector.  */
3307
3308 static void
3309 exclude_escaping_types (VEC (tree, heap) **unsuitable_types)
3310 {
3311   exclude_types_passed_to_local_func (unsuitable_types);
3312   exclude_returned_types (unsuitable_types);
3313   exclude_escaping_types_1 (unsuitable_types);
3314 }
3315
3316 /* This function analyzes whether the form of 
3317    structure is such that we are capable to transform it. 
3318    Nested structures are checked here. Unsuitable structure
3319    types are added to UNSUITABLE_TYPE vector.  */
3320
3321 static void
3322 analyze_struct_form (VEC (tree, heap) **unsuitable_types)
3323 {
3324   d_str str;
3325   unsigned i;
3326
3327   for (i = 0; VEC_iterate (structure, structures, i, str); i++)
3328     check_struct_form (str, unsuitable_types);
3329 }
3330
3331 /* This function looks for structure types instantiated in the program. 
3332    The candidate types are added to the structures vector. 
3333    Unsuitable types are collected into UNSUITABLE_TYPES vector.  */
3334
3335 static void
3336 build_data_structure (VEC (tree, heap) **unsuitable_types)
3337 {
3338   tree var, type;
3339   tree var_list;
3340   struct varpool_node *current_varpool;
3341   struct cgraph_node *c_node;
3342
3343   /* Check global variables.  */ 
3344   FOR_EACH_STATIC_VARIABLE (current_varpool)
3345     {
3346       var = current_varpool->decl;
3347       if (is_candidate (var, &type, unsuitable_types))
3348         add_structure (type);
3349     }
3350
3351   /* Now add structures that are types of function parameters and 
3352      local variables.  */
3353   for (c_node = cgraph_nodes; c_node; c_node = c_node->next)
3354     {
3355       enum availability avail = 
3356         cgraph_function_body_availability (c_node);
3357
3358       /* We need AVAIL_AVAILABLE for main function.  */
3359       if (avail == AVAIL_LOCAL || avail == AVAIL_AVAILABLE)
3360         {
3361           struct function *fn = DECL_STRUCT_FUNCTION (c_node->decl);
3362
3363           for (var = DECL_ARGUMENTS (c_node->decl); var; 
3364                var = TREE_CHAIN (var))
3365               if (is_candidate (var, &type, unsuitable_types))
3366                 add_structure (type);
3367
3368           /* Check function local variables.  */
3369           for (var_list = fn->local_decls; var_list; 
3370                var_list = TREE_CHAIN (var_list))
3371             {
3372               var = TREE_VALUE (var_list);
3373
3374               if (is_candidate (var, &type, unsuitable_types))
3375                 add_structure (type);
3376             }
3377         }
3378     }
3379 }
3380
3381 /* This function returns true if the program contains 
3382    a call to user defined allocation function, or other
3383    functions that can interfere with struct-reorg optimizations.  */
3384
3385 static bool
3386 program_redefines_malloc_p (void)
3387 {
3388   struct cgraph_node *c_node;
3389   struct cgraph_node *c_node2;
3390   struct cgraph_edge *c_edge;
3391   tree fndecl;
3392   tree fndecl2;
3393   
3394   for (c_node = cgraph_nodes; c_node; c_node = c_node->next)
3395     {
3396       fndecl = c_node->decl;
3397
3398       for (c_edge = c_node->callees; c_edge; c_edge = c_edge->next_callee)
3399         {
3400           c_node2 = c_edge->callee;
3401           fndecl2 = c_node2->decl;
3402           if (is_gimple_call (c_edge->call_stmt))
3403             {
3404               const char * fname = get_name (fndecl2);
3405
3406               if ((gimple_call_flags (c_edge->call_stmt) & ECF_MALLOC)
3407                   && (DECL_FUNCTION_CODE (fndecl2) != BUILT_IN_MALLOC)
3408                   && (DECL_FUNCTION_CODE (fndecl2) != BUILT_IN_CALLOC)
3409                   && (DECL_FUNCTION_CODE (fndecl2) != BUILT_IN_ALLOCA))
3410                 return true;
3411
3412               /* Check that there is no __builtin_object_size,
3413                __builtin_offsetof, or realloc's in the program.  */
3414               if (DECL_FUNCTION_CODE (fndecl2) == BUILT_IN_OBJECT_SIZE
3415                   || !strcmp (fname, "__builtin_offsetof")
3416                   || !strcmp (fname, "realloc"))
3417                 return true;            
3418             }
3419         }
3420     }
3421   
3422   return false;
3423 }
3424
3425 /* In this function we assume that an allocation statement 
3426
3427    var = (type_cast) malloc (size);
3428    
3429    is converted into the following set of statements:
3430
3431    T.1 = size;
3432    T.2 = malloc (T.1);
3433    T.3 = (type_cast) T.2;
3434    var = T.3;
3435
3436    In this function we collect into alloc_sites the allocation 
3437    sites of variables of structure types that are present 
3438    in structures vector.  */
3439
3440 static void
3441 collect_alloc_sites (void)
3442 {
3443   struct cgraph_node *node;
3444   struct cgraph_edge *cs;
3445
3446   for (node = cgraph_nodes; node; node = node->next)
3447     if (node->analyzed && node->decl)
3448       {
3449         for (cs = node->callees; cs; cs = cs->next_callee)
3450           {
3451             gimple stmt = cs->call_stmt;
3452
3453             if (stmt)
3454               {
3455                 tree decl;
3456
3457                 if (is_gimple_call (stmt)
3458                     && (decl = gimple_call_fndecl (stmt)) 
3459                     && gimple_call_lhs (stmt))
3460                   {
3461                     unsigned i;
3462
3463                     if (is_alloc_of_struct (stmt, &i))
3464                       {
3465                         /* We support only malloc now.  */
3466                         if (DECL_FUNCTION_CODE (decl) == BUILT_IN_MALLOC)
3467                           {
3468                             d_str str;
3469                             
3470                             str = VEC_index (structure, structures, i);
3471                             add_alloc_site (node->decl, stmt, str);
3472                           }
3473                         else
3474                           {
3475                             if (dump_file)
3476                               {
3477                                 fprintf (dump_file, 
3478                                          "\nUnsupported allocation function ");
3479                                 print_gimple_stmt (dump_file, stmt, 0, 0);
3480                               }
3481                             remove_structure (i);               
3482                           }
3483                       }
3484                   }
3485               }       
3486           }
3487       }
3488 }
3489
3490 /* Print collected accesses.  */
3491
3492 static void
3493 dump_accesses (void)
3494 {
3495   d_str str;
3496   unsigned i;
3497
3498   if (!dump_file)
3499     return;
3500
3501   for (i = 0; VEC_iterate (structure, structures, i, str); i++)
3502     dump_accs (str);
3503 }
3504
3505 /* This function checks whether the accesses of structures in condition 
3506    expressions are of the kind we are capable to transform. 
3507    If not, such structures are removed from the vector of structures.  */
3508
3509 static void
3510 check_cond_exprs (void)
3511 {
3512   d_str str;
3513   unsigned i;
3514
3515   i = 0;
3516   while (VEC_iterate (structure, structures, i, str))
3517     {
3518       bool safe_p = true;
3519
3520       if (str->accs)
3521         htab_traverse (str->accs, safe_cond_expr_check, &safe_p);
3522       if (!safe_p)
3523         remove_structure (i);
3524       else
3525         i++;
3526     }
3527 }
3528
3529 /* We exclude from non-field accesses of the structure 
3530    all statements that will be treated as part of the structure 
3531    allocation sites or field accesses.  */
3532
3533 static void
3534 exclude_alloc_and_field_accs (struct cgraph_node *node)
3535 {
3536   d_str str;
3537   unsigned i;
3538
3539   for (i = 0; VEC_iterate (structure, structures, i, str); i++)
3540     exclude_alloc_and_field_accs_1 (str, node);
3541 }
3542
3543 /* This function collects accesses of the fields of the structures 
3544    that appear at function FN.  */
3545
3546 static void
3547 collect_accesses_in_func (struct function *fn)
3548 {
3549   basic_block bb;
3550
3551   if (! fn)
3552     return;
3553
3554   /* Collect accesses for each basic blocks separately.  */
3555   FOR_EACH_BB_FN (bb, fn)
3556     collect_accesses_in_bb (bb);
3557 }
3558
3559 /* This function summarizes counts of the fields into the structure count.  */
3560
3561 static void
3562 sum_counts (d_str str, gcov_type *hottest)
3563 {
3564   int i;
3565       
3566   str->count = 0;
3567   for (i = 0; i < str->num_fields; i++)
3568     {
3569       if (dump_file)
3570         {
3571           fprintf (dump_file, "\nCounter of field \"");
3572           print_generic_expr (dump_file, str->fields[i].decl, 0);
3573           fprintf (dump_file, "\" is " HOST_WIDEST_INT_PRINT_DEC, 
3574                    str->fields[i].count);
3575         }
3576       str->count += str->fields[i].count;
3577     }
3578
3579   if (dump_file)
3580     {
3581       fprintf (dump_file, "\nCounter of struct \"");
3582       print_generic_expr (dump_file, str->decl, 0);
3583       fprintf (dump_file, "\" is " HOST_WIDEST_INT_PRINT_DEC, str->count);
3584     }
3585
3586   if (str->count > *hottest)
3587     *hottest = str->count;
3588 }
3589
3590 /* This function peels the field into separate structure if it's
3591    sufficiently hot, i.e. if its count provides at least 90% of 
3592    the maximum field count in the structure.  */
3593
3594 static void
3595 peel_hot_fields (d_str str)
3596 {
3597   gcov_type max_field_count;
3598   sbitmap fields_left = sbitmap_alloc (str->num_fields);
3599   int i;
3600
3601   sbitmap_ones (fields_left);
3602   max_field_count = 
3603     (gcov_type) (get_max_field_count (str)/100)*90;
3604
3605   str->struct_clustering = NULL;
3606
3607   for (i = 0; i < str->num_fields; i++)
3608     {
3609       if (str->count >= max_field_count)
3610         {
3611           RESET_BIT (fields_left, i);     
3612           peel_field (i, str);
3613         }
3614     }
3615
3616   i = sbitmap_first_set_bit (fields_left);
3617   if (i != -1)
3618     gen_cluster (fields_left, str);
3619   else
3620     sbitmap_free (fields_left);
3621
3622
3623 /* This function is a helper for do_reorg. It goes over 
3624    functions in call graph and performs actual transformation 
3625    on them.  */
3626
3627 static void
3628 do_reorg_1 (void)
3629 {
3630   struct cgraph_node *node;
3631
3632   /* Initialize the default bitmap obstack.  */
3633   bitmap_obstack_initialize (NULL);
3634
3635   for (node = cgraph_nodes; node; node = node->next)
3636     if (node->analyzed && node->decl && !node->next_clone)
3637       {
3638         push_cfun (DECL_STRUCT_FUNCTION (node->decl));
3639         current_function_decl = node->decl;
3640         if (dump_file)
3641           fprintf (dump_file, "\nFunction to do reorg is  %s: \n",
3642                    (const char *) IDENTIFIER_POINTER (DECL_NAME (node->decl)));
3643         do_reorg_for_func (node);
3644         free_dominance_info (CDI_DOMINATORS);
3645         free_dominance_info (CDI_POST_DOMINATORS);
3646         current_function_decl = NULL;
3647         pop_cfun ();
3648       }
3649
3650   set_cfun (NULL);
3651   bitmap_obstack_release (NULL);
3652 }
3653
3654 /* This function creates new global struct variables.
3655    For each original variable, the set of new variables 
3656    is created with the new structure types corresponding 
3657    to the structure type of original variable. 
3658    Only VAR_DECL variables are treated by this function.  */
3659
3660 static void 
3661 create_new_global_vars (void)
3662 {
3663   struct varpool_node *current_varpool;
3664   unsigned HOST_WIDE_INT i;
3665   unsigned HOST_WIDE_INT varpool_size = 0;
3666
3667   for (i = 0; i < 2; i++)
3668     {
3669       if (i)
3670         new_global_vars = htab_create (varpool_size, 
3671                                        new_var_hash, new_var_eq, NULL);
3672       FOR_EACH_STATIC_VARIABLE(current_varpool)
3673         {
3674           tree  var_decl = current_varpool->decl;
3675
3676           if (!var_decl || TREE_CODE (var_decl) != VAR_DECL)