| Message ID | 4eef6ceb-23ba-da47-8899-d5b08143cba5@redhat.com |
|---|---|
| State | New |
| Headers | show |
| Series | [committed] Fix bogus propagation in DOM | expand |
On Sun, Nov 19, 2017 at 9:16 PM, Jeff Law <law@redhat.com> wrote: > On my local branch gcc.dg/torture/pr56349.c fails by sending GCC into an > infinite loop trying to simplify a self-referring statement. ie > something like > > x_1 = x_1 + 10; > > That, of course, shouldn't be happening in SSA form. After some digging > I've found the culprit. > > Let's say we've got a PHI. > > a_1 = PHI (a_0, a_2) > > If DOM decides that the edge associated with a_2 is not executable, then > DOM will consider the PHI a degenerate and enter a_1 = a_0 into its > equivalence table. > > That in turn will result in propagation of a_0 into uses of a_1. > > That, of course, isn't right. There's nothing that guarantees that the > definition of a_0 dominates the uses of a_1. In the testcase that bogus > propagation cascades and eventually results in a self-referring node > like I showed above. > > The solution here is to note whether or not we ignored any PHI > arguments. If we do and the equivalence we want to enter is SSA_NAME = > SSA_NAME, then we must reject the equivalence. Obviously if we wanted > to enter SSA_NAME = CONST, then we can still do so. > > Bootstrapped and regression tested on x86_64. Installing on the trunk. Hmm, but if the edge isn't executable then it will be removed and thus the definition _will_ dominate. So I think the error happens elsewhere. With the change you remove one of the advantages of tracking unexecutable edges, namely that we can treat those merges optimistically resulting in more CSE. You didn't add a testcase so I can't have a quick look myself. Short: I think you're papering over an issue elsehwere. Richard. > jeff > > commit 2b37e05b327e6b1170f72c51c21681b1dc5b8337 > Author: Jeff Law <law@redhat.com> > Date: Sun Nov 19 13:14:55 2017 -0700 > > * tree-ssa-dom.c (record_equivalences_from_phis): Fix handling > of degenerates resulting from ignoring an edge. > > diff --git a/gcc/ChangeLog b/gcc/ChangeLog > index ae05dacf791..5ce981d0871 100644 > --- a/gcc/ChangeLog > +++ b/gcc/ChangeLog > @@ -1,3 +1,8 @@ > +2017-11-19 Jeff Law <law@redhat.com> > + > + * tree-ssa-dom.c (record_equivalences_from_phis): Fix handling > + of degenerates resulting from ignoring an edge. > + > 2017-11-19 Jan Hubicka <hubicka@ucw.cz> > > PR ipa/81360 > diff --git a/gcc/tree-ssa-dom.c b/gcc/tree-ssa-dom.c > index eb85b4a09ad..916d66134c3 100644 > --- a/gcc/tree-ssa-dom.c > +++ b/gcc/tree-ssa-dom.c > @@ -1011,6 +1011,7 @@ record_equivalences_from_phis (basic_block bb) > tree rhs = NULL; > size_t i; > > + bool ignored_phi_arg = false; > for (i = 0; i < gimple_phi_num_args (phi); i++) > { > tree t = gimple_phi_arg_def (phi, i); > @@ -1021,10 +1022,14 @@ record_equivalences_from_phis (basic_block bb) > if (lhs == t) > continue; > > - /* If the associated edge is not marked as executable, then it > - can be ignored. */ > + /* We want to track if we ignored any PHI arguments because > + their associated edges were not executable. This impacts > + whether or not we can use any equivalence we might discover. */ > if ((gimple_phi_arg_edge (phi, i)->flags & EDGE_EXECUTABLE) == 0) > - continue; > + { > + ignored_phi_arg = true; > + continue; > + } > > t = dom_valueize (t); > > @@ -1049,9 +1054,15 @@ record_equivalences_from_phis (basic_block bb) > a useful equivalence. We do not need to record unwind data for > this, since this is a true assignment and not an equivalence > inferred from a comparison. All uses of this ssa name are dominated > - by this assignment, so unwinding just costs time and space. */ > + by this assignment, so unwinding just costs time and space. > + > + Note that if we ignored a PHI argument and the resulting equivalence > + is SSA_NAME = SSA_NAME. Then we can not use the equivalence as the > + uses of the LHS SSA_NAME are not necessarily dominated by the > + assignment of the RHS SSA_NAME. */ > if (i == gimple_phi_num_args (phi) > - && may_propagate_copy (lhs, rhs)) > + && may_propagate_copy (lhs, rhs) > + && (!ignored_phi_arg || TREE_CODE (rhs) != SSA_NAME)) > set_ssa_name_value (lhs, rhs); > } > } >
On 11/20/2017 03:25 AM, Richard Biener wrote: > On Sun, Nov 19, 2017 at 9:16 PM, Jeff Law <law@redhat.com> wrote: >> On my local branch gcc.dg/torture/pr56349.c fails by sending GCC into an >> infinite loop trying to simplify a self-referring statement. ie >> something like >> >> x_1 = x_1 + 10; >> >> That, of course, shouldn't be happening in SSA form. After some digging >> I've found the culprit. >> >> Let's say we've got a PHI. >> >> a_1 = PHI (a_0, a_2) >> >> If DOM decides that the edge associated with a_2 is not executable, then >> DOM will consider the PHI a degenerate and enter a_1 = a_0 into its >> equivalence table. >> >> That in turn will result in propagation of a_0 into uses of a_1. >> >> That, of course, isn't right. There's nothing that guarantees that the >> definition of a_0 dominates the uses of a_1. In the testcase that bogus >> propagation cascades and eventually results in a self-referring node >> like I showed above. >> >> The solution here is to note whether or not we ignored any PHI >> arguments. If we do and the equivalence we want to enter is SSA_NAME = >> SSA_NAME, then we must reject the equivalence. Obviously if we wanted >> to enter SSA_NAME = CONST, then we can still do so. >> >> Bootstrapped and regression tested on x86_64. Installing on the trunk. > > Hmm, but if the edge isn't executable then it will be removed and thus the > definition _will_ dominate. So I think the error happens elsewhere. With > the change you remove one of the advantages of tracking unexecutable > edges, namely that we can treat those merges optimistically resulting in > more CSE. > > You didn't add a testcase so I can't have a quick look myself. > > Short: I think you're papering over an issue elsehwere. Depends on your point of view :-) It's not something I think you can trigger on the trunk right now. But the testcase is pr56349. You need the embedded vrp bits installed into DOM and for DOM to also use those bits to detect branches that have a static destination. So I'll just walk you through it... At the start of the second DOM pass we have this: f () { int k__lsm.8; int * k; int a; int _2; int b.0_3; int _4; unsigned int ivtmp_5; int _6; short int iftmp.3_14; int _15; int b.4_25; short int iftmp.3_27; short int c.2_33; unsigned int ivtmp_38; ;; basic block 2, loop depth 0 ;; pred: ENTRY a_9 = 1; ivtmp_38 = 1; a_31 = a_9 + 1; ivtmp_5 = ivtmp_38 + 4294967295; _2 = 1; b.0_3 = b; _4 = b.0_3 | _2; b = _4; if (_4 == 0) goto <bb 12>; [66.00%] else goto <bb 10>; [34.00%] ;; succ: 12 ;; 10 ;; basic block 3, loop depth 1 ;; pred: 5 ;; 3 goto <bb 3>; [100.00%] ;; succ: 3 ;; basic block 4, loop depth 0 ;; pred: 11 ;; 12 lbl1: c.2_33 = c; ;; succ: 5 ;; basic block 5, loop depth 1 ;; pred: 4 ;; 5 if (c.2_33 != 0) goto <bb 3>; [85.00%] else goto <bb 5>; [15.00%] ;; succ: 3 ;; 5 ;; basic block 6, loop depth 0 ;; pred: 11 b.4_25 = b; if (b.4_25 != 0) goto <bb 7>; [50.00%] else goto <bb 8>; [50.00%] ;; succ: 7 ;; 8 ;; basic block 7, loop depth 0 ;; pred: 6 iftmp.3_27 = (short int) b.4_25; goto <bb 9>; [100.00%] ;; succ: 9 ;; basic block 8, loop depth 0 ;; pred: 6 ;; 12 # k_37 = PHI <k_30(6), 0B(12)> ;; succ: 9 ;; basic block 9, loop depth 0 ;; pred: 7 ;; 8 # iftmp.3_14 = PHI <iftmp.3_27(7), 2(8)> # k_44 = PHI <k_30(7), k_37(8)> c = iftmp.3_14; if (iftmp.3_14 != 0) goto <bb 10>; [50.00%] else goto <bb 11>; [50.00%] ;; succ: 10 ;; 11 ;; basic block 10, loop depth 0 ;; pred: 2 ;; 9 # k_10 = PHI <0B(2), k_44(9)> lbl2: b = 0; ;; succ: 11 ;; basic block 11, loop depth 0 ;; pred: 10 ;; 9 # k_11 = PHI <k_10(10), k_44(9)> k_30 = k_11 + 4; _6 = MEM[(int *)k_11 + 4B]; if (_6 != 0) goto <bb 6>; [66.00%] else goto <bb 4>; [34.00%] ;; succ: 6 ;; 4 ;; basic block 12, loop depth 0 ;; pred: 2 _15 = MEM[(int *)0B]; if (_15 != 0) goto <bb 8>; [66.00%] else goto <bb 4>; [34.00%] ;; succ: 8 ;; 4 } The first tidbit of interest is we can statically determine that bb2 will always transfer control to bb10. The edge 2->12 is marked as not executable. That also means that 12->4 and 12->8 are not executable as well. The PHI in BB8 is critical: # k_37 = PHI <k_30(6), 0B(12)> With the edge 8->12 being unexecutable the PHI is essentially k_37 = k_30 and we'll try to propagate k_30 into the uses of k_37. The first use of interest is BB9. # k_44 = PHI <k_30(7), k_37(8)> Which turns into # k_44 = PHI <k_30(7), k_30(8)> And we've lost. The assignment to k_30 does not currently dominate k_44 and won't until after we've done cfg cleanups and updated the dominator information. How does this matter? We have to continue to follow things through DOM. We can then propagate k_30 into uses of k_44, which we do for the PHIs in BB10 and BB11 which turn into: <bb 10> [local count: 0]: # k_10 = PHI <0B(2), k_30(9)> <bb 11> [local count: 1]: # k_11 = PHI <k_10(10), k_30(9)> k_30 = k_11 + 4; _6 = MEM[(int *)k_11 + 4B]; if (_6 != 0) goto <bb 6>; [66.00%] else goto <bb 4>; [34.00%] Now the fun part. After we have finished optimizing bb9, we try to thread its outgoing edges. Of particular interest is the edge 9->11. We do temporary propagation as part of the jump threading process. ie, when we traverse 9->11 we know that k_11 will have the value k_30. So we transform the assignment k_30 = k_11 + 4 into k_30 = k_30 + 4 Then we try to simplify that statement and infinitely recurse. I considered trying to key behavior on EDGE_DFS_BACK (6->8). It'd be something like don't record equivalences from a degenerate PHI where the remaining edge(s) are EDGE_DFS_BACK. But I just couldn't convince myself that was actually reasonable or sufficient in general. Jeff
On Mon, Nov 20, 2017 at 7:33 PM, Jeff Law <law@redhat.com> wrote: > On 11/20/2017 03:25 AM, Richard Biener wrote: >> On Sun, Nov 19, 2017 at 9:16 PM, Jeff Law <law@redhat.com> wrote: >>> On my local branch gcc.dg/torture/pr56349.c fails by sending GCC into an >>> infinite loop trying to simplify a self-referring statement. ie >>> something like >>> >>> x_1 = x_1 + 10; >>> >>> That, of course, shouldn't be happening in SSA form. After some digging >>> I've found the culprit. >>> >>> Let's say we've got a PHI. >>> >>> a_1 = PHI (a_0, a_2) >>> >>> If DOM decides that the edge associated with a_2 is not executable, then >>> DOM will consider the PHI a degenerate and enter a_1 = a_0 into its >>> equivalence table. >>> >>> That in turn will result in propagation of a_0 into uses of a_1. >>> >>> That, of course, isn't right. There's nothing that guarantees that the >>> definition of a_0 dominates the uses of a_1. In the testcase that bogus >>> propagation cascades and eventually results in a self-referring node >>> like I showed above. >>> >>> The solution here is to note whether or not we ignored any PHI >>> arguments. If we do and the equivalence we want to enter is SSA_NAME = >>> SSA_NAME, then we must reject the equivalence. Obviously if we wanted >>> to enter SSA_NAME = CONST, then we can still do so. >>> >>> Bootstrapped and regression tested on x86_64. Installing on the trunk. >> >> Hmm, but if the edge isn't executable then it will be removed and thus the >> definition _will_ dominate. So I think the error happens elsewhere. With >> the change you remove one of the advantages of tracking unexecutable >> edges, namely that we can treat those merges optimistically resulting in >> more CSE. >> >> You didn't add a testcase so I can't have a quick look myself. >> >> Short: I think you're papering over an issue elsehwere. > Depends on your point of view :-) > > It's not something I think you can trigger on the trunk right now. But > the testcase is pr56349. You need the embedded vrp bits installed into > DOM and for DOM to also use those bits to detect branches that have a > static destination. > > So I'll just walk you through it... > > At the start of the second DOM pass we have this: > > f () > { > int k__lsm.8; > int * k; > int a; > int _2; > int b.0_3; > int _4; > unsigned int ivtmp_5; > int _6; > short int iftmp.3_14; > int _15; > int b.4_25; > short int iftmp.3_27; > short int c.2_33; > unsigned int ivtmp_38; > > ;; basic block 2, loop depth 0 > ;; pred: ENTRY > a_9 = 1; > ivtmp_38 = 1; > a_31 = a_9 + 1; > ivtmp_5 = ivtmp_38 + 4294967295; > _2 = 1; > b.0_3 = b; > _4 = b.0_3 | _2; > b = _4; > if (_4 == 0) > goto <bb 12>; [66.00%] > else > goto <bb 10>; [34.00%] > ;; succ: 12 > ;; 10 > > ;; basic block 3, loop depth 1 > ;; pred: 5 > ;; 3 > goto <bb 3>; [100.00%] > ;; succ: 3 > > ;; basic block 4, loop depth 0 > ;; pred: 11 > ;; 12 > lbl1: > c.2_33 = c; > ;; succ: 5 > > ;; basic block 5, loop depth 1 > ;; pred: 4 > ;; 5 > if (c.2_33 != 0) > goto <bb 3>; [85.00%] > else > goto <bb 5>; [15.00%] > ;; succ: 3 > ;; 5 > > ;; basic block 6, loop depth 0 > ;; pred: 11 > b.4_25 = b; > if (b.4_25 != 0) > goto <bb 7>; [50.00%] > else > goto <bb 8>; [50.00%] > ;; succ: 7 > ;; 8 > > ;; basic block 7, loop depth 0 > ;; pred: 6 > iftmp.3_27 = (short int) b.4_25; > goto <bb 9>; [100.00%] > ;; succ: 9 > > ;; basic block 8, loop depth 0 > ;; pred: 6 > ;; 12 > # k_37 = PHI <k_30(6), 0B(12)> > ;; succ: 9 > > ;; basic block 9, loop depth 0 > ;; pred: 7 > ;; 8 > # iftmp.3_14 = PHI <iftmp.3_27(7), 2(8)> > # k_44 = PHI <k_30(7), k_37(8)> > c = iftmp.3_14; > if (iftmp.3_14 != 0) > goto <bb 10>; [50.00%] > else > goto <bb 11>; [50.00%] > ;; succ: 10 > ;; 11 > > ;; basic block 10, loop depth 0 > ;; pred: 2 > ;; 9 > # k_10 = PHI <0B(2), k_44(9)> > lbl2: > b = 0; > ;; succ: 11 > > ;; basic block 11, loop depth 0 > ;; pred: 10 > ;; 9 > # k_11 = PHI <k_10(10), k_44(9)> > k_30 = k_11 + 4; > _6 = MEM[(int *)k_11 + 4B]; > if (_6 != 0) > goto <bb 6>; [66.00%] > else > goto <bb 4>; [34.00%] > ;; succ: 6 > ;; 4 > > ;; basic block 12, loop depth 0 > ;; pred: 2 > _15 = MEM[(int *)0B]; > if (_15 != 0) > goto <bb 8>; [66.00%] > else > goto <bb 4>; [34.00%] > ;; succ: 8 > ;; 4 > > } > > The first tidbit of interest is we can statically determine that bb2 > will always transfer control to bb10. The edge 2->12 is marked as not > executable. That also means that 12->4 and 12->8 are not executable as > well. > > The PHI in BB8 is critical: > > # k_37 = PHI <k_30(6), 0B(12)> > > With the edge 8->12 being unexecutable the PHI is essentially k_37 = > k_30 and we'll try to propagate k_30 into the uses of k_37. > > The first use of interest is BB9. > > > # k_44 = PHI <k_30(7), k_37(8)> > > Which turns into > # k_44 = PHI <k_30(7), k_30(8)> > > And we've lost. The assignment to k_30 does not currently dominate k_44 > and won't until after we've done cfg cleanups and updated the dominator > information. > > How does this matter? We have to continue to follow things through DOM. > > > We can then propagate k_30 into uses of k_44, which we do for the PHIs > in BB10 and BB11 which turn into: > > <bb 10> [local count: 0]: > # k_10 = PHI <0B(2), k_30(9)> > > > <bb 11> [local count: 1]: > # k_11 = PHI <k_10(10), k_30(9)> > k_30 = k_11 + 4; > _6 = MEM[(int *)k_11 + 4B]; > if (_6 != 0) > goto <bb 6>; [66.00%] > else > goto <bb 4>; [34.00%] > > > Now the fun part. > > After we have finished optimizing bb9, we try to thread its outgoing > edges. Of particular interest is the edge 9->11. > > We do temporary propagation as part of the jump threading process. ie, > when we traverse 9->11 we know that k_11 will have the value k_30. So > we transform the assignment > > k_30 = k_11 + 4 > > into > > k_30 = k_30 + 4 > > Then we try to simplify that statement and infinitely recurse. > > > I considered trying to key behavior on EDGE_DFS_BACK (6->8). It'd be > something like don't record equivalences from a degenerate PHI where the > remaining edge(s) are EDGE_DFS_BACK. But I just couldn't convince > myself that was actually reasonable or sufficient in general. The key point is that you can never record "symbolic" equivalences on backedges. Because in SSA you rely on PHIs to fence SSA names from leaking cross iterations. That is, _1 in iteration 1 is obviously not equal to _1 in iteration 2. Other passes like VRP and value-numbering need to take care of this as well. You can of course record that _1 is 2 (constant) even across a backedge. So I think your consideration was exactly correct. Richard. > Jeff
On 11/21/2017 07:56 AM, Richard Biener wrote: >> >> >> I considered trying to key behavior on EDGE_DFS_BACK (6->8). It'd be >> something like don't record equivalences from a degenerate PHI where the >> remaining edge(s) are EDGE_DFS_BACK. But I just couldn't convince >> myself that was actually reasonable or sufficient in general. > > The key point is that you can never record "symbolic" equivalences on > backedges. Because in SSA you rely on PHIs to fence SSA names from > leaking cross iterations. That is, _1 in iteration 1 is obviously not equal > to _1 in iteration 2. > > Other passes like VRP and value-numbering need to take care of this > as well. > > You can of course record that _1 is 2 (constant) even across a backedge. > > So I think your consideration was exactly correct. So finally getting back to this. Thankfully I was able to find an old branch, revert the tree-ssa-dom.c bits and via some on-the-fly hackery trigger the issue again. This also enabled me to verify that triggering on EDGE_DFS_BACK would in fact resolve this issue. So attached are two patches. The first is the reversion. The second is the change to avoid recording the equivalence for a backedge in the CFG. Bootstrapped and regression tested on x86_64. Also verified by hand (using that old branch) that we wouldn't get into the infinite loop if we reverted and used EDGE_DFS_BACK to trigger ignoring the equivalence. Installing on the trunk. Jeff commit 46a2536a74d7f6981a02da05041885d097d9e23c Author: Jeff Law <law@torsion.usersys.redhat.com> Date: Mon Dec 18 19:18:47 2017 -0500 Revert 2017-11-19 Jeff Law <law@redhat.com> * tree-ssa-dom.c (record_equivalences_from_phis): Fix handling of degenerates resulting from ignoring an edge. diff --git a/gcc/ChangeLog b/gcc/ChangeLog index d165b5ccf41..b5854f7a67c 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,11 @@ +2017-12-18 Jeff Law <law@redhat.com> + + Revert + 2017-11-19 Jeff Law <law@redhat.com> + + * tree-ssa-dom.c (record_equivalences_from_phis): Fix handling + of degenerates resulting from ignoring an edge. + 2017-12-18 Martin Sebor <msebor@redhat.com> PR middle-end/83373 diff --git a/gcc/tree-ssa-dom.c b/gcc/tree-ssa-dom.c index 93c992a9215..05bc807071f 100644 --- a/gcc/tree-ssa-dom.c +++ b/gcc/tree-ssa-dom.c @@ -1109,7 +1109,6 @@ record_equivalences_from_phis (basic_block bb) tree rhs = NULL; size_t i; - bool ignored_phi_arg = false; for (i = 0; i < gimple_phi_num_args (phi); i++) { tree t = gimple_phi_arg_def (phi, i); @@ -1120,14 +1119,10 @@ record_equivalences_from_phis (basic_block bb) if (lhs == t) continue; - /* We want to track if we ignored any PHI arguments because - their associated edges were not executable. This impacts - whether or not we can use any equivalence we might discover. */ + /* If the associated edge is not marked as executable, then it + can be ignored. */ if ((gimple_phi_arg_edge (phi, i)->flags & EDGE_EXECUTABLE) == 0) - { - ignored_phi_arg = true; - continue; - } + continue; t = dom_valueize (t); @@ -1152,15 +1147,9 @@ record_equivalences_from_phis (basic_block bb) a useful equivalence. We do not need to record unwind data for this, since this is a true assignment and not an equivalence inferred from a comparison. All uses of this ssa name are dominated - by this assignment, so unwinding just costs time and space. - - Note that if we ignored a PHI argument and the resulting equivalence - is SSA_NAME = SSA_NAME. Then we can not use the equivalence as the - uses of the LHS SSA_NAME are not necessarily dominated by the - assignment of the RHS SSA_NAME. */ + by this assignment, so unwinding just costs time and space. */ if (i == gimple_phi_num_args (phi) - && may_propagate_copy (lhs, rhs) - && (!ignored_phi_arg || TREE_CODE (rhs) != SSA_NAME)) + && may_propagate_copy (lhs, rhs)) set_ssa_name_value (lhs, rhs); } } commit 61046656ff4e832bd1019e90c251b1c4c2c43883 Author: Jeff Law <law@torsion.usersys.redhat.com> Date: Mon Dec 18 23:28:37 2017 -0500 * tree-ssa-dom.c (record_equivalences_from_phis): Do not record symbolic equivalences from backedges in the CFG. diff --git a/gcc/ChangeLog b/gcc/ChangeLog index b5854f7a67c..96146e8934f 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,5 +1,8 @@ 2017-12-18 Jeff Law <law@redhat.com> + * tree-ssa-dom.c (record_equivalences_from_phis): Do not + record symbolic equivalences from backedges in the CFG. + Revert 2017-11-19 Jeff Law <law@redhat.com> diff --git a/gcc/tree-ssa-dom.c b/gcc/tree-ssa-dom.c index 05bc807071f..663d07b6fe9 100644 --- a/gcc/tree-ssa-dom.c +++ b/gcc/tree-ssa-dom.c @@ -1126,6 +1126,12 @@ record_equivalences_from_phis (basic_block bb) t = dom_valueize (t); + /* If T is an SSA_NAME and its associated edge is a backedge, + then quit as we can not utilize this equivalence. */ + if (TREE_CODE (t) == SSA_NAME + && (gimple_phi_arg_edge (phi, i)->flags & EDGE_DFS_BACK)) + break; + /* If we have not processed an alternative yet, then set RHS to this alternative. */ if (rhs == NULL)
diff --git a/gcc/ChangeLog b/gcc/ChangeLog index ae05dacf791..5ce981d0871 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,8 @@ +2017-11-19 Jeff Law <law@redhat.com> + + * tree-ssa-dom.c (record_equivalences_from_phis): Fix handling + of degenerates resulting from ignoring an edge. + 2017-11-19 Jan Hubicka <hubicka@ucw.cz> PR ipa/81360 diff --git a/gcc/tree-ssa-dom.c b/gcc/tree-ssa-dom.c index eb85b4a09ad..916d66134c3 100644 --- a/gcc/tree-ssa-dom.c +++ b/gcc/tree-ssa-dom.c @@ -1011,6 +1011,7 @@ record_equivalences_from_phis (basic_block bb) tree rhs = NULL; size_t i; + bool ignored_phi_arg = false; for (i = 0; i < gimple_phi_num_args (phi); i++) { tree t = gimple_phi_arg_def (phi, i); @@ -1021,10 +1022,14 @@ record_equivalences_from_phis (basic_block bb) if (lhs == t) continue; - /* If the associated edge is not marked as executable, then it - can be ignored. */ + /* We want to track if we ignored any PHI arguments because + their associated edges were not executable. This impacts + whether or not we can use any equivalence we might discover. */ if ((gimple_phi_arg_edge (phi, i)->flags & EDGE_EXECUTABLE) == 0) - continue; + { + ignored_phi_arg = true; + continue; + } t = dom_valueize (t); @@ -1049,9 +1054,15 @@ record_equivalences_from_phis (basic_block bb) a useful equivalence. We do not need to record unwind data for this, since this is a true assignment and not an equivalence inferred from a comparison. All uses of this ssa name are dominated - by this assignment, so unwinding just costs time and space. */ + by this assignment, so unwinding just costs time and space. + + Note that if we ignored a PHI argument and the resulting equivalence + is SSA_NAME = SSA_NAME. Then we can not use the equivalence as the + uses of the LHS SSA_NAME are not necessarily dominated by the + assignment of the RHS SSA_NAME. */ if (i == gimple_phi_num_args (phi) - && may_propagate_copy (lhs, rhs)) + && may_propagate_copy (lhs, rhs) + && (!ignored_phi_arg || TREE_CODE (rhs) != SSA_NAME)) set_ssa_name_value (lhs, rhs); } }
On my local branch gcc.dg/torture/pr56349.c fails by sending GCC into an infinite loop trying to simplify a self-referring statement. ie something like x_1 = x_1 + 10; That, of course, shouldn't be happening in SSA form. After some digging I've found the culprit. Let's say we've got a PHI. a_1 = PHI (a_0, a_2) If DOM decides that the edge associated with a_2 is not executable, then DOM will consider the PHI a degenerate and enter a_1 = a_0 into its equivalence table. That in turn will result in propagation of a_0 into uses of a_1. That, of course, isn't right. There's nothing that guarantees that the definition of a_0 dominates the uses of a_1. In the testcase that bogus propagation cascades and eventually results in a self-referring node like I showed above. The solution here is to note whether or not we ignored any PHI arguments. If we do and the equivalence we want to enter is SSA_NAME = SSA_NAME, then we must reject the equivalence. Obviously if we wanted to enter SSA_NAME = CONST, then we can still do so. Bootstrapped and regression tested on x86_64. Installing on the trunk. jeff commit 2b37e05b327e6b1170f72c51c21681b1dc5b8337 Author: Jeff Law <law@redhat.com> Date: Sun Nov 19 13:14:55 2017 -0700 * tree-ssa-dom.c (record_equivalences_from_phis): Fix handling of degenerates resulting from ignoring an edge.