[cfe-dev] CFG blocks and variable scope

[Ted Kremenek]

On Mar 30, 2009, at 3:55 PM, Martin Doucha wrote:

> Ted Kremenek wrote:
>> I don't follow this argument.  First, I don't understand the memory
>> concerns.  Having statements point to group of N variables still
>> requires N+1 pointers versus having N pointers in a basic block to
>> virtual statements.  A basic block that contains virtual statements
>> (which would be a format for this information that existing clients
>> would already understand) would require space for the basic block
>> (which is insignificant) and N pointers.
>
> The problem is there may be multiple blocks with virtual statements.  
> Now
> if you have M blocks and N variables to destroy (the same variables in
> each block), the group approach requires O(M+N) memory while the  
> direct
> approach requires O(M*N) memory. Though these numbers are unlikely  
> to be
> significantly different for hand-written code, don't underestimate the
> stupidity of automatic code generators.

This is an interesting point.  I wonder how much, however, this is a  
real concern in practice.  Consider the LLVM IR for a complex C++  
program.  The LLVM IR is SSA-based CFG that needs to model C++  
destructor calls at a much lower level.  Any "continue", "break", or  
"goto" that crosses scope boundaries requires logic in the IR for the  
necessary destructor calls.  It seems like the same problems you  
describe would be present there.

This aside, we certainly can handle the case you described with the  
right abstractions and still provide the same CFG interface that  
clients expect.  Since we are free to implement basic blocks in any  
matter that we wish (and have different kinds of basic block  
encodings), we can use virtual basic blocks to encode what variables  
are destroyed but employ data sharing between these virtual basic  
blocks to keep the memory costs down.  Through a proper iterator  
interface, clients would iterate over the "virtual" statements in the  
virtual basic blocks, even if we don't explicitly create those  
statements.  This approach can be viewed of the combination of the two  
approaches discussed, except that this has a simpler interface for  
clients.