We finished today the guard elimination pass, which is responsible for redundant null check and array bounds check elimination. Since all conditional branches appear as guards in our representation, the guard elimination pass is able to merge and simplify loop conditions and array bounds checks into the minimum amount of necessary checks. Consider the following code example:


int i = 0;
while (i < 5000) {
  a[i++] = 0;
  a[i++] = 0;
}


The resulting intermediate representation (IR) code has 6 implicit guards (two null checks, two lower bounds checks, and two upper bounds checks), and a 7th explicit guard representing the loop condition. The guard elimination pass reduces these to a single check.

The guard elimination pass detects and simplifies three different scenarios involving redundant guards. First, any null check guard on a local allocation is deleted. Second, redundant equality (or not equality) checks involving the same operands are deleted. This frequently occurs due to dynamic type checking which is enforced with guard in our intermediate representation. The last condition we optimize are mergable guards on monotonic induction variables. Here we optimize two distinct cases.

First we check whether the array condition checks for the reverse of the monotonicity of the induction variable, i.e. the guard checks whether the value is less than zero, but we know that the variable is non-decreasing. These guards are flagged as invariant and are hoisted out of the loop by the invariant code motion pass.

In a second step we check whether we have seen any other guards involving the same induction variable upstream in the tree (from the point to the root of the tree). If so, we form the minimum or maximum of the value the variable is compared with (depending on the branch type), and then use a single guard. The calculation of the minimum/maximum will be hoisted out of the loop (in general we only optimize guards that check against an invariant value, so any minimum/maximum of invariant values is always guaranteed to be hoisted).

A slight complication arises if we apply this latter optimization to guards that have previously been flagged as invariant by the previous step. Since the minimum/maximum calculation is emitted in place of the subsequent (redundant) guard instructions, we cannot simply change the first guard to compare against the newly calculated minimum/maximum value, because it is defined further downstream in the instruction sequenece. We can also not simply kill the first guard and do the check in the last guard we see, because we might not catch exceptions at the first guard site.

Fortunately, this problem is limited to guards that are invariant (and thus are hoisted out of the loop). For guards that are not, the condition part is actually guaranteed to appear first once invariant code motion has been performed. Thus, for any guard thats not invariant (i.e. does not check that a non-decreasing variable is less than zero), we can simply change the first guard we saw to point to the newly emitted minimum/maximum instruction. Invariant code motion will ensure that the minimum/maximum instruction will be hoisted above the first guard. The subsequent guards are simply deleted in this case.

For invariant guards, on the other hand, since they go into the prolog themselves, we cannot easily eliminate any of them, and while we do change their operands, we actually leave them intact in the prolog and multiple checks are performed. However, this is not particularily performance critical since the prolog executes only once per loop.