* [PATCH] PR tree-optimization/109462 - Don't use ANY PHI equivalences in range-on-entry. @ 2023-04-11 23:52 Andrew MacLeod 2023-04-12 8:20 ` Jakub Jelinek 2023-04-12 9:12 ` Richard Biener 0 siblings, 2 replies; 11+ messages in thread From: Andrew MacLeod @ 2023-04-11 23:52 UTC (permalink / raw) To: gcc-patches; +Cc: Jakub Jelinek, Richard Biener, hernandez, aldy [-- Attachment #1: Type: text/plain, Size: 1541 bytes --] This is a carry over from PR 108139. When we have a PHI node which has 2 arguments and one is undefined, we create an equivalence between the LHS and the non-undefined PHI argument. THis allows us to perform certain optimizations. The problem is, when we are evaluating range-on-entry in the cache, its depends on where that equivalence is made, from where we have no context. a_3 = <b_2 (3), c_3 (4)> if c_3 is undefined, then a_3 is equivalent to b_2... but b_2 is not equivalence to a_3 everywhere.. its a one way thing. 108139 fixed this by not evaluating any equivalences if the equivalence was the LHS. What it missed, was it possible we are calculating the range of a_3. b_2 is not defined in a phi node, so it happily used the equivalence. This PR demonstrates that we can't always use that equivlence either without more context. There can be places in the IL where a_3 is used, but b_2 has moved to a new value within a loop. So we can't do this if either NAME or the equivalence is equal via a PHI node with an undefined argument. Unfortunately, this unsafe assumption is why PR 101912 is fixed. Fixing this issue properly is going to cause that to reopen as it is unsafe. (That PR is a false uninitialized warning issue, rather than an wrong-code issue) This bootstraps on x86_64-pc-linux-gnu with that single regression, which I have XFAILed for now. OK for trunk? Once Jakub verifies it actually fixes the execution problem. we have no executable test . yet. Andrew [-- Attachment #2: 462.patch --] [-- Type: text/x-patch, Size: 2165 bytes --] commit 90848fb75cf91a45edd355d2b1485ef835099609 Author: Andrew MacLeod <amacleod@redhat.com> Date: Tue Apr 11 17:29:03 2023 -0400 Don't use ANY PHI equivalences in range-on-entry. PR 108139 dissallows PHI equivalencies in the on-entry calculator, but it was only checking if the equivlaence was a PHI. In this case, NAME itself is a PHI with an equivlaence caused by an undefined value, so we also need to check that case. Unfortunately this un-fixes 101912. PR tree-optimization/109462 gcc/ * gimple-range-cache.cc (ranger_cache::fill_block_cache): Don't check for equivalences if NAME is a phi node. gcc/testsuite/ * gcc.dg/uninit-pr101912.c: XFAIL the warning. diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc index 6a098d8ec28..3b52f1e734c 100644 --- a/gcc/gimple-range-cache.cc +++ b/gcc/gimple-range-cache.cc @@ -1218,7 +1218,9 @@ ranger_cache::fill_block_cache (tree name, basic_block bb, basic_block def_bb) fprintf (dump_file, "\n"); } // See if any equivalences can refine it. - if (m_oracle) + // PR 109462, like 108139 below, a one way equivalence introduced + // by a PHI node can also be through the definition side. Disallow it. + if (m_oracle && !is_a<gphi *> (SSA_NAME_DEF_STMT (name))) { tree equiv_name; relation_kind rel; diff --git a/gcc/testsuite/gcc.dg/uninit-pr101912.c b/gcc/testsuite/gcc.dg/uninit-pr101912.c index 1550c03436d..62cd2a0c73e 100644 --- a/gcc/testsuite/gcc.dg/uninit-pr101912.c +++ b/gcc/testsuite/gcc.dg/uninit-pr101912.c @@ -11,7 +11,7 @@ tzloadbody (void) for (int i = 0; i < n; i++) { int corr = getint (); - if (corr < 1 || (corr == 1 && !(leapcnt == 0 || (prevcorr < corr ? corr == prevcorr + 1 : (corr == prevcorr || corr == prevcorr - 1))))) /* { dg-bogus "uninitialized" } */ + if (corr < 1 || (corr == 1 && !(leapcnt == 0 || (prevcorr < corr ? corr == prevcorr + 1 : (corr == prevcorr || corr == prevcorr - 1))))) /* { dg-bogus "uninitialized" "pr101912" { xfail *-*-* } } */ return -1; prevcorr = corr; ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [PATCH] PR tree-optimization/109462 - Don't use ANY PHI equivalences in range-on-entry. 2023-04-11 23:52 [PATCH] PR tree-optimization/109462 - Don't use ANY PHI equivalences in range-on-entry Andrew MacLeod @ 2023-04-12 8:20 ` Jakub Jelinek 2023-04-12 13:12 ` Andrew MacLeod 2023-04-12 9:12 ` Richard Biener 1 sibling, 1 reply; 11+ messages in thread From: Jakub Jelinek @ 2023-04-12 8:20 UTC (permalink / raw) To: Andrew MacLeod; +Cc: gcc-patches, Richard Biener, hernandez, aldy On Tue, Apr 11, 2023 at 07:52:29PM -0400, Andrew MacLeod wrote: > This bootstraps on x86_64-pc-linux-gnu with that single regression, which I > have XFAILed for now. OK for trunk? Yes. > Once Jakub verifies it actually fixes > the execution problem. we have no executable test . yet. I have verified this fix both on the original clang testcase, and on a self-contained testcase I've reduced overnight and this morning. Ok to commit it to trunk incrementally after your commit? BTW, I've wondered if it is just this uninitialized phi arg problem or if I could reproduce it also if the phi arg was initialized but had the same range as the current iteration is known to have due to a comparison (even when the actual value is from the previous loop's iteration). In the test below, that would be Result.c = r_paren; before while (!TheLexer.LexFromRawLexer (I)) loop. But it wasn't miscompiled in that case. 2023-04-12 Jakub Jelinek <jakub@redhat.com> PR tree-optimization/109462 * g++.dg/opt/pr109462.C: New test. --- gcc/testsuite/g++.dg/opt/pr109462.C.jj 2023-04-12 09:58:23.085603031 +0200 +++ gcc/testsuite/g++.dg/opt/pr109462.C 2023-04-12 09:54:22.472079711 +0200 @@ -0,0 +1,94 @@ +// PR tree-optimization/109462 +// { dg-do run { target c++11 } } +// { dg-options "-O2" } + +struct A { + A (const char *); + A (const char *, int); + bool empty (); + int size (); + bool equals (A); + A trim (char); + A trim (); +}; +[[gnu::noipa]] A::A (const char *) {} +[[gnu::noipa]] A::A (const char *, int) { __builtin_abort (); } +[[gnu::noipa]] bool A::empty () { __builtin_abort (); } +[[gnu::noipa]] int A::size () { __builtin_abort (); } +[[gnu::noipa]] bool A::equals (A) { return true; } +[[gnu::noipa]] A A::trim (char) { __builtin_abort (); } +[[gnu::noipa]] A A::trim () { __builtin_abort (); } + +enum B { raw_identifier = 6, l_paren = 21, r_paren = 22 }; +[[gnu::noipa]] bool isAnyIdentifier (B) { return true; } +[[gnu::noipa]] bool isStringLiteral (B) { __builtin_abort (); } + +struct C { + B c; + B getKind () { return c; } + bool is (B x) { return c == x; } + unsigned getLength () { __builtin_abort (); } + A getRawIdentifier () { + A x (""); + c == raw_identifier ? void () : __builtin_abort (); + return x; + } + const char *getLiteralData (); +}; +[[gnu::noipa]] const char *C::getLiteralData () { __builtin_abort (); } + +struct D { + D (); + bool LexFromRawLexer (C &); +}; +[[gnu::noipa]] D::D () {} +[[gnu::noipa]] bool D::LexFromRawLexer (C &t) { + static int cnt; + C tok[] = { { raw_identifier }, { l_paren }, { raw_identifier }, { r_paren } }; + t = tok[cnt++]; + return false; +} + +bool ok = false; +[[gnu::noipa]] void reportEmptyContextError () +{ + ok = true; +} + +[[gnu::noipa]] void +VisitObjCMessageExpr () +{ + D TheLexer; + C I; + C Result; + int p_count = 0; + while (!TheLexer.LexFromRawLexer (I)) { + if (I.getKind () == l_paren) + ++p_count; + if (I.getKind () == r_paren) { + if (p_count == 1) + break; + --p_count; + } + Result = I; + } + if (isAnyIdentifier (Result.getKind ())) { + if (Result.getRawIdentifier ().equals ("nil")) { + reportEmptyContextError (); + return; + } + } + if (!isStringLiteral (Result.getKind ())) + return; + A Comment = A (Result.getLiteralData (), Result.getLength ()).trim ('"'); + if ((Comment.trim ().size () == 0 && Comment.size () > 0) || Comment.empty ()) + reportEmptyContextError (); +} + +int +main () +{ + VisitObjCMessageExpr (); + if (!ok) + __builtin_abort (); +} Jakub ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [PATCH] PR tree-optimization/109462 - Don't use ANY PHI equivalences in range-on-entry. 2023-04-12 8:20 ` Jakub Jelinek @ 2023-04-12 13:12 ` Andrew MacLeod 0 siblings, 0 replies; 11+ messages in thread From: Andrew MacLeod @ 2023-04-12 13:12 UTC (permalink / raw) To: Jakub Jelinek; +Cc: gcc-patches, Richard Biener, hernandez, aldy On 4/12/23 04:20, Jakub Jelinek wrote: > On Tue, Apr 11, 2023 at 07:52:29PM -0400, Andrew MacLeod wrote: >> This bootstraps on x86_64-pc-linux-gnu with that single regression, which I >> have XFAILed for now. OK for trunk? > Yes. > >> Once Jakub verifies it actually fixes >> the execution problem. we have no executable test . yet. > I have verified this fix both on the original clang testcase, and > on a self-contained testcase I've reduced overnight and this morning. > > Ok to commit it to trunk incrementally after your commit? Sure. I just pushed it. Andrew ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [PATCH] PR tree-optimization/109462 - Don't use ANY PHI equivalences in range-on-entry. 2023-04-11 23:52 [PATCH] PR tree-optimization/109462 - Don't use ANY PHI equivalences in range-on-entry Andrew MacLeod 2023-04-12 8:20 ` Jakub Jelinek @ 2023-04-12 9:12 ` Richard Biener 2023-04-12 10:58 ` Jakub Jelinek 1 sibling, 1 reply; 11+ messages in thread From: Richard Biener @ 2023-04-12 9:12 UTC (permalink / raw) To: Andrew MacLeod; +Cc: gcc-patches, Jakub Jelinek, hernandez, aldy On Wed, Apr 12, 2023 at 1:52 AM Andrew MacLeod <amacleod@redhat.com> wrote: > > This is a carry over from PR 108139. > > When we have a PHI node which has 2 arguments and one is undefined, we > create an equivalence between the LHS and the non-undefined PHI > argument. THis allows us to perform certain optimizations. > > The problem is, when we are evaluating range-on-entry in the cache, its > depends on where that equivalence is made, from where we have no context. > > a_3 = <b_2 (3), c_3 (4)> > > if c_3 is undefined, then a_3 is equivalent to b_2... but b_2 is not > equivalence to a_3 everywhere.. its a one way thing. > > 108139 fixed this by not evaluating any equivalences if the equivalence > was the LHS. > > What it missed, was it possible we are calculating the range of a_3. > b_2 is not defined in a phi node, so it happily used the equivalence. > This PR demonstrates that we can't always use that equivlence either > without more context. There can be places in the IL where a_3 is used, > but b_2 has moved to a new value within a loop. I think that's only possible when b_2 flows in via a backedge (from BB3). So isn't this all about backedges? Indeed creating equivalences across backedges is futile with SSA. I think ranger requires dominators, so to have the above scenario - a_3 used after the b_2 definition - requires BB3 to be dominated by the a_3 definition which is what you could check. > > So we can't do this if either NAME or the equivalence is equal via a PHI > node with an undefined argument. > > Unfortunately, this unsafe assumption is why PR 101912 is fixed. > Fixing this issue properly is going to cause that to reopen as it is > unsafe. (That PR is a false uninitialized warning issue, rather than an > wrong-code issue) > > This bootstraps on x86_64-pc-linux-gnu with that single regression, > which I have XFAILed for now. OK for trunk? Once Jakub verifies it > actually fixes the execution problem. we have no executable test . yet. > > Andrew > > > ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [PATCH] PR tree-optimization/109462 - Don't use ANY PHI equivalences in range-on-entry. 2023-04-12 9:12 ` Richard Biener @ 2023-04-12 10:58 ` Jakub Jelinek 2023-04-12 11:01 ` Richard Biener 0 siblings, 1 reply; 11+ messages in thread From: Jakub Jelinek @ 2023-04-12 10:58 UTC (permalink / raw) To: Richard Biener; +Cc: Andrew MacLeod, gcc-patches, hernandez, aldy On Wed, Apr 12, 2023 at 11:12:17AM +0200, Richard Biener wrote: > > 108139 fixed this by not evaluating any equivalences if the equivalence > > was the LHS. > > > > What it missed, was it possible we are calculating the range of a_3. > > b_2 is not defined in a phi node, so it happily used the equivalence. > > This PR demonstrates that we can't always use that equivlence either > > without more context. There can be places in the IL where a_3 is used, > > but b_2 has moved to a new value within a loop. > > I think that's only possible when b_2 flows in via a backedge (from BB3). > So isn't this all about backedges? Indeed creating equivalences across Apparently backedges and undefined phi arg, without that it doesn't seem to trigger because then it isn't considered equivalent even if the two have same range. > backedges is futile with SSA. I think ranger requires dominators, so > to have the above scenario - a_3 used after the b_2 definition - requires > BB3 to be dominated by the a_3 definition which is what you could check. Would be nice. Though, I'm afraid it still wouldn't fix the PR101912 testcase, because it has exactly what happens in this PR, undefined phi arg from the pre-header and uses of the previous iteration's value (i.e. across backedge). Jakub ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [PATCH] PR tree-optimization/109462 - Don't use ANY PHI equivalences in range-on-entry. 2023-04-12 10:58 ` Jakub Jelinek @ 2023-04-12 11:01 ` Richard Biener 2023-04-12 20:55 ` Andrew MacLeod 0 siblings, 1 reply; 11+ messages in thread From: Richard Biener @ 2023-04-12 11:01 UTC (permalink / raw) To: Jakub Jelinek; +Cc: Andrew MacLeod, gcc-patches, hernandez, aldy On Wed, Apr 12, 2023 at 12:59 PM Jakub Jelinek <jakub@redhat.com> wrote: > > On Wed, Apr 12, 2023 at 11:12:17AM +0200, Richard Biener wrote: > > > 108139 fixed this by not evaluating any equivalences if the equivalence > > > was the LHS. > > > > > > What it missed, was it possible we are calculating the range of a_3. > > > b_2 is not defined in a phi node, so it happily used the equivalence. > > > This PR demonstrates that we can't always use that equivlence either > > > without more context. There can be places in the IL where a_3 is used, > > > but b_2 has moved to a new value within a loop. > > > > I think that's only possible when b_2 flows in via a backedge (from BB3). > > So isn't this all about backedges? Indeed creating equivalences across > > Apparently backedges and undefined phi arg, without that it doesn't seem > to trigger because then it isn't considered equivalent even if the two have > same range. > > > backedges is futile with SSA. I think ranger requires dominators, so > > to have the above scenario - a_3 used after the b_2 definition - requires > > BB3 to be dominated by the a_3 definition which is what you could check. > > Would be nice. > > Though, I'm afraid it still wouldn't fix the PR101912 testcase, because > it has exactly what happens in this PR, undefined phi arg from the > pre-header and uses of the previous iteration's value (i.e. across > backedge). Well yes, that's what's not allowed. So when the PHI dominates the to-be-equivalenced argument edge src then the equivalence isn't valid because there's a place (that very source block for example) a use of the PHI lhs could appear and where we'd then mixup iterations. > > Jakub > ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [PATCH] PR tree-optimization/109462 - Don't use ANY PHI equivalences in range-on-entry. 2023-04-12 11:01 ` Richard Biener @ 2023-04-12 20:55 ` Andrew MacLeod 2023-04-13 13:56 ` Richard Biener 0 siblings, 1 reply; 11+ messages in thread From: Andrew MacLeod @ 2023-04-12 20:55 UTC (permalink / raw) To: Richard Biener, Jakub Jelinek; +Cc: gcc-patches, hernandez, aldy [-- Attachment #1: Type: text/plain, Size: 2724 bytes --] On 4/12/23 07:01, Richard Biener wrote: > On Wed, Apr 12, 2023 at 12:59 PM Jakub Jelinek <jakub@redhat.com> wrote: >> >> Would be nice. >> >> Though, I'm afraid it still wouldn't fix the PR101912 testcase, because >> it has exactly what happens in this PR, undefined phi arg from the >> pre-header and uses of the previous iteration's value (i.e. across >> backedge). > Well yes, that's what's not allowed. So when the PHI dominates the > to-be-equivalenced argument edge src then the equivalence isn't > valid because there's a place (that very source block for example) a use of the > PHI lhs could appear and where we'd then mixup iterations. > If we want to implement this cleaner, then as you say, we don't create the equivalence if the PHI node dominates the argument edge. The attached patch does just that, removing the both the "fix" for 108139 and the just committed one for 109462, replacing them with catching this at the time of equivalence registering. It bootstraps and passes all regressions tests. Do you want me to check this into trunk? Andrew PS Of course, we still fail 101912. The only way I see us being able to do anything with that is to effectively peel the first iteration off, either physically, or logically with the path ranger to determine if a given use is actually reachable by the undefined value. <bb2> <bb 9> : # prevcorr_7 = PHI <prevcorr_19(D)(2), corr_22(8)> # leapcnt_8 = PHI <0(2), leapcnt_26(8)> if (leapcnt_8 < n_16) // 0 < n_16 goto <bb 3>; [INV] <bb 3> : corr_22 = getint (); if (corr_22 <= 0) goto <bb 7>; [INV] else goto <bb 4>; [INV] <bb 4> : _1 = corr_22 == 1; _2 = leapcnt_8 != 0; // [0, 0] = 0 != 0 _3 = _1 & _2; // [0, 0] = 0 & _2 if (_3 != 0) // 4->5 is not taken on the path starting 2->9 goto <bb 5>; [INV] else goto <bb 8>; [INV] <bb 5> : // We know this path is not taken when prevcorr_7 == prevcorr_19(D)(2) if (prevcorr_7 != 1) goto <bb 6>; [INV] else goto <bb 8>; [INV] <bb 6> : _5 = prevcorr_7 + -1; if (prevcorr_7 != 2) goto <bb 7>; [INV] else goto <bb 8>; [INV] Using the path ranger (Would it even need tweaks aldy?) , before issuing the warning the uninit code could easily start at each use, construct the path(s) to that use from the unitialized value, and determine when prevcorr is uninitialized, 2->9->3->4->5 will not be executed and of course,neither will 2->9->3->4->5->6 I think threading already does something similar? [-- Attachment #2: 462b.patch --] [-- Type: text/x-patch, Size: 4103 bytes --] commit 79b13320cf739c965bc8c7ceb8b27903271a3f6e Author: Andrew MacLeod <amacleod@redhat.com> Date: Wed Apr 12 13:10:55 2023 -0400 Ensure PHI equivalencies do not dominate the argument edge. When we create an equivalency between a PHI definition and an argument, ensure the defintion does not dominate the incoming argument edge. PR tree-optimziation/108139 PR tree-optimziation/109462 * gimple-range-cache.cc (ranger_cache::fill_block_cache): Remove equivalency check for PHI nodes. * gimple-range-fold.cc (fold_using_range::range_of_phi): Ensure def does not dominate single-arg equivalency edges. diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc index 3b52f1e734c..2314478d558 100644 --- a/gcc/gimple-range-cache.cc +++ b/gcc/gimple-range-cache.cc @@ -1220,7 +1220,7 @@ ranger_cache::fill_block_cache (tree name, basic_block bb, basic_block def_bb) // See if any equivalences can refine it. // PR 109462, like 108139 below, a one way equivalence introduced // by a PHI node can also be through the definition side. Disallow it. - if (m_oracle && !is_a<gphi *> (SSA_NAME_DEF_STMT (name))) + if (m_oracle) { tree equiv_name; relation_kind rel; @@ -1237,13 +1237,6 @@ ranger_cache::fill_block_cache (tree name, basic_block bb, basic_block def_bb) if (!m_gori.has_edge_range_p (equiv_name)) continue; - // PR 108139. It is hazardous to assume an equivalence with - // a PHI is the same value. The PHI may be an equivalence - // via UNDEFINED arguments which is really a one way equivalence. - // PHIDEF == name, but name may not be == PHIDEF. - if (is_a<gphi *> (SSA_NAME_DEF_STMT (equiv_name))) - continue; - // Check if the equiv definition dominates this block if (equiv_bb == bb || (equiv_bb && !dominated_by_p (CDI_DOMINATORS, bb, equiv_bb))) diff --git a/gcc/gimple-range-fold.cc b/gcc/gimple-range-fold.cc index e81f6b3699e..8860152d3a0 100644 --- a/gcc/gimple-range-fold.cc +++ b/gcc/gimple-range-fold.cc @@ -742,7 +742,8 @@ fold_using_range::range_of_phi (vrange &r, gphi *phi, fur_source &src) // Track if all executable arguments are the same. tree single_arg = NULL_TREE; - bool seen_arg = false; + edge single_arg_edge = NULL; + basic_block bb = gimple_bb (phi); // Start with an empty range, unioning in each argument's range. r.set_undefined (); @@ -773,13 +774,23 @@ fold_using_range::range_of_phi (vrange &r, gphi *phi, fur_source &src) src.gori ()->register_dependency (phi_def, arg); // Track if all arguments are the same. - if (!seen_arg) + if (!single_arg_edge) { - seen_arg = true; single_arg = arg; + single_arg_edge = gimple_phi_arg_edge (phi, x); } else if (single_arg != arg) single_arg = NULL_TREE; + else + { + // Check the current single edge for dominance, and if its ok, + // set it to the new edge. Otherwise not a single_arg case. + if (dom_info_available_p (CDI_DOMINATORS) + && !dominated_by_p (CDI_DOMINATORS, single_arg_edge->src, bb)) + single_arg_edge = gimple_phi_arg_edge (phi, x); + else + single_arg = NULL_TREE; + } } // Once the value reaches varying, stop looking. @@ -795,9 +806,14 @@ fold_using_range::range_of_phi (vrange &r, gphi *phi, fur_source &src) // If the PHI boils down to a single effective argument, look at it. if (single_arg) { - // Symbolic arguments are equivalences. if (gimple_range_ssa_p (single_arg)) - src.register_relation (phi, VREL_EQ, phi_def, single_arg); + { + // Register an equivalence only if the PHI does not dominate + // the argmuent edge. See PR 108139/109462. + if (dom_info_available_p (CDI_DOMINATORS) + && !dominated_by_p (CDI_DOMINATORS, single_arg_edge->src, bb)) + src.register_relation (phi, VREL_EQ, phi_def, single_arg); + } else if (src.get_operand (arg_range, single_arg) && arg_range.singleton_p ()) { ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [PATCH] PR tree-optimization/109462 - Don't use ANY PHI equivalences in range-on-entry. 2023-04-12 20:55 ` Andrew MacLeod @ 2023-04-13 13:56 ` Richard Biener 2023-04-13 15:48 ` Andrew MacLeod 0 siblings, 1 reply; 11+ messages in thread From: Richard Biener @ 2023-04-13 13:56 UTC (permalink / raw) To: Andrew MacLeod; +Cc: Jakub Jelinek, gcc-patches, hernandez, aldy On Wed, Apr 12, 2023 at 10:55 PM Andrew MacLeod <amacleod@redhat.com> wrote: > > > On 4/12/23 07:01, Richard Biener wrote: > > On Wed, Apr 12, 2023 at 12:59 PM Jakub Jelinek <jakub@redhat.com> wrote: > >> > >> Would be nice. > >> > >> Though, I'm afraid it still wouldn't fix the PR101912 testcase, because > >> it has exactly what happens in this PR, undefined phi arg from the > >> pre-header and uses of the previous iteration's value (i.e. across > >> backedge). > > Well yes, that's what's not allowed. So when the PHI dominates the > > to-be-equivalenced argument edge src then the equivalence isn't > > valid because there's a place (that very source block for example) a use of the > > PHI lhs could appear and where we'd then mixup iterations. > > > If we want to implement this cleaner, then as you say, we don't create > the equivalence if the PHI node dominates the argument edge. The > attached patch does just that, removing the both the "fix" for 108139 > and the just committed one for 109462, replacing them with catching this > at the time of equivalence registering. > > It bootstraps and passes all regressions tests. > Do you want me to check this into trunk? Uh, it looks a bit convoluted. Wouldn't the following be enough? OK if that works (or fixed if I messed up trivially) diff --git a/gcc/gimple-range-fold.cc b/gcc/gimple-range-fold.cc index e81f6b3699e..9c29012e160 100644 --- a/gcc/gimple-range-fold.cc +++ b/gcc/gimple-range-fold.cc @@ -776,7 +776,11 @@ fold_using_range::range_of_phi (vrange &r, gphi *phi, fur_source &src) if (!seen_arg) { seen_arg = true; - single_arg = arg; + // Avoid registering an equivalence if the PHI dominates the + // argument edge. See PR 108139/109462. + if (dom_info_available_p (CDI_DOMINATORS) + && !dominated_by_p (CDI_DOMINATORS, e->src, gimple_bb (phi))) + single_arg = arg; } else if (single_arg != arg) single_arg = NULL_TREE; > Andrew > > PS Of course, we still fail 101912. The only way I see us being > able to do anything with that is to effectively peel the first iteration > off, either physically, or logically with the path ranger to determine > if a given use is actually reachable by the undefined value. > > <bb2> > > <bb 9> : > # prevcorr_7 = PHI <prevcorr_19(D)(2), corr_22(8)> > # leapcnt_8 = PHI <0(2), leapcnt_26(8)> > if (leapcnt_8 < n_16) // 0 < n_16 > goto <bb 3>; [INV] > > <bb 3> : > corr_22 = getint (); > if (corr_22 <= 0) > goto <bb 7>; [INV] > else > goto <bb 4>; [INV] > > <bb 4> : > _1 = corr_22 == 1; > _2 = leapcnt_8 != 0; // [0, 0] = 0 != 0 > _3 = _1 & _2; // [0, 0] = 0 & _2 > if (_3 != 0) // 4->5 is not taken on the path starting > 2->9 > goto <bb 5>; [INV] > else > goto <bb 8>; [INV] > > <bb 5> : // We know this path is not taken when > prevcorr_7 == prevcorr_19(D)(2) > if (prevcorr_7 != 1) > goto <bb 6>; [INV] > else > goto <bb 8>; [INV] > > <bb 6> : > _5 = prevcorr_7 + -1; > if (prevcorr_7 != 2) > goto <bb 7>; [INV] > else > goto <bb 8>; [INV] > > Using the path ranger (Would it even need tweaks aldy?) , before issuing > the warning the uninit code could easily start at each use, construct > the path(s) to that use from the unitialized value, and determine when > prevcorr is uninitialized, 2->9->3->4->5 will not be executed and of > course,neither will 2->9->3->4->5->6 > > I think threading already does something similar? It does quite more convoluted things than that - it computes predicates on paths with its own representation & simplifications. It might be worth trying if replacing this with a lot of path rangers would help - but then it heavily relies on relation simplification it implements (and at the same time it does that very imperfectly). Richard. > > ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [PATCH] PR tree-optimization/109462 - Don't use ANY PHI equivalences in range-on-entry. 2023-04-13 13:56 ` Richard Biener @ 2023-04-13 15:48 ` Andrew MacLeod 2023-04-13 16:18 ` Richard Biener 2023-04-13 16:20 ` Richard Biener 0 siblings, 2 replies; 11+ messages in thread From: Andrew MacLeod @ 2023-04-13 15:48 UTC (permalink / raw) To: Richard Biener; +Cc: Jakub Jelinek, gcc-patches, hernandez, aldy [-- Attachment #1: Type: text/plain, Size: 3515 bytes --] On 4/13/23 09:56, Richard Biener wrote: > On Wed, Apr 12, 2023 at 10:55 PM Andrew MacLeod <amacleod@redhat.com> wrote: >> >> On 4/12/23 07:01, Richard Biener wrote: >>> On Wed, Apr 12, 2023 at 12:59 PM Jakub Jelinek <jakub@redhat.com> wrote: >>>> Would be nice. >>>> >>>> Though, I'm afraid it still wouldn't fix the PR101912 testcase, because >>>> it has exactly what happens in this PR, undefined phi arg from the >>>> pre-header and uses of the previous iteration's value (i.e. across >>>> backedge). >>> Well yes, that's what's not allowed. So when the PHI dominates the >>> to-be-equivalenced argument edge src then the equivalence isn't >>> valid because there's a place (that very source block for example) a use of the >>> PHI lhs could appear and where we'd then mixup iterations. >>> >> If we want to implement this cleaner, then as you say, we don't create >> the equivalence if the PHI node dominates the argument edge. The >> attached patch does just that, removing the both the "fix" for 108139 >> and the just committed one for 109462, replacing them with catching this >> at the time of equivalence registering. >> >> It bootstraps and passes all regressions tests. >> Do you want me to check this into trunk? > Uh, it looks a bit convoluted. Wouldn't the following be enough? OK > if that works > (or fixed if I messed up trivially) > > diff --git a/gcc/gimple-range-fold.cc b/gcc/gimple-range-fold.cc > index e81f6b3699e..9c29012e160 100644 > --- a/gcc/gimple-range-fold.cc > +++ b/gcc/gimple-range-fold.cc > @@ -776,7 +776,11 @@ fold_using_range::range_of_phi (vrange &r, gphi > *phi, fur_source &src) > if (!seen_arg) > { > seen_arg = true; > - single_arg = arg; > + // Avoid registering an equivalence if the PHI dominates the > + // argument edge. See PR 108139/109462. > + if (dom_info_available_p (CDI_DOMINATORS) > + && !dominated_by_p (CDI_DOMINATORS, e->src, gimple_bb (phi))) > + single_arg = arg; > } > else if (single_arg != arg) > single_arg = NULL_TREE; > > It would exposes a slight hole.. in cases where there is more than one copy of the name, ie: for a_2 = PHI <c_3, c_3> we currently will create an equivalence between a_2 and c_3 because its considered a single argument. Not a big deal for this case since all arguments are c_3, but the hole would be when we have something like: a_2 = PHI<c_3, c_3, d_4(D)> if d_4 is undefined, then with the above patch we would only check the dominance of the first edge with c_3. we'd need to check all of them. The patch is slightly convoluted because we always defer checking the edge/processing single arguments until we think there is a reason to (for performance). My patch simple does the deferred check on the previous edge and sets the new one so that we would check both edges are valid before setting the equivalence. Even as it is with this deferred check we're about 0.4% slower in VRP. IF we didnt do this deferring, then every PHI is going to have a check. And along the way, remove the boolean seen_arg because having single_arg_edge set produces the same information. Perhaps it would be cleaner to simply defer the entire thing to the end, like so. Performance is pretty much identical in the end. Bootstraps on x86_64-pc-linux-gnu, regressions are running. Assuming no regressions pop up, OK for trunk? Andrew [-- Attachment #2: 462c.patch --] [-- Type: text/x-patch, Size: 3247 bytes --] commit 9e16ef8e4de26bdc6e570bd327bbe15845491169 Author: Andrew MacLeod <amacleod@redhat.com> Date: Wed Apr 12 13:10:55 2023 -0400 Ensure PHI equivalencies do not dominate the argument edge. When we create an equivalency between a PHI definition and an argument, ensure the definition does not dominate the incoming argument edge. PR tree-optimziation/108139 PR tree-optimziation/109462 * gimple-range-cache.cc (ranger_cache::fill_block_cache): Remove equivalency check for PHI nodes. * gimple-range-fold.cc (fold_using_range::range_of_phi): Ensure def does not dominate single-arg equivalency edges. diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc index 3b52f1e734c..2314478d558 100644 --- a/gcc/gimple-range-cache.cc +++ b/gcc/gimple-range-cache.cc @@ -1220,7 +1220,7 @@ ranger_cache::fill_block_cache (tree name, basic_block bb, basic_block def_bb) // See if any equivalences can refine it. // PR 109462, like 108139 below, a one way equivalence introduced // by a PHI node can also be through the definition side. Disallow it. - if (m_oracle && !is_a<gphi *> (SSA_NAME_DEF_STMT (name))) + if (m_oracle) { tree equiv_name; relation_kind rel; @@ -1237,13 +1237,6 @@ ranger_cache::fill_block_cache (tree name, basic_block bb, basic_block def_bb) if (!m_gori.has_edge_range_p (equiv_name)) continue; - // PR 108139. It is hazardous to assume an equivalence with - // a PHI is the same value. The PHI may be an equivalence - // via UNDEFINED arguments which is really a one way equivalence. - // PHIDEF == name, but name may not be == PHIDEF. - if (is_a<gphi *> (SSA_NAME_DEF_STMT (equiv_name))) - continue; - // Check if the equiv definition dominates this block if (equiv_bb == bb || (equiv_bb && !dominated_by_p (CDI_DOMINATORS, bb, equiv_bb))) diff --git a/gcc/gimple-range-fold.cc b/gcc/gimple-range-fold.cc index e81f6b3699e..429734f954a 100644 --- a/gcc/gimple-range-fold.cc +++ b/gcc/gimple-range-fold.cc @@ -795,9 +795,28 @@ fold_using_range::range_of_phi (vrange &r, gphi *phi, fur_source &src) // If the PHI boils down to a single effective argument, look at it. if (single_arg) { - // Symbolic arguments are equivalences. + // Symbolic arguments can be equivalences. if (gimple_range_ssa_p (single_arg)) - src.register_relation (phi, VREL_EQ, phi_def, single_arg); + { + // Only allow the equivalence if the PHI definition does not + // dominate any incoming edge for SINGLE_ARG. + // See PR 108139 and 109462. + basic_block bb = gimple_bb (phi); + if (!dom_info_available_p (CDI_DOMINATORS)) + single_arg = NULL; + else + for (x = 0; x < gimple_phi_num_args (phi); x++) + if (gimple_phi_arg_def (phi, x) == single_arg + && dominated_by_p (CDI_DOMINATORS, + gimple_phi_arg_edge (phi, x)->src, + bb)) + { + single_arg = NULL; + break; + } + if (single_arg) + src.register_relation (phi, VREL_EQ, phi_def, single_arg); + } else if (src.get_operand (arg_range, single_arg) && arg_range.singleton_p ()) { ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [PATCH] PR tree-optimization/109462 - Don't use ANY PHI equivalences in range-on-entry. 2023-04-13 15:48 ` Andrew MacLeod @ 2023-04-13 16:18 ` Richard Biener 2023-04-13 16:20 ` Richard Biener 1 sibling, 0 replies; 11+ messages in thread From: Richard Biener @ 2023-04-13 16:18 UTC (permalink / raw) To: Andrew MacLeod; +Cc: Jakub Jelinek, gcc-patches, hernandez, aldy > Am 13.04.2023 um 17:49 schrieb Andrew MacLeod <amacleod@redhat.com>: > > >> On 4/13/23 09:56, Richard Biener wrote: >>> On Wed, Apr 12, 2023 at 10:55 PM Andrew MacLeod <amacleod@redhat.com> wrote: >>> >>> On 4/12/23 07:01, Richard Biener wrote: >>>> On Wed, Apr 12, 2023 at 12:59 PM Jakub Jelinek <jakub@redhat.com> wrote: >>>>> Would be nice. >>>>> >>>>> Though, I'm afraid it still wouldn't fix the PR101912 testcase, because >>>>> it has exactly what happens in this PR, undefined phi arg from the >>>>> pre-header and uses of the previous iteration's value (i.e. across >>>>> backedge). >>>> Well yes, that's what's not allowed. So when the PHI dominates the >>>> to-be-equivalenced argument edge src then the equivalence isn't >>>> valid because there's a place (that very source block for example) a use of the >>>> PHI lhs could appear and where we'd then mixup iterations. >>>> >>> If we want to implement this cleaner, then as you say, we don't create >>> the equivalence if the PHI node dominates the argument edge. The >>> attached patch does just that, removing the both the "fix" for 108139 >>> and the just committed one for 109462, replacing them with catching this >>> at the time of equivalence registering. >>> >>> It bootstraps and passes all regressions tests. >>> Do you want me to check this into trunk? >> Uh, it looks a bit convoluted. Wouldn't the following be enough? OK >> if that works >> (or fixed if I messed up trivially) >> >> diff --git a/gcc/gimple-range-fold.cc b/gcc/gimple-range-fold.cc >> index e81f6b3699e..9c29012e160 100644 >> --- a/gcc/gimple-range-fold.cc >> +++ b/gcc/gimple-range-fold.cc >> @@ -776,7 +776,11 @@ fold_using_range::range_of_phi (vrange &r, gphi >> *phi, fur_source &src) >> if (!seen_arg) >> { >> seen_arg = true; >> - single_arg = arg; >> + // Avoid registering an equivalence if the PHI dominates the >> + // argument edge. See PR 108139/109462. >> + if (dom_info_available_p (CDI_DOMINATORS) >> + && !dominated_by_p (CDI_DOMINATORS, e->src, gimple_bb (phi))) >> + single_arg = arg; >> } >> else if (single_arg != arg) >> single_arg = NULL_TREE; >> >> > It would exposes a slight hole.. in cases where there is more than one copy of the name, ie: > > for a_2 = PHI <c_3, c_3> we currently will create an equivalence between a_2 and c_3 because its considered a single argument. Not a big deal for this case since all arguments are c_3, but the hole would be when we have something like: > > a_2 = PHI<c_3, c_3, d_4(D)> if d_4 is undefined, then with the above patch we would only check the dominance of the first edge with c_3. we'd need to check all of them. I didn’t think so, but on a second thought for multiple backedges and an irreducible region you are right. Once we see an edge with the reverse domination we’re fine though. I originally checked all edges but thought checking the first is enough. > The patch is slightly convoluted because we always defer checking the edge/processing single arguments until we think there is a reason to (for performance). My patch simple does the deferred check on the previous edge and sets the new one so that we would check both edges are valid before setting the equivalence. Even as it is with this deferred check we're about 0.4% slower in VRP. IF we didnt do this deferring, then every PHI is going to have a check. > > And along the way, remove the boolean seen_arg because having single_arg_edge set produces the same information. > > Perhaps it would be cleaner to simply defer the entire thing to the end, like so. > Performance is pretty much identical in the end. > > Bootstraps on x86_64-pc-linux-gnu, regressions are running. Assuming no regressions pop up, OK for trunk? > > Andrew > > > > > > <462c.patch> ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [PATCH] PR tree-optimization/109462 - Don't use ANY PHI equivalences in range-on-entry. 2023-04-13 15:48 ` Andrew MacLeod 2023-04-13 16:18 ` Richard Biener @ 2023-04-13 16:20 ` Richard Biener 1 sibling, 0 replies; 11+ messages in thread From: Richard Biener @ 2023-04-13 16:20 UTC (permalink / raw) To: Andrew MacLeod; +Cc: Jakub Jelinek, gcc-patches, hernandez, aldy > Am 13.04.2023 um 17:49 schrieb Andrew MacLeod <amacleod@redhat.com>: > > >> On 4/13/23 09:56, Richard Biener wrote: >>> On Wed, Apr 12, 2023 at 10:55 PM Andrew MacLeod <amacleod@redhat.com> wrote: >>> >>> On 4/12/23 07:01, Richard Biener wrote: >>>> On Wed, Apr 12, 2023 at 12:59 PM Jakub Jelinek <jakub@redhat.com> wrote: >>>>> Would be nice. >>>>> >>>>> Though, I'm afraid it still wouldn't fix the PR101912 testcase, because >>>>> it has exactly what happens in this PR, undefined phi arg from the >>>>> pre-header and uses of the previous iteration's value (i.e. across >>>>> backedge). >>>> Well yes, that's what's not allowed. So when the PHI dominates the >>>> to-be-equivalenced argument edge src then the equivalence isn't >>>> valid because there's a place (that very source block for example) a use of the >>>> PHI lhs could appear and where we'd then mixup iterations. >>>> >>> If we want to implement this cleaner, then as you say, we don't create >>> the equivalence if the PHI node dominates the argument edge. The >>> attached patch does just that, removing the both the "fix" for 108139 >>> and the just committed one for 109462, replacing them with catching this >>> at the time of equivalence registering. >>> >>> It bootstraps and passes all regressions tests. >>> Do you want me to check this into trunk? >> Uh, it looks a bit convoluted. Wouldn't the following be enough? OK >> if that works >> (or fixed if I messed up trivially) >> >> diff --git a/gcc/gimple-range-fold.cc b/gcc/gimple-range-fold.cc >> index e81f6b3699e..9c29012e160 100644 >> --- a/gcc/gimple-range-fold.cc >> +++ b/gcc/gimple-range-fold.cc >> @@ -776,7 +776,11 @@ fold_using_range::range_of_phi (vrange &r, gphi >> *phi, fur_source &src) >> if (!seen_arg) >> { >> seen_arg = true; >> - single_arg = arg; >> + // Avoid registering an equivalence if the PHI dominates the >> + // argument edge. See PR 108139/109462. >> + if (dom_info_available_p (CDI_DOMINATORS) >> + && !dominated_by_p (CDI_DOMINATORS, e->src, gimple_bb (phi))) >> + single_arg = arg; >> } >> else if (single_arg != arg) >> single_arg = NULL_TREE; >> >> > It would exposes a slight hole.. in cases where there is more than one copy of the name, ie: > > for a_2 = PHI <c_3, c_3> we currently will create an equivalence between a_2 and c_3 because its considered a single argument. Not a big deal for this case since all arguments are c_3, but the hole would be when we have something like: > > a_2 = PHI<c_3, c_3, d_4(D)> if d_4 is undefined, then with the above patch we would only check the dominance of the first edge with c_3. we'd need to check all of them. > > The patch is slightly convoluted because we always defer checking the edge/processing single arguments until we think there is a reason to (for performance). My patch simple does the deferred check on the previous edge and sets the new one so that we would check both edges are valid before setting the equivalence. Even as it is with this deferred check we're about 0.4% slower in VRP. IF we didnt do this deferring, then every PHI is going to have a check. > > And along the way, remove the boolean seen_arg because having single_arg_edge set produces the same information. > > Perhaps it would be cleaner to simply defer the entire thing to the end, like so. > Performance is pretty much identical in the end. > > Bootstraps on x86_64-pc-linux-gnu, regressions are running. Assuming no regressions pop up, OK for trunk? Yes. I like this more. OK Richard > Andrew > > > > > > <462c.patch> ^ permalink raw reply [flat|nested] 11+ messages in thread
end of thread, other threads:[~2023-04-13 16:20 UTC | newest] Thread overview: 11+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2023-04-11 23:52 [PATCH] PR tree-optimization/109462 - Don't use ANY PHI equivalences in range-on-entry Andrew MacLeod 2023-04-12 8:20 ` Jakub Jelinek 2023-04-12 13:12 ` Andrew MacLeod 2023-04-12 9:12 ` Richard Biener 2023-04-12 10:58 ` Jakub Jelinek 2023-04-12 11:01 ` Richard Biener 2023-04-12 20:55 ` Andrew MacLeod 2023-04-13 13:56 ` Richard Biener 2023-04-13 15:48 ` Andrew MacLeod 2023-04-13 16:18 ` Richard Biener 2023-04-13 16:20 ` Richard Biener
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).