#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.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 "fibheap.h"
#include "hashtab.h"
#include "tree-iterator.h"
#include "real.h"
#include "alloc-pool.h"
#include "tree-pass.h"
#include "flags.h"
#include "bitmap.h"
#include "langhooks.h"
#include "cfgloop.h"
static bool in_fre = false;
typedef struct value_set_node
{
tree expr;
struct value_set_node *next;
} *value_set_node_t;
typedef struct value_set
{
value_set_node_t head;
value_set_node_t tail;
size_t length;
bool indexed;
bitmap values;
} *value_set_t;
typedef struct bitmap_set
{
bitmap expressions;
bitmap values;
} *bitmap_set_t;
typedef struct bb_value_sets
{
value_set_t exp_gen;
bitmap_set_t phi_gen;
bitmap_set_t tmp_gen;
bitmap_set_t avail_out;
value_set_t antic_in;
bitmap_set_t new_sets;
bitmap rvuse_in;
bitmap rvuse_out;
bitmap rvuse_gen;
bitmap rvuse_kill;
value_set_t antic_safe_loads;
} *bb_value_sets_t;
#define EXP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->exp_gen
#define PHI_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->phi_gen
#define TMP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->tmp_gen
#define AVAIL_OUT(BB) ((bb_value_sets_t) ((BB)->aux))->avail_out
#define ANTIC_IN(BB) ((bb_value_sets_t) ((BB)->aux))->antic_in
#define RVUSE_IN(BB) ((bb_value_sets_t) ((BB)->aux))->rvuse_in
#define RVUSE_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->rvuse_gen
#define RVUSE_KILL(BB) ((bb_value_sets_t) ((BB)->aux))->rvuse_kill
#define RVUSE_OUT(BB) ((bb_value_sets_t) ((BB)->aux))->rvuse_out
#define NEW_SETS(BB) ((bb_value_sets_t) ((BB)->aux))->new_sets
#define ANTIC_SAFE_LOADS(BB) ((bb_value_sets_t) ((BB)->aux))->antic_safe_loads
static struct
{
int eliminations;
int insertions;
int phis;
int constified;
} pre_stats;
static tree bitmap_find_leader (bitmap_set_t, tree);
static tree find_leader (value_set_t, tree);
static void value_insert_into_set (value_set_t, tree);
static void bitmap_value_insert_into_set (bitmap_set_t, tree);
static void bitmap_value_replace_in_set (bitmap_set_t, tree);
static void insert_into_set (value_set_t, tree);
static void bitmap_set_copy (bitmap_set_t, bitmap_set_t);
static bool bitmap_set_contains_value (bitmap_set_t, tree);
static bitmap_set_t bitmap_set_new (void);
static value_set_t set_new (bool);
static bool is_undefined_value (tree);
static tree create_expression_by_pieces (basic_block, tree, tree);
static tree find_or_generate_expression (basic_block, tree, tree);
static alloc_pool value_set_pool;
static alloc_pool bitmap_set_pool;
static alloc_pool value_set_node_pool;
static alloc_pool binary_node_pool;
static alloc_pool unary_node_pool;
static alloc_pool reference_node_pool;
static alloc_pool comparison_node_pool;
static alloc_pool expression_node_pool;
static alloc_pool list_node_pool;
static alloc_pool modify_expr_node_pool;
static bitmap_obstack grand_bitmap_obstack;
static tree pretemp;
static tree storetemp;
static tree mergephitemp;
static tree prephitemp;
static bitmap need_eh_cleanup;
static htab_t phi_translate_table;
typedef struct expr_pred_trans_d
{
tree e;
basic_block pred;
VEC (tree, gc) *vuses;
tree v;
hashval_t hashcode;
} *expr_pred_trans_t;
static hashval_t
expr_pred_trans_hash (const void *p)
{
const expr_pred_trans_t ve = (expr_pred_trans_t) p;
return ve->hashcode;
}
static int
expr_pred_trans_eq (const void *p1, const void *p2)
{
const expr_pred_trans_t ve1 = (expr_pred_trans_t) p1;
const expr_pred_trans_t ve2 = (expr_pred_trans_t) p2;
basic_block b1 = ve1->pred;
basic_block b2 = ve2->pred;
int i;
tree vuse1;
if (b1 != b2)
return false;
if (!expressions_equal_p (ve1->e, ve2->e))
return false;
if (ve1->vuses == ve2->vuses)
return true;
if (VEC_length (tree, ve1->vuses) != VEC_length (tree, ve2->vuses))
return false;
for (i = 0; VEC_iterate (tree, ve1->vuses, i, vuse1); i++)
{
if (VEC_index (tree, ve2->vuses, i) != vuse1)
return false;
}
return true;
}
static inline tree
phi_trans_lookup (tree e, basic_block pred, VEC (tree, gc) *vuses)
{
void **slot;
struct expr_pred_trans_d ept;
ept.e = e;
ept.pred = pred;
ept.vuses = vuses;
ept.hashcode = vn_compute (e, (unsigned long) pred);
slot = htab_find_slot_with_hash (phi_translate_table, &ept, ept.hashcode,
NO_INSERT);
if (!slot)
return NULL;
else
return ((expr_pred_trans_t) *slot)->v;
}
static inline void
phi_trans_add (tree e, tree v, basic_block pred, VEC (tree, gc) *vuses)
{
void **slot;
expr_pred_trans_t new_pair = XNEW (struct expr_pred_trans_d);
new_pair->e = e;
new_pair->pred = pred;
new_pair->vuses = vuses;
new_pair->v = v;
new_pair->hashcode = vn_compute (e, (unsigned long) pred);
slot = htab_find_slot_with_hash (phi_translate_table, new_pair,
new_pair->hashcode, INSERT);
if (*slot)
free (*slot);
*slot = (void *) new_pair;
}
void
add_to_value (tree v, tree e)
{
if (is_gimple_min_invariant (v))
return;
if (VALUE_HANDLE_EXPR_SET (v) == NULL)
VALUE_HANDLE_EXPR_SET (v) = set_new (false);
insert_into_set (VALUE_HANDLE_EXPR_SET (v), e);
}
static inline bool
value_exists_in_set_bitmap (value_set_t set, tree v)
{
if (!set->values)
return false;
return bitmap_bit_p (set->values, VALUE_HANDLE_ID (v));
}
static void
value_remove_from_set_bitmap (value_set_t set, tree v)
{
gcc_assert (set->indexed);
if (!set->values)
return;
bitmap_clear_bit (set->values, VALUE_HANDLE_ID (v));
}
static inline void
value_insert_into_set_bitmap (value_set_t set, tree v)
{
gcc_assert (set->indexed);
if (set->values == NULL)
set->values = BITMAP_ALLOC (&grand_bitmap_obstack);
bitmap_set_bit (set->values, VALUE_HANDLE_ID (v));
}
static bitmap_set_t
bitmap_set_new (void)
{
bitmap_set_t ret = (bitmap_set_t) pool_alloc (bitmap_set_pool);
ret->expressions = BITMAP_ALLOC (&grand_bitmap_obstack);
ret->values = BITMAP_ALLOC (&grand_bitmap_obstack);
return ret;
}
static value_set_t
set_new (bool indexed)
{
value_set_t ret;
ret = (value_set_t) pool_alloc (value_set_pool);
ret->head = ret->tail = NULL;
ret->length = 0;
ret->indexed = indexed;
ret->values = NULL;
return ret;
}
static void
bitmap_insert_into_set (bitmap_set_t set, tree expr)
{
tree val;
gcc_assert (TREE_CODE (expr) == SSA_NAME);
val = get_value_handle (expr);
gcc_assert (val);
if (!is_gimple_min_invariant (val))
{
bitmap_set_bit (set->values, VALUE_HANDLE_ID (val));
bitmap_set_bit (set->expressions, SSA_NAME_VERSION (expr));
}
}
static void
insert_into_set (value_set_t set, tree expr)
{
value_set_node_t newnode = (value_set_node_t) pool_alloc (value_set_node_pool);
tree val = get_value_handle (expr);
gcc_assert (val);
if (is_gimple_min_invariant (val))
return;
if (set->indexed)
value_insert_into_set_bitmap (set, val);
newnode->next = NULL;
newnode->expr = expr;
set->length ++;
if (set->head == NULL)
{
set->head = set->tail = newnode;
}
else
{
set->tail->next = newnode;
set->tail = newnode;
}
}
static void
bitmap_set_copy (bitmap_set_t dest, bitmap_set_t orig)
{
bitmap_copy (dest->expressions, orig->expressions);
bitmap_copy (dest->values, orig->values);
}
static void
bitmap_set_and (bitmap_set_t dest, bitmap_set_t orig)
{
bitmap_iterator bi;
unsigned int i;
bitmap temp = BITMAP_ALLOC (&grand_bitmap_obstack);
bitmap_and_into (dest->values, orig->values);
bitmap_copy (temp, dest->expressions);
EXECUTE_IF_SET_IN_BITMAP (temp, 0, i, bi)
{
tree name = ssa_name (i);
tree val = get_value_handle (name);
if (!bitmap_bit_p (dest->values, VALUE_HANDLE_ID (val)))
bitmap_clear_bit (dest->expressions, i);
}
BITMAP_FREE (temp);
}
static void
bitmap_set_and_compl (bitmap_set_t dest, bitmap_set_t orig)
{
bitmap_iterator bi;
unsigned int i;
bitmap temp = BITMAP_ALLOC (&grand_bitmap_obstack);
bitmap_and_compl_into (dest->values, orig->values);
bitmap_copy (temp, dest->expressions);
EXECUTE_IF_SET_IN_BITMAP (temp, 0, i, bi)
{
tree name = ssa_name (i);
tree val = get_value_handle (name);
if (!bitmap_bit_p (dest->values, VALUE_HANDLE_ID (val)))
bitmap_clear_bit (dest->expressions, i);
}
BITMAP_FREE (temp);
}
static bool
bitmap_set_empty_p (bitmap_set_t set)
{
return bitmap_empty_p (set->values);
}
static void
set_copy (value_set_t dest, value_set_t orig)
{
value_set_node_t node;
if (!orig || !orig->head)
return;
for (node = orig->head;
node;
node = node->next)
{
insert_into_set (dest, node->expr);
}
}
static void
set_remove (value_set_t set, tree expr)
{
value_set_node_t node, prev;
value_remove_from_set_bitmap (set, get_value_handle (expr));
set->length--;
prev = NULL;
for (node = set->head;
node != NULL;
prev = node, node = node->next)
{
if (node->expr == expr)
{
if (prev == NULL)
set->head = node->next;
else
prev->next= node->next;
if (node == set->tail)
set->tail = prev;
pool_free (value_set_node_pool, node);
return;
}
}
}
static bool
set_contains_value (value_set_t set, tree val)
{
if (is_gimple_min_invariant (val))
return true;
if (!set || set->length == 0)
return false;
return value_exists_in_set_bitmap (set, val);
}
static bool
bitmap_set_contains (bitmap_set_t set, tree expr)
{
if (is_gimple_min_invariant (get_value_handle (expr)))
return true;
if (TREE_CODE (expr) != SSA_NAME)
return false;
return bitmap_bit_p (set->expressions, SSA_NAME_VERSION (expr));
}
static bool
bitmap_set_contains_value (bitmap_set_t set, tree val)
{
if (is_gimple_min_invariant (val))
return true;
return bitmap_bit_p (set->values, VALUE_HANDLE_ID (val));
}
static void
bitmap_set_replace_value (bitmap_set_t set, tree lookfor, tree expr)
{
value_set_t exprset;
value_set_node_t node;
if (is_gimple_min_invariant (lookfor))
return;
if (!bitmap_set_contains_value (set, lookfor))
return;
exprset = VALUE_HANDLE_EXPR_SET (lookfor);
for (node = exprset->head; node; node = node->next)
{
if (TREE_CODE (node->expr) == SSA_NAME)
{
if (bitmap_bit_p (set->expressions, SSA_NAME_VERSION (node->expr)))
{
bitmap_clear_bit (set->expressions, SSA_NAME_VERSION (node->expr));
bitmap_set_bit (set->expressions, SSA_NAME_VERSION (expr));
return;
}
}
}
}
static value_set_t
bitmap_set_subtract_from_value_set (value_set_t a, bitmap_set_t b,
bool indexed)
{
value_set_t ret = set_new (indexed);
value_set_node_t node;
for (node = a->head;
node;
node = node->next)
{
if (!bitmap_set_contains (b, node->expr))
insert_into_set (ret, node->expr);
}
return ret;
}
static bool
set_equal (value_set_t a, value_set_t b)
{
value_set_node_t node;
if (a->length != b->length)
return false;
for (node = a->head;
node;
node = node->next)
{
if (!set_contains_value (b, get_value_handle (node->expr)))
return false;
}
return true;
}
static void
bitmap_value_replace_in_set (bitmap_set_t set, tree expr)
{
tree val = get_value_handle (expr);
if (bitmap_set_contains_value (set, val))
bitmap_set_replace_value (set, val, expr);
else
bitmap_insert_into_set (set, expr);
}
static void
bitmap_value_insert_into_set (bitmap_set_t set, tree expr)
{
tree val = get_value_handle (expr);
if (is_gimple_min_invariant (val))
return;
if (!bitmap_set_contains_value (set, val))
bitmap_insert_into_set (set, expr);
}
static void
value_insert_into_set (value_set_t set, tree expr)
{
tree val = get_value_handle (expr);
if (is_gimple_min_invariant (val))
return;
if (!set_contains_value (set, val))
insert_into_set (set, expr);
}
static void
bitmap_print_value_set (FILE *outfile, bitmap_set_t set,
const char *setname, int blockindex)
{
fprintf (outfile, "%s[%d] := { ", setname, blockindex);
if (set)
{
bool first = true;
unsigned i;
bitmap_iterator bi;
EXECUTE_IF_SET_IN_BITMAP (set->expressions, 0, i, bi)
{
if (!first)
fprintf (outfile, ", ");
first = false;
print_generic_expr (outfile, ssa_name (i), 0);
fprintf (outfile, " (");
print_generic_expr (outfile, get_value_handle (ssa_name (i)), 0);
fprintf (outfile, ") ");
}
}
fprintf (outfile, " }\n");
}
static void
print_value_set (FILE *outfile, value_set_t set,
const char *setname, int blockindex)
{
value_set_node_t node;
fprintf (outfile, "%s[%d] := { ", setname, blockindex);
if (set)
{
for (node = set->head;
node;
node = node->next)
{
print_generic_expr (outfile, node->expr, 0);
fprintf (outfile, " (");
print_generic_expr (outfile, get_value_handle (node->expr), 0);
fprintf (outfile, ") ");
if (node->next)
fprintf (outfile, ", ");
}
}
fprintf (outfile, " }\n");
}
void
print_value_expressions (FILE *outfile, tree val)
{
if (VALUE_HANDLE_EXPR_SET (val))
{
char s[10];
sprintf (s, "VH.%04d", VALUE_HANDLE_ID (val));
print_value_set (outfile, VALUE_HANDLE_EXPR_SET (val), s, 0);
}
}
void
debug_value_expressions (tree val)
{
print_value_expressions (stderr, val);
}
void debug_value_set (value_set_t, const char *, int);
void
debug_value_set (value_set_t set, const char *setname, int blockindex)
{
print_value_set (stderr, set, setname, blockindex);
}
static tree
fully_constant_expression (tree t)
{
tree folded;
folded = fold (t);
if (folded && is_gimple_min_invariant (folded))
return folded;
return t;
}
static tree
pool_copy_list (tree list)
{
tree head;
tree prev, next;
if (list == 0)
return 0;
head = (tree) pool_alloc (list_node_pool);
memcpy (head, list, tree_size (list));
prev = head;
next = TREE_CHAIN (list);
while (next)
{
TREE_CHAIN (prev) = (tree) pool_alloc (list_node_pool);
memcpy (TREE_CHAIN (prev), next, tree_size (next));
prev = TREE_CHAIN (prev);
next = TREE_CHAIN (next);
}
return head;
}
static VEC(tree, gc) *
translate_vuses_through_block (VEC (tree, gc) *vuses, basic_block block)
{
tree oldvuse;
VEC(tree, gc) *result = NULL;
int i;
for (i = 0; VEC_iterate (tree, vuses, i, oldvuse); i++)
{
tree phi = SSA_NAME_DEF_STMT (oldvuse);
if (TREE_CODE (phi) == PHI_NODE)
{
edge e = find_edge (block, bb_for_stmt (phi));
if (e)
{
tree def = PHI_ARG_DEF (phi, e->dest_idx);
if (def != oldvuse)
{
if (!result)
result = VEC_copy (tree, gc, vuses);
VEC_replace (tree, result, i, def);
}
}
}
}
if (result)
{
sort_vuses (result);
return result;
}
return vuses;
}
static tree
phi_translate (tree expr, value_set_t set, basic_block pred,
basic_block phiblock)
{
tree phitrans = NULL;
tree oldexpr = expr;
if (expr == NULL)
return NULL;
if (is_gimple_min_invariant (expr))
return expr;
if (EXPR_P (expr))
{
tree vh;
vh = get_value_handle (expr);
if (vh && TREE_CODE (vh) == VALUE_HANDLE)
phitrans = phi_trans_lookup (expr, pred, VALUE_HANDLE_VUSES (vh));
else
phitrans = phi_trans_lookup (expr, pred, NULL);
}
else
phitrans = phi_trans_lookup (expr, pred, NULL);
if (phitrans)
return phitrans;
switch (TREE_CODE_CLASS (TREE_CODE (expr)))
{
case tcc_expression:
{
if (TREE_CODE (expr) != CALL_EXPR)
return NULL;
else
{
tree oldop0 = TREE_OPERAND (expr, 0);
tree oldarglist = TREE_OPERAND (expr, 1);
tree oldop2 = TREE_OPERAND (expr, 2);
tree newop0;
tree newarglist;
tree newop2 = NULL;
tree oldwalker;
tree newwalker;
tree newexpr;
tree vh = get_value_handle (expr);
bool listchanged = false;
VEC (tree, gc) *vuses = VALUE_HANDLE_VUSES (vh);
VEC (tree, gc) *tvuses;
newop0 = phi_translate (find_leader (set, oldop0),
set, pred, phiblock);
if (newop0 == NULL)
return NULL;
if (oldop2)
{
newop2 = phi_translate (find_leader (set, oldop2),
set, pred, phiblock);
if (newop2 == NULL)
return NULL;
}
newarglist = pool_copy_list (oldarglist);
for (oldwalker = oldarglist, newwalker = newarglist;
oldwalker && newwalker;
oldwalker = TREE_CHAIN (oldwalker),
newwalker = TREE_CHAIN (newwalker))
{
tree oldval = TREE_VALUE (oldwalker);
tree newval;
if (oldval)
{
if (AGGREGATE_TYPE_P (TREE_TYPE (oldval)))
return NULL;
newval = phi_translate (find_leader (set, oldval),
set, pred, phiblock);
if (newval == NULL)
return NULL;
if (newval != oldval)
{
listchanged = true;
TREE_VALUE (newwalker) = get_value_handle (newval);
}
}
}
if (listchanged)
vn_lookup_or_add (newarglist, NULL);
tvuses = translate_vuses_through_block (vuses, pred);
if (listchanged || (newop0 != oldop0) || (oldop2 != newop2)
|| vuses != tvuses)
{
newexpr = (tree) pool_alloc (expression_node_pool);
memcpy (newexpr, expr, tree_size (expr));
TREE_OPERAND (newexpr, 0) = newop0 == oldop0 ? oldop0 : get_value_handle (newop0);
TREE_OPERAND (newexpr, 1) = listchanged ? newarglist : oldarglist;
TREE_OPERAND (newexpr, 2) = newop2 == oldop2 ? oldop2 : get_value_handle (newop2);
newexpr->common.ann = NULL;
vn_lookup_or_add_with_vuses (newexpr, tvuses);
expr = newexpr;
phi_trans_add (oldexpr, newexpr, pred, tvuses);
}
}
}
return expr;
case tcc_declaration:
{
VEC (tree, gc) * oldvuses = NULL;
VEC (tree, gc) * newvuses = NULL;
oldvuses = VALUE_HANDLE_VUSES (get_value_handle (expr));
if (oldvuses)
newvuses = translate_vuses_through_block (oldvuses, pred);
if (oldvuses != newvuses)
vn_lookup_or_add_with_vuses (expr, newvuses);
phi_trans_add (oldexpr, expr, pred, newvuses);
}
return expr;
case tcc_reference:
{
tree oldop0 = TREE_OPERAND (expr, 0);
tree oldop1 = NULL;
tree newop0;
tree newop1 = NULL;
tree oldop2 = NULL;
tree newop2 = NULL;
tree oldop3 = NULL;
tree newop3 = NULL;
tree newexpr;
VEC (tree, gc) * oldvuses = NULL;
VEC (tree, gc) * newvuses = NULL;
if (TREE_CODE (expr) != INDIRECT_REF
&& TREE_CODE (expr) != COMPONENT_REF
&& TREE_CODE (expr) != ARRAY_REF)
return NULL;
newop0 = phi_translate (find_leader (set, oldop0),
set, pred, phiblock);
if (newop0 == NULL)
return NULL;
if (TREE_CODE (expr) == ARRAY_REF)
{
oldop1 = TREE_OPERAND (expr, 1);
newop1 = phi_translate (find_leader (set, oldop1),
set, pred, phiblock);
if (newop1 == NULL)
return NULL;
oldop2 = TREE_OPERAND (expr, 2);
if (oldop2)
{
newop2 = phi_translate (find_leader (set, oldop2),
set, pred, phiblock);
if (newop2 == NULL)
return NULL;
}
oldop3 = TREE_OPERAND (expr, 3);
if (oldop3)
{
newop3 = phi_translate (find_leader (set, oldop3),
set, pred, phiblock);
if (newop3 == NULL)
return NULL;
}
}
oldvuses = VALUE_HANDLE_VUSES (get_value_handle (expr));
if (oldvuses)
newvuses = translate_vuses_through_block (oldvuses, pred);
if (newop0 != oldop0 || newvuses != oldvuses
|| newop1 != oldop1
|| newop2 != oldop2
|| newop3 != oldop3)
{
tree t;
newexpr = pool_alloc (reference_node_pool);
memcpy (newexpr, expr, tree_size (expr));
TREE_OPERAND (newexpr, 0) = get_value_handle (newop0);
if (TREE_CODE (expr) == ARRAY_REF)
{
TREE_OPERAND (newexpr, 1) = get_value_handle (newop1);
if (newop2)
TREE_OPERAND (newexpr, 2) = get_value_handle (newop2);
if (newop3)
TREE_OPERAND (newexpr, 3) = get_value_handle (newop3);
}
t = fully_constant_expression (newexpr);
if (t != newexpr)
{
pool_free (reference_node_pool, newexpr);
newexpr = t;
}
else
{
newexpr->common.ann = NULL;
vn_lookup_or_add_with_vuses (newexpr, newvuses);
}
expr = newexpr;
phi_trans_add (oldexpr, newexpr, pred, newvuses);
}
}
return expr;
break;
case tcc_binary:
case tcc_comparison:
{
tree oldop1 = TREE_OPERAND (expr, 0);
tree oldop2 = TREE_OPERAND (expr, 1);
tree newop1;
tree newop2;
tree newexpr;
newop1 = phi_translate (find_leader (set, oldop1),
set, pred, phiblock);
if (newop1 == NULL)
return NULL;
newop2 = phi_translate (find_leader (set, oldop2),
set, pred, phiblock);
if (newop2 == NULL)
return NULL;
if (newop1 != oldop1 || newop2 != oldop2)
{
tree t;
newexpr = (tree) pool_alloc (binary_node_pool);
memcpy (newexpr, expr, tree_size (expr));
TREE_OPERAND (newexpr, 0) = newop1 == oldop1 ? oldop1 : get_value_handle (newop1);
TREE_OPERAND (newexpr, 1) = newop2 == oldop2 ? oldop2 : get_value_handle (newop2);
t = fully_constant_expression (newexpr);
if (t != newexpr)
{
pool_free (binary_node_pool, newexpr);
newexpr = t;
}
else
{
newexpr->common.ann = NULL;
vn_lookup_or_add (newexpr, NULL);
}
expr = newexpr;
phi_trans_add (oldexpr, newexpr, pred, NULL);
}
}
return expr;
case tcc_unary:
{
tree oldop1 = TREE_OPERAND (expr, 0);
tree newop1;
tree newexpr;
newop1 = phi_translate (find_leader (set, oldop1),
set, pred, phiblock);
if (newop1 == NULL)
return NULL;
if (newop1 != oldop1)
{
tree t;
newexpr = (tree) pool_alloc (unary_node_pool);
memcpy (newexpr, expr, tree_size (expr));
TREE_OPERAND (newexpr, 0) = get_value_handle (newop1);
t = fully_constant_expression (newexpr);
if (t != newexpr)
{
pool_free (unary_node_pool, newexpr);
newexpr = t;
}
else
{
newexpr->common.ann = NULL;
vn_lookup_or_add (newexpr, NULL);
}
expr = newexpr;
phi_trans_add (oldexpr, newexpr, pred, NULL);
}
}
return expr;
case tcc_exceptional:
{
tree phi = NULL;
edge e;
gcc_assert (TREE_CODE (expr) == SSA_NAME);
if (TREE_CODE (SSA_NAME_DEF_STMT (expr)) == PHI_NODE)
phi = SSA_NAME_DEF_STMT (expr);
else
return expr;
e = find_edge (pred, bb_for_stmt (phi));
if (e)
{
if (is_undefined_value (PHI_ARG_DEF (phi, e->dest_idx)))
return NULL;
vn_lookup_or_add (PHI_ARG_DEF (phi, e->dest_idx), NULL);
return PHI_ARG_DEF (phi, e->dest_idx);
}
}
return expr;
default:
gcc_unreachable ();
}
}
static void
phi_translate_set (value_set_t dest, value_set_t set, basic_block pred,
basic_block phiblock)
{
value_set_node_t node;
for (node = set->head;
node;
node = node->next)
{
tree translated;
translated = phi_translate (node->expr, set, pred, phiblock);
if (translated && !is_gimple_min_invariant (translated))
{
tree vh = get_value_handle (translated);
VEC (tree, gc) *vuses;
vuses = !is_gimple_min_invariant (vh)
? VALUE_HANDLE_VUSES (vh) : NULL;
phi_trans_add (node->expr, translated, pred, vuses);
}
if (translated != NULL)
value_insert_into_set (dest, translated);
}
}
static tree
bitmap_find_leader (bitmap_set_t set, tree val)
{
if (val == NULL)
return NULL;
if (is_gimple_min_invariant (val))
return val;
if (bitmap_set_contains_value (set, val))
{
value_set_t exprset;
value_set_node_t node;
exprset = VALUE_HANDLE_EXPR_SET (val);
for (node = exprset->head; node; node = node->next)
{
if (TREE_CODE (node->expr) == SSA_NAME)
{
if (bitmap_bit_p (set->expressions,
SSA_NAME_VERSION (node->expr)))
return node->expr;
}
}
}
return NULL;
}
static tree
find_leader (value_set_t set, tree val)
{
value_set_node_t node;
if (val == NULL)
return NULL;
if (is_gimple_min_invariant (val))
return val;
if (set->length == 0)
return NULL;
if (value_exists_in_set_bitmap (set, val))
{
for (node = set->head;
node;
node = node->next)
{
if (get_value_handle (node->expr) == val)
return node->expr;
}
}
return NULL;
}
static bitmap
get_representative (bitmap *map, int id)
{
if (map[id] != NULL)
return map[id];
return NULL;
}
static bool
vuses_dies_in_block_x (VEC (tree, gc) *vuses, basic_block block)
{
int i;
tree vuse;
for (i = 0; VEC_iterate (tree, vuses, i, vuse); i++)
{
if (!bitmap_bit_p (RVUSE_IN (block), SSA_NAME_VERSION (vuse))
|| bitmap_bit_p (RVUSE_KILL (block), SSA_NAME_VERSION (vuse)))
return true;
}
return false;
}
static bool
valid_in_set (value_set_t set, tree expr, basic_block block)
{
tree vh = get_value_handle (expr);
switch (TREE_CODE_CLASS (TREE_CODE (expr)))
{
case tcc_binary:
case tcc_comparison:
{
tree op1 = TREE_OPERAND (expr, 0);
tree op2 = TREE_OPERAND (expr, 1);
return set_contains_value (set, op1) && set_contains_value (set, op2);
}
case tcc_unary:
{
tree op1 = TREE_OPERAND (expr, 0);
return set_contains_value (set, op1);
}
case tcc_expression:
{
if (TREE_CODE (expr) == CALL_EXPR)
{
tree op0 = TREE_OPERAND (expr, 0);
tree arglist = TREE_OPERAND (expr, 1);
tree op2 = TREE_OPERAND (expr, 2);
if (!set_contains_value (set, op0)
|| (op2 && !set_contains_value (set, op2)))
return false;
for (; arglist; arglist = TREE_CHAIN (arglist))
{
if (!set_contains_value (set, TREE_VALUE (arglist)))
return false;
}
return !vuses_dies_in_block_x (VALUE_HANDLE_VUSES (vh), block);
}
return false;
}
case tcc_reference:
{
if (TREE_CODE (expr) == INDIRECT_REF
|| TREE_CODE (expr) == COMPONENT_REF
|| TREE_CODE (expr) == ARRAY_REF)
{
tree op0 = TREE_OPERAND (expr, 0);
gcc_assert (is_gimple_min_invariant (op0)
|| TREE_CODE (op0) == VALUE_HANDLE);
if (!set_contains_value (set, op0))
return false;
if (TREE_CODE (expr) == ARRAY_REF)
{
tree op1 = TREE_OPERAND (expr, 1);
tree op2 = TREE_OPERAND (expr, 2);
tree op3 = TREE_OPERAND (expr, 3);
gcc_assert (is_gimple_min_invariant (op1)
|| TREE_CODE (op1) == VALUE_HANDLE);
if (!set_contains_value (set, op1))
return false;
gcc_assert (!op2 || is_gimple_min_invariant (op2)
|| TREE_CODE (op2) == VALUE_HANDLE);
if (op2
&& !set_contains_value (set, op2))
return false;
gcc_assert (!op3 || is_gimple_min_invariant (op3)
|| TREE_CODE (op3) == VALUE_HANDLE);
if (op3
&& !set_contains_value (set, op3))
return false;
}
return set_contains_value (ANTIC_SAFE_LOADS (block),
vh)
|| !vuses_dies_in_block_x (VALUE_HANDLE_VUSES (vh),
block);
}
}
return false;
case tcc_exceptional:
gcc_assert (TREE_CODE (expr) == SSA_NAME);
return true;
case tcc_declaration:
return !vuses_dies_in_block_x (VALUE_HANDLE_VUSES (vh), block);
default:
gcc_unreachable ();
}
}
static void
clean (value_set_t set, basic_block block)
{
value_set_node_t node;
value_set_node_t next;
node = set->head;
while (node)
{
next = node->next;
if (!valid_in_set (set, node->expr, block))
set_remove (set, node->expr);
node = next;
}
}
static sbitmap has_abnormal_preds;
static bool
compute_antic_aux (basic_block block, bool block_has_abnormal_pred_edge)
{
basic_block son;
bool changed = false;
value_set_t S, old, ANTIC_OUT;
value_set_node_t node;
ANTIC_OUT = S = NULL;
if (block_has_abnormal_pred_edge)
goto maybe_dump_sets;
old = set_new (false);
set_copy (old, ANTIC_IN (block));
ANTIC_OUT = set_new (true);
if (EDGE_COUNT (block->succs) == 0)
;
else if (single_succ_p (block))
{
phi_translate_set (ANTIC_OUT, ANTIC_IN (single_succ (block)),
block, single_succ (block));
}
else
{
VEC(basic_block, heap) * worklist;
edge e;
size_t i;
basic_block bprime, first;
edge_iterator ei;
worklist = VEC_alloc (basic_block, heap, EDGE_COUNT (block->succs));
FOR_EACH_EDGE (e, ei, block->succs)
VEC_quick_push (basic_block, worklist, e->dest);
first = VEC_index (basic_block, worklist, 0);
set_copy (ANTIC_OUT, ANTIC_IN (first));
for (i = 1; VEC_iterate (basic_block, worklist, i, bprime); i++)
{
node = ANTIC_OUT->head;
while (node)
{
tree val;
value_set_node_t next = node->next;
val = get_value_handle (node->expr);
if (!set_contains_value (ANTIC_IN (bprime), val))
set_remove (ANTIC_OUT, node->expr);
node = next;
}
}
VEC_free (basic_block, heap, worklist);
}
S = bitmap_set_subtract_from_value_set (ANTIC_OUT, TMP_GEN (block), false);
ANTIC_IN (block) = bitmap_set_subtract_from_value_set (EXP_GEN (block),
TMP_GEN (block),
true);
for (node = S->head; node; node = node->next)
value_insert_into_set (ANTIC_IN (block), node->expr);
clean (ANTIC_IN (block), block);
if (!set_equal (old, ANTIC_IN (block)))
changed = true;
maybe_dump_sets:
if (dump_file && (dump_flags & TDF_DETAILS))
{
if (ANTIC_OUT)
print_value_set (dump_file, ANTIC_OUT, "ANTIC_OUT", block->index);
if (ANTIC_SAFE_LOADS (block))
print_value_set (dump_file, ANTIC_SAFE_LOADS (block),
"ANTIC_SAFE_LOADS", block->index);
print_value_set (dump_file, ANTIC_IN (block), "ANTIC_IN", block->index);
if (S)
print_value_set (dump_file, S, "S", block->index);
}
for (son = first_dom_son (CDI_POST_DOMINATORS, block);
son;
son = next_dom_son (CDI_POST_DOMINATORS, son))
{
changed |= compute_antic_aux (son,
TEST_BIT (has_abnormal_preds, son->index));
}
return changed;
}
static void
compute_antic (void)
{
bool changed = true;
int num_iterations = 0;
basic_block block;
has_abnormal_preds = sbitmap_alloc (last_basic_block);
sbitmap_zero (has_abnormal_preds);
FOR_EACH_BB (block)
{
edge_iterator ei;
edge e;
FOR_EACH_EDGE (e, ei, block->preds)
if (e->flags & EDGE_ABNORMAL)
{
SET_BIT (has_abnormal_preds, block->index);
break;
}
ANTIC_IN (block) = set_new (true);
}
ANTIC_IN (EXIT_BLOCK_PTR) = set_new (true);
while (changed)
{
num_iterations++;
changed = false;
changed = compute_antic_aux (EXIT_BLOCK_PTR, false);
}
sbitmap_free (has_abnormal_preds);
if (dump_file && (dump_flags & TDF_STATS))
fprintf (dump_file, "compute_antic required %d iterations\n", num_iterations);
}
static void
dump_bitmap_of_names (FILE *out, bitmap names)
{
bitmap_iterator bi;
unsigned int i;
fprintf (out, " { ");
EXECUTE_IF_SET_IN_BITMAP (names, 0, i, bi)
{
print_generic_expr (out, ssa_name (i), 0);
fprintf (out, " ");
}
fprintf (out, "}\n");
}
static bitmap *vuse_names;
static void
compute_vuse_representatives (void)
{
tree phi;
basic_block bb;
VEC (tree, heap) *phis = NULL;
bool changed = true;
size_t i;
FOR_EACH_BB (bb)
{
for (phi = phi_nodes (bb);
phi;
phi = PHI_CHAIN (phi))
if (!is_gimple_reg (PHI_RESULT (phi)))
VEC_safe_push (tree, heap, phis, phi);
}
while (changed)
{
changed = false;
for (i = 0; VEC_iterate (tree, phis, i, phi); i++)
{
size_t ver = SSA_NAME_VERSION (PHI_RESULT (phi));
use_operand_p usep;
ssa_op_iter iter;
if (vuse_names[ver] == NULL)
{
vuse_names[ver] = BITMAP_ALLOC (&grand_bitmap_obstack);
bitmap_set_bit (vuse_names[ver], ver);
}
FOR_EACH_PHI_ARG (usep, phi, iter, SSA_OP_ALL_USES)
{
tree use = USE_FROM_PTR (usep);
bitmap usebitmap = get_representative (vuse_names,
SSA_NAME_VERSION (use));
if (usebitmap != NULL)
{
changed |= bitmap_ior_into (vuse_names[ver],
usebitmap);
}
else
{
changed |= !bitmap_bit_p (vuse_names[ver],
SSA_NAME_VERSION (use));
if (changed)
bitmap_set_bit (vuse_names[ver],
SSA_NAME_VERSION (use));
}
}
}
}
if (dump_file && (dump_flags & TDF_DETAILS))
for (i = 0; VEC_iterate (tree, phis, i, phi); i++)
{
bitmap reps = get_representative (vuse_names,
SSA_NAME_VERSION (PHI_RESULT (phi)));
if (reps)
{
print_generic_expr (dump_file, PHI_RESULT (phi), 0);
fprintf (dump_file, " represents ");
dump_bitmap_of_names (dump_file, reps);
}
}
VEC_free (tree, heap, phis);
}
static void
compute_rvuse_and_antic_safe (void)
{
size_t i;
tree phi;
basic_block bb;
int *postorder;
bool changed = true;
unsigned int *first_store_uid;
first_store_uid = xcalloc (n_basic_blocks, sizeof (unsigned int));
compute_vuse_representatives ();
FOR_ALL_BB (bb)
{
RVUSE_IN (bb) = BITMAP_ALLOC (&grand_bitmap_obstack);
RVUSE_GEN (bb) = BITMAP_ALLOC (&grand_bitmap_obstack);
RVUSE_KILL (bb) = BITMAP_ALLOC (&grand_bitmap_obstack);
RVUSE_OUT (bb) = BITMAP_ALLOC (&grand_bitmap_obstack);
ANTIC_SAFE_LOADS (bb) = NULL;
}
for (i = 0; i < num_ssa_names; i++)
{
tree name = ssa_name (i);
if (name && !is_gimple_reg (name)
&& IS_EMPTY_STMT (SSA_NAME_DEF_STMT (name)))
bitmap_set_bit (RVUSE_OUT (ENTRY_BLOCK_PTR),
SSA_NAME_VERSION (name));
}
FOR_EACH_BB (bb)
{
block_stmt_iterator bsi;
ssa_op_iter iter;
def_operand_p defp;
use_operand_p usep;
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
{
tree stmt = bsi_stmt (bsi);
if (first_store_uid[bb->index] == 0
&& !ZERO_SSA_OPERANDS (stmt, SSA_OP_VMAYUSE | SSA_OP_VMAYDEF
| SSA_OP_VMUSTDEF | SSA_OP_VMUSTKILL))
{
first_store_uid[bb->index] = stmt_ann (stmt)->uid;
}
FOR_EACH_SSA_USE_OPERAND (usep, stmt, iter, SSA_OP_VIRTUAL_KILLS
| SSA_OP_VMAYUSE)
{
tree use = USE_FROM_PTR (usep);
bitmap repbit = get_representative (vuse_names,
SSA_NAME_VERSION (use));
if (repbit != NULL)
{
bitmap_and_compl_into (RVUSE_GEN (bb), repbit);
bitmap_ior_into (RVUSE_KILL (bb), repbit);
}
else
{
bitmap_set_bit (RVUSE_KILL (bb), SSA_NAME_VERSION (use));
bitmap_clear_bit (RVUSE_GEN (bb), SSA_NAME_VERSION (use));
}
}
FOR_EACH_SSA_DEF_OPERAND (defp, stmt, iter, SSA_OP_VIRTUAL_DEFS)
{
tree def = DEF_FROM_PTR (defp);
bitmap_set_bit (RVUSE_GEN (bb), SSA_NAME_VERSION (def));
}
}
}
FOR_EACH_BB (bb)
{
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
{
if (!is_gimple_reg (PHI_RESULT (phi)))
{
edge e;
edge_iterator ei;
tree def = PHI_RESULT (phi);
FOR_EACH_EDGE (e, ei, bb->preds)
bitmap_set_bit (RVUSE_GEN (e->src), SSA_NAME_VERSION (def));
}
}
}
postorder = XNEWVEC (int, n_basic_blocks - NUM_FIXED_BLOCKS);
pre_and_rev_post_order_compute (NULL, postorder, false);
changed = true;
while (changed)
{
int j;
changed = false;
for (j = 0; j < n_basic_blocks - NUM_FIXED_BLOCKS; j++)
{
edge e;
edge_iterator ei;
bb = BASIC_BLOCK (postorder[j]);
FOR_EACH_EDGE (e, ei, bb->preds)
bitmap_ior_into (RVUSE_IN (bb), RVUSE_OUT (e->src));
changed |= bitmap_ior_and_compl (RVUSE_OUT (bb),
RVUSE_GEN (bb),
RVUSE_IN (bb),
RVUSE_KILL (bb));
}
}
free (postorder);
if (dump_file && (dump_flags & TDF_DETAILS))
{
FOR_ALL_BB (bb)
{
fprintf (dump_file, "RVUSE_IN (%d) =", bb->index);
dump_bitmap_of_names (dump_file, RVUSE_IN (bb));
fprintf (dump_file, "RVUSE_KILL (%d) =", bb->index);
dump_bitmap_of_names (dump_file, RVUSE_KILL (bb));
fprintf (dump_file, "RVUSE_GEN (%d) =", bb->index);
dump_bitmap_of_names (dump_file, RVUSE_GEN (bb));
fprintf (dump_file, "RVUSE_OUT (%d) =", bb->index);
dump_bitmap_of_names (dump_file, RVUSE_OUT (bb));
}
}
FOR_EACH_BB (bb)
{
value_set_node_t node;
if (bitmap_empty_p (RVUSE_KILL (bb)))
continue;
for (node = EXP_GEN (bb)->head; node; node = node->next)
{
if (REFERENCE_CLASS_P (node->expr))
{
tree vh = get_value_handle (node->expr);
tree maybe = bitmap_find_leader (AVAIL_OUT (bb), vh);
if (maybe)
{
tree def = SSA_NAME_DEF_STMT (maybe);
if (bb_for_stmt (def) != bb)
continue;
if (TREE_CODE (def) == PHI_NODE
|| stmt_ann (def)->uid < first_store_uid[bb->index])
{
if (ANTIC_SAFE_LOADS (bb) == NULL)
ANTIC_SAFE_LOADS (bb) = set_new (true);
value_insert_into_set (ANTIC_SAFE_LOADS (bb),
node->expr);
}
}
}
}
}
free (first_store_uid);
}
static bool
can_value_number_call (tree stmt)
{
tree call = get_call_expr_in (stmt);
if (call_expr_flags (call) & (ECF_PURE | ECF_CONST))
return true;
return false;
}
static bool
can_value_number_operation (tree op)
{
return UNARY_CLASS_P (op)
|| BINARY_CLASS_P (op)
|| COMPARISON_CLASS_P (op)
|| REFERENCE_CLASS_P (op)
|| (TREE_CODE (op) == CALL_EXPR
&& can_value_number_call (op));
}
static bool
can_PRE_operation (tree op)
{
return UNARY_CLASS_P (op)
|| BINARY_CLASS_P (op)
|| COMPARISON_CLASS_P (op)
|| TREE_CODE (op) == INDIRECT_REF
|| TREE_CODE (op) == COMPONENT_REF
|| TREE_CODE (op) == CALL_EXPR
|| TREE_CODE (op) == ARRAY_REF;
}
static VEC(tree,heap) *inserted_exprs;
static VEC(tree, heap) *need_creation;
static tree
create_component_ref_by_pieces (basic_block block, tree expr, tree stmts)
{
tree genop = expr;
tree folded;
if (TREE_CODE (genop) == VALUE_HANDLE)
{
tree found = bitmap_find_leader (AVAIL_OUT (block), expr);
if (found)
return found;
}
if (TREE_CODE (genop) == VALUE_HANDLE)
genop = VALUE_HANDLE_EXPR_SET (expr)->head->expr;
switch TREE_CODE (genop)
{
case ARRAY_REF:
{
tree op0;
tree op1, op2, op3;
op0 = create_component_ref_by_pieces (block,
TREE_OPERAND (genop, 0),
stmts);
op1 = TREE_OPERAND (genop, 1);
if (TREE_CODE (op1) == VALUE_HANDLE)
op1 = find_or_generate_expression (block, op1, stmts);
op2 = TREE_OPERAND (genop, 2);
if (op2 && TREE_CODE (op2) == VALUE_HANDLE)
op2 = find_or_generate_expression (block, op2, stmts);
op3 = TREE_OPERAND (genop, 3);
if (op3 && TREE_CODE (op3) == VALUE_HANDLE)
op3 = find_or_generate_expression (block, op3, stmts);
folded = build4 (ARRAY_REF, TREE_TYPE (genop), op0, op1,
op2, op3);
return folded;
}
case COMPONENT_REF:
{
tree op0;
tree op1;
op0 = create_component_ref_by_pieces (block,
TREE_OPERAND (genop, 0),
stmts);
op1 = VALUE_HANDLE_EXPR_SET (TREE_OPERAND (genop, 1))->head->expr;
folded = fold_build3 (COMPONENT_REF, TREE_TYPE (genop), op0, op1,
NULL_TREE);
return folded;
}
break;
case INDIRECT_REF:
{
tree op1 = TREE_OPERAND (genop, 0);
tree genop1 = find_or_generate_expression (block, op1, stmts);
folded = fold_build1 (TREE_CODE (genop), TREE_TYPE (genop),
genop1);
return folded;
}
break;
case VAR_DECL:
case PARM_DECL:
case RESULT_DECL:
case SSA_NAME:
case STRING_CST:
return genop;
default:
gcc_unreachable ();
}
return NULL_TREE;
}
static tree
find_or_generate_expression (basic_block block, tree expr, tree stmts)
{
tree genop = bitmap_find_leader (AVAIL_OUT (block), expr);
if (genop == NULL)
{
genop = VALUE_HANDLE_EXPR_SET (expr)->head->expr;
gcc_assert (can_PRE_operation (genop));
genop = create_expression_by_pieces (block, genop, stmts);
}
return genop;
}
#define NECESSARY(stmt) stmt->common.asm_written_flag
static tree
create_expression_by_pieces (basic_block block, tree expr, tree stmts)
{
tree temp, name;
tree folded, forced_stmts, newexpr;
tree v;
tree_stmt_iterator tsi;
switch (TREE_CODE_CLASS (TREE_CODE (expr)))
{
case tcc_expression:
{
tree op0, op2;
tree arglist;
tree genop0, genop2;
tree genarglist;
tree walker, genwalker;
gcc_assert (TREE_CODE (expr) == CALL_EXPR);
genop2 = NULL;
op0 = TREE_OPERAND (expr, 0);
arglist = TREE_OPERAND (expr, 1);
op2 = TREE_OPERAND (expr, 2);
genop0 = find_or_generate_expression (block, op0, stmts);
genarglist = copy_list (arglist);
for (walker = arglist, genwalker = genarglist;
genwalker && walker;
genwalker = TREE_CHAIN (genwalker), walker = TREE_CHAIN (walker))
{
TREE_VALUE (genwalker)
= find_or_generate_expression (block, TREE_VALUE (walker),
stmts);
}
if (op2)
genop2 = find_or_generate_expression (block, op2, stmts);
folded = fold_build3 (TREE_CODE (expr), TREE_TYPE (expr),
genop0, genarglist, genop2);
break;
}
break;
case tcc_reference:
{
if (TREE_CODE (expr) == COMPONENT_REF
|| TREE_CODE (expr) == ARRAY_REF)
{
folded = create_component_ref_by_pieces (block, expr, stmts);
}
else
{
tree op1 = TREE_OPERAND (expr, 0);
tree genop1 = find_or_generate_expression (block, op1, stmts);
folded = fold_build1 (TREE_CODE (expr), TREE_TYPE (expr),
genop1);
}
break;
}
case tcc_binary:
case tcc_comparison:
{
tree op1 = TREE_OPERAND (expr, 0);
tree op2 = TREE_OPERAND (expr, 1);
tree genop1 = find_or_generate_expression (block, op1, stmts);
tree genop2 = find_or_generate_expression (block, op2, stmts);
folded = fold_build2 (TREE_CODE (expr), TREE_TYPE (expr),
genop1, genop2);
break;
}
case tcc_unary:
{
tree op1 = TREE_OPERAND (expr, 0);
tree genop1 = find_or_generate_expression (block, op1, stmts);
folded = fold_build1 (TREE_CODE (expr), TREE_TYPE (expr),
genop1);
break;
}
default:
gcc_unreachable ();
}
newexpr = force_gimple_operand (unshare_expr (folded), &forced_stmts,
false, NULL);
if (forced_stmts)
{
tsi = tsi_start (forced_stmts);
for (; !tsi_end_p (tsi); tsi_next (&tsi))
{
tree stmt = tsi_stmt (tsi);
tree forcedname = TREE_OPERAND (stmt, 0);
tree forcedexpr = TREE_OPERAND (stmt, 1);
tree val = vn_lookup_or_add (forcedexpr, NULL);
VEC_safe_push (tree, heap, inserted_exprs, stmt);
vn_add (forcedname, val);
bitmap_value_replace_in_set (NEW_SETS (block), forcedname);
bitmap_value_replace_in_set (AVAIL_OUT (block), forcedname);
mark_new_vars_to_rename (stmt);
}
tsi = tsi_last (stmts);
tsi_link_after (&tsi, forced_stmts, TSI_CONTINUE_LINKING);
}
if (!pretemp || TREE_TYPE (expr) != TREE_TYPE (pretemp))
{
pretemp = create_tmp_var (TREE_TYPE (expr), "pretmp");
get_var_ann (pretemp);
}
temp = pretemp;
add_referenced_var (temp);
if (TREE_CODE (TREE_TYPE (expr)) == COMPLEX_TYPE)
DECL_COMPLEX_GIMPLE_REG_P (temp) = 1;
newexpr = build2 (MODIFY_EXPR, TREE_TYPE (expr), temp, newexpr);
name = make_ssa_name (temp, newexpr);
TREE_OPERAND (newexpr, 0) = name;
NECESSARY (newexpr) = 0;
tsi = tsi_last (stmts);
tsi_link_after (&tsi, newexpr, TSI_CONTINUE_LINKING);
VEC_safe_push (tree, heap, inserted_exprs, newexpr);
mark_new_vars_to_rename (newexpr);
v = get_value_handle (expr);
vn_add (name, v);
bitmap_value_replace_in_set (NEW_SETS (block), name);
bitmap_value_replace_in_set (AVAIL_OUT (block), name);
pre_stats.insertions++;
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Inserted ");
print_generic_expr (dump_file, newexpr, 0);
fprintf (dump_file, " in predecessor %d\n", block->index);
}
return name;
}
static bool
insert_into_preds_of_block (basic_block block, value_set_node_t node,
tree *avail)
{
tree val = get_value_handle (node->expr);
edge pred;
bool insertions = false;
bool nophi = false;
basic_block bprime;
tree eprime;
edge_iterator ei;
tree type = TREE_TYPE (avail[EDGE_PRED (block, 0)->src->index]);
tree temp;
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Found partial redundancy for expression ");
print_generic_expr (dump_file, node->expr, 0);
fprintf (dump_file, " (");
print_generic_expr (dump_file, val, 0);
fprintf (dump_file, ")");
fprintf (dump_file, "\n");
}
if (block->loop_depth > 0 && EDGE_COUNT (block->preds) == 2
&& TREE_CODE_CLASS (TREE_CODE (node->expr)) != tcc_reference )
{
bool firstinsideloop = false;
bool secondinsideloop = false;
firstinsideloop = flow_bb_inside_loop_p (block->loop_father,
EDGE_PRED (block, 0)->src);
secondinsideloop = flow_bb_inside_loop_p (block->loop_father,
EDGE_PRED (block, 1)->src);
if (firstinsideloop ^ secondinsideloop)
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Skipping insertion of phi for partial redundancy: Looks like an induction variable\n");
nophi = true;
}
}
FOR_EACH_EDGE (pred, ei, block->preds)
{
tree stmts = alloc_stmt_list ();
tree builtexpr;
bprime = pred->src;
eprime = avail[bprime->index];
if (can_PRE_operation (eprime))
{
#ifdef ENABLE_CHECKING
tree vh;
vh = TREE_CODE (eprime) == VALUE_HANDLE
? eprime
: get_value_handle (eprime);
if (TREE_CODE (vh) == VALUE_HANDLE)
{
int i;
tree vuse;
for (i = 0;
VEC_iterate (tree, VALUE_HANDLE_VUSES (vh), i, vuse);
i++)
{
size_t id = SSA_NAME_VERSION (vuse);
gcc_assert (bitmap_bit_p (RVUSE_OUT (bprime), id)
|| IS_EMPTY_STMT (SSA_NAME_DEF_STMT (vuse)));
}
}
#endif
builtexpr = create_expression_by_pieces (bprime,
eprime,
stmts);
bsi_insert_on_edge (pred, stmts);
avail[bprime->index] = builtexpr;
insertions = true;
}
}
if (nophi && insertions)
return true;
else if (nophi && !insertions)
return false;
if (!prephitemp || TREE_TYPE (prephitemp) != type)
{
prephitemp = create_tmp_var (type, "prephitmp");
get_var_ann (prephitemp);
}
temp = prephitemp;
add_referenced_var (temp);
if (TREE_CODE (type) == COMPLEX_TYPE)
DECL_COMPLEX_GIMPLE_REG_P (temp) = 1;
temp = create_phi_node (temp, block);
NECESSARY (temp) = 0;
VEC_safe_push (tree, heap, inserted_exprs, temp);
FOR_EACH_EDGE (pred, ei, block->preds)
add_phi_arg (temp, avail[pred->src->index], pred);
vn_add (PHI_RESULT (temp), val);
bitmap_insert_into_set (PHI_GEN (block),
PHI_RESULT (temp));
bitmap_value_replace_in_set (AVAIL_OUT (block),
PHI_RESULT (temp));
bitmap_insert_into_set (NEW_SETS (block),
PHI_RESULT (temp));
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Created phi ");
print_generic_expr (dump_file, temp, 0);
fprintf (dump_file, " in block %d\n", block->index);
}
pre_stats.phis++;
return true;
}
static bool
insert_aux (basic_block block)
{
basic_block son;
bool new_stuff = false;
if (block)
{
basic_block dom;
dom = get_immediate_dominator (CDI_DOMINATORS, block);
if (dom)
{
unsigned i;
bitmap_iterator bi;
bitmap_set_t newset = NEW_SETS (dom);
if (newset)
{
EXECUTE_IF_SET_IN_BITMAP (newset->expressions, 0, i, bi)
{
bitmap_value_replace_in_set (NEW_SETS (block), ssa_name (i));
bitmap_value_replace_in_set (AVAIL_OUT (block), ssa_name (i));
}
}
if (!single_pred_p (block))
{
value_set_node_t node;
for (node = ANTIC_IN (block)->head;
node;
node = node->next)
{
if (can_PRE_operation (node->expr)
&& !AGGREGATE_TYPE_P (TREE_TYPE (node->expr)))
{
tree *avail;
tree val;
bool by_some = false;
bool cant_insert = false;
bool all_same = true;
tree first_s = NULL;
edge pred;
basic_block bprime;
tree eprime = NULL_TREE;
edge_iterator ei;
val = get_value_handle (node->expr);
if (bitmap_set_contains_value (PHI_GEN (block), val))
continue;
if (bitmap_set_contains_value (AVAIL_OUT (dom), val))
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Found fully redundant value\n");
continue;
}
avail = XCNEWVEC (tree, last_basic_block);
FOR_EACH_EDGE (pred, ei, block->preds)
{
tree vprime;
tree edoubleprime;
if (EDGE_CRITICAL_P (pred))
{
cant_insert = true;
break;
}
bprime = pred->src;
eprime = phi_translate (node->expr,
ANTIC_IN (block),
bprime, block);
if (eprime == NULL)
{
cant_insert = true;
break;
}
eprime = fully_constant_expression (eprime);
vprime = get_value_handle (eprime);
gcc_assert (vprime);
edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime),
vprime);
if (edoubleprime == NULL)
{
avail[bprime->index] = eprime;
all_same = false;
}
else
{
avail[bprime->index] = edoubleprime;
by_some = true;
if (first_s == NULL)
first_s = edoubleprime;
else if (!operand_equal_p (first_s, edoubleprime,
0))
all_same = false;
}
}
if (!cant_insert && !all_same && by_some)
{
if (insert_into_preds_of_block (block, node, avail))
new_stuff = true;
}
else if (!cant_insert && all_same && eprime
&& is_gimple_min_invariant (eprime)
&& !is_gimple_min_invariant (val))
{
value_set_t exprset = VALUE_HANDLE_EXPR_SET (val);
value_set_node_t node;
for (node = exprset->head; node; node = node->next)
{
if (TREE_CODE (node->expr) == SSA_NAME)
{
vn_add (node->expr, eprime);
pre_stats.constified++;
}
}
}
free (avail);
}
}
}
}
}
for (son = first_dom_son (CDI_DOMINATORS, block);
son;
son = next_dom_son (CDI_DOMINATORS, son))
{
new_stuff |= insert_aux (son);
}
return new_stuff;
}
static void
insert (void)
{
bool new_stuff = true;
basic_block bb;
int num_iterations = 0;
FOR_ALL_BB (bb)
NEW_SETS (bb) = bitmap_set_new ();
while (new_stuff)
{
num_iterations++;
new_stuff = false;
new_stuff = insert_aux (ENTRY_BLOCK_PTR);
}
if (num_iterations > 2 && dump_file && (dump_flags & TDF_STATS))
fprintf (dump_file, "insert required %d iterations\n", num_iterations);
}
static bool
is_undefined_value (tree expr)
{
return (TREE_CODE (expr) == SSA_NAME
&& IS_EMPTY_STMT (SSA_NAME_DEF_STMT (expr))
&& TREE_CODE (SSA_NAME_VAR (expr)) != PARM_DECL);
}
static inline void
add_to_sets (tree var, tree expr, tree stmt, bitmap_set_t s1,
bitmap_set_t s2)
{
tree val = vn_lookup_or_add (expr, stmt);
if (var != expr)
vn_add (var, val);
if (s1)
bitmap_insert_into_set (s1, var);
bitmap_value_insert_into_set (s2, var);
}
static inline tree
create_value_expr_from (tree expr, basic_block block, tree stmt)
{
int i;
enum tree_code code = TREE_CODE (expr);
tree vexpr;
alloc_pool pool;
gcc_assert (TREE_CODE_CLASS (code) == tcc_unary
|| TREE_CODE_CLASS (code) == tcc_binary
|| TREE_CODE_CLASS (code) == tcc_comparison
|| TREE_CODE_CLASS (code) == tcc_reference
|| TREE_CODE_CLASS (code) == tcc_expression
|| TREE_CODE_CLASS (code) == tcc_exceptional
|| TREE_CODE_CLASS (code) == tcc_declaration);
if (TREE_CODE_CLASS (code) == tcc_unary)
pool = unary_node_pool;
else if (TREE_CODE_CLASS (code) == tcc_reference)
pool = reference_node_pool;
else if (TREE_CODE_CLASS (code) == tcc_binary)
pool = binary_node_pool;
else if (TREE_CODE_CLASS (code) == tcc_comparison)
pool = comparison_node_pool;
else if (TREE_CODE_CLASS (code) == tcc_exceptional)
{
gcc_assert (code == TREE_LIST);
pool = list_node_pool;
}
else
{
gcc_assert (code == CALL_EXPR);
pool = expression_node_pool;
}
vexpr = (tree) pool_alloc (pool);
memcpy (vexpr, expr, tree_size (expr));
if (code == TREE_LIST)
{
tree op = NULL_TREE;
tree temp = NULL_TREE;
if (TREE_CHAIN (vexpr))
temp = create_value_expr_from (TREE_CHAIN (vexpr), block, stmt);
TREE_CHAIN (vexpr) = temp ? temp : TREE_CHAIN (vexpr);
if (REFERENCE_CLASS_P (TREE_VALUE (vexpr)))
{
tree tempop;
op = TREE_VALUE (vexpr);
tempop = create_value_expr_from (op, block, stmt);
op = tempop ? tempop : op;
TREE_VALUE (vexpr) = vn_lookup_or_add (op, stmt);
}
else
{
op = TREE_VALUE (vexpr);
TREE_VALUE (vexpr) = vn_lookup_or_add (TREE_VALUE (vexpr), NULL);
}
if (!is_undefined_value (op))
value_insert_into_set (EXP_GEN (block), op);
return vexpr;
}
for (i = 0; i < TREE_CODE_LENGTH (code); i++)
{
tree val, op;
op = TREE_OPERAND (expr, i);
if (op == NULL_TREE)
continue;
if (REFERENCE_CLASS_P (op))
{
tree tempop = create_value_expr_from (op, block, stmt);
op = tempop ? tempop : op;
val = vn_lookup_or_add (op, stmt);
}
else if (TREE_CODE (op) == TREE_LIST)
{
tree tempop;
gcc_assert (TREE_CODE (expr) == CALL_EXPR);
tempop = create_value_expr_from (op, block, stmt);
op = tempop ? tempop : op;
vn_lookup_or_add (op, NULL);
val = op;
}
else
val = vn_lookup_or_add (op, NULL);
if (!is_undefined_value (op) && TREE_CODE (op) != TREE_LIST)
value_insert_into_set (EXP_GEN (block), op);
if (TREE_CODE (val) == VALUE_HANDLE)
TREE_TYPE (val) = TREE_TYPE (TREE_OPERAND (vexpr, i));
TREE_OPERAND (vexpr, i) = val;
}
return vexpr;
}
static void
insert_extra_phis (basic_block block, basic_block dom)
{
if (!single_pred_p (block))
{
edge e;
edge_iterator ei;
bool first = true;
bitmap_set_t tempset = bitmap_set_new ();
FOR_EACH_EDGE (e, ei, block->preds)
{
if (e->flags & EDGE_ABNORMAL)
return;
if (first)
{
bitmap_set_copy (tempset, AVAIL_OUT (e->src));
first = false;
}
else
bitmap_set_and (tempset, AVAIL_OUT (e->src));
}
if (dom)
bitmap_set_and_compl (tempset, AVAIL_OUT (dom));
if (!bitmap_set_empty_p (tempset))
{
unsigned int i;
bitmap_iterator bi;
EXECUTE_IF_SET_IN_BITMAP (tempset->expressions, 0, i, bi)
{
tree name = ssa_name (i);
tree val = get_value_handle (name);
tree temp;
if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
continue;
if (!mergephitemp
|| TREE_TYPE (name) != TREE_TYPE (mergephitemp))
{
mergephitemp = create_tmp_var (TREE_TYPE (name),
"mergephitmp");
get_var_ann (mergephitemp);
}
temp = mergephitemp;
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Creating phi ");
print_generic_expr (dump_file, temp, 0);
fprintf (dump_file, " to merge available but not dominating values ");
}
add_referenced_var (temp);
temp = create_phi_node (temp, block);
NECESSARY (temp) = 0;
VEC_safe_push (tree, heap, inserted_exprs, temp);
FOR_EACH_EDGE (e, ei, block->preds)
{
tree leader = bitmap_find_leader (AVAIL_OUT (e->src), val);
gcc_assert (leader);
add_phi_arg (temp, leader, e);
if (dump_file && (dump_flags & TDF_DETAILS))
{
print_generic_expr (dump_file, leader, 0);
fprintf (dump_file, " in block %d,", e->src->index);
}
}
vn_add (PHI_RESULT (temp), val);
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "\n");
}
}
}
}
static bool
try_look_through_load (tree lhs, tree mem_ref, tree stmt, basic_block block)
{
tree store_stmt = NULL;
tree rhs;
ssa_op_iter i;
tree vuse;
FOR_EACH_SSA_TREE_OPERAND (vuse, stmt, i, SSA_OP_VIRTUAL_USES)
{
tree def_stmt;
gcc_assert (TREE_CODE (vuse) == SSA_NAME);
def_stmt = SSA_NAME_DEF_STMT (vuse);
if (!def_stmt
|| TREE_CODE (def_stmt) != MODIFY_EXPR
|| !ZERO_SSA_OPERANDS (def_stmt, SSA_OP_VIRTUAL_USES))
return false;
if (store_stmt && store_stmt != def_stmt)
return false;
else
{
if (!operand_equal_p (TREE_OPERAND (def_stmt, 0), mem_ref, 0))
return false;
store_stmt = def_stmt;
}
}
rhs = TREE_OPERAND (store_stmt, 1);
if ((TREE_CODE (rhs) == SSA_NAME
&& !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs))
|| is_gimple_min_invariant (rhs)
|| TREE_CODE (rhs) == ADDR_EXPR
|| TREE_INVARIANT (rhs))
{
add_to_sets (lhs, rhs, store_stmt, TMP_GEN (block), AVAIL_OUT (block));
if (TREE_CODE (rhs) == SSA_NAME
&& !is_undefined_value (rhs))
value_insert_into_set (EXP_GEN (block), rhs);
return true;
}
return false;
}
static tree
poolify_tree (tree node)
{
switch (TREE_CODE (node))
{
case INDIRECT_REF:
{
tree temp = pool_alloc (reference_node_pool);
memcpy (temp, node, tree_size (node));
TREE_OPERAND (temp, 0) = poolify_tree (TREE_OPERAND (temp, 0));
return temp;
}
break;
case MODIFY_EXPR:
{
tree temp = pool_alloc (modify_expr_node_pool);
memcpy (temp, node, tree_size (node));
TREE_OPERAND (temp, 0) = poolify_tree (TREE_OPERAND (temp, 0));
TREE_OPERAND (temp, 1) = poolify_tree (TREE_OPERAND (temp, 1));
return temp;
}
break;
case SSA_NAME:
case INTEGER_CST:
case STRING_CST:
case REAL_CST:
case PARM_DECL:
case VAR_DECL:
case RESULT_DECL:
return node;
default:
gcc_unreachable ();
}
}
static tree modify_expr_template;
static tree
poolify_modify_expr (tree type, tree op1, tree op2)
{
if (modify_expr_template == NULL)
modify_expr_template = build2 (MODIFY_EXPR, type, op1, op2);
TREE_OPERAND (modify_expr_template, 0) = op1;
TREE_OPERAND (modify_expr_template, 1) = op2;
TREE_TYPE (modify_expr_template) = type;
return poolify_tree (modify_expr_template);
}
static void
insert_fake_stores (void)
{
basic_block block;
FOR_ALL_BB (block)
{
block_stmt_iterator bsi;
for (bsi = bsi_start (block); !bsi_end_p (bsi); bsi_next (&bsi))
{
tree stmt = bsi_stmt (bsi);
if (TREE_CODE (stmt) == MODIFY_EXPR
&& TREE_CODE (TREE_OPERAND (stmt, 0)) == INDIRECT_REF
&& !AGGREGATE_TYPE_P (TREE_TYPE (TREE_OPERAND (stmt, 0)))
&& TREE_CODE (TREE_TYPE (TREE_OPERAND (stmt, 0))) != COMPLEX_TYPE)
{
ssa_op_iter iter;
def_operand_p defp;
tree lhs = TREE_OPERAND (stmt, 0);
tree rhs = TREE_OPERAND (stmt, 1);
tree new;
bool notokay = false;
FOR_EACH_SSA_DEF_OPERAND (defp, stmt, iter, SSA_OP_VIRTUAL_DEFS)
{
tree defvar = DEF_FROM_PTR (defp);
if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (defvar))
{
notokay = true;
break;
}
}
if (notokay)
continue;
if (!storetemp || TREE_TYPE (rhs) != TREE_TYPE (storetemp))
{
storetemp = create_tmp_var (TREE_TYPE (rhs), "storetmp");
get_var_ann (storetemp);
}
new = poolify_modify_expr (TREE_TYPE (stmt), storetemp, lhs);
lhs = make_ssa_name (storetemp, new);
TREE_OPERAND (new, 0) = lhs;
create_ssa_artficial_load_stmt (new, stmt);
NECESSARY (new) = 0;
VEC_safe_push (tree, heap, inserted_exprs, new);
VEC_safe_push (tree, heap, need_creation, new);
bsi_insert_after (&bsi, new, BSI_NEW_STMT);
}
}
}
}
static void
realify_fake_stores (void)
{
unsigned int i;
tree stmt;
for (i = 0; VEC_iterate (tree, need_creation, i, stmt); i++)
{
if (NECESSARY (stmt))
{
block_stmt_iterator bsi;
tree newstmt;
add_referenced_var (SSA_NAME_VAR (TREE_OPERAND (stmt, 0)));
bsi = bsi_for_stmt (stmt);
bsi_prev (&bsi);
newstmt = build2 (MODIFY_EXPR, void_type_node,
TREE_OPERAND (stmt, 0),
TREE_OPERAND (bsi_stmt (bsi), 1));
SSA_NAME_DEF_STMT (TREE_OPERAND (newstmt, 0)) = newstmt;
bsi_insert_before (&bsi, newstmt, BSI_SAME_STMT);
bsi = bsi_for_stmt (stmt);
bsi_remove (&bsi, true);
}
else
release_defs (stmt);
}
}
static bool
try_combine_conversion (tree *expr_p)
{
tree expr = *expr_p;
tree t;
if (!((TREE_CODE (expr) == NOP_EXPR
|| TREE_CODE (expr) == CONVERT_EXPR)
&& TREE_CODE (TREE_OPERAND (expr, 0)) == VALUE_HANDLE
&& !VALUE_HANDLE_VUSES (TREE_OPERAND (expr, 0))))
return false;
t = fold_unary (TREE_CODE (expr), TREE_TYPE (expr),
VALUE_HANDLE_EXPR_SET (TREE_OPERAND (expr, 0))->head->expr);
if (!t)
return false;
STRIP_USELESS_TYPE_CONVERSION (t);
if (!(TREE_CODE (t) == VALUE_HANDLE
|| is_gimple_min_invariant (t)))
t = vn_lookup (t, NULL);
if (t && t != expr)
{
*expr_p = t;
return true;
}
return false;
}
static void
compute_avail (void)
{
basic_block block, son;
basic_block *worklist;
size_t sp = 0;
tree param;
for (param = DECL_ARGUMENTS (current_function_decl);
param;
param = TREE_CHAIN (param))
{
if (default_def (param) != NULL)
{
tree def = default_def (param);
vn_lookup_or_add (def, NULL);
bitmap_insert_into_set (TMP_GEN (ENTRY_BLOCK_PTR), def);
bitmap_value_insert_into_set (AVAIL_OUT (ENTRY_BLOCK_PTR), def);
}
}
if (cfun->static_chain_decl)
{
param = cfun->static_chain_decl;
if (default_def (param) != NULL)
{
tree def = default_def (param);
vn_lookup_or_add (def, NULL);
bitmap_insert_into_set (TMP_GEN (ENTRY_BLOCK_PTR), def);
bitmap_value_insert_into_set (AVAIL_OUT (ENTRY_BLOCK_PTR), def);
}
}
worklist = XNEWVEC (basic_block, n_basic_blocks);
for (son = first_dom_son (CDI_DOMINATORS, ENTRY_BLOCK_PTR);
son;
son = next_dom_son (CDI_DOMINATORS, son))
worklist[sp++] = son;
while (sp)
{
block_stmt_iterator bsi;
tree stmt, phi;
basic_block dom;
unsigned int stmt_uid = 1;
block = worklist[--sp];
dom = get_immediate_dominator (CDI_DOMINATORS, block);
if (dom)
bitmap_set_copy (AVAIL_OUT (block), AVAIL_OUT (dom));
if (!in_fre)
insert_extra_phis (block, dom);
for (phi = phi_nodes (block); phi; phi = PHI_CHAIN (phi))
if (is_gimple_reg (PHI_RESULT (phi)))
add_to_sets (PHI_RESULT (phi), PHI_RESULT (phi), NULL,
PHI_GEN (block), AVAIL_OUT (block));
for (bsi = bsi_start (block); !bsi_end_p (bsi); bsi_next (&bsi))
{
stmt_ann_t ann;
ssa_op_iter iter;
tree op;
stmt = bsi_stmt (bsi);
ann = stmt_ann (stmt);
ann->uid = stmt_uid++;
if (TREE_CODE (stmt) == MODIFY_EXPR
&& !ann->has_volatile_ops
&& TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME
&& !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (TREE_OPERAND (stmt, 0)))
{
tree lhs = TREE_OPERAND (stmt, 0);
tree rhs = TREE_OPERAND (stmt, 1);
if (TREE_CODE (lhs) == SSA_NAME
&& !ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_USES)
&& try_look_through_load (lhs, rhs, stmt, block))
continue;
STRIP_USELESS_TYPE_CONVERSION (rhs);
if (can_value_number_operation (rhs))
{
tree newt = create_value_expr_from (rhs, block, stmt);
if (newt)
{
if (try_combine_conversion (&newt))
vn_add (lhs, newt);
else
{
tree val = vn_lookup_or_add (newt, stmt);
vn_add (lhs, val);
value_insert_into_set (EXP_GEN (block), newt);
}
bitmap_insert_into_set (TMP_GEN (block), lhs);
bitmap_value_insert_into_set (AVAIL_OUT (block), lhs);
continue;
}
}
else if ((TREE_CODE (rhs) == SSA_NAME
&& !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs))
|| is_gimple_min_invariant (rhs)
|| TREE_CODE (rhs) == ADDR_EXPR
|| TREE_INVARIANT (rhs)
|| DECL_P (rhs))
{
add_to_sets (lhs, rhs, stmt, TMP_GEN (block),
AVAIL_OUT (block));
if (TREE_CODE (rhs) == SSA_NAME
&& !is_undefined_value (rhs))
value_insert_into_set (EXP_GEN (block), rhs);
continue;
}
}
FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF)
add_to_sets (op, op, NULL, TMP_GEN (block), AVAIL_OUT (block));
FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE)
add_to_sets (op, op, NULL, NULL , AVAIL_OUT (block));
}
for (son = first_dom_son (CDI_DOMINATORS, block);
son;
son = next_dom_son (CDI_DOMINATORS, son))
worklist[sp++] = son;
}
free (worklist);
}
static void
eliminate (void)
{
basic_block b;
FOR_EACH_BB (b)
{
block_stmt_iterator i;
for (i = bsi_start (b); !bsi_end_p (i); bsi_next (&i))
{
tree stmt = bsi_stmt (i);
if (TREE_CODE (stmt) == MODIFY_EXPR
&& TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME
&& TREE_CODE (TREE_OPERAND (stmt ,1)) != SSA_NAME
&& !is_gimple_min_invariant (TREE_OPERAND (stmt, 1))
&& !stmt_ann (stmt)->has_volatile_ops)
{
tree lhs = TREE_OPERAND (stmt, 0);
tree *rhs_p = &TREE_OPERAND (stmt, 1);
tree sprime;
sprime = bitmap_find_leader (AVAIL_OUT (b),
vn_lookup (lhs, NULL));
if (sprime
&& sprime != lhs
&& (TREE_CODE (*rhs_p) != SSA_NAME
|| may_propagate_copy (*rhs_p, sprime)))
{
gcc_assert (sprime != *rhs_p);
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Replaced ");
print_generic_expr (dump_file, *rhs_p, 0);
fprintf (dump_file, " with ");
print_generic_expr (dump_file, sprime, 0);
fprintf (dump_file, " in ");
print_generic_stmt (dump_file, stmt, 0);
}
if (TREE_CODE (sprime) == SSA_NAME)
NECESSARY (SSA_NAME_DEF_STMT (sprime)) = 1;
if (TREE_CODE (*rhs_p) != SSA_NAME
&& !tree_ssa_useless_type_conversion_1 (TREE_TYPE (*rhs_p),
TREE_TYPE (sprime)))
sprime = fold_convert (TREE_TYPE (*rhs_p), sprime);
pre_stats.eliminations++;
propagate_tree_value (rhs_p, sprime);
update_stmt (stmt);
if (maybe_clean_or_replace_eh_stmt (stmt, stmt))
{
bitmap_set_bit (need_eh_cleanup,
bb_for_stmt (stmt)->index);
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, " Removed EH side effects.\n");
}
}
}
}
}
}
static inline tree
mark_operand_necessary (tree op)
{
tree stmt;
gcc_assert (op);
if (TREE_CODE (op) != SSA_NAME)
return NULL;
stmt = SSA_NAME_DEF_STMT (op);
gcc_assert (stmt);
if (NECESSARY (stmt)
|| IS_EMPTY_STMT (stmt))
return NULL;
NECESSARY (stmt) = 1;
return stmt;
}
static void
remove_dead_inserted_code (void)
{
VEC(tree,heap) *worklist = NULL;
int i;
tree t;
worklist = VEC_alloc (tree, heap, VEC_length (tree, inserted_exprs));
for (i = 0; VEC_iterate (tree, inserted_exprs, i, t); i++)
{
if (NECESSARY (t))
VEC_quick_push (tree, worklist, t);
}
while (VEC_length (tree, worklist) > 0)
{
t = VEC_pop (tree, worklist);
if (TREE_CODE (t) == PHI_NODE)
{
int k;
VEC_reserve (tree, heap, worklist, PHI_NUM_ARGS (t));
for (k = 0; k < PHI_NUM_ARGS (t); k++)
{
tree arg = PHI_ARG_DEF (t, k);
if (TREE_CODE (arg) == SSA_NAME)
{
arg = mark_operand_necessary (arg);
if (arg)
VEC_quick_push (tree, worklist, arg);
}
}
}
else
{
ssa_op_iter iter;
tree use;
FOR_EACH_SSA_TREE_OPERAND (use, t, iter, SSA_OP_ALL_USES)
{
tree n = mark_operand_necessary (use);
if (n)
VEC_safe_push (tree, heap, worklist, n);
}
}
}
for (i = 0; VEC_iterate (tree, inserted_exprs, i, t); i++)
{
if (!NECESSARY (t))
{
block_stmt_iterator bsi;
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Removing unnecessary insertion:");
print_generic_stmt (dump_file, t, 0);
}
if (TREE_CODE (t) == PHI_NODE)
{
remove_phi_node (t, NULL);
}
else
{
bsi = bsi_for_stmt (t);
bsi_remove (&bsi, true);
release_defs (t);
}
}
}
VEC_free (tree, heap, worklist);
}
static void
init_pre (bool do_fre)
{
basic_block bb;
in_fre = do_fre;
inserted_exprs = NULL;
need_creation = NULL;
pretemp = NULL_TREE;
storetemp = NULL_TREE;
mergephitemp = NULL_TREE;
prephitemp = NULL_TREE;
vn_init ();
if (!do_fre)
current_loops = loop_optimizer_init (LOOPS_NORMAL);
connect_infinite_loops_to_exit ();
memset (&pre_stats, 0, sizeof (pre_stats));
if (!single_pred_p (single_succ (ENTRY_BLOCK_PTR)))
if (!(single_succ_edge (ENTRY_BLOCK_PTR)->flags & EDGE_ABNORMAL))
split_edge (single_succ_edge (ENTRY_BLOCK_PTR));
FOR_ALL_BB (bb)
bb->aux = xcalloc (1, sizeof (struct bb_value_sets));
bitmap_obstack_initialize (&grand_bitmap_obstack);
phi_translate_table = htab_create (511, expr_pred_trans_hash,
expr_pred_trans_eq, free);
value_set_pool = create_alloc_pool ("Value sets",
sizeof (struct value_set), 30);
bitmap_set_pool = create_alloc_pool ("Bitmap sets",
sizeof (struct bitmap_set), 30);
value_set_node_pool = create_alloc_pool ("Value set nodes",
sizeof (struct value_set_node), 30);
calculate_dominance_info (CDI_POST_DOMINATORS);
calculate_dominance_info (CDI_DOMINATORS);
binary_node_pool = create_alloc_pool ("Binary tree nodes",
tree_code_size (PLUS_EXPR), 30);
unary_node_pool = create_alloc_pool ("Unary tree nodes",
tree_code_size (NEGATE_EXPR), 30);
reference_node_pool = create_alloc_pool ("Reference tree nodes",
tree_code_size (ARRAY_REF), 30);
expression_node_pool = create_alloc_pool ("Expression tree nodes",
tree_code_size (CALL_EXPR), 30);
list_node_pool = create_alloc_pool ("List tree nodes",
tree_code_size (TREE_LIST), 30);
comparison_node_pool = create_alloc_pool ("Comparison tree nodes",
tree_code_size (EQ_EXPR), 30);
modify_expr_node_pool = create_alloc_pool ("MODIFY_EXPR nodes",
tree_code_size (MODIFY_EXPR),
30);
modify_expr_template = NULL;
FOR_ALL_BB (bb)
{
EXP_GEN (bb) = set_new (true);
PHI_GEN (bb) = bitmap_set_new ();
TMP_GEN (bb) = bitmap_set_new ();
AVAIL_OUT (bb) = bitmap_set_new ();
}
need_eh_cleanup = BITMAP_ALLOC (NULL);
}
static void
fini_pre (bool do_fre)
{
basic_block bb;
unsigned int i;
VEC_free (tree, heap, inserted_exprs);
VEC_free (tree, heap, need_creation);
bitmap_obstack_release (&grand_bitmap_obstack);
free_alloc_pool (value_set_pool);
free_alloc_pool (bitmap_set_pool);
free_alloc_pool (value_set_node_pool);
free_alloc_pool (binary_node_pool);
free_alloc_pool (reference_node_pool);
free_alloc_pool (unary_node_pool);
free_alloc_pool (list_node_pool);
free_alloc_pool (expression_node_pool);
free_alloc_pool (comparison_node_pool);
free_alloc_pool (modify_expr_node_pool);
htab_delete (phi_translate_table);
remove_fake_exit_edges ();
FOR_ALL_BB (bb)
{
free (bb->aux);
bb->aux = NULL;
}
free_dominance_info (CDI_POST_DOMINATORS);
vn_delete ();
if (!bitmap_empty_p (need_eh_cleanup))
{
tree_purge_all_dead_eh_edges (need_eh_cleanup);
cleanup_tree_cfg ();
}
BITMAP_FREE (need_eh_cleanup);
for (i = 0; i < num_ssa_names; i++)
{
tree name = ssa_name (i);
if (!name)
continue;
if (SSA_NAME_VALUE (name)
&& TREE_CODE (SSA_NAME_VALUE (name)) == VALUE_HANDLE)
SSA_NAME_VALUE (name) = NULL;
}
if (!do_fre && current_loops)
{
loop_optimizer_finalize (current_loops);
current_loops = NULL;
}
}
static void
execute_pre (bool do_fre)
{
init_pre (do_fre);
if (!do_fre)
insert_fake_stores ();
compute_avail ();
if (dump_file && (dump_flags & TDF_DETAILS))
{
basic_block bb;
FOR_ALL_BB (bb)
{
print_value_set (dump_file, EXP_GEN (bb), "exp_gen", bb->index);
bitmap_print_value_set (dump_file, TMP_GEN (bb), "tmp_gen",
bb->index);
bitmap_print_value_set (dump_file, AVAIL_OUT (bb), "avail_out",
bb->index);
}
}
if (!do_fre && n_basic_blocks < 4000)
{
vuse_names = XCNEWVEC (bitmap, num_ssa_names);
compute_rvuse_and_antic_safe ();
compute_antic ();
insert ();
free (vuse_names);
}
eliminate ();
if (dump_file && (dump_flags & TDF_STATS))
{
fprintf (dump_file, "Insertions: %d\n", pre_stats.insertions);
fprintf (dump_file, "New PHIs: %d\n", pre_stats.phis);
fprintf (dump_file, "Eliminated: %d\n", pre_stats.eliminations);
fprintf (dump_file, "Constified: %d\n", pre_stats.constified);
}
bsi_commit_edge_inserts ();
if (!do_fre)
{
remove_dead_inserted_code ();
realify_fake_stores ();
}
fini_pre (do_fre);
}
static unsigned int
do_pre (void)
{
execute_pre (false);
return 0;
}
static bool
gate_pre (void)
{
return flag_tree_pre != 0;
}
struct tree_opt_pass pass_pre =
{
"pre",
gate_pre,
do_pre,
NULL,
NULL,
0,
TV_TREE_PRE,
PROP_no_crit_edges | PROP_cfg
| PROP_ssa | PROP_alias,
0,
0,
0,
TODO_update_ssa_only_virtuals | TODO_dump_func | TODO_ggc_collect
| TODO_verify_ssa,
0
};
static unsigned int
execute_fre (void)
{
execute_pre (true);
return 0;
}
static bool
gate_fre (void)
{
return flag_tree_fre != 0;
}
struct tree_opt_pass pass_fre =
{
"fre",
gate_fre,
execute_fre,
NULL,
NULL,
0,
TV_TREE_FRE,
PROP_cfg | PROP_ssa | PROP_alias,
0,
0,
0,
TODO_dump_func | TODO_ggc_collect | TODO_verify_ssa,
0
};