From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 13962 invoked by alias); 7 Nov 2011 09:55:29 -0000 Received: (qmail 13933 invoked by uid 22791); 7 Nov 2011 09:55:24 -0000 X-SWARE-Spam-Status: No, hits=-7.4 required=5.0 tests=AWL,BAYES_00,RCVD_IN_DNSWL_HI,RP_MATCHES_RCVD,SPF_HELO_PASS,TW_CF,TW_TM X-Spam-Check-By: sourceware.org Received: from mx1.redhat.com (HELO mx1.redhat.com) (209.132.183.28) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Mon, 07 Nov 2011 09:55:05 +0000 Received: from int-mx01.intmail.prod.int.phx2.redhat.com (int-mx01.intmail.prod.int.phx2.redhat.com [10.5.11.11]) by mx1.redhat.com (8.14.4/8.14.4) with ESMTP id pA79t4Qp024539 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=OK) for ; Mon, 7 Nov 2011 04:55:04 -0500 Received: from ns3.rdu.redhat.com (ns3.rdu.redhat.com [10.11.255.199]) by int-mx01.intmail.prod.int.phx2.redhat.com (8.13.8/8.13.8) with ESMTP id pA79t39N013146 for ; Mon, 7 Nov 2011 04:55:04 -0500 Received: from [10.3.113.8] ([10.3.113.8]) by ns3.rdu.redhat.com (8.13.8/8.13.8) with ESMTP id pA79t2jK019658 for ; Mon, 7 Nov 2011 04:55:03 -0500 Message-ID: <4EB7AAF6.6060702@redhat.com> Date: Mon, 07 Nov 2011 09:58:00 -0000 From: Jeff Law User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:7.0) Gecko/20110927 Thunderbird/7.0 MIME-Version: 1.0 To: gcc-patches Subject: RFA: New pass to delete unexecutable paths in the CFG Content-Type: multipart/mixed; boundary="------------010105060502070801000402" X-IsSubscribed: yes Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org X-SW-Source: 2011-11/txt/msg00893.txt.bz2 This is a multi-part message in MIME format. --------------010105060502070801000402 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Content-length: 2850 -----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----- --------------010105060502070801000402 Content-Type: text/plain; name="P" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="P" Content-length: 28840 * 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 + . */ + + #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 + . */ + + /* 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 + . */ + + #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 */ + } + }; --------------010105060502070801000402--