OSDN Git Service

e2091e5fda49cec2ea82c3c95e22dbddcd543c16
[pf3gnuchains/gcc-fork.git] / gcc / tree-sra.c
1 /* Scalar Replacement of Aggregates (SRA) converts some structure
2    references into scalar references, exposing them to the scalar
3    optimizers.
4    Copyright (C) 2008, 2009, 2010, 2011 Free Software Foundation, Inc.
5    Contributed by Martin Jambor <mjambor@suse.cz>
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 /* This file implements Scalar Reduction of Aggregates (SRA).  SRA is run
24    twice, once in the early stages of compilation (early SRA) and once in the
25    late stages (late SRA).  The aim of both is to turn references to scalar
26    parts of aggregates into uses of independent scalar variables.
27
28    The two passes are nearly identical, the only difference is that early SRA
29    does not scalarize unions which are used as the result in a GIMPLE_RETURN
30    statement because together with inlining this can lead to weird type
31    conversions.
32
33    Both passes operate in four stages:
34
35    1. The declarations that have properties which make them candidates for
36       scalarization are identified in function find_var_candidates().  The
37       candidates are stored in candidate_bitmap.
38
39    2. The function body is scanned.  In the process, declarations which are
40       used in a manner that prevent their scalarization are removed from the
41       candidate bitmap.  More importantly, for every access into an aggregate,
42       an access structure (struct access) is created by create_access() and
43       stored in a vector associated with the aggregate.  Among other
44       information, the aggregate declaration, the offset and size of the access
45       and its type are stored in the structure.
46
47       On a related note, assign_link structures are created for every assign
48       statement between candidate aggregates and attached to the related
49       accesses.
50
51    3. The vectors of accesses are analyzed.  They are first sorted according to
52       their offset and size and then scanned for partially overlapping accesses
53       (i.e. those which overlap but one is not entirely within another).  Such
54       an access disqualifies the whole aggregate from being scalarized.
55
56       If there is no such inhibiting overlap, a representative access structure
57       is chosen for every unique combination of offset and size.  Afterwards,
58       the pass builds a set of trees from these structures, in which children
59       of an access are within their parent (in terms of offset and size).
60
61       Then accesses  are propagated  whenever possible (i.e.  in cases  when it
62       does not create a partially overlapping access) across assign_links from
63       the right hand side to the left hand side.
64
65       Then the set of trees for each declaration is traversed again and those
66       accesses which should be replaced by a scalar are identified.
67
68    4. The function is traversed again, and for every reference into an
69       aggregate that has some component which is about to be scalarized,
70       statements are amended and new statements are created as necessary.
71       Finally, if a parameter got scalarized, the scalar replacements are
72       initialized with values from respective parameter aggregates.  */
73
74 #include "config.h"
75 #include "system.h"
76 #include "coretypes.h"
77 #include "alloc-pool.h"
78 #include "tm.h"
79 #include "tree.h"
80 #include "gimple.h"
81 #include "cgraph.h"
82 #include "tree-flow.h"
83 #include "ipa-prop.h"
84 #include "tree-pretty-print.h"
85 #include "statistics.h"
86 #include "tree-dump.h"
87 #include "timevar.h"
88 #include "params.h"
89 #include "target.h"
90 #include "flags.h"
91 #include "dbgcnt.h"
92 #include "tree-inline.h"
93 #include "gimple-pretty-print.h"
94 #include "ipa-inline.h"
95
96 /* Enumeration of all aggregate reductions we can do.  */
97 enum sra_mode { SRA_MODE_EARLY_IPA,   /* early call regularization */
98                 SRA_MODE_EARLY_INTRA, /* early intraprocedural SRA */
99                 SRA_MODE_INTRA };     /* late intraprocedural SRA */
100
101 /* Global variable describing which aggregate reduction we are performing at
102    the moment.  */
103 static enum sra_mode sra_mode;
104
105 struct assign_link;
106
107 /* ACCESS represents each access to an aggregate variable (as a whole or a
108    part).  It can also represent a group of accesses that refer to exactly the
109    same fragment of an aggregate (i.e. those that have exactly the same offset
110    and size).  Such representatives for a single aggregate, once determined,
111    are linked in a linked list and have the group fields set.
112
113    Moreover, when doing intraprocedural SRA, a tree is built from those
114    representatives (by the means of first_child and next_sibling pointers), in
115    which all items in a subtree are "within" the root, i.e. their offset is
116    greater or equal to offset of the root and offset+size is smaller or equal
117    to offset+size of the root.  Children of an access are sorted by offset.
118
119    Note that accesses to parts of vector and complex number types always
120    represented by an access to the whole complex number or a vector.  It is a
121    duty of the modifying functions to replace them appropriately.  */
122
123 struct access
124 {
125   /* Values returned by  `get_ref_base_and_extent' for each component reference
126      If EXPR isn't a component reference  just set `BASE = EXPR', `OFFSET = 0',
127      `SIZE = TREE_SIZE (TREE_TYPE (expr))'.  */
128   HOST_WIDE_INT offset;
129   HOST_WIDE_INT size;
130   tree base;
131
132   /* Expression.  It is context dependent so do not use it to create new
133      expressions to access the original aggregate.  See PR 42154 for a
134      testcase.  */
135   tree expr;
136   /* Type.  */
137   tree type;
138
139   /* The statement this access belongs to.  */
140   gimple stmt;
141
142   /* Next group representative for this aggregate. */
143   struct access *next_grp;
144
145   /* Pointer to the group representative.  Pointer to itself if the struct is
146      the representative.  */
147   struct access *group_representative;
148
149   /* If this access has any children (in terms of the definition above), this
150      points to the first one.  */
151   struct access *first_child;
152
153   /* In intraprocedural SRA, pointer to the next sibling in the access tree as
154      described above.  In IPA-SRA this is a pointer to the next access
155      belonging to the same group (having the same representative).  */
156   struct access *next_sibling;
157
158   /* Pointers to the first and last element in the linked list of assign
159      links.  */
160   struct assign_link *first_link, *last_link;
161
162   /* Pointer to the next access in the work queue.  */
163   struct access *next_queued;
164
165   /* Replacement variable for this access "region."  Never to be accessed
166      directly, always only by the means of get_access_replacement() and only
167      when grp_to_be_replaced flag is set.  */
168   tree replacement_decl;
169
170   /* Is this particular access write access? */
171   unsigned write : 1;
172
173   /* Is this access an access to a non-addressable field? */
174   unsigned non_addressable : 1;
175
176   /* Is this access currently in the work queue?  */
177   unsigned grp_queued : 1;
178
179   /* Does this group contain a write access?  This flag is propagated down the
180      access tree.  */
181   unsigned grp_write : 1;
182
183   /* Does this group contain a read access?  This flag is propagated down the
184      access tree.  */
185   unsigned grp_read : 1;
186
187   /* Does this group contain a read access that comes from an assignment
188      statement?  This flag is propagated down the access tree.  */
189   unsigned grp_assignment_read : 1;
190
191   /* Does this group contain a write access that comes from an assignment
192      statement?  This flag is propagated down the access tree.  */
193   unsigned grp_assignment_write : 1;
194
195   /* Does this group contain a read access through a scalar type?  This flag is
196      not propagated in the access tree in any direction.  */
197   unsigned grp_scalar_read : 1;
198
199   /* Does this group contain a write access through a scalar type?  This flag
200      is not propagated in the access tree in any direction.  */
201   unsigned grp_scalar_write : 1;
202
203   /* Is this access an artificial one created to scalarize some record
204      entirely? */
205   unsigned grp_total_scalarization : 1;
206
207   /* Other passes of the analysis use this bit to make function
208      analyze_access_subtree create scalar replacements for this group if
209      possible.  */
210   unsigned grp_hint : 1;
211
212   /* Is the subtree rooted in this access fully covered by scalar
213      replacements?  */
214   unsigned grp_covered : 1;
215
216   /* If set to true, this access and all below it in an access tree must not be
217      scalarized.  */
218   unsigned grp_unscalarizable_region : 1;
219
220   /* Whether data have been written to parts of the aggregate covered by this
221      access which is not to be scalarized.  This flag is propagated up in the
222      access tree.  */
223   unsigned grp_unscalarized_data : 1;
224
225   /* Does this access and/or group contain a write access through a
226      BIT_FIELD_REF?  */
227   unsigned grp_partial_lhs : 1;
228
229   /* Set when a scalar replacement should be created for this variable.  We do
230      the decision and creation at different places because create_tmp_var
231      cannot be called from within FOR_EACH_REFERENCED_VAR. */
232   unsigned grp_to_be_replaced : 1;
233
234   /* Should TREE_NO_WARNING of a replacement be set?  */
235   unsigned grp_no_warning : 1;
236
237   /* Is it possible that the group refers to data which might be (directly or
238      otherwise) modified?  */
239   unsigned grp_maybe_modified : 1;
240
241   /* Set when this is a representative of a pointer to scalar (i.e. by
242      reference) parameter which we consider for turning into a plain scalar
243      (i.e. a by value parameter).  */
244   unsigned grp_scalar_ptr : 1;
245
246   /* Set when we discover that this pointer is not safe to dereference in the
247      caller.  */
248   unsigned grp_not_necessarilly_dereferenced : 1;
249 };
250
251 typedef struct access *access_p;
252
253 DEF_VEC_P (access_p);
254 DEF_VEC_ALLOC_P (access_p, heap);
255
256 /* Alloc pool for allocating access structures.  */
257 static alloc_pool access_pool;
258
259 /* A structure linking lhs and rhs accesses from an aggregate assignment.  They
260    are used to propagate subaccesses from rhs to lhs as long as they don't
261    conflict with what is already there.  */
262 struct assign_link
263 {
264   struct access *lacc, *racc;
265   struct assign_link *next;
266 };
267
268 /* Alloc pool for allocating assign link structures.  */
269 static alloc_pool link_pool;
270
271 /* Base (tree) -> Vector (VEC(access_p,heap) *) map.  */
272 static struct pointer_map_t *base_access_vec;
273
274 /* Bitmap of candidates.  */
275 static bitmap candidate_bitmap;
276
277 /* Bitmap of candidates which we should try to entirely scalarize away and
278    those which cannot be (because they are and need be used as a whole).  */
279 static bitmap should_scalarize_away_bitmap, cannot_scalarize_away_bitmap;
280
281 /* Obstack for creation of fancy names.  */
282 static struct obstack name_obstack;
283
284 /* Head of a linked list of accesses that need to have its subaccesses
285    propagated to their assignment counterparts. */
286 static struct access *work_queue_head;
287
288 /* Number of parameters of the analyzed function when doing early ipa SRA.  */
289 static int func_param_count;
290
291 /* scan_function sets the following to true if it encounters a call to
292    __builtin_apply_args.  */
293 static bool encountered_apply_args;
294
295 /* Set by scan_function when it finds a recursive call.  */
296 static bool encountered_recursive_call;
297
298 /* Set by scan_function when it finds a recursive call with less actual
299    arguments than formal parameters..  */
300 static bool encountered_unchangable_recursive_call;
301
302 /* This is a table in which for each basic block and parameter there is a
303    distance (offset + size) in that parameter which is dereferenced and
304    accessed in that BB.  */
305 static HOST_WIDE_INT *bb_dereferences;
306 /* Bitmap of BBs that can cause the function to "stop" progressing by
307    returning, throwing externally, looping infinitely or calling a function
308    which might abort etc.. */
309 static bitmap final_bbs;
310
311 /* Representative of no accesses at all. */
312 static struct access  no_accesses_representant;
313
314 /* Predicate to test the special value.  */
315
316 static inline bool
317 no_accesses_p (struct access *access)
318 {
319   return access == &no_accesses_representant;
320 }
321
322 /* Dump contents of ACCESS to file F in a human friendly way.  If GRP is true,
323    representative fields are dumped, otherwise those which only describe the
324    individual access are.  */
325
326 static struct
327 {
328   /* Number of processed aggregates is readily available in
329      analyze_all_variable_accesses and so is not stored here.  */
330
331   /* Number of created scalar replacements.  */
332   int replacements;
333
334   /* Number of times sra_modify_expr or sra_modify_assign themselves changed an
335      expression.  */
336   int exprs;
337
338   /* Number of statements created by generate_subtree_copies.  */
339   int subtree_copies;
340
341   /* Number of statements created by load_assign_lhs_subreplacements.  */
342   int subreplacements;
343
344   /* Number of times sra_modify_assign has deleted a statement.  */
345   int deleted;
346
347   /* Number of times sra_modify_assign has to deal with subaccesses of LHS and
348      RHS reparately due to type conversions or nonexistent matching
349      references.  */
350   int separate_lhs_rhs_handling;
351
352   /* Number of parameters that were removed because they were unused.  */
353   int deleted_unused_parameters;
354
355   /* Number of scalars passed as parameters by reference that have been
356      converted to be passed by value.  */
357   int scalar_by_ref_to_by_val;
358
359   /* Number of aggregate parameters that were replaced by one or more of their
360      components.  */
361   int aggregate_params_reduced;
362
363   /* Numbber of components created when splitting aggregate parameters.  */
364   int param_reductions_created;
365 } sra_stats;
366
367 static void
368 dump_access (FILE *f, struct access *access, bool grp)
369 {
370   fprintf (f, "access { ");
371   fprintf (f, "base = (%d)'", DECL_UID (access->base));
372   print_generic_expr (f, access->base, 0);
373   fprintf (f, "', offset = " HOST_WIDE_INT_PRINT_DEC, access->offset);
374   fprintf (f, ", size = " HOST_WIDE_INT_PRINT_DEC, access->size);
375   fprintf (f, ", expr = ");
376   print_generic_expr (f, access->expr, 0);
377   fprintf (f, ", type = ");
378   print_generic_expr (f, access->type, 0);
379   if (grp)
380     fprintf (f, ", grp_read = %d, grp_write = %d, grp_assignment_read = %d, "
381              "grp_assignment_write = %d, grp_scalar_read = %d, "
382              "grp_scalar_write = %d, grp_total_scalarization = %d, "
383              "grp_hint = %d, grp_covered = %d, "
384              "grp_unscalarizable_region = %d, grp_unscalarized_data = %d, "
385              "grp_partial_lhs = %d, grp_to_be_replaced = %d, "
386              "grp_maybe_modified = %d, "
387              "grp_not_necessarilly_dereferenced = %d\n",
388              access->grp_read, access->grp_write, access->grp_assignment_read,
389              access->grp_assignment_write, access->grp_scalar_read,
390              access->grp_scalar_write, access->grp_total_scalarization,
391              access->grp_hint, access->grp_covered,
392              access->grp_unscalarizable_region, access->grp_unscalarized_data,
393              access->grp_partial_lhs, access->grp_to_be_replaced,
394              access->grp_maybe_modified,
395              access->grp_not_necessarilly_dereferenced);
396   else
397     fprintf (f, ", write = %d, grp_total_scalarization = %d, "
398              "grp_partial_lhs = %d\n",
399              access->write, access->grp_total_scalarization,
400              access->grp_partial_lhs);
401 }
402
403 /* Dump a subtree rooted in ACCESS to file F, indent by LEVEL.  */
404
405 static void
406 dump_access_tree_1 (FILE *f, struct access *access, int level)
407 {
408   do
409     {
410       int i;
411
412       for (i = 0; i < level; i++)
413         fputs ("* ", dump_file);
414
415       dump_access (f, access, true);
416
417       if (access->first_child)
418         dump_access_tree_1 (f, access->first_child, level + 1);
419
420       access = access->next_sibling;
421     }
422   while (access);
423 }
424
425 /* Dump all access trees for a variable, given the pointer to the first root in
426    ACCESS.  */
427
428 static void
429 dump_access_tree (FILE *f, struct access *access)
430 {
431   for (; access; access = access->next_grp)
432     dump_access_tree_1 (f, access, 0);
433 }
434
435 /* Return true iff ACC is non-NULL and has subaccesses.  */
436
437 static inline bool
438 access_has_children_p (struct access *acc)
439 {
440   return acc && acc->first_child;
441 }
442
443 /* Return true iff ACC is (partly) covered by at least one replacement.  */
444
445 static bool
446 access_has_replacements_p (struct access *acc)
447 {
448   struct access *child;
449   if (acc->grp_to_be_replaced)
450     return true;
451   for (child = acc->first_child; child; child = child->next_sibling)
452     if (access_has_replacements_p (child))
453       return true;
454   return false;
455 }
456
457 /* Return a vector of pointers to accesses for the variable given in BASE or
458    NULL if there is none.  */
459
460 static VEC (access_p, heap) *
461 get_base_access_vector (tree base)
462 {
463   void **slot;
464
465   slot = pointer_map_contains (base_access_vec, base);
466   if (!slot)
467     return NULL;
468   else
469     return *(VEC (access_p, heap) **) slot;
470 }
471
472 /* Find an access with required OFFSET and SIZE in a subtree of accesses rooted
473    in ACCESS.  Return NULL if it cannot be found.  */
474
475 static struct access *
476 find_access_in_subtree (struct access *access, HOST_WIDE_INT offset,
477                         HOST_WIDE_INT size)
478 {
479   while (access && (access->offset != offset || access->size != size))
480     {
481       struct access *child = access->first_child;
482
483       while (child && (child->offset + child->size <= offset))
484         child = child->next_sibling;
485       access = child;
486     }
487
488   return access;
489 }
490
491 /* Return the first group representative for DECL or NULL if none exists.  */
492
493 static struct access *
494 get_first_repr_for_decl (tree base)
495 {
496   VEC (access_p, heap) *access_vec;
497
498   access_vec = get_base_access_vector (base);
499   if (!access_vec)
500     return NULL;
501
502   return VEC_index (access_p, access_vec, 0);
503 }
504
505 /* Find an access representative for the variable BASE and given OFFSET and
506    SIZE.  Requires that access trees have already been built.  Return NULL if
507    it cannot be found.  */
508
509 static struct access *
510 get_var_base_offset_size_access (tree base, HOST_WIDE_INT offset,
511                                  HOST_WIDE_INT size)
512 {
513   struct access *access;
514
515   access = get_first_repr_for_decl (base);
516   while (access && (access->offset + access->size <= offset))
517     access = access->next_grp;
518   if (!access)
519     return NULL;
520
521   return find_access_in_subtree (access, offset, size);
522 }
523
524 /* Add LINK to the linked list of assign links of RACC.  */
525 static void
526 add_link_to_rhs (struct access *racc, struct assign_link *link)
527 {
528   gcc_assert (link->racc == racc);
529
530   if (!racc->first_link)
531     {
532       gcc_assert (!racc->last_link);
533       racc->first_link = link;
534     }
535   else
536     racc->last_link->next = link;
537
538   racc->last_link = link;
539   link->next = NULL;
540 }
541
542 /* Move all link structures in their linked list in OLD_RACC to the linked list
543    in NEW_RACC.  */
544 static void
545 relink_to_new_repr (struct access *new_racc, struct access *old_racc)
546 {
547   if (!old_racc->first_link)
548     {
549       gcc_assert (!old_racc->last_link);
550       return;
551     }
552
553   if (new_racc->first_link)
554     {
555       gcc_assert (!new_racc->last_link->next);
556       gcc_assert (!old_racc->last_link || !old_racc->last_link->next);
557
558       new_racc->last_link->next = old_racc->first_link;
559       new_racc->last_link = old_racc->last_link;
560     }
561   else
562     {
563       gcc_assert (!new_racc->last_link);
564
565       new_racc->first_link = old_racc->first_link;
566       new_racc->last_link = old_racc->last_link;
567     }
568   old_racc->first_link = old_racc->last_link = NULL;
569 }
570
571 /* Add ACCESS to the work queue (which is actually a stack).  */
572
573 static void
574 add_access_to_work_queue (struct access *access)
575 {
576   if (!access->grp_queued)
577     {
578       gcc_assert (!access->next_queued);
579       access->next_queued = work_queue_head;
580       access->grp_queued = 1;
581       work_queue_head = access;
582     }
583 }
584
585 /* Pop an access from the work queue, and return it, assuming there is one.  */
586
587 static struct access *
588 pop_access_from_work_queue (void)
589 {
590   struct access *access = work_queue_head;
591
592   work_queue_head = access->next_queued;
593   access->next_queued = NULL;
594   access->grp_queued = 0;
595   return access;
596 }
597
598
599 /* Allocate necessary structures.  */
600
601 static void
602 sra_initialize (void)
603 {
604   candidate_bitmap = BITMAP_ALLOC (NULL);
605   should_scalarize_away_bitmap = BITMAP_ALLOC (NULL);
606   cannot_scalarize_away_bitmap = BITMAP_ALLOC (NULL);
607   gcc_obstack_init (&name_obstack);
608   access_pool = create_alloc_pool ("SRA accesses", sizeof (struct access), 16);
609   link_pool = create_alloc_pool ("SRA links", sizeof (struct assign_link), 16);
610   base_access_vec = pointer_map_create ();
611   memset (&sra_stats, 0, sizeof (sra_stats));
612   encountered_apply_args = false;
613   encountered_recursive_call = false;
614   encountered_unchangable_recursive_call = false;
615 }
616
617 /* Hook fed to pointer_map_traverse, deallocate stored vectors.  */
618
619 static bool
620 delete_base_accesses (const void *key ATTRIBUTE_UNUSED, void **value,
621                      void *data ATTRIBUTE_UNUSED)
622 {
623   VEC (access_p, heap) *access_vec;
624   access_vec = (VEC (access_p, heap) *) *value;
625   VEC_free (access_p, heap, access_vec);
626
627   return true;
628 }
629
630 /* Deallocate all general structures.  */
631
632 static void
633 sra_deinitialize (void)
634 {
635   BITMAP_FREE (candidate_bitmap);
636   BITMAP_FREE (should_scalarize_away_bitmap);
637   BITMAP_FREE (cannot_scalarize_away_bitmap);
638   free_alloc_pool (access_pool);
639   free_alloc_pool (link_pool);
640   obstack_free (&name_obstack, NULL);
641
642   pointer_map_traverse (base_access_vec, delete_base_accesses, NULL);
643   pointer_map_destroy (base_access_vec);
644 }
645
646 /* Remove DECL from candidates for SRA and write REASON to the dump file if
647    there is one.  */
648 static void
649 disqualify_candidate (tree decl, const char *reason)
650 {
651   bitmap_clear_bit (candidate_bitmap, DECL_UID (decl));
652
653   if (dump_file && (dump_flags & TDF_DETAILS))
654     {
655       fprintf (dump_file, "! Disqualifying ");
656       print_generic_expr (dump_file, decl, 0);
657       fprintf (dump_file, " - %s\n", reason);
658     }
659 }
660
661 /* Return true iff the type contains a field or an element which does not allow
662    scalarization.  */
663
664 static bool
665 type_internals_preclude_sra_p (tree type, const char **msg)
666 {
667   tree fld;
668   tree et;
669
670   switch (TREE_CODE (type))
671     {
672     case RECORD_TYPE:
673     case UNION_TYPE:
674     case QUAL_UNION_TYPE:
675       for (fld = TYPE_FIELDS (type); fld; fld = DECL_CHAIN (fld))
676         if (TREE_CODE (fld) == FIELD_DECL)
677           {
678             tree ft = TREE_TYPE (fld);
679
680             if (TREE_THIS_VOLATILE (fld))
681               {
682                 *msg = "volatile structure field";
683                 return true;
684               }
685             if (!DECL_FIELD_OFFSET (fld))
686               {
687                 *msg = "no structure field offset";
688                 return true;
689               }
690             if (!DECL_SIZE (fld))
691               {
692                 *msg = "zero structure field size";
693                 return true;
694               }
695             if (!host_integerp (DECL_FIELD_OFFSET (fld), 1))
696               {
697                 *msg = "structure field offset not fixed";
698                 return true;
699               }
700             if (!host_integerp (DECL_SIZE (fld), 1))
701               {
702                 *msg = "structure field size not fixed";
703                 return true;
704               }       
705             if (AGGREGATE_TYPE_P (ft)
706                     && int_bit_position (fld) % BITS_PER_UNIT != 0)
707               {
708                 *msg = "structure field is bit field";
709                 return true;
710               }
711
712             if (AGGREGATE_TYPE_P (ft) && type_internals_preclude_sra_p (ft, msg))
713               return true;
714           }
715
716       return false;
717
718     case ARRAY_TYPE:
719       et = TREE_TYPE (type);
720
721       if (TYPE_VOLATILE (et))
722         {
723           *msg = "element type is volatile";
724           return true;
725         }
726
727       if (AGGREGATE_TYPE_P (et) && type_internals_preclude_sra_p (et, msg))
728         return true;
729
730       return false;
731
732     default:
733       return false;
734     }
735 }
736
737 /* If T is an SSA_NAME, return NULL if it is not a default def or return its
738    base variable if it is.  Return T if it is not an SSA_NAME.  */
739
740 static tree
741 get_ssa_base_param (tree t)
742 {
743   if (TREE_CODE (t) == SSA_NAME)
744     {
745       if (SSA_NAME_IS_DEFAULT_DEF (t))
746         return SSA_NAME_VAR (t);
747       else
748         return NULL_TREE;
749     }
750   return t;
751 }
752
753 /* Mark a dereference of BASE of distance DIST in a basic block tht STMT
754    belongs to, unless the BB has already been marked as a potentially
755    final.  */
756
757 static void
758 mark_parm_dereference (tree base, HOST_WIDE_INT dist, gimple stmt)
759 {
760   basic_block bb = gimple_bb (stmt);
761   int idx, parm_index = 0;
762   tree parm;
763
764   if (bitmap_bit_p (final_bbs, bb->index))
765     return;
766
767   for (parm = DECL_ARGUMENTS (current_function_decl);
768        parm && parm != base;
769        parm = DECL_CHAIN (parm))
770     parm_index++;
771
772   gcc_assert (parm_index < func_param_count);
773
774   idx = bb->index * func_param_count + parm_index;
775   if (bb_dereferences[idx] < dist)
776     bb_dereferences[idx] = dist;
777 }
778
779 /* Allocate an access structure for BASE, OFFSET and SIZE, clear it, fill in
780    the three fields.  Also add it to the vector of accesses corresponding to
781    the base.  Finally, return the new access.  */
782
783 static struct access *
784 create_access_1 (tree base, HOST_WIDE_INT offset, HOST_WIDE_INT size)
785 {
786   VEC (access_p, heap) *vec;
787   struct access *access;
788   void **slot;
789
790   access = (struct access *) pool_alloc (access_pool);
791   memset (access, 0, sizeof (struct access));
792   access->base = base;
793   access->offset = offset;
794   access->size = size;
795
796   slot = pointer_map_contains (base_access_vec, base);
797   if (slot)
798     vec = (VEC (access_p, heap) *) *slot;
799   else
800     vec = VEC_alloc (access_p, heap, 32);
801
802   VEC_safe_push (access_p, heap, vec, access);
803
804   *((struct VEC (access_p,heap) **)
805         pointer_map_insert (base_access_vec, base)) = vec;
806
807   return access;
808 }
809
810 /* Create and insert access for EXPR. Return created access, or NULL if it is
811    not possible.  */
812
813 static struct access *
814 create_access (tree expr, gimple stmt, bool write)
815 {
816   struct access *access;
817   HOST_WIDE_INT offset, size, max_size;
818   tree base = expr;
819   bool ptr, unscalarizable_region = false;
820
821   base = get_ref_base_and_extent (expr, &offset, &size, &max_size);
822
823   if (sra_mode == SRA_MODE_EARLY_IPA
824       && TREE_CODE (base) == MEM_REF)
825     {
826       base = get_ssa_base_param (TREE_OPERAND (base, 0));
827       if (!base)
828         return NULL;
829       ptr = true;
830     }
831   else
832     ptr = false;
833
834   if (!DECL_P (base) || !bitmap_bit_p (candidate_bitmap, DECL_UID (base)))
835     return NULL;
836
837   if (sra_mode == SRA_MODE_EARLY_IPA)
838     {
839       if (size < 0 || size != max_size)
840         {
841           disqualify_candidate (base, "Encountered a variable sized access.");
842           return NULL;
843         }
844       if (TREE_CODE (expr) == COMPONENT_REF
845           && DECL_BIT_FIELD (TREE_OPERAND (expr, 1)))
846         {
847           disqualify_candidate (base, "Encountered a bit-field access.");
848           return NULL;
849         }
850       gcc_checking_assert ((offset % BITS_PER_UNIT) == 0);
851
852       if (ptr)
853         mark_parm_dereference (base, offset + size, stmt);
854     }
855   else
856     {
857       if (size != max_size)
858         {
859           size = max_size;
860           unscalarizable_region = true;
861         }
862       if (size < 0)
863         {
864           disqualify_candidate (base, "Encountered an unconstrained access.");
865           return NULL;
866         }
867     }
868
869   access = create_access_1 (base, offset, size);
870   access->expr = expr;
871   access->type = TREE_TYPE (expr);
872   access->write = write;
873   access->grp_unscalarizable_region = unscalarizable_region;
874   access->stmt = stmt;
875
876   if (TREE_CODE (expr) == COMPONENT_REF
877       && DECL_NONADDRESSABLE_P (TREE_OPERAND (expr, 1)))
878     access->non_addressable = 1;
879
880   return access;
881 }
882
883
884 /* Return true iff TYPE is a RECORD_TYPE with fields that are either of gimple
885    register types or (recursively) records with only these two kinds of fields.
886    It also returns false if any of these records contains a bit-field.  */
887
888 static bool
889 type_consists_of_records_p (tree type)
890 {
891   tree fld;
892
893   if (TREE_CODE (type) != RECORD_TYPE)
894     return false;
895
896   for (fld = TYPE_FIELDS (type); fld; fld = DECL_CHAIN (fld))
897     if (TREE_CODE (fld) == FIELD_DECL)
898       {
899         tree ft = TREE_TYPE (fld);
900
901         if (DECL_BIT_FIELD (fld))
902           return false;
903
904         if (!is_gimple_reg_type (ft)
905             && !type_consists_of_records_p (ft))
906           return false;
907       }
908
909   return true;
910 }
911
912 /* Create total_scalarization accesses for all scalar type fields in DECL that
913    must be of a RECORD_TYPE conforming to type_consists_of_records_p.  BASE
914    must be the top-most VAR_DECL representing the variable, OFFSET must be the
915    offset of DECL within BASE.  REF must be the memory reference expression for
916    the given decl.  */
917
918 static void
919 completely_scalarize_record (tree base, tree decl, HOST_WIDE_INT offset,
920                              tree ref)
921 {
922   tree fld, decl_type = TREE_TYPE (decl);
923
924   for (fld = TYPE_FIELDS (decl_type); fld; fld = DECL_CHAIN (fld))
925     if (TREE_CODE (fld) == FIELD_DECL)
926       {
927         HOST_WIDE_INT pos = offset + int_bit_position (fld);
928         tree ft = TREE_TYPE (fld);
929         tree nref = build3 (COMPONENT_REF, TREE_TYPE (fld), ref, fld,
930                             NULL_TREE);
931
932         if (is_gimple_reg_type (ft))
933           {
934             struct access *access;
935             HOST_WIDE_INT size;
936
937             size = tree_low_cst (DECL_SIZE (fld), 1);
938             access = create_access_1 (base, pos, size);
939             access->expr = nref;
940             access->type = ft;
941             access->grp_total_scalarization = 1;
942             /* Accesses for intraprocedural SRA can have their stmt NULL.  */
943           }
944         else
945           completely_scalarize_record (base, fld, pos, nref);
946       }
947 }
948
949 /* Create total_scalarization accesses for all scalar type fields in VAR and
950    for VAR a a whole.  VAR must be of a RECORD_TYPE conforming to
951    type_consists_of_records_p.   */
952
953 static void
954 completely_scalarize_var (tree var)
955 {
956   HOST_WIDE_INT size = tree_low_cst (DECL_SIZE (var), 1);
957   struct access *access;
958
959   access = create_access_1 (var, 0, size);
960   access->expr = var;
961   access->type = TREE_TYPE (var);
962   access->grp_total_scalarization = 1;
963
964   completely_scalarize_record (var, var, 0, var);
965 }
966
967 /* Search the given tree for a declaration by skipping handled components and
968    exclude it from the candidates.  */
969
970 static void
971 disqualify_base_of_expr (tree t, const char *reason)
972 {
973   t = get_base_address (t);
974   if (sra_mode == SRA_MODE_EARLY_IPA
975       && TREE_CODE (t) == MEM_REF)
976     t = get_ssa_base_param (TREE_OPERAND (t, 0));
977
978   if (t && DECL_P (t))
979     disqualify_candidate (t, reason);
980 }
981
982 /* Scan expression EXPR and create access structures for all accesses to
983    candidates for scalarization.  Return the created access or NULL if none is
984    created.  */
985
986 static struct access *
987 build_access_from_expr_1 (tree expr, gimple stmt, bool write)
988 {
989   struct access *ret = NULL;
990   bool partial_ref;
991
992   if (TREE_CODE (expr) == BIT_FIELD_REF
993       || TREE_CODE (expr) == IMAGPART_EXPR
994       || TREE_CODE (expr) == REALPART_EXPR)
995     {
996       expr = TREE_OPERAND (expr, 0);
997       partial_ref = true;
998     }
999   else
1000     partial_ref = false;
1001
1002   /* We need to dive through V_C_Es in order to get the size of its parameter
1003      and not the result type.  Ada produces such statements.  We are also
1004      capable of handling the topmost V_C_E but not any of those buried in other
1005      handled components.  */
1006   if (TREE_CODE (expr) == VIEW_CONVERT_EXPR)
1007     expr = TREE_OPERAND (expr, 0);
1008
1009   if (contains_view_convert_expr_p (expr))
1010     {
1011       disqualify_base_of_expr (expr, "V_C_E under a different handled "
1012                                "component.");
1013       return NULL;
1014     }
1015
1016   switch (TREE_CODE (expr))
1017     {
1018     case MEM_REF:
1019       if (TREE_CODE (TREE_OPERAND (expr, 0)) != ADDR_EXPR
1020           && sra_mode != SRA_MODE_EARLY_IPA)
1021         return NULL;
1022       /* fall through */
1023     case VAR_DECL:
1024     case PARM_DECL:
1025     case RESULT_DECL:
1026     case COMPONENT_REF:
1027     case ARRAY_REF:
1028     case ARRAY_RANGE_REF:
1029       ret = create_access (expr, stmt, write);
1030       break;
1031
1032     default:
1033       break;
1034     }
1035
1036   if (write && partial_ref && ret)
1037     ret->grp_partial_lhs = 1;
1038
1039   return ret;
1040 }
1041
1042 /* Scan expression EXPR and create access structures for all accesses to
1043    candidates for scalarization.  Return true if any access has been inserted.
1044    STMT must be the statement from which the expression is taken, WRITE must be
1045    true if the expression is a store and false otherwise. */
1046
1047 static bool
1048 build_access_from_expr (tree expr, gimple stmt, bool write)
1049 {
1050   struct access *access;
1051
1052   access = build_access_from_expr_1 (expr, stmt, write);
1053   if (access)
1054     {
1055       /* This means the aggregate is accesses as a whole in a way other than an
1056          assign statement and thus cannot be removed even if we had a scalar
1057          replacement for everything.  */
1058       if (cannot_scalarize_away_bitmap)
1059         bitmap_set_bit (cannot_scalarize_away_bitmap, DECL_UID (access->base));
1060       return true;
1061     }
1062   return false;
1063 }
1064
1065 /* Disqualify LHS and RHS for scalarization if STMT must end its basic block in
1066    modes in which it matters, return true iff they have been disqualified.  RHS
1067    may be NULL, in that case ignore it.  If we scalarize an aggregate in
1068    intra-SRA we may need to add statements after each statement.  This is not
1069    possible if a statement unconditionally has to end the basic block.  */
1070 static bool
1071 disqualify_ops_if_throwing_stmt (gimple stmt, tree lhs, tree rhs)
1072 {
1073   if ((sra_mode == SRA_MODE_EARLY_INTRA || sra_mode == SRA_MODE_INTRA)
1074       && (stmt_can_throw_internal (stmt) || stmt_ends_bb_p (stmt)))
1075     {
1076       disqualify_base_of_expr (lhs, "LHS of a throwing stmt.");
1077       if (rhs)
1078         disqualify_base_of_expr (rhs, "RHS of a throwing stmt.");
1079       return true;
1080     }
1081   return false;
1082 }
1083
1084 /* Return true if EXP is a memory reference less aligned than ALIGN.  This is
1085    invoked only on strict-alignment targets.  */
1086
1087 static bool
1088 tree_non_aligned_mem_p (tree exp, unsigned int align)
1089 {
1090   unsigned int exp_align;
1091
1092   if (TREE_CODE (exp) == VIEW_CONVERT_EXPR)
1093     exp = TREE_OPERAND (exp, 0);
1094
1095   if (TREE_CODE (exp) == SSA_NAME || is_gimple_min_invariant (exp))
1096     return false;
1097
1098   /* get_object_alignment will fall back to BITS_PER_UNIT if it cannot
1099      compute an explicit alignment.  Pretend that dereferenced pointers
1100      are always aligned on strict-alignment targets.  */
1101   if (TREE_CODE (exp) == MEM_REF || TREE_CODE (exp) == TARGET_MEM_REF)
1102     exp_align = get_object_or_type_alignment (exp);
1103   else
1104     exp_align = get_object_alignment (exp);
1105
1106   if (exp_align < align)
1107     return true;
1108
1109   return false;
1110 }
1111
1112 /* Return true if EXP is a memory reference less aligned than what the access
1113    ACC would require.  This is invoked only on strict-alignment targets.  */
1114
1115 static bool
1116 tree_non_aligned_mem_for_access_p (tree exp, struct access *acc)
1117 {
1118   unsigned int acc_align;
1119
1120   /* The alignment of the access is that of its expression.  However, it may
1121      have been artificially increased, e.g. by a local alignment promotion,
1122      so we cap it to the alignment of the type of the base, on the grounds
1123      that valid sub-accesses cannot be more aligned than that.  */
1124   acc_align = get_object_alignment (acc->expr);
1125   if (acc->base && acc_align > TYPE_ALIGN (TREE_TYPE (acc->base)))
1126     acc_align = TYPE_ALIGN (TREE_TYPE (acc->base));
1127
1128   return tree_non_aligned_mem_p (exp, acc_align);
1129 }
1130
1131 /* Scan expressions occuring in STMT, create access structures for all accesses
1132    to candidates for scalarization and remove those candidates which occur in
1133    statements or expressions that prevent them from being split apart.  Return
1134    true if any access has been inserted.  */
1135
1136 static bool
1137 build_accesses_from_assign (gimple stmt)
1138 {
1139   tree lhs, rhs;
1140   struct access *lacc, *racc;
1141
1142   if (!gimple_assign_single_p (stmt)
1143       /* Scope clobbers don't influence scalarization.  */
1144       || gimple_clobber_p (stmt))
1145     return false;
1146
1147   lhs = gimple_assign_lhs (stmt);
1148   rhs = gimple_assign_rhs1 (stmt);
1149
1150   if (disqualify_ops_if_throwing_stmt (stmt, lhs, rhs))
1151     return false;
1152
1153   racc = build_access_from_expr_1 (rhs, stmt, false);
1154   lacc = build_access_from_expr_1 (lhs, stmt, true);
1155
1156   if (lacc)
1157     {
1158       lacc->grp_assignment_write = 1;
1159       if (STRICT_ALIGNMENT && tree_non_aligned_mem_for_access_p (rhs, lacc))
1160         lacc->grp_unscalarizable_region = 1;
1161     }
1162
1163   if (racc)
1164     {
1165       racc->grp_assignment_read = 1;
1166       if (should_scalarize_away_bitmap && !gimple_has_volatile_ops (stmt)
1167           && !is_gimple_reg_type (racc->type))
1168         bitmap_set_bit (should_scalarize_away_bitmap, DECL_UID (racc->base));
1169       if (STRICT_ALIGNMENT && tree_non_aligned_mem_for_access_p (lhs, racc))
1170         racc->grp_unscalarizable_region = 1;
1171     }
1172
1173   if (lacc && racc
1174       && (sra_mode == SRA_MODE_EARLY_INTRA || sra_mode == SRA_MODE_INTRA)
1175       && !lacc->grp_unscalarizable_region
1176       && !racc->grp_unscalarizable_region
1177       && AGGREGATE_TYPE_P (TREE_TYPE (lhs))
1178       /* FIXME: Turn the following line into an assert after PR 40058 is
1179          fixed.  */
1180       && lacc->size == racc->size
1181       && useless_type_conversion_p (lacc->type, racc->type))
1182     {
1183       struct assign_link *link;
1184
1185       link = (struct assign_link *) pool_alloc (link_pool);
1186       memset (link, 0, sizeof (struct assign_link));
1187
1188       link->lacc = lacc;
1189       link->racc = racc;
1190
1191       add_link_to_rhs (racc, link);
1192     }
1193
1194   return lacc || racc;
1195 }
1196
1197 /* Callback of walk_stmt_load_store_addr_ops visit_addr used to determine
1198    GIMPLE_ASM operands with memory constrains which cannot be scalarized.  */
1199
1200 static bool
1201 asm_visit_addr (gimple stmt ATTRIBUTE_UNUSED, tree op,
1202                 void *data ATTRIBUTE_UNUSED)
1203 {
1204   op = get_base_address (op);
1205   if (op
1206       && DECL_P (op))
1207     disqualify_candidate (op, "Non-scalarizable GIMPLE_ASM operand.");
1208
1209   return false;
1210 }
1211
1212 /* Return true iff callsite CALL has at least as many actual arguments as there
1213    are formal parameters of the function currently processed by IPA-SRA.  */
1214
1215 static inline bool
1216 callsite_has_enough_arguments_p (gimple call)
1217 {
1218   return gimple_call_num_args (call) >= (unsigned) func_param_count;
1219 }
1220
1221 /* Scan function and look for interesting expressions and create access
1222    structures for them.  Return true iff any access is created.  */
1223
1224 static bool
1225 scan_function (void)
1226 {
1227   basic_block bb;
1228   bool ret = false;
1229
1230   FOR_EACH_BB (bb)
1231     {
1232       gimple_stmt_iterator gsi;
1233       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1234         {
1235           gimple stmt = gsi_stmt (gsi);
1236           tree t;
1237           unsigned i;
1238
1239           if (final_bbs && stmt_can_throw_external (stmt))
1240             bitmap_set_bit (final_bbs, bb->index);
1241           switch (gimple_code (stmt))
1242             {
1243             case GIMPLE_RETURN:
1244               t = gimple_return_retval (stmt);
1245               if (t != NULL_TREE)
1246                 ret |= build_access_from_expr (t, stmt, false);
1247               if (final_bbs)
1248                 bitmap_set_bit (final_bbs, bb->index);
1249               break;
1250
1251             case GIMPLE_ASSIGN:
1252               ret |= build_accesses_from_assign (stmt);
1253               break;
1254
1255             case GIMPLE_CALL:
1256               for (i = 0; i < gimple_call_num_args (stmt); i++)
1257                 ret |= build_access_from_expr (gimple_call_arg (stmt, i),
1258                                                stmt, false);
1259
1260               if (sra_mode == SRA_MODE_EARLY_IPA)
1261                 {
1262                   tree dest = gimple_call_fndecl (stmt);
1263                   int flags = gimple_call_flags (stmt);
1264
1265                   if (dest)
1266                     {
1267                       if (DECL_BUILT_IN_CLASS (dest) == BUILT_IN_NORMAL
1268                           && DECL_FUNCTION_CODE (dest) == BUILT_IN_APPLY_ARGS)
1269                         encountered_apply_args = true;
1270                       if (cgraph_get_node (dest)
1271                           == cgraph_get_node (current_function_decl))
1272                         {
1273                           encountered_recursive_call = true;
1274                           if (!callsite_has_enough_arguments_p (stmt))
1275                             encountered_unchangable_recursive_call = true;
1276                         }
1277                     }
1278
1279                   if (final_bbs
1280                       && (flags & (ECF_CONST | ECF_PURE)) == 0)
1281                     bitmap_set_bit (final_bbs, bb->index);
1282                 }
1283
1284               t = gimple_call_lhs (stmt);
1285               if (t && !disqualify_ops_if_throwing_stmt (stmt, t, NULL))
1286                 ret |= build_access_from_expr (t, stmt, true);
1287               break;
1288
1289             case GIMPLE_ASM:
1290               walk_stmt_load_store_addr_ops (stmt, NULL, NULL, NULL,
1291                                              asm_visit_addr);
1292               if (final_bbs)
1293                 bitmap_set_bit (final_bbs, bb->index);
1294
1295               for (i = 0; i < gimple_asm_ninputs (stmt); i++)
1296                 {
1297                   t = TREE_VALUE (gimple_asm_input_op (stmt, i));
1298                   ret |= build_access_from_expr (t, stmt, false);
1299                 }
1300               for (i = 0; i < gimple_asm_noutputs (stmt); i++)
1301                 {
1302                   t = TREE_VALUE (gimple_asm_output_op (stmt, i));
1303                   ret |= build_access_from_expr (t, stmt, true);
1304                 }
1305               break;
1306
1307             default:
1308               break;
1309             }
1310         }
1311     }
1312
1313   return ret;
1314 }
1315
1316 /* Helper of QSORT function. There are pointers to accesses in the array.  An
1317    access is considered smaller than another if it has smaller offset or if the
1318    offsets are the same but is size is bigger. */
1319
1320 static int
1321 compare_access_positions (const void *a, const void *b)
1322 {
1323   const access_p *fp1 = (const access_p *) a;
1324   const access_p *fp2 = (const access_p *) b;
1325   const access_p f1 = *fp1;
1326   const access_p f2 = *fp2;
1327
1328   if (f1->offset != f2->offset)
1329     return f1->offset < f2->offset ? -1 : 1;
1330
1331   if (f1->size == f2->size)
1332     {
1333       if (f1->type == f2->type)
1334         return 0;
1335       /* Put any non-aggregate type before any aggregate type.  */
1336       else if (!is_gimple_reg_type (f1->type)
1337           && is_gimple_reg_type (f2->type))
1338         return 1;
1339       else if (is_gimple_reg_type (f1->type)
1340                && !is_gimple_reg_type (f2->type))
1341         return -1;
1342       /* Put any complex or vector type before any other scalar type.  */
1343       else if (TREE_CODE (f1->type) != COMPLEX_TYPE
1344                && TREE_CODE (f1->type) != VECTOR_TYPE
1345                && (TREE_CODE (f2->type) == COMPLEX_TYPE
1346                    || TREE_CODE (f2->type) == VECTOR_TYPE))
1347         return 1;
1348       else if ((TREE_CODE (f1->type) == COMPLEX_TYPE
1349                 || TREE_CODE (f1->type) == VECTOR_TYPE)
1350                && TREE_CODE (f2->type) != COMPLEX_TYPE
1351                && TREE_CODE (f2->type) != VECTOR_TYPE)
1352         return -1;
1353       /* Put the integral type with the bigger precision first.  */
1354       else if (INTEGRAL_TYPE_P (f1->type)
1355                && INTEGRAL_TYPE_P (f2->type))
1356         return TYPE_PRECISION (f2->type) - TYPE_PRECISION (f1->type);
1357       /* Put any integral type with non-full precision last.  */
1358       else if (INTEGRAL_TYPE_P (f1->type)
1359                && (TREE_INT_CST_LOW (TYPE_SIZE (f1->type))
1360                    != TYPE_PRECISION (f1->type)))
1361         return 1;
1362       else if (INTEGRAL_TYPE_P (f2->type)
1363                && (TREE_INT_CST_LOW (TYPE_SIZE (f2->type))
1364                    != TYPE_PRECISION (f2->type)))
1365         return -1;
1366       /* Stabilize the sort.  */
1367       return TYPE_UID (f1->type) - TYPE_UID (f2->type);
1368     }
1369
1370   /* We want the bigger accesses first, thus the opposite operator in the next
1371      line: */
1372   return f1->size > f2->size ? -1 : 1;
1373 }
1374
1375
1376 /* Append a name of the declaration to the name obstack.  A helper function for
1377    make_fancy_name.  */
1378
1379 static void
1380 make_fancy_decl_name (tree decl)
1381 {
1382   char buffer[32];
1383
1384   tree name = DECL_NAME (decl);
1385   if (name)
1386     obstack_grow (&name_obstack, IDENTIFIER_POINTER (name),
1387                   IDENTIFIER_LENGTH (name));
1388   else
1389     {
1390       sprintf (buffer, "D%u", DECL_UID (decl));
1391       obstack_grow (&name_obstack, buffer, strlen (buffer));
1392     }
1393 }
1394
1395 /* Helper for make_fancy_name.  */
1396
1397 static void
1398 make_fancy_name_1 (tree expr)
1399 {
1400   char buffer[32];
1401   tree index;
1402
1403   if (DECL_P (expr))
1404     {
1405       make_fancy_decl_name (expr);
1406       return;
1407     }
1408
1409   switch (TREE_CODE (expr))
1410     {
1411     case COMPONENT_REF:
1412       make_fancy_name_1 (TREE_OPERAND (expr, 0));
1413       obstack_1grow (&name_obstack, '$');
1414       make_fancy_decl_name (TREE_OPERAND (expr, 1));
1415       break;
1416
1417     case ARRAY_REF:
1418       make_fancy_name_1 (TREE_OPERAND (expr, 0));
1419       obstack_1grow (&name_obstack, '$');
1420       /* Arrays with only one element may not have a constant as their
1421          index. */
1422       index = TREE_OPERAND (expr, 1);
1423       if (TREE_CODE (index) != INTEGER_CST)
1424         break;
1425       sprintf (buffer, HOST_WIDE_INT_PRINT_DEC, TREE_INT_CST_LOW (index));
1426       obstack_grow (&name_obstack, buffer, strlen (buffer));
1427       break;
1428
1429     case ADDR_EXPR:
1430       make_fancy_name_1 (TREE_OPERAND (expr, 0));
1431       break;
1432
1433     case MEM_REF:
1434       make_fancy_name_1 (TREE_OPERAND (expr, 0));
1435       if (!integer_zerop (TREE_OPERAND (expr, 1)))
1436         {
1437           obstack_1grow (&name_obstack, '$');
1438           sprintf (buffer, HOST_WIDE_INT_PRINT_DEC,
1439                    TREE_INT_CST_LOW (TREE_OPERAND (expr, 1)));
1440           obstack_grow (&name_obstack, buffer, strlen (buffer));
1441         }
1442       break;
1443
1444     case BIT_FIELD_REF:
1445     case REALPART_EXPR:
1446     case IMAGPART_EXPR:
1447       gcc_unreachable ();       /* we treat these as scalars.  */
1448       break;
1449     default:
1450       break;
1451     }
1452 }
1453
1454 /* Create a human readable name for replacement variable of ACCESS.  */
1455
1456 static char *
1457 make_fancy_name (tree expr)
1458 {
1459   make_fancy_name_1 (expr);
1460   obstack_1grow (&name_obstack, '\0');
1461   return XOBFINISH (&name_obstack, char *);
1462 }
1463
1464 /* Construct a MEM_REF that would reference a part of aggregate BASE of type
1465    EXP_TYPE at the given OFFSET.  If BASE is something for which
1466    get_addr_base_and_unit_offset returns NULL, gsi must be non-NULL and is used
1467    to insert new statements either before or below the current one as specified
1468    by INSERT_AFTER.  This function is not capable of handling bitfields.  */
1469
1470 tree
1471 build_ref_for_offset (location_t loc, tree base, HOST_WIDE_INT offset,
1472                       tree exp_type, gimple_stmt_iterator *gsi,
1473                       bool insert_after)
1474 {
1475   tree prev_base = base;
1476   tree off;
1477   HOST_WIDE_INT base_offset;
1478   unsigned HOST_WIDE_INT misalign;
1479   unsigned int align;
1480
1481   gcc_checking_assert (offset % BITS_PER_UNIT == 0);
1482
1483   base = get_addr_base_and_unit_offset (base, &base_offset);
1484
1485   /* get_addr_base_and_unit_offset returns NULL for references with a variable
1486      offset such as array[var_index].  */
1487   if (!base)
1488     {
1489       gimple stmt;
1490       tree tmp, addr;
1491
1492       gcc_checking_assert (gsi);
1493       tmp = create_tmp_reg (build_pointer_type (TREE_TYPE (prev_base)), NULL);
1494       add_referenced_var (tmp);
1495       tmp = make_ssa_name (tmp, NULL);
1496       addr = build_fold_addr_expr (unshare_expr (prev_base));
1497       STRIP_USELESS_TYPE_CONVERSION (addr);
1498       stmt = gimple_build_assign (tmp, addr);
1499       gimple_set_location (stmt, loc);
1500       SSA_NAME_DEF_STMT (tmp) = stmt;
1501       if (insert_after)
1502         gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
1503       else
1504         gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
1505       update_stmt (stmt);
1506
1507       off = build_int_cst (reference_alias_ptr_type (prev_base),
1508                            offset / BITS_PER_UNIT);
1509       base = tmp;
1510     }
1511   else if (TREE_CODE (base) == MEM_REF)
1512     {
1513       off = build_int_cst (TREE_TYPE (TREE_OPERAND (base, 1)),
1514                            base_offset + offset / BITS_PER_UNIT);
1515       off = int_const_binop (PLUS_EXPR, TREE_OPERAND (base, 1), off);
1516       base = unshare_expr (TREE_OPERAND (base, 0));
1517     }
1518   else
1519     {
1520       off = build_int_cst (reference_alias_ptr_type (base),
1521                            base_offset + offset / BITS_PER_UNIT);
1522       base = build_fold_addr_expr (unshare_expr (base));
1523     }
1524
1525   /* If prev_base were always an originally performed access
1526      we can extract more optimistic alignment information
1527      by looking at the access mode.  That would constrain the
1528      alignment of base + base_offset which we would need to
1529      adjust according to offset.
1530      ???  But it is not at all clear that prev_base is an access
1531      that was in the IL that way, so be conservative for now.  */
1532   align = get_pointer_alignment_1 (base, &misalign);
1533   misalign += (double_int_sext (tree_to_double_int (off),
1534                                 TYPE_PRECISION (TREE_TYPE (off))).low
1535                * BITS_PER_UNIT);
1536   misalign = misalign & (align - 1);
1537   if (misalign != 0)
1538     align = (misalign & -misalign);
1539   if (align < TYPE_ALIGN (exp_type))
1540     exp_type = build_aligned_type (exp_type, align);
1541
1542   return fold_build2_loc (loc, MEM_REF, exp_type, base, off);
1543 }
1544
1545 DEF_VEC_ALLOC_P_STACK (tree);
1546 #define VEC_tree_stack_alloc(alloc) VEC_stack_alloc (tree, alloc)
1547
1548 /* Construct a memory reference to a part of an aggregate BASE at the given
1549    OFFSET and of the type of MODEL.  In case this is a chain of references
1550    to component, the function will replicate the chain of COMPONENT_REFs of
1551    the expression of MODEL to access it.  GSI and INSERT_AFTER have the same
1552    meaning as in build_ref_for_offset.  */
1553
1554 static tree
1555 build_ref_for_model (location_t loc, tree base, HOST_WIDE_INT offset,
1556                      struct access *model, gimple_stmt_iterator *gsi,
1557                      bool insert_after)
1558 {
1559   tree type = model->type, t;
1560   VEC(tree,stack) *cr_stack = NULL;
1561
1562   if (TREE_CODE (model->expr) == COMPONENT_REF)
1563     {
1564       tree expr = model->expr;
1565
1566       /* Create a stack of the COMPONENT_REFs so later we can walk them in
1567          order from inner to outer.  */
1568       cr_stack = VEC_alloc (tree, stack, 6);
1569
1570       do {
1571         tree field = TREE_OPERAND (expr, 1);
1572         tree cr_offset = component_ref_field_offset (expr);
1573         HOST_WIDE_INT bit_pos
1574           = tree_low_cst (cr_offset, 1) * BITS_PER_UNIT
1575               + TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (field));
1576
1577         /* We can be called with a model different from the one associated
1578            with BASE so we need to avoid going up the chain too far.  */
1579         if (offset - bit_pos < 0)
1580           break;
1581
1582         offset -= bit_pos;
1583         VEC_safe_push (tree, stack, cr_stack, expr);
1584
1585         expr = TREE_OPERAND (expr, 0);
1586         type = TREE_TYPE (expr);
1587       } while (TREE_CODE (expr) == COMPONENT_REF);
1588     }
1589
1590   t = build_ref_for_offset (loc, base, offset, type, gsi, insert_after);
1591
1592   if (TREE_CODE (model->expr) == COMPONENT_REF)
1593     {
1594       unsigned i;
1595       tree expr;
1596
1597       /* Now replicate the chain of COMPONENT_REFs from inner to outer.  */
1598       FOR_EACH_VEC_ELT_REVERSE (tree, cr_stack, i, expr)
1599         {
1600           tree field = TREE_OPERAND (expr, 1);
1601           t = fold_build3_loc (loc, COMPONENT_REF, TREE_TYPE (field), t, field,
1602                                TREE_OPERAND (expr, 2));
1603         }
1604
1605       VEC_free (tree, stack, cr_stack);
1606     }
1607
1608   return t;
1609 }
1610
1611 /* Construct a memory reference consisting of component_refs and array_refs to
1612    a part of an aggregate *RES (which is of type TYPE).  The requested part
1613    should have type EXP_TYPE at be the given OFFSET.  This function might not
1614    succeed, it returns true when it does and only then *RES points to something
1615    meaningful.  This function should be used only to build expressions that we
1616    might need to present to user (e.g. in warnings).  In all other situations,
1617    build_ref_for_model or build_ref_for_offset should be used instead.  */
1618
1619 static bool
1620 build_user_friendly_ref_for_offset (tree *res, tree type, HOST_WIDE_INT offset,
1621                                     tree exp_type)
1622 {
1623   while (1)
1624     {
1625       tree fld;
1626       tree tr_size, index, minidx;
1627       HOST_WIDE_INT el_size;
1628
1629       if (offset == 0 && exp_type
1630           && types_compatible_p (exp_type, type))
1631         return true;
1632
1633       switch (TREE_CODE (type))
1634         {
1635         case UNION_TYPE:
1636         case QUAL_UNION_TYPE:
1637         case RECORD_TYPE:
1638           for (fld = TYPE_FIELDS (type); fld; fld = DECL_CHAIN (fld))
1639             {
1640               HOST_WIDE_INT pos, size;
1641               tree expr, *expr_ptr;
1642
1643               if (TREE_CODE (fld) != FIELD_DECL)
1644                 continue;
1645
1646               pos = int_bit_position (fld);
1647               gcc_assert (TREE_CODE (type) == RECORD_TYPE || pos == 0);
1648               tr_size = DECL_SIZE (fld);
1649               if (!tr_size || !host_integerp (tr_size, 1))
1650                 continue;
1651               size = tree_low_cst (tr_size, 1);
1652               if (size == 0)
1653                 {
1654                   if (pos != offset)
1655                     continue;
1656                 }
1657               else if (pos > offset || (pos + size) <= offset)
1658                 continue;
1659
1660               expr = build3 (COMPONENT_REF, TREE_TYPE (fld), *res, fld,
1661                              NULL_TREE);
1662               expr_ptr = &expr;
1663               if (build_user_friendly_ref_for_offset (expr_ptr, TREE_TYPE (fld),
1664                                                       offset - pos, exp_type))
1665                 {
1666                   *res = expr;
1667                   return true;
1668                 }
1669             }
1670           return false;
1671
1672         case ARRAY_TYPE:
1673           tr_size = TYPE_SIZE (TREE_TYPE (type));
1674           if (!tr_size || !host_integerp (tr_size, 1))
1675             return false;
1676           el_size = tree_low_cst (tr_size, 1);
1677
1678           minidx = TYPE_MIN_VALUE (TYPE_DOMAIN (type));
1679           if (TREE_CODE (minidx) != INTEGER_CST || el_size == 0)
1680             return false;
1681           index = build_int_cst (TYPE_DOMAIN (type), offset / el_size);
1682           if (!integer_zerop (minidx))
1683             index = int_const_binop (PLUS_EXPR, index, minidx);
1684           *res = build4 (ARRAY_REF, TREE_TYPE (type), *res, index,
1685                          NULL_TREE, NULL_TREE);
1686           offset = offset % el_size;
1687           type = TREE_TYPE (type);
1688           break;
1689
1690         default:
1691           if (offset != 0)
1692             return false;
1693
1694           if (exp_type)
1695             return false;
1696           else
1697             return true;
1698         }
1699     }
1700 }
1701
1702 /* Return true iff TYPE is stdarg va_list type.  */
1703
1704 static inline bool
1705 is_va_list_type (tree type)
1706 {
1707   return TYPE_MAIN_VARIANT (type) == TYPE_MAIN_VARIANT (va_list_type_node);
1708 }
1709
1710 /* Print message to dump file why a variable was rejected. */
1711
1712 static void
1713 reject (tree var, const char *msg)
1714 {
1715   if (dump_file && (dump_flags & TDF_DETAILS))
1716     {
1717       fprintf (dump_file, "Rejected (%d): %s: ", DECL_UID (var), msg);
1718       print_generic_expr (dump_file, var, 0);
1719       fprintf (dump_file, "\n");
1720     }
1721 }
1722
1723 /* The very first phase of intraprocedural SRA.  It marks in candidate_bitmap
1724    those with type which is suitable for scalarization.  */
1725
1726 static bool
1727 find_var_candidates (void)
1728 {
1729   tree var, type;
1730   referenced_var_iterator rvi;
1731   bool ret = false;
1732   const char *msg;
1733
1734   FOR_EACH_REFERENCED_VAR (cfun, var, rvi)
1735     {
1736       if (TREE_CODE (var) != VAR_DECL && TREE_CODE (var) != PARM_DECL)
1737         continue;
1738       type = TREE_TYPE (var);
1739
1740       if (!AGGREGATE_TYPE_P (type)) 
1741         {
1742           reject (var, "not aggregate");
1743           continue;
1744         }
1745       if (needs_to_live_in_memory (var))
1746         {
1747           reject (var, "needs to live in memory");
1748           continue;
1749         }
1750       if (TREE_THIS_VOLATILE (var))
1751         {
1752           reject (var, "is volatile");
1753           continue;
1754         }
1755       if (!COMPLETE_TYPE_P (type))
1756         {
1757           reject (var, "has incomplete type");
1758           continue;
1759         }
1760       if (!host_integerp (TYPE_SIZE (type), 1))
1761         {
1762           reject (var, "type size not fixed");
1763           continue;
1764         }
1765       if (tree_low_cst (TYPE_SIZE (type), 1) == 0)
1766         {
1767           reject (var, "type size is zero");
1768           continue;
1769         }
1770       if (type_internals_preclude_sra_p (type, &msg))
1771         {
1772           reject (var, msg);
1773           continue;
1774         }
1775       if (/* Fix for PR 41089.  tree-stdarg.c needs to have va_lists intact but
1776               we also want to schedule it rather late.  Thus we ignore it in
1777               the early pass. */
1778           (sra_mode == SRA_MODE_EARLY_INTRA
1779               && is_va_list_type (type)))
1780         {
1781           reject (var, "is va_list");
1782           continue;
1783         }
1784
1785       bitmap_set_bit (candidate_bitmap, DECL_UID (var));
1786
1787       if (dump_file && (dump_flags & TDF_DETAILS))
1788         {
1789           fprintf (dump_file, "Candidate (%d): ", DECL_UID (var));
1790           print_generic_expr (dump_file, var, 0);
1791           fprintf (dump_file, "\n");
1792         }
1793       ret = true;
1794     }
1795
1796   return ret;
1797 }
1798
1799 /* Sort all accesses for the given variable, check for partial overlaps and
1800    return NULL if there are any.  If there are none, pick a representative for
1801    each combination of offset and size and create a linked list out of them.
1802    Return the pointer to the first representative and make sure it is the first
1803    one in the vector of accesses.  */
1804
1805 static struct access *
1806 sort_and_splice_var_accesses (tree var)
1807 {
1808   int i, j, access_count;
1809   struct access *res, **prev_acc_ptr = &res;
1810   VEC (access_p, heap) *access_vec;
1811   bool first = true;
1812   HOST_WIDE_INT low = -1, high = 0;
1813
1814   access_vec = get_base_access_vector (var);
1815   if (!access_vec)
1816     return NULL;
1817   access_count = VEC_length (access_p, access_vec);
1818
1819   /* Sort by <OFFSET, SIZE>.  */
1820   VEC_qsort (access_p, access_vec, compare_access_positions);
1821
1822   i = 0;
1823   while (i < access_count)
1824     {
1825       struct access *access = VEC_index (access_p, access_vec, i);
1826       bool grp_write = access->write;
1827       bool grp_read = !access->write;
1828       bool grp_scalar_write = access->write
1829         && is_gimple_reg_type (access->type);
1830       bool grp_scalar_read = !access->write
1831         && is_gimple_reg_type (access->type);
1832       bool grp_assignment_read = access->grp_assignment_read;
1833       bool grp_assignment_write = access->grp_assignment_write;
1834       bool multiple_scalar_reads = false;
1835       bool total_scalarization = access->grp_total_scalarization;
1836       bool grp_partial_lhs = access->grp_partial_lhs;
1837       bool first_scalar = is_gimple_reg_type (access->type);
1838       bool unscalarizable_region = access->grp_unscalarizable_region;
1839
1840       if (first || access->offset >= high)
1841         {
1842           first = false;
1843           low = access->offset;
1844           high = access->offset + access->size;
1845         }
1846       else if (access->offset > low && access->offset + access->size > high)
1847         return NULL;
1848       else
1849         gcc_assert (access->offset >= low
1850                     && access->offset + access->size <= high);
1851
1852       j = i + 1;
1853       while (j < access_count)
1854         {
1855           struct access *ac2 = VEC_index (access_p, access_vec, j);
1856           if (ac2->offset != access->offset || ac2->size != access->size)
1857             break;
1858           if (ac2->write)
1859             {
1860               grp_write = true;
1861               grp_scalar_write = (grp_scalar_write
1862                                   || is_gimple_reg_type (ac2->type));
1863             }
1864           else
1865             {
1866               grp_read = true;
1867               if (is_gimple_reg_type (ac2->type))
1868                 {
1869                   if (grp_scalar_read)
1870                     multiple_scalar_reads = true;
1871                   else
1872                     grp_scalar_read = true;
1873                 }
1874             }
1875           grp_assignment_read |= ac2->grp_assignment_read;
1876           grp_assignment_write |= ac2->grp_assignment_write;
1877           grp_partial_lhs |= ac2->grp_partial_lhs;
1878           unscalarizable_region |= ac2->grp_unscalarizable_region;
1879           total_scalarization |= ac2->grp_total_scalarization;
1880           relink_to_new_repr (access, ac2);
1881
1882           /* If there are both aggregate-type and scalar-type accesses with
1883              this combination of size and offset, the comparison function
1884              should have put the scalars first.  */
1885           gcc_assert (first_scalar || !is_gimple_reg_type (ac2->type));
1886           ac2->group_representative = access;
1887           j++;
1888         }
1889
1890       i = j;
1891
1892       access->group_representative = access;
1893       access->grp_write = grp_write;
1894       access->grp_read = grp_read;
1895       access->grp_scalar_read = grp_scalar_read;
1896       access->grp_scalar_write = grp_scalar_write;
1897       access->grp_assignment_read = grp_assignment_read;
1898       access->grp_assignment_write = grp_assignment_write;
1899       access->grp_hint = multiple_scalar_reads || total_scalarization;
1900       access->grp_total_scalarization = total_scalarization;
1901       access->grp_partial_lhs = grp_partial_lhs;
1902       access->grp_unscalarizable_region = unscalarizable_region;
1903       if (access->first_link)
1904         add_access_to_work_queue (access);
1905
1906       *prev_acc_ptr = access;
1907       prev_acc_ptr = &access->next_grp;
1908     }
1909
1910   gcc_assert (res == VEC_index (access_p, access_vec, 0));
1911   return res;
1912 }
1913
1914 /* Create a variable for the given ACCESS which determines the type, name and a
1915    few other properties.  Return the variable declaration and store it also to
1916    ACCESS->replacement.  */
1917
1918 static tree
1919 create_access_replacement (struct access *access, bool rename)
1920 {
1921   tree repl;
1922
1923   repl = create_tmp_var (access->type, "SR");
1924   add_referenced_var (repl);
1925   if (rename)
1926     mark_sym_for_renaming (repl);
1927
1928   if (!access->grp_partial_lhs
1929       && (TREE_CODE (access->type) == COMPLEX_TYPE
1930           || TREE_CODE (access->type) == VECTOR_TYPE))
1931     DECL_GIMPLE_REG_P (repl) = 1;
1932
1933   DECL_SOURCE_LOCATION (repl) = DECL_SOURCE_LOCATION (access->base);
1934   DECL_ARTIFICIAL (repl) = 1;
1935   DECL_IGNORED_P (repl) = DECL_IGNORED_P (access->base);
1936
1937   if (DECL_NAME (access->base)
1938       && !DECL_IGNORED_P (access->base)
1939       && !DECL_ARTIFICIAL (access->base))
1940     {
1941       char *pretty_name = make_fancy_name (access->expr);
1942       tree debug_expr = unshare_expr (access->expr), d;
1943
1944       DECL_NAME (repl) = get_identifier (pretty_name);
1945       obstack_free (&name_obstack, pretty_name);
1946
1947       /* Get rid of any SSA_NAMEs embedded in debug_expr,
1948          as DECL_DEBUG_EXPR isn't considered when looking for still
1949          used SSA_NAMEs and thus they could be freed.  All debug info
1950          generation cares is whether something is constant or variable
1951          and that get_ref_base_and_extent works properly on the
1952          expression.  */
1953       for (d = debug_expr; handled_component_p (d); d = TREE_OPERAND (d, 0))
1954         switch (TREE_CODE (d))
1955           {
1956           case ARRAY_REF:
1957           case ARRAY_RANGE_REF:
1958             if (TREE_OPERAND (d, 1)
1959                 && TREE_CODE (TREE_OPERAND (d, 1)) == SSA_NAME)
1960               TREE_OPERAND (d, 1) = SSA_NAME_VAR (TREE_OPERAND (d, 1));
1961             if (TREE_OPERAND (d, 3)
1962                 && TREE_CODE (TREE_OPERAND (d, 3)) == SSA_NAME)
1963               TREE_OPERAND (d, 3) = SSA_NAME_VAR (TREE_OPERAND (d, 3));
1964             /* FALLTHRU */
1965           case COMPONENT_REF:
1966             if (TREE_OPERAND (d, 2)
1967                 && TREE_CODE (TREE_OPERAND (d, 2)) == SSA_NAME)
1968               TREE_OPERAND (d, 2) = SSA_NAME_VAR (TREE_OPERAND (d, 2));
1969             break;
1970           default:
1971             break;
1972           }
1973       SET_DECL_DEBUG_EXPR (repl, debug_expr);
1974       DECL_DEBUG_EXPR_IS_FROM (repl) = 1;
1975       if (access->grp_no_warning)
1976         TREE_NO_WARNING (repl) = 1;
1977       else
1978         TREE_NO_WARNING (repl) = TREE_NO_WARNING (access->base);
1979     }
1980   else
1981     TREE_NO_WARNING (repl) = 1;
1982
1983   if (dump_file)
1984     {
1985       fprintf (dump_file, "Created a replacement for ");
1986       print_generic_expr (dump_file, access->base, 0);
1987       fprintf (dump_file, " offset: %u, size: %u: ",
1988                (unsigned) access->offset, (unsigned) access->size);
1989       print_generic_expr (dump_file, repl, 0);
1990       fprintf (dump_file, "\n");
1991     }
1992   sra_stats.replacements++;
1993
1994   return repl;
1995 }
1996
1997 /* Return ACCESS scalar replacement, create it if it does not exist yet.  */
1998
1999 static inline tree
2000 get_access_replacement (struct access *access)
2001 {
2002   gcc_assert (access->grp_to_be_replaced);
2003
2004   if (!access->replacement_decl)
2005     access->replacement_decl = create_access_replacement (access, true);
2006   return access->replacement_decl;
2007 }
2008
2009 /* Return ACCESS scalar replacement, create it if it does not exist yet but do
2010    not mark it for renaming.  */
2011
2012 static inline tree
2013 get_unrenamed_access_replacement (struct access *access)
2014 {
2015   gcc_assert (!access->grp_to_be_replaced);
2016
2017   if (!access->replacement_decl)
2018     access->replacement_decl = create_access_replacement (access, false);
2019   return access->replacement_decl;
2020 }
2021
2022
2023 /* Build a subtree of accesses rooted in *ACCESS, and move the pointer in the
2024    linked list along the way.  Stop when *ACCESS is NULL or the access pointed
2025    to it is not "within" the root.  Return false iff some accesses partially
2026    overlap.  */
2027
2028 static bool
2029 build_access_subtree (struct access **access)
2030 {
2031   struct access *root = *access, *last_child = NULL;
2032   HOST_WIDE_INT limit = root->offset + root->size;
2033
2034   *access = (*access)->next_grp;
2035   while  (*access && (*access)->offset + (*access)->size <= limit)
2036     {
2037       if (!last_child)
2038         root->first_child = *access;
2039       else
2040         last_child->next_sibling = *access;
2041       last_child = *access;
2042
2043       if (!build_access_subtree (access))
2044         return false;
2045     }
2046
2047   if (*access && (*access)->offset < limit)
2048     return false;
2049
2050   return true;
2051 }
2052
2053 /* Build a tree of access representatives, ACCESS is the pointer to the first
2054    one, others are linked in a list by the next_grp field.  Return false iff
2055    some accesses partially overlap.  */
2056
2057 static bool
2058 build_access_trees (struct access *access)
2059 {
2060   while (access)
2061     {
2062       struct access *root = access;
2063
2064       if (!build_access_subtree (&access))
2065         return false;
2066       root->next_grp = access;
2067     }
2068   return true;
2069 }
2070
2071 /* Return true if expr contains some ARRAY_REFs into a variable bounded
2072    array.  */
2073
2074 static bool
2075 expr_with_var_bounded_array_refs_p (tree expr)
2076 {
2077   while (handled_component_p (expr))
2078     {
2079       if (TREE_CODE (expr) == ARRAY_REF
2080           && !host_integerp (array_ref_low_bound (expr), 0))
2081         return true;
2082       expr = TREE_OPERAND (expr, 0);
2083     }
2084   return false;
2085 }
2086
2087 /* Analyze the subtree of accesses rooted in ROOT, scheduling replacements when
2088    both seeming beneficial and when ALLOW_REPLACEMENTS allows it.  Also set all
2089    sorts of access flags appropriately along the way, notably always set
2090    grp_read and grp_assign_read according to MARK_READ and grp_write when
2091    MARK_WRITE is true.
2092
2093    Creating a replacement for a scalar access is considered beneficial if its
2094    grp_hint is set (this means we are either attempting total scalarization or
2095    there is more than one direct read access) or according to the following
2096    table:
2097
2098    Access written to through a scalar type (once or more times)
2099    |
2100    |    Written to in an assignment statement
2101    |    |
2102    |    |       Access read as scalar _once_
2103    |    |       |
2104    |    |       |       Read in an assignment statement
2105    |    |       |       |
2106    |    |       |       |       Scalarize       Comment
2107 -----------------------------------------------------------------------------
2108    0    0       0       0                       No access for the scalar
2109    0    0       0       1                       No access for the scalar
2110    0    0       1       0       No              Single read - won't help
2111    0    0       1       1       No              The same case
2112    0    1       0       0                       No access for the scalar
2113    0    1       0       1                       No access for the scalar
2114    0    1       1       0       Yes             s = *g; return s.i;
2115    0    1       1       1       Yes             The same case as above
2116    1    0       0       0       No              Won't help
2117    1    0       0       1       Yes             s.i = 1; *g = s;
2118    1    0       1       0       Yes             s.i = 5; g = s.i;
2119    1    0       1       1       Yes             The same case as above
2120    1    1       0       0       No              Won't help.
2121    1    1       0       1       Yes             s.i = 1; *g = s;
2122    1    1       1       0       Yes             s = *g; return s.i;
2123    1    1       1       1       Yes             Any of the above yeses  */
2124
2125 static bool
2126 analyze_access_subtree (struct access *root, struct access *parent,
2127                         bool allow_replacements)
2128 {
2129   struct access *child;
2130   HOST_WIDE_INT limit = root->offset + root->size;
2131   HOST_WIDE_INT covered_to = root->offset;
2132   bool scalar = is_gimple_reg_type (root->type);
2133   bool hole = false, sth_created = false;
2134
2135   if (parent)
2136     {
2137       if (parent->grp_read)
2138         root->grp_read = 1;
2139       if (parent->grp_assignment_read)
2140         root->grp_assignment_read = 1;
2141       if (parent->grp_write)
2142         root->grp_write = 1;
2143       if (parent->grp_assignment_write)
2144         root->grp_assignment_write = 1;
2145       if (parent->grp_total_scalarization)
2146         root->grp_total_scalarization = 1;
2147     }
2148
2149   if (root->grp_unscalarizable_region)
2150     allow_replacements = false;
2151
2152   if (allow_replacements && expr_with_var_bounded_array_refs_p (root->expr))
2153     allow_replacements = false;
2154
2155   for (child = root->first_child; child; child = child->next_sibling)
2156     {
2157       hole |= covered_to < child->offset;
2158       sth_created |= analyze_access_subtree (child, root,
2159                                              allow_replacements && !scalar);
2160
2161       root->grp_unscalarized_data |= child->grp_unscalarized_data;
2162       root->grp_total_scalarization &= child->grp_total_scalarization;
2163       if (child->grp_covered)
2164         covered_to += child->size;
2165       else
2166         hole = true;
2167     }
2168
2169   if (allow_replacements && scalar && !root->first_child
2170       && (root->grp_hint
2171           || ((root->grp_scalar_read || root->grp_assignment_read)
2172               && (root->grp_scalar_write || root->grp_assignment_write))))
2173     {
2174       bool new_integer_type;
2175       if (TREE_CODE (root->type) == ENUMERAL_TYPE)
2176         {
2177           tree rt = root->type;
2178           root->type = build_nonstandard_integer_type (TYPE_PRECISION (rt),
2179                                                        TYPE_UNSIGNED (rt));
2180           new_integer_type = true;
2181         }
2182       else
2183         new_integer_type = false;
2184
2185       if (dump_file && (dump_flags & TDF_DETAILS))
2186         {
2187           fprintf (dump_file, "Marking ");
2188           print_generic_expr (dump_file, root->base, 0);
2189           fprintf (dump_file, " offset: %u, size: %u ",
2190                    (unsigned) root->offset, (unsigned) root->size);
2191           fprintf (dump_file, " to be replaced%s.\n",
2192                    new_integer_type ? " with an integer": "");
2193         }
2194
2195       root->grp_to_be_replaced = 1;
2196       sth_created = true;
2197       hole = false;
2198     }
2199   else
2200     {
2201       if (covered_to < limit)
2202         hole = true;
2203       if (scalar)
2204         root->grp_total_scalarization = 0;
2205     }
2206
2207   if (sth_created
2208       && (!hole || root->grp_total_scalarization))
2209     {
2210       root->grp_covered = 1;
2211       return true;
2212     }
2213   if (root->grp_write || TREE_CODE (root->base) == PARM_DECL)
2214     root->grp_unscalarized_data = 1; /* not covered and written to */
2215   if (sth_created)
2216     return true;
2217   return false;
2218 }
2219
2220 /* Analyze all access trees linked by next_grp by the means of
2221    analyze_access_subtree.  */
2222 static bool
2223 analyze_access_trees (struct access *access)
2224 {
2225   bool ret = false;
2226
2227   while (access)
2228     {
2229       if (analyze_access_subtree (access, NULL, true))
2230         ret = true;
2231       access = access->next_grp;
2232     }
2233
2234   return ret;
2235 }
2236
2237 /* Return true iff a potential new child of LACC at offset OFFSET and with size
2238    SIZE would conflict with an already existing one.  If exactly such a child
2239    already exists in LACC, store a pointer to it in EXACT_MATCH.  */
2240
2241 static bool
2242 child_would_conflict_in_lacc (struct access *lacc, HOST_WIDE_INT norm_offset,
2243                               HOST_WIDE_INT size, struct access **exact_match)
2244 {
2245   struct access *child;
2246
2247   for (child = lacc->first_child; child; child = child->next_sibling)
2248     {
2249       if (child->offset == norm_offset && child->size == size)
2250         {
2251           *exact_match = child;
2252           return true;
2253         }
2254
2255       if (child->offset < norm_offset + size
2256           && child->offset + child->size > norm_offset)
2257         return true;
2258     }
2259
2260   return false;
2261 }
2262
2263 /* Create a new child access of PARENT, with all properties just like MODEL
2264    except for its offset and with its grp_write false and grp_read true.
2265    Return the new access or NULL if it cannot be created.  Note that this access
2266    is created long after all splicing and sorting, it's not located in any
2267    access vector and is automatically a representative of its group.  */
2268
2269 static struct access *
2270 create_artificial_child_access (struct access *parent, struct access *model,
2271                                 HOST_WIDE_INT new_offset)
2272 {
2273   struct access *access;
2274   struct access **child;
2275   tree expr = parent->base;
2276
2277   gcc_assert (!model->grp_unscalarizable_region);
2278
2279   access = (struct access *) pool_alloc (access_pool);
2280   memset (access, 0, sizeof (struct access));
2281   if (!build_user_friendly_ref_for_offset (&expr, TREE_TYPE (expr), new_offset,
2282                                            model->type))
2283     {
2284       access->grp_no_warning = true;
2285       expr = build_ref_for_model (EXPR_LOCATION (parent->base), parent->base,
2286                                   new_offset, model, NULL, false);
2287     }
2288
2289   access->base = parent->base;
2290   access->expr = expr;
2291   access->offset = new_offset;
2292   access->size = model->size;
2293   access->type = model->type;
2294   access->grp_write = true;
2295   access->grp_read = false;
2296
2297   child = &parent->first_child;
2298   while (*child && (*child)->offset < new_offset)
2299     child = &(*child)->next_sibling;
2300
2301   access->next_sibling = *child;
2302   *child = access;
2303
2304   return access;
2305 }
2306
2307
2308 /* Propagate all subaccesses of RACC across an assignment link to LACC. Return
2309    true if any new subaccess was created.  Additionally, if RACC is a scalar
2310    access but LACC is not, change the type of the latter, if possible.  */
2311
2312 static bool
2313 propagate_subaccesses_across_link (struct access *lacc, struct access *racc)
2314 {
2315   struct access *rchild;
2316   HOST_WIDE_INT norm_delta = lacc->offset - racc->offset;
2317   bool ret = false;
2318
2319   if (is_gimple_reg_type (lacc->type)
2320       || lacc->grp_unscalarizable_region
2321       || racc->grp_unscalarizable_region)
2322     return false;
2323
2324   if (is_gimple_reg_type (racc->type))
2325     {
2326       if (!lacc->first_child && !racc->first_child)
2327         {
2328           tree t = lacc->base;
2329
2330           lacc->type = racc->type;
2331           if (build_user_friendly_ref_for_offset (&t, TREE_TYPE (t),
2332                                                   lacc->offset, racc->type))
2333             lacc->expr = t;
2334           else
2335             {
2336               lacc->expr = build_ref_for_model (EXPR_LOCATION (lacc->base),
2337                                                 lacc->base, lacc->offset,
2338                                                 racc, NULL, false);
2339               lacc->grp_no_warning = true;
2340             }
2341         }
2342       return false;
2343     }
2344
2345   for (rchild = racc->first_child; rchild; rchild = rchild->next_sibling)
2346     {
2347       struct access *new_acc = NULL;
2348       HOST_WIDE_INT norm_offset = rchild->offset + norm_delta;
2349
2350       if (rchild->grp_unscalarizable_region)
2351         continue;
2352
2353       if (child_would_conflict_in_lacc (lacc, norm_offset, rchild->size,
2354                                         &new_acc))
2355         {
2356           if (new_acc)
2357             {
2358               rchild->grp_hint = 1;
2359               new_acc->grp_hint |= new_acc->grp_read;
2360               if (rchild->first_child)
2361                 ret |= propagate_subaccesses_across_link (new_acc, rchild);
2362             }
2363           continue;
2364         }
2365
2366       rchild->grp_hint = 1;
2367       new_acc = create_artificial_child_access (lacc, rchild, norm_offset);
2368       if (new_acc)
2369         {
2370           ret = true;
2371           if (racc->first_child)
2372             propagate_subaccesses_across_link (new_acc, rchild);
2373         }
2374     }
2375
2376   return ret;
2377 }
2378
2379 /* Propagate all subaccesses across assignment links.  */
2380
2381 static void
2382 propagate_all_subaccesses (void)
2383 {
2384   while (work_queue_head)
2385     {
2386       struct access *racc = pop_access_from_work_queue ();
2387       struct assign_link *link;
2388
2389       gcc_assert (racc->first_link);
2390
2391       for (link = racc->first_link; link; link = link->next)
2392         {
2393           struct access *lacc = link->lacc;
2394
2395           if (!bitmap_bit_p (candidate_bitmap, DECL_UID (lacc->base)))
2396             continue;
2397           lacc = lacc->group_representative;
2398           if (propagate_subaccesses_across_link (lacc, racc)
2399               && lacc->first_link)
2400             add_access_to_work_queue (lacc);
2401         }
2402     }
2403 }
2404
2405 /* Go through all accesses collected throughout the (intraprocedural) analysis
2406    stage, exclude overlapping ones, identify representatives and build trees
2407    out of them, making decisions about scalarization on the way.  Return true
2408    iff there are any to-be-scalarized variables after this stage. */
2409
2410 static bool
2411 analyze_all_variable_accesses (void)
2412 {
2413   int res = 0;
2414   bitmap tmp = BITMAP_ALLOC (NULL);
2415   bitmap_iterator bi;
2416   unsigned i, max_total_scalarization_size;
2417
2418   max_total_scalarization_size = UNITS_PER_WORD * BITS_PER_UNIT
2419     * MOVE_RATIO (optimize_function_for_speed_p (cfun));
2420
2421   EXECUTE_IF_SET_IN_BITMAP (candidate_bitmap, 0, i, bi)
2422     if (bitmap_bit_p (should_scalarize_away_bitmap, i)
2423         && !bitmap_bit_p (cannot_scalarize_away_bitmap, i))
2424       {
2425         tree var = referenced_var (i);
2426
2427         if (TREE_CODE (var) == VAR_DECL
2428             && type_consists_of_records_p (TREE_TYPE (var)))
2429           {
2430             if ((unsigned) tree_low_cst (TYPE_SIZE (TREE_TYPE (var)), 1)
2431                 <= max_total_scalarization_size)
2432               {
2433                 completely_scalarize_var (var);
2434                 if (dump_file && (dump_flags & TDF_DETAILS))
2435                   {
2436                     fprintf (dump_file, "Will attempt to totally scalarize ");
2437                     print_generic_expr (dump_file, var, 0);
2438                     fprintf (dump_file, " (UID: %u): \n", DECL_UID (var));
2439                   }
2440               }
2441             else if (dump_file && (dump_flags & TDF_DETAILS))
2442               {
2443                 fprintf (dump_file, "Too big to totally scalarize: ");
2444                 print_generic_expr (dump_file, var, 0);
2445                 fprintf (dump_file, " (UID: %u)\n", DECL_UID (var));
2446               }
2447           }
2448       }
2449
2450   bitmap_copy (tmp, candidate_bitmap);
2451   EXECUTE_IF_SET_IN_BITMAP (tmp, 0, i, bi)
2452     {
2453       tree var = referenced_var (i);
2454       struct access *access;
2455
2456       access = sort_and_splice_var_accesses (var);
2457       if (!access || !build_access_trees (access))
2458         disqualify_candidate (var,
2459                               "No or inhibitingly overlapping accesses.");
2460     }
2461
2462   propagate_all_subaccesses ();
2463
2464   bitmap_copy (tmp, candidate_bitmap);
2465   EXECUTE_IF_SET_IN_BITMAP (tmp, 0, i, bi)
2466     {
2467       tree var = referenced_var (i);
2468       struct access *access = get_first_repr_for_decl (var);
2469
2470       if (analyze_access_trees (access))
2471         {
2472           res++;
2473           if (dump_file && (dump_flags & TDF_DETAILS))
2474             {
2475               fprintf (dump_file, "\nAccess trees for ");
2476               print_generic_expr (dump_file, var, 0);
2477               fprintf (dump_file, " (UID: %u): \n", DECL_UID (var));
2478               dump_access_tree (dump_file, access);
2479               fprintf (dump_file, "\n");
2480             }
2481         }
2482       else
2483         disqualify_candidate (var, "No scalar replacements to be created.");
2484     }
2485
2486   BITMAP_FREE (tmp);
2487
2488   if (res)
2489     {
2490       statistics_counter_event (cfun, "Scalarized aggregates", res);
2491       return true;
2492     }
2493   else
2494     return false;
2495 }
2496
2497 /* Generate statements copying scalar replacements of accesses within a subtree
2498    into or out of AGG.  ACCESS, all its children, siblings and their children
2499    are to be processed.  AGG is an aggregate type expression (can be a
2500    declaration but does not have to be, it can for example also be a mem_ref or
2501    a series of handled components).  TOP_OFFSET is the offset of the processed
2502    subtree which has to be subtracted from offsets of individual accesses to
2503    get corresponding offsets for AGG.  If CHUNK_SIZE is non-null, copy only
2504    replacements in the interval <start_offset, start_offset + chunk_size>,
2505    otherwise copy all.  GSI is a statement iterator used to place the new
2506    statements.  WRITE should be true when the statements should write from AGG
2507    to the replacement and false if vice versa.  if INSERT_AFTER is true, new
2508    statements will be added after the current statement in GSI, they will be
2509    added before the statement otherwise.  */
2510
2511 static void
2512 generate_subtree_copies (struct access *access, tree agg,
2513                          HOST_WIDE_INT top_offset,
2514                          HOST_WIDE_INT start_offset, HOST_WIDE_INT chunk_size,
2515                          gimple_stmt_iterator *gsi, bool write,
2516                          bool insert_after, location_t loc)
2517 {
2518   do
2519     {
2520       if (chunk_size && access->offset >= start_offset + chunk_size)
2521         return;
2522
2523       if (access->grp_to_be_replaced
2524           && (chunk_size == 0
2525               || access->offset + access->size > start_offset))
2526         {
2527           tree expr, repl = get_access_replacement (access);
2528           gimple stmt;
2529
2530           expr = build_ref_for_model (loc, agg, access->offset - top_offset,
2531                                       access, gsi, insert_after);
2532
2533           if (write)
2534             {
2535               if (access->grp_partial_lhs)
2536                 expr = force_gimple_operand_gsi (gsi, expr, true, NULL_TREE,
2537                                                  !insert_after,
2538                                                  insert_after ? GSI_NEW_STMT
2539                                                  : GSI_SAME_STMT);
2540               stmt = gimple_build_assign (repl, expr);
2541             }
2542           else
2543             {
2544               TREE_NO_WARNING (repl) = 1;
2545               if (access->grp_partial_lhs)
2546                 repl = force_gimple_operand_gsi (gsi, repl, true, NULL_TREE,
2547                                                  !insert_after,
2548                                                  insert_after ? GSI_NEW_STMT
2549                                                  : GSI_SAME_STMT);
2550               stmt = gimple_build_assign (expr, repl);
2551             }
2552           gimple_set_location (stmt, loc);
2553
2554           if (insert_after)
2555             gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
2556           else
2557             gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
2558           update_stmt (stmt);
2559           sra_stats.subtree_copies++;
2560         }
2561
2562       if (access->first_child)
2563         generate_subtree_copies (access->first_child, agg, top_offset,
2564                                  start_offset, chunk_size, gsi,
2565                                  write, insert_after, loc);
2566
2567       access = access->next_sibling;
2568     }
2569   while (access);
2570 }
2571
2572 /* Assign zero to all scalar replacements in an access subtree.  ACCESS is the
2573    the root of the subtree to be processed.  GSI is the statement iterator used
2574    for inserting statements which are added after the current statement if
2575    INSERT_AFTER is true or before it otherwise.  */
2576
2577 static void
2578 init_subtree_with_zero (struct access *access, gimple_stmt_iterator *gsi,
2579                         bool insert_after, location_t loc)
2580
2581 {
2582   struct access *child;
2583
2584   if (access->grp_to_be_replaced)
2585     {
2586       gimple stmt;
2587
2588       stmt = gimple_build_assign (get_access_replacement (access),
2589                                   build_zero_cst (access->type));
2590       if (insert_after)
2591         gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
2592       else
2593         gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
2594       update_stmt (stmt);
2595       gimple_set_location (stmt, loc);
2596     }
2597
2598   for (child = access->first_child; child; child = child->next_sibling)
2599     init_subtree_with_zero (child, gsi, insert_after, loc);
2600 }
2601
2602 /* Search for an access representative for the given expression EXPR and
2603    return it or NULL if it cannot be found.  */
2604
2605 static struct access *
2606 get_access_for_expr (tree expr)
2607 {
2608   HOST_WIDE_INT offset, size, max_size;
2609   tree base;
2610
2611   /* FIXME: This should not be necessary but Ada produces V_C_Es with a type of
2612      a different size than the size of its argument and we need the latter
2613      one.  */
2614   if (TREE_CODE (expr) == VIEW_CONVERT_EXPR)
2615     expr = TREE_OPERAND (expr, 0);
2616
2617   base = get_ref_base_and_extent (expr, &offset, &size, &max_size);
2618   if (max_size == -1 || !DECL_P (base))
2619     return NULL;
2620
2621   if (!bitmap_bit_p (candidate_bitmap, DECL_UID (base)))
2622     return NULL;
2623
2624   return get_var_base_offset_size_access (base, offset, max_size);
2625 }
2626
2627 /* Replace the expression EXPR with a scalar replacement if there is one and
2628    generate other statements to do type conversion or subtree copying if
2629    necessary.  GSI is used to place newly created statements, WRITE is true if
2630    the expression is being written to (it is on a LHS of a statement or output
2631    in an assembly statement).  */
2632
2633 static bool
2634 sra_modify_expr (tree *expr, gimple_stmt_iterator *gsi, bool write)
2635 {
2636   location_t loc;
2637   struct access *access;
2638   tree type, bfr;
2639
2640   if (TREE_CODE (*expr) == BIT_FIELD_REF)
2641     {
2642       bfr = *expr;
2643       expr = &TREE_OPERAND (*expr, 0);
2644     }
2645   else
2646     bfr = NULL_TREE;
2647
2648   if (TREE_CODE (*expr) == REALPART_EXPR || TREE_CODE (*expr) == IMAGPART_EXPR)
2649     expr = &TREE_OPERAND (*expr, 0);
2650   access = get_access_for_expr (*expr);
2651   if (!access)
2652     return false;
2653   type = TREE_TYPE (*expr);
2654
2655   loc = gimple_location (gsi_stmt (*gsi));
2656   if (access->grp_to_be_replaced)
2657     {
2658       tree repl = get_access_replacement (access);
2659       /* If we replace a non-register typed access simply use the original
2660          access expression to extract the scalar component afterwards.
2661          This happens if scalarizing a function return value or parameter
2662          like in gcc.c-torture/execute/20041124-1.c, 20050316-1.c and
2663          gcc.c-torture/compile/20011217-1.c.
2664
2665          We also want to use this when accessing a complex or vector which can
2666          be accessed as a different type too, potentially creating a need for
2667          type conversion (see PR42196) and when scalarized unions are involved
2668          in assembler statements (see PR42398).  */
2669       if (!useless_type_conversion_p (type, access->type))
2670         {
2671           tree ref;
2672
2673           ref = build_ref_for_model (loc, access->base, access->offset, access,
2674                                      NULL, false);
2675
2676           if (write)
2677             {
2678               gimple stmt;
2679
2680               if (access->grp_partial_lhs)
2681                 ref = force_gimple_operand_gsi (gsi, ref, true, NULL_TREE,
2682                                                  false, GSI_NEW_STMT);
2683               stmt = gimple_build_assign (repl, ref);
2684               gimple_set_location (stmt, loc);
2685               gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
2686             }
2687           else
2688             {
2689               gimple stmt;
2690
2691               if (access->grp_partial_lhs)
2692                 repl = force_gimple_operand_gsi (gsi, repl, true, NULL_TREE,
2693                                                  true, GSI_SAME_STMT);
2694               stmt = gimple_build_assign (ref, repl);
2695               gimple_set_location (stmt, loc);
2696               gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
2697             }
2698         }
2699       else
2700         *expr = repl;
2701       sra_stats.exprs++;
2702     }
2703
2704   if (access->first_child)
2705     {
2706       HOST_WIDE_INT start_offset, chunk_size;
2707       if (bfr
2708           && host_integerp (TREE_OPERAND (bfr, 1), 1)
2709           && host_integerp (TREE_OPERAND (bfr, 2), 1))
2710         {
2711           chunk_size = tree_low_cst (TREE_OPERAND (bfr, 1), 1);
2712           start_offset = access->offset
2713             + tree_low_cst (TREE_OPERAND (bfr, 2), 1);
2714         }
2715       else
2716         start_offset = chunk_size = 0;
2717
2718       generate_subtree_copies (access->first_child, access->base, 0,
2719                                start_offset, chunk_size, gsi, write, write,
2720                                loc);
2721     }
2722   return true;
2723 }
2724
2725 /* Where scalar replacements of the RHS have been written to when a replacement
2726    of a LHS of an assigments cannot be direclty loaded from a replacement of
2727    the RHS. */
2728 enum unscalarized_data_handling { SRA_UDH_NONE,  /* Nothing done so far. */
2729                                   SRA_UDH_RIGHT, /* Data flushed to the RHS. */
2730                                   SRA_UDH_LEFT }; /* Data flushed to the LHS. */
2731
2732 /* Store all replacements in the access tree rooted in TOP_RACC either to their
2733    base aggregate if there are unscalarized data or directly to LHS of the
2734    statement that is pointed to by GSI otherwise.  */
2735
2736 static enum unscalarized_data_handling
2737 handle_unscalarized_data_in_subtree (struct access *top_racc,
2738                                      gimple_stmt_iterator *gsi)
2739 {
2740   if (top_racc->grp_unscalarized_data)
2741     {
2742       generate_subtree_copies (top_racc->first_child, top_racc->base, 0, 0, 0,
2743                                gsi, false, false,
2744                                gimple_location (gsi_stmt (*gsi)));
2745       return SRA_UDH_RIGHT;
2746     }
2747   else
2748     {
2749       tree lhs = gimple_assign_lhs (gsi_stmt (*gsi));
2750       generate_subtree_copies (top_racc->first_child, lhs, top_racc->offset,
2751                                0, 0, gsi, false, false,
2752                                gimple_location (gsi_stmt (*gsi)));
2753       return SRA_UDH_LEFT;
2754     }
2755 }
2756
2757
2758 /* Try to generate statements to load all sub-replacements in an access subtree
2759    formed by children of LACC from scalar replacements in the TOP_RACC subtree.
2760    If that is not possible, refresh the TOP_RACC base aggregate and load the
2761    accesses from it.  LEFT_OFFSET is the offset of the left whole subtree being
2762    copied. NEW_GSI is stmt iterator used for statement insertions after the
2763    original assignment, OLD_GSI is used to insert statements before the
2764    assignment.  *REFRESHED keeps the information whether we have needed to
2765    refresh replacements of the LHS and from which side of the assignments this
2766    takes place.  */
2767
2768 static void
2769 load_assign_lhs_subreplacements (struct access *lacc, struct access *top_racc,
2770                                  HOST_WIDE_INT left_offset,
2771                                  gimple_stmt_iterator *old_gsi,
2772                                  gimple_stmt_iterator *new_gsi,
2773                                  enum unscalarized_data_handling *refreshed)
2774 {
2775   location_t loc = gimple_location (gsi_stmt (*old_gsi));
2776   for (lacc = lacc->first_child; lacc; lacc = lacc->next_sibling)
2777     {
2778       if (lacc->grp_to_be_replaced)
2779         {
2780           struct access *racc;
2781           HOST_WIDE_INT offset = lacc->offset - left_offset + top_racc->offset;
2782           gimple stmt;
2783           tree rhs;
2784
2785           racc = find_access_in_subtree (top_racc, offset, lacc->size);
2786           if (racc && racc->grp_to_be_replaced)
2787             {
2788               rhs = get_access_replacement (racc);
2789               if (!useless_type_conversion_p (lacc->type, racc->type))
2790                 rhs = fold_build1_loc (loc, VIEW_CONVERT_EXPR, lacc->type, rhs);
2791
2792               if (racc->grp_partial_lhs && lacc->grp_partial_lhs)
2793                 rhs = force_gimple_operand_gsi (old_gsi, rhs, true, NULL_TREE,
2794                                                 true, GSI_SAME_STMT);
2795             }
2796           else
2797             {
2798               /* No suitable access on the right hand side, need to load from
2799                  the aggregate.  See if we have to update it first... */
2800               if (*refreshed == SRA_UDH_NONE)
2801                 *refreshed = handle_unscalarized_data_in_subtree (top_racc,
2802                                                                   old_gsi);
2803
2804               if (*refreshed == SRA_UDH_LEFT)
2805                 rhs = build_ref_for_model (loc, lacc->base, lacc->offset, lacc,
2806                                             new_gsi, true);
2807               else
2808                 rhs = build_ref_for_model (loc, top_racc->base, offset, lacc,
2809                                             new_gsi, true);
2810               if (lacc->grp_partial_lhs)
2811                 rhs = force_gimple_operand_gsi (new_gsi, rhs, true, NULL_TREE,
2812                                                 false, GSI_NEW_STMT);
2813             }
2814
2815           stmt = gimple_build_assign (get_access_replacement (lacc), rhs);
2816           gsi_insert_after (new_gsi, stmt, GSI_NEW_STMT);
2817           gimple_set_location (stmt, loc);
2818           update_stmt (stmt);
2819           sra_stats.subreplacements++;
2820         }
2821       else if (*refreshed == SRA_UDH_NONE
2822                && lacc->grp_read && !lacc->grp_covered)
2823         *refreshed = handle_unscalarized_data_in_subtree (top_racc,
2824                                                           old_gsi);
2825
2826       if (lacc->first_child)
2827         load_assign_lhs_subreplacements (lacc, top_racc, left_offset,
2828                                          old_gsi, new_gsi, refreshed);
2829     }
2830 }
2831
2832 /* Result code for SRA assignment modification.  */
2833 enum assignment_mod_result { SRA_AM_NONE,       /* nothing done for the stmt */
2834                              SRA_AM_MODIFIED,  /* stmt changed but not
2835                                                   removed */
2836                              SRA_AM_REMOVED };  /* stmt eliminated */
2837
2838 /* Modify assignments with a CONSTRUCTOR on their RHS.  STMT contains a pointer
2839    to the assignment and GSI is the statement iterator pointing at it.  Returns
2840    the same values as sra_modify_assign.  */
2841
2842 static enum assignment_mod_result
2843 sra_modify_constructor_assign (gimple *stmt, gimple_stmt_iterator *gsi)
2844 {
2845   tree lhs = gimple_assign_lhs (*stmt);
2846   struct access *acc;
2847   location_t loc;
2848
2849   acc = get_access_for_expr (lhs);
2850   if (!acc)
2851     return SRA_AM_NONE;
2852
2853   if (gimple_clobber_p (*stmt))
2854     {
2855       /* Remove clobbers of fully scalarized variables, otherwise
2856          do nothing.  */
2857       if (acc->grp_covered)
2858         {
2859           unlink_stmt_vdef (*stmt);
2860           gsi_remove (gsi, true);
2861           return SRA_AM_REMOVED;
2862         }
2863       else
2864         return SRA_AM_NONE;
2865     }
2866
2867   loc = gimple_location (*stmt);
2868   if (VEC_length (constructor_elt,
2869                   CONSTRUCTOR_ELTS (gimple_assign_rhs1 (*stmt))) > 0)
2870     {
2871       /* I have never seen this code path trigger but if it can happen the
2872          following should handle it gracefully.  */
2873       if (access_has_children_p (acc))
2874         generate_subtree_copies (acc->first_child, acc->base, 0, 0, 0, gsi,
2875                                  true, true, loc);
2876       return SRA_AM_MODIFIED;
2877     }
2878
2879   if (acc->grp_covered)
2880     {
2881       init_subtree_with_zero (acc, gsi, false, loc);
2882       unlink_stmt_vdef (*stmt);
2883       gsi_remove (gsi, true);
2884       return SRA_AM_REMOVED;
2885     }
2886   else
2887     {
2888       init_subtree_with_zero (acc, gsi, true, loc);
2889       return SRA_AM_MODIFIED;
2890     }
2891 }
2892
2893 /* Create and return a new suitable default definition SSA_NAME for RACC which
2894    is an access describing an uninitialized part of an aggregate that is being
2895    loaded.  */
2896
2897 static tree
2898 get_repl_default_def_ssa_name (struct access *racc)
2899 {
2900   tree repl, decl;
2901
2902   decl = get_unrenamed_access_replacement (racc);
2903
2904   repl = gimple_default_def (cfun, decl);
2905   if (!repl)
2906     {
2907       repl = make_ssa_name (decl, gimple_build_nop ());
2908       set_default_def (decl, repl);
2909     }
2910
2911   return repl;
2912 }
2913
2914 /* Return true if REF has a COMPONENT_REF with a bit-field field declaration
2915    somewhere in it.  */
2916
2917 static inline bool
2918 contains_bitfld_comp_ref_p (const_tree ref)
2919 {
2920   while (handled_component_p (ref))
2921     {
2922       if (TREE_CODE (ref) == COMPONENT_REF
2923           && DECL_BIT_FIELD (TREE_OPERAND (ref, 1)))
2924         return true;
2925       ref = TREE_OPERAND (ref, 0);
2926     }
2927
2928   return false;
2929 }
2930
2931 /* Return true if REF has an VIEW_CONVERT_EXPR or a COMPONENT_REF with a
2932    bit-field field declaration somewhere in it.  */
2933
2934 static inline bool
2935 contains_vce_or_bfcref_p (const_tree ref)
2936 {
2937   while (handled_component_p (ref))
2938     {
2939       if (TREE_CODE (ref) == VIEW_CONVERT_EXPR
2940           || (TREE_CODE (ref) == COMPONENT_REF
2941               && DECL_BIT_FIELD (TREE_OPERAND (ref, 1))))
2942         return true;
2943       ref = TREE_OPERAND (ref, 0);
2944     }
2945
2946   return false;
2947 }
2948
2949 /* Examine both sides of the assignment statement pointed to by STMT, replace
2950    them with a scalare replacement if there is one and generate copying of
2951    replacements if scalarized aggregates have been used in the assignment.  GSI
2952    is used to hold generated statements for type conversions and subtree
2953    copying.  */
2954
2955 static enum assignment_mod_result
2956 sra_modify_assign (gimple *stmt, gimple_stmt_iterator *gsi)
2957 {
2958   struct access *lacc, *racc;
2959   tree lhs, rhs;
2960   bool modify_this_stmt = false;
2961   bool force_gimple_rhs = false;
2962   location_t loc;
2963   gimple_stmt_iterator orig_gsi = *gsi;
2964
2965   if (!gimple_assign_single_p (*stmt))
2966     return SRA_AM_NONE;
2967   lhs = gimple_assign_lhs (*stmt);
2968   rhs = gimple_assign_rhs1 (*stmt);
2969
2970   if (TREE_CODE (rhs) == CONSTRUCTOR)
2971     return sra_modify_constructor_assign (stmt, gsi);
2972
2973   if (TREE_CODE (rhs) == REALPART_EXPR || TREE_CODE (lhs) == REALPART_EXPR
2974       || TREE_CODE (rhs) == IMAGPART_EXPR || TREE_CODE (lhs) == IMAGPART_EXPR
2975       || TREE_CODE (rhs) == BIT_FIELD_REF || TREE_CODE (lhs) == BIT_FIELD_REF)
2976     {
2977       modify_this_stmt = sra_modify_expr (gimple_assign_rhs1_ptr (*stmt),
2978                                           gsi, false);
2979       modify_this_stmt |= sra_modify_expr (gimple_assign_lhs_ptr (*stmt),
2980                                            gsi, true);
2981       return modify_this_stmt ? SRA_AM_MODIFIED : SRA_AM_NONE;
2982     }
2983
2984   lacc = get_access_for_expr (lhs);
2985   racc = get_access_for_expr (rhs);
2986   if (!lacc && !racc)
2987     return SRA_AM_NONE;
2988
2989   loc = gimple_location (*stmt);
2990   if (lacc && lacc->grp_to_be_replaced)
2991     {
2992       lhs = get_access_replacement (lacc);
2993       gimple_assign_set_lhs (*stmt, lhs);
2994       modify_this_stmt = true;
2995       if (lacc->grp_partial_lhs)
2996         force_gimple_rhs = true;
2997       sra_stats.exprs++;
2998     }
2999
3000   if (racc && racc->grp_to_be_replaced)
3001     {
3002       rhs = get_access_replacement (racc);
3003       modify_this_stmt = true;
3004       if (racc->grp_partial_lhs)
3005         force_gimple_rhs = true;
3006       sra_stats.exprs++;
3007     }
3008   else if (racc
3009            && !racc->grp_unscalarized_data
3010            && TREE_CODE (lhs) == SSA_NAME
3011            && !access_has_replacements_p (racc))
3012     {
3013       rhs = get_repl_default_def_ssa_name (racc);
3014       modify_this_stmt = true;
3015       sra_stats.exprs++;
3016     }
3017
3018   if (modify_this_stmt)
3019     {
3020       if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
3021         {
3022           /* If we can avoid creating a VIEW_CONVERT_EXPR do so.
3023              ???  This should move to fold_stmt which we simply should
3024              call after building a VIEW_CONVERT_EXPR here.  */
3025           if (AGGREGATE_TYPE_P (TREE_TYPE (lhs))
3026               && !contains_bitfld_comp_ref_p (lhs)
3027               && !access_has_children_p (lacc))
3028             {
3029               lhs = build_ref_for_model (loc, lhs, 0, racc, gsi, false);
3030               gimple_assign_set_lhs (*stmt, lhs);
3031             }
3032           else if (AGGREGATE_TYPE_P (TREE_TYPE (rhs))
3033                    && !contains_vce_or_bfcref_p (rhs)
3034                    && !access_has_children_p (racc))
3035             rhs = build_ref_for_model (loc, rhs, 0, lacc, gsi, false);
3036
3037           if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
3038             {
3039               rhs = fold_build1_loc (loc, VIEW_CONVERT_EXPR, TREE_TYPE (lhs),
3040                                      rhs);
3041               if (is_gimple_reg_type (TREE_TYPE (lhs))
3042                   && TREE_CODE (lhs) != SSA_NAME)
3043                 force_gimple_rhs = true;
3044             }
3045         }
3046     }
3047
3048   /* From this point on, the function deals with assignments in between
3049      aggregates when at least one has scalar reductions of some of its
3050      components.  There are three possible scenarios: Both the LHS and RHS have
3051      to-be-scalarized components, 2) only the RHS has or 3) only the LHS has.
3052
3053      In the first case, we would like to load the LHS components from RHS
3054      components whenever possible.  If that is not possible, we would like to
3055      read it directly from the RHS (after updating it by storing in it its own
3056      components).  If there are some necessary unscalarized data in the LHS,
3057      those will be loaded by the original assignment too.  If neither of these
3058      cases happen, the original statement can be removed.  Most of this is done
3059      by load_assign_lhs_subreplacements.
3060
3061      In the second case, we would like to store all RHS scalarized components
3062      directly into LHS and if they cover the aggregate completely, remove the
3063      statement too.  In the third case, we want the LHS components to be loaded
3064      directly from the RHS (DSE will remove the original statement if it
3065      becomes redundant).
3066
3067      This is a bit complex but manageable when types match and when unions do
3068      not cause confusion in a way that we cannot really load a component of LHS
3069      from the RHS or vice versa (the access representing this level can have
3070      subaccesses that are accessible only through a different union field at a
3071      higher level - different from the one used in the examined expression).
3072      Unions are fun.
3073
3074      Therefore, I specially handle a fourth case, happening when there is a
3075      specific type cast or it is impossible to locate a scalarized subaccess on
3076      the other side of the expression.  If that happens, I simply "refresh" the
3077      RHS by storing in it is scalarized components leave the original statement
3078      there to do the copying and then load the scalar replacements of the LHS.
3079      This is what the first branch does.  */
3080
3081   if (modify_this_stmt
3082       || gimple_has_volatile_ops (*stmt)
3083       || contains_vce_or_bfcref_p (rhs)
3084       || contains_vce_or_bfcref_p (lhs))
3085     {
3086       if (access_has_children_p (racc))
3087         generate_subtree_copies (racc->first_child, racc->base, 0, 0, 0,
3088                                  gsi, false, false, loc);
3089       if (access_has_children_p (lacc))
3090         generate_subtree_copies (lacc->first_child, lacc->base, 0, 0, 0,
3091                                  gsi, true, true, loc);
3092       sra_stats.separate_lhs_rhs_handling++;
3093
3094       /* This gimplification must be done after generate_subtree_copies,
3095          lest we insert the subtree copies in the middle of the gimplified
3096          sequence.  */
3097       if (force_gimple_rhs)
3098         rhs = force_gimple_operand_gsi (&orig_gsi, rhs, true, NULL_TREE,
3099                                         true, GSI_SAME_STMT);
3100       if (gimple_assign_rhs1 (*stmt) != rhs)
3101         {
3102           modify_this_stmt = true;
3103           gimple_assign_set_rhs_from_tree (&orig_gsi, rhs);
3104           gcc_assert (*stmt == gsi_stmt (orig_gsi));
3105         }
3106
3107       return modify_this_stmt ? SRA_AM_MODIFIED : SRA_AM_NONE;
3108     }
3109   else
3110     {
3111       if (access_has_children_p (lacc) && access_has_children_p (racc))
3112         {
3113           gimple_stmt_iterator orig_gsi = *gsi;
3114           enum unscalarized_data_handling refreshed;
3115
3116           if (lacc->grp_read && !lacc->grp_covered)
3117             refreshed = handle_unscalarized_data_in_subtree (racc, gsi);
3118           else
3119             refreshed = SRA_UDH_NONE;
3120
3121           load_assign_lhs_subreplacements (lacc, racc, lacc->offset,
3122                                            &orig_gsi, gsi, &refreshed);
3123           if (refreshed != SRA_UDH_RIGHT)
3124             {
3125               gsi_next (gsi);
3126               unlink_stmt_vdef (*stmt);
3127               gsi_remove (&orig_gsi, true);
3128               sra_stats.deleted++;
3129               return SRA_AM_REMOVED;
3130             }
3131         }
3132       else
3133         {
3134           if (access_has_children_p (racc)
3135               && !racc->grp_unscalarized_data)
3136             {
3137               if (dump_file)
3138                 {
3139                   fprintf (dump_file, "Removing load: ");
3140                   print_gimple_stmt (dump_file, *stmt, 0, 0);
3141                 }
3142               generate_subtree_copies (racc->first_child, lhs,
3143                                        racc->offset, 0, 0, gsi,
3144                                        false, false, loc);
3145               gcc_assert (*stmt == gsi_stmt (*gsi));
3146               unlink_stmt_vdef (*stmt);
3147               gsi_remove (gsi, true);
3148               sra_stats.deleted++;
3149               return SRA_AM_REMOVED;
3150             }
3151           /* Restore the aggregate RHS from its components so the
3152              prevailing aggregate copy does the right thing.  */
3153           if (access_has_children_p (racc))
3154             generate_subtree_copies (racc->first_child, racc->base, 0, 0, 0,
3155                                      gsi, false, false, loc);
3156           /* Re-load the components of the aggregate copy destination.
3157              But use the RHS aggregate to load from to expose more
3158              optimization opportunities.  */
3159           if (access_has_children_p (lacc))
3160             generate_subtree_copies (lacc->first_child, rhs, lacc->offset,
3161                                      0, 0, gsi, true, true, loc);
3162         }
3163
3164       return SRA_AM_NONE;
3165     }
3166 }
3167
3168 /* Traverse the function body and all modifications as decided in
3169    analyze_all_variable_accesses.  Return true iff the CFG has been
3170    changed.  */
3171
3172 static bool
3173 sra_modify_function_body (void)
3174 {
3175   bool cfg_changed = false;
3176   basic_block bb;
3177
3178   FOR_EACH_BB (bb)
3179     {
3180       gimple_stmt_iterator gsi = gsi_start_bb (bb);
3181       while (!gsi_end_p (gsi))
3182         {
3183           gimple stmt = gsi_stmt (gsi);
3184           enum assignment_mod_result assign_result;
3185           bool modified = false, deleted = false;
3186           tree *t;
3187           unsigned i;
3188
3189           switch (gimple_code (stmt))
3190             {
3191             case GIMPLE_RETURN:
3192               t = gimple_return_retval_ptr (stmt);
3193               if (*t != NULL_TREE)
3194                 modified |= sra_modify_expr (t, &gsi, false);
3195               break;
3196
3197             case GIMPLE_ASSIGN:
3198               assign_result = sra_modify_assign (&stmt, &gsi);
3199               modified |= assign_result == SRA_AM_MODIFIED;
3200               deleted = assign_result == SRA_AM_REMOVED;
3201               break;
3202
3203             case GIMPLE_CALL:
3204               /* Operands must be processed before the lhs.  */
3205               for (i = 0; i < gimple_call_num_args (stmt); i++)
3206                 {
3207                   t = gimple_call_arg_ptr (stmt, i);
3208                   modified |= sra_modify_expr (t, &gsi, false);
3209                 }
3210
3211               if (gimple_call_lhs (stmt))
3212                 {
3213                   t = gimple_call_lhs_ptr (stmt);
3214                   modified |= sra_modify_expr (t, &gsi, true);
3215                 }
3216               break;
3217
3218             case GIMPLE_ASM:
3219               for (i = 0; i < gimple_asm_ninputs (stmt); i++)
3220                 {
3221                   t = &TREE_VALUE (gimple_asm_input_op (stmt, i));
3222                   modified |= sra_modify_expr (t, &gsi, false);
3223                 }
3224               for (i = 0; i < gimple_asm_noutputs (stmt); i++)
3225                 {
3226                   t = &TREE_VALUE (gimple_asm_output_op (stmt, i));
3227                   modified |= sra_modify_expr (t, &gsi, true);
3228                 }
3229               break;
3230
3231             default:
3232               break;
3233             }
3234
3235           if (modified)
3236             {
3237               update_stmt (stmt);
3238               if (maybe_clean_eh_stmt (stmt)
3239                   && gimple_purge_dead_eh_edges (gimple_bb (stmt)))
3240                 cfg_changed = true;
3241             }
3242           if (!deleted)
3243             gsi_next (&gsi);
3244         }
3245     }
3246
3247   return cfg_changed;
3248 }
3249
3250 /* Generate statements initializing scalar replacements of parts of function
3251    parameters.  */
3252
3253 static void
3254 initialize_parameter_reductions (void)
3255 {
3256   gimple_stmt_iterator gsi;
3257   gimple_seq seq = NULL;
3258   tree parm;
3259
3260   for (parm = DECL_ARGUMENTS (current_function_decl);
3261        parm;
3262        parm = DECL_CHAIN (parm))
3263     {
3264       VEC (access_p, heap) *access_vec;
3265       struct access *access;
3266
3267       if (!bitmap_bit_p (candidate_bitmap, DECL_UID (parm)))
3268         continue;
3269       access_vec = get_base_access_vector (parm);
3270       if (!access_vec)
3271         continue;
3272
3273       if (!seq)
3274         {
3275           seq = gimple_seq_alloc ();
3276           gsi = gsi_start (seq);
3277         }
3278
3279       for (access = VEC_index (access_p, access_vec, 0);
3280            access;
3281            access = access->next_grp)
3282         generate_subtree_copies (access, parm, 0, 0, 0, &gsi, true, true,
3283                                  EXPR_LOCATION (parm));
3284     }
3285
3286   if (seq)
3287     gsi_insert_seq_on_edge_immediate (single_succ_edge (ENTRY_BLOCK_PTR), seq);
3288 }
3289
3290 /* The "main" function of intraprocedural SRA passes.  Runs the analysis and if
3291    it reveals there are components of some aggregates to be scalarized, it runs
3292    the required transformations.  */
3293 static unsigned int
3294 perform_intra_sra (void)
3295 {
3296   int ret = 0;
3297   sra_initialize ();
3298
3299   if (!find_var_candidates ())
3300     goto out;
3301
3302   if (!scan_function ())
3303     goto out;
3304
3305   if (!analyze_all_variable_accesses ())
3306     goto out;
3307
3308   if (sra_modify_function_body ())
3309     ret = TODO_update_ssa | TODO_cleanup_cfg;
3310   else
3311     ret = TODO_update_ssa;
3312   initialize_parameter_reductions ();
3313
3314   statistics_counter_event (cfun, "Scalar replacements created",
3315                             sra_stats.replacements);
3316   statistics_counter_event (cfun, "Modified expressions", sra_stats.exprs);
3317   statistics_counter_event (cfun, "Subtree copy stmts",
3318                             sra_stats.subtree_copies);
3319   statistics_counter_event (cfun, "Subreplacement stmts",
3320                             sra_stats.subreplacements);
3321   statistics_counter_event (cfun, "Deleted stmts", sra_stats.deleted);
3322   statistics_counter_event (cfun, "Separate LHS and RHS handling",
3323                             sra_stats.separate_lhs_rhs_handling);
3324
3325  out:
3326   sra_deinitialize ();
3327   return ret;
3328 }
3329
3330 /* Perform early intraprocedural SRA.  */
3331 static unsigned int
3332 early_intra_sra (void)
3333 {
3334   sra_mode = SRA_MODE_EARLY_INTRA;
3335   return perform_intra_sra ();
3336 }
3337
3338 /* Perform "late" intraprocedural SRA.  */
3339 static unsigned int
3340 late_intra_sra (void)
3341 {
3342   sra_mode = SRA_MODE_INTRA;
3343   return perform_intra_sra ();
3344 }
3345
3346
3347 static bool
3348 gate_intra_sra (void)
3349 {
3350   return flag_tree_sra != 0 && dbg_cnt (tree_sra);
3351 }
3352
3353
3354 struct gimple_opt_pass pass_sra_early =
3355 {
3356  {
3357   GIMPLE_PASS,
3358   "esra",                               /* name */
3359   gate_intra_sra,                       /* gate */
3360   early_intra_sra,                      /* execute */
3361   NULL,                                 /* sub */
3362   NULL,                                 /* next */
3363   0,                                    /* static_pass_number */
3364   TV_TREE_SRA,                          /* tv_id */
3365   PROP_cfg | PROP_ssa,                  /* properties_required */
3366   0,                                    /* properties_provided */
3367   0,                                    /* properties_destroyed */
3368   0,                                    /* todo_flags_start */
3369   TODO_update_ssa
3370   | TODO_ggc_collect
3371   | TODO_verify_ssa                     /* todo_flags_finish */
3372  }
3373 };
3374
3375 struct gimple_opt_pass pass_sra =
3376 {
3377  {
3378   GIMPLE_PASS,
3379   "sra",                                /* name */
3380   gate_intra_sra,                       /* gate */
3381   late_intra_sra,                       /* execute */
3382   NULL,                                 /* sub */
3383   NULL,                                 /* next */
3384   0,                                    /* static_pass_number */
3385   TV_TREE_SRA,                          /* tv_id */
3386   PROP_cfg | PROP_ssa,                  /* properties_required */
3387   0,                                    /* properties_provided */
3388   0,                                    /* properties_destroyed */
3389   TODO_update_address_taken,            /* todo_flags_start */
3390   TODO_update_ssa
3391   | TODO_ggc_collect
3392   | TODO_verify_ssa                     /* todo_flags_finish */
3393  }
3394 };
3395
3396
3397 /* Return true iff PARM (which must be a parm_decl) is an unused scalar
3398    parameter.  */
3399
3400 static bool
3401 is_unused_scalar_param (tree parm)
3402 {
3403   tree name;
3404   return (is_gimple_reg (parm)
3405           && (!(name = gimple_default_def (cfun, parm))
3406               || has_zero_uses (name)));
3407 }
3408
3409 /* Scan immediate uses of a default definition SSA name of a parameter PARM and
3410    examine whether there are any direct or otherwise infeasible ones.  If so,
3411    return true, otherwise return false.  PARM must be a gimple register with a
3412    non-NULL default definition.  */
3413
3414 static bool
3415 ptr_parm_has_direct_uses (tree parm)
3416 {
3417   imm_use_iterator ui;
3418   gimple stmt;
3419   tree name = gimple_default_def (cfun, parm);
3420   bool ret = false;
3421
3422   FOR_EACH_IMM_USE_STMT (stmt, ui, name)
3423     {
3424       int uses_ok = 0;
3425       use_operand_p use_p;
3426
3427       if (is_gimple_debug (stmt))
3428         continue;
3429
3430       /* Valid uses include dereferences on the lhs and the rhs.  */
3431       if (gimple_has_lhs (stmt))
3432         {
3433           tree lhs = gimple_get_lhs (stmt);
3434           while (handled_component_p (lhs))
3435             lhs = TREE_OPERAND (lhs, 0);
3436           if (TREE_CODE (lhs) == MEM_REF
3437               && TREE_OPERAND (lhs, 0) == name
3438               && integer_zerop (TREE_OPERAND (lhs, 1))
3439               && types_compatible_p (TREE_TYPE (lhs),
3440                                      TREE_TYPE (TREE_TYPE (name)))
3441               && !TREE_THIS_VOLATILE (lhs))
3442             uses_ok++;
3443         }
3444       if (gimple_assign_single_p (stmt))
3445         {
3446           tree rhs = gimple_assign_rhs1 (stmt);
3447           while (handled_component_p (rhs))
3448             rhs = TREE_OPERAND (rhs, 0);
3449           if (TREE_CODE (rhs) == MEM_REF
3450               && TREE_OPERAND (rhs, 0) == name
3451               && integer_zerop (TREE_OPERAND (rhs, 1))
3452               && types_compatible_p (TREE_TYPE (rhs),
3453                                      TREE_TYPE (TREE_TYPE (name)))
3454               && !TREE_THIS_VOLATILE (rhs))
3455             uses_ok++;
3456         }
3457       else if (is_gimple_call (stmt))
3458         {
3459           unsigned i;
3460           for (i = 0; i < gimple_call_num_args (stmt); ++i)
3461             {
3462               tree arg = gimple_call_arg (stmt, i);
3463               while (handled_component_p (arg))
3464                 arg = TREE_OPERAND (arg, 0);
3465               if (TREE_CODE (arg) == MEM_REF
3466                   && TREE_OPERAND (arg, 0) == name
3467                   && integer_zerop (TREE_OPERAND (arg, 1))
3468                   && types_compatible_p (TREE_TYPE (arg),
3469                                          TREE_TYPE (TREE_TYPE (name)))
3470                   && !TREE_THIS_VOLATILE (arg))
3471                 uses_ok++;
3472             }
3473         }
3474
3475       /* If the number of valid uses does not match the number of
3476          uses in this stmt there is an unhandled use.  */
3477       FOR_EACH_IMM_USE_ON_STMT (use_p, ui)
3478         --uses_ok;
3479
3480       if (uses_ok != 0)
3481         ret = true;
3482
3483       if (ret)
3484         BREAK_FROM_IMM_USE_STMT (ui);
3485     }
3486
3487   return ret;
3488 }
3489
3490 /* Identify candidates for reduction for IPA-SRA based on their type and mark
3491    them in candidate_bitmap.  Note that these do not necessarily include
3492    parameter which are unused and thus can be removed.  Return true iff any
3493    such candidate has been found.  */
3494
3495 static bool
3496 find_param_candidates (void)
3497 {
3498   tree parm;
3499   int count = 0;
3500   bool ret = false;
3501   const char *msg;
3502
3503   for (parm = DECL_ARGUMENTS (current_function_decl);
3504        parm;
3505        parm = DECL_CHAIN (parm))
3506     {
3507       tree type = TREE_TYPE (parm);
3508
3509       count++;
3510
3511       if (TREE_THIS_VOLATILE (parm)
3512           || TREE_ADDRESSABLE (parm)
3513           || (!is_gimple_reg_type (type) && is_va_list_type (type)))
3514         continue;
3515
3516       if (is_unused_scalar_param (parm))
3517         {
3518           ret = true;
3519           continue;
3520         }
3521
3522       if (POINTER_TYPE_P (type))
3523         {
3524           type = TREE_TYPE (type);
3525
3526           if (TREE_CODE (type) == FUNCTION_TYPE
3527               || TYPE_VOLATILE (type)
3528               || (TREE_CODE (type) == ARRAY_TYPE
3529                   && TYPE_NONALIASED_COMPONENT (type))
3530               || !is_gimple_reg (parm)
3531               || is_va_list_type (type)
3532               || ptr_parm_has_direct_uses (parm))
3533             continue;
3534         }
3535       else if (!AGGREGATE_TYPE_P (type))
3536         continue;
3537
3538       if (!COMPLETE_TYPE_P (type)
3539           || !host_integerp (TYPE_SIZE (type), 1)
3540           || tree_low_cst (TYPE_SIZE (type), 1) == 0
3541           || (AGGREGATE_TYPE_P (type)
3542               && type_internals_preclude_sra_p (type, &msg)))
3543         continue;
3544
3545       bitmap_set_bit (candidate_bitmap, DECL_UID (parm));
3546       ret = true;
3547       if (dump_file && (dump_flags & TDF_DETAILS))
3548         {
3549           fprintf (dump_file, "Candidate (%d): ", DECL_UID (parm));
3550           print_generic_expr (dump_file, parm, 0);
3551           fprintf (dump_file, "\n");
3552         }
3553     }
3554
3555   func_param_count = count;
3556   return ret;
3557 }
3558
3559 /* Callback of walk_aliased_vdefs, marks the access passed as DATA as
3560    maybe_modified. */
3561
3562 static bool
3563 mark_maybe_modified (ao_ref *ao ATTRIBUTE_UNUSED, tree vdef ATTRIBUTE_UNUSED,
3564                      void *data)
3565 {
3566   struct access *repr = (struct access *) data;
3567
3568   repr->grp_maybe_modified = 1;
3569   return true;
3570 }
3571
3572 /* Analyze what representatives (in linked lists accessible from
3573    REPRESENTATIVES) can be modified by side effects of statements in the
3574    current function.  */
3575
3576 static void
3577 analyze_modified_params (VEC (access_p, heap) *representatives)
3578 {
3579   int i;
3580
3581   for (i = 0; i < func_param_count; i++)
3582     {
3583       struct access *repr;
3584
3585       for (repr = VEC_index (access_p, representatives, i);
3586            repr;
3587            repr = repr->next_grp)
3588         {
3589           struct access *access;
3590           bitmap visited;
3591           ao_ref ar;
3592
3593           if (no_accesses_p (repr))
3594             continue;
3595           if (!POINTER_TYPE_P (TREE_TYPE (repr->base))
3596               || repr->grp_maybe_modified)
3597             continue;
3598
3599           ao_ref_init (&ar, repr->expr);
3600           visited = BITMAP_ALLOC (NULL);
3601           for (access = repr; access; access = access->next_sibling)
3602             {
3603               /* All accesses are read ones, otherwise grp_maybe_modified would
3604                  be trivially set.  */
3605               walk_aliased_vdefs (&ar, gimple_vuse (access->stmt),
3606                                   mark_maybe_modified, repr, &visited);
3607               if (repr->grp_maybe_modified)
3608                 break;
3609             }
3610           BITMAP_FREE (visited);
3611         }
3612     }
3613 }
3614
3615 /* Propagate distances in bb_dereferences in the opposite direction than the
3616    control flow edges, in each step storing the maximum of the current value
3617    and the minimum of all successors.  These steps are repeated until the table
3618    stabilizes.  Note that BBs which might terminate the functions (according to
3619    final_bbs bitmap) never updated in this way.  */
3620
3621 static void
3622 propagate_dereference_distances (void)
3623 {
3624   VEC (basic_block, heap) *queue;
3625   basic_block bb;
3626
3627   queue = VEC_alloc (basic_block, heap, last_basic_block_for_function (cfun));
3628   VEC_quick_push (basic_block, queue, ENTRY_BLOCK_PTR);
3629   FOR_EACH_BB (bb)
3630     {
3631       VEC_quick_push (basic_block, queue, bb);
3632       bb->aux = bb;
3633     }
3634
3635   while (!VEC_empty (basic_block, queue))
3636     {
3637       edge_iterator ei;
3638       edge e;
3639       bool change = false;
3640       int i;
3641
3642       bb = VEC_pop (basic_block, queue);
3643       bb->aux = NULL;
3644
3645       if (bitmap_bit_p (final_bbs, bb->index))
3646         continue;
3647
3648       for (i = 0; i < func_param_count; i++)
3649         {
3650           int idx = bb->index * func_param_count + i;
3651           bool first = true;
3652           HOST_WIDE_INT inh = 0;
3653
3654           FOR_EACH_EDGE (e, ei, bb->succs)
3655           {
3656             int succ_idx = e->dest->index * func_param_count + i;
3657
3658             if (e->src == EXIT_BLOCK_PTR)
3659               continue;
3660
3661             if (first)
3662               {
3663                 first = false;
3664                 inh = bb_dereferences [succ_idx];
3665               }
3666             else if (bb_dereferences [succ_idx] < inh)
3667               inh = bb_dereferences [succ_idx];
3668           }
3669
3670           if (!first && bb_dereferences[idx] < inh)
3671             {
3672               bb_dereferences[idx] = inh;
3673               change = true;
3674             }
3675         }
3676
3677       if (change && !bitmap_bit_p (final_bbs, bb->index))
3678         FOR_EACH_EDGE (e, ei, bb->preds)
3679           {
3680             if (e->src->aux)
3681               continue;
3682
3683             e->src->aux = e->src;
3684             VEC_quick_push (basic_block, queue, e->src);
3685           }
3686     }
3687
3688   VEC_free (basic_block, heap, queue);
3689 }
3690
3691 /* Dump a dereferences TABLE with heading STR to file F.  */
3692
3693 static void
3694 dump_dereferences_table (FILE *f, const char *str, HOST_WIDE_INT *table)
3695 {
3696   basic_block bb;
3697
3698   fprintf (dump_file, str);
3699   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
3700     {
3701       fprintf (f, "%4i  %i   ", bb->index, bitmap_bit_p (final_bbs, bb->index));
3702       if (bb != EXIT_BLOCK_PTR)
3703         {
3704           int i;
3705           for (i = 0; i < func_param_count; i++)
3706             {
3707               int idx = bb->index * func_param_count + i;
3708               fprintf (f, " %4" HOST_WIDE_INT_PRINT "d", table[idx]);
3709             }
3710         }
3711       fprintf (f, "\n");
3712     }
3713   fprintf (dump_file, "\n");
3714 }
3715
3716 /* Determine what (parts of) parameters passed by reference that are not
3717    assigned to are not certainly dereferenced in this function and thus the
3718    dereferencing cannot be safely moved to the caller without potentially
3719    introducing a segfault.  Mark such REPRESENTATIVES as
3720    grp_not_necessarilly_dereferenced.
3721
3722    The dereferenced maximum "distance," i.e. the offset + size of the accessed
3723    part is calculated rather than simple booleans are calculated for each
3724    pointer parameter to handle cases when only a fraction of the whole
3725    aggregate is allocated (see testsuite/gcc.c-torture/execute/ipa-sra-2.c for
3726    an example).
3727
3728    The maximum dereference distances for each pointer parameter and BB are
3729    already stored in bb_dereference.  This routine simply propagates these
3730    values upwards by propagate_dereference_distances and then compares the
3731    distances of individual parameters in the ENTRY BB to the equivalent
3732    distances of each representative of a (fraction of a) parameter.  */
3733
3734 static void
3735 analyze_caller_dereference_legality (VEC (access_p, heap) *representatives)
3736 {
3737   int i;
3738
3739   if (dump_file && (dump_flags & TDF_DETAILS))
3740     dump_dereferences_table (dump_file,
3741                              "Dereference table before propagation:\n",
3742                              bb_dereferences);
3743
3744   propagate_dereference_distances ();
3745
3746   if (dump_file && (dump_flags & TDF_DETAILS))
3747     dump_dereferences_table (dump_file,
3748                              "Dereference table after propagation:\n",
3749                              bb_dereferences);
3750
3751   for (i = 0; i < func_param_count; i++)
3752     {
3753       struct access *repr = VEC_index (access_p, representatives, i);
3754       int idx = ENTRY_BLOCK_PTR->index * func_param_count + i;
3755
3756       if (!repr || no_accesses_p (repr))
3757         continue;
3758
3759       do
3760         {
3761           if ((repr->offset + repr->size) > bb_dereferences[idx])
3762             repr->grp_not_necessarilly_dereferenced = 1;
3763           repr = repr->next_grp;
3764         }
3765       while (repr);
3766     }
3767 }
3768
3769 /* Return the representative access for the parameter declaration PARM if it is
3770    a scalar passed by reference which is not written to and the pointer value
3771    is not used directly.  Thus, if it is legal to dereference it in the caller
3772    and we can rule out modifications through aliases, such parameter should be
3773    turned into one passed by value.  Return NULL otherwise.  */
3774
3775 static struct access *
3776 unmodified_by_ref_scalar_representative (tree parm)
3777 {
3778   int i, access_count;
3779   struct access *repr;
3780   VEC (access_p, heap) *access_vec;
3781
3782   access_vec = get_base_access_vector (parm);
3783   gcc_assert (access_vec);
3784   repr = VEC_index (access_p, access_vec, 0);
3785   if (repr->write)
3786     return NULL;
3787   repr->group_representative = repr;
3788
3789   access_count = VEC_length (access_p, access_vec);
3790   for (i = 1; i < access_count; i++)
3791     {
3792       struct access *access = VEC_index (access_p, access_vec, i);
3793       if (access->write)
3794         return NULL;
3795       access->group_representative = repr;
3796       access->next_sibling = repr->next_sibling;
3797       repr->next_sibling = access;
3798     }
3799
3800   repr->grp_read = 1;
3801   repr->grp_scalar_ptr = 1;
3802   return repr;
3803 }
3804
3805 /* Return true iff this access precludes IPA-SRA of the parameter it is
3806    associated with. */
3807
3808 static bool
3809 access_precludes_ipa_sra_p (struct access *access)
3810 {
3811   /* Avoid issues such as the second simple testcase in PR 42025.  The problem
3812      is incompatible assign in a call statement (and possibly even in asm
3813      statements).  This can be relaxed by using a new temporary but only for
3814      non-TREE_ADDRESSABLE types and is probably not worth the complexity. (In
3815      intraprocedural SRA we deal with this by keeping the old aggregate around,
3816      something we cannot do in IPA-SRA.)  */
3817   if (access->write
3818       && (is_gimple_call (access->stmt)
3819           || gimple_code (access->stmt) == GIMPLE_ASM))
3820     return true;
3821
3822   if (STRICT_ALIGNMENT
3823       && tree_non_aligned_mem_p (access->expr, TYPE_ALIGN (access->type)))
3824     return true;
3825
3826   return false;
3827 }
3828
3829
3830 /* Sort collected accesses for parameter PARM, identify representatives for
3831    each accessed region and link them together.  Return NULL if there are
3832    different but overlapping accesses, return the special ptr value meaning
3833    there are no accesses for this parameter if that is the case and return the
3834    first representative otherwise.  Set *RO_GRP if there is a group of accesses
3835    with only read (i.e. no write) accesses.  */
3836
3837 static struct access *
3838 splice_param_accesses (tree parm, bool *ro_grp)
3839 {
3840   int i, j, access_count, group_count;
3841   int agg_size, total_size = 0;
3842   struct access *access, *res, **prev_acc_ptr = &res;
3843   VEC (access_p, heap) *access_vec;
3844
3845   access_vec = get_base_access_vector (parm);
3846   if (!access_vec)
3847     return &no_accesses_representant;
3848   access_count = VEC_length (access_p, access_vec);
3849
3850   VEC_qsort (access_p, access_vec, compare_access_positions);
3851
3852   i = 0;
3853   total_size = 0;
3854   group_count = 0;
3855   while (i < access_count)
3856     {
3857       bool modification;
3858       tree a1_alias_type;
3859       access = VEC_index (access_p, access_vec, i);
3860       modification = access->write;
3861       if (access_precludes_ipa_sra_p (access))
3862         return NULL;
3863       a1_alias_type = reference_alias_ptr_type (access->expr);
3864
3865       /* Access is about to become group representative unless we find some
3866          nasty overlap which would preclude us from breaking this parameter
3867          apart. */
3868
3869       j = i + 1;
3870       while (j < access_count)
3871         {
3872           struct access *ac2 = VEC_index (access_p, access_vec, j);
3873           if (ac2->offset != access->offset)
3874             {
3875               /* All or nothing law for parameters. */
3876               if (access->offset + access->size > ac2->offset)
3877                 return NULL;
3878               else
3879                 break;
3880             }
3881           else if (ac2->size != access->size)
3882             return NULL;
3883
3884           if (access_precludes_ipa_sra_p (ac2)
3885               || (ac2->type != access->type
3886                   && (TREE_ADDRESSABLE (ac2->type)
3887                       || TREE_ADDRESSABLE (access->type)))
3888               || (reference_alias_ptr_type (ac2->expr) != a1_alias_type))
3889             return NULL;
3890
3891           modification |= ac2->write;
3892           ac2->group_representative = access;
3893           ac2->next_sibling = access->next_sibling;
3894           access->next_sibling = ac2;
3895           j++;
3896         }
3897
3898       group_count++;
3899       access->grp_maybe_modified = modification;
3900       if (!modification)
3901         *ro_grp = true;
3902       *prev_acc_ptr = access;
3903       prev_acc_ptr = &access->next_grp;
3904       total_size += access->size;
3905       i = j;
3906     }
3907
3908   if (POINTER_TYPE_P (TREE_TYPE (parm)))
3909     agg_size = tree_low_cst (TYPE_SIZE (TREE_TYPE (TREE_TYPE (parm))), 1);
3910   else
3911     agg_size = tree_low_cst (TYPE_SIZE (TREE_TYPE (parm)), 1);
3912   if (total_size >= agg_size)
3913     return NULL;
3914
3915   gcc_assert (group_count > 0);
3916   return res;
3917 }
3918
3919 /* Decide whether parameters with representative accesses given by REPR should
3920    be reduced into components.  */
3921
3922 static int
3923 decide_one_param_reduction (struct access *repr)
3924 {
3925   int total_size, cur_parm_size, agg_size, new_param_count, parm_size_limit;
3926   bool by_ref;
3927   tree parm;
3928
3929   parm = repr->base;
3930   cur_parm_size = tree_low_cst (TYPE_SIZE (TREE_TYPE (parm)), 1);
3931   gcc_assert (cur_parm_size > 0);
3932
3933   if (POINTER_TYPE_P (TREE_TYPE (parm)))
3934     {
3935       by_ref = true;
3936       agg_size = tree_low_cst (TYPE_SIZE (TREE_TYPE (TREE_TYPE (parm))), 1);
3937     }
3938   else
3939     {
3940       by_ref = false;
3941       agg_size = cur_parm_size;
3942     }
3943
3944   if (dump_file)
3945     {
3946       struct access *acc;
3947       fprintf (dump_file, "Evaluating PARAM group sizes for ");
3948       print_generic_expr (dump_file, parm, 0);
3949       fprintf (dump_file, " (UID: %u): \n", DECL_UID (parm));
3950       for (acc = repr; acc; acc = acc->next_grp)
3951         dump_access (dump_file, acc, true);
3952     }
3953
3954   total_size = 0;
3955   new_param_count = 0;
3956
3957   for (; repr; repr = repr->next_grp)
3958     {
3959       gcc_assert (parm == repr->base);
3960
3961       /* Taking the address of a non-addressable field is verboten.  */
3962       if (by_ref && repr->non_addressable)
3963         return 0;
3964
3965       /* Do not decompose a non-BLKmode param in a way that would
3966          create BLKmode params.  Especially for by-reference passing
3967          (thus, pointer-type param) this is hardly worthwhile.  */
3968       if (DECL_MODE (parm) != BLKmode
3969           && TYPE_MODE (repr->type) == BLKmode)
3970         return 0;
3971
3972       if (!by_ref || (!repr->grp_maybe_modified
3973                       && !repr->grp_not_necessarilly_dereferenced))
3974         total_size += repr->size;
3975       else
3976         total_size += cur_parm_size;
3977
3978       new_param_count++;
3979     }
3980
3981   gcc_assert (new_param_count > 0);
3982
3983   if (optimize_function_for_size_p (cfun))
3984     parm_size_limit = cur_parm_size;
3985   else
3986     parm_size_limit = (PARAM_VALUE (PARAM_IPA_SRA_PTR_GROWTH_FACTOR)
3987                        * cur_parm_size);
3988
3989   if (total_size < agg_size
3990       && total_size <= parm_size_limit)
3991     {
3992       if (dump_file)
3993         fprintf (dump_file, "    ....will be split into %i components\n",
3994                  new_param_count);
3995       return new_param_count;
3996     }
3997   else
3998     return 0;
3999 }
4000
4001 /* The order of the following enums is important, we need to do extra work for
4002    UNUSED_PARAMS, BY_VAL_ACCESSES and UNMODIF_BY_REF_ACCESSES.  */
4003 enum ipa_splicing_result { NO_GOOD_ACCESS, UNUSED_PARAMS, BY_VAL_ACCESSES,
4004                           MODIF_BY_REF_ACCESSES, UNMODIF_BY_REF_ACCESSES };
4005
4006 /* Identify representatives of all accesses to all candidate parameters for
4007    IPA-SRA.  Return result based on what representatives have been found. */
4008
4009 static enum ipa_splicing_result
4010 splice_all_param_accesses (VEC (access_p, heap) **representatives)
4011 {
4012   enum ipa_splicing_result result = NO_GOOD_ACCESS;
4013   tree parm;
4014   struct access *repr;
4015
4016   *representatives = VEC_alloc (access_p, heap, func_param_count);
4017
4018   for (parm = DECL_ARGUMENTS (current_function_decl);
4019        parm;
4020        parm = DECL_CHAIN (parm))
4021     {
4022       if (is_unused_scalar_param (parm))
4023         {
4024           VEC_quick_push (access_p, *representatives,
4025                           &no_accesses_representant);
4026           if (result == NO_GOOD_ACCESS)
4027             result = UNUSED_PARAMS;
4028         }
4029       else if (POINTER_TYPE_P (TREE_TYPE (parm))
4030                && is_gimple_reg_type (TREE_TYPE (TREE_TYPE (parm)))
4031                && bitmap_bit_p (candidate_bitmap, DECL_UID (parm)))
4032         {
4033           repr = unmodified_by_ref_scalar_representative (parm);
4034           VEC_quick_push (access_p, *representatives, repr);
4035           if (repr)
4036             result = UNMODIF_BY_REF_ACCESSES;
4037         }
4038       else if (bitmap_bit_p (candidate_bitmap, DECL_UID (parm)))
4039         {
4040           bool ro_grp = false;
4041           repr = splice_param_accesses (parm, &ro_grp);
4042           VEC_quick_push (access_p, *representatives, repr);
4043
4044           if (repr && !no_accesses_p (repr))
4045             {
4046               if (POINTER_TYPE_P (TREE_TYPE (parm)))
4047                 {
4048                   if (ro_grp)
4049                     result = UNMODIF_BY_REF_ACCESSES;
4050                   else if (result < MODIF_BY_REF_ACCESSES)
4051                     result = MODIF_BY_REF_ACCESSES;
4052                 }
4053               else if (result < BY_VAL_ACCESSES)
4054                 result = BY_VAL_ACCESSES;
4055             }
4056           else if (no_accesses_p (repr) && (result == NO_GOOD_ACCESS))
4057             result = UNUSED_PARAMS;
4058         }
4059       else
4060         VEC_quick_push (access_p, *representatives, NULL);
4061     }
4062
4063   if (result == NO_GOOD_ACCESS)
4064     {
4065       VEC_free (access_p, heap, *representatives);
4066       *representatives = NULL;
4067       return NO_GOOD_ACCESS;
4068     }
4069
4070   return result;
4071 }
4072
4073 /* Return the index of BASE in PARMS.  Abort if it is not found.  */
4074
4075 static inline int
4076 get_param_index (tree base, VEC(tree, heap) *parms)
4077 {
4078   int i, len;
4079
4080   len = VEC_length (tree, parms);
4081   for (i = 0; i < len; i++)
4082     if (VEC_index (tree, parms, i) == base)
4083       return i;
4084   gcc_unreachable ();
4085 }
4086
4087 /* Convert the decisions made at the representative level into compact
4088    parameter adjustments.  REPRESENTATIVES are pointers to first
4089    representatives of each param accesses, ADJUSTMENTS_COUNT is the expected
4090    final number of adjustments.  */
4091
4092 static ipa_parm_adjustment_vec
4093 turn_representatives_into_adjustments (VEC (access_p, heap) *representatives,
4094                                        int adjustments_count)
4095 {
4096   VEC (tree, heap) *parms;
4097   ipa_parm_adjustment_vec adjustments;
4098   tree parm;
4099   int i;
4100
4101   gcc_assert (adjustments_count > 0);
4102   parms = ipa_get_vector_of_formal_parms (current_function_decl);
4103   adjustments = VEC_alloc (ipa_parm_adjustment_t, heap, adjustments_count);
4104   parm = DECL_ARGUMENTS (current_function_decl);
4105   for (i = 0; i < func_param_count; i++, parm = DECL_CHAIN (parm))
4106     {
4107       struct access *repr = VEC_index (access_p, representatives, i);
4108
4109       if (!repr || no_accesses_p (repr))
4110         {
4111           struct ipa_parm_adjustment *adj;
4112
4113           adj = VEC_quick_push (ipa_parm_adjustment_t, adjustments, NULL);
4114           memset (adj, 0, sizeof (*adj));
4115           adj->base_index = get_param_index (parm, parms);
4116           adj->base = parm;
4117           if (!repr)
4118             adj->copy_param = 1;
4119           else
4120             adj->remove_param = 1;
4121         }
4122       else
4123         {
4124           struct ipa_parm_adjustment *adj;
4125           int index = get_param_index (parm, parms);
4126
4127           for (; repr; repr = repr->next_grp)
4128             {
4129               adj = VEC_quick_push (ipa_parm_adjustment_t, adjustments, NULL);
4130               memset (adj, 0, sizeof (*adj));
4131               gcc_assert (repr->base == parm);
4132               adj->base_index = index;
4133               adj->base = repr->base;
4134               adj->type = repr->type;
4135               adj->alias_ptr_type = reference_alias_ptr_type (repr->expr);
4136               adj->offset = repr->offset;
4137               adj->by_ref = (POINTER_TYPE_P (TREE_TYPE (repr->base))
4138                              && (repr->grp_maybe_modified
4139                                  || repr->grp_not_necessarilly_dereferenced));
4140
4141             }
4142         }
4143     }
4144   VEC_free (tree, heap, parms);
4145   return adjustments;
4146 }
4147
4148 /* Analyze the collected accesses and produce a plan what to do with the
4149    parameters in the form of adjustments, NULL meaning nothing.  */
4150
4151 static ipa_parm_adjustment_vec
4152 analyze_all_param_acesses (void)
4153 {
4154   enum ipa_splicing_result repr_state;
4155