/* Dead code elimination pass for the GNU compiler.
|
/* Dead code elimination pass for the GNU compiler.
|
Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011
|
Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011
|
Free Software Foundation, Inc.
|
Free Software Foundation, Inc.
|
Contributed by Ben Elliston <bje@redhat.com>
|
Contributed by Ben Elliston <bje@redhat.com>
|
and Andrew MacLeod <amacleod@redhat.com>
|
and Andrew MacLeod <amacleod@redhat.com>
|
Adapted to use control dependence by Steven Bosscher, SUSE Labs.
|
Adapted to use control dependence by Steven Bosscher, SUSE Labs.
|
|
|
This file is part of GCC.
|
This file is part of GCC.
|
|
|
GCC is free software; you can redistribute it and/or modify it
|
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
|
under the terms of the GNU General Public License as published by the
|
Free Software Foundation; either version 3, or (at your option) any
|
Free Software Foundation; either version 3, or (at your option) any
|
later version.
|
later version.
|
|
|
GCC is distributed in the hope that it will be useful, but WITHOUT
|
GCC is distributed in the hope that it will be useful, but WITHOUT
|
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
for more details.
|
for more details.
|
|
|
You should have received a copy of the GNU General Public License
|
You should have received a copy of the GNU General Public License
|
along with GCC; see the file COPYING3. If not see
|
along with GCC; see the file COPYING3. If not see
|
<http://www.gnu.org/licenses/>. */
|
<http://www.gnu.org/licenses/>. */
|
|
|
/* Dead code elimination.
|
/* Dead code elimination.
|
|
|
References:
|
References:
|
|
|
Building an Optimizing Compiler,
|
Building an Optimizing Compiler,
|
Robert Morgan, Butterworth-Heinemann, 1998, Section 8.9.
|
Robert Morgan, Butterworth-Heinemann, 1998, Section 8.9.
|
|
|
Advanced Compiler Design and Implementation,
|
Advanced Compiler Design and Implementation,
|
Steven Muchnick, Morgan Kaufmann, 1997, Section 18.10.
|
Steven Muchnick, Morgan Kaufmann, 1997, Section 18.10.
|
|
|
Dead-code elimination is the removal of statements which have no
|
Dead-code elimination is the removal of statements which have no
|
impact on the program's output. "Dead statements" have no impact
|
impact on the program's output. "Dead statements" have no impact
|
on the program's output, while "necessary statements" may have
|
on the program's output, while "necessary statements" may have
|
impact on the output.
|
impact on the output.
|
|
|
The algorithm consists of three phases:
|
The algorithm consists of three phases:
|
1. Marking as necessary all statements known to be necessary,
|
1. Marking as necessary all statements known to be necessary,
|
e.g. most function calls, writing a value to memory, etc;
|
e.g. most function calls, writing a value to memory, etc;
|
2. Propagating necessary statements, e.g., the statements
|
2. Propagating necessary statements, e.g., the statements
|
giving values to operands in necessary statements; and
|
giving values to operands in necessary statements; and
|
3. Removing dead statements. */
|
3. Removing dead statements. */
|
|
|
#include "config.h"
|
#include "config.h"
|
#include "system.h"
|
#include "system.h"
|
#include "coretypes.h"
|
#include "coretypes.h"
|
#include "tm.h"
|
#include "tm.h"
|
|
|
#include "tree.h"
|
#include "tree.h"
|
#include "tree-pretty-print.h"
|
#include "tree-pretty-print.h"
|
#include "gimple-pretty-print.h"
|
#include "gimple-pretty-print.h"
|
#include "basic-block.h"
|
#include "basic-block.h"
|
#include "tree-flow.h"
|
#include "tree-flow.h"
|
#include "gimple.h"
|
#include "gimple.h"
|
#include "tree-dump.h"
|
#include "tree-dump.h"
|
#include "tree-pass.h"
|
#include "tree-pass.h"
|
#include "timevar.h"
|
#include "timevar.h"
|
#include "flags.h"
|
#include "flags.h"
|
#include "cfgloop.h"
|
#include "cfgloop.h"
|
#include "tree-scalar-evolution.h"
|
#include "tree-scalar-evolution.h"
|
|
|
static struct stmt_stats
|
static struct stmt_stats
|
{
|
{
|
int total;
|
int total;
|
int total_phis;
|
int total_phis;
|
int removed;
|
int removed;
|
int removed_phis;
|
int removed_phis;
|
} stats;
|
} stats;
|
|
|
#define STMT_NECESSARY GF_PLF_1
|
#define STMT_NECESSARY GF_PLF_1
|
|
|
static VEC(gimple,heap) *worklist;
|
static VEC(gimple,heap) *worklist;
|
|
|
/* Vector indicating an SSA name has already been processed and marked
|
/* Vector indicating an SSA name has already been processed and marked
|
as necessary. */
|
as necessary. */
|
static sbitmap processed;
|
static sbitmap processed;
|
|
|
/* Vector indicating that the last statement of a basic block has already
|
/* Vector indicating that the last statement of a basic block has already
|
been marked as necessary. */
|
been marked as necessary. */
|
static sbitmap last_stmt_necessary;
|
static sbitmap last_stmt_necessary;
|
|
|
/* Vector indicating that BB contains statements that are live. */
|
/* Vector indicating that BB contains statements that are live. */
|
static sbitmap bb_contains_live_stmts;
|
static sbitmap bb_contains_live_stmts;
|
|
|
/* Before we can determine whether a control branch is dead, we need to
|
/* Before we can determine whether a control branch is dead, we need to
|
compute which blocks are control dependent on which edges.
|
compute which blocks are control dependent on which edges.
|
|
|
We expect each block to be control dependent on very few edges so we
|
We expect each block to be control dependent on very few edges so we
|
use a bitmap for each block recording its edges. An array holds the
|
use a bitmap for each block recording its edges. An array holds the
|
bitmap. The Ith bit in the bitmap is set if that block is dependent
|
bitmap. The Ith bit in the bitmap is set if that block is dependent
|
on the Ith edge. */
|
on the Ith edge. */
|
static bitmap *control_dependence_map;
|
static bitmap *control_dependence_map;
|
|
|
/* Vector indicating that a basic block has already had all the edges
|
/* Vector indicating that a basic block has already had all the edges
|
processed that it is control dependent on. */
|
processed that it is control dependent on. */
|
static sbitmap visited_control_parents;
|
static sbitmap visited_control_parents;
|
|
|
/* TRUE if this pass alters the CFG (by removing control statements).
|
/* TRUE if this pass alters the CFG (by removing control statements).
|
FALSE otherwise.
|
FALSE otherwise.
|
|
|
If this pass alters the CFG, then it will arrange for the dominators
|
If this pass alters the CFG, then it will arrange for the dominators
|
to be recomputed. */
|
to be recomputed. */
|
static bool cfg_altered;
|
static bool cfg_altered;
|
|
|
/* Execute code that follows the macro for each edge (given number
|
/* Execute code that follows the macro for each edge (given number
|
EDGE_NUMBER within the CODE) for which the block with index N is
|
EDGE_NUMBER within the CODE) for which the block with index N is
|
control dependent. */
|
control dependent. */
|
#define EXECUTE_IF_CONTROL_DEPENDENT(BI, N, EDGE_NUMBER) \
|
#define EXECUTE_IF_CONTROL_DEPENDENT(BI, N, EDGE_NUMBER) \
|
EXECUTE_IF_SET_IN_BITMAP (control_dependence_map[(N)], 0, \
|
EXECUTE_IF_SET_IN_BITMAP (control_dependence_map[(N)], 0, \
|
(EDGE_NUMBER), (BI))
|
(EDGE_NUMBER), (BI))
|
|
|
|
|
/* Indicate block BB is control dependent on an edge with index EDGE_INDEX. */
|
/* Indicate block BB is control dependent on an edge with index EDGE_INDEX. */
|
static inline void
|
static inline void
|
set_control_dependence_map_bit (basic_block bb, int edge_index)
|
set_control_dependence_map_bit (basic_block bb, int edge_index)
|
{
|
{
|
if (bb == ENTRY_BLOCK_PTR)
|
if (bb == ENTRY_BLOCK_PTR)
|
return;
|
return;
|
gcc_assert (bb != EXIT_BLOCK_PTR);
|
gcc_assert (bb != EXIT_BLOCK_PTR);
|
bitmap_set_bit (control_dependence_map[bb->index], edge_index);
|
bitmap_set_bit (control_dependence_map[bb->index], edge_index);
|
}
|
}
|
|
|
/* Clear all control dependences for block BB. */
|
/* Clear all control dependences for block BB. */
|
static inline void
|
static inline void
|
clear_control_dependence_bitmap (basic_block bb)
|
clear_control_dependence_bitmap (basic_block bb)
|
{
|
{
|
bitmap_clear (control_dependence_map[bb->index]);
|
bitmap_clear (control_dependence_map[bb->index]);
|
}
|
}
|
|
|
|
|
/* Find the immediate postdominator PDOM of the specified basic block BLOCK.
|
/* Find the immediate postdominator PDOM of the specified basic block BLOCK.
|
This function is necessary because some blocks have negative numbers. */
|
This function is necessary because some blocks have negative numbers. */
|
|
|
static inline basic_block
|
static inline basic_block
|
find_pdom (basic_block block)
|
find_pdom (basic_block block)
|
{
|
{
|
gcc_assert (block != ENTRY_BLOCK_PTR);
|
gcc_assert (block != ENTRY_BLOCK_PTR);
|
|
|
if (block == EXIT_BLOCK_PTR)
|
if (block == EXIT_BLOCK_PTR)
|
return EXIT_BLOCK_PTR;
|
return EXIT_BLOCK_PTR;
|
else
|
else
|
{
|
{
|
basic_block bb = get_immediate_dominator (CDI_POST_DOMINATORS, block);
|
basic_block bb = get_immediate_dominator (CDI_POST_DOMINATORS, block);
|
if (! bb)
|
if (! bb)
|
return EXIT_BLOCK_PTR;
|
return EXIT_BLOCK_PTR;
|
return bb;
|
return bb;
|
}
|
}
|
}
|
}
|
|
|
|
|
/* Determine all blocks' control dependences on the given edge with edge_list
|
/* Determine all blocks' control dependences on the given edge with edge_list
|
EL index EDGE_INDEX, ala Morgan, Section 3.6. */
|
EL index EDGE_INDEX, ala Morgan, Section 3.6. */
|
|
|
static void
|
static void
|
find_control_dependence (struct edge_list *el, int edge_index)
|
find_control_dependence (struct edge_list *el, int edge_index)
|
{
|
{
|
basic_block current_block;
|
basic_block current_block;
|
basic_block ending_block;
|
basic_block ending_block;
|
|
|
gcc_assert (INDEX_EDGE_PRED_BB (el, edge_index) != EXIT_BLOCK_PTR);
|
gcc_assert (INDEX_EDGE_PRED_BB (el, edge_index) != EXIT_BLOCK_PTR);
|
|
|
if (INDEX_EDGE_PRED_BB (el, edge_index) == ENTRY_BLOCK_PTR)
|
if (INDEX_EDGE_PRED_BB (el, edge_index) == ENTRY_BLOCK_PTR)
|
ending_block = single_succ (ENTRY_BLOCK_PTR);
|
ending_block = single_succ (ENTRY_BLOCK_PTR);
|
else
|
else
|
ending_block = find_pdom (INDEX_EDGE_PRED_BB (el, edge_index));
|
ending_block = find_pdom (INDEX_EDGE_PRED_BB (el, edge_index));
|
|
|
for (current_block = INDEX_EDGE_SUCC_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 != ending_block && current_block != EXIT_BLOCK_PTR;
|
current_block = find_pdom (current_block))
|
current_block = find_pdom (current_block))
|
{
|
{
|
edge e = INDEX_EDGE (el, edge_index);
|
edge e = INDEX_EDGE (el, edge_index);
|
|
|
/* For abnormal edges, we don't make current_block control
|
/* For abnormal edges, we don't make current_block control
|
dependent because instructions that throw are always necessary
|
dependent because instructions that throw are always necessary
|
anyway. */
|
anyway. */
|
if (e->flags & EDGE_ABNORMAL)
|
if (e->flags & EDGE_ABNORMAL)
|
continue;
|
continue;
|
|
|
set_control_dependence_map_bit (current_block, edge_index);
|
set_control_dependence_map_bit (current_block, edge_index);
|
}
|
}
|
}
|
}
|
|
|
|
|
/* Record all blocks' control dependences on all edges in the edge
|
/* Record all blocks' control dependences on all edges in the edge
|
list EL, ala Morgan, Section 3.6. */
|
list EL, ala Morgan, Section 3.6. */
|
|
|
static void
|
static void
|
find_all_control_dependences (struct edge_list *el)
|
find_all_control_dependences (struct edge_list *el)
|
{
|
{
|
int i;
|
int i;
|
|
|
for (i = 0; i < NUM_EDGES (el); ++i)
|
for (i = 0; i < NUM_EDGES (el); ++i)
|
find_control_dependence (el, i);
|
find_control_dependence (el, i);
|
}
|
}
|
|
|
/* If STMT is not already marked necessary, mark it, and add it to the
|
/* If STMT is not already marked necessary, mark it, and add it to the
|
worklist if ADD_TO_WORKLIST is true. */
|
worklist if ADD_TO_WORKLIST is true. */
|
|
|
static inline void
|
static inline void
|
mark_stmt_necessary (gimple stmt, bool add_to_worklist)
|
mark_stmt_necessary (gimple stmt, bool add_to_worklist)
|
{
|
{
|
gcc_assert (stmt);
|
gcc_assert (stmt);
|
|
|
if (gimple_plf (stmt, STMT_NECESSARY))
|
if (gimple_plf (stmt, STMT_NECESSARY))
|
return;
|
return;
|
|
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
{
|
{
|
fprintf (dump_file, "Marking useful stmt: ");
|
fprintf (dump_file, "Marking useful stmt: ");
|
print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
|
print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
|
fprintf (dump_file, "\n");
|
fprintf (dump_file, "\n");
|
}
|
}
|
|
|
gimple_set_plf (stmt, STMT_NECESSARY, true);
|
gimple_set_plf (stmt, STMT_NECESSARY, true);
|
if (add_to_worklist)
|
if (add_to_worklist)
|
VEC_safe_push (gimple, heap, worklist, stmt);
|
VEC_safe_push (gimple, heap, worklist, stmt);
|
if (bb_contains_live_stmts && !is_gimple_debug (stmt))
|
if (bb_contains_live_stmts && !is_gimple_debug (stmt))
|
SET_BIT (bb_contains_live_stmts, gimple_bb (stmt)->index);
|
SET_BIT (bb_contains_live_stmts, gimple_bb (stmt)->index);
|
}
|
}
|
|
|
|
|
/* Mark the statement defining operand OP as necessary. */
|
/* Mark the statement defining operand OP as necessary. */
|
|
|
static inline void
|
static inline void
|
mark_operand_necessary (tree op)
|
mark_operand_necessary (tree op)
|
{
|
{
|
gimple stmt;
|
gimple stmt;
|
int ver;
|
int ver;
|
|
|
gcc_assert (op);
|
gcc_assert (op);
|
|
|
ver = SSA_NAME_VERSION (op);
|
ver = SSA_NAME_VERSION (op);
|
if (TEST_BIT (processed, ver))
|
if (TEST_BIT (processed, ver))
|
{
|
{
|
stmt = SSA_NAME_DEF_STMT (op);
|
stmt = SSA_NAME_DEF_STMT (op);
|
gcc_assert (gimple_nop_p (stmt)
|
gcc_assert (gimple_nop_p (stmt)
|
|| gimple_plf (stmt, STMT_NECESSARY));
|
|| gimple_plf (stmt, STMT_NECESSARY));
|
return;
|
return;
|
}
|
}
|
SET_BIT (processed, ver);
|
SET_BIT (processed, ver);
|
|
|
stmt = SSA_NAME_DEF_STMT (op);
|
stmt = SSA_NAME_DEF_STMT (op);
|
gcc_assert (stmt);
|
gcc_assert (stmt);
|
|
|
if (gimple_plf (stmt, STMT_NECESSARY) || gimple_nop_p (stmt))
|
if (gimple_plf (stmt, STMT_NECESSARY) || gimple_nop_p (stmt))
|
return;
|
return;
|
|
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
{
|
{
|
fprintf (dump_file, "marking necessary through ");
|
fprintf (dump_file, "marking necessary through ");
|
print_generic_expr (dump_file, op, 0);
|
print_generic_expr (dump_file, op, 0);
|
fprintf (dump_file, " stmt ");
|
fprintf (dump_file, " stmt ");
|
print_gimple_stmt (dump_file, stmt, 0, 0);
|
print_gimple_stmt (dump_file, stmt, 0, 0);
|
}
|
}
|
|
|
gimple_set_plf (stmt, STMT_NECESSARY, true);
|
gimple_set_plf (stmt, STMT_NECESSARY, true);
|
if (bb_contains_live_stmts)
|
if (bb_contains_live_stmts)
|
SET_BIT (bb_contains_live_stmts, gimple_bb (stmt)->index);
|
SET_BIT (bb_contains_live_stmts, gimple_bb (stmt)->index);
|
VEC_safe_push (gimple, heap, worklist, stmt);
|
VEC_safe_push (gimple, heap, worklist, stmt);
|
}
|
}
|
|
|
|
|
/* Mark STMT as necessary if it obviously is. Add it to the worklist if
|
/* Mark STMT as necessary if it obviously is. Add it to the worklist if
|
it can make other statements necessary.
|
it can make other statements necessary.
|
|
|
If AGGRESSIVE is false, control statements are conservatively marked as
|
If AGGRESSIVE is false, control statements are conservatively marked as
|
necessary. */
|
necessary. */
|
|
|
static void
|
static void
|
mark_stmt_if_obviously_necessary (gimple stmt, bool aggressive)
|
mark_stmt_if_obviously_necessary (gimple stmt, bool aggressive)
|
{
|
{
|
/* With non-call exceptions, we have to assume that all statements could
|
/* With non-call exceptions, we have to assume that all statements could
|
throw. If a statement may throw, it is inherently necessary. */
|
throw. If a statement may throw, it is inherently necessary. */
|
if (cfun->can_throw_non_call_exceptions && stmt_could_throw_p (stmt))
|
if (cfun->can_throw_non_call_exceptions && stmt_could_throw_p (stmt))
|
{
|
{
|
mark_stmt_necessary (stmt, true);
|
mark_stmt_necessary (stmt, true);
|
return;
|
return;
|
}
|
}
|
|
|
/* Statements that are implicitly live. Most function calls, asm
|
/* Statements that are implicitly live. Most function calls, asm
|
and return statements are required. Labels and GIMPLE_BIND nodes
|
and return statements are required. Labels and GIMPLE_BIND nodes
|
are kept because they are control flow, and we have no way of
|
are kept because they are control flow, and we have no way of
|
knowing whether they can be removed. DCE can eliminate all the
|
knowing whether they can be removed. DCE can eliminate all the
|
other statements in a block, and CFG can then remove the block
|
other statements in a block, and CFG can then remove the block
|
and labels. */
|
and labels. */
|
switch (gimple_code (stmt))
|
switch (gimple_code (stmt))
|
{
|
{
|
case GIMPLE_PREDICT:
|
case GIMPLE_PREDICT:
|
case GIMPLE_LABEL:
|
case GIMPLE_LABEL:
|
mark_stmt_necessary (stmt, false);
|
mark_stmt_necessary (stmt, false);
|
return;
|
return;
|
|
|
case GIMPLE_ASM:
|
case GIMPLE_ASM:
|
case GIMPLE_RESX:
|
case GIMPLE_RESX:
|
case GIMPLE_RETURN:
|
case GIMPLE_RETURN:
|
mark_stmt_necessary (stmt, true);
|
mark_stmt_necessary (stmt, true);
|
return;
|
return;
|
|
|
case GIMPLE_CALL:
|
case GIMPLE_CALL:
|
{
|
{
|
tree callee = gimple_call_fndecl (stmt);
|
tree callee = gimple_call_fndecl (stmt);
|
if (callee != NULL_TREE
|
if (callee != NULL_TREE
|
&& DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL)
|
&& DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL)
|
switch (DECL_FUNCTION_CODE (callee))
|
switch (DECL_FUNCTION_CODE (callee))
|
{
|
{
|
case BUILT_IN_MALLOC:
|
case BUILT_IN_MALLOC:
|
case BUILT_IN_CALLOC:
|
case BUILT_IN_CALLOC:
|
case BUILT_IN_ALLOCA:
|
case BUILT_IN_ALLOCA:
|
case BUILT_IN_ALLOCA_WITH_ALIGN:
|
case BUILT_IN_ALLOCA_WITH_ALIGN:
|
return;
|
return;
|
|
|
default:;
|
default:;
|
}
|
}
|
/* Most, but not all function calls are required. Function calls that
|
/* Most, but not all function calls are required. Function calls that
|
produce no result and have no side effects (i.e. const pure
|
produce no result and have no side effects (i.e. const pure
|
functions) are unnecessary. */
|
functions) are unnecessary. */
|
if (gimple_has_side_effects (stmt))
|
if (gimple_has_side_effects (stmt))
|
{
|
{
|
mark_stmt_necessary (stmt, true);
|
mark_stmt_necessary (stmt, true);
|
return;
|
return;
|
}
|
}
|
if (!gimple_call_lhs (stmt))
|
if (!gimple_call_lhs (stmt))
|
return;
|
return;
|
break;
|
break;
|
}
|
}
|
|
|
case GIMPLE_DEBUG:
|
case GIMPLE_DEBUG:
|
/* Debug temps without a value are not useful. ??? If we could
|
/* Debug temps without a value are not useful. ??? If we could
|
easily locate the debug temp bind stmt for a use thereof,
|
easily locate the debug temp bind stmt for a use thereof,
|
would could refrain from marking all debug temps here, and
|
would could refrain from marking all debug temps here, and
|
mark them only if they're used. */
|
mark them only if they're used. */
|
if (!gimple_debug_bind_p (stmt)
|
if (!gimple_debug_bind_p (stmt)
|
|| gimple_debug_bind_has_value_p (stmt)
|
|| gimple_debug_bind_has_value_p (stmt)
|
|| TREE_CODE (gimple_debug_bind_get_var (stmt)) != DEBUG_EXPR_DECL)
|
|| TREE_CODE (gimple_debug_bind_get_var (stmt)) != DEBUG_EXPR_DECL)
|
mark_stmt_necessary (stmt, false);
|
mark_stmt_necessary (stmt, false);
|
return;
|
return;
|
|
|
case GIMPLE_GOTO:
|
case GIMPLE_GOTO:
|
gcc_assert (!simple_goto_p (stmt));
|
gcc_assert (!simple_goto_p (stmt));
|
mark_stmt_necessary (stmt, true);
|
mark_stmt_necessary (stmt, true);
|
return;
|
return;
|
|
|
case GIMPLE_COND:
|
case GIMPLE_COND:
|
gcc_assert (EDGE_COUNT (gimple_bb (stmt)->succs) == 2);
|
gcc_assert (EDGE_COUNT (gimple_bb (stmt)->succs) == 2);
|
/* Fall through. */
|
/* Fall through. */
|
|
|
case GIMPLE_SWITCH:
|
case GIMPLE_SWITCH:
|
if (! aggressive)
|
if (! aggressive)
|
mark_stmt_necessary (stmt, true);
|
mark_stmt_necessary (stmt, true);
|
break;
|
break;
|
|
|
case GIMPLE_ASSIGN:
|
case GIMPLE_ASSIGN:
|
if (TREE_CODE (gimple_assign_lhs (stmt)) == SSA_NAME
|
if (TREE_CODE (gimple_assign_lhs (stmt)) == SSA_NAME
|
&& TREE_CLOBBER_P (gimple_assign_rhs1 (stmt)))
|
&& TREE_CLOBBER_P (gimple_assign_rhs1 (stmt)))
|
return;
|
return;
|
break;
|
break;
|
|
|
default:
|
default:
|
break;
|
break;
|
}
|
}
|
|
|
/* If the statement has volatile operands, it needs to be preserved.
|
/* If the statement has volatile operands, it needs to be preserved.
|
Same for statements that can alter control flow in unpredictable
|
Same for statements that can alter control flow in unpredictable
|
ways. */
|
ways. */
|
if (gimple_has_volatile_ops (stmt) || is_ctrl_altering_stmt (stmt))
|
if (gimple_has_volatile_ops (stmt) || is_ctrl_altering_stmt (stmt))
|
{
|
{
|
mark_stmt_necessary (stmt, true);
|
mark_stmt_necessary (stmt, true);
|
return;
|
return;
|
}
|
}
|
|
|
if (is_hidden_global_store (stmt))
|
if (is_hidden_global_store (stmt))
|
{
|
{
|
mark_stmt_necessary (stmt, true);
|
mark_stmt_necessary (stmt, true);
|
return;
|
return;
|
}
|
}
|
|
|
return;
|
return;
|
}
|
}
|
|
|
|
|
/* Mark the last statement of BB as necessary. */
|
/* Mark the last statement of BB as necessary. */
|
|
|
static void
|
static void
|
mark_last_stmt_necessary (basic_block bb)
|
mark_last_stmt_necessary (basic_block bb)
|
{
|
{
|
gimple stmt = last_stmt (bb);
|
gimple stmt = last_stmt (bb);
|
|
|
SET_BIT (last_stmt_necessary, bb->index);
|
SET_BIT (last_stmt_necessary, bb->index);
|
SET_BIT (bb_contains_live_stmts, bb->index);
|
SET_BIT (bb_contains_live_stmts, bb->index);
|
|
|
/* We actually mark the statement only if it is a control statement. */
|
/* We actually mark the statement only if it is a control statement. */
|
if (stmt && is_ctrl_stmt (stmt))
|
if (stmt && is_ctrl_stmt (stmt))
|
mark_stmt_necessary (stmt, true);
|
mark_stmt_necessary (stmt, true);
|
}
|
}
|
|
|
|
|
/* Mark control dependent edges of BB as necessary. We have to do this only
|
/* Mark control dependent edges of BB as necessary. We have to do this only
|
once for each basic block so we set the appropriate bit after we're done.
|
once for each basic block so we set the appropriate bit after we're done.
|
|
|
When IGNORE_SELF is true, ignore BB in the list of control dependences. */
|
When IGNORE_SELF is true, ignore BB in the list of control dependences. */
|
|
|
static void
|
static void
|
mark_control_dependent_edges_necessary (basic_block bb, struct edge_list *el,
|
mark_control_dependent_edges_necessary (basic_block bb, struct edge_list *el,
|
bool ignore_self)
|
bool ignore_self)
|
{
|
{
|
bitmap_iterator bi;
|
bitmap_iterator bi;
|
unsigned edge_number;
|
unsigned edge_number;
|
bool skipped = false;
|
bool skipped = false;
|
|
|
gcc_assert (bb != EXIT_BLOCK_PTR);
|
gcc_assert (bb != EXIT_BLOCK_PTR);
|
|
|
if (bb == ENTRY_BLOCK_PTR)
|
if (bb == ENTRY_BLOCK_PTR)
|
return;
|
return;
|
|
|
EXECUTE_IF_CONTROL_DEPENDENT (bi, bb->index, edge_number)
|
EXECUTE_IF_CONTROL_DEPENDENT (bi, bb->index, edge_number)
|
{
|
{
|
basic_block cd_bb = INDEX_EDGE_PRED_BB (el, edge_number);
|
basic_block cd_bb = INDEX_EDGE_PRED_BB (el, edge_number);
|
|
|
if (ignore_self && cd_bb == bb)
|
if (ignore_self && cd_bb == bb)
|
{
|
{
|
skipped = true;
|
skipped = true;
|
continue;
|
continue;
|
}
|
}
|
|
|
if (!TEST_BIT (last_stmt_necessary, cd_bb->index))
|
if (!TEST_BIT (last_stmt_necessary, cd_bb->index))
|
mark_last_stmt_necessary (cd_bb);
|
mark_last_stmt_necessary (cd_bb);
|
}
|
}
|
|
|
if (!skipped)
|
if (!skipped)
|
SET_BIT (visited_control_parents, bb->index);
|
SET_BIT (visited_control_parents, bb->index);
|
}
|
}
|
|
|
|
|
/* Find obviously necessary statements. These are things like most function
|
/* Find obviously necessary statements. These are things like most function
|
calls, and stores to file level variables.
|
calls, and stores to file level variables.
|
|
|
If EL is NULL, control statements are conservatively marked as
|
If EL is NULL, control statements are conservatively marked as
|
necessary. Otherwise it contains the list of edges used by control
|
necessary. Otherwise it contains the list of edges used by control
|
dependence analysis. */
|
dependence analysis. */
|
|
|
static void
|
static void
|
find_obviously_necessary_stmts (struct edge_list *el)
|
find_obviously_necessary_stmts (struct edge_list *el)
|
{
|
{
|
basic_block bb;
|
basic_block bb;
|
gimple_stmt_iterator gsi;
|
gimple_stmt_iterator gsi;
|
edge e;
|
edge e;
|
gimple phi, stmt;
|
gimple phi, stmt;
|
int flags;
|
int flags;
|
|
|
FOR_EACH_BB (bb)
|
FOR_EACH_BB (bb)
|
{
|
{
|
/* PHI nodes are never inherently necessary. */
|
/* PHI nodes are never inherently necessary. */
|
for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
|
for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
|
{
|
{
|
phi = gsi_stmt (gsi);
|
phi = gsi_stmt (gsi);
|
gimple_set_plf (phi, STMT_NECESSARY, false);
|
gimple_set_plf (phi, STMT_NECESSARY, false);
|
}
|
}
|
|
|
/* Check all statements in the block. */
|
/* Check all statements in the block. */
|
for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
|
for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
|
{
|
{
|
stmt = gsi_stmt (gsi);
|
stmt = gsi_stmt (gsi);
|
gimple_set_plf (stmt, STMT_NECESSARY, false);
|
gimple_set_plf (stmt, STMT_NECESSARY, false);
|
mark_stmt_if_obviously_necessary (stmt, el != NULL);
|
mark_stmt_if_obviously_necessary (stmt, el != NULL);
|
}
|
}
|
}
|
}
|
|
|
/* Pure and const functions are finite and thus have no infinite loops in
|
/* Pure and const functions are finite and thus have no infinite loops in
|
them. */
|
them. */
|
flags = flags_from_decl_or_type (current_function_decl);
|
flags = flags_from_decl_or_type (current_function_decl);
|
if ((flags & (ECF_CONST|ECF_PURE)) && !(flags & ECF_LOOPING_CONST_OR_PURE))
|
if ((flags & (ECF_CONST|ECF_PURE)) && !(flags & ECF_LOOPING_CONST_OR_PURE))
|
return;
|
return;
|
|
|
/* Prevent the empty possibly infinite loops from being removed. */
|
/* Prevent the empty possibly infinite loops from being removed. */
|
if (el)
|
if (el)
|
{
|
{
|
loop_iterator li;
|
loop_iterator li;
|
struct loop *loop;
|
struct loop *loop;
|
scev_initialize ();
|
scev_initialize ();
|
if (mark_irreducible_loops ())
|
if (mark_irreducible_loops ())
|
FOR_EACH_BB (bb)
|
FOR_EACH_BB (bb)
|
{
|
{
|
edge_iterator ei;
|
edge_iterator ei;
|
FOR_EACH_EDGE (e, ei, bb->succs)
|
FOR_EACH_EDGE (e, ei, bb->succs)
|
if ((e->flags & EDGE_DFS_BACK)
|
if ((e->flags & EDGE_DFS_BACK)
|
&& (e->flags & EDGE_IRREDUCIBLE_LOOP))
|
&& (e->flags & EDGE_IRREDUCIBLE_LOOP))
|
{
|
{
|
if (dump_file)
|
if (dump_file)
|
fprintf (dump_file, "Marking back edge of irreducible loop %i->%i\n",
|
fprintf (dump_file, "Marking back edge of irreducible loop %i->%i\n",
|
e->src->index, e->dest->index);
|
e->src->index, e->dest->index);
|
mark_control_dependent_edges_necessary (e->dest, el, false);
|
mark_control_dependent_edges_necessary (e->dest, el, false);
|
}
|
}
|
}
|
}
|
|
|
FOR_EACH_LOOP (li, loop, 0)
|
FOR_EACH_LOOP (li, loop, 0)
|
if (!finite_loop_p (loop))
|
if (!finite_loop_p (loop))
|
{
|
{
|
if (dump_file)
|
if (dump_file)
|
fprintf (dump_file, "can not prove finiteness of loop %i\n", loop->num);
|
fprintf (dump_file, "can not prove finiteness of loop %i\n", loop->num);
|
mark_control_dependent_edges_necessary (loop->latch, el, false);
|
mark_control_dependent_edges_necessary (loop->latch, el, false);
|
}
|
}
|
scev_finalize ();
|
scev_finalize ();
|
}
|
}
|
}
|
}
|
|
|
|
|
/* Return true if REF is based on an aliased base, otherwise false. */
|
/* Return true if REF is based on an aliased base, otherwise false. */
|
|
|
static bool
|
static bool
|
ref_may_be_aliased (tree ref)
|
ref_may_be_aliased (tree ref)
|
{
|
{
|
gcc_assert (TREE_CODE (ref) != WITH_SIZE_EXPR);
|
gcc_assert (TREE_CODE (ref) != WITH_SIZE_EXPR);
|
while (handled_component_p (ref))
|
while (handled_component_p (ref))
|
ref = TREE_OPERAND (ref, 0);
|
ref = TREE_OPERAND (ref, 0);
|
if (TREE_CODE (ref) == MEM_REF
|
if (TREE_CODE (ref) == MEM_REF
|
&& TREE_CODE (TREE_OPERAND (ref, 0)) == ADDR_EXPR)
|
&& TREE_CODE (TREE_OPERAND (ref, 0)) == ADDR_EXPR)
|
ref = TREE_OPERAND (TREE_OPERAND (ref, 0), 0);
|
ref = TREE_OPERAND (TREE_OPERAND (ref, 0), 0);
|
return !(DECL_P (ref)
|
return !(DECL_P (ref)
|
&& !may_be_aliased (ref));
|
&& !may_be_aliased (ref));
|
}
|
}
|
|
|
static bitmap visited = NULL;
|
static bitmap visited = NULL;
|
static unsigned int longest_chain = 0;
|
static unsigned int longest_chain = 0;
|
static unsigned int total_chain = 0;
|
static unsigned int total_chain = 0;
|
static unsigned int nr_walks = 0;
|
static unsigned int nr_walks = 0;
|
static bool chain_ovfl = false;
|
static bool chain_ovfl = false;
|
|
|
/* Worker for the walker that marks reaching definitions of REF,
|
/* Worker for the walker that marks reaching definitions of REF,
|
which is based on a non-aliased decl, necessary. It returns
|
which is based on a non-aliased decl, necessary. It returns
|
true whenever the defining statement of the current VDEF is
|
true whenever the defining statement of the current VDEF is
|
a kill for REF, as no dominating may-defs are necessary for REF
|
a kill for REF, as no dominating may-defs are necessary for REF
|
anymore. DATA points to the basic-block that contains the
|
anymore. DATA points to the basic-block that contains the
|
stmt that refers to REF. */
|
stmt that refers to REF. */
|
|
|
static bool
|
static bool
|
mark_aliased_reaching_defs_necessary_1 (ao_ref *ref, tree vdef, void *data)
|
mark_aliased_reaching_defs_necessary_1 (ao_ref *ref, tree vdef, void *data)
|
{
|
{
|
gimple def_stmt = SSA_NAME_DEF_STMT (vdef);
|
gimple def_stmt = SSA_NAME_DEF_STMT (vdef);
|
|
|
/* All stmts we visit are necessary. */
|
/* All stmts we visit are necessary. */
|
mark_operand_necessary (vdef);
|
mark_operand_necessary (vdef);
|
|
|
/* If the stmt lhs kills ref, then we can stop walking. */
|
/* If the stmt lhs kills ref, then we can stop walking. */
|
if (gimple_has_lhs (def_stmt)
|
if (gimple_has_lhs (def_stmt)
|
&& TREE_CODE (gimple_get_lhs (def_stmt)) != SSA_NAME
|
&& TREE_CODE (gimple_get_lhs (def_stmt)) != SSA_NAME
|
/* The assignment is not necessarily carried out if it can throw
|
/* The assignment is not necessarily carried out if it can throw
|
and we can catch it in the current function where we could inspect
|
and we can catch it in the current function where we could inspect
|
the previous value.
|
the previous value.
|
??? We only need to care about the RHS throwing. For aggregate
|
??? We only need to care about the RHS throwing. For aggregate
|
assignments or similar calls and non-call exceptions the LHS
|
assignments or similar calls and non-call exceptions the LHS
|
might throw as well. */
|
might throw as well. */
|
&& !stmt_can_throw_internal (def_stmt))
|
&& !stmt_can_throw_internal (def_stmt))
|
{
|
{
|
tree base, lhs = gimple_get_lhs (def_stmt);
|
tree base, lhs = gimple_get_lhs (def_stmt);
|
HOST_WIDE_INT size, offset, max_size;
|
HOST_WIDE_INT size, offset, max_size;
|
ao_ref_base (ref);
|
ao_ref_base (ref);
|
base = get_ref_base_and_extent (lhs, &offset, &size, &max_size);
|
base = get_ref_base_and_extent (lhs, &offset, &size, &max_size);
|
/* We can get MEM[symbol: sZ, index: D.8862_1] here,
|
/* We can get MEM[symbol: sZ, index: D.8862_1] here,
|
so base == refd->base does not always hold. */
|
so base == refd->base does not always hold. */
|
if (base == ref->base)
|
if (base == ref->base)
|
{
|
{
|
/* For a must-alias check we need to be able to constrain
|
/* For a must-alias check we need to be able to constrain
|
the accesses properly. */
|
the accesses properly. */
|
if (size != -1 && size == max_size
|
if (size != -1 && size == max_size
|
&& ref->max_size != -1)
|
&& ref->max_size != -1)
|
{
|
{
|
if (offset <= ref->offset
|
if (offset <= ref->offset
|
&& offset + size >= ref->offset + ref->max_size)
|
&& offset + size >= ref->offset + ref->max_size)
|
return true;
|
return true;
|
}
|
}
|
/* Or they need to be exactly the same. */
|
/* Or they need to be exactly the same. */
|
else if (ref->ref
|
else if (ref->ref
|
/* Make sure there is no induction variable involved
|
/* Make sure there is no induction variable involved
|
in the references (gcc.c-torture/execute/pr42142.c).
|
in the references (gcc.c-torture/execute/pr42142.c).
|
The simplest way is to check if the kill dominates
|
The simplest way is to check if the kill dominates
|
the use. */
|
the use. */
|
&& dominated_by_p (CDI_DOMINATORS, (basic_block) data,
|
&& dominated_by_p (CDI_DOMINATORS, (basic_block) data,
|
gimple_bb (def_stmt))
|
gimple_bb (def_stmt))
|
&& operand_equal_p (ref->ref, lhs, 0))
|
&& operand_equal_p (ref->ref, lhs, 0))
|
return true;
|
return true;
|
}
|
}
|
}
|
}
|
|
|
/* Otherwise keep walking. */
|
/* Otherwise keep walking. */
|
return false;
|
return false;
|
}
|
}
|
|
|
static void
|
static void
|
mark_aliased_reaching_defs_necessary (gimple stmt, tree ref)
|
mark_aliased_reaching_defs_necessary (gimple stmt, tree ref)
|
{
|
{
|
unsigned int chain;
|
unsigned int chain;
|
ao_ref refd;
|
ao_ref refd;
|
gcc_assert (!chain_ovfl);
|
gcc_assert (!chain_ovfl);
|
ao_ref_init (&refd, ref);
|
ao_ref_init (&refd, ref);
|
chain = walk_aliased_vdefs (&refd, gimple_vuse (stmt),
|
chain = walk_aliased_vdefs (&refd, gimple_vuse (stmt),
|
mark_aliased_reaching_defs_necessary_1,
|
mark_aliased_reaching_defs_necessary_1,
|
gimple_bb (stmt), NULL);
|
gimple_bb (stmt), NULL);
|
if (chain > longest_chain)
|
if (chain > longest_chain)
|
longest_chain = chain;
|
longest_chain = chain;
|
total_chain += chain;
|
total_chain += chain;
|
nr_walks++;
|
nr_walks++;
|
}
|
}
|
|
|
/* Worker for the walker that marks reaching definitions of REF, which
|
/* Worker for the walker that marks reaching definitions of REF, which
|
is not based on a non-aliased decl. For simplicity we need to end
|
is not based on a non-aliased decl. For simplicity we need to end
|
up marking all may-defs necessary that are not based on a non-aliased
|
up marking all may-defs necessary that are not based on a non-aliased
|
decl. The only job of this walker is to skip may-defs based on
|
decl. The only job of this walker is to skip may-defs based on
|
a non-aliased decl. */
|
a non-aliased decl. */
|
|
|
static bool
|
static bool
|
mark_all_reaching_defs_necessary_1 (ao_ref *ref ATTRIBUTE_UNUSED,
|
mark_all_reaching_defs_necessary_1 (ao_ref *ref ATTRIBUTE_UNUSED,
|
tree vdef, void *data ATTRIBUTE_UNUSED)
|
tree vdef, void *data ATTRIBUTE_UNUSED)
|
{
|
{
|
gimple def_stmt = SSA_NAME_DEF_STMT (vdef);
|
gimple def_stmt = SSA_NAME_DEF_STMT (vdef);
|
|
|
/* We have to skip already visited (and thus necessary) statements
|
/* We have to skip already visited (and thus necessary) statements
|
to make the chaining work after we dropped back to simple mode. */
|
to make the chaining work after we dropped back to simple mode. */
|
if (chain_ovfl
|
if (chain_ovfl
|
&& TEST_BIT (processed, SSA_NAME_VERSION (vdef)))
|
&& TEST_BIT (processed, SSA_NAME_VERSION (vdef)))
|
{
|
{
|
gcc_assert (gimple_nop_p (def_stmt)
|
gcc_assert (gimple_nop_p (def_stmt)
|
|| gimple_plf (def_stmt, STMT_NECESSARY));
|
|| gimple_plf (def_stmt, STMT_NECESSARY));
|
return false;
|
return false;
|
}
|
}
|
|
|
/* We want to skip stores to non-aliased variables. */
|
/* We want to skip stores to non-aliased variables. */
|
if (!chain_ovfl
|
if (!chain_ovfl
|
&& gimple_assign_single_p (def_stmt))
|
&& gimple_assign_single_p (def_stmt))
|
{
|
{
|
tree lhs = gimple_assign_lhs (def_stmt);
|
tree lhs = gimple_assign_lhs (def_stmt);
|
if (!ref_may_be_aliased (lhs))
|
if (!ref_may_be_aliased (lhs))
|
return false;
|
return false;
|
}
|
}
|
|
|
/* We want to skip statments that do not constitute stores but have
|
/* We want to skip statments that do not constitute stores but have
|
a virtual definition. */
|
a virtual definition. */
|
if (is_gimple_call (def_stmt))
|
if (is_gimple_call (def_stmt))
|
{
|
{
|
tree callee = gimple_call_fndecl (def_stmt);
|
tree callee = gimple_call_fndecl (def_stmt);
|
if (callee != NULL_TREE
|
if (callee != NULL_TREE
|
&& DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL)
|
&& DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL)
|
switch (DECL_FUNCTION_CODE (callee))
|
switch (DECL_FUNCTION_CODE (callee))
|
{
|
{
|
case BUILT_IN_MALLOC:
|
case BUILT_IN_MALLOC:
|
case BUILT_IN_CALLOC:
|
case BUILT_IN_CALLOC:
|
case BUILT_IN_ALLOCA:
|
case BUILT_IN_ALLOCA:
|
case BUILT_IN_ALLOCA_WITH_ALIGN:
|
case BUILT_IN_ALLOCA_WITH_ALIGN:
|
case BUILT_IN_FREE:
|
case BUILT_IN_FREE:
|
return false;
|
return false;
|
|
|
default:;
|
default:;
|
}
|
}
|
}
|
}
|
|
|
mark_operand_necessary (vdef);
|
mark_operand_necessary (vdef);
|
|
|
return false;
|
return false;
|
}
|
}
|
|
|
static void
|
static void
|
mark_all_reaching_defs_necessary (gimple stmt)
|
mark_all_reaching_defs_necessary (gimple stmt)
|
{
|
{
|
walk_aliased_vdefs (NULL, gimple_vuse (stmt),
|
walk_aliased_vdefs (NULL, gimple_vuse (stmt),
|
mark_all_reaching_defs_necessary_1, NULL, &visited);
|
mark_all_reaching_defs_necessary_1, NULL, &visited);
|
}
|
}
|
|
|
/* Return true for PHI nodes with one or identical arguments
|
/* Return true for PHI nodes with one or identical arguments
|
can be removed. */
|
can be removed. */
|
static bool
|
static bool
|
degenerate_phi_p (gimple phi)
|
degenerate_phi_p (gimple phi)
|
{
|
{
|
unsigned int i;
|
unsigned int i;
|
tree op = gimple_phi_arg_def (phi, 0);
|
tree op = gimple_phi_arg_def (phi, 0);
|
for (i = 1; i < gimple_phi_num_args (phi); i++)
|
for (i = 1; i < gimple_phi_num_args (phi); i++)
|
if (gimple_phi_arg_def (phi, i) != op)
|
if (gimple_phi_arg_def (phi, i) != op)
|
return false;
|
return false;
|
return true;
|
return true;
|
}
|
}
|
|
|
/* Propagate necessity using the operands of necessary statements.
|
/* Propagate necessity using the operands of necessary statements.
|
Process the uses on each statement in the worklist, and add all
|
Process the uses on each statement in the worklist, and add all
|
feeding statements which contribute to the calculation of this
|
feeding statements which contribute to the calculation of this
|
value to the worklist.
|
value to the worklist.
|
|
|
In conservative mode, EL is NULL. */
|
In conservative mode, EL is NULL. */
|
|
|
static void
|
static void
|
propagate_necessity (struct edge_list *el)
|
propagate_necessity (struct edge_list *el)
|
{
|
{
|
gimple stmt;
|
gimple stmt;
|
bool aggressive = (el ? true : false);
|
bool aggressive = (el ? true : false);
|
|
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
fprintf (dump_file, "\nProcessing worklist:\n");
|
fprintf (dump_file, "\nProcessing worklist:\n");
|
|
|
while (VEC_length (gimple, worklist) > 0)
|
while (VEC_length (gimple, worklist) > 0)
|
{
|
{
|
/* Take STMT from worklist. */
|
/* Take STMT from worklist. */
|
stmt = VEC_pop (gimple, worklist);
|
stmt = VEC_pop (gimple, worklist);
|
|
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
{
|
{
|
fprintf (dump_file, "processing: ");
|
fprintf (dump_file, "processing: ");
|
print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
|
print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
|
fprintf (dump_file, "\n");
|
fprintf (dump_file, "\n");
|
}
|
}
|
|
|
if (aggressive)
|
if (aggressive)
|
{
|
{
|
/* Mark the last statement of the basic blocks on which the block
|
/* Mark the last statement of the basic blocks on which the block
|
containing STMT is control dependent, but only if we haven't
|
containing STMT is control dependent, but only if we haven't
|
already done so. */
|
already done so. */
|
basic_block bb = gimple_bb (stmt);
|
basic_block bb = gimple_bb (stmt);
|
if (bb != ENTRY_BLOCK_PTR
|
if (bb != ENTRY_BLOCK_PTR
|
&& !TEST_BIT (visited_control_parents, bb->index))
|
&& !TEST_BIT (visited_control_parents, bb->index))
|
mark_control_dependent_edges_necessary (bb, el, false);
|
mark_control_dependent_edges_necessary (bb, el, false);
|
}
|
}
|
|
|
if (gimple_code (stmt) == GIMPLE_PHI
|
if (gimple_code (stmt) == GIMPLE_PHI
|
/* We do not process virtual PHI nodes nor do we track their
|
/* We do not process virtual PHI nodes nor do we track their
|
necessity. */
|
necessity. */
|
&& is_gimple_reg (gimple_phi_result (stmt)))
|
&& is_gimple_reg (gimple_phi_result (stmt)))
|
{
|
{
|
/* PHI nodes are somewhat special in that each PHI alternative has
|
/* PHI nodes are somewhat special in that each PHI alternative has
|
data and control dependencies. All the statements feeding the
|
data and control dependencies. All the statements feeding the
|
PHI node's arguments are always necessary. In aggressive mode,
|
PHI node's arguments are always necessary. In aggressive mode,
|
we also consider the control dependent edges leading to the
|
we also consider the control dependent edges leading to the
|
predecessor block associated with each PHI alternative as
|
predecessor block associated with each PHI alternative as
|
necessary. */
|
necessary. */
|
size_t k;
|
size_t k;
|
|
|
for (k = 0; k < gimple_phi_num_args (stmt); k++)
|
for (k = 0; k < gimple_phi_num_args (stmt); k++)
|
{
|
{
|
tree arg = PHI_ARG_DEF (stmt, k);
|
tree arg = PHI_ARG_DEF (stmt, k);
|
if (TREE_CODE (arg) == SSA_NAME)
|
if (TREE_CODE (arg) == SSA_NAME)
|
mark_operand_necessary (arg);
|
mark_operand_necessary (arg);
|
}
|
}
|
|
|
/* For PHI operands it matters from where the control flow arrives
|
/* For PHI operands it matters from where the control flow arrives
|
to the BB. Consider the following example:
|
to the BB. Consider the following example:
|
|
|
a=exp1;
|
a=exp1;
|
b=exp2;
|
b=exp2;
|
if (test)
|
if (test)
|
;
|
;
|
else
|
else
|
;
|
;
|
c=PHI(a,b)
|
c=PHI(a,b)
|
|
|
We need to mark control dependence of the empty basic blocks, since they
|
We need to mark control dependence of the empty basic blocks, since they
|
contains computation of PHI operands.
|
contains computation of PHI operands.
|
|
|
Doing so is too restrictive in the case the predecestor block is in
|
Doing so is too restrictive in the case the predecestor block is in
|
the loop. Consider:
|
the loop. Consider:
|
|
|
if (b)
|
if (b)
|
{
|
{
|
int i;
|
int i;
|
for (i = 0; i<1000; ++i)
|
for (i = 0; i<1000; ++i)
|
;
|
;
|
j = 0;
|
j = 0;
|
}
|
}
|
return j;
|
return j;
|
|
|
There is PHI for J in the BB containing return statement.
|
There is PHI for J in the BB containing return statement.
|
In this case the control dependence of predecestor block (that is
|
In this case the control dependence of predecestor block (that is
|
within the empty loop) also contains the block determining number
|
within the empty loop) also contains the block determining number
|
of iterations of the block that would prevent removing of empty
|
of iterations of the block that would prevent removing of empty
|
loop in this case.
|
loop in this case.
|
|
|
This scenario can be avoided by splitting critical edges.
|
This scenario can be avoided by splitting critical edges.
|
To save the critical edge splitting pass we identify how the control
|
To save the critical edge splitting pass we identify how the control
|
dependence would look like if the edge was split.
|
dependence would look like if the edge was split.
|
|
|
Consider the modified CFG created from current CFG by splitting
|
Consider the modified CFG created from current CFG by splitting
|
edge B->C. In the postdominance tree of modified CFG, C' is
|
edge B->C. In the postdominance tree of modified CFG, C' is
|
always child of C. There are two cases how chlids of C' can look
|
always child of C. There are two cases how chlids of C' can look
|
like:
|
like:
|
|
|
1) C' is leaf
|
1) C' is leaf
|
|
|
In this case the only basic block C' is control dependent on is B.
|
In this case the only basic block C' is control dependent on is B.
|
|
|
2) C' has single child that is B
|
2) C' has single child that is B
|
|
|
In this case control dependence of C' is same as control
|
In this case control dependence of C' is same as control
|
dependence of B in original CFG except for block B itself.
|
dependence of B in original CFG except for block B itself.
|
(since C' postdominate B in modified CFG)
|
(since C' postdominate B in modified CFG)
|
|
|
Now how to decide what case happens? There are two basic options:
|
Now how to decide what case happens? There are two basic options:
|
|
|
a) C postdominate B. Then C immediately postdominate B and
|
a) C postdominate B. Then C immediately postdominate B and
|
case 2 happens iff there is no other way from B to C except
|
case 2 happens iff there is no other way from B to C except
|
the edge B->C.
|
the edge B->C.
|
|
|
There is other way from B to C iff there is succesor of B that
|
There is other way from B to C iff there is succesor of B that
|
is not postdominated by B. Testing this condition is somewhat
|
is not postdominated by B. Testing this condition is somewhat
|
expensive, because we need to iterate all succesors of B.
|
expensive, because we need to iterate all succesors of B.
|
We are safe to assume that this does not happen: we will mark B
|
We are safe to assume that this does not happen: we will mark B
|
as needed when processing the other path from B to C that is
|
as needed when processing the other path from B to C that is
|
conrol dependent on B and marking control dependencies of B
|
conrol dependent on B and marking control dependencies of B
|
itself is harmless because they will be processed anyway after
|
itself is harmless because they will be processed anyway after
|
processing control statement in B.
|
processing control statement in B.
|
|
|
b) C does not postdominate B. Always case 1 happens since there is
|
b) C does not postdominate B. Always case 1 happens since there is
|
path from C to exit that does not go through B and thus also C'. */
|
path from C to exit that does not go through B and thus also C'. */
|
|
|
if (aggressive && !degenerate_phi_p (stmt))
|
if (aggressive && !degenerate_phi_p (stmt))
|
{
|
{
|
for (k = 0; k < gimple_phi_num_args (stmt); k++)
|
for (k = 0; k < gimple_phi_num_args (stmt); k++)
|
{
|
{
|
basic_block arg_bb = gimple_phi_arg_edge (stmt, k)->src;
|
basic_block arg_bb = gimple_phi_arg_edge (stmt, k)->src;
|
|
|
if (gimple_bb (stmt)
|
if (gimple_bb (stmt)
|
!= get_immediate_dominator (CDI_POST_DOMINATORS, arg_bb))
|
!= get_immediate_dominator (CDI_POST_DOMINATORS, arg_bb))
|
{
|
{
|
if (!TEST_BIT (last_stmt_necessary, arg_bb->index))
|
if (!TEST_BIT (last_stmt_necessary, arg_bb->index))
|
mark_last_stmt_necessary (arg_bb);
|
mark_last_stmt_necessary (arg_bb);
|
}
|
}
|
else if (arg_bb != ENTRY_BLOCK_PTR
|
else if (arg_bb != ENTRY_BLOCK_PTR
|
&& !TEST_BIT (visited_control_parents,
|
&& !TEST_BIT (visited_control_parents,
|
arg_bb->index))
|
arg_bb->index))
|
mark_control_dependent_edges_necessary (arg_bb, el, true);
|
mark_control_dependent_edges_necessary (arg_bb, el, true);
|
}
|
}
|
}
|
}
|
}
|
}
|
else
|
else
|
{
|
{
|
/* Propagate through the operands. Examine all the USE, VUSE and
|
/* Propagate through the operands. Examine all the USE, VUSE and
|
VDEF operands in this statement. Mark all the statements
|
VDEF operands in this statement. Mark all the statements
|
which feed this statement's uses as necessary. */
|
which feed this statement's uses as necessary. */
|
ssa_op_iter iter;
|
ssa_op_iter iter;
|
tree use;
|
tree use;
|
|
|
/* If this is a call to free which is directly fed by an
|
/* If this is a call to free which is directly fed by an
|
allocation function do not mark that necessary through
|
allocation function do not mark that necessary through
|
processing the argument. */
|
processing the argument. */
|
if (gimple_call_builtin_p (stmt, BUILT_IN_FREE))
|
if (gimple_call_builtin_p (stmt, BUILT_IN_FREE))
|
{
|
{
|
tree ptr = gimple_call_arg (stmt, 0);
|
tree ptr = gimple_call_arg (stmt, 0);
|
gimple def_stmt;
|
gimple def_stmt;
|
tree def_callee;
|
tree def_callee;
|
/* If the pointer we free is defined by an allocation
|
/* If the pointer we free is defined by an allocation
|
function do not add the call to the worklist. */
|
function do not add the call to the worklist. */
|
if (TREE_CODE (ptr) == SSA_NAME
|
if (TREE_CODE (ptr) == SSA_NAME
|
&& is_gimple_call (def_stmt = SSA_NAME_DEF_STMT (ptr))
|
&& is_gimple_call (def_stmt = SSA_NAME_DEF_STMT (ptr))
|
&& (def_callee = gimple_call_fndecl (def_stmt))
|
&& (def_callee = gimple_call_fndecl (def_stmt))
|
&& DECL_BUILT_IN_CLASS (def_callee) == BUILT_IN_NORMAL
|
&& DECL_BUILT_IN_CLASS (def_callee) == BUILT_IN_NORMAL
|
&& (DECL_FUNCTION_CODE (def_callee) == BUILT_IN_MALLOC
|
&& (DECL_FUNCTION_CODE (def_callee) == BUILT_IN_MALLOC
|
|| DECL_FUNCTION_CODE (def_callee) == BUILT_IN_CALLOC))
|
|| DECL_FUNCTION_CODE (def_callee) == BUILT_IN_CALLOC))
|
continue;
|
continue;
|
}
|
}
|
|
|
FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
|
FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
|
mark_operand_necessary (use);
|
mark_operand_necessary (use);
|
|
|
use = gimple_vuse (stmt);
|
use = gimple_vuse (stmt);
|
if (!use)
|
if (!use)
|
continue;
|
continue;
|
|
|
/* If we dropped to simple mode make all immediately
|
/* If we dropped to simple mode make all immediately
|
reachable definitions necessary. */
|
reachable definitions necessary. */
|
if (chain_ovfl)
|
if (chain_ovfl)
|
{
|
{
|
mark_all_reaching_defs_necessary (stmt);
|
mark_all_reaching_defs_necessary (stmt);
|
continue;
|
continue;
|
}
|
}
|
|
|
/* For statements that may load from memory (have a VUSE) we
|
/* For statements that may load from memory (have a VUSE) we
|
have to mark all reaching (may-)definitions as necessary.
|
have to mark all reaching (may-)definitions as necessary.
|
We partition this task into two cases:
|
We partition this task into two cases:
|
1) explicit loads based on decls that are not aliased
|
1) explicit loads based on decls that are not aliased
|
2) implicit loads (like calls) and explicit loads not
|
2) implicit loads (like calls) and explicit loads not
|
based on decls that are not aliased (like indirect
|
based on decls that are not aliased (like indirect
|
references or loads from globals)
|
references or loads from globals)
|
For 1) we mark all reaching may-defs as necessary, stopping
|
For 1) we mark all reaching may-defs as necessary, stopping
|
at dominating kills. For 2) we want to mark all dominating
|
at dominating kills. For 2) we want to mark all dominating
|
references necessary, but non-aliased ones which we handle
|
references necessary, but non-aliased ones which we handle
|
in 1). By keeping a global visited bitmap for references
|
in 1). By keeping a global visited bitmap for references
|
we walk for 2) we avoid quadratic behavior for those. */
|
we walk for 2) we avoid quadratic behavior for those. */
|
|
|
if (is_gimple_call (stmt))
|
if (is_gimple_call (stmt))
|
{
|
{
|
tree callee = gimple_call_fndecl (stmt);
|
tree callee = gimple_call_fndecl (stmt);
|
unsigned i;
|
unsigned i;
|
|
|
/* Calls to functions that are merely acting as barriers
|
/* Calls to functions that are merely acting as barriers
|
or that only store to memory do not make any previous
|
or that only store to memory do not make any previous
|
stores necessary. */
|
stores necessary. */
|
if (callee != NULL_TREE
|
if (callee != NULL_TREE
|
&& DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL
|
&& DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL
|
&& (DECL_FUNCTION_CODE (callee) == BUILT_IN_MEMSET
|
&& (DECL_FUNCTION_CODE (callee) == BUILT_IN_MEMSET
|
|| DECL_FUNCTION_CODE (callee) == BUILT_IN_MEMSET_CHK
|
|| DECL_FUNCTION_CODE (callee) == BUILT_IN_MEMSET_CHK
|
|| DECL_FUNCTION_CODE (callee) == BUILT_IN_MALLOC
|
|| DECL_FUNCTION_CODE (callee) == BUILT_IN_MALLOC
|
|| DECL_FUNCTION_CODE (callee) == BUILT_IN_CALLOC
|
|| DECL_FUNCTION_CODE (callee) == BUILT_IN_CALLOC
|
|| DECL_FUNCTION_CODE (callee) == BUILT_IN_FREE
|
|| DECL_FUNCTION_CODE (callee) == BUILT_IN_FREE
|
|| DECL_FUNCTION_CODE (callee) == BUILT_IN_VA_END
|
|| DECL_FUNCTION_CODE (callee) == BUILT_IN_VA_END
|
|| DECL_FUNCTION_CODE (callee) == BUILT_IN_ALLOCA
|
|| DECL_FUNCTION_CODE (callee) == BUILT_IN_ALLOCA
|
|| (DECL_FUNCTION_CODE (callee)
|
|| (DECL_FUNCTION_CODE (callee)
|
== BUILT_IN_ALLOCA_WITH_ALIGN)
|
== BUILT_IN_ALLOCA_WITH_ALIGN)
|
|| DECL_FUNCTION_CODE (callee) == BUILT_IN_STACK_SAVE
|
|| DECL_FUNCTION_CODE (callee) == BUILT_IN_STACK_SAVE
|
|| DECL_FUNCTION_CODE (callee) == BUILT_IN_STACK_RESTORE
|
|| DECL_FUNCTION_CODE (callee) == BUILT_IN_STACK_RESTORE
|
|| DECL_FUNCTION_CODE (callee) == BUILT_IN_ASSUME_ALIGNED))
|
|| DECL_FUNCTION_CODE (callee) == BUILT_IN_ASSUME_ALIGNED))
|
continue;
|
continue;
|
|
|
/* Calls implicitly load from memory, their arguments
|
/* Calls implicitly load from memory, their arguments
|
in addition may explicitly perform memory loads. */
|
in addition may explicitly perform memory loads. */
|
mark_all_reaching_defs_necessary (stmt);
|
mark_all_reaching_defs_necessary (stmt);
|
for (i = 0; i < gimple_call_num_args (stmt); ++i)
|
for (i = 0; i < gimple_call_num_args (stmt); ++i)
|
{
|
{
|
tree arg = gimple_call_arg (stmt, i);
|
tree arg = gimple_call_arg (stmt, i);
|
if (TREE_CODE (arg) == SSA_NAME
|
if (TREE_CODE (arg) == SSA_NAME
|
|| is_gimple_min_invariant (arg))
|
|| is_gimple_min_invariant (arg))
|
continue;
|
continue;
|
if (TREE_CODE (arg) == WITH_SIZE_EXPR)
|
if (TREE_CODE (arg) == WITH_SIZE_EXPR)
|
arg = TREE_OPERAND (arg, 0);
|
arg = TREE_OPERAND (arg, 0);
|
if (!ref_may_be_aliased (arg))
|
if (!ref_may_be_aliased (arg))
|
mark_aliased_reaching_defs_necessary (stmt, arg);
|
mark_aliased_reaching_defs_necessary (stmt, arg);
|
}
|
}
|
}
|
}
|
else if (gimple_assign_single_p (stmt))
|
else if (gimple_assign_single_p (stmt))
|
{
|
{
|
tree rhs;
|
tree rhs;
|
/* If this is a load mark things necessary. */
|
/* If this is a load mark things necessary. */
|
rhs = gimple_assign_rhs1 (stmt);
|
rhs = gimple_assign_rhs1 (stmt);
|
if (TREE_CODE (rhs) != SSA_NAME
|
if (TREE_CODE (rhs) != SSA_NAME
|
&& !is_gimple_min_invariant (rhs)
|
&& !is_gimple_min_invariant (rhs)
|
&& TREE_CODE (rhs) != CONSTRUCTOR)
|
&& TREE_CODE (rhs) != CONSTRUCTOR)
|
{
|
{
|
if (!ref_may_be_aliased (rhs))
|
if (!ref_may_be_aliased (rhs))
|
mark_aliased_reaching_defs_necessary (stmt, rhs);
|
mark_aliased_reaching_defs_necessary (stmt, rhs);
|
else
|
else
|
mark_all_reaching_defs_necessary (stmt);
|
mark_all_reaching_defs_necessary (stmt);
|
}
|
}
|
}
|
}
|
else if (gimple_code (stmt) == GIMPLE_RETURN)
|
else if (gimple_code (stmt) == GIMPLE_RETURN)
|
{
|
{
|
tree rhs = gimple_return_retval (stmt);
|
tree rhs = gimple_return_retval (stmt);
|
/* A return statement may perform a load. */
|
/* A return statement may perform a load. */
|
if (rhs
|
if (rhs
|
&& TREE_CODE (rhs) != SSA_NAME
|
&& TREE_CODE (rhs) != SSA_NAME
|
&& !is_gimple_min_invariant (rhs)
|
&& !is_gimple_min_invariant (rhs)
|
&& TREE_CODE (rhs) != CONSTRUCTOR)
|
&& TREE_CODE (rhs) != CONSTRUCTOR)
|
{
|
{
|
if (!ref_may_be_aliased (rhs))
|
if (!ref_may_be_aliased (rhs))
|
mark_aliased_reaching_defs_necessary (stmt, rhs);
|
mark_aliased_reaching_defs_necessary (stmt, rhs);
|
else
|
else
|
mark_all_reaching_defs_necessary (stmt);
|
mark_all_reaching_defs_necessary (stmt);
|
}
|
}
|
}
|
}
|
else if (gimple_code (stmt) == GIMPLE_ASM)
|
else if (gimple_code (stmt) == GIMPLE_ASM)
|
{
|
{
|
unsigned i;
|
unsigned i;
|
mark_all_reaching_defs_necessary (stmt);
|
mark_all_reaching_defs_necessary (stmt);
|
/* Inputs may perform loads. */
|
/* Inputs may perform loads. */
|
for (i = 0; i < gimple_asm_ninputs (stmt); ++i)
|
for (i = 0; i < gimple_asm_ninputs (stmt); ++i)
|
{
|
{
|
tree op = TREE_VALUE (gimple_asm_input_op (stmt, i));
|
tree op = TREE_VALUE (gimple_asm_input_op (stmt, i));
|
if (TREE_CODE (op) != SSA_NAME
|
if (TREE_CODE (op) != SSA_NAME
|
&& !is_gimple_min_invariant (op)
|
&& !is_gimple_min_invariant (op)
|
&& TREE_CODE (op) != CONSTRUCTOR
|
&& TREE_CODE (op) != CONSTRUCTOR
|
&& !ref_may_be_aliased (op))
|
&& !ref_may_be_aliased (op))
|
mark_aliased_reaching_defs_necessary (stmt, op);
|
mark_aliased_reaching_defs_necessary (stmt, op);
|
}
|
}
|
}
|
}
|
else if (gimple_code (stmt) == GIMPLE_TRANSACTION)
|
else if (gimple_code (stmt) == GIMPLE_TRANSACTION)
|
{
|
{
|
/* The beginning of a transaction is a memory barrier. */
|
/* The beginning of a transaction is a memory barrier. */
|
/* ??? If we were really cool, we'd only be a barrier
|
/* ??? If we were really cool, we'd only be a barrier
|
for the memories touched within the transaction. */
|
for the memories touched within the transaction. */
|
mark_all_reaching_defs_necessary (stmt);
|
mark_all_reaching_defs_necessary (stmt);
|
}
|
}
|
else
|
else
|
gcc_unreachable ();
|
gcc_unreachable ();
|
|
|
/* If we over-used our alias oracle budget drop to simple
|
/* If we over-used our alias oracle budget drop to simple
|
mode. The cost metric allows quadratic behavior
|
mode. The cost metric allows quadratic behavior
|
(number of uses times number of may-defs queries) up to
|
(number of uses times number of may-defs queries) up to
|
a constant maximal number of queries and after that falls back to
|
a constant maximal number of queries and after that falls back to
|
super-linear complexity. */
|
super-linear complexity. */
|
if (/* Constant but quadratic for small functions. */
|
if (/* Constant but quadratic for small functions. */
|
total_chain > 128 * 128
|
total_chain > 128 * 128
|
/* Linear in the number of may-defs. */
|
/* Linear in the number of may-defs. */
|
&& total_chain > 32 * longest_chain
|
&& total_chain > 32 * longest_chain
|
/* Linear in the number of uses. */
|
/* Linear in the number of uses. */
|
&& total_chain > nr_walks * 32)
|
&& total_chain > nr_walks * 32)
|
{
|
{
|
chain_ovfl = true;
|
chain_ovfl = true;
|
if (visited)
|
if (visited)
|
bitmap_clear (visited);
|
bitmap_clear (visited);
|
}
|
}
|
}
|
}
|
}
|
}
|
}
|
}
|
|
|
/* Replace all uses of NAME by underlying variable and mark it
|
/* Replace all uses of NAME by underlying variable and mark it
|
for renaming. */
|
for renaming. */
|
|
|
void
|
void
|
mark_virtual_operand_for_renaming (tree name)
|
mark_virtual_operand_for_renaming (tree name)
|
{
|
{
|
bool used = false;
|
bool used = false;
|
imm_use_iterator iter;
|
imm_use_iterator iter;
|
use_operand_p use_p;
|
use_operand_p use_p;
|
gimple stmt;
|
gimple stmt;
|
tree name_var;
|
tree name_var;
|
|
|
name_var = SSA_NAME_VAR (name);
|
name_var = SSA_NAME_VAR (name);
|
FOR_EACH_IMM_USE_STMT (stmt, iter, name)
|
FOR_EACH_IMM_USE_STMT (stmt, iter, name)
|
{
|
{
|
FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
|
FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
|
SET_USE (use_p, name_var);
|
SET_USE (use_p, name_var);
|
update_stmt (stmt);
|
update_stmt (stmt);
|
used = true;
|
used = true;
|
}
|
}
|
if (used)
|
if (used)
|
mark_sym_for_renaming (name_var);
|
mark_sym_for_renaming (name_var);
|
}
|
}
|
|
|
/* Replace all uses of result of PHI by underlying variable and mark it
|
/* Replace all uses of result of PHI by underlying variable and mark it
|
for renaming. */
|
for renaming. */
|
|
|
void
|
void
|
mark_virtual_phi_result_for_renaming (gimple phi)
|
mark_virtual_phi_result_for_renaming (gimple phi)
|
{
|
{
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
{
|
{
|
fprintf (dump_file, "Marking result for renaming : ");
|
fprintf (dump_file, "Marking result for renaming : ");
|
print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
|
print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
|
fprintf (dump_file, "\n");
|
fprintf (dump_file, "\n");
|
}
|
}
|
|
|
mark_virtual_operand_for_renaming (gimple_phi_result (phi));
|
mark_virtual_operand_for_renaming (gimple_phi_result (phi));
|
}
|
}
|
|
|
|
|
/* Remove dead PHI nodes from block BB. */
|
/* Remove dead PHI nodes from block BB. */
|
|
|
static bool
|
static bool
|
remove_dead_phis (basic_block bb)
|
remove_dead_phis (basic_block bb)
|
{
|
{
|
bool something_changed = false;
|
bool something_changed = false;
|
gimple_seq phis;
|
gimple_seq phis;
|
gimple phi;
|
gimple phi;
|
gimple_stmt_iterator gsi;
|
gimple_stmt_iterator gsi;
|
phis = phi_nodes (bb);
|
phis = phi_nodes (bb);
|
|
|
for (gsi = gsi_start (phis); !gsi_end_p (gsi);)
|
for (gsi = gsi_start (phis); !gsi_end_p (gsi);)
|
{
|
{
|
stats.total_phis++;
|
stats.total_phis++;
|
phi = gsi_stmt (gsi);
|
phi = gsi_stmt (gsi);
|
|
|
/* We do not track necessity of virtual PHI nodes. Instead do
|
/* We do not track necessity of virtual PHI nodes. Instead do
|
very simple dead PHI removal here. */
|
very simple dead PHI removal here. */
|
if (!is_gimple_reg (gimple_phi_result (phi)))
|
if (!is_gimple_reg (gimple_phi_result (phi)))
|
{
|
{
|
/* Virtual PHI nodes with one or identical arguments
|
/* Virtual PHI nodes with one or identical arguments
|
can be removed. */
|
can be removed. */
|
if (degenerate_phi_p (phi))
|
if (degenerate_phi_p (phi))
|
{
|
{
|
tree vdef = gimple_phi_result (phi);
|
tree vdef = gimple_phi_result (phi);
|
tree vuse = gimple_phi_arg_def (phi, 0);
|
tree vuse = gimple_phi_arg_def (phi, 0);
|
|
|
use_operand_p use_p;
|
use_operand_p use_p;
|
imm_use_iterator iter;
|
imm_use_iterator iter;
|
gimple use_stmt;
|
gimple use_stmt;
|
FOR_EACH_IMM_USE_STMT (use_stmt, iter, vdef)
|
FOR_EACH_IMM_USE_STMT (use_stmt, iter, vdef)
|
FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
|
FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
|
SET_USE (use_p, vuse);
|
SET_USE (use_p, vuse);
|
if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (vdef)
|
if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (vdef)
|
&& TREE_CODE (vuse) == SSA_NAME)
|
&& TREE_CODE (vuse) == SSA_NAME)
|
SSA_NAME_OCCURS_IN_ABNORMAL_PHI (vuse) = 1;
|
SSA_NAME_OCCURS_IN_ABNORMAL_PHI (vuse) = 1;
|
}
|
}
|
else
|
else
|
gimple_set_plf (phi, STMT_NECESSARY, true);
|
gimple_set_plf (phi, STMT_NECESSARY, true);
|
}
|
}
|
|
|
if (!gimple_plf (phi, STMT_NECESSARY))
|
if (!gimple_plf (phi, STMT_NECESSARY))
|
{
|
{
|
something_changed = true;
|
something_changed = true;
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
{
|
{
|
fprintf (dump_file, "Deleting : ");
|
fprintf (dump_file, "Deleting : ");
|
print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
|
print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
|
fprintf (dump_file, "\n");
|
fprintf (dump_file, "\n");
|
}
|
}
|
|
|
remove_phi_node (&gsi, true);
|
remove_phi_node (&gsi, true);
|
stats.removed_phis++;
|
stats.removed_phis++;
|
continue;
|
continue;
|
}
|
}
|
|
|
gsi_next (&gsi);
|
gsi_next (&gsi);
|
}
|
}
|
return something_changed;
|
return something_changed;
|
}
|
}
|
|
|
/* Forward edge E to respective POST_DOM_BB and update PHIs. */
|
/* Forward edge E to respective POST_DOM_BB and update PHIs. */
|
|
|
static edge
|
static edge
|
forward_edge_to_pdom (edge e, basic_block post_dom_bb)
|
forward_edge_to_pdom (edge e, basic_block post_dom_bb)
|
{
|
{
|
gimple_stmt_iterator gsi;
|
gimple_stmt_iterator gsi;
|
edge e2 = NULL;
|
edge e2 = NULL;
|
edge_iterator ei;
|
edge_iterator ei;
|
|
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
fprintf (dump_file, "Redirecting edge %i->%i to %i\n", e->src->index,
|
fprintf (dump_file, "Redirecting edge %i->%i to %i\n", e->src->index,
|
e->dest->index, post_dom_bb->index);
|
e->dest->index, post_dom_bb->index);
|
|
|
e2 = redirect_edge_and_branch (e, post_dom_bb);
|
e2 = redirect_edge_and_branch (e, post_dom_bb);
|
cfg_altered = true;
|
cfg_altered = true;
|
|
|
/* If edge was already around, no updating is neccesary. */
|
/* If edge was already around, no updating is neccesary. */
|
if (e2 != e)
|
if (e2 != e)
|
return e2;
|
return e2;
|
|
|
if (!gimple_seq_empty_p (phi_nodes (post_dom_bb)))
|
if (!gimple_seq_empty_p (phi_nodes (post_dom_bb)))
|
{
|
{
|
/* We are sure that for every live PHI we are seeing control dependent BB.
|
/* We are sure that for every live PHI we are seeing control dependent BB.
|
This means that we can pick any edge to duplicate PHI args from. */
|
This means that we can pick any edge to duplicate PHI args from. */
|
FOR_EACH_EDGE (e2, ei, post_dom_bb->preds)
|
FOR_EACH_EDGE (e2, ei, post_dom_bb->preds)
|
if (e2 != e)
|
if (e2 != e)
|
break;
|
break;
|
for (gsi = gsi_start_phis (post_dom_bb); !gsi_end_p (gsi);)
|
for (gsi = gsi_start_phis (post_dom_bb); !gsi_end_p (gsi);)
|
{
|
{
|
gimple phi = gsi_stmt (gsi);
|
gimple phi = gsi_stmt (gsi);
|
tree op;
|
tree op;
|
source_location locus;
|
source_location locus;
|
|
|
/* PHIs for virtuals have no control dependency relation on them.
|
/* PHIs for virtuals have no control dependency relation on them.
|
We are lost here and must force renaming of the symbol. */
|
We are lost here and must force renaming of the symbol. */
|
if (!is_gimple_reg (gimple_phi_result (phi)))
|
if (!is_gimple_reg (gimple_phi_result (phi)))
|
{
|
{
|
mark_virtual_phi_result_for_renaming (phi);
|
mark_virtual_phi_result_for_renaming (phi);
|
remove_phi_node (&gsi, true);
|
remove_phi_node (&gsi, true);
|
continue;
|
continue;
|
}
|
}
|
|
|
/* Dead PHI do not imply control dependency. */
|
/* Dead PHI do not imply control dependency. */
|
if (!gimple_plf (phi, STMT_NECESSARY))
|
if (!gimple_plf (phi, STMT_NECESSARY))
|
{
|
{
|
gsi_next (&gsi);
|
gsi_next (&gsi);
|
continue;
|
continue;
|
}
|
}
|
|
|
op = gimple_phi_arg_def (phi, e2->dest_idx);
|
op = gimple_phi_arg_def (phi, e2->dest_idx);
|
locus = gimple_phi_arg_location (phi, e2->dest_idx);
|
locus = gimple_phi_arg_location (phi, e2->dest_idx);
|
add_phi_arg (phi, op, e, locus);
|
add_phi_arg (phi, op, e, locus);
|
/* The resulting PHI if not dead can only be degenerate. */
|
/* The resulting PHI if not dead can only be degenerate. */
|
gcc_assert (degenerate_phi_p (phi));
|
gcc_assert (degenerate_phi_p (phi));
|
gsi_next (&gsi);
|
gsi_next (&gsi);
|
}
|
}
|
}
|
}
|
return e;
|
return e;
|
}
|
}
|
|
|
/* Remove dead statement pointed to by iterator I. Receives the basic block BB
|
/* Remove dead statement pointed to by iterator I. Receives the basic block BB
|
containing I so that we don't have to look it up. */
|
containing I so that we don't have to look it up. */
|
|
|
static void
|
static void
|
remove_dead_stmt (gimple_stmt_iterator *i, basic_block bb)
|
remove_dead_stmt (gimple_stmt_iterator *i, basic_block bb)
|
{
|
{
|
gimple stmt = gsi_stmt (*i);
|
gimple stmt = gsi_stmt (*i);
|
|
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
{
|
{
|
fprintf (dump_file, "Deleting : ");
|
fprintf (dump_file, "Deleting : ");
|
print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
|
print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
|
fprintf (dump_file, "\n");
|
fprintf (dump_file, "\n");
|
}
|
}
|
|
|
stats.removed++;
|
stats.removed++;
|
|
|
/* If we have determined that a conditional branch statement contributes
|
/* If we have determined that a conditional branch statement contributes
|
nothing to the program, then we not only remove it, but we also change
|
nothing to the program, then we not only remove it, but we also change
|
the flow graph so that the current block will simply fall-thru to its
|
the flow graph so that the current block will simply fall-thru to its
|
immediate post-dominator. The blocks we are circumventing will be
|
immediate post-dominator. The blocks we are circumventing will be
|
removed by cleanup_tree_cfg if this change in the flow graph makes them
|
removed by cleanup_tree_cfg if this change in the flow graph makes them
|
unreachable. */
|
unreachable. */
|
if (is_ctrl_stmt (stmt))
|
if (is_ctrl_stmt (stmt))
|
{
|
{
|
basic_block post_dom_bb;
|
basic_block post_dom_bb;
|
edge e, e2;
|
edge e, e2;
|
edge_iterator ei;
|
edge_iterator ei;
|
|
|
post_dom_bb = get_immediate_dominator (CDI_POST_DOMINATORS, bb);
|
post_dom_bb = get_immediate_dominator (CDI_POST_DOMINATORS, bb);
|
|
|
e = find_edge (bb, post_dom_bb);
|
e = find_edge (bb, post_dom_bb);
|
|
|
/* If edge is already there, try to use it. This avoids need to update
|
/* If edge is already there, try to use it. This avoids need to update
|
PHI nodes. Also watch for cases where post dominator does not exists
|
PHI nodes. Also watch for cases where post dominator does not exists
|
or is exit block. These can happen for infinite loops as we create
|
or is exit block. These can happen for infinite loops as we create
|
fake edges in the dominator tree. */
|
fake edges in the dominator tree. */
|
if (e)
|
if (e)
|
;
|
;
|
else if (! post_dom_bb || post_dom_bb == EXIT_BLOCK_PTR)
|
else if (! post_dom_bb || post_dom_bb == EXIT_BLOCK_PTR)
|
e = EDGE_SUCC (bb, 0);
|
e = EDGE_SUCC (bb, 0);
|
else
|
else
|
e = forward_edge_to_pdom (EDGE_SUCC (bb, 0), post_dom_bb);
|
e = forward_edge_to_pdom (EDGE_SUCC (bb, 0), post_dom_bb);
|
gcc_assert (e);
|
gcc_assert (e);
|
e->probability = REG_BR_PROB_BASE;
|
e->probability = REG_BR_PROB_BASE;
|
e->count = bb->count;
|
e->count = bb->count;
|
|
|
/* The edge is no longer associated with a conditional, so it does
|
/* The edge is no longer associated with a conditional, so it does
|
not have TRUE/FALSE flags. */
|
not have TRUE/FALSE flags. */
|
e->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
|
e->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
|
|
|
/* The lone outgoing edge from BB will be a fallthru edge. */
|
/* The lone outgoing edge from BB will be a fallthru edge. */
|
e->flags |= EDGE_FALLTHRU;
|
e->flags |= EDGE_FALLTHRU;
|
|
|
/* Remove the remaining outgoing edges. */
|
/* Remove the remaining outgoing edges. */
|
for (ei = ei_start (bb->succs); (e2 = ei_safe_edge (ei)); )
|
for (ei = ei_start (bb->succs); (e2 = ei_safe_edge (ei)); )
|
if (e != e2)
|
if (e != e2)
|
{
|
{
|
cfg_altered = true;
|
cfg_altered = true;
|
remove_edge (e2);
|
remove_edge (e2);
|
}
|
}
|
else
|
else
|
ei_next (&ei);
|
ei_next (&ei);
|
}
|
}
|
|
|
/* If this is a store into a variable that is being optimized away,
|
/* If this is a store into a variable that is being optimized away,
|
add a debug bind stmt if possible. */
|
add a debug bind stmt if possible. */
|
if (MAY_HAVE_DEBUG_STMTS
|
if (MAY_HAVE_DEBUG_STMTS
|
&& gimple_assign_single_p (stmt)
|
&& gimple_assign_single_p (stmt)
|
&& is_gimple_val (gimple_assign_rhs1 (stmt)))
|
&& is_gimple_val (gimple_assign_rhs1 (stmt)))
|
{
|
{
|
tree lhs = gimple_assign_lhs (stmt);
|
tree lhs = gimple_assign_lhs (stmt);
|
if ((TREE_CODE (lhs) == VAR_DECL || TREE_CODE (lhs) == PARM_DECL)
|
if ((TREE_CODE (lhs) == VAR_DECL || TREE_CODE (lhs) == PARM_DECL)
|
&& !DECL_IGNORED_P (lhs)
|
&& !DECL_IGNORED_P (lhs)
|
&& is_gimple_reg_type (TREE_TYPE (lhs))
|
&& is_gimple_reg_type (TREE_TYPE (lhs))
|
&& !is_global_var (lhs)
|
&& !is_global_var (lhs)
|
&& !DECL_HAS_VALUE_EXPR_P (lhs))
|
&& !DECL_HAS_VALUE_EXPR_P (lhs))
|
{
|
{
|
tree rhs = gimple_assign_rhs1 (stmt);
|
tree rhs = gimple_assign_rhs1 (stmt);
|
gimple note
|
gimple note
|
= gimple_build_debug_bind (lhs, unshare_expr (rhs), stmt);
|
= gimple_build_debug_bind (lhs, unshare_expr (rhs), stmt);
|
gsi_insert_after (i, note, GSI_SAME_STMT);
|
gsi_insert_after (i, note, GSI_SAME_STMT);
|
}
|
}
|
}
|
}
|
|
|
unlink_stmt_vdef (stmt);
|
unlink_stmt_vdef (stmt);
|
gsi_remove (i, true);
|
gsi_remove (i, true);
|
release_defs (stmt);
|
release_defs (stmt);
|
}
|
}
|
|
|
/* Eliminate unnecessary statements. Any instruction not marked as necessary
|
/* Eliminate unnecessary statements. Any instruction not marked as necessary
|
contributes nothing to the program, and can be deleted. */
|
contributes nothing to the program, and can be deleted. */
|
|
|
static bool
|
static bool
|
eliminate_unnecessary_stmts (void)
|
eliminate_unnecessary_stmts (void)
|
{
|
{
|
bool something_changed = false;
|
bool something_changed = false;
|
basic_block bb;
|
basic_block bb;
|
gimple_stmt_iterator gsi, psi;
|
gimple_stmt_iterator gsi, psi;
|
gimple stmt;
|
gimple stmt;
|
tree call;
|
tree call;
|
VEC (basic_block, heap) *h;
|
VEC (basic_block, heap) *h;
|
|
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
fprintf (dump_file, "\nEliminating unnecessary statements:\n");
|
fprintf (dump_file, "\nEliminating unnecessary statements:\n");
|
|
|
clear_special_calls ();
|
clear_special_calls ();
|
|
|
/* Walking basic blocks and statements in reverse order avoids
|
/* Walking basic blocks and statements in reverse order avoids
|
releasing SSA names before any other DEFs that refer to them are
|
releasing SSA names before any other DEFs that refer to them are
|
released. This helps avoid loss of debug information, as we get
|
released. This helps avoid loss of debug information, as we get
|
a chance to propagate all RHSs of removed SSAs into debug uses,
|
a chance to propagate all RHSs of removed SSAs into debug uses,
|
rather than only the latest ones. E.g., consider:
|
rather than only the latest ones. E.g., consider:
|
|
|
x_3 = y_1 + z_2;
|
x_3 = y_1 + z_2;
|
a_5 = x_3 - b_4;
|
a_5 = x_3 - b_4;
|
# DEBUG a => a_5
|
# DEBUG a => a_5
|
|
|
If we were to release x_3 before a_5, when we reached a_5 and
|
If we were to release x_3 before a_5, when we reached a_5 and
|
tried to substitute it into the debug stmt, we'd see x_3 there,
|
tried to substitute it into the debug stmt, we'd see x_3 there,
|
but x_3's DEF, type, etc would have already been disconnected.
|
but x_3's DEF, type, etc would have already been disconnected.
|
By going backwards, the debug stmt first changes to:
|
By going backwards, the debug stmt first changes to:
|
|
|
# DEBUG a => x_3 - b_4
|
# DEBUG a => x_3 - b_4
|
|
|
and then to:
|
and then to:
|
|
|
# DEBUG a => y_1 + z_2 - b_4
|
# DEBUG a => y_1 + z_2 - b_4
|
|
|
as desired. */
|
as desired. */
|
gcc_assert (dom_info_available_p (CDI_DOMINATORS));
|
gcc_assert (dom_info_available_p (CDI_DOMINATORS));
|
h = get_all_dominated_blocks (CDI_DOMINATORS, single_succ (ENTRY_BLOCK_PTR));
|
h = get_all_dominated_blocks (CDI_DOMINATORS, single_succ (ENTRY_BLOCK_PTR));
|
|
|
while (VEC_length (basic_block, h))
|
while (VEC_length (basic_block, h))
|
{
|
{
|
bb = VEC_pop (basic_block, h);
|
bb = VEC_pop (basic_block, h);
|
|
|
/* Remove dead statements. */
|
/* Remove dead statements. */
|
for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi = psi)
|
for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi = psi)
|
{
|
{
|
stmt = gsi_stmt (gsi);
|
stmt = gsi_stmt (gsi);
|
|
|
psi = gsi;
|
psi = gsi;
|
gsi_prev (&psi);
|
gsi_prev (&psi);
|
|
|
stats.total++;
|
stats.total++;
|
|
|
/* We can mark a call to free as not necessary if the
|
/* We can mark a call to free as not necessary if the
|
defining statement of its argument is an allocation
|
defining statement of its argument is an allocation
|
function and that is not necessary itself. */
|
function and that is not necessary itself. */
|
if (gimple_call_builtin_p (stmt, BUILT_IN_FREE))
|
if (gimple_call_builtin_p (stmt, BUILT_IN_FREE))
|
{
|
{
|
tree ptr = gimple_call_arg (stmt, 0);
|
tree ptr = gimple_call_arg (stmt, 0);
|
tree callee2;
|
tree callee2;
|
gimple def_stmt;
|
gimple def_stmt;
|
if (TREE_CODE (ptr) != SSA_NAME)
|
if (TREE_CODE (ptr) != SSA_NAME)
|
continue;
|
continue;
|
def_stmt = SSA_NAME_DEF_STMT (ptr);
|
def_stmt = SSA_NAME_DEF_STMT (ptr);
|
if (!is_gimple_call (def_stmt)
|
if (!is_gimple_call (def_stmt)
|
|| gimple_plf (def_stmt, STMT_NECESSARY))
|
|| gimple_plf (def_stmt, STMT_NECESSARY))
|
continue;
|
continue;
|
callee2 = gimple_call_fndecl (def_stmt);
|
callee2 = gimple_call_fndecl (def_stmt);
|
if (callee2 == NULL_TREE
|
if (callee2 == NULL_TREE
|
|| DECL_BUILT_IN_CLASS (callee2) != BUILT_IN_NORMAL
|
|| DECL_BUILT_IN_CLASS (callee2) != BUILT_IN_NORMAL
|
|| (DECL_FUNCTION_CODE (callee2) != BUILT_IN_MALLOC
|
|| (DECL_FUNCTION_CODE (callee2) != BUILT_IN_MALLOC
|
&& DECL_FUNCTION_CODE (callee2) != BUILT_IN_CALLOC))
|
&& DECL_FUNCTION_CODE (callee2) != BUILT_IN_CALLOC))
|
continue;
|
continue;
|
gimple_set_plf (stmt, STMT_NECESSARY, false);
|
gimple_set_plf (stmt, STMT_NECESSARY, false);
|
}
|
}
|
|
|
/* If GSI is not necessary then remove it. */
|
/* If GSI is not necessary then remove it. */
|
if (!gimple_plf (stmt, STMT_NECESSARY))
|
if (!gimple_plf (stmt, STMT_NECESSARY))
|
{
|
{
|
if (!is_gimple_debug (stmt))
|
if (!is_gimple_debug (stmt))
|
something_changed = true;
|
something_changed = true;
|
remove_dead_stmt (&gsi, bb);
|
remove_dead_stmt (&gsi, bb);
|
}
|
}
|
else if (is_gimple_call (stmt))
|
else if (is_gimple_call (stmt))
|
{
|
{
|
tree name = gimple_call_lhs (stmt);
|
tree name = gimple_call_lhs (stmt);
|
|
|
notice_special_calls (stmt);
|
notice_special_calls (stmt);
|
|
|
/* When LHS of var = call (); is dead, simplify it into
|
/* When LHS of var = call (); is dead, simplify it into
|
call (); saving one operand. */
|
call (); saving one operand. */
|
if (name
|
if (name
|
&& TREE_CODE (name) == SSA_NAME
|
&& TREE_CODE (name) == SSA_NAME
|
&& !TEST_BIT (processed, SSA_NAME_VERSION (name))
|
&& !TEST_BIT (processed, SSA_NAME_VERSION (name))
|
/* Avoid doing so for allocation calls which we
|
/* Avoid doing so for allocation calls which we
|
did not mark as necessary, it will confuse the
|
did not mark as necessary, it will confuse the
|
special logic we apply to malloc/free pair removal. */
|
special logic we apply to malloc/free pair removal. */
|
&& (!(call = gimple_call_fndecl (stmt))
|
&& (!(call = gimple_call_fndecl (stmt))
|
|| DECL_BUILT_IN_CLASS (call) != BUILT_IN_NORMAL
|
|| DECL_BUILT_IN_CLASS (call) != BUILT_IN_NORMAL
|
|| (DECL_FUNCTION_CODE (call) != BUILT_IN_MALLOC
|
|| (DECL_FUNCTION_CODE (call) != BUILT_IN_MALLOC
|
&& DECL_FUNCTION_CODE (call) != BUILT_IN_CALLOC
|
&& DECL_FUNCTION_CODE (call) != BUILT_IN_CALLOC
|
&& DECL_FUNCTION_CODE (call) != BUILT_IN_ALLOCA
|
&& DECL_FUNCTION_CODE (call) != BUILT_IN_ALLOCA
|
&& (DECL_FUNCTION_CODE (call)
|
&& (DECL_FUNCTION_CODE (call)
|
!= BUILT_IN_ALLOCA_WITH_ALIGN))))
|
!= BUILT_IN_ALLOCA_WITH_ALIGN))))
|
{
|
{
|
something_changed = true;
|
something_changed = true;
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
{
|
{
|
fprintf (dump_file, "Deleting LHS of call: ");
|
fprintf (dump_file, "Deleting LHS of call: ");
|
print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
|
print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
|
fprintf (dump_file, "\n");
|
fprintf (dump_file, "\n");
|
}
|
}
|
|
|
gimple_call_set_lhs (stmt, NULL_TREE);
|
gimple_call_set_lhs (stmt, NULL_TREE);
|
maybe_clean_or_replace_eh_stmt (stmt, stmt);
|
maybe_clean_or_replace_eh_stmt (stmt, stmt);
|
update_stmt (stmt);
|
update_stmt (stmt);
|
release_ssa_name (name);
|
release_ssa_name (name);
|
}
|
}
|
}
|
}
|
}
|
}
|
}
|
}
|
|
|
VEC_free (basic_block, heap, h);
|
VEC_free (basic_block, heap, h);
|
|
|
/* Since we don't track liveness of virtual PHI nodes, it is possible that we
|
/* Since we don't track liveness of virtual PHI nodes, it is possible that we
|
rendered some PHI nodes unreachable while they are still in use.
|
rendered some PHI nodes unreachable while they are still in use.
|
Mark them for renaming. */
|
Mark them for renaming. */
|
if (cfg_altered)
|
if (cfg_altered)
|
{
|
{
|
basic_block prev_bb;
|
basic_block prev_bb;
|
|
|
find_unreachable_blocks ();
|
find_unreachable_blocks ();
|
|
|
/* Delete all unreachable basic blocks in reverse dominator order. */
|
/* Delete all unreachable basic blocks in reverse dominator order. */
|
for (bb = EXIT_BLOCK_PTR->prev_bb; bb != ENTRY_BLOCK_PTR; bb = prev_bb)
|
for (bb = EXIT_BLOCK_PTR->prev_bb; bb != ENTRY_BLOCK_PTR; bb = prev_bb)
|
{
|
{
|
prev_bb = bb->prev_bb;
|
prev_bb = bb->prev_bb;
|
|
|
if (!TEST_BIT (bb_contains_live_stmts, bb->index)
|
if (!TEST_BIT (bb_contains_live_stmts, bb->index)
|
|| !(bb->flags & BB_REACHABLE))
|
|| !(bb->flags & BB_REACHABLE))
|
{
|
{
|
for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
|
for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
|
if (!is_gimple_reg (gimple_phi_result (gsi_stmt (gsi))))
|
if (!is_gimple_reg (gimple_phi_result (gsi_stmt (gsi))))
|
{
|
{
|
bool found = false;
|
bool found = false;
|
imm_use_iterator iter;
|
imm_use_iterator iter;
|
|
|
FOR_EACH_IMM_USE_STMT (stmt, iter, gimple_phi_result (gsi_stmt (gsi)))
|
FOR_EACH_IMM_USE_STMT (stmt, iter, gimple_phi_result (gsi_stmt (gsi)))
|
{
|
{
|
if (!(gimple_bb (stmt)->flags & BB_REACHABLE))
|
if (!(gimple_bb (stmt)->flags & BB_REACHABLE))
|
continue;
|
continue;
|
if (gimple_code (stmt) == GIMPLE_PHI
|
if (gimple_code (stmt) == GIMPLE_PHI
|
|| gimple_plf (stmt, STMT_NECESSARY))
|
|| gimple_plf (stmt, STMT_NECESSARY))
|
{
|
{
|
found = true;
|
found = true;
|
BREAK_FROM_IMM_USE_STMT (iter);
|
BREAK_FROM_IMM_USE_STMT (iter);
|
}
|
}
|
}
|
}
|
if (found)
|
if (found)
|
mark_virtual_phi_result_for_renaming (gsi_stmt (gsi));
|
mark_virtual_phi_result_for_renaming (gsi_stmt (gsi));
|
}
|
}
|
|
|
if (!(bb->flags & BB_REACHABLE))
|
if (!(bb->flags & BB_REACHABLE))
|
{
|
{
|
/* Speed up the removal of blocks that don't
|
/* Speed up the removal of blocks that don't
|
dominate others. Walking backwards, this should
|
dominate others. Walking backwards, this should
|
be the common case. ??? Do we need to recompute
|
be the common case. ??? Do we need to recompute
|
dominators because of cfg_altered? */
|
dominators because of cfg_altered? */
|
if (!MAY_HAVE_DEBUG_STMTS
|
if (!MAY_HAVE_DEBUG_STMTS
|
|| !first_dom_son (CDI_DOMINATORS, bb))
|
|| !first_dom_son (CDI_DOMINATORS, bb))
|
delete_basic_block (bb);
|
delete_basic_block (bb);
|
else
|
else
|
{
|
{
|
h = get_all_dominated_blocks (CDI_DOMINATORS, bb);
|
h = get_all_dominated_blocks (CDI_DOMINATORS, bb);
|
|
|
while (VEC_length (basic_block, h))
|
while (VEC_length (basic_block, h))
|
{
|
{
|
bb = VEC_pop (basic_block, h);
|
bb = VEC_pop (basic_block, h);
|
prev_bb = bb->prev_bb;
|
prev_bb = bb->prev_bb;
|
/* Rearrangements to the CFG may have failed
|
/* Rearrangements to the CFG may have failed
|
to update the dominators tree, so that
|
to update the dominators tree, so that
|
formerly-dominated blocks are now
|
formerly-dominated blocks are now
|
otherwise reachable. */
|
otherwise reachable. */
|
if (!!(bb->flags & BB_REACHABLE))
|
if (!!(bb->flags & BB_REACHABLE))
|
continue;
|
continue;
|
delete_basic_block (bb);
|
delete_basic_block (bb);
|
}
|
}
|
|
|
VEC_free (basic_block, heap, h);
|
VEC_free (basic_block, heap, h);
|
}
|
}
|
}
|
}
|
}
|
}
|
}
|
}
|
}
|
}
|
FOR_EACH_BB (bb)
|
FOR_EACH_BB (bb)
|
{
|
{
|
/* Remove dead PHI nodes. */
|
/* Remove dead PHI nodes. */
|
something_changed |= remove_dead_phis (bb);
|
something_changed |= remove_dead_phis (bb);
|
}
|
}
|
|
|
return something_changed;
|
return something_changed;
|
}
|
}
|
|
|
|
|
/* Print out removed statement statistics. */
|
/* Print out removed statement statistics. */
|
|
|
static void
|
static void
|
print_stats (void)
|
print_stats (void)
|
{
|
{
|
float percg;
|
float percg;
|
|
|
percg = ((float) stats.removed / (float) stats.total) * 100;
|
percg = ((float) stats.removed / (float) stats.total) * 100;
|
fprintf (dump_file, "Removed %d of %d statements (%d%%)\n",
|
fprintf (dump_file, "Removed %d of %d statements (%d%%)\n",
|
stats.removed, stats.total, (int) percg);
|
stats.removed, stats.total, (int) percg);
|
|
|
if (stats.total_phis == 0)
|
if (stats.total_phis == 0)
|
percg = 0;
|
percg = 0;
|
else
|
else
|
percg = ((float) stats.removed_phis / (float) stats.total_phis) * 100;
|
percg = ((float) stats.removed_phis / (float) stats.total_phis) * 100;
|
|
|
fprintf (dump_file, "Removed %d of %d PHI nodes (%d%%)\n",
|
fprintf (dump_file, "Removed %d of %d PHI nodes (%d%%)\n",
|
stats.removed_phis, stats.total_phis, (int) percg);
|
stats.removed_phis, stats.total_phis, (int) percg);
|
}
|
}
|
|
|
/* Initialization for this pass. Set up the used data structures. */
|
/* Initialization for this pass. Set up the used data structures. */
|
|
|
static void
|
static void
|
tree_dce_init (bool aggressive)
|
tree_dce_init (bool aggressive)
|
{
|
{
|
memset ((void *) &stats, 0, sizeof (stats));
|
memset ((void *) &stats, 0, sizeof (stats));
|
|
|
if (aggressive)
|
if (aggressive)
|
{
|
{
|
int i;
|
int i;
|
|
|
control_dependence_map = XNEWVEC (bitmap, last_basic_block);
|
control_dependence_map = XNEWVEC (bitmap, last_basic_block);
|
for (i = 0; i < last_basic_block; ++i)
|
for (i = 0; i < last_basic_block; ++i)
|
control_dependence_map[i] = BITMAP_ALLOC (NULL);
|
control_dependence_map[i] = BITMAP_ALLOC (NULL);
|
|
|
last_stmt_necessary = sbitmap_alloc (last_basic_block);
|
last_stmt_necessary = sbitmap_alloc (last_basic_block);
|
sbitmap_zero (last_stmt_necessary);
|
sbitmap_zero (last_stmt_necessary);
|
bb_contains_live_stmts = sbitmap_alloc (last_basic_block);
|
bb_contains_live_stmts = sbitmap_alloc (last_basic_block);
|
sbitmap_zero (bb_contains_live_stmts);
|
sbitmap_zero (bb_contains_live_stmts);
|
}
|
}
|
|
|
processed = sbitmap_alloc (num_ssa_names + 1);
|
processed = sbitmap_alloc (num_ssa_names + 1);
|
sbitmap_zero (processed);
|
sbitmap_zero (processed);
|
|
|
worklist = VEC_alloc (gimple, heap, 64);
|
worklist = VEC_alloc (gimple, heap, 64);
|
cfg_altered = false;
|
cfg_altered = false;
|
}
|
}
|
|
|
/* Cleanup after this pass. */
|
/* Cleanup after this pass. */
|
|
|
static void
|
static void
|
tree_dce_done (bool aggressive)
|
tree_dce_done (bool aggressive)
|
{
|
{
|
if (aggressive)
|
if (aggressive)
|
{
|
{
|
int i;
|
int i;
|
|
|
for (i = 0; i < last_basic_block; ++i)
|
for (i = 0; i < last_basic_block; ++i)
|
BITMAP_FREE (control_dependence_map[i]);
|
BITMAP_FREE (control_dependence_map[i]);
|
free (control_dependence_map);
|
free (control_dependence_map);
|
|
|
sbitmap_free (visited_control_parents);
|
sbitmap_free (visited_control_parents);
|
sbitmap_free (last_stmt_necessary);
|
sbitmap_free (last_stmt_necessary);
|
sbitmap_free (bb_contains_live_stmts);
|
sbitmap_free (bb_contains_live_stmts);
|
bb_contains_live_stmts = NULL;
|
bb_contains_live_stmts = NULL;
|
}
|
}
|
|
|
sbitmap_free (processed);
|
sbitmap_free (processed);
|
|
|
VEC_free (gimple, heap, worklist);
|
VEC_free (gimple, heap, worklist);
|
}
|
}
|
|
|
/* Main routine to eliminate dead code.
|
/* Main routine to eliminate dead code.
|
|
|
AGGRESSIVE controls the aggressiveness of the algorithm.
|
AGGRESSIVE controls the aggressiveness of the algorithm.
|
In conservative mode, we ignore control dependence and simply declare
|
In conservative mode, we ignore control dependence and simply declare
|
all but the most trivially dead branches necessary. This mode is fast.
|
all but the most trivially dead branches necessary. This mode is fast.
|
In aggressive mode, control dependences are taken into account, which
|
In aggressive mode, control dependences are taken into account, which
|
results in more dead code elimination, but at the cost of some time.
|
results in more dead code elimination, but at the cost of some time.
|
|
|
FIXME: Aggressive mode before PRE doesn't work currently because
|
FIXME: Aggressive mode before PRE doesn't work currently because
|
the dominance info is not invalidated after DCE1. This is
|
the dominance info is not invalidated after DCE1. This is
|
not an issue right now because we only run aggressive DCE
|
not an issue right now because we only run aggressive DCE
|
as the last tree SSA pass, but keep this in mind when you
|
as the last tree SSA pass, but keep this in mind when you
|
start experimenting with pass ordering. */
|
start experimenting with pass ordering. */
|
|
|
static unsigned int
|
static unsigned int
|
perform_tree_ssa_dce (bool aggressive)
|
perform_tree_ssa_dce (bool aggressive)
|
{
|
{
|
struct edge_list *el = NULL;
|
struct edge_list *el = NULL;
|
bool something_changed = 0;
|
bool something_changed = 0;
|
|
|
calculate_dominance_info (CDI_DOMINATORS);
|
calculate_dominance_info (CDI_DOMINATORS);
|
|
|
/* Preheaders are needed for SCEV to work.
|
/* Preheaders are needed for SCEV to work.
|
Simple lateches and recorded exits improve chances that loop will
|
Simple lateches and recorded exits improve chances that loop will
|
proved to be finite in testcases such as in loop-15.c and loop-24.c */
|
proved to be finite in testcases such as in loop-15.c and loop-24.c */
|
if (aggressive)
|
if (aggressive)
|
loop_optimizer_init (LOOPS_NORMAL
|
loop_optimizer_init (LOOPS_NORMAL
|
| LOOPS_HAVE_RECORDED_EXITS);
|
| LOOPS_HAVE_RECORDED_EXITS);
|
|
|
tree_dce_init (aggressive);
|
tree_dce_init (aggressive);
|
|
|
if (aggressive)
|
if (aggressive)
|
{
|
{
|
/* Compute control dependence. */
|
/* Compute control dependence. */
|
timevar_push (TV_CONTROL_DEPENDENCES);
|
timevar_push (TV_CONTROL_DEPENDENCES);
|
calculate_dominance_info (CDI_POST_DOMINATORS);
|
calculate_dominance_info (CDI_POST_DOMINATORS);
|
el = create_edge_list ();
|
el = create_edge_list ();
|
find_all_control_dependences (el);
|
find_all_control_dependences (el);
|
timevar_pop (TV_CONTROL_DEPENDENCES);
|
timevar_pop (TV_CONTROL_DEPENDENCES);
|
|
|
visited_control_parents = sbitmap_alloc (last_basic_block);
|
visited_control_parents = sbitmap_alloc (last_basic_block);
|
sbitmap_zero (visited_control_parents);
|
sbitmap_zero (visited_control_parents);
|
|
|
mark_dfs_back_edges ();
|
mark_dfs_back_edges ();
|
}
|
}
|
|
|
find_obviously_necessary_stmts (el);
|
find_obviously_necessary_stmts (el);
|
|
|
if (aggressive)
|
if (aggressive)
|
loop_optimizer_finalize ();
|
loop_optimizer_finalize ();
|
|
|
longest_chain = 0;
|
longest_chain = 0;
|
total_chain = 0;
|
total_chain = 0;
|
nr_walks = 0;
|
nr_walks = 0;
|
chain_ovfl = false;
|
chain_ovfl = false;
|
visited = BITMAP_ALLOC (NULL);
|
visited = BITMAP_ALLOC (NULL);
|
propagate_necessity (el);
|
propagate_necessity (el);
|
BITMAP_FREE (visited);
|
BITMAP_FREE (visited);
|
|
|
something_changed |= eliminate_unnecessary_stmts ();
|
something_changed |= eliminate_unnecessary_stmts ();
|
something_changed |= cfg_altered;
|
something_changed |= cfg_altered;
|
|
|
/* We do not update postdominators, so free them unconditionally. */
|
/* We do not update postdominators, so free them unconditionally. */
|
free_dominance_info (CDI_POST_DOMINATORS);
|
free_dominance_info (CDI_POST_DOMINATORS);
|
|
|
/* If we removed paths in the CFG, then we need to update
|
/* If we removed paths in the CFG, then we need to update
|
dominators as well. I haven't investigated the possibility
|
dominators as well. I haven't investigated the possibility
|
of incrementally updating dominators. */
|
of incrementally updating dominators. */
|
if (cfg_altered)
|
if (cfg_altered)
|
free_dominance_info (CDI_DOMINATORS);
|
free_dominance_info (CDI_DOMINATORS);
|
|
|
statistics_counter_event (cfun, "Statements deleted", stats.removed);
|
statistics_counter_event (cfun, "Statements deleted", stats.removed);
|
statistics_counter_event (cfun, "PHI nodes deleted", stats.removed_phis);
|
statistics_counter_event (cfun, "PHI nodes deleted", stats.removed_phis);
|
|
|
/* Debugging dumps. */
|
/* Debugging dumps. */
|
if (dump_file && (dump_flags & (TDF_STATS|TDF_DETAILS)))
|
if (dump_file && (dump_flags & (TDF_STATS|TDF_DETAILS)))
|
print_stats ();
|
print_stats ();
|
|
|
tree_dce_done (aggressive);
|
tree_dce_done (aggressive);
|
|
|
free_edge_list (el);
|
free_edge_list (el);
|
|
|
if (something_changed)
|
if (something_changed)
|
return (TODO_update_ssa | TODO_cleanup_cfg | TODO_ggc_collect
|
return (TODO_update_ssa | TODO_cleanup_cfg | TODO_ggc_collect
|
| TODO_remove_unused_locals);
|
| TODO_remove_unused_locals);
|
else
|
else
|
return 0;
|
return 0;
|
}
|
}
|
|
|
/* Pass entry points. */
|
/* Pass entry points. */
|
static unsigned int
|
static unsigned int
|
tree_ssa_dce (void)
|
tree_ssa_dce (void)
|
{
|
{
|
return perform_tree_ssa_dce (/*aggressive=*/false);
|
return perform_tree_ssa_dce (/*aggressive=*/false);
|
}
|
}
|
|
|
static unsigned int
|
static unsigned int
|
tree_ssa_dce_loop (void)
|
tree_ssa_dce_loop (void)
|
{
|
{
|
unsigned int todo;
|
unsigned int todo;
|
todo = perform_tree_ssa_dce (/*aggressive=*/false);
|
todo = perform_tree_ssa_dce (/*aggressive=*/false);
|
if (todo)
|
if (todo)
|
{
|
{
|
free_numbers_of_iterations_estimates ();
|
free_numbers_of_iterations_estimates ();
|
scev_reset ();
|
scev_reset ();
|
}
|
}
|
return todo;
|
return todo;
|
}
|
}
|
|
|
static unsigned int
|
static unsigned int
|
tree_ssa_cd_dce (void)
|
tree_ssa_cd_dce (void)
|
{
|
{
|
return perform_tree_ssa_dce (/*aggressive=*/optimize >= 2);
|
return perform_tree_ssa_dce (/*aggressive=*/optimize >= 2);
|
}
|
}
|
|
|
static bool
|
static bool
|
gate_dce (void)
|
gate_dce (void)
|
{
|
{
|
return flag_tree_dce != 0;
|
return flag_tree_dce != 0;
|
}
|
}
|
|
|
struct gimple_opt_pass pass_dce =
|
struct gimple_opt_pass pass_dce =
|
{
|
{
|
{
|
{
|
GIMPLE_PASS,
|
GIMPLE_PASS,
|
"dce", /* name */
|
"dce", /* name */
|
gate_dce, /* gate */
|
gate_dce, /* gate */
|
tree_ssa_dce, /* execute */
|
tree_ssa_dce, /* execute */
|
NULL, /* sub */
|
NULL, /* sub */
|
NULL, /* next */
|
NULL, /* next */
|
0, /* static_pass_number */
|
0, /* static_pass_number */
|
TV_TREE_DCE, /* tv_id */
|
TV_TREE_DCE, /* tv_id */
|
PROP_cfg | PROP_ssa, /* properties_required */
|
PROP_cfg | PROP_ssa, /* properties_required */
|
0, /* properties_provided */
|
0, /* properties_provided */
|
0, /* properties_destroyed */
|
0, /* properties_destroyed */
|
0, /* todo_flags_start */
|
0, /* todo_flags_start */
|
TODO_verify_ssa /* todo_flags_finish */
|
TODO_verify_ssa /* todo_flags_finish */
|
}
|
}
|
};
|
};
|
|
|
struct gimple_opt_pass pass_dce_loop =
|
struct gimple_opt_pass pass_dce_loop =
|
{
|
{
|
{
|
{
|
GIMPLE_PASS,
|
GIMPLE_PASS,
|
"dceloop", /* name */
|
"dceloop", /* name */
|
gate_dce, /* gate */
|
gate_dce, /* gate */
|
tree_ssa_dce_loop, /* execute */
|
tree_ssa_dce_loop, /* execute */
|
NULL, /* sub */
|
NULL, /* sub */
|
NULL, /* next */
|
NULL, /* next */
|
0, /* static_pass_number */
|
0, /* static_pass_number */
|
TV_TREE_DCE, /* tv_id */
|
TV_TREE_DCE, /* tv_id */
|
PROP_cfg | PROP_ssa, /* properties_required */
|
PROP_cfg | PROP_ssa, /* properties_required */
|
0, /* properties_provided */
|
0, /* properties_provided */
|
0, /* properties_destroyed */
|
0, /* properties_destroyed */
|
0, /* todo_flags_start */
|
0, /* todo_flags_start */
|
TODO_verify_ssa /* todo_flags_finish */
|
TODO_verify_ssa /* todo_flags_finish */
|
}
|
}
|
};
|
};
|
|
|
struct gimple_opt_pass pass_cd_dce =
|
struct gimple_opt_pass pass_cd_dce =
|
{
|
{
|
{
|
{
|
GIMPLE_PASS,
|
GIMPLE_PASS,
|
"cddce", /* name */
|
"cddce", /* name */
|
gate_dce, /* gate */
|
gate_dce, /* gate */
|
tree_ssa_cd_dce, /* execute */
|
tree_ssa_cd_dce, /* execute */
|
NULL, /* sub */
|
NULL, /* sub */
|
NULL, /* next */
|
NULL, /* next */
|
0, /* static_pass_number */
|
0, /* static_pass_number */
|
TV_TREE_CD_DCE, /* tv_id */
|
TV_TREE_CD_DCE, /* tv_id */
|
PROP_cfg | PROP_ssa, /* properties_required */
|
PROP_cfg | PROP_ssa, /* properties_required */
|
0, /* properties_provided */
|
0, /* properties_provided */
|
0, /* properties_destroyed */
|
0, /* properties_destroyed */
|
0, /* todo_flags_start */
|
0, /* todo_flags_start */
|
TODO_verify_ssa
|
TODO_verify_ssa
|
| TODO_verify_flow /* todo_flags_finish */
|
| TODO_verify_flow /* todo_flags_finish */
|
}
|
}
|
};
|
};
|
|
|
