Re: [PATCH]: Rewrite tree level PRE

["Richard Guenther" <richard dot guenther at gmail dot com>]

On Sun, Jul 6, 2008 at 6:33 AM, Daniel Berlin <dberlin@dberlin.org> wrote:
> This patch effectively rewrites tree PRE to share datastructures with
> tree-vn, instead of copying statements and modifying trees (which
> don't work so well in a tuples world :P).
>
> As part of the rewrite, it also fixes a bunch of missed optimizations
> because PRE will now move globals.
> It also uses roughly half as much memory as before (since PRE no
> longer copies statements but instead shares the vn structures with the
> vn).
> The fundamentals are the same as they were before, it simply no longer
> does it's own value numbering.
> Since PRE was the only user of VALUE_HANDLES, i have removed them as
> part of this patch.
> Since PRE was the only user of most of tree-vn.c, i removed it and
> moved the 3 still-used functions to tree-ssa-sccvn.c
> PRE is also now type correct, in that the insertions it creates should
> have matched types, whereas before they were generally a mismash (it
> would happily create phi nodes whose arguments had mixed types, etc).
>
> This patch will cause some FRE failures due to a small bit of code i
> disabled in tree-ssa-sccvn.c.  I have discussed this with richard
> guenther and he has said he will fix it up, so the ssa-fre-* failures
> are temporary.
>
> Other than than PRE of globals, it should PRE all of the expressions
> we used to, plus a few more in the way of loads.  I have verified this
> by hand comparing the eliminations performed during a bootstrap of
> gcc.
> I have not performed more benchmarking than that, as the main goal was
> a feature equivalent rewrite that would enable tuple conversion to
> procede. The fact that it will PRE globals is simply a side effect of
> sharing a representation with the VN.
>
> The patch is large but 99% of it is the rewritten tree-ssa-pre.c.
>
> Bootstrapped and regtested on i686-darwin (With the safe-ctype change
> reverted) and i686-linux.
> I will wait a few days for comments before committing it (All the code
> outside of PRE that I am removing was added as part of PRE, but if
> someone wants to object to it's removal, please let me know).

This triggers a latent issue in SCCVN (it breaks bootstrap on x86_64 with Ada).

copy_reference_ops_from_ref for ARRAY_REF also needs to record
TREE_OPERAND (ref, 2) (likewise foro COMPONENT_REF).

Without that we ICE during gimplifying of

(*pretmp.7645_139)[pretmp.7649_143]{lb: (long int) <PLACEHOLDER_EXPR
struct types__text_buffer___XUP>.P_BOUNDS->LB0 sz: 1}

#1  0x00000000009be6ab in gimplify_expr (expr_p=0x2b0b398ed8f0,
    pre_p=0x7fff721f58d8, post_p=0x7fff721f5088,
    gimple_test_f=0xb7cfe4 <is_gimple_min_lval>, fallback=fb_either)
    at ../../trunk/gcc/gimplify.c:6321
...
#10 0x00000000009c16b0 in force_gimple_operand (expr=0x2b0b398ed820,
    stmts=0x7fff721f58d8, simple=0 '\0', var=0x0)
    at ../../trunk/gcc/gimplify.c:6825
#11 0x0000000000cc9859 in create_expression_by_pieces (block=0x2b0b39c5c480,
    expr=0x1ecd1c8, stmts=0x2b0b39914360, domstmt=0x0, type=0x2b0b38ea9480)
---Type <return> to continue, or q <return> to quit---
    at ../../trunk/gcc/tree-ssa-pre.c:2667

we obviously cannot use the PLACEHOLDER_EXPR, but need to use the
gimplified value that was stored in the ARRAY_EXPRs operand 3.

So, the number of ops in vn_reference_op_struct needs to increase by one.

To reproduce

./xgcc -B. -B/usr/local/x86_64-unknown-linux-gnu/bin/ -c -g -O2
-gnatpg -gnata -gnatwns -nostdinc -I- -I. -Iada -I../../trunk/gcc/ada
../../trunk/gcc/ada/ali.adb -o ada/ali.o

in the stage1 gcc/ dir.

Richard.

> 2008-07-05  Daniel Berlin  <dberlin@dberlin.org>
>
>        Fix PR tree-optimization/23455
>        Fix PR tree-optimization/35286
>        Fix PR tree-optimization/35287
>        * Makefile.in (OBJS-common): Remove tree-vn.o.
>        tree-vn.o: Remove.
>        * dbgcnt.def: Add treepre_insert debug counter.
>        * gcc/tree-flow.h (add_to_value): Updated for other changes.
>        (debug_value_expressions): Ditto.
>        (print_value_expressions): Ditto.
>        * tree-pretty-print.c (dump_generic_node): Updated for
>        VALUE_HANDLE removal.
>        * tree-ssa-dom.c (record_equality): Ditto.
>        (cprop_operand): Ditto.
>        (lookup_avail_expr): Ditto.
>        * tree-ssa-threadedge.c
>        (record_temporary_equivalences_from_stmts_at_dest): Ditto.
>        (simplify_control_stmt_condition): Ditto.
>        * tree.c (tree_code_size): Ditto.
>        (tree_node_structure): Ditto.
>        (iterative_hash_expr): Ditto.
>        * tree.def: Ditto.
>        * tree.h (VALUE_HANDLE_ID): Ditto.
>        (VALUE_HANDLE_EXPR_SET): Ditto.
>        (struct tree_value_handle): Ditto.
>        (union tree_node): Ditto.
>        * treestruct.def: Ditto.
>        * tree-vn.c: Removed.
>        * tree-ssa-pre.c: Rewritten entirely.
>        * tree-ssa-sccvn.c (constant_to_value_id): New hashtable.
>        (constant_value_ids): Ditto.
>        (vn_nary_op_t): Moved to header.
>        (vn_phi_t): Ditto.
>        (vn_reference_op_t): Ditto
>        (vn_reference_t): Ditto.
>        (next_value_id): New variable.
>        (VN_INFO): Add an assert.
>        (vn_constant_eq): New function.
>        (vn_constant_hash): Ditto.
>        (get_or_alloc_constant_value_id): Ditto.
>        (value_id_constant_p): Ditto.
>        (vn_reference_compute_hash): De-staticify.
>        (copy_reference_ops_from_ref): Don't use get_callee_fndecl.
>        Disable some code with a FIXME.
>        Remove VALUE_HANDLE use.
>        (valueize_refs): Update opcode if it changes from ssa name to
>        constant.
>        (vn_reference_lookup_1): Add new argument.
>        (vn_reference_lookup):  Ditto.
>        (vn_reference_lookup_pieces): New function.
>        (vn_reference_insert): Add return type. Modify to deal with value
>        ids.
>        (vn_reference_insert_pieces):  New function.
>        (vn_nary_op_compute_hash): De-staticify.
>        (vn_nary_op_eq): Ditto.
>        (vn_nary_op_lookup_pieces): New function.
>        (vn_nary_op_lookup): Add new argument.
>        (vn_nary_op_insert_pieces): New function.
>        (vn_nary_op_insert): Add return type. Modify to deal with value
>        ids.
>        (vn_phi_insert): Ditto.
>        (visit_unary_op): Update for callee changes.
>        (visit_binary_op): Ditto.
>        (visit_reference_op_load): Ditto.
>        (visit_reference_op_store): Ditto.
>        (init_scc_vn): Init next_value_id, constant_to_value_id and constant_value_ids.
>        (free_scc_vn): Free them.
>        (set_hashtable_value_ids): New function.
>        (run_scc_vn): Use it.
>        (get_max_value_id): New function.
>        (get_next_value_id): Ditto.
>        (expressions_equal_p): Moved from tree-vn.c
>        (sort_vuses): Ditto.
>        (sort_vuses_heap): Ditto.
>        * tree-ssa-sccvn.h: Structures moved from tree-ssa-sccvn.c (noted
>        above).
>
>
> --Dan
>