[GSoC] Further work on addressing mode selection
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
[gsoc] Generic addressing mode selection
Hi all, I'm Erik Krisztián Varga, a 2nd year Electrical Engineering student, and I'd be interested in contributing to gcc as part of GSoC 2015. I'd like to work on adding an addressing mode selection pass to the RTL based on the ideas described in Eckstein et. al.'s paper on the subject [1]. The basic idea is to reduce the problem to a Partitioned Boolean Quadratic Programming (PBQP) problem and to find a close-to-optimal solution with a heuristic algorithm. It should be possible to model a lot of addressing modes with the cost matrix approach described in the paper, so this would be a generic way to do AMS for different architectures. Quite a few things would have to be done to implement the algorithm, like finding the correct models for the various addressing instructions in the supported architectures, or implementing an efficient representation of the cost vectors and matrices, but I think it should be possible in the scope of a Summer to have at least a working prototype ready. Would someone be interested in mentoring this project for GSoC? Is there anything similar currently being worked on? I think Oleg Endo has started implementing such a pass a while ago (mentioned in PR56590). Best regards, Erik [1] http://sydney.edu.au/engineering/it/~scholz/publications/cgo03.pdf
Re: [gsoc] Generic addressing mode selection
On Sun, Mar 22, 2015 at 10:10 PM, Oleg Endo wrote: > The PBQP approach is indeed very tempting, but there > are a lot more things to it than just the solver. To get good > improvements of the generated code, the optimization also has to be able > to reorder memory accesses and perform other transformations such as > converting pre-inc into post-inc modes in loops etc. I confess there are some optimizations that the PBQP approach doesn't take into account, like reordering the instructions. Could you elaborate a bit on the prec-inc to post-inc conversion? I might be missing something, but I think the PBQP algorithm should have no problem transforming the addressing mode to post-inc if that makes the overall cost less. Of course, PBQP is just one approach, and I would be willing to try other methods. > Although my point of view is a bit > SH biased, I believe that once it's working on SH, other platforms will > benefit from it. Yeah, it's probably a good idea to implement AMS for a specific platform first, and SH does have a variety of addressing modes. > The scope would > need to be narrowed down a bit for a GSoC project, but if you want, we > could give it a try and I would step forward as a mentor. I'd like to give this a try, I'm sure a lot could be achieved in a summer. Could you share how you planned to approach the problem? I'd also be interested in some of the papers you found (I haven't yet been able to find much on the subject apart from the PBQP method). Best regards, Erik
Re: [gsoc] Generic addressing mode selection
Hi all, I've submitted my proposal to the GSoC website, it can be found here: [1] After hearing some ideas from Oleg, I decided to go with working on detecting and optimizing a few specific memory access patterns instead of implementing a PBQP solver. Any suggestions or comments are welcome. I read that it's necessary to have a copyright assignment filed with the Free Software Foundation to be able to contribute larger amounts of code to GCC. When would it be best to start applying for a copyright assignment (e.g. sometime during the community bonding period, or the coding period, or around now)? Best regards, Erik [1] http://www.google-melange.com/gsoc/proposal/public/google/gsoc2015/erikvarga/5676830073815040
Re: [gsoc] Generic addressing mode selection
On Thu, Mar 26, 2015 at 11:46 PM, Oleg Endo wrote: > On Thu, 2015-03-26 at 09:43 -0600, Jeff Law wrote: >> If you're looking at exploiting auto-inc addressing, others and myself >> have speculated that something built around >> straight-line-strength-reduction at the RTL level would be ideal for >> exploiting that capability. >> >> That may be more suitable for a GSOC project than tackling the entire >> space of address mode selections. > > As far as I understand the proposal, the goal is not to solve all AMS > problems, but rather to lay the foundation for doing these kinds of > optimizations and deal with a few assorted ones (most likely auto-mod > will be a candidate). Thus, I think Erik's proposal sounds feasible, > although I'd expect some of the allocations/priorities in the schedule > to change during the project. But that's not something unusual to > happen. That's right, the project's aim is to handle some specific access patterns and, in the process, build a framework that makes subsequent optimizations easier to write, not to tackle AMS in its entirety. I'll reword the proposal a bit to more accurately reflect this. Best regards, Erik
