diff mbox series

Allow fully resolving backward jump threading passes.

Message ID 20211015142535.324483-1-aldyh@redhat.com
State New
Headers show
Series Allow fully resolving backward jump threading passes. | expand

Commit Message

Aldy Hernandez Oct. 15, 2021, 2:25 p.m. UTC 
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.

OK pending tests?

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):
	(pass_early_thread_jumps::gate): Inline.
	(pass_early_thread_jumps::execute): Inline.
	(class pass_thread_jumps_full): New.
---
 gcc/tree-pass.h               |   1 +
 gcc/tree-ssa-threadbackward.c | 178 ++++++++++++++++++++--------------
 2 files changed, 108 insertions(+), 71 deletions(-)

Comments

Jeff Law Oct. 15, 2021, 2:40 p.m. UTC | #1 
On 10/15/2021 8:25 AM, Aldy Hernandez wrote:
> 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.
>
> OK pending tests?
>
> 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):
> 	(pass_early_thread_jumps::gate): Inline.
> 	(pass_early_thread_jumps::execute): Inline.
> 	(class pass_thread_jumps_full): New.
OK.
jeff
diff mbox series

Patch

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 *