Re: [PATCH] Fix various reassoc issues (PR tree-optimization/58791, tree-optimization/58775)
On Tue, Oct 22, 2013 at 6:09 AM, Jakub Jelinek wrote: > Hi! > > I've spent over two days looking at reassoc, fixing spots where > we invalidly reused SSA_NAMEs (this results in wrong-debug, as the added > guality testcases show, even some ICEs (pr58791-3.c) and wrong range info > for SSA_NAMEs) and cleaning up the stmt scheduling stuff (e.g. all gsi_move* > calls are gone, if we need to "move" something or set an SSA_NAME to > different value than previously, we'll now always create new > stmt and the old one depending on the case either remove or mark as visited > zero uses, so that it will be removed later on by reassociate_bb. > Of course some gimple_assign_set_rhs* etc. calls are still valid even > without creating new stmts, optimizing some statement to equivalent > computation is fine, but computing something different in an old SSA_NAME > is not. > > I've also noticed that build_and_add_sum was using different framework from > rewrite_expr_tree, the former was using stmt_dominates_stmt_p (which is IMHO > quite clean interface, but with the added uid stuff in reassoc can be > unnecessarily slow on large basic blocks) and rewrite_expr_tree was using > worse APIs, but using the uids. So, the patch also unifies that, into > a new reassoc_stmt_dominates_stmt_p that has the same semantics as the > tree-ssa-loop-niter.c function, but uses uids internally. rewrite_expr_tree > is changed so that it recurses first, then handles current level (which is > needed if the recursion needs to create new stmt and give back a new > SSA_NAME), which allowed removing the ensure_ops_are_available recursive > stuff. Also, uids are now computed in break_up_subtract_bb (and are per-bb, > starting with 1, we never compare uids from different bbs), which allows > us to get rid of an extra whole IL walk. > > For the inter-bb optimization, I had to stop modifying stmts right away > in update_range_test, because we don't want to reuse SSA_NAMEs and if we > modified there, we'd need to modify potentially many dependent SSA_NAMEs > and sometimes many times. So, now it instead just updates oe->op values > and maybe_optimize_range_tests just looks at those values and updates > what is needed. > > Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk? > > For 4.8 a partial backport would be possible, but quite a lot of work, > for 4.7 I'd prefer not to backport given that there gsi_for_stmt isn't O(1). > > 2013-10-22 Jakub Jelinek > > PR tree-optimization/58775 > PR tree-optimization/58791 > * tree-ssa-reassoc.c (reassoc_stmt_dominates_stmt_p): New function. > (insert_stmt_after): Rewritten, don't move the stmt, but really > insert it. > (get_stmt_uid_with_default): Remove. > (build_and_add_sum): Use insert_stmt_after and > reassoc_stmt_dominates_stmt_p. Fix up uid if bb contains only > labels. > (update_range_test): Set uid on stmts added by > force_gimple_operand_gsi. Don't immediately modify statements > in inter-bb optimization, just update oe->op values. > (optimize_range_tests): Return bool whether any changed have > been made. > (update_ops): New function. > (struct inter_bb_range_test_entry): New type. > (maybe_optimize_range_tests): Perform statement changes here. > (not_dominated_by, appears_later_in_bb, get_def_stmt, > ensure_ops_are_available): Remove. > (find_insert_point): Rewritten. > (rewrite_expr_tree): Remove MOVED argument, add CHANGED argument, > return LHS of the (new resp. old) stmt. Don't call > ensure_ops_are_available, don't reuse SSA_NAMEs, recurse first > instead of last, move new stmt at the right place. > (linearize_expr, repropagate_negates): Don't reuse SSA_NAMEs. > (negate_value): Likewise. Set uids. > (break_up_subtract_bb): Initialize uids. > (reassociate_bb): Adjust rewrite_expr_tree caller. > (do_reassoc): Don't call renumber_gimple_stmt_uids. > It caused: http://gcc.gnu.org/bugzilla/show_bug.cgi?id=59154 H.J.
Re: [PATCH] Fix various reassoc issues (PR tree-optimization/58791, tree-optimization/58775)
On 10/23/13 04:35, Jakub Jelinek wrote:
For debug info quality it actually isn't just about using different
SSA_NAME, but also not reusing the defining stmt; only then the code
will magically try to create debug temporaries and expressions from the old
dead defining stmt.
Joys. Something else to remember.
-/* Returns the UID of STMT if it is non-NULL. Otherwise return 1. */
+/* Returns true if statement S1 dominates statement S2. Like
+ stmt_dominates_stmt_p, but uses stmt UIDs to optimize. */
-static inline unsigned
-get_stmt_uid_with_default (gimple stmt)
+static bool
+reassoc_stmt_dominates_stmt_p (gimple s1, gimple s2)
+{
+ basic_block bb1 = gimple_bb (s1), bb2 = gimple_bb (s2);
+
+ if (!bb1 || s1 == s2)
+return true;
+
+ if (!bb2)
+return false;
Maybe this was carried over from somewhere else, but that looks
awful strange. When !bb1 you return true, but if !bb2 you return
false. At the least it deserves a comment.
bb{1,2} == NULL means a default definition of the corresponding lhs.
Ahh, it makes much more sense now.
ISTM that should be documented in the function header and in
stmt_dominates_stmt_p in. Yes, I know you're not responsible for this
mess, but better to get it cleaned up now since you're in there.
Obviously no need for a re-bootstrap to add that comment fix.
+ if (gimple_uid (s1) < gimple_uid (s2))
+ return true;
+
+ if (gimple_uid (s1) > gimple_uid (s2))
+ return false;
So if one (but not both) of the UIDs isn't set yet, one of these two
statements will return, which seems wrong since we don't know where
the statement without a UID is relative to the statement with a UID.
Am I missing something?
Right now we shouldn't see an unset uid here at all, unless it is a PHI,
which is handled earlier. break_up_subtract_bb initializes them for
all preexisting stmts, and the various places which add new stmts are
responsible for setting uid to either the uid of the immediately preceeding
or following stmt that has uid set (or 1 if the bb was previously empty).
OK. Might be worth a comment as well -- something as simple as only
PHIs have unset UIDs here. Once that precondition is known the code is
pretty easy to understand.
+ gimple_stmt_iterator gsi = gsi_for_stmt (s1);
+ unsigned int uid = gimple_uid (s1);
+ for (gsi_next (&gsi); !gsi_end_p (gsi); gsi_next (&gsi))
+ {
+ gimple s = gsi_stmt (gsi);
+ if (gimple_uid (s) != uid)
+ break;
+ if (s == s2)
+ return true;
+ }
Don't we only get here if both UIDs are zero (or the same by other
means)?If so does this code even make sense?
Both UIDs zero should not happen, both UIDs the same can happen, we don't
renumber the whole bb upon inserting something into the bb.
Ok.
Note the above isn't in any way a new code, just a cleanup of the
preexisting, just earlier the thing was done in more than one place
and could mishandle the uid setting.
I understand that. But I can easily see that the function is either
mis-named, poorly documented, or utter crap. The question is which is
it :-)
Anyway, from my understanding, insert_point is always a SSA_NAME setter
So let's get that documented. Again, once the precondition is
understood, the code makes more sense.
At this point my only concerns are getting those functions documented a
bit better -- which you can do as a pre-approved followup.
Being away from GCC for a long time has actually been good in some ways
in that I don't have experience with much of the new bits. Thus I rely
a lot more on comments, function/variable names, etc to provide some of
the context.
Jeff
Re: [PATCH] Fix various reassoc issues (PR tree-optimization/58791, tree-optimization/58775)
On Wed, Oct 23, 2013 at 01:54:05PM +0200, Richard Biener wrote:
> I'm ok with the patch. Not sure if we want to backport it at all - we
> will only have wrong-debug issues (well, "only").
I've added some comments and one assert (that the uids are non-zero).
Because of that assertion I'll bootstrap/regtest it again.
2013-10-23 Jakub Jelinek
PR tree-optimization/58775
PR tree-optimization/58791
* tree-ssa-reassoc.c (reassoc_stmt_dominates_stmt_p): New function.
(insert_stmt_after): Rewritten, don't move the stmt, but really
insert it.
(get_stmt_uid_with_default): Remove.
(build_and_add_sum): Use insert_stmt_after and
reassoc_stmt_dominates_stmt_p. Fix up uid if bb contains only
labels.
(update_range_test): Set uid on stmts added by
force_gimple_operand_gsi. Don't immediately modify statements
in inter-bb optimization, just update oe->op values.
(optimize_range_tests): Return bool whether any changed have
been made.
(update_ops): New function.
(struct inter_bb_range_test_entry): New type.
(maybe_optimize_range_tests): Perform statement changes here.
(not_dominated_by, appears_later_in_bb, get_def_stmt,
ensure_ops_are_available): Remove.
(find_insert_point): Rewritten.
(rewrite_expr_tree): Remove MOVED argument, add CHANGED argument,
return LHS of the (new resp. old) stmt. Don't call
ensure_ops_are_available, don't reuse SSA_NAMEs, recurse first
instead of last, move new stmt at the right place.
(linearize_expr, repropagate_negates): Don't reuse SSA_NAMEs.
(negate_value): Likewise. Set uids.
(break_up_subtract_bb): Initialize uids.
(reassociate_bb): Adjust rewrite_expr_tree caller.
(do_reassoc): Don't call renumber_gimple_stmt_uids.
* gcc.dg/guality/pr58791-1.c: New test.
* gcc.dg/guality/pr58791-2.c: New test.
* gcc.dg/guality/pr58791-3.c: New test.
* gcc.dg/guality/pr58791-4.c: New test.
* gcc.dg/guality/pr58791-5.c: New test.
* gcc.c-torture/compile/pr58775.c: New test.
* gcc.dg/tree-ssa/reassoc-28.c: Don't scan reassoc1 dump.
--- gcc/tree-ssa-reassoc.c.jj 2013-10-22 18:36:51.880395382 +0200
+++ gcc/tree-ssa-reassoc.c 2013-10-23 12:54:49.550475286 +0200
@@ -1143,12 +1143,94 @@ zero_one_operation (tree *def, enum tree
while (1);
}
-/* Returns the UID of STMT if it is non-NULL. Otherwise return 1. */
+/* Returns true if statement S1 dominates statement S2. Like
+ stmt_dominates_stmt_p, but uses stmt UIDs to optimize. */
-static inline unsigned
-get_stmt_uid_with_default (gimple stmt)
+static bool
+reassoc_stmt_dominates_stmt_p (gimple s1, gimple s2)
+{
+ basic_block bb1 = gimple_bb (s1), bb2 = gimple_bb (s2);
+
+ /* If bb1 is NULL, it should be a GIMPLE_NOP def stmt of an (D)
+ SSA_NAME. Assume it lives at the beginning of function and
+ thus dominates everything. */
+ if (!bb1 || s1 == s2)
+return true;
+
+ /* If bb2 is NULL, it doesn't dominate any stmt with a bb. */
+ if (!bb2)
+return false;
+
+ if (bb1 == bb2)
+{
+ /* PHIs in the same basic block are assumed to be
+executed all in parallel, if only one stmt is a PHI,
+it dominates the other stmt in the same basic block. */
+ if (gimple_code (s1) == GIMPLE_PHI)
+ return true;
+
+ if (gimple_code (s2) == GIMPLE_PHI)
+ return false;
+
+ gcc_assert (gimple_uid (s1) && gimple_uid (s2));
+
+ if (gimple_uid (s1) < gimple_uid (s2))
+ return true;
+
+ if (gimple_uid (s1) > gimple_uid (s2))
+ return false;
+
+ gimple_stmt_iterator gsi = gsi_for_stmt (s1);
+ unsigned int uid = gimple_uid (s1);
+ for (gsi_next (&gsi); !gsi_end_p (gsi); gsi_next (&gsi))
+ {
+ gimple s = gsi_stmt (gsi);
+ if (gimple_uid (s) != uid)
+ break;
+ if (s == s2)
+ return true;
+ }
+
+ return false;
+}
+
+ return dominated_by_p (CDI_DOMINATORS, bb2, bb1);
+}
+
+/* Insert STMT after INSERT_POINT. */
+
+static void
+insert_stmt_after (gimple stmt, gimple insert_point)
{
- return stmt ? gimple_uid (stmt) : 1;
+ gimple_stmt_iterator gsi;
+ basic_block bb;
+
+ if (gimple_code (insert_point) == GIMPLE_PHI)
+bb = gimple_bb (insert_point);
+ else if (!stmt_ends_bb_p (insert_point))
+{
+ gsi = gsi_for_stmt (insert_point);
+ gimple_set_uid (stmt, gimple_uid (insert_point));
+ gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
+ return;
+}
+ else
+/* We assume INSERT_POINT is a SSA_NAME_DEF_STMT of some SSA_NAME,
+ thus if it must end a basic block, it should be a call that can
+ throw, or some assignment that can throw. If it throws, the LHS
+ of it will not be initialized though, so only valid places using
+ the SSA_NAME should be dominated by the
Re: [PATCH] Fix various reassoc issues (PR tree-optimization/58791, tree-optimization/58775)
On Wed, 23 Oct 2013, Jakub Jelinek wrote:
> On Tue, Oct 22, 2013 at 12:47:41PM -0600, Jeff Law wrote:
> > On 10/22/13 07:09, Jakub Jelinek wrote:
> > >I've spent over two days looking at reassoc, fixing spots where
> > >we invalidly reused SSA_NAMEs (this results in wrong-debug, as the added
> > >guality testcases show, even some ICEs (pr58791-3.c) and wrong range info
> > >for SSA_NAMEs)
>
> > This is something we all need to remember, directly reusing an
> > existing SSA_NAME for a new value and the like this is bad. It's
> > far better to release the name back to the manager and grab a new
> > one.
>
> For debug info quality it actually isn't just about using different
> SSA_NAME, but also not reusing the defining stmt; only then the code
> will magically try to create debug temporaries and expressions from the old
> dead defining stmt.
>
> > >-/* Returns the UID of STMT if it is non-NULL. Otherwise return 1. */
> > >+/* Returns true if statement S1 dominates statement S2. Like
> > >+ stmt_dominates_stmt_p, but uses stmt UIDs to optimize. */
> > >
> > >-static inline unsigned
> > >-get_stmt_uid_with_default (gimple stmt)
> > >+static bool
> > >+reassoc_stmt_dominates_stmt_p (gimple s1, gimple s2)
> > >+{
> > >+ basic_block bb1 = gimple_bb (s1), bb2 = gimple_bb (s2);
> > >+
> > >+ if (!bb1 || s1 == s2)
> > >+return true;
> > >+
> > >+ if (!bb2)
> > >+return false;
> > Maybe this was carried over from somewhere else, but that looks
> > awful strange. When !bb1 you return true, but if !bb2 you return
> > false. At the least it deserves a comment.
>
> bb{1,2} == NULL means a default definition of the corresponding lhs.
> If bb2 is NULL and bb1 is not, then s2 (assumed to be at the beginning of
> function) certainly doesn't dominate s1, if bb2 is not NULL and bb1 is, then
> s1 (assumed to be at the beginning of function) dominates s2, if both bb1
> and bb2 are NULL, then both are assumed to be at the same spot, so like the
> s1 == s2 case.
>
> Note, the if (!bb1 || s1 == s2) return true; comes from the
> tree-ssa-loop-niter.c origin, if (!bb2) return false; does not.
>
> > >+ if (bb1 == bb2)
> > >+{
> > >+ if (gimple_code (s2) == GIMPLE_PHI)
> > >+ return false;
> > >+
> > >+ if (gimple_code (s1) == GIMPLE_PHI)
> > >+ return true;
> > Deserves a comment. I know what's going on here, but it's easier to
> > read it in a comment rather than recalling the all-phis-in-parallel
> > rule and verifying this handles that correctly.
>
> Ok.
>
> > >+ if (gimple_uid (s1) < gimple_uid (s2))
> > >+ return true;
> > >+
> > >+ if (gimple_uid (s1) > gimple_uid (s2))
> > >+ return false;
> > So if one (but not both) of the UIDs isn't set yet, one of these two
> > statements will return, which seems wrong since we don't know where
> > the statement without a UID is relative to the statement with a UID.
> > Am I missing something?
>
> Right now we shouldn't see an unset uid here at all, unless it is a PHI,
> which is handled earlier. break_up_subtract_bb initializes them for
> all preexisting stmts, and the various places which add new stmts are
> responsible for setting uid to either the uid of the immediately preceeding
> or following stmt that has uid set (or 1 if the bb was previously empty).
>
> > >+ gimple_stmt_iterator gsi = gsi_for_stmt (s1);
> > >+ unsigned int uid = gimple_uid (s1);
> > >+ for (gsi_next (&gsi); !gsi_end_p (gsi); gsi_next (&gsi))
> > >+ {
> > >+gimple s = gsi_stmt (gsi);
> > >+if (gimple_uid (s) != uid)
> > >+ break;
> > >+if (s == s2)
> > >+ return true;
> > >+ }
> > Don't we only get here if both UIDs are zero (or the same by other
> > means)?If so does this code even make sense?
>
> Both UIDs zero should not happen, both UIDs the same can happen, we don't
> renumber the whole bb upon inserting something into the bb.
> >
> >
> > >+
> > >+/* Insert STMT after INSERT_POINT. */
> > >+
> > >+static void
> > >+insert_stmt_after (gimple stmt, gimple insert_point)
> > > {
> > >- return stmt ? gimple_uid (stmt) : 1;
> > >+ gimple_stmt_iterator gsi;
> > >+ basic_block bb;
> > >+
> > >+ if (gimple_code (insert_point) == GIMPLE_PHI)
> > >+bb = gimple_bb (insert_point);
> > >+ else if (!stmt_ends_bb_p (insert_point))
> > >+{
> > >+ gsi = gsi_for_stmt (insert_point);
> > >+ gimple_set_uid (stmt, gimple_uid (insert_point));
> > >+ gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
> > >+ return;
> > >+}
> > >+ else
> > >+bb = find_fallthru_edge (gimple_bb (insert_point)->succs)->dest;
> > >+ gsi = gsi_after_labels (bb);
> > >+ if (gsi_end_p (gsi))
> > >+{
> > >+ gimple_stmt_iterator gsi2 = gsi_last_bb (bb);
> > >+ gimple_set_uid (stmt,
> > >+gsi_end_p (gsi2) ? 1 : gimple_uid (gsi_stmt (gsi2)));
> > >+}
> > >+ else
> > >+gimple_set_uid (stmt, gimple_uid (gsi_stmt (gsi)));
> > >+ gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
> > So
Re: [PATCH] Fix various reassoc issues (PR tree-optimization/58791, tree-optimization/58775)
On Tue, Oct 22, 2013 at 12:47:41PM -0600, Jeff Law wrote:
> On 10/22/13 07:09, Jakub Jelinek wrote:
> >I've spent over two days looking at reassoc, fixing spots where
> >we invalidly reused SSA_NAMEs (this results in wrong-debug, as the added
> >guality testcases show, even some ICEs (pr58791-3.c) and wrong range info
> >for SSA_NAMEs)
> This is something we all need to remember, directly reusing an
> existing SSA_NAME for a new value and the like this is bad. It's
> far better to release the name back to the manager and grab a new
> one.
For debug info quality it actually isn't just about using different
SSA_NAME, but also not reusing the defining stmt; only then the code
will magically try to create debug temporaries and expressions from the old
dead defining stmt.
> >-/* Returns the UID of STMT if it is non-NULL. Otherwise return 1. */
> >+/* Returns true if statement S1 dominates statement S2. Like
> >+ stmt_dominates_stmt_p, but uses stmt UIDs to optimize. */
> >
> >-static inline unsigned
> >-get_stmt_uid_with_default (gimple stmt)
> >+static bool
> >+reassoc_stmt_dominates_stmt_p (gimple s1, gimple s2)
> >+{
> >+ basic_block bb1 = gimple_bb (s1), bb2 = gimple_bb (s2);
> >+
> >+ if (!bb1 || s1 == s2)
> >+return true;
> >+
> >+ if (!bb2)
> >+return false;
> Maybe this was carried over from somewhere else, but that looks
> awful strange. When !bb1 you return true, but if !bb2 you return
> false. At the least it deserves a comment.
bb{1,2} == NULL means a default definition of the corresponding lhs.
If bb2 is NULL and bb1 is not, then s2 (assumed to be at the beginning of
function) certainly doesn't dominate s1, if bb2 is not NULL and bb1 is, then
s1 (assumed to be at the beginning of function) dominates s2, if both bb1
and bb2 are NULL, then both are assumed to be at the same spot, so like the
s1 == s2 case.
Note, the if (!bb1 || s1 == s2) return true; comes from the
tree-ssa-loop-niter.c origin, if (!bb2) return false; does not.
> >+ if (bb1 == bb2)
> >+{
> >+ if (gimple_code (s2) == GIMPLE_PHI)
> >+return false;
> >+
> >+ if (gimple_code (s1) == GIMPLE_PHI)
> >+return true;
> Deserves a comment. I know what's going on here, but it's easier to
> read it in a comment rather than recalling the all-phis-in-parallel
> rule and verifying this handles that correctly.
Ok.
> >+ if (gimple_uid (s1) < gimple_uid (s2))
> >+return true;
> >+
> >+ if (gimple_uid (s1) > gimple_uid (s2))
> >+return false;
> So if one (but not both) of the UIDs isn't set yet, one of these two
> statements will return, which seems wrong since we don't know where
> the statement without a UID is relative to the statement with a UID.
> Am I missing something?
Right now we shouldn't see an unset uid here at all, unless it is a PHI,
which is handled earlier. break_up_subtract_bb initializes them for
all preexisting stmts, and the various places which add new stmts are
responsible for setting uid to either the uid of the immediately preceeding
or following stmt that has uid set (or 1 if the bb was previously empty).
> >+ gimple_stmt_iterator gsi = gsi_for_stmt (s1);
> >+ unsigned int uid = gimple_uid (s1);
> >+ for (gsi_next (&gsi); !gsi_end_p (gsi); gsi_next (&gsi))
> >+{
> >+ gimple s = gsi_stmt (gsi);
> >+ if (gimple_uid (s) != uid)
> >+break;
> >+ if (s == s2)
> >+return true;
> >+}
> Don't we only get here if both UIDs are zero (or the same by other
> means)?If so does this code even make sense?
Both UIDs zero should not happen, both UIDs the same can happen, we don't
renumber the whole bb upon inserting something into the bb.
>
>
> >+
> >+/* Insert STMT after INSERT_POINT. */
> >+
> >+static void
> >+insert_stmt_after (gimple stmt, gimple insert_point)
> > {
> >- return stmt ? gimple_uid (stmt) : 1;
> >+ gimple_stmt_iterator gsi;
> >+ basic_block bb;
> >+
> >+ if (gimple_code (insert_point) == GIMPLE_PHI)
> >+bb = gimple_bb (insert_point);
> >+ else if (!stmt_ends_bb_p (insert_point))
> >+{
> >+ gsi = gsi_for_stmt (insert_point);
> >+ gimple_set_uid (stmt, gimple_uid (insert_point));
> >+ gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
> >+ return;
> >+}
> >+ else
> >+bb = find_fallthru_edge (gimple_bb (insert_point)->succs)->dest;
> >+ gsi = gsi_after_labels (bb);
> >+ if (gsi_end_p (gsi))
> >+{
> >+ gimple_stmt_iterator gsi2 = gsi_last_bb (bb);
> >+ gimple_set_uid (stmt,
> >+ gsi_end_p (gsi2) ? 1 : gimple_uid (gsi_stmt (gsi2)));
> >+}
> >+ else
> >+gimple_set_uid (stmt, gimple_uid (gsi_stmt (gsi)));
> >+ gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
> So from reading the name of the function, it's not clear that this
> inserts on the fallthru edge in the case where INSERT_POINT is the
> end of a block. And does that make sense? ISTM you'd want it on
> all the outgoing edges. And you have to worry about things like
Re: [PATCH] Fix various reassoc issues (PR tree-optimization/58791, tree-optimization/58775)
On 10/22/13 07:09, Jakub Jelinek wrote:
Hi!
I've spent over two days looking at reassoc, fixing spots where
we invalidly reused SSA_NAMEs (this results in wrong-debug, as the added
guality testcases show, even some ICEs (pr58791-3.c) and wrong range info
for SSA_NAMEs)
This is something we all need to remember, directly reusing an existing
SSA_NAME for a new value and the like this is bad. It's far better to
release the name back to the manager and grab a new one.
and cleaning up the stmt scheduling stuff (e.g. all gsi_move*
calls are gone, if we need to "move" something or set an SSA_NAME to
different value than previously, we'll now always create new
stmt and the old one depending on the case either remove or mark as visited
zero uses, so that it will be removed later on by reassociate_bb.
Goodness.
Of course some gimple_assign_set_rhs* etc. calls are still valid even
without creating new stmts, optimizing some statement to equivalent
computation is fine, but computing something different in an old SSA_NAME
is not.
Right.
Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?
For 4.8 a partial backport would be possible, but quite a lot of work,
for 4.7 I'd prefer not to backport given that there gsi_for_stmt isn't O(1).
2013-10-22 Jakub Jelinek
PR tree-optimization/58775
PR tree-optimization/58791
* tree-ssa-reassoc.c (reassoc_stmt_dominates_stmt_p): New function.
(insert_stmt_after): Rewritten, don't move the stmt, but really
insert it.
(get_stmt_uid_with_default): Remove.
(build_and_add_sum): Use insert_stmt_after and
reassoc_stmt_dominates_stmt_p. Fix up uid if bb contains only
labels.
(update_range_test): Set uid on stmts added by
force_gimple_operand_gsi. Don't immediately modify statements
in inter-bb optimization, just update oe->op values.
(optimize_range_tests): Return bool whether any changed have
been made.
(update_ops): New function.
(struct inter_bb_range_test_entry): New type.
(maybe_optimize_range_tests): Perform statement changes here.
(not_dominated_by, appears_later_in_bb, get_def_stmt,
ensure_ops_are_available): Remove.
(find_insert_point): Rewritten.
(rewrite_expr_tree): Remove MOVED argument, add CHANGED argument,
return LHS of the (new resp. old) stmt. Don't call
ensure_ops_are_available, don't reuse SSA_NAMEs, recurse first
instead of last, move new stmt at the right place.
(linearize_expr, repropagate_negates): Don't reuse SSA_NAMEs.
(negate_value): Likewise. Set uids.
(break_up_subtract_bb): Initialize uids.
(reassociate_bb): Adjust rewrite_expr_tree caller.
(do_reassoc): Don't call renumber_gimple_stmt_uids.
* gcc.dg/guality/pr58791-1.c: New test.
* gcc.dg/guality/pr58791-2.c: New test.
* gcc.dg/guality/pr58791-3.c: New test.
* gcc.dg/guality/pr58791-4.c: New test.
* gcc.dg/guality/pr58791-5.c: New test.
* gcc.c-torture/compile/pr58775.c: New test.
* gcc.dg/tree-ssa/reassoc-28.c: Don't scan reassoc1 dump.
--- gcc/tree-ssa-reassoc.c.jj 2013-10-21 09:00:25.0 +0200
+++ gcc/tree-ssa-reassoc.c 2013-10-22 12:04:38.693490273 +0200
@@ -1143,12 +1143,80 @@ zero_one_operation (tree *def, enum tree
while (1);
}
-/* Returns the UID of STMT if it is non-NULL. Otherwise return 1. */
+/* Returns true if statement S1 dominates statement S2. Like
+ stmt_dominates_stmt_p, but uses stmt UIDs to optimize. */
-static inline unsigned
-get_stmt_uid_with_default (gimple stmt)
+static bool
+reassoc_stmt_dominates_stmt_p (gimple s1, gimple s2)
+{
+ basic_block bb1 = gimple_bb (s1), bb2 = gimple_bb (s2);
+
+ if (!bb1 || s1 == s2)
+return true;
+
+ if (!bb2)
+return false;
Maybe this was carried over from somewhere else, but that looks awful
strange. When !bb1 you return true, but if !bb2 you return false. At
the least it deserves a comment.
+
+ if (bb1 == bb2)
+{
+ if (gimple_code (s2) == GIMPLE_PHI)
+ return false;
+
+ if (gimple_code (s1) == GIMPLE_PHI)
+ return true;
Deserves a comment. I know what's going on here, but it's easier to
read it in a comment rather than recalling the all-phis-in-parallel rule
and verifying this handles that correctly.
+
+ if (gimple_uid (s1) < gimple_uid (s2))
+ return true;
+
+ if (gimple_uid (s1) > gimple_uid (s2))
+ return false;
So if one (but not both) of the UIDs isn't set yet, one of these two
statements will return, which seems wrong since we don't know where the
statement without a UID is relative to the statement with a UID. Am I
missing something?
+
+ gimple_stmt_iterator gsi = gsi_for_stmt (s1);
+ unsigned int uid = gimple_uid (s1);
+ for (gsi_next (&gsi); !gsi_end_p (gsi); gsi_next (&gsi))
+ {
+
[PATCH] Fix various reassoc issues (PR tree-optimization/58791, tree-optimization/58775)
Hi!
I've spent over two days looking at reassoc, fixing spots where
we invalidly reused SSA_NAMEs (this results in wrong-debug, as the added
guality testcases show, even some ICEs (pr58791-3.c) and wrong range info
for SSA_NAMEs) and cleaning up the stmt scheduling stuff (e.g. all gsi_move*
calls are gone, if we need to "move" something or set an SSA_NAME to
different value than previously, we'll now always create new
stmt and the old one depending on the case either remove or mark as visited
zero uses, so that it will be removed later on by reassociate_bb.
Of course some gimple_assign_set_rhs* etc. calls are still valid even
without creating new stmts, optimizing some statement to equivalent
computation is fine, but computing something different in an old SSA_NAME
is not.
I've also noticed that build_and_add_sum was using different framework from
rewrite_expr_tree, the former was using stmt_dominates_stmt_p (which is IMHO
quite clean interface, but with the added uid stuff in reassoc can be
unnecessarily slow on large basic blocks) and rewrite_expr_tree was using
worse APIs, but using the uids. So, the patch also unifies that, into
a new reassoc_stmt_dominates_stmt_p that has the same semantics as the
tree-ssa-loop-niter.c function, but uses uids internally. rewrite_expr_tree
is changed so that it recurses first, then handles current level (which is
needed if the recursion needs to create new stmt and give back a new
SSA_NAME), which allowed removing the ensure_ops_are_available recursive
stuff. Also, uids are now computed in break_up_subtract_bb (and are per-bb,
starting with 1, we never compare uids from different bbs), which allows
us to get rid of an extra whole IL walk.
For the inter-bb optimization, I had to stop modifying stmts right away
in update_range_test, because we don't want to reuse SSA_NAMEs and if we
modified there, we'd need to modify potentially many dependent SSA_NAMEs
and sometimes many times. So, now it instead just updates oe->op values
and maybe_optimize_range_tests just looks at those values and updates
what is needed.
Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?
For 4.8 a partial backport would be possible, but quite a lot of work,
for 4.7 I'd prefer not to backport given that there gsi_for_stmt isn't O(1).
2013-10-22 Jakub Jelinek
PR tree-optimization/58775
PR tree-optimization/58791
* tree-ssa-reassoc.c (reassoc_stmt_dominates_stmt_p): New function.
(insert_stmt_after): Rewritten, don't move the stmt, but really
insert it.
(get_stmt_uid_with_default): Remove.
(build_and_add_sum): Use insert_stmt_after and
reassoc_stmt_dominates_stmt_p. Fix up uid if bb contains only
labels.
(update_range_test): Set uid on stmts added by
force_gimple_operand_gsi. Don't immediately modify statements
in inter-bb optimization, just update oe->op values.
(optimize_range_tests): Return bool whether any changed have
been made.
(update_ops): New function.
(struct inter_bb_range_test_entry): New type.
(maybe_optimize_range_tests): Perform statement changes here.
(not_dominated_by, appears_later_in_bb, get_def_stmt,
ensure_ops_are_available): Remove.
(find_insert_point): Rewritten.
(rewrite_expr_tree): Remove MOVED argument, add CHANGED argument,
return LHS of the (new resp. old) stmt. Don't call
ensure_ops_are_available, don't reuse SSA_NAMEs, recurse first
instead of last, move new stmt at the right place.
(linearize_expr, repropagate_negates): Don't reuse SSA_NAMEs.
(negate_value): Likewise. Set uids.
(break_up_subtract_bb): Initialize uids.
(reassociate_bb): Adjust rewrite_expr_tree caller.
(do_reassoc): Don't call renumber_gimple_stmt_uids.
* gcc.dg/guality/pr58791-1.c: New test.
* gcc.dg/guality/pr58791-2.c: New test.
* gcc.dg/guality/pr58791-3.c: New test.
* gcc.dg/guality/pr58791-4.c: New test.
* gcc.dg/guality/pr58791-5.c: New test.
* gcc.c-torture/compile/pr58775.c: New test.
* gcc.dg/tree-ssa/reassoc-28.c: Don't scan reassoc1 dump.
--- gcc/tree-ssa-reassoc.c.jj 2013-10-21 09:00:25.0 +0200
+++ gcc/tree-ssa-reassoc.c 2013-10-22 12:04:38.693490273 +0200
@@ -1143,12 +1143,80 @@ zero_one_operation (tree *def, enum tree
while (1);
}
-/* Returns the UID of STMT if it is non-NULL. Otherwise return 1. */
+/* Returns true if statement S1 dominates statement S2. Like
+ stmt_dominates_stmt_p, but uses stmt UIDs to optimize. */
-static inline unsigned
-get_stmt_uid_with_default (gimple stmt)
+static bool
+reassoc_stmt_dominates_stmt_p (gimple s1, gimple s2)
+{
+ basic_block bb1 = gimple_bb (s1), bb2 = gimple_bb (s2);
+
+ if (!bb1 || s1 == s2)
+return true;
+
+ if (!bb2)
+return false;
+
+ if (bb1 == bb2)
+{
+ if (gimple_code (s2) ==
