[RFA] Isolate erroneous paths optimization

On 11/04/13 06:19, Richard Biener wrote:
> On Thu, Oct 31, 2013 at 7:11 AM, Jeff Law <law@redhat.com> wrote:
>>
>> I've incorporated the various suggestions from Marc and Richi, except for
>> Richi's to integrate this into jump threading.
>>
>> I've also made the following changes since the last version:
>>
>>    1. Added more testcases.
>>
>>    2. Use infer_nonnull_range, moving it from tree-vrp.c
>>    into gimple.c.  Minor improvements to infer_nonnull_range
>>    to make it handle more cases we care about and avoid using
>>    unnecessary routines from tree-ssa.c (which can now be removed)
>>
>>    3. Multiple undefined statements in a block are handled in the
>>    logical way.
>>
>> Bootstrapped and regression tested on x86_64-unknown-linux-gnu.  OK for the
>> trunk?
>
> Comments inline
Thanks, always appreciated.

>> index deeb3f2..6db9f56 100644
>> --- a/gcc/common.opt
>> +++ b/gcc/common.opt
>> @@ -2104,6 +2104,12 @@ foptimize-strlen
>>   Common Report Var(flag_optimize_strlen) Optimization
>>   Enable string length optimizations on trees
>>
>> +fisolate-erroneous-paths
>> +Common Report Var(flag_isolate_erroneous_paths) Init(1) Optimization
>
> Drop Init(1) (see below)
Probably a cut-n-paste.  As I've mentioned in another thread, the option 
stuff is a huge black box that I haven't really looked at. I'm pretty 
sure I just took something and hacked it.  Fixed.

>> +
>> +  /* If we did not run to the end of DUPLICATE, then SI points to STMT and
>> +     SI2 points to the duplicate of STMT in DUPLICATE.  */
>> +  if (!gsi_end_p (si2))
>> +    {
>> +      /* SI2 is the iterator in the duplicate block and it now points
>> +        to our victim statement.  */
>> +      gimple_seq seq = NULL;
>> +      gimple stmt
>> +       = gimple_build_call (builtin_decl_explicit (BUILT_IN_TRAP), 0);
>> +      gimple_seq_add_stmt (&seq, stmt);
>> +      gsi_insert_before (&si2, seq, GSI_SAME_STMT);
>> +      /* Now delete all remaining statements in this block.  */
>> +      for (; !gsi_end_p (si2);)
>> +       gsi_remove (&si2, true);
>
> Please do
>
>     stmt = gsi_stmt (si2);
>     unlink_stmt_vdef (stmt);
>     gsi_remove (&si2, true);
>     release_defs (stmt);
>
> to "completely" remove the stmts correctly (you've left SSA names
> unreleased and virtual SSA form broken).
I had to think about this for a while -- we have to be a bit careful 
here because of the limitations of the name manager.  But I think this 
case is OK.  Specifically any SSA_NAMEs we release here won't have any 
dangling references due to unreachable blocks.  Thus we don't run afoul 
of the limitations of the name manager (yes, that problem is still on my 
todo list to fix up).

>> +             next_i = i + 1;
>> +             if (integer_zerop (op))
>> +               {
>
> I always prefer
>
>                     if (!integer_zerop (op))
>                       continue;
>
> to reduce indentation of following code (but that's personal
> preference).
No strong opinions here.  Changed per your request.

>> +                 FOR_EACH_IMM_USE_STMT (use_stmt, iter, lhs)
>> +                   {
>> +                     /* We only care about uses in BB which are
>> assignements
>> +                        with memory operands.
>> +
>> +                        We could see if any uses are as function arguments
>> +                        when the callee has marked the argument as being
>> +                        non-null.  */
>> +                     if (gimple_bb (use_stmt) != bb
>> +                         || (!is_gimple_assign (use_stmt)
>> +                             && !is_gimple_call (use_stmt)
>> +                             && gimple_code (use_stmt) != GIMPLE_RETURN))
>
> any reason for this restrictions on use_stmt?
Historical when this used to open-code the check for NULL pointer 
dereferences.  infer_nonnull_range should do the right thing.  Redundant 
checks bits removed, comment updated.

>> +
>> +      /* Now look at the statements in the block and see if any of
>> +        them explicitly dereference a NULL pointer.  Believe it or
>> +        not, this does happen from time to time.  */
>
> "happens because of constant propagation."
"because of jump threading and constant propagation" I went through the 
trouble of tracking this down a little while ago to ensure this code was 
still useful and didn't update the comment.  FWIW, the included tests 
show instances where we can get explicit dereferences of NULL due to 
jump threading + constant propagation.

>
>> +      for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
>> +       {
>> +         gimple stmt = gsi_stmt (si);
>> +
>> +
>
> extra vertical space
Fixed.

>
>> +         /* By passing null_pointer_node, we can use infer_nonnull_range
>> +            to detect explicit NULL pointer dereferences and other uses
>> +            where a non-NULL value is required.  */
>> +         if (infer_nonnull_range (stmt, null_pointer_node))
>> +           {
>> +             /* First insert a TRAP before this statement.  */
>> +             gimple_seq seq = NULL;
>> +             tree t
>> +               = build_call_expr_loc (0,
>
> Use the location of 'stmt'?
>
>> +                                      builtin_decl_explicit
>> (BUILT_IN_TRAP),
>> +                                      0);
>> +             gimplify_and_add (t, &seq);
>> +             gsi_insert_before (&si, seq, GSI_SAME_STMT);
>
> and please build GIMPLE directly here as well.
Hmm, thought I had already fixed this in both stanzas.

>
>> +             /* Now delete all remaining statements in this block.  */
>> +             for (gimple_stmt_iterator si2 = si; !gsi_end_p (si2);)
>> +               gsi_remove (&si2, true);
>
> See above.
>
> Maybe you can split this common functionality out into a helper.
I'd been considering this already.  Done.

>> +static bool
>> +gate_isolate_erroneous_paths (void)
>> +{
>> +  /* If we do not have a suitable builtin function for the trap statement,
>> +     then do not perform the optimization.  */
>> +  return (flag_isolate_erroneous_paths != 0
>> +         && builtin_decl_explicit (BUILT_IN_TRAP) != NULL);
>
> I don't think this can happen.
Fortran front-end doesn't provide this IIRC.

>>
>> +/* Callback for walk_stmt_load_store_ops.
>> +
>> +   Return TRUE if OP will dereference the tree stored in DATA, FALSE
>> +   otherwise.
>> +
>> +   This routine only makes a superficial check for a dereference.  Thus
>> +   it must only be used if it is safe to return a false negative.  */
>> +static bool
>> +check_loadstore (gimple stmt ATTRIBUTE_UNUSED, tree op, void *data)
>> +{
>> +  if ((TREE_CODE (op) == MEM_REF || TREE_CODE (op) == TARGET_MEM_REF)
>> +      && operand_equal_p (TREE_OPERAND (op, 0), (tree)data, 0))
>
> As you are interested in pointer dereferences and we are in SSA form
> you can use pointer equality:
>
>             && TREE_OPERAND (op, 0) == (tree) data
We're also interested in explicit NULL dereferences, explicit uses of 
NULL for parameters marked as being non-null and explicit NULL return 
values in functions marked as never returning NULL.  So DATA could be 0B 
here.  And those aren't unique.   Thus pointer equality is not 
sufficient.  The included tests show examples that fail if we strictly 
use pointer equality.

>> +         /* If "nonnull" applies to all the arguments, then ARG
>> +            is non-null if it's in the argument list.  */
>> +         if (TREE_VALUE (attrs) == NULL_TREE)
>> +           {
>> +             for (unsigned int i = 0; i < gimple_call_num_args (stmt); i++)
>> +               {
>> +                 if (operand_equal_p (op, gimple_call_arg (stmt, i), 0)
>
> See above (pointer comparison).
Same comment applies.  We want to catch 0B for explicit NULL pointer 
arguments in an arglist.

>
>> +                     && POINTER_TYPE_P (TREE_TYPE (gimple_call_arg (stmt,
>> i))))
>> +                   return true;
>> +               }
>> +             return false;
>> +           }
>> +
>> +         /* Now see if op appears in the nonnull list.  */
>> +         for (tree t = TREE_VALUE (attrs); t; t = TREE_CHAIN (t))
>> +           {
>> +             int idx = TREE_INT_CST_LOW (TREE_VALUE (t)) - 1;
>> +             tree arg = gimple_call_arg (stmt, idx);
>> +             if (operand_equal_p (op, arg, 0))
>
> See above.
Similarly.

>
>> +               return true;
>> +           }
>> +       }
>> +    }
>> +
>> +  /* If this function is marked as returning non-null, then we can
>> +     infer OP is non-null if it is used in the return statement.  */
>> +  if (gimple_code (stmt) == GIMPLE_RETURN
>> +      && gimple_return_retval (stmt)
>> +      && operand_equal_p (gimple_return_retval (stmt), op, 0)
>
> See above.
Similarly.

>> @@ -453,6 +453,7 @@ static const struct default_options
>> default_options_table[] =
>>       { OPT_LEVELS_1_PLUS, OPT_ftree_ch, NULL, 1 },
>>       { OPT_LEVELS_1_PLUS, OPT_fcombine_stack_adjustments, NULL, 1 },
>>       { OPT_LEVELS_1_PLUS, OPT_fcompare_elim, NULL, 1 },
>> +    { OPT_LEVELS_1_PLUS, OPT_fisolate_erroneous_paths, NULL, 1 },
>
> Why enable this at -O1?  We have -fno-strict-overflow, -fno-strict-aliasing
> at -O1 so I'd rather defer this to -O2 and above (including -Os).
No particular reason.  -O2 and above is fine with me.  Changed to 
OPT_LEVELS_2_PLUS.  Removes the need to change 20030711-1.c as that test 
only runs at -O1.

This patch also doesn't need to add gsi_start_nondebug_after_labels as 
Andrew P. added that function recently.

>
> Otherwise the patch looks ok to me.
Attached is the updated patch.  Bootstrapped and regression tested on 
x86_64-unknown-linux-gnu.

jeff
* Makefile.in (OBJS): Add gimple-ssa-isolate-paths.o
	* common.opt (-fisolate-erroneous-paths): Add option and
	documentation.
	* gimple-ssa-isolate-paths.c: New file.
	* gimple.c (check_loadstore): New function.
	(infer_nonnull_range): Moved into gimple.c from tree-vrp.c
	Verify OP is in the argument list and the argument corresponding
	to OP is a pointer type.  Use operand_equal_p rather than
	pointer equality when testing if OP is on the nonnull list.
	Use check_loadstore rather than count_ptr_derefs.  Handle
	GIMPLE_RETURN statements.
	* tree-vrp.c (infer_nonnull_range): Remove.
	* gimple.h (infer_nonnull_range): Declare.
	* opts.c (default_options_table): Add OPT_fisolate_erroneous_paths.
	* passes.def: Add pass_isolate_erroneous_paths.
	* timevar.def (TV_ISOLATE_ERRONEOUS_PATHS): New timevar.
	* tree-pass.h (make_pass_isolate_erroneous_paths): Declare.
	* tree-ssa.c (struct count_ptr_d): Remove.
	(count_ptr_derefs, count_uses_and_derefs): Remove.
	* tree-ssa.h (count_uses_and_derefs): Remove.

	* gcc.dg/pr38984.c: Add -fno-isolate-erroneous-paths.
	* gcc.dg/tree-ssa/isolate-1.c: New test.
	* gcc.dg/tree-ssa/isolate-2.c: New test.
	* gcc.dg/tree-ssa/isolate-3.c: New test.
	* gcc.dg/tree-ssa/isolate-4.c: New test.

[RFA] Isolate erroneous paths optimization

Commit Message

Comments

Patch