JIT Loop Invariant Hoisting

在上一篇文章中，我们已经对 Loop Invariant 概念有一个简单的了解，在文章的最后提到的 Loop Invariant 将在这篇文章做一个简单的介绍。

在我们开始之前

如果你了解 C# 程序的运行，应该知道 C# 代码先被编译器编译为 MSIL 中间代码，在实际运行的时候才通过 JIT 编译器将 MSIL 代码编译成机器代码并运行。因此，编译器有两个时段可以对代码进行优化：

• C# -> MSIL
• MSIL -> MACHINE CODE 但是，C#到MSIL的优化有限，大部分优化都是通过 JIT 来完成的。而这篇文章也是围绕微软最新的 RyuJIT 编译器来展开，其可能与旧的 JIT有所区别，但是应该差异不大。

Loop Invariant

首先看一下微软对 Loop Invariant Code Hoisting 的说明：

This phase traverses all the loop nests, in outer-to-inner order (thus hoisting expressions outside the largest loop in which they are invariant). It traverses all of the statements in the blocks in the loop that are always executed. If the statement is:

• A valid CSE candidate
• Has no side-effects
• Does not raise an exception OR occurs in the loop prior to any side-effects
• Has a valid value number, and it is a lclVar defined outside the loop, or its children (the value numbers from which it was computed) are invariant.

JIT 从外到内遍历所有的循环嵌套。它遍历循环嵌套结构中始终会被运行的BasicBlock（这是JIT里的类型，这里暂不展开，你可以暂时将其理解为编译器的基本类型）里的语句，并且这些语句符合以下条件：

• 是一个 CSE
• 没有副作用
• 不会触发异常或者发生在任何副作用之前
• 拥有一个可用的数字，这个数字定义在循环嵌套外或者其子元素是不可变的

---

上面提到的始终会被运行的循环嵌套（loop that are always executed), 如何理解? 嗯…，简单来讲，我们知道的循环结构，例如大部分编程语言都会有的 for loop 和 do while loop，这两种循环嵌套中，do while loop 就符合一定会被执行的循环嵌套，因为循环判断在一次循环后才会执行，而有些for loop 也可以被转换为 do while loop, JIT 会判断这个loop能否转换为do while loop后才进行后续的 loop hoisting 操作。

CSE - Common Subexpression Elimination

Utilizes value numbers to identify redundant computations, which are then evaluated to a new temp lvlVar, and then reused.

利用数字来识别（替代？）多余的计算，然后将它们计算为新的临时值，并重复利用。就如上篇文章中for循环中的 x+y。
观察RyuJIT 中用于判定CSE的函数片段：

/*****************************************************************************
 *
 *  The following determines whether the given expression is a worthy CSE
 *  candidate.
 */
bool Compiler::optIsCSEcandidate(GenTreePtr tree)
{
     /* No good if the expression contains side effects or if it was marked as DONT CSE */

    if  (tree->gtFlags & (GTF_ASG|GTF_DONT_CSE))
    {
        return  false;
    }

    /* The only reason a TYP_STRUCT tree might occur is as an argument to
       GT_ADDR. It will never be actually materialized. So ignore them.
       Also TYP_VOIDs */

    var_types   type = tree->TypeGet();
    genTreeOps  oper = tree->OperGet();

    if (type == TYP_STRUCT || type == TYP_VOID)
        return false;

    ...

#ifdef _TARGET_X86_
    if (type == TYP_FLOAT)
    {
        // TODO-X86-CQ: Revisit this
        // Don't CSE a TYP_FLOAT on x86 as we currently can only enregister doubles 
        return false;
    }
#else
    if (oper == GT_CNS_DBL)
    {
        // TODO-CQ: Revisit this
        // Don't try to CSE a GT_CNS_DBL as they can represent both float and doubles
        return false;
    }
#endif

    ...
  /* Check for some special cases */

    switch (oper)
    {
        ...

        case GT_LCL_VAR:
        return  false;   // Can't CSE a volatile LCL_VAR

        ...
    }

    ...
}

当然，这个函数还有许多细节，这里只挑选几个典型的片段。看代码可以知道：

• 可以明确指定不能使用 CSE
• 不能有赋值表达式
• 在x86下 float 不能作为 CSE, x64 下不支持 float 和 double
• 不支持 struct 和 void
• 如果是可变 (volatile) 的变量，也不能作为CSE，这在之前的一篇文章中有对 volatile 的说明

Loop-Hoisting 还有颇多细节这里并没有覆盖，有兴趣可以去看源码：https://github.com/dotnet/coreclr/blob/master/src/jit/optimizer.cpp