This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[RFC] value-number tree-combining in FRE
- From: Richard Guenther <rguenther at suse dot de>
- To: gcc-patches at gcc dot gnu dot org
- Date: Fri, 21 Apr 2006 16:50:26 +0200 (CEST)
- Subject: [RFC] value-number tree-combining in FRE
This implements simple tree-combining using value-numbers generated by
FRE. The patch bootstraps and tests on x86_64-unknown-linux, but its
still "incomplete" in that it only combines tcc_unary and tcc_binary.
Also to not complicate FRE, it only combines to results that have their
value-number available already. So it does f.i. not handle
int foo(int i)
{
int j = i - 1;
int k = i + 2;
return j + k;
}
where it has
2: Trying to combine from VH.1 + VH.2 with VH.0 - 1 and VH.0 + 2
2: Results in VH.0 + VH.0 + 1 but no VN for that.
so it strictly only helps to expose more FRE opportunities and is
mostly successful here by eliminating casts. But it does handle the
case where fold can simplify expressions to a constant (as those do
not need value-numbers), such as in
void foo(void*);
static inline char* bar(char * const p)
{
foo(p);
return p;
}
unsigned long baz(char * const p)
{
return (unsigned long)(bar(p+1) - bar(p));
}
So, this is mainly to get some feedback on the idea of integrating
tree-combining with value-numbering - maybe this is a totally crazy idea.
I did not do measurements of the compile-time impact of the patch nor
did I check if the transformation triggers in gcc itself (I mainly
looked through the testcases in bugzilla that mention "tree combiner").
Comments?
Thanks,
Richard.
2006-04-21 Richard Guenther <rguenther@suse.de>
PR tree-optimization/14287
PR tree-optimization/14844 (only with -fwrapv)
PR tree-optimization/19792 (bar() only)
PR tree-optimization/21608
PR tree-optimization/21690
PR tree-optimization/27090
* tree-ssa-pre.c (get_final_vn_from_combined_expr): New
function.
(maybe_combine_vns): Likewise.
(compute_avail): Add do_fre argument. After constructing
the value-handle expression, combine it with previous
value-handles and use the result if it is available.
(execute_pre): Pass do_fre to compute_avail.
Index: tree-ssa-pre.c
===================================================================
*** tree-ssa-pre.c (revision 113113)
--- tree-ssa-pre.c (working copy)
*************** create_expression_by_pieces (basic_block
*** 2458,2463 ****
--- 2458,2586 ----
return name;
}
+ /* Look up the existing value number for the combined EXPR
+ and return it or NULL_TREE. */
+
+ static tree
+ get_final_vn_from_combined_expr (tree expr, int level)
+ {
+ tree vn;
+
+ if (!expr)
+ return expr;
+
+ if (dump_file)
+ {
+ fprintf (dump_file, "%d: Results in ", level);
+ print_generic_expr (dump_file, expr, 0);
+ }
+ if (TREE_CODE (expr) == VALUE_HANDLE
+ || is_gimple_min_invariant (expr))
+ {
+ if (dump_file)
+ fprintf (dump_file, "\n");
+ return expr;
+ }
+
+ vn = vn_lookup (expr, NULL);
+ if (vn)
+ {
+ if (dump_file)
+ {
+ fprintf (dump_file, " with VN ");
+ print_generic_expr (dump_file, vn, 0);
+ fprintf (dump_file, "\n");
+ }
+ return vn;
+ }
+ if (dump_file)
+ fprintf (dump_file, " but no VN for that.\n");
+ return NULL_TREE;
+ }
+
+ /* Try to combine expressions for the value numbers contained in
+ expression EXPR, up to a recursion level of LEVEL. Insert
+ expressions starting from VN, if not NULL. Returns an existing
+ simpler value number, or NULL, if no simplification can be
+ made or there is no value number (and so expression leader) for
+ the simplified expression. */
+
+ static tree
+ maybe_combine_vns (tree vn, int level, basic_block bb)
+ {
+ tree t;
+
+ if (is_gimple_min_invariant (vn))
+ return vn;
+
+ if (TREE_CODE (vn) != VALUE_HANDLE)
+ t = vn;
+ else
+ t = VALUE_HANDLE_EXPR_SET (vn)->head->expr;
+ if (TREE_CODE (t) == SSA_NAME)
+ return vn;
+ /* Fold obviously does not deal with VN.1.VN.2 stuff, but ICEs. */
+ if (REFERENCE_CLASS_P (t))
+ return vn;
+
+ if (--level == 0)
+ return t;
+
+ switch (TREE_CODE_CLASS (TREE_CODE (t)))
+ {
+ case tcc_unary:
+ {
+ tree sub0, tmp;
+ if ((TREE_CODE (TREE_OPERAND (t, 0)) == VALUE_HANDLE
+ && VALUE_HANDLE_VUSES (TREE_OPERAND (t, 0))))
+ return t;
+ sub0 = maybe_combine_vns (TREE_OPERAND (t, 0), level, bb);
+ if (dump_file)
+ {
+ fprintf (dump_file, "%d: Trying to combine from ", level);
+ print_generic_expr (dump_file, t, 0);
+ fprintf (dump_file, " with ");
+ print_generic_expr (dump_file, sub0, 0);
+ fprintf (dump_file, "\n");
+ }
+ tmp = fold_unary (TREE_CODE (t), TREE_TYPE (t), sub0);
+ tmp = get_final_vn_from_combined_expr (tmp, level);
+ if (tmp)
+ return tmp;
+ return build1 (TREE_CODE (t), TREE_TYPE (t), sub0);
+ }
+ case tcc_binary:
+ {
+ tree sub0, sub1, tmp;
+ if ((TREE_CODE (TREE_OPERAND (t, 0)) == VALUE_HANDLE
+ && VALUE_HANDLE_VUSES (TREE_OPERAND (t, 0)))
+ || (TREE_CODE (TREE_OPERAND (t, 1)) == VALUE_HANDLE
+ && VALUE_HANDLE_VUSES (TREE_OPERAND (t, 1))))
+ return t;
+ sub0 = maybe_combine_vns (TREE_OPERAND (t, 0), level, bb);
+ sub1 = maybe_combine_vns (TREE_OPERAND (t, 1), level, bb);
+ if (dump_file)
+ {
+ fprintf (dump_file, "%d: Trying to combine from ", level);
+ print_generic_expr (dump_file, t, 0);
+ fprintf (dump_file, " with ");
+ print_generic_expr (dump_file, sub0, 0);
+ fprintf (dump_file, " and ");
+ print_generic_expr (dump_file, sub1, 0);
+ fprintf (dump_file, "\n");
+ }
+ tmp = fold_binary (TREE_CODE (t), TREE_TYPE (t), sub0, sub1);
+ tmp = get_final_vn_from_combined_expr (tmp, level);
+ if (tmp)
+ return tmp;
+ return build2 (TREE_CODE (t), TREE_TYPE (t), sub0, sub1);
+ }
+ default:
+ ;
+ }
+ return t;
+ }
+
/* Insert the to-be-made-available values of NODE for each
predecessor, stored in AVAIL, into the predecessors of BLOCK, and
merge the result with a phi node, given the same value handle as
*************** realify_fake_stores (void)
*** 3318,3324 ****
AVAIL_OUT[BLOCK] = AVAIL_IN[BLOCK] U PHI_GEN[BLOCK] U TMP_GEN[BLOCK]. */
static void
! compute_avail (void)
{
basic_block block, son;
basic_block *worklist;
--- 3441,3447 ----
AVAIL_OUT[BLOCK] = AVAIL_IN[BLOCK] U PHI_GEN[BLOCK] U TMP_GEN[BLOCK]. */
static void
! compute_avail (bool do_fre)
{
basic_block block, son;
basic_block *worklist;
*************** compute_avail (void)
*** 3430,3438 ****
tree newt = create_value_expr_from (rhs, block, stmt);
if (newt)
{
! add_to_sets (lhs, newt, stmt, TMP_GEN (block),
! AVAIL_OUT (block));
! value_insert_into_set (EXP_GEN (block), newt);
continue;
}
}
--- 3553,3583 ----
tree newt = create_value_expr_from (rhs, block, stmt);
if (newt)
{
! tree tmp = newt;
! if (do_fre)
! tmp = maybe_combine_vns (newt, 3, block);
! if (tmp != newt
! && (TREE_CODE (tmp) == VALUE_HANDLE
! || is_gimple_min_invariant (tmp)))
! {
! if (dump_file)
! {
! fprintf (dump_file, "Combined from ");
! print_generic_expr (dump_file, newt, 0);
! fprintf (dump_file, " to ");
! print_generic_expr (dump_file, tmp, 0);
! fprintf (dump_file, "\n");
! }
! vn_add (lhs, tmp);
! }
! else
! {
! tree val = vn_lookup_or_add (newt, stmt);
! vn_add (lhs, val);
! value_insert_into_set (EXP_GEN (block), newt);
! }
! bitmap_insert_into_set (TMP_GEN (block), lhs);
! bitmap_value_insert_into_set (AVAIL_OUT (block), lhs);
continue;
}
}
*************** execute_pre (bool do_fre)
*** 3823,3829 ****
insert_fake_stores ();
/* Collect and value number expressions computed in each basic block. */
! compute_avail ();
if (dump_file && (dump_flags & TDF_DETAILS))
{
--- 3968,3974 ----
insert_fake_stores ();
/* Collect and value number expressions computed in each basic block. */
! compute_avail (do_fre);
if (dump_file && (dump_flags & TDF_DETAILS))
{