| /* Scalar Replacement of Aggregates (SRA) converts some structure |
| references into scalar references, exposing them to the scalar |
| optimizers. |
| Copyright (C) 2008-2021 Free Software Foundation, Inc. |
| Contributed by Martin Jambor <mjambor@suse.cz> |
| |
| 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 3, 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 COPYING3. If not see |
| <http://www.gnu.org/licenses/>. */ |
| |
| /* This file implements Scalar Reduction of Aggregates (SRA). SRA is run |
| twice, once in the early stages of compilation (early SRA) and once in the |
| late stages (late SRA). The aim of both is to turn references to scalar |
| parts of aggregates into uses of independent scalar variables. |
| |
| The two passes are nearly identical, the only difference is that early SRA |
| does not scalarize unions which are used as the result in a GIMPLE_RETURN |
| statement because together with inlining this can lead to weird type |
| conversions. |
| |
| Both passes operate in four stages: |
| |
| 1. The declarations that have properties which make them candidates for |
| scalarization are identified in function find_var_candidates(). The |
| candidates are stored in candidate_bitmap. |
| |
| 2. The function body is scanned. In the process, declarations which are |
| used in a manner that prevent their scalarization are removed from the |
| candidate bitmap. More importantly, for every access into an aggregate, |
| an access structure (struct access) is created by create_access() and |
| stored in a vector associated with the aggregate. Among other |
| information, the aggregate declaration, the offset and size of the access |
| and its type are stored in the structure. |
| |
| On a related note, assign_link structures are created for every assign |
| statement between candidate aggregates and attached to the related |
| accesses. |
| |
| 3. The vectors of accesses are analyzed. They are first sorted according to |
| their offset and size and then scanned for partially overlapping accesses |
| (i.e. those which overlap but one is not entirely within another). Such |
| an access disqualifies the whole aggregate from being scalarized. |
| |
| If there is no such inhibiting overlap, a representative access structure |
| is chosen for every unique combination of offset and size. Afterwards, |
| the pass builds a set of trees from these structures, in which children |
| of an access are within their parent (in terms of offset and size). |
| |
| Then accesses are propagated whenever possible (i.e. in cases when it |
| does not create a partially overlapping access) across assign_links from |
| the right hand side to the left hand side. |
| |
| Then the set of trees for each declaration is traversed again and those |
| accesses which should be replaced by a scalar are identified. |
| |
| 4. The function is traversed again, and for every reference into an |
| aggregate that has some component which is about to be scalarized, |
| statements are amended and new statements are created as necessary. |
| Finally, if a parameter got scalarized, the scalar replacements are |
| initialized with values from respective parameter aggregates. */ |
| |
| #include "config.h" |
| #include "system.h" |
| #include "coretypes.h" |
| #include "backend.h" |
| #include "target.h" |
| #include "rtl.h" |
| #include "tree.h" |
| #include "gimple.h" |
| #include "predict.h" |
| #include "alloc-pool.h" |
| #include "tree-pass.h" |
| #include "ssa.h" |
| #include "cgraph.h" |
| #include "gimple-pretty-print.h" |
| #include "alias.h" |
| #include "fold-const.h" |
| #include "tree-eh.h" |
| #include "stor-layout.h" |
| #include "gimplify.h" |
| #include "gimple-iterator.h" |
| #include "gimplify-me.h" |
| #include "gimple-walk.h" |
| #include "tree-cfg.h" |
| #include "tree-dfa.h" |
| #include "tree-ssa.h" |
| #include "dbgcnt.h" |
| #include "builtins.h" |
| #include "tree-sra.h" |
| |
| |
| /* Enumeration of all aggregate reductions we can do. */ |
| enum sra_mode { SRA_MODE_EARLY_IPA, /* early call regularization */ |
| SRA_MODE_EARLY_INTRA, /* early intraprocedural SRA */ |
| SRA_MODE_INTRA }; /* late intraprocedural SRA */ |
| |
| /* Global variable describing which aggregate reduction we are performing at |
| the moment. */ |
| static enum sra_mode sra_mode; |
| |
| struct assign_link; |
| |
| /* ACCESS represents each access to an aggregate variable (as a whole or a |
| part). It can also represent a group of accesses that refer to exactly the |
| same fragment of an aggregate (i.e. those that have exactly the same offset |
| and size). Such representatives for a single aggregate, once determined, |
| are linked in a linked list and have the group fields set. |
| |
| Moreover, when doing intraprocedural SRA, a tree is built from those |
| representatives (by the means of first_child and next_sibling pointers), in |
| which all items in a subtree are "within" the root, i.e. their offset is |
| greater or equal to offset of the root and offset+size is smaller or equal |
| to offset+size of the root. Children of an access are sorted by offset. |
| |
| Note that accesses to parts of vector and complex number types always |
| represented by an access to the whole complex number or a vector. It is a |
| duty of the modifying functions to replace them appropriately. */ |
| |
| struct access |
| { |
| /* Values returned by `get_ref_base_and_extent' for each component reference |
| If EXPR isn't a component reference just set `BASE = EXPR', `OFFSET = 0', |
| `SIZE = TREE_SIZE (TREE_TYPE (expr))'. */ |
| HOST_WIDE_INT offset; |
| HOST_WIDE_INT size; |
| tree base; |
| |
| /* Expression. It is context dependent so do not use it to create new |
| expressions to access the original aggregate. See PR 42154 for a |
| testcase. */ |
| tree expr; |
| /* Type. */ |
| tree type; |
| |
| /* The statement this access belongs to. */ |
| gimple *stmt; |
| |
| /* Next group representative for this aggregate. */ |
| struct access *next_grp; |
| |
| /* Pointer to the group representative. Pointer to itself if the struct is |
| the representative. */ |
| struct access *group_representative; |
| |
| /* After access tree has been constructed, this points to the parent of the |
| current access, if there is one. NULL for roots. */ |
| struct access *parent; |
| |
| /* If this access has any children (in terms of the definition above), this |
| points to the first one. */ |
| struct access *first_child; |
| |
| /* In intraprocedural SRA, pointer to the next sibling in the access tree as |
| described above. */ |
| struct access *next_sibling; |
| |
| /* Pointers to the first and last element in the linked list of assign |
| links for propagation from LHS to RHS. */ |
| struct assign_link *first_rhs_link, *last_rhs_link; |
| |
| /* Pointers to the first and last element in the linked list of assign |
| links for propagation from LHS to RHS. */ |
| struct assign_link *first_lhs_link, *last_lhs_link; |
| |
| /* Pointer to the next access in the work queues. */ |
| struct access *next_rhs_queued, *next_lhs_queued; |
| |
| /* Replacement variable for this access "region." Never to be accessed |
| directly, always only by the means of get_access_replacement() and only |
| when grp_to_be_replaced flag is set. */ |
| tree replacement_decl; |
| |
| /* Is this access made in reverse storage order? */ |
| unsigned reverse : 1; |
| |
| /* Is this particular access write access? */ |
| unsigned write : 1; |
| |
| /* Is this access currently in the rhs work queue? */ |
| unsigned grp_rhs_queued : 1; |
| |
| /* Is this access currently in the lhs work queue? */ |
| unsigned grp_lhs_queued : 1; |
| |
| /* Does this group contain a write access? This flag is propagated down the |
| access tree. */ |
| unsigned grp_write : 1; |
| |
| /* Does this group contain a read access? This flag is propagated down the |
| access tree. */ |
| unsigned grp_read : 1; |
| |
| /* Does this group contain a read access that comes from an assignment |
| statement? This flag is propagated down the access tree. */ |
| unsigned grp_assignment_read : 1; |
| |
| /* Does this group contain a write access that comes from an assignment |
| statement? This flag is propagated down the access tree. */ |
| unsigned grp_assignment_write : 1; |
| |
| /* Does this group contain a read access through a scalar type? This flag is |
| not propagated in the access tree in any direction. */ |
| unsigned grp_scalar_read : 1; |
| |
| /* Does this group contain a write access through a scalar type? This flag |
| is not propagated in the access tree in any direction. */ |
| unsigned grp_scalar_write : 1; |
| |
| /* In a root of an access tree, true means that the entire tree should be |
| totally scalarized - that all scalar leafs should be scalarized and |
| non-root grp_total_scalarization accesses should be honored. Otherwise, |
| non-root accesses with grp_total_scalarization should never get scalar |
| replacements. */ |
| unsigned grp_total_scalarization : 1; |
| |
| /* Other passes of the analysis use this bit to make function |
| analyze_access_subtree create scalar replacements for this group if |
| possible. */ |
| unsigned grp_hint : 1; |
| |
| /* Is the subtree rooted in this access fully covered by scalar |
| replacements? */ |
| unsigned grp_covered : 1; |
| |
| /* If set to true, this access and all below it in an access tree must not be |
| scalarized. */ |
| unsigned grp_unscalarizable_region : 1; |
| |
| /* Whether data have been written to parts of the aggregate covered by this |
| access which is not to be scalarized. This flag is propagated up in the |
| access tree. */ |
| unsigned grp_unscalarized_data : 1; |
| |
| /* Set if all accesses in the group consist of the same chain of |
| COMPONENT_REFs and ARRAY_REFs. */ |
| unsigned grp_same_access_path : 1; |
| |
| /* Does this access and/or group contain a write access through a |
| BIT_FIELD_REF? */ |
| unsigned grp_partial_lhs : 1; |
| |
| /* Set when a scalar replacement should be created for this variable. */ |
| unsigned grp_to_be_replaced : 1; |
| |
| /* Set when we want a replacement for the sole purpose of having it in |
| generated debug statements. */ |
| unsigned grp_to_be_debug_replaced : 1; |
| |
| /* Should TREE_NO_WARNING of a replacement be set? */ |
| unsigned grp_no_warning : 1; |
| }; |
| |
| typedef struct access *access_p; |
| |
| |
| /* Alloc pool for allocating access structures. */ |
| static object_allocator<struct access> access_pool ("SRA accesses"); |
| |
| /* A structure linking lhs and rhs accesses from an aggregate assignment. They |
| are used to propagate subaccesses from rhs to lhs and vice versa as long as |
| they don't conflict with what is already there. In the RHS->LHS direction, |
| we also propagate grp_write flag to lazily mark that the access contains any |
| meaningful data. */ |
| struct assign_link |
| { |
| struct access *lacc, *racc; |
| struct assign_link *next_rhs, *next_lhs; |
| }; |
| |
| /* Alloc pool for allocating assign link structures. */ |
| static object_allocator<assign_link> assign_link_pool ("SRA links"); |
| |
| /* Base (tree) -> Vector (vec<access_p> *) map. */ |
| static hash_map<tree, auto_vec<access_p> > *base_access_vec; |
| |
| /* Hash to limit creation of artificial accesses */ |
| static hash_map<tree, unsigned> *propagation_budget; |
| |
| /* Candidate hash table helpers. */ |
| |
| struct uid_decl_hasher : nofree_ptr_hash <tree_node> |
| { |
| static inline hashval_t hash (const tree_node *); |
| static inline bool equal (const tree_node *, const tree_node *); |
| }; |
| |
| /* Hash a tree in a uid_decl_map. */ |
| |
| inline hashval_t |
| uid_decl_hasher::hash (const tree_node *item) |
| { |
| return item->decl_minimal.uid; |
| } |
| |
| /* Return true if the DECL_UID in both trees are equal. */ |
| |
| inline bool |
| uid_decl_hasher::equal (const tree_node *a, const tree_node *b) |
| { |
| return (a->decl_minimal.uid == b->decl_minimal.uid); |
| } |
| |
| /* Set of candidates. */ |
| static bitmap candidate_bitmap; |
| static hash_table<uid_decl_hasher> *candidates; |
| |
| /* For a candidate UID return the candidates decl. */ |
| |
| static inline tree |
| candidate (unsigned uid) |
| { |
| tree_node t; |
| t.decl_minimal.uid = uid; |
| return candidates->find_with_hash (&t, static_cast <hashval_t> (uid)); |
| } |
| |
| /* Bitmap of candidates which we should try to entirely scalarize away and |
| those which cannot be (because they are and need be used as a whole). */ |
| static bitmap should_scalarize_away_bitmap, cannot_scalarize_away_bitmap; |
| |
| /* Bitmap of candidates in the constant pool, which cannot be scalarized |
| because this would produce non-constant expressions (e.g. Ada). */ |
| static bitmap disqualified_constants; |
| |
| /* Obstack for creation of fancy names. */ |
| static struct obstack name_obstack; |
| |
| /* Head of a linked list of accesses that need to have its subaccesses |
| propagated to their assignment counterparts. */ |
| static struct access *rhs_work_queue_head, *lhs_work_queue_head; |
| |
| /* Dump contents of ACCESS to file F in a human friendly way. If GRP is true, |
| representative fields are dumped, otherwise those which only describe the |
| individual access are. */ |
| |
| static struct |
| { |
| /* Number of processed aggregates is readily available in |
| analyze_all_variable_accesses and so is not stored here. */ |
| |
| /* Number of created scalar replacements. */ |
| int replacements; |
| |
| /* Number of times sra_modify_expr or sra_modify_assign themselves changed an |
| expression. */ |
| int exprs; |
| |
| /* Number of statements created by generate_subtree_copies. */ |
| int subtree_copies; |
| |
| /* Number of statements created by load_assign_lhs_subreplacements. */ |
| int subreplacements; |
| |
| /* Number of times sra_modify_assign has deleted a statement. */ |
| int deleted; |
| |
| /* Number of times sra_modify_assign has to deal with subaccesses of LHS and |
| RHS reparately due to type conversions or nonexistent matching |
| references. */ |
| int separate_lhs_rhs_handling; |
| |
| /* Number of parameters that were removed because they were unused. */ |
| int deleted_unused_parameters; |
| |
| /* Number of scalars passed as parameters by reference that have been |
| converted to be passed by value. */ |
| int scalar_by_ref_to_by_val; |
| |
| /* Number of aggregate parameters that were replaced by one or more of their |
| components. */ |
| int aggregate_params_reduced; |
| |
| /* Numbber of components created when splitting aggregate parameters. */ |
| int param_reductions_created; |
| } sra_stats; |
| |
| static void |
| dump_access (FILE *f, struct access *access, bool grp) |
| { |
| fprintf (f, "access { "); |
| fprintf (f, "base = (%d)'", DECL_UID (access->base)); |
| print_generic_expr (f, access->base); |
| fprintf (f, "', offset = " HOST_WIDE_INT_PRINT_DEC, access->offset); |
| fprintf (f, ", size = " HOST_WIDE_INT_PRINT_DEC, access->size); |
| fprintf (f, ", expr = "); |
| print_generic_expr (f, access->expr); |
| fprintf (f, ", type = "); |
| print_generic_expr (f, access->type); |
| fprintf (f, ", reverse = %d", access->reverse); |
| if (grp) |
| fprintf (f, ", grp_read = %d, grp_write = %d, grp_assignment_read = %d, " |
| "grp_assignment_write = %d, grp_scalar_read = %d, " |
| "grp_scalar_write = %d, grp_total_scalarization = %d, " |
| "grp_hint = %d, grp_covered = %d, " |
| "grp_unscalarizable_region = %d, grp_unscalarized_data = %d, " |
| "grp_same_access_path = %d, grp_partial_lhs = %d, " |
| "grp_to_be_replaced = %d, grp_to_be_debug_replaced = %d}\n", |
| access->grp_read, access->grp_write, access->grp_assignment_read, |
| access->grp_assignment_write, access->grp_scalar_read, |
| access->grp_scalar_write, access->grp_total_scalarization, |
| access->grp_hint, access->grp_covered, |
| access->grp_unscalarizable_region, access->grp_unscalarized_data, |
| access->grp_same_access_path, access->grp_partial_lhs, |
| access->grp_to_be_replaced, access->grp_to_be_debug_replaced); |
| else |
| fprintf (f, ", write = %d, grp_total_scalarization = %d, " |
| "grp_partial_lhs = %d}\n", |
| access->write, access->grp_total_scalarization, |
| access->grp_partial_lhs); |
| } |
| |
| /* Dump a subtree rooted in ACCESS to file F, indent by LEVEL. */ |
| |
| static void |
| dump_access_tree_1 (FILE *f, struct access *access, int level) |
| { |
| do |
| { |
| int i; |
| |
| for (i = 0; i < level; i++) |
| fputs ("* ", f); |
| |
| dump_access (f, access, true); |
| |
| if (access->first_child) |
| dump_access_tree_1 (f, access->first_child, level + 1); |
| |
| access = access->next_sibling; |
| } |
| while (access); |
| } |
| |
| /* Dump all access trees for a variable, given the pointer to the first root in |
| ACCESS. */ |
| |
| static void |
| dump_access_tree (FILE *f, struct access *access) |
| { |
| for (; access; access = access->next_grp) |
| dump_access_tree_1 (f, access, 0); |
| } |
| |
| /* Return true iff ACC is non-NULL and has subaccesses. */ |
| |
| static inline bool |
| access_has_children_p (struct access *acc) |
| { |
| return acc && acc->first_child; |
| } |
| |
| /* Return true iff ACC is (partly) covered by at least one replacement. */ |
| |
| static bool |
| access_has_replacements_p (struct access *acc) |
| { |
| struct access *child; |
| if (acc->grp_to_be_replaced) |
| return true; |
| for (child = acc->first_child; child; child = child->next_sibling) |
| if (access_has_replacements_p (child)) |
| return true; |
| return false; |
| } |
| |
| /* Return a vector of pointers to accesses for the variable given in BASE or |
| NULL if there is none. */ |
| |
| static vec<access_p> * |
| get_base_access_vector (tree base) |
| { |
| return base_access_vec->get (base); |
| } |
| |
| /* Find an access with required OFFSET and SIZE in a subtree of accesses rooted |
| in ACCESS. Return NULL if it cannot be found. */ |
| |
| static struct access * |
| find_access_in_subtree (struct access *access, HOST_WIDE_INT offset, |
| HOST_WIDE_INT size) |
| { |
| while (access && (access->offset != offset || access->size != size)) |
| { |
| struct access *child = access->first_child; |
| |
| while (child && (child->offset + child->size <= offset)) |
| child = child->next_sibling; |
| access = child; |
| } |
| |
| /* Total scalarization does not replace single field structures with their |
| single field but rather creates an access for them underneath. Look for |
| it. */ |
| if (access) |
| while (access->first_child |
| && access->first_child->offset == offset |
| && access->first_child->size == size) |
| access = access->first_child; |
| |
| return access; |
| } |
| |
| /* Return the first group representative for DECL or NULL if none exists. */ |
| |
| static struct access * |
| get_first_repr_for_decl (tree base) |
| { |
| vec<access_p> *access_vec; |
| |
| access_vec = get_base_access_vector (base); |
| if (!access_vec) |
| return NULL; |
| |
| return (*access_vec)[0]; |
| } |
| |
| /* Find an access representative for the variable BASE and given OFFSET and |
| SIZE. Requires that access trees have already been built. Return NULL if |
| it cannot be found. */ |
| |
| static struct access * |
| get_var_base_offset_size_access (tree base, HOST_WIDE_INT offset, |
| HOST_WIDE_INT size) |
| { |
| struct access *access; |
| |
| access = get_first_repr_for_decl (base); |
| while (access && (access->offset + access->size <= offset)) |
| access = access->next_grp; |
| if (!access) |
| return NULL; |
| |
| return find_access_in_subtree (access, offset, size); |
| } |
| |
| /* Add LINK to the linked list of assign links of RACC. */ |
| |
| static void |
| add_link_to_rhs (struct access *racc, struct assign_link *link) |
| { |
| gcc_assert (link->racc == racc); |
| |
| if (!racc->first_rhs_link) |
| { |
| gcc_assert (!racc->last_rhs_link); |
| racc->first_rhs_link = link; |
| } |
| else |
| racc->last_rhs_link->next_rhs = link; |
| |
| racc->last_rhs_link = link; |
| link->next_rhs = NULL; |
| } |
| |
| /* Add LINK to the linked list of lhs assign links of LACC. */ |
| |
| static void |
| add_link_to_lhs (struct access *lacc, struct assign_link *link) |
| { |
| gcc_assert (link->lacc == lacc); |
| |
| if (!lacc->first_lhs_link) |
| { |
| gcc_assert (!lacc->last_lhs_link); |
| lacc->first_lhs_link = link; |
| } |
| else |
| lacc->last_lhs_link->next_lhs = link; |
| |
| lacc->last_lhs_link = link; |
| link->next_lhs = NULL; |
| } |
| |
| /* Move all link structures in their linked list in OLD_ACC to the linked list |
| in NEW_ACC. */ |
| static void |
| relink_to_new_repr (struct access *new_acc, struct access *old_acc) |
| { |
| if (old_acc->first_rhs_link) |
| { |
| |
| if (new_acc->first_rhs_link) |
| { |
| gcc_assert (!new_acc->last_rhs_link->next_rhs); |
| gcc_assert (!old_acc->last_rhs_link |
| || !old_acc->last_rhs_link->next_rhs); |
| |
| new_acc->last_rhs_link->next_rhs = old_acc->first_rhs_link; |
| new_acc->last_rhs_link = old_acc->last_rhs_link; |
| } |
| else |
| { |
| gcc_assert (!new_acc->last_rhs_link); |
| |
| new_acc->first_rhs_link = old_acc->first_rhs_link; |
| new_acc->last_rhs_link = old_acc->last_rhs_link; |
| } |
| old_acc->first_rhs_link = old_acc->last_rhs_link = NULL; |
| } |
| else |
| gcc_assert (!old_acc->last_rhs_link); |
| |
| if (old_acc->first_lhs_link) |
| { |
| |
| if (new_acc->first_lhs_link) |
| { |
| gcc_assert (!new_acc->last_lhs_link->next_lhs); |
| gcc_assert (!old_acc->last_lhs_link |
| || !old_acc->last_lhs_link->next_lhs); |
| |
| new_acc->last_lhs_link->next_lhs = old_acc->first_lhs_link; |
| new_acc->last_lhs_link = old_acc->last_lhs_link; |
| } |
| else |
| { |
| gcc_assert (!new_acc->last_lhs_link); |
| |
| new_acc->first_lhs_link = old_acc->first_lhs_link; |
| new_acc->last_lhs_link = old_acc->last_lhs_link; |
| } |
| old_acc->first_lhs_link = old_acc->last_lhs_link = NULL; |
| } |
| else |
| gcc_assert (!old_acc->last_lhs_link); |
| |
| } |
| |
| /* Add ACCESS to the work to queue for propagation of subaccesses from RHS to |
| LHS (which is actually a stack). */ |
| |
| static void |
| add_access_to_rhs_work_queue (struct access *access) |
| { |
| if (access->first_rhs_link && !access->grp_rhs_queued) |
| { |
| gcc_assert (!access->next_rhs_queued); |
| access->next_rhs_queued = rhs_work_queue_head; |
| access->grp_rhs_queued = 1; |
| rhs_work_queue_head = access; |
| } |
| } |
| |
| /* Add ACCESS to the work to queue for propagation of subaccesses from LHS to |
| RHS (which is actually a stack). */ |
| |
| static void |
| add_access_to_lhs_work_queue (struct access *access) |
| { |
| if (access->first_lhs_link && !access->grp_lhs_queued) |
| { |
| gcc_assert (!access->next_lhs_queued); |
| access->next_lhs_queued = lhs_work_queue_head; |
| access->grp_lhs_queued = 1; |
| lhs_work_queue_head = access; |
| } |
| } |
| |
| /* Pop an access from the work queue for propagating from RHS to LHS, and |
| return it, assuming there is one. */ |
| |
| static struct access * |
| pop_access_from_rhs_work_queue (void) |
| { |
| struct access *access = rhs_work_queue_head; |
| |
| rhs_work_queue_head = access->next_rhs_queued; |
| access->next_rhs_queued = NULL; |
| access->grp_rhs_queued = 0; |
| return access; |
| } |
| |
| /* Pop an access from the work queue for propagating from LHS to RHS, and |
| return it, assuming there is one. */ |
| |
| static struct access * |
| pop_access_from_lhs_work_queue (void) |
| { |
| struct access *access = lhs_work_queue_head; |
| |
| lhs_work_queue_head = access->next_lhs_queued; |
| access->next_lhs_queued = NULL; |
| access->grp_lhs_queued = 0; |
| return access; |
| } |
| |
| /* Allocate necessary structures. */ |
| |
| static void |
| sra_initialize (void) |
| { |
| candidate_bitmap = BITMAP_ALLOC (NULL); |
| candidates = new hash_table<uid_decl_hasher> |
| (vec_safe_length (cfun->local_decls) / 2); |
| should_scalarize_away_bitmap = BITMAP_ALLOC (NULL); |
| cannot_scalarize_away_bitmap = BITMAP_ALLOC (NULL); |
| disqualified_constants = BITMAP_ALLOC (NULL); |
| gcc_obstack_init (&name_obstack); |
| base_access_vec = new hash_map<tree, auto_vec<access_p> >; |
| memset (&sra_stats, 0, sizeof (sra_stats)); |
| } |
| |
| /* Deallocate all general structures. */ |
| |
| static void |
| sra_deinitialize (void) |
| { |
| BITMAP_FREE (candidate_bitmap); |
| delete candidates; |
| candidates = NULL; |
| BITMAP_FREE (should_scalarize_away_bitmap); |
| BITMAP_FREE (cannot_scalarize_away_bitmap); |
| BITMAP_FREE (disqualified_constants); |
| access_pool.release (); |
| assign_link_pool.release (); |
| obstack_free (&name_obstack, NULL); |
| |
| delete base_access_vec; |
| } |
| |
| /* Return true if DECL is a VAR_DECL in the constant pool, false otherwise. */ |
| |
| static bool constant_decl_p (tree decl) |
| { |
| return VAR_P (decl) && DECL_IN_CONSTANT_POOL (decl); |
| } |
| |
| /* Remove DECL from candidates for SRA and write REASON to the dump file if |
| there is one. */ |
| |
| static void |
| disqualify_candidate (tree decl, const char *reason) |
| { |
| if (bitmap_clear_bit (candidate_bitmap, DECL_UID (decl))) |
| candidates->remove_elt_with_hash (decl, DECL_UID (decl)); |
| if (constant_decl_p (decl)) |
| bitmap_set_bit (disqualified_constants, DECL_UID (decl)); |
| |
| if (dump_file && (dump_flags & TDF_DETAILS)) |
| { |
| fprintf (dump_file, "! Disqualifying "); |
| print_generic_expr (dump_file, decl); |
| fprintf (dump_file, " - %s\n", reason); |
| } |
| } |
| |
| /* Return true iff the type contains a field or an element which does not allow |
| scalarization. Use VISITED_TYPES to avoid re-checking already checked |
| (sub-)types. */ |
| |
| static bool |
| type_internals_preclude_sra_p_1 (tree type, const char **msg, |
| hash_set<tree> *visited_types) |
| { |
| tree fld; |
| tree et; |
| |
| if (visited_types->contains (type)) |
| return false; |
| visited_types->add (type); |
| |
| switch (TREE_CODE (type)) |
| { |
| case RECORD_TYPE: |
| case UNION_TYPE: |
| case QUAL_UNION_TYPE: |
| for (fld = TYPE_FIELDS (type); fld; fld = DECL_CHAIN (fld)) |
| if (TREE_CODE (fld) == FIELD_DECL) |
| { |
| if (TREE_CODE (fld) == FUNCTION_DECL) |
| continue; |
| tree ft = TREE_TYPE (fld); |
| |
| if (TREE_THIS_VOLATILE (fld)) |
| { |
| *msg = "volatile structure field"; |
| return true; |
| } |
| if (!DECL_FIELD_OFFSET (fld)) |
| { |
| *msg = "no structure field offset"; |
| return true; |
| } |
| if (!DECL_SIZE (fld)) |
| { |
| *msg = "zero structure field size"; |
| return true; |
| } |
| if (!tree_fits_uhwi_p (DECL_FIELD_OFFSET (fld))) |
| { |
| *msg = "structure field offset not fixed"; |
| return true; |
| } |
| if (!tree_fits_uhwi_p (DECL_SIZE (fld))) |
| { |
| *msg = "structure field size not fixed"; |
| return true; |
| } |
| if (!tree_fits_shwi_p (bit_position (fld))) |
| { |
| *msg = "structure field size too big"; |
| return true; |
| } |
| if (AGGREGATE_TYPE_P (ft) |
| && int_bit_position (fld) % BITS_PER_UNIT != 0) |
| { |
| *msg = "structure field is bit field"; |
| return true; |
| } |
| |
| if (AGGREGATE_TYPE_P (ft) |
| && type_internals_preclude_sra_p_1 (ft, msg, visited_types)) |
| return true; |
| } |
| |
| return false; |
| |
| case ARRAY_TYPE: |
| et = TREE_TYPE (type); |
| |
| if (TYPE_VOLATILE (et)) |
| { |
| *msg = "element type is volatile"; |
| return true; |
| } |
| |
| if (AGGREGATE_TYPE_P (et) |
| && type_internals_preclude_sra_p_1 (et, msg, visited_types)) |
| return true; |
| |
| return false; |
| |
| default: |
| return false; |
| } |
| } |
| |
| /* Return true iff the type contains a field or an element which does not allow |
| scalarization. */ |
| |
| bool |
| type_internals_preclude_sra_p (tree type, const char **msg) |
| { |
| hash_set<tree> visited_types; |
| return type_internals_preclude_sra_p_1 (type, msg, &visited_types); |
| } |
| |
| |
| /* Allocate an access structure for BASE, OFFSET and SIZE, clear it, fill in |
| the three fields. Also add it to the vector of accesses corresponding to |
| the base. Finally, return the new access. */ |
| |
| static struct access * |
| create_access_1 (tree base, HOST_WIDE_INT offset, HOST_WIDE_INT size) |
| { |
| struct access *access = access_pool.allocate (); |
| |
| memset (access, 0, sizeof (struct access)); |
| access->base = base; |
| access->offset = offset; |
| access->size = size; |
| |
| base_access_vec->get_or_insert (base).safe_push (access); |
| |
| return access; |
| } |
| |
| static bool maybe_add_sra_candidate (tree); |
| |
| /* Create and insert access for EXPR. Return created access, or NULL if it is |
| not possible. Also scan for uses of constant pool as we go along and add |
| to candidates. */ |
| |
| static struct access * |
| create_access (tree expr, gimple *stmt, bool write) |
| { |
| struct access *access; |
| poly_int64 poffset, psize, pmax_size; |
| tree base = expr; |
| bool reverse, unscalarizable_region = false; |
| |
| base = get_ref_base_and_extent (expr, &poffset, &psize, &pmax_size, |
| &reverse); |
| |
| /* For constant-pool entries, check we can substitute the constant value. */ |
| if (constant_decl_p (base)) |
| { |
| gcc_assert (!bitmap_bit_p (disqualified_constants, DECL_UID (base))); |
| if (expr != base |
| && !is_gimple_reg_type (TREE_TYPE (expr)) |
| && dump_file && (dump_flags & TDF_DETAILS)) |
| { |
| /* This occurs in Ada with accesses to ARRAY_RANGE_REFs, |
| and elements of multidimensional arrays (which are |
| multi-element arrays in their own right). */ |
| fprintf (dump_file, "Allowing non-reg-type load of part" |
| " of constant-pool entry: "); |
| print_generic_expr (dump_file, expr); |
| } |
| maybe_add_sra_candidate (base); |
| } |
| |
| if (!DECL_P (base) || !bitmap_bit_p (candidate_bitmap, DECL_UID (base))) |
| return NULL; |
| |
| HOST_WIDE_INT offset, size, max_size; |
| if (!poffset.is_constant (&offset) |
| || !psize.is_constant (&size) |
| || !pmax_size.is_constant (&max_size)) |
| { |
| disqualify_candidate (base, "Encountered a polynomial-sized access."); |
| return NULL; |
| } |
| |
| if (size != max_size) |
| { |
| size = max_size; |
| unscalarizable_region = true; |
| } |
| if (size == 0) |
| return NULL; |
| if (offset < 0) |
| { |
| disqualify_candidate (base, "Encountered a negative offset access."); |
| return NULL; |
| } |
| if (size < 0) |
| { |
| disqualify_candidate (base, "Encountered an unconstrained access."); |
| return NULL; |
| } |
| if (offset + size > tree_to_shwi (DECL_SIZE (base))) |
| { |
| disqualify_candidate (base, "Encountered an access beyond the base."); |
| return NULL; |
| } |
| |
| access = create_access_1 (base, offset, size); |
| access->expr = expr; |
| access->type = TREE_TYPE (expr); |
| access->write = write; |
| access->grp_unscalarizable_region = unscalarizable_region; |
| access->stmt = stmt; |
| access->reverse = reverse; |
| |
| return access; |
| } |
| |
| |
| /* Return true iff TYPE is scalarizable - i.e. a RECORD_TYPE or fixed-length |
| ARRAY_TYPE with fields that are either of gimple register types (excluding |
| bit-fields) or (recursively) scalarizable types. CONST_DECL must be true if |
| we are considering a decl from constant pool. If it is false, char arrays |
| will be refused. */ |
| |
| static bool |
| scalarizable_type_p (tree type, bool const_decl) |
| { |
| if (is_gimple_reg_type (type)) |
| return true; |
| if (type_contains_placeholder_p (type)) |
| return false; |
| |
| bool have_predecessor_field = false; |
| HOST_WIDE_INT prev_pos = 0; |
| |
| switch (TREE_CODE (type)) |
| { |
| case RECORD_TYPE: |
| for (tree fld = TYPE_FIELDS (type); fld; fld = DECL_CHAIN (fld)) |
| if (TREE_CODE (fld) == FIELD_DECL) |
| { |
| tree ft = TREE_TYPE (fld); |
| |
| if (zerop (DECL_SIZE (fld))) |
| continue; |
| |
| HOST_WIDE_INT pos = int_bit_position (fld); |
| if (have_predecessor_field |
| && pos <= prev_pos) |
| return false; |
| |
| have_predecessor_field = true; |
| prev_pos = pos; |
| |
| if (DECL_BIT_FIELD (fld)) |
| return false; |
| |
| if (!scalarizable_type_p (ft, const_decl)) |
| return false; |
| } |
| |
| return true; |
| |
| case ARRAY_TYPE: |
| { |
| HOST_WIDE_INT min_elem_size; |
| if (const_decl) |
| min_elem_size = 0; |
| else |
| min_elem_size = BITS_PER_UNIT; |
| |
| if (TYPE_DOMAIN (type) == NULL_TREE |
| || !tree_fits_shwi_p (TYPE_SIZE (type)) |
| || !tree_fits_shwi_p (TYPE_SIZE (TREE_TYPE (type))) |
| || (tree_to_shwi (TYPE_SIZE (TREE_TYPE (type))) <= min_elem_size) |
| || !tree_fits_shwi_p (TYPE_MIN_VALUE (TYPE_DOMAIN (type)))) |
| return false; |
| if (tree_to_shwi (TYPE_SIZE (type)) == 0 |
| && TYPE_MAX_VALUE (TYPE_DOMAIN (type)) == NULL_TREE) |
| /* Zero-element array, should not prevent scalarization. */ |
| ; |
| else if ((tree_to_shwi (TYPE_SIZE (type)) <= 0) |
| || !tree_fits_shwi_p (TYPE_MAX_VALUE (TYPE_DOMAIN (type)))) |
| /* Variable-length array, do not allow scalarization. */ |
| return false; |
| |
| tree elem = TREE_TYPE (type); |
| if (!scalarizable_type_p (elem, const_decl)) |
| return false; |
| return true; |
| } |
| default: |
| return false; |
| } |
| } |
| |
| /* Return true if REF has an VIEW_CONVERT_EXPR somewhere in it. */ |
| |
| static inline bool |
| contains_view_convert_expr_p (const_tree ref) |
| { |
| while (handled_component_p (ref)) |
| { |
| if (TREE_CODE (ref) == VIEW_CONVERT_EXPR) |
| return true; |
| ref = TREE_OPERAND (ref, 0); |
| } |
| |
| return false; |
| } |
| |
| /* Return true if REF contains a VIEW_CONVERT_EXPR or a COMPONENT_REF with a |
| bit-field field declaration. If TYPE_CHANGING_P is non-NULL, set the bool |
| it points to will be set if REF contains any of the above or a MEM_REF |
| expression that effectively performs type conversion. */ |
| |
| static bool |
| contains_vce_or_bfcref_p (const_tree ref, bool *type_changing_p = NULL) |
| { |
| while (handled_component_p (ref)) |
| { |
| if (TREE_CODE (ref) == VIEW_CONVERT_EXPR |
| || (TREE_CODE (ref) == COMPONENT_REF |
| && DECL_BIT_FIELD (TREE_OPERAND (ref, 1)))) |
| { |
| if (type_changing_p) |
| *type_changing_p = true; |
| return true; |
| } |
| ref = TREE_OPERAND (ref, 0); |
| } |
| |
| if (!type_changing_p |
| || TREE_CODE (ref) != MEM_REF |
| || TREE_CODE (TREE_OPERAND (ref, 0)) != ADDR_EXPR) |
| return false; |
| |
| tree mem = TREE_OPERAND (TREE_OPERAND (ref, 0), 0); |
| if (TYPE_MAIN_VARIANT (TREE_TYPE (ref)) |
| != TYPE_MAIN_VARIANT (TREE_TYPE (mem))) |
| *type_changing_p = true; |
| |
| return false; |
| } |
| |
| /* Search the given tree for a declaration by skipping handled components and |
| exclude it from the candidates. */ |
| |
| static void |
| disqualify_base_of_expr (tree t, const char *reason) |
| { |
| t = get_base_address (t); |
| if (t && DECL_P (t)) |
| disqualify_candidate (t, reason); |
| } |
| |
| /* Scan expression EXPR and create access structures for all accesses to |
| candidates for scalarization. Return the created access or NULL if none is |
| created. */ |
| |
| static struct access * |
| build_access_from_expr_1 (tree expr, gimple *stmt, bool write) |
| { |
| struct access *ret = NULL; |
| bool partial_ref; |
| |
| if (TREE_CODE (expr) == BIT_FIELD_REF |
| || TREE_CODE (expr) == IMAGPART_EXPR |
| || TREE_CODE (expr) == REALPART_EXPR) |
| { |
| expr = TREE_OPERAND (expr, 0); |
| partial_ref = true; |
| } |
| else |
| partial_ref = false; |
| |
| if (storage_order_barrier_p (expr)) |
| { |
| disqualify_base_of_expr (expr, "storage order barrier."); |
| return NULL; |
| } |
| |
| /* We need to dive through V_C_Es in order to get the size of its parameter |
| and not the result type. Ada produces such statements. We are also |
| capable of handling the topmost V_C_E but not any of those buried in other |
| handled components. */ |
| if (TREE_CODE (expr) == VIEW_CONVERT_EXPR) |
| expr = TREE_OPERAND (expr, 0); |
| |
| if (contains_view_convert_expr_p (expr)) |
| { |
| disqualify_base_of_expr (expr, "V_C_E under a different handled " |
| "component."); |
| return NULL; |
| } |
| if (TREE_THIS_VOLATILE (expr)) |
| { |
| disqualify_base_of_expr (expr, "part of a volatile reference."); |
| return NULL; |
| } |
| |
| switch (TREE_CODE (expr)) |
| { |
| case MEM_REF: |
| if (TREE_CODE (TREE_OPERAND (expr, 0)) != ADDR_EXPR) |
| return NULL; |
| /* fall through */ |
| case VAR_DECL: |
| case PARM_DECL: |
| case RESULT_DECL: |
| case COMPONENT_REF: |
| case ARRAY_REF: |
| case ARRAY_RANGE_REF: |
| ret = create_access (expr, stmt, write); |
| break; |
| |
| default: |
| break; |
| } |
| |
| if (write && partial_ref && ret) |
| ret->grp_partial_lhs = 1; |
| |
| return ret; |
| } |
| |
| /* Scan expression EXPR and create access structures for all accesses to |
| candidates for scalarization. Return true if any access has been inserted. |
| STMT must be the statement from which the expression is taken, WRITE must be |
| true if the expression is a store and false otherwise. */ |
| |
| static bool |
| build_access_from_expr (tree expr, gimple *stmt, bool write) |
| { |
| struct access *access; |
| |
| access = build_access_from_expr_1 (expr, stmt, write); |
| if (access) |
| { |
| /* This means the aggregate is accesses as a whole in a way other than an |
| assign statement and thus cannot be removed even if we had a scalar |
| replacement for everything. */ |
| if (cannot_scalarize_away_bitmap) |
| bitmap_set_bit (cannot_scalarize_away_bitmap, DECL_UID (access->base)); |
| return true; |
| } |
| return false; |
| } |
| |
| /* Return the single non-EH successor edge of BB or NULL if there is none or |
| more than one. */ |
| |
| static edge |
| single_non_eh_succ (basic_block bb) |
| { |
| edge e, res = NULL; |
| edge_iterator ei; |
| |
| FOR_EACH_EDGE (e, ei, bb->succs) |
| if (!(e->flags & EDGE_EH)) |
| { |
| if (res) |
| return NULL; |
| res = e; |
| } |
| |
| return res; |
| } |
| |
| /* Disqualify LHS and RHS for scalarization if STMT has to terminate its BB and |
| there is no alternative spot where to put statements SRA might need to |
| generate after it. The spot we are looking for is an edge leading to a |
| single non-EH successor, if it exists and is indeed single. RHS may be |
| NULL, in that case ignore it. */ |
| |
| static bool |
| disqualify_if_bad_bb_terminating_stmt (gimple *stmt, tree lhs, tree rhs) |
| { |
| if (stmt_ends_bb_p (stmt)) |
| { |
| if (single_non_eh_succ (gimple_bb (stmt))) |
| return false; |
| |
| disqualify_base_of_expr (lhs, "LHS of a throwing stmt."); |
| if (rhs) |
| disqualify_base_of_expr (rhs, "RHS of a throwing stmt."); |
| return true; |
| } |
| return false; |
| } |
| |
| /* Return true if the nature of BASE is such that it contains data even if |
| there is no write to it in the function. */ |
| |
| static bool |
| comes_initialized_p (tree base) |
| { |
| return TREE_CODE (base) == PARM_DECL || constant_decl_p (base); |
| } |
| |
| /* Scan expressions occurring in STMT, create access structures for all accesses |
| to candidates for scalarization and remove those candidates which occur in |
| statements or expressions that prevent them from being split apart. Return |
| true if any access has been inserted. */ |
| |
| static bool |
| build_accesses_from_assign (gimple *stmt) |
| { |
| tree lhs, rhs; |
| struct access *lacc, *racc; |
| |
| if (!gimple_assign_single_p (stmt) |
| /* Scope clobbers don't influence scalarization. */ |
| || gimple_clobber_p (stmt)) |
| return false; |
| |
| lhs = gimple_assign_lhs (stmt); |
| rhs = gimple_assign_rhs1 (stmt); |
| |
| if (disqualify_if_bad_bb_terminating_stmt (stmt, lhs, rhs)) |
| return false; |
| |
| racc = build_access_from_expr_1 (rhs, stmt, false); |
| lacc = build_access_from_expr_1 (lhs, stmt, true); |
| |
| if (lacc) |
| { |
| lacc->grp_assignment_write = 1; |
| if (storage_order_barrier_p (rhs)) |
| lacc->grp_unscalarizable_region = 1; |
| |
| if (should_scalarize_away_bitmap && !is_gimple_reg_type (lacc->type)) |
| { |
| bool type_changing_p = false; |
| contains_vce_or_bfcref_p (lhs, &type_changing_p); |
| if (type_changing_p) |
| bitmap_set_bit (cannot_scalarize_away_bitmap, |
| DECL_UID (lacc->base)); |
| } |
| } |
| |
| if (racc) |
| { |
| racc->grp_assignment_read = 1; |
| if (should_scalarize_away_bitmap && !is_gimple_reg_type (racc->type)) |
| { |
| bool type_changing_p = false; |
| contains_vce_or_bfcref_p (rhs, &type_changing_p); |
| |
| if (type_changing_p || gimple_has_volatile_ops (stmt)) |
| bitmap_set_bit (cannot_scalarize_away_bitmap, |
| DECL_UID (racc->base)); |
| else |
| bitmap_set_bit (should_scalarize_away_bitmap, |
| DECL_UID (racc->base)); |
| } |
| if (storage_order_barrier_p (lhs)) |
| racc->grp_unscalarizable_region = 1; |
| } |
| |
| if (lacc && racc |
| && (sra_mode == SRA_MODE_EARLY_INTRA || sra_mode == SRA_MODE_INTRA) |
| && !lacc->grp_unscalarizable_region |
| && !racc->grp_unscalarizable_region |
| && AGGREGATE_TYPE_P (TREE_TYPE (lhs)) |
| && lacc->size == racc->size |
| && useless_type_conversion_p (lacc->type, racc->type)) |
| { |
| struct assign_link *link; |
| |
| link = assign_link_pool.allocate (); |
| memset (link, 0, sizeof (struct assign_link)); |
| |
| link->lacc = lacc; |
| link->racc = racc; |
| add_link_to_rhs (racc, link); |
| add_link_to_lhs (lacc, link); |
| add_access_to_rhs_work_queue (racc); |
| add_access_to_lhs_work_queue (lacc); |
| |
| /* Let's delay marking the areas as written until propagation of accesses |
| across link, unless the nature of rhs tells us that its data comes |
| from elsewhere. */ |
| if (!comes_initialized_p (racc->base)) |
| lacc->write = false; |
| } |
| |
| return lacc || racc; |
| } |
| |
| /* Callback of walk_stmt_load_store_addr_ops visit_addr used to determine |
| GIMPLE_ASM operands with memory constrains which cannot be scalarized. */ |
| |
| static bool |
| asm_visit_addr (gimple *, tree op, tree, void *) |
| { |
| op = get_base_address (op); |
| if (op |
| && DECL_P (op)) |
| disqualify_candidate (op, "Non-scalarizable GIMPLE_ASM operand."); |
| |
| return false; |
| } |
| |
| /* Scan function and look for interesting expressions and create access |
| structures for them. Return true iff any access is created. */ |
| |
| static bool |
| scan_function (void) |
| { |
| basic_block bb; |
| bool ret = false; |
| |
| FOR_EACH_BB_FN (bb, cfun) |
| { |
| gimple_stmt_iterator gsi; |
| for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) |
| { |
| gimple *stmt = gsi_stmt (gsi); |
| tree t; |
| unsigned i; |
| |
| switch (gimple_code (stmt)) |
| { |
| case GIMPLE_RETURN: |
| t = gimple_return_retval (as_a <greturn *> (stmt)); |
| if (t != NULL_TREE) |
| ret |= build_access_from_expr (t, stmt, false); |
| break; |
| |
| case GIMPLE_ASSIGN: |
| ret |= build_accesses_from_assign (stmt); |
| break; |
| |
| case GIMPLE_CALL: |
| for (i = 0; i < gimple_call_num_args (stmt); i++) |
| ret |= build_access_from_expr (gimple_call_arg (stmt, i), |
| stmt, false); |
| |
| t = gimple_call_lhs (stmt); |
| if (t && !disqualify_if_bad_bb_terminating_stmt (stmt, t, NULL)) |
| ret |= build_access_from_expr (t, stmt, true); |
| break; |
| |
| case GIMPLE_ASM: |
| { |
| gasm *asm_stmt = as_a <gasm *> (stmt); |
| walk_stmt_load_store_addr_ops (asm_stmt, NULL, NULL, NULL, |
| asm_visit_addr); |
| for (i = 0; i < gimple_asm_ninputs (asm_stmt); i++) |
| { |
| t = TREE_VALUE (gimple_asm_input_op (asm_stmt, i)); |
| ret |= build_access_from_expr (t, asm_stmt, false); |
| } |
| for (i = 0; i < gimple_asm_noutputs (asm_stmt); i++) |
| { |
| t = TREE_VALUE (gimple_asm_output_op (asm_stmt, i)); |
| ret |= build_access_from_expr (t, asm_stmt, true); |
| } |
| } |
| break; |
| |
| default: |
| break; |
| } |
| } |
| } |
| |
| return ret; |
| } |
| |
| /* Helper of QSORT function. There are pointers to accesses in the array. An |
| access is considered smaller than another if it has smaller offset or if the |
| offsets are the same but is size is bigger. */ |
| |
| static int |
| compare_access_positions (const void *a, const void *b) |
| { |
| const access_p *fp1 = (const access_p *) a; |
| const access_p *fp2 = (const access_p *) b; |
| const access_p f1 = *fp1; |
| const access_p f2 = *fp2; |
| |
| if (f1->offset != f2->offset) |
| return f1->offset < f2->offset ? -1 : 1; |
| |
| if (f1->size == f2->size) |
| { |
| if (f1->type == f2->type) |
| return 0; |
| /* Put any non-aggregate type before any aggregate type. */ |
| else if (!is_gimple_reg_type (f1->type) |
| && is_gimple_reg_type (f2->type)) |
| return 1; |
| else if (is_gimple_reg_type (f1->type) |
| && !is_gimple_reg_type (f2->type)) |
| return -1; |
| /* Put any complex or vector type before any other scalar type. */ |
| else if (TREE_CODE (f1->type) != COMPLEX_TYPE |
| && TREE_CODE (f1->type) != VECTOR_TYPE |
| && (TREE_CODE (f2->type) == COMPLEX_TYPE |
| || TREE_CODE (f2->type) == VECTOR_TYPE)) |
| return 1; |
| else if ((TREE_CODE (f1->type) == COMPLEX_TYPE |
| || TREE_CODE (f1->type) == VECTOR_TYPE) |
| && TREE_CODE (f2->type) != COMPLEX_TYPE |
| && TREE_CODE (f2->type) != VECTOR_TYPE) |
| return -1; |
| /* Put any integral type before any non-integral type. When splicing, we |
| make sure that those with insufficient precision and occupying the |
| same space are not scalarized. */ |
| else if (INTEGRAL_TYPE_P (f1->type) |
| && !INTEGRAL_TYPE_P (f2->type)) |
| return -1; |
| else if (!INTEGRAL_TYPE_P (f1->type) |
| && INTEGRAL_TYPE_P (f2->type)) |
| return 1; |
| /* Put the integral type with the bigger precision first. */ |
| else if (INTEGRAL_TYPE_P (f1->type) |
| && INTEGRAL_TYPE_P (f2->type) |
| && (TYPE_PRECISION (f2->type) != TYPE_PRECISION (f1->type))) |
| return TYPE_PRECISION (f2->type) - TYPE_PRECISION (f1->type); |
| /* Stabilize the sort. */ |
| return TYPE_UID (f1->type) - TYPE_UID (f2->type); |
| } |
| |
| /* We want the bigger accesses first, thus the opposite operator in the next |
| line: */ |
| return f1->size > f2->size ? -1 : 1; |
| } |
| |
| |
| /* Append a name of the declaration to the name obstack. A helper function for |
| make_fancy_name. */ |
| |
| static void |
| make_fancy_decl_name (tree decl) |
| { |
| char buffer[32]; |
| |
| tree name = DECL_NAME (decl); |
| if (name) |
| obstack_grow (&name_obstack, IDENTIFIER_POINTER (name), |
| IDENTIFIER_LENGTH (name)); |
| else |
| { |
| sprintf (buffer, "D%u", DECL_UID (decl)); |
| obstack_grow (&name_obstack, buffer, strlen (buffer)); |
| } |
| } |
| |
| /* Helper for make_fancy_name. */ |
| |
| static void |
| make_fancy_name_1 (tree expr) |
| { |
| char buffer[32]; |
| tree index; |
| |
| if (DECL_P (expr)) |
| { |
| make_fancy_decl_name (expr); |
| return; |
| } |
| |
| switch (TREE_CODE (expr)) |
| { |
| case COMPONENT_REF: |
| make_fancy_name_1 (TREE_OPERAND (expr, 0)); |
| obstack_1grow (&name_obstack, '$'); |
| make_fancy_decl_name (TREE_OPERAND (expr, 1)); |
| break; |
| |
| case ARRAY_REF: |
| make_fancy_name_1 (TREE_OPERAND (expr, 0)); |
| obstack_1grow (&name_obstack, '$'); |
| /* Arrays with only one element may not have a constant as their |
| index. */ |
| index = TREE_OPERAND (expr, 1); |
| if (TREE_CODE (index) != INTEGER_CST) |
| break; |
| sprintf (buffer, HOST_WIDE_INT_PRINT_DEC, TREE_INT_CST_LOW (index)); |
| obstack_grow (&name_obstack, buffer, strlen (buffer)); |
| break; |
| |
| case ADDR_EXPR: |
| make_fancy_name_1 (TREE_OPERAND (expr, 0)); |
| break; |
| |
| case MEM_REF: |
| make_fancy_name_1 (TREE_OPERAND (expr, 0)); |
| if (!integer_zerop (TREE_OPERAND (expr, 1))) |
| { |
| obstack_1grow (&name_obstack, '$'); |
| sprintf (buffer, HOST_WIDE_INT_PRINT_DEC, |
| TREE_INT_CST_LOW (TREE_OPERAND (expr, 1))); |
| obstack_grow (&name_obstack, buffer, strlen (buffer)); |
| } |
| break; |
| |
| case BIT_FIELD_REF: |
| case REALPART_EXPR: |
| case IMAGPART_EXPR: |
| gcc_unreachable (); /* we treat these as scalars. */ |
| break; |
| default: |
| break; |
| } |
| } |
| |
| /* Create a human readable name for replacement variable of ACCESS. */ |
| |
| static char * |
| make_fancy_name (tree expr) |
| { |
| make_fancy_name_1 (expr); |
| obstack_1grow (&name_obstack, '\0'); |
| return XOBFINISH (&name_obstack, char *); |
| } |
| |
| /* Construct a MEM_REF that would reference a part of aggregate BASE of type |
| EXP_TYPE at the given OFFSET and with storage order REVERSE. If BASE is |
| something for which get_addr_base_and_unit_offset returns NULL, gsi must |
| be non-NULL and is used to insert new statements either before or below |
| the current one as specified by INSERT_AFTER. This function is not capable |
| of handling bitfields. */ |
| |
| tree |
| build_ref_for_offset (location_t loc, tree base, poly_int64 offset, |
| bool reverse, tree exp_type, gimple_stmt_iterator *gsi, |
| bool insert_after) |
| { |
| tree prev_base = base; |
| tree off; |
| tree mem_ref; |
| poly_int64 base_offset; |
| unsigned HOST_WIDE_INT misalign; |
| unsigned int align; |
| |
| /* Preserve address-space information. */ |
| addr_space_t as = TYPE_ADDR_SPACE (TREE_TYPE (base)); |
| if (as != TYPE_ADDR_SPACE (exp_type)) |
| exp_type = build_qualified_type (exp_type, |
| TYPE_QUALS (exp_type) |
| | ENCODE_QUAL_ADDR_SPACE (as)); |
| |
| poly_int64 byte_offset = exact_div (offset, BITS_PER_UNIT); |
| get_object_alignment_1 (base, &align, &misalign); |
| base = get_addr_base_and_unit_offset (base, &base_offset); |
| |
| /* get_addr_base_and_unit_offset returns NULL for references with a variable |
| offset such as array[var_index]. */ |
| if (!base) |
| { |
| gassign *stmt; |
| tree tmp, addr; |
| |
| gcc_checking_assert (gsi); |
| tmp = make_ssa_name (build_pointer_type (TREE_TYPE (prev_base))); |
| addr = build_fold_addr_expr (unshare_expr (prev_base)); |
| STRIP_USELESS_TYPE_CONVERSION (addr); |
| stmt = gimple_build_assign (tmp, addr); |
| gimple_set_location (stmt, loc); |
| if (insert_after) |
| gsi_insert_after (gsi, stmt, GSI_NEW_STMT); |
| else |
| gsi_insert_before (gsi, stmt, GSI_SAME_STMT); |
| |
| off = build_int_cst (reference_alias_ptr_type (prev_base), byte_offset); |
| base = tmp; |
| } |
| else if (TREE_CODE (base) == MEM_REF) |
| { |
| off = build_int_cst (TREE_TYPE (TREE_OPERAND (base, 1)), |
| base_offset + byte_offset); |
| off = int_const_binop (PLUS_EXPR, TREE_OPERAND (base, 1), off); |
| base = unshare_expr (TREE_OPERAND (base, 0)); |
| } |
| else |
| { |
| off = build_int_cst (reference_alias_ptr_type (prev_base), |
| base_offset + byte_offset); |
| base = build_fold_addr_expr (unshare_expr (base)); |
| } |
| |
| unsigned int align_bound = known_alignment (misalign + offset); |
| if (align_bound != 0) |
| align = MIN (align, align_bound); |
| if (align != TYPE_ALIGN (exp_type)) |
| exp_type = build_aligned_type (exp_type, align); |
| |
| mem_ref = fold_build2_loc (loc, MEM_REF, exp_type, base, off); |
| REF_REVERSE_STORAGE_ORDER (mem_ref) = reverse; |
| if (TREE_THIS_VOLATILE (prev_base)) |
| TREE_THIS_VOLATILE (mem_ref) = 1; |
| if (TREE_SIDE_EFFECTS (prev_base)) |
| TREE_SIDE_EFFECTS (mem_ref) = 1; |
| return mem_ref; |
| } |
| |
| /* Construct and return a memory reference that is equal to a portion of |
| MODEL->expr but is based on BASE. If this cannot be done, return NULL. */ |
| |
| static tree |
| build_reconstructed_reference (location_t, tree base, struct access *model) |
| { |
| tree expr = model->expr, prev_expr = NULL; |
| while (!types_compatible_p (TREE_TYPE (expr), TREE_TYPE (base))) |
| { |
| if (!handled_component_p (expr)) |
| return NULL_TREE; |
| prev_expr = expr; |
| expr = TREE_OPERAND (expr, 0); |
| } |
| |
| /* Guard against broken VIEW_CONVERT_EXPRs... */ |
| if (!prev_expr) |
| return NULL_TREE; |
| |
| TREE_OPERAND (prev_expr, 0) = base; |
| tree ref = unshare_expr (model->expr); |
| TREE_OPERAND (prev_expr, 0) = expr; |
| return ref; |
| } |
| |
| /* Construct a memory reference to a part of an aggregate BASE at the given |
| OFFSET and of the same type as MODEL. In case this is a reference to a |
| bit-field, the function will replicate the last component_ref of model's |
| expr to access it. GSI and INSERT_AFTER have the same meaning as in |
| build_ref_for_offset. */ |
| |
| static tree |
| build_ref_for_model (location_t loc, tree base, HOST_WIDE_INT offset, |
| struct access *model, gimple_stmt_iterator *gsi, |
| bool insert_after) |
| { |
| gcc_assert (offset >= 0); |
| if (TREE_CODE (model->expr) == COMPONENT_REF |
| && DECL_BIT_FIELD (TREE_OPERAND (model->expr, 1))) |
| { |
| /* This access represents a bit-field. */ |
| tree t, exp_type, fld = TREE_OPERAND (model->expr, 1); |
| |
| offset -= int_bit_position (fld); |
| exp_type = TREE_TYPE (TREE_OPERAND (model->expr, 0)); |
| t = build_ref_for_offset (loc, base, offset, model->reverse, exp_type, |
| gsi, insert_after); |
| /* The flag will be set on the record type. */ |
| REF_REVERSE_STORAGE_ORDER (t) = 0; |
| return fold_build3_loc (loc, COMPONENT_REF, TREE_TYPE (fld), t, fld, |
| NULL_TREE); |
| } |
| else |
| { |
| tree res; |
| if (model->grp_same_access_path |
| && !TREE_THIS_VOLATILE (base) |
| && (TYPE_ADDR_SPACE (TREE_TYPE (base)) |
| == TYPE_ADDR_SPACE (TREE_TYPE (model->expr))) |
| && offset <= model->offset |
| /* build_reconstructed_reference can still fail if we have already |
| massaged BASE because of another type incompatibility. */ |
| && (res = build_reconstructed_reference (loc, base, model))) |
| return res; |
| else |
| return build_ref_for_offset (loc, base, offset, model->reverse, |
| model->type, gsi, insert_after); |
| } |
| } |
| |
| /* Attempt to build a memory reference that we could but into a gimple |
| debug_bind statement. Similar to build_ref_for_model but punts if it has to |
| create statements and return s NULL instead. This function also ignores |
| alignment issues and so its results should never end up in non-debug |
| statements. */ |
| |
| static tree |
| build_debug_ref_for_model (location_t loc, tree base, HOST_WIDE_INT offset, |
| struct access *model) |
| { |
| poly_int64 base_offset; |
| tree off; |
| |
| if (TREE_CODE (model->expr) == COMPONENT_REF |
| && DECL_BIT_FIELD (TREE_OPERAND (model->expr, 1))) |
| return NULL_TREE; |
| |
| base = get_addr_base_and_unit_offset (base, &base_offset); |
| if (!base) |
| return NULL_TREE; |
| if (TREE_CODE (base) == MEM_REF) |
| { |
| off = build_int_cst (TREE_TYPE (TREE_OPERAND (base, 1)), |
| base_offset + offset / BITS_PER_UNIT); |
| off = int_const_binop (PLUS_EXPR, TREE_OPERAND (base, 1), off); |
| base = unshare_expr (TREE_OPERAND (base, 0)); |
| } |
| else |
| { |
| off = build_int_cst (reference_alias_ptr_type (base), |
| base_offset + offset / BITS_PER_UNIT); |
| base = build_fold_addr_expr (unshare_expr (base)); |
| } |
| |
| return fold_build2_loc (loc, MEM_REF, model->type, base, off); |
| } |
| |
| /* Construct a memory reference consisting of component_refs and array_refs to |
| a part of an aggregate *RES (which is of type TYPE). The requested part |
| should have type EXP_TYPE at be the given OFFSET. This function might not |
| succeed, it returns true when it does and only then *RES points to something |
| meaningful. This function should be used only to build expressions that we |
| might need to present to user (e.g. in warnings). In all other situations, |
| build_ref_for_model or build_ref_for_offset should be used instead. */ |
| |
| static bool |
| build_user_friendly_ref_for_offset (tree *res, tree type, HOST_WIDE_INT offset, |
| tree exp_type) |
| { |
| while (1) |
| { |
| tree fld; |
| tree tr_size, index, minidx; |
| HOST_WIDE_INT el_size; |
| |
| if (offset == 0 && exp_type |
| && types_compatible_p (exp_type, type)) |
| return true; |
| |
| switch (TREE_CODE (type)) |
| { |
| case UNION_TYPE: |
| case QUAL_UNION_TYPE: |
| case RECORD_TYPE: |
| for (fld = TYPE_FIELDS (type); fld; fld = DECL_CHAIN (fld)) |
| { |
| HOST_WIDE_INT pos, size; |
| tree tr_pos, expr, *expr_ptr; |
| |
| if (TREE_CODE (fld) != FIELD_DECL) |
| continue; |
| |
| tr_pos = bit_position (fld); |
| if (!tr_pos || !tree_fits_uhwi_p (tr_pos)) |
| continue; |
| pos = tree_to_uhwi (tr_pos); |
| gcc_assert (TREE_CODE (type) == RECORD_TYPE || pos == 0); |
| tr_size = DECL_SIZE (fld); |
| if (!tr_size || !tree_fits_uhwi_p (tr_size)) |
| continue; |
| size = tree_to_uhwi (tr_size); |
| if (size == 0) |
| { |
| if (pos != offset) |
| continue; |
| } |
| else if (pos > offset || (pos + size) <= offset) |
| continue; |
| |
| expr = build3 (COMPONENT_REF, TREE_TYPE (fld), *res, fld, |
| NULL_TREE); |
| expr_ptr = &expr; |
| if (build_user_friendly_ref_for_offset (expr_ptr, TREE_TYPE (fld), |
| offset - pos, exp_type)) |
| { |
| *res = expr; |
| return true; |
| } |
| } |
| return false; |
| |
| case ARRAY_TYPE: |
| tr_size = TYPE_SIZE (TREE_TYPE (type)); |
| if (!tr_size || !tree_fits_uhwi_p (tr_size)) |
| return false; |
| el_size = tree_to_uhwi (tr_size); |
| |
| minidx = TYPE_MIN_VALUE (TYPE_DOMAIN (type)); |
| if (TREE_CODE (minidx) != INTEGER_CST || el_size == 0) |
| return false; |
| index = build_int_cst (TYPE_DOMAIN (type), offset / el_size); |
| if (!integer_zerop (minidx)) |
| index = int_const_binop (PLUS_EXPR, index, minidx); |
| *res = build4 (ARRAY_REF, TREE_TYPE (type), *res, index, |
| NULL_TREE, NULL_TREE); |
| offset = offset % el_size; |
| type = TREE_TYPE (type); |
| break; |
| |
| default: |
| if (offset != 0) |
| return false; |
| |
| if (exp_type) |
| return false; |
| else |
| return true; |
| } |
| } |
| } |
| |
| /* Print message to dump file why a variable was rejected. */ |
| |
| static void |
| reject (tree var, const char *msg) |
| { |
| if (dump_file && (dump_flags & TDF_DETAILS)) |
| { |
| fprintf (dump_file, "Rejected (%d): %s: ", DECL_UID (var), msg); |
| print_generic_expr (dump_file, var); |
| fprintf (dump_file, "\n"); |
| } |
| } |
| |
| /* Return true if VAR is a candidate for SRA. */ |
| |
| static bool |
| maybe_add_sra_candidate (tree var) |
| { |
| tree type = TREE_TYPE (var); |
| const char *msg; |
| tree_node **slot; |
| |
| if (!AGGREGATE_TYPE_P (type)) |
| { |
| reject (var, "not aggregate"); |
| return false; |
| } |
| /* Allow constant-pool entries that "need to live in memory". */ |
| if (needs_to_live_in_memory (var) && !constant_decl_p (var)) |
| { |
| reject (var, "needs to live in memory"); |
| return false; |
| } |
| if (TREE_THIS_VOLATILE (var)) |
| { |
| reject (var, "is volatile"); |
| return false; |
| } |
| if (!COMPLETE_TYPE_P (type)) |
| { |
| reject (var, "has incomplete type"); |
| return false; |
| } |
| if (!tree_fits_shwi_p (TYPE_SIZE (type))) |
| { |
| reject (var, "type size not fixed"); |
| return false; |
| } |
| if (tree_to_shwi (TYPE_SIZE (type)) == 0) |
| { |
| reject (var, "type size is zero"); |
| return false; |
| } |
| if (type_internals_preclude_sra_p (type, &msg)) |
| { |
| reject (var, msg); |
| return false; |
| } |
| if (/* Fix for PR 41089. tree-stdarg.c needs to have va_lists intact but |
| we also want to schedule it rather late. Thus we ignore it in |
| the early pass. */ |
| (sra_mode == SRA_MODE_EARLY_INTRA |
| && is_va_list_type (type))) |
| { |
| reject (var, "is va_list"); |
| return false; |
| } |
| |
| bitmap_set_bit (candidate_bitmap, DECL_UID (var)); |
| slot = candidates->find_slot_with_hash (var, DECL_UID (var), INSERT); |
| *slot = var; |
| |
| if (dump_file && (dump_flags & TDF_DETAILS)) |
| { |
| fprintf (dump_file, "Candidate (%d): ", DECL_UID (var)); |
| print_generic_expr (dump_file, var); |
| fprintf (dump_file, "\n"); |
| } |
| |
| return true; |
| } |
| |
| /* The very first phase of intraprocedural SRA. It marks in candidate_bitmap |
| those with type which is suitable for scalarization. */ |
| |
| static bool |
| find_var_candidates (void) |
| { |
| tree var, parm; |
| unsigned int i; |
| bool ret = false; |
| |
| for (parm = DECL_ARGUMENTS (current_function_decl); |
| parm; |
| parm = DECL_CHAIN (parm)) |
| ret |= maybe_add_sra_candidate (parm); |
| |
| FOR_EACH_LOCAL_DECL (cfun, i, var) |
| { |
| if (!VAR_P (var)) |
| continue; |
| |
| ret |= maybe_add_sra_candidate (var); |
| } |
| |
| return ret; |
| } |
| |
| /* Return true if EXP is a reference chain of COMPONENT_REFs and AREAY_REFs |
| ending either with a DECL or a MEM_REF with zero offset. */ |
| |
| static bool |
| path_comparable_for_same_access (tree expr) |
| { |
| while (handled_component_p (expr)) |
| { |
| if (TREE_CODE (expr) == ARRAY_REF) |
| { |
| /* SSA name indices can occur here too when the array is of sie one. |
| But we cannot just re-use array_refs with SSA names elsewhere in |
| the function, so disallow non-constant indices. TODO: Remove this |
| limitation after teaching build_reconstructed_reference to replace |
| the index with the index type lower bound. */ |
| if (TREE_CODE (TREE_OPERAND (expr, 1)) != INTEGER_CST) |
| return false; |
| } |
| expr = TREE_OPERAND (expr, 0); |
| } |
| |
| if (TREE_CODE (expr) == MEM_REF) |
| { |
| if (!zerop (TREE_OPERAND (expr, 1))) |
| return false; |
| } |
| else |
| gcc_assert (DECL_P (expr)); |
| |
| return true; |
| } |
| |
| /* Assuming that EXP1 consists of only COMPONENT_REFs and ARRAY_REFs, return |
| true if the chain of these handled components are exactly the same as EXP2 |
| and the expression under them is the same DECL or an equivalent MEM_REF. |
| The reference picked by compare_access_positions must go to EXP1. */ |
| |
| static bool |
| same_access_path_p (tree exp1, tree exp2) |
| { |
| if (TREE_CODE (exp1) != TREE_CODE (exp2)) |
| { |
| /* Special case single-field structures loaded sometimes as the field |
| and sometimes as the structure. If the field is of a scalar type, |
| compare_access_positions will put it into exp1. |
| |
| TODO: The gimple register type condition can be removed if teach |
| compare_access_positions to put inner types first. */ |
| if (is_gimple_reg_type (TREE_TYPE (exp1)) |
| && TREE_CODE (exp1) == COMPONENT_REF |
| && (TYPE_MAIN_VARIANT (TREE_TYPE (TREE_OPERAND (exp1, 0))) |
| == TYPE_MAIN_VARIANT (TREE_TYPE (exp2)))) |
| exp1 = TREE_OPERAND (exp1, 0); |
| else |
| return false; |
| } |
| |
| if (!operand_equal_p (exp1, exp2, OEP_ADDRESS_OF)) |
| return false; |
| |
| return true; |
| } |
| |
| /* Sort all accesses for the given variable, check for partial overlaps and |
| return NULL if there are any. If there are none, pick a representative for |
| each combination of offset and size and create a linked list out of them. |
| Return the pointer to the first representative and make sure it is the first |
| one in the vector of accesses. */ |
| |
| static struct access * |
| sort_and_splice_var_accesses (tree var) |
| { |
| int i, j, access_count; |
| struct access *res, **prev_acc_ptr = &res; |
| vec<access_p> *access_vec; |
| bool first = true; |
| HOST_WIDE_INT low = -1, high = 0; |
| |
| access_vec = get_base_access_vector (var); |
| if (!access_vec) |
| return NULL; |
| access_count = access_vec->length (); |
| |
| /* Sort by <OFFSET, SIZE>. */ |
| access_vec->qsort (compare_access_positions); |
| |
| i = 0; |
| while (i < access_count) |
| { |
| struct access *access = (*access_vec)[i]; |
| bool grp_write = access->write; |
| bool grp_read = !access->write; |
| bool grp_scalar_write = access->write |
| && is_gimple_reg_type (access->type); |
| bool grp_scalar_read = !access->write |
| && is_gimple_reg_type (access->type); |
| bool grp_assignment_read = access->grp_assignment_read; |
| bool grp_assignment_write = access->grp_assignment_write; |
| bool multiple_scalar_reads = false; |
| bool grp_partial_lhs = access->grp_partial_lhs; |
| bool first_scalar = is_gimple_reg_type (access->type); |
| bool unscalarizable_region = access->grp_unscalarizable_region; |
| bool grp_same_access_path = true; |
| bool bf_non_full_precision |
| = (INTEGRAL_TYPE_P (access->type) |
| && TYPE_PRECISION (access->type) != access->size |
| && TREE_CODE (access->expr) == COMPONENT_REF |
| && DECL_BIT_FIELD (TREE_OPERAND (access->expr, 1))); |
| |
| if (first || access->offset >= high) |
| { |
| first = false; |
| low = access->offset; |
| high = access->offset + access->size; |
| } |
| else if (access->offset > low && access->offset + access->size > high) |
| return NULL; |
| else |
| gcc_assert (access->offset >= low |
| && access->offset + access->size <= high); |
| |
| grp_same_access_path = path_comparable_for_same_access (access->expr); |
| |
| j = i + 1; |
| while (j < access_count) |
| { |
| struct access *ac2 = (*access_vec)[j]; |
| if (ac2->offset != access->offset || ac2->size != access->size) |
| break; |
| if (ac2->write) |
| { |
| grp_write = true; |
| grp_scalar_write = (grp_scalar_write |
| || is_gimple_reg_type (ac2->type)); |
| } |
| else |
| { |
| grp_read = true; |
| if (is_gimple_reg_type (ac2->type)) |
| { |
| if (grp_scalar_read) |
| multiple_scalar_reads = true; |
| else |
| grp_scalar_read = true; |
| } |
| } |
| grp_assignment_read |= ac2->grp_assignment_read; |
| grp_assignment_write |= ac2->grp_assignment_write; |
| grp_partial_lhs |= ac2->grp_partial_lhs; |
| unscalarizable_region |= ac2->grp_unscalarizable_region; |
| relink_to_new_repr (access, ac2); |
| |
| /* If there are both aggregate-type and scalar-type accesses with |
| this combination of size and offset, the comparison function |
| should have put the scalars first. */ |
| gcc_assert (first_scalar || !is_gimple_reg_type (ac2->type)); |
| /* It also prefers integral types to non-integral. However, when the |
| precision of the selected type does not span the entire area and |
| should also be used for a non-integer (i.e. float), we must not |
| let that happen. Normally analyze_access_subtree expands the type |
| to cover the entire area but for bit-fields it doesn't. */ |
| if (bf_non_full_precision && !INTEGRAL_TYPE_P (ac2->type)) |
| { |
| if (dump_file && (dump_flags & TDF_DETAILS)) |
| { |
| fprintf (dump_file, "Cannot scalarize the following access " |
| "because insufficient precision integer type was " |
| "selected.\n "); |
| dump_access (dump_file, access, false); |
| } |
| unscalarizable_region = true; |
| } |
| |
| if (grp_same_access_path |
| && !same_access_path_p (access->expr, ac2->expr)) |
| grp_same_access_path = false; |
| |
| ac2->group_representative = access; |
| j++; |
| } |
| |
| i = j; |
| |
| access->group_representative = access; |
| access->grp_write = grp_write; |
| access->grp_read = grp_read; |
| access->grp_scalar_read = grp_scalar_read; |
| access->grp_scalar_write = grp_scalar_write; |
| access->grp_assignment_read = grp_assignment_read; |
| access->grp_assignment_write = grp_assignment_write; |
| access->grp_hint = multiple_scalar_reads && !constant_decl_p (var); |
| access->grp_partial_lhs = grp_partial_lhs; |
| access->grp_unscalarizable_region = unscalarizable_region; |
| access->grp_same_access_path = grp_same_access_path; |
| |
| *prev_acc_ptr = access; |
| prev_acc_ptr = &access->next_grp; |
| } |
| |
| gcc_assert (res == (*access_vec)[0]); |
| return res; |
| } |
| |
| /* Create a variable for the given ACCESS which determines the type, name and a |
| few other properties. Return the variable declaration and store it also to |
| ACCESS->replacement. REG_TREE is used when creating a declaration to base a |
| default-definition SSA name on in order to facilitate an uninitialized |
| warning. It is used instead of the actual ACCESS type if that is not of a |
| gimple register type. */ |
| |
| static tree |
| create_access_replacement (struct access *access, tree reg_type = NULL_TREE) |
| { |
| tree repl; |
| |
| tree type = access->type; |
| if (reg_type && !is_gimple_reg_type (type)) |
| type = reg_type; |
| |
| if (access->grp_to_be_debug_replaced) |
| { |
| repl = create_tmp_var_raw (access->type); |
| DECL_CONTEXT (repl) = current_function_decl; |
| } |
| else |
| /* Drop any special alignment on the type if it's not on the main |
| variant. This avoids issues with weirdo ABIs like AAPCS. */ |
| repl = create_tmp_var (build_qualified_type (TYPE_MAIN_VARIANT (type), |
| TYPE_QUALS (type)), "SR"); |
| if (access->grp_partial_lhs |
| && is_gimple_reg_type (type)) |
| DECL_NOT_GIMPLE_REG_P (repl) = 1; |
| |
| DECL_SOURCE_LOCATION (repl) = DECL_SOURCE_LOCATION (access->base); |
| DECL_ARTIFICIAL (repl) = 1; |
| DECL_IGNORED_P (repl) = DECL_IGNORED_P (access->base); |
| |
| if (DECL_NAME (access->base) |
| && !DECL_IGNORED_P (access->base) |
| && !DECL_ARTIFICIAL (access->base)) |
| { |
| char *pretty_name = make_fancy_name (access->expr); |
| tree debug_expr = unshare_expr_without_location (access->expr), d; |
| bool fail = false; |
| |
| DECL_NAME (repl) = get_identifier (pretty_name); |
| DECL_NAMELESS (repl) = 1; |
| obstack_free (&name_obstack, pretty_name); |
| |
| /* Get rid of any SSA_NAMEs embedded in debug_expr, |
| as DECL_DEBUG_EXPR isn't considered when looking for still |
| used SSA_NAMEs and thus they could be freed. All debug info |
| generation cares is whether something is constant or variable |
| and that get_ref_base_and_extent works properly on the |
| expression. It cannot handle accesses at a non-constant offset |
| though, so just give up in those cases. */ |
| for (d = debug_expr; |
| !fail && (handled_component_p (d) || TREE_CODE (d) == MEM_REF); |
| d = TREE_OPERAND (d, 0)) |
| switch (TREE_CODE (d)) |
| { |
| case ARRAY_REF: |
| case ARRAY_RANGE_REF: |
| if (TREE_OPERAND (d, 1) |
| && TREE_CODE (TREE_OPERAND (d, 1)) != INTEGER_CST) |
| fail = true; |
| if (TREE_OPERAND (d, 3) |
| && TREE_CODE (TREE_OPERAND (d, 3)) != INTEGER_CST) |
| fail = true; |
| /* FALLTHRU */ |
| case COMPONENT_REF: |
| if (TREE_OPERAND (d, 2) |
| && TREE_CODE (TREE_OPERAND (d, 2)) != INTEGER_CST) |
| fail = true; |
| break; |
| case MEM_REF: |
| if (TREE_CODE (TREE_OPERAND (d, 0)) != ADDR_EXPR) |
| fail = true; |
| else |
| d = TREE_OPERAND (d, 0); |
| break; |
| default: |
| break; |
| } |
| if (!fail) |
| { |
| SET_DECL_DEBUG_EXPR (repl, debug_expr); |
| DECL_HAS_DEBUG_EXPR_P (repl) = 1; |
| } |
| if (access->grp_no_warning) |
| TREE_NO_WARNING (repl) = 1; |
| else |
| TREE_NO_WARNING (repl) = TREE_NO_WARNING (access->base); |
| } |
| else |
| TREE_NO_WARNING (repl) = 1; |
| |
| if (dump_file) |
| { |
| if (access->grp_to_be_debug_replaced) |
| { |
| fprintf (dump_file, "Created a debug-only replacement for "); |
| print_generic_expr (dump_file, access->base); |
| fprintf (dump_file, " offset: %u, size: %u\n", |
| (unsigned) access->offset, (unsigned) access->size); |
| } |
| else |
| { |
| fprintf (dump_file, "Created a replacement for "); |
| print_generic_expr (dump_file, access->base); |
| fprintf (dump_file, " offset: %u, size: %u: ", |
| (unsigned) access->offset, (unsigned) access->size); |
| print_generic_expr (dump_file, repl, TDF_UID); |
| fprintf (dump_file, "\n"); |
| } |
| } |
| sra_stats.replacements++; |
| |
| return repl; |
| } |
| |
| /* Return ACCESS scalar replacement, which must exist. */ |
| |
| static inline tree |
| get_access_replacement (struct access *access) |
| { |
| gcc_checking_assert (access->replacement_decl); |
| return access->replacement_decl; |
| } |
| |
| |
| /* Build a subtree of accesses rooted in *ACCESS, and move the pointer in the |
| linked list along the way. Stop when *ACCESS is NULL or the access pointed |
| to it is not "within" the root. Return false iff some accesses partially |
| overlap. */ |
| |
| static bool |
| build_access_subtree (struct access **access) |
| { |
| struct access *root = *access, *last_child = NULL; |
| HOST_WIDE_INT limit = root->offset + root->size; |
| |
| *access = (*access)->next_grp; |
| while (*access && (*access)->offset + (*access)->size <= limit) |
| { |
| if (!last_child) |
| root->first_child = *access; |
| else |
| last_child->next_sibling = *access; |
| last_child = *access; |
| (*access)->parent = root; |
| (*access)->grp_write |= root->grp_write; |
| |
| if (!build_access_subtree (access)) |
| return false; |
| } |
| |
| if (*access && (*access)->offset < limit) |
| return false; |
| |
| return true; |
| } |
| |
| /* Build a tree of access representatives, ACCESS is the pointer to the first |
| one, others are linked in a list by the next_grp field. Return false iff |
| some accesses partially overlap. */ |
| |
| static bool |
| build_access_trees (struct access *access) |
| { |
| while (access) |
| { |
| struct access *root = access; |
| |
| if (!build_access_subtree (&access)) |
| return false; |
| root->next_grp = access; |
| } |
| return true; |
| } |
| |
| /* Traverse the access forest where ROOT is the first root and verify that |
| various important invariants hold true. */ |
| |
| DEBUG_FUNCTION void |
| verify_sra_access_forest (struct access *root) |
| { |
| struct access *access = root; |
| tree first_base = root->base; |
| gcc_assert (DECL_P (first_base)); |
| do |
| { |
| gcc_assert (access->base == first_base); |
| if (access->parent) |
| gcc_assert (access->offset >= access->parent->offset |
| && access->size <= access->parent->size); |
| if (access->next_sibling) |
| gcc_assert (access->next_sibling->offset |
| >= access->offset + access->size); |
| |
| poly_int64 poffset, psize, pmax_size; |
| bool reverse; |
| tree base = get_ref_base_and_extent (access->expr, &poffset, &psize, |
| &pmax_size, &reverse); |
| HOST_WIDE_INT offset, size, max_size; |
| if (!poffset.is_constant (&offset) |
| || !psize.is_constant (&size) |
| || !pmax_size.is_constant (&max_size)) |
| gcc_unreachable (); |
| gcc_assert (base == first_base); |
| gcc_assert (offset == access->offset); |
| gcc_assert (access->grp_unscalarizable_region |
| || access->grp_total_scalarization |
| || size == max_size); |
| gcc_assert (access->grp_unscalarizable_region |
| || !is_gimple_reg_type (access->type) |
| || size == access->size); |
| gcc_assert (reverse == access->reverse); |
| |
| if (access->first_child) |
| { |
| gcc_assert (access->first_child->parent == access); |
| access = access->first_child; |
| } |
| else if (access->next_sibling) |
| { |
| gcc_assert (access->next_sibling->parent == access->parent); |
| access = access->next_sibling; |
| } |
| else |
| { |
| while (access->parent && !access->next_sibling) |
| access = access->parent; |
| if (access->next_sibling) |
| access = access->next_sibling; |
| else |
| { |
| gcc_assert (access == root); |
| root = root->next_grp; |
| access = root; |
| } |
| } |
| } |
| while (access); |
| } |
| |
| /* Verify access forests of all candidates with accesses by calling |
| verify_access_forest on each on them. */ |
| |
| DEBUG_FUNCTION void |
| verify_all_sra_access_forests (void) |
| { |
| bitmap_iterator bi; |
| unsigned i; |
| EXECUTE_IF_SET_IN_BITMAP (candidate_bitmap, 0, i, bi) |
| { |
| tree var = candidate (i); |
| struct access *access = get_first_repr_for_decl (var); |
| if (access) |
| { |
| gcc_assert (access->base == var); |
| verify_sra_access_forest (access); |
| } |
| } |
| } |
| |
| /* Return true if expr contains some ARRAY_REFs into a variable bounded |
| array. */ |
| |
| static bool |
| expr_with_var_bounded_array_refs_p (tree expr) |
| { |
| while (handled_component_p (expr)) |
| { |
| if (TREE_CODE (expr) == ARRAY_REF |
| && !tree_fits_shwi_p (array_ref_low_bound (expr))) |
| return true; |
| expr = TREE_OPERAND (expr, 0); |
| } |
| return false; |
| } |
| |
| /* Analyze the subtree of accesses rooted in ROOT, scheduling replacements when |
| both seeming beneficial and when ALLOW_REPLACEMENTS allows it. If TOTALLY |
| is set, we are totally scalarizing the aggregate. Also set all sorts of |
| access flags appropriately along the way, notably always set grp_read and |
| grp_assign_read according to MARK_READ and grp_write when MARK_WRITE is |
| true. |
| |
| Creating a replacement for a scalar access is considered beneficial if its |
| grp_hint ot TOTALLY is set (this means either that there is more than one |
| direct read access or that we are attempting total scalarization) or |
| according to the following table: |
| |
| Access written to through a scalar type (once or more times) |
| | |
| | Written to in an assignment statement |
| | | |
| | | Access read as scalar _once_ |
| | | | |
| | | | Read in an assignment statement |
| | | | | |
| | | | | Scalarize Comment |
| ----------------------------------------------------------------------------- |
| 0 0 0 0 No access for the scalar |
| 0 0 0 1 No access for the scalar |
| 0 0 1 0 No Single read - won't help |
| 0 0 1 1 No The same case |
| 0 1 0 0 No access for the scalar |
| 0 1 0 1 No access for the scalar |
| 0 1 1 0 Yes s = *g; return s.i; |
| 0 1 1 1 Yes The same case as above |
| 1 0 0 0 No Won't help |
| 1 0 0 1 Yes s.i = 1; *g = s; |
| 1 0 1 0 Yes s.i = 5; g = s.i; |
| 1 0 1 1 Yes The same case as above |
| 1 1 0 0 No Won't help. |
| 1 1 0 1 Yes s.i = 1; *g = s; |
| 1 1 1 0 Yes s = *g; return s.i; |
| 1 1 1 1 Yes Any of the above yeses */ |
| |
| static bool |
| analyze_access_subtree (struct access *root, struct access *parent, |
| bool allow_replacements, bool totally) |
| { |
| struct access *child; |
| HOST_WIDE_INT limit = root->offset + root->size; |
| HOST_WIDE_INT covered_to = root->offset; |
| bool scalar = is_gimple_reg_type (root->type); |
| bool hole = false, sth_created = false; |
| |
| if (parent) |
| { |
| if (parent->grp_read) |
| root->grp_read = 1; |
| if (parent->grp_assignment_read) |
| root->grp_assignment_read = 1; |
| if (parent->grp_write) |
| root->grp_write = 1; |
| if (parent->grp_assignment_write) |
| root->grp_assignment_write = 1; |
| if (!parent->grp_same_access_path) |
| root->grp_same_access_path = 0; |
| } |
| |
| if (root->grp_unscalarizable_region) |
| allow_replacements = false; |
| |
| if (allow_replacements && expr_with_var_bounded_array_refs_p (root->expr)) |
| allow_replacements = false; |
| |
| for (child = root->first_child; child; child = child->next_sibling) |
| { |
| hole |= covered_to < child->offset; |
| sth_created |= analyze_access_subtree (child, root, |
| allow_replacements && !scalar, |
| totally); |
| |
| root->grp_unscalarized_data |= child->grp_unscalarized_data; |
| if (child->grp_covered) |
| covered_to += child->size; |
| else |
| hole = true; |
| } |
| |
| if (allow_replacements && scalar && !root->first_child |
| && (totally || !root->grp_total_scalarization) |
| && (totally |
| || root->grp_hint |
| || ((root->grp_scalar_read || root->grp_assignment_read) |
| && (root->grp_scalar_write || root->grp_assignment_write)))) |
| { |
| /* Always create access replacements that cover the whole access. |
| For integral types this means the precision has to match. |
| Avoid assumptions based on the integral type kind, too. */ |
| if (INTEGRAL_TYPE_P (root->type) |
| && (TREE_CODE (root->type) != INTEGER_TYPE |
| || TYPE_PRECISION (root->type) != root->size) |
| /* But leave bitfield accesses alone. */ |
| && (TREE_CODE (root->expr) != COMPONENT_REF |
| || !DECL_BIT_FIELD (TREE_OPERAND (root->expr, 1)))) |
| { |
| tree rt = root->type; |
| gcc_assert ((root->offset % BITS_PER_UNIT) == 0 |
| && (root->size % BITS_PER_UNIT) == 0); |
| root->type = build_nonstandard_integer_type (root->size, |
| TYPE_UNSIGNED (rt)); |
| root->expr = build_ref_for_offset (UNKNOWN_LOCATION, root->base, |
| root->offset, root->reverse, |
| root->type, NULL, false); |
| |
| if (dump_file && (dump_flags & TDF_DETAILS)) |
| { |
| fprintf (dump_file, "Changing the type of a replacement for "); |
| print_generic_expr (dump_file, root->base); |
| fprintf (dump_file, " offset: %u, size: %u ", |
| (unsigned) root->offset, (unsigned) root->size); |
| fprintf (dump_file, " to an integer.\n"); |
| } |
| } |
| |
| root->grp_to_be_replaced = 1; |
| root->replacement_decl = create_access_replacement (root); |
| sth_created = true; |
| hole = false; |
| } |
| else |
| { |
| if (allow_replacements |
| && scalar && !root->first_child |
| && !root->grp_total_scalarization |
| && (root->grp_scalar_write || root->grp_assignment_write) |
| && !bitmap_bit_p (cannot_scalarize_away_bitmap, |
| DECL_UID (root->base))) |
| { |
| gcc_checking_assert (!root->grp_scalar_read |
| && !root->grp_assignment_read); |
| sth_created = true; |
| if (MAY_HAVE_DEBUG_BIND_STMTS) |
| { |
| root->grp_to_be_debug_replaced = 1; |
| root->replacement_decl = create_access_replacement (root); |
| } |
| } |
| |
| if (covered_to < limit) |
| hole = true; |
| if (scalar || !allow_replacements) |
| root->grp_total_scalarization = 0; |
| } |
| |
| if (!hole || totally) |
| root->grp_covered = 1; |
| else if (root->grp_write || comes_initialized_p (root->base)) |
| root->grp_unscalarized_data = 1; /* not covered and written to */ |
| return sth_created; |
| } |
| |
| /* Analyze all access trees linked by next_grp by the means of |
| analyze_access_subtree. */ |
| static bool |
| analyze_access_trees (struct access *access) |
| { |
| bool ret = false; |
| |
| while (access) |
| { |
| if (analyze_access_subtree (access, NULL, true, |
| access->grp_total_scalarization)) |
| ret = true; |
| access = access->next_grp; |
| } |
| |
| return ret; |
| } |
| |
| /* Return true iff a potential new child of ACC at offset OFFSET and with size |
| SIZE would conflict with an already existing one. If exactly such a child |
| already exists in ACC, store a pointer to it in EXACT_MATCH. */ |
| |
| static bool |
| child_would_conflict_in_acc (struct access *acc, HOST_WIDE_INT norm_offset, |
| HOST_WIDE_INT size, struct access **exact_match) |
| { |
| struct access *child; |
| |
| for (child = acc->first_child; child; child = child->next_sibling) |
| { |
| if (child->offset == norm_offset && child->size == size) |
| { |
| *exact_match = child; |
| return true; |
| } |
| |
| if (child->offset < norm_offset + size |
| && child->offset + child->size > norm_offset) |
| return true; |
| } |
| |
| return false; |
| } |
| |
| /* Create a new child access of PARENT, with all properties just like MODEL |
| except for its offset and with its grp_write false and grp_read true. |
| Return the new access or NULL if it cannot be created. Note that this |
| access is created long after all splicing and sorting, it's not located in |
| any access vector and is automatically a representative of its group. Set |
| the gpr_write flag of the new accesss if SET_GRP_WRITE is true. */ |
| |
| static struct access * |
| create_artificial_child_access (struct access *parent, struct access *model, |
| HOST_WIDE_INT new_offset, |
| bool set_grp_read, bool set_grp_write) |
| { |
| struct access **child; |
| tree expr = parent->base; |
| |
| gcc_assert (!model->grp_unscalarizable_region); |
| |
| struct access *access = access_pool.allocate (); |
| memset (access, 0, sizeof (struct access)); |
| if (!build_user_friendly_ref_for_offset (&expr, TREE_TYPE (expr), new_offset, |
| model->type)) |
| { |
| access->grp_no_warning = true; |
| expr = build_ref_for_model (EXPR_LOCATION (parent->base), parent->base, |
| new_offset, model, NULL, false); |
| } |
| |
| access->base = parent->base; |
| access->expr = expr; |
| access->offset = new_offset; |
| access->size = model->size; |
| access->type = model->type; |
| access->parent = parent; |
| access->grp_read = set_grp_read; |
| access->grp_write = set_grp_write; |
| access->reverse = model->reverse; |
| |
| child = &parent->first_child; |
| while (*child && (*child)->offset < new_offset) |
| child = &(*child)->next_sibling; |
| |
| access->next_sibling = *child; |
| *child = access; |
| |
| return access; |
| } |
| |
| |
| /* Beginning with ACCESS, traverse its whole access subtree and mark all |
| sub-trees as written to. If any of them has not been marked so previously |
| and has assignment links leading from it, re-enqueue it. */ |
| |
| static void |
| subtree_mark_written_and_rhs_enqueue (struct access *access) |
| { |
| if (access->grp_write) |
| return; |
| access->grp_write = true; |
| add_access_to_rhs_work_queue (access); |
| |
| struct access *child; |
| for (child = access->first_child; child; child = child->next_sibling) |
| subtree_mark_written_and_rhs_enqueue (child); |
| } |
| |
| /* If there is still budget to create a propagation access for DECL, return |
| true and decrement the budget. Otherwise return false. */ |
| |
| static bool |
| budget_for_propagation_access (tree decl) |
| { |
| unsigned b, *p = propagation_budget->get (decl); |
| if (p) |
| b = *p; |
| else |
| b = param_sra_max_propagations; |
| |
| if (b == 0) |
| return false; |
| b--; |
| |
| if (b == 0 && dump_file && (dump_flags & TDF_DETAILS)) |
| { |
| fprintf (dump_file, "The propagation budget of "); |
| print_generic_expr (dump_file, decl); |
| fprintf (dump_file, " (UID: %u) has been exhausted.\n", DECL_UID (decl)); |
| } |
| propagation_budget->put (decl, b); |
| return true; |
| } |
| |
| /* Return true if ACC or any of its subaccesses has grp_child set. */ |
| |
| static bool |
| access_or_its_child_written (struct access *acc) |
| { |
| if (acc->grp_write) |
| return true; |
| for (struct access *sub = acc->first_child; sub; sub = sub->next_sibling) |
| if (access_or_its_child_written (sub)) |
| return true; |
| return false; |
| } |
| |
| /* Propagate subaccesses and grp_write flags of RACC across an assignment link |
| to LACC. Enqueue sub-accesses as necessary so that the write flag is |
| propagated transitively. Return true if anything changed. Additionally, if |
| RACC is a scalar access but LACC is not, change the type of the latter, if |
| possible. */ |
| |
| static bool |
| propagate_subaccesses_from_rhs (struct access *lacc, struct access *racc) |
| { |
| struct access *rchild; |
| HOST_WIDE_INT norm_delta = lacc->offset - racc->offset; |
| bool ret = false; |
| |
| /* IF the LHS is still not marked as being written to, we only need to do so |
| if the RHS at this level actually was. */ |
| if (!lacc->grp_write) |
| { |
| gcc_checking_assert (!comes_initialized_p (racc->base)); |
| if (racc->grp_write) |
| { |
| subtree_mark_written_and_rhs_enqueue (lacc); |
| ret = true; |
| } |
| } |
| |
| if (is_gimple_reg_type (lacc->type) |
| || lacc->grp_unscalarizable_region |
| || racc->grp_unscalarizable_region) |
| { |
| if (!lacc->grp_write) |
| { |
| ret = true; |
| subtree_mark_written_and_rhs_enqueue (lacc); |
| } |
| return ret; |
| } |
| |
| if (is_gimple_reg_type (racc->type)) |
| { |
| if (!lacc->grp_write) |
| { |
| ret = true; |
| subtree_mark_written_and_rhs_enqueue (lacc); |
| } |
| if (!lacc->first_child && !racc->first_child) |
| { |
| /* We are about to change the access type from aggregate to scalar, |
| so we need to put the reverse flag onto the access, if any. */ |
| const bool reverse = TYPE_REVERSE_STORAGE_ORDER (lacc->type); |
| tree t = lacc->base; |
| |
| lacc->type = racc->type; |
| if (build_user_friendly_ref_for_offset (&t, TREE_TYPE (t), |
| lacc->offset, racc->type)) |
| { |
| lacc->expr = t; |
| lacc->grp_same_access_path = true; |
| } |
| else |
| { |
| lacc->expr = build_ref_for_model (EXPR_LOCATION (lacc->base), |
| lacc->base, lacc->offset, |
| racc, NULL, false); |
| if (TREE_CODE (lacc->expr) == MEM_REF) |
| REF_REVERSE_STORAGE_ORDER (lacc->expr) = reverse; |
| lacc->grp_no_warning = true; |
| lacc->grp_same_access_path = false; |
| } |
| lacc->reverse = reverse; |
| } |
| return ret; |
| } |
| |
| for (rchild = racc->first_child; rchild; rchild = rchild->next_sibling) |
| { |
| struct access *new_acc = NULL; |
| HOST_WIDE_INT norm_offset = rchild->offset + norm_delta; |
| |
| if (child_would_conflict_in_acc (lacc, norm_offset, rchild->size, |
| &new_acc)) |
| { |
| if (new_acc) |
| { |
| if (!new_acc->grp_write && rchild->grp_write) |
| { |
| gcc_assert (!lacc->grp_write); |
| subtree_mark_written_and_rhs_enqueue (new_acc); |
| ret = true; |
| } |
| |
| rchild->grp_hint = 1; |
| new_acc->grp_hint |= new_acc->grp_read; |
| if (rchild->first_child |
| && propagate_subaccesses_from_rhs (new_acc, rchild)) |
| { |
| ret = 1; |
| add_access_to_rhs_work_queue (new_acc); |
| } |
| } |
| else |
| { |
| if (!lacc->grp_write) |
| { |
| ret = true; |
| subtree_mark_written_and_rhs_enqueue (lacc); |
| } |
| } |
| continue; |
| } |
| |
| if (rchild->grp_unscalarizable_region |
| || !budget_for_propagation_access (lacc->base)) |
| { |
| if (!lacc->grp_write && access_or_its_child_written (rchild)) |
| { |
| ret = true; |
| subtree_mark_written_and_rhs_enqueue (lacc); |
| } |
| continue; |
| } |
| |
| rchild->grp_hint = 1; |
| /* Because get_ref_base_and_extent always includes padding in size for |
| accesses to DECLs but not necessarily for COMPONENT_REFs of the same |
| type, we might be actually attempting to here to create a child of the |
| same type as the parent. */ |
| if (!types_compatible_p (lacc->type, rchild->type)) |
| new_acc = create_artificial_child_access (lacc, rchild, norm_offset, |
| false, |
| (lacc->grp_write |
| || rchild->grp_write)); |
| else |
| new_acc = lacc; |
| gcc_checking_assert (new_acc); |
| if (racc->first_child) |
| propagate_subaccesses_from_rhs (new_acc, rchild); |
| |
| add_access_to_rhs_work_queue (lacc); |
| ret = true; |
| } |
| |
| return ret; |
| } |
| |
| /* Propagate subaccesses of LACC across an assignment link to RACC if they |
| should inhibit total scalarization of the corresponding area. No flags are |
| being propagated in the process. Return true if anything changed. */ |
| |
| static bool |
| propagate_subaccesses_from_lhs (struct access *lacc, struct access *racc) |
| { |
| if (is_gimple_reg_type (racc->type) |
| || lacc->grp_unscalarizable_region |
| || racc->grp_unscalarizable_region) |
| return false; |
| |
| /* TODO: Do we want set some new racc flag to stop potential total |
| scalarization if lacc is a scalar access (and none fo the two have |
| children)? */ |
| |
| bool ret = false; |
| HOST_WIDE_INT norm_delta = racc->offset - lacc->offset; |
| for (struct access *lchild = lacc->first_child; |
| lchild; |
| lchild = lchild->next_sibling) |
| { |
| struct access *matching_acc = NULL; |
| HOST_WIDE_INT norm_offset = lchild->offset + norm_delta; |
| |
| if (lchild->grp_unscalarizable_region |
| || child_would_conflict_in_acc (racc, norm_offset, lchild->size, |
| &matching_acc) |
| || !budget_for_propagation_access (racc->base)) |
| { |
| if (matching_acc |
| && propagate_subaccesses_from_lhs (lchild, matching_acc)) |
| add_access_to_lhs_work_queue (matching_acc); |
| continue; |
| } |
| |
| /* Because get_ref_base_and_extent always includes padding in size for |
| accesses to DECLs but not necessarily for COMPONENT_REFs of the same |
| type, we might be actually attempting to here to create a child of the |
| same type as the parent. */ |
| if (!types_compatible_p (racc->type, lchild->type)) |
| { |
| struct access *new_acc |
| = create_artificial_child_access (racc, lchild, norm_offset, |
| true, false); |
| propagate_subaccesses_from_lhs (lchild, new_acc); |
| } |
| else |
| propagate_subaccesses_from_lhs (lchild, racc); |
| ret = true; |
| } |
| return ret; |
| } |
| |
| /* Propagate all subaccesses across assignment links. */ |
| |
| static void |
| propagate_all_subaccesses (void) |
| { |
| propagation_budget = new hash_map<tree, unsigned>; |
| while (rhs_work_queue_head) |
| { |
| struct access *racc = pop_access_from_rhs_work_queue (); |
| struct assign_link *link; |
| |
| if (racc->group_representative) |
| racc= racc->group_representative; |
| gcc_assert (racc->first_rhs_link); |
| |
| for (link = racc->first_rhs_link; link; link = link->next_rhs) |
| { |
| struct access *lacc = link->lacc; |
| |
| if (!bitmap_bit_p (candidate_bitmap, DECL_UID (lacc->base))) |
| continue; |
| lacc = lacc->group_representative; |
| |
| bool reque_parents = false; |
| if (!bitmap_bit_p (candidate_bitmap, DECL_UID (racc->base))) |
| { |
| if (!lacc->grp_write) |
| { |
| subtree_mark_written_and_rhs_enqueue (lacc); |
| reque_parents = true; |
| } |
| } |
| else if (propagate_subaccesses_from_rhs (lacc, racc)) |
| reque_parents = true; |
| |
| if (reque_parents) |
| do |
| { |
| add_access_to_rhs_work_queue (lacc); |
| lacc = lacc->parent; |
| } |
| while (lacc); |
| } |
| } |
| |
| while (lhs_work_queue_head) |
| { |
| struct access *lacc = pop_access_from_lhs_work_queue (); |
| struct assign_link *link; |
| |
| if (lacc->group_representative) |
| lacc = lacc->group_representative; |
| gcc_assert (lacc->first_lhs_link); |
| |
| if (!bitmap_bit_p (candidate_bitmap, DECL_UID (lacc->base))) |
| continue; |
| |
| for (link = lacc->first_lhs_link; link; link = link->next_lhs) |
| { |
| struct access *racc = link->racc; |
| |
| if (racc->group_representative) |
| racc = racc->group_representative; |
| if (!bitmap_bit_p (candidate_bitmap, DECL_UID (racc->base))) |
| continue; |
| if (propagate_subaccesses_from_lhs (lacc, racc)) |
| add_access_to_lhs_work_queue (racc); |
| } |
| } |
| delete propagation_budget; |
| } |
| |
| /* Return true if the forest beginning with ROOT does not contain |
| unscalarizable regions or non-byte aligned accesses. */ |
| |
| static bool |
| can_totally_scalarize_forest_p (struct access *root) |
| { |
| struct access *access = root; |
| do |
| { |
| if (access->grp_unscalarizable_region |
| || (access->offset % BITS_PER_UNIT) != 0 |
| || (access->size % BITS_PER_UNIT) != 0 |
| || (is_gimple_reg_type (access->type) |
| && access->first_child)) |
| return false; |
| |
| if (access->first_child) |
| access = access->first_child; |
| else if (access->next_sibling) |
| access = access->next_sibling; |
| else |
| { |
| while (access->parent && !access->next_sibling) |
| access = access->parent; |
| if (access->next_sibling) |
| access = access->next_sibling; |
| else |
| { |
| gcc_assert (access == root); |
| root = root->next_grp; |
| access = root; |
| } |
| } |
| } |
| while (access); |
| return true; |
| } |
| |
| /* Create and return an ACCESS in PARENT spanning from POS with SIZE, TYPE and |
| reference EXPR for total scalarization purposes and mark it as such. Within |
| the children of PARENT, link it in between PTR and NEXT_SIBLING. */ |
| |
| static struct access * |
| create_total_scalarization_access (struct access *parent, HOST_WIDE_INT pos, |
| HOST_WIDE_INT size, tree type, tree expr, |
| struct access **ptr, |
| struct access *next_sibling) |
| { |
| struct access *access = access_pool.allocate (); |
| memset (access, 0, sizeof (struct access)); |
| access->base = parent->base; |
| access->offset = pos; |
| access->size = size; |
| access->expr = expr; |
| access->type = type; |
| access->parent = parent; |
| access->grp_write = parent->grp_write; |
| access->grp_total_scalarization = 1; |
| access->grp_hint = 1; |
| access->grp_same_access_path = path_comparable_for_same_access (expr); |
| access->reverse = reverse_storage_order_for_component_p (expr); |
| |
| access->next_sibling = next_sibling; |
| *ptr = access; |
| return access; |
| } |
| |
| /* Create and return an ACCESS in PARENT spanning from POS with SIZE, TYPE and |
| reference EXPR for total scalarization purposes and mark it as such, link it |
| at *PTR and reshape the tree so that those elements at *PTR and their |
| siblings which fall within the part described by POS and SIZE are moved to |
| be children of the new access. If a partial overlap is detected, return |
| NULL. */ |
| |
| static struct access * |
| create_total_access_and_reshape (struct access *parent, HOST_WIDE_INT pos, |
| HOST_WIDE_INT size, tree type, tree expr, |
| struct access **ptr) |
| { |
| struct access **p = ptr; |
| |
| while (*p && (*p)->offset < pos + size) |
| { |
| if ((*p)->offset + (*p)->size > pos + size) |
| return NULL; |
| p = &(*p)->next_sibling; |
| } |
| |
| struct access *next_child = *ptr; |
| struct access *new_acc |
| = create_total_scalarization_access (parent, pos, size, type, expr, |
| ptr, *p); |
| if (p != ptr) |
| { |
| new_acc->first_child = next_child; |
| *p = NULL; |
| for (struct access *a = next_child; a; a = a->next_sibling) |
| a->parent = new_acc; |
| } |
| return new_acc; |
| } |
| |
| static bool totally_scalarize_subtree (struct access *root); |
| |
| /* Return true if INNER is either the same type as OUTER or if it is the type |
| of a record field in OUTER at offset zero, possibly in nested |
| sub-records. */ |
| |
| static bool |
| access_and_field_type_match_p (tree outer, tree inner) |
| { |
| if (TYPE_MAIN_VARIANT (outer) == TYPE_MAIN_VARIANT (inner)) |
| return true; |
| if (TREE_CODE (outer) != RECORD_TYPE) |
| return false; |
| tree fld = TYPE_FIELDS (outer); |
| while (fld) |
| { |
| if (TREE_CODE (fld) == FIELD_DECL) |
| { |
| if (!zerop (DECL_FIELD_OFFSET (fld))) |
| return false; |
| if (TYPE_MAIN_VARIANT (TREE_TYPE (fld)) == inner) |
| return true; |
| if (TREE_CODE (TREE_TYPE (fld)) == RECORD_TYPE) |
| fld = TYPE_FIELDS (TREE_TYPE (fld)); |
| else |
| return false; |
| } |
| else |
| fld = DECL_CHAIN (fld); |
| } |
| return false; |
| } |
| |
| /* Return type of total_should_skip_creating_access indicating whether a total |
| scalarization access for a field/element should be created, whether it |
| already exists or whether the entire total scalarization has to fail. */ |
| |
| enum total_sra_field_state {TOTAL_FLD_CREATE, TOTAL_FLD_DONE, TOTAL_FLD_FAILED}; |
| |
| /* Do all the necessary steps in total scalarization when the given aggregate |
| type has a TYPE at POS with the given SIZE should be put into PARENT and |
| when we have processed all its siblings with smaller offsets up until and |
| including LAST_SEEN_SIBLING (which can be NULL). |
| |
| If some further siblings are to be skipped, set *LAST_SEEN_SIBLING as |
| appropriate. Return TOTAL_FLD_CREATE id the caller should carry on with |
| creating a new access, TOTAL_FLD_DONE if access or accesses capable of |
| representing the described part of the aggregate for the purposes of total |
| scalarization already exist or TOTAL_FLD_FAILED if there is a problem which |
| prevents total scalarization from happening at all. */ |
| |
| static enum total_sra_field_state |
| total_should_skip_creating_access (struct access *parent, |
| struct access **last_seen_sibling, |
| tree type, HOST_WIDE_INT pos, |
| HOST_WIDE_INT size) |
| { |
| struct access *next_child; |
| if (!*last_seen_sibling) |
| next_child = parent->first_child; |
| else |
| next_child = (*last_seen_sibling)->next_sibling; |
| |
| /* First, traverse the chain of siblings until it points to an access with |
| offset at least equal to POS. Check all skipped accesses whether they |
| span the POS boundary and if so, return with a failure. */ |
| while (next_child && next_child->offset < pos) |
| { |
| if (next_child->offset + next_child->size > pos) |
| return TOTAL_FLD_FAILED; |
| *last_seen_sibling = next_child; |
| next_child = next_child->next_sibling; |
| } |
| |
| /* Now check whether next_child has exactly the right POS and SIZE and if so, |
| whether it can represent what we need and can be totally scalarized |
| itself. */ |
| if (next_child && next_child->offset == pos |
| && next_child->size == size) |
| { |
| if (!is_gimple_reg_type (next_child->type) |
| && (!access_and_field_type_match_p (type, next_child->type) |
| || !totally_scalarize_subtree (next_child))) |
|