[cfe-dev] Reference-counted statements

[Chris Lattner]

On Aug 7, 2009, at 9:26 AM, Douglas Gregor wrote:

> Daniel, Ted, John and I had a design discussion yesterday about the  
> ownership model for expressions and statements in Clang. The  
> catalyst for this discussion is the generic tree transformation that  
> went into Clang earlier this week, and on the problem of  
> transforming expression trees. In particular, given the expression
>
> 	x + y
>
> let's say that the tree transformer transforms x into x' but leaves  
> y alone. It will then attempt to construct a new addition operation
>
> 	x' +' y
>

It is unfortunate, but I agree that this is probably the best way to  
handle this.  Go for it!  Now we *really* don't want parent pointers  
in the AST :)

-Chris

> With today's strict ownership model for expressions, we have a  
> problem: both the + and the transformed +' believe that they own the  
> subexpression y, which will lead to double-frees, use-after-free  
> errors, etc.
>
> One immediate possibility would be to clone the subexpression y  
> (into a y' that is exactly similar to y); then the +' expression  
> will own x' and y' and the strict ownership model is retained. This  
> solution is relatively easy to implement, and is being used already  
> (in a limited way) during template instantiation. However, it has  
> performance costs in both time and memory. Moreover, it might not be  
> the right answer for other clients of Clang's ASTs, which may need  
> to refer to an expression within the the AST that might be  
> prematurely destroyed.
>
> We think that the addition of reference-counting to statements and  
> expressions is the right answer for Clang, and I've attached a patch  
> that adds such reference counting. Essentially, each statement (and,  
> therefore, expression) gets a an embedded reference count; the  
> Destroy method of a statement decrements the reference count, then  
> deallocates the expression and destroys its children if the  
> reference count hits zero.
>
> Most AST clients will still use simple Stmt or Expr pointers and  
> will not need to increase or decrease the reference counts. In those  
> few places where we are explicitly sharing statements or expressions  
> (e.g., as part of a tree transform), we will call the statement's  
> Retain operation to increase the reference count. In the attached  
> patch, I've introduced Retain calls in a few places to illustrate  
> the idea:
>
> 	1) When performing template instantiation for non-dependent leaf  
> nodes (e.g., literals), we retain the literal as written in the  
> source code bump its reference count by one. Previously, we were  
> cloning.
>
> 	2) When adding a SwitchCase (for a "case" or a "default" statement)  
> to a switch, we retain that SwitchCase. The switch statement itself  
> then Destroys its SwitchCases as part of its own destruction. This  
> fixes a bunch of crash-on-invalid problems we've had with switch  
> statements (see PR3444).
>
> Two performance-related notes: first, the size of statements and  
> expressions did not get any bigger. We reduced the size of the  
> statement class field in Stmt from 32 bits to 8 bits [*] and used  
> the remaining 24 bits for the reference count. Second, the reference  
> counts are modified very, very rarely, and only in response to  
> explicit sharing (as in the two cases I've shown), so we are not  
> concerned about additional overhead introduced by the counting.
>
> Comments, questions, etc. all welcome!
>
> 	- Doug
>
> [*] 256 statement/expression types should be enough for anyone! ;)
>
> <ref-counted- 
> stmts.patch>_______________________________________________
> cfe-dev mailing list
> cfe-dev at cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev