This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

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


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


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]