[cfe-dev] CFG temporary objects destructors

[Ted Kremenek]

On Oct 24, 2010, at 7:57 PM, Zhongxing Xu <xuzhongxing at gmail.com> wrote:

> 
> 
> On Mon, Oct 25, 2010 at 2:13 AM, Ted Kremenek <kremenek at apple.com> wrote:
> On Oct 22, 2010, at 10:41 PM, Zhongxing Xu <xuzhongxing at gmail.com> wrote:
> 
>> 
>> 
>> 2010/10/23 Ted Kremenek <kremenek at apple.com>
>> On Oct 17, 2010, at 3:06 PM, Marcin Świderski wrote:
>> 
>> > Blocks structure that is constructed is fine, but I don't know what to use for terminator of block initiating the branch and for first element in block closing the branch (I didn't check this yet, but I think that it could be used during backward analysis). Could I use fake if/else statement for this? Similar solution is used to make every declaration into separate statement.
>> 
>> What we could do is generalize terminators in the same way we did with CFGElements.  Right now terminators are Stmt*, but they could be something like CFGTerminator, which could discriminate between regular terminators and those used for blocks guarding destructor calls.  The CFGTerminator for those blocks could essentially be the same Stmt* as the terminator guarding the block with the constructor, but with a special bit indicating it is for the matching destructor(s).  The nice thing about this approach is that it naturally ties the two blocks together, they can share the same condition values, etc.
>> 
>> We need a way to convey the branch information to the second logical op used as terminator. At first we bind logical op to a UndefinedVal which indicates which branch is taken. Then the logical op is bound to its real value. At the second terminator where the logical op appears, we still need the taken branch information to decide which branch to take.
> 
> Indeed.  After thinking about this some more, we can't just keep a reference the original block-level expression that represented the branch condition and hope that is enough.  That expression's SVal should still be in the Environment (since it would still be live), and we could use it a second time when deciding the branch.  That only works, however, if we only took a single branch (not both of them) and the SVal didn't reference any symbolic values (which depend on state).  Thus recording the branch taken seems to be the most accurate and simplest approach.
> 
> We could possibly insert this information into the Environment (possibly using some bit mangling for the Stmt* key value), have the data value represent the branch taken, and then have the liveness of that entry be the same as the liveness of the original condition expression.
> 
> For example, in A || B, the expression 'A' is used to determine the first branch.  For that, we have a block-level expression (a Stmt*) which serves as a condition for the terminator '||'.  That value gets inserted into the Environment as part of regular evaluation, and stays live until after we are done with evaluating the '||' terminator (LiveVariables analysis does this for us).  In addition, we could insert another entry whose key is similar to the one for the block-level expression but instead has a bit twiddled (e.g., we take the Stmt* for 'A', which represents the condition value used for the first branch, and then bit-mangle it).  We could use that to record what branch we took, and keep that entry around as long as the original block-level expression (e.g., the Stmt* for 'A') would stay in the Environment.  That value's lifetime would get extended by having a special CFGTerminator that referenced that block-level expression and represented the terminator for jumping to the block with the destructor calls.  We then consult the branch value when choosing what block to jump to for the destructors.
> 
> That means we need to modify the dataflow solver since the Terminator does not participate the dataflow computation for now, right? 

Perhaps. We only need to model this if we care about the flow-sensitive (path-insensitive) dataflow solver caring about infeasible paths where A() is called but ~A() is not (which would be the case if we ignored these branch conditions).  If we didn't care about such control-dependencies (which we ignore for a ton of other things for basic dataflow analysis) then it doesn't really matter.

However, modeling this in the dataflow solver would be possible.  We'd just need to model some path-sensitivity, which means we'd have multiple dataflow facts associated with a ProgramPoint (each with a condition "guard" of what destructor blocks to run).  Modeling such path-sensitivity in the dataflow solver would be similar to how dataflow analysis is described in the ESP paper (Microsoft).  It also means that the analysis can become exponential, since it is path-sensitive, although it might not in the common case when it comes to tracking destructor guards because of how constructors and destructors are balanced.

My guess is that modeling such "basic" path-sensitivity is not going to buy us anything for most simple dataflow analyses.  When we care about path precision, we can rely on the path-sensitive engine.  At the very least this is a reasonable starting point; if we find we need more precision in the flow-sensitive dataflow analysis engine, we can always refine it.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20101024/9e1d83f9/attachment.html>