/* Code sinking for trees
|
/* Code sinking for trees
|
Copyright (C) 2001, 2002, 2003, 2004, 2007 Free Software Foundation, Inc.
|
Copyright (C) 2001, 2002, 2003, 2004, 2007 Free Software Foundation, Inc.
|
Contributed by Daniel Berlin <dan@dberlin.org>
|
Contributed by Daniel Berlin <dan@dberlin.org>
|
|
|
This file is part of GCC.
|
This file is part of GCC.
|
|
|
GCC is free software; you can redistribute it and/or modify
|
GCC is free software; you can redistribute it and/or modify
|
it under the terms of the GNU General Public License as published by
|
it under the terms of the GNU General Public License as published by
|
the Free Software Foundation; either version 3, or (at your option)
|
the Free Software Foundation; either version 3, or (at your option)
|
any later version.
|
any later version.
|
|
|
GCC is distributed in the hope that it will be useful,
|
GCC is distributed in the hope that it will be useful,
|
but WITHOUT ANY WARRANTY; without even the implied warranty of
|
but WITHOUT ANY WARRANTY; without even the implied warranty of
|
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
GNU General Public License for more details.
|
GNU General Public License 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 "ggc.h"
|
#include "ggc.h"
|
#include "tree.h"
|
#include "tree.h"
|
#include "basic-block.h"
|
#include "basic-block.h"
|
#include "diagnostic.h"
|
#include "diagnostic.h"
|
#include "tree-inline.h"
|
#include "tree-inline.h"
|
#include "tree-flow.h"
|
#include "tree-flow.h"
|
#include "tree-gimple.h"
|
#include "tree-gimple.h"
|
#include "tree-dump.h"
|
#include "tree-dump.h"
|
#include "timevar.h"
|
#include "timevar.h"
|
#include "fibheap.h"
|
#include "fibheap.h"
|
#include "hashtab.h"
|
#include "hashtab.h"
|
#include "tree-iterator.h"
|
#include "tree-iterator.h"
|
#include "real.h"
|
#include "real.h"
|
#include "alloc-pool.h"
|
#include "alloc-pool.h"
|
#include "tree-pass.h"
|
#include "tree-pass.h"
|
#include "flags.h"
|
#include "flags.h"
|
#include "bitmap.h"
|
#include "bitmap.h"
|
#include "langhooks.h"
|
#include "langhooks.h"
|
#include "cfgloop.h"
|
#include "cfgloop.h"
|
|
|
/* TODO:
|
/* TODO:
|
1. Sinking store only using scalar promotion (IE without moving the RHS):
|
1. Sinking store only using scalar promotion (IE without moving the RHS):
|
|
|
*q = p;
|
*q = p;
|
p = p + 1;
|
p = p + 1;
|
if (something)
|
if (something)
|
*q = <not p>;
|
*q = <not p>;
|
else
|
else
|
y = *q;
|
y = *q;
|
|
|
|
|
should become
|
should become
|
sinktemp = p;
|
sinktemp = p;
|
p = p + 1;
|
p = p + 1;
|
if (something)
|
if (something)
|
*q = <not p>;
|
*q = <not p>;
|
else
|
else
|
{
|
{
|
*q = sinktemp;
|
*q = sinktemp;
|
y = *q
|
y = *q
|
}
|
}
|
Store copy propagation will take care of the store elimination above.
|
Store copy propagation will take care of the store elimination above.
|
|
|
|
|
2. Sinking using Partial Dead Code Elimination. */
|
2. Sinking using Partial Dead Code Elimination. */
|
|
|
|
|
static struct
|
static struct
|
{
|
{
|
/* The number of statements sunk down the flowgraph by code sinking. */
|
/* The number of statements sunk down the flowgraph by code sinking. */
|
int sunk;
|
int sunk;
|
|
|
} sink_stats;
|
} sink_stats;
|
|
|
|
|
/* Given a PHI, and one of its arguments (DEF), find the edge for
|
/* Given a PHI, and one of its arguments (DEF), find the edge for
|
that argument and return it. If the argument occurs twice in the PHI node,
|
that argument and return it. If the argument occurs twice in the PHI node,
|
we return NULL. */
|
we return NULL. */
|
|
|
static basic_block
|
static basic_block
|
find_bb_for_arg (tree phi, tree def)
|
find_bb_for_arg (tree phi, tree def)
|
{
|
{
|
int i;
|
int i;
|
bool foundone = false;
|
bool foundone = false;
|
basic_block result = NULL;
|
basic_block result = NULL;
|
for (i = 0; i < PHI_NUM_ARGS (phi); i++)
|
for (i = 0; i < PHI_NUM_ARGS (phi); i++)
|
if (PHI_ARG_DEF (phi, i) == def)
|
if (PHI_ARG_DEF (phi, i) == def)
|
{
|
{
|
if (foundone)
|
if (foundone)
|
return NULL;
|
return NULL;
|
foundone = true;
|
foundone = true;
|
result = PHI_ARG_EDGE (phi, i)->src;
|
result = PHI_ARG_EDGE (phi, i)->src;
|
}
|
}
|
return result;
|
return result;
|
}
|
}
|
|
|
/* When the first immediate use is in a statement, then return true if all
|
/* When the first immediate use is in a statement, then return true if all
|
immediate uses in IMM are in the same statement.
|
immediate uses in IMM are in the same statement.
|
We could also do the case where the first immediate use is in a phi node,
|
We could also do the case where the first immediate use is in a phi node,
|
and all the other uses are in phis in the same basic block, but this
|
and all the other uses are in phis in the same basic block, but this
|
requires some expensive checking later (you have to make sure no def/vdef
|
requires some expensive checking later (you have to make sure no def/vdef
|
in the statement occurs for multiple edges in the various phi nodes it's
|
in the statement occurs for multiple edges in the various phi nodes it's
|
used in, so that you only have one place you can sink it to. */
|
used in, so that you only have one place you can sink it to. */
|
|
|
static bool
|
static bool
|
all_immediate_uses_same_place (tree stmt)
|
all_immediate_uses_same_place (tree stmt)
|
{
|
{
|
tree firstuse = NULL_TREE;
|
tree firstuse = NULL_TREE;
|
ssa_op_iter op_iter;
|
ssa_op_iter op_iter;
|
imm_use_iterator imm_iter;
|
imm_use_iterator imm_iter;
|
use_operand_p use_p;
|
use_operand_p use_p;
|
tree var;
|
tree var;
|
|
|
FOR_EACH_SSA_TREE_OPERAND (var, stmt, op_iter, SSA_OP_ALL_DEFS)
|
FOR_EACH_SSA_TREE_OPERAND (var, stmt, op_iter, SSA_OP_ALL_DEFS)
|
{
|
{
|
FOR_EACH_IMM_USE_FAST (use_p, imm_iter, var)
|
FOR_EACH_IMM_USE_FAST (use_p, imm_iter, var)
|
{
|
{
|
if (firstuse == NULL_TREE)
|
if (firstuse == NULL_TREE)
|
firstuse = USE_STMT (use_p);
|
firstuse = USE_STMT (use_p);
|
else
|
else
|
if (firstuse != USE_STMT (use_p))
|
if (firstuse != USE_STMT (use_p))
|
return false;
|
return false;
|
}
|
}
|
}
|
}
|
|
|
return true;
|
return true;
|
}
|
}
|
|
|
/* Some global stores don't necessarily have V_MAY_DEF's of global variables,
|
/* Some global stores don't necessarily have V_MAY_DEF's of global variables,
|
but we still must avoid moving them around. */
|
but we still must avoid moving them around. */
|
|
|
bool
|
bool
|
is_hidden_global_store (tree stmt)
|
is_hidden_global_store (tree stmt)
|
{
|
{
|
/* Check virtual definitions. If we get here, the only virtual
|
/* Check virtual definitions. If we get here, the only virtual
|
definitions we should see are those generated by assignment
|
definitions we should see are those generated by assignment
|
statements. */
|
statements. */
|
if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS))
|
if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS))
|
{
|
{
|
tree lhs;
|
tree lhs;
|
|
|
gcc_assert (TREE_CODE (stmt) == MODIFY_EXPR);
|
gcc_assert (TREE_CODE (stmt) == MODIFY_EXPR);
|
|
|
/* Note that we must not check the individual virtual operands
|
/* Note that we must not check the individual virtual operands
|
here. In particular, if this is an aliased store, we could
|
here. In particular, if this is an aliased store, we could
|
end up with something like the following (SSA notation
|
end up with something like the following (SSA notation
|
redacted for brevity):
|
redacted for brevity):
|
|
|
foo (int *p, int i)
|
foo (int *p, int i)
|
{
|
{
|
int x;
|
int x;
|
p_1 = (i_2 > 3) ? &x : p;
|
p_1 = (i_2 > 3) ? &x : p;
|
|
|
# x_4 = V_MAY_DEF <x_3>
|
# x_4 = V_MAY_DEF <x_3>
|
*p_1 = 5;
|
*p_1 = 5;
|
|
|
return 2;
|
return 2;
|
}
|
}
|
|
|
Notice that the store to '*p_1' should be preserved, if we
|
Notice that the store to '*p_1' should be preserved, if we
|
were to check the virtual definitions in that store, we would
|
were to check the virtual definitions in that store, we would
|
not mark it needed. This is because 'x' is not a global
|
not mark it needed. This is because 'x' is not a global
|
variable.
|
variable.
|
|
|
Therefore, we check the base address of the LHS. If the
|
Therefore, we check the base address of the LHS. If the
|
address is a pointer, we check if its name tag or symbol tag is
|
address is a pointer, we check if its name tag or symbol tag is
|
a global variable. Otherwise, we check if the base variable
|
a global variable. Otherwise, we check if the base variable
|
is a global. */
|
is a global. */
|
lhs = TREE_OPERAND (stmt, 0);
|
lhs = TREE_OPERAND (stmt, 0);
|
if (REFERENCE_CLASS_P (lhs))
|
if (REFERENCE_CLASS_P (lhs))
|
lhs = get_base_address (lhs);
|
lhs = get_base_address (lhs);
|
|
|
if (lhs == NULL_TREE)
|
if (lhs == NULL_TREE)
|
{
|
{
|
/* If LHS is NULL, it means that we couldn't get the base
|
/* If LHS is NULL, it means that we couldn't get the base
|
address of the reference. In which case, we should not
|
address of the reference. In which case, we should not
|
move this store. */
|
move this store. */
|
return true;
|
return true;
|
}
|
}
|
else if (DECL_P (lhs))
|
else if (DECL_P (lhs))
|
{
|
{
|
/* If the store is to a global symbol, we need to keep it. */
|
/* If the store is to a global symbol, we need to keep it. */
|
if (is_global_var (lhs))
|
if (is_global_var (lhs))
|
return true;
|
return true;
|
|
|
}
|
}
|
else if (INDIRECT_REF_P (lhs))
|
else if (INDIRECT_REF_P (lhs))
|
{
|
{
|
tree ptr = TREE_OPERAND (lhs, 0);
|
tree ptr = TREE_OPERAND (lhs, 0);
|
struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
|
struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
|
tree nmt = (pi) ? pi->name_mem_tag : NULL_TREE;
|
tree nmt = (pi) ? pi->name_mem_tag : NULL_TREE;
|
tree smt = var_ann (SSA_NAME_VAR (ptr))->symbol_mem_tag;
|
tree smt = var_ann (SSA_NAME_VAR (ptr))->symbol_mem_tag;
|
|
|
/* If either the name tag or the symbol tag for PTR is a
|
/* If either the name tag or the symbol tag for PTR is a
|
global variable, then the store is necessary. */
|
global variable, then the store is necessary. */
|
if ((nmt && is_global_var (nmt))
|
if ((nmt && is_global_var (nmt))
|
|| (smt && is_global_var (smt)))
|
|| (smt && is_global_var (smt)))
|
{
|
{
|
return true;
|
return true;
|
}
|
}
|
}
|
}
|
else
|
else
|
gcc_unreachable ();
|
gcc_unreachable ();
|
}
|
}
|
return false;
|
return false;
|
}
|
}
|
|
|
/* Find the nearest common dominator of all of the immediate uses in IMM. */
|
/* Find the nearest common dominator of all of the immediate uses in IMM. */
|
|
|
static basic_block
|
static basic_block
|
nearest_common_dominator_of_uses (tree stmt)
|
nearest_common_dominator_of_uses (tree stmt)
|
{
|
{
|
bitmap blocks = BITMAP_ALLOC (NULL);
|
bitmap blocks = BITMAP_ALLOC (NULL);
|
basic_block commondom;
|
basic_block commondom;
|
unsigned int j;
|
unsigned int j;
|
bitmap_iterator bi;
|
bitmap_iterator bi;
|
ssa_op_iter op_iter;
|
ssa_op_iter op_iter;
|
imm_use_iterator imm_iter;
|
imm_use_iterator imm_iter;
|
use_operand_p use_p;
|
use_operand_p use_p;
|
tree var;
|
tree var;
|
|
|
bitmap_clear (blocks);
|
bitmap_clear (blocks);
|
FOR_EACH_SSA_TREE_OPERAND (var, stmt, op_iter, SSA_OP_ALL_DEFS)
|
FOR_EACH_SSA_TREE_OPERAND (var, stmt, op_iter, SSA_OP_ALL_DEFS)
|
{
|
{
|
FOR_EACH_IMM_USE_FAST (use_p, imm_iter, var)
|
FOR_EACH_IMM_USE_FAST (use_p, imm_iter, var)
|
{
|
{
|
tree usestmt = USE_STMT (use_p);
|
tree usestmt = USE_STMT (use_p);
|
basic_block useblock;
|
basic_block useblock;
|
|
|
if (TREE_CODE (usestmt) == PHI_NODE)
|
if (TREE_CODE (usestmt) == PHI_NODE)
|
{
|
{
|
int idx = PHI_ARG_INDEX_FROM_USE (use_p);
|
int idx = PHI_ARG_INDEX_FROM_USE (use_p);
|
|
|
useblock = PHI_ARG_EDGE (usestmt, idx)->src;
|
useblock = PHI_ARG_EDGE (usestmt, idx)->src;
|
}
|
}
|
else
|
else
|
{
|
{
|
useblock = bb_for_stmt (usestmt);
|
useblock = bb_for_stmt (usestmt);
|
}
|
}
|
|
|
/* Short circuit. Nothing dominates the entry block. */
|
/* Short circuit. Nothing dominates the entry block. */
|
if (useblock == ENTRY_BLOCK_PTR)
|
if (useblock == ENTRY_BLOCK_PTR)
|
{
|
{
|
BITMAP_FREE (blocks);
|
BITMAP_FREE (blocks);
|
return NULL;
|
return NULL;
|
}
|
}
|
bitmap_set_bit (blocks, useblock->index);
|
bitmap_set_bit (blocks, useblock->index);
|
}
|
}
|
}
|
}
|
commondom = BASIC_BLOCK (bitmap_first_set_bit (blocks));
|
commondom = BASIC_BLOCK (bitmap_first_set_bit (blocks));
|
EXECUTE_IF_SET_IN_BITMAP (blocks, 0, j, bi)
|
EXECUTE_IF_SET_IN_BITMAP (blocks, 0, j, bi)
|
commondom = nearest_common_dominator (CDI_DOMINATORS, commondom,
|
commondom = nearest_common_dominator (CDI_DOMINATORS, commondom,
|
BASIC_BLOCK (j));
|
BASIC_BLOCK (j));
|
BITMAP_FREE (blocks);
|
BITMAP_FREE (blocks);
|
return commondom;
|
return commondom;
|
}
|
}
|
|
|
/* Given a statement (STMT) and the basic block it is currently in (FROMBB),
|
/* Given a statement (STMT) and the basic block it is currently in (FROMBB),
|
determine the location to sink the statement to, if any.
|
determine the location to sink the statement to, if any.
|
Return the basic block to sink it to, or NULL if we should not sink
|
Return the basic block to sink it to, or NULL if we should not sink
|
it. */
|
it. */
|
|
|
static tree
|
static tree
|
statement_sink_location (tree stmt, basic_block frombb)
|
statement_sink_location (tree stmt, basic_block frombb)
|
{
|
{
|
tree use, def;
|
tree use, def;
|
use_operand_p one_use = NULL_USE_OPERAND_P;
|
use_operand_p one_use = NULL_USE_OPERAND_P;
|
basic_block sinkbb;
|
basic_block sinkbb;
|
use_operand_p use_p;
|
use_operand_p use_p;
|
def_operand_p def_p;
|
def_operand_p def_p;
|
ssa_op_iter iter;
|
ssa_op_iter iter;
|
stmt_ann_t ann;
|
stmt_ann_t ann;
|
tree rhs;
|
tree rhs;
|
imm_use_iterator imm_iter;
|
imm_use_iterator imm_iter;
|
|
|
FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
|
FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
|
{
|
{
|
FOR_EACH_IMM_USE_FAST (one_use, imm_iter, def)
|
FOR_EACH_IMM_USE_FAST (one_use, imm_iter, def)
|
{
|
{
|
break;
|
break;
|
}
|
}
|
if (one_use != NULL_USE_OPERAND_P)
|
if (one_use != NULL_USE_OPERAND_P)
|
break;
|
break;
|
}
|
}
|
|
|
/* Return if there are no immediate uses of this stmt. */
|
/* Return if there are no immediate uses of this stmt. */
|
if (one_use == NULL_USE_OPERAND_P)
|
if (one_use == NULL_USE_OPERAND_P)
|
return NULL;
|
return NULL;
|
|
|
if (TREE_CODE (stmt) != MODIFY_EXPR)
|
if (TREE_CODE (stmt) != MODIFY_EXPR)
|
return NULL;
|
return NULL;
|
rhs = TREE_OPERAND (stmt, 1);
|
rhs = TREE_OPERAND (stmt, 1);
|
|
|
/* There are a few classes of things we can't or don't move, some because we
|
/* There are a few classes of things we can't or don't move, some because we
|
don't have code to handle it, some because it's not profitable and some
|
don't have code to handle it, some because it's not profitable and some
|
because it's not legal.
|
because it's not legal.
|
|
|
We can't sink things that may be global stores, at least not without
|
We can't sink things that may be global stores, at least not without
|
calculating a lot more information, because we may cause it to no longer
|
calculating a lot more information, because we may cause it to no longer
|
be seen by an external routine that needs it depending on where it gets
|
be seen by an external routine that needs it depending on where it gets
|
moved to.
|
moved to.
|
|
|
We don't want to sink loads from memory.
|
We don't want to sink loads from memory.
|
|
|
We can't sink statements that end basic blocks without splitting the
|
We can't sink statements that end basic blocks without splitting the
|
incoming edge for the sink location to place it there.
|
incoming edge for the sink location to place it there.
|
|
|
We can't sink statements that have volatile operands.
|
We can't sink statements that have volatile operands.
|
|
|
We don't want to sink dead code, so anything with 0 immediate uses is not
|
We don't want to sink dead code, so anything with 0 immediate uses is not
|
sunk.
|
sunk.
|
|
|
*/
|
*/
|
ann = stmt_ann (stmt);
|
ann = stmt_ann (stmt);
|
if (stmt_ends_bb_p (stmt)
|
if (stmt_ends_bb_p (stmt)
|
|| TREE_SIDE_EFFECTS (rhs)
|
|| TREE_SIDE_EFFECTS (rhs)
|
|| TREE_CODE (rhs) == EXC_PTR_EXPR
|
|| TREE_CODE (rhs) == EXC_PTR_EXPR
|
|| TREE_CODE (rhs) == FILTER_EXPR
|
|| TREE_CODE (rhs) == FILTER_EXPR
|
|| is_hidden_global_store (stmt)
|
|| is_hidden_global_store (stmt)
|
|| ann->has_volatile_ops
|
|| ann->has_volatile_ops
|
|| !ZERO_SSA_OPERANDS (stmt, SSA_OP_VUSE))
|
|| !ZERO_SSA_OPERANDS (stmt, SSA_OP_VUSE))
|
return NULL;
|
return NULL;
|
|
|
FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS)
|
FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS)
|
{
|
{
|
tree def = DEF_FROM_PTR (def_p);
|
tree def = DEF_FROM_PTR (def_p);
|
if (is_global_var (SSA_NAME_VAR (def))
|
if (is_global_var (SSA_NAME_VAR (def))
|
|| SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def))
|
|| SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def))
|
return NULL;
|
return NULL;
|
}
|
}
|
|
|
FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
|
FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
|
{
|
{
|
tree use = USE_FROM_PTR (use_p);
|
tree use = USE_FROM_PTR (use_p);
|
if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (use))
|
if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (use))
|
return NULL;
|
return NULL;
|
}
|
}
|
|
|
/* If all the immediate uses are not in the same place, find the nearest
|
/* If all the immediate uses are not in the same place, find the nearest
|
common dominator of all the immediate uses. For PHI nodes, we have to
|
common dominator of all the immediate uses. For PHI nodes, we have to
|
find the nearest common dominator of all of the predecessor blocks, since
|
find the nearest common dominator of all of the predecessor blocks, since
|
that is where insertion would have to take place. */
|
that is where insertion would have to take place. */
|
if (!all_immediate_uses_same_place (stmt))
|
if (!all_immediate_uses_same_place (stmt))
|
{
|
{
|
basic_block commondom = nearest_common_dominator_of_uses (stmt);
|
basic_block commondom = nearest_common_dominator_of_uses (stmt);
|
|
|
if (commondom == frombb)
|
if (commondom == frombb)
|
return NULL;
|
return NULL;
|
|
|
/* Our common dominator has to be dominated by frombb in order to be a
|
/* Our common dominator has to be dominated by frombb in order to be a
|
trivially safe place to put this statement, since it has multiple
|
trivially safe place to put this statement, since it has multiple
|
uses. */
|
uses. */
|
if (!dominated_by_p (CDI_DOMINATORS, commondom, frombb))
|
if (!dominated_by_p (CDI_DOMINATORS, commondom, frombb))
|
return NULL;
|
return NULL;
|
|
|
/* It doesn't make sense to move to a dominator that post-dominates
|
/* It doesn't make sense to move to a dominator that post-dominates
|
frombb, because it means we've just moved it into a path that always
|
frombb, because it means we've just moved it into a path that always
|
executes if frombb executes, instead of reducing the number of
|
executes if frombb executes, instead of reducing the number of
|
executions . */
|
executions . */
|
if (dominated_by_p (CDI_POST_DOMINATORS, frombb, commondom))
|
if (dominated_by_p (CDI_POST_DOMINATORS, frombb, commondom))
|
{
|
{
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
fprintf (dump_file, "Not moving store, common dominator post-dominates from block.\n");
|
fprintf (dump_file, "Not moving store, common dominator post-dominates from block.\n");
|
return NULL;
|
return NULL;
|
}
|
}
|
|
|
if (commondom == frombb || commondom->loop_depth > frombb->loop_depth)
|
if (commondom == frombb || commondom->loop_depth > frombb->loop_depth)
|
return NULL;
|
return NULL;
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
{
|
{
|
fprintf (dump_file, "Common dominator of all uses is %d\n",
|
fprintf (dump_file, "Common dominator of all uses is %d\n",
|
commondom->index);
|
commondom->index);
|
}
|
}
|
return first_stmt (commondom);
|
return first_stmt (commondom);
|
}
|
}
|
|
|
use = USE_STMT (one_use);
|
use = USE_STMT (one_use);
|
if (TREE_CODE (use) != PHI_NODE)
|
if (TREE_CODE (use) != PHI_NODE)
|
{
|
{
|
sinkbb = bb_for_stmt (use);
|
sinkbb = bb_for_stmt (use);
|
if (sinkbb == frombb || sinkbb->loop_depth > frombb->loop_depth
|
if (sinkbb == frombb || sinkbb->loop_depth > frombb->loop_depth
|
|| sinkbb->loop_father != frombb->loop_father)
|
|| sinkbb->loop_father != frombb->loop_father)
|
return NULL;
|
return NULL;
|
return use;
|
return use;
|
}
|
}
|
|
|
/* Note that at this point, all uses must be in the same statement, so it
|
/* Note that at this point, all uses must be in the same statement, so it
|
doesn't matter which def op we choose, pick the first one. */
|
doesn't matter which def op we choose, pick the first one. */
|
FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
|
FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
|
break;
|
break;
|
|
|
|
|
sinkbb = find_bb_for_arg (use, def);
|
sinkbb = find_bb_for_arg (use, def);
|
if (!sinkbb)
|
if (!sinkbb)
|
return NULL;
|
return NULL;
|
|
|
/* This will happen when you have
|
/* This will happen when you have
|
a_3 = PHI <a_13, a_26>
|
a_3 = PHI <a_13, a_26>
|
|
|
a_26 = V_MAY_DEF <a_3>
|
a_26 = V_MAY_DEF <a_3>
|
|
|
If the use is a phi, and is in the same bb as the def,
|
If the use is a phi, and is in the same bb as the def,
|
we can't sink it. */
|
we can't sink it. */
|
|
|
if (bb_for_stmt (use) == frombb)
|
if (bb_for_stmt (use) == frombb)
|
return NULL;
|
return NULL;
|
if (sinkbb == frombb || sinkbb->loop_depth > frombb->loop_depth
|
if (sinkbb == frombb || sinkbb->loop_depth > frombb->loop_depth
|
|| sinkbb->loop_father != frombb->loop_father)
|
|| sinkbb->loop_father != frombb->loop_father)
|
return NULL;
|
return NULL;
|
|
|
return first_stmt (sinkbb);
|
return first_stmt (sinkbb);
|
}
|
}
|
|
|
/* Perform code sinking on BB */
|
/* Perform code sinking on BB */
|
|
|
static void
|
static void
|
sink_code_in_bb (basic_block bb)
|
sink_code_in_bb (basic_block bb)
|
{
|
{
|
basic_block son;
|
basic_block son;
|
block_stmt_iterator bsi;
|
block_stmt_iterator bsi;
|
edge_iterator ei;
|
edge_iterator ei;
|
edge e;
|
edge e;
|
|
|
/* If this block doesn't dominate anything, there can't be any place to sink
|
/* If this block doesn't dominate anything, there can't be any place to sink
|
the statements to. */
|
the statements to. */
|
if (first_dom_son (CDI_DOMINATORS, bb) == NULL)
|
if (first_dom_son (CDI_DOMINATORS, bb) == NULL)
|
goto earlyout;
|
goto earlyout;
|
|
|
/* We can't move things across abnormal edges, so don't try. */
|
/* We can't move things across abnormal edges, so don't try. */
|
FOR_EACH_EDGE (e, ei, bb->succs)
|
FOR_EACH_EDGE (e, ei, bb->succs)
|
if (e->flags & EDGE_ABNORMAL)
|
if (e->flags & EDGE_ABNORMAL)
|
goto earlyout;
|
goto earlyout;
|
|
|
for (bsi = bsi_last (bb); !bsi_end_p (bsi);)
|
for (bsi = bsi_last (bb); !bsi_end_p (bsi);)
|
{
|
{
|
tree stmt = bsi_stmt (bsi);
|
tree stmt = bsi_stmt (bsi);
|
block_stmt_iterator tobsi;
|
block_stmt_iterator tobsi;
|
tree sinkstmt;
|
tree sinkstmt;
|
|
|
sinkstmt = statement_sink_location (stmt, bb);
|
sinkstmt = statement_sink_location (stmt, bb);
|
if (!sinkstmt)
|
if (!sinkstmt)
|
{
|
{
|
if (!bsi_end_p (bsi))
|
if (!bsi_end_p (bsi))
|
bsi_prev (&bsi);
|
bsi_prev (&bsi);
|
continue;
|
continue;
|
}
|
}
|
if (dump_file)
|
if (dump_file)
|
{
|
{
|
fprintf (dump_file, "Sinking ");
|
fprintf (dump_file, "Sinking ");
|
print_generic_expr (dump_file, stmt, TDF_VOPS);
|
print_generic_expr (dump_file, stmt, TDF_VOPS);
|
fprintf (dump_file, " from bb %d to bb %d\n",
|
fprintf (dump_file, " from bb %d to bb %d\n",
|
bb->index, bb_for_stmt (sinkstmt)->index);
|
bb->index, bb_for_stmt (sinkstmt)->index);
|
}
|
}
|
tobsi = bsi_for_stmt (sinkstmt);
|
tobsi = bsi_for_stmt (sinkstmt);
|
/* Find the first non-label. */
|
/* Find the first non-label. */
|
while (!bsi_end_p (tobsi)
|
while (!bsi_end_p (tobsi)
|
&& TREE_CODE (bsi_stmt (tobsi)) == LABEL_EXPR)
|
&& TREE_CODE (bsi_stmt (tobsi)) == LABEL_EXPR)
|
bsi_next (&tobsi);
|
bsi_next (&tobsi);
|
|
|
/* If this is the end of the basic block, we need to insert at the end
|
/* If this is the end of the basic block, we need to insert at the end
|
of the basic block. */
|
of the basic block. */
|
if (bsi_end_p (tobsi))
|
if (bsi_end_p (tobsi))
|
bsi_move_to_bb_end (&bsi, bb_for_stmt (sinkstmt));
|
bsi_move_to_bb_end (&bsi, bb_for_stmt (sinkstmt));
|
else
|
else
|
bsi_move_before (&bsi, &tobsi);
|
bsi_move_before (&bsi, &tobsi);
|
|
|
sink_stats.sunk++;
|
sink_stats.sunk++;
|
if (!bsi_end_p (bsi))
|
if (!bsi_end_p (bsi))
|
bsi_prev (&bsi);
|
bsi_prev (&bsi);
|
|
|
}
|
}
|
earlyout:
|
earlyout:
|
for (son = first_dom_son (CDI_POST_DOMINATORS, bb);
|
for (son = first_dom_son (CDI_POST_DOMINATORS, bb);
|
son;
|
son;
|
son = next_dom_son (CDI_POST_DOMINATORS, son))
|
son = next_dom_son (CDI_POST_DOMINATORS, son))
|
{
|
{
|
sink_code_in_bb (son);
|
sink_code_in_bb (son);
|
}
|
}
|
}
|
}
|
|
|
/* Perform code sinking.
|
/* Perform code sinking.
|
This moves code down the flowgraph when we know it would be
|
This moves code down the flowgraph when we know it would be
|
profitable to do so, or it wouldn't increase the number of
|
profitable to do so, or it wouldn't increase the number of
|
executions of the statement.
|
executions of the statement.
|
|
|
IE given
|
IE given
|
|
|
a_1 = b + c;
|
a_1 = b + c;
|
if (<something>)
|
if (<something>)
|
{
|
{
|
}
|
}
|
else
|
else
|
{
|
{
|
foo (&b, &c);
|
foo (&b, &c);
|
a_5 = b + c;
|
a_5 = b + c;
|
}
|
}
|
a_6 = PHI (a_5, a_1);
|
a_6 = PHI (a_5, a_1);
|
USE a_6.
|
USE a_6.
|
|
|
we'll transform this into:
|
we'll transform this into:
|
|
|
if (<something>)
|
if (<something>)
|
{
|
{
|
a_1 = b + c;
|
a_1 = b + c;
|
}
|
}
|
else
|
else
|
{
|
{
|
foo (&b, &c);
|
foo (&b, &c);
|
a_5 = b + c;
|
a_5 = b + c;
|
}
|
}
|
a_6 = PHI (a_5, a_1);
|
a_6 = PHI (a_5, a_1);
|
USE a_6.
|
USE a_6.
|
|
|
Note that this reduces the number of computations of a = b + c to 1
|
Note that this reduces the number of computations of a = b + c to 1
|
when we take the else edge, instead of 2.
|
when we take the else edge, instead of 2.
|
*/
|
*/
|
static void
|
static void
|
execute_sink_code (void)
|
execute_sink_code (void)
|
{
|
{
|
struct loops *loops = loop_optimizer_init (LOOPS_NORMAL);
|
struct loops *loops = loop_optimizer_init (LOOPS_NORMAL);
|
|
|
connect_infinite_loops_to_exit ();
|
connect_infinite_loops_to_exit ();
|
memset (&sink_stats, 0, sizeof (sink_stats));
|
memset (&sink_stats, 0, sizeof (sink_stats));
|
calculate_dominance_info (CDI_DOMINATORS | CDI_POST_DOMINATORS);
|
calculate_dominance_info (CDI_DOMINATORS | CDI_POST_DOMINATORS);
|
sink_code_in_bb (EXIT_BLOCK_PTR);
|
sink_code_in_bb (EXIT_BLOCK_PTR);
|
if (dump_file && (dump_flags & TDF_STATS))
|
if (dump_file && (dump_flags & TDF_STATS))
|
fprintf (dump_file, "Sunk statements:%d\n", sink_stats.sunk);
|
fprintf (dump_file, "Sunk statements:%d\n", sink_stats.sunk);
|
free_dominance_info (CDI_POST_DOMINATORS);
|
free_dominance_info (CDI_POST_DOMINATORS);
|
remove_fake_exit_edges ();
|
remove_fake_exit_edges ();
|
loop_optimizer_finalize (loops);
|
loop_optimizer_finalize (loops);
|
}
|
}
|
|
|
/* Gate and execute functions for PRE. */
|
/* Gate and execute functions for PRE. */
|
|
|
static unsigned int
|
static unsigned int
|
do_sink (void)
|
do_sink (void)
|
{
|
{
|
execute_sink_code ();
|
execute_sink_code ();
|
return 0;
|
return 0;
|
}
|
}
|
|
|
static bool
|
static bool
|
gate_sink (void)
|
gate_sink (void)
|
{
|
{
|
return flag_tree_sink != 0;
|
return flag_tree_sink != 0;
|
}
|
}
|
|
|
struct tree_opt_pass pass_sink_code =
|
struct tree_opt_pass pass_sink_code =
|
{
|
{
|
"sink", /* name */
|
"sink", /* name */
|
gate_sink, /* gate */
|
gate_sink, /* gate */
|
do_sink, /* execute */
|
do_sink, /* execute */
|
NULL, /* sub */
|
NULL, /* sub */
|
NULL, /* next */
|
NULL, /* next */
|
0, /* static_pass_number */
|
0, /* static_pass_number */
|
TV_TREE_SINK, /* tv_id */
|
TV_TREE_SINK, /* tv_id */
|
PROP_no_crit_edges | PROP_cfg
|
PROP_no_crit_edges | PROP_cfg
|
| PROP_ssa | PROP_alias, /* properties_required */
|
| PROP_ssa | PROP_alias, /* properties_required */
|
0, /* properties_provided */
|
0, /* properties_provided */
|
0, /* properties_destroyed */
|
0, /* properties_destroyed */
|
0, /* todo_flags_start */
|
0, /* todo_flags_start */
|
TODO_update_ssa
|
TODO_update_ssa
|
| TODO_dump_func
|
| TODO_dump_func
|
| TODO_ggc_collect
|
| TODO_ggc_collect
|
| TODO_verify_ssa, /* todo_flags_finish */
|
| TODO_verify_ssa, /* todo_flags_finish */
|
0 /* letter */
|
0 /* letter */
|
};
|
};
|
|
|
