OSDN Git Service

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