RFA: New pass to delete unexecutable paths in the CFG

RFA: New pass to delete unexecutable paths in the CFG

[Jeff Law]

[-- Attachment #1: Type: text/plain, Size: 2850 bytes --]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1


[ Working virtually from Hawaii tonight...  :-) ]

So while working on warnings for NULL pointer dereferences and seeing
how many explicit & implicit NULL pointer dereferences are left in the
statement stream due to various VEC & other oddities, I realized we
can actually optimize this code.

First, it's perfectly fine to have a NULL pointer dereference in a
program as long as that code is never executed.  Once the code is
executed, we've entered the realm of undefined behavior.

Thus in a conforming program we can safely assume that a provable NULL
pointer dereference can never be executed at runtime.  This implies
there is a path through the CFG that is unexecutable.

If the path is unexecutable, then we would really like to identify the
path and remove it from the CFG.  This saves space, it also
potentially eliminates a runtime comparison and the simplifications
can lead to secondary optimizations such as more const/copy
propagation, block merging, etc.

This pass detects NULL pointer dereferences, both those explicit in
the IL and those implied by PHI nodes.  It then removes the edge upon
which those dereferences are control dependent.  This makes explicit
NULL pointer dereferences unreachable in the CFG and eliminates the
NULL PHI argument in the implicit dereferences.

You might legitimately wonder how often this triggers.   A GCC 4.6.0
checking-enabled compiler sees a .64% codesize improvement from this
optimization.  That's an awful lot of unexecutable code.  The NULL
references come from the VEC implementation and a variety of other
sources.

- From a runtime standpoint using that same gcc-4.6.0 compiler to
compile a bunch of .i files under the watchful eye of valgrind we see
a .1% reduction in total branches executed.  Furthermore, for every
runtime branch we eliminate, we eliminate 2.25 other insns.  So we're
eliminating the cc0 setter as one would expect, but we're also able to
remove other code, so we're getting some secondary benefits as well.

Bootstrapped on x86_64-unknown-linux-gnu.  An earlier version has
regression tested, but this version's regression testing hasn't
completed yet.  OK for trunk assuming no failures in the regression
test?  (nothing like sliding in at the last minute).




-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iQEcBAEBAgAGBQJOt6r1AAoJEBRtltQi2kC7tmQIAL4LR/Kpk1wC359nziShuhTT
sYiyFdrKbJAHQ5t25257axTeuQQ3Y8YCLacoXONqafhPbn6fg5RdBuvagFxUoRNx
tYTYO/bSZzU4vEIKsktguYwdd1XdekFcJG1enumxZf3wb0QBKuQ4xCyXMVzvgqKs
kVRQnrUCjSbnxRwSALCVjrrwnmbMANB/rOlG6UZHru6cgE/pyHEzBIxOBKE2V+v+
UH8YTsmO+P+dJ1K0SLP1vu+T4v+XxFArX1LLu5pRUZ9Wnf4TFtyxvi/iUNndbHJ3
YPuAumYRYfNkFff1ohjamp7mLSkUW/bfRoYjvZJQQHChQ4yUtKKgx/3pctlfoiQ=
=CQl5
-----END PGP SIGNATURE-----

[-- Attachment #2: P --]
[-- Type: text/plain, Size: 28840 bytes --]

	* tree-ssa-dce.c: Include control-dependence.h.
	(EXECUTE_IF_CONTROL_DEPENDENT): Moved from here to control-dependence.c
	(set_control_dependence_map_bit, find_pdom): Likewise.
	(clear_control_dependence_map_bit, find_control_dependence): 
	(find_all_control_dependences): Likewise.
	(mark_control_dependence_edges_necessary): Tweak for argument
	order chagne in EXECUTE_IF_CONTROL_DEPENDENT.
	(perform_tree_ssa_dce): Pass in the control dependence map.
	* control-dependence.c:  New file.
	* control-dependence.h: New file.
	* Makefile.in (OBJS): Add control-dependence.o and tree-ssa-unexec.o
	(control-dependence.o): Add dependences.
	(tree-ssa-unexec.o): Likewise.
	(tree-ssa-dce.o): Depends on control-dependence.h.
	* passes.c (init_optimization_passes): Run tree-ssa-unexec.
	* tree-ssa-unexec.c: New file.
	* tree-pass.h (pass_remove_unexecutable_paths): Declare.
	* opts.c (default_options): Enable executable path elimination at -O1.
	* timevar.def (TV_TREE_UNEXEC_PATHS): New timevar.
	* common.opt (-ftree-unexec-paths): New option.

	* gcc.dg/tree-ssa/20030711-3.c: Use -fno-tree-unexec-paths.

Index: gcc/tree-pass.h
===================================================================
*** gcc/tree-pass.h	(revision 180836)
--- gcc/tree-pass.h	(working copy)
*************** extern struct gimple_opt_pass pass_sink_
*** 437,442 ****
--- 437,443 ----
  extern struct gimple_opt_pass pass_fre;
  extern struct gimple_opt_pass pass_check_data_deps;
  extern struct gimple_opt_pass pass_copy_prop;
+ extern struct gimple_opt_pass pass_remove_unexecutable_paths;
  extern struct gimple_opt_pass pass_vrp;
  extern struct gimple_opt_pass pass_uncprop;
  extern struct gimple_opt_pass pass_return_slot;
Index: gcc/testsuite/gcc.dg/tree-ssa/20030711-3.c
===================================================================
*** gcc/testsuite/gcc.dg/tree-ssa/20030711-3.c	(revision 180836)
--- gcc/testsuite/gcc.dg/tree-ssa/20030711-3.c	(working copy)
***************
*** 1,5 ****
  /* { dg-do compile } */
! /* { dg-options "-O1 -fdump-tree-dom2" } */
    
  
  struct rtx_def;
--- 1,5 ----
  /* { dg-do compile } */
! /* { dg-options "-O1 -fdump-tree-dom2" -fno-tree-unexec-paths} */
    
  
  struct rtx_def;
Index: gcc/opts.c
===================================================================
*** gcc/opts.c	(revision 180836)
--- gcc/opts.c	(working copy)
*************** static const struct default_options defa
*** 450,455 ****
--- 450,456 ----
      { 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_ftree_unexec_paths, NULL, 1 },
  
      /* -O2 optimizations.  */
      { OPT_LEVELS_2_PLUS, OPT_finline_small_functions, NULL, 1 },
Index: gcc/timevar.def
===================================================================
*** gcc/timevar.def	(revision 180836)
--- gcc/timevar.def	(working copy)
*************** DEFTIMEVAR (TV_TREE_SSA_INCREMENTAL  , "
*** 139,144 ****
--- 139,145 ----
  DEFTIMEVAR (TV_TREE_OPS	             , "tree operand scan")
  DEFTIMEVAR (TV_TREE_SSA_DOMINATOR_OPTS   , "dominator optimization")
  DEFTIMEVAR (TV_TREE_SRA              , "tree SRA")
+ DEFTIMEVAR (TV_TREE_UNEXEC_PATHS     , "tree SSA unexec 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")
Index: gcc/common.opt
===================================================================
*** gcc/common.opt	(revision 180836)
--- gcc/common.opt	(working copy)
*************** ftree-dse
*** 1962,1967 ****
--- 1962,1972 ----
  Common Report Var(flag_tree_dse) Optimization
  Enable dead store elimination
  
+ ftree-unexec-paths
+ Common Report Var(flag_tree_unexec_paths) Optimization
+ Detect paths which can never be executed in a conforming program and remove
+ them.  For example, a path leading to a dereference of a NULL pointer may be removed.
+ 
  ftree-forwprop
  Common Report Var(flag_tree_forwprop) Init(1) Optimization
  Enable forward propagation on trees
Index: gcc/tree-ssa-dce.c
===================================================================
*** gcc/tree-ssa-dce.c	(revision 180836)
--- gcc/tree-ssa-dce.c	(working copy)
*************** along with GCC; see the file COPYING3.  
*** 60,65 ****
--- 60,66 ----
  #include "flags.h"
  #include "cfgloop.h"
  #include "tree-scalar-evolution.h"
+ #include "control-dependence.h"
  
  static struct stmt_stats
  {
*************** static sbitmap visited_control_parents;
*** 104,200 ****
     to be recomputed.  */
  static bool cfg_altered;
  
- /* Execute code that follows the macro for each edge (given number
-    EDGE_NUMBER within the CODE) for which the block with index N is
-    control dependent.  */
- #define EXECUTE_IF_CONTROL_DEPENDENT(BI, N, EDGE_NUMBER)	\
-   EXECUTE_IF_SET_IN_BITMAP (control_dependence_map[(N)], 0,	\
- 			    (EDGE_NUMBER), (BI))
- 
- 
- /* Indicate block BB is control dependent on an edge with index EDGE_INDEX.  */
- static inline void
- set_control_dependence_map_bit (basic_block bb, int edge_index)
- {
-   if (bb == ENTRY_BLOCK_PTR)
-     return;
-   gcc_assert (bb != EXIT_BLOCK_PTR);
-   bitmap_set_bit (control_dependence_map[bb->index], edge_index);
- }
- 
- /* Clear all control dependences for block BB.  */
- static inline void
- clear_control_dependence_bitmap (basic_block bb)
- {
-   bitmap_clear (control_dependence_map[bb->index]);
- }
- 
- 
- /* Find the immediate postdominator PDOM of the specified basic block BLOCK.
-    This function is necessary because some blocks have negative numbers.  */
- 
- static inline basic_block
- find_pdom (basic_block block)
- {
-   gcc_assert (block != ENTRY_BLOCK_PTR);
- 
-   if (block == EXIT_BLOCK_PTR)
-     return EXIT_BLOCK_PTR;
-   else
-     {
-       basic_block bb = get_immediate_dominator (CDI_POST_DOMINATORS, block);
-       if (! bb)
- 	return EXIT_BLOCK_PTR;
-       return bb;
-     }
- }
- 
- 
- /* Determine all blocks' control dependences on the given edge with edge_list
-    EL index EDGE_INDEX, ala Morgan, Section 3.6.  */
- 
- static void
- find_control_dependence (struct edge_list *el, int edge_index)
- {
-   basic_block current_block;
-   basic_block ending_block;
- 
-   gcc_assert (INDEX_EDGE_PRED_BB (el, edge_index) != EXIT_BLOCK_PTR);
- 
-   if (INDEX_EDGE_PRED_BB (el, edge_index) == ENTRY_BLOCK_PTR)
-     ending_block = single_succ (ENTRY_BLOCK_PTR);
-   else
-     ending_block = find_pdom (INDEX_EDGE_PRED_BB (el, edge_index));
- 
-   for (current_block = INDEX_EDGE_SUCC_BB (el, edge_index);
-        current_block != ending_block && current_block != EXIT_BLOCK_PTR;
-        current_block = find_pdom (current_block))
-     {
-       edge e = INDEX_EDGE (el, edge_index);
- 
-       /* For abnormal edges, we don't make current_block control
- 	 dependent because instructions that throw are always necessary
- 	 anyway.  */
-       if (e->flags & EDGE_ABNORMAL)
- 	continue;
- 
-       set_control_dependence_map_bit (current_block, edge_index);
-     }
- }
- 
- 
- /* Record all blocks' control dependences on all edges in the edge
-    list EL, ala Morgan, Section 3.6.  */
- 
- static void
- find_all_control_dependences (struct edge_list *el)
- {
-   int i;
- 
-   for (i = 0; i < NUM_EDGES (el); ++i)
-     find_control_dependence (el, i);
- }
- 
  /* If STMT is not already marked necessary, mark it, and add it to the
     worklist if ADD_TO_WORKLIST is true.  */
  
--- 105,110 ----
*************** mark_control_dependent_edges_necessary (
*** 408,414 ****
    if (bb == ENTRY_BLOCK_PTR)
      return;
  
!   EXECUTE_IF_CONTROL_DEPENDENT (bi, bb->index, edge_number)
      {
        basic_block cd_bb = INDEX_EDGE_PRED_BB (el, edge_number);
  
--- 318,325 ----
    if (bb == ENTRY_BLOCK_PTR)
      return;
  
!   EXECUTE_IF_CONTROL_DEPENDENT (control_dependence_map, bb->index,
! 				edge_number, bi)
      {
        basic_block cd_bb = INDEX_EDGE_PRED_BB (el, edge_number);
  
*************** perform_tree_ssa_dce (bool aggressive)
*** 1524,1530 ****
        timevar_push (TV_CONTROL_DEPENDENCES);
        calculate_dominance_info (CDI_POST_DOMINATORS);
        el = create_edge_list ();
!       find_all_control_dependences (el);
        timevar_pop (TV_CONTROL_DEPENDENCES);
  
        visited_control_parents = sbitmap_alloc (last_basic_block);
--- 1435,1441 ----
        timevar_push (TV_CONTROL_DEPENDENCES);
        calculate_dominance_info (CDI_POST_DOMINATORS);
        el = create_edge_list ();
!       find_all_control_dependences (el, control_dependence_map);
        timevar_pop (TV_CONTROL_DEPENDENCES);
  
        visited_control_parents = sbitmap_alloc (last_basic_block);
Index: gcc/Makefile.in
===================================================================
*** gcc/Makefile.in	(revision 180836)
--- gcc/Makefile.in	(working copy)
*************** OBJS = \
*** 1180,1185 ****
--- 1180,1186 ----
  	combine.o \
  	combine-stack-adj.o \
  	compare-elim.o \
+ 	control-dependence.o \
  	convert.o \
  	coverage.o \
  	cppbuiltin.o \
*************** OBJS = \
*** 1419,1424 ****
--- 1420,1426 ----
  	tree-ssa-threadedge.o \
  	tree-ssa-threadupdate.o \
  	tree-ssa-uncprop.o \
+ 	tree-ssa-unexec.o \
  	tree-ssa-uninit.o \
  	tree-ssa.o \
  	tree-ssanames.o \
*************** ggc-none.o: ggc-none.c $(CONFIG_H) $(SYS
*** 2175,2180 ****
--- 2177,2185 ----
  stringpool.o: stringpool.c $(CONFIG_H) $(SYSTEM_H) coretypes.h \
  	$(TREE_H) $(GGC_H) $(GGC_INTERNAL_H) gt-stringpool.h $(CPPLIB_H) $(SYMTAB_H)
  
+ control-dependence.o : control-dependence.c $(CONFIG_H) $(SYSTEM_H) \
+ 	coretypes.h $(BASIC_BLOCK_H) $(BITMAP_H) control-dependence.h
+ 
  convert.o: convert.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(TREE_H) \
     $(FLAGS_H) convert.h $(DIAGNOSTIC_CORE_H) langhooks.h
  
*************** tree-ssa-dce.o : tree-ssa-dce.c $(CONFIG
*** 3052,3058 ****
      $(TREE_FLOW_H) $(DIAGNOSTIC_H) $(TIMEVAR_H) $(TM_H) \
      coretypes.h $(TREE_DUMP_H) $(TREE_PASS_H) $(FLAGS_H) $(BASIC_BLOCK_H) \
      $(GGC_H) $(GIMPLE_H) $(CFGLOOP_H) $(SCEV_H) tree-pretty-print.h \
!     gimple-pretty-print.h
  tree-call-cdce.o : tree-call-cdce.c $(CONFIG_H) $(SYSTEM_H) $(TREE_H) \
      $(TREE_FLOW_H) $(DIAGNOSTIC_H) $(TIMEVAR_H) $(TM_H) \
      coretypes.h $(TREE_DUMP_H) $(TREE_PASS_H) $(FLAGS_H) $(BASIC_BLOCK_H) \
--- 3057,3068 ----
      $(TREE_FLOW_H) $(DIAGNOSTIC_H) $(TIMEVAR_H) $(TM_H) \
      coretypes.h $(TREE_DUMP_H) $(TREE_PASS_H) $(FLAGS_H) $(BASIC_BLOCK_H) \
      $(GGC_H) $(GIMPLE_H) $(CFGLOOP_H) $(SCEV_H) tree-pretty-print.h \
!     gimple-pretty-print.h control-dependence.h
! tree-ssa-unexec.o : tree-ssa-unexec.c $(CONFIG_H) $(SYSTEM_H) $(TREE_H) \
!     $(TREE_FLOW_H) $(DIAGNOSTIC_H) $(TIMEVAR_H) $(TM_H) \
!     coretypes.h $(TREE_DUMP_H) $(TREE_PASS_H) $(FLAGS_H) $(BASIC_BLOCK_H) \
!     $(GGC_H) $(GIMPLE_H) $(CFGLOOP_H) $(SCEV_H) tree-pretty-print.h \
!     gimple-pretty-print.h control-dependence.h
  tree-call-cdce.o : tree-call-cdce.c $(CONFIG_H) $(SYSTEM_H) $(TREE_H) \
      $(TREE_FLOW_H) $(DIAGNOSTIC_H) $(TIMEVAR_H) $(TM_H) \
      coretypes.h $(TREE_DUMP_H) $(TREE_PASS_H) $(FLAGS_H) $(BASIC_BLOCK_H) \
Index: gcc/passes.c
===================================================================
*** gcc/passes.c	(revision 180836)
--- gcc/passes.c	(working copy)
*************** init_optimization_passes (void)
*** 1315,1320 ****
--- 1315,1328 ----
  	 only examines PHIs to discover const/copy propagation
  	 opportunities.  */
        NEXT_PASS (pass_phi_only_cprop);
+       /* At this point the majority of const/copy propagations are
+ 	 exposed, so go ahead and identify paths that can never be
+ 	 executed in a conforming program and eliminate them.
+ 
+ 	 This will simplify the CFG and may expose further optimizations
+ 	 which will hopefully be picked up via PRE and the last dominator
+ 	 pass.  */
+       NEXT_PASS (pass_remove_unexecutable_paths);
        NEXT_PASS (pass_dse);
        NEXT_PASS (pass_reassoc);
        NEXT_PASS (pass_dce);
*** /dev/null	Wed Nov  2 07:09:57 2011
--- control-dependence.c	Thu Nov  3 21:35:57 2011
***************
*** 0 ****
--- 1,107 ----
+ /* Control Dependence
+    Copyright (C) 2011
+    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 "basic-block.h"
+ #include "bitmap.h"
+ #include "control-dependence.h"
+ 
+ 
+ /* Indicate block BB is control dependent on an edge with index EDGE_INDEX.  */
+ static inline void 
+ set_control_dependence_map_bit (basic_block bb, int edge_index, bitmap *cd_map)
+ {
+   if (bb == ENTRY_BLOCK_PTR)
+     return;
+   gcc_assert (bb != EXIT_BLOCK_PTR);
+   bitmap_set_bit (cd_map[bb->index], edge_index);
+ }
+ 
+ /* Find the immediate postdominator PDOM of the specified basic block BLOCK.
+    This function is necessary because some blocks have negative numbers.  */
+ 
+ static inline basic_block
+ find_pdom (basic_block block)
+ {
+   gcc_assert (block != ENTRY_BLOCK_PTR);
+ 
+   if (block == EXIT_BLOCK_PTR)
+     return EXIT_BLOCK_PTR;
+   else
+     {
+       basic_block bb = get_immediate_dominator (CDI_POST_DOMINATORS, block);
+       if (! bb)
+ 	return EXIT_BLOCK_PTR;
+       return bb;
+     }
+ }
+ 
+ 
+ /* Determine all blocks' control dependences on the given edge with edge_list
+    EL index EDGE_INDEX, ala Morgan, Section 3.6.  */
+ 
+ static void
+ find_control_dependence (struct edge_list *el, int edge_index, bitmap *cd_map)
+ {
+   basic_block current_block;
+   basic_block ending_block;
+ 
+   gcc_assert (INDEX_EDGE_PRED_BB (el, edge_index) != EXIT_BLOCK_PTR);
+ 
+   if (INDEX_EDGE_PRED_BB (el, edge_index) == ENTRY_BLOCK_PTR)
+     ending_block = single_succ (ENTRY_BLOCK_PTR);
+   else
+     ending_block = find_pdom (INDEX_EDGE_PRED_BB (el, edge_index));
+ 
+   for (current_block = INDEX_EDGE_SUCC_BB (el, edge_index);
+        current_block != ending_block && current_block != EXIT_BLOCK_PTR;
+        current_block = find_pdom (current_block))
+     {
+       edge e = INDEX_EDGE (el, edge_index);
+ 
+       /* For abnormal edges, we don't make current_block control
+ 	 dependent because instructions that throw are always necessary
+ 	 anyway.  */
+       if (e->flags & EDGE_ABNORMAL)
+ 	continue;
+ 
+       set_control_dependence_map_bit (current_block, edge_index, cd_map);
+     }
+ }
+ 
+ 
+ /* Record all blocks' control dependences on all edges in the edge
+    list EL, ala Morgan, Section 3.6. 
+ 
+    The results are recorded into the CD_MAP array.  The array is indexed
+    by basic block numbers.  Each element in the array is a bitmap of edge
+    indices the given block is control dependent upon.   */
+ 
+ void
+ find_all_control_dependences (struct edge_list *el, bitmap *cd_map)
+ {
+   int i;
+ 
+   for (i = 0; i < NUM_EDGES (el); ++i)
+     find_control_dependence (el, i, cd_map);
+ }
+ 
*** /dev/null	Wed Nov  2 07:09:57 2011
--- control-dependence.h	Thu Nov  3 22:00:22 2011
***************
*** 0 ****
--- 1,36 ----
+ /* Control Dependence
+    Copyright (C) 2011
+    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/>.  */
+ 
+ /* Record all blocks' control dependences on all edges in the edge
+    list EL, ala Morgan, Section 3.6. 
+ 
+    The results are recorded into the CD_MAP array.  The array is indexed
+    by basic block numbers.  Each element in the array is a bitmap of edge
+    indices the given block is control dependent upon.   */
+ 
+ void find_all_control_dependences (struct edge_list *, bitmap *);
+ 
+ /* Execute code that follows the macro for each edge (given number
+    EDGE_NUMBER within the CODE) for which the block with index N is
+    control dependent.  */
+ #define EXECUTE_IF_CONTROL_DEPENDENT(MAP, N, EDGE_NUMBER, BI)	\
+   EXECUTE_IF_SET_IN_BITMAP ((MAP)[(N)], 0, (EDGE_NUMBER), (BI))
+ 
+ 
*** /dev/null	Wed Nov  2 07:09:57 2011
--- tree-ssa-unexec.c	Mon Nov  7 00:20:07 2011
***************
*** 0 ****
--- 1,357 ----
+ /* Detect paths through the CFG which can never be executed in a conforming
+    program and eliminate them.
+ 
+    Copyright (C) 2011
+    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 "tm.h"
+ #include "tree.h"
+ #include "flags.h"
+ #include "tm_p.h"
+ #include "basic-block.h"
+ #include "output.h"
+ #include "function.h"
+ #include "tree-pretty-print.h"
+ #include "gimple-pretty-print.h"
+ #include "timevar.h"
+ #include "tree-dump.h"
+ #include "tree-flow.h"
+ #include "tree-pass.h"
+ #include "tree-ssa-propagate.h"
+ #include "langhooks.h"
+ #include "cfgloop.h"
+ #include "control-dependence.h"
+ 
+ 
+ /* Note if we've optimized anything and thus want to run CFG cleanups
+    when this pass is complete.  Obviously if this pass does nothing, then
+    CFG cleanups would be a waste of time.  */
+ bool cfg_altered;
+ 
+ /* Remove the GIMPLE_COND statement and the outgoing edge E from BB. 
+    Return true if E was removed, false otherwise.  */
+ 
+ static bool
+ remove_cond_and_edge (basic_block bb, edge e)
+ {
+   gimple_stmt_iterator gsi = gsi_last_bb (bb);
+   edge_iterator ei;
+   gimple stmt;
+   edge tmp_e;
+ 
+   /* I can't think of a case were an empty block would have more
+      than one successor.  Thus, there shouldn't be any way for an empty
+      block to control the execution of a later block and we shouldn't
+      ever get here in that state.  */
+   gcc_assert (!gsi_end_p (gsi));
+ 
+   /* We only handle fixing GIMPLE_COND statements.  We could
+      possibly handle GIMPLE_SWITCH with more work.  */
+   stmt = gsi_stmt (gsi);
+   if (gimple_code (stmt) != GIMPLE_COND)
+     return false;
+ 	      
+    /* Remove the GIMPLE_COND from CD_BB.  */
+    gsi_remove (&gsi, true);
+ 
+    /* Now fixup the outgoing edges.  One will be removed
+       (INDEX_EDGE (el, j)).  The other needs the TRUE/FALSE
+       flags cleared and the FALLTHRU flag set.  */
+    for (ei = ei_start (bb->succs); (tmp_e = ei_safe_edge (ei)); )
+     {
+       if (e == tmp_e)
+ 	{
+ 	  remove_edge (e);
+ 	  cfg_altered = true;
+ 	}
+       else
+ 	{
+ 	  tmp_e->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
+ 	  tmp_e->flags |= EDGE_FALLTHRU;
+ 		  
+ 	  ei_next (&ei);
+ 	}
+     }
+   return true;
+ }
+ 
+ /* 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.  Thus, we can conclude the block containing
+    the offending statement is unreachable and optimize accordingly.
+ 
+    We detect explicit NULL pointer dereferences as well as those implied
+    by a PHI argument having a NULL value and when reached from the appropriate
+    edge the NULL value flowing to a dereference.
+ 
+    In the former case, we want to remove the control dependent edge that
+    eventually leads us to the explicit dereference.  That will make the
+    block containing the explicit dereference unreachable in the CFG.
+ 
+    For PHIs, if the NULL argument's edge is not critical, then we can
+    perform the same optimization for the EDGE's source.    If the edge
+    is critical, then we can just remove the offending edge and conditional.
+ 
+    We could also detect uses of uninitialized variables and treat them in
+    a similar manner.  */
+ 
+ static unsigned int
+ execute_remove_unexecutable_paths (void)
+ {
+   basic_block bb;
+   bitmap unexecutable_blocks = BITMAP_ALLOC (NULL);
+ 
+   /* Mark blocks where statements explicitly dereferencing a NULL
+      pointer are found.  When NULL PHI arguments unconditionally
+      flow to a dereference, mark edge->src if the edge is not critical.
+      If the edge is critical, just remove it.  */
+   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. 
+ 
+ 	 Basically we're looking to see if an incoming edge to BB is
+ 	 unexecutable and optimizing if so.  */
+       for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
+ 	{
+ 	  gimple phi = gsi_stmt (si);
+ 	  tree lhs = gimple_phi_result (phi);
+ 	  int removed_edge = 0;
+ 	  unsigned int i;
+ 
+ 	  /* 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.  */
+ 	  for (i = 0; i < gimple_phi_num_args (phi); i = i + 1 - removed_edge)
+ 	    {
+ 	      tree op = gimple_phi_arg_def (phi, i);
+ 
+ 	      removed_edge = 0;
+ 	      if (operand_equal_p (op, integer_zero_node, 0))
+ 		{
+ 		  gimple use_stmt;
+ 		  imm_use_iterator iter;
+ 
+ 		  /* 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)
+ 		    {
+ 		      unsigned int j;
+ 
+ 		      /* We only care about uses in BB which are assignements
+  			 with memory operands.  */
+ 		      if (gimple_bb (use_stmt) != bb
+ 			  || !gimple_has_mem_ops (use_stmt)
+ 			  || gimple_code (use_stmt) != GIMPLE_ASSIGN)
+ 			continue;
+ 
+ 		      /* Look at each operand for a memory reference using
+  			 LHS.  */
+ 		      for (j = 0; j < gimple_num_ops (use_stmt); j++)
+ 			{
+ 			  tree op = gimple_op (use_stmt, j);
+ 
+ 			  if (op == NULL)
+ 			    continue;
+ 
+ 			  while (handled_component_p (op))
+ 			    op = TREE_OPERAND (op, 0);
+ 
+ 			  if ((TREE_CODE (op) == MEM_REF
+ 			       || TREE_CODE (op) == INDIRECT_REF)
+ 			      && TREE_OPERAND (op, 0) == lhs)
+ 			    {
+ 			      /* We can optimize.  Two cases.  First if E is
+ 				 not critical (E->src has just one successor)
+ 				 then we can just mark E->src for processing
+ 				 later as E->src must not be executable at
+ 				 runtime.
+ 
+ 				 If E is critical, then we want to remove E
+ 				 which requires updating the GIMPLE_COND
+ 				 in E->src.  */
+ 			      edge e = gimple_phi_arg_edge (phi, i);
+ 			      basic_block src = e->src;
+ 
+ 			      if (single_succ_p (src))
+ 				{
+ 				  if (dump_file && (dump_flags & TDF_DETAILS))
+ 				    fprintf (dump_file,
+ 					     "Edge %d->%d is unexecutable\n",
+ 					     e->src->index,
+ 					     e->dest->index);
+ 					       
+ 				  bitmap_set_bit (unexecutable_blocks,
+ 						  src->index);
+ 				}
+ 			      else
+ 				{
+ 				  removed_edge |= remove_cond_and_edge (src, e);
+ 				}
+ 
+ 			      break;
+ 			    }
+ 			}
+ 
+ 		      /* We don't want to look at other uses, safely break
+ 			 from the immediate use iterator.  */
+ 		      if (removed_edge)
+ 		        BREAK_FROM_IMM_USE_STMT (iter);
+ 		    }
+ 		}
+ 	    }
+ 	}
+ 
+       /* Now see if we can mark BB as unexecutable by looking at its
+ 	 statements.  */
+       for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
+ 	{
+ 	  gimple stmt = gsi_stmt (si);
+ 	  unsigned int i;
+ 
+ 	  /* We only care about assignments with memory operands.  */
+ 	  if (!gimple_has_mem_ops (stmt)
+ 	      || gimple_code (stmt) != GIMPLE_ASSIGN)
+ 	    continue;
+ 
+ 	  /* Look at each operand for a memory reference using an explicit
+ 	     NULL pointer.  */
+ 	  for (i = 0; i < gimple_num_ops (stmt); i++)
+ 	    {
+ 	      tree op = gimple_op (stmt, i);
+ 
+ 	      if (op == NULL)
+ 		continue;
+ 
+ 	      while (handled_component_p (op))
+ 		op = TREE_OPERAND (op, 0);
+ 
+ 	      if (TREE_CODE (op) == MEM_REF || TREE_CODE (op) == INDIRECT_REF)
+ 		{
+ 		  tree op0 = TREE_OPERAND (op, 0);
+ 		  /* If the operand is NULL, then this block must not be
+  		     executable at runtime.  */
+ 		  if (operand_equal_p (op0, integer_zero_node, 0))
+ 		    bitmap_set_bit (unexecutable_blocks,
+ 				    gimple_bb (stmt)->index);
+ 		}
+ 	    }
+ 	}
+     }
+ 
+   /* Most of the time we're not going to find anything interesting, so
+      don't bother computing post dominators, control dependencies, etc
+      unless we're going to be able to optimize this function.  */
+   if (! bitmap_empty_p (unexecutable_blocks))
+     {
+       struct edge_list *el = NULL;
+       bitmap_iterator bi, bj;
+       unsigned int i, j;
+       bitmap *cd_map;
+       bitmap edges_removed = BITMAP_ALLOC (NULL);
+ 
+       /* Simple debugging.  Perhaps we should also include the control
+  	 dependent edge which is unexecutable in the dump?  */
+       if (dump_file && (dump_flags & TDF_DETAILS))
+ 	{
+ 	  fprintf (dump_file, "The following blocks are unexecutable.\n");
+ 	  debug_bitmap_file (dump_file, unexecutable_blocks);
+ 	}
+ 
+       /* Build the control dependency map.  For a given block we need to
+          know what edges it is control dependent upon.  */
+       cd_map = XNEWVEC (bitmap, last_basic_block);
+       for (i = 0; i < (unsigned) last_basic_block; i++)
+ 	cd_map[i] = BITMAP_ALLOC (NULL);
+ 
+       timevar_push (TV_CONTROL_DEPENDENCES);
+       calculate_dominance_info (CDI_POST_DOMINATORS);
+       el = create_edge_list ();
+       find_all_control_dependences (el, cd_map);
+       timevar_pop (TV_CONTROL_DEPENDENCES);
+ 
+       EXECUTE_IF_SET_IN_BITMAP (unexecutable_blocks, 0, i, bi)
+ 	{
+ 	  EXECUTE_IF_CONTROL_DEPENDENT (cd_map, i, j, bj)
+ 	    {
+ 	      if (bitmap_set_bit (edges_removed, j))
+ 		remove_cond_and_edge (INDEX_EDGE_PRED_BB (el, j),
+ 				      INDEX_EDGE (el, j));
+ 	    }
+ 	}
+ 
+       for (i = 0; i < (unsigned) last_basic_block; i++)
+ 	BITMAP_FREE (cd_map[i]);
+       free (cd_map);
+       BITMAP_FREE (edges_removed);
+     }
+ 
+   BITMAP_FREE (unexecutable_blocks);
+   if (cfg_altered)
+     {
+       free_dominance_info (CDI_DOMINATORS);
+       free_dominance_info (CDI_POST_DOMINATORS);
+       return TODO_cleanup_cfg;
+     }
+   return 0;
+ }
+ 
+ static bool
+ gate_remove_unexecutable_paths (void)
+ {
+   return flag_tree_unexec_paths != 0;
+ 
+ }
+ 
+ struct gimple_opt_pass pass_remove_unexecutable_paths =
+ {
+  {
+   GIMPLE_PASS,
+   "unexecpaths",			/* name */
+   gate_remove_unexecutable_paths,	/* gate */
+   execute_remove_unexecutable_paths,	/* execute */
+   NULL,					/* sub */
+   NULL,					/* next */
+   0,					/* static_pass_number */
+   TV_TREE_UNEXEC_PATHS, 		/* tv_id */
+   PROP_ssa | PROP_cfg,			/* properties_required */
+   0,					/* properties_provided */
+   0,					/* properties_destroyed */
+   0,					/* todo_flags_start */
+   TODO_verify_ssa
+   | TODO_verify_flow			/* todo_flags_finish */
+  }
+ };

Re: RFA: New pass to delete unexecutable paths in the CFG

[Jakub Jelinek]

On Mon, Nov 07, 2011 at 02:55:02AM -0700, Jeff Law wrote:
> [ Working virtually from Hawaii tonight...  :-) ]

;)

> You might legitimately wonder how often this triggers.   A GCC 4.6.0
> checking-enabled compiler sees a .64% codesize improvement from this
> optimization.  That's an awful lot of unexecutable code.  The NULL
> references come from the VEC implementation and a variety of other
> sources.

I'd say it is a good idea, though I wonder if the gate shouldn't
also use && flag_delete_null_pointer_checks or at least if the default
for this new option shouldn't be based on flag_delete_null_pointer_checks.
-fno-delete-null-pointer-checks is documented for quite some time as an option
which allows NULL pointer dereferences (and AFAIK AVR uses it) and
people who use that option will most likely want to disable this
optimization too.

	Jakub

Re: RFA: New pass to delete unexecutable paths in the CFG

[Richard Guenther]

On Mon, Nov 7, 2011 at 11:07 AM, Jakub Jelinek <jakub@redhat.com> wrote:
> On Mon, Nov 07, 2011 at 02:55:02AM -0700, Jeff Law wrote:
>> [ Working virtually from Hawaii tonight...  :-) ]
>
> ;)
>
>> You might legitimately wonder how often this triggers.   A GCC 4.6.0
>> checking-enabled compiler sees a .64% codesize improvement from this
>> optimization.  That's an awful lot of unexecutable code.  The NULL
>> references come from the VEC implementation and a variety of other
>> sources.
>
> I'd say it is a good idea, though I wonder if the gate shouldn't
> also use && flag_delete_null_pointer_checks or at least if the default
> for this new option shouldn't be based on flag_delete_null_pointer_checks.
> -fno-delete-null-pointer-checks is documented for quite some time as an option
> which allows NULL pointer dereferences (and AFAIK AVR uses it) and
> people who use that option will most likely want to disable this
> optimization too.

I also wonder if instead of a new pass control-dependent DCE can
be taught of this?  At least I presume that this code removal can
expose DCE opportunities and DCE can expose these code removal
opportunities?

Did you consider simplifying the code by simply relying on
points-to analysis?  Thus for the dereferenced SSA name check

 pi = SSA_NAME_PTR_INFO (name);
 if (pi
    && pt_solution_empty_p (&pi->pt))
   ...

?  I once implemented a warning to warn about such derefrences,
but it (of course ...) triggers for all the unexecutable code paths...

points-to should be both more precise (it tracks uninitialized pointers
and it tracks memory) and less precise (because it's only flow-sensitive
for SSA names).

Richard.

Re: RFA: New pass to delete unexecutable paths in the CFG

[Richard Guenther]

On Mon, Nov 7, 2011 at 11:16 AM, Richard Guenther
<richard.guenther@gmail.com> wrote:
> On Mon, Nov 7, 2011 at 11:07 AM, Jakub Jelinek <jakub@redhat.com> wrote:
>> On Mon, Nov 07, 2011 at 02:55:02AM -0700, Jeff Law wrote:
>>> [ Working virtually from Hawaii tonight...  :-) ]
>>
>> ;)
>>
>>> You might legitimately wonder how often this triggers.   A GCC 4.6.0
>>> checking-enabled compiler sees a .64% codesize improvement from this
>>> optimization.  That's an awful lot of unexecutable code.  The NULL
>>> references come from the VEC implementation and a variety of other
>>> sources.
>>
>> I'd say it is a good idea, though I wonder if the gate shouldn't
>> also use && flag_delete_null_pointer_checks or at least if the default
>> for this new option shouldn't be based on flag_delete_null_pointer_checks.
>> -fno-delete-null-pointer-checks is documented for quite some time as an option
>> which allows NULL pointer dereferences (and AFAIK AVR uses it) and
>> people who use that option will most likely want to disable this
>> optimization too.
>
> I also wonder if instead of a new pass control-dependent DCE can
> be taught of this?  At least I presume that this code removal can
> expose DCE opportunities and DCE can expose these code removal
> opportunities?
>
> Did you consider simplifying the code by simply relying on
> points-to analysis?  Thus for the dereferenced SSA name check
>
>  pi = SSA_NAME_PTR_INFO (name);
>  if (pi
>    && pt_solution_empty_p (&pi->pt))
>   ...
>
> ?  I once implemented a warning to warn about such derefrences,
> but it (of course ...) triggers for all the unexecutable code paths...
>
> points-to should be both more precise (it tracks uninitialized pointers
> and it tracks memory) and less precise (because it's only flow-sensitive
> for SSA names).

Oh, and points-to plus DSE/DCE might confuse your pass as stores that
points-to can prove go "nowhere" are removed.

int main()
{
  int *p = 0;
  *p = 1;
}

with -fno-tree-ccp we remove the store (ugh, I suppose we should not
do that ;)).

Richard.

> Richard.
>

Re: RFA: New pass to delete unexecutable paths in the CFG

[Tom Tromey]

>>>>> "Jeff" == Jeff Law <law@redhat.com> writes:

Jeff> First, it's perfectly fine to have a NULL pointer dereference in a
Jeff> program as long as that code is never executed.  Once the code is
Jeff> executed, we've entered the realm of undefined behavior.

Jeff> Thus in a conforming program we can safely assume that a provable NULL
Jeff> pointer dereference can never be executed at runtime.  This implies
Jeff> there is a path through the CFG that is unexecutable.

IIUC, then this isn't true for Java.  In Java the attempt to dereference
NULL throws a NullPointerException, which can be caught, etc.  It isn't
undefined.

Tom

Re: RFA: New pass to delete unexecutable paths in the CFG

[Jeff Law]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 11/07/11 06:53, Tom Tromey wrote:
>>>>>> "Jeff" == Jeff Law <law@redhat.com> writes:
> 
> Jeff> First, it's perfectly fine to have a NULL pointer dereference
> in a Jeff> program as long as that code is never executed.  Once
> the code is Jeff> executed, we've entered the realm of undefined
> behavior.
> 
> Jeff> Thus in a conforming program we can safely assume that a
> provable NULL Jeff> pointer dereference can never be executed at
> runtime.  This implies Jeff> there is a path through the CFG that
> is unexecutable.
> 
> IIUC, then this isn't true for Java.  In Java the attempt to
> dereference NULL throws a NullPointerException, which can be
> caught, etc.  It isn't undefined.
So, presumably there's no way to know we're throwing to
NullPointerException from the exception information attached to the
statement or BB?  If not I could disable if the statement with the
memory op throws anywhere.  It's not ideal, but conservatively correct.

jeff

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iQEcBAEBAgAGBQJOt/ypAAoJEBRtltQi2kC7uhIH/jpk2jx7mn7i/RVA9jqiR3BU
tz4KRL1+giqWj8B2gG+y6vn8tBOFrruymIP4ewRjO1Q6IIvlDr6dyWSIXAw/TQ8g
p0V7Cfk+cxOkMJ6m6T/qpHjdtJsfx9FYQF6JSHPpalzh7FxlSIVJ9vGejmNqjHHG
ZxqDZd8emz0e7C4KtrX5mkMSZDHXo2+vWulwf8lwCJBjDLLR0nylv5GFREIuSDDR
BEkosWYfgJfngjmiwiXu8re9kEBpdRlnzDh+416VkSKTwjqHvqnb1Ux3rlBKHR7U
/DAQVcFNYdjwHFmTjvc50NPgOMf1fMEw9wCaMtL1THJlRMwpyaR5R8Gc+PiQjLk=
=bdeT
-----END PGP SIGNATURE-----

Re: RFA: New pass to delete unexecutable paths in the CFG

[Richard Guenther]

On Mon, Nov 7, 2011 at 4:43 PM, Jeff Law <law@redhat.com> wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> On 11/07/11 06:53, Tom Tromey wrote:
>>>>>>> "Jeff" == Jeff Law <law@redhat.com> writes:
>>
>> Jeff> First, it's perfectly fine to have a NULL pointer dereference
>> in a Jeff> program as long as that code is never executed.  Once
>> the code is Jeff> executed, we've entered the realm of undefined
>> behavior.
>>
>> Jeff> Thus in a conforming program we can safely assume that a
>> provable NULL Jeff> pointer dereference can never be executed at
>> runtime.  This implies Jeff> there is a path through the CFG that
>> is unexecutable.
>>
>> IIUC, then this isn't true for Java.  In Java the attempt to
>> dereference NULL throws a NullPointerException, which can be
>> caught, etc.  It isn't undefined.
> So, presumably there's no way to know we're throwing to
> NullPointerException from the exception information attached to the
> statement or BB?  If not I could disable if the statement with the
> memory op throws anywhere.  It's not ideal, but conservatively correct.

Well, stmt_could_throw_p says that (java has non-call exceptions).

OTOH I'm not sure we want to change a possible trap (And thus
program abort) to a fallthru ...

Richard.

Re: RFA: New pass to delete unexecutable paths in the CFG

[Tom Tromey]

>>>>> "Jeff" == Jeff Law <law@redhat.com> writes:

Jeff> So, presumably there's no way to know we're throwing to
Jeff> NullPointerException from the exception information attached to the
Jeff> statement or BB?  If not I could disable if the statement with the
Jeff> memory op throws anywhere.  It's not ideal, but conservatively correct.

I don't know the answer, but Java uses -fnon-call-exceptions, so maybe
gating it on this would be appropriate.  Or, adding a new flag that the
Java FE sets would also be fine by me.

Tom

Re: RFA: New pass to delete unexecutable paths in the CFG

[Jeff Law]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1


> 
> I also wonder if instead of a new pass control-dependent DCE can be
> taught of this?
It could.   I'm not sure it really buys us anything except maybe being
able to reuse the pdom & control-dependency analysis.

It actually more naturally belongs in cprop because it's cprop that
exposes NULL pointers in useful ways (in memory dereferences and as
PHI args).




 At least I presume that this code removal can
> expose DCE opportunities and DCE can expose these code removal 
> opportunities?
In theory, yes.  However, because we find & remove the edge upon which
the memory reference is control dependent upon, what we really expose
is unreachable code.  Hence the CFG cleanup pass.

Secondary effects I've witnessed are more block merging exposed due to
CFG simplifications and further const/copy propagation exposed by edge
removal at the point where unexecutable & executable paths meet.

It's not hard to imagine how this could lead to additional DCE
opportunities and other optimizations, I just haven't looked for them
or noticed them.  The valgrind results are a good indication that
we're picking up good secondary optimizations.

I don't think DCE will often lead to new opportunities for this code,
it could happen, but I'd expect it to be the exception rather than the
norm.

FWIW, the location of the pass right now sits just after DOM1 so a
goodly amount of constant propagation is already done, but we still
get a chance to pick up the secondary optimization opportunities in
DOM2.  The pass also sits between two DCE passes, so if DCE is
exposing opportunities for this pass, we get them and if this pass is
exposing opportunities for DCE, we get them too :-)



> 
> Did you consider simplifying the code by simply relying on 
> points-to analysis?  Thus for the dereferenced SSA name check
> 
> pi = SSA_NAME_PTR_INFO (name); if (pi && pt_solution_empty_p
> (&pi->pt))
Nope.   I guess it could be added, though it's often important to know
the origin of the NULL pointer.

p5 = PHI (p4 (1), 0 (0))
...
if (cond)
  goto X
else
  goto Y

X:
  foo (P5)
  goto Z
Y:
  *p5 = <value>
Z:


Analysis will mark P5 is being potentially NULL, but it would
incorrect to remove the edge corresponding to the NULL PHI arguement
as traversing that edge does not guarantee we will dereference the
NULL pointer.

The most interesting answer from PTA would be things like this pointer
must be NULL, but if that's true, then it should have been propagated
to the use sites already.

> ...
> 
> ?  I once implemented a warning to warn about such derefrences, but
> it (of course ...) triggers for all the unexecutable code paths...
Yup.  The one I've got here looks like a traditional propagation
engine.  There's knobs on it to tweak how it handles loads from
memory, call return values, etc.  Utilizing PTA would certainly help.
 I'll put that on the TODO list.  I would have liked to have it
polished in time for GCC 4.7, but other events got in the way.

Jeff
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iQEcBAEBAgAGBQJOuAJbAAoJEBRtltQi2kC7cA4H/jrPusXwvf0ECDh5MP/hNcna
R+zHWQPVOsPsyZkJCEuGqBkLT0+2ar0fS0uiqcXrZelY+TqAw0geg5t60w4lHF9p
9ERDqsBExVZW0X2VdnTZrYyfyB/fOc9xIizp/KxDWV33i7CwDFOyYR7QwXZnAMcp
7lpdzzxRbFaq05kj9K2aFtt8X/N7+Gn7dsI7kTLexmU2T+rXEF8P/HEqNefz70tV
t23W9V81cbZDP9g9LhJzrMfQrylI/lSk+Nve10aBal0EVPi5IzWAvxfL5uxD3G4l
sxOuH9bD7dNGDdJI1JnFxz56Z4DNI/0ARHM/RsZDbcAFUm8FG/DIzitBPslFegY=
=24NO
-----END PGP SIGNATURE-----

Re: RFA: New pass to delete unexecutable paths in the CFG

[Richard Guenther]

On Mon, Nov 7, 2011 at 5:07 PM, Jeff Law <law@redhat.com> wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
>
>>
>> I also wonder if instead of a new pass control-dependent DCE can be
>> taught of this?
> It could.   I'm not sure it really buys us anything except maybe being
> able to reuse the pdom & control-dependency analysis.
>
> It actually more naturally belongs in cprop because it's cprop that
> exposes NULL pointers in useful ways (in memory dereferences and as
> PHI args).

Heh, indeed, that as well.  I suppose every pass that handles
unexecutable edges in some way might benefit from this.  Like for

 if (i)
   j_1 = 1;
 else
   {
    j_2 = 2;
    *0 = ...;
   }
 j_3 = PHI <j_1, j_2>

we could CCP j_1 = 1 to j_3 ...

Even without actually removing the edge and the trapping stmt.

For DCE the most interesting part would be to end the block at
the point of  the trap - thus - replace the store with a __builtin_trap ()
which then trivially makes all code w/o side-effects on the path
dead.

Richard.

>
>
>
>  At least I presume that this code removal can
>> expose DCE opportunities and DCE can expose these code removal
>> opportunities?
> In theory, yes.  However, because we find & remove the edge upon which
> the memory reference is control dependent upon, what we really expose
> is unreachable code.  Hence the CFG cleanup pass.
>
> Secondary effects I've witnessed are more block merging exposed due to
> CFG simplifications and further const/copy propagation exposed by edge
> removal at the point where unexecutable & executable paths meet.
>
> It's not hard to imagine how this could lead to additional DCE
> opportunities and other optimizations, I just haven't looked for them
> or noticed them.  The valgrind results are a good indication that
> we're picking up good secondary optimizations.
>
> I don't think DCE will often lead to new opportunities for this code,
> it could happen, but I'd expect it to be the exception rather than the
> norm.
>
> FWIW, the location of the pass right now sits just after DOM1 so a
> goodly amount of constant propagation is already done, but we still
> get a chance to pick up the secondary optimization opportunities in
> DOM2.  The pass also sits between two DCE passes, so if DCE is
> exposing opportunities for this pass, we get them and if this pass is
> exposing opportunities for DCE, we get them too :-)
>
>
>
>>
>> Did you consider simplifying the code by simply relying on
>> points-to analysis?  Thus for the dereferenced SSA name check
>>
>> pi = SSA_NAME_PTR_INFO (name); if (pi && pt_solution_empty_p
>> (&pi->pt))
> Nope.   I guess it could be added, though it's often important to know
> the origin of the NULL pointer.
>
> p5 = PHI (p4 (1), 0 (0))
> ...
> if (cond)
>  goto X
> else
>  goto Y
>
> X:
>  foo (P5)
>  goto Z
> Y:
>  *p5 = <value>
> Z:
>
>
> Analysis will mark P5 is being potentially NULL, but it would
> incorrect to remove the edge corresponding to the NULL PHI arguement
> as traversing that edge does not guarantee we will dereference the
> NULL pointer.
>
> The most interesting answer from PTA would be things like this pointer
> must be NULL, but if that's true, then it should have been propagated
> to the use sites already.
>
>> ...
>>
>> ?  I once implemented a warning to warn about such derefrences, but
>> it (of course ...) triggers for all the unexecutable code paths...
> Yup.  The one I've got here looks like a traditional propagation
> engine.  There's knobs on it to tweak how it handles loads from
> memory, call return values, etc.  Utilizing PTA would certainly help.
>  I'll put that on the TODO list.  I would have liked to have it
> polished in time for GCC 4.7, but other events got in the way.
>
> Jeff
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.4.11 (GNU/Linux)
> Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/
>
> iQEcBAEBAgAGBQJOuAJbAAoJEBRtltQi2kC7cA4H/jrPusXwvf0ECDh5MP/hNcna
> R+zHWQPVOsPsyZkJCEuGqBkLT0+2ar0fS0uiqcXrZelY+TqAw0geg5t60w4lHF9p
> 9ERDqsBExVZW0X2VdnTZrYyfyB/fOc9xIizp/KxDWV33i7CwDFOyYR7QwXZnAMcp
> 7lpdzzxRbFaq05kj9K2aFtt8X/N7+Gn7dsI7kTLexmU2T+rXEF8P/HEqNefz70tV
> t23W9V81cbZDP9g9LhJzrMfQrylI/lSk+Nve10aBal0EVPi5IzWAvxfL5uxD3G4l
> sxOuH9bD7dNGDdJI1JnFxz56Z4DNI/0ARHM/RsZDbcAFUm8FG/DIzitBPslFegY=
> =24NO
> -----END PGP SIGNATURE-----
>

Re: RFA: New pass to delete unexecutable paths in the CFG

[Kai Tietz]

2011/11/7 Richard Guenther <richard.guenther@gmail.com>:
> On Mon, Nov 7, 2011 at 5:07 PM, Jeff Law <law@redhat.com> wrote:
>> -----BEGIN PGP SIGNED MESSAGE-----
>> Hash: SHA1
>>
>>
>>>
>>> I also wonder if instead of a new pass control-dependent DCE can be
>>> taught of this?
>> It could.   I'm not sure it really buys us anything except maybe being
>> able to reuse the pdom & control-dependency analysis.
>>
>> It actually more naturally belongs in cprop because it's cprop that
>> exposes NULL pointers in useful ways (in memory dereferences and as
>> PHI args).
>
> Heh, indeed, that as well.  I suppose every pass that handles
> unexecutable edges in some way might benefit from this.  Like for
>
>  if (i)
>   j_1 = 1;
>  else
>   {
>    j_2 = 2;
>    *0 = ...;
>   }
>  j_3 = PHI <j_1, j_2>
>
> we could CCP j_1 = 1 to j_3 ...
>
> Even without actually removing the edge and the trapping stmt.
>
> For DCE the most interesting part would be to end the block at
> the point of  the trap - thus - replace the store with a __builtin_trap ()
> which then trivially makes all code w/o side-effects on the path
> dead.
>
> Richard.

Well, easiest sample to see effect of if-joining is on patterns like
this.  As here neither PHI-opt nor tail-merge helps pretty much, as
condition chain doesn't get reduced to simple form.  The sample above
seems to be too less explicit to get the point.

Eg:

int doo (void);

int foo (unsigned int a, unsigned int b)
{
  if (a == 0) rerturn doo ();
  if (b == 0) return doo ();
  if (a == 1) return doo ();
  if (b == 1) return doo ();
  if (a == 2) return doo ();
  if (b == 2) return doo ();
  return -2;
}

This sample would be the same (in associative form) as

int doo (void);

int foo (unsigned int a, unsigned int b)
{
  if (a == 0 || b == 0 || a == 1 || b == 1 || a == 2 || b == 2) rerturn doo ();
  return -2;
}

(btw both samples won't be folded for IA due current BC).

With the first patch doing the transformation to associative
truth-bitwise for all simple operands, the second example will be
folded by reassoc-pass to
...
if (a <= 2 || b <=2) return doo ();
return -2;
...

With the if-joining also the first example gets optimized to this simple form.

Regards,
Kai

Re: RFA: New pass to delete unexecutable paths in the CFG

[Paolo Bonzini]

On 11/07/2011 04:54 PM, Tom Tromey wrote:
>>>>>> "Jeff" == Jeff Law<law@redhat.com>  writes:
>
> Jeff>  So, presumably there's no way to know we're throwing to
> Jeff>  NullPointerException from the exception information attached to the
> Jeff>  statement or BB?  If not I could disable if the statement with the
> Jeff>  memory op throws anywhere.  It's not ideal, but conservatively correct.
>
> I don't know the answer, but Java uses -fnon-call-exceptions, so maybe
> gating it on this would be appropriate.  Or, adding a new flag that the
> Java FE sets would also be fine by me.

I'm not sure if GCC will currently delete the "if" statement in

    try {
        x = x.getSomething();
    } catch (NullPointerException npe) { }

    if (x) ...

but even if it doesn't, the Java front-end should probably reset 
flag_delete_null_pointer_checks.

Paolo

Re: RFA: New pass to delete unexecutable paths in the CFG

[Jeff Law]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 11/07/11 09:24, Richard Guenther wrote:
> On Mon, Nov 7, 2011 at 5:07 PM, Jeff Law <law@redhat.com> wrote:
> 
>>>> 
>>>> I also wonder if instead of a new pass control-dependent DCE
>>>> can be taught of this?
> It could.   I'm not sure it really buys us anything except maybe
> being able to reuse the pdom & control-dependency analysis.
> 
> It actually more naturally belongs in cprop because it's cprop
> that exposes NULL pointers in useful ways (in memory dereferences
> and as PHI args).
> 
>> Heh, indeed, that as well.  I suppose every pass that handles 
>> unexecutable edges in some way might benefit from this.  Like
>> for
> 
>> if (i) j_1 = 1; else { j_2 = 2; *0 = ...; } j_3 = PHI <j_1, j_2>
> 
>> we could CCP j_1 = 1 to j_3 ...
Yea, but we already do that...  We'd propagate the constant 1 into the
PHI.  DOM, CCP and probably VRP all do this..

> 
>> Even without actually removing the edge and the trapping stmt.
I'm guessing you mean we could propagate j_1's value to the uses of
j_3.  This is true, but misses the primary effect of the patch, namely
to remove the controlling conditional branch which leads to the *0 (if
(i)) in your sample.

Those controlling conditions *are* executed at runtime and we want to
remove them if at all possible.  Once that's done all the things you'd
expect/want to happen do so naturally with the existing optimizers.

> 
>> For DCE the most interesting part would be to end the block at 
>> the point of  the trap - thus - replace the store with a
>> __builtin_trap () which then trivially makes all code w/o
>> side-effects on the path dead.
But we're still stuck with the conditional leading to the path with
the __builtin_trap.  That's what we want to avoid since those
conditionals are executed at runtime.

Jeff
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iQEcBAEBAgAGBQJOuCltAAoJEBRtltQi2kC7acEIAJXOaJt0jZIuKS5ZsxrvADGO
TVqT0tosqOvm9EkOsZve72WSZ1fQpklbdbuNwUPvxhb60Z4Q+a2C/kKbxq1PeJs5
Ba/lj2R8Na9mg9Nps/bDnDVvuOATk59IhyoEjnZlUMMkVYZS1LOgTcdPvc1ItbhQ
D+0SxaDfBPLLJ1zHcOJ2jXnF+MDFq1We5yZG2czOOYWup9zbCpmkrNzN/MisxAeU
W8PT48VHTD/Ez6zOCswVtvkmLUhOWEcSG5Um2dt90RF5K8gSigzgeFO2wal+uJe5
YpY9IPrK0OK2tCXjGQulaGKhylyN6ynEwCdHJYQua1g1Q7I7rxBxJ/oMMcxw9zE=
=Dd+Z
-----END PGP SIGNATURE-----

Re: RFA: New pass to delete unexecutable paths in the CFG

[Jeff Law]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 11/07/11 08:54, Tom Tromey wrote:
>>>>>> "Jeff" == Jeff Law <law@redhat.com> writes:
> 
> Jeff> So, presumably there's no way to know we're throwing to Jeff>
> NullPointerException from the exception information attached to
> the Jeff> statement or BB?  If not I could disable if the statement
> with the Jeff> memory op throws anywhere.  It's not ideal, but
> conservatively correct.
> 
> I don't know the answer, but Java uses -fnon-call-exceptions, so
> maybe gating it on this would be appropriate.  Or, adding a new
> flag that the Java FE sets would also be fine by me.
I'll poke at it a little; I suspect the easiest thing to do will be to
either avoid this entirely if -fnon-call-exceptions or avoid if
there're an abnormal edge leading out of the block.

Jeff

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iQEcBAEBAgAGBQJOuCpWAAoJEBRtltQi2kC7STwH/0OHElnvs4hiUi0GwYaPq5AZ
q8nTXK1l3R3eZqwv6Rjtc99MBEQWbDCgtv5VPU7l0ePcZ5Kk277PpRNQjMAkQp7g
BeW5U8RMxwczIeHGk8h9RNqIQREUHSeAzCGqXeZzIKEPUy3WeKe7Kufj+TOLo5ZX
+B4iE/uzMmmr4l0qLVHEtL6bQ3ZWsDbK87WTZknHE9tQQryRvhXmM6j3HpYn+7sK
bULWNaoUuZW4YbUiGGLM77t/hPgTPR1K7JA2tKAsxrXj+0sqanE8/ZydvgYzoaYd
bTJ3bqhMnkWRCnSGmAgjScQLYFwNJlu6QzTWI6Dp6EhWMnbDnbIFwXwIVDOzhrc=
=SFAu
-----END PGP SIGNATURE-----

Re: RFA: New pass to delete unexecutable paths in the CFG

[Jeff Law]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 11/07/11 08:49, Richard Guenther wrote:

> 
> OTOH I'm not sure we want to change a possible trap (And thus 
> program abort) to a fallthru ...
I think this is the big question we need to answer; there's other
places were we rely upon ISO's standards to enable optimization.  But
this one just feels a little different...  Or maybe I'm shy after the
kernel security problem caused by relying on dereferenced pointer not
being null.

I could easily see not enabling the switch by default for a period of
time, or enabling the optimization by default along with some kind of
warning.

Jeff
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iQEcBAEBAgAGBQJOuCuJAAoJEBRtltQi2kC7Q3cIAJRZGTaPlhQp3Y7fyx4A3rTJ
xmO45FkfkVba3NVqqCy2Ei95ezORhqzt2X31pzUuNZmyAXagnlizcY2uBNrgcRIl
+AltdDn3V+B19oABLrnVoxKjlb0yqHOKxikZcktFZuBB6zJBYOveWbWir5pMt2se
0K7pCXc6oe3MJfaYrPnZSkYEf5pcJw0ZKXxrK46HakWv5/oBi+kw5fo9aiEW0bhu
FQWxnfiNEsp4w+ac4PY/oQmcquI2AjeMrHiSKuZquC+r34SCYHMlSR9cED9WSy+7
RIlHygJYFcF9YwYEEbn61yyHfKbrIg6StizpkFVvu/oa2uDtqVFpFFBV0znO3aY=
=iF0s
-----END PGP SIGNATURE-----

Re: RFA: New pass to delete unexecutable paths in the CFG

[Jeff Law]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 11/07/11 03:07, Jakub Jelinek wrote:
> On Mon, Nov 07, 2011 at 02:55:02AM -0700, Jeff Law wrote:
>> [ Working virtually from Hawaii tonight...  :-) ]
> 
> ;)
> 
>> You might legitimately wonder how often this triggers.   A GCC
>> 4.6.0 checking-enabled compiler sees a .64% codesize improvement
>> from this optimization.  That's an awful lot of unexecutable
>> code.  The NULL references come from the VEC implementation and a
>> variety of other sources.
> 
> I'd say it is a good idea, though I wonder if the gate shouldn't 
> also use && flag_delete_null_pointer_checks or at least if the
> default for this new option shouldn't be based on
> flag_delete_null_pointer_checks. -fno-delete-null-pointer-checks is
> documented for quite some time as an option which allows NULL
> pointer dereferences (and AFAIK AVR uses it) and people who use
> that option will most likely want to disable this optimization
> too.
Yea, I'd been back and forth on this too -- I don't like gating on the
null-pointer-check flag, but I agree that folks using
- -fno-delete-null-... probably aren't going to want the new
optimization either.

I'll put on my thinking cap and see if I can come up with a good name
that encompasses both classes of optimization without getting overly
broad.

jeff
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iQEcBAEBAgAGBQJOuCwXAAoJEBRtltQi2kC7I6UH/2PRnCZxPCHvImghz8IN3ThX
IANY9jCSqRzzsebWtTwZ9Y0XE6uQhMpEx/98/ZFZ96OC8rrQkoYR+Jf4DOAP82ja
SMDpBETK6BZ7Y/bMKgzJA/QfIlxIcRNScGqZg+F+C3WPqJADHAxCmWGqx/c4/Mwz
aylaEBVi/7klqxpmxlkSeN6n0whXf8zL/XmTovpro/6B3oiJaVd1diyrJl3s9vL4
BwjvsbA8ZosLPVCcdLY+9OWjhlnwbOxQQ/xzN8g7knPGNVhe4pXaBmzNiPXGKzrN
1qteyLNdVvnOWj/h1w9a3Ew2EJ3eLUXTytM5BjDfA3gF9Jd1umN81Js+Z/sBRXA=
=W7V6
-----END PGP SIGNATURE-----

Re: RFA: New pass to delete unexecutable paths in the CFG

[Jeff Law]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 11/07/11 03:21, Richard Guenther wrote:

> 
> Oh, and points-to plus DSE/DCE might confuse your pass as stores
> that points-to can prove go "nowhere" are removed.
I think this is OK in the sense that we may miss a case where we could
have detected a path was unexecutable, but that's just a missed
optimization, not a correctness issue.

jeff
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iQEcBAEBAgAGBQJOuCzaAAoJEBRtltQi2kC7LM8IAKKSRpunevuhIzZtpi3h+FFw
LYO0E4U0wrlif/eS8mgzkXbZnEolHIsZBoOJyAxwgbWKqt6SbnDQl93fv5t67TsK
EYNE2uXG84/2u88vx31nFXYAY9OKFj3Kt0RH64PjEsFYZ9qCYAHN4opL0kLToxrF
4dZ33TXZuOe/AAdL+Z1OZRntfYy2rJWf5O2QITsyYfrs0aFfoZkvm7RD3+Luwvks
XG6nUreLvq5dior8FCrBX3yjm1c/uOxuUaKtooWYwyF4T1pDxXDL2R/QgMQhsmBZ
jJiTZOXYbnjy1L9lf/PCENnd4cmcJeETyY8wuKeYjIwizcdh0yKpHEuIS0zlry8=
=ESJY
-----END PGP SIGNATURE-----

Re: RFA: New pass to delete unexecutable paths in the CFG

[Richard Guenther]

On Mon, Nov 7, 2011 at 8:03 PM, Jeff Law <law@redhat.com> wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> On 11/07/11 08:49, Richard Guenther wrote:
>
>>
>> OTOH I'm not sure we want to change a possible trap (And thus
>> program abort) to a fallthru ...
> I think this is the big question we need to answer; there's other
> places were we rely upon ISO's standards to enable optimization.  But
> this one just feels a little different...  Or maybe I'm shy after the
> kernel security problem caused by relying on dereferenced pointer not
> being null.
>
> I could easily see not enabling the switch by default for a period of
> time, or enabling the optimization by default along with some kind of
> warning.

Indeed.  We'd have to tell people that they cannot catch *(void *)0 = 0
with a SIGSEGV signal handler unless they compile with some magic flag.
Thus, the question is whether we want to optimize things in a way that
are non-obvious to people viewing things from a POSIX point of view
rather than a C standard conforming issue.

But what we could do by default is transform such stores to a trap
representation, or at least making the feeding stmts dead by changing
the stored value and the address to a constant (thus, even preserve
the trap kind).  fold_stmt could change the stored value if the address
is literal zero, and all passes that know it is zero should propagate
it anyway.  That wouldn't remove the outgoing edge from the store
of course, cfgcleanup could be teached to do that though (and
we could invent a trap kind argument to __builtin_trap).

Richard.

Re: RFA: New pass to delete unexecutable paths in the CFG

[Paolo Bonzini]

On 11/07/2011 07:54 PM, Jeff Law wrote:
> But we're still stuck with the conditional leading to the path with
> the __builtin_trap.  That's what we want to avoid since those
> conditionals are executed at runtime.

Just to understand, what does this do with your optimization?

void f(void *p)
{
    if (p)
      {
        puts("sell_soul_to_devil");
        puts("post_reload_rewrite");
      }

    *p = 2;
}

   ...
   f(NULL);

Does the program sell its soul to the devil before crashing?

Paolo

Re: RFA: New pass to delete unexecutable paths in the CFG

[Jeff Law]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 11/08/11 04:18, Paolo Bonzini wrote:
> On 11/07/2011 07:54 PM, Jeff Law wrote:
>> But we're still stuck with the conditional leading to the path
>> with the __builtin_trap.  That's what we want to avoid since
>> those conditionals are executed at runtime.
> 
> Just to understand, what does this do with your optimization?
> 
> void f(void *p) { if (p) { puts("sell_soul_to_devil"); 
> puts("post_reload_rewrite"); }
> 
> *p = 2; }
> 
> ... f(NULL);
> 
> Does the program sell its soul to the devil before crashing?
If "f" is not inlined into its caller, then there's nothing for the
new pass to do.  There's no explicit NULL dereference and there's no
assignments to "p", so there's no PHI at the merge point for P.


If f is inlined into the caller, exposing NULL as a value for P, we'd have

if (0)
  {
    whatever
  }

 *0 = 2;

The conditional would be removed leaving just


  *0 = 2

To know the effect, we'd have to have more context of the caller.

If the caller was just

void bar ()
{
  f (NULL);
}

*0 = 2 is not control dependent on any path and thus it'd be left alone.



Jeff
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iQEcBAEBAgAGBQJOuYMWAAoJEBRtltQi2kC7HxoH/3tJIsoGp0qha3ys48M/tszg
zsVatm9mN6QiloU64UmpnUTdiBIgU66DcWUKkwqwmi+v1tdYr+OkhyrdrRvW4OQh
A6XsQnMnyw7jO2IEqqvB25blNEXR+qCTqwmyMI1dQXg0dJEhnLVuxI05Z1waD/Q9
bs7UbQqvpIYQSZwAB+22Bre2VR944l0O6FG1rWcVWmHdDFTgM8NdTr3gnuPLkev3
8/9ekkHiiOuBgmg60PVyax6NqBoiLtt3KAodVB5wUrq2rVhrjDwr9FIKsg4oe6dO
DdkZhs5h6kAkLZ9D/yv8ZLkqn/P6j3jlhVYIMe7/YbBc0Ae8cn9gpYtK0vfmirk=
=AUFy
-----END PGP SIGNATURE-----

Re: RFA: New pass to delete unexecutable paths in the CFG

[Jeff Law]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 11/07/11 15:25, Richard Guenther wrote:
> 
> Indeed.  We'd have to tell people that they cannot catch *(void *)0
> = 0 with a SIGSEGV signal handler unless they compile with some
> magic flag. Thus, the question is whether we want to optimize
> things in a way that are non-obvious to people viewing things from
> a POSIX point of view rather than a C standard conforming issue.
Agreed.  The path I'd started going down was a flag like
"-fassume-null-dereference-faults-and-is-uncatchable" or something
like that.  -fdelete-null-pointer-checks  would be subsumed by the new
flag.


> 
> 
> But what we could do by default is transform such stores to a trap 
> representation, or at least making the feeding stmts dead by
> changing the stored value and the address to a constant (thus, even
> preserve the trap kind).  fold_stmt could change the stored value
> if the address is literal zero, and all passes that know it is zero
> should propagate it anyway.  That wouldn't remove the outgoing edge
> from the store of course, cfgcleanup could be teached to do that
> though (and we could invent a trap kind argument to
> __builtin_trap).
More correctly, we'd wipe the path from the control edge to the *0
statement and remove the out edges from the block with the *0.  Then
just leave the *0 or a __builtin_trap.

We'd leave the control edge itself leading to the *0/trap.  That
allows us to get most of the space savings optimization as well as
most of the secondary benefits.  The programmer could still catch the
trapping signal.

That doesn't work in the case of the implied dereference via  NULL PHI
arg.  For that case we'd have to copy the block with the PHI, the
incoming edges would be partitioned into those implying a null
dereference vs those not implying a null dereference.  Effectively
this isolates the path with the implied NULL dereference and turns it
into an explicit NULL dereference and we could optimize as noted above.

So the question is do we want to proceed with any of this work?  If so
I can update the patch, if not I'll go back to my warning work :-)

jeff
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iQEcBAEBAgAGBQJOuYdZAAoJEBRtltQi2kC7z8oH/RVnZ03u2E20D2IbH++f0tiD
0StUVXlgtGGZHtY3jUupFzsQSSoyYtZhbgsVCCIm2Vu56t8jnb1YeWh8U4LVzsnA
SifQo9txI5rp9NECahsqHUMxYFOlFDXVfIzc2c0Fq/RTZ5dRCVCYgHTRODHB1qcJ
tXw4ckT0YOTEatGJsGt7QJtmEcjao71QV6UENbnzK6OIr7pD+hvFD0zUk7cZCyjW
eIH3uy075qt06o3tCyDq0KU6sz8HqHZu9r9WFKx7pi2Tyqxysxps4KiH/X9ruz74
w+0fVIHnqUbszMjqsOSls+Qu/DvhKVACIwGyStcgMyHyTcgrnyy7WkGzkWgcOQk=
=mSLN
-----END PGP SIGNATURE-----

Re: RFA: New pass to delete unexecutable paths in the CFG

[Paolo Bonzini]

On 11/08/2011 08:29 PM, Jeff Law wrote:
>> Just to understand, what does this do with your optimization?
>>
>> void f(void *p) {
>>  if (p) {
>>    puts("sell_soul_to_devil"); puts("post_reload_rewrite"); }
>>
>>  *p = 2; }
>>
>> ... f(NULL);
>>
>> Does the program sell its soul to the devil before crashing?
>
> If "f" is not inlined into its caller, then there's nothing for the
> new pass to do.  There's no explicit NULL dereference and there's no
> assignments to "p", so there's no PHI at the merge point for P.

But is that just a limitation of the representation?  With assertions as 
in VRP you'd have

    if (p_1) goto BB1 else goto BB2
BB1: ... goto BB3;
BB2: p_2 = assert(p_1, p_1 == 0); goto BB3;

    p_3 = phi (p_1<BB1>, p_2<BB2>);
    *p_3 = 2;

What would happen then?

Paolo

Re: RFA: New pass to delete unexecutable paths in the CFG

[Jeff Law]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 11/08/11 13:15, Paolo Bonzini wrote:
> On 11/08/2011 08:29 PM, Jeff Law wrote:
>>> Just to understand, what does this do with your optimization?
>>> 
>>> void f(void *p) { if (p) { puts("sell_soul_to_devil");
>>> puts("post_reload_rewrite"); }
>>> 
>>> *p = 2; }
>>> 
>>> ... f(NULL);
>>> 
>>> Does the program sell its soul to the devil before crashing?
>> 
>> If "f" is not inlined into its caller, then there's nothing for
>> the new pass to do.  There's no explicit NULL dereference and
>> there's no assignments to "p", so there's no PHI at the merge
>> point for P.
> 
> But is that just a limitation of the representation?  With
> assertions as in VRP you'd have
> 
> if (p_1) goto BB1 else goto BB2 BB1: ... goto BB3; BB2: p_2 =
> assert(p_1, p_1 == 0); goto BB3;
> 
> p_3 = phi (p_1<BB1>, p_2<BB2>); *p_3 = 2;
> 
> What would happen then?
We don't have access to those assertions as they're removed well prior
to this pass running.  However, if we did, or if we had redundant PHIs
in the stream which were propagated we'd be presented with something like

BB0  if (p_1) goto BB1 else goto BB2

BB1: ... goto BB3
BB2:
BB3: p_2 = phi (p_1 (BB1), 0(BB2))
     *p_2 = 2;


We'd recognize that the edge bb2->bb3 is unexecutable as doing so
leads to a NULL pointer dereference.  Since the edge bb2->bb3 is not a
critical edge, we know that bb2 as a whole is unexecutable.  bb2 is
control dependent on the edge bb0->bb2.

We would remove the edge bb0->bb2 and the control statement if (p_1)
....  That makes BB2 unreachable resulting in

BB0 goto BB1
BB1 ...
BB3 p_2 = phi (p_1)
    *p_2 = 2;

Which would then be optimized into

BB0: ...
     *p_1 = 2;

Which is exactly what I would expect the code to do with the knowledge
that passing 0 to f results in undefined behaviour.


jeff
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iQEcBAEBAgAGBQJOuZAGAAoJEBRtltQi2kC7gkwIAJLBfsgICHOWKVBFTAv1U1Xx
8+gR3o70JJmoZY7wOv51ReUOU3Nxzj36f/HzY0SHgNBDu4gxo94HzFkUp1x5u1uw
NUwv802p3JKpIroi8Tonu42mEhIzWGTOIUCLdrxqc3fdPtEMQrC5ExjeKdt//x61
+/JVzz4pNO2ZeYLfATa8fZDLtz0vBhmXD+Ue+p71i0sqw0TfNs+DYvuneW7Bk0uy
TfNpaVRZp+xJgYukrNqZqXw7+O4OuqU5Y1X42CCoz8m6+Zxado1sOB6jeEQjyyqH
+Liewv0jas67velgycrNRG4O0ppoOUF8vVY26ofeWtV16otc9/Yuz6+iqGJOJgo=
=8mxV
-----END PGP SIGNATURE-----

Re: RFA: New pass to delete unexecutable paths in the CFG

[Paolo Bonzini]

On 11/08/2011 09:24 PM, Jeff Law wrote:
> We don't have access to those assertions as they're removed well prior
> to this pass running.  However, if we did, or if we had redundant PHIs
> in the stream which were propagated we'd be presented with something like
>
> BB0  if (p_1) goto BB1 else goto BB2
>
> BB1: ... goto BB3
> BB2:
> BB3: p_2 = phi (p_1 (BB1), 0(BB2))
>       *p_2 = 2;
>
>
> We'd recognize that the edge bb2->bb3 is unexecutable as doing so
> leads to a NULL pointer dereference.  Since the edge bb2->bb3 is not a
> critical edge, we know that bb2 as a whole is unexecutable.  bb2 is
> control dependent on the edge bb0->bb2.

(Side note regarding critical edges: have you tried splitting them 
before your pass?)

> We would remove the edge bb0->bb2 and the control statement if (p_1)
> ....  That makes BB2 unreachable resulting in
>
> BB0 goto BB1
> BB1 ...
> BB3 p_2 = phi (p_1)
>      *p_2 = 2;
>
> Which would then be optimized into
>
> BB0: ...
>       *p_1 = 2;
>
> Which is exactly what I would expect the code to do with the knowledge
> that passing 0 to f results in undefined behaviour.

Ok, so that's exactly what I was thinking about.  In this case the 
optimization is obviously allowed by the C standard; you have

     if (p)
       something;
     *p = 0;

and the "*p = 0" has been in some sense translated to

     if (!p)
       something;
     *p = 0;

which is only different on undefined paths.  But I'm not sure that more 
complicated cases, where there are other instructions between the "if" 
and "*p = 0", would also be allowed by the C standard.  For example, I 
think a function call in the "else" branch, or between the PHI and the 
dereference should prevent the optimization, because the function call 
might never return for what we know.  Probably a volatile asm too.  Does 
your patch do that?  (Testcases! :)).

In general, this is quite different from all other existing GCC 
optimizations based on undefined behavior.  Whenever you trigger 
undefined behavior, right now the effects do not extend *before* the 
undefined operation.  The proposed pass would change that, so that its 
effects are a bit more surprising when debugging.  If your bug is that 
you forgot a "return;" in the else branch, you surely wouldn't expect 
the compiler to swallow the entire branch.  Unfortunately debugging at 
-O0 is not always an option.

Paolo

Re: RFA: New pass to delete unexecutable paths in the CFG

[Richard Guenther]

On Tue, Nov 8, 2011 at 8:47 PM, Jeff Law <law@redhat.com> wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> On 11/07/11 15:25, Richard Guenther wrote:
>>
>> Indeed.  We'd have to tell people that they cannot catch *(void *)0
>> = 0 with a SIGSEGV signal handler unless they compile with some
>> magic flag. Thus, the question is whether we want to optimize
>> things in a way that are non-obvious to people viewing things from
>> a POSIX point of view rather than a C standard conforming issue.
> Agreed.  The path I'd started going down was a flag like
> "-fassume-null-dereference-faults-and-is-uncatchable" or something
> like that.  -fdelete-null-pointer-checks  would be subsumed by the new
> flag.
>
>
>>
>>
>> But what we could do by default is transform such stores to a trap
>> representation, or at least making the feeding stmts dead by
>> changing the stored value and the address to a constant (thus, even
>> preserve the trap kind).  fold_stmt could change the stored value
>> if the address is literal zero, and all passes that know it is zero
>> should propagate it anyway.  That wouldn't remove the outgoing edge
>> from the store of course, cfgcleanup could be teached to do that
>> though (and we could invent a trap kind argument to
>> __builtin_trap).
> More correctly, we'd wipe the path from the control edge to the *0
> statement and remove the out edges from the block with the *0.  Then
> just leave the *0 or a __builtin_trap.
>
> We'd leave the control edge itself leading to the *0/trap.  That
> allows us to get most of the space savings optimization as well as
> most of the secondary benefits.  The programmer could still catch the
> trapping signal.
>
> That doesn't work in the case of the implied dereference via  NULL PHI
> arg.  For that case we'd have to copy the block with the PHI, the
> incoming edges would be partitioned into those implying a null
> dereference vs those not implying a null dereference.  Effectively
> this isolates the path with the implied NULL dereference and turns it
> into an explicit NULL dereference and we could optimize as noted above.

Hm, indeed.

> So the question is do we want to proceed with any of this work?  If so
> I can update the patch, if not I'll go back to my warning work :-)

I think we do want to continue with this work - probably not removing
the faulting dereference though.  I'd say we add a noreturn
__builtin_nullptr_deref () in place of it (eventually doing the path
isolation you mentioned above) and warn about the ones that survive
until RTL
expansion (where we'd just expand it as *0 = 0).

In fact, the warning part of it might be the most useful piece for our users ;)

Thanks,
Richard.

Re: RFA: New pass to delete unexecutable paths in the CFG

[Jeff Law]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 11/09/11 02:00, Richard Guenther wrote:
> 
>> So the question is do we want to proceed with any of this work?
>> If so I can update the patch, if not I'll go back to my warning
>> work :-)
> 
> I think we do want to continue with this work - probably not
> removing the faulting dereference though.  I'd say we add a
> noreturn __builtin_nullptr_deref () in place of it (eventually
> doing the path isolation you mentioned above) and warn about the
> ones that survive until RTL expansion (where we'd just expand it as
> *0 = 0).
Seems reasonable.  Interestingly enough the path isolation part would
be a special case of the path isolation code I want to build anyway.

FWIW, there's other things which we probably want to handle in a
similar fashion.  For example, out of range array references,
particularly those implied by PHIs with out of range indices.


> 
> In fact, the warning part of it might be the most useful piece for
> our users ;)
Most definitely.  Optimizing this stuff was merely a sideshow; I
believe the warning bits are far more useful.

Jeff

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iQEcBAEBAgAGBQJOurocAAoJEBRtltQi2kC7J3AIAJXwvQdfkXJGDtOvajvnbONy
EHH0SQPObDRW97CTNhS2Ky270SRzfZoF0dFAFEwnfoaHISkHxcWnJB6GIjYQZEG0
WJiY2QEJSeXvbX517S2AZLlvVA1Lzq/NFyPtw8I+Z4D23dqFWMF/OIQhBBMqanAN
GOmhsTFgn0njv6PR3ksD8Rvlf2GgfpKfrt2b8LFv2eEl1wIGf0uBEMFXgJJVBjcL
tWibKpxT9roreEwzoKtPV1Gn+vZ9grclNhQ501l9exzoonIvg+EY9amhUQgtSPFA
JeZUOgj3XHI1cWpCHeTMLnkar0w0XtWoqQd//+6RhFmdKFBQA9pV5XdVPJ2A8GA=
=vqbV
-----END PGP SIGNATURE-----

Re: RFA: New pass to delete unexecutable paths in the CFG

[Jeff Law]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 11/09/11 01:09, Paolo Bonzini wrote:
> On 11/08/2011 09:24 PM, Jeff Law wrote:
>> We don't have access to those assertions as they're removed well
>> prior to this pass running.  However, if we did, or if we had
>> redundant PHIs in the stream which were propagated we'd be
>> presented with something like
>> 
>> BB0  if (p_1) goto BB1 else goto BB2
>> 
>> BB1: ... goto BB3 BB2: BB3: p_2 = phi (p_1 (BB1), 0(BB2)) *p_2 =
>> 2;
>> 
>> 
>> We'd recognize that the edge bb2->bb3 is unexecutable as doing
>> so leads to a NULL pointer dereference.  Since the edge bb2->bb3
>> is not a critical edge, we know that bb2 as a whole is
>> unexecutable.  bb2 is control dependent on the edge bb0->bb2.
> 
> (Side note regarding critical edges: have you tried splitting them 
> before your pass?)
No.  The pass really came about at the last minute when I realized I
could take the warning work (which was not ready), twiddle it slightly
and get an optimization.

Critical edges don't really inhibit this optimizer.  They allow us to
trivially distinguish between the case where the whole block is
unexecutable vs just one of its outgoing edges being unexecutable.

If we were to split the critical edge, we would ultimately get the
same results in the end.

> 
> Ok, so that's exactly what I was thinking about.  In this case the 
> optimization is obviously allowed by the C standard; you have
> 
> if (p) something; *p = 0;
> 
> and the "*p = 0" has been in some sense translated to
> 
> if (!p) something; *p = 0;
> 
> which is only different on undefined paths.  But I'm not sure that
> more complicated cases, where there are other instructions between
> the "if" and "*p = 0", would also be allowed by the C standard.
> For example, I think a function call in the "else" branch, or
> between the PHI and the dereference should prevent the
> optimization, because the function call might never return for what
> we know.  Probably a volatile asm too.  Does your patch do that?
> (Testcases! :)).
My patch totally ignores the other code on the unexecutable path.  So
we can miss externally visible side effects, if we were to somehow get
on the unexecutable path.  But that's the whole point, in a conforming
program we can't ever get on the unexecutable path.



> In general, this is quite different from all other existing GCC 
> optimizations based on undefined behavior.  Whenever you trigger 
> undefined behavior, right now the effects do not extend *before*
> the undefined operation.  The proposed pass would change that, so
> that its effects are a bit more surprising when debugging.  If your
> bug is that you forgot a "return;" in the else branch, you surely
> wouldn't expect the compiler to swallow the entire branch.
> Unfortunately debugging at -O0 is not always an option.
Most certainly, it's controversial.  I'm still debating with myself
over whether or not this is a wise direction to take.

As I've mentioned elsewhere, this is something that fell into my lap
as I was working on a closely related warning.  The warning is, to me
at least, ultimately far more interesting than the optimization.
Triggering the warning tells us to look at the code for a few things.

  1. Truly incorrect code which leads to a NULL pointer dereference.
  2. Correct, but inefficient source, like we've seen for VEC_BASE.
  3. Missed optimizations, again like we've seen for VEC_BASE

Jeff
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iQEcBAEBAgAGBQJOur4eAAoJEBRtltQi2kC7t+MH/R2asrStW6dOOEOxuQWmKLIR
uYGkknGsv36KJOD+rnzulv3iNZW2ubYvYNBCkJAJn6/PjRDvV9T9/82ZHY9m2+Cb
SvWFOnP/gU8yEzksiS5fRB6rRzYOXUMX1/nXqmMDAfprRg9vYOBo34zQU93KonMT
k2GBtXSD5vFXX3VL6ffGSnQk9i59A0eSPMs+0q6n3pGztd9AjvgPkJAMDP3qep9m
jgCM0x+5gQwGzGCIVF65JqowAoqOaT3ZIGRajTvOZSa7N5gc+fvI3Czizb6lFr6R
Xls4Q/G3M2T5uXENvAN6SiN0Sv24WTEWxIoyKS0X1KTSC78gyG2QVAMFaYwRj6A=
=DOjd
-----END PGP SIGNATURE-----

Re: RFA: New pass to delete unexecutable paths in the CFG

[Jakub Jelinek]

On Wed, Nov 09, 2011 at 10:53:34AM -0700, Jeff Law wrote:
> > which is only different on undefined paths.  But I'm not sure that
> > more complicated cases, where there are other instructions between
> > the "if" and "*p = 0", would also be allowed by the C standard.
> > For example, I think a function call in the "else" branch, or
> > between the PHI and the dereference should prevent the
> > optimization, because the function call might never return for what
> > we know.  Probably a volatile asm too.  Does your patch do that?
> > (Testcases! :)).
> My patch totally ignores the other code on the unexecutable path.  So
> we can miss externally visible side effects, if we were to somehow get
> on the unexecutable path.  But that's the whole point, in a conforming
> program we can't ever get on the unexecutable path.

Well, side-effects that could be validly scheduled after the NULL pointer
dereference are just fine to be omitted.  But if there is a function call
that might call exit (0); in it, or throw an exception and thus never
reach the trap point, then omitting those would be an invalid optimization.

	Jakub

Re: RFA: New pass to delete unexecutable paths in the CFG

[Paolo Bonzini]

On 11/09/2011 06:53 PM, Jeff Law wrote:
> My patch totally ignores the other code on the unexecutable path.  So
> we can miss externally visible side effects, if we were to somehow get
> on the unexecutable path.  But that's the whole point, in a conforming
> program we can't ever get on the unexecutable path.

But if a subroutine call never returns, we wouldn't get to the undefined 
behavior in the first place.

Paolo

Re: RFA: New pass to delete unexecutable paths in the CFG

[Jeff Law]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 11/09/11 15:10, Paolo Bonzini wrote:
> On 11/09/2011 06:53 PM, Jeff Law wrote:
>> My patch totally ignores the other code on the unexecutable path.
>> So we can miss externally visible side effects, if we were to
>> somehow get on the unexecutable path.  But that's the whole
>> point, in a conforming program we can't ever get on the
>> unexecutable path.
> 
> But if a subroutine call never returns, we wouldn't get to the
> undefined behavior in the first place.
Yea, I'd been pondering this aspect as well.  The cases that most
concern me would be aborts and infinite loops.

Stuff like EH is represented in the CFG and the control dependence
stuff would ensure we do the right thing.

I think there are enough unanswered questions that we should defer
this until after 4.7 branches.  Or at the least not have the option on
by default for 4.7, even if the issues raised in the threads are
addressed.


Jeff
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iQEcBAEBAgAGBQJOvBvtAAoJEBRtltQi2kC7kmUH/j4KOxLwlgLJZmYEp1fPAvOp
riga57XaawnZtxnZYDwD8TQ8l5a2lsj8LMUthBUFq6Bl8NLTh4uJRAtWLbhS9D7Q
t1sl+2D2CjzdX4J2Ygs7asKrPld+OIFizttu6pYw9CZ2o4Ia21xnmLnDqtbkBiC6
BZ+qGtzjMetEZQhsQYYz8q/B44eF5Cnfsl5ISaKVaF2ZfR3dZGhoxqujuD1/bZtQ
Rijrg6uddiLQZrMvKT9WiJL+eoZYUvB1tTLD8tRs7e2YPSmQuxpmcN4JKc+DsPEF
d+n1ZWYSG2EmoHCaHwkSq0X5oxGjNz+hfbSpyM+sVXEubilM1BiEBvwegK22GWo=
=lPeq
-----END PGP SIGNATURE-----

RFA: disable -fdelete-null-pointer-checks for Java

[Jeff Law]

[-- Attachment #1: Type: text/plain, Size: 989 bytes --]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 11/07/11 09:56, Paolo Bonzini wrote:
 I'm not sure if GCC will currently delete the "if" statement in
> 
> try { x = x.getSomething(); } catch (NullPointerException npe) { }
> 
> if (x) ...
> 
> but even if it doesn't, the Java front-end should probably reset 
> flag_delete_null_pointer_checks.
Agreed.  Bootstrapped and regression tested on x86_64-unknown-linux-gnu.

OK for trunk?

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iQEcBAEBAgAGBQJOwfKUAAoJEBRtltQi2kC74vUIALaNiAGCHwU0ysflj4ZfqNjx
bMH/sUbkqCOx64xUbh43js8yPFvRZkcmLRgvJNc+D/XXhdvNbvGzWlFzzIgmjwnH
+a6G+fkuL5FkxhA9IrNWTH/IbYqf0onfnhcgNKgMdhEgdMxfwiScocye68TP7CrB
Jo/McnCe7xN9XVIvPTeSvz7q5mh5lOuoEhIFKyMGpFDE9vyMQpiPMkdZrNLwpmf7
IUS/V6Q6eIu9Z165DDMbR5DllQ7G9pclm7sZWmUgnF1jsIt22ZMhJPGJCyrSfSt3
efsxoT5pRoopbpdh0HAhQiS43KlPi75sQJwr73s48lhB4uPYEGjpj9JVniBB5l4=
=82BQ
-----END PGP SIGNATURE-----

[-- Attachment #2: P --]
[-- Type: text/plain, Size: 687 bytes --]

	* lang.c (java_init_options_struct): Disable optimizations
	which assume a NULL pointer dereference will cause a fault.

Index: lang.c
===================================================================
*** lang.c	(revision 181321)
--- lang.c	(working copy)
*************** java_init_options_struct (struct gcc_opt
*** 556,561 ****
--- 556,565 ----
  
    /* Java requires left-to-right evaluation of subexpressions.  */
    opts->x_flag_evaluation_order = 1;
+ 
+   /* Java catches catch NULL pointer exceptions, thus we can not necessarily
+      rely on a pointer having a non-NULL value after a dereference.  */
+   opts->x_flag_delete_null_pointer_checks = 0;
  }
  
  static void