openacc: Shared memory layout optimisation

openacc: Shared memory layout optimisation

This patch implements an algorithm to lay out local data-share (LDS)
space.  It currently works for AMD GCN.  At the moment, LDS is used for
three things:

  1. Gang-private variables
  2. Reduction temporaries (accumulators)
  3. Broadcasting for worker partitioning

After the patch is applied, (2) and (3) are placed at preallocated
locations in LDS, and (1) continues to be handled by the backend (as it
is at present prior to this patch being applied). LDS now looks like this:

  +--------------+ (gang-private size + 1024, = 1536)
  | free space   |
  |    ...       |
  | - - - - - - -|
  | worker bcast |
  +--------------+
  | reductions   |
  +--------------+ <<< -mgang-private-size=<number> (def. 512)
  | gang-private |
  |    vars      |
  +--------------+ (32)
  | low LDS vars |
  +--------------+ LDS base

So, gang-private space is fixed at a constant amount at compile time
(which can be increased with a command-line switch if necessary
for some given code). The layout algorithm takes out a slice of the
remainder of usable space for reduction vars, and uses the rest for
worker partitioning.

The partitioning algorithm works as follows.

 1. An "adjacency" set is built up for each basic block that might
    do a broadcast. This is calculated by starting at each such block,
    and doing a recursive DFS walk over successors to find the next
    block (or blocks) that *also* does a broadcast
    (dfs_broadcast_reachable_1).

 2. The adjacency set is inverted to get adjacent predecessor blocks also.

 3. Blocks that will perform a broadcast are sorted by size of that
    broadcast: the biggest blocks are handled first.

 4. A splay tree structure is used to calculate the spans of LDS memory
    that are already allocated by the blocks adjacent to this one
    (merge_ranges{,_1}.

 5. The current block's broadcast space is allocated from the first free
    span not allocated in the splay tree structure calculated above
    (first_fit_range). This seems to work quite nicely and efficiently
    with the splay tree structure.

 6. Continue with the next-biggest broadcast block until we're done.

In this way, "adjacent" broadcasts will not use the same piece of
LDS memory.

PR96334 "openacc: Unshare reduction temporaries for GCN" got merged in:

The GCN backend uses tree nodes like MEM((__lds TYPE *) <constant>)
for reduction temporaries. Unlike e.g. var decls and SSA names, these
nodes cannot be shared during gimplification, but are so in some
circumstances. This is detected when appropriate --enable-checking
options are used. This patch unshares such nodes when they are reused
more than once.

gcc/
	* config/gcn/gcn-protos.h
	(gcn_goacc_create_worker_broadcast_record): Update prototype.
	* config/gcn/gcn-tree.c (gcn_goacc_get_worker_red_decl): Use
	preallocated block of LDS memory.  Do not cache/share decls for
	reduction temporaries between invocations.
	(gcn_goacc_reduction_teardown): Unshare VAR on second use.
	(gcn_goacc_create_worker_broadcast_record): Add OFFSET parameter
	and return temporary LDS space at that offset.  Return pointer in
	"sender" case.
	* config/gcn/gcn.c (acc_lds_size, gang_private_hwm, lds_allocs):
	New global vars.
	(ACC_LDS_SIZE): Define as acc_lds_size.
	(gcn_init_machine_status): Don't initialise lds_allocated,
	lds_allocs, reduc_decls fields of machine function struct.
	(gcn_option_override): Handle default size for gang-private
	variables and -mgang-private-size option.
	(gcn_expand_prologue): Use LDS_SIZE instead of LDS_SIZE-1 when
	initialising M0_REG.
	(gcn_shared_mem_layout): New function.
	(gcn_print_lds_decl): Update comment. Use global lds_allocs map and
	gang_private_hwm variable.
	(TARGET_GOACC_SHARED_MEM_LAYOUT): Define target hook.
	* config/gcn/gcn.h (machine_function): Remove lds_allocated,
	lds_allocs, reduc_decls. Add reduction_base, reduction_limit.
	* config/gcn/gcn.opt (gang_private_size_opt): New global.
	(mgang-private-size=): New option.
	* doc/tm.texi.in (TARGET_GOACC_SHARED_MEM_LAYOUT): Place
	documentation hook.
	* doc/tm.texi: Regenerate.
	* omp-oacc-neuter-broadcast.cc (targhooks.h, diagnostic-core.h):
	Add includes.
	(build_sender_ref): Handle sender_decl being pointer.
	(worker_single_copy): Add PLACEMENT and ISOLATE_BROADCASTS
	parameters.  Pass placement argument to
	create_worker_broadcast_record hook invocations.  Handle
	sender_decl being pointer and isolate_broadcasts inserting extra
	barriers.
	(blk_offset_map_t): Add typedef.
	(neuter_worker_single): Add BLK_OFFSET_MAP parameter.  Pass
	preallocated range to worker_single_copy call.
	(dfs_broadcast_reachable_1): New function.
	(idx_decl_pair_t, used_range_vec_t): New typedefs.
	(sort_size_descending): New function.
	(addr_range): New class.
	(splay_tree_compare_addr_range, splay_tree_free_key)
	(first_fit_range, merge_ranges_1, merge_ranges): New functions.
	(execute_omp_oacc_neuter_broadcast): Rename to...
	(oacc_do_neutering): ... this.  Add BOUNDS_LO, BOUNDS_HI
	parameters.  Arrange layout of shared memory for broadcast
	operations.
	(execute_omp_oacc_neuter_broadcast): New function.
	(pass_omp_oacc_neuter_broadcast::gate): Remove num_workers==1
	handling from here.  Enable pass for all OpenACC routines in order
	to call shared memory-layout hook.
	* target.def (create_worker_broadcast_record): Add OFFSET
	parameter.
	(shared_mem_layout): New hook.
libgomp/
	* testsuite/libgomp.oacc-c-c++-common/broadcast-many.c: Update.