[cfe-dev] [PATCH] Clang Static Analyzer support for temporary destructors
Manuel Klimek
klimek at google.com
Mon Mar 24 10:15:11 PDT 2014
On Mon, Mar 24, 2014 at 6:09 PM, Jordan Rose <jordan_rose at apple.com> wrote:
>
> On Mar 24, 2014, at 9:29 , Alex McCarthy <alexmc at google.com> wrote:
>
> I tried to debug this a bit more last week, and I'm still stumped. Ted,
> Jordan or Anna, do you have time to take a deeper look at this? Anna, would
> you mind clarifying http://llvm.org/bugs/show_bug.cgi?id=18159 (details
> below)?
>
> Here are two test cases similar to the ones I added to
> temp-obj-dtors-cfg-output.cpp and temporaries.cpp:
>
> int testConsistencyNestedSimple2(bool value) {
> if (value) {
> if (!value || check(NoReturnDtor())) {
> return 1; // impossible
> }
> }
> return 0;
> }
>
> int testConsistencyNestedComplex2(bool value) {
> if (value) {
> if (!value || !value || check(NoReturnDtor())) {
> return 1; // impossible
> }
> }
> return 0;
> }
>
> Since NoReturnDtor is an object with a temporary that never returns, it's
> impossible for either function to return 1. Before this patch, I think both
> test cases would fail or crash with destructor analysis turned on. This
> patch makes the simple case pass, but the compex case fails. I don't
> understand why.
>
>
> Take a look at the CFG for testConsistencyNestedComplex2:
>
> int testConsistencyNestedComplex2(bool value)
> * [B10 (ENTRY)]*
> Succs (1): B9
>
> * [B1]*
> 1: 0
> 2: return [B1.1];
> Preds (2): B3 B9
> Succs (1): B0
>
> * [B2]*
> 1: 1
> 2: return [B2.1];
> Preds (1): B3
> Succs (1): B0
>
> * [B3]*
> T: if [B5.1]
> Preds (1): B5
> Succs (2): B2 B1
>
> * [B4]*
> 1: ~NoReturnDtor() (Temporary object destructor)
> Preds (1): B5
> Succs (1): B0
>
> * [B5]*
> 1: [B8.3] || [B7.3] || [B6.6]
> T: (Temp Dtor) [B8.3] || [B7.3] || ...
> Preds (3): B6 B7 B8
> Succs (2): B3 B4
>
> * [B6]*
> 1: check
> 2: [B6.1] (ImplicitCastExpr, FunctionToPointerDecay, _Bool (*)(struct
> NoReturnDtor &&))
> 3: NoReturnDtor() (CXXConstructExpr, struct NoReturnDtor)
> 4: [B6.3] (BindTemporary)
> 5: [B6.4]
> 6: [B6.2]([B6.5])
> Preds (1): B7
> Succs (1): B5
>
> * [B7]*
> 1: value
> 2: [B7.1] (ImplicitCastExpr, LValueToRValue, _Bool)
> 3: ![B7.2]
> T: [B8.3] || [B7.3] || ...
> Preds (1): B8
> Succs (2): B5 B6
>
> * [B8]*
> 1: value
> 2: [B8.1] (ImplicitCastExpr, LValueToRValue, _Bool)
> 3: ![B8.2]
> T: [B8.3] || ...
> Preds (1): B9
> Succs (2): B5 B7
>
> * [B9]*
> 1: value
> 2: [B9.1] (ImplicitCastExpr, LValueToRValue, _Bool)
> T: if [B9.2]
> Preds (1): B10
> Succs (2): B8 B1
>
> * [B0 (EXIT)]*
> Preds (3): B1 B2 B4
>
> Notice block B4, where the temporary destructor is run. It's called when
> we get to B5 and see that the second-to-last || condition was false.
>
> What gets us to B5? Every single part of the || chain, because it's the
> only way to get to the actual if in B3. But by the time we go there, we've
> lost the values of the source expressions, just like you said. IIRC,
> without temporary destructors this isn't important, because we can figure
> out which branch we came from based on the previous block edge. But now
> that's not going to work.
>
> What Pavel tried is making all the values in the || chain stay live, so
> that we could decide whether or not to branch based on that, instead of
> based on how we got there. But that created a different problem: if we go
> directly from the first || condition to the final one, *we don't have the
> second one yet.* Worse, if we're in a loop, the liveness analysis
> (sometimes?) gets totally confused, and considers the value of the second
> expression from the *last* time through the loop to still be live. Which
> then does the wrong thing.
>
> That's PR18159 <http://llvm.org/bugs/show_bug.cgi?id=18159>.
>
> (And that "sometimes" is killer. We had a terrible time trying to reduce
> the test case—various things would perturb it one way or another to make
> the problem appear or not.)
>
> A while ago Ted mentioned that we should just synthesize shadow bool
> variables of some kind to track whether or not something's been
> initialized. I'm starting to think more and more that that's the right
> idea. (It's basically what IRGen does.) We don't exactly have an
> implementation for it, though.
>
If I remember correctly that was also Chandler's favorite opinion from the
start (just do whatever IRGen does).
> Anyway, I think that's what's not working in your test cases. I'll look
> through the patch to see if there are more pieces we can commit in advance.
> (The extraction of getRegionForConstructedObject seems like good general
> cleanup anyway.)
>
> Jordan
>
>
>
> I've attached dumps of clang analyzer's exploded graph state while
> processing these functions with my patch with destructor analysis turned on
> and off. (the diagrams in the pdfs are very tiny, you'll need something
> with serious zoom like the mac Preview app to read them). I think the bug
> *might* be caused by constraints being dropped when we analyze new blocks:
> in the Simple cases, we maintain a constraint on value being [1, 255] until
> we've completely finished processing the if statement and we've executed
> its terminator. In the complex case, we forget the constraints on value
> when transitioning between blocks before we've finished the if statement. I
> *think* this is when we enter the new block created to contain the
> temporary. But I'm still not sure how to read this, or whether this is a
> red herring.
>
> If this is a problem where we're forgetting constraints on variables, this
> might be http://llvm.org/bugs/show_bug.cgi?id=18159 which Anna filed in
> December. The bug says that this problem can be reproduced by dumping live
> variables and looking at the output: I've run these test cases with debug.DumpLiveVars
> but I'm not sure what to look for. Anna, could you please add more detail
> to the bug, or potentially add some test cases that pass or fail if this
> bug is fixed or still present?
>
> Thanks for your help, all. Let me know if you want to do some physical or
> virtual in-person debugging. I'm moving pretty slowly due to unfamiliarity
> with the tools, codebase, and compilers in general, and I'm sure a half
> hour of your experienced eyes on the problem would go a long way :)
>
>
>
> -Alex
>
>
> On Sat, Mar 22, 2014 at 5:33 PM, Alexander Kornienko <alexfh at google.com>wrote:
>
>> I'm waiting impatiently for this patch to land ;)
>> Any progress here? Jordan, AFAIU the ball is on your side?
>>
>>
>>
>> On Thu, Mar 6, 2014 at 8:47 PM, Alex McCarthy <alexmc at google.com> wrote:
>>
>>> Thanks for taking a look, Jordan, I really appreciate the extra eyes.
>>> Please find an updated patch attached.
>>>
>>> I misread the test in temporaries.cpp, thanks. I've restored the test so
>>> it's testing the right thing: it still fails and I'm currently stumped.
>>> I've produced some simpler test cases that are much easier to analyze, but
>>> I still don't understand how this incorrect behavior is triggered. I've
>>> also added more CFG dumps to temp-obj-dtors-cfg-output.cpp.test to see if
>>> anything stands out. I've also added a lot of debug output which clearly
>>> has to be removed before submission. I'd really appreciate any more advice
>>> you have here, and I'll keep (slowly) debugging in the mean time.
>>>
>>> The array processing while loop I added to ExprEngineCxx.cpp's
>>> ::VisitCXXDestructor was an attempt to fix the crash that I found when
>>> processing initializer_lists of temporary objects. I added a new test to
>>> dtor-xx11.cpp to cover this case:
>>>
>>> namespace Cxx11BraceInit {
>>> struct Foo {
>>> ~Foo() {}
>>> };
>>>
>>> void testInitializerList() {
>>> for (Foo foo : {Foo(), Foo()}) {}
>>> }
>>> }
>>>
>>> Without the array special casing, clang crashes while parsing this:
>>> clang:
>>> third_party/llvm/llvm/tools/clang/lib/StaticAnalyzer/Core/ExprEngineCXX.cpp:322:
>>> void clang::ento::ExprEngine::VisitCXXDestructor(clang::QualType, const
>>> clang::ento::MemRegion *, const clang::Stmt *, bool,
>>> clang::ento::ExplodedNode *, clang::ento::ExplodedNodeSet &): Assertion
>>> `RecordDecl && "Only CXXRecordDecls destructors can be processed"' failed.
>>>
>>> I've updated the special casing to be a bit simpler, but I think it (or
>>> something like it) is necessary to avoid crashing on initializer_lists.
>>> What do you think?
>>>
>>> Your recommendation of skipping destructors in VisitCXXConstructExpr
>>> worked perfectly: I've updated getRegionForConstructedObject in
>>> ExprEngineCXX.cpp to recurse when it finds a destructor, and that fixed the
>>> spurious garbage return value warnings, which now means that this patch
>>> eliminates all large scale false positives on this project's codebase.
>>> Thanks for your help!
>>>
>>> If there are any parts of this change that you'd like to split out and
>>> individually commit (like the dtor handling in PathDiagnostic.cpp) that
>>> sounds fine to me. I'm happy with whatever patching combination you'd
>>> prefer if you help me through the splitting and committing process.
>>>
>>> Thanks again for your help with this!
>>>
>>> -Alex
>>>
>>>
>>> On Tue, Mar 4, 2014 at 7:45 PM, Jordan Rose <jordan_rose at apple.com>wrote:
>>>
>>>> Wow, thanks for working on this, Alex. Unfortunately I think there may
>>>> be a few more problems than simply turning things back on. In particular,
>>>> from test/Analysis/temporaries.cpp:
>>>>
>>>> if (compute(i == 5 &&
>>>> (i == 4 || i == 4 ||
>>>> compute(i == 5 && (i == 4 ||
>>>> check(NoReturnDtor()))))) ||
>>>> i != 4) {
>>>> - clang_analyzer_eval(true); // no warning, unreachable code
>>>> + clang_analyzer_eval(true); // expected-warning{{TRUE}} (possible
>>>> when i=6)
>>>> }
>>>>
>>>> i cannot equal 6 at this point in the code; testConsistencyNested has a
>>>> line earlier that says "if (i != 5) return". So we're not getting the
>>>> correct behavior here—either the destructor isn't ending up in the right
>>>> place in the CFG, or something is invalidating the value of 'i' that
>>>> shouldn't be. I would guess it's the former, since this series of tests
>>>> were designed to check Pavel's reworking of the CFG.
>>>>
>>>> This part confuses me:
>>>>
>>>> + while (const ArrayType *ArrayType =
>>>> Ctx.getAsArrayType(ObjectType)) {
>>>> + ObjectType = ArrayType->getElementType();
>>>> + VisitCXXDestructor(ObjectType, Dest, S, IsBaseDtor, Pred, Dst);
>>>> + }
>>>>
>>>> For a multidimensional array of, say, Foo, this visits "array",
>>>> "array[0]", "array[0][0]", etc, down to the single element case. In
>>>> addition, visiting "array[0]" will *also* trigger a destruction of
>>>> "array[0][0]", etc., since this loop happens as the very first thing in
>>>> VisitCXXDestructor.
>>>>
>>>> I would just leave the FIXME as is here, and not worry about this.
>>>>
>>>> // FIXME: We need to run the same destructor on every element of the
>>>> array.
>>>> // This workaround will just run the first destructor (which will
>>>> still
>>>> // invalidate the entire array).
>>>>
>>>> And then we have your new test case:
>>>>
>>>> + //TODO: figure out why this case causes an unexpected "Undefined or
>>>> garbage value returned to caller" warning
>>>> + bool testNamedCustomDestructor() {
>>>> + if (CheckCustomDestructor c = CheckCustomDestructor())
>>>> + return true;
>>>> + return false;
>>>> + }
>>>>
>>>> First of all, nicely discovered. I'm not immediately sure what's wrong
>>>> here, but let's take a look at the CFG:
>>>>
>>>> * [B3]*
>>>> 1: CheckCustomDestructor() (CXXConstructExpr, struct
>>>> CheckCustomDestructor)
>>>> 2: [B3.1] (BindTemporary)
>>>> 3: [B3.2] (ImplicitCastExpr, NoOp, const struct
>>>> CheckCustomDestructor)
>>>> 4: [B3.3]
>>>> 5: [B3.4] (CXXConstructExpr, struct CheckCustomDestructor)
>>>> 6: ~CheckCustomDestructor() (Temporary object destructor)
>>>> 7: CheckCustomDestructor c = CheckCustomDestructor();
>>>>
>>>> B3.1 is the actual creation of the temporary. B3.5 is the copy
>>>> constructor required by the C++ standard to copy the temporary into 'c'.
>>>> B3.6 is the destruction of the temporary, and B3.7 is the actual VarDecl
>>>> for 'c'. (The block then goes on to call 'operator bool' on 'c' and then do
>>>> the if-branch.)
>>>>
>>>> The current handling of constructors for VarDecls is a bit hacky. If
>>>> you look in ExprEngine::VisitCXXConstructExpr, you'll notice it tries to
>>>> look ahead to the next CFG element to see if it's constructing a particular
>>>> variable. If so, it sets the target region to that variable. The trouble
>>>> is, there's now a destructor between B3.5 and B3.7, so my guess is that the
>>>> analyzer has decided it's *not* constructing a variable. I am okay
>>>> with cheating right now by skipping over destructor CFG elements in
>>>> VisitCXXConstructExpr, but I haven't thought about if there's a better way
>>>> to tell that a particular CXXConstructExpr goes with a particular VarDecl.
>>>>
>>>> As far as this part goes...
>>>>
>>>> - case CFGElement::TemporaryDtor:
>>>> + case CFGElement::TemporaryDtor: {
>>>> + const CFGTemporaryDtor &Dtor = Source.castAs<CFGTemporaryDtor>();
>>>> + return PathDiagnosticLocation(Dtor.getBindTemporaryExpr(), SM,
>>>> CallerCtx);
>>>> + }
>>>>
>>>> ...that seems like a good obvious change, and I'm happy to commit that
>>>> (or for you to commit that) without turning anything else on. :-)
>>>>
>>>> I know this is a lot to throw at you at once, but please continue to
>>>> e-mail me with questions and progress. I'm very happy that someone is able
>>>> to put time into this.
>>>>
>>>> Jordan
>>>>
>>>>
>>>> On Mar 2, 2014, at 0:41 , Alex McCarthy <alexmc at google.com> wrote:
>>>>
>>>> Hi all,
>>>>
>>>> I'm running clang's static analyzer on a C++ codebase at Google. I saw
>>>> a roughly a 50% false positive rate which stemmed from the analyzer not
>>>> recognizing temporary object destructors: this issue is discussed in some
>>>> length in another thread, which mentions a similar error rate on the
>>>> Chromium codebase:
>>>> http://comments.gmane.org/gmane.comp.compilers.clang.devel/33901
>>>>
>>>> Starting from Pavel's work which was reverted in
>>>> http://llvm-reviews.chandlerc.com/rL186925 , I've put together a new
>>>> patch (see attachment) that attempts to fix temporary object destructor
>>>> handling.
>>>>
>>>> This new patch fixes all of the new regression tests added after
>>>> Pavel's change was reverted, notably including
>>>> http://llvm-reviews.chandlerc.com/rL187133 . I've also fixed some
>>>> other crashes, including a crash when processing an array of temporary
>>>> objects use in a C++11 initializer_list, covered by a new regression test
>>>> in cfe/test/Analysis/dtor-cxx11.cpp . And most importantly, running
>>>> clang with this patch eliminates the 50% false positive rate I saw
>>>> previously (from ~800 warnings to ~400 across the ~1700 file codebase).
>>>>
>>>>
>>>> Now for the bad news:
>>>>
>>>> This patch introduces a new regression which wasn't covered by existing
>>>> tests: named temporaries declared and used within if statements are
>>>> considered dead while they're still being used, which results in "Undefined
>>>> or garbage value returned to caller" errors. I've added regression tests
>>>> to test/Analysis/dtor.cpp to cover this case, which currently fail. I've
>>>> also updated test/Analysis/temp-obj-dtors-cfg-output.cpp with relevant CFG
>>>> dumps to try to debug the problem. This new false positive is much nosier
>>>> than the ones this patch fixes: the only advantage to the current patch
>>>> as-is is that the garbage return value warnings are emitted in a small
>>>> collection of header files, making them much easier to ignore en masse.
>>>>
>>>> I don't have any compiler experience, so I'm moving slowly in the clang
>>>> codebase and could use some help understanding where to look next. I've
>>>> mostly been handling each crash or error as I find it, but I don't have a
>>>> high level understanding of the impact or context of my change. In
>>>> particular, I don't know how to read the CFG dumps I've generated, so I'm
>>>> not sure where things are going wrong. Ted, Jordan, and Anna: Manuel
>>>> Klimek mentioned that you've looked into this issue at length. Do have any
>>>> advice on what I'm doing wrong, or could you suggest other approaches I
>>>> might be able to try? Anything you can think of that can speed up my search
>>>> for a fix would be greatly appreciated.
>>>>
>>>> If we can get this patch working, it should address the following
>>>> issues:
>>>> http://llvm.org/bugs/show_bug.cgi?id=15599
>>>> http://llvm.org/bugs/show_bug.cgi?id=16664
>>>> http://llvm.org/bugs/show_bug.cgi?id=18159 (not sure, this bug is
>>>> referenced by a newly fixed test in test/Analysis/temporaries.cpp)
>>>>
>>>> Thanks for your help,
>>>> -Alex McCarthy
>>>> <temporary-destructors.patch>
>>>>
>>>>
>>
> <ClangSimpleNoDtors.pdf><ClangComplexNoDtors.pdf><ClangSimple.pdf>
> <ClangComplex.pdf>
>
>
>
> _______________________________________________
> cfe-dev mailing list
> cfe-dev at cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20140324/15d285e1/attachment.html>
More information about the cfe-dev
mailing list