OSDN Git Service

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