[gcc r12-4461] Allow fully resolving backward jump threading passes.

[gcc r12-4461] Allow fully resolving backward jump threading passes.

[Aldy Hernandez]

https://gcc.gnu.org/g:5d4d64faa71a6389bfb76bfb3334b63360cf62c0

commit r12-4461-g5d4d64faa71a6389bfb76bfb3334b63360cf62c0
Author: Aldy Hernandez <aldyh@redhat.com>
Date:   Fri Oct 15 14:46:32 2021 +0200

    Allow fully resolving backward jump threading passes.
    
    This refactors the backward threader pass so that it can be called in
    either fully resolving mode, or in classic mode where any unknowns
    default to VARYING.  Doing so opens the door for
    "pass_thread_jumps_full" which has the resolving bits set.
    
    This pass has not been added to the pipeline, but with it in place, we
    can now experiment with it to see how to reduce the number of
    jump threaders.  The first suspect will probably be enabling fully
    resolving in the backward threader pass immediately preceeding VRP2,
    and removing the VRP2 threader pass.  Now that VRP and the backward
    threader are sharing a solver, and most of the threads get handcuffed
    by cancel_threads(), we should have a variety of scenarios to try.
    
    In the process, I have cleaned up things to make it trivial to see
    what the difference between the 3 variants are (early jump
    threading, quick jump threading without resolving SSAs, and fully
    resolving jump threading).  Since I moved stuff around, it's probably
    easier to just look at the last section in tree-ssa-threadbackward to
    see how it's all laid out.
    
    No functional changes as the new pass hasn't been added to the
    pipeline.
    
    gcc/ChangeLog:
    
            * tree-pass.h (make_pass_thread_jumps_full): New.
            * tree-ssa-threadbackward.c (pass_thread_jumps::gate): Inline.
            (try_thread_blocks): Add resolve and speed arguments.
            (pass_thread_jumps::execute): Inline.
            (do_early_thread_jumps): New.
            (do_thread_jumps): New.
            (make_pass_thread_jumps): Move.
            (pass_early_thread_jumps::gate): Inline.
            (pass_early_thread_jumps::execute): Inline.
            (class pass_thread_jumps_full): New.

Diff:
---
 gcc/tree-pass.h               |   1 +
 gcc/tree-ssa-threadbackward.c | 178 +++++++++++++++++++++++++-----------------
 2 files changed, 108 insertions(+), 71 deletions(-)

diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h
index 84477a47b88..d379769a943 100644
--- a/gcc/tree-pass.h
+++ b/gcc/tree-pass.h
@@ -407,6 +407,7 @@ extern gimple_opt_pass *make_pass_cd_dce (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_call_cdce (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_merge_phi (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_thread_jumps (gcc::context *ctxt);
+extern gimple_opt_pass *make_pass_thread_jumps_full (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_early_thread_jumps (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_split_crit_edges (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_laddress (gcc::context *ctxt);
diff --git a/gcc/tree-ssa-threadbackward.c b/gcc/tree-ssa-threadbackward.c
index 8cc92a484fe..62f936a9651 100644
--- a/gcc/tree-ssa-threadbackward.c
+++ b/gcc/tree-ssa-threadbackward.c
@@ -114,7 +114,7 @@ private:
   static const edge UNREACHABLE_EDGE;
   // Set to TRUE if unknown SSA names along a path should be resolved
   // with the ranger.  Otherwise, unknown SSA names are assumed to be
-  // VARYING.  Setting to true more precise but slower.
+  // VARYING.  Setting to true is more precise but slower.
   bool m_resolve;
 };
 
@@ -925,47 +925,15 @@ back_threader_registry::register_path (const vec<basic_block> &m_path,
   return true;
 }
 
-namespace {
-
-const pass_data pass_data_thread_jumps =
-{
-  GIMPLE_PASS,
-  "thread",
-  OPTGROUP_NONE,
-  TV_TREE_SSA_THREAD_JUMPS,
-  ( PROP_cfg | PROP_ssa ),
-  0,
-  0,
-  0,
-  TODO_update_ssa,
-};
-
-class pass_thread_jumps : public gimple_opt_pass
-{
-public:
-  pass_thread_jumps (gcc::context *ctxt)
-    : gimple_opt_pass (pass_data_thread_jumps, ctxt)
-  {}
-
-  opt_pass * clone (void) { return new pass_thread_jumps (m_ctxt); }
-  virtual bool gate (function *);
-  virtual unsigned int execute (function *);
-};
-
-bool
-pass_thread_jumps::gate (function *fun ATTRIBUTE_UNUSED)
-{
-  return flag_thread_jumps && flag_expensive_optimizations;
-}
-
-// Try to thread blocks in FUN.  Return TRUE if any jump thread paths were
-// registered.
+// Try to thread blocks in FUN.  RESOLVE is TRUE when fully resolving
+// unknown SSAs.  SPEED is TRUE when optimizing for speed.
+//
+// Return TRUE if any jump thread paths were registered.
 
 static bool
-try_thread_blocks (function *fun)
+try_thread_blocks (function *fun, bool resolve, bool speed)
 {
-  /* Try to thread each block with more than one successor.  */
-  back_threader threader (/*speed=*/true, /*resolve=*/false);
+  back_threader threader (speed, resolve);
   basic_block bb;
   FOR_EACH_BB_FN (bb, fun)
     {
@@ -975,24 +943,27 @@ try_thread_blocks (function *fun)
   return threader.thread_through_all_blocks (/*peel_loop_headers=*/true);
 }
 
-unsigned int
-pass_thread_jumps::execute (function *fun)
+static unsigned int
+do_early_thread_jumps (function *fun, bool resolve)
 {
-  loop_optimizer_init (LOOPS_HAVE_PREHEADERS | LOOPS_HAVE_SIMPLE_LATCHES);
+  loop_optimizer_init (AVOID_CFG_MODIFICATIONS);
 
-  bool changed = try_thread_blocks (fun);
+  try_thread_blocks (fun, resolve, /*speed=*/false);
 
   loop_optimizer_finalize ();
-
-  return changed ? TODO_cleanup_cfg : 0;
-}
-
+  return 0;
 }
 
-gimple_opt_pass *
-make_pass_thread_jumps (gcc::context *ctxt)
+static unsigned int
+do_thread_jumps (function *fun, bool resolve)
 {
-  return new pass_thread_jumps (ctxt);
+  loop_optimizer_init (LOOPS_HAVE_PREHEADERS | LOOPS_HAVE_SIMPLE_LATCHES);
+
+  bool changed = try_thread_blocks (fun, resolve, /*speed=*/true);
+
+  loop_optimizer_finalize ();
+
+  return changed ? TODO_cleanup_cfg : 0;
 }
 
 namespace {
@@ -1010,6 +981,33 @@ const pass_data pass_data_early_thread_jumps =
   ( TODO_cleanup_cfg | TODO_update_ssa ),
 };
 
+const pass_data pass_data_thread_jumps =
+{
+  GIMPLE_PASS,
+  "thread",
+  OPTGROUP_NONE,
+  TV_TREE_SSA_THREAD_JUMPS,
+  ( PROP_cfg | PROP_ssa ),
+  0,
+  0,
+  0,
+  TODO_update_ssa,
+};
+
+const pass_data pass_data_thread_jumps_full =
+{
+  GIMPLE_PASS,
+  "thread-full",
+  OPTGROUP_NONE,
+  TV_TREE_SSA_THREAD_JUMPS,
+  ( PROP_cfg | PROP_ssa ),
+  0,
+  0,
+  0,
+  TODO_update_ssa,
+};
+
+// Early jump threading pass optimizing for size.
 class pass_early_thread_jumps : public gimple_opt_pass
 {
 public:
@@ -1017,36 +1015,74 @@ public:
     : gimple_opt_pass (pass_data_early_thread_jumps, ctxt)
   {}
 
-  opt_pass * clone (void) { return new pass_early_thread_jumps (m_ctxt); }
-  virtual bool gate (function *);
-  virtual unsigned int execute (function *);
+  opt_pass * clone () override
+  {
+    return new pass_early_thread_jumps (m_ctxt);
+  }
+  bool gate (function *) override
+  {
+    return flag_thread_jumps;
+  }
+  unsigned int execute (function *fun) override
+  {
+    return do_early_thread_jumps (fun, /*resolve=*/false);
+  }
 };
 
-bool
-pass_early_thread_jumps::gate (function *fun ATTRIBUTE_UNUSED)
+// Jump threading pass without resolving of unknown SSAs.
+class pass_thread_jumps : public gimple_opt_pass
 {
-  return flag_thread_jumps;
-}
+public:
+  pass_thread_jumps (gcc::context *ctxt)
+    : gimple_opt_pass (pass_data_thread_jumps, ctxt)
+  {}
+  opt_pass * clone (void) override
+  {
+    return new pass_thread_jumps (m_ctxt);
+  }
+  bool gate (function *) override
+  {
+    return flag_thread_jumps && flag_expensive_optimizations;
+  }
+  unsigned int execute (function *fun) override
+  {
+    return do_thread_jumps (fun, /*resolve=*/false);
+  }
+};
 
-unsigned int
-pass_early_thread_jumps::execute (function *fun)
+// Jump threading pass that fully resolves unknown SSAs.
+class pass_thread_jumps_full : public gimple_opt_pass
 {
-  loop_optimizer_init (AVOID_CFG_MODIFICATIONS);
+public:
+  pass_thread_jumps_full (gcc::context *ctxt)
+    : gimple_opt_pass (pass_data_thread_jumps_full, ctxt)
+  {}
+  opt_pass * clone (void) override
+  {
+    return new pass_thread_jumps (m_ctxt);
+  }
+  bool gate (function *) override
+  {
+    return flag_thread_jumps && flag_expensive_optimizations;
+  }
+  unsigned int execute (function *fun) override
+  {
+    return do_thread_jumps (fun, /*resolve=*/true);
+  }
+};
 
-  /* Try to thread each block with more than one successor.  */
-  back_threader threader (/*speed_p=*/false, /*resolve=*/false);
-  basic_block bb;
-  FOR_EACH_BB_FN (bb, fun)
-    {
-      if (EDGE_COUNT (bb->succs) > 1)
-	threader.maybe_thread_block (bb);
-    }
-  threader.thread_through_all_blocks (/*peel_loop_headers=*/true);
+} // namespace {
 
-  loop_optimizer_finalize ();
-  return 0;
+gimple_opt_pass *
+make_pass_thread_jumps (gcc::context *ctxt)
+{
+  return new pass_thread_jumps (ctxt);
 }
 
+gimple_opt_pass *
+make_pass_thread_jumps_full (gcc::context *ctxt)
+{
+  return new pass_thread_jumps_full (ctxt);
 }
 
 gimple_opt_pass *