OSDN Git Service

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