Today we continue our discussion on WRL research report titled Swift Java compiler. We saw the use of blocks with SSA graphs. We now look at the Swift type system. The type of each value of a graph is computed as the SSA graph is built from the byte code. However, it is not always possible to recover the exact types in a Java program. Instead it is always possible to assign a consistent set of types to the values such that the effects of the method represented by SSA graph is the same as that of the original method. For some operation, the actual value types further specifies the operation. For each type T, Swift can keep track of these additional properties:
1) the value that is known to be an object of exactly class T
2) the value is an array with a particular constant size
3) the value is known to be non-null
By incorporating these types into the type-systems. we can therefore describe the properties of any value in the SSA graph by its type. Moreover, there can now be properties for different levels of recursive types, such as arrays.
We now review representing and ordering memory operations. Local variables are strongly scoped within the current method. Java has strong typing and no pointers, hence these variables cannot be altered by another method in the same thread or by another thread. The SSA form comes useful to represent these.Values in the SSA graph can be considered to be temporary variables stored in a large set of virtual registers. It is only near the end of the compilation process that the register allocator chooses which values are stored in actual registers and which are spilled to the stack.
On the other hand, reads or writes of global variables or locations allocated from the heap must be represented explicitly as memory operations, since there may be many hidden dependencies among these operations.
Regardless of local or global, the compiler may have to ensure that the original ordering among memory operations is maintained even thought they may not be connected on the SSA graph. As an example a store followed by a load may not have any scheduling dependence if the store does not produce a result that the load reads, however their ordering may still need to be preserved. In such cases, the ordering is enforced by Swift IR by having the store actually produce a result. This is called a global store and it represents the current contents of global memory. Since the store operations modify the contents, it executes a copy on write.Additionally, each load operation takes the global store as an extra input. These data dependences between memory operations allow many optimizations to immediately generalize to memory operations. The exception is that the SSA store does not include the required dependences called anti-dependences between load and store operations. The Swift compiler enforces these dependences via explicit checks during scheduling.
#codingexercise
Double GetAlternateEvenNumberRangeSumSquareRootSquare (Double [] A)
{
if (A == null) return 0;
Return A.AlternateEvenNumberRangeSumSquareRootSquare();
}
We continue to look at the improvements introduced by the Swift compiler. The explicit checks that the Swift compiler adds are for example that the load operation which takes a global store S as input is not moved down past a store operation that modifies. While the constraints are added, it is done to avoid the anti-dependences. The anti-dependences would require a new kind of edge in the SSA graph and avoiding them reduces the number of edges in the SSA graph.
If the current global store is different on two incoming edges of a block, then a merge block called the phi node is inserted into the graph to merge the two global stores into a new current store. Similarly the phi node of the global store when inserted at the top of a loop ensures that memory operations do not incorrectly move out of the loop. The addition of phi nodes to the SSA graph increases the number of nodes in the graph but they are not as drastic as the increase in the number of edges discussed earlier. Moreover, the benefit of adding a phi node is that memory operations are treated like all other values in the SSA graph.
1) the value that is known to be an object of exactly class T
2) the value is an array with a particular constant size
3) the value is known to be non-null
By incorporating these types into the type-systems. we can therefore describe the properties of any value in the SSA graph by its type. Moreover, there can now be properties for different levels of recursive types, such as arrays.
We now review representing and ordering memory operations. Local variables are strongly scoped within the current method. Java has strong typing and no pointers, hence these variables cannot be altered by another method in the same thread or by another thread. The SSA form comes useful to represent these.Values in the SSA graph can be considered to be temporary variables stored in a large set of virtual registers. It is only near the end of the compilation process that the register allocator chooses which values are stored in actual registers and which are spilled to the stack.
On the other hand, reads or writes of global variables or locations allocated from the heap must be represented explicitly as memory operations, since there may be many hidden dependencies among these operations.
Regardless of local or global, the compiler may have to ensure that the original ordering among memory operations is maintained even thought they may not be connected on the SSA graph. As an example a store followed by a load may not have any scheduling dependence if the store does not produce a result that the load reads, however their ordering may still need to be preserved. In such cases, the ordering is enforced by Swift IR by having the store actually produce a result. This is called a global store and it represents the current contents of global memory. Since the store operations modify the contents, it executes a copy on write.Additionally, each load operation takes the global store as an extra input. These data dependences between memory operations allow many optimizations to immediately generalize to memory operations. The exception is that the SSA store does not include the required dependences called anti-dependences between load and store operations. The Swift compiler enforces these dependences via explicit checks during scheduling.
#codingexercise
Double GetAlternateEvenNumberRangeSumSquareRootSquare (Double [] A)
{
if (A == null) return 0;
Return A.AlternateEvenNumberRangeSumSquareRootSquare();
}
We continue to look at the improvements introduced by the Swift compiler. The explicit checks that the Swift compiler adds are for example that the load operation which takes a global store S as input is not moved down past a store operation that modifies. While the constraints are added, it is done to avoid the anti-dependences. The anti-dependences would require a new kind of edge in the SSA graph and avoiding them reduces the number of edges in the SSA graph.
If the current global store is different on two incoming edges of a block, then a merge block called the phi node is inserted into the graph to merge the two global stores into a new current store. Similarly the phi node of the global store when inserted at the top of a loop ensures that memory operations do not incorrectly move out of the loop. The addition of phi nodes to the SSA graph increases the number of nodes in the graph but they are not as drastic as the increase in the number of edges discussed earlier. Moreover, the benefit of adding a phi node is that memory operations are treated like all other values in the SSA graph.
No comments:
Post a Comment