tree-ssa-reassoc.c [plain text]
#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "errors.h"
#include "ggc.h"
#include "tree.h"
#include "basic-block.h"
#include "diagnostic.h"
#include "tree-inline.h"
#include "tree-flow.h"
#include "tree-gimple.h"
#include "tree-dump.h"
#include "timevar.h"
#include "tree-iterator.h"
#include "tree-pass.h"
#include "alloc-pool.h"
#include "vec.h"
#include "langhooks.h"
static struct
{
int linearized;
int constants_eliminated;
int ops_eliminated;
int rewritten;
} reassociate_stats;
typedef struct operand_entry
{
unsigned int rank;
tree op;
} *operand_entry_t;
static alloc_pool operand_entry_pool;
static unsigned int *bb_rank;
static htab_t operand_rank;
static operand_entry_t
find_operand_rank (tree e)
{
void **slot;
struct operand_entry vrd;
vrd.op = e;
slot = htab_find_slot (operand_rank, &vrd, NO_INSERT);
if (!slot)
return NULL;
return ((operand_entry_t) *slot);
}
static void
insert_operand_rank (tree e, unsigned int rank)
{
void **slot;
operand_entry_t new_pair = pool_alloc (operand_entry_pool);
new_pair->op = e;
new_pair->rank = rank;
slot = htab_find_slot (operand_rank, new_pair, INSERT);
gcc_assert (*slot == NULL);
*slot = new_pair;
}
static hashval_t
operand_entry_hash (const void *p)
{
const operand_entry_t vr = (operand_entry_t) p;
return iterative_hash_expr (vr->op, 0);
}
static int
operand_entry_eq (const void *p1, const void *p2)
{
const operand_entry_t vr1 = (operand_entry_t) p1;
const operand_entry_t vr2 = (operand_entry_t) p2;
return vr1->op == vr2->op;
}
static unsigned int
get_rank (tree e)
{
operand_entry_t vr;
if (is_gimple_min_invariant (e))
return 0;
if (TREE_CODE (e) == SSA_NAME)
{
tree stmt;
tree rhs;
unsigned int rank, maxrank;
int i;
if (TREE_CODE (SSA_NAME_VAR (e)) == PARM_DECL
&& e == default_def (SSA_NAME_VAR (e)))
return find_operand_rank (e)->rank;
stmt = SSA_NAME_DEF_STMT (e);
if (bb_for_stmt (stmt) == NULL)
return 0;
if (TREE_CODE (stmt) != MODIFY_EXPR
|| !ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS))
return bb_rank[bb_for_stmt (stmt)->index];
vr = find_operand_rank (e);
if (vr)
return vr->rank;
rank = 0;
maxrank = bb_rank[bb_for_stmt(stmt)->index];
rhs = TREE_OPERAND (stmt, 1);
if (TREE_CODE_LENGTH (TREE_CODE (rhs)) == 0)
rank = MAX (rank, get_rank (rhs));
else
{
for (i = 0;
i < TREE_CODE_LENGTH (TREE_CODE (rhs))
&& TREE_OPERAND (rhs, i)
&& rank != maxrank;
i++)
rank = MAX(rank, get_rank (TREE_OPERAND (rhs, i)));
}
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Rank for ");
print_generic_expr (dump_file, e, 0);
fprintf (dump_file, " is %d\n", (rank + 1));
}
insert_operand_rank (e, (rank + 1));
return (rank + 1);
}
return 0;
}
DEF_VEC_P(operand_entry_t);
DEF_VEC_ALLOC_P(operand_entry_t, heap);
#define INTEGER_CONST_TYPE 1 << 3
#define FLOAT_CONST_TYPE 1 << 2
#define OTHER_CONST_TYPE 1 << 1
static inline int
constant_type (tree t)
{
if (INTEGRAL_TYPE_P (TREE_TYPE (t)))
return INTEGER_CONST_TYPE;
else if (SCALAR_FLOAT_TYPE_P (TREE_TYPE (t)))
return FLOAT_CONST_TYPE;
else
return OTHER_CONST_TYPE;
}
static int
sort_by_operand_rank (const void *pa, const void *pb)
{
const operand_entry_t oea = *(const operand_entry_t *)pa;
const operand_entry_t oeb = *(const operand_entry_t *)pb;
if (oeb->rank == 0 && oea->rank == 0)
return constant_type (oeb->op) - constant_type (oea->op);
if ((oeb->rank - oea->rank == 0)
&& TREE_CODE (oea->op) == SSA_NAME
&& TREE_CODE (oeb->op) == SSA_NAME)
return SSA_NAME_VERSION (oeb->op) - SSA_NAME_VERSION (oea->op);
return oeb->rank - oea->rank;
}
static void
add_to_ops_vec (VEC(operand_entry_t, heap) **ops, tree op)
{
operand_entry_t oe = pool_alloc (operand_entry_pool);
oe->op = op;
oe->rank = get_rank (op);
VEC_safe_push (operand_entry_t, heap, *ops, oe);
}
static bool
is_reassociable_op (tree stmt, enum tree_code code)
{
if (!IS_EMPTY_STMT (stmt)
&& TREE_CODE (stmt) == MODIFY_EXPR
&& TREE_CODE (TREE_OPERAND (stmt, 1)) == code
&& has_single_use (TREE_OPERAND (stmt, 0)))
return true;
return false;
}
static tree
get_unary_op (tree name, enum tree_code opcode)
{
tree stmt = SSA_NAME_DEF_STMT (name);
tree rhs;
if (TREE_CODE (stmt) != MODIFY_EXPR)
return NULL_TREE;
rhs = TREE_OPERAND (stmt, 1);
if (TREE_CODE (rhs) == opcode)
return TREE_OPERAND (rhs, 0);
return NULL_TREE;
}
static bool
eliminate_duplicate_pair (enum tree_code opcode,
VEC (operand_entry_t, heap) **ops,
bool *all_done,
unsigned int i,
operand_entry_t curr,
operand_entry_t last)
{
if (last && last->op == curr->op)
{
switch (opcode)
{
case MAX_EXPR:
case MIN_EXPR:
case BIT_IOR_EXPR:
case BIT_AND_EXPR:
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Equivalence: ");
print_generic_expr (dump_file, curr->op, 0);
fprintf (dump_file, " [&|minmax] ");
print_generic_expr (dump_file, last->op, 0);
fprintf (dump_file, " -> ");
print_generic_stmt (dump_file, last->op, 0);
}
VEC_ordered_remove (operand_entry_t, *ops, i);
reassociate_stats.ops_eliminated ++;
return true;
case BIT_XOR_EXPR:
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Equivalence: ");
print_generic_expr (dump_file, curr->op, 0);
fprintf (dump_file, " ^ ");
print_generic_expr (dump_file, last->op, 0);
fprintf (dump_file, " -> nothing\n");
}
reassociate_stats.ops_eliminated += 2;
if (VEC_length (operand_entry_t, *ops) == 2)
{
VEC_free (operand_entry_t, heap, *ops);
*ops = NULL;
add_to_ops_vec (ops, fold_convert (TREE_TYPE (last->op),
integer_zero_node));
*all_done = true;
}
else
{
VEC_ordered_remove (operand_entry_t, *ops, i-1);
VEC_ordered_remove (operand_entry_t, *ops, i-1);
}
return true;
default:
break;
}
}
return false;
}
static bool
eliminate_plus_minus_pair (enum tree_code opcode,
VEC (operand_entry_t, heap) **ops,
unsigned int currindex,
operand_entry_t curr)
{
tree negateop;
unsigned int i;
operand_entry_t oe;
if (opcode != PLUS_EXPR || TREE_CODE (curr->op) != SSA_NAME)
return false;
negateop = get_unary_op (curr->op, NEGATE_EXPR);
if (negateop == NULL_TREE)
return false;
for (i = currindex + 1;
VEC_iterate (operand_entry_t, *ops, i, oe)
&& oe->rank >= curr->rank - 1 ;
i++)
{
if (oe->op == negateop)
{
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Equivalence: ");
print_generic_expr (dump_file, negateop, 0);
fprintf (dump_file, " + -");
print_generic_expr (dump_file, oe->op, 0);
fprintf (dump_file, " -> 0\n");
}
VEC_ordered_remove (operand_entry_t, *ops, i);
add_to_ops_vec (ops, fold_convert(TREE_TYPE (oe->op),
integer_zero_node));
VEC_ordered_remove (operand_entry_t, *ops, currindex);
reassociate_stats.ops_eliminated ++;
return true;
}
}
return false;
}
static bool
eliminate_not_pairs (enum tree_code opcode,
VEC (operand_entry_t, heap) **ops,
unsigned int currindex,
operand_entry_t curr)
{
tree notop;
unsigned int i;
operand_entry_t oe;
if ((opcode != BIT_IOR_EXPR && opcode != BIT_AND_EXPR)
|| TREE_CODE (curr->op) != SSA_NAME)
return false;
notop = get_unary_op (curr->op, BIT_NOT_EXPR);
if (notop == NULL_TREE)
return false;
for (i = currindex + 1;
VEC_iterate (operand_entry_t, *ops, i, oe)
&& oe->rank >= curr->rank - 1;
i++)
{
if (oe->op == notop)
{
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Equivalence: ");
print_generic_expr (dump_file, notop, 0);
if (opcode == BIT_AND_EXPR)
fprintf (dump_file, " & ~");
else if (opcode == BIT_IOR_EXPR)
fprintf (dump_file, " | ~");
print_generic_expr (dump_file, oe->op, 0);
if (opcode == BIT_AND_EXPR)
fprintf (dump_file, " -> 0\n");
else if (opcode == BIT_IOR_EXPR)
fprintf (dump_file, " -> -1\n");
}
if (opcode == BIT_AND_EXPR)
oe->op = fold_convert (TREE_TYPE (oe->op), integer_zero_node);
else if (opcode == BIT_IOR_EXPR)
oe->op = build_low_bits_mask (TREE_TYPE (oe->op),
TYPE_PRECISION (TREE_TYPE (oe->op)));
reassociate_stats.ops_eliminated
+= VEC_length (operand_entry_t, *ops) - 1;
VEC_free (operand_entry_t, heap, *ops);
*ops = NULL;
VEC_safe_push (operand_entry_t, heap, *ops, oe);
return true;
}
}
return false;
}
static void
eliminate_using_constants (enum tree_code opcode,
VEC(operand_entry_t, heap) **ops)
{
operand_entry_t oelast = VEC_last (operand_entry_t, *ops);
if (oelast->rank == 0 && INTEGRAL_TYPE_P (TREE_TYPE (oelast->op)))
{
switch (opcode)
{
case BIT_AND_EXPR:
if (integer_zerop (oelast->op))
{
if (VEC_length (operand_entry_t, *ops) != 1)
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Found & 0, removing all other ops\n");
reassociate_stats.ops_eliminated
+= VEC_length (operand_entry_t, *ops) - 1;
VEC_free (operand_entry_t, heap, *ops);
*ops = NULL;
VEC_safe_push (operand_entry_t, heap, *ops, oelast);
return;
}
}
else if (integer_all_onesp (oelast->op))
{
if (VEC_length (operand_entry_t, *ops) != 1)
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Found & -1, removing\n");
VEC_pop (operand_entry_t, *ops);
reassociate_stats.ops_eliminated++;
}
}
break;
case BIT_IOR_EXPR:
if (integer_all_onesp (oelast->op))
{
if (VEC_length (operand_entry_t, *ops) != 1)
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Found | -1, removing all other ops\n");
reassociate_stats.ops_eliminated
+= VEC_length (operand_entry_t, *ops) - 1;
VEC_free (operand_entry_t, heap, *ops);
*ops = NULL;
VEC_safe_push (operand_entry_t, heap, *ops, oelast);
return;
}
}
else if (integer_zerop (oelast->op))
{
if (VEC_length (operand_entry_t, *ops) != 1)
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Found | 0, removing\n");
VEC_pop (operand_entry_t, *ops);
reassociate_stats.ops_eliminated++;
}
}
break;
case MULT_EXPR:
if (integer_zerop (oelast->op))
{
if (VEC_length (operand_entry_t, *ops) != 1)
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Found * 0, removing all other ops\n");
reassociate_stats.ops_eliminated
+= VEC_length (operand_entry_t, *ops) - 1;
VEC_free (operand_entry_t, heap, *ops);
*ops = NULL;
VEC_safe_push (operand_entry_t, heap, *ops, oelast);
return;
}
}
else if (integer_onep (oelast->op))
{
if (VEC_length (operand_entry_t, *ops) != 1)
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Found * 1, removing\n");
VEC_pop (operand_entry_t, *ops);
reassociate_stats.ops_eliminated++;
return;
}
}
break;
case BIT_XOR_EXPR:
case PLUS_EXPR:
case MINUS_EXPR:
if (integer_zerop (oelast->op))
{
if (VEC_length (operand_entry_t, *ops) != 1)
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Found [|^+] 0, removing\n");
VEC_pop (operand_entry_t, *ops);
reassociate_stats.ops_eliminated++;
return;
}
}
break;
default:
break;
}
}
}
static void
optimize_ops_list (enum tree_code opcode,
VEC (operand_entry_t, heap) **ops)
{
unsigned int length = VEC_length (operand_entry_t, *ops);
unsigned int i;
operand_entry_t oe;
operand_entry_t oelast = NULL;
bool iterate = false;
if (length == 1)
return;
oelast = VEC_last (operand_entry_t, *ops);
if (oelast->rank == 0 && is_gimple_min_invariant (oelast->op))
{
operand_entry_t oelm1 = VEC_index (operand_entry_t, *ops, length - 2);
if (oelm1->rank == 0
&& is_gimple_min_invariant (oelm1->op)
&& lang_hooks.types_compatible_p (TREE_TYPE (oelm1->op),
TREE_TYPE (oelast->op)))
{
tree folded = fold_binary (opcode, TREE_TYPE (oelm1->op),
oelm1->op, oelast->op);
if (folded && is_gimple_min_invariant (folded))
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Merging constants\n");
VEC_pop (operand_entry_t, *ops);
VEC_pop (operand_entry_t, *ops);
add_to_ops_vec (ops, folded);
reassociate_stats.constants_eliminated++;
optimize_ops_list (opcode, ops);
return;
}
}
}
eliminate_using_constants (opcode, ops);
oelast = NULL;
for (i = 0; VEC_iterate (operand_entry_t, *ops, i, oe);)
{
bool done = false;
if (eliminate_not_pairs (opcode, ops, i, oe))
return;
if (eliminate_duplicate_pair (opcode, ops, &done, i, oe, oelast)
|| (!done && eliminate_plus_minus_pair (opcode, ops, i, oe)))
{
if (done)
return;
iterate = true;
oelast = NULL;
continue;
}
oelast = oe;
i++;
}
length = VEC_length (operand_entry_t, *ops);
oelast = VEC_last (operand_entry_t, *ops);
if (iterate)
optimize_ops_list (opcode, ops);
}
static bool
is_phi_for_stmt (tree stmt, tree operand)
{
tree def_stmt;
tree lhs = TREE_OPERAND (stmt, 0);
use_operand_p arg_p;
ssa_op_iter i;
if (TREE_CODE (operand) != SSA_NAME)
return false;
def_stmt = SSA_NAME_DEF_STMT (operand);
if (TREE_CODE (def_stmt) != PHI_NODE)
return false;
FOR_EACH_PHI_ARG (arg_p, def_stmt, i, SSA_OP_USE)
if (lhs == USE_FROM_PTR (arg_p))
return true;
return false;
}
static void
rewrite_expr_tree (tree stmt, unsigned int opindex,
VEC(operand_entry_t, heap) * ops)
{
tree rhs = TREE_OPERAND (stmt, 1);
operand_entry_t oe;
if (opindex + 3 == VEC_length (operand_entry_t, ops))
{
operand_entry_t oe1, oe2, oe3;
oe1 = VEC_index (operand_entry_t, ops, opindex);
oe2 = VEC_index (operand_entry_t, ops, opindex + 1);
oe3 = VEC_index (operand_entry_t, ops, opindex + 2);
if ((oe1->rank == oe2->rank
&& oe2->rank != oe3->rank)
|| (is_phi_for_stmt (stmt, oe3->op)
&& !is_phi_for_stmt (stmt, oe1->op)
&& !is_phi_for_stmt (stmt, oe2->op)))
{
struct operand_entry temp = *oe3;
oe3->op = oe1->op;
oe3->rank = oe1->rank;
oe1->op = temp.op;
oe1->rank= temp.rank;
}
}
if (opindex + 2 == VEC_length (operand_entry_t, ops))
{
operand_entry_t oe1, oe2;
oe1 = VEC_index (operand_entry_t, ops, opindex);
oe2 = VEC_index (operand_entry_t, ops, opindex + 1);
if (TREE_OPERAND (rhs, 0) != oe1->op
|| TREE_OPERAND (rhs, 1) != oe2->op)
{
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Transforming ");
print_generic_expr (dump_file, rhs, 0);
}
TREE_OPERAND (rhs, 0) = oe1->op;
TREE_OPERAND (rhs, 1) = oe2->op;
update_stmt (stmt);
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, " into ");
print_generic_stmt (dump_file, rhs, 0);
}
}
return;
}
gcc_assert (opindex + 2 < VEC_length (operand_entry_t, ops));
oe = VEC_index (operand_entry_t, ops, opindex);
if (oe->op != TREE_OPERAND (rhs, 1))
{
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Transforming ");
print_generic_expr (dump_file, rhs, 0);
}
TREE_OPERAND (rhs, 1) = oe->op;
update_stmt (stmt);
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, " into ");
print_generic_stmt (dump_file, rhs, 0);
}
}
rewrite_expr_tree (SSA_NAME_DEF_STMT (TREE_OPERAND (rhs, 0)),
opindex + 1, ops);
}
static void
linearize_expr (tree stmt)
{
block_stmt_iterator bsinow, bsirhs;
tree rhs = TREE_OPERAND (stmt, 1);
enum tree_code rhscode = TREE_CODE (rhs);
tree binrhs = SSA_NAME_DEF_STMT (TREE_OPERAND (rhs, 1));
tree binlhs = SSA_NAME_DEF_STMT (TREE_OPERAND (rhs, 0));
tree newbinrhs = NULL_TREE;
gcc_assert (is_reassociable_op (binlhs, TREE_CODE (rhs))
&& is_reassociable_op (binrhs, TREE_CODE (rhs)));
bsinow = bsi_for_stmt (stmt);
bsirhs = bsi_for_stmt (binrhs);
bsi_move_before (&bsirhs, &bsinow);
TREE_OPERAND (rhs, 1) = TREE_OPERAND (TREE_OPERAND (binrhs, 1), 0);
if (TREE_CODE (TREE_OPERAND (rhs, 1)) == SSA_NAME)
newbinrhs = SSA_NAME_DEF_STMT (TREE_OPERAND (rhs, 1));
TREE_OPERAND (TREE_OPERAND (binrhs, 1), 0) = TREE_OPERAND (binlhs, 0);
TREE_OPERAND (rhs, 0) = TREE_OPERAND (binrhs, 0);
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Linearized: ");
print_generic_stmt (dump_file, rhs, 0);
}
reassociate_stats.linearized++;
update_stmt (binrhs);
update_stmt (binlhs);
update_stmt (stmt);
TREE_VISITED (binrhs) = 1;
TREE_VISITED (binlhs) = 1;
TREE_VISITED (stmt) = 1;
if (newbinrhs && is_reassociable_op (newbinrhs, rhscode))
linearize_expr (stmt);
}
static tree
get_single_immediate_use (tree lhs)
{
use_operand_p immuse;
tree immusestmt;
if (TREE_CODE (lhs) == SSA_NAME
&& single_imm_use (lhs, &immuse, &immusestmt))
{
if (TREE_CODE (immusestmt) == RETURN_EXPR)
immusestmt = TREE_OPERAND (immusestmt, 0);
if (TREE_CODE (immusestmt) == MODIFY_EXPR)
return immusestmt;
}
return NULL_TREE;
}
static VEC(tree, heap) *broken_up_subtracts;
static tree
negate_value (tree tonegate, block_stmt_iterator *bsi)
{
tree negatedef = tonegate;
tree resultofnegate;
if (TREE_CODE (tonegate) == SSA_NAME)
negatedef = SSA_NAME_DEF_STMT (tonegate);
if (TREE_CODE (tonegate) == SSA_NAME
&& TREE_CODE (negatedef) == MODIFY_EXPR
&& TREE_CODE (TREE_OPERAND (negatedef, 0)) == SSA_NAME
&& has_single_use (TREE_OPERAND (negatedef, 0))
&& TREE_CODE (TREE_OPERAND (negatedef, 1)) == PLUS_EXPR)
{
block_stmt_iterator bsi;
tree binop = TREE_OPERAND (negatedef, 1);
bsi = bsi_for_stmt (negatedef);
TREE_OPERAND (binop, 0) = negate_value (TREE_OPERAND (binop, 0),
&bsi);
bsi = bsi_for_stmt (negatedef);
TREE_OPERAND (binop, 1) = negate_value (TREE_OPERAND (binop, 1),
&bsi);
update_stmt (negatedef);
return TREE_OPERAND (negatedef, 0);
}
tonegate = fold_build1 (NEGATE_EXPR, TREE_TYPE (tonegate), tonegate);
resultofnegate = force_gimple_operand_bsi (bsi, tonegate, true,
NULL_TREE);
VEC_safe_push (tree, heap, broken_up_subtracts, resultofnegate);
return resultofnegate;
}
static bool
should_break_up_subtract (tree stmt)
{
tree lhs = TREE_OPERAND (stmt, 0);
tree rhs = TREE_OPERAND (stmt, 1);
tree binlhs = TREE_OPERAND (rhs, 0);
tree binrhs = TREE_OPERAND (rhs, 1);
tree immusestmt;
if (TREE_CODE (binlhs) == SSA_NAME
&& is_reassociable_op (SSA_NAME_DEF_STMT (binlhs), PLUS_EXPR))
return true;
if (TREE_CODE (binrhs) == SSA_NAME
&& is_reassociable_op (SSA_NAME_DEF_STMT (binrhs), PLUS_EXPR))
return true;
if (TREE_CODE (lhs) == SSA_NAME
&& (immusestmt = get_single_immediate_use (lhs))
&& TREE_CODE (TREE_OPERAND (immusestmt, 1)) == PLUS_EXPR)
return true;
return false;
}
static void
break_up_subtract (tree stmt, block_stmt_iterator *bsi)
{
tree rhs = TREE_OPERAND (stmt, 1);
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Breaking up subtract ");
print_generic_stmt (dump_file, stmt, 0);
}
TREE_SET_CODE (TREE_OPERAND (stmt, 1), PLUS_EXPR);
TREE_OPERAND (rhs, 1) = negate_value (TREE_OPERAND (rhs, 1), bsi);
update_stmt (stmt);
}
static void
linearize_expr_tree (VEC(operand_entry_t, heap) **ops, tree stmt)
{
block_stmt_iterator bsinow, bsilhs;
tree rhs = TREE_OPERAND (stmt, 1);
tree binrhs = TREE_OPERAND (rhs, 1);
tree binlhs = TREE_OPERAND (rhs, 0);
tree binlhsdef, binrhsdef;
bool binlhsisreassoc = false;
bool binrhsisreassoc = false;
enum tree_code rhscode = TREE_CODE (rhs);
TREE_VISITED (stmt) = 1;
if (TREE_CODE (binlhs) == SSA_NAME)
{
binlhsdef = SSA_NAME_DEF_STMT (binlhs);
binlhsisreassoc = is_reassociable_op (binlhsdef, rhscode);
}
if (TREE_CODE (binrhs) == SSA_NAME)
{
binrhsdef = SSA_NAME_DEF_STMT (binrhs);
binrhsisreassoc = is_reassociable_op (binrhsdef, rhscode);
}
if (!binlhsisreassoc)
{
tree temp;
if (!binrhsisreassoc)
{
add_to_ops_vec (ops, binrhs);
add_to_ops_vec (ops, binlhs);
return;
}
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "swapping operands of ");
print_generic_expr (dump_file, stmt, 0);
}
swap_tree_operands (stmt, &TREE_OPERAND (rhs, 0),
&TREE_OPERAND (rhs, 1));
update_stmt (stmt);
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, " is now ");
print_generic_stmt (dump_file, stmt, 0);
}
temp = binlhs;
binlhs = binrhs;
binrhs = temp;
}
else if (binrhsisreassoc)
{
linearize_expr (stmt);
gcc_assert (rhs == TREE_OPERAND (stmt, 1));
binlhs = TREE_OPERAND (rhs, 0);
binrhs = TREE_OPERAND (rhs, 1);
}
gcc_assert (TREE_CODE (binrhs) != SSA_NAME
|| !is_reassociable_op (SSA_NAME_DEF_STMT (binrhs), rhscode));
bsinow = bsi_for_stmt (stmt);
bsilhs = bsi_for_stmt (SSA_NAME_DEF_STMT (binlhs));
bsi_move_before (&bsilhs, &bsinow);
linearize_expr_tree (ops, SSA_NAME_DEF_STMT (binlhs));
add_to_ops_vec (ops, binrhs);
}
static void
repropagate_negates (void)
{
unsigned int i = 0;
tree negate;
for (i = 0; VEC_iterate (tree, broken_up_subtracts, i, negate); i++)
{
tree user = get_single_immediate_use (negate);
if (user
&& TREE_CODE (user) == MODIFY_EXPR
&& TREE_CODE (TREE_OPERAND (user, 1)) == PLUS_EXPR)
{
tree rhs = TREE_OPERAND (user, 1);
if (TREE_OPERAND (TREE_OPERAND (user, 1), 0) == negate)
{
tree temp = TREE_OPERAND (rhs, 0);
TREE_OPERAND (rhs, 0) = TREE_OPERAND (rhs, 1);
TREE_OPERAND (rhs, 1) = temp;
}
if (TREE_OPERAND (TREE_OPERAND (user, 1), 1) == negate)
{
TREE_SET_CODE (rhs, MINUS_EXPR);
TREE_OPERAND (rhs, 1) = get_unary_op (negate, NEGATE_EXPR);
update_stmt (user);
}
}
}
}
static void
break_up_subtract_bb (basic_block bb)
{
block_stmt_iterator bsi;
basic_block son;
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
{
tree stmt = bsi_stmt (bsi);
if (TREE_CODE (stmt) == MODIFY_EXPR)
{
tree lhs = TREE_OPERAND (stmt, 0);
tree rhs = TREE_OPERAND (stmt, 1);
TREE_VISITED (stmt) = 0;
if ((!INTEGRAL_TYPE_P (TREE_TYPE (lhs))
|| !INTEGRAL_TYPE_P (TREE_TYPE (rhs)))
&& (!SCALAR_FLOAT_TYPE_P (TREE_TYPE (rhs))
|| !SCALAR_FLOAT_TYPE_P (TREE_TYPE(lhs))
|| !flag_unsafe_math_optimizations))
continue;
if (TREE_CODE (rhs) == MINUS_EXPR)
if (should_break_up_subtract (stmt))
break_up_subtract (stmt, &bsi);
}
}
for (son = first_dom_son (CDI_DOMINATORS, bb);
son;
son = next_dom_son (CDI_DOMINATORS, son))
break_up_subtract_bb (son);
}
static void
reassociate_bb (basic_block bb)
{
block_stmt_iterator bsi;
basic_block son;
for (bsi = bsi_last (bb); !bsi_end_p (bsi); bsi_prev (&bsi))
{
tree stmt = bsi_stmt (bsi);
if (TREE_CODE (stmt) == MODIFY_EXPR)
{
tree lhs = TREE_OPERAND (stmt, 0);
tree rhs = TREE_OPERAND (stmt, 1);
if (TREE_VISITED (stmt))
continue;
if ((!INTEGRAL_TYPE_P (TREE_TYPE (lhs))
|| !INTEGRAL_TYPE_P (TREE_TYPE (rhs)))
&& (!SCALAR_FLOAT_TYPE_P (TREE_TYPE (rhs))
|| !SCALAR_FLOAT_TYPE_P (TREE_TYPE(lhs))
|| !flag_unsafe_math_optimizations))
continue;
if (associative_tree_code (TREE_CODE (rhs)))
{
VEC(operand_entry_t, heap) *ops = NULL;
if (TREE_CODE (lhs) == SSA_NAME && has_zero_uses (lhs))
continue;
TREE_VISITED (stmt) = 1;
linearize_expr_tree (&ops, stmt);
qsort (VEC_address (operand_entry_t, ops),
VEC_length (operand_entry_t, ops),
sizeof (operand_entry_t),
sort_by_operand_rank);
optimize_ops_list (TREE_CODE (rhs), &ops);
if (VEC_length (operand_entry_t, ops) == 1)
{
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Transforming ");
print_generic_expr (dump_file, rhs, 0);
}
TREE_OPERAND (stmt, 1) = VEC_last (operand_entry_t, ops)->op;
update_stmt (stmt);
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, " into ");
print_generic_stmt (dump_file,
TREE_OPERAND (stmt, 1), 0);
}
}
else
{
rewrite_expr_tree (stmt, 0, ops);
}
VEC_free (operand_entry_t, heap, ops);
}
}
}
for (son = first_dom_son (CDI_POST_DOMINATORS, bb);
son;
son = next_dom_son (CDI_POST_DOMINATORS, son))
reassociate_bb (son);
}
void dump_ops_vector (FILE *file, VEC (operand_entry_t, heap) *ops);
void debug_ops_vector (VEC (operand_entry_t, heap) *ops);
void
dump_ops_vector (FILE *file, VEC (operand_entry_t, heap) *ops)
{
operand_entry_t oe;
unsigned int i;
for (i = 0; VEC_iterate (operand_entry_t, ops, i, oe); i++)
{
fprintf (file, "Op %d -> rank: %d, tree: ", i, oe->rank);
print_generic_stmt (file, oe->op, 0);
}
}
void
debug_ops_vector (VEC (operand_entry_t, heap) *ops)
{
dump_ops_vector (stderr, ops);
}
static void
do_reassoc (void)
{
break_up_subtract_bb (ENTRY_BLOCK_PTR);
reassociate_bb (EXIT_BLOCK_PTR);
}
static void
init_reassoc (void)
{
int i;
unsigned int rank = 2;
tree param;
int *bbs = XNEWVEC (int, last_basic_block + 1);
memset (&reassociate_stats, 0, sizeof (reassociate_stats));
operand_entry_pool = create_alloc_pool ("operand entry pool",
sizeof (struct operand_entry), 30);
pre_and_rev_post_order_compute (NULL, bbs, false);
bb_rank = XCNEWVEC (unsigned int, last_basic_block + 1);
operand_rank = htab_create (511, operand_entry_hash,
operand_entry_eq, 0);
for (param = DECL_ARGUMENTS (current_function_decl);
param;
param = TREE_CHAIN (param))
{
if (default_def (param) != NULL)
{
tree def = default_def (param);
insert_operand_rank (def, ++rank);
}
}
if (cfun->static_chain_decl != NULL)
{
tree def = default_def (cfun->static_chain_decl);
if (def != NULL)
insert_operand_rank (def, ++rank);
}
for (i = 0; i < n_basic_blocks - NUM_FIXED_BLOCKS; i++)
bb_rank[bbs[i]] = ++rank << 16;
free (bbs);
calculate_dominance_info (CDI_DOMINATORS);
calculate_dominance_info (CDI_POST_DOMINATORS);
broken_up_subtracts = NULL;
}
static void
fini_reassoc (void)
{
if (dump_file && (dump_flags & TDF_STATS))
{
fprintf (dump_file, "Reassociation stats:\n");
fprintf (dump_file, "Linearized: %d\n",
reassociate_stats.linearized);
fprintf (dump_file, "Constants eliminated: %d\n",
reassociate_stats.constants_eliminated);
fprintf (dump_file, "Ops eliminated: %d\n",
reassociate_stats.ops_eliminated);
fprintf (dump_file, "Statements rewritten: %d\n",
reassociate_stats.rewritten);
}
htab_delete (operand_rank);
free_alloc_pool (operand_entry_pool);
free (bb_rank);
VEC_free (tree, heap, broken_up_subtracts);
free_dominance_info (CDI_POST_DOMINATORS);
}
static unsigned int
execute_reassoc (void)
{
init_reassoc ();
do_reassoc ();
repropagate_negates ();
fini_reassoc ();
return 0;
}
struct tree_opt_pass pass_reassoc =
{
"reassoc",
NULL,
execute_reassoc,
NULL,
NULL,
0,
TV_TREE_REASSOC,
PROP_cfg | PROP_ssa | PROP_alias,
0,
0,
0,
TODO_dump_func | TODO_ggc_collect | TODO_verify_ssa,
0
};