X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Ftree-ssa-dse.c;h=9559b4cb2f580d3cc0b47d1d9f70bce652173b9d;hb=49fce50b2ea8ff83917581815b997870ee2cb706;hp=4d929e1331b507543df4efa6736f442e320ec900;hpb=88dbf20f7cbfc296419f03e500ea15fd2161ded7;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/tree-ssa-dse.c b/gcc/tree-ssa-dse.c index 4d929e1331b..9559b4cb2f5 100644 --- a/gcc/tree-ssa-dse.c +++ b/gcc/tree-ssa-dse.c @@ -1,11 +1,12 @@ /* Dead store elimination - Copyright (C) 2004, 2005 Free Software Foundation, Inc. + Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009 + 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 2, or (at your option) +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, @@ -14,15 +15,13 @@ 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 COPYING. If not, write to -the Free Software Foundation, 59 Temple Place - Suite 330, -Boston, MA 02111-1307, USA. */ +along with GCC; see the file COPYING3. If not see +. */ #include "config.h" #include "system.h" #include "coretypes.h" #include "tm.h" -#include "errors.h" #include "ggc.h" #include "tree.h" #include "rtl.h" @@ -35,6 +34,7 @@ Boston, MA 02111-1307, USA. */ #include "tree-dump.h" #include "domwalk.h" #include "flags.h" +#include "langhooks.h" /* This file implements dead store elimination. @@ -64,7 +64,7 @@ Boston, MA 02111-1307, USA. */ relationship between dead store and redundant load elimination. In fact, they are the same transformation applied to different views of the CFG. */ - + struct dse_global_data { @@ -85,44 +85,28 @@ struct dse_block_local_data }; static bool gate_dse (void); -static void tree_ssa_dse (void); +static unsigned int tree_ssa_dse (void); static void dse_initialize_block_local_data (struct dom_walk_data *, basic_block, bool); -static void dse_optimize_stmt (struct dom_walk_data *, - basic_block, - block_stmt_iterator); -static void dse_record_phis (struct dom_walk_data *, basic_block); -static void dse_finalize_block (struct dom_walk_data *, basic_block); +static void dse_enter_block (struct dom_walk_data *, basic_block); +static void dse_leave_block (struct dom_walk_data *, basic_block); static void record_voperand_set (bitmap, bitmap *, unsigned int); -static unsigned max_stmt_uid; /* Maximal uid of a statement. Uids to phi - nodes are assigned using the versions of - ssa names they define. */ - /* Returns uid of statement STMT. */ static unsigned -get_stmt_uid (tree stmt) +get_stmt_uid (gimple stmt) { - if (TREE_CODE (stmt) == PHI_NODE) - return SSA_NAME_VERSION (PHI_RESULT (stmt)) + max_stmt_uid; - - return stmt_ann (stmt)->uid; -} + if (gimple_code (stmt) == GIMPLE_PHI) + return SSA_NAME_VERSION (gimple_phi_result (stmt)) + + gimple_stmt_max_uid (cfun); -/* Function indicating whether we ought to include information for 'var' - when calculating immediate uses. For this pass we only want use - information for virtual variables. */ - -static bool -need_imm_uses_for (tree var) -{ - return !is_gimple_reg (var); + return gimple_uid (stmt); } - /* Set bit UID in bitmaps GLOBAL and *LOCAL, creating *LOCAL as needed. */ + static void record_voperand_set (bitmap global, bitmap *local, unsigned int uid) { @@ -136,6 +120,7 @@ record_voperand_set (bitmap global, bitmap *local, unsigned int uid) bitmap_set_bit (*local, uid); bitmap_set_bit (global, uid); } + /* Initialize block local data structures. */ static void @@ -144,7 +129,8 @@ dse_initialize_block_local_data (struct dom_walk_data *walk_data, bool recycled) { struct dse_block_local_data *bd - = VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack); + = (struct dse_block_local_data *) + VEC_last (void_p, walk_data->block_data_stack); /* If we are given a recycled block local data structure, ensure any bitmap associated with the block is cleared. */ @@ -155,6 +141,117 @@ dse_initialize_block_local_data (struct dom_walk_data *walk_data, } } +/* A helper of dse_optimize_stmt. + Given a GIMPLE_ASSIGN in STMT, find a candidate statement *USE_STMT that + may prove STMT to be dead. + Return TRUE if the above conditions are met, otherwise FALSE. */ + +static bool +dse_possible_dead_store_p (gimple stmt, gimple *use_stmt) +{ + gimple temp; + unsigned cnt = 0; + + *use_stmt = NULL; + + /* Find the first dominated statement that clobbers (part of) the + memory stmt stores to with no intermediate statement that may use + part of the memory stmt stores. That is, find a store that may + prove stmt to be a dead store. */ + temp = stmt; + do + { + gimple prev, use_stmt; + imm_use_iterator ui; + bool fail = false; + tree defvar; + + /* Limit stmt walking to be linear in the number of possibly + dead stores. */ + if (++cnt > 256) + return false; + + if (gimple_code (temp) == GIMPLE_PHI) + defvar = PHI_RESULT (temp); + else + defvar = gimple_vdef (temp); + prev = temp; + temp = NULL; + FOR_EACH_IMM_USE_STMT (use_stmt, ui, defvar) + { + cnt++; + + /* In simple cases we can look through PHI nodes, but we + have to be careful with loops and with memory references + containing operands that are also operands of PHI nodes. + See gcc.c-torture/execute/20051110-*.c. */ + if (gimple_code (use_stmt) == GIMPLE_PHI) + { + if (temp + /* We can look through PHIs to post-dominated regions + without worrying if the use not also dominates prev + (in which case it would be a loop PHI with the use + in a latch block). */ + || gimple_bb (prev) == gimple_bb (use_stmt) + || !dominated_by_p (CDI_POST_DOMINATORS, + gimple_bb (prev), gimple_bb (use_stmt)) + || dominated_by_p (CDI_DOMINATORS, + gimple_bb (prev), gimple_bb (use_stmt))) + { + fail = true; + BREAK_FROM_IMM_USE_STMT (ui); + } + temp = use_stmt; + } + /* If the statement is a use the store is not dead. */ + else if (ref_maybe_used_by_stmt_p (use_stmt, + gimple_assign_lhs (stmt))) + { + fail = true; + BREAK_FROM_IMM_USE_STMT (ui); + } + /* If this is a store, remember it or bail out if we have + multiple ones (the will be in different CFG parts then). */ + else if (gimple_vdef (use_stmt)) + { + if (temp) + { + fail = true; + BREAK_FROM_IMM_USE_STMT (ui); + } + temp = use_stmt; + } + } + + if (fail) + return false; + + /* If we didn't find any definition this means the store is dead + if it isn't a store to global reachable memory. In this case + just pretend the stmt makes itself dead. Otherwise fail. */ + if (!temp) + { + if (is_hidden_global_store (stmt)) + return false; + + temp = stmt; + break; + } + } + /* We deliberately stop on clobbering statements and not only on + killing ones to make walking cheaper. Otherwise we can just + continue walking until both stores have equal reference trees. */ + while (!stmt_may_clobber_ref_p (temp, gimple_assign_lhs (stmt))); + + if (!is_gimple_assign (temp)) + return false; + + *use_stmt = temp; + + return true; +} + + /* Attempt to eliminate dead stores in the statement referenced by BSI. A dead store is a store into a memory location which will later be @@ -167,148 +264,118 @@ dse_initialize_block_local_data (struct dom_walk_data *walk_data, post dominates the first store, then the first store is dead. */ static void -dse_optimize_stmt (struct dom_walk_data *walk_data, - basic_block bb ATTRIBUTE_UNUSED, - block_stmt_iterator bsi) +dse_optimize_stmt (struct dse_global_data *dse_gd, + struct dse_block_local_data *bd, + gimple_stmt_iterator gsi) { - struct dse_block_local_data *bd - = VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack); - struct dse_global_data *dse_gd = walk_data->global_data; - tree stmt = bsi_stmt (bsi); - stmt_ann_t ann = stmt_ann (stmt); - v_may_def_optype v_may_defs; - - get_stmt_operands (stmt); - v_may_defs = V_MAY_DEF_OPS (ann); + gimple stmt = gsi_stmt (gsi); /* If this statement has no virtual defs, then there is nothing to do. */ - if (NUM_V_MAY_DEFS (v_may_defs) == 0) + if (!gimple_vdef (stmt)) return; - /* We know we have virtual definitions. If this is a MODIFY_EXPR that's - not also a function call, then record it into our table. */ - if (get_call_expr_in (stmt)) + /* We know we have virtual definitions. If this is a GIMPLE_ASSIGN + that's not also a function call, then record it into our table. */ + if (is_gimple_call (stmt) && gimple_call_fndecl (stmt)) return; - if (ann->has_volatile_ops) + if (gimple_has_volatile_ops (stmt)) return; - if (TREE_CODE (stmt) == MODIFY_EXPR) + if (is_gimple_assign (stmt)) { - unsigned int num_uses = 0, count = 0; - use_operand_p first_use_p = NULL_USE_OPERAND_P; - use_operand_p use_p; - tree use, use_stmt; - tree defvar = NULL_TREE, usevar = NULL_TREE; - use_operand_p var2; - def_operand_p var1; - ssa_op_iter op_iter; - - FOR_EACH_SSA_MAYDEF_OPERAND (var1, var2, stmt, op_iter) - { - defvar = DEF_FROM_PTR (var1); - usevar = USE_FROM_PTR (var2); - num_uses += num_imm_uses (defvar); - count++; - if (num_uses > 1 || count > 1) - break; - } + gimple use_stmt; - if (count == 1 && num_uses == 1) - { - single_imm_use (defvar, &use_p, &use_stmt); - gcc_assert (use_p != NULL_USE_OPERAND_P); - first_use_p = use_p; - use = USE_FROM_PTR (use_p); - } - else - { - record_voperand_set (dse_gd->stores, &bd->stores, ann->uid); - return; - } - - /* Skip through any PHI nodes we have already seen if the PHI - represents the only use of this store. + record_voperand_set (dse_gd->stores, &bd->stores, gimple_uid (stmt)); - Note this does not handle the case where the store has - multiple V_MAY_DEFs which all reach a set of PHI nodes in the - same block. */ - while (use_p != NULL_USE_OPERAND_P - && TREE_CODE (use_stmt) == PHI_NODE - && bitmap_bit_p (dse_gd->stores, get_stmt_uid (use_stmt))) - { - /* Skip past this PHI and loop again in case we had a PHI - chain. */ - if (single_imm_use (PHI_RESULT (use_stmt), &use_p, &use_stmt)) - use = USE_FROM_PTR (use_p); - } + if (!dse_possible_dead_store_p (stmt, &use_stmt)) + return; - /* If we have precisely one immediate use at this point, then we may - have found redundant store. */ - if (use_p != NULL_USE_OPERAND_P - && bitmap_bit_p (dse_gd->stores, get_stmt_uid (use_stmt)) - && operand_equal_p (TREE_OPERAND (stmt, 0), - TREE_OPERAND (use_stmt, 0), 0)) + /* If we have precisely one immediate use at this point and the + stores are to the same memory location or there is a chain of + virtual uses from stmt and the stmt which stores to that same + memory location, then we may have found redundant store. */ + if (bitmap_bit_p (dse_gd->stores, get_stmt_uid (use_stmt)) + && operand_equal_p (gimple_assign_lhs (stmt), + gimple_assign_lhs (use_stmt), 0)) { - tree def; - ssa_op_iter iter; - - /* Make sure we propagate the ABNORMAL bit setting. */ - if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (first_use_p))) - SSA_NAME_OCCURS_IN_ABNORMAL_PHI (usevar) = 1; - /* Then we need to fix the operand of the consuming stmt. */ - SET_USE (first_use_p, usevar); + /* If use_stmt is or might be a nop assignment, e.g. for + struct { ... } S a, b, *p; ... + b = a; b = b; + or + b = a; b = *p; where p might be &b, + or + *p = a; *p = b; where p might be &b, + or + *p = *u; *p = *v; where p might be v, then USE_STMT + acts as a use as well as definition, so store in STMT + is not dead. */ + if (stmt != use_stmt + && !is_gimple_reg (gimple_assign_rhs1 (use_stmt)) + && !is_gimple_min_invariant (gimple_assign_rhs1 (use_stmt)) + /* ??? Should {} be invariant? */ + && gimple_assign_rhs_code (use_stmt) != CONSTRUCTOR + && refs_may_alias_p (gimple_assign_lhs (use_stmt), + gimple_assign_rhs1 (use_stmt))) + return; if (dump_file && (dump_flags & TDF_DETAILS)) { fprintf (dump_file, " Deleted dead store '"); - print_generic_expr (dump_file, bsi_stmt (bsi), dump_flags); + print_gimple_stmt (dump_file, gsi_stmt (gsi), dump_flags, 0); fprintf (dump_file, "'\n"); } - /* Remove the dead store. */ - bsi_remove (&bsi); + /* Then we need to fix the operand of the consuming stmt. */ + unlink_stmt_vdef (stmt); - /* The virtual defs for the dead statement will need to be - updated. Since these names are going to disappear, - FUD chains for uses downstream need to be updated. */ - FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_VIRTUAL_DEFS) - mark_sym_for_renaming (SSA_NAME_VAR (def)); + /* Remove the dead store. */ + gsi_remove (&gsi, true); /* And release any SSA_NAMEs set in this statement back to the SSA_NAME manager. */ release_defs (stmt); } - - record_voperand_set (dse_gd->stores, &bd->stores, ann->uid); } } /* Record that we have seen the PHIs at the start of BB which correspond to virtual operands. */ static void -dse_record_phis (struct dom_walk_data *walk_data, basic_block bb) +dse_record_phi (struct dse_global_data *dse_gd, + struct dse_block_local_data *bd, + gimple phi) +{ + if (!is_gimple_reg (gimple_phi_result (phi))) + record_voperand_set (dse_gd->stores, &bd->stores, get_stmt_uid (phi)); +} + +static void +dse_enter_block (struct dom_walk_data *walk_data, basic_block bb) { struct dse_block_local_data *bd - = VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack); - struct dse_global_data *dse_gd = walk_data->global_data; - tree phi; - - for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) - if (need_imm_uses_for (PHI_RESULT (phi))) - record_voperand_set (dse_gd->stores, - &bd->stores, - get_stmt_uid (phi)); + = (struct dse_block_local_data *) + VEC_last (void_p, walk_data->block_data_stack); + struct dse_global_data *dse_gd + = (struct dse_global_data *) walk_data->global_data; + gimple_stmt_iterator gsi; + + for (gsi = gsi_last (bb_seq (bb)); !gsi_end_p (gsi); gsi_prev (&gsi)) + dse_optimize_stmt (dse_gd, bd, gsi); + for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) + dse_record_phi (dse_gd, bd, gsi_stmt (gsi)); } static void -dse_finalize_block (struct dom_walk_data *walk_data, - basic_block bb ATTRIBUTE_UNUSED) +dse_leave_block (struct dom_walk_data *walk_data, + basic_block bb ATTRIBUTE_UNUSED) { struct dse_block_local_data *bd - = VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack); - struct dse_global_data *dse_gd = walk_data->global_data; + = (struct dse_block_local_data *) + VEC_last (void_p, walk_data->block_data_stack); + struct dse_global_data *dse_gd + = (struct dse_global_data *) walk_data->global_data; bitmap stores = dse_gd->stores; unsigned int i; bitmap_iterator bi; @@ -321,42 +388,29 @@ dse_finalize_block (struct dom_walk_data *walk_data, } } -static void +/* Main entry point. */ + +static unsigned int tree_ssa_dse (void) { struct dom_walk_data walk_data; struct dse_global_data dse_gd; - basic_block bb; - /* Create a UID for each statement in the function. Ordering of the - UIDs is not important for this pass. */ - max_stmt_uid = 0; - FOR_EACH_BB (bb) - { - block_stmt_iterator bsi; - - for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) - stmt_ann (bsi_stmt (bsi))->uid = max_stmt_uid++; - } + renumber_gimple_stmt_uids (); /* We might consider making this a property of each pass so that it can be [re]computed on an as-needed basis. Particularly since this pass could be seen as an extension of DCE which needs post dominators. */ calculate_dominance_info (CDI_POST_DOMINATORS); + calculate_dominance_info (CDI_DOMINATORS); /* Dead store elimination is fundamentally a walk of the post-dominator tree and a backwards walk of statements within each block. */ - walk_data.walk_stmts_backward = true; walk_data.dom_direction = CDI_POST_DOMINATORS; walk_data.initialize_block_local_data = dse_initialize_block_local_data; - walk_data.before_dom_children_before_stmts = NULL; - walk_data.before_dom_children_walk_stmts = dse_optimize_stmt; - walk_data.before_dom_children_after_stmts = dse_record_phis; - walk_data.after_dom_children_before_stmts = NULL; - walk_data.after_dom_children_walk_stmts = NULL; - walk_data.after_dom_children_after_stmts = dse_finalize_block; - walk_data.interesting_blocks = NULL; + walk_data.before_dom_children = dse_enter_block; + walk_data.after_dom_children = dse_leave_block; walk_data.block_local_data_size = sizeof (struct dse_block_local_data); @@ -378,6 +432,7 @@ tree_ssa_dse (void) /* For now, just wipe the post-dominator information. */ free_dominance_info (CDI_POST_DOMINATORS); + return 0; } static bool @@ -386,7 +441,10 @@ gate_dse (void) return flag_tree_dse != 0; } -struct tree_opt_pass pass_dse = { +struct gimple_opt_pass pass_dse = +{ + { + GIMPLE_PASS, "dse", /* name */ gate_dse, /* gate */ tree_ssa_dse, /* execute */ @@ -394,15 +452,13 @@ struct tree_opt_pass pass_dse = { NULL, /* next */ 0, /* static_pass_number */ TV_TREE_DSE, /* tv_id */ - PROP_cfg - | PROP_ssa - | PROP_alias, /* properties_required */ + PROP_cfg | PROP_ssa, /* properties_required */ 0, /* properties_provided */ 0, /* properties_destroyed */ 0, /* todo_flags_start */ TODO_dump_func | TODO_ggc_collect - | TODO_update_ssa - | TODO_verify_ssa, /* todo_flags_finish */ - 0 /* letter */ + | TODO_verify_ssa /* todo_flags_finish */ + } }; +