Re: [PATCH] Fix various reassoc issues (PR tree-optimization/58791, tree-optimization/58775)

[Jeff Law <law at redhat dot com>]

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  <jakub@redhat.com>
>
> 	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.000000000 +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))
> +	{
> +	  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?


> +
> +/* 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 abnormals, 
critical edges, etc.

Maybe there's some constraint I'm not aware of in the callers that makes 
this a non-issue, but at the least these quirks should be documented so 
that someone else doesn't make the mistake of thinking insert_stmt_after 
handles those cases in the obvious way.

I don't really know the reassoc code well, so I'm going to defer to 
others on the rest.

jeff