/* Scalar Replacement of Aggregates (SRA) converts some structure references into scalar references, exposing them to the scalar optimizers. Copyright (C) 2003, 2004 Free Software Foundation, Inc. Contributed by Diego Novillo This file is part of GCC. GCC is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2, or (at your option) any later version. GCC is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with GCC; see the file COPYING. If not, write to the Free Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ #include "config.h" #include "system.h" #include "coretypes.h" #include "tm.h" #include "errors.h" #include "ggc.h" #include "tree.h" /* These RTL headers are needed for basic-block.h. */ #include "rtl.h" #include "tm_p.h" #include "hard-reg-set.h" #include "basic-block.h" #include "diagnostic.h" #include "langhooks.h" #include "tree-inline.h" #include "tree-flow.h" #include "tree-gimple.h" #include "tree-dump.h" #include "tree-pass.h" #include "timevar.h" #include "flags.h" #include "bitmap.h" /* Maximum number of fields that a structure should have to be scalarized. FIXME This limit has been arbitrarily set to 5. Experiment to find a sensible setting. */ #define MAX_NFIELDS_FOR_SRA 5 /* Codes indicating how to copy one structure into another. */ enum sra_copy_mode { SCALAR_SCALAR, FIELD_SCALAR, SCALAR_FIELD }; /* Local functions. */ static inline bool can_be_scalarized_p (tree); static inline void insert_edge_copies (tree stmt, basic_block bb); static tree create_scalar_copies (tree lhs, tree rhs, enum sra_copy_mode mode); static inline void scalarize_component_ref (tree, tree *tp); static void scalarize_structures (void); static void scalarize_stmt (block_stmt_iterator *); static void scalarize_modify_expr (block_stmt_iterator *); static void scalarize_call_expr (block_stmt_iterator *); static void scalarize_asm_expr (block_stmt_iterator *); static void scalarize_return_expr (block_stmt_iterator *); /* The set of aggregate variables that are candidates for scalarization. */ static bitmap sra_candidates; /* Set of scalarizable PARM_DECLs that need copy-in operations at the beginning of the function. */ static bitmap needs_copy_in; /* This structure holds the mapping between and element of an aggregate and the scalar replacement variable. */ struct sra_elt { enum tree_code kind; tree base; tree field; tree replace; }; static htab_t sra_map; static hashval_t sra_elt_hash (const void *x) { const struct sra_elt *e = x; hashval_t h = (size_t) e->base * e->kind; if (e->kind == COMPONENT_REF) h ^= (size_t) e->field; return h; } static int sra_elt_eq (const void *x, const void *y) { const struct sra_elt *a = x; const struct sra_elt *b = y; if (a->kind != b->kind) return false; if (a->base != b->base) return false; if (a->kind == COMPONENT_REF) if (a->field != b->field) return false; return true; } /* Mark all the variables in VDEF operands for STMT for renaming. This becomes necessary when we modify all of a non-scalar. */ static void mark_all_vdefs (tree stmt) { vdef_optype vdefs; size_t i, n; get_stmt_operands (stmt); vdefs = VDEF_OPS (stmt_ann (stmt)); n = NUM_VDEFS (vdefs); for (i = 0; i < n; i++) { tree sym = VDEF_RESULT (vdefs, i); bitmap_set_bit (vars_to_rename, var_ann (sym)->uid); } } /* Return true if DECL is an SRA candidate. */ static bool is_sra_candidate_decl (tree decl) { return DECL_P (decl) && bitmap_bit_p (sra_candidates, var_ann (decl)->uid); } /* Return true if EXP is of the form , where REF is one of the field access references we handle and DECL is an SRA candidate. Set ALLOW_BIT_FIELD_REF to accept BIT_FIELD_REF as well. This is normally false, except when we're trying to work around it. */ static bool is_sra_candidate_ref (tree exp, bool allow_bit_field_ref) { switch (TREE_CODE (exp)) { case BIT_FIELD_REF: if (!allow_bit_field_ref) break; /* FALLTHRU */ case COMPONENT_REF: case REALPART_EXPR: case IMAGPART_EXPR: return is_sra_candidate_decl (TREE_OPERAND (exp, 0)); default: break; } return false; } /* Return the scalar in SRA_MAP[VAR_IX][FIELD_IX]. If none exists, create a new scalar with type TYPE. */ static tree lookup_scalar (struct sra_elt *key, tree type) { struct sra_elt **slot, *res; slot = (struct sra_elt **) htab_find_slot (sra_map, key, INSERT); res = *slot; if (!res) { res = xmalloc (sizeof (*res)); *slot = res; *res = *key; res->replace = make_rename_temp (type, "SR"); if (DECL_NAME (key->base) && !DECL_IGNORED_P (key->base)) { char *name = NULL; switch (key->kind) { case COMPONENT_REF: if (!DECL_NAME (key->field)) break; name = concat (IDENTIFIER_POINTER (DECL_NAME (key->base)), "$", IDENTIFIER_POINTER (DECL_NAME (key->field)), NULL); break; case REALPART_EXPR: name = concat (IDENTIFIER_POINTER (DECL_NAME (key->base)), "$real", NULL); break; case IMAGPART_EXPR: name = concat (IDENTIFIER_POINTER (DECL_NAME (key->base)), "$imag", NULL); break; default: abort (); } if (name) { DECL_NAME (res->replace) = get_identifier (name); free (name); } } DECL_SOURCE_LOCATION (res->replace) = DECL_SOURCE_LOCATION (key->base); TREE_NO_WARNING (res->replace) = TREE_NO_WARNING (key->base); DECL_ARTIFICIAL (res->replace) = DECL_ARTIFICIAL (key->base); } return res->replace; } /* Given a structure reference VAR.FIELD, return a scalar representing it. If no scalar is found, a new one is created and added to the SRA_MAP matrix. */ static tree get_scalar_for_field (tree var, tree field) { struct sra_elt key; #ifdef ENABLE_CHECKING /* Validate that FIELD actually exists in VAR's type. */ { tree f; for (f = TYPE_FIELDS (TREE_TYPE (var)); f ; f = TREE_CHAIN (f)) if (f == field) goto found; abort (); found:; } #endif key.kind = COMPONENT_REF; key.base = var; key.field = field; return lookup_scalar (&key, TREE_TYPE (field)); } /* Similarly for the parts of a complex type. */ static tree get_scalar_for_complex_part (tree var, enum tree_code part) { struct sra_elt key; key.kind = part; key.base = var; return lookup_scalar (&key, TREE_TYPE (TREE_TYPE (var))); } /* Return true if the fields of VAR can be replaced by scalar temporaries. This only happens if VAR is not call-clobbered and it contains less than MAX_NFIELDS_FOR_SRA scalar fields. */ static inline bool can_be_scalarized_p (tree var) { tree field, type; int nfields; if (!is_gimple_non_addressable (var)) { if (dump_file && (dump_flags & TDF_DETAILS)) { fprintf (dump_file, "Cannot scalarize variable "); print_generic_expr (dump_file, var, dump_flags); fprintf (dump_file, " because it must live in memory\n"); } return false; } if (TREE_THIS_VOLATILE (var)) { if (dump_file && (dump_flags & TDF_DETAILS)) { fprintf (dump_file, "Cannot scalarize variable "); print_generic_expr (dump_file, var, dump_flags); fprintf (dump_file, " because it is declared volatile\n"); } return false; } /* Any COMPLEX_TYPE that has reached this point can be scalarized. */ if (TREE_CODE (TREE_TYPE (var)) == COMPLEX_TYPE) return true; type = TREE_TYPE (var); nfields = 0; for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field)) { if (TREE_CODE (field) != FIELD_DECL) continue; /* FIXME: We really should recurse down the type hierarchy and scalarize the fields at the leaves. */ if (AGGREGATE_TYPE_P (TREE_TYPE (field))) { if (dump_file && (dump_flags & TDF_DETAILS)) { fprintf (dump_file, "Cannot scalarize variable "); print_generic_expr (dump_file, var, dump_flags); fprintf (dump_file, " because it contains an aggregate type field, "); print_generic_expr (dump_file, field, dump_flags); fprintf (dump_file, "\n"); } return false; } /* FIXME: Similarly. Indeed, considering that we treat complex as an aggregate, this is exactly the same problem. Structures with __complex__ fields are tested in the libstdc++ testsuite: 26_numerics/complex_inserters_extractors.cc. */ if (TREE_CODE (TREE_TYPE (field)) == COMPLEX_TYPE) { if (dump_file && (dump_flags & TDF_DETAILS)) { fprintf (dump_file, "Cannot scalarize variable "); print_generic_expr (dump_file, var, dump_flags); fprintf (dump_file, " because it contains a __complex__ field, "); print_generic_expr (dump_file, field, dump_flags); fprintf (dump_file, "\n"); } return false; } /* FIXME. We don't scalarize structures with bit fields yet. To support this, we should make sure that all the fields fit in one word and modify every operation done on the scalarized bit fields to mask them properly. */ if (DECL_BIT_FIELD (field)) { if (dump_file && (dump_flags & TDF_DETAILS)) { fprintf (dump_file, "Cannot scalarize variable "); print_generic_expr (dump_file, var, dump_flags); fprintf (dump_file, " because it contains a bit-field, "); print_generic_expr (dump_file, field, dump_flags); fprintf (dump_file, "\n"); } return false; } nfields++; if (nfields > MAX_NFIELDS_FOR_SRA) { if (dump_file && (dump_flags & TDF_DETAILS)) { fprintf (dump_file, "Cannot scalarize variable "); print_generic_expr (dump_file, var, dump_flags); fprintf (dump_file, " because it contains more than %d fields\n", MAX_NFIELDS_FOR_SRA); } return false; } } /* If the structure had no FIELD_DECLs, then don't bother scalarizing it. */ return nfields > 0; } /* Replace the COMPONENT_REF, REALPART_EXPR or IMAGPART_EXPR pointed-to by TP inside STMT with the corresponding scalar replacement from SRA_MAP. */ static inline void scalarize_component_ref (tree stmt, tree *tp) { tree t = *tp, obj = TREE_OPERAND (t, 0); /* When scalarizing a function argument, we will need to insert copy-in operations from the original PARM_DECLs. Note that these copy-in operations may end up being dead, but we won't know until we rename the new variables into SSA. */ if (TREE_CODE (obj) == PARM_DECL) bitmap_set_bit (needs_copy_in, var_ann (obj)->uid); switch (TREE_CODE (t)) { case COMPONENT_REF: t = get_scalar_for_field (obj, TREE_OPERAND (t, 1)); break; case REALPART_EXPR: case IMAGPART_EXPR: t = get_scalar_for_complex_part (obj, TREE_CODE (t)); break; default: abort (); } *tp = t; modify_stmt (stmt); } /* Scalarize the structure assignment for the statement pointed by SI_P. */ static void scalarize_structure_assignment (block_stmt_iterator *si_p) { var_ann_t lhs_ann, rhs_ann; tree lhs, rhs, list, orig_stmt; bool lhs_can, rhs_can; orig_stmt = bsi_stmt (*si_p); lhs = TREE_OPERAND (orig_stmt, 0); rhs = TREE_OPERAND (orig_stmt, 1); list = NULL_TREE; #if defined ENABLE_CHECKING if (TREE_CODE (orig_stmt) != MODIFY_EXPR) abort (); #endif /* Remove all type casts from RHS. This may seem heavy handed but it's actually safe and it is necessary in the presence of C++ reinterpret_cast<> where structure assignments of different structures will be present in the IL. This was the case of PR 13347 (http://gcc.gnu.org/bugzilla/show_bug.cgi?id=13347) which had something like this: struct A f; struct B g; f = (struct A)g; Both 'f' and 'g' were scalarizable, but the presence of the type cast was causing SRA to not replace the RHS of the assignment with g's scalar replacements. Furthermore, the fact that this assignment reached this point without causing syntax errors means that the type cast is safe and that a field-by-field assignment from 'g' into 'f' is the right thing to do. */ STRIP_NOPS (rhs); lhs_ann = DECL_P (lhs) ? var_ann (lhs) : NULL; rhs_ann = DECL_P (rhs) ? var_ann (rhs) : NULL; #if defined ENABLE_CHECKING /* Two different variables should not have the same UID. */ if (lhs_ann && rhs_ann && lhs != rhs && lhs_ann->uid == rhs_ann->uid) abort (); #endif lhs_can = lhs_ann && bitmap_bit_p (sra_candidates, lhs_ann->uid); rhs_can = rhs_ann && bitmap_bit_p (sra_candidates, rhs_ann->uid); /* Both LHS and RHS are scalarizable. */ if (lhs_can && rhs_can) list = create_scalar_copies (lhs, rhs, SCALAR_SCALAR); /* Only RHS is scalarizable. */ else if (rhs_can) list = create_scalar_copies (lhs, rhs, FIELD_SCALAR); /* Only LHS is scalarizable. */ else if (lhs_can) list = create_scalar_copies (lhs, rhs, SCALAR_FIELD); /* If neither side is scalarizable, do nothing else. */ else return; /* Set line number information for our replacements. */ if (EXPR_HAS_LOCATION (orig_stmt)) annotate_all_with_locus (&list, EXPR_LOCATION (orig_stmt)); /* Replace the existing statement with the newly created list of scalarized copies. When replacing the original statement, the first copy replaces it and the remaining copies are inserted either after the first copy or on the outgoing edges of the original statement's block. */ { tree_stmt_iterator tsi = tsi_start (list); bsi_replace (si_p, tsi_stmt (tsi), true); tsi_delink (&tsi); if (stmt_ends_bb_p (orig_stmt)) insert_edge_copies (list, bb_for_stmt (orig_stmt)); else bsi_insert_after (si_p, list, BSI_CONTINUE_LINKING); } } /* Traverse all the referenced variables in the program looking for structures that could be replaced with scalars. */ static bool find_candidates_for_sra (void) { size_t i; bool any_set = false; for (i = 0; i < num_referenced_vars; i++) { tree var = referenced_var (i); if ((TREE_CODE (TREE_TYPE (var)) == RECORD_TYPE || TREE_CODE (TREE_TYPE (var)) == COMPLEX_TYPE) && can_be_scalarized_p (var)) { bitmap_set_bit (sra_candidates, var_ann (var)->uid); any_set = true; } } return any_set; } /* Insert STMT on all the outgoing edges out of BB. Note that if BB has more than one edge, STMT will be replicated for each edge. Also, abnormal edges will be ignored. */ static inline void insert_edge_copies (tree stmt, basic_block bb) { edge e; bool first_copy; first_copy = true; for (e = bb->succ; e; e = e->succ_next) { /* We don't need to insert copies on abnormal edges. The value of the scalar replacement is not guaranteed to be valid through an abnormal edge. */ if (!(e->flags & EDGE_ABNORMAL)) { if (first_copy) { bsi_insert_on_edge (e, stmt); first_copy = false; } else bsi_insert_on_edge (e, lhd_unsave_expr_now (stmt)); } } } /* Append a new assignment statement to TSI. */ static tree csc_assign (tree_stmt_iterator *tsi, tree lhs, tree rhs) { tree stmt = build (MODIFY_EXPR, TREE_TYPE (lhs), lhs, rhs); modify_stmt (stmt); tsi_link_after (tsi, stmt, TSI_NEW_STMT); return stmt; } /* A subroutine of create_scalar_copies. Construct a COMPONENT_REF expression for BASE referencing FIELD. INDEX is the field index. */ static tree csc_build_component_ref (tree base, tree field) { switch (TREE_CODE (base)) { case CONSTRUCTOR: /* Only appears on RHS. The only remaining CONSTRUCTORS for record types that should remain are empty, and imply that the entire structure should be zeroed. */ if (CONSTRUCTOR_ELTS (base)) abort (); return convert (TREE_TYPE (field), integer_zero_node); default: /* Avoid sharing BASE when building the different COMPONENT_REFs. We let the first field have the original version. */ if (field != TYPE_FIELDS (TREE_TYPE (base))) base = unshare_expr (base); break; case VAR_DECL: case PARM_DECL: /* Special case for the above -- decls are always shared. */ break; } return build (COMPONENT_REF, TREE_TYPE (field), base, field); } /* Similarly for REALPART_EXPR and IMAGPART_EXPR for complex types. */ static tree csc_build_complex_part (tree base, enum tree_code part) { switch (TREE_CODE (base)) { case COMPLEX_CST: if (part == REALPART_EXPR) return TREE_REALPART (base); else return TREE_IMAGPART (base); case COMPLEX_EXPR: if (part == REALPART_EXPR) return TREE_OPERAND (base, 0); else return TREE_OPERAND (base, 1); default: /* Avoid sharing BASE when building the different references. We let the real part have the original version. */ if (part != REALPART_EXPR) base = unshare_expr (base); break; case VAR_DECL: case PARM_DECL: /* Special case for the above -- decls are always shared. */ break; } return build1 (part, TREE_TYPE (TREE_TYPE (base)), base); } /* Create and return a list of assignments to perform a scalarized structure assignment 'LHS = RHS'. Both LHS and RHS are assumed to be of an aggregate or complex type. Three types of copies may be specified: SCALAR_SCALAR will emit assignments for all the scalar temporaries corresponding to the fields of LHS and RHS. FIELD_SCALAR will emit assignments from the scalar replacements of RHS into each of the fields of the LHS. SCALAR_FIELD will emit assignments from each field of the RHS into the scalar replacements of the LHS. */ static tree create_scalar_copies (tree lhs, tree rhs, enum sra_copy_mode mode) { tree type, list; tree_stmt_iterator tsi; #if defined ENABLE_CHECKING /* Sanity checking. Check that we are not trying to scalarize a non-decl. */ if (!DECL_P (lhs) && (mode == SCALAR_FIELD || mode == SCALAR_SCALAR)) abort (); if (!DECL_P (rhs) && (mode == FIELD_SCALAR || mode == SCALAR_SCALAR)) abort (); #endif type = TREE_TYPE (lhs); list = alloc_stmt_list (); tsi = tsi_start (list); /* VA_ARG_EXPRs have side effects, so we need to copy it first to a temporary before scalarizing. FIXME: This should disappear once VA_ARG_EXPRs are properly lowered. */ if (TREE_CODE (rhs) == VA_ARG_EXPR) { tree stmt, tmp; /* Add TMP = VA_ARG_EXPR <> */ tmp = make_rename_temp (TREE_TYPE (rhs), NULL); stmt = csc_assign (&tsi, tmp, rhs); /* Mark all the variables in VDEF operands for renaming, because the VA_ARG_EXPR will now be in a different statement. */ mark_all_vdefs (stmt); /* Set RHS to be the new temporary TMP. */ rhs = tmp; } /* When making *_SCALAR copies from PARM_DECLs, we will need to insert copy-in operations from the original PARM_DECLs. Note that these copy-in operations may end up being dead, but we won't know until we rename the new variables into SSA. */ if ((mode == SCALAR_SCALAR || mode == FIELD_SCALAR) && TREE_CODE (rhs) == PARM_DECL) bitmap_set_bit (needs_copy_in, var_ann (rhs)->uid); /* Now create scalar copies for each individual field according to MODE. */ if (TREE_CODE (type) == COMPLEX_TYPE) { /* Create scalar copies of both the real and imaginary parts. */ tree real_lhs, real_rhs, imag_lhs, imag_rhs; if (mode == SCALAR_FIELD) { real_rhs = csc_build_complex_part (rhs, REALPART_EXPR); imag_rhs = csc_build_complex_part (rhs, IMAGPART_EXPR); } else { real_rhs = get_scalar_for_complex_part (rhs, REALPART_EXPR); imag_rhs = get_scalar_for_complex_part (rhs, IMAGPART_EXPR); } if (mode == FIELD_SCALAR) { /* In this case we do not need to create but one statement, since we can create a new complex value whole. */ if (TREE_CONSTANT (real_rhs) && TREE_CONSTANT (imag_rhs)) rhs = build_complex (type, real_rhs, imag_rhs); else rhs = build (COMPLEX_EXPR, type, real_rhs, imag_rhs); csc_assign (&tsi, lhs, rhs); } else { real_lhs = get_scalar_for_complex_part (lhs, REALPART_EXPR); imag_lhs = get_scalar_for_complex_part (lhs, IMAGPART_EXPR); csc_assign (&tsi, real_lhs, real_rhs); csc_assign (&tsi, imag_lhs, imag_rhs); } } else { tree lf, rf; /* ??? C++ generates copies between different pointer-to-member structures of different types. To combat this, we must track the field of both the left and right structures, so that we index the variables with fields of their own type. */ for (lf = TYPE_FIELDS (type), rf = TYPE_FIELDS (TREE_TYPE (rhs)); lf; lf = TREE_CHAIN (lf), rf = TREE_CHAIN (rf)) { tree lhs_var, rhs_var; /* Only copy FIELD_DECLs. */ if (TREE_CODE (lf) != FIELD_DECL) continue; if (mode == FIELD_SCALAR) lhs_var = csc_build_component_ref (lhs, lf); else lhs_var = get_scalar_for_field (lhs, lf); if (mode == SCALAR_FIELD) rhs_var = csc_build_component_ref (rhs, rf); else rhs_var = get_scalar_for_field (rhs, rf); csc_assign (&tsi, lhs_var, rhs_var); } } /* All the scalar copies just created will either create new definitions or remove existing definitions of LHS, so we need to mark it for renaming. */ if (TREE_SIDE_EFFECTS (list)) { if (mode == SCALAR_FIELD || mode == SCALAR_SCALAR) { /* If the LHS has been scalarized, mark it for renaming. */ bitmap_set_bit (vars_to_rename, var_ann (lhs)->uid); } else if (mode == FIELD_SCALAR) { /* Otherwise, mark all the symbols in the VDEFs for the last scalarized statement just created. Since all the statements introduce the same VDEFs, we only need to check the last one. */ mark_all_vdefs (tsi_stmt (tsi)); } else abort (); } return list; } /* A helper function that creates the copies, updates line info, and emits the code either before or after BSI. */ static void emit_scalar_copies (block_stmt_iterator *bsi, tree lhs, tree rhs, enum sra_copy_mode mode) { tree list = create_scalar_copies (lhs, rhs, mode); tree stmt = bsi_stmt (*bsi); if (EXPR_HAS_LOCATION (stmt)) annotate_all_with_locus (&list, EXPR_LOCATION (stmt)); bsi_insert_before (bsi, list, BSI_SAME_STMT); } /* Traverse all the statements in the function replacing references to scalarizable structures with their corresponding scalar temporaries. */ static void scalarize_structures (void) { basic_block bb; block_stmt_iterator si; size_t i; FOR_EACH_BB (bb) for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si)) { tree stmt; stmt_ann_t ann; stmt = bsi_stmt (si); ann = stmt_ann (stmt); /* If the statement has no virtual operands, then it doesn't make structure references that we care about. */ if (NUM_VDEFS (VDEF_OPS (ann)) == 0 && NUM_VUSES (VUSE_OPS (ann)) == 0) continue; /* Structure references may only appear in certain statements. */ if (TREE_CODE (stmt) != MODIFY_EXPR && TREE_CODE (stmt) != CALL_EXPR && TREE_CODE (stmt) != RETURN_EXPR && TREE_CODE (stmt) != ASM_EXPR) continue; scalarize_stmt (&si); } /* Initialize the scalar replacements for every structure that is a function argument. */ EXECUTE_IF_SET_IN_BITMAP (needs_copy_in, 0, i, { tree var = referenced_var (i); tree list = create_scalar_copies (var, var, SCALAR_FIELD); bsi_insert_on_edge (ENTRY_BLOCK_PTR->succ, list); }); /* Commit edge insertions. */ bsi_commit_edge_inserts (NULL); } /* Scalarize structure references in the statement pointed by SI_P. */ static void scalarize_stmt (block_stmt_iterator *si_p) { tree stmt = bsi_stmt (*si_p); /* Handle assignments. */ if (TREE_CODE (stmt) == MODIFY_EXPR && TREE_CODE (TREE_OPERAND (stmt, 1)) != CALL_EXPR) scalarize_modify_expr (si_p); /* Handle RETURN_EXPR. */ else if (TREE_CODE (stmt) == RETURN_EXPR) scalarize_return_expr (si_p); /* Handle function calls (note that this must be handled after MODIFY_EXPR and RETURN_EXPR because a function call can appear in both). */ else if (get_call_expr_in (stmt) != NULL_TREE) scalarize_call_expr (si_p); /* Handle ASM_EXPRs. */ else if (TREE_CODE (stmt) == ASM_EXPR) scalarize_asm_expr (si_p); } /* Helper for scalarize_stmt to handle assignments. */ static void scalarize_modify_expr (block_stmt_iterator *si_p) { tree stmt = bsi_stmt (*si_p); tree lhs = TREE_OPERAND (stmt, 0); tree rhs = TREE_OPERAND (stmt, 1); /* Found AGGREGATE.FIELD = ... */ if (is_sra_candidate_ref (lhs, false)) { tree sym; vdef_optype vdefs; scalarize_component_ref (stmt, &TREE_OPERAND (stmt, 0)); /* Mark the LHS to be renamed, as we have just removed the previous VDEF for AGGREGATE. The statement should have exactly one VDEF for variable AGGREGATE. */ vdefs = STMT_VDEF_OPS (stmt); if (NUM_VDEFS (vdefs) != 1) abort (); sym = SSA_NAME_VAR (VDEF_RESULT (vdefs, 0)); bitmap_set_bit (vars_to_rename, var_ann (sym)->uid); } /* Found ... = AGGREGATE.FIELD */ else if (is_sra_candidate_ref (rhs, false)) scalarize_component_ref (stmt, &TREE_OPERAND (stmt, 1)); /* Found ... = BIT_FIELD_REF <>. This is similar to a CALL_EXPR, if the operand of the BIT_FIELD_REF is a scalarizable structure, we need to copy from its scalar replacements before doing the bitfield operation. FIXME: BIT_FIELD_REFs are often generated by fold-const.c. This is not always desirable because they obfuscate the original predicates, limiting what the tree optimizers may do. For instance, in testsuite/g++.dg/opt/nrv4.C the use of SRA allows the optimizers to optimize function main() to 'return 0;'. However, the folder generates a BIT_FIELD_REF operation for one of the comparisons, preventing the optimizers from removing all the redundant operations. */ else if (is_sra_candidate_ref (rhs, true)) { tree var = TREE_OPERAND (rhs, 0); emit_scalar_copies (si_p, var, var, FIELD_SCALAR); } /* Found AGGREGATE = ... or ... = AGGREGATE */ else if (DECL_P (lhs) || DECL_P (rhs)) scalarize_structure_assignment (si_p); } /* Scalarize structure references in LIST. Use DONE to avoid duplicates. */ static inline void scalarize_tree_list (tree list, block_stmt_iterator *si_p, bitmap done) { tree op; for (op = list; op; op = TREE_CHAIN (op)) { tree arg = TREE_VALUE (op); if (is_sra_candidate_decl (arg)) { int index = var_ann (arg)->uid; if (!bitmap_bit_p (done, index)) { emit_scalar_copies (si_p, arg, arg, FIELD_SCALAR); bitmap_set_bit (done, index); } } else if (is_sra_candidate_ref (arg, false)) { tree stmt = bsi_stmt (*si_p); scalarize_component_ref (stmt, &TREE_VALUE (op)); } } } /* Helper for scalarize_stmt to handle function calls. */ static void scalarize_call_expr (block_stmt_iterator *si_p) { tree stmt = bsi_stmt (*si_p); tree call = (TREE_CODE (stmt) == MODIFY_EXPR) ? TREE_OPERAND (stmt, 1) : stmt; struct bitmap_head_def done_head; /* First scalarize the arguments. Order is important, because the copy operations for the arguments need to go before the call. Scalarization of the return value needs to go after the call. */ bitmap_initialize (&done_head, 1); scalarize_tree_list (TREE_OPERAND (call, 1), si_p, &done_head); bitmap_clear (&done_head); /* Scalarize the return value, if any. */ if (TREE_CODE (stmt) == MODIFY_EXPR) { tree var = TREE_OPERAND (stmt, 0); /* If the LHS of the assignment is a scalarizable structure, insert copies into the scalar replacements after the call. */ if (is_sra_candidate_decl (var)) { tree list = create_scalar_copies (var, var, SCALAR_FIELD); if (EXPR_HAS_LOCATION (stmt)) annotate_all_with_locus (&list, EXPR_LOCATION (stmt)); if (stmt_ends_bb_p (stmt)) insert_edge_copies (list, bb_for_stmt (stmt)); else bsi_insert_after (si_p, list, BSI_NEW_STMT); } } } /* Helper for scalarize_stmt to handle ASM_EXPRs. */ static void scalarize_asm_expr (block_stmt_iterator *si_p) { tree stmt = bsi_stmt (*si_p); struct bitmap_head_def done_head; bitmap_initialize (&done_head, 1); scalarize_tree_list (ASM_INPUTS (stmt), si_p, &done_head); scalarize_tree_list (ASM_OUTPUTS (stmt), si_p, &done_head); bitmap_clear (&done_head); /* ??? Process outputs after the asm. */ } /* Helper for scalarize_stmt to handle return expressions. */ static void scalarize_return_expr (block_stmt_iterator *si_p) { tree stmt = bsi_stmt (*si_p); tree op = TREE_OPERAND (stmt, 0); if (op == NULL_TREE) return; /* Handle a bare RESULT_DECL. This will handle for types needed constructors, or possibly after NRV type optimizations. */ if (is_sra_candidate_decl (op)) emit_scalar_copies (si_p, op, op, FIELD_SCALAR); else if (TREE_CODE (op) == MODIFY_EXPR) { tree *rhs_p = &TREE_OPERAND (op, 1); tree rhs = *rhs_p; /* Handle 'return STRUCTURE;' */ if (is_sra_candidate_decl (rhs)) emit_scalar_copies (si_p, rhs, rhs, FIELD_SCALAR); /* Handle 'return STRUCTURE.FIELD;' */ else if (is_sra_candidate_ref (rhs, false)) scalarize_component_ref (stmt, rhs_p); /* Handle 'return CALL_EXPR;' */ else if (TREE_CODE (rhs) == CALL_EXPR) { struct bitmap_head_def done_head; bitmap_initialize (&done_head, 1); scalarize_tree_list (TREE_OPERAND (rhs, 1), si_p, &done_head); bitmap_clear (&done_head); } } } /* Debugging dump for the scalar replacement map. */ static int dump_sra_map_trav (void **slot, void *data) { struct sra_elt *e = *slot; FILE *f = data; switch (e->kind) { case REALPART_EXPR: fputs ("__real__ ", f); print_generic_expr (dump_file, e->base, dump_flags); fprintf (f, " -> %s\n", get_name (e->replace)); break; case IMAGPART_EXPR: fputs ("__imag__ ", f); print_generic_expr (dump_file, e->base, dump_flags); fprintf (f, " -> %s\n", get_name (e->replace)); break; case COMPONENT_REF: print_generic_expr (dump_file, e->base, dump_flags); fprintf (f, ".%s -> %s\n", get_name (e->field), get_name (e->replace)); break; default: abort (); } return 1; } static void dump_sra_map (FILE *f) { fputs ("Scalar replacements:\n", f); htab_traverse_noresize (sra_map, dump_sra_map_trav, f); fputs ("\n\n", f); } /* Main entry point to Scalar Replacement of Aggregates (SRA). This pass re-writes non-aliased structure references into scalar temporaries. The goal is to expose some/all structures to the scalar optimizers. FNDECL is the function to process. VARS_TO_RENAME_P is a pointer to the set of variables that need to be renamed into SSA after this pass is done. These are going to be all the new scalars created by the SRA process. Notice that since this pass creates new variables, the bitmap representing all the variables in the program will be re-sized here. PHASE indicates which dump file from the DUMP_FILES array to use when dumping debugging information. TODO 1- Scalarize COMPLEX_TYPEs 2- Scalarize ARRAY_REFs that are always referenced with a constant index. 3- Timings to determine when scalarization is not profitable. 4- Determine what's a good value for MAX_NFIELDS_FOR_SRA. */ static void tree_sra (void) { /* Initialize local variables. */ sra_candidates = BITMAP_XMALLOC (); sra_map = NULL; needs_copy_in = NULL; /* Find structures to be scalarized. */ if (!find_candidates_for_sra ()) { BITMAP_XFREE (sra_candidates); return; } /* If we found any, re-write structure references with their corresponding scalar replacement. */ sra_map = htab_create (101, sra_elt_hash, sra_elt_eq, free); needs_copy_in = BITMAP_XMALLOC (); scalarize_structures (); if (dump_file) dump_sra_map (dump_file); /* Free allocated memory. */ htab_delete (sra_map); sra_map = NULL; BITMAP_XFREE (needs_copy_in); BITMAP_XFREE (sra_candidates); } static bool gate_sra (void) { return flag_tree_sra != 0; } struct tree_opt_pass pass_sra = { "sra", /* name */ gate_sra, /* gate */ tree_sra, /* execute */ NULL, /* sub */ NULL, /* next */ 0, /* static_pass_number */ TV_TREE_SRA, /* tv_id */ PROP_cfg | PROP_ssa, /* properties_required */ 0, /* properties_provided */ 0, /* properties_destroyed */ 0, /* todo_flags_start */ TODO_dump_func | TODO_rename_vars | TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */ };