Assignment Specialization

 

Copying the contents of an inlined object into its container potentially alters aliasing relations, and we must ensure that such copying is safe. A common case is an object is initialized and then assigned to an inlined slot and from then on is accessed via the container (this happens in Figure 5). To handle such cases, we analyze to determine method arguments that can be passed by value; if the argument to the field's mutator method may be passed in by value, we can copy it into the inlined fields safely.

Our analysis is defined in terms of contours, which represent method calls, edges which map arguments between caller and callee, and uses, which are primitive operations, in particular calls and assignments. The basic idea behind this analysis is that objects may be passed by value if they have not previously been stored and are not subsequently used. We first define some local operations upon specific values and contours that form the groundwork for our analysis:

Caller(e)

is the calling use of inter-procedural edge e.

Callee(e)

is the called contour of inter-procedural edge e.

Call(u, v))

yields true if the use u of value v is a call.

Edge(u)

is the inter-procedural edge corresponding to use u, assuming u is a call.

Uses(v)

is the set of uses of a value v in its contour; these uses represent calls and primitive actions like setting a variable.

UsesBefore(e,v)

is the set of possible uses of v in Caller(e) before the edge e.

UsesAfter(e,v)

is the set of possible uses of v in Caller(e) after the edge e.

Map(v,e)

gives the argument value in the called contour corresponding to the value v passed across edge e.

LocalCreation(v)

returns true if v is the product of a new operation within its contour.

DontStore(u,v)

is true if the use u does not store v in an instance variable or a global variable.

Given these operations, we define a NoStore predicate that is true if a given value v is not stored in persistent state (all such state in our model is either an instance variable or a global variable).

$\mathrm{NoStoreCall}\left(u,v\right)\leftarrow \mathrm{Call}\left(u\right)\wedge \mathrm{NoStore}\left(\mathrm{Callee}\left(\mathrm{Edge}\left(u\right)\right),\mathrm{Map}\left(\mathrm{Edge}\left(u\right),v\right)\right)$

$\mathrm{NoStoreUse}\left(u,v\right)\leftarrow \neg \mathrm{Call}\left(u\right)\wedge \mathrm{DontStore}\left(u,v\right)$

$\mathrm{NoStore}\left(u,v\right)\leftarrow \mathrm{NoStoreCall}\left(u,v\right)\vee \mathrm{NoStoreUse}\left(u,v\right)$

$\mathrm{NoStore}\left(c,v\right)\leftarrow {\forall p_i}_{p_i\in \mathrm{Uses}\left(u\right)}\mathrm{NoStore}\left(p_i,v\right)$

Valuability for locally created objects (results of new operations within a given contour) can be checked by looking at all the uses of such objects within the contour. Once an object is passed in by value, we can copy it, and hence it is, effectively, created locally. The following helper predicate reflects this:

$\mathrm{CreatedLocally}\left(v\right)\leftarrow \mathrm{LocalCreation}\left(v\right)\vee \mathrm{CallByValue}\left(v\right)$

We are now ready to define valuability: an argument is callable by value if it can be passed by value from each call site. PassByValue and CallByValue formalize the criterion set out above:

$\mathrm{PassByValue}\left(p,v\right)\leftarrow {\forall p_i}_{p_i\in \mathrm{UsesBefore}\left(p,i\right)}\left(\mathrm{NoStore}\left(p_i,v\right)\wedge \neg \mathrm{UsesAfter}\left(p,v\right)\wedge \mathrm{CreatedLocally}\left(v\right)\right)$

$\mathrm{CallByValue}\left(v\right)\leftarrow {\forall p_i,v_i}_{\left\{\left(p_i,v_i\right)‖\mathrm{Map}\left(\mathrm{Edge}\left(p_i\right),v_i\right)=v\right\}}\mathrm{PassByValue}\left(p_i,v_i\right)$

A given field may be inlined only if the mutator method has its value argument passed in by value.