[PATCH] tree: Fix up save_expr [PR52339]
Hi! As mentioned in the PR, save_expr seems to be very optimistic when some expression is invariant, which can result in various wrong-code issues. The problem is with the TREE_READONLY (t) && !TREE_SIDE_EFFECTS (t) case in tree_invariant_p_1. TREE_READONLY (t) in that case says that the object shouldn't be modified during its lifetime and !TREE_SIDE_EFFECTS (t) that it can be evaluated safely multiple times, but that doesn't mean we can avoid wrapping the expression into SAVE_EXPR say for a TREE_READONLY COMPONENT_REF with INDIRECT_REF as first operand - either the lifetime of the TREE_READONLY object could end earlier than when we need to reevaluate the object (that happens in the pr52339-1.c case where save_expr is called on p->a and then free (p) is done or pr52339.C where delete a->b when calling ~B () dtor deallocates a), or e.g. the pointer could change as in pr52339-2.c (so evaluating p->a again after ++p yields a possibly different value than originally and again we need a SAVE_EXPR). Attached are two patches which fix this, unfortunately both regress FAIL: gnat.dg/loop_optimization21.adb scan-tree-dump-times optimized "Index_Check" 1 FAIL: gnat.dg/vect1.adb scan-tree-dump-times vect "vectorized 1 loops" 15 FAIL: gnat.dg/vect2.adb scan-tree-dump-times vect "vectorized 1 loops" 15 FAIL: gnat.dg/vect3.adb scan-tree-dump-times vect "vectorized 1 loops" 15 FAIL: gnat.dg/vect4.adb scan-tree-dump-times vect "vectorized 1 loops" 15 FAIL: gnat.dg/vect5.adb scan-tree-dump-times vect "vectorized 1 loops" 15 FAIL: gnat.dg/vect6.adb scan-tree-dump-times vect "vectorized 1 loops" 15 on x86_64-linux (the first scan triggers 2 times rather than once, the next 3 13 times rather than 15 and the last 3 14 times rather than 15 times). The first patch has been otherwise successfully bootstrapped/regtested on x86_64-linux and i686-linux (with that above regressions), the second one is probably better but has been so far tested just on the new testcases and verified to also cause the above Ada regressions. Ok for trunk (which version), what to do about the regressions, shall we just adjust the expected counts or something else? E.g. in the vect6.adb case it is the procedure Add (X : Varray; Y : Long_Float; R : out Varray) is begin for I in X'Range loop R(I) := X(I) + Y; end loop; end; function that is no longer vectorized. Both patches lead to lots of former r.P_BOUNDS->LB0 r.P_BOUNDS->UB0 x.P_BOUNDS->LB0 x.P_BOUNDS->UB0 expressions to be wrapped into SAVE_EXPRs. Jakub 2023-05-05 Jakub Jelinek PR c++/52339 * tree.cc (tree_invariant_p_2): New function, copied from tree_invariant_p. (contains_indirect_refs): New function. (tree_invariant_p): Rewritten as wrapper around tree_invariant_p_2. Return false if expression contains INDIRECT_REFs or MEM_REFs which actually dereference some pointer. (save_expr): Use SAVE_EXPR if tree_invariant_p_1 expression contains INDIRECT_REFs or MEM_REfs which actually dereference some pointer. (skip_simple_arithmetic): Use tree_invariant_p_2 instead of tree_invariant_p. * g++.dg/opt/pr52339.C: New test. * gcc.c-torture/execute/pr52339-1.c: New test. * gcc.c-torture/execute/pr52339-2.c: New test. --- gcc/tree.cc.jj 2023-05-01 09:59:46.686293833 +0200 +++ gcc/tree.cc 2023-05-04 15:40:58.684762277 +0200 @@ -3920,13 +3920,43 @@ tree_invariant_p_1 (tree t) /* Return true if T is function-invariant. */ -bool -tree_invariant_p (tree t) +static bool +tree_invariant_p_2 (tree t) { tree inner = skip_simple_arithmetic (t); return tree_invariant_p_1 (inner); } +/* Return non-NULL if *TP is INDIRECT_REF or MEM_REF with first operand + other than address of a decl. */ + +static tree +contains_indirect_refs (tree *tp, int *, void *) +{ + tree t = *tp; + if (TREE_CODE (t) == INDIRECT_REF) +return t; + else if (TREE_CODE (t) == MEM_REF + && (TREE_CODE (TREE_OPERAND (t, 0)) != ADDR_EXPR + || !DECL_P (TREE_OPERAND (TREE_OPERAND (t, 0), 0 +return t; + else +return NULL_TREE; +} + +/* Return true if T is function-invariant. Return false for expressions + containing pointer/reference dereferences. */ + +bool +tree_invariant_p (tree t) +{ + if (!tree_invariant_p_2 (t)) +return false; + return (TREE_CONSTANT (t) + || !walk_tree_without_duplicates (&t, contains_indirect_refs, + NULL)); +} + /* Wrap a SAVE_EXPR around EXPR, if appropriate. Do this to any expression which may be used in more than one place, but must be evaluated only once. @@ -3963,7 +3993,13 @@ save_expr (tree expr) if (TREE_CODE (inner) == ERROR_MARK) return inner; - if (tree_invariant_p_1 (inner)) + if (tree_invariant_p_1 (inner) + && (TREE_CONSTANT (expr) + /* Use SAVE_EXPR if there are any pointer dereferences, evaluating +
Re: [PATCH] tree: Fix up save_expr [PR52339]
On 5/13/23 06:58, Eric Botcazou wrote: I think we really need Eric (as one who e.g. introduced the DECL_INVARIANT_P apparently for this kind of stuff) to have a look at that on the Ada side. I have been investigating this for a few days and it's no small change for Ada and probably for other languages with dynamic types. SAVE_EXPRs are delicate to handle because 1) they are TREE_SIDE_EFFECTS (it's explained in save_expr) so out of TREE_READONLY && !TREE_SIDE_EFFECTS trees, you now get side effects which then propagate to all parent nodes Hmm, interesting point. The C++ front-end often explicitly creates a temporary with a TARGET_EXPR rather than SAVE_EXPR, and then later refers to just the variable; this avoids spreading TREE_SIDE_EFFECTS around, though it wasn't done for that reason. 2) their placement is problematic in conditional expressions, for example if you replace cond > 0 ? A : A + 1 with cond > 0 ? SAVE_EXPR (A) : SAVE_EXPR (A) + 1 then gimplification will, say, create the temporary and initialize it in the first arm so, if at runtime you take the second arm, you'll read the temporary uninitialized. Absolutely, you shouldn't have the same SAVE_EXPR on two sides of a ?: without also evaluating it in the condition (or earlier). But that's already true for cases that already aren't invariant, so I'm surprised that this change would cause new problems of this sort. That's caught for scalar values by the SSA form (if your patch is applied to a GCC 12 tree, you'll get ICEs in the ACATS testsuite because of this through finalize_type_size -> variable_size -> save_expr, it is probably mitigated/addressed in GCC 14 by 68e0063397ba820e71adc220b2da0581dce29ffa). That's also why making gnat_invariant_expr return (some of) them does not look really safe. In addition to this, in Ada we have bounds of unconstrained arrays which are both read-only and stored indirectly, i.e. you have an INDIRECT_REF in the tree (it is marked TREE_THIS_NOTRAP because the bounds are always present), and which obviously play a crucial role in loops running over the arrays. This issue is responsible for the regressions in the gnat.dg testsuite. We want to be able to treat such things as invariant somehow even if we can't do that for references to user data that might be changed by intervening code. That is, indicate that we know that the _REF actually refers to a const variable or is otherwise known to be unchanging. Perhaps that should be a new flag that tree_invariant_p can check instead of TREE_READONLY. Jason
Re: [PATCH] tree: Fix up save_expr [PR52339]
> We want to be able to treat such things as invariant somehow even if we > can't do that for references to user data that might be changed by > intervening code. > > That is, indicate that we know that the _REF actually refers to a const > variable or is otherwise known to be unchanging. > > Perhaps that should be a new flag that tree_invariant_p can check > instead of TREE_READONLY. Richard earlier suggested a langhook; given that Ada will be the main (sole?) user of it, this would probably be better. -- Eric Botcazou
Re: [PATCH] tree: Fix up save_expr [PR52339]
On Tue, May 30, 2023 at 10:03:05AM +0200, Eric Botcazou wrote: > > We want to be able to treat such things as invariant somehow even if we > > can't do that for references to user data that might be changed by > > intervening code. > > > > That is, indicate that we know that the _REF actually refers to a const > > variable or is otherwise known to be unchanging. > > > > Perhaps that should be a new flag that tree_invariant_p can check > > instead of TREE_READONLY. > > Richard earlier suggested a langhook; given that Ada will be the main (sole?) > user of it, this would probably be better. Are the DECL_INVARIANT_P FIELD_DECLs in Ada really invariant no matter how exactly they are accessed? Or can Ada suffer from the same problem as C/C++, where the FIELD_DECL is TREE_READONLY, but could go out of scope or a pointer to it could change. I mean the p->fld cases in C/C++, where there could be free (p); or p++ etc. in between the place where save_expr is first evaluated and later uses? Jakub
Re: [PATCH] tree: Fix up save_expr [PR52339]
On 5/30/23 04:23, Jakub Jelinek wrote: On Tue, May 30, 2023 at 10:03:05AM +0200, Eric Botcazou wrote: We want to be able to treat such things as invariant somehow even if we can't do that for references to user data that might be changed by intervening code. That is, indicate that we know that the _REF actually refers to a const variable or is otherwise known to be unchanging. Perhaps that should be a new flag that tree_invariant_p can check instead of TREE_READONLY. Richard earlier suggested a langhook; given that Ada will be the main (sole?) user of it, this would probably be better. Are the DECL_INVARIANT_P FIELD_DECLs in Ada really invariant no matter how exactly they are accessed? Or can Ada suffer from the same problem as C/C++, where the FIELD_DECL is TREE_READONLY, but could go out of scope or a pointer to it could change. I mean the p->fld cases in C/C++, where there could be free (p); or p++ etc. in between the place where save_expr is first evaluated and later uses? Note that it is fine to treat p->fld as invariant in C++ if fld is TREE_READONLY and p is itself invariant. The implementation is allowed to assume that other code didn't destroy *p and create a new object with a different value of p in the same location under https://eel.is/c++draft/basic.memobj#basic.life-8.3 Are the Ada references to VLA bounds represented that way? Jason
Re: [PATCH] tree: Fix up save_expr [PR52339]
On Tue, May 30, 2023 at 04:36:34PM -0400, Jason Merrill wrote: > Note that it is fine to treat p->fld as invariant in C++ if fld is > TREE_READONLY and p is itself invariant. The implementation is allowed to > assume that other code didn't destroy *p and create a new object with a > different value of p in the same location under > https://eel.is/c++draft/basic.memobj#basic.life-8.3 You mean #include struct S { const int fld; S (int x) : fld (x) {} }; int foo (S *p) { int a[p->fld]; delete p; return sizeof (a); } is invalid (sure, VLA is an extension)? Jakub
Re: [PATCH] tree: Fix up save_expr [PR52339]
On 5/30/23 16:51, Jakub Jelinek wrote: On Tue, May 30, 2023 at 04:36:34PM -0400, Jason Merrill wrote: Note that it is fine to treat p->fld as invariant in C++ if fld is TREE_READONLY and p is itself invariant. The implementation is allowed to assume that other code didn't destroy *p and create a new object with a different value of p in the same location under https://eel.is/c++draft/basic.memobj#basic.life-8.3 You mean #include struct S { const int fld; S (int x) : fld (x) {} }; int foo (S *p) { int a[p->fld]; delete p; return sizeof (a); } is invalid (sure, VLA is an extension)? Good point, no, I would expect that to work, since the user didn't actually write p->fld again. Jason
Re: [PATCH] tree: Fix up save_expr [PR52339]
On Fri, May 05, 2023 at 11:04:09AM +0200, Jakub Jelinek via Gcc-patches wrote: > As mentioned in the PR, save_expr seems to be very optimistic when > some expression is invariant, which can result in various wrong-code > issues. > The problem is with the TREE_READONLY (t) && !TREE_SIDE_EFFECTS (t) > case in tree_invariant_p_1. TREE_READONLY (t) in that case says > that the object shouldn't be modified during its lifetime and > !TREE_SIDE_EFFECTS (t) that it can be evaluated safely multiple times, > but that doesn't mean we can avoid wrapping the expression into SAVE_EXPR > say for a TREE_READONLY COMPONENT_REF with INDIRECT_REF as first operand > - either the lifetime of the TREE_READONLY object could end earlier than > when we need to reevaluate the object (that happens in the > pr52339-1.c case where save_expr is called on p->a and then free (p) is > done or pr52339.C where delete a->b when calling ~B () dtor deallocates a), > or e.g. the pointer could change as in pr52339-2.c (so evaluating p->a again > after ++p yields a possibly different value than originally and again we need > a SAVE_EXPR). > > Attached are two patches which fix this, unfortunately both regress > FAIL: gnat.dg/loop_optimization21.adb scan-tree-dump-times optimized > "Index_Check" 1 > FAIL: gnat.dg/vect1.adb scan-tree-dump-times vect "vectorized 1 loops" 15 > FAIL: gnat.dg/vect2.adb scan-tree-dump-times vect "vectorized 1 loops" 15 > FAIL: gnat.dg/vect3.adb scan-tree-dump-times vect "vectorized 1 loops" 15 > FAIL: gnat.dg/vect4.adb scan-tree-dump-times vect "vectorized 1 loops" 15 > FAIL: gnat.dg/vect5.adb scan-tree-dump-times vect "vectorized 1 loops" 15 > FAIL: gnat.dg/vect6.adb scan-tree-dump-times vect "vectorized 1 loops" 15 > on x86_64-linux (the first scan triggers 2 times rather than once, > the next 3 13 times rather than 15 and the last 3 14 times rather than 15 > times). > The first patch has been otherwise successfully bootstrapped/regtested on > x86_64-linux and i686-linux (with that above regressions), the second one > is probably better but has been so far tested just on the new testcases and > verified to also cause the above Ada regressions. Looking at the Ada cases (I admit I don't really understand why it isn't vectorized, the IL is so different from the start because of the extra SAVE_EXPRs that it is very hard to diff stuff), the case where save_expr used to return the argument and no longer does are those r.P_BOUNDS->LB0 etc. cases. Now, I wondered if (pre-gimplification) we couldn't make an exception and allow the base to be INDIRECT_REF or of a REFERENCE_TYPE with the idea that references are really imutable and can't be changed during its lifetime (after gimplification whether something is REFERENCE_TYPE or POINTER_TYPE is lost), but that isn't what Ada is using. So, another possibility would be to allow bases of TREE_READONLY (t) && !TREE_SIDE_EFFECTS (t) which are INDIRECT_REFs of tree_invariant_p_1 addresses. That doesn't work either, in the r.P_BOUNDS->LB0 case P_BOUNDS is a FIELD_DECL with POINTER_TYPE, LB0 is TREE_READONLY FIELD_DECL and that COMPONENT_REF is also TREE_READONLY, r is TREE_READONLY PARM_DECL, but unforuntately the r.P_BOUNDS COMPONENT_REF isn't marked TREE_READONLY. Thus, shall we treat as tree_invariant_p_1 also handled components which are !TREE_SIDE_EFFECTS (t), but not TREE_READONLY and only their base is TREE_READONLY? Or do that only during the recursion? Jakub
Re: [PATCH] tree: Fix up save_expr [PR52339]
On Fri, May 05, 2023 at 11:55:41AM +0200, Jakub Jelinek via Gcc-patches wrote: > Looking at the Ada cases (I admit I don't really understand why it isn't > vectorized, the IL is so different from the start because of the extra > SAVE_EXPRs that it is very hard to diff stuff), the case where save_expr > used to return the argument and no longer does are those > r.P_BOUNDS->LB0 > etc. cases. Now, I wondered if (pre-gimplification) we couldn't make an > exception and allow the base to be INDIRECT_REF or of a REFERENCE_TYPE > with the idea that references are really imutable and can't be changed > during its lifetime (after gimplification whether something is > REFERENCE_TYPE or POINTER_TYPE is lost), but that isn't what Ada is using. > > So, another possibility would be to allow bases of TREE_READONLY (t) && > !TREE_SIDE_EFFECTS (t) which are INDIRECT_REFs of tree_invariant_p_1 > addresses. That doesn't work either, in the r.P_BOUNDS->LB0 case > P_BOUNDS is a FIELD_DECL with POINTER_TYPE, LB0 is TREE_READONLY FIELD_DECL > and that COMPONENT_REF is also TREE_READONLY, r is TREE_READONLY PARM_DECL, > but unforuntately the r.P_BOUNDS COMPONENT_REF isn't marked TREE_READONLY. > > Thus, shall we treat as tree_invariant_p_1 also handled components which > are !TREE_SIDE_EFFECTS (t), but not TREE_READONLY and only their base > is TREE_READONLY? Or do that only during the recursion? But doing that feels quite risky. While the following version of the patch avoids the Ada regressions, the fact that we don't miscompile the pr52339-1.c testcase modified to have int foo (const struct S *const p, struct S *q) rather than int foo (const struct S *p, struct S *q) is only because the FE happens to add there some useless cast in between. While the pointer is invariant, I'm afraid nothing guarantees it goes out of scope in between multiple uses of the expression returned by save_expr. 2023-05-05 Jakub Jelinek PR c++/52339 * tree.cc (tree_invariant_p_1): For TREE_READONLY (t) without side-effects, only return true if DECL_P (get_base_address (t)). * g++.dg/opt/pr52339.C: New test. * gcc.c-torture/execute/pr52339-1.c: New test. * gcc.c-torture/execute/pr52339-2.c: New test. --- gcc/tree.cc.jj 2023-05-01 09:59:46.686293833 +0200 +++ gcc/tree.cc 2023-05-05 12:34:26.989523468 +0200 @@ -3876,10 +3876,26 @@ tree_invariant_p_1 (tree t) { tree op; - if (TREE_CONSTANT (t) - || (TREE_READONLY (t) && !TREE_SIDE_EFFECTS (t))) + if (TREE_CONSTANT (t)) return true; + if (TREE_READONLY (t) && !TREE_SIDE_EFFECTS (t)) +{ + /* Return true for const qualified vars, but for members or array +elements without side-effects return true only if the base +object is a decl. If the base is e.g. a pointer dereference, +what the pointer points to could be deallocated or the pointer +could be changed. See PR52339. */ + tree base = get_base_address (t); + if (DECL_P (base)) + return true; + /* As an exception, allow pointer dereferences as long as the pointer +is invariant. */ + if (TREE_CODE (base) == INDIRECT_REF + && tree_invariant_p_1 (get_base_address (TREE_OPERAND (base, 0 + return true; +} + switch (TREE_CODE (t)) { case SAVE_EXPR: --- gcc/testsuite/g++.dg/opt/pr52339.C.jj 2023-05-04 15:23:20.459935705 +0200 +++ gcc/testsuite/g++.dg/opt/pr52339.C 2023-05-04 15:22:35.640578681 +0200 @@ -0,0 +1,19 @@ +// PR c++/52339 +// { dg-do run { target c++11 } } + + +struct B; +struct A { B *b; }; +struct B { + A *a; + B () : a(new A{this}) {} + ~B () { delete a; } +}; + +int +main () +{ + B *b = new B; + const A *a = b->a; + delete a->b; +} --- gcc/testsuite/gcc.c-torture/execute/pr52339-1.c.jj 2023-05-04 15:22:59.177241023 +0200 +++ gcc/testsuite/gcc.c-torture/execute/pr52339-1.c 2023-05-04 15:20:19.820527142 +0200 @@ -0,0 +1,29 @@ +/* PR c++/52339 */ + +struct S { int a; }; + +void +bar (int *p, struct S *q) +{ + __builtin_free (q); +} + +int +foo (const struct S *p, struct S *q) +{ + int b[p->a]; + bar (b, q); + return sizeof (b); +} + +int +main () +{ + struct S *p = __builtin_malloc (sizeof (struct S)); + if (!p) +return 0; + p->a = 42; + if (foo (p, p) != 42 * sizeof (int)) +__builtin_abort (); + return 0; +} --- gcc/testsuite/gcc.c-torture/execute/pr52339-2.c.jj 2022-11-21 10:04:00.210677046 +0100 +++ gcc/testsuite/gcc.c-torture/execute/pr52339-2.c 2023-05-04 19:34:08.581686806 +0200 @@ -0,0 +1,20 @@ +/* PR c++/52339 */ + +struct S { int a; }; + +int +foo (const struct S *p) +{ + int b[p->a]; + ++p; + return sizeof (b); +} + +int +main () +{ + struct S s[] = { { 42 }, { 43 } }; + if (foo (s) != 42 * sizeof (int)) +__builtin_abort (); + return 0; +} Jakub
Re: [PATCH] tree: Fix up save_expr [PR52339]
On 5/5/23 06:45, Jakub Jelinek wrote: On Fri, May 05, 2023 at 11:55:41AM +0200, Jakub Jelinek via Gcc-patches wrote: Looking at the Ada cases (I admit I don't really understand why it isn't vectorized, the IL is so different from the start because of the extra SAVE_EXPRs that it is very hard to diff stuff), the case where save_expr used to return the argument and no longer does are those r.P_BOUNDS->LB0 etc. cases. Now, I wondered if (pre-gimplification) we couldn't make an exception and allow the base to be INDIRECT_REF or of a REFERENCE_TYPE with the idea that references are really imutable and can't be changed during its lifetime (after gimplification whether something is REFERENCE_TYPE or POINTER_TYPE is lost), but that isn't what Ada is using. And anyway, a reference can also refer to a non-const object. So, another possibility would be to allow bases of TREE_READONLY (t) && !TREE_SIDE_EFFECTS (t) which are INDIRECT_REFs of tree_invariant_p_1 addresses. That doesn't work either, in the r.P_BOUNDS->LB0 case P_BOUNDS is a FIELD_DECL with POINTER_TYPE, LB0 is TREE_READONLY FIELD_DECL and that COMPONENT_REF is also TREE_READONLY, r is TREE_READONLY PARM_DECL, but unforuntately the r.P_BOUNDS COMPONENT_REF isn't marked TREE_READONLY. And an invariant pointer can point to a non-const object. Thus, shall we treat as tree_invariant_p_1 also handled components which are !TREE_SIDE_EFFECTS (t), but not TREE_READONLY and only their base is TREE_READONLY? Or do that only during the recursion? But doing that feels quite risky. While the following version of the patch avoids the Ada regressions, the fact that we don't miscompile the pr52339-1.c testcase modified to have int foo (const struct S *const p, struct S *q) rather than int foo (const struct S *p, struct S *q) is only because the FE happens to add there some useless cast in between. While the pointer is invariant, I'm afraid nothing guarantees it goes out of scope in between multiple uses of the expression returned by save_expr. Right. 2023-05-05 Jakub Jelinek PR c++/52339 * tree.cc (tree_invariant_p_1): For TREE_READONLY (t) without side-effects, only return true if DECL_P (get_base_address (t)). * g++.dg/opt/pr52339.C: New test. * gcc.c-torture/execute/pr52339-1.c: New test. * gcc.c-torture/execute/pr52339-2.c: New test. --- gcc/tree.cc.jj 2023-05-01 09:59:46.686293833 +0200 +++ gcc/tree.cc 2023-05-05 12:34:26.989523468 +0200 @@ -3876,10 +3876,26 @@ tree_invariant_p_1 (tree t) { tree op; - if (TREE_CONSTANT (t) - || (TREE_READONLY (t) && !TREE_SIDE_EFFECTS (t))) + if (TREE_CONSTANT (t)) return true; + if (TREE_READONLY (t) && !TREE_SIDE_EFFECTS (t)) +{ + /* Return true for const qualified vars, but for members or array +elements without side-effects return true only if the base +object is a decl. If the base is e.g. a pointer dereference, +what the pointer points to could be deallocated or the pointer +could be changed. See PR52339. */ + tree base = get_base_address (t); + if (DECL_P (base)) + return true; So I think the above is correct. + /* As an exception, allow pointer dereferences as long as the pointer +is invariant. */ + if (TREE_CODE (base) == INDIRECT_REF + && tree_invariant_p_1 (get_base_address (TREE_OPERAND (base, 0 + return true; And this is unsafe. +} + switch (TREE_CODE (t)) { case SAVE_EXPR: --- gcc/testsuite/g++.dg/opt/pr52339.C.jj 2023-05-04 15:23:20.459935705 +0200 +++ gcc/testsuite/g++.dg/opt/pr52339.C 2023-05-04 15:22:35.640578681 +0200 @@ -0,0 +1,19 @@ +// PR c++/52339 +// { dg-do run { target c++11 } } + + +struct B; +struct A { B *b; }; +struct B { + A *a; + B () : a(new A{this}) {} + ~B () { delete a; } +}; + +int +main () +{ + B *b = new B; + const A *a = b->a; + delete a->b; +} --- gcc/testsuite/gcc.c-torture/execute/pr52339-1.c.jj 2023-05-04 15:22:59.177241023 +0200 +++ gcc/testsuite/gcc.c-torture/execute/pr52339-1.c 2023-05-04 15:20:19.820527142 +0200 @@ -0,0 +1,29 @@ +/* PR c++/52339 */ + +struct S { int a; }; + +void +bar (int *p, struct S *q) +{ + __builtin_free (q); +} + +int +foo (const struct S *p, struct S *q) +{ + int b[p->a]; + bar (b, q); + return sizeof (b); +} + +int +main () +{ + struct S *p = __builtin_malloc (sizeof (struct S)); + if (!p) +return 0; + p->a = 42; + if (foo (p, p) != 42 * sizeof (int)) +__builtin_abort (); + return 0; +} --- gcc/testsuite/gcc.c-torture/execute/pr52339-2.c.jj 2022-11-21 10:04:00.210677046 +0100 +++ gcc/testsuite/gcc.c-torture/execute/pr52339-2.c 2023-05-04 19:34:08.581686806 +0200 @@ -0,0 +1,20 @@ +/* PR c++/52339 */ + +struct S { int a; }; + +int +foo (const struct S *p) +{ + int b[p->a]; + ++p; + return sizeof (b); +} + +int +main () +{ + struct S s[] = { { 42 }, { 43 } }; + if (foo (s) != 42 * sizeof
Re: [PATCH] tree: Fix up save_expr [PR52339]
On Fri, May 05, 2023 at 07:38:45AM -0400, Jason Merrill wrote: > On 5/5/23 06:45, Jakub Jelinek wrote: > > + if (TREE_READONLY (t) && !TREE_SIDE_EFFECTS (t)) > > +{ > > + /* Return true for const qualified vars, but for members or array > > +elements without side-effects return true only if the base > > +object is a decl. If the base is e.g. a pointer dereference, > > +what the pointer points to could be deallocated or the pointer > > +could be changed. See PR52339. */ > > + tree base = get_base_address (t); > > + if (DECL_P (base)) > > + return true; > > So I think the above is correct. Ok, will test it with testsuite adjustments for the Ada testcases. See below. > > + /* As an exception, allow pointer dereferences as long as the pointer > > +is invariant. */ > > + if (TREE_CODE (base) == INDIRECT_REF > > + && tree_invariant_p_1 (get_base_address (TREE_OPERAND (base, 0 > > + return true; > > And this is unsafe. Ok, idea withdrawn. Had further look at the vect6.adb case, but I think it is for the Ada people to analyze. The *.original dump differences there are as I said instead of using r.P_BOUNDS->LB0 r.P_BOUNDS->UB0 x.P_BOUNDS->LB0 x.P_BOUNDS->UB0 wrap those into SAVE_EXPR in various places (that is the expected part, that is what the patch was about), but also: -SAVE_EXPR LB0 < r.P_BOUNDS->LB0 || x.P_BOUNDS->UB0 > r.P_BOUNDS->UB0>; <<< Unknown tree: loop_stmt I.0 != (unsigned long) vect6__add__L_1__T3b___U I.0 = I.0 + 1; i = (vect6_pkg__index_type) I.0; - if ((SAVE_EXPR LB0 < r.P_BOUNDS->LB0 || x.P_BOUNDS->UB0 > r.P_BOUNDS->UB0>) && .BUILTIN_EXPECT (r.P_BOUNDS->LB0 > i || r.P_BOUNDS->UB0 < i, 0, 15)) + if (SAVE_EXPR LB0> > i || SAVE_EXPR UB0> < i) { .gnat_rcheck_CE_Index_Check ("vect6.adb", 9); } So, if the {x,r}.P_BOUNDS->{U,B}B0 expressions aren't wrapped into SAVE_EXPRs, something in the FE decides to evaluate x.P_BOUNDS->LB0 < r.P_BOUNDS->LB0 || x.P_BOUNDS->UB0 > r.P_BOUNDS->UB0 expression into a temporary before the loop and && the bounds condition inside of the loop with it, while with the patch that doesn't happen. And, that turns out in loop unswitching being successful without my patch and not with my patch, where we can vectorize the unswitched loop without the .gnat_rcheck_CE_Index_Check call. Perhaps ada/gcc-interface/utils2.cc (gnat_invariant_expr) could be taught to handle SAVE_EXPR by looking at its operand? --- gcc/ada/gcc-interface/utils2.cc.jj 2023-01-16 23:19:05.539727388 +0100 +++ gcc/ada/gcc-interface/utils2.cc 2023-05-05 15:37:30.193990948 +0200 @@ -3332,6 +3332,7 @@ gnat_invariant_expr (tree expr) case IMAGPART_EXPR: case VIEW_CONVERT_EXPR: CASE_CONVERT: + case SAVE_EXPR: break; case INDIRECT_REF: fixes the vect{1,2,3,4,5,6}.adb regressions but not the loop_optimization21.adb one. But I'm afraid I really have no idea what that code is doing. 2023-05-05 Jakub Jelinek PR c++/52339 * tree.cc (tree_invariant_p_1): For TREE_READONLY (t) without side-effects, only return true if DECL_P (get_base_address (t)). * g++.dg/opt/pr52339.C: New test. * gcc.c-torture/execute/pr52339-1.c: New test. * gcc.c-torture/execute/pr52339-2.c: New test. * gnat.dg/loop_optimization21.adb: Adjust expected match count. * gnat.dg/vect1.adb: Likewise. * gnat.dg/vect2.adb: Likewise. * gnat.dg/vect3.adb: Likewise. * gnat.dg/vect4.adb: Likewise. * gnat.dg/vect5.adb: Likewise. * gnat.dg/vect6.adb: Likewise. --- gcc/tree.cc.jj 2023-05-01 09:59:46.686293833 +0200 +++ gcc/tree.cc 2023-05-05 10:19:19.061827355 +0200 @@ -3876,10 +3876,21 @@ tree_invariant_p_1 (tree t) { tree op; - if (TREE_CONSTANT (t) - || (TREE_READONLY (t) && !TREE_SIDE_EFFECTS (t))) + if (TREE_CONSTANT (t)) return true; + if (TREE_READONLY (t) && !TREE_SIDE_EFFECTS (t)) +{ + /* Return true for const qualified vars, but for members or array +elements without side-effects return true only if the base +object is a decl. If the base is e.g. a pointer dereference, +what the pointer points to could be deallocated or the pointer +could be changed. See PR52339. */ + tree base = get_base_address (t); + if (DECL_P (base)) + return true; +} + switch (TREE_CODE (t)) { case SAVE_EXPR: --- gcc/testsuite/g++.dg/opt/pr52339.C.jj 2023-05-04 15:23:20.459935705 +0200 +++ gcc/testsuite/g++.dg/opt/pr52339.C 2023-05-04 15:22:35.640578681 +0200 @@ -0,0 +1,19 @@ +// PR c++/52339 +// { dg-do run { target c++11 } } + + +struct B; +struct A { B *b; }; +struct B { + A *a; + B () : a(new A{this}) {} + ~B () { delete a; } +}; + +int +main () +{ + B *b = new B; + const A *a = b->a; + delete a->b; +} --- gcc/testsuit
Re: [PATCH] tree: Fix up save_expr [PR52339]
On 5/5/23 09:40, Jakub Jelinek wrote: On Fri, May 05, 2023 at 07:38:45AM -0400, Jason Merrill wrote: On 5/5/23 06:45, Jakub Jelinek wrote: + if (TREE_READONLY (t) && !TREE_SIDE_EFFECTS (t)) +{ + /* Return true for const qualified vars, but for members or array +elements without side-effects return true only if the base +object is a decl. If the base is e.g. a pointer dereference, +what the pointer points to could be deallocated or the pointer +could be changed. See PR52339. */ + tree base = get_base_address (t); + if (DECL_P (base)) + return true; So I think the above is correct. Ok, will test it with testsuite adjustments for the Ada testcases. See below. + /* As an exception, allow pointer dereferences as long as the pointer +is invariant. */ + if (TREE_CODE (base) == INDIRECT_REF + && tree_invariant_p_1 (get_base_address (TREE_OPERAND (base, 0 + return true; And this is unsafe. Ok, idea withdrawn. Had further look at the vect6.adb case, but I think it is for the Ada people to analyze. The *.original dump differences there are as I said instead of using r.P_BOUNDS->LB0 r.P_BOUNDS->UB0 x.P_BOUNDS->LB0 x.P_BOUNDS->UB0 wrap those into SAVE_EXPR in various places (that is the expected part, that is what the patch was about), but also: -SAVE_EXPR LB0 < r.P_BOUNDS->LB0 || x.P_BOUNDS->UB0 > r.P_BOUNDS->UB0>; <<< Unknown tree: loop_stmt I.0 != (unsigned long) vect6__add__L_1__T3b___U I.0 = I.0 + 1; i = (vect6_pkg__index_type) I.0; - if ((SAVE_EXPR LB0 < r.P_BOUNDS->LB0 || x.P_BOUNDS->UB0 > r.P_BOUNDS->UB0>) && .BUILTIN_EXPECT (r.P_BOUNDS->LB0 > i || r.P_BOUNDS->UB0 < i, 0, 15)) + if (SAVE_EXPR LB0> > i || SAVE_EXPR UB0> < i) { .gnat_rcheck_CE_Index_Check ("vect6.adb", 9); } From this diff it looks like the change stops looking at x.P_BOUNDS entirely, which seems like more of an optimization than hoisting that check out of the loop? So, if the {x,r}.P_BOUNDS->{U,B}B0 expressions aren't wrapped into SAVE_EXPRs, something in the FE decides to evaluate x.P_BOUNDS->LB0 < r.P_BOUNDS->LB0 || x.P_BOUNDS->UB0 > r.P_BOUNDS->UB0 expression into a temporary before the loop and && the bounds condition inside of the loop with it, while with the patch that doesn't happen. And, that turns out in loop unswitching being successful without my patch and not with my patch, where we can vectorize the unswitched loop without the .gnat_rcheck_CE_Index_Check call. Perhaps ada/gcc-interface/utils2.cc (gnat_invariant_expr) could be taught to handle SAVE_EXPR by looking at its operand? --- gcc/ada/gcc-interface/utils2.cc.jj 2023-01-16 23:19:05.539727388 +0100 +++ gcc/ada/gcc-interface/utils2.cc 2023-05-05 15:37:30.193990948 +0200 @@ -3332,6 +3332,7 @@ gnat_invariant_expr (tree expr) case IMAGPART_EXPR: case VIEW_CONVERT_EXPR: CASE_CONVERT: + case SAVE_EXPR: I guess doing this would allow gnat_invariant_expr to handle DECL_INVARIANT_P that save_expr doesn't know about. But it seems that it makes the same assumption as tree_invariant_p_1 about the pointed-to object not changing: case INDIRECT_REF: if ((!invariant_p && !TREE_READONLY (t)) || TREE_SIDE_EFFECTS (t)) return NULL_TREE; I don't know if this assumption is any more valid in Ada than in C/C++. break; case INDIRECT_REF: fixes the vect{1,2,3,4,5,6}.adb regressions but not the loop_optimization21.adb one. But I'm afraid I really have no idea what that code is doing. 2023-05-05 Jakub Jelinek PR c++/52339 * tree.cc (tree_invariant_p_1): For TREE_READONLY (t) without side-effects, only return true if DECL_P (get_base_address (t)). * g++.dg/opt/pr52339.C: New test. * gcc.c-torture/execute/pr52339-1.c: New test. * gcc.c-torture/execute/pr52339-2.c: New test. * gnat.dg/loop_optimization21.adb: Adjust expected match count. * gnat.dg/vect1.adb: Likewise. * gnat.dg/vect2.adb: Likewise. * gnat.dg/vect3.adb: Likewise. * gnat.dg/vect4.adb: Likewise. * gnat.dg/vect5.adb: Likewise. * gnat.dg/vect6.adb: Likewise. --- gcc/tree.cc.jj 2023-05-01 09:59:46.686293833 +0200 +++ gcc/tree.cc 2023-05-05 10:19:19.061827355 +0200 @@ -3876,10 +3876,21 @@ tree_invariant_p_1 (tree t) { tree op; - if (TREE_CONSTANT (t) - || (TREE_READONLY (t) && !TREE_SIDE_EFFECTS (t))) + if (TREE_CONSTANT (t)) return true; + if (TREE_READONLY (t) && !TREE_SIDE_EFFECTS (t)) +{ + /* Return true for const qualified vars, but for members or array +elements without side-effects return true only if the base +object is a decl. If the base is e.g. a pointer dereference, +what the pointer points to could be deallocated or the pointer +
Re: [PATCH] tree: Fix up save_expr [PR52339]
On Fri, May 05, 2023 at 01:32:02PM -0400, Jason Merrill wrote: > > --- gcc/ada/gcc-interface/utils2.cc.jj 2023-01-16 23:19:05.539727388 > > +0100 > > +++ gcc/ada/gcc-interface/utils2.cc 2023-05-05 15:37:30.193990948 +0200 > > @@ -3332,6 +3332,7 @@ gnat_invariant_expr (tree expr) > > case IMAGPART_EXPR: > > case VIEW_CONVERT_EXPR: > > CASE_CONVERT: > > + case SAVE_EXPR: > > I guess doing this would allow gnat_invariant_expr to handle > DECL_INVARIANT_P that save_expr doesn't know about. But it seems that it > makes the same assumption as tree_invariant_p_1 about the pointed-to object > not changing: > > > case INDIRECT_REF: > > if ((!invariant_p && !TREE_READONLY (t)) || TREE_SIDE_EFFECTS (t)) > > return NULL_TREE; > > I don't know if this assumption is any more valid in Ada than in C/C++. I think we really need Eric (as one who e.g. introduced the DECL_INVARIANT_P apparently for this kind of stuff) to have a look at that on the Ada side. The question is if the posted tree.cc (smallest) patch + 3 new testcases + the 7 ada testsuite workarounds are ok for trunk if it passes bootstrap/regtest, then I'd file a PR about the Ada regression and only once it is dealt with would consider backporting, or if we need to wait for Eric before making progress. Jakub
Re: [PATCH] tree: Fix up save_expr [PR52339]
On Fri, 5 May 2023, Jakub Jelinek wrote: > On Fri, May 05, 2023 at 01:32:02PM -0400, Jason Merrill wrote: > > > --- gcc/ada/gcc-interface/utils2.cc.jj2023-01-16 23:19:05.539727388 > > > +0100 > > > +++ gcc/ada/gcc-interface/utils2.cc 2023-05-05 15:37:30.193990948 > > > +0200 > > > @@ -3332,6 +3332,7 @@ gnat_invariant_expr (tree expr) > > > case IMAGPART_EXPR: > > > case VIEW_CONVERT_EXPR: > > > CASE_CONVERT: > > > + case SAVE_EXPR: > > > > I guess doing this would allow gnat_invariant_expr to handle > > DECL_INVARIANT_P that save_expr doesn't know about. But it seems that it > > makes the same assumption as tree_invariant_p_1 about the pointed-to object > > not changing: > > > > > case INDIRECT_REF: > > > if ((!invariant_p && !TREE_READONLY (t)) || TREE_SIDE_EFFECTS > > > (t)) > > > return NULL_TREE; > > > > I don't know if this assumption is any more valid in Ada than in C/C++. > > I think we really need Eric (as one who e.g. introduced the > DECL_INVARIANT_P apparently for this kind of stuff) to have a look at that on > the > Ada side. > > The question is if the posted tree.cc (smallest) patch + 3 new testcases > + the 7 ada testsuite workarounds are ok for trunk if it passes > bootstrap/regtest, then I'd file a PR about the Ada regression and only once > it is dealt with would consider backporting, or if we need to wait for Eric > before making progress. I wonder if we should defer some of the choices to a langhook like make the tree_invariant_p_1 a langhook invocation with the default to call tree_invariant_p_1. After lowering we can reset the langhook to the default. I think we at least need the generic save_expr to be langhook aware during the time we fold the original non-gimplified GENERIC IL (but no longer for the generated GENERIC and to be gimplified IL the middle-end eventually generates later). Richard.
Re: [PATCH] tree: Fix up save_expr [PR52339]
On Mon, May 08, 2023 at 06:23:54AM +, Richard Biener wrote: > I wonder if we should defer some of the choices to a langhook > like make the tree_invariant_p_1 a langhook invocation with the > default to call tree_invariant_p_1. After lowering we can reset > the langhook to the default. We certainly can. The only outliner would be Ada I think, but we really need to know what holds and doesn't hold there. Jakub
Re: [PATCH] tree: Fix up save_expr [PR52339]
> I think we really need Eric (as one who e.g. introduced the > DECL_INVARIANT_P apparently for this kind of stuff) to have a look at that > on the Ada side. DECL_INVARIANT_P is only set on discriminants with no default value and those are really invariant in Ada, i.e. do not change once set. > The question is if the posted tree.cc (smallest) patch + 3 new testcases > + the 7 ada testsuite workarounds are ok for trunk if it passes > bootstrap/regtest, then I'd file a PR about the Ada regression and only once > it is dealt with would consider backporting, or if we need to wait for Eric > before making progress. Let me have a quick look first, as pessimizing loop optimizations in Ada in order to fix a 11-year old PR seems to be a little bit hasty. -- Eric Botcazou
Re: [PATCH] tree: Fix up save_expr [PR52339]
> I think we really need Eric (as one who e.g. introduced the > DECL_INVARIANT_P apparently for this kind of stuff) to have a look at that > on the Ada side. I have been investigating this for a few days and it's no small change for Ada and probably for other languages with dynamic types. SAVE_EXPRs are delicate to handle because 1) they are TREE_SIDE_EFFECTS (it's explained in save_expr) so out of TREE_READONLY && !TREE_SIDE_EFFECTS trees, you now get side effects which then propagate to all parent nodes 2) their placement is problematic in conditional expressions, for example if you replace cond > 0 ? A : A + 1 with cond > 0 ? SAVE_EXPR (A) : SAVE_EXPR (A) + 1 then gimplification will, say, create the temporary and initialize it in the first arm so, if at runtime you take the second arm, you'll read the temporary uninitialized. That's caught for scalar values by the SSA form (if your patch is applied to a GCC 12 tree, you'll get ICEs in the ACATS testsuite because of this through finalize_type_size -> variable_size -> save_expr, it is probably mitigated/addressed in GCC 14 by 68e0063397ba820e71adc220b2da0581dce29ffa). That's also why making gnat_invariant_expr return (some of) them does not look really safe. In addition to this, in Ada we have bounds of unconstrained arrays which are both read-only and stored indirectly, i.e. you have an INDIRECT_REF in the tree (it is marked TREE_THIS_NOTRAP because the bounds are always present), and which obviously play a crucial role in loops running over the arrays. This issue is responsible for the regressions in the gnat.dg testsuite. I think that we can reasonably deal with the second issue in the Ada front-end because we know the semantics of the bounds of unconstrained arrays, and I'm testing a patch to that effect, but the first issue might be annoying too. -- Eric Botcazou