<html><head><meta http-equiv="Content-Type" content="text/html; charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class="">After additional investigation (summarized in the table below), we have decided to flip the switch.<div class="">Some additional notes on postgres: most additional reports come from the auto-generated bison file,</div><div class="">increase in memory comes from that same file (as we simply have a lot more reports for a single invocation).</div><div class="">Once <a href="https://reviews.llvm.org/D43421" class="">https://reviews.llvm.org/D43421</a> [analyzer] Do not analyze bison-generated files comes through, those should be suppressed.</div><div class=""><br class=""><div class="">Relevant differential revisions are:</div><div class=""><br class=""></div><div class=""> - <a href="https://reviews.llvm.org/D43354" class="">https://reviews.llvm.org/D43354</a> [analyzer] Exploration strategy prioritizing unexplored nodes first</div><div class=""> - <a href="https://reviews.llvm.org/D43782" class="">https://reviews.llvm.org/D43782</a> [analyzer] Switch the default exploration strategy to priority queue based on coverage</div><div class=""><br class=""><table class="" style="font-family: -webkit-standard; width: 1249px;"><colgroup class=""><col class="" style="width: 0px;"><col class="" style="width: 0px;"><col class="" style="width: 0px;"><col class="" style="width: 0px;"><col class="" style="width: 0px;"><col class="" style="width: 0px;"><col class="" style="width: 0px;"></colgroup><tbody class=""><tr class="odd"><td class=""><b class=""><br class=""><br class="">Project<br class=""><br class=""><br class=""></b></td><td class=""><b class="">Total User Time (s)</b></td><td class=""><b class="">Total Coverage (%)</b></td><td class=""><b class="">Max Resident Set Size (MB)</b></td><td class=""><b class="">Total Reports</b></td><td class=""><b class="">Max Path Length</b></td><td class=""><br class=""></td></tr><tr class="even"><td class="">sqlite3 (dfs)</td><td class="">439</td><td class="">62</td><td class="">196</td><td class="">34</td><td class="">79</td><td class=""></td></tr><tr class="odd"><td class="">sqlite3 (cqueue)</td><td class="">236 (-46%)</td><td class="">80 (+29%)</td><td class="">211 (-7%)</td><td class="">46 (+14 / -2) (+35%)</td><td class="">118 (+49%)</td><td class=""></td></tr><tr class="even"><td class="">XNU (dfs)</td><td class="">5237</td><td class="">71</td><td class="">2222</td><td class="">1942</td><td class="">833</td><td class=""></td></tr><tr class="odd"><td class="">XNU (cqueue)</td><td class="">5046 (-3%)</td><td class="">82 (+15%)</td><td class="">2224 (+0%)</td><td class="">2194 (+275 / -23) (+12%)</td><td class="">360 (-56%)</td><td class=""></td></tr><tr class="even"><td class="">openSSL (dfs)</td><td class="">810</td><td class="">81</td><td class="">187</td><td class="">184</td><td class="">465</td><td class=""><br class=""></td></tr><tr class="odd"><td class="">openSSL (cqueue)</td><td class="">862 (+6%)</td><td class="">86 (+6%)</td><td class="">144 (-22%)</td><td class="">193 (+9 / -0) (+4%)</td><td class="">170 (-63%)</td><td class=""></td></tr><tr class="even"><td class="">postgres (dfs)</td><td class="">3638</td><td class="">73</td><td class="">272</td><td class="">979</td><td class="">294</td><td class=""><br class=""></td></tr><tr class="odd"><td class="">postgres (cqueue)</td><td class="">3703 (+2%)</td><td class="">85 (+16%)</td><td class="">543 (+100%)</td><td class="">1352 (+390 / -17) (+38%)</td><td class="">199 (-32%)</td><td class=""><br class=""></td></tr><tr class="even"><td class="">adium (dfs)</td><td class="">2805</td><td class="">93</td><td class="">222</td><td class="">338</td><td class="">94</td><td class=""></td></tr><tr class="odd"><td class="">adium (cqueue)</td><td class="">3075 (+10%)</td><td class="">95 (+2%)</td><td class="">209 (-5%)</td><td class="">347 (+9 / -0) (+3%)</td><td class="">94 (-0%)</td><td class=""><br class=""></td></tr></tbody></table><div><br class=""><blockquote type="cite" class=""><div class="">On Feb 4, 2018, at 4:43 AM, Gábor Horváth <<a href="mailto:xazax.hun@gmail.com" class="">xazax.hun@gmail.com</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><br class="Apple-interchange-newline"><br style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none;" class=""><div class="gmail_quote" style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none;">On 1 February 2018 at 23:39, George Karpenkov<span class="Apple-converted-space"> </span><span dir="ltr" class=""><<a href="mailto:ekarpenkov@apple.com" target="_blank" class="">ekarpenkov@apple.com</a>></span><span class="Apple-converted-space"> </span>wrote:<br class=""><blockquote class="gmail_quote" style="margin: 0px 0px 0px 0.8ex; border-left-width: 1px; border-left-style: solid; border-left-color: rgb(204, 204, 204); padding-left: 1ex;"><div style="word-wrap: break-word; line-break: after-white-space;" class=""><br class=""><div class=""><span class=""><br class=""><blockquote type="cite" class=""><div class="">On Jan 31, 2018, at 10:15 PM, Anna Zaks <<a href="mailto:ganna@apple.com" target="_blank" class="">ganna@apple.com</a>> wrote:</div><div class=""><div style="word-wrap: break-word; line-break: after-white-space;" class=""><div class=""><div class="">A high jump in basic blocks coverage could be explained by your argument. (By the way, have you measured that?)</div></div></div></div></blockquote><div class=""><br class=""></div></span>On sqlite3, with trunk:<br class=""><div class=""><br class=""></div><div class="">===---------------------------<wbr class="">------------------------------<wbr class="">----------------===</div><div class=""> Miscellaneous Ungrouped Timers</div><div class="">===---------------------------<wbr class="">------------------------------<wbr class="">----------------===</div><div class=""><br class=""></div><div class=""> ---User Time--- --System Time-- --User+System-- ---Wall Time--- --- Name ---</div><div class=""> <span class="Apple-converted-space"> </span><font color="#ff2600" class="">379.8440</font><span class="Apple-converted-space"> </span>(100.0%) 6.6433 (100.0%) 386.4873 (100.0%) 391.7896 (100.0%) Analyzer Total Time</div><div class=""> <span class="Apple-converted-space"> </span>379.8440 (100.0%) 6.6433 (100.0%) 386.4873 (100.0%) 391.7896 (100.0%) Total</div><div class=""><br class=""></div><div class="">===---------------------------<wbr class="">------------------------------<wbr class="">----------------===</div><div class=""> <span class="Apple-converted-space"> </span>... Statistics Collected ...</div><div class="">===---------------------------<wbr class="">------------------------------<wbr class="">----------------===</div><div class=""><br class=""></div><div class=""> <span class="Apple-converted-space"> </span>1153 AnalysisConsumer - The maximum number of basic blocks in a function.</div><div class=""> 22876 AnalysisConsumer - The # of basic blocks in the analyzed functions.</div><div class=""> <span class="Apple-converted-space"> </span>1552 AnalysisConsumer - The # of functions at top level.</div><div class=""> 581 AnalysisConsumer - The # of functions and blocks analyzed (as top level with inlining turned on).</div><div class=""> <span class="Apple-converted-space"> </span><font color="#ff2600" class="">62 AnalysisConsumer - The % of reachable basic blocks</font>.</div><div class=""> <span class="Apple-converted-space"> </span><font color="#ff2600" class="">4091 BugReporter - The maximum number of bug reports in the same equivalence class</font></div><div class=""> 607 BugReporter - The maximum number of bug reports in the same equivalence class where at least one report is valid (not suppressed)</div><div class=""> <span class="Apple-converted-space"> </span>9411 CoreEngine - The # of paths explored by the analyzer.</div><div class=""> 210 CoreEngine - The # of times we reached the max number of steps.</div><div class="">52196353 CoreEngine - The # of steps executed.</div><div class=""> <span class="Apple-converted-space"> </span>752599 ExprEngine - The # of times we inlined a call</div><div class=""> 59461 ExprEngine - The # of aborted paths due to reaching the maximum block count in a top level function</div><div class=""> 64855 ExprEngine - The # of times we reached inline count maximum</div><div class="">12580704 ExprEngine - The # of times RemoveDeadBindings is called</div><div class=""> 310 ExprEngine - The # of times we re-evaluated a call without inlining</div><div class=""><br class=""></div><div class=""><b class="">With new approach: (resulting in 7 more reports)</b></div><div class=""><br class=""></div><div class=""><div class="">===---------------------------<wbr class="">------------------------------<wbr class="">----------------===</div><div class=""> Miscellaneous Ungrouped Timers</div><div class="">===---------------------------<wbr class="">------------------------------<wbr class="">----------------===</div><div class=""><br class=""></div><div class=""> ---User Time--- --System Time-- --User+System-- ---Wall Time--- --- Name ---</div><div class=""> <span class="Apple-converted-space"> </span><font color="#669c35" class="">265.6685</font><span class="Apple-converted-space"> </span>(100.0%) 4.5682 (100.0%) 270.2367 (100.0%) 423.9704 (100.0%) Analyzer Total Time</div><div class=""> <span class="Apple-converted-space"> </span>265.6685 (100.0%) 4.5682 (100.0%) 270.2367 (100.0%) 423.9704 (100.0%) Total</div><div class=""><br class=""></div><div class="">===---------------------------<wbr class="">------------------------------<wbr class="">----------------===</div><div class=""> <span class="Apple-converted-space"> </span>... Statistics Collected ...</div><div class="">===---------------------------<wbr class="">------------------------------<wbr class="">----------------===</div><div class=""><br class=""></div><div class=""> <span class="Apple-converted-space"> </span>1153 AnalysisConsumer - The maximum number of basic blocks in a function.</div><div class=""> 22876 AnalysisConsumer - The # of basic blocks in the analyzed functions.</div><div class=""> <span class="Apple-converted-space"> </span>1552 AnalysisConsumer - The # of functions at top level.</div><div class=""> 448 AnalysisConsumer - The # of functions and blocks analyzed (as top level with inlining turned on).</div><div class=""> <span class="Apple-converted-space"> </span><font color="#669c35" class="">77 AnalysisConsumer - The % of reachable basic blocks</font><b class="">.</b></div><div class=""> <font color="#4f7a28" class="">576 BugReporter - The maximum number of bug reports in the same equivalence class</font></div><div class=""> 576 BugReporter - The maximum number of bug reports in the same equivalence class where at least one report is valid (not suppressed)</div><div class=""> <span class="Apple-converted-space"> </span>7717 CoreEngine - The # of paths explored by the analyzer.</div><div class=""> 143 CoreEngine - The # of times we reached the max number of steps.</div><div class="">36012220 CoreEngine - The # of steps executed.</div><div class=""> <span class="Apple-converted-space"> </span>527875 ExprEngine - The # of times we inlined a call</div><div class=""> 33368 ExprEngine - The # of aborted paths due to reaching the maximum block count in a top level function</div><div class=""> 37822 ExprEngine - The # of times we reached inline count maximum</div><div class=""> 8551997 ExprEngine - The # of times RemoveDeadBindings is called</div><div class=""> 295 ExprEngine - The # of times we re-evaluated a call without inlining</div></div><div class=""><br class=""></div><div class="">We can also see a factor of 8 decrease in the maximum number of bug reports within the same equivalence class,</div><div class="">which further validates the hypothesis that the budget is no longer spent on going around the loop and finding the same bug over and over again.</div><div class="">Moreover, even the user time is significantly decreased (I would assume because we run out of budget faster as paths get longer).</div></div></div></blockquote><div class=""><br class=""></div><div class="">I think, it would be good to know what is the reason behind the significant decrease in the running time. Maybe discovering the shorter paths first (with less looping around) and we cache out on the longer paths later? Or in case the reason is that we run out one of the analysis budgets earlier, maybe it would be worth to consider altering the default budget limits.<br class=""></div><div class=""> </div><blockquote class="gmail_quote" style="margin: 0px 0px 0px 0.8ex; border-left-width: 1px; border-left-style: solid; border-left-color: rgb(204, 204, 204); padding-left: 1ex;"><div style="word-wrap: break-word; line-break: after-white-space;" class=""><div class=""><div class=""><div class="h5"><br class=""><blockquote type="cite" class=""><div class=""><div style="word-wrap: break-word; line-break: after-white-space;" class=""><div class=""><div class=""><br class=""></div>However, whenever I see that we start reporting hundreds of new bugs on a single codebase it looks suspicious. Will the developers really want and need to fix more than 3 hundred bugs on postgresql? Often when we dig deeper we find out that either we became too aggressive in reporting what people will view as false positives or we are reporting duplicate reports that have the same underlying cause. It’s possible postgresql is really that buggy, but we really need to be careful here. </div><div class=""><br class=""><blockquote type="cite" class=""><div class=""><div style="word-wrap: break-word; line-break: after-white-space;" class=""><div class=""><div class=""><br class=""><blockquote type="cite" class=""><div class="">On Jan 31, 2018, at 9:52 PM, Anna Zaks <<a href="mailto:ganna@apple.com" target="_blank" class="">ganna@apple.com</a>> wrote:</div><br class="m_-1316112105211519357Apple-interchange-newline"><div class=""><div style="word-wrap: break-word; line-break: after-white-space;" class=""><br class=""><div class=""><br class=""><blockquote type="cite" class=""><div class="">On Jan 31, 2018, at 9:41 PM, George Karpenkov <<a href="mailto:ekarpenkov@apple.com" target="_blank" class="">ekarpenkov@apple.com</a>> wrote:</div><br class="m_-1316112105211519357Apple-interchange-newline"><div class=""><br class="m_-1316112105211519357Apple-interchange-newline"><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><blockquote type="cite" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><div class="">On Jan 31, 2018, at 8:46 PM, Anna Zaks <<a href="mailto:ganna@apple.com" target="_blank" class="">ganna@apple.com</a>> wrote:</div><br class="m_-1316112105211519357Apple-interchange-newline"><div class=""><div style="word-wrap: break-word; line-break: after-white-space;" class=""><div class=""><br class=""><blockquote type="cite" class=""><div class="">On Jan 31, 2018, at 5:00 PM, George Karpenkov <<a href="mailto:ekarpenkov@apple.com" target="_blank" class="">ekarpenkov@apple.com</a>> wrote:</div><br class="m_-1316112105211519357Apple-interchange-newline"><div class=""><div style="word-wrap: break-word; line-break: after-white-space;" class="">The list did not like a posting with many images,<div class="">so I have posted an evaluation to phabricator:<span class="m_-1316112105211519357Apple-converted-space"> </span><a href="https://reviews.llvm.org/M1" target="_blank" class="">https://reviews.<wbr class="">llvm.org/M1</a></div><div class=""><br class=""></div><div class="">The text part was:</div><div class=""><br class=""></div><div class=""><p style="margin: 0px 0px 12px; padding: 0px; border: 0px; font-family: "Segoe UI", "Segoe UI Emoji", "Segoe UI Symbol", Lato, "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 13px;" class="">After fixing a few bugs, another evaluation of the approach shows considerably better results.</p><p style="margin: 0px 0px 12px; padding: 0px; border: 0px; font-family: "Segoe UI", "Segoe UI Emoji", "Segoe UI Symbol", Lato, "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 13px;" class="">On openssl:</p><ul class="m_-1316112105211519357remarkup-list" style="margin: 12px 0px 12px 30px; padding: 0px; border: 0px; list-style-position: initial; font-family: "Segoe UI", "Segoe UI Emoji", "Segoe UI Symbol", Lato, "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 13px;"><li class="m_-1316112105211519357remarkup-list-item" style="margin: 0px; padding: 0px; border: 0px; line-height: 1.7em;">9 reports added</li><li class="m_-1316112105211519357remarkup-list-item" style="margin: 0px; padding: 0px; border: 0px; line-height: 1.7em;">1 report removed</li></ul><p style="margin: 0px 0px 12px; padding: 0px; border: 0px; font-family: "Segoe UI", "Segoe UI Emoji", "Segoe UI Symbol", Lato, "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 13px;" class="">On postgresql:</p><ul class="m_-1316112105211519357remarkup-list" style="margin: 12px 0px 12px 30px; padding: 0px; border: 0px; list-style-position: initial; font-family: "Segoe UI", "Segoe UI Emoji", "Segoe UI Symbol", Lato, "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 13px;"><li class="m_-1316112105211519357remarkup-list-item" style="margin: 0px; padding: 0px; border: 0px; line-height: 1.7em;">377 reports added</li><li class="m_-1316112105211519357remarkup-list-item" style="margin: 0px; padding: 0px; border: 0px; line-height: 1.7em;">43 reports removed</li></ul><p style="margin: 0px 0px 12px; padding: 0px; border: 0px; font-family: "Segoe UI", "Segoe UI Emoji", "Segoe UI Symbol", Lato, "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 13px;" class="">On sqlite3 + a few other misc files:</p><ul class="m_-1316112105211519357remarkup-list" style="margin: 12px 0px 12px 30px; padding: 0px; border: 0px; list-style-position: initial; font-family: "Segoe UI", "Segoe UI Emoji", "Segoe UI Symbol", Lato, "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 13px;"><li class="m_-1316112105211519357remarkup-list-item" style="margin: 0px; padding: 0px; border: 0px; line-height: 1.7em;">239 reports added</li></ul></div></div></div></blockquote><div class="">This is a lot of additional reports! Are there actually that many bugs in that codebase that need to be fixed?</div></div></div></div></blockquote><div style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><br class=""></div><div style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class="">Out of 239 or in general? The 239 reports mostly come from non-sqlite files.</div></div></blockquote><div class=""><br class=""></div>Can you provide data just for sqlite?</div><div class=""><br class=""></div><div class="">For postgresql the number of additional reports also seems very high.</div><div class=""><br class=""><blockquote type="cite" class=""><div class=""><div style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class="">In general, for most practical purposes C codebases provide an infinite supply of bugs :P</div><div style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><br class=""></div><div style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class="">On a more serious note, I don’t think this is very surprising.</div><div style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class="">The previous emails in this chain have shown that for loops, the analyzer has a very high chance of entering</div><div style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class="">a degenerate behavior where the longest path through the loop will be evaluated first,</div><div style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class="">and a large chunk of the analyzer budget is then spent on going around the loop in circles.</div><div style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><br class=""></div><div style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class="">Under new exploration strategy, paths which increase coverage are explored first, and then we can actually find</div><div style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class="">bugs with the budget which is no longer spent going in circles.</div><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><blockquote type="cite" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><div class=""><div style="word-wrap: break-word; line-break: after-white-space;" class=""><div class=""><div class="">I think we need to manually evaluate these reports.</div></div></div></div></blockquote><div style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><br class=""></div><div style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class="">Yes, I’ve looked through quite a few of them, the false positive ratio seems to be actually getting lower,</div><div style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class="">as the probability of the report being a false positive grows with the path length,</div><div style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class="">and path lengths are getting much shorter.</div><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><blockquote type="cite" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><div class=""><div style="word-wrap: break-word; line-break: after-white-space;" class=""><div class="">Also, we have to make sure uniquing works. Do all regression tests pass?<br class=""></div></div></div></blockquote><div style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><br class=""></div><div style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class="">Yes.</div><blockquote type="cite" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><div class=""><div style="word-wrap: break-word; line-break: after-white-space;" class=""><div class=""><blockquote type="cite" class=""><div class=""><div style="word-wrap: break-word; line-break: after-white-space;" class=""><div class=""><ul class="m_-1316112105211519357remarkup-list" style="margin: 12px 0px 12px 30px; padding: 0px; border: 0px; list-style-position: initial; font-family: "Segoe UI", "Segoe UI Emoji", "Segoe UI Symbol", Lato, "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 13px;"><li class="m_-1316112105211519357remarkup-list-item" style="margin: 0px; padding: 0px; border: 0px; line-height: 1.7em;">1 report removed</li></ul><p style="margin: 0px 0px 12px; padding: 0px; border: 0px; font-family: "Segoe UI", "Segoe UI Emoji", "Segoe UI Symbol", Lato, "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 13px;" class="">Note on histograms (here and below)</p><div style="margin: 0px; padding: 0px; border: 0px; font-family: "Segoe UI", "Segoe UI Emoji", "Segoe UI Symbol", Lato, "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 13px;" class="">-> Histograms only show the ratio for same bugs (compared using issue hash),<br style="margin-top: 0px;" class="">that is, if the histogram says “decrease by a factor of three”, it means the new approach finds the *same* bug<br class="">with a path size 1/3d of the original<br class="">-> Histograms omit data points where the path length has remained the same<br class="">(as otherwise they completely dominate the histogram)<br class="">-> Relative histograms are provided as both ratio and logarithm of the ratio.<br class="">Logarithms of the ratio are convenient as they are symmetric in case changes balance out<br class="">(e.g. log(1/2) = -log(2/1))</div><div class=""><br class=""><blockquote type="cite" class=""><div class="">On Jan 30, 2018, at 4:23 PM, George Karpenkov <<a href="mailto:ekarpenkov@apple.com" target="_blank" class="">ekarpenkov@apple.com</a>> wrote:</div><br class="m_-1316112105211519357Apple-interchange-newline"><div class=""><div style="word-wrap: break-word; line-break: after-white-space;" class=""><div class="">Preliminary evaluation of a patch which prefers exploring nodes associated with statements which weren’t seen before first:</div><div class=""><br class=""></div>On openssl:<div class=""><br class=""></div><div class=""> - Adds four reports</div><div class=""> - Removes four reports </div><div class=""> - Path lengths before: 317, 75, 75, 72, 70, 58, 50, 50, 44, 36, 23, 23, 21, 21, 20, 20, 19, 19, 19, 19, 18, 18, 18, 16, 15, 15, 15, 14, 13, 13, 12, 11, 11, 9, 7, 7, 6, 4</div><div class=""> - Path lengths after: 72, 60, 59, 53, 53, 52, 46, 38, 37, 30, 29, 28, 23, 21, 20, 19, 19, 19, 19, 19, 18, 16, 15, 15, 15, 15, 13, 13, 12, 12, 11, 9, 8, 7, 7, 7, 6, 4</div><div class=""><br class=""></div><div class="">The quality of the added reports seems higher, mainly due to the fact that report length is shorter.</div><div class=""><br class=""></div><div class="">On postgresql:</div><div class=""><br class=""></div><div class=""> - Added 80 reports</div><div class=""> - Removed 154 reports</div><div class=""> -> Out of those, 72 are reports on the yacc/bison autogenerated files, so whatever the cause is, good thing they are gone</div><div class=""> - The overall number of reports is 1188</div><div class=""> - Path lengths are lower on overall, but not in such a dramatic way</div><div class=""> - For many reports, I am quite confused as to why they got removed</div><div class=""><br class=""></div><div class="">On sqlite:</div><div class=""><br class=""></div><div class=""> - 7 inserted, 7 removed</div><div class=""><br class=""></div><div class=""><div class=""><div class=""><blockquote type="cite" class=""><div class="">On Jan 30, 2018, at 1:10 PM, Artem Dergachev <<a href="mailto:noqnoqneo@gmail.com" target="_blank" class="">noqnoqneo@gmail.com</a>> wrote:</div><br class="m_-1316112105211519357Apple-interchange-newline"><div class=""><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; text-decoration: none;" class=""><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; text-decoration: none;" class=""><span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; text-decoration: none; float: none; display: inline !important;" class="">On 30/01/2018 12:40 PM, Gábor Horváth via cfe-dev wrote:</span><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; text-decoration: none;" class=""><blockquote type="cite" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; text-decoration: none;" class="">Hi George, Artem,<br class=""><br class="">I am glad that you are looking into this problem!<br class=""><br class="">On 30 January 2018 at 01:12, George Karpenkov via cfe-dev <<a href="mailto:cfe-dev@lists.llvm.org" target="_blank" class="">cfe-dev@lists.llvm.org</a><span class="m_-1316112105211519357Apple-converted-space"> </span><<a href="mailto:cfe-dev@lists.llvm.org" target="_blank" class="">mailt<wbr class="">o:cfe-dev@lists.llvm.org</a>>> wrote:<br class=""><br class=""> Hi All,<br class=""><br class=""> I was investigating recently bug reports with very long analyzer<br class=""> paths (more than a few hundred nodes).<br class=""> In many of such cases the path is long for no good reason: namely,<br class=""> the analyzer would go 3 times around the loop before<br class=""> going further.<br class=""> The issue is surprisingly common, and it was exacerbated with a<br class=""> recent bump of analyzer thresholds.<br class=""><br class=""> The problem is reproduced on the following file:<br class=""><br class=""> ```<br class=""> extern int coin();<br class=""><br class=""> int foo() {<br class=""> <span class="Apple-converted-space"> </span>int *x = 0;<br class=""> <span class="Apple-converted-space"> </span>while (coin()) {<br class=""> <span class="Apple-converted-space"> </span>if (coin())<br class=""> <span class="Apple-converted-space"> </span>return *x;<br class=""> <span class="Apple-converted-space"> </span>}<br class=""> <span class="Apple-converted-space"> </span>return 0;<br class=""> }<br class=""><br class=""> void bar() {<br class=""> <span class="Apple-converted-space"> </span>while(coin())<br class=""> <span class="Apple-converted-space"> </span>if (coin())<br class=""> <span class="Apple-converted-space"> </span>foo();<br class=""> }<br class=""> ```<br class=""><br class=""> While a shortest path to the error does not loop around, the<br class=""> current version of the analyzer<br class=""> will go around the loop three times before going further.<br class=""> (and we are quite fortunate that the unrolling limit for loops is<br class=""> three, otherwise it would keep going<br class=""> until the unrolling limit is reached).<br class=""><br class=""> Multiple issues were discovered during the investigation.<br class=""><br class=""> 1. Analyzer queue does not have a concept of priority, and<br class=""> performs a simple DFS by default.<br class=""> Thus if the successor of the if-branch under the loop in “bar"<br class=""> containing the desired destination is generated second,<br class=""> it will never be evaluated until the loop exploration limit is<br class=""> exhausted.<br class=""><br class=""> 2. The previous issue slows down the exploration, but is not<br class=""> enough to get a pathological behavior of ultra-long paths.<br class=""> The second problem is a combination of:<br class=""> a) Block counter is not a part of a node's identity, and node A<br class=""> with a small block counter can be merged into a node B with a<br class=""> large block counter,<br class=""> and the resulting node will have a block counter associated with B.<br class=""><br class=""><br class="">Sorry for the questions, just wanted to clarify some things. You mean ExplodedNodes? By merge, you mean the same thing as "caching-out"?<br class=""></blockquote><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; text-decoration: none;" class=""><span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; text-decoration: none; float: none; display: inline !important;" class="">Yeah, George notices that if we construct the same ExplodedNode on two different paths that have different block counts, we'd cache-out on the latter path, while the worklist element of the first path would still possess the original block count.</span><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; text-decoration: none;" class=""><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; text-decoration: none;" class=""><span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; text-decoration: none; float: none; display: inline !important;" class="">Which happens a lot when we're evaluating foo() conservatively in this example.</span><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; text-decoration: none;" class=""><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; text-decoration: none;" class=""><span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; text-decoration: none; float: none; display: inline !important;" class="">This isn't directly related to our problem though, as i noticed in<span class="m_-1316112105211519357Apple-converted-space"> </span></span><a href="http://lists.llvm.org/pipermail/cfe-dev/2018-January/056719.html" target="_blank" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class="">http://lists.llvm.org/<wbr class="">pipermail/cfe-dev/2018-<wbr class="">January/056719.html</a><span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; text-decoration: none; float: none; display: inline !important;" class=""><span class="m_-1316112105211519357Apple-converted-space"> </span>.</span><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; text-decoration: none;" class=""><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; text-decoration: none;" class=""><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; text-decoration: none;" class=""><blockquote type="cite" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; text-decoration: none;" class=""> b) The issue in (a) is triggered due to our heuristic to abandon<br class=""> the function’s exploration and switch to conservative evaluation<br class=""> if we are already *inside* the function and the block limit has<br class=""> been reached.<br class=""><br class=""> Issue (1) combined with (2-b) causes the problematic behavior: the<br class=""> issue is discovered on the longest path first,<br class=""> and by the time the shortest path gets to “bar”, the block limit<br class=""> is already reached, and the switch to conservative evaluation is<br class=""> performed.<br class=""><br class=""> Thus there are two mitigation strategies currently being evaluated:<br class=""><br class=""> i) Remove the heuristic in (2-b)<br class=""> ii) Use a priority queue to hold nodes which should be explored;<br class=""> prefer nodes which give new source code coverage over others<br class=""> (or alternatively prefer nodes with least depth of loop stack)<br class=""><br class=""> Me and Artem have evaluated the option (i) and the results were<br class=""> surprisingly good: some reports disappear, and slightly more<br class=""> reports reappear.<br class=""> The quality of the new reports seems to be slightly better, and I<br class=""> am still trying to figure out exact reasons.<br class=""> I suspect merges resulting from heuristic (2-b) cause us to lose<br class=""> some actually valid reports.<br class=""><br class=""><br class="">I also find the results surprising. If you have more information about the reasons please do not forget to follow up this thread. We are curious :)<br class=""><br class=""><br class=""> Option (ii) has not been evaluated fully yet, but current<br class=""> experiments show slightly more reports (5-10%), and a radical<br class=""> decline in report lengths<br class=""> (e.g. from 400+ to <100 for largest reports)<br class=""><br class=""> Are there any thoughts on the matter?<br class=""><br class=""> Personally I think we should do both (i) and (ii), even if they<br class=""> would shake up the results.<br class=""> - The original idea for heuristics (2-b) was to be able to produce<br class=""> a report even if we are out of budget, but since it actually<br class=""> results in less reports,<br class=""> I think the data does not validate the approach.<br class=""><br class=""> - Option (ii) is AFAIK how most similar engines work, and should<br class=""> get us much larger coverage (and shorter paths) for the same node<br class=""> budget,<br class=""> even at the cost of log(N) overhead of the priority queue.<br class=""> Moreover, not having the priority queue will bite us later if we<br class=""> ever decide to further<br class=""> increase the analyzer budget or to increase the unroll limit.<br class=""><br class=""><br class="">I wonder what will the performance implication be. But I also like the idea of having a priority queue. If we find that we get more and better report<br class="">but also have worse performance, we can also consider reducing the analysis budget slightly.<br class=""><br class="">Regards,<br class="">Gábor<br class=""><br class=""><br class=""> George<br class=""><br class=""><br class=""><br class=""> ___________________________<wbr class="">____________________<br class=""> cfe-dev mailing list<br class=""> <a href="mailto:cfe-dev@lists.llvm.org" target="_blank" class="">cfe-dev@lists.llvm.org</a><span class="m_-1316112105211519357Apple-converted-space"> </span><<a href="mailto:cfe-dev@lists.llvm.org" target="_blank" class="">mai<wbr class="">lto:cfe-dev@lists.llvm.org</a>><br class=""> <a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev" target="_blank" class="">http://lists.llvm.org/cgi-<wbr class="">bin/mailman/listinfo/cfe-dev</a><br class=""> <<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev" target="_blank" class="">http://lists.llvm.org/cgi-<wbr class="">bin/mailman/listinfo/cfe-dev</a>><br class=""><br class=""><br class=""><br class=""><br class="">______________________________<wbr class="">_________________<br class="">cfe-dev mailing list<br class=""><a href="mailto:cfe-dev@lists.llvm.org" target="_blank" class="">cfe-dev@lists.llvm.org</a><br class=""><a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev" target="_blank" class="">http://lists.llvm.org/cgi-bin/<wbr class="">mailman/listinfo/cfe-dev</a></blockquote></div></blockquote></div></div></div></div></div></blockquote></div></div></div></div></blockquote></div></div></div></blockquote></div></blockquote></div></div></div></blockquote></div></div></div></div></blockquote></div></div></div></blockquote></div></div></div></div></blockquote></div></div></blockquote></div><br class=""></div></div></body></html>