| Message ID | 20150213235033.GA20179@f1.c.bardezibar.internal |
|---|---|
| State | New |
| Headers | show |
On 02/13/15 16:50, Sebastian Pop wrote: > Hi, > > the attached patch fixes PR65048 by checking before jump-threading that a path > to be threaded is still valid: as the testcase shows, there may be paths that > are not connected anymore because the cfg has changed in a previous jump-thread. > > PR tree-optimization/65048 > * tree-ssa-threadupdate.c (valid_jump_thread_path): New. > (thread_through_all_blocks): Call valid_jump_thread_path. > Remove invalid FSM jump-thread paths. > > * gcc.dg/tree-ssa/ssa-dom-thread-9.c: New. > > The patch passed bootstrap and regression tests on x86_64-linux. > Ok for trunk? These kinds of situations are normally pruned out in mark_threaded_blocks. The dumps for the FSM threads are a bit sparse -- they don't show the entire path. That makes it much harder to see what's going on. It also appears that FSM is registering lots of duplicate paths. grep Registering j*.dom1 | grep -v PHI | sort Registering FSM jump thread: (10, 12) incoming edge; (15, 3) nocopy; Registering FSM jump thread: (11, 12) incoming edge; (15, 16) nocopy; Registering FSM jump thread: (16, 3) incoming edge; (15, 16) nocopy; Registering FSM jump thread: (5, 10) incoming edge; (13, 14) nocopy; Registering FSM jump thread: (5, 10) incoming edge; (13, 14) nocopy; Registering FSM jump thread: (5, 11) incoming edge; (13, 14) nocopy; Registering FSM jump thread: (5, 11) incoming edge; (13, 14) nocopy; Registering FSM jump thread: (6, 14) incoming edge; (13, 14) nocopy; Registering FSM jump thread: (6, 14) incoming edge; (13, 14) nocopy; Registering FSM jump thread: (6, 3) incoming edge; (13, 14) nocopy; Registering FSM jump thread: (6, 3) incoming edge; (13, 14) nocopy; Registering FSM jump thread: (7, 10) incoming edge; (13, 14) nocopy; Registering FSM jump thread: (7, 10) incoming edge; (13, 14) nocopy; Registering FSM jump thread: (7, 11) incoming edge; (13, 14) nocopy; Registering FSM jump thread: (7, 11) incoming edge; (13, 14) nocopy; Registering FSM jump thread: (8, 14) incoming edge; (13, 14) nocopy; Registering FSM jump thread: (8, 14) incoming edge; (13, 14) nocopy; Registering FSM jump thread: (8, 3) incoming edge; (13, 14) nocopy; Registering FSM jump thread: (8, 3) incoming edge; (13, 14) nocopy; Something seems wrong there. Anyway, so what node precisely is not connected? Is that happening as a result of the duplicated jump threads or is it something else? Jeff
Jeff Law wrote: > These kinds of situations are normally pruned out in mark_threaded_blocks. I added the FSM code generation before calling mark_threaded_blocks. > > The dumps for the FSM threads are a bit sparse -- they don't show > the entire path. That makes it much harder to see what's going on. Would a patch improving the FSM dumps ok to commit separately to trunk? > It also appears that FSM is registering lots of duplicate paths. I discussed about this with my colleague Brian in CC, and we think it is feasible to avoid registering duplicate paths by computing a hashing the paths that have been already discovered, and checksum the paths before inserting in the paths vector. I don't think removing duplicate paths would help in the current case. > Anyway, so what node precisely is not connected? Is that happening > as a result of the duplicated jump threads or is it something else? Here is a more complete dump of what is going on: Registering FSM jump thread: (6, 7) (7, 10) (10, 11) (11, 12) Registering FSM jump thread: (5, 7) (7, 10) (10, 11) (11, 12) Registering FSM jump thread: (6, 7) (7, 10) (10, 11) (11, 12) Registering FSM jump thread: (5, 7) (7, 10) (10, 11) (11, 12) Registering FSM jump thread: (6, 7) (7, 10) (10, 11) (11, 12) Registering FSM jump thread: (5, 7) (7, 10) (10, 11) (11, 12) generating code for: Registering FSM jump thread: (6, 7) (7, 10) (10, 11) (11, 12) generating code for: Registering FSM jump thread: (5, 7) (7, 10) (10, 11) (11, 12) That was the first round of jump threading: we discovered all the paths to be threaded, and then we code generated only two jump-threads. Here is the second run of jump-thread, probably on a different function: Registering FSM jump thread: (6, 14) (14, 15) (15, 16) (16, 3) (3, 4) (4, 9) (9, 12) (12, 13) (13, 14) Registering FSM jump thread: (8, 14) (14, 15) (15, 16) (16, 3) (3, 4) (4, 9) (9, 12) (12, 13) (13, 14) Registering FSM jump thread: (6, 3) (3, 4) (4, 9) (9, 12) (12, 13) (13, 14) Registering FSM jump thread: (8, 3) (3, 4) (4, 9) (9, 12) (12, 13) (13, 14) Registering FSM jump thread: (5, 11) (11, 12) (12, 13) (13, 14) Registering FSM jump thread: (7, 11) (11, 12) (12, 13) (13, 14) Registering FSM jump thread: (5, 10) (10, 12) (12, 13) (13, 14) Registering FSM jump thread: (7, 10) (10, 12) (12, 13) (13, 14) Registering FSM jump thread: (6, 14) (14, 15) (15, 16) (16, 3) (3, 4) (4, 9) (9, 12) (12, 13) (13, 14) Registering FSM jump thread: (8, 14) (14, 15) (15, 16) (16, 3) (3, 4) (4, 9) (9, 12) (12, 13) (13, 14) Registering FSM jump thread: (6, 3) (3, 4) (4, 9) (9, 12) (12, 13) (13, 14) Registering FSM jump thread: (8, 3) (3, 4) (4, 9) (9, 12) (12, 13) (13, 14) Registering FSM jump thread: (5, 11) (11, 12) (12, 13) (13, 14) Registering FSM jump thread: (7, 11) (11, 12) (12, 13) (13, 14) Registering FSM jump thread: (5, 10) (10, 12) (12, 13) (13, 14) Registering FSM jump thread: (7, 10) (10, 12) (12, 13) (13, 14) Registering FSM jump thread: (16, 3) (3, 4) (4, 9) (9, 12) (12, 13) (13, 15) (15, 16) Registering FSM jump thread: (11, 12) (12, 13) (13, 15) (15, 16) Registering FSM jump thread: (10, 12) (12, 13) (13, 15) (15, 3) generating code for: Registering FSM jump thread: (6, 14) (14, 15) (15, 16) (16, 3) (3, 4) (4, 9) (9, 12) (12, 13) (13, 14) generating code for: Registering FSM jump thread: (10, 12) (12, 13) (13, 15) (15, 3) generating code for: Registering FSM jump thread: (11, 12) (12, 13) (13, 15) (15, 16) generating code for: Registering FSM jump thread: (16, 3) (3, 4) (4, 9) (9, 12) (12, 13) (13, 15) (15, 16) invalid jump-thread: Registering FSM jump thread: (7, 10) (10, 25) (12, 13) (13, 14) invalid jump-thread: Registering FSM jump thread: (5, 10) (10, 25) (12, 13) (13, 14) invalid jump-thread: Registering FSM jump thread: (7, 11) (11, 28) (12, 13) (13, 14) invalid jump-thread: Registering FSM jump thread: (5, 11) (11, 28) (12, 13) (13, 14) generating code for: Registering FSM jump thread: (8, 3) (3, 4) (4, 9) (9, 12) (12, 13) (13, 14) invalid jump-thread: Registering FSM jump thread: (7, 10) (10, 25) (12, 13) (13, 14) invalid jump-thread: Registering FSM jump thread: (5, 10) (10, 25) (12, 13) (13, 14) invalid jump-thread: Registering FSM jump thread: (7, 11) (11, 28) (12, 13) (13, 14) invalid jump-thread: Registering FSM jump thread: (5, 11) (11, 28) (12, 13) (13, 14) After having generated 4 jump threads, we end up trying to code generate a path that is not connected anymore: (7, 10) (10, 25) (12, 13) (13, 14) This is due to the fact that we have already code generated a jump-thread for this path: (10, 12) (12, 13) (13, 15) (15, 3) and we redirected the edge (10, 12) to (10, 25). The code generated for the path looks like this: (10, 25) (25, 26) (26, 27) (27, 3) There are two solutions to the problem of changing CFG that invalidates the existing jump-thread paths that we collected before starting code generation: - we either discard invalid jump-threads not connected anymore: this is what the patch I sent out does; - or we could patch the other registered jump-threads as we code generate: in this particular case, once we generate code for (10, 12) (12, 13) (13, 15) (15, 3) we would walk through the remaining jump-threads and patch all the paths that got disconnected, i.e., containing (10, 12), or after code generation, these paths would contain the sequence of edges (10, 25) (12, 13). We can do that because we still have the copy_bb table around at that time. Jeff, please let us know which solution you would like to submit to trunk. Thanks, Sebastian
On 02/18/15 15:27, Sebastian Pop wrote: > Jeff Law wrote: >> These kinds of situations are normally pruned out in mark_threaded_blocks. > > I added the FSM code generation before calling mark_threaded_blocks. OK. Hmm. Makes me wonder what happens if we have a normal jump thread path embedded inside an FSM path. > >> >> The dumps for the FSM threads are a bit sparse -- they don't show >> the entire path. That makes it much harder to see what's going on. > > Would a patch improving the FSM dumps ok to commit separately to trunk? Most definitely. I realize we're in stage4, but I'd approve such a change. > >> It also appears that FSM is registering lots of duplicate paths. > > I discussed about this with my colleague Brian in CC, and we think it is > feasible to avoid registering duplicate paths by computing a hashing the paths > that have been already discovered, and checksum the paths before inserting in > the paths vector. I don't think removing duplicate paths would help in the > current case. OK. It was the first thing that jumped out, if it's not the core issue here, then we can defer it. > Here is the second run of jump-thread, probably on a different function: > > Registering FSM jump thread: (6, 14) (14, 15) (15, 16) (16, 3) (3, 4) (4, 9) (9, 12) (12, 13) (13, 14) > Registering FSM jump thread: (8, 14) (14, 15) (15, 16) (16, 3) (3, 4) (4, 9) (9, 12) (12, 13) (13, 14) > Registering FSM jump thread: (6, 3) (3, 4) (4, 9) (9, 12) (12, 13) (13, 14) > Registering FSM jump thread: (8, 3) (3, 4) (4, 9) (9, 12) (12, 13) (13, 14) > Registering FSM jump thread: (5, 11) (11, 12) (12, 13) (13, 14) > Registering FSM jump thread: (7, 11) (11, 12) (12, 13) (13, 14) > Registering FSM jump thread: (5, 10) (10, 12) (12, 13) (13, 14) > Registering FSM jump thread: (7, 10) (10, 12) (12, 13) (13, 14) > Registering FSM jump thread: (6, 14) (14, 15) (15, 16) (16, 3) (3, 4) (4, 9) (9, 12) (12, 13) (13, 14) > Registering FSM jump thread: (8, 14) (14, 15) (15, 16) (16, 3) (3, 4) (4, 9) (9, 12) (12, 13) (13, 14) > Registering FSM jump thread: (6, 3) (3, 4) (4, 9) (9, 12) (12, 13) (13, 14) > Registering FSM jump thread: (8, 3) (3, 4) (4, 9) (9, 12) (12, 13) (13, 14) > Registering FSM jump thread: (5, 11) (11, 12) (12, 13) (13, 14) > Registering FSM jump thread: (7, 11) (11, 12) (12, 13) (13, 14) > Registering FSM jump thread: (5, 10) (10, 12) (12, 13) (13, 14) > Registering FSM jump thread: (7, 10) (10, 12) (12, 13) (13, 14) > Registering FSM jump thread: (16, 3) (3, 4) (4, 9) (9, 12) (12, 13) (13, 15) (15, 16) > Registering FSM jump thread: (11, 12) (12, 13) (13, 15) (15, 16) > Registering FSM jump thread: (10, 12) (12, 13) (13, 15) (15, 3) > generating code for: Registering FSM jump thread: (6, 14) (14, 15) (15, 16) (16, 3) (3, 4) (4, 9) (9, 12) (12, 13) (13, 14) > generating code for: Registering FSM jump thread: (10, 12) (12, 13) (13, 15) (15, 3) > generating code for: Registering FSM jump thread: (11, 12) (12, 13) (13, 15) (15, 16) > generating code for: Registering FSM jump thread: (16, 3) (3, 4) (4, 9) (9, 12) (12, 13) (13, 15) (15, 16) > invalid jump-thread: Registering FSM jump thread: (7, 10) (10, 25) (12, 13) (13, 14) > invalid jump-thread: Registering FSM jump thread: (5, 10) (10, 25) (12, 13) (13, 14) > invalid jump-thread: Registering FSM jump thread: (7, 11) (11, 28) (12, 13) (13, 14) > invalid jump-thread: Registering FSM jump thread: (5, 11) (11, 28) (12, 13) (13, 14) > generating code for: Registering FSM jump thread: (8, 3) (3, 4) (4, 9) (9, 12) (12, 13) (13, 14) > invalid jump-thread: Registering FSM jump thread: (7, 10) (10, 25) (12, 13) (13, 14) > invalid jump-thread: Registering FSM jump thread: (5, 10) (10, 25) (12, 13) (13, 14) > invalid jump-thread: Registering FSM jump thread: (7, 11) (11, 28) (12, 13) (13, 14) > invalid jump-thread: Registering FSM jump thread: (5, 11) (11, 28) (12, 13) (13, 14) > > After having generated 4 jump threads, we end up trying to code generate a path > that is not connected anymore: (7, 10) (10, 25) (12, 13) (13, 14) > This is due to the fact that we have already code generated a jump-thread for this path: > (10, 12) (12, 13) (13, 15) (15, 3) > and we redirected the edge (10, 12) to (10, 25). > The code generated for the path looks like this: > (10, 25) (25, 26) (26, 27) (27, 3) Very helpful. Thank you. [ snip ] > Registering FSM jump thread: (10, 12) (12, 13) (13, 15) (15, 3) [ snip ] > Registering FSM jump thread: (7, 10) (10, 12) (12, 13) (13, 14) What I'm having a bit of trouble wrapping my head around is how can those two paths both be valid when you register them? They have different transitions out of bb13, one going to bb15 the other to bb14, but they're both coming in via (10, 12). Maybe I'm missing something, but that's where I'd start. > > There are two solutions to the problem of changing CFG that invalidates the > existing jump-thread paths that we collected before starting code generation: > > - we either discard invalid jump-threads not connected anymore: this is what the > patch I sent out does; > > - or we could patch the other registered jump-threads as we code generate: > in this particular case, once we generate code for > (10, 12) (12, 13) (13, 15) (15, 3) > we would walk through the remaining jump-threads and patch all the paths > that got disconnected, i.e., containing (10, 12), or after code generation, > these paths would contain the sequence of edges (10, 25) (12, 13). > We can do that because we still have the copy_bb table around at that time. > > Jeff, please let us know which solution you would like to submit to trunk. I'm not sure yet because I'm struggling with convincing myself that those two registered paths are legitimate at the time they're registered. We may ultimately need something which recognizes that some paths are no longer valid after generating code for other paths, but let's make sure the paths that are registered are reasonable first. jeff
Jeff Law wrote: > > Registering FSM jump thread: (10, 12) (12, 13) (13, 15) (15, 3) > [ snip ] > > Registering FSM jump thread: (7, 10) (10, 12) (12, 13) (13, 14) > > What I'm having a bit of trouble wrapping my head around is how can > those two paths both be valid when you register them? They have > different transitions out of bb13, one going to bb15 the other to > bb14, but they're both coming in via (10, 12). Here is the output of debug_loops(3) showing the two paths before we start the FSM code generation: bb_7 (preds = {bb_4 }, succs = {bb_8 bb_10 bb_11 }) { <L26>: # .MEM_26 = VDEF <.MEM_1> a = 84; switch (x_8(D)) <default: <L24>, case 65: <L12>, case 85: <L4>> } bb_10 (preds = {bb_9 bb_5 bb_7 }, succs = {bb_12 }) { # .MEM_30 = PHI <.MEM_4(9), .MEM_20(5), .MEM_26(7)> # _34 = PHI <_7(9), 65(5), 84(7)> <L12>: goto <bb 12> (<L10>); } bb_12 (preds = {bb_9 bb_11 bb_10 }, succs = {bb_3 bb_13 }) { # _13 = PHI <_12(9), 65(11), 84(10)> # .MEM_32 = PHI <.MEM_4(9), .MEM_31(11), .MEM_30(10)> # _36 = PHI <_7(9), _35(11), _34(10)> <L10>: # .MEM_6 = VDEF <.MEM_32> b = _13; # VUSE <.MEM_6> c.0_10 = c; switch (c.0_10) <default: <L20>, case 85: <L14>> } bb_13 (preds = {bb_12 }, succs = {bb_14 bb_15 }) { <L14>: switch (_36) <default: <L15>, case 71: <L16>> } bb_14 (preds = {bb_13 bb_6 bb_8 }, succs = {bb_15 }) { # .MEM_33 = PHI <.MEM_6(13), .MEM_23(6), .MEM_28(8)> # _37 = PHI <_36(13), 65(6), 84(8)> # _39 = PHI <_13(13), _12(6), _12(8)> <L15>: # .MEM_18 = VDEF <.MEM_33> fn (); } bb_15 (preds = {bb_13 bb_14 }, succs = {bb_3 bb_16 }) { # .MEM_17 = PHI <.MEM_6(13), .MEM_18(14)> # _38 = PHI <_36(13), _37(14)> # _40 = PHI <_13(13), _39(14)> <L16>: switch (_40) <default: <L20>, case 65: <L17>> } bb_3 (preds = {bb_16 bb_15 bb_12 bb_6 bb_8 }, succs = {bb_4 }) { # .MEM_3 = PHI <.MEM_19(16), .MEM_17(15), .MEM_6(12), .MEM_23(6), .MEM_28(8)> # _9 = PHI <_38(16), _38(15), _36(12), 65(6), 84(8)> # _16 = PHI <65(16), _40(15), _13(12), _12(6), _12(8)> <L20>: } First, let's look at why we jump thread from 10 to 3: > > Registering FSM jump thread: (10, 12) (12, 13) (13, 15) (15, 3) In other words, let's see how we can infer that "from bb_15 we are guaranteed to jump into bb_3 if we come from bb_10." So this switch in bb_15 is guaranteed to jump to the default case: switch (_40) <default: <L20>, case 65: <L17>> # _40 = PHI <_13(13), _39(14)> because when coming from bb_13, "_40 = _13", and then in bb_12 we have the definition # _13 = PHI <_12(9), 65(11), 84(10)> and so if we come from bb_10, the value of _13 is 84. Because 84 != 65, switch (_40) will switch to default, that is a jump from bb_15 to bb_3. Now let's see how we jump thread from 7 to 14: > > Registering FSM jump thread: (7, 10) (10, 12) (12, 13) (13, 14) Why do we know that from bb_13 we necessarily jump to bb_14 if we have just executed the code in bb_7? In other words, why do we jump to the default case of switch (_36) <default: <L15>, case 71: <L16>> # _36 = PHI <_7(9), _35(11), _34(10)> # _34 = PHI <_7(9), 65(5), 84(7)> so coming from bb_7, the value of the switch is 84 that is different than case 71, so we jump to the default case in "switch (_36) <default: <L15>, case 71: <L16>>". > let's make sure the paths that are registered are reasonable first I think it is reasonable to jump thread these two paths. Sebastian
On 02/25/15 11:37, Sebastian Pop wrote: > Jeff Law wrote: >>> Registering FSM jump thread: (10, 12) (12, 13) (13, 15) (15, 3) >> [ snip ] >>> Registering FSM jump thread: (7, 10) (10, 12) (12, 13) (13, 14) >> >> What I'm having a bit of trouble wrapping my head around is how can >> those two paths both be valid when you register them? They have >> different transitions out of bb13, one going to bb15 the other to >> bb14, but they're both coming in via (10, 12). > > Here is the output of debug_loops(3) showing the two paths before we start the > FSM code generation: > > bb_7 (preds = {bb_4 }, succs = {bb_8 bb_10 bb_11 }) > { > <L26>: > # .MEM_26 = VDEF <.MEM_1> > a = 84; > switch (x_8(D)) <default: <L24>, case 65: <L12>, case 85: <L4>> > } > bb_10 (preds = {bb_9 bb_5 bb_7 }, succs = {bb_12 }) > { > # .MEM_30 = PHI <.MEM_4(9), .MEM_20(5), .MEM_26(7)> > # _34 = PHI <_7(9), 65(5), 84(7)> > <L12>: > goto <bb 12> (<L10>); > } > bb_12 (preds = {bb_9 bb_11 bb_10 }, succs = {bb_3 bb_13 }) > { > # _13 = PHI <_12(9), 65(11), 84(10)> > # .MEM_32 = PHI <.MEM_4(9), .MEM_31(11), .MEM_30(10)> > # _36 = PHI <_7(9), _35(11), _34(10)> > <L10>: > # .MEM_6 = VDEF <.MEM_32> > b = _13; > # VUSE <.MEM_6> > c.0_10 = c; > switch (c.0_10) <default: <L20>, case 85: <L14>> > } > bb_13 (preds = {bb_12 }, succs = {bb_14 bb_15 }) > { > <L14>: > switch (_36) <default: <L15>, case 71: <L16>> > } > bb_14 (preds = {bb_13 bb_6 bb_8 }, succs = {bb_15 }) > { > # .MEM_33 = PHI <.MEM_6(13), .MEM_23(6), .MEM_28(8)> > # _37 = PHI <_36(13), 65(6), 84(8)> > # _39 = PHI <_13(13), _12(6), _12(8)> > <L15>: > # .MEM_18 = VDEF <.MEM_33> > fn (); > } > bb_15 (preds = {bb_13 bb_14 }, succs = {bb_3 bb_16 }) > { > # .MEM_17 = PHI <.MEM_6(13), .MEM_18(14)> > # _38 = PHI <_36(13), _37(14)> > # _40 = PHI <_13(13), _39(14)> > <L16>: > switch (_40) <default: <L20>, case 65: <L17>> > } > bb_3 (preds = {bb_16 bb_15 bb_12 bb_6 bb_8 }, succs = {bb_4 }) > { > # .MEM_3 = PHI <.MEM_19(16), .MEM_17(15), .MEM_6(12), .MEM_23(6), .MEM_28(8)> > # _9 = PHI <_38(16), _38(15), _36(12), 65(6), 84(8)> > # _16 = PHI <65(16), _40(15), _13(12), _12(6), _12(8)> > <L20>: > } > > First, let's look at why we jump thread from 10 to 3: >>> Registering FSM jump thread: (10, 12) (12, 13) (13, 15) (15, 3) > > In other words, let's see how we can infer that "from bb_15 we are guaranteed to > jump into bb_3 if we come from bb_10." > > So this switch in bb_15 is guaranteed to jump to the default case: > switch (_40) <default: <L20>, case 65: <L17>> > > # _40 = PHI <_13(13), _39(14)> > > because when coming from bb_13, "_40 = _13", and then in bb_12 we have the definition > # _13 = PHI <_12(9), 65(11), 84(10)> > > and so if we come from bb_10, the value of _13 is 84. > Because 84 != 65, switch (_40) will switch to default, that is a jump from bb_15 to bb_3. > > > Now let's see how we jump thread from 7 to 14: >>> Registering FSM jump thread: (7, 10) (10, 12) (12, 13) (13, 14) > > Why do we know that from bb_13 we necessarily jump to bb_14 if we have just > executed the code in bb_7? > > In other words, why do we jump to the default case of > switch (_36) <default: <L15>, case 71: <L16>> > > # _36 = PHI <_7(9), _35(11), _34(10)> > # _34 = PHI <_7(9), 65(5), 84(7)> > > so coming from bb_7, the value of the switch is 84 that is different than case 71, > so we jump to the default case in "switch (_36) <default: <L15>, case 71: <L16>>". > >> let's make sure the paths that are registered are reasonable first > > I think it is reasonable to jump thread these two paths. So this is why the debugging output is so important ;-) We might consider further enhancing the debug output to mark the state of each of those intermediate blocks, of particular importance is whether or not the block has a known static destination on the path. In this test, the branch out of 13 is not known statically in the first path,but is known in the second path. Thus 13' in the first path will continue to have a conditional branch (to 14 or 15' where 15' always goes to 3). 13'' in the second path will unconditionally transfer to 14. So, now time for me to go read that patch thoroughly. Thanks, jeff
On 02/13/15 16:50, Sebastian Pop wrote: > Hi, > > the attached patch fixes PR65048 by checking before jump-threading that a path > to be threaded is still valid: as the testcase shows, there may be paths that > are not connected anymore because the cfg has changed in a previous jump-thread. > > PR tree-optimization/65048 > * tree-ssa-threadupdate.c (valid_jump_thread_path): New. > (thread_through_all_blocks): Call valid_jump_thread_path. > Remove invalid FSM jump-thread paths. > > * gcc.dg/tree-ssa/ssa-dom-thread-9.c: New. > > The patch passed bootstrap and regression tests on x86_64-linux. > Ok for trunk? OK. jeff
On 02/13/15 16:50, Sebastian Pop wrote: > Hi, > > the attached patch fixes PR65048 by checking before jump-threading that a path > to be threaded is still valid: as the testcase shows, there may be paths that > are not connected anymore because the cfg has changed in a previous jump-thread. > > PR tree-optimization/65048 > * tree-ssa-threadupdate.c (valid_jump_thread_path): New. > (thread_through_all_blocks): Call valid_jump_thread_path. > Remove invalid FSM jump-thread paths. > > * gcc.dg/tree-ssa/ssa-dom-thread-9.c: New. > > The patch passed bootstrap and regression tests on x86_64-linux. > Ok for trunk? I added a regression marker to the new test & its ChangeLog and committed this for you. Will twiddle BZ appropriately in a minute. Thanks, Jeff
On Thu, Feb 26, 2015 at 7:56 AM, Jeff Law <law@redhat.com> wrote: > On 02/13/15 16:50, Sebastian Pop wrote: >> >> Hi, >> >> the attached patch fixes PR65048 by checking before jump-threading that a >> path >> to be threaded is still valid: as the testcase shows, there may be paths >> that >> are not connected anymore because the cfg has changed in a previous >> jump-thread. >> >> PR tree-optimization/65048 >> * tree-ssa-threadupdate.c (valid_jump_thread_path): New. >> (thread_through_all_blocks): Call valid_jump_thread_path. >> Remove invalid FSM jump-thread paths. >> >> * gcc.dg/tree-ssa/ssa-dom-thread-9.c: New. >> >> The patch passed bootstrap and regression tests on x86_64-linux. >> Ok for trunk? > > I added a regression marker to the new test & its ChangeLog and committed > this for you. Will twiddle BZ appropriately in a minute. Thanks Jeff. I updated my tree with the patch, and I was waiting for regstrap to finish before pushing the change. For the record, the patch passed regstrap on x86_64-linux. Sebastian
Sebastian Pop <sebpop@gmail.com> writes: > +void > +baz (void) > +{ > + while (1) > + { > + a = foo (); > + b = foo (); FAIL: gcc.dg/tree-ssa/ssa-dom-thread-9.c (test for excess errors) Excess errors: /daten/aranym/gcc/gcc-20150227/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-9.c:45:11: error: too few arguments to function 'foo' /daten/aranym/gcc/gcc-20150227/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-9.c:46:11: error: too few arguments to function 'foo' Andreas.
From 79b93a743649b898010cfea70769184bca28efb1 Mon Sep 17 00:00:00 2001 From: Sebastian Pop <sebpop@gmail.com> Date: Tue, 10 Feb 2015 22:36:50 +0100 Subject: [PATCH] check that paths are still valid to be threaded PR tree-optimization/65048 * tree-ssa-threadupdate.c (valid_jump_thread_path): New. (thread_through_all_blocks): Call valid_jump_thread_path. Remove invalid FSM jump-thread paths. * gcc.dg/tree-ssa/ssa-dom-thread-9.c: New. --- gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-9.c | 49 ++++++++++++++++++++++ gcc/tree-ssa-threadupdate.c | 40 +++++++++++++++--- 2 files changed, 83 insertions(+), 6 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-9.c diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-9.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-9.c new file mode 100644 index 0000000..a843753 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-9.c @@ -0,0 +1,49 @@ +/* { dg-do compile } */ +/* { dg-options "-O3" } */ + +int a, b, c, d; +void fn (void); + +int +foo (x) +{ + switch (x) + { + case 'A': + return 'T'; + case 'U': + return 'A'; + } +} + +void +bar (int x, int y) +{ + switch (c) + { + case 'U': + switch (x) + { + default: + fn (); + case 'G': + switch (y) + { + case 'A': + d = 7; + } + } + } +} + +void +baz (void) +{ + while (1) + { + a = foo (); + b = foo (); + bar (a, b); + } +} + diff --git a/gcc/tree-ssa-threadupdate.c b/gcc/tree-ssa-threadupdate.c index 3326144..7a41ab2 100644 --- a/gcc/tree-ssa-threadupdate.c +++ b/gcc/tree-ssa-threadupdate.c @@ -2473,6 +2473,21 @@ duplicate_seme_region (edge entry, edge exit, return true; } +/* Return true when PATH is a valid jump-thread path. */ + +static bool +valid_jump_thread_path (vec<jump_thread_edge *> *path) +{ + unsigned len = path->length (); + + /* Check that the path is connected. */ + for (unsigned int j = 0; j < len - 1; j++) + if ((*path)[j]->e->dest != (*path)[j+1]->e->src) + return false; + + return true; +} + /* Walk through all blocks and thread incoming edges to the appropriate outgoing edge for each edge pair recorded in THREADED_EDGES. @@ -2505,12 +2520,25 @@ thread_through_all_blocks (bool may_peel_loop_headers) vec<jump_thread_edge *> *path = paths[i]; edge entry = (*path)[0]->e; - if ((*path)[0]->type != EDGE_FSM_THREAD - /* Do not jump-thread twice from the same block. */ - || bitmap_bit_p (threaded_blocks, entry->src->index)) { - i++; - continue; - } + /* Only code-generate FSM jump-threads in this loop. */ + if ((*path)[0]->type != EDGE_FSM_THREAD) + { + i++; + continue; + } + + /* Do not jump-thread twice from the same block. */ + if (bitmap_bit_p (threaded_blocks, entry->src->index) + /* Verify that the jump thread path is still valid: a + previous jump-thread may have changed the CFG, and + invalidated the current path. */ + || !valid_jump_thread_path (path)) + { + /* Remove invalid FSM jump-thread paths. */ + delete_jump_thread_path (path); + paths.unordered_remove (i); + continue; + } unsigned len = path->length (); edge exit = (*path)[len - 1]->e; -- 1.7.2.5
Hi, the attached patch fixes PR65048 by checking before jump-threading that a path to be threaded is still valid: as the testcase shows, there may be paths that are not connected anymore because the cfg has changed in a previous jump-thread. PR tree-optimization/65048 * tree-ssa-threadupdate.c (valid_jump_thread_path): New. (thread_through_all_blocks): Call valid_jump_thread_path. Remove invalid FSM jump-thread paths. * gcc.dg/tree-ssa/ssa-dom-thread-9.c: New. The patch passed bootstrap and regression tests on x86_64-linux. Ok for trunk? Thanks, Sebastian