This is an archive of the discontinued LLVM Phabricator instance.

CFG: Add CFGElement for automatic variables that leave the scope
ClosedPublic

Authored by mgehre on Nov 26 2015, 3:59 PM.

Details

Summary

This mimics the implementation for the implicit destructors. The
generation of this scope leaving elements is hidden behind
a flag to the CFGBuilder, thus it should not affect existing code.

Diff Detail

Repository
rL LLVM

Event Timeline

mgehre updated this revision to Diff 41278.Nov 26 2015, 3:59 PM
mgehre retitled this revision from to CFG: Add CFGElement for automatic variables that leave the scope.
mgehre updated this object.
mgehre added reviewers: krememek, jordan_rose.
mgehre added a subscriber: cfe-commits.

The lifetime checker that needs this is at D15032

alexfh added a subscriber: alexfh.Mar 18 2016, 3:58 AM

Richard, can you review this?

rsmith edited edge metadata.Mar 30 2016, 11:09 AM

Please add a test that builds and dumps a CFG and checks it has the right shape. It's generally not sufficient for the only tests for one LLVM project to exist in a different LLVM project. See test/Analysis/cfg.cpp for an example of how to do this.

include/clang/Analysis/CFG.h
170 ↗(On Diff #41278)

What is this intended to model? There seem to be a few options here:

  1. The point at which the destructor would run if the object had a non-trivial destructor
  2. The point at which the storage duration for the underlying storage ends
  3. The point at which the lifetime of the object ends

Note that these are all different -- for an object with a non-trivial destructor, (1) and (3) are the same and for any other object (2) and (3) are the same; (2) occurs after all destructors for the scope have run.

This matters for cases like:

void f() {
  struct A { int *p; ~A() { *p = 0; } } a;
  int n;
  a.p = &n;
}

Here, the lifetime of n would end before the lifetime of a if n had a non-trivial destructor. If ns lifetime actually ended there, this code would have undefined behavior. But because the destruction of n is trivial, the lifetime of n instead ends when its storage duration ends, which is *after* A's destructor runs, so the code is valid.

Please add a comment to this class to describe what it means.

728 ↗(On Diff #41278)

Why must reverse order be used? It's not possible for the effects of these operations to interact with each other, is it? At least according to the C++ standard, the "end of storage duration" effects all occur simultaneously.

lib/Analysis/CFG.cpp
1233 ↗(On Diff #41278)

thats -> that

1447 ↗(On Diff #41278)

This will sometimes bail out without adding a scope; if both AddAutomaticObjLeavesScope and AddImplicitDtors are set, this seems like the wrong behavior. You should check for AddAutomaticObjLeavesScope first and unconditionally ensure there is a scope for that case.

1490–1491 ↗(On Diff #41278)

This is not a mechanism for adding automatic destructors. This FIXME seems unnecessary.

1501 ↗(On Diff #41278)

Bad indentation

Thank you very much for your review. I'm sorry that I'm currently quite busy, but I will find some time to answer at the end of this week.

Matthias,

Could you take a look at http://reviews.llvm.org/D16403? It looks like a duplicating work but it should cover not Objective-C only.

mgehre added inline comments.Apr 6 2016, 2:56 PM
include/clang/Analysis/CFG.h
170 ↗(On Diff #41278)

The intend is to show the point after which it is undefined behavior to refer to an object, i.e.

  1. The point at which the lifetime of the object ends

I will add a comment to clarify this. I propose to rename the class to "CFGLifetimeEnds", okay?

728 ↗(On Diff #41278)

The order is important as you showed in your example above. The liftetime checker should be able to detect the undefined behavior in

struct B { B() {}; int n; };
void f() {
  struct A {B *p; ~A() { b->n = 0; } } a;
  B b;
  a.p = &b;
}
mgehre added a comment.Apr 7 2016, 1:53 PM

By the way, is there a tool to generate parts of the test based on clang output, i.e.
something that will prefix the output of clang with "CHECK: " and "CHECK-NEXT:" so I can copy-and-paste
it into my test file?

mgehre updated this revision to Diff 52959.Apr 7 2016, 3:02 PM
mgehre edited edge metadata.

Update for review comments

  • Change name from ObjLeavesScope to LifetimeEnds
  • Make sure that trivially destructible objects end their lifetime after non-trivial destructible objects
  • Add test
  • Add analyzer option to enable LifetimeEnds CFG entries (disabled by default)

Note that AddImplicitDtors is mutally exclusive with AddLifetime (may be changed by a later patch)

mgehre updated this revision to Diff 53092.Apr 8 2016, 2:48 PM

Fix assert in LocalScope::const_iterator::distance when using goto to jump over trivially constructable variable declarations
Added two test cases for this

mgehre updated this object.Apr 8 2016, 4:49 PM
mgehre updated this revision to Diff 53261.Apr 11 2016, 9:37 AM

Remove unused CFGBuilder::prependLifetimeEndsWithTerminator

Friendly ping

dcoughlin edited reviewers, added: dcoughlin; removed: jordan_rose, krememek.Aug 2 2016, 4:48 PM
dcoughlin edited edge metadata.Aug 16 2016, 6:31 PM

Thanks for patch! Some comments inline.

You don't have to do it in this patch, but I think it would be good to get this working with AddImplicitDtors. I think it would also be good to (eventually) add CFGElements marking when the storage duration for underlying storage ends. This would allow the static analyzer to warn when writing to storage that no longer exists, which is something I believe a.sidorin is working on in D19979.

lib/Analysis/CFG.cpp
285 ↗(On Diff #53261)

I think you can make this linear time by walking up the spine of *this until you find either L or the root and caching the ancestors along the way. If you found L, you are done. If not, you can then walk up the spine from L until you find a scope in the cache.

While this approach is unlikely to be needed for human-written code, we do want to make sure to gracefully handle bizarre, deeply-nested scopes that have been programmatically generated.

1091 ↗(On Diff #53261)

I don't think you handle back-patched gotos yet. For example, consider:

void foo() {
  int i;
  label:
  B b;
  goto label;
  i++;
}

Here the lifetime of b should end immediately before the goto (right?) but your patch says it ends after i++.

1260 ↗(On Diff #53261)

Nit: Missing word here. "To *go* from B to E ..."?

mgehre updated this revision to Diff 91378.Mar 10 2017, 10:44 AM
mgehre marked an inline comment as done.

Handle back-patches gotos and add test case
Turned LocalScope::const_iterator::shared_parent from O(N^2) into O(N) time
The combination with AddImplicitDtors will be added in a separate patch

I'm sorry for the long delay!

Regarding " I think it would also be good to (eventually) add CFGElements marking when the storage duration for underlying storage ends.":
From what I understand, this only differs from the end of lifetime in case of objects with non-trivial destructors, where the lifetime ends before
the destructor is called and the storage duration ends afterwards.
In which case is this difference important to the static analyzer? Accessing an object after its lifetime ended is already UB, so the static analyzer could warn on this,
even before the storage duration for underlying storage ends.

mgehre marked an inline comment as done.Mar 30 2017, 11:40 AM

Friendly ping

dcoughlin accepted this revision.Jul 5 2017, 10:52 AM

Sorry for the long delay! This looks good to me. Do you have commit access, or do you need someone to commit it for you?

Regarding " I think it would also be good to (eventually) add CFGElements marking when the storage duration for underlying storage ends.":
From what I understand, this only differs from the end of lifetime in case of objects with non-trivial destructors, where the lifetime ends before
the destructor is called and the storage duration ends afterwards.
In which case is this difference important to the static analyzer? Accessing an object after its lifetime ended is already UB, so the static analyzer could warn on this,
even before the storage duration for underlying storage ends.

There a couple of cases where the difference between storage duration and lifetime could be important to the analyzer. For example, you can end the lifetime of an object prematurely by calling its destructor explicitly. Then, you can later create a new object in its place with new -- but only if the storage is still around. So

  F f;
  f.~F();
// lifetime of object in 'f' ends
  new (&f) F;
// lifetime of new object in 'f' begins

is fine, but

F *p;
{
  F f;
  f.~F();
  p = &f;
}
new (p) F;

is not.

This revision is now accepted and ready to land.Jul 5 2017, 10:52 AM
This revision was automatically updated to reflect the committed changes.