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
