Refactor jump_thread_path_registry.

In an attempt to refactor thread_through_all_blocks(), I've realized
that there is a mess of code dealing with coexisting forward and
backward thread types.  However, this is an impossible scenario, as
the registry contains either forward/old-style threads, or backward
threads (EDGE_FSM_THREADs), never both.

The fact that both types of threads cannot coexist, simplifies the
code considerably.  For that matter, it splits things up nicely
because there are some common bits that can go into a base class, and
some differing code that can go into derived classes.

Diving things in this way makes it very obvious which parts belong in
the old-style copier and which parts belong to the generic copier.
Doing all this provided some nice cleanups, as well as fixing a latent
bug in adjust_paths_after_duplication.

The diff is somewhat hard to read, so perhaps looking at the final
output would be easier.

A general overview of what this patch achieves can be seen by just
looking at this simplified class layout:

// Abstract class for the jump thread registry.

class jt_path_registry
{
public:
  jt_path_registry ();
  virtual ~jt_path_registry ();
  bool register_jump_thread (vec<jump_thread_edge *> *);
  bool thread_through_all_blocks (bool peel_loop_headers);
  jump_thread_edge *allocate_thread_edge (edge e, jump_thread_edge_type t);
  vec<jump_thread_edge *> *allocate_thread_path ();
protected:
  vec<vec<jump_thread_edge *> *> m_paths;
  unsigned long m_num_threaded_edges;
private:
  virtual bool update_cfg (bool peel_loop_headers) = 0;
};

// Forward threader path registry using a custom BB copier.

class fwd_jt_path_registry : public jt_path_registry
{
public:
  fwd_jt_path_registry ();
  ~fwd_jt_path_registry ();
  void remove_jump_threads_including (edge);
private:
  bool update_cfg (bool peel_loop_headers) override;
  void mark_threaded_blocks (bitmap threaded_blocks);
  bool thread_block_1 (basic_block, bool noloop_only, bool joiners);
  bool thread_block (basic_block, bool noloop_only);
  bool thread_through_loop_header (class loop *loop,
                                   bool may_peel_loop_headers);
  class redirection_data *lookup_redirection_data (edge e, enum insert_option);
  hash_table<struct removed_edges> *m_removed_edges;
  hash_table<redirection_data> *m_redirection_data;
};

// Backward threader path registry using a generic BB copier.

class back_jt_path_registry : public jt_path_registry
{
private:
  bool update_cfg (bool peel_loop_headers) override;
  void adjust_paths_after_duplication (unsigned curr_path_num);
  bool duplicate_thread_path (edge entry, edge exit, basic_block *region,
                              unsigned n_region, unsigned current_path_no);
  bool rewire_first_differing_edge (unsigned path_num, unsigned edge_num);
};

That is, the forward and backward bits have been completely split,
while deriving from a base class for the common functionality.

Most everything is mechanical, but there are a few gotchas:

a) back_jt_path_registry::update_cfg(), which contains the backward
threading specific bits, is rather simple, since most of the code in
the original thread_through_all_blocks() only applied to the forward
threader: removed edges, mark_threaded_blocks,
thread_through_loop_header, the copy tables (*).

(*) The back threader has its own copy tables in
duplicate_thread_path.

b) In some cases, adjust_paths_after_duplication() was commoning out
so many blocks that it was removing the initial EDGE_FSM_THREAD
marker.  I've fixed this.

c) AFAICT, when run from the forward threader,
thread_through_all_blocks() attempts to remove threads starting with
an edge already seen, but it would never see anything because the loop
doing the checking only has a visited_starting_edges.contains(), and
no corresponding visited_starting_edges.add().  The add() method in
thread_through_all_blocks belongs to the backward threading bits, and
as I've explained, both types cannot coexist.  I've removed the checks
in the forward bits since they don't appear to do anything.  If this
was an oversight, and we want to avoid threading already seen edges in
the forward threader, I can move this functionality to the base class.

Ultimately I would like to move all the registry code to
tree-ssa-threadregistry.*.  I've avoided this in this patch to aid in
review.

My apologies for this longass explanation, but I want to make sure
we're covering all of our bases.

Tested on x86-64 Linux by a very tedious process of moving chunks
around, running "make check-gcc RUNTESTFLAGS=tree-ssa.exp", and
repeating ad-nauseum.  And of course, by running a full bootstrap and
tests.

OK?

p.s. In a follow-up patch I will rename the confusing EDGE_FSM_THREAD
type.

gcc/ChangeLog:

	* tree-ssa-threadbackward.c (class back_threader_registry): Use
	back_jt_path_registry.
	* tree-ssa-threadedge.c (jump_threader::jump_threader): Use
	fwd_jt_path_registry.
	* tree-ssa-threadedge.h (class jump_threader): Same..
	* tree-ssa-threadupdate.c
	(jump_thread_path_registry::jump_thread_path_registry): Rename...
	(jt_path_registry::jt_path_registry): ...to this.
	(jump_thread_path_registry::~jump_thread_path_registry): Rename...
	(jt_path_registry::~jt_path_registry): ...this.
	(fwd_jt_path_registry::fwd_jt_path_registry): New.
	(fwd_jt_path_registry::~fwd_jt_path_registry): New.
	(jump_thread_path_registry::allocate_thread_edge): Rename...
	(jt_path_registry::allocate_thread_edge): ...to this.
	(jump_thread_path_registry::allocate_thread_path): Rename...
	(jt_path_registry::allocate_thread_path): ...to this.
	(jump_thread_path_registry::lookup_redirection_data): Rename...
	(fwd_jt_path_registry::lookup_redirection_data): ...to this.
	(jump_thread_path_registry::thread_block_1): Rename...
	(fwd_jt_path_registry::thread_block_1): ...to this.
	(jump_thread_path_registry::thread_block): Rename...
	(fwd_jt_path_registry::thread_block): ...to this.
	(jt_path_registry::thread_through_loop_header): Rename...
	(fwd_jt_path_registry::thread_through_loop_header): ...to this.
	(jump_thread_path_registry::mark_threaded_blocks): Rename...
	(fwd_jt_path_registry::mark_threaded_blocks): ...to this.
	(jump_thread_path_registry::debug_path): Rename...
	(jt_path_registry::debug_path): ...to this.
	(jump_thread_path_registry::dump): Rename...
	(jt_path_registry::debug): ...to this.
	(jump_thread_path_registry::rewire_first_differing_edge): Rename...
	(back_jt_path_registry::rewire_first_differing_edge): ...to this.
	(jump_thread_path_registry::adjust_paths_after_duplication): Rename...
	(back_jt_path_registry::adjust_paths_after_duplication): ...to this.
	(jump_thread_path_registry::duplicate_thread_path): Rename...
	(back_jt_path_registry::duplicate_thread_path): ...to this.  Also,
	drop ill-formed candidates.
	(jump_thread_path_registry::remove_jump_threads_including): Rename...
	(fwd_jt_path_registry::remove_jump_threads_including): ...to this.
	(jt_path_registry::thread_through_all_blocks): New.
	(back_jt_path_registry::update_cfg): New.
	(fwd_jt_path_registry::update_cfg): New.
	(jump_thread_path_registry::register_jump_thread): Rename...
	(jt_path_registry::register_jump_thread): ...to this.
	* tree-ssa-threadupdate.h (class jump_thread_path_registry):
	Abstract to...
	(class jt_path_registry): ...here.
	(class fwd_jt_path_registry): New.
	(class back_jt_path_registry): New.

1 files changed, 1 insertions, 1 deletions

diff --git a/gcc/tree-ssa-threadbackward.c b/gcc/tree-ssa-threadbackward.c
index e729923..7ff5cec 100644
--- a/gcc/tree-ssa-threadbackward.c
+++ b/gcc/tree-ssa-threadbackward.c
@@ -56,7 +56,7 @@ public:
   bool register_path (const vec<basic_block> &, edge taken);
   bool thread_through_all_blocks (bool may_peel_loop_headers);
 private:
-  jump_thread_path_registry m_lowlevel_registry;
+  back_jt_path_registry m_lowlevel_registry;
   const int m_max_allowable_paths;
   int m_threaded_paths;
 };