<html><head><meta http-equiv="Content-Type" content="text/html charset=windows-1252"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;">Hi John,<div><br></div><div>The approach you describe certainly would work in many cases, but not all. What you describe is essentially a “summary based analysis” where the first pass gathers enough facts to summarize the effects of a function call that can then be used to improve analysis results in the second pass. I think what you’ve described is very practical for many kinds of problems, but I suspect it will not yield the best results in general.</div><div><br></div><div>A few things to consider:</div><div><br></div><div>(1) If we ignore recursive functions for a moment and consider DAG-like call graphs, called functions can be interdispersed through a codebase in different files. If the summary you need for the “second pass” does not depend on context, then one pass is sufficient to gather the information for the second pass. If the summaries are context-sensitive (i.e., they depend on how functions were called) then multiple passes may be needed to propagate the context/summary information accordingly. Traditionally global analysis tools address this problem by not really doing multiple builds, but instead recording enough information during the first pass on the side to do post-analysis of the call graph itself.</div><div><br></div><div>(2) Summaries can be very rich. It’s totally plausible (as you describe) to come up with some hand-tuned summaries for specific problems (e.g., NULL pointer analysis) that work well (although possibly loose some precision if context-sensitivity is needed), but general summary based analysis in the analyzer will likely need something a bit more automatic to contend with all the different kinds of checkers people write.</div><div><br></div><div>(3) Another goal of the analyzer is to integrate it naturally into development workflows. In a continuous integration system, a build is likely to run once. Some commercial analyzer tools try to capture enough of the build in a lightweight manner (so not to interfere with the speed of the build) and then do the analysis on the side. Relying on repeating a build to do global analysis might not be feasible in practice.</div><div><br></div><div>That said, I think many of your observations are spot on, and capture some of the flavor of what would need to be done in general.</div><div><br></div><div>Cheers,</div><div>Ted</div><div><br></div><div><div><div>On Mar 27, 2014, at 8:27 PM, Hammond, John <<a href="mailto:john.hammond@intel.com">john.hammond@intel.com</a>> wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite"><div lang="EN-US" link="blue" vlink="purple" style="font-family: Helvetica; font-size: 14px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><div class="WordSection1" style="page: WordSection1;"><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);">Howdy,<o:p></o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);"> </span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);">I had the same question. But in each specific case I found that I could:<o:p></o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);"> </span></div><div style="margin: 0in 0in 0.0001pt 0.5in; font-size: 12pt; font-family: 'Times New Roman', serif; text-indent: -0.25in;"><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);"><span>1.<span style="font-style: normal; font-variant: normal; font-weight: normal; font-size: 7pt; line-height: normal; font-family: 'Times New Roman';"> <span class="Apple-converted-space"> </span></span></span></span><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);">Divide the analysis in to a data gathering phase and an error reporting phase (so two global make passes).<o:p></o:p></span></div><div style="margin: 0in 0in 0.0001pt 0.5in; font-size: 12pt; font-family: 'Times New Roman', serif; text-indent: -0.25in;"><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);"><span>2.<span style="font-style: normal; font-variant: normal; font-weight: normal; font-size: 7pt; line-height: normal; font-family: 'Times New Roman';"> <span class="Apple-converted-space"> </span></span></span></span><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);">Write a single bi-modal AST visitor or path sensitive checker that emits a flat text file which abstracts the results of the first phase.<o:p></o:p></span></div><div style="margin: 0in 0in 0.0001pt 0.5in; font-size: 12pt; font-family: 'Times New Roman', serif; text-indent: -0.25in;"><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);"><span>3.<span style="font-style: normal; font-variant: normal; font-weight: normal; font-size: 7pt; line-height: normal; font-family: 'Times New Roman';"> <span class="Apple-converted-space"> </span></span></span></span><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);">Write some python or awk that munges the output of the first phase into a single file.<o:p></o:p></span></div><div style="margin: 0in 0in 0.0001pt 0.5in; font-size: 12pt; font-family: 'Times New Roman', serif; text-indent: -0.25in;"><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);"><span>4.<span style="font-style: normal; font-variant: normal; font-weight: normal; font-size: 7pt; line-height: normal; font-family: 'Times New Roman';"> <span class="Apple-converted-space"> </span></span></span></span><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);">Have the checker read that file in the second phase and emit appropriate diagnostics.<o:p></o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);"> </span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);">So for example, say we would like to analyze NULL pointer dereferences. In phase 1, for each TU, for function definition emit (in structured flat text)<o:p></o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; text-indent: 0.5in;"><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);">ReturnsNULL FUNCTION<o:p></o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);">or<o:p></o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);"> DependentReturn CALLER CALLEE<o:p></o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);"> </span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);">Where FUNCTION, CALLER, and CALLEE uniquely identify a function (I use PATH:LINE:COL:NAME of the canonical declaration and emit errors when functions may not be canonically declared).<o:p></o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);"> </span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);">Step 3 above does the graph theoretic reduction to determine which functions may return NULL and puts this in a single file.<o:p></o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);"> </span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);">Step 4 reruns make and passes that file as an argument or environmental variable to the checker/AST visitor.<o:p></o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);"> </span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);">Usually I modify ccc-analyzer by adding some environmental variables to decide which files to write in phase 1 and which to read in phase 2. Then I write a bash script that wraps make and sets everything up.<o:p></o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);"> </span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);">It probably sounds worse than it is. All of that said, native support for global analysis would be awesome.<o:p></o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);"><o:p></o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);">Best,<o:p></o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);"> </span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);">John<o:p></o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);"> </span></div><div style="border-style: none none none solid; border-left-color: blue; border-left-width: 1.5pt; padding: 0in 0in 0in 4pt;"><div><div style="border-style: solid none none; border-top-color: rgb(181, 196, 223); border-top-width: 1pt; padding: 3pt 0in 0in;"><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><b><span style="font-size: 10pt; font-family: Tahoma, sans-serif;">From:</span></b><span style="font-size: 10pt; font-family: Tahoma, sans-serif;"><span class="Apple-converted-space"> </span><a href="mailto:cfe-dev-bounces@cs.uiuc.edu">cfe-dev-bounces@cs.uiuc.edu</a> [<a href="mailto:cfe-dev-bounces@cs.uiuc.edu">mailto:cfe-dev-bounces@cs.uiuc.edu</a>]<span class="Apple-converted-space"> </span><b>On Behalf Of<span class="Apple-converted-space"> </span></b>Jordan Rose<br><b>Sent:</b><span class="Apple-converted-space"> </span>Thursday, March 27, 2014 5:20 PM<br><b>To:</b><span class="Apple-converted-space"> </span><a href="mailto:larry.1.yang@nokia.com">larry.1.yang@nokia.com</a><br><b>Cc:</b><span class="Apple-converted-space"> </span>cfe-dev@cs.uiuc.edu<br><b>Subject:</b><span class="Apple-converted-space"> </span>Re: [cfe-dev] abstract interpretation work across different source files<o:p></o:p></span></div></div></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><o:p> </o:p></div><div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;">Hi, Larry. This is something we've wanted to do for a long time, but it's not a project to undertake lightly. Currently, the static analyzer uses the same logic as the compiler to parse a source file (and its headers) into an AST, and then run that. When you start talking about multiple source files, what we have isn't immediately reusable—Clang's just not set up to handle multiple translation units that also interact, with the exception of some of the indexing work. So the challenge is to come up with some way to share information across translation units (or, less plausibly, to rewire Clang to handle multiple translation units in a common context).<o:p></o:p></div></div><div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><o:p> </o:p></div></div><div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;">In some of our discussions on this, we've come up with the ideas of either "marshalling" data from one ASTContext to another (which turned out to be quite difficult to get right), or of recording "summaries" of each function that describe how to evaluate it from another context. I think the summary-based approach is a better avenue to go down, but then you have to decide how to get these summaries in and out of the analyzer and what information to include in them. And they have to be better than the default behavior we have now for opaque function calls...but then this has the possibility to be really, really useful.<o:p></o:p></div></div><div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><o:p> </o:p></div></div><div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;">(Who is "we"? Mostly Ted Kremenek, the code owner for the analyzer, along with Anna Zaks and myself.)<o:p></o:p></div></div><div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><o:p> </o:p></div></div><div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;">I hope that shines a light on some of the difficulties in implementing this well—it's a project of weeks, if not months. If you're still interested in looking at this, let's come up with a plan to tackle some of these problems. Alternately, I'd be happy to see you contributing to the analyzer, but starting out with something possibly less daunting. :-)<o:p></o:p></div></div><div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><o:p> </o:p></div></div><div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;">Jordan<o:p></o:p></div></div><div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><o:p> </o:p></div></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><o:p> </o:p></div><div><div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;">On Mar 18, 2014, at 21:54 ,<span class="Apple-converted-space"> </span><a href="mailto:larry.1.yang@nokia.com" style="color: purple; text-decoration: underline;">larry.1.yang@nokia.com</a><span class="Apple-converted-space"> </span>wrote:<o:p></o:p></div></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><br><br><o:p></o:p></div><div><div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><span style="font-size: 11pt; font-family: Calibri, sans-serif;">Hello there,<o:p></o:p></span></div></div><div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><span style="font-size: 11pt; font-family: Calibri, sans-serif;"> <o:p></o:p></span></div></div><div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><span style="font-size: 11pt; font-family: Calibri, sans-serif;">I am looking at clang static analyzer recently, and thinking whether I could make it’s abstract interpretation work across different source files, so that the constraints from source file a.c could be applied to other source files like b.c and c.c.<o:p></o:p></span></div></div><div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><span style="font-size: 11pt; font-family: Calibri, sans-serif;"> <o:p></o:p></span></div></div><div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><span style="font-size: 11pt; font-family: Calibri, sans-serif;">Any directions/hints on this will be much appreciated.<o:p></o:p></span></div></div><div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><span style="font-size: 11pt; font-family: Calibri, sans-serif;"> <o:p></o:p></span></div></div><div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><span style="font-size: 11pt; font-family: Calibri, sans-serif;">Br,<o:p></o:p></span></div></div><div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><span style="font-size: 11pt; font-family: Calibri, sans-serif;">Larry<o:p></o:p></span></div></div><div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><span style="font-size: 11pt; font-family: Calibri, sans-serif;"> <o:p></o:p></span></div></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><span style="font-size: 9pt; font-family: Helvetica, sans-serif;">_______________________________________________<br>cfe-dev mailing list<br><a href="mailto:cfe-dev@cs.uiuc.edu" style="color: purple; text-decoration: underline;"><span style="color: purple;">cfe-dev@cs.uiuc.edu</span></a><br><a href="http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev" style="color: purple; text-decoration: underline;"><span style="color: purple;">http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev</span></a><o:p></o:p></span></div></div></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><o:p> </o:p></div></div></div>_______________________________________________<br>cfe-dev mailing list<br><a href="mailto:cfe-dev@cs.uiuc.edu">cfe-dev@cs.uiuc.edu</a><br>http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev</div></blockquote></div><br></div></body></html>