From d398949230786a4d678677fab0070ad779cc1c84 Mon Sep 17 00:00:00 2001 From: Richard Biener Date: Fri, 6 Nov 2020 15:13:56 +0100 Subject: [PATCH] make PRE constant value IDs negative This separates constant and non-constant value-ids to allow for a more efficient constant_value_id_p and for more efficient bit-packing inside the bitmap sets which never contain any constant values. There's further optimization opportunities but at this stage I'll do small refactorings. 2020-11-06 Richard Biener * tree-ssa-sccvn.h (get_max_constant_value_id): Declare. (get_next_constant_value_id): Likewise. (value_id_constant_p): Inline and simplify. * tree-ssa-sccvn.c (constant_value_ids): Remove. (next_constant_value_id): Add. (get_or_alloc_constant_value_id): Adjust. (value_id_constant_p): Remove definition. (get_max_constant_value_id): Define. (get_next_value_id): Add assert for overflow. (get_next_constant_value_id): Define. (run_rpo_vn): Adjust. (free_rpo_vn): Likewise. (do_rpo_vn): Initialize next_constant_value_id. * tree-ssa-pre.c (constant_value_expressions): New. (add_to_value): Split into constant/non-constant value handling. Avoid exact re-allocation. (vn_valnum_from_value_id): Adjust. (phi_translate_1): Remove spurious exact re-allocation. (bitmap_find_leader): Adjust. Make sure we return a CONSTANT value for a constant value id. (do_pre_regular_insertion): Use 2 auto-elements for avail. (do_pre_partial_partial_insertion): Likewise. (init_pre): Allocate constant_value_expressions. (fini_pre): Release constant_value_expressions. --- gcc/tree-ssa-pre.c | 57 ++++++++++++++++++++++++++++++++++------------------ gcc/tree-ssa-sccvn.c | 34 +++++++++++++++++++------------ gcc/tree-ssa-sccvn.h | 12 ++++++++++- 3 files changed, 69 insertions(+), 34 deletions(-) diff --git a/gcc/tree-ssa-pre.c b/gcc/tree-ssa-pre.c index 39c52c9..65e8aaa 100644 --- a/gcc/tree-ssa-pre.c +++ b/gcc/tree-ssa-pre.c @@ -444,6 +444,9 @@ public: /* Mapping from value id to expressions with that value_id. */ static vec value_expressions; +/* ??? We want to just record a single expression for each constant + value, one of kind CONSTANT. */ +static vec constant_value_expressions; /* Sets that we need to keep track of. */ typedef struct bb_bitmap_sets @@ -624,18 +627,30 @@ add_to_value (unsigned int v, pre_expr e) gcc_checking_assert (get_expr_value_id (e) == v); - if (v >= value_expressions.length ()) + if (value_id_constant_p (v)) { - value_expressions.safe_grow_cleared (v + 1, true); - } + if (-v >= constant_value_expressions.length ()) + constant_value_expressions.safe_grow_cleared (-v + 1); - set = value_expressions[v]; - if (!set) - { - set = BITMAP_ALLOC (&grand_bitmap_obstack); - value_expressions[v] = set; + set = constant_value_expressions[-v]; + if (!set) + { + set = BITMAP_ALLOC (&grand_bitmap_obstack); + constant_value_expressions[-v] = set; + } } + else + { + if (v >= value_expressions.length ()) + value_expressions.safe_grow_cleared (v + 1); + 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)); } @@ -687,7 +702,11 @@ vn_valnum_from_value_id (unsigned int val) { bitmap_iterator bi; unsigned int i; - bitmap exprset = value_expressions[val]; + 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); @@ -1451,8 +1470,6 @@ phi_translate_1 (bitmap_set_t dest, else { new_val_id = get_next_value_id (); - value_expressions.safe_grow_cleared (get_max_value_id () + 1, - true); nary = vn_nary_op_insert_pieces (newnary->length, newnary->opcode, newnary->type, @@ -1603,11 +1620,7 @@ phi_translate_1 (bitmap_set_t dest, else { if (changed || !same_valid) - { - new_val_id = get_next_value_id (); - value_expressions.safe_grow_cleared - (get_max_value_id () + 1, true); - } + new_val_id = get_next_value_id (); else new_val_id = ref->value_id; if (!newoperands.exists ()) @@ -1745,7 +1758,7 @@ bitmap_find_leader (bitmap_set_t set, unsigned int val) { unsigned int i; bitmap_iterator bi; - bitmap exprset = value_expressions[val]; + bitmap exprset = constant_value_expressions[-val]; EXECUTE_IF_SET_IN_BITMAP (exprset, 0, i, bi) { @@ -1753,6 +1766,7 @@ bitmap_find_leader (bitmap_set_t set, unsigned int val) if (expr->kind == CONSTANT) return expr; } + gcc_unreachable (); } if (bitmap_set_contains_value (set, val)) { @@ -3190,7 +3204,7 @@ do_pre_regular_insertion (basic_block block, basic_block dom) bool new_stuff = false; vec exprs; pre_expr expr; - auto_vec avail; + auto_vec avail; int i; exprs = sorted_array_from_bitmap_set (ANTIC_IN (block)); @@ -3357,7 +3371,7 @@ do_pre_partial_partial_insertion (basic_block block, basic_block dom) bool new_stuff = false; vec exprs; pre_expr expr; - auto_vec avail; + auto_vec avail; int i; exprs = sorted_array_from_bitmap_set (PA_IN (block)); @@ -4111,7 +4125,9 @@ init_pre (void) expressions.create (0); expressions.safe_push (NULL); value_expressions.create (get_max_value_id () + 1); - value_expressions.safe_grow_cleared (get_max_value_id () + 1, true); + value_expressions.quick_grow_cleared (get_max_value_id () + 1); + constant_value_expressions.create (get_max_constant_value_id () + 1); + constant_value_expressions.quick_grow_cleared (get_max_constant_value_id () + 1); name_to_id.create (0); inserted_exprs = BITMAP_ALLOC (NULL); @@ -4142,6 +4158,7 @@ static void fini_pre () { value_expressions.release (); + constant_value_expressions.release (); expressions.release (); BITMAP_FREE (inserted_exprs); bitmap_obstack_release (&grand_bitmap_obstack); diff --git a/gcc/tree-ssa-sccvn.c b/gcc/tree-ssa-sccvn.c index c139adb..8c9880e 100644 --- a/gcc/tree-ssa-sccvn.c +++ b/gcc/tree-ssa-sccvn.c @@ -288,7 +288,6 @@ vn_constant_hasher::equal (const vn_constant_s *vc1, const vn_constant_s *vc2) } static hash_table *constant_to_value_id; -static bitmap constant_value_ids; /* Obstack we allocate the vn-tables elements from. */ @@ -322,6 +321,7 @@ tree VN_TOP; /* Unique counter for our value ids. */ static unsigned int next_value_id; +static int next_constant_value_id; /* Table of vn_ssa_aux_t's, one per ssa_name. The vn_ssa_aux_t objects @@ -611,20 +611,11 @@ get_or_alloc_constant_value_id (tree constant) vcp = XNEW (struct vn_constant_s); vcp->hashcode = vc.hashcode; vcp->constant = constant; - vcp->value_id = get_next_value_id (); + vcp->value_id = get_next_constant_value_id (); *slot = vcp; - bitmap_set_bit (constant_value_ids, vcp->value_id); return vcp->value_id; } -/* Return true if V is a value id for a constant. */ - -bool -value_id_constant_p (unsigned int v) -{ - return bitmap_bit_p (constant_value_ids, v); -} - /* Compute the hash for a reference operand VRO1. */ static void @@ -5578,14 +5569,32 @@ get_max_value_id (void) return next_value_id; } +/* Return the maximum constant value id we have ever seen. */ + +unsigned int +get_max_constant_value_id (void) +{ + return -next_constant_value_id; +} + /* Return the next unique value id. */ unsigned int get_next_value_id (void) { + gcc_checking_assert ((int)next_value_id > 0); return next_value_id++; } +/* Return the next unique value id for constants. */ + +unsigned int +get_next_constant_value_id (void) +{ + gcc_checking_assert (next_constant_value_id < 0); + return next_constant_value_id--; +} + /* Compare two expressions E1 and E2 and return true if they are equal. */ @@ -6654,7 +6663,6 @@ run_rpo_vn (vn_lookup_kind kind) /* ??? Prune requirement of these. */ constant_to_value_id = new hash_table (23); - constant_value_ids = BITMAP_ALLOC (NULL); /* Initialize the value ids and prune out remaining VN_TOPs from dead code. */ @@ -6721,7 +6729,6 @@ free_rpo_vn (void) delete constant_to_value_id; constant_to_value_id = NULL; - BITMAP_FREE (constant_value_ids); } /* Hook for maybe_push_res_to_seq, lookup the expression in the VN tables. */ @@ -7446,6 +7453,7 @@ do_rpo_vn (function *fn, edge entry, bitmap exit_bbs, / (n_basic_blocks_for_fn (fn) - NUM_FIXED_BLOCKS)); VN_TOP = create_tmp_var_raw (void_type_node, "vn_top"); next_value_id = 1; + next_constant_value_id = -1; vn_ssa_aux_hash = new hash_table (region_size * 2); gcc_obstack_init (&vn_ssa_aux_obstack); diff --git a/gcc/tree-ssa-sccvn.h b/gcc/tree-ssa-sccvn.h index 48701c3..3420e6b 100644 --- a/gcc/tree-ssa-sccvn.h +++ b/gcc/tree-ssa-sccvn.h @@ -269,11 +269,21 @@ bool vn_nary_op_eq (const_vn_nary_op_t const vno1, bool vn_nary_may_trap (vn_nary_op_t); bool vn_reference_may_trap (vn_reference_t); bool vn_reference_eq (const_vn_reference_t const, const_vn_reference_t const); + unsigned int get_max_value_id (void); +unsigned int get_max_constant_value_id (void); unsigned int get_next_value_id (void); +unsigned int get_next_constant_value_id (void); unsigned int get_constant_value_id (tree); unsigned int get_or_alloc_constant_value_id (tree); -bool value_id_constant_p (unsigned int); + +/* Return true if V is a value id for a constant. */ +static inline bool +value_id_constant_p (unsigned int v) +{ + return (int)v < 0; +} + tree fully_constant_vn_reference_p (vn_reference_t); tree vn_nary_simplify (vn_nary_op_t); -- 2.7.4