Re: [patch] fix PR65048: check that jump-thread paths are still valid

[Jeff Law]

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