On Wed, May 2, 2018 at 12:44 AM, Jeff Law <l...@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 <l...@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"} } */
>
