1 /* Scalar Replacement of Aggregates (SRA) converts some structure
2 references into scalar references, exposing them to the scalar
4 Copyright (C) 2003, 2004 Free Software Foundation, Inc.
5 Contributed by Diego Novillo <dnovillo@redhat.com>
7 This file is part of GCC.
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
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
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
26 #include "coretypes.h"
32 /* These RTL headers are needed for basic-block.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-simple.h"
42 #include "tree-dump.h"
43 #include "tree-pass.h"
49 /* Maximum number of fields that a structure should have to be scalarized.
50 FIXME This limit has been arbitrarily set to 5. Experiment to find a
52 #define MAX_NFIELDS_FOR_SRA 5
54 /* Codes indicating how to copy one structure into another. */
55 enum sra_copy_mode { SCALAR_SCALAR, FIELD_SCALAR, SCALAR_FIELD };
57 /* Local functions. */
58 static inline bool can_be_scalarized_p (tree);
59 static inline void insert_edge_copies (tree stmt, basic_block bb);
60 static tree create_scalar_copies (tree lhs, tree rhs, enum sra_copy_mode mode);
61 static inline void scalarize_component_ref (tree, tree *tp);
62 static void scalarize_structures (void);
63 static void scalarize_stmt (block_stmt_iterator *);
64 static void scalarize_modify_expr (block_stmt_iterator *);
65 static void scalarize_call_expr (block_stmt_iterator *);
66 static void scalarize_asm_expr (block_stmt_iterator *);
67 static void scalarize_return_expr (block_stmt_iterator *);
69 /* The set of aggregate variables that are candidates for scalarization. */
70 static bitmap sra_candidates;
72 /* Set of scalarizable PARM_DECLs that need copy-in operations at the
73 beginning of the function. */
74 static bitmap needs_copy_in;
76 /* This structure holds the mapping between and element of an aggregate
77 and the scalar replacement variable. */
86 static htab_t sra_map;
89 sra_elt_hash (const void *x)
91 const struct sra_elt *e = x;
92 hashval_t h = (size_t) e->base * e->kind;
93 if (e->kind == COMPONENT_REF)
94 h ^= (size_t) e->field;
99 sra_elt_eq (const void *x, const void *y)
101 const struct sra_elt *a = x;
102 const struct sra_elt *b = y;
104 if (a->kind != b->kind)
106 if (a->base != b->base)
108 if (a->kind == COMPONENT_REF)
109 if (a->field != b->field)
115 /* Build a temporary. Make sure and register it to be renamed. */
118 make_temp (tree type, const char *prefix)
120 tree t = create_tmp_var (type, prefix);
121 add_referenced_tmp_var (t);
122 bitmap_set_bit (vars_to_rename, var_ann (t)->uid);
126 /* Mark all the variables in VDEF operands for STMT for renaming.
127 This becomes necessary when we modify all of a non-scalar. */
130 mark_all_vdefs (tree stmt)
135 get_stmt_operands (stmt);
136 vdefs = VDEF_OPS (stmt_ann (stmt));
137 n = NUM_VDEFS (vdefs);
139 for (i = 0; i < n; i++)
141 tree sym = VDEF_RESULT (vdefs, i);
142 bitmap_set_bit (vars_to_rename, var_ann (sym)->uid);
146 /* Return true if DECL is an SRA candidate. */
149 is_sra_candidate_decl (tree decl)
151 return DECL_P (decl) && bitmap_bit_p (sra_candidates, var_ann (decl)->uid);
154 /* Return true if EXP is of the form <ref decl>, where REF is one of the
155 field access references we handle and DECL is an SRA candidate.
157 Set ALLOW_BIT_FIELD_REF to accept BIT_FIELD_REF as well. This is
158 normally false, except when we're trying to work around it. */
161 is_sra_candidate_ref (tree exp, bool allow_bit_field_ref)
163 switch (TREE_CODE (exp))
166 if (!allow_bit_field_ref)
173 return is_sra_candidate_decl (TREE_OPERAND (exp, 0));
182 /* Return the scalar in SRA_MAP[VAR_IX][FIELD_IX]. If none exists, create
183 a new scalar with type TYPE. */
186 lookup_scalar (struct sra_elt *key, tree type)
188 struct sra_elt **slot, *res;
190 slot = (struct sra_elt **) htab_find_slot (sra_map, key, INSERT);
194 res = xmalloc (sizeof (*res));
197 res->replace = make_temp (type, "SR");
199 if (DECL_NAME (key->base) && !DECL_IGNORED_P (key->base))
205 if (!DECL_NAME (key->field))
207 name = concat (IDENTIFIER_POINTER (DECL_NAME (key->base)),
209 IDENTIFIER_POINTER (DECL_NAME (key->field)),
213 name = concat (IDENTIFIER_POINTER (DECL_NAME (key->base)),
217 name = concat (IDENTIFIER_POINTER (DECL_NAME (key->base)),
225 DECL_NAME (res->replace) = get_identifier (name);
230 DECL_SOURCE_LOCATION (res->replace) = DECL_SOURCE_LOCATION (key->base);
231 TREE_NO_WARNING (res->replace) = TREE_NO_WARNING (key->base);
232 DECL_ARTIFICIAL (res->replace) = DECL_ARTIFICIAL (key->base);
239 /* Given a structure reference VAR.FIELD, return a scalar representing it.
240 If no scalar is found, a new one is created and added to the SRA_MAP
244 get_scalar_for_field (tree var, tree field)
248 #ifdef ENABLE_CHECKING
249 /* Validate that FIELD actually exists in VAR's type. */
252 for (f = TYPE_FIELDS (TREE_TYPE (var)); f ; f = TREE_CHAIN (f))
260 key.kind = COMPONENT_REF;
264 return lookup_scalar (&key, TREE_TYPE (field));
268 /* Similarly for the parts of a complex type. */
271 get_scalar_for_complex_part (tree var, enum tree_code part)
278 return lookup_scalar (&key, TREE_TYPE (TREE_TYPE (var)));
281 /* Return true if the fields of VAR can be replaced by scalar temporaries.
282 This only happens if VAR is not call-clobbered and it contains less
283 than MAX_NFIELDS_FOR_SRA scalar fields. */
286 can_be_scalarized_p (tree var)
291 if (!is_gimple_non_addressable (var))
293 if (dump_file && (dump_flags & TDF_DETAILS))
295 fprintf (dump_file, "Cannot scalarize variable ");
296 print_generic_expr (dump_file, var, dump_flags);
297 fprintf (dump_file, " because it must live in memory\n");
302 if (TREE_THIS_VOLATILE (var))
304 if (dump_file && (dump_flags & TDF_DETAILS))
306 fprintf (dump_file, "Cannot scalarize variable ");
307 print_generic_expr (dump_file, var, dump_flags);
308 fprintf (dump_file, " because it is declared volatile\n");
313 /* Any COMPLEX_TYPE that has reached this point can be scalarized. */
314 if (TREE_CODE (TREE_TYPE (var)) == COMPLEX_TYPE)
317 type = TREE_TYPE (var);
319 for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
321 if (TREE_CODE (field) != FIELD_DECL)
324 /* FIXME: We really should recurse down the type hierarchy and
325 scalarize the fields at the leaves. */
326 if (AGGREGATE_TYPE_P (TREE_TYPE (field)))
328 if (dump_file && (dump_flags & TDF_DETAILS))
330 fprintf (dump_file, "Cannot scalarize variable ");
331 print_generic_expr (dump_file, var, dump_flags);
333 " because it contains an aggregate type field, ");
334 print_generic_expr (dump_file, field, dump_flags);
335 fprintf (dump_file, "\n");
340 /* FIXME: Similarly. Indeed, considering that we treat complex
341 as an aggregate, this is exactly the same problem.
342 Structures with __complex__ fields are tested in the libstdc++
343 testsuite: 26_numerics/complex_inserters_extractors.cc. */
344 if (TREE_CODE (TREE_TYPE (field)) == COMPLEX_TYPE)
346 if (dump_file && (dump_flags & TDF_DETAILS))
348 fprintf (dump_file, "Cannot scalarize variable ");
349 print_generic_expr (dump_file, var, dump_flags);
351 " because it contains a __complex__ field, ");
352 print_generic_expr (dump_file, field, dump_flags);
353 fprintf (dump_file, "\n");
358 /* FIXME. We don't scalarize structures with bit fields yet. To
359 support this, we should make sure that all the fields fit in one
360 word and modify every operation done on the scalarized bit fields
361 to mask them properly. */
362 if (DECL_BIT_FIELD (field))
364 if (dump_file && (dump_flags & TDF_DETAILS))
366 fprintf (dump_file, "Cannot scalarize variable ");
367 print_generic_expr (dump_file, var, dump_flags);
369 " because it contains a bit-field, ");
370 print_generic_expr (dump_file, field, dump_flags);
371 fprintf (dump_file, "\n");
377 if (nfields > MAX_NFIELDS_FOR_SRA)
379 if (dump_file && (dump_flags & TDF_DETAILS))
381 fprintf (dump_file, "Cannot scalarize variable ");
382 print_generic_expr (dump_file, var, dump_flags);
384 " because it contains more than %d fields\n",
385 MAX_NFIELDS_FOR_SRA);
391 /* If the structure had no FIELD_DECLs, then don't bother
397 /* Replace the COMPONENT_REF, REALPART_EXPR or IMAGPART_EXPR pointed-to by
398 TP inside STMT with the corresponding scalar replacement from SRA_MAP. */
401 scalarize_component_ref (tree stmt, tree *tp)
403 tree t = *tp, obj = TREE_OPERAND (t, 0);
405 /* When scalarizing a function argument, we will need to insert copy-in
406 operations from the original PARM_DECLs. Note that these copy-in
407 operations may end up being dead, but we won't know until we rename
408 the new variables into SSA. */
409 if (TREE_CODE (obj) == PARM_DECL)
410 bitmap_set_bit (needs_copy_in, var_ann (obj)->uid);
412 switch (TREE_CODE (t))
415 t = get_scalar_for_field (obj, TREE_OPERAND (t, 1));
419 t = get_scalar_for_complex_part (obj, TREE_CODE (t));
430 /* Scalarize the structure assignment for the statement pointed by SI_P. */
433 scalarize_structure_assignment (block_stmt_iterator *si_p)
435 var_ann_t lhs_ann, rhs_ann;
436 tree lhs, rhs, list, orig_stmt;
437 bool lhs_can, rhs_can;
439 orig_stmt = bsi_stmt (*si_p);
440 lhs = TREE_OPERAND (orig_stmt, 0);
441 rhs = TREE_OPERAND (orig_stmt, 1);
444 #if defined ENABLE_CHECKING
445 if (TREE_CODE (orig_stmt) != MODIFY_EXPR)
449 /* Remove all type casts from RHS. This may seem heavy handed but
450 it's actually safe and it is necessary in the presence of C++
451 reinterpret_cast<> where structure assignments of different
452 structures will be present in the IL. This was the case of PR
453 13347 (http://gcc.gnu.org/bugzilla/show_bug.cgi?id=13347) which
454 had something like this:
460 Both 'f' and 'g' were scalarizable, but the presence of the type
461 cast was causing SRA to not replace the RHS of the assignment
462 with g's scalar replacements. Furthermore, the fact that this
463 assignment reached this point without causing syntax errors means
464 that the type cast is safe and that a field-by-field assignment
465 from 'g' into 'f' is the right thing to do. */
468 lhs_ann = DECL_P (lhs) ? var_ann (lhs) : NULL;
469 rhs_ann = DECL_P (rhs) ? var_ann (rhs) : NULL;
471 #if defined ENABLE_CHECKING
472 /* Two different variables should not have the same UID. */
476 && lhs_ann->uid == rhs_ann->uid)
480 lhs_can = lhs_ann && bitmap_bit_p (sra_candidates, lhs_ann->uid);
481 rhs_can = rhs_ann && bitmap_bit_p (sra_candidates, rhs_ann->uid);
483 /* Both LHS and RHS are scalarizable. */
484 if (lhs_can && rhs_can)
485 list = create_scalar_copies (lhs, rhs, SCALAR_SCALAR);
487 /* Only RHS is scalarizable. */
489 list = create_scalar_copies (lhs, rhs, FIELD_SCALAR);
491 /* Only LHS is scalarizable. */
493 list = create_scalar_copies (lhs, rhs, SCALAR_FIELD);
495 /* If neither side is scalarizable, do nothing else. */
499 /* Set line number information for our replacements. */
500 if (EXPR_HAS_LOCATION (orig_stmt))
501 annotate_all_with_locus (&list, EXPR_LOCATION (orig_stmt));
503 /* Replace the existing statement with the newly created list of
504 scalarized copies. When replacing the original statement, the first
505 copy replaces it and the remaining copies are inserted either after
506 the first copy or on the outgoing edges of the original statement's
509 tree_stmt_iterator tsi = tsi_start (list);
510 bsi_replace (si_p, tsi_stmt (tsi), true);
512 if (stmt_ends_bb_p (orig_stmt))
513 insert_edge_copies (list, bb_for_stmt (orig_stmt));
515 bsi_insert_after (si_p, list, BSI_CONTINUE_LINKING);
520 /* Traverse all the referenced variables in the program looking for
521 structures that could be replaced with scalars. */
524 find_candidates_for_sra (void)
527 bool any_set = false;
529 for (i = 0; i < num_referenced_vars; i++)
531 tree var = referenced_var (i);
533 if ((TREE_CODE (TREE_TYPE (var)) == RECORD_TYPE
534 || TREE_CODE (TREE_TYPE (var)) == COMPLEX_TYPE)
535 && can_be_scalarized_p (var))
537 bitmap_set_bit (sra_candidates, var_ann (var)->uid);
546 /* Insert STMT on all the outgoing edges out of BB. Note that if BB
547 has more than one edge, STMT will be replicated for each edge. Also,
548 abnormal edges will be ignored. */
551 insert_edge_copies (tree stmt, basic_block bb)
557 for (e = bb->succ; e; e = e->succ_next)
559 /* We don't need to insert copies on abnormal edges. The
560 value of the scalar replacement is not guaranteed to
561 be valid through an abnormal edge. */
562 if (!(e->flags & EDGE_ABNORMAL))
566 bsi_insert_on_edge (e, stmt);
570 bsi_insert_on_edge (e, lhd_unsave_expr_now (stmt));
576 /* Append a new assignment statement to TSI. */
579 csc_assign (tree_stmt_iterator *tsi, tree lhs, tree rhs)
581 tree stmt = build (MODIFY_EXPR, TREE_TYPE (lhs), lhs, rhs);
583 tsi_link_after (tsi, stmt, TSI_NEW_STMT);
587 /* A subroutine of create_scalar_copies. Construct a COMPONENT_REF
588 expression for BASE referencing FIELD. INDEX is the field index. */
591 csc_build_component_ref (tree base, tree field)
593 switch (TREE_CODE (base))
596 /* Only appears on RHS. The only remaining CONSTRUCTORS for
597 record types that should remain are empty, and imply that
598 the entire structure should be zeroed. */
599 if (CONSTRUCTOR_ELTS (base))
601 return convert (TREE_TYPE (field), integer_zero_node);
604 /* Avoid sharing BASE when building the different COMPONENT_REFs.
605 We let the first field have the original version. */
606 if (field != TYPE_FIELDS (TREE_TYPE (base)))
607 base = unshare_expr (base);
612 /* Special case for the above -- decls are always shared. */
616 return build (COMPONENT_REF, TREE_TYPE (field), base, field);
619 /* Similarly for REALPART_EXPR and IMAGPART_EXPR for complex types. */
622 csc_build_complex_part (tree base, enum tree_code part)
624 switch (TREE_CODE (base))
627 if (part == REALPART_EXPR)
628 return TREE_REALPART (base);
630 return TREE_IMAGPART (base);
633 if (part == REALPART_EXPR)
634 return TREE_OPERAND (base, 0);
636 return TREE_OPERAND (base, 1);
639 /* Avoid sharing BASE when building the different references.
640 We let the real part have the original version. */
641 if (part != REALPART_EXPR)
642 base = unshare_expr (base);
647 /* Special case for the above -- decls are always shared. */
651 return build1 (part, TREE_TYPE (TREE_TYPE (base)), base);
654 /* Create and return a list of assignments to perform a scalarized
655 structure assignment 'LHS = RHS'. Both LHS and RHS are assumed to be
656 of an aggregate or complex type. Three types of copies may be specified:
658 SCALAR_SCALAR will emit assignments for all the scalar temporaries
659 corresponding to the fields of LHS and RHS.
661 FIELD_SCALAR will emit assignments from the scalar replacements of
662 RHS into each of the fields of the LHS.
664 SCALAR_FIELD will emit assignments from each field of the RHS into
665 the scalar replacements of the LHS. */
668 create_scalar_copies (tree lhs, tree rhs, enum sra_copy_mode mode)
671 tree_stmt_iterator tsi;
673 #if defined ENABLE_CHECKING
674 /* Sanity checking. Check that we are not trying to scalarize a
676 if (!DECL_P (lhs) && (mode == SCALAR_FIELD || mode == SCALAR_SCALAR))
678 if (!DECL_P (rhs) && (mode == FIELD_SCALAR || mode == SCALAR_SCALAR))
682 type = TREE_TYPE (lhs);
683 list = alloc_stmt_list ();
684 tsi = tsi_start (list);
686 /* VA_ARG_EXPRs have side effects, so we need to copy it first to a
687 temporary before scalarizing. FIXME: This should disappear once
688 VA_ARG_EXPRs are properly lowered. */
689 if (TREE_CODE (rhs) == VA_ARG_EXPR)
693 /* Add TMP = VA_ARG_EXPR <> */
694 tmp = make_temp (TREE_TYPE (rhs), NULL);
695 stmt = csc_assign (&tsi, tmp, rhs);
697 /* Mark all the variables in VDEF operands for renaming, because
698 the VA_ARG_EXPR will now be in a different statement. */
699 mark_all_vdefs (stmt);
701 /* Set RHS to be the new temporary TMP. */
705 /* When making *_SCALAR copies from PARM_DECLs, we will need to insert
706 copy-in operations from the original PARM_DECLs. Note that these
707 copy-in operations may end up being dead, but we won't know until
708 we rename the new variables into SSA. */
709 if ((mode == SCALAR_SCALAR || mode == FIELD_SCALAR)
710 && TREE_CODE (rhs) == PARM_DECL)
711 bitmap_set_bit (needs_copy_in, var_ann (rhs)->uid);
713 /* Now create scalar copies for each individual field according to MODE. */
714 if (TREE_CODE (type) == COMPLEX_TYPE)
716 /* Create scalar copies of both the real and imaginary parts. */
717 tree real_lhs, real_rhs, imag_lhs, imag_rhs;
719 if (mode == SCALAR_FIELD)
721 real_rhs = csc_build_complex_part (rhs, REALPART_EXPR);
722 imag_rhs = csc_build_complex_part (rhs, IMAGPART_EXPR);
726 real_rhs = get_scalar_for_complex_part (rhs, REALPART_EXPR);
727 imag_rhs = get_scalar_for_complex_part (rhs, IMAGPART_EXPR);
730 if (mode == FIELD_SCALAR)
732 /* In this case we do not need to create but one statement,
733 since we can create a new complex value whole. */
735 if (TREE_CONSTANT (real_rhs) && TREE_CONSTANT (imag_rhs))
736 rhs = build_complex (type, real_rhs, imag_rhs);
738 rhs = build (COMPLEX_EXPR, type, real_rhs, imag_rhs);
739 csc_assign (&tsi, lhs, rhs);
743 real_lhs = get_scalar_for_complex_part (lhs, REALPART_EXPR);
744 imag_lhs = get_scalar_for_complex_part (lhs, IMAGPART_EXPR);
746 csc_assign (&tsi, real_lhs, real_rhs);
747 csc_assign (&tsi, imag_lhs, imag_rhs);
754 /* ??? C++ generates copies between different pointer-to-member
755 structures of different types. To combat this, we must track
756 the field of both the left and right structures, so that we
757 index the variables with fields of their own type. */
759 for (lf = TYPE_FIELDS (type), rf = TYPE_FIELDS (TREE_TYPE (rhs));
761 lf = TREE_CHAIN (lf), rf = TREE_CHAIN (rf))
763 tree lhs_var, rhs_var;
765 /* Only copy FIELD_DECLs. */
766 if (TREE_CODE (lf) != FIELD_DECL)
769 if (mode == FIELD_SCALAR)
770 lhs_var = csc_build_component_ref (lhs, lf);
772 lhs_var = get_scalar_for_field (lhs, lf);
774 if (mode == SCALAR_FIELD)
775 rhs_var = csc_build_component_ref (rhs, rf);
777 rhs_var = get_scalar_for_field (rhs, rf);
779 csc_assign (&tsi, lhs_var, rhs_var);
783 /* All the scalar copies just created will either create new definitions
784 or remove existing definitions of LHS, so we need to mark it for
786 if (TREE_SIDE_EFFECTS (list))
788 if (mode == SCALAR_FIELD || mode == SCALAR_SCALAR)
790 /* If the LHS has been scalarized, mark it for renaming. */
791 bitmap_set_bit (vars_to_rename, var_ann (lhs)->uid);
793 else if (mode == FIELD_SCALAR)
795 /* Otherwise, mark all the symbols in the VDEFs for the last
796 scalarized statement just created. Since all the statements
797 introduce the same VDEFs, we only need to check the last one. */
798 mark_all_vdefs (tsi_stmt (tsi));
807 /* A helper function that creates the copies, updates line info,
808 and emits the code either before or after BSI. */
811 emit_scalar_copies (block_stmt_iterator *bsi, tree lhs, tree rhs,
812 enum sra_copy_mode mode)
814 tree list = create_scalar_copies (lhs, rhs, mode);
815 tree stmt = bsi_stmt (*bsi);
817 if (EXPR_HAS_LOCATION (stmt))
818 annotate_all_with_locus (&list, EXPR_LOCATION (stmt));
820 bsi_insert_before (bsi, list, BSI_SAME_STMT);
823 /* Traverse all the statements in the function replacing references to
824 scalarizable structures with their corresponding scalar temporaries. */
827 scalarize_structures (void)
830 block_stmt_iterator si;
834 for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
839 stmt = bsi_stmt (si);
840 ann = stmt_ann (stmt);
842 /* If the statement has no virtual operands, then it doesn't make
843 structure references that we care about. */
844 if (NUM_VDEFS (VDEF_OPS (ann)) == 0
845 && NUM_VUSES (VUSE_OPS (ann)) == 0)
848 /* Structure references may only appear in certain statements. */
849 if (TREE_CODE (stmt) != MODIFY_EXPR
850 && TREE_CODE (stmt) != CALL_EXPR
851 && TREE_CODE (stmt) != RETURN_EXPR
852 && TREE_CODE (stmt) != ASM_EXPR)
855 scalarize_stmt (&si);
858 /* Initialize the scalar replacements for every structure that is a
859 function argument. */
860 EXECUTE_IF_SET_IN_BITMAP (needs_copy_in, 0, i,
862 tree var = referenced_var (i);
863 tree list = create_scalar_copies (var, var, SCALAR_FIELD);
864 bsi_insert_on_edge (ENTRY_BLOCK_PTR->succ, list);
867 /* Commit edge insertions. */
868 bsi_commit_edge_inserts (NULL);
872 /* Scalarize structure references in the statement pointed by SI_P. */
875 scalarize_stmt (block_stmt_iterator *si_p)
877 tree stmt = bsi_stmt (*si_p);
879 /* Handle assignments. */
880 if (TREE_CODE (stmt) == MODIFY_EXPR
881 && TREE_CODE (TREE_OPERAND (stmt, 1)) != CALL_EXPR)
882 scalarize_modify_expr (si_p);
884 /* Handle RETURN_EXPR. */
885 else if (TREE_CODE (stmt) == RETURN_EXPR)
886 scalarize_return_expr (si_p);
888 /* Handle function calls (note that this must be handled after
889 MODIFY_EXPR and RETURN_EXPR because a function call can appear in
891 else if (get_call_expr_in (stmt) != NULL_TREE)
892 scalarize_call_expr (si_p);
894 /* Handle ASM_EXPRs. */
895 else if (TREE_CODE (stmt) == ASM_EXPR)
896 scalarize_asm_expr (si_p);
900 /* Helper for scalarize_stmt to handle assignments. */
903 scalarize_modify_expr (block_stmt_iterator *si_p)
905 tree stmt = bsi_stmt (*si_p);
906 tree lhs = TREE_OPERAND (stmt, 0);
907 tree rhs = TREE_OPERAND (stmt, 1);
909 /* Found AGGREGATE.FIELD = ... */
910 if (is_sra_candidate_ref (lhs, false))
915 scalarize_component_ref (stmt, &TREE_OPERAND (stmt, 0));
917 /* Mark the LHS to be renamed, as we have just removed the previous
918 VDEF for AGGREGATE. The statement should have exactly one VDEF
919 for variable AGGREGATE. */
920 vdefs = STMT_VDEF_OPS (stmt);
921 if (NUM_VDEFS (vdefs) != 1)
923 sym = SSA_NAME_VAR (VDEF_RESULT (vdefs, 0));
924 bitmap_set_bit (vars_to_rename, var_ann (sym)->uid);
927 /* Found ... = AGGREGATE.FIELD */
928 else if (is_sra_candidate_ref (rhs, false))
929 scalarize_component_ref (stmt, &TREE_OPERAND (stmt, 1));
931 /* Found ... = BIT_FIELD_REF <>. This is similar to a CALL_EXPR, if the
932 operand of the BIT_FIELD_REF is a scalarizable structure, we need to
933 copy from its scalar replacements before doing the bitfield operation.
935 FIXME: BIT_FIELD_REFs are often generated by fold-const.c. This is
936 not always desirable because they obfuscate the original predicates,
937 limiting what the tree optimizers may do. For instance, in
938 testsuite/g++.dg/opt/nrv4.C the use of SRA allows the optimizers to
939 optimize function main() to 'return 0;'. However, the folder
940 generates a BIT_FIELD_REF operation for one of the comparisons,
941 preventing the optimizers from removing all the redundant
943 else if (is_sra_candidate_ref (rhs, true))
945 tree var = TREE_OPERAND (rhs, 0);
946 emit_scalar_copies (si_p, var, var, FIELD_SCALAR);
949 /* Found AGGREGATE = ... or ... = AGGREGATE */
950 else if (DECL_P (lhs) || DECL_P (rhs))
951 scalarize_structure_assignment (si_p);
955 /* Scalarize structure references in LIST. Use DONE to avoid duplicates. */
958 scalarize_tree_list (tree list, block_stmt_iterator *si_p, bitmap done)
962 for (op = list; op; op = TREE_CHAIN (op))
964 tree arg = TREE_VALUE (op);
966 if (is_sra_candidate_decl (arg))
968 int index = var_ann (arg)->uid;
969 if (!bitmap_bit_p (done, index))
971 emit_scalar_copies (si_p, arg, arg, FIELD_SCALAR);
972 bitmap_set_bit (done, index);
975 else if (is_sra_candidate_ref (arg, false))
977 tree stmt = bsi_stmt (*si_p);
978 scalarize_component_ref (stmt, &TREE_VALUE (op));
984 /* Helper for scalarize_stmt to handle function calls. */
987 scalarize_call_expr (block_stmt_iterator *si_p)
989 tree stmt = bsi_stmt (*si_p);
990 tree call = (TREE_CODE (stmt) == MODIFY_EXPR) ? TREE_OPERAND (stmt, 1) : stmt;
991 struct bitmap_head_def done_head;
993 /* First scalarize the arguments. Order is important, because the copy
994 operations for the arguments need to go before the call.
995 Scalarization of the return value needs to go after the call. */
996 bitmap_initialize (&done_head, 1);
997 scalarize_tree_list (TREE_OPERAND (call, 1), si_p, &done_head);
998 bitmap_clear (&done_head);
1000 /* Scalarize the return value, if any. */
1001 if (TREE_CODE (stmt) == MODIFY_EXPR)
1003 tree var = TREE_OPERAND (stmt, 0);
1005 /* If the LHS of the assignment is a scalarizable structure, insert
1006 copies into the scalar replacements after the call. */
1007 if (is_sra_candidate_decl (var))
1009 tree list = create_scalar_copies (var, var, SCALAR_FIELD);
1010 if (EXPR_HAS_LOCATION (stmt))
1011 annotate_all_with_locus (&list, EXPR_LOCATION (stmt));
1012 if (stmt_ends_bb_p (stmt))
1013 insert_edge_copies (list, bb_for_stmt (stmt));
1015 bsi_insert_after (si_p, list, BSI_NEW_STMT);
1021 /* Helper for scalarize_stmt to handle ASM_EXPRs. */
1024 scalarize_asm_expr (block_stmt_iterator *si_p)
1026 tree stmt = bsi_stmt (*si_p);
1027 struct bitmap_head_def done_head;
1029 bitmap_initialize (&done_head, 1);
1030 scalarize_tree_list (ASM_INPUTS (stmt), si_p, &done_head);
1031 scalarize_tree_list (ASM_OUTPUTS (stmt), si_p, &done_head);
1032 bitmap_clear (&done_head);
1034 /* ??? Process outputs after the asm. */
1038 /* Helper for scalarize_stmt to handle return expressions. */
1041 scalarize_return_expr (block_stmt_iterator *si_p)
1043 tree stmt = bsi_stmt (*si_p);
1044 tree op = TREE_OPERAND (stmt, 0);
1046 if (op == NULL_TREE)
1049 /* Handle a bare RESULT_DECL. This will handle for types needed
1050 constructors, or possibly after NRV type optimizations. */
1051 if (is_sra_candidate_decl (op))
1052 emit_scalar_copies (si_p, op, op, FIELD_SCALAR);
1053 else if (TREE_CODE (op) == MODIFY_EXPR)
1055 tree *rhs_p = &TREE_OPERAND (op, 1);
1058 /* Handle 'return STRUCTURE;' */
1059 if (is_sra_candidate_decl (rhs))
1060 emit_scalar_copies (si_p, rhs, rhs, FIELD_SCALAR);
1062 /* Handle 'return STRUCTURE.FIELD;' */
1063 else if (is_sra_candidate_ref (rhs, false))
1064 scalarize_component_ref (stmt, rhs_p);
1066 /* Handle 'return CALL_EXPR;' */
1067 else if (TREE_CODE (rhs) == CALL_EXPR)
1069 struct bitmap_head_def done_head;
1070 bitmap_initialize (&done_head, 1);
1071 scalarize_tree_list (TREE_OPERAND (rhs, 1), si_p, &done_head);
1072 bitmap_clear (&done_head);
1078 /* Debugging dump for the scalar replacement map. */
1081 dump_sra_map_trav (void **slot, void *data)
1083 struct sra_elt *e = *slot;
1089 fputs ("__real__ ", f);
1090 print_generic_expr (dump_file, e->base, dump_flags);
1091 fprintf (f, " -> %s\n", get_name (e->replace));
1094 fputs ("__imag__ ", f);
1095 print_generic_expr (dump_file, e->base, dump_flags);
1096 fprintf (f, " -> %s\n", get_name (e->replace));
1099 print_generic_expr (dump_file, e->base, dump_flags);
1100 fprintf (f, ".%s -> %s\n", get_name (e->field), get_name (e->replace));
1110 dump_sra_map (FILE *f)
1112 fputs ("Scalar replacements:\n", f);
1113 htab_traverse_noresize (sra_map, dump_sra_map_trav, f);
1117 /* Main entry point to Scalar Replacement of Aggregates (SRA). This pass
1118 re-writes non-aliased structure references into scalar temporaries. The
1119 goal is to expose some/all structures to the scalar optimizers.
1121 FNDECL is the function to process.
1123 VARS_TO_RENAME_P is a pointer to the set of variables that need to be
1124 renamed into SSA after this pass is done. These are going to be all the
1125 new scalars created by the SRA process. Notice that since this pass
1126 creates new variables, the bitmap representing all the variables in the
1127 program will be re-sized here.
1129 PHASE indicates which dump file from the DUMP_FILES array to use when
1130 dumping debugging information.
1134 1- Scalarize COMPLEX_TYPEs
1135 2- Scalarize ARRAY_REFs that are always referenced with a
1137 3- Timings to determine when scalarization is not profitable.
1138 4- Determine what's a good value for MAX_NFIELDS_FOR_SRA. */
1143 /* Initialize local variables. */
1144 sra_candidates = BITMAP_XMALLOC ();
1146 needs_copy_in = NULL;
1148 /* Find structures to be scalarized. */
1149 if (!find_candidates_for_sra ())
1151 BITMAP_XFREE (sra_candidates);
1155 /* If we found any, re-write structure references with their
1156 corresponding scalar replacement. */
1157 sra_map = htab_create (101, sra_elt_hash, sra_elt_eq, free);
1158 needs_copy_in = BITMAP_XMALLOC ();
1160 scalarize_structures ();
1163 dump_sra_map (dump_file);
1165 /* Free allocated memory. */
1166 htab_delete (sra_map);
1168 BITMAP_XFREE (needs_copy_in);
1169 BITMAP_XFREE (sra_candidates);
1175 return flag_tree_sra != 0;
1178 struct tree_opt_pass pass_sra =
1181 gate_sra, /* gate */
1182 tree_sra, /* execute */
1185 0, /* static_pass_number */
1186 TV_TREE_SRA, /* tv_id */
1187 PROP_cfg | PROP_ssa, /* properties_required */
1188 0, /* properties_provided */
1189 0, /* properties_destroyed */
1190 0, /* todo_flags_start */
1191 TODO_dump_func | TODO_rename_vars
1192 | TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */