diff mbox series

Add ability to use full resolving path solver in the backward threader.

Message ID 20211014151343.254622-1-aldyh@redhat.com
State New
Headers show
Series Add ability to use full resolving path solver in the backward threader. | expand

Commit Message

Aldy Hernandez Oct. 14, 2021, 3:13 p.m. UTC 
The path solver runs in two modes: a quick mode which assumes any unknown
SSA names are VARYING, and a fully resolving mode using the ranger.

The backward threader currently uses the quick mode, because the fully
resolving mode was not available initially.  Since we now have the ability
in the solver (used by the hybrid threader), I thought it'd be useful to
have the knob for when the time comes.

Note that enabling the fully resolving mode will require some experimenting,
as enabling it would likely render other jump threading passes irrelevant
(VRP threading comes to mind).

There should be no functional changes as the resolver is set to false.

OK pending tests?

gcc/ChangeLog:

	* tree-ssa-threadbackward.c (class back_threader): Add m_resolve.
	(back_threader::back_threader): Same.
	(back_threader::resolve_phi): Try to solve without looking back if
	possible.
	(back_threader::find_paths_to_names): Same.
	(try_thread_blocks): Pass resolve argument to back threader.
	(pass_early_thread_jumps::execute): Same.
---
 gcc/tree-ssa-threadbackward.c | 41 ++++++++++++++++++++++++++++++-----
 1 file changed, 35 insertions(+), 6 deletions(-)

Comments

Jeff Law Oct. 14, 2021, 4:21 p.m. UTC | #1 
On 10/14/2021 9:13 AM, Aldy Hernandez wrote:
> The path solver runs in two modes: a quick mode which assumes any unknown
> SSA names are VARYING, and a fully resolving mode using the ranger.
>
> The backward threader currently uses the quick mode, because the fully
> resolving mode was not available initially.  Since we now have the ability
> in the solver (used by the hybrid threader), I thought it'd be useful to
> have the knob for when the time comes.
>
> Note that enabling the fully resolving mode will require some experimenting,
> as enabling it would likely render other jump threading passes irrelevant
> (VRP threading comes to mind).
>
> There should be no functional changes as the resolver is set to false.
>
> OK pending tests?
>
> gcc/ChangeLog:
>
> 	* tree-ssa-threadbackward.c (class back_threader): Add m_resolve.
> 	(back_threader::back_threader): Same.
> 	(back_threader::resolve_phi): Try to solve without looking back if
> 	possible.
> 	(back_threader::find_paths_to_names): Same.
> 	(try_thread_blocks): Pass resolve argument to back threader.
> 	(pass_early_thread_jumps::execute): Same.
OK
jeff
diff mbox series

Patch

diff --git a/gcc/tree-ssa-threadbackward.c b/gcc/tree-ssa-threadbackward.c
index 7c2c1112bee..8cc92a484fe 100644
--- a/gcc/tree-ssa-threadbackward.c
+++ b/gcc/tree-ssa-threadbackward.c
@@ -77,7 +77,7 @@  private:
 class back_threader
 {
 public:
-  back_threader (bool speed_p);
+  back_threader (bool speed_p, bool resolve);
   ~back_threader ();
   void maybe_thread_block (basic_block bb);
   bool thread_through_all_blocks (bool may_peel_loop_headers);
@@ -112,17 +112,22 @@  private:
   tree m_name;
   // Marker to differentiate unreachable edges.
   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.
+  bool m_resolve;
 };
 
 // Used to differentiate unreachable edges, so we may stop the search
 // in a the given direction.
 const edge back_threader::UNREACHABLE_EDGE = (edge) -1;
 
-back_threader::back_threader (bool speed_p)
+back_threader::back_threader (bool speed_p, bool resolve)
   : m_profit (speed_p),
-    m_solver (m_ranger, /*resolve=*/false)
+    m_solver (m_ranger, resolve)
 {
   m_last_stmt = NULL;
+  m_resolve = resolve;
 }
 
 back_threader::~back_threader ()
@@ -295,7 +300,23 @@  back_threader::resolve_phi (gphi *phi, bitmap interesting)
 
 	  bitmap_set_bit (interesting, v);
 	  bitmap_set_bit (m_imports, v);
-	  done |= find_paths_to_names (e->src, interesting);
+
+	  // When resolving unknowns, see if the incoming SSA can be
+	  // resolved on entry without having to keep looking back.
+	  bool keep_looking = true;
+	  if (m_resolve)
+	    {
+	      m_path.safe_push (e->src);
+	      if (maybe_register_path ())
+		{
+		  keep_looking = false;
+		  m_visited_bbs.add (e->src);
+		}
+	      m_path.pop ();
+	    }
+	  if (keep_looking)
+	    done |= find_paths_to_names (e->src, interesting);
+
 	  bitmap_clear_bit (interesting, v);
 	}
       else if (TREE_CODE (arg) == INTEGER_CST)
@@ -360,6 +381,14 @@  back_threader::find_paths_to_names (basic_block bb, bitmap interesting)
       return false;
     }
 
+  // Try to resolve the path with nothing but ranger knowledge.
+  if (m_resolve && m_path.length () > 1 && maybe_register_path ())
+    {
+      m_path.pop ();
+      m_visited_bbs.remove (bb);
+      return true;
+    }
+
   auto_bitmap processed;
   unsigned i;
   bool done = false;
@@ -936,7 +965,7 @@  static bool
 try_thread_blocks (function *fun)
 {
   /* Try to thread each block with more than one successor.  */
-  back_threader threader (/*speed_p=*/true);
+  back_threader threader (/*speed=*/true, /*resolve=*/false);
   basic_block bb;
   FOR_EACH_BB_FN (bb, fun)
     {
@@ -1005,7 +1034,7 @@  pass_early_thread_jumps::execute (function *fun)
   loop_optimizer_init (AVOID_CFG_MODIFICATIONS);
 
   /* Try to thread each block with more than one successor.  */
-  back_threader threader (/*speed_p=*/false);
+  back_threader threader (/*speed_p=*/false, /*resolve=*/false);
   basic_block bb;
   FOR_EACH_BB_FN (bb, fun)
     {