we can repair later on.
3. We can do back-substitution or smarter value numbering to catch
commutative expressions split up over multiple statements.
+ 4. ANTIC_SAFE_LOADS could be a lot smarter than it is now.
+ Right now, it is simply calculating loads that occur before
+ any store in a block, instead of loads that occur before
+ stores that affect them. This is relatively more expensive, and
+ it's not clear how much more it will buy us.
*/
/* For ease of terminology, "expression node" in the below refers to
bitmap rvuse_out;
bitmap rvuse_gen;
bitmap rvuse_kill;
+
+ /* For actually occuring loads, as long as they occur before all the
+ other stores in the block, we know they are antic at the top of
+ the block, regardless of 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 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
/* This structure is used to keep track of statistics on what
optimization PRE was able to perform. */
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);
/* We can add and remove elements and entries to and from sets
if (is_gimple_min_invariant (val))
return true;
- if (set->length == 0)
+ if (!set || set->length == 0)
return false;
return value_exists_in_set_bitmap (set, val);
tree newval;
if (oldval)
{
+ /* This may seem like a weird place for this
+ check, but it's actually the easiest place to
+ do it. We can't do it lower on in the
+ recursion because it's valid for pieces of a
+ component ref to be of AGGREGATE_TYPE, as long
+ as the outermost one is not.
+ To avoid *that* case, we have a check for
+ AGGREGATE_TYPE_P in insert_aux. However, that
+ check will *not* catch this case because here
+ it occurs in the argument list. */
+ if (AGGREGATE_TYPE_P (TREE_TYPE (oldval)))
+ return NULL;
newval = phi_translate (find_leader (set, oldval),
set, pred, phiblock);
if (newval == NULL)
VEC (tree, gc) * oldvuses = NULL;
VEC (tree, gc) * newvuses = NULL;
- if (TREE_CODE (expr) != INDIRECT_REF)
+ if (TREE_CODE (expr) != INDIRECT_REF
+ && TREE_CODE (expr) != COMPONENT_REF)
return NULL;
newop1 = phi_translate (find_leader (set, oldop1),
for (i = 0; VEC_iterate (tree, vuses, i, vuse); i++)
{
- /* Any places where this is too conservative, are places
+ /* Any places where this is too conservative, are places
where we created a new version and shouldn't have. */
if (!bitmap_bit_p (RVUSE_IN (block), SSA_NAME_VERSION (vuse))
- || bitmap_bit_p (RVUSE_KILL (block), SSA_NAME_VERSION
- (vuse)))
+ || bitmap_bit_p (RVUSE_KILL (block), SSA_NAME_VERSION (vuse)))
return true;
}
return false;
case tcc_reference:
{
- if (TREE_CODE (expr) == INDIRECT_REF)
+ if (TREE_CODE (expr) == INDIRECT_REF
+ || TREE_CODE (expr) == COMPONENT_REF)
{
tree op0 = TREE_OPERAND (expr, 0);
if (is_gimple_min_invariant (op0)
{
bool retval = set_contains_value (set, op0);
if (retval)
- return !vuses_dies_in_block_x (VALUE_HANDLE_VUSES (vh),
+ {
+ return set_contains_value (ANTIC_SAFE_LOADS (block),
+ vh)
+ || !vuses_dies_in_block_x (VALUE_HANDLE_VUSES (vh),
block);
+ }
return false;
}
}
{
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);
}
VEC_free (tree, heap, phis);
}
-/* Compute reaching vuses. This is a small bit of iterative dataflow
- to determine what virtual uses reach what blocks. Because we can't
- generate overlapping virtual uses, and virtual uses *do* actually
- die, this ends up being faster in most cases than continually
- walking the virtual use/def chains to determine whether we are
- inside a block where a given virtual is still available to be
- used. */
+/* Compute reaching vuses and antic safe loads. RVUSE computation is
+ is a small bit of iterative dataflow to determine what virtual uses
+ reach what blocks. Because we can't generate overlapping virtual
+ uses, and virtual uses *do* actually die, this ends up being faster
+ in most cases than continually walking the virtual use/def chains
+ to determine whether we are inside a block where a given virtual is
+ still available to be used.
+
+ ANTIC_SAFE_LOADS are those loads that actually occur before any kill to
+ their vuses in the block,and thus, are safe at the top of the
+ block.
+
+ An example:
+
+ <block begin>
+ b = *a
+ *a = 9
+ <block end>
+
+ b = *a is an antic safe load because it still safe to consider it
+ ANTIC at the top of the block.
+
+ We currently compute a conservative approximation to
+ ANTIC_SAFE_LOADS. We compute those loads that occur before *any*
+ stores in the block. This is not because it is difficult to
+ compute the precise answer, but because it is expensive. More
+ testing is necessary to determine whether it is worth computing the
+ precise answer. */
static void
-compute_rvuse (void)
+compute_rvuse_and_antic_safe (void)
{
size_t i;
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_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;
}
-
/* Mark live on entry */
for (i = 0; i < num_ssa_names; i++)
{
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)
{
RVUSE_IN[BB] = Union of RVUSE_OUT of predecessors.
RVUSE_OUT[BB] = RVUSE_GEN[BB] U (RVUSE_IN[BB] - RVUSE_KILL[BB])
*/
- postorder = xmalloc (sizeof (int) * (n_basic_blocks - NUM_FIXED_BLOCKS));
+ postorder = XNEWVEC (int, n_basic_blocks - NUM_FIXED_BLOCKS);
pre_and_rev_post_order_compute (NULL, postorder, false);
changed = true;
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);
}
/* Return true if we can value number the call in STMT. This is true
|| BINARY_CLASS_P (op)
|| COMPARISON_CLASS_P (op)
|| TREE_CODE (op) == INDIRECT_REF
+ || TREE_CODE (op) == COMPONENT_REF
|| TREE_CODE (op) == CALL_EXPR;
}
to see which expressions need to be put into GC'able memory */
static VEC(tree, heap) *need_creation;
+/* For COMPONENT_REF's, we can't have any intermediates for the
+ COMPONENT_REF or INDIRECT_REF portion, because we'd end up with
+ trying to rename aggregates into ssa form directly, which is a no
+ no.
+
+ Thus, this routine doesn't create temporaries, it just builds a
+ single access expression for the array, calling
+ find_or_generate_expression to build the innermost pieces.
+
+ This function is a subroutine of create_expression_by_pieces, and
+ should not be called on it's own unless you really know what you
+ are doing.
+*/
+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 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 SSA_NAME:
+ return genop;
+ default:
+ gcc_unreachable ();
+ }
+
+ return NULL_TREE;
+}
/* Find a leader for an expression, or generate one using
create_expression_by_pieces if it's ANTIC but
}
break;
case tcc_reference:
- gcc_assert (TREE_CODE (expr) == INDIRECT_REF);
{
- 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);
+ if (TREE_CODE (expr) == COMPONENT_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;
}
node;
node = node->next)
{
- if (can_PRE_operation (node->expr))
+ if (can_PRE_operation (node->expr)
+ && !AGGREGATE_TYPE_P (TREE_TYPE (node->expr)))
{
tree *avail;
tree val;
FOR_EACH_EDGE (e, ei, block->preds)
{
- /* We cannot handle abnormal incomming edges correctly. */
+ /* We cannot handle abnormal incoming edges correctly. */
if (e->flags & EDGE_ABNORMAL)
return;
basic_block *worklist;
size_t sp = 0;
tree param;
-
/* For arguments with default definitions, we pretend they are
defined in the entry block. */
for (param = DECL_ARGUMENTS (current_function_decl);
block_stmt_iterator bsi;
tree stmt, phi;
basic_block dom;
+ unsigned int stmt_uid = 1;
/* Pick a block from the worklist. */
block = worklist[--sp];
stmt = bsi_stmt (bsi);
ann = stmt_ann (stmt);
+
+ ann->uid = stmt_uid++;
/* For regular value numbering, we are only interested in
assignments of the form X_i = EXPR, where EXPR represents
vn_init ();
if (!do_fre)
- current_loops = loop_optimizer_init (dump_file);
+ current_loops = loop_optimizer_init (LOOPS_NORMAL);
connect_infinite_loops_to_exit ();
memset (&pre_stats, 0, sizeof (pre_stats));
}
if (!do_fre && current_loops)
{
- loop_optimizer_finalize (current_loops, dump_file);
+ loop_optimizer_finalize (current_loops);
current_loops = NULL;
}
}
computing ANTIC, either, even though it's plenty fast. */
if (!do_fre && n_basic_blocks < 4000)
{
- vuse_names = xcalloc (num_ssa_names, sizeof (bitmap));
- compute_rvuse ();
+ vuse_names = XCNEWVEC (bitmap, num_ssa_names);
+ compute_rvuse_and_antic_safe ();
compute_antic ();
insert ();
free (vuse_names);
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
- TODO_update_ssa | TODO_dump_func | TODO_ggc_collect
+ TODO_update_ssa_only_virtuals | TODO_dump_func | TODO_ggc_collect
| TODO_verify_ssa, /* todo_flags_finish */
0 /* letter */
};
OSDN Git Service
