Re: [PATCH] tree-optimization/111807 - ICE in verify_sra_access_forest

Re: [PATCH] tree-optimization/111807 - ICE in verify_sra_access_forest

[Martin Jambor]

Hi,

sorry for getting to this only so late, my email backlog from my medical
leave still isn't empty.

On Mon, Oct 16 2023, Richard Biener wrote:
> The following addresses build_reconstructed_reference failing to
> build references with a different offset than the models and thus
> the caller conditional being off.  This manifests when attempting
> to build a ref with offset 160 from the model BIT_FIELD_REF <l_4827[9], 8, 0>
> onto the same base l_4827 but the models offset being 288.  This
> cannot work for any kind of ref I can think of, not just with
> BIT_FIELD_REFs.
>
> Bootstrapped and tested on x86_64-unknown-linux-gnu, will push
> later.
>
> Martin - do you remember which case was supposed to be allowed
> with offset < model->offset?
>

It happens quite often, even in our testsuite.  In fact, the condition
is not even supposed to be necessary and is there just an early exit in
hopeless cases with malformed programs.

The problem is that the function is used in two contexts and in one of
them we are not careful about ARRAY_REFs, as explained below in a commit
message of a patch I'd like to push.  Needless to say, it has passed
bootstrap and testing on x86_64-linux, I'm running the same on
aarch64-linux.

What do you think?

Martin



Subject: [PATCH] SRA: Relax requirements to use build_reconstructed_reference (PR 111807)

This patch half-reverts 3aaf704bca3e and replaces it with a fix with
relaxed requiremets for invoking build_reconstructed_reference in
build_ref_for_model.

build_ref_for_model/build_ref_for_offset is used in two slightly
different contexts. The first is when we are looking at an assignment
like

   p->field_A.field_B = s.field_B;

and we have a replacements for e.g. s.field_B.field_C.field_D and we
want to store them directly to p->field_A.field_B.field_C.field_D (as
opposed to going through s or using a MEM_REF based in
p->field_A.field_B).  In this case, the offset of the
"model" (s.field_B.field_C.field_D) within this can be different than
offset within the LHS that we want to reach (field_C.field_D within
the "base" p->field_A.field_B).  Patch 3aaf704bca3e has caused us to
unnecessarily create MEM_REFs for these situations.  These uses of
build_ref_for_model work with the relaxed condition just fine.

The second, problematic, context is when somewhere in the function we
have an assignment

  s.field_A = t.field_A.field_B;

and we are creating an access structure to represent s.field_A.field_B
even if it is not actually accessed in the original input.  This is
done after scanning the entire function body and we need to construct
a "universal" reference to s.field_A.field_B.  In this case the "base"
is "s" and it has to be the DECL itself and not some reference for it
because for arbitrary references we need a GSI pointing to a statement
which we don't have, the reference is supposed to be universal.

But then using build_ref_for_model and within it
build_reconstructed_reference misbehaves if the expression contains
any ARRAY_REFs.  In the first case those are fine because as we
eventually reach the aggregate type that matches a real LHS or RHS, we
know we we can just bolt the rest of the references onto it and end up
with the correct overall reference.  However when dealing with

   s.array[1].field_A = s.array[2].field_B;

we cannot just bolt array[2] reference when we want array[1] but that
is exactly what happens when we use build_reconstructed_reference and
keep it walking all the way to s.

I was considering making all users of the second kind use directly
build_ref_for_offset instead of build_ref_for_model but the latter
also handles COMPONENT_REFs to bit-fields which the former does not.
Therefore I have decided to use the NULL-ness of GSI as an indicator
how strict we need to be.  I have changed the function comment to
reflect that.

I have been able to observe disambiguation improvements with this patch
over current master, we do successfully manage a few more
aliasing_component_refs_p disambiguations when compiling cc1, going
from:

  Alias oracle query stats:
    refs_may_alias_p: 94354287 disambiguations, 106279231 queries
    ref_maybe_used_by_call_p: 1572511 disambiguations, 95618222 queries
    call_may_clobber_ref_p: 649273 disambiguations, 659371 queries
    stmt_kills_ref_p: 142342 kills, 8407309 queries
    nonoverlapping_component_refs_p: 19 disambiguations, 10227 queries
    nonoverlapping_refs_since_match_p: 15665 disambiguations, 52585 must overlaps, 68893 queries
    aliasing_component_refs_p: 67090 disambiguations, 3081766 queries
    TBAA oracle: 22675296 disambiguations 61781978 queries
                 14045969 are in alias set 0
                 10997085 queries asked about the same object
                 153 queries asked about the same alias set
                 0 access volatile
                 12485774 are dependent in the DAG
                 1577701 are aritificially in conflict with void *

  Modref stats:
    modref kill: 832 kills, 19399 queries
    modref use: 50760 disambiguations, 1825109 queries
    modref clobber: 1371014 disambiguations, 40152535 queries
    5190238 tbaa queries (0.129263 per modref query)
    1341663 base compares (0.033414 per modref query)

  PTA query stats:
    pt_solution_includes: 36784427 disambiguations, 46141175 queries
    pt_solutions_intersect: 4519387 disambiguations, 17081996 queries

to:

  Alias oracle query stats:
    refs_may_alias_p: 94354083 disambiguations, 106278948 queries
    ref_maybe_used_by_call_p: 1572511 disambiguations, 95618018 queries
    call_may_clobber_ref_p: 649273 disambiguations, 659371 queries
    stmt_kills_ref_p: 142342 kills, 8407310 queries
    nonoverlapping_component_refs_p: 19 disambiguations, 10227 queries
    nonoverlapping_refs_since_match_p: 15665 disambiguations, 52585 must overlaps, 68893 queries
    aliasing_component_refs_p: 67104 disambiguations, 3081781 queries
    TBAA oracle: 22676608 disambiguations 61782455 queries
                 14044948 are in alias set 0
                 10998619 queries asked about the same object
                 153 queries asked about the same alias set
                 0 access volatile
                 12484882 are dependent in the DAG
                 1577245 are aritificially in conflict with void *

  Modref stats:
    modref kill: 832 kills, 19399 queries
    modref use: 50760 disambiguations, 1825106 queries
    modref clobber: 1371028 disambiguations, 40152504 queries
    5190319 tbaa queries (0.129265 per modref query)
    1341403 base compares (0.033408 per modref query)

  PTA query stats:
    pt_solution_includes: 36784449 disambiguations, 46141210 queries
    pt_solutions_intersect: 4519320 disambiguations, 17082083 queries

gcc/ChangeLog:

2023-12-13  Martin Jambor  <mjambor@suse.cz>

	PR tree-optimization/111807
	* tree-sra.cc (build_ref_for_model): Allow offset smaller than
	model->offset when gsi is non-NULL.  Adjust function comment.
---
 gcc/tree-sra.cc | 10 +++++++---
 1 file changed, 7 insertions(+), 3 deletions(-)

diff --git a/gcc/tree-sra.cc b/gcc/tree-sra.cc
index 3bd0c7a9af0..1dba721be11 100644
--- a/gcc/tree-sra.cc
+++ b/gcc/tree-sra.cc
@@ -1843,8 +1843,11 @@ build_reconstructed_reference (location_t, tree base, struct access *model)
 /* Construct a memory reference to a part of an aggregate BASE at the given
    OFFSET and of the same type as MODEL.  In case this is a reference to a
    bit-field, the function will replicate the last component_ref of model's
-   expr to access it.  GSI and INSERT_AFTER have the same meaning as in
-   build_ref_for_offset.  */
+   expr to access it.  INSERT_AFTER and GSI have the same meaning as in
+   build_ref_for_offset, furthermore, when GSI is NULL, the function expects
+   that it re-builds the entire reference from a DECL to the final access and
+   so will create a MEM_REF when OFFSET does not exactly match offset of
+   MODEL.  */
 
 static tree
 build_ref_for_model (location_t loc, tree base, HOST_WIDE_INT offset,
@@ -1874,7 +1877,8 @@ build_ref_for_model (location_t loc, tree base, HOST_WIDE_INT offset,
 	  && !TREE_THIS_VOLATILE (base)
 	  && (TYPE_ADDR_SPACE (TREE_TYPE (base))
 	      == TYPE_ADDR_SPACE (TREE_TYPE (model->expr)))
-	  && offset == model->offset
+	  && (offset == model->offset
+	      || (gsi && offset <= model->offset))
 	  /* build_reconstructed_reference can still fail if we have already
 	     massaged BASE because of another type incompatibility.  */
 	  && (res = build_reconstructed_reference (loc, base, model)))
-- 
2.43.0

Re: [PATCH] tree-optimization/111807 - ICE in verify_sra_access_forest

[Richard Biener]

> Am 13.12.2023 um 17:07 schrieb Martin Jambor <mjambor@suse.cz>:
> 
> Hi,
> 
> sorry for getting to this only so late, my email backlog from my medical
> leave still isn't empty.
> 
>> On Mon, Oct 16 2023, Richard Biener wrote:
>> The following addresses build_reconstructed_reference failing to
>> build references with a different offset than the models and thus
>> the caller conditional being off.  This manifests when attempting
>> to build a ref with offset 160 from the model BIT_FIELD_REF <l_4827[9], 8, 0>
>> onto the same base l_4827 but the models offset being 288.  This
>> cannot work for any kind of ref I can think of, not just with
>> BIT_FIELD_REFs.
>> 
>> Bootstrapped and tested on x86_64-unknown-linux-gnu, will push
>> later.
>> 
>> Martin - do you remember which case was supposed to be allowed
>> with offset < model->offset?
>> 
> 
> It happens quite often, even in our testsuite.  In fact, the condition
> is not even supposed to be necessary and is there just an early exit in
> hopeless cases with malformed programs.
> 
> The problem is that the function is used in two contexts and in one of
> them we are not careful about ARRAY_REFs, as explained below in a commit
> message of a patch I'd like to push.  Needless to say, it has passed
> bootstrap and testing on x86_64-linux, I'm running the same on
> aarch64-linux.
> 
> What do you think

Thanks for the explanation. This wasn’t obvious.  The patch is OK from my side.

Thanks,
Richard 


> Martin
> 
> 
> 
> Subject: [PATCH] SRA: Relax requirements to use build_reconstructed_reference (PR 111807)
> 
> This patch half-reverts 3aaf704bca3e and replaces it with a fix with
> relaxed requiremets for invoking build_reconstructed_reference in
> build_ref_for_model.
> 
> build_ref_for_model/build_ref_for_offset is used in two slightly
> different contexts. The first is when we are looking at an assignment
> like
> 
>   p->field_A.field_B = s.field_B;
> 
> and we have a replacements for e.g. s.field_B.field_C.field_D and we
> want to store them directly to p->field_A.field_B.field_C.field_D (as
> opposed to going through s or using a MEM_REF based in
> p->field_A.field_B).  In this case, the offset of the
> "model" (s.field_B.field_C.field_D) within this can be different than
> offset within the LHS that we want to reach (field_C.field_D within
> the "base" p->field_A.field_B).  Patch 3aaf704bca3e has caused us to
> unnecessarily create MEM_REFs for these situations.  These uses of
> build_ref_for_model work with the relaxed condition just fine.
> 
> The second, problematic, context is when somewhere in the function we
> have an assignment
> 
>  s.field_A = t.field_A.field_B;
> 
> and we are creating an access structure to represent s.field_A.field_B
> even if it is not actually accessed in the original input.  This is
> done after scanning the entire function body and we need to construct
> a "universal" reference to s.field_A.field_B.  In this case the "base"
> is "s" and it has to be the DECL itself and not some reference for it
> because for arbitrary references we need a GSI pointing to a statement
> which we don't have, the reference is supposed to be universal.
> 
> But then using build_ref_for_model and within it
> build_reconstructed_reference misbehaves if the expression contains
> any ARRAY_REFs.  In the first case those are fine because as we
> eventually reach the aggregate type that matches a real LHS or RHS, we
> know we we can just bolt the rest of the references onto it and end up
> with the correct overall reference.  However when dealing with
> 
>   s.array[1].field_A = s.array[2].field_B;
> 
> we cannot just bolt array[2] reference when we want array[1] but that
> is exactly what happens when we use build_reconstructed_reference and
> keep it walking all the way to s.
> 
> I was considering making all users of the second kind use directly
> build_ref_for_offset instead of build_ref_for_model but the latter
> also handles COMPONENT_REFs to bit-fields which the former does not.
> Therefore I have decided to use the NULL-ness of GSI as an indicator
> how strict we need to be.  I have changed the function comment to
> reflect that.
> 
> I have been able to observe disambiguation improvements with this patch
> over current master, we do successfully manage a few more
> aliasing_component_refs_p disambiguations when compiling cc1, going
> from:
> 
>  Alias oracle query stats:
>    refs_may_alias_p: 94354287 disambiguations, 106279231 queries
>    ref_maybe_used_by_call_p: 1572511 disambiguations, 95618222 queries
>    call_may_clobber_ref_p: 649273 disambiguations, 659371 queries
>    stmt_kills_ref_p: 142342 kills, 8407309 queries
>    nonoverlapping_component_refs_p: 19 disambiguations, 10227 queries
>    nonoverlapping_refs_since_match_p: 15665 disambiguations, 52585 must overlaps, 68893 queries
>    aliasing_component_refs_p: 67090 disambiguations, 3081766 queries
>    TBAA oracle: 22675296 disambiguations 61781978 queries
>                 14045969 are in alias set 0
>                 10997085 queries asked about the same object
>                 153 queries asked about the same alias set
>                 0 access volatile
>                 12485774 are dependent in the DAG
>                 1577701 are aritificially in conflict with void *
> 
>  Modref stats:
>    modref kill: 832 kills, 19399 queries
>    modref use: 50760 disambiguations, 1825109 queries
>    modref clobber: 1371014 disambiguations, 40152535 queries
>    5190238 tbaa queries (0.129263 per modref query)
>    1341663 base compares (0.033414 per modref query)
> 
>  PTA query stats:
>    pt_solution_includes: 36784427 disambiguations, 46141175 queries
>    pt_solutions_intersect: 4519387 disambiguations, 17081996 queries
> 
> to:
> 
>  Alias oracle query stats:
>    refs_may_alias_p: 94354083 disambiguations, 106278948 queries
>    ref_maybe_used_by_call_p: 1572511 disambiguations, 95618018 queries
>    call_may_clobber_ref_p: 649273 disambiguations, 659371 queries
>    stmt_kills_ref_p: 142342 kills, 8407310 queries
>    nonoverlapping_component_refs_p: 19 disambiguations, 10227 queries
>    nonoverlapping_refs_since_match_p: 15665 disambiguations, 52585 must overlaps, 68893 queries
>    aliasing_component_refs_p: 67104 disambiguations, 3081781 queries
>    TBAA oracle: 22676608 disambiguations 61782455 queries
>                 14044948 are in alias set 0
>                 10998619 queries asked about the same object
>                 153 queries asked about the same alias set
>                 0 access volatile
>                 12484882 are dependent in the DAG
>                 1577245 are aritificially in conflict with void *
> 
>  Modref stats:
>    modref kill: 832 kills, 19399 queries
>    modref use: 50760 disambiguations, 1825106 queries
>    modref clobber: 1371028 disambiguations, 40152504 queries
>    5190319 tbaa queries (0.129265 per modref query)
>    1341403 base compares (0.033408 per modref query)
> 
>  PTA query stats:
>    pt_solution_includes: 36784449 disambiguations, 46141210 queries
>    pt_solutions_intersect: 4519320 disambiguations, 17082083 queries
> 
> gcc/ChangeLog:
> 
> 2023-12-13  Martin Jambor  <mjambor@suse.cz>
> 
>    PR tree-optimization/111807
>    * tree-sra.cc (build_ref_for_model): Allow offset smaller than
>    model->offset when gsi is non-NULL.  Adjust function comment.
> ---
> gcc/tree-sra.cc | 10 +++++++---
> 1 file changed, 7 insertions(+), 3 deletions(-)
> 
> diff --git a/gcc/tree-sra.cc b/gcc/tree-sra.cc
> index 3bd0c7a9af0..1dba721be11 100644
> --- a/gcc/tree-sra.cc
> +++ b/gcc/tree-sra.cc
> @@ -1843,8 +1843,11 @@ build_reconstructed_reference (location_t, tree base, struct access *model)
> /* Construct a memory reference to a part of an aggregate BASE at the given
>    OFFSET and of the same type as MODEL.  In case this is a reference to a
>    bit-field, the function will replicate the last component_ref of model's
> -   expr to access it.  GSI and INSERT_AFTER have the same meaning as in
> -   build_ref_for_offset.  */
> +   expr to access it.  INSERT_AFTER and GSI have the same meaning as in
> +   build_ref_for_offset, furthermore, when GSI is NULL, the function expects
> +   that it re-builds the entire reference from a DECL to the final access and
> +   so will create a MEM_REF when OFFSET does not exactly match offset of
> +   MODEL.  */
> 
> static tree
> build_ref_for_model (location_t loc, tree base, HOST_WIDE_INT offset,
> @@ -1874,7 +1877,8 @@ build_ref_for_model (location_t loc, tree base, HOST_WIDE_INT offset,
>      && !TREE_THIS_VOLATILE (base)
>      && (TYPE_ADDR_SPACE (TREE_TYPE (base))
>          == TYPE_ADDR_SPACE (TREE_TYPE (model->expr)))
> -      && offset == model->offset
> +      && (offset == model->offset
> +          || (gsi && offset <= model->offset))
>      /* build_reconstructed_reference can still fail if we have already
>         massaged BASE because of another type incompatibility.  */
>      && (res = build_reconstructed_reference (loc, base, model)))
> --
> 2.43.0
> 
> 
> 
> 
> 

[PATCH] tree-optimization/111807 - ICE in verify_sra_access_forest

[Richard Biener]

The following addresses build_reconstructed_reference failing to
build references with a different offset than the models and thus
the caller conditional being off.  This manifests when attempting
to build a ref with offset 160 from the model BIT_FIELD_REF <l_4827[9], 8, 0>
onto the same base l_4827 but the models offset being 288.  This
cannot work for any kind of ref I can think of, not just with
BIT_FIELD_REFs.

Bootstrapped and tested on x86_64-unknown-linux-gnu, will push
later.

Martin - do you remember which case was supposed to be allowed
with offset < model->offset?

Thanks,
Richard.

	PR tree-optimization/111807
	* tree-sra.cc (build_ref_for_model): Only call
	build_reconstructed_reference when the offsets are the same.

	* gcc.dg/torture/pr111807.c: New testcase.
---
 gcc/testsuite/gcc.dg/torture/pr111807.c | 12 ++++++++++++
 gcc/tree-sra.cc                         |  2 +-
 2 files changed, 13 insertions(+), 1 deletion(-)
 create mode 100644 gcc/testsuite/gcc.dg/torture/pr111807.c

diff --git a/gcc/testsuite/gcc.dg/torture/pr111807.c b/gcc/testsuite/gcc.dg/torture/pr111807.c
new file mode 100644
index 00000000000..09fbdcfb667
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/torture/pr111807.c
@@ -0,0 +1,12 @@
+/* { dg-do compile } */
+
+static struct A {
+  int x : 4;
+} a;
+static int b;
+int main()
+{
+  struct A t[2];
+  t[0] = b ? t[1] : a;
+  return (b ? t[1].x : 0) && 1;
+}
diff --git a/gcc/tree-sra.cc b/gcc/tree-sra.cc
index 24d0c20da6a..f8dff8b27d7 100644
--- a/gcc/tree-sra.cc
+++ b/gcc/tree-sra.cc
@@ -1751,7 +1751,7 @@ build_ref_for_model (location_t loc, tree base, HOST_WIDE_INT offset,
 	  && !TREE_THIS_VOLATILE (base)
 	  && (TYPE_ADDR_SPACE (TREE_TYPE (base))
 	      == TYPE_ADDR_SPACE (TREE_TYPE (model->expr)))
-	  && offset <= model->offset
+	  && offset == model->offset
 	  /* build_reconstructed_reference can still fail if we have already
 	     massaged BASE because of another type incompatibility.  */
 	  && (res = build_reconstructed_reference (loc, base, model)))
-- 
2.35.3