CFG temporary objects destructors

Hi

I’m currently working on modeling destructors of temporary objects in CFG. I’ve attached patch with prototype implementation and some tests.

After some thinking I’ve decided to add additional step with forward traversing of AST for every CXXExprWithTemporaries node. During this step destructors are added to CFG for every CXXBindTemporaryExpr (with special case for binding const reference to temporary). However I have a problem with branching for destructors that have to be called conditionaly. 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.

  • Marcin

cfg-temp-obj-dtor.patch (15.7 KB)

temp_dtors_test.cpp (1.08 KB)

Hi Marcin,

Aside from your other comment (which I will get to later), I had a question about the following:

+CFGBlock *CFGBuilder::VisitBinaryOperatorForTemporaryDtors(BinaryOperator *E) {
+ if (E->isLogicalOp()) {
+ // Destructors for temporaries in LHS expression should be called after
+ // those for RHS expression. Even if this will unnecessarily create a block,
+ // this block will be used at least by the full expression.

In the CFG, where we must represent control-flow between the LHS and RHS subexpressions, we actually have the RHS appear first in the CFG. I believe, however, that the compiler chooses the reverse direction. Should we reverse it to match? I think your logic here assumes that the LHS temporaries are created first.

Ted

More specifically, my comment applies to the following code:

+CFGBlock *CFGBuilder::VisitBinaryOperatorForTemporaryDtors(BinaryOperator *E) {
+ if (E->isLogicalOp()) {
+ // Destructors for temporaries in LHS expression should be called after
+ // those for RHS expression. Even if this will unnecessarily create a block,
+ // this block will be used at least by the full expression.

Basically this assumption doesn't match how we treat binary operators in the CFG. We should probably fix having the LHS always precessed first. Any objections?

I think I understand what you are getting at, but could you provide a code example to illustrate?

W dniu 21 października 2010 06:36 użytkownik Ted Kremenek <kremenek@apple.com> napisał:

Understood. The point I was trying to convey was that for non-logical binary operators it is the case that the RHS appears in the CFG before the LHS, which doesn’t match the compiler’s behavior. For logical operators, I think everything is working as expected.

2010/10/21 Ted Kremenek <kremenek@apple.com>

When the binary operator is logical operator, why we need to replicate the control flow when adding the dtors in LHS and RHS? Could we just add the dtor right after where the LHS and RHS are evaluated?

That is, for code

A && B

we generate CFG like this:

A && B
~A()


B
~B()

A && B

Since in logical binary operator, we only need the boolean value. The temporary object can be destroyed right after it is evaluated.

2010/10/18 Marcin Świderski <marcin.sfider@gmail.com>

W dniu 22 października 2010 11:22 użytkownik Zhongxing Xu <xuzhongxing@gmail.com> napisał:

When the binary operator is logical operator, why we need to replicate the control flow when adding the dtors in LHS and RHS? Could we just add the dtor right after where the LHS and RHS are evaluated?

That is, for code

A && B

we generate CFG like this:

A && B
~A()


B
~B()

A && B

Since in logical binary operator, we only need the boolean value. The temporary object can be destroyed right after it is evaluated.

This depends on how much we want to simulate real control flow of expression. C++ standard states that destructors of temporaries should be called at the end of full expression and in reverse order of their construction. Your example does not satisfy this. It only guaranties that destructor for temporary will be called.

I think Zhongxing is right. Here is what the compiler does:

$ cat t.cpp

class A {
public:
A();
~A();
operator bool();
};
class B {
public:
B();
~B();
operator bool();
};

A foo();
B bar();

int test() {
return foo() || bar();
}

$ /Developer/usr/bin/clang -S t.cpp -O2 -fno-exceptions
$ cat t.s | c++filt

test(): ## @_Z4testv
Leh_func_begin0:

BB#0: ## %entry

pushq %rbp
Ltmp0:
movq %rsp, %rbp
Ltmp1:
pushq %r14
pushq %rbx
subq $16, %rsp
Ltmp2:
leaq -24(%rbp), %rbx
movq %rbx, %rdi
callq foo()
movq %rbx, %rdi
callq A::operator bool()
testb %al, %al
movl $1, %ebx
jne LBB0_2

BB#1: ## %temp.cond-dtor.call

leaq -32(%rbp), %rbx
movq %rbx, %rdi
callq bar()
movq %rbx, %rdi
callq B::operator bool()
movb %al, %r14b
movq %rbx, %rdi
callq B::~B()
movzbl %r14b, %ebx
LBB0_2: ## %temp.cond-dtor.cont
leaq -24(%rbp), %rdi
callq A::~A()
movl %ebx, %eax
addq $16, %rsp
popq %rbx
popq %r14
popq %rbp
ret
Leh_func_end0:

We can clearly see that there are 3 basic blocks and only 1 conditional branch. Notice that ~B() is called immediately after calling ‘operator bool()’ in class B.

My caution here is that we don’t want to make CFG construction time too expensive, as it will directly impact compile-time. I’m not saying we shouldn’t do this, only that we are mindful of possible performance implications.

In this case, I would just start with handling BinaryOperator more correctly.

Marcin is right; the temporary is destroyed conditionally at the end of the full expression. It just happens to be the case that that immediately follows the call to ‘B::operator bool()’ in your example. You can see that easily in the following modification to your example:

void baz(bool);
int test() {
foo(foo() || bar());
}

test(): ## @_Z4testv
Leh_func_begin0:

BB#0: ## %entry

pushq %rbp
Ltmp0:
movq %rsp, %rbp
Ltmp1:
pushq %r14
pushq %rbx
subq $16, %rsp
Ltmp2:
leaq -24(%rbp), %rbx
movq %rbx, %rdi
callq foo()
movq %rbx, %rdi
callq A::operator bool()
cmpb $1, %al
jne LBB0_2

BB#1: ## %lor.end.thread7

movl $1, %edi
callq baz(bool)
jmp LBB0_3
LBB0_2: ## %temp.cond-dtor.call
leaq -32(%rbp), %rbx
movq %rbx, %rdi
callq bar()
movq %rbx, %rdi
callq B::operator bool()
movzbl %al, %edi
callq baz(bool)
movl %eax, %r14d
movq %rbx, %rdi
callq B::~B()
movl %r14d, %eax
LBB0_3: ## %temp.cond-dtor.cont
movl %eax, %ebx
leaq -24(%rbp), %rdi
callq A::~A()
movl %ebx, %eax
addq $16, %rsp
popq %rbx
popq %r14
popq %rbp
ret

Er, actually, the optimizer has helpfully cloned the call to ‘baz’ so as to obscure my point, but I think you get it.

John.

Is the outer call to foo() suppose to be a call to baz()?

Yes, sorry.

John.

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.

Thanks John.

2010/10/23 Marcin Świderski <marcin.sfider@gmail.com>

W dniu 22 października 2010 11:22 użytkownik Zhongxing Xu <xuzhongxing@gmail.com> napisał:

When the binary operator is logical operator, why we need to replicate the control flow when adding the dtors in LHS and RHS? Could we just add the dtor right after where the LHS and RHS are evaluated?

That is, for code

A && B

we generate CFG like this:

A && B
~A()


B
~B()

A && B

Since in logical binary operator, we only need the boolean value. The temporary object can be destroyed right after it is evaluated.

This depends on how much we want to simulate real control flow of expression. C++ standard states that destructors of temporaries should be called at the end of full expression and in reverse order of their construction. Your example does not satisfy this. It only guaranties that destructor for temporary will be called.

I know it does not conform to the standard. I just proposed it to see if it is a viable alternative for CFG construction. But extending the CFG terminator could be a good idea. I’ll think about it.

2010/10/23 Ted Kremenek <kremenek@apple.com>

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?