OSDN Git Service

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