[LLVMdev] interprocedural static backwards slicing

Tue Oct 11 15:42:17 PDT 2011

On 10/11/11 5:05 PM, Jinwook Shin wrote:
> Thanks John for the super quick checkin. I was a little surprised here.

Creating a new project was easy, and it seemed the easiest way to send 
the code to you.
:)

>
> Yesterday/today I spent some time trying to build poolalloc on my mac dev
> machine. Unfortunately, it failed to build [1].

Can you do a make VERBOSE=1 and send me the output?  I'd like to know 
what file it's trying to compile and with what compiler it's compiling 
the file (gcc, llvm-gcc, or clang).

Also, you don't need to build all of poolalloc.  If you compile what's 
in the lib directory, that should suffice.

>   Looks like the compiler
> can't find the header files under /usr/include/c++. I also tried to build
> on my linux box and saw the same problem. giri built successfully. Are you
> sure poolalloc builds on 2.7? 'cause I saw [2]. And the release_26 branch
> of llvm and poolalloc indeed produced a working poolalloc module on my
> box, though giri failed to build with llvm 2.6.

Yes, I'm sure it works with LLVM 2.7.  The README had just not been 
updated (I've fixed that now).

>
> By the way, llvm-gcc v.2.7 was on the PATH while the build break was
> happening. So this time I did a little experiment by removing llvm-gcc 2.7
> from the PATH, and I saw a different error [3]. I guess the system
> llvm-gcc was used for the bitcode generation, hence the mismatch of the
> intrinsic prototype. I'd appreciate some hints here.

You need to use a version of llvm-gcc that matches the version of LLVM 
that you are using.  So, for LLVM 2.7, you need to use the corresponding 
release of llvm-gcc.  What you did for the first build was correct.

>
> I'll give you a separate email regarding contributing code to the LLVM
> community.

Okay.  Thanks.

-- John T.

>
> Thanks,
> Jin
>
> [1]
>
> llvm-2.7/llvm/projects/poolalloc/include/poolalloc/MMAPSupport.h:16:19:
> error: cstdlib: No such file or directory
> llvm-2.7/llvm/projects/poolalloc/include/poolalloc/MMAPSupport.h:17:19:
> error: cassert: No such file or directory
>
> [2]
>
> /llvm-2.7/llvm/projects/poolalloc/README:
>
> KNOWN ISSUES:
> =============
>
> Automatic Pool Allocation is currently broken on 2.7 due to malloc and
> free instructions being removed.  Use the release_26 branch of llvm
> and poolalloc for a working poolalloc module.
>
>
>
> [3]
>
> llvm[2]: Compiling PoolAllocator.cpp for Release build (bytecode)
> llvm[2]: Compiling PoolAllocator.cpp for Release build (PIC)
> llvm[2]: Compiling PoolAllocator.ll to PoolAllocator.bc for Release build
> (bytecode)
> Intrinsic prototype has incorrect number of arguments!
> void (i8*, i8*, i64, i32, i1)* @llvm.memmove.p0i8.p0i8.i64
> Broken module found, compilation aborted!
> 0  opt               0x0000000106fde582 _ZL15PrintStackTracePv + 34
> 1  opt               0x0000000106fdea49 _ZL13SignalHandleri + 553
> 2  libsystem_c.dylib 0x00007fff92d42cfa _sigtramp + 26
> 3  opt               0x0000000106f02ff1
> llvm::UpgradeIntrinsicFunction(llvm::Function*, llvm::Function*&) + 3633
> 4  opt               0x0000000106f97fc7 (anonymous
> namespace)::Verifier::abortIfBroken() + 311
> 5  opt               0x0000000106fa5138 (anonymous
> namespace)::Verifier::runOnFunction(llvm::Function&) + 2304
> 6  opt               0x0000000106f80b7c
> llvm::FPPassManager::runOnFunction(llvm::Function&) + 392
> 7  opt               0x0000000106f7bc7b
> llvm::FPPassManager::runOnModule(llvm::Module&) + 61
> 8  opt               0x0000000106f8085b
> llvm::MPPassManager::runOnModule(llvm::Module&) + 321
> 9  opt               0x0000000106f81a91
> llvm::PassManagerImpl::run(llvm::Module&) + 221
> 10 opt               0x0000000106f81b11
> llvm::PassManager::run(llvm::Module&) + 13
> 11 opt               0x0000000106cc6229 main + 3033
> 12 opt               0x0000000106cbf7a4 start + 52
> 13 opt               0x0000000000000006 start + 18446744069300553878
> Stack dump:
> 0.	Program arguments: /Users/username/llvm-2.7/llvm/Release/bin/opt
> /Users/username/llvm-2.7/llvm/projects/poolalloc/runtime/FL2Allocator/Relea
> se/PoolAllocator.ll -std-compile-opts -strip-debug -o
> /Users/username/llvm-2.7/llvm/projects/poolalloc/runtime/FL2Allocator/Relea
> se/PoolAllocator.bc
> 1.	Running pass 'Function Pass Manager' on module
> '/Users/username/llvm-2.7/llvm/projects/poolalloc/runtime/FL2Allocator/Rele
> ase/PoolAllocator.ll'.
> 2.	Running pass 'Module Verifier' on function '@poolaccesstrace'
> llvm[2]: Linking Release Shared Library poolalloc_rt.dylib
> llvm[2]: Building Release Archive Library libpoolalloc_rt.a
> make[2]: ***
> [/Users/username/llvm-2.7/llvm/projects/poolalloc/runtime/FL2Allocator/Rele
> ase/PoolAllocator.bc] Abort trap: 6
> make[1]: *** [all] Error 1
> make: *** [all] Error 1
>
>
>
> On 10/10/11 9:30 AM, "John Criswell"<criswell at illinois.edu>  wrote:
>
>> On 10/9/11 12:12 AM, Jinwook Shin wrote:
>>> Thanks John. I appreciate your help and I look forward to obtaining the
>>> code.
>>>
>>> A proper LLVM sub-project: No rush on this and please take your time.
>>> Thanks.
>> Okay, I've created a new LLVM sub-project called Giri(*).  It currently
>> contains only the static backwards slicing pass.  I'll add the dynamic
>> slicing code to the project later.
>>
>> The static slicing code works with LLVM 2.7 and the release_27 branch of
>> the poolalloc project (the poolalloc project contains our DSA points-to
>> analysis pass which the static slicing code uses to get the program's
>> callgraph).
>>
>> You can get the code using the following SVN command:
>>
>> cd llvm/projects
>> svn co https://llvm.org/svn/llvm-project/poolalloc/branches/release_27
>> poolalloc
>> svn co https://llvm.org/svn/llvm-project/giri/trunk giri
>>
>> Inside of your LLVM object tree, you need to configure the projects.
>> For example, if your source tree and object tree are the same, you would
>> do:
>>
>> cd llvm/projects
>> cd poolalloc
>> ./configure
>> make
>> cd ../giri
>> ./configure
>> make
>>
>> Right now, the backwards slicing code attempts to find the backwards
>> slice of all stores.  Someone will need to enhance the code to find
>> which stores can reach which loads and to use that information to get a
>> true backwards slice.  Our DSA points-to analysis can be utilized to do
>> that.
>>
>> The code should also be updated to use LLVM mainline (what will be LLVM
>> 3.0).  The interfaces that other passes use to query its results may
>> also need changing.
>>
>> If you're interested in making these changes, I can give you commit
>> access to the giri repository so that you can make changes directly and
>> have them shared with others in the LLVM community.
>>
>> -- John T.
>>
>> (*) For the curious, the project is named "giri" because, to the best of
>> my knowlege, this is a Japanese word that means "slice."  I believe
>> "kiri" may be an alternate spelling.
>>
>>> - Jin
>>>
>>> -----Original Message-----
>>> From: Criswell, John T [mailto:criswell at illinois.edu]
>>> Sent: Saturday, October 08, 2011 11:58 AM
>>> To: Jinwook Shin; llvmdev at cs.uiuc.edu
>>> Subject: RE: interprocedural static backwards slicing
>>>
>>> Dear Jin,
>>>
>>> I've talked with Vikram, and we agree that having this code (and a
>>> dynamic backwards slicing pass that Swarup and I wrote) in a publicly
>>> available SVN repository is a good thing.
>>>
>>> I'll try to get you a copy of the static slicing code some time next
>>> week (I should be able to work on it Monday morning) so that you can
>>> start working with it right away.  I can work on making a proper LLVM
>>> sub-project (ala http://llvm.org/docs/Projects.html) later, although I
>>> don't know exactly when I can get to that (I've got some important work
>>> priorities to contend with in mid-October).
>>>
>>> -- John T.
>>>
>>> ________________________________________
>>> From: Jinwook Shin [Jinwook.Shin at microsoft.com]
>>> Sent: Thursday, October 06, 2011 12:59 PM
>>> To: Criswell, John T; llvmdev at cs.uiuc.edu
>>> Subject: interprocedural static backwards slicing
>>>
>>> Hello John et al -
>>>
>>> I have been struggling to implement static backwards slicing with LLVM.
>>> After digging llvmdev postings for some time, I see that other people
>>> were having similar difficulties and John's got almost complete code
>>> that may be shared. May I get a copy of it, too? Better yet, it would be
>>> helpful for many other people if the code were checked in to an example
>>> directory or something in the LLVM source branch.
>>>
>>> Thanks!
>>> - Jin
>>>
>>>
>>