OSDN Git Service

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