public inbox for gcc-patches@gcc.gnu.org
 help / color / mirror / Atom feed
* RFA: New pass to delete unexecutable paths in the CFG
@ 2011-11-07  9:58 Jeff Law
  2011-11-07 10:19 ` Jakub Jelinek
  2011-11-07 14:16 ` Tom Tromey
  0 siblings, 2 replies; 31+ messages in thread
From: Jeff Law @ 2011-11-07  9:58 UTC (permalink / raw)
  To: gcc-patches

[-- 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 */
+  }
+ };

^ permalink raw reply	[flat|nested] 31+ messages in thread
end of thread, other threads:[~2011-11-15  5:03 UTC | newest]

Thread overview: 31+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2011-11-07  9:58 RFA: New pass to delete unexecutable paths in the CFG Jeff Law
2011-11-07 10:19 ` Jakub Jelinek
2011-11-07 10:21   ` Richard Guenther
2011-11-07 10:30     ` Richard Guenther
2011-11-07 19:20       ` Jeff Law
2011-11-07 16:14     ` Jeff Law
2011-11-07 16:30       ` Richard Guenther
2011-11-07 16:57         ` Kai Tietz
2011-11-07 19:03         ` Jeff Law
2011-11-08 11:50           ` Paolo Bonzini
2011-11-08 19:48             ` Jeff Law
2011-11-08 20:38               ` Paolo Bonzini
2011-11-08 20:59                 ` Jeff Law
2011-11-09  8:37                   ` Paolo Bonzini
2011-11-09 18:11                     ` Jeff Law
2011-11-09 18:12                       ` Jakub Jelinek
2011-11-09 22:45                       ` Paolo Bonzini
2011-11-10 19:27                         ` Jeff Law
2011-11-07 19:14   ` Jeff Law
2011-11-07 14:16 ` Tom Tromey
2011-11-07 15:54   ` Jeff Law
2011-11-07 15:54     ` Richard Guenther
2011-11-07 19:09       ` Jeff Law
2011-11-07 22:34         ` Richard Guenther
2011-11-08 20:02           ` Jeff Law
2011-11-09  9:50             ` Richard Guenther
2011-11-09 17:43               ` Jeff Law
2011-11-07 15:55     ` Tom Tromey
2011-11-07 17:01       ` Paolo Bonzini
2011-11-15  7:52         ` RFA: disable -fdelete-null-pointer-checks for Java Jeff Law
2011-11-07 19:05       ` RFA: New pass to delete unexecutable paths in the CFG Jeff Law

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