[GSoC] Further work on addressing mode selection

[Erik Varga <erik dot varga256 at gmail dot com>]

Hi all,

I worked on adding an addressing mode selection pass to GCC last year
as part of GSoC 2015, and would like to do some further work on it for
this year's GSoC. Oleg, my mentor for last year's project, said he
would be willing to mentor this year too, if the project gets
accepted.
The current state of the project can be found at [1]. As of commit
2e360ebc47..., compiling the CSiBE set with AMS enabled results in a
0.5% code size improvement on average. (The newer commits introduce
some experimental changes that reduce the improvements a bit, I'm
currently working on addressing that).
For the GSoC project, I'd like to add some further optimization
sub-passes to AMS to achieve better code-size improvements, and fix
the failing test cases so that it can be merged into the GCC trunk.
Once these are finished, I can start extending AMS so that it works on
other architectures (right now, it supports SH only). The project's
proposal can be found at [2].

Here are some code samples to illustrate AMS's current capabilities:

Noticing post-inc opportunities:

int test (char* x)
{
  return x[0] + x[1] + x[2] + x[3];
}

ams:
mov.b @r4+,r0
mov.b @r4+,r1
add r1,r0
mov.b @r4+,r1
add r1,r0
mov.b @r4,r1
rts
add r1,r0

no-ams:
mov.b @(1,r4),r0
mov.b @r4,r2
add r0,r2
mov.b @(2,r4),r0
mov r0,r1
mov.b @(3,r4),r0
add r2,r1
mov r0,r4
mov r1,r0
rts
add r4,r0

Using post-inc to stay within the allowed displacement range:

int test (int* a)
{
  return a[0] + a[16] + a[1] + a[17];
}

ams:
mov.l @r5+,r0
mov.l @(60,r5),r1
add r1,r0
mov.l @r5+,r1
add r1,r0
mov.l @(60,r5),r1

no ams:
mov r5,r1
add #64,r1
mov.l @(0,r1),r2
mov.l @r5,r0
mov.l @(4,r1),r1
add r2,r0
mov.l @(4,r5),r2
add r2,r0

Reusing constants for multiple accesses:

static volatile int* const g_0 = (volatile int*)0x1240;
static volatile int* const g_1 = (volatile int*)0x1244;
static volatile int* const g_2 = (volatile int*)0x1248;
static volatile int* const g_3 = (volatile int*)0x124C;
int fun29 (void)
{
  return *g_0 + *g_1 + *g_2 + *g_3;
}

ams:
mov.w .L98,r1
mov.l @r1,r0
mov.l @(4,r1),r2
add r2,r0
mov.l @(8,r1),r2
mov.l @(12,r1),r1
add r2,r0
rts
add r1,r0
.align 1
.L98:
.short 4672

no-ams:
mov.w .L98,r1
mov.l @r1+,r0
mov.l @r1,r1
add r1,r0
mov.w .L99,r1
mov.l @r1,r1
add r1,r0
mov.w .L100,r1
mov.l @r1,r1
rts
add r1,r0
.align 1
.L98:
.short 4672
.L99:
.short 4680
.L100:
.short 4684

Grouping related accesses and handling them separately (in this case,
the arr1 and arr2 accesses):
int test (int* arr1, int index, int* arr2)
{
  arr1[index+1] = 10;
  *--arr2 = 30;
  arr1[index+2] = 20;
  *--arr2 = 40;
}

ams:
shll2 r5
add r5,r4
mov #10,r1
mov.l r1,@(4,r4)
mov #30,r1
mov.l r1,@-r6
mov #20,r1
mov.l r1,@(8,r4)
mov #40,r1
rts
mov.l r1,@-r6

no-ams:
add #1,r5
mov r5,r0
shll2 r0
mov #10,r1
mov.l r1,@(r0,r4)
add #-64,r6
mov #30,r1
mov.l r1,@(60,r6)
add r0,r4
mov #20,r1
mov.l r1,@(4,r4)
mov #40,r1
rts
mov.l r1,@(56,r6)

Best regards,
Erik

[1] https://github.com/erikvarga/gcc
[2] https://docs.google.com/document/d/1FxeXOJu7C4XcxXDm3zt-vQNtXHNnh2MJbBdDcxQkHN8/edit?usp=sharing