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"
82 #include "diagnostic.h"
83 #include "statistics.h"
84 #include "tree-dump.h"
90 /* Enumeration of all aggregate reductions we can do. */
91 enum sra_mode { SRA_MODE_EARLY_INTRA, /* early intraprocedural SRA */
92 SRA_MODE_INTRA }; /* late intraprocedural SRA */
94 /* Global variable describing which aggregate reduction we are performing at
96 static enum sra_mode sra_mode;
100 /* ACCESS represents each access to an aggregate variable (as a whole or a
101 part). It can also represent a group of accesses that refer to exactly the
102 same fragment of an aggregate (i.e. those that have exactly the same offset
103 and size). Such representatives for a single aggregate, once determined,
104 are linked in a linked list and have the group fields set.
106 Moreover, when doing intraprocedural SRA, a tree is built from those
107 representatives (by the means of first_child and next_sibling pointers), in
108 which all items in a subtree are "within" the root, i.e. their offset is
109 greater or equal to offset of the root and offset+size is smaller or equal
110 to offset+size of the root. Children of an access are sorted by offset.
112 Note that accesses to parts of vector and complex number types always
113 represented by an access to the whole complex number or a vector. It is a
114 duty of the modifying functions to replace them appropriately. */
118 /* Values returned by `get_ref_base_and_extent' for each component reference
119 If EXPR isn't a component reference just set `BASE = EXPR', `OFFSET = 0',
120 `SIZE = TREE_SIZE (TREE_TYPE (expr))'. */
121 HOST_WIDE_INT offset;
130 /* Next group representative for this aggregate. */
131 struct access *next_grp;
133 /* Pointer to the group representative. Pointer to itself if the struct is
134 the representative. */
135 struct access *group_representative;
137 /* If this access has any children (in terms of the definition above), this
138 points to the first one. */
139 struct access *first_child;
141 /* Pointer to the next sibling in the access tree as described above. */
142 struct access *next_sibling;
144 /* Pointers to the first and last element in the linked list of assign
146 struct assign_link *first_link, *last_link;
148 /* Pointer to the next access in the work queue. */
149 struct access *next_queued;
151 /* Replacement variable for this access "region." Never to be accessed
152 directly, always only by the means of get_access_replacement() and only
153 when grp_to_be_replaced flag is set. */
154 tree replacement_decl;
156 /* Is this particular access write access? */
159 /* Is this access currently in the work queue? */
160 unsigned grp_queued : 1;
161 /* Does this group contain a write access? This flag is propagated down the
163 unsigned grp_write : 1;
164 /* Does this group contain a read access? This flag is propagated down the
166 unsigned grp_read : 1;
167 /* Is the subtree rooted in this access fully covered by scalar
169 unsigned grp_covered : 1;
170 /* If set to true, this access and all below it in an access tree must not be
172 unsigned grp_unscalarizable_region : 1;
173 /* Whether data have been written to parts of the aggregate covered by this
174 access which is not to be scalarized. This flag is propagated up in the
176 unsigned grp_unscalarized_data : 1;
177 /* Does this access and/or group contain a write access through a
179 unsigned grp_partial_lhs : 1;
181 /* Set when a scalar replacement should be created for this variable. We do
182 the decision and creation at different places because create_tmp_var
183 cannot be called from within FOR_EACH_REFERENCED_VAR. */
184 unsigned grp_to_be_replaced : 1;
187 typedef struct access *access_p;
189 DEF_VEC_P (access_p);
190 DEF_VEC_ALLOC_P (access_p, heap);
192 /* Alloc pool for allocating access structures. */
193 static alloc_pool access_pool;
195 /* A structure linking lhs and rhs accesses from an aggregate assignment. They
196 are used to propagate subaccesses from rhs to lhs as long as they don't
197 conflict with what is already there. */
200 struct access *lacc, *racc;
201 struct assign_link *next;
204 /* Alloc pool for allocating assign link structures. */
205 static alloc_pool link_pool;
207 /* Base (tree) -> Vector (VEC(access_p,heap) *) map. */
208 static struct pointer_map_t *base_access_vec;
210 /* Bitmap of bases (candidates). */
211 static bitmap candidate_bitmap;
212 /* Obstack for creation of fancy names. */
213 static struct obstack name_obstack;
215 /* Head of a linked list of accesses that need to have its subaccesses
216 propagated to their assignment counterparts. */
217 static struct access *work_queue_head;
219 /* Dump contents of ACCESS to file F in a human friendly way. If GRP is true,
220 representative fields are dumped, otherwise those which only describe the
221 individual access are. */
225 /* Number of created scalar replacements. */
228 /* Number of times sra_modify_expr or sra_modify_assign themselves changed an
232 /* Number of statements created by generate_subtree_copies. */
235 /* Number of statements created by load_assign_lhs_subreplacements. */
238 /* Number of times sra_modify_assign has deleted a statement. */
241 /* Number of times sra_modify_assign has to deal with subaccesses of LHS and
242 RHS reparately due to type conversions or nonexistent matching
244 int separate_lhs_rhs_handling;
246 /* Number of processed aggregates is readily available in
247 analyze_all_variable_accesses and so is not stored here. */
251 dump_access (FILE *f, struct access *access, bool grp)
253 fprintf (f, "access { ");
254 fprintf (f, "base = (%d)'", DECL_UID (access->base));
255 print_generic_expr (f, access->base, 0);
256 fprintf (f, "', offset = " HOST_WIDE_INT_PRINT_DEC, access->offset);
257 fprintf (f, ", size = " HOST_WIDE_INT_PRINT_DEC, access->size);
258 fprintf (f, ", expr = ");
259 print_generic_expr (f, access->expr, 0);
260 fprintf (f, ", type = ");
261 print_generic_expr (f, access->type, 0);
263 fprintf (f, ", grp_write = %d, grp_read = %d, grp_covered = %d, "
264 "grp_unscalarizable_region = %d, grp_unscalarized_data = %d, "
265 "grp_partial_lhs = %d, grp_to_be_replaced = %d\n",
266 access->grp_write, access->grp_read, access->grp_covered,
267 access->grp_unscalarizable_region, access->grp_unscalarized_data,
268 access->grp_partial_lhs, access->grp_to_be_replaced);
270 fprintf (f, ", write = %d, grp_partial_lhs = %d\n", access->write,
271 access->grp_partial_lhs);
274 /* Dump a subtree rooted in ACCESS to file F, indent by LEVEL. */
277 dump_access_tree_1 (FILE *f, struct access *access, int level)
283 for (i = 0; i < level; i++)
284 fputs ("* ", dump_file);
286 dump_access (f, access, true);
288 if (access->first_child)
289 dump_access_tree_1 (f, access->first_child, level + 1);
291 access = access->next_sibling;
296 /* Dump all access trees for a variable, given the pointer to the first root in
300 dump_access_tree (FILE *f, struct access *access)
302 for (; access; access = access->next_grp)
303 dump_access_tree_1 (f, access, 0);
306 /* Return true iff ACC is non-NULL and has subaccesses. */
309 access_has_children_p (struct access *acc)
311 return acc && acc->first_child;
314 /* Return a vector of pointers to accesses for the variable given in BASE or
315 NULL if there is none. */
317 static VEC (access_p, heap) *
318 get_base_access_vector (tree base)
322 slot = pointer_map_contains (base_access_vec, base);
326 return *(VEC (access_p, heap) **) slot;
329 /* Find an access with required OFFSET and SIZE in a subtree of accesses rooted
330 in ACCESS. Return NULL if it cannot be found. */
332 static struct access *
333 find_access_in_subtree (struct access *access, HOST_WIDE_INT offset,
336 while (access && (access->offset != offset || access->size != size))
338 struct access *child = access->first_child;
340 while (child && (child->offset + child->size <= offset))
341 child = child->next_sibling;
348 /* Return the first group representative for DECL or NULL if none exists. */
350 static struct access *
351 get_first_repr_for_decl (tree base)
353 VEC (access_p, heap) *access_vec;
355 access_vec = get_base_access_vector (base);
359 return VEC_index (access_p, access_vec, 0);
362 /* Find an access representative for the variable BASE and given OFFSET and
363 SIZE. Requires that access trees have already been built. Return NULL if
364 it cannot be found. */
366 static struct access *
367 get_var_base_offset_size_access (tree base, HOST_WIDE_INT offset,
370 struct access *access;
372 access = get_first_repr_for_decl (base);
373 while (access && (access->offset + access->size <= offset))
374 access = access->next_grp;
378 return find_access_in_subtree (access, offset, size);
381 /* Add LINK to the linked list of assign links of RACC. */
383 add_link_to_rhs (struct access *racc, struct assign_link *link)
385 gcc_assert (link->racc == racc);
387 if (!racc->first_link)
389 gcc_assert (!racc->last_link);
390 racc->first_link = link;
393 racc->last_link->next = link;
395 racc->last_link = link;
399 /* Move all link structures in their linked list in OLD_RACC to the linked list
402 relink_to_new_repr (struct access *new_racc, struct access *old_racc)
404 if (!old_racc->first_link)
406 gcc_assert (!old_racc->last_link);
410 if (new_racc->first_link)
412 gcc_assert (!new_racc->last_link->next);
413 gcc_assert (!old_racc->last_link || !old_racc->last_link->next);
415 new_racc->last_link->next = old_racc->first_link;
416 new_racc->last_link = old_racc->last_link;
420 gcc_assert (!new_racc->last_link);
422 new_racc->first_link = old_racc->first_link;
423 new_racc->last_link = old_racc->last_link;
425 old_racc->first_link = old_racc->last_link = NULL;
428 /* Add ACCESS to the work queue (which is actually a stack). */
431 add_access_to_work_queue (struct access *access)
433 if (!access->grp_queued)
435 gcc_assert (!access->next_queued);
436 access->next_queued = work_queue_head;
437 access->grp_queued = 1;
438 work_queue_head = access;
442 /* Pop an access from the work queue, and return it, assuming there is one. */
444 static struct access *
445 pop_access_from_work_queue (void)
447 struct access *access = work_queue_head;
449 work_queue_head = access->next_queued;
450 access->next_queued = NULL;
451 access->grp_queued = 0;
456 /* Allocate necessary structures. */
459 sra_initialize (void)
461 candidate_bitmap = BITMAP_ALLOC (NULL);
462 gcc_obstack_init (&name_obstack);
463 access_pool = create_alloc_pool ("SRA accesses", sizeof (struct access), 16);
464 link_pool = create_alloc_pool ("SRA links", sizeof (struct assign_link), 16);
465 base_access_vec = pointer_map_create ();
466 memset (&sra_stats, 0, sizeof (sra_stats));
469 /* Hook fed to pointer_map_traverse, deallocate stored vectors. */
472 delete_base_accesses (const void *key ATTRIBUTE_UNUSED, void **value,
473 void *data ATTRIBUTE_UNUSED)
475 VEC (access_p, heap) *access_vec;
476 access_vec = (VEC (access_p, heap) *) *value;
477 VEC_free (access_p, heap, access_vec);
482 /* Deallocate all general structures. */
485 sra_deinitialize (void)
487 BITMAP_FREE (candidate_bitmap);
488 free_alloc_pool (access_pool);
489 free_alloc_pool (link_pool);
490 obstack_free (&name_obstack, NULL);
492 pointer_map_traverse (base_access_vec, delete_base_accesses, NULL);
493 pointer_map_destroy (base_access_vec);
496 /* Remove DECL from candidates for SRA and write REASON to the dump file if
499 disqualify_candidate (tree decl, const char *reason)
501 bitmap_clear_bit (candidate_bitmap, DECL_UID (decl));
503 if (dump_file && (dump_flags & TDF_DETAILS))
505 fprintf (dump_file, "! Disqualifying ");
506 print_generic_expr (dump_file, decl, 0);
507 fprintf (dump_file, " - %s\n", reason);
511 /* Return true iff the type contains a field or an element which does not allow
515 type_internals_preclude_sra_p (tree type)
520 switch (TREE_CODE (type))
524 case QUAL_UNION_TYPE:
525 for (fld = TYPE_FIELDS (type); fld; fld = TREE_CHAIN (fld))
526 if (TREE_CODE (fld) == FIELD_DECL)
528 tree ft = TREE_TYPE (fld);
530 if (TREE_THIS_VOLATILE (fld)
531 || !DECL_FIELD_OFFSET (fld) || !DECL_SIZE (fld)
532 || !host_integerp (DECL_FIELD_OFFSET (fld), 1)
533 || !host_integerp (DECL_SIZE (fld), 1))
536 if (AGGREGATE_TYPE_P (ft)
537 && type_internals_preclude_sra_p (ft))
544 et = TREE_TYPE (type);
546 if (AGGREGATE_TYPE_P (et))
547 return type_internals_preclude_sra_p (et);
556 /* Create and insert access for EXPR. Return created access, or NULL if it is
559 static struct access *
560 create_access (tree expr, bool write)
562 struct access *access;
564 VEC (access_p,heap) *vec;
565 HOST_WIDE_INT offset, size, max_size;
567 bool unscalarizable_region = false;
569 base = get_ref_base_and_extent (expr, &offset, &size, &max_size);
571 if (!DECL_P (base) || !bitmap_bit_p (candidate_bitmap, DECL_UID (base)))
574 if (size != max_size)
577 unscalarizable_region = true;
582 disqualify_candidate (base, "Encountered an unconstrained access.");
586 access = (struct access *) pool_alloc (access_pool);
587 memset (access, 0, sizeof (struct access));
590 access->offset = offset;
593 access->type = TREE_TYPE (expr);
594 access->write = write;
595 access->grp_unscalarizable_region = unscalarizable_region;
597 slot = pointer_map_contains (base_access_vec, base);
599 vec = (VEC (access_p, heap) *) *slot;
601 vec = VEC_alloc (access_p, heap, 32);
603 VEC_safe_push (access_p, heap, vec, access);
605 *((struct VEC (access_p,heap) **)
606 pointer_map_insert (base_access_vec, base)) = vec;
612 /* Search the given tree for a declaration by skipping handled components and
613 exclude it from the candidates. */
616 disqualify_base_of_expr (tree t, const char *reason)
618 while (handled_component_p (t))
619 t = TREE_OPERAND (t, 0);
622 disqualify_candidate (t, reason);
625 /* Scan expression EXPR and create access structures for all accesses to
626 candidates for scalarization. Return the created access or NULL if none is
629 static struct access *
630 build_access_from_expr_1 (tree *expr_ptr, bool write)
632 struct access *ret = NULL;
633 tree expr = *expr_ptr;
636 if (TREE_CODE (expr) == BIT_FIELD_REF
637 || TREE_CODE (expr) == IMAGPART_EXPR
638 || TREE_CODE (expr) == REALPART_EXPR)
640 expr = TREE_OPERAND (expr, 0);
646 /* We need to dive through V_C_Es in order to get the size of its parameter
647 and not the result type. Ada produces such statements. We are also
648 capable of handling the topmost V_C_E but not any of those buried in other
649 handled components. */
650 if (TREE_CODE (expr) == VIEW_CONVERT_EXPR)
651 expr = TREE_OPERAND (expr, 0);
653 if (contains_view_convert_expr_p (expr))
655 disqualify_base_of_expr (expr, "V_C_E under a different handled "
660 switch (TREE_CODE (expr))
667 case ARRAY_RANGE_REF:
668 ret = create_access (expr, write);
675 if (write && partial_ref && ret)
676 ret->grp_partial_lhs = 1;
681 /* Callback of scan_function. Scan expression EXPR and create access
682 structures for all accesses to candidates for scalarization. Return true if
683 any access has been inserted. */
686 build_access_from_expr (tree *expr_ptr,
687 gimple_stmt_iterator *gsi ATTRIBUTE_UNUSED, bool write,
688 void *data ATTRIBUTE_UNUSED)
690 return build_access_from_expr_1 (expr_ptr, write) != NULL;
693 /* Disqualify LHS and RHS for scalarization if STMT must end its basic block in
694 modes in which it matters, return true iff they have been disqualified. RHS
695 may be NULL, in that case ignore it. If we scalarize an aggregate in
696 intra-SRA we may need to add statements after each statement. This is not
697 possible if a statement unconditionally has to end the basic block. */
699 disqualify_ops_if_throwing_stmt (gimple stmt, tree lhs, tree rhs)
701 if (stmt_can_throw_internal (stmt) || stmt_ends_bb_p (stmt))
703 disqualify_base_of_expr (lhs, "LHS of a throwing stmt.");
705 disqualify_base_of_expr (rhs, "RHS of a throwing stmt.");
712 /* Result code for scan_assign callback for scan_function. */
713 enum scan_assign_result { SRA_SA_NONE, /* nothing done for the stmt */
714 SRA_SA_PROCESSED, /* stmt analyzed/changed */
715 SRA_SA_REMOVED }; /* stmt redundant and eliminated */
718 /* Callback of scan_function. Scan expressions occuring in the statement
719 pointed to by STMT_EXPR, create access structures for all accesses to
720 candidates for scalarization and remove those candidates which occur in
721 statements or expressions that prevent them from being split apart. Return
722 true if any access has been inserted. */
724 static enum scan_assign_result
725 build_accesses_from_assign (gimple *stmt_ptr,
726 gimple_stmt_iterator *gsi ATTRIBUTE_UNUSED,
727 void *data ATTRIBUTE_UNUSED)
729 gimple stmt = *stmt_ptr;
730 tree *lhs_ptr, *rhs_ptr;
731 struct access *lacc, *racc;
733 if (!gimple_assign_single_p (stmt))
736 lhs_ptr = gimple_assign_lhs_ptr (stmt);
737 rhs_ptr = gimple_assign_rhs1_ptr (stmt);
739 if (disqualify_ops_if_throwing_stmt (stmt, *lhs_ptr, *rhs_ptr))
742 racc = build_access_from_expr_1 (rhs_ptr, false);
743 lacc = build_access_from_expr_1 (lhs_ptr, true);
746 && !lacc->grp_unscalarizable_region
747 && !racc->grp_unscalarizable_region
748 && AGGREGATE_TYPE_P (TREE_TYPE (*lhs_ptr))
749 /* FIXME: Turn the following line into an assert after PR 40058 is
751 && lacc->size == racc->size
752 && useless_type_conversion_p (lacc->type, racc->type))
754 struct assign_link *link;
756 link = (struct assign_link *) pool_alloc (link_pool);
757 memset (link, 0, sizeof (struct assign_link));
762 add_link_to_rhs (racc, link);
765 return (lacc || racc) ? SRA_SA_PROCESSED : SRA_SA_NONE;
768 /* Callback of walk_stmt_load_store_addr_ops visit_addr used to determine
769 GIMPLE_ASM operands with memory constrains which cannot be scalarized. */
772 asm_visit_addr (gimple stmt ATTRIBUTE_UNUSED, tree op,
773 void *data ATTRIBUTE_UNUSED)
776 disqualify_candidate (op, "Non-scalarizable GIMPLE_ASM operand.");
782 /* Scan function and look for interesting statements. Return true if any has
783 been found or processed, as indicated by callbacks. SCAN_EXPR is a callback
784 called on all expressions within statements except assign statements and
785 those deemed entirely unsuitable for some reason (all operands in such
786 statements and expression are removed from candidate_bitmap). SCAN_ASSIGN
787 is a callback called on all assign statements, HANDLE_SSA_DEFS is a callback
788 called on assign statements and those call statements which have a lhs and
789 it is the only callback which can be NULL. ANALYSIS_STAGE is true when
790 running in the analysis stage of a pass and thus no statement is being
791 modified. DATA is a pointer passed to all callbacks. If any single
792 callback returns true, this function also returns true, otherwise it returns
796 scan_function (bool (*scan_expr) (tree *, gimple_stmt_iterator *, bool, void *),
797 enum scan_assign_result (*scan_assign) (gimple *,
798 gimple_stmt_iterator *,
800 bool (*handle_ssa_defs)(gimple, void *),
801 bool analysis_stage, void *data)
803 gimple_stmt_iterator gsi;
811 bool bb_changed = false;
813 gsi = gsi_start_bb (bb);
814 while (!gsi_end_p (gsi))
816 gimple stmt = gsi_stmt (gsi);
817 enum scan_assign_result assign_result;
818 bool any = false, deleted = false;
820 switch (gimple_code (stmt))
823 t = gimple_return_retval_ptr (stmt);
825 any |= scan_expr (t, &gsi, false, data);
829 assign_result = scan_assign (&stmt, &gsi, data);
830 any |= assign_result == SRA_SA_PROCESSED;
831 deleted = assign_result == SRA_SA_REMOVED;
832 if (handle_ssa_defs && assign_result != SRA_SA_REMOVED)
833 any |= handle_ssa_defs (stmt, data);
837 /* Operands must be processed before the lhs. */
838 for (i = 0; i < gimple_call_num_args (stmt); i++)
840 tree *argp = gimple_call_arg_ptr (stmt, i);
841 any |= scan_expr (argp, &gsi, false, data);
844 if (gimple_call_lhs (stmt))
846 tree *lhs_ptr = gimple_call_lhs_ptr (stmt);
848 || !disqualify_ops_if_throwing_stmt (stmt,
851 any |= scan_expr (lhs_ptr, &gsi, true, data);
853 any |= handle_ssa_defs (stmt, data);
861 walk_stmt_load_store_addr_ops (stmt, NULL, NULL, NULL,
863 for (i = 0; i < gimple_asm_ninputs (stmt); i++)
865 tree *op = &TREE_VALUE (gimple_asm_input_op (stmt, i));
866 any |= scan_expr (op, &gsi, false, data);
868 for (i = 0; i < gimple_asm_noutputs (stmt); i++)
870 tree *op = &TREE_VALUE (gimple_asm_output_op (stmt, i));
871 any |= scan_expr (op, &gsi, true, data);
886 if (!stmt_could_throw_p (stmt))
887 remove_stmt_from_eh_region (stmt);
898 if (!analysis_stage && bb_changed)
899 gimple_purge_dead_eh_edges (bb);
905 /* Helper of QSORT function. There are pointers to accesses in the array. An
906 access is considered smaller than another if it has smaller offset or if the
907 offsets are the same but is size is bigger. */
910 compare_access_positions (const void *a, const void *b)
912 const access_p *fp1 = (const access_p *) a;
913 const access_p *fp2 = (const access_p *) b;
914 const access_p f1 = *fp1;
915 const access_p f2 = *fp2;
917 if (f1->offset != f2->offset)
918 return f1->offset < f2->offset ? -1 : 1;
920 if (f1->size == f2->size)
922 /* Put any non-aggregate type before any aggregate type. */
923 if (!is_gimple_reg_type (f1->type)
924 && is_gimple_reg_type (f2->type))
926 else if (is_gimple_reg_type (f1->type)
927 && !is_gimple_reg_type (f2->type))
929 /* Put the integral type with the bigger precision first. */
930 else if (INTEGRAL_TYPE_P (f1->type)
931 && INTEGRAL_TYPE_P (f2->type))
932 return TYPE_PRECISION (f1->type) > TYPE_PRECISION (f2->type) ? -1 : 1;
933 /* Put any integral type with non-full precision last. */
934 else if (INTEGRAL_TYPE_P (f1->type)
935 && (TREE_INT_CST_LOW (TYPE_SIZE (f1->type))
936 != TYPE_PRECISION (f1->type)))
938 else if (INTEGRAL_TYPE_P (f2->type)
939 && (TREE_INT_CST_LOW (TYPE_SIZE (f2->type))
940 != TYPE_PRECISION (f2->type)))
942 /* Stabilize the sort. */
943 return TYPE_UID (f1->type) - TYPE_UID (f2->type);
946 /* We want the bigger accesses first, thus the opposite operator in the next
948 return f1->size > f2->size ? -1 : 1;
952 /* Append a name of the declaration to the name obstack. A helper function for
956 make_fancy_decl_name (tree decl)
960 tree name = DECL_NAME (decl);
962 obstack_grow (&name_obstack, IDENTIFIER_POINTER (name),
963 IDENTIFIER_LENGTH (name));
966 sprintf (buffer, "D%u", DECL_UID (decl));
967 obstack_grow (&name_obstack, buffer, strlen (buffer));
971 /* Helper for make_fancy_name. */
974 make_fancy_name_1 (tree expr)
981 make_fancy_decl_name (expr);
985 switch (TREE_CODE (expr))
988 make_fancy_name_1 (TREE_OPERAND (expr, 0));
989 obstack_1grow (&name_obstack, '$');
990 make_fancy_decl_name (TREE_OPERAND (expr, 1));
994 make_fancy_name_1 (TREE_OPERAND (expr, 0));
995 obstack_1grow (&name_obstack, '$');
996 /* Arrays with only one element may not have a constant as their
998 index = TREE_OPERAND (expr, 1);
999 if (TREE_CODE (index) != INTEGER_CST)
1001 sprintf (buffer, HOST_WIDE_INT_PRINT_DEC, TREE_INT_CST_LOW (index));
1002 obstack_grow (&name_obstack, buffer, strlen (buffer));
1009 gcc_unreachable (); /* we treat these as scalars. */
1016 /* Create a human readable name for replacement variable of ACCESS. */
1019 make_fancy_name (tree expr)
1021 make_fancy_name_1 (expr);
1022 obstack_1grow (&name_obstack, '\0');
1023 return XOBFINISH (&name_obstack, char *);
1026 /* Helper function for build_ref_for_offset. */
1029 build_ref_for_offset_1 (tree *res, tree type, HOST_WIDE_INT offset,
1035 tree tr_size, index;
1036 HOST_WIDE_INT el_size;
1038 if (offset == 0 && exp_type
1039 && types_compatible_p (exp_type, type))
1042 switch (TREE_CODE (type))
1045 case QUAL_UNION_TYPE:
1047 /* Some ADA records are half-unions, treat all of them the same. */
1048 for (fld = TYPE_FIELDS (type); fld; fld = TREE_CHAIN (fld))
1050 HOST_WIDE_INT pos, size;
1051 tree expr, *expr_ptr;
1053 if (TREE_CODE (fld) != FIELD_DECL)
1056 pos = int_bit_position (fld);
1057 gcc_assert (TREE_CODE (type) == RECORD_TYPE || pos == 0);
1058 size = tree_low_cst (DECL_SIZE (fld), 1);
1059 if (pos > offset || (pos + size) <= offset)
1064 expr = build3 (COMPONENT_REF, TREE_TYPE (fld), *res, fld,
1070 if (build_ref_for_offset_1 (expr_ptr, TREE_TYPE (fld),
1071 offset - pos, exp_type))
1081 tr_size = TYPE_SIZE (TREE_TYPE (type));
1082 if (!tr_size || !host_integerp (tr_size, 1))
1084 el_size = tree_low_cst (tr_size, 1);
1088 index = build_int_cst (TYPE_DOMAIN (type), offset / el_size);
1089 if (!integer_zerop (TYPE_MIN_VALUE (TYPE_DOMAIN (type))))
1090 index = int_const_binop (PLUS_EXPR, index,
1091 TYPE_MIN_VALUE (TYPE_DOMAIN (type)),
1093 *res = build4 (ARRAY_REF, TREE_TYPE (type), *res, index,
1094 NULL_TREE, NULL_TREE);
1096 offset = offset % el_size;
1097 type = TREE_TYPE (type);
1112 /* Construct an expression that would reference a part of aggregate *EXPR of
1113 type TYPE at the given OFFSET of the type EXP_TYPE. If EXPR is NULL, the
1114 function only determines whether it can build such a reference without
1117 FIXME: Eventually this should be replaced with
1118 maybe_fold_offset_to_reference() from tree-ssa-ccp.c but that requires a
1119 minor rewrite of fold_stmt.
1123 build_ref_for_offset (tree *expr, tree type, HOST_WIDE_INT offset,
1124 tree exp_type, bool allow_ptr)
1126 location_t loc = expr ? EXPR_LOCATION (*expr) : UNKNOWN_LOCATION;
1128 if (allow_ptr && POINTER_TYPE_P (type))
1130 type = TREE_TYPE (type);
1132 *expr = fold_build1_loc (loc, INDIRECT_REF, type, *expr);
1135 return build_ref_for_offset_1 (expr, type, offset, exp_type);
1138 /* The very first phase of intraprocedural SRA. It marks in candidate_bitmap
1139 those with type which is suitable for scalarization. */
1142 find_var_candidates (void)
1145 referenced_var_iterator rvi;
1148 FOR_EACH_REFERENCED_VAR (var, rvi)
1150 if (TREE_CODE (var) != VAR_DECL && TREE_CODE (var) != PARM_DECL)
1152 type = TREE_TYPE (var);
1154 if (!AGGREGATE_TYPE_P (type)
1155 || needs_to_live_in_memory (var)
1156 || TREE_THIS_VOLATILE (var)
1157 || !COMPLETE_TYPE_P (type)
1158 || !host_integerp (TYPE_SIZE (type), 1)
1159 || tree_low_cst (TYPE_SIZE (type), 1) == 0
1160 || type_internals_preclude_sra_p (type))
1163 bitmap_set_bit (candidate_bitmap, DECL_UID (var));
1165 if (dump_file && (dump_flags & TDF_DETAILS))
1167 fprintf (dump_file, "Candidate (%d): ", DECL_UID (var));
1168 print_generic_expr (dump_file, var, 0);
1169 fprintf (dump_file, "\n");
1177 /* Sort all accesses for the given variable, check for partial overlaps and
1178 return NULL if there are any. If there are none, pick a representative for
1179 each combination of offset and size and create a linked list out of them.
1180 Return the pointer to the first representative and make sure it is the first
1181 one in the vector of accesses. */
1183 static struct access *
1184 sort_and_splice_var_accesses (tree var)
1186 int i, j, access_count;
1187 struct access *res, **prev_acc_ptr = &res;
1188 VEC (access_p, heap) *access_vec;
1190 HOST_WIDE_INT low = -1, high = 0;
1192 access_vec = get_base_access_vector (var);
1195 access_count = VEC_length (access_p, access_vec);
1197 /* Sort by <OFFSET, SIZE>. */
1198 qsort (VEC_address (access_p, access_vec), access_count, sizeof (access_p),
1199 compare_access_positions);
1202 while (i < access_count)
1204 struct access *access = VEC_index (access_p, access_vec, i);
1205 bool modification = access->write;
1206 bool grp_read = !access->write;
1207 bool grp_partial_lhs = access->grp_partial_lhs;
1208 bool first_scalar = is_gimple_reg_type (access->type);
1209 bool unscalarizable_region = access->grp_unscalarizable_region;
1211 if (first || access->offset >= high)
1214 low = access->offset;
1215 high = access->offset + access->size;
1217 else if (access->offset > low && access->offset + access->size > high)
1220 gcc_assert (access->offset >= low
1221 && access->offset + access->size <= high);
1224 while (j < access_count)
1226 struct access *ac2 = VEC_index (access_p, access_vec, j);
1227 if (ac2->offset != access->offset || ac2->size != access->size)
1229 modification |= ac2->write;
1230 grp_read |= !ac2->write;
1231 grp_partial_lhs |= ac2->grp_partial_lhs;
1232 unscalarizable_region |= ac2->grp_unscalarizable_region;
1233 relink_to_new_repr (access, ac2);
1235 /* If there are both aggregate-type and scalar-type accesses with
1236 this combination of size and offset, the comparison function
1237 should have put the scalars first. */
1238 gcc_assert (first_scalar || !is_gimple_reg_type (ac2->type));
1239 ac2->group_representative = access;
1245 access->group_representative = access;
1246 access->grp_write = modification;
1247 access->grp_read = grp_read;
1248 access->grp_partial_lhs = grp_partial_lhs;
1249 access->grp_unscalarizable_region = unscalarizable_region;
1250 if (access->first_link)
1251 add_access_to_work_queue (access);
1253 *prev_acc_ptr = access;
1254 prev_acc_ptr = &access->next_grp;
1257 gcc_assert (res == VEC_index (access_p, access_vec, 0));
1261 /* Create a variable for the given ACCESS which determines the type, name and a
1262 few other properties. Return the variable declaration and store it also to
1263 ACCESS->replacement. */
1266 create_access_replacement (struct access *access)
1270 repl = create_tmp_var (access->type, "SR");
1272 add_referenced_var (repl);
1273 mark_sym_for_renaming (repl);
1275 if (!access->grp_partial_lhs
1276 && (TREE_CODE (access->type) == COMPLEX_TYPE
1277 || TREE_CODE (access->type) == VECTOR_TYPE))
1278 DECL_GIMPLE_REG_P (repl) = 1;
1280 DECL_SOURCE_LOCATION (repl) = DECL_SOURCE_LOCATION (access->base);
1281 DECL_ARTIFICIAL (repl) = 1;
1283 if (DECL_NAME (access->base)
1284 && !DECL_IGNORED_P (access->base)
1285 && !DECL_ARTIFICIAL (access->base))
1287 char *pretty_name = make_fancy_name (access->expr);
1289 DECL_NAME (repl) = get_identifier (pretty_name);
1290 obstack_free (&name_obstack, pretty_name);
1292 SET_DECL_DEBUG_EXPR (repl, access->expr);
1293 DECL_DEBUG_EXPR_IS_FROM (repl) = 1;
1294 DECL_IGNORED_P (repl) = 0;
1297 DECL_IGNORED_P (repl) = DECL_IGNORED_P (access->base);
1298 TREE_NO_WARNING (repl) = TREE_NO_WARNING (access->base);
1302 fprintf (dump_file, "Created a replacement for ");
1303 print_generic_expr (dump_file, access->base, 0);
1304 fprintf (dump_file, " offset: %u, size: %u: ",
1305 (unsigned) access->offset, (unsigned) access->size);
1306 print_generic_expr (dump_file, repl, 0);
1307 fprintf (dump_file, "\n");
1309 sra_stats.replacements++;
1314 /* Return ACCESS scalar replacement, create it if it does not exist yet. */
1317 get_access_replacement (struct access *access)
1319 gcc_assert (access->grp_to_be_replaced);
1321 if (!access->replacement_decl)
1322 access->replacement_decl = create_access_replacement (access);
1323 return access->replacement_decl;
1326 /* Build a subtree of accesses rooted in *ACCESS, and move the pointer in the
1327 linked list along the way. Stop when *ACCESS is NULL or the access pointed
1328 to it is not "within" the root. */
1331 build_access_subtree (struct access **access)
1333 struct access *root = *access, *last_child = NULL;
1334 HOST_WIDE_INT limit = root->offset + root->size;
1336 *access = (*access)->next_grp;
1337 while (*access && (*access)->offset + (*access)->size <= limit)
1340 root->first_child = *access;
1342 last_child->next_sibling = *access;
1343 last_child = *access;
1345 build_access_subtree (access);
1349 /* Build a tree of access representatives, ACCESS is the pointer to the first
1350 one, others are linked in a list by the next_grp field. Decide about scalar
1351 replacements on the way, return true iff any are to be created. */
1354 build_access_trees (struct access *access)
1358 struct access *root = access;
1360 build_access_subtree (&access);
1361 root->next_grp = access;
1365 /* Analyze the subtree of accesses rooted in ROOT, scheduling replacements when
1366 both seeming beneficial and when ALLOW_REPLACEMENTS allows it. Also set
1367 all sorts of access flags appropriately along the way, notably always ser
1368 grp_read when MARK_READ is true and grp_write when MARK_WRITE is true. */
1371 analyze_access_subtree (struct access *root, bool allow_replacements,
1372 bool mark_read, bool mark_write)
1374 struct access *child;
1375 HOST_WIDE_INT limit = root->offset + root->size;
1376 HOST_WIDE_INT covered_to = root->offset;
1377 bool scalar = is_gimple_reg_type (root->type);
1378 bool hole = false, sth_created = false;
1381 root->grp_read = true;
1382 else if (root->grp_read)
1386 root->grp_write = true;
1387 else if (root->grp_write)
1390 if (root->grp_unscalarizable_region)
1391 allow_replacements = false;
1393 for (child = root->first_child; child; child = child->next_sibling)
1395 if (!hole && child->offset < covered_to)
1398 covered_to += child->size;
1400 sth_created |= analyze_access_subtree (child, allow_replacements,
1401 mark_read, mark_write);
1403 root->grp_unscalarized_data |= child->grp_unscalarized_data;
1404 hole |= !child->grp_covered;
1407 if (allow_replacements && scalar && !root->first_child)
1409 if (dump_file && (dump_flags & TDF_DETAILS))
1411 fprintf (dump_file, "Marking ");
1412 print_generic_expr (dump_file, root->base, 0);
1413 fprintf (dump_file, " offset: %u, size: %u: ",
1414 (unsigned) root->offset, (unsigned) root->size);
1415 fprintf (dump_file, " to be replaced.\n");
1418 root->grp_to_be_replaced = 1;
1422 else if (covered_to < limit)
1425 if (sth_created && !hole)
1427 root->grp_covered = 1;
1430 if (root->grp_write || TREE_CODE (root->base) == PARM_DECL)
1431 root->grp_unscalarized_data = 1; /* not covered and written to */
1437 /* Analyze all access trees linked by next_grp by the means of
1438 analyze_access_subtree. */
1440 analyze_access_trees (struct access *access)
1446 if (analyze_access_subtree (access, true, false, false))
1448 access = access->next_grp;
1454 /* Return true iff a potential new child of LACC at offset OFFSET and with size
1455 SIZE would conflict with an already existing one. If exactly such a child
1456 already exists in LACC, store a pointer to it in EXACT_MATCH. */
1459 child_would_conflict_in_lacc (struct access *lacc, HOST_WIDE_INT norm_offset,
1460 HOST_WIDE_INT size, struct access **exact_match)
1462 struct access *child;
1464 for (child = lacc->first_child; child; child = child->next_sibling)
1466 if (child->offset == norm_offset && child->size == size)
1468 *exact_match = child;
1472 if (child->offset < norm_offset + size
1473 && child->offset + child->size > norm_offset)
1480 /* Set the expr of TARGET to one just like MODEL but with is own base at the
1481 bottom of the handled components. */
1484 duplicate_expr_for_different_base (struct access *target,
1485 struct access *model)
1487 tree t, expr = unshare_expr (model->expr);
1489 gcc_assert (handled_component_p (expr));
1491 while (handled_component_p (TREE_OPERAND (t, 0)))
1492 t = TREE_OPERAND (t, 0);
1493 gcc_assert (TREE_OPERAND (t, 0) == model->base);
1494 TREE_OPERAND (t, 0) = target->base;
1496 target->expr = expr;
1500 /* Create a new child access of PARENT, with all properties just like MODEL
1501 except for its offset and with its grp_write false and grp_read true.
1502 Return the new access. Note that this access is created long after all
1503 splicing and sorting, it's not located in any access vector and is
1504 automatically a representative of its group. */
1506 static struct access *
1507 create_artificial_child_access (struct access *parent, struct access *model,
1508 HOST_WIDE_INT new_offset)
1510 struct access *access;
1511 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 duplicate_expr_for_different_base (access, model);
1521 access->type = model->type;
1522 access->grp_write = true;
1523 access->grp_read = false;
1525 child = &parent->first_child;
1526 while (*child && (*child)->offset < new_offset)
1527 child = &(*child)->next_sibling;
1529 access->next_sibling = *child;
1536 /* Propagate all subaccesses of RACC across an assignment link to LACC. Return
1537 true if any new subaccess was created. Additionally, if RACC is a scalar
1538 access but LACC is not, change the type of the latter. */
1541 propagate_subacesses_accross_link (struct access *lacc, struct access *racc)
1543 struct access *rchild;
1544 HOST_WIDE_INT norm_delta = lacc->offset - racc->offset;
1548 if (is_gimple_reg_type (lacc->type)
1549 || lacc->grp_unscalarizable_region
1550 || racc->grp_unscalarizable_region)
1553 if (!lacc->first_child && !racc->first_child
1554 && is_gimple_reg_type (racc->type))
1556 duplicate_expr_for_different_base (lacc, racc);
1557 lacc->type = racc->type;
1561 for (rchild = racc->first_child; rchild; rchild = rchild->next_sibling)
1563 struct access *new_acc = NULL;
1564 HOST_WIDE_INT norm_offset = rchild->offset + norm_delta;
1566 if (rchild->grp_unscalarizable_region)
1569 if (child_would_conflict_in_lacc (lacc, norm_offset, rchild->size,
1572 if (new_acc && rchild->first_child)
1573 ret |= propagate_subacesses_accross_link (new_acc, rchild);
1577 /* If a (part of) a union field is on the RHS of an assignment, it can
1578 have sub-accesses which do not make sense on the LHS (PR 40351).
1579 Check that this is not the case. */
1580 if (!build_ref_for_offset (NULL, TREE_TYPE (lacc->base), norm_offset,
1581 rchild->type, false))
1584 new_acc = create_artificial_child_access (lacc, rchild, norm_offset);
1585 if (racc->first_child)
1586 propagate_subacesses_accross_link (new_acc, rchild);
1594 /* Propagate all subaccesses across assignment links. */
1597 propagate_all_subaccesses (void)
1599 while (work_queue_head)
1601 struct access *racc = pop_access_from_work_queue ();
1602 struct assign_link *link;
1604 gcc_assert (racc->first_link);
1606 for (link = racc->first_link; link; link = link->next)
1608 struct access *lacc = link->lacc;
1610 if (!bitmap_bit_p (candidate_bitmap, DECL_UID (lacc->base)))
1612 lacc = lacc->group_representative;
1613 if (propagate_subacesses_accross_link (lacc, racc)
1614 && lacc->first_link)
1615 add_access_to_work_queue (lacc);
1620 /* Go through all accesses collected throughout the (intraprocedural) analysis
1621 stage, exclude overlapping ones, identify representatives and build trees
1622 out of them, making decisions about scalarization on the way. Return true
1623 iff there are any to-be-scalarized variables after this stage. */
1626 analyze_all_variable_accesses (void)
1629 referenced_var_iterator rvi;
1632 FOR_EACH_REFERENCED_VAR (var, rvi)
1633 if (bitmap_bit_p (candidate_bitmap, DECL_UID (var)))
1635 struct access *access;
1637 access = sort_and_splice_var_accesses (var);
1639 build_access_trees (access);
1641 disqualify_candidate (var,
1642 "No or inhibitingly overlapping accesses.");
1645 propagate_all_subaccesses ();
1647 FOR_EACH_REFERENCED_VAR (var, rvi)
1648 if (bitmap_bit_p (candidate_bitmap, DECL_UID (var)))
1650 struct access *access = get_first_repr_for_decl (var);
1652 if (analyze_access_trees (access))
1655 if (dump_file && (dump_flags & TDF_DETAILS))
1657 fprintf (dump_file, "\nAccess trees for ");
1658 print_generic_expr (dump_file, var, 0);
1659 fprintf (dump_file, " (UID: %u): \n", DECL_UID (var));
1660 dump_access_tree (dump_file, access);
1661 fprintf (dump_file, "\n");
1665 disqualify_candidate (var, "No scalar replacements to be created.");
1670 statistics_counter_event (cfun, "Scalarized aggregates", res);
1677 /* Return true iff a reference statement into aggregate AGG can be built for
1678 every single to-be-replaced accesses that is a child of ACCESS, its sibling
1679 or a child of its sibling. TOP_OFFSET is the offset from the processed
1680 access subtree that has to be subtracted from offset of each access. */
1683 ref_expr_for_all_replacements_p (struct access *access, tree agg,
1684 HOST_WIDE_INT top_offset)
1688 if (access->grp_to_be_replaced
1689 && !build_ref_for_offset (NULL, TREE_TYPE (agg),
1690 access->offset - top_offset,
1691 access->type, false))
1694 if (access->first_child
1695 && !ref_expr_for_all_replacements_p (access->first_child, agg,
1699 access = access->next_sibling;
1706 /* Generate statements copying scalar replacements of accesses within a subtree
1707 into or out of AGG. ACCESS is the first child of the root of the subtree to
1708 be processed. AGG is an aggregate type expression (can be a declaration but
1709 does not have to be, it can for example also be an indirect_ref).
1710 TOP_OFFSET is the offset of the processed subtree which has to be subtracted
1711 from offsets of individual accesses to get corresponding offsets for AGG.
1712 If CHUNK_SIZE is non-null, copy only replacements in the interval
1713 <start_offset, start_offset + chunk_size>, otherwise copy all. GSI is a
1714 statement iterator used to place the new statements. WRITE should be true
1715 when the statements should write from AGG to the replacement and false if
1716 vice versa. if INSERT_AFTER is true, new statements will be added after the
1717 current statement in GSI, they will be added before the statement
1721 generate_subtree_copies (struct access *access, tree agg,
1722 HOST_WIDE_INT top_offset,
1723 HOST_WIDE_INT start_offset, HOST_WIDE_INT chunk_size,
1724 gimple_stmt_iterator *gsi, bool write,
1729 tree expr = unshare_expr (agg);
1731 if (chunk_size && access->offset >= start_offset + chunk_size)
1734 if (access->grp_to_be_replaced
1736 || access->offset + access->size > start_offset))
1738 tree repl = get_access_replacement (access);
1742 ref_found = build_ref_for_offset (&expr, TREE_TYPE (agg),
1743 access->offset - top_offset,
1744 access->type, false);
1745 gcc_assert (ref_found);
1749 if (access->grp_partial_lhs)
1750 expr = force_gimple_operand_gsi (gsi, expr, true, NULL_TREE,
1752 insert_after ? GSI_NEW_STMT
1754 stmt = gimple_build_assign (repl, expr);
1758 TREE_NO_WARNING (repl) = 1;
1759 if (access->grp_partial_lhs)
1760 repl = force_gimple_operand_gsi (gsi, repl, true, NULL_TREE,
1762 insert_after ? GSI_NEW_STMT
1764 stmt = gimple_build_assign (expr, repl);
1768 gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
1770 gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
1772 sra_stats.subtree_copies++;
1775 if (access->first_child)
1776 generate_subtree_copies (access->first_child, agg, top_offset,
1777 start_offset, chunk_size, gsi,
1778 write, insert_after);
1780 access = access->next_sibling;
1785 /* Assign zero to all scalar replacements in an access subtree. ACCESS is the
1786 the root of the subtree to be processed. GSI is the statement iterator used
1787 for inserting statements which are added after the current statement if
1788 INSERT_AFTER is true or before it otherwise. */
1791 init_subtree_with_zero (struct access *access, gimple_stmt_iterator *gsi,
1795 struct access *child;
1797 if (access->grp_to_be_replaced)
1801 stmt = gimple_build_assign (get_access_replacement (access),
1802 fold_convert (access->type,
1803 integer_zero_node));
1805 gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
1807 gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
1811 for (child = access->first_child; child; child = child->next_sibling)
1812 init_subtree_with_zero (child, gsi, insert_after);
1815 /* Search for an access representative for the given expression EXPR and
1816 return it or NULL if it cannot be found. */
1818 static struct access *
1819 get_access_for_expr (tree expr)
1821 HOST_WIDE_INT offset, size, max_size;
1824 /* FIXME: This should not be necessary but Ada produces V_C_Es with a type of
1825 a different size than the size of its argument and we need the latter
1827 if (TREE_CODE (expr) == VIEW_CONVERT_EXPR)
1828 expr = TREE_OPERAND (expr, 0);
1830 base = get_ref_base_and_extent (expr, &offset, &size, &max_size);
1831 if (max_size == -1 || !DECL_P (base))
1834 if (!bitmap_bit_p (candidate_bitmap, DECL_UID (base)))
1837 return get_var_base_offset_size_access (base, offset, max_size);
1840 /* Callback for scan_function. Replace the expression EXPR with a scalar
1841 replacement if there is one and generate other statements to do type
1842 conversion or subtree copying if necessary. GSI is used to place newly
1843 created statements, WRITE is true if the expression is being written to (it
1844 is on a LHS of a statement or output in an assembly statement). */
1847 sra_modify_expr (tree *expr, gimple_stmt_iterator *gsi, bool write,
1848 void *data ATTRIBUTE_UNUSED)
1850 struct access *access;
1853 if (TREE_CODE (*expr) == BIT_FIELD_REF)
1856 expr = &TREE_OPERAND (*expr, 0);
1861 if (TREE_CODE (*expr) == REALPART_EXPR || TREE_CODE (*expr) == IMAGPART_EXPR)
1862 expr = &TREE_OPERAND (*expr, 0);
1863 access = get_access_for_expr (*expr);
1866 type = TREE_TYPE (*expr);
1868 if (access->grp_to_be_replaced)
1870 tree repl = get_access_replacement (access);
1871 /* If we replace a non-register typed access simply use the original
1872 access expression to extract the scalar component afterwards.
1873 This happens if scalarizing a function return value or parameter
1874 like in gcc.c-torture/execute/20041124-1.c, 20050316-1.c and
1875 gcc.c-torture/compile/20011217-1.c. */
1876 if (!is_gimple_reg_type (type))
1881 tree ref = unshare_expr (access->expr);
1882 if (access->grp_partial_lhs)
1883 ref = force_gimple_operand_gsi (gsi, ref, true, NULL_TREE,
1884 false, GSI_NEW_STMT);
1885 stmt = gimple_build_assign (repl, ref);
1886 gsi_insert_after (gsi, stmt, GSI_NEW_STMT);
1890 if (access->grp_partial_lhs)
1891 repl = force_gimple_operand_gsi (gsi, repl, true, NULL_TREE,
1892 true, GSI_SAME_STMT);
1893 stmt = gimple_build_assign (unshare_expr (access->expr), repl);
1894 gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
1899 gcc_assert (useless_type_conversion_p (type, access->type));
1905 if (access->first_child)
1907 HOST_WIDE_INT start_offset, chunk_size;
1909 && host_integerp (TREE_OPERAND (bfr, 1), 1)
1910 && host_integerp (TREE_OPERAND (bfr, 2), 1))
1912 chunk_size = tree_low_cst (TREE_OPERAND (bfr, 1), 1);
1913 start_offset = access->offset
1914 + tree_low_cst (TREE_OPERAND (bfr, 2), 1);
1917 start_offset = chunk_size = 0;
1919 generate_subtree_copies (access->first_child, access->base, 0,
1920 start_offset, chunk_size, gsi, write, write);
1925 /* Where scalar replacements of the RHS have been written to when a replacement
1926 of a LHS of an assigments cannot be direclty loaded from a replacement of
1928 enum unscalarized_data_handling { SRA_UDH_NONE, /* Nothing done so far. */
1929 SRA_UDH_RIGHT, /* Data flushed to the RHS. */
1930 SRA_UDH_LEFT }; /* Data flushed to the LHS. */
1932 /* Store all replacements in the access tree rooted in TOP_RACC either to their
1933 base aggregate if there are unscalarized data or directly to LHS
1936 static enum unscalarized_data_handling
1937 handle_unscalarized_data_in_subtree (struct access *top_racc, tree lhs,
1938 gimple_stmt_iterator *gsi)
1940 if (top_racc->grp_unscalarized_data)
1942 generate_subtree_copies (top_racc->first_child, top_racc->base, 0, 0, 0,
1944 return SRA_UDH_RIGHT;
1948 generate_subtree_copies (top_racc->first_child, lhs, top_racc->offset,
1949 0, 0, gsi, false, false);
1950 return SRA_UDH_LEFT;
1955 /* Try to generate statements to load all sub-replacements in an access
1956 (sub)tree (LACC is the first child) from scalar replacements in the TOP_RACC
1957 (sub)tree. If that is not possible, refresh the TOP_RACC base aggregate and
1958 load the accesses from it. LEFT_OFFSET is the offset of the left whole
1959 subtree being copied, RIGHT_OFFSET is the same thing for the right subtree.
1960 GSI is stmt iterator used for statement insertions. *REFRESHED is true iff
1961 the rhs top aggregate has already been refreshed by contents of its scalar
1962 reductions and is set to true if this function has to do it. */
1965 load_assign_lhs_subreplacements (struct access *lacc, struct access *top_racc,
1966 HOST_WIDE_INT left_offset,
1967 HOST_WIDE_INT right_offset,
1968 gimple_stmt_iterator *old_gsi,
1969 gimple_stmt_iterator *new_gsi,
1970 enum unscalarized_data_handling *refreshed,
1973 location_t loc = EXPR_LOCATION (lacc->expr);
1976 if (lacc->grp_to_be_replaced)
1978 struct access *racc;
1979 HOST_WIDE_INT offset = lacc->offset - left_offset + right_offset;
1983 racc = find_access_in_subtree (top_racc, offset, lacc->size);
1984 if (racc && racc->grp_to_be_replaced)
1986 rhs = get_access_replacement (racc);
1987 if (!useless_type_conversion_p (lacc->type, racc->type))
1988 rhs = fold_build1_loc (loc, VIEW_CONVERT_EXPR, lacc->type, rhs);
1994 /* No suitable access on the right hand side, need to load from
1995 the aggregate. See if we have to update it first... */
1996 if (*refreshed == SRA_UDH_NONE)
1997 *refreshed = handle_unscalarized_data_in_subtree (top_racc,
2000 if (*refreshed == SRA_UDH_LEFT)
2001 rhs = unshare_expr (lacc->expr);
2004 rhs = unshare_expr (top_racc->base);
2005 repl_found = build_ref_for_offset (&rhs,
2006 TREE_TYPE (top_racc->base),
2007 offset, lacc->type, false);
2008 gcc_assert (repl_found);
2012 stmt = gimple_build_assign (get_access_replacement (lacc), rhs);
2013 gsi_insert_after (new_gsi, stmt, GSI_NEW_STMT);
2015 sra_stats.subreplacements++;
2017 else if (*refreshed == SRA_UDH_NONE
2018 && lacc->grp_read && !lacc->grp_covered)
2019 *refreshed = handle_unscalarized_data_in_subtree (top_racc, lhs,
2022 if (lacc->first_child)
2023 load_assign_lhs_subreplacements (lacc->first_child, top_racc,
2024 left_offset, right_offset,
2025 old_gsi, new_gsi, refreshed, lhs);
2026 lacc = lacc->next_sibling;
2031 /* Modify assignments with a CONSTRUCTOR on their RHS. STMT contains a pointer
2032 to the assignment and GSI is the statement iterator pointing at it. Returns
2033 the same values as sra_modify_assign. */
2035 static enum scan_assign_result
2036 sra_modify_constructor_assign (gimple *stmt, gimple_stmt_iterator *gsi)
2038 tree lhs = gimple_assign_lhs (*stmt);
2041 acc = get_access_for_expr (lhs);
2045 if (VEC_length (constructor_elt,
2046 CONSTRUCTOR_ELTS (gimple_assign_rhs1 (*stmt))) > 0)
2048 /* I have never seen this code path trigger but if it can happen the
2049 following should handle it gracefully. */
2050 if (access_has_children_p (acc))
2051 generate_subtree_copies (acc->first_child, acc->base, 0, 0, 0, gsi,
2053 return SRA_SA_PROCESSED;
2056 if (acc->grp_covered)
2058 init_subtree_with_zero (acc, gsi, false);
2059 unlink_stmt_vdef (*stmt);
2060 gsi_remove (gsi, true);
2061 return SRA_SA_REMOVED;
2065 init_subtree_with_zero (acc, gsi, true);
2066 return SRA_SA_PROCESSED;
2071 /* Callback of scan_function to process assign statements. It examines both
2072 sides of the statement, replaces them with a scalare replacement if there is
2073 one and generating copying of replacements if scalarized aggregates have been
2074 used in the assignment. STMT is a pointer to the assign statement, GSI is
2075 used to hold generated statements for type conversions and subtree
2078 static enum scan_assign_result
2079 sra_modify_assign (gimple *stmt, gimple_stmt_iterator *gsi,
2080 void *data ATTRIBUTE_UNUSED)
2082 struct access *lacc, *racc;
2084 bool modify_this_stmt = false;
2085 bool force_gimple_rhs = false;
2086 location_t loc = gimple_location (*stmt);
2088 if (!gimple_assign_single_p (*stmt))
2090 lhs = gimple_assign_lhs (*stmt);
2091 rhs = gimple_assign_rhs1 (*stmt);
2093 if (TREE_CODE (rhs) == CONSTRUCTOR)
2094 return sra_modify_constructor_assign (stmt, gsi);
2096 if (TREE_CODE (rhs) == REALPART_EXPR || TREE_CODE (lhs) == REALPART_EXPR
2097 || TREE_CODE (rhs) == IMAGPART_EXPR || TREE_CODE (lhs) == IMAGPART_EXPR
2098 || TREE_CODE (rhs) == BIT_FIELD_REF || TREE_CODE (lhs) == BIT_FIELD_REF)
2100 modify_this_stmt = sra_modify_expr (gimple_assign_rhs1_ptr (*stmt),
2102 modify_this_stmt |= sra_modify_expr (gimple_assign_lhs_ptr (*stmt),
2104 return modify_this_stmt ? SRA_SA_PROCESSED : SRA_SA_NONE;
2107 lacc = get_access_for_expr (lhs);
2108 racc = get_access_for_expr (rhs);
2112 if (lacc && lacc->grp_to_be_replaced)
2114 lhs = get_access_replacement (lacc);
2115 gimple_assign_set_lhs (*stmt, lhs);
2116 modify_this_stmt = true;
2117 if (lacc->grp_partial_lhs)
2118 force_gimple_rhs = true;
2122 if (racc && racc->grp_to_be_replaced)
2124 rhs = get_access_replacement (racc);
2125 modify_this_stmt = true;
2126 if (racc->grp_partial_lhs)
2127 force_gimple_rhs = true;
2131 if (modify_this_stmt)
2133 if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
2135 /* If we can avoid creating a VIEW_CONVERT_EXPR do so.
2136 ??? This should move to fold_stmt which we simply should
2137 call after building a VIEW_CONVERT_EXPR here. */
2138 if (AGGREGATE_TYPE_P (TREE_TYPE (lhs))
2139 && !access_has_children_p (lacc))
2141 tree expr = unshare_expr (lhs);
2142 if (build_ref_for_offset (&expr, TREE_TYPE (lhs), 0,
2143 TREE_TYPE (rhs), false))
2146 gimple_assign_set_lhs (*stmt, expr);
2149 else if (AGGREGATE_TYPE_P (TREE_TYPE (rhs))
2150 && !access_has_children_p (racc))
2152 tree expr = unshare_expr (rhs);
2153 if (build_ref_for_offset (&expr, TREE_TYPE (rhs), 0,
2154 TREE_TYPE (lhs), false))
2157 if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
2159 rhs = fold_build1_loc (loc, VIEW_CONVERT_EXPR, TREE_TYPE (lhs), rhs);
2160 if (!is_gimple_reg (lhs))
2161 force_gimple_rhs = true;
2165 if (force_gimple_rhs)
2166 rhs = force_gimple_operand_gsi (gsi, rhs, true, NULL_TREE,
2167 true, GSI_SAME_STMT);
2168 if (gimple_assign_rhs1 (*stmt) != rhs)
2170 gimple_assign_set_rhs_from_tree (gsi, rhs);
2171 gcc_assert (*stmt == gsi_stmt (*gsi));
2175 /* From this point on, the function deals with assignments in between
2176 aggregates when at least one has scalar reductions of some of its
2177 components. There are three possible scenarios: Both the LHS and RHS have
2178 to-be-scalarized components, 2) only the RHS has or 3) only the LHS has.
2180 In the first case, we would like to load the LHS components from RHS
2181 components whenever possible. If that is not possible, we would like to
2182 read it directly from the RHS (after updating it by storing in it its own
2183 components). If there are some necessary unscalarized data in the LHS,
2184 those will be loaded by the original assignment too. If neither of these
2185 cases happen, the original statement can be removed. Most of this is done
2186 by load_assign_lhs_subreplacements.
2188 In the second case, we would like to store all RHS scalarized components
2189 directly into LHS and if they cover the aggregate completely, remove the
2190 statement too. In the third case, we want the LHS components to be loaded
2191 directly from the RHS (DSE will remove the original statement if it
2194 This is a bit complex but manageable when types match and when unions do
2195 not cause confusion in a way that we cannot really load a component of LHS
2196 from the RHS or vice versa (the access representing this level can have
2197 subaccesses that are accessible only through a different union field at a
2198 higher level - different from the one used in the examined expression).
2201 Therefore, I specially handle a fourth case, happening when there is a
2202 specific type cast or it is impossible to locate a scalarized subaccess on
2203 the other side of the expression. If that happens, I simply "refresh" the
2204 RHS by storing in it is scalarized components leave the original statement
2205 there to do the copying and then load the scalar replacements of the LHS.
2206 This is what the first branch does. */
2208 if (contains_view_convert_expr_p (rhs) || contains_view_convert_expr_p (lhs)
2209 || (access_has_children_p (racc)
2210 && !ref_expr_for_all_replacements_p (racc, lhs, racc->offset))
2211 || (access_has_children_p (lacc)
2212 && !ref_expr_for_all_replacements_p (lacc, rhs, lacc->offset)))
2214 if (access_has_children_p (racc))
2215 generate_subtree_copies (racc->first_child, racc->base, 0, 0, 0,
2217 if (access_has_children_p (lacc))
2218 generate_subtree_copies (lacc->first_child, lacc->base, 0, 0, 0,
2220 sra_stats.separate_lhs_rhs_handling++;
2224 if (access_has_children_p (lacc) && access_has_children_p (racc))
2226 gimple_stmt_iterator orig_gsi = *gsi;
2227 enum unscalarized_data_handling refreshed;
2229 if (lacc->grp_read && !lacc->grp_covered)
2230 refreshed = handle_unscalarized_data_in_subtree (racc, lhs, gsi);
2232 refreshed = SRA_UDH_NONE;
2234 load_assign_lhs_subreplacements (lacc->first_child, racc,
2235 lacc->offset, racc->offset,
2236 &orig_gsi, gsi, &refreshed, lhs);
2237 if (refreshed != SRA_UDH_RIGHT)
2239 if (*stmt == gsi_stmt (*gsi))
2242 unlink_stmt_vdef (*stmt);
2243 gsi_remove (&orig_gsi, true);
2244 sra_stats.deleted++;
2245 return SRA_SA_REMOVED;
2250 if (access_has_children_p (racc))
2252 if (!racc->grp_unscalarized_data)
2254 generate_subtree_copies (racc->first_child, lhs,
2255 racc->offset, 0, 0, gsi,
2257 gcc_assert (*stmt == gsi_stmt (*gsi));
2258 unlink_stmt_vdef (*stmt);
2259 gsi_remove (gsi, true);
2260 sra_stats.deleted++;
2261 return SRA_SA_REMOVED;
2264 generate_subtree_copies (racc->first_child, lhs,
2265 racc->offset, 0, 0, gsi, false, true);
2267 else if (access_has_children_p (lacc))
2268 generate_subtree_copies (lacc->first_child, rhs, lacc->offset,
2269 0, 0, gsi, true, true);
2272 return modify_this_stmt ? SRA_SA_PROCESSED : SRA_SA_NONE;
2275 /* Generate statements initializing scalar replacements of parts of function
2279 initialize_parameter_reductions (void)
2281 gimple_stmt_iterator gsi;
2282 gimple_seq seq = NULL;
2285 for (parm = DECL_ARGUMENTS (current_function_decl);
2287 parm = TREE_CHAIN (parm))
2289 VEC (access_p, heap) *access_vec;
2290 struct access *access;
2292 if (!bitmap_bit_p (candidate_bitmap, DECL_UID (parm)))
2294 access_vec = get_base_access_vector (parm);
2300 seq = gimple_seq_alloc ();
2301 gsi = gsi_start (seq);
2304 for (access = VEC_index (access_p, access_vec, 0);
2306 access = access->next_grp)
2307 generate_subtree_copies (access, parm, 0, 0, 0, &gsi, true, true);
2311 gsi_insert_seq_on_edge_immediate (single_succ_edge (ENTRY_BLOCK_PTR), seq);
2314 /* The "main" function of intraprocedural SRA passes. Runs the analysis and if
2315 it reveals there are components of some aggregates to be scalarized, it runs
2316 the required transformations. */
2318 perform_intra_sra (void)
2323 if (!find_var_candidates ())
2326 if (!scan_function (build_access_from_expr, build_accesses_from_assign, NULL,
2330 if (!analyze_all_variable_accesses ())
2333 scan_function (sra_modify_expr, sra_modify_assign, NULL,
2335 initialize_parameter_reductions ();
2337 statistics_counter_event (cfun, "Scalar replacements created",
2338 sra_stats.replacements);
2339 statistics_counter_event (cfun, "Modified expressions", sra_stats.exprs);
2340 statistics_counter_event (cfun, "Subtree copy stmts",
2341 sra_stats.subtree_copies);
2342 statistics_counter_event (cfun, "Subreplacement stmts",
2343 sra_stats.subreplacements);
2344 statistics_counter_event (cfun, "Deleted stmts", sra_stats.deleted);
2345 statistics_counter_event (cfun, "Separate LHS and RHS handling",
2346 sra_stats.separate_lhs_rhs_handling);
2348 ret = TODO_update_ssa;
2351 sra_deinitialize ();
2355 /* Perform early intraprocedural SRA. */
2357 early_intra_sra (void)
2359 sra_mode = SRA_MODE_EARLY_INTRA;
2360 return perform_intra_sra ();
2363 /* Perform "late" intraprocedural SRA. */
2365 late_intra_sra (void)
2367 sra_mode = SRA_MODE_INTRA;
2368 return perform_intra_sra ();
2373 gate_intra_sra (void)
2375 return flag_tree_sra != 0;
2379 struct gimple_opt_pass pass_sra_early =
2384 gate_intra_sra, /* gate */
2385 early_intra_sra, /* execute */
2388 0, /* static_pass_number */
2389 TV_TREE_SRA, /* tv_id */
2390 PROP_cfg | PROP_ssa, /* properties_required */
2391 0, /* properties_provided */
2392 0, /* properties_destroyed */
2393 0, /* todo_flags_start */
2397 | TODO_verify_ssa /* todo_flags_finish */
2402 struct gimple_opt_pass pass_sra =
2407 gate_intra_sra, /* gate */
2408 late_intra_sra, /* execute */
2411 0, /* static_pass_number */
2412 TV_TREE_SRA, /* tv_id */
2413 PROP_cfg | PROP_ssa, /* properties_required */
2414 0, /* properties_provided */
2415 0, /* properties_destroyed */
2416 TODO_update_address_taken, /* todo_flags_start */
2420 | TODO_verify_ssa /* todo_flags_finish */