OSDN Git Service

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