OSDN Git Service

2012-01-27 Richard Guenther <rguenther@suse.de>
[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
1465   gcc_checking_assert (offset % BITS_PER_UNIT == 0);
1466
1467   base = get_addr_base_and_unit_offset (base, &base_offset);
1468
1469   /* get_addr_base_and_unit_offset returns NULL for references with a variable
1470      offset such as array[var_index].  */
1471   if (!base)
1472     {
1473       gimple stmt;
1474       tree tmp, addr;
1475
1476       gcc_checking_assert (gsi);
1477       tmp = create_tmp_reg (build_pointer_type (TREE_TYPE (prev_base)), NULL);
1478       add_referenced_var (tmp);
1479       tmp = make_ssa_name (tmp, NULL);
1480       addr = build_fold_addr_expr (unshare_expr (prev_base));
1481       STRIP_USELESS_TYPE_CONVERSION (addr);
1482       stmt = gimple_build_assign (tmp, addr);
1483       gimple_set_location (stmt, loc);
1484       SSA_NAME_DEF_STMT (tmp) = stmt;
1485       if (insert_after)
1486         gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
1487       else
1488         gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
1489       update_stmt (stmt);
1490
1491       off = build_int_cst (reference_alias_ptr_type (prev_base),
1492                            offset / BITS_PER_UNIT);
1493       base = tmp;
1494     }
1495   else if (TREE_CODE (base) == MEM_REF)
1496     {
1497       off = build_int_cst (TREE_TYPE (TREE_OPERAND (base, 1)),
1498                            base_offset + offset / BITS_PER_UNIT);
1499       off = int_const_binop (PLUS_EXPR, TREE_OPERAND (base, 1), off);
1500       base = unshare_expr (TREE_OPERAND (base, 0));
1501     }
1502   else
1503     {
1504       off = build_int_cst (reference_alias_ptr_type (base),
1505                            base_offset + offset / BITS_PER_UNIT);
1506       base = build_fold_addr_expr (unshare_expr (base));
1507     }
1508
1509   return fold_build2_loc (loc, MEM_REF, exp_type, base, off);
1510 }
1511
1512 DEF_VEC_ALLOC_P_STACK (tree);
1513 #define VEC_tree_stack_alloc(alloc) VEC_stack_alloc (tree, alloc)
1514
1515 /* Construct a memory reference to a part of an aggregate BASE at the given
1516    OFFSET and of the type of MODEL.  In case this is a chain of references
1517    to component, the function will replicate the chain of COMPONENT_REFs of
1518    the expression of MODEL to access it.  GSI and INSERT_AFTER have the same
1519    meaning as in build_ref_for_offset.  */
1520
1521 static tree
1522 build_ref_for_model (location_t loc, tree base, HOST_WIDE_INT offset,
1523                      struct access *model, gimple_stmt_iterator *gsi,
1524                      bool insert_after)
1525 {
1526   tree type = model->type, t;
1527   VEC(tree,stack) *cr_stack = NULL;
1528
1529   if (TREE_CODE (model->expr) == COMPONENT_REF)
1530     {
1531       tree expr = model->expr;
1532
1533       /* Create a stack of the COMPONENT_REFs so later we can walk them in
1534          order from inner to outer.  */
1535       cr_stack = VEC_alloc (tree, stack, 6);
1536
1537       do {
1538         tree field = TREE_OPERAND (expr, 1);
1539         tree cr_offset = component_ref_field_offset (expr);
1540         HOST_WIDE_INT bit_pos
1541           = tree_low_cst (cr_offset, 1) * BITS_PER_UNIT
1542               + TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (field));
1543
1544         /* We can be called with a model different from the one associated
1545            with BASE so we need to avoid going up the chain too far.  */
1546         if (offset - bit_pos < 0)
1547           break;
1548
1549         offset -= bit_pos;
1550         VEC_safe_push (tree, stack, cr_stack, expr);
1551
1552         expr = TREE_OPERAND (expr, 0);
1553         type = TREE_TYPE (expr);
1554       } while (TREE_CODE (expr) == COMPONENT_REF);
1555     }
1556
1557   t = build_ref_for_offset (loc, base, offset, type, gsi, insert_after);
1558
1559   if (TREE_CODE (model->expr) == COMPONENT_REF)
1560     {
1561       unsigned i;
1562       tree expr;
1563
1564       /* Now replicate the chain of COMPONENT_REFs from inner to outer.  */
1565       FOR_EACH_VEC_ELT_REVERSE (tree, cr_stack, i, expr)
1566         {
1567           tree field = TREE_OPERAND (expr, 1);
1568           t = fold_build3_loc (loc, COMPONENT_REF, TREE_TYPE (field), t, field,
1569                                TREE_OPERAND (expr, 2));
1570         }
1571
1572       VEC_free (tree, stack, cr_stack);
1573     }
1574
1575   return t;
1576 }
1577
1578 /* Construct a memory reference consisting of component_refs and array_refs to
1579    a part of an aggregate *RES (which is of type TYPE).  The requested part
1580    should have type EXP_TYPE at be the given OFFSET.  This function might not
1581    succeed, it returns true when it does and only then *RES points to something
1582    meaningful.  This function should be used only to build expressions that we
1583    might need to present to user (e.g. in warnings).  In all other situations,
1584    build_ref_for_model or build_ref_for_offset should be used instead.  */
1585
1586 static bool
1587 build_user_friendly_ref_for_offset (tree *res, tree type, HOST_WIDE_INT offset,
1588                                     tree exp_type)
1589 {
1590   while (1)
1591     {
1592       tree fld;
1593       tree tr_size, index, minidx;
1594       HOST_WIDE_INT el_size;
1595
1596       if (offset == 0 && exp_type
1597           && types_compatible_p (exp_type, type))
1598         return true;
1599
1600       switch (TREE_CODE (type))
1601         {
1602         case UNION_TYPE:
1603         case QUAL_UNION_TYPE:
1604         case RECORD_TYPE:
1605           for (fld = TYPE_FIELDS (type); fld; fld = DECL_CHAIN (fld))
1606             {
1607               HOST_WIDE_INT pos, size;
1608               tree expr, *expr_ptr;
1609
1610               if (TREE_CODE (fld) != FIELD_DECL)
1611                 continue;
1612
1613               pos = int_bit_position (fld);
1614               gcc_assert (TREE_CODE (type) == RECORD_TYPE || pos == 0);
1615               tr_size = DECL_SIZE (fld);
1616               if (!tr_size || !host_integerp (tr_size, 1))
1617                 continue;
1618               size = tree_low_cst (tr_size, 1);
1619               if (size == 0)
1620                 {
1621                   if (pos != offset)
1622                     continue;
1623                 }
1624               else if (pos > offset || (pos + size) <= offset)
1625                 continue;
1626
1627               expr = build3 (COMPONENT_REF, TREE_TYPE (fld), *res, fld,
1628                              NULL_TREE);
1629               expr_ptr = &expr;
1630               if (build_user_friendly_ref_for_offset (expr_ptr, TREE_TYPE (fld),
1631                                                       offset - pos, exp_type))
1632                 {
1633                   *res = expr;
1634                   return true;
1635                 }
1636             }
1637           return false;
1638
1639         case ARRAY_TYPE:
1640           tr_size = TYPE_SIZE (TREE_TYPE (type));
1641           if (!tr_size || !host_integerp (tr_size, 1))
1642             return false;
1643           el_size = tree_low_cst (tr_size, 1);
1644
1645           minidx = TYPE_MIN_VALUE (TYPE_DOMAIN (type));
1646           if (TREE_CODE (minidx) != INTEGER_CST || el_size == 0)
1647             return false;
1648           index = build_int_cst (TYPE_DOMAIN (type), offset / el_size);
1649           if (!integer_zerop (minidx))
1650             index = int_const_binop (PLUS_EXPR, index, minidx);
1651           *res = build4 (ARRAY_REF, TREE_TYPE (type), *res, index,
1652                          NULL_TREE, NULL_TREE);
1653           offset = offset % el_size;
1654           type = TREE_TYPE (type);
1655           break;
1656
1657         default:
1658           if (offset != 0)
1659             return false;
1660
1661           if (exp_type)
1662             return false;
1663           else
1664             return true;
1665         }
1666     }
1667 }
1668
1669 /* Return true iff TYPE is stdarg va_list type.  */
1670
1671 static inline bool
1672 is_va_list_type (tree type)
1673 {
1674   return TYPE_MAIN_VARIANT (type) == TYPE_MAIN_VARIANT (va_list_type_node);
1675 }
1676
1677 /* Print message to dump file why a variable was rejected. */
1678
1679 static void
1680 reject (tree var, const char *msg)
1681 {
1682   if (dump_file && (dump_flags & TDF_DETAILS))
1683     {
1684       fprintf (dump_file, "Rejected (%d): %s: ", DECL_UID (var), msg);
1685       print_generic_expr (dump_file, var, 0);
1686       fprintf (dump_file, "\n");
1687     }
1688 }
1689
1690 /* The very first phase of intraprocedural SRA.  It marks in candidate_bitmap
1691    those with type which is suitable for scalarization.  */
1692
1693 static bool
1694 find_var_candidates (void)
1695 {
1696   tree var, type;
1697   referenced_var_iterator rvi;
1698   bool ret = false;
1699   const char *msg;
1700
1701   FOR_EACH_REFERENCED_VAR (cfun, var, rvi)
1702     {
1703       if (TREE_CODE (var) != VAR_DECL && TREE_CODE (var) != PARM_DECL)
1704         continue;
1705       type = TREE_TYPE (var);
1706
1707       if (!AGGREGATE_TYPE_P (type)) 
1708         {
1709           reject (var, "not aggregate");
1710           continue;
1711         }
1712       if (needs_to_live_in_memory (var))
1713         {
1714           reject (var, "needs to live in memory");
1715           continue;
1716         }
1717       if (TREE_THIS_VOLATILE (var))
1718         {
1719           reject (var, "is volatile");
1720           continue;
1721         }
1722       if (!COMPLETE_TYPE_P (type))
1723         {
1724           reject (var, "has incomplete type");
1725           continue;
1726         }
1727       if (!host_integerp (TYPE_SIZE (type), 1))
1728         {
1729           reject (var, "type size not fixed");
1730           continue;
1731         }
1732       if (tree_low_cst (TYPE_SIZE (type), 1) == 0)
1733         {
1734           reject (var, "type size is zero");
1735           continue;
1736         }
1737       if (type_internals_preclude_sra_p (type, &msg))
1738         {
1739           reject (var, msg);
1740           continue;
1741         }
1742       if (/* Fix for PR 41089.  tree-stdarg.c needs to have va_lists intact but
1743               we also want to schedule it rather late.  Thus we ignore it in
1744               the early pass. */
1745           (sra_mode == SRA_MODE_EARLY_INTRA
1746               && is_va_list_type (type)))
1747         {
1748           reject (var, "is va_list");
1749           continue;
1750         }
1751
1752       bitmap_set_bit (candidate_bitmap, DECL_UID (var));
1753
1754       if (dump_file && (dump_flags & TDF_DETAILS))
1755         {
1756           fprintf (dump_file, "Candidate (%d): ", DECL_UID (var));
1757           print_generic_expr (dump_file, var, 0);
1758           fprintf (dump_file, "\n");
1759         }
1760       ret = true;
1761     }
1762
1763   return ret;
1764 }
1765
1766 /* Sort all accesses for the given variable, check for partial overlaps and
1767    return NULL if there are any.  If there are none, pick a representative for
1768    each combination of offset and size and create a linked list out of them.
1769    Return the pointer to the first representative and make sure it is the first
1770    one in the vector of accesses.  */
1771
1772 static struct access *
1773 sort_and_splice_var_accesses (tree var)
1774 {
1775   int i, j, access_count;
1776   struct access *res, **prev_acc_ptr = &res;
1777   VEC (access_p, heap) *access_vec;
1778   bool first = true;
1779   HOST_WIDE_INT low = -1, high = 0;
1780
1781   access_vec = get_base_access_vector (var);
1782   if (!access_vec)
1783     return NULL;
1784   access_count = VEC_length (access_p, access_vec);
1785
1786   /* Sort by <OFFSET, SIZE>.  */
1787   VEC_qsort (access_p, access_vec, compare_access_positions);
1788
1789   i = 0;
1790   while (i < access_count)
1791     {
1792       struct access *access = VEC_index (access_p, access_vec, i);
1793       bool grp_write = access->write;
1794       bool grp_read = !access->write;
1795       bool grp_scalar_write = access->write
1796         && is_gimple_reg_type (access->type);
1797       bool grp_scalar_read = !access->write
1798         && is_gimple_reg_type (access->type);
1799       bool grp_assignment_read = access->grp_assignment_read;
1800       bool grp_assignment_write = access->grp_assignment_write;
1801       bool multiple_scalar_reads = false;
1802       bool total_scalarization = access->grp_total_scalarization;
1803       bool grp_partial_lhs = access->grp_partial_lhs;
1804       bool first_scalar = is_gimple_reg_type (access->type);
1805       bool unscalarizable_region = access->grp_unscalarizable_region;
1806
1807       if (first || access->offset >= high)
1808         {
1809           first = false;
1810           low = access->offset;
1811           high = access->offset + access->size;
1812         }
1813       else if (access->offset > low && access->offset + access->size > high)
1814         return NULL;
1815       else
1816         gcc_assert (access->offset >= low
1817                     && access->offset + access->size <= high);
1818
1819       j = i + 1;
1820       while (j < access_count)
1821         {
1822           struct access *ac2 = VEC_index (access_p, access_vec, j);
1823           if (ac2->offset != access->offset || ac2->size != access->size)
1824             break;
1825           if (ac2->write)
1826             {
1827               grp_write = true;
1828               grp_scalar_write = (grp_scalar_write
1829                                   || is_gimple_reg_type (ac2->type));
1830             }
1831           else
1832             {
1833               grp_read = true;
1834               if (is_gimple_reg_type (ac2->type))
1835                 {
1836                   if (grp_scalar_read)
1837                     multiple_scalar_reads = true;
1838                   else
1839                     grp_scalar_read = true;
1840                 }
1841             }
1842           grp_assignment_read |= ac2->grp_assignment_read;
1843           grp_assignment_write |= ac2->grp_assignment_write;
1844           grp_partial_lhs |= ac2->grp_partial_lhs;
1845           unscalarizable_region |= ac2->grp_unscalarizable_region;
1846           total_scalarization |= ac2->grp_total_scalarization;
1847           relink_to_new_repr (access, ac2);
1848
1849           /* If there are both aggregate-type and scalar-type accesses with
1850              this combination of size and offset, the comparison function
1851              should have put the scalars first.  */
1852           gcc_assert (first_scalar || !is_gimple_reg_type (ac2->type));
1853           ac2->group_representative = access;
1854           j++;
1855         }
1856
1857       i = j;
1858
1859       access->group_representative = access;
1860       access->grp_write = grp_write;
1861       access->grp_read = grp_read;
1862       access->grp_scalar_read = grp_scalar_read;
1863       access->grp_scalar_write = grp_scalar_write;
1864       access->grp_assignment_read = grp_assignment_read;
1865       access->grp_assignment_write = grp_assignment_write;
1866       access->grp_hint = multiple_scalar_reads || total_scalarization;
1867       access->grp_total_scalarization = total_scalarization;
1868       access->grp_partial_lhs = grp_partial_lhs;
1869       access->grp_unscalarizable_region = unscalarizable_region;
1870       if (access->first_link)
1871         add_access_to_work_queue (access);
1872
1873       *prev_acc_ptr = access;
1874       prev_acc_ptr = &access->next_grp;
1875     }
1876
1877   gcc_assert (res == VEC_index (access_p, access_vec, 0));
1878   return res;
1879 }
1880
1881 /* Create a variable for the given ACCESS which determines the type, name and a
1882    few other properties.  Return the variable declaration and store it also to
1883    ACCESS->replacement.  */
1884
1885 static tree
1886 create_access_replacement (struct access *access, bool rename)
1887 {
1888   tree repl;
1889
1890   repl = create_tmp_var (access->type, "SR");
1891   add_referenced_var (repl);
1892   if (rename)
1893     mark_sym_for_renaming (repl);
1894
1895   if (!access->grp_partial_lhs
1896       && (TREE_CODE (access->type) == COMPLEX_TYPE
1897           || TREE_CODE (access->type) == VECTOR_TYPE))
1898     DECL_GIMPLE_REG_P (repl) = 1;
1899
1900   DECL_SOURCE_LOCATION (repl) = DECL_SOURCE_LOCATION (access->base);
1901   DECL_ARTIFICIAL (repl) = 1;
1902   DECL_IGNORED_P (repl) = DECL_IGNORED_P (access->base);
1903
1904   if (DECL_NAME (access->base)
1905       && !DECL_IGNORED_P (access->base)
1906       && !DECL_ARTIFICIAL (access->base))
1907     {
1908       char *pretty_name = make_fancy_name (access->expr);
1909       tree debug_expr = unshare_expr (access->expr), d;
1910
1911       DECL_NAME (repl) = get_identifier (pretty_name);
1912       obstack_free (&name_obstack, pretty_name);
1913
1914       /* Get rid of any SSA_NAMEs embedded in debug_expr,
1915          as DECL_DEBUG_EXPR isn't considered when looking for still
1916          used SSA_NAMEs and thus they could be freed.  All debug info
1917          generation cares is whether something is constant or variable
1918          and that get_ref_base_and_extent works properly on the
1919          expression.  */
1920       for (d = debug_expr; handled_component_p (d); d = TREE_OPERAND (d, 0))
1921         switch (TREE_CODE (d))
1922           {
1923           case ARRAY_REF:
1924           case ARRAY_RANGE_REF:
1925             if (TREE_OPERAND (d, 1)
1926                 && TREE_CODE (TREE_OPERAND (d, 1)) == SSA_NAME)
1927               TREE_OPERAND (d, 1) = SSA_NAME_VAR (TREE_OPERAND (d, 1));
1928             if (TREE_OPERAND (d, 3)
1929                 && TREE_CODE (TREE_OPERAND (d, 3)) == SSA_NAME)
1930               TREE_OPERAND (d, 3) = SSA_NAME_VAR (TREE_OPERAND (d, 3));
1931             /* FALLTHRU */
1932           case COMPONENT_REF:
1933             if (TREE_OPERAND (d, 2)
1934                 && TREE_CODE (TREE_OPERAND (d, 2)) == SSA_NAME)
1935               TREE_OPERAND (d, 2) = SSA_NAME_VAR (TREE_OPERAND (d, 2));
1936             break;
1937           default:
1938             break;
1939           }
1940       SET_DECL_DEBUG_EXPR (repl, debug_expr);
1941       DECL_DEBUG_EXPR_IS_FROM (repl) = 1;
1942       if (access->grp_no_warning)
1943         TREE_NO_WARNING (repl) = 1;
1944       else
1945         TREE_NO_WARNING (repl) = TREE_NO_WARNING (access->base);
1946     }
1947   else
1948     TREE_NO_WARNING (repl) = 1;
1949
1950   if (dump_file)
1951     {
1952       fprintf (dump_file, "Created a replacement for ");
1953       print_generic_expr (dump_file, access->base, 0);
1954       fprintf (dump_file, " offset: %u, size: %u: ",
1955                (unsigned) access->offset, (unsigned) access->size);
1956       print_generic_expr (dump_file, repl, 0);
1957       fprintf (dump_file, "\n");
1958     }
1959   sra_stats.replacements++;
1960
1961   return repl;
1962 }
1963
1964 /* Return ACCESS scalar replacement, create it if it does not exist yet.  */
1965
1966 static inline tree
1967 get_access_replacement (struct access *access)
1968 {
1969   gcc_assert (access->grp_to_be_replaced);
1970
1971   if (!access->replacement_decl)
1972     access->replacement_decl = create_access_replacement (access, true);
1973   return access->replacement_decl;
1974 }
1975
1976 /* Return ACCESS scalar replacement, create it if it does not exist yet but do
1977    not mark it for renaming.  */
1978
1979 static inline tree
1980 get_unrenamed_access_replacement (struct access *access)
1981 {
1982   gcc_assert (!access->grp_to_be_replaced);
1983
1984   if (!access->replacement_decl)
1985     access->replacement_decl = create_access_replacement (access, false);
1986   return access->replacement_decl;
1987 }
1988
1989
1990 /* Build a subtree of accesses rooted in *ACCESS, and move the pointer in the
1991    linked list along the way.  Stop when *ACCESS is NULL or the access pointed
1992    to it is not "within" the root.  Return false iff some accesses partially
1993    overlap.  */
1994
1995 static bool
1996 build_access_subtree (struct access **access)
1997 {
1998   struct access *root = *access, *last_child = NULL;
1999   HOST_WIDE_INT limit = root->offset + root->size;
2000
2001   *access = (*access)->next_grp;
2002   while  (*access && (*access)->offset + (*access)->size <= limit)
2003     {
2004       if (!last_child)
2005         root->first_child = *access;
2006       else
2007         last_child->next_sibling = *access;
2008       last_child = *access;
2009
2010       if (!build_access_subtree (access))
2011         return false;
2012     }
2013
2014   if (*access && (*access)->offset < limit)
2015     return false;
2016
2017   return true;
2018 }
2019
2020 /* Build a tree of access representatives, ACCESS is the pointer to the first
2021    one, others are linked in a list by the next_grp field.  Return false iff
2022    some accesses partially overlap.  */
2023
2024 static bool
2025 build_access_trees (struct access *access)
2026 {
2027   while (access)
2028     {
2029       struct access *root = access;
2030
2031       if (!build_access_subtree (&access))
2032         return false;
2033       root->next_grp = access;
2034     }
2035   return true;
2036 }
2037
2038 /* Return true if expr contains some ARRAY_REFs into a variable bounded
2039    array.  */
2040
2041 static bool
2042 expr_with_var_bounded_array_refs_p (tree expr)
2043 {
2044   while (handled_component_p (expr))
2045     {
2046       if (TREE_CODE (expr) == ARRAY_REF
2047           && !host_integerp (array_ref_low_bound (expr), 0))
2048         return true;
2049       expr = TREE_OPERAND (expr, 0);
2050     }
2051   return false;
2052 }
2053
2054 /* Analyze the subtree of accesses rooted in ROOT, scheduling replacements when
2055    both seeming beneficial and when ALLOW_REPLACEMENTS allows it.  Also set all
2056    sorts of access flags appropriately along the way, notably always set
2057    grp_read and grp_assign_read according to MARK_READ and grp_write when
2058    MARK_WRITE is true.
2059
2060    Creating a replacement for a scalar access is considered beneficial if its
2061    grp_hint is set (this means we are either attempting total scalarization or
2062    there is more than one direct read access) or according to the following
2063    table:
2064
2065    Access written to through a scalar type (once or more times)
2066    |
2067    |    Written to in an assignment statement
2068    |    |
2069    |    |       Access read as scalar _once_
2070    |    |       |
2071    |    |       |       Read in an assignment statement
2072    |    |       |       |
2073    |    |       |       |       Scalarize       Comment
2074 -----------------------------------------------------------------------------
2075    0    0       0       0                       No access for the scalar
2076    0    0       0       1                       No access for the scalar
2077    0    0       1       0       No              Single read - won't help
2078    0    0       1       1       No              The same case
2079    0    1       0       0                       No access for the scalar
2080    0    1       0       1                       No access for the scalar
2081    0    1       1       0       Yes             s = *g; return s.i;
2082    0    1       1       1       Yes             The same case as above
2083    1    0       0       0       No              Won't help
2084    1    0       0       1       Yes             s.i = 1; *g = s;
2085    1    0       1       0       Yes             s.i = 5; g = s.i;
2086    1    0       1       1       Yes             The same case as above
2087    1    1       0       0       No              Won't help.
2088    1    1       0       1       Yes             s.i = 1; *g = s;
2089    1    1       1       0       Yes             s = *g; return s.i;
2090    1    1       1       1       Yes             Any of the above yeses  */
2091
2092 static bool
2093 analyze_access_subtree (struct access *root, struct access *parent,
2094                         bool allow_replacements)
2095 {
2096   struct access *child;
2097   HOST_WIDE_INT limit = root->offset + root->size;
2098   HOST_WIDE_INT covered_to = root->offset;
2099   bool scalar = is_gimple_reg_type (root->type);
2100   bool hole = false, sth_created = false;
2101
2102   if (parent)
2103     {
2104       if (parent->grp_read)
2105         root->grp_read = 1;
2106       if (parent->grp_assignment_read)
2107         root->grp_assignment_read = 1;
2108       if (parent->grp_write)
2109         root->grp_write = 1;
2110       if (parent->grp_assignment_write)
2111         root->grp_assignment_write = 1;
2112       if (parent->grp_total_scalarization)
2113         root->grp_total_scalarization = 1;
2114     }
2115
2116   if (root->grp_unscalarizable_region)
2117     allow_replacements = false;
2118
2119   if (allow_replacements && expr_with_var_bounded_array_refs_p (root->expr))
2120     allow_replacements = false;
2121
2122   for (child = root->first_child; child; child = child->next_sibling)
2123     {
2124       hole |= covered_to < child->offset;
2125       sth_created |= analyze_access_subtree (child, root,
2126                                              allow_replacements && !scalar);
2127
2128       root->grp_unscalarized_data |= child->grp_unscalarized_data;
2129       root->grp_total_scalarization &= child->grp_total_scalarization;
2130       if (child->grp_covered)
2131         covered_to += child->size;
2132       else
2133         hole = true;
2134     }
2135
2136   if (allow_replacements && scalar && !root->first_child
2137       && (root->grp_hint
2138           || ((root->grp_scalar_read || root->grp_assignment_read)
2139               && (root->grp_scalar_write || root->grp_assignment_write))))
2140     {
2141       bool new_integer_type;
2142       if (TREE_CODE (root->type) == ENUMERAL_TYPE)
2143         {
2144           tree rt = root->type;
2145           root->type = build_nonstandard_integer_type (TYPE_PRECISION (rt),
2146                                                        TYPE_UNSIGNED (rt));
2147           new_integer_type = true;
2148         }
2149       else
2150         new_integer_type = false;
2151
2152       if (dump_file && (dump_flags & TDF_DETAILS))
2153         {
2154           fprintf (dump_file, "Marking ");
2155           print_generic_expr (dump_file, root->base, 0);
2156           fprintf (dump_file, " offset: %u, size: %u ",
2157                    (unsigned) root->offset, (unsigned) root->size);
2158           fprintf (dump_file, " to be replaced%s.\n",
2159                    new_integer_type ? " with an integer": "");
2160         }
2161
2162       root->grp_to_be_replaced = 1;
2163       sth_created = true;
2164       hole = false;
2165     }
2166   else
2167     {
2168       if (covered_to < limit)
2169         hole = true;
2170       if (scalar)
2171         root->grp_total_scalarization = 0;
2172     }
2173
2174   if (sth_created
2175       && (!hole || root->grp_total_scalarization))
2176     {
2177       root->grp_covered = 1;
2178       return true;
2179     }
2180   if (root->grp_write || TREE_CODE (root->base) == PARM_DECL)
2181     root->grp_unscalarized_data = 1; /* not covered and written to */
2182   if (sth_created)
2183     return true;
2184   return false;
2185 }
2186
2187 /* Analyze all access trees linked by next_grp by the means of
2188    analyze_access_subtree.  */
2189 static bool
2190 analyze_access_trees (struct access *access)
2191 {
2192   bool ret = false;
2193
2194   while (access)
2195     {
2196       if (analyze_access_subtree (access, NULL, true))
2197         ret = true;
2198       access = access->next_grp;
2199     }
2200
2201   return ret;
2202 }
2203
2204 /* Return true iff a potential new child of LACC at offset OFFSET and with size
2205    SIZE would conflict with an already existing one.  If exactly such a child
2206    already exists in LACC, store a pointer to it in EXACT_MATCH.  */
2207
2208 static bool
2209 child_would_conflict_in_lacc (struct access *lacc, HOST_WIDE_INT norm_offset,
2210                               HOST_WIDE_INT size, struct access **exact_match)
2211 {
2212   struct access *child;
2213
2214   for (child = lacc->first_child; child; child = child->next_sibling)
2215     {
2216       if (child->offset == norm_offset && child->size == size)
2217         {
2218           *exact_match = child;
2219           return true;
2220         }
2221
2222       if (child->offset < norm_offset + size
2223           && child->offset + child->size > norm_offset)
2224         return true;
2225     }
2226
2227   return false;
2228 }
2229
2230 /* Create a new child access of PARENT, with all properties just like MODEL
2231    except for its offset and with its grp_write false and grp_read true.
2232    Return the new access or NULL if it cannot be created.  Note that this access
2233    is created long after all splicing and sorting, it's not located in any
2234    access vector and is automatically a representative of its group.  */
2235
2236 static struct access *
2237 create_artificial_child_access (struct access *parent, struct access *model,
2238                                 HOST_WIDE_INT new_offset)
2239 {
2240   struct access *access;
2241   struct access **child;
2242   tree expr = parent->base;
2243
2244   gcc_assert (!model->grp_unscalarizable_region);
2245
2246   access = (struct access *) pool_alloc (access_pool);
2247   memset (access, 0, sizeof (struct access));
2248   if (!build_user_friendly_ref_for_offset (&expr, TREE_TYPE (expr), new_offset,
2249                                            model->type))
2250     {
2251       access->grp_no_warning = true;
2252       expr = build_ref_for_model (EXPR_LOCATION (parent->base), parent->base,
2253                                   new_offset, model, NULL, false);
2254     }
2255
2256   access->base = parent->base;
2257   access->expr = expr;
2258   access->offset = new_offset;
2259   access->size = model->size;
2260   access->type = model->type;
2261   access->grp_write = true;
2262   access->grp_read = false;
2263
2264   child = &parent->first_child;
2265   while (*child && (*child)->offset < new_offset)
2266     child = &(*child)->next_sibling;
2267
2268   access->next_sibling = *child;
2269   *child = access;
2270
2271   return access;
2272 }
2273
2274
2275 /* Propagate all subaccesses of RACC across an assignment link to LACC. Return
2276    true if any new subaccess was created.  Additionally, if RACC is a scalar
2277    access but LACC is not, change the type of the latter, if possible.  */
2278
2279 static bool
2280 propagate_subaccesses_across_link (struct access *lacc, struct access *racc)
2281 {
2282   struct access *rchild;
2283   HOST_WIDE_INT norm_delta = lacc->offset - racc->offset;
2284   bool ret = false;
2285
2286   if (is_gimple_reg_type (lacc->type)
2287       || lacc->grp_unscalarizable_region
2288       || racc->grp_unscalarizable_region)
2289     return false;
2290
2291   if (is_gimple_reg_type (racc->type))
2292     {
2293       if (!lacc->first_child && !racc->first_child)
2294         {
2295           tree t = lacc->base;
2296
2297           lacc->type = racc->type;
2298           if (build_user_friendly_ref_for_offset (&t, TREE_TYPE (t),
2299                                                   lacc->offset, racc->type))
2300             lacc->expr = t;
2301           else
2302             {
2303               lacc->expr = build_ref_for_model (EXPR_LOCATION (lacc->base),
2304                                                 lacc->base, lacc->offset,
2305                                                 racc, NULL, false);
2306               lacc->grp_no_warning = true;
2307             }
2308         }
2309       return false;
2310     }
2311
2312   for (rchild = racc->first_child; rchild; rchild = rchild->next_sibling)
2313     {
2314       struct access *new_acc = NULL;
2315       HOST_WIDE_INT norm_offset = rchild->offset + norm_delta;
2316
2317       if (rchild->grp_unscalarizable_region)
2318         continue;
2319
2320       if (child_would_conflict_in_lacc (lacc, norm_offset, rchild->size,
2321                                         &new_acc))
2322         {
2323           if (new_acc)
2324             {
2325               rchild->grp_hint = 1;
2326               new_acc->grp_hint |= new_acc->grp_read;
2327               if (rchild->first_child)
2328                 ret |= propagate_subaccesses_across_link (new_acc, rchild);
2329             }
2330           continue;
2331         }
2332
2333       rchild->grp_hint = 1;
2334       new_acc = create_artificial_child_access (lacc, rchild, norm_offset);
2335       if (new_acc)
2336         {
2337           ret = true;
2338           if (racc->first_child)
2339             propagate_subaccesses_across_link (new_acc, rchild);
2340         }
2341     }
2342
2343   return ret;
2344 }
2345
2346 /* Propagate all subaccesses across assignment links.  */
2347
2348 static void
2349 propagate_all_subaccesses (void)
2350 {
2351   while (work_queue_head)
2352     {
2353       struct access *racc = pop_access_from_work_queue ();
2354       struct assign_link *link;
2355
2356       gcc_assert (racc->first_link);
2357
2358       for (link = racc->first_link; link; link = link->next)
2359         {
2360           struct access *lacc = link->lacc;
2361
2362           if (!bitmap_bit_p (candidate_bitmap, DECL_UID (lacc->base)))
2363             continue;
2364           lacc = lacc->group_representative;
2365           if (propagate_subaccesses_across_link (lacc, racc)
2366               && lacc->first_link)
2367             add_access_to_work_queue (lacc);
2368         }
2369     }
2370 }
2371
2372 /* Go through all accesses collected throughout the (intraprocedural) analysis
2373    stage, exclude overlapping ones, identify representatives and build trees
2374    out of them, making decisions about scalarization on the way.  Return true
2375    iff there are any to-be-scalarized variables after this stage. */
2376
2377 static bool
2378 analyze_all_variable_accesses (void)
2379 {
2380   int res = 0;
2381   bitmap tmp = BITMAP_ALLOC (NULL);
2382   bitmap_iterator bi;
2383   unsigned i, max_total_scalarization_size;
2384
2385   max_total_scalarization_size = UNITS_PER_WORD * BITS_PER_UNIT
2386     * MOVE_RATIO (optimize_function_for_speed_p (cfun));
2387
2388   EXECUTE_IF_SET_IN_BITMAP (candidate_bitmap, 0, i, bi)
2389     if (bitmap_bit_p (should_scalarize_away_bitmap, i)
2390         && !bitmap_bit_p (cannot_scalarize_away_bitmap, i))
2391       {
2392         tree var = referenced_var (i);
2393
2394         if (TREE_CODE (var) == VAR_DECL
2395             && type_consists_of_records_p (TREE_TYPE (var)))
2396           {
2397             if ((unsigned) tree_low_cst (TYPE_SIZE (TREE_TYPE (var)), 1)
2398                 <= max_total_scalarization_size)
2399               {
2400                 completely_scalarize_var (var);
2401                 if (dump_file && (dump_flags & TDF_DETAILS))
2402                   {
2403                     fprintf (dump_file, "Will attempt to totally scalarize ");
2404                     print_generic_expr (dump_file, var, 0);
2405                     fprintf (dump_file, " (UID: %u): \n", DECL_UID (var));
2406                   }
2407               }
2408             else if (dump_file && (dump_flags & TDF_DETAILS))
2409               {
2410                 fprintf (dump_file, "Too big to totally scalarize: ");
2411                 print_generic_expr (dump_file, var, 0);
2412                 fprintf (dump_file, " (UID: %u)\n", DECL_UID (var));
2413               }
2414           }
2415       }
2416
2417   bitmap_copy (tmp, candidate_bitmap);
2418   EXECUTE_IF_SET_IN_BITMAP (tmp, 0, i, bi)
2419     {
2420       tree var = referenced_var (i);
2421       struct access *access;
2422
2423       access = sort_and_splice_var_accesses (var);
2424       if (!access || !build_access_trees (access))
2425         disqualify_candidate (var,
2426                               "No or inhibitingly overlapping accesses.");
2427     }
2428
2429   propagate_all_subaccesses ();
2430
2431   bitmap_copy (tmp, candidate_bitmap);
2432   EXECUTE_IF_SET_IN_BITMAP (tmp, 0, i, bi)
2433     {
2434       tree var = referenced_var (i);
2435       struct access *access = get_first_repr_for_decl (var);
2436
2437       if (analyze_access_trees (access))
2438         {
2439           res++;
2440           if (dump_file && (dump_flags & TDF_DETAILS))
2441             {
2442               fprintf (dump_file, "\nAccess trees for ");
2443               print_generic_expr (dump_file, var, 0);
2444               fprintf (dump_file, " (UID: %u): \n", DECL_UID (var));
2445               dump_access_tree (dump_file, access);
2446               fprintf (dump_file, "\n");
2447             }
2448         }
2449       else
2450         disqualify_candidate (var, "No scalar replacements to be created.");
2451     }
2452
2453   BITMAP_FREE (tmp);
2454
2455   if (res)
2456     {
2457       statistics_counter_event (cfun, "Scalarized aggregates", res);
2458       return true;
2459     }
2460   else
2461     return false;
2462 }
2463
2464 /* Generate statements copying scalar replacements of accesses within a subtree
2465    into or out of AGG.  ACCESS, all its children, siblings and their children
2466    are to be processed.  AGG is an aggregate type expression (can be a
2467    declaration but does not have to be, it can for example also be a mem_ref or
2468    a series of handled components).  TOP_OFFSET is the offset of the processed
2469    subtree which has to be subtracted from offsets of individual accesses to
2470    get corresponding offsets for AGG.  If CHUNK_SIZE is non-null, copy only
2471    replacements in the interval <start_offset, start_offset + chunk_size>,
2472    otherwise copy all.  GSI is a statement iterator used to place the new
2473    statements.  WRITE should be true when the statements should write from AGG
2474    to the replacement and false if vice versa.  if INSERT_AFTER is true, new
2475    statements will be added after the current statement in GSI, they will be
2476    added before the statement otherwise.  */
2477
2478 static void
2479 generate_subtree_copies (struct access *access, tree agg,
2480                          HOST_WIDE_INT top_offset,
2481                          HOST_WIDE_INT start_offset, HOST_WIDE_INT chunk_size,
2482                          gimple_stmt_iterator *gsi, bool write,
2483                          bool insert_after, location_t loc)
2484 {
2485   do
2486     {
2487       if (chunk_size && access->offset >= start_offset + chunk_size)
2488         return;
2489
2490       if (access->grp_to_be_replaced
2491           && (chunk_size == 0
2492               || access->offset + access->size > start_offset))
2493         {
2494           tree expr, repl = get_access_replacement (access);
2495           gimple stmt;
2496
2497           expr = build_ref_for_model (loc, agg, access->offset - top_offset,
2498                                       access, gsi, insert_after);
2499
2500           if (write)
2501             {
2502               if (access->grp_partial_lhs)
2503                 expr = force_gimple_operand_gsi (gsi, expr, true, NULL_TREE,
2504                                                  !insert_after,
2505                                                  insert_after ? GSI_NEW_STMT
2506                                                  : GSI_SAME_STMT);
2507               stmt = gimple_build_assign (repl, expr);
2508             }
2509           else
2510             {
2511               TREE_NO_WARNING (repl) = 1;
2512               if (access->grp_partial_lhs)
2513                 repl = force_gimple_operand_gsi (gsi, repl, true, NULL_TREE,
2514                                                  !insert_after,
2515                                                  insert_after ? GSI_NEW_STMT
2516                                                  : GSI_SAME_STMT);
2517               stmt = gimple_build_assign (expr, repl);
2518             }
2519           gimple_set_location (stmt, loc);
2520
2521           if (insert_after)
2522             gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
2523           else
2524             gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
2525           update_stmt (stmt);
2526           sra_stats.subtree_copies++;
2527         }
2528
2529       if (access->first_child)
2530         generate_subtree_copies (access->first_child, agg, top_offset,
2531                                  start_offset, chunk_size, gsi,
2532                                  write, insert_after, loc);
2533
2534       access = access->next_sibling;
2535     }
2536   while (access);
2537 }
2538
2539 /* Assign zero to all scalar replacements in an access subtree.  ACCESS is the
2540    the root of the subtree to be processed.  GSI is the statement iterator used
2541    for inserting statements which are added after the current statement if
2542    INSERT_AFTER is true or before it otherwise.  */
2543
2544 static void
2545 init_subtree_with_zero (struct access *access, gimple_stmt_iterator *gsi,
2546                         bool insert_after, location_t loc)
2547
2548 {
2549   struct access *child;
2550
2551   if (access->grp_to_be_replaced)
2552     {
2553       gimple stmt;
2554
2555       stmt = gimple_build_assign (get_access_replacement (access),
2556                                   build_zero_cst (access->type));
2557       if (insert_after)
2558         gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
2559       else
2560         gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
2561       update_stmt (stmt);
2562       gimple_set_location (stmt, loc);
2563     }
2564
2565   for (child = access->first_child; child; child = child->next_sibling)
2566     init_subtree_with_zero (child, gsi, insert_after, loc);
2567 }
2568
2569 /* Search for an access representative for the given expression EXPR and
2570    return it or NULL if it cannot be found.  */
2571
2572 static struct access *
2573 get_access_for_expr (tree expr)
2574 {
2575   HOST_WIDE_INT offset, size, max_size;
2576   tree base;
2577
2578   /* FIXME: This should not be necessary but Ada produces V_C_Es with a type of
2579      a different size than the size of its argument and we need the latter
2580      one.  */
2581   if (TREE_CODE (expr) == VIEW_CONVERT_EXPR)
2582     expr = TREE_OPERAND (expr, 0);
2583
2584   base = get_ref_base_and_extent (expr, &offset, &size, &max_size);
2585   if (max_size == -1 || !DECL_P (base))
2586     return NULL;
2587
2588   if (!bitmap_bit_p (candidate_bitmap, DECL_UID (base)))
2589     return NULL;
2590
2591   return get_var_base_offset_size_access (base, offset, max_size);
2592 }
2593
2594 /* Replace the expression EXPR with a scalar replacement if there is one and
2595    generate other statements to do type conversion or subtree copying if
2596    necessary.  GSI is used to place newly created statements, WRITE is true if
2597    the expression is being written to (it is on a LHS of a statement or output
2598    in an assembly statement).  */
2599
2600 static bool
2601 sra_modify_expr (tree *expr, gimple_stmt_iterator *gsi, bool write)
2602 {
2603   location_t loc;
2604   struct access *access;
2605   tree type, bfr;
2606
2607   if (TREE_CODE (*expr) == BIT_FIELD_REF)
2608     {
2609       bfr = *expr;
2610       expr = &TREE_OPERAND (*expr, 0);
2611     }
2612   else
2613     bfr = NULL_TREE;
2614
2615   if (TREE_CODE (*expr) == REALPART_EXPR || TREE_CODE (*expr) == IMAGPART_EXPR)
2616     expr = &TREE_OPERAND (*expr, 0);
2617   access = get_access_for_expr (*expr);
2618   if (!access)
2619     return false;
2620   type = TREE_TYPE (*expr);
2621
2622   loc = gimple_location (gsi_stmt (*gsi));
2623   if (access->grp_to_be_replaced)
2624     {
2625       tree repl = get_access_replacement (access);
2626       /* If we replace a non-register typed access simply use the original
2627          access expression to extract the scalar component afterwards.
2628          This happens if scalarizing a function return value or parameter
2629          like in gcc.c-torture/execute/20041124-1.c, 20050316-1.c and
2630          gcc.c-torture/compile/20011217-1.c.
2631
2632          We also want to use this when accessing a complex or vector which can
2633          be accessed as a different type too, potentially creating a need for
2634          type conversion (see PR42196) and when scalarized unions are involved
2635          in assembler statements (see PR42398).  */
2636       if (!useless_type_conversion_p (type, access->type))
2637         {
2638           tree ref;
2639
2640           ref = build_ref_for_model (loc, access->base, access->offset, access,
2641                                      NULL, false);
2642
2643           if (write)
2644             {
2645               gimple stmt;
2646
2647               if (access->grp_partial_lhs)
2648                 ref = force_gimple_operand_gsi (gsi, ref, true, NULL_TREE,
2649                                                  false, GSI_NEW_STMT);
2650               stmt = gimple_build_assign (repl, ref);
2651               gimple_set_location (stmt, loc);
2652               gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
2653             }
2654           else
2655             {
2656               gimple stmt;
2657
2658               if (access->grp_partial_lhs)
2659                 repl = force_gimple_operand_gsi (gsi, repl, true, NULL_TREE,
2660                                                  true, GSI_SAME_STMT);
2661               stmt = gimple_build_assign (ref, repl);
2662               gimple_set_location (stmt, loc);
2663               gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
2664             }
2665         }
2666       else
2667         *expr = repl;
2668       sra_stats.exprs++;
2669     }
2670
2671   if (access->first_child)
2672     {
2673       HOST_WIDE_INT start_offset, chunk_size;
2674       if (bfr
2675           && host_integerp (TREE_OPERAND (bfr, 1), 1)
2676           && host_integerp (TREE_OPERAND (bfr, 2), 1))
2677         {
2678           chunk_size = tree_low_cst (TREE_OPERAND (bfr, 1), 1);
2679           start_offset = access->offset
2680             + tree_low_cst (TREE_OPERAND (bfr, 2), 1);
2681         }
2682       else
2683         start_offset = chunk_size = 0;
2684
2685       generate_subtree_copies (access->first_child, access->base, 0,
2686                                start_offset, chunk_size, gsi, write, write,
2687                                loc);
2688     }
2689   return true;
2690 }
2691
2692 /* Where scalar replacements of the RHS have been written to when a replacement
2693    of a LHS of an assigments cannot be direclty loaded from a replacement of
2694    the RHS. */
2695 enum unscalarized_data_handling { SRA_UDH_NONE,  /* Nothing done so far. */
2696                                   SRA_UDH_RIGHT, /* Data flushed to the RHS. */
2697                                   SRA_UDH_LEFT }; /* Data flushed to the LHS. */
2698
2699 /* Store all replacements in the access tree rooted in TOP_RACC either to their
2700    base aggregate if there are unscalarized data or directly to LHS of the
2701    statement that is pointed to by GSI otherwise.  */
2702
2703 static enum unscalarized_data_handling
2704 handle_unscalarized_data_in_subtree (struct access *top_racc,
2705                                      gimple_stmt_iterator *gsi)
2706 {
2707   if (top_racc->grp_unscalarized_data)
2708     {
2709       generate_subtree_copies (top_racc->first_child, top_racc->base, 0, 0, 0,
2710                                gsi, false, false,
2711                                gimple_location (gsi_stmt (*gsi)));
2712       return SRA_UDH_RIGHT;
2713     }
2714   else
2715     {
2716       tree lhs = gimple_assign_lhs (gsi_stmt (*gsi));
2717       generate_subtree_copies (top_racc->first_child, lhs, top_racc->offset,
2718                                0, 0, gsi, false, false,
2719                                gimple_location (gsi_stmt (*gsi)));
2720       return SRA_UDH_LEFT;
2721     }
2722 }
2723
2724
2725 /* Try to generate statements to load all sub-replacements in an access subtree
2726    formed by children of LACC from scalar replacements in the TOP_RACC subtree.
2727    If that is not possible, refresh the TOP_RACC base aggregate and load the
2728    accesses from it.  LEFT_OFFSET is the offset of the left whole subtree being
2729    copied. NEW_GSI is stmt iterator used for statement insertions after the
2730    original assignment, OLD_GSI is used to insert statements before the
2731    assignment.  *REFRESHED keeps the information whether we have needed to
2732    refresh replacements of the LHS and from which side of the assignments this
2733    takes place.  */
2734
2735 static void
2736 load_assign_lhs_subreplacements (struct access *lacc, struct access *top_racc,
2737                                  HOST_WIDE_INT left_offset,
2738                                  gimple_stmt_iterator *old_gsi,
2739                                  gimple_stmt_iterator *new_gsi,
2740                                  enum unscalarized_data_handling *refreshed)
2741 {
2742   location_t loc = gimple_location (gsi_stmt (*old_gsi));
2743   for (lacc = lacc->first_child; lacc; lacc = lacc->next_sibling)
2744     {
2745       if (lacc->grp_to_be_replaced)
2746         {
2747           struct access *racc;
2748           HOST_WIDE_INT offset = lacc->offset - left_offset + top_racc->offset;
2749           gimple stmt;
2750           tree rhs;
2751
2752           racc = find_access_in_subtree (top_racc, offset, lacc->size);
2753           if (racc && racc->grp_to_be_replaced)
2754             {
2755               rhs = get_access_replacement (racc);
2756               if (!useless_type_conversion_p (lacc->type, racc->type))
2757                 rhs = fold_build1_loc (loc, VIEW_CONVERT_EXPR, lacc->type, rhs);
2758
2759               if (racc->grp_partial_lhs && lacc->grp_partial_lhs)
2760                 rhs = force_gimple_operand_gsi (old_gsi, rhs, true, NULL_TREE,
2761                                                 true, GSI_SAME_STMT);
2762             }
2763           else
2764             {
2765               /* No suitable access on the right hand side, need to load from
2766                  the aggregate.  See if we have to update it first... */
2767               if (*refreshed == SRA_UDH_NONE)
2768                 *refreshed = handle_unscalarized_data_in_subtree (top_racc,
2769                                                                   old_gsi);
2770
2771               if (*refreshed == SRA_UDH_LEFT)
2772                 rhs = build_ref_for_model (loc, lacc->base, lacc->offset, lacc,
2773                                             new_gsi, true);
2774               else
2775                 rhs = build_ref_for_model (loc, top_racc->base, offset, lacc,
2776                                             new_gsi, true);
2777               if (lacc->grp_partial_lhs)
2778                 rhs = force_gimple_operand_gsi (new_gsi, rhs, true, NULL_TREE,
2779                                                 false, GSI_NEW_STMT);
2780             }
2781
2782           stmt = gimple_build_assign (get_access_replacement (lacc), rhs);
2783           gsi_insert_after (new_gsi, stmt, GSI_NEW_STMT);
2784           gimple_set_location (stmt, loc);
2785           update_stmt (stmt);
2786           sra_stats.subreplacements++;
2787         }
2788       else if (*refreshed == SRA_UDH_NONE
2789                && lacc->grp_read && !lacc->grp_covered)
2790         *refreshed = handle_unscalarized_data_in_subtree (top_racc,
2791                                                           old_gsi);
2792
2793       if (lacc->first_child)
2794         load_assign_lhs_subreplacements (lacc, top_racc, left_offset,
2795                                          old_gsi, new_gsi, refreshed);
2796     }
2797 }
2798
2799 /* Result code for SRA assignment modification.  */
2800 enum assignment_mod_result { SRA_AM_NONE,       /* nothing done for the stmt */
2801                              SRA_AM_MODIFIED,  /* stmt changed but not
2802                                                   removed */
2803                              SRA_AM_REMOVED };  /* stmt eliminated */
2804
2805 /* Modify assignments with a CONSTRUCTOR on their RHS.  STMT contains a pointer
2806    to the assignment and GSI is the statement iterator pointing at it.  Returns
2807    the same values as sra_modify_assign.  */
2808
2809 static enum assignment_mod_result
2810 sra_modify_constructor_assign (gimple *stmt, gimple_stmt_iterator *gsi)
2811 {
2812   tree lhs = gimple_assign_lhs (*stmt);
2813   struct access *acc;
2814   location_t loc;
2815
2816   acc = get_access_for_expr (lhs);
2817   if (!acc)
2818     return SRA_AM_NONE;
2819
2820   loc = gimple_location (*stmt);
2821   if (VEC_length (constructor_elt,
2822                   CONSTRUCTOR_ELTS (gimple_assign_rhs1 (*stmt))) > 0)
2823     {
2824       /* I have never seen this code path trigger but if it can happen the
2825          following should handle it gracefully.  */
2826       if (access_has_children_p (acc))
2827         generate_subtree_copies (acc->first_child, acc->base, 0, 0, 0, gsi,
2828                                  true, true, loc);
2829       return SRA_AM_MODIFIED;
2830     }
2831
2832   if (acc->grp_covered)
2833     {
2834       init_subtree_with_zero (acc, gsi, false, loc);
2835       unlink_stmt_vdef (*stmt);
2836       gsi_remove (gsi, true);
2837       return SRA_AM_REMOVED;
2838     }
2839   else
2840     {
2841       init_subtree_with_zero (acc, gsi, true, loc);
2842       return SRA_AM_MODIFIED;
2843     }
2844 }
2845
2846 /* Create and return a new suitable default definition SSA_NAME for RACC which
2847    is an access describing an uninitialized part of an aggregate that is being
2848    loaded.  */
2849
2850 static tree
2851 get_repl_default_def_ssa_name (struct access *racc)
2852 {
2853   tree repl, decl;
2854
2855   decl = get_unrenamed_access_replacement (racc);
2856
2857   repl = gimple_default_def (cfun, decl);
2858   if (!repl)
2859     {
2860       repl = make_ssa_name (decl, gimple_build_nop ());
2861       set_default_def (decl, repl);
2862     }
2863
2864   return repl;
2865 }
2866
2867 /* Return true if REF has a COMPONENT_REF with a bit-field field declaration
2868    somewhere in it.  */
2869
2870 static inline bool
2871 contains_bitfld_comp_ref_p (const_tree ref)
2872 {
2873   while (handled_component_p (ref))
2874     {
2875       if (TREE_CODE (ref) == COMPONENT_REF
2876           && DECL_BIT_FIELD (TREE_OPERAND (ref, 1)))
2877         return true;
2878       ref = TREE_OPERAND (ref, 0);
2879     }
2880
2881   return false;
2882 }
2883
2884 /* Return true if REF has an VIEW_CONVERT_EXPR or a COMPONENT_REF with a
2885    bit-field field declaration somewhere in it.  */
2886
2887 static inline bool
2888 contains_vce_or_bfcref_p (const_tree ref)
2889 {
2890   while (handled_component_p (ref))
2891     {
2892       if (TREE_CODE (ref) == VIEW_CONVERT_EXPR
2893           || (TREE_CODE (ref) == COMPONENT_REF
2894               && DECL_BIT_FIELD (TREE_OPERAND (ref, 1))))
2895         return true;
2896       ref = TREE_OPERAND (ref, 0);
2897     }
2898
2899   return false;
2900 }
2901
2902 /* Examine both sides of the assignment statement pointed to by STMT, replace
2903    them with a scalare replacement if there is one and generate copying of
2904    replacements if scalarized aggregates have been used in the assignment.  GSI
2905    is used to hold generated statements for type conversions and subtree
2906    copying.  */
2907
2908 static enum assignment_mod_result
2909 sra_modify_assign (gimple *stmt, gimple_stmt_iterator *gsi)
2910 {
2911   struct access *lacc, *racc;
2912   tree lhs, rhs;
2913   bool modify_this_stmt = false;
2914   bool force_gimple_rhs = false;
2915   location_t loc;
2916   gimple_stmt_iterator orig_gsi = *gsi;
2917
2918   if (!gimple_assign_single_p (*stmt))
2919     return SRA_AM_NONE;
2920   lhs = gimple_assign_lhs (*stmt);
2921   rhs = gimple_assign_rhs1 (*stmt);
2922
2923   if (TREE_CODE (rhs) == CONSTRUCTOR)
2924     return sra_modify_constructor_assign (stmt, gsi);
2925
2926   if (TREE_CODE (rhs) == REALPART_EXPR || TREE_CODE (lhs) == REALPART_EXPR
2927       || TREE_CODE (rhs) == IMAGPART_EXPR || TREE_CODE (lhs) == IMAGPART_EXPR
2928       || TREE_CODE (rhs) == BIT_FIELD_REF || TREE_CODE (lhs) == BIT_FIELD_REF)
2929     {
2930       modify_this_stmt = sra_modify_expr (gimple_assign_rhs1_ptr (*stmt),
2931                                           gsi, false);
2932       modify_this_stmt |= sra_modify_expr (gimple_assign_lhs_ptr (*stmt),
2933                                            gsi, true);
2934       return modify_this_stmt ? SRA_AM_MODIFIED : SRA_AM_NONE;
2935     }
2936
2937   lacc = get_access_for_expr (lhs);
2938   racc = get_access_for_expr (rhs);
2939   if (!lacc && !racc)
2940     return SRA_AM_NONE;
2941
2942   loc = gimple_location (*stmt);
2943   if (lacc && lacc->grp_to_be_replaced)
2944     {
2945       lhs = get_access_replacement (lacc);
2946       gimple_assign_set_lhs (*stmt, lhs);
2947       modify_this_stmt = true;
2948       if (lacc->grp_partial_lhs)
2949         force_gimple_rhs = true;
2950       sra_stats.exprs++;
2951     }
2952
2953   if (racc && racc->grp_to_be_replaced)
2954     {
2955       rhs = get_access_replacement (racc);
2956       modify_this_stmt = true;
2957       if (racc->grp_partial_lhs)
2958         force_gimple_rhs = true;
2959       sra_stats.exprs++;
2960     }
2961
2962   if (modify_this_stmt)
2963     {
2964       if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
2965         {
2966           /* If we can avoid creating a VIEW_CONVERT_EXPR do so.
2967              ???  This should move to fold_stmt which we simply should
2968              call after building a VIEW_CONVERT_EXPR here.  */
2969           if (AGGREGATE_TYPE_P (TREE_TYPE (lhs))
2970               && !contains_bitfld_comp_ref_p (lhs)
2971               && !access_has_children_p (lacc))
2972             {
2973               lhs = build_ref_for_model (loc, lhs, 0, racc, gsi, false);
2974               gimple_assign_set_lhs (*stmt, lhs);
2975             }
2976           else if (AGGREGATE_TYPE_P (TREE_TYPE (rhs))
2977                    && !contains_vce_or_bfcref_p (rhs)
2978                    && !access_has_children_p (racc))
2979             rhs = build_ref_for_model (loc, rhs, 0, lacc, gsi, false);
2980
2981           if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
2982             {
2983               rhs = fold_build1_loc (loc, VIEW_CONVERT_EXPR, TREE_TYPE (lhs),
2984                                      rhs);
2985               if (is_gimple_reg_type (TREE_TYPE (lhs))
2986                   && TREE_CODE (lhs) != SSA_NAME)
2987                 force_gimple_rhs = true;
2988             }
2989         }
2990     }
2991
2992   /* From this point on, the function deals with assignments in between
2993      aggregates when at least one has scalar reductions of some of its
2994      components.  There are three possible scenarios: Both the LHS and RHS have
2995      to-be-scalarized components, 2) only the RHS has or 3) only the LHS has.
2996
2997      In the first case, we would like to load the LHS components from RHS
2998      components whenever possible.  If that is not possible, we would like to
2999      read it directly from the RHS (after updating it by storing in it its own
3000      components).  If there are some necessary unscalarized data in the LHS,
3001      those will be loaded by the original assignment too.  If neither of these
3002      cases happen, the original statement can be removed.  Most of this is done
3003      by load_assign_lhs_subreplacements.
3004
3005      In the second case, we would like to store all RHS scalarized components
3006      directly into LHS and if they cover the aggregate completely, remove the
3007      statement too.  In the third case, we want the LHS components to be loaded
3008      directly from the RHS (DSE will remove the original statement if it
3009      becomes redundant).
3010
3011      This is a bit complex but manageable when types match and when unions do
3012      not cause confusion in a way that we cannot really load a component of LHS
3013      from the RHS or vice versa (the access representing this level can have
3014      subaccesses that are accessible only through a different union field at a
3015      higher level - different from the one used in the examined expression).
3016      Unions are fun.
3017
3018      Therefore, I specially handle a fourth case, happening when there is a
3019      specific type cast or it is impossible to locate a scalarized subaccess on
3020      the other side of the expression.  If that happens, I simply "refresh" the
3021      RHS by storing in it is scalarized components leave the original statement
3022      there to do the copying and then load the scalar replacements of the LHS.
3023      This is what the first branch does.  */
3024
3025   if (modify_this_stmt
3026       || gimple_has_volatile_ops (*stmt)
3027       || contains_vce_or_bfcref_p (rhs)
3028       || contains_vce_or_bfcref_p (lhs))
3029     {
3030       if (access_has_children_p (racc))
3031         generate_subtree_copies (racc->first_child, racc->base, 0, 0, 0,
3032                                  gsi, false, false, loc);
3033       if (access_has_children_p (lacc))
3034         generate_subtree_copies (lacc->first_child, lacc->base, 0, 0, 0,
3035                                  gsi, true, true, loc);
3036       sra_stats.separate_lhs_rhs_handling++;
3037     }
3038   else
3039     {
3040       if (access_has_children_p (lacc) && access_has_children_p (racc))
3041         {
3042           gimple_stmt_iterator orig_gsi = *gsi;
3043           enum unscalarized_data_handling refreshed;
3044
3045           if (lacc->grp_read && !lacc->grp_covered)
3046             refreshed = handle_unscalarized_data_in_subtree (racc, gsi);
3047           else
3048             refreshed = SRA_UDH_NONE;
3049
3050           load_assign_lhs_subreplacements (lacc, racc, lacc->offset,
3051                                            &orig_gsi, gsi, &refreshed);
3052           if (refreshed != SRA_UDH_RIGHT)
3053             {
3054               gsi_next (gsi);
3055               unlink_stmt_vdef (*stmt);
3056               gsi_remove (&orig_gsi, true);
3057               sra_stats.deleted++;
3058               return SRA_AM_REMOVED;
3059             }
3060         }
3061       else
3062         {
3063           if (racc)
3064             {
3065               if (!racc->grp_to_be_replaced && !racc->grp_unscalarized_data)
3066                 {
3067                   if (dump_file)
3068                     {
3069                       fprintf (dump_file, "Removing load: ");
3070                       print_gimple_stmt (dump_file, *stmt, 0, 0);
3071                     }
3072
3073                   if (TREE_CODE (lhs) == SSA_NAME)
3074                     {
3075                       rhs = get_repl_default_def_ssa_name (racc);
3076                       if (!useless_type_conversion_p (TREE_TYPE (lhs),
3077                                                       TREE_TYPE (rhs)))
3078                         rhs = fold_build1_loc (loc, VIEW_CONVERT_EXPR,
3079                                                TREE_TYPE (lhs), rhs);
3080                     }
3081                   else
3082                     {
3083                       if (racc->first_child)
3084                         generate_subtree_copies (racc->first_child, lhs,
3085                                                  racc->offset, 0, 0, gsi,
3086                                                  false, false, loc);
3087
3088                       gcc_assert (*stmt == gsi_stmt (*gsi));
3089                       unlink_stmt_vdef (*stmt);
3090                       gsi_remove (gsi, true);
3091                       sra_stats.deleted++;
3092                       return SRA_AM_REMOVED;
3093                     }
3094                 }
3095               else if (racc->first_child)
3096                 generate_subtree_copies (racc->first_child, lhs, racc->offset,
3097                                          0, 0, gsi, false, true, loc);
3098             }
3099           if (access_has_children_p (lacc))
3100             generate_subtree_copies (lacc->first_child, rhs, lacc->offset,
3101                                      0, 0, gsi, true, true, loc);
3102         }
3103     }
3104
3105   /* This gimplification must be done after generate_subtree_copies, lest we
3106      insert the subtree copies in the middle of the gimplified sequence.  */
3107   if (force_gimple_rhs)
3108     rhs = force_gimple_operand_gsi (&orig_gsi, rhs, true, NULL_TREE,
3109                                     true, GSI_SAME_STMT);
3110   if (gimple_assign_rhs1 (*stmt) != rhs)
3111     {
3112       modify_this_stmt = true;
3113       gimple_assign_set_rhs_from_tree (&orig_gsi, rhs);
3114       gcc_assert (*stmt == gsi_stmt (orig_gsi));
3115     }
3116
3117   return modify_this_stmt ? SRA_AM_MODIFIED : SRA_AM_NONE;
3118 }
3119
3120 /* Traverse the function body and all modifications as decided in
3121    analyze_all_variable_accesses.  Return true iff the CFG has been
3122    changed.  */
3123
3124 static bool
3125 sra_modify_function_body (void)
3126 {
3127   bool cfg_changed = false;
3128   basic_block bb;
3129
3130   FOR_EACH_BB (bb)
3131     {
3132       gimple_stmt_iterator gsi = gsi_start_bb (bb);
3133       while (!gsi_end_p (gsi))
3134         {
3135           gimple stmt = gsi_stmt (gsi);
3136           enum assignment_mod_result assign_result;
3137           bool modified = false, deleted = false;
3138           tree *t;
3139           unsigned i;
3140
3141           switch (gimple_code (stmt))
3142             {
3143             case GIMPLE_RETURN:
3144               t = gimple_return_retval_ptr (stmt);
3145               if (*t != NULL_TREE)
3146                 modified |= sra_modify_expr (t, &gsi, false);
3147               break;
3148
3149             case GIMPLE_ASSIGN:
3150               assign_result = sra_modify_assign (&stmt, &gsi);
3151               modified |= assign_result == SRA_AM_MODIFIED;
3152               deleted = assign_result == SRA_AM_REMOVED;
3153               break;
3154
3155             case GIMPLE_CALL:
3156               /* Operands must be processed before the lhs.  */
3157               for (i = 0; i < gimple_call_num_args (stmt); i++)
3158                 {
3159                   t = gimple_call_arg_ptr (stmt, i);
3160                   modified |= sra_modify_expr (t, &gsi, false);
3161                 }
3162
3163               if (gimple_call_lhs (stmt))
3164                 {
3165                   t = gimple_call_lhs_ptr (stmt);
3166                   modified |= sra_modify_expr (t, &gsi, true);
3167                 }
3168               break;
3169
3170             case GIMPLE_ASM:
3171               for (i = 0; i < gimple_asm_ninputs (stmt); i++)
3172                 {
3173                   t = &TREE_VALUE (gimple_asm_input_op (stmt, i));
3174                   modified |= sra_modify_expr (t, &gsi, false);
3175                 }
3176               for (i = 0; i < gimple_asm_noutputs (stmt); i++)
3177                 {
3178                   t = &TREE_VALUE (gimple_asm_output_op (stmt, i));
3179                   modified |= sra_modify_expr (t, &gsi, true);
3180                 }
3181               break;
3182
3183             default:
3184               break;
3185             }
3186
3187           if (modified)
3188             {
3189               update_stmt (stmt);
3190               if (maybe_clean_eh_stmt (stmt)
3191                   && gimple_purge_dead_eh_edges (gimple_bb (stmt)))
3192                 cfg_changed = true;
3193             }
3194           if (!deleted)
3195             gsi_next (&gsi);
3196         }
3197     }
3198
3199   return cfg_changed;
3200 }
3201
3202 /* Generate statements initializing scalar replacements of parts of function
3203    parameters.  */
3204
3205 static void
3206 initialize_parameter_reductions (void)
3207 {
3208   gimple_stmt_iterator gsi;
3209   gimple_seq seq = NULL;
3210   tree parm;
3211
3212   for (parm = DECL_ARGUMENTS (current_function_decl);
3213        parm;
3214        parm = DECL_CHAIN (parm))
3215     {
3216       VEC (access_p, heap) *access_vec;
3217       struct access *access;
3218
3219       if (!bitmap_bit_p (candidate_bitmap, DECL_UID (parm)))
3220         continue;
3221       access_vec = get_base_access_vector (parm);
3222       if (!access_vec)
3223         continue;
3224
3225       if (!seq)
3226         {
3227           seq = gimple_seq_alloc ();
3228           gsi = gsi_start (seq);
3229         }
3230
3231       for (access = VEC_index (access_p, access_vec, 0);
3232            access;
3233            access = access->next_grp)
3234         generate_subtree_copies (access, parm, 0, 0, 0, &gsi, true, true,
3235                                  EXPR_LOCATION (parm));
3236     }
3237
3238   if (seq)
3239     gsi_insert_seq_on_edge_immediate (single_succ_edge (ENTRY_BLOCK_PTR), seq);
3240 }
3241
3242 /* The "main" function of intraprocedural SRA passes.  Runs the analysis and if
3243    it reveals there are components of some aggregates to be scalarized, it runs
3244    the required transformations.  */
3245 static unsigned int
3246 perform_intra_sra (void)
3247 {
3248   int ret = 0;
3249   sra_initialize ();
3250
3251   if (!find_var_candidates ())
3252     goto out;
3253
3254   if (!scan_function ())
3255     goto out;
3256
3257   if (!analyze_all_variable_accesses ())
3258     goto out;
3259
3260   if (sra_modify_function_body ())
3261     ret = TODO_update_ssa | TODO_cleanup_cfg;
3262   else
3263     ret = TODO_update_ssa;
3264   initialize_parameter_reductions ();
3265
3266   statistics_counter_event (cfun, "Scalar replacements created",
3267                             sra_stats.replacements);
3268   statistics_counter_event (cfun, "Modified expressions", sra_stats.exprs);
3269   statistics_counter_event (cfun, "Subtree copy stmts",
3270                             sra_stats.subtree_copies);
3271   statistics_counter_event (cfun, "Subreplacement stmts",
3272                             sra_stats.subreplacements);
3273   statistics_counter_event (cfun, "Deleted stmts", sra_stats.deleted);
3274   statistics_counter_event (cfun, "Separate LHS and RHS handling",
3275                             sra_stats.separate_lhs_rhs_handling);
3276
3277  out:
3278   sra_deinitialize ();
3279   return ret;
3280 }
3281
3282 /* Perform early intraprocedural SRA.  */
3283 static unsigned int
3284 early_intra_sra (void)
3285 {
3286   sra_mode = SRA_MODE_EARLY_INTRA;
3287   return perform_intra_sra ();
3288 }
3289
3290 /* Perform "late" intraprocedural SRA.  */
3291 static unsigned int
3292 late_intra_sra (void)
3293 {
3294   sra_mode = SRA_MODE_INTRA;
3295   return perform_intra_sra ();
3296 }
3297
3298
3299 static bool
3300 gate_intra_sra (void)
3301 {
3302   return flag_tree_sra != 0 && dbg_cnt (tree_sra);
3303 }
3304
3305
3306 struct gimple_opt_pass pass_sra_early =
3307 {
3308  {
3309   GIMPLE_PASS,
3310   "esra",                               /* name */
3311   gate_intra_sra,                       /* gate */
3312   early_intra_sra,                      /* execute */
3313   NULL,                                 /* sub */
3314   NULL,                                 /* next */
3315   0,                                    /* static_pass_number */
3316   TV_TREE_SRA,                          /* tv_id */
3317   PROP_cfg | PROP_ssa,                  /* properties_required */
3318   0,                                    /* properties_provided */
3319   0,                                    /* properties_destroyed */
3320   0,                                    /* todo_flags_start */
3321   TODO_update_ssa
3322   | TODO_ggc_collect
3323   | TODO_verify_ssa                     /* todo_flags_finish */
3324  }
3325 };
3326
3327 struct gimple_opt_pass pass_sra =
3328 {
3329  {
3330   GIMPLE_PASS,
3331   "sra",                                /* name */
3332   gate_intra_sra,                       /* gate */
3333   late_intra_sra,                       /* execute */
3334   NULL,                                 /* sub */
3335   NULL,                                 /* next */
3336   0,                                    /* static_pass_number */
3337   TV_TREE_SRA,                          /* tv_id */
3338   PROP_cfg | PROP_ssa,                  /* properties_required */
3339   0,                                    /* properties_provided */
3340   0,                                    /* properties_destroyed */
3341   TODO_update_address_taken,            /* todo_flags_start */
3342   TODO_update_ssa
3343   | TODO_ggc_collect
3344   | TODO_verify_ssa                     /* todo_flags_finish */
3345  }
3346 };
3347
3348
3349 /* Return true iff PARM (which must be a parm_decl) is an unused scalar
3350    parameter.  */
3351
3352 static bool
3353 is_unused_scalar_param (tree parm)
3354 {
3355   tree name;
3356   return (is_gimple_reg (parm)
3357           && (!(name = gimple_default_def (cfun, parm))
3358               || has_zero_uses (name)));
3359 }
3360
3361 /* Scan immediate uses of a default definition SSA name of a parameter PARM and
3362    examine whether there are any direct or otherwise infeasible ones.  If so,
3363    return true, otherwise return false.  PARM must be a gimple register with a
3364    non-NULL default definition.  */
3365
3366 static bool
3367 ptr_parm_has_direct_uses (tree parm)
3368 {
3369   imm_use_iterator ui;
3370   gimple stmt;
3371   tree name = gimple_default_def (cfun, parm);
3372   bool ret = false;
3373
3374   FOR_EACH_IMM_USE_STMT (stmt, ui, name)
3375     {
3376       int uses_ok = 0;
3377       use_operand_p use_p;
3378
3379       if (is_gimple_debug (stmt))
3380         continue;
3381
3382       /* Valid uses include dereferences on the lhs and the rhs.  */
3383       if (gimple_has_lhs (stmt))
3384         {
3385           tree lhs = gimple_get_lhs (stmt);
3386           while (handled_component_p (lhs))
3387             lhs = TREE_OPERAND (lhs, 0);
3388           if (TREE_CODE (lhs) == MEM_REF
3389               && TREE_OPERAND (lhs, 0) == name
3390               && integer_zerop (TREE_OPERAND (lhs, 1))
3391               && types_compatible_p (TREE_TYPE (lhs),
3392                                      TREE_TYPE (TREE_TYPE (name)))
3393               && !TREE_THIS_VOLATILE (lhs))
3394             uses_ok++;
3395         }
3396       if (gimple_assign_single_p (stmt))
3397         {
3398           tree rhs = gimple_assign_rhs1 (stmt);
3399           while (handled_component_p (rhs))
3400             rhs = TREE_OPERAND (rhs, 0);
3401           if (TREE_CODE (rhs) == MEM_REF
3402               && TREE_OPERAND (rhs, 0) == name
3403               && integer_zerop (TREE_OPERAND (rhs, 1))
3404               && types_compatible_p (TREE_TYPE (rhs),
3405                                      TREE_TYPE (TREE_TYPE (name)))
3406               && !TREE_THIS_VOLATILE (rhs))
3407             uses_ok++;
3408         }
3409       else if (is_gimple_call (stmt))
3410         {
3411           unsigned i;
3412           for (i = 0; i < gimple_call_num_args (stmt); ++i)
3413             {
3414               tree arg = gimple_call_arg (stmt, i);
3415               while (handled_component_p (arg))
3416                 arg = TREE_OPERAND (arg, 0);
3417               if (TREE_CODE (arg) == MEM_REF
3418                   && TREE_OPERAND (arg, 0) == name
3419                   && integer_zerop (TREE_OPERAND (arg, 1))
3420                   && types_compatible_p (TREE_TYPE (arg),
3421                                          TREE_TYPE (TREE_TYPE (name)))
3422                   && !TREE_THIS_VOLATILE (arg))
3423                 uses_ok++;
3424             }
3425         }
3426
3427       /* If the number of valid uses does not match the number of
3428          uses in this stmt there is an unhandled use.  */
3429       FOR_EACH_IMM_USE_ON_STMT (use_p, ui)
3430         --uses_ok;
3431
3432       if (uses_ok != 0)
3433         ret = true;
3434
3435       if (ret)
3436         BREAK_FROM_IMM_USE_STMT (ui);
3437     }
3438
3439   return ret;
3440 }
3441
3442 /* Identify candidates for reduction for IPA-SRA based on their type and mark
3443    them in candidate_bitmap.  Note that these do not necessarily include
3444    parameter which are unused and thus can be removed.  Return true iff any
3445    such candidate has been found.  */
3446
3447 static bool
3448 find_param_candidates (void)
3449 {
3450   tree parm;
3451   int count = 0;
3452   bool ret = false;
3453   const char *msg;
3454
3455   for (parm = DECL_ARGUMENTS (current_function_decl);
3456        parm;
3457        parm = DECL_CHAIN (parm))
3458     {
3459       tree type = TREE_TYPE (parm);
3460
3461       count++;
3462
3463       if (TREE_THIS_VOLATILE (parm)
3464           || TREE_ADDRESSABLE (parm)
3465           || (!is_gimple_reg_type (type) && is_va_list_type (type)))
3466         continue;
3467
3468       if (is_unused_scalar_param (parm))
3469         {
3470           ret = true;
3471           continue;
3472         }
3473
3474       if (POINTER_TYPE_P (type))
3475         {
3476           type = TREE_TYPE (type);
3477
3478           if (TREE_CODE (type) == FUNCTION_TYPE
3479               || TYPE_VOLATILE (type)
3480               || (TREE_CODE (type) == ARRAY_TYPE
3481                   && TYPE_NONALIASED_COMPONENT (type))
3482               || !is_gimple_reg (parm)
3483               || is_va_list_type (type)
3484               || ptr_parm_has_direct_uses (parm))
3485             continue;
3486         }
3487       else if (!AGGREGATE_TYPE_P (type))
3488         continue;
3489
3490       if (!COMPLETE_TYPE_P (type)
3491           || !host_integerp (TYPE_SIZE (type), 1)
3492           || tree_low_cst (TYPE_SIZE (type), 1) == 0
3493           || (AGGREGATE_TYPE_P (type)
3494               && type_internals_preclude_sra_p (type, &msg)))
3495         continue;
3496
3497       bitmap_set_bit (candidate_bitmap, DECL_UID (parm));
3498       ret = true;
3499       if (dump_file && (dump_flags & TDF_DETAILS))
3500         {
3501           fprintf (dump_file, "Candidate (%d): ", DECL_UID (parm));
3502           print_generic_expr (dump_file, parm, 0);
3503           fprintf (dump_file, "\n");
3504         }
3505     }
3506
3507   func_param_count = count;
3508   return ret;
3509 }
3510
3511 /* Callback of walk_aliased_vdefs, marks the access passed as DATA as
3512    maybe_modified. */
3513
3514 static bool
3515 mark_maybe_modified (ao_ref *ao ATTRIBUTE_UNUSED, tree vdef ATTRIBUTE_UNUSED,
3516                      void *data)
3517 {
3518   struct access *repr = (struct access *) data;
3519
3520   repr->grp_maybe_m