search for: dscallgraph

Any suggestions for how to interpret DSCallGraph's output for the following? I'm trying to use DSCallGraph to get a conservative estimate of a whole-program SCC call graph. I wanted to see how it handles real call-graph cycles involving functions both internal and external to the module. So I made a test program with the following actu...

Andrew Lenharth wrote: > If I remember correctly, it only tries to resolve indirect calls. The > analysis doesn't track direct calls because you can do it just as well > yourself. DSCallGraph::callee_begin() and DSCallGraph::callee_end() cooperate to iterate over an empty set (EmptyActual) for any call site not found in the ActualCallees map. So if direct calls are not tracked, then I would expect the callee iterators for *both* direct calls to yield this empty set. Getting the empty...

...Tue, Aug 9, 2011 at 10:45 PM, Ben Liblit <liblit at cs.wisc.edu> wrote: > Andrew Lenharth wrote: >> If I remember correctly, it only tries to resolve indirect calls.  The >> analysis doesn't track direct calls because you can do it just as well >> yourself. > > DSCallGraph::callee_begin() and DSCallGraph::callee_end() cooperate to > iterate over an empty set (EmptyActual) for any call site not found in > the ActualCallees map.  So if direct calls are not tracked, then I would > expect the callee iterators for *both* direct calls to yield this empty > set....

...ource, compiled to bitcode using Clang: > >        void foo(); > >        void test() >        { >          foo(); >          foo(); >        } > > It should be rather obvious that each of the two call sites in test() must > have exactly one callee: foo().  However, DSCallGraph reports *zero* > possible callees at the first call site.  (It does correctly report foo() as > the one possible callee at the second call site.) > > Why is the analysis getting this wrong?  Of course I am trying to build up > to more complex, indirect calls.  But right now this very...

...more than a day older than the current trunk head. My test input is the following C source, compiled to bitcode using Clang: void foo(); void test() { foo(); foo(); } It should be rather obvious that each of the two call sites in test() must have exactly one callee: foo(). However, DSCallGraph reports *zero* possible callees at the first call site. (It does correctly report foo() as the one possible callee at the second call site.) Why is the analysis getting this wrong? Of course I am trying to build up to more complex, indirect calls. But right now this very simple case has me...

I wrote: > I'll keep poking at this some more and let you folks know if I hit any other surprises. Well, that didn't take long. :-) I have found two new surprises in DSCallGraph as built by TDDataStructures. Consider the following program, which is complete and self-contained and which has one simple indirect call site: volatile int unknown; static void red() { } static void blue() { } int main() { (unknown ? red : blue)(); return 0; } If I save this as...

In an earlier message (http://lists.cs.uiuc.edu/pipermail/llvmdev/2011-August/042298.html), Andrew Lenharth suggested that EQTDDataStructures (from the poolalloc project) may only try to resolve indirect function calls. However, I am now finding that the generated DSCallGraph over-approximates the callees in a very simple indirect call. Some over-approximation is unavoidable, but this case seems simple enough that any reasonable analysis ought to have been able to give the exact, correct answer. My example C++ source file, compiled to bitcode using clang from the...

Will Dietz wrote: > This is actually the expected behavior for EQTD :). Expected by you, maybe. :-D > If you switch to TD you'll get better alias-analysis information, and > in this example the correct result. OK, I have switched to TDDataStructures as well, and I am also seeing much better (for my purposes) results in simple tests. I'll keep poking at this some more and

...ote: > In an earlier message > (http://lists.cs.uiuc.edu/pipermail/llvmdev/2011-August/042298.html), > Andrew Lenharth suggested that EQTDDataStructures (from the poolalloc > project) may only try to resolve indirect function calls. However, I > am now finding that the generated DSCallGraph over-approximates the > callees in a very simple indirect call. Some over-approximation is > unavoidable, but this case seems simple enough that any reasonable > analysis ought to have been able to give the exact, correct answer. > > My example C++ source file, compiled to bitcod...

On Wed, Aug 10, 2011 at 10:37 AM, Ben Liblit <liblit at cs.wisc.edu> wrote: > Equally strange: if I comment out the "base->virt();" call, then DSCallGraph > *does* give the expected answer that "(unknown ? red : blue)()" could call > either red() or blue() but not Base::virt(). Somehow having that > vtable-based call present forces the other call to be unexpectedly > conservative in its over-approximation. It's hard to say...

...       static void red() { } >        static void blue() { } > >        int main() >        { >          (unknown ? red : blue)(); >          return 0; >        } > > If I save this as "test.c", compile it with clang, and run my ShowCallGraph > testing pass, DSCallGraph lists *zero* callees and claims that its results > for the indirect call site are incomplete. Reproduced. > If I save this same program as "test.cpp", compile it with clang, and run my > ShowCallGraph testing pass, DSCallGraph correctly lists both red() and > blue() as possi...

...rbana-Champaign http://llvm.org/~vadve On Aug 11, 2011, at 6:24 AM, <llvmdev-request at cs.uiuc.edu> wrote: > Date: Wed, 10 Aug 2011 23:44:14 -0500 > From: Will Dietz <willdtz at gmail.com> > Subject: Re: [LLVMdev] EQTDDataStructures omits obvious, direct callee > from DSCallGraph > To: Ben Liblit <liblit at cs.wisc.edu> > Cc: llvmdev at cs.uiuc.edu > Message-ID: > <CAKGWAO-Co6V0VFTHRyjpq9MQNPsv9Wo+36=vFTczhFgwB9Ks5g at mail.gmail.com> > Content-Type: text/plain; charset=ISO-8859-1 > > On Tue, Aug 9, 2011 at 10:45 PM, Ben Liblit <liblit...

...he results you report when using EQTD). Give that change a shot and let us know if you have any further questions/issues. FWIW at the moment DSA doesn't give good results for vtable-heavy code, marking all such callsites as incomplete and cannot resolve them. Offhand, I don't remember if DSCallGraph will correctly report a pessimistic callee set or if we expect you to look at the Incomplete flag yourself. Anyway, this is a fundamental limitation of DSA that probably won't be fixed anytime soon, just a heads-up. Hope this helps! :) ~Will

John Criswell wrote: > 1) I'll try out your example C++ code below and see if I can get the > same results that you do. However, I'm at a conference right now (Usenix > Security), so I don't know exactly when I'll get to it. Excellent. Thanks, John! > 2) DSA can get pessimistic results when dealing with external code (as > Andrew described). It is designed for

...c > > Directions on configuring it and examples of how to use it can be found > in the SAFECode project: http://safecode.cs.illinois.edu. > > If you want to use DSA, please let me know, and I can point you to an > example in SAFECode or the Poolalloc source code that uses the > DSCallGraph interface. > > -- John T. > Could you please point me the DSA example in poolalloc project? I just check that code out. Thanks a lot! linhai >> " >> >> thanks a lot! >> >> Linhai >>> > >

...oject/poolalloc/trunk poolalloc Directions on configuring it and examples of how to use it can be found in the SAFECode project: http://safecode.cs.illinois.edu. If you want to use DSA, please let me know, and I can point you to an example in SAFECode or the Poolalloc source code that uses the DSCallGraph interface. -- John T. > " > > thanks a lot! > > Linhai >>

> On 1/26/11 3:00 PM, songlh at cs.wisc.edu wrote: >>> On 1/26/11 2:40 PM, songlh at cs.wisc.edu wrote: >>>> thanks! >>>> >>>> After I check the ll file, I find this: >>>> >>>> %1 = load %struct.nsAString** %aBuf_addr, align 4, !dbg !2048 >>>> %2 = getelementptr inbounds %struct.nsAString* %1, i32 0, i32 0, !dbg

Hi, I'm trying to write a pass to detect all free()/delete() call instructions in LLVM IR.The method is as follows. First I find Call Instructions: CallInst *CI=dyn_cast<CallInst>(&*i); then see if the Function name matches: name=CI->getCalledFunction()->getName(); if(name=="_ZdlPv"||name=="_ZdaPv"||name=="free")

...ion.cpp for Release+Asserts build llvm[4]: Compiling Basic.cpp for Release+Asserts build llvm[4]: Compiling BottomUpClosure.cpp for Release+Asserts build llvm[4]: Compiling CallTargets.cpp for Release+Asserts build llvm[4]: Compiling CompleteBottomUp.cpp for Release+Asserts build llvm[4]: Compiling DSCallGraph.cpp for Release+Asserts build llvm[4]: Compiling DSGraph.cpp for Release+Asserts build llvm[4]: Compiling DSTest.cpp for Release+Asserts build llvm[4]: Compiling DataStructure.cpp for Release+Asserts build llvm[4]: Compiling DataStructureStats.cpp for Release+Asserts build llvm[4]: Compiling EntryP...