OSDN Git Service

PR middle-end/22156
[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                                  BITS_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 (BITS_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_equal (cst2, TYPE_SIZE (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 (BITS_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   cst = int_const_binop (LSHIFT_EXPR, mask, maxshift, true);
2347   cst2 = int_const_binop (LSHIFT_EXPR, mask, minshift, true);
2348   mask = int_const_binop (MINUS_EXPR, cst, cst2, true);
2349   mask = fold_build1 (BIT_NOT_EXPR, utype, mask);
2350
2351   if (TYPE_MAIN_VARIANT (utype) != TYPE_MAIN_VARIANT (TREE_TYPE (var))
2352       && !integer_zerop (mask))
2353     {
2354       tmp = var;
2355       if (!is_gimple_variable (tmp))
2356         tmp = unshare_expr (var);
2357
2358       tmp2 = make_rename_temp (utype, "SR");
2359
2360       if (INTEGRAL_TYPE_P (TREE_TYPE (var)))
2361         stmt = build_gimple_modify_stmt (tmp2, fold_convert (utype, tmp));
2362       else
2363         stmt = build_gimple_modify_stmt (tmp2, fold_build1 (VIEW_CONVERT_EXPR,
2364                                                             utype, tmp));
2365       append_to_statement_list (stmt, &list);
2366     }
2367   else
2368     tmp2 = var;
2369
2370   if (!integer_zerop (mask))
2371     {
2372       tmp = make_rename_temp (utype, "SR");
2373       stmt = build_gimple_modify_stmt (tmp,
2374                                        fold_build2 (BIT_AND_EXPR, utype,
2375                                                     tmp2, mask));
2376       append_to_statement_list (stmt, &list);
2377     }
2378   else
2379     tmp = mask;
2380
2381   if (is_gimple_reg (src) && INTEGRAL_TYPE_P (TREE_TYPE (src)))
2382     tmp2 = src;
2383   else if (INTEGRAL_TYPE_P (TREE_TYPE (src)))
2384     {
2385       tmp2 = make_rename_temp (TREE_TYPE (src), "SR");
2386       stmt = sra_build_assignment (tmp2, src);
2387       append_to_statement_list (stmt, &list);
2388     }
2389   else
2390     {
2391       tmp2 = make_rename_temp
2392         (lang_hooks.types.type_for_size
2393          (TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (src))),
2394           1), "SR");
2395       stmt = sra_build_assignment (tmp2, fold_build1 (VIEW_CONVERT_EXPR,
2396                                                       TREE_TYPE (tmp2), src));
2397       append_to_statement_list (stmt, &list);
2398     }
2399
2400   if (!TYPE_UNSIGNED (TREE_TYPE (tmp2)))
2401     {
2402       tree ut = unsigned_type_for (TREE_TYPE (tmp2));
2403       tmp3 = make_rename_temp (ut, "SR");
2404       tmp2 = fold_convert (ut, tmp2);
2405       stmt = sra_build_assignment (tmp3, tmp2);
2406       append_to_statement_list (stmt, &list);
2407
2408       tmp2 = fold_build1 (BIT_NOT_EXPR, utype, mask);
2409       tmp2 = int_const_binop (RSHIFT_EXPR, tmp2, minshift, true);
2410       tmp2 = fold_convert (ut, tmp2);
2411       tmp2 = fold_build2 (BIT_AND_EXPR, utype, tmp3, tmp2);
2412
2413       if (tmp3 != tmp2)
2414         {
2415           tmp3 = make_rename_temp (ut, "SR");
2416           stmt = sra_build_assignment (tmp3, tmp2);
2417           append_to_statement_list (stmt, &list);
2418         }
2419
2420       tmp2 = tmp3;
2421     }
2422
2423   if (TYPE_MAIN_VARIANT (TREE_TYPE (tmp2)) != TYPE_MAIN_VARIANT (utype))
2424     {
2425       tmp3 = make_rename_temp (utype, "SR");
2426       tmp2 = fold_convert (utype, tmp2);
2427       stmt = sra_build_assignment (tmp3, tmp2);
2428       append_to_statement_list (stmt, &list);
2429       tmp2 = tmp3;
2430     }
2431
2432   if (!integer_zerop (minshift))
2433     {
2434       tmp3 = make_rename_temp (utype, "SR");
2435       stmt = build_gimple_modify_stmt (tmp3,
2436                                        fold_build2 (LSHIFT_EXPR, utype,
2437                                                     tmp2, minshift));
2438       append_to_statement_list (stmt, &list);
2439       tmp2 = tmp3;
2440     }
2441
2442   if (utype != TREE_TYPE (var))
2443     tmp3 = make_rename_temp (utype, "SR");
2444   else
2445     tmp3 = var;
2446   stmt = build_gimple_modify_stmt (tmp3,
2447                                    fold_build2 (BIT_IOR_EXPR, utype,
2448                                                 tmp, tmp2));
2449   append_to_statement_list (stmt, &list);
2450
2451   if (tmp3 != var)
2452     {
2453       if (TREE_TYPE (var) == type)
2454         stmt = build_gimple_modify_stmt (var,
2455                                          fold_convert (type, tmp3));
2456       else
2457         stmt = build_gimple_modify_stmt (var,
2458                                          fold_build1 (VIEW_CONVERT_EXPR,
2459                                                       TREE_TYPE (var), tmp3));
2460       append_to_statement_list (stmt, &list);
2461     }
2462
2463   return list;
2464 }
2465
2466 /* Expand an assignment of SRC to the scalarized representation of
2467    ELT.  If it is a field group, try to widen the assignment to cover
2468    the full variable.  */
2469
2470 static tree
2471 sra_build_elt_assignment (struct sra_elt *elt, tree src)
2472 {
2473   tree dst = elt->replacement;
2474   tree var, tmp, cst, cst2, list, stmt;
2475
2476   if (TREE_CODE (dst) != BIT_FIELD_REF
2477       || !elt->in_bitfld_block)
2478     return sra_build_assignment (REPLDUP (dst), src);
2479
2480   var = TREE_OPERAND (dst, 0);
2481
2482   /* Try to widen the assignment to the entire variable.
2483      We need the source to be a BIT_FIELD_REF as well, such that, for
2484      BIT_FIELD_REF<d,sz,dp> = BIT_FIELD_REF<s,sz,sp>,
2485      by design, conditions are met such that we can turn it into
2486      d = BIT_FIELD_REF<s,dw,sp-dp>.  */
2487   if (elt->in_bitfld_block == 2
2488       && TREE_CODE (src) == BIT_FIELD_REF)
2489     {
2490       cst = TYPE_SIZE (TREE_TYPE (var));
2491       cst2 = size_binop (MINUS_EXPR, TREE_OPERAND (src, 2),
2492                          TREE_OPERAND (dst, 2));
2493
2494       src = TREE_OPERAND (src, 0);
2495
2496       /* Avoid full-width bit-fields.  */
2497       if (integer_zerop (cst2)
2498           && tree_int_cst_equal (cst, TYPE_SIZE (TREE_TYPE (src))))
2499         {
2500           if (INTEGRAL_TYPE_P (TREE_TYPE (src))
2501               && !TYPE_UNSIGNED (TREE_TYPE (src)))
2502             src = fold_convert (unsigned_type_for (TREE_TYPE (src)), src);
2503
2504           /* If a single conversion won't do, we'll need a statement
2505              list.  */
2506           if (TYPE_MAIN_VARIANT (TREE_TYPE (var))
2507               != TYPE_MAIN_VARIANT (TREE_TYPE (src)))
2508             {
2509               list = NULL;
2510
2511               if (!INTEGRAL_TYPE_P (TREE_TYPE (src))
2512                   || !TYPE_UNSIGNED (TREE_TYPE (src)))
2513                 src = fold_build1 (VIEW_CONVERT_EXPR,
2514                                    lang_hooks.types.type_for_size
2515                                    (TREE_INT_CST_LOW
2516                                     (TYPE_SIZE (TREE_TYPE (src))),
2517                                     1), src);
2518
2519               tmp = make_rename_temp (TREE_TYPE (src), "SR");
2520               stmt = build_gimple_modify_stmt (tmp, src);
2521               append_to_statement_list (stmt, &list);
2522
2523               stmt = sra_build_assignment (var,
2524                                            fold_convert (TREE_TYPE (var),
2525                                                          tmp));
2526               append_to_statement_list (stmt, &list);
2527
2528               return list;
2529             }
2530
2531           src = fold_convert (TREE_TYPE (var), src);
2532         }
2533       else
2534         {
2535           src = fold_build3 (BIT_FIELD_REF, TREE_TYPE (var), src, cst, cst2);
2536           BIT_FIELD_REF_UNSIGNED (src) = 1;
2537         }
2538
2539       return sra_build_assignment (var, src);
2540     }
2541
2542   return sra_build_bf_assignment (dst, src);
2543 }
2544
2545 /* Generate a set of assignment statements in *LIST_P to copy all
2546    instantiated elements under ELT to or from the equivalent structure
2547    rooted at EXPR.  COPY_OUT controls the direction of the copy, with
2548    true meaning to copy out of EXPR into ELT.  */
2549
2550 static void
2551 generate_copy_inout (struct sra_elt *elt, bool copy_out, tree expr,
2552                      tree *list_p)
2553 {
2554   struct sra_elt *c;
2555   tree t;
2556
2557   if (!copy_out && TREE_CODE (expr) == SSA_NAME
2558       && TREE_CODE (TREE_TYPE (expr)) == COMPLEX_TYPE)
2559     {
2560       tree r, i;
2561
2562       c = lookup_element (elt, integer_zero_node, NULL, NO_INSERT);
2563       r = c->replacement;
2564       c = lookup_element (elt, integer_one_node, NULL, NO_INSERT);
2565       i = c->replacement;
2566
2567       t = build2 (COMPLEX_EXPR, elt->type, r, i);
2568       t = sra_build_bf_assignment (expr, t);
2569       SSA_NAME_DEF_STMT (expr) = t;
2570       append_to_statement_list (t, list_p);
2571     }
2572   else if (elt->replacement)
2573     {
2574       if (copy_out)
2575         t = sra_build_elt_assignment (elt, expr);
2576       else
2577         t = sra_build_bf_assignment (expr, REPLDUP (elt->replacement));
2578       append_to_statement_list (t, list_p);
2579     }
2580   else
2581     {
2582       FOR_EACH_ACTUAL_CHILD (c, elt)
2583         {
2584           t = generate_one_element_ref (c, unshare_expr (expr));
2585           generate_copy_inout (c, copy_out, t, list_p);
2586         }
2587     }
2588 }
2589
2590 /* Generate a set of assignment statements in *LIST_P to copy all instantiated
2591    elements under SRC to their counterparts under DST.  There must be a 1-1
2592    correspondence of instantiated elements.  */
2593
2594 static void
2595 generate_element_copy (struct sra_elt *dst, struct sra_elt *src, tree *list_p)
2596 {
2597   struct sra_elt *dc, *sc;
2598
2599   FOR_EACH_ACTUAL_CHILD (dc, dst)
2600     {
2601       sc = lookup_element (src, dc->element, NULL, NO_INSERT);
2602       if (!sc && dc->in_bitfld_block == 2)
2603         {
2604           struct sra_elt *dcs;
2605
2606           FOR_EACH_ACTUAL_CHILD (dcs, dc)
2607             {
2608               sc = lookup_element (src, dcs->element, NULL, NO_INSERT);
2609               gcc_assert (sc);
2610               generate_element_copy (dcs, sc, list_p);
2611             }
2612
2613           continue;
2614         }
2615       gcc_assert (sc);
2616       generate_element_copy (dc, sc, list_p);
2617     }
2618
2619   if (dst->replacement)
2620     {
2621       tree t;
2622
2623       gcc_assert (src->replacement);
2624
2625       t = sra_build_elt_assignment (dst, REPLDUP (src->replacement));
2626       append_to_statement_list (t, list_p);
2627     }
2628 }
2629
2630 /* Generate a set of assignment statements in *LIST_P to zero all instantiated
2631    elements under ELT.  In addition, do not assign to elements that have been
2632    marked VISITED but do reset the visited flag; this allows easy coordination
2633    with generate_element_init.  */
2634
2635 static void
2636 generate_element_zero (struct sra_elt *elt, tree *list_p)
2637 {
2638   struct sra_elt *c;
2639
2640   if (elt->visited)
2641     {
2642       elt->visited = false;
2643       return;
2644     }
2645
2646   if (!elt->in_bitfld_block)
2647     FOR_EACH_ACTUAL_CHILD (c, elt)
2648       generate_element_zero (c, list_p);
2649
2650   if (elt->replacement)
2651     {
2652       tree t;
2653
2654       gcc_assert (elt->is_scalar);
2655       t = fold_convert (elt->type, integer_zero_node);
2656
2657       t = sra_build_elt_assignment (elt, t);
2658       append_to_statement_list (t, list_p);
2659     }
2660 }
2661
2662 /* Generate an assignment VAR = INIT, where INIT may need gimplification.
2663    Add the result to *LIST_P.  */
2664
2665 static void
2666 generate_one_element_init (struct sra_elt *elt, tree init, tree *list_p)
2667 {
2668   /* The replacement can be almost arbitrarily complex.  Gimplify.  */
2669   tree stmt = sra_build_elt_assignment (elt, init);
2670   gimplify_and_add (stmt, list_p);
2671 }
2672
2673 /* Generate a set of assignment statements in *LIST_P to set all instantiated
2674    elements under ELT with the contents of the initializer INIT.  In addition,
2675    mark all assigned elements VISITED; this allows easy coordination with
2676    generate_element_zero.  Return false if we found a case we couldn't
2677    handle.  */
2678
2679 static bool
2680 generate_element_init_1 (struct sra_elt *elt, tree init, tree *list_p)
2681 {
2682   bool result = true;
2683   enum tree_code init_code;
2684   struct sra_elt *sub;
2685   tree t;
2686   unsigned HOST_WIDE_INT idx;
2687   tree value, purpose;
2688
2689   /* We can be passed DECL_INITIAL of a static variable.  It might have a
2690      conversion, which we strip off here.  */
2691   STRIP_USELESS_TYPE_CONVERSION (init);
2692   init_code = TREE_CODE (init);
2693
2694   if (elt->is_scalar)
2695     {
2696       if (elt->replacement)
2697         {
2698           generate_one_element_init (elt, init, list_p);
2699           elt->visited = true;
2700         }
2701       return result;
2702     }
2703
2704   switch (init_code)
2705     {
2706     case COMPLEX_CST:
2707     case COMPLEX_EXPR:
2708       FOR_EACH_ACTUAL_CHILD (sub, elt)
2709         {
2710           if (sub->element == integer_zero_node)
2711             t = (init_code == COMPLEX_EXPR
2712                  ? TREE_OPERAND (init, 0) : TREE_REALPART (init));
2713           else
2714             t = (init_code == COMPLEX_EXPR
2715                  ? TREE_OPERAND (init, 1) : TREE_IMAGPART (init));
2716           result &= generate_element_init_1 (sub, t, list_p);
2717         }
2718       break;
2719
2720     case CONSTRUCTOR:
2721       FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (init), idx, purpose, value)
2722         {
2723           if (TREE_CODE (purpose) == RANGE_EXPR)
2724             {
2725               tree lower = TREE_OPERAND (purpose, 0);
2726               tree upper = TREE_OPERAND (purpose, 1);
2727
2728               while (1)
2729                 {
2730                   sub = lookup_element (elt, lower, NULL, NO_INSERT);
2731                   if (sub != NULL)
2732                     result &= generate_element_init_1 (sub, value, list_p);
2733                   if (tree_int_cst_equal (lower, upper))
2734                     break;
2735                   lower = int_const_binop (PLUS_EXPR, lower,
2736                                            integer_one_node, true);
2737                 }
2738             }
2739           else
2740             {
2741               sub = lookup_element (elt, purpose, NULL, NO_INSERT);
2742               if (sub != NULL)
2743                 result &= generate_element_init_1 (sub, value, list_p);
2744             }
2745         }
2746       break;
2747
2748     default:
2749       elt->visited = true;
2750       result = false;
2751     }
2752
2753   return result;
2754 }
2755
2756 /* A wrapper function for generate_element_init_1 that handles cleanup after
2757    gimplification.  */
2758
2759 static bool
2760 generate_element_init (struct sra_elt *elt, tree init, tree *list_p)
2761 {
2762   bool ret;
2763
2764   push_gimplify_context ();
2765   ret = generate_element_init_1 (elt, init, list_p);
2766   pop_gimplify_context (NULL);
2767
2768   /* The replacement can expose previously unreferenced variables.  */
2769   if (ret && *list_p)
2770     {
2771       tree_stmt_iterator i;
2772
2773       for (i = tsi_start (*list_p); !tsi_end_p (i); tsi_next (&i))
2774         find_new_referenced_vars (tsi_stmt_ptr (i));
2775     }
2776
2777   return ret;
2778 }
2779
2780 /* Insert STMT on all the outgoing edges out of BB.  Note that if BB
2781    has more than one edge, STMT will be replicated for each edge.  Also,
2782    abnormal edges will be ignored.  */
2783
2784 void
2785 insert_edge_copies (tree stmt, basic_block bb)
2786 {
2787   edge e;
2788   edge_iterator ei;
2789   bool first_copy;
2790
2791   first_copy = true;
2792   FOR_EACH_EDGE (e, ei, bb->succs)
2793     {
2794       /* We don't need to insert copies on abnormal edges.  The
2795          value of the scalar replacement is not guaranteed to
2796          be valid through an abnormal edge.  */
2797       if (!(e->flags & EDGE_ABNORMAL))
2798         {
2799           if (first_copy)
2800             {
2801               bsi_insert_on_edge (e, stmt);
2802               first_copy = false;
2803             }
2804           else
2805             bsi_insert_on_edge (e, unsave_expr_now (stmt));
2806         }
2807     }
2808 }
2809
2810 /* Helper function to insert LIST before BSI, and set up line number info.  */
2811
2812 void
2813 sra_insert_before (block_stmt_iterator *bsi, tree list)
2814 {
2815   tree stmt = bsi_stmt (*bsi);
2816
2817   if (EXPR_HAS_LOCATION (stmt))
2818     annotate_all_with_locus (&list, EXPR_LOCATION (stmt));
2819   bsi_insert_before (bsi, list, BSI_SAME_STMT);
2820 }
2821
2822 /* Similarly, but insert after BSI.  Handles insertion onto edges as well.  */
2823
2824 void
2825 sra_insert_after (block_stmt_iterator *bsi, tree list)
2826 {
2827   tree stmt = bsi_stmt (*bsi);
2828
2829   if (EXPR_HAS_LOCATION (stmt))
2830     annotate_all_with_locus (&list, EXPR_LOCATION (stmt));
2831
2832   if (stmt_ends_bb_p (stmt))
2833     insert_edge_copies (list, bsi->bb);
2834   else
2835     bsi_insert_after (bsi, list, BSI_SAME_STMT);
2836 }
2837
2838 /* Similarly, but replace the statement at BSI.  */
2839
2840 static void
2841 sra_replace (block_stmt_iterator *bsi, tree list)
2842 {
2843   sra_insert_before (bsi, list);
2844   bsi_remove (bsi, false);
2845   if (bsi_end_p (*bsi))
2846     *bsi = bsi_last (bsi->bb);
2847   else
2848     bsi_prev (bsi);
2849 }
2850
2851 /* Data structure that bitfield_overlaps_p fills in with information
2852    about the element passed in and how much of it overlaps with the
2853    bit-range passed it to.  */
2854
2855 struct bitfield_overlap_info
2856 {
2857   /* The bit-length of an element.  */
2858   tree field_len;
2859
2860   /* The bit-position of the element in its parent.  */
2861   tree field_pos;
2862
2863   /* The number of bits of the element that overlap with the incoming
2864      bit range.  */
2865   tree overlap_len;
2866
2867   /* The first bit of the element that overlaps with the incoming bit
2868      range.  */
2869   tree overlap_pos;
2870 };
2871
2872 /* Return true if a BIT_FIELD_REF<(FLD->parent), BLEN, BPOS>
2873    expression (refereced as BF below) accesses any of the bits in FLD,
2874    false if it doesn't.  If DATA is non-null, its field_len and
2875    field_pos are filled in such that BIT_FIELD_REF<(FLD->parent),
2876    field_len, field_pos> (referenced as BFLD below) represents the
2877    entire field FLD->element, and BIT_FIELD_REF<BFLD, overlap_len,
2878    overlap_pos> represents the portion of the entire field that
2879    overlaps with BF.  */
2880
2881 static bool
2882 bitfield_overlaps_p (tree blen, tree bpos, struct sra_elt *fld,
2883                      struct bitfield_overlap_info *data)
2884 {
2885   tree flen, fpos;
2886   bool ret;
2887
2888   if (TREE_CODE (fld->element) == FIELD_DECL)
2889     {
2890       flen = fold_convert (bitsizetype, DECL_SIZE (fld->element));
2891       fpos = fold_convert (bitsizetype, DECL_FIELD_OFFSET (fld->element));
2892       fpos = size_binop (MULT_EXPR, fpos, bitsize_int (BITS_PER_UNIT));
2893       fpos = size_binop (PLUS_EXPR, fpos, DECL_FIELD_BIT_OFFSET (fld->element));
2894     }
2895   else if (TREE_CODE (fld->element) == BIT_FIELD_REF)
2896     {
2897       flen = fold_convert (bitsizetype, TREE_OPERAND (fld->element, 1));
2898       fpos = fold_convert (bitsizetype, TREE_OPERAND (fld->element, 2));
2899     }
2900   else
2901     gcc_unreachable ();
2902
2903   gcc_assert (host_integerp (blen, 1)
2904               && host_integerp (bpos, 1)
2905               && host_integerp (flen, 1)
2906               && host_integerp (fpos, 1));
2907
2908   ret = ((!tree_int_cst_lt (fpos, bpos)
2909           && tree_int_cst_lt (size_binop (MINUS_EXPR, fpos, bpos),
2910                               blen))
2911          || (!tree_int_cst_lt (bpos, fpos)
2912              && tree_int_cst_lt (size_binop (MINUS_EXPR, bpos, fpos),
2913                                  flen)));
2914
2915   if (!ret)
2916     return ret;
2917
2918   if (data)
2919     {
2920       tree bend, fend;
2921
2922       data->field_len = flen;
2923       data->field_pos = fpos;
2924
2925       fend = size_binop (PLUS_EXPR, fpos, flen);
2926       bend = size_binop (PLUS_EXPR, bpos, blen);
2927
2928       if (tree_int_cst_lt (bend, fend))
2929         data->overlap_len = size_binop (MINUS_EXPR, bend, fpos);
2930       else
2931         data->overlap_len = NULL;
2932
2933       if (tree_int_cst_lt (fpos, bpos))
2934         {
2935           data->overlap_pos = size_binop (MINUS_EXPR, bpos, fpos);
2936           data->overlap_len = size_binop (MINUS_EXPR,
2937                                           data->overlap_len
2938                                           ? data->overlap_len
2939                                           : data->field_len,
2940                                           data->overlap_pos);
2941         }
2942       else
2943         data->overlap_pos = NULL;
2944     }
2945
2946   return ret;
2947 }
2948
2949 /* Add to LISTP a sequence of statements that copies BLEN bits between
2950    VAR and the scalarized elements of ELT, starting a bit VPOS of VAR
2951    and at bit BPOS of ELT.  The direction of the copy is given by
2952    TO_VAR.  */
2953
2954 static void
2955 sra_explode_bitfield_assignment (tree var, tree vpos, bool to_var,
2956                                  tree *listp, tree blen, tree bpos,
2957                                  struct sra_elt *elt)
2958 {
2959   struct sra_elt *fld;
2960   struct bitfield_overlap_info flp;
2961
2962   FOR_EACH_ACTUAL_CHILD (fld, elt)
2963     {
2964       tree flen, fpos;
2965
2966       if (!bitfield_overlaps_p (blen, bpos, fld, &flp))
2967         continue;
2968
2969       flen = flp.overlap_len ? flp.overlap_len : flp.field_len;
2970       fpos = flp.overlap_pos ? flp.overlap_pos : bitsize_int (0);
2971
2972       if (fld->replacement)
2973         {
2974           tree infld, invar, st;
2975
2976           infld = fld->replacement;
2977
2978           if (TREE_CODE (infld) == BIT_FIELD_REF)
2979             {
2980               fpos = size_binop (PLUS_EXPR, fpos, TREE_OPERAND (infld, 2));
2981               infld = TREE_OPERAND (infld, 0);
2982             }
2983           else if (BITS_BIG_ENDIAN && DECL_P (fld->element)
2984                    && !tree_int_cst_equal (TYPE_SIZE (TREE_TYPE (infld)),
2985                                            DECL_SIZE (fld->element)))
2986             {
2987               fpos = size_binop (PLUS_EXPR, fpos,
2988                                  TYPE_SIZE (TREE_TYPE (infld)));
2989               fpos = size_binop (MINUS_EXPR, fpos,
2990                                  DECL_SIZE (fld->element));
2991             }
2992
2993           infld = fold_build3 (BIT_FIELD_REF,
2994                                lang_hooks.types.type_for_size
2995                                (TREE_INT_CST_LOW (flen), 1),
2996                                infld, flen, fpos);
2997           BIT_FIELD_REF_UNSIGNED (infld) = 1;
2998
2999           invar = size_binop (MINUS_EXPR, flp.field_pos, bpos);
3000           if (flp.overlap_pos)
3001             invar = size_binop (PLUS_EXPR, invar, flp.overlap_pos);
3002           invar = size_binop (PLUS_EXPR, invar, vpos);
3003
3004           invar = fold_build3 (BIT_FIELD_REF, TREE_TYPE (infld),
3005                                var, flen, invar);
3006           BIT_FIELD_REF_UNSIGNED (invar) = 1;
3007
3008           if (to_var)
3009             st = sra_build_bf_assignment (invar, infld);
3010           else
3011             st = sra_build_bf_assignment (infld, invar);
3012
3013           append_to_statement_list (st, listp);
3014         }
3015       else
3016         {
3017           tree sub = size_binop (MINUS_EXPR, flp.field_pos, bpos);
3018           sub = size_binop (PLUS_EXPR, vpos, sub);
3019           if (flp.overlap_pos)
3020             sub = size_binop (PLUS_EXPR, sub, flp.overlap_pos);
3021
3022           sra_explode_bitfield_assignment (var, sub, to_var, listp,
3023                                            flen, fpos, fld);
3024         }
3025     }
3026 }
3027
3028 /* Add to LISTBEFOREP statements that copy scalarized members of ELT
3029    that overlap with BIT_FIELD_REF<(ELT->element), BLEN, BPOS> back
3030    into the full variable, and to LISTAFTERP, if non-NULL, statements
3031    that copy the (presumably modified) overlapping portions of the
3032    full variable back to the scalarized variables.  */
3033
3034 static void
3035 sra_sync_for_bitfield_assignment (tree *listbeforep, tree *listafterp,
3036                                   tree blen, tree bpos,
3037                                   struct sra_elt *elt)
3038 {
3039   struct sra_elt *fld;
3040   struct bitfield_overlap_info flp;
3041
3042   FOR_EACH_ACTUAL_CHILD (fld, elt)
3043     if (bitfield_overlaps_p (blen, bpos, fld, &flp))
3044       {
3045         if (fld->replacement || (!flp.overlap_len && !flp.overlap_pos))
3046           {
3047             generate_copy_inout (fld, false, generate_element_ref (fld),
3048                                  listbeforep);
3049             mark_no_warning (fld);
3050             if (listafterp)
3051               generate_copy_inout (fld, true, generate_element_ref (fld),
3052                                    listafterp);
3053           }
3054         else
3055           {
3056             tree flen = flp.overlap_len ? flp.overlap_len : flp.field_len;
3057             tree fpos = flp.overlap_pos ? flp.overlap_pos : bitsize_int (0);
3058
3059             sra_sync_for_bitfield_assignment (listbeforep, listafterp,
3060                                               flen, fpos, fld);
3061           }
3062       }
3063 }
3064
3065 /* Scalarize a USE.  To recap, this is either a simple reference to ELT,
3066    if elt is scalar, or some occurrence of ELT that requires a complete
3067    aggregate.  IS_OUTPUT is true if ELT is being modified.  */
3068
3069 static void
3070 scalarize_use (struct sra_elt *elt, tree *expr_p, block_stmt_iterator *bsi,
3071                bool is_output, bool use_all)
3072 {
3073   tree stmt = bsi_stmt (*bsi);
3074   tree bfexpr;
3075
3076   if (elt->replacement)
3077     {
3078       tree replacement = elt->replacement;
3079
3080       /* If we have a replacement, then updating the reference is as
3081          simple as modifying the existing statement in place.  */
3082       if (is_output
3083           && TREE_CODE (elt->replacement) == BIT_FIELD_REF
3084           && is_gimple_reg (TREE_OPERAND (elt->replacement, 0))
3085           && TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
3086           && &GIMPLE_STMT_OPERAND (stmt, 0) == expr_p)
3087         {
3088           tree newstmt = sra_build_elt_assignment
3089             (elt, GIMPLE_STMT_OPERAND (stmt, 1));
3090           if (TREE_CODE (newstmt) != STATEMENT_LIST)
3091             {
3092               tree list = NULL;
3093               append_to_statement_list (newstmt, &list);
3094               newstmt = list;
3095             }
3096           sra_replace (bsi, newstmt);
3097           return;
3098         }
3099       else if (!is_output
3100                && TREE_CODE (elt->replacement) == BIT_FIELD_REF
3101                && TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
3102                && &GIMPLE_STMT_OPERAND (stmt, 1) == expr_p)
3103         {
3104           tree tmp = make_rename_temp
3105             (TREE_TYPE (GIMPLE_STMT_OPERAND (stmt, 0)), "SR");
3106           tree newstmt = sra_build_assignment (tmp, REPLDUP (elt->replacement));
3107
3108           if (TREE_CODE (newstmt) != STATEMENT_LIST)
3109             {
3110               tree list = NULL;
3111               append_to_statement_list (newstmt, &list);
3112               newstmt = list;
3113             }
3114           sra_insert_before (bsi, newstmt);
3115           replacement = tmp;
3116         }
3117       if (is_output)
3118           mark_all_v_defs (stmt);
3119       *expr_p = REPLDUP (replacement);
3120       update_stmt (stmt);
3121     }
3122   else if (use_all && is_output
3123            && TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
3124            && TREE_CODE (bfexpr
3125                          = GIMPLE_STMT_OPERAND (stmt, 0)) == BIT_FIELD_REF
3126            && &TREE_OPERAND (bfexpr, 0) == expr_p
3127            && INTEGRAL_TYPE_P (TREE_TYPE (bfexpr))
3128            && TREE_CODE (TREE_TYPE (*expr_p)) == RECORD_TYPE)
3129     {
3130       tree listbefore = NULL, listafter = NULL;
3131       tree blen = fold_convert (bitsizetype, TREE_OPERAND (bfexpr, 1));
3132       tree bpos = fold_convert (bitsizetype, TREE_OPERAND (bfexpr, 2));
3133       bool update = false;
3134
3135       if (!elt->use_block_copy)
3136         {
3137           tree type = TREE_TYPE (bfexpr);
3138           tree var = make_rename_temp (type, "SR"), tmp, st;
3139
3140           GIMPLE_STMT_OPERAND (stmt, 0) = var;
3141           update = true;
3142
3143           if (!TYPE_UNSIGNED (type))
3144             {
3145               type = unsigned_type_for (type);
3146               tmp = make_rename_temp (type, "SR");
3147               st = build_gimple_modify_stmt (tmp,
3148                                              fold_convert (type, var));
3149               append_to_statement_list (st, &listafter);
3150               var = tmp;
3151             }
3152
3153           sra_explode_bitfield_assignment
3154             (var, bitsize_int (0), false, &listafter, blen, bpos, elt);
3155         }
3156       else
3157         sra_sync_for_bitfield_assignment
3158           (&listbefore, &listafter, blen, bpos, elt);
3159
3160       if (listbefore)
3161         {
3162           mark_all_v_defs (listbefore);
3163           sra_insert_before (bsi, listbefore);
3164         }
3165       if (listafter)
3166         {
3167           mark_all_v_defs (listafter);
3168           sra_insert_after (bsi, listafter);
3169         }
3170
3171       if (update)
3172         update_stmt (stmt);
3173     }
3174   else if (use_all && !is_output
3175            && TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
3176            && TREE_CODE (bfexpr
3177                          = GIMPLE_STMT_OPERAND (stmt, 1)) == BIT_FIELD_REF
3178            && &TREE_OPERAND (GIMPLE_STMT_OPERAND (stmt, 1), 0) == expr_p
3179            && INTEGRAL_TYPE_P (TREE_TYPE (bfexpr))
3180            && TREE_CODE (TREE_TYPE (*expr_p)) == RECORD_TYPE)
3181     {
3182       tree list = NULL;
3183       tree blen = fold_convert (bitsizetype, TREE_OPERAND (bfexpr, 1));
3184       tree bpos = fold_convert (bitsizetype, TREE_OPERAND (bfexpr, 2));
3185       bool update = false;
3186
3187       if (!elt->use_block_copy)
3188         {
3189           tree type = TREE_TYPE (bfexpr);
3190           tree var;
3191
3192           if (!TYPE_UNSIGNED (type))
3193             type = unsigned_type_for (type);
3194
3195           var = make_rename_temp (type, "SR");
3196
3197           append_to_statement_list (build_gimple_modify_stmt
3198                                     (var, build_int_cst_wide (type, 0, 0)),
3199                                     &list);
3200
3201           sra_explode_bitfield_assignment
3202             (var, bitsize_int (0), true, &list, blen, bpos, elt);
3203
3204           GIMPLE_STMT_OPERAND (stmt, 1) = var;
3205           update = true;
3206         }
3207       else
3208         sra_sync_for_bitfield_assignment
3209           (&list, NULL, blen, bpos, elt);
3210
3211       if (list)
3212         {
3213           mark_all_v_defs (list);
3214           sra_insert_before (bsi, list);
3215         }
3216
3217       if (update)
3218         update_stmt (stmt);
3219     }
3220   else
3221     {
3222       tree list = NULL;
3223
3224       /* Otherwise we need some copies.  If ELT is being read, then we
3225          want to store all (modified) sub-elements back into the
3226          structure before the reference takes place.  If ELT is being
3227          written, then we want to load the changed values back into
3228          our shadow variables.  */
3229       /* ??? We don't check modified for reads, we just always write all of
3230          the values.  We should be able to record the SSA number of the VOP
3231          for which the values were last read.  If that number matches the
3232          SSA number of the VOP in the current statement, then we needn't
3233          emit an assignment.  This would also eliminate double writes when
3234          a structure is passed as more than one argument to a function call.
3235          This optimization would be most effective if sra_walk_function
3236          processed the blocks in dominator order.  */
3237
3238       generate_copy_inout (elt, is_output, generate_element_ref (elt), &list);
3239       if (list == NULL)
3240         return;
3241       mark_all_v_defs (list);
3242       if (is_output)
3243         sra_insert_after (bsi, list);
3244       else
3245         {
3246           sra_insert_before (bsi, list);
3247           if (use_all)
3248             mark_no_warning (elt);
3249         }
3250     }
3251 }
3252
3253 /* Scalarize a COPY.  To recap, this is an assignment statement between
3254    two scalarizable references, LHS_ELT and RHS_ELT.  */
3255
3256 static void
3257 scalarize_copy (struct sra_elt *lhs_elt, struct sra_elt *rhs_elt,
3258                 block_stmt_iterator *bsi)
3259 {
3260   tree list, stmt;
3261
3262   if (lhs_elt->replacement && rhs_elt->replacement)
3263     {
3264       /* If we have two scalar operands, modify the existing statement.  */
3265       stmt = bsi_stmt (*bsi);
3266
3267       /* See the commentary in sra_walk_function concerning
3268          RETURN_EXPR, and why we should never see one here.  */
3269       gcc_assert (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT);
3270
3271       GIMPLE_STMT_OPERAND (stmt, 0) = lhs_elt->replacement;
3272       GIMPLE_STMT_OPERAND (stmt, 1) = REPLDUP (rhs_elt->replacement);
3273       update_stmt (stmt);
3274     }
3275   else if (lhs_elt->use_block_copy || rhs_elt->use_block_copy)
3276     {
3277       /* If either side requires a block copy, then sync the RHS back
3278          to the original structure, leave the original assignment
3279          statement (which will perform the block copy), then load the
3280          LHS values out of its now-updated original structure.  */
3281       /* ??? Could perform a modified pair-wise element copy.  That
3282          would at least allow those elements that are instantiated in
3283          both structures to be optimized well.  */
3284
3285       list = NULL;
3286       generate_copy_inout (rhs_elt, false,
3287                            generate_element_ref (rhs_elt), &list);
3288       if (list)
3289         {
3290           mark_all_v_defs (list);
3291           sra_insert_before (bsi, list);
3292         }
3293
3294       list = NULL;
3295       generate_copy_inout (lhs_elt, true,
3296                            generate_element_ref (lhs_elt), &list);
3297       if (list)
3298         {
3299           mark_all_v_defs (list);
3300           sra_insert_after (bsi, list);
3301         }
3302     }
3303   else
3304     {
3305       /* Otherwise both sides must be fully instantiated.  In which
3306          case perform pair-wise element assignments and replace the
3307          original block copy statement.  */
3308
3309       stmt = bsi_stmt (*bsi);
3310       mark_all_v_defs (stmt);
3311
3312       list = NULL;
3313       generate_element_copy (lhs_elt, rhs_elt, &list);
3314       gcc_assert (list);
3315       mark_all_v_defs (list);
3316       sra_replace (bsi, list);
3317     }
3318 }
3319
3320 /* Scalarize an INIT.  To recap, this is an assignment to a scalarizable
3321    reference from some form of constructor: CONSTRUCTOR, COMPLEX_CST or
3322    COMPLEX_EXPR.  If RHS is NULL, it should be treated as an empty
3323    CONSTRUCTOR.  */
3324
3325 static void
3326 scalarize_init (struct sra_elt *lhs_elt, tree rhs, block_stmt_iterator *bsi)
3327 {
3328   bool result = true;
3329   tree list = NULL;
3330
3331   /* Generate initialization statements for all members extant in the RHS.  */
3332   if (rhs)
3333     {
3334       /* Unshare the expression just in case this is from a decl's initial.  */
3335       rhs = unshare_expr (rhs);
3336       result = generate_element_init (lhs_elt, rhs, &list);
3337     }
3338
3339   /* CONSTRUCTOR is defined such that any member not mentioned is assigned
3340      a zero value.  Initialize the rest of the instantiated elements.  */
3341   generate_element_zero (lhs_elt, &list);
3342
3343   if (!result)
3344     {
3345       /* If we failed to convert the entire initializer, then we must
3346          leave the structure assignment in place and must load values
3347          from the structure into the slots for which we did not find
3348          constants.  The easiest way to do this is to generate a complete
3349          copy-out, and then follow that with the constant assignments
3350          that we were able to build.  DCE will clean things up.  */
3351       tree list0 = NULL;
3352       generate_copy_inout (lhs_elt, true, generate_element_ref (lhs_elt),
3353                            &list0);
3354       append_to_statement_list (list, &list0);
3355       list = list0;
3356     }
3357
3358   if (lhs_elt->use_block_copy || !result)
3359     {
3360       /* Since LHS is not fully instantiated, we must leave the structure
3361          assignment in place.  Treating this case differently from a USE
3362          exposes constants to later optimizations.  */
3363       if (list)
3364         {
3365           mark_all_v_defs (list);
3366           sra_insert_after (bsi, list);
3367         }
3368     }
3369   else
3370     {
3371       /* The LHS is fully instantiated.  The list of initializations
3372          replaces the original structure assignment.  */
3373       gcc_assert (list);
3374       mark_all_v_defs (bsi_stmt (*bsi));
3375       mark_all_v_defs (list);
3376       sra_replace (bsi, list);
3377     }
3378 }
3379
3380 /* A subroutine of scalarize_ldst called via walk_tree.  Set TREE_NO_TRAP
3381    on all INDIRECT_REFs.  */
3382
3383 static tree
3384 mark_notrap (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED)
3385 {
3386   tree t = *tp;
3387
3388   if (TREE_CODE (t) == INDIRECT_REF)
3389     {
3390       TREE_THIS_NOTRAP (t) = 1;
3391       *walk_subtrees = 0;
3392     }
3393   else if (IS_TYPE_OR_DECL_P (t))
3394     *walk_subtrees = 0;
3395
3396   return NULL;
3397 }
3398
3399 /* Scalarize a LDST.  To recap, this is an assignment between one scalarizable
3400    reference ELT and one non-scalarizable reference OTHER.  IS_OUTPUT is true
3401    if ELT is on the left-hand side.  */
3402
3403 static void
3404 scalarize_ldst (struct sra_elt *elt, tree other,
3405                 block_stmt_iterator *bsi, bool is_output)
3406 {
3407   /* Shouldn't have gotten called for a scalar.  */
3408   gcc_assert (!elt->replacement);
3409
3410   if (elt->use_block_copy)
3411     {
3412       /* Since ELT is not fully instantiated, we have to leave the
3413          block copy in place.  Treat this as a USE.  */
3414       scalarize_use (elt, NULL, bsi, is_output, false);
3415     }
3416   else
3417     {
3418       /* The interesting case is when ELT is fully instantiated.  In this
3419          case we can have each element stored/loaded directly to/from the
3420          corresponding slot in OTHER.  This avoids a block copy.  */
3421
3422       tree list = NULL, stmt = bsi_stmt (*bsi);
3423
3424       mark_all_v_defs (stmt);
3425       generate_copy_inout (elt, is_output, other, &list);
3426       gcc_assert (list);
3427       mark_all_v_defs (list);
3428
3429       /* Preserve EH semantics.  */
3430       if (stmt_ends_bb_p (stmt))
3431         {
3432           tree_stmt_iterator tsi;
3433           tree first, blist = NULL;
3434           bool thr = (bsi->bb->flags & EDGE_COMPLEX) != 0;
3435
3436           /* If the last statement of this BB created an EH edge
3437              before scalarization, we have to locate the first
3438              statement that can throw in the new statement list and
3439              use that as the last statement of this BB, such that EH
3440              semantics is preserved.  All statements up to this one
3441              are added to the same BB.  All other statements in the
3442              list will be added to normal outgoing edges of the same
3443              BB.  If they access any memory, it's the same memory, so
3444              we can assume they won't throw.  */
3445           tsi = tsi_start (list);
3446           for (first = tsi_stmt (tsi);
3447                thr && !tsi_end_p (tsi) && !tree_could_throw_p (first);
3448                first = tsi_stmt (tsi))
3449             {
3450               tsi_delink (&tsi);
3451               append_to_statement_list (first, &blist);
3452             }
3453
3454           /* Extract the first remaining statement from LIST, this is
3455              the EH statement if there is one.  */
3456           tsi_delink (&tsi);
3457
3458           if (blist)
3459             sra_insert_before (bsi, blist);
3460
3461           /* Replace the old statement with this new representative.  */
3462           bsi_replace (bsi, first, true);
3463
3464           if (!tsi_end_p (tsi))
3465             {
3466               /* If any reference would trap, then they all would.  And more
3467                  to the point, the first would.  Therefore none of the rest
3468                  will trap since the first didn't.  Indicate this by
3469                  iterating over the remaining statements and set
3470                  TREE_THIS_NOTRAP in all INDIRECT_REFs.  */
3471               do
3472                 {
3473                   walk_tree (tsi_stmt_ptr (tsi), mark_notrap, NULL, NULL);
3474                   tsi_next (&tsi);
3475                 }
3476               while (!tsi_end_p (tsi));
3477
3478               insert_edge_copies (list, bsi->bb);
3479             }
3480         }
3481       else
3482         sra_replace (bsi, list);
3483     }
3484 }
3485
3486 /* Generate initializations for all scalarizable parameters.  */
3487
3488 static void
3489 scalarize_parms (void)
3490 {
3491   tree list = NULL;
3492   unsigned i;
3493   bitmap_iterator bi;
3494
3495   EXECUTE_IF_SET_IN_BITMAP (needs_copy_in, 0, i, bi)
3496     {
3497       tree var = referenced_var (i);
3498       struct sra_elt *elt = lookup_element (NULL, var, NULL, NO_INSERT);
3499       generate_copy_inout (elt, true, var, &list);
3500     }
3501
3502   if (list)
3503     {
3504       insert_edge_copies (list, ENTRY_BLOCK_PTR);
3505       mark_all_v_defs (list);
3506     }
3507 }
3508
3509 /* Entry point to phase 4.  Update the function to match replacements.  */
3510
3511 static void
3512 scalarize_function (void)
3513 {
3514   static const struct sra_walk_fns fns = {
3515     scalarize_use, scalarize_copy, scalarize_init, scalarize_ldst, false
3516   };
3517
3518   sra_walk_function (&fns);
3519   scalarize_parms ();
3520   bsi_commit_edge_inserts ();
3521 }
3522
3523 \f
3524 /* Debug helper function.  Print ELT in a nice human-readable format.  */
3525
3526 static void
3527 dump_sra_elt_name (FILE *f, struct sra_elt *elt)
3528 {
3529   if (elt->parent && TREE_CODE (elt->parent->type) == COMPLEX_TYPE)
3530     {
3531       fputs (elt->element == integer_zero_node ? "__real__ " : "__imag__ ", f);
3532       dump_sra_elt_name (f, elt->parent);
3533     }
3534   else
3535     {
3536       if (elt->parent)
3537         dump_sra_elt_name (f, elt->parent);
3538       if (DECL_P (elt->element))
3539         {
3540           if (TREE_CODE (elt->element) == FIELD_DECL)
3541             fputc ('.', f);
3542           print_generic_expr (f, elt->element, dump_flags);
3543         }
3544       else if (TREE_CODE (elt->element) == BIT_FIELD_REF)
3545         fprintf (f, "$B" HOST_WIDE_INT_PRINT_DEC "F" HOST_WIDE_INT_PRINT_DEC,
3546                  tree_low_cst (TREE_OPERAND (elt->element, 2), 1),
3547                  tree_low_cst (TREE_OPERAND (elt->element, 1), 1));
3548       else if (TREE_CODE (elt->element) == RANGE_EXPR)
3549         fprintf (f, "["HOST_WIDE_INT_PRINT_DEC".."HOST_WIDE_INT_PRINT_DEC"]",
3550                  TREE_INT_CST_LOW (TREE_OPERAND (elt->element, 0)),
3551                  TREE_INT_CST_LOW (TREE_OPERAND (elt->element, 1)));
3552       else
3553         fprintf (f, "[" HOST_WIDE_INT_PRINT_DEC "]",
3554                  TREE_INT_CST_LOW (elt->element));
3555     }