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

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.

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.

- Jin

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.

Thanks John for the super quick checkin. I was a little surprised here.

Yesterday/today I spent some time trying to build poolalloc on my mac dev
machine. Unfortunately, it failed to build [1]. 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.

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.

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

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:

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.
:slight_smile:

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.

Hi John,

Attached is the output. Looks like llvm-g++ was used when the error
occurred. Yes, I can build what's in the lib directory, so I'm now
unblocked.

Thanks,
Jin

make.log (86.7 KB)