JIT: Loop hoisting re-ordering exceptions

[JosephTremoulet]

Loop-hoisting optimization mentions in a comment that "We assume that expressions will be hoisted so that they are evaluated in the same order as they would have been in the loop," but that assumption doesn't hold with the current implementation. Consider the following code:

using System;
using System.Runtime.CompilerServices;

namespace N
{
    public class C
    {
        int f = 2;

        [MethodImpl(MethodImplOptions.NoInlining)]
        static bool cross(int k, int y, C c)
        {
            bool b = false;

            for (int i = 0; i < k; ++i)
            {
                // Here "c.f" is invariant, but is evaluated after "i / y"
                // which may throw a different kind of exception, so can't
                // be hoisted without potentially changing the exception kind
                // thrown.
                b = (i / y < i + c.f);
            }

            return b;
        }

        [MethodImpl(MethodImplOptions.NoInlining)]
        static bool swap(int k, int x, int y, C c)
        {
            bool b = false;

            for (int i = 0; i < k; ++i)
            {
                // Sub-expressions "x / y" and "c.f" are both invariant
                // w.r.t. this loop, and can be hoisted.  Since each can
                // raise an exception, and the exceptions have different
                // types, their relative order must be preserved -- the
                // hoisted copy of "x / y" must be evaluated before the
                // hoisted copy of "c.f"
                b = (x / y < i + c.f);
            }

            return b;
        }

        public static int Main(string[] args)
        {
            int errors = 0;

            try
            {
                cross(10, 0, null);
                // DivByZero should be raised from 'swap'; normal return
                // is an error.
                ++errors;
            }
            catch (DivideByZeroException)
            {
                // This is the correct result -- i / y should be evaluated and
                // raise this exception (before c.f raises nulllref).
            }
            catch
            {
                // Any exception other than DivideByZero is a failure
                ++errors;
            }

            try
            {
                swap(10, 11, 0, null);
                // DivByZero should be raised from 'swap'; normal return
                // is an error.
                ++errors;
            }
            catch (DivideByZeroException)
            {
                // This is the correct result -- x / y should be evaluated and
                // raise this exception (before c.f raises nulllref).
            }
            catch
            {
                // Any exception other than DivideByZero is a failure
                ++errors;
            }

            return 100 + errors;
        }
    }
}

In the case of method cross, there's an invariant expression in the loop which may throw, but it is preceded by a variant expression which may throw a different kind of exception; the optimizer currently performs the hoist and changes the observable exception type.

In the case of method swap, two invariant expressions are hoisted, but the order of their hoisted copies in the preheader is reversed from their order in the loop, which again is observable since the two invariant expressions can raise different types of exception.

The sequence of events leading to the swapped order in swap is:

1. x / y < i + c.f is visited by optHoistLoopExprsForTree
   1. x / y is recursively visited. It is marked as invariant and hoistable, but not hoisted yet because we're waiting to see if the whole parent expression is invariant and hoistable.
   2. i + c.f is recursivley visited
      1. i is resursively visited, and found to be variant
      2. c.f is recursively visited, and found to be invariant and hoistable
   3. i + c.f is post-visited; it is not invariant or hoistable, but it has an invariant hoistable child c.f, which is now hoisted
2. x / y < i + c.f is post-visited; it is not invariant or hoistable, but it has an invariant hoistable child x / y, which is now hoisted

This same sequence of events swapping the hoisted expressions in swap was responsible for swapping a static field access and a static initializer call in dotnet/corefx#11524, due to which dotnet/coreclr#6889 was reverted in dotnet/coreclr#7118. It's possible this is the same issue prompting the workaround that disable hoisting of ClsVars.

category:correctness
theme:loop-opt
skill-level:expert
cost:medium

[pgavlin]

@JosephTremoulet: do you think this will make 1.2?

[mikedn]

In the case of method cross, there's an invariant expression in the loop which may throw, but it is preceded by a variant expression which may throw a different kind of exception; the optimizer currently performs the hoist and changes the observable exception type.

Here it's probably worth pointing out that hoisting can be done correctly in the following case:

b = (c.g + i / y < i + c.f);

c.g is invariant and if hoisted it will also allowing hoisting of c.f because both either throw NullRef or do not throw. The recently added extended support for exception tracking in value numbering should make this easier to implement.

In the case of method swap, two invariant expressions are hoisted, but the order of their hoisted copies in the preheader is reversed from their order in the loop, which again is observable since the two invariant expressions can raise different types of exception.

This is relatively easy to fix. When a non-hoistable node is encountered all previously encountered hoistable trees must be hoisted, not only its children.