So if we have:
a = PHI <b, c>
d = use(a)
Try to optimize use(b) and use(c) [and the other values on the corresponding
edge].
This is for single uses as we don't want to increase the number of phis then
this can be
done at -Os. It allows for simple partial redundant caculation on the phi
entries.
Also this is cheapish since we only allow for single use and we remove the old
phi
and the old use statement too.
This is an RFC because we have a few failures including a go front-end issue.
The go front-end issue is debuged and a workaround patch is in PR 102138
comment #11.
I also ran into a case where pr46309-2.c started to fail; the analysis of the
failure
is located in PR 119988 (this is actually the second time I ran into this; the
first
time was with a similar patch but only handling conversions).
gcc.dg/builtin-object-size-[12].c is also failing but forwprop is doing the
correct
thing but the testcase is not expecting to translate:
```
if (x < 0)
r = &a.a[9];
else
r = &a.c[1];
...
t_1 = __builtin_object_size (r, 0)
```
as r is only a single use in the BOS here. I am trying to figure out if that is
ok and maybe we should still have a second use of r to force not doing the
forwprop.
I also have these testcase failures:
+FAIL: gcc.dg/tree-ssa/phi_on_compare-4.c scan-tree-dump threadfull1 "Jumps
threaded: 2"
+FAIL: gcc.dg/tree-ssa/pr61839_1.c scan-tree-dump-times vrp1 "243048929 :
121524464" 1
+FAIL: gcc.dg/tree-ssa/ssa-pre-32.c scan-tree-dump pre "# prephitmp_[0-9]+ =
PHI <[xy]_[0-9]+\\\\(D\\\\)[^,]*, [xy]_[0-9]+\\\\(D\\\\)"
+FAIL: gcc.dg/tree-ssa/ssa-pre-4.c scan-tree-dump-times pre "Eliminated: 1" 1
+FAIL: gcc.dg/tree-ssa/ssa-pre-5.c scan-tree-dump-times pre "Eliminated: 1" 1
But those just need to be fixed up as far as I can tell by disabling forwprop
and maybe make a secondary testcase for the forwprop optimization now.
I also have not collected data in any case to see how often this does something
or loops.
Also should this be forwprop or in phiprop?
Also if forwprop, should instead phiprop be integrated into forwprop and
removed?
I am thinking phiprop is a style of forwprop but I could be wrong.
Jeff also had a different version of this posted at
https://gcc.gnu.org/pipermail/gcc-patches/2017-November/489192.html
With some stats.
The main difference between this and his patch is this patch uses
gimple_fold_stmt_to_constant_1
while Jeff's patch did the combing himself to call fold.
gimple_fold_stmt_to_constant_1 has support for calls and even loads (though not
all loads). This
is part of the reason why I did it this way.
Plus this one does not a heurstic like his;
stmt_likely_produces_constant_result. Because
I wanted to handle the case where ssa names came back.
His patch is also adds it to phiprop rather than forwprop. I raised that as an
open question above.
Comments on Richard B.'s review to Jeff's patch:
> So rather than creating the PHI immediately please do sth like
I did exactly that even without noticing it in Richard's review.
> 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.
That is one of the bigger difference for sure here.
> As a early bail-out we probably
> want to avoid this transform on loop headers (thus when backedges are
> involved).
Since I am doing this on phis where the result only has a single use, it won't
have
an effect on backedges at all.
> 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.
Right that is why I limited it to a single use. I was thinking of that
before reading Richard's review.
Thanks,
Andrea Pinski
gcc/ChangeLog:
* tree-ssa-forwprop.cc (phi_valuization): New function.
(forwprop_phi): New function.
(pass_forwprop::execute): Call phi_valuization on all phis of a bb until
the no change is done.
Signed-off-by: Andrew Pinski <[email protected]>
---
gcc/tree-ssa-forwprop.cc | 180 +++++++++++++++++++++++++++++++++++++++
1 file changed, 180 insertions(+)
diff --git a/gcc/tree-ssa-forwprop.cc b/gcc/tree-ssa-forwprop.cc
index 9bb001d2f63..431735494bf 100644
--- a/gcc/tree-ssa-forwprop.cc
+++ b/gcc/tree-ssa-forwprop.cc
@@ -5272,6 +5272,168 @@ optimize_unreachable (basic_block bb)
return ret;
}
+static edge phi_valueization_edge;
+
+static tree phi_valuization (tree val)
+{
+ if (TREE_CODE (val) == SSA_NAME)
+ {
+ gphi *stmt = dyn_cast<gphi*> (SSA_NAME_DEF_STMT (val));
+ if (stmt
+ && gimple_bb (stmt) == phi_valueization_edge->dest)
+ return gimple_phi_arg_def (stmt, phi_valueization_edge->dest_idx);
+ }
+ return val;
+}
+
+
+/* Try to see if forwprop single use PHI will produces
+ simplifications and an example is:
+
+ a_1 = PHI <1 (2), 2 (3), 4(5)>
+ ...
+ b_2 = a_1 + 2;
+
+ This uses the values of the other phis on each edge too.
+ So having:
+ a_1 = PHI <1 (2), 2 (3), 4(5)>
+ b_2 = PHI <3 (2), 5 (3), 8(5)>
+ c_3 = a_1 + b_2;
+
+ will produce a simplified PHI of:
+ c_3 = PHI <4 (2), 7 (3), 12(5)>
+
+ This handles more than just constants for an example:
+ c_3 = PHI <a_1 (2), 0(3)>
+ d_4 = c_3 | a_1;
+
+ will produce a simplified PHI of:
+ d_4 = PHI <a_1 (2), a_1(3)>
+
+ Returns true if a phi was replaced. */
+
+static bool
+forwprop_phi (gphi *phi)
+{
+ tree res = gimple_phi_result (phi);
+ if (virtual_operand_p (res))
+ return false;
+ use_operand_p use;
+ gimple *use_stmt;
+ /* Handle only single use ssa names.
+ FIXME: this could be expanded to multiple use
+ but in the same statement. An example is `a*a`
+ where a's phi arguments are all constants. */
+ if (!single_imm_use (res, &use, &use_stmt))
+ return false;
+
+ /* Handle only assignments and calls.
+ FIXME: Handle GIMPLE_COND. Producing a
+ boolean might improve jump threading. */
+ if (!is_a<gassign*> (use_stmt)
+ && !is_a<gcall*> (use_stmt))
+ return false;
+
+ /* Can only do this if we are replacing a SSA NAME lhs. */
+ tree lhs = gimple_get_lhs (use_stmt);
+ if (!lhs || TREE_CODE (lhs) != SSA_NAME)
+ return false;
+
+ auto_vec<tree, 3> new_phi_args;
+ new_phi_args.reserve (gimple_phi_num_args (phi), true);
+ new_phi_args.quick_grow_cleared (gimple_phi_num_args (phi));
+ basic_block bb = gimple_bb (phi);
+ edge_iterator ei;
+ edge e;
+ FOR_EACH_EDGE (e, ei, bb->preds)
+ {
+ tree use = PHI_ARG_DEF_FROM_EDGE (phi, e);
+ /* This can only be done if we can prop the argument into the phi
+ result. An example where this matters is names that are
+ from abnormal edges. */
+ if (!may_propagate_copy (res, use))
+ return false;
+ phi_valueization_edge = e;
+ tree translated;
+
+ translated = gimple_fold_stmt_to_constant_1 (use_stmt, phi_valuization);
+ if (!translated)
+ return false;
+
+ /* Only invariants and ssa names can be used as phi arguments. */
+ if (!is_gimple_min_invariant (translated)
+ && TREE_CODE (translated) != SSA_NAME)
+ return false;
+
+ /* If we get back an ssa name, make sure it
+ is valid for the phi argument, that is the
+ definition is dominating the edge. */
+ if (TREE_CODE (translated) == SSA_NAME)
+ {
+ basic_block tbb = gimple_bb (SSA_NAME_DEF_STMT (translated));
+ basic_block ebb = e->src;
+ /* The translated defining statement needs to be dominated
+ by the edge's src bb. */
+ if (tbb
+ && tbb != ebb
+ && !dominated_by_p (CDI_DOMINATORS, tbb, ebb))
+ return false;
+ }
+ new_phi_args[e->dest_idx] = translated;
+ }
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "phi: ");
+ print_gimple_expr (dump_file, phi, 0);
+ fprintf (dump_file, "\n combined with: ");
+ print_gimple_expr (dump_file, use_stmt, 0);
+ fprintf (dump_file, "\nWill be replaced with:\n");
+ }
+
+ /* Create the new phi and fill it in. */
+ gphi *newphi = create_phi_node (lhs, gimple_bb (phi));
+ location_t use_locus = gimple_location (use_stmt);
+ tree first = NULL_TREE;
+ bool all_same = true;
+ for (unsigned i = 0; i < gimple_phi_num_args (phi); i++)
+ {
+ tree use = new_phi_args[i];
+ /* Record if all the same so we can update forwprop's lattice
+ for copy prop. */
+ if (!first)
+ first = use;
+ else if (! operand_equal_p (first, use, 0))
+ all_same = false;
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ tree arg = gimple_phi_arg_def (phi, i);
+ fprintf (dump_file, "arg: %u `", i);
+ print_generic_expr (dump_file, arg, TDF_SLIM);
+ fprintf (dump_file, "` translated to `");
+ print_generic_expr (dump_file, new_phi_args[i], TDF_SLIM);
+ fprintf (dump_file, "`.\n");
+ }
+ SET_PHI_ARG_DEF (newphi, i, use);
+ gimple_phi_arg_set_location (newphi, i, use_locus);
+ }
+
+ /* Remove the old use stmt. */
+ gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt);
+ gsi_remove (&gsi, true);
+ unlink_stmt_vdef (use_stmt);
+
+ /* Remove the old phi. */
+ gsi = gsi_for_stmt (phi);
+ remove_phi_node (&gsi, true);
+
+ /* Update the lattice if needed. */
+ if (all_same)
+ fwprop_set_lattice_val (lhs, first);
+
+ return true;
+}
+
unsigned int
pass_forwprop::execute (function *fun)
{
@@ -5400,9 +5562,27 @@ pass_forwprop::execute (function *fun)
if (may_propagate_copy (res, first))
to_remove_defs.safe_push (SSA_NAME_VERSION (res));
fwprop_set_lattice_val (res, first);
+ continue;
}
}
+ /* Try to forwprop PHIs and their arguments into
+ used once statements. */
+ if (!optimize_debug)
+ for (gphi_iterator si = gsi_start_phis (bb); !gsi_end_p (si);)
+ {
+ if (forwprop_phi (*si))
+ {
+ /* Start over if we replaced a phi as the iterator is
+ invalidated and we might have remved an usage for
+ another phi and also the new phi might have a single
+ usage. */
+ si = gsi_start_phis (bb);
+ continue;
+ }
+ gsi_next (&si);
+ }
+
/* Apply forward propagation to all stmts in the basic-block.
Note we update GSI within the loop as necessary. */
unsigned int uid = 1;
--
2.43.0
