[tuples] Remove 'next' and 'prev' fields in gimple_statement_base

[tuples] Remove 'next' and 'prev' fields in gimple_statement_base

[Diego Novillo]

[-- Attachment #1: Type: text/plain, Size: 6144 bytes --]

This patch fixes several dozen testsuite failures due to mishandling
of gimple sequences.  In the initial design we had next and prev links
inside gimple statements.  This was causing grief for two reasons:

- It is different than the existing implementation.  So the linked
list manipulation code had corner cases when inserting and removing
statements and sequences into other sequences.

- I would like to change the implementation of sequences to make them
closer to arrays.  I've found a couple of data structures that may be
useful, but for that I needed to make the gimple_seq nodes *not* be
gimple statements.  I will experiment more with this after the branch
is bootstrapping.

Moving 'next' and 'prev' out of gimple means that gimple_seq are now
exactly like STATEMENT_LIST.  I also removed the *_link_* routines, as
they were superfluous.  We don't need to distinguish
tree_stmt_iterator from block_stmt_iterator anymore.  Everything uses
gimple_stmt_iterator now.

Tested on x86.


Diego.

2008-02-19  Diego Novillo  <dnovillo@google.com>

        * tree-complex.c (expand_complex_div_wide): Call gsi_bb.
        * tree.h (std_gimplify_va_arg_expr): Change gimple_seq
        arguments to gimple_seq *.
        Update all users.
        (gimplify_parameters): Change return type to gimple_seq.
        Update all users.
        * target.h (struct gcc_target)<gimplify_va_arg_expr>:
        Change gimple_seq arguments to gimple_seq *.
        Update all users.
        * tree-phinodes.c (free_phinodes): Convert to VEC.
        Update all users.
        * omp-low.c (lower_rec_input_clauses): Change gimple_seq
        arguments to gimple_seq *.  Update all users.
        (lower_reduction_clauses): Convert sub_list to
        gimple_seq.
        (lower_regimplify): Convert PRE to gimple_seq.
        (lower_regimplify): Call gimple_seq_insert_before instead
        of tsi_link_before.
        * tree-gimple.h (get_initialized_tmp_var,
        get_formal_tmp_var, gimplify_expr, gimplify_type_sizes,
        gimplify_one_sizepos, gimplify_stmt, gimplify_and_add,
        gimplify_va_arg_expr): Change gimple_seq arguments to
        gimple_seq *.  Update all users.
        * gimple-iterator.c: Include value-prof.h.
        (gsi_link_seq_before): Remove.  Update all users.
        (gsi_link_seq_after): Remove.  Update all users.
        (gsi_link_after): Remove.  Update all users.
        (gsi_link_before): Remove.  Update all users.
        (update_bb_for_stmts): New.
        (gsi_insert_seq_nodes_before): New.
        (gsi_insert_seq_nodes_after): New.
        (gsi_insert_seq_before): Re-write.  Call
        gsi_insert_seq_nodes_before.
        (gsi_insert_seq_after): Re-write.  Call
        gsi_insert_seq_nodes_after.
        (gsi_replace): Re-enable EH updating.
        (update_modified_stmt): Move earlier in the file.
        (gsi_insert_after): Re-write.  Call
        gsi_insert_seq_nodes_after.
        (gsi_insert_before): Re-write.  Call
        gsi_insert_seq_nodes_before.
        (gsi_remove): Move from gimple.h.  Re-write.
        * langhooks.h (struct lang_hooks): Change gimple_seq
        arguments for gimplify_expr to gimple_seq *.
        Update all users.
        * coretypes.h (struct gimple_seq_d): Rename from struct
        gimple_sequence.  Update all users.
        (struct gimple_seq_node_d): New.
        (gimple_seq_node): New.
        (const_gimple_seq_node): New.
        * tree-flow.h (force_gimple_operand): Change gimple_seq
        argument to gimple_seq *.  Update all users.
        * c-common.h (c_gimplify_expr): Change gimple_seq
        argument to gimple_seq *.  Update all users.
        * Makefile.in (build):
        * gimple.c (gimple_seq_cache): New.
        (gimple_seq_alloc): Take sequences from gimple_seq_cache,
        if possible.
        (gimple_seq_free): New.
        (gimple_seq_add_stmt): Rename from gimple_seq_add.
        Change gimple_seq argument to gimple_seq *.  Update all users.
        (gimple_seq_add_seq): Rename from gimple_seq_append.
        Update all users.
        (gimple_remove): Remove.  Update all users.
        (gimple_seq_reverse): Remove unused function.
        (gimple_set_bb): Only update block-to-labels map if
        CFUN->CFG exists.
        * gimple.h (struct gimple_seq_node_d): New.
        (struct gimple_seq_d): Change fields 'first' and 'last'
        to type gimple_seq_node.  Update all users.
        Add field 'next_free'.
        (gimple_seq_first): Change return type to
        gimple_seq_node.  Update all users.
        (gimple_seq_first_stmt): New.
        (gimple_seq_last): Change return type to gimple_seq_node.
        Update all users.
        (gimple_seq_last_stmt): New.
        (gimple_seq_set_first): Change second argument to type
        gimple_seq_node.  Update all users.
        (gimple_seq_set_last): Change second argument to type
        gimple_seq_node.  Update all users.
        (struct gimple_statement_base): Remove field 'next' and
        'prev'.  Update all users.
        (struct gimple_statement_omp): Change fields of type
        struct gimple_sequence to type gimple_seq.  Update all
        users.
        (struct gimple_statement_bind): Likewise.
        (struct gimple_statement_catch): Likewise.
        (struct gimple_statement_eh_filter): Likewise.
        (struct gimple_statement_try): Likewise.
        (struct gimple_statement_wce): Likewise.
        (struct gimple_statement_omp_for): Likewise.
        (gimple_set_prev): Remove.  Update all users.
        (gimple_set_next): Remove.  Update all users.
        (gimple_next): Remove.  Update all users.
        (gimple_prev): Remove.  Update all users.
        (gimple_seq_bb): New.
        (gimple_catch_handler_ptr): New.
        (gimple_stmt_iterator): Remove field 'stmt'.
        Add field 'ptr'.  Update all users.
        (gsi_remove): Move to gimple-iterator.c
        * tree-cfg.c (pass_build_cfg): Re-enable PROP_gimple_leh.
        * Makefile.in (builtins.o-warn, expr.o-warn, dse.o-warn,
        ebitmap.o-warn, lower-subreg.o-warn, tree-chrec.o-warn):
        Change -Wno-error to -Wno-uninitialized.

[-- Attachment #2: 20080219-remove-next-prev.diff.txt.gz --]
[-- Type: application/x-gzip, Size: 33024 bytes --]

Re: [tuples] Remove 'next' and 'prev' fields in gimple_statement_base

[Zdenek Dvorak]

Hi,

> This patch fixes several dozen testsuite failures due to mishandling
> of gimple sequences.  In the initial design we had next and prev links
> inside gimple statements.  This was causing grief for two reasons:

it might also have some benefits:

-- lower memory consumption
-- less indirection in accessing statements (possibly improving compile
   time)
-- possibility to get iterator for statement in constant time (which is
   occasionally useful, when we get the statement from
   SSA_NAME_DEF_STMT, and want to work with it).

So although for the moment it is probably better to keep things simple
and consistent and make the branch work for now, it moving prev & next
back to gimple_base would probably be an useful future project,

Zdenek

Re: [tuples] Remove 'next' and 'prev' fields in gimple_statement_base

[Diego Novillo]

On Tue, Feb 19, 2008 at 12:10 PM, Zdenek Dvorak <rakdver@kam.mff.cuni.cz> wrote:

>  So although for the moment it is probably better to keep things simple
>  and consistent and make the branch work for now, it moving prev & next
>  back to gimple_base would probably be an useful future project,

Yeah, though instead of keeping a double-linked structure I want to
explore the idea of using a variant of arrays.  With that we can
totally remove next and prev, keep close to constant time iteration
and have efficient insertion/removal in the middle.  One alternative I
looked at are tiered vectors
(http://citeseer.ist.psu.edu/519744.html), which looked half-decent
(but I haven't really tested them).

If that fails, I guess we can always go back to moving next/prev into
gimple itself.


Diego.

Re: [tuples] Remove 'next' and 'prev' fields in gimple_statement_base

[Zdenek Dvorak]

Hi,

> On Tue, Feb 19, 2008 at 12:10 PM, Zdenek Dvorak <rakdver@kam.mff.cuni.cz> wrote:
> 
> >  So although for the moment it is probably better to keep things simple
> >  and consistent and make the branch work for now, it moving prev & next
> >  back to gimple_base would probably be an useful future project,
> 
> Yeah, though instead of keeping a double-linked structure I want to
> explore the idea of using a variant of arrays.  With that we can
> totally remove next and prev, keep close to constant time iteration
> and have efficient insertion/removal in the middle.  One alternative I
> looked at are tiered vectors
> (http://citeseer.ist.psu.edu/519744.html), which looked half-decent
> (but I haven't really tested them).
> 
> If that fails, I guess we can always go back to moving next/prev into
> gimple itself.

my guess is that basic blocks are so short on average that overhead
of anything fancier than linked list or simple array would dominate
any possible gains (and simple arrays are not feasible due to quadratic
behavior on long basic blocks, making linked lists the best choice).
But of course one would need to try some alternatives to be sure,

Zdenek

Re: [tuples] Remove 'next' and 'prev' fields in gimple_statement_base

[Aldy Hernandez]

> - It is different than the existing implementation.  So the linked
> list manipulation code had corner cases when inserting and removing
> statements and sequences into other sequences.

Arghhh, I was hoping we'd never run into statements into separate
sequences.  Oh well...

> Moving 'next' and 'prev' out of gimple means that gimple_seq are now
> exactly like STATEMENT_LIST.  I also removed the *_link_* routines, as

Thanks for doing this.