* [PATCH] More PRE TLC
@ 2012-05-03 13:04 Richard Guenther
0 siblings, 0 replies; 3+ messages in thread
From: Richard Guenther @ 2012-05-03 13:04 UTC (permalink / raw)
To: gcc-patches
This moves handling of trapping ops to prune_clobbered_mems and
compute_avail, similar to how I moved handling of clobbered mems
earlier. It fixes one existing testcase even.
Bootstrapped and tested on x86_64-unknown-linux-gnu, applied.
Richard.
2012-05-03 Richard Guenther <rguenther@suse.de>
* tree-ssa-pre.c (valid_in_sets): Remove checking of trapping
operations.
(prune_clobbered_mems): Do it here. Do not uselessly sort
expressions.
(compute_avail): Do not add possibly trapping operations to
EXP_GEN if they might not be executed in the block.
* gcc.dg/tree-ssa/ssa-pre-27.c: Remove XFAIL.
Index: gcc/tree-ssa-pre.c
===================================================================
*** gcc/tree-ssa-pre.c (revision 187092)
--- gcc/tree-ssa-pre.c (working copy)
*************** valid_in_sets (bitmap_set_t set1, bitmap
*** 2069,2081 ****
for (i = 0; i < nary->length; i++)
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
- as the available expression might be after the exit point. */
- if (BB_MAY_NOTRETURN (block)
- && vn_nary_may_trap (nary))
- return false;
return true;
}
break;
--- 2069,2074 ----
*************** clean (bitmap_set_t set, basic_block blo
*** 2140,2174 ****
}
/* Clean the set of expressions that are no longer valid in SET because
! they are clobbered in BLOCK. */
static void
prune_clobbered_mems (bitmap_set_t set, basic_block block)
{
! VEC (pre_expr, heap) *exprs = sorted_array_from_bitmap_set (set);
! pre_expr expr;
! int i;
! FOR_EACH_VEC_ELT (pre_expr, exprs, i, expr)
{
! vn_reference_t ref;
! if (expr->kind != REFERENCE)
! continue;
!
! ref = PRE_EXPR_REFERENCE (expr);
! if (ref->vuse)
{
! gimple def_stmt = SSA_NAME_DEF_STMT (ref->vuse);
! if (!gimple_nop_p (def_stmt)
! && ((gimple_bb (def_stmt) != block
! && !dominated_by_p (CDI_DOMINATORS,
! block, gimple_bb (def_stmt)))
! || (gimple_bb (def_stmt) == block
! && value_dies_in_block_x (expr, block))))
bitmap_remove_from_set (set, expr);
}
}
- VEC_free (pre_expr, heap, exprs);
}
static sbitmap has_abnormal_preds;
--- 2133,2176 ----
}
/* Clean the set of expressions that are no longer valid in SET because
! they are clobbered in BLOCK or because they trap and may not be executed. */
static void
prune_clobbered_mems (bitmap_set_t set, basic_block block)
{
! bitmap_iterator bi;
! unsigned i;
! FOR_EACH_EXPR_ID_IN_SET (set, i, bi)
{
! pre_expr expr = expression_for_id (i);
! if (expr->kind == REFERENCE)
! {
! vn_reference_t ref = PRE_EXPR_REFERENCE (expr);
! if (ref->vuse)
! {
! gimple def_stmt = SSA_NAME_DEF_STMT (ref->vuse);
! if (!gimple_nop_p (def_stmt)
! && ((gimple_bb (def_stmt) != block
! && !dominated_by_p (CDI_DOMINATORS,
! block, gimple_bb (def_stmt)))
! || (gimple_bb (def_stmt) == block
! && value_dies_in_block_x (expr, block))))
! bitmap_remove_from_set (set, expr);
! }
! }
! else if (expr->kind == NARY)
{
! vn_nary_op_t nary = PRE_EXPR_NARY (expr);
! /* 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
! as the available expression might be after the exit point. */
! if (BB_MAY_NOTRETURN (block)
! && vn_nary_may_trap (nary))
bitmap_remove_from_set (set, expr);
}
}
}
static sbitmap has_abnormal_preds;
*************** compute_avail (void)
*** 4119,4124 ****
--- 4121,4133 ----
if (TREE_CODE (nary->op[i]) == SSA_NAME)
add_to_exp_gen (block, nary->op[i]);
+ /* If the NARY traps and there was a preceeding
+ point in the block that might not return avoid
+ adding the nary to EXP_GEN. */
+ if (BB_MAY_NOTRETURN (block)
+ && vn_nary_may_trap (nary))
+ continue;
+
result = (pre_expr) pool_alloc (pre_expr_pool);
result->kind = NARY;
result->id = 0;
Index: gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-27.c
===================================================================
*** gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-27.c (revision 187091)
--- gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-27.c (working copy)
*************** int foo2 (int i, int j, int b)
*** 17,29 ****
int res = 0;
if (b)
res = i/j;
! /* But we fail so here because of the possibly not returning
! call in the same basic-block. */
res += i/j;
bar ();
return res;
}
! /* { dg-final { scan-tree-dump-times "# prephitmp" 1 "pre" } } */
! /* { dg-final { scan-tree-dump-times "# prephitmp" 2 "pre" { xfail *-*-* } } } */
/* { dg-final { cleanup-tree-dump "pre" } } */
--- 17,28 ----
int res = 0;
if (b)
res = i/j;
! /* And here, the possibly not returning call in the same basic-block
! comes after the trapping i/j. */
res += i/j;
bar ();
return res;
}
! /* { dg-final { scan-tree-dump-times "# prephitmp" 2 "pre" } } */
/* { dg-final { cleanup-tree-dump "pre" } } */
^ permalink raw reply [flat|nested] 3+ messages in thread
* [PATCH] More PRE TLC
@ 2017-08-02 6:51 Richard Biener
0 siblings, 0 replies; 3+ messages in thread
From: Richard Biener @ 2017-08-02 6:51 UTC (permalink / raw)
To: gcc-patches
Bootstrapped and tested on x86_64-unknown-linux-gnu, applied.
Richard.
2017-08-02 Richard Biener <rguenther@suse.de>
* tree-ssa-pre.c (bitmap_insert_into_set_1): Remove and inline
into ...
(bitmap_insert_into_set): ... this.
Index: gcc/tree-ssa-pre.c
===================================================================
--- gcc/tree-ssa-pre.c (revision 250777)
+++ gcc/tree-ssa-pre.c (working copy)
@@ -540,8 +540,6 @@ static void bitmap_set_copy (bitmap_set_
static void bitmap_set_and (bitmap_set_t, bitmap_set_t);
static bool bitmap_set_contains_value (bitmap_set_t, unsigned int);
static void bitmap_insert_into_set (bitmap_set_t, pre_expr);
-static void bitmap_insert_into_set_1 (bitmap_set_t, pre_expr,
- unsigned int, bool);
static bitmap_set_t bitmap_set_new (void);
static tree create_expression_by_pieces (basic_block, pre_expr, gimple_seq *,
tree);
@@ -732,27 +730,22 @@ bitmap_remove_from_set (bitmap_set_t set
}
}
+/* Insert an expression EXPR into a bitmapped set. */
+
static void
-bitmap_insert_into_set_1 (bitmap_set_t set, pre_expr expr,
- unsigned int val, bool allow_constants)
+bitmap_insert_into_set (bitmap_set_t set, pre_expr expr)
{
- if (allow_constants || !value_id_constant_p (val))
+ unsigned int val = get_expr_value_id (expr);
+ if (! value_id_constant_p (val))
{
- /* We specifically expect this and only this function to be able to
- insert constants into a set. */
+ /* Note this is the only function causing multiple expressions
+ for the same value to appear in a set. This is needed for
+ TMP_GEN, PHI_GEN and NEW_SETs. */
bitmap_set_bit (&set->values, val);
bitmap_set_bit (&set->expressions, get_or_alloc_expression_id (expr));
}
}
-/* Insert an expression EXPR into a bitmapped set. */
-
-static void
-bitmap_insert_into_set (bitmap_set_t set, pre_expr expr)
-{
- bitmap_insert_into_set_1 (set, expr, get_expr_value_id (expr), false);
-}
-
/* Copy a bitmapped set ORIG, into bitmapped set DEST. */
static void
@@ -2471,7 +2515,8 @@ compute_antic (void)
{
/* For partial antic we ignore backedges and thus we do not need
to perform any iteration when we process blocks in postorder. */
- int postorder_num = pre_and_rev_post_order_compute (NULL, postorder.address (), false);
+ int postorder_num
+ = pre_and_rev_post_order_compute (NULL, postorder.address (), false);
for (i = postorder_num - 1 ; i >= 0; i--)
{
basic_block block = BASIC_BLOCK_FOR_FN (cfun, postorder[i]);
^ permalink raw reply [flat|nested] 3+ messages in thread
* [PATCH] More PRE TLC
@ 2020-11-10 11:10 Richard Biener
0 siblings, 0 replies; 3+ messages in thread
From: Richard Biener @ 2020-11-10 11:10 UTC (permalink / raw)
To: gcc-patches
This makes get_expr_value_id cheap and completes the
constant value-id simplification by turning the constant_value_expressions
into a direct map instead of a set of pre_exprs for the value.
Bootstrapped and tested on x86_64-unknown-linux-gnu, pushed.
2020-11-10 Richard Biener <rguenther@suse.de>
* tree-ssa-pre.c (pre_expr_d::value_id): Add.
(constant_value_expressions): Turn into an array of pre_expr.
(get_or_alloc_expr_for_nary): New function.
(get_or_alloc_expr_for_reference): Likewise.
(add_to_value): For constant values only ever add a single
CONSTANT.
(get_expr_value_id): Return the new value_id member.
(vn_valnum_from_value_id): Split out and simplify constant
value id handling.
(get_or_alloc_expr_for_constant): Set the value_id member.
(phi_translate_1): Use get_or_alloc_expr_for_*.
(compute_avail): Likewise.
(bitmap_find_leader): Simplify constant value id handling.
---
gcc/tree-ssa-pre.c | 183 ++++++++++++++++++++++-----------------------
1 file changed, 89 insertions(+), 94 deletions(-)
diff --git a/gcc/tree-ssa-pre.c b/gcc/tree-ssa-pre.c
index fec3b2f80f1..160f3b4593a 100644
--- a/gcc/tree-ssa-pre.c
+++ b/gcc/tree-ssa-pre.c
@@ -256,6 +256,7 @@ typedef struct pre_expr_d : nofree_ptr_hash <pre_expr_d>
{
enum pre_expr_kind kind;
unsigned int id;
+ unsigned value_id;
location_t loc;
pre_expr_union u;
@@ -422,11 +423,65 @@ get_or_alloc_expr_for_name (tree name)
result = pre_expr_pool.allocate ();
result->kind = NAME;
result->loc = UNKNOWN_LOCATION;
+ result->value_id = VN_INFO (name)->value_id;
PRE_EXPR_NAME (result) = name;
alloc_expression_id (result);
return result;
}
+/* Given an NARY, get or create a pre_expr to represent it. */
+
+static pre_expr
+get_or_alloc_expr_for_nary (vn_nary_op_t nary,
+ location_t loc = UNKNOWN_LOCATION)
+{
+ struct pre_expr_d expr;
+ pre_expr result;
+ unsigned int result_id;
+
+ expr.kind = NARY;
+ expr.id = 0;
+ PRE_EXPR_NARY (&expr) = nary;
+ result_id = lookup_expression_id (&expr);
+ if (result_id != 0)
+ return expression_for_id (result_id);
+
+ result = pre_expr_pool.allocate ();
+ result->kind = NARY;
+ result->loc = loc;
+ result->value_id = nary->value_id;
+ PRE_EXPR_NARY (result) = nary;
+ alloc_expression_id (result);
+ return result;
+}
+
+/* Given an REFERENCE, get or create a pre_expr to represent it. */
+
+static pre_expr
+get_or_alloc_expr_for_reference (vn_reference_t reference,
+ location_t loc = UNKNOWN_LOCATION)
+{
+ struct pre_expr_d expr;
+ pre_expr result;
+ unsigned int result_id;
+
+ expr.kind = REFERENCE;
+ expr.id = 0;
+ PRE_EXPR_REFERENCE (&expr) = reference;
+ result_id = lookup_expression_id (&expr);
+ if (result_id != 0)
+ return expression_for_id (result_id);
+
+ result = pre_expr_pool.allocate ();
+ result->kind = REFERENCE;
+ result->loc = loc;
+ result->value_id = reference->value_id;
+ PRE_EXPR_REFERENCE (result) = reference;
+ alloc_expression_id (result);
+ return result;
+}
+
+
/* An unordered bitmap set. One bitmap tracks values, the other,
expressions. */
typedef class bitmap_set
@@ -444,9 +499,9 @@ public:
/* Mapping from value id to expressions with that value_id. */
static vec<bitmap> value_expressions;
-/* ??? We want to just record a single expression for each constant
- value, one of kind CONSTANT. */
-static vec<bitmap> constant_value_expressions;
+/* We just record a single expression for each constant value,
+ one of kind CONSTANT. */
+static vec<pre_expr> constant_value_expressions;
/* This structure is used to keep track of statistics on what
@@ -640,35 +695,33 @@ phi_trans_add (expr_pred_trans_t *entry, pre_expr e, basic_block pred)
static void
add_to_value (unsigned int v, pre_expr e)
{
- bitmap set;
-
gcc_checking_assert (get_expr_value_id (e) == v);
if (value_id_constant_p (v))
{
+ if (e->kind != CONSTANT)
+ return;
+
if (-v >= constant_value_expressions.length ())
constant_value_expressions.safe_grow_cleared (-v + 1);
- set = constant_value_expressions[-v];
- if (!set)
- {
- set = BITMAP_ALLOC (&grand_bitmap_obstack);
- constant_value_expressions[-v] = set;
- }
+ pre_expr leader = constant_value_expressions[-v];
+ if (!leader)
+ constant_value_expressions[-v] = e;
}
else
{
if (v >= value_expressions.length ())
value_expressions.safe_grow_cleared (v + 1);
- set = value_expressions[v];
+ bitmap set = value_expressions[v];
if (!set)
{
set = BITMAP_ALLOC (&grand_bitmap_obstack);
value_expressions[v] = set;
}
+ bitmap_set_bit (set, get_or_alloc_expression_id (e));
}
- bitmap_set_bit (set, get_or_alloc_expression_id (e));
}
/* Create a new bitmap set and return it. */
@@ -687,29 +740,10 @@ bitmap_set_new (void)
static unsigned int
get_expr_value_id (pre_expr expr)
{
- unsigned int id;
- switch (expr->kind)
- {
- case CONSTANT:
- id = get_constant_value_id (PRE_EXPR_CONSTANT (expr));
- break;
- case NAME:
- id = VN_INFO (PRE_EXPR_NAME (expr))->value_id;
- break;
- case NARY:
- gcc_assert (!PRE_EXPR_NARY (expr)->predicated_values);
- id = PRE_EXPR_NARY (expr)->value_id;
- break;
- case REFERENCE:
- 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 expr->value_id;
}
/* Return a VN valnum (SSA name or constant) for the PRE value-id VAL. */
@@ -717,20 +751,22 @@ get_expr_value_id (pre_expr expr)
static tree
vn_valnum_from_value_id (unsigned int val)
{
+ if (value_id_constant_p (val))
+ {
+ pre_expr vexpr = constant_value_expressions[-val];
+ if (vexpr)
+ return PRE_EXPR_CONSTANT (vexpr);
+ return NULL_TREE;
+ }
+
+ bitmap exprset = value_expressions[val];
bitmap_iterator bi;
unsigned int i;
- bitmap exprset;
- if (value_id_constant_p (val))
- exprset = constant_value_expressions[-val];
- else
- exprset = value_expressions[val];
EXECUTE_IF_SET_IN_BITMAP (exprset, 0, i, bi)
{
pre_expr vexpr = expression_for_id (i);
if (vexpr->kind == NAME)
return VN_INFO (PRE_EXPR_NAME (vexpr))->valnum;
- else if (vexpr->kind == CONSTANT)
- return PRE_EXPR_CONSTANT (vexpr);
}
return NULL_TREE;
}
@@ -1102,7 +1138,6 @@ static pre_expr
get_or_alloc_expr_for_constant (tree constant)
{
unsigned int result_id;
- unsigned int value_id;
struct pre_expr_d expr;
pre_expr newexpr;
@@ -1117,8 +1152,8 @@ get_or_alloc_expr_for_constant (tree constant)
newexpr->loc = UNKNOWN_LOCATION;
PRE_EXPR_CONSTANT (newexpr) = constant;
alloc_expression_id (newexpr);
- value_id = get_or_alloc_constant_value_id (constant);
- add_to_value (value_id, newexpr);
+ newexpr->value_id = get_or_alloc_constant_value_id (constant);
+ add_to_value (newexpr->value_id, newexpr);
return newexpr;
}
@@ -1475,17 +1510,7 @@ phi_translate_1 (bitmap_set_t dest,
if (result && is_gimple_min_invariant (result))
return get_or_alloc_expr_for_constant (result);
- expr = pre_expr_pool.allocate ();
- expr->kind = NARY;
- expr->id = 0;
- expr->loc = expr_loc;
- if (nary && !nary->predicated_values)
- {
- PRE_EXPR_NARY (expr) = nary;
- new_val_id = nary->value_id;
- get_or_alloc_expression_id (expr);
- }
- else
+ if (!nary || nary->predicated_values)
{
new_val_id = get_next_value_id ();
nary = vn_nary_op_insert_pieces (newnary->length,
@@ -1493,10 +1518,9 @@ phi_translate_1 (bitmap_set_t dest,
newnary->type,
&newnary->op[0],
result, new_val_id);
- PRE_EXPR_NARY (expr) = nary;
- get_or_alloc_expression_id (expr);
}
- add_to_value (new_val_id, expr);
+ expr = get_or_alloc_expr_for_nary (nary, expr_loc);
+ add_to_value (get_expr_value_id (expr), expr);
}
return expr;
}
@@ -1628,11 +1652,6 @@ phi_translate_1 (bitmap_set_t dest,
return NULL;
}
- expr = pre_expr_pool.allocate ();
- expr->kind = REFERENCE;
- expr->id = 0;
- expr->loc = expr_loc;
-
if (newref)
new_val_id = newref->value_id;
else
@@ -1649,8 +1668,7 @@ phi_translate_1 (bitmap_set_t dest,
result, new_val_id);
newoperands = vNULL;
}
- PRE_EXPR_REFERENCE (expr) = newref;
- get_or_alloc_expression_id (expr);
+ expr = get_or_alloc_expr_for_reference (newref, expr_loc);
add_to_value (new_val_id, expr);
}
newoperands.release ();
@@ -1782,19 +1800,8 @@ static pre_expr
bitmap_find_leader (bitmap_set_t set, unsigned int val)
{
if (value_id_constant_p (val))
- {
- unsigned int i;
- bitmap_iterator bi;
- bitmap exprset = constant_value_expressions[-val];
+ return constant_value_expressions[-val];
- EXECUTE_IF_SET_IN_BITMAP (exprset, 0, i, bi)
- {
- pre_expr expr = expression_for_id (i);
- if (expr->kind == CONSTANT)
- return expr;
- }
- gcc_unreachable ();
- }
if (bitmap_set_contains_value (set, val))
{
/* Rather than walk the entire bitmap of expressions, and see
@@ -3932,13 +3939,8 @@ compute_avail (void)
|| gimple_bb (SSA_NAME_DEF_STMT
(gimple_vuse (stmt))) != block)
{
- result = pre_expr_pool.allocate ();
- result->kind = REFERENCE;
- result->id = 0;
- result->loc = gimple_location (stmt);
- PRE_EXPR_REFERENCE (result) = ref;
-
- get_or_alloc_expression_id (result);
+ result = get_or_alloc_expr_for_reference
+ (ref, gimple_location (stmt));
add_to_value (get_expr_value_id (result), result);
bitmap_value_insert_into_set (EXP_GEN (block), result);
}
@@ -3973,11 +3975,8 @@ compute_avail (void)
&& vn_nary_may_trap (nary))
continue;
- result = pre_expr_pool.allocate ();
- result->kind = NARY;
- result->id = 0;
- result->loc = gimple_location (stmt);
- PRE_EXPR_NARY (result) = nary;
+ result = get_or_alloc_expr_for_nary
+ (nary, gimple_location (stmt));
break;
}
@@ -4098,11 +4097,8 @@ compute_avail (void)
}
operands.release ();
- result = pre_expr_pool.allocate ();
- result->kind = REFERENCE;
- result->id = 0;
- result->loc = gimple_location (stmt);
- PRE_EXPR_REFERENCE (result) = ref;
+ result = get_or_alloc_expr_for_reference
+ (ref, gimple_location (stmt));
break;
}
@@ -4110,7 +4106,6 @@ compute_avail (void)
continue;
}
- get_or_alloc_expression_id (result);
add_to_value (get_expr_value_id (result), result);
bitmap_value_insert_into_set (EXP_GEN (block), result);
continue;
--
2.26.2
^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~2020-11-10 11:10 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2012-05-03 13:04 [PATCH] More PRE TLC Richard Guenther
2017-08-02 6:51 Richard Biener
2020-11-10 11:10 Richard Biener
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).