/* Generic SSA value propagation engine.
|
/* Generic SSA value propagation engine.
|
Copyright (C) 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
|
Copyright (C) 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
|
Contributed by Diego Novillo <dnovillo@redhat.com>
|
Contributed by Diego Novillo <dnovillo@redhat.com>
|
|
|
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/>. */
|
|
|
#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 "flags.h"
|
#include "flags.h"
|
#include "rtl.h"
|
#include "rtl.h"
|
#include "tm_p.h"
|
#include "tm_p.h"
|
#include "ggc.h"
|
#include "ggc.h"
|
#include "basic-block.h"
|
#include "basic-block.h"
|
#include "output.h"
|
#include "output.h"
|
#include "expr.h"
|
#include "expr.h"
|
#include "function.h"
|
#include "function.h"
|
#include "diagnostic.h"
|
#include "diagnostic.h"
|
#include "timevar.h"
|
#include "timevar.h"
|
#include "tree-dump.h"
|
#include "tree-dump.h"
|
#include "tree-flow.h"
|
#include "tree-flow.h"
|
#include "tree-pass.h"
|
#include "tree-pass.h"
|
#include "tree-ssa-propagate.h"
|
#include "tree-ssa-propagate.h"
|
#include "langhooks.h"
|
#include "langhooks.h"
|
#include "varray.h"
|
#include "varray.h"
|
#include "vec.h"
|
#include "vec.h"
|
|
|
/* This file implements a generic value propagation engine based on
|
/* This file implements a generic value propagation engine based on
|
the same propagation used by the SSA-CCP algorithm [1].
|
the same propagation used by the SSA-CCP algorithm [1].
|
|
|
Propagation is performed by simulating the execution of every
|
Propagation is performed by simulating the execution of every
|
statement that produces the value being propagated. Simulation
|
statement that produces the value being propagated. Simulation
|
proceeds as follows:
|
proceeds as follows:
|
|
|
1- Initially, all edges of the CFG are marked not executable and
|
1- Initially, all edges of the CFG are marked not executable and
|
the CFG worklist is seeded with all the statements in the entry
|
the CFG worklist is seeded with all the statements in the entry
|
basic block (block 0).
|
basic block (block 0).
|
|
|
2- Every statement S is simulated with a call to the call-back
|
2- Every statement S is simulated with a call to the call-back
|
function SSA_PROP_VISIT_STMT. This evaluation may produce 3
|
function SSA_PROP_VISIT_STMT. This evaluation may produce 3
|
results:
|
results:
|
|
|
SSA_PROP_NOT_INTERESTING: Statement S produces nothing of
|
SSA_PROP_NOT_INTERESTING: Statement S produces nothing of
|
interest and does not affect any of the work lists.
|
interest and does not affect any of the work lists.
|
|
|
SSA_PROP_VARYING: The value produced by S cannot be determined
|
SSA_PROP_VARYING: The value produced by S cannot be determined
|
at compile time. Further simulation of S is not required.
|
at compile time. Further simulation of S is not required.
|
If S is a conditional jump, all the outgoing edges for the
|
If S is a conditional jump, all the outgoing edges for the
|
block are considered executable and added to the work
|
block are considered executable and added to the work
|
list.
|
list.
|
|
|
SSA_PROP_INTERESTING: S produces a value that can be computed
|
SSA_PROP_INTERESTING: S produces a value that can be computed
|
at compile time. Its result can be propagated into the
|
at compile time. Its result can be propagated into the
|
statements that feed from S. Furthermore, if S is a
|
statements that feed from S. Furthermore, if S is a
|
conditional jump, only the edge known to be taken is added
|
conditional jump, only the edge known to be taken is added
|
to the work list. Edges that are known not to execute are
|
to the work list. Edges that are known not to execute are
|
never simulated.
|
never simulated.
|
|
|
3- PHI nodes are simulated with a call to SSA_PROP_VISIT_PHI. The
|
3- PHI nodes are simulated with a call to SSA_PROP_VISIT_PHI. The
|
return value from SSA_PROP_VISIT_PHI has the same semantics as
|
return value from SSA_PROP_VISIT_PHI has the same semantics as
|
described in #2.
|
described in #2.
|
|
|
4- Three work lists are kept. Statements are only added to these
|
4- Three work lists are kept. Statements are only added to these
|
lists if they produce one of SSA_PROP_INTERESTING or
|
lists if they produce one of SSA_PROP_INTERESTING or
|
SSA_PROP_VARYING.
|
SSA_PROP_VARYING.
|
|
|
CFG_BLOCKS contains the list of blocks to be simulated.
|
CFG_BLOCKS contains the list of blocks to be simulated.
|
Blocks are added to this list if their incoming edges are
|
Blocks are added to this list if their incoming edges are
|
found executable.
|
found executable.
|
|
|
VARYING_SSA_EDGES contains the list of statements that feed
|
VARYING_SSA_EDGES contains the list of statements that feed
|
from statements that produce an SSA_PROP_VARYING result.
|
from statements that produce an SSA_PROP_VARYING result.
|
These are simulated first to speed up processing.
|
These are simulated first to speed up processing.
|
|
|
INTERESTING_SSA_EDGES contains the list of statements that
|
INTERESTING_SSA_EDGES contains the list of statements that
|
feed from statements that produce an SSA_PROP_INTERESTING
|
feed from statements that produce an SSA_PROP_INTERESTING
|
result.
|
result.
|
|
|
5- Simulation terminates when all three work lists are drained.
|
5- Simulation terminates when all three work lists are drained.
|
|
|
Before calling ssa_propagate, it is important to clear
|
Before calling ssa_propagate, it is important to clear
|
DONT_SIMULATE_AGAIN for all the statements in the program that
|
DONT_SIMULATE_AGAIN for all the statements in the program that
|
should be simulated. This initialization allows an implementation
|
should be simulated. This initialization allows an implementation
|
to specify which statements should never be simulated.
|
to specify which statements should never be simulated.
|
|
|
It is also important to compute def-use information before calling
|
It is also important to compute def-use information before calling
|
ssa_propagate.
|
ssa_propagate.
|
|
|
References:
|
References:
|
|
|
[1] Constant propagation with conditional branches,
|
[1] Constant propagation with conditional branches,
|
Wegman and Zadeck, ACM TOPLAS 13(2):181-210.
|
Wegman and Zadeck, ACM TOPLAS 13(2):181-210.
|
|
|
[2] Building an Optimizing Compiler,
|
[2] Building an Optimizing Compiler,
|
Robert Morgan, Butterworth-Heinemann, 1998, Section 8.9.
|
Robert Morgan, Butterworth-Heinemann, 1998, Section 8.9.
|
|
|
[3] Advanced Compiler Design and Implementation,
|
[3] Advanced Compiler Design and Implementation,
|
Steven Muchnick, Morgan Kaufmann, 1997, Section 12.6 */
|
Steven Muchnick, Morgan Kaufmann, 1997, Section 12.6 */
|
|
|
/* Function pointers used to parameterize the propagation engine. */
|
/* Function pointers used to parameterize the propagation engine. */
|
static ssa_prop_visit_stmt_fn ssa_prop_visit_stmt;
|
static ssa_prop_visit_stmt_fn ssa_prop_visit_stmt;
|
static ssa_prop_visit_phi_fn ssa_prop_visit_phi;
|
static ssa_prop_visit_phi_fn ssa_prop_visit_phi;
|
|
|
/* Use the TREE_DEPRECATED bitflag to mark statements that have been
|
/* Use the TREE_DEPRECATED bitflag to mark statements that have been
|
added to one of the SSA edges worklists. This flag is used to
|
added to one of the SSA edges worklists. This flag is used to
|
avoid visiting statements unnecessarily when draining an SSA edge
|
avoid visiting statements unnecessarily when draining an SSA edge
|
worklist. If while simulating a basic block, we find a statement with
|
worklist. If while simulating a basic block, we find a statement with
|
STMT_IN_SSA_EDGE_WORKLIST set, we clear it to prevent SSA edge
|
STMT_IN_SSA_EDGE_WORKLIST set, we clear it to prevent SSA edge
|
processing from visiting it again. */
|
processing from visiting it again. */
|
#define STMT_IN_SSA_EDGE_WORKLIST(T) TREE_DEPRECATED (T)
|
#define STMT_IN_SSA_EDGE_WORKLIST(T) TREE_DEPRECATED (T)
|
|
|
/* A bitmap to keep track of executable blocks in the CFG. */
|
/* A bitmap to keep track of executable blocks in the CFG. */
|
static sbitmap executable_blocks;
|
static sbitmap executable_blocks;
|
|
|
/* Array of control flow edges on the worklist. */
|
/* Array of control flow edges on the worklist. */
|
static VEC(basic_block,heap) *cfg_blocks;
|
static VEC(basic_block,heap) *cfg_blocks;
|
|
|
static unsigned int cfg_blocks_num = 0;
|
static unsigned int cfg_blocks_num = 0;
|
static int cfg_blocks_tail;
|
static int cfg_blocks_tail;
|
static int cfg_blocks_head;
|
static int cfg_blocks_head;
|
|
|
static sbitmap bb_in_list;
|
static sbitmap bb_in_list;
|
|
|
/* Worklist of SSA edges which will need reexamination as their
|
/* Worklist of SSA edges which will need reexamination as their
|
definition has changed. SSA edges are def-use edges in the SSA
|
definition has changed. SSA edges are def-use edges in the SSA
|
web. For each D-U edge, we store the target statement or PHI node
|
web. For each D-U edge, we store the target statement or PHI node
|
U. */
|
U. */
|
static GTY(()) VEC(tree,gc) *interesting_ssa_edges;
|
static GTY(()) VEC(tree,gc) *interesting_ssa_edges;
|
|
|
/* Identical to INTERESTING_SSA_EDGES. For performance reasons, the
|
/* Identical to INTERESTING_SSA_EDGES. For performance reasons, the
|
list of SSA edges is split into two. One contains all SSA edges
|
list of SSA edges is split into two. One contains all SSA edges
|
who need to be reexamined because their lattice value changed to
|
who need to be reexamined because their lattice value changed to
|
varying (this worklist), and the other contains all other SSA edges
|
varying (this worklist), and the other contains all other SSA edges
|
to be reexamined (INTERESTING_SSA_EDGES).
|
to be reexamined (INTERESTING_SSA_EDGES).
|
|
|
Since most values in the program are VARYING, the ideal situation
|
Since most values in the program are VARYING, the ideal situation
|
is to move them to that lattice value as quickly as possible.
|
is to move them to that lattice value as quickly as possible.
|
Thus, it doesn't make sense to process any other type of lattice
|
Thus, it doesn't make sense to process any other type of lattice
|
value until all VARYING values are propagated fully, which is one
|
value until all VARYING values are propagated fully, which is one
|
thing using the VARYING worklist achieves. In addition, if we
|
thing using the VARYING worklist achieves. In addition, if we
|
don't use a separate worklist for VARYING edges, we end up with
|
don't use a separate worklist for VARYING edges, we end up with
|
situations where lattice values move from
|
situations where lattice values move from
|
UNDEFINED->INTERESTING->VARYING instead of UNDEFINED->VARYING. */
|
UNDEFINED->INTERESTING->VARYING instead of UNDEFINED->VARYING. */
|
static GTY(()) VEC(tree,gc) *varying_ssa_edges;
|
static GTY(()) VEC(tree,gc) *varying_ssa_edges;
|
|
|
|
|
/* Return true if the block worklist empty. */
|
/* Return true if the block worklist empty. */
|
|
|
static inline bool
|
static inline bool
|
cfg_blocks_empty_p (void)
|
cfg_blocks_empty_p (void)
|
{
|
{
|
return (cfg_blocks_num == 0);
|
return (cfg_blocks_num == 0);
|
}
|
}
|
|
|
|
|
/* Add a basic block to the worklist. The block must not be already
|
/* Add a basic block to the worklist. The block must not be already
|
in the worklist, and it must not be the ENTRY or EXIT block. */
|
in the worklist, and it must not be the ENTRY or EXIT block. */
|
|
|
static void
|
static void
|
cfg_blocks_add (basic_block bb)
|
cfg_blocks_add (basic_block bb)
|
{
|
{
|
gcc_assert (bb != ENTRY_BLOCK_PTR && bb != EXIT_BLOCK_PTR);
|
gcc_assert (bb != ENTRY_BLOCK_PTR && bb != EXIT_BLOCK_PTR);
|
gcc_assert (!TEST_BIT (bb_in_list, bb->index));
|
gcc_assert (!TEST_BIT (bb_in_list, bb->index));
|
|
|
if (cfg_blocks_empty_p ())
|
if (cfg_blocks_empty_p ())
|
{
|
{
|
cfg_blocks_tail = cfg_blocks_head = 0;
|
cfg_blocks_tail = cfg_blocks_head = 0;
|
cfg_blocks_num = 1;
|
cfg_blocks_num = 1;
|
}
|
}
|
else
|
else
|
{
|
{
|
cfg_blocks_num++;
|
cfg_blocks_num++;
|
if (cfg_blocks_num > VEC_length (basic_block, cfg_blocks))
|
if (cfg_blocks_num > VEC_length (basic_block, cfg_blocks))
|
{
|
{
|
/* We have to grow the array now. Adjust to queue to occupy
|
/* We have to grow the array now. Adjust to queue to occupy
|
the full space of the original array. We do not need to
|
the full space of the original array. We do not need to
|
initialize the newly allocated portion of the array
|
initialize the newly allocated portion of the array
|
because we keep track of CFG_BLOCKS_HEAD and
|
because we keep track of CFG_BLOCKS_HEAD and
|
CFG_BLOCKS_HEAD. */
|
CFG_BLOCKS_HEAD. */
|
cfg_blocks_tail = VEC_length (basic_block, cfg_blocks);
|
cfg_blocks_tail = VEC_length (basic_block, cfg_blocks);
|
cfg_blocks_head = 0;
|
cfg_blocks_head = 0;
|
VEC_safe_grow (basic_block, heap, cfg_blocks, 2 * cfg_blocks_tail);
|
VEC_safe_grow (basic_block, heap, cfg_blocks, 2 * cfg_blocks_tail);
|
}
|
}
|
else
|
else
|
cfg_blocks_tail = ((cfg_blocks_tail + 1)
|
cfg_blocks_tail = ((cfg_blocks_tail + 1)
|
% VEC_length (basic_block, cfg_blocks));
|
% VEC_length (basic_block, cfg_blocks));
|
}
|
}
|
|
|
VEC_replace (basic_block, cfg_blocks, cfg_blocks_tail, bb);
|
VEC_replace (basic_block, cfg_blocks, cfg_blocks_tail, bb);
|
SET_BIT (bb_in_list, bb->index);
|
SET_BIT (bb_in_list, bb->index);
|
}
|
}
|
|
|
|
|
/* Remove a block from the worklist. */
|
/* Remove a block from the worklist. */
|
|
|
static basic_block
|
static basic_block
|
cfg_blocks_get (void)
|
cfg_blocks_get (void)
|
{
|
{
|
basic_block bb;
|
basic_block bb;
|
|
|
bb = VEC_index (basic_block, cfg_blocks, cfg_blocks_head);
|
bb = VEC_index (basic_block, cfg_blocks, cfg_blocks_head);
|
|
|
gcc_assert (!cfg_blocks_empty_p ());
|
gcc_assert (!cfg_blocks_empty_p ());
|
gcc_assert (bb);
|
gcc_assert (bb);
|
|
|
cfg_blocks_head = ((cfg_blocks_head + 1)
|
cfg_blocks_head = ((cfg_blocks_head + 1)
|
% VEC_length (basic_block, cfg_blocks));
|
% VEC_length (basic_block, cfg_blocks));
|
--cfg_blocks_num;
|
--cfg_blocks_num;
|
RESET_BIT (bb_in_list, bb->index);
|
RESET_BIT (bb_in_list, bb->index);
|
|
|
return bb;
|
return bb;
|
}
|
}
|
|
|
|
|
/* We have just defined a new value for VAR. If IS_VARYING is true,
|
/* We have just defined a new value for VAR. If IS_VARYING is true,
|
add all immediate uses of VAR to VARYING_SSA_EDGES, otherwise add
|
add all immediate uses of VAR to VARYING_SSA_EDGES, otherwise add
|
them to INTERESTING_SSA_EDGES. */
|
them to INTERESTING_SSA_EDGES. */
|
|
|
static void
|
static void
|
add_ssa_edge (tree var, bool is_varying)
|
add_ssa_edge (tree var, bool is_varying)
|
{
|
{
|
imm_use_iterator iter;
|
imm_use_iterator iter;
|
use_operand_p use_p;
|
use_operand_p use_p;
|
|
|
FOR_EACH_IMM_USE_FAST (use_p, iter, var)
|
FOR_EACH_IMM_USE_FAST (use_p, iter, var)
|
{
|
{
|
tree use_stmt = USE_STMT (use_p);
|
tree use_stmt = USE_STMT (use_p);
|
|
|
if (!DONT_SIMULATE_AGAIN (use_stmt)
|
if (!DONT_SIMULATE_AGAIN (use_stmt)
|
&& !STMT_IN_SSA_EDGE_WORKLIST (use_stmt))
|
&& !STMT_IN_SSA_EDGE_WORKLIST (use_stmt))
|
{
|
{
|
STMT_IN_SSA_EDGE_WORKLIST (use_stmt) = 1;
|
STMT_IN_SSA_EDGE_WORKLIST (use_stmt) = 1;
|
if (is_varying)
|
if (is_varying)
|
VEC_safe_push (tree, gc, varying_ssa_edges, use_stmt);
|
VEC_safe_push (tree, gc, varying_ssa_edges, use_stmt);
|
else
|
else
|
VEC_safe_push (tree, gc, interesting_ssa_edges, use_stmt);
|
VEC_safe_push (tree, gc, interesting_ssa_edges, use_stmt);
|
}
|
}
|
}
|
}
|
}
|
}
|
|
|
|
|
/* Add edge E to the control flow worklist. */
|
/* Add edge E to the control flow worklist. */
|
|
|
static void
|
static void
|
add_control_edge (edge e)
|
add_control_edge (edge e)
|
{
|
{
|
basic_block bb = e->dest;
|
basic_block bb = e->dest;
|
if (bb == EXIT_BLOCK_PTR)
|
if (bb == EXIT_BLOCK_PTR)
|
return;
|
return;
|
|
|
/* If the edge had already been executed, skip it. */
|
/* If the edge had already been executed, skip it. */
|
if (e->flags & EDGE_EXECUTABLE)
|
if (e->flags & EDGE_EXECUTABLE)
|
return;
|
return;
|
|
|
e->flags |= EDGE_EXECUTABLE;
|
e->flags |= EDGE_EXECUTABLE;
|
|
|
/* If the block is already in the list, we're done. */
|
/* If the block is already in the list, we're done. */
|
if (TEST_BIT (bb_in_list, bb->index))
|
if (TEST_BIT (bb_in_list, bb->index))
|
return;
|
return;
|
|
|
cfg_blocks_add (bb);
|
cfg_blocks_add (bb);
|
|
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
fprintf (dump_file, "Adding Destination of edge (%d -> %d) to worklist\n\n",
|
fprintf (dump_file, "Adding Destination of edge (%d -> %d) to worklist\n\n",
|
e->src->index, e->dest->index);
|
e->src->index, e->dest->index);
|
}
|
}
|
|
|
|
|
/* Simulate the execution of STMT and update the work lists accordingly. */
|
/* Simulate the execution of STMT and update the work lists accordingly. */
|
|
|
static void
|
static void
|
simulate_stmt (tree stmt)
|
simulate_stmt (tree stmt)
|
{
|
{
|
enum ssa_prop_result val = SSA_PROP_NOT_INTERESTING;
|
enum ssa_prop_result val = SSA_PROP_NOT_INTERESTING;
|
edge taken_edge = NULL;
|
edge taken_edge = NULL;
|
tree output_name = NULL_TREE;
|
tree output_name = NULL_TREE;
|
|
|
/* Don't bother visiting statements that are already
|
/* Don't bother visiting statements that are already
|
considered varying by the propagator. */
|
considered varying by the propagator. */
|
if (DONT_SIMULATE_AGAIN (stmt))
|
if (DONT_SIMULATE_AGAIN (stmt))
|
return;
|
return;
|
|
|
if (TREE_CODE (stmt) == PHI_NODE)
|
if (TREE_CODE (stmt) == PHI_NODE)
|
{
|
{
|
val = ssa_prop_visit_phi (stmt);
|
val = ssa_prop_visit_phi (stmt);
|
output_name = PHI_RESULT (stmt);
|
output_name = PHI_RESULT (stmt);
|
}
|
}
|
else
|
else
|
val = ssa_prop_visit_stmt (stmt, &taken_edge, &output_name);
|
val = ssa_prop_visit_stmt (stmt, &taken_edge, &output_name);
|
|
|
if (val == SSA_PROP_VARYING)
|
if (val == SSA_PROP_VARYING)
|
{
|
{
|
DONT_SIMULATE_AGAIN (stmt) = 1;
|
DONT_SIMULATE_AGAIN (stmt) = 1;
|
|
|
/* If the statement produced a new varying value, add the SSA
|
/* If the statement produced a new varying value, add the SSA
|
edges coming out of OUTPUT_NAME. */
|
edges coming out of OUTPUT_NAME. */
|
if (output_name)
|
if (output_name)
|
add_ssa_edge (output_name, true);
|
add_ssa_edge (output_name, true);
|
|
|
/* If STMT transfers control out of its basic block, add
|
/* If STMT transfers control out of its basic block, add
|
all outgoing edges to the work list. */
|
all outgoing edges to the work list. */
|
if (stmt_ends_bb_p (stmt))
|
if (stmt_ends_bb_p (stmt))
|
{
|
{
|
edge e;
|
edge e;
|
edge_iterator ei;
|
edge_iterator ei;
|
basic_block bb = bb_for_stmt (stmt);
|
basic_block bb = bb_for_stmt (stmt);
|
FOR_EACH_EDGE (e, ei, bb->succs)
|
FOR_EACH_EDGE (e, ei, bb->succs)
|
add_control_edge (e);
|
add_control_edge (e);
|
}
|
}
|
}
|
}
|
else if (val == SSA_PROP_INTERESTING)
|
else if (val == SSA_PROP_INTERESTING)
|
{
|
{
|
/* If the statement produced new value, add the SSA edges coming
|
/* If the statement produced new value, add the SSA edges coming
|
out of OUTPUT_NAME. */
|
out of OUTPUT_NAME. */
|
if (output_name)
|
if (output_name)
|
add_ssa_edge (output_name, false);
|
add_ssa_edge (output_name, false);
|
|
|
/* If we know which edge is going to be taken out of this block,
|
/* If we know which edge is going to be taken out of this block,
|
add it to the CFG work list. */
|
add it to the CFG work list. */
|
if (taken_edge)
|
if (taken_edge)
|
add_control_edge (taken_edge);
|
add_control_edge (taken_edge);
|
}
|
}
|
}
|
}
|
|
|
/* Process an SSA edge worklist. WORKLIST is the SSA edge worklist to
|
/* Process an SSA edge worklist. WORKLIST is the SSA edge worklist to
|
drain. This pops statements off the given WORKLIST and processes
|
drain. This pops statements off the given WORKLIST and processes
|
them until there are no more statements on WORKLIST.
|
them until there are no more statements on WORKLIST.
|
We take a pointer to WORKLIST because it may be reallocated when an
|
We take a pointer to WORKLIST because it may be reallocated when an
|
SSA edge is added to it in simulate_stmt. */
|
SSA edge is added to it in simulate_stmt. */
|
|
|
static void
|
static void
|
process_ssa_edge_worklist (VEC(tree,gc) **worklist)
|
process_ssa_edge_worklist (VEC(tree,gc) **worklist)
|
{
|
{
|
/* Drain the entire worklist. */
|
/* Drain the entire worklist. */
|
while (VEC_length (tree, *worklist) > 0)
|
while (VEC_length (tree, *worklist) > 0)
|
{
|
{
|
basic_block bb;
|
basic_block bb;
|
|
|
/* Pull the statement to simulate off the worklist. */
|
/* Pull the statement to simulate off the worklist. */
|
tree stmt = VEC_pop (tree, *worklist);
|
tree stmt = VEC_pop (tree, *worklist);
|
|
|
/* If this statement was already visited by simulate_block, then
|
/* If this statement was already visited by simulate_block, then
|
we don't need to visit it again here. */
|
we don't need to visit it again here. */
|
if (!STMT_IN_SSA_EDGE_WORKLIST (stmt))
|
if (!STMT_IN_SSA_EDGE_WORKLIST (stmt))
|
continue;
|
continue;
|
|
|
/* STMT is no longer in a worklist. */
|
/* STMT is no longer in a worklist. */
|
STMT_IN_SSA_EDGE_WORKLIST (stmt) = 0;
|
STMT_IN_SSA_EDGE_WORKLIST (stmt) = 0;
|
|
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
{
|
{
|
fprintf (dump_file, "\nSimulating statement (from ssa_edges): ");
|
fprintf (dump_file, "\nSimulating statement (from ssa_edges): ");
|
print_generic_stmt (dump_file, stmt, dump_flags);
|
print_generic_stmt (dump_file, stmt, dump_flags);
|
}
|
}
|
|
|
bb = bb_for_stmt (stmt);
|
bb = bb_for_stmt (stmt);
|
|
|
/* PHI nodes are always visited, regardless of whether or not
|
/* PHI nodes are always visited, regardless of whether or not
|
the destination block is executable. Otherwise, visit the
|
the destination block is executable. Otherwise, visit the
|
statement only if its block is marked executable. */
|
statement only if its block is marked executable. */
|
if (TREE_CODE (stmt) == PHI_NODE
|
if (TREE_CODE (stmt) == PHI_NODE
|
|| TEST_BIT (executable_blocks, bb->index))
|
|| TEST_BIT (executable_blocks, bb->index))
|
simulate_stmt (stmt);
|
simulate_stmt (stmt);
|
}
|
}
|
}
|
}
|
|
|
|
|
/* Simulate the execution of BLOCK. Evaluate the statement associated
|
/* Simulate the execution of BLOCK. Evaluate the statement associated
|
with each variable reference inside the block. */
|
with each variable reference inside the block. */
|
|
|
static void
|
static void
|
simulate_block (basic_block block)
|
simulate_block (basic_block block)
|
{
|
{
|
tree phi;
|
tree phi;
|
|
|
/* There is nothing to do for the exit block. */
|
/* There is nothing to do for the exit block. */
|
if (block == EXIT_BLOCK_PTR)
|
if (block == EXIT_BLOCK_PTR)
|
return;
|
return;
|
|
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
fprintf (dump_file, "\nSimulating block %d\n", block->index);
|
fprintf (dump_file, "\nSimulating block %d\n", block->index);
|
|
|
/* Always simulate PHI nodes, even if we have simulated this block
|
/* Always simulate PHI nodes, even if we have simulated this block
|
before. */
|
before. */
|
for (phi = phi_nodes (block); phi; phi = PHI_CHAIN (phi))
|
for (phi = phi_nodes (block); phi; phi = PHI_CHAIN (phi))
|
simulate_stmt (phi);
|
simulate_stmt (phi);
|
|
|
/* If this is the first time we've simulated this block, then we
|
/* If this is the first time we've simulated this block, then we
|
must simulate each of its statements. */
|
must simulate each of its statements. */
|
if (!TEST_BIT (executable_blocks, block->index))
|
if (!TEST_BIT (executable_blocks, block->index))
|
{
|
{
|
block_stmt_iterator j;
|
block_stmt_iterator j;
|
unsigned int normal_edge_count;
|
unsigned int normal_edge_count;
|
edge e, normal_edge;
|
edge e, normal_edge;
|
edge_iterator ei;
|
edge_iterator ei;
|
|
|
/* Note that we have simulated this block. */
|
/* Note that we have simulated this block. */
|
SET_BIT (executable_blocks, block->index);
|
SET_BIT (executable_blocks, block->index);
|
|
|
for (j = bsi_start (block); !bsi_end_p (j); bsi_next (&j))
|
for (j = bsi_start (block); !bsi_end_p (j); bsi_next (&j))
|
{
|
{
|
tree stmt = bsi_stmt (j);
|
tree stmt = bsi_stmt (j);
|
|
|
/* If this statement is already in the worklist then
|
/* If this statement is already in the worklist then
|
"cancel" it. The reevaluation implied by the worklist
|
"cancel" it. The reevaluation implied by the worklist
|
entry will produce the same value we generate here and
|
entry will produce the same value we generate here and
|
thus reevaluating it again from the worklist is
|
thus reevaluating it again from the worklist is
|
pointless. */
|
pointless. */
|
if (STMT_IN_SSA_EDGE_WORKLIST (stmt))
|
if (STMT_IN_SSA_EDGE_WORKLIST (stmt))
|
STMT_IN_SSA_EDGE_WORKLIST (stmt) = 0;
|
STMT_IN_SSA_EDGE_WORKLIST (stmt) = 0;
|
|
|
simulate_stmt (stmt);
|
simulate_stmt (stmt);
|
}
|
}
|
|
|
/* We can not predict when abnormal edges will be executed, so
|
/* We can not predict when abnormal edges will be executed, so
|
once a block is considered executable, we consider any
|
once a block is considered executable, we consider any
|
outgoing abnormal edges as executable.
|
outgoing abnormal edges as executable.
|
|
|
At the same time, if this block has only one successor that is
|
At the same time, if this block has only one successor that is
|
reached by non-abnormal edges, then add that successor to the
|
reached by non-abnormal edges, then add that successor to the
|
worklist. */
|
worklist. */
|
normal_edge_count = 0;
|
normal_edge_count = 0;
|
normal_edge = NULL;
|
normal_edge = NULL;
|
FOR_EACH_EDGE (e, ei, block->succs)
|
FOR_EACH_EDGE (e, ei, block->succs)
|
{
|
{
|
if (e->flags & EDGE_ABNORMAL)
|
if (e->flags & EDGE_ABNORMAL)
|
add_control_edge (e);
|
add_control_edge (e);
|
else
|
else
|
{
|
{
|
normal_edge_count++;
|
normal_edge_count++;
|
normal_edge = e;
|
normal_edge = e;
|
}
|
}
|
}
|
}
|
|
|
if (normal_edge_count == 1)
|
if (normal_edge_count == 1)
|
add_control_edge (normal_edge);
|
add_control_edge (normal_edge);
|
}
|
}
|
}
|
}
|
|
|
|
|
/* Initialize local data structures and work lists. */
|
/* Initialize local data structures and work lists. */
|
|
|
static void
|
static void
|
ssa_prop_init (void)
|
ssa_prop_init (void)
|
{
|
{
|
edge e;
|
edge e;
|
edge_iterator ei;
|
edge_iterator ei;
|
basic_block bb;
|
basic_block bb;
|
size_t i;
|
size_t i;
|
|
|
/* Worklists of SSA edges. */
|
/* Worklists of SSA edges. */
|
interesting_ssa_edges = VEC_alloc (tree, gc, 20);
|
interesting_ssa_edges = VEC_alloc (tree, gc, 20);
|
varying_ssa_edges = VEC_alloc (tree, gc, 20);
|
varying_ssa_edges = VEC_alloc (tree, gc, 20);
|
|
|
executable_blocks = sbitmap_alloc (last_basic_block);
|
executable_blocks = sbitmap_alloc (last_basic_block);
|
sbitmap_zero (executable_blocks);
|
sbitmap_zero (executable_blocks);
|
|
|
bb_in_list = sbitmap_alloc (last_basic_block);
|
bb_in_list = sbitmap_alloc (last_basic_block);
|
sbitmap_zero (bb_in_list);
|
sbitmap_zero (bb_in_list);
|
|
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
dump_immediate_uses (dump_file);
|
dump_immediate_uses (dump_file);
|
|
|
cfg_blocks = VEC_alloc (basic_block, heap, 20);
|
cfg_blocks = VEC_alloc (basic_block, heap, 20);
|
VEC_safe_grow (basic_block, heap, cfg_blocks, 20);
|
VEC_safe_grow (basic_block, heap, cfg_blocks, 20);
|
|
|
/* Initialize the values for every SSA_NAME. */
|
/* Initialize the values for every SSA_NAME. */
|
for (i = 1; i < num_ssa_names; i++)
|
for (i = 1; i < num_ssa_names; i++)
|
if (ssa_name (i))
|
if (ssa_name (i))
|
SSA_NAME_VALUE (ssa_name (i)) = NULL_TREE;
|
SSA_NAME_VALUE (ssa_name (i)) = NULL_TREE;
|
|
|
/* Initially assume that every edge in the CFG is not executable.
|
/* Initially assume that every edge in the CFG is not executable.
|
(including the edges coming out of ENTRY_BLOCK_PTR). */
|
(including the edges coming out of ENTRY_BLOCK_PTR). */
|
FOR_ALL_BB (bb)
|
FOR_ALL_BB (bb)
|
{
|
{
|
block_stmt_iterator si;
|
block_stmt_iterator si;
|
|
|
for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
|
for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
|
STMT_IN_SSA_EDGE_WORKLIST (bsi_stmt (si)) = 0;
|
STMT_IN_SSA_EDGE_WORKLIST (bsi_stmt (si)) = 0;
|
|
|
FOR_EACH_EDGE (e, ei, bb->succs)
|
FOR_EACH_EDGE (e, ei, bb->succs)
|
e->flags &= ~EDGE_EXECUTABLE;
|
e->flags &= ~EDGE_EXECUTABLE;
|
}
|
}
|
|
|
/* Seed the algorithm by adding the successors of the entry block to the
|
/* Seed the algorithm by adding the successors of the entry block to the
|
edge worklist. */
|
edge worklist. */
|
FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
|
FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
|
add_control_edge (e);
|
add_control_edge (e);
|
}
|
}
|
|
|
|
|
/* Free allocated storage. */
|
/* Free allocated storage. */
|
|
|
static void
|
static void
|
ssa_prop_fini (void)
|
ssa_prop_fini (void)
|
{
|
{
|
VEC_free (tree, gc, interesting_ssa_edges);
|
VEC_free (tree, gc, interesting_ssa_edges);
|
VEC_free (tree, gc, varying_ssa_edges);
|
VEC_free (tree, gc, varying_ssa_edges);
|
VEC_free (basic_block, heap, cfg_blocks);
|
VEC_free (basic_block, heap, cfg_blocks);
|
cfg_blocks = NULL;
|
cfg_blocks = NULL;
|
sbitmap_free (bb_in_list);
|
sbitmap_free (bb_in_list);
|
sbitmap_free (executable_blocks);
|
sbitmap_free (executable_blocks);
|
}
|
}
|
|
|
|
|
/* Get the main expression from statement STMT. */
|
/* Get the main expression from statement STMT. */
|
|
|
tree
|
tree
|
get_rhs (tree stmt)
|
get_rhs (tree stmt)
|
{
|
{
|
enum tree_code code = TREE_CODE (stmt);
|
enum tree_code code = TREE_CODE (stmt);
|
|
|
switch (code)
|
switch (code)
|
{
|
{
|
case RETURN_EXPR:
|
case RETURN_EXPR:
|
stmt = TREE_OPERAND (stmt, 0);
|
stmt = TREE_OPERAND (stmt, 0);
|
if (!stmt || TREE_CODE (stmt) != MODIFY_EXPR)
|
if (!stmt || TREE_CODE (stmt) != MODIFY_EXPR)
|
return stmt;
|
return stmt;
|
/* FALLTHRU */
|
/* FALLTHRU */
|
|
|
case MODIFY_EXPR:
|
case MODIFY_EXPR:
|
stmt = TREE_OPERAND (stmt, 1);
|
stmt = TREE_OPERAND (stmt, 1);
|
if (TREE_CODE (stmt) == WITH_SIZE_EXPR)
|
if (TREE_CODE (stmt) == WITH_SIZE_EXPR)
|
return TREE_OPERAND (stmt, 0);
|
return TREE_OPERAND (stmt, 0);
|
else
|
else
|
return stmt;
|
return stmt;
|
|
|
case COND_EXPR:
|
case COND_EXPR:
|
return COND_EXPR_COND (stmt);
|
return COND_EXPR_COND (stmt);
|
case SWITCH_EXPR:
|
case SWITCH_EXPR:
|
return SWITCH_COND (stmt);
|
return SWITCH_COND (stmt);
|
case GOTO_EXPR:
|
case GOTO_EXPR:
|
return GOTO_DESTINATION (stmt);
|
return GOTO_DESTINATION (stmt);
|
case LABEL_EXPR:
|
case LABEL_EXPR:
|
return LABEL_EXPR_LABEL (stmt);
|
return LABEL_EXPR_LABEL (stmt);
|
|
|
default:
|
default:
|
return stmt;
|
return stmt;
|
}
|
}
|
}
|
}
|
|
|
|
|
/* Set the main expression of *STMT_P to EXPR. If EXPR is not a valid
|
/* Set the main expression of *STMT_P to EXPR. If EXPR is not a valid
|
GIMPLE expression no changes are done and the function returns
|
GIMPLE expression no changes are done and the function returns
|
false. */
|
false. */
|
|
|
bool
|
bool
|
set_rhs (tree *stmt_p, tree expr)
|
set_rhs (tree *stmt_p, tree expr)
|
{
|
{
|
tree stmt = *stmt_p, op;
|
tree stmt = *stmt_p, op;
|
enum tree_code code = TREE_CODE (expr);
|
enum tree_code code = TREE_CODE (expr);
|
stmt_ann_t ann;
|
stmt_ann_t ann;
|
tree var;
|
tree var;
|
ssa_op_iter iter;
|
ssa_op_iter iter;
|
|
|
/* Verify the constant folded result is valid gimple. */
|
/* Verify the constant folded result is valid gimple. */
|
if (TREE_CODE_CLASS (code) == tcc_binary
|
if (TREE_CODE_CLASS (code) == tcc_binary
|
|| TREE_CODE_CLASS (code) == tcc_comparison)
|
|| TREE_CODE_CLASS (code) == tcc_comparison)
|
{
|
{
|
if (!is_gimple_val (TREE_OPERAND (expr, 0))
|
if (!is_gimple_val (TREE_OPERAND (expr, 0))
|
|| !is_gimple_val (TREE_OPERAND (expr, 1)))
|
|| !is_gimple_val (TREE_OPERAND (expr, 1)))
|
return false;
|
return false;
|
}
|
}
|
else if (TREE_CODE_CLASS (code) == tcc_unary)
|
else if (TREE_CODE_CLASS (code) == tcc_unary)
|
{
|
{
|
if (!is_gimple_val (TREE_OPERAND (expr, 0)))
|
if (!is_gimple_val (TREE_OPERAND (expr, 0)))
|
return false;
|
return false;
|
}
|
}
|
else if (code == ADDR_EXPR)
|
else if (code == ADDR_EXPR)
|
{
|
{
|
if (TREE_CODE (TREE_OPERAND (expr, 0)) == ARRAY_REF
|
if (TREE_CODE (TREE_OPERAND (expr, 0)) == ARRAY_REF
|
&& !is_gimple_val (TREE_OPERAND (TREE_OPERAND (expr, 0), 1)))
|
&& !is_gimple_val (TREE_OPERAND (TREE_OPERAND (expr, 0), 1)))
|
return false;
|
return false;
|
}
|
}
|
else if (code == COMPOUND_EXPR
|
else if (code == COMPOUND_EXPR
|
|| code == MODIFY_EXPR)
|
|| code == MODIFY_EXPR)
|
return false;
|
return false;
|
|
|
if (EXPR_HAS_LOCATION (stmt)
|
if (EXPR_HAS_LOCATION (stmt)
|
&& EXPR_P (expr)
|
&& EXPR_P (expr)
|
&& ! EXPR_HAS_LOCATION (expr)
|
&& ! EXPR_HAS_LOCATION (expr)
|
&& TREE_SIDE_EFFECTS (expr)
|
&& TREE_SIDE_EFFECTS (expr)
|
&& TREE_CODE (expr) != LABEL_EXPR)
|
&& TREE_CODE (expr) != LABEL_EXPR)
|
SET_EXPR_LOCATION (expr, EXPR_LOCATION (stmt));
|
SET_EXPR_LOCATION (expr, EXPR_LOCATION (stmt));
|
|
|
switch (TREE_CODE (stmt))
|
switch (TREE_CODE (stmt))
|
{
|
{
|
case RETURN_EXPR:
|
case RETURN_EXPR:
|
op = TREE_OPERAND (stmt, 0);
|
op = TREE_OPERAND (stmt, 0);
|
if (TREE_CODE (op) != MODIFY_EXPR)
|
if (TREE_CODE (op) != MODIFY_EXPR)
|
{
|
{
|
TREE_OPERAND (stmt, 0) = expr;
|
TREE_OPERAND (stmt, 0) = expr;
|
break;
|
break;
|
}
|
}
|
stmt = op;
|
stmt = op;
|
/* FALLTHRU */
|
/* FALLTHRU */
|
|
|
case MODIFY_EXPR:
|
case MODIFY_EXPR:
|
op = TREE_OPERAND (stmt, 1);
|
op = TREE_OPERAND (stmt, 1);
|
if (TREE_CODE (op) == WITH_SIZE_EXPR)
|
if (TREE_CODE (op) == WITH_SIZE_EXPR)
|
stmt = op;
|
stmt = op;
|
TREE_OPERAND (stmt, 1) = expr;
|
TREE_OPERAND (stmt, 1) = expr;
|
break;
|
break;
|
|
|
case COND_EXPR:
|
case COND_EXPR:
|
if (!is_gimple_condexpr (expr))
|
if (!is_gimple_condexpr (expr))
|
return false;
|
return false;
|
COND_EXPR_COND (stmt) = expr;
|
COND_EXPR_COND (stmt) = expr;
|
break;
|
break;
|
case SWITCH_EXPR:
|
case SWITCH_EXPR:
|
SWITCH_COND (stmt) = expr;
|
SWITCH_COND (stmt) = expr;
|
break;
|
break;
|
case GOTO_EXPR:
|
case GOTO_EXPR:
|
GOTO_DESTINATION (stmt) = expr;
|
GOTO_DESTINATION (stmt) = expr;
|
break;
|
break;
|
case LABEL_EXPR:
|
case LABEL_EXPR:
|
LABEL_EXPR_LABEL (stmt) = expr;
|
LABEL_EXPR_LABEL (stmt) = expr;
|
break;
|
break;
|
|
|
default:
|
default:
|
/* Replace the whole statement with EXPR. If EXPR has no side
|
/* Replace the whole statement with EXPR. If EXPR has no side
|
effects, then replace *STMT_P with an empty statement. */
|
effects, then replace *STMT_P with an empty statement. */
|
ann = stmt_ann (stmt);
|
ann = stmt_ann (stmt);
|
*stmt_p = TREE_SIDE_EFFECTS (expr) ? expr : build_empty_stmt ();
|
*stmt_p = TREE_SIDE_EFFECTS (expr) ? expr : build_empty_stmt ();
|
(*stmt_p)->common.ann = (tree_ann_t) ann;
|
(*stmt_p)->common.ann = (tree_ann_t) ann;
|
|
|
if (in_ssa_p
|
if (in_ssa_p
|
&& TREE_SIDE_EFFECTS (expr))
|
&& TREE_SIDE_EFFECTS (expr))
|
{
|
{
|
/* Fix all the SSA_NAMEs created by *STMT_P to point to its new
|
/* Fix all the SSA_NAMEs created by *STMT_P to point to its new
|
replacement. */
|
replacement. */
|
FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_DEFS)
|
FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_DEFS)
|
{
|
{
|
if (TREE_CODE (var) == SSA_NAME)
|
if (TREE_CODE (var) == SSA_NAME)
|
SSA_NAME_DEF_STMT (var) = *stmt_p;
|
SSA_NAME_DEF_STMT (var) = *stmt_p;
|
}
|
}
|
}
|
}
|
break;
|
break;
|
}
|
}
|
|
|
return true;
|
return true;
|
}
|
}
|
|
|
|
|
/* Entry point to the propagation engine.
|
/* Entry point to the propagation engine.
|
|
|
VISIT_STMT is called for every statement visited.
|
VISIT_STMT is called for every statement visited.
|
VISIT_PHI is called for every PHI node visited. */
|
VISIT_PHI is called for every PHI node visited. */
|
|
|
void
|
void
|
ssa_propagate (ssa_prop_visit_stmt_fn visit_stmt,
|
ssa_propagate (ssa_prop_visit_stmt_fn visit_stmt,
|
ssa_prop_visit_phi_fn visit_phi)
|
ssa_prop_visit_phi_fn visit_phi)
|
{
|
{
|
ssa_prop_visit_stmt = visit_stmt;
|
ssa_prop_visit_stmt = visit_stmt;
|
ssa_prop_visit_phi = visit_phi;
|
ssa_prop_visit_phi = visit_phi;
|
|
|
ssa_prop_init ();
|
ssa_prop_init ();
|
|
|
/* Iterate until the worklists are empty. */
|
/* Iterate until the worklists are empty. */
|
while (!cfg_blocks_empty_p ()
|
while (!cfg_blocks_empty_p ()
|
|| VEC_length (tree, interesting_ssa_edges) > 0
|
|| VEC_length (tree, interesting_ssa_edges) > 0
|
|| VEC_length (tree, varying_ssa_edges) > 0)
|
|| VEC_length (tree, varying_ssa_edges) > 0)
|
{
|
{
|
if (!cfg_blocks_empty_p ())
|
if (!cfg_blocks_empty_p ())
|
{
|
{
|
/* Pull the next block to simulate off the worklist. */
|
/* Pull the next block to simulate off the worklist. */
|
basic_block dest_block = cfg_blocks_get ();
|
basic_block dest_block = cfg_blocks_get ();
|
simulate_block (dest_block);
|
simulate_block (dest_block);
|
}
|
}
|
|
|
/* In order to move things to varying as quickly as
|
/* In order to move things to varying as quickly as
|
possible,process the VARYING_SSA_EDGES worklist first. */
|
possible,process the VARYING_SSA_EDGES worklist first. */
|
process_ssa_edge_worklist (&varying_ssa_edges);
|
process_ssa_edge_worklist (&varying_ssa_edges);
|
|
|
/* Now process the INTERESTING_SSA_EDGES worklist. */
|
/* Now process the INTERESTING_SSA_EDGES worklist. */
|
process_ssa_edge_worklist (&interesting_ssa_edges);
|
process_ssa_edge_worklist (&interesting_ssa_edges);
|
}
|
}
|
|
|
ssa_prop_fini ();
|
ssa_prop_fini ();
|
}
|
}
|
|
|
|
|
/* Return the first V_MAY_DEF or V_MUST_DEF operand for STMT. */
|
/* Return the first V_MAY_DEF or V_MUST_DEF operand for STMT. */
|
|
|
tree
|
tree
|
first_vdef (tree stmt)
|
first_vdef (tree stmt)
|
{
|
{
|
ssa_op_iter iter;
|
ssa_op_iter iter;
|
tree op;
|
tree op;
|
|
|
/* Simply return the first operand we arrive at. */
|
/* Simply return the first operand we arrive at. */
|
FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_VIRTUAL_DEFS)
|
FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_VIRTUAL_DEFS)
|
return (op);
|
return (op);
|
|
|
gcc_unreachable ();
|
gcc_unreachable ();
|
}
|
}
|
|
|
|
|
/* Return true if STMT is of the form 'LHS = mem_ref', where 'mem_ref'
|
/* Return true if STMT is of the form 'LHS = mem_ref', where 'mem_ref'
|
is a non-volatile pointer dereference, a structure reference or a
|
is a non-volatile pointer dereference, a structure reference or a
|
reference to a single _DECL. Ignore volatile memory references
|
reference to a single _DECL. Ignore volatile memory references
|
because they are not interesting for the optimizers. */
|
because they are not interesting for the optimizers. */
|
|
|
bool
|
bool
|
stmt_makes_single_load (tree stmt)
|
stmt_makes_single_load (tree stmt)
|
{
|
{
|
tree rhs;
|
tree rhs;
|
|
|
if (TREE_CODE (stmt) != MODIFY_EXPR)
|
if (TREE_CODE (stmt) != MODIFY_EXPR)
|
return false;
|
return false;
|
|
|
if (ZERO_SSA_OPERANDS (stmt, SSA_OP_VMAYDEF|SSA_OP_VUSE))
|
if (ZERO_SSA_OPERANDS (stmt, SSA_OP_VMAYDEF|SSA_OP_VUSE))
|
return false;
|
return false;
|
|
|
rhs = TREE_OPERAND (stmt, 1);
|
rhs = TREE_OPERAND (stmt, 1);
|
STRIP_NOPS (rhs);
|
STRIP_NOPS (rhs);
|
|
|
return (!TREE_THIS_VOLATILE (rhs)
|
return (!TREE_THIS_VOLATILE (rhs)
|
&& (DECL_P (rhs)
|
&& (DECL_P (rhs)
|
|| REFERENCE_CLASS_P (rhs)));
|
|| REFERENCE_CLASS_P (rhs)));
|
}
|
}
|
|
|
|
|
/* Return true if STMT is of the form 'mem_ref = RHS', where 'mem_ref'
|
/* Return true if STMT is of the form 'mem_ref = RHS', where 'mem_ref'
|
is a non-volatile pointer dereference, a structure reference or a
|
is a non-volatile pointer dereference, a structure reference or a
|
reference to a single _DECL. Ignore volatile memory references
|
reference to a single _DECL. Ignore volatile memory references
|
because they are not interesting for the optimizers. */
|
because they are not interesting for the optimizers. */
|
|
|
bool
|
bool
|
stmt_makes_single_store (tree stmt)
|
stmt_makes_single_store (tree stmt)
|
{
|
{
|
tree lhs;
|
tree lhs;
|
|
|
if (TREE_CODE (stmt) != MODIFY_EXPR)
|
if (TREE_CODE (stmt) != MODIFY_EXPR)
|
return false;
|
return false;
|
|
|
if (ZERO_SSA_OPERANDS (stmt, SSA_OP_VMAYDEF|SSA_OP_VMUSTDEF))
|
if (ZERO_SSA_OPERANDS (stmt, SSA_OP_VMAYDEF|SSA_OP_VMUSTDEF))
|
return false;
|
return false;
|
|
|
lhs = TREE_OPERAND (stmt, 0);
|
lhs = TREE_OPERAND (stmt, 0);
|
STRIP_NOPS (lhs);
|
STRIP_NOPS (lhs);
|
|
|
return (!TREE_THIS_VOLATILE (lhs)
|
return (!TREE_THIS_VOLATILE (lhs)
|
&& (DECL_P (lhs)
|
&& (DECL_P (lhs)
|
|| REFERENCE_CLASS_P (lhs)));
|
|| REFERENCE_CLASS_P (lhs)));
|
}
|
}
|
|
|
|
|
/* If STMT makes a single memory load and all the virtual use operands
|
/* If STMT makes a single memory load and all the virtual use operands
|
have the same value in array VALUES, return it. Otherwise, return
|
have the same value in array VALUES, return it. Otherwise, return
|
NULL. */
|
NULL. */
|
|
|
prop_value_t *
|
prop_value_t *
|
get_value_loaded_by (tree stmt, prop_value_t *values)
|
get_value_loaded_by (tree stmt, prop_value_t *values)
|
{
|
{
|
ssa_op_iter i;
|
ssa_op_iter i;
|
tree vuse;
|
tree vuse;
|
prop_value_t *prev_val = NULL;
|
prop_value_t *prev_val = NULL;
|
prop_value_t *val = NULL;
|
prop_value_t *val = NULL;
|
|
|
FOR_EACH_SSA_TREE_OPERAND (vuse, stmt, i, SSA_OP_VIRTUAL_USES)
|
FOR_EACH_SSA_TREE_OPERAND (vuse, stmt, i, SSA_OP_VIRTUAL_USES)
|
{
|
{
|
val = &values[SSA_NAME_VERSION (vuse)];
|
val = &values[SSA_NAME_VERSION (vuse)];
|
if (prev_val && prev_val->value != val->value)
|
if (prev_val && prev_val->value != val->value)
|
return NULL;
|
return NULL;
|
prev_val = val;
|
prev_val = val;
|
}
|
}
|
|
|
return val;
|
return val;
|
}
|
}
|
|
|
|
|
/* Propagation statistics. */
|
/* Propagation statistics. */
|
struct prop_stats_d
|
struct prop_stats_d
|
{
|
{
|
long num_const_prop;
|
long num_const_prop;
|
long num_copy_prop;
|
long num_copy_prop;
|
long num_pred_folded;
|
long num_pred_folded;
|
};
|
};
|
|
|
static struct prop_stats_d prop_stats;
|
static struct prop_stats_d prop_stats;
|
|
|
/* Replace USE references in statement STMT with the values stored in
|
/* Replace USE references in statement STMT with the values stored in
|
PROP_VALUE. Return true if at least one reference was replaced. If
|
PROP_VALUE. Return true if at least one reference was replaced. If
|
REPLACED_ADDRESSES_P is given, it will be set to true if an address
|
REPLACED_ADDRESSES_P is given, it will be set to true if an address
|
constant was replaced. */
|
constant was replaced. */
|
|
|
bool
|
bool
|
replace_uses_in (tree stmt, bool *replaced_addresses_p,
|
replace_uses_in (tree stmt, bool *replaced_addresses_p,
|
prop_value_t *prop_value)
|
prop_value_t *prop_value)
|
{
|
{
|
bool replaced = false;
|
bool replaced = false;
|
use_operand_p use;
|
use_operand_p use;
|
ssa_op_iter iter;
|
ssa_op_iter iter;
|
|
|
FOR_EACH_SSA_USE_OPERAND (use, stmt, iter, SSA_OP_USE)
|
FOR_EACH_SSA_USE_OPERAND (use, stmt, iter, SSA_OP_USE)
|
{
|
{
|
tree tuse = USE_FROM_PTR (use);
|
tree tuse = USE_FROM_PTR (use);
|
tree val = prop_value[SSA_NAME_VERSION (tuse)].value;
|
tree val = prop_value[SSA_NAME_VERSION (tuse)].value;
|
|
|
if (val == tuse || val == NULL_TREE)
|
if (val == tuse || val == NULL_TREE)
|
continue;
|
continue;
|
|
|
if (TREE_CODE (stmt) == ASM_EXPR
|
if (TREE_CODE (stmt) == ASM_EXPR
|
&& !may_propagate_copy_into_asm (tuse))
|
&& !may_propagate_copy_into_asm (tuse))
|
continue;
|
continue;
|
|
|
if (!may_propagate_copy (tuse, val))
|
if (!may_propagate_copy (tuse, val))
|
continue;
|
continue;
|
|
|
if (TREE_CODE (val) != SSA_NAME)
|
if (TREE_CODE (val) != SSA_NAME)
|
prop_stats.num_const_prop++;
|
prop_stats.num_const_prop++;
|
else
|
else
|
prop_stats.num_copy_prop++;
|
prop_stats.num_copy_prop++;
|
|
|
propagate_value (use, val);
|
propagate_value (use, val);
|
|
|
replaced = true;
|
replaced = true;
|
if (POINTER_TYPE_P (TREE_TYPE (tuse)) && replaced_addresses_p)
|
if (POINTER_TYPE_P (TREE_TYPE (tuse)) && replaced_addresses_p)
|
*replaced_addresses_p = true;
|
*replaced_addresses_p = true;
|
}
|
}
|
|
|
return replaced;
|
return replaced;
|
}
|
}
|
|
|
|
|
/* Replace the VUSE references in statement STMT with the values
|
/* Replace the VUSE references in statement STMT with the values
|
stored in PROP_VALUE. Return true if a reference was replaced. If
|
stored in PROP_VALUE. Return true if a reference was replaced. If
|
REPLACED_ADDRESSES_P is given, it will be set to true if an address
|
REPLACED_ADDRESSES_P is given, it will be set to true if an address
|
constant was replaced.
|
constant was replaced.
|
|
|
Replacing VUSE operands is slightly more complex than replacing
|
Replacing VUSE operands is slightly more complex than replacing
|
regular USEs. We are only interested in two types of replacements
|
regular USEs. We are only interested in two types of replacements
|
here:
|
here:
|
|
|
1- If the value to be replaced is a constant or an SSA name for a
|
1- If the value to be replaced is a constant or an SSA name for a
|
GIMPLE register, then we are making a copy/constant propagation
|
GIMPLE register, then we are making a copy/constant propagation
|
from a memory store. For instance,
|
from a memory store. For instance,
|
|
|
# a_3 = V_MAY_DEF <a_2>
|
# a_3 = V_MAY_DEF <a_2>
|
a.b = x_1;
|
a.b = x_1;
|
...
|
...
|
# VUSE <a_3>
|
# VUSE <a_3>
|
y_4 = a.b;
|
y_4 = a.b;
|
|
|
This replacement is only possible iff STMT is an assignment
|
This replacement is only possible iff STMT is an assignment
|
whose RHS is identical to the LHS of the statement that created
|
whose RHS is identical to the LHS of the statement that created
|
the VUSE(s) that we are replacing. Otherwise, we may do the
|
the VUSE(s) that we are replacing. Otherwise, we may do the
|
wrong replacement:
|
wrong replacement:
|
|
|
# a_3 = V_MAY_DEF <a_2>
|
# a_3 = V_MAY_DEF <a_2>
|
# b_5 = V_MAY_DEF <b_4>
|
# b_5 = V_MAY_DEF <b_4>
|
*p = 10;
|
*p = 10;
|
...
|
...
|
# VUSE <b_5>
|
# VUSE <b_5>
|
x_8 = b;
|
x_8 = b;
|
|
|
Even though 'b_5' acquires the value '10' during propagation,
|
Even though 'b_5' acquires the value '10' during propagation,
|
there is no way for the propagator to tell whether the
|
there is no way for the propagator to tell whether the
|
replacement is correct in every reached use, because values are
|
replacement is correct in every reached use, because values are
|
computed at definition sites. Therefore, when doing final
|
computed at definition sites. Therefore, when doing final
|
substitution of propagated values, we have to check each use
|
substitution of propagated values, we have to check each use
|
site. Since the RHS of STMT ('b') is different from the LHS of
|
site. Since the RHS of STMT ('b') is different from the LHS of
|
the originating statement ('*p'), we cannot replace 'b' with
|
the originating statement ('*p'), we cannot replace 'b' with
|
'10'.
|
'10'.
|
|
|
Similarly, when merging values from PHI node arguments,
|
Similarly, when merging values from PHI node arguments,
|
propagators need to take care not to merge the same values
|
propagators need to take care not to merge the same values
|
stored in different locations:
|
stored in different locations:
|
|
|
if (...)
|
if (...)
|
# a_3 = V_MAY_DEF <a_2>
|
# a_3 = V_MAY_DEF <a_2>
|
a.b = 3;
|
a.b = 3;
|
else
|
else
|
# a_4 = V_MAY_DEF <a_2>
|
# a_4 = V_MAY_DEF <a_2>
|
a.c = 3;
|
a.c = 3;
|
# a_5 = PHI <a_3, a_4>
|
# a_5 = PHI <a_3, a_4>
|
|
|
It would be wrong to propagate '3' into 'a_5' because that
|
It would be wrong to propagate '3' into 'a_5' because that
|
operation merges two stores to different memory locations.
|
operation merges two stores to different memory locations.
|
|
|
|
|
2- If the value to be replaced is an SSA name for a virtual
|
2- If the value to be replaced is an SSA name for a virtual
|
register, then we simply replace each VUSE operand with its
|
register, then we simply replace each VUSE operand with its
|
value from PROP_VALUE. This is the same replacement done by
|
value from PROP_VALUE. This is the same replacement done by
|
replace_uses_in. */
|
replace_uses_in. */
|
|
|
static bool
|
static bool
|
replace_vuses_in (tree stmt, bool *replaced_addresses_p,
|
replace_vuses_in (tree stmt, bool *replaced_addresses_p,
|
prop_value_t *prop_value)
|
prop_value_t *prop_value)
|
{
|
{
|
bool replaced = false;
|
bool replaced = false;
|
ssa_op_iter iter;
|
ssa_op_iter iter;
|
use_operand_p vuse;
|
use_operand_p vuse;
|
|
|
if (stmt_makes_single_load (stmt))
|
if (stmt_makes_single_load (stmt))
|
{
|
{
|
/* If STMT is an assignment whose RHS is a single memory load,
|
/* If STMT is an assignment whose RHS is a single memory load,
|
see if we are trying to propagate a constant or a GIMPLE
|
see if we are trying to propagate a constant or a GIMPLE
|
register (case #1 above). */
|
register (case #1 above). */
|
prop_value_t *val = get_value_loaded_by (stmt, prop_value);
|
prop_value_t *val = get_value_loaded_by (stmt, prop_value);
|
tree rhs = TREE_OPERAND (stmt, 1);
|
tree rhs = TREE_OPERAND (stmt, 1);
|
|
|
if (val
|
if (val
|
&& val->value
|
&& val->value
|
&& (is_gimple_reg (val->value)
|
&& (is_gimple_reg (val->value)
|
|| is_gimple_min_invariant (val->value))
|
|| is_gimple_min_invariant (val->value))
|
&& simple_cst_equal (rhs, val->mem_ref) == 1)
|
&& simple_cst_equal (rhs, val->mem_ref) == 1)
|
|
|
{
|
{
|
/* If we are replacing a constant address, inform our
|
/* If we are replacing a constant address, inform our
|
caller. */
|
caller. */
|
if (TREE_CODE (val->value) != SSA_NAME
|
if (TREE_CODE (val->value) != SSA_NAME
|
&& POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (stmt, 1)))
|
&& POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (stmt, 1)))
|
&& replaced_addresses_p)
|
&& replaced_addresses_p)
|
*replaced_addresses_p = true;
|
*replaced_addresses_p = true;
|
|
|
/* We can only perform the substitution if the load is done
|
/* We can only perform the substitution if the load is done
|
from the same memory location as the original store.
|
from the same memory location as the original store.
|
Since we already know that there are no intervening
|
Since we already know that there are no intervening
|
stores between DEF_STMT and STMT, we only need to check
|
stores between DEF_STMT and STMT, we only need to check
|
that the RHS of STMT is the same as the memory reference
|
that the RHS of STMT is the same as the memory reference
|
propagated together with the value. */
|
propagated together with the value. */
|
TREE_OPERAND (stmt, 1) = val->value;
|
TREE_OPERAND (stmt, 1) = val->value;
|
|
|
if (TREE_CODE (val->value) != SSA_NAME)
|
if (TREE_CODE (val->value) != SSA_NAME)
|
prop_stats.num_const_prop++;
|
prop_stats.num_const_prop++;
|
else
|
else
|
prop_stats.num_copy_prop++;
|
prop_stats.num_copy_prop++;
|
|
|
/* Since we have replaced the whole RHS of STMT, there
|
/* Since we have replaced the whole RHS of STMT, there
|
is no point in checking the other VUSEs, as they will
|
is no point in checking the other VUSEs, as they will
|
all have the same value. */
|
all have the same value. */
|
return true;
|
return true;
|
}
|
}
|
}
|
}
|
|
|
/* Otherwise, the values for every VUSE operand must be other
|
/* Otherwise, the values for every VUSE operand must be other
|
SSA_NAMEs that can be propagated into STMT. */
|
SSA_NAMEs that can be propagated into STMT. */
|
FOR_EACH_SSA_USE_OPERAND (vuse, stmt, iter, SSA_OP_VIRTUAL_USES)
|
FOR_EACH_SSA_USE_OPERAND (vuse, stmt, iter, SSA_OP_VIRTUAL_USES)
|
{
|
{
|
tree var = USE_FROM_PTR (vuse);
|
tree var = USE_FROM_PTR (vuse);
|
tree val = prop_value[SSA_NAME_VERSION (var)].value;
|
tree val = prop_value[SSA_NAME_VERSION (var)].value;
|
|
|
if (val == NULL_TREE || var == val)
|
if (val == NULL_TREE || var == val)
|
continue;
|
continue;
|
|
|
/* Constants and copies propagated between real and virtual
|
/* Constants and copies propagated between real and virtual
|
operands are only possible in the cases handled above. They
|
operands are only possible in the cases handled above. They
|
should be ignored in any other context. */
|
should be ignored in any other context. */
|
if (is_gimple_min_invariant (val) || is_gimple_reg (val))
|
if (is_gimple_min_invariant (val) || is_gimple_reg (val))
|
continue;
|
continue;
|
|
|
propagate_value (vuse, val);
|
propagate_value (vuse, val);
|
prop_stats.num_copy_prop++;
|
prop_stats.num_copy_prop++;
|
replaced = true;
|
replaced = true;
|
}
|
}
|
|
|
return replaced;
|
return replaced;
|
}
|
}
|
|
|
|
|
/* Replace propagated values into all the arguments for PHI using the
|
/* Replace propagated values into all the arguments for PHI using the
|
values from PROP_VALUE. */
|
values from PROP_VALUE. */
|
|
|
static void
|
static void
|
replace_phi_args_in (tree phi, prop_value_t *prop_value)
|
replace_phi_args_in (tree phi, prop_value_t *prop_value)
|
{
|
{
|
int i;
|
int i;
|
bool replaced = false;
|
bool replaced = false;
|
tree prev_phi = NULL;
|
tree prev_phi = NULL;
|
|
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
prev_phi = unshare_expr (phi);
|
prev_phi = unshare_expr (phi);
|
|
|
for (i = 0; i < PHI_NUM_ARGS (phi); i++)
|
for (i = 0; i < PHI_NUM_ARGS (phi); i++)
|
{
|
{
|
tree arg = PHI_ARG_DEF (phi, i);
|
tree arg = PHI_ARG_DEF (phi, i);
|
|
|
if (TREE_CODE (arg) == SSA_NAME)
|
if (TREE_CODE (arg) == SSA_NAME)
|
{
|
{
|
tree val = prop_value[SSA_NAME_VERSION (arg)].value;
|
tree val = prop_value[SSA_NAME_VERSION (arg)].value;
|
|
|
if (val && val != arg && may_propagate_copy (arg, val))
|
if (val && val != arg && may_propagate_copy (arg, val))
|
{
|
{
|
if (TREE_CODE (val) != SSA_NAME)
|
if (TREE_CODE (val) != SSA_NAME)
|
prop_stats.num_const_prop++;
|
prop_stats.num_const_prop++;
|
else
|
else
|
prop_stats.num_copy_prop++;
|
prop_stats.num_copy_prop++;
|
|
|
propagate_value (PHI_ARG_DEF_PTR (phi, i), val);
|
propagate_value (PHI_ARG_DEF_PTR (phi, i), val);
|
replaced = true;
|
replaced = true;
|
|
|
/* If we propagated a copy and this argument flows
|
/* If we propagated a copy and this argument flows
|
through an abnormal edge, update the replacement
|
through an abnormal edge, update the replacement
|
accordingly. */
|
accordingly. */
|
if (TREE_CODE (val) == SSA_NAME
|
if (TREE_CODE (val) == SSA_NAME
|
&& PHI_ARG_EDGE (phi, i)->flags & EDGE_ABNORMAL)
|
&& PHI_ARG_EDGE (phi, i)->flags & EDGE_ABNORMAL)
|
SSA_NAME_OCCURS_IN_ABNORMAL_PHI (val) = 1;
|
SSA_NAME_OCCURS_IN_ABNORMAL_PHI (val) = 1;
|
}
|
}
|
}
|
}
|
}
|
}
|
|
|
if (replaced && dump_file && (dump_flags & TDF_DETAILS))
|
if (replaced && dump_file && (dump_flags & TDF_DETAILS))
|
{
|
{
|
fprintf (dump_file, "Folded PHI node: ");
|
fprintf (dump_file, "Folded PHI node: ");
|
print_generic_stmt (dump_file, prev_phi, TDF_SLIM);
|
print_generic_stmt (dump_file, prev_phi, TDF_SLIM);
|
fprintf (dump_file, " into: ");
|
fprintf (dump_file, " into: ");
|
print_generic_stmt (dump_file, phi, TDF_SLIM);
|
print_generic_stmt (dump_file, phi, TDF_SLIM);
|
fprintf (dump_file, "\n");
|
fprintf (dump_file, "\n");
|
}
|
}
|
}
|
}
|
|
|
|
|
/* If STMT has a predicate whose value can be computed using the value
|
/* If STMT has a predicate whose value can be computed using the value
|
range information computed by VRP, compute its value and return true.
|
range information computed by VRP, compute its value and return true.
|
Otherwise, return false. */
|
Otherwise, return false. */
|
|
|
static bool
|
static bool
|
fold_predicate_in (tree stmt)
|
fold_predicate_in (tree stmt)
|
{
|
{
|
tree *pred_p = NULL;
|
tree *pred_p = NULL;
|
bool modify_expr_p = false;
|
bool modify_expr_p = false;
|
tree val;
|
tree val;
|
|
|
if (TREE_CODE (stmt) == MODIFY_EXPR
|
if (TREE_CODE (stmt) == MODIFY_EXPR
|
&& COMPARISON_CLASS_P (TREE_OPERAND (stmt, 1)))
|
&& COMPARISON_CLASS_P (TREE_OPERAND (stmt, 1)))
|
{
|
{
|
modify_expr_p = true;
|
modify_expr_p = true;
|
pred_p = &TREE_OPERAND (stmt, 1);
|
pred_p = &TREE_OPERAND (stmt, 1);
|
}
|
}
|
else if (TREE_CODE (stmt) == COND_EXPR)
|
else if (TREE_CODE (stmt) == COND_EXPR)
|
pred_p = &COND_EXPR_COND (stmt);
|
pred_p = &COND_EXPR_COND (stmt);
|
else
|
else
|
return false;
|
return false;
|
|
|
val = vrp_evaluate_conditional (*pred_p, stmt);
|
val = vrp_evaluate_conditional (*pred_p, stmt);
|
if (val)
|
if (val)
|
{
|
{
|
if (modify_expr_p)
|
if (modify_expr_p)
|
val = fold_convert (TREE_TYPE (*pred_p), val);
|
val = fold_convert (TREE_TYPE (*pred_p), val);
|
|
|
if (dump_file)
|
if (dump_file)
|
{
|
{
|
fprintf (dump_file, "Folding predicate ");
|
fprintf (dump_file, "Folding predicate ");
|
print_generic_expr (dump_file, *pred_p, 0);
|
print_generic_expr (dump_file, *pred_p, 0);
|
fprintf (dump_file, " to ");
|
fprintf (dump_file, " to ");
|
print_generic_expr (dump_file, val, 0);
|
print_generic_expr (dump_file, val, 0);
|
fprintf (dump_file, "\n");
|
fprintf (dump_file, "\n");
|
}
|
}
|
|
|
prop_stats.num_pred_folded++;
|
prop_stats.num_pred_folded++;
|
*pred_p = val;
|
*pred_p = val;
|
return true;
|
return true;
|
}
|
}
|
|
|
return false;
|
return false;
|
}
|
}
|
|
|
|
|
/* Perform final substitution and folding of propagated values.
|
/* Perform final substitution and folding of propagated values.
|
|
|
PROP_VALUE[I] contains the single value that should be substituted
|
PROP_VALUE[I] contains the single value that should be substituted
|
at every use of SSA name N_I. If PROP_VALUE is NULL, no values are
|
at every use of SSA name N_I. If PROP_VALUE is NULL, no values are
|
substituted.
|
substituted.
|
|
|
If USE_RANGES_P is true, statements that contain predicate
|
If USE_RANGES_P is true, statements that contain predicate
|
expressions are evaluated with a call to vrp_evaluate_conditional.
|
expressions are evaluated with a call to vrp_evaluate_conditional.
|
This will only give meaningful results when called from tree-vrp.c
|
This will only give meaningful results when called from tree-vrp.c
|
(the information used by vrp_evaluate_conditional is built by the
|
(the information used by vrp_evaluate_conditional is built by the
|
VRP pass). */
|
VRP pass). */
|
|
|
void
|
void
|
substitute_and_fold (prop_value_t *prop_value, bool use_ranges_p)
|
substitute_and_fold (prop_value_t *prop_value, bool use_ranges_p)
|
{
|
{
|
basic_block bb;
|
basic_block bb;
|
|
|
if (prop_value == NULL && !use_ranges_p)
|
if (prop_value == NULL && !use_ranges_p)
|
return;
|
return;
|
|
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
fprintf (dump_file, "\nSubstituing values and folding statements\n\n");
|
fprintf (dump_file, "\nSubstituing values and folding statements\n\n");
|
|
|
memset (&prop_stats, 0, sizeof (prop_stats));
|
memset (&prop_stats, 0, sizeof (prop_stats));
|
|
|
/* Substitute values in every statement of every basic block. */
|
/* Substitute values in every statement of every basic block. */
|
FOR_EACH_BB (bb)
|
FOR_EACH_BB (bb)
|
{
|
{
|
block_stmt_iterator i;
|
block_stmt_iterator i;
|
tree phi;
|
tree phi;
|
|
|
/* Propagate known values into PHI nodes. */
|
/* Propagate known values into PHI nodes. */
|
if (prop_value)
|
if (prop_value)
|
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
|
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
|
replace_phi_args_in (phi, prop_value);
|
replace_phi_args_in (phi, prop_value);
|
|
|
for (i = bsi_start (bb); !bsi_end_p (i); bsi_next (&i))
|
for (i = bsi_start (bb); !bsi_end_p (i); bsi_next (&i))
|
{
|
{
|
bool replaced_address, did_replace;
|
bool replaced_address, did_replace;
|
tree prev_stmt = NULL;
|
tree prev_stmt = NULL;
|
tree stmt = bsi_stmt (i);
|
tree stmt = bsi_stmt (i);
|
|
|
/* Ignore ASSERT_EXPRs. They are used by VRP to generate
|
/* Ignore ASSERT_EXPRs. They are used by VRP to generate
|
range information for names and they are discarded
|
range information for names and they are discarded
|
afterwards. */
|
afterwards. */
|
if (TREE_CODE (stmt) == MODIFY_EXPR
|
if (TREE_CODE (stmt) == MODIFY_EXPR
|
&& TREE_CODE (TREE_OPERAND (stmt, 1)) == ASSERT_EXPR)
|
&& TREE_CODE (TREE_OPERAND (stmt, 1)) == ASSERT_EXPR)
|
continue;
|
continue;
|
|
|
/* Replace the statement with its folded version and mark it
|
/* Replace the statement with its folded version and mark it
|
folded. */
|
folded. */
|
did_replace = false;
|
did_replace = false;
|
replaced_address = false;
|
replaced_address = false;
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
prev_stmt = unshare_expr (stmt);
|
prev_stmt = unshare_expr (stmt);
|
|
|
/* If we have range information, see if we can fold
|
/* If we have range information, see if we can fold
|
predicate expressions. */
|
predicate expressions. */
|
if (use_ranges_p)
|
if (use_ranges_p)
|
did_replace = fold_predicate_in (stmt);
|
did_replace = fold_predicate_in (stmt);
|
|
|
if (prop_value)
|
if (prop_value)
|
{
|
{
|
/* Only replace real uses if we couldn't fold the
|
/* Only replace real uses if we couldn't fold the
|
statement using value range information (value range
|
statement using value range information (value range
|
information is not collected on virtuals, so we only
|
information is not collected on virtuals, so we only
|
need to check this for real uses). */
|
need to check this for real uses). */
|
if (!did_replace)
|
if (!did_replace)
|
did_replace |= replace_uses_in (stmt, &replaced_address,
|
did_replace |= replace_uses_in (stmt, &replaced_address,
|
prop_value);
|
prop_value);
|
|
|
did_replace |= replace_vuses_in (stmt, &replaced_address,
|
did_replace |= replace_vuses_in (stmt, &replaced_address,
|
prop_value);
|
prop_value);
|
}
|
}
|
|
|
/* If we made a replacement, fold and cleanup the statement. */
|
/* If we made a replacement, fold and cleanup the statement. */
|
if (did_replace)
|
if (did_replace)
|
{
|
{
|
tree old_stmt = stmt;
|
tree old_stmt = stmt;
|
tree rhs;
|
tree rhs;
|
|
|
fold_stmt (bsi_stmt_ptr (i));
|
fold_stmt (bsi_stmt_ptr (i));
|
stmt = bsi_stmt (i);
|
stmt = bsi_stmt (i);
|
|
|
/* If we folded a builtin function, we'll likely
|
/* If we folded a builtin function, we'll likely
|
need to rename VDEFs. */
|
need to rename VDEFs. */
|
mark_new_vars_to_rename (stmt);
|
mark_new_vars_to_rename (stmt);
|
|
|
/* If we cleaned up EH information from the statement,
|
/* If we cleaned up EH information from the statement,
|
remove EH edges. */
|
remove EH edges. */
|
if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt))
|
if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt))
|
tree_purge_dead_eh_edges (bb);
|
tree_purge_dead_eh_edges (bb);
|
|
|
rhs = get_rhs (stmt);
|
rhs = get_rhs (stmt);
|
if (TREE_CODE (rhs) == ADDR_EXPR)
|
if (TREE_CODE (rhs) == ADDR_EXPR)
|
recompute_tree_invariant_for_addr_expr (rhs);
|
recompute_tree_invariant_for_addr_expr (rhs);
|
|
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
{
|
{
|
fprintf (dump_file, "Folded statement: ");
|
fprintf (dump_file, "Folded statement: ");
|
print_generic_stmt (dump_file, prev_stmt, TDF_SLIM);
|
print_generic_stmt (dump_file, prev_stmt, TDF_SLIM);
|
fprintf (dump_file, " into: ");
|
fprintf (dump_file, " into: ");
|
print_generic_stmt (dump_file, stmt, TDF_SLIM);
|
print_generic_stmt (dump_file, stmt, TDF_SLIM);
|
fprintf (dump_file, "\n");
|
fprintf (dump_file, "\n");
|
}
|
}
|
}
|
}
|
|
|
/* Some statements may be simplified using ranges. For
|
/* Some statements may be simplified using ranges. For
|
example, division may be replaced by shifts, modulo
|
example, division may be replaced by shifts, modulo
|
replaced with bitwise and, etc. Do this after
|
replaced with bitwise and, etc. Do this after
|
substituting constants, folding, etc so that we're
|
substituting constants, folding, etc so that we're
|
presented with a fully propagated, canonicalized
|
presented with a fully propagated, canonicalized
|
statement. */
|
statement. */
|
if (use_ranges_p)
|
if (use_ranges_p)
|
simplify_stmt_using_ranges (stmt);
|
simplify_stmt_using_ranges (stmt);
|
|
|
}
|
}
|
}
|
}
|
|
|
if (dump_file && (dump_flags & TDF_STATS))
|
if (dump_file && (dump_flags & TDF_STATS))
|
{
|
{
|
fprintf (dump_file, "Constants propagated: %6ld\n",
|
fprintf (dump_file, "Constants propagated: %6ld\n",
|
prop_stats.num_const_prop);
|
prop_stats.num_const_prop);
|
fprintf (dump_file, "Copies propagated: %6ld\n",
|
fprintf (dump_file, "Copies propagated: %6ld\n",
|
prop_stats.num_copy_prop);
|
prop_stats.num_copy_prop);
|
fprintf (dump_file, "Predicates folded: %6ld\n",
|
fprintf (dump_file, "Predicates folded: %6ld\n",
|
prop_stats.num_pred_folded);
|
prop_stats.num_pred_folded);
|
}
|
}
|
}
|
}
|
|
|
#include "gt-tree-ssa-propagate.h"
|
#include "gt-tree-ssa-propagate.h"
|
|
|
