OSDN Git Service

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