[analyzer] Temporaries.

classic Classic list List threaded Threaded
14 messages Options
Reply | Threaded
Open this post in threaded view
|

[analyzer] Temporaries.

Hans Wennborg via cfe-dev
Handling C++ temporary object construction and destruction seems to be
the biggest cause of false positives on C++ code at the moment. I'd be
looking into this, even though for now i don't see the whole scale of
problem.

== CFG, destructors, and ProgramPoints ==

We should probably enable `-analyzer-config cfg-temporary-dtors=true` by
default soon. It is a fairly low-impact change because it only alters
the CFG but the analyzer rarely actually uses the new nodes. Destructors
for the most part are still evaluated conservatively, with improper
object regions. So it causes almost no changes in the analyzer's
positives for now, but it definitely opens up room for further improvements.

I'm observing a couple of problems with this mode at the moment, namely
the rich CFG destructor element hierarchy is not currently complemented
by an equally rich ProgramPoint hierarchy. This causes the analysis to
merge nodes which are not equivalent, for example two implicit
destructors of the same type (with the same function declaration) may
sometimes cause the ExplodedGraph to coil up and stop analysis (lost
coverage) because of having the same program state at the
erroneously-same program point. Because situations when we can guarantee
a change in the program state are pretty rare, we'd have to produce more
program point kinds to handle this correctly.

CallEvent hierarchy is also very much affected in a similar manner -
because apparently we're constructing program points by looking at
CallEvents, so they'd need to carry all the information that's needed to
construct the pre-call/post-call program point.

== Construction contexts ==

We are correctly modeling "this" object region during
construction/destruction of variables with automatic storage duration,
fields and base classes, and on operator new() since recently, as long
as these aren't arrays of objects. It was not yet implemented for other
cases such as temporaries, initializer lists, fields or C++17 base
classes within aggregates, and pass-by-value from/to functions (the
latter being a slightly different problem than temporaries).

First of all, by "not yet implemented" i mean that instead of
constructing into (destroying) the correct object (in the correct memory
region), we come up with a "temporary region", which looks exactly like
a region of a valid C++ temporary but is only used for communicating
that it is not the right region. Then we look at the region, see that it
is a temporary, and avoid inlining constructors, because it would make
little sense when the region is not correct. However, if we are to model
temporaries, we need another way of communicating our failure to find
the correct region, which is being addressed by
https://reviews.llvm.org/D42457

Also in the cases when the correct region is used, it is being computed
in a funky way: in order to figure out where do we construct the object,
we walk forward in the CFG (or from child to parent in the AST) to find
the next/parent statement that would accomodate the newly constructed
object. This means that the CFG, while perfectly telling us what to do
in what order (which we, unlike CodeGen, cannot easily take from AST
because we cannot afford recursive evaluation of statements, mainly
because of inlining), discards too much context to be helpful in
understanding how to do it.

I tried to add the information about such "trigger statements" for
constructors into CFG and it is extremely helpful and easy to both use
and extend. This assumes adding a new sub-class of CFGElement for
constructors, which maintain a "construction context" - for now it's
just a trigger statement. For instance, in

   class C { ... };
   void foo() {
     C c;
   }

...the trigger for constructor C() would be DeclStmt `C c`, and once we
know this we can immediately figure out that the construction target is
the region of variable `c`. Construction trigger is not necessarily a
statement - it may be a CXXCtorInitializer, which is an AST node kind of
its own. Additionally, when constructing aggregates via initializer
lists, we may have the same statement trigger multiple constructors, eg. in

   class C { public: C(int); ~C(); };
   struct S { C c1, c2, c3; };
   void foo() {
     S s { 1, 2, 3 };
   }

... we have three different constructors (actually six different
constructors if we include elidable copy constructors) for c1, c2, c3
(and lack of constructor for `s` because of the aggregate thing). It
would be more natural to declare that the specific field or index would
be a part of the CFG's construction context, as well as the intermediate
InitListExpr, so even in these simple cases the construction context may
get quite bulky. And this example is quite popular on actual code -
probably the second worst cause of false positives after temporaries.

For now i have no specific plan on what would construction context for
temporaries contain in the general case. I might not be able to get the
data structures right from the start. In any case, it might be necessary
to perform additional memory allocations for these CFG elements (for
analyzer's CFG only, so it wouldn't affect compilation time or warnings).

I believe that getting the correct target region in as many cases as
possible would be the main part of my work for the nearest future. And i
want to move most this work to CFG, while letting the analyzer pick up
the trigger statement from it and trust it as blindly as possible.

== Workflow ==

When working on operator new, i tried hard to maintain a reasonable
history, making around 15 local rebases. It was not awesome because it
was hard for the reviewers to understand the context of the new changes,
and changes could have easily kicked in during rebases. A few lessons
learned here would be to commit more aggressively, i.e. avoiding
stockpiling a large history of patches (essentially a large branch),
which in turn would be possible through trying harder to avoid unrelated
hard-to-test core changes (as long as it doesn't require weird
workarounds) that aren't covered by a flag (such as those evalCast
fixes), in order to make sure reviewing take less responsibility. It's
fine if some parts would later be fixed (assuming they would indeed be
fixed), if it means making the turnaround faster and the tail of patches
shorter - that's also the attitude i'd try to maintain when reviewing
stuff myself.
_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: [analyzer] Temporaries.

Hans Wennborg via cfe-dev
A bit of an update.

== Temporary destructors ==

Adding some initial support for temporary destructors seems pretty easy
and straightforward at this point, given the awesome work done by Manuel
Klimek on our CFG a few years ago.

1. We already have the awesome CFGTemporaryDtor elements, which have the
backreference to the CXXBindTemporaryExpr for their temporaries.

2. In simple cases CXXBindTemporaryExprs have an immediate constructor
within them, and therefore we can provide the CXXBindTemporaryExprs as
the construction context's trigger statements, and therefore have a
reliable CXXTempObjectRegion for constructors.

3. Then we already track the CXXBindTemporaryExprs for the active
temporaries in the program state. We can attach any constructor
information to them, such as the target region, if we need to (probably
we can reconstruct it by looking at the expression and the location
context, not sure if we want to).

4. So when we reach the CFGTemporaryDtor element, we can just lookup all
the info we need, and perform the destruction properly.

5. There's a bit of a liveness problem, because it seems that our
liveness analysis tends to throw away the temporary too early. I can
easily hack this problem away by marking all regions that correspond to
active temporaries as live. I'll see if there's a better solution.

== CXXDefaultArgExpr problems ==

There's a known problem with those. Consider:

   void foo(const C &c = C()) {
   }

   void bar() {
     foo();
     foo();
   }

Each call of foo() contains a CXXDefaultArgExpr for c. The default
argument value C() is constructed before we enter foo() and destroyed
after we leave foo(). However, c's initializer, "= C()", is *not part of
the AST of bar()*. In particular, when foo() is called twice, the
initializer for the two calls is the same, only CXXDefaultArgExprs are
different. This screws a lot of invariants in the analyzer: program
points start coinciding (causing the analysis to loop and cache out),
Environment doesn't expect the same expression in the same location
context have two different values (suppose calls are nested into each
other), analysis taking wrong branches, and so on.

Luckily, default-arg expressions that aren't zero integers or null
pointers are pretty rare. Still, we'd need to eventually think how to
avoid any really bad practical problems with them.

On 25/01/2018 9:08 AM, Artem Dergachev wrote:

> Handling C++ temporary object construction and destruction seems to be
> the biggest cause of false positives on C++ code at the moment. I'd be
> looking into this, even though for now i don't see the whole scale of
> problem.
>
> == CFG, destructors, and ProgramPoints ==
>
> We should probably enable `-analyzer-config cfg-temporary-dtors=true`
> by default soon. It is a fairly low-impact change because it only
> alters the CFG but the analyzer rarely actually uses the new nodes.
> Destructors for the most part are still evaluated conservatively, with
> improper object regions. So it causes almost no changes in the
> analyzer's positives for now, but it definitely opens up room for
> further improvements.
>
> I'm observing a couple of problems with this mode at the moment,
> namely the rich CFG destructor element hierarchy is not currently
> complemented by an equally rich ProgramPoint hierarchy. This causes
> the analysis to merge nodes which are not equivalent, for example two
> implicit destructors of the same type (with the same function
> declaration) may sometimes cause the ExplodedGraph to coil up and stop
> analysis (lost coverage) because of having the same program state at
> the erroneously-same program point. Because situations when we can
> guarantee a change in the program state are pretty rare, we'd have to
> produce more program point kinds to handle this correctly.
>
> CallEvent hierarchy is also very much affected in a similar manner -
> because apparently we're constructing program points by looking at
> CallEvents, so they'd need to carry all the information that's needed
> to construct the pre-call/post-call program point.
>
> == Construction contexts ==
>
> We are correctly modeling "this" object region during
> construction/destruction of variables with automatic storage duration,
> fields and base classes, and on operator new() since recently, as long
> as these aren't arrays of objects. It was not yet implemented for
> other cases such as temporaries, initializer lists, fields or C++17
> base classes within aggregates, and pass-by-value from/to functions
> (the latter being a slightly different problem than temporaries).
>
> First of all, by "not yet implemented" i mean that instead of
> constructing into (destroying) the correct object (in the correct
> memory region), we come up with a "temporary region", which looks
> exactly like a region of a valid C++ temporary but is only used for
> communicating that it is not the right region. Then we look at the
> region, see that it is a temporary, and avoid inlining constructors,
> because it would make little sense when the region is not correct.
> However, if we are to model temporaries, we need another way of
> communicating our failure to find the correct region, which is being
> addressed by https://reviews.llvm.org/D42457
>
> Also in the cases when the correct region is used, it is being
> computed in a funky way: in order to figure out where do we construct
> the object, we walk forward in the CFG (or from child to parent in the
> AST) to find the next/parent statement that would accomodate the newly
> constructed object. This means that the CFG, while perfectly telling
> us what to do in what order (which we, unlike CodeGen, cannot easily
> take from AST because we cannot afford recursive evaluation of
> statements, mainly because of inlining), discards too much context to
> be helpful in understanding how to do it.
>
> I tried to add the information about such "trigger statements" for
> constructors into CFG and it is extremely helpful and easy to both use
> and extend. This assumes adding a new sub-class of CFGElement for
> constructors, which maintain a "construction context" - for now it's
> just a trigger statement. For instance, in
>
>   class C { ... };
>   void foo() {
>     C c;
>   }
>
> ...the trigger for constructor C() would be DeclStmt `C c`, and once
> we know this we can immediately figure out that the construction
> target is the region of variable `c`. Construction trigger is not
> necessarily a statement - it may be a CXXCtorInitializer, which is an
> AST node kind of its own. Additionally, when constructing aggregates
> via initializer lists, we may have the same statement trigger multiple
> constructors, eg. in
>
>   class C { public: C(int); ~C(); };
>   struct S { C c1, c2, c3; };
>   void foo() {
>     S s { 1, 2, 3 };
>   }
>
> ... we have three different constructors (actually six different
> constructors if we include elidable copy constructors) for c1, c2, c3
> (and lack of constructor for `s` because of the aggregate thing). It
> would be more natural to declare that the specific field or index
> would be a part of the CFG's construction context, as well as the
> intermediate InitListExpr, so even in these simple cases the
> construction context may get quite bulky. And this example is quite
> popular on actual code - probably the second worst cause of false
> positives after temporaries.
>
> For now i have no specific plan on what would construction context for
> temporaries contain in the general case. I might not be able to get
> the data structures right from the start. In any case, it might be
> necessary to perform additional memory allocations for these CFG
> elements (for analyzer's CFG only, so it wouldn't affect compilation
> time or warnings).
>
> I believe that getting the correct target region in as many cases as
> possible would be the main part of my work for the nearest future. And
> i want to move most this work to CFG, while letting the analyzer pick
> up the trigger statement from it and trust it as blindly as possible.
>
> == Workflow ==
>
> When working on operator new, i tried hard to maintain a reasonable
> history, making around 15 local rebases. It was not awesome because it
> was hard for the reviewers to understand the context of the new
> changes, and changes could have easily kicked in during rebases. A few
> lessons learned here would be to commit more aggressively, i.e.
> avoiding stockpiling a large history of patches (essentially a large
> branch), which in turn would be possible through trying harder to
> avoid unrelated hard-to-test core changes (as long as it doesn't
> require weird workarounds) that aren't covered by a flag (such as
> those evalCast fixes), in order to make sure reviewing take less
> responsibility. It's fine if some parts would later be fixed (assuming
> they would indeed be fixed), if it means making the turnaround faster
> and the tail of patches shorter - that's also the attitude i'd try to
> maintain when reviewing stuff myself.

_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: [analyzer] Temporaries.

Hans Wennborg via cfe-dev
More explanations on how the analyzer keeps making its way around the
C++ AST.

== Lifetime extension ==

This is a brain dump of how (and how much) lifetime extension of
temporary objects is currently broken in the static analyzert. Spoilers:
not too much, it seems, but annoying nevertheless.

Consider an example:

      1    class C {
      2    public:
      3      C() {}
      4      ~C() {}
      5    };
      6
      7    void foo() {
      8      const C &c = C();
      9    }

With the AST for the variable declaration:

       DeclStmt 0x7fa5ac85cba0 <line:8:3, col:19>
       `-VarDecl 0x7fa5ac85c878 <col:3, col:18> col:12 c 'const C &' cinit
         `-ExprWithCleanups 0x7fa5ac85cb30 <col:16, col:18> 'const C' lvalue
           `-MaterializeTemporaryExpr 0x7fa5ac85cb00 <col:16, col:18>
'const C' lvalue extended by Var 0x7fa5ac85c878 'c' 'const C &'
             `-ImplicitCastExpr 0x7fa5ac85cae8 <col:16, col:18> 'const
C' <NoOp>
               `-CXXBindTemporaryExpr 0x7fa5ac85cac8 <col:16, col:18>
'C' (CXXTemporary 0x7fa5ac85cac0)
                 `-CXXTemporaryObjectExpr 0x7fa5ac85ca88 <col:16,
col:18> 'C' 'void ()'

*here goes a periodic reminder that CXXTemporaryObjectExpr is a
sub-class of CXXConstructExpr*

Notice how MaterializeTemporaryExpr is the innermost expression (the
first one in the order of execution) that is an lvalue. Essentially, you
can think of it as the mythical "rvalue-to-lvalue" cast that takes in a
C++ object rvalue and returns the this-value for that object. Because
all C++ objects have a this-value that never changes throughout their
lifetime, it is essentially their identity. Otherwise you can't call
methods on them.

MaterializeTemporaryExpr also contains information about the lifetime
extension process: we needed the this-value in order to bind it to
variable 'c'. You see that in the AST.

In the analyzer, however, MaterializeTemporaryExpr does a different
thing, as a temporary solution (no pun intended). It constructs a new
temporary region out of thin air and binds the rvalue object to that
temporary in the Store. The respective function in our code is called
"createTemporaryRegionIfNeeded". It also has a separate purpose of
converting rvalue sub-object adjustments into lvalue sub-object
adjustments, which we wouldn't discuss this time.

Now that we learned how to inline temporary constructors and
destructors, it essentially means that the this-value in the constructor
and in the destructor would be different. Because first we construct the
object into temporary region R1, then we take lazyCompoundVal{R1} to
represent the value of CXXTemporaryObjectExpr, then we materialize
lazyCompoundVal{R1} to R2, then we bind R2 to variable 'c', then we call
the automatic(!) destructor for 'c' which contains R2. To be clear, the
region store at the time of destruction would be:

   c: R2,
   R2: lazyCompoundVal{R1}.

It means that fields of the object would contain the correct values,
there would be the correct number of destructors called (no temporary
destructors, just one automatic destructor), but the identity of the
object (this-value) would change in the process. Unless the object
actually makes any decisions or does any manipulations that involve its
this-value, the modeling should be correct. When the object starts to
actively use its this-value in its inlined methods, the analysis would
do wrong stuff. Additionally, it causes a mess in the checkers when they
try to track objects by their this-values - i.e. IteratorChecker has a
lot of additional code to work around the fact that the region for the
object constantly changes.

 From the above it is clear that MaterializeTemporaryExpr should not
construct any new regions, at least not in this case. We already have
the correct region, namely R1, which should be re-used.

It is tempting to take R1 directly from lazyCompoundVal{R1} - it already
has memories about once being a value of R1. I'm not sure it's not going
to work - it may work, at least i'm not ready to come up with a
counterexample. But the meaning of LazyCompoundVal's parent region is
different and coincides with what we want just accidentally. Namely,
lazyCompoundVal{R1} is a value of an object that was bound to R1 in some
particular moment of time in the past, without any explanation of when
this moment of time was - but there's no indication if R1 is the region
of the temporary we've just constructed, or a region of an unrelated
object that used to have the same value back then. As we'd see later,
MaterializeTemporaryExpr doesn't always contain a constructor within it
- there are a lot of cases to cover, and if the trick doesn't work even
once, it's going to be hard, so i'd probably not going to commit into
maintaining this invariant. Though it might be plausible to modify add
an SVal kind that does exactly what we mean here - i.e. a value that
does indeed correspond to a specific C++ object identified by region. It
might be a beautiful solution, but it may also fail miserably if tricky
cornercases show up - so i'm not ready to commit to that. Also the
correct way of dealing with such values (i.e. for how long are they
relevant?) would be extremely difficult to explain to checker developers.

The more straightforward approach here is to include
MaterializeTemporaryExpr (hereinafter MTE) into the construction
context. It means, if a temporary that we're about to construct would be
lifetime-extended later, we'd rather know about that during
construction, and maintain a map in the program state from MTE to their
respective temporary regions that were used for representing the
respective construction targets. Upon encountering the respective MTE
we'd simply retrieve the implicit temporary storage for the value from
the program state and declare that temporary region to be the value of
the MTE. This would mimic the approach we have with
CXXBindTemporaryExprs (hereinafter BTE) and their respective regions
that allows temporary destructors to work - but this time it's going to
be about MaterializeTemporaryExprs and automatic destructors. I imagine
that on the checker side this can potentially be exposed via some sort
of State->getTemporaryStorage(Expr) call, but i believe that generally
this process should be as transparent to the checkers as possible.

It sounds as if both of these maps could be eliminated by always making
sure that the target temporary is constructed "with" the MTE (for
lifetime-extended temproraries) or BTE (for temporaries that require
destruction at the end of full-expression). In this case, with the help
of construction context-assisted lookahead, we declare that the target
of the construction is CXXTempObjectRegion(MTE, LC) or
CXXTempObjectRegion(BTE, LC) respectively, rather than
CXXTempObjectRegion(CXXConstructExpr). Then during evaluation of MTE or
BTE we'd simply construct the same region with the expression we're
currently evaluating, and it's automagically going to be the correct
region. This approach, however, becomes confusing when we start dealing
with elidable constructors (explained below). So for now i believe that
it is quite irrelevant which expression is identifying the temporary region.

== Elidable constructors ==

While it doesn't sound like an immediately important task to implement
copy elision in the analyzer, it may help with making some things
easier. And it'd also make some reports fancier, as mentioned in
https://reviews.llvm.org/D43144.

Elidable copy-constructors can be explained as a form of lifetime
extension. Instead of copying the temporary, they keep using the
original value of the temporary, which in some pretty twisted sense
means that they are lifetime-extending it to be able to use it. For
example, if we modify our example by replacing the lifetime-extending
reference variable with a value-type variable:

      1    class C {
      2    public:
      3      C() {}
      4      ~C() {}
      5    };
      6
      7    void foo() {
      8      C c = C();
      9    }

...then we'd still have an MTE, even though lifetime extension would
seem to be gone:

       DeclStmt 0x7fb8f005afb8 <line:8:3, col:12>
       `-VarDecl 0x7fb8f005ac50 <col:3, col:11> col:5 c 'C' cinit
         `-ExprWithCleanups 0x7fb8f005afa0 <col:9, col:11> 'C'
           `-CXXConstructExpr 0x7fb8f005af68 <col:9, col:11> 'C' 'void
(const C &) noexcept' elidable
             `-MaterializeTemporaryExpr 0x7fb8f005af00 <col:9, col:11>
'const C' lvalue
               `-ImplicitCastExpr 0x7fb8f005aee8 <col:9, col:11> 'const
C' <NoOp>
                 `-CXXBindTemporaryExpr 0x7fb8f005aec8 <col:9, col:11>
'C' (CXXTemporary 0x7fb8f005aec0)
                   `-CXXTemporaryObjectExpr 0x7fb8f005ae88 <col:9,
col:11> 'C' 'void ()'

In this case the MTE is expressing the fact that the temporary
constructed via CXXTemporaryObjectExpr can be "lifetime-extended" (by
actually merging it with the stack variable) rather than copied, if the
CXXConstructExpr surrounding it would be chosen to be elided. The AST
doesn't make the elision choice for us - but is compatible with both
choices. The MTE essentially overrides the necessity of immediate
destruction provided by the BTE, and lets the surrounding AST decide
upon the lifetime of the object.

Because the analyzer currently does not do copy elision, it will use the
MTE only to compute the argument for the elidable copy-constructor, and
then perform the copy-construction, and then destroy the original
temporary at the end of the full-expression. Note, however, that in this
case we need to properly support both the BTE (for the temporary
destructor to work) and the MTE (for computing its value). We need to
implement the MTE's ability to perform "rvalue-to-lvalue-cast" even if
the temporary destruction is still necessary. For this reason, if we
rely on constructing temporary regions with the correct BTEs or MTEs, at
least one of these tasks becomes impossible to perform.

If we were to support copy elision, then the CXXTemporaryObjectExpr
constructor would go directly into the variable region. For the purposes
of modeling, it'd mean that only CXXTemporaryObjectExpr would actually
need to be modeled. But this would require additional coding in the
construction context to be able to realize that the target is the
variable while modeling the CXXTemporaryObjectExpr.

For the sake of completeness, let's consider the ternary operator example:

      1    class C {
      2    public:
      3      C(int) {}
      4      ~C() {}
      5    };
      6
      7    void foo(int coin) {
      8      const C &c = coin ? C(1) : C(2);
      9    }

The respective AST would be:

       DeclStmt 0x7fc1e20023e0 <line:8:3, col:34>
       `-VarDecl 0x7fc1e2001dc8 <col:3, col:33> col:12 c 'const C &' cinit
         `-ExprWithCleanups 0x7fc1e2002370 <col:16, col:33> 'const C' lvalue
           `-MaterializeTemporaryExpr 0x7fc1e2002340 <col:16, col:33>
'const C' lvalue extended by Var 0x7fc1e2001dc8 'c' 'const C &'
             `-ImplicitCastExpr 0x7fc1e2002328 <col:16, col:33> 'const
C' <NoOp>
               `-ConditionalOperator 0x7fc1e20022f8 <col:16, col:33> 'C'
                 |-ImplicitCastExpr 0x7fc1e2002170 <col:16> 'bool'
<IntegralToBoolean>
                 | `-ImplicitCastExpr 0x7fc1e2002158 <col:16> 'int'
<LValueToRValue>
                 |   `-DeclRefExpr 0x7fc1e2001e28 <col:16> 'int' lvalue
ParmVar 0x7fc1e2001c18 'coin' 'int'
                 |-CXXBindTemporaryExpr 0x7fc1e2002248 <col:23, col:26>
'C' (CXXTemporary 0x7fc1e2002240)
                 | `-CXXConstructExpr 0x7fc1e2002208 <col:23, col:26>
'C' 'void (const C &) noexcept' elidable
                 |   `-MaterializeTemporaryExpr 0x7fc1e20021a0 <col:23,
col:26> 'const C' lvalue
                 |     `-ImplicitCastExpr 0x7fc1e2002188 <col:23,
col:26> 'const C' <NoOp>
                 |       `-CXXFunctionalCastExpr 0x7fc1e2002078 <col:23,
col:26> 'C' functional cast to class C <ConstructorConversion>
                 |         `-CXXBindTemporaryExpr 0x7fc1e2002058
<col:23, col:26> 'C' (CXXTemporary 0x7fc1e2002050)
                 |           `-CXXConstructExpr 0x7fc1e2002018 <col:23,
col:26> 'C' 'void (int)'
                 |             `-IntegerLiteral 0x7fc1e2001e60 <col:25>
'int' 1
                 `-CXXBindTemporaryExpr 0x7fc1e20022d8 <col:30, col:33>
'C' (CXXTemporary 0x7fc1e20022d0)
                   `-CXXConstructExpr 0x7fc1e2002298 <col:30, col:33>
'C' 'void (const C &) noexcept' elidable
                     `-MaterializeTemporaryExpr 0x7fc1e2002280 <col:30,
col:33> 'const C' lvalue
                       `-ImplicitCastExpr 0x7fc1e2002268 <col:30,
col:33> 'const C' <NoOp>
                         `-CXXFunctionalCastExpr 0x7fc1e2002130 <col:30,
col:33> 'C' functional cast to class C <ConstructorConversion>
                           `-CXXBindTemporaryExpr 0x7fc1e2002110
<col:30, col:33> 'C' (CXXTemporary 0x7fc1e2002108)
                             `-CXXConstructExpr 0x7fc1e20020d0 <col:30,
col:33> 'C' 'void (int)'
                               `-IntegerLiteral 0x7fc1e20020b0 <col:32>
'int' 2

Each branch contains two constructors: the temporary and the elidable
copy. The temporaries are surrounded with their respective BTEs and
copy-elision-kind MTEs, which indicates that they need to be either
destroyed as temporaries, or, if copy elision is chosen, have their
lifetime decided upon by the surrounding AST. The elidable copy
constructors also, being temporaries, have their respective BTEs. Note,
however, that there is only one MTE for both BTEs for the elidable
constructors.

So after the conditional operator is resolved (which is the first thing
we need to do, according to the CFG), we'd go ahead and perform the
constructors, and their trigger would be their respective BTE in the
non-elide case, and the single top-level MTE in the elide case. In the
non-elide case, copy constructors would be triggered by the top-level MTE.

It means that, once again, copy elision would prevent us from handling
both the BTE and the copy-elision-kind MTE in the single construction,
allowing the "predictable target region" trick to work: when we need the
temporary destructor, we construct directly into CXXTempObjectRegion of
the BTE and it gets automatically picked up during destruction, and when
we need the automatic destructor, we construct directly into
CXXTempObjectRegion of the MTE and we can easily compute the value of
the MTE. But when we don't do copy elision, we'd have to keep at least
one of those in the program state map.

== Return by value ==

Returning C++ objects by value is actually very similar to constructing
it. Consider:

      1    class C {
      2    public:
      3      C() {}
      4      ~C() {}
      5    };
      6
      7    C bar() {
      8      C c;
      9      return c;
     10    }
     11
     12    void foo() {
     13      const C &c = bar();
     14    }

With the respective AST for DeclStmt in foo():

       DeclStmt 0x7fe62c84f8e8 <line:13:3, col:21>
       `-VarDecl 0x7fe62c84f6b8 <col:3, col:20> col:12 c 'const C &' cinit
         `-ExprWithCleanups 0x7fe62c84f878 <col:16, col:20> 'const C' lvalue
           `-MaterializeTemporaryExpr 0x7fe62c84f848 <col:16, col:20>
'const C' lvalue extended by Var 0x7fe62c84f6b8 'c' 'const C &'
             `-ImplicitCastExpr 0x7fe62c84f830 <col:16, col:20> 'const
C' <NoOp>
               `-CXXBindTemporaryExpr 0x7fe62c84f810 <col:16, col:20>
'C' (CXXTemporary 0x7fe62c84f808)
                 `-CallExpr 0x7fe62c84f7e0 <col:16, col:20> 'C'
                   `-ImplicitCastExpr 0x7fe62c84f7c8 <col:16> 'C (*)()'
<FunctionToPointerDecay>
                     `-DeclRefExpr 0x7fe62c84f770 <col:16> 'C ()' lvalue
Function 0x7fe62c84f190 'bar' 'C ()'

And for the ReturnStmt in bar():

       ReturnStmt 0x7fe62c84f5b0 <line:9:3, col:10>
       `-CXXConstructExpr 0x7fe62c84f578 <col:10> 'C' 'void (const C &)
noexcept' elidable
         `-ImplicitCastExpr 0x7fe62c84f518 <col:10> 'const C' lvalue <NoOp>
           `-DeclRefExpr 0x7fe62c84f4f0 <col:10> 'C' lvalue Var
0x7fe62c84f280 'c' 'C'

Since https://reviews.llvm.org/D42875 we can already realize that the
constructor in bar(), assuming that we're inlining bar() during
analysis, would be constructed into something that is a return value of
bar(). This allows us, by looking that the StackFrameContext's call
site, to figure out that it is being constructed into the CallExpr in
foo(). Now if only we knew that that the call site is a
lifetime-extended temporary, i.e. if only we had a pointer to the
foo()'s MTE at the CallExpr's CFG element, we'd be able to find the
correct target region for construction: the CXXTempObjectRegion for the
MTE in the StackFrameContext of foo(). So i'm proposing to add some sort
of construction context to not only constructors, but also to functions
that return objects, and then during construction perform the lookup in
three easy steps:

   1. in the callee's CFG from constructor to return statement,
   2. through the location from the return statement to the call site,
   3. then through the caller's CFG from the call site to the MTE.

If the function is not inlined, we can still make use of the
construction context to represent the return value as a
LazyCompoundValue of the MTE's temporary. It would eliminate the need to
replace the return value with another value while evaluating the MTE,
and of course the need to re-bind the object to a different this-region.

So i believe that this is a good way to eliminate the need for the
"createTemporaryRegionIfNeeded" thing in the function calls as well.


On 06/02/2018 1:41 PM, Artem Dergachev wrote:

> A bit of an update.
>
> == Temporary destructors ==
>
> Adding some initial support for temporary destructors seems pretty
> easy and straightforward at this point, given the awesome work done by
> Manuel Klimek on our CFG a few years ago.
>
> 1. We already have the awesome CFGTemporaryDtor elements, which have
> the backreference to the CXXBindTemporaryExpr for their temporaries.
>
> 2. In simple cases CXXBindTemporaryExprs have an immediate constructor
> within them, and therefore we can provide the CXXBindTemporaryExprs as
> the construction context's trigger statements, and therefore have a
> reliable CXXTempObjectRegion for constructors.
>
> 3. Then we already track the CXXBindTemporaryExprs for the active
> temporaries in the program state. We can attach any constructor
> information to them, such as the target region, if we need to
> (probably we can reconstruct it by looking at the expression and the
> location context, not sure if we want to).
>
> 4. So when we reach the CFGTemporaryDtor element, we can just lookup
> all the info we need, and perform the destruction properly.
>
> 5. There's a bit of a liveness problem, because it seems that our
> liveness analysis tends to throw away the temporary too early. I can
> easily hack this problem away by marking all regions that correspond
> to active temporaries as live. I'll see if there's a better solution.
>
> == CXXDefaultArgExpr problems ==
>
> There's a known problem with those. Consider:
>
>   void foo(const C &c = C()) {
>   }
>
>   void bar() {
>     foo();
>     foo();
>   }
>
> Each call of foo() contains a CXXDefaultArgExpr for c. The default
> argument value C() is constructed before we enter foo() and destroyed
> after we leave foo(). However, c's initializer, "= C()", is *not part
> of the AST of bar()*. In particular, when foo() is called twice, the
> initializer for the two calls is the same, only CXXDefaultArgExprs are
> different. This screws a lot of invariants in the analyzer: program
> points start coinciding (causing the analysis to loop and cache out),
> Environment doesn't expect the same expression in the same location
> context have two different values (suppose calls are nested into each
> other), analysis taking wrong branches, and so on.
>
> Luckily, default-arg expressions that aren't zero integers or null
> pointers are pretty rare. Still, we'd need to eventually think how to
> avoid any really bad practical problems with them.
>
> On 25/01/2018 9:08 AM, Artem Dergachev wrote:
>> Handling C++ temporary object construction and destruction seems to
>> be the biggest cause of false positives on C++ code at the moment.
>> I'd be looking into this, even though for now i don't see the whole
>> scale of problem.
>>
>> == CFG, destructors, and ProgramPoints ==
>>
>> We should probably enable `-analyzer-config cfg-temporary-dtors=true`
>> by default soon. It is a fairly low-impact change because it only
>> alters the CFG but the analyzer rarely actually uses the new nodes.
>> Destructors for the most part are still evaluated conservatively,
>> with improper object regions. So it causes almost no changes in the
>> analyzer's positives for now, but it definitely opens up room for
>> further improvements.
>>
>> I'm observing a couple of problems with this mode at the moment,
>> namely the rich CFG destructor element hierarchy is not currently
>> complemented by an equally rich ProgramPoint hierarchy. This causes
>> the analysis to merge nodes which are not equivalent, for example two
>> implicit destructors of the same type (with the same function
>> declaration) may sometimes cause the ExplodedGraph to coil up and
>> stop analysis (lost coverage) because of having the same program
>> state at the erroneously-same program point. Because situations when
>> we can guarantee a change in the program state are pretty rare, we'd
>> have to produce more program point kinds to handle this correctly.
>>
>> CallEvent hierarchy is also very much affected in a similar manner -
>> because apparently we're constructing program points by looking at
>> CallEvents, so they'd need to carry all the information that's needed
>> to construct the pre-call/post-call program point.
>>
>> == Construction contexts ==
>>
>> We are correctly modeling "this" object region during
>> construction/destruction of variables with automatic storage
>> duration, fields and base classes, and on operator new() since
>> recently, as long as these aren't arrays of objects. It was not yet
>> implemented for other cases such as temporaries, initializer lists,
>> fields or C++17 base classes within aggregates, and pass-by-value
>> from/to functions (the latter being a slightly different problem than
>> temporaries).
>>
>> First of all, by "not yet implemented" i mean that instead of
>> constructing into (destroying) the correct object (in the correct
>> memory region), we come up with a "temporary region", which looks
>> exactly like a region of a valid C++ temporary but is only used for
>> communicating that it is not the right region. Then we look at the
>> region, see that it is a temporary, and avoid inlining constructors,
>> because it would make little sense when the region is not correct.
>> However, if we are to model temporaries, we need another way of
>> communicating our failure to find the correct region, which is being
>> addressed by https://reviews.llvm.org/D42457
>>
>> Also in the cases when the correct region is used, it is being
>> computed in a funky way: in order to figure out where do we construct
>> the object, we walk forward in the CFG (or from child to parent in
>> the AST) to find the next/parent statement that would accomodate the
>> newly constructed object. This means that the CFG, while perfectly
>> telling us what to do in what order (which we, unlike CodeGen, cannot
>> easily take from AST because we cannot afford recursive evaluation of
>> statements, mainly because of inlining), discards too much context to
>> be helpful in understanding how to do it.
>>
>> I tried to add the information about such "trigger statements" for
>> constructors into CFG and it is extremely helpful and easy to both
>> use and extend. This assumes adding a new sub-class of CFGElement for
>> constructors, which maintain a "construction context" - for now it's
>> just a trigger statement. For instance, in
>>
>>   class C { ... };
>>   void foo() {
>>     C c;
>>   }
>>
>> ...the trigger for constructor C() would be DeclStmt `C c`, and once
>> we know this we can immediately figure out that the construction
>> target is the region of variable `c`. Construction trigger is not
>> necessarily a statement - it may be a CXXCtorInitializer, which is an
>> AST node kind of its own. Additionally, when constructing aggregates
>> via initializer lists, we may have the same statement trigger
>> multiple constructors, eg. in
>>
>>   class C { public: C(int); ~C(); };
>>   struct S { C c1, c2, c3; };
>>   void foo() {
>>     S s { 1, 2, 3 };
>>   }
>>
>> ... we have three different constructors (actually six different
>> constructors if we include elidable copy constructors) for c1, c2, c3
>> (and lack of constructor for `s` because of the aggregate thing). It
>> would be more natural to declare that the specific field or index
>> would be a part of the CFG's construction context, as well as the
>> intermediate InitListExpr, so even in these simple cases the
>> construction context may get quite bulky. And this example is quite
>> popular on actual code - probably the second worst cause of false
>> positives after temporaries.
>>
>> For now i have no specific plan on what would construction context
>> for temporaries contain in the general case. I might not be able to
>> get the data structures right from the start. In any case, it might
>> be necessary to perform additional memory allocations for these CFG
>> elements (for analyzer's CFG only, so it wouldn't affect compilation
>> time or warnings).
>>
>> I believe that getting the correct target region in as many cases as
>> possible would be the main part of my work for the nearest future.
>> And i want to move most this work to CFG, while letting the analyzer
>> pick up the trigger statement from it and trust it as blindly as
>> possible.
>>
>> == Workflow ==
>>
>> When working on operator new, i tried hard to maintain a reasonable
>> history, making around 15 local rebases. It was not awesome because
>> it was hard for the reviewers to understand the context of the new
>> changes, and changes could have easily kicked in during rebases. A
>> few lessons learned here would be to commit more aggressively, i.e.
>> avoiding stockpiling a large history of patches (essentially a large
>> branch), which in turn would be possible through trying harder to
>> avoid unrelated hard-to-test core changes (as long as it doesn't
>> require weird workarounds) that aren't covered by a flag (such as
>> those evalCast fixes), in order to make sure reviewing take less
>> responsibility. It's fine if some parts would later be fixed
>> (assuming they would indeed be fixed), if it means making the
>> turnaround faster and the tail of patches shorter - that's also the
>> attitude i'd try to maintain when reviewing stuff myself.
>

_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: [analyzer] Temporaries.

Hans Wennborg via cfe-dev
While all three more or less work, a combination of the three -
temporary destructors, broken lifetime extension, and copy elision -
causes massive false positives at the moment. Consider:

      1    #include <memory>
      2
      3    void use(const char *);
      4
      5    void foo() {
      6      char *p = new char[10];
      7      std::unique_ptr<char []> x = std::unique_ptr<char[]>(p);
      8      use(p);
      9    }

This causes a use-after free warning, even though everything we ever
wanted was inlined. Here's the AST for line 7:

  DeclStmt 0x7fddb999d8a8 <line:7:3, col:58>
  `-VarDecl 0x7fddba8ad738 <col:3, col:57> col:28 x
'std::unique_ptr<char []>':'std::__1::unique_ptr<char [],
std::__1::default_delete<char []> >' cinit
    `-ExprWithCleanups 0x7fddb999d890 <col:32, col:57>
'std::unique_ptr<char []>':'std::__1::unique_ptr<char [],
std::__1::default_delete<char []> >'
      `-CXXConstructExpr 0x7fddb999d858 <col:32, col:57>
'std::unique_ptr<char []>':'std::__1::unique_ptr<char [],
std::__1::default_delete<char []> >' 'void (std::__1::unique_ptr<char
[], std::__1::default_delete<char []> > &&) noexcept' elidable
        `-MaterializeTemporaryExpr 0x7fddb999d840 <col:32, col:57>
'std::unique_ptr<char []>':'std::__1::unique_ptr<char [],
std::__1::default_delete<char []> >' xvalue
          `-CXXFunctionalCastExpr 0x7fddb999b7f0 <col:32, col:57>
'std::unique_ptr<char []>':'std::__1::unique_ptr<char [],
std::__1::default_delete<char []> >' functional cast to
std::unique_ptr<char []> <ConstructorConversion>
            `-CXXBindTemporaryExpr 0x7fddb999b7d0 <col:32, col:57>
'std::unique_ptr<char []>':'std::__1::unique_ptr<char [],
std::__1::default_delete<char []> >' (CXXTemporary 0x7fddb999b7c8)
              `-CXXConstructExpr 0x7fddb999b6a0 <col:32, col:57>
'std::unique_ptr<char []>':'std::__1::unique_ptr<char [],
std::__1::default_delete<char []> >' 'void (char *, typename
enable_if<__same_or_less_cv_qualified<char *, pointer>::value,
__nat>::type) noexcept'
                |-ImplicitCastExpr 0x7fddb999ad88 <col:56> 'char *'
<LValueToRValue>
                | `-DeclRefExpr 0x7fddba8ad958 <col:56> 'char *' lvalue
Var 0x7fddba8ad1d0 'p' 'char *'
                `-CXXDefaultArgExpr 0x7fddb999b680 <<invalid sloc>>
'typename enable_if<__same_or_less_cv_qualified<char *, pointer>::value,
__nat>::type':'std::__1::unique_ptr<char [],
std::__1::default_delete<char []> >::__nat'

So we're constructing a temporary unique_ptr, binding the temporary for
subsequent destruction, functional-casting it (no-op), materializing it
for elidable move-construction, doing elidable move-construction into
variable 'x', then destroying the original temporary.

During move-construction, we're erasing our pointer from the temporary
and transfer it into 'x'.

However, due to the previous MaterializeTemporaryExpr, which "is" "the"
"lifetime extension" ("through elidable move"), we have incorrectly
created a copy of the temporary. So during move-construction we've
erased our pointer in the copy of the temporary, but not in the original
temporary.

The destructor, however, is deleting the original correct temporary, not
the erroneous copy! And the original temporary still owns the pointer.

It's not possible for MaterializeTemporaryExpr to inform the destructor
that the address has changed because our MaterializeTemporaryExpr
doesn't know the old address that needs to be replaced.

Sounds like it's time to do something about lifetime extension.

On 14/02/2018 1:20 PM, Artem Dergachev wrote:

> More explanations on how the analyzer keeps making its way around the
> C++ AST.
>
> == Lifetime extension ==
>
> This is a brain dump of how (and how much) lifetime extension of
> temporary objects is currently broken in the static analyzert.
> Spoilers: not too much, it seems, but annoying nevertheless.
>
> Consider an example:
>
>      1    class C {
>      2    public:
>      3      C() {}
>      4      ~C() {}
>      5    };
>      6
>      7    void foo() {
>      8      const C &c = C();
>      9    }
>
> With the AST for the variable declaration:
>
>       DeclStmt 0x7fa5ac85cba0 <line:8:3, col:19>
>       `-VarDecl 0x7fa5ac85c878 <col:3, col:18> col:12 c 'const C &' cinit
>         `-ExprWithCleanups 0x7fa5ac85cb30 <col:16, col:18> 'const C'
> lvalue
>           `-MaterializeTemporaryExpr 0x7fa5ac85cb00 <col:16, col:18>
> 'const C' lvalue extended by Var 0x7fa5ac85c878 'c' 'const C &'
>             `-ImplicitCastExpr 0x7fa5ac85cae8 <col:16, col:18> 'const
> C' <NoOp>
>               `-CXXBindTemporaryExpr 0x7fa5ac85cac8 <col:16, col:18>
> 'C' (CXXTemporary 0x7fa5ac85cac0)
>                 `-CXXTemporaryObjectExpr 0x7fa5ac85ca88 <col:16,
> col:18> 'C' 'void ()'
>
> *here goes a periodic reminder that CXXTemporaryObjectExpr is a
> sub-class of CXXConstructExpr*
>
> Notice how MaterializeTemporaryExpr is the innermost expression (the
> first one in the order of execution) that is an lvalue. Essentially,
> you can think of it as the mythical "rvalue-to-lvalue" cast that takes
> in a C++ object rvalue and returns the this-value for that object.
> Because all C++ objects have a this-value that never changes
> throughout their lifetime, it is essentially their identity. Otherwise
> you can't call methods on them.
>
> MaterializeTemporaryExpr also contains information about the lifetime
> extension process: we needed the this-value in order to bind it to
> variable 'c'. You see that in the AST.
>
> In the analyzer, however, MaterializeTemporaryExpr does a different
> thing, as a temporary solution (no pun intended). It constructs a new
> temporary region out of thin air and binds the rvalue object to that
> temporary in the Store. The respective function in our code is called
> "createTemporaryRegionIfNeeded". It also has a separate purpose of
> converting rvalue sub-object adjustments into lvalue sub-object
> adjustments, which we wouldn't discuss this time.
>
> Now that we learned how to inline temporary constructors and
> destructors, it essentially means that the this-value in the
> constructor and in the destructor would be different. Because first we
> construct the object into temporary region R1, then we take
> lazyCompoundVal{R1} to represent the value of CXXTemporaryObjectExpr,
> then we materialize lazyCompoundVal{R1} to R2, then we bind R2 to
> variable 'c', then we call the automatic(!) destructor for 'c' which
> contains R2. To be clear, the region store at the time of destruction
> would be:
>
>   c: R2,
>   R2: lazyCompoundVal{R1}.
>
> It means that fields of the object would contain the correct values,
> there would be the correct number of destructors called (no temporary
> destructors, just one automatic destructor), but the identity of the
> object (this-value) would change in the process. Unless the object
> actually makes any decisions or does any manipulations that involve
> its this-value, the modeling should be correct. When the object starts
> to actively use its this-value in its inlined methods, the analysis
> would do wrong stuff. Additionally, it causes a mess in the checkers
> when they try to track objects by their this-values - i.e.
> IteratorChecker has a lot of additional code to work around the fact
> that the region for the object constantly changes.
>
> From the above it is clear that MaterializeTemporaryExpr should not
> construct any new regions, at least not in this case. We already have
> the correct region, namely R1, which should be re-used.
>
> It is tempting to take R1 directly from lazyCompoundVal{R1} - it
> already has memories about once being a value of R1. I'm not sure it's
> not going to work - it may work, at least i'm not ready to come up
> with a counterexample. But the meaning of LazyCompoundVal's parent
> region is different and coincides with what we want just accidentally.
> Namely, lazyCompoundVal{R1} is a value of an object that was bound to
> R1 in some particular moment of time in the past, without any
> explanation of when this moment of time was - but there's no
> indication if R1 is the region of the temporary we've just
> constructed, or a region of an unrelated object that used to have the
> same value back then. As we'd see later, MaterializeTemporaryExpr
> doesn't always contain a constructor within it - there are a lot of
> cases to cover, and if the trick doesn't work even once, it's going to
> be hard, so i'd probably not going to commit into maintaining this
> invariant. Though it might be plausible to modify add an SVal kind
> that does exactly what we mean here - i.e. a value that does indeed
> correspond to a specific C++ object identified by region. It might be
> a beautiful solution, but it may also fail miserably if tricky
> cornercases show up - so i'm not ready to commit to that. Also the
> correct way of dealing with such values (i.e. for how long are they
> relevant?) would be extremely difficult to explain to checker developers.
>
> The more straightforward approach here is to include
> MaterializeTemporaryExpr (hereinafter MTE) into the construction
> context. It means, if a temporary that we're about to construct would
> be lifetime-extended later, we'd rather know about that during
> construction, and maintain a map in the program state from MTE to
> their respective temporary regions that were used for representing the
> respective construction targets. Upon encountering the respective MTE
> we'd simply retrieve the implicit temporary storage for the value from
> the program state and declare that temporary region to be the value of
> the MTE. This would mimic the approach we have with
> CXXBindTemporaryExprs (hereinafter BTE) and their respective regions
> that allows temporary destructors to work - but this time it's going
> to be about MaterializeTemporaryExprs and automatic destructors. I
> imagine that on the checker side this can potentially be exposed via
> some sort of State->getTemporaryStorage(Expr) call, but i believe that
> generally this process should be as transparent to the checkers as
> possible.
>
> It sounds as if both of these maps could be eliminated by always
> making sure that the target temporary is constructed "with" the MTE
> (for lifetime-extended temproraries) or BTE (for temporaries that
> require destruction at the end of full-expression). In this case, with
> the help of construction context-assisted lookahead, we declare that
> the target of the construction is CXXTempObjectRegion(MTE, LC) or
> CXXTempObjectRegion(BTE, LC) respectively, rather than
> CXXTempObjectRegion(CXXConstructExpr). Then during evaluation of MTE
> or BTE we'd simply construct the same region with the expression we're
> currently evaluating, and it's automagically going to be the correct
> region. This approach, however, becomes confusing when we start
> dealing with elidable constructors (explained below). So for now i
> believe that it is quite irrelevant which expression is identifying
> the temporary region.
>
> == Elidable constructors ==
>
> While it doesn't sound like an immediately important task to implement
> copy elision in the analyzer, it may help with making some things
> easier. And it'd also make some reports fancier, as mentioned in
> https://reviews.llvm.org/D43144.
>
> Elidable copy-constructors can be explained as a form of lifetime
> extension. Instead of copying the temporary, they keep using the
> original value of the temporary, which in some pretty twisted sense
> means that they are lifetime-extending it to be able to use it. For
> example, if we modify our example by replacing the lifetime-extending
> reference variable with a value-type variable:
>
>      1    class C {
>      2    public:
>      3      C() {}
>      4      ~C() {}
>      5    };
>      6
>      7    void foo() {
>      8      C c = C();
>      9    }
>
> ...then we'd still have an MTE, even though lifetime extension would
> seem to be gone:
>
>       DeclStmt 0x7fb8f005afb8 <line:8:3, col:12>
>       `-VarDecl 0x7fb8f005ac50 <col:3, col:11> col:5 c 'C' cinit
>         `-ExprWithCleanups 0x7fb8f005afa0 <col:9, col:11> 'C'
>           `-CXXConstructExpr 0x7fb8f005af68 <col:9, col:11> 'C' 'void
> (const C &) noexcept' elidable
>             `-MaterializeTemporaryExpr 0x7fb8f005af00 <col:9, col:11>
> 'const C' lvalue
>               `-ImplicitCastExpr 0x7fb8f005aee8 <col:9, col:11> 'const
> C' <NoOp>
>                 `-CXXBindTemporaryExpr 0x7fb8f005aec8 <col:9, col:11>
> 'C' (CXXTemporary 0x7fb8f005aec0)
>                   `-CXXTemporaryObjectExpr 0x7fb8f005ae88 <col:9,
> col:11> 'C' 'void ()'
>
> In this case the MTE is expressing the fact that the temporary
> constructed via CXXTemporaryObjectExpr can be "lifetime-extended" (by
> actually merging it with the stack variable) rather than copied, if
> the CXXConstructExpr surrounding it would be chosen to be elided. The
> AST doesn't make the elision choice for us - but is compatible with
> both choices. The MTE essentially overrides the necessity of immediate
> destruction provided by the BTE, and lets the surrounding AST decide
> upon the lifetime of the object.
>
> Because the analyzer currently does not do copy elision, it will use
> the MTE only to compute the argument for the elidable
> copy-constructor, and then perform the copy-construction, and then
> destroy the original temporary at the end of the full-expression.
> Note, however, that in this case we need to properly support both the
> BTE (for the temporary destructor to work) and the MTE (for computing
> its value). We need to implement the MTE's ability to perform
> "rvalue-to-lvalue-cast" even if the temporary destruction is still
> necessary. For this reason, if we rely on constructing temporary
> regions with the correct BTEs or MTEs, at least one of these tasks
> becomes impossible to perform.
>
> If we were to support copy elision, then the CXXTemporaryObjectExpr
> constructor would go directly into the variable region. For the
> purposes of modeling, it'd mean that only CXXTemporaryObjectExpr would
> actually need to be modeled. But this would require additional coding
> in the construction context to be able to realize that the target is
> the variable while modeling the CXXTemporaryObjectExpr.
>
> For the sake of completeness, let's consider the ternary operator
> example:
>
>      1    class C {
>      2    public:
>      3      C(int) {}
>      4      ~C() {}
>      5    };
>      6
>      7    void foo(int coin) {
>      8      const C &c = coin ? C(1) : C(2);
>      9    }
>
> The respective AST would be:
>
>       DeclStmt 0x7fc1e20023e0 <line:8:3, col:34>
>       `-VarDecl 0x7fc1e2001dc8 <col:3, col:33> col:12 c 'const C &' cinit
>         `-ExprWithCleanups 0x7fc1e2002370 <col:16, col:33> 'const C'
> lvalue
>           `-MaterializeTemporaryExpr 0x7fc1e2002340 <col:16, col:33>
> 'const C' lvalue extended by Var 0x7fc1e2001dc8 'c' 'const C &'
>             `-ImplicitCastExpr 0x7fc1e2002328 <col:16, col:33> 'const
> C' <NoOp>
>               `-ConditionalOperator 0x7fc1e20022f8 <col:16, col:33> 'C'
>                 |-ImplicitCastExpr 0x7fc1e2002170 <col:16> 'bool'
> <IntegralToBoolean>
>                 | `-ImplicitCastExpr 0x7fc1e2002158 <col:16> 'int'
> <LValueToRValue>
>                 |   `-DeclRefExpr 0x7fc1e2001e28 <col:16> 'int' lvalue
> ParmVar 0x7fc1e2001c18 'coin' 'int'
>                 |-CXXBindTemporaryExpr 0x7fc1e2002248 <col:23, col:26>
> 'C' (CXXTemporary 0x7fc1e2002240)
>                 | `-CXXConstructExpr 0x7fc1e2002208 <col:23, col:26>
> 'C' 'void (const C &) noexcept' elidable
>                 |   `-MaterializeTemporaryExpr 0x7fc1e20021a0 <col:23,
> col:26> 'const C' lvalue
>                 |     `-ImplicitCastExpr 0x7fc1e2002188 <col:23,
> col:26> 'const C' <NoOp>
>                 |       `-CXXFunctionalCastExpr 0x7fc1e2002078
> <col:23, col:26> 'C' functional cast to class C <ConstructorConversion>
>                 |         `-CXXBindTemporaryExpr 0x7fc1e2002058
> <col:23, col:26> 'C' (CXXTemporary 0x7fc1e2002050)
>                 |           `-CXXConstructExpr 0x7fc1e2002018 <col:23,
> col:26> 'C' 'void (int)'
>                 |             `-IntegerLiteral 0x7fc1e2001e60 <col:25>
> 'int' 1
>                 `-CXXBindTemporaryExpr 0x7fc1e20022d8 <col:30, col:33>
> 'C' (CXXTemporary 0x7fc1e20022d0)
>                   `-CXXConstructExpr 0x7fc1e2002298 <col:30, col:33>
> 'C' 'void (const C &) noexcept' elidable
>                     `-MaterializeTemporaryExpr 0x7fc1e2002280 <col:30,
> col:33> 'const C' lvalue
>                       `-ImplicitCastExpr 0x7fc1e2002268 <col:30,
> col:33> 'const C' <NoOp>
>                         `-CXXFunctionalCastExpr 0x7fc1e2002130
> <col:30, col:33> 'C' functional cast to class C <ConstructorConversion>
>                           `-CXXBindTemporaryExpr 0x7fc1e2002110
> <col:30, col:33> 'C' (CXXTemporary 0x7fc1e2002108)
>                             `-CXXConstructExpr 0x7fc1e20020d0 <col:30,
> col:33> 'C' 'void (int)'
>                               `-IntegerLiteral 0x7fc1e20020b0 <col:32>
> 'int' 2
>
> Each branch contains two constructors: the temporary and the elidable
> copy. The temporaries are surrounded with their respective BTEs and
> copy-elision-kind MTEs, which indicates that they need to be either
> destroyed as temporaries, or, if copy elision is chosen, have their
> lifetime decided upon by the surrounding AST. The elidable copy
> constructors also, being temporaries, have their respective BTEs.
> Note, however, that there is only one MTE for both BTEs for the
> elidable constructors.
>
> So after the conditional operator is resolved (which is the first
> thing we need to do, according to the CFG), we'd go ahead and perform
> the constructors, and their trigger would be their respective BTE in
> the non-elide case, and the single top-level MTE in the elide case. In
> the non-elide case, copy constructors would be triggered by the
> top-level MTE.
>
> It means that, once again, copy elision would prevent us from handling
> both the BTE and the copy-elision-kind MTE in the single construction,
> allowing the "predictable target region" trick to work: when we need
> the temporary destructor, we construct directly into
> CXXTempObjectRegion of the BTE and it gets automatically picked up
> during destruction, and when we need the automatic destructor, we
> construct directly into CXXTempObjectRegion of the MTE and we can
> easily compute the value of the MTE. But when we don't do copy
> elision, we'd have to keep at least one of those in the program state
> map.
>
> == Return by value ==
>
> Returning C++ objects by value is actually very similar to
> constructing it. Consider:
>
>      1    class C {
>      2    public:
>      3      C() {}
>      4      ~C() {}
>      5    };
>      6
>      7    C bar() {
>      8      C c;
>      9      return c;
>     10    }
>     11
>     12    void foo() {
>     13      const C &c = bar();
>     14    }
>
> With the respective AST for DeclStmt in foo():
>
>       DeclStmt 0x7fe62c84f8e8 <line:13:3, col:21>
>       `-VarDecl 0x7fe62c84f6b8 <col:3, col:20> col:12 c 'const C &' cinit
>         `-ExprWithCleanups 0x7fe62c84f878 <col:16, col:20> 'const C'
> lvalue
>           `-MaterializeTemporaryExpr 0x7fe62c84f848 <col:16, col:20>
> 'const C' lvalue extended by Var 0x7fe62c84f6b8 'c' 'const C &'
>             `-ImplicitCastExpr 0x7fe62c84f830 <col:16, col:20> 'const
> C' <NoOp>
>               `-CXXBindTemporaryExpr 0x7fe62c84f810 <col:16, col:20>
> 'C' (CXXTemporary 0x7fe62c84f808)
>                 `-CallExpr 0x7fe62c84f7e0 <col:16, col:20> 'C'
>                   `-ImplicitCastExpr 0x7fe62c84f7c8 <col:16> 'C (*)()'
> <FunctionToPointerDecay>
>                     `-DeclRefExpr 0x7fe62c84f770 <col:16> 'C ()'
> lvalue Function 0x7fe62c84f190 'bar' 'C ()'
>
> And for the ReturnStmt in bar():
>
>       ReturnStmt 0x7fe62c84f5b0 <line:9:3, col:10>
>       `-CXXConstructExpr 0x7fe62c84f578 <col:10> 'C' 'void (const C &)
> noexcept' elidable
>         `-ImplicitCastExpr 0x7fe62c84f518 <col:10> 'const C' lvalue
> <NoOp>
>           `-DeclRefExpr 0x7fe62c84f4f0 <col:10> 'C' lvalue Var
> 0x7fe62c84f280 'c' 'C'
>
> Since https://reviews.llvm.org/D42875 we can already realize that the
> constructor in bar(), assuming that we're inlining bar() during
> analysis, would be constructed into something that is a return value
> of bar(). This allows us, by looking that the StackFrameContext's call
> site, to figure out that it is being constructed into the CallExpr in
> foo(). Now if only we knew that that the call site is a
> lifetime-extended temporary, i.e. if only we had a pointer to the
> foo()'s MTE at the CallExpr's CFG element, we'd be able to find the
> correct target region for construction: the CXXTempObjectRegion for
> the MTE in the StackFrameContext of foo(). So i'm proposing to add
> some sort of construction context to not only constructors, but also
> to functions that return objects, and then during construction perform
> the lookup in three easy steps:
>
>   1. in the callee's CFG from constructor to return statement,
>   2. through the location from the return statement to the call site,
>   3. then through the caller's CFG from the call site to the MTE.
>
> If the function is not inlined, we can still make use of the
> construction context to represent the return value as a
> LazyCompoundValue of the MTE's temporary. It would eliminate the need
> to replace the return value with another value while evaluating the
> MTE, and of course the need to re-bind the object to a different
> this-region.
>
> So i believe that this is a good way to eliminate the need for the
> "createTemporaryRegionIfNeeded" thing in the function calls as well.
>
>
> On 06/02/2018 1:41 PM, Artem Dergachev wrote:
>> A bit of an update.
>>
>> == Temporary destructors ==
>>
>> Adding some initial support for temporary destructors seems pretty
>> easy and straightforward at this point, given the awesome work done
>> by Manuel Klimek on our CFG a few years ago.
>>
>> 1. We already have the awesome CFGTemporaryDtor elements, which have
>> the backreference to the CXXBindTemporaryExpr for their temporaries.
>>
>> 2. In simple cases CXXBindTemporaryExprs have an immediate
>> constructor within them, and therefore we can provide the
>> CXXBindTemporaryExprs as the construction context's trigger
>> statements, and therefore have a reliable CXXTempObjectRegion for
>> constructors.
>>
>> 3. Then we already track the CXXBindTemporaryExprs for the active
>> temporaries in the program state. We can attach any constructor
>> information to them, such as the target region, if we need to
>> (probably we can reconstruct it by looking at the expression and the
>> location context, not sure if we want to).
>>
>> 4. So when we reach the CFGTemporaryDtor element, we can just lookup
>> all the info we need, and perform the destruction properly.
>>
>> 5. There's a bit of a liveness problem, because it seems that our
>> liveness analysis tends to throw away the temporary too early. I can
>> easily hack this problem away by marking all regions that correspond
>> to active temporaries as live. I'll see if there's a better solution.
>>
>> == CXXDefaultArgExpr problems ==
>>
>> There's a known problem with those. Consider:
>>
>>   void foo(const C &c = C()) {
>>   }
>>
>>   void bar() {
>>     foo();
>>     foo();
>>   }
>>
>> Each call of foo() contains a CXXDefaultArgExpr for c. The default
>> argument value C() is constructed before we enter foo() and destroyed
>> after we leave foo(). However, c's initializer, "= C()", is *not part
>> of the AST of bar()*. In particular, when foo() is called twice, the
>> initializer for the two calls is the same, only CXXDefaultArgExprs
>> are different. This screws a lot of invariants in the analyzer:
>> program points start coinciding (causing the analysis to loop and
>> cache out), Environment doesn't expect the same expression in the
>> same location context have two different values (suppose calls are
>> nested into each other), analysis taking wrong branches, and so on.
>>
>> Luckily, default-arg expressions that aren't zero integers or null
>> pointers are pretty rare. Still, we'd need to eventually think how to
>> avoid any really bad practical problems with them.
>>
>> On 25/01/2018 9:08 AM, Artem Dergachev wrote:
>>> Handling C++ temporary object construction and destruction seems to
>>> be the biggest cause of false positives on C++ code at the moment.
>>> I'd be looking into this, even though for now i don't see the whole
>>> scale of problem.
>>>
>>> == CFG, destructors, and ProgramPoints ==
>>>
>>> We should probably enable `-analyzer-config
>>> cfg-temporary-dtors=true` by default soon. It is a fairly low-impact
>>> change because it only alters the CFG but the analyzer rarely
>>> actually uses the new nodes. Destructors for the most part are still
>>> evaluated conservatively, with improper object regions. So it causes
>>> almost no changes in the analyzer's positives for now, but it
>>> definitely opens up room for further improvements.
>>>
>>> I'm observing a couple of problems with this mode at the moment,
>>> namely the rich CFG destructor element hierarchy is not currently
>>> complemented by an equally rich ProgramPoint hierarchy. This causes
>>> the analysis to merge nodes which are not equivalent, for example
>>> two implicit destructors of the same type (with the same function
>>> declaration) may sometimes cause the ExplodedGraph to coil up and
>>> stop analysis (lost coverage) because of having the same program
>>> state at the erroneously-same program point. Because situations when
>>> we can guarantee a change in the program state are pretty rare, we'd
>>> have to produce more program point kinds to handle this correctly.
>>>
>>> CallEvent hierarchy is also very much affected in a similar manner -
>>> because apparently we're constructing program points by looking at
>>> CallEvents, so they'd need to carry all the information that's
>>> needed to construct the pre-call/post-call program point.
>>>
>>> == Construction contexts ==
>>>
>>> We are correctly modeling "this" object region during
>>> construction/destruction of variables with automatic storage
>>> duration, fields and base classes, and on operator new() since
>>> recently, as long as these aren't arrays of objects. It was not yet
>>> implemented for other cases such as temporaries, initializer lists,
>>> fields or C++17 base classes within aggregates, and pass-by-value
>>> from/to functions (the latter being a slightly different problem
>>> than temporaries).
>>>
>>> First of all, by "not yet implemented" i mean that instead of
>>> constructing into (destroying) the correct object (in the correct
>>> memory region), we come up with a "temporary region", which looks
>>> exactly like a region of a valid C++ temporary but is only used for
>>> communicating that it is not the right region. Then we look at the
>>> region, see that it is a temporary, and avoid inlining constructors,
>>> because it would make little sense when the region is not correct.
>>> However, if we are to model temporaries, we need another way of
>>> communicating our failure to find the correct region, which is being
>>> addressed by https://reviews.llvm.org/D42457
>>>
>>> Also in the cases when the correct region is used, it is being
>>> computed in a funky way: in order to figure out where do we
>>> construct the object, we walk forward in the CFG (or from child to
>>> parent in the AST) to find the next/parent statement that would
>>> accomodate the newly constructed object. This means that the CFG,
>>> while perfectly telling us what to do in what order (which we,
>>> unlike CodeGen, cannot easily take from AST because we cannot afford
>>> recursive evaluation of statements, mainly because of inlining),
>>> discards too much context to be helpful in understanding how to do it.
>>>
>>> I tried to add the information about such "trigger statements" for
>>> constructors into CFG and it is extremely helpful and easy to both
>>> use and extend. This assumes adding a new sub-class of CFGElement
>>> for constructors, which maintain a "construction context" - for now
>>> it's just a trigger statement. For instance, in
>>>
>>>   class C { ... };
>>>   void foo() {
>>>     C c;
>>>   }
>>>
>>> ...the trigger for constructor C() would be DeclStmt `C c`, and once
>>> we know this we can immediately figure out that the construction
>>> target is the region of variable `c`. Construction trigger is not
>>> necessarily a statement - it may be a CXXCtorInitializer, which is
>>> an AST node kind of its own. Additionally, when constructing
>>> aggregates via initializer lists, we may have the same statement
>>> trigger multiple constructors, eg. in
>>>
>>>   class C { public: C(int); ~C(); };
>>>   struct S { C c1, c2, c3; };
>>>   void foo() {
>>>     S s { 1, 2, 3 };
>>>   }
>>>
>>> ... we have three different constructors (actually six different
>>> constructors if we include elidable copy constructors) for c1, c2,
>>> c3 (and lack of constructor for `s` because of the aggregate thing).
>>> It would be more natural to declare that the specific field or index
>>> would be a part of the CFG's construction context, as well as the
>>> intermediate InitListExpr, so even in these simple cases the
>>> construction context may get quite bulky. And this example is quite
>>> popular on actual code - probably the second worst cause of false
>>> positives after temporaries.
>>>
>>> For now i have no specific plan on what would construction context
>>> for temporaries contain in the general case. I might not be able to
>>> get the data structures right from the start. In any case, it might
>>> be necessary to perform additional memory allocations for these CFG
>>> elements (for analyzer's CFG only, so it wouldn't affect compilation
>>> time or warnings).
>>>
>>> I believe that getting the correct target region in as many cases as
>>> possible would be the main part of my work for the nearest future.
>>> And i want to move most this work to CFG, while letting the analyzer
>>> pick up the trigger statement from it and trust it as blindly as
>>> possible.
>>>
>>> == Workflow ==
>>>
>>> When working on operator new, i tried hard to maintain a reasonable
>>> history, making around 15 local rebases. It was not awesome because
>>> it was hard for the reviewers to understand the context of the new
>>> changes, and changes could have easily kicked in during rebases. A
>>> few lessons learned here would be to commit more aggressively, i.e.
>>> avoiding stockpiling a large history of patches (essentially a large
>>> branch), which in turn would be possible through trying harder to
>>> avoid unrelated hard-to-test core changes (as long as it doesn't
>>> require weird workarounds) that aren't covered by a flag (such as
>>> those evalCast fixes), in order to make sure reviewing take less
>>> responsibility. It's fine if some parts would later be fixed
>>> (assuming they would indeed be fixed), if it means making the
>>> turnaround faster and the tail of patches shorter - that's also the
>>> attitude i'd try to maintain when reviewing stuff myself.
>>
>

_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: [analyzer] Temporaries.

Hans Wennborg via cfe-dev
In reply to this post by Hans Wennborg via cfe-dev
Hello Artem,

Thank you for working on this and sharing the status.
Do we expect coverage changes after allowing destructors to be inlined?

25.01.2018 20:08, Artem Dergachev via cfe-dev пишет:

> Handling C++ temporary object construction and destruction seems to be
> the biggest cause of false positives on C++ code at the moment. I'd be
> looking into this, even though for now i don't see the whole scale of
> problem.
>
> == CFG, destructors, and ProgramPoints ==
>
> We should probably enable `-analyzer-config cfg-temporary-dtors=true`
> by default soon. It is a fairly low-impact change because it only
> alters the CFG but the analyzer rarely actually uses the new nodes.
> Destructors for the most part are still evaluated conservatively, with
> improper object regions. So it causes almost no changes in the
> analyzer's positives for now, but it definitely opens up room for
> further improvements.
>
> I'm observing a couple of problems with this mode at the moment,
> namely the rich CFG destructor element hierarchy is not currently
> complemented by an equally rich ProgramPoint hierarchy. This causes
> the analysis to merge nodes which are not equivalent, for example two
> implicit destructors of the same type (with the same function
> declaration) may sometimes cause the ExplodedGraph to coil up and stop
> analysis (lost coverage) because of having the same program state at
> the erroneously-same program point. Because situations when we can
> guarantee a change in the program state are pretty rare, we'd have to
> produce more program point kinds to handle this correctly.
>
> CallEvent hierarchy is also very much affected in a similar manner -
> because apparently we're constructing program points by looking at
> CallEvents, so they'd need to carry all the information that's needed
> to construct the pre-call/post-call program point.
>
> == Construction contexts ==
>
> We are correctly modeling "this" object region during
> construction/destruction of variables with automatic storage duration,
> fields and base classes, and on operator new() since recently, as long
> as these aren't arrays of objects. It was not yet implemented for
> other cases such as temporaries, initializer lists, fields or C++17
> base classes within aggregates, and pass-by-value from/to functions
> (the latter being a slightly different problem than temporaries).
>
> First of all, by "not yet implemented" i mean that instead of
> constructing into (destroying) the correct object (in the correct
> memory region), we come up with a "temporary region", which looks
> exactly like a region of a valid C++ temporary but is only used for
> communicating that it is not the right region. Then we look at the
> region, see that it is a temporary, and avoid inlining constructors,
> because it would make little sense when the region is not correct.
> However, if we are to model temporaries, we need another way of
> communicating our failure to find the correct region, which is being
> addressed by https://reviews.llvm.org/D42457
>
> Also in the cases when the correct region is used, it is being
> computed in a funky way: in order to figure out where do we construct
> the object, we walk forward in the CFG (or from child to parent in the
> AST) to find the next/parent statement that would accomodate the newly
> constructed object. This means that the CFG, while perfectly telling
> us what to do in what order (which we, unlike CodeGen, cannot easily
> take from AST because we cannot afford recursive evaluation of
> statements, mainly because of inlining), discards too much context to
> be helpful in understanding how to do it.
>
> I tried to add the information about such "trigger statements" for
> constructors into CFG and it is extremely helpful and easy to both use
> and extend. This assumes adding a new sub-class of CFGElement for
> constructors, which maintain a "construction context" - for now it's
> just a trigger statement. For instance, in
>
>   class C { ... };
>   void foo() {
>     C c;
>   }
>
> ...the trigger for constructor C() would be DeclStmt `C c`, and once
> we know this we can immediately figure out that the construction
> target is the region of variable `c`. Construction trigger is not
> necessarily a statement - it may be a CXXCtorInitializer, which is an
> AST node kind of its own. Additionally, when constructing aggregates
> via initializer lists, we may have the same statement trigger multiple
> constructors, eg. in
>
>   class C { public: C(int); ~C(); };
>   struct S { C c1, c2, c3; };
>   void foo() {
>     S s { 1, 2, 3 };
>   }
>
> ... we have three different constructors (actually six different
> constructors if we include elidable copy constructors) for c1, c2, c3
> (and lack of constructor for `s` because of the aggregate thing). It
> would be more natural to declare that the specific field or index
> would be a part of the CFG's construction context, as well as the
> intermediate InitListExpr, so even in these simple cases the
> construction context may get quite bulky. And this example is quite
> popular on actual code - probably the second worst cause of false
> positives after temporaries.
>
> For now i have no specific plan on what would construction context for
> temporaries contain in the general case. I might not be able to get
> the data structures right from the start. In any case, it might be
> necessary to perform additional memory allocations for these CFG
> elements (for analyzer's CFG only, so it wouldn't affect compilation
> time or warnings).
>
> I believe that getting the correct target region in as many cases as
> possible would be the main part of my work for the nearest future. And
> i want to move most this work to CFG, while letting the analyzer pick
> up the trigger statement from it and trust it as blindly as possible.
>
> == Workflow ==
>
> When working on operator new, i tried hard to maintain a reasonable
> history, making around 15 local rebases. It was not awesome because it
> was hard for the reviewers to understand the context of the new
> changes, and changes could have easily kicked in during rebases. A few
> lessons learned here would be to commit more aggressively, i.e.
> avoiding stockpiling a large history of patches (essentially a large
> branch), which in turn would be possible through trying harder to
> avoid unrelated hard-to-test core changes (as long as it doesn't
> require weird workarounds) that aren't covered by a flag (such as
> those evalCast fixes), in order to make sure reviewing take less
> responsibility. It's fine if some parts would later be fixed (assuming
> they would indeed be fixed), if it means making the turnaround faster
> and the tail of patches shorter - that's also the attitude i'd try to
> maintain when reviewing stuff myself.
> _______________________________________________
> cfe-dev mailing list
> [hidden email]
> http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev


--
Best regards,
Aleksei Sidorin,
SRR, Samsung Electronics

_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: [analyzer] Temporaries.

Hans Wennborg via cfe-dev
For now i'm not seeing much coverage increase, and i'm not aiming for
that, though i've already seen a couple of neat temporary-specific new
true positives.

We avoid the gtest noreturn destructor sink mentioned in
https://reviews.llvm.org/D42779 but there's not much of these in regular
code.

Apart from that, i'm expecting a typical skew in coverage due to more
aggressive inlining, but that's it.

For now it's hard to understand coverage change because there are quite
a few new false positives hanging around, similar to
http://lists.llvm.org/pipermail/cfe-dev/2018-February/056909.html


On 19/02/2018 1:51 AM, Aleksei Sidorin wrote:

> Hello Artem,
>
> Thank you for working on this and sharing the status.
> Do we expect coverage changes after allowing destructors to be inlined?
>
> 25.01.2018 20:08, Artem Dergachev via cfe-dev пишет:
>> Handling C++ temporary object construction and destruction seems to
>> be the biggest cause of false positives on C++ code at the moment.
>> I'd be looking into this, even though for now i don't see the whole
>> scale of problem.
>>
>> == CFG, destructors, and ProgramPoints ==
>>
>> We should probably enable `-analyzer-config cfg-temporary-dtors=true`
>> by default soon. It is a fairly low-impact change because it only
>> alters the CFG but the analyzer rarely actually uses the new nodes.
>> Destructors for the most part are still evaluated conservatively,
>> with improper object regions. So it causes almost no changes in the
>> analyzer's positives for now, but it definitely opens up room for
>> further improvements.
>>
>> I'm observing a couple of problems with this mode at the moment,
>> namely the rich CFG destructor element hierarchy is not currently
>> complemented by an equally rich ProgramPoint hierarchy. This causes
>> the analysis to merge nodes which are not equivalent, for example two
>> implicit destructors of the same type (with the same function
>> declaration) may sometimes cause the ExplodedGraph to coil up and
>> stop analysis (lost coverage) because of having the same program
>> state at the erroneously-same program point. Because situations when
>> we can guarantee a change in the program state are pretty rare, we'd
>> have to produce more program point kinds to handle this correctly.
>>
>> CallEvent hierarchy is also very much affected in a similar manner -
>> because apparently we're constructing program points by looking at
>> CallEvents, so they'd need to carry all the information that's needed
>> to construct the pre-call/post-call program point.
>>
>> == Construction contexts ==
>>
>> We are correctly modeling "this" object region during
>> construction/destruction of variables with automatic storage
>> duration, fields and base classes, and on operator new() since
>> recently, as long as these aren't arrays of objects. It was not yet
>> implemented for other cases such as temporaries, initializer lists,
>> fields or C++17 base classes within aggregates, and pass-by-value
>> from/to functions (the latter being a slightly different problem than
>> temporaries).
>>
>> First of all, by "not yet implemented" i mean that instead of
>> constructing into (destroying) the correct object (in the correct
>> memory region), we come up with a "temporary region", which looks
>> exactly like a region of a valid C++ temporary but is only used for
>> communicating that it is not the right region. Then we look at the
>> region, see that it is a temporary, and avoid inlining constructors,
>> because it would make little sense when the region is not correct.
>> However, if we are to model temporaries, we need another way of
>> communicating our failure to find the correct region, which is being
>> addressed by https://reviews.llvm.org/D42457
>>
>> Also in the cases when the correct region is used, it is being
>> computed in a funky way: in order to figure out where do we construct
>> the object, we walk forward in the CFG (or from child to parent in
>> the AST) to find the next/parent statement that would accomodate the
>> newly constructed object. This means that the CFG, while perfectly
>> telling us what to do in what order (which we, unlike CodeGen, cannot
>> easily take from AST because we cannot afford recursive evaluation of
>> statements, mainly because of inlining), discards too much context to
>> be helpful in understanding how to do it.
>>
>> I tried to add the information about such "trigger statements" for
>> constructors into CFG and it is extremely helpful and easy to both
>> use and extend. This assumes adding a new sub-class of CFGElement for
>> constructors, which maintain a "construction context" - for now it's
>> just a trigger statement. For instance, in
>>
>>   class C { ... };
>>   void foo() {
>>     C c;
>>   }
>>
>> ...the trigger for constructor C() would be DeclStmt `C c`, and once
>> we know this we can immediately figure out that the construction
>> target is the region of variable `c`. Construction trigger is not
>> necessarily a statement - it may be a CXXCtorInitializer, which is an
>> AST node kind of its own. Additionally, when constructing aggregates
>> via initializer lists, we may have the same statement trigger
>> multiple constructors, eg. in
>>
>>   class C { public: C(int); ~C(); };
>>   struct S { C c1, c2, c3; };
>>   void foo() {
>>     S s { 1, 2, 3 };
>>   }
>>
>> ... we have three different constructors (actually six different
>> constructors if we include elidable copy constructors) for c1, c2, c3
>> (and lack of constructor for `s` because of the aggregate thing). It
>> would be more natural to declare that the specific field or index
>> would be a part of the CFG's construction context, as well as the
>> intermediate InitListExpr, so even in these simple cases the
>> construction context may get quite bulky. And this example is quite
>> popular on actual code - probably the second worst cause of false
>> positives after temporaries.
>>
>> For now i have no specific plan on what would construction context
>> for temporaries contain in the general case. I might not be able to
>> get the data structures right from the start. In any case, it might
>> be necessary to perform additional memory allocations for these CFG
>> elements (for analyzer's CFG only, so it wouldn't affect compilation
>> time or warnings).
>>
>> I believe that getting the correct target region in as many cases as
>> possible would be the main part of my work for the nearest future.
>> And i want to move most this work to CFG, while letting the analyzer
>> pick up the trigger statement from it and trust it as blindly as
>> possible.
>>
>> == Workflow ==
>>
>> When working on operator new, i tried hard to maintain a reasonable
>> history, making around 15 local rebases. It was not awesome because
>> it was hard for the reviewers to understand the context of the new
>> changes, and changes could have easily kicked in during rebases. A
>> few lessons learned here would be to commit more aggressively, i.e.
>> avoiding stockpiling a large history of patches (essentially a large
>> branch), which in turn would be possible through trying harder to
>> avoid unrelated hard-to-test core changes (as long as it doesn't
>> require weird workarounds) that aren't covered by a flag (such as
>> those evalCast fixes), in order to make sure reviewing take less
>> responsibility. It's fine if some parts would later be fixed
>> (assuming they would indeed be fixed), if it means making the
>> turnaround faster and the tail of patches shorter - that's also the
>> attitude i'd try to maintain when reviewing stuff myself.
>> _______________________________________________
>> cfe-dev mailing list
>> [hidden email]
>> http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
>
>

_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: [analyzer] Temporaries.

Hans Wennborg via cfe-dev
A bit of an update. Previous messages for easier navigation through this
thread:

http://lists.llvm.org/pipermail/cfe-dev/2018-January/056691.html
http://lists.llvm.org/pipermail/cfe-dev/2018-February/056813.html
http://lists.llvm.org/pipermail/cfe-dev/2018-February/056898.html
http://lists.llvm.org/pipermail/cfe-dev/2018-February/056909.html
http://lists.llvm.org/pipermail/cfe-dev/2018-February/056929.html

== Overall status ==

Previous changes had minimal effects on the false positives i observed.
However, once return-by-value and construction-conversion support has
landed, improved modeling has finally yielded significant results,
fixing at least 150 false positives (around 40% of all positives) on a
few sub-projects of WebKit (incl. WebCore, JavaScriptCore).

Large chunks of the remaining false positives are related to brace
initialization constructors which i'll try to support at least in simple
cases (eg. a single layer of braces).

Many of the remaining reports are hard to understand - it seems that
trackNullOrUndefValue isn't always doing a good job. Other reports are
over-saturated with inlined temporary destructors: path pruning may be
working incorrectly.

On other projects i've seen interesting bug reports against code that
works incorrectly when copy elision isn't happening (of a poorly
implemented class that performs memory management). We're capable of
finding such bugs because we don't model copy elision yet. Such code is
not portable, but many users that use just one compiler can afford
relying on its implementation details, and copy elision is usually
supported by most major compilers. These reports would probably go away
because i'd like to model copy elision anyway because it's generally a
good thing: it improves analyzer performance and reduces path lengths.
And we'd still catch these bugs when non-elidable copies will be made.

These results are with temporary destructor inlining turned on. I'm
holding off on destructor inlining for now because i'm seeing false
positives on other projects, even though the reference counting
suppression is working fairly well.

Lack of default argument support is still causing a small but noticeable
coverage drop. The CFG for this syntax seems usable but i guess full
support would require introducing a new LocationContext sub-class.
Binary conditional operators are still not supported (even in CFG), but
it doesn't seem to cause many problems.

== C++17 problems ==

 > http://en.cppreference.com/w/cpp/language/copy_elision
 > (since C++17)
 > Under the following circumstances, the compilers are REQUIRED to omit
the copy- and move- construction of class objects even if the copy/move
constructor and the destructor have observable side-effects. They need
not be present or accessible, as the language rules ensure that no
copy/move operation takes place, even conceptually:
 > In initialization, if the initializer expression is a prvalue and the
cv-unqualified version of the source type is the same class as the class
of the destination, the initializer expression is used to initialize the
destination object...
 > In a function call, if the operand of a return statement is a prvalue
and the return type of the function is the same as the type of that
prvalue...

This is going to be fun to support. Specifically, this means that
neither initialization 'C c = C();' nor return-statement 'return C()'
(where 'C()' may as well be replaced with a function call of type 'C')
contains an elidable copy in the AST anymore, but only a single
constructor of variable 'c' (or the returned-to object) - probably with
an intermediate CXXBindTemporaryExpr if the class has a non-trivial
destructor. A few consequences of this change:

* For now the CFG itself is broken in this case because it includes a
temporary destructor that shouldn't be there.

* The construction context for a function that returns an object by
value may now be not only a temporary object context, but also a simple
variable context or a returned value context - we'll need to handle
these cases.

* Liveness does not work correctly - previously it was relying on
CXXBindTemporaryExpr or MaterializeTemporaryExpr but now these aren't
guaranteed to even exist, so by the time we reach 'c' from 'C()' we may
already destroy bindings to the not-yet-alive variable 'c' we've added
in the constructor. This is especially obvious for the conditional
operator case, i.e. 'C c = x ? C(1) : C(2);' - in this case in C++17
there is just one constructor happening on every particular path.

* Returned values may now chain together - the target object of a
constructor that's called as part of the return statement may be
multiple stack frames above the constructor call, which we'd need to
unwind recursively.

For now i'll disable temporary- and returned-value- construction
contexts in C++17.
_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: [analyzer] Temporaries.

Hans Wennborg via cfe-dev
== Copy elision ==

= Why? =

I've underestimated the importance of implementing copy elision at first.

Eliding copies changes observable behavior of the program if the
copy/move constructor has side effects. Whether to elide creation of a
temporary object in certain operations is up to implementation, but most
implementations currently support and prefer copy elision, so if we
don't do the same in the analyzer we'd be analyzing a different program,
and users who don't care about portability may become grumpy because
they are sure that copy elision is happening.

Additionally, copy elision makes paths longer - including the number of
diagnostic pieces - which makes reports harder to understand and
exhausts the analyzer's budget faster.

= How? =

Consider an example:

      1    class C {
      2    public:
      3      C(int, int);
      4      C(const C &);
      5      ~C();
      6    };
      7
      8    void foo() {
      9      C c = C(123, 456);
     10    }

The respective AST:

       DeclStmt 0x7fe1d3001ed8 <line:9:3, col:20>
       `-VarDecl 0x7fe1d3001d08 <col:3, col:19> col:5 c 'C' cinit
         `-ExprWithCleanups 0x7fe1d3001ec0 <col:9, col:19> 'C'
           `-CXXConstructExpr 0x7fe1d3001e88 <col:9, col:19> 'C' 'void
(const C &)' elidable
             `-MaterializeTemporaryExpr 0x7fe1d3001e70 <col:9, col:19>
'const C' lvalue
               `-ImplicitCastExpr 0x7fe1d3001e58 <col:9, col:19> 'const
C' <NoOp>
                 `-CXXBindTemporaryExpr 0x7fe1d3001e38 <col:9, col:19>
'C' (CXXTemporary 0x7fe1d3001e30)
                   `-CXXTemporaryObjectExpr 0x7fe1d3001db8 <col:9,
col:19> 'C' 'void (int, int)'
                     |-IntegerLiteral 0x7fe1d3001d78 <col:11> 'int' 123
                     `-IntegerLiteral 0x7fe1d3001d98 <col:16> 'int' 456

And the CFG:

[B1]
    1: 123
    2: 456
    3: C([B1.1], [B1.2]) (CXXConstructExpr, [B1.4], [B1.6], class C)
    4: [B1.3] (BindTemporary)
    5: [B1.4] (ImplicitCastExpr, NoOp, const class C)
    6: [B1.5] (MaterializeTemporaryExpr)
    7: [B1.6] (CXXConstructExpr, [B1.8], class C)
    8: C c = C(123, 456);
    9: ~C() (Temporary object destructor)
   10: [B1.8].~C() (Implicit destructor)

This explains pretty well what we should do if we don't do copy elision:
we construct a temporary on B1.3 that's destroyed on B1.9 after being
materialized into an lvalue that's referenced by the copy-constructor
parameter; the copy-constructor will copy the object into the actual
variable.

Now, if we are to elide the copy constructor, the original constructor
C(123, 456) should construct the variable directly, and all statements
in between (B1.4, B1.5, B1.6, B1.7) and the destructor (B1.9) turn into
no-op.

I can imagine two ways of implementing such behavior:

(i). Completely remove elided elements B1.4, B1.5, B1.6, B1.7, B1.9 from
the CFG.
(ii). Keep CFG roughly the same but model elided elements as no-op in
the analyzer.

I believe that approach (ii) is ultimately better, even though (i)
sounds very tempting.

Approach (i) assumes that the modified CFG would kinda look like this:

[B1]
    1: 123
    2: 456
    3: C([B1.1], [B1.2]) (CXXConstructExpr, [B1.4], class C)
    4: C c = C(123, 456);
    5: [B1.4].~C() (Implicit destructor)

Our CFGConstructor element [B1.3] will essentially be frankensteined
from *inner* CXXTemporaryObjectExpr 0x7fe1d3001db8 (it's printed as
CXXConstructExpr in those CFG dumps) and the construction context of the
*outer* copy-constructor CXXConstructExpr 0x7fe1d3001e88.

This CFG looks pretty good on its own. It's almost indistinguishable
from the CFG for 'C c(123, 456)' and contains all that's needed to
properly initialize 'c'.

However the more i think about it, the more it seems to violate the
principle of least astonishment. For instance,
getSVal(DeclStmt->getSingleDecl()->getInit(), LC) would yield UnknownVal
because the constructor that has initialized the variable is different
from the one that's present in the initializer of the variable. The code
to obtain the "actual" initializer expression may be very complicated
because initializers can be quite complex (imagine a ?: operator; the
code for extracting the actual initializer will essentially duplicate
the code for finding construction contexts).

Essentially, all of the expressions between the DeclStmt and the
CXXTemporaryObjectExpr will never be set in the Environment and would be
unknown. Any user (imagine a checker) who will try to understand what is
going on in the current program point by exploring values of expressions
will fail here.

We are going to evaluate our DeclStmt without evaluating its immediate
sub-expressions. Why would the sub-sub-sub-sub-sub-expression that we
need to evaluate the DeclStmt be still kept alive in the Environment?

If we try to make checkers' life easier by setting values in the
Environment anyway for expressions that aren't present in the CFG, how
would liveness analysis know when to garbage-collect them given this
analysis is also CFG-based?

In fact I'm quite scared to imagine how our liveness analysis would
react when he realizes that there are a lot of expressions right in the
middle of a feasible path that are completely omitted from the CFG. I
guess we are omitting some dead paths from the CFG, but omitting
expressions in the middle of a statement will almost certainly make
liveness analysis more complicated.

Long story short, approach (i) violates a large amount of very basic and
intuitive invariants that we've so far maintained. Which is scary and
will make further development harder, even if we manage to make it work.

Approach (ii) is much more in the spirit of C++ standard
[class.copy.elision]:

 > "the implementation treats the source and target of the omitted
copy/move operation as simply two different ways of referring to the
same object".

Essentially, copy elision is an aliasing relationship between the stack
variable 'c' and the temporary object within its initializer. This makes
perfect sense in the CodeGen where both of these are just some stack
addresses. In analyzer terms, we declare that the CXXTempObjectRegion
for our CXXTemporaryObjectExpr and the VarRegion for our variable 'c'
are the same region. Because we don't have aliasing / renaming support
in the analyzer, we take the route of picking our regions correctly from
the start (that's, in some sense, the whole point of this construction
context hassle! - avoiding the need to rename regions later - which
would have probably been the right thing to do even if we could rename
regions). It leaves us with the following values for the expressions in
the Environment:

CXXTemporaryObjectExpr -> lazyCompoundVal{VarRegion 'c', Store after
construction}
CXXBindTemporaryExpr -> lazyCompoundVal{VarRegion 'c', Store after
construction}
MaterializeTemporaryExpr -> c
CXXConstructExpr -> lazyCompoundVal{VarRegion 'c', Store after construction}

Only CXXTemporaryObjectExpr will be actually modeled (hopefully by
inlining the constructor), with VarRegion 'c' acting as this-argument.

This leaves us with CXXConstructExpr that constructs into its own source
argument, which is exactly what the standard expects from us, even if
it's a bit amusing. It would not construct anything, of course, just
bind the value. It is questionable whether we need a checker callback
for the elided constructor (and if we do, which ones specifically).

CFG needs to be extended to add more context to the
CXXTemporaryObjectExpr in order to execute approach (ii) correctly. We
still need access to the CXXConstructExpr's construction context in
order to perform the very first construction, so i guess that the
construction context for CXXTemporaryObjectExpr would be a combination
of both. Note that there may be more than one elided copy constructor
(eg. there are two if the initializer is a ?: operator - and, well,
there may be multiple nested ?: operators).

Additionally, when we model elided expressions, we need to know that
they are elided by looking at them. We may add this information to their
CFG elements (this, again, looks tempting, but requires more CFG element
kinds) or mark expressions as elided in the program state (which we can
easily do because they are already mentioned in one of the construction
contexts).
_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: [analyzer] Temporaries.

Hans Wennborg via cfe-dev
== Errata ==

In the previous message i wrote:

 > copy elision makes paths longer

I meant lack of copy elision><


== C++17, Functional casts, Liveness ==

I wanted to share this example to document a certain bug we seem to
currently have with our liveness analysis, in order to get back to it
later and also to justify how careful we should be.

A naive attempt to support C++17 mandatory copy elision for variable and
constructor initializers (return values are a bit more tricky) would be
to model C++17-specific construction contexts added in
https://reviews.llvm.org/D44597 and https://reviews.llvm.org/D44763 
similarly to their "simple" counterparts.

This approach fails, however, in a fairly funny manner. Consider an example:

```
class C1 {
   int x;
public:
   C1(int x): x(x) {}
   int getX() const { return x; }
   ~C1();
};

class C2 {
   int x;
   int y;
public:
   C2(int x, int y): x(x), y(y) {}
   int getX() const { return x; }
   int getY() const { return y; }
   ~C2();
};

void foo(int coin) {
   C1 c1 = coin ? C1(1) : C1(2);
   c1.getX();
   C2 c2 = coin ? C2(3, 4) : C2(5, 6);
   c2.getX();
}
```

In this example C1 is a wrapper around a single integer and C2 is a
wrapper around a pair of integers; there are no other differences
between these two classes. However, if we attempt to treat
CXX17ElidedCopyConstructionContext and SimpleVariableConstructionContext
similarly in ExprEngine::getRegionForConstructedObject(), we suddenly
get the following warning:

$ clang -cc1 -analyze -analyzer-checker core test.cpp -std=c++17
test.cpp:14:22: warning: Undefined or garbage value returned to caller
   int getX() const { return x; }
                      ^~~~~~~~
1 warning generated.

The warning appears for C2 but not for C1. The warning is a false
positive that appears because construction results were removed from the
Store because variable 'c2' is not yet live when the construction
happens. However, variable 'c1' is live when its construction happens.

It is, emm, uhm, moderately easy to notice that the AST for constructors
of C1 and C2 on ternary operator branches are completely different:
C1(1) is a functional cast from integer 1 to class C1, while C2 is a
normal temporary object expression.

Indeed, here's the AST for c1:

```
     |-DeclStmt 0x7ff92c002570 <line:20:3, col:31>
     | `-VarDecl 0x7ff92c002100 <col:3, col:30> col:6 used c1 'C1' cinit
     |   `-ExprWithCleanups 0x7ff92c002558 <col:11, col:30> 'C1'
     |     `-ConditionalOperator 0x7ff92c002528 <col:11, col:30> 'C1'
     |       |-ImplicitCastExpr 0x7ff92c002510 <col:11> 'bool'
<IntegralToBoolean>
     |       | `-ImplicitCastExpr 0x7ff92c0024f8 <col:11> 'int'
<LValueToRValue>
     |       |   `-DeclRefExpr 0x7ff92c002160 <col:11> 'int' lvalue
ParmVar 0x7ff92c001f80 'coin' 'int'
     |       |-CXXFunctionalCastExpr 0x7ff92c002418 <col:18, col:22>
'C1' functional cast to class C1 <ConstructorConversion>
     |       | `-CXXBindTemporaryExpr 0x7ff92c0023f8 <col:18, col:22>
'C1' (CXXTemporary 0x7ff92c0023f0)
     |       |   `-CXXConstructExpr 0x7ff92c002388 <col:18, col:22> 'C1'
'void (int)'
     |       |     `-IntegerLiteral 0x7ff92c002198 <col:21> 'int' 1
     |       `-CXXFunctionalCastExpr 0x7ff92c0024d0 <col:26, col:30>
'C1' functional cast to class C1 <ConstructorConversion>
     |         `-CXXBindTemporaryExpr 0x7ff92c0024b0 <col:26, col:30>
'C1' (CXXTemporary 0x7ff92c0024a8)
     |           `-CXXConstructExpr 0x7ff92c002470 <col:26, col:30> 'C1'
'void (int)'
     |             `-IntegerLiteral 0x7ff92c002450 <col:29> 'int' 2
```

... and here's the AST for c2:

```
     |-DeclStmt 0x7ff92c002b10 <line:22:3, col:37>
     | `-VarDecl 0x7ff92c0026c8 <col:3, col:36> col:6 used c2 'C2' cinit
     |   `-ExprWithCleanups 0x7ff92c002af8 <col:11, col:36> 'C2'
     |     `-ConditionalOperator 0x7ff92c002ac8 <col:11, col:36> 'C2'
     |       |-ImplicitCastExpr 0x7ff92c002ab0 <col:11> 'bool'
<IntegralToBoolean>
     |       | `-ImplicitCastExpr 0x7ff92c002a98 <col:11> 'int'
<LValueToRValue>
     |       |   `-DeclRefExpr 0x7ff92c002728 <col:11> 'int' lvalue
ParmVar 0x7ff92c001f80 'coin' 'int'
     |       |-CXXBindTemporaryExpr 0x7ff92c0029b8 <col:18, col:25> 'C2'
(CXXTemporary 0x7ff92c0029b0)
     |       | `-CXXTemporaryObjectExpr 0x7ff92c002968 <col:18, col:25>
'C2' 'void (int, int)'
     |       |   |-IntegerLiteral 0x7ff92c002760 <col:21> 'int' 3
     |       |   `-IntegerLiteral 0x7ff92c002780 <col:24> 'int' 4
     |       `-CXXBindTemporaryExpr 0x7ff92c002a78 <col:29, col:36> 'C2'
(CXXTemporary 0x7ff92c002a70)
     |         `-CXXTemporaryObjectExpr 0x7ff92c002a28 <col:29, col:36>
'C2' 'void (int, int)'
     |           |-IntegerLiteral 0x7ff92c0029e8 <col:32> 'int' 5
     |           `-IntegerLiteral 0x7ff92c002a08 <col:35> 'int' 6
```

Note that the AST for c1 has MORE expressions (which presumably means
more chances to garbage-collect), but in fact it is c2 that is getting
garbage-collected.

This looks to me like a bug - or at least an inconsistency - in liveness
analysis, and the long-term fix that will allow us to finally support
C++17 would probably be to fix this inconsistency.

The fact that liveness analysis has never given us any problems so far -
apart from not supporting some new features we requested from it - is
very surprising. Our liveness analysis must be very conservative if the
first problem we've seen with it in, like, years is in a C++17 feature
that was not even planned back when liveness analysis was written. If
liveness analysis is so conservative, maybe we could speed up the
analyzer dramatically by making it eliminate more expressions and
variables during removeDead()?


On 3/21/18 8:45 PM, Artem Dergachev wrote:

> == Copy elision ==
>
> = Why? =
>
> I've underestimated the importance of implementing copy elision at first.
>
> Eliding copies changes observable behavior of the program if the
> copy/move constructor has side effects. Whether to elide creation of a
> temporary object in certain operations is up to implementation, but
> most implementations currently support and prefer copy elision, so if
> we don't do the same in the analyzer we'd be analyzing a different
> program, and users who don't care about portability may become grumpy
> because they are sure that copy elision is happening.
>
> Additionally, copy elision makes paths longer - including the number
> of diagnostic pieces - which makes reports harder to understand and
> exhausts the analyzer's budget faster.
(cut)
_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: [analyzer] Temporaries.

Hans Wennborg via cfe-dev
In reply to this post by Hans Wennborg via cfe-dev
Hi Artem,

I can say that approach 2 is much more clear for me. At least, from the
user's point of view.

22.03.2018 06:45, Artem Dergachev via cfe-dev пишет:

> == Copy elision ==
>
> = Why? =
>
> I've underestimated the importance of implementing copy elision at first.
>
> Eliding copies changes observable behavior of the program if the
> copy/move constructor has side effects. Whether to elide creation of a
> temporary object in certain operations is up to implementation, but
> most implementations currently support and prefer copy elision, so if
> we don't do the same in the analyzer we'd be analyzing a different
> program, and users who don't care about portability may become grumpy
> because they are sure that copy elision is happening.
>
> Additionally, copy elision makes paths longer - including the number
> of diagnostic pieces - which makes reports harder to understand and
> exhausts the analyzer's budget faster.
>
> = How? =
>
> Consider an example:
>
>      1    class C {
>      2    public:
>      3      C(int, int);
>      4      C(const C &);
>      5      ~C();
>      6    };
>      7
>      8    void foo() {
>      9      C c = C(123, 456);
>     10    }
>
> The respective AST:
>
>       DeclStmt 0x7fe1d3001ed8 <line:9:3, col:20>
>       `-VarDecl 0x7fe1d3001d08 <col:3, col:19> col:5 c 'C' cinit
>         `-ExprWithCleanups 0x7fe1d3001ec0 <col:9, col:19> 'C'
>           `-CXXConstructExpr 0x7fe1d3001e88 <col:9, col:19> 'C' 'void
> (const C &)' elidable
>             `-MaterializeTemporaryExpr 0x7fe1d3001e70 <col:9, col:19>
> 'const C' lvalue
>               `-ImplicitCastExpr 0x7fe1d3001e58 <col:9, col:19> 'const
> C' <NoOp>
>                 `-CXXBindTemporaryExpr 0x7fe1d3001e38 <col:9, col:19>
> 'C' (CXXTemporary 0x7fe1d3001e30)
>                   `-CXXTemporaryObjectExpr 0x7fe1d3001db8 <col:9,
> col:19> 'C' 'void (int, int)'
>                     |-IntegerLiteral 0x7fe1d3001d78 <col:11> 'int' 123
>                     `-IntegerLiteral 0x7fe1d3001d98 <col:16> 'int' 456
>
> And the CFG:
>
> [B1]
>    1: 123
>    2: 456
>    3: C([B1.1], [B1.2]) (CXXConstructExpr, [B1.4], [B1.6], class C)
>    4: [B1.3] (BindTemporary)
>    5: [B1.4] (ImplicitCastExpr, NoOp, const class C)
>    6: [B1.5] (MaterializeTemporaryExpr)
>    7: [B1.6] (CXXConstructExpr, [B1.8], class C)
>    8: C c = C(123, 456);
>    9: ~C() (Temporary object destructor)
>   10: [B1.8].~C() (Implicit destructor)
>
> This explains pretty well what we should do if we don't do copy
> elision: we construct a temporary on B1.3 that's destroyed on B1.9
> after being materialized into an lvalue that's referenced by the
> copy-constructor parameter; the copy-constructor will copy the object
> into the actual variable.
>
> Now, if we are to elide the copy constructor, the original constructor
> C(123, 456) should construct the variable directly, and all statements
> in between (B1.4, B1.5, B1.6, B1.7) and the destructor (B1.9) turn
> into no-op.
>
> I can imagine two ways of implementing such behavior:
>
> (i). Completely remove elided elements B1.4, B1.5, B1.6, B1.7, B1.9
> from the CFG.
> (ii). Keep CFG roughly the same but model elided elements as no-op in
> the analyzer.
>
> I believe that approach (ii) is ultimately better, even though (i)
> sounds very tempting.
>
> Approach (i) assumes that the modified CFG would kinda look like this:
>
> [B1]
>    1: 123
>    2: 456
>    3: C([B1.1], [B1.2]) (CXXConstructExpr, [B1.4], class C)
>    4: C c = C(123, 456);
>    5: [B1.4].~C() (Implicit destructor)
>
> Our CFGConstructor element [B1.3] will essentially be frankensteined
> from *inner* CXXTemporaryObjectExpr 0x7fe1d3001db8 (it's printed as
> CXXConstructExpr in those CFG dumps) and the construction context of
> the *outer* copy-constructor CXXConstructExpr 0x7fe1d3001e88.
>
> This CFG looks pretty good on its own. It's almost indistinguishable
> from the CFG for 'C c(123, 456)' and contains all that's needed to
> properly initialize 'c'.
>
> However the more i think about it, the more it seems to violate the
> principle of least astonishment. For instance,
> getSVal(DeclStmt->getSingleDecl()->getInit(), LC) would yield
> UnknownVal because the constructor that has initialized the variable
> is different from the one that's present in the initializer of the
> variable. The code to obtain the "actual" initializer expression may
> be very complicated because initializers can be quite complex (imagine
> a ?: operator; the code for extracting the actual initializer will
> essentially duplicate the code for finding construction contexts).
>
> Essentially, all of the expressions between the DeclStmt and the
> CXXTemporaryObjectExpr will never be set in the Environment and would
> be unknown. Any user (imagine a checker) who will try to understand
> what is going on in the current program point by exploring values of
> expressions will fail here.
>
> We are going to evaluate our DeclStmt without evaluating its immediate
> sub-expressions. Why would the sub-sub-sub-sub-sub-expression that we
> need to evaluate the DeclStmt be still kept alive in the Environment?
>
> If we try to make checkers' life easier by setting values in the
> Environment anyway for expressions that aren't present in the CFG, how
> would liveness analysis know when to garbage-collect them given this
> analysis is also CFG-based?
>
> In fact I'm quite scared to imagine how our liveness analysis would
> react when he realizes that there are a lot of expressions right in
> the middle of a feasible path that are completely omitted from the
> CFG. I guess we are omitting some dead paths from the CFG, but
> omitting expressions in the middle of a statement will almost
> certainly make liveness analysis more complicated.
>
> Long story short, approach (i) violates a large amount of very basic
> and intuitive invariants that we've so far maintained. Which is scary
> and will make further development harder, even if we manage to make it
> work.
>
> Approach (ii) is much more in the spirit of C++ standard
> [class.copy.elision]:
>
> > "the implementation treats the source and target of the omitted
> copy/move operation as simply two different ways of referring to the
> same object".
>
> Essentially, copy elision is an aliasing relationship between the
> stack variable 'c' and the temporary object within its initializer.
> This makes perfect sense in the CodeGen where both of these are just
> some stack addresses. In analyzer terms, we declare that the
> CXXTempObjectRegion for our CXXTemporaryObjectExpr and the VarRegion
> for our variable 'c' are the same region. Because we don't have
> aliasing / renaming support in the analyzer, we take the route of
> picking our regions correctly from the start (that's, in some sense,
> the whole point of this construction context hassle! - avoiding the
> need to rename regions later - which would have probably been the
> right thing to do even if we could rename regions). It leaves us with
> the following values for the expressions in the Environment:
>
> CXXTemporaryObjectExpr -> lazyCompoundVal{VarRegion 'c', Store after
> construction}
> CXXBindTemporaryExpr -> lazyCompoundVal{VarRegion 'c', Store after
> construction}
> MaterializeTemporaryExpr -> c
> CXXConstructExpr -> lazyCompoundVal{VarRegion 'c', Store after
> construction}
>
> Only CXXTemporaryObjectExpr will be actually modeled (hopefully by
> inlining the constructor), with VarRegion 'c' acting as this-argument.
>
> This leaves us with CXXConstructExpr that constructs into its own
> source argument, which is exactly what the standard expects from us,
> even if it's a bit amusing. It would not construct anything, of
> course, just bind the value. It is questionable whether we need a
> checker callback for the elided constructor (and if we do, which ones
> specifically).
>
> CFG needs to be extended to add more context to the
> CXXTemporaryObjectExpr in order to execute approach (ii) correctly. We
> still need access to the CXXConstructExpr's construction context in
> order to perform the very first construction, so i guess that the
> construction context for CXXTemporaryObjectExpr would be a combination
> of both. Note that there may be more than one elided copy constructor
> (eg. there are two if the initializer is a ?: operator - and, well,
> there may be multiple nested ?: operators).
>
> Additionally, when we model elided expressions, we need to know that
> they are elided by looking at them. We may add this information to
> their CFG elements (this, again, looks tempting, but requires more CFG
> element kinds) or mark expressions as elided in the program state
> (which we can easily do because they are already mentioned in one of
> the construction contexts).
> _______________________________________________
> cfe-dev mailing list
> [hidden email]
> http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev


_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: [analyzer] Temporaries.

Hans Wennborg via cfe-dev
In reply to this post by Hans Wennborg via cfe-dev


On 14 February 2018 at 22:20, Artem Dergachev via cfe-dev <[hidden email]> wrote:
More explanations on how the analyzer keeps making its way around the C++ AST.

== Lifetime extension ==

This is a brain dump of how (and how much) lifetime extension of temporary objects is currently broken in the static analyzert. Spoilers: not too much, it seems, but annoying nevertheless.

Consider an example:

     1    class C {
     2    public:
     3      C() {}
     4      ~C() {}
     5    };
     6
     7    void foo() {
     8      const C &c = C();
     9    }

With the AST for the variable declaration:

      DeclStmt 0x7fa5ac85cba0 <line:8:3, col:19>
      `-VarDecl 0x7fa5ac85c878 <col:3, col:18> col:12 c 'const C &' cinit
        `-ExprWithCleanups 0x7fa5ac85cb30 <col:16, col:18> 'const C' lvalue
          `-MaterializeTemporaryExpr 0x7fa5ac85cb00 <col:16, col:18> 'const C' lvalue extended by Var 0x7fa5ac85c878 'c' 'const C &'
            `-ImplicitCastExpr 0x7fa5ac85cae8 <col:16, col:18> 'const C' <NoOp>
              `-CXXBindTemporaryExpr 0x7fa5ac85cac8 <col:16, col:18> 'C' (CXXTemporary 0x7fa5ac85cac0)
                `-CXXTemporaryObjectExpr 0x7fa5ac85ca88 <col:16, col:18> 'C' 'void ()'

*here goes a periodic reminder that CXXTemporaryObjectExpr is a sub-class of CXXConstructExpr*

Notice how MaterializeTemporaryExpr is the innermost expression (the first one in the order of execution) that is an lvalue. Essentially, you can think of it as the mythical "rvalue-to-lvalue" cast that takes in a C++ object rvalue and returns the this-value for that object. Because all C++ objects have a this-value that never changes throughout their lifetime, it is essentially their identity. Otherwise you can't call methods on them.

MaterializeTemporaryExpr also contains information about the lifetime extension process: we needed the this-value in order to bind it to variable 'c'. You see that in the AST.

In the analyzer, however, MaterializeTemporaryExpr does a different thing, as a temporary solution (no pun intended). It constructs a new temporary region out of thin air and binds the rvalue object to that temporary in the Store. The respective function in our code is called "createTemporaryRegionIfNeeded". It also has a separate purpose of converting rvalue sub-object adjustments into lvalue sub-object adjustments, which we wouldn't discuss this time.

Now that we learned how to inline temporary constructors and destructors, it essentially means that the this-value in the constructor and in the destructor would be different. Because first we construct the object into temporary region R1, then we take lazyCompoundVal{R1} to represent the value of CXXTemporaryObjectExpr, then we materialize lazyCompoundVal{R1} to R2, then we bind R2 to variable 'c', then we call the automatic(!) destructor for 'c' which contains R2. To be clear, the region store at the time of destruction would be:

  c: R2,
  R2: lazyCompoundVal{R1}.

It means that fields of the object would contain the correct values, there would be the correct number of destructors called (no temporary destructors, just one automatic destructor), but the identity of the object (this-value) would change in the process. Unless the object actually makes any decisions or does any manipulations that involve its this-value, the modeling should be correct. When the object starts to actively use its this-value in its inlined methods, the analysis would do wrong stuff. Additionally, it causes a mess in the checkers when they try to track objects by their this-values - i.e. IteratorChecker has a lot of additional code to work around the fact that the region for the object constantly changes.

From the above it is clear that MaterializeTemporaryExpr should not construct any new regions, at least not in this case. We already have the correct region, namely R1, which should be re-used.

Hi Artem!

We found a strange false positive that might be related to what you describe above but not sure though. Could you take a look?
It looks like we are seeing a null pointer dereference error, and the null value comes from the destructor which was invoked on a temporary.
If this is not the case, the path diagnostic might be misleading.

Regards,
Gábor
 

It is tempting to take R1 directly from lazyCompoundVal{R1} - it already has memories about once being a value of R1. I'm not sure it's not going to work - it may work, at least i'm not ready to come up with a counterexample. But the meaning of LazyCompoundVal's parent region is different and coincides with what we want just accidentally. Namely, lazyCompoundVal{R1} is a value of an object that was bound to R1 in some particular moment of time in the past, without any explanation of when this moment of time was - but there's no indication if R1 is the region of the temporary we've just constructed, or a region of an unrelated object that used to have the same value back then. As we'd see later, MaterializeTemporaryExpr doesn't always contain a constructor within it - there are a lot of cases to cover, and if the trick doesn't work even once, it's going to be hard, so i'd probably not going to commit into maintaining this invariant. Though it might be plausible to modify add an SVal kind that does exactly what we mean here - i.e. a value that does indeed correspond to a specific C++ object identified by region. It might be a beautiful solution, but it may also fail miserably if tricky cornercases show up - so i'm not ready to commit to that. Also the correct way of dealing with such values (i.e. for how long are they relevant?) would be extremely difficult to explain to checker developers.

The more straightforward approach here is to include MaterializeTemporaryExpr (hereinafter MTE) into the construction context. It means, if a temporary that we're about to construct would be lifetime-extended later, we'd rather know about that during construction, and maintain a map in the program state from MTE to their respective temporary regions that were used for representing the respective construction targets. Upon encountering the respective MTE we'd simply retrieve the implicit temporary storage for the value from the program state and declare that temporary region to be the value of the MTE. This would mimic the approach we have with CXXBindTemporaryExprs (hereinafter BTE) and their respective regions that allows temporary destructors to work - but this time it's going to be about MaterializeTemporaryExprs and automatic destructors. I imagine that on the checker side this can potentially be exposed via some sort of State->getTemporaryStorage(Expr) call, but i believe that generally this process should be as transparent to the checkers as possible.

It sounds as if both of these maps could be eliminated by always making sure that the target temporary is constructed "with" the MTE (for lifetime-extended temproraries) or BTE (for temporaries that require destruction at the end of full-expression). In this case, with the help of construction context-assisted lookahead, we declare that the target of the construction is CXXTempObjectRegion(MTE, LC) or CXXTempObjectRegion(BTE, LC) respectively, rather than CXXTempObjectRegion(CXXConstructExpr). Then during evaluation of MTE or BTE we'd simply construct the same region with the expression we're currently evaluating, and it's automagically going to be the correct region. This approach, however, becomes confusing when we start dealing with elidable constructors (explained below). So for now i believe that it is quite irrelevant which expression is identifying the temporary region.

== Elidable constructors ==

While it doesn't sound like an immediately important task to implement copy elision in the analyzer, it may help with making some things easier. And it'd also make some reports fancier, as mentioned in https://reviews.llvm.org/D43144.

Elidable copy-constructors can be explained as a form of lifetime extension. Instead of copying the temporary, they keep using the original value of the temporary, which in some pretty twisted sense means that they are lifetime-extending it to be able to use it. For example, if we modify our example by replacing the lifetime-extending reference variable with a value-type variable:

     1    class C {
     2    public:
     3      C() {}
     4      ~C() {}
     5    };
     6
     7    void foo() {
     8      C c = C();
     9    }

...then we'd still have an MTE, even though lifetime extension would seem to be gone:

      DeclStmt 0x7fb8f005afb8 <line:8:3, col:12>
      `-VarDecl 0x7fb8f005ac50 <col:3, col:11> col:5 c 'C' cinit
        `-ExprWithCleanups 0x7fb8f005afa0 <col:9, col:11> 'C'
          `-CXXConstructExpr 0x7fb8f005af68 <col:9, col:11> 'C' 'void (const C &) noexcept' elidable
            `-MaterializeTemporaryExpr 0x7fb8f005af00 <col:9, col:11> 'const C' lvalue
              `-ImplicitCastExpr 0x7fb8f005aee8 <col:9, col:11> 'const C' <NoOp>
                `-CXXBindTemporaryExpr 0x7fb8f005aec8 <col:9, col:11> 'C' (CXXTemporary 0x7fb8f005aec0)
                  `-CXXTemporaryObjectExpr 0x7fb8f005ae88 <col:9, col:11> 'C' 'void ()'

In this case the MTE is expressing the fact that the temporary constructed via CXXTemporaryObjectExpr can be "lifetime-extended" (by actually merging it with the stack variable) rather than copied, if the CXXConstructExpr surrounding it would be chosen to be elided. The AST doesn't make the elision choice for us - but is compatible with both choices. The MTE essentially overrides the necessity of immediate destruction provided by the BTE, and lets the surrounding AST decide upon the lifetime of the object.

Because the analyzer currently does not do copy elision, it will use the MTE only to compute the argument for the elidable copy-constructor, and then perform the copy-construction, and then destroy the original temporary at the end of the full-expression. Note, however, that in this case we need to properly support both the BTE (for the temporary destructor to work) and the MTE (for computing its value). We need to implement the MTE's ability to perform "rvalue-to-lvalue-cast" even if the temporary destruction is still necessary. For this reason, if we rely on constructing temporary regions with the correct BTEs or MTEs, at least one of these tasks becomes impossible to perform.

If we were to support copy elision, then the CXXTemporaryObjectExpr constructor would go directly into the variable region. For the purposes of modeling, it'd mean that only CXXTemporaryObjectExpr would actually need to be modeled. But this would require additional coding in the construction context to be able to realize that the target is the variable while modeling the CXXTemporaryObjectExpr.

For the sake of completeness, let's consider the ternary operator example:

     1    class C {
     2    public:
     3      C(int) {}
     4      ~C() {}
     5    };
     6
     7    void foo(int coin) {
     8      const C &c = coin ? C(1) : C(2);
     9    }

The respective AST would be:

      DeclStmt 0x7fc1e20023e0 <line:8:3, col:34>
      `-VarDecl 0x7fc1e2001dc8 <col:3, col:33> col:12 c 'const C &' cinit
        `-ExprWithCleanups 0x7fc1e2002370 <col:16, col:33> 'const C' lvalue
          `-MaterializeTemporaryExpr 0x7fc1e2002340 <col:16, col:33> 'const C' lvalue extended by Var 0x7fc1e2001dc8 'c' 'const C &'
            `-ImplicitCastExpr 0x7fc1e2002328 <col:16, col:33> 'const C' <NoOp>
              `-ConditionalOperator 0x7fc1e20022f8 <col:16, col:33> 'C'
                |-ImplicitCastExpr 0x7fc1e2002170 <col:16> 'bool' <IntegralToBoolean>
                | `-ImplicitCastExpr 0x7fc1e2002158 <col:16> 'int' <LValueToRValue>
                |   `-DeclRefExpr 0x7fc1e2001e28 <col:16> 'int' lvalue ParmVar 0x7fc1e2001c18 'coin' 'int'
                |-CXXBindTemporaryExpr 0x7fc1e2002248 <col:23, col:26> 'C' (CXXTemporary 0x7fc1e2002240)
                | `-CXXConstructExpr 0x7fc1e2002208 <col:23, col:26> 'C' 'void (const C &) noexcept' elidable
                |   `-MaterializeTemporaryExpr 0x7fc1e20021a0 <col:23, col:26> 'const C' lvalue
                |     `-ImplicitCastExpr 0x7fc1e2002188 <col:23, col:26> 'const C' <NoOp>
                |       `-CXXFunctionalCastExpr 0x7fc1e2002078 <col:23, col:26> 'C' functional cast to class C <ConstructorConversion>
                |         `-CXXBindTemporaryExpr 0x7fc1e2002058 <col:23, col:26> 'C' (CXXTemporary 0x7fc1e2002050)
                |           `-CXXConstructExpr 0x7fc1e2002018 <col:23, col:26> 'C' 'void (int)'
                |             `-IntegerLiteral 0x7fc1e2001e60 <col:25> 'int' 1
                `-CXXBindTemporaryExpr 0x7fc1e20022d8 <col:30, col:33> 'C' (CXXTemporary 0x7fc1e20022d0)
                  `-CXXConstructExpr 0x7fc1e2002298 <col:30, col:33> 'C' 'void (const C &) noexcept' elidable
                    `-MaterializeTemporaryExpr 0x7fc1e2002280 <col:30, col:33> 'const C' lvalue
                      `-ImplicitCastExpr 0x7fc1e2002268 <col:30, col:33> 'const C' <NoOp>
                        `-CXXFunctionalCastExpr 0x7fc1e2002130 <col:30, col:33> 'C' functional cast to class C <ConstructorConversion>
                          `-CXXBindTemporaryExpr 0x7fc1e2002110 <col:30, col:33> 'C' (CXXTemporary 0x7fc1e2002108)
                            `-CXXConstructExpr 0x7fc1e20020d0 <col:30, col:33> 'C' 'void (int)'
                              `-IntegerLiteral 0x7fc1e20020b0 <col:32> 'int' 2

Each branch contains two constructors: the temporary and the elidable copy. The temporaries are surrounded with their respective BTEs and copy-elision-kind MTEs, which indicates that they need to be either destroyed as temporaries, or, if copy elision is chosen, have their lifetime decided upon by the surrounding AST. The elidable copy constructors also, being temporaries, have their respective BTEs. Note, however, that there is only one MTE for both BTEs for the elidable constructors.

So after the conditional operator is resolved (which is the first thing we need to do, according to the CFG), we'd go ahead and perform the constructors, and their trigger would be their respective BTE in the non-elide case, and the single top-level MTE in the elide case. In the non-elide case, copy constructors would be triggered by the top-level MTE.

It means that, once again, copy elision would prevent us from handling both the BTE and the copy-elision-kind MTE in the single construction, allowing the "predictable target region" trick to work: when we need the temporary destructor, we construct directly into CXXTempObjectRegion of the BTE and it gets automatically picked up during destruction, and when we need the automatic destructor, we construct directly into CXXTempObjectRegion of the MTE and we can easily compute the value of the MTE. But when we don't do copy elision, we'd have to keep at least one of those in the program state map.

== Return by value ==

Returning C++ objects by value is actually very similar to constructing it. Consider:

     1    class C {
     2    public:
     3      C() {}
     4      ~C() {}
     5    };
     6
     7    C bar() {
     8      C c;
     9      return c;
    10    }
    11
    12    void foo() {
    13      const C &c = bar();
    14    }

With the respective AST for DeclStmt in foo():

      DeclStmt 0x7fe62c84f8e8 <line:13:3, col:21>
      `-VarDecl 0x7fe62c84f6b8 <col:3, col:20> col:12 c 'const C &' cinit
        `-ExprWithCleanups 0x7fe62c84f878 <col:16, col:20> 'const C' lvalue
          `-MaterializeTemporaryExpr 0x7fe62c84f848 <col:16, col:20> 'const C' lvalue extended by Var 0x7fe62c84f6b8 'c' 'const C &'
            `-ImplicitCastExpr 0x7fe62c84f830 <col:16, col:20> 'const C' <NoOp>
              `-CXXBindTemporaryExpr 0x7fe62c84f810 <col:16, col:20> 'C' (CXXTemporary 0x7fe62c84f808)
                `-CallExpr 0x7fe62c84f7e0 <col:16, col:20> 'C'
                  `-ImplicitCastExpr 0x7fe62c84f7c8 <col:16> 'C (*)()' <FunctionToPointerDecay>
                    `-DeclRefExpr 0x7fe62c84f770 <col:16> 'C ()' lvalue Function 0x7fe62c84f190 'bar' 'C ()'

And for the ReturnStmt in bar():

      ReturnStmt 0x7fe62c84f5b0 <line:9:3, col:10>
      `-CXXConstructExpr 0x7fe62c84f578 <col:10> 'C' 'void (const C &) noexcept' elidable
        `-ImplicitCastExpr 0x7fe62c84f518 <col:10> 'const C' lvalue <NoOp>
          `-DeclRefExpr 0x7fe62c84f4f0 <col:10> 'C' lvalue Var 0x7fe62c84f280 'c' 'C'

Since https://reviews.llvm.org/D42875 we can already realize that the constructor in bar(), assuming that we're inlining bar() during analysis, would be constructed into something that is a return value of bar(). This allows us, by looking that the StackFrameContext's call site, to figure out that it is being constructed into the CallExpr in foo(). Now if only we knew that that the call site is a lifetime-extended temporary, i.e. if only we had a pointer to the foo()'s MTE at the CallExpr's CFG element, we'd be able to find the correct target region for construction: the CXXTempObjectRegion for the MTE in the StackFrameContext of foo(). So i'm proposing to add some sort of construction context to not only constructors, but also to functions that return objects, and then during construction perform the lookup in three easy steps:

  1. in the callee's CFG from constructor to return statement,
  2. through the location from the return statement to the call site,
  3. then through the caller's CFG from the call site to the MTE.

If the function is not inlined, we can still make use of the construction context to represent the return value as a LazyCompoundValue of the MTE's temporary. It would eliminate the need to replace the return value with another value while evaluating the MTE, and of course the need to re-bind the object to a different this-region.

So i believe that this is a good way to eliminate the need for the "createTemporaryRegionIfNeeded" thing in the function calls as well.



On 06/02/2018 1:41 PM, Artem Dergachev wrote:
A bit of an update.

== Temporary destructors ==

Adding some initial support for temporary destructors seems pretty easy and straightforward at this point, given the awesome work done by Manuel Klimek on our CFG a few years ago.

1. We already have the awesome CFGTemporaryDtor elements, which have the backreference to the CXXBindTemporaryExpr for their temporaries.

2. In simple cases CXXBindTemporaryExprs have an immediate constructor within them, and therefore we can provide the CXXBindTemporaryExprs as the construction context's trigger statements, and therefore have a reliable CXXTempObjectRegion for constructors.

3. Then we already track the CXXBindTemporaryExprs for the active temporaries in the program state. We can attach any constructor information to them, such as the target region, if we need to (probably we can reconstruct it by looking at the expression and the location context, not sure if we want to).

4. So when we reach the CFGTemporaryDtor element, we can just lookup all the info we need, and perform the destruction properly.

5. There's a bit of a liveness problem, because it seems that our liveness analysis tends to throw away the temporary too early. I can easily hack this problem away by marking all regions that correspond to active temporaries as live. I'll see if there's a better solution.

== CXXDefaultArgExpr problems ==

There's a known problem with those. Consider:

  void foo(const C &c = C()) {
  }

  void bar() {
    foo();
    foo();
  }

Each call of foo() contains a CXXDefaultArgExpr for c. The default argument value C() is constructed before we enter foo() and destroyed after we leave foo(). However, c's initializer, "= C()", is *not part of the AST of bar()*. In particular, when foo() is called twice, the initializer for the two calls is the same, only CXXDefaultArgExprs are different. This screws a lot of invariants in the analyzer: program points start coinciding (causing the analysis to loop and cache out), Environment doesn't expect the same expression in the same location context have two different values (suppose calls are nested into each other), analysis taking wrong branches, and so on.

Luckily, default-arg expressions that aren't zero integers or null pointers are pretty rare. Still, we'd need to eventually think how to avoid any really bad practical problems with them.

On 25/01/2018 9:08 AM, Artem Dergachev wrote:
Handling C++ temporary object construction and destruction seems to be the biggest cause of false positives on C++ code at the moment. I'd be looking into this, even though for now i don't see the whole scale of problem.

== CFG, destructors, and ProgramPoints ==

We should probably enable `-analyzer-config cfg-temporary-dtors=true` by default soon. It is a fairly low-impact change because it only alters the CFG but the analyzer rarely actually uses the new nodes. Destructors for the most part are still evaluated conservatively, with improper object regions. So it causes almost no changes in the analyzer's positives for now, but it definitely opens up room for further improvements.

I'm observing a couple of problems with this mode at the moment, namely the rich CFG destructor element hierarchy is not currently complemented by an equally rich ProgramPoint hierarchy. This causes the analysis to merge nodes which are not equivalent, for example two implicit destructors of the same type (with the same function declaration) may sometimes cause the ExplodedGraph to coil up and stop analysis (lost coverage) because of having the same program state at the erroneously-same program point. Because situations when we can guarantee a change in the program state are pretty rare, we'd have to produce more program point kinds to handle this correctly.

CallEvent hierarchy is also very much affected in a similar manner - because apparently we're constructing program points by looking at CallEvents, so they'd need to carry all the information that's needed to construct the pre-call/post-call program point.

== Construction contexts ==

We are correctly modeling "this" object region during construction/destruction of variables with automatic storage duration, fields and base classes, and on operator new() since recently, as long as these aren't arrays of objects. It was not yet implemented for other cases such as temporaries, initializer lists, fields or C++17 base classes within aggregates, and pass-by-value from/to functions (the latter being a slightly different problem than temporaries).

First of all, by "not yet implemented" i mean that instead of constructing into (destroying) the correct object (in the correct memory region), we come up with a "temporary region", which looks exactly like a region of a valid C++ temporary but is only used for communicating that it is not the right region. Then we look at the region, see that it is a temporary, and avoid inlining constructors, because it would make little sense when the region is not correct. However, if we are to model temporaries, we need another way of communicating our failure to find the correct region, which is being addressed by https://reviews.llvm.org/D42457

Also in the cases when the correct region is used, it is being computed in a funky way: in order to figure out where do we construct the object, we walk forward in the CFG (or from child to parent in the AST) to find the next/parent statement that would accomodate the newly constructed object. This means that the CFG, while perfectly telling us what to do in what order (which we, unlike CodeGen, cannot easily take from AST because we cannot afford recursive evaluation of statements, mainly because of inlining), discards too much context to be helpful in understanding how to do it.

I tried to add the information about such "trigger statements" for constructors into CFG and it is extremely helpful and easy to both use and extend. This assumes adding a new sub-class of CFGElement for constructors, which maintain a "construction context" - for now it's just a trigger statement. For instance, in

  class C { ... };
  void foo() {
    C c;
  }

...the trigger for constructor C() would be DeclStmt `C c`, and once we know this we can immediately figure out that the construction target is the region of variable `c`. Construction trigger is not necessarily a statement - it may be a CXXCtorInitializer, which is an AST node kind of its own. Additionally, when constructing aggregates via initializer lists, we may have the same statement trigger multiple constructors, eg. in

  class C { public: C(int); ~C(); };
  struct S { C c1, c2, c3; };
  void foo() {
    S s { 1, 2, 3 };
  }

... we have three different constructors (actually six different constructors if we include elidable copy constructors) for c1, c2, c3 (and lack of constructor for `s` because of the aggregate thing). It would be more natural to declare that the specific field or index would be a part of the CFG's construction context, as well as the intermediate InitListExpr, so even in these simple cases the construction context may get quite bulky. And this example is quite popular on actual code - probably the second worst cause of false positives after temporaries.

For now i have no specific plan on what would construction context for temporaries contain in the general case. I might not be able to get the data structures right from the start. In any case, it might be necessary to perform additional memory allocations for these CFG elements (for analyzer's CFG only, so it wouldn't affect compilation time or warnings).

I believe that getting the correct target region in as many cases as possible would be the main part of my work for the nearest future. And i want to move most this work to CFG, while letting the analyzer pick up the trigger statement from it and trust it as blindly as possible.

== Workflow ==

When working on operator new, i tried hard to maintain a reasonable history, making around 15 local rebases. It was not awesome because it was hard for the reviewers to understand the context of the new changes, and changes could have easily kicked in during rebases. A few lessons learned here would be to commit more aggressively, i.e. avoiding stockpiling a large history of patches (essentially a large branch), which in turn would be possible through trying harder to avoid unrelated hard-to-test core changes (as long as it doesn't require weird workarounds) that aren't covered by a flag (such as those evalCast fixes), in order to make sure reviewing take less responsibility. It's fine if some parts would later be fixed (assuming they would indeed be fixed), if it means making the turnaround faster and the tail of patches shorter - that's also the attitude i'd try to maintain when reviewing stuff myself.


_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev


_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: [analyzer] Temporaries.

Hans Wennborg via cfe-dev


On 4/12/18 1:10 PM, Gábor Horváth wrote:


On 14 February 2018 at 22:20, Artem Dergachev via cfe-dev <[hidden email]> wrote:
More explanations on how the analyzer keeps making its way around the C++ AST.

== Lifetime extension ==

This is a brain dump of how (and how much) lifetime extension of temporary objects is currently broken in the static analyzert. Spoilers: not too much, it seems, but annoying nevertheless.

Consider an example:

     1    class C {
     2    public:
     3      C() {}
     4      ~C() {}
     5    };
     6
     7    void foo() {
     8      const C &c = C();
     9    }

With the AST for the variable declaration:

      DeclStmt 0x7fa5ac85cba0 <line:8:3, col:19>
      `-VarDecl 0x7fa5ac85c878 <col:3, col:18> col:12 c 'const C &' cinit
        `-ExprWithCleanups 0x7fa5ac85cb30 <col:16, col:18> 'const C' lvalue
          `-MaterializeTemporaryExpr 0x7fa5ac85cb00 <col:16, col:18> 'const C' lvalue extended by Var 0x7fa5ac85c878 'c' 'const C &'
            `-ImplicitCastExpr 0x7fa5ac85cae8 <col:16, col:18> 'const C' <NoOp>
              `-CXXBindTemporaryExpr 0x7fa5ac85cac8 <col:16, col:18> 'C' (CXXTemporary 0x7fa5ac85cac0)
                `-CXXTemporaryObjectExpr 0x7fa5ac85ca88 <col:16, col:18> 'C' 'void ()'

*here goes a periodic reminder that CXXTemporaryObjectExpr is a sub-class of CXXConstructExpr*

Notice how MaterializeTemporaryExpr is the innermost expression (the first one in the order of execution) that is an lvalue. Essentially, you can think of it as the mythical "rvalue-to-lvalue" cast that takes in a C++ object rvalue and returns the this-value for that object. Because all C++ objects have a this-value that never changes throughout their lifetime, it is essentially their identity. Otherwise you can't call methods on them.

MaterializeTemporaryExpr also contains information about the lifetime extension process: we needed the this-value in order to bind it to variable 'c'. You see that in the AST.

In the analyzer, however, MaterializeTemporaryExpr does a different thing, as a temporary solution (no pun intended). It constructs a new temporary region out of thin air and binds the rvalue object to that temporary in the Store. The respective function in our code is called "createTemporaryRegionIfNeeded". It also has a separate purpose of converting rvalue sub-object adjustments into lvalue sub-object adjustments, which we wouldn't discuss this time.

Now that we learned how to inline temporary constructors and destructors, it essentially means that the this-value in the constructor and in the destructor would be different. Because first we construct the object into temporary region R1, then we take lazyCompoundVal{R1} to represent the value of CXXTemporaryObjectExpr, then we materialize lazyCompoundVal{R1} to R2, then we bind R2 to variable 'c', then we call the automatic(!) destructor for 'c' which contains R2. To be clear, the region store at the time of destruction would be:

  c: R2,
  R2: lazyCompoundVal{R1}.

It means that fields of the object would contain the correct values, there would be the correct number of destructors called (no temporary destructors, just one automatic destructor), but the identity of the object (this-value) would change in the process. Unless the object actually makes any decisions or does any manipulations that involve its this-value, the modeling should be correct. When the object starts to actively use its this-value in its inlined methods, the analysis would do wrong stuff. Additionally, it causes a mess in the checkers when they try to track objects by their this-values - i.e. IteratorChecker has a lot of additional code to work around the fact that the region for the object constantly changes.

From the above it is clear that MaterializeTemporaryExpr should not construct any new regions, at least not in this case. We already have the correct region, namely R1, which should be re-used.

Hi Artem!

We found a strange false positive that might be related to what you describe above but not sure though. Could you take a look?
It looks like we are seeing a null pointer dereference error, and the null value comes from the destructor which was invoked on a temporary.
If this is not the case, the path diagnostic might be misleading.

Regards,
Gábor

Hmm, i don't fully understand it yet. It seems to me that RefHash3KeysIdPoolEnumerator drains the whole pool upon destruction (fIdPtrs is not a member of the temporary, it's an external entity), so it indeed can't really be safely passed around or copied (i.e. elidable copies are not moves).

So i'd easily believe that this code only works because all copies are elided, i.e. the code is not portable (at least not until C++17) but usually works because most compilers are clever enough. We'll probably get rid of such positives when we implement copy elision.

In case i got it all wrong, do you accidentally have a reproducer for me to have a closer look? If CTU stuff is hard to provide a reproducer for, you should be able to write a small code snippet directly into RefHash3KeysIdPool.c to reproduce the problem. I'll also accept a trimmed (as in -trim-egraph) exploded graph dot file even if it's huge.

P.S. The "Calling..." icon is hilarious :D
 

It is tempting to take R1 directly from lazyCompoundVal{R1} - it already has memories about once being a value of R1. I'm not sure it's not going to work - it may work, at least i'm not ready to come up with a counterexample. But the meaning of LazyCompoundVal's parent region is different and coincides with what we want just accidentally. Namely, lazyCompoundVal{R1} is a value of an object that was bound to R1 in some particular moment of time in the past, without any explanation of when this moment of time was - but there's no indication if R1 is the region of the temporary we've just constructed, or a region of an unrelated object that used to have the same value back then. As we'd see later, MaterializeTemporaryExpr doesn't always contain a constructor within it - there are a lot of cases to cover, and if the trick doesn't work even once, it's going to be hard, so i'd probably not going to commit into maintaining this invariant. Though it might be plausible to modify add an SVal kind that does exactly what we mean here - i.e. a value that does indeed correspond to a specific C++ object identified by region. It might be a beautiful solution, but it may also fail miserably if tricky cornercases show up - so i'm not ready to commit to that. Also the correct way of dealing with such values (i.e. for how long are they relevant?) would be extremely difficult to explain to checker developers.

The more straightforward approach here is to include MaterializeTemporaryExpr (hereinafter MTE) into the construction context. It means, if a temporary that we're about to construct would be lifetime-extended later, we'd rather know about that during construction, and maintain a map in the program state from MTE to their respective temporary regions that were used for representing the respective construction targets. Upon encountering the respective MTE we'd simply retrieve the implicit temporary storage for the value from the program state and declare that temporary region to be the value of the MTE. This would mimic the approach we have with CXXBindTemporaryExprs (hereinafter BTE) and their respective regions that allows temporary destructors to work - but this time it's going to be about MaterializeTemporaryExprs and automatic destructors. I imagine that on the checker side this can potentially be exposed via some sort of State->getTemporaryStorage(Expr) call, but i believe that generally this process should be as transparent to the checkers as possible.

It sounds as if both of these maps could be eliminated by always making sure that the target temporary is constructed "with" the MTE (for lifetime-extended temproraries) or BTE (for temporaries that require destruction at the end of full-expression). In this case, with the help of construction context-assisted lookahead, we declare that the target of the construction is CXXTempObjectRegion(MTE, LC) or CXXTempObjectRegion(BTE, LC) respectively, rather than CXXTempObjectRegion(CXXConstructExpr). Then during evaluation of MTE or BTE we'd simply construct the same region with the expression we're currently evaluating, and it's automagically going to be the correct region. This approach, however, becomes confusing when we start dealing with elidable constructors (explained below). So for now i believe that it is quite irrelevant which expression is identifying the temporary region.

== Elidable constructors ==

While it doesn't sound like an immediately important task to implement copy elision in the analyzer, it may help with making some things easier. And it'd also make some reports fancier, as mentioned in https://reviews.llvm.org/D43144.

Elidable copy-constructors can be explained as a form of lifetime extension. Instead of copying the temporary, they keep using the original value of the temporary, which in some pretty twisted sense means that they are lifetime-extending it to be able to use it. For example, if we modify our example by replacing the lifetime-extending reference variable with a value-type variable:

     1    class C {
     2    public:
     3      C() {}
     4      ~C() {}
     5    };
     6
     7    void foo() {
     8      C c = C();
     9    }

...then we'd still have an MTE, even though lifetime extension would seem to be gone:

      DeclStmt 0x7fb8f005afb8 <line:8:3, col:12>
      `-VarDecl 0x7fb8f005ac50 <col:3, col:11> col:5 c 'C' cinit
        `-ExprWithCleanups 0x7fb8f005afa0 <col:9, col:11> 'C'
          `-CXXConstructExpr 0x7fb8f005af68 <col:9, col:11> 'C' 'void (const C &) noexcept' elidable
            `-MaterializeTemporaryExpr 0x7fb8f005af00 <col:9, col:11> 'const C' lvalue
              `-ImplicitCastExpr 0x7fb8f005aee8 <col:9, col:11> 'const C' <NoOp>
                `-CXXBindTemporaryExpr 0x7fb8f005aec8 <col:9, col:11> 'C' (CXXTemporary 0x7fb8f005aec0)
                  `-CXXTemporaryObjectExpr 0x7fb8f005ae88 <col:9, col:11> 'C' 'void ()'

In this case the MTE is expressing the fact that the temporary constructed via CXXTemporaryObjectExpr can be "lifetime-extended" (by actually merging it with the stack variable) rather than copied, if the CXXConstructExpr surrounding it would be chosen to be elided. The AST doesn't make the elision choice for us - but is compatible with both choices. The MTE essentially overrides the necessity of immediate destruction provided by the BTE, and lets the surrounding AST decide upon the lifetime of the object.

Because the analyzer currently does not do copy elision, it will use the MTE only to compute the argument for the elidable copy-constructor, and then perform the copy-construction, and then destroy the original temporary at the end of the full-expression. Note, however, that in this case we need to properly support both the BTE (for the temporary destructor to work) and the MTE (for computing its value). We need to implement the MTE's ability to perform "rvalue-to-lvalue-cast" even if the temporary destruction is still necessary. For this reason, if we rely on constructing temporary regions with the correct BTEs or MTEs, at least one of these tasks becomes impossible to perform.

If we were to support copy elision, then the CXXTemporaryObjectExpr constructor would go directly into the variable region. For the purposes of modeling, it'd mean that only CXXTemporaryObjectExpr would actually need to be modeled. But this would require additional coding in the construction context to be able to realize that the target is the variable while modeling the CXXTemporaryObjectExpr.

For the sake of completeness, let's consider the ternary operator example:

     1    class C {
     2    public:
     3      C(int) {}
     4      ~C() {}
     5    };
     6
     7    void foo(int coin) {
     8      const C &c = coin ? C(1) : C(2);
     9    }

The respective AST would be:

      DeclStmt 0x7fc1e20023e0 <line:8:3, col:34>
      `-VarDecl 0x7fc1e2001dc8 <col:3, col:33> col:12 c 'const C &' cinit
        `-ExprWithCleanups 0x7fc1e2002370 <col:16, col:33> 'const C' lvalue
          `-MaterializeTemporaryExpr 0x7fc1e2002340 <col:16, col:33> 'const C' lvalue extended by Var 0x7fc1e2001dc8 'c' 'const C &'
            `-ImplicitCastExpr 0x7fc1e2002328 <col:16, col:33> 'const C' <NoOp>
              `-ConditionalOperator 0x7fc1e20022f8 <col:16, col:33> 'C'
                |-ImplicitCastExpr 0x7fc1e2002170 <col:16> 'bool' <IntegralToBoolean>
                | `-ImplicitCastExpr 0x7fc1e2002158 <col:16> 'int' <LValueToRValue>
                |   `-DeclRefExpr 0x7fc1e2001e28 <col:16> 'int' lvalue ParmVar 0x7fc1e2001c18 'coin' 'int'
                |-CXXBindTemporaryExpr 0x7fc1e2002248 <col:23, col:26> 'C' (CXXTemporary 0x7fc1e2002240)
                | `-CXXConstructExpr 0x7fc1e2002208 <col:23, col:26> 'C' 'void (const C &) noexcept' elidable
                |   `-MaterializeTemporaryExpr 0x7fc1e20021a0 <col:23, col:26> 'const C' lvalue
                |     `-ImplicitCastExpr 0x7fc1e2002188 <col:23, col:26> 'const C' <NoOp>
                |       `-CXXFunctionalCastExpr 0x7fc1e2002078 <col:23, col:26> 'C' functional cast to class C <ConstructorConversion>
                |         `-CXXBindTemporaryExpr 0x7fc1e2002058 <col:23, col:26> 'C' (CXXTemporary 0x7fc1e2002050)
                |           `-CXXConstructExpr 0x7fc1e2002018 <col:23, col:26> 'C' 'void (int)'
                |             `-IntegerLiteral 0x7fc1e2001e60 <col:25> 'int' 1
                `-CXXBindTemporaryExpr 0x7fc1e20022d8 <col:30, col:33> 'C' (CXXTemporary 0x7fc1e20022d0)
                  `-CXXConstructExpr 0x7fc1e2002298 <col:30, col:33> 'C' 'void (const C &) noexcept' elidable
                    `-MaterializeTemporaryExpr 0x7fc1e2002280 <col:30, col:33> 'const C' lvalue
                      `-ImplicitCastExpr 0x7fc1e2002268 <col:30, col:33> 'const C' <NoOp>
                        `-CXXFunctionalCastExpr 0x7fc1e2002130 <col:30, col:33> 'C' functional cast to class C <ConstructorConversion>
                          `-CXXBindTemporaryExpr 0x7fc1e2002110 <col:30, col:33> 'C' (CXXTemporary 0x7fc1e2002108)
                            `-CXXConstructExpr 0x7fc1e20020d0 <col:30, col:33> 'C' 'void (int)'
                              `-IntegerLiteral 0x7fc1e20020b0 <col:32> 'int' 2

Each branch contains two constructors: the temporary and the elidable copy. The temporaries are surrounded with their respective BTEs and copy-elision-kind MTEs, which indicates that they need to be either destroyed as temporaries, or, if copy elision is chosen, have their lifetime decided upon by the surrounding AST. The elidable copy constructors also, being temporaries, have their respective BTEs. Note, however, that there is only one MTE for both BTEs for the elidable constructors.

So after the conditional operator is resolved (which is the first thing we need to do, according to the CFG), we'd go ahead and perform the constructors, and their trigger would be their respective BTE in the non-elide case, and the single top-level MTE in the elide case. In the non-elide case, copy constructors would be triggered by the top-level MTE.

It means that, once again, copy elision would prevent us from handling both the BTE and the copy-elision-kind MTE in the single construction, allowing the "predictable target region" trick to work: when we need the temporary destructor, we construct directly into CXXTempObjectRegion of the BTE and it gets automatically picked up during destruction, and when we need the automatic destructor, we construct directly into CXXTempObjectRegion of the MTE and we can easily compute the value of the MTE. But when we don't do copy elision, we'd have to keep at least one of those in the program state map.

== Return by value ==

Returning C++ objects by value is actually very similar to constructing it. Consider:

     1    class C {
     2    public:
     3      C() {}
     4      ~C() {}
     5    };
     6
     7    C bar() {
     8      C c;
     9      return c;
    10    }
    11
    12    void foo() {
    13      const C &c = bar();
    14    }

With the respective AST for DeclStmt in foo():

      DeclStmt 0x7fe62c84f8e8 <line:13:3, col:21>
      `-VarDecl 0x7fe62c84f6b8 <col:3, col:20> col:12 c 'const C &' cinit
        `-ExprWithCleanups 0x7fe62c84f878 <col:16, col:20> 'const C' lvalue
          `-MaterializeTemporaryExpr 0x7fe62c84f848 <col:16, col:20> 'const C' lvalue extended by Var 0x7fe62c84f6b8 'c' 'const C &'
            `-ImplicitCastExpr 0x7fe62c84f830 <col:16, col:20> 'const C' <NoOp>
              `-CXXBindTemporaryExpr 0x7fe62c84f810 <col:16, col:20> 'C' (CXXTemporary 0x7fe62c84f808)
                `-CallExpr 0x7fe62c84f7e0 <col:16, col:20> 'C'
                  `-ImplicitCastExpr 0x7fe62c84f7c8 <col:16> 'C (*)()' <FunctionToPointerDecay>
                    `-DeclRefExpr 0x7fe62c84f770 <col:16> 'C ()' lvalue Function 0x7fe62c84f190 'bar' 'C ()'

And for the ReturnStmt in bar():

      ReturnStmt 0x7fe62c84f5b0 <line:9:3, col:10>
      `-CXXConstructExpr 0x7fe62c84f578 <col:10> 'C' 'void (const C &) noexcept' elidable
        `-ImplicitCastExpr 0x7fe62c84f518 <col:10> 'const C' lvalue <NoOp>
          `-DeclRefExpr 0x7fe62c84f4f0 <col:10> 'C' lvalue Var 0x7fe62c84f280 'c' 'C'

Since https://reviews.llvm.org/D42875 we can already realize that the constructor in bar(), assuming that we're inlining bar() during analysis, would be constructed into something that is a return value of bar(). This allows us, by looking that the StackFrameContext's call site, to figure out that it is being constructed into the CallExpr in foo(). Now if only we knew that that the call site is a lifetime-extended temporary, i.e. if only we had a pointer to the foo()'s MTE at the CallExpr's CFG element, we'd be able to find the correct target region for construction: the CXXTempObjectRegion for the MTE in the StackFrameContext of foo(). So i'm proposing to add some sort of construction context to not only constructors, but also to functions that return objects, and then during construction perform the lookup in three easy steps:

  1. in the callee's CFG from constructor to return statement,
  2. through the location from the return statement to the call site,
  3. then through the caller's CFG from the call site to the MTE.

If the function is not inlined, we can still make use of the construction context to represent the return value as a LazyCompoundValue of the MTE's temporary. It would eliminate the need to replace the return value with another value while evaluating the MTE, and of course the need to re-bind the object to a different this-region.

So i believe that this is a good way to eliminate the need for the "createTemporaryRegionIfNeeded" thing in the function calls as well.



On 06/02/2018 1:41 PM, Artem Dergachev wrote:
A bit of an update.

== Temporary destructors ==

Adding some initial support for temporary destructors seems pretty easy and straightforward at this point, given the awesome work done by Manuel Klimek on our CFG a few years ago.

1. We already have the awesome CFGTemporaryDtor elements, which have the backreference to the CXXBindTemporaryExpr for their temporaries.

2. In simple cases CXXBindTemporaryExprs have an immediate constructor within them, and therefore we can provide the CXXBindTemporaryExprs as the construction context's trigger statements, and therefore have a reliable CXXTempObjectRegion for constructors.

3. Then we already track the CXXBindTemporaryExprs for the active temporaries in the program state. We can attach any constructor information to them, such as the target region, if we need to (probably we can reconstruct it by looking at the expression and the location context, not sure if we want to).

4. So when we reach the CFGTemporaryDtor element, we can just lookup all the info we need, and perform the destruction properly.

5. There's a bit of a liveness problem, because it seems that our liveness analysis tends to throw away the temporary too early. I can easily hack this problem away by marking all regions that correspond to active temporaries as live. I'll see if there's a better solution.

== CXXDefaultArgExpr problems ==

There's a known problem with those. Consider:

  void foo(const C &c = C()) {
  }

  void bar() {
    foo();
    foo();
  }

Each call of foo() contains a CXXDefaultArgExpr for c. The default argument value C() is constructed before we enter foo() and destroyed after we leave foo(). However, c's initializer, "= C()", is *not part of the AST of bar()*. In particular, when foo() is called twice, the initializer for the two calls is the same, only CXXDefaultArgExprs are different. This screws a lot of invariants in the analyzer: program points start coinciding (causing the analysis to loop and cache out), Environment doesn't expect the same expression in the same location context have two different values (suppose calls are nested into each other), analysis taking wrong branches, and so on.

Luckily, default-arg expressions that aren't zero integers or null pointers are pretty rare. Still, we'd need to eventually think how to avoid any really bad practical problems with them.

On 25/01/2018 9:08 AM, Artem Dergachev wrote:
Handling C++ temporary object construction and destruction seems to be the biggest cause of false positives on C++ code at the moment. I'd be looking into this, even though for now i don't see the whole scale of problem.

== CFG, destructors, and ProgramPoints ==

We should probably enable `-analyzer-config cfg-temporary-dtors=true` by default soon. It is a fairly low-impact change because it only alters the CFG but the analyzer rarely actually uses the new nodes. Destructors for the most part are still evaluated conservatively, with improper object regions. So it causes almost no changes in the analyzer's positives for now, but it definitely opens up room for further improvements.

I'm observing a couple of problems with this mode at the moment, namely the rich CFG destructor element hierarchy is not currently complemented by an equally rich ProgramPoint hierarchy. This causes the analysis to merge nodes which are not equivalent, for example two implicit destructors of the same type (with the same function declaration) may sometimes cause the ExplodedGraph to coil up and stop analysis (lost coverage) because of having the same program state at the erroneously-same program point. Because situations when we can guarantee a change in the program state are pretty rare, we'd have to produce more program point kinds to handle this correctly.

CallEvent hierarchy is also very much affected in a similar manner - because apparently we're constructing program points by looking at CallEvents, so they'd need to carry all the information that's needed to construct the pre-call/post-call program point.

== Construction contexts ==

We are correctly modeling "this" object region during construction/destruction of variables with automatic storage duration, fields and base classes, and on operator new() since recently, as long as these aren't arrays of objects. It was not yet implemented for other cases such as temporaries, initializer lists, fields or C++17 base classes within aggregates, and pass-by-value from/to functions (the latter being a slightly different problem than temporaries).

First of all, by "not yet implemented" i mean that instead of constructing into (destroying) the correct object (in the correct memory region), we come up with a "temporary region", which looks exactly like a region of a valid C++ temporary but is only used for communicating that it is not the right region. Then we look at the region, see that it is a temporary, and avoid inlining constructors, because it would make little sense when the region is not correct. However, if we are to model temporaries, we need another way of communicating our failure to find the correct region, which is being addressed by https://reviews.llvm.org/D42457

Also in the cases when the correct region is used, it is being computed in a funky way: in order to figure out where do we construct the object, we walk forward in the CFG (or from child to parent in the AST) to find the next/parent statement that would accomodate the newly constructed object. This means that the CFG, while perfectly telling us what to do in what order (which we, unlike CodeGen, cannot easily take from AST because we cannot afford recursive evaluation of statements, mainly because of inlining), discards too much context to be helpful in understanding how to do it.

I tried to add the information about such "trigger statements" for constructors into CFG and it is extremely helpful and easy to both use and extend. This assumes adding a new sub-class of CFGElement for constructors, which maintain a "construction context" - for now it's just a trigger statement. For instance, in

  class C { ... };
  void foo() {
    C c;
  }

...the trigger for constructor C() would be DeclStmt `C c`, and once we know this we can immediately figure out that the construction target is the region of variable `c`. Construction trigger is not necessarily a statement - it may be a CXXCtorInitializer, which is an AST node kind of its own. Additionally, when constructing aggregates via initializer lists, we may have the same statement trigger multiple constructors, eg. in

  class C { public: C(int); ~C(); };
  struct S { C c1, c2, c3; };
  void foo() {
    S s { 1, 2, 3 };
  }

... we have three different constructors (actually six different constructors if we include elidable copy constructors) for c1, c2, c3 (and lack of constructor for `s` because of the aggregate thing). It would be more natural to declare that the specific field or index would be a part of the CFG's construction context, as well as the intermediate InitListExpr, so even in these simple cases the construction context may get quite bulky. And this example is quite popular on actual code - probably the second worst cause of false positives after temporaries.

For now i have no specific plan on what would construction context for temporaries contain in the general case. I might not be able to get the data structures right from the start. In any case, it might be necessary to perform additional memory allocations for these CFG elements (for analyzer's CFG only, so it wouldn't affect compilation time or warnings).

I believe that getting the correct target region in as many cases as possible would be the main part of my work for the nearest future. And i want to move most this work to CFG, while letting the analyzer pick up the trigger statement from it and trust it as blindly as possible.

== Workflow ==

When working on operator new, i tried hard to maintain a reasonable history, making around 15 local rebases. It was not awesome because it was hard for the reviewers to understand the context of the new changes, and changes could have easily kicked in during rebases. A few lessons learned here would be to commit more aggressively, i.e. avoiding stockpiling a large history of patches (essentially a large branch), which in turn would be possible through trying harder to avoid unrelated hard-to-test core changes (as long as it doesn't require weird workarounds) that aren't covered by a flag (such as those evalCast fixes), in order to make sure reviewing take less responsibility. It's fine if some parts would later be fixed (assuming they would indeed be fixed), if it means making the turnaround faster and the tail of patches shorter - that's also the attitude i'd try to maintain when reviewing stuff myself.


_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev



_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: [analyzer] Temporaries.

Hans Wennborg via cfe-dev


On 12 April 2018 at 22:50, Artem Dergachev <[hidden email]> wrote:


On 4/12/18 1:10 PM, Gábor Horváth wrote:


On 14 February 2018 at 22:20, Artem Dergachev via cfe-dev <[hidden email]> wrote:
More explanations on how the analyzer keeps making its way around the C++ AST.

== Lifetime extension ==

This is a brain dump of how (and how much) lifetime extension of temporary objects is currently broken in the static analyzert. Spoilers: not too much, it seems, but annoying nevertheless.

Consider an example:

     1    class C {
     2    public:
     3      C() {}
     4      ~C() {}
     5    };
     6
     7    void foo() {
     8      const C &c = C();
     9    }

With the AST for the variable declaration:

      DeclStmt 0x7fa5ac85cba0 <line:8:3, col:19>
      `-VarDecl 0x7fa5ac85c878 <col:3, col:18> col:12 c 'const C &' cinit
        `-ExprWithCleanups 0x7fa5ac85cb30 <col:16, col:18> 'const C' lvalue
          `-MaterializeTemporaryExpr 0x7fa5ac85cb00 <col:16, col:18> 'const C' lvalue extended by Var 0x7fa5ac85c878 'c' 'const C &'
            `-ImplicitCastExpr 0x7fa5ac85cae8 <col:16, col:18> 'const C' <NoOp>
              `-CXXBindTemporaryExpr 0x7fa5ac85cac8 <col:16, col:18> 'C' (CXXTemporary 0x7fa5ac85cac0)
                `-CXXTemporaryObjectExpr 0x7fa5ac85ca88 <col:16, col:18> 'C' 'void ()'

*here goes a periodic reminder that CXXTemporaryObjectExpr is a sub-class of CXXConstructExpr*

Notice how MaterializeTemporaryExpr is the innermost expression (the first one in the order of execution) that is an lvalue. Essentially, you can think of it as the mythical "rvalue-to-lvalue" cast that takes in a C++ object rvalue and returns the this-value for that object. Because all C++ objects have a this-value that never changes throughout their lifetime, it is essentially their identity. Otherwise you can't call methods on them.

MaterializeTemporaryExpr also contains information about the lifetime extension process: we needed the this-value in order to bind it to variable 'c'. You see that in the AST.

In the analyzer, however, MaterializeTemporaryExpr does a different thing, as a temporary solution (no pun intended). It constructs a new temporary region out of thin air and binds the rvalue object to that temporary in the Store. The respective function in our code is called "createTemporaryRegionIfNeeded". It also has a separate purpose of converting rvalue sub-object adjustments into lvalue sub-object adjustments, which we wouldn't discuss this time.

Now that we learned how to inline temporary constructors and destructors, it essentially means that the this-value in the constructor and in the destructor would be different. Because first we construct the object into temporary region R1, then we take lazyCompoundVal{R1} to represent the value of CXXTemporaryObjectExpr, then we materialize lazyCompoundVal{R1} to R2, then we bind R2 to variable 'c', then we call the automatic(!) destructor for 'c' which contains R2. To be clear, the region store at the time of destruction would be:

  c: R2,
  R2: lazyCompoundVal{R1}.

It means that fields of the object would contain the correct values, there would be the correct number of destructors called (no temporary destructors, just one automatic destructor), but the identity of the object (this-value) would change in the process. Unless the object actually makes any decisions or does any manipulations that involve its this-value, the modeling should be correct. When the object starts to actively use its this-value in its inlined methods, the analysis would do wrong stuff. Additionally, it causes a mess in the checkers when they try to track objects by their this-values - i.e. IteratorChecker has a lot of additional code to work around the fact that the region for the object constantly changes.

From the above it is clear that MaterializeTemporaryExpr should not construct any new regions, at least not in this case. We already have the correct region, namely R1, which should be re-used.

Hi Artem!

We found a strange false positive that might be related to what you describe above but not sure though. Could you take a look?
It looks like we are seeing a null pointer dereference error, and the null value comes from the destructor which was invoked on a temporary.
If this is not the case, the path diagnostic might be misleading.

Regards,
Gábor

Hmm, i don't fully understand it yet. It seems to me that RefHash3KeysIdPoolEnumerator drains the whole pool upon destruction (fIdPtrs is not a member of the temporary, it's an external entity), so it indeed can't really be safely passed around or copied (i.e. elidable copies are not moves).

Oh, I think you are right! Somehow I assumed the there is a deep copy going on but after looking at the copy constructor, it looks like that is not the case. Sorry for bothering :)
 

So i'd easily believe that this code only works because all copies are elided, i.e. the code is not portable (at least not until C++17) but usually works because most compilers are clever enough. We'll probably get rid of such positives when we implement copy elision.

In case i got it all wrong, do you accidentally have a reproducer for me to have a closer look? If CTU stuff is hard to provide a reproducer for, you should be able to write a small code snippet directly into RefHash3KeysIdPool.c to reproduce the problem. I'll also accept a trimmed (as in -trim-egraph) exploded graph dot file even if it's huge.

P.S. The "Calling..." icon is hilarious :D

 

It is tempting to take R1 directly from lazyCompoundVal{R1} - it already has memories about once being a value of R1. I'm not sure it's not going to work - it may work, at least i'm not ready to come up with a counterexample. But the meaning of LazyCompoundVal's parent region is different and coincides with what we want just accidentally. Namely, lazyCompoundVal{R1} is a value of an object that was bound to R1 in some particular moment of time in the past, without any explanation of when this moment of time was - but there's no indication if R1 is the region of the temporary we've just constructed, or a region of an unrelated object that used to have the same value back then. As we'd see later, MaterializeTemporaryExpr doesn't always contain a constructor within it - there are a lot of cases to cover, and if the trick doesn't work even once, it's going to be hard, so i'd probably not going to commit into maintaining this invariant. Though it might be plausible to modify add an SVal kind that does exactly what we mean here - i.e. a value that does indeed correspond to a specific C++ object identified by region. It might be a beautiful solution, but it may also fail miserably if tricky cornercases show up - so i'm not ready to commit to that. Also the correct way of dealing with such values (i.e. for how long are they relevant?) would be extremely difficult to explain to checker developers.

The more straightforward approach here is to include MaterializeTemporaryExpr (hereinafter MTE) into the construction context. It means, if a temporary that we're about to construct would be lifetime-extended later, we'd rather know about that during construction, and maintain a map in the program state from MTE to their respective temporary regions that were used for representing the respective construction targets. Upon encountering the respective MTE we'd simply retrieve the implicit temporary storage for the value from the program state and declare that temporary region to be the value of the MTE. This would mimic the approach we have with CXXBindTemporaryExprs (hereinafter BTE) and their respective regions that allows temporary destructors to work - but this time it's going to be about MaterializeTemporaryExprs and automatic destructors. I imagine that on the checker side this can potentially be exposed via some sort of State->getTemporaryStorage(Expr) call, but i believe that generally this process should be as transparent to the checkers as possible.

It sounds as if both of these maps could be eliminated by always making sure that the target temporary is constructed "with" the MTE (for lifetime-extended temproraries) or BTE (for temporaries that require destruction at the end of full-expression). In this case, with the help of construction context-assisted lookahead, we declare that the target of the construction is CXXTempObjectRegion(MTE, LC) or CXXTempObjectRegion(BTE, LC) respectively, rather than CXXTempObjectRegion(CXXConstructExpr). Then during evaluation of MTE or BTE we'd simply construct the same region with the expression we're currently evaluating, and it's automagically going to be the correct region. This approach, however, becomes confusing when we start dealing with elidable constructors (explained below). So for now i believe that it is quite irrelevant which expression is identifying the temporary region.

== Elidable constructors ==

While it doesn't sound like an immediately important task to implement copy elision in the analyzer, it may help with making some things easier. And it'd also make some reports fancier, as mentioned in https://reviews.llvm.org/D43144.

Elidable copy-constructors can be explained as a form of lifetime extension. Instead of copying the temporary, they keep using the original value of the temporary, which in some pretty twisted sense means that they are lifetime-extending it to be able to use it. For example, if we modify our example by replacing the lifetime-extending reference variable with a value-type variable:

     1    class C {
     2    public:
     3      C() {}
     4      ~C() {}
     5    };
     6
     7    void foo() {
     8      C c = C();
     9    }

...then we'd still have an MTE, even though lifetime extension would seem to be gone:

      DeclStmt 0x7fb8f005afb8 <line:8:3, col:12>
      `-VarDecl 0x7fb8f005ac50 <col:3, col:11> col:5 c 'C' cinit
        `-ExprWithCleanups 0x7fb8f005afa0 <col:9, col:11> 'C'
          `-CXXConstructExpr 0x7fb8f005af68 <col:9, col:11> 'C' 'void (const C &) noexcept' elidable
            `-MaterializeTemporaryExpr 0x7fb8f005af00 <col:9, col:11> 'const C' lvalue
              `-ImplicitCastExpr 0x7fb8f005aee8 <col:9, col:11> 'const C' <NoOp>
                `-CXXBindTemporaryExpr 0x7fb8f005aec8 <col:9, col:11> 'C' (CXXTemporary 0x7fb8f005aec0)
                  `-CXXTemporaryObjectExpr 0x7fb8f005ae88 <col:9, col:11> 'C' 'void ()'

In this case the MTE is expressing the fact that the temporary constructed via CXXTemporaryObjectExpr can be "lifetime-extended" (by actually merging it with the stack variable) rather than copied, if the CXXConstructExpr surrounding it would be chosen to be elided. The AST doesn't make the elision choice for us - but is compatible with both choices. The MTE essentially overrides the necessity of immediate destruction provided by the BTE, and lets the surrounding AST decide upon the lifetime of the object.

Because the analyzer currently does not do copy elision, it will use the MTE only to compute the argument for the elidable copy-constructor, and then perform the copy-construction, and then destroy the original temporary at the end of the full-expression. Note, however, that in this case we need to properly support both the BTE (for the temporary destructor to work) and the MTE (for computing its value). We need to implement the MTE's ability to perform "rvalue-to-lvalue-cast" even if the temporary destruction is still necessary. For this reason, if we rely on constructing temporary regions with the correct BTEs or MTEs, at least one of these tasks becomes impossible to perform.

If we were to support copy elision, then the CXXTemporaryObjectExpr constructor would go directly into the variable region. For the purposes of modeling, it'd mean that only CXXTemporaryObjectExpr would actually need to be modeled. But this would require additional coding in the construction context to be able to realize that the target is the variable while modeling the CXXTemporaryObjectExpr.

For the sake of completeness, let's consider the ternary operator example:

     1    class C {
     2    public:
     3      C(int) {}
     4      ~C() {}
     5    };
     6
     7    void foo(int coin) {
     8      const C &c = coin ? C(1) : C(2);
     9    }

The respective AST would be:

      DeclStmt 0x7fc1e20023e0 <line:8:3, col:34>
      `-VarDecl 0x7fc1e2001dc8 <col:3, col:33> col:12 c 'const C &' cinit
        `-ExprWithCleanups 0x7fc1e2002370 <col:16, col:33> 'const C' lvalue
          `-MaterializeTemporaryExpr 0x7fc1e2002340 <col:16, col:33> 'const C' lvalue extended by Var 0x7fc1e2001dc8 'c' 'const C &'
            `-ImplicitCastExpr 0x7fc1e2002328 <col:16, col:33> 'const C' <NoOp>
              `-ConditionalOperator 0x7fc1e20022f8 <col:16, col:33> 'C'
                |-ImplicitCastExpr 0x7fc1e2002170 <col:16> 'bool' <IntegralToBoolean>
                | `-ImplicitCastExpr 0x7fc1e2002158 <col:16> 'int' <LValueToRValue>
                |   `-DeclRefExpr 0x7fc1e2001e28 <col:16> 'int' lvalue ParmVar 0x7fc1e2001c18 'coin' 'int'
                |-CXXBindTemporaryExpr 0x7fc1e2002248 <col:23, col:26> 'C' (CXXTemporary 0x7fc1e2002240)
                | `-CXXConstructExpr 0x7fc1e2002208 <col:23, col:26> 'C' 'void (const C &) noexcept' elidable
                |   `-MaterializeTemporaryExpr 0x7fc1e20021a0 <col:23, col:26> 'const C' lvalue
                |     `-ImplicitCastExpr 0x7fc1e2002188 <col:23, col:26> 'const C' <NoOp>
                |       `-CXXFunctionalCastExpr 0x7fc1e2002078 <col:23, col:26> 'C' functional cast to class C <ConstructorConversion>
                |         `-CXXBindTemporaryExpr 0x7fc1e2002058 <col:23, col:26> 'C' (CXXTemporary 0x7fc1e2002050)
                |           `-CXXConstructExpr 0x7fc1e2002018 <col:23, col:26> 'C' 'void (int)'
                |             `-IntegerLiteral 0x7fc1e2001e60 <col:25> 'int' 1
                `-CXXBindTemporaryExpr 0x7fc1e20022d8 <col:30, col:33> 'C' (CXXTemporary 0x7fc1e20022d0)
                  `-CXXConstructExpr 0x7fc1e2002298 <col:30, col:33> 'C' 'void (const C &) noexcept' elidable
                    `-MaterializeTemporaryExpr 0x7fc1e2002280 <col:30, col:33> 'const C' lvalue
                      `-ImplicitCastExpr 0x7fc1e2002268 <col:30, col:33> 'const C' <NoOp>
                        `-CXXFunctionalCastExpr 0x7fc1e2002130 <col:30, col:33> 'C' functional cast to class C <ConstructorConversion>
                          `-CXXBindTemporaryExpr 0x7fc1e2002110 <col:30, col:33> 'C' (CXXTemporary 0x7fc1e2002108)
                            `-CXXConstructExpr 0x7fc1e20020d0 <col:30, col:33> 'C' 'void (int)'
                              `-IntegerLiteral 0x7fc1e20020b0 <col:32> 'int' 2

Each branch contains two constructors: the temporary and the elidable copy. The temporaries are surrounded with their respective BTEs and copy-elision-kind MTEs, which indicates that they need to be either destroyed as temporaries, or, if copy elision is chosen, have their lifetime decided upon by the surrounding AST. The elidable copy constructors also, being temporaries, have their respective BTEs. Note, however, that there is only one MTE for both BTEs for the elidable constructors.

So after the conditional operator is resolved (which is the first thing we need to do, according to the CFG), we'd go ahead and perform the constructors, and their trigger would be their respective BTE in the non-elide case, and the single top-level MTE in the elide case. In the non-elide case, copy constructors would be triggered by the top-level MTE.

It means that, once again, copy elision would prevent us from handling both the BTE and the copy-elision-kind MTE in the single construction, allowing the "predictable target region" trick to work: when we need the temporary destructor, we construct directly into CXXTempObjectRegion of the BTE and it gets automatically picked up during destruction, and when we need the automatic destructor, we construct directly into CXXTempObjectRegion of the MTE and we can easily compute the value of the MTE. But when we don't do copy elision, we'd have to keep at least one of those in the program state map.

== Return by value ==

Returning C++ objects by value is actually very similar to constructing it. Consider:

     1    class C {
     2    public:
     3      C() {}
     4      ~C() {}
     5    };
     6
     7    C bar() {
     8      C c;
     9      return c;
    10    }
    11
    12    void foo() {
    13      const C &c = bar();
    14    }

With the respective AST for DeclStmt in foo():

      DeclStmt 0x7fe62c84f8e8 <line:13:3, col:21>
      `-VarDecl 0x7fe62c84f6b8 <col:3, col:20> col:12 c 'const C &' cinit
        `-ExprWithCleanups 0x7fe62c84f878 <col:16, col:20> 'const C' lvalue
          `-MaterializeTemporaryExpr 0x7fe62c84f848 <col:16, col:20> 'const C' lvalue extended by Var 0x7fe62c84f6b8 'c' 'const C &'
            `-ImplicitCastExpr 0x7fe62c84f830 <col:16, col:20> 'const C' <NoOp>
              `-CXXBindTemporaryExpr 0x7fe62c84f810 <col:16, col:20> 'C' (CXXTemporary 0x7fe62c84f808)
                `-CallExpr 0x7fe62c84f7e0 <col:16, col:20> 'C'
                  `-ImplicitCastExpr 0x7fe62c84f7c8 <col:16> 'C (*)()' <FunctionToPointerDecay>
                    `-DeclRefExpr 0x7fe62c84f770 <col:16> 'C ()' lvalue Function 0x7fe62c84f190 'bar' 'C ()'

And for the ReturnStmt in bar():

      ReturnStmt 0x7fe62c84f5b0 <line:9:3, col:10>
      `-CXXConstructExpr 0x7fe62c84f578 <col:10> 'C' 'void (const C &) noexcept' elidable
        `-ImplicitCastExpr 0x7fe62c84f518 <col:10> 'const C' lvalue <NoOp>
          `-DeclRefExpr 0x7fe62c84f4f0 <col:10> 'C' lvalue Var 0x7fe62c84f280 'c' 'C'

Since https://reviews.llvm.org/D42875 we can already realize that the constructor in bar(), assuming that we're inlining bar() during analysis, would be constructed into something that is a return value of bar(). This allows us, by looking that the StackFrameContext's call site, to figure out that it is being constructed into the CallExpr in foo(). Now if only we knew that that the call site is a lifetime-extended temporary, i.e. if only we had a pointer to the foo()'s MTE at the CallExpr's CFG element, we'd be able to find the correct target region for construction: the CXXTempObjectRegion for the MTE in the StackFrameContext of foo(). So i'm proposing to add some sort of construction context to not only constructors, but also to functions that return objects, and then during construction perform the lookup in three easy steps:

  1. in the callee's CFG from constructor to return statement,
  2. through the location from the return statement to the call site,
  3. then through the caller's CFG from the call site to the MTE.

If the function is not inlined, we can still make use of the construction context to represent the return value as a LazyCompoundValue of the MTE's temporary. It would eliminate the need to replace the return value with another value while evaluating the MTE, and of course the need to re-bind the object to a different this-region.

So i believe that this is a good way to eliminate the need for the "createTemporaryRegionIfNeeded" thing in the function calls as well.



On 06/02/2018 1:41 PM, Artem Dergachev wrote:
A bit of an update.

== Temporary destructors ==

Adding some initial support for temporary destructors seems pretty easy and straightforward at this point, given the awesome work done by Manuel Klimek on our CFG a few years ago.

1. We already have the awesome CFGTemporaryDtor elements, which have the backreference to the CXXBindTemporaryExpr for their temporaries.

2. In simple cases CXXBindTemporaryExprs have an immediate constructor within them, and therefore we can provide the CXXBindTemporaryExprs as the construction context's trigger statements, and therefore have a reliable CXXTempObjectRegion for constructors.

3. Then we already track the CXXBindTemporaryExprs for the active temporaries in the program state. We can attach any constructor information to them, such as the target region, if we need to (probably we can reconstruct it by looking at the expression and the location context, not sure if we want to).

4. So when we reach the CFGTemporaryDtor element, we can just lookup all the info we need, and perform the destruction properly.

5. There's a bit of a liveness problem, because it seems that our liveness analysis tends to throw away the temporary too early. I can easily hack this problem away by marking all regions that correspond to active temporaries as live. I'll see if there's a better solution.

== CXXDefaultArgExpr problems ==

There's a known problem with those. Consider:

  void foo(const C &c = C()) {
  }

  void bar() {
    foo();
    foo();
  }

Each call of foo() contains a CXXDefaultArgExpr for c. The default argument value C() is constructed before we enter foo() and destroyed after we leave foo(). However, c's initializer, "= C()", is *not part of the AST of bar()*. In particular, when foo() is called twice, the initializer for the two calls is the same, only CXXDefaultArgExprs are different. This screws a lot of invariants in the analyzer: program points start coinciding (causing the analysis to loop and cache out), Environment doesn't expect the same expression in the same location context have two different values (suppose calls are nested into each other), analysis taking wrong branches, and so on.

Luckily, default-arg expressions that aren't zero integers or null pointers are pretty rare. Still, we'd need to eventually think how to avoid any really bad practical problems with them.

On 25/01/2018 9:08 AM, Artem Dergachev wrote:
Handling C++ temporary object construction and destruction seems to be the biggest cause of false positives on C++ code at the moment. I'd be looking into this, even though for now i don't see the whole scale of problem.

== CFG, destructors, and ProgramPoints ==

We should probably enable `-analyzer-config cfg-temporary-dtors=true` by default soon. It is a fairly low-impact change because it only alters the CFG but the analyzer rarely actually uses the new nodes. Destructors for the most part are still evaluated conservatively, with improper object regions. So it causes almost no changes in the analyzer's positives for now, but it definitely opens up room for further improvements.

I'm observing a couple of problems with this mode at the moment, namely the rich CFG destructor element hierarchy is not currently complemented by an equally rich ProgramPoint hierarchy. This causes the analysis to merge nodes which are not equivalent, for example two implicit destructors of the same type (with the same function declaration) may sometimes cause the ExplodedGraph to coil up and stop analysis (lost coverage) because of having the same program state at the erroneously-same program point. Because situations when we can guarantee a change in the program state are pretty rare, we'd have to produce more program point kinds to handle this correctly.

CallEvent hierarchy is also very much affected in a similar manner - because apparently we're constructing program points by looking at CallEvents, so they'd need to carry all the information that's needed to construct the pre-call/post-call program point.

== Construction contexts ==

We are correctly modeling "this" object region during construction/destruction of variables with automatic storage duration, fields and base classes, and on operator new() since recently, as long as these aren't arrays of objects. It was not yet implemented for other cases such as temporaries, initializer lists, fields or C++17 base classes within aggregates, and pass-by-value from/to functions (the latter being a slightly different problem than temporaries).

First of all, by "not yet implemented" i mean that instead of constructing into (destroying) the correct object (in the correct memory region), we come up with a "temporary region", which looks exactly like a region of a valid C++ temporary but is only used for communicating that it is not the right region. Then we look at the region, see that it is a temporary, and avoid inlining constructors, because it would make little sense when the region is not correct. However, if we are to model temporaries, we need another way of communicating our failure to find the correct region, which is being addressed by https://reviews.llvm.org/D42457

Also in the cases when the correct region is used, it is being computed in a funky way: in order to figure out where do we construct the object, we walk forward in the CFG (or from child to parent in the AST) to find the next/parent statement that would accomodate the newly constructed object. This means that the CFG, while perfectly telling us what to do in what order (which we, unlike CodeGen, cannot easily take from AST because we cannot afford recursive evaluation of statements, mainly because of inlining), discards too much context to be helpful in understanding how to do it.

I tried to add the information about such "trigger statements" for constructors into CFG and it is extremely helpful and easy to both use and extend. This assumes adding a new sub-class of CFGElement for constructors, which maintain a "construction context" - for now it's just a trigger statement. For instance, in

  class C { ... };
  void foo() {
    C c;
  }

...the trigger for constructor C() would be DeclStmt `C c`, and once we know this we can immediately figure out that the construction target is the region of variable `c`. Construction trigger is not necessarily a statement - it may be a CXXCtorInitializer, which is an AST node kind of its own. Additionally, when constructing aggregates via initializer lists, we may have the same statement trigger multiple constructors, eg. in

  class C { public: C(int); ~C(); };
  struct S { C c1, c2, c3; };
  void foo() {
    S s { 1, 2, 3 };
  }

... we have three different constructors (actually six different constructors if we include elidable copy constructors) for c1, c2, c3 (and lack of constructor for `s` because of the aggregate thing). It would be more natural to declare that the specific field or index would be a part of the CFG's construction context, as well as the intermediate InitListExpr, so even in these simple cases the construction context may get quite bulky. And this example is quite popular on actual code - probably the second worst cause of false positives after temporaries.

For now i have no specific plan on what would construction context for temporaries contain in the general case. I might not be able to get the data structures right from the start. In any case, it might be necessary to perform additional memory allocations for these CFG elements (for analyzer's CFG only, so it wouldn't affect compilation time or warnings).

I believe that getting the correct target region in as many cases as possible would be the main part of my work for the nearest future. And i want to move most this work to CFG, while letting the analyzer pick up the trigger statement from it and trust it as blindly as possible.

== Workflow ==

When working on operator new, i tried hard to maintain a reasonable history, making around 15 local rebases. It was not awesome because it was hard for the reviewers to understand the context of the new changes, and changes could have easily kicked in during rebases. A few lessons learned here would be to commit more aggressively, i.e. avoiding stockpiling a large history of patches (essentially a large branch), which in turn would be possible through trying harder to avoid unrelated hard-to-test core changes (as long as it doesn't require weird workarounds) that aren't covered by a flag (such as those evalCast fixes), in order to make sure reviewing take less responsibility. It's fine if some parts would later be fixed (assuming they would indeed be fixed), if it means making the turnaround faster and the tail of patches shorter - that's also the attitude i'd try to maintain when reviewing stuff myself.


_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev




_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: [analyzer] Temporaries.

Hans Wennborg via cfe-dev
In reply to this post by Hans Wennborg via cfe-dev
A bit of an update. Previous messages for easier navigation through this
thread:

http://lists.llvm.org/pipermail/cfe-dev/2018-January/056691.html
http://lists.llvm.org/pipermail/cfe-dev/2018-February/056813.html
http://lists.llvm.org/pipermail/cfe-dev/2018-February/056898.html
http://lists.llvm.org/pipermail/cfe-dev/2018-February/056909.html
http://lists.llvm.org/pipermail/cfe-dev/2018-February/056929.html
http://lists.llvm.org/pipermail/cfe-dev/2018-March/057255.html
http://lists.llvm.org/pipermail/cfe-dev/2018-March/057357.html
http://lists.llvm.org/pipermail/cfe-dev/2018-April/057641.html


== Story so far ==

Our AST for C++ constructors is rather unusual: the this-argument of the
construct-expression is not its sub-expression but is instead scattered
around its parent expressions. For example, constructor within 'A a(1,
2, 3)' has AST

DeclStmt
`- VarDecl 'a'
     `- CXXConstructExpr
       |- 1
       |- 2
       `- 3

from which it can be seen that it constructs variable 'a', but there's
no information about variable 'a' within CXXConstructExpr itself or its
children. This lead to problems within the analyzer that was unable to
figure out what object is constructed by looking at the CFG statements
that go in order of execution (first CXXConstructExpr, then DeclStmt).
Additionally, this leads to problems with liveness analysis, because the
constructor ends up putting stuff into a memory region that isn't yet live.

In order to deal with that, i've augmented the CFGElement for the
construct-expression to provide a ConstructionContext object that
captures all necessary parent statements. Whenever CFG provides a
ConstructionContext, it is easy for the analyzer to work correctly. This
helped us support many new cases of object construction that weren't
previously supported, including temporary object construction and
construction into operator new(). This helped us suppress huge amounts
of false positives, noticeably we can now produce reasonable results on
WebKit which is a relatively exotic C++ codebase. Still, many more cases
need to be handled.


== Plans ==

I'll probably focus on adding support for copy elision first. A few
mails ago i explained how important this feature is, and it is probably
also the biggest self-contained chunk of work that remains in this realm
so far. I'll start with a bit of refactoring because some technical debt
remains - see below :)


== Simple variables and liveness ==

So far i paid relatively little attention to how the simple case

   A a(1, 2, 3);

works. It kidna worked, so i expected it to not need fixing apart from
the simple refactoring to switch from CFG lookahead to the
ConstructionContext. However when i looked at
https://bugs.llvm.org/show_bug.cgi?id=37270 it turned out to be much
worse than i expected.

The CFG for that would look like this:

   CXXConstructExpr (prvalue expression of type A, construction context
points to the DeclStmt)
   ... (sometimes some irrelevant implicit stuff in between)
   DeclStmt 'a'

Now let's see. Assume there's a construction context.

(a) The way i expected it to have worked:

   1. CXXConstructExpr is modeled and produces bindings to 'a'. It
evaluates to LazyCompoundVal of 'a'.
   2. DeclStmt doesn't need to be modeled because bindings are already
there.

(b) The way it might as well have worked:

   1. CXXConstructExpr is modeled and produces bindings to 'a'. It
evaluates to LazyCompoundVal of 'a'.
   2. DeclStmt is modeled by binding the value of its initializer, which
is a LazyCompoundVal of 'a', to 'a'.

(c) The way it actually turned out to work:

   1. CXXConstructExpr is modeled and produces bindings to 'a'. It
evaluates to MemRegionVal '&a' (wat?).
   2. DeclStmt is modeled by binding the LazyCompoundVal of 'a' that is
loaded from its initializer '&a' to 'a' (like (b).2 just with a load).

On (c).1 things get really weird because CXXConstructExpr is a prvalue
expression of object type, and therefore must be modeled as a NonLoc.
The load on (c).2 doesn't really correspond to any meaningful AST or
semantics here.

In order to regain some sanity, i tried to see what was wrong with (a)
and (b). Approach (b) is actually relatively easy to implement, however
it has a downside of producing a default LazyCompoundVal binding in the
Store instead of many direct bindings normally produced by an inlined
constructor. Apart from the performance overhead of looking through an
extra LazyCompoundVal every time we load from the variable later, we'll
have analysis precision suffer because RegionStore is bad at modeling
binding extents. There is a variety of tests in our test suite that
would degrade because of that.

So it's indeed useful to try to preserve the bindings as they were bound
by the inlined constructor.

Now, would (a) actually work? NO!!! Because, well, all of a sudden we
find out that now bindings to 'a' are dead in sense of liveness analysis
and are removed from the Store. And the fact that they're still present
within the LazyCompoundVal won't help us on (a).2 because we promised to
not bind the LazyCompoundVal. Yet it worked just fine in (c) because the
bindings were kept alive because region '&a' was kept alive because it
was incorrectly bound to the CXXConstructExpr in the Environment!

Here comes the moment of truth. Construction contexts for operator new
and temporaries all had their own program state traits to prevent the
memory region from dying until we leave the construction site.
Apparently, these construction context kinds *were not special*.
Essentially, every kind of construction context needs a path-sensitive
program state trait in order to work.

--

Now, why path-sensitive? In case of temporaries and operator new it's
kinda obvious, but in case of a variable we could simply declare "please
don't remove bindings to this variable on that whole sub-tree", right?
Right. But our construction contexts are imperfect, and, unfortunately,
step 1 doesn't always work. If a variable is constructed with an
unsupported construction context on a certain path, we need to use
method (b).2 as our last resort: if the construction goes into a dummy
region, we need to take the constructed LazyCompoundValue and bind it to
our variable.

The current code for that turned out to be outdated as well. Instead of
looking at whether we've had a construction context, we're looking at
whether we've had a constructor, via CFG look-behind that's a reverse of
how previously construction contexts worked through CFG look-ahead, see
findDirectConstructorForCurrentCFGElement(). The aforementioned bugzilla
bug is essentially a bug in this approach. We could have fixed it by
adding extra logic into findDirectConstructorForCurrentCFGElement() to
skip more statements, but it'd eventually duplicate a lot of logic for
finding construction contexts. And i'm not sure we'd be able to make it
work correctly for path-sensitive copy elision, such as C++17 mandatory
copy elision within the ?: operator, where the constructor may be in a
different CFG block and we might need to scan the whole CFG to find it.

So that's one more reason to have a path-sensitive program state trait
even for simple variables: we'll be able to figure out if construction
target for the variable was modeled precisely. Hopefully we'll be able
to get rid of that when our construction contexts become precise and
cover all cases, but for now we can't.

My plan is to get rid of multiple state traits for
new/destructors/materializations/etc. and make a single program state
trait ("objects under construction") to rule them all - now that it
sounds as if we'll always need it anyway. Then use the new trait to fix
those some constructor modeling. I think the hopefully-minimal run-time
overhead (which may actually be paid off with the removal of the
look-behind) is worth it when it comes to maintaining our Loc vs. NonLoc
invariants, presenting expression values correctly to the checkers,
keeping our code small and at all possible to understand, and allowing
us to move further.
_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev