OSDN Git Service

PR tree-optimization/33655
[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) 2003, 2004, 2005, 2006, 2007
5      Free Software Foundation, Inc.
6    Contributed by Diego Novillo <dnovillo@redhat.com>
7
8 This file is part of GCC.
9
10 GCC is free software; you can redistribute it and/or modify it
11 under the terms of the GNU General Public License as published by the
12 Free Software Foundation; either version 3, or (at your option) any
13 later version.
14
15 GCC is distributed in the hope that it will be useful, but WITHOUT
16 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
17 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
18 for more details.
19
20 You should have received a copy of the GNU General Public License
21 along with GCC; see the file COPYING3.  If not see
22 <http://www.gnu.org/licenses/>.  */
23
24 #include "config.h"
25 #include "system.h"
26 #include "coretypes.h"
27 #include "tm.h"
28 #include "ggc.h"
29 #include "tree.h"
30
31 /* These RTL headers are needed for basic-block.h.  */
32 #include "rtl.h"
33 #include "tm_p.h"
34 #include "hard-reg-set.h"
35 #include "basic-block.h"
36 #include "diagnostic.h"
37 #include "langhooks.h"
38 #include "tree-inline.h"
39 #include "tree-flow.h"
40 #include "tree-gimple.h"
41 #include "tree-dump.h"
42 #include "tree-pass.h"
43 #include "timevar.h"
44 #include "flags.h"
45 #include "bitmap.h"
46 #include "obstack.h"
47 #include "target.h"
48 /* expr.h is needed for MOVE_RATIO.  */
49 #include "expr.h"
50 #include "params.h"
51
52
53 /* This object of this pass is to replace a non-addressable aggregate with a
54    set of independent variables.  Most of the time, all of these variables
55    will be scalars.  But a secondary objective is to break up larger
56    aggregates into smaller aggregates.  In the process we may find that some
57    bits of the larger aggregate can be deleted as unreferenced.
58
59    This substitution is done globally.  More localized substitutions would
60    be the purvey of a load-store motion pass.
61
62    The optimization proceeds in phases:
63
64      (1) Identify variables that have types that are candidates for
65          decomposition.
66
67      (2) Scan the function looking for the ways these variables are used.
68          In particular we're interested in the number of times a variable
69          (or member) is needed as a complete unit, and the number of times
70          a variable (or member) is copied.
71
72      (3) Based on the usage profile, instantiate substitution variables.
73
74      (4) Scan the function making replacements.
75 */
76
77
78 /* True if this is the "early" pass, before inlining.  */
79 static bool early_sra;
80
81 /* The set of todo flags to return from tree_sra.  */
82 static unsigned int todoflags;
83
84 /* The set of aggregate variables that are candidates for scalarization.  */
85 static bitmap sra_candidates;
86
87 /* Set of scalarizable PARM_DECLs that need copy-in operations at the
88    beginning of the function.  */
89 static bitmap needs_copy_in;
90
91 /* Sets of bit pairs that cache type decomposition and instantiation.  */
92 static bitmap sra_type_decomp_cache;
93 static bitmap sra_type_inst_cache;
94
95 /* One of these structures is created for each candidate aggregate and
96    each (accessed) member or group of members of such an aggregate.  */
97 struct sra_elt
98 {
99   /* A tree of the elements.  Used when we want to traverse everything.  */
100   struct sra_elt *parent;
101   struct sra_elt *groups;
102   struct sra_elt *children;
103   struct sra_elt *sibling;
104
105   /* If this element is a root, then this is the VAR_DECL.  If this is
106      a sub-element, this is some token used to identify the reference.
107      In the case of COMPONENT_REF, this is the FIELD_DECL.  In the case
108      of an ARRAY_REF, this is the (constant) index.  In the case of an
109      ARRAY_RANGE_REF, this is the (constant) RANGE_EXPR.  In the case
110      of a complex number, this is a zero or one.  */
111   tree element;
112
113   /* The type of the element.  */
114   tree type;
115
116   /* A VAR_DECL, for any sub-element we've decided to replace.  */
117   tree replacement;
118
119   /* The number of times the element is referenced as a whole.  I.e.
120      given "a.b.c", this would be incremented for C, but not for A or B.  */
121   unsigned int n_uses;
122
123   /* The number of times the element is copied to or from another
124      scalarizable element.  */
125   unsigned int n_copies;
126
127   /* True if TYPE is scalar.  */
128   bool is_scalar;
129
130   /* True if this element is a group of members of its parent.  */
131   bool is_group;
132
133   /* True if we saw something about this element that prevents scalarization,
134      such as non-constant indexing.  */
135   bool cannot_scalarize;
136
137   /* True if we've decided that structure-to-structure assignment
138      should happen via memcpy and not per-element.  */
139   bool use_block_copy;
140
141   /* True if everything under this element has been marked TREE_NO_WARNING.  */
142   bool all_no_warning;
143
144   /* A flag for use with/after random access traversals.  */
145   bool visited;
146
147   /* True if there is BIT_FIELD_REF on the lhs with a vector. */
148   bool is_vector_lhs;
149
150   /* 1 if the element is a field that is part of a block, 2 if the field
151      is the block itself, 0 if it's neither.  */
152   char in_bitfld_block;
153 };
154
155 #define IS_ELEMENT_FOR_GROUP(ELEMENT) (TREE_CODE (ELEMENT) == RANGE_EXPR)
156
157 #define FOR_EACH_ACTUAL_CHILD(CHILD, ELT)                       \
158   for ((CHILD) = (ELT)->is_group                                \
159                  ? next_child_for_group (NULL, (ELT))           \
160                  : (ELT)->children;                             \
161        (CHILD);                                                 \
162        (CHILD) = (ELT)->is_group                                \
163                  ? next_child_for_group ((CHILD), (ELT))        \
164                  : (CHILD)->sibling)
165
166 /* Helper function for above macro.  Return next child in group.  */
167 static struct sra_elt *
168 next_child_for_group (struct sra_elt *child, struct sra_elt *group)
169 {
170   gcc_assert (group->is_group);
171
172   /* Find the next child in the parent.  */
173   if (child)
174     child = child->sibling;
175   else
176     child = group->parent->children;
177
178   /* Skip siblings that do not belong to the group.  */
179   while (child)
180     {
181       tree g_elt = group->element;
182       if (TREE_CODE (g_elt) == RANGE_EXPR)
183         {
184           if (!tree_int_cst_lt (child->element, TREE_OPERAND (g_elt, 0))
185               && !tree_int_cst_lt (TREE_OPERAND (g_elt, 1), child->element))
186             break;
187         }
188       else
189         gcc_unreachable ();
190
191       child = child->sibling;
192     }
193
194   return child;
195 }
196
197 /* Random access to the child of a parent is performed by hashing.
198    This prevents quadratic behavior, and allows SRA to function
199    reasonably on larger records.  */
200 static htab_t sra_map;
201
202 /* All structures are allocated out of the following obstack.  */
203 static struct obstack sra_obstack;
204
205 /* Debugging functions.  */
206 static void dump_sra_elt_name (FILE *, struct sra_elt *);
207 extern void debug_sra_elt_name (struct sra_elt *);
208
209 /* Forward declarations.  */
210 static tree generate_element_ref (struct sra_elt *);
211 static tree sra_build_assignment (tree dst, tree src);
212 static void mark_all_v_defs (tree list);
213
214 \f
215 /* Return true if DECL is an SRA candidate.  */
216
217 static bool
218 is_sra_candidate_decl (tree decl)
219 {
220   return DECL_P (decl) && bitmap_bit_p (sra_candidates, DECL_UID (decl));
221 }
222
223 /* Return true if TYPE is a scalar type.  */
224
225 static bool
226 is_sra_scalar_type (tree type)
227 {
228   enum tree_code code = TREE_CODE (type);
229   return (code == INTEGER_TYPE || code == REAL_TYPE || code == VECTOR_TYPE
230           || code == FIXED_POINT_TYPE
231           || code == ENUMERAL_TYPE || code == BOOLEAN_TYPE
232           || code == POINTER_TYPE || code == OFFSET_TYPE
233           || code == REFERENCE_TYPE);
234 }
235
236 /* Return true if TYPE can be decomposed into a set of independent variables.
237
238    Note that this doesn't imply that all elements of TYPE can be
239    instantiated, just that if we decide to break up the type into
240    separate pieces that it can be done.  */
241
242 bool
243 sra_type_can_be_decomposed_p (tree type)
244 {
245   unsigned int cache = TYPE_UID (TYPE_MAIN_VARIANT (type)) * 2;
246   tree t;
247
248   /* Avoid searching the same type twice.  */
249   if (bitmap_bit_p (sra_type_decomp_cache, cache+0))
250     return true;
251   if (bitmap_bit_p (sra_type_decomp_cache, cache+1))
252     return false;
253
254   /* The type must have a definite nonzero size.  */
255   if (TYPE_SIZE (type) == NULL || TREE_CODE (TYPE_SIZE (type)) != INTEGER_CST
256       || integer_zerop (TYPE_SIZE (type)))
257     goto fail;
258
259   /* The type must be a non-union aggregate.  */
260   switch (TREE_CODE (type))
261     {
262     case RECORD_TYPE:
263       {
264         bool saw_one_field = false;
265
266         for (t = TYPE_FIELDS (type); t ; t = TREE_CHAIN (t))
267           if (TREE_CODE (t) == FIELD_DECL)
268             {
269               /* Reject incorrectly represented bit fields.  */
270               if (DECL_BIT_FIELD (t)
271                   && (tree_low_cst (DECL_SIZE (t), 1)
272                       != TYPE_PRECISION (TREE_TYPE (t))))
273                 goto fail;
274
275               saw_one_field = true;
276             }
277
278         /* Record types must have at least one field.  */
279         if (!saw_one_field)
280           goto fail;
281       }
282       break;
283
284     case ARRAY_TYPE:
285       /* Array types must have a fixed lower and upper bound.  */
286       t = TYPE_DOMAIN (type);
287       if (t == NULL)
288         goto fail;
289       if (TYPE_MIN_VALUE (t) == NULL || !TREE_CONSTANT (TYPE_MIN_VALUE (t)))
290         goto fail;
291       if (TYPE_MAX_VALUE (t) == NULL || !TREE_CONSTANT (TYPE_MAX_VALUE (t)))
292         goto fail;
293       break;
294
295     case COMPLEX_TYPE:
296       break;
297
298     default:
299       goto fail;
300     }
301
302   bitmap_set_bit (sra_type_decomp_cache, cache+0);
303   return true;
304
305  fail:
306   bitmap_set_bit (sra_type_decomp_cache, cache+1);
307   return false;
308 }
309
310 /* Return true if DECL can be decomposed into a set of independent
311    (though not necessarily scalar) variables.  */
312
313 static bool
314 decl_can_be_decomposed_p (tree var)
315 {
316   /* Early out for scalars.  */
317   if (is_sra_scalar_type (TREE_TYPE (var)))
318     return false;
319
320   /* The variable must not be aliased.  */
321   if (!is_gimple_non_addressable (var))
322     {
323       if (dump_file && (dump_flags & TDF_DETAILS))
324         {
325           fprintf (dump_file, "Cannot scalarize variable ");
326           print_generic_expr (dump_file, var, dump_flags);
327           fprintf (dump_file, " because it must live in memory\n");
328         }
329       return false;
330     }
331
332   /* The variable must not be volatile.  */
333   if (TREE_THIS_VOLATILE (var))
334     {
335       if (dump_file && (dump_flags & TDF_DETAILS))
336         {
337           fprintf (dump_file, "Cannot scalarize variable ");
338           print_generic_expr (dump_file, var, dump_flags);
339           fprintf (dump_file, " because it is declared volatile\n");
340         }
341       return false;
342     }
343
344   /* We must be able to decompose the variable's type.  */
345   if (!sra_type_can_be_decomposed_p (TREE_TYPE (var)))
346     {
347       if (dump_file && (dump_flags & TDF_DETAILS))
348         {
349           fprintf (dump_file, "Cannot scalarize variable ");
350           print_generic_expr (dump_file, var, dump_flags);
351           fprintf (dump_file, " because its type cannot be decomposed\n");
352         }
353       return false;
354     }
355
356   /* HACK: if we decompose a va_list_type_node before inlining, then we'll
357      confuse tree-stdarg.c, and we won't be able to figure out which and
358      how many arguments are accessed.  This really should be improved in
359      tree-stdarg.c, as the decomposition is truely a win.  This could also
360      be fixed if the stdarg pass ran early, but this can't be done until
361      we've aliasing information early too.  See PR 30791.  */
362   if (early_sra
363       && TYPE_MAIN_VARIANT (TREE_TYPE (var))
364          == TYPE_MAIN_VARIANT (va_list_type_node))
365     return false;
366
367   return true;
368 }
369
370 /* Return true if TYPE can be *completely* decomposed into scalars.  */
371
372 static bool
373 type_can_instantiate_all_elements (tree type)
374 {
375   if (is_sra_scalar_type (type))
376     return true;
377   if (!sra_type_can_be_decomposed_p (type))
378     return false;
379
380   switch (TREE_CODE (type))
381     {
382     case RECORD_TYPE:
383       {
384         unsigned int cache = TYPE_UID (TYPE_MAIN_VARIANT (type)) * 2;
385         tree f;
386
387         if (bitmap_bit_p (sra_type_inst_cache, cache+0))
388           return true;
389         if (bitmap_bit_p (sra_type_inst_cache, cache+1))
390           return false;
391
392         for (f = TYPE_FIELDS (type); f ; f = TREE_CHAIN (f))
393           if (TREE_CODE (f) == FIELD_DECL)
394             {
395               if (!type_can_instantiate_all_elements (TREE_TYPE (f)))
396                 {
397                   bitmap_set_bit (sra_type_inst_cache, cache+1);
398                   return false;
399                 }
400             }
401
402         bitmap_set_bit (sra_type_inst_cache, cache+0);
403         return true;
404       }
405
406     case ARRAY_TYPE:
407       return type_can_instantiate_all_elements (TREE_TYPE (type));
408
409     case COMPLEX_TYPE:
410       return true;
411
412     default:
413       gcc_unreachable ();
414     }
415 }
416
417 /* Test whether ELT or some sub-element cannot be scalarized.  */
418
419 static bool
420 can_completely_scalarize_p (struct sra_elt *elt)
421 {
422   struct sra_elt *c;
423
424   if (elt->cannot_scalarize)
425     return false;
426
427   for (c = elt->children; c; c = c->sibling)
428     if (!can_completely_scalarize_p (c))
429       return false;
430
431   for (c = elt->groups; c; c = c->sibling)
432     if (!can_completely_scalarize_p (c))
433       return false;
434
435   return true;
436 }
437
438 \f
439 /* A simplified tree hashing algorithm that only handles the types of
440    trees we expect to find in sra_elt->element.  */
441
442 static hashval_t
443 sra_hash_tree (tree t)
444 {
445   hashval_t h;
446
447   switch (TREE_CODE (t))
448     {
449     case VAR_DECL:
450     case PARM_DECL:
451     case RESULT_DECL:
452       h = DECL_UID (t);
453       break;
454
455     case INTEGER_CST:
456       h = TREE_INT_CST_LOW (t) ^ TREE_INT_CST_HIGH (t);
457       break;
458
459     case RANGE_EXPR:
460       h = iterative_hash_expr (TREE_OPERAND (t, 0), 0);
461       h = iterative_hash_expr (TREE_OPERAND (t, 1), h);
462       break;
463
464     case FIELD_DECL:
465       /* We can have types that are compatible, but have different member
466          lists, so we can't hash fields by ID.  Use offsets instead.  */
467       h = iterative_hash_expr (DECL_FIELD_OFFSET (t), 0);
468       h = iterative_hash_expr (DECL_FIELD_BIT_OFFSET (t), h);
469       break;
470
471     case BIT_FIELD_REF:
472       /* Don't take operand 0 into account, that's our parent.  */
473       h = iterative_hash_expr (TREE_OPERAND (t, 1), 0);
474       h = iterative_hash_expr (TREE_OPERAND (t, 2), h);
475       break;
476
477     default:
478       gcc_unreachable ();
479     }
480
481   return h;
482 }
483
484 /* Hash function for type SRA_PAIR.  */
485
486 static hashval_t
487 sra_elt_hash (const void *x)
488 {
489   const struct sra_elt *e = x;
490   const struct sra_elt *p;
491   hashval_t h;
492
493   h = sra_hash_tree (e->element);
494
495   /* Take into account everything except bitfield blocks back up the
496      chain.  Given that chain lengths are rarely very long, this
497      should be acceptable.  If we truly identify this as a performance
498      problem, it should work to hash the pointer value
499      "e->parent".  */
500   for (p = e->parent; p ; p = p->parent)
501     if (!p->in_bitfld_block)
502       h = (h * 65521) ^ sra_hash_tree (p->element);
503
504   return h;
505 }
506
507 /* Equality function for type SRA_PAIR.  */
508
509 static int
510 sra_elt_eq (const void *x, const void *y)
511 {
512   const struct sra_elt *a = x;
513   const struct sra_elt *b = y;
514   tree ae, be;
515   const struct sra_elt *ap = a->parent;
516   const struct sra_elt *bp = b->parent;
517
518   if (ap)
519     while (ap->in_bitfld_block)
520       ap = ap->parent;
521   if (bp)
522     while (bp->in_bitfld_block)
523       bp = bp->parent;
524
525   if (ap != bp)
526     return false;
527
528   ae = a->element;
529   be = b->element;
530
531   if (ae == be)
532     return true;
533   if (TREE_CODE (ae) != TREE_CODE (be))
534     return false;
535
536   switch (TREE_CODE (ae))
537     {
538     case VAR_DECL:
539     case PARM_DECL:
540     case RESULT_DECL:
541       /* These are all pointer unique.  */
542       return false;
543
544     case INTEGER_CST:
545       /* Integers are not pointer unique, so compare their values.  */
546       return tree_int_cst_equal (ae, be);
547
548     case RANGE_EXPR:
549       return
550         tree_int_cst_equal (TREE_OPERAND (ae, 0), TREE_OPERAND (be, 0))
551         && tree_int_cst_equal (TREE_OPERAND (ae, 1), TREE_OPERAND (be, 1));
552
553     case FIELD_DECL:
554       /* Fields are unique within a record, but not between
555          compatible records.  */
556       if (DECL_FIELD_CONTEXT (ae) == DECL_FIELD_CONTEXT (be))
557         return false;
558       return fields_compatible_p (ae, be);
559
560     case BIT_FIELD_REF:
561       return
562         tree_int_cst_equal (TREE_OPERAND (ae, 1), TREE_OPERAND (be, 1))
563         && tree_int_cst_equal (TREE_OPERAND (ae, 2), TREE_OPERAND (be, 2));
564
565     default:
566       gcc_unreachable ();
567     }
568 }
569
570 /* Create or return the SRA_ELT structure for CHILD in PARENT.  PARENT
571    may be null, in which case CHILD must be a DECL.  */
572
573 static struct sra_elt *
574 lookup_element (struct sra_elt *parent, tree child, tree type,
575                 enum insert_option insert)
576 {
577   struct sra_elt dummy;
578   struct sra_elt **slot;
579   struct sra_elt *elt;
580
581   if (parent)
582     dummy.parent = parent->is_group ? parent->parent : parent;
583   else
584     dummy.parent = NULL;
585   dummy.element = child;
586
587   slot = (struct sra_elt **) htab_find_slot (sra_map, &dummy, insert);
588   if (!slot && insert == NO_INSERT)
589     return NULL;
590
591   elt = *slot;
592   if (!elt && insert == INSERT)
593     {
594       *slot = elt = obstack_alloc (&sra_obstack, sizeof (*elt));
595       memset (elt, 0, sizeof (*elt));
596
597       elt->parent = parent;
598       elt->element = child;
599       elt->type = type;
600       elt->is_scalar = is_sra_scalar_type (type);
601
602       if (parent)
603         {
604           if (IS_ELEMENT_FOR_GROUP (elt->element))
605             {
606               elt->is_group = true;
607               elt->sibling = parent->groups;
608               parent->groups = elt;
609             }
610           else
611             {
612               elt->sibling = parent->children;
613               parent->children = elt;
614             }
615         }
616
617       /* If this is a parameter, then if we want to scalarize, we have
618          one copy from the true function parameter.  Count it now.  */
619       if (TREE_CODE (child) == PARM_DECL)
620         {
621           elt->n_copies = 1;
622           bitmap_set_bit (needs_copy_in, DECL_UID (child));
623         }
624     }
625
626   return elt;
627 }
628
629 /* Create or return the SRA_ELT structure for EXPR if the expression
630    refers to a scalarizable variable.  */
631
632 static struct sra_elt *
633 maybe_lookup_element_for_expr (tree expr)
634 {
635   struct sra_elt *elt;
636   tree child;
637
638   switch (TREE_CODE (expr))
639     {
640     case VAR_DECL:
641     case PARM_DECL:
642     case RESULT_DECL:
643       if (is_sra_candidate_decl (expr))
644         return lookup_element (NULL, expr, TREE_TYPE (expr), INSERT);
645       return NULL;
646
647     case ARRAY_REF:
648       /* We can't scalarize variable array indices.  */
649       if (in_array_bounds_p (expr))
650         child = TREE_OPERAND (expr, 1);
651       else
652         return NULL;
653       break;
654
655     case ARRAY_RANGE_REF:
656       /* We can't scalarize variable array indices.  */
657       if (range_in_array_bounds_p (expr))
658         {
659           tree domain = TYPE_DOMAIN (TREE_TYPE (expr));
660           child = build2 (RANGE_EXPR, integer_type_node,
661                           TYPE_MIN_VALUE (domain), TYPE_MAX_VALUE (domain));
662         }
663       else
664         return NULL;
665       break;
666
667     case COMPONENT_REF:
668       {
669         tree type = TREE_TYPE (TREE_OPERAND (expr, 0));
670         /* Don't look through unions.  */
671         if (TREE_CODE (type) != RECORD_TYPE)
672           return NULL;
673         /* Neither through variable-sized records.  */
674         if (TYPE_SIZE (type) == NULL_TREE
675             || TREE_CODE (TYPE_SIZE (type)) != INTEGER_CST)
676           return NULL;
677         child = TREE_OPERAND (expr, 1);
678       }
679       break;
680
681     case REALPART_EXPR:
682       child = integer_zero_node;
683       break;
684     case IMAGPART_EXPR:
685       child = integer_one_node;
686       break;
687
688     default:
689       return NULL;
690     }
691
692   elt = maybe_lookup_element_for_expr (TREE_OPERAND (expr, 0));
693   if (elt)
694     return lookup_element (elt, child, TREE_TYPE (expr), INSERT);
695   return NULL;
696 }
697
698 \f
699 /* Functions to walk just enough of the tree to see all scalarizable
700    references, and categorize them.  */
701
702 /* A set of callbacks for phases 2 and 4.  They'll be invoked for the
703    various kinds of references seen.  In all cases, *BSI is an iterator
704    pointing to the statement being processed.  */
705 struct sra_walk_fns
706 {
707   /* Invoked when ELT is required as a unit.  Note that ELT might refer to
708      a leaf node, in which case this is a simple scalar reference.  *EXPR_P
709      points to the location of the expression.  IS_OUTPUT is true if this
710      is a left-hand-side reference.  USE_ALL is true if we saw something we
711      couldn't quite identify and had to force the use of the entire object.  */
712   void (*use) (struct sra_elt *elt, tree *expr_p,
713                block_stmt_iterator *bsi, bool is_output, bool use_all);
714
715   /* Invoked when we have a copy between two scalarizable references.  */
716   void (*copy) (struct sra_elt *lhs_elt, struct sra_elt *rhs_elt,
717                 block_stmt_iterator *bsi);
718
719   /* Invoked when ELT is initialized from a constant.  VALUE may be NULL,
720      in which case it should be treated as an empty CONSTRUCTOR.  */
721   void (*init) (struct sra_elt *elt, tree value, block_stmt_iterator *bsi);
722
723   /* Invoked when we have a copy between one scalarizable reference ELT
724      and one non-scalarizable reference OTHER without side-effects. 
725      IS_OUTPUT is true if ELT is on the left-hand side.  */
726   void (*ldst) (struct sra_elt *elt, tree other,
727                 block_stmt_iterator *bsi, bool is_output);
728
729   /* True during phase 2, false during phase 4.  */
730   /* ??? This is a hack.  */
731   bool initial_scan;
732 };
733
734 #ifdef ENABLE_CHECKING
735 /* Invoked via walk_tree, if *TP contains a candidate decl, return it.  */
736
737 static tree
738 sra_find_candidate_decl (tree *tp, int *walk_subtrees,
739                          void *data ATTRIBUTE_UNUSED)
740 {
741   tree t = *tp;
742   enum tree_code code = TREE_CODE (t);
743
744   if (code == VAR_DECL || code == PARM_DECL || code == RESULT_DECL)
745     {
746       *walk_subtrees = 0;
747       if (is_sra_candidate_decl (t))
748         return t;
749     }
750   else if (TYPE_P (t))
751     *walk_subtrees = 0;
752
753   return NULL;
754 }
755 #endif
756
757 /* Walk most expressions looking for a scalarizable aggregate.
758    If we find one, invoke FNS->USE.  */
759
760 static void
761 sra_walk_expr (tree *expr_p, block_stmt_iterator *bsi, bool is_output,
762                const struct sra_walk_fns *fns)
763 {
764   tree expr = *expr_p;
765   tree inner = expr;
766   bool disable_scalarization = false;
767   bool use_all_p = false;
768
769   /* We're looking to collect a reference expression between EXPR and INNER,
770      such that INNER is a scalarizable decl and all other nodes through EXPR
771      are references that we can scalarize.  If we come across something that
772      we can't scalarize, we reset EXPR.  This has the effect of making it
773      appear that we're referring to the larger expression as a whole.  */
774
775   while (1)
776     switch (TREE_CODE (inner))
777       {
778       case VAR_DECL:
779       case PARM_DECL:
780       case RESULT_DECL:
781         /* If there is a scalarizable decl at the bottom, then process it.  */
782         if (is_sra_candidate_decl (inner))
783           {
784             struct sra_elt *elt = maybe_lookup_element_for_expr (expr);
785             if (disable_scalarization)
786               elt->cannot_scalarize = true;
787             else
788               fns->use (elt, expr_p, bsi, is_output, use_all_p);
789           }
790         return;
791
792       case ARRAY_REF:
793         /* Non-constant index means any member may be accessed.  Prevent the
794            expression from being scalarized.  If we were to treat this as a
795            reference to the whole array, we can wind up with a single dynamic
796            index reference inside a loop being overridden by several constant
797            index references during loop setup.  It's possible that this could
798            be avoided by using dynamic usage counts based on BB trip counts
799            (based on loop analysis or profiling), but that hardly seems worth
800            the effort.  */
801         /* ??? Hack.  Figure out how to push this into the scan routines
802            without duplicating too much code.  */
803         if (!in_array_bounds_p (inner))
804           {
805             disable_scalarization = true;
806             goto use_all;
807           }
808         /* ??? Are we assured that non-constant bounds and stride will have
809            the same value everywhere?  I don't think Fortran will...  */
810         if (TREE_OPERAND (inner, 2) || TREE_OPERAND (inner, 3))
811           goto use_all;
812         inner = TREE_OPERAND (inner, 0);
813         break;
814
815       case ARRAY_RANGE_REF:
816         if (!range_in_array_bounds_p (inner))
817           {
818             disable_scalarization = true;
819             goto use_all;
820           }
821         /* ??? See above non-constant bounds and stride .  */
822         if (TREE_OPERAND (inner, 2) || TREE_OPERAND (inner, 3))
823           goto use_all;
824         inner = TREE_OPERAND (inner, 0);
825         break;
826
827       case COMPONENT_REF:
828         {
829           tree type = TREE_TYPE (TREE_OPERAND (inner, 0));
830           /* Don't look through unions.  */
831           if (TREE_CODE (type) != RECORD_TYPE)
832             goto use_all;
833           /* Neither through variable-sized records.  */
834           if (TYPE_SIZE (type) == NULL_TREE
835               || TREE_CODE (TYPE_SIZE (type)) != INTEGER_CST)
836             goto use_all;
837           inner = TREE_OPERAND (inner, 0);
838         }
839         break;
840
841       case REALPART_EXPR:
842       case IMAGPART_EXPR:
843         inner = TREE_OPERAND (inner, 0);
844         break;
845
846       case BIT_FIELD_REF:
847         /* A bit field reference to a specific vector is scalarized but for
848            ones for inputs need to be marked as used on the left hand size so
849            when we scalarize it, we can mark that variable as non renamable.  */
850         if (is_output
851             && TREE_CODE (TREE_TYPE (TREE_OPERAND (inner, 0))) == VECTOR_TYPE)
852           {
853             struct sra_elt *elt
854               = maybe_lookup_element_for_expr (TREE_OPERAND (inner, 0));
855             if (elt)
856               elt->is_vector_lhs = true;
857           }
858         /* A bit field reference (access to *multiple* fields simultaneously)
859            is not currently scalarized.  Consider this an access to the
860            complete outer element, to which walk_tree will bring us next.  */
861           
862         goto use_all;
863
864       case VIEW_CONVERT_EXPR:
865       case NOP_EXPR:
866         /* Similarly, a view/nop explicitly wants to look at an object in a
867            type other than the one we've scalarized.  */
868         goto use_all;
869
870       case WITH_SIZE_EXPR:
871         /* This is a transparent wrapper.  The entire inner expression really
872            is being used.  */
873         goto use_all;
874
875       use_all:
876         expr_p = &TREE_OPERAND (inner, 0);
877         inner = expr = *expr_p;
878         use_all_p = true;
879         break;
880
881       default:
882 #ifdef ENABLE_CHECKING
883         /* Validate that we're not missing any references.  */
884         gcc_assert (!walk_tree (&inner, sra_find_candidate_decl, NULL, NULL));
885 #endif
886         return;
887       }
888 }
889
890 /* Walk a TREE_LIST of values looking for scalarizable aggregates.
891    If we find one, invoke FNS->USE.  */
892
893 static void
894 sra_walk_tree_list (tree list, block_stmt_iterator *bsi, bool is_output,
895                     const struct sra_walk_fns *fns)
896 {
897   tree op;
898   for (op = list; op ; op = TREE_CHAIN (op))
899     sra_walk_expr (&TREE_VALUE (op), bsi, is_output, fns);
900 }
901
902 /* Walk the arguments of a CALL_EXPR looking for scalarizable aggregates.
903    If we find one, invoke FNS->USE.  */
904
905 static void
906 sra_walk_call_expr (tree expr, block_stmt_iterator *bsi,
907                     const struct sra_walk_fns *fns)
908 {
909   int i;
910   int nargs = call_expr_nargs (expr);
911   for (i = 0; i < nargs; i++)
912     sra_walk_expr (&CALL_EXPR_ARG (expr, i), bsi, false, fns);
913 }
914
915 /* Walk the inputs and outputs of an ASM_EXPR looking for scalarizable
916    aggregates.  If we find one, invoke FNS->USE.  */
917
918 static void
919 sra_walk_asm_expr (tree expr, block_stmt_iterator *bsi,
920                    const struct sra_walk_fns *fns)
921 {
922   sra_walk_tree_list (ASM_INPUTS (expr), bsi, false, fns);
923   sra_walk_tree_list (ASM_OUTPUTS (expr), bsi, true, fns);
924 }
925
926 /* Walk a GIMPLE_MODIFY_STMT and categorize the assignment appropriately.  */
927
928 static void
929 sra_walk_gimple_modify_stmt (tree expr, block_stmt_iterator *bsi,
930                              const struct sra_walk_fns *fns)
931 {
932   struct sra_elt *lhs_elt, *rhs_elt;
933   tree lhs, rhs;
934
935   lhs = GIMPLE_STMT_OPERAND (expr, 0);
936   rhs = GIMPLE_STMT_OPERAND (expr, 1);
937   lhs_elt = maybe_lookup_element_for_expr (lhs);
938   rhs_elt = maybe_lookup_element_for_expr (rhs);
939
940   /* If both sides are scalarizable, this is a COPY operation.  */
941   if (lhs_elt && rhs_elt)
942     {
943       fns->copy (lhs_elt, rhs_elt, bsi);
944       return;
945     }
946
947   /* If the RHS is scalarizable, handle it.  There are only two cases.  */
948   if (rhs_elt)
949     {
950       if (!rhs_elt->is_scalar && !TREE_SIDE_EFFECTS (lhs))
951         fns->ldst (rhs_elt, lhs, bsi, false);
952       else
953         fns->use (rhs_elt, &GIMPLE_STMT_OPERAND (expr, 1), bsi, false, false);
954     }
955
956   /* If it isn't scalarizable, there may be scalarizable variables within, so
957      check for a call or else walk the RHS to see if we need to do any
958      copy-in operations.  We need to do it before the LHS is scalarized so
959      that the statements get inserted in the proper place, before any
960      copy-out operations.  */
961   else
962     {
963       tree call = get_call_expr_in (rhs);
964       if (call)
965         sra_walk_call_expr (call, bsi, fns);
966       else
967         sra_walk_expr (&GIMPLE_STMT_OPERAND (expr, 1), bsi, false, fns);
968     }
969
970   /* Likewise, handle the LHS being scalarizable.  We have cases similar
971      to those above, but also want to handle RHS being constant.  */
972   if (lhs_elt)
973     {
974       /* If this is an assignment from a constant, or constructor, then
975          we have access to all of the elements individually.  Invoke INIT.  */
976       if (TREE_CODE (rhs) == COMPLEX_EXPR
977           || TREE_CODE (rhs) == COMPLEX_CST
978           || TREE_CODE (rhs) == CONSTRUCTOR)
979         fns->init (lhs_elt, rhs, bsi);
980
981       /* If this is an assignment from read-only memory, treat this as if
982          we'd been passed the constructor directly.  Invoke INIT.  */
983       else if (TREE_CODE (rhs) == VAR_DECL
984                && TREE_STATIC (rhs)
985                && TREE_READONLY (rhs)
986                && targetm.binds_local_p (rhs))
987         fns->init (lhs_elt, DECL_INITIAL (rhs), bsi);
988
989       /* If this is a copy from a non-scalarizable lvalue, invoke LDST.
990          The lvalue requirement prevents us from trying to directly scalarize
991          the result of a function call.  Which would result in trying to call
992          the function multiple times, and other evil things.  */
993       else if (!lhs_elt->is_scalar
994                && !TREE_SIDE_EFFECTS (rhs) && is_gimple_addressable (rhs))
995         fns->ldst (lhs_elt, rhs, bsi, true);
996
997       /* Otherwise we're being used in some context that requires the
998          aggregate to be seen as a whole.  Invoke USE.  */
999       else
1000         fns->use (lhs_elt, &GIMPLE_STMT_OPERAND (expr, 0), bsi, true, false);
1001     }
1002
1003   /* Similarly to above, LHS_ELT being null only means that the LHS as a
1004      whole is not a scalarizable reference.  There may be occurrences of
1005      scalarizable variables within, which implies a USE.  */
1006   else
1007     sra_walk_expr (&GIMPLE_STMT_OPERAND (expr, 0), bsi, true, fns);
1008 }
1009
1010 /* Entry point to the walk functions.  Search the entire function,
1011    invoking the callbacks in FNS on each of the references to
1012    scalarizable variables.  */
1013
1014 static void
1015 sra_walk_function (const struct sra_walk_fns *fns)
1016 {
1017   basic_block bb;
1018   block_stmt_iterator si, ni;
1019
1020   /* ??? Phase 4 could derive some benefit to walking the function in
1021      dominator tree order.  */
1022
1023   FOR_EACH_BB (bb)
1024     for (si = bsi_start (bb); !bsi_end_p (si); si = ni)
1025       {
1026         tree stmt, t;
1027         stmt_ann_t ann;
1028
1029         stmt = bsi_stmt (si);
1030         ann = stmt_ann (stmt);
1031
1032         ni = si;
1033         bsi_next (&ni);
1034
1035         /* If the statement has no virtual operands, then it doesn't
1036            make any structure references that we care about.  */
1037         if (gimple_aliases_computed_p (cfun)
1038             && ZERO_SSA_OPERANDS (stmt, (SSA_OP_VIRTUAL_DEFS | SSA_OP_VUSE)))
1039               continue;
1040
1041         switch (TREE_CODE (stmt))
1042           {
1043           case RETURN_EXPR:
1044             /* If we have "return <retval>" then the return value is
1045                already exposed for our pleasure.  Walk it as a USE to
1046                force all the components back in place for the return.
1047
1048                If we have an embedded assignment, then <retval> is of
1049                a type that gets returned in registers in this ABI, and
1050                we do not wish to extend their lifetimes.  Treat this
1051                as a USE of the variable on the RHS of this assignment.  */
1052
1053             t = TREE_OPERAND (stmt, 0);
1054             if (t == NULL_TREE)
1055               ;
1056             else if (TREE_CODE (t) == GIMPLE_MODIFY_STMT)
1057               sra_walk_expr (&GIMPLE_STMT_OPERAND (t, 1), &si, false, fns);
1058             else
1059               sra_walk_expr (&TREE_OPERAND (stmt, 0), &si, false, fns);
1060             break;
1061
1062           case GIMPLE_MODIFY_STMT:
1063             sra_walk_gimple_modify_stmt (stmt, &si, fns);
1064             break;
1065           case CALL_EXPR:
1066             sra_walk_call_expr (stmt, &si, fns);
1067             break;
1068           case ASM_EXPR:
1069             sra_walk_asm_expr (stmt, &si, fns);
1070             break;
1071
1072           default:
1073             break;
1074           }
1075       }
1076 }
1077 \f
1078 /* Phase One: Scan all referenced variables in the program looking for
1079    structures that could be decomposed.  */
1080
1081 static bool
1082 find_candidates_for_sra (void)
1083 {
1084   bool any_set = false;
1085   tree var;
1086   referenced_var_iterator rvi;
1087
1088   FOR_EACH_REFERENCED_VAR (var, rvi)
1089     {
1090       if (decl_can_be_decomposed_p (var))
1091         {
1092           bitmap_set_bit (sra_candidates, DECL_UID (var));
1093           any_set = true;
1094         }
1095     }
1096
1097   return any_set;
1098 }
1099
1100 \f
1101 /* Phase Two: Scan all references to scalarizable variables.  Count the
1102    number of times they are used or copied respectively.  */
1103
1104 /* Callbacks to fill in SRA_WALK_FNS.  Everything but USE is
1105    considered a copy, because we can decompose the reference such that
1106    the sub-elements needn't be contiguous.  */
1107
1108 static void
1109 scan_use (struct sra_elt *elt, tree *expr_p ATTRIBUTE_UNUSED,
1110           block_stmt_iterator *bsi ATTRIBUTE_UNUSED,
1111           bool is_output ATTRIBUTE_UNUSED, bool use_all ATTRIBUTE_UNUSED)
1112 {
1113   elt->n_uses += 1;
1114 }
1115
1116 static void
1117 scan_copy (struct sra_elt *lhs_elt, struct sra_elt *rhs_elt,
1118            block_stmt_iterator *bsi ATTRIBUTE_UNUSED)
1119 {
1120   lhs_elt->n_copies += 1;
1121   rhs_elt->n_copies += 1;
1122 }
1123
1124 static void
1125 scan_init (struct sra_elt *lhs_elt, tree rhs ATTRIBUTE_UNUSED,
1126            block_stmt_iterator *bsi ATTRIBUTE_UNUSED)
1127 {
1128   lhs_elt->n_copies += 1;
1129 }
1130
1131 static void
1132 scan_ldst (struct sra_elt *elt, tree other ATTRIBUTE_UNUSED,
1133            block_stmt_iterator *bsi ATTRIBUTE_UNUSED,
1134            bool is_output ATTRIBUTE_UNUSED)
1135 {
1136   elt->n_copies += 1;
1137 }
1138
1139 /* Dump the values we collected during the scanning phase.  */
1140
1141 static void
1142 scan_dump (struct sra_elt *elt)
1143 {
1144   struct sra_elt *c;
1145
1146   dump_sra_elt_name (dump_file, elt);
1147   fprintf (dump_file, ": n_uses=%u n_copies=%u\n", elt->n_uses, elt->n_copies);
1148
1149   for (c = elt->children; c ; c = c->sibling)
1150     scan_dump (c);
1151
1152   for (c = elt->groups; c ; c = c->sibling)
1153     scan_dump (c);
1154 }
1155
1156 /* Entry point to phase 2.  Scan the entire function, building up
1157    scalarization data structures, recording copies and uses.  */
1158
1159 static void
1160 scan_function (void)
1161 {
1162   static const struct sra_walk_fns fns = {
1163     scan_use, scan_copy, scan_init, scan_ldst, true
1164   };
1165   bitmap_iterator bi;
1166
1167   sra_walk_function (&fns);
1168
1169   if (dump_file && (dump_flags & TDF_DETAILS))
1170     {
1171       unsigned i;
1172
1173       fputs ("\nScan results:\n", dump_file);
1174       EXECUTE_IF_SET_IN_BITMAP (sra_candidates, 0, i, bi)
1175         {
1176           tree var = referenced_var (i);
1177           struct sra_elt *elt = lookup_element (NULL, var, NULL, NO_INSERT);
1178           if (elt)
1179             scan_dump (elt);
1180         }
1181       fputc ('\n', dump_file);
1182     }
1183 }
1184 \f
1185 /* Phase Three: Make decisions about which variables to scalarize, if any.
1186    All elements to be scalarized have replacement variables made for them.  */
1187
1188 /* A subroutine of build_element_name.  Recursively build the element
1189    name on the obstack.  */
1190
1191 static void
1192 build_element_name_1 (struct sra_elt *elt)
1193 {
1194   tree t;
1195   char buffer[32];
1196
1197   if (elt->parent)
1198     {
1199       build_element_name_1 (elt->parent);
1200       obstack_1grow (&sra_obstack, '$');
1201
1202       if (TREE_CODE (elt->parent->type) == COMPLEX_TYPE)
1203         {
1204           if (elt->element == integer_zero_node)
1205             obstack_grow (&sra_obstack, "real", 4);
1206           else
1207             obstack_grow (&sra_obstack, "imag", 4);
1208           return;
1209         }
1210     }
1211
1212   t = elt->element;
1213   if (TREE_CODE (t) == INTEGER_CST)
1214     {
1215       /* ??? Eh.  Don't bother doing double-wide printing.  */
1216       sprintf (buffer, HOST_WIDE_INT_PRINT_DEC, TREE_INT_CST_LOW (t));
1217       obstack_grow (&sra_obstack, buffer, strlen (buffer));
1218     }
1219   else if (TREE_CODE (t) == BIT_FIELD_REF)
1220     {
1221       sprintf (buffer, "B" HOST_WIDE_INT_PRINT_DEC,
1222                tree_low_cst (TREE_OPERAND (t, 2), 1));
1223       obstack_grow (&sra_obstack, buffer, strlen (buffer));
1224       sprintf (buffer, "F" HOST_WIDE_INT_PRINT_DEC,
1225                tree_low_cst (TREE_OPERAND (t, 1), 1));
1226       obstack_grow (&sra_obstack, buffer, strlen (buffer));
1227     }
1228   else
1229     {
1230       tree name = DECL_NAME (t);
1231       if (name)
1232         obstack_grow (&sra_obstack, IDENTIFIER_POINTER (name),
1233                       IDENTIFIER_LENGTH (name));
1234       else
1235         {
1236           sprintf (buffer, "D%u", DECL_UID (t));
1237           obstack_grow (&sra_obstack, buffer, strlen (buffer));
1238         }
1239     }
1240 }
1241
1242 /* Construct a pretty variable name for an element's replacement variable.
1243    The name is built on the obstack.  */
1244
1245 static char *
1246 build_element_name (struct sra_elt *elt)
1247 {
1248   build_element_name_1 (elt);
1249   obstack_1grow (&sra_obstack, '\0');
1250   return XOBFINISH (&sra_obstack, char *);
1251 }
1252
1253 /* Instantiate an element as an independent variable.  */
1254
1255 static void
1256 instantiate_element (struct sra_elt *elt)
1257 {
1258   struct sra_elt *base_elt;
1259   tree var, base;
1260   bool nowarn = TREE_NO_WARNING (elt->element);
1261
1262   for (base_elt = elt; base_elt->parent; base_elt = base_elt->parent)
1263     if (!nowarn)
1264       nowarn = TREE_NO_WARNING (base_elt->parent->element);
1265   base = base_elt->element;
1266
1267   elt->replacement = var = make_rename_temp (elt->type, "SR");
1268
1269   if (DECL_P (elt->element)
1270       && !tree_int_cst_equal (DECL_SIZE (var), DECL_SIZE (elt->element)))
1271     {
1272       DECL_SIZE (var) = DECL_SIZE (elt->element);
1273       DECL_SIZE_UNIT (var) = DECL_SIZE_UNIT (elt->element);
1274
1275       elt->in_bitfld_block = 1;
1276       elt->replacement = build3 (BIT_FIELD_REF, elt->type, var,
1277                                  DECL_SIZE (var),
1278                                  BYTES_BIG_ENDIAN
1279                                  ? size_binop (MINUS_EXPR,
1280                                                TYPE_SIZE (elt->type),
1281                                                DECL_SIZE (var))
1282                                  : bitsize_int (0));
1283       if (!INTEGRAL_TYPE_P (elt->type)
1284           || TYPE_UNSIGNED (elt->type))
1285         BIT_FIELD_REF_UNSIGNED (elt->replacement) = 1;
1286     }
1287
1288   /* For vectors, if used on the left hand side with BIT_FIELD_REF,
1289      they are not a gimple register.  */
1290   if (TREE_CODE (TREE_TYPE (var)) == VECTOR_TYPE && elt->is_vector_lhs)
1291     DECL_GIMPLE_REG_P (var) = 0;
1292
1293   DECL_SOURCE_LOCATION (var) = DECL_SOURCE_LOCATION (base);
1294   DECL_ARTIFICIAL (var) = 1;
1295
1296   if (TREE_THIS_VOLATILE (elt->type))
1297     {
1298       TREE_THIS_VOLATILE (var) = 1;
1299       TREE_SIDE_EFFECTS (var) = 1;
1300     }
1301
1302   if (DECL_NAME (base) && !DECL_IGNORED_P (base))
1303     {
1304       char *pretty_name = build_element_name (elt);
1305       DECL_NAME (var) = get_identifier (pretty_name);
1306       obstack_free (&sra_obstack, pretty_name);
1307
1308       SET_DECL_DEBUG_EXPR (var, generate_element_ref (elt));
1309       DECL_DEBUG_EXPR_IS_FROM (var) = 1;
1310       
1311       DECL_IGNORED_P (var) = 0;
1312       TREE_NO_WARNING (var) = nowarn;
1313     }
1314   else
1315     {
1316       DECL_IGNORED_P (var) = 1;
1317       /* ??? We can't generate any warning that would be meaningful.  */
1318       TREE_NO_WARNING (var) = 1;
1319     }
1320
1321   /* Zero-initialize bit-field scalarization variables, to avoid
1322      triggering undefined behavior.  */
1323   if (TREE_CODE (elt->element) == BIT_FIELD_REF
1324       || (var != elt->replacement
1325           && TREE_CODE (elt->replacement) == BIT_FIELD_REF))
1326     {
1327       tree init = sra_build_assignment (var, fold_convert (TREE_TYPE (var),
1328                                                            integer_zero_node));
1329       insert_edge_copies (init, ENTRY_BLOCK_PTR);
1330       mark_all_v_defs (init);
1331     }
1332
1333   if (dump_file)
1334     {
1335       fputs ("  ", dump_file);
1336       dump_sra_elt_name (dump_file, elt);
1337       fputs (" -> ", dump_file);
1338       print_generic_expr (dump_file, var, dump_flags);
1339       fputc ('\n', dump_file);
1340     }
1341 }
1342
1343 /* Make one pass across an element tree deciding whether or not it's
1344    profitable to instantiate individual leaf scalars.
1345
1346    PARENT_USES and PARENT_COPIES are the sum of the N_USES and N_COPIES
1347    fields all the way up the tree.  */
1348
1349 static void
1350 decide_instantiation_1 (struct sra_elt *elt, unsigned int parent_uses,
1351                         unsigned int parent_copies)
1352 {
1353   if (dump_file && !elt->parent)
1354     {
1355       fputs ("Initial instantiation for ", dump_file);
1356       dump_sra_elt_name (dump_file, elt);
1357       fputc ('\n', dump_file);
1358     }
1359
1360   if (elt->cannot_scalarize)
1361     return;
1362
1363   if (elt->is_scalar)
1364     {
1365       /* The decision is simple: instantiate if we're used more frequently
1366          than the parent needs to be seen as a complete unit.  */
1367       if (elt->n_uses + elt->n_copies + parent_copies > parent_uses)
1368         instantiate_element (elt);
1369     }
1370   else
1371     {
1372       struct sra_elt *c, *group;
1373       unsigned int this_uses = elt->n_uses + parent_uses;
1374       unsigned int this_copies = elt->n_copies + parent_copies;
1375
1376       /* Consider groups of sub-elements as weighing in favour of
1377          instantiation whatever their size.  */
1378       for (group = elt->groups; group ; group = group->sibling)
1379         FOR_EACH_ACTUAL_CHILD (c, group)
1380           {
1381             c->n_uses += group->n_uses;
1382             c->n_copies += group->n_copies;
1383           }
1384
1385       for (c = elt->children; c ; c = c->sibling)
1386         decide_instantiation_1 (c, this_uses, this_copies);
1387     }
1388 }
1389
1390 /* Compute the size and number of all instantiated elements below ELT.
1391    We will only care about this if the size of the complete structure
1392    fits in a HOST_WIDE_INT, so we don't have to worry about overflow.  */
1393
1394 static unsigned int
1395 sum_instantiated_sizes (struct sra_elt *elt, unsigned HOST_WIDE_INT *sizep)
1396 {
1397   if (elt->replacement)
1398     {
1399       *sizep += TREE_INT_CST_LOW (TYPE_SIZE_UNIT (elt->type));
1400       return 1;
1401     }
1402   else
1403     {
1404       struct sra_elt *c;
1405       unsigned int count = 0;
1406
1407       for (c = elt->children; c ; c = c->sibling)
1408         count += sum_instantiated_sizes (c, sizep);
1409
1410       return count;
1411     }
1412 }
1413
1414 /* Instantiate fields in ELT->TYPE that are not currently present as
1415    children of ELT.  */
1416
1417 static void instantiate_missing_elements (struct sra_elt *elt);
1418
1419 static struct sra_elt *
1420 instantiate_missing_elements_1 (struct sra_elt *elt, tree child, tree type)
1421 {
1422   struct sra_elt *sub = lookup_element (elt, child, type, INSERT);
1423   if (sub->is_scalar)
1424     {
1425       if (sub->replacement == NULL)
1426         instantiate_element (sub);
1427     }
1428   else
1429     instantiate_missing_elements (sub);
1430   return sub;
1431 }
1432
1433 /* Obtain the canonical type for field F of ELEMENT.  */
1434
1435 static tree
1436 canon_type_for_field (tree f, tree element)
1437 {
1438   tree field_type = TREE_TYPE (f);
1439
1440   /* canonicalize_component_ref() unwidens some bit-field types (not
1441      marked as DECL_BIT_FIELD in C++), so we must do the same, lest we
1442      may introduce type mismatches.  */
1443   if (INTEGRAL_TYPE_P (field_type)
1444       && DECL_MODE (f) != TYPE_MODE (field_type))
1445     field_type = TREE_TYPE (get_unwidened (build3 (COMPONENT_REF,
1446                                                    field_type,
1447                                                    element,
1448                                                    f, NULL_TREE),
1449                                            NULL_TREE));
1450
1451   return field_type;
1452 }
1453
1454 /* Look for adjacent fields of ELT starting at F that we'd like to
1455    scalarize as a single variable.  Return the last field of the
1456    group.  */
1457
1458 static tree
1459 try_instantiate_multiple_fields (struct sra_elt *elt, tree f)
1460 {
1461   int count;
1462   unsigned HOST_WIDE_INT align, bit, size, alchk;
1463   enum machine_mode mode;
1464   tree first = f, prev;
1465   tree type, var;
1466   struct sra_elt *block;
1467
1468   if (!is_sra_scalar_type (TREE_TYPE (f))
1469       || !host_integerp (DECL_FIELD_OFFSET (f), 1)
1470       || !host_integerp (DECL_FIELD_BIT_OFFSET (f), 1)
1471       || !host_integerp (DECL_SIZE (f), 1)
1472       || lookup_element (elt, f, NULL, NO_INSERT))
1473     return f;
1474
1475   block = elt;
1476
1477   /* For complex and array objects, there are going to be integer
1478      literals as child elements.  In this case, we can't just take the
1479      alignment and mode of the decl, so we instead rely on the element
1480      type.
1481
1482      ??? We could try to infer additional alignment from the full
1483      object declaration and the location of the sub-elements we're
1484      accessing.  */
1485   for (count = 0; !DECL_P (block->element); count++)
1486     block = block->parent;
1487
1488   align = DECL_ALIGN (block->element);
1489   alchk = GET_MODE_BITSIZE (DECL_MODE (block->element));
1490
1491   if (count)
1492     {
1493       type = TREE_TYPE (block->element);
1494       while (count--)
1495         type = TREE_TYPE (type);
1496
1497       align = TYPE_ALIGN (type);
1498       alchk = GET_MODE_BITSIZE (TYPE_MODE (type));
1499     }
1500
1501   if (align < alchk)
1502     align = alchk;
1503
1504   /* Coalescing wider fields is probably pointless and
1505      inefficient.  */
1506   if (align > BITS_PER_WORD)
1507     align = BITS_PER_WORD;
1508
1509   bit = tree_low_cst (DECL_FIELD_OFFSET (f), 1) * BITS_PER_UNIT
1510     + tree_low_cst (DECL_FIELD_BIT_OFFSET (f), 1);
1511   size = tree_low_cst (DECL_SIZE (f), 1);
1512
1513   alchk = align - 1;
1514   alchk = ~alchk;
1515
1516   if ((bit & alchk) != ((bit + size - 1) & alchk))
1517     return f;
1518
1519   /* Find adjacent fields in the same alignment word.  */
1520
1521   for (prev = f, f = TREE_CHAIN (f);
1522        f && TREE_CODE (f) == FIELD_DECL
1523          && is_sra_scalar_type (TREE_TYPE (f))
1524          && host_integerp (DECL_FIELD_OFFSET (f), 1)
1525          && host_integerp (DECL_FIELD_BIT_OFFSET (f), 1)
1526          && host_integerp (DECL_SIZE (f), 1)
1527          && !lookup_element (elt, f, NULL, NO_INSERT);
1528        prev = f, f = TREE_CHAIN (f))
1529     {
1530       unsigned HOST_WIDE_INT nbit, nsize;
1531
1532       nbit = tree_low_cst (DECL_FIELD_OFFSET (f), 1) * BITS_PER_UNIT
1533         + tree_low_cst (DECL_FIELD_BIT_OFFSET (f), 1);
1534       nsize = tree_low_cst (DECL_SIZE (f), 1);
1535
1536       if (bit + size == nbit)
1537         {
1538           if ((bit & alchk) != ((nbit + nsize - 1) & alchk))
1539             {
1540               /* If we're at an alignment boundary, don't bother
1541                  growing alignment such that we can include this next
1542                  field.  */
1543               if ((nbit & alchk)
1544                   || GET_MODE_BITSIZE (DECL_MODE (f)) <= align)
1545                 break;
1546
1547               align = GET_MODE_BITSIZE (DECL_MODE (f));
1548               alchk = align - 1;
1549               alchk = ~alchk;
1550
1551               if ((bit & alchk) != ((nbit + nsize - 1) & alchk))
1552                 break;
1553             }
1554           size += nsize;
1555         }
1556       else if (nbit + nsize == bit)
1557         {
1558           if ((nbit & alchk) != ((bit + size - 1) & alchk))
1559             {
1560               if ((bit & alchk)
1561                   || GET_MODE_BITSIZE (DECL_MODE (f)) <= align)
1562                 break;
1563
1564               align = GET_MODE_BITSIZE (DECL_MODE (f));
1565               alchk = align - 1;
1566               alchk = ~alchk;
1567
1568               if ((nbit & alchk) != ((bit + size - 1) & alchk))
1569                 break;
1570             }
1571           bit = nbit;
1572           size += nsize;
1573         }
1574       else
1575         break;
1576     }
1577
1578   f = prev;
1579
1580   if (f == first)
1581     return f;
1582
1583   gcc_assert ((bit & alchk) == ((bit + size - 1) & alchk));
1584
1585   /* Try to widen the bit range so as to cover padding bits as well.  */
1586
1587   if ((bit & ~alchk) || size != align)
1588     {
1589       unsigned HOST_WIDE_INT mbit = bit & alchk;
1590       unsigned HOST_WIDE_INT msize = align;
1591
1592       for (f = TYPE_FIELDS (elt->type);
1593            f; f = TREE_CHAIN (f))
1594         {
1595           unsigned HOST_WIDE_INT fbit, fsize;
1596
1597           /* Skip the fields from first to prev.  */
1598           if (f == first)
1599             {
1600               f = prev;
1601               continue;
1602             }
1603
1604           if (!(TREE_CODE (f) == FIELD_DECL
1605                 && host_integerp (DECL_FIELD_OFFSET (f), 1)
1606                 && host_integerp (DECL_FIELD_BIT_OFFSET (f), 1)))
1607             continue;
1608
1609           fbit = tree_low_cst (DECL_FIELD_OFFSET (f), 1) * BITS_PER_UNIT
1610             + tree_low_cst (DECL_FIELD_BIT_OFFSET (f), 1);
1611
1612           /* If we're past the selected word, we're fine.  */
1613           if ((bit & alchk) < (fbit & alchk))
1614             continue;
1615
1616           if (host_integerp (DECL_SIZE (f), 1))
1617             fsize = tree_low_cst (DECL_SIZE (f), 1);
1618           else
1619             /* Assume a variable-sized field takes up all space till
1620                the end of the word.  ??? Endianness issues?  */
1621             fsize = align - (fbit & alchk);
1622
1623           if ((fbit & alchk) < (bit & alchk))
1624             {
1625               /* A large field might start at a previous word and
1626                  extend into the selected word.  Exclude those
1627                  bits.  ??? Endianness issues? */
1628               HOST_WIDE_INT diff = fbit + fsize - mbit;
1629
1630               if (diff <= 0)
1631                 continue;
1632
1633               mbit += diff;
1634               msize -= diff;
1635             }
1636           else
1637             {
1638               /* Non-overlapping, great.  */
1639               if (fbit + fsize <= mbit
1640                   || mbit + msize <= fbit)
1641                 continue;
1642
1643               if (fbit <= mbit)
1644                 {
1645                   unsigned HOST_WIDE_INT diff = fbit + fsize - mbit;
1646                   mbit += diff;
1647                   msize -= diff;
1648                 }
1649               else if (fbit > mbit)
1650                 msize -= (mbit + msize - fbit);
1651               else
1652                 gcc_unreachable ();
1653             }
1654         }
1655
1656       bit = mbit;
1657       size = msize;
1658     }
1659
1660   /* Now we know the bit range we're interested in.  Find the smallest
1661      machine mode we can use to access it.  */
1662
1663   for (mode = smallest_mode_for_size (size, MODE_INT);
1664        ;
1665        mode = GET_MODE_WIDER_MODE (mode))
1666     {
1667       gcc_assert (mode != VOIDmode);
1668
1669       alchk = GET_MODE_PRECISION (mode) - 1;
1670       alchk = ~alchk;
1671
1672       if ((bit & alchk) == ((bit + size - 1) & alchk))
1673         break;
1674     }
1675
1676   gcc_assert (~alchk < align);
1677
1678   /* Create the field group as a single variable.  */
1679
1680   type = lang_hooks.types.type_for_mode (mode, 1);
1681   gcc_assert (type);
1682   var = build3 (BIT_FIELD_REF, type, NULL_TREE,
1683                 bitsize_int (size),
1684                 bitsize_int (bit));
1685   BIT_FIELD_REF_UNSIGNED (var) = 1;
1686
1687   block = instantiate_missing_elements_1 (elt, var, type);
1688   gcc_assert (block && block->is_scalar);
1689
1690   var = block->replacement;
1691
1692   if ((bit & ~alchk)
1693       || (HOST_WIDE_INT)size != tree_low_cst (DECL_SIZE (var), 1))
1694     {
1695       block->replacement = build3 (BIT_FIELD_REF,
1696                                    TREE_TYPE (block->element), var,
1697                                    bitsize_int (size),
1698                                    bitsize_int (bit & ~alchk));
1699       BIT_FIELD_REF_UNSIGNED (block->replacement) = 1;
1700     }
1701
1702   block->in_bitfld_block = 2;
1703
1704   /* Add the member fields to the group, such that they access
1705      portions of the group variable.  */
1706
1707   for (f = first; f != TREE_CHAIN (prev); f = TREE_CHAIN (f))
1708     {
1709       tree field_type = canon_type_for_field (f, elt->element);
1710       struct sra_elt *fld = lookup_element (block, f, field_type, INSERT);
1711
1712       gcc_assert (fld && fld->is_scalar && !fld->replacement);
1713
1714       fld->replacement = build3 (BIT_FIELD_REF, field_type, var,
1715                                  DECL_SIZE (f),
1716                                  bitsize_int
1717                                  ((TREE_INT_CST_LOW (DECL_FIELD_OFFSET (f))
1718                                    * BITS_PER_UNIT
1719                                    + (TREE_INT_CST_LOW
1720                                       (DECL_FIELD_BIT_OFFSET (f))))
1721                                   & ~alchk));
1722       BIT_FIELD_REF_UNSIGNED (fld->replacement) = TYPE_UNSIGNED (field_type);
1723       fld->in_bitfld_block = 1;
1724     }
1725
1726   return prev;
1727 }
1728
1729 static void
1730 instantiate_missing_elements (struct sra_elt *elt)
1731 {
1732   tree type = elt->type;
1733
1734   switch (TREE_CODE (type))
1735     {
1736     case RECORD_TYPE:
1737       {
1738         tree f;
1739         for (f = TYPE_FIELDS (type); f ; f = TREE_CHAIN (f))
1740           if (TREE_CODE (f) == FIELD_DECL)
1741             {
1742               tree last = try_instantiate_multiple_fields (elt, f);
1743
1744               if (last != f)
1745                 {
1746                   f = last;
1747                   continue;
1748                 }
1749
1750               instantiate_missing_elements_1 (elt, f,
1751                                               canon_type_for_field
1752                                               (f, elt->element));
1753             }
1754         break;
1755       }
1756
1757     case ARRAY_TYPE:
1758       {
1759         tree i, max, subtype;
1760
1761         i = TYPE_MIN_VALUE (TYPE_DOMAIN (type));
1762         max = TYPE_MAX_VALUE (TYPE_DOMAIN (type));
1763         subtype = TREE_TYPE (type);
1764
1765         while (1)
1766           {
1767             instantiate_missing_elements_1 (elt, i, subtype);
1768             if (tree_int_cst_equal (i, max))
1769               break;
1770             i = int_const_binop (PLUS_EXPR, i, integer_one_node, true);
1771           }
1772
1773         break;
1774       }
1775
1776     case COMPLEX_TYPE:
1777       type = TREE_TYPE (type);
1778       instantiate_missing_elements_1 (elt, integer_zero_node, type);
1779       instantiate_missing_elements_1 (elt, integer_one_node, type);
1780       break;
1781
1782     default:
1783       gcc_unreachable ();
1784     }
1785 }
1786
1787 /* Return true if there is only one non aggregate field in the record, TYPE.
1788    Return false otherwise.  */
1789
1790 static bool
1791 single_scalar_field_in_record_p (tree type)
1792 {
1793    int num_fields = 0;
1794    tree field;
1795    if (TREE_CODE (type) != RECORD_TYPE)
1796      return false;
1797
1798    for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
1799      if (TREE_CODE (field) == FIELD_DECL)
1800        {
1801          num_fields++;
1802
1803          if (num_fields == 2)
1804            return false;
1805          
1806          if (AGGREGATE_TYPE_P (TREE_TYPE (field)))
1807            return false;
1808        }
1809
1810    return true;
1811 }
1812
1813 /* Make one pass across an element tree deciding whether to perform block
1814    or element copies.  If we decide on element copies, instantiate all
1815    elements.  Return true if there are any instantiated sub-elements.  */
1816
1817 static bool
1818 decide_block_copy (struct sra_elt *elt)
1819 {
1820   struct sra_elt *c;
1821   bool any_inst;
1822
1823   /* We shouldn't be invoked on groups of sub-elements as they must
1824      behave like their parent as far as block copy is concerned.  */
1825   gcc_assert (!elt->is_group);
1826
1827   /* If scalarization is disabled, respect it.  */
1828   if (elt->cannot_scalarize)
1829     {
1830       elt->use_block_copy = 1;
1831
1832       if (dump_file)
1833         {
1834           fputs ("Scalarization disabled for ", dump_file);
1835           dump_sra_elt_name (dump_file, elt);
1836           fputc ('\n', dump_file);
1837         }
1838
1839       /* Disable scalarization of sub-elements */
1840       for (c = elt->children; c; c = c->sibling)
1841         {
1842           c->cannot_scalarize = 1;
1843           decide_block_copy (c);
1844         }
1845
1846       /* Groups behave like their parent.  */
1847       for (c = elt->groups; c; c = c->sibling)
1848         {
1849           c->cannot_scalarize = 1;
1850           c->use_block_copy = 1;
1851         }
1852
1853       return false;
1854     }
1855
1856   /* Don't decide if we've no uses and no groups.  */
1857   if (elt->n_uses == 0 && elt->n_copies == 0 && elt->groups == NULL)
1858     ;
1859
1860   else if (!elt->is_scalar)
1861     {
1862       tree size_tree = TYPE_SIZE_UNIT (elt->type);
1863       bool use_block_copy = true;
1864
1865       /* Tradeoffs for COMPLEX types pretty much always make it better
1866          to go ahead and split the components.  */
1867       if (TREE_CODE (elt->type) == COMPLEX_TYPE)
1868         use_block_copy = false;
1869
1870       /* Don't bother trying to figure out the rest if the structure is
1871          so large we can't do easy arithmetic.  This also forces block
1872          copies for variable sized structures.  */
1873       else if (host_integerp (size_tree, 1))
1874         {
1875           unsigned HOST_WIDE_INT full_size, inst_size = 0;
1876           unsigned int max_size, max_count, inst_count, full_count;
1877
1878           /* If the sra-max-structure-size parameter is 0, then the
1879              user has not overridden the parameter and we can choose a
1880              sensible default.  */
1881           max_size = SRA_MAX_STRUCTURE_SIZE
1882             ? SRA_MAX_STRUCTURE_SIZE
1883             : MOVE_RATIO * UNITS_PER_WORD;
1884           max_count = SRA_MAX_STRUCTURE_COUNT
1885             ? SRA_MAX_STRUCTURE_COUNT
1886             : MOVE_RATIO;
1887
1888           full_size = tree_low_cst (size_tree, 1);
1889           full_count = count_type_elements (elt->type, false);
1890           inst_count = sum_instantiated_sizes (elt, &inst_size);
1891
1892           /* If there is only one scalar field in the record, don't block copy.  */
1893           if (single_scalar_field_in_record_p (elt->type))
1894             use_block_copy = false;
1895
1896           /* ??? What to do here.  If there are two fields, and we've only
1897              instantiated one, then instantiating the other is clearly a win.
1898              If there are a large number of fields then the size of the copy
1899              is much more of a factor.  */
1900
1901           /* If the structure is small, and we've made copies, go ahead
1902              and instantiate, hoping that the copies will go away.  */
1903           if (full_size <= max_size
1904               && (full_count - inst_count) <= max_count
1905               && elt->n_copies > elt->n_uses)
1906             use_block_copy = false;
1907           else if (inst_count * 100 >= full_count * SRA_FIELD_STRUCTURE_RATIO
1908                    && inst_size * 100 >= full_size * SRA_FIELD_STRUCTURE_RATIO)
1909             use_block_copy = false;
1910
1911           /* In order to avoid block copy, we have to be able to instantiate
1912              all elements of the type.  See if this is possible.  */
1913           if (!use_block_copy
1914               && (!can_completely_scalarize_p (elt)
1915                   || !type_can_instantiate_all_elements (elt->type)))
1916             use_block_copy = true;
1917         }
1918
1919       elt->use_block_copy = use_block_copy;
1920
1921       /* Groups behave like their parent.  */
1922       for (c = elt->groups; c; c = c->sibling)
1923         c->use_block_copy = use_block_copy;
1924
1925       if (dump_file)
1926         {
1927           fprintf (dump_file, "Using %s for ",
1928                    use_block_copy ? "block-copy" : "element-copy");
1929           dump_sra_elt_name (dump_file, elt);
1930           fputc ('\n', dump_file);
1931         }
1932
1933       if (!use_block_copy)
1934         {
1935           instantiate_missing_elements (elt);
1936           return true;
1937         }
1938     }
1939
1940   any_inst = elt->replacement != NULL;
1941
1942   for (c = elt->children; c ; c = c->sibling)
1943     any_inst |= decide_block_copy (c);
1944
1945   return any_inst;
1946 }
1947
1948 /* Entry point to phase 3.  Instantiate scalar replacement variables.  */
1949
1950 static void
1951 decide_instantiations (void)
1952 {
1953   unsigned int i;
1954   bool cleared_any;
1955   bitmap_head done_head;
1956   bitmap_iterator bi;
1957
1958   /* We cannot clear bits from a bitmap we're iterating over,
1959      so save up all the bits to clear until the end.  */
1960   bitmap_initialize (&done_head, &bitmap_default_obstack);
1961   cleared_any = false;
1962
1963   EXECUTE_IF_SET_IN_BITMAP (sra_candidates, 0, i, bi)
1964     {
1965       tree var = referenced_var (i);
1966       struct sra_elt *elt = lookup_element (NULL, var, NULL, NO_INSERT);
1967       if (elt)
1968         {
1969           decide_instantiation_1 (elt, 0, 0);
1970           if (!decide_block_copy (elt))
1971             elt = NULL;
1972         }
1973       if (!elt)
1974         {
1975           bitmap_set_bit (&done_head, i);
1976           cleared_any = true;
1977         }
1978     }
1979
1980   if (cleared_any)
1981     {
1982       bitmap_and_compl_into (sra_candidates, &done_head);
1983       bitmap_and_compl_into (needs_copy_in, &done_head);
1984     }
1985   bitmap_clear (&done_head);
1986   
1987   mark_set_for_renaming (sra_candidates);
1988
1989   if (dump_file)
1990     fputc ('\n', dump_file);
1991 }
1992
1993 \f
1994 /* Phase Four: Update the function to match the replacements created.  */
1995
1996 /* Mark all the variables in VDEF/VUSE operators for STMT for
1997    renaming. This becomes necessary when we modify all of a
1998    non-scalar.  */
1999
2000 static void
2001 mark_all_v_defs_1 (tree stmt)
2002 {
2003   tree sym;
2004   ssa_op_iter iter;
2005
2006   update_stmt_if_modified (stmt);
2007
2008   FOR_EACH_SSA_TREE_OPERAND (sym, stmt, iter, SSA_OP_ALL_VIRTUALS)
2009     {
2010       if (TREE_CODE (sym) == SSA_NAME)
2011         sym = SSA_NAME_VAR (sym);
2012       mark_sym_for_renaming (sym);
2013     }
2014 }
2015
2016
2017 /* Mark all the variables in virtual operands in all the statements in
2018    LIST for renaming.  */
2019
2020 static void
2021 mark_all_v_defs (tree list)
2022 {
2023   if (TREE_CODE (list) != STATEMENT_LIST)
2024     mark_all_v_defs_1 (list);
2025   else
2026     {
2027       tree_stmt_iterator i;
2028       for (i = tsi_start (list); !tsi_end_p (i); tsi_next (&i))
2029         mark_all_v_defs_1 (tsi_stmt (i));
2030     }
2031 }
2032
2033
2034 /* Mark every replacement under ELT with TREE_NO_WARNING.  */
2035
2036 static void
2037 mark_no_warning (struct sra_elt *elt)
2038 {
2039   if (!elt->all_no_warning)
2040     {
2041       if (elt->replacement)
2042         TREE_NO_WARNING (elt->replacement) = 1;
2043       else
2044         {
2045           struct sra_elt *c;
2046           FOR_EACH_ACTUAL_CHILD (c, elt)
2047             mark_no_warning (c);
2048         }
2049       elt->all_no_warning = true;
2050     }
2051 }
2052
2053 /* Build a single level component reference to ELT rooted at BASE.  */
2054
2055 static tree
2056 generate_one_element_ref (struct sra_elt *elt, tree base)
2057 {
2058   switch (TREE_CODE (TREE_TYPE (base)))
2059     {
2060     case RECORD_TYPE:
2061       {
2062         tree field = elt->element;
2063
2064         /* We can't test elt->in_bitfld_blk here because, when this is
2065            called from instantiate_element, we haven't set this field
2066            yet.  */
2067         if (TREE_CODE (field) == BIT_FIELD_REF)
2068           {
2069             tree ret = unshare_expr (field);
2070             TREE_OPERAND (ret, 0) = base;
2071             return ret;
2072           }
2073
2074         /* Watch out for compatible records with differing field lists.  */
2075         if (DECL_FIELD_CONTEXT (field) != TYPE_MAIN_VARIANT (TREE_TYPE (base)))
2076           field = find_compatible_field (TREE_TYPE (base), field);
2077
2078         return build3 (COMPONENT_REF, elt->type, base, field, NULL);
2079       }
2080
2081     case ARRAY_TYPE:
2082       if (TREE_CODE (elt->element) == RANGE_EXPR)
2083         return build4 (ARRAY_RANGE_REF, elt->type, base,
2084                        TREE_OPERAND (elt->element, 0), NULL, NULL);
2085       else
2086         return build4 (ARRAY_REF, elt->type, base, elt->element, NULL, NULL);
2087
2088     case COMPLEX_TYPE:
2089       if (elt->element == integer_zero_node)
2090         return build1 (REALPART_EXPR, elt->type, base);
2091       else
2092         return build1 (IMAGPART_EXPR, elt->type, base);
2093
2094     default:
2095       gcc_unreachable ();
2096     }
2097 }
2098
2099 /* Build a full component reference to ELT rooted at its native variable.  */
2100
2101 static tree
2102 generate_element_ref (struct sra_elt *elt)
2103 {
2104   if (elt->parent)
2105     return generate_one_element_ref (elt, generate_element_ref (elt->parent));
2106   else
2107     return elt->element;
2108 }
2109
2110 /* Return true if BF is a bit-field that we can handle like a scalar.  */
2111
2112 static bool
2113 scalar_bitfield_p (tree bf)
2114 {
2115   return (TREE_CODE (bf) == BIT_FIELD_REF
2116           && (is_gimple_reg (TREE_OPERAND (bf, 0))
2117               || (TYPE_MODE (TREE_TYPE (TREE_OPERAND (bf, 0))) != BLKmode
2118                   && (!TREE_SIDE_EFFECTS (TREE_OPERAND (bf, 0))
2119                       || (GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE
2120                                                        (TREE_OPERAND (bf, 0))))
2121                           <= BITS_PER_WORD)))));
2122 }
2123
2124 /* Create an assignment statement from SRC to DST.  */
2125
2126 static tree
2127 sra_build_assignment (tree dst, tree src)
2128 {
2129   /* Turning BIT_FIELD_REFs into bit operations enables other passes
2130      to do a much better job at optimizing the code.  */
2131   if (scalar_bitfield_p (src))
2132     {
2133       tree cst, cst2, mask, minshift, maxshift;
2134       tree tmp, var, utype, stype;
2135       tree list, stmt;
2136       bool unsignedp = BIT_FIELD_REF_UNSIGNED (src);
2137
2138       var = TREE_OPERAND (src, 0);
2139       cst = TREE_OPERAND (src, 2);
2140       cst2 = size_binop (PLUS_EXPR, TREE_OPERAND (src, 1),
2141                          TREE_OPERAND (src, 2));
2142
2143       if (BYTES_BIG_ENDIAN)
2144         {
2145           maxshift = size_binop (MINUS_EXPR, TYPE_SIZE (TREE_TYPE (var)), cst);
2146           minshift = size_binop (MINUS_EXPR, TYPE_SIZE (TREE_TYPE (var)), cst2);
2147         }
2148       else
2149         {
2150           maxshift = cst2;
2151           minshift = cst;
2152         }
2153
2154       stype = TREE_TYPE (var);
2155       if (!INTEGRAL_TYPE_P (stype))
2156         stype = lang_hooks.types.type_for_size (TREE_INT_CST_LOW
2157                                                 (TYPE_SIZE (stype)), 1);
2158       else if (!TYPE_UNSIGNED (stype))
2159         stype = unsigned_type_for (stype);
2160
2161       utype = TREE_TYPE (dst);
2162       if (!INTEGRAL_TYPE_P (utype))
2163         utype = lang_hooks.types.type_for_size (TREE_INT_CST_LOW
2164                                                 (TYPE_SIZE (utype)), 1);
2165       else if (!TYPE_UNSIGNED (utype))
2166         utype = unsigned_type_for (utype);
2167
2168       list = NULL;
2169
2170       cst2 = size_binop (MINUS_EXPR, maxshift, minshift);
2171       if (TREE_INT_CST_LOW (cst2) == TYPE_PRECISION (utype))
2172         {
2173           unsignedp = true;
2174           mask = NULL_TREE;
2175         }
2176       else
2177         {
2178           mask = build_int_cst_wide (utype, 1, 0);
2179           cst = int_const_binop (LSHIFT_EXPR, mask, cst2, true);
2180           mask = int_const_binop (MINUS_EXPR, cst, mask, true);
2181         }
2182
2183       tmp = make_rename_temp (stype, "SR");
2184       if (TYPE_MAIN_VARIANT (TREE_TYPE (var)) != TYPE_MAIN_VARIANT (stype))
2185         {
2186           if (INTEGRAL_TYPE_P (TREE_TYPE (var)))
2187             stmt = build_gimple_modify_stmt (tmp,
2188                                              fold_convert (stype, var));
2189           else
2190             stmt = build_gimple_modify_stmt (tmp,
2191                                              fold_build1 (VIEW_CONVERT_EXPR,
2192                                                           stype, var));
2193           append_to_statement_list (stmt, &list);
2194
2195           var = tmp;
2196         }
2197
2198       if (!integer_zerop (minshift))
2199         {
2200           tmp = make_rename_temp (stype, "SR");
2201           stmt = build_gimple_modify_stmt (tmp,
2202                                            fold_build2 (RSHIFT_EXPR, stype,
2203                                                         var, minshift));
2204           append_to_statement_list (stmt, &list);
2205
2206           var = tmp;
2207         }
2208
2209       if (TYPE_MAIN_VARIANT (utype) != TYPE_MAIN_VARIANT (stype))
2210         {
2211           if (!mask && unsignedp
2212               && (TYPE_MAIN_VARIANT (utype)
2213                   == TYPE_MAIN_VARIANT (TREE_TYPE (dst))))
2214             tmp = dst;
2215           else
2216             tmp = make_rename_temp (utype, "SR");
2217
2218           stmt = build_gimple_modify_stmt (tmp, fold_convert (utype, var));
2219           append_to_statement_list (stmt, &list);
2220
2221           var = tmp;
2222         }
2223
2224       if (mask)
2225         {
2226           if (!unsignedp
2227               || (TYPE_MAIN_VARIANT (TREE_TYPE (dst))
2228                   != TYPE_MAIN_VARIANT (utype)))
2229             tmp = make_rename_temp (utype, "SR");
2230           else
2231             tmp = dst;
2232
2233           stmt = build_gimple_modify_stmt (tmp,
2234                                            fold_build2 (BIT_AND_EXPR, utype,
2235                                                         var, mask));
2236           append_to_statement_list (stmt, &list);
2237
2238           var = tmp;
2239         }
2240
2241       if (!unsignedp)
2242         {
2243           tree signbit = int_const_binop (LSHIFT_EXPR,
2244                                           build_int_cst_wide (utype, 1, 0),
2245                                           size_binop (MINUS_EXPR, cst2,
2246                                                       bitsize_int (1)),
2247                                           true);
2248
2249           tmp = make_rename_temp (utype, "SR");
2250           stmt = build_gimple_modify_stmt (tmp,
2251                                            fold_build2 (BIT_XOR_EXPR, utype,
2252                                                         var, signbit));
2253           append_to_statement_list (stmt, &list);
2254
2255           var = tmp;
2256
2257           if (TYPE_MAIN_VARIANT (TREE_TYPE (dst)) != TYPE_MAIN_VARIANT (utype))
2258             tmp = make_rename_temp (utype, "SR");
2259           else
2260             tmp = dst;
2261
2262           stmt = build_gimple_modify_stmt (tmp,
2263                                            fold_build2 (MINUS_EXPR, utype,
2264                                                         var, signbit));
2265           append_to_statement_list (stmt, &list);
2266
2267           var = tmp;
2268         }
2269
2270       if (var != dst)
2271         {
2272           if (INTEGRAL_TYPE_P (TREE_TYPE (dst)))
2273             var = fold_convert (TREE_TYPE (dst), var);
2274           else
2275             var = fold_build1 (VIEW_CONVERT_EXPR, TREE_TYPE (dst), var);
2276
2277           stmt = build_gimple_modify_stmt (dst, var);
2278           append_to_statement_list (stmt, &list);
2279         }
2280
2281       return list;
2282     }
2283
2284   /* It was hoped that we could perform some type sanity checking
2285      here, but since front-ends can emit accesses of fields in types
2286      different from their nominal types and copy structures containing
2287      them as a whole, we'd have to handle such differences here.
2288      Since such accesses under different types require compatibility
2289      anyway, there's little point in making tests and/or adding
2290      conversions to ensure the types of src and dst are the same.
2291      So we just assume type differences at this point are ok.  */
2292   return build_gimple_modify_stmt (dst, src);
2293 }
2294
2295 /* BIT_FIELD_REFs must not be shared.  sra_build_elt_assignment()
2296    takes care of assignments, but we must create copies for uses.  */
2297 #define REPLDUP(t) (TREE_CODE (t) != BIT_FIELD_REF ? (t) : unshare_expr (t))
2298
2299 /* Emit an assignment from SRC to DST, but if DST is a scalarizable
2300    BIT_FIELD_REF, turn it into bit operations.  */
2301
2302 static tree
2303 sra_build_bf_assignment (tree dst, tree src)
2304 {
2305   tree var, type, utype, tmp, tmp2, tmp3;
2306   tree list, stmt;
2307   tree cst, cst2, mask;
2308   tree minshift, maxshift;
2309
2310   if (TREE_CODE (dst) != BIT_FIELD_REF)
2311     return sra_build_assignment (dst, src);
2312
2313   var = TREE_OPERAND (dst, 0);
2314
2315   if (!scalar_bitfield_p (dst))
2316     return sra_build_assignment (REPLDUP (dst), src);
2317
2318   list = NULL;
2319
2320   cst = fold_convert (bitsizetype, TREE_OPERAND (dst, 2));
2321   cst2 = size_binop (PLUS_EXPR,
2322                      fold_convert (bitsizetype, TREE_OPERAND (dst, 1)),
2323                      cst);
2324
2325   if (BYTES_BIG_ENDIAN)
2326     {
2327       maxshift = size_binop (MINUS_EXPR, TYPE_SIZE (TREE_TYPE (var)), cst);
2328       minshift = size_binop (MINUS_EXPR, TYPE_SIZE (TREE_TYPE (var)), cst2);
2329     }
2330   else
2331     {
2332       maxshift = cst2;
2333       minshift = cst;
2334     }
2335
2336   type = TREE_TYPE (var);
2337   if (!INTEGRAL_TYPE_P (type))
2338     type = lang_hooks.types.type_for_size
2339       (TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (var))), 1);
2340   if (TYPE_UNSIGNED (type))
2341     utype = type;
2342   else
2343     utype = unsigned_type_for (type);
2344
2345   mask = build_int_cst_wide (utype, 1, 0);
2346   if (TREE_INT_CST_LOW (maxshift) == TYPE_PRECISION (utype))
2347     cst = build_int_cst_wide (utype, 0, 0);
2348   else
2349     cst = int_const_binop (LSHIFT_EXPR, mask, maxshift, true);
2350   if (integer_zerop (minshift))
2351     cst2 = mask;
2352   else
2353     cst2 = int_const_binop (LSHIFT_EXPR, mask, minshift, true);
2354   mask = int_const_binop (MINUS_EXPR, cst, cst2, true);
2355   mask = fold_build1 (BIT_NOT_EXPR, utype, mask);
2356
2357   if (TYPE_MAIN_VARIANT (utype) != TYPE_MAIN_VARIANT (TREE_TYPE (var))
2358       && !integer_zerop (mask))
2359     {
2360       tmp = var;
2361       if (!is_gimple_variable (tmp))
2362         tmp = unshare_expr (var);
2363
2364       tmp2 = make_rename_temp (utype, "SR");
2365
2366       if (INTEGRAL_TYPE_P (TREE_TYPE (var)))
2367         stmt = build_gimple_modify_stmt (tmp2, fold_convert (utype, tmp));
2368       else
2369         stmt = build_gimple_modify_stmt (tmp2, fold_build1 (VIEW_CONVERT_EXPR,
2370                                                             utype, tmp));
2371       append_to_statement_list (stmt, &list);
2372     }
2373   else
2374     tmp2 = var;
2375
2376   if (!integer_zerop (mask))
2377     {
2378       tmp = make_rename_temp (utype, "SR");
2379       stmt = build_gimple_modify_stmt (tmp,
2380                                        fold_build2 (BIT_AND_EXPR, utype,
2381                                                     tmp2, mask));
2382       append_to_statement_list (stmt, &list);
2383     }
2384   else
2385     tmp = mask;
2386
2387   if (is_gimple_reg (src) && INTEGRAL_TYPE_P (TREE_TYPE (src)))
2388     tmp2 = src;
2389   else if (INTEGRAL_TYPE_P (TREE_TYPE (src)))
2390     {
2391       tmp2 = make_rename_temp (TREE_TYPE (src), "SR");
2392       stmt = sra_build_assignment (tmp2, src);
2393       append_to_statement_list (stmt, &list);
2394     }
2395   else
2396     {
2397       tmp2 = make_rename_temp
2398         (lang_hooks.types.type_for_size
2399          (TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (src))),
2400           1), "SR");
2401       stmt = sra_build_assignment (tmp2, fold_build1 (VIEW_CONVERT_EXPR,
2402                                                       TREE_TYPE (tmp2), src));
2403       append_to_statement_list (stmt, &list);
2404     }
2405
2406   if (!TYPE_UNSIGNED (TREE_TYPE (tmp2)))
2407     {
2408       tree ut = unsigned_type_for (TREE_TYPE (tmp2));
2409       tmp3 = make_rename_temp (ut, "SR");
2410       tmp2 = fold_convert (ut, tmp2);
2411       stmt = sra_build_assignment (tmp3, tmp2);
2412       append_to_statement_list (stmt, &list);
2413
2414       tmp2 = fold_build1 (BIT_NOT_EXPR, utype, mask);
2415       tmp2 = int_const_binop (RSHIFT_EXPR, tmp2, minshift, true);
2416       tmp2 = fold_convert (ut, tmp2);
2417       tmp2 = fold_build2 (BIT_AND_EXPR, ut, tmp3, tmp2);
2418
2419       if (tmp3 != tmp2)
2420         {
2421           tmp3 = make_rename_temp (ut, "SR");
2422           stmt = sra_build_assignment (tmp3, tmp2);
2423           append_to_statement_list (stmt, &list);
2424         }
2425
2426       tmp2 = tmp3;
2427     }
2428
2429   if (TYPE_MAIN_VARIANT (TREE_TYPE (tmp2)) != TYPE_MAIN_VARIANT (utype))
2430     {
2431       tmp3 = make_rename_temp (utype, "SR");
2432       tmp2 = fold_convert (utype, tmp2);
2433       stmt = sra_build_assignment (tmp3, tmp2);
2434       append_to_statement_list (stmt, &list);
2435       tmp2 = tmp3;
2436     }
2437
2438   if (!integer_zerop (minshift))
2439     {
2440       tmp3 = make_rename_temp (utype, "SR");
2441       stmt = build_gimple_modify_stmt (tmp3,
2442                                        fold_build2 (LSHIFT_EXPR, utype,
2443                                                     tmp2, minshift));
2444       append_to_statement_list (stmt, &list);
2445       tmp2 = tmp3;
2446     }
2447
2448   if (utype != TREE_TYPE (var))
2449     tmp3 = make_rename_temp (utype, "SR");
2450   else
2451     tmp3 = var;
2452   stmt = build_gimple_modify_stmt (tmp3,
2453                                    fold_build2 (BIT_IOR_EXPR, utype,
2454                                                 tmp, tmp2));
2455   append_to_statement_list (stmt, &list);
2456
2457   if (tmp3 != var)
2458     {
2459       if (TREE_TYPE (var) == type)
2460         stmt = build_gimple_modify_stmt (var,
2461                                          fold_convert (type, tmp3));
2462       else
2463         stmt = build_gimple_modify_stmt (var,
2464                                          fold_build1 (VIEW_CONVERT_EXPR,
2465                                                       TREE_TYPE (var), tmp3));
2466       append_to_statement_list (stmt, &list);
2467     }
2468
2469   return list;
2470 }
2471
2472 /* Expand an assignment of SRC to the scalarized representation of
2473    ELT.  If it is a field group, try to widen the assignment to cover
2474    the full variable.  */
2475
2476 static tree
2477 sra_build_elt_assignment (struct sra_elt *elt, tree src)
2478 {
2479   tree dst = elt->replacement;
2480   tree var, tmp, cst, cst2, list, stmt;
2481
2482   if (TREE_CODE (dst) != BIT_FIELD_REF
2483       || !elt->in_bitfld_block)
2484     return sra_build_assignment (REPLDUP (dst), src);
2485
2486   var = TREE_OPERAND (dst, 0);
2487
2488   /* Try to widen the assignment to the entire variable.
2489      We need the source to be a BIT_FIELD_REF as well, such that, for
2490      BIT_FIELD_REF<d,sz,dp> = BIT_FIELD_REF<s,sz,sp>,
2491      by design, conditions are met such that we can turn it into
2492      d = BIT_FIELD_REF<s,dw,sp-dp>.  */
2493   if (elt->in_bitfld_block == 2
2494       && TREE_CODE (src) == BIT_FIELD_REF)
2495     {
2496       cst = TYPE_SIZE (TREE_TYPE (var));
2497       cst2 = size_binop (MINUS_EXPR, TREE_OPERAND (src, 2),
2498                          TREE_OPERAND (dst, 2));
2499
2500       src = TREE_OPERAND (src, 0);
2501
2502       /* Avoid full-width bit-fields.  */
2503       if (integer_zerop (cst2)
2504           && tree_int_cst_equal (cst, TYPE_SIZE (TREE_TYPE (src))))
2505         {
2506           if (INTEGRAL_TYPE_P (TREE_TYPE (src))
2507               && !TYPE_UNSIGNED (TREE_TYPE (src)))
2508             src = fold_convert (unsigned_type_for (TREE_TYPE (src)), src);
2509
2510           /* If a single conversion won't do, we'll need a statement
2511              list.  */
2512           if (TYPE_MAIN_VARIANT (TREE_TYPE (var))
2513               != TYPE_MAIN_VARIANT (TREE_TYPE (src)))
2514             {
2515               list = NULL;
2516
2517               if (!INTEGRAL_TYPE_P (TREE_TYPE (src)))
2518                 src = fold_build1 (VIEW_CONVERT_EXPR,
2519                                    lang_hooks.types.type_for_size
2520                                    (TREE_INT_CST_LOW
2521                                     (TYPE_SIZE (TREE_TYPE (src))),
2522                                     1), src);
2523               gcc_assert (TYPE_UNSIGNED (TREE_TYPE (src)));
2524
2525               tmp = make_rename_temp (TREE_TYPE (src), "SR");
2526               stmt = build_gimple_modify_stmt (tmp, src);
2527               append_to_statement_list (stmt, &list);
2528
2529               stmt = sra_build_assignment (var,
2530                                            fold_convert (TREE_TYPE (var),
2531                                                          tmp));
2532               append_to_statement_list (stmt, &list);
2533
2534               return list;
2535             }
2536
2537           src = fold_convert (TREE_TYPE (var), src);
2538         }
2539       else
2540         {
2541           src = fold_build3 (BIT_FIELD_REF, TREE_TYPE (var), src, cst, cst2);
2542           BIT_FIELD_REF_UNSIGNED (src) = 1;
2543         }
2544
2545       return sra_build_assignment (var, src);
2546     }
2547
2548   return sra_build_bf_assignment (dst, src);
2549 }
2550
2551 /* Generate a set of assignment statements in *LIST_P to copy all
2552    instantiated elements under ELT to or from the equivalent structure
2553    rooted at EXPR.  COPY_OUT controls the direction of the copy, with
2554    true meaning to copy out of EXPR into ELT.  */
2555
2556 static void
2557 generate_copy_inout (struct sra_elt *elt, bool copy_out, tree expr,
2558                      tree *list_p)
2559 {
2560   struct sra_elt *c;
2561   tree t;
2562
2563   if (!copy_out && TREE_CODE (expr) == SSA_NAME
2564       && TREE_CODE (TREE_TYPE (expr)) == COMPLEX_TYPE)
2565     {
2566       tree r, i;
2567
2568       c = lookup_element (elt, integer_zero_node, NULL, NO_INSERT);
2569       r = c->replacement;
2570       c = lookup_element (elt, integer_one_node, NULL, NO_INSERT);
2571       i = c->replacement;
2572
2573       t = build2 (COMPLEX_EXPR, elt->type, r, i);
2574       t = sra_build_bf_assignment (expr, t);
2575       SSA_NAME_DEF_STMT (expr) = t;
2576       append_to_statement_list (t, list_p);
2577     }
2578   else if (elt->replacement)
2579     {
2580       if (copy_out)
2581         t = sra_build_elt_assignment (elt, expr);
2582       else
2583         t = sra_build_bf_assignment (expr, REPLDUP (elt->replacement));
2584       append_to_statement_list (t, list_p);
2585     }
2586   else
2587     {
2588       FOR_EACH_ACTUAL_CHILD (c, elt)
2589         {
2590           t = generate_one_element_ref (c, unshare_expr (expr));
2591           generate_copy_inout (c, copy_out, t, list_p);
2592         }
2593     }
2594 }
2595
2596 /* Generate a set of assignment statements in *LIST_P to copy all instantiated
2597    elements under SRC to their counterparts under DST.  There must be a 1-1
2598    correspondence of instantiated elements.  */
2599
2600 static void
2601 generate_element_copy (struct sra_elt *dst, struct sra_elt *src, tree *list_p)
2602 {
2603   struct sra_elt *dc, *sc;
2604
2605   FOR_EACH_ACTUAL_CHILD (dc, dst)
2606     {
2607       sc = lookup_element (src, dc->element, NULL, NO_INSERT);
2608       if (!sc && dc->in_bitfld_block == 2)
2609         {
2610           struct sra_elt *dcs;
2611
2612           FOR_EACH_ACTUAL_CHILD (dcs, dc)
2613             {
2614               sc = lookup_element (src, dcs->element, NULL, NO_INSERT);
2615               gcc_assert (sc);
2616               generate_element_copy (dcs, sc, list_p);
2617             }
2618
2619           continue;
2620         }
2621       gcc_assert (sc);
2622       generate_element_copy (dc, sc, list_p);
2623     }
2624
2625   if (dst->replacement)
2626     {
2627       tree t;
2628
2629       gcc_assert (src->replacement);
2630
2631       t = sra_build_elt_assignment (dst, REPLDUP (src->replacement));
2632       append_to_statement_list (t, list_p);
2633     }
2634 }
2635
2636 /* Generate a set of assignment statements in *LIST_P to zero all instantiated
2637    elements under ELT.  In addition, do not assign to elements that have been
2638    marked VISITED but do reset the visited flag; this allows easy coordination
2639    with generate_element_init.  */
2640
2641 static void
2642 generate_element_zero (struct sra_elt *elt, tree *list_p)
2643 {
2644   struct sra_elt *c;
2645
2646   if (elt->visited)
2647     {
2648       elt->visited = false;
2649       return;
2650     }
2651
2652   if (!elt->in_bitfld_block)
2653     FOR_EACH_ACTUAL_CHILD (c, elt)
2654       generate_element_zero (c, list_p);
2655
2656   if (elt->replacement)
2657     {
2658       tree t;
2659
2660       gcc_assert (elt->is_scalar);
2661       t = fold_convert (elt->type, integer_zero_node);
2662
2663       t = sra_build_elt_assignment (elt, t);
2664       append_to_statement_list (t, list_p);
2665     }
2666 }
2667
2668 /* Generate an assignment VAR = INIT, where INIT may need gimplification.
2669    Add the result to *LIST_P.  */
2670
2671 static void
2672 generate_one_element_init (struct sra_elt *elt, tree init, tree *list_p)
2673 {
2674   /* The replacement can be almost arbitrarily complex.  Gimplify.  */
2675   tree stmt = sra_build_elt_assignment (elt, init);
2676   gimplify_and_add (stmt, list_p);
2677 }
2678
2679 /* Generate a set of assignment statements in *LIST_P to set all instantiated
2680    elements under ELT with the contents of the initializer INIT.  In addition,
2681    mark all assigned elements VISITED; this allows easy coordination with
2682    generate_element_zero.  Return false if we found a case we couldn't
2683    handle.  */
2684
2685 static bool
2686 generate_element_init_1 (struct sra_elt *elt, tree init, tree *list_p)
2687 {
2688   bool result = true;
2689   enum tree_code init_code;
2690   struct sra_elt *sub;
2691   tree t;
2692   unsigned HOST_WIDE_INT idx;
2693   tree value, purpose;
2694
2695   /* We can be passed DECL_INITIAL of a static variable.  It might have a
2696      conversion, which we strip off here.  */
2697   STRIP_USELESS_TYPE_CONVERSION (init);
2698   init_code = TREE_CODE (init);
2699
2700   if (elt->is_scalar)
2701     {
2702       if (elt->replacement)
2703         {
2704           generate_one_element_init (elt, init, list_p);
2705           elt->visited = true;
2706         }
2707       return result;
2708     }
2709
2710   switch (init_code)
2711     {
2712     case COMPLEX_CST:
2713     case COMPLEX_EXPR:
2714       FOR_EACH_ACTUAL_CHILD (sub, elt)
2715         {
2716           if (sub->element == integer_zero_node)
2717             t = (init_code == COMPLEX_EXPR
2718                  ? TREE_OPERAND (init, 0) : TREE_REALPART (init));
2719           else
2720             t = (init_code == COMPLEX_EXPR
2721                  ? TREE_OPERAND (init, 1) : TREE_IMAGPART (init));
2722           result &= generate_element_init_1 (sub, t, list_p);
2723         }
2724       break;
2725
2726     case CONSTRUCTOR:
2727       FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (init), idx, purpose, value)
2728         {
2729           if (TREE_CODE (purpose) == RANGE_EXPR)
2730             {
2731               tree lower = TREE_OPERAND (purpose, 0);
2732               tree upper = TREE_OPERAND (purpose, 1);
2733
2734               while (1)
2735                 {
2736                   sub = lookup_element (elt, lower, NULL, NO_INSERT);
2737                   if (sub != NULL)
2738                     result &= generate_element_init_1 (sub, value, list_p);
2739                   if (tree_int_cst_equal (lower, upper))
2740                     break;
2741                   lower = int_const_binop (PLUS_EXPR, lower,
2742                                            integer_one_node, true);
2743                 }
2744             }
2745           else
2746             {
2747               sub = lookup_element (elt, purpose, NULL, NO_INSERT);
2748               if (sub != NULL)
2749                 result &= generate_element_init_1 (sub, value, list_p);
2750             }
2751         }
2752       break;
2753
2754     default:
2755       elt->visited = true;
2756       result = false;
2757     }
2758
2759   return result;
2760 }
2761
2762 /* A wrapper function for generate_element_init_1 that handles cleanup after
2763    gimplification.  */
2764
2765 static bool
2766 generate_element_init (struct sra_elt *elt, tree init, tree *list_p)
2767 {
2768   bool ret;
2769
2770   push_gimplify_context ();
2771   ret = generate_element_init_1 (elt, init, list_p);
2772   pop_gimplify_context (NULL);
2773
2774   /* The replacement can expose previously unreferenced variables.  */
2775   if (ret && *list_p)
2776     {
2777       tree_stmt_iterator i;
2778
2779       for (i = tsi_start (*list_p); !tsi_end_p (i); tsi_next (&i))
2780         find_new_referenced_vars (tsi_stmt_ptr (i));
2781     }
2782
2783   return ret;
2784 }
2785
2786 /* Insert STMT on all the outgoing edges out of BB.  Note that if BB
2787    has more than one edge, STMT will be replicated for each edge.  Also,
2788    abnormal edges will be ignored.  */
2789
2790 void
2791 insert_edge_copies (tree stmt, basic_block bb)
2792 {
2793   edge e;
2794   edge_iterator ei;
2795   bool first_copy;
2796
2797   first_copy = true;
2798   FOR_EACH_EDGE (e, ei, bb->succs)
2799     {
2800       /* We don't need to insert copies on abnormal edges.  The
2801          value of the scalar replacement is not guaranteed to
2802          be valid through an abnormal edge.  */
2803       if (!(e->flags & EDGE_ABNORMAL))
2804         {
2805           if (first_copy)
2806             {
2807               bsi_insert_on_edge (e, stmt);
2808               first_copy = false;
2809             }
2810           else
2811             bsi_insert_on_edge (e, unsave_expr_now (stmt));
2812         }
2813     }
2814 }
2815
2816 /* Helper function to insert LIST before BSI, and set up line number info.  */
2817
2818 void
2819 sra_insert_before (block_stmt_iterator *bsi, tree list)
2820 {
2821   tree stmt = bsi_stmt (*bsi);
2822
2823   if (EXPR_HAS_LOCATION (stmt))
2824     annotate_all_with_locus (&list, EXPR_LOCATION (stmt));
2825   bsi_insert_before (bsi, list, BSI_SAME_STMT);
2826 }
2827
2828 /* Similarly, but insert after BSI.  Handles insertion onto edges as well.  */
2829
2830 void
2831 sra_insert_after (block_stmt_iterator *bsi, tree list)
2832 {
2833   tree stmt = bsi_stmt (*bsi);
2834
2835   if (EXPR_HAS_LOCATION (stmt))
2836     annotate_all_with_locus (&list, EXPR_LOCATION (stmt));
2837
2838   if (stmt_ends_bb_p (stmt))
2839     insert_edge_copies (list, bsi->bb);
2840   else
2841     bsi_insert_after (bsi, list, BSI_SAME_STMT);
2842 }
2843
2844 /* Similarly, but replace the statement at BSI.  */
2845
2846 static void
2847 sra_replace (block_stmt_iterator *bsi, tree list)
2848 {
2849   sra_insert_before (bsi, list);
2850   bsi_remove (bsi, false);
2851   if (bsi_end_p (*bsi))
2852     *bsi = bsi_last (bsi->bb);
2853   else
2854     bsi_prev (bsi);
2855 }
2856
2857 /* Data structure that bitfield_overlaps_p fills in with information
2858    about the element passed in and how much of it overlaps with the
2859    bit-range passed it to.  */
2860
2861 struct bitfield_overlap_info
2862 {
2863   /* The bit-length of an element.  */
2864   tree field_len;
2865
2866   /* The bit-position of the element in its parent.  */
2867   tree field_pos;
2868
2869   /* The number of bits of the element that overlap with the incoming
2870      bit range.  */
2871   tree overlap_len;
2872
2873   /* The first bit of the element that overlaps with the incoming bit
2874      range.  */
2875   tree overlap_pos;
2876 };
2877
2878 /* Return true if a BIT_FIELD_REF<(FLD->parent), BLEN, BPOS>
2879    expression (refereced as BF below) accesses any of the bits in FLD,
2880    false if it doesn't.  If DATA is non-null, its field_len and
2881    field_pos are filled in such that BIT_FIELD_REF<(FLD->parent),
2882    field_len, field_pos> (referenced as BFLD below) represents the
2883    entire field FLD->element, and BIT_FIELD_REF<BFLD, overlap_len,
2884    overlap_pos> represents the portion of the entire field that
2885    overlaps with BF.  */
2886
2887 static bool
2888 bitfield_overlaps_p (tree blen, tree bpos, struct sra_elt *fld,
2889                      struct bitfield_overlap_info *data)
2890 {
2891   tree flen, fpos;
2892   bool ret;
2893
2894   if (TREE_CODE (fld->element) == FIELD_DECL)
2895     {
2896       flen = fold_convert (bitsizetype, DECL_SIZE (fld->element));
2897       fpos = fold_convert (bitsizetype, DECL_FIELD_OFFSET (fld->element));
2898       fpos = size_binop (MULT_EXPR, fpos, bitsize_int (BITS_PER_UNIT));
2899       fpos = size_binop (PLUS_EXPR, fpos, DECL_FIELD_BIT_OFFSET (fld->element));
2900     }
2901   else if (TREE_CODE (fld->element) == BIT_FIELD_REF)
2902     {
2903       flen = fold_convert (bitsizetype, TREE_OPERAND (fld->element, 1));
2904       fpos = fold_convert (bitsizetype, TREE_OPERAND (fld->element, 2));
2905     }
2906   else if (TREE_CODE (fld->element) == INTEGER_CST)
2907     {
2908       flen = fold_convert (bitsizetype, TYPE_SIZE (fld->type));
2909       fpos = fold_convert (bitsizetype, fld->element);
2910       fpos = size_binop (MULT_EXPR, flen, fpos);
2911     }
2912   else
2913     gcc_unreachable ();
2914
2915   gcc_assert (host_integerp (blen, 1)
2916               && host_integerp (bpos, 1)
2917               && host_integerp (flen, 1)
2918               && host_integerp (fpos, 1));
2919
2920   ret = ((!tree_int_cst_lt (fpos, bpos)
2921           && tree_int_cst_lt (size_binop (MINUS_EXPR, fpos, bpos),
2922                               blen))
2923          || (!tree_int_cst_lt (bpos, fpos)
2924              && tree_int_cst_lt (size_binop (MINUS_EXPR, bpos, fpos),
2925                                  flen)));
2926
2927   if (!ret)
2928     return ret;
2929
2930   if (data)
2931     {
2932       tree bend, fend;
2933
2934       data->field_len = flen;
2935       data->field_pos = fpos;
2936
2937       fend = size_binop (PLUS_EXPR, fpos, flen);
2938       bend = size_binop (PLUS_EXPR, bpos, blen);
2939
2940       if (tree_int_cst_lt (bend, fend))
2941         data->overlap_len = size_binop (MINUS_EXPR, bend, fpos);
2942       else
2943         data->overlap_len = NULL;
2944
2945       if (tree_int_cst_lt (fpos, bpos))
2946         {
2947           data->overlap_pos = size_binop (MINUS_EXPR, bpos, fpos);
2948           data->overlap_len = size_binop (MINUS_EXPR,
2949                                           data->overlap_len
2950                                           ? data->overlap_len
2951                                           : data->field_len,
2952                                           data->overlap_pos);
2953         }
2954       else
2955         data->overlap_pos = NULL;
2956     }
2957
2958   return ret;
2959 }
2960
2961 /* Add to LISTP a sequence of statements that copies BLEN bits between
2962    VAR and the scalarized elements of ELT, starting a bit VPOS of VAR
2963    and at bit BPOS of ELT.  The direction of the copy is given by
2964    TO_VAR.  */
2965
2966 static void
2967 sra_explode_bitfield_assignment (tree var, tree vpos, bool to_var,
2968                                  tree *listp, tree blen, tree bpos,
2969                                  struct sra_elt *elt)
2970 {
2971   struct sra_elt *fld;
2972   struct bitfield_overlap_info flp;
2973
2974   FOR_EACH_ACTUAL_CHILD (fld, elt)
2975     {
2976       tree flen, fpos;
2977
2978       if (!bitfield_overlaps_p (blen, bpos, fld, &flp))
2979         continue;
2980
2981       flen = flp.overlap_len ? flp.overlap_len : flp.field_len;
2982       fpos = flp.overlap_pos ? flp.overlap_pos : bitsize_int (0);
2983
2984       if (fld->replacement)
2985         {
2986           tree infld, invar, st, type;
2987
2988           infld = fld->replacement;
2989
2990           type = TREE_TYPE (infld);
2991           if (TYPE_PRECISION (type) != TREE_INT_CST_LOW (flen))
2992             type = lang_hooks.types.type_for_size (TREE_INT_CST_LOW (flen), 1);
2993
2994           if (TREE_CODE (infld) == BIT_FIELD_REF)
2995             {
2996               fpos = size_binop (PLUS_EXPR, fpos, TREE_OPERAND (infld, 2));
2997               infld = TREE_OPERAND (infld, 0);
2998             }
2999           else if (BYTES_BIG_ENDIAN && DECL_P (fld->element)
3000                    && !tree_int_cst_equal (TYPE_SIZE (TREE_TYPE (infld)),
3001                                            DECL_SIZE (fld->element)))
3002             {
3003               fpos = size_binop (PLUS_EXPR, fpos,
3004                                  TYPE_SIZE (TREE_TYPE (infld)));
3005               fpos = size_binop (MINUS_EXPR, fpos,
3006                                  DECL_SIZE (fld->element));
3007             }
3008
3009           infld = fold_build3 (BIT_FIELD_REF, type, infld, flen, fpos);
3010           BIT_FIELD_REF_UNSIGNED (infld) = 1;
3011
3012           invar = size_binop (MINUS_EXPR, flp.field_pos, bpos);
3013           if (flp.overlap_pos)
3014             invar = size_binop (PLUS_EXPR, invar, flp.overlap_pos);
3015           invar = size_binop (PLUS_EXPR, invar, vpos);
3016
3017           invar = fold_build3 (BIT_FIELD_REF, type, var, flen, invar);
3018           BIT_FIELD_REF_UNSIGNED (invar) = 1;
3019
3020           if (to_var)
3021             st = sra_build_bf_assignment (invar, infld);
3022           else
3023             st = sra_build_bf_assignment (infld, invar);
3024
3025           append_to_statement_list (st, listp);
3026         }
3027       else
3028         {
3029           tree sub = size_binop (MINUS_EXPR, flp.field_pos, bpos);
3030           sub = size_binop (PLUS_EXPR, vpos, sub);
3031           if (flp.overlap_pos)
3032             sub = size_binop (PLUS_EXPR, sub, flp.overlap_pos);
3033
3034           sra_explode_bitfield_assignment (var, sub, to_var, listp,
3035                                            flen, fpos, fld);
3036         }
3037     }
3038 }
3039
3040 /* Add to LISTBEFOREP statements that copy scalarized members of ELT
3041    that overlap with BIT_FIELD_REF<(ELT->element), BLEN, BPOS> back
3042    into the full variable, and to LISTAFTERP, if non-NULL, statements
3043    that copy the (presumably modified) overlapping portions of the
3044    full variable back to the scalarized variables.  */
3045
3046 static void
3047 sra_sync_for_bitfield_assignment (tree *listbeforep, tree *listafterp,
3048                                   tree blen, tree bpos,
3049                                   struct sra_elt *elt)
3050 {
3051   struct sra_elt *fld;
3052   struct bitfield_overlap_info flp;
3053
3054   FOR_EACH_ACTUAL_CHILD (fld, elt)
3055     if (bitfield_overlaps_p (blen, bpos, fld, &flp))
3056       {
3057         if (fld->replacement || (!flp.overlap_len && !flp.overlap_pos))
3058           {
3059             generate_copy_inout (fld, false, generate_element_ref (fld),
3060                                  listbeforep);
3061             mark_no_warning (fld);
3062             if (listafterp)
3063               generate_copy_inout (fld, true, generate_element_ref (fld),
3064                                    listafterp);
3065           }
3066         else
3067           {
3068             tree flen = flp.overlap_len ? flp.overlap_len : flp.field_len;
3069             tree fpos = flp.overlap_pos ? flp.overlap_pos : bitsize_int (0);
3070
3071             sra_sync_for_bitfield_assignment (listbeforep, listafterp,
3072                                               flen, fpos, fld);
3073           }
3074       }
3075 }
3076
3077 /* Scalarize a USE.  To recap, this is either a simple reference to ELT,
3078    if elt is scalar, or some occurrence of ELT that requires a complete
3079    aggregate.  IS_OUTPUT is true if ELT is being modified.  */
3080
3081 static void
3082 scalarize_use (struct sra_elt *elt, tree *expr_p, block_stmt_iterator *bsi,
3083                bool is_output, bool use_all)
3084 {
3085   tree stmt = bsi_stmt (*bsi);
3086   tree bfexpr;
3087
3088   if (elt->replacement)
3089     {
3090       tree replacement = elt->replacement;
3091
3092       /* If we have a replacement, then updating the reference is as
3093          simple as modifying the existing statement in place.  */
3094       if (is_output
3095           && TREE_CODE (elt->replacement) == BIT_FIELD_REF
3096           && is_gimple_reg (TREE_OPERAND (elt->replacement, 0))
3097           && TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
3098           && &GIMPLE_STMT_OPERAND (stmt, 0) == expr_p)
3099         {
3100           tree newstmt = sra_build_elt_assignment
3101             (elt, GIMPLE_STMT_OPERAND (stmt, 1));
3102           if (TREE_CODE (newstmt) != STATEMENT_LIST)
3103             {
3104               tree list = NULL;
3105               append_to_statement_list (newstmt, &list);
3106               newstmt = list;
3107             }
3108           sra_replace (bsi, newstmt);
3109           return;
3110         }
3111       else if (!is_output
3112                && TREE_CODE (elt->replacement) == BIT_FIELD_REF
3113                && TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
3114                && &GIMPLE_STMT_OPERAND (stmt, 1) == expr_p)
3115         {
3116           tree tmp = make_rename_temp
3117             (TREE_TYPE (GIMPLE_STMT_OPERAND (stmt, 0)), "SR");
3118           tree newstmt = sra_build_assignment (tmp, REPLDUP (elt->replacement));
3119
3120           if (TREE_CODE (newstmt) != STATEMENT_LIST)
3121             {
3122               tree list = NULL;
3123               append_to_statement_list (newstmt, &list);
3124               newstmt = list;
3125             }
3126           sra_insert_before (bsi, newstmt);
3127           replacement = tmp;
3128         }
3129       if (is_output)
3130           mark_all_v_defs (stmt);
3131       *expr_p = REPLDUP (replacement);
3132       update_stmt (stmt);
3133     }
3134   else if (use_all && is_output
3135            && TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
3136            && TREE_CODE (bfexpr
3137                          = GIMPLE_STMT_OPERAND (stmt, 0)) == BIT_FIELD_REF
3138            && &TREE_OPERAND (bfexpr, 0) == expr_p
3139            && INTEGRAL_TYPE_P (TREE_TYPE (bfexpr))
3140            && TREE_CODE (TREE_TYPE (*expr_p)) == RECORD_TYPE)
3141     {
3142       tree listbefore = NULL, listafter = NULL;
3143       tree blen = fold_convert (bitsizetype, TREE_OPERAND (bfexpr, 1));
3144       tree bpos = fold_convert (bitsizetype, TREE_OPERAND (bfexpr, 2));
3145       bool update = false;
3146
3147       if (!elt->use_block_copy)
3148         {
3149           tree type = TREE_TYPE (bfexpr);
3150           tree var = make_rename_temp (type, "SR"), tmp, st;
3151
3152           GIMPLE_STMT_OPERAND (stmt, 0) = var;
3153           update = true;
3154
3155           if (!TYPE_UNSIGNED (type))
3156             {
3157               type = unsigned_type_for (type);
3158               tmp = make_rename_temp (type, "SR");
3159               st = build_gimple_modify_stmt (tmp,
3160                                              fold_convert (type, var));
3161               append_to_statement_list (st, &listafter);
3162               var = tmp;
3163             }
3164
3165           sra_explode_bitfield_assignment
3166             (var, bitsize_int (0), false, &listafter, blen, bpos, elt);
3167         }
3168       else
3169         sra_sync_for_bitfield_assignment
3170           (&listbefore, &listafter, blen, bpos, elt);
3171
3172       if (listbefore)
3173         {
3174           mark_all_v_defs (listbefore);
3175           sra_insert_before (bsi, listbefore);
3176         }
3177       if (listafter)
3178         {
3179           mark_all_v_defs (listafter);
3180           sra_insert_after (bsi, listafter);
3181         }
3182
3183       if (update)
3184         update_stmt (stmt);
3185     }
3186   else if (use_all && !is_output
3187            && TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
3188            && TREE_CODE (bfexpr
3189                          = GIMPLE_STMT_OPERAND (stmt, 1)) == BIT_FIELD_REF
3190            && &TREE_OPERAND (GIMPLE_STMT_OPERAND (stmt, 1), 0) == expr_p
3191            && INTEGRAL_TYPE_P (TREE_TYPE (bfexpr))
3192            && TREE_CODE (TREE_TYPE (*expr_p)) == RECORD_TYPE)
3193     {
3194       tree list = NULL;
3195       tree blen = fold_convert (bitsizetype, TREE_OPERAND (bfexpr, 1));
3196       tree bpos = fold_convert (bitsizetype, TREE_OPERAND (bfexpr, 2));
3197       bool update = false;
3198
3199       if (!elt->use_block_copy)
3200         {
3201           tree type = TREE_TYPE (bfexpr);
3202           tree var;
3203
3204           if (!TYPE_UNSIGNED (type))
3205             type = unsigned_type_for (type);
3206
3207           var = make_rename_temp (type, "SR");
3208
3209           append_to_statement_list (build_gimple_modify_stmt
3210                                     (var, build_int_cst_wide (type, 0, 0)),
3211                                     &list);
3212
3213           sra_explode_bitfield_assignment
3214             (var, bitsize_int (0), true, &list, blen, bpos, elt);
3215
3216           GIMPLE_STMT_OPERAND (stmt, 1) = var;
3217           update = true;
3218         }
3219       else
3220         sra_sync_for_bitfield_assignment
3221           (&list, NULL, blen, bpos, elt);
3222
3223       if (list)
3224         {
3225           mark_all_v_defs (list);
3226           sra_insert_before (bsi, list);
3227         }
3228
3229       if (update)
3230         update_stmt (stmt);
3231     }
3232   else
3233     {
3234       tree list = NULL;
3235
3236       /* Otherwise we need some copies.  If ELT is being read, then we
3237          want to store all (modified) sub-elements back into the
3238          structure before the reference takes place.  If ELT is being
3239          written, then we want to load the changed values back into
3240          our shadow variables.  */
3241       /* ??? We don't check modified for reads, we just always write all of
3242          the values.  We should be able to record the SSA number of the VOP
3243          for which the values were last read.  If that number matches the
3244          SSA number of the VOP in the current statement, then we needn't
3245          emit an assignment.  This would also eliminate double writes when
3246          a structure is passed as more than one argument to a function call.
3247          This optimization would be most effective if sra_walk_function
3248          processed the blocks in dominator order.  */
3249
3250       generate_copy_inout (elt, is_output, generate_element_ref (elt), &list);
3251       if (list == NULL)
3252         return;
3253       mark_all_v_defs (list);
3254       if (is_output)
3255         sra_insert_after (bsi, list);
3256       else
3257         {
3258           sra_insert_before (bsi, list);
3259           if (use_all)
3260             mark_no_warning (elt);
3261         }
3262     }
3263 }
3264
3265 /* Scalarize a COPY.  To recap, this is an assignment statement between
3266    two scalarizable references, LHS_ELT and RHS_ELT.  */
3267
3268 static void
3269 scalarize_copy (struct sra_elt *lhs_elt, struct sra_elt *rhs_elt,
3270                 block_stmt_iterator *bsi)
3271 {
3272   tree list, stmt;
3273
3274   if (lhs_elt->replacement && rhs_elt->replacement)
3275     {
3276       /* If we have two scalar operands, modify the existing statement.  */
3277       stmt = bsi_stmt (*bsi);
3278
3279       /* See the commentary in sra_walk_function concerning
3280          RETURN_EXPR, and why we should never see one here.  */
3281       gcc_assert (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT);
3282
3283       GIMPLE_STMT_OPERAND (stmt, 0) = lhs_elt->replacement;
3284       GIMPLE_STMT_OPERAND (stmt, 1) = REPLDUP (rhs_elt->replacement);
3285       update_stmt (stmt);
3286     }
3287   else if (lhs_elt->use_block_copy || rhs_elt->use_block_copy)
3288     {
3289       /* If either side requires a block copy, then sync the RHS back
3290          to the original structure, leave the original assignment
3291          statement (which will perform the block copy), then load the
3292          LHS values out of its now-updated original structure.  */
3293       /* ??? Could perform a modified pair-wise element copy.  That
3294          would at least allow those elements that are instantiated in
3295          both structures to be optimized well.  */
3296
3297       list = NULL;
3298       generate_copy_inout (rhs_elt, false,
3299                            generate_element_ref (rhs_elt), &list);
3300       if (list)
3301         {
3302           mark_all_v_defs (list);
3303           sra_insert_before (bsi, list);
3304         }
3305
3306       list = NULL;
3307       generate_copy_inout (lhs_elt, true,
3308                            generate_element_ref (lhs_elt), &list);
3309       if (list)
3310         {
3311           mark_all_v_defs (list);
3312           sra_insert_after (bsi, list);
3313         }
3314     }
3315   else
3316     {
3317       /* Otherwise both sides must be fully instantiated.  In which
3318          case perform pair-wise element assignments and replace the
3319          original block copy statement.  */
3320
3321       stmt = bsi_stmt (*bsi);
3322       mark_all_v_defs (stmt);
3323
3324       list = NULL;
3325       generate_element_copy (lhs_elt, rhs_elt, &list);
3326       gcc_assert (list);
3327       mark_all_v_defs (list);
3328       sra_replace (bsi, list);
3329     }
3330 }
3331
3332 /* Scalarize an INIT.  To recap, this is an assignment to a scalarizable
3333    reference from some form of constructor: CONSTRUCTOR, COMPLEX_CST or
3334    COMPLEX_EXPR.  If RHS is NULL, it should be treated as an empty
3335    CONSTRUCTOR.  */
3336
3337 static void
3338 scalarize_init (struct sra_elt *lhs_elt, tree rhs, block_stmt_iterator *bsi)
3339 {
3340   bool result = true;
3341   tree list = NULL;
3342
3343   /* Generate initialization statements for all members extant in the RHS.  */
3344   if (rhs)
3345     {
3346       /* Unshare the expression just in case this is from a decl's initial.  */
3347       rhs = unshare_expr (rhs);
3348       result = generate_element_init (lhs_elt, rhs, &list);
3349     }
3350
3351   /* CONSTRUCTOR is defined such that any member not mentioned is assigned
3352      a zero value.  Initialize the rest of the instantiated elements.  */
3353   generate_element_zero (lhs_elt, &list);
3354
3355   if (!result)
3356     {
3357       /* If we failed to convert the entire initializer, then we must
3358          leave the structure assignment in place and must load values
3359          from the structure into the slots for which we did not find
3360          constants.  The easiest way to do this is to generate a complete
3361          copy-out, and then follow that with the constant assignments
3362          that we were able to build.  DCE will clean things up.  */
3363       tree list0 = NULL;
3364       generate_copy_inout (lhs_elt, true, generate_element_ref (lhs_elt),
3365                            &list0);
3366       append_to_statement_list (list, &list0);
3367       list = list0;
3368     }
3369
3370   if (lhs_elt->use_block_copy || !result)
3371     {
3372       /* Since LHS is not fully instantiated, we must leave the structure
3373          assignment in place.  Treating this case differently from a USE
3374          exposes constants to later optimizations.  */
3375       if (list)
3376         {
3377           mark_all_v_defs (list);
3378           sra_insert_after (bsi, list);
3379         }
3380     }
3381   else
3382     {
3383       /* The LHS is fully instantiated.  The list of initializations
3384          replaces the original structure assignment.  */
3385       gcc_assert (list);
3386       mark_all_v_defs (bsi_stmt (*bsi));
3387       mark_all_v_defs (list);
3388       sra_replace (bsi, list);
3389     }
3390 }
3391
3392 /* A subroutine of scalarize_ldst called via walk_tree.  Set TREE_NO_TRAP
3393    on all INDIRECT_REFs.  */
3394
3395 static tree
3396 mark_notrap (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED)
3397 {
3398   tree t = *tp;
3399
3400   if (TREE_CODE (t) == INDIRECT_REF)
3401     {
3402       TREE_THIS_NOTRAP (t) = 1;
3403       *walk_subtrees = 0;
3404     }
3405   else if (IS_TYPE_OR_DECL_P (t))
3406     *walk_subtrees = 0;
3407
3408   return NULL;
3409 }
3410
3411 /* Scalarize a LDST.  To recap, this is an assignment between one scalarizable
3412    reference ELT and one non-scalarizable reference OTHER.  IS_OUTPUT is true
3413    if ELT is on the left-hand side.  */
3414
3415 static void
3416 scalarize_ldst (struct sra_elt *elt, tree other,
3417                 block_stmt_iterator *bsi, bool is_output)
3418 {
3419   /* Shouldn't have gotten called for a scalar.  */
3420   gcc_assert (!elt->replacement);
3421
3422   if (elt->use_block_copy)
3423     {
3424       /* Since ELT is not fully instantiated, we have to leave the
3425          block copy in place.  Treat this as a USE.  */
3426       scalarize_use (elt, NULL, bsi, is_output, false);
3427     }
3428   else
3429     {
3430       /* The interesting case is when ELT is fully instantiated.  In this
3431          case we can have each element stored/loaded directly to/from the
3432          corresponding slot in OTHER.  This avoids a block copy.  */
3433
3434       tree list = NULL, stmt = bsi_stmt (*bsi);
3435
3436       mark_all_v_defs (stmt);
3437       generate_copy_inout (elt, is_output, other, &list);
3438       gcc_assert (list);
3439       mark_all_v_defs (list);
3440
3441       /* Preserve EH semantics.  */
3442       if (stmt_ends_bb_p (stmt))
3443         {
3444           tree_stmt_iterator tsi;
3445           tree first, blist = NULL;
3446           bool thr = tree_could_throw_p (stmt);
3447
3448           /* If the last statement of this BB created an EH edge
3449              before scalarization, we have to locate the first
3450              statement that can throw in the new statement list and
3451              use that as the last statement of this BB, such that EH
3452              semantics is preserved.  All statements up to this one
3453              are added to the same BB.  All other statements in the
3454              list will be added to normal outgoing edges of the same
3455              BB.  If they access any memory, it's the same memory, so
3456              we can assume they won't throw.  */
3457           tsi = tsi_start (list);
3458           for (first = tsi_stmt (tsi);
3459                thr && !tsi_end_p (tsi) && !tree_could_throw_p (first);
3460                first = tsi_stmt (tsi))
3461             {
3462               tsi_delink (&tsi);
3463               append_to_statement_list (first, &blist);
3464             }
3465
3466           /* Extract the first remaining statement from LIST, this is
3467              the EH statement if there is one.  */
3468           tsi_delink (&tsi);
3469
3470           if (blist)
3471             sra_insert_before (bsi, blist);
3472
3473           /* Replace the old statement with this new representative.  */
3474           bsi_replace (bsi, first, true);
3475
3476           if (!tsi_end_p (tsi))
3477             {
3478               /* If any reference would trap, then they all would.  And more
3479                  to the point, the first would.  Therefore none of the rest
3480                  will trap since the first didn't.  Indicate this by
3481                  iterating over the remaining statements and set
3482                  TREE_THIS_NOTRAP in all INDIRECT_REFs.  */
3483               do
3484                 {
3485                   walk_tree (tsi_stmt_ptr (tsi), mark_notrap, NULL, NULL);
3486                   tsi_next (&tsi);
3487                 }
3488               while (!tsi_end_p (tsi));
3489
3490               insert_edge_copies (list, bsi->bb);
3491             }
3492         }
3493       else
3494         sra_replace (bsi, list);
3495     }
3496 }
3497
3498 /* Generate initializations for all scalarizable parameters.  */
3499
3500 static void
3501 scalarize_parms (void)
3502 {
3503   tree list = NULL;
3504   unsigned i;
3505   bitmap_iterator bi;
3506
3507   EXECUTE_IF_SET_IN_BITMAP (needs_copy_in, 0, i, bi)
3508     {
3509       tree var = referenced_var (i);
3510       struct sra_elt *elt = lookup_element (NULL, var, NULL, NO_INSERT);
3511       generate_copy_inout (elt, true, var, &list);
3512     }
3513
3514   if (list)
3515     {
3516       insert_edge_copies (list, ENTRY_BLOCK_PTR);
3517       mark_all_v_defs (list);
3518     }
3519 }
3520
3521 /* Entry point to phase 4.  Update the function to match replacements.  */
3522
3523 static void
3524 scalarize_function (void)
3525 {
3526   static const struct sra_walk_fns fns = {
3527     scalarize_use, scalarize_copy, scalarize_init, scalarize_ldst, false
3528   };
3529
3530   sra_walk_function (&fns);
3531   scalarize_parms ();
3532   bsi_commit_edge_inserts ();
3533 }
3534
3535 \f
3536 /* Debug helper function.  Print ELT in a nice human-readable format.  */
3537
3538 static void
3539 dump_sra_elt_name (FILE *f, struct sra_elt *elt)
3540 {
3541   if (elt->parent && TREE_CODE (elt->parent->type) == COMPLEX_TYPE)
3542     {
3543       fputs (elt->element == integer_zero_node ? "__real__ " : "__imag__ ", f);
3544       dump_sra_elt_name (f, elt->parent);
3545     }
3546   else
3547     {
3548       if (elt->parent)
3549         dump_sra_elt_name (f, elt->parent);
3550       if (DECL_P (elt->element))
3551         {
3552           if (TREE_CODE (elt->element) == FIELD_DECL)
3553             fputc ('.', f);
3554           print_generic_expr (f, elt->element, dump_flags);
3555         }
3556       else if (TREE_CODE (elt->element) == BIT_FIELD_REF)
3557         fprintf (f, "$B" HOST_WIDE_INT_PRINT_DEC "F" HOST_WIDE_INT_PRINT_DEC,
3558                  tree_low_cst (TREE_OPERAND (elt->element, 2), 1),