<div dir="ltr"><font color="#000000" style="background-color:rgb(255,255,255)">Hi!<br><br>In this mail, I'll briefly summarize what I already achieved during my GSoC and discuss what I plan to do moving forward. Feel free to skip ahead if you feel up to date!</font><div><b><font color="#000000" style="background-color:rgb(255,255,255)"><br></font></b></div><div><b><font color="#000000" style="background-color:rgb(255,255,255)">What happened so far?</font></b></div><div><b><font color="#000000" style="background-color:rgb(255,255,255)"><br></font></b></div><div><font color="#000000" style="background-color:rgb(255,255,255)">I proposed to enhance bug reports in the Static Analyzer [1]. I specifically targeted reports that were incomplete in a sense that the report didn't contain information to explain why we concluded that the bug report is a true positive. I've shared the following code snippet numerous times, as it captures several different problems the analyzer can't deal with yet:</font></div><div><font color="#000000" style="background-color:rgb(255,255,255)"><br></font></div><div><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap;background-color:rgb(255,255,255)"><font color="#000000">01 int flag;</font></span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap;background-color:rgb(255,255,255)"><font color="#000000">02 bool coin();</font></span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap;background-color:rgb(255,255,255)"><font color="#000000">03 </font></span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap;background-color:rgb(255,255,255)"><font color="#000000">04 void foo() {</font></span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font color="#000000" style="background-color:rgb(255,255,255)"><span style="font-family:"Courier New";font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">05   flag = coin();</span><span style="font-family:"Courier New";white-space:pre-wrap"> // no note, but there should be one</span></font></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap;background-color:rgb(255,255,255)"><font color="#000000">06 }</font></span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap;background-color:rgb(255,255,255)"><font color="#000000">07 </font></span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap;background-color:rgb(255,255,255)"><font color="#000000">08 int main() {</font></span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap;background-color:rgb(255,255,255)"><font color="#000000">09   int *x = 0; // x initialized to 0</font></span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap;background-color:rgb(255,255,255)"><font color="#000000">10   flag = 1;</font></span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font color="#000000" style="background-color:rgb(255,255,255)"><span style="font-family:"Courier New";font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">11   foo();</span><span style="font-family:"Courier New";white-space:pre-wrap"> // no note, but there should be one</span></font></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap;background-color:rgb(255,255,255)"><font color="#000000">12   if (flag) // assumed false</font></span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap;background-color:rgb(255,255,255)"><font color="#000000">13     x = new int;</font></span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap;background-color:rgb(255,255,255)"><font color="#000000">14   foo(); // no note, but there should be one</font></span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap;background-color:rgb(255,255,255)"><font color="#000000">15 </font></span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap;background-color:rgb(255,255,255)"><font color="#000000">16   if (flag) // assumed true</font></span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap;background-color:rgb(255,255,255)"><font color="#000000">17     *x = 5; // warn</font></span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap;background-color:rgb(255,255,255)"><font color="#000000">18 }</font></span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap;background-color:rgb(255,255,255)"><font color="#000000"><br></font></span></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap;background-color:rgb(255,255,255)"><font face="arial, sans-serif" color="#000000">In my first update mail [2] I explained that the assumption on line 12 is very important, because we wouldn't find a nullpointer dereference had flag been true. Similarly, the assumption of line 16 is important. You can see that following the notes in the bug path, despite setting flag to 1 on line 10, we assume it to to be zero, and to be non-zero again.</font></span></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap;background-color:rgb(255,255,255)"><font face="arial, sans-serif" color="#000000"><br></font></span></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap;background-color:rgb(255,255,255)"><font face="arial, sans-serif" color="#000000">The goal is to teach the analyzer that the flag's value on both line 16 and 12 is important, and not to prune the calls to foo, where we should note that flag's value has been reset. The standard way to achieve this is to <i>track</i> flag in these location (similarly to how x is already tracked). When a variable is tracked, the analyzer constructs notes that explain why believe that it's value is what believe it to be at the tracking location.</font></span></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap;background-color:rgb(255,255,255)"><font face="arial, sans-serif" color="#000000"><br></font></span></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap;background-color:rgb(255,255,255)"><font face="arial, sans-serif" color="#000000">This implies that analyzer can argue about data dependencies quite well (it can use the information it gathered during symbolic analysis by inspecting the <i>exploded graph </i>(all the information gathered during symbolic analysis), specifically the <i>bugpath</i> (the linear path from the <i>error node</i> [where the error was emitted] to the <i>root</i> [where analysis begun]).</font></span></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap;background-color:rgb(255,255,255)"><font face="arial, sans-serif" color="#000000"><br></font></span></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font color="#000000" face="arial, sans-serif"><span style="white-space:pre-wrap;background-color:rgb(255,255,255)">The technique I came up with to help on this was inspired by <i>static backward program slicing </i>[3]. Program slicing is essentially creating a subset of the program (<i>program slice</i>) relevant to a (statement, {set of variables}) pair (<i>slicing criterion</i>).</span></font></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font color="#000000" face="courier new, monospace"><span style="white-space:pre-wrap;background-color:rgb(255,255,255)"><br></span></font></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font color="#000000" face="courier new, monospace"><span style="white-space:pre-wrap;background-color:rgb(255,255,255)">void f() {</span></font></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font color="#000000" face="courier new, monospace"><span style="white-space:pre-wrap;background-color:rgb(255,255,255)">  int n;
  read(n);</span></font></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font color="#000000" face="courier new, monospace"><span style="white-space:pre-wrap;background-color:rgb(255,255,255)">  int sum = 0;
  int product = 1;
  for (int i = 0; i < n; ++i) {
    sum += i;</span></font></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font color="#000000" face="courier new, monospace"><span style="white-space:pre-wrap;background-color:rgb(255,255,255)">    product *= i;
  }
  write(sum);</span></font></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font color="#000000" face="courier new, monospace"><span style="white-space:pre-wrap;background-color:rgb(255,255,255)">  write(product);</span></font></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font color="#000000" face="courier new, monospace"><span style="white-space:pre-wrap;background-color:rgb(255,255,255)">}</span></font></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font color="#000000" face="courier new, monospace"><span style="white-space:pre-wrap;background-color:rgb(255,255,255)"><br></span></font></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font color="#000000"><span style="white-space:pre-wrap;background-color:rgb(255,255,255)"><font face="arial, sans-serif">For the slicing criterion </font><font face="courier new, monospace">(write(product), {product})</font><font face="arial, sans-serif"> the following program slice would be created:</font></span></font></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font color="#000000" face="courier new, monospace"><span style="white-space:pre-wrap;background-color:rgb(255,255,255)"><br class="m_5226235364419470481gmail-Apple-interchange-newline">void f() {</span></font></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font color="#000000" face="courier new, monospace"><span style="white-space:pre-wrap;background-color:rgb(255,255,255)">  int n;
  read(n);</span></font></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font color="#000000" face="courier new, monospace"><span style="white-space:pre-wrap;background-color:rgb(255,255,255)">
  int product = 1;
  for (int i = 0; i < n; ++i) {</span></font></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font color="#000000" face="courier new, monospace"><span style="white-space:pre-wrap;background-color:rgb(255,255,255)"><br></span></font></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font color="#000000" face="courier new, monospace"><span style="white-space:pre-wrap;background-color:rgb(255,255,255)">    product *= i;
  }</span></font></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font color="#000000" face="courier new, monospace"><span style="white-space:pre-wrap;background-color:rgb(255,255,255)"><br></span></font></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font color="#000000" face="courier new, monospace"><span style="white-space:pre-wrap;background-color:rgb(255,255,255)">  write(product);</span></font></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font color="#000000" face="courier new, monospace"><span style="white-space:pre-wrap;background-color:rgb(255,255,255)">}</span></font></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font color="#000000" face="courier new, monospace"><span style="white-space:pre-wrap;background-color:rgb(255,255,255)"><br></span></font></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font color="#000000" face="arial, sans-serif"><span style="white-space:pre-wrap;background-color:rgb(255,255,255)">Program slicing, roughly speaking, works by collecting a set of relevant variables and a set of relevant statements by tracing data and control dependencies [3].</span></font></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font color="#000000" face="arial, sans-serif"><span style="white-space:pre-wrap;background-color:rgb(255,255,255)"><br></span></font></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font color="#000000" face="arial, sans-serif"><span style="white-space:pre-wrap;background-color:rgb(255,255,255)">Since the analyzer is also in need of this functionality (realizing which parts of the program is relevant to the bug's occurrence), and since data dependencies are already understood, I modified LLVM's <i>Iterated Dominance Frontier</i> calculator to be used with clang's CFG, which can be used to calculate control dependencies, assisting bug report generation.</span></font></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font color="#000000" face="arial, sans-serif"><span style="white-space:pre-wrap;background-color:rgb(255,255,255)"><br></span></font></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font color="#000000" face="arial, sans-serif"><span style="white-space:pre-wrap;background-color:rgb(255,255,255)">So far, I used this to realize that the condition on line 16 is important, and start tracking it. The patch that implemented it works by tracking the conditions of control dependency blocks of already tracked variables: since x is tracked on line 17, and the block on line 16 is a control dependency of it, we track the condition expression of that block (flag).</span></font></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font color="#000000" face="arial, sans-serif"><span style="white-space:pre-wrap;background-color:rgb(255,255,255)"><br></span></font></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font color="#000000" face="arial, sans-serif"><span style="white-space:pre-wrap;background-color:rgb(255,255,255)">It was quickly discovered that it's a bad approach to use the same tracking for both error-causing variables and conditions, as it lead to a bunch of uninteresting notes being inserted to bug reports -- we mainly want the bug reports to be untouched, and only expand it with information previously not present that made it potentially impossible to understand how the bug report came about (like flag's value changing). Ideas for this shared in a mail [4], where the consensus was to basically prune every note that didn't happen in a nested stackframe (the stackframe where flag's value changed (foo()) is nested in the frame where we started tracking it (main())).</span></font></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font color="#000000" face="arial, sans-serif"><span style="white-space:pre-wrap;background-color:rgb(255,255,255)"><br></span></font></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font color="#000000" face="arial, sans-serif"><span style="white-space:pre-wrap;background-color:rgb(255,255,255)">I gathered data on several large, open source C++ projects, and I feel confident that there are only so many loose ends left to be tied: don't track asserts conditions, calls to operator bool, and make the extra notes state clearly that we're talking about "just a condition", rather then a bug causing variable.</span></font></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font color="#000000" face="arial, sans-serif"><span style="white-space:pre-wrap;background-color:rgb(255,255,255)"><br></span></font></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font color="#000000" face="arial, sans-serif"><span style="white-space:pre-wrap;background-color:rgb(255,255,255)">In my first mail [2] I also detailed that realizing that line 16 is important is a vastly different case then the one on line 12: the bugpath doesn't contain line 13 (since we assumed flag to be false on line 12), so using BugReporterVisitors wouldn't be sufficient: we called there cases <i>must-have-happened</i>, where the information we need to realize that a control dependency is important is contained in the bugpath, and <i>should-not-have-happened</i> when it isn't.</span></font></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font color="#000000" face="arial, sans-serif"><span style="white-space:pre-wrap;background-color:rgb(255,255,255)"><br></span></font></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font color="#000000" face="arial, sans-serif"><span style="white-space:pre-wrap;background-color:rgb(255,255,255)">In followup mail to that thread [5] explained that the should-not-have-happened case can be further divided into <i>inlined category</i> (initially referred to as category 1), where the information we need isn't in the bugpath, but is in function that the analyzer visited, allowing us to resolve parameters and have access to a variety of tools, and the <i>not inlined category</i> (initially referred to as category 2) where the infromation lays in a non-inlined function.</span></font></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font color="#000000" face="arial, sans-serif"><span style="white-space:pre-wrap;background-color:rgb(255,255,255)"><br></span></font></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font color="#000000" face="arial, sans-serif"><span style="white-space:pre-wrap;background-color:rgb(255,255,255)">Inlined category (bar is inlined, but we don't explore line 10):</span></font></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap;background-color:rgb(255,255,255)"><font color="#000000"><br class="m_5226235364419470481gmail-Apple-interchange-newline">01 int flag;</font></span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap;background-color:rgb(255,255,255)"><font color="#000000">02 bool coin();</font></span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap;background-color:rgb(255,255,255)"><font color="#000000">03 </font></span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap;background-color:rgb(255,255,255)"><font color="#000000">04 void foo() {</font></span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font color="#000000" style="background-color:rgb(255,255,255)"><span style="font-family:"Courier New";font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">05   flag = coin();</span><span style="font-family:"Courier New";white-space:pre-wrap"> // no note, but there should be one</span></font></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap;background-color:rgb(255,255,255)"><font color="#000000">06 }</font></span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap;background-color:rgb(255,255,255)"><font color="#000000">07</font></span></p><p style="font-family:Arial,Helvetica,sans-serif;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-decoration-style:initial;text-decoration-color:initial;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap;background-color:rgb(255,255,255)"><font color="#000000">08 void bar(int &i) {</font></span></p><p dir="ltr" style="font-family:Arial,Helvetica,sans-serif;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-decoration-style:initial;text-decoration-color:initial;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap;background-color:rgb(255,255,255)"><font color="#000000">09   if (flag) // assumed false</font></span></p><p dir="ltr" style="font-family:Arial,Helvetica,sans-serif;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-decoration-style:initial;text-decoration-color:initial;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap;background-color:rgb(255,255,255)"><font color="#000000">10     i = new int;</font></span></p><p style="font-family:Arial,Helvetica,sans-serif;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-decoration-style:initial;text-decoration-color:initial;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap;background-color:rgb(255,255,255)"><font color="#000000">11 }</font></span></p><p dir="ltr" style="font-family:Arial,Helvetica,sans-serif;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-decoration-style:initial;text-decoration-color:initial;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap;background-color:rgb(255,255,255)"><font color="#000000">12 </font></span></p><p dir="ltr" style="font-family:Arial,Helvetica,sans-serif;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-decoration-style:initial;text-decoration-color:initial;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap;background-color:rgb(255,255,255)"><font color="#000000">13 int main() {</font></span></p><p dir="ltr" style="font-family:Arial,Helvetica,sans-serif;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-decoration-style:initial;text-decoration-color:initial;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap;background-color:rgb(255,255,255)"><font color="#000000">14   int *x = 0; // x initialized to 0</font></span></p><p dir="ltr" style="font-family:Arial,Helvetica,sans-serif;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-decoration-style:initial;text-decoration-color:initial;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap;background-color:rgb(255,255,255)"><font color="#000000">15   flag = 1;</font></span></p><p dir="ltr" style="font-family:Arial,Helvetica,sans-serif;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-decoration-style:initial;text-decoration-color:initial;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font color="#000000" style="background-color:rgb(255,255,255)"><span style="font-family:"Courier New";font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">16   foo();</span><span style="font-family:"Courier New";white-space:pre-wrap"> // no note, but there should be one</span></font></p><p style="font-family:Arial,Helvetica,sans-serif;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-decoration-style:initial;text-decoration-color:initial;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap;background-color:rgb(255,255,255)"><font color="#000000">17   bar(x);</font></span></p><p dir="ltr" style="font-family:Arial,Helvetica,sans-serif;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-decoration-style:initial;text-decoration-color:initial;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap;background-color:rgb(255,255,255)"><font color="#000000">18   foo(); // no note, but there should be one</font></span></p><p dir="ltr" style="font-family:Arial,Helvetica,sans-serif;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-decoration-style:initial;text-decoration-color:initial;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap;background-color:rgb(255,255,255)"><font color="#000000">19 </font></span></p><p dir="ltr" style="font-family:Arial,Helvetica,sans-serif;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-decoration-style:initial;text-decoration-color:initial;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap;background-color:rgb(255,255,255)"><font color="#000000">20   if (flag) // assumed true</font></span></p><p dir="ltr" style="font-family:Arial,Helvetica,sans-serif;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-decoration-style:initial;text-decoration-color:initial;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap;background-color:rgb(255,255,255)"><font color="#000000">21     *x = 5; // warn</font></span></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font color="#000000"><span class="m_5226235364419470481gmail-im" style="background-color:rgb(255,255,255)"></span></font></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap;background-color:rgb(255,255,255)"><font color="#000000">22 }</font></span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap;background-color:rgb(255,255,255)"><font color="#000000"><br></font></span></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font color="#000000" face="arial, sans-serif"><span style="white-space:pre-wrap;background-color:rgb(255,255,255)">Not inlined category (bar isn't inlined at all):</span></font></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap;background-color:rgb(255,255,255)"><font color="#000000"><br class="m_5226235364419470481gmail-m_432785897350353662gmail-Apple-interchange-newline">01 int flag;</font></span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap;background-color:rgb(255,255,255)"><font color="#000000">02 bool coin();</font></span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap;background-color:rgb(255,255,255)"><font color="#000000">03 </font></span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap;background-color:rgb(255,255,255)"><font color="#000000">04 void foo() {</font></span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font color="#000000" style="background-color:rgb(255,255,255)"><span style="font-family:"Courier New";font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">05   flag = coin();</span><span style="font-family:"Courier New";white-space:pre-wrap"> // no note, but there should be one</span></font></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap;background-color:rgb(255,255,255)"><font color="#000000">06 }</font></span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap;background-color:rgb(255,255,255)"><font color="#000000">07</font></span></p><p style="font-family:Arial,Helvetica,sans-serif;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-decoration-style:initial;text-decoration-color:initial;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap;background-color:rgb(255,255,255)"><font color="#000000">08 void bar(int &i) {</font></span></p><p dir="ltr" style="font-family:Arial,Helvetica,sans-serif;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-decoration-style:initial;text-decoration-color:initial;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap;background-color:rgb(255,255,255)"><font color="#000000">09   i = new int;</font></span></p><p style="font-family:Arial,Helvetica,sans-serif;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-decoration-style:initial;text-decoration-color:initial;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap;background-color:rgb(255,255,255)"><font color="#000000">10 }</font></span></p><p dir="ltr" style="font-family:Arial,Helvetica,sans-serif;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-decoration-style:initial;text-decoration-color:initial;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap;background-color:rgb(255,255,255)"><font color="#000000">11 </font></span></p><p dir="ltr" style="font-family:Arial,Helvetica,sans-serif;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-decoration-style:initial;text-decoration-color:initial;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap;background-color:rgb(255,255,255)"><font color="#000000">12 int main() {</font></span></p><p dir="ltr" style="font-family:Arial,Helvetica,sans-serif;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-decoration-style:initial;text-decoration-color:initial;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap;background-color:rgb(255,255,255)"><font color="#000000">13   int *x = 0; // x initialized to 0</font></span></p><p dir="ltr" style="font-family:Arial,Helvetica,sans-serif;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-decoration-style:initial;text-decoration-color:initial;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap;background-color:rgb(255,255,255)"><font color="#000000">14   flag = 1;</font></span></p><p dir="ltr" style="font-family:Arial,Helvetica,sans-serif;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-decoration-style:initial;text-decoration-color:initial;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font color="#000000" style="background-color:rgb(255,255,255)"><span style="font-family:"Courier New";font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">15   foo();</span><span style="font-family:"Courier New";white-space:pre-wrap"> // no note, but there should be one</span></font></p><p style="font-family:Arial,Helvetica,sans-serif;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-decoration-style:initial;text-decoration-color:initial;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font color="#000000" face="Courier New"><span style="white-space:pre-wrap;background-color:rgb(255,255,255)">16   if (flag) // assumed false</span></font></p><p style="font-family:Arial,Helvetica,sans-serif;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-decoration-style:initial;text-decoration-color:initial;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap;background-color:rgb(255,255,255)"><font color="#000000">17     bar(x);</font></span></p><p dir="ltr" style="font-family:Arial,Helvetica,sans-serif;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-decoration-style:initial;text-decoration-color:initial;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap;background-color:rgb(255,255,255)"><font color="#000000">18   foo(); // no note, but there should be one</font></span></p><p dir="ltr" style="font-family:Arial,Helvetica,sans-serif;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-decoration-style:initial;text-decoration-color:initial;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap;background-color:rgb(255,255,255)"><font color="#000000">19 </font></span></p><p dir="ltr" style="font-family:Arial,Helvetica,sans-serif;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-decoration-style:initial;text-decoration-color:initial;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap;background-color:rgb(255,255,255)"><font color="#000000">20   if (flag) // assumed true</font></span></p><p dir="ltr" style="font-family:Arial,Helvetica,sans-serif;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-decoration-style:initial;text-decoration-color:initial;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap;background-color:rgb(255,255,255)"><font color="#000000">21     *x = 5; // warn</font></span></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font color="#000000"><span class="m_5226235364419470481gmail-im" style="background-color:rgb(255,255,255)"></span></font></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap;background-color:rgb(255,255,255)"><font color="#000000">22 }</font></span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap;background-color:rgb(255,255,255)"><font face="arial, sans-serif" color="#000000"><br></font></span></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font color="#000000" style="background-color:rgb(255,255,255)">The not inlined category seems to be far more difficult, like, not even solvable probably with the amount of time I have left, so I only plan to aim for the inlined category cases within the should-not-have-happened problem. I shared a sketch algorithm in a followup mail [6], but I it was brought to my attention that using a reaching definition algorithm might be a superior approach.</font></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font color="#000000"><b style="background-color:rgb(255,255,255)"><br></b></font></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font color="#000000" style="background-color:rgb(255,255,255)">There were a variety of other things I did under the name of the project, but they aren't as exciting to be put in a summary ;)</font></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font color="#000000"><b style="background-color:rgb(255,255,255)"><br></b></font></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font color="#000000"><b style="background-color:rgb(255,255,255)">Using reaching definitions analysis to solve the should-not-have-happened inline category cases</b></font></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font color="#000000" style="background-color:rgb(255,255,255)"><br></font></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font color="#000000" style="background-color:rgb(255,255,255)">I am no expert on this topic, please feel free to correct me if I write something dumb.</font></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font color="#000000" style="background-color:rgb(255,255,255)"><br></font></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font color="#000000"><font style="background-color:rgb(255,255,255)">The reaching definitions analysis was originally made for instruction, not C++ code: "a reaching definition for a given instruction is an earlier instruction whose target variable can reach (be assigned to) the given one without an intervening assignment." [7].</font></font></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font color="#000000"><font style="background-color:rgb(255,255,255)"><br></font></font></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font color="#000000" style="background-color:rgb(255,255,255)"><font><font>When we say <i>reaching definition</i><b><i>s</i> </b>we refer to the analysis: the </font></font><span style="font-family:"courier new",monospace">REACHin[S]</span><font><font> set for basic block <font face="courier new, monospace">S</font><font face="arial, sans-serif"> </font>is the set of definitions reaching <font face="courier new, monospace">S</font>, and <font face="courier new, monospace">REACHout[S]</font> </font>are all reaching definitions of its predecessors minus those reaching definitions whose variable is killed by <font face="courier new, monospace">S</font> (contains an intervening assignment) plus any new definitions generated within <font face="courier new, monospace">S</font>.</font></font></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font color="#000000" style="background-color:rgb(255,255,255)"><br></font></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font color="#000000" style="background-color:rgb(255,255,255)">Now, when we're talking about <i>variables,</i> the shortcomings of this algorithm when it comes to C++ are obvious: aliasing. I guess we can always just try to be conservative in one way or another: no longer look for reaching definitions after a call to a function where the variable was passed as a non-const reference, or a write to reference of the same type.</font></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><br class="gmail-Apple-interchange-newline"></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt">There are plenty of big unknown here -- I'm inexperienced with implementing such algorithms, and I fear some esoteric AST elements in Clang may need to be a source of a lot of headache.</p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font color="#000000" style="background-color:rgb(255,255,255)"><br></font></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font color="#000000" style="background-color:rgb(255,255,255)">Here's an idea to how we could use reaching definitions analysis to discover important statements (like the one on line 13 in the first example of this mail), and track it's control dependencies:</font></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font color="#000000" style="background-color:rgb(255,255,255)"><br></font></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";color:rgb(34,34,34);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">// Traverses the bugpath to discover all reaching definitions, even</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";color:rgb(34,34,34);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">// in nested stackframes. Returns true if any reaching definition is</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";color:rgb(34,34,34);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">// found.</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";color:rgb(34,34,34);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">function conditionTracker(N : ExplodedNode, X : variable,</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";color:rgb(34,34,34);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">                          Report : BugReport, OriginB : OriginB)</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";color:rgb(34,34,34);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">  </span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";color:rgb(34,34,34);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">  SetOfReachingDefinitions = reaching definitions to X at N</span></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><b style="font-weight:normal" id="gmail-docs-internal-guid-b6281e9b-7fff-a2f4-d0d5-bb27ff92ba05"><br></b></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";color:rgb(34,34,34);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">  while N is not null do</span></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><b style="font-weight:normal"><br></b></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";color:rgb(34,34,34);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">    // Look for the function call to F</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";color:rgb(34,34,34);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">    N := N->getFirstPred()</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";color:rgb(34,34,34);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">    if not N->getLocationAs<CallExit>() then</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";color:rgb(34,34,34);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">      continue</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";color:rgb(34,34,34);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">    fi</span></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><b style="font-weight:normal"><br></b></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";color:rgb(34,34,34);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">    B := CFGBlock associated with N</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";color:rgb(34,34,34);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">    if there is no path from B to OriginB then</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";color:rgb(34,34,34);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">      continue</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";color:rgb(34,34,34);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">    fi</span></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><b style="font-weight:normal"><br></b></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";color:rgb(34,34,34);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">    CallEnterN := N’s matching CallEnter</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";color:rgb(34,34,34);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">    if CallEnterN is null then</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";color:rgb(34,34,34);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">      continue // and assert that we’re in a top frame</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";color:rgb(34,34,34);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">    fi</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";color:rgb(34,34,34);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">    </span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";color:rgb(34,34,34);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">    // CallEnterN’s pred should be in the same CFG as OriginB.</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";color:rgb(34,34,34);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">    CalleeE := CFGElement associated with CallEnterN->getFirstPred()</span></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><b style="font-weight:normal"><br></b></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";color:rgb(34,34,34);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">    ParamSet := set of F’s parameters at CallEnterN to which</span><span style="background-color:transparent;font-family:"Courier New";white-space:pre-wrap"> X</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="background-color:transparent;font-family:"Courier New";white-space:pre-wrap">                is passed to as a non-const reference</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";color:rgb(34,34,34);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">         </span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";color:rgb(34,34,34);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">    for all NewX variables in ParamSet do</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";color:rgb(34,34,34);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">      if conditionTracker(N, NewX, Report, F’s exit block) then</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";color:rgb(34,34,34);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">        SetOfReachingDefinitions += CalleeE</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";color:rgb(34,34,34);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">      fi</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";color:rgb(34,34,34);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">    od</span></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><b style="font-weight:normal"><br></b></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";color:rgb(34,34,34);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">    // X is global/static, or a field and F is a method, etc...</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";color:rgb(34,34,34);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">    if F would have access to X regardless then</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";color:rgb(34,34,34);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">      if conditionTracker(N, X, Report, F’s exit block) then</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";color:rgb(34,34,34);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">        SetOfReachingDefinitions += CalleeE</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";color:rgb(34,34,34);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">      fi</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";color:rgb(34,34,34);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">    fi</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";color:rgb(34,34,34);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">  od</span></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><b style="font-weight:normal"><br></b></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";color:rgb(34,34,34);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">  for all RD CFGElementRefs in SetOfReachingDefinitions do</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";color:rgb(34,34,34);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">    track control dependencies of RD</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";color:rgb(34,34,34);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">  od</span></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><b style="font-weight:normal"><br></b></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:"Courier New";color:rgb(34,34,34);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">  return not whether SetOfReachingDefinitions is empty</span></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font color="#000000" style="background-color:rgb(255,255,255)"><br></font></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font color="#000000" style="background-color:rgb(255,255,255)"><b>Should we just traverse the ExplodedGraph?</b></font></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font color="#000000" style="background-color:rgb(255,255,255)"><b><br></b></font></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font color="#000000" style="background-color:rgb(255,255,255)">In a mail sent by Artem [8], another possible application of the reaching definition algorithm was discussed. However, during our meeting, it was mentioned that maybe for that specific use case, traversing the ExplodedGraph might be a better approach. Should I approach the should-not-have-happened case with this technique as well, maybe it could be reused.</font></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font color="#000000" style="background-color:rgb(255,255,255)"><br></font></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font color="#000000" style="background-color:rgb(255,255,255)">I don't fancy this. First off, generalizing in the future to also cover the not inlined category is I think more difficult with this approach. Second, algorithms like reaching definitions are set in stone, and coming up with a reliable, correct way to handle the ExplodedGraph may be too difficult and time consuming for me at this point.</font></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><br></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt">Any feedback is appreciated!</p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt">Cheers,</p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font color="#000000" style="background-color:rgb(255,255,255)">Kristóf</font></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font color="#000000" style="background-color:rgb(255,255,255)"><br></font></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font color="#000000" style="background-color:rgb(255,255,255)"><span style="font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap"><font face="arial, sans-serif">[1] </font></span><a href="https://docs.google.com/document/d/1ci1BCAKojPlqIxIw1J_K2dnATA3z01PuwR_vHJS55TI/edit" target="_blank">https://docs.google.com/document/d/1ci1BCAKojPlqIxIw1J_K2dnATA3z01PuwR_vHJS55TI/edit</a></font></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font face="arial, sans-serif" color="#000000" style="background-color:rgb(255,255,255)"><span style="font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">[2] </span><a href="http://lists.llvm.org/pipermail/cfe-dev/2019-June/062535.html" target="_blank">http://lists.llvm.org/pipermail/cfe-dev/2019-June/062535.html</a></font></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font color="#000000" style="background-color:rgb(255,255,255)"><span style="font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap"><font face="arial, sans-serif">[3]</font></span><span style="font-variant-numeric:normal;font-variant-east-asian:normal;font-family:Arial;vertical-align:baseline;white-space:pre-wrap"> </span><a href="http://lists.llvm.org/pipermail/cfe-dev/2019-June/062613.html" target="_blank">http://lists.llvm.org/pipermail/cfe-dev/2019-June/062613.html</a><span style="font-family:arial,sans-serif;white-space:pre-wrap"> </span></font></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font face="arial, sans-serif" color="#000000" style="background-color:rgb(255,255,255)"><span style="font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">[4] </span><span style="font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">Tip, Frank. </span><span style="font-variant-numeric:normal;font-variant-east-asian:normal;font-style:italic;vertical-align:baseline;white-space:pre-wrap">A survey of program slicing techniques</span><span style="font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">. Centrum voor Wiskunde en Informatica, 1994.</span></font></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font color="#000000" style="background-color:rgb(255,255,255)"><span style="font-variant-numeric:normal;font-variant-east-asian:normal;font-family:Arial;vertical-align:baseline;white-space:pre-wrap">[5] </span><span style="font-family:arial,sans-serif;white-space:pre-wrap"><a href="http://lists.llvm.org/pipermail/cfe-dev/2019-June/062540.html" target="_blank">http://lists.llvm.org/pipermail/cfe-dev/2019-June/062540.html</a></span></font></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font color="#000000" style="background-color:rgb(255,255,255)"><font><span style="font-family:arial,sans-serif;white-space:pre-wrap">[6] </span></font><a href="http://lists.llvm.org/pipermail/cfe-dev/2019-June/062566.html" target="_blank">http://lists.llvm.org/pipermail/cfe-dev/2019-June/062566.html</a></font></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font color="#000000" style="background-color:rgb(255,255,255)"><font>[7] </font><a href="https://en.wikipedia.org/wiki/Reaching_definition" target="_blank">https://en.wikipedia.org/wiki/Reaching_definition</a></font></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt">[8] <a href="http://lists.llvm.org/pipermail/cfe-dev/2019-June/062727.html">http://lists.llvm.org/pipermail/cfe-dev/2019-June/062727.html</a></p></div></div>