* [PATCH] PRE TLC
@ 2014-09-02 14:08 Richard Biener
0 siblings, 0 replies; 5+ messages in thread
From: Richard Biener @ 2014-09-02 14:08 UTC (permalink / raw)
To: gcc-patches
The following patch removes dead code (blocks are never defered
because we iterate in a proper CFG order now) and avoids building
up the el_avail vector one element at a time.
Bootstrapped on x86_64-unknown-linux-gnu, testing in progress.
Richard.
2014-09-02 Richard Biener <rguenther@suse.de>
* tree-ssa-pre.c (alloc_expression_id): Use quick_grow_cleared.
(struct bb_bitmap_sets): Remove deferred member.
(BB_DEFERRED): Remove.
(defer_or_phi_translate_block): Remove.
(compute_antic_aux): Remove deferring of blocks, assert
proper iteration order.
(compute_antic): Do not set BB_DEFERRED.
(eliminate): Allocate el_avail of proper size initially.
Index: gcc/tree-ssa-pre.c
===================================================================
--- gcc/tree-ssa-pre.c.orig 2014-09-02 16:01:08.733146617 +0200
+++ gcc/tree-ssa-pre.c 2014-09-02 15:56:23.687166242 +0200
@@ -272,11 +272,10 @@ alloc_expression_id (pre_expr expr)
{
unsigned version = SSA_NAME_VERSION (PRE_EXPR_NAME (expr));
/* vec::safe_grow_cleared allocates no headroom. Avoid frequent
- re-allocations by using vec::reserve upfront. There is no
- vec::quick_grow_cleared unfortunately. */
+ re-allocations by using vec::reserve upfront. */
unsigned old_len = name_to_id.length ();
name_to_id.reserve (num_ssa_names - old_len);
- name_to_id.safe_grow_cleared (num_ssa_names);
+ name_to_id.quick_grow_cleared (num_ssa_names);
gcc_assert (name_to_id[version] == 0);
name_to_id[version] = expr->id;
}
@@ -427,10 +426,6 @@ typedef struct bb_bitmap_sets
/* True if we have visited this block during ANTIC calculation. */
unsigned int visited : 1;
- /* True we have deferred processing this block during ANTIC
- calculation until its successor is processed. */
- unsigned int deferred : 1;
-
/* True when the block contains a call that might not return. */
unsigned int contains_may_not_return_call : 1;
} *bb_value_sets_t;
@@ -444,7 +439,6 @@ typedef struct bb_bitmap_sets
#define NEW_SETS(BB) ((bb_value_sets_t) ((BB)->aux))->new_sets
#define EXPR_DIES(BB) ((bb_value_sets_t) ((BB)->aux))->expr_dies
#define BB_VISITED(BB) ((bb_value_sets_t) ((BB)->aux))->visited
-#define BB_DEFERRED(BB) ((bb_value_sets_t) ((BB)->aux))->deferred
#define BB_MAY_NOTRETURN(BB) ((bb_value_sets_t) ((BB)->aux))->contains_may_not_return_call
@@ -2085,26 +2079,6 @@ static sbitmap has_abnormal_preds;
static sbitmap changed_blocks;
-/* Decide whether to defer a block for a later iteration, or PHI
- translate SOURCE to DEST using phis in PHIBLOCK. Return false if we
- should defer the block, and true if we processed it. */
-
-static bool
-defer_or_phi_translate_block (bitmap_set_t dest, bitmap_set_t source,
- basic_block block, basic_block phiblock)
-{
- if (!BB_VISITED (phiblock))
- {
- bitmap_set_bit (changed_blocks, block->index);
- BB_VISITED (block) = 0;
- BB_DEFERRED (block) = 1;
- return false;
- }
- else
- phi_translate_set (dest, source, block, phiblock);
- return true;
-}
-
/* Compute the ANTIC set for BLOCK.
If succs(BLOCK) > 1 then
@@ -2144,30 +2118,8 @@ compute_antic_aux (basic_block block, bo
else if (single_succ_p (block))
{
basic_block succ_bb = single_succ (block);
-
- /* We trade iterations of the dataflow equations for having to
- phi translate the maximal set, which is incredibly slow
- (since the maximal set often has 300+ members, even when you
- have a small number of blocks).
- Basically, we defer the computation of ANTIC for this block
- until we have processed it's successor, which will inevitably
- have a *much* smaller set of values to phi translate once
- clean has been run on it.
- The cost of doing this is that we technically perform more
- iterations, however, they are lower cost iterations.
-
- Timings for PRE on tramp3d-v4:
- without maximal set fix: 11 seconds
- with maximal set fix/without deferring: 26 seconds
- with maximal set fix/with deferring: 11 seconds
- */
-
- if (!defer_or_phi_translate_block (ANTIC_OUT, ANTIC_IN (succ_bb),
- block, succ_bb))
- {
- changed = true;
- goto maybe_dump_sets;
- }
+ gcc_assert (BB_VISITED (succ_bb));
+ phi_translate_set (ANTIC_OUT, ANTIC_IN (succ_bb), block, succ_bb);
}
/* If we have multiple successors, we take the intersection of all of
them. Note that in the case of loop exit phi nodes, we may have
@@ -2187,20 +2139,11 @@ compute_antic_aux (basic_block block, bo
worklist.quick_push (e->dest);
}
- /* Of multiple successors we have to have visited one already. */
- if (!first)
- {
- bitmap_set_bit (changed_blocks, block->index);
- BB_VISITED (block) = 0;
- BB_DEFERRED (block) = 1;
- changed = true;
- goto maybe_dump_sets;
- }
+ /* Of multiple successors we have to have visited one already
+ which is guaranteed by iteration order. */
+ gcc_assert (first != NULL);
- if (!gimple_seq_empty_p (phi_nodes (first)))
- phi_translate_set (ANTIC_OUT, ANTIC_IN (first), block, first);
- else
- bitmap_set_copy (ANTIC_OUT, ANTIC_IN (first));
+ phi_translate_set (ANTIC_OUT, ANTIC_IN (first), block, first);
FOR_EACH_VEC_ELT (worklist, i, bprime)
{
@@ -2248,23 +2191,14 @@ compute_antic_aux (basic_block block, bo
maybe_dump_sets:
if (dump_file && (dump_flags & TDF_DETAILS))
{
- if (!BB_DEFERRED (block) || BB_VISITED (block))
- {
- if (ANTIC_OUT)
- print_bitmap_set (dump_file, ANTIC_OUT, "ANTIC_OUT", block->index);
+ if (ANTIC_OUT)
+ print_bitmap_set (dump_file, ANTIC_OUT, "ANTIC_OUT", block->index);
- print_bitmap_set (dump_file, ANTIC_IN (block), "ANTIC_IN",
- block->index);
+ print_bitmap_set (dump_file, ANTIC_IN (block), "ANTIC_IN",
+ block->index);
- if (S)
- print_bitmap_set (dump_file, S, "S", block->index);
- }
- else
- {
- fprintf (dump_file,
- "Block %d was deferred for a future iteration.\n",
- block->index);
- }
+ if (S)
+ print_bitmap_set (dump_file, S, "S", block->index);
}
if (old)
bitmap_set_free (old);
@@ -2446,7 +2380,6 @@ compute_antic (void)
}
BB_VISITED (block) = 0;
- BB_DEFERRED (block) = 0;
/* While we are here, give empty ANTIC_IN sets to each block. */
ANTIC_IN (block) = bitmap_set_new ();
@@ -4503,7 +4436,7 @@ eliminate (bool do_pre)
el_to_remove.create (0);
el_todo = 0;
- el_avail.create (0);
+ el_avail.create (num_ssa_names);
el_avail_stack.create (0);
eliminate_dom_walker (CDI_DOMINATORS,
^ permalink raw reply [flat|nested] 5+ messages in thread
* [PATCH] PRE TLC
@ 2017-05-05 12:13 Richard Biener
0 siblings, 0 replies; 5+ messages in thread
From: Richard Biener @ 2017-05-05 12:13 UTC (permalink / raw)
To: gcc-patches
Bootstrapped and tested on x86_64-unknown-linux-gnu, applied.
Richard.
2017-05-05 Richard Biener <rguenther@suse.de>
* tree-ssa-pre.c (get_or_alloc_expr_for): Simplify.
Index: gcc/tree-ssa-pre.c
===================================================================
--- gcc/tree-ssa-pre.c (revision 247577)
+++ gcc/tree-ssa-pre.c (working copy)
@@ -1173,31 +1173,7 @@ get_or_alloc_expr_for (tree t)
return get_or_alloc_expr_for_name (t);
else if (is_gimple_min_invariant (t))
return get_or_alloc_expr_for_constant (t);
- else
- {
- /* More complex expressions can result from SCCVN expression
- simplification that inserts values for them. As they all
- do not have VOPs the get handled by the nary ops struct. */
- vn_nary_op_t result;
- unsigned int result_id;
- vn_nary_op_lookup (t, &result);
- if (result != NULL)
- {
- pre_expr e = pre_expr_pool.allocate ();
- e->kind = NARY;
- PRE_EXPR_NARY (e) = result;
- result_id = lookup_expression_id (e);
- if (result_id != 0)
- {
- pre_expr_pool.remove (e);
- e = expression_for_id (result_id);
- return e;
- }
- alloc_expression_id (e);
- return e;
- }
- }
- return NULL;
+ gcc_unreachable ();
}
/* Return the folded version of T if T, when folded, is a gimple
^ permalink raw reply [flat|nested] 5+ messages in thread
* [PATCH] PRE TLC
@ 2012-11-29 13:52 Richard Biener
0 siblings, 0 replies; 5+ messages in thread
From: Richard Biener @ 2012-11-29 13:52 UTC (permalink / raw)
To: gcc-patches
When working on PR55124 I noticed we do some useless work in PRE.
This cleans it up and makes it more obvious what we do in compute_avail.
Bootstrapped and tested on x86_64-unknown-linux-gnu, applied to trunk.
Richard.
2012-11-29 Richard Biener <rguenther@suse.de>
* tree-ssa-pre.c (get_expr_value_id): Do not add expr
to the set of value expressions here.
(add_to_exp_gen, make_values_for_phi): Fold into ...
(compute_avail): ... here, and avoid useless work. Dump
avail sets in processing order.
(do_pre): Do not dump avail sets here.
Index: gcc/tree-ssa-pre.c
===================================================================
--- gcc/tree-ssa-pre.c (revision 193932)
+++ gcc/tree-ssa-pre.c (working copy)
@@ -612,28 +612,28 @@ bitmap_set_new (void)
static unsigned int
get_expr_value_id (pre_expr expr)
{
+ unsigned int id;
switch (expr->kind)
{
case CONSTANT:
- {
- unsigned int id;
- id = get_constant_value_id (PRE_EXPR_CONSTANT (expr));
- if (id == 0)
- {
- id = get_or_alloc_constant_value_id (PRE_EXPR_CONSTANT (expr));
- add_to_value (id, expr);
- }
- return id;
- }
+ id = get_or_alloc_constant_value_id (PRE_EXPR_CONSTANT (expr));
+ break;
case NAME:
- return VN_INFO (PRE_EXPR_NAME (expr))->value_id;
+ id = VN_INFO (PRE_EXPR_NAME (expr))->value_id;
+ break;
case NARY:
- return PRE_EXPR_NARY (expr)->value_id;
+ id = PRE_EXPR_NARY (expr)->value_id;
+ break;
case REFERENCE:
- return PRE_EXPR_REFERENCE (expr)->value_id;
+ id = PRE_EXPR_REFERENCE (expr)->value_id;
+ break;
default:
gcc_unreachable ();
}
+ /* ??? We cannot assert that expr has a value-id (it can be 0), because
+ we assign value-ids only to expressions that have a result
+ in set_hashtable_value_ids. */
+ return id;
}
/* Return a SCCVN valnum (SSA name or constant) for the PRE value-id VAL. */
@@ -3624,48 +3624,6 @@ insert (void)
}
-/* Add OP to EXP_GEN (block), and possibly to the maximal set. */
-
-static void
-add_to_exp_gen (basic_block block, tree op)
-{
- pre_expr result;
-
- if (TREE_CODE (op) == SSA_NAME && ssa_undefined_value_p (op))
- return;
-
- result = get_or_alloc_expr_for_name (op);
- bitmap_value_insert_into_set (EXP_GEN (block), result);
-}
-
-/* Create value ids for PHI in BLOCK. */
-
-static void
-make_values_for_phi (gimple phi, basic_block block)
-{
- tree result = gimple_phi_result (phi);
- unsigned i;
-
- /* We have no need for virtual phis, as they don't represent
- actual computations. */
- if (virtual_operand_p (result))
- return;
-
- pre_expr e = get_or_alloc_expr_for_name (result);
- add_to_value (get_expr_value_id (e), e);
- bitmap_value_insert_into_set (AVAIL_OUT (block), e);
- bitmap_insert_into_set (PHI_GEN (block), e);
- for (i = 0; i < gimple_phi_num_args (phi); ++i)
- {
- tree arg = gimple_phi_arg_def (phi, i);
- if (TREE_CODE (arg) == SSA_NAME)
- {
- e = get_or_alloc_expr_for_name (arg);
- add_to_value (get_expr_value_id (e), e);
- }
- }
-}
-
/* Compute the AVAIL set for all basic blocks.
This function performs value numbering of the statements in each basic
@@ -3703,6 +3661,14 @@ compute_avail (void)
bitmap_value_insert_into_set (AVAIL_OUT (ENTRY_BLOCK_PTR), e);
}
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ print_bitmap_set (dump_file, TMP_GEN (ENTRY_BLOCK_PTR),
+ "tmp_gen", ENTRY_BLOCK);
+ print_bitmap_set (dump_file, AVAIL_OUT (ENTRY_BLOCK_PTR),
+ "avail_out", ENTRY_BLOCK);
+ }
+
/* Allocate the worklist. */
worklist = XNEWVEC (basic_block, n_basic_blocks);
@@ -3731,7 +3697,19 @@ compute_avail (void)
/* Generate values for PHI nodes. */
for (gsi = gsi_start_phis (block); !gsi_end_p (gsi); gsi_next (&gsi))
- make_values_for_phi (gsi_stmt (gsi), block);
+ {
+ tree result = gimple_phi_result (gsi_stmt (gsi));
+
+ /* We have no need for virtual phis, as they don't represent
+ actual computations. */
+ if (virtual_operand_p (result))
+ continue;
+
+ pre_expr e = get_or_alloc_expr_for_name (result);
+ add_to_value (get_expr_value_id (e), e);
+ bitmap_value_insert_into_set (AVAIL_OUT (block), e);
+ bitmap_insert_into_set (PHI_GEN (block), e);
+ }
BB_MAY_NOTRETURN (block) = 0;
@@ -3775,7 +3753,12 @@ compute_avail (void)
continue;
FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE)
- add_to_exp_gen (block, op);
+ {
+ if (ssa_undefined_value_p (op))
+ continue;
+ pre_expr e = get_or_alloc_expr_for_name (op);
+ bitmap_value_insert_into_set (EXP_GEN (block), e);
+ }
switch (gimple_code (stmt))
{
@@ -3911,6 +3894,18 @@ compute_avail (void)
}
}
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ print_bitmap_set (dump_file, EXP_GEN (block),
+ "exp_gen", block->index);
+ print_bitmap_set (dump_file, PHI_GEN (block),
+ "phi_gen", block->index);
+ print_bitmap_set (dump_file, TMP_GEN (block),
+ "tmp_gen", block->index);
+ print_bitmap_set (dump_file, AVAIL_OUT (block),
+ "avail_out", block->index);
+ }
+
/* Put the dominator children of BLOCK on the worklist of blocks
to compute available sets for. */
for (son = first_dom_son (CDI_DOMINATORS, block);
@@ -4667,22 +4662,6 @@ do_pre (void)
/* Collect and value number expressions computed in each basic block. */
compute_avail ();
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- basic_block bb;
- FOR_ALL_BB (bb)
- {
- print_bitmap_set (dump_file, EXP_GEN (bb),
- "exp_gen", bb->index);
- print_bitmap_set (dump_file, PHI_GEN (bb),
- "phi_gen", bb->index);
- print_bitmap_set (dump_file, TMP_GEN (bb),
- "tmp_gen", bb->index);
- print_bitmap_set (dump_file, AVAIL_OUT (bb),
- "avail_out", bb->index);
- }
- }
-
/* Insert can get quite slow on an incredibly large number of basic
blocks due to some quadratic behavior. Until this behavior is
fixed, don't run it when he have an incredibly large number of
^ permalink raw reply [flat|nested] 5+ messages in thread
* [PATCH] PRE TLC
@ 2012-09-21 14:58 Richard Guenther
0 siblings, 0 replies; 5+ messages in thread
From: Richard Guenther @ 2012-09-21 14:58 UTC (permalink / raw)
To: gcc-patches
This removes the no longer required dominating stmt argument from
the insertion routines (since the eliminate () reorg) and also
reflects that insertion now never can fail (again).
Bootstrapped on x86_64-unknown-linux-gnu, testing in progress.
Richard.
2012-09-21 Richard Guenther <rguenther@suse.de>
* tree-ssa-pre.c (bitmap_find_leader, create_expression_by_pieces,
find_or_generate_expression): Remove dominating stmt argument.
(find_leader_in_sets, phi_translate_1, bitmap_find_leader,
create_component_ref_by_pieces_1, create_component_ref_by_pieces,
do_regular_insertion, do_partial_partial_insertion): Adjust.
(compute_avail): Do not set uids.
Index: gcc/tree-ssa-pre.c
===================================================================
--- gcc/tree-ssa-pre.c (revision 191613)
+++ gcc/tree-ssa-pre.c (working copy)
@@ -453,7 +453,7 @@ static struct
} pre_stats;
static bool do_partial_partial;
-static pre_expr bitmap_find_leader (bitmap_set_t, unsigned int, gimple);
+static pre_expr bitmap_find_leader (bitmap_set_t, unsigned int);
static void bitmap_value_insert_into_set (bitmap_set_t, pre_expr);
static void bitmap_value_replace_in_set (bitmap_set_t, pre_expr);
static void bitmap_set_copy (bitmap_set_t, bitmap_set_t);
@@ -463,9 +463,8 @@ static void bitmap_insert_into_set_1 (bi
unsigned int, bool);
static bitmap_set_t bitmap_set_new (void);
static tree create_expression_by_pieces (basic_block, pre_expr, gimple_seq *,
- gimple, tree);
-static tree find_or_generate_expression (basic_block, pre_expr, gimple_seq *,
- gimple);
+ tree);
+static tree find_or_generate_expression (basic_block, tree, gimple_seq *);
static unsigned int get_expr_value_id (pre_expr);
/* We can add and remove elements and entries to and from sets
@@ -1339,9 +1338,9 @@ find_leader_in_sets (unsigned int val, b
{
pre_expr result;
- result = bitmap_find_leader (set1, val, NULL);
+ result = bitmap_find_leader (set1, val);
if (!result && set2)
- result = bitmap_find_leader (set2, val, NULL);
+ result = bitmap_find_leader (set2, val);
return result;
}
@@ -1733,39 +1732,26 @@ phi_translate_1 (pre_expr expr, bitmap_s
case NAME:
{
- gimple phi = NULL;
- edge e;
- gimple def_stmt;
tree name = PRE_EXPR_NAME (expr);
-
- def_stmt = SSA_NAME_DEF_STMT (name);
+ gimple def_stmt = SSA_NAME_DEF_STMT (name);
+ /* If the SSA name is defined by a PHI node in this block,
+ translate it. */
if (gimple_code (def_stmt) == GIMPLE_PHI
&& gimple_bb (def_stmt) == phiblock)
- phi = def_stmt;
- else
- return expr;
-
- e = find_edge (pred, gimple_bb (phi));
- if (e)
{
- tree def = PHI_ARG_DEF (phi, e->dest_idx);
- pre_expr newexpr;
-
- if (TREE_CODE (def) == SSA_NAME)
- def = VN_INFO (def)->valnum;
+ edge e = find_edge (pred, gimple_bb (def_stmt));
+ tree def = PHI_ARG_DEF (def_stmt, e->dest_idx);
/* Handle constant. */
if (is_gimple_min_invariant (def))
return get_or_alloc_expr_for_constant (def);
- if (TREE_CODE (def) == SSA_NAME && ssa_undefined_value_p (def))
- return NULL;
-
- newexpr = get_or_alloc_expr_for_name (def);
- return newexpr;
+ return get_or_alloc_expr_for_name (def);
}
+ /* Otherwise return it unchanged - it will get cleaned if its
+ value is not available in PREDs AVAIL_OUT set of expressions. */
+ return expr;
}
- return expr;
default:
gcc_unreachable ();
@@ -1854,7 +1840,7 @@ phi_translate_set (bitmap_set_t dest, bi
Return NULL if no leader is found. */
static pre_expr
-bitmap_find_leader (bitmap_set_t set, unsigned int val, gimple stmt)
+bitmap_find_leader (bitmap_set_t set, unsigned int val)
{
if (value_id_constant_p (val))
{
@@ -1887,23 +1873,7 @@ bitmap_find_leader (bitmap_set_t set, un
bitmap exprset = VEC_index (bitmap, value_expressions, val);
EXECUTE_IF_AND_IN_BITMAP (exprset, &set->expressions, 0, i, bi)
- {
- pre_expr val = expression_for_id (i);
- /* At the point where stmt is not null, there should always
- be an SSA_NAME first in the list of expressions. */
- if (stmt)
- {
- gimple def_stmt = SSA_NAME_DEF_STMT (PRE_EXPR_NAME (val));
- if (gimple_code (def_stmt) != GIMPLE_PHI
- && gimple_bb (def_stmt) == gimple_bb (stmt)
- /* PRE insertions are at the end of the basic-block
- and have UID 0. */
- && (gimple_uid (def_stmt) == 0
- || gimple_uid (def_stmt) >= gimple_uid (stmt)))
- continue;
- }
- return val;
- }
+ return expression_for_id (i);
}
return NULL;
}
@@ -2586,8 +2556,7 @@ static bitmap inserted_exprs;
static tree
create_component_ref_by_pieces_1 (basic_block block, vn_reference_t ref,
- unsigned int *operand, gimple_seq *stmts,
- gimple domstmt)
+ unsigned int *operand, gimple_seq *stmts)
{
vn_reference_op_t currop = &VEC_index (vn_reference_op_s, ref->operands,
*operand);
@@ -2603,31 +2572,15 @@ create_component_ref_by_pieces_1 (basic_
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;
- }
+ fn = find_or_generate_expression (block, currop->op0, stmts);
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;
- }
+ sc = find_or_generate_expression (block, currop->op1, stmts);
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;
- }
+ operand, stmts);
nargs++;
}
folded = build_call_array (currop->type,
@@ -2643,10 +2596,8 @@ create_component_ref_by_pieces_1 (basic_
case MEM_REF:
{
tree baseop = create_component_ref_by_pieces_1 (block, ref, operand,
- stmts, domstmt);
+ stmts);
tree offset = currop->op0;
- if (!baseop)
- return NULL_TREE;
if (TREE_CODE (baseop) == ADDR_EXPR
&& handled_component_p (TREE_OPERAND (baseop, 0)))
{
@@ -2665,30 +2616,15 @@ create_component_ref_by_pieces_1 (basic_
case TARGET_MEM_REF:
{
- pre_expr op0expr, op1expr;
tree genop0 = NULL_TREE, genop1 = NULL_TREE;
vn_reference_op_t nextop = &VEC_index (vn_reference_op_s, ref->operands,
++*operand);
tree baseop = create_component_ref_by_pieces_1 (block, ref, operand,
- stmts, domstmt);
- if (!baseop)
- return NULL_TREE;
+ stmts);
if (currop->op0)
- {
- op0expr = get_or_alloc_expr_for (currop->op0);
- genop0 = find_or_generate_expression (block, op0expr,
- stmts, domstmt);
- if (!genop0)
- return NULL_TREE;
- }
+ genop0 = find_or_generate_expression (block, currop->op0, stmts);
if (nextop->op0)
- {
- op1expr = get_or_alloc_expr_for (nextop->op0);
- genop1 = find_or_generate_expression (block, op1expr,
- stmts, domstmt);
- if (!genop1)
- return NULL_TREE;
- }
+ genop1 = find_or_generate_expression (block, nextop->op0, stmts);
return build5 (TARGET_MEM_REF, currop->type,
baseop, currop->op2, genop0, currop->op1, genop1);
}
@@ -2705,41 +2641,24 @@ create_component_ref_by_pieces_1 (basic_
case VIEW_CONVERT_EXPR:
{
tree genop0 = create_component_ref_by_pieces_1 (block, ref,
- operand,
- stmts, domstmt);
- if (!genop0)
- return NULL_TREE;
-
+ operand, stmts);
return fold_build1 (currop->opcode, currop->type, genop0);
}
case WITH_SIZE_EXPR:
{
tree genop0 = create_component_ref_by_pieces_1 (block, ref, operand,
- stmts, domstmt);
- pre_expr op1expr = get_or_alloc_expr_for (currop->op0);
- tree genop1;
-
- if (!genop0)
- return NULL_TREE;
-
- genop1 = find_or_generate_expression (block, op1expr, stmts, domstmt);
- if (!genop1)
- return NULL_TREE;
-
+ stmts);
+ tree genop1 = find_or_generate_expression (block, currop->op0, stmts);
return fold_build2 (currop->opcode, currop->type, genop0, genop1);
}
case BIT_FIELD_REF:
{
tree genop0 = create_component_ref_by_pieces_1 (block, ref, operand,
- stmts, domstmt);
+ stmts);
tree op1 = currop->op0;
tree op2 = currop->op1;
-
- if (!genop0)
- return NULL_TREE;
-
return fold_build3 (BIT_FIELD_REF, currop->type, genop0, op1, op2);
}
@@ -2751,19 +2670,10 @@ create_component_ref_by_pieces_1 (basic_
{
tree genop0;
tree genop1 = currop->op0;
- pre_expr op1expr;
tree genop2 = currop->op1;
- pre_expr op2expr;
tree genop3 = currop->op2;
- pre_expr op3expr;
- genop0 = create_component_ref_by_pieces_1 (block, ref, operand,
- stmts, domstmt);
- if (!genop0)
- return NULL_TREE;
- op1expr = get_or_alloc_expr_for (genop1);
- genop1 = find_or_generate_expression (block, op1expr, stmts, domstmt);
- if (!genop1)
- return NULL_TREE;
+ genop0 = create_component_ref_by_pieces_1 (block, ref, operand, stmts);
+ genop1 = find_or_generate_expression (block, genop1, stmts);
if (genop2)
{
tree domain_type = TYPE_DOMAIN (TREE_TYPE (genop0));
@@ -2773,13 +2683,7 @@ create_component_ref_by_pieces_1 (basic_
|| integer_zerop (TYPE_MIN_VALUE (domain_type))))
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;
- }
+ genop2 = find_or_generate_expression (block, genop2, stmts);
}
if (genop3)
{
@@ -2794,11 +2698,7 @@ create_component_ref_by_pieces_1 (basic_
{
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;
+ genop3 = find_or_generate_expression (block, genop3, stmts);
}
}
return build4 (currop->opcode, currop->type, genop0, genop1,
@@ -2809,30 +2709,17 @@ create_component_ref_by_pieces_1 (basic_
tree op0;
tree op1;
tree genop2 = currop->op1;
- pre_expr op2expr;
- op0 = create_component_ref_by_pieces_1 (block, ref, operand,
- stmts, domstmt);
- if (!op0)
- return NULL_TREE;
- /* op1 should be a FIELD_DECL, which are represented by
- themselves. */
+ op0 = create_component_ref_by_pieces_1 (block, ref, operand, stmts);
+ /* op1 should be a FIELD_DECL, which are represented by themselves. */
op1 = currop->op0;
if (genop2)
- {
- op2expr = get_or_alloc_expr_for (genop2);
- genop2 = find_or_generate_expression (block, op2expr, stmts,
- domstmt);
- if (!genop2)
- return NULL_TREE;
- }
-
+ genop2 = find_or_generate_expression (block, genop2, stmts);
return fold_build3 (COMPONENT_REF, TREE_TYPE (op1), op0, op1, genop2);
}
case SSA_NAME:
{
- pre_expr op0expr = get_or_alloc_expr_for (currop->op0);
- genop = find_or_generate_expression (block, op0expr, stmts, domstmt);
+ genop = find_or_generate_expression (block, currop->op0, stmts);
return genop;
}
case STRING_CST:
@@ -2867,17 +2754,17 @@ create_component_ref_by_pieces_1 (basic_
static tree
create_component_ref_by_pieces (basic_block block, vn_reference_t ref,
- gimple_seq *stmts, gimple domstmt)
+ gimple_seq *stmts)
{
unsigned int op = 0;
- return create_component_ref_by_pieces_1 (block, ref, &op, stmts, domstmt);
+ return create_component_ref_by_pieces_1 (block, ref, &op, stmts);
}
/* Find a leader for an expression, or generate one using
create_expression_by_pieces if it's ANTIC but
complex.
BLOCK is the basic_block we are looking for leaders in.
- EXPR is the expression to find a leader or generate for.
+ OP is the tree expression to find a leader for or generate.
STMTS is the statement list to put the inserted expressions on.
Returns the SSA_NAME of the LHS of the generated expression or the
leader.
@@ -2887,51 +2774,32 @@ create_component_ref_by_pieces (basic_bl
on failure. */
static tree
-find_or_generate_expression (basic_block block, pre_expr expr,
- gimple_seq *stmts, gimple domstmt)
+find_or_generate_expression (basic_block block, tree op, gimple_seq *stmts)
{
- pre_expr leader = bitmap_find_leader (AVAIL_OUT (block),
- get_expr_value_id (expr), domstmt);
- tree genop = NULL;
+ pre_expr expr = get_or_alloc_expr_for (op);
+ unsigned int lookfor = get_expr_value_id (expr);
+ pre_expr leader = bitmap_find_leader (AVAIL_OUT (block), lookfor);
if (leader)
{
if (leader->kind == NAME)
- genop = PRE_EXPR_NAME (leader);
+ return PRE_EXPR_NAME (leader);
else if (leader->kind == CONSTANT)
- genop = PRE_EXPR_CONSTANT (leader);
+ return PRE_EXPR_CONSTANT (leader);
}
- /* If it's still NULL, it must be a complex expression, so generate
- it recursively. Not so if inserting expressions for values generated
- by SCCVN. */
- if (genop == NULL
- && !domstmt)
- {
- bitmap exprset;
- unsigned int lookfor = get_expr_value_id (expr);
- bool handled = false;
- bitmap_iterator bi;
- unsigned int i;
-
- exprset = VEC_index (bitmap, value_expressions, lookfor);
- EXECUTE_IF_SET_IN_BITMAP (exprset, 0, i, bi)
- {
- pre_expr temp = expression_for_id (i);
- if (temp->kind != NAME)
- {
- handled = true;
- genop = create_expression_by_pieces (block, temp, stmts,
- domstmt,
- get_expr_type (expr));
- break;
- }
- }
- if (!handled && domstmt)
- return NULL_TREE;
-
- gcc_assert (handled);
+ /* It must be a complex expression, so generate it recursively. */
+ bitmap exprset = VEC_index (bitmap, value_expressions, lookfor);
+ bitmap_iterator bi;
+ unsigned int i;
+ EXECUTE_IF_SET_IN_BITMAP (exprset, 0, i, bi)
+ {
+ pre_expr temp = expression_for_id (i);
+ if (temp->kind != NAME)
+ return create_expression_by_pieces (block, temp, stmts,
+ get_expr_type (expr));
}
- return genop;
+
+ gcc_unreachable ();
}
#define NECESSARY GF_PLF_1
@@ -2956,7 +2824,7 @@ find_or_generate_expression (basic_block
static tree
create_expression_by_pieces (basic_block block, pre_expr expr,
- gimple_seq *stmts, gimple domstmt, tree type)
+ gimple_seq *stmts, tree type)
{
tree name;
tree folded;
@@ -2980,7 +2848,7 @@ create_expression_by_pieces (basic_block
case REFERENCE:
{
vn_reference_t ref = PRE_EXPR_REFERENCE (expr);
- folded = create_component_ref_by_pieces (block, ref, stmts, domstmt);
+ folded = create_component_ref_by_pieces (block, ref, stmts);
}
break;
case NARY:
@@ -2990,11 +2858,7 @@ create_expression_by_pieces (basic_block
unsigned i;
for (i = 0; i < nary->length; ++i)
{
- pre_expr op = get_or_alloc_expr_for (nary->op[i]);
- genop[i] = find_or_generate_expression (block, op,
- stmts, domstmt);
- if (!genop[i])
- return NULL_TREE;
+ genop[i] = find_or_generate_expression (block, nary->op[i], stmts);
/* Ensure genop[] is properly typed for POINTER_PLUS_EXPR. It
may have conversions stripped. */
if (nary->opcode == POINTER_PLUS_EXPR)
@@ -3036,8 +2900,6 @@ create_expression_by_pieces (basic_block
}
}
break;
- default:
- return NULL_TREE;
}
if (!useless_type_conversion_p (exprtype, TREE_TYPE (folded)))
@@ -3228,10 +3090,8 @@ insert_into_preds_of_block (basic_block
if (eprime->kind != NAME && eprime->kind != CONSTANT)
{
- builtexpr = create_expression_by_pieces (bprime,
- eprime,
- &stmts, NULL,
- type);
+ builtexpr = create_expression_by_pieces (bprime, eprime,
+ &stmts, type);
gcc_assert (!(pred->flags & EDGE_ABNORMAL));
gsi_insert_seq_on_edge (pred, stmts);
VEC_replace (pre_expr, avail, pred->dest_idx,
@@ -3474,7 +3334,7 @@ do_regular_insertion (basic_block block,
eprime = fully_constant_expression (eprime);
vprime = get_expr_value_id (eprime);
edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime),
- vprime, NULL);
+ vprime);
if (edoubleprime == NULL)
{
VEC_replace (pre_expr, avail, pred->dest_idx, eprime);
@@ -3637,8 +3497,7 @@ do_partial_partial_insertion (basic_bloc
eprime = fully_constant_expression (eprime);
vprime = get_expr_value_id (eprime);
- edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime),
- vprime, NULL);
+ edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime), vprime);
VEC_replace (pre_expr, avail, pred->dest_idx, edoubleprime);
if (edoubleprime == NULL)
{
@@ -3870,7 +3729,6 @@ compute_avail (void)
gimple_stmt_iterator gsi;
gimple stmt;
basic_block dom;
- unsigned int stmt_uid = 1;
/* Pick a block from the worklist. */
block = worklist[--sp];
@@ -3895,7 +3753,6 @@ compute_avail (void)
tree op;
stmt = gsi_stmt (gsi);
- gimple_set_uid (stmt, stmt_uid++);
/* Cache whether the basic-block has any non-visible side-effect
or control flow.
^ permalink raw reply [flat|nested] 5+ messages in thread
* [PATCH] PRE TLC
@ 2012-05-03 11:10 Richard Guenther
0 siblings, 0 replies; 5+ messages in thread
From: Richard Guenther @ 2012-05-03 11:10 UTC (permalink / raw)
To: gcc-patches
When looking at PR53168 I noticed that clean () can be optimized
and simplified quite a bit. Likewise that we do not dump whether
we find a partial or a partial partial redundancy, nor dump
the insert iteration. Also dumping the PRE sets is tedious
from inside gdb so this adds a debug function to do that.
Bootstrapped and tested on x86_64-unknown-linux-gnu, applied.
Richard.
2012-05-03 Richard Guenther <rguenther@suse.de>
* tree-ssa-pre.c (debug_bitmap_sets_for): New function.
(union_contains_value): Remove.
(vro_valid_in_sets): Likewise.
(op_valid_in_sets): New function.
(valid_in_sets): Use op_valid_in_sets.
(insert_into_preds_of_block): Move dumping ...
(do_regular_insertion): ... here.
(do_partial_partial_insertion): ... and here. Dump that
we've found a partial partial redundancy.
(insert): Dump the current insert iteration.
Index: gcc/tree-ssa-pre.c
===================================================================
--- gcc/tree-ssa-pre.c (revision 187081)
+++ gcc/tree-ssa-pre.c (working copy)
@@ -1029,6 +1029,24 @@ debug_bitmap_set (bitmap_set_t set)
print_bitmap_set (stderr, set, "debug", 0);
}
+void debug_bitmap_sets_for (basic_block);
+
+DEBUG_FUNCTION void
+debug_bitmap_sets_for (basic_block bb)
+{
+ print_bitmap_set (stderr, AVAIL_OUT (bb), "avail_out", bb->index);
+ if (!in_fre)
+ {
+ print_bitmap_set (stderr, EXP_GEN (bb), "exp_gen", bb->index);
+ print_bitmap_set (stderr, PHI_GEN (bb), "phi_gen", bb->index);
+ print_bitmap_set (stderr, TMP_GEN (bb), "tmp_gen", bb->index);
+ print_bitmap_set (stderr, ANTIC_IN (bb), "antic_in", bb->index);
+ if (do_partial_partial)
+ print_bitmap_set (stderr, PA_IN (bb), "pa_in", bb->index);
+ print_bitmap_set (stderr, NEW_SETS (bb), "new_sets", bb->index);
+ }
+}
+
/* Print out the expressions that have VAL to OUTFILE. */
static void
@@ -2014,57 +2032,19 @@ value_dies_in_block_x (pre_expr expr, ba
}
-#define union_contains_value(SET1, SET2, VAL) \
- (bitmap_set_contains_value ((SET1), (VAL)) \
- || ((SET2) && bitmap_set_contains_value ((SET2), (VAL))))
+/* Determine if OP is valid in SET1 U SET2, which it is when the union
+ contains its value-id. */
-/* Determine if vn_reference_op_t VRO is legal in SET1 U SET2.
- */
static bool
-vro_valid_in_sets (bitmap_set_t set1, bitmap_set_t set2,
- vn_reference_op_t vro)
+op_valid_in_sets (bitmap_set_t set1, bitmap_set_t set2, tree op)
{
- if (vro->op0 && TREE_CODE (vro->op0) == SSA_NAME)
- {
- struct pre_expr_d temp;
- temp.kind = NAME;
- temp.id = 0;
- PRE_EXPR_NAME (&temp) = vro->op0;
- temp.id = lookup_expression_id (&temp);
- if (temp.id == 0)
- return false;
- if (!union_contains_value (set1, set2,
- get_expr_value_id (&temp)))
- return false;
- }
- if (vro->op1 && TREE_CODE (vro->op1) == SSA_NAME)
+ if (op && TREE_CODE (op) == SSA_NAME)
{
- struct pre_expr_d temp;
- temp.kind = NAME;
- temp.id = 0;
- PRE_EXPR_NAME (&temp) = vro->op1;
- temp.id = lookup_expression_id (&temp);
- if (temp.id == 0)
- return false;
- if (!union_contains_value (set1, set2,
- get_expr_value_id (&temp)))
- return false;
- }
-
- if (vro->op2 && TREE_CODE (vro->op2) == SSA_NAME)
- {
- struct pre_expr_d temp;
- temp.kind = NAME;
- temp.id = 0;
- PRE_EXPR_NAME (&temp) = vro->op2;
- temp.id = lookup_expression_id (&temp);
- if (temp.id == 0)
- return false;
- if (!union_contains_value (set1, set2,
- get_expr_value_id (&temp)))
+ unsigned int value_id = VN_INFO (op)->value_id;
+ if (!bitmap_set_contains_value (set1, value_id)
+ || (set2 && !bitmap_set_contains_value (set2, value_id)))
return false;
}
-
return true;
}
@@ -2087,21 +2067,8 @@ valid_in_sets (bitmap_set_t set1, bitmap
unsigned int i;
vn_nary_op_t nary = PRE_EXPR_NARY (expr);
for (i = 0; i < nary->length; i++)
- {
- if (TREE_CODE (nary->op[i]) == SSA_NAME)
- {
- struct pre_expr_d temp;
- temp.kind = NAME;
- temp.id = 0;
- PRE_EXPR_NAME (&temp) = nary->op[i];
- temp.id = lookup_expression_id (&temp);
- if (temp.id == 0)
- return false;
- if (!union_contains_value (set1, set2,
- get_expr_value_id (&temp)))
- return false;
- }
- }
+ if (!op_valid_in_sets (set1, set2, nary->op[i]))
+ return false;
/* If the NARY may trap make sure the block does not contain
a possible exit point.
??? This is overly conservative if we translate AVAIL_OUT
@@ -2120,7 +2087,9 @@ valid_in_sets (bitmap_set_t set1, bitmap
FOR_EACH_VEC_ELT (vn_reference_op_s, ref->operands, i, vro)
{
- if (!vro_valid_in_sets (set1, set2, vro))
+ if (!op_valid_in_sets (set1, set2, vro->op0)
+ || !op_valid_in_sets (set1, set2, vro->op1)
+ || !op_valid_in_sets (set1, set2, vro->op2))
return false;
}
return true;
@@ -3330,13 +3299,6 @@ insert_into_preds_of_block (basic_block
tree temp;
gimple phi;
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "Found partial redundancy for expression ");
- print_pre_expr (dump_file, expr);
- fprintf (dump_file, " (%04d)\n", val);
- }
-
/* Make sure we aren't creating an induction variable. */
if (block->loop_depth > 0 && EDGE_COUNT (block->preds) == 2)
{
@@ -3651,11 +3613,21 @@ do_regular_insertion (basic_block block,
"optimized for speed edge\n", val);
}
}
- else if (dbg_cnt (treepre_insert)
- && insert_into_preds_of_block (block,
- get_expression_id (expr),
- avail))
- new_stuff = true;
+ else if (dbg_cnt (treepre_insert))
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "Found partial redundancy for "
+ "expression ");
+ print_pre_expr (dump_file, expr);
+ fprintf (dump_file, " (%04d)\n",
+ get_expr_value_id (expr));
+ }
+ if (insert_into_preds_of_block (block,
+ get_expression_id (expr),
+ avail))
+ new_stuff = true;
+ }
}
/* If all edges produce the same value and that value is
an invariant, then the PHI has the same value on all
@@ -3813,6 +3785,14 @@ do_partial_partial_insertion (basic_bloc
else if (dbg_cnt (treepre_insert))
{
pre_stats.pa_insert++;
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "Found partial partial redundancy "
+ "for expression ");
+ print_pre_expr (dump_file, expr);
+ fprintf (dump_file, " (%04d)\n",
+ get_expr_value_id (expr));
+ }
if (insert_into_preds_of_block (block,
get_expression_id (expr),
avail))
@@ -3888,6 +3868,8 @@ insert (void)
while (new_stuff)
{
num_iterations++;
+ if (dump_file && dump_flags & TDF_DETAILS)
+ fprintf (dump_file, "Starting insert iteration %d\n", num_iterations);
new_stuff = insert_aux (ENTRY_BLOCK_PTR);
}
statistics_histogram_event (cfun, "insert iterations", num_iterations);
^ permalink raw reply [flat|nested] 5+ messages in thread
end of thread, other threads:[~2017-05-05 12:04 UTC | newest]
Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2014-09-02 14:08 [PATCH] PRE TLC Richard Biener
-- strict thread matches above, loose matches on Subject: below --
2017-05-05 12:13 Richard Biener
2012-11-29 13:52 Richard Biener
2012-09-21 14:58 Richard Guenther
2012-05-03 11:10 Richard Guenther
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).