Use Specialization

 

To determine from which object fields any given value in the program may have come, we tag values that result from field accesses and propagate these tags through the inter-procedural data-flow graph. The basic idea is that values are tagged with the names of any fields from which they may have come, and these tags are transitive on field accesses to objects that themselves were the result of a field access. More formally, our data-flow analysis framework gives us the following properties of each value in the program:

Backs(v)

are the values from which data flows into v

Creators(v)

is the set of object contours of v.

We also define tags with which to mark the results of accesses to fields; these tags keep track of the fields from which a given value might have come. Fields themselves are represented by special values that denote the contents of the field. Note that MakeTag can built nested tags for accesses to nested objects.

NoField

is a special tag for values that did not flow from field accesses

MakeTag(f, tag)

returns the tag representing values that came from field f from an object whose origin is represented by tag.

Head(tag)

returns the last field in the given tag, i.e. Head(MakeTag(f, tag)) = f.

Tags(v)

is the set of tags associated with the value v.

We have three different trasnfer functions for our data-flow analysis, corresponding to three cases: object creations, instance variable accesses and other operations. Object creations are places where new objects are allocated (i.e. new statements) and their result values get the special NoField tag.

$\text{v = new Object}\to \mathrm{Tags}\left(v\right)\leftarrow \left\{\mathrm{NoField}\right\}$

Instance variable accesses append the accessed field onto the existing tags of the object being accessed; thus v gets a tag representing all the fields accessed to obtain this value.

$\text{v = o.f}\to \mathrm{Tags}\left(\right)\leftarrow {\cup }_{i\in \mathrm{Tags}\left(o\right)}\mathrm{MakeTag}(f,i)$

where f is the special value for the given field. Other values get their tags by propagation from all their reaching definitions in the inter-procedural graph; the use of the Creators of the tag prevents extraneous propagation that would otherwise occur across dynamic dispatches.

$\mathrm{Tags}\left(v\right)\leftarrow {\cup }_{i\in \mathrm{Backs}\left(v\right)}\left\{t‖t\in \mathrm{Tags}\left(i\right)\wedge \mathrm{Creators}\left(\mathrm{Head}\right(t\left)\right)\cap \mathrm{Creators}\left(v\right)\right\}$

Marks from different slots, or from no slot, can converge whenever data-flow paths do, and the analysis uses the contours provided by the framework to split such paths. As method contours are created on demand, the analysis must assert when two calls to the same method require different contours; this happens when two objects with different tags are supplied at different call sites to the same argument. That is, $c_1$ can be in the contour of$c_2$ only if

${\forall }_i\mathrm{Tags}\left(\mathrm{Arg},\left(c_1.i\right)\right)\subset \mathrm{Tags}\left(\mathrm{Arg}(c_2,i)\right)$

where Arg(c,i) represents the ith argument of call c. An example situation that requires splitting is the two calls to abs in do_rectangle; it is illustrated in Figure 8.

  
Figure 8: A Call Confluence

We also use creator sensitivity to disambiguate values with different tags that flow into an object contour's state. This arises in the two List objects created in do_rectangle, and is illustrated in Figure 9. The object contour must be split into new ones, one for each distinct tag amongst the definitions. Thus, the definitions of contour o must be partitioned into contours $o_n\mathrm{such\; that}$

${\forall f}_{f\in \mathrm{Fields}\left(o\right)}{\forall v_i{v}_j}_{v_i{v}_j\in \mathrm{Backs}\left(\mathrm{o.f}\right)}\left(\exists o_n{v}_i\in \mathrm{Backs}\left(o_n.f\right)\wedge v_j\in \mathrm{Backs}\left(o_n.f\right)\right)\to \mathrm{Tags}\left(v_i\right)=\mathrm{Tags}\left(v_j\right)$

Once the definitions have been partitioned thus, the analysis framework will split the object contour if possible.

  
Figure 9: Field Confluences

This analysis marks each value with an approximation of from which fields it may have come. We use this information to specialize the program to work on inline-allocated objects: a field can be inline allocated only if this analysis is able to distinguish exactly where the given field is used. That is, the tags of the given field must not be confused with tags from any other field.