OSDN Git Service

PR tree-opt/20127
[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 Free Software Foundation, Inc.
5    Contributed by Diego Novillo <dnovillo@redhat.com>
6
7 This file is part of GCC.
8
9 GCC is free software; you can redistribute it and/or modify it
10 under the terms of the GNU General Public License as published by the
11 Free Software Foundation; either version 2, or (at your option) any
12 later version.
13
14 GCC is distributed in the hope that it will be useful, but WITHOUT
15 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
17 for more details.
18
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING.  If not, write to the Free
21 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
22 02111-1307, USA.  */
23
24 #include "config.h"
25 #include "system.h"
26 #include "coretypes.h"
27 #include "tm.h"
28 #include "errors.h"
29 #include "ggc.h"
30 #include "tree.h"
31
32 /* These RTL headers are needed for basic-block.h.  */
33 #include "rtl.h"
34 #include "tm_p.h"
35 #include "hard-reg-set.h"
36 #include "basic-block.h"
37 #include "diagnostic.h"
38 #include "langhooks.h"
39 #include "tree-inline.h"
40 #include "tree-flow.h"
41 #include "tree-gimple.h"
42 #include "tree-dump.h"
43 #include "tree-pass.h"
44 #include "timevar.h"
45 #include "flags.h"
46 #include "bitmap.h"
47 #include "obstack.h"
48 #include "target.h"
49 /* expr.h is needed for MOVE_RATIO.  */
50 #include "expr.h"
51 #include "params.h"
52
53
54 /* This object of this pass is to replace a non-addressable aggregate with a
55    set of independent variables.  Most of the time, all of these variables
56    will be scalars.  But a secondary objective is to break up larger
57    aggregates into smaller aggregates.  In the process we may find that some
58    bits of the larger aggregate can be deleted as unreferenced.
59
60    This substitution is done globally.  More localized substitutions would
61    be the purvey of a load-store motion pass.
62
63    The optimization proceeds in phases:
64
65      (1) Identify variables that have types that are candidates for
66          decomposition.
67
68      (2) Scan the function looking for the ways these variables are used.
69          In particular we're interested in the number of times a variable
70          (or member) is needed as a complete unit, and the number of times
71          a variable (or member) is copied.
72
73      (3) Based on the usage profile, instantiate substitution variables.
74
75      (4) Scan the function making replacements.
76 */
77
78
79 /* The set of aggregate variables that are candidates for scalarization.  */
80 static bitmap sra_candidates;
81
82 /* Set of scalarizable PARM_DECLs that need copy-in operations at the
83    beginning of the function.  */
84 static bitmap needs_copy_in;
85
86 /* Sets of bit pairs that cache type decomposition and instantiation.  */
87 static bitmap sra_type_decomp_cache;
88 static bitmap sra_type_inst_cache;
89
90 /* One of these structures is created for each candidate aggregate
91    and each (accessed) member of such an aggregate.  */
92 struct sra_elt
93 {
94   /* A tree of the elements.  Used when we want to traverse everything.  */
95   struct sra_elt *parent;
96   struct sra_elt *children;
97   struct sra_elt *sibling;
98
99   /* If this element is a root, then this is the VAR_DECL.  If this is
100      a sub-element, this is some token used to identify the reference.
101      In the case of COMPONENT_REF, this is the FIELD_DECL.  In the case
102      of an ARRAY_REF, this is the (constant) index.  In the case of a
103      complex number, this is a zero or one.  */
104   tree element;
105
106   /* The type of the element.  */
107   tree type;
108
109   /* A VAR_DECL, for any sub-element we've decided to replace.  */
110   tree replacement;
111
112   /* The number of times the element is referenced as a whole.  I.e.
113      given "a.b.c", this would be incremented for C, but not for A or B.  */
114   unsigned int n_uses;
115
116   /* The number of times the element is copied to or from another
117      scalarizable element.  */
118   unsigned int n_copies;
119
120   /* True if TYPE is scalar.  */
121   bool is_scalar;
122
123   /* True if we saw something about this element that prevents scalarization,
124      such as non-constant indexing.  */
125   bool cannot_scalarize;
126
127   /* True if we've decided that structure-to-structure assignment
128      should happen via memcpy and not per-element.  */
129   bool use_block_copy;
130
131   /* A flag for use with/after random access traversals.  */
132   bool visited;
133 };
134
135 /* Random access to the child of a parent is performed by hashing.
136    This prevents quadratic behavior, and allows SRA to function
137    reasonably on larger records.  */
138 static htab_t sra_map;
139
140 /* All structures are allocated out of the following obstack.  */
141 static struct obstack sra_obstack;
142
143 /* Debugging functions.  */
144 static void dump_sra_elt_name (FILE *, struct sra_elt *);
145 extern void debug_sra_elt_name (struct sra_elt *);
146
147 /* Forward declarations.  */
148 static tree generate_element_ref (struct sra_elt *);
149 \f
150 /* Return true if DECL is an SRA candidate.  */
151
152 static bool
153 is_sra_candidate_decl (tree decl)
154 {
155   return DECL_P (decl) && bitmap_bit_p (sra_candidates, var_ann (decl)->uid);
156 }
157
158 /* Return true if TYPE is a scalar type.  */
159
160 static bool
161 is_sra_scalar_type (tree type)
162 {
163   enum tree_code code = TREE_CODE (type);
164   return (code == INTEGER_TYPE || code == REAL_TYPE || code == VECTOR_TYPE
165           || code == ENUMERAL_TYPE || code == BOOLEAN_TYPE
166           || code == CHAR_TYPE || code == POINTER_TYPE || code == OFFSET_TYPE
167           || code == REFERENCE_TYPE);
168 }
169
170 /* Return true if TYPE can be decomposed into a set of independent variables.
171
172    Note that this doesn't imply that all elements of TYPE can be
173    instantiated, just that if we decide to break up the type into
174    separate pieces that it can be done.  */
175
176 static bool
177 type_can_be_decomposed_p (tree type)
178 {
179   unsigned int cache = TYPE_UID (TYPE_MAIN_VARIANT (type)) * 2;
180   tree t;
181
182   /* Avoid searching the same type twice.  */
183   if (bitmap_bit_p (sra_type_decomp_cache, cache+0))
184     return true;
185   if (bitmap_bit_p (sra_type_decomp_cache, cache+1))
186     return false;
187
188   /* The type must have a definite nonzero size.  */
189   if (TYPE_SIZE (type) == NULL || TREE_CODE (TYPE_SIZE (type)) != INTEGER_CST
190       || integer_zerop (TYPE_SIZE (type)))
191     goto fail;
192
193   /* The type must be a non-union aggregate.  */
194   switch (TREE_CODE (type))
195     {
196     case RECORD_TYPE:
197       {
198         bool saw_one_field = false;
199
200         for (t = TYPE_FIELDS (type); t ; t = TREE_CHAIN (t))
201           if (TREE_CODE (t) == FIELD_DECL)
202             {
203               /* Reject incorrectly represented bit fields.  */
204               if (DECL_BIT_FIELD (t)
205                   && (tree_low_cst (DECL_SIZE (t), 1)
206                       != TYPE_PRECISION (TREE_TYPE (t))))
207                 goto fail;
208
209               saw_one_field = true;
210             }
211
212         /* Record types must have at least one field.  */
213         if (!saw_one_field)
214           goto fail;
215       }
216       break;
217
218     case ARRAY_TYPE:
219       /* Array types must have a fixed lower and upper bound.  */
220       t = TYPE_DOMAIN (type);
221       if (t == NULL)
222         goto fail;
223       if (TYPE_MIN_VALUE (t) == NULL || !TREE_CONSTANT (TYPE_MIN_VALUE (t)))
224         goto fail;
225       if (TYPE_MAX_VALUE (t) == NULL || !TREE_CONSTANT (TYPE_MAX_VALUE (t)))
226         goto fail;
227       break;
228
229     case COMPLEX_TYPE:
230       break;
231
232     default:
233       goto fail;
234     }
235
236   bitmap_set_bit (sra_type_decomp_cache, cache+0);
237   return true;
238
239  fail:
240   bitmap_set_bit (sra_type_decomp_cache, cache+1);
241   return false;
242 }
243
244 /* Return true if DECL can be decomposed into a set of independent
245    (though not necessarily scalar) variables.  */
246
247 static bool
248 decl_can_be_decomposed_p (tree var)
249 {
250   /* Early out for scalars.  */
251   if (is_sra_scalar_type (TREE_TYPE (var)))
252     return false;
253
254   /* The variable must not be aliased.  */
255   if (!is_gimple_non_addressable (var))
256     {
257       if (dump_file && (dump_flags & TDF_DETAILS))
258         {
259           fprintf (dump_file, "Cannot scalarize variable ");
260           print_generic_expr (dump_file, var, dump_flags);
261           fprintf (dump_file, " because it must live in memory\n");
262         }
263       return false;
264     }
265
266   /* The variable must not be volatile.  */
267   if (TREE_THIS_VOLATILE (var))
268     {
269       if (dump_file && (dump_flags & TDF_DETAILS))
270         {
271           fprintf (dump_file, "Cannot scalarize variable ");
272           print_generic_expr (dump_file, var, dump_flags);
273           fprintf (dump_file, " because it is declared volatile\n");
274         }
275       return false;
276     }
277
278   /* We must be able to decompose the variable's type.  */
279   if (!type_can_be_decomposed_p (TREE_TYPE (var)))
280     {
281       if (dump_file && (dump_flags & TDF_DETAILS))
282         {
283           fprintf (dump_file, "Cannot scalarize variable ");
284           print_generic_expr (dump_file, var, dump_flags);
285           fprintf (dump_file, " because its type cannot be decomposed\n");
286         }
287       return false;
288     }
289
290   return true;
291 }
292
293 /* Return true if TYPE can be *completely* decomposed into scalars.  */
294
295 static bool
296 type_can_instantiate_all_elements (tree type)
297 {
298   if (is_sra_scalar_type (type))
299     return true;
300   if (!type_can_be_decomposed_p (type))
301     return false;
302
303   switch (TREE_CODE (type))
304     {
305     case RECORD_TYPE:
306       {
307         unsigned int cache = TYPE_UID (TYPE_MAIN_VARIANT (type)) * 2;
308         tree f;
309
310         if (bitmap_bit_p (sra_type_inst_cache, cache+0))
311           return true;
312         if (bitmap_bit_p (sra_type_inst_cache, cache+1))
313           return false;
314
315         for (f = TYPE_FIELDS (type); f ; f = TREE_CHAIN (f))
316           if (TREE_CODE (f) == FIELD_DECL)
317             {
318               if (!type_can_instantiate_all_elements (TREE_TYPE (f)))
319                 {
320                   bitmap_set_bit (sra_type_inst_cache, cache+1);
321                   return false;
322                 }
323             }
324
325         bitmap_set_bit (sra_type_inst_cache, cache+0);
326         return true;
327       }
328
329     case ARRAY_TYPE:
330       return type_can_instantiate_all_elements (TREE_TYPE (type));
331
332     case COMPLEX_TYPE:
333       return true;
334
335     default:
336       gcc_unreachable ();
337     }
338 }
339
340 /* Test whether ELT or some sub-element cannot be scalarized.  */
341
342 static bool
343 can_completely_scalarize_p (struct sra_elt *elt)
344 {
345   struct sra_elt *c;
346
347   if (elt->cannot_scalarize)
348     return false;
349
350   for (c = elt->children; c ; c = c->sibling)
351     if (!can_completely_scalarize_p (c))
352       return false;
353
354   return true;
355 }
356
357 \f
358 /* A simplified tree hashing algorithm that only handles the types of
359    trees we expect to find in sra_elt->element.  */
360
361 static hashval_t
362 sra_hash_tree (tree t)
363 {
364   hashval_t h;
365
366   switch (TREE_CODE (t))
367     {
368     case VAR_DECL:
369     case PARM_DECL:
370     case RESULT_DECL:
371       h = DECL_UID (t);
372       break;
373
374     case INTEGER_CST:
375       h = TREE_INT_CST_LOW (t) ^ TREE_INT_CST_HIGH (t);
376       break;
377
378     case FIELD_DECL:
379       /* We can have types that are compatible, but have different member
380          lists, so we can't hash fields by ID.  Use offsets instead.  */
381       h = iterative_hash_expr (DECL_FIELD_OFFSET (t), 0);
382       h = iterative_hash_expr (DECL_FIELD_BIT_OFFSET (t), h);
383       break;
384
385     default:
386       gcc_unreachable ();
387     }
388
389   return h;
390 }
391
392 /* Hash function for type SRA_PAIR.  */
393
394 static hashval_t
395 sra_elt_hash (const void *x)
396 {
397   const struct sra_elt *e = x;
398   const struct sra_elt *p;
399   hashval_t h;
400
401   h = sra_hash_tree (e->element);
402
403   /* Take into account everything back up the chain.  Given that chain
404      lengths are rarely very long, this should be acceptable.  If we
405      truly identify this as a performance problem, it should work to
406      hash the pointer value "e->parent".  */
407   for (p = e->parent; p ; p = p->parent)
408     h = (h * 65521) ^ sra_hash_tree (p->element);
409
410   return h;
411 }
412
413 /* Equality function for type SRA_PAIR.  */
414
415 static int
416 sra_elt_eq (const void *x, const void *y)
417 {
418   const struct sra_elt *a = x;
419   const struct sra_elt *b = y;
420   tree ae, be;
421
422   if (a->parent != b->parent)
423     return false;
424
425   ae = a->element;
426   be = b->element;
427
428   if (ae == be)
429     return true;
430   if (TREE_CODE (ae) != TREE_CODE (be))
431     return false;
432
433   switch (TREE_CODE (ae))
434     {
435     case VAR_DECL:
436     case PARM_DECL:
437     case RESULT_DECL:
438       /* These are all pointer unique.  */
439       return false;
440
441     case INTEGER_CST:
442       /* Integers are not pointer unique, so compare their values.  */
443       return tree_int_cst_equal (ae, be);
444
445     case FIELD_DECL:
446       /* Fields are unique within a record, but not between
447          compatible records.  */
448       if (DECL_FIELD_CONTEXT (ae) == DECL_FIELD_CONTEXT (be))
449         return false;
450       return fields_compatible_p (ae, be);
451
452     default:
453       gcc_unreachable ();
454     }
455 }
456
457 /* Create or return the SRA_ELT structure for CHILD in PARENT.  PARENT
458    may be null, in which case CHILD must be a DECL.  */
459
460 static struct sra_elt *
461 lookup_element (struct sra_elt *parent, tree child, tree type,
462                 enum insert_option insert)
463 {
464   struct sra_elt dummy;
465   struct sra_elt **slot;
466   struct sra_elt *elt;
467
468   dummy.parent = parent;
469   dummy.element = child;
470
471   slot = (struct sra_elt **) htab_find_slot (sra_map, &dummy, insert);
472   if (!slot && insert == NO_INSERT)
473     return NULL;
474
475   elt = *slot;
476   if (!elt && insert == INSERT)
477     {
478       *slot = elt = obstack_alloc (&sra_obstack, sizeof (*elt));
479       memset (elt, 0, sizeof (*elt));
480
481       elt->parent = parent;
482       elt->element = child;
483       elt->type = type;
484       elt->is_scalar = is_sra_scalar_type (type);
485
486       if (parent)
487         {
488           elt->sibling = parent->children;
489           parent->children = elt;
490         }
491
492       /* If this is a parameter, then if we want to scalarize, we have
493          one copy from the true function parameter.  Count it now.  */
494       if (TREE_CODE (child) == PARM_DECL)
495         {
496           elt->n_copies = 1;
497           bitmap_set_bit (needs_copy_in, var_ann (child)->uid);
498         }
499     }
500
501   return elt;
502 }
503
504 /* Return true if the ARRAY_REF in EXPR is a constant, in bounds access.  */
505
506 static bool
507 is_valid_const_index (tree expr)
508 {
509   tree dom, t, index = TREE_OPERAND (expr, 1);
510
511   if (TREE_CODE (index) != INTEGER_CST)
512     return false;
513
514   /* Watch out for stupid user tricks, indexing outside the array.
515
516      Careful, we're not called only on scalarizable types, so do not
517      assume constant array bounds.  We needn't do anything with such
518      cases, since they'll be referring to objects that we should have
519      already rejected for scalarization, so returning false is fine.  */
520
521   dom = TYPE_DOMAIN (TREE_TYPE (TREE_OPERAND (expr, 0)));
522   if (dom == NULL)
523     return false;
524
525   t = TYPE_MIN_VALUE (dom);
526   if (!t || TREE_CODE (t) != INTEGER_CST)
527     return false;
528   if (tree_int_cst_lt (index, t))
529     return false;
530
531   t = TYPE_MAX_VALUE (dom);
532   if (!t || TREE_CODE (t) != INTEGER_CST)
533     return false;
534   if (tree_int_cst_lt (t, index))
535     return false;
536
537   return true;
538 }
539
540 /* Create or return the SRA_ELT structure for EXPR if the expression
541    refers to a scalarizable variable.  */
542
543 static struct sra_elt *
544 maybe_lookup_element_for_expr (tree expr)
545 {
546   struct sra_elt *elt;
547   tree child;
548
549   switch (TREE_CODE (expr))
550     {
551     case VAR_DECL:
552     case PARM_DECL:
553     case RESULT_DECL:
554       if (is_sra_candidate_decl (expr))
555         return lookup_element (NULL, expr, TREE_TYPE (expr), INSERT);
556       return NULL;
557
558     case ARRAY_REF:
559       /* We can't scalarize variable array indicies.  */
560       if (is_valid_const_index (expr))
561         child = TREE_OPERAND (expr, 1);
562       else
563         return NULL;
564       break;
565
566     case COMPONENT_REF:
567       /* Don't look through unions.  */
568       if (TREE_CODE (TREE_TYPE (TREE_OPERAND (expr, 0))) != RECORD_TYPE)
569         return NULL;
570       child = TREE_OPERAND (expr, 1);
571       break;
572
573     case REALPART_EXPR:
574       child = integer_zero_node;
575       break;
576     case IMAGPART_EXPR:
577       child = integer_one_node;
578       break;
579
580     default:
581       return NULL;
582     }
583
584   elt = maybe_lookup_element_for_expr (TREE_OPERAND (expr, 0));
585   if (elt)
586     return lookup_element (elt, child, TREE_TYPE (expr), INSERT);
587   return NULL;
588 }
589
590 \f
591 /* Functions to walk just enough of the tree to see all scalarizable
592    references, and categorize them.  */
593
594 /* A set of callbacks for phases 2 and 4.  They'll be invoked for the
595    various kinds of references seen.  In all cases, *BSI is an iterator
596    pointing to the statement being processed.  */
597 struct sra_walk_fns
598 {
599   /* Invoked when ELT is required as a unit.  Note that ELT might refer to
600      a leaf node, in which case this is a simple scalar reference.  *EXPR_P
601      points to the location of the expression.  IS_OUTPUT is true if this
602      is a left-hand-side reference.  */
603   void (*use) (struct sra_elt *elt, tree *expr_p,
604                block_stmt_iterator *bsi, bool is_output);
605
606   /* Invoked when we have a copy between two scalarizable references.  */
607   void (*copy) (struct sra_elt *lhs_elt, struct sra_elt *rhs_elt,
608                 block_stmt_iterator *bsi);
609
610   /* Invoked when ELT is initialized from a constant.  VALUE may be NULL,
611      in which case it should be treated as an empty CONSTRUCTOR.  */
612   void (*init) (struct sra_elt *elt, tree value, block_stmt_iterator *bsi);
613
614   /* Invoked when we have a copy between one scalarizable reference ELT
615      and one non-scalarizable reference OTHER.  IS_OUTPUT is true if ELT
616      is on the left-hand side.  */
617   void (*ldst) (struct sra_elt *elt, tree other,
618                 block_stmt_iterator *bsi, bool is_output);
619
620   /* True during phase 2, false during phase 4.  */
621   /* ??? This is a hack.  */
622   bool initial_scan;
623 };
624
625 #ifdef ENABLE_CHECKING
626 /* Invoked via walk_tree, if *TP contains a candidate decl, return it.  */
627
628 static tree
629 sra_find_candidate_decl (tree *tp, int *walk_subtrees,
630                          void *data ATTRIBUTE_UNUSED)
631 {
632   tree t = *tp;
633   enum tree_code code = TREE_CODE (t);
634
635   if (code == VAR_DECL || code == PARM_DECL || code == RESULT_DECL)
636     {
637       *walk_subtrees = 0;
638       if (is_sra_candidate_decl (t))
639         return t;
640     }
641   else if (TYPE_P (t))
642     *walk_subtrees = 0;
643
644   return NULL;
645 }
646 #endif
647
648 /* Walk most expressions looking for a scalarizable aggregate.
649    If we find one, invoke FNS->USE.  */
650
651 static void
652 sra_walk_expr (tree *expr_p, block_stmt_iterator *bsi, bool is_output,
653                const struct sra_walk_fns *fns)
654 {
655   tree expr = *expr_p;
656   tree inner = expr;
657   bool disable_scalarization = false;
658
659   /* We're looking to collect a reference expression between EXPR and INNER,
660      such that INNER is a scalarizable decl and all other nodes through EXPR
661      are references that we can scalarize.  If we come across something that
662      we can't scalarize, we reset EXPR.  This has the effect of making it
663      appear that we're referring to the larger expression as a whole.  */
664
665   while (1)
666     switch (TREE_CODE (inner))
667       {
668       case VAR_DECL:
669       case PARM_DECL:
670       case RESULT_DECL:
671         /* If there is a scalarizable decl at the bottom, then process it.  */
672         if (is_sra_candidate_decl (inner))
673           {
674             struct sra_elt *elt = maybe_lookup_element_for_expr (expr);
675             if (disable_scalarization)
676               elt->cannot_scalarize = true;
677             else
678               fns->use (elt, expr_p, bsi, is_output);
679           }
680         return;
681
682       case ARRAY_REF:
683         /* Non-constant index means any member may be accessed.  Prevent the
684            expression from being scalarized.  If we were to treat this as a
685            reference to the whole array, we can wind up with a single dynamic
686            index reference inside a loop being overridden by several constant
687            index references during loop setup.  It's possible that this could
688            be avoided by using dynamic usage counts based on BB trip counts
689            (based on loop analysis or profiling), but that hardly seems worth
690            the effort.  */
691         /* ??? Hack.  Figure out how to push this into the scan routines
692            without duplicating too much code.  */
693         if (!is_valid_const_index (inner))
694           {
695             disable_scalarization = true;
696             goto use_all;
697           }
698         /* ??? Are we assured that non-constant bounds and stride will have
699            the same value everywhere?  I don't think Fortran will...  */
700         if (TREE_OPERAND (inner, 2) || TREE_OPERAND (inner, 3))
701           goto use_all;
702         inner = TREE_OPERAND (inner, 0);
703         break;
704
705       case COMPONENT_REF:
706         /* A reference to a union member constitutes a reference to the
707            entire union.  */
708         if (TREE_CODE (TREE_TYPE (TREE_OPERAND (inner, 0))) != RECORD_TYPE)
709           goto use_all;
710         /* ??? See above re non-constant stride.  */
711         if (TREE_OPERAND (inner, 2))
712           goto use_all;
713         inner = TREE_OPERAND (inner, 0);
714         break;
715
716       case REALPART_EXPR:
717       case IMAGPART_EXPR:
718         inner = TREE_OPERAND (inner, 0);
719         break;
720
721       case BIT_FIELD_REF:
722         /* A bit field reference (access to *multiple* fields simultaneously)
723            is not currently scalarized.  Consider this an access to the
724            complete outer element, to which walk_tree will bring us next.  */
725         goto use_all;
726
727       case ARRAY_RANGE_REF:
728         /* Similarly, an subrange reference is used to modify indexing.  Which
729            means that the canonical element names that we have won't work.  */
730         goto use_all;
731
732       case VIEW_CONVERT_EXPR:
733       case NOP_EXPR:
734         /* Similarly, a view/nop explicitly wants to look at an object in a
735            type other than the one we've scalarized.  */
736         goto use_all;
737
738       case WITH_SIZE_EXPR:
739         /* This is a transparent wrapper.  The entire inner expression really
740            is being used.  */
741         goto use_all;
742
743       use_all:
744         expr_p = &TREE_OPERAND (inner, 0);
745         inner = expr = *expr_p;
746         break;
747
748       default:
749 #ifdef ENABLE_CHECKING
750         /* Validate that we're not missing any references.  */
751         gcc_assert (!walk_tree (&inner, sra_find_candidate_decl, NULL, NULL));
752 #endif
753         return;
754       }
755 }
756
757 /* Walk a TREE_LIST of values looking for scalarizable aggregates.
758    If we find one, invoke FNS->USE.  */
759
760 static void
761 sra_walk_tree_list (tree list, block_stmt_iterator *bsi, bool is_output,
762                     const struct sra_walk_fns *fns)
763 {
764   tree op;
765   for (op = list; op ; op = TREE_CHAIN (op))
766     sra_walk_expr (&TREE_VALUE (op), bsi, is_output, fns);
767 }
768
769 /* Walk the arguments of a CALL_EXPR looking for scalarizable aggregates.
770    If we find one, invoke FNS->USE.  */
771
772 static void
773 sra_walk_call_expr (tree expr, block_stmt_iterator *bsi,
774                     const struct sra_walk_fns *fns)
775 {
776   sra_walk_tree_list (TREE_OPERAND (expr, 1), bsi, false, fns);
777 }
778
779 /* Walk the inputs and outputs of an ASM_EXPR looking for scalarizable
780    aggregates.  If we find one, invoke FNS->USE.  */
781
782 static void
783 sra_walk_asm_expr (tree expr, block_stmt_iterator *bsi,
784                    const struct sra_walk_fns *fns)
785 {
786   sra_walk_tree_list (ASM_INPUTS (expr), bsi, false, fns);
787   sra_walk_tree_list (ASM_OUTPUTS (expr), bsi, true, fns);
788 }
789
790 /* Walk a MODIFY_EXPR and categorize the assignment appropriately.  */
791
792 static void
793 sra_walk_modify_expr (tree expr, block_stmt_iterator *bsi,
794                       const struct sra_walk_fns *fns)
795 {
796   struct sra_elt *lhs_elt, *rhs_elt;
797   tree lhs, rhs;
798
799   lhs = TREE_OPERAND (expr, 0);
800   rhs = TREE_OPERAND (expr, 1);
801   lhs_elt = maybe_lookup_element_for_expr (lhs);
802   rhs_elt = maybe_lookup_element_for_expr (rhs);
803
804   /* If both sides are scalarizable, this is a COPY operation.  */
805   if (lhs_elt && rhs_elt)
806     {
807       fns->copy (lhs_elt, rhs_elt, bsi);
808       return;
809     }
810
811   /* If the RHS is scalarizable, handle it.  There are only two cases.  */
812   if (rhs_elt)
813     {
814       if (!rhs_elt->is_scalar)
815         fns->ldst (rhs_elt, lhs, bsi, false);
816       else
817         fns->use (rhs_elt, &TREE_OPERAND (expr, 1), bsi, false);
818     }
819
820   /* If it isn't scalarizable, there may be scalarizable variables within, so
821      check for a call or else walk the RHS to see if we need to do any
822      copy-in operations.  We need to do it before the LHS is scalarized so
823      that the statements get inserted in the proper place, before any
824      copy-out operations.  */
825   else
826     {
827       tree call = get_call_expr_in (rhs);
828       if (call)
829         sra_walk_call_expr (call, bsi, fns);
830       else
831         sra_walk_expr (&TREE_OPERAND (expr, 1), bsi, false, fns);
832     }
833
834   /* Likewise, handle the LHS being scalarizable.  We have cases similar
835      to those above, but also want to handle RHS being constant.  */
836   if (lhs_elt)
837     {
838       /* If this is an assignment from a constant, or constructor, then
839          we have access to all of the elements individually.  Invoke INIT.  */
840       if (TREE_CODE (rhs) == COMPLEX_EXPR
841           || TREE_CODE (rhs) == COMPLEX_CST
842           || TREE_CODE (rhs) == CONSTRUCTOR)
843         fns->init (lhs_elt, rhs, bsi);
844
845       /* If this is an assignment from read-only memory, treat this as if
846          we'd been passed the constructor directly.  Invoke INIT.  */
847       else if (TREE_CODE (rhs) == VAR_DECL
848                && TREE_STATIC (rhs)
849                && TREE_READONLY (rhs)
850                && targetm.binds_local_p (rhs))
851         fns->init (lhs_elt, DECL_INITIAL (rhs), bsi);
852
853       /* If this is a copy from a non-scalarizable lvalue, invoke LDST.
854          The lvalue requirement prevents us from trying to directly scalarize
855          the result of a function call.  Which would result in trying to call
856          the function multiple times, and other evil things.  */
857       else if (!lhs_elt->is_scalar && is_gimple_addressable (rhs))
858         fns->ldst (lhs_elt, rhs, bsi, true);
859
860       /* Otherwise we're being used in some context that requires the
861          aggregate to be seen as a whole.  Invoke USE.  */
862       else
863         fns->use (lhs_elt, &TREE_OPERAND (expr, 0), bsi, true);
864     }
865
866   /* Similarly to above, LHS_ELT being null only means that the LHS as a
867      whole is not a scalarizable reference.  There may be occurrences of
868      scalarizable variables within, which implies a USE.  */
869   else
870     sra_walk_expr (&TREE_OPERAND (expr, 0), bsi, true, fns);
871 }
872
873 /* Entry point to the walk functions.  Search the entire function,
874    invoking the callbacks in FNS on each of the references to
875    scalarizable variables.  */
876
877 static void
878 sra_walk_function (const struct sra_walk_fns *fns)
879 {
880   basic_block bb;
881   block_stmt_iterator si, ni;
882
883   /* ??? Phase 4 could derive some benefit to walking the function in
884      dominator tree order.  */
885
886   FOR_EACH_BB (bb)
887     for (si = bsi_start (bb); !bsi_end_p (si); si = ni)
888       {
889         tree stmt, t;
890         stmt_ann_t ann;
891
892         stmt = bsi_stmt (si);
893         ann = stmt_ann (stmt);
894
895         ni = si;
896         bsi_next (&ni);
897
898         /* If the statement has no virtual operands, then it doesn't
899            make any structure references that we care about.  */
900         if (NUM_V_MAY_DEFS (V_MAY_DEF_OPS (ann)) == 0
901             && NUM_VUSES (VUSE_OPS (ann)) == 0
902             && NUM_V_MUST_DEFS (V_MUST_DEF_OPS (ann)) == 0)
903           continue;
904
905         switch (TREE_CODE (stmt))
906           {
907           case RETURN_EXPR:
908             /* If we have "return <retval>" then the return value is
909                already exposed for our pleasure.  Walk it as a USE to
910                force all the components back in place for the return.
911
912                If we have an embedded assignment, then <retval> is of
913                a type that gets returned in registers in this ABI, and
914                we do not wish to extend their lifetimes.  Treat this
915                as a USE of the variable on the RHS of this assignment.  */
916
917             t = TREE_OPERAND (stmt, 0);
918             if (TREE_CODE (t) == MODIFY_EXPR)
919               sra_walk_expr (&TREE_OPERAND (t, 1), &si, false, fns);
920             else
921               sra_walk_expr (&TREE_OPERAND (stmt, 0), &si, false, fns);
922             break;
923
924           case MODIFY_EXPR:
925             sra_walk_modify_expr (stmt, &si, fns);
926             break;
927           case CALL_EXPR:
928             sra_walk_call_expr (stmt, &si, fns);
929             break;
930           case ASM_EXPR:
931             sra_walk_asm_expr (stmt, &si, fns);
932             break;
933
934           default:
935             break;
936           }
937       }
938 }
939 \f
940 /* Phase One: Scan all referenced variables in the program looking for
941    structures that could be decomposed.  */
942
943 static bool
944 find_candidates_for_sra (void)
945 {
946   size_t i;
947   bool any_set = false;
948
949   for (i = 0; i < num_referenced_vars; i++)
950     {
951       tree var = referenced_var (i);
952       if (decl_can_be_decomposed_p (var))
953         {
954           bitmap_set_bit (sra_candidates, var_ann (var)->uid);
955           any_set = true;
956         }
957     }
958
959   return any_set;
960 }
961
962 \f
963 /* Phase Two: Scan all references to scalarizable variables.  Count the
964    number of times they are used or copied respectively.  */
965
966 /* Callbacks to fill in SRA_WALK_FNS.  Everything but USE is
967    considered a copy, because we can decompose the reference such that
968    the sub-elements needn't be contiguous.  */
969
970 static void
971 scan_use (struct sra_elt *elt, tree *expr_p ATTRIBUTE_UNUSED,
972           block_stmt_iterator *bsi ATTRIBUTE_UNUSED,
973           bool is_output ATTRIBUTE_UNUSED)
974 {
975   elt->n_uses += 1;
976 }
977
978 static void
979 scan_copy (struct sra_elt *lhs_elt, struct sra_elt *rhs_elt,
980            block_stmt_iterator *bsi ATTRIBUTE_UNUSED)
981 {
982   lhs_elt->n_copies += 1;
983   rhs_elt->n_copies += 1;
984 }
985
986 static void
987 scan_init (struct sra_elt *lhs_elt, tree rhs ATTRIBUTE_UNUSED,
988            block_stmt_iterator *bsi ATTRIBUTE_UNUSED)
989 {
990   lhs_elt->n_copies += 1;
991 }
992
993 static void
994 scan_ldst (struct sra_elt *elt, tree other ATTRIBUTE_UNUSED,
995            block_stmt_iterator *bsi ATTRIBUTE_UNUSED,
996            bool is_output ATTRIBUTE_UNUSED)
997 {
998   elt->n_copies += 1;
999 }
1000
1001 /* Dump the values we collected during the scanning phase.  */
1002
1003 static void
1004 scan_dump (struct sra_elt *elt)
1005 {
1006   struct sra_elt *c;
1007
1008   dump_sra_elt_name (dump_file, elt);
1009   fprintf (dump_file, ": n_uses=%u n_copies=%u\n", elt->n_uses, elt->n_copies);
1010
1011   for (c = elt->children; c ; c = c->sibling)
1012     scan_dump (c);
1013 }
1014
1015 /* Entry point to phase 2.  Scan the entire function, building up
1016    scalarization data structures, recording copies and uses.  */
1017
1018 static void
1019 scan_function (void)
1020 {
1021   static const struct sra_walk_fns fns = {
1022     scan_use, scan_copy, scan_init, scan_ldst, true
1023   };
1024   bitmap_iterator bi;
1025
1026   sra_walk_function (&fns);
1027
1028   if (dump_file && (dump_flags & TDF_DETAILS))
1029     {
1030       unsigned i;
1031
1032       fputs ("\nScan results:\n", dump_file);
1033       EXECUTE_IF_SET_IN_BITMAP (sra_candidates, 0, i, bi)
1034         {
1035           tree var = referenced_var (i);
1036           struct sra_elt *elt = lookup_element (NULL, var, NULL, NO_INSERT);
1037           if (elt)
1038             scan_dump (elt);
1039         }
1040       fputc ('\n', dump_file);
1041     }
1042 }
1043 \f
1044 /* Phase Three: Make decisions about which variables to scalarize, if any.
1045    All elements to be scalarized have replacement variables made for them.  */
1046
1047 /* A subroutine of build_element_name.  Recursively build the element
1048    name on the obstack.  */
1049
1050 static void
1051 build_element_name_1 (struct sra_elt *elt)
1052 {
1053   tree t;
1054   char buffer[32];
1055
1056   if (elt->parent)
1057     {
1058       build_element_name_1 (elt->parent);
1059       obstack_1grow (&sra_obstack, '$');
1060
1061       if (TREE_CODE (elt->parent->type) == COMPLEX_TYPE)
1062         {
1063           if (elt->element == integer_zero_node)
1064             obstack_grow (&sra_obstack, "real", 4);
1065           else
1066             obstack_grow (&sra_obstack, "imag", 4);
1067           return;
1068         }
1069     }
1070
1071   t = elt->element;
1072   if (TREE_CODE (t) == INTEGER_CST)
1073     {
1074       /* ??? Eh.  Don't bother doing double-wide printing.  */
1075       sprintf (buffer, HOST_WIDE_INT_PRINT_DEC, TREE_INT_CST_LOW (t));
1076       obstack_grow (&sra_obstack, buffer, strlen (buffer));
1077     }
1078   else
1079     {
1080       tree name = DECL_NAME (t);
1081       if (name)
1082         obstack_grow (&sra_obstack, IDENTIFIER_POINTER (name),
1083                       IDENTIFIER_LENGTH (name));
1084       else
1085         {
1086           sprintf (buffer, "D%u", DECL_UID (t));
1087           obstack_grow (&sra_obstack, buffer, strlen (buffer));
1088         }
1089     }
1090 }
1091
1092 /* Construct a pretty variable name for an element's replacement variable.
1093    The name is built on the obstack.  */
1094
1095 static char *
1096 build_element_name (struct sra_elt *elt)
1097 {
1098   build_element_name_1 (elt);
1099   obstack_1grow (&sra_obstack, '\0');
1100   return obstack_finish (&sra_obstack);
1101 }
1102
1103 /* Instantiate an element as an independent variable.  */
1104
1105 static void
1106 instantiate_element (struct sra_elt *elt)
1107 {
1108   struct sra_elt *base_elt;
1109   tree var, base;
1110
1111   for (base_elt = elt; base_elt->parent; base_elt = base_elt->parent)
1112     continue;
1113   base = base_elt->element;
1114
1115   elt->replacement = var = make_rename_temp (elt->type, "SR");
1116   DECL_SOURCE_LOCATION (var) = DECL_SOURCE_LOCATION (base);
1117   DECL_ARTIFICIAL (var) = 1;
1118
1119   if (TREE_THIS_VOLATILE (elt->type))
1120     {
1121       TREE_THIS_VOLATILE (var) = 1;
1122       TREE_SIDE_EFFECTS (var) = 1;
1123     }
1124
1125   if (DECL_NAME (base) && !DECL_IGNORED_P (base))
1126     {
1127       char *pretty_name = build_element_name (elt);
1128       DECL_NAME (var) = get_identifier (pretty_name);
1129       obstack_free (&sra_obstack, pretty_name);
1130
1131       DECL_DEBUG_EXPR (var) = generate_element_ref (elt);
1132       DECL_DEBUG_EXPR_IS_FROM (var) = 1;
1133
1134       DECL_IGNORED_P (var) = 0;
1135       TREE_NO_WARNING (var) = TREE_NO_WARNING (base);
1136     }
1137   else
1138     {
1139       DECL_IGNORED_P (var) = 1;
1140       /* ??? We can't generate any warning that would be meaningful.  */
1141       TREE_NO_WARNING (var) = 1;
1142     }
1143
1144   if (dump_file)
1145     {
1146       fputs ("  ", dump_file);
1147       dump_sra_elt_name (dump_file, elt);
1148       fputs (" -> ", dump_file);
1149       print_generic_expr (dump_file, var, dump_flags);
1150       fputc ('\n', dump_file);
1151     }
1152 }
1153
1154 /* Make one pass across an element tree deciding whether or not it's
1155    profitable to instantiate individual leaf scalars.
1156
1157    PARENT_USES and PARENT_COPIES are the sum of the N_USES and N_COPIES
1158    fields all the way up the tree.  */
1159
1160 static void
1161 decide_instantiation_1 (struct sra_elt *elt, unsigned int parent_uses,
1162                         unsigned int parent_copies)
1163 {
1164   if (dump_file && !elt->parent)
1165     {
1166       fputs ("Initial instantiation for ", dump_file);
1167       dump_sra_elt_name (dump_file, elt);
1168       fputc ('\n', dump_file);
1169     }
1170
1171   if (elt->cannot_scalarize)
1172     return;
1173
1174   if (elt->is_scalar)
1175     {
1176       /* The decision is simple: instantiate if we're used more frequently
1177          than the parent needs to be seen as a complete unit.  */
1178       if (elt->n_uses + elt->n_copies + parent_copies > parent_uses)
1179         instantiate_element (elt);
1180     }
1181   else
1182     {
1183       struct sra_elt *c;
1184       unsigned int this_uses = elt->n_uses + parent_uses;
1185       unsigned int this_copies = elt->n_copies + parent_copies;
1186
1187       for (c = elt->children; c ; c = c->sibling)
1188         decide_instantiation_1 (c, this_uses, this_copies);
1189     }
1190 }
1191
1192 /* Compute the size and number of all instantiated elements below ELT.
1193    We will only care about this if the size of the complete structure
1194    fits in a HOST_WIDE_INT, so we don't have to worry about overflow.  */
1195
1196 static unsigned int
1197 sum_instantiated_sizes (struct sra_elt *elt, unsigned HOST_WIDE_INT *sizep)
1198 {
1199   if (elt->replacement)
1200     {
1201       *sizep += TREE_INT_CST_LOW (TYPE_SIZE_UNIT (elt->type));
1202       return 1;
1203     }
1204   else
1205     {
1206       struct sra_elt *c;
1207       unsigned int count = 0;
1208
1209       for (c = elt->children; c ; c = c->sibling)
1210         count += sum_instantiated_sizes (c, sizep);
1211
1212       return count;
1213     }
1214 }
1215
1216 /* Instantiate fields in ELT->TYPE that are not currently present as
1217    children of ELT.  */
1218
1219 static void instantiate_missing_elements (struct sra_elt *elt);
1220
1221 static void
1222 instantiate_missing_elements_1 (struct sra_elt *elt, tree child, tree type)
1223 {
1224   struct sra_elt *sub = lookup_element (elt, child, type, INSERT);
1225   if (sub->is_scalar)
1226     {
1227       if (sub->replacement == NULL)
1228         instantiate_element (sub);
1229     }
1230   else
1231     instantiate_missing_elements (sub);
1232 }
1233
1234 static void
1235 instantiate_missing_elements (struct sra_elt *elt)
1236 {
1237   tree type = elt->type;
1238
1239   switch (TREE_CODE (type))
1240     {
1241     case RECORD_TYPE:
1242       {
1243         tree f;
1244         for (f = TYPE_FIELDS (type); f ; f = TREE_CHAIN (f))
1245           if (TREE_CODE (f) == FIELD_DECL)
1246             instantiate_missing_elements_1 (elt, f, TREE_TYPE (f));
1247         break;
1248       }
1249
1250     case ARRAY_TYPE:
1251       {
1252         tree i, max, subtype;
1253
1254         i = TYPE_MIN_VALUE (TYPE_DOMAIN (type));
1255         max = TYPE_MAX_VALUE (TYPE_DOMAIN (type));
1256         subtype = TREE_TYPE (type);
1257
1258         while (1)
1259           {
1260             instantiate_missing_elements_1 (elt, i, subtype);
1261             if (tree_int_cst_equal (i, max))
1262               break;
1263             i = int_const_binop (PLUS_EXPR, i, integer_one_node, true);
1264           }
1265
1266         break;
1267       }
1268
1269     case COMPLEX_TYPE:
1270       type = TREE_TYPE (type);
1271       instantiate_missing_elements_1 (elt, integer_zero_node, type);
1272       instantiate_missing_elements_1 (elt, integer_one_node, type);
1273       break;
1274
1275     default:
1276       gcc_unreachable ();
1277     }
1278 }
1279
1280 /* Make one pass across an element tree deciding whether to perform block
1281    or element copies.  If we decide on element copies, instantiate all
1282    elements.  Return true if there are any instantiated sub-elements.  */
1283
1284 static bool
1285 decide_block_copy (struct sra_elt *elt)
1286 {
1287   struct sra_elt *c;
1288   bool any_inst;
1289
1290   /* If scalarization is disabled, respect it.  */
1291   if (elt->cannot_scalarize)
1292     {
1293       elt->use_block_copy = 1;
1294
1295       if (dump_file)
1296         {
1297           fputs ("Scalarization disabled for ", dump_file);
1298           dump_sra_elt_name (dump_file, elt);
1299           fputc ('\n', dump_file);
1300         }
1301
1302       return false;
1303     }
1304
1305   /* Don't decide if we've no uses.  */
1306   if (elt->n_uses == 0 && elt->n_copies == 0)
1307     ;
1308
1309   else if (!elt->is_scalar)
1310     {
1311       tree size_tree = TYPE_SIZE_UNIT (elt->type);
1312       bool use_block_copy = true;
1313
1314       /* Tradeoffs for COMPLEX types pretty much always make it better
1315          to go ahead and split the components.  */
1316       if (TREE_CODE (elt->type) == COMPLEX_TYPE)
1317         use_block_copy = false;
1318
1319       /* Don't bother trying to figure out the rest if the structure is
1320          so large we can't do easy arithmetic.  This also forces block
1321          copies for variable sized structures.  */
1322       else if (host_integerp (size_tree, 1))
1323         {
1324           unsigned HOST_WIDE_INT full_size, inst_size = 0;
1325           unsigned int inst_count;
1326           unsigned int max_size;
1327
1328           /* If the sra-max-structure-size parameter is 0, then the
1329              user has not overridden the parameter and we can choose a
1330              sensible default.  */
1331           max_size = SRA_MAX_STRUCTURE_SIZE
1332             ? SRA_MAX_STRUCTURE_SIZE
1333             : MOVE_RATIO * UNITS_PER_WORD;
1334
1335           full_size = tree_low_cst (size_tree, 1);
1336
1337           /* ??? What to do here.  If there are two fields, and we've only
1338              instantiated one, then instantiating the other is clearly a win.
1339              If there are a large number of fields then the size of the copy
1340              is much more of a factor.  */
1341
1342           /* If the structure is small, and we've made copies, go ahead
1343              and instantiate, hoping that the copies will go away.  */
1344           if (full_size <= max_size
1345               && elt->n_copies > elt->n_uses)
1346             use_block_copy = false;
1347           else
1348             {
1349               inst_count = sum_instantiated_sizes (elt, &inst_size);
1350
1351               if (inst_size * 100 >= full_size * SRA_FIELD_STRUCTURE_RATIO)
1352                 use_block_copy = false;
1353             }
1354
1355           /* In order to avoid block copy, we have to be able to instantiate
1356              all elements of the type.  See if this is possible.  */
1357           if (!use_block_copy
1358               && (!can_completely_scalarize_p (elt)
1359                   || !type_can_instantiate_all_elements (elt->type)))
1360             use_block_copy = true;
1361         }
1362       elt->use_block_copy = use_block_copy;
1363
1364       if (dump_file)
1365         {
1366           fprintf (dump_file, "Using %s for ",
1367                    use_block_copy ? "block-copy" : "element-copy");
1368           dump_sra_elt_name (dump_file, elt);
1369           fputc ('\n', dump_file);
1370         }
1371
1372       if (!use_block_copy)
1373         {
1374           instantiate_missing_elements (elt);
1375           return true;
1376         }
1377     }
1378
1379   any_inst = elt->replacement != NULL;
1380
1381   for (c = elt->children; c ; c = c->sibling)
1382     any_inst |= decide_block_copy (c);
1383
1384   return any_inst;
1385 }
1386
1387 /* Entry point to phase 3.  Instantiate scalar replacement variables.  */
1388
1389 static void
1390 decide_instantiations (void)
1391 {
1392   unsigned int i;
1393   bool cleared_any;
1394   bitmap_head done_head;
1395   bitmap_iterator bi;
1396
1397   /* We cannot clear bits from a bitmap we're iterating over,
1398      so save up all the bits to clear until the end.  */
1399   bitmap_initialize (&done_head, &bitmap_default_obstack);
1400   cleared_any = false;
1401
1402   EXECUTE_IF_SET_IN_BITMAP (sra_candidates, 0, i, bi)
1403     {
1404       tree var = referenced_var (i);
1405       struct sra_elt *elt = lookup_element (NULL, var, NULL, NO_INSERT);
1406       if (elt)
1407         {
1408           decide_instantiation_1 (elt, 0, 0);
1409           if (!decide_block_copy (elt))
1410             elt = NULL;
1411         }
1412       if (!elt)
1413         {
1414           bitmap_set_bit (&done_head, i);
1415           cleared_any = true;
1416         }
1417     }
1418
1419   if (cleared_any)
1420     {
1421       bitmap_and_compl_into (sra_candidates, &done_head);
1422       bitmap_and_compl_into (needs_copy_in, &done_head);
1423     }
1424   bitmap_clear (&done_head);
1425
1426   if (dump_file)
1427     fputc ('\n', dump_file);
1428 }
1429
1430 \f
1431 /* Phase Four: Update the function to match the replacements created.  */
1432
1433 /* Mark all the variables in V_MAY_DEF or V_MUST_DEF operands for STMT for
1434    renaming. This becomes necessary when we modify all of a non-scalar.  */
1435
1436 static void
1437 mark_all_v_defs (tree stmt)
1438 {
1439   tree sym;
1440   ssa_op_iter iter;
1441
1442   get_stmt_operands (stmt);
1443
1444   FOR_EACH_SSA_TREE_OPERAND (sym, stmt, iter, SSA_OP_ALL_VIRTUALS)
1445     {
1446       if (TREE_CODE (sym) == SSA_NAME)
1447         sym = SSA_NAME_VAR (sym);
1448       bitmap_set_bit (vars_to_rename, var_ann (sym)->uid);
1449     }
1450 }
1451
1452 /* Build a single level component reference to ELT rooted at BASE.  */
1453
1454 static tree
1455 generate_one_element_ref (struct sra_elt *elt, tree base)
1456 {
1457   switch (TREE_CODE (TREE_TYPE (base)))
1458     {
1459     case RECORD_TYPE:
1460       {
1461         tree field = elt->element;
1462
1463         /* Watch out for compatible records with differing field lists.  */
1464         if (DECL_FIELD_CONTEXT (field) != TYPE_MAIN_VARIANT (TREE_TYPE (base)))
1465           field = find_compatible_field (TREE_TYPE (base), field);
1466
1467         return build (COMPONENT_REF, elt->type, base, field, NULL);
1468       }
1469
1470     case ARRAY_TYPE:
1471       return build (ARRAY_REF, elt->type, base, elt->element, NULL, NULL);
1472
1473     case COMPLEX_TYPE:
1474       if (elt->element == integer_zero_node)
1475         return build (REALPART_EXPR, elt->type, base);
1476       else
1477         return build (IMAGPART_EXPR, elt->type, base);
1478
1479     default:
1480       gcc_unreachable ();
1481     }
1482 }
1483
1484 /* Build a full component reference to ELT rooted at its native variable.  */
1485
1486 static tree
1487 generate_element_ref (struct sra_elt *elt)
1488 {
1489   if (elt->parent)
1490     return generate_one_element_ref (elt, generate_element_ref (elt->parent));
1491   else
1492     return elt->element;
1493 }
1494
1495 /* Generate a set of assignment statements in *LIST_P to copy all
1496    instantiated elements under ELT to or from the equivalent structure
1497    rooted at EXPR.  COPY_OUT controls the direction of the copy, with
1498    true meaning to copy out of EXPR into ELT.  */
1499
1500 static void
1501 generate_copy_inout (struct sra_elt *elt, bool copy_out, tree expr,
1502                      tree *list_p)
1503 {
1504   struct sra_elt *c;
1505   tree t;
1506
1507   if (elt->replacement)
1508     {
1509       if (copy_out)
1510         t = build (MODIFY_EXPR, void_type_node, elt->replacement, expr);
1511       else
1512         t = build (MODIFY_EXPR, void_type_node, expr, elt->replacement);
1513       append_to_statement_list (t, list_p);
1514     }
1515   else
1516     {
1517       for (c = elt->children; c ; c = c->sibling)
1518         {
1519           t = generate_one_element_ref (c, unshare_expr (expr));
1520           generate_copy_inout (c, copy_out, t, list_p);
1521         }
1522     }
1523 }
1524
1525 /* Generate a set of assignment statements in *LIST_P to copy all instantiated
1526    elements under SRC to their counterparts under DST.  There must be a 1-1
1527    correspondence of instantiated elements.  */
1528
1529 static void
1530 generate_element_copy (struct sra_elt *dst, struct sra_elt *src, tree *list_p)
1531 {
1532   struct sra_elt *dc, *sc;
1533
1534   for (dc = dst->children; dc ; dc = dc->sibling)
1535     {
1536       sc = lookup_element (src, dc->element, NULL, NO_INSERT);
1537       gcc_assert (sc);
1538       generate_element_copy (dc, sc, list_p);
1539     }
1540
1541   if (dst->replacement)
1542     {
1543       tree t;
1544
1545       gcc_assert (src->replacement);
1546
1547       t = build (MODIFY_EXPR, void_type_node, dst->replacement,
1548                  src->replacement);
1549       append_to_statement_list (t, list_p);
1550     }
1551 }
1552
1553 /* Generate a set of assignment statements in *LIST_P to zero all instantiated
1554    elements under ELT.  In addition, do not assign to elements that have been
1555    marked VISITED but do reset the visited flag; this allows easy coordination
1556    with generate_element_init.  */
1557
1558 static void
1559 generate_element_zero (struct sra_elt *elt, tree *list_p)
1560 {
1561   struct sra_elt *c;
1562
1563   if (elt->visited)
1564     {
1565       elt->visited = false;
1566       return;
1567     }
1568
1569   for (c = elt->children; c ; c = c->sibling)
1570     generate_element_zero (c, list_p);
1571
1572   if (elt->replacement)
1573     {
1574       tree t;
1575
1576       gcc_assert (elt->is_scalar);
1577       t = fold_convert (elt->type, integer_zero_node);
1578
1579       t = build (MODIFY_EXPR, void_type_node, elt->replacement, t);
1580       append_to_statement_list (t, list_p);
1581     }
1582 }
1583
1584 /* Generate an assignment VAR = INIT, where INIT may need gimplification.
1585    Add the result to *LIST_P.  */
1586
1587 static void
1588 generate_one_element_init (tree var, tree init, tree *list_p)
1589 {
1590   /* The replacement can be almost arbitrarily complex.  Gimplify.  */
1591   tree stmt = build (MODIFY_EXPR, void_type_node, var, init);
1592   gimplify_and_add (stmt, list_p);
1593 }
1594
1595 /* Generate a set of assignment statements in *LIST_P to set all instantiated
1596    elements under ELT with the contents of the initializer INIT.  In addition,
1597    mark all assigned elements VISITED; this allows easy coordination with
1598    generate_element_zero.  Return false if we found a case we couldn't
1599    handle.  */
1600
1601 static bool
1602 generate_element_init_1 (struct sra_elt *elt, tree init, tree *list_p)
1603 {
1604   bool result = true;
1605   enum tree_code init_code;
1606   struct sra_elt *sub;
1607   tree t;
1608
1609   /* We can be passed DECL_INITIAL of a static variable.  It might have a
1610      conversion, which we strip off here.  */
1611   STRIP_USELESS_TYPE_CONVERSION (init);
1612   init_code = TREE_CODE (init);
1613
1614   if (elt->is_scalar)
1615     {
1616       if (elt->replacement)
1617         {
1618           generate_one_element_init (elt->replacement, init, list_p);
1619           elt->visited = true;
1620         }
1621       return result;
1622     }
1623
1624   switch (init_code)
1625     {
1626     case COMPLEX_CST:
1627     case COMPLEX_EXPR:
1628       for (sub = elt->children; sub ; sub = sub->sibling)
1629         {
1630           if (sub->element == integer_zero_node)
1631             t = (init_code == COMPLEX_EXPR
1632                  ? TREE_OPERAND (init, 0) : TREE_REALPART (init));
1633           else
1634             t = (init_code == COMPLEX_EXPR
1635                  ? TREE_OPERAND (init, 1) : TREE_IMAGPART (init));
1636           result &= generate_element_init_1 (sub, t, list_p);
1637         }
1638       break;
1639
1640     case CONSTRUCTOR:
1641       for (t = CONSTRUCTOR_ELTS (init); t ; t = TREE_CHAIN (t))
1642         {
1643           sub = lookup_element (elt, TREE_PURPOSE (t), NULL, NO_INSERT);
1644           if (sub == NULL)
1645             continue;
1646           result &= generate_element_init_1 (sub, TREE_VALUE (t), list_p);
1647         }
1648       break;
1649
1650     default:
1651       elt->visited = true;
1652       result = false;
1653     }
1654
1655   return result;
1656 }
1657
1658 /* A wrapper function for generate_element_init_1 that handles cleanup after
1659    gimplification.  */
1660
1661 static bool
1662 generate_element_init (struct sra_elt *elt, tree init, tree *list_p)
1663 {
1664   bool ret;
1665
1666   push_gimplify_context ();
1667   ret = generate_element_init_1 (elt, init, list_p);
1668   pop_gimplify_context (NULL);
1669
1670   /* The replacement can expose previously unreferenced variables.  */
1671   if (ret && *list_p)
1672     {
1673       tree_stmt_iterator i;
1674       size_t old, new, j;
1675
1676       old = num_referenced_vars;
1677
1678       for (i = tsi_start (*list_p); !tsi_end_p (i); tsi_next (&i))
1679         find_new_referenced_vars (tsi_stmt_ptr (i));
1680
1681       new = num_referenced_vars;
1682       for (j = old; j < new; ++j)
1683         bitmap_set_bit (vars_to_rename, j);
1684     }
1685
1686   return ret;
1687 }
1688
1689 /* Insert STMT on all the outgoing edges out of BB.  Note that if BB
1690    has more than one edge, STMT will be replicated for each edge.  Also,
1691    abnormal edges will be ignored.  */
1692
1693 void
1694 insert_edge_copies (tree stmt, basic_block bb)
1695 {
1696   edge e;
1697   edge_iterator ei;
1698   bool first_copy;
1699
1700   first_copy = true;
1701   FOR_EACH_EDGE (e, ei, bb->succs)
1702     {
1703       /* We don't need to insert copies on abnormal edges.  The
1704          value of the scalar replacement is not guaranteed to
1705          be valid through an abnormal edge.  */
1706       if (!(e->flags & EDGE_ABNORMAL))
1707         {
1708           if (first_copy)
1709             {
1710               bsi_insert_on_edge (e, stmt);
1711               first_copy = false;
1712             }
1713           else
1714             bsi_insert_on_edge (e, unsave_expr_now (stmt));
1715         }
1716     }
1717 }
1718
1719 /* Helper function to insert LIST before BSI, and set up line number info.  */
1720
1721 static void
1722 sra_insert_before (block_stmt_iterator *bsi, tree list)
1723 {
1724   tree stmt = bsi_stmt (*bsi);
1725
1726   if (EXPR_HAS_LOCATION (stmt))
1727     annotate_all_with_locus (&list, EXPR_LOCATION (stmt));
1728   bsi_insert_before (bsi, list, BSI_SAME_STMT);
1729 }
1730
1731 /* Similarly, but insert after BSI.  Handles insertion onto edges as well.  */
1732
1733 static void
1734 sra_insert_after (block_stmt_iterator *bsi, tree list)
1735 {
1736   tree stmt = bsi_stmt (*bsi);
1737
1738   if (EXPR_HAS_LOCATION (stmt))
1739     annotate_all_with_locus (&list, EXPR_LOCATION (stmt));
1740
1741   if (stmt_ends_bb_p (stmt))
1742     insert_edge_copies (list, bsi->bb);
1743   else
1744     bsi_insert_after (bsi, list, BSI_SAME_STMT);
1745 }
1746
1747 /* Similarly, but replace the statement at BSI.  */
1748
1749 static void
1750 sra_replace (block_stmt_iterator *bsi, tree list)
1751 {
1752   sra_insert_before (bsi, list);
1753   bsi_remove (bsi);
1754   if (bsi_end_p (*bsi))
1755     *bsi = bsi_last (bsi->bb);
1756   else
1757     bsi_prev (bsi);
1758 }
1759
1760 /* Scalarize a USE.  To recap, this is either a simple reference to ELT,
1761    if elt is scalar, or some occurrence of ELT that requires a complete
1762    aggregate.  IS_OUTPUT is true if ELT is being modified.  */
1763
1764 static void
1765 scalarize_use (struct sra_elt *elt, tree *expr_p, block_stmt_iterator *bsi,
1766                bool is_output)
1767 {
1768   tree list = NULL, stmt = bsi_stmt (*bsi);
1769
1770   if (elt->replacement)
1771     {
1772       /* If we have a replacement, then updating the reference is as
1773          simple as modifying the existing statement in place.  */
1774       if (is_output)
1775         mark_all_v_defs (stmt);
1776       *expr_p = elt->replacement;
1777       modify_stmt (stmt);
1778     }
1779   else
1780     {
1781       /* Otherwise we need some copies.  If ELT is being read, then we want
1782          to store all (modified) sub-elements back into the structure before
1783          the reference takes place.  If ELT is being written, then we want to
1784          load the changed values back into our shadow variables.  */
1785       /* ??? We don't check modified for reads, we just always write all of
1786          the values.  We should be able to record the SSA number of the VOP
1787          for which the values were last read.  If that number matches the
1788          SSA number of the VOP in the current statement, then we needn't
1789          emit an assignment.  This would also eliminate double writes when
1790          a structure is passed as more than one argument to a function call.
1791          This optimization would be most effective if sra_walk_function
1792          processed the blocks in dominator order.  */
1793
1794       generate_copy_inout (elt, is_output, generate_element_ref (elt), &list);
1795       if (list == NULL)
1796         return;
1797       mark_all_v_defs (expr_first (list));
1798       if (is_output)
1799         sra_insert_after (bsi, list);
1800       else
1801         sra_insert_before (bsi, list);
1802     }
1803 }
1804
1805 /* Scalarize a COPY.  To recap, this is an assignment statement between
1806    two scalarizable references, LHS_ELT and RHS_ELT.  */
1807
1808 static void
1809 scalarize_copy (struct sra_elt *lhs_elt, struct sra_elt *rhs_elt,
1810                 block_stmt_iterator *bsi)
1811 {
1812   tree list, stmt;
1813
1814   if (lhs_elt->replacement && rhs_elt->replacement)
1815     {
1816       /* If we have two scalar operands, modify the existing statement.  */
1817       stmt = bsi_stmt (*bsi);
1818
1819       /* See the commentary in sra_walk_function concerning
1820          RETURN_EXPR, and why we should never see one here.  */
1821       gcc_assert (TREE_CODE (stmt) == MODIFY_EXPR);
1822
1823       TREE_OPERAND (stmt, 0) = lhs_elt->replacement;
1824       TREE_OPERAND (stmt, 1) = rhs_elt->replacement;
1825       modify_stmt (stmt);
1826     }
1827   else if (lhs_elt->use_block_copy || rhs_elt->use_block_copy)
1828     {
1829       /* If either side requires a block copy, then sync the RHS back
1830          to the original structure, leave the original assignment
1831          statement (which will perform the block copy), then load the
1832          LHS values out of its now-updated original structure.  */
1833       /* ??? Could perform a modified pair-wise element copy.  That
1834          would at least allow those elements that are instantiated in
1835          both structures to be optimized well.  */
1836
1837       list = NULL;
1838       generate_copy_inout (rhs_elt, false,
1839                            generate_element_ref (rhs_elt), &list);
1840       if (list)
1841         {
1842           mark_all_v_defs (expr_first (list));
1843           sra_insert_before (bsi, list);
1844         }
1845
1846       list = NULL;
1847       generate_copy_inout (lhs_elt, true,
1848                            generate_element_ref (lhs_elt), &list);
1849       if (list)
1850         sra_insert_after (bsi, list);
1851     }
1852   else
1853     {
1854       /* Otherwise both sides must be fully instantiated.  In which
1855          case perform pair-wise element assignments and replace the
1856          original block copy statement.  */
1857
1858       stmt = bsi_stmt (*bsi);
1859       mark_all_v_defs (stmt);
1860
1861       list = NULL;
1862       generate_element_copy (lhs_elt, rhs_elt, &list);
1863       gcc_assert (list);
1864       sra_replace (bsi, list);
1865     }
1866 }
1867
1868 /* Scalarize an INIT.  To recap, this is an assignment to a scalarizable
1869    reference from some form of constructor: CONSTRUCTOR, COMPLEX_CST or
1870    COMPLEX_EXPR.  If RHS is NULL, it should be treated as an empty
1871    CONSTRUCTOR.  */
1872
1873 static void
1874 scalarize_init (struct sra_elt *lhs_elt, tree rhs, block_stmt_iterator *bsi)
1875 {
1876   bool result = true;
1877   tree list = NULL;
1878
1879   /* Generate initialization statements for all members extant in the RHS.  */
1880   if (rhs)
1881     {
1882       /* Unshare the expression just in case this is from a decl's initial.  */
1883       rhs = unshare_expr (rhs);
1884       result = generate_element_init (lhs_elt, rhs, &list);
1885     }
1886
1887   /* CONSTRUCTOR is defined such that any member not mentioned is assigned
1888      a zero value.  Initialize the rest of the instantiated elements.  */
1889   generate_element_zero (lhs_elt, &list);
1890
1891   if (!result)
1892     {
1893       /* If we failed to convert the entire initializer, then we must
1894          leave the structure assignment in place and must load values
1895          from the structure into the slots for which we did not find
1896          constants.  The easiest way to do this is to generate a complete
1897          copy-out, and then follow that with the constant assignments
1898          that we were able to build.  DCE will clean things up.  */
1899       tree list0 = NULL;
1900       generate_copy_inout (lhs_elt, true, generate_element_ref (lhs_elt),
1901                            &list0);
1902       append_to_statement_list (list, &list0);
1903       list = list0;
1904     }
1905
1906   if (lhs_elt->use_block_copy || !result)
1907     {
1908       /* Since LHS is not fully instantiated, we must leave the structure
1909          assignment in place.  Treating this case differently from a USE
1910          exposes constants to later optimizations.  */
1911       if (list)
1912         {
1913           mark_all_v_defs (expr_first (list));
1914           sra_insert_after (bsi, list);
1915         }
1916     }
1917   else
1918     {
1919       /* The LHS is fully instantiated.  The list of initializations
1920          replaces the original structure assignment.  */
1921       gcc_assert (list);
1922       mark_all_v_defs (bsi_stmt (*bsi));
1923       sra_replace (bsi, list);
1924     }
1925 }
1926
1927 /* A subroutine of scalarize_ldst called via walk_tree.  Set TREE_NO_TRAP
1928    on all INDIRECT_REFs.  */
1929
1930 static tree
1931 mark_notrap (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED)
1932 {
1933   tree t = *tp;
1934
1935   if (TREE_CODE (t) == INDIRECT_REF)
1936     {
1937       TREE_THIS_NOTRAP (t) = 1;
1938       *walk_subtrees = 0;
1939     }
1940   else if (IS_TYPE_OR_DECL_P (t))
1941     *walk_subtrees = 0;
1942
1943   return NULL;
1944 }
1945
1946 /* Scalarize a LDST.  To recap, this is an assignment between one scalarizable
1947    reference ELT and one non-scalarizable reference OTHER.  IS_OUTPUT is true
1948    if ELT is on the left-hand side.  */
1949
1950 static void
1951 scalarize_ldst (struct sra_elt *elt, tree other,
1952                 block_stmt_iterator *bsi, bool is_output)
1953 {
1954   /* Shouldn't have gotten called for a scalar.  */
1955   gcc_assert (!elt->replacement);
1956
1957   if (elt->use_block_copy)
1958     {
1959       /* Since ELT is not fully instantiated, we have to leave the
1960          block copy in place.  Treat this as a USE.  */
1961       scalarize_use (elt, NULL, bsi, is_output);
1962     }
1963   else
1964     {
1965       /* The interesting case is when ELT is fully instantiated.  In this
1966          case we can have each element stored/loaded directly to/from the
1967          corresponding slot in OTHER.  This avoids a block copy.  */
1968
1969       tree list = NULL, stmt = bsi_stmt (*bsi);
1970
1971       mark_all_v_defs (stmt);
1972       generate_copy_inout (elt, is_output, other, &list);
1973       gcc_assert (list);
1974
1975       /* Preserve EH semantics.  */
1976       if (stmt_ends_bb_p (stmt))
1977         {
1978           tree_stmt_iterator tsi;
1979           tree first;
1980
1981           /* Extract the first statement from LIST.  */
1982           tsi = tsi_start (list);
1983           first = tsi_stmt (tsi);
1984           tsi_delink (&tsi);
1985
1986           /* Replace the old statement with this new representative.  */
1987           bsi_replace (bsi, first, true);
1988
1989           if (!tsi_end_p (tsi))
1990             {
1991               /* If any reference would trap, then they all would.  And more
1992                  to the point, the first would.  Therefore none of the rest
1993                  will trap since the first didn't.  Indicate this by
1994                  iterating over the remaining statements and set
1995                  TREE_THIS_NOTRAP in all INDIRECT_REFs.  */
1996               do
1997                 {
1998                   walk_tree (tsi_stmt_ptr (tsi), mark_notrap, NULL, NULL);
1999                   tsi_next (&tsi);
2000                 }
2001               while (!tsi_end_p (tsi));
2002
2003               insert_edge_copies (list, bsi->bb);
2004             }
2005         }
2006       else
2007         sra_replace (bsi, list);
2008     }
2009 }
2010
2011 /* Generate initializations for all scalarizable parameters.  */
2012
2013 static void
2014 scalarize_parms (void)
2015 {
2016   tree list = NULL;
2017   unsigned i;
2018   bitmap_iterator bi;
2019
2020   EXECUTE_IF_SET_IN_BITMAP (needs_copy_in, 0, i, bi)
2021     {
2022       tree var = referenced_var (i);
2023       struct sra_elt *elt = lookup_element (NULL, var, NULL, NO_INSERT);
2024       generate_copy_inout (elt, true, var, &list);
2025     }
2026
2027   if (list)
2028     insert_edge_copies (list, ENTRY_BLOCK_PTR);
2029 }
2030
2031 /* Entry point to phase 4.  Update the function to match replacements.  */
2032
2033 static void
2034 scalarize_function (void)
2035 {
2036   static const struct sra_walk_fns fns = {
2037     scalarize_use, scalarize_copy, scalarize_init, scalarize_ldst, false
2038   };
2039
2040   sra_walk_function (&fns);
2041   scalarize_parms ();
2042   bsi_commit_edge_inserts ();
2043 }
2044
2045 \f
2046 /* Debug helper function.  Print ELT in a nice human-readable format.  */
2047
2048 static void
2049 dump_sra_elt_name (FILE *f, struct sra_elt *elt)
2050 {
2051   if (elt->parent && TREE_CODE (elt->parent->type) == COMPLEX_TYPE)
2052     {
2053       fputs (elt->element == integer_zero_node ? "__real__ " : "__imag__ ", f);
2054       dump_sra_elt_name (f, elt->parent);
2055     }
2056   else
2057     {
2058       if (elt->parent)
2059         dump_sra_elt_name (f, elt->parent);
2060       if (DECL_P (elt->element))
2061         {
2062           if (TREE_CODE (elt->element) == FIELD_DECL)
2063             fputc ('.', f);
2064           print_generic_expr (f, elt->element, dump_flags);
2065         }
2066       else
2067         fprintf (f, "[" HOST_WIDE_INT_PRINT_DEC "]",
2068                  TREE_INT_CST_LOW (elt->element));
2069     }
2070 }
2071
2072 /* Likewise, but callable from the debugger.  */
2073
2074 void
2075 debug_sra_elt_name (struct sra_elt *elt)
2076 {
2077   dump_sra_elt_name (stderr, elt);
2078   fputc ('\n', stderr);
2079 }
2080
2081 /* Main entry point.  */
2082
2083 static void
2084 tree_sra (void)
2085 {
2086   /* Initialize local variables.  */
2087   gcc_obstack_init (&sra_obstack);
2088   sra_candidates = BITMAP_ALLOC (NULL);
2089   needs_copy_in = BITMAP_ALLOC (NULL);
2090   sra_type_decomp_cache = BITMAP_ALLOC (NULL);
2091   sra_type_inst_cache = BITMAP_ALLOC (NULL);
2092   sra_map = htab_create (101, sra_elt_hash, sra_elt_eq, NULL);
2093
2094   /* Scan.  If we find anything, instantiate and scalarize.  */
2095   if (find_candidates_for_sra ())
2096     {
2097       scan_function ();
2098       decide_instantiations ();
2099       scalarize_function ();
2100     }
2101
2102   /* Free allocated memory.  */
2103   htab_delete (sra_map);
2104   sra_map = NULL;
2105   BITMAP_FREE (sra_candidates);
2106   BITMAP_FREE (needs_copy_in);
2107   BITMAP_FREE (sra_type_decomp_cache);
2108   BITMAP_FREE (sra_type_inst_cache);
2109   obstack_free (&sra_obstack, NULL);
2110 }
2111
2112 static bool
2113 gate_sra (void)
2114 {
2115   return flag_tree_sra != 0;
2116 }
2117
2118 struct tree_opt_pass pass_sra =
2119 {
2120   "sra",                                /* name */
2121   gate_sra,                             /* gate */
2122   tree_sra,                             /* execute */
2123   NULL,                                 /* sub */
2124   NULL,                                 /* next */
2125   0,                                    /* static_pass_number */
2126   TV_TREE_SRA,                          /* tv_id */
2127   PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
2128   0,                                    /* properties_provided */
2129   0,                                    /* properties_destroyed */
2130   0,                                    /* todo_flags_start */
2131   TODO_dump_func | TODO_rename_vars
2132     | TODO_ggc_collect | TODO_verify_ssa,  /* todo_flags_finish */
2133   0                                     /* letter */
2134 };