OpenCores
URL https://opencores.org/ocsvn/openrisc_me/openrisc_me/trunk

Subversion Repositories openrisc_me

[/] [openrisc/] [trunk/] [gnu-src/] [gcc-4.5.1/] [gcc/] [ipa-struct-reorg.c] - Blame information for rev 281

Go to most recent revision | Details | Compare with Previous | View Log

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

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.