[LLVMdev] llvm-poolalloc DSA patch: code cleanups and thread safety

[Tom Bergan]

Hello,

I have a patch to DSA you may be interested in.  I thought I'd post this to
llvmdev so it will be archived and googeable in case others need it, even if
you decide to not merge this into mainline :-)  Here are the highlights:

* I refactored StdLibDataStructures::processFunction into processFunction
and processCallSite to remove a lot of copy/pasted code.  I also moved the
libAction table from StdLibPass.cpp to a new module, StdLibInfo.cpp, so it
can be reused elsewhere.

* I brought back DSAA, because I need it :-)  Most importantly, I revised
DSAA to make it is thread-safe.  This involved:
  (a) special-casing pthread_create (see changes in StdLibInfo.cpp and
StdLibPass.cpp)
  (b) adding a thread-escape analysis
  (c) checking for memory barriers in getModRefInfo(CS, Loc): if
CS.getCalledFunction() is a memory barrier (such as pthread_mutex_lock) or
invokes one transitively, and if Loc is not a thread-local Location (i.e.,
if it may escape the thread), then getModRefInfo() must return ModRef

* I brought back SteensgaardDataStructures, which was needed for the
thread-escape analysis in DSAA.

Attached is a patch, llvm-poollalloc.diff, which was generated against the
latest svn revision, 137611.  The patch compiles and tests against LLVM
2.9.  (The project I need DSAA for requires LLVM 2.9.  I believe it will
compile against LLVM 3.0 if you remove all the s/Type/const Type/ lines in
the patch, but I haven't had a chance to verify this.)

Also attached are two diffs showing the changes to Steensgaard.cpp and
DataStuctureAA.cpp compared to the version of those files I resurrected from
svn.  Finally, I also attached a simple example program, break-dsa.c, which
compiles incorrectly with the old DSAA when optimized with -ds-aa -gvn.
This illustrates the need for thread-safety checks.

Thanks,
-Tom

On Thu, Aug 11, 2011 at 8:16 AM, John Criswell <criswell at cs.uiuc.edu> wrote:

>  On 8/10/11 3:24 PM, Tom Bergan wrote:
>
> Hello,
>
> Apologies for the direct mail, I wasn't sure if there was an appropriate
> mailing list.  I have a few questions about llvm-poolalloc's DSA
> implementation.  I'm using the latest svn revision (137169).
>
>
> Questions about DSA can be sent to llvmdev at cs.illinois.edu.
>
> As an FYI, I'm at Usenix Security this week, so I'm only getting small
> amounts of sporadic work done.  I'll be back in the office next week.
>
>
>
> (1) Do I misunderstand the meaning of "incomplete", as in
> node->isIncompleteNode()?  I've run EQTDDataStructures on the attached
> program (foo.c, foo.ll), generating the function graph for main which is
> attached (eqtd.main.pdf).  Shouldn't the %p node be marked Incomplete, since
> its address is passed to an unknown external function?
>
>
> In the original DSA implementation, you would be correct.  However, within
> the last few years, we enhanced DSA to have a new flag called External (the
> 'E' flag in the DSGraph).  A DSNode is marked external if a pointer to the
> memory object is passed to external code or comes from external code.
>
> The rationale behind the change is that the Incomplete flag used to mean
> two things: the DSNode was modified by external code, or the DSA analysis
> results were incomplete and more processing could yield more information
> about the DSNode (e.g., in the Bottom-Up DSA pass, DSA hasn't propagated
> information from callers to callees, so function arguments are marked
> incomplete).  The External flag allows us to distinguish between these two
> cases.
>
>
>
>
> (2) Is the AllocIdentify pass specific to poolalloc?  i.e., if I'm using
> DSA as a general purpose alias analysis, is the AllocIdentify pass useful?
>
>
> I think AllocIdentify is a general analysis pass that can be used by
> anybody.  That said, I don't know if DSA is using it or not.  I'd have to
> look at the code.
>
>
>
> (3) From the commit log, I see that you're moving to the the LLVM 3.0 API
> :-)  There are many uses of getOperand() which haven't been updated yet.
> For example, StdLibPass.cpp should use CallInst->getCalledValue() and
> CallInst->getArgument() instead of getOperand().  I have a patch to fix this
> in StdLibPass.cpp, which I can send soonish after I clean it up.
>
>
> That would be great.  I just got DSA compiling with LLVM mainline last
> week, so there's issues to shake out yet.
>
> -- John T.
>
>
> Thanks!
> -Tom
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20110816/cf5fd218/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: llvm-poolalloc.diff
Type: application/octet-stream
Size: 137206 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20110816/cf5fd218/attachment.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: DataStructureAA.cpp.diff
Type: application/octet-stream
Size: 30637 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20110816/cf5fd218/attachment-0001.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Steensgaard.cpp.diff
Type: application/octet-stream
Size: 14276 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20110816/cf5fd218/attachment-0002.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: break-dsa.c
Type: text/x-csrc
Size: 402 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20110816/cf5fd218/attachment.c>