This is an archive of the discontinued LLVM Phabricator instance.

Proposal on how to fix temporary dtors.
ClosedPublic

Authored by klimek on May 6 2014, 12:48 PM.

Details

Summary

Alex McCarthy and me have put our heads together and come up with something
that works. This still needs some cleanup, and has broken tests (in the compiler
based "consumed" and "reachable code" analysis, as mentioned in other threads).

We would like to get some feedback on the architecture, and whether the changes
the the CFG make sense or are expected to make problems in corner cases.

The gist of the change is a change to how the CFG is created:
For every temporary, add a new block that runs the dtor, and a decision
block that has the CXXBindTemporaryExpr as terminator. That way, we have one
entry and exit block for each temporary cleanup, and as long as they're chained
in the right order, it'll work.
This is of course suboptimal in multiple ways:

  • often we know when one destructor has executed that we must also execute the dtor of things that were generated previously; this makes the code and the CFG significantly more complex, though; the biggest downside seems to be that we potentially generate more states; not sure whether it's worth it
  • often we do not actually need a new block (for example, if the temporary is created unconditionally); in that case, we could just run with a single block; again this would make the code more complex though, and I'm not sure it's worth the effort, unless we feel it's an important invariant on the CFG

Diff Detail

Event Timeline

klimek updated this revision to Diff 9124.May 6 2014, 12:48 PM
klimek retitled this revision from to Proposal on how to fix temporary dtors..
klimek updated this object.
klimek edited the test plan for this revision. (Show Details)
klimek added reviewers: jordan_rose, krememek.
klimek added subscribers: alexmc, Unknown Object (MLST).
alexmc added a comment.May 6 2014, 2:06 PM

This is awesome, thanks Manuel! I can't wait to see this working :)

lib/Analysis/CFG.cpp
3675

Noob question: If we return FalseBlock below, do we need to visit CondBlock and TrueBlock even if they aren't returned? If we do need to visit them, is the order important? (Consider documenting this if this isn't super-obvious to someone with more clang experience than me :) )

lib/StaticAnalyzer/Core/ExprEngine.cpp
823

If includeTemporaryDtorsInCFG is not set, should we avoid this state modification?

1502

I think it's worth pulling this out into a new processTemporary helper method rather than adding it to processBranch: you're not reusing any of the logic in processBranch in the temporary dtor case.

This would involve adding a new HandleTemporary helper (or similar) that you'd call instead of HandleBranch, and that would call processTemporary

test/Analysis/temporaries.cpp
270

Don't we hit the NoReturnDtor when i == 0, which will prevent us from getting to i==2? This seems correct as-is.

333

Can you add a test that cleans up multiple temporaries in one condition? Maybe something like this (not sure if this compiles, we might need to add a check2(obj1, obj2) function):

class Dtor {
  ~Dtor() {}
};

void testMultipleTemporaries(bool value) {
  if (value) {
    // ~Dtor should run before ~NoReturnDtor() because construction order is guaranteed by comma operator
    if (!value || check((NoReturnDtor(), Dtor())) || value) {
      clang_analyzer_eval(true); // no warning, unreachable code
    }
  }
}

We could also make ~Dtor emit a warning which would only be triggered if Dtor was constructed with a certain value (e.g. check(Dtor(/*warning=*/true), NoReturnDtor()), then see if clang warns on that error that should never happen.

I also thought again about the problem of where to reset the bound state of the bind-temporary. The problem with the current solution is that it puts pretty strong requirements on how the CFG looks: we need to guarantee that for every constructed temporary, we will control-flow through the decision node that branches to the destructor call. At a first glance this may seem benign, but when I first thought about how to construct the CFG in that case, I believed the "optimum" to be one where we don't have any decision blocks when there is no control flow, and where we use the knowledge from where we are in a logical operator chain to unconditionally flow into the next destructor block.
For example:
A() || B() || C() || D()
When we are in the destructor block for D(), we *know* that we have to call the destructor of C(), thus we could unconditionally flow into C's destructor block without first flowing into its decision block (like the current code does).
I'm not sure it makes sense to do that (as it's more complex), but on the other hand I'm not sure it makes sense to preclude that with an implementation detail of how we track the temp ctor calls.

lib/Analysis/CFG.cpp
3675

Yes, the CFG blocks are hooked up even if they aren't returned. Actually, most of the hooking up goes via the Block and Succ members, and afaiu the returned value is mostly for convenience (and usually equals Block).
I'm not sure whether it makes sense to document that here, as it seems to be an invariant used throughout the CFG builder.

lib/StaticAnalyzer/Core/ExprEngine.cpp
823

That's a good question (for Jordan ;)

Another question is whether we still want to do the runCheckersForPre / runCheckersForPost enchilada.

1502

I agree. I mainly haven't done that, as somewhere in that chain there is an interface, and the method is abstract. I found only one use, so I assume somebody else implements that interface outside of the clang codebase. I'd like to hear what Jordan thinks on that issue, architecture-wise.

test/Analysis/temporaries.cpp
270

/me headdesks.

333

Added the test, and it works as expected. The problem is that I have no idea how to verify the construction order, as (according to comments I've seen in the code) the analyzer does not inline destructors (or at least temporary destructors).

jordan_rose edited edge metadata.May 7 2014, 9:55 AM

Wow, this actually came out very nicely. Good work, Manuel and Alex! I have a few comments on individual pieces, but overall I'm actually pretty confident in this. Have you run it over a large codebase yet?

often we know when one destructor has executed that we must also execute the dtor of things that were generated previously; this makes the code and the CFG significantly more complex, though; the biggest downside seems to be that we potentially generate more states; not sure whether it's worth it

often we do not actually need a new block (for example, if the temporary is created unconditionally); in that case, we could just run with a single block; again this would make the code more complex though, and I'm not sure it's worth the effort, unless we feel it's an important invariant on the CFG

We do still have this knowledge: it's whether the logical expression immediately dominating the last temporary processed is the same as the logical expression dominating the current temporary. That's not perfect (it doesn't handle the A() || B() || C() case), but it works in the simple cases, and handles unconditional creation as well. That said, if we do this we need to make sure the state is cleaned up correctly, as I mention below.

I'm not sure how changing either of these behaviors would generate more states. It seems like if you have different sets of destructors to run, the states are already necessarily different, and once you've reached the common set of destructors, you'd have the same opportunity to "cache out", i.e. match an existing node in the ExplodedGraph.

lib/StaticAnalyzer/Core/ExprEngine.cpp
54–56

This needs to include the current StackFrameContext as well (for recursive functions). You can get that from the current LocationContext.

823

We're trying to run pre/post-checks on all non-trivial statements, so yes, we should still do it. It's almost simple enough that we can hoist that out of the big switch, but I'm not sure that's correct for all statement kinds, and no one's looked into it.

(But now that we have C++11, I'm really inclined to hoist the thing into a closure, so that people don't have to write that "loop over the nodes generated by pre-checkers" loop themselves.)

As for the state modification, what I mainly care about is that we clean up the map. Since that doesn't happen when temporary destructors are off, yes, we should be checking here. (Note that this is also important if we stop generating conditions for every temporary destructor—we need to make sure that the state is clean by the end of the full-expression even if we skip some of the conditions.)

1502

These days the interface isn't serving us much real purpose. In theory CoreEngine is just traversing CFGs, and doesn't actually know very much about C ef al. It then hands the CFGElements off to its SubEngine, which actually processes them and tells the CoreEngine where to go next if there's a branch. ExprEngine is the particularly SubEngine that understands the AST / the language.

In practice there's a lot of linguistic knowledge coded into CoreEngine, just because there's a lot of linguistic knowledge in the CFG and in ProgramPoints these days. But either way, SubEngine is more of an interface than a real base class; I don't think Ted ever expected that we'd get subclassing more than one level deep. It's okay to split this up into helper methods.

test/Analysis/temporaries.cpp
333

We've turned that off until we can get it right, yes. We can turn that back on after this patch. I'm happy to make this a CFG-dump test for now.

klimek added a comment.May 9 2014, 4:29 AM

Just a short update:
I ran this over our internal codebase, and found a roughly 0.5% change in
warnings. All the ones I investigated were new warnings of the form:
SomeType x = ...;
CHECK(some.Other() || something.Else()); // this is the macro that
evaluates to a no-return destructor iff the condition is false
...
doSomethingWith(x);

And now we would get a warning that 'x' is never used after being
initialized (I assume because it now always thinks the noreturn dtor is
run). I'll have to investigate some more.

Cheers,
/Manuel

Giving this a shot at pulling it together, and got a couple more questions...

lib/StaticAnalyzer/Core/ExprEngine.cpp
54–56

Can you elaborate on how I would put that into a datastructure? Just use a std::pair? (doesn't seem to work with ImmutableSet though)

Also, I seem unable to write a test that breaks because of this - any hints would be highly welcome.

jordan_rose added inline comments.May 21 2014, 8:23 PM
lib/StaticAnalyzer/Core/ExprEngine.cpp
54–56

We'd have to write a specialization of ImutProfileInfo for std::pair, but that's probably not a bad idea anyway. Please feel free to add one to ImmutableSet.h.

I would guess the test case would look something like this:

static bool test(bool isInner) {
  if (isInner || NoReturnDtor() || test(true)) {
    *(volatile int *)0 = 1; // should warn
  }
}
void topLevel() {
  test(false);
}
klimek updated this revision to Diff 9765.May 23 2014, 9:46 AM
klimek edited edge metadata.

Worked in all the review comments.

The remaining failing test is blocked on:
http://reviews.llvm.org/D3638

Ok, I think I worked through the issues. Please take another look :D

lib/StaticAnalyzer/Core/ExprEngine.cpp
54–56

Sent patch for review & added test.

823

Done.

1502

Done.

Looking really good, thanks Manuel! I'll leave the final acceptance for Jordan or someone else with more clang cred than I.

It looks like this fixes all of the FIXMEs in temporaries.cpp. Does this (hopefully) close out all known bugs with temporary dtor handling?

If so, wooooo :D

lib/StaticAnalyzer/Core/ExprEngine.cpp
1458–1459

Maybe add a message to this assert, like "Temporary destructor branches should be handled by processBindTemporary" or similar?

1488

Consider adding an assert message

lib/StaticAnalyzer/Core/ExprEngineCXX.cpp
25 ↗(On Diff #9765)

Consider documenting that we need the stack frame to handle recursion

190 ↗(On Diff #9765)

is it worth adding a makeBindTemporaryContext(BTE, Pred) helper?

test/Analysis/temporaries.cpp
256

Can you add a ternary test that does generate expected warnings if the branching doesn't flow through a noreturn temporary dtor?

282

This looks identical to the namespaced struct defined on line 115: maybe extract that definition and remove this duplicate? (same with extern check)

290

Can we provide (inline) destructor bodies that do or don't warn to test this? (in a followup change)

klimek updated this revision to Diff 9771.May 23 2014, 11:58 AM

Apply review comments.

lib/StaticAnalyzer/Core/ExprEngine.cpp
1458–1459

Done.

1488

Done.

lib/StaticAnalyzer/Core/ExprEngineCXX.cpp
25 ↗(On Diff #9765)

Done.

190 ↗(On Diff #9765)

I don't think so.

test/Analysis/temporaries.cpp
256

Done. Aaaand it revealed a bug in the test. Nice catch!

282

Done.

290

Not yet, for that we need to switch on inlining of destructors.

This generally looks good to me but I'd like to take one more look when I'm a bit more awake.

lib/StaticAnalyzer/Core/ExprEngine.cpp
1488

No need for llvm:: qualification here.

test/Analysis/temporaries.cpp
285

clang_analyzer_checkReached is probably better here. Old habits.

292–295

Yeah, I can't think of a way to fix this without inlining destructors. But that's the next thing to turn on!

klimek updated this revision to Diff 9795.May 25 2014, 11:15 PM

Apply review comments.

The question where to put the FoldingSetTraits is still open (see http://reviews.llvm.org/D3895 and my reply on-list (I really need to sit down and implement better mail parsing for phab)).

lib/StaticAnalyzer/Core/ExprEngine.cpp
1488

Done.

test/Analysis/temporaries.cpp
285

Assuming you mean clang_analyzer_warnIfReached, done.

292–295

\o/

klimek added inline comments.May 26 2014, 6:36 AM
lib/Analysis/CFG.cpp
3678

I found a test case where conditional operators are still broken - working on a fix.

klimek added inline comments.May 26 2014, 8:18 AM
lib/Analysis/CFG.cpp
3628–3632

The actual problem was here:
Instead of unconditionally setting Succ to B, we have to do:
if (B) Succ = B;
(like below).

The problem is that this leads to new regressions (which are correct to regress :P).

Consider:
struct abort {

abort();
~abort() __attribute__((noreturn));

};

int f1(int x) {

switch (x)
default:
abort();

}

The problem is that with the new way the CFG is built for temp dtors, we'll get a "branch" at destruction time of the abort, that either doesn't return (good), or falls through to the normal path (oh noes).
Of course there is no path where the constructor wasn't executed, but a simple path based analysis doesn't know that (UnreachableCode.cpp).

The idea to fix that would be to only insert the decision blocks for temporary destructors if we are at a branching point, and otherwise just flow up like normal.

Other ideas / thoughts?

klimek updated this revision to Diff 9812.May 26 2014, 10:39 AM

Fixes regression found when running over large internal codebase.

klimek updated this revision to Diff 9813.May 26 2014, 11:04 AM

Comment and restructuring.

Ok, I think I've got a solution I'm somewhat happy with - this now implements one of the ideas I had in the very beginning - we only insert branches for temp dtors when they are needed, thus giving the simple analyses better information to rely on.

Please take another look...

klimek updated this revision to Diff 9814.May 26 2014, 11:12 AM

Remove dead variable in non-debug mode.

Maybe this is a bit paranoid, but I'm confused as to how we can only save one LastBindTemporary value instead of a stack. What's the purpose of that particular variable again? It seems to be used for more than just "if there are no temporaries, we don't need a cleanup block".

include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h
98–99

Now that I think about it, this name is wrong. It's really "HandleCleanupTemporaryBranch" or something. The CXXBindTemporaryExpr just tells you which temporary it is. (And similar for similarly-named functions.)

lib/Analysis/CFG.cpp
472–481

You might as well make this a proper doc comment.

lib/StaticAnalyzer/Core/ExprEngine.cpp
822–823

Calling this VisitCXXBindTemporaryExpr but then only having it actually be called when the flag is set seems like a bad idea if anyone ever needs to add behavior that should happen all the time. Either the check should be moved inside the method or it should be called something else.

test/Analysis/temporaries.cpp
349

This and the true ? ... below will get optimized out at CFG construction time. If that's correct, you should comment it; if you want to test path sensitivity, you should take a boolean input variable and then fully constrain it at the top of the function.

I'm also confused by the use of LastBindTemporary, and why we only need to save the last one. A clearer name might help make this more understandable.

klimek updated this revision to Diff 9863.May 28 2014, 2:02 AM

Apply review comments.

Regarding LastBindTemporary and stacks:
My initial thought was that if VisitForTemporaryDtors can hit nested full-statements, it'd be incorrect anyway, so I assumed it can't happen.

Now that I look into it, it seems like I might be able to create a case where that happens (using a lambda inside an expression which itself of course has new full statements). I'm not sure yet what the right fix is, or whether there is something I'm not aware of yet that catches that. I'll investigate some more.

Generally, the idea is that the "stack" state is kept in the VisitXXXForTemporaryDtors, specifically VisitForTemporaryDtorsBranch, which:

  1. Calls VisitForTemporaryDtors(E):

a) If that does not hit another VisitForTemporaryDtorsBranch, we'll just aggregate all temporary dtors below in a single block; the guard for that block now will be the topmost temporary dtor in that block, which is the last one we visited (due insert-at-top for blocks), thus LastBindTemporary.
b) If that does hit another VisitForTemporaryDtorsBranch, that one will have run through (a), and then have added all temporary dtors that need to run before the inner branch point, if any; if we found any after the inner branch (that should be executed before the inner branch), it will be in LastBindTemporary, and we'll add the branch; otherwise, we know that there was no temporary added since the inner branch, so we do not need to add another branch

I should probably add an implementation comment with that exact content for VisitForTemporaryDtorsBranch, unless you guys come up with a better idea on how to implement the behavior.

include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h
98–99

Done.

lib/Analysis/CFG.cpp
472–481

Done.

lib/StaticAnalyzer/Core/ExprEngine.cpp
822–823

Good point. Moved the if inside.

test/Analysis/temporaries.cpp
349

This was a regression test that broke with the last version of the patch... Funnily enough it only broke with the conditional operator case, not the if() case. I'll run the CFG for both and verify what they do / did in the patch, and update this with my findings...

klimek updated this revision to Diff 9869.May 28 2014, 5:27 AM

Add comments in the tests as to what we're trying to test.

Yeppers:
[]() { check(NoReturnDtor()); } != nullptr || check(Dtor());
is wrong (we think we always die, while nothing is being executed...)

Working on a fix...

klimek updated this revision to Diff 9876.May 28 2014, 6:03 AM

Do not recursively visit lambdas for temporaries. This fixes the CFG, but does
not yet fix what we can reach.

We should treat blocks the same as lambdas. How about GNU StmtExprs?

if (check(OtherDtor()) &&
    ({ int x = 1; NoReturnDtor(); x + 1})) { ... }

To be fair, I'm not even sure how those are supposed to behave.

I'm not sure how your last-bind trick really works. In this code:

First() && (Second() || Second()) && Third()

none of the temporaries can be aggregated, but I'm not sure how LastBoundTemporary accomplishes that, even given your explanation.

Can we start with the inefficient version that tests every temporary individually, and then consolidate afterwards?

test/Analysis/temporaries.cpp
362–364

If this is the right test, then the comment was all I really wanted. There is of course a difference between this and the if-statement — the destructor here is in the same full-expression as the condition.

klimek updated this revision to Diff 9886.May 28 2014, 12:38 PM

Another try at solving the temporary destructor CFG.

The passing of conditionality up and down the stack via references is weirding me out, but I think I've convinced myself it's correct. You still need a test case with a block expr, though.

I'll try to look this over one more time this afternoon or evening.

Still missing a blocks example. :-)

lib/StaticAnalyzer/Core/ExprEngine.cpp
821–822

Why is Pred being passed here? The PreVisit set has the same information.

lib/StaticAnalyzer/Core/ExprEngineCXX.cpp
521–527 ↗(On Diff #9886)

Right, this is not correct. We need to iterate over the nodes in the pre-visit set and update all of them to generate Dst.

test/Analysis/temporaries.cpp
291–294

I don't think we assume that lambda-exprs are always non-null. We should.

klimek updated this revision to Diff 10045.Jun 3 2014, 1:57 AM

Clean up lambdas; add test for statement expressions
Explode all nodes.

klimek added a comment.Jun 3 2014, 1:59 AM

We still have the question about what to do with the FoldingSetNode for pairs in the other patch open.

lib/StaticAnalyzer/Core/ExprEngine.cpp
821–822

Done.

lib/StaticAnalyzer/Core/ExprEngineCXX.cpp
521–527 ↗(On Diff #9886)

/me headdesks. Done. I'm still not sure I understand all the necessary pieces to generate new nodes (and have no idea how to write tests that trigger the corner cases), so I'd appreciate another careful look (or some test ideas).

test/Analysis/temporaries.cpp
291–294

It's much worse. We currently ignore lambdas. I updated the test / added a comment.

jordan_rose accepted this revision.Jun 11 2014, 10:06 AM
jordan_rose edited edge metadata.

Let's bring it home!

Thanks again for working on this. I'm excited to have it in trunk and hopefully soon to turn it on by default.

lib/StaticAnalyzer/Core/ExprEngineCXX.cpp
521–527 ↗(On Diff #9886)

I'm not sure about the tests offhand, either—most likely it's currently untestable because we have no pre-statement checkers looking for CXXBindTemporaryExprs. The general principle, though, is that anything that has an ExplodedNodeSet out parameter has the potential to generate new nodes.

test/Analysis/temporaries.cpp
283–288

I know this was my example, but I'm concerned that testRecursiveFrames will be evaluated as top-level as well, in which case the inner case is trivially reached. Let's make sure it is trying the !isInner case around with a little hack:

if (isInner ||
    (clang_analyzer_warnIfReached(), false) || // expected-warning{{REACHABLE}}
    check(NoReturnDtor()) ||
    testRecursiveFrames(true)) {
This revision is now accepted and ready to land.Jun 11 2014, 10:06 AM
klimek updated this revision to Diff 10342.Jun 11 2014, 9:59 PM
klimek edited edge metadata.

Update recursive frames test for temp dtor tracking.

Sometimes it helps to try to write a nice commit message to find the flaws in one's thinking.

Consider:

void testSequencingOfConditionalTempDtors(bool b) {
   b || (check(Dtor()), check(NoReturnDtor()));
   clang_analyzer_warnIfReached();  // expected-warning{{REACHABLE}}
 }

I assume this should pass. We need to put the decision point before the full sequence of unconditional we find. I got confused by the 'normal-order/bottom-up' build (/me headdesks appropriately to punish himself).
I'll continue working on it.

klimek updated this revision to Diff 10425.Jun 15 2014, 11:10 AM

Fix taking track of sequences of temporary destructors.

At first I misread that as

void testSequencingOfConditionalTempDtors(bool b) {
   (b || check(Dtor())), check(NoReturnDtor());
   clang_analyzer_warnIfReached();  // expected-warning{{REACHABLE}}
 }

which should NOT be reachable. That's probably also a good test case. The comma operator is a real pain.

klimek updated this revision to Diff 10431.Jun 15 2014, 2:50 PM

More tests...

At first I misread that as

void testSequencingOfConditionalTempDtors(bool b) {
   (b || check(Dtor())), check(NoReturnDtor());
   clang_analyzer_warnIfReached();  // expected-warning{{REACHABLE}}
 }

which should NOT be reachable. That's probably also a good test case. The comma operator is a real pain.

Funnily enough I had 10 minutes where I debugged why the CFG was looking incorrect, only to detect that in my small repro I had actually forgotten the parens for the comma operator.

Jordan: do you want some time for a pass on the changed algorithm, or does it still LG?

Cheers,
/Manuel

Can you describe the new algorithm in a comment somewhere? I really don't quite have the hang of it, and that makes me worried about maintaining it.

klimek updated this revision to Diff 10495.Jun 17 2014, 5:08 AM

Simplify implementation and document it.

I think the algorithm makes sense. I'm not sure it's different, though, than just passing up the first (or last) CXXBindTemporaryExpr visited for a given expression, which would look like this:

// For a logical expression...
VisitForTemporaryDtors(E->getLHS(), false, &LastBTE);
const CXXBindTemporaryExpr *InnerBTE = nullptr;
VisitForTemporaryDtors(E->getRHS(), false, &InnerBTE);
InsertTempDtorDecisionBlock(InnerBTE);

Are there any cases that wouldn't cover?

klimek updated this revision to Diff 10827.Jun 25 2014, 5:23 AM

Fix cleaning up of the temporary state.

Can you add an assertion at the end of a block that there are no outstanding temporary destructors in the current stack frame? That seems useful.

lib/Analysis/CFG.cpp
3583

Lost a newline here.

lib/StaticAnalyzer/Core/ExprEngine.cpp
681–686

I'm not sure you're supposed to reuse Dst with multiple builders. However, you know there's only one node in CleanDtorState, so you should be able to just skip the loop.

klimek closed this revision.Aug 6 2014, 5:55 AM

Thx! Landed as r214962.

lib/Analysis/CFG.cpp
3583

Done.

lib/StaticAnalyzer/Core/ExprEngine.cpp
681–686

Done.