Today we continue to read the WRL research report on the Swift Java Compiler. We saw that the Global Common SubExpression elimination and global code motion have significant optimization  benefits. We now look at Global Code Motion. The main purpose of Global Code Motion is to move loop independent values outside of loops and to ensure that all values are in blocks that dominate their users after global CSE. One such algorithm is the Click's code motion algorithm that proceeds via two passes over the SSA graph. The first pass finds the earliest possible placement of all values by requiring only that a value be placed in a position that dominates all its users. This requirement implies that the early placement will dominate the late value. After determining the latest placement for value in the second pass, the algorithm scans the sequence of blocks from the early to the late placement value. The values are then placed in the latest block. They are ordered such that the innermost loop is the lowest in the denominator tree. The result of this motion is that the value is moved out of loops as much as possible, and is otherwise put in the most control dependent block. Just before the code motion, duplicate inputs to phi nodes are eliminated. The SSA graph for a method has a phi node in the final block that merges all the possible return values. To get rid of the duplicate code sequences, the phi nodes are scanned for duplicate input. If one such is found, then the only other phi node in the block is for global stores. The duplicates are then eliminated by inserting an extra predecessor block that joins all the blocks corresponding to duplicate inputs. This results in the register copies for the duplicate inputs to be merged into a single code sequence and the duplicated value can now move down into the new block.
As an example, if we have a method that takes a single parameter,, does a few parameter checks initially and loops over the iterator of the parameter to check for a condition and returns true/false,
then per the discussion above, there is a phi node that merges all the return values. The generated code has sequences that load false as well as true and jump to the epilog. These may be redundant for their respective return value and they are eliminated by inserting the extra predecessor block.

Today we continue to read the WRL research report on the Swift Java Compiler. We saw that the Global Common SubExpression elimination and global code motion have significant optimization  benefits In addition there was one modification made to the partitioning algorithm to deal with values that cause exceptions. Exception causing values cannot be moved from their original block so code motion can not be applied to here to ensure that the values dominate their use after CSE is applied. If we take the case of two identical exceptions causing values, the first value can only replace the second if the first values block dominates the second values block. Also, the second values' block is redundant only if the first block did not throw an exception. Here Swift requires that the second values block is dominated by the non-exception successor of the first values block.
These conditions are satisfied if the CSE algorithm is modified as follows. First is the rule that the dominating value of the partition of exception causing values is kept as the first element of the partition. At the end of each run, the value in each partition is dominated by the the exception causing values otherwise the partition is split by making the exception causing value as the first element of a split into those dominated by this exception causing value and otherwise. The smaller of the two partitions is added to the worklist for another run. This is repeated until all the partitions have their value dominating the rest.
Global CSE is effective in eliminating runtime checks automatically and for compressing the control flow graph. Both the CSE and Code motion is executed once after all the inter procedural analysis and during machine independent processing. Swift does another round of it after the conversion of machine-dependent IR, in order to eliminate the common sub expressions that appear in the lower level form.

Today we continue to read the WRL research report on the Swift Java Compiler. We were discussing Global Common SubExpression elimination and global code motion. We were discussing how CSE is applied whenever there are two values that are equivalent and particularly even if neither of the two values are dominant. This is determined based on a work list. The values are all split into identical initial partitions based solely on their operation fields. For each of these partitions a set of values are build that takes one of the values in the partition. The partition is then split and the smaller of the two pis put into the worklist. This way each partition has all values equivalent.
Swift iterates through all the partitions and picks out the values from each partition. If a partition has more than one value, Swift picks out only the dominant value. It throws a way the other values.
CSE is very helpful in optimization. For example it removes the null checks against the parameters. In fact, CSE helps remove the same runtime check against the parameter from many places. In addition it removes the edges from the CFG.
#coding exercise
GetAlternateOddNumberRangeSumCubeRootSixthSquare (Double [] A)
{
if (A == null) return 0;
Return A.AlternateOddNumberRangeSumCubeRootSixthSquare();
}

Today we continue to read the WRL research report on the Swift Java Compiler. We were discussing method splitting and the criteria for the splitting point. We now look at Global Common SubExpression elimination and global code motion. Swift applies CSE to any two values that are equivalent no matter where they occur in the control flow graph. Even if neither of the two values are dominant, one value is replaced by the other. Global CSE is followed by a pass of global code motion, which places values in blocks so that all the values dominate all their users.
Two values are considered equivalent if they have identical operations and equivalent inputs. During the CSE, Swift computes equivalent values via a partitioning algorithm that splits all values into initial partitions based solely on their operation fields and puts the partitions on a work-list.  The work list is the set of values that are not necessarily equivalent. Each time it takes a partition P of the work list, it builds the set of values Si which takes one of the values in the partition as the ith input. If there is a partition Q which has some set of its values Q prime but not all of its values in Si, then it is split up into Q prime and the remaining and the smaller of the two partitions is added to the wordlist. This way Swift builds up each partition to have all values equivalent
Double GetAlternateOddNumberRangeSumCubeRootFourthSquare (Double [] A)

{

if (A == null) return 0;

Return A.AlternateOddNumberRangeSumCubeRootFourthSquare();

}

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.

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();

}

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();
}