| Message ID | ri6y2tsa0pm.fsf@suse.cz |
|---|---|
| State | New |
| Headers | show |
| Series | [1/4] SRA: Add verification of accesses | expand |
On Tue, 28 Jan 2020, Martin Jambor wrote: > Hi, > > the previous patch unfortunately does not fix the first testcase in PR > 92706 and since I am afraid it might be the important one, I also > focused on that. The issue here is again total scalarization accesses > clashing with those representing accesses in the IL - on another > aggregate but here the sides are switched. Whereas in the previous > case the total scalarization accesses prevented propagation along > assignments, here we have the user accesses on the LHS, so even though > we do not create anything there, we totally scalarize the RHS and > again end up with assignments with different scalarizations leading to > bad code. > > So we clearly need to propagate information about accesses from RHSs > to LHSs too, which the patch below does. Because the intent is only > preventing bad total scalarization - which the last patch now performs > late enough - and do not care about grp_write flag and so forth, the > propagation is a bit simpler and so I did not try to unify all of the > code for both directions. > > More information and some discussion is in the thread from the initial > submission, the code has not changed in any (substantial) way. See > https://gcc.gnu.org/ml/gcc-patches/2019-12/msg01184.html and > https://gcc.gnu.org/ml/gcc-patches/2020-01/msg00698.html. > > Bootstrapped and tested on x86_64-linux. OK. Guess you should commit the series up to here separately from the followup PR92486. Thanks, Richard. > Thanks, > > Martin > > 2019-12-11 Martin Jambor <mjambor@suse.cz> > > PR tree-optimization/92706 > * tree-sra.c (struct access): Fields first_link, last_link, > next_queued and grp_queued renamed to first_rhs_link, last_rhs_link, > next_rhs_queued and grp_rhs_queued respectively, new fields > first_lhs_link, last_lhs_link, next_lhs_queued and grp_lhs_queued. > (struct assign_link): Field next renamed to next_rhs, new field > next_lhs. Updated comment. > (work_queue_head): Renamed to rhs_work_queue_head. > (lhs_work_queue_head): New variable. > (add_link_to_lhs): New function. > (relink_to_new_repr): Also relink LHS lists. > (add_access_to_work_queue): Renamed to add_access_to_rhs_work_queue. > (add_access_to_lhs_work_queue): New function. > (pop_access_from_work_queue): Renamed to > pop_access_from_rhs_work_queue. > (pop_access_from_lhs_work_queue): New function. > (build_accesses_from_assign): Also add links to LHS lists and to LHS > work_queue. > (child_would_conflict_in_lacc): Renamed to > child_would_conflict_in_acc. Adjusted parameter names. > (create_artificial_child_access): New parameter set_grp_read, use it. > (subtree_mark_written_and_enqueue): Renamed to > subtree_mark_written_and_rhs_enqueue. > (propagate_subaccesses_across_link): Renamed to > propagate_subaccesses_from_rhs. > (propagate_subaccesses_from_lhs): New function. > (propagate_all_subaccesses): Also propagate subaccesses from LHSs to > RHSs. > > testsuite/ > * gcc.dg/tree-ssa/pr92706-1.c: New test. > --- > gcc/testsuite/gcc.dg/tree-ssa/pr92706-1.c | 17 ++ > gcc/tree-sra.c | 306 ++++++++++++++++------ > 2 files changed, 248 insertions(+), 75 deletions(-) > create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr92706-1.c > > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr92706-1.c b/gcc/testsuite/gcc.dg/tree-ssa/pr92706-1.c > new file mode 100644 > index 00000000000..c36d103798e > --- /dev/null > +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr92706-1.c > @@ -0,0 +1,17 @@ > +/* { dg-do compile } */ > +/* { dg-options "-O2 -fdump-tree-esra-details" } */ > + > +struct S { int i[4]; } __attribute__((aligned(128))); > +typedef __int128_t my_int128 __attribute__((may_alias)); > +__int128_t load (void *p) > +{ > + struct S v; > + __builtin_memcpy (&v, p, sizeof (struct S)); > + struct S u; > + u = v; > + struct S w; > + w = u; > + return *(my_int128 *)&w; > +} > + > +/* { dg-final { scan-tree-dump-not "Created a replacement for u offset: \[^0\]" "esra" } } */ > diff --git a/gcc/tree-sra.c b/gcc/tree-sra.c > index 2b0849858de..ea8594db193 100644 > --- a/gcc/tree-sra.c > +++ b/gcc/tree-sra.c > @@ -167,11 +167,15 @@ struct access > struct access *next_sibling; > > /* Pointers to the first and last element in the linked list of assign > - links. */ > - struct assign_link *first_link, *last_link; > + links for propagation from LHS to RHS. */ > + struct assign_link *first_rhs_link, *last_rhs_link; > > - /* Pointer to the next access in the work queue. */ > - struct access *next_queued; > + /* Pointers to the first and last element in the linked list of assign > + links for propagation from LHS to RHS. */ > + struct assign_link *first_lhs_link, *last_lhs_link; > + > + /* Pointer to the next access in the work queues. */ > + struct access *next_rhs_queued, *next_lhs_queued; > > /* Replacement variable for this access "region." Never to be accessed > directly, always only by the means of get_access_replacement() and only > @@ -184,8 +188,11 @@ struct access > /* Is this particular access write access? */ > unsigned write : 1; > > - /* Is this access currently in the work queue? */ > - unsigned grp_queued : 1; > + /* Is this access currently in the rhs work queue? */ > + unsigned grp_rhs_queued : 1; > + > + /* Is this access currently in the lhs work queue? */ > + unsigned grp_lhs_queued : 1; > > /* Does this group contain a write access? This flag is propagated down the > access tree. */ > @@ -262,12 +269,14 @@ typedef struct access *access_p; > static object_allocator<struct access> access_pool ("SRA accesses"); > > /* A structure linking lhs and rhs accesses from an aggregate assignment. They > - are used to propagate subaccesses from rhs to lhs as long as they don't > - conflict with what is already there. */ > + are used to propagate subaccesses from rhs to lhs and vice versa as long as > + they don't conflict with what is already there. In the RHS->LHS direction, > + we also propagate grp_write flag to lazily mark that the access contains any > + meaningful data. */ > struct assign_link > { > struct access *lacc, *racc; > - struct assign_link *next; > + struct assign_link *next_rhs, *next_lhs; > }; > > /* Alloc pool for allocating assign link structures. */ > @@ -327,7 +336,7 @@ static struct obstack name_obstack; > > /* Head of a linked list of accesses that need to have its subaccesses > propagated to their assignment counterparts. */ > -static struct access *work_queue_head; > +static struct access *rhs_work_queue_head, *lhs_work_queue_head; > > /* Dump contents of ACCESS to file F in a human friendly way. If GRP is true, > representative fields are dumped, otherwise those which only describe the > @@ -534,79 +543,155 @@ get_var_base_offset_size_access (tree base, HOST_WIDE_INT offset, > } > > /* Add LINK to the linked list of assign links of RACC. */ > + > static void > add_link_to_rhs (struct access *racc, struct assign_link *link) > { > gcc_assert (link->racc == racc); > > - if (!racc->first_link) > + if (!racc->first_rhs_link) > { > - gcc_assert (!racc->last_link); > - racc->first_link = link; > + gcc_assert (!racc->last_rhs_link); > + racc->first_rhs_link = link; > } > else > - racc->last_link->next = link; > + racc->last_rhs_link->next_rhs = link; > > - racc->last_link = link; > - link->next = NULL; > + racc->last_rhs_link = link; > + link->next_rhs = NULL; > } > > -/* Move all link structures in their linked list in OLD_RACC to the linked list > - in NEW_RACC. */ > +/* Add LINK to the linked list of lhs assign links of LACC. */ > + > static void > -relink_to_new_repr (struct access *new_racc, struct access *old_racc) > +add_link_to_lhs (struct access *lacc, struct assign_link *link) > { > - if (!old_racc->first_link) > + gcc_assert (link->lacc == lacc); > + > + if (!lacc->first_lhs_link) > { > - gcc_assert (!old_racc->last_link); > - return; > + gcc_assert (!lacc->last_lhs_link); > + lacc->first_lhs_link = link; > } > + else > + lacc->last_lhs_link->next_lhs = link; > + > + lacc->last_lhs_link = link; > + link->next_lhs = NULL; > +} > > - if (new_racc->first_link) > +/* Move all link structures in their linked list in OLD_ACC to the linked list > + in NEW_ACC. */ > +static void > +relink_to_new_repr (struct access *new_acc, struct access *old_acc) > +{ > + if (old_acc->first_rhs_link) > { > - gcc_assert (!new_racc->last_link->next); > - gcc_assert (!old_racc->last_link || !old_racc->last_link->next); > > - new_racc->last_link->next = old_racc->first_link; > - new_racc->last_link = old_racc->last_link; > + if (new_acc->first_rhs_link) > + { > + gcc_assert (!new_acc->last_rhs_link->next_rhs); > + gcc_assert (!old_acc->last_rhs_link > + || !old_acc->last_rhs_link->next_rhs); > + > + new_acc->last_rhs_link->next_rhs = old_acc->first_rhs_link; > + new_acc->last_rhs_link = old_acc->last_rhs_link; > + } > + else > + { > + gcc_assert (!new_acc->last_rhs_link); > + > + new_acc->first_rhs_link = old_acc->first_rhs_link; > + new_acc->last_rhs_link = old_acc->last_rhs_link; > + } > + old_acc->first_rhs_link = old_acc->last_rhs_link = NULL; > } > else > + gcc_assert (!old_acc->last_rhs_link); > + > + if (old_acc->first_lhs_link) > { > - gcc_assert (!new_racc->last_link); > > - new_racc->first_link = old_racc->first_link; > - new_racc->last_link = old_racc->last_link; > + if (new_acc->first_lhs_link) > + { > + gcc_assert (!new_acc->last_lhs_link->next_lhs); > + gcc_assert (!old_acc->last_lhs_link > + || !old_acc->last_lhs_link->next_lhs); > + > + new_acc->last_lhs_link->next_lhs = old_acc->first_lhs_link; > + new_acc->last_lhs_link = old_acc->last_lhs_link; > + } > + else > + { > + gcc_assert (!new_acc->last_lhs_link); > + > + new_acc->first_lhs_link = old_acc->first_lhs_link; > + new_acc->last_lhs_link = old_acc->last_lhs_link; > + } > + old_acc->first_lhs_link = old_acc->last_lhs_link = NULL; > } > - old_racc->first_link = old_racc->last_link = NULL; > + else > + gcc_assert (!old_acc->last_lhs_link); > + > } > > -/* Add ACCESS to the work queue (which is actually a stack). */ > +/* Add ACCESS to the work to queue for propagation of subaccesses from RHS to > + LHS (which is actually a stack). */ > > static void > -add_access_to_work_queue (struct access *access) > +add_access_to_rhs_work_queue (struct access *access) > { > - if (access->first_link && !access->grp_queued) > + if (access->first_rhs_link && !access->grp_rhs_queued) > { > - gcc_assert (!access->next_queued); > - access->next_queued = work_queue_head; > - access->grp_queued = 1; > - work_queue_head = access; > + gcc_assert (!access->next_rhs_queued); > + access->next_rhs_queued = rhs_work_queue_head; > + access->grp_rhs_queued = 1; > + rhs_work_queue_head = access; > } > } > > -/* Pop an access from the work queue, and return it, assuming there is one. */ > +/* Add ACCESS to the work to queue for propagation of subaccesses from LHS to > + RHS (which is actually a stack). */ > + > +static void > +add_access_to_lhs_work_queue (struct access *access) > +{ > + if (access->first_lhs_link && !access->grp_lhs_queued) > + { > + gcc_assert (!access->next_lhs_queued); > + access->next_lhs_queued = lhs_work_queue_head; > + access->grp_lhs_queued = 1; > + lhs_work_queue_head = access; > + } > +} > + > +/* Pop an access from the work queue for propagating from RHS to LHS, and > + return it, assuming there is one. */ > > static struct access * > -pop_access_from_work_queue (void) > +pop_access_from_rhs_work_queue (void) > { > - struct access *access = work_queue_head; > + struct access *access = rhs_work_queue_head; > > - work_queue_head = access->next_queued; > - access->next_queued = NULL; > - access->grp_queued = 0; > + rhs_work_queue_head = access->next_rhs_queued; > + access->next_rhs_queued = NULL; > + access->grp_rhs_queued = 0; > return access; > } > > +/* Pop an access from the work queue for propagating from LHS to RHS, and > + return it, assuming there is one. */ > + > +static struct access * > +pop_access_from_lhs_work_queue (void) > +{ > + struct access *access = lhs_work_queue_head; > + > + lhs_work_queue_head = access->next_lhs_queued; > + access->next_lhs_queued = NULL; > + access->grp_lhs_queued = 0; > + return access; > +} > > /* Allocate necessary structures. */ > > @@ -1203,7 +1288,9 @@ build_accesses_from_assign (gimple *stmt) > link->lacc = lacc; > link->racc = racc; > add_link_to_rhs (racc, link); > - add_access_to_work_queue (racc); > + add_link_to_lhs (lacc, link); > + add_access_to_rhs_work_queue (racc); > + add_access_to_lhs_work_queue (lacc); > > /* Let's delay marking the areas as written until propagation of accesses > across link, unless the nature of rhs tells us that its data comes > @@ -2492,17 +2579,17 @@ analyze_access_trees (struct access *access) > return ret; > } > > -/* Return true iff a potential new child of LACC at offset OFFSET and with size > +/* Return true iff a potential new child of ACC at offset OFFSET and with size > SIZE would conflict with an already existing one. If exactly such a child > - already exists in LACC, store a pointer to it in EXACT_MATCH. */ > + already exists in ACC, store a pointer to it in EXACT_MATCH. */ > > static bool > -child_would_conflict_in_lacc (struct access *lacc, HOST_WIDE_INT norm_offset, > +child_would_conflict_in_acc (struct access *acc, HOST_WIDE_INT norm_offset, > HOST_WIDE_INT size, struct access **exact_match) > { > struct access *child; > > - for (child = lacc->first_child; child; child = child->next_sibling) > + for (child = acc->first_child; child; child = child->next_sibling) > { > if (child->offset == norm_offset && child->size == size) > { > @@ -2528,7 +2615,7 @@ child_would_conflict_in_lacc (struct access *lacc, HOST_WIDE_INT norm_offset, > static struct access * > create_artificial_child_access (struct access *parent, struct access *model, > HOST_WIDE_INT new_offset, > - bool set_grp_write) > + bool set_grp_read, bool set_grp_write) > { > struct access **child; > tree expr = parent->base; > @@ -2551,8 +2638,8 @@ create_artificial_child_access (struct access *parent, struct access *model, > access->size = model->size; > access->type = model->type; > access->parent = parent; > + access->grp_read = set_grp_read; > access->grp_write = set_grp_write; > - access->grp_read = false; > access->reverse = model->reverse; > > child = &parent->first_child; > @@ -2571,16 +2658,16 @@ create_artificial_child_access (struct access *parent, struct access *model, > and has assignment links leading from it, re-enqueue it. */ > > static void > -subtree_mark_written_and_enqueue (struct access *access) > +subtree_mark_written_and_rhs_enqueue (struct access *access) > { > if (access->grp_write) > return; > access->grp_write = true; > - add_access_to_work_queue (access); > + add_access_to_rhs_work_queue (access); > > struct access *child; > for (child = access->first_child; child; child = child->next_sibling) > - subtree_mark_written_and_enqueue (child); > + subtree_mark_written_and_rhs_enqueue (child); > } > > /* Propagate subaccesses and grp_write flags of RACC across an assignment link > @@ -2590,7 +2677,7 @@ subtree_mark_written_and_enqueue (struct access *access) > possible. */ > > static bool > -propagate_subaccesses_across_link (struct access *lacc, struct access *racc) > +propagate_subaccesses_from_rhs (struct access *lacc, struct access *racc) > { > struct access *rchild; > HOST_WIDE_INT norm_delta = lacc->offset - racc->offset; > @@ -2603,7 +2690,7 @@ propagate_subaccesses_across_link (struct access *lacc, struct access *racc) > gcc_checking_assert (!comes_initialized_p (racc->base)); > if (racc->grp_write) > { > - subtree_mark_written_and_enqueue (lacc); > + subtree_mark_written_and_rhs_enqueue (lacc); > ret = true; > } > } > @@ -2615,7 +2702,7 @@ propagate_subaccesses_across_link (struct access *lacc, struct access *racc) > if (!lacc->grp_write) > { > ret = true; > - subtree_mark_written_and_enqueue (lacc); > + subtree_mark_written_and_rhs_enqueue (lacc); > } > return ret; > } > @@ -2625,7 +2712,7 @@ propagate_subaccesses_across_link (struct access *lacc, struct access *racc) > if (!lacc->grp_write) > { > ret = true; > - subtree_mark_written_and_enqueue (lacc); > + subtree_mark_written_and_rhs_enqueue (lacc); > } > if (!lacc->first_child && !racc->first_child) > { > @@ -2655,7 +2742,7 @@ propagate_subaccesses_across_link (struct access *lacc, struct access *racc) > struct access *new_acc = NULL; > HOST_WIDE_INT norm_offset = rchild->offset + norm_delta; > > - if (child_would_conflict_in_lacc (lacc, norm_offset, rchild->size, > + if (child_would_conflict_in_acc (lacc, norm_offset, rchild->size, > &new_acc)) > { > if (new_acc) > @@ -2663,17 +2750,17 @@ propagate_subaccesses_across_link (struct access *lacc, struct access *racc) > if (!new_acc->grp_write && rchild->grp_write) > { > gcc_assert (!lacc->grp_write); > - subtree_mark_written_and_enqueue (new_acc); > + subtree_mark_written_and_rhs_enqueue (new_acc); > ret = true; > } > > rchild->grp_hint = 1; > new_acc->grp_hint |= new_acc->grp_read; > if (rchild->first_child > - && propagate_subaccesses_across_link (new_acc, rchild)) > + && propagate_subaccesses_from_rhs (new_acc, rchild)) > { > ret = 1; > - add_access_to_work_queue (new_acc); > + add_access_to_rhs_work_queue (new_acc); > } > } > else > @@ -2681,7 +2768,7 @@ propagate_subaccesses_across_link (struct access *lacc, struct access *racc) > if (!lacc->grp_write) > { > ret = true; > - subtree_mark_written_and_enqueue (lacc); > + subtree_mark_written_and_rhs_enqueue (lacc); > } > } > continue; > @@ -2692,41 +2779,85 @@ propagate_subaccesses_across_link (struct access *lacc, struct access *racc) > if (rchild->grp_write && !lacc->grp_write) > { > ret = true; > - subtree_mark_written_and_enqueue (lacc); > + subtree_mark_written_and_rhs_enqueue (lacc); > } > continue; > } > > rchild->grp_hint = 1; > new_acc = create_artificial_child_access (lacc, rchild, norm_offset, > - lacc->grp_write > - || rchild->grp_write); > + false, (lacc->grp_write > + || rchild->grp_write)); > gcc_checking_assert (new_acc); > if (racc->first_child) > - propagate_subaccesses_across_link (new_acc, rchild); > + propagate_subaccesses_from_rhs (new_acc, rchild); > > - add_access_to_work_queue (lacc); > + add_access_to_rhs_work_queue (lacc); > ret = true; > } > > return ret; > } > > +/* Propagate subaccesses of LACC across an assignment link to RACC if they > + should inhibit total scalarization of the corresponding area. No flags are > + being propagated in the process. Return true if anything changed. */ > + > +static bool > +propagate_subaccesses_from_lhs (struct access *lacc, struct access *racc) > +{ > + if (is_gimple_reg_type (racc->type) > + || lacc->grp_unscalarizable_region > + || racc->grp_unscalarizable_region) > + return false; > + > + /* TODO: Do we want set some new racc flag to stop potential total > + scalarization if lacc is a scalar access (and none fo the two have > + children)? */ > + > + bool ret = false; > + HOST_WIDE_INT norm_delta = racc->offset - lacc->offset; > + for (struct access *lchild = lacc->first_child; > + lchild; > + lchild = lchild->next_sibling) > + { > + struct access *matching_acc = NULL; > + HOST_WIDE_INT norm_offset = lchild->offset + norm_delta; > + > + if (lchild->grp_unscalarizable_region > + || child_would_conflict_in_acc (racc, norm_offset, lchild->size, > + &matching_acc)) > + { > + if (matching_acc > + && propagate_subaccesses_from_lhs (lchild, matching_acc)) > + add_access_to_lhs_work_queue (matching_acc); > + continue; > + } > + > + struct access *new_acc > + = create_artificial_child_access (racc, lchild, norm_offset, > + true, false); > + propagate_subaccesses_from_lhs (lchild, new_acc); > + ret = true; > + } > + return ret; > +} > + > /* Propagate all subaccesses across assignment links. */ > > static void > propagate_all_subaccesses (void) > { > - while (work_queue_head) > + while (rhs_work_queue_head) > { > - struct access *racc = pop_access_from_work_queue (); > + struct access *racc = pop_access_from_rhs_work_queue (); > struct assign_link *link; > > if (racc->group_representative) > racc= racc->group_representative; > - gcc_assert (racc->first_link); > + gcc_assert (racc->first_rhs_link); > > - for (link = racc->first_link; link; link = link->next) > + for (link = racc->first_rhs_link; link; link = link->next_rhs) > { > struct access *lacc = link->lacc; > > @@ -2739,22 +2870,47 @@ propagate_all_subaccesses (void) > { > if (!lacc->grp_write) > { > - subtree_mark_written_and_enqueue (lacc); > + subtree_mark_written_and_rhs_enqueue (lacc); > reque_parents = true; > } > } > - else if (propagate_subaccesses_across_link (lacc, racc)) > + else if (propagate_subaccesses_from_rhs (lacc, racc)) > reque_parents = true; > > if (reque_parents) > do > { > - add_access_to_work_queue (lacc); > + add_access_to_rhs_work_queue (lacc); > lacc = lacc->parent; > } > while (lacc); > } > } > + > + while (lhs_work_queue_head) > + { > + struct access *lacc = pop_access_from_lhs_work_queue (); > + struct assign_link *link; > + > + if (lacc->group_representative) > + lacc = lacc->group_representative; > + gcc_assert (lacc->first_lhs_link); > + > + if (!bitmap_bit_p (candidate_bitmap, DECL_UID (lacc->base))) > + continue; > + > + for (link = lacc->first_lhs_link; link; link = link->next_lhs) > + { > + struct access *racc = link->racc; > + > + if (racc->group_representative) > + racc = racc->group_representative; > + if (!bitmap_bit_p (candidate_bitmap, DECL_UID (racc->base))) > + continue; > + if (propagate_subaccesses_from_lhs (lacc, racc)) > + add_access_to_lhs_work_queue (racc); > + } > + } > } > > /* Return true if the forest beginning with ROOT does not contain >
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr92706-1.c b/gcc/testsuite/gcc.dg/tree-ssa/pr92706-1.c new file mode 100644 index 00000000000..c36d103798e --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr92706-1.c @@ -0,0 +1,17 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-esra-details" } */ + +struct S { int i[4]; } __attribute__((aligned(128))); +typedef __int128_t my_int128 __attribute__((may_alias)); +__int128_t load (void *p) +{ + struct S v; + __builtin_memcpy (&v, p, sizeof (struct S)); + struct S u; + u = v; + struct S w; + w = u; + return *(my_int128 *)&w; +} + +/* { dg-final { scan-tree-dump-not "Created a replacement for u offset: \[^0\]" "esra" } } */ diff --git a/gcc/tree-sra.c b/gcc/tree-sra.c index 2b0849858de..ea8594db193 100644 --- a/gcc/tree-sra.c +++ b/gcc/tree-sra.c @@ -167,11 +167,15 @@ struct access struct access *next_sibling; /* Pointers to the first and last element in the linked list of assign - links. */ - struct assign_link *first_link, *last_link; + links for propagation from LHS to RHS. */ + struct assign_link *first_rhs_link, *last_rhs_link; - /* Pointer to the next access in the work queue. */ - struct access *next_queued; + /* Pointers to the first and last element in the linked list of assign + links for propagation from LHS to RHS. */ + struct assign_link *first_lhs_link, *last_lhs_link; + + /* Pointer to the next access in the work queues. */ + struct access *next_rhs_queued, *next_lhs_queued; /* Replacement variable for this access "region." Never to be accessed directly, always only by the means of get_access_replacement() and only @@ -184,8 +188,11 @@ struct access /* Is this particular access write access? */ unsigned write : 1; - /* Is this access currently in the work queue? */ - unsigned grp_queued : 1; + /* Is this access currently in the rhs work queue? */ + unsigned grp_rhs_queued : 1; + + /* Is this access currently in the lhs work queue? */ + unsigned grp_lhs_queued : 1; /* Does this group contain a write access? This flag is propagated down the access tree. */ @@ -262,12 +269,14 @@ typedef struct access *access_p; static object_allocator<struct access> access_pool ("SRA accesses"); /* A structure linking lhs and rhs accesses from an aggregate assignment. They - are used to propagate subaccesses from rhs to lhs as long as they don't - conflict with what is already there. */ + are used to propagate subaccesses from rhs to lhs and vice versa as long as + they don't conflict with what is already there. In the RHS->LHS direction, + we also propagate grp_write flag to lazily mark that the access contains any + meaningful data. */ struct assign_link { struct access *lacc, *racc; - struct assign_link *next; + struct assign_link *next_rhs, *next_lhs; }; /* Alloc pool for allocating assign link structures. */ @@ -327,7 +336,7 @@ static struct obstack name_obstack; /* Head of a linked list of accesses that need to have its subaccesses propagated to their assignment counterparts. */ -static struct access *work_queue_head; +static struct access *rhs_work_queue_head, *lhs_work_queue_head; /* Dump contents of ACCESS to file F in a human friendly way. If GRP is true, representative fields are dumped, otherwise those which only describe the @@ -534,79 +543,155 @@ get_var_base_offset_size_access (tree base, HOST_WIDE_INT offset, } /* Add LINK to the linked list of assign links of RACC. */ + static void add_link_to_rhs (struct access *racc, struct assign_link *link) { gcc_assert (link->racc == racc); - if (!racc->first_link) + if (!racc->first_rhs_link) { - gcc_assert (!racc->last_link); - racc->first_link = link; + gcc_assert (!racc->last_rhs_link); + racc->first_rhs_link = link; } else - racc->last_link->next = link; + racc->last_rhs_link->next_rhs = link; - racc->last_link = link; - link->next = NULL; + racc->last_rhs_link = link; + link->next_rhs = NULL; } -/* Move all link structures in their linked list in OLD_RACC to the linked list - in NEW_RACC. */ +/* Add LINK to the linked list of lhs assign links of LACC. */ + static void -relink_to_new_repr (struct access *new_racc, struct access *old_racc) +add_link_to_lhs (struct access *lacc, struct assign_link *link) { - if (!old_racc->first_link) + gcc_assert (link->lacc == lacc); + + if (!lacc->first_lhs_link) { - gcc_assert (!old_racc->last_link); - return; + gcc_assert (!lacc->last_lhs_link); + lacc->first_lhs_link = link; } + else + lacc->last_lhs_link->next_lhs = link; + + lacc->last_lhs_link = link; + link->next_lhs = NULL; +} - if (new_racc->first_link) +/* Move all link structures in their linked list in OLD_ACC to the linked list + in NEW_ACC. */ +static void +relink_to_new_repr (struct access *new_acc, struct access *old_acc) +{ + if (old_acc->first_rhs_link) { - gcc_assert (!new_racc->last_link->next); - gcc_assert (!old_racc->last_link || !old_racc->last_link->next); - new_racc->last_link->next = old_racc->first_link; - new_racc->last_link = old_racc->last_link; + if (new_acc->first_rhs_link) + { + gcc_assert (!new_acc->last_rhs_link->next_rhs); + gcc_assert (!old_acc->last_rhs_link + || !old_acc->last_rhs_link->next_rhs); + + new_acc->last_rhs_link->next_rhs = old_acc->first_rhs_link; + new_acc->last_rhs_link = old_acc->last_rhs_link; + } + else + { + gcc_assert (!new_acc->last_rhs_link); + + new_acc->first_rhs_link = old_acc->first_rhs_link; + new_acc->last_rhs_link = old_acc->last_rhs_link; + } + old_acc->first_rhs_link = old_acc->last_rhs_link = NULL; } else + gcc_assert (!old_acc->last_rhs_link); + + if (old_acc->first_lhs_link) { - gcc_assert (!new_racc->last_link); - new_racc->first_link = old_racc->first_link; - new_racc->last_link = old_racc->last_link; + if (new_acc->first_lhs_link) + { + gcc_assert (!new_acc->last_lhs_link->next_lhs); + gcc_assert (!old_acc->last_lhs_link + || !old_acc->last_lhs_link->next_lhs); + + new_acc->last_lhs_link->next_lhs = old_acc->first_lhs_link; + new_acc->last_lhs_link = old_acc->last_lhs_link; + } + else + { + gcc_assert (!new_acc->last_lhs_link); + + new_acc->first_lhs_link = old_acc->first_lhs_link; + new_acc->last_lhs_link = old_acc->last_lhs_link; + } + old_acc->first_lhs_link = old_acc->last_lhs_link = NULL; } - old_racc->first_link = old_racc->last_link = NULL; + else + gcc_assert (!old_acc->last_lhs_link); + } -/* Add ACCESS to the work queue (which is actually a stack). */ +/* Add ACCESS to the work to queue for propagation of subaccesses from RHS to + LHS (which is actually a stack). */ static void -add_access_to_work_queue (struct access *access) +add_access_to_rhs_work_queue (struct access *access) { - if (access->first_link && !access->grp_queued) + if (access->first_rhs_link && !access->grp_rhs_queued) { - gcc_assert (!access->next_queued); - access->next_queued = work_queue_head; - access->grp_queued = 1; - work_queue_head = access; + gcc_assert (!access->next_rhs_queued); + access->next_rhs_queued = rhs_work_queue_head; + access->grp_rhs_queued = 1; + rhs_work_queue_head = access; } } -/* Pop an access from the work queue, and return it, assuming there is one. */ +/* Add ACCESS to the work to queue for propagation of subaccesses from LHS to + RHS (which is actually a stack). */ + +static void +add_access_to_lhs_work_queue (struct access *access) +{ + if (access->first_lhs_link && !access->grp_lhs_queued) + { + gcc_assert (!access->next_lhs_queued); + access->next_lhs_queued = lhs_work_queue_head; + access->grp_lhs_queued = 1; + lhs_work_queue_head = access; + } +} + +/* Pop an access from the work queue for propagating from RHS to LHS, and + return it, assuming there is one. */ static struct access * -pop_access_from_work_queue (void) +pop_access_from_rhs_work_queue (void) { - struct access *access = work_queue_head; + struct access *access = rhs_work_queue_head; - work_queue_head = access->next_queued; - access->next_queued = NULL; - access->grp_queued = 0; + rhs_work_queue_head = access->next_rhs_queued; + access->next_rhs_queued = NULL; + access->grp_rhs_queued = 0; return access; } +/* Pop an access from the work queue for propagating from LHS to RHS, and + return it, assuming there is one. */ + +static struct access * +pop_access_from_lhs_work_queue (void) +{ + struct access *access = lhs_work_queue_head; + + lhs_work_queue_head = access->next_lhs_queued; + access->next_lhs_queued = NULL; + access->grp_lhs_queued = 0; + return access; +} /* Allocate necessary structures. */ @@ -1203,7 +1288,9 @@ build_accesses_from_assign (gimple *stmt) link->lacc = lacc; link->racc = racc; add_link_to_rhs (racc, link); - add_access_to_work_queue (racc); + add_link_to_lhs (lacc, link); + add_access_to_rhs_work_queue (racc); + add_access_to_lhs_work_queue (lacc); /* Let's delay marking the areas as written until propagation of accesses across link, unless the nature of rhs tells us that its data comes @@ -2492,17 +2579,17 @@ analyze_access_trees (struct access *access) return ret; } -/* Return true iff a potential new child of LACC at offset OFFSET and with size +/* Return true iff a potential new child of ACC at offset OFFSET and with size SIZE would conflict with an already existing one. If exactly such a child - already exists in LACC, store a pointer to it in EXACT_MATCH. */ + already exists in ACC, store a pointer to it in EXACT_MATCH. */ static bool -child_would_conflict_in_lacc (struct access *lacc, HOST_WIDE_INT norm_offset, +child_would_conflict_in_acc (struct access *acc, HOST_WIDE_INT norm_offset, HOST_WIDE_INT size, struct access **exact_match) { struct access *child; - for (child = lacc->first_child; child; child = child->next_sibling) + for (child = acc->first_child; child; child = child->next_sibling) { if (child->offset == norm_offset && child->size == size) { @@ -2528,7 +2615,7 @@ child_would_conflict_in_lacc (struct access *lacc, HOST_WIDE_INT norm_offset, static struct access * create_artificial_child_access (struct access *parent, struct access *model, HOST_WIDE_INT new_offset, - bool set_grp_write) + bool set_grp_read, bool set_grp_write) { struct access **child; tree expr = parent->base; @@ -2551,8 +2638,8 @@ create_artificial_child_access (struct access *parent, struct access *model, access->size = model->size; access->type = model->type; access->parent = parent; + access->grp_read = set_grp_read; access->grp_write = set_grp_write; - access->grp_read = false; access->reverse = model->reverse; child = &parent->first_child; @@ -2571,16 +2658,16 @@ create_artificial_child_access (struct access *parent, struct access *model, and has assignment links leading from it, re-enqueue it. */ static void -subtree_mark_written_and_enqueue (struct access *access) +subtree_mark_written_and_rhs_enqueue (struct access *access) { if (access->grp_write) return; access->grp_write = true; - add_access_to_work_queue (access); + add_access_to_rhs_work_queue (access); struct access *child; for (child = access->first_child; child; child = child->next_sibling) - subtree_mark_written_and_enqueue (child); + subtree_mark_written_and_rhs_enqueue (child); } /* Propagate subaccesses and grp_write flags of RACC across an assignment link @@ -2590,7 +2677,7 @@ subtree_mark_written_and_enqueue (struct access *access) possible. */ static bool -propagate_subaccesses_across_link (struct access *lacc, struct access *racc) +propagate_subaccesses_from_rhs (struct access *lacc, struct access *racc) { struct access *rchild; HOST_WIDE_INT norm_delta = lacc->offset - racc->offset; @@ -2603,7 +2690,7 @@ propagate_subaccesses_across_link (struct access *lacc, struct access *racc) gcc_checking_assert (!comes_initialized_p (racc->base)); if (racc->grp_write) { - subtree_mark_written_and_enqueue (lacc); + subtree_mark_written_and_rhs_enqueue (lacc); ret = true; } } @@ -2615,7 +2702,7 @@ propagate_subaccesses_across_link (struct access *lacc, struct access *racc) if (!lacc->grp_write) { ret = true; - subtree_mark_written_and_enqueue (lacc); + subtree_mark_written_and_rhs_enqueue (lacc); } return ret; } @@ -2625,7 +2712,7 @@ propagate_subaccesses_across_link (struct access *lacc, struct access *racc) if (!lacc->grp_write) { ret = true; - subtree_mark_written_and_enqueue (lacc); + subtree_mark_written_and_rhs_enqueue (lacc); } if (!lacc->first_child && !racc->first_child) { @@ -2655,7 +2742,7 @@ propagate_subaccesses_across_link (struct access *lacc, struct access *racc) struct access *new_acc = NULL; HOST_WIDE_INT norm_offset = rchild->offset + norm_delta; - if (child_would_conflict_in_lacc (lacc, norm_offset, rchild->size, + if (child_would_conflict_in_acc (lacc, norm_offset, rchild->size, &new_acc)) { if (new_acc) @@ -2663,17 +2750,17 @@ propagate_subaccesses_across_link (struct access *lacc, struct access *racc) if (!new_acc->grp_write && rchild->grp_write) { gcc_assert (!lacc->grp_write); - subtree_mark_written_and_enqueue (new_acc); + subtree_mark_written_and_rhs_enqueue (new_acc); ret = true; } rchild->grp_hint = 1; new_acc->grp_hint |= new_acc->grp_read; if (rchild->first_child - && propagate_subaccesses_across_link (new_acc, rchild)) + && propagate_subaccesses_from_rhs (new_acc, rchild)) { ret = 1; - add_access_to_work_queue (new_acc); + add_access_to_rhs_work_queue (new_acc); } } else @@ -2681,7 +2768,7 @@ propagate_subaccesses_across_link (struct access *lacc, struct access *racc) if (!lacc->grp_write) { ret = true; - subtree_mark_written_and_enqueue (lacc); + subtree_mark_written_and_rhs_enqueue (lacc); } } continue; @@ -2692,41 +2779,85 @@ propagate_subaccesses_across_link (struct access *lacc, struct access *racc) if (rchild->grp_write && !lacc->grp_write) { ret = true; - subtree_mark_written_and_enqueue (lacc); + subtree_mark_written_and_rhs_enqueue (lacc); } continue; } rchild->grp_hint = 1; new_acc = create_artificial_child_access (lacc, rchild, norm_offset, - lacc->grp_write - || rchild->grp_write); + false, (lacc->grp_write + || rchild->grp_write)); gcc_checking_assert (new_acc); if (racc->first_child) - propagate_subaccesses_across_link (new_acc, rchild); + propagate_subaccesses_from_rhs (new_acc, rchild); - add_access_to_work_queue (lacc); + add_access_to_rhs_work_queue (lacc); ret = true; } return ret; } +/* Propagate subaccesses of LACC across an assignment link to RACC if they + should inhibit total scalarization of the corresponding area. No flags are + being propagated in the process. Return true if anything changed. */ + +static bool +propagate_subaccesses_from_lhs (struct access *lacc, struct access *racc) +{ + if (is_gimple_reg_type (racc->type) + || lacc->grp_unscalarizable_region + || racc->grp_unscalarizable_region) + return false; + + /* TODO: Do we want set some new racc flag to stop potential total + scalarization if lacc is a scalar access (and none fo the two have + children)? */ + + bool ret = false; + HOST_WIDE_INT norm_delta = racc->offset - lacc->offset; + for (struct access *lchild = lacc->first_child; + lchild; + lchild = lchild->next_sibling) + { + struct access *matching_acc = NULL; + HOST_WIDE_INT norm_offset = lchild->offset + norm_delta; + + if (lchild->grp_unscalarizable_region + || child_would_conflict_in_acc (racc, norm_offset, lchild->size, + &matching_acc)) + { + if (matching_acc + && propagate_subaccesses_from_lhs (lchild, matching_acc)) + add_access_to_lhs_work_queue (matching_acc); + continue; + } + + struct access *new_acc + = create_artificial_child_access (racc, lchild, norm_offset, + true, false); + propagate_subaccesses_from_lhs (lchild, new_acc); + ret = true; + } + return ret; +} + /* Propagate all subaccesses across assignment links. */ static void propagate_all_subaccesses (void) { - while (work_queue_head) + while (rhs_work_queue_head) { - struct access *racc = pop_access_from_work_queue (); + struct access *racc = pop_access_from_rhs_work_queue (); struct assign_link *link; if (racc->group_representative) racc= racc->group_representative; - gcc_assert (racc->first_link); + gcc_assert (racc->first_rhs_link); - for (link = racc->first_link; link; link = link->next) + for (link = racc->first_rhs_link; link; link = link->next_rhs) { struct access *lacc = link->lacc; @@ -2739,22 +2870,47 @@ propagate_all_subaccesses (void) { if (!lacc->grp_write) { - subtree_mark_written_and_enqueue (lacc); + subtree_mark_written_and_rhs_enqueue (lacc); reque_parents = true; } } - else if (propagate_subaccesses_across_link (lacc, racc)) + else if (propagate_subaccesses_from_rhs (lacc, racc)) reque_parents = true; if (reque_parents) do { - add_access_to_work_queue (lacc); + add_access_to_rhs_work_queue (lacc); lacc = lacc->parent; } while (lacc); } } + + while (lhs_work_queue_head) + { + struct access *lacc = pop_access_from_lhs_work_queue (); + struct assign_link *link; + + if (lacc->group_representative) + lacc = lacc->group_representative; + gcc_assert (lacc->first_lhs_link); + + if (!bitmap_bit_p (candidate_bitmap, DECL_UID (lacc->base))) + continue; + + for (link = lacc->first_lhs_link; link; link = link->next_lhs) + { + struct access *racc = link->racc; + + if (racc->group_representative) + racc = racc->group_representative; + if (!bitmap_bit_p (candidate_bitmap, DECL_UID (racc->base))) + continue; + if (propagate_subaccesses_from_lhs (lacc, racc)) + add_access_to_lhs_work_queue (racc); + } + } } /* Return true if the forest beginning with ROOT does not contain