[RFA] Optimize PHIs with constant arguments better

Time to come back to this now that the trunk is open again...


-------- Forwarded Message --------
Subject: [GCC 9][RFC][PATCH] Optimize PHIs with constant arguments better
Date: Thu, 30 Nov 2017 16:24:33 -0700
From: Jeff Law <law@redhat.com>
To: gcc-patches <gcc-patches@gcc.gnu.org>



This addresses some code quality regressions with some work scheduled
for gcc-9.  However, if anyone is aware of BZs that could be helped with
this patch, don't hesitate to pass them along.  Depending on their
severity we could always re-evaluate the plan for this patch.

The patch optimizes sequences like this:


 # iftmp.4_16 = PHI <0(7), 1(8), 0(9)>
 _30 = (unsigned char) iftmp.4_16;

ie, we have a PHI where all its arguments are known (differing)
constants.  The PHI feeds an operation which can be compile-time
evaluated for all the PHI's arguments.

This arises most often where the result of the PHI is type converted via
 NOP_EXPR.  But it also happens for a boolean comparisons, arithmetic
and logicals and other type conversions.

We can optimize away the statement by creating a new PHI node holding
the result of the statement applied to each of the original PHI's
constant operands.  So for the fragment above we'd generate:

 # iftmp.4_16 = PHI <0(7), 1(8), 0(9)>
 # _30 = PHI <0(7), 1(8), 0(9)>

These kind of backward propagations can cascade.  Here's an example I
saw during analysis of test results:

 # m_5 = PHI <10(5), 12(6), 14(7)>
<L13>:
  _2 = (long unsigned int) m_5;
  _3 = _2 * 32;
  goto <bb 12>; [100.00%]

After this patch the two statements have been eliminated in favor of
generating PHIs with constant arguments:

And after PHI propagation we have:
  # m_5 = PHI <10(5), 12(6), 14(7)>
  # _2 = PHI <10(5), 12(6), 14(7)>
  # _3 = PHI <320(5), 384(6), 448(7)>
<L13>:
  goto <bb 12>; [100.00%]

DCE will come along and wipe out m_5 and _2 if they are unused.

I initially covered just NOP_EXPR in the proof of concept.   But it's
trivial to extend to cover other unaries, and binary/comparisons where
one operand was already a constant, so I did that.  This applies
surprisingly often during a bootstrap.  An earlier version (which didn't
handle multiple uses of the result of the PHI) triggered over 6000 times
during a bootstrap:

NOP_EXPR    5161
LT_EXPR      658
GE_EXPR      504
NE_EXPR      310
BIT_NOT_EXPR 295
BIT_AND_EXPR  94
PLUS_EXPR     77
NEGATE_EXPR   48
LSHIFT_EXPR   40
EQ_EXPR       34
GT_EXPR       16
BIT_IOR_EXPR  10
MINUS_EXPR     8

There's actually other cases we could handle were

x = PHI (a, 0);
y = a & x;

Turns into

x = PHI (a, 0);
y = PHI (a, 0);


I'm not sure how often these non-constant cases happen -- I haven't
tried to support this or gain any data on how often this kind of case
might happen.

FWIW, there are cases were the PHI arguments are constant, but we still
can't simplify.  For example:


x = PHI (0, 1, 2)

y = 1234 / x;


When we process this we'll try to simplify 1234 / 0 to a constant which
fails.  We have to gracefully remove the partially initialized PHI node
in that case.  This is tested by existing tests in the suite.

You'll also see that certain tests in the suite such as pr61839_3,
ssa-pre-4.c are twiddled.  I've suppressed phi backwards propagation in
the original test so that it's not compromised.  THere's also a variant
of each test which verifies that the transformation is handled by phi
back propagation.

Bootstrapped and regression tested on x86, both in isolation and in a
larger patch series.

I see there's a couple whitespace issues in the patch.  I'll fix those.
I'd like to get comments/review on the meat of the patch though.



Jeff
* tree-ssa-phiprop.c (propagate_with_phi_1): Renamed from
	propagate_with_phi.
	(stmt_likely_produces_constant_result): New function.
	(fold_use_into_phi, propagate_with_phi_2):  Likewise.
	(pass_phiprop::execute): Corresponding changes.  Call
	propagate_with_phi_2.

	* gcc.dg/tree-ssa/pr61743-1.c: Use -fno-tree-phiprop.
	* gcc.dg/tree-ssa/pr61839_1.c: Likewise.
	* gcc.dg/tree-ssa/pr61839_3.c: Likewise.
	* gcc.dg/tree-ssa/ssa-pre-4.c: Likewise.

	* gcc.dg/tree-ssa/pr61743-1a.c: New test.
	* gcc.dg/tree-ssa/pr61839_1a.c: Likewise.
	* gcc.dg/tree-ssa/pr61839_3a.c: Likewise.
	* gcc.dg/tree-ssa/ssa-pre-4a.c: New test.

On Wed, May 2, 2018 at 12:44 AM, Jeff Law <law@redhat.com> wrote:
>
> Time to come back to this now that the trunk is open again...
>
>
> -------- Forwarded Message --------
> Subject: [GCC 9][RFC][PATCH] Optimize PHIs with constant arguments better
> Date: Thu, 30 Nov 2017 16:24:33 -0700
> From: Jeff Law <law@redhat.com>
> To: gcc-patches <gcc-patches@gcc.gnu.org>
>
>
>
> This addresses some code quality regressions with some work scheduled
> for gcc-9.  However, if anyone is aware of BZs that could be helped with
> this patch, don't hesitate to pass them along.  Depending on their
> severity we could always re-evaluate the plan for this patch.
>
> The patch optimizes sequences like this:
>
>
>  # iftmp.4_16 = PHI <0(7), 1(8), 0(9)>
>  _30 = (unsigned char) iftmp.4_16;
>
> ie, we have a PHI where all its arguments are known (differing)
> constants.  The PHI feeds an operation which can be compile-time
> evaluated for all the PHI's arguments.
>
> This arises most often where the result of the PHI is type converted via
>  NOP_EXPR.  But it also happens for a boolean comparisons, arithmetic
> and logicals and other type conversions.
>
> We can optimize away the statement by creating a new PHI node holding
> the result of the statement applied to each of the original PHI's
> constant operands.  So for the fragment above we'd generate:
>
>  # iftmp.4_16 = PHI <0(7), 1(8), 0(9)>
>  # _30 = PHI <0(7), 1(8), 0(9)>
>
> These kind of backward propagations can cascade.  Here's an example I
> saw during analysis of test results:
>
>  # m_5 = PHI <10(5), 12(6), 14(7)>
> <L13>:
>   _2 = (long unsigned int) m_5;
>   _3 = _2 * 32;
>   goto <bb 12>; [100.00%]
>
> After this patch the two statements have been eliminated in favor of
> generating PHIs with constant arguments:
>
> And after PHI propagation we have:
>   # m_5 = PHI <10(5), 12(6), 14(7)>
>   # _2 = PHI <10(5), 12(6), 14(7)>
>   # _3 = PHI <320(5), 384(6), 448(7)>
> <L13>:
>   goto <bb 12>; [100.00%]
>
> DCE will come along and wipe out m_5 and _2 if they are unused.
>
> I initially covered just NOP_EXPR in the proof of concept.   But it's
> trivial to extend to cover other unaries, and binary/comparisons where
> one operand was already a constant, so I did that.  This applies
> surprisingly often during a bootstrap.  An earlier version (which didn't
> handle multiple uses of the result of the PHI) triggered over 6000 times
> during a bootstrap:
>
> NOP_EXPR    5161
> LT_EXPR      658
> GE_EXPR      504
> NE_EXPR      310
> BIT_NOT_EXPR 295
> BIT_AND_EXPR  94
> PLUS_EXPR     77
> NEGATE_EXPR   48
> LSHIFT_EXPR   40
> EQ_EXPR       34
> GT_EXPR       16
> BIT_IOR_EXPR  10
> MINUS_EXPR     8
>
> There's actually other cases we could handle were
>
> x = PHI (a, 0);
> y = a & x;
>
> Turns into
>
> x = PHI (a, 0);
> y = PHI (a, 0);
>
>
> I'm not sure how often these non-constant cases happen -- I haven't
> tried to support this or gain any data on how often this kind of case
> might happen.
>
> FWIW, there are cases were the PHI arguments are constant, but we still
> can't simplify.  For example:
>
>
> x = PHI (0, 1, 2)
>
> y = 1234 / x;
>
>
> When we process this we'll try to simplify 1234 / 0 to a constant which
> fails.  We have to gracefully remove the partially initialized PHI node
> in that case.  This is tested by existing tests in the suite.
>
> You'll also see that certain tests in the suite such as pr61839_3,
> ssa-pre-4.c are twiddled.  I've suppressed phi backwards propagation in
> the original test so that it's not compromised.  THere's also a variant
> of each test which verifies that the transformation is handled by phi
> back propagation.
>
> Bootstrapped and regression tested on x86, both in isolation and in a
> larger patch series.
>
> I see there's a couple whitespace issues in the patch.  I'll fix those.
> I'd like to get comments/review on the meat of the patch though.

As a general comment I'd note what this patch does is sth that
PRE does as well (and quite aggressively so).  So I'd say if we
kind-of duplicate this transform we should tame it down (see comments
below).

Given it duplicates functionality I guess that you placed it inside
phiprop was mostly due to pass ordering as you mention jump
threading can happen earlier?  phiopt would have been another
natural choice.

>
>
> Jeff
>
>
>
>         * tree-ssa-phiprop.c (propagate_with_phi_1): Renamed from
>         propagate_with_phi.
>         (stmt_likely_produces_constant_result): New function.
>         (fold_use_into_phi, propagate_with_phi_2):  Likewise.
>         (pass_phiprop::execute): Corresponding changes.  Call
>         propagate_with_phi_2.
>
>         * gcc.dg/tree-ssa/pr61743-1.c: Use -fno-tree-phiprop.
>         * gcc.dg/tree-ssa/pr61839_1.c: Likewise.
>         * gcc.dg/tree-ssa/pr61839_3.c: Likewise.
>         * gcc.dg/tree-ssa/ssa-pre-4.c: Likewise.
>
>         * gcc.dg/tree-ssa/pr61743-1a.c: New test.
>         * gcc.dg/tree-ssa/pr61839_1a.c: Likewise.
>         * gcc.dg/tree-ssa/pr61839_3a.c: Likewise.
>         * gcc.dg/tree-ssa/ssa-pre-4a.c: New test.
>
> diff --git a/gcc/tree-ssa-phiprop.c b/gcc/tree-ssa-phiprop.c
> index 494158b..f2ec2b3 100644
> --- a/gcc/tree-ssa-phiprop.c
> +++ b/gcc/tree-ssa-phiprop.c
> @@ -259,8 +259,8 @@ chk_uses (tree, tree *idx, void *data)
>     with aliasing issues as we are moving memory reads.  */
>
>  static bool
> -propagate_with_phi (basic_block bb, gphi *phi, struct phiprop_d *phivn,
> -                   size_t n)
> +propagate_with_phi_1 (basic_block bb, gphi *phi, struct phiprop_d *phivn,
> +                     size_t n)
>  {
>    tree ptr = PHI_RESULT (phi);
>    gimple *use_stmt;
> @@ -440,6 +440,207 @@ next:;
>    return phi_inserted;
>  }
>
> +/* Return TRUE if USE_STMT, which uses PHI_RESULT will likely produce
> +   a constant result if PHI_RESULT is itself a constant.  Else return
> +   FALSE.
> +
> +   It is safe for this routine to always return TRUE.  If the result
> +   is not a constant it will be detected and properly handled later.
> +
> +   This is overly conservative.  If USE_STMT were to produce an SSA_NAME,
> +   then that would still work for our purposes.  */
> +
> +static bool
> +stmt_likely_produces_constant_result (gimple *use_stmt, tree phi_result)
> +{
> +  enum tree_code code = gimple_assign_rhs_code (use_stmt);
> +  switch (TREE_CODE_CLASS (code))
> +    {
> +    /* With few exceptions, a unary operator applied to a constant
> +       will result in a constant.  So they are OK without digging
> +       deeper into the operator/operands.  */
> +    case tcc_unary:
> +      return true;
> +
> +    /* For binary and comparisons we'll generally be able to generate
> +       a constant if only one operand is an SSA_NAME.  */
> +    case tcc_binary:
> +    case tcc_comparison:
> +      {
> +       tree rhs1 = gimple_assign_rhs1 (use_stmt);
> +       tree rhs2 = gimple_assign_rhs2 (use_stmt);
> +
> +       /* We need to check for RES op CONST and CONST op RES.  Consider
> +          MINUS_EXPR or MIN/MAX where RES could be the first or the second
> +          argument.  */
> +       if (rhs1 == phi_result
> +           && TREE_CODE_CLASS (TREE_CODE (rhs2)) == tcc_constant)
> +         return true;
> +
> +       if (rhs2 == phi_result
> +           && TREE_CODE_CLASS (TREE_CODE (rhs1)) == tcc_constant)
> +         return true;
> +
> +       /* We do not try to handle two SSA_NAME operands.  */
> +       return false;
> +      }
> +
> +    /* There might be some tcc_reference or tcc_exceptional types we
> +       could handle with deeper investigation.  COND_EXPR comes to mind.  */
> +    default:
> +      return false;
> +    }
> +}
> +
> +/* PHI in block BB produces RESULT.  PHI_RESULT is used in USE_STMT.
> +
> +   All of PHIs arguments are simple constants.  See if propagating
> +   the PHI arguments into USE_STMT produces a constant.  If that is
> +   the case for all the PHI arguments, then STMT is replaced with a
> +   new PHI and we return TRUE.  Else make no changes to the IL and
> +   return FALSE.
> +
> +   When applied this transformation reduces runtime computations and
> +   replaces them with either constant initializations.  This also enables
> +   jump threading to occur earlier in the optimization pipeline.  */
> +
> +static bool
> +fold_use_into_phi (gphi *phi, gimple *use_stmt,
> +                  basic_block bb, tree phi_result)
> +{
> +  /* Now verify the use is an assigment to an SSA_NAME.  */
> +  if (!is_gimple_assign (use_stmt)
> +      || TREE_CODE (gimple_assign_lhs (use_stmt)) != SSA_NAME)
> +    return false;
> +
> +  /* If USE_STMT does not likely produce a constant result, then
> +     do not try to fold this use.  Note this is overly conservative
> +     as we could handle USE_STMT simplifying to an SSA_NAME rather than
> +     just constants.  */
> +  if (!stmt_likely_produces_constant_result (use_stmt, phi_result))
> +    return false;
> +
> +  /* Build a new PHI node to replace the definition of the USE_STMT's LHS.  */
> +  gphi *new_phi = create_phi_node (NULL_TREE, bb);
> +
> +  /* Now fill in its arguments by applying the operator to each
> +     argument of the original PHI.  */

So rather than creating the PHI immediately please do sth like

  auto_vec<tree, 8> new_args;
  new_args.reserve_exact (gimple_phi_num_args (phi));
  FOR_EACH_EDGE (...)
    push-to-new-args-vec-or bail out

  alloc PHI and add args in second sweep over edges.

> +  edge e;
> +  edge_iterator ei;
> +  tree use_result = gimple_assign_lhs (use_stmt);
> +  tree type = TREE_TYPE (use_result);
> +  enum tree_code code = gimple_assign_rhs_code (use_stmt);
> +  FOR_EACH_EDGE (e, ei, bb->preds)
> +    {
> +      tree old_arg = PHI_ARG_DEF_FROM_EDGE (phi, e);
> +      tree new_arg;
> +
> +      switch (TREE_CODE_CLASS (code))
> +       {
> +       case tcc_unary:
> +         new_arg = fold_unary_to_constant (code, type, old_arg);
> +         break;
> +
> +       case tcc_binary:
> +       case tcc_comparison:
> +         {
> +           tree rhs1 = gimple_assign_rhs1 (use_stmt);
> +           tree rhs2 = gimple_assign_rhs2 (use_stmt);
> +         if (rhs1 == phi_result)
> +           new_arg = fold_binary (code, type,
> +                                  old_arg, gimple_assign_rhs2 (use_stmt));
> +         else if (rhs2 == phi_result)
> +           new_arg = fold_binary (code, type,
> +                                  gimple_assign_rhs1 (use_stmt), old_arg);
> +         else
> +           gcc_unreachable ();
> +         break;
> +         }

So I wonder if we don't want to be more aggressive here and not care
about PHI arg constant-ness or other operator state of the operation.

You should be able to do sth like (with the single-use constraint!)

   use_operand_p use_p;
   gimple *use_stmt;
   single_imm_use (gimple_phi_result (phi), &use_p, &use_stmt);
   tree orig_arg = USE_FROM_PTR (use_p);

 in the loop then do

    *(use_p->use) = phi-arg;  // do not use SET_USE to keep immediate
uses intact
    tree res = gimple_fold_stmt_to_constant (USE_STMT (use_p), NULL);
    if (is_gimple_min_invariant (res))
      OK, record it;
    else
      {
         *(use_p->use) = orig_arg;
         return false;
      }

I suspect the cases where we do have the first N edges to optimize to a constant
but a later one will fail the optimization isn't common.  As a early
bail-out we probably
want to avoid this transform on loop headers (thus when backedges are involved).

Note that for the case where we have n > 1 edges with constant
propagation result
it might be profitable to create a forwarder for the constant or
non-constant parts
thus end up with

     cst_result_1 = PHI< .... >;
     goto merge;

     orig_phi_2 = PHI< edges with non-cst-result... >;
     noncst_result_3 = OP (orig_phi_2);

     res_4 = PHI <cst_result_1, noncst_result_3>
merge:

where of course whether we may hoist OP () needs to be checked.

> +       default:
> +         gcc_unreachable ();
> +       }
> +
> +      /* We did not get a constant.  This can happen (imagine division
> +        by zero).  We have to remove the PHI from the IL, as the PHI
> +        is only partially constructed.  */
> +      if (!new_arg)
> +       {
> +         /* Set the PHI_RESULT to a new, throw-away SSA_NAME.  This avoids
> +            problems unlinking the "uses" of a currently NULL PHI_RESULT.  */
> +         gimple_phi_set_result (new_phi, make_ssa_name (type));
> +
> +         /* Actually remove the PHI from the IL.  It is safe to remove the
> +            PHI if some of its PHI arguments are still uninitialized.  */
> +         gimple_stmt_iterator gsi = gsi_for_stmt (new_phi);
> +         remove_phi_node (&gsi, true);
> +         return false;
> +       }
> +
> +      source_location locus = gimple_phi_arg_location_from_edge (phi, e);
> +      add_phi_arg (new_phi, new_arg, e, locus);
> +    }
> +
> +  gimple_phi_set_result (new_phi, use_result);
> +
> +  /* At this point we have our new PHI installed where we want it.
> +     Delete the old PHI and USE_STMT.  */
> +  gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt);
> +  gsi_remove (&gsi, true);
> +  return true;
> +}
> +
> +/* Look for sequences like this:
> +
> +    # iftmp.4_16 = PHI <0(7), 1(8), 0(9)>
> +    _30 = (unsigned char) iftmp.4_16;
> +
> +   We can "hoist" the conversion into the PHI and get it for free, generating:
> +
> +     # iftmp.4_16 = PHI <0(7), 1(8), 0(9)>
> +     # _30 = PHI <0(7), 1(8), 0(9)>
> +
> +   DCE will eliminate the first PHI.  In addition to getting the conversion
> +   for free, removal of the conversion improves backwards threading.  */
> +
> +static bool
> +propagate_with_phi_2 (basic_block bb, gphi *phi)
> +{
> +  /* First verify that all the arguments of the PHI are constants.
> +
> +     This is overly conservative.  Consider:
> +
> +       y = PHI (x, -1, 0);
> +       z = y & x;
> +
> +     We could transform that into:
> +
> +       y = PHI (x, -1, 0);
> +       z = PHI (x, x, 0);
> +
> +     It's not clear how important those cases are and we punt them
> +     for now.  */
> +  use_operand_p arg_p;
> +  ssa_op_iter i;
> +  FOR_EACH_PHI_ARG (arg_p, phi, i, SSA_OP_USE)
> +    {
> +      tree arg = USE_FROM_PTR (arg_p);
> +      if (TREE_CODE_CLASS (TREE_CODE (arg)) != tcc_constant)
> +       return false;
> +    }
> +
> +  /* Not iterate over each immediate use to see if the statement can
> +     be implemented as a PHI rather than a real statement.  */
> +  gimple *use_stmt;
> +  imm_use_iterator ui;
> +  bool retval = false;
> +  tree phi_result = PHI_RESULT (phi);
> +  FOR_EACH_IMM_USE_STMT (use_stmt, ui, phi_result)
> +    retval |= fold_use_into_phi (phi, use_stmt, bb, phi_result);

So you say DCE will remove the PHI but then you handle multiple
uses where some of them might fail to transform.

Thus should we restrict this to single-uses?  That way we also avoid
to end up with too many PHIs and we can remove the original PHI
immediately.

> +  return retval;
> +}
> +
>  /* Main entry for phiprop pass.  */
>
>  namespace {
> @@ -492,7 +693,10 @@ pass_phiprop::execute (function *fun)
>                                   single_succ (ENTRY_BLOCK_PTR_FOR_FN (fun)));
>    FOR_EACH_VEC_ELT (bbs, i, bb)
>      for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
> -      did_something |= propagate_with_phi (bb, gsi.phi (), phivn, n);
> +      {
> +          did_something |= propagate_with_phi_1 (bb, gsi.phi (), phivn, n);
> +         did_something |= propagate_with_phi_2 (bb, gsi.phi ());
> +      }
>
>    if (did_something)
>      gsi_commit_edge_inserts ();
>
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr61743-1.c b/gcc/testsuite/gcc.dg/tree-ssa/pr61743-1.c
> index a5c83cf..7771044 100644
> --- a/gcc/testsuite/gcc.dg/tree-ssa/pr61743-1.c
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr61743-1.c
> @@ -1,5 +1,5 @@
>  /* { dg-do compile } */
> -/* { dg-options "-O3 -funroll-loops -fno-tree-vectorize -fdump-tree-cunroll-details -fdump-tree-cunrolli-details -fno-peel-loops" } */
> +/* { dg-options "-O3 -fno-tree-phiprop -funroll-loops -fno-tree-vectorize -fdump-tree-cunroll-details -fdump-tree-cunrolli-details -fno-peel-loops" } */
>
>  #define N 8
>  #define M 14
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr61743-1a.c b/gcc/testsuite/gcc.dg/tree-ssa/pr61743-1a.c
> new file mode 100644
> index 0000000..dd64472
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr61743-1a.c
> @@ -0,0 +1,10 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O3 -funroll-loops -fno-tree-vectorize -fdump-tree-cunroll-details -fdump-tree-cunrolli-details -fdump-tree-phiprop -fno-peel-loops" } */
> +
> +#include "pr61743-1.c"
> +
> +/* { dg-final { scan-tree-dump-times "PHI <(\?:320|384|448)\\(\[0-9\]+\\), (\?:320|384|448)\\(\[0-9\]+\\), (\?:320|384|448)\\(\[0-9\]+\\)>" 1 "phiprop"} } */
> +
> +/* The code with PHI back propagation is simpler and we unswitch more.  */
> +/* { dg-final { scan-tree-dump-times "loop with 4 iterations completely unrolled" 10 "cunroll" } } */
> +/* { dg-final { scan-tree-dump-times "loop with 9 iterations completely unrolled" 2 "cunrolli" } } */
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr61839_1.c b/gcc/testsuite/gcc.dg/tree-ssa/pr61839_1.c
> index 9f8168a..5bf1982 100644
> --- a/gcc/testsuite/gcc.dg/tree-ssa/pr61839_1.c
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr61839_1.c
> @@ -1,6 +1,6 @@
>  /* PR tree-optimization/61839.  */
>  /* { dg-do run } */
> -/* { dg-options "-O2 -fdump-tree-vrp1 -fdump-tree-optimized" } */
> +/* { dg-options "-O2 -fdump-tree-vrp1 -fno-tree-phiprop -fdump-tree-optimized" } */
>  /* { dg-require-effective-target int32plus } */
>
>  __attribute__ ((noinline))
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr61839_1a.c b/gcc/testsuite/gcc.dg/tree-ssa/pr61839_1a.c
> new file mode 100644
> index 0000000..99a9016
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr61839_1a.c
> @@ -0,0 +1,11 @@
> +/* PR tree-optimization/61839.  */
> +/* { dg-do run } */
> +/* { dg-options "-O2 -fdump-tree-vrp1 -fdump-tree-phiprop" } */
> +/* { dg-require-effective-target int32plus } */
> +
> +#include "pr61839_1.c"
> +
> +/* Scan for c = 972195717) >> [0, 1] in function foo.  */
> +/* { dg-final { scan-tree-dump-times "486097858 : 972195717" 1  "vrp1" } } */
> +/* Scan for c = 972195717) >> [2, 3] in function bar.  */
> +/* { dg-final { scan-tree-dump-times "PHI <(?:243048929|121524464)\\(\[0-9\]+\\), (?:243048929|121524464)\\(\[0-9\]+\\)>" 1 "phiprop"} } */
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr61839_3.c b/gcc/testsuite/gcc.dg/tree-ssa/pr61839_3.c
> index 5ceb073..ad908c0 100644
> --- a/gcc/testsuite/gcc.dg/tree-ssa/pr61839_3.c
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr61839_3.c
> @@ -1,6 +1,6 @@
>  /* PR tree-optimization/61839.  */
>  /* { dg-do run } */
> -/* { dg-options "-O2 -fdump-tree-vrp1 -fdump-tree-optimized" } */
> +/* { dg-options "-O2 -fno-tree-phiprop -fdump-tree-vrp1 -fdump-tree-optimized" } */
>
>  __attribute__ ((noinline))
>  int foo (int a, unsigned b)
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr61839_3a.c b/gcc/testsuite/gcc.dg/tree-ssa/pr61839_3a.c
> new file mode 100644
> index 0000000..3a4d800
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr61839_3a.c
> @@ -0,0 +1,9 @@
> +/* PR tree-optimization/61839.  */
> +/* { dg-do run } */
> +/* { dg-options "-O2 -fdump-tree-phiprop -fdump-tree-optimized" } */
> +#include "pr61839_3.c"
> +
> +/* Scan for a PHI with (12, 13) << 8 in function foo.  */
> +/* { dg-final { scan-tree-dump-times "PHI <\(3072|3328\)\\(\[0-9\]+\\), \(3072|3328\)\\(\[0-9\
> +]+\\)>" 1 "phiprop"} } */
> +/* { dg-final { scan-tree-dump-times "3072" 0  "optimized" } } */
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-4.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-4.c
> index 5b4fd54..0bc5f73 100644
> --- a/gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-4.c
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-4.c
> @@ -1,5 +1,5 @@
>  /* { dg-do compile } */
> -/* { dg-options "-O2 -fdump-tree-pre-stats" } */
> +/* { dg-options "-O2 -fno-tree-phiprop -fdump-tree-pre-stats" } */
>  int foo(void)
>  {
>         int x, c, y;
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-4a.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-4a.c
> new file mode 100644
> index 0000000..70e8b16
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-4a.c
> @@ -0,0 +1,6 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-phiprop" } */
> +#include "ssa-pre-4.c"
> +/* We should eliminate the x+1 computation from this routine, replacing
> +   it with a phi of 3, 4 */
> +/* { dg-final { scan-tree-dump-times "PHI <\[34\]\\(\[0-9\]+\\), \[34\]\\(\[0-9\]+\\)>" 1 "phiprop"} } */
>