On Mar 1, 2008, at 3:40 AM, Richard Warburton wrote:>> Also, LLVM benefits quite a bit from mod/ref info for function. I
>> don't know if you've thought about it at all, but it is an
important
>> problem. If you're interested, my thesis describes these issues in
>> detail.
>
> I'll peruse this, are there any other relevant, LLVM specific texts
> that are appropriate for this, and not linked from the documentation
> page[0] ?
Not that I know of.
>>> 1. Is this too ambitious for a google summer of code project?
>>
>> It depends on your familiarity with the domain. If you haven't
>> worked
>> in the area of alias analysis (and applications) it probably is.
>> There are lot of smaller subprojects that would be useful for llvm
>> though.
>
> In order that I may be to gauge what options there are, can you
> suggest some examples of these subprojects.
There are lots of mini projects, revolving around use of better alias
analysis:
1. The alias analysis API supports the getModRefBehavior method, which
allows the implementation to give details analysis of the functions.
For example, we could implement full knowledge of printf/scanf side
effects, which would be useful (PR1604).
2. We need some way to reason about errno. Consider a loop like this:
for ()
x += sqrt(loopinvariant);
We'd like to transform this into:
t = sqrt(loopinvariant);
for ()
x += t;
This transformation is safe, because the value of errno isn't
otherwise changed in the loop and the exit value of errno from the
loop is the same. We currently can't do this, because sqrt clobbers
errno, so it isn't "readonly" or "readnone" and we
don't have a good
way to model this.
The hard part of this project is figuring out how to describe errno
in the optimizer: each libc #defines errno to something different it
seems. Maybe the solution is to have a __builtin_errno_addr() or
something and change sys headers to use it.
3. An easy project is to add the 'nocapture' attribute to the LLVM IR
(PR2055) and have passes infer and propagate it around. Its presence
can significantly improve local alias analysis at very low cost.
4. The globals mod/ref pass basically does really simple and cheap
bottom-up context sensitive alias analysis. It being simple and cheap
are really important, but there are simple things that we could do to
better capture the effects of functions that access pointer
arguments. This can be really important for C++ methods, which spend
lots of time accessing pointers off 'this'.
5. There are lots of ways to optimize out and improve handling of
memcpy/memset (PR452)
6. It would be excellent to replace loops with scalar stores in them
into memset/memcpy calls. This dramatically speeds up programs like
'viterbi' in the testsuite.
7. There may still be some ideas in PR1373 left.
-Chris