Hello,<br><br>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:<br>
<br>* 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.<br>
<br>* I brought back DSAA, because I need it :-)  Most importantly, I revised DSAA to make it is thread-safe.  This involved:<br>  (a) special-casing pthread_create (see changes in StdLibInfo.cpp and StdLibPass.cpp)<br>  (b) adding a thread-escape analysis<br>
  (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<br>
<br>* I brought back SteensgaardDataStructures, which was needed for the thread-escape analysis in DSAA.<br><br>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.)<br>
<br>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.<br>
<br>Thanks,<br>-Tom<br><br><div class="gmail_quote">On Thu, Aug 11, 2011 at 8:16 AM, John Criswell <span dir="ltr"><<a href="mailto:criswell@cs.uiuc.edu">criswell@cs.uiuc.edu</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">

  
    
  
  <div bgcolor="#FFFFFF" text="#000000"><div class="im">
    On 8/10/11 3:24 PM, Tom Bergan wrote:
    <blockquote type="cite">
      
      Hello,<br>
      <br>
      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).<br>
    </blockquote>
    <br></div>
    Questions about DSA can be sent to <a href="mailto:llvmdev@cs.illinois.edu" target="_blank">llvmdev@cs.illinois.edu</a>.<br>
    <br>
    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.<div class="im"><br>
    <br>
    <blockquote type="cite">
      <br>
      (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?<br>
    </blockquote>
    <br></div>
    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.<br>
    <br>
    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.<div class="im"><br>
    <br>
    <br>
    <blockquote type="cite">
      <br>
      (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?<br>
    </blockquote>
    <br></div>
    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.<div class="im"><br>
    <br>
    <blockquote type="cite"><br>
      (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.<br>
    </blockquote>
    <br></div>
    That would be great.  I just got DSA compiling with LLVM mainline
    last week, so there's issues to shake out yet.<br>
    <br>
    -- John T.<br>
    <br>
    <blockquote type="cite">
      <br>
      Thanks!<br>
      -Tom<br>
    </blockquote>
    <br>
  </div>

</blockquote></div><br>