#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 "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"
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;
} *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 NEW_SETS(BB) ((bb_value_sets_t) ((BB)->aux))->new_sets
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 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 bitmap_obstack grand_bitmap_obstack;
static bitmap need_eh_cleanup;
static htab_t phi_translate_table;
typedef struct expr_pred_trans_d
{
tree e;
basic_block pred;
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;
if (b1 != b2)
return false;
if (expressions_equal_p (ve1->e, ve2->e))
return true;
return false;
}
static inline tree
phi_trans_lookup (tree e, basic_block pred)
{
void **slot;
struct expr_pred_trans_d ept;
ept.e = e;
ept.pred = pred;
ept.hashcode = vn_compute (e, (unsigned long) pred, NULL);
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)
{
void **slot;
expr_pred_trans_t new_pair = xmalloc (sizeof (*new_pair));
new_pair->e = e;
new_pair->pred = pred;
new_pair->v = v;
new_pair->hashcode = vn_compute (e, (unsigned long) pred, NULL);
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 = 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 = 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 = 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
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->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
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;
phitrans = phi_trans_lookup (expr, pred);
if (phitrans)
return phitrans;
switch (TREE_CODE_CLASS (TREE_CODE (expr)))
{
case tcc_reference:
return NULL;
case tcc_binary:
{
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)
{
newexpr = pool_alloc (binary_node_pool);
memcpy (newexpr, expr, tree_size (expr));
create_tree_ann (newexpr);
TREE_OPERAND (newexpr, 0) = newop1 == oldop1 ? oldop1 : get_value_handle (newop1);
TREE_OPERAND (newexpr, 1) = newop2 == oldop2 ? oldop2 : get_value_handle (newop2);
vn_lookup_or_add (newexpr, NULL);
expr = newexpr;
phi_trans_add (oldexpr, newexpr, pred);
}
}
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)
{
newexpr = pool_alloc (unary_node_pool);
memcpy (newexpr, expr, tree_size (expr));
create_tree_ann (newexpr);
TREE_OPERAND (newexpr, 0) = get_value_handle (newop1);
vn_lookup_or_add (newexpr, NULL);
expr = newexpr;
phi_trans_add (oldexpr, newexpr, pred);
}
}
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);
phi_trans_add (node->expr, translated, pred);
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 bool
valid_in_set (value_set_t set, tree expr)
{
switch (TREE_CODE_CLASS (TREE_CODE (expr)))
{
case tcc_binary:
{
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_reference:
return false;
case tcc_exceptional:
gcc_assert (TREE_CODE (expr) == SSA_NAME);
return true;
case tcc_declaration:
return false;
default:
gcc_unreachable ();
}
}
static void
clean (value_set_t set)
{
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))
set_remove (set, node->expr);
node = next;
}
}
DEF_VEC_MALLOC_P (basic_block);
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 (EDGE_COUNT (block->succs) == 1)
{
phi_translate_set (ANTIC_OUT, ANTIC_IN(EDGE_SUCC (block, 0)->dest),
block, EDGE_SUCC (block, 0)->dest);
}
else
{
VEC (basic_block) * worklist;
edge e;
size_t i;
basic_block bprime, first;
edge_iterator ei;
worklist = VEC_alloc (basic_block, 2);
FOR_EACH_EDGE (e, ei, block->succs)
VEC_safe_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, 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));
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);
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 VEC(tree_on_heap) *inserted_exprs;
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 (UNARY_CLASS_P (genop)
|| BINARY_CLASS_P (genop)
|| REFERENCE_CLASS_P (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 name = NULL_TREE;
tree newexpr = NULL_TREE;
tree v;
switch (TREE_CODE_CLASS (TREE_CODE (expr)))
{
case tcc_binary:
{
tree_stmt_iterator tsi;
tree forced_stmts;
tree genop1, genop2;
tree temp;
tree folded;
tree op1 = TREE_OPERAND (expr, 0);
tree op2 = TREE_OPERAND (expr, 1);
genop1 = find_or_generate_expression (block, op1, stmts);
genop2 = find_or_generate_expression (block, op2, stmts);
temp = create_tmp_var (TREE_TYPE (expr), "pretmp");
add_referenced_tmp_var (temp);
folded = fold (build (TREE_CODE (expr), TREE_TYPE (expr),
genop1, genop2));
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_on_heap, inserted_exprs, stmt);
vn_add (forcedname, val, NULL);
bitmap_value_replace_in_set (NEW_SETS (block), forcedname);
bitmap_value_replace_in_set (AVAIL_OUT (block), forcedname);
}
tsi = tsi_last (stmts);
tsi_link_after (&tsi, forced_stmts, TSI_CONTINUE_LINKING);
}
newexpr = build (MODIFY_EXPR, TREE_TYPE (expr),
temp, newexpr);
NECESSARY (newexpr) = 0;
name = make_ssa_name (temp, newexpr);
TREE_OPERAND (newexpr, 0) = name;
tsi = tsi_last (stmts);
tsi_link_after (&tsi, newexpr, TSI_CONTINUE_LINKING);
VEC_safe_push (tree_on_heap, inserted_exprs, newexpr);
pre_stats.insertions++;
break;
}
case tcc_unary:
{
tree_stmt_iterator tsi;
tree forced_stmts = NULL;
tree genop1;
tree temp;
tree folded;
tree op1 = TREE_OPERAND (expr, 0);
genop1 = find_or_generate_expression (block, op1, stmts);
temp = create_tmp_var (TREE_TYPE (expr), "pretmp");
add_referenced_tmp_var (temp);
folded = fold (build (TREE_CODE (expr), TREE_TYPE (expr),
genop1));
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_on_heap, inserted_exprs, stmt);
vn_add (forcedname, val, NULL);
bitmap_value_replace_in_set (NEW_SETS (block), forcedname);
bitmap_value_replace_in_set (AVAIL_OUT (block), forcedname);
}
tsi = tsi_last (stmts);
tsi_link_after (&tsi, forced_stmts, TSI_CONTINUE_LINKING);
}
newexpr = build (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_on_heap, inserted_exprs, newexpr);
pre_stats.insertions++;
break;
}
default:
gcc_unreachable ();
}
v = get_value_handle (expr);
vn_add (name, v, NULL);
bitmap_value_replace_in_set (NEW_SETS (block), name);
bitmap_value_replace_in_set (AVAIL_OUT (block), name);
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 tree
fully_constant_expression (tree t)
{
tree folded;
folded = fold (t);
if (folded && is_gimple_min_invariant (folded))
return folded;
return t;
}
static bool
insert_into_preds_of_block (basic_block block, value_set_node_t node,
tree *avail, const char *tmpname)
{
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, "\n");
}
if (block->loop_depth > 0 && EDGE_COUNT (block->preds) == 2)
{
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 (BINARY_CLASS_P (eprime)
|| UNARY_CLASS_P (eprime))
{
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;
temp = create_tmp_var (type, tmpname);
add_referenced_tmp_var (temp);
temp = create_phi_node (temp, block);
NECESSARY (temp) = 0;
VEC_safe_push (tree_on_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, NULL);
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 (EDGE_COUNT (block->preds) > 1)
{
value_set_node_t node;
for (node = ANTIC_IN (block)->head;
node;
node = node->next)
{
if (BINARY_CLASS_P (node->expr)
|| UNARY_CLASS_P (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 = xcalloc (last_basic_block, sizeof (tree));
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,
"prephitmp"))
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, NULL);
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, vuse_optype vuses, bitmap_set_t s1,
bitmap_set_t s2)
{
tree val = vn_lookup_or_add (expr, vuses);
if (var != expr)
vn_add (var, val, NULL);
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, vuse_optype vuses)
{
int i;
enum tree_code code = TREE_CODE (expr);
tree vexpr;
gcc_assert (TREE_CODE_CLASS (code) == tcc_unary
|| TREE_CODE_CLASS (code) == tcc_binary
|| TREE_CODE_CLASS (code) == tcc_reference);
if (TREE_CODE_CLASS (code) == tcc_unary)
vexpr = pool_alloc (unary_node_pool);
else if (TREE_CODE_CLASS (code) == tcc_reference)
vexpr = pool_alloc (reference_node_pool);
else
vexpr = pool_alloc (binary_node_pool);
memcpy (vexpr, expr, tree_size (expr));
for (i = 0; i < TREE_CODE_LENGTH (code); i++)
{
tree op = TREE_OPERAND (expr, i);
if (op != NULL)
{
tree val = vn_lookup_or_add (op, vuses);
if (!is_undefined_value (op))
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
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 val;
tree def = default_def (param);
val = 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 = xmalloc (sizeof (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;
block = worklist[--sp];
dom = get_immediate_dominator (CDI_DOMINATORS, block);
if (dom)
bitmap_set_copy (AVAIL_OUT (block), AVAIL_OUT (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;
size_t j;
stmt = bsi_stmt (bsi);
ann = stmt_ann (stmt);
get_stmt_operands (stmt);
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);
vuse_optype vuses = STMT_VUSE_OPS (stmt);
STRIP_USELESS_TYPE_CONVERSION (rhs);
if (TREE_CODE (rhs) == SSA_NAME
|| is_gimple_min_invariant (rhs))
{
add_to_sets (lhs, rhs, vuses, 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;
}
else if (UNARY_CLASS_P (rhs) || BINARY_CLASS_P (rhs)
|| TREE_CODE (rhs) == INDIRECT_REF)
{
tree newt = create_value_expr_from (rhs, block, vuses);
add_to_sets (lhs, newt, vuses, TMP_GEN (block),
AVAIL_OUT (block));
value_insert_into_set (EXP_GEN (block), newt);
continue;
}
}
for (j = 0; j < NUM_DEFS (STMT_DEF_OPS (stmt)); j++)
{
tree def = DEF_OP (STMT_DEF_OPS (stmt), j);
add_to_sets (def, def, NULL, TMP_GEN (block),
AVAIL_OUT (block));
}
for (j = 0; j < NUM_USES (STMT_USE_OPS (stmt)); j++)
{
tree use = USE_OP (STMT_USE_OPS (stmt), j);
add_to_sets (use, use, 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;
pre_stats.eliminations++;
propagate_tree_value (rhs_p, sprime);
modify_stmt (stmt);
if (maybe_clean_eh_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 void
mark_operand_necessary (tree op, VEC(tree_on_heap) **worklist)
{
tree stmt;
int ver;
gcc_assert (op);
ver = SSA_NAME_VERSION (op);
stmt = SSA_NAME_DEF_STMT (op);
gcc_assert (stmt);
if (NECESSARY (stmt)
|| IS_EMPTY_STMT (stmt))
return;
NECESSARY (stmt) = 1;
VEC_safe_push (tree_on_heap, *worklist, stmt);
}
static void
remove_dead_inserted_code (void)
{
VEC (tree_on_heap) *worklist = NULL;
int i;
tree t;
for (i = 0; VEC_iterate (tree_on_heap, inserted_exprs, i, t); i++)
{
if (NECESSARY (t))
VEC_safe_push (tree_on_heap, worklist, t);
}
while (VEC_length (tree_on_heap, worklist) > 0)
{
t = VEC_pop (tree_on_heap, worklist);
if (TREE_CODE (t) == PHI_NODE)
{
int k;
for (k = 0; k < PHI_NUM_ARGS (t); k++)
{
tree arg = PHI_ARG_DEF (t, k);
if (TREE_CODE (arg) == SSA_NAME)
mark_operand_necessary (arg, &worklist);
}
}
else
{
ssa_op_iter iter;
tree use;
get_stmt_operands (t);
FOR_EACH_SSA_TREE_OPERAND (use, t, iter, SSA_OP_ALL_USES)
mark_operand_necessary (use, &worklist);
}
}
for (i = 0; VEC_iterate (tree_on_heap, 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, bb_for_stmt (t));
}
else
{
bsi = bsi_for_stmt (t);
bsi_remove (&bsi);
}
}
}
VEC_free (tree_on_heap, worklist);
}
static void
init_pre (bool do_fre)
{
basic_block bb;
inserted_exprs = NULL;
vn_init ();
if (!do_fre)
current_loops = loop_optimizer_init (dump_file);
connect_infinite_loops_to_exit ();
memset (&pre_stats, 0, sizeof (pre_stats));
if (EDGE_COUNT (EDGE_SUCC (ENTRY_BLOCK_PTR, 0)->dest->preds) > 1)
if (!(EDGE_SUCC (ENTRY_BLOCK_PTR, 0)->flags & EDGE_ABNORMAL))
split_edge (EDGE_SUCC (ENTRY_BLOCK_PTR, 0));
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);
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_on_heap, inserted_exprs);
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);
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, dump_file);
current_loops = NULL;
}
}
static void
execute_pre (bool do_fre)
{
init_pre (do_fre);
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)
{
compute_antic ();
insert ();
}
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 ();
fini_pre (do_fre);
}
static void
do_pre (void)
{
execute_pre (false);
}
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_dump_func | TODO_ggc_collect | TODO_verify_ssa,
0
};
static void
do_fre (void)
{
execute_pre (true);
}
static bool
gate_fre (void)
{
return flag_tree_fre != 0;
}
struct tree_opt_pass pass_fre =
{
"fre",
gate_fre,
do_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
};