/* SSA-PRE for trees.
- Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009
+ Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
Free Software Foundation, Inc.
Contributed by Daniel Berlin <dan@dberlin.org> and Steven Bosscher
<stevenb@suse.de>
case REFERENCE:
{
vn_reference_t ref = PRE_EXPR_REFERENCE (e);
- VEC (vn_reference_op_s, heap) *operands = ref->operands;
- vn_reference_op_t op;
-
- /* Try to simplify the translated expression if it is
- a call to a builtin function with at most two arguments. */
- op = VEC_index (vn_reference_op_s, operands, 0);
- if (op->opcode == CALL_EXPR
- && TREE_CODE (op->op0) == ADDR_EXPR
- && TREE_CODE (TREE_OPERAND (op->op0, 0)) == FUNCTION_DECL
- && DECL_BUILT_IN (TREE_OPERAND (op->op0, 0))
- && VEC_length (vn_reference_op_s, operands) >= 2
- && VEC_length (vn_reference_op_s, operands) <= 3)
- {
- vn_reference_op_t arg0, arg1 = NULL;
- bool anyconst = false;
- arg0 = VEC_index (vn_reference_op_s, operands, 1);
- if (VEC_length (vn_reference_op_s, operands) > 2)
- arg1 = VEC_index (vn_reference_op_s, operands, 2);
- if (TREE_CODE_CLASS (arg0->opcode) == tcc_constant
- || (arg0->opcode == ADDR_EXPR
- && is_gimple_min_invariant (arg0->op0)))
- anyconst = true;
- if (arg1
- && (TREE_CODE_CLASS (arg1->opcode) == tcc_constant
- || (arg1->opcode == ADDR_EXPR
- && is_gimple_min_invariant (arg1->op0))))
- anyconst = true;
- if (anyconst)
- {
- tree folded = build_call_expr (TREE_OPERAND (op->op0, 0),
- arg1 ? 2 : 1,
- arg0->op0,
- arg1 ? arg1->op0 : NULL);
- if (folded
- && TREE_CODE (folded) == NOP_EXPR)
- folded = TREE_OPERAND (folded, 0);
- if (folded
- && is_gimple_min_invariant (folded))
- return get_or_alloc_expr_for_constant (folded);
- }
- }
- return e;
- }
+ tree folded;
+ if ((folded = fully_constant_vn_reference_p (ref)))
+ return get_or_alloc_expr_for_constant (folded);
+ return e;
+ }
default:
return e;
}
that we will return. */
if (!pretemp || exprtype != TREE_TYPE (pretemp))
{
- pretemp = create_tmp_var (exprtype, "pretmp");
+ pretemp = create_tmp_reg (exprtype, "pretmp");
get_var_ann (pretemp);
}
+static pre_expr
+phi_translate (pre_expr expr, bitmap_set_t set1, bitmap_set_t set2,
+ basic_block pred, basic_block phiblock);
/* Translate EXPR using phis in PHIBLOCK, so that it has the values of
the phis in PRED. Return NULL if we can't find a leader for each part
of the translated expression. */
static pre_expr
-phi_translate (pre_expr expr, bitmap_set_t set1, bitmap_set_t set2,
- basic_block pred, basic_block phiblock)
+phi_translate_1 (pre_expr expr, bitmap_set_t set1, bitmap_set_t set2,
+ basic_block pred, basic_block phiblock)
{
- pre_expr oldexpr = expr;
- pre_expr phitrans;
-
- if (!expr)
- return NULL;
-
- /* Constants contain no values that need translation. */
- if (expr->kind == CONSTANT)
- return expr;
-
- if (value_id_constant_p (get_expr_value_id (expr)))
- return expr;
-
- phitrans = phi_trans_lookup (expr, pred);
- if (phitrans)
- return phitrans;
-
switch (expr->kind)
{
case NARY:
}
add_to_value (new_val_id, expr);
}
- phi_trans_add (oldexpr, expr, pred);
return expr;
}
break;
ref->type,
newoperands,
&newref, true);
- if (newref)
+ if (result)
VEC_free (vn_reference_op_s, heap, newoperands);
if (result && is_gimple_min_invariant (result))
add_to_value (new_val_id, expr);
}
VEC_free (vn_reference_op_s, heap, newoperands);
- phi_trans_add (oldexpr, expr, pred);
return expr;
}
break;
}
}
+/* Wrapper around phi_translate_1 providing caching functionality. */
+
+static pre_expr
+phi_translate (pre_expr expr, bitmap_set_t set1, bitmap_set_t set2,
+ basic_block pred, basic_block phiblock)
+{
+ pre_expr phitrans;
+
+ if (!expr)
+ return NULL;
+
+ /* Constants contain no values that need translation. */
+ if (expr->kind == CONSTANT)
+ return expr;
+
+ if (value_id_constant_p (get_expr_value_id (expr)))
+ return expr;
+
+ if (expr->kind != NAME)
+ {
+ phitrans = phi_trans_lookup (expr, pred);
+ if (phitrans)
+ return phitrans;
+ }
+
+ /* Translate. */
+ phitrans = phi_translate_1 (expr, set1, set2, pred, phiblock);
+
+ /* Don't add empty translations to the cache. Neither add
+ translations of NAMEs as those are cheap to translate. */
+ if (phitrans
+ && expr->kind != NAME)
+ phi_trans_add (expr, phitrans, pred);
+
+ return phitrans;
+}
+
+
/* For each expression in SET, translate the values through phi nodes
in PHIBLOCK using edge PHIBLOCK->PRED, and store the resulting
expressions in DEST. */
{
pre_expr translated;
translated = phi_translate (expr, set, NULL, pred, phiblock);
+ if (!translated)
+ continue;
- /* Don't add empty translations to the cache */
- if (translated)
- phi_trans_add (expr, translated, pred);
-
- if (translated != NULL)
+ /* We might end up with multiple expressions from SET being
+ translated to the same value. In this case we do not want
+ to retain the NARY or REFERENCE expression but prefer a NAME
+ which would be the leader. */
+ if (translated->kind == NAME)
+ bitmap_value_replace_in_set (dest, translated);
+ else
bitmap_value_insert_into_set (dest, translated);
}
VEC_free (pre_expr, heap, exprs);
fprintf (dump_file, "Starting iteration %d\n", num_iterations);
num_iterations++;
changed = false;
- for (i = 0; i < n_basic_blocks - NUM_FIXED_BLOCKS; i++)
+ for (i = n_basic_blocks - NUM_FIXED_BLOCKS - 1; i >= 0; i--)
{
if (TEST_BIT (changed_blocks, postorder[i]))
{
fprintf (dump_file, "Starting iteration %d\n", num_iterations);
num_iterations++;
changed = false;
- for (i = 0; i < n_basic_blocks - NUM_FIXED_BLOCKS; i++)
+ for (i = n_basic_blocks - NUM_FIXED_BLOCKS - 1 ; i >= 0; i--)
{
if (TEST_BIT (changed_blocks, postorder[i]))
{
{
case CALL_EXPR:
{
- tree folded, sc = currop->op1;
+ tree folded, sc = NULL_TREE;
unsigned int nargs = 0;
- tree *args = XNEWVEC (tree, VEC_length (vn_reference_op_s,
- ref->operands) - 1);
+ tree fn, *args;
+ if (TREE_CODE (currop->op0) == FUNCTION_DECL)
+ fn = currop->op0;
+ else
+ {
+ pre_expr op0 = get_or_alloc_expr_for (currop->op0);
+ fn = find_or_generate_expression (block, op0, stmts, domstmt);
+ if (!fn)
+ return NULL_TREE;
+ }
+ if (currop->op1)
+ {
+ pre_expr scexpr = get_or_alloc_expr_for (currop->op1);
+ sc = find_or_generate_expression (block, scexpr, stmts, domstmt);
+ if (!sc)
+ return NULL_TREE;
+ }
+ args = XNEWVEC (tree, VEC_length (vn_reference_op_s,
+ ref->operands) - 1);
while (*operand < VEC_length (vn_reference_op_s, ref->operands))
{
args[nargs] = create_component_ref_by_pieces_1 (block, ref,
operand, stmts,
domstmt);
+ if (!args[nargs])
+ {
+ free (args);
+ return NULL_TREE;
+ }
nargs++;
}
folded = build_call_array (currop->type,
- TREE_CODE (currop->op0) == FUNCTION_DECL
- ? build_fold_addr_expr (currop->op0)
- : currop->op0,
+ (TREE_CODE (fn) == FUNCTION_DECL
+ ? build_fold_addr_expr (fn) : fn),
nargs, args);
free (args);
if (sc)
- {
- pre_expr scexpr = get_or_alloc_expr_for (sc);
- sc = find_or_generate_expression (block, scexpr, stmts, domstmt);
- if (!sc)
- return NULL_TREE;
- CALL_EXPR_STATIC_CHAIN (folded) = sc;
- }
+ CALL_EXPR_STATIC_CHAIN (folded) = sc;
return folded;
}
break;
return NULL_TREE;
if (genop2)
{
- op2expr = get_or_alloc_expr_for (genop2);
- genop2 = find_or_generate_expression (block, op2expr, stmts,
- domstmt);
- if (!genop2)
- return NULL_TREE;
+ /* Drop zero minimum index. */
+ if (tree_int_cst_equal (genop2, integer_zero_node))
+ genop2 = NULL_TREE;
+ else
+ {
+ op2expr = get_or_alloc_expr_for (genop2);
+ genop2 = find_or_generate_expression (block, op2expr, stmts,
+ domstmt);
+ if (!genop2)
+ return NULL_TREE;
+ }
}
if (genop3)
{
tree elmt_type = TREE_TYPE (TREE_TYPE (genop0));
- genop3 = size_binop (EXACT_DIV_EXPR, genop3,
- size_int (TYPE_ALIGN_UNIT (elmt_type)));
- op3expr = get_or_alloc_expr_for (genop3);
- genop3 = find_or_generate_expression (block, op3expr, stmts,
- domstmt);
- if (!genop3)
- return NULL_TREE;
+ /* We can't always put a size in units of the element alignment
+ here as the element alignment may be not visible. See
+ PR43783. Simply drop the element size for constant
+ sizes. */
+ if (tree_int_cst_equal (genop3, TYPE_SIZE_UNIT (elmt_type)))
+ genop3 = NULL_TREE;
+ else
+ {
+ genop3 = size_binop (EXACT_DIV_EXPR, genop3,
+ size_int (TYPE_ALIGN_UNIT (elmt_type)));
+ op3expr = get_or_alloc_expr_for (genop3);
+ genop3 = find_or_generate_expression (block, op3expr, stmts,
+ domstmt);
+ if (!genop3)
+ return NULL_TREE;
+ }
}
return build4 (currop->opcode, currop->type, genop0, genop1,
genop2, genop3);
stmts, domstmt);
if (!genop1 || !genop2)
return NULL_TREE;
- genop1 = fold_convert (TREE_TYPE (nary->op[0]),
- genop1);
/* Ensure op2 is a sizetype for POINTER_PLUS_EXPR. It
may be a constant with the wrong type. */
if (nary->opcode == POINTER_PLUS_EXPR)
- genop2 = fold_convert (sizetype, genop2);
+ {
+ genop1 = fold_convert (nary->type, genop1);
+ genop2 = fold_convert (sizetype, genop2);
+ }
else
- genop2 = fold_convert (TREE_TYPE (nary->op[1]), genop2);
+ {
+ genop1 = fold_convert (TREE_TYPE (nary->op[0]), genop1);
+ genop2 = fold_convert (TREE_TYPE (nary->op[1]), genop2);
+ }
folded = fold_build2 (nary->opcode, nary->type,
genop1, genop2);
that we will return. */
if (!pretemp || exprtype != TREE_TYPE (pretemp))
{
- pretemp = create_tmp_var (exprtype, "pretmp");
+ pretemp = create_tmp_reg (exprtype, "pretmp");
get_var_ann (pretemp);
}
temp = pretemp;
add_referenced_var (temp);
- if (TREE_CODE (exprtype) == COMPLEX_TYPE
- || TREE_CODE (exprtype) == VECTOR_TYPE)
- DECL_GIMPLE_REG_P (temp) = 1;
-
newstmt = gimple_build_assign (temp, folded);
name = make_ssa_name (temp, newstmt);
gimple_assign_set_lhs (newstmt, name);
for (i = 0; VEC_iterate (gimple, to_remove, i, stmt); ++i)
{
tree lhs = gimple_assign_lhs (stmt);
+ tree rhs = gimple_assign_rhs1 (stmt);
use_operand_p use_p;
gimple use_stmt;
/* If there is a single use only, propagate the equivalency
instead of keeping the copy. */
if (TREE_CODE (lhs) == SSA_NAME
+ && TREE_CODE (rhs) == SSA_NAME
&& single_imm_use (lhs, &use_p, &use_stmt)
- && may_propagate_copy (USE_FROM_PTR (use_p),
- gimple_assign_rhs1 (stmt)))
+ && may_propagate_copy (USE_FROM_PTR (use_p), rhs))
{
SET_USE (use_p, gimple_assign_rhs1 (stmt));
update_stmt (use_stmt);
VEC_free (gimple, heap, worklist);
}
+/* Compute a reverse post-order in *POST_ORDER. If INCLUDE_ENTRY_EXIT is
+ true, then then ENTRY_BLOCK and EXIT_BLOCK are included. Returns
+ the number of visited blocks. */
+
+static int
+my_rev_post_order_compute (int *post_order, bool include_entry_exit)
+{
+ edge_iterator *stack;
+ int sp;
+ int post_order_num = 0;
+ sbitmap visited;
+
+ if (include_entry_exit)
+ post_order[post_order_num++] = EXIT_BLOCK;
+
+ /* Allocate stack for back-tracking up CFG. */
+ stack = XNEWVEC (edge_iterator, n_basic_blocks + 1);
+ sp = 0;
+
+ /* Allocate bitmap to track nodes that have been visited. */
+ visited = sbitmap_alloc (last_basic_block);
+
+ /* None of the nodes in the CFG have been visited yet. */
+ sbitmap_zero (visited);
+
+ /* Push the last edge on to the stack. */
+ stack[sp++] = ei_start (EXIT_BLOCK_PTR->preds);
+
+ while (sp)
+ {
+ edge_iterator ei;
+ basic_block src;
+ basic_block dest;
+
+ /* Look at the edge on the top of the stack. */
+ ei = stack[sp - 1];
+ src = ei_edge (ei)->src;
+ dest = ei_edge (ei)->dest;
+
+ /* Check if the edge destination has been visited yet. */
+ if (src != ENTRY_BLOCK_PTR && ! TEST_BIT (visited, src->index))
+ {
+ /* Mark that we have visited the destination. */
+ SET_BIT (visited, src->index);
+
+ if (EDGE_COUNT (src->preds) > 0)
+ /* Since the DEST node has been visited for the first
+ time, check its successors. */
+ stack[sp++] = ei_start (src->preds);
+ else
+ post_order[post_order_num++] = src->index;
+ }
+ else
+ {
+ if (ei_one_before_end_p (ei) && dest != EXIT_BLOCK_PTR)
+ post_order[post_order_num++] = dest->index;
+
+ if (!ei_one_before_end_p (ei))
+ ei_next (&stack[sp - 1]);
+ else
+ sp--;
+ }
+ }
+
+ if (include_entry_exit)
+ post_order[post_order_num++] = ENTRY_BLOCK;
+
+ free (stack);
+ sbitmap_free (visited);
+ return post_order_num;
+}
+
+
/* Initialize data structures used by PRE. */
static void
postorder = XNEWVEC (int, n_basic_blocks - NUM_FIXED_BLOCKS);
- post_order_compute (postorder, false, false);
+ my_rev_post_order_compute (postorder, false);
FOR_ALL_BB (bb)
bb->aux = XCNEWVEC (struct bb_bitmap_sets, 1);
OSDN Git Service
