[gcc r12-4422] Add ability to use full resolving path solver in the backward threader.

[gcc r12-4422] Add ability to use full resolving path solver in the backward threader.

[Aldy Hernandez]

https://gcc.gnu.org/g:401aaa5983a7d31849b3b7a88f13eb6c7f74f11a

commit r12-4422-g401aaa5983a7d31849b3b7a88f13eb6c7f74f11a
Author: Aldy Hernandez <aldyh@redhat.com>
Date:   Thu Oct 14 15:01:49 2021 +0200

    Add ability to use full resolving path solver in the backward threader.
    
    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.
    
    Tested on x86-64 Linux.
    
    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.

Diff:
---
 gcc/tree-ssa-threadbackward.c | 41 +++++++++++++++++++++++++++++++++++------
 1 file changed, 35 insertions(+), 6 deletions(-)

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)
     {