Re: [PATCH] backwards threader: handle SSA names occurring in abnormal PHIs

On Thu, 13 Aug 2026, Aldy Hernandez wrote:

> [Andrew: are you OK with the changes to gimple_range_ssa_names and
> gimple_range_ssa_p, or would you prefer it to be solved a different
> way?]
> 
> [Richi/Jeff, are you OK with this, since you've done work in this area?]
> 
> The backward threader refuses to look at any SSA name occurring in an
> abnormal PHI, but DOM's threader does, at least for PHIs where the
> path taken does not include an abnormal edge.  For example:
> 
>     x_5(ab) = PHI <45(5), y_8(ab)>
>     ...
>     if (x_5 == 45)
> 
> If we're threading a path coming in from BB5, it's perfectly valid to
> thread this path, even if x_5 itself is AB.
> 
> This patch adds the functionality to the path solver, and also enables
> threading computed gotos whose destination occurs in an abnormal PHI,
> which happens when the goto block is itself one of the goto's targets.
> 
> I'm adding an abnormal_ok flag to gimple_range_ssa_p and
> gimple_range_ssa_names, defaulting to false, so path discovery and the
> solver track names occurring in abnormal PHIs like any other.
> 
> The flag lives in gimple_range_ssa_p rather than in a path solver
> local predicate because operand collection must agree with the
> predicate: gimple_range_ssa_names walks a statement's operands via the
> range-op handler and filters them with gimple_range_ssa_p.  A
> path-local version would have to duplicate all this.  I tried it both
> ways, and the path solver local predicate was fugly.

Hmm, there's no reason to not perform analysis on SSA names marked
as abnormal.  You'd not get any useful control expression for the
edges, but the copy part holds.  What you have to be careful with
is not disrupting coalescing during transforms because where
SSA names on abnormal edges (thus in PHI args) are special is that
you cannot insert a copy there, so we have to allocate the incoming
value and the PHI result to the same register.

So I wonder why gimple_range_ssa_p cares about abnormals at all.

What can be problematic is duplicating a PHI where the copy
inherits an abnormal incoming edge - extra copies of abnormally
marked SSA names are to be avoided.

So I wonder if you can split this up and remove the abnormal
restriction from range analysis (and see what breaks - I'm curious).

Richard.

> gcc/ChangeLog:
> 
> 	PR tree-optimization/126103
> 	* gimple-range-fold.h (gimple_range_ssa_p): Add abnormal_ok
> 	argument.
> 	* gimple-range-op.h (gimple_range_ssa_names): Same.
> 	* gimple-range-op.cc (gimple_range_ssa_names): Same.
> 	* gimple-range-path.cc (path_range_query::get_cache): Allow
> 	names occurring in abnormal PHIs.
> 	(path_range_query::ssa_range_in_phi): Assert the incoming path
> 	edge is not abnormal.
> 	(path_range_query::compute_exit_dependencies): Allow names
> 	occurring in abnormal PHIs.
> 	(path_range_query::maybe_register_phi_relation): Comment.
> 	* tree-ssa-threadbackward.cc (back_threader::find_paths_to_names):
> 	Follow abnormal PHIs and names occurring in abnormal PHIs.
> 	(back_threader::maybe_thread_block): Allow names occurring in
> 	abnormal PHIs.
> 
> gcc/testsuite/ChangeLog:
> 
> 	PR tree-optimization/126103
> 	* gcc.dg/tree-ssa/ssa-thread-abnormal-phi-1.c: New test.
> 	* gcc.dg/tree-ssa/ssa-thread-abnormal-phi-2.c: New test.
> 	* gcc.dg/tree-ssa/backthread-computed-goto-2.c: New test.
> ---
>  gcc/gimple-range-fold.h                       |  6 ++-
>  gcc/gimple-range-op.cc                        | 16 ++++---
>  gcc/gimple-range-op.h                         |  3 +-
>  gcc/gimple-range-path.cc                      | 11 ++++-
>  .../tree-ssa/backthread-computed-goto-2.c     | 22 +++++++++
>  .../tree-ssa/ssa-thread-abnormal-phi-1.c      | 46 +++++++++++++++++++
>  .../tree-ssa/ssa-thread-abnormal-phi-2.c      | 45 ++++++++++++++++++
>  gcc/tree-ssa-threadbackward.cc                | 11 ++---
>  8 files changed, 141 insertions(+), 19 deletions(-)
>  create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/backthread-computed-goto-2.c
>  create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-abnormal-phi-1.c
>  create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-abnormal-phi-2.c
> 
> diff --git a/gcc/gimple-range-fold.h b/gcc/gimple-range-fold.h
> index b11c179d173..13d7d56288e 100644
> --- a/gcc/gimple-range-fold.h
> +++ b/gcc/gimple-range-fold.h
> @@ -84,13 +84,15 @@ gimple_range_type (const gimple *s)
>  }
>  
>  // Return EXP if it is an SSA_NAME with a type supported by gimple ranges.
> +// If ABNORMAL_OK, also accept SSA names occurring in abnormal PHIs,
> +// which only the path solver can handle currently.
>  
>  inline tree
> -gimple_range_ssa_p (tree exp)
> +gimple_range_ssa_p (tree exp, bool abnormal_ok = false)
>  {
>    if (exp && TREE_CODE (exp) == SSA_NAME &&
>        !SSA_NAME_IS_VIRTUAL_OPERAND (exp) &&
> -      !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (exp) &&
> +      (abnormal_ok || !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (exp)) &&
>        value_range::supports_type_p (TREE_TYPE (exp)))
>      return exp;
>    return NULL_TREE;
> diff --git a/gcc/gimple-range-op.cc b/gcc/gimple-range-op.cc
> index 63eccc3fb9f..64db73bd912 100644
> --- a/gcc/gimple-range-op.cc
> +++ b/gcc/gimple-range-op.cc
> @@ -48,10 +48,12 @@ along with GCC; see the file COPYING3.  If not see
>  
>  // Given stmt S, fill VEC, up to VEC_SIZE elements, with relevant ssa-names
>  // on the statement.  For efficiency, it is an error to not pass in enough
> -// elements for the vector.  Return the number of ssa-names.
> +// elements for the vector.  Return the number of ssa-names.  If
> +// ABNORMAL_OK, also include SSA names occurring in abnormal PHIs.
>  
>  unsigned
> -gimple_range_ssa_names (tree *vec, unsigned vec_size, gimple *stmt)
> +gimple_range_ssa_names (tree *vec, unsigned vec_size, gimple *stmt,
> +			bool abnormal_ok)
>  {
>    tree ssa;
>    int count = 0;
> @@ -60,9 +62,9 @@ gimple_range_ssa_names (tree *vec, unsigned vec_size, gimple *stmt)
>    if (handler)
>      {
>        gcc_checking_assert (vec_size >= 2);
> -      if ((ssa = gimple_range_ssa_p (handler.operand1 ())))
> +      if ((ssa = gimple_range_ssa_p (handler.operand1 (), abnormal_ok)))
>  	vec[count++] = ssa;
> -      if ((ssa = gimple_range_ssa_p (handler.operand2 ())))
> +      if ((ssa = gimple_range_ssa_p (handler.operand2 (), abnormal_ok)))
>  	vec[count++] = ssa;
>      }
>    else if (is_a<gassign *> (stmt)
> @@ -70,11 +72,11 @@ gimple_range_ssa_names (tree *vec, unsigned vec_size, gimple *stmt)
>      {
>        gcc_checking_assert (vec_size >= 3);
>        gassign *st = as_a<gassign *> (stmt);
> -      if ((ssa = gimple_range_ssa_p (gimple_assign_rhs1 (st))))
> +      if ((ssa = gimple_range_ssa_p (gimple_assign_rhs1 (st), abnormal_ok)))
>  	vec[count++] = ssa;
> -      if ((ssa = gimple_range_ssa_p (gimple_assign_rhs2 (st))))
> +      if ((ssa = gimple_range_ssa_p (gimple_assign_rhs2 (st), abnormal_ok)))
>  	vec[count++] = ssa;
> -      if ((ssa = gimple_range_ssa_p (gimple_assign_rhs3 (st))))
> +      if ((ssa = gimple_range_ssa_p (gimple_assign_rhs3 (st), abnormal_ok)))
>  	vec[count++] = ssa;
>      }
>    return count;
> diff --git a/gcc/gimple-range-op.h b/gcc/gimple-range-op.h
> index 51da0ddebea..0425e122acf 100644
> --- a/gcc/gimple-range-op.h
> +++ b/gcc/gimple-range-op.h
> @@ -52,6 +52,7 @@ private:
>  // on the statement.  For efficiency, it is an error to not pass in enough
>  // elements for the vector.  Return the number of ssa-names.
>  
> -unsigned gimple_range_ssa_names (tree *vec, unsigned vec_size, gimple *stmt);
> +unsigned gimple_range_ssa_names (tree *vec, unsigned vec_size, gimple *stmt,
> +				 bool abnormal_ok = false);
>  
>  #endif // GCC_GIMPLE_RANGE_OP_H
> diff --git a/gcc/gimple-range-path.cc b/gcc/gimple-range-path.cc
> index 8a89da3dda3..4e62b25ffb2 100644
> --- a/gcc/gimple-range-path.cc
> +++ b/gcc/gimple-range-path.cc
> @@ -81,7 +81,7 @@ path_range_query::exit_dependency_p (tree name)
>  inline bool
>  path_range_query::get_cache (vrange &r, tree name)
>  {
> -  if (!gimple_range_ssa_p (name))
> +  if (!gimple_range_ssa_p (name, /*abnormal_ok=*/true))
>      return get_global_range_query ()->range_of_expr (r, name);
>  
>    return m_cache.get_range (r, name);
> @@ -256,6 +256,10 @@ path_range_query::ssa_range_in_phi (vrange &r, gphi *phi)
>    basic_block bb = gimple_bb (phi);
>    basic_block prev = prev_bb ();
>    edge e_in = find_edge (prev, bb);
> +  // The incoming edge the path supplies is never abnormal, so the
> +  // argument on it is a valid value for the PHI result even when the
> +  // result occurs in an abnormal PHI.
> +  gcc_checking_assert (!(e_in->flags & EDGE_ABNORMAL));
>    tree arg = PHI_ARG_DEF_FROM_EDGE (phi, e_in);
>    // Avoid using the cache for ARGs defined in this block, as
>    // that could create an ordering problem.
> @@ -526,7 +530,8 @@ path_range_query::compute_exit_dependencies (bitmap dependencies)
>        else if (gassign *ass = dyn_cast <gassign *> (def_stmt))
>  	{
>  	  tree ssa[3];
> -	  unsigned count = gimple_range_ssa_names (ssa, 3, ass);
> +	  unsigned count = gimple_range_ssa_names (ssa, 3, ass,
> +						   /*abnormal_ok=*/true);
>  	  for (unsigned j = 0; j < count; ++j)
>  	    if (add_to_exit_dependencies (ssa[j], dependencies))
>  	      worklist.safe_push (ssa[j]);
> @@ -691,6 +696,8 @@ path_range_query::maybe_register_phi_relation (gphi *phi, edge e)
>  {
>    tree arg = gimple_phi_arg_def (phi, e->dest_idx);
>  
> +  // Deliberately not abnormal_ok: keep names occurring in abnormal
> +  // PHIs out of the relation oracle.
>    if (!gimple_range_ssa_p (arg))
>      return;
>  
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/backthread-computed-goto-2.c b/gcc/testsuite/gcc.dg/tree-ssa/backthread-computed-goto-2.c
> new file mode 100644
> index 00000000000..86d0f688210
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/backthread-computed-goto-2.c
> @@ -0,0 +1,22 @@
> +/* PR tree-optimization/126103 */
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdisable-tree-ethread -fdump-tree-threadfull1-details" } */
> +
> +int g;
> +
> +void
> +h (int a)
> +{
> +  void *q;
> +  if (a)
> +    q = &&L0;
> +  else
> +    q = &&L2;
> +L2:
> +  g++;
> +  goto *q;
> +L0:
> +  return;
> +}
> +
> +/* { dg-final { scan-tree-dump-times "Registering jump thread" 2 "threadfull1" } } */
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-abnormal-phi-1.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-abnormal-phi-1.c
> new file mode 100644
> index 00000000000..7fe315fdea8
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-abnormal-phi-1.c
> @@ -0,0 +1,46 @@
> +/* PR tree-optimization/126103 */
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdisable-tree-ethread -fdump-tree-threadfull1-details" } */
> +
> +/* The conditional at "join" tests the result of an abnormal PHI:
> +   t = PHI <k(ab), 0, 0>.  Both normal predecessors feed constant 0,
> +   so the backward threader must thread them past the conditional;
> +   the abnormal predecessor keeps the original block.  The two normal
> +   predecessors of the computed goto also know its destination, so
> +   they are threaded as well.  */
> +
> +void foo (void);
> +void bar (void);
> +
> +void
> +f (int k)
> +{
> +  void *p = (k & 1) ? &&yes : &&join;
> +  int t;
> +
> +  if (k > 0)
> +    {
> +      t = k;
> +      goto *p;
> +    }
> +
> +  if (k < -5)
> +    {
> +      foo ();
> +      t = 0;
> +    }
> +  else
> +    {
> +      bar ();
> +      t = 0;
> +    }
> +
> +join:
> +  if (t != 0)
> +    {
> +yes:
> +      foo ();
> +    }
> +}
> +
> +/* { dg-final { scan-tree-dump-times "Registering jump thread" 4 "threadfull1" } } */
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-abnormal-phi-2.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-abnormal-phi-2.c
> new file mode 100644
> index 00000000000..8f74084ee2c
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-abnormal-phi-2.c
> @@ -0,0 +1,45 @@
> +/* PR tree-optimization/126103 */
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdisable-tree-ethread -fdump-tree-threadfull1-details" } */
> +
> +/* Like ssa-thread-abnormal-phi-1.c, but the conditional tests a value
> +   derived from the abnormal PHI.  */
> +
> +void foo (void);
> +void bar (void);
> +int g;
> +
> +void
> +f (int k)
> +{
> +  void *p = (k & 1) ? &&yes : &&join;
> +  int t;
> +
> +  if (k > 0)
> +    {
> +      t = k;
> +      goto *p;
> +    }
> +
> +  if (k < -5)
> +    {
> +      foo ();
> +      t = 1;
> +    }
> +  else
> +    {
> +      bar ();
> +      t = 0;
> +    }
> +
> +join:
> +  if (g)
> +    bar ();
> +  if ((t & 2) == 0)
> +    {
> +yes:
> +      foo ();
> +    }
> +}
> +
> +/* { dg-final { scan-tree-dump-times "Registering jump thread" 6 "threadfull1" } } */
> diff --git a/gcc/tree-ssa-threadbackward.cc b/gcc/tree-ssa-threadbackward.cc
> index 77726ba66cd..dd33ccfd23b 100644
> --- a/gcc/tree-ssa-threadbackward.cc
> +++ b/gcc/tree-ssa-threadbackward.cc
> @@ -450,17 +450,14 @@ back_threader::find_paths_to_names (basic_block bb, bitmap interesting,
>  		}
>  	      /* Local PHIs participate in renaming below.  */
>  	      if (gphi *phi = dyn_cast<gphi *> (def_stmt))
> -		{
> -		  tree res = gimple_phi_result (phi);
> -		  if (!SSA_NAME_OCCURS_IN_ABNORMAL_PHI (res))
> -		    interesting_phis.safe_push (phi);
> -		}
> +		interesting_phis.safe_push (phi);
>  	      /* For other local defs process their uses, amending
>  		 imports on the way.  */
>  	      else
>  		{
>  		  tree ssa[3];
> -		  unsigned lim = gimple_range_ssa_names (ssa, 3, def_stmt);
> +		  unsigned lim = gimple_range_ssa_names (ssa, 3, def_stmt,
> +							 /*abnormal_ok=*/true);
>  		  for (unsigned j = 0; j < lim; ++j)
>  		    {
>  		      tree rhs = ssa[j];
> @@ -564,7 +561,7 @@ back_threader::maybe_thread_block (basic_block bb)
>    tree name;
>    FOR_EACH_SSA_TREE_OPERAND (name, stmt, iter, SSA_OP_USE)
>      {
> -      if (!gimple_range_ssa_p (name))
> +      if (!gimple_range_ssa_p (name, /*abnormal_ok=*/true))
>  	return;
>        bitmap_set_bit (m_imports, SSA_NAME_VERSION (name));
>      }
> 

-- 
Richard Biener <[email protected]>
SUSE Software Solutions Germany GmbH,
Frankenstrasse 146, 90461 Nuernberg, Germany;
GF: Jochen Jaser, Andrew McDonald, Abhinav Puri; (HRB 36809, AG Nuernberg)