Today we continue to read the WRL research report on the Swift Java Compiler. We were discussing  runtime check elimination. We said that swift does some simple determinations based on  the users of a value and not based on any hypothesis or theorem. These checks or type tests can be made based on the  properties of the values and the control flow of the method. We saw this for both null check and type tests and the redundancies were removed. The bounds check was a bit more involved. Swift applies condition gathering recursively down to a fixed depth, and applies transitive properties between three variables. Some simple algebraic rules such as sum of two variables are also applied. This approach is effective because Swift's IR provides intermediate access to all the users of a value v, and therefore makes it easy to find program expressions that help prove properties about v. In addition, Swift does a round of global CSE before doing the check removal which lets Swift combine values equivalent to v and collect all their uses together.
We discuss array store checks as another run time check for Swift to optimize. In Java, this check ensures that the object being stored into the array is compatible with the base type of the array. Swift attempts to eliminate array store checks via several methods.  To eliminate any of these checks Swift has to resolve the base type of the array.It will also eliminate an array store check  if the base type of the array is known and can hold the known type of the stored value. If the value is a null or loaded from another element of the array, those checks are eliminated too. Swift also checks the class of the base type of array has no subclasses. If the type is final, then the store check cannot fail and is eliminated.
#coding exercise
GetAlternateOddNumberRangeSumCubeRootTenthPower (Double [] A)
{
if (A == null) return 0;
Return A.AlternateOddNumberRangeSumCubeRootTenthPower();
}

Today we continue to read the WRL research report on the Swift Java Compiler. We were discussing  branch removal and the two methods that Swift uses. The first method involves removing of branches for conditions that evaluate to 0 or 1 and involves removing a phi node that also removes an edge from the control flow graph The second method translates logical comparisons to bitwise comparisons. We now study runtime check elimination.  Some checks or type tests can be made on the properties of values and corroborated with the control flow of a method. For example, if a statement checks if a value is non-null, then null checks can be eliminated in one branch of this if - statement. Generalizing this, Swift scans the current SSA graph for run-time checks that have not been eliminated. In the example above, if the successor block along one of the edges of the null time check has null checks, then they can be eliminated However values that depend on the null time check should not float above the successor block. To do this, Swift places a pin value and changes all users of the null-check to use pin value instead. Pin values do not generate any machine code but they are pinned to their original block. These measures guarantee that the values that depend on the null check stay within the correct branch of the IF statement. The same discussion applies for cast checks.
For example, for a cast check of value v, Swift scans the users of v for instanceof checks on v that control an IF. Similar to the null checks, redundant IFs are eliminated by searching for a dominant IF with the same controlling condition.
For a bounds check, however, Swift does somewhat more work. If Swift were to try to eliminate a bounds check whose index is value v. then Swift first scans the users of v to derive conditions on v. If it finds a comparision on v that controls an IF, then it may know that the comparision or its negation is true. On the other hand, if v is an induction variable of a loop that is monotonically increasing / decreasing, then v is guaranteed to be greater/less than its starting value. In the example of a for loop, the termination condition specifies that the index is always less than the termination value which is usually an array length. Similarly for a zero based loop, the index has to be greater than or equal to zero given that the index is monotonically increasing. Together these two conditions guarantee that the bounds check associated with accessing the array element at index i will always succeed and so Swift will swiftly remove it.
The key idea behind runtime checks is that Swift does not try to solve a system of inequalities involving i in order to prove properties of i. Instead, it looks at all the users of the value representing i, and determines if any direct comparisions of i can be shown to be true.
#coding exercise
GetAlternateOddNumberRangeSumCubeRootEigthPower (Double [] A)
{
if (A == null) return 0;
Return A.AlternateOddNumberRangeSumCubeRootEigthPower();
}

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 reviewed Global Code Motion. We now look at branch removal. Swift has a phase that uses two methods to attempt to remove branches. The first method removes branches that are used to compute a value that is either 0 or 1. Instead it wants to assign them directly. However in JVM there are no byte codes that produce a boolean value directly from a comparison. A branch is therefore involved however Swift tries to optimize it. It simply searches through all the phi nodes in the method whose two inputs are constants of 0 and 1. If it translates to an If-then-else, then Swift can replace the use of the phi nodes with the controlling boolean of the If node. When the phi node is optimized away, the if-then-else control flow structure is also removed. Swift also tries to remove branches by converting logical and/or expression to bitwise and/or expression.  For example, the code for a conditional that has two conditions with a logical 'and', requires two branches since the second condition is not evaluated if the first one fails. However, if the conditions are fairly simple and have no side effects, then they can be combined with a bitwise AND and then do a conditional branch. This reduction in the number of branches is important because extra branches can reduce the rate of instruction fetching and may even result in a  speculation down the wrong path.
This optimization is fairly easy to implement in the Swift IR. Swift simply looks through all the blocks in CFG for a block that is controlled by an IF node and one of whose successors is also an IF node. If such a block is found, Swift checks the other criteria namely no side effects. There must be no memory write operation, method call or other exception causing operations. If these are satisfied then the conditions can be combined and the branches can be eliminated. 

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

}