Hey Ted (and any other analyzer hackers out there)<div><br><div class="gmail_quote">On Sat, Sep 10, 2011 at 1:14 AM, Chandler Carruth <span dir="ltr"><<a href="mailto:chandlerc@google.com">chandlerc@google.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;"><div>Everything we need is here, but there is an unfortunate structure: the block (B3) with the no-return destructor is nat an immediate predecessor of the exit block. As a result, we never look within B3 for no-return destructors, and fail to recognize that B1 and B0 are dead, and that there is no possibility of reaching the exit block without returning.</div>
<div><br></div><div>There is a comment in AnalysisBasedWarnings which indicates that the correct solution may be to actually prevent B1 (or any other block) from being added as a successor of B3, and explicitly add the exit block as a successor so we don't end up with an orphaned exit block. Is this the right approach to take? Can you provide any tips for how to implement this? I looked into it for a while, and it didn't seem straightforward. I can find all of the places where we add implicit destructors to the CFG, and when one of them is added that in attributed no-return, clear the successors of the current block and add the exit block as a successor. However, it looks like in some cases we process implicit destructors before actually adding successor(s) to a block. In that case, clearing won't help. What do you think is the cleanest place to put this in the CFGBuilder, and what is the cleanest strategy? Maybe we should track on the CFGBlock itself whether it is a 'no-return' block, and when adding successors check that bit and refuse to add any. Or we could catch when lazily creating a new block, and if the previous one contains any no-return elements clear its successors?</div>
</blockquote></div><br></div><div>So I dived into this with fresh eyes and I think I figured the various bits of it out. Now I understand better both what was going wrong, and what the FIXME about severing edges is *really* talking about.</div>
<div><br></div><div>The fundamental problem I'm hitting is that we special case the formation of CFGBlocks when a no-return construct is encountered. When such a block is hit, we ignore any successor-sequence already built and instead create a block with a direct and immediate successor of the exit block. This allows the analysis to quickly find the no-return CFGBlocks (and elements), and also ensures that the CFGBlocks that *would* have succeeded a no-return construct are correctly modeled as unreachable blocks.</div>
<div><br></div><div>In order to handle this situation when working with implicit destructors, we have to from a new block whenever we encounter one of these destructors, and correctly setup its successors. I've attached a patch which I think mostly does this. It adds a FIXME to the only part of the CFG builder where we don't do this, because that part injects destructors into the *beginning* of a block. I need to think a bit more about how the block datastructures work before I'll feel comfortable fixing that, as it'll be a different form of split from the others. This code path only comes up when patching up gotos, so I'm not particularly concerned if the no-return modeling there is imperfect. =]</div>
<div><br></div><div>With this patch I get the following CFG for the code snippet I posted originally:</div><div><div> [ B4 (ENTRY) ]</div><div> Predecessors (0):</div><div> Successors (1): B2</div><div><br></div><div>
[ B1 ]</div><div> 1: [B2.2].~other() (Implicit destructor)</div><div> Predecessors (0):</div><div> Successors (1): B0</div><div><br></div><div> [ B2 ]</div><div> 1: </div><div> 2: other o;</div><div>
3: i</div><div> 4: [B2.3]</div><div> T: switch [B2.4]</div><div> Predecessors (1): B4</div><div> Successors (1): B3</div><div><br></div><div> [ B3 ]</div><div> default:</div><div> 1: my_abort_struct()</div>
<div> 2: [B3.1] (BindTemporary)</div><div> 3: ~my_abort_struct() (Temporary object destructor)</div><div> Predecessors (1): B2</div><div> Successors (1): B0</div><div><br></div><div> [ B0 (EXIT) ]</div><div>
Predecessors (2): B1 B3</div><div> Successors (0):</div></div><div><br></div><div>Here we correctly model that B1 cannot be reached, and B3 has the immediate edge to B0. If I change the code snippet to declare a variable of my_abort_struct type instead of create a temporary (thus exercising the other CFG-buiding path I changed in this patch) I get this CFG:</div>
<div><div> [ B4 (ENTRY) ]</div><div> Predecessors (0):</div><div> Successors (1): B2</div><div><br></div><div> [ B1 ]</div><div> 1: [B2.2].~other() (Implicit destructor)</div><div> Predecessors (0):</div><div>
Successors (1): B0</div><div><br></div><div> [ B2 ]</div><div> 1: </div><div> 2: other o;</div><div> 3: i</div><div> 4: [B2.3]</div><div> T: switch [B2.4]</div><div> Predecessors (1): B4</div>
<div> Successors (1): B3</div><div><br></div><div> [ B3 ]</div><div> default:</div><div> 1: </div><div> 2: my_abort_struct s;</div><div> 3: [B3.2].~my_abort_struct() (Implicit destructor)</div><div> Predecessors (1): B2</div>
<div> Successors (1): B0</div><div><br></div><div> [ B0 (EXIT) ]</div><div> Predecessors (2): B1 B3</div><div> Successors (0):</div></div><div><br></div><div>Same story, the CFG correctly models the no-return destructor. For a somewhat trickier case, with 3 variables, the middle forming a no-return destructor you can even see that this correctly marks which destructor is unreachable!</div>
<div>code:</div><div><div>int f7(int i) {</div><div> other o;</div><div> switch (i) {</div><div> default:</div><div> other o1;</div><div> my_abort_struct s;</div><div> other o2;</div><div> }</div><div>
}</div></div><div><br></div><div>CFG:</div><div><div> [ B5 (ENTRY) ]</div><div> Predecessors (0):</div><div> Successors (1): B2</div><div> </div><div> [ B1 ]</div><div> 1: [B2.2].~other() (Implicit destructor)</div>
<div> Predecessors (1): B3</div><div> Successors (1): B0</div><div> </div><div> [ B2 ]</div><div> 1:</div><div> 2: other o;</div><div> 3: i</div><div> 4: [B2.3]</div><div> T: switch [B2.4]</div>
<div> Predecessors (1): B5</div><div> Successors (1): B4</div><div> </div><div> [ B3 ]</div><div> 1: [B4.2].~other() (Implicit destructor)</div><div> Predecessors (0):</div><div> Successors (1): B1</div><div>
</div><div> [ B4 ]</div><div> default:</div><div> 1:</div><div> 2: other o1;</div><div> 3:</div><div> 4: my_abort_struct s;</div><div> 5:</div><div> 6: other o2;</div><div> 7: [B4.6].~other() (Implicit destructor)</div>
<div> 8: [B4.4].~my_abort_struct() (Implicit destructor)</div><div> Predecessors (1): B2</div><div> Successors (1): B0</div><div> </div><div> [ B0 (EXIT) ]</div><div> Predecessors (2): B1 B4</div><div> Successors (0):</div>
</div><div><br></div><div><br></div><div>I think this patch is a really useful improvement in accuracy, but it does add some non-trivial overhead to the process of adding implicit destructors into the CFG for automatic variables.. Does it seem acceptable? I don't see particularly cleaner ways of doing this... =/</div>
<div><br></div><div>If this patch is OK, or after any performance tuning you'd like to see here, I think I also better understand the FIXME in the analysis file. Do you actually want to switch the CFG to have *no* successors for blocks which contain a no-return element? That seems like it would be a very clean way of modelling this and would simplify the analysis for -Wreturn-type significantly. Let me know your thoughts here; I see a clean way to implement this after a couple of refactorings to consolidate the code I'm changing in this patch. (Currently, there is duplicate code. I left the refactoring and consolidation for a follow-up to make reviewing this one easier.)</div>
<div><br></div><div>Thanks!</div>