The dominator analysis is a prerequisite for the concurrent points-to analysis; the reason will be enlightened in the next section. The dominator analysis task is to reveal what variable assignments have been performed previous to the current location, but within the same locked region as the current location.
We initially define the fact the dominator analysis computes, called the dominator set orDS(`), as:
DS(`) =P(S× P(L))
whereS =NandL=N. Thereby an element (s, ls) represents that the assignment to the variable with value s is dominating under the set of locks in ls. We define the function on the dominator setDS(`)(s) =ls, which yieldslsin the pair (s, ls)∈ DS(`).
The dominator analysis computes the dominator set in a forward manner on the CFG, such that we may express the input DS◦(`) and outputDS•(`), which corresponds to the facts flowing forward in the control flow, as:
DS◦(`) =
ι if`=`◦ F
DA{DS•(`0)|(`0, `)∈CF G} otherwise DS•(`) = f`(DS◦(`))
The dominator analysis resembles a must analysis, as it will combine facts, such that the combining of sets results in that variable values not present on all paths will not be part of the resulting dominator set. However, the combining of assignments to the same variable under different lockset, that do not intersect, should also not be part of the result, which cannot be expressed by∩solely and therefore the combine operator for the dominator analysis, F
DA :P(DS)→DS, must be defined specifically. We definetDA:DS×DS→DS:
The transfer functions for the dominator analysis vary and either are a function of the instruction and the top of the stack at the current location,f`(ins(`), top(S`)) or only a function of the current location, implicitly already denoted byf`.
In the following we demonstrate the dominator analysis behavior from examples and later formalize the transfer functions that define the analysis behavior.
3.5 Dominator Analysis 69
3.5.1 Variable Assignments
First of all, the dominator analysis must compute the dominator sets based on the locations where variables are assigned.
1 p u b l i c v o i d D o m i n a t o r A s s i g n m e n t E x a m p l e {
2 p u b l i c v o i d d o A s s i g n () {
3 O b j e c t o3 = new O b j e c t () ; /* o3 = 2 , n e w O b j e c t () =3 */
4 s y n c h r o n i z e d(t h i s) { /* t h i s =1 */
5 O b j e c t o2 = new O b j e c t () ; /* o2 = 4 , n e w O b j e c t () =5 */
6 /* e t c */
7 }
8 }
9 }
Listing 3.16: An example used to demonstrate the dominator analysis.
Listing 3.16, shows an example Java class for which the dominator analysis will be demonstrated. We describe how the dominator set is computed for line 6, by looking at how the dominator analysis must react upon variable assignments during control flow.
In the above example, the CFG of the method doAssignis the target of the analy-sis. The initial analysis information to doAssignis empty, because no assignments precede from constructors or initializations. The input fact at line 3 is then empty, DS◦(3) ={}. The assignment in line 3 could therefore potentially add the value of o3 to the dominator set. However, LS(3) = {} and nothing is added to the dom-inator set. The reason is that the domdom-inator set shall only express the values of variables that have been assigned within a region protected by at least one lock.
The analysis then proceeds with the empty dominator set, DS•(3) = {}, which is unaffected by line 4, thus DS•(4) = {}. At line 5 however, LS(5) = {(1,1)} and therefore the assignment too2must now be added to the dominator set, such that it becomes DS•(5) ={(4,{1})}, which represents that after line 5, the variableo1has been assigned to under the lock this. The dominator set present at line 6 is then DS◦(6) ={(4,{1})}, which ends this simple example.
3.5.1.1 Transfer Function
We will formalize the transfer function of variable assignments according to the be-havior presented in the previous section. This can be reviewed in table3.9 below.
3.5.2 Method Invocation
The dominator analysis must also be aware of method invocations. For invocations to non-final, non-private methods within the class of interest, the over-approximation
ins(`) DS•(`) =f`(DS◦(`))
Table 3.9: Transfer functions for variable assignments in the dominator analysis.
of the behavior regarding the dominator analysis, is that nothing will be added the dominator set on such a dispatch, because the behavior of these methods cannot be known at compile-time. This also applies for dispatches to methods outside the class of interest. However, for dispatches to private or final methods within the class of interest, the behavior is deterministic and the dominator analysis may analyze these dispatches as they occur in the traversal, with a context sensitive approach, where the context information is the points-to set, the lock set and the dominator set at the location of the dispatch. This behavior will be demonstrated in the example in listing3.17.
Listing 3.17: An example with a dispatch to a final method, that must be handled by the dominator analysis.
The dominator set after line 5 of the Java source must reflect that o1 has been assigned to under the lock of this. The analysis handles this, by identifying that a dispatch to the final method within the class of interest, doAssignment, is invoked in line (5). Then it initiates an analysis of doAssignment with ι = DS◦(5) and performs the analysis of doAssignment. As the assignment to o1in line 10 occurs, the dominator set result is then updated toDS={(2,{1})}, representing thato1is
3.5 Dominator Analysis 71
assigned to under the lock ofthis. The dominator sets at the end points of the CFG ofdoAssignmentare then combined according totDA; in this case there is only one end point of the CFG, so the computed result is the output dominator set of line 5, namelyDS•(5) ={(2,{1})}.
3.5.2.1 Transfer Function
We now formalize the dominator analysis transfer function that handles dispatches.
For this purpose, we define the function RDA(m, DS◦(`)), which is a function that initiates a dominator analysis and analyzes the dispatch on location`with the initial analysis information, ι = DS◦(`), combines all return facts according to tDA and returns the resulting dominator set. The formalization is shown in Table3.10.
ins(`) DS•(`) =f`(DS◦(`))
All [Given:DS◦(`) =P(S×L)]
DS•(`) ={(s, l)| ∀s∈S,∀l∈DS◦(`)(s) :l∈LS(`)}
Table 3.10: Transfer function for dispatches in the dominator analysis.
3.5.3 Removing Dominating Assignments
What remains to describe for the dominator analysis, is that values representing variables that have been assigned to within a specific locked scope, must be removed again from the dominator set, if the locked scope a value is assigned in ends.
1 p u b l i c c l a s s D o m i n a t o r R e m o v e E n t r y E x a m p l e {
2 p u b l i c v o i d d o S y n c h r o n i z e d A s s i g n m e n t s () {
3 O b j e c t o1 ; /* o1 =2 */
4 s y n c h r o n i z e d(t h i s) { /* t h i s =1 */
5 o1 = new O b j e c t () ; /* n e w O b j e c t () =3 */
6 }
7 /* e t c . */
8 }
9 }
Listing 3.18: In the example the point of interest is when the synchronized region ends, which must influences the dominator set.
Consider line 7 in listing 3.18. Here the synchronization on this has ended, and therefore interleavings may exist between the assignment to o1 and line 7, and o1 may not be present with an assignment under the lock this in the dominator set in line 7. The dominator analysis handles this as it visits locations. It looks up the lockset at the location it visits,LS(`), and if any dominating assignments are present
in the dominator set with any locks not present in LS(`), then these assignments must be removed from the set. In the example, the lock set in line 7 does not contain any locks. However, the input dominator set contains an assignment too1under the this lock. Thenl\LS(7) ={1} \ {} 6=∅, as DS◦(7)(2) =l={1}, and (2,1) must be removed from the dominator set, yielding an empty dominator set in line 7.
3.5.3.1 Transfer Functions
We can formalize the behavior just described in a transfer function that applies to all locations, without being a function of the instruction, as it only relies on the incoming dominator set and the lockset on the location. This can be seen in table3.11.
ins(`) DS•(`) =f`(DS◦(`))
All [Given:DS◦(`) =P(S×L)]
DS•(`) =
{(s, l)| ∀s∈S,∀l∈DS◦(`)(s) :l∈LS(`)}
Table 3.11: Transfer function for removing dominating assignments in the dominator analysis.
3.5.4 Summary
In the previous sections, it is documented how the dominator analysis behaves and transfer functions defining this behavior are stated. We now sum these up in the Table3.12.