1 /* Scalar Replacement of Aggregates (SRA) converts some structure
2 references into scalar references, exposing them to the scalar
4 Copyright (C) 2008, 2009 Free Software Foundation, Inc.
5 Contributed by Martin Jambor <mjambor@suse.cz>
7 This file is part of GCC.
9 GCC is free software; you can redistribute it and/or modify it under
10 the terms of the GNU General Public License as published by the Free
11 Software Foundation; either version 3, or (at your option) any later
14 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
15 WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING3. If not see
21 <http://www.gnu.org/licenses/>. */
23 /* This file implements Scalar Reduction of Aggregates (SRA). SRA is run
24 twice, once in the early stages of compilation (early SRA) and once in the
25 late stages (late SRA). The aim of both is to turn references to scalar
26 parts of aggregates into uses of independent scalar variables.
28 The two passes are nearly identical, the only difference is that early SRA
29 does not scalarize unions which are used as the result in a GIMPLE_RETURN
30 statement because together with inlining this can lead to weird type
33 Both passes operate in four stages:
35 1. The declarations that have properties which make them candidates for
36 scalarization are identified in function find_var_candidates(). The
37 candidates are stored in candidate_bitmap.
39 2. The function body is scanned. In the process, declarations which are
40 used in a manner that prevent their scalarization are removed from the
41 candidate bitmap. More importantly, for every access into an aggregate,
42 an access structure (struct access) is created by create_access() and
43 stored in a vector associated with the aggregate. Among other
44 information, the aggregate declaration, the offset and size of the access
45 and its type are stored in the structure.
47 On a related note, assign_link structures are created for every assign
48 statement between candidate aggregates and attached to the related
51 3. The vectors of accesses are analyzed. They are first sorted according to
52 their offset and size and then scanned for partially overlapping accesses
53 (i.e. those which overlap but one is not entirely within another). Such
54 an access disqualifies the whole aggregate from being scalarized.
56 If there is no such inhibiting overlap, a representative access structure
57 is chosen for every unique combination of offset and size. Afterwards,
58 the pass builds a set of trees from these structures, in which children
59 of an access are within their parent (in terms of offset and size).
61 Then accesses are propagated whenever possible (i.e. in cases when it
62 does not create a partially overlapping access) across assign_links from
63 the right hand side to the left hand side.
65 Then the set of trees for each declaration is traversed again and those
66 accesses which should be replaced by a scalar are identified.
68 4. The function is traversed again, and for every reference into an
69 aggregate that has some component which is about to be scalarized,
70 statements are amended and new statements are created as necessary.
71 Finally, if a parameter got scalarized, the scalar replacements are
72 initialized with values from respective parameter aggregates. */
76 #include "coretypes.h"
77 #include "alloc-pool.h"
81 #include "tree-flow.h"
83 #include "diagnostic.h"
84 #include "statistics.h"
85 #include "tree-dump.h"
91 /* Enumeration of all aggregate reductions we can do. */
92 enum sra_mode { SRA_MODE_EARLY_INTRA, /* early intraprocedural SRA */
93 SRA_MODE_INTRA }; /* late intraprocedural SRA */
95 /* Global variable describing which aggregate reduction we are performing at
97 static enum sra_mode sra_mode;
101 /* ACCESS represents each access to an aggregate variable (as a whole or a
102 part). It can also represent a group of accesses that refer to exactly the
103 same fragment of an aggregate (i.e. those that have exactly the same offset
104 and size). Such representatives for a single aggregate, once determined,
105 are linked in a linked list and have the group fields set.
107 Moreover, when doing intraprocedural SRA, a tree is built from those
108 representatives (by the means of first_child and next_sibling pointers), in
109 which all items in a subtree are "within" the root, i.e. their offset is
110 greater or equal to offset of the root and offset+size is smaller or equal
111 to offset+size of the root. Children of an access are sorted by offset.
113 Note that accesses to parts of vector and complex number types always
114 represented by an access to the whole complex number or a vector. It is a
115 duty of the modifying functions to replace them appropriately. */
119 /* Values returned by `get_ref_base_and_extent' for each component reference
120 If EXPR isn't a component reference just set `BASE = EXPR', `OFFSET = 0',
121 `SIZE = TREE_SIZE (TREE_TYPE (expr))'. */
122 HOST_WIDE_INT offset;
131 /* Next group representative for this aggregate. */
132 struct access *next_grp;
134 /* Pointer to the group representative. Pointer to itself if the struct is
135 the representative. */
136 struct access *group_representative;
138 /* If this access has any children (in terms of the definition above), this
139 points to the first one. */
140 struct access *first_child;
142 /* Pointer to the next sibling in the access tree as described above. */
143 struct access *next_sibling;
145 /* Pointers to the first and last element in the linked list of assign
147 struct assign_link *first_link, *last_link;
149 /* Pointer to the next access in the work queue. */
150 struct access *next_queued;
152 /* Replacement variable for this access "region." Never to be accessed
153 directly, always only by the means of get_access_replacement() and only
154 when grp_to_be_replaced flag is set. */
155 tree replacement_decl;
157 /* Is this particular access write access? */
160 /* Is this access currently in the work queue? */
161 unsigned grp_queued : 1;
162 /* Does this group contain a write access? This flag is propagated down the
164 unsigned grp_write : 1;
165 /* Does this group contain a read access? This flag is propagated down the
167 unsigned grp_read : 1;
168 /* Other passes of the analysis use this bit to make function
169 analyze_access_subtree create scalar replacements for this group if
171 unsigned grp_hint : 1;
172 /* Is the subtree rooted in this access fully covered by scalar
174 unsigned grp_covered : 1;
175 /* If set to true, this access and all below it in an access tree must not be
177 unsigned grp_unscalarizable_region : 1;
178 /* Whether data have been written to parts of the aggregate covered by this
179 access which is not to be scalarized. This flag is propagated up in the
181 unsigned grp_unscalarized_data : 1;
182 /* Does this access and/or group contain a write access through a
184 unsigned grp_partial_lhs : 1;
186 /* Set when a scalar replacement should be created for this variable. We do
187 the decision and creation at different places because create_tmp_var
188 cannot be called from within FOR_EACH_REFERENCED_VAR. */
189 unsigned grp_to_be_replaced : 1;
192 typedef struct access *access_p;
194 DEF_VEC_P (access_p);
195 DEF_VEC_ALLOC_P (access_p, heap);
197 /* Alloc pool for allocating access structures. */
198 static alloc_pool access_pool;
200 /* A structure linking lhs and rhs accesses from an aggregate assignment. They
201 are used to propagate subaccesses from rhs to lhs as long as they don't
202 conflict with what is already there. */
205 struct access *lacc, *racc;
206 struct assign_link *next;
209 /* Alloc pool for allocating assign link structures. */
210 static alloc_pool link_pool;
212 /* Base (tree) -> Vector (VEC(access_p,heap) *) map. */
213 static struct pointer_map_t *base_access_vec;
215 /* Bitmap of bases (candidates). */
216 static bitmap candidate_bitmap;
217 /* Obstack for creation of fancy names. */
218 static struct obstack name_obstack;
220 /* Head of a linked list of accesses that need to have its subaccesses
221 propagated to their assignment counterparts. */
222 static struct access *work_queue_head;
224 /* Dump contents of ACCESS to file F in a human friendly way. If GRP is true,
225 representative fields are dumped, otherwise those which only describe the
226 individual access are. */
230 /* Number of created scalar replacements. */
233 /* Number of times sra_modify_expr or sra_modify_assign themselves changed an
237 /* Number of statements created by generate_subtree_copies. */
240 /* Number of statements created by load_assign_lhs_subreplacements. */
243 /* Number of times sra_modify_assign has deleted a statement. */
246 /* Number of times sra_modify_assign has to deal with subaccesses of LHS and
247 RHS reparately due to type conversions or nonexistent matching
249 int separate_lhs_rhs_handling;
251 /* Number of processed aggregates is readily available in
252 analyze_all_variable_accesses and so is not stored here. */
256 dump_access (FILE *f, struct access *access, bool grp)
258 fprintf (f, "access { ");
259 fprintf (f, "base = (%d)'", DECL_UID (access->base));
260 print_generic_expr (f, access->base, 0);
261 fprintf (f, "', offset = " HOST_WIDE_INT_PRINT_DEC, access->offset);
262 fprintf (f, ", size = " HOST_WIDE_INT_PRINT_DEC, access->size);
263 fprintf (f, ", expr = ");
264 print_generic_expr (f, access->expr, 0);
265 fprintf (f, ", type = ");
266 print_generic_expr (f, access->type, 0);
268 fprintf (f, ", grp_write = %d, grp_read = %d, grp_hint = %d, "
269 "grp_covered = %d, grp_unscalarizable_region = %d, "
270 "grp_unscalarized_data = %d, grp_partial_lhs = %d, "
271 "grp_to_be_replaced = %d\n",
272 access->grp_write, access->grp_read, access->grp_hint,
273 access->grp_covered, access->grp_unscalarizable_region,
274 access->grp_unscalarized_data, access->grp_partial_lhs,
275 access->grp_to_be_replaced);
277 fprintf (f, ", write = %d, grp_partial_lhs = %d\n", access->write,
278 access->grp_partial_lhs);
281 /* Dump a subtree rooted in ACCESS to file F, indent by LEVEL. */
284 dump_access_tree_1 (FILE *f, struct access *access, int level)
290 for (i = 0; i < level; i++)
291 fputs ("* ", dump_file);
293 dump_access (f, access, true);
295 if (access->first_child)
296 dump_access_tree_1 (f, access->first_child, level + 1);
298 access = access->next_sibling;
303 /* Dump all access trees for a variable, given the pointer to the first root in
307 dump_access_tree (FILE *f, struct access *access)
309 for (; access; access = access->next_grp)
310 dump_access_tree_1 (f, access, 0);
313 /* Return true iff ACC is non-NULL and has subaccesses. */
316 access_has_children_p (struct access *acc)
318 return acc && acc->first_child;
321 /* Return a vector of pointers to accesses for the variable given in BASE or
322 NULL if there is none. */
324 static VEC (access_p, heap) *
325 get_base_access_vector (tree base)
329 slot = pointer_map_contains (base_access_vec, base);
333 return *(VEC (access_p, heap) **) slot;
336 /* Find an access with required OFFSET and SIZE in a subtree of accesses rooted
337 in ACCESS. Return NULL if it cannot be found. */
339 static struct access *
340 find_access_in_subtree (struct access *access, HOST_WIDE_INT offset,
343 while (access && (access->offset != offset || access->size != size))
345 struct access *child = access->first_child;
347 while (child && (child->offset + child->size <= offset))
348 child = child->next_sibling;
355 /* Return the first group representative for DECL or NULL if none exists. */
357 static struct access *
358 get_first_repr_for_decl (tree base)
360 VEC (access_p, heap) *access_vec;
362 access_vec = get_base_access_vector (base);
366 return VEC_index (access_p, access_vec, 0);
369 /* Find an access representative for the variable BASE and given OFFSET and
370 SIZE. Requires that access trees have already been built. Return NULL if
371 it cannot be found. */
373 static struct access *
374 get_var_base_offset_size_access (tree base, HOST_WIDE_INT offset,
377 struct access *access;
379 access = get_first_repr_for_decl (base);
380 while (access && (access->offset + access->size <= offset))
381 access = access->next_grp;
385 return find_access_in_subtree (access, offset, size);
388 /* Add LINK to the linked list of assign links of RACC. */
390 add_link_to_rhs (struct access *racc, struct assign_link *link)
392 gcc_assert (link->racc == racc);
394 if (!racc->first_link)
396 gcc_assert (!racc->last_link);
397 racc->first_link = link;
400 racc->last_link->next = link;
402 racc->last_link = link;
406 /* Move all link structures in their linked list in OLD_RACC to the linked list
409 relink_to_new_repr (struct access *new_racc, struct access *old_racc)
411 if (!old_racc->first_link)
413 gcc_assert (!old_racc->last_link);
417 if (new_racc->first_link)
419 gcc_assert (!new_racc->last_link->next);
420 gcc_assert (!old_racc->last_link || !old_racc->last_link->next);
422 new_racc->last_link->next = old_racc->first_link;
423 new_racc->last_link = old_racc->last_link;
427 gcc_assert (!new_racc->last_link);
429 new_racc->first_link = old_racc->first_link;
430 new_racc->last_link = old_racc->last_link;
432 old_racc->first_link = old_racc->last_link = NULL;
435 /* Add ACCESS to the work queue (which is actually a stack). */
438 add_access_to_work_queue (struct access *access)
440 if (!access->grp_queued)
442 gcc_assert (!access->next_queued);
443 access->next_queued = work_queue_head;
444 access->grp_queued = 1;
445 work_queue_head = access;
449 /* Pop an access from the work queue, and return it, assuming there is one. */
451 static struct access *
452 pop_access_from_work_queue (void)
454 struct access *access = work_queue_head;
456 work_queue_head = access->next_queued;
457 access->next_queued = NULL;
458 access->grp_queued = 0;
463 /* Allocate necessary structures. */
466 sra_initialize (void)
468 candidate_bitmap = BITMAP_ALLOC (NULL);
469 gcc_obstack_init (&name_obstack);
470 access_pool = create_alloc_pool ("SRA accesses", sizeof (struct access), 16);
471 link_pool = create_alloc_pool ("SRA links", sizeof (struct assign_link), 16);
472 base_access_vec = pointer_map_create ();
473 memset (&sra_stats, 0, sizeof (sra_stats));
476 /* Hook fed to pointer_map_traverse, deallocate stored vectors. */
479 delete_base_accesses (const void *key ATTRIBUTE_UNUSED, void **value,
480 void *data ATTRIBUTE_UNUSED)
482 VEC (access_p, heap) *access_vec;
483 access_vec = (VEC (access_p, heap) *) *value;
484 VEC_free (access_p, heap, access_vec);
489 /* Deallocate all general structures. */
492 sra_deinitialize (void)
494 BITMAP_FREE (candidate_bitmap);
495 free_alloc_pool (access_pool);
496 free_alloc_pool (link_pool);
497 obstack_free (&name_obstack, NULL);
499 pointer_map_traverse (base_access_vec, delete_base_accesses, NULL);
500 pointer_map_destroy (base_access_vec);
503 /* Remove DECL from candidates for SRA and write REASON to the dump file if
506 disqualify_candidate (tree decl, const char *reason)
508 bitmap_clear_bit (candidate_bitmap, DECL_UID (decl));
510 if (dump_file && (dump_flags & TDF_DETAILS))
512 fprintf (dump_file, "! Disqualifying ");
513 print_generic_expr (dump_file, decl, 0);
514 fprintf (dump_file, " - %s\n", reason);
518 /* Return true iff the type contains a field or an element which does not allow
522 type_internals_preclude_sra_p (tree type)
527 switch (TREE_CODE (type))
531 case QUAL_UNION_TYPE:
532 for (fld = TYPE_FIELDS (type); fld; fld = TREE_CHAIN (fld))
533 if (TREE_CODE (fld) == FIELD_DECL)
535 tree ft = TREE_TYPE (fld);
537 if (TREE_THIS_VOLATILE (fld)
538 || !DECL_FIELD_OFFSET (fld) || !DECL_SIZE (fld)
539 || !host_integerp (DECL_FIELD_OFFSET (fld), 1)
540 || !host_integerp (DECL_SIZE (fld), 1))
543 if (AGGREGATE_TYPE_P (ft)
544 && type_internals_preclude_sra_p (ft))
551 et = TREE_TYPE (type);
553 if (AGGREGATE_TYPE_P (et))
554 return type_internals_preclude_sra_p (et);
563 /* Create and insert access for EXPR. Return created access, or NULL if it is
566 static struct access *
567 create_access (tree expr, bool write)
569 struct access *access;
571 VEC (access_p,heap) *vec;
572 HOST_WIDE_INT offset, size, max_size;
574 bool unscalarizable_region = false;
576 base = get_ref_base_and_extent (expr, &offset, &size, &max_size);
578 if (!DECL_P (base) || !bitmap_bit_p (candidate_bitmap, DECL_UID (base)))
581 if (size != max_size)
584 unscalarizable_region = true;
589 disqualify_candidate (base, "Encountered an unconstrained access.");
593 access = (struct access *) pool_alloc (access_pool);
594 memset (access, 0, sizeof (struct access));
597 access->offset = offset;
600 access->type = TREE_TYPE (expr);
601 access->write = write;
602 access->grp_unscalarizable_region = unscalarizable_region;
604 slot = pointer_map_contains (base_access_vec, base);
606 vec = (VEC (access_p, heap) *) *slot;
608 vec = VEC_alloc (access_p, heap, 32);
610 VEC_safe_push (access_p, heap, vec, access);
612 *((struct VEC (access_p,heap) **)
613 pointer_map_insert (base_access_vec, base)) = vec;
619 /* Search the given tree for a declaration by skipping handled components and
620 exclude it from the candidates. */
623 disqualify_base_of_expr (tree t, const char *reason)
625 while (handled_component_p (t))
626 t = TREE_OPERAND (t, 0);
629 disqualify_candidate (t, reason);
632 /* Scan expression EXPR and create access structures for all accesses to
633 candidates for scalarization. Return the created access or NULL if none is
636 static struct access *
637 build_access_from_expr_1 (tree *expr_ptr, bool write)
639 struct access *ret = NULL;
640 tree expr = *expr_ptr;
643 if (TREE_CODE (expr) == BIT_FIELD_REF
644 || TREE_CODE (expr) == IMAGPART_EXPR
645 || TREE_CODE (expr) == REALPART_EXPR)
647 expr = TREE_OPERAND (expr, 0);
653 /* We need to dive through V_C_Es in order to get the size of its parameter
654 and not the result type. Ada produces such statements. We are also
655 capable of handling the topmost V_C_E but not any of those buried in other
656 handled components. */
657 if (TREE_CODE (expr) == VIEW_CONVERT_EXPR)
658 expr = TREE_OPERAND (expr, 0);
660 if (contains_view_convert_expr_p (expr))
662 disqualify_base_of_expr (expr, "V_C_E under a different handled "
667 switch (TREE_CODE (expr))
674 case ARRAY_RANGE_REF:
675 ret = create_access (expr, write);
682 if (write && partial_ref && ret)
683 ret->grp_partial_lhs = 1;
688 /* Callback of scan_function. Scan expression EXPR and create access
689 structures for all accesses to candidates for scalarization. Return true if
690 any access has been inserted. */
693 build_access_from_expr (tree *expr_ptr,
694 gimple_stmt_iterator *gsi ATTRIBUTE_UNUSED, bool write,
695 void *data ATTRIBUTE_UNUSED)
697 return build_access_from_expr_1 (expr_ptr, write) != NULL;
700 /* Disqualify LHS and RHS for scalarization if STMT must end its basic block in
701 modes in which it matters, return true iff they have been disqualified. RHS
702 may be NULL, in that case ignore it. If we scalarize an aggregate in
703 intra-SRA we may need to add statements after each statement. This is not
704 possible if a statement unconditionally has to end the basic block. */
706 disqualify_ops_if_throwing_stmt (gimple stmt, tree lhs, tree rhs)
708 if (stmt_can_throw_internal (stmt) || stmt_ends_bb_p (stmt))
710 disqualify_base_of_expr (lhs, "LHS of a throwing stmt.");
712 disqualify_base_of_expr (rhs, "RHS of a throwing stmt.");
719 /* Result code for scan_assign callback for scan_function. */
720 enum scan_assign_result { SRA_SA_NONE, /* nothing done for the stmt */
721 SRA_SA_PROCESSED, /* stmt analyzed/changed */
722 SRA_SA_REMOVED }; /* stmt redundant and eliminated */
725 /* Callback of scan_function. Scan expressions occuring in the statement
726 pointed to by STMT_EXPR, create access structures for all accesses to
727 candidates for scalarization and remove those candidates which occur in
728 statements or expressions that prevent them from being split apart. Return
729 true if any access has been inserted. */
731 static enum scan_assign_result
732 build_accesses_from_assign (gimple *stmt_ptr,
733 gimple_stmt_iterator *gsi ATTRIBUTE_UNUSED,
734 void *data ATTRIBUTE_UNUSED)
736 gimple stmt = *stmt_ptr;
737 tree *lhs_ptr, *rhs_ptr;
738 struct access *lacc, *racc;
740 if (!gimple_assign_single_p (stmt))
743 lhs_ptr = gimple_assign_lhs_ptr (stmt);
744 rhs_ptr = gimple_assign_rhs1_ptr (stmt);
746 if (disqualify_ops_if_throwing_stmt (stmt, *lhs_ptr, *rhs_ptr))
749 racc = build_access_from_expr_1 (rhs_ptr, false);
750 lacc = build_access_from_expr_1 (lhs_ptr, true);
753 && !lacc->grp_unscalarizable_region
754 && !racc->grp_unscalarizable_region
755 && AGGREGATE_TYPE_P (TREE_TYPE (*lhs_ptr))
756 /* FIXME: Turn the following line into an assert after PR 40058 is
758 && lacc->size == racc->size
759 && useless_type_conversion_p (lacc->type, racc->type))
761 struct assign_link *link;
763 link = (struct assign_link *) pool_alloc (link_pool);
764 memset (link, 0, sizeof (struct assign_link));
769 add_link_to_rhs (racc, link);
772 return (lacc || racc) ? SRA_SA_PROCESSED : SRA_SA_NONE;
775 /* Callback of walk_stmt_load_store_addr_ops visit_addr used to determine
776 GIMPLE_ASM operands with memory constrains which cannot be scalarized. */
779 asm_visit_addr (gimple stmt ATTRIBUTE_UNUSED, tree op,
780 void *data ATTRIBUTE_UNUSED)
783 disqualify_candidate (op, "Non-scalarizable GIMPLE_ASM operand.");
789 /* Scan function and look for interesting statements. Return true if any has
790 been found or processed, as indicated by callbacks. SCAN_EXPR is a callback
791 called on all expressions within statements except assign statements and
792 those deemed entirely unsuitable for some reason (all operands in such
793 statements and expression are removed from candidate_bitmap). SCAN_ASSIGN
794 is a callback called on all assign statements, HANDLE_SSA_DEFS is a callback
795 called on assign statements and those call statements which have a lhs and
796 it is the only callback which can be NULL. ANALYSIS_STAGE is true when
797 running in the analysis stage of a pass and thus no statement is being
798 modified. DATA is a pointer passed to all callbacks. If any single
799 callback returns true, this function also returns true, otherwise it returns
803 scan_function (bool (*scan_expr) (tree *, gimple_stmt_iterator *, bool, void *),
804 enum scan_assign_result (*scan_assign) (gimple *,
805 gimple_stmt_iterator *,
807 bool (*handle_ssa_defs)(gimple, void *),
808 bool analysis_stage, void *data)
810 gimple_stmt_iterator gsi;
818 bool bb_changed = false;
820 gsi = gsi_start_bb (bb);
821 while (!gsi_end_p (gsi))
823 gimple stmt = gsi_stmt (gsi);
824 enum scan_assign_result assign_result;
825 bool any = false, deleted = false;
827 switch (gimple_code (stmt))
830 t = gimple_return_retval_ptr (stmt);
832 any |= scan_expr (t, &gsi, false, data);
836 assign_result = scan_assign (&stmt, &gsi, data);
837 any |= assign_result == SRA_SA_PROCESSED;
838 deleted = assign_result == SRA_SA_REMOVED;
839 if (handle_ssa_defs && assign_result != SRA_SA_REMOVED)
840 any |= handle_ssa_defs (stmt, data);
844 /* Operands must be processed before the lhs. */
845 for (i = 0; i < gimple_call_num_args (stmt); i++)
847 tree *argp = gimple_call_arg_ptr (stmt, i);
848 any |= scan_expr (argp, &gsi, false, data);
851 if (gimple_call_lhs (stmt))
853 tree *lhs_ptr = gimple_call_lhs_ptr (stmt);
855 || !disqualify_ops_if_throwing_stmt (stmt,
858 any |= scan_expr (lhs_ptr, &gsi, true, data);
860 any |= handle_ssa_defs (stmt, data);
868 walk_stmt_load_store_addr_ops (stmt, NULL, NULL, NULL,
870 for (i = 0; i < gimple_asm_ninputs (stmt); i++)
872 tree *op = &TREE_VALUE (gimple_asm_input_op (stmt, i));
873 any |= scan_expr (op, &gsi, false, data);
875 for (i = 0; i < gimple_asm_noutputs (stmt); i++)
877 tree *op = &TREE_VALUE (gimple_asm_output_op (stmt, i));
878 any |= scan_expr (op, &gsi, true, data);
893 if (!stmt_could_throw_p (stmt))
894 remove_stmt_from_eh_region (stmt);
905 if (!analysis_stage && bb_changed)
906 gimple_purge_dead_eh_edges (bb);
912 /* Helper of QSORT function. There are pointers to accesses in the array. An
913 access is considered smaller than another if it has smaller offset or if the
914 offsets are the same but is size is bigger. */
917 compare_access_positions (const void *a, const void *b)
919 const access_p *fp1 = (const access_p *) a;
920 const access_p *fp2 = (const access_p *) b;
921 const access_p f1 = *fp1;
922 const access_p f2 = *fp2;
924 if (f1->offset != f2->offset)
925 return f1->offset < f2->offset ? -1 : 1;
927 if (f1->size == f2->size)
929 /* Put any non-aggregate type before any aggregate type. */
930 if (!is_gimple_reg_type (f1->type)
931 && is_gimple_reg_type (f2->type))
933 else if (is_gimple_reg_type (f1->type)
934 && !is_gimple_reg_type (f2->type))
936 /* Put the integral type with the bigger precision first. */
937 else if (INTEGRAL_TYPE_P (f1->type)
938 && INTEGRAL_TYPE_P (f2->type))
939 return TYPE_PRECISION (f1->type) > TYPE_PRECISION (f2->type) ? -1 : 1;
940 /* Put any integral type with non-full precision last. */
941 else if (INTEGRAL_TYPE_P (f1->type)
942 && (TREE_INT_CST_LOW (TYPE_SIZE (f1->type))
943 != TYPE_PRECISION (f1->type)))
945 else if (INTEGRAL_TYPE_P (f2->type)
946 && (TREE_INT_CST_LOW (TYPE_SIZE (f2->type))
947 != TYPE_PRECISION (f2->type)))
949 /* Stabilize the sort. */
950 return TYPE_UID (f1->type) - TYPE_UID (f2->type);
953 /* We want the bigger accesses first, thus the opposite operator in the next
955 return f1->size > f2->size ? -1 : 1;
959 /* Append a name of the declaration to the name obstack. A helper function for
963 make_fancy_decl_name (tree decl)
967 tree name = DECL_NAME (decl);
969 obstack_grow (&name_obstack, IDENTIFIER_POINTER (name),
970 IDENTIFIER_LENGTH (name));
973 sprintf (buffer, "D%u", DECL_UID (decl));
974 obstack_grow (&name_obstack, buffer, strlen (buffer));
978 /* Helper for make_fancy_name. */
981 make_fancy_name_1 (tree expr)
988 make_fancy_decl_name (expr);
992 switch (TREE_CODE (expr))
995 make_fancy_name_1 (TREE_OPERAND (expr, 0));
996 obstack_1grow (&name_obstack, '$');
997 make_fancy_decl_name (TREE_OPERAND (expr, 1));
1001 make_fancy_name_1 (TREE_OPERAND (expr, 0));
1002 obstack_1grow (&name_obstack, '$');
1003 /* Arrays with only one element may not have a constant as their
1005 index = TREE_OPERAND (expr, 1);
1006 if (TREE_CODE (index) != INTEGER_CST)
1008 sprintf (buffer, HOST_WIDE_INT_PRINT_DEC, TREE_INT_CST_LOW (index));
1009 obstack_grow (&name_obstack, buffer, strlen (buffer));
1016 gcc_unreachable (); /* we treat these as scalars. */
1023 /* Create a human readable name for replacement variable of ACCESS. */
1026 make_fancy_name (tree expr)
1028 make_fancy_name_1 (expr);
1029 obstack_1grow (&name_obstack, '\0');
1030 return XOBFINISH (&name_obstack, char *);
1033 /* Helper function for build_ref_for_offset. */
1036 build_ref_for_offset_1 (tree *res, tree type, HOST_WIDE_INT offset,
1042 tree tr_size, index;
1043 HOST_WIDE_INT el_size;
1045 if (offset == 0 && exp_type
1046 && types_compatible_p (exp_type, type))
1049 switch (TREE_CODE (type))
1052 case QUAL_UNION_TYPE:
1054 /* Some ADA records are half-unions, treat all of them the same. */
1055 for (fld = TYPE_FIELDS (type); fld; fld = TREE_CHAIN (fld))
1057 HOST_WIDE_INT pos, size;
1058 tree expr, *expr_ptr;
1060 if (TREE_CODE (fld) != FIELD_DECL)
1063 pos = int_bit_position (fld);
1064 gcc_assert (TREE_CODE (type) == RECORD_TYPE || pos == 0);
1065 size = tree_low_cst (DECL_SIZE (fld), 1);
1066 if (pos > offset || (pos + size) <= offset)
1071 expr = build3 (COMPONENT_REF, TREE_TYPE (fld), *res, fld,
1077 if (build_ref_for_offset_1 (expr_ptr, TREE_TYPE (fld),
1078 offset - pos, exp_type))
1088 tr_size = TYPE_SIZE (TREE_TYPE (type));
1089 if (!tr_size || !host_integerp (tr_size, 1))
1091 el_size = tree_low_cst (tr_size, 1);
1095 index = build_int_cst (TYPE_DOMAIN (type), offset / el_size);
1096 if (!integer_zerop (TYPE_MIN_VALUE (TYPE_DOMAIN (type))))
1097 index = int_const_binop (PLUS_EXPR, index,
1098 TYPE_MIN_VALUE (TYPE_DOMAIN (type)),
1100 *res = build4 (ARRAY_REF, TREE_TYPE (type), *res, index,
1101 NULL_TREE, NULL_TREE);
1103 offset = offset % el_size;
1104 type = TREE_TYPE (type);
1119 /* Construct an expression that would reference a part of aggregate *EXPR of
1120 type TYPE at the given OFFSET of the type EXP_TYPE. If EXPR is NULL, the
1121 function only determines whether it can build such a reference without
1124 FIXME: Eventually this should be replaced with
1125 maybe_fold_offset_to_reference() from tree-ssa-ccp.c but that requires a
1126 minor rewrite of fold_stmt.
1130 build_ref_for_offset (tree *expr, tree type, HOST_WIDE_INT offset,
1131 tree exp_type, bool allow_ptr)
1133 location_t loc = expr ? EXPR_LOCATION (*expr) : UNKNOWN_LOCATION;
1135 if (allow_ptr && POINTER_TYPE_P (type))
1137 type = TREE_TYPE (type);
1139 *expr = fold_build1_loc (loc, INDIRECT_REF, type, *expr);
1142 return build_ref_for_offset_1 (expr, type, offset, exp_type);
1145 /* The very first phase of intraprocedural SRA. It marks in candidate_bitmap
1146 those with type which is suitable for scalarization. */
1149 find_var_candidates (void)
1152 referenced_var_iterator rvi;
1155 FOR_EACH_REFERENCED_VAR (var, rvi)
1157 if (TREE_CODE (var) != VAR_DECL && TREE_CODE (var) != PARM_DECL)
1159 type = TREE_TYPE (var);
1161 if (!AGGREGATE_TYPE_P (type)
1162 || needs_to_live_in_memory (var)
1163 || TREE_THIS_VOLATILE (var)
1164 || !COMPLETE_TYPE_P (type)
1165 || !host_integerp (TYPE_SIZE (type), 1)
1166 || tree_low_cst (TYPE_SIZE (type), 1) == 0
1167 || type_internals_preclude_sra_p (type))
1170 bitmap_set_bit (candidate_bitmap, DECL_UID (var));
1172 if (dump_file && (dump_flags & TDF_DETAILS))
1174 fprintf (dump_file, "Candidate (%d): ", DECL_UID (var));
1175 print_generic_expr (dump_file, var, 0);
1176 fprintf (dump_file, "\n");
1184 /* Sort all accesses for the given variable, check for partial overlaps and
1185 return NULL if there are any. If there are none, pick a representative for
1186 each combination of offset and size and create a linked list out of them.
1187 Return the pointer to the first representative and make sure it is the first
1188 one in the vector of accesses. */
1190 static struct access *
1191 sort_and_splice_var_accesses (tree var)
1193 int i, j, access_count;
1194 struct access *res, **prev_acc_ptr = &res;
1195 VEC (access_p, heap) *access_vec;
1197 HOST_WIDE_INT low = -1, high = 0;
1199 access_vec = get_base_access_vector (var);
1202 access_count = VEC_length (access_p, access_vec);
1204 /* Sort by <OFFSET, SIZE>. */
1205 qsort (VEC_address (access_p, access_vec), access_count, sizeof (access_p),
1206 compare_access_positions);
1209 while (i < access_count)
1211 struct access *access = VEC_index (access_p, access_vec, i);
1212 bool grp_write = access->write;
1213 bool grp_read = !access->write;
1214 bool multiple_reads = false;
1215 bool grp_partial_lhs = access->grp_partial_lhs;
1216 bool first_scalar = is_gimple_reg_type (access->type);
1217 bool unscalarizable_region = access->grp_unscalarizable_region;
1219 if (first || access->offset >= high)
1222 low = access->offset;
1223 high = access->offset + access->size;
1225 else if (access->offset > low && access->offset + access->size > high)
1228 gcc_assert (access->offset >= low
1229 && access->offset + access->size <= high);
1232 while (j < access_count)
1234 struct access *ac2 = VEC_index (access_p, access_vec, j);
1235 if (ac2->offset != access->offset || ac2->size != access->size)
1242 multiple_reads = true;
1246 grp_partial_lhs |= ac2->grp_partial_lhs;
1247 unscalarizable_region |= ac2->grp_unscalarizable_region;
1248 relink_to_new_repr (access, ac2);
1250 /* If there are both aggregate-type and scalar-type accesses with
1251 this combination of size and offset, the comparison function
1252 should have put the scalars first. */
1253 gcc_assert (first_scalar || !is_gimple_reg_type (ac2->type));
1254 ac2->group_representative = access;
1260 access->group_representative = access;
1261 access->grp_write = grp_write;
1262 access->grp_read = grp_read;
1263 access->grp_hint = multiple_reads;
1264 access->grp_partial_lhs = grp_partial_lhs;
1265 access->grp_unscalarizable_region = unscalarizable_region;
1266 if (access->first_link)
1267 add_access_to_work_queue (access);
1269 *prev_acc_ptr = access;
1270 prev_acc_ptr = &access->next_grp;
1273 gcc_assert (res == VEC_index (access_p, access_vec, 0));
1277 /* Create a variable for the given ACCESS which determines the type, name and a
1278 few other properties. Return the variable declaration and store it also to
1279 ACCESS->replacement. */
1282 create_access_replacement (struct access *access)
1286 repl = create_tmp_var (access->type, "SR");
1288 add_referenced_var (repl);
1289 mark_sym_for_renaming (repl);
1291 if (!access->grp_partial_lhs
1292 && (TREE_CODE (access->type) == COMPLEX_TYPE
1293 || TREE_CODE (access->type) == VECTOR_TYPE))
1294 DECL_GIMPLE_REG_P (repl) = 1;
1296 DECL_SOURCE_LOCATION (repl) = DECL_SOURCE_LOCATION (access->base);
1297 DECL_ARTIFICIAL (repl) = 1;
1299 if (DECL_NAME (access->base)
1300 && !DECL_IGNORED_P (access->base)
1301 && !DECL_ARTIFICIAL (access->base))
1303 char *pretty_name = make_fancy_name (access->expr);
1305 DECL_NAME (repl) = get_identifier (pretty_name);
1306 obstack_free (&name_obstack, pretty_name);
1308 SET_DECL_DEBUG_EXPR (repl, access->expr);
1309 DECL_DEBUG_EXPR_IS_FROM (repl) = 1;
1310 DECL_IGNORED_P (repl) = 0;
1313 DECL_IGNORED_P (repl) = DECL_IGNORED_P (access->base);
1314 TREE_NO_WARNING (repl) = TREE_NO_WARNING (access->base);
1318 fprintf (dump_file, "Created a replacement for ");
1319 print_generic_expr (dump_file, access->base, 0);
1320 fprintf (dump_file, " offset: %u, size: %u: ",
1321 (unsigned) access->offset, (unsigned) access->size);
1322 print_generic_expr (dump_file, repl, 0);
1323 fprintf (dump_file, "\n");
1325 sra_stats.replacements++;
1330 /* Return ACCESS scalar replacement, create it if it does not exist yet. */
1333 get_access_replacement (struct access *access)
1335 gcc_assert (access->grp_to_be_replaced);
1337 if (!access->replacement_decl)
1338 access->replacement_decl = create_access_replacement (access);
1339 return access->replacement_decl;
1342 /* Build a subtree of accesses rooted in *ACCESS, and move the pointer in the
1343 linked list along the way. Stop when *ACCESS is NULL or the access pointed
1344 to it is not "within" the root. */
1347 build_access_subtree (struct access **access)
1349 struct access *root = *access, *last_child = NULL;
1350 HOST_WIDE_INT limit = root->offset + root->size;
1352 *access = (*access)->next_grp;
1353 while (*access && (*access)->offset + (*access)->size <= limit)
1356 root->first_child = *access;
1358 last_child->next_sibling = *access;
1359 last_child = *access;
1361 build_access_subtree (access);
1365 /* Build a tree of access representatives, ACCESS is the pointer to the first
1366 one, others are linked in a list by the next_grp field. Decide about scalar
1367 replacements on the way, return true iff any are to be created. */
1370 build_access_trees (struct access *access)
1374 struct access *root = access;
1376 build_access_subtree (&access);
1377 root->next_grp = access;
1381 /* Analyze the subtree of accesses rooted in ROOT, scheduling replacements when
1382 both seeming beneficial and when ALLOW_REPLACEMENTS allows it. Also set
1383 all sorts of access flags appropriately along the way, notably always ser
1384 grp_read when MARK_READ is true and grp_write when MARK_WRITE is true. */
1387 analyze_access_subtree (struct access *root, bool allow_replacements,
1388 bool mark_read, bool mark_write)
1390 struct access *child;
1391 HOST_WIDE_INT limit = root->offset + root->size;
1392 HOST_WIDE_INT covered_to = root->offset;
1393 bool scalar = is_gimple_reg_type (root->type);
1394 bool hole = false, sth_created = false;
1395 bool direct_read = root->grp_read;
1398 root->grp_read = true;
1399 else if (root->grp_read)
1403 root->grp_write = true;
1404 else if (root->grp_write)
1407 if (root->grp_unscalarizable_region)
1408 allow_replacements = false;
1410 for (child = root->first_child; child; child = child->next_sibling)
1412 if (!hole && child->offset < covered_to)
1415 covered_to += child->size;
1417 sth_created |= analyze_access_subtree (child, allow_replacements,
1418 mark_read, mark_write);
1420 root->grp_unscalarized_data |= child->grp_unscalarized_data;
1421 hole |= !child->grp_covered;
1424 if (allow_replacements && scalar && !root->first_child
1426 || (direct_read && root->grp_write)))
1428 if (dump_file && (dump_flags & TDF_DETAILS))
1430 fprintf (dump_file, "Marking ");
1431 print_generic_expr (dump_file, root->base, 0);
1432 fprintf (dump_file, " offset: %u, size: %u: ",
1433 (unsigned) root->offset, (unsigned) root->size);
1434 fprintf (dump_file, " to be replaced.\n");
1437 root->grp_to_be_replaced = 1;
1441 else if (covered_to < limit)
1444 if (sth_created && !hole)
1446 root->grp_covered = 1;
1449 if (root->grp_write || TREE_CODE (root->base) == PARM_DECL)
1450 root->grp_unscalarized_data = 1; /* not covered and written to */
1456 /* Analyze all access trees linked by next_grp by the means of
1457 analyze_access_subtree. */
1459 analyze_access_trees (struct access *access)
1465 if (analyze_access_subtree (access, true, false, false))
1467 access = access->next_grp;
1473 /* Return true iff a potential new child of LACC at offset OFFSET and with size
1474 SIZE would conflict with an already existing one. If exactly such a child
1475 already exists in LACC, store a pointer to it in EXACT_MATCH. */
1478 child_would_conflict_in_lacc (struct access *lacc, HOST_WIDE_INT norm_offset,
1479 HOST_WIDE_INT size, struct access **exact_match)
1481 struct access *child;
1483 for (child = lacc->first_child; child; child = child->next_sibling)
1485 if (child->offset == norm_offset && child->size == size)
1487 *exact_match = child;
1491 if (child->offset < norm_offset + size
1492 && child->offset + child->size > norm_offset)
1499 /* Create a new child access of PARENT, with all properties just like MODEL
1500 except for its offset and with its grp_write false and grp_read true.
1501 Return the new access. Note that this access is created long after all
1502 splicing and sorting, it's not located in any access vector and is
1503 automatically a representative of its group. */
1505 static struct access *
1506 create_artificial_child_access (struct access *parent, struct access *model,
1507 HOST_WIDE_INT new_offset)
1509 struct access *access;
1510 struct access **child;
1513 gcc_assert (!model->grp_unscalarizable_region);
1515 access = (struct access *) pool_alloc (access_pool);
1516 memset (access, 0, sizeof (struct access));
1517 access->base = parent->base;
1518 access->offset = new_offset;
1519 access->size = model->size;
1520 access->type = model->type;
1521 access->grp_write = true;
1522 access->grp_read = false;
1523 access->expr = access->base;
1524 ok = build_ref_for_offset (&access->expr, TREE_TYPE (access->expr),
1525 new_offset, access->type, false);
1528 child = &parent->first_child;
1529 while (*child && (*child)->offset < new_offset)
1530 child = &(*child)->next_sibling;
1532 access->next_sibling = *child;
1539 /* Propagate all subaccesses of RACC across an assignment link to LACC. Return
1540 true if any new subaccess was created. Additionally, if RACC is a scalar
1541 access but LACC is not, change the type of the latter. */
1544 propagate_subacesses_accross_link (struct access *lacc, struct access *racc)
1546 struct access *rchild;
1547 HOST_WIDE_INT norm_delta = lacc->offset - racc->offset;
1550 if (is_gimple_reg_type (lacc->type)
1551 || lacc->grp_unscalarizable_region
1552 || racc->grp_unscalarizable_region)
1555 if (!lacc->first_child && !racc->first_child
1556 && is_gimple_reg_type (racc->type))
1560 lacc->expr = lacc->base;
1561 ok = build_ref_for_offset (&lacc->expr, TREE_TYPE (lacc->expr),
1562 lacc->offset, racc->type, false);
1564 lacc->type = racc->type;
1568 for (rchild = racc->first_child; rchild; rchild = rchild->next_sibling)
1570 struct access *new_acc = NULL;
1571 HOST_WIDE_INT norm_offset = rchild->offset + norm_delta;
1573 if (rchild->grp_unscalarizable_region)
1576 if (child_would_conflict_in_lacc (lacc, norm_offset, rchild->size,
1581 rchild->grp_hint = 1;
1582 new_acc->grp_hint |= new_acc->grp_read;
1583 if (rchild->first_child)
1584 ret |= propagate_subacesses_accross_link (new_acc, rchild);
1589 /* If a (part of) a union field is on the RHS of an assignment, it can
1590 have sub-accesses which do not make sense on the LHS (PR 40351).
1591 Check that this is not the case. */
1592 if (!build_ref_for_offset (NULL, TREE_TYPE (lacc->base), norm_offset,
1593 rchild->type, false))
1596 rchild->grp_hint = 1;
1597 new_acc = create_artificial_child_access (lacc, rchild, norm_offset);
1598 if (racc->first_child)
1599 propagate_subacesses_accross_link (new_acc, rchild);
1607 /* Propagate all subaccesses across assignment links. */
1610 propagate_all_subaccesses (void)
1612 while (work_queue_head)
1614 struct access *racc = pop_access_from_work_queue ();
1615 struct assign_link *link;
1617 gcc_assert (racc->first_link);
1619 for (link = racc->first_link; link; link = link->next)
1621 struct access *lacc = link->lacc;
1623 if (!bitmap_bit_p (candidate_bitmap, DECL_UID (lacc->base)))
1625 lacc = lacc->group_representative;
1626 if (propagate_subacesses_accross_link (lacc, racc)
1627 && lacc->first_link)
1628 add_access_to_work_queue (lacc);
1633 /* Go through all accesses collected throughout the (intraprocedural) analysis
1634 stage, exclude overlapping ones, identify representatives and build trees
1635 out of them, making decisions about scalarization on the way. Return true
1636 iff there are any to-be-scalarized variables after this stage. */
1639 analyze_all_variable_accesses (void)
1642 referenced_var_iterator rvi;
1645 FOR_EACH_REFERENCED_VAR (var, rvi)
1646 if (bitmap_bit_p (candidate_bitmap, DECL_UID (var)))
1648 struct access *access;
1650 access = sort_and_splice_var_accesses (var);
1652 build_access_trees (access);
1654 disqualify_candidate (var,
1655 "No or inhibitingly overlapping accesses.");
1658 propagate_all_subaccesses ();
1660 FOR_EACH_REFERENCED_VAR (var, rvi)
1661 if (bitmap_bit_p (candidate_bitmap, DECL_UID (var)))
1663 struct access *access = get_first_repr_for_decl (var);
1665 if (analyze_access_trees (access))
1668 if (dump_file && (dump_flags & TDF_DETAILS))
1670 fprintf (dump_file, "\nAccess trees for ");
1671 print_generic_expr (dump_file, var, 0);
1672 fprintf (dump_file, " (UID: %u): \n", DECL_UID (var));
1673 dump_access_tree (dump_file, access);
1674 fprintf (dump_file, "\n");
1678 disqualify_candidate (var, "No scalar replacements to be created.");
1683 statistics_counter_event (cfun, "Scalarized aggregates", res);
1690 /* Return true iff a reference statement into aggregate AGG can be built for
1691 every single to-be-replaced accesses that is a child of ACCESS, its sibling
1692 or a child of its sibling. TOP_OFFSET is the offset from the processed
1693 access subtree that has to be subtracted from offset of each access. */
1696 ref_expr_for_all_replacements_p (struct access *access, tree agg,
1697 HOST_WIDE_INT top_offset)
1701 if (access->grp_to_be_replaced
1702 && !build_ref_for_offset (NULL, TREE_TYPE (agg),
1703 access->offset - top_offset,
1704 access->type, false))
1707 if (access->first_child
1708 && !ref_expr_for_all_replacements_p (access->first_child, agg,
1712 access = access->next_sibling;
1719 /* Generate statements copying scalar replacements of accesses within a subtree
1720 into or out of AGG. ACCESS is the first child of the root of the subtree to
1721 be processed. AGG is an aggregate type expression (can be a declaration but
1722 does not have to be, it can for example also be an indirect_ref).
1723 TOP_OFFSET is the offset of the processed subtree which has to be subtracted
1724 from offsets of individual accesses to get corresponding offsets for AGG.
1725 If CHUNK_SIZE is non-null, copy only replacements in the interval
1726 <start_offset, start_offset + chunk_size>, otherwise copy all. GSI is a
1727 statement iterator used to place the new statements. WRITE should be true
1728 when the statements should write from AGG to the replacement and false if
1729 vice versa. if INSERT_AFTER is true, new statements will be added after the
1730 current statement in GSI, they will be added before the statement
1734 generate_subtree_copies (struct access *access, tree agg,
1735 HOST_WIDE_INT top_offset,
1736 HOST_WIDE_INT start_offset, HOST_WIDE_INT chunk_size,
1737 gimple_stmt_iterator *gsi, bool write,
1742 tree expr = unshare_expr (agg);
1744 if (chunk_size && access->offset >= start_offset + chunk_size)
1747 if (access->grp_to_be_replaced
1749 || access->offset + access->size > start_offset))
1751 tree repl = get_access_replacement (access);
1755 ref_found = build_ref_for_offset (&expr, TREE_TYPE (agg),
1756 access->offset - top_offset,
1757 access->type, false);
1758 gcc_assert (ref_found);
1762 if (access->grp_partial_lhs)
1763 expr = force_gimple_operand_gsi (gsi, expr, true, NULL_TREE,
1765 insert_after ? GSI_NEW_STMT
1767 stmt = gimple_build_assign (repl, expr);
1771 TREE_NO_WARNING (repl) = 1;
1772 if (access->grp_partial_lhs)
1773 repl = force_gimple_operand_gsi (gsi, repl, true, NULL_TREE,
1775 insert_after ? GSI_NEW_STMT
1777 stmt = gimple_build_assign (expr, repl);
1781 gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
1783 gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
1785 sra_stats.subtree_copies++;
1788 if (access->first_child)
1789 generate_subtree_copies (access->first_child, agg, top_offset,
1790 start_offset, chunk_size, gsi,
1791 write, insert_after);
1793 access = access->next_sibling;
1798 /* Assign zero to all scalar replacements in an access subtree. ACCESS is the
1799 the root of the subtree to be processed. GSI is the statement iterator used
1800 for inserting statements which are added after the current statement if
1801 INSERT_AFTER is true or before it otherwise. */
1804 init_subtree_with_zero (struct access *access, gimple_stmt_iterator *gsi,
1808 struct access *child;
1810 if (access->grp_to_be_replaced)
1814 stmt = gimple_build_assign (get_access_replacement (access),
1815 fold_convert (access->type,
1816 integer_zero_node));
1818 gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
1820 gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
1824 for (child = access->first_child; child; child = child->next_sibling)
1825 init_subtree_with_zero (child, gsi, insert_after);
1828 /* Search for an access representative for the given expression EXPR and
1829 return it or NULL if it cannot be found. */
1831 static struct access *
1832 get_access_for_expr (tree expr)
1834 HOST_WIDE_INT offset, size, max_size;
1837 /* FIXME: This should not be necessary but Ada produces V_C_Es with a type of
1838 a different size than the size of its argument and we need the latter
1840 if (TREE_CODE (expr) == VIEW_CONVERT_EXPR)
1841 expr = TREE_OPERAND (expr, 0);
1843 base = get_ref_base_and_extent (expr, &offset, &size, &max_size);
1844 if (max_size == -1 || !DECL_P (base))
1847 if (!bitmap_bit_p (candidate_bitmap, DECL_UID (base)))
1850 return get_var_base_offset_size_access (base, offset, max_size);
1853 /* Callback for scan_function. Replace the expression EXPR with a scalar
1854 replacement if there is one and generate other statements to do type
1855 conversion or subtree copying if necessary. GSI is used to place newly
1856 created statements, WRITE is true if the expression is being written to (it
1857 is on a LHS of a statement or output in an assembly statement). */
1860 sra_modify_expr (tree *expr, gimple_stmt_iterator *gsi, bool write,
1861 void *data ATTRIBUTE_UNUSED)
1863 struct access *access;
1866 if (TREE_CODE (*expr) == BIT_FIELD_REF)
1869 expr = &TREE_OPERAND (*expr, 0);
1874 if (TREE_CODE (*expr) == REALPART_EXPR || TREE_CODE (*expr) == IMAGPART_EXPR)
1875 expr = &TREE_OPERAND (*expr, 0);
1876 access = get_access_for_expr (*expr);
1879 type = TREE_TYPE (*expr);
1881 if (access->grp_to_be_replaced)
1883 tree repl = get_access_replacement (access);
1884 /* If we replace a non-register typed access simply use the original
1885 access expression to extract the scalar component afterwards.
1886 This happens if scalarizing a function return value or parameter
1887 like in gcc.c-torture/execute/20041124-1.c, 20050316-1.c and
1888 gcc.c-torture/compile/20011217-1.c. */
1889 if (!is_gimple_reg_type (type))
1894 tree ref = unshare_expr (access->expr);
1895 if (access->grp_partial_lhs)
1896 ref = force_gimple_operand_gsi (gsi, ref, true, NULL_TREE,
1897 false, GSI_NEW_STMT);
1898 stmt = gimple_build_assign (repl, ref);
1899 gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
1903 if (access->grp_partial_lhs)
1904 repl = force_gimple_operand_gsi (gsi, repl, true, NULL_TREE,
1905 true, GSI_SAME_STMT);
1906 stmt = gimple_build_assign (unshare_expr (access->expr), repl);
1907 gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
1912 gcc_assert (useless_type_conversion_p (type, access->type));
1918 if (access->first_child)
1920 HOST_WIDE_INT start_offset, chunk_size;
1922 && host_integerp (TREE_OPERAND (bfr, 1), 1)
1923 && host_integerp (TREE_OPERAND (bfr, 2), 1))
1925 chunk_size = tree_low_cst (TREE_OPERAND (bfr, 1), 1);
1926 start_offset = access->offset
1927 + tree_low_cst (TREE_OPERAND (bfr, 2), 1);
1930 start_offset = chunk_size = 0;
1932 generate_subtree_copies (access->first_child, access->base, 0,
1933 start_offset, chunk_size, gsi, write, write);
1938 /* Where scalar replacements of the RHS have been written to when a replacement
1939 of a LHS of an assigments cannot be direclty loaded from a replacement of
1941 enum unscalarized_data_handling { SRA_UDH_NONE, /* Nothing done so far. */
1942 SRA_UDH_RIGHT, /* Data flushed to the RHS. */
1943 SRA_UDH_LEFT }; /* Data flushed to the LHS. */
1945 /* Store all replacements in the access tree rooted in TOP_RACC either to their
1946 base aggregate if there are unscalarized data or directly to LHS
1949 static enum unscalarized_data_handling
1950 handle_unscalarized_data_in_subtree (struct access *top_racc, tree lhs,
1951 gimple_stmt_iterator *gsi)
1953 if (top_racc->grp_unscalarized_data)
1955 generate_subtree_copies (top_racc->first_child, top_racc->base, 0, 0, 0,
1957 return SRA_UDH_RIGHT;
1961 generate_subtree_copies (top_racc->first_child, lhs, top_racc->offset,
1962 0, 0, gsi, false, false);
1963 return SRA_UDH_LEFT;
1968 /* Try to generate statements to load all sub-replacements in an access
1969 (sub)tree (LACC is the first child) from scalar replacements in the TOP_RACC
1970 (sub)tree. If that is not possible, refresh the TOP_RACC base aggregate and
1971 load the accesses from it. LEFT_OFFSET is the offset of the left whole
1972 subtree being copied, RIGHT_OFFSET is the same thing for the right subtree.
1973 GSI is stmt iterator used for statement insertions. *REFRESHED is true iff
1974 the rhs top aggregate has already been refreshed by contents of its scalar
1975 reductions and is set to true if this function has to do it. */
1978 load_assign_lhs_subreplacements (struct access *lacc, struct access *top_racc,
1979 HOST_WIDE_INT left_offset,
1980 HOST_WIDE_INT right_offset,
1981 gimple_stmt_iterator *old_gsi,
1982 gimple_stmt_iterator *new_gsi,
1983 enum unscalarized_data_handling *refreshed,
1986 location_t loc = EXPR_LOCATION (lacc->expr);
1989 if (lacc->grp_to_be_replaced)
1991 struct access *racc;
1992 HOST_WIDE_INT offset = lacc->offset - left_offset + right_offset;
1996 racc = find_access_in_subtree (top_racc, offset, lacc->size);
1997 if (racc && racc->grp_to_be_replaced)
1999 rhs = get_access_replacement (racc);
2000 if (!useless_type_conversion_p (lacc->type, racc->type))
2001 rhs = fold_build1_loc (loc, VIEW_CONVERT_EXPR, lacc->type, rhs);
2007 /* No suitable access on the right hand side, need to load from
2008 the aggregate. See if we have to update it first... */
2009 if (*refreshed == SRA_UDH_NONE)
2010 *refreshed = handle_unscalarized_data_in_subtree (top_racc,
2013 if (*refreshed == SRA_UDH_LEFT)
2014 rhs = unshare_expr (lacc->expr);
2017 rhs = unshare_expr (top_racc->base);
2018 repl_found = build_ref_for_offset (&rhs,
2019 TREE_TYPE (top_racc->base),
2020 offset, lacc->type, false);
2021 gcc_assert (repl_found);
2025 stmt = gimple_build_assign (get_access_replacement (lacc), rhs);
2026 gsi_insert_after (new_gsi, stmt, GSI_NEW_STMT);
2028 sra_stats.subreplacements++;
2030 else if (*refreshed == SRA_UDH_NONE
2031 && lacc->grp_read && !lacc->grp_covered)
2032 *refreshed = handle_unscalarized_data_in_subtree (top_racc, lhs,
2035 if (lacc->first_child)
2036 load_assign_lhs_subreplacements (lacc->first_child, top_racc,
2037 left_offset, right_offset,
2038 old_gsi, new_gsi, refreshed, lhs);
2039 lacc = lacc->next_sibling;
2044 /* Modify assignments with a CONSTRUCTOR on their RHS. STMT contains a pointer
2045 to the assignment and GSI is the statement iterator pointing at it. Returns
2046 the same values as sra_modify_assign. */
2048 static enum scan_assign_result
2049 sra_modify_constructor_assign (gimple *stmt, gimple_stmt_iterator *gsi)
2051 tree lhs = gimple_assign_lhs (*stmt);
2054 acc = get_access_for_expr (lhs);
2058 if (VEC_length (constructor_elt,
2059 CONSTRUCTOR_ELTS (gimple_assign_rhs1 (*stmt))) > 0)
2061 /* I have never seen this code path trigger but if it can happen the
2062 following should handle it gracefully. */
2063 if (access_has_children_p (acc))
2064 generate_subtree_copies (acc->first_child, acc->base, 0, 0, 0, gsi,
2066 return SRA_SA_PROCESSED;
2069 if (acc->grp_covered)
2071 init_subtree_with_zero (acc, gsi, false);
2072 unlink_stmt_vdef (*stmt);
2073 gsi_remove (gsi, true);
2074 return SRA_SA_REMOVED;
2078 init_subtree_with_zero (acc, gsi, true);
2079 return SRA_SA_PROCESSED;
2084 /* Callback of scan_function to process assign statements. It examines both
2085 sides of the statement, replaces them with a scalare replacement if there is
2086 one and generating copying of replacements if scalarized aggregates have been
2087 used in the assignment. STMT is a pointer to the assign statement, GSI is
2088 used to hold generated statements for type conversions and subtree
2091 static enum scan_assign_result
2092 sra_modify_assign (gimple *stmt, gimple_stmt_iterator *gsi,
2093 void *data ATTRIBUTE_UNUSED)
2095 struct access *lacc, *racc;
2097 bool modify_this_stmt = false;
2098 bool force_gimple_rhs = false;
2099 location_t loc = gimple_location (*stmt);
2101 if (!gimple_assign_single_p (*stmt))
2103 lhs = gimple_assign_lhs (*stmt);
2104 rhs = gimple_assign_rhs1 (*stmt);
2106 if (TREE_CODE (rhs) == CONSTRUCTOR)
2107 return sra_modify_constructor_assign (stmt, gsi);
2109 if (TREE_CODE (rhs) == REALPART_EXPR || TREE_CODE (lhs) == REALPART_EXPR
2110 || TREE_CODE (rhs) == IMAGPART_EXPR || TREE_CODE (lhs) == IMAGPART_EXPR
2111 || TREE_CODE (rhs) == BIT_FIELD_REF || TREE_CODE (lhs) == BIT_FIELD_REF)
2113 modify_this_stmt = sra_modify_expr (gimple_assign_rhs1_ptr (*stmt),
2115 modify_this_stmt |= sra_modify_expr (gimple_assign_lhs_ptr (*stmt),
2117 return modify_this_stmt ? SRA_SA_PROCESSED : SRA_SA_NONE;
2120 lacc = get_access_for_expr (lhs);
2121 racc = get_access_for_expr (rhs);
2125 if (lacc && lacc->grp_to_be_replaced)
2127 lhs = get_access_replacement (lacc);
2128 gimple_assign_set_lhs (*stmt, lhs);
2129 modify_this_stmt = true;
2130 if (lacc->grp_partial_lhs)
2131 force_gimple_rhs = true;
2135 if (racc && racc->grp_to_be_replaced)
2137 rhs = get_access_replacement (racc);
2138 modify_this_stmt = true;
2139 if (racc->grp_partial_lhs)
2140 force_gimple_rhs = true;
2144 if (modify_this_stmt)
2146 if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
2148 /* If we can avoid creating a VIEW_CONVERT_EXPR do so.
2149 ??? This should move to fold_stmt which we simply should
2150 call after building a VIEW_CONVERT_EXPR here. */
2151 if (AGGREGATE_TYPE_P (TREE_TYPE (lhs))
2152 && !access_has_children_p (lacc))
2154 tree expr = unshare_expr (lhs);
2155 if (build_ref_for_offset (&expr, TREE_TYPE (lhs), 0,
2156 TREE_TYPE (rhs), false))
2159 gimple_assign_set_lhs (*stmt, expr);
2162 else if (AGGREGATE_TYPE_P (TREE_TYPE (rhs))
2163 && !access_has_children_p (racc))
2165 tree expr = unshare_expr (rhs);
2166 if (build_ref_for_offset (&expr, TREE_TYPE (rhs), 0,
2167 TREE_TYPE (lhs), false))
2170 if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
2172 rhs = fold_build1_loc (loc, VIEW_CONVERT_EXPR, TREE_TYPE (lhs), rhs);
2173 if (!is_gimple_reg (lhs))
2174 force_gimple_rhs = true;
2178 if (force_gimple_rhs)
2179 rhs = force_gimple_operand_gsi (gsi, rhs, true, NULL_TREE,
2180 true, GSI_SAME_STMT);
2181 if (gimple_assign_rhs1 (*stmt) != rhs)
2183 gimple_assign_set_rhs_from_tree (gsi, rhs);
2184 gcc_assert (*stmt == gsi_stmt (*gsi));
2188 /* From this point on, the function deals with assignments in between
2189 aggregates when at least one has scalar reductions of some of its
2190 components. There are three possible scenarios: Both the LHS and RHS have
2191 to-be-scalarized components, 2) only the RHS has or 3) only the LHS has.
2193 In the first case, we would like to load the LHS components from RHS
2194 components whenever possible. If that is not possible, we would like to
2195 read it directly from the RHS (after updating it by storing in it its own
2196 components). If there are some necessary unscalarized data in the LHS,
2197 those will be loaded by the original assignment too. If neither of these
2198 cases happen, the original statement can be removed. Most of this is done
2199 by load_assign_lhs_subreplacements.
2201 In the second case, we would like to store all RHS scalarized components
2202 directly into LHS and if they cover the aggregate completely, remove the
2203 statement too. In the third case, we want the LHS components to be loaded
2204 directly from the RHS (DSE will remove the original statement if it
2207 This is a bit complex but manageable when types match and when unions do
2208 not cause confusion in a way that we cannot really load a component of LHS
2209 from the RHS or vice versa (the access representing this level can have
2210 subaccesses that are accessible only through a different union field at a
2211 higher level - different from the one used in the examined expression).
2214 Therefore, I specially handle a fourth case, happening when there is a
2215 specific type cast or it is impossible to locate a scalarized subaccess on
2216 the other side of the expression. If that happens, I simply "refresh" the
2217 RHS by storing in it is scalarized components leave the original statement
2218 there to do the copying and then load the scalar replacements of the LHS.
2219 This is what the first branch does. */
2221 if (contains_view_convert_expr_p (rhs) || contains_view_convert_expr_p (lhs)
2222 || (access_has_children_p (racc)
2223 && !ref_expr_for_all_replacements_p (racc, lhs, racc->offset))
2224 || (access_has_children_p (lacc)
2225 && !ref_expr_for_all_replacements_p (lacc, rhs, lacc->offset)))
2227 if (access_has_children_p (racc))
2228 generate_subtree_copies (racc->first_child, racc->base, 0, 0, 0,
2230 if (access_has_children_p (lacc))
2231 generate_subtree_copies (lacc->first_child, lacc->base, 0, 0, 0,
2233 sra_stats.separate_lhs_rhs_handling++;
2237 if (access_has_children_p (lacc) && access_has_children_p (racc))
2239 gimple_stmt_iterator orig_gsi = *gsi;
2240 enum unscalarized_data_handling refreshed;
2242 if (lacc->grp_read && !lacc->grp_covered)
2243 refreshed = handle_unscalarized_data_in_subtree (racc, lhs, gsi);
2245 refreshed = SRA_UDH_NONE;
2247 load_assign_lhs_subreplacements (lacc->first_child, racc,
2248 lacc->offset, racc->offset,
2249 &orig_gsi, gsi, &refreshed, lhs);
2250 if (refreshed != SRA_UDH_RIGHT)
2252 if (*stmt == gsi_stmt (*gsi))
2255 unlink_stmt_vdef (*stmt);
2256 gsi_remove (&orig_gsi, true);
2257 sra_stats.deleted++;
2258 return SRA_SA_REMOVED;
2263 if (access_has_children_p (racc))
2265 if (!racc->grp_unscalarized_data)
2267 generate_subtree_copies (racc->first_child, lhs,
2268 racc->offset, 0, 0, gsi,
2270 gcc_assert (*stmt == gsi_stmt (*gsi));
2271 unlink_stmt_vdef (*stmt);
2272 gsi_remove (gsi, true);
2273 sra_stats.deleted++;
2274 return SRA_SA_REMOVED;
2277 generate_subtree_copies (racc->first_child, lhs,
2278 racc->offset, 0, 0, gsi, false, true);
2280 else if (access_has_children_p (lacc))
2281 generate_subtree_copies (lacc->first_child, rhs, lacc->offset,
2282 0, 0, gsi, true, true);
2285 return modify_this_stmt ? SRA_SA_PROCESSED : SRA_SA_NONE;
2288 /* Generate statements initializing scalar replacements of parts of function
2292 initialize_parameter_reductions (void)
2294 gimple_stmt_iterator gsi;
2295 gimple_seq seq = NULL;
2298 for (parm = DECL_ARGUMENTS (current_function_decl);
2300 parm = TREE_CHAIN (parm))
2302 VEC (access_p, heap) *access_vec;
2303 struct access *access;
2305 if (!bitmap_bit_p (candidate_bitmap, DECL_UID (parm)))
2307 access_vec = get_base_access_vector (parm);
2313 seq = gimple_seq_alloc ();
2314 gsi = gsi_start (seq);
2317 for (access = VEC_index (access_p, access_vec, 0);
2319 access = access->next_grp)
2320 generate_subtree_copies (access, parm, 0, 0, 0, &gsi, true, true);
2324 gsi_insert_seq_on_edge_immediate (single_succ_edge (ENTRY_BLOCK_PTR), seq);
2327 /* The "main" function of intraprocedural SRA passes. Runs the analysis and if
2328 it reveals there are components of some aggregates to be scalarized, it runs
2329 the required transformations. */
2331 perform_intra_sra (void)
2336 if (!find_var_candidates ())
2339 if (!scan_function (build_access_from_expr, build_accesses_from_assign, NULL,
2343 if (!analyze_all_variable_accesses ())
2346 scan_function (sra_modify_expr, sra_modify_assign, NULL,
2348 initialize_parameter_reductions ();
2350 statistics_counter_event (cfun, "Scalar replacements created",
2351 sra_stats.replacements);
2352 statistics_counter_event (cfun, "Modified expressions", sra_stats.exprs);
2353 statistics_counter_event (cfun, "Subtree copy stmts",
2354 sra_stats.subtree_copies);
2355 statistics_counter_event (cfun, "Subreplacement stmts",
2356 sra_stats.subreplacements);
2357 statistics_counter_event (cfun, "Deleted stmts", sra_stats.deleted);
2358 statistics_counter_event (cfun, "Separate LHS and RHS handling",
2359 sra_stats.separate_lhs_rhs_handling);
2361 ret = TODO_update_ssa;
2364 sra_deinitialize ();
2368 /* Perform early intraprocedural SRA. */
2370 early_intra_sra (void)
2372 sra_mode = SRA_MODE_EARLY_INTRA;
2373 return perform_intra_sra ();
2376 /* Perform "late" intraprocedural SRA. */
2378 late_intra_sra (void)
2380 sra_mode = SRA_MODE_INTRA;
2381 return perform_intra_sra ();
2386 gate_intra_sra (void)
2388 return flag_tree_sra != 0;
2392 struct gimple_opt_pass pass_sra_early =
2397 gate_intra_sra, /* gate */
2398 early_intra_sra, /* execute */
2401 0, /* static_pass_number */
2402 TV_TREE_SRA, /* tv_id */
2403 PROP_cfg | PROP_ssa, /* properties_required */
2404 0, /* properties_provided */
2405 0, /* properties_destroyed */
2406 0, /* todo_flags_start */
2410 | TODO_verify_ssa /* todo_flags_finish */
2415 struct gimple_opt_pass pass_sra =
2420 gate_intra_sra, /* gate */
2421 late_intra_sra, /* execute */
2424 0, /* static_pass_number */
2425 TV_TREE_SRA, /* tv_id */
2426 PROP_cfg | PROP_ssa, /* properties_required */
2427 0, /* properties_provided */
2428 0, /* properties_destroyed */
2429 TODO_update_address_taken, /* todo_flags_start */
2433 | TODO_verify_ssa /* todo_flags_finish */