[LLVMdev] Google Summer of Code Idea

[Chris Lattner]

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