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-gimple.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 tree create_scalar_copies (tree lhs, tree rhs, enum sra_copy_mode mode);
60 static inline void scalarize_component_ref (tree, tree *tp);
61 static void scalarize_structures (void);
62 static void scalarize_stmt (block_stmt_iterator *);
63 static void scalarize_modify_expr (block_stmt_iterator *);
64 static void scalarize_call_expr (block_stmt_iterator *);
65 static void scalarize_asm_expr (block_stmt_iterator *);
66 static void scalarize_return_expr (block_stmt_iterator *);
68 /* The set of aggregate variables that are candidates for scalarization. */
69 static bitmap sra_candidates;
71 /* Set of scalarizable PARM_DECLs that need copy-in operations at the
72 beginning of the function. */
73 static bitmap needs_copy_in;
75 /* This structure holds the mapping between and element of an aggregate
76 and the scalar replacement variable. */
85 static htab_t sra_map;
88 sra_elt_hash (const void *x)
90 const struct sra_elt *e = x;
91 hashval_t h = (size_t) e->base * e->kind;
92 if (e->kind == COMPONENT_REF)
93 h ^= (size_t) e->field;
98 sra_elt_eq (const void *x, const void *y)
100 const struct sra_elt *a = x;
101 const struct sra_elt *b = y;
103 if (a->kind != b->kind)
105 if (a->base != b->base)
107 if (a->kind == COMPONENT_REF)
108 if (a->field != b->field)
114 /* Mark all the variables in V_MAY_DEF operands for STMT for renaming.
115 This becomes necessary when we modify all of a non-scalar. */
118 mark_all_v_may_defs (tree stmt)
120 v_may_def_optype v_may_defs;
123 get_stmt_operands (stmt);
124 v_may_defs = V_MAY_DEF_OPS (stmt_ann (stmt));
125 n = NUM_V_MAY_DEFS (v_may_defs);
127 for (i = 0; i < n; i++)
129 tree sym = V_MAY_DEF_RESULT (v_may_defs, i);
130 bitmap_set_bit (vars_to_rename, var_ann (sym)->uid);
134 /* Mark all the variables in V_MUST_DEF operands for STMT for renaming.
135 This becomes necessary when we modify all of a non-scalar. */
138 mark_all_v_must_defs (tree stmt)
140 v_must_def_optype v_must_defs;
143 get_stmt_operands (stmt);
144 v_must_defs = V_MUST_DEF_OPS (stmt_ann (stmt));
145 n = NUM_V_MUST_DEFS (v_must_defs);
147 for (i = 0; i < n; i++)
149 tree sym = V_MUST_DEF_OP (v_must_defs, i);
150 bitmap_set_bit (vars_to_rename, var_ann (sym)->uid);
154 /* Return true if DECL is an SRA candidate. */
157 is_sra_candidate_decl (tree decl)
159 return DECL_P (decl) && bitmap_bit_p (sra_candidates, var_ann (decl)->uid);
162 /* Return true if EXP is of the form <ref decl>, where REF is one of the
163 field access references we handle and DECL is an SRA candidate.
165 Set ALLOW_BIT_FIELD_REF to accept BIT_FIELD_REF as well. This is
166 normally false, except when we're trying to work around it. */
169 is_sra_candidate_ref (tree exp, bool allow_bit_field_ref)
171 switch (TREE_CODE (exp))
174 if (!allow_bit_field_ref)
181 return is_sra_candidate_decl (TREE_OPERAND (exp, 0));
190 /* Return the scalar in SRA_MAP[VAR_IX][FIELD_IX]. If none exists, create
191 a new scalar with type TYPE. */
194 lookup_scalar (struct sra_elt *key, tree type)
196 struct sra_elt **slot, *res;
198 slot = (struct sra_elt **) htab_find_slot (sra_map, key, INSERT);
202 res = xmalloc (sizeof (*res));
205 res->replace = make_rename_temp (type, "SR");
207 if (DECL_NAME (key->base) && !DECL_IGNORED_P (key->base))
213 if (!DECL_NAME (key->field))
215 name = concat (IDENTIFIER_POINTER (DECL_NAME (key->base)),
217 IDENTIFIER_POINTER (DECL_NAME (key->field)),
221 name = concat (IDENTIFIER_POINTER (DECL_NAME (key->base)),
225 name = concat (IDENTIFIER_POINTER (DECL_NAME (key->base)),
233 DECL_NAME (res->replace) = get_identifier (name);
238 DECL_SOURCE_LOCATION (res->replace) = DECL_SOURCE_LOCATION (key->base);
239 TREE_NO_WARNING (res->replace) = TREE_NO_WARNING (key->base);
240 DECL_ARTIFICIAL (res->replace) = DECL_ARTIFICIAL (key->base);
247 /* Given a structure reference VAR.FIELD, return a scalar representing it.
248 If no scalar is found, a new one is created and added to the SRA_MAP
252 get_scalar_for_field (tree var, tree field)
256 #ifdef ENABLE_CHECKING
257 /* Validate that FIELD actually exists in VAR's type. */
260 for (f = TYPE_FIELDS (TREE_TYPE (var)); f ; f = TREE_CHAIN (f))
268 key.kind = COMPONENT_REF;
272 return lookup_scalar (&key, TREE_TYPE (field));
276 /* Similarly for the parts of a complex type. */
279 get_scalar_for_complex_part (tree var, enum tree_code part)
286 return lookup_scalar (&key, TREE_TYPE (TREE_TYPE (var)));
289 /* Return true if the fields of VAR can be replaced by scalar temporaries.
290 This only happens if VAR is not call-clobbered and it contains less
291 than MAX_NFIELDS_FOR_SRA scalar fields. */
294 can_be_scalarized_p (tree var)
299 if (!is_gimple_non_addressable (var))
301 if (dump_file && (dump_flags & TDF_DETAILS))
303 fprintf (dump_file, "Cannot scalarize variable ");
304 print_generic_expr (dump_file, var, dump_flags);
305 fprintf (dump_file, " because it must live in memory\n");
310 if (TREE_THIS_VOLATILE (var))
312 if (dump_file && (dump_flags & TDF_DETAILS))
314 fprintf (dump_file, "Cannot scalarize variable ");
315 print_generic_expr (dump_file, var, dump_flags);
316 fprintf (dump_file, " because it is declared volatile\n");
321 /* Any COMPLEX_TYPE that has reached this point can be scalarized. */
322 if (TREE_CODE (TREE_TYPE (var)) == COMPLEX_TYPE)
325 type = TREE_TYPE (var);
327 for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
329 if (TREE_CODE (field) != FIELD_DECL)
332 /* FIXME: We really should recurse down the type hierarchy and
333 scalarize the fields at the leaves. */
334 if (AGGREGATE_TYPE_P (TREE_TYPE (field)))
336 if (dump_file && (dump_flags & TDF_DETAILS))
338 fprintf (dump_file, "Cannot scalarize variable ");
339 print_generic_expr (dump_file, var, dump_flags);
341 " because it contains an aggregate type field, ");
342 print_generic_expr (dump_file, field, dump_flags);
343 fprintf (dump_file, "\n");
348 /* FIXME: Similarly. Indeed, considering that we treat complex
349 as an aggregate, this is exactly the same problem.
350 Structures with __complex__ fields are tested in the libstdc++
351 testsuite: 26_numerics/complex_inserters_extractors.cc. */
352 if (TREE_CODE (TREE_TYPE (field)) == COMPLEX_TYPE)
354 if (dump_file && (dump_flags & TDF_DETAILS))
356 fprintf (dump_file, "Cannot scalarize variable ");
357 print_generic_expr (dump_file, var, dump_flags);
359 " because it contains a __complex__ field, ");
360 print_generic_expr (dump_file, field, dump_flags);
361 fprintf (dump_file, "\n");
366 /* FIXME. We don't scalarize structures with bit fields yet. To
367 support this, we should make sure that all the fields fit in one
368 word and modify every operation done on the scalarized bit fields
369 to mask them properly. */
370 if (DECL_BIT_FIELD (field))
372 if (dump_file && (dump_flags & TDF_DETAILS))
374 fprintf (dump_file, "Cannot scalarize variable ");
375 print_generic_expr (dump_file, var, dump_flags);
377 " because it contains a bit-field, ");
378 print_generic_expr (dump_file, field, dump_flags);
379 fprintf (dump_file, "\n");
385 if (nfields > MAX_NFIELDS_FOR_SRA)
387 if (dump_file && (dump_flags & TDF_DETAILS))
389 fprintf (dump_file, "Cannot scalarize variable ");
390 print_generic_expr (dump_file, var, dump_flags);
392 " because it contains more than %d fields\n",
393 MAX_NFIELDS_FOR_SRA);
399 /* If the structure had no FIELD_DECLs, then don't bother
405 /* Replace the COMPONENT_REF, REALPART_EXPR or IMAGPART_EXPR pointed-to by
406 TP inside STMT with the corresponding scalar replacement from SRA_MAP. */
409 scalarize_component_ref (tree stmt, tree *tp)
411 tree t = *tp, obj = TREE_OPERAND (t, 0);
413 /* When scalarizing a function argument, we will need to insert copy-in
414 operations from the original PARM_DECLs. Note that these copy-in
415 operations may end up being dead, but we won't know until we rename
416 the new variables into SSA. */
417 if (TREE_CODE (obj) == PARM_DECL)
418 bitmap_set_bit (needs_copy_in, var_ann (obj)->uid);
420 switch (TREE_CODE (t))
423 t = get_scalar_for_field (obj, TREE_OPERAND (t, 1));
427 t = get_scalar_for_complex_part (obj, TREE_CODE (t));
438 /* Scalarize the structure assignment for the statement pointed by SI_P. */
441 scalarize_structure_assignment (block_stmt_iterator *si_p)
443 var_ann_t lhs_ann, rhs_ann;
444 tree lhs, rhs, list, orig_stmt;
445 bool lhs_can, rhs_can;
447 orig_stmt = bsi_stmt (*si_p);
448 lhs = TREE_OPERAND (orig_stmt, 0);
449 rhs = TREE_OPERAND (orig_stmt, 1);
452 #if defined ENABLE_CHECKING
453 if (TREE_CODE (orig_stmt) != MODIFY_EXPR)
457 /* Remove all type casts from RHS. This may seem heavy handed but
458 it's actually safe and it is necessary in the presence of C++
459 reinterpret_cast<> where structure assignments of different
460 structures will be present in the IL. This was the case of PR
461 13347 (http://gcc.gnu.org/bugzilla/show_bug.cgi?id=13347) which
462 had something like this:
468 Both 'f' and 'g' were scalarizable, but the presence of the type
469 cast was causing SRA to not replace the RHS of the assignment
470 with g's scalar replacements. Furthermore, the fact that this
471 assignment reached this point without causing syntax errors means
472 that the type cast is safe and that a field-by-field assignment
473 from 'g' into 'f' is the right thing to do. */
476 lhs_ann = DECL_P (lhs) ? var_ann (lhs) : NULL;
477 rhs_ann = DECL_P (rhs) ? var_ann (rhs) : NULL;
479 #if defined ENABLE_CHECKING
480 /* Two different variables should not have the same UID. */
484 && lhs_ann->uid == rhs_ann->uid)
488 lhs_can = lhs_ann && bitmap_bit_p (sra_candidates, lhs_ann->uid);
489 rhs_can = rhs_ann && bitmap_bit_p (sra_candidates, rhs_ann->uid);
491 /* Both LHS and RHS are scalarizable. */
492 if (lhs_can && rhs_can)
493 list = create_scalar_copies (lhs, rhs, SCALAR_SCALAR);
495 /* Only RHS is scalarizable. */
497 list = create_scalar_copies (lhs, rhs, FIELD_SCALAR);
499 /* Only LHS is scalarizable. */
501 list = create_scalar_copies (lhs, rhs, SCALAR_FIELD);
503 /* If neither side is scalarizable, do nothing else. */
507 /* Set line number information for our replacements. */
508 if (EXPR_HAS_LOCATION (orig_stmt))
509 annotate_all_with_locus (&list, EXPR_LOCATION (orig_stmt));
511 /* Replace the existing statement with the newly created list of
512 scalarized copies. When replacing the original statement, the first
513 copy replaces it and the remaining copies are inserted either after
514 the first copy or on the outgoing edges of the original statement's
517 tree_stmt_iterator tsi = tsi_start (list);
518 bsi_replace (si_p, tsi_stmt (tsi), true);
520 if (stmt_ends_bb_p (orig_stmt))
521 insert_edge_copies (list, bb_for_stmt (orig_stmt));
523 bsi_insert_after (si_p, list, BSI_CONTINUE_LINKING);
528 /* Traverse all the referenced variables in the program looking for
529 structures that could be replaced with scalars. */
532 find_candidates_for_sra (void)
535 bool any_set = false;
537 for (i = 0; i < num_referenced_vars; i++)
539 tree var = referenced_var (i);
541 if ((TREE_CODE (TREE_TYPE (var)) == RECORD_TYPE
542 || TREE_CODE (TREE_TYPE (var)) == COMPLEX_TYPE)
543 && can_be_scalarized_p (var))
545 bitmap_set_bit (sra_candidates, var_ann (var)->uid);
554 /* Insert STMT on all the outgoing edges out of BB. Note that if BB
555 has more than one edge, STMT will be replicated for each edge. Also,
556 abnormal edges will be ignored. */
559 insert_edge_copies (tree stmt, basic_block bb)
565 for (e = bb->succ; e; e = e->succ_next)
567 /* We don't need to insert copies on abnormal edges. The
568 value of the scalar replacement is not guaranteed to
569 be valid through an abnormal edge. */
570 if (!(e->flags & EDGE_ABNORMAL))
574 bsi_insert_on_edge (e, stmt);
578 bsi_insert_on_edge (e, lhd_unsave_expr_now (stmt));
584 /* Append a new assignment statement to TSI. */
587 csc_assign (tree_stmt_iterator *tsi, tree lhs, tree rhs)
589 tree stmt = build (MODIFY_EXPR, TREE_TYPE (lhs), lhs, rhs);
591 tsi_link_after (tsi, stmt, TSI_NEW_STMT);
595 /* A subroutine of create_scalar_copies. Construct a COMPONENT_REF
596 expression for BASE referencing FIELD. INDEX is the field index. */
599 csc_build_component_ref (tree base, tree field)
601 switch (TREE_CODE (base))
604 /* Only appears on RHS. The only remaining CONSTRUCTORS for
605 record types that should remain are empty, and imply that
606 the entire structure should be zeroed. */
607 if (CONSTRUCTOR_ELTS (base))
609 return fold_convert (TREE_TYPE (field), integer_zero_node);
612 /* Avoid sharing BASE when building the different COMPONENT_REFs.
613 We let the first field have the original version. */
614 if (field != TYPE_FIELDS (TREE_TYPE (base)))
615 base = unshare_expr (base);
620 /* Special case for the above -- decls are always shared. */
624 return build (COMPONENT_REF, TREE_TYPE (field), base, field);
627 /* Similarly for REALPART_EXPR and IMAGPART_EXPR for complex types. */
630 csc_build_complex_part (tree base, enum tree_code part)
632 switch (TREE_CODE (base))
635 if (part == REALPART_EXPR)
636 return TREE_REALPART (base);
638 return TREE_IMAGPART (base);
641 if (part == REALPART_EXPR)
642 return TREE_OPERAND (base, 0);
644 return TREE_OPERAND (base, 1);
647 /* Avoid sharing BASE when building the different references.
648 We let the real part have the original version. */
649 if (part != REALPART_EXPR)
650 base = unshare_expr (base);
655 /* Special case for the above -- decls are always shared. */
659 return build1 (part, TREE_TYPE (TREE_TYPE (base)), base);
662 /* Create and return a list of assignments to perform a scalarized
663 structure assignment 'LHS = RHS'. Both LHS and RHS are assumed to be
664 of an aggregate or complex type. Three types of copies may be specified:
666 SCALAR_SCALAR will emit assignments for all the scalar temporaries
667 corresponding to the fields of LHS and RHS.
669 FIELD_SCALAR will emit assignments from the scalar replacements of
670 RHS into each of the fields of the LHS.
672 SCALAR_FIELD will emit assignments from each field of the RHS into
673 the scalar replacements of the LHS. */
676 create_scalar_copies (tree lhs, tree rhs, enum sra_copy_mode mode)
679 tree_stmt_iterator tsi;
681 #if defined ENABLE_CHECKING
682 /* Sanity checking. Check that we are not trying to scalarize a
684 if (!DECL_P (lhs) && (mode == SCALAR_FIELD || mode == SCALAR_SCALAR))
686 if (!DECL_P (rhs) && (mode == FIELD_SCALAR || mode == SCALAR_SCALAR))
690 type = TREE_TYPE (lhs);
691 list = alloc_stmt_list ();
692 tsi = tsi_start (list);
694 /* VA_ARG_EXPRs have side effects, so we need to copy it first to a
695 temporary before scalarizing. FIXME: This should disappear once
696 VA_ARG_EXPRs are properly lowered. */
697 if (TREE_CODE (rhs) == VA_ARG_EXPR)
701 /* Add TMP = VA_ARG_EXPR <> */
702 tmp = make_rename_temp (TREE_TYPE (rhs), NULL);
703 stmt = csc_assign (&tsi, tmp, rhs);
705 /* Mark all the variables in VDEF operands for renaming, because
706 the VA_ARG_EXPR will now be in a different statement. */
707 mark_all_v_may_defs (stmt);
708 mark_all_v_must_defs (stmt);
710 /* Set RHS to be the new temporary TMP. */
714 /* When making *_SCALAR copies from PARM_DECLs, we will need to insert
715 copy-in operations from the original PARM_DECLs. Note that these
716 copy-in operations may end up being dead, but we won't know until
717 we rename the new variables into SSA. */
718 if ((mode == SCALAR_SCALAR || mode == FIELD_SCALAR)
719 && TREE_CODE (rhs) == PARM_DECL)
720 bitmap_set_bit (needs_copy_in, var_ann (rhs)->uid);
722 /* Now create scalar copies for each individual field according to MODE. */
723 if (TREE_CODE (type) == COMPLEX_TYPE)
725 /* Create scalar copies of both the real and imaginary parts. */
726 tree real_lhs, real_rhs, imag_lhs, imag_rhs;
728 if (mode == SCALAR_FIELD)
730 real_rhs = csc_build_complex_part (rhs, REALPART_EXPR);
731 imag_rhs = csc_build_complex_part (rhs, IMAGPART_EXPR);
735 real_rhs = get_scalar_for_complex_part (rhs, REALPART_EXPR);
736 imag_rhs = get_scalar_for_complex_part (rhs, IMAGPART_EXPR);
739 if (mode == FIELD_SCALAR)
741 /* In this case we do not need to create but one statement,
742 since we can create a new complex value whole. */
744 if (TREE_CONSTANT (real_rhs) && TREE_CONSTANT (imag_rhs))
745 rhs = build_complex (type, real_rhs, imag_rhs);
747 rhs = build (COMPLEX_EXPR, type, real_rhs, imag_rhs);
748 csc_assign (&tsi, lhs, rhs);
752 real_lhs = get_scalar_for_complex_part (lhs, REALPART_EXPR);
753 imag_lhs = get_scalar_for_complex_part (lhs, IMAGPART_EXPR);
755 csc_assign (&tsi, real_lhs, real_rhs);
756 csc_assign (&tsi, imag_lhs, imag_rhs);
763 /* ??? C++ generates copies between different pointer-to-member
764 structures of different types. To combat this, we must track
765 the field of both the left and right structures, so that we
766 index the variables with fields of their own type. */
768 for (lf = TYPE_FIELDS (type), rf = TYPE_FIELDS (TREE_TYPE (rhs));
770 lf = TREE_CHAIN (lf), rf = TREE_CHAIN (rf))
772 tree lhs_var, rhs_var;
774 /* Only copy FIELD_DECLs. */
775 if (TREE_CODE (lf) != FIELD_DECL)
778 if (mode == FIELD_SCALAR)
779 lhs_var = csc_build_component_ref (lhs, lf);
781 lhs_var = get_scalar_for_field (lhs, lf);
783 if (mode == SCALAR_FIELD)
784 rhs_var = csc_build_component_ref (rhs, rf);
786 rhs_var = get_scalar_for_field (rhs, rf);
788 csc_assign (&tsi, lhs_var, rhs_var);
792 /* All the scalar copies just created will either create new definitions
793 or remove existing definitions of LHS, so we need to mark it for
795 if (TREE_SIDE_EFFECTS (list))
797 if (mode == SCALAR_FIELD || mode == SCALAR_SCALAR)
799 /* If the LHS has been scalarized, mark it for renaming. */
800 bitmap_set_bit (vars_to_rename, var_ann (lhs)->uid);
802 else if (mode == FIELD_SCALAR)
804 /* Otherwise, mark all the symbols in the VDEFs for the last
805 scalarized statement just created. Since all the statements
806 introduce the same VDEFs, we only need to check the last one. */
807 mark_all_v_may_defs (tsi_stmt (tsi));
808 mark_all_v_must_defs (tsi_stmt (tsi));
817 /* A helper function that creates the copies, updates line info,
818 and emits the code either before or after BSI. */
821 emit_scalar_copies (block_stmt_iterator *bsi, tree lhs, tree rhs,
822 enum sra_copy_mode mode)
824 tree list = create_scalar_copies (lhs, rhs, mode);
825 tree stmt = bsi_stmt (*bsi);
827 if (EXPR_HAS_LOCATION (stmt))
828 annotate_all_with_locus (&list, EXPR_LOCATION (stmt));
830 bsi_insert_before (bsi, list, BSI_SAME_STMT);
833 /* Traverse all the statements in the function replacing references to
834 scalarizable structures with their corresponding scalar temporaries. */
837 scalarize_structures (void)
840 block_stmt_iterator si;
844 for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
849 stmt = bsi_stmt (si);
850 ann = stmt_ann (stmt);
852 /* If the statement has no virtual operands, then it doesn't make
853 structure references that we care about. */
854 if (NUM_V_MAY_DEFS (V_MAY_DEF_OPS (ann)) == 0
855 && NUM_VUSES (VUSE_OPS (ann)) == 0
856 && NUM_V_MUST_DEFS (V_MUST_DEF_OPS (ann)) == 0)
859 /* Structure references may only appear in certain statements. */
860 if (TREE_CODE (stmt) != MODIFY_EXPR
861 && TREE_CODE (stmt) != CALL_EXPR
862 && TREE_CODE (stmt) != RETURN_EXPR
863 && TREE_CODE (stmt) != ASM_EXPR)
866 scalarize_stmt (&si);
869 /* Initialize the scalar replacements for every structure that is a
870 function argument. */
871 EXECUTE_IF_SET_IN_BITMAP (needs_copy_in, 0, i,
873 tree var = referenced_var (i);
874 tree list = create_scalar_copies (var, var, SCALAR_FIELD);
875 bsi_insert_on_edge (ENTRY_BLOCK_PTR->succ, list);
878 /* Commit edge insertions. */
879 bsi_commit_edge_inserts (NULL);
883 /* Scalarize structure references in the statement pointed by SI_P. */
886 scalarize_stmt (block_stmt_iterator *si_p)
888 tree stmt = bsi_stmt (*si_p);
890 /* Handle assignments. */
891 if (TREE_CODE (stmt) == MODIFY_EXPR
892 && TREE_CODE (TREE_OPERAND (stmt, 1)) != CALL_EXPR)
893 scalarize_modify_expr (si_p);
895 /* Handle RETURN_EXPR. */
896 else if (TREE_CODE (stmt) == RETURN_EXPR)
897 scalarize_return_expr (si_p);
899 /* Handle function calls (note that this must be handled after
900 MODIFY_EXPR and RETURN_EXPR because a function call can appear in
902 else if (get_call_expr_in (stmt) != NULL_TREE)
903 scalarize_call_expr (si_p);
905 /* Handle ASM_EXPRs. */
906 else if (TREE_CODE (stmt) == ASM_EXPR)
907 scalarize_asm_expr (si_p);
911 /* Helper for scalarize_stmt to handle assignments. */
914 scalarize_modify_expr (block_stmt_iterator *si_p)
916 tree stmt = bsi_stmt (*si_p);
917 tree lhs = TREE_OPERAND (stmt, 0);
918 tree rhs = TREE_OPERAND (stmt, 1);
920 /* Found AGGREGATE.FIELD = ... */
921 if (is_sra_candidate_ref (lhs, false))
924 v_may_def_optype v_may_defs;
926 scalarize_component_ref (stmt, &TREE_OPERAND (stmt, 0));
928 /* Mark the LHS to be renamed, as we have just removed the previous
929 V_MAY_DEF for AGGREGATE. The statement should have exactly one
930 V_MAY_DEF for variable AGGREGATE. */
931 v_may_defs = STMT_V_MAY_DEF_OPS (stmt);
932 if (NUM_V_MAY_DEFS (v_may_defs) != 1)
934 sym = SSA_NAME_VAR (V_MAY_DEF_RESULT (v_may_defs, 0));
935 bitmap_set_bit (vars_to_rename, var_ann (sym)->uid);
938 /* Found ... = AGGREGATE.FIELD */
939 else if (is_sra_candidate_ref (rhs, false))
940 scalarize_component_ref (stmt, &TREE_OPERAND (stmt, 1));
942 /* Found ... = BIT_FIELD_REF <>. This is similar to a CALL_EXPR, if the
943 operand of the BIT_FIELD_REF is a scalarizable structure, we need to
944 copy from its scalar replacements before doing the bitfield operation.
946 FIXME: BIT_FIELD_REFs are often generated by fold-const.c. This is
947 not always desirable because they obfuscate the original predicates,
948 limiting what the tree optimizers may do. For instance, in
949 testsuite/g++.dg/opt/nrv4.C the use of SRA allows the optimizers to
950 optimize function main() to 'return 0;'. However, the folder
951 generates a BIT_FIELD_REF operation for one of the comparisons,
952 preventing the optimizers from removing all the redundant
954 else if (is_sra_candidate_ref (rhs, true))
956 tree var = TREE_OPERAND (rhs, 0);
957 emit_scalar_copies (si_p, var, var, FIELD_SCALAR);
960 /* Found AGGREGATE = ... or ... = AGGREGATE */
961 else if (DECL_P (lhs) || DECL_P (rhs))
962 scalarize_structure_assignment (si_p);
966 /* Scalarize structure references in LIST. Use DONE to avoid duplicates. */
969 scalarize_tree_list (tree list, block_stmt_iterator *si_p, bitmap done)
973 for (op = list; op; op = TREE_CHAIN (op))
975 tree arg = TREE_VALUE (op);
977 if (is_sra_candidate_decl (arg))
979 int index = var_ann (arg)->uid;
980 if (!bitmap_bit_p (done, index))
982 emit_scalar_copies (si_p, arg, arg, FIELD_SCALAR);
983 bitmap_set_bit (done, index);
986 else if (is_sra_candidate_ref (arg, false))
988 tree stmt = bsi_stmt (*si_p);
989 scalarize_component_ref (stmt, &TREE_VALUE (op));
995 /* Helper for scalarize_stmt to handle function calls. */
998 scalarize_call_expr (block_stmt_iterator *si_p)
1000 tree stmt = bsi_stmt (*si_p);
1001 tree call = (TREE_CODE (stmt) == MODIFY_EXPR) ? TREE_OPERAND (stmt, 1) : stmt;
1002 struct bitmap_head_def done_head;
1004 /* First scalarize the arguments. Order is important, because the copy
1005 operations for the arguments need to go before the call.
1006 Scalarization of the return value needs to go after the call. */
1007 bitmap_initialize (&done_head, 1);
1008 scalarize_tree_list (TREE_OPERAND (call, 1), si_p, &done_head);
1009 bitmap_clear (&done_head);
1011 /* Scalarize the return value, if any. */
1012 if (TREE_CODE (stmt) == MODIFY_EXPR)
1014 tree var = TREE_OPERAND (stmt, 0);
1016 /* If the LHS of the assignment is a scalarizable structure, insert
1017 copies into the scalar replacements after the call. */
1018 if (is_sra_candidate_decl (var))
1020 tree list = create_scalar_copies (var, var, SCALAR_FIELD);
1021 if (EXPR_HAS_LOCATION (stmt))
1022 annotate_all_with_locus (&list, EXPR_LOCATION (stmt));
1023 if (stmt_ends_bb_p (stmt))
1024 insert_edge_copies (list, bb_for_stmt (stmt));
1026 bsi_insert_after (si_p, list, BSI_NEW_STMT);
1032 /* Helper for scalarize_stmt to handle ASM_EXPRs. */
1035 scalarize_asm_expr (block_stmt_iterator *si_p)
1037 tree stmt = bsi_stmt (*si_p);
1038 struct bitmap_head_def done_head;
1040 bitmap_initialize (&done_head, 1);
1041 scalarize_tree_list (ASM_INPUTS (stmt), si_p, &done_head);
1042 scalarize_tree_list (ASM_OUTPUTS (stmt), si_p, &done_head);
1043 bitmap_clear (&done_head);
1045 /* ??? Process outputs after the asm. */
1049 /* Helper for scalarize_stmt to handle return expressions. */
1052 scalarize_return_expr (block_stmt_iterator *si_p)
1054 tree stmt = bsi_stmt (*si_p);
1055 tree op = TREE_OPERAND (stmt, 0);
1057 if (op == NULL_TREE)
1060 /* Handle a bare RESULT_DECL. This will handle for types needed
1061 constructors, or possibly after NRV type optimizations. */
1062 if (is_sra_candidate_decl (op))
1063 emit_scalar_copies (si_p, op, op, FIELD_SCALAR);
1064 else if (TREE_CODE (op) == MODIFY_EXPR)
1066 tree *rhs_p = &TREE_OPERAND (op, 1);
1069 /* Handle 'return STRUCTURE;' */
1070 if (is_sra_candidate_decl (rhs))
1071 emit_scalar_copies (si_p, rhs, rhs, FIELD_SCALAR);
1073 /* Handle 'return STRUCTURE.FIELD;' */
1074 else if (is_sra_candidate_ref (rhs, false))
1075 scalarize_component_ref (stmt, rhs_p);
1077 /* Handle 'return CALL_EXPR;' */
1078 else if (TREE_CODE (rhs) == CALL_EXPR)
1080 struct bitmap_head_def done_head;
1081 bitmap_initialize (&done_head, 1);
1082 scalarize_tree_list (TREE_OPERAND (rhs, 1), si_p, &done_head);
1083 bitmap_clear (&done_head);
1089 /* Debugging dump for the scalar replacement map. */
1092 dump_sra_map_trav (void **slot, void *data)
1094 struct sra_elt *e = *slot;
1100 fputs ("__real__ ", f);
1101 print_generic_expr (dump_file, e->base, dump_flags);
1102 fprintf (f, " -> %s\n", get_name (e->replace));
1105 fputs ("__imag__ ", f);
1106 print_generic_expr (dump_file, e->base, dump_flags);
1107 fprintf (f, " -> %s\n", get_name (e->replace));
1110 print_generic_expr (dump_file, e->base, dump_flags);
1111 fprintf (f, ".%s -> %s\n", get_name (e->field), get_name (e->replace));
1121 dump_sra_map (FILE *f)
1123 fputs ("Scalar replacements:\n", f);
1124 htab_traverse_noresize (sra_map, dump_sra_map_trav, f);
1128 /* Main entry point to Scalar Replacement of Aggregates (SRA). This pass
1129 re-writes non-aliased structure references into scalar temporaries. The
1130 goal is to expose some/all structures to the scalar optimizers.
1132 Scalarization proceeds in two main phases. First, every structure
1133 referenced in the program that complies with can_be_scalarized_p is
1134 marked for scalarization (find_candidates_for_sra).
1136 Second, a mapping between structure fields and scalar temporaries so
1137 that every time a particular field of a particular structure is
1138 referenced in the code, we replace it with its corresponding scalar
1139 temporary (scalarize_structures).
1143 1- Scalarize COMPLEX_TYPEs
1144 2- Scalarize ARRAY_REFs that are always referenced with a
1146 3- Timings to determine when scalarization is not profitable.
1147 4- Determine what's a good value for MAX_NFIELDS_FOR_SRA. */
1152 /* Initialize local variables. */
1153 sra_candidates = BITMAP_XMALLOC ();
1155 needs_copy_in = NULL;
1157 /* Find structures to be scalarized. */
1158 if (!find_candidates_for_sra ())
1160 BITMAP_XFREE (sra_candidates);
1164 /* If we found any, re-write structure references with their
1165 corresponding scalar replacement. */
1166 sra_map = htab_create (101, sra_elt_hash, sra_elt_eq, free);
1167 needs_copy_in = BITMAP_XMALLOC ();
1169 scalarize_structures ();
1172 dump_sra_map (dump_file);
1174 /* Free allocated memory. */
1175 htab_delete (sra_map);
1177 BITMAP_XFREE (needs_copy_in);
1178 BITMAP_XFREE (sra_candidates);
1184 return flag_tree_sra != 0;
1187 struct tree_opt_pass pass_sra =
1190 gate_sra, /* gate */
1191 tree_sra, /* execute */
1194 0, /* static_pass_number */
1195 TV_TREE_SRA, /* tv_id */
1196 PROP_cfg | PROP_ssa, /* properties_required */
1197 0, /* properties_provided */
1198 0, /* properties_destroyed */
1199 0, /* todo_flags_start */
1200 TODO_dump_func | TODO_rename_vars
1201 | TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */