/* Global, SSA-based optimizations using mathematical identities.
|
/* Global, SSA-based optimizations using mathematical identities.
|
Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010
|
Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010
|
Free Software Foundation, Inc.
|
Free Software Foundation, Inc.
|
|
|
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/>. */
|
|
|
/* Currently, the only mini-pass in this file tries to CSE reciprocal
|
/* Currently, the only mini-pass in this file tries to CSE reciprocal
|
operations. These are common in sequences such as this one:
|
operations. These are common in sequences such as this one:
|
|
|
modulus = sqrt(x*x + y*y + z*z);
|
modulus = sqrt(x*x + y*y + z*z);
|
x = x / modulus;
|
x = x / modulus;
|
y = y / modulus;
|
y = y / modulus;
|
z = z / modulus;
|
z = z / modulus;
|
|
|
that can be optimized to
|
that can be optimized to
|
|
|
modulus = sqrt(x*x + y*y + z*z);
|
modulus = sqrt(x*x + y*y + z*z);
|
rmodulus = 1.0 / modulus;
|
rmodulus = 1.0 / modulus;
|
x = x * rmodulus;
|
x = x * rmodulus;
|
y = y * rmodulus;
|
y = y * rmodulus;
|
z = z * rmodulus;
|
z = z * rmodulus;
|
|
|
We do this for loop invariant divisors, and with this pass whenever
|
We do this for loop invariant divisors, and with this pass whenever
|
we notice that a division has the same divisor multiple times.
|
we notice that a division has the same divisor multiple times.
|
|
|
Of course, like in PRE, we don't insert a division if a dominator
|
Of course, like in PRE, we don't insert a division if a dominator
|
already has one. However, this cannot be done as an extension of
|
already has one. However, this cannot be done as an extension of
|
PRE for several reasons.
|
PRE for several reasons.
|
|
|
First of all, with some experiments it was found out that the
|
First of all, with some experiments it was found out that the
|
transformation is not always useful if there are only two divisions
|
transformation is not always useful if there are only two divisions
|
hy the same divisor. This is probably because modern processors
|
hy the same divisor. This is probably because modern processors
|
can pipeline the divisions; on older, in-order processors it should
|
can pipeline the divisions; on older, in-order processors it should
|
still be effective to optimize two divisions by the same number.
|
still be effective to optimize two divisions by the same number.
|
We make this a param, and it shall be called N in the remainder of
|
We make this a param, and it shall be called N in the remainder of
|
this comment.
|
this comment.
|
|
|
Second, if trapping math is active, we have less freedom on where
|
Second, if trapping math is active, we have less freedom on where
|
to insert divisions: we can only do so in basic blocks that already
|
to insert divisions: we can only do so in basic blocks that already
|
contain one. (If divisions don't trap, instead, we can insert
|
contain one. (If divisions don't trap, instead, we can insert
|
divisions elsewhere, which will be in blocks that are common dominators
|
divisions elsewhere, which will be in blocks that are common dominators
|
of those that have the division).
|
of those that have the division).
|
|
|
We really don't want to compute the reciprocal unless a division will
|
We really don't want to compute the reciprocal unless a division will
|
be found. To do this, we won't insert the division in a basic block
|
be found. To do this, we won't insert the division in a basic block
|
that has less than N divisions *post-dominating* it.
|
that has less than N divisions *post-dominating* it.
|
|
|
The algorithm constructs a subset of the dominator tree, holding the
|
The algorithm constructs a subset of the dominator tree, holding the
|
blocks containing the divisions and the common dominators to them,
|
blocks containing the divisions and the common dominators to them,
|
and walk it twice. The first walk is in post-order, and it annotates
|
and walk it twice. The first walk is in post-order, and it annotates
|
each block with the number of divisions that post-dominate it: this
|
each block with the number of divisions that post-dominate it: this
|
gives information on where divisions can be inserted profitably.
|
gives information on where divisions can be inserted profitably.
|
The second walk is in pre-order, and it inserts divisions as explained
|
The second walk is in pre-order, and it inserts divisions as explained
|
above, and replaces divisions by multiplications.
|
above, and replaces divisions by multiplications.
|
|
|
In the best case, the cost of the pass is O(n_statements). In the
|
In the best case, the cost of the pass is O(n_statements). In the
|
worst-case, the cost is due to creating the dominator tree subset,
|
worst-case, the cost is due to creating the dominator tree subset,
|
with a cost of O(n_basic_blocks ^ 2); however this can only happen
|
with a cost of O(n_basic_blocks ^ 2); however this can only happen
|
for n_statements / n_basic_blocks statements. So, the amortized cost
|
for n_statements / n_basic_blocks statements. So, the amortized cost
|
of creating the dominator tree subset is O(n_basic_blocks) and the
|
of creating the dominator tree subset is O(n_basic_blocks) and the
|
worst-case cost of the pass is O(n_statements * n_basic_blocks).
|
worst-case cost of the pass is O(n_statements * n_basic_blocks).
|
|
|
More practically, the cost will be small because there are few
|
More practically, the cost will be small because there are few
|
divisions, and they tend to be in the same basic block, so insert_bb
|
divisions, and they tend to be in the same basic block, so insert_bb
|
is called very few times.
|
is called very few times.
|
|
|
If we did this using domwalk.c, an efficient implementation would have
|
If we did this using domwalk.c, an efficient implementation would have
|
to work on all the variables in a single pass, because we could not
|
to work on all the variables in a single pass, because we could not
|
work on just a subset of the dominator tree, as we do now, and the
|
work on just a subset of the dominator tree, as we do now, and the
|
cost would also be something like O(n_statements * n_basic_blocks).
|
cost would also be something like O(n_statements * n_basic_blocks).
|
The data structures would be more complex in order to work on all the
|
The data structures would be more complex in order to work on all the
|
variables in a single pass. */
|
variables in a single pass. */
|
|
|
#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 "flags.h"
|
#include "flags.h"
|
#include "tree.h"
|
#include "tree.h"
|
#include "tree-flow.h"
|
#include "tree-flow.h"
|
#include "real.h"
|
#include "real.h"
|
#include "timevar.h"
|
#include "timevar.h"
|
#include "tree-pass.h"
|
#include "tree-pass.h"
|
#include "alloc-pool.h"
|
#include "alloc-pool.h"
|
#include "basic-block.h"
|
#include "basic-block.h"
|
#include "target.h"
|
#include "target.h"
|
#include "diagnostic.h"
|
#include "diagnostic.h"
|
#include "rtl.h"
|
#include "rtl.h"
|
#include "expr.h"
|
#include "expr.h"
|
#include "optabs.h"
|
#include "optabs.h"
|
|
|
/* This structure represents one basic block that either computes a
|
/* This structure represents one basic block that either computes a
|
division, or is a common dominator for basic block that compute a
|
division, or is a common dominator for basic block that compute a
|
division. */
|
division. */
|
struct occurrence {
|
struct occurrence {
|
/* The basic block represented by this structure. */
|
/* The basic block represented by this structure. */
|
basic_block bb;
|
basic_block bb;
|
|
|
/* If non-NULL, the SSA_NAME holding the definition for a reciprocal
|
/* If non-NULL, the SSA_NAME holding the definition for a reciprocal
|
inserted in BB. */
|
inserted in BB. */
|
tree recip_def;
|
tree recip_def;
|
|
|
/* If non-NULL, the GIMPLE_ASSIGN for a reciprocal computation that
|
/* If non-NULL, the GIMPLE_ASSIGN for a reciprocal computation that
|
was inserted in BB. */
|
was inserted in BB. */
|
gimple recip_def_stmt;
|
gimple recip_def_stmt;
|
|
|
/* Pointer to a list of "struct occurrence"s for blocks dominated
|
/* Pointer to a list of "struct occurrence"s for blocks dominated
|
by BB. */
|
by BB. */
|
struct occurrence *children;
|
struct occurrence *children;
|
|
|
/* Pointer to the next "struct occurrence"s in the list of blocks
|
/* Pointer to the next "struct occurrence"s in the list of blocks
|
sharing a common dominator. */
|
sharing a common dominator. */
|
struct occurrence *next;
|
struct occurrence *next;
|
|
|
/* The number of divisions that are in BB before compute_merit. The
|
/* The number of divisions that are in BB before compute_merit. The
|
number of divisions that are in BB or post-dominate it after
|
number of divisions that are in BB or post-dominate it after
|
compute_merit. */
|
compute_merit. */
|
int num_divisions;
|
int num_divisions;
|
|
|
/* True if the basic block has a division, false if it is a common
|
/* True if the basic block has a division, false if it is a common
|
dominator for basic blocks that do. If it is false and trapping
|
dominator for basic blocks that do. If it is false and trapping
|
math is active, BB is not a candidate for inserting a reciprocal. */
|
math is active, BB is not a candidate for inserting a reciprocal. */
|
bool bb_has_division;
|
bool bb_has_division;
|
};
|
};
|
|
|
|
|
/* The instance of "struct occurrence" representing the highest
|
/* The instance of "struct occurrence" representing the highest
|
interesting block in the dominator tree. */
|
interesting block in the dominator tree. */
|
static struct occurrence *occ_head;
|
static struct occurrence *occ_head;
|
|
|
/* Allocation pool for getting instances of "struct occurrence". */
|
/* Allocation pool for getting instances of "struct occurrence". */
|
static alloc_pool occ_pool;
|
static alloc_pool occ_pool;
|
|
|
|
|
|
|
/* Allocate and return a new struct occurrence for basic block BB, and
|
/* Allocate and return a new struct occurrence for basic block BB, and
|
whose children list is headed by CHILDREN. */
|
whose children list is headed by CHILDREN. */
|
static struct occurrence *
|
static struct occurrence *
|
occ_new (basic_block bb, struct occurrence *children)
|
occ_new (basic_block bb, struct occurrence *children)
|
{
|
{
|
struct occurrence *occ;
|
struct occurrence *occ;
|
|
|
bb->aux = occ = (struct occurrence *) pool_alloc (occ_pool);
|
bb->aux = occ = (struct occurrence *) pool_alloc (occ_pool);
|
memset (occ, 0, sizeof (struct occurrence));
|
memset (occ, 0, sizeof (struct occurrence));
|
|
|
occ->bb = bb;
|
occ->bb = bb;
|
occ->children = children;
|
occ->children = children;
|
return occ;
|
return occ;
|
}
|
}
|
|
|
|
|
/* Insert NEW_OCC into our subset of the dominator tree. P_HEAD points to a
|
/* Insert NEW_OCC into our subset of the dominator tree. P_HEAD points to a
|
list of "struct occurrence"s, one per basic block, having IDOM as
|
list of "struct occurrence"s, one per basic block, having IDOM as
|
their common dominator.
|
their common dominator.
|
|
|
We try to insert NEW_OCC as deep as possible in the tree, and we also
|
We try to insert NEW_OCC as deep as possible in the tree, and we also
|
insert any other block that is a common dominator for BB and one
|
insert any other block that is a common dominator for BB and one
|
block already in the tree. */
|
block already in the tree. */
|
|
|
static void
|
static void
|
insert_bb (struct occurrence *new_occ, basic_block idom,
|
insert_bb (struct occurrence *new_occ, basic_block idom,
|
struct occurrence **p_head)
|
struct occurrence **p_head)
|
{
|
{
|
struct occurrence *occ, **p_occ;
|
struct occurrence *occ, **p_occ;
|
|
|
for (p_occ = p_head; (occ = *p_occ) != NULL; )
|
for (p_occ = p_head; (occ = *p_occ) != NULL; )
|
{
|
{
|
basic_block bb = new_occ->bb, occ_bb = occ->bb;
|
basic_block bb = new_occ->bb, occ_bb = occ->bb;
|
basic_block dom = nearest_common_dominator (CDI_DOMINATORS, occ_bb, bb);
|
basic_block dom = nearest_common_dominator (CDI_DOMINATORS, occ_bb, bb);
|
if (dom == bb)
|
if (dom == bb)
|
{
|
{
|
/* BB dominates OCC_BB. OCC becomes NEW_OCC's child: remove OCC
|
/* BB dominates OCC_BB. OCC becomes NEW_OCC's child: remove OCC
|
from its list. */
|
from its list. */
|
*p_occ = occ->next;
|
*p_occ = occ->next;
|
occ->next = new_occ->children;
|
occ->next = new_occ->children;
|
new_occ->children = occ;
|
new_occ->children = occ;
|
|
|
/* Try the next block (it may as well be dominated by BB). */
|
/* Try the next block (it may as well be dominated by BB). */
|
}
|
}
|
|
|
else if (dom == occ_bb)
|
else if (dom == occ_bb)
|
{
|
{
|
/* OCC_BB dominates BB. Tail recurse to look deeper. */
|
/* OCC_BB dominates BB. Tail recurse to look deeper. */
|
insert_bb (new_occ, dom, &occ->children);
|
insert_bb (new_occ, dom, &occ->children);
|
return;
|
return;
|
}
|
}
|
|
|
else if (dom != idom)
|
else if (dom != idom)
|
{
|
{
|
gcc_assert (!dom->aux);
|
gcc_assert (!dom->aux);
|
|
|
/* There is a dominator between IDOM and BB, add it and make
|
/* There is a dominator between IDOM and BB, add it and make
|
two children out of NEW_OCC and OCC. First, remove OCC from
|
two children out of NEW_OCC and OCC. First, remove OCC from
|
its list. */
|
its list. */
|
*p_occ = occ->next;
|
*p_occ = occ->next;
|
new_occ->next = occ;
|
new_occ->next = occ;
|
occ->next = NULL;
|
occ->next = NULL;
|
|
|
/* None of the previous blocks has DOM as a dominator: if we tail
|
/* None of the previous blocks has DOM as a dominator: if we tail
|
recursed, we would reexamine them uselessly. Just switch BB with
|
recursed, we would reexamine them uselessly. Just switch BB with
|
DOM, and go on looking for blocks dominated by DOM. */
|
DOM, and go on looking for blocks dominated by DOM. */
|
new_occ = occ_new (dom, new_occ);
|
new_occ = occ_new (dom, new_occ);
|
}
|
}
|
|
|
else
|
else
|
{
|
{
|
/* Nothing special, go on with the next element. */
|
/* Nothing special, go on with the next element. */
|
p_occ = &occ->next;
|
p_occ = &occ->next;
|
}
|
}
|
}
|
}
|
|
|
/* No place was found as a child of IDOM. Make BB a sibling of IDOM. */
|
/* No place was found as a child of IDOM. Make BB a sibling of IDOM. */
|
new_occ->next = *p_head;
|
new_occ->next = *p_head;
|
*p_head = new_occ;
|
*p_head = new_occ;
|
}
|
}
|
|
|
/* Register that we found a division in BB. */
|
/* Register that we found a division in BB. */
|
|
|
static inline void
|
static inline void
|
register_division_in (basic_block bb)
|
register_division_in (basic_block bb)
|
{
|
{
|
struct occurrence *occ;
|
struct occurrence *occ;
|
|
|
occ = (struct occurrence *) bb->aux;
|
occ = (struct occurrence *) bb->aux;
|
if (!occ)
|
if (!occ)
|
{
|
{
|
occ = occ_new (bb, NULL);
|
occ = occ_new (bb, NULL);
|
insert_bb (occ, ENTRY_BLOCK_PTR, &occ_head);
|
insert_bb (occ, ENTRY_BLOCK_PTR, &occ_head);
|
}
|
}
|
|
|
occ->bb_has_division = true;
|
occ->bb_has_division = true;
|
occ->num_divisions++;
|
occ->num_divisions++;
|
}
|
}
|
|
|
|
|
/* Compute the number of divisions that postdominate each block in OCC and
|
/* Compute the number of divisions that postdominate each block in OCC and
|
its children. */
|
its children. */
|
|
|
static void
|
static void
|
compute_merit (struct occurrence *occ)
|
compute_merit (struct occurrence *occ)
|
{
|
{
|
struct occurrence *occ_child;
|
struct occurrence *occ_child;
|
basic_block dom = occ->bb;
|
basic_block dom = occ->bb;
|
|
|
for (occ_child = occ->children; occ_child; occ_child = occ_child->next)
|
for (occ_child = occ->children; occ_child; occ_child = occ_child->next)
|
{
|
{
|
basic_block bb;
|
basic_block bb;
|
if (occ_child->children)
|
if (occ_child->children)
|
compute_merit (occ_child);
|
compute_merit (occ_child);
|
|
|
if (flag_exceptions)
|
if (flag_exceptions)
|
bb = single_noncomplex_succ (dom);
|
bb = single_noncomplex_succ (dom);
|
else
|
else
|
bb = dom;
|
bb = dom;
|
|
|
if (dominated_by_p (CDI_POST_DOMINATORS, bb, occ_child->bb))
|
if (dominated_by_p (CDI_POST_DOMINATORS, bb, occ_child->bb))
|
occ->num_divisions += occ_child->num_divisions;
|
occ->num_divisions += occ_child->num_divisions;
|
}
|
}
|
}
|
}
|
|
|
|
|
/* Return whether USE_STMT is a floating-point division by DEF. */
|
/* Return whether USE_STMT is a floating-point division by DEF. */
|
static inline bool
|
static inline bool
|
is_division_by (gimple use_stmt, tree def)
|
is_division_by (gimple use_stmt, tree def)
|
{
|
{
|
return is_gimple_assign (use_stmt)
|
return is_gimple_assign (use_stmt)
|
&& gimple_assign_rhs_code (use_stmt) == RDIV_EXPR
|
&& gimple_assign_rhs_code (use_stmt) == RDIV_EXPR
|
&& gimple_assign_rhs2 (use_stmt) == def
|
&& gimple_assign_rhs2 (use_stmt) == def
|
/* Do not recognize x / x as valid division, as we are getting
|
/* Do not recognize x / x as valid division, as we are getting
|
confused later by replacing all immediate uses x in such
|
confused later by replacing all immediate uses x in such
|
a stmt. */
|
a stmt. */
|
&& gimple_assign_rhs1 (use_stmt) != def;
|
&& gimple_assign_rhs1 (use_stmt) != def;
|
}
|
}
|
|
|
/* Walk the subset of the dominator tree rooted at OCC, setting the
|
/* Walk the subset of the dominator tree rooted at OCC, setting the
|
RECIP_DEF field to a definition of 1.0 / DEF that can be used in
|
RECIP_DEF field to a definition of 1.0 / DEF that can be used in
|
the given basic block. The field may be left NULL, of course,
|
the given basic block. The field may be left NULL, of course,
|
if it is not possible or profitable to do the optimization.
|
if it is not possible or profitable to do the optimization.
|
|
|
DEF_BSI is an iterator pointing at the statement defining DEF.
|
DEF_BSI is an iterator pointing at the statement defining DEF.
|
If RECIP_DEF is set, a dominator already has a computation that can
|
If RECIP_DEF is set, a dominator already has a computation that can
|
be used. */
|
be used. */
|
|
|
static void
|
static void
|
insert_reciprocals (gimple_stmt_iterator *def_gsi, struct occurrence *occ,
|
insert_reciprocals (gimple_stmt_iterator *def_gsi, struct occurrence *occ,
|
tree def, tree recip_def, int threshold)
|
tree def, tree recip_def, int threshold)
|
{
|
{
|
tree type;
|
tree type;
|
gimple new_stmt;
|
gimple new_stmt;
|
gimple_stmt_iterator gsi;
|
gimple_stmt_iterator gsi;
|
struct occurrence *occ_child;
|
struct occurrence *occ_child;
|
|
|
if (!recip_def
|
if (!recip_def
|
&& (occ->bb_has_division || !flag_trapping_math)
|
&& (occ->bb_has_division || !flag_trapping_math)
|
&& occ->num_divisions >= threshold)
|
&& occ->num_divisions >= threshold)
|
{
|
{
|
/* Make a variable with the replacement and substitute it. */
|
/* Make a variable with the replacement and substitute it. */
|
type = TREE_TYPE (def);
|
type = TREE_TYPE (def);
|
recip_def = make_rename_temp (type, "reciptmp");
|
recip_def = make_rename_temp (type, "reciptmp");
|
new_stmt = gimple_build_assign_with_ops (RDIV_EXPR, recip_def,
|
new_stmt = gimple_build_assign_with_ops (RDIV_EXPR, recip_def,
|
build_one_cst (type), def);
|
build_one_cst (type), def);
|
|
|
if (occ->bb_has_division)
|
if (occ->bb_has_division)
|
{
|
{
|
/* Case 1: insert before an existing division. */
|
/* Case 1: insert before an existing division. */
|
gsi = gsi_after_labels (occ->bb);
|
gsi = gsi_after_labels (occ->bb);
|
while (!gsi_end_p (gsi) && !is_division_by (gsi_stmt (gsi), def))
|
while (!gsi_end_p (gsi) && !is_division_by (gsi_stmt (gsi), def))
|
gsi_next (&gsi);
|
gsi_next (&gsi);
|
|
|
gsi_insert_before (&gsi, new_stmt, GSI_SAME_STMT);
|
gsi_insert_before (&gsi, new_stmt, GSI_SAME_STMT);
|
}
|
}
|
else if (def_gsi && occ->bb == def_gsi->bb)
|
else if (def_gsi && occ->bb == def_gsi->bb)
|
{
|
{
|
/* Case 2: insert right after the definition. Note that this will
|
/* Case 2: insert right after the definition. Note that this will
|
never happen if the definition statement can throw, because in
|
never happen if the definition statement can throw, because in
|
that case the sole successor of the statement's basic block will
|
that case the sole successor of the statement's basic block will
|
dominate all the uses as well. */
|
dominate all the uses as well. */
|
gsi_insert_after (def_gsi, new_stmt, GSI_NEW_STMT);
|
gsi_insert_after (def_gsi, new_stmt, GSI_NEW_STMT);
|
}
|
}
|
else
|
else
|
{
|
{
|
/* Case 3: insert in a basic block not containing defs/uses. */
|
/* Case 3: insert in a basic block not containing defs/uses. */
|
gsi = gsi_after_labels (occ->bb);
|
gsi = gsi_after_labels (occ->bb);
|
gsi_insert_before (&gsi, new_stmt, GSI_SAME_STMT);
|
gsi_insert_before (&gsi, new_stmt, GSI_SAME_STMT);
|
}
|
}
|
|
|
occ->recip_def_stmt = new_stmt;
|
occ->recip_def_stmt = new_stmt;
|
}
|
}
|
|
|
occ->recip_def = recip_def;
|
occ->recip_def = recip_def;
|
for (occ_child = occ->children; occ_child; occ_child = occ_child->next)
|
for (occ_child = occ->children; occ_child; occ_child = occ_child->next)
|
insert_reciprocals (def_gsi, occ_child, def, recip_def, threshold);
|
insert_reciprocals (def_gsi, occ_child, def, recip_def, threshold);
|
}
|
}
|
|
|
|
|
/* Replace the division at USE_P with a multiplication by the reciprocal, if
|
/* Replace the division at USE_P with a multiplication by the reciprocal, if
|
possible. */
|
possible. */
|
|
|
static inline void
|
static inline void
|
replace_reciprocal (use_operand_p use_p)
|
replace_reciprocal (use_operand_p use_p)
|
{
|
{
|
gimple use_stmt = USE_STMT (use_p);
|
gimple use_stmt = USE_STMT (use_p);
|
basic_block bb = gimple_bb (use_stmt);
|
basic_block bb = gimple_bb (use_stmt);
|
struct occurrence *occ = (struct occurrence *) bb->aux;
|
struct occurrence *occ = (struct occurrence *) bb->aux;
|
|
|
if (optimize_bb_for_speed_p (bb)
|
if (optimize_bb_for_speed_p (bb)
|
&& occ->recip_def && use_stmt != occ->recip_def_stmt)
|
&& occ->recip_def && use_stmt != occ->recip_def_stmt)
|
{
|
{
|
gimple_assign_set_rhs_code (use_stmt, MULT_EXPR);
|
gimple_assign_set_rhs_code (use_stmt, MULT_EXPR);
|
SET_USE (use_p, occ->recip_def);
|
SET_USE (use_p, occ->recip_def);
|
fold_stmt_inplace (use_stmt);
|
fold_stmt_inplace (use_stmt);
|
update_stmt (use_stmt);
|
update_stmt (use_stmt);
|
}
|
}
|
}
|
}
|
|
|
|
|
/* Free OCC and return one more "struct occurrence" to be freed. */
|
/* Free OCC and return one more "struct occurrence" to be freed. */
|
|
|
static struct occurrence *
|
static struct occurrence *
|
free_bb (struct occurrence *occ)
|
free_bb (struct occurrence *occ)
|
{
|
{
|
struct occurrence *child, *next;
|
struct occurrence *child, *next;
|
|
|
/* First get the two pointers hanging off OCC. */
|
/* First get the two pointers hanging off OCC. */
|
next = occ->next;
|
next = occ->next;
|
child = occ->children;
|
child = occ->children;
|
occ->bb->aux = NULL;
|
occ->bb->aux = NULL;
|
pool_free (occ_pool, occ);
|
pool_free (occ_pool, occ);
|
|
|
/* Now ensure that we don't recurse unless it is necessary. */
|
/* Now ensure that we don't recurse unless it is necessary. */
|
if (!child)
|
if (!child)
|
return next;
|
return next;
|
else
|
else
|
{
|
{
|
while (next)
|
while (next)
|
next = free_bb (next);
|
next = free_bb (next);
|
|
|
return child;
|
return child;
|
}
|
}
|
}
|
}
|
|
|
|
|
/* Look for floating-point divisions among DEF's uses, and try to
|
/* Look for floating-point divisions among DEF's uses, and try to
|
replace them by multiplications with the reciprocal. Add
|
replace them by multiplications with the reciprocal. Add
|
as many statements computing the reciprocal as needed.
|
as many statements computing the reciprocal as needed.
|
|
|
DEF must be a GIMPLE register of a floating-point type. */
|
DEF must be a GIMPLE register of a floating-point type. */
|
|
|
static void
|
static void
|
execute_cse_reciprocals_1 (gimple_stmt_iterator *def_gsi, tree def)
|
execute_cse_reciprocals_1 (gimple_stmt_iterator *def_gsi, tree def)
|
{
|
{
|
use_operand_p use_p;
|
use_operand_p use_p;
|
imm_use_iterator use_iter;
|
imm_use_iterator use_iter;
|
struct occurrence *occ;
|
struct occurrence *occ;
|
int count = 0, threshold;
|
int count = 0, threshold;
|
|
|
gcc_assert (FLOAT_TYPE_P (TREE_TYPE (def)) && is_gimple_reg (def));
|
gcc_assert (FLOAT_TYPE_P (TREE_TYPE (def)) && is_gimple_reg (def));
|
|
|
FOR_EACH_IMM_USE_FAST (use_p, use_iter, def)
|
FOR_EACH_IMM_USE_FAST (use_p, use_iter, def)
|
{
|
{
|
gimple use_stmt = USE_STMT (use_p);
|
gimple use_stmt = USE_STMT (use_p);
|
if (is_division_by (use_stmt, def))
|
if (is_division_by (use_stmt, def))
|
{
|
{
|
register_division_in (gimple_bb (use_stmt));
|
register_division_in (gimple_bb (use_stmt));
|
count++;
|
count++;
|
}
|
}
|
}
|
}
|
|
|
/* Do the expensive part only if we can hope to optimize something. */
|
/* Do the expensive part only if we can hope to optimize something. */
|
threshold = targetm.min_divisions_for_recip_mul (TYPE_MODE (TREE_TYPE (def)));
|
threshold = targetm.min_divisions_for_recip_mul (TYPE_MODE (TREE_TYPE (def)));
|
if (count >= threshold)
|
if (count >= threshold)
|
{
|
{
|
gimple use_stmt;
|
gimple use_stmt;
|
for (occ = occ_head; occ; occ = occ->next)
|
for (occ = occ_head; occ; occ = occ->next)
|
{
|
{
|
compute_merit (occ);
|
compute_merit (occ);
|
insert_reciprocals (def_gsi, occ, def, NULL, threshold);
|
insert_reciprocals (def_gsi, occ, def, NULL, threshold);
|
}
|
}
|
|
|
FOR_EACH_IMM_USE_STMT (use_stmt, use_iter, def)
|
FOR_EACH_IMM_USE_STMT (use_stmt, use_iter, def)
|
{
|
{
|
if (is_division_by (use_stmt, def))
|
if (is_division_by (use_stmt, def))
|
{
|
{
|
FOR_EACH_IMM_USE_ON_STMT (use_p, use_iter)
|
FOR_EACH_IMM_USE_ON_STMT (use_p, use_iter)
|
replace_reciprocal (use_p);
|
replace_reciprocal (use_p);
|
}
|
}
|
}
|
}
|
}
|
}
|
|
|
for (occ = occ_head; occ; )
|
for (occ = occ_head; occ; )
|
occ = free_bb (occ);
|
occ = free_bb (occ);
|
|
|
occ_head = NULL;
|
occ_head = NULL;
|
}
|
}
|
|
|
static bool
|
static bool
|
gate_cse_reciprocals (void)
|
gate_cse_reciprocals (void)
|
{
|
{
|
return optimize && flag_reciprocal_math;
|
return optimize && flag_reciprocal_math;
|
}
|
}
|
|
|
/* Go through all the floating-point SSA_NAMEs, and call
|
/* Go through all the floating-point SSA_NAMEs, and call
|
execute_cse_reciprocals_1 on each of them. */
|
execute_cse_reciprocals_1 on each of them. */
|
static unsigned int
|
static unsigned int
|
execute_cse_reciprocals (void)
|
execute_cse_reciprocals (void)
|
{
|
{
|
basic_block bb;
|
basic_block bb;
|
tree arg;
|
tree arg;
|
|
|
occ_pool = create_alloc_pool ("dominators for recip",
|
occ_pool = create_alloc_pool ("dominators for recip",
|
sizeof (struct occurrence),
|
sizeof (struct occurrence),
|
n_basic_blocks / 3 + 1);
|
n_basic_blocks / 3 + 1);
|
|
|
calculate_dominance_info (CDI_DOMINATORS);
|
calculate_dominance_info (CDI_DOMINATORS);
|
calculate_dominance_info (CDI_POST_DOMINATORS);
|
calculate_dominance_info (CDI_POST_DOMINATORS);
|
|
|
#ifdef ENABLE_CHECKING
|
#ifdef ENABLE_CHECKING
|
FOR_EACH_BB (bb)
|
FOR_EACH_BB (bb)
|
gcc_assert (!bb->aux);
|
gcc_assert (!bb->aux);
|
#endif
|
#endif
|
|
|
for (arg = DECL_ARGUMENTS (cfun->decl); arg; arg = TREE_CHAIN (arg))
|
for (arg = DECL_ARGUMENTS (cfun->decl); arg; arg = TREE_CHAIN (arg))
|
if (gimple_default_def (cfun, arg)
|
if (gimple_default_def (cfun, arg)
|
&& FLOAT_TYPE_P (TREE_TYPE (arg))
|
&& FLOAT_TYPE_P (TREE_TYPE (arg))
|
&& is_gimple_reg (arg))
|
&& is_gimple_reg (arg))
|
execute_cse_reciprocals_1 (NULL, gimple_default_def (cfun, arg));
|
execute_cse_reciprocals_1 (NULL, gimple_default_def (cfun, arg));
|
|
|
FOR_EACH_BB (bb)
|
FOR_EACH_BB (bb)
|
{
|
{
|
gimple_stmt_iterator gsi;
|
gimple_stmt_iterator gsi;
|
gimple phi;
|
gimple phi;
|
tree def;
|
tree def;
|
|
|
for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
|
for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
|
{
|
{
|
phi = gsi_stmt (gsi);
|
phi = gsi_stmt (gsi);
|
def = PHI_RESULT (phi);
|
def = PHI_RESULT (phi);
|
if (FLOAT_TYPE_P (TREE_TYPE (def))
|
if (FLOAT_TYPE_P (TREE_TYPE (def))
|
&& is_gimple_reg (def))
|
&& is_gimple_reg (def))
|
execute_cse_reciprocals_1 (NULL, def);
|
execute_cse_reciprocals_1 (NULL, def);
|
}
|
}
|
|
|
for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); gsi_next (&gsi))
|
for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); gsi_next (&gsi))
|
{
|
{
|
gimple stmt = gsi_stmt (gsi);
|
gimple stmt = gsi_stmt (gsi);
|
|
|
if (gimple_has_lhs (stmt)
|
if (gimple_has_lhs (stmt)
|
&& (def = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_DEF)) != NULL
|
&& (def = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_DEF)) != NULL
|
&& FLOAT_TYPE_P (TREE_TYPE (def))
|
&& FLOAT_TYPE_P (TREE_TYPE (def))
|
&& TREE_CODE (def) == SSA_NAME)
|
&& TREE_CODE (def) == SSA_NAME)
|
execute_cse_reciprocals_1 (&gsi, def);
|
execute_cse_reciprocals_1 (&gsi, def);
|
}
|
}
|
|
|
if (optimize_bb_for_size_p (bb))
|
if (optimize_bb_for_size_p (bb))
|
continue;
|
continue;
|
|
|
/* Scan for a/func(b) and convert it to reciprocal a*rfunc(b). */
|
/* Scan for a/func(b) and convert it to reciprocal a*rfunc(b). */
|
for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); gsi_next (&gsi))
|
for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); gsi_next (&gsi))
|
{
|
{
|
gimple stmt = gsi_stmt (gsi);
|
gimple stmt = gsi_stmt (gsi);
|
tree fndecl;
|
tree fndecl;
|
|
|
if (is_gimple_assign (stmt)
|
if (is_gimple_assign (stmt)
|
&& gimple_assign_rhs_code (stmt) == RDIV_EXPR)
|
&& gimple_assign_rhs_code (stmt) == RDIV_EXPR)
|
{
|
{
|
tree arg1 = gimple_assign_rhs2 (stmt);
|
tree arg1 = gimple_assign_rhs2 (stmt);
|
gimple stmt1;
|
gimple stmt1;
|
|
|
if (TREE_CODE (arg1) != SSA_NAME)
|
if (TREE_CODE (arg1) != SSA_NAME)
|
continue;
|
continue;
|
|
|
stmt1 = SSA_NAME_DEF_STMT (arg1);
|
stmt1 = SSA_NAME_DEF_STMT (arg1);
|
|
|
if (is_gimple_call (stmt1)
|
if (is_gimple_call (stmt1)
|
&& gimple_call_lhs (stmt1)
|
&& gimple_call_lhs (stmt1)
|
&& (fndecl = gimple_call_fndecl (stmt1))
|
&& (fndecl = gimple_call_fndecl (stmt1))
|
&& (DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
|
&& (DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
|
|| DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_MD))
|
|| DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_MD))
|
{
|
{
|
enum built_in_function code;
|
enum built_in_function code;
|
bool md_code, fail;
|
bool md_code, fail;
|
imm_use_iterator ui;
|
imm_use_iterator ui;
|
use_operand_p use_p;
|
use_operand_p use_p;
|
|
|
code = DECL_FUNCTION_CODE (fndecl);
|
code = DECL_FUNCTION_CODE (fndecl);
|
md_code = DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_MD;
|
md_code = DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_MD;
|
|
|
fndecl = targetm.builtin_reciprocal (code, md_code, false);
|
fndecl = targetm.builtin_reciprocal (code, md_code, false);
|
if (!fndecl)
|
if (!fndecl)
|
continue;
|
continue;
|
|
|
/* Check that all uses of the SSA name are divisions,
|
/* Check that all uses of the SSA name are divisions,
|
otherwise replacing the defining statement will do
|
otherwise replacing the defining statement will do
|
the wrong thing. */
|
the wrong thing. */
|
fail = false;
|
fail = false;
|
FOR_EACH_IMM_USE_FAST (use_p, ui, arg1)
|
FOR_EACH_IMM_USE_FAST (use_p, ui, arg1)
|
{
|
{
|
gimple stmt2 = USE_STMT (use_p);
|
gimple stmt2 = USE_STMT (use_p);
|
if (is_gimple_debug (stmt2))
|
if (is_gimple_debug (stmt2))
|
continue;
|
continue;
|
if (!is_gimple_assign (stmt2)
|
if (!is_gimple_assign (stmt2)
|
|| gimple_assign_rhs_code (stmt2) != RDIV_EXPR
|
|| gimple_assign_rhs_code (stmt2) != RDIV_EXPR
|
|| gimple_assign_rhs1 (stmt2) == arg1
|
|| gimple_assign_rhs1 (stmt2) == arg1
|
|| gimple_assign_rhs2 (stmt2) != arg1)
|
|| gimple_assign_rhs2 (stmt2) != arg1)
|
{
|
{
|
fail = true;
|
fail = true;
|
break;
|
break;
|
}
|
}
|
}
|
}
|
if (fail)
|
if (fail)
|
continue;
|
continue;
|
|
|
gimple_replace_lhs (stmt1, arg1);
|
gimple_replace_lhs (stmt1, arg1);
|
gimple_call_set_fndecl (stmt1, fndecl);
|
gimple_call_set_fndecl (stmt1, fndecl);
|
update_stmt (stmt1);
|
update_stmt (stmt1);
|
|
|
FOR_EACH_IMM_USE_STMT (stmt, ui, arg1)
|
FOR_EACH_IMM_USE_STMT (stmt, ui, arg1)
|
{
|
{
|
gimple_assign_set_rhs_code (stmt, MULT_EXPR);
|
gimple_assign_set_rhs_code (stmt, MULT_EXPR);
|
fold_stmt_inplace (stmt);
|
fold_stmt_inplace (stmt);
|
update_stmt (stmt);
|
update_stmt (stmt);
|
}
|
}
|
}
|
}
|
}
|
}
|
}
|
}
|
}
|
}
|
|
|
free_dominance_info (CDI_DOMINATORS);
|
free_dominance_info (CDI_DOMINATORS);
|
free_dominance_info (CDI_POST_DOMINATORS);
|
free_dominance_info (CDI_POST_DOMINATORS);
|
free_alloc_pool (occ_pool);
|
free_alloc_pool (occ_pool);
|
return 0;
|
return 0;
|
}
|
}
|
|
|
struct gimple_opt_pass pass_cse_reciprocals =
|
struct gimple_opt_pass pass_cse_reciprocals =
|
{
|
{
|
{
|
{
|
GIMPLE_PASS,
|
GIMPLE_PASS,
|
"recip", /* name */
|
"recip", /* name */
|
gate_cse_reciprocals, /* gate */
|
gate_cse_reciprocals, /* gate */
|
execute_cse_reciprocals, /* execute */
|
execute_cse_reciprocals, /* execute */
|
NULL, /* sub */
|
NULL, /* sub */
|
NULL, /* next */
|
NULL, /* next */
|
0, /* static_pass_number */
|
0, /* static_pass_number */
|
TV_NONE, /* tv_id */
|
TV_NONE, /* tv_id */
|
PROP_ssa, /* properties_required */
|
PROP_ssa, /* properties_required */
|
0, /* properties_provided */
|
0, /* properties_provided */
|
0, /* properties_destroyed */
|
0, /* properties_destroyed */
|
0, /* todo_flags_start */
|
0, /* todo_flags_start */
|
TODO_dump_func | TODO_update_ssa | TODO_verify_ssa
|
TODO_dump_func | TODO_update_ssa | TODO_verify_ssa
|
| TODO_verify_stmts /* todo_flags_finish */
|
| TODO_verify_stmts /* todo_flags_finish */
|
}
|
}
|
};
|
};
|
|
|
/* Records an occurrence at statement USE_STMT in the vector of trees
|
/* Records an occurrence at statement USE_STMT in the vector of trees
|
STMTS if it is dominated by *TOP_BB or dominates it or this basic block
|
STMTS if it is dominated by *TOP_BB or dominates it or this basic block
|
is not yet initialized. Returns true if the occurrence was pushed on
|
is not yet initialized. Returns true if the occurrence was pushed on
|
the vector. Adjusts *TOP_BB to be the basic block dominating all
|
the vector. Adjusts *TOP_BB to be the basic block dominating all
|
statements in the vector. */
|
statements in the vector. */
|
|
|
static bool
|
static bool
|
maybe_record_sincos (VEC(gimple, heap) **stmts,
|
maybe_record_sincos (VEC(gimple, heap) **stmts,
|
basic_block *top_bb, gimple use_stmt)
|
basic_block *top_bb, gimple use_stmt)
|
{
|
{
|
basic_block use_bb = gimple_bb (use_stmt);
|
basic_block use_bb = gimple_bb (use_stmt);
|
if (*top_bb
|
if (*top_bb
|
&& (*top_bb == use_bb
|
&& (*top_bb == use_bb
|
|| dominated_by_p (CDI_DOMINATORS, use_bb, *top_bb)))
|
|| dominated_by_p (CDI_DOMINATORS, use_bb, *top_bb)))
|
VEC_safe_push (gimple, heap, *stmts, use_stmt);
|
VEC_safe_push (gimple, heap, *stmts, use_stmt);
|
else if (!*top_bb
|
else if (!*top_bb
|
|| dominated_by_p (CDI_DOMINATORS, *top_bb, use_bb))
|
|| dominated_by_p (CDI_DOMINATORS, *top_bb, use_bb))
|
{
|
{
|
VEC_safe_push (gimple, heap, *stmts, use_stmt);
|
VEC_safe_push (gimple, heap, *stmts, use_stmt);
|
*top_bb = use_bb;
|
*top_bb = use_bb;
|
}
|
}
|
else
|
else
|
return false;
|
return false;
|
|
|
return true;
|
return true;
|
}
|
}
|
|
|
/* Look for sin, cos and cexpi calls with the same argument NAME and
|
/* Look for sin, cos and cexpi calls with the same argument NAME and
|
create a single call to cexpi CSEing the result in this case.
|
create a single call to cexpi CSEing the result in this case.
|
We first walk over all immediate uses of the argument collecting
|
We first walk over all immediate uses of the argument collecting
|
statements that we can CSE in a vector and in a second pass replace
|
statements that we can CSE in a vector and in a second pass replace
|
the statement rhs with a REALPART or IMAGPART expression on the
|
the statement rhs with a REALPART or IMAGPART expression on the
|
result of the cexpi call we insert before the use statement that
|
result of the cexpi call we insert before the use statement that
|
dominates all other candidates. */
|
dominates all other candidates. */
|
|
|
static void
|
static void
|
execute_cse_sincos_1 (tree name)
|
execute_cse_sincos_1 (tree name)
|
{
|
{
|
gimple_stmt_iterator gsi;
|
gimple_stmt_iterator gsi;
|
imm_use_iterator use_iter;
|
imm_use_iterator use_iter;
|
tree fndecl, res, type;
|
tree fndecl, res, type;
|
gimple def_stmt, use_stmt, stmt;
|
gimple def_stmt, use_stmt, stmt;
|
int seen_cos = 0, seen_sin = 0, seen_cexpi = 0;
|
int seen_cos = 0, seen_sin = 0, seen_cexpi = 0;
|
VEC(gimple, heap) *stmts = NULL;
|
VEC(gimple, heap) *stmts = NULL;
|
basic_block top_bb = NULL;
|
basic_block top_bb = NULL;
|
int i;
|
int i;
|
|
|
type = TREE_TYPE (name);
|
type = TREE_TYPE (name);
|
FOR_EACH_IMM_USE_STMT (use_stmt, use_iter, name)
|
FOR_EACH_IMM_USE_STMT (use_stmt, use_iter, name)
|
{
|
{
|
if (gimple_code (use_stmt) != GIMPLE_CALL
|
if (gimple_code (use_stmt) != GIMPLE_CALL
|
|| !gimple_call_lhs (use_stmt)
|
|| !gimple_call_lhs (use_stmt)
|
|| !(fndecl = gimple_call_fndecl (use_stmt))
|
|| !(fndecl = gimple_call_fndecl (use_stmt))
|
|| DECL_BUILT_IN_CLASS (fndecl) != BUILT_IN_NORMAL)
|
|| DECL_BUILT_IN_CLASS (fndecl) != BUILT_IN_NORMAL)
|
continue;
|
continue;
|
|
|
switch (DECL_FUNCTION_CODE (fndecl))
|
switch (DECL_FUNCTION_CODE (fndecl))
|
{
|
{
|
CASE_FLT_FN (BUILT_IN_COS):
|
CASE_FLT_FN (BUILT_IN_COS):
|
seen_cos |= maybe_record_sincos (&stmts, &top_bb, use_stmt) ? 1 : 0;
|
seen_cos |= maybe_record_sincos (&stmts, &top_bb, use_stmt) ? 1 : 0;
|
break;
|
break;
|
|
|
CASE_FLT_FN (BUILT_IN_SIN):
|
CASE_FLT_FN (BUILT_IN_SIN):
|
seen_sin |= maybe_record_sincos (&stmts, &top_bb, use_stmt) ? 1 : 0;
|
seen_sin |= maybe_record_sincos (&stmts, &top_bb, use_stmt) ? 1 : 0;
|
break;
|
break;
|
|
|
CASE_FLT_FN (BUILT_IN_CEXPI):
|
CASE_FLT_FN (BUILT_IN_CEXPI):
|
seen_cexpi |= maybe_record_sincos (&stmts, &top_bb, use_stmt) ? 1 : 0;
|
seen_cexpi |= maybe_record_sincos (&stmts, &top_bb, use_stmt) ? 1 : 0;
|
break;
|
break;
|
|
|
default:;
|
default:;
|
}
|
}
|
}
|
}
|
|
|
if (seen_cos + seen_sin + seen_cexpi <= 1)
|
if (seen_cos + seen_sin + seen_cexpi <= 1)
|
{
|
{
|
VEC_free(gimple, heap, stmts);
|
VEC_free(gimple, heap, stmts);
|
return;
|
return;
|
}
|
}
|
|
|
/* Simply insert cexpi at the beginning of top_bb but not earlier than
|
/* Simply insert cexpi at the beginning of top_bb but not earlier than
|
the name def statement. */
|
the name def statement. */
|
fndecl = mathfn_built_in (type, BUILT_IN_CEXPI);
|
fndecl = mathfn_built_in (type, BUILT_IN_CEXPI);
|
if (!fndecl)
|
if (!fndecl)
|
return;
|
return;
|
res = make_rename_temp (TREE_TYPE (TREE_TYPE (fndecl)), "sincostmp");
|
res = make_rename_temp (TREE_TYPE (TREE_TYPE (fndecl)), "sincostmp");
|
stmt = gimple_build_call (fndecl, 1, name);
|
stmt = gimple_build_call (fndecl, 1, name);
|
gimple_call_set_lhs (stmt, res);
|
gimple_call_set_lhs (stmt, res);
|
|
|
def_stmt = SSA_NAME_DEF_STMT (name);
|
def_stmt = SSA_NAME_DEF_STMT (name);
|
if (!SSA_NAME_IS_DEFAULT_DEF (name)
|
if (!SSA_NAME_IS_DEFAULT_DEF (name)
|
&& gimple_code (def_stmt) != GIMPLE_PHI
|
&& gimple_code (def_stmt) != GIMPLE_PHI
|
&& gimple_bb (def_stmt) == top_bb)
|
&& gimple_bb (def_stmt) == top_bb)
|
{
|
{
|
gsi = gsi_for_stmt (def_stmt);
|
gsi = gsi_for_stmt (def_stmt);
|
gsi_insert_after (&gsi, stmt, GSI_SAME_STMT);
|
gsi_insert_after (&gsi, stmt, GSI_SAME_STMT);
|
}
|
}
|
else
|
else
|
{
|
{
|
gsi = gsi_after_labels (top_bb);
|
gsi = gsi_after_labels (top_bb);
|
gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
|
gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
|
}
|
}
|
update_stmt (stmt);
|
update_stmt (stmt);
|
|
|
/* And adjust the recorded old call sites. */
|
/* And adjust the recorded old call sites. */
|
for (i = 0; VEC_iterate(gimple, stmts, i, use_stmt); ++i)
|
for (i = 0; VEC_iterate(gimple, stmts, i, use_stmt); ++i)
|
{
|
{
|
tree rhs = NULL;
|
tree rhs = NULL;
|
fndecl = gimple_call_fndecl (use_stmt);
|
fndecl = gimple_call_fndecl (use_stmt);
|
|
|
switch (DECL_FUNCTION_CODE (fndecl))
|
switch (DECL_FUNCTION_CODE (fndecl))
|
{
|
{
|
CASE_FLT_FN (BUILT_IN_COS):
|
CASE_FLT_FN (BUILT_IN_COS):
|
rhs = fold_build1 (REALPART_EXPR, type, res);
|
rhs = fold_build1 (REALPART_EXPR, type, res);
|
break;
|
break;
|
|
|
CASE_FLT_FN (BUILT_IN_SIN):
|
CASE_FLT_FN (BUILT_IN_SIN):
|
rhs = fold_build1 (IMAGPART_EXPR, type, res);
|
rhs = fold_build1 (IMAGPART_EXPR, type, res);
|
break;
|
break;
|
|
|
CASE_FLT_FN (BUILT_IN_CEXPI):
|
CASE_FLT_FN (BUILT_IN_CEXPI):
|
rhs = res;
|
rhs = res;
|
break;
|
break;
|
|
|
default:;
|
default:;
|
gcc_unreachable ();
|
gcc_unreachable ();
|
}
|
}
|
|
|
/* Replace call with a copy. */
|
/* Replace call with a copy. */
|
stmt = gimple_build_assign (gimple_call_lhs (use_stmt), rhs);
|
stmt = gimple_build_assign (gimple_call_lhs (use_stmt), rhs);
|
|
|
gsi = gsi_for_stmt (use_stmt);
|
gsi = gsi_for_stmt (use_stmt);
|
gsi_insert_after (&gsi, stmt, GSI_SAME_STMT);
|
gsi_insert_after (&gsi, stmt, GSI_SAME_STMT);
|
gsi_remove (&gsi, true);
|
gsi_remove (&gsi, true);
|
}
|
}
|
|
|
VEC_free(gimple, heap, stmts);
|
VEC_free(gimple, heap, stmts);
|
}
|
}
|
|
|
/* Go through all calls to sin, cos and cexpi and call execute_cse_sincos_1
|
/* Go through all calls to sin, cos and cexpi and call execute_cse_sincos_1
|
on the SSA_NAME argument of each of them. */
|
on the SSA_NAME argument of each of them. */
|
|
|
static unsigned int
|
static unsigned int
|
execute_cse_sincos (void)
|
execute_cse_sincos (void)
|
{
|
{
|
basic_block bb;
|
basic_block bb;
|
|
|
calculate_dominance_info (CDI_DOMINATORS);
|
calculate_dominance_info (CDI_DOMINATORS);
|
|
|
FOR_EACH_BB (bb)
|
FOR_EACH_BB (bb)
|
{
|
{
|
gimple_stmt_iterator gsi;
|
gimple_stmt_iterator gsi;
|
|
|
for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); gsi_next (&gsi))
|
for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); gsi_next (&gsi))
|
{
|
{
|
gimple stmt = gsi_stmt (gsi);
|
gimple stmt = gsi_stmt (gsi);
|
tree fndecl;
|
tree fndecl;
|
|
|
if (is_gimple_call (stmt)
|
if (is_gimple_call (stmt)
|
&& gimple_call_lhs (stmt)
|
&& gimple_call_lhs (stmt)
|
&& (fndecl = gimple_call_fndecl (stmt))
|
&& (fndecl = gimple_call_fndecl (stmt))
|
&& DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL)
|
&& DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL)
|
{
|
{
|
tree arg;
|
tree arg;
|
|
|
switch (DECL_FUNCTION_CODE (fndecl))
|
switch (DECL_FUNCTION_CODE (fndecl))
|
{
|
{
|
CASE_FLT_FN (BUILT_IN_COS):
|
CASE_FLT_FN (BUILT_IN_COS):
|
CASE_FLT_FN (BUILT_IN_SIN):
|
CASE_FLT_FN (BUILT_IN_SIN):
|
CASE_FLT_FN (BUILT_IN_CEXPI):
|
CASE_FLT_FN (BUILT_IN_CEXPI):
|
arg = gimple_call_arg (stmt, 0);
|
arg = gimple_call_arg (stmt, 0);
|
if (TREE_CODE (arg) == SSA_NAME)
|
if (TREE_CODE (arg) == SSA_NAME)
|
execute_cse_sincos_1 (arg);
|
execute_cse_sincos_1 (arg);
|
break;
|
break;
|
|
|
default:;
|
default:;
|
}
|
}
|
}
|
}
|
}
|
}
|
}
|
}
|
|
|
free_dominance_info (CDI_DOMINATORS);
|
free_dominance_info (CDI_DOMINATORS);
|
return 0;
|
return 0;
|
}
|
}
|
|
|
static bool
|
static bool
|
gate_cse_sincos (void)
|
gate_cse_sincos (void)
|
{
|
{
|
/* Make sure we have either sincos or cexp. */
|
/* Make sure we have either sincos or cexp. */
|
return (TARGET_HAS_SINCOS
|
return (TARGET_HAS_SINCOS
|
|| TARGET_C99_FUNCTIONS)
|
|| TARGET_C99_FUNCTIONS)
|
&& optimize;
|
&& optimize;
|
}
|
}
|
|
|
struct gimple_opt_pass pass_cse_sincos =
|
struct gimple_opt_pass pass_cse_sincos =
|
{
|
{
|
{
|
{
|
GIMPLE_PASS,
|
GIMPLE_PASS,
|
"sincos", /* name */
|
"sincos", /* name */
|
gate_cse_sincos, /* gate */
|
gate_cse_sincos, /* gate */
|
execute_cse_sincos, /* execute */
|
execute_cse_sincos, /* execute */
|
NULL, /* sub */
|
NULL, /* sub */
|
NULL, /* next */
|
NULL, /* next */
|
0, /* static_pass_number */
|
0, /* static_pass_number */
|
TV_NONE, /* tv_id */
|
TV_NONE, /* tv_id */
|
PROP_ssa, /* properties_required */
|
PROP_ssa, /* properties_required */
|
0, /* properties_provided */
|
0, /* properties_provided */
|
0, /* properties_destroyed */
|
0, /* properties_destroyed */
|
0, /* todo_flags_start */
|
0, /* todo_flags_start */
|
TODO_dump_func | TODO_update_ssa | TODO_verify_ssa
|
TODO_dump_func | TODO_update_ssa | TODO_verify_ssa
|
| TODO_verify_stmts /* todo_flags_finish */
|
| TODO_verify_stmts /* todo_flags_finish */
|
}
|
}
|
};
|
};
|
|
|
/* A symbolic number is used to detect byte permutation and selection
|
/* A symbolic number is used to detect byte permutation and selection
|
patterns. Therefore the field N contains an artificial number
|
patterns. Therefore the field N contains an artificial number
|
consisting of byte size markers:
|
consisting of byte size markers:
|
|
|
0 - byte has the value 0
|
0 - byte has the value 0
|
1..size - byte contains the content of the byte
|
1..size - byte contains the content of the byte
|
number indexed with that value minus one */
|
number indexed with that value minus one */
|
|
|
struct symbolic_number {
|
struct symbolic_number {
|
unsigned HOST_WIDEST_INT n;
|
unsigned HOST_WIDEST_INT n;
|
int size;
|
int size;
|
};
|
};
|
|
|
/* Perform a SHIFT or ROTATE operation by COUNT bits on symbolic
|
/* Perform a SHIFT or ROTATE operation by COUNT bits on symbolic
|
number N. Return false if the requested operation is not permitted
|
number N. Return false if the requested operation is not permitted
|
on a symbolic number. */
|
on a symbolic number. */
|
|
|
static inline bool
|
static inline bool
|
do_shift_rotate (enum tree_code code,
|
do_shift_rotate (enum tree_code code,
|
struct symbolic_number *n,
|
struct symbolic_number *n,
|
int count)
|
int count)
|
{
|
{
|
if (count % 8 != 0)
|
if (count % 8 != 0)
|
return false;
|
return false;
|
|
|
/* Zero out the extra bits of N in order to avoid them being shifted
|
/* Zero out the extra bits of N in order to avoid them being shifted
|
into the significant bits. */
|
into the significant bits. */
|
if (n->size < (int)sizeof (HOST_WIDEST_INT))
|
if (n->size < (int)sizeof (HOST_WIDEST_INT))
|
n->n &= ((unsigned HOST_WIDEST_INT)1 << (n->size * BITS_PER_UNIT)) - 1;
|
n->n &= ((unsigned HOST_WIDEST_INT)1 << (n->size * BITS_PER_UNIT)) - 1;
|
|
|
switch (code)
|
switch (code)
|
{
|
{
|
case LSHIFT_EXPR:
|
case LSHIFT_EXPR:
|
n->n <<= count;
|
n->n <<= count;
|
break;
|
break;
|
case RSHIFT_EXPR:
|
case RSHIFT_EXPR:
|
n->n >>= count;
|
n->n >>= count;
|
break;
|
break;
|
case LROTATE_EXPR:
|
case LROTATE_EXPR:
|
n->n = (n->n << count) | (n->n >> ((n->size * BITS_PER_UNIT) - count));
|
n->n = (n->n << count) | (n->n >> ((n->size * BITS_PER_UNIT) - count));
|
break;
|
break;
|
case RROTATE_EXPR:
|
case RROTATE_EXPR:
|
n->n = (n->n >> count) | (n->n << ((n->size * BITS_PER_UNIT) - count));
|
n->n = (n->n >> count) | (n->n << ((n->size * BITS_PER_UNIT) - count));
|
break;
|
break;
|
default:
|
default:
|
return false;
|
return false;
|
}
|
}
|
return true;
|
return true;
|
}
|
}
|
|
|
/* Perform sanity checking for the symbolic number N and the gimple
|
/* Perform sanity checking for the symbolic number N and the gimple
|
statement STMT. */
|
statement STMT. */
|
|
|
static inline bool
|
static inline bool
|
verify_symbolic_number_p (struct symbolic_number *n, gimple stmt)
|
verify_symbolic_number_p (struct symbolic_number *n, gimple stmt)
|
{
|
{
|
tree lhs_type;
|
tree lhs_type;
|
|
|
lhs_type = gimple_expr_type (stmt);
|
lhs_type = gimple_expr_type (stmt);
|
|
|
if (TREE_CODE (lhs_type) != INTEGER_TYPE)
|
if (TREE_CODE (lhs_type) != INTEGER_TYPE)
|
return false;
|
return false;
|
|
|
if (TYPE_PRECISION (lhs_type) != n->size * BITS_PER_UNIT)
|
if (TYPE_PRECISION (lhs_type) != n->size * BITS_PER_UNIT)
|
return false;
|
return false;
|
|
|
return true;
|
return true;
|
}
|
}
|
|
|
/* find_bswap_1 invokes itself recursively with N and tries to perform
|
/* find_bswap_1 invokes itself recursively with N and tries to perform
|
the operation given by the rhs of STMT on the result. If the
|
the operation given by the rhs of STMT on the result. If the
|
operation could successfully be executed the function returns the
|
operation could successfully be executed the function returns the
|
tree expression of the source operand and NULL otherwise. */
|
tree expression of the source operand and NULL otherwise. */
|
|
|
static tree
|
static tree
|
find_bswap_1 (gimple stmt, struct symbolic_number *n, int limit)
|
find_bswap_1 (gimple stmt, struct symbolic_number *n, int limit)
|
{
|
{
|
enum tree_code code;
|
enum tree_code code;
|
tree rhs1, rhs2 = NULL;
|
tree rhs1, rhs2 = NULL;
|
gimple rhs1_stmt, rhs2_stmt;
|
gimple rhs1_stmt, rhs2_stmt;
|
tree source_expr1;
|
tree source_expr1;
|
enum gimple_rhs_class rhs_class;
|
enum gimple_rhs_class rhs_class;
|
|
|
if (!limit || !is_gimple_assign (stmt))
|
if (!limit || !is_gimple_assign (stmt))
|
return NULL_TREE;
|
return NULL_TREE;
|
|
|
rhs1 = gimple_assign_rhs1 (stmt);
|
rhs1 = gimple_assign_rhs1 (stmt);
|
|
|
if (TREE_CODE (rhs1) != SSA_NAME)
|
if (TREE_CODE (rhs1) != SSA_NAME)
|
return NULL_TREE;
|
return NULL_TREE;
|
|
|
code = gimple_assign_rhs_code (stmt);
|
code = gimple_assign_rhs_code (stmt);
|
rhs_class = gimple_assign_rhs_class (stmt);
|
rhs_class = gimple_assign_rhs_class (stmt);
|
rhs1_stmt = SSA_NAME_DEF_STMT (rhs1);
|
rhs1_stmt = SSA_NAME_DEF_STMT (rhs1);
|
|
|
if (rhs_class == GIMPLE_BINARY_RHS)
|
if (rhs_class == GIMPLE_BINARY_RHS)
|
rhs2 = gimple_assign_rhs2 (stmt);
|
rhs2 = gimple_assign_rhs2 (stmt);
|
|
|
/* Handle unary rhs and binary rhs with integer constants as second
|
/* Handle unary rhs and binary rhs with integer constants as second
|
operand. */
|
operand. */
|
|
|
if (rhs_class == GIMPLE_UNARY_RHS
|
if (rhs_class == GIMPLE_UNARY_RHS
|
|| (rhs_class == GIMPLE_BINARY_RHS
|
|| (rhs_class == GIMPLE_BINARY_RHS
|
&& TREE_CODE (rhs2) == INTEGER_CST))
|
&& TREE_CODE (rhs2) == INTEGER_CST))
|
{
|
{
|
if (code != BIT_AND_EXPR
|
if (code != BIT_AND_EXPR
|
&& code != LSHIFT_EXPR
|
&& code != LSHIFT_EXPR
|
&& code != RSHIFT_EXPR
|
&& code != RSHIFT_EXPR
|
&& code != LROTATE_EXPR
|
&& code != LROTATE_EXPR
|
&& code != RROTATE_EXPR
|
&& code != RROTATE_EXPR
|
&& code != NOP_EXPR
|
&& code != NOP_EXPR
|
&& code != CONVERT_EXPR)
|
&& code != CONVERT_EXPR)
|
return NULL_TREE;
|
return NULL_TREE;
|
|
|
source_expr1 = find_bswap_1 (rhs1_stmt, n, limit - 1);
|
source_expr1 = find_bswap_1 (rhs1_stmt, n, limit - 1);
|
|
|
/* If find_bswap_1 returned NULL STMT is a leaf node and we have
|
/* If find_bswap_1 returned NULL STMT is a leaf node and we have
|
to initialize the symbolic number. */
|
to initialize the symbolic number. */
|
if (!source_expr1)
|
if (!source_expr1)
|
{
|
{
|
/* Set up the symbolic number N by setting each byte to a
|
/* Set up the symbolic number N by setting each byte to a
|
value between 1 and the byte size of rhs1. The highest
|
value between 1 and the byte size of rhs1. The highest
|
order byte is set to n->size and the lowest order
|
order byte is set to n->size and the lowest order
|
byte to 1. */
|
byte to 1. */
|
n->size = TYPE_PRECISION (TREE_TYPE (rhs1));
|
n->size = TYPE_PRECISION (TREE_TYPE (rhs1));
|
if (n->size % BITS_PER_UNIT != 0)
|
if (n->size % BITS_PER_UNIT != 0)
|
return NULL_TREE;
|
return NULL_TREE;
|
n->size /= BITS_PER_UNIT;
|
n->size /= BITS_PER_UNIT;
|
n->n = (sizeof (HOST_WIDEST_INT) < 8 ? 0 :
|
n->n = (sizeof (HOST_WIDEST_INT) < 8 ? 0 :
|
(unsigned HOST_WIDEST_INT)0x08070605 << 32 | 0x04030201);
|
(unsigned HOST_WIDEST_INT)0x08070605 << 32 | 0x04030201);
|
|
|
if (n->size < (int)sizeof (HOST_WIDEST_INT))
|
if (n->size < (int)sizeof (HOST_WIDEST_INT))
|
n->n &= ((unsigned HOST_WIDEST_INT)1 <<
|
n->n &= ((unsigned HOST_WIDEST_INT)1 <<
|
(n->size * BITS_PER_UNIT)) - 1;
|
(n->size * BITS_PER_UNIT)) - 1;
|
|
|
source_expr1 = rhs1;
|
source_expr1 = rhs1;
|
}
|
}
|
|
|
switch (code)
|
switch (code)
|
{
|
{
|
case BIT_AND_EXPR:
|
case BIT_AND_EXPR:
|
{
|
{
|
int i;
|
int i;
|
unsigned HOST_WIDEST_INT val = widest_int_cst_value (rhs2);
|
unsigned HOST_WIDEST_INT val = widest_int_cst_value (rhs2);
|
unsigned HOST_WIDEST_INT tmp = val;
|
unsigned HOST_WIDEST_INT tmp = val;
|
|
|
/* Only constants masking full bytes are allowed. */
|
/* Only constants masking full bytes are allowed. */
|
for (i = 0; i < n->size; i++, tmp >>= BITS_PER_UNIT)
|
for (i = 0; i < n->size; i++, tmp >>= BITS_PER_UNIT)
|
if ((tmp & 0xff) != 0 && (tmp & 0xff) != 0xff)
|
if ((tmp & 0xff) != 0 && (tmp & 0xff) != 0xff)
|
return NULL_TREE;
|
return NULL_TREE;
|
|
|
n->n &= val;
|
n->n &= val;
|
}
|
}
|
break;
|
break;
|
case LSHIFT_EXPR:
|
case LSHIFT_EXPR:
|
case RSHIFT_EXPR:
|
case RSHIFT_EXPR:
|
case LROTATE_EXPR:
|
case LROTATE_EXPR:
|
case RROTATE_EXPR:
|
case RROTATE_EXPR:
|
if (!do_shift_rotate (code, n, (int)TREE_INT_CST_LOW (rhs2)))
|
if (!do_shift_rotate (code, n, (int)TREE_INT_CST_LOW (rhs2)))
|
return NULL_TREE;
|
return NULL_TREE;
|
break;
|
break;
|
CASE_CONVERT:
|
CASE_CONVERT:
|
{
|
{
|
int type_size;
|
int type_size;
|
|
|
type_size = TYPE_PRECISION (gimple_expr_type (stmt));
|
type_size = TYPE_PRECISION (gimple_expr_type (stmt));
|
if (type_size % BITS_PER_UNIT != 0)
|
if (type_size % BITS_PER_UNIT != 0)
|
return NULL_TREE;
|
return NULL_TREE;
|
|
|
if (type_size / BITS_PER_UNIT < (int)(sizeof (HOST_WIDEST_INT)))
|
if (type_size / BITS_PER_UNIT < (int)(sizeof (HOST_WIDEST_INT)))
|
{
|
{
|
/* If STMT casts to a smaller type mask out the bits not
|
/* If STMT casts to a smaller type mask out the bits not
|
belonging to the target type. */
|
belonging to the target type. */
|
n->n &= ((unsigned HOST_WIDEST_INT)1 << type_size) - 1;
|
n->n &= ((unsigned HOST_WIDEST_INT)1 << type_size) - 1;
|
}
|
}
|
n->size = type_size / BITS_PER_UNIT;
|
n->size = type_size / BITS_PER_UNIT;
|
}
|
}
|
break;
|
break;
|
default:
|
default:
|
return NULL_TREE;
|
return NULL_TREE;
|
};
|
};
|
return verify_symbolic_number_p (n, stmt) ? source_expr1 : NULL;
|
return verify_symbolic_number_p (n, stmt) ? source_expr1 : NULL;
|
}
|
}
|
|
|
/* Handle binary rhs. */
|
/* Handle binary rhs. */
|
|
|
if (rhs_class == GIMPLE_BINARY_RHS)
|
if (rhs_class == GIMPLE_BINARY_RHS)
|
{
|
{
|
struct symbolic_number n1, n2;
|
struct symbolic_number n1, n2;
|
tree source_expr2;
|
tree source_expr2;
|
|
|
if (code != BIT_IOR_EXPR)
|
if (code != BIT_IOR_EXPR)
|
return NULL_TREE;
|
return NULL_TREE;
|
|
|
if (TREE_CODE (rhs2) != SSA_NAME)
|
if (TREE_CODE (rhs2) != SSA_NAME)
|
return NULL_TREE;
|
return NULL_TREE;
|
|
|
rhs2_stmt = SSA_NAME_DEF_STMT (rhs2);
|
rhs2_stmt = SSA_NAME_DEF_STMT (rhs2);
|
|
|
switch (code)
|
switch (code)
|
{
|
{
|
case BIT_IOR_EXPR:
|
case BIT_IOR_EXPR:
|
source_expr1 = find_bswap_1 (rhs1_stmt, &n1, limit - 1);
|
source_expr1 = find_bswap_1 (rhs1_stmt, &n1, limit - 1);
|
|
|
if (!source_expr1)
|
if (!source_expr1)
|
return NULL_TREE;
|
return NULL_TREE;
|
|
|
source_expr2 = find_bswap_1 (rhs2_stmt, &n2, limit - 1);
|
source_expr2 = find_bswap_1 (rhs2_stmt, &n2, limit - 1);
|
|
|
if (source_expr1 != source_expr2
|
if (source_expr1 != source_expr2
|
|| n1.size != n2.size)
|
|| n1.size != n2.size)
|
return NULL_TREE;
|
return NULL_TREE;
|
|
|
n->size = n1.size;
|
n->size = n1.size;
|
n->n = n1.n | n2.n;
|
n->n = n1.n | n2.n;
|
|
|
if (!verify_symbolic_number_p (n, stmt))
|
if (!verify_symbolic_number_p (n, stmt))
|
return NULL_TREE;
|
return NULL_TREE;
|
|
|
break;
|
break;
|
default:
|
default:
|
return NULL_TREE;
|
return NULL_TREE;
|
}
|
}
|
return source_expr1;
|
return source_expr1;
|
}
|
}
|
return NULL_TREE;
|
return NULL_TREE;
|
}
|
}
|
|
|
/* Check if STMT completes a bswap implementation consisting of ORs,
|
/* Check if STMT completes a bswap implementation consisting of ORs,
|
SHIFTs and ANDs. Return the source tree expression on which the
|
SHIFTs and ANDs. Return the source tree expression on which the
|
byte swap is performed and NULL if no bswap was found. */
|
byte swap is performed and NULL if no bswap was found. */
|
|
|
static tree
|
static tree
|
find_bswap (gimple stmt)
|
find_bswap (gimple stmt)
|
{
|
{
|
/* The number which the find_bswap result should match in order to
|
/* The number which the find_bswap result should match in order to
|
have a full byte swap. The number is shifted to the left according
|
have a full byte swap. The number is shifted to the left according
|
to the size of the symbolic number before using it. */
|
to the size of the symbolic number before using it. */
|
unsigned HOST_WIDEST_INT cmp =
|
unsigned HOST_WIDEST_INT cmp =
|
sizeof (HOST_WIDEST_INT) < 8 ? 0 :
|
sizeof (HOST_WIDEST_INT) < 8 ? 0 :
|
(unsigned HOST_WIDEST_INT)0x01020304 << 32 | 0x05060708;
|
(unsigned HOST_WIDEST_INT)0x01020304 << 32 | 0x05060708;
|
|
|
struct symbolic_number n;
|
struct symbolic_number n;
|
tree source_expr;
|
tree source_expr;
|
|
|
/* The last parameter determines the depth search limit. It usually
|
/* The last parameter determines the depth search limit. It usually
|
correlates directly to the number of bytes to be touched. We
|
correlates directly to the number of bytes to be touched. We
|
increase that number by one here in order to also cover signed ->
|
increase that number by one here in order to also cover signed ->
|
unsigned conversions of the src operand as can be seen in
|
unsigned conversions of the src operand as can be seen in
|
libgcc. */
|
libgcc. */
|
source_expr = find_bswap_1 (stmt, &n,
|
source_expr = find_bswap_1 (stmt, &n,
|
TREE_INT_CST_LOW (
|
TREE_INT_CST_LOW (
|
TYPE_SIZE_UNIT (gimple_expr_type (stmt))) + 1);
|
TYPE_SIZE_UNIT (gimple_expr_type (stmt))) + 1);
|
|
|
if (!source_expr)
|
if (!source_expr)
|
return NULL_TREE;
|
return NULL_TREE;
|
|
|
/* Zero out the extra bits of N and CMP. */
|
/* Zero out the extra bits of N and CMP. */
|
if (n.size < (int)sizeof (HOST_WIDEST_INT))
|
if (n.size < (int)sizeof (HOST_WIDEST_INT))
|
{
|
{
|
unsigned HOST_WIDEST_INT mask =
|
unsigned HOST_WIDEST_INT mask =
|
((unsigned HOST_WIDEST_INT)1 << (n.size * BITS_PER_UNIT)) - 1;
|
((unsigned HOST_WIDEST_INT)1 << (n.size * BITS_PER_UNIT)) - 1;
|
|
|
n.n &= mask;
|
n.n &= mask;
|
cmp >>= (sizeof (HOST_WIDEST_INT) - n.size) * BITS_PER_UNIT;
|
cmp >>= (sizeof (HOST_WIDEST_INT) - n.size) * BITS_PER_UNIT;
|
}
|
}
|
|
|
/* A complete byte swap should make the symbolic number to start
|
/* A complete byte swap should make the symbolic number to start
|
with the largest digit in the highest order byte. */
|
with the largest digit in the highest order byte. */
|
if (cmp != n.n)
|
if (cmp != n.n)
|
return NULL_TREE;
|
return NULL_TREE;
|
|
|
return source_expr;
|
return source_expr;
|
}
|
}
|
|
|
/* Find manual byte swap implementations and turn them into a bswap
|
/* Find manual byte swap implementations and turn them into a bswap
|
builtin invokation. */
|
builtin invokation. */
|
|
|
static unsigned int
|
static unsigned int
|
execute_optimize_bswap (void)
|
execute_optimize_bswap (void)
|
{
|
{
|
basic_block bb;
|
basic_block bb;
|
bool bswap32_p, bswap64_p;
|
bool bswap32_p, bswap64_p;
|
bool changed = false;
|
bool changed = false;
|
tree bswap32_type = NULL_TREE, bswap64_type = NULL_TREE;
|
tree bswap32_type = NULL_TREE, bswap64_type = NULL_TREE;
|
|
|
if (BITS_PER_UNIT != 8)
|
if (BITS_PER_UNIT != 8)
|
return 0;
|
return 0;
|
|
|
if (sizeof (HOST_WIDEST_INT) < 8)
|
if (sizeof (HOST_WIDEST_INT) < 8)
|
return 0;
|
return 0;
|
|
|
bswap32_p = (built_in_decls[BUILT_IN_BSWAP32]
|
bswap32_p = (built_in_decls[BUILT_IN_BSWAP32]
|
&& optab_handler (bswap_optab, SImode)->insn_code !=
|
&& optab_handler (bswap_optab, SImode)->insn_code !=
|
CODE_FOR_nothing);
|
CODE_FOR_nothing);
|
bswap64_p = (built_in_decls[BUILT_IN_BSWAP64]
|
bswap64_p = (built_in_decls[BUILT_IN_BSWAP64]
|
&& (optab_handler (bswap_optab, DImode)->insn_code !=
|
&& (optab_handler (bswap_optab, DImode)->insn_code !=
|
CODE_FOR_nothing
|
CODE_FOR_nothing
|
|| (bswap32_p && word_mode == SImode)));
|
|| (bswap32_p && word_mode == SImode)));
|
|
|
if (!bswap32_p && !bswap64_p)
|
if (!bswap32_p && !bswap64_p)
|
return 0;
|
return 0;
|
|
|
/* Determine the argument type of the builtins. The code later on
|
/* Determine the argument type of the builtins. The code later on
|
assumes that the return and argument type are the same. */
|
assumes that the return and argument type are the same. */
|
if (bswap32_p)
|
if (bswap32_p)
|
{
|
{
|
tree fndecl = built_in_decls[BUILT_IN_BSWAP32];
|
tree fndecl = built_in_decls[BUILT_IN_BSWAP32];
|
bswap32_type = TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (fndecl)));
|
bswap32_type = TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (fndecl)));
|
}
|
}
|
|
|
if (bswap64_p)
|
if (bswap64_p)
|
{
|
{
|
tree fndecl = built_in_decls[BUILT_IN_BSWAP64];
|
tree fndecl = built_in_decls[BUILT_IN_BSWAP64];
|
bswap64_type = TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (fndecl)));
|
bswap64_type = TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (fndecl)));
|
}
|
}
|
|
|
FOR_EACH_BB (bb)
|
FOR_EACH_BB (bb)
|
{
|
{
|
gimple_stmt_iterator gsi;
|
gimple_stmt_iterator gsi;
|
|
|
for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); gsi_next (&gsi))
|
for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); gsi_next (&gsi))
|
{
|
{
|
gimple stmt = gsi_stmt (gsi);
|
gimple stmt = gsi_stmt (gsi);
|
tree bswap_src, bswap_type;
|
tree bswap_src, bswap_type;
|
tree bswap_tmp;
|
tree bswap_tmp;
|
tree fndecl = NULL_TREE;
|
tree fndecl = NULL_TREE;
|
int type_size;
|
int type_size;
|
gimple call;
|
gimple call;
|
|
|
if (!is_gimple_assign (stmt)
|
if (!is_gimple_assign (stmt)
|
|| gimple_assign_rhs_code (stmt) != BIT_IOR_EXPR)
|
|| gimple_assign_rhs_code (stmt) != BIT_IOR_EXPR)
|
continue;
|
continue;
|
|
|
type_size = TYPE_PRECISION (gimple_expr_type (stmt));
|
type_size = TYPE_PRECISION (gimple_expr_type (stmt));
|
|
|
switch (type_size)
|
switch (type_size)
|
{
|
{
|
case 32:
|
case 32:
|
if (bswap32_p)
|
if (bswap32_p)
|
{
|
{
|
fndecl = built_in_decls[BUILT_IN_BSWAP32];
|
fndecl = built_in_decls[BUILT_IN_BSWAP32];
|
bswap_type = bswap32_type;
|
bswap_type = bswap32_type;
|
}
|
}
|
break;
|
break;
|
case 64:
|
case 64:
|
if (bswap64_p)
|
if (bswap64_p)
|
{
|
{
|
fndecl = built_in_decls[BUILT_IN_BSWAP64];
|
fndecl = built_in_decls[BUILT_IN_BSWAP64];
|
bswap_type = bswap64_type;
|
bswap_type = bswap64_type;
|
}
|
}
|
break;
|
break;
|
default:
|
default:
|
continue;
|
continue;
|
}
|
}
|
|
|
if (!fndecl)
|
if (!fndecl)
|
continue;
|
continue;
|
|
|
bswap_src = find_bswap (stmt);
|
bswap_src = find_bswap (stmt);
|
|
|
if (!bswap_src)
|
if (!bswap_src)
|
continue;
|
continue;
|
|
|
changed = true;
|
changed = true;
|
|
|
bswap_tmp = bswap_src;
|
bswap_tmp = bswap_src;
|
|
|
/* Convert the src expression if necessary. */
|
/* Convert the src expression if necessary. */
|
if (!useless_type_conversion_p (TREE_TYPE (bswap_tmp), bswap_type))
|
if (!useless_type_conversion_p (TREE_TYPE (bswap_tmp), bswap_type))
|
{
|
{
|
gimple convert_stmt;
|
gimple convert_stmt;
|
|
|
bswap_tmp = create_tmp_var (bswap_type, "bswapsrc");
|
bswap_tmp = create_tmp_var (bswap_type, "bswapsrc");
|
add_referenced_var (bswap_tmp);
|
add_referenced_var (bswap_tmp);
|
bswap_tmp = make_ssa_name (bswap_tmp, NULL);
|
bswap_tmp = make_ssa_name (bswap_tmp, NULL);
|
|
|
convert_stmt = gimple_build_assign_with_ops (
|
convert_stmt = gimple_build_assign_with_ops (
|
CONVERT_EXPR, bswap_tmp, bswap_src, NULL);
|
CONVERT_EXPR, bswap_tmp, bswap_src, NULL);
|
gsi_insert_before (&gsi, convert_stmt, GSI_SAME_STMT);
|
gsi_insert_before (&gsi, convert_stmt, GSI_SAME_STMT);
|
}
|
}
|
|
|
call = gimple_build_call (fndecl, 1, bswap_tmp);
|
call = gimple_build_call (fndecl, 1, bswap_tmp);
|
|
|
bswap_tmp = gimple_assign_lhs (stmt);
|
bswap_tmp = gimple_assign_lhs (stmt);
|
|
|
/* Convert the result if necessary. */
|
/* Convert the result if necessary. */
|
if (!useless_type_conversion_p (TREE_TYPE (bswap_tmp), bswap_type))
|
if (!useless_type_conversion_p (TREE_TYPE (bswap_tmp), bswap_type))
|
{
|
{
|
gimple convert_stmt;
|
gimple convert_stmt;
|
|
|
bswap_tmp = create_tmp_var (bswap_type, "bswapdst");
|
bswap_tmp = create_tmp_var (bswap_type, "bswapdst");
|
add_referenced_var (bswap_tmp);
|
add_referenced_var (bswap_tmp);
|
bswap_tmp = make_ssa_name (bswap_tmp, NULL);
|
bswap_tmp = make_ssa_name (bswap_tmp, NULL);
|
convert_stmt = gimple_build_assign_with_ops (
|
convert_stmt = gimple_build_assign_with_ops (
|
CONVERT_EXPR, gimple_assign_lhs (stmt), bswap_tmp, NULL);
|
CONVERT_EXPR, gimple_assign_lhs (stmt), bswap_tmp, NULL);
|
gsi_insert_after (&gsi, convert_stmt, GSI_SAME_STMT);
|
gsi_insert_after (&gsi, convert_stmt, GSI_SAME_STMT);
|
}
|
}
|
|
|
gimple_call_set_lhs (call, bswap_tmp);
|
gimple_call_set_lhs (call, bswap_tmp);
|
|
|
if (dump_file)
|
if (dump_file)
|
{
|
{
|
fprintf (dump_file, "%d bit bswap implementation found at: ",
|
fprintf (dump_file, "%d bit bswap implementation found at: ",
|
(int)type_size);
|
(int)type_size);
|
print_gimple_stmt (dump_file, stmt, 0, 0);
|
print_gimple_stmt (dump_file, stmt, 0, 0);
|
}
|
}
|
|
|
gsi_insert_after (&gsi, call, GSI_SAME_STMT);
|
gsi_insert_after (&gsi, call, GSI_SAME_STMT);
|
gsi_remove (&gsi, true);
|
gsi_remove (&gsi, true);
|
}
|
}
|
}
|
}
|
|
|
return (changed ? TODO_dump_func | TODO_update_ssa | TODO_verify_ssa
|
return (changed ? TODO_dump_func | TODO_update_ssa | TODO_verify_ssa
|
| TODO_verify_stmts : 0);
|
| TODO_verify_stmts : 0);
|
}
|
}
|
|
|
static bool
|
static bool
|
gate_optimize_bswap (void)
|
gate_optimize_bswap (void)
|
{
|
{
|
return flag_expensive_optimizations && optimize;
|
return flag_expensive_optimizations && optimize;
|
}
|
}
|
|
|
struct gimple_opt_pass pass_optimize_bswap =
|
struct gimple_opt_pass pass_optimize_bswap =
|
{
|
{
|
{
|
{
|
GIMPLE_PASS,
|
GIMPLE_PASS,
|
"bswap", /* name */
|
"bswap", /* name */
|
gate_optimize_bswap, /* gate */
|
gate_optimize_bswap, /* gate */
|
execute_optimize_bswap, /* execute */
|
execute_optimize_bswap, /* execute */
|
NULL, /* sub */
|
NULL, /* sub */
|
NULL, /* next */
|
NULL, /* next */
|
0, /* static_pass_number */
|
0, /* static_pass_number */
|
TV_NONE, /* tv_id */
|
TV_NONE, /* tv_id */
|
PROP_ssa, /* properties_required */
|
PROP_ssa, /* properties_required */
|
0, /* properties_provided */
|
0, /* properties_provided */
|
0, /* properties_destroyed */
|
0, /* properties_destroyed */
|
0, /* todo_flags_start */
|
0, /* todo_flags_start */
|
0 /* todo_flags_finish */
|
0 /* todo_flags_finish */
|
}
|
}
|
};
|
};
|
|
|
