Today we continue to read the WRL research report about the Swift Java Compiler. We were looking into Method splitting. We saw that class methods that proliferate even though they have small amount of code are good candidates for inlining. However they may include checks that can cause exceptions. In these exception cases, the method may not be inlined. Moreover, this case may use extra register saves and restores. Therefore, the method is split into two versions one for the happy code path and the other for the exception code path. Swift determines whether a method is splittable rather conservatively. Unless the method has small amount of code such as looking up or setting an encapsulated field or array member, the methods is not considered for splitting. A method is splittable only if it has a single path to the return statement that calls no other methods as well as multiple other paths that eventually throw exception. The path to the normal exit is then considered the common case. The information to split the method is computed and cached by the method analysis module. When Swift compiles a splittable method, it will generate auxiliary methods along the uncommon code paths.and replace them with the auxiliary methods. The IR of the original method is thus modified. These calls to the auxiliary method are then inlined.
Tuesday, March 10, 2015
Monday, March 9, 2015
Today we will continue our discussion on the WRL research report about the Swift Java Compiler. We were looking into method resolution and inlining. When Swift is invoked in simple Class Hierarchy Analysis mode, it will not use CHA to resolve methods for use by any interprocedural analysis, such as alias analysis or escape analysis. It will only use it for virtual call resolution in the methods that are being compiled and convert them to direct calls. In addition, if a call was resolved using CHA, then Swift won't do method inlining for that call. However, it will allow method inlining if the receiver of the call is an input argument of the containing method. With these restrictions, the JVM will find it easy to update code optimized using CHA when a class is dynamically loaded. For each compiled method of the classes which if they are subclassed by a dynamically loaded class will require the method to be modified or invalidated, Swift will provide a list to the JVM. Along with each class, Swift indicates which new method would require a modification of the containing method and for each of these,whether a particular direct call can be modified or if the containing method's code needs to be invalidated or recompiled.
We next look at method splitting. This technique is used when the bulk of the usage of the method follows a small happy code path and a small rare percentage runs some checks and fails it causing either an error exit or an exception. In such cases, the method is split because the usual code path can now be inlined and enable further optimizations. This is usually the case for methods of a class that usually return a field or an element of the array
#codingexercise
Double GetAlternateOddNumberRangeSumSquareRootFourthSquare (Double [] A)
{
if (A == null) return 0;
Return A.AlternateOddNumberRangeSumSquareRootFourthSquare();
}
We next look at method splitting. This technique is used when the bulk of the usage of the method follows a small happy code path and a small rare percentage runs some checks and fails it causing either an error exit or an exception. In such cases, the method is split because the usual code path can now be inlined and enable further optimizations. This is usually the case for methods of a class that usually return a field or an element of the array
#codingexercise
Double GetAlternateOddNumberRangeSumSquareRootFourthSquare (Double [] A)
{
if (A == null) return 0;
Return A.AlternateOddNumberRangeSumSquareRootFourthSquare();
}
Sunday, March 8, 2015
Today we will continue to discuss Swift Java Compiler. In the previous post we started looking at method resolution and inlining. We discussed how we could detect that most super class constructors maybe empty. If Swift is used in an environment where dynamic loading can occur, then the use of CHA (Class hierarchy analysis) is limited to simplify correctness issues. In general, if a method is compiled with information that a particular class has no subclasses or a particular method has only a single implementation, then the method's code must be modified if dynamic loading means that this is no longer applicable. However, this method may be in executing and even running a tight loop and we may not be able to wait. If the method has a virtual method call that is resolved to a direct call using CHA and it is not inlined, then we can just turn off CHA even if the method is running. Here the JVM generates a stub and the jump to the virtual call is done atomically. The more difficult problem is to reverse the effects of CHA when a call is resolved and inlined. The resolved call only becomes incorrect if the receiver can contain an object from the dynamically loaded class. If the receiver is an argument of the containing method, then it existed prior and cannot change. The receiver cannot reference an object of the dynamically loaded class, and hence for the duration of the current invocation, the containing method will be correct. The containing method can be invalidated simply by creating a new version with the virtual call reinstated. In this case, all the future calls must use the new version. The JVM can further choose to not generate a new compiled code, and instead ensure that future calls of the containing method revert to interpreting the byte code directly and using less optimized JIT code.
#codingexercise
Double GetAlternateOddNumberRangeSumSquareRootSixthSquare (Double [] A)
{
if (A == null) return 0;
Return A.AlternateOddNumberRangeSumSquareRootSixthSquare();
}
#codingexercise
Double GetAlternateOddNumberRangeSumSquareRootSixthSquare (Double [] A)
{
if (A == null) return 0;
Return A.AlternateOddNumberRangeSumSquareRootSixthSquare();
}
Saturday, March 7, 2015
We discuss the Swift Java compiler further. We were looking into Swift's LocType and StoreOp in the dataflow analysis. Since Swift does a full analysis, it correctly determines when a particular locType cannot be modified in a loop.The state information for each node is updated which is then used to update the dependencies. Each load operation for example may have a change of store as its input following the store resolution process. This makes the relaxed dependence information available to all later passes. In the example of load operations with changed input, they will now be combined into a single load opeartion. Other similar effects from subsequent passes could involve a load operation to be scheduled earlier or to be moved out of a loop.
Swift's analysis is interprocedural since it makes use of summaries of the effects of methods.As with other method properties.the write effects of a method are computed on demand by the method analysis module. This yields a list of fields that do not affect data flow and array element types (LocTypes) that the method or the calls made might modify.Unlike many other properties the immediate effects of a byte code can be determined without building a CFG or SSA graph.
Since the locations are categorized into distinct field and array element types, Swift has used a type based alias analysis scheme. The field name of the location is also considered part of its type. That said, the store resolution can easily be used with a more sophisticated alias analysis that can manage different kinds of LocTypes and improve accuracy.
Let us now look at method resolution and inlining. Swift resolves virtual method calls using information from various kinds of analyses. For example, if Swift is using Class hierarchy analysis, the method implementation may indicate there is only one possible implementation that could be referenced by a virtual call. If there is no CHA analysis, the final keyword can indicate if the implementation is only one. Or from the type analysis, it may indicate that the receiver may have a particular exact type and therefore can only invoke one specific method. Similarly interface calls can be resolved. Method inlining may be applied recursively as part of other interprocedural optimizations. This helps with such things as the removal of superclass constructors which may be mostly empty.
#codingexercise
Double GetAlternateOddNumberRangeSumSquareRootEigthSquare (Double [] A)
{
if (A == null) return 0;
Return A.AlternateOddNumberRangeSumSquareRootEigthSquare();
}
Swift's analysis is interprocedural since it makes use of summaries of the effects of methods.As with other method properties.the write effects of a method are computed on demand by the method analysis module. This yields a list of fields that do not affect data flow and array element types (LocTypes) that the method or the calls made might modify.Unlike many other properties the immediate effects of a byte code can be determined without building a CFG or SSA graph.
Since the locations are categorized into distinct field and array element types, Swift has used a type based alias analysis scheme. The field name of the location is also considered part of its type. That said, the store resolution can easily be used with a more sophisticated alias analysis that can manage different kinds of LocTypes and improve accuracy.
Let us now look at method resolution and inlining. Swift resolves virtual method calls using information from various kinds of analyses. For example, if Swift is using Class hierarchy analysis, the method implementation may indicate there is only one possible implementation that could be referenced by a virtual call. If there is no CHA analysis, the final keyword can indicate if the implementation is only one. Or from the type analysis, it may indicate that the receiver may have a particular exact type and therefore can only invoke one specific method. Similarly interface calls can be resolved. Method inlining may be applied recursively as part of other interprocedural optimizations. This helps with such things as the removal of superclass constructors which may be mostly empty.
#codingexercise
Double GetAlternateOddNumberRangeSumSquareRootEigthSquare (Double [] A)
{
if (A == null) return 0;
Return A.AlternateOddNumberRangeSumSquareRootEigthSquare();
}
Friday, March 6, 2015
Today we continue reading the WRL research report on Swift Java Compiler. We were discussing alias analysis We will see a few more ways to relax memory dependencies. The basic Swift IR is retained. A process called store resolution is used to relax memory dependences by changing the global store inputs of some memory operations. In the case of the loop example mentioned earlier, rather than changing the stores of A and B to be the global store inputs, we keep them the original store inputs and move them out of the loop. Store resolution does a forward dataflow computation to build up information about memory operations, as follows.
We look at the sub-graph of the SSA graph where global stores are produced. We label such operations that produce them as StoreOps. We want to compute information at these nodes about sets of locations that are easy to classify. With the help of the language, we know particular fields are of certain types and array elements are of particular types. These different sets of location can be labeled LocTypes. At each node of the subgraph we want to find for each LocType, the most recent StoreOp that might have modified the locations of that type
From the dataflow, the state at each node maps each LocType to the most recent preceding StoreOp which might have modified locations of that LocType. The state entry has a default StoreOp that applies to most LocTypes. and miscellaneous ordered pairs of (LocType, StoreOp) for any locTypes that don't map to the default. Perhaps we can classify them to have more salient entries in the state.
#codingexercise
Double GetAlternateOddNumberRangeSumSquareRootTenthSquare (Double [] A)
{
if (A == null) return 0;
Return A.AlternateOddNumberRangeSumSquareRootTenthSquare();
}
We look at the sub-graph of the SSA graph where global stores are produced. We label such operations that produce them as StoreOps. We want to compute information at these nodes about sets of locations that are easy to classify. With the help of the language, we know particular fields are of certain types and array elements are of particular types. These different sets of location can be labeled LocTypes. At each node of the subgraph we want to find for each LocType, the most recent StoreOp that might have modified the locations of that type
From the dataflow, the state at each node maps each LocType to the most recent preceding StoreOp which might have modified locations of that LocType. The state entry has a default StoreOp that applies to most LocTypes. and miscellaneous ordered pairs of (LocType, StoreOp) for any locTypes that don't map to the default. Perhaps we can classify them to have more salient entries in the state.
#codingexercise
Double GetAlternateOddNumberRangeSumSquareRootTenthSquare (Double [] A)
{
if (A == null) return 0;
Return A.AlternateOddNumberRangeSumSquareRootTenthSquare();
}
Thursday, March 5, 2015
In the previous post, we were discussing alias analysis in the Swift Java compiler from the WRL research report. We recall that it attempts to relax data dependencies in the SSA graph. If there are two memory locations, then alias analysis checks to see if they are the same. If we take the example of sloop, that contains two array store operations, then there will be a phi node at the top of the loop that merges the initial global store entering the loop with that at the end of each iteration. If the values don't move outside the loop, they should be reloaded in each iteration.
Memory operations that access the same field or same type of array element of a particular type can only be affected by memory operations that access the same field or same type of array element. global stores cannot modify the type. To represent dependences among memory operations with more precision is to have many different types of global stores. There are several problems with this approach. First, this would create more edges and nodes in the SSA graph Extra phi nodes will be required for many different kinds of global stores. Method body would now require arg nodes for many different kinds of global stores. If the effects of a method call are unknown, then it would take every possible kind of global store as input, and produce new versions as output. We already talked about synchronization nodes having different versions when there are unnecessary synchronizations specified. We would create even more versions with different types of global stores. Method inlining also becomes complicated in that it might also require that additional arg nodes be created from the caller.
Memory operations that access the same field or same type of array element of a particular type can only be affected by memory operations that access the same field or same type of array element. global stores cannot modify the type. To represent dependences among memory operations with more precision is to have many different types of global stores. There are several problems with this approach. First, this would create more edges and nodes in the SSA graph Extra phi nodes will be required for many different kinds of global stores. Method body would now require arg nodes for many different kinds of global stores. If the effects of a method call are unknown, then it would take every possible kind of global store as input, and produce new versions as output. We already talked about synchronization nodes having different versions when there are unnecessary synchronizations specified. We would create even more versions with different types of global stores. Method inlining also becomes complicated in that it might also require that additional arg nodes be created from the caller.
Wednesday, March 4, 2015
In the previous post, we discussed escape analysis as implemented in the Java Swift compiler and discussed in the corresponding WRL research report. Specifically we looked at references that can escape from the current method or thread. This helps us do optimizations such as allocating the objects on the stack or on the heap and the removal of unnecessary synchronization. We found that the Swift compiler uses the summary of the method together with the inter procedural analysis. It finds the usages of the references to determine if the references are being held globally or used in an array that can let it escape. With this analysis, Swift looks for values which are either objects that are directly allocated in the method or are newly allocated unaliased objects returned by method calls. It makes a conservative selection and comes up with a pruned list. For methods that don't require synchronization, it adds the corresponding operations to the SSA graph.
We review Alias analysis next. Here Swift attempts to relax data dependencies in the SSA graph. By alias, we mean that two memory locations are not the same when they are accessed. For example, if a loop contains two array store operations then there is a phi node in the Swift IR at the top of the loop and this merges the initial global store entering the loop with that at the end of each iteration. The values of the variables loaded inside of the loop cannot move outside the loop. Therefore they are reloaded in each iteration.
We review Alias analysis next. Here Swift attempts to relax data dependencies in the SSA graph. By alias, we mean that two memory locations are not the same when they are accessed. For example, if a loop contains two array store operations then there is a phi node in the Swift IR at the top of the loop and this merges the initial global store entering the loop with that at the end of each iteration. The values of the variables loaded inside of the loop cannot move outside the loop. Therefore they are reloaded in each iteration.
Subscribe to:
Comments (Atom)