[RFC] Implement load sinking in loops

[Eric Botcazou]

Hi,

we recently noticed that, even at -O3, the compiler doesn't figure out that 
the following loop is dumb:

#define SIZE 64

int foo (int v[])
{
  int r;

  for (i = 0; i < SIZE; i++)
    r = v[i];

  return r;
}

which was a bit of a surprise.  On second thoughts, this isn't entirely 
unexpected, as it probably matters only for (slightly) pathological cases.
The attached patch nevertheless implements a form of load sinking in loops so 
as to optimize these cases.  It's combined with invariant motion to optimize:

int foo (int v[], int a)
{
  int r, i;

  for (i = 0; i < SIZE; i++)
    r = v[i] + a;

  return r;
}

and with store sinking to optimize:

int foo (int v1[], int v2[])
{
  int r[SIZE];
  int i, j;

  for (j = 0; j < SIZE; j++)
    for (i = 0; i < SIZE; i++)
      r[j] = v1[j] + v2[i];

  return r[SIZE - 1];
}

The optimization is enabled at -O2 in the patch for measurement purposes but, 
given how rarely it triggers (e.g. exactly 10 occurrences in a GCC bootstrap, 
compiler-only, all languages except Go), it's probably best suited to -O3.
Or perhaps we don't care and it should simply be dropped...  Thoughts?

Tested on x86_64-suse-linux.


2012-10-08  Eric Botcazou  <ebotcazou@adacore.com>

	* gimple.h (gsi_insert_seq_on_edge_before): Declare.
	* gimple-iterator.c (gsi_insert_seq_on_edge_before): New function.
	* tree-ssa-loop-im.c (struct mem_ref_loc): Add LHS field.
	(mem_ref_in_stmt): Remove gcc_assert.
	(copy_load_and_single_use_chain): New function.
	(execute_lm): Likewise.
	(hoist_memory_references): Hoist the loads after the stores.
	(ref_always_accessed_p): Rename into...
	(ref_always_stored_p): ...this.  Remove STORE_P and add ONCE_P.
	(can_lsm_ref_p): New function extracted from...
	(can_sm_ref_p): ...here.  Call it.
	(follow_invariant_single_use_chain): New function.
	(can_lm_ref_p): Likewise.
	(find_refs_for_sm): Rename into..
	(find_refs_for_lsm): ...this.  Find load hoisting opportunities.
	(loop_suitable_for_sm): Rename into...
	(loop_suitable_for_lsm): ...this.
	(store_motion_loop): Rename into...
	(load_store_motion_loop): ...this.  Adjust calls to above functions.
	(tree_ssa_lim): Likewise.


2012-10-08  Eric Botcazou  <ebotcazou@adacore.com>

	* gcc.dg/tree-ssa/loadmotion-1.c: New test.
	* gcc.dg/tree-ssa/loadmotion-2.c: New test.
	* gcc.dg/tree-ssa/loadmotion-3.c: New test.


-- 
Eric Botcazou
-------------- next part --------------
A non-text attachment was scrubbed...
Name: p.diff
Type: text/x-patch
Size: 20250 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/gcc-patches/attachments/20121008/537205bc/attachment.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: loadmotion-1.c
Type: text/x-csrc
Size: 321 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/gcc-patches/attachments/20121008/537205bc/attachment-0001.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: loadmotion-2.c
Type: text/x-csrc
Size: 366 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/gcc-patches/attachments/20121008/537205bc/attachment-0002.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: loadmotion-3.c
Type: text/x-csrc
Size: 391 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/gcc-patches/attachments/20121008/537205bc/attachment-0003.bin>