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 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 /* Mark all the variables in V_MAY_DEF operands for STMT for renaming.
116 This becomes necessary when we modify all of a non-scalar. */
119 mark_all_v_may_defs (tree stmt
)
121 v_may_def_optype v_may_defs
;
124 get_stmt_operands (stmt
);
125 v_may_defs
= V_MAY_DEF_OPS (stmt_ann (stmt
));
126 n
= NUM_V_MAY_DEFS (v_may_defs
);
128 for (i
= 0; i
< n
; i
++)
130 tree sym
= V_MAY_DEF_RESULT (v_may_defs
, i
);
131 bitmap_set_bit (vars_to_rename
, var_ann (sym
)->uid
);
135 /* Mark all the variables in V_MUST_DEF operands for STMT for renaming.
136 This becomes necessary when we modify all of a non-scalar. */
139 mark_all_v_must_defs (tree stmt
)
141 v_must_def_optype v_must_defs
;
144 get_stmt_operands (stmt
);
145 v_must_defs
= V_MUST_DEF_OPS (stmt_ann (stmt
));
146 n
= NUM_V_MUST_DEFS (v_must_defs
);
148 for (i
= 0; i
< n
; i
++)
150 tree sym
= V_MUST_DEF_OP (v_must_defs
, i
);
151 bitmap_set_bit (vars_to_rename
, var_ann (sym
)->uid
);
155 /* Return true if DECL is an SRA candidate. */
158 is_sra_candidate_decl (tree decl
)
160 return DECL_P (decl
) && bitmap_bit_p (sra_candidates
, var_ann (decl
)->uid
);
163 /* Return true if EXP is of the form <ref decl>, where REF is one of the
164 field access references we handle and DECL is an SRA candidate.
166 Set ALLOW_BIT_FIELD_REF to accept BIT_FIELD_REF as well. This is
167 normally false, except when we're trying to work around it. */
170 is_sra_candidate_ref (tree exp
, bool allow_bit_field_ref
)
172 switch (TREE_CODE (exp
))
175 if (!allow_bit_field_ref
)
182 return is_sra_candidate_decl (TREE_OPERAND (exp
, 0));
191 /* Return the scalar in SRA_MAP[VAR_IX][FIELD_IX]. If none exists, create
192 a new scalar with type TYPE. */
195 lookup_scalar (struct sra_elt
*key
, tree type
)
197 struct sra_elt
**slot
, *res
;
199 slot
= (struct sra_elt
**) htab_find_slot (sra_map
, key
, INSERT
);
203 res
= xmalloc (sizeof (*res
));
206 res
->replace
= make_rename_temp (type
, "SR");
208 if (DECL_NAME (key
->base
) && !DECL_IGNORED_P (key
->base
))
214 if (!DECL_NAME (key
->field
))
216 name
= concat (IDENTIFIER_POINTER (DECL_NAME (key
->base
)),
218 IDENTIFIER_POINTER (DECL_NAME (key
->field
)),
222 name
= concat (IDENTIFIER_POINTER (DECL_NAME (key
->base
)),
226 name
= concat (IDENTIFIER_POINTER (DECL_NAME (key
->base
)),
234 DECL_NAME (res
->replace
) = get_identifier (name
);
239 DECL_SOURCE_LOCATION (res
->replace
) = DECL_SOURCE_LOCATION (key
->base
);
240 TREE_NO_WARNING (res
->replace
) = TREE_NO_WARNING (key
->base
);
241 DECL_ARTIFICIAL (res
->replace
) = DECL_ARTIFICIAL (key
->base
);
248 /* Given a structure reference VAR.FIELD, return a scalar representing it.
249 If no scalar is found, a new one is created and added to the SRA_MAP
253 get_scalar_for_field (tree var
, tree field
)
257 #ifdef ENABLE_CHECKING
258 /* Validate that FIELD actually exists in VAR's type. */
261 for (f
= TYPE_FIELDS (TREE_TYPE (var
)); f
; f
= TREE_CHAIN (f
))
269 key
.kind
= COMPONENT_REF
;
273 return lookup_scalar (&key
, TREE_TYPE (field
));
277 /* Similarly for the parts of a complex type. */
280 get_scalar_for_complex_part (tree var
, enum tree_code part
)
287 return lookup_scalar (&key
, TREE_TYPE (TREE_TYPE (var
)));
290 /* Return true if the fields of VAR can be replaced by scalar temporaries.
291 This only happens if VAR is not call-clobbered and it contains less
292 than MAX_NFIELDS_FOR_SRA scalar fields. */
295 can_be_scalarized_p (tree var
)
300 if (!is_gimple_non_addressable (var
))
302 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
304 fprintf (dump_file
, "Cannot scalarize variable ");
305 print_generic_expr (dump_file
, var
, dump_flags
);
306 fprintf (dump_file
, " because it must live in memory\n");
311 if (TREE_THIS_VOLATILE (var
))
313 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
315 fprintf (dump_file
, "Cannot scalarize variable ");
316 print_generic_expr (dump_file
, var
, dump_flags
);
317 fprintf (dump_file
, " because it is declared volatile\n");
322 /* Any COMPLEX_TYPE that has reached this point can be scalarized. */
323 if (TREE_CODE (TREE_TYPE (var
)) == COMPLEX_TYPE
)
326 type
= TREE_TYPE (var
);
328 for (field
= TYPE_FIELDS (type
); field
; field
= TREE_CHAIN (field
))
330 if (TREE_CODE (field
) != FIELD_DECL
)
333 /* FIXME: We really should recurse down the type hierarchy and
334 scalarize the fields at the leaves. */
335 if (AGGREGATE_TYPE_P (TREE_TYPE (field
)))
337 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
339 fprintf (dump_file
, "Cannot scalarize variable ");
340 print_generic_expr (dump_file
, var
, dump_flags
);
342 " because it contains an aggregate type field, ");
343 print_generic_expr (dump_file
, field
, dump_flags
);
344 fprintf (dump_file
, "\n");
349 /* FIXME: Similarly. Indeed, considering that we treat complex
350 as an aggregate, this is exactly the same problem.
351 Structures with __complex__ fields are tested in the libstdc++
352 testsuite: 26_numerics/complex_inserters_extractors.cc. */
353 if (TREE_CODE (TREE_TYPE (field
)) == COMPLEX_TYPE
)
355 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
357 fprintf (dump_file
, "Cannot scalarize variable ");
358 print_generic_expr (dump_file
, var
, dump_flags
);
360 " because it contains a __complex__ field, ");
361 print_generic_expr (dump_file
, field
, dump_flags
);
362 fprintf (dump_file
, "\n");
367 /* FIXME. We don't scalarize structures with bit fields yet. To
368 support this, we should make sure that all the fields fit in one
369 word and modify every operation done on the scalarized bit fields
370 to mask them properly. */
371 if (DECL_BIT_FIELD (field
))
373 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
375 fprintf (dump_file
, "Cannot scalarize variable ");
376 print_generic_expr (dump_file
, var
, dump_flags
);
378 " because it contains a bit-field, ");
379 print_generic_expr (dump_file
, field
, dump_flags
);
380 fprintf (dump_file
, "\n");
386 if (nfields
> MAX_NFIELDS_FOR_SRA
)
388 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
390 fprintf (dump_file
, "Cannot scalarize variable ");
391 print_generic_expr (dump_file
, var
, dump_flags
);
393 " because it contains more than %d fields\n",
394 MAX_NFIELDS_FOR_SRA
);
400 /* If the structure had no FIELD_DECLs, then don't bother
406 /* Replace the COMPONENT_REF, REALPART_EXPR or IMAGPART_EXPR pointed-to by
407 TP inside STMT with the corresponding scalar replacement from SRA_MAP. */
410 scalarize_component_ref (tree stmt
, tree
*tp
)
412 tree t
= *tp
, obj
= TREE_OPERAND (t
, 0);
414 /* When scalarizing a function argument, we will need to insert copy-in
415 operations from the original PARM_DECLs. Note that these copy-in
416 operations may end up being dead, but we won't know until we rename
417 the new variables into SSA. */
418 if (TREE_CODE (obj
) == PARM_DECL
)
419 bitmap_set_bit (needs_copy_in
, var_ann (obj
)->uid
);
421 switch (TREE_CODE (t
))
424 t
= get_scalar_for_field (obj
, TREE_OPERAND (t
, 1));
428 t
= get_scalar_for_complex_part (obj
, TREE_CODE (t
));
439 /* Scalarize the structure assignment for the statement pointed by SI_P. */
442 scalarize_structure_assignment (block_stmt_iterator
*si_p
)
444 var_ann_t lhs_ann
, rhs_ann
;
445 tree lhs
, rhs
, list
, orig_stmt
;
446 bool lhs_can
, rhs_can
;
448 orig_stmt
= bsi_stmt (*si_p
);
449 lhs
= TREE_OPERAND (orig_stmt
, 0);
450 rhs
= TREE_OPERAND (orig_stmt
, 1);
453 #if defined ENABLE_CHECKING
454 if (TREE_CODE (orig_stmt
) != MODIFY_EXPR
)
458 /* Remove all type casts from RHS. This may seem heavy handed but
459 it's actually safe and it is necessary in the presence of C++
460 reinterpret_cast<> where structure assignments of different
461 structures will be present in the IL. This was the case of PR
462 13347 (http://gcc.gnu.org/bugzilla/show_bug.cgi?id=13347) which
463 had something like this:
469 Both 'f' and 'g' were scalarizable, but the presence of the type
470 cast was causing SRA to not replace the RHS of the assignment
471 with g's scalar replacements. Furthermore, the fact that this
472 assignment reached this point without causing syntax errors means
473 that the type cast is safe and that a field-by-field assignment
474 from 'g' into 'f' is the right thing to do. */
477 lhs_ann
= DECL_P (lhs
) ? var_ann (lhs
) : NULL
;
478 rhs_ann
= DECL_P (rhs
) ? var_ann (rhs
) : NULL
;
480 #if defined ENABLE_CHECKING
481 /* Two different variables should not have the same UID. */
485 && lhs_ann
->uid
== rhs_ann
->uid
)
489 lhs_can
= lhs_ann
&& bitmap_bit_p (sra_candidates
, lhs_ann
->uid
);
490 rhs_can
= rhs_ann
&& bitmap_bit_p (sra_candidates
, rhs_ann
->uid
);
492 /* Both LHS and RHS are scalarizable. */
493 if (lhs_can
&& rhs_can
)
494 list
= create_scalar_copies (lhs
, rhs
, SCALAR_SCALAR
);
496 /* Only RHS is scalarizable. */
498 list
= create_scalar_copies (lhs
, rhs
, FIELD_SCALAR
);
500 /* Only LHS is scalarizable. */
502 list
= create_scalar_copies (lhs
, rhs
, SCALAR_FIELD
);
504 /* If neither side is scalarizable, do nothing else. */
508 /* Set line number information for our replacements. */
509 if (EXPR_HAS_LOCATION (orig_stmt
))
510 annotate_all_with_locus (&list
, EXPR_LOCATION (orig_stmt
));
512 /* Replace the existing statement with the newly created list of
513 scalarized copies. When replacing the original statement, the first
514 copy replaces it and the remaining copies are inserted either after
515 the first copy or on the outgoing edges of the original statement's
518 tree_stmt_iterator tsi
= tsi_start (list
);
519 bsi_replace (si_p
, tsi_stmt (tsi
), true);
521 if (stmt_ends_bb_p (orig_stmt
))
522 insert_edge_copies (list
, bb_for_stmt (orig_stmt
));
524 bsi_insert_after (si_p
, list
, BSI_CONTINUE_LINKING
);
529 /* Traverse all the referenced variables in the program looking for
530 structures that could be replaced with scalars. */
533 find_candidates_for_sra (void)
536 bool any_set
= false;
538 for (i
= 0; i
< num_referenced_vars
; i
++)
540 tree var
= referenced_var (i
);
542 if ((TREE_CODE (TREE_TYPE (var
)) == RECORD_TYPE
543 || TREE_CODE (TREE_TYPE (var
)) == COMPLEX_TYPE
)
544 && can_be_scalarized_p (var
))
546 bitmap_set_bit (sra_candidates
, var_ann (var
)->uid
);
555 /* Insert STMT on all the outgoing edges out of BB. Note that if BB
556 has more than one edge, STMT will be replicated for each edge. Also,
557 abnormal edges will be ignored. */
560 insert_edge_copies (tree stmt
, basic_block bb
)
566 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
568 /* We don't need to insert copies on abnormal edges. The
569 value of the scalar replacement is not guaranteed to
570 be valid through an abnormal edge. */
571 if (!(e
->flags
& EDGE_ABNORMAL
))
575 bsi_insert_on_edge (e
, stmt
);
579 bsi_insert_on_edge (e
, lhd_unsave_expr_now (stmt
));
585 /* Append a new assignment statement to TSI. */
588 csc_assign (tree_stmt_iterator
*tsi
, tree lhs
, tree rhs
)
590 tree stmt
= build (MODIFY_EXPR
, TREE_TYPE (lhs
), lhs
, rhs
);
592 tsi_link_after (tsi
, stmt
, TSI_NEW_STMT
);
596 /* A subroutine of create_scalar_copies. Construct a COMPONENT_REF
597 expression for BASE referencing FIELD. INDEX is the field index. */
600 csc_build_component_ref (tree base
, tree field
)
602 switch (TREE_CODE (base
))
605 /* Only appears on RHS. The only remaining CONSTRUCTORS for
606 record types that should remain are empty, and imply that
607 the entire structure should be zeroed. */
608 if (CONSTRUCTOR_ELTS (base
))
610 return fold_convert (TREE_TYPE (field
), integer_zero_node
);
613 /* Avoid sharing BASE when building the different COMPONENT_REFs.
614 We let the first field have the original version. */
615 if (field
!= TYPE_FIELDS (TREE_TYPE (base
)))
616 base
= unshare_expr (base
);
621 /* Special case for the above -- decls are always shared. */
625 return build (COMPONENT_REF
, TREE_TYPE (field
), base
, field
);
628 /* Similarly for REALPART_EXPR and IMAGPART_EXPR for complex types. */
631 csc_build_complex_part (tree base
, enum tree_code part
)
633 switch (TREE_CODE (base
))
636 if (part
== REALPART_EXPR
)
637 return TREE_REALPART (base
);
639 return TREE_IMAGPART (base
);
642 if (part
== REALPART_EXPR
)
643 return TREE_OPERAND (base
, 0);
645 return TREE_OPERAND (base
, 1);
648 /* Avoid sharing BASE when building the different references.
649 We let the real part have the original version. */
650 if (part
!= REALPART_EXPR
)
651 base
= unshare_expr (base
);
656 /* Special case for the above -- decls are always shared. */
660 return build1 (part
, TREE_TYPE (TREE_TYPE (base
)), base
);
663 /* Create and return a list of assignments to perform a scalarized
664 structure assignment 'LHS = RHS'. Both LHS and RHS are assumed to be
665 of an aggregate or complex type. Three types of copies may be specified:
667 SCALAR_SCALAR will emit assignments for all the scalar temporaries
668 corresponding to the fields of LHS and RHS.
670 FIELD_SCALAR will emit assignments from the scalar replacements of
671 RHS into each of the fields of the LHS.
673 SCALAR_FIELD will emit assignments from each field of the RHS into
674 the scalar replacements of the LHS. */
677 create_scalar_copies (tree lhs
, tree rhs
, enum sra_copy_mode mode
)
680 tree_stmt_iterator tsi
;
682 #if defined ENABLE_CHECKING
683 /* Sanity checking. Check that we are not trying to scalarize a
685 if (!DECL_P (lhs
) && (mode
== SCALAR_FIELD
|| mode
== SCALAR_SCALAR
))
687 if (!DECL_P (rhs
) && (mode
== FIELD_SCALAR
|| mode
== SCALAR_SCALAR
))
691 type
= TREE_TYPE (lhs
);
692 list
= alloc_stmt_list ();
693 tsi
= tsi_start (list
);
695 /* VA_ARG_EXPRs have side effects, so we need to copy it first to a
696 temporary before scalarizing. FIXME: This should disappear once
697 VA_ARG_EXPRs are properly lowered. */
698 if (TREE_CODE (rhs
) == VA_ARG_EXPR
)
702 /* Add TMP = VA_ARG_EXPR <> */
703 tmp
= make_rename_temp (TREE_TYPE (rhs
), NULL
);
704 stmt
= csc_assign (&tsi
, tmp
, rhs
);
706 /* Mark all the variables in VDEF operands for renaming, because
707 the VA_ARG_EXPR will now be in a different statement. */
708 mark_all_v_may_defs (stmt
);
709 mark_all_v_must_defs (stmt
);
711 /* Set RHS to be the new temporary TMP. */
715 /* When making *_SCALAR copies from PARM_DECLs, we will need to insert
716 copy-in operations from the original PARM_DECLs. Note that these
717 copy-in operations may end up being dead, but we won't know until
718 we rename the new variables into SSA. */
719 if ((mode
== SCALAR_SCALAR
|| mode
== FIELD_SCALAR
)
720 && TREE_CODE (rhs
) == PARM_DECL
)
721 bitmap_set_bit (needs_copy_in
, var_ann (rhs
)->uid
);
723 /* Now create scalar copies for each individual field according to MODE. */
724 if (TREE_CODE (type
) == COMPLEX_TYPE
)
726 /* Create scalar copies of both the real and imaginary parts. */
727 tree real_lhs
, real_rhs
, imag_lhs
, imag_rhs
;
729 if (mode
== SCALAR_FIELD
)
731 real_rhs
= csc_build_complex_part (rhs
, REALPART_EXPR
);
732 imag_rhs
= csc_build_complex_part (rhs
, IMAGPART_EXPR
);
736 real_rhs
= get_scalar_for_complex_part (rhs
, REALPART_EXPR
);
737 imag_rhs
= get_scalar_for_complex_part (rhs
, IMAGPART_EXPR
);
740 if (mode
== FIELD_SCALAR
)
742 /* In this case we do not need to create but one statement,
743 since we can create a new complex value whole. */
745 if (TREE_CONSTANT (real_rhs
) && TREE_CONSTANT (imag_rhs
))
746 rhs
= build_complex (type
, real_rhs
, imag_rhs
);
748 rhs
= build (COMPLEX_EXPR
, type
, real_rhs
, imag_rhs
);
749 csc_assign (&tsi
, lhs
, rhs
);
753 real_lhs
= get_scalar_for_complex_part (lhs
, REALPART_EXPR
);
754 imag_lhs
= get_scalar_for_complex_part (lhs
, IMAGPART_EXPR
);
756 csc_assign (&tsi
, real_lhs
, real_rhs
);
757 csc_assign (&tsi
, imag_lhs
, imag_rhs
);
764 /* ??? C++ generates copies between different pointer-to-member
765 structures of different types. To combat this, we must track
766 the field of both the left and right structures, so that we
767 index the variables with fields of their own type. */
769 for (lf
= TYPE_FIELDS (type
), rf
= TYPE_FIELDS (TREE_TYPE (rhs
));
771 lf
= TREE_CHAIN (lf
), rf
= TREE_CHAIN (rf
))
773 tree lhs_var
, rhs_var
;
775 /* Only copy FIELD_DECLs. */
776 if (TREE_CODE (lf
) != FIELD_DECL
)
779 if (mode
== FIELD_SCALAR
)
780 lhs_var
= csc_build_component_ref (lhs
, lf
);
782 lhs_var
= get_scalar_for_field (lhs
, lf
);
784 if (mode
== SCALAR_FIELD
)
785 rhs_var
= csc_build_component_ref (rhs
, rf
);
787 rhs_var
= get_scalar_for_field (rhs
, rf
);
789 csc_assign (&tsi
, lhs_var
, rhs_var
);
793 /* All the scalar copies just created will either create new definitions
794 or remove existing definitions of LHS, so we need to mark it for
796 if (TREE_SIDE_EFFECTS (list
))
798 if (mode
== SCALAR_FIELD
|| mode
== SCALAR_SCALAR
)
800 /* If the LHS has been scalarized, mark it for renaming. */
801 bitmap_set_bit (vars_to_rename
, var_ann (lhs
)->uid
);
803 else if (mode
== FIELD_SCALAR
)
805 /* Otherwise, mark all the symbols in the VDEFs for the last
806 scalarized statement just created. Since all the statements
807 introduce the same VDEFs, we only need to check the last one. */
808 mark_all_v_may_defs (tsi_stmt (tsi
));
809 mark_all_v_must_defs (tsi_stmt (tsi
));
818 /* A helper function that creates the copies, updates line info,
819 and emits the code either before or after BSI. */
822 emit_scalar_copies (block_stmt_iterator
*bsi
, tree lhs
, tree rhs
,
823 enum sra_copy_mode mode
)
825 tree list
= create_scalar_copies (lhs
, rhs
, mode
);
826 tree stmt
= bsi_stmt (*bsi
);
828 if (EXPR_HAS_LOCATION (stmt
))
829 annotate_all_with_locus (&list
, EXPR_LOCATION (stmt
));
831 bsi_insert_before (bsi
, list
, BSI_SAME_STMT
);
834 /* Traverse all the statements in the function replacing references to
835 scalarizable structures with their corresponding scalar temporaries. */
838 scalarize_structures (void)
841 block_stmt_iterator si
;
845 for (si
= bsi_start (bb
); !bsi_end_p (si
); bsi_next (&si
))
850 stmt
= bsi_stmt (si
);
851 ann
= stmt_ann (stmt
);
853 /* If the statement has no virtual operands, then it doesn't make
854 structure references that we care about. */
855 if (NUM_V_MAY_DEFS (V_MAY_DEF_OPS (ann
)) == 0
856 && NUM_VUSES (VUSE_OPS (ann
)) == 0
857 && NUM_V_MUST_DEFS (V_MUST_DEF_OPS (ann
)) == 0)
860 /* Structure references may only appear in certain statements. */
861 if (TREE_CODE (stmt
) != MODIFY_EXPR
862 && TREE_CODE (stmt
) != CALL_EXPR
863 && TREE_CODE (stmt
) != RETURN_EXPR
864 && TREE_CODE (stmt
) != ASM_EXPR
)
867 scalarize_stmt (&si
);
870 /* Initialize the scalar replacements for every structure that is a
871 function argument. */
872 EXECUTE_IF_SET_IN_BITMAP (needs_copy_in
, 0, i
,
874 tree var
= referenced_var (i
);
875 tree list
= create_scalar_copies (var
, var
, SCALAR_FIELD
);
876 bsi_insert_on_edge (ENTRY_BLOCK_PTR
->succ
, list
);
879 /* Commit edge insertions. */
880 bsi_commit_edge_inserts (NULL
);
884 /* Scalarize structure references in the statement pointed by SI_P. */
887 scalarize_stmt (block_stmt_iterator
*si_p
)
889 tree stmt
= bsi_stmt (*si_p
);
891 /* Handle assignments. */
892 if (TREE_CODE (stmt
) == MODIFY_EXPR
893 && TREE_CODE (TREE_OPERAND (stmt
, 1)) != CALL_EXPR
)
894 scalarize_modify_expr (si_p
);
896 /* Handle RETURN_EXPR. */
897 else if (TREE_CODE (stmt
) == RETURN_EXPR
)
898 scalarize_return_expr (si_p
);
900 /* Handle function calls (note that this must be handled after
901 MODIFY_EXPR and RETURN_EXPR because a function call can appear in
903 else if (get_call_expr_in (stmt
) != NULL_TREE
)
904 scalarize_call_expr (si_p
);
906 /* Handle ASM_EXPRs. */
907 else if (TREE_CODE (stmt
) == ASM_EXPR
)
908 scalarize_asm_expr (si_p
);
912 /* Helper for scalarize_stmt to handle assignments. */
915 scalarize_modify_expr (block_stmt_iterator
*si_p
)
917 tree stmt
= bsi_stmt (*si_p
);
918 tree lhs
= TREE_OPERAND (stmt
, 0);
919 tree rhs
= TREE_OPERAND (stmt
, 1);
921 /* Found AGGREGATE.FIELD = ... */
922 if (is_sra_candidate_ref (lhs
, false))
925 v_may_def_optype v_may_defs
;
927 scalarize_component_ref (stmt
, &TREE_OPERAND (stmt
, 0));
929 /* Mark the LHS to be renamed, as we have just removed the previous
930 V_MAY_DEF for AGGREGATE. The statement should have exactly one
931 V_MAY_DEF for variable AGGREGATE. */
932 v_may_defs
= STMT_V_MAY_DEF_OPS (stmt
);
933 if (NUM_V_MAY_DEFS (v_may_defs
) != 1)
935 sym
= SSA_NAME_VAR (V_MAY_DEF_RESULT (v_may_defs
, 0));
936 bitmap_set_bit (vars_to_rename
, var_ann (sym
)->uid
);
939 /* Found ... = AGGREGATE.FIELD */
940 else if (is_sra_candidate_ref (rhs
, false))
941 scalarize_component_ref (stmt
, &TREE_OPERAND (stmt
, 1));
943 /* Found ... = BIT_FIELD_REF <>. This is similar to a CALL_EXPR, if the
944 operand of the BIT_FIELD_REF is a scalarizable structure, we need to
945 copy from its scalar replacements before doing the bitfield operation.
947 FIXME: BIT_FIELD_REFs are often generated by fold-const.c. This is
948 not always desirable because they obfuscate the original predicates,
949 limiting what the tree optimizers may do. For instance, in
950 testsuite/g++.dg/opt/nrv4.C the use of SRA allows the optimizers to
951 optimize function main() to 'return 0;'. However, the folder
952 generates a BIT_FIELD_REF operation for one of the comparisons,
953 preventing the optimizers from removing all the redundant
955 else if (is_sra_candidate_ref (rhs
, true))
957 tree var
= TREE_OPERAND (rhs
, 0);
958 emit_scalar_copies (si_p
, var
, var
, FIELD_SCALAR
);
961 /* Found AGGREGATE = ... or ... = AGGREGATE */
962 else if (DECL_P (lhs
) || DECL_P (rhs
))
963 scalarize_structure_assignment (si_p
);
967 /* Scalarize structure references in LIST. Use DONE to avoid duplicates. */
970 scalarize_tree_list (tree list
, block_stmt_iterator
*si_p
, bitmap done
)
974 for (op
= list
; op
; op
= TREE_CHAIN (op
))
976 tree arg
= TREE_VALUE (op
);
978 if (is_sra_candidate_decl (arg
))
980 int index
= var_ann (arg
)->uid
;
981 if (!bitmap_bit_p (done
, index
))
983 emit_scalar_copies (si_p
, arg
, arg
, FIELD_SCALAR
);
984 bitmap_set_bit (done
, index
);
987 else if (is_sra_candidate_ref (arg
, false))
989 tree stmt
= bsi_stmt (*si_p
);
990 scalarize_component_ref (stmt
, &TREE_VALUE (op
));
996 /* Helper for scalarize_stmt to handle function calls. */
999 scalarize_call_expr (block_stmt_iterator
*si_p
)
1001 tree stmt
= bsi_stmt (*si_p
);
1002 tree call
= (TREE_CODE (stmt
) == MODIFY_EXPR
) ? TREE_OPERAND (stmt
, 1) : stmt
;
1003 struct bitmap_head_def done_head
;
1005 /* First scalarize the arguments. Order is important, because the copy
1006 operations for the arguments need to go before the call.
1007 Scalarization of the return value needs to go after the call. */
1008 bitmap_initialize (&done_head
, 1);
1009 scalarize_tree_list (TREE_OPERAND (call
, 1), si_p
, &done_head
);
1010 bitmap_clear (&done_head
);
1012 /* Scalarize the return value, if any. */
1013 if (TREE_CODE (stmt
) == MODIFY_EXPR
)
1015 tree var
= TREE_OPERAND (stmt
, 0);
1017 /* If the LHS of the assignment is a scalarizable structure, insert
1018 copies into the scalar replacements after the call. */
1019 if (is_sra_candidate_decl (var
))
1021 tree list
= create_scalar_copies (var
, var
, SCALAR_FIELD
);
1022 if (EXPR_HAS_LOCATION (stmt
))
1023 annotate_all_with_locus (&list
, EXPR_LOCATION (stmt
));
1024 if (stmt_ends_bb_p (stmt
))
1025 insert_edge_copies (list
, bb_for_stmt (stmt
));
1027 bsi_insert_after (si_p
, list
, BSI_NEW_STMT
);
1033 /* Helper for scalarize_stmt to handle ASM_EXPRs. */
1036 scalarize_asm_expr (block_stmt_iterator
*si_p
)
1038 tree stmt
= bsi_stmt (*si_p
);
1039 struct bitmap_head_def done_head
;
1041 bitmap_initialize (&done_head
, 1);
1042 scalarize_tree_list (ASM_INPUTS (stmt
), si_p
, &done_head
);
1043 scalarize_tree_list (ASM_OUTPUTS (stmt
), si_p
, &done_head
);
1044 bitmap_clear (&done_head
);
1046 /* ??? Process outputs after the asm. */
1050 /* Helper for scalarize_stmt to handle return expressions. */
1053 scalarize_return_expr (block_stmt_iterator
*si_p
)
1055 tree stmt
= bsi_stmt (*si_p
);
1056 tree op
= TREE_OPERAND (stmt
, 0);
1058 if (op
== NULL_TREE
)
1061 /* Handle a bare RESULT_DECL. This will handle for types needed
1062 constructors, or possibly after NRV type optimizations. */
1063 if (is_sra_candidate_decl (op
))
1064 emit_scalar_copies (si_p
, op
, op
, FIELD_SCALAR
);
1065 else if (TREE_CODE (op
) == MODIFY_EXPR
)
1067 tree
*rhs_p
= &TREE_OPERAND (op
, 1);
1070 /* Handle 'return STRUCTURE;' */
1071 if (is_sra_candidate_decl (rhs
))
1072 emit_scalar_copies (si_p
, rhs
, rhs
, FIELD_SCALAR
);
1074 /* Handle 'return STRUCTURE.FIELD;' */
1075 else if (is_sra_candidate_ref (rhs
, false))
1076 scalarize_component_ref (stmt
, rhs_p
);
1078 /* Handle 'return CALL_EXPR;' */
1079 else if (TREE_CODE (rhs
) == CALL_EXPR
)
1081 struct bitmap_head_def done_head
;
1082 bitmap_initialize (&done_head
, 1);
1083 scalarize_tree_list (TREE_OPERAND (rhs
, 1), si_p
, &done_head
);
1084 bitmap_clear (&done_head
);
1090 /* Debugging dump for the scalar replacement map. */
1093 dump_sra_map_trav (void **slot
, void *data
)
1095 struct sra_elt
*e
= *slot
;
1101 fputs ("__real__ ", f
);
1102 print_generic_expr (dump_file
, e
->base
, dump_flags
);
1103 fprintf (f
, " -> %s\n", get_name (e
->replace
));
1106 fputs ("__imag__ ", f
);
1107 print_generic_expr (dump_file
, e
->base
, dump_flags
);
1108 fprintf (f
, " -> %s\n", get_name (e
->replace
));
1111 print_generic_expr (dump_file
, e
->base
, dump_flags
);
1112 fprintf (f
, ".%s -> %s\n", get_name (e
->field
), get_name (e
->replace
));
1122 dump_sra_map (FILE *f
)
1124 fputs ("Scalar replacements:\n", f
);
1125 htab_traverse_noresize (sra_map
, dump_sra_map_trav
, f
);
1129 /* Main entry point to Scalar Replacement of Aggregates (SRA). This pass
1130 re-writes non-aliased structure references into scalar temporaries. The
1131 goal is to expose some/all structures to the scalar optimizers.
1133 FNDECL is the function to process.
1135 VARS_TO_RENAME_P is a pointer to the set of variables that need to be
1136 renamed into SSA after this pass is done. These are going to be all the
1137 new scalars created by the SRA process. Notice that since this pass
1138 creates new variables, the bitmap representing all the variables in the
1139 program will be re-sized here.
1141 PHASE indicates which dump file from the DUMP_FILES array to use when
1142 dumping debugging information.
1146 1- Scalarize COMPLEX_TYPEs
1147 2- Scalarize ARRAY_REFs that are always referenced with a
1149 3- Timings to determine when scalarization is not profitable.
1150 4- Determine what's a good value for MAX_NFIELDS_FOR_SRA. */
1155 /* Initialize local variables. */
1156 sra_candidates
= BITMAP_XMALLOC ();
1158 needs_copy_in
= NULL
;
1160 /* Find structures to be scalarized. */
1161 if (!find_candidates_for_sra ())
1163 BITMAP_XFREE (sra_candidates
);
1167 /* If we found any, re-write structure references with their
1168 corresponding scalar replacement. */
1169 sra_map
= htab_create (101, sra_elt_hash
, sra_elt_eq
, free
);
1170 needs_copy_in
= BITMAP_XMALLOC ();
1172 scalarize_structures ();
1175 dump_sra_map (dump_file
);
1177 /* Free allocated memory. */
1178 htab_delete (sra_map
);
1180 BITMAP_XFREE (needs_copy_in
);
1181 BITMAP_XFREE (sra_candidates
);
1187 return flag_tree_sra
!= 0;
1190 struct tree_opt_pass pass_sra
=
1193 gate_sra
, /* gate */
1194 tree_sra
, /* execute */
1197 0, /* static_pass_number */
1198 TV_TREE_SRA
, /* tv_id */
1199 PROP_cfg
| PROP_ssa
, /* properties_required */
1200 0, /* properties_provided */
1201 0, /* properties_destroyed */
1202 0, /* todo_flags_start */
1203 TODO_dump_func
| TODO_rename_vars
1204 | TODO_ggc_collect
| TODO_verify_ssa
/* todo_flags_finish */