This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [RFA][PATCH] Isolate erroneous paths optimization


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,
> 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.
>         (gsi_start_nondebug_after_labels): New function.
>         * 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/20030711-3.c: Update expected output.
>         * 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.
>
>
>
> diff --git a/gcc/Makefile.in b/gcc/Makefile.in
> index 29609fd..7e9a702 100644
> --- a/gcc/Makefile.in
> +++ b/gcc/Makefile.in
> @@ -1233,6 +1233,7 @@ OBJS = \
>         gimple-fold.o \
>         gimple-low.o \
>         gimple-pretty-print.o \
> +       gimple-ssa-isolate-paths.o \
>         gimple-ssa-strength-reduction.o \
>         gimple-streamer-in.o \
>         gimple-streamer-out.o \
> diff --git a/gcc/common.opt b/gcc/common.opt
> 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)

> +Detect paths which trigger erroneous or undefined behaviour.  Isolate those
> +paths from the main control flow and turn the statement with erroneous or
> +undefined behaviour into a trap.
> +
>  ftree-loop-distribution
>  Common Report Var(flag_tree_loop_distribution) Optimization
>  Enable loop distribution on trees
> diff --git a/gcc/gimple-ssa-isolate-paths.c b/gcc/gimple-ssa-isolate-paths.c
> new file mode 100644
> index 0000000..aa526cc
> --- /dev/null
> +++ b/gcc/gimple-ssa-isolate-paths.c
> @@ -0,0 +1,332 @@
> +/* Detect paths through the CFG which can never be executed in a conforming
> +   program and isolate them.
> +
> +   Copyright (C) 2013
> +   Free Software Foundation, Inc.
> +
> +This file is part of GCC.
> +
> +GCC is free software; you can redistribute it and/or modify
> +it under the terms of the GNU General Public License as published by
> +the Free Software Foundation; either version 3, or (at your option)
> +any later version.
> +
> +GCC is distributed in the hope that it will be useful,
> +but WITHOUT ANY WARRANTY; without even the implied warranty of
> +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
> +GNU General Public License for more details.
> +
> +You should have received a copy of the GNU General Public License
> +along with GCC; see the file COPYING3.  If not see
> +<http://www.gnu.org/licenses/>.  */
> +
> +#include "config.h"
> +#include "system.h"
> +#include "coretypes.h"
> +#include "tree.h"
> +#include "flags.h"
> +#include "basic-block.h"
> +#include "gimple.h"
> +#include "tree-ssa.h"
> +#include "gimple-ssa.h"
> +#include "tree-ssa-operands.h"
> +#include "tree-phinodes.h"
> +#include "ssa-iterators.h"
> +#include "cfgloop.h"
> +#include "tree-pass.h"
> +
> +
> +static bool cfg_altered;
> +
> +/* BB when reached via incoming edge E will exhibit undefined behaviour
> +   at STMT.  Isolate and optimize the path which exhibits undefined
> +   behaviour.
> +
> +   Isolation is simple.  Duplicate BB and redirect E to BB'.
> +
> +   Optimization is simple as well.  Replace STMT in BB' with an
> +   unconditional trap and remove all outgoing edges from BB'.
> +
> +   DUPLICATE is a pre-existing duplicate, use it as BB' if it exists.
> +
> +   Return BB'.  */
> +
> +basic_block
> +isolate_path (basic_block bb, basic_block duplicate, edge e, gimple stmt)
> +{
> +  gimple_stmt_iterator si, si2;
> +  edge_iterator ei;
> +  edge e2;
> +
> +
> +  /* First duplicate BB if we have not done so already and remove all
> +     the duplicate's outgoing edges as duplicate is going to
> unconditionally
> +     trap.  Removing the outgoing edges is both an optimization and ensures
> +     we don't need to do any PHI node updates.  */
> +  if (!duplicate)
> +    {
> +      duplicate = duplicate_block (bb, NULL, NULL);
> +      for (ei = ei_start (duplicate->succs); (e2 = ei_safe_edge (ei)); )
> +       remove_edge (e2);
> +    }
> +
> +  /* Complete the isolation step by redirecting E to reach DUPLICATE.  */
> +  e2 = redirect_edge_and_branch (e, duplicate);
> +  if (e2)
> +    flush_pending_stmts (e2);
> +
> +
> +  /* There may be more than one statement in DUPLICATE which exhibits
> +     undefined behaviour.  Ultimately we want the first such statement in
> +     DUPLCIATE so that we're able to delete as much code as possible.
> +
> +     So each time we discover undefined behaviour in DUPLICATE, search for
> +     the statement which triggers undefined behaviour.  If found, then
> +     transform the statement into a trap and delete everything after the
> +     statement.  If not found, then this particular instance was subsumed
> by
> +     an earlier instance of undefined behaviour and there's nothing to do.
> +
> +     This is made more complicated by the fact that we have STMT, which is
> in
> +     BB rather than in DUPLICATE.  So we set up two iterators, one for each
> +     block and walk forward looking for STMT in BB, advancing each iterator
> at
> +     each step.
> +
> +     When we find STMT the second iterator should point to STMT's
> equivalent in
> +     duplicate.  If DUPLICATE ends before STMT is found in BB, then there's
> +     nothing to do.
> +
> +     Ignore labels and debug statements.  */
> +  si = gsi_start_nondebug_after_labels (bb);
> +  si2 = gsi_start_nondebug_after_labels (duplicate);
> +  while (!gsi_end_p (si) && !gsi_end_p (si2) && gsi_stmt (si) != stmt)
> +    {
> +      gsi_next_nondebug (&si);
> +      gsi_next_nondebug (&si2);
> +    }
> +
> +  /* This would be an indicator that we never found STMT in BB, which
> should
> +     never happen.  */
> +  gcc_assert (!gsi_end_p (si));
> +
> +  /* 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).

> +    }
> +
> +  return duplicate;
> +}
> +
> +/* Search the function for statements which, if executed, would cause
> +   the program to fault such as a dereference of a NULL pointer.
> +
> +   Such a program can't be valid if such a statement was to execute
> +   according to ISO standards.
> +
> +   We detect explicit NULL pointer dereferences as well as those implied
> +   by a PHI argument having a NULL value which unconditionally flows into
> +   a dereference in the same block as the PHI.
> +
> +   In the former case we replace the offending statement with an
> +   unconditional trap and eliminate the outgoing edges from the statement's
> +   basic block.  This may expose secondary optimization opportunities.
> +
> +   In the latter case, we isolate the path(s) with the NULL PHI
> +   feeding the dereference.  We can then replace the offending statement
> +   and eliminate the outgoing edges in the duplicate.  Again, this may
> +   expose secondary optimization opportunities.
> +
> +   A warning for both cases may be advisable as well.
> +
> +   Other statically detectable violations of the ISO standard could be
> +   handled in a similar way, such as out-of-bounds array indexing.  */
> +
> +static unsigned int
> +gimple_ssa_isolate_erroneous_paths (void)
> +{
> +  basic_block bb;
> +
> +  initialize_original_copy_tables ();
> +
> +  /* Search all the blocks for edges which, if traversed, will
> +     result in undefined behaviour.  */
> +  cfg_altered = false;
> +  FOR_EACH_BB (bb)
> +    {
> +      gimple_stmt_iterator si;
> +
> +      /* First look for a PHI which sets a pointer to NULL and which
> +        is then dereferenced within BB.  This is somewhat overly
> +        conservative, but probably catches most of the interesting
> +        cases.   */
> +      for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
> +       {
> +         gimple phi = gsi_stmt (si);
> +         tree lhs = gimple_phi_result (phi);
> +
> +         /* If the result is not a pointer, then there is no need to
> +            examine the arguments.  */
> +         if (!POINTER_TYPE_P (TREE_TYPE (lhs)))
> +           continue;
> +
> +         /* PHI produces a pointer result.  See if any of the PHI's
> +            arguments are NULL.
> +
> +            When we remove an edge, we want to reprocess the current
> +            index, hence the ugly way we update I for each iteration.  */
> +         basic_block duplicate = NULL;
> +         for (unsigned i = 0, next_i = 0;
> +              i < gimple_phi_num_args (phi);
> +              i = next_i)
> +           {
> +             tree op = gimple_phi_arg_def (phi, i);
> +
> +             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).

> +                 edge e = gimple_phi_arg_edge (phi, i);
> +                 imm_use_iterator iter;
> +                 gimple use_stmt;
> +
> +                 /* We've got a NULL PHI argument.  Now see if the
> +                    PHI's result is dereferenced within BB.  */
> +                 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?

> +                       continue;
> +
> +                     if (infer_nonnull_range (use_stmt, lhs))
> +                       {
> +                         duplicate = isolate_path (bb, duplicate,
> +                                                   e, use_stmt);
> +
> +                         /* When we remove an incoming edge, we need to
> +                            reprocess the Ith element.  */
> +                         next_i = i;
> +                         cfg_altered = true;
> +                       }
> +                   }
> +               }
> +           }
> +       }
> +
> +      /* 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."

> +      for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
> +       {
> +         gimple stmt = gsi_stmt (si);
> +
> +

extra vertical space

> +         /* 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.

> +             /* 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.

> +             /* And finally, remove all outgoing edges from BB.  */
> +             edge e;
> +             for (edge_iterator ei = ei_start (bb->succs);
> +                  (e = ei_safe_edge (ei)); )
> +               remove_edge (e);
> +
> +             /* Ignore any more operands on this statement and
> +                continue the statement iterator (which should
> +                terminate its loop immediately.  */
> +             cfg_altered = true;
> +             break;
> +           }
> +       }
> +    }
> +  free_original_copy_tables ();
> +
> +  /* We scramble the CFG and loop structures a bit, clean up
> +     appropriately.  We really should incrementally update the
> +     loop structures, in theory it shouldn't be that hard.  */
> +  if (cfg_altered)
> +    {
> +      free_dominance_info (CDI_DOMINATORS);
> +      free_dominance_info (CDI_POST_DOMINATORS);
> +      loops_state_set (LOOPS_NEED_FIXUP);
> +      return TODO_cleanup_cfg | TODO_update_ssa;
> +    }
> +  return 0;
> +}
> +
> +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.

> +}
> +
> +namespace {
> +const pass_data pass_data_isolate_erroneous_paths =
> +{
> +  GIMPLE_PASS, /* type */
> +  "isolate-paths", /* name */
> +  OPTGROUP_NONE, /* optinfo_flags */
> +  true, /* has_gate */
> +  true, /* has_execute */
> +  TV_ISOLATE_ERRONEOUS_PATHS, /* tv_id */
> +  ( PROP_cfg | PROP_ssa ), /* properties_required */
> +  0, /* properties_provided */
> +  0, /* properties_destroyed */
> +  0, /* todo_flags_start */
> +  TODO_verify_ssa, /* todo_flags_finish */
> +};
> +
> +class pass_isolate_erroneous_paths : public gimple_opt_pass
> +{
> +public:
> +  pass_isolate_erroneous_paths (gcc::context *ctxt)
> +    : gimple_opt_pass (pass_data_isolate_erroneous_paths, ctxt)
> +  {}
> +
> +  /* opt_pass methods: */
> +  opt_pass * clone () { return new pass_isolate_erroneous_paths (m_ctxt); }
> +  bool gate () { return gate_isolate_erroneous_paths (); }
> +  unsigned int execute () { return gimple_ssa_isolate_erroneous_paths (); }
> +
> +}; // class pass_uncprop
> +}
> +
> +gimple_opt_pass *
> +make_pass_isolate_erroneous_paths (gcc::context *ctxt)
> +{
> +  return new pass_isolate_erroneous_paths (ctxt);
> +}
> diff --git a/gcc/gimple.c b/gcc/gimple.c
> index 3ddceb9..fbb1393 100644
> --- a/gcc/gimple.c
> +++ b/gcc/gimple.c
> @@ -4083,6 +4083,87 @@ nonfreeing_call_p (gimple call)
>    return false;
>  }
>
> +/* 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

note that this should also work for memory inputs/outputs of ASMs
and for dereferences in calls (happens for aggregate arguments
and return values).  So in theory it should work for all kind of stmts
(or walk_stmt_load_store_addr_ops would have a bug).

> +    return true;
> +  return false;
> +}
> +
> +/* If OP can be inferred to be non-zero after STMT executes, return true.
> */
> +
> +bool
> +infer_nonnull_range (gimple stmt, tree op)
> +{
> +  /* We can only assume that a pointer dereference will yield
> +     non-NULL if -fdelete-null-pointer-checks is enabled.  */
> +  if (!flag_delete_null_pointer_checks
> +      || !POINTER_TYPE_P (TREE_TYPE (op))
> +      || gimple_code (stmt) == GIMPLE_ASM)
> +    return false;
> +
> +  if (walk_stmt_load_store_ops (stmt, (void *)op,
> +                               check_loadstore, check_loadstore))
> +    return true;
> +
> +  if (is_gimple_call (stmt) && !gimple_call_internal_p (stmt))
> +    {
> +      tree fntype = gimple_call_fntype (stmt);
> +      tree attrs = TYPE_ATTRIBUTES (fntype);
> +      for (; attrs; attrs = TREE_CHAIN (attrs))
> +       {
> +         attrs = lookup_attribute ("nonnull", attrs);
> +
> +         /* If "nonnull" wasn't specified, we know nothing about
> +            the argument.  */
> +         if (attrs == NULL_TREE)
> +           return false;
> +
> +         /* 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).

> +                     && 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.

> +               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.

> +      && lookup_attribute ("returns_nonnull",
> +                          TYPE_ATTRIBUTES (TREE_TYPE
> (current_function_decl))))
> +    return true;
> +
> +  return false;
> +}
> +
>  /* Create a new VAR_DECL and copy information from VAR to it.  */
>
>  tree
> diff --git a/gcc/gimple.h b/gcc/gimple.h
> index e34411d..4d00493 100644
> --- a/gcc/gimple.h
> +++ b/gcc/gimple.h
> @@ -1088,6 +1088,7 @@ extern void dump_decl_set (FILE *, bitmap);
>  extern bool gimple_can_coalesce_p (tree, tree);
>  extern bool nonfreeing_call_p (gimple);
>  extern tree copy_var_decl (tree, tree, tree);
> +extern bool infer_nonnull_range (gimple, tree);
>
>  /* In trans-mem.c.  */
>  extern void diagnose_tm_safe_errors (tree);
> @@ -5533,6 +5534,20 @@ gsi_start_nondebug_bb (basic_block bb)
>    return i;
>  }
>
> +/* Return a new iterator pointing to the first non-debug, non-label
> statement
> +   in basic block BB.  */
> +
> +static inline gimple_stmt_iterator
> +gsi_start_nondebug_after_labels (basic_block bb)
> +{
> +  gimple_stmt_iterator gsi = gsi_start_nondebug_bb (bb);
> +
> +  while (!gsi_end_p (gsi) && gimple_code (gsi_stmt (gsi)) == GIMPLE_LABEL)
> +    gsi_next_nondebug (&gsi);
> +
> +  return gsi;
> +}
> +
>  /* Return a new iterator pointing to the last non-debug statement in
>     basic block BB.  */
>
> diff --git a/gcc/opts.c b/gcc/opts.c
> index 728d36d..e1e09c7 100644
> --- a/gcc/opts.c
> +++ b/gcc/opts.c
> @@ -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).

Otherwise the patch looks ok to me.

Thanks,
Richard.

>      { OPT_LEVELS_1_PLUS, OPT_ftree_slsr, NULL, 1 },
>
>      /* -O2 optimizations.  */
> diff --git a/gcc/passes.def b/gcc/passes.def
> index 404b790..1607b59 100644
> --- a/gcc/passes.def
> +++ b/gcc/passes.def
> @@ -166,9 +166,16 @@ along with GCC; see the file COPYING3.  If not see
>          is removed, and this place fits nicely.  Remember this when
>          trying to move or duplicate pass_dominator somewhere earlier.  */
>        NEXT_PASS (pass_dominator);
> +      /* At this point the majority of const/copy propagations
> +        are exposed.  Go ahead and identify paths that should never
> +        be executed in a conforming program and isolate those paths.
> +
> +        This will expose more degenerate PHIs in the main path and
> +        expose more PRE/DOM optimization opportunities.  */
> +      NEXT_PASS (pass_isolate_erroneous_paths);
>        /* The only const/copy propagation opportunities left after
> -        DOM should be due to degenerate PHI nodes.  So rather than
> -        run the full propagators, run a specialized pass which
> +        DOM and erroneous path isolation should be due to degenerate PHI
> nodes.
> +        So rather than run the full propagators, run a specialized pass
> which
>          only examines PHIs to discover const/copy propagation
>          opportunities.  */
>        NEXT_PASS (pass_phi_only_cprop);
> diff --git a/gcc/testsuite/gcc.dg/pr38984.c b/gcc/testsuite/gcc.dg/pr38984.c
> index 11f1e7f..0c03180 100644
> --- a/gcc/testsuite/gcc.dg/pr38984.c
> +++ b/gcc/testsuite/gcc.dg/pr38984.c
> @@ -1,5 +1,5 @@
>  /* { dg-do compile } */
> -/* { dg-options "-O2 -fno-delete-null-pointer-checks -fdump-tree-optimized"
> }
> +/* { dg-options "-O2 -fno-delete-null-pointer-checks -fdump-tree-optimized
> -fno-isolate-erroneous-paths" }
>   * */
>
>  int f(int *p)
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/20030711-3.c
> b/gcc/testsuite/gcc.dg/tree-ssa/20030711-3.c
> index ec04e17..bcd5681 100644
> --- a/gcc/testsuite/gcc.dg/tree-ssa/20030711-3.c
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/20030711-3.c
> @@ -52,10 +52,10 @@ get_alias_set (t)
>  /* There should be one load of decl.rtl.  */
>  /* { dg-final { scan-tree-dump-times "decl\\.rtl" 1 "dom2"} } */
>
> -/* There should be two loads of rtmem.  */
> -/* { dg-final { scan-tree-dump-times "rtmem" 2 "dom2"} } */
> +/* There should be one load of rtmem.  */
> +/* { dg-final { scan-tree-dump-times "rtmem" 1 "dom2"} } */
>
> -/* There should be one load of alias.  */
> -/* { dg-final { scan-tree-dump-times "->alias" 1 "dom2"} } */
> +/* There should be no load of alias.  */
> +/* { dg-final { scan-tree-dump-not "->alias" "dom2"} } */
>
>  /* { dg-final { cleanup-tree-dump "dom2" } } */
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/isolate-1.c
> b/gcc/testsuite/gcc.dg/tree-ssa/isolate-1.c
> new file mode 100644
> index 0000000..6b779b4
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/isolate-1.c
> @@ -0,0 +1,58 @@
> +
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-isolate-paths" } */
> +
> +
> +struct demangle_component
> +{
> +
> +  int type;
> +  int zzz;
> +
> +};
> +
> +
> +struct d_info
> +{
> +  struct demangle_component *comps;
> +  int next_comp;
> +  int num_comps;
> +};
> +
> +
> +static struct demangle_component *
> +d_make_empty (struct d_info *di)
> +{
> +  struct demangle_component *p;
> +
> +  if (di->next_comp >= di->num_comps)
> +    return ((void *)0);
> +  p = &di->comps[di->next_comp];
> +  return p;
> +}
> +
> +
> +
> +struct demangle_component *
> +d_type (struct d_info *di)
> +{
> +   struct demangle_component *ret;
> +   ret = d_make_empty (di);
> +   ret->type = 42;
> +   ret->zzz = -1;
> +   return ret;
> +}
> +
> +/* We're testing two aspects of isolation here.  First that isolation
> +   occurs, second that if we have two null dereferences in a block that
> +   that we delete everything from the first dereferece to the end of the
> +   block, regardless of which comes first in the immediate use iterator.
> */
> +/* { dg-final { scan-tree-dump-times "__builtin_trap" 1 "isolate-paths"} }
> */
> +/* { dg-final { scan-tree-dump-times "->type" 1 "isolate-paths"} } */
> +/* { dg-final { scan-tree-dump-times "->zzz" 1 "isolate-paths"} } */
> +/* { dg-final { cleanup-tree-dump "isolate-paths" } } */
> +
> +
> +
> +
> +
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/isolate-2.c
> b/gcc/testsuite/gcc.dg/tree-ssa/isolate-2.c
> new file mode 100644
> index 0000000..290b44c
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/isolate-2.c
> @@ -0,0 +1,43 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-isolate-paths -fdump-tree-phicprop1" } */
> +
> +
> +int z;
> +int y;
> +
> +int * foo(int a) __attribute__((returns_nonnull));
> +int * bar(void) __attribute__((returns_nonnull));
> +
> +int *
> +foo(int a)
> +
> +{
> +  switch (a)
> +    {
> +      case 0:
> +        return &z;
> +      default:
> +        return (int *)0;
> +    }
> +}
> +
> +
> +int *
> +bar (void)
> +{
> +  return 0;
> +}
> +
> +/* We testing that the path isolation code can take advantage of the
> +   returns non-null attribute to isolate a path where NULL flows into
> +   a return statement.  We test this twice, once where the NULL flows
> +   from a PHI, the second with an explicit return 0 in the IL.
> +
> +   We also verify that after isolation phi-cprop simplifies the
> +   return statement so that it returns &z directly.
> +/* { dg-final { scan-tree-dump-times "__builtin_trap" 2 "isolate-paths"} }
> */
> +/* { dg-final { scan-tree-dump-times "return &z;" 1 "phicprop1"} } */
> +/* { dg-final { cleanup-tree-dump "isolate-paths" } } */
> +/* { dg-final { cleanup-tree-dump "phicprop1" } } */
> +
> +
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/isolate-3.c
> b/gcc/testsuite/gcc.dg/tree-ssa/isolate-3.c
> new file mode 100644
> index 0000000..7dddd80
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/isolate-3.c
> @@ -0,0 +1,65 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-isolate-paths" } */
> +
> +
> +typedef long unsigned int size_t;
> +extern void *memset (void *__s, int __c, size_t __n)
> +  __attribute__ ((__nothrow__, __leaf__)) __attribute__ ((__nonnull__
> (1)));
> +struct rtx_def;
> +typedef struct rtx_def *rtx;
> +typedef struct VEC_rtx_base
> +
> +{
> +  unsigned num;
> +  unsigned alloc;
> +  rtx vec[1];
> +} VEC_rtx_base;
> +static __inline__ rtx *
> +VEC_rtx_base_address (VEC_rtx_base * vec_)
> +{
> +  return vec_ ? vec_->vec : 0;
> +}
> +typedef struct VEC_rtx_gc
> +{
> +  VEC_rtx_base base;
> +} VEC_rtx_gc;
> +
> +static __inline__ void
> +VEC_rtx_gc_safe_grow (VEC_rtx_gc ** vec_, int size_, const char *file_,
> +                      unsigned line_, const char *function_)
> +{
> +  ((*vec_) ? &(*vec_)->base : 0)->num = size_;
> +}
> +
> +static __inline__ void
> +VEC_rtx_gc_safe_grow_cleared (VEC_rtx_gc ** vec_, int size_,
> +                              const char *file_, unsigned line_,
> +                              const char *function_, int oldsize)
> +{
> +  VEC_rtx_gc_safe_grow (vec_, size_, file_, line_, function_);
> +  memset (&(VEC_rtx_base_address ((*vec_) ? &(*vec_)->base : 0))[oldsize],
> 0,
> +          sizeof (rtx) * (size_ - oldsize));
> +}
> +
> +static VEC_rtx_gc *reg_base_value;
> +void
> +init_alias_analysis (void)
> +{
> +  unsigned int maxreg = max_reg_num ();
> +  (VEC_rtx_gc_safe_grow_cleared
> +   (&(reg_base_value), maxreg, "../../../gcc-4.6.0/gcc/alias.c", 2755,
> +    __FUNCTION__, arf ()));
> +}
> +
> +
> +
> +/* This is an example of how a NULL pointer dereference can show up
> +   without a PHI.  Note VEC_rtx_gcc_safe_grow.  If an earlier pass
> +   (such as VRP) isolates the NULL path for some reason or another
> +   we end up with an explicit NULL dereference in the IL.  Yes, it
> +   started with a PHI, but by the time the path isolation code runs
> +   its explicit in the IL.  */
> +/* { dg-final { scan-tree-dump-times "__builtin_trap" 1 "isolate-paths"} }
> */
> +/* { dg-final { cleanup-tree-dump "isolate-paths" } } */
> +
> +
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/isolate-4.c
> b/gcc/testsuite/gcc.dg/tree-ssa/isolate-4.c
> new file mode 100644
> index 0000000..6937d25
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/isolate-4.c
> @@ -0,0 +1,32 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-isolate-paths -fdump-tree-phicprop1" } */
> +
> +
> +extern void foo(void *) __attribute__ ((__nonnull__ (1)));
> +
> +int z;
> +
> +void
> +com (int a)
> +{
> +    foo (a == 42 ? &z  : (void *) 0);
> +}
> +
> +void
> +bar (void)
> +{
> +  foo ((void *)0);
> +}
> +
> +/* We testing that the path isolation code can take advantage of the
> +   returns non-null attribute to isolate a path where NULL flows into
> +   a return statement.
> +
> +   We also verify that after isolation phi-cprop simplifies the
> +   return statement so that it returns &z directly.
> +/* { dg-final { scan-tree-dump-times "__builtin_trap" 2 "isolate-paths"} }
> */
> +/* { dg-final { scan-tree-dump-times "foo .&z.;" 1 "phicprop1"} } */
> +/* { dg-final { cleanup-tree-dump "isolate-paths" } } */
> +/* { dg-final { cleanup-tree-dump "phicprop1" } } */
> +
> +
> diff --git a/gcc/timevar.def b/gcc/timevar.def
> index 5a880a8..4c11511 100644
> --- a/gcc/timevar.def
> +++ b/gcc/timevar.def
> @@ -144,6 +144,7 @@ DEFTIMEVAR (TV_TREE_SSA_INCREMENTAL  , "tree SSA
> incremental")
>  DEFTIMEVAR (TV_TREE_OPS                     , "tree operand scan")
>  DEFTIMEVAR (TV_TREE_SSA_DOMINATOR_OPTS   , "dominator optimization")
>  DEFTIMEVAR (TV_TREE_SRA              , "tree SRA")
> +DEFTIMEVAR (TV_ISOLATE_ERRONEOUS_PATHS    , "isolate eroneous paths")
>  DEFTIMEVAR (TV_TREE_CCP                     , "tree CCP")
>  DEFTIMEVAR (TV_TREE_PHI_CPROP       , "tree PHI const/copy prop")
>  DEFTIMEVAR (TV_TREE_SPLIT_EDGES      , "tree split crit edges")
> diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h
> index 5237438..3f251b6 100644
> --- a/gcc/tree-pass.h
> +++ b/gcc/tree-pass.h
> @@ -425,6 +425,7 @@ extern gimple_opt_pass *make_pass_sink_code
> (gcc::context *ctxt);
>  extern gimple_opt_pass *make_pass_fre (gcc::context *ctxt);
>  extern gimple_opt_pass *make_pass_check_data_deps (gcc::context *ctxt);
>  extern gimple_opt_pass *make_pass_copy_prop (gcc::context *ctxt);
> +extern gimple_opt_pass *make_pass_isolate_erroneous_paths (gcc::context
> *ctxt);
>  extern gimple_opt_pass *make_pass_vrp (gcc::context *ctxt);
>  extern gimple_opt_pass *make_pass_uncprop (gcc::context *ctxt);
>  extern gimple_opt_pass *make_pass_return_slot (gcc::context *ctxt);
> diff --git a/gcc/tree-ssa.c b/gcc/tree-ssa.c
> index 0b743d1..ba8045d 100644
> --- a/gcc/tree-ssa.c
> +++ b/gcc/tree-ssa.c
> @@ -236,100 +236,6 @@ flush_pending_stmts (edge e)
>    redirect_edge_var_map_clear (e);
>  }
>
> -
> -/* Data structure used to count the number of dereferences to PTR
> -   inside an expression.  */
> -struct count_ptr_d
> -{
> -  tree ptr;
> -  unsigned num_stores;
> -  unsigned num_loads;
> -};
> -
> -
> -/* Helper for count_uses_and_derefs.  Called by walk_tree to look for
> -   (ALIGN/MISALIGNED_)INDIRECT_REF nodes for the pointer passed in DATA.
> */
> -
> -static tree
> -count_ptr_derefs (tree *tp, int *walk_subtrees, void *data)
> -{
> -  struct walk_stmt_info *wi_p = (struct walk_stmt_info *) data;
> -  struct count_ptr_d *count_p = (struct count_ptr_d *) wi_p->info;
> -
> -  /* Do not walk inside ADDR_EXPR nodes.  In the expression &ptr->fld,
> -     pointer 'ptr' is *not* dereferenced, it is simply used to compute
> -     the address of 'fld' as 'ptr + offsetof(fld)'.  */
> -  if (TREE_CODE (*tp) == ADDR_EXPR)
> -    {
> -      *walk_subtrees = 0;
> -      return NULL_TREE;
> -    }
> -
> -  if (TREE_CODE (*tp) == MEM_REF && TREE_OPERAND (*tp, 0) == count_p->ptr)
> -    {
> -      if (wi_p->is_lhs)
> -       count_p->num_stores++;
> -      else
> -       count_p->num_loads++;
> -    }
> -
> -  return NULL_TREE;
> -}
> -
> -
> -/* Count the number of direct and indirect uses for pointer PTR in
> -   statement STMT.  The number of direct uses is stored in
> -   *NUM_USES_P.  Indirect references are counted separately depending
> -   on whether they are store or load operations.  The counts are
> -   stored in *NUM_STORES_P and *NUM_LOADS_P.  */
> -
> -void
> -count_uses_and_derefs (tree ptr, gimple stmt, unsigned *num_uses_p,
> -                      unsigned *num_loads_p, unsigned *num_stores_p)
> -{
> -  ssa_op_iter i;
> -  tree use;
> -
> -  *num_uses_p = 0;
> -  *num_loads_p = 0;
> -  *num_stores_p = 0;
> -
> -  /* Find out the total number of uses of PTR in STMT.  */
> -  FOR_EACH_SSA_TREE_OPERAND (use, stmt, i, SSA_OP_USE)
> -    if (use == ptr)
> -      (*num_uses_p)++;
> -
> -  /* Now count the number of indirect references to PTR.  This is
> -     truly awful, but we don't have much choice.  There are no parent
> -     pointers inside INDIRECT_REFs, so an expression like
> -     '*x_1 = foo (x_1, *x_1)' needs to be traversed piece by piece to
> -     find all the indirect and direct uses of x_1 inside.  The only
> -     shortcut we can take is the fact that GIMPLE only allows
> -     INDIRECT_REFs inside the expressions below.  */
> -  if (is_gimple_assign (stmt)
> -      || gimple_code (stmt) == GIMPLE_RETURN
> -      || gimple_code (stmt) == GIMPLE_ASM
> -      || is_gimple_call (stmt))
> -    {
> -      struct walk_stmt_info wi;
> -      struct count_ptr_d count;
> -
> -      count.ptr = ptr;
> -      count.num_stores = 0;
> -      count.num_loads = 0;
> -
> -      memset (&wi, 0, sizeof (wi));
> -      wi.info = &count;
> -      walk_gimple_op (stmt, count_ptr_derefs, &wi);
> -
> -      *num_stores_p = count.num_stores;
> -      *num_loads_p = count.num_loads;
> -    }
> -
> -  gcc_assert (*num_uses_p >= *num_loads_p + *num_stores_p);
> -}
> -
> -
>  /* Replace the LHS of STMT, an assignment, either a GIMPLE_ASSIGN or a
>     GIMPLE_CALL, with NLHS, in preparation for modifying the RHS to an
>     expression with a different value.
> diff --git a/gcc/tree-ssa.h b/gcc/tree-ssa.h
> index ab1c920..89ea5c6 100644
> --- a/gcc/tree-ssa.h
> +++ b/gcc/tree-ssa.h
> @@ -39,8 +39,6 @@ extern edge_var_map_vector *redirect_edge_var_map_vector
> (edge);
>  extern void redirect_edge_var_map_destroy (void);
>  extern edge ssa_redirect_edge (edge, basic_block);
>  extern void flush_pending_stmts (edge);
> -extern void count_uses_and_derefs (tree, gimple, unsigned *, unsigned *,
> -                                  unsigned *);
>  extern void gimple_replace_ssa_lhs (gimple, tree);
>  extern tree target_for_debug_bind (tree);
>  extern void insert_debug_temp_for_var_def (gimple_stmt_iterator *, tree);
> diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
> index d3a07f3..a98ce25 100644
> --- a/gcc/tree-vrp.c
> +++ b/gcc/tree-vrp.c
> @@ -4476,57 +4476,6 @@ fp_predicate (gimple stmt)
>    return FLOAT_TYPE_P (TREE_TYPE (gimple_cond_lhs (stmt)));
>  }
>
> -
> -/* If OP can be inferred to be non-zero after STMT executes, return true.
> */
> -
> -static bool
> -infer_nonnull_range (gimple stmt, tree op)
> -{
> -  /* We can only assume that a pointer dereference will yield
> -     non-NULL if -fdelete-null-pointer-checks is enabled.  */
> -  if (!flag_delete_null_pointer_checks
> -      || !POINTER_TYPE_P (TREE_TYPE (op))
> -      || gimple_code (stmt) == GIMPLE_ASM)
> -    return false;
> -
> -  unsigned num_uses, num_loads, num_stores;
> -
> -  count_uses_and_derefs (op, stmt, &num_uses, &num_loads, &num_stores);
> -  if (num_loads + num_stores > 0)
> -    return true;
> -
> -  if (is_gimple_call (stmt) && !gimple_call_internal_p (stmt))
> -    {
> -      tree fntype = gimple_call_fntype (stmt);
> -      tree attrs = TYPE_ATTRIBUTES (fntype);
> -      for (; attrs; attrs = TREE_CHAIN (attrs))
> -       {
> -         attrs = lookup_attribute ("nonnull", attrs);
> -
> -         /* If "nonnull" wasn't specified, we know nothing about
> -            the argument.  */
> -         if (attrs == NULL_TREE)
> -           return false;
> -
> -         /* If "nonnull" applies to all the arguments, then ARG
> -            is non-null.  */
> -         if (TREE_VALUE (attrs) == NULL_TREE)
> -           return true;
> -
> -         /* 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 (op == arg)
> -               return true;
> -           }
> -       }
> -    }
> -
> -  return false;
> -}
> -
>  /* If the range of values taken by OP can be inferred after STMT executes,
>     return the comparison code (COMP_CODE_P) and value (VAL_P) that
>     describes the inferred range.  Return true if a range could be
>


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]