OSDN Git Service

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