* [RFA][PATCH] Isolate erroneous paths optimization
@ 2013-10-31 8:34 Jeff Law
2013-11-04 13:20 ` Richard Biener
0 siblings, 1 reply; 41+ messages in thread
From: Jeff Law @ 2013-10-31 8:34 UTC (permalink / raw)
To: gcc-patches
[-- Attachment #1: Type: text/plain, Size: 644 bytes --]
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?
Thanks,
Jeff
[-- Attachment #2: patch --]
[-- Type: text/plain, Size: 33574 bytes --]
* 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
+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);
+ }
+
+ 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))
+ {
+ 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))
+ 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. */
+ for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
+ {
+ gimple stmt = gsi_stmt (si);
+
+
+ /* 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,
+ builtin_decl_explicit (BUILT_IN_TRAP),
+ 0);
+ gimplify_and_add (t, &seq);
+ gsi_insert_before (&si, seq, GSI_SAME_STMT);
+
+ /* Now delete all remaining statements in this block. */
+ for (gimple_stmt_iterator si2 = si; !gsi_end_p (si2);)
+ gsi_remove (&si2, true);
+
+ /* 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);
+}
+
+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))
+ 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)
+ && 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))
+ 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)
+ && 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 },
{ 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
^ permalink raw reply [flat|nested] 41+ messages in thread
* Re: [RFA][PATCH] Isolate erroneous paths optimization
2013-10-31 8:34 [RFA][PATCH] Isolate erroneous paths optimization Jeff Law
@ 2013-11-04 13:20 ` Richard Biener
2013-11-05 2:03 ` Jeff Law
0 siblings, 1 reply; 41+ messages in thread
From: Richard Biener @ 2013-11-04 13:20 UTC (permalink / raw)
To: Jeff Law; +Cc: gcc-patches
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
>
^ permalink raw reply [flat|nested] 41+ messages in thread
* Re: [RFA][PATCH] Isolate erroneous paths optimization
2013-11-04 13:20 ` Richard Biener
@ 2013-11-05 2:03 ` Jeff Law
2013-11-05 11:59 ` Richard Biener
` (2 more replies)
0 siblings, 3 replies; 41+ messages in thread
From: Jeff Law @ 2013-11-05 2:03 UTC (permalink / raw)
To: Richard Biener; +Cc: gcc-patches
[-- Attachment #1: Type: text/plain, Size: 9704 bytes --]
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
[-- Attachment #2: patch --]
[-- Type: text/plain, Size: 31842 bytes --]
* 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.
diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index cc88fb8..9dd5dbe 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -1234,6 +1234,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 3a40db2..bda4790 100644
--- a/gcc/common.opt
+++ b/gcc/common.opt
@@ -2109,6 +2109,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) Optimization
+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..4868867
--- /dev/null
+++ b/gcc/gimple-ssa-isolate-paths.c
@@ -0,0 +1,325 @@
+/* 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 "tree-ssanames.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;
+
+/* Insert a trap before SI and remove SI and all statements after SI. */
+
+static void
+insert_trap_and_remove_trailing_statements (gimple_stmt_iterator *si_p)
+{
+ 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 (si_p, seq, GSI_SAME_STMT);
+
+ /* Now delete all remaining statements in this block. */
+ for (; !gsi_end_p (*si_p);)
+ {
+ stmt = gsi_stmt (*si_p);
+ unlink_stmt_vdef (stmt);
+ gsi_remove (si_p, true);
+ release_defs (stmt);
+ }
+}
+
+/* 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 (bb);
+ si2 = gsi_start_nondebug_after_labels_bb (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. Insert a trap
+ before SI2 and remove SI2 and all trailing statements. */
+ if (!gsi_end_p (si2))
+ insert_trap_and_remove_trailing_statements (&si2);
+
+ 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))
+ continue;
+
+ 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. Catching cases in
+ in other blocks would require more complex path
+ isolation code. */
+ if (gimple_bb (use_stmt) != bb)
+ 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. This happens
+ because of jump threading and constant propagation. */
+ for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
+ {
+ gimple stmt = gsi_stmt (si);
+
+ /* 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))
+ {
+ insert_trap_and_remove_trailing_statements (&si);
+
+ /* 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);
+}
+
+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 20f6010..15688af 100644
--- a/gcc/gimple.c
+++ b/gcc/gimple.c
@@ -4103,6 +4103,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))
+ 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)
+ && 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))
+ 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)
+ && 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 b34424c..430b50c 100644
--- a/gcc/gimple.h
+++ b/gcc/gimple.h
@@ -1089,6 +1089,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);
diff --git a/gcc/opts.c b/gcc/opts.c
index 4db20f0..3a939ac 100644
--- a/gcc/opts.c
+++ b/gcc/opts.c
@@ -493,6 +493,7 @@ static const struct default_options default_options_table[] =
{ OPT_LEVELS_2_PLUS, OPT_fvect_cost_model_, NULL, VECT_COST_MODEL_CHEAP },
{ OPT_LEVELS_2_PLUS_SPEED_ONLY, OPT_foptimize_strlen, NULL, 1 },
{ OPT_LEVELS_2_PLUS, OPT_fhoist_adjacent_loads, NULL, 1 },
+ { OPT_LEVELS_2_PLUS, OPT_fisolate_erroneous_paths, NULL, 1 },
/* -O3 optimizations. */
{ OPT_LEVELS_3_PLUS, OPT_ftree_loop_distribute_patterns, NULL, 1 },
diff --git a/gcc/passes.def b/gcc/passes.def
index 31ce113..0dabba4 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/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 66d61ae..afdadb8 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 c4d09fe..3aeaeeb 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 b74bed3..2a90430 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
^ permalink raw reply [flat|nested] 41+ messages in thread
* Re: [RFA][PATCH] Isolate erroneous paths optimization
2013-11-05 2:03 ` Jeff Law
@ 2013-11-05 11:59 ` Richard Biener
2013-11-05 18:45 ` Jeff Law
2013-11-05 19:56 ` Jeff Law
2013-11-06 5:42 ` Ian Lance Taylor
2013-11-13 18:13 ` Ulrich Weigand
2 siblings, 2 replies; 41+ messages in thread
From: Richard Biener @ 2013-11-05 11:59 UTC (permalink / raw)
To: Jeff Law; +Cc: gcc-patches
On Tue, Nov 5, 2013 at 2:57 AM, Jeff Law <law@redhat.com> wrote:
> 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.
Are you sure? omp lowering makes unconditional use of it and I see
it created in f95-lang.c. There are various other unconditional uses
one covering vararg functions, one exceptions. I doubt we have a
language that doesn't have BUILT_IN_TRAP, and if that is so, it should
be fixed to provide it ... (java seems to miss it).
>
>>>
>>> +/* 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.
Oh, indeed.
>
>
>
>>> + /* 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.
Ok.
Thanks,
Richard.
>
> 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.
>
> diff --git a/gcc/Makefile.in b/gcc/Makefile.in
> index cc88fb8..9dd5dbe 100644
> --- a/gcc/Makefile.in
> +++ b/gcc/Makefile.in
> @@ -1234,6 +1234,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 3a40db2..bda4790 100644
> --- a/gcc/common.opt
> +++ b/gcc/common.opt
> @@ -2109,6 +2109,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) Optimization
> +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..4868867
> --- /dev/null
> +++ b/gcc/gimple-ssa-isolate-paths.c
> @@ -0,0 +1,325 @@
> +/* 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 "tree-ssanames.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;
> +
> +/* Insert a trap before SI and remove SI and all statements after SI. */
> +
> +static void
> +insert_trap_and_remove_trailing_statements (gimple_stmt_iterator *si_p)
> +{
> + 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 (si_p, seq, GSI_SAME_STMT);
> +
> + /* Now delete all remaining statements in this block. */
> + for (; !gsi_end_p (*si_p);)
> + {
> + stmt = gsi_stmt (*si_p);
> + unlink_stmt_vdef (stmt);
> + gsi_remove (si_p, true);
> + release_defs (stmt);
> + }
> +}
> +
> +/* 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 (bb);
> + si2 = gsi_start_nondebug_after_labels_bb (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. Insert a trap
> + before SI2 and remove SI2 and all trailing statements. */
> + if (!gsi_end_p (si2))
> + insert_trap_and_remove_trailing_statements (&si2);
> +
> + 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))
> + continue;
> +
> + 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. Catching cases in
> + in other blocks would require more complex path
> + isolation code. */
> + if (gimple_bb (use_stmt) != bb)
> + 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. This happens
> + because of jump threading and constant propagation. */
> + for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
> + {
> + gimple stmt = gsi_stmt (si);
> +
> + /* 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))
> + {
> + insert_trap_and_remove_trailing_statements (&si);
> +
> + /* 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);
> +}
> +
> +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 20f6010..15688af 100644
> --- a/gcc/gimple.c
> +++ b/gcc/gimple.c
> @@ -4103,6 +4103,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))
> + 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)
> + && 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))
> + 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)
> + && 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 b34424c..430b50c 100644
> --- a/gcc/gimple.h
> +++ b/gcc/gimple.h
> @@ -1089,6 +1089,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);
> diff --git a/gcc/opts.c b/gcc/opts.c
> index 4db20f0..3a939ac 100644
> --- a/gcc/opts.c
> +++ b/gcc/opts.c
> @@ -493,6 +493,7 @@ static const struct default_options
> default_options_table[] =
> { OPT_LEVELS_2_PLUS, OPT_fvect_cost_model_, NULL, VECT_COST_MODEL_CHEAP
> },
> { OPT_LEVELS_2_PLUS_SPEED_ONLY, OPT_foptimize_strlen, NULL, 1 },
> { OPT_LEVELS_2_PLUS, OPT_fhoist_adjacent_loads, NULL, 1 },
> + { OPT_LEVELS_2_PLUS, OPT_fisolate_erroneous_paths, NULL, 1 },
>
> /* -O3 optimizations. */
> { OPT_LEVELS_3_PLUS, OPT_ftree_loop_distribute_patterns, NULL, 1 },
> diff --git a/gcc/passes.def b/gcc/passes.def
> index 31ce113..0dabba4 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/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 66d61ae..afdadb8 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 c4d09fe..3aeaeeb 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 b74bed3..2a90430 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
>
^ permalink raw reply [flat|nested] 41+ messages in thread
* Re: [RFA][PATCH] Isolate erroneous paths optimization
2013-11-05 11:59 ` Richard Biener
@ 2013-11-05 18:45 ` Jeff Law
2013-11-05 19:56 ` Jeff Law
1 sibling, 0 replies; 41+ messages in thread
From: Jeff Law @ 2013-11-05 18:45 UTC (permalink / raw)
To: Richard Biener; +Cc: gcc-patches
On 11/05/13 04:53, Richard Biener wrote:
>>
>> Fortran front-end doesn't provide this IIRC.
>
> Are you sure? omp lowering makes unconditional use of it and I see
> it created in f95-lang.c. There are various other unconditional uses
> one covering vararg functions, one exceptions. I doubt we have a
> language that doesn't have BUILT_IN_TRAP, and if that is so, it should
> be fixed to provide it ... (java seems to miss it).
Could have been java -- I added that fragment in response to finding an
implicit NULL dereference during a bootstrap and noting the language
simply never defined the appropriate builtin.
Java would actually make sense -- removing the fragment doesn't trip the
bootstrap failure anymore -- which can be explained by the change to use
infer_nonnull_range which returns false unless
-fdelete-null-pointer-checks is enabled (which it isn't for java).
Jeff
^ permalink raw reply [flat|nested] 41+ messages in thread
* Re: [RFA][PATCH] Isolate erroneous paths optimization
2013-11-05 11:59 ` Richard Biener
2013-11-05 18:45 ` Jeff Law
@ 2013-11-05 19:56 ` Jeff Law
1 sibling, 0 replies; 41+ messages in thread
From: Jeff Law @ 2013-11-05 19:56 UTC (permalink / raw)
To: Richard Biener; +Cc: gcc-patches
On 11/05/13 04:53, Richard Biener wrote:
>>
>> Fortran front-end doesn't provide this IIRC.
>
> Are you sure? omp lowering makes unconditional use of it and I see
> it created in f95-lang.c. There are various other unconditional uses
> one covering vararg functions, one exceptions. I doubt we have a
> language that doesn't have BUILT_IN_TRAP, and if that is so, it should
> be fixed to provide it ... (java seems to miss it).
Just to confirm, I hacked things up a bit and was able to trip the
failure again in the java front-end.
I'll go ahead with the patch as-is with a followup to add the builtin to
the java front-end and remove the hack from gimple-ssa-isolate-paths.
jeff
^ permalink raw reply [flat|nested] 41+ messages in thread
* Re: [RFA][PATCH] Isolate erroneous paths optimization
2013-11-05 2:03 ` Jeff Law
2013-11-05 11:59 ` Richard Biener
@ 2013-11-06 5:42 ` Ian Lance Taylor
2013-11-06 6:11 ` Jeff Law
2013-11-06 7:05 ` Marc Glisse
2013-11-13 18:13 ` Ulrich Weigand
2 siblings, 2 replies; 41+ messages in thread
From: Ian Lance Taylor @ 2013-11-06 5:42 UTC (permalink / raw)
To: Jeff Law; +Cc: Richard Biener, gcc-patches
On Mon, Nov 4, 2013 at 5:57 PM, Jeff Law <law@redhat.com> wrote:
>
> * 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.
This patch actually breaks the Go testsuite. In Go dereferencing a
nil pointer is well-defined: it causes panic that can be caught. This
breaks a test for that functionality by changing the panic to a
builtin_trap.
That's not a big deal; I'll just disable this optimization in the Go
frontend.
What I'm really writing about is that it seems to me that there should
be some docs for this new option in gcc/doc/invoke.texi. I don't see
any.
Ian
^ permalink raw reply [flat|nested] 41+ messages in thread
* Re: [RFA][PATCH] Isolate erroneous paths optimization
2013-11-06 5:42 ` Ian Lance Taylor
@ 2013-11-06 6:11 ` Jeff Law
2013-11-06 7:05 ` Marc Glisse
1 sibling, 0 replies; 41+ messages in thread
From: Jeff Law @ 2013-11-06 6:11 UTC (permalink / raw)
To: Ian Lance Taylor; +Cc: Richard Biener, gcc-patches
On 11/05/13 22:24, Ian Lance Taylor wrote:
> On Mon, Nov 4, 2013 at 5:57 PM, Jeff Law <law@redhat.com> wrote:
>>
>> * 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.
>
>
> This patch actually breaks the Go testsuite. In Go dereferencing a
> nil pointer is well-defined: it causes panic that can be caught. This
> breaks a test for that functionality by changing the panic to a
> builtin_trap.
>
> That's not a big deal; I'll just disable this optimization in the Go
> frontend.
That's certainly the right thing to do. Sorry, I don't have Go enabled
so I didn't catch it.
>
> What I'm really writing about is that it seems to me that there should
> be some docs for this new option in gcc/doc/invoke.texi. I don't see
> any.
Sigh. I'll take care of that oversight.
jeff
^ permalink raw reply [flat|nested] 41+ messages in thread
* Re: [RFA][PATCH] Isolate erroneous paths optimization
2013-11-06 5:42 ` Ian Lance Taylor
2013-11-06 6:11 ` Jeff Law
@ 2013-11-06 7:05 ` Marc Glisse
2013-11-06 14:34 ` Ian Lance Taylor
1 sibling, 1 reply; 41+ messages in thread
From: Marc Glisse @ 2013-11-06 7:05 UTC (permalink / raw)
To: Ian Lance Taylor; +Cc: Jeff Law, Richard Biener, gcc-patches
On Tue, 5 Nov 2013, Ian Lance Taylor wrote:
> This patch actually breaks the Go testsuite. In Go dereferencing a
> nil pointer is well-defined: it causes panic that can be caught. This
> breaks a test for that functionality by changing the panic to a
> builtin_trap.
>
> That's not a big deal; I'll just disable this optimization in the Go
> frontend.
Shouldn't go use -fno-delete-null-pointer-checks by default then? That
should disable this optimization and others that rely on the same idea.
--
Marc Glisse
^ permalink raw reply [flat|nested] 41+ messages in thread
* Re: [RFA][PATCH] Isolate erroneous paths optimization
2013-11-06 7:05 ` Marc Glisse
@ 2013-11-06 14:34 ` Ian Lance Taylor
2013-11-06 14:41 ` Richard Biener
0 siblings, 1 reply; 41+ messages in thread
From: Ian Lance Taylor @ 2013-11-06 14:34 UTC (permalink / raw)
To: gcc-patches; +Cc: Jeff Law, Richard Biener
On Tue, Nov 5, 2013 at 10:50 PM, Marc Glisse <marc.glisse@inria.fr> wrote:
> On Tue, 5 Nov 2013, Ian Lance Taylor wrote:
>
>> This patch actually breaks the Go testsuite. In Go dereferencing a
>> nil pointer is well-defined: it causes panic that can be caught. This
>> breaks a test for that functionality by changing the panic to a
>> builtin_trap.
>>
>> That's not a big deal; I'll just disable this optimization in the Go
>> frontend.
>
>
> Shouldn't go use -fno-delete-null-pointer-checks by default then? That
> should disable this optimization and others that rely on the same idea.
No, that is a different optimization with different properties. The
-fdelete-null-pointer-checks optimization assumes that if you write
x = *p;
if (p == NULL) { printf ("NULL\n"); }
that the test p == NULL can not succeed. In Go, that is true. If p
is NULL the *p will cause a panic and ordinary code execution will not
proceed.
The recent -fisolate-erroneous-paths optimization will change code
like this:
if (p == NULL) { printf ("NULL\n"); }
x = *p;
into code like this:
if (p == NULL) { printf ("NULL\n"); __builtin_trap (); }
x = *p;
That is, it will insert a trap rather than dereferencing the pointer
known to be NULL. This doesn't work for Go because we really do want
the panic, not the __builtin_trap. This optimization would work fine
for Go if there were a way to explicitly call the panic function
rather than calling trap, but that would be a frontend-dependent
aspect to a middle-end optimization.
Ian
^ permalink raw reply [flat|nested] 41+ messages in thread
* Re: [RFA][PATCH] Isolate erroneous paths optimization
2013-11-06 14:34 ` Ian Lance Taylor
@ 2013-11-06 14:41 ` Richard Biener
2013-11-06 15:15 ` Ian Lance Taylor
0 siblings, 1 reply; 41+ messages in thread
From: Richard Biener @ 2013-11-06 14:41 UTC (permalink / raw)
To: Ian Lance Taylor; +Cc: gcc-patches, Jeff Law
On Wed, Nov 6, 2013 at 3:24 PM, Ian Lance Taylor <iant@google.com> wrote:
> On Tue, Nov 5, 2013 at 10:50 PM, Marc Glisse <marc.glisse@inria.fr> wrote:
>> On Tue, 5 Nov 2013, Ian Lance Taylor wrote:
>>
>>> This patch actually breaks the Go testsuite. In Go dereferencing a
>>> nil pointer is well-defined: it causes panic that can be caught. This
>>> breaks a test for that functionality by changing the panic to a
>>> builtin_trap.
>>>
>>> That's not a big deal; I'll just disable this optimization in the Go
>>> frontend.
>>
>>
>> Shouldn't go use -fno-delete-null-pointer-checks by default then? That
>> should disable this optimization and others that rely on the same idea.
>
> No, that is a different optimization with different properties. The
> -fdelete-null-pointer-checks optimization assumes that if you write
> x = *p;
> if (p == NULL) { printf ("NULL\n"); }
> that the test p == NULL can not succeed. In Go, that is true. If p
> is NULL the *p will cause a panic and ordinary code execution will not
> proceed.
>
> The recent -fisolate-erroneous-paths optimization will change code
> like this:
> if (p == NULL) { printf ("NULL\n"); }
> x = *p;
> into code like this:
> if (p == NULL) { printf ("NULL\n"); __builtin_trap (); }
> x = *p;
> That is, it will insert a trap rather than dereferencing the pointer
> known to be NULL. This doesn't work for Go because we really do want
> the panic, not the __builtin_trap. This optimization would work fine
> for Go if there were a way to explicitly call the panic function
> rather than calling trap, but that would be a frontend-dependent
> aspect to a middle-end optimization.
But then you have -fnon-call-exceptions enabled? Where obviously
-fisolate-erroneous-paths also shouldn't apply?
Richard.
> Ian
^ permalink raw reply [flat|nested] 41+ messages in thread
* Re: [RFA][PATCH] Isolate erroneous paths optimization
2013-11-06 14:41 ` Richard Biener
@ 2013-11-06 15:15 ` Ian Lance Taylor
2013-11-06 15:23 ` Richard Biener
2013-11-06 16:15 ` [RFA][PATCH] Isolate erroneous paths optimization Jeff Law
0 siblings, 2 replies; 41+ messages in thread
From: Ian Lance Taylor @ 2013-11-06 15:15 UTC (permalink / raw)
To: Richard Biener; +Cc: gcc-patches, Jeff Law
On Wed, Nov 6, 2013 at 6:29 AM, Richard Biener
<richard.guenther@gmail.com> wrote:
> On Wed, Nov 6, 2013 at 3:24 PM, Ian Lance Taylor <iant@google.com> wrote:
>> On Tue, Nov 5, 2013 at 10:50 PM, Marc Glisse <marc.glisse@inria.fr> wrote:
>>> On Tue, 5 Nov 2013, Ian Lance Taylor wrote:
>>>
>>>> This patch actually breaks the Go testsuite. In Go dereferencing a
>>>> nil pointer is well-defined: it causes panic that can be caught. This
>>>> breaks a test for that functionality by changing the panic to a
>>>> builtin_trap.
>>>>
>>>> That's not a big deal; I'll just disable this optimization in the Go
>>>> frontend.
>>>
>>>
>>> Shouldn't go use -fno-delete-null-pointer-checks by default then? That
>>> should disable this optimization and others that rely on the same idea.
>>
>> No, that is a different optimization with different properties. The
>> -fdelete-null-pointer-checks optimization assumes that if you write
>> x = *p;
>> if (p == NULL) { printf ("NULL\n"); }
>> that the test p == NULL can not succeed. In Go, that is true. If p
>> is NULL the *p will cause a panic and ordinary code execution will not
>> proceed.
>>
>> The recent -fisolate-erroneous-paths optimization will change code
>> like this:
>> if (p == NULL) { printf ("NULL\n"); }
>> x = *p;
>> into code like this:
>> if (p == NULL) { printf ("NULL\n"); __builtin_trap (); }
>> x = *p;
>> That is, it will insert a trap rather than dereferencing the pointer
>> known to be NULL. This doesn't work for Go because we really do want
>> the panic, not the __builtin_trap. This optimization would work fine
>> for Go if there were a way to explicitly call the panic function
>> rather than calling trap, but that would be a frontend-dependent
>> aspect to a middle-end optimization.
>
> But then you have -fnon-call-exceptions enabled?
Yes (go_langhook_init_options_struct in go/go-lang.c).
> Where obviously
> -fisolate-erroneous-paths also shouldn't apply?
I guess that's not entirely obvious to me. I'm not sure that
-fnon-call-exceptions means that all trapping instructions must be
executed.
Ian
^ permalink raw reply [flat|nested] 41+ messages in thread
* Re: [RFA][PATCH] Isolate erroneous paths optimization
2013-11-06 15:15 ` Ian Lance Taylor
@ 2013-11-06 15:23 ` Richard Biener
2013-11-06 15:24 ` Ian Lance Taylor
2013-11-06 16:15 ` [RFA][PATCH] Isolate erroneous paths optimization Jeff Law
1 sibling, 1 reply; 41+ messages in thread
From: Richard Biener @ 2013-11-06 15:23 UTC (permalink / raw)
To: Ian Lance Taylor; +Cc: gcc-patches, Jeff Law
On Wed, Nov 6, 2013 at 4:08 PM, Ian Lance Taylor <iant@google.com> wrote:
> On Wed, Nov 6, 2013 at 6:29 AM, Richard Biener
> <richard.guenther@gmail.com> wrote:
>> On Wed, Nov 6, 2013 at 3:24 PM, Ian Lance Taylor <iant@google.com> wrote:
>>> On Tue, Nov 5, 2013 at 10:50 PM, Marc Glisse <marc.glisse@inria.fr> wrote:
>>>> On Tue, 5 Nov 2013, Ian Lance Taylor wrote:
>>>>
>>>>> This patch actually breaks the Go testsuite. In Go dereferencing a
>>>>> nil pointer is well-defined: it causes panic that can be caught. This
>>>>> breaks a test for that functionality by changing the panic to a
>>>>> builtin_trap.
>>>>>
>>>>> That's not a big deal; I'll just disable this optimization in the Go
>>>>> frontend.
>>>>
>>>>
>>>> Shouldn't go use -fno-delete-null-pointer-checks by default then? That
>>>> should disable this optimization and others that rely on the same idea.
>>>
>>> No, that is a different optimization with different properties. The
>>> -fdelete-null-pointer-checks optimization assumes that if you write
>>> x = *p;
>>> if (p == NULL) { printf ("NULL\n"); }
>>> that the test p == NULL can not succeed. In Go, that is true. If p
>>> is NULL the *p will cause a panic and ordinary code execution will not
>>> proceed.
>>>
>>> The recent -fisolate-erroneous-paths optimization will change code
>>> like this:
>>> if (p == NULL) { printf ("NULL\n"); }
>>> x = *p;
>>> into code like this:
>>> if (p == NULL) { printf ("NULL\n"); __builtin_trap (); }
>>> x = *p;
>>> That is, it will insert a trap rather than dereferencing the pointer
>>> known to be NULL. This doesn't work for Go because we really do want
>>> the panic, not the __builtin_trap. This optimization would work fine
>>> for Go if there were a way to explicitly call the panic function
>>> rather than calling trap, but that would be a frontend-dependent
>>> aspect to a middle-end optimization.
>>
>> But then you have -fnon-call-exceptions enabled?
>
> Yes (go_langhook_init_options_struct in go/go-lang.c).
>
>> Where obviously
>> -fisolate-erroneous-paths also shouldn't apply?
>
> I guess that's not entirely obvious to me. I'm not sure that
> -fnon-call-exceptions means that all trapping instructions must be
> executed.
No, I don't think it means that. But I think that you cannot transform
foo ()
{
*0 = 1;
}
to __builtin_trap as you can catch the trap via an exception handler
in a caller of foo, no? The question is whether we may change
one kind of "trap" for another (which we'd do in this case). Also
__builtin_trap () may expand to a abort () call IIRC if the target
doesn't have a suitable instruction that traps.
Richard.
> Ian
^ permalink raw reply [flat|nested] 41+ messages in thread
* Re: [RFA][PATCH] Isolate erroneous paths optimization
2013-11-06 15:23 ` Richard Biener
@ 2013-11-06 15:24 ` Ian Lance Taylor
2013-11-06 15:27 ` Richard Biener
` (2 more replies)
0 siblings, 3 replies; 41+ messages in thread
From: Ian Lance Taylor @ 2013-11-06 15:24 UTC (permalink / raw)
To: Richard Biener; +Cc: gcc-patches, Jeff Law
On Wed, Nov 6, 2013 at 7:15 AM, Richard Biener
<richard.guenther@gmail.com> wrote:
>
> But I think that you cannot transform
>
> foo ()
> {
> *0 = 1;
> }
>
> to __builtin_trap as you can catch the trap via an exception handler
> in a caller of foo, no?
That is true. OK, I can see an argument that when using
-fnon-call-exceptions that kind of code should not be changed to call
__builtin_trap.
In that case I think it would be fine to run the isolate paths
optimization, but to not omit the actual dereference of the NULL
pointer (possibly the dereference could be followed by a trap).
Ian
^ permalink raw reply [flat|nested] 41+ messages in thread
* Re: [RFA][PATCH] Isolate erroneous paths optimization
2013-11-06 15:24 ` Ian Lance Taylor
@ 2013-11-06 15:27 ` Richard Biener
2013-11-06 15:59 ` Jakub Jelinek
2013-11-06 16:26 ` Jeff Law
2013-11-06 16:20 ` Jeff Law
2013-11-10 13:06 ` Eric Botcazou
2 siblings, 2 replies; 41+ messages in thread
From: Richard Biener @ 2013-11-06 15:27 UTC (permalink / raw)
To: Ian Lance Taylor; +Cc: gcc-patches, Jeff Law
On Wed, Nov 6, 2013 at 4:20 PM, Ian Lance Taylor <iant@google.com> wrote:
> On Wed, Nov 6, 2013 at 7:15 AM, Richard Biener
> <richard.guenther@gmail.com> wrote:
>>
>> But I think that you cannot transform
>>
>> foo ()
>> {
>> *0 = 1;
>> }
>>
>> to __builtin_trap as you can catch the trap via an exception handler
>> in a caller of foo, no?
>
> That is true. OK, I can see an argument that when using
> -fnon-call-exceptions that kind of code should not be changed to call
> __builtin_trap.
>
> In that case I think it would be fine to run the isolate paths
> optimization, but to not omit the actual dereference of the NULL
> pointer (possibly the dereference could be followed by a trap).
Yeah, we need the trap to properly end the BB (even if that is a
waste instruction generated).
Richard.
> Ian
^ permalink raw reply [flat|nested] 41+ messages in thread
* Re: [RFA][PATCH] Isolate erroneous paths optimization
2013-11-06 15:27 ` Richard Biener
@ 2013-11-06 15:59 ` Jakub Jelinek
2013-11-06 17:01 ` Jeff Law
2013-11-06 16:26 ` Jeff Law
1 sibling, 1 reply; 41+ messages in thread
From: Jakub Jelinek @ 2013-11-06 15:59 UTC (permalink / raw)
To: Richard Biener; +Cc: Ian Lance Taylor, gcc-patches, Jeff Law
On Wed, Nov 06, 2013 at 04:23:06PM +0100, Richard Biener wrote:
> > In that case I think it would be fine to run the isolate paths
> > optimization, but to not omit the actual dereference of the NULL
> > pointer (possibly the dereference could be followed by a trap).
>
> Yeah, we need the trap to properly end the BB (even if that is a
> waste instruction generated).
BTW, why do we generate in this optimization __builtin_trap rather than
just __builtin_unreachable ()? The former still generates some code (abort,
some aborting instruction, ...), while the former is just an assertion that
valid code will not reach it.
Jakub
^ permalink raw reply [flat|nested] 41+ messages in thread
* Re: [RFA][PATCH] Isolate erroneous paths optimization
2013-11-06 15:15 ` Ian Lance Taylor
2013-11-06 15:23 ` Richard Biener
@ 2013-11-06 16:15 ` Jeff Law
1 sibling, 0 replies; 41+ messages in thread
From: Jeff Law @ 2013-11-06 16:15 UTC (permalink / raw)
To: Ian Lance Taylor, Richard Biener; +Cc: gcc-patches
On 11/06/13 08:08, Ian Lance Taylor wrote:
>>>
>>> The recent -fisolate-erroneous-paths optimization will change code
>>> like this:
>>> if (p == NULL) { printf ("NULL\n"); }
>>> x = *p;
>>> into code like this:
>>> if (p == NULL) { printf ("NULL\n"); __builtin_trap (); }
>>> x = *p;
>>> That is, it will insert a trap rather than dereferencing the pointer
>>> known to be NULL. This doesn't work for Go because we really do want
>>> the panic, not the __builtin_trap. This optimization would work fine
>>> for Go if there were a way to explicitly call the panic function
>>> rather than calling trap, but that would be a frontend-dependent
>>> aspect to a middle-end optimization.
>>
>> But then you have -fnon-call-exceptions enabled?
>
> Yes (go_langhook_init_options_struct in go/go-lang.c).
I wonder if we could have the front-ends define a builtin to use in this
kind of situation and use the builtin trap as a fallback if the
front-end didn't provide a suitable builtin.
>
>> Where obviously
>> -fisolate-erroneous-paths also shouldn't apply?
>
> I guess that's not entirely obvious to me. I'm not sure that
> -fnon-call-exceptions means that all trapping instructions must be
> executed.
In effect, yes.
Jeff
^ permalink raw reply [flat|nested] 41+ messages in thread
* Re: [RFA][PATCH] Isolate erroneous paths optimization
2013-11-06 15:24 ` Ian Lance Taylor
2013-11-06 15:27 ` Richard Biener
@ 2013-11-06 16:20 ` Jeff Law
2013-11-10 13:06 ` Eric Botcazou
2 siblings, 0 replies; 41+ messages in thread
From: Jeff Law @ 2013-11-06 16:20 UTC (permalink / raw)
To: Ian Lance Taylor, Richard Biener; +Cc: gcc-patches
On 11/06/13 08:20, Ian Lance Taylor wrote:
> On Wed, Nov 6, 2013 at 7:15 AM, Richard Biener
> <richard.guenther@gmail.com> wrote:
>>
>> But I think that you cannot transform
>>
>> foo ()
>> {
>> *0 = 1;
>> }
>>
>> to __builtin_trap as you can catch the trap via an exception handler
>> in a caller of foo, no?
>
> That is true. OK, I can see an argument that when using
> -fnon-call-exceptions that kind of code should not be changed to call
> __builtin_trap.
>
> In that case I think it would be fine to run the isolate paths
> optimization, but to not omit the actual dereference of the NULL
> pointer (possibly the dereference could be followed by a trap).
That would be trivial to implement. I went back and forth on whether to
to leave the *0 or issue the trap. A program could catch the *0 and do
something in its handler. Changing the *0 to a trap would change hte
program's behaviour if it took different action in the handler on the trap.
The trap works better in other cases that don't involve a dereference
though. For example, if a function has an argument that is marked as
must be non-null and we find a path which passes null for that argument
trapping seems best.
jeff
^ permalink raw reply [flat|nested] 41+ messages in thread
* Re: [RFA][PATCH] Isolate erroneous paths optimization
2013-11-06 15:27 ` Richard Biener
2013-11-06 15:59 ` Jakub Jelinek
@ 2013-11-06 16:26 ` Jeff Law
1 sibling, 0 replies; 41+ messages in thread
From: Jeff Law @ 2013-11-06 16:26 UTC (permalink / raw)
To: Richard Biener, Ian Lance Taylor; +Cc: gcc-patches
On 11/06/13 08:23, Richard Biener wrote:
> On Wed, Nov 6, 2013 at 4:20 PM, Ian Lance Taylor <iant@google.com> wrote:
>> On Wed, Nov 6, 2013 at 7:15 AM, Richard Biener
>> <richard.guenther@gmail.com> wrote:
>>>
>>> But I think that you cannot transform
>>>
>>> foo ()
>>> {
>>> *0 = 1;
>>> }
>>>
>>> to __builtin_trap as you can catch the trap via an exception handler
>>> in a caller of foo, no?
>>
>> That is true. OK, I can see an argument that when using
>> -fnon-call-exceptions that kind of code should not be changed to call
>> __builtin_trap.
>>
>> In that case I think it would be fine to run the isolate paths
>> optimization, but to not omit the actual dereference of the NULL
>> pointer (possibly the dereference could be followed by a trap).
>
> Yeah, we need the trap to properly end the BB (even if that is a
> waste instruction generated).
Right. We *really* don't want execution to continue. We've entered an
undefined state and continuing execution can lead to all kinds of nasty
problems, including security exploits.
jeff
^ permalink raw reply [flat|nested] 41+ messages in thread
* Re: [RFA][PATCH] Isolate erroneous paths optimization
2013-11-06 17:01 ` Jeff Law
@ 2013-11-06 16:36 ` Jakub Jelinek
0 siblings, 0 replies; 41+ messages in thread
From: Jakub Jelinek @ 2013-11-06 16:36 UTC (permalink / raw)
To: Jeff Law; +Cc: Richard Biener, Ian Lance Taylor, gcc-patches
On Wed, Nov 06, 2013 at 09:15:57AM -0700, Jeff Law wrote:
> On 11/06/13 08:27, Jakub Jelinek wrote:
> >On Wed, Nov 06, 2013 at 04:23:06PM +0100, Richard Biener wrote:
> >>>In that case I think it would be fine to run the isolate paths
> >>>optimization, but to not omit the actual dereference of the NULL
> >>>pointer (possibly the dereference could be followed by a trap).
> >>
> >>Yeah, we need the trap to properly end the BB (even if that is a
> >>waste instruction generated).
> >
> >BTW, why do we generate in this optimization __builtin_trap rather than
> >just __builtin_unreachable ()? The former still generates some code (abort,
> >some aborting instruction, ...), while the former is just an assertion that
> >valid code will not reach it.
> Because if you do reach the site, you really want to halt the
> program to avoid potential security exploits. I'm actually of the
> opinion that builtin_unreachable should be trapping as well.
__builtin_unreachable () is trapping if -fsanitize=unreachable, but
otherwise it is just an optimization hint, intentionally so, that allows
optimizing on the fact that it doesn't happen. If from fear of security
exploits we'd stop trying to optimize code well, we'd need to punt on using
undefined integer overflow and many other things.
Jakub
^ permalink raw reply [flat|nested] 41+ messages in thread
* Re: [RFA][PATCH] Isolate erroneous paths optimization
2013-11-06 15:59 ` Jakub Jelinek
@ 2013-11-06 17:01 ` Jeff Law
2013-11-06 16:36 ` Jakub Jelinek
0 siblings, 1 reply; 41+ messages in thread
From: Jeff Law @ 2013-11-06 17:01 UTC (permalink / raw)
To: Jakub Jelinek, Richard Biener; +Cc: Ian Lance Taylor, gcc-patches
On 11/06/13 08:27, Jakub Jelinek wrote:
> On Wed, Nov 06, 2013 at 04:23:06PM +0100, Richard Biener wrote:
>>> In that case I think it would be fine to run the isolate paths
>>> optimization, but to not omit the actual dereference of the NULL
>>> pointer (possibly the dereference could be followed by a trap).
>>
>> Yeah, we need the trap to properly end the BB (even if that is a
>> waste instruction generated).
>
> BTW, why do we generate in this optimization __builtin_trap rather than
> just __builtin_unreachable ()? The former still generates some code (abort,
> some aborting instruction, ...), while the former is just an assertion that
> valid code will not reach it.
Because if you do reach the site, you really want to halt the program to
avoid potential security exploits. I'm actually of the opinion that
builtin_unreachable should be trapping as well.
jeff
^ permalink raw reply [flat|nested] 41+ messages in thread
* Re: [RFA][PATCH] Isolate erroneous paths optimization
2013-11-06 15:24 ` Ian Lance Taylor
2013-11-06 15:27 ` Richard Biener
2013-11-06 16:20 ` Jeff Law
@ 2013-11-10 13:06 ` Eric Botcazou
2013-11-11 9:33 ` Jeff Law
2 siblings, 1 reply; 41+ messages in thread
From: Eric Botcazou @ 2013-11-10 13:06 UTC (permalink / raw)
To: Ian Lance Taylor; +Cc: gcc-patches, Richard Biener, Jeff Law
> > But I think that you cannot transform
> >
> > foo ()
> > {
> >
> > *0 = 1;
> >
> > }
> >
> > to __builtin_trap as you can catch the trap via an exception handler
> > in a caller of foo, no?
>
> That is true. OK, I can see an argument that when using
> -fnon-call-exceptions that kind of code should not be changed to call
> __builtin_trap.
That's exactly the reason why gnat.dg/memtrap.adb started to fail after Jeff's
patch went it. So, if -fisolate-erroneous-paths isn't amended, we'll need to
disable it in Ada like in Go.
> In that case I think it would be fine to run the isolate paths
> optimization, but to not omit the actual dereference of the NULL
> pointer (possibly the dereference could be followed by a trap).
This would probably work for Ada as well.
--
Eric Botcazou
^ permalink raw reply [flat|nested] 41+ messages in thread
* Re: [RFA][PATCH] Isolate erroneous paths optimization
2013-11-10 13:06 ` Eric Botcazou
@ 2013-11-11 9:33 ` Jeff Law
2013-11-11 9:50 ` Eric Botcazou
` (2 more replies)
0 siblings, 3 replies; 41+ messages in thread
From: Jeff Law @ 2013-11-11 9:33 UTC (permalink / raw)
To: Eric Botcazou, Ian Lance Taylor; +Cc: gcc-patches, Richard Biener
On 11/10/13 05:34, Eric Botcazou wrote:
>>> But I think that you cannot transform
>>>
>>> foo ()
>>> {
>>>
>>> *0 = 1;
>>>
>>> }
>>>
>>> to __builtin_trap as you can catch the trap via an exception handler
>>> in a caller of foo, no?
>>
>> That is true. OK, I can see an argument that when using
>> -fnon-call-exceptions that kind of code should not be changed to call
>> __builtin_trap.
>
> That's exactly the reason why gnat.dg/memtrap.adb started to fail after Jeff's
> patch went it. So, if -fisolate-erroneous-paths isn't amended, we'll need to
> disable it in Ada like in Go.
>
>> In that case I think it would be fine to run the isolate paths
>> optimization, but to not omit the actual dereference of the NULL
>> pointer (possibly the dereference could be followed by a trap).
>
> This would probably work for Ada as well.
OK. It sounds like there's a pretty general consensus that we ought ot
go ahead and leave in a load/store of a NULL pointer. I'll go ahead and
run with that. I'll probably just emit SSA_NAME = *0, unless someone
thinks we ought ot distinguish between loads and stores, emitting
SSA_NAME = *0 and *0 = 0 for the two cases respectively.
However, that brings up an couple interesting questions.
Let's say we find a NULL pointer which reaches a return statement in a
function which is marked as returns_nonnull. In that case there is no
dereference. Presumably for that kind of scenario we'll just keep the
builtin trap.
Similarly, assume we extend this pass to detect out-of-bounds array
indexing. It's fairly simple to do and has always been in my plan. In
that case leaving in the array indexing won't necessarily generate a
fault. For those presumably we'll just want the builtin_trap as well?
Again, I don't mind inserting a *0, I just want to have a plan for the
other undefined behaviours we currently detect and those which I plan on
catching soon.
Jeff
^ permalink raw reply [flat|nested] 41+ messages in thread
* Re: [RFA][PATCH] Isolate erroneous paths optimization
2013-11-11 9:33 ` Jeff Law
@ 2013-11-11 9:50 ` Eric Botcazou
2013-11-11 17:41 ` Jeff Law
2013-11-11 12:55 ` Richard Biener
2013-11-12 17:42 ` [PATCH] Isolate erroneous paths optimization -- preserve *0 Jeff Law
2 siblings, 1 reply; 41+ messages in thread
From: Eric Botcazou @ 2013-11-11 9:50 UTC (permalink / raw)
To: Jeff Law; +Cc: gcc-patches, Ian Lance Taylor, Richard Biener
> However, that brings up an couple interesting questions.
>
> Let's say we find a NULL pointer which reaches a return statement in a
> function which is marked as returns_nonnull. In that case there is no
> dereference. Presumably for that kind of scenario we'll just keep the
> builtin trap.
>
> Similarly, assume we extend this pass to detect out-of-bounds array
> indexing. It's fairly simple to do and has always been in my plan. In
> that case leaving in the array indexing won't necessarily generate a
> fault. For those presumably we'll just want the builtin_trap as well?
>
> Again, I don't mind inserting a *0, I just want to have a plan for the
> other undefined behaviours we currently detect and those which I plan on
> catching soon.
The more general problem is that, with -fnon-call-exceptions, we really expect
a fully-fledged exception to be raised when something goes wrong. Inserting
__builtin_trap doesn't work because it's simply not equivalent to a throw. In
other words, if __builtin_throw would be inserted instead of __builtin_trap
with -fnon-call-exceptions, things would probably be acceptable as-is.
--
Eric Botcazou
^ permalink raw reply [flat|nested] 41+ messages in thread
* Re: [RFA][PATCH] Isolate erroneous paths optimization
2013-11-11 9:33 ` Jeff Law
2013-11-11 9:50 ` Eric Botcazou
@ 2013-11-11 12:55 ` Richard Biener
2013-11-11 17:07 ` Jeff Law
2013-11-12 17:42 ` [PATCH] Isolate erroneous paths optimization -- preserve *0 Jeff Law
2 siblings, 1 reply; 41+ messages in thread
From: Richard Biener @ 2013-11-11 12:55 UTC (permalink / raw)
To: Jeff Law; +Cc: Eric Botcazou, Ian Lance Taylor, GCC Patches
On Mon, Nov 11, 2013 at 4:11 AM, Jeff Law <law@redhat.com> wrote:
> On 11/10/13 05:34, Eric Botcazou wrote:
>>>>
>>>> But I think that you cannot transform
>>>>
>>>> foo ()
>>>> {
>>>>
>>>> *0 = 1;
>>>>
>>>> }
>>>>
>>>> to __builtin_trap as you can catch the trap via an exception handler
>>>> in a caller of foo, no?
>>>
>>>
>>> That is true. OK, I can see an argument that when using
>>> -fnon-call-exceptions that kind of code should not be changed to call
>>> __builtin_trap.
>>
>>
>> That's exactly the reason why gnat.dg/memtrap.adb started to fail after
>> Jeff's
>> patch went it. So, if -fisolate-erroneous-paths isn't amended, we'll need
>> to
>> disable it in Ada like in Go.
>>
>>> In that case I think it would be fine to run the isolate paths
>>> optimization, but to not omit the actual dereference of the NULL
>>> pointer (possibly the dereference could be followed by a trap).
>>
>>
>> This would probably work for Ada as well.
>
> OK. It sounds like there's a pretty general consensus that we ought ot go
> ahead and leave in a load/store of a NULL pointer. I'll go ahead and run
> with that. I'll probably just emit SSA_NAME = *0, unless someone thinks we
> ought ot distinguish between loads and stores, emitting SSA_NAME = *0 and *0
> = 0 for the two cases respectively.
Can't you simply keep the trapping stmt as-is?
Richard.
> However, that brings up an couple interesting questions.
>
> Let's say we find a NULL pointer which reaches a return statement in a
> function which is marked as returns_nonnull. In that case there is no
> dereference. Presumably for that kind of scenario we'll just keep the
> builtin trap.
>
> Similarly, assume we extend this pass to detect out-of-bounds array
> indexing. It's fairly simple to do and has always been in my plan. In that
> case leaving in the array indexing won't necessarily generate a fault. For
> those presumably we'll just want the builtin_trap as well?
>
> Again, I don't mind inserting a *0, I just want to have a plan for the other
> undefined behaviours we currently detect and those which I plan on catching
> soon.
>
> Jeff
>
^ permalink raw reply [flat|nested] 41+ messages in thread
* Re: [RFA][PATCH] Isolate erroneous paths optimization
2013-11-11 12:55 ` Richard Biener
@ 2013-11-11 17:07 ` Jeff Law
0 siblings, 0 replies; 41+ messages in thread
From: Jeff Law @ 2013-11-11 17:07 UTC (permalink / raw)
To: Richard Biener; +Cc: Eric Botcazou, Ian Lance Taylor, GCC Patches
On 11/11/13 05:16, Richard Biener wrote:
> On Mon, Nov 11, 2013 at 4:11 AM, Jeff Law <law@redhat.com> wrote:
>> On 11/10/13 05:34, Eric Botcazou wrote:
>>>>>
>>>>> But I think that you cannot transform
>>>>>
>>>>> foo ()
>>>>> {
>>>>>
>>>>> *0 = 1;
>>>>>
>>>>> }
>>>>>
>>>>> to __builtin_trap as you can catch the trap via an exception handler
>>>>> in a caller of foo, no?
>>>>
>>>>
>>>> That is true. OK, I can see an argument that when using
>>>> -fnon-call-exceptions that kind of code should not be changed to call
>>>> __builtin_trap.
>>>
>>>
>>> That's exactly the reason why gnat.dg/memtrap.adb started to fail after
>>> Jeff's
>>> patch went it. So, if -fisolate-erroneous-paths isn't amended, we'll need
>>> to
>>> disable it in Ada like in Go.
>>>
>>>> In that case I think it would be fine to run the isolate paths
>>>> optimization, but to not omit the actual dereference of the NULL
>>>> pointer (possibly the dereference could be followed by a trap).
>>>
>>>
>>> This would probably work for Ada as well.
>>
>> OK. It sounds like there's a pretty general consensus that we ought ot go
>> ahead and leave in a load/store of a NULL pointer. I'll go ahead and run
>> with that. I'll probably just emit SSA_NAME = *0, unless someone thinks we
>> ought ot distinguish between loads and stores, emitting SSA_NAME = *0 and *0
>> = 0 for the two cases respectively.
>
> Can't you simply keep the trapping stmt as-is?
You eliminate less dead code if the trapping statement is a store. You
want all the RHS nonsense in that case to just "go away".
jeff
^ permalink raw reply [flat|nested] 41+ messages in thread
* Re: [RFA][PATCH] Isolate erroneous paths optimization
2013-11-11 9:50 ` Eric Botcazou
@ 2013-11-11 17:41 ` Jeff Law
2013-11-11 17:43 ` Jakub Jelinek
0 siblings, 1 reply; 41+ messages in thread
From: Jeff Law @ 2013-11-11 17:41 UTC (permalink / raw)
To: Eric Botcazou; +Cc: gcc-patches, Ian Lance Taylor, Richard Biener
On 11/11/13 02:33, Eric Botcazou wrote:
>> However, that brings up an couple interesting questions.
>>
>> Let's say we find a NULL pointer which reaches a return statement in a
>> function which is marked as returns_nonnull. In that case there is no
>> dereference. Presumably for that kind of scenario we'll just keep the
>> builtin trap.
>>
>> Similarly, assume we extend this pass to detect out-of-bounds array
>> indexing. It's fairly simple to do and has always been in my plan. In
>> that case leaving in the array indexing won't necessarily generate a
>> fault. For those presumably we'll just want the builtin_trap as well?
>>
>> Again, I don't mind inserting a *0, I just want to have a plan for the
>> other undefined behaviours we currently detect and those which I plan on
>> catching soon.
>
> The more general problem is that, with -fnon-call-exceptions, we really expect
> a fully-fledged exception to be raised when something goes wrong. Inserting
> __builtin_trap doesn't work because it's simply not equivalent to a throw. In
> other words, if __builtin_throw would be inserted instead of __builtin_trap
> with -fnon-call-exceptions, things would probably be acceptable as-is.
Hmm, maybe that's a better soultion then. When non-call-exceptions is
active, throw rather than trap.
Seems fairly reasonable.
Jeff
^ permalink raw reply [flat|nested] 41+ messages in thread
* Re: [RFA][PATCH] Isolate erroneous paths optimization
2013-11-11 17:41 ` Jeff Law
@ 2013-11-11 17:43 ` Jakub Jelinek
2013-11-11 17:46 ` Ian Lance Taylor
2013-11-11 18:31 ` Eric Botcazou
0 siblings, 2 replies; 41+ messages in thread
From: Jakub Jelinek @ 2013-11-11 17:43 UTC (permalink / raw)
To: Jeff Law; +Cc: Eric Botcazou, gcc-patches, Ian Lance Taylor, Richard Biener
On Mon, Nov 11, 2013 at 09:24:27AM -0700, Jeff Law wrote:
> On 11/11/13 02:33, Eric Botcazou wrote:
> >>However, that brings up an couple interesting questions.
> >>
> >>Let's say we find a NULL pointer which reaches a return statement in a
> >>function which is marked as returns_nonnull. In that case there is no
> >>dereference. Presumably for that kind of scenario we'll just keep the
> >>builtin trap.
> >>
> >>Similarly, assume we extend this pass to detect out-of-bounds array
> >>indexing. It's fairly simple to do and has always been in my plan. In
> >>that case leaving in the array indexing won't necessarily generate a
> >>fault. For those presumably we'll just want the builtin_trap as well?
> >>
> >>Again, I don't mind inserting a *0, I just want to have a plan for the
> >>other undefined behaviours we currently detect and those which I plan on
> >>catching soon.
> >
> >The more general problem is that, with -fnon-call-exceptions, we really expect
> >a fully-fledged exception to be raised when something goes wrong. Inserting
> >__builtin_trap doesn't work because it's simply not equivalent to a throw. In
> >other words, if __builtin_throw would be inserted instead of __builtin_trap
> >with -fnon-call-exceptions, things would probably be acceptable as-is.
> Hmm, maybe that's a better soultion then. When non-call-exceptions
> is active, throw rather than trap.
But throw what? It is up to the runtimes of -fnon-call-exceptions languages
to decide if they actually want to throw or do something else in the signal
handlers, and what exactly to throw.
Jakub
^ permalink raw reply [flat|nested] 41+ messages in thread
* Re: [RFA][PATCH] Isolate erroneous paths optimization
2013-11-11 17:43 ` Jakub Jelinek
@ 2013-11-11 17:46 ` Ian Lance Taylor
2013-11-11 18:31 ` Eric Botcazou
1 sibling, 0 replies; 41+ messages in thread
From: Ian Lance Taylor @ 2013-11-11 17:46 UTC (permalink / raw)
To: Jakub Jelinek; +Cc: Jeff Law, Eric Botcazou, gcc-patches, Richard Biener
On Mon, Nov 11, 2013 at 8:27 AM, Jakub Jelinek <jakub@redhat.com> wrote:
> On Mon, Nov 11, 2013 at 09:24:27AM -0700, Jeff Law wrote:
>> On 11/11/13 02:33, Eric Botcazou wrote:
>> >>However, that brings up an couple interesting questions.
>> >>
>> >>Let's say we find a NULL pointer which reaches a return statement in a
>> >>function which is marked as returns_nonnull. In that case there is no
>> >>dereference. Presumably for that kind of scenario we'll just keep the
>> >>builtin trap.
>> >>
>> >>Similarly, assume we extend this pass to detect out-of-bounds array
>> >>indexing. It's fairly simple to do and has always been in my plan. In
>> >>that case leaving in the array indexing won't necessarily generate a
>> >>fault. For those presumably we'll just want the builtin_trap as well?
>> >>
>> >>Again, I don't mind inserting a *0, I just want to have a plan for the
>> >>other undefined behaviours we currently detect and those which I plan on
>> >>catching soon.
>> >
>> >The more general problem is that, with -fnon-call-exceptions, we really expect
>> >a fully-fledged exception to be raised when something goes wrong. Inserting
>> >__builtin_trap doesn't work because it's simply not equivalent to a throw. In
>> >other words, if __builtin_throw would be inserted instead of __builtin_trap
>> >with -fnon-call-exceptions, things would probably be acceptable as-is.
>> Hmm, maybe that's a better soultion then. When non-call-exceptions
>> is active, throw rather than trap.
>
> But throw what? It is up to the runtimes of -fnon-call-exceptions languages
> to decide if they actually want to throw or do something else in the signal
> handlers, and what exactly to throw.
Yes. At least for Go it would work fine to call a language defined
function for a nil pointer dereference (in fact I already have one you
could call), but then LTO might be an issue.
Ian
^ permalink raw reply [flat|nested] 41+ messages in thread
* Re: [RFA][PATCH] Isolate erroneous paths optimization
2013-11-11 17:43 ` Jakub Jelinek
2013-11-11 17:46 ` Ian Lance Taylor
@ 2013-11-11 18:31 ` Eric Botcazou
2013-11-11 19:24 ` Ian Lance Taylor
1 sibling, 1 reply; 41+ messages in thread
From: Eric Botcazou @ 2013-11-11 18:31 UTC (permalink / raw)
To: Jakub Jelinek; +Cc: gcc-patches, Jeff Law, Ian Lance Taylor, Richard Biener
> But throw what? It is up to the runtimes of -fnon-call-exceptions languages
> to decide if they actually want to throw or do something else in the signal
> handlers, and what exactly to throw.
Throw nothing per se, __builtin_throw would simply trap and ensure that the
exception thrown by the signal handlers can be handled properly, i.e. it would
be recognized by the exception machinery of the compiler as throwing.
--
Eric Botcazou
^ permalink raw reply [flat|nested] 41+ messages in thread
* Re: [RFA][PATCH] Isolate erroneous paths optimization
2013-11-11 18:31 ` Eric Botcazou
@ 2013-11-11 19:24 ` Ian Lance Taylor
2013-11-11 20:10 ` Eric Botcazou
0 siblings, 1 reply; 41+ messages in thread
From: Ian Lance Taylor @ 2013-11-11 19:24 UTC (permalink / raw)
To: Eric Botcazou; +Cc: Jakub Jelinek, gcc-patches, Jeff Law, Richard Biener
On Mon, Nov 11, 2013 at 9:41 AM, Eric Botcazou <ebotcazou@adacore.com> wrote:
>> But throw what? It is up to the runtimes of -fnon-call-exceptions languages
>> to decide if they actually want to throw or do something else in the signal
>> handlers, and what exactly to throw.
>
> Throw nothing per se, __builtin_throw would simply trap and ensure that the
> exception thrown by the signal handlers can be handled properly, i.e. it would
> be recognized by the exception machinery of the compiler as throwing.
Sorry, I don't understand what you are proposing.
Simply trapping doesn't tell you anything about caused the trap.
There are at least two distinct possibilities: NULL pointer
dereference and integer division by zero. There should be some way to
distinguish those two cases. It's reasonably easy to do so in a
signal handler. When should we do if the compiler generate a call to
__builtin_throw?
Since I probably misunderstand, let me ask it a different way. Let's
say there is code that the compiler can prove will dereference a NULL
pointer. What should the compiler generate for that case?
Ian
^ permalink raw reply [flat|nested] 41+ messages in thread
* Re: [RFA][PATCH] Isolate erroneous paths optimization
2013-11-11 19:24 ` Ian Lance Taylor
@ 2013-11-11 20:10 ` Eric Botcazou
2013-11-11 21:22 ` Ian Lance Taylor
0 siblings, 1 reply; 41+ messages in thread
From: Eric Botcazou @ 2013-11-11 20:10 UTC (permalink / raw)
To: Ian Lance Taylor; +Cc: gcc-patches, Jakub Jelinek, Jeff Law, Richard Biener
> Simply trapping doesn't tell you anything about caused the trap.
> There are at least two distinct possibilities: NULL pointer
> dereference and integer division by zero. There should be some way to
> distinguish those two cases. It's reasonably easy to do so in a
> signal handler. When should we do if the compiler generate a call to
> __builtin_throw?
You would use the fallback code in the signal handler, throwing the exception
used when you don't know the precise cause of the erroneous execution. Or
else we could pass an argument to __builtin_throw, but we would need some low-
level convention to pass it on to the handler.
--
Eric Botcazou
^ permalink raw reply [flat|nested] 41+ messages in thread
* Re: [RFA][PATCH] Isolate erroneous paths optimization
2013-11-11 20:10 ` Eric Botcazou
@ 2013-11-11 21:22 ` Ian Lance Taylor
0 siblings, 0 replies; 41+ messages in thread
From: Ian Lance Taylor @ 2013-11-11 21:22 UTC (permalink / raw)
To: Eric Botcazou; +Cc: gcc-patches, Jakub Jelinek, Jeff Law, Richard Biener
On Mon, Nov 11, 2013 at 10:55 AM, Eric Botcazou <ebotcazou@adacore.com> wrote:
>> Simply trapping doesn't tell you anything about caused the trap.
>> There are at least two distinct possibilities: NULL pointer
>> dereference and integer division by zero. There should be some way to
>> distinguish those two cases. It's reasonably easy to do so in a
>> signal handler. When should we do if the compiler generate a call to
>> __builtin_throw?
>
> You would use the fallback code in the signal handler, throwing the exception
> used when you don't know the precise cause of the erroneous execution. Or
> else we could pass an argument to __builtin_throw, but we would need some low-
> level convention to pass it on to the handler.
For Go that would be a (probably minor) degradation. Right now the
signal handler knows whether it is looking at a NULL pointer
dereference or a division by zero, because it gets a different signal.
On most modern systems you can be even more precise by looking at the
siginfo struct, and the Go runtime does do that.
But looking even lower-level, what we are talking about here is a
generic function that will be in libgcc, not a language-specific
function. That function could throw a general exception, but it can't
invoke any language-specific approach. And that general exception
would have to have some generic label. But I guess that the
language-specific personality function could recognize that generic
label and take some appropriate action.
Ian
^ permalink raw reply [flat|nested] 41+ messages in thread
* [PATCH] Isolate erroneous paths optimization -- preserve *0.
2013-11-11 9:33 ` Jeff Law
2013-11-11 9:50 ` Eric Botcazou
2013-11-11 12:55 ` Richard Biener
@ 2013-11-12 17:42 ` Jeff Law
2013-11-12 18:05 ` Marc Glisse
2013-11-14 10:25 ` H.J. Lu
2 siblings, 2 replies; 41+ messages in thread
From: Jeff Law @ 2013-11-12 17:42 UTC (permalink / raw)
To: gcc-patches
[-- Attachment #1: Type: text/plain, Size: 1357 bytes --]
On 11/10/13 20:11, Jeff Law wrote:
> OK. It sounds like there's a pretty general consensus that we ought ot
> go ahead and leave in a load/store of a NULL pointer. I'll go ahead and
> run with that. I'll probably just emit SSA_NAME = *0, unless someone
> thinks we ought ot distinguish between loads and stores, emitting
> SSA_NAME = *0 and *0 = 0 for the two cases respectively.
[ ... ]
Here's a patch which arranges to leave a null pointer dereferece in the
IL. For a memory load through a null pointer, we just leave the
statement as-is since the LHS is going to be a throw-away SSA_NAME. For
a store through a null pointer, we try to simplify the RHS when it's
trivially easy to do so (when the RHS is an integral type). This allows
DCE to sometimes do a better job if the RHS is something that was
computed on the isolated path. This could be easily extended to
floating types, vectors and structures if someone is interested. We
issue the builtin_trap after the null dereference.
For other cases (invalid NULL argument, invalid NULL return), we
continue to issue the builtin trap in the same manner we did before.
I've adjusted the existing tests and added a new one which verifies the
RHS of a store through a null pointer is simplified.
Bootstrapped and regression tested on x86_64-unknown-linux-gnu.
Installed on the trunk.
[-- Attachment #2: patch --]
[-- Type: text/plain, Size: 7770 bytes --]
* gimple-ssa-isolate-paths.c (check_loadstore): New function.
(insert_trap_and_remove_trailing_statements): New argument OP which
is the NULL pointer. Emit the trap after the load/store through
the NULL pointer. Simplify the RHS of a store through a NULL pointer
when trivial to do so.
(isolate_path): Corresponding changes.
(gimple_ssa_isolate_erroneous_path): Likewise.
* gcc.dg/tree-ssa/isolate-1.c: Update expected output.
* gcc.dg/tree-ssa/isolate-5.c: New test.
diff --git a/gcc/gimple-ssa-isolate-paths.c b/gcc/gimple-ssa-isolate-paths.c
index 983ed4d..1203cfc 100644
--- a/gcc/gimple-ssa-isolate-paths.c
+++ b/gcc/gimple-ssa-isolate-paths.c
@@ -39,17 +39,65 @@ along with GCC; see the file COPYING3. If not see
static bool cfg_altered;
-/* Insert a trap before SI and remove SI and all statements after SI. */
+/* 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))
+ return true;
+ return false;
+}
+
+/* Insert a trap after SI and remove SI and all statements after the trap. */
static void
-insert_trap_and_remove_trailing_statements (gimple_stmt_iterator *si_p)
+insert_trap_and_remove_trailing_statements (gimple_stmt_iterator *si_p, tree op)
{
- 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 (si_p, seq, GSI_SAME_STMT);
+ /* We want the NULL pointer dereference to actually occur so that
+ code that wishes to catch the signal can do so.
- /* Now delete all remaining statements in this block. */
+ If the dereference is a load, then there's nothing to do as the
+ LHS will be a throw-away SSA_NAME and the LHS is the NULL dereference.
+
+ If the dereference is a store and we can easily transform the RHS,
+ then simplify the RHS to enable more DCE. */
+ gimple stmt = gsi_stmt (*si_p);
+ if (walk_stmt_load_store_ops (stmt, (void *)op, NULL, check_loadstore)
+ && INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (stmt))))
+ {
+ /* We just need to turn the RHS into zero converted to the proper
+ type. */
+ tree type = TREE_TYPE (gimple_assign_lhs (stmt));
+ gimple_assign_set_rhs_code (stmt, INTEGER_CST);
+ gimple_assign_set_rhs1 (stmt, fold_convert (type, integer_zero_node));
+ update_stmt (stmt);
+ }
+
+ gimple new_stmt
+ = gimple_build_call (builtin_decl_explicit (BUILT_IN_TRAP), 0);
+ gimple_seq seq = NULL;
+ gimple_seq_add_stmt (&seq, new_stmt);
+
+ /* If we had a NULL pointer dereference, then we want to insert the
+ __builtin_trap after the statement, for the other cases we want
+ to insert before the statement. */
+ if (walk_stmt_load_store_ops (stmt, (void *)op,
+ check_loadstore,
+ check_loadstore))
+ gsi_insert_after (si_p, seq, GSI_NEW_STMT);
+ else
+ gsi_insert_before (si_p, seq, GSI_NEW_STMT);
+
+ /* The iterator points to the __builtin_trap. Advance the iterator
+ and delete everything else in the block. */
+ gsi_next (si_p);
for (; !gsi_end_p (*si_p);)
{
stmt = gsi_stmt (*si_p);
@@ -73,7 +121,8 @@ insert_trap_and_remove_trailing_statements (gimple_stmt_iterator *si_p)
Return BB'. */
basic_block
-isolate_path (basic_block bb, basic_block duplicate, edge e, gimple stmt)
+isolate_path (basic_block bb, basic_block duplicate,
+ edge e, gimple stmt, tree op)
{
gimple_stmt_iterator si, si2;
edge_iterator ei;
@@ -133,7 +182,7 @@ isolate_path (basic_block bb, basic_block duplicate, edge e, gimple stmt)
SI2 points to the duplicate of STMT in DUPLICATE. Insert a trap
before SI2 and remove SI2 and all trailing statements. */
if (!gsi_end_p (si2))
- insert_trap_and_remove_trailing_statements (&si2);
+ insert_trap_and_remove_trailing_statements (&si2, op);
return duplicate;
}
@@ -224,7 +273,7 @@ gimple_ssa_isolate_erroneous_paths (void)
if (infer_nonnull_range (use_stmt, lhs))
{
duplicate = isolate_path (bb, duplicate,
- e, use_stmt);
+ e, use_stmt, lhs);
/* When we remove an incoming edge, we need to
reprocess the Ith element. */
@@ -247,7 +296,8 @@ gimple_ssa_isolate_erroneous_paths (void)
where a non-NULL value is required. */
if (infer_nonnull_range (stmt, null_pointer_node))
{
- insert_trap_and_remove_trailing_statements (&si);
+ insert_trap_and_remove_trailing_statements (&si,
+ null_pointer_node);
/* And finally, remove all outgoing edges from BB. */
edge e;
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/isolate-1.c b/gcc/testsuite/gcc.dg/tree-ssa/isolate-1.c
index 6b779b4..33745ba 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/isolate-1.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/isolate-1.c
@@ -43,12 +43,14 @@ d_type (struct d_info *di)
return ret;
}
-/* We're testing two aspects of isolation here. First that isolation
+/* We're testing three 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. */
+ block, regardless of which comes first in the immediate use iterator
+ and finally that we set the RHS of the store to zero. */
/* { 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 "->type = 42" 1 "isolate-paths"} } */
+/* { dg-final { scan-tree-dump-times "->type = 0" 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-5.c b/gcc/testsuite/gcc.dg/tree-ssa/isolate-5.c
new file mode 100644
index 0000000..a70871e
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/isolate-5.c
@@ -0,0 +1,60 @@
+
+/* { 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);
+ foo (ret->type);
+ bar (ret->zzz);
+ 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.
+
+ We leave the 0->type in the IL, so expect to see ->type twice. */
+/* { dg-final { scan-tree-dump-times "__builtin_trap" 1 "isolate-paths"} } */
+/* { dg-final { scan-tree-dump-times "->type" 2 "isolate-paths"} } */
+/* { dg-final { scan-tree-dump-times "->zzz" 1 "isolate-paths"} } */
+/* { dg-final { cleanup-tree-dump "isolate-paths" } } */
+
+
+
+
+
^ permalink raw reply [flat|nested] 41+ messages in thread
* Re: [PATCH] Isolate erroneous paths optimization -- preserve *0.
2013-11-12 17:42 ` [PATCH] Isolate erroneous paths optimization -- preserve *0 Jeff Law
@ 2013-11-12 18:05 ` Marc Glisse
2013-11-12 18:17 ` Jeff Law
2013-11-12 19:41 ` Jeff Law
2013-11-14 10:25 ` H.J. Lu
1 sibling, 2 replies; 41+ messages in thread
From: Marc Glisse @ 2013-11-12 18:05 UTC (permalink / raw)
To: Jeff Law; +Cc: gcc-patches
On Tue, 12 Nov 2013, Jeff Law wrote:
> Here's a patch which arranges to leave a null pointer dereferece in the IL.
> For a memory load through a null pointer, we just leave the statement as-is
> since the LHS is going to be a throw-away SSA_NAME. For a store through a
> null pointer, we try to simplify the RHS when it's trivially easy to do so
> (when the RHS is an integral type). This allows DCE to sometimes do a better
> job if the RHS is something that was computed on the isolated path. This
> could be easily extended to floating types, vectors and structures if someone
> is interested. We issue the builtin_trap after the null dereference.
You didn't like Jakub's comment about __builtin_unreachable?
> - /* Now delete all remaining statements in this block. */
> + If the dereference is a load, then there's nothing to do as the
> + LHS will be a throw-away SSA_NAME and the LHS is the NULL dereference.
I assume the second LHS should be RHS. Don't you want to mark it somehow
so the next DCE doesn't remove it?
For PR59083, signals as yet another control flow mechanism are a pain...
--
Marc Glisse
^ permalink raw reply [flat|nested] 41+ messages in thread
* Re: [PATCH] Isolate erroneous paths optimization -- preserve *0.
2013-11-12 18:05 ` Marc Glisse
@ 2013-11-12 18:17 ` Jeff Law
2013-11-12 18:41 ` Marc Glisse
2013-11-12 19:41 ` Jeff Law
1 sibling, 1 reply; 41+ messages in thread
From: Jeff Law @ 2013-11-12 18:17 UTC (permalink / raw)
To: gcc-patches
On 11/12/13 10:14, Marc Glisse wrote:
> On Tue, 12 Nov 2013, Jeff Law wrote:
>
>> Here's a patch which arranges to leave a null pointer dereferece in
>> the IL. For a memory load through a null pointer, we just leave the
>> statement as-is since the LHS is going to be a throw-away SSA_NAME.
>> For a store through a null pointer, we try to simplify the RHS when
>> it's trivially easy to do so (when the RHS is an integral type). This
>> allows DCE to sometimes do a better job if the RHS is something that
>> was computed on the isolated path. This could be easily extended to
>> floating types, vectors and structures if someone is interested. We
>> issue the builtin_trap after the null dereference.
>
> You didn't like Jakub's comment about __builtin_unreachable?
No, it's certainly not appropriate for this optimization. The problem
with using builtin_unreachable is if you do reach that point, you fall
into an unrelated blob of code in the executable. That is a huge
security issue.
>
>> - /* Now delete all remaining statements in this block. */
>> + If the dereference is a load, then there's nothing to do as the
>> + LHS will be a throw-away SSA_NAME and the LHS is the NULL
>> dereference.
>
> I assume the second LHS should be RHS. Don't you want to mark it somehow
> so the next DCE doesn't remove it?
I'll fix the comment. Good point about DCE possibly removing the code.
I'll have to take a look at that.
>
> For PR59083, signals as yet another control flow mechanism are a pain...
Yup. The ability to catch the null dereference in a signal handler is
the primary motivation behind keeping the dereference in the IL.
jeff
^ permalink raw reply [flat|nested] 41+ messages in thread
* Re: [PATCH] Isolate erroneous paths optimization -- preserve *0.
2013-11-12 18:17 ` Jeff Law
@ 2013-11-12 18:41 ` Marc Glisse
2013-11-12 19:30 ` Marek Polacek
0 siblings, 1 reply; 41+ messages in thread
From: Marc Glisse @ 2013-11-12 18:41 UTC (permalink / raw)
To: Jeff Law; +Cc: gcc-patches
On Tue, 12 Nov 2013, Jeff Law wrote:
> On 11/12/13 10:14, Marc Glisse wrote:
>> You didn't like Jakub's comment about __builtin_unreachable?
> No, it's certainly not appropriate for this optimization. The problem with
> using builtin_unreachable is if you do reach that point, you fall into an
> unrelated blob of code in the executable. That is a huge security issue.
I guess this will end up as a flag and the debate will only be about the
default value of the flag?
(-fsanitize=Idontrememberwhat would already be such a flag ;-) but you may
prefer a more specific one)
Note that security is a concern for some applications, but for others it
is irrelevant and performance trumps it. I would even consider a flag that
turns abort, trap, etc into __builtin_unreachable.
Anyway, thanks for the optimization, I am only discussing the details
because I like it.
--
Marc Glisse
^ permalink raw reply [flat|nested] 41+ messages in thread
* Re: [PATCH] Isolate erroneous paths optimization -- preserve *0.
2013-11-12 18:41 ` Marc Glisse
@ 2013-11-12 19:30 ` Marek Polacek
0 siblings, 0 replies; 41+ messages in thread
From: Marek Polacek @ 2013-11-12 19:30 UTC (permalink / raw)
To: gcc-patches; +Cc: Jeff Law
On Tue, Nov 12, 2013 at 07:08:22PM +0100, Marc Glisse wrote:
> On Tue, 12 Nov 2013, Jeff Law wrote:
>
> >On 11/12/13 10:14, Marc Glisse wrote:
> >>You didn't like Jakub's comment about __builtin_unreachable?
> >No, it's certainly not appropriate for this optimization. The
> >problem with using builtin_unreachable is if you do reach that
> >point, you fall into an unrelated blob of code in the executable.
> >That is a huge security issue.
>
> I guess this will end up as a flag and the debate will only be about
> the default value of the flag?
>
> (-fsanitize=Idontrememberwhat would already be such a flag ;-) but
> you may prefer a more specific one)
Incidentally, I'll post a patch that implements -fsanitize=null
in a bit. Well, I yet have to write ChangeLogs, so don't hold your
breath ;).
-fsanitize=null will call an ubsan builtin if the control flow reaches
the point where we're loading from/storing to a NULL pointer. The maybe
bad thing is that these builtins are not noreturn, so after issuing
an error message, we happily dereference the NULL pointer (I did it
this way because it's what clang does). Changing these builtins to be
noreturn is possible, though not as easy as it seems.
Marek
^ permalink raw reply [flat|nested] 41+ messages in thread
* Re: [PATCH] Isolate erroneous paths optimization -- preserve *0.
2013-11-12 18:05 ` Marc Glisse
2013-11-12 18:17 ` Jeff Law
@ 2013-11-12 19:41 ` Jeff Law
1 sibling, 0 replies; 41+ messages in thread
From: Jeff Law @ 2013-11-12 19:41 UTC (permalink / raw)
To: gcc-patches
On 11/12/13 10:14, Marc Glisse wrote:
>
> I assume the second LHS should be RHS. Don't you want to mark it somehow
> so the next DCE doesn't remove it?
Sigh, yes DCE is removing the load.
That can be fixed by just marking the MEM_REF as volatile and updating
the statement. It's a pretty trivial change.
Jeff
^ permalink raw reply [flat|nested] 41+ messages in thread
* Re: [RFA][PATCH] Isolate erroneous paths optimization
2013-11-05 2:03 ` Jeff Law
2013-11-05 11:59 ` Richard Biener
2013-11-06 5:42 ` Ian Lance Taylor
@ 2013-11-13 18:13 ` Ulrich Weigand
2 siblings, 0 replies; 41+ messages in thread
From: Ulrich Weigand @ 2013-11-13 18:13 UTC (permalink / raw)
To: Jeff Law; +Cc: Richard Biener, gcc-patches
Jeff Law wrote:
> * 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.
This causes compiler segfaults for me when building Python 2.7.5.
See http://gcc.gnu.org/bugzilla/show_bug.cgi?id=59119
for a reduced test case ...
Bye,
Ulrich
--
Dr. Ulrich Weigand
GNU/Linux compilers and toolchain
Ulrich.Weigand@de.ibm.com
^ permalink raw reply [flat|nested] 41+ messages in thread
* Re: [PATCH] Isolate erroneous paths optimization -- preserve *0.
2013-11-12 17:42 ` [PATCH] Isolate erroneous paths optimization -- preserve *0 Jeff Law
2013-11-12 18:05 ` Marc Glisse
@ 2013-11-14 10:25 ` H.J. Lu
1 sibling, 0 replies; 41+ messages in thread
From: H.J. Lu @ 2013-11-14 10:25 UTC (permalink / raw)
To: Jeff Law; +Cc: GCC Patches
On Tue, Nov 12, 2013 at 8:42 AM, Jeff Law <law@redhat.com> wrote:
> On 11/10/13 20:11, Jeff Law wrote:
>>
>> OK. It sounds like there's a pretty general consensus that we ought ot
>> go ahead and leave in a load/store of a NULL pointer. I'll go ahead and
>> run with that. I'll probably just emit SSA_NAME = *0, unless someone
>> thinks we ought ot distinguish between loads and stores, emitting
>> SSA_NAME = *0 and *0 = 0 for the two cases respectively.
>
> [ ... ]
> Here's a patch which arranges to leave a null pointer dereferece in the IL.
> For a memory load through a null pointer, we just leave the statement as-is
> since the LHS is going to be a throw-away SSA_NAME. For a store through a
> null pointer, we try to simplify the RHS when it's trivially easy to do so
> (when the RHS is an integral type). This allows DCE to sometimes do a
> better job if the RHS is something that was computed on the isolated path.
> This could be easily extended to floating types, vectors and structures if
> someone is interested. We issue the builtin_trap after the null
> dereference.
>
> For other cases (invalid NULL argument, invalid NULL return), we continue to
> issue the builtin trap in the same manner we did before.
>
> I've adjusted the existing tests and added a new one which verifies the RHS
> of a store through a null pointer is simplified.
>
> Bootstrapped and regression tested on x86_64-unknown-linux-gnu. Installed on
> the trunk.
>
>
>
> * gimple-ssa-isolate-paths.c (check_loadstore): New function.
> (insert_trap_and_remove_trailing_statements): New argument OP which
> is the NULL pointer. Emit the trap after the load/store through
> the NULL pointer. Simplify the RHS of a store through a NULL
> pointer
> when trivial to do so.
> (isolate_path): Corresponding changes.
> (gimple_ssa_isolate_erroneous_path): Likewise.
>
This caused:
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=59127
--
H.J.
^ permalink raw reply [flat|nested] 41+ messages in thread
end of thread, other threads:[~2013-11-14 9:41 UTC | newest]
Thread overview: 41+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2013-10-31 8:34 [RFA][PATCH] Isolate erroneous paths optimization Jeff Law
2013-11-04 13:20 ` Richard Biener
2013-11-05 2:03 ` Jeff Law
2013-11-05 11:59 ` Richard Biener
2013-11-05 18:45 ` Jeff Law
2013-11-05 19:56 ` Jeff Law
2013-11-06 5:42 ` Ian Lance Taylor
2013-11-06 6:11 ` Jeff Law
2013-11-06 7:05 ` Marc Glisse
2013-11-06 14:34 ` Ian Lance Taylor
2013-11-06 14:41 ` Richard Biener
2013-11-06 15:15 ` Ian Lance Taylor
2013-11-06 15:23 ` Richard Biener
2013-11-06 15:24 ` Ian Lance Taylor
2013-11-06 15:27 ` Richard Biener
2013-11-06 15:59 ` Jakub Jelinek
2013-11-06 17:01 ` Jeff Law
2013-11-06 16:36 ` Jakub Jelinek
2013-11-06 16:26 ` Jeff Law
2013-11-06 16:20 ` Jeff Law
2013-11-10 13:06 ` Eric Botcazou
2013-11-11 9:33 ` Jeff Law
2013-11-11 9:50 ` Eric Botcazou
2013-11-11 17:41 ` Jeff Law
2013-11-11 17:43 ` Jakub Jelinek
2013-11-11 17:46 ` Ian Lance Taylor
2013-11-11 18:31 ` Eric Botcazou
2013-11-11 19:24 ` Ian Lance Taylor
2013-11-11 20:10 ` Eric Botcazou
2013-11-11 21:22 ` Ian Lance Taylor
2013-11-11 12:55 ` Richard Biener
2013-11-11 17:07 ` Jeff Law
2013-11-12 17:42 ` [PATCH] Isolate erroneous paths optimization -- preserve *0 Jeff Law
2013-11-12 18:05 ` Marc Glisse
2013-11-12 18:17 ` Jeff Law
2013-11-12 18:41 ` Marc Glisse
2013-11-12 19:30 ` Marek Polacek
2013-11-12 19:41 ` Jeff Law
2013-11-14 10:25 ` H.J. Lu
2013-11-06 16:15 ` [RFA][PATCH] Isolate erroneous paths optimization Jeff Law
2013-11-13 18:13 ` Ulrich Weigand
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).