llvm dev - May 2015 - [LLVMdev] llvm DSA - reproduce the result in PLDI 07 paper

Dear all,
I am trying to reproduce the "Percent May Alias" result described in
PLDI
07's paper "Making Context-Sensitive Points-to Analysis with Heap
Cloning
Practical For The Real World"
(http://llvm.org/pubs/2007-06-10-PLDI-DSA.html
).

However, my "Percent May Alias" for all the benchmarks is much
greater,
especially "bzip2".

The DSA code I use is from "https://github.com/smackers/smack". I have
diff
the code between smack and poolalloc_32. They are almost the same except
the "#include" statements.

I was wondering whether I need to do some configuration to make DSA work
properly.

Thank you!

Zhiyuan
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150406/16f18f2d/attachment.html>

Dear Zhiyuan,

In order to reproduce the results from the paper, you'll need to 
replicate a system from that era.  You'll need to use the same version 
of LLVM and DSA that the paper used.  I think that was LLVM 1.9 (the 
release_19 branch of LLVM and poolalloc), but I'm not sure.  You should 
check to see if the paper specifies the version.

As you'll be using a very old version of LLVM, it may be worth setting 
up a VM with a corresponding old version of Linux.  I suspect newer 
compilers will not compile a version of LLVM that is that old, so using 
an old version of Linux with an old version of GCC may be needed.  I 
think Fedora Core 2 is the OS we were using at the time.

To answer the question of why you can't use a modern version of LLVM and 
poolalloc, it's because LLVM has changed significantly. DSA relies upon 
the type annotations provided in the LLVM IR to "bootstrap" its type 
inference (bootstrap is not quite the right word, but it's the closest 
one of which I could think).  As LLVM matured, transformations would 
ditch the type information (e.g., transforming typed GEPs into untyped 
GEPs into a byte array), making DSA's ability to do type-inference (and 
thereby improving field sensitivity) more difficult.  Throw into the mix 
the fact that DSA is maintained by an academic research group, and the 
result is that modern DSA doesn't have the accuracy that the original 
DSA did.

The good news is that I think DSA can be fixed by making its 
type-inferencing code smarter.  The bad news is that it'd be a fair 
amount of work to do.  So far, no one has had sufficient 
desire/motivation to design and implement the improvements.

Regards,

John Criswell


On 4/6/15 4:56 PM, Wan Zhiyuan wrote:
> Dear all,
> I am trying to reproduce the "Percent May Alias" result described
in
> PLDI 07's paper "Making Context-Sensitive Points-to Analysis with
Heap
> Cloning Practical For The Real World" 
> (http://llvm.org/pubs/2007-06-10-PLDI-DSA.html).
>
> However, my "Percent May Alias" for all the benchmarks is much 
> greater, especially "bzip2".
>
> The DSA code I use is from "https://github.com/smackers/smack". I
have
> diff the code between smack and poolalloc_32. They are almost the same 
> except the "#include" statements.
>
> I was wondering whether I need to do some configuration to make DSA 
> work properly.
>
> Thank you!
>
> Zhiyuan
>
>
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

-- 
John Criswell
Assistant Professor
Department of Computer Science, University of Rochester
http://www.cs.rochester.edu/u/criswell

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150406/c69b71ab/attachment.html>

Dear John,
I intend to implement the improvements on DSA.
After running DSA on SPEC, I found DSA gives low precision for mcf and
bzip2.
I have checked the most imprecise c files in mcf an found that the code
seems to be a mixture of "PHI" and "GEP" instructions.

Could you please give me some hints about what the big picture of the
improvement should be and how to start?

Thank you!

Regards,
Zhiyuan

On Mon, Apr 6, 2015 at 5:22 PM, John Criswell <jtcriswel at gmail.com>
wrote:
>  Dear Zhiyuan,
>
> In order to reproduce the results from the paper, you'll need to
replicate
> a system from that era.  You'll need to use the same version of LLVM
and
> DSA that the paper used.  I think that was LLVM 1.9 (the release_19 branch
> of LLVM and poolalloc), but I'm not sure.  You should check to see if
the
> paper specifies the version.
>
> As you'll be using a very old version of LLVM, it may be worth setting
up
> a VM with a corresponding old version of Linux.  I suspect newer compilers
> will not compile a version of LLVM that is that old, so using an old
> version of Linux with an old version of GCC may be needed.  I think Fedora
> Core 2 is the OS we were using at the time.
>
> To answer the question of why you can't use a modern version of LLVM
and
> poolalloc, it's because LLVM has changed significantly.  DSA relies
upon
> the type annotations provided in the LLVM IR to "bootstrap" its
type
> inference (bootstrap is not quite the right word, but it's the closest
one
> of which I could think).  As LLVM matured, transformations would ditch the
> type information (e.g., transforming typed GEPs into untyped GEPs into a
> byte array), making DSA's ability to do type-inference (and thereby
> improving field sensitivity) more difficult.  Throw into the mix the fact
> that DSA is maintained by an academic research group, and the result is
> that modern DSA doesn't have the accuracy that the original DSA did.
>
> The good news is that I think DSA can be fixed by making its
> type-inferencing code smarter.  The bad news is that it'd be a fair
amount
> of work to do.  So far, no one has had sufficient desire/motivation to
> design and implement the improvements.
>
> Regards,
>
> John Criswell
>
>
>
> On 4/6/15 4:56 PM, Wan Zhiyuan wrote:
>
> Dear all,
> I am trying to reproduce the "Percent May Alias" result described
in PLDI
> 07's paper "Making Context-Sensitive Points-to Analysis with Heap
Cloning
> Practical For The Real World" (
> http://llvm.org/pubs/2007-06-10-PLDI-DSA.html).
>
>  However, my "Percent May Alias" for all the benchmarks is much
greater,
> especially "bzip2".
>
>  The DSA code I use is from "https://github.com/smackers/smack".
I have
> diff the code between smack and poolalloc_32. They are almost the same
> except the "#include" statements.
>
>  I was wondering whether I need to do some configuration to make DSA work
> properly.
>
>  Thank you!
>
>  Zhiyuan
>
>
>
>
>
> _______________________________________________
> LLVM Developers mailing listLLVMdev at cs.uiuc.edu        
http://llvm.cs.uiuc.eduhttp://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
>
>
> --
> John Criswell
> Assistant Professor
> Department of Computer Science, University of
Rochesterhttp://www.cs.rochester.edu/u/criswell
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150505/813b03f8/attachment.html>