Out Of SSA Rewrite - New TER implementation

Andrew MacLeod amacleod@redhat.com
Tue Nov 21 19:06:00 GMT 2006

This patch re-implements TER.  The fundamental idea remains the same...
step through the function determining tracking which single use
expressions are currently available for substitution,  and marking them
as replaceable if the use is seen while they are still valid.

The list of "current" values was maintained in a linked list, and the
patch in  http://gcc.gnu.org/ml/gcc-patches/2006-08/msg00896.html
replaced that with a bitmap, which turns out ot be much faster in the
more horrible cases.

On top of that a lot of functions have been renamed to make them
clearer, a long description of what TER does and how is at the top of
the file.  The mechanism for tracking current expressions is different
now as well. This allows TER to get a few cases it couldn't get before,
addressing a couple of open PRs.  Although it shares similar
functionality, this really is a rewrite of TER. 

It has also been moved to its own self contained file, tree-ssa-ter.c.
I'd suggest just reading the file rather than the patch :-)

Bootstrapped and regression tested on i686-pc-linux-gnu.  There is one
additional regression caused by this patch. I will address that efore
checking anything in.

It appears to be a bug in the expansion code.

The testcase is gfortran.fortran-torture/execute/st_function.f90.

TER expands 2 additional expression which it didn't before.

    D.1261 = (char[1:] *) &"0123456789"[1]{lb: 1 sz: 1};
    __builtin_memcpy (&st4.6, D.1261, 4);

now gets expanded to 

  __builtin_memcpy (&st4.6, (char[1:] *) &"0123456789"[1]{lb: 1 sz: 1}, 4);


    p1 = (char[1:4] *) &i;
    __builtin_memmove (&p.1, p1, 4);

gets expanded to 

    __builtin_memmove (&p.1, (char[1:4] *) &i, 4);

I haven't investigated which is being handled incorrectly yet, but will
look into it before checking the code in.


	* Makefile.in: Add new file tree-ssa-ter.c.
	* tree-outof-ssa.c (struct temp_expr_table_d, new_temp_expr_table, 
	free_temp_expr_table, add_value_to_version_list, 
	add_value_to_partition_list, remove_value_from_partition_list, 
	add_dependence, check_replaceable, finish_expr, mark_replaceable, 
	kill_expr, kill_virtual_exprs, find_replaceable_in_bb, 
	find_replaceable_exprs, dump_replaceable_exprs): Move to tree-ssa-ter.c.
	* tree-ssa-live.h (find_replaceable_exprs, dump_replaceable_exprs): Add
	* tree-ssa-ter.c: New file.
	(struct value_expr_d): Remove.
	(struct temp_expr_table_d): Rename fields, add explicit vector of
	replaceable expressions instead of sharing. Change value_expr_p's to 
	bitmap.  Delete free_list.
	(new_temp_expr_table): Rename fields, count number of ssa_names in
	each partition.
	(free_temp_expr_table): Rename field, free new fields.
	(new_value_expr, free_value_expr, find_value_in_list, add_value_to_list,
	add_info_to_list, remove_value_from_list): Delete.
	(version_to_be_replaced_p): New. Is an ssa-name replaceable?
	(make_dependent_on_partition): New. Set bit in version list, allocating
	a bitmap if need be.
	(add_to_partition_kill_list): New.  Set bit in the partition list,
	allocating a bitmap if need be.
	(remove_from_partition_kill_list): New.  Remove a bit from the
	partition list, free the bitmap if it is empty.
	(add_dependence): Use renamed field, cleanup. Don't add a dependence
	on partitions with only one member.
	(is_replaceable_p): New.  Split out replaceability check from 
	(process_replaceable): New. Replacement code split from 
	(check_replaceable): Removed.
	(finished_with_expr): Renamed from finish_expr.
	(kill_expr): Use renamed fields. Less parameters.
	(kill_virtual_exprs): Less parameters.
	(mark_replaceable): Use renamed fields.
	(find_replaceable_in_bb): Use renamed fields, cleanup.
	(find_replaceable_exprs): Use renamed routines, cleanup.
	(dump_replaceable_exprs): don;t go past end of ssa_names list.
	(debug_ter): New.  Debug routine to dump state.

-------------- next part --------------
A non-text attachment was scrubbed...
Name: ter.diff
Type: text/x-patch
Size: 51804 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/gcc-patches/attachments/20061121/d4fc60d7/attachment.bin>

More information about the Gcc-patches mailing list